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

Series of MDS codes over prime fields GF ( p ) = Z p are constructed such that the ratio of the distance to the length approaches (1 − R ) for given R, 0 < R < 1; in these cases the arithmetic is modular arithmetic which is extremely efficient and easy to implement, section 3.5. Samples are given in the different sections and an example is given on the workings of the decoding algorithms in section 3.6.1. The explicit examples given need to be of reasonably small size for display here but in general there is no restriction on the length or dimension in practice. Maximum Distance Separable Codes to Order Explicit efficient encoding and decoding algorithms of complexity max { O ( n log n ) , O ( t 2 ) } exist for the codes and this is explained in section 2.3. The codes are encompassing and excel known used and practical codes. See for example section 3.8 for the following: MDS codes of the form (255 , r ) for any r, 1 ≤ r ≤ 255 are constructed over GF (2 8 ). They are constructed explicitly and have efficient encoding and decoding algorithms which reduce to finding a solution of a Hankel t × ( t + 1) system, where t is the error-correcting capability, and matrix multiplications by a Fourier matrix. These can be compared to the Reed-Solomon codes over GF (2 8 ). The method extends easily to the formation of MDS codes of the form (511 , r ) for any r, 1 ≤ r ≤ 511 over GF (2 9 ), and then further to MDS codes (2 k − 1 , r ) over GF (2 k ). Codes over prime fields are particularly nice and as an example (256 , r ) codes are constructed over GF (257) = Z 257 . The arithmetic is modular arithmetic over Z 257 ; these perform better than the (255 , r ) RS codes over GF (2 8 ). These can also easily be extended for larger primes as for example (10008 , r ) MDS codes over GF (10009). In general: For any prime p , ( p − 1 , r ) codes over GF ( p ) = Z p are constructed for any r, 1 ≤ r ≤ ( p − 1); for any k , (2 k − 1 , r ) codes are constructed over GF (2 k ) and any r, 1 ≤ r ≤ (2 k − 1). As already noted the constructed codes have (very) efficient encoding and decoding algorithms. The encoding and decoding methods involve multiplications by a Fourier matrix and finding a solution to a Hankel t × ( t + 1) system, where t is the error-correcting capability of the MDS code. Background on coding theory and field theory may be found in [1], [17] or [18]. An ( n, r ) linear code is a linear code of length n and dimension r ; the rate of the code is r n . An ( n, r, d ) linear code is a code of length n , dimension r and (minimum) distance d . The code is an MDS code provided d = ( n − r + 1), which is the maximum distance an ( n, r ) code can attain. The error-capability of ( n, r, d ) is t = ⌊ d − 1 2 ⌋ which is the maximum number of errors the code can correct successfully. The finite field of order q is denoted by GF ( q ) and of necessity q is a power of a prime. The codes are generated by the unit-derived method – see [9, 11, 16] – by choosing rows in se- quence of Fourier/Vandermonde matrices over finite fields following the methods developed in [6, 7]. They are easy to implement, explicit and with efficient encoding and decoding algorithms of complexity max { ( O log n ) , O ( t 2 ) where t is the error-correcting capability. Different types of MDS codes, such as Quantum or Linearly complementary dual (LCD) codes, can be constructed based on general schemes; see section 3.9.1 for references on these developments. This section also notes a reference to using these types of error-correcting codes in solving underdetermined systems of equations for compressed sensing applications. In [9, 16] systems of unit-derived codes are developed; a suitable version in book chapter form is available at [11]. In summary the unit-derived codes are obtained as follows. Let UV = I n in a ring. Let G be the r × n matrix generated by choosing any r rows of U and let H T be the n × ( n − r ) matrix obtained from V by eliminating the corresponding columns of V . Then G generates an ( n, r ) code and H is the the check matrix of the code. The system can be considered in format as GH T = 0 r × ( n − r ) . When the first rows are chosen as generator matrix, the process may be presented as follows. Let UV = I n with U = A B , V = ( C, D ) where A is an r × n matrix, B is an ( n − r ) × n matrix, C is an n × r matrix and D is an n × ( n − r ) matrix. Then UV = I gives A B ( C, D ) = I r 0 0 I n − r and so in © 2021 Global Journals 1 Global Journal of Science Frontier Research Volume XXI Issue IV Year 2021 2 ( F ) Version I a) Particular types of MDS codes II. C onstructions a) Background material 1. Richard E. Blahut, Algebraic Codes for data transmission, Cambridge University Press, 2003. R ef