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

Maximum Distance Separable Codes to Order 3. 2 5 − 1 = 31. From the Fourier 31 × 31 matrix over GF (2 5 ) construct the MDS { (31 , 29 , 3) , (31 , 27 , 5) , (31 , 25 , 7) , . . ., (31 , 3 , 29) , (31 , 1 , 31) } codes which can respectively cor- rect { 1 , 2 , 3 , . . . , 14 , 15 } errors. 4. 2 8 − 1 = 255. Thus MDS codes (255 , r ) are constructed over GF (2 8 ) for all r . These could be compared to Reed-Solomon codes used in practice and perform better. Even further consider 2 9 − 1 = 511. Then MDS codes (511 , r ) are constructed over GF (2 9 ). For example (511 , 495 , 17) , (511 , 487 , 25) codes are constructed over GF (2 9 ); the decoding algorithm involves finding a solution to 9 × 8, 13 × 12 (respectively) Hankel systems of equations, and matrix Fourier multiplication. The codes over prime fields in section 3.8 of length 256 over GF (257) = Z 257 and of length 508 over GF (509) = Z 509 perform better. 5. . . . . . . 6. General 2 q − 1 = n . From the Fourier n × n matrix over GF (2 q ) construct the MDS ( n, n − 2 , 3) , ( n, n − 4 , 5) , ( n, n − 6 , 7) , . . . , ( n, n − 2 m, 2 m + 1) , . . . , ( n, 3 , n − 2) , ( n, 1 , n ) codes which can correct respectively { 1 , 2 , 3 , . . . , m, . . . , n − 3 2 , n − 1 2 } errors. It is clear that similar series of relatively large length MDS codes may be constructed over finite fields of characteristics other than 2. Z p Construct large length MDS codes over prime fields. This is a particular general case of section 3.7 but is singled out as the arithmetic involved, modular arithmetic, is smooth and very efficient and the examples are nice and practical. For any prime p the Fourier ( p − 1) × ( p − 1) matrix exists over GF ( p ) = Z p . A primitive ( p − 1) root of unity is required in GF ( p ) 3 . The arithmetic is modular arithmetic in Z p which is nice. The general method then allows the construction of MDS ( p − 1 , r ) codes over GF ( p ) for any 1 ≤ r ≤ ( p − 1). It is better to use even r , so that the distance is then odd – for p > 2. Here are samples: 1. p = 11. Then MDS codes of the form { (10 , 8 , 3) , (10 , 6 , 5) , (10 , 4 , 7) , (10 , 2 , 9) } are constructed over GF (11) = Z 11 . They can respectively correct { 1 , 2 , 3 , 4 } errors. A primitive 10 th root of unity is (2 mod 11); also (7 mod 11) is a primitive 10 th root of unity. The method allows the construction of (at least) φ (11) = 10 MDS (12 , r ) codes for each r . 2. p = 13. Then MDS codes of the forms { (12 , 10 , 3) , (12 , 8 , 5) , (12 , 6 , 7) , (12 , 4 , 9) , (12 , 2 , 11) } are constructed over GF (13) = Z 13 which can correct respectively { 1 , 2 , 3 , 4 , 5 } errors. A primitive 12 th root of unity is (2 mod 13) or (7 mod 13). 3. p = 17. Then MDS codes of the forms { (16 , 14 , 3) , (16 , 12 , 5) , (16 , 10 , 7) , (16 , 8 , 9) , (16 , 6 , 11) , (16 , 4 , 13) , (16 , 2 , 15) } which can correct respec- tively { 1 , 2 , 3 , 4 , 5 , 6 , 7 } errors are constructed over GF (17) = Z 17 . A primitive 16 th root of unity in GF (17) is (3 mod 17) or (5 mod 17) and there are φ (16) = 8 such generators. 4. . . . . . . 5. Relatively large sample with modular arithmetic: for comparison. Consider GF (257) = Z 257 and 257 is prime. Construct the Fourier matrix F 256 with a primitive 256 th root of unity ω in GF (257). Since the order of 3 mod 257 is 256 then a choice for ω is (3 mod 257). Denote the rows of F 256 in order by { e 0 , e 1 , . . . , e 255 } . Suppose a dimension r is required. Choose C = h e 0 , e 1 , . . . , e r − 1 i to get an MDS (256 , r ) code. The arithmetic is modular arithmetic, mod 257, and work is done with powers of (3 mod 257). 1 Global Journal of Science Frontier Research Volume XXI Issue IV Year 2021 9 ( F ) © 2021 Global Journals Version I h) Length ( − 1) codes in prime field GF( ) = 3 It seems there is no known algorithm in which to find a generator of ( ) that is substantially better than a bruteforce method - see Keith Conrad’s notes [4]. Note however there are precisely 1) primitive ( 1) roots of unity in Z p / { 0 } φ ( p − p − GF ( p ) = Z p . N otes