Menu
Publications
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Editor-in-Chief
Nikiforov
Vladimir O.
D.Sc., Prof.
Partners
doi: 10.17586/2226-1494-2024-24-1-70-80
Correction of single error bursts beyond the code correction capability using information sets
Read the full article
';
Article in Russian
For citation:
Abstract
For citation:
Isaeva M.N., Ovchinnikov A.A. Correction of single error bursts beyond the code correction capability using information sets. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2024, vol. 24, no. 1, pp. 70–80 (in Russian). doi: 10.17586/2226-1494-2024-24-1-70-80
Abstract
The most important method of ensuring data integrity is correcting errors that occur during information storage, processing or transmission. The error-correcting coding methods are used to correct errors. In real systems, noise processes are correlated. However, traditional coding and decoding methods use decorrelation, and it is known that this procedure reduces the maximum achievable characteristics of coding. Thus, constructing computationally efficient decoding methods that would correct grouped errors for a wide class of codes is an actual problem. In this paper the decoding by information sets is used to correct single bursts. This method has exponential complexity when correcting independent errors. The proposed approach uses a number of information sets linearly growing with code length, which provides polynomial decoding complexity. A further reduction of the number of information sets is possible with the proposed method of using dense information sets. It allows evaluating both the set of errors potentially corrected by the code and the characteristics of the decoder. An improvement of the decoding method using an error vector counter is proposed, which allows in some cases to increase the number of corrected error vectors. This method allows significantly reducing the number of information sets or increasing the number of corrected error vectors according to the minimum burst length criterion. The proposed decoders allow correction of single error bursts in polynomial time for arbitrary linear codes. The results of experiments based on standard array show that decoders not only correct all errors within the burst correcting capability of the code, but also a significant number of error vectors beyond of it. Possible directions of further research are the analysis of the proposed decoding algorithms for long codes where the method of analysis based on the standard array is not applicable; the development and analysis of decoding methods for multiple bursts and the joint correction of grouped and random errors.
Keywords: information sets, error correcting capability, low-density parity-check codes, channels with memory, error bursts
Acknowledgements. The article was prepared within the framework of the Basic Research Program at HSE University, Internet of Things and Cyber-Physical Systems Laboratory, St. Petersburg School of Physics, Mathematics, and Computer Science.
References
Acknowledgements. The article was prepared within the framework of the Basic Research Program at HSE University, Internet of Things and Cyber-Physical Systems Laboratory, St. Petersburg School of Physics, Mathematics, and Computer Science.
References
- Bogatyrev V.A., Bogatyrev S.V., Bogatyrev A.V. Assessment of the readiness of a computer system for timely servicing of requests when combined with information recovery of memory after failures. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2023, vol. 23, no. 3, pp. 608–617. (in Russian). https://doi.org/10.17586/2226-1494-2023-23-3-608-617
- Moon T.K. Error Correction Coding: Mathematical Methods and Algorithms. Wiley, 2021, 992 p.
- MacWilliams F.J., Sloane N.J.A. The Theory of Error-Correcting Codes. North-Holland Publishing Company, 1983, 762 p. North-Holland Mathematical Library, Vol. 16.
- Krouk E., Ovchinnikov A., Poikonen J. Channel models and reliable communication. Modulation and Coding Techniques in Wireless Communications. Wiley, 2011, pp. 1–20. https://doi.org/10.1002/9780470976777.ch1
- Bogatyrev V.A., Bogatyrev A.V., Bogatyrev S.V. Multipath transmission of heterogeneous traffic in acceptable delays with packet replication and destruction of expired replicas in the nodes that make up the path. Communications in Computer and Information Science, 2023, vol. 1748, pp. 104–121. https://doi.org/10.1007/978-3-031-30648-8_9
- Bogatyrev V., Bogatyrev S., Bogatyrev A. Timeliness of multipath redundant transmissions when all paths are not accessible for some request sources. Studies in Systems, Decision and Control, 2023, vol. 457, pp. 671–681. https://doi.org/10.1007/978-3-031-22938-1_46
- Kulhandjian M., Kulhandjian H., D’Amours C. Improved soft decoding of Reed-Solomon codes on Gilbert-Elliott channels. Proc. of the IEEE International Symposium on Information Theory (ISIT), 2019, pp. 1072–1076. https://doi.org/10.1109/ISIT.2019.8849456
- Xie N., Zhang T., Haratsch E.F. Improving burst error tolerance of LDPC-centric coding systems in read channel. IEEE Transactions on Magnetics, 2010, vol. 46, no. 3, pp. 933–941. https://doi.org/10.1109/TMAG.2009.2034012
- Yang M., Pan Z., Djordjevic I.B. FPGA-based burst-error performance analysis and optimization of regular and irregular SD-LDPC codes for 50G-PON and beyond. Optics Express, 2023, vol. 31, no. 6, pp. 10936–10946. https://doi.org/10.1364/OE.477546
- Xiao X., Vasić B., Lin S., Li J., Abdel-Ghaffar K. Quasi-cyclic LDPC codes with parity-check matrices of column weight two or more for correcting phased bursts of erasures. IEEE Transactions on Communications, 2021, vol. 69, no. 5, pp. 2812–2823. https://doi.org/10.1109/TCOMM.2021.3059001
- Eckford A., Kschischang F., Pasupathy S. Analysis of low-density parity-check codes for the gilbert–elliott channel. IEEE Transactions on Information Theory, 2005, vol. 51, no. 11, pp. 3872–3889. https://doi.org/10.1109/TIT.2005.856934
- Ovchinnikov A., Veresova A., Fominykh A. Usage of LDPC codes in a gilbert channel. Proceedings of Telecommunication Universities, 2022, vol. 8, no. 4, pp. 55‒63. https://doi.org/10.31854/1813-324X-2022-8-4-55-63
- Ghaddar N., Kim Y.-H., Milstein L.B., Ma L., Yi B.K. Joint channel estimation and coding over channels with memory using polar codes. IEEE Transactions on Communications, 2021, vol. 69, no. 10, pp. 6575–6589. https://doi.org/10.1109/TCOMM.2021.3098822
- Ovchinnikov A.A., Veresova A.M., Fominykh A.A. Decoding of linear codes for single error bursts correction based on the determination of certain events. Information and Control Systems, 2022, no. 6, pp. 41–52. https://doi.org/10.31799/1684-8853-2022-6-41-52
- Barg A., Krouk E., van Tilborg H.C.A. On the complexity of minimum distance decoding of long linear codes. IEEE Transactions on Information Theory, 1999, vol. 45, no. 5, pp. 1392‒1405. https://doi.org/10.1109/18.771141
- Both L., May A. Optimizing BJMM with nearest neighbors: full decoding in 22/21n and McEliece security. WCC Workshop on Coding and Cryptography, 2017, vol. 214.
- Isaeva M.N. Finding information sets when correcting error bursts with quasi-cyclic codes. T-Comm, 2023, vol. 17, no. 7, pp. 4–12. (in Russian). https://doi.org/10.36724/2072-8735-2023-17-7-4-12
- Fossorier M.P.C. Quasicyclic low-density parity-check codes from circulant permutation matrices. IEEE Transactions on Information Theory, 2004, vol. 50, no. 8, pp. 1788–1793. https://doi.org/10.1109/TIT.2004.831841
- Xiao X., Vasić B., Lin S., Abdel-Ghaffar K., Ryan W.E. Reed-Solomon based quasi-cyclic LDPC codes: designs, girth, cycle structure, and reduction of short cycles. IEEE Transactions on Communications, 2019, vol. 67, no. 8, pp. 5275–5286. https://doi.org/10.1109/TCOMM.2019.2916605
- Krouk E.A., Ovchinnikov A.A. Exact burst-correction capability of gilbert codes. Information and Control Systems, 2016, no. 1, pp. 80–87. (in Russian). https://doi.org/10.15217/issn1684-8853.2016.1.80
