Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Wave Electronics and its Application in Information and Telecommunication Systems (WECONF)

About the peculiarities of searching for Information Sets of Block-Permutation LDPC-Codes when Correcting Error Bursts

M. N. Isaeva, Andrei A. Ovchinnikov

Published May 29, 2023• 1 citation
Publisher

Abstract

Modern communication standards use error-correcting coding, especially LDPC codes. Various algorithms are used to decode them, including decoding by information sets. The algorithm for decoding over information sets has exponential complexity. Errors may occur on any communication channel when transmitting messages. Traditionally, independent errors are considered when researching decoding algorithms. However, in real systems, errors are grouped into bursts. This article discusses the probability of detecting information sets while correcting error bursts. Random matrices and block permutation matrices are considered. Graphs of the dependence of the probability of finding information sets on the number of positions that are considered when searching for information sets are given.

DOI
10.1109/weconf57201.2023.10148016

Related papers

FINDING INFORMATION SETS WHEN CORRECTING ERROR BURSTS WITH QUASI-CYCLIC CODES

M. N. Isaeva

This article discusses the question of assessing the probability of finding information sets in block-permutation and block-circulant matrices. Traditionally, interference-resistant coding is considered independent errors, however, in real systems they can be grouped and generate a so-called error burst. Known estimates of the probability of finding information sets are conducted for random matrices, and for correcting error bursts widespread block-permutation low density parity check codes (LDPC-codes) or block-circulant quasi cyclic codes (QC-codes) can be used. To estimate the probability of finding information sets mathematical modeling was used. Experiments have been carried out to identify parameters for specific structures that give the greatest probability of finding information sets. The article presents the results reflecting certain features in the values of the probability of finding information sets for matrices of different types, given assumptions and hypotheses about the features. Dependence of the presence of an information set from the size and location of its search interval inside the block permutation matrix was identified. The results of this research may be used to reduce the complexity of decoding by information sets, which, when considering random matrices, is exponential.

T-Comm - Телекоммуникации и Транспорт•Jan 1, 2023•3 citations

Development of dense information sets for Gilbert codes and its extensions

M. N. Isaeva

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.

Scientific and technical journal of information technologies mechanics and optics•Apr 24, 2025•2 citations

About One Algorithm for Correcting Bursts Using Block-Permutation LDPC-Codes

Вересова Алина Максимовна, Andrei A. Ovchinnikov

The approaches to decoding block-permutation low-density parity-check codes in channels with memory are considered. The modification of windowed bit-flipping algorithm for bursty channels is proposed, which is guaranteed to correct bursts within the correcting capabilities of the code. The method of determining the position of bursts is proposed. The simulation results in a memory channel with a limit on the burst length are presented.

Wave Electronics and its Application in Information and Telecommunication Systems (WECONF)•Jun 1, 2019•19 citations

Burst Detection and Correction for Gilbert Codes and its QC-LDPC Extensions

Вересова Алина Максимовна, Andrei A. Ovchinnikov

The article discusses the issue of determining the location of an error burst based on the structure of a block-permutation low-density parity-check code. Quasi-cyclic low-density parity-check codes with a small number of blocks are considered, making it possible to correct the longest possible bursts within this construction. Through experimentation, the maximum, minimum, and average number of attempts was estimated when determining the start position of the error burst. The features of determining the location of a packet in block-permutation low-density parity-check codes are revealed. The proposed method is based on using majority decoding techniques and allows reducing the average number of attempts to locate a burst from hundreds to units for the codes under consideration. Using the packet detection method, which is based on the analysis of the structure of the parity-check matrix, algorithms for decoding Gilbert and extended Gilbert codes have been proposed, ensuring the correction of bursts within their error-correction capabilities. The process of decoding extended Gilbert codes utilizes list decoding in a supercode, with a criterion for selecting the error vector based on the syndrome.

International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON)•Sep 30, 2024•2 citations

About Constructing Block Permutation LDPC Codes for Channels with Memory

Anna A. Fominykh, M. N. Isaeva, Andrei A. Ovchinnikov

This article examines constructing block-permutation low-density parity-check codes for error burst correction. Block-permutation constructions with superimposed zero masks are considered. We have analyzed the approach of construction such matrices consisting of two stages: finding the location of zero blocks and finding the base matrix. Experimental results containing analysis of correction capability of considered codes over the channel with memory are presented.

Wave Electronics and its Application in Information and Telecommunication Systems (WECONF)•May 31, 2021•2 citations

Decoding of linear codes for single error bursts correction based on the determination of certain events

Andrei A. Ovchinnikov, Вересова Алина Максимовна, Anna A. Fominykh

