Global Journal of Science Frontier Research, F: Mathematics and Decision Science, Volume 21 Issue 4

Maximum Distance Separable Codes to Order   e 0 e 1 ... e n − 1   ( f 0 , f 1 , f 2 , . . . , f n − 1 ) =   e 0 e 1 ... e n − 1   ( e 0 T , e n − 1 T , e n − 2 T , . . . , e 1 T ) = nI n Efficient encoding and decoding algorithms exist for these codes by the methods/algorithms developed in [6] which follow from those developed in [15]. In general the complexity is max { O ( n log n ) , O ( t 2 ) } where n is the length and t is the error-correcting capability, that is, t = ⌊ d − 1 2 ⌋ where d is the distance. See the algorithms in [6] for details; there the decoding algorithms are derived and are written down precisely in suitable format. The decoding algorithms reduce to finding a solution to a Hankel t × ( t + 1) systems, which can be done in O ( t 2 ) time at worst, and the other encoding and decoding algorithms are matrix multiplications which can be reduced to multiplication by a Fourier matrix which takes O ( n log n ) time. Suppose it is required to construct MDS ( n, r ) codes for given n and r . First construct a n × n Fourier matrix over a finite field. A Fourier n × n matrix is constructible over a finite field of characteristic p where p 6 | n , see section 3.9. Take r rows in sequence with arithmetic difference k satisfying gcd( n, k ) = 1 from this Fourier matrix. Then by Theorem 2.1, see [6] for details, the code generated by these rows is an ( n, r ) MDS code. There are many different ways for constructing the ( n, r ) code from the Fourier n × n matrix – one could start at any row with k = 1 and could also start at any row for any k satisfying ( n, k ) = 1. A check matrix may be read off immediately from section 2 and a direct decoding algorithm of complexity max { O ( n log n ) , O ( t 2 ) } is given in [6], where t is the error-correcting capability. Suppose it is required to construct an MDS code of rate R and to required error-correcting capability. The required code is of the form ( n, r ) with ( n − r +1) ≥ (2 t +1) where t is the required error-correcting capability. Now ( n − r + 1) ≥ (2 t + 1) requires n (1 − R ) ≥ 2 t . Thus require n ≥ 2 t 1 − R . With these requirements construct the Fourier n × n and from this take r ≥ nR rows in arithmetic sequence with arithmetic difference k satisfying gcd( n, k ) = 1. The code constructed has the required parameters. The finite fields over which this Fourier matrix can be constructed is deduced from section 3.9. Samples It is required to construct a rate R = 7 8 code which can correct 25 errors. Thus, from general form n ≥ 2 t 1 − R , require n ≥ 50 1 8 and so n ≥ 400. Consider n = 400. Construct a Fourier 400 × 400 matrix F 400 over a suitable finite field. Then r = 350 for rate 7 8 . Now take any 350 rows in sequence from F 400 with arithmetic difference k satisfying gcd(400 , k ) = 1. Now k = 1 starting at first row works in any case but there are many more which are suitable. The code generated by these rows is an (400 , 350 , 51) code, Theorem 2.1, which can correct 25 errors. Over which fields can the Fourier 400 × 400 matrix exist? The characteristic of the field must not divide 400 but finite fields of any other characteristic exist over which the Fourier 400 × 400 matrix is constructible. For example: the order of 3 mod 400 is 20 so GF (3 20 ) is suitable; the order of 7 mod 400 is 4 so GF (7 4 ) is suitable. Exercise: Which other fields are suitable? However 401 is prime and the order of 401 mod 400 is 1 and thus the prime field GF (401) is suitable. It is also easy to find a primitive 400 root of unity in GF (401); indeed the order of ω = (3 mod 401) is 1 Global Journal of Science Frontier Research Volume XXI Issue IV Year 2021 5 ( F ) © 2021 Global Journals Version I Thus 400 in GF (401) and this element may be used to generate the 400 × 400 Fourier matrix over GF (401). The arithmetic is modular arithmetic in Z 401 = GF (401). 1 A field of characteristic 2 close to the requirements may be prescribed. Then let n = 399 and note that the order of 2 mod 399 is 18. Thus use the field GF (2 18 ) over which the Fourier 399 × 399 matrix c) Complexity III. M aximum D istance S eparable C odes a) Given n, r b) MDS to required rate and error-correcting capability 6. Ted Hurley and Donny Hurley, “ Coding theory: the unit-derived methodology ” , Int. J. Information and Coding Theory, Vol. 5, no.1, 55-80, 2018. R ef