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 Transactions on Information Theory

Error propagation and definite decoding of convolutional codes

John P. Robinson

Published Jan 1, 1968• 31 citations
Publisher

Abstract

The error-propagation effect in decoding convolutional codes is a result of the internal feedback in the usual decoding method, feedback decoding (FD). As a measure of this effect, the propagation lengthLof a system is defined as the maximum span of decoding errors following a decoding error when all succeding parity checks are satisfied. A relationship betweenL, the parity check matrix, and the decoding algorithm is developed. A decoding method having no internal feedback, definite decoding (DD), is formalized. It is shown that a code using FD with limitedLexists if and only if that same code can be decoded using DD. When using DD a smaller class of errors is corrected. The self-orthogonal codes are shown to be decodable using FD withLsmall. The minimum possible value ofLwhen using bounded distance decoding is given for some of these codes. Codes are given which minimize the spacing between single correctable errors using DD. These values of spacing are compared with those for similar (known) codes which use FD, and with the theoretical minimum spacing.

DOI
10.1109/tit.1968.1054082

Related papers

A Feedback Belief Propagation Algorithm for LDPC Convolutional Codes

Yuanhua Liu, Xinmei Wang, Yucheng He

A feedback belief propagation (BP) decoding algorithm for low-density parity-check convolutional codes is proposed. The proposed algorithm can activate the variable nodes more efficiently by applying feedback decoding at each decoding iteration. Compared with the on-demand BP algorithm, the proposed algorithm has a doubled convergence speed and causes only about half of the decoding delay at similar error performances without any increase of storage requirement. Simulation results show that the proposed algorithm can offer a good trade-off between the error-correcting performance and the decoding complexity.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•2 citations

A Class of Low-Density Parity-Check Convolutional Codes Based on Difference Families

Yucheng He, Christian Cardinal, David Haccoun

An algebraic construction for a class of low-density parity-check (LDPC) convolutional codes is presented on the basis of difference families associated with the code generator matrix. It can be shown that these codes have girth of at least 10 on the Tanner graph which is independent of either the size of the code generator matrix or the minimum Hamming distance of the codes. The code construction guarantees the independence of the messages exchanged in the belief propagation decoding process during two successive decoding iterations. Computer simulations show that over the additive white Gaussian noise channel, the best error performance of these codes at moderate signal-to- noise ratio values is practically obtained using only three to five iterations.

International Conference on Communications•Jan 1, 2008•2 citations

Improved belief propagation algorithm for decoding of convolutional LDPC codes

Chen Ru-wei

A novel belief propagation(BP) decoding algorithm for convolutional low-density parity-check codes is proposed.The proposed algorithm raises the efficiency of updating the variable information by applying feedback information at each decoding iteration and employs the weighting factor to reduce the error propagation caused by the cycles in the Tanner graph,thus yielding a faster convergence of the decoding.Simulation results show that an error performance better than that of the existing belief propagation algorithm can be achieved,while the 5/8 decoding delay and the computation complexity are effectively reduced.Compared with the existing BP,the proposed algorithm achieves a gain of 0.16dB at the BER of 10-6 with the same number of iterations.

Journal of Xidian University•Jan 1, 2009•0 citations

Separating erasures from errors for decoding

Khaled Abdel-Ghaffar, Jos H. Weber

Most decoding algorithms of linear codes, in general, are designed to correct or detect errors. However, many channels cause erasures in addition to errors. In principle, decoding over such channels can be accomplished by deleting the erased symbols and decoding the resulting vector with respect to a punctured code. For any given linear code and any given maximum number of correctable erasures, we introduce parity-check matrices yielding parity-check equations that do not check any of the erased symbols and which are sufficient to characterize all punctured codes corresponding to this maximum number of erasures. This allows for the separation of erasures from errors to facilitate decoding. The parity-check matrices typically have redundant rows. We give several constructions of such matrices and prove general bounds on their minimum sizes.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•15 citations

Optimization–based decoding algorithms for LDPC convolutional codes in communication systems

Banu Kabakulak, Z. Caner Taşkın, Alí Emre Pusane

In a digital communication system, information is sent from one place to another over a noisy communication channel. It may be possible to detect and correct errors that occur during the transmission if one encodes the original information by adding redundant bits. Low–Density Parity–Check (LDPC) convolutional codes, a member of the LDPC code family, encode the original information to improve error correction capability. In practice these codes are used to decode very long information sequences, where the information arrives in subsequent packets over time, such as video streams. We consider the problem of decoding the received information with minimum error from an optimization point of view and investigate integer programming–based exact and heuristic decoding algorithms for its solution. In particular, we consider relax–and–fix heuristics that decode information in small windows. Computational results indicate that our approaches identify near–optimal solutions significantly faster than a commercial solver in high channel error rates. Our proposed algorithms can find higher quality solutions compared with the state of the art iterative decoding heuristic.

arXiv:1708.05618•IISE Transactions•Dec 20, 2018•4 citations

Pseudo-Codewords in LDPC Convolutional Codes

Roxana Smarandache, Alí Emre Pusane, Pascal O. Vontobel +1 more