Introduction: In modern systems for communication, data storage and processing the error-correction capability of codes are estimated for memoryless channels. In real channels the noise is correlated, which leads to grouping error in bursts. A traditional method to fight this phenomenon is channel decorrelation, which does not allow developing of coding schemes, mostly utilizing the channel capacity. Thus the development of bursts decoding algorithms for arbitrary linear codes is the actual task. Purpose: To develop a single error burst decoding algorithm for linear codes, to estimate the decoding error probability and computational complexity. Results: Two approaches are proposed to burst error correction. The first one is based on combining the window sliding modification of well-known bit-flipping algorithm with preliminary analysis of the structure of parity check matrix. The second one is based on the recursive procedure of constructing the sequence of certain events which, in the worst case, performs the exhaustive search of error bursts, but in many cases the search may be significantly decreased by using the proposed heuristics. The proposed recursive decoding algorithm allows a guaranteed correction of any single error bursts within burst-correction capability of the code, and in many cases beyond the burst-correction capability. The complexity of this algorithm is significantly lower than that of a bit flipping algorithm if the parity-check matrix of the code is sparse enough. An alternative hybrid decoding algorithm is proposed utilizing the bit-flipping approach and showing the error probability and completion time comparable to the recursive algorithm, however, in this case the possibility of a guaranteed burst correction hardly can be proved. Practical relevance: The proposed decoding methods may be used in modern and perspective communication systems, allowing energy saving and increasing reliability of data transmission by better error performance and computational complexity.

Информационно-управляющие системы•Dec 27, 2022•10 citations
Modern communication standards use error-correcting coding, especially LDPC codes. Various algorithms are used to decode them, including decoding by information sets. The algorithm for decoding over information sets has exponential complexity. Errors may occur on any communication channel when transmitting messages. Traditionally, independent errors are considered when researching decoding algorithms. However, in real systems, errors are grouped into bursts. This article discusses the probability of detecting information sets while correcting error bursts. Random matrices and block permutation matrices are considered. Graphs of the dependence of the probability of finding information sets on the number of positions that are considered when searching for information sets are given.
This article discusses the question of assessing the probability of finding information sets in block-permutation and block-circulant matrices. Traditionally, interference-resistant coding is considered independent errors, however, in real systems they can be grouped and generate a so-called error burst. Known estimates of the probability of finding information sets are conducted for random matrices, and for correcting error bursts widespread block-permutation low density parity check codes (LDPC-codes) or block-circulant quasi cyclic codes (QC-codes) can be used. To estimate the probability of finding information sets mathematical modeling was used. Experiments have been carried out to identify parameters for specific structures that give the greatest probability of finding information sets. The article presents the results reflecting certain features in the values of the probability of finding information sets for matrices of different types, given assumptions and hypotheses about the features. Dependence of the presence of an information set from the size and location of its search interval inside the block permutation matrix was identified. The results of this research may be used to reduce the complexity of decoding by information sets, which, when considering random matrices, is exponential.
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.
The article discusses the issue of determining the location of an error burst based on the structure of a block-permutation low-density parity-check code. Quasi-cyclic low-density parity-check codes with a small number of blocks are considered, making it possible to correct the longest possible bursts within this construction. Through experimentation, the maximum, minimum, and average number of attempts was estimated when determining the start position of the error burst. The features of determining the location of a packet in block-permutation low-density parity-check codes are revealed. The proposed method is based on using majority decoding techniques and allows reducing the average number of attempts to locate a burst from hundreds to units for the codes under consideration. Using the packet detection method, which is based on the analysis of the structure of the parity-check matrix, algorithms for decoding Gilbert and extended Gilbert codes have been proposed, ensuring the correction of bursts within their error-correction capabilities. The process of decoding extended Gilbert codes utilizes list decoding in a supercode, with a criterion for selecting the error vector based on the syndrome.
Introduction: In modern systems for communication, data storage and processing the error-correction capability of codes are estimated for memoryless channels. In real channels the noise is correlated, which leads to grouping error in bursts. A traditional method to fight this phenomenon is channel decorrelation, which does not allow developing of coding schemes, mostly utilizing the channel capacity. Thus the development of bursts decoding algorithms for arbitrary linear codes is the actual task. Purpose: To develop a single error burst decoding algorithm for linear codes, to estimate the decoding error probability and computational complexity. Results: Two approaches are proposed to burst error correction. The first one is based on combining the window sliding modification of well-known bit-flipping algorithm with preliminary analysis of the structure of parity check matrix. The second one is based on the recursive procedure of constructing the sequence of certain events which, in the worst case, performs the exhaustive search of error bursts, but in many cases the search may be significantly decreased by using the proposed heuristics. The proposed recursive decoding algorithm allows a guaranteed correction of any single error bursts within burst-correction capability of the code, and in many cases beyond the burst-correction capability. The complexity of this algorithm is significantly lower than that of a bit flipping algorithm if the parity-check matrix of the code is sparse enough. An alternative hybrid decoding algorithm is proposed utilizing the bit-flipping approach and showing the error probability and completion time comparable to the recursive algorithm, however, in this case the possibility of a guaranteed burst correction hardly can be proved. Practical relevance: The proposed decoding methods may be used in modern and perspective communication systems, allowing energy saving and increasing reliability of data transmission by better error performance and computational complexity.