Correction of single error bursts beyond the code correction capability using information sets
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 met...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Saint Petersburg National Research University of Information Technologies, Mechanics and Optics (ITMO University)
2024-02-01
|
| Series: | Naučno-tehničeskij Vestnik Informacionnyh Tehnologij, Mehaniki i Optiki |
| Subjects: | |
| Online Access: | https://ntv.ifmo.ru/file/article/22587.pdf |
| _version_ | 1797315420503408640 |
|---|---|
| author | Maria N. Isaeva Andrei A. Ovchinnikov |
| author_facet | Maria N. Isaeva Andrei A. Ovchinnikov |
| author_sort | Maria N. Isaeva |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-08T03:01:32Z |
| format | Article |
| id | doaj.art-f10b0dd999a14cdcaa3e2f16da4a0a52 |
| institution | Directory Open Access Journal |
| issn | 2226-1494 2500-0373 |
| language | English |
| last_indexed | 2024-03-08T03:01:32Z |
| publishDate | 2024-02-01 |
| publisher | Saint Petersburg National Research University of Information Technologies, Mechanics and Optics (ITMO University) |
| record_format | Article |
| series | Naučno-tehničeskij Vestnik Informacionnyh Tehnologij, Mehaniki i Optiki |
| spelling | doaj.art-f10b0dd999a14cdcaa3e2f16da4a0a522024-02-13T10:51:33ZengSaint Petersburg National Research University of Information Technologies, Mechanics and Optics (ITMO University)Naučno-tehničeskij Vestnik Informacionnyh Tehnologij, Mehaniki i Optiki2226-14942500-03732024-02-01241708010.17586/2226-1494-2024-24-1-70-80Correction of single error bursts beyond the code correction capability using information setsMaria N. Isaeva0https://orcid.org/0009-0007-6228-0617Andrei A. Ovchinnikov1https://orcid.org/0000-0002-8523-9429Junior Researcher, HSE University, Saint Petersburg, 190008, Russian Federation, sc 57243599200PhD, Associate Professor, Leading Researcher, HSE University, Saint Petersburg, 190008, Russian Federation, sc 57207711162The 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.https://ntv.ifmo.ru/file/article/22587.pdfinformation setserror correcting capabilitylow-density parity-check codeschannels with memoryerror bursts |
| spellingShingle | Maria N. Isaeva Andrei A. Ovchinnikov Correction of single error bursts beyond the code correction capability using information sets Naučno-tehničeskij Vestnik Informacionnyh Tehnologij, Mehaniki i Optiki information sets error correcting capability low-density parity-check codes channels with memory error bursts |
| title | Correction of single error bursts beyond the code correction capability using information sets |
| title_full | Correction of single error bursts beyond the code correction capability using information sets |
| title_fullStr | Correction of single error bursts beyond the code correction capability using information sets |
| title_full_unstemmed | Correction of single error bursts beyond the code correction capability using information sets |
| title_short | Correction of single error bursts beyond the code correction capability using information sets |
| title_sort | correction of single error bursts beyond the code correction capability using information sets |
| topic | information sets error correcting capability low-density parity-check codes channels with memory error bursts |
| url | https://ntv.ifmo.ru/file/article/22587.pdf |
| work_keys_str_mv | AT marianisaeva correctionofsingleerrorburstsbeyondthecodecorrectioncapabilityusinginformationsets AT andreiaovchinnikov correctionofsingleerrorburstsbeyondthecodecorrectioncapabilityusinginformationsets |