A.M. Veresova1, A.A. Ovchinnikov2

1,2 Saint-Petersburg State University of Aerospace Instrumentation (St. Petersburg, Russia)

In modern communications, low-density parity-check codes are widely used to provide the reliability of transmission. To choose effective methods of encoding and decoding, it is necessary to build a mathematical model of the channel. Due to the simplicity of the analysis, it is often assumed that errors in the channel occur independently of each other, but in reality, most errors are grouped in nature. Models with a finite number of states are used to describe such channels. An example of such a model is the Gilbert-Elliott channel, which has two states, bad (B) and good (G), for which 0<...<1. In such channels, it can be assumed that errors are grouped according to the time that channel was in bad state, and each such group will be considered an error burst. This model can describe both channels with single error bursts and multiple ones.

There is an algorithm for decoding block-permutation low-density parity-check codes that allows you to correct single error bursts.

However, due to the tendency to increase the length of the codes used, it becomes possible that several bursts occur at the length of the codeword, and in this case this algorithm will not be able to correct them.

The classical algorithm for decoding low-density codes – Belief-Propagation – can be used in a channel with memory, but errors will be considered as independent, that is, the channel memory will not be taken into account. This algorithm uses a representation of the code in the form of a Tanner graph and consists in forwarding messages along the edges of this graph. Eckford suggested using the same approach to describe the Gilbert-Elliott channel and combining this graph with the Tanner graph. Thus, there is some evaluation of the channel states, which is used to make a decision in the BP algorithm.

For this modification, experiments were performed, consisting in modeling the transmission of various codes over the Gilbert channel with different sets of parameters. Experiments have shown that the channel state estimation can significantly reduce the probability of error for a wide range of parameters if the channel is characterized by frequent changes of states. However, in a channel with mostly single error packets, there is no improvement compared to the classic BPA.

Thus, the problem of efficient decoding of low-density codes in memory channels remains open.

Veresova A.M., Ovchinnikov A.A. Usage of low-density parity-check codes in channels with memory with different number of error bursts. Science Intensive Technologies. 2021. V. 22. № 8. P. 34−40. DOI: https://doi.org/10.18127/j19998465-202108-07 (in Russian)

1. Krouk E., Semenov S. Modulation and Coding Techniques in Wireless Communications. Chichester, UK: John Wiley & Sons, Ltd. 2011. 680 p.
2. Ivaniš P., Drajić D. Information Theory and Coding – Solved Problems. Cham: Springer International Publishing. 2017.
3. Kudryashov B.D. Teoriya informacii: Uchebnik dlya vuzov. SPb.: Piter. 2009. 320 s. (in Russian).
4. Gallager R.G. Information theory and reliable communication. New York: John Wiley & Sons, Inc. 1968. 608 p.
5. Kemeny J.G., Snell J.L. Finite markov chains: with a new appendix “generalization of a fundamental matrix”: Undergraduate texts in mathematics. 3-rd ed. New York: Springer. 1983. 224 p.
6. Gilbert E.N. Capacity of a Burst-Noise Channel. The Bell System Technical Journal. 1960. V. 39. № 5. P. 1253–1265.
7. Elliott E.O. Estimates of Error Rates for Codes on Burst-Noise Channels. The Bell System Technical Journal. 1963. V. 42. № 5. P. 1977–1997.
8. Gallager R.G. Low Density Parity Check Codes. Cambridge, MA: MIT Press. 1963. 90 p.
9. Ryan W.E., Lin S. Channel Codes: Classical and Modern. New York: Cambridge University Press. 2009. 710 p.
10. Ivanov D.O., Kozlov A.V., Ovchinnikov A.A. Ob odnoj konstrukcii kodov s maloj plotnost'yu proverok na chetnost' s ciklicheskoj strukturoj makroblokov. Informacionno-upravlyayushchie sistemy. 2017. № 2 (87). S. 58–66 (in Russian).
11. Xiao-Yu Hu, Eleftheriou E., Arnold D.M. Regular and irregular progressive edge-growth tanner graphs. IEEE Transactions on Information Theory. 2005. V. 51. № 1. P. 386–398.
12. Zyablov V.V., Pinsker M.S. Ocenka slozhnosti ispravleniya oshibok nizkoplotnostnymi kodami Gallagera. Problemy peredachi informacii. 1975. T. 11. № 1. S. 23–36 (in Russian).
13. Eckford A.W., Kschischang F.R., Pasupathy S. Analysis of Low-Density Parity-Check Codes for the Gilbert–Elliott Channel. IEEE Transactions on Information Theory. 2005. V. 51. № 11. P. 3872–3889.
14. Veresova A.M., Ovchinnikov A.A. About One Algorithm For Correcting Bursts Using Block-Permutation LDPC-Codes. 2019 Wave Electronics and its Application in Information and Telecommunication Systems (WECONF). St.-Petersburg. Russia. 2019. P. 1–4.