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

IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering

Estimation of Independent Errors and Bursts Correction Capability of Linear Codes

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

Published Jan 29, 2024• 5 citations
Publisher

Abstract

The article explores the problem of determining the error-correcting capability of linear codes for simultaneous correction of bursts and independent errors in communication channels affected by memory, similar to those described by a two-state Markov model representing good and bad channel states. Traditional methods for assessing error correction capability rely on standard array, which are computationally expensive. The article introduces an algorithm that, based on the multiplicity of correctable bursts and independent errors, calculates the maximum burst length that can be corrected. This algorithm exhibits polynomial complexity for small numbers of correctable bursts and independent errors. Furthermore, the article provides empirical assessments of the joint error-correcting capability for specific linear codes and estimates the algorithm's computational complexity. These results demonstrate the feasibility of determining error-correcting capability for code lengths significantly exceeding those that standard array can handle. These findings have practical applications for evaluating error-correcting parameters in memory-based communication channels.

DOI
10.1109/elcon61730.2024.10468456

Related papers

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

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

About Burst-Correction Capability of Block-Permutation LDPC Codes Ensembles

K. A. Bakay, Andrei A. Ovchinnikov, D. V. Ilina

The problem of maximal correctable error burst length estimation is considered for the probabilistic ensemble of block-permutation low-density parity-check codes. It is noted that this task has polynomial running time. For the number of probabilistic ensembles the simulations are performed showing that the correctable burst length grows linearly with the block size of the block-permutation construction, and with high probability equals to the block size minus one.

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

On the error-correcting capabilities of iterative error correction codes

Vasyl Semerenko

The influence of the theory of information on development of the error correcting coding theory has been studied. Main differences between the probabilistic approach and the deterministic approach in the analysis of error-correcting capabilities of different classes of linear codes have been demonstrated.The automaton hierarchical models for analysis of permutation decoding of cyclic codes have been developed and a cyclic permutation generator based on two Moore automata has been proposed.A study has been carried out into the regular and irregular states of linear finite-state machines (LFSM) based on the automaton representation of cyclic codes. A possibility of significant simplification of decoding of cyclic codes based on conversion of irregular LFSM syndromes into regular ones using permutations has been shown.The formalized methods for determination of error-correcting capabilities of iteratively decoded cyclic codes (IDCC) have been devised. They imply the replacementof traditional complete checking of all possible options for comparison of code words to directional search for the solution of the assigned problem, which leads to a significant time saving for calculations. The algorithm for determination of error-correcting capabilities of IDCC with respect to double errors is given.It has been shown that all iterative codes increase their error-correcting capabilities with an increase in the number of iterations and one can set it as a percentage for errors of various multiplicities. A distribution of error syndromes to separate iterations has been performed, which makes it possible to reduce the length of a check word in a code. As a result, this leads to an increase in a rate of iterative codes in comparison with the traditional correction codes.A comparative analysis of IDCC and LDPC codes has been carried out to determine a scope of their optimal use

Eastern-European Journal of Enterprise Technologies•Feb 21, 2019•1 citation

Construction and Performance of Quantum Burst Error Correction Codes for Correlated Errors

Jihao Fan, Min-Hsiu Hsieh, Hanwu Chen +2 more

In practical communication and computation systems, errors occur predominantly in adjacent positions rather than in a random manner. In this paper, we develop a stabilizer formalism for quantum burst error correction codes (QBECC) to combat such error patterns in the quantum regime. Our contributions are as follows. Firstly, we derive an upper bound for the correctable burst errors of QBECCs, the quantum Reiger bound (QRB). Secondly, we propose two constructions of QBECCs: one by heuristic computer search and the other by concatenating two quantum tensor product codes (QTPCs). We obtain several new QBECCs with better parameters than existing codes with the same coding length. Moreover, some of the constructed codes can saturate the quantum Reiger bounds. Finally, we perform numerical experiments for our constructed codes over Markovian correlated depolarizing quantum memory channels, and show that QBECCs indeed outperform standard QECCs in this scenario.

arXiv:1801.03861•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•12 citations

Characterizing the Burst Error Correction Ability of Quantum Cyclic Codes

Jihao Fan, Min-Hsiu Hsieh

Quantum burst error correction codes (QBECCs) are of great importance to deal with the memory effect in quantum channels. As the most important family of QBECCs, quantum cyclic codes (QCCs) play a vital role in the correction of burst errors. In this work, we characterize the burst error correction ability of QCCs constructed from the Calderbank-Shor-Steane (CSS) and the Hermitian constructions. We determine the burst error correction limit of QCCs and quantum Reed-Solomon codes with algorithms in polynomial-time complexities. As a result, lots of QBECCs saturating the quantum Reiger bound are obtained. We show that quantum Reed-Solomon codes have better burst error correction abilities than the previous results. At last, we give the quantum error-trapping decoder (QETD) of QCCs for decoding burst errors. The decoder runs in linear time and can decode both degenerate and nondegenerate burst errors. What’s more, the numerical results show that QETD can decode much more degenerate burst errors than the nondegenerate ones.

arXiv:2501.04310•IEEE Transactions on Information Theory•Feb 2, 2026•2 citations
The article explores the problem of determining the error-correcting capability of linear codes for simultaneous correction of bursts and independent errors in communication channels affected by memory, similar to those described by a two-state Markov model representing good and bad channel states. Traditional methods for assessing error correction capability rely on standard array, which are computationally expensive. The article introduces an algorithm that, based on the multiplicity of correctable bursts and independent errors, calculates the maximum burst length that can be corrected. This algorithm exhibits polynomial complexity for small numbers of correctable bursts and independent errors. Furthermore, the article provides empirical assessments of the joint error-correcting capability for specific linear codes and estimates the algorithm's computational complexity. These results demonstrate the feasibility of determining error-correcting capability for code lengths significantly exceeding those that standard array can handle. These findings have practical applications for evaluating error-correcting parameters in memory-based communication channels.
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.
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.
The influence of the theory of information on development of the error correcting coding theory has been studied. Main differences between the probabilistic approach and the deterministic approach in the analysis of error-correcting capabilities of different classes of linear codes have been demonstrated.The automaton hierarchical models for analysis of permutation decoding of cyclic codes have been developed and a cyclic permutation generator based on two Moore automata has been proposed.A study has been carried out into the regular and irregular states of linear finite-state machines (LFSM) based on the automaton representation of cyclic codes. A possibility of significant simplification of decoding of cyclic codes based on conversion of irregular LFSM syndromes into regular ones using permutations has been shown.The formalized methods for determination of error-correcting capabilities of iteratively decoded cyclic codes (IDCC) have been devised. They imply the replacementof traditional complete checking of all possible options for comparison of code words to directional search for the solution of the assigned problem, which leads to a significant time saving for calculations. The algorithm for determination of error-correcting capabilities of IDCC with respect to double errors is given.It has been shown that all iterative codes increase their error-correcting capabilities with an increase in the number of iterations and one can set it as a percentage for errors of various multiplicities. A distribution of error syndromes to separate iterations has been performed, which makes it possible to reduce the length of a check word in a code. As a result, this leads to an increase in a rate of iterative codes in comparison with the traditional correction codes.A comparative analysis of IDCC and LDPC codes has been carried out to determine a scope of their optimal use
In practical communication and computation systems, errors occur predominantly in adjacent positions rather than in a random manner. In this paper, we develop a stabilizer formalism for quantum burst error correction codes (QBECC) to combat such error patterns in the quantum regime. Our contributions are as follows. Firstly, we derive an upper bound for the correctable burst errors of QBECCs, the quantum Reiger bound (QRB). Secondly, we propose two constructions of QBECCs: one by heuristic computer search and the other by concatenating two quantum tensor product codes (QTPCs). We obtain several new QBECCs with better parameters than existing codes with the same coding length. Moreover, some of the constructed codes can saturate the quantum Reiger bounds. Finally, we perform numerical experiments for our constructed codes over Markovian correlated depolarizing quantum memory channels, and show that QBECCs indeed outperform standard QECCs in this scenario.
Quantum burst error correction codes (QBECCs) are of great importance to deal with the memory effect in quantum channels. As the most important family of QBECCs, quantum cyclic codes (QCCs) play a vital role in the correction of burst errors. In this work, we characterize the burst error correction ability of QCCs constructed from the Calderbank-Shor-Steane (CSS) and the Hermitian constructions. We determine the burst error correction limit of QCCs and quantum Reed-Solomon codes with algorithms in polynomial-time complexities. As a result, lots of QBECCs saturating the quantum Reiger bound are obtained. We show that quantum Reed-Solomon codes have better burst error correction abilities than the previous results. At last, we give the quantum error-trapping decoder (QETD) of QCCs for decoding burst errors. The decoder runs in linear time and can decode both degenerate and nondegenerate burst errors. What’s more, the numerical results show that QETD can decode much more degenerate burst errors than the nondegenerate ones.