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

Maximum Distance Separable Codes to Order Then   1 1 1 . . . 1 1 ω ω 2 . . . ω n − 1 1 ω 2 ω 4 . . . ω 2( n − 1) ... ... ... . . . ... 1 ω n − 1 ω 2( n − 1) . . . ω ( n − 1)( n − 1)     1 1 1 . . . 1 1 ω n − 1 ω 2( n − 1) . . . ω ( n − 1)( n − 1) 1 ω n − 2 ω 2( n − 2) . . . ω ( n − 1)( n − 2) ... ... ... . . . ... 1 ω ω 2 . . . ω ( n − 1)   = nI n Hence F n F ∗ n = nI n where F ∗ n denotes the second matrix on the left of the equation. Replacing ω by ω n − 1 in F n is seen to give this F ∗ n which itself is a Fourier matrix. Refer to section 3.9 for results on which fields contain an n th root of unity but in any case an n th root of unity can only exist in a field whose characteristic does not divide n . The following theorem on deriving MDS codes from Fourier matrices by unit-derived scheme is contained in [6]: [6] (i) Let F n be a Fourier n × n matrix over a field F . Let C be the unit-derived code obtained by choosing in order r rows of V in arithmetic sequence with arithmetic difference k and gcd( n, k ) = 1 . Then C is an MDS ( n, r, n − r + 1) code. In particular this is true when k = 1 , that is when the r rows are chosen in succession. (ii) Let C be as in part (i). Then there exist efficient encoding and decoding algorithms for C . There is a similar, more general in some ways, theorem for Vandermonde matrices: [6] Let V = V ( x 1 , x 2 , . . . , x n ) be a Vandermonde n × n matrix over a field F with distinct and non-zero x i . Let C be the unit-derived code obtained by choosing in order r rows of V in arithmetic sequence with difference k . If ( x i x − 1 j ) is not a k th root of unity for i 6 = j then C is an ( n, r, n − r + 1) mds code over F . In particular the result holds for consecutive rows as then k = 1 and x i 6 = x j for i 6 = j . These are fundamental results. For ‘rows in sequence’ in the Fourier matrix cases, Theorem 2.1, and for some Vandermonde cases, it is permitted that rows may wrap around and then e k is taken to mean e ( k mod n ) . Thus for example Theorem 2.1 could be applied to a code generated by h e r , . . . , e n − 1 , e 0 , e 1 , . . . , e s i where h e 0 , e 1 , . . . , e n − 1 i are the rows in order of a Fourier matrix. The general Vandermonde case is more difficult to deal with in practice but in any case using Fourier matrices is sufficient for coding purposes. Decoding methods for the codes produced are given in the algorithms in [6] and in particular these are particularly nice for the codes from Fourier matrices. The decoding methods are based on the decoding schemes derived in [15] in connection with compressed sensing for solving underdetermined systems using error-correcting codes. These decoding methods themselves are based on the error-correcting methods due to Pellikaan [13] which is a method of finding error-correcting pairs – error-correcting pairs are shown to exist for the constructed codes and efficient decoding algorithms are derived from this. These decoding algorithms are explicitly written down in detail in [6]. In addition the encoding itself is straightforward. The complexity of encoding and decoding is max { O ( n log n ) , O ( t 2 ) } where t = ⌊ n − r 2 ⌋ ; t is the error- correcting capability of the code. The complexity is given in Section 2.3 and is derived in [6]. Let F ∗ n denote the matrix with F n F ∗ n = nI n × n for the Fourier matrix F n . Denote the rows of F n in order by { e 0 , e 1 , . . . , e n − 1 } and denote the columns of F ∗ n in order by { f 0 , f 1 , . . . , f n − 1 } . Then it is important to note that f i = e n − i T , e i = f n − i T with the convention that suffices are taken modulo n . Also note e i f i = n and e i f j = 0 , i 6 = j . © 2021 Global Journals 1 Global Journal of Science Frontier Research Volume XXI Issue IV Year 2021 4 ( F ) Version I Theorem 2.1 Theorem 2.2 15. T. Hurley, “ Solving underdetermined systems with error correcting codes ” , Intl. J. Information and Coding Theory, Vol 4, no. 4, 201-221, 2017. R ef