Iterative Shaping of Error Patterns For Normal Syndrome Decoding of Iterative Codes

The problem of two-dimensional syndrome-norm decoding of iterative codes based on a library of error patterns is considered. In two-dimensional coding, sequence code is first transformed into a code matrix, and then the row and column check code are calculated. In the decoder, the error position of the twodimensional can be obtained by the operations that first calculate the syndromes and norms, then match with the error patterns in the existing library. The error pattern library is stored in the memory and generated by the subset of the error pattern. Subset patterns are generated from the base pattern using row and column permutations. The norm calculated based on the syndrome unambiguously determines the base pattern and the corresponding subset of error patterns, which reduces the search space for the syndrome to a subset. In this case, the syndrome is used as an address for retrieving a specific error pattern and correction rule from the memory. With the error rate increased, the size of the error pattern library is raised and the computational complexity of its formation is enlarged. As a result, the known methods for generating the error pattern library become non sufficient. This paper proposed a mathematical model, a generator structure, and an algorithm for fast generation of an error pattern library based on the iterative expansion of the error patterns, which makes it possible to reduce the number of generated redundant error patterns by orders of magnitude and significantly shorten the computational complexity in comparison with the known approaches.

1. Elias P. Error-free coding. IEEE Trans Inf Theory. 1954;4(4):29-37.

2. Shu L., Daniel J C., Jr. Error Control Coding, Second Edition. 2004:44-63.

3. Hamming R.W. Error Detecting and Error Correcting Codes. Bell Syst. Tech. J. 1950;29(1):47-600.

4. Fu B., Ampadu P. On hamming product codes with type-II hybrid ARQ for on-chip interconnects. IEEE Trans Circuits Syst I, Reg Papers. 2009;56(9):2042-2054.

5. Pham khac Hoan., Smolyakova O. G., Konopelko V.K. [Optimizing parameters of iterated codes with adaptive three-phase decoding]. Doklady BGUIR = Doklady BGUIR. 2009;1(39):86-92. (In Russ.)

6. Peterson W.W. Encoding and Error-Correction Procedures for the Bose-Chaudhuri Codes. IRE Trans. Inform. Theory, IT-6. 1960;4:59-70.

7. Chien R.T. Cyclic Decoding Procedure for the Bose-Chaudhuri-Hocquenghem Codes. IEEE Trans. Inform. Theory, IT-IO. 1964;3:57-63.

8. Berlekamp E.R. Algebraic Coding Theory. McGraw-Hill, New York; 1968.

9. Lipnitski V.A., Konopelko V.K. [The theory of syndrome norms in the permutation decoding action unjammable codes]. Doklady BGUIR = Doklady BGUIR. 2000;1(1):146-157. (In Russ.)

10. Konopelko V.K., Lipnitski A.V., Spichekova N.V. [Point pattern classification and classical number partition problem]. Doklady BGUIR = Doklady BGUIR. 2010;5(51):112-117. (In Russ.)

11. Tsvetkov V.Y., Konopelko V.K., Lipnitski A.V. [Prediction, recognition, and pattern formation of multiangle patterns from moving objects]. Minsk, 2014;181-219. (In Russ.)

12. Smolyakova O.G., Konopelko V.K. [Classification vectors of errors at two-dimensional coding of the information]. Doklady BGUIR = Doklady BGUIR. 2008;7(37):19-28. (In Russ.)