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

T-Comm - Телекоммуникации и Транспорт

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

M. N. Isaeva

Published Jan 1, 2023• 3 citations
Publisher

Abstract

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.

DOI
10.36724/2072-8735-2023-17-7-4-12

Related papers

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

M. N. Isaeva, Andrei A. Ovchinnikov

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.

Wave Electronics and its Application in Information and Telecommunication Systems (WECONF)•May 29, 2023•1 citation

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

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

Quasi-cyclic LDPC codes for fast encoding

Seho Myung, Kyeongcheol Yang, Jaeyoel Kim

In this correspondence we present a special class of quasi-cyclic low-density parity-check (QC-LDPC) codes, called block-type LDPC (B-LDPC) codes, which have an efficient encoding algorithm due to the simple structure of their parity-check matrices. Since the parity-check matrix of a QC-LDPC code consists of circulant permutation matrices or the zero matrix, the required memory for storing it can be significantly reduced, as compared with randomly constructed LDPC codes. We show that the girth of a QC-LDPC code is upper-bounded by a certain number which is determined by the positions of circulant permutation matrices. The B-LDPC codes are constructed as irregular QC-LDPC codes with parity-check matrices of an almost lower triangular form so that they have an efficient encoding algorithm, good noise threshold, and low error floor. Their encoding complexity is linearly scaled regardless of the size of circulant permutation matrices.

IEEE Transactions on Information Theory•Jul 19, 2005•278 citations

Rotation-Distance Analysis of QC-LDPC Code Based on Circulant Permutation Matrices

Douglas J. Leith

Cycle distribution of LDPC(Low-Density Parity-Check) codes affects the codes decoding performance and encoding complexity,however it is commonly NP hard to analyse.We propose the rotation-distance for analysis of QC-LDPC(Quasi-Cyclic Low-Density Parity-Check) code based on circulant matrices.The circulant sub-matrices within the parity-check are treated as a matrix node to simplify theTanner graphs of the codes.Thus cycles of QC-LDPC codes can be found efficiently,and we demonstrate the usefulness of the new method by a simple proof of the known result that 12 is an upper limit of the girth of the QC-LDPC codes we considered.Moreover,the cycle analysis based on the new method also reveals relations between decoding performance and the cycle distribution of the code.

Journal of Jilin University•Jan 1, 2011•0 citations

Rank Analysis of Parity-Check Matrices for Quasi-Cyclic LDPC Codes

Po‐Chun Yang, Chung-Hsuan Wang, Chi-Chao Chao

Quasi-cyclic low-density parity-check (QC-LDPC) codes are an important class of LDPC codes which can be encoded and decoded with low complexity and suitable for many applications. As the code dimension, which describes the number of protected information bits, is equal to the code length minus the rank of the parity-check matrix and the parity-check matrix for QC-LDPC codes is usually not full-rank, determining the rank of the parity-check matrix is of essential importance. In this paper, we study the rank of the parity-check matrix for QC-LDPC codes based on the associated polynomials for circulant matrices. A formula for the rank of the parity-check matrix with only one row-block is first derived. We then extend the result to matrices with two, three, or more row-blocks. Some bounds are also presented for matrices with arbitrary numbers of row-blocks. Furthermore, the exact rank is determined for a class of algebraically constructed parity-check matrices.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•5 citations
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.
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.
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.
In this correspondence we present a special class of quasi-cyclic low-density parity-check (QC-LDPC) codes, called block-type LDPC (B-LDPC) codes, which have an efficient encoding algorithm due to the simple structure of their parity-check matrices. Since the parity-check matrix of a QC-LDPC code consists of circulant permutation matrices or the zero matrix, the required memory for storing it can be significantly reduced, as compared with randomly constructed LDPC codes. We show that the girth of a QC-LDPC code is upper-bounded by a certain number which is determined by the positions of circulant permutation matrices. The B-LDPC codes are constructed as irregular QC-LDPC codes with parity-check matrices of an almost lower triangular form so that they have an efficient encoding algorithm, good noise threshold, and low error floor. Their encoding complexity is linearly scaled regardless of the size of circulant permutation matrices.
Cycle distribution of LDPC(Low-Density Parity-Check) codes affects the codes decoding performance and encoding complexity,however it is commonly NP hard to analyse.We propose the rotation-distance for analysis of QC-LDPC(Quasi-Cyclic Low-Density Parity-Check) code based on circulant matrices.The circulant sub-matrices within the parity-check are treated as a matrix node to simplify theTanner graphs of the codes.Thus cycles of QC-LDPC codes can be found efficiently,and we demonstrate the usefulness of the new method by a simple proof of the known result that 12 is an upper limit of the girth of the QC-LDPC codes we considered.Moreover,the cycle analysis based on the new method also reveals relations between decoding performance and the cycle distribution of the code.
Quasi-cyclic low-density parity-check (QC-LDPC) codes are an important class of LDPC codes which can be encoded and decoded with low complexity and suitable for many applications. As the code dimension, which describes the number of protected information bits, is equal to the code length minus the rank of the parity-check matrix and the parity-check matrix for QC-LDPC codes is usually not full-rank, determining the rank of the parity-check matrix is of essential importance. In this paper, we study the rank of the parity-check matrix for QC-LDPC codes based on the associated polynomials for circulant matrices. A formula for the rank of the parity-check matrix with only one row-block is first derived. We then extend the result to matrices with two, three, or more row-blocks. Some bounds are also presented for matrices with arbitrary numbers of row-blocks. Furthermore, the exact rank is determined for a class of algebraically constructed parity-check matrices.