Iterative message-passing decoders for low-density parity-check (LDPC) block codes are known to be subject to decoding failures due to so-called pseudo-codewords. These failures can cause the large signal-to-noise ratio performance of message-passing decoding to be worse than that predicted by the maximum-likelihood decoding union bound. In this paper we study the pseudo-codeword problem for the class of LDPC convolutional codes decoded continuously using an iterative, sliding window, message-passing decoder. In particular, for an LDPC convolutional code derived by unwrapping a quasi-cyclic LDPC block code, we show that the free pseudo-weight of the convolutional code is at least as large as the minimum pseudo-weight of the underlying quasi-cyclic code. This result parallels the well-known relationship between the free Hamming distance of convolutional codes and the minimum Hamming distance of their quasi-cyclic counterparts. Finally, simulation results are included that show improved performance for unwrapped LDPC convolutional codes compared to their underlying quasi-cyclic codes

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•16 citations
The error-propagation effect in decoding convolutional codes is a result of the internal feedback in the usual decoding method, feedback decoding (FD). As a measure of this effect, the propagation lengthLof a system is defined as the maximum span of decoding errors following a decoding error when all succeding parity checks are satisfied. A relationship betweenL, the parity check matrix, and the decoding algorithm is developed. A decoding method having no internal feedback, definite decoding (DD), is formalized. It is shown that a code using FD with limitedLexists if and only if that same code can be decoded using DD. When using DD a smaller class of errors is corrected. The self-orthogonal codes are shown to be decodable using FD withLsmall. The minimum possible value ofLwhen using bounded distance decoding is given for some of these codes. Codes are given which minimize the spacing between single correctable errors using DD. These values of spacing are compared with those for similar (known) codes which use FD, and with the theoretical minimum spacing.
A feedback belief propagation (BP) decoding algorithm for low-density parity-check convolutional codes is proposed. The proposed algorithm can activate the variable nodes more efficiently by applying feedback decoding at each decoding iteration. Compared with the on-demand BP algorithm, the proposed algorithm has a doubled convergence speed and causes only about half of the decoding delay at similar error performances without any increase of storage requirement. Simulation results show that the proposed algorithm can offer a good trade-off between the error-correcting performance and the decoding complexity.
An algebraic construction for a class of low-density parity-check (LDPC) convolutional codes is presented on the basis of difference families associated with the code generator matrix. It can be shown that these codes have girth of at least 10 on the Tanner graph which is independent of either the size of the code generator matrix or the minimum Hamming distance of the codes. The code construction guarantees the independence of the messages exchanged in the belief propagation decoding process during two successive decoding iterations. Computer simulations show that over the additive white Gaussian noise channel, the best error performance of these codes at moderate signal-to- noise ratio values is practically obtained using only three to five iterations.
A novel belief propagation(BP) decoding algorithm for convolutional low-density parity-check codes is proposed.The proposed algorithm raises the efficiency of updating the variable information by applying feedback information at each decoding iteration and employs the weighting factor to reduce the error propagation caused by the cycles in the Tanner graph,thus yielding a faster convergence of the decoding.Simulation results show that an error performance better than that of the existing belief propagation algorithm can be achieved,while the 5/8 decoding delay and the computation complexity are effectively reduced.Compared with the existing BP,the proposed algorithm achieves a gain of 0.16dB at the BER of 10-6 with the same number of iterations.
Most decoding algorithms of linear codes, in general, are designed to correct or detect errors. However, many channels cause erasures in addition to errors. In principle, decoding over such channels can be accomplished by deleting the erased symbols and decoding the resulting vector with respect to a punctured code. For any given linear code and any given maximum number of correctable erasures, we introduce parity-check matrices yielding parity-check equations that do not check any of the erased symbols and which are sufficient to characterize all punctured codes corresponding to this maximum number of erasures. This allows for the separation of erasures from errors to facilitate decoding. The parity-check matrices typically have redundant rows. We give several constructions of such matrices and prove general bounds on their minimum sizes.
In a digital communication system, information is sent from one place to another over a noisy communication channel. It may be possible to detect and correct errors that occur during the transmission if one encodes the original information by adding redundant bits. Low–Density Parity–Check (LDPC) convolutional codes, a member of the LDPC code family, encode the original information to improve error correction capability. In practice these codes are used to decode very long information sequences, where the information arrives in subsequent packets over time, such as video streams. We consider the problem of decoding the received information with minimum error from an optimization point of view and investigate integer programming–based exact and heuristic decoding algorithms for its solution. In particular, we consider relax–and–fix heuristics that decode information in small windows. Computational results indicate that our approaches identify near–optimal solutions significantly faster than a commercial solver in high channel error rates. Our proposed algorithms can find higher quality solutions compared with the state of the art iterative decoding heuristic.
Iterative message-passing decoders for low-density parity-check (LDPC) block codes are known to be subject to decoding failures due to so-called pseudo-codewords. These failures can cause the large signal-to-noise ratio performance of message-passing decoding to be worse than that predicted by the maximum-likelihood decoding union bound. In this paper we study the pseudo-codeword problem for the class of LDPC convolutional codes decoded continuously using an iterative, sliding window, message-passing decoder. In particular, for an LDPC convolutional code derived by unwrapping a quasi-cyclic LDPC block code, we show that the free pseudo-weight of the convolutional code is at least as large as the minimum pseudo-weight of the underlying quasi-cyclic code. This result parallels the well-known relationship between the free Hamming distance of convolutional codes and the minimum Hamming distance of their quasi-cyclic counterparts. Finally, simulation results are included that show improved performance for unwrapped LDPC convolutional codes compared to their underlying quasi-cyclic codes