Development of dense information sets for Gilbert codes and its extensions

When transmitting information over channels with grouping errors, the traditional approach is channel decorrelation and use of codes correcting independent errors. The decorrelation procedure lowers achievable rates of reliable transmission, therefore the problem of using special codes for channels with memory and construction of computationally effective decoding methods for correction of grouping errors is actual. For the class of random codes, an approach is known using information sets of limited diameter to correct error bursts. The size of the set of information sets grows linearly with increasing code length, and the construction of the set is described by a probabilistic procedure. This article considers the construction of a set of information sets for a special class of codes that correct error bursts called Gilbert codes. The sets of code positions of the smallest possible diameter are considered. Based on the calculation of the ranks of the submatrices of the parity-check matrix of the Gilbert code, the probability that the set of positions is an information set is estimated. For a given location of the information set, the positions of the corrected bursts are analyzed. Based on the analysis, a method for constructing a set of dense information sets for Gilbert codes for correcting all error bursts within the code correcting capacity is proposed. Using the features of setting the parameters of Gilbert codes, an estimate of the size of the resulting set of dense information sets is carried out. For a simple block size of the paritycheck matrix of a quasi-cyclic code, it is shown that for Gilbert codes a dense information set is located at any position. In the case of extended Gilbert codes, it is shown that sets of minimum diameter exist only at the last position of each block. A procedure for constructing a set of dense information sets of minimum diameter for Gilbert codes and their extensions is proposed. A comparison is made of the set size of information sets and the probability of obtaining it for Gilbert codes and random codes. It is shown that the number of information sets obtained by the proposed procedure does not increase with the length of the code. The results obtained in the paper demonstrate the possibility of developing computationally efficient decoders based on information sets when correcting single error bursts. Unlike random linear codes, for which the methods of constructing information sets including dense ones, are probabilistic, a procedure for guaranteed construction of a set of information sets of minimal diameter is specified for Gilbert codes. The quasi-cyclic structure of Gilbert codes allows constructing sets of dense information sets of smaller dimension than for random codes. The obtained results allow us to guarantee the correction of error bursts within the correcting capacity of Gilbert codes and their extensions with low computational complexity. The use of computationally efficient procedures for encoding and decoding error bursts will improve the reliability of message delivery in channels with memory.

1. Velichko V.V., Popkov G.V., Popkov V.K. Models and Methods of Increasing the Survivability of Modern Communication Systems. Moscow, Hotline–Telecom, 2014, 270 p. (in Russian)

2. Netes V.A. Fundamentals of Reliability Theory. Moscow, Hotline– Telecom, 2024, 102 p. (in Russian)

3. Polovko A.M., Gurov S.V. Fundamentals of Reliability Theory. St. Petersburg BHVPetersburg, 2006, 704 p. (in Russian)

4. Bogatyrev A.V., Bogatyrev V.A., Bogatyrev S.V. The probability of timeliness of a fully connected exchange in a redundant real-time communication system. Proc. of the Wave Electronics and its Application in Information and Telecommunication Systems (WECONF) , 2020, pp. 1–4. https://doi.org/10.1109/weconf48837.2020.9131517

5. 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

6. Bogatyrev V.A., Bogatyrev S.V., Bogatyrev A.V. Control of multipath transmissions in the nodes of switching segments of reserved paths. Proc. of the International Conference on Information, Control, and Communication Technologies (ICCT), 2022, pp. 1–5. https://doi.org/10.1109/ICCT56057.2022.9976839

7. Lin S., Li J. Fundamentals of Classical and Modern Error-Correcting Codes. Cambridge, Cambridge University Press, 2022, 840 p.

8. Moon T.K. Error Correction Coding: Mathematical methods and algorithms. Wiley, 2020, 992 p.

9. 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

10. Xiao X., Vasic 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

11. Li L., Lv J., Li Y., Dai X., Wang X. Burst error identification method for LDPC coded systems. IEEE Communications Letters, 2024, vol. 28, no. 7, pp. 1–5. https://doi.org/10.1109/LCOMM.2024.3391826

12. Yang M., Pan Z., Djordjevic I.B. FPGA-based burst-error performance analysis and optimization of regular and irregular SDLDPC codes for 50G-PON and beyond. Optics Express, 2023, vol. 31, no. 6, pp. 10936–10946. https://doi.org/10.1364/OE.477546

13. Aharoni Z., Huleihel B., Pfister H.D., Permuter H.H. Data-Driven polar codes for unknown Channels with and without memory. Proc. of the IEEE International Symposium on Information Theory (ISIT), 2023, pp. 1890–1895.https://doi.org/10.1109 / ISIT54713.2023.10206663

14. Fang Y., Chen J. Decoding polar codes for a generalized GilbertElliott channel with unknown parameter. IEEE Transactions on Communications, 2021, vol. 69, no. 10, pp. 6455–6468. https://doi.org/10.1109/TCOMM.2021.3095195

15. 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

16. Ovchinnikov А.А., Veresova А.М., Fominykh А.А. 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

17. 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). https://doi.org/10.17586/2226-1494-2024-24-1-70-80

18. 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

19. Krouk E.A., Ovchinnikov A.A. Exact burst-correction capability of Gilbert Codes. Information and Control Systems, 2016, no. 1(80), pp. 80–87. (in Russian). https://doi.org/10.15217/issn16848853.2016.1.80

20. Veresova A., Ovchinnikov. Burst detection and correction for Gilbert Codes and its QC-LDPC extensions. Proc. of the IEEE International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), 2024, pp. 47–51. https://doi.org/10.1109/sIBIRCON63777.2024.10758475

21. Isaeva M.N. Development and analysis of a method for constructing dense information sets for error bursts correction. T-Comm, 2024, vol. 18, no. 10, pp. 20–26. (in Russian). https://doi.org/10.36724/2072-8735-2024-18-10-20-26

22. Kruk E.A., Fedorenko S.V. Decoding by generalized information sets. Problemy Peredachi Informatsii, 1995, vol. 31, no. 2, pp. 54–61. (in Russian)

23. 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

24. Graham R.L., Knuth D.E., Patashnik O. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley Professional, 1994, 672 p.