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

Bounds on Block Error Probability for Multilevel Concatenated Codes

Shu Lin, H.T. Moorthy, Diana Stojanovic

Published Jul 10, 1996• 0 citations
OpenAlex

Abstract

Maximum likelihood decoding of long block codes is not feasable due to large complexity. Some classes of codes are shown to be decomposable into multilevel concatenated codes (MLCC). For these codes, multistage decoding provides good trade-off between performance and complexity. In this paper, we derive an upper bound on the probability of block error for MLCC. We use this bound to evaluate difference in performance for different decompositions of some codes. Examples given show that a significant reduction in complexity can be achieved when increasing number of stages of decoding. Resulting performance degradation varies for different decompositions. A guideline is given for finding good m-level decompositions.

Related papers

Suboptimum decoding of decomposable block codes

T. Takata, Y. Yamashita, Toru Fujiwara +2 more

To decode a long block code with a large minimum distance by maximum likelihood decoding is practically impossible because the decoding complexity is simply enormous. However, if a code can be decomposed into constituent codes with smaller dimensions and simpler structure, it is possible to devise a practical and yet efficient scheme to decode the code. This paper investigates a class of decomposable codes, their distance and structural properties. It is shown that this class includes several classes of well-known and efficient codes as subclasses. Several methods for constructing decomposable codes or decomposing codes are presented. A two-stage (soft-decision or hard-decision) decoding scheme for decomposable codes, their translates or unions of translates is devised, and its error performance is analyzed for an AWGN channel. The two-stage soft-decision decoding is suboptimum. Error performances of some specific decomposable codes based on the proposed two-stage soft-decision decoding are evaluated. It is shown that the proposed two-stage suboptimum decoding scheme provides an excellent trade-off between the error performance and decoding complexity for codes of moderate and long block length.>

IEEE Transactions on Information Theory•Jan 1, 1994•22 citations

An upper bound on the effective error coefficient of two-stage decoding, and good two-level decompositions of some Reed-Muller codes

Jiantin Wu, Shu Hwa Lin, Tadao Kasami +2 more

An upper bound on the effective error coefficient of a two-level code with two-stage decoding is presented. This bound provides a guideline for constructing two-level codes to achieve a good trade-off between the error performance and decoding complexity. Based on this bound, good two-level decompositions of some Reed-Muller codes for two-stage decoding are found. Simulation results on the error performances of some Reed-Muller codes of lengths up to 64 with two-stage soft-decision suboptimum decoding based on their two-level decompositions are given.>

IEEE Transactions on Communications•Feb 1, 1994•13 citations

Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial

Igal Sason, Shlomo Shitz Shamai

This article is focused on the performance evaluation of linear codes under optimal maximum-likelihood (ML) decoding. Though the ML decoding algorithm is prohibitively complex for most practical codes, their performance analysis under ML decoding allows to predict their performance without resorting to computer simulations. It also provides a benchmark for testing the sub-optimality of iterative (or other practical) decoding algorithms. This analysis also establishes the goodness of linear codes (or ensembles), determined by the gap between their achievable rates under optimal ML decoding and information theoretical limits. In this article, upper and lower bounds on the error probability of linear codes under ML decoding are surveyed and applied to codes and ensembles of codes on graphs. For upper bounds, we discuss various bounds where focus is put on Gallager bounding techniques and their relation to a variety of other reported bounds. Within the class of lower bounds, we address de Caen’s based bounds and their improvements, and also consider sphere-packing bounds with their recent improvements targeting codes of moderate block lengths.

Foundations and Trends® in Communications and Information Theory•Jul 7, 2006•153 citations

Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial

Igal Sason, Shlomo Shitz Shamai

Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial focuses on the performance evaluation of linear codes under optimal maximum-likelihood (ML) decoding. Though the ML decoding algorithm is prohibitively complex for most practical codes, their performance analysis under ML decoding allows to predict their performance without resorting to computer simulations. It also provides a benchmark for testing the sub-optimality of iterative (or other practical) decoding algorithms. This analysis also establishes the goodness of linear codes (or ensembles), determined by the gap between their achievable rates under optimal ML decoding and information theoretical limits. In Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial, upper and lower bounds on the error probability of linear codes under ML decoding are surveyed and applied to codes and ensembles of codes on graphs. For upper bounds, we discuss various bounds where focus is put on Gallager bounding techniques and their relation to a variety of other reported bounds. Within the class of lower bounds, we address de Caen's based bounds and their improvements, and also consider sphere-packing bounds with their recent improvements targeting codes of moderate block lengths. Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial is a comprehensive introduction to this important topic for students, practitioners and researchers working in communications and information theory.

now publishers, Inc. eBooks•Jan 1, 2006•47 citations

The Block Error Probability of Detailedly Represented Irregular LDPC Code Ensembles under Maximum Likelihood Decoding

Ryoji Ikegaya, K. Kasai, T. Shibuya +1 more

In this paper, we have derived the upper bound of the average block error probability of a given detailedly represented irregular low-density parity-check (LDPC) code ensemble under maximum likelihood decoding.

IEEE Information Theory Workshop (ITW)•May 25, 2006•0 citations

Performance of Multistage Universal Decoder for Given Linear Codes over Additive Noise Channels

Tomohiko Uyematsu, Fumio Kanaya

We propose a multilevel coding and multistage decod-ing scheme which is universal for a class of additive noise channels. Then, for a given pair of binary linear codes, we show an upper bound of the decoding er-ror probability. Further, we clarify the condition that the proposed coding and decoding scheme achieves the capacity of the channel and that the decoding error probability vanishes exponentially with code length. 1.

•Aug 10, 2007•2 citations
Maximum likelihood decoding of long block codes is not feasable due to large complexity. Some classes of codes are shown to be decomposable into multilevel concatenated codes (MLCC). For these codes, multistage decoding provides good trade-off between performance and complexity. In this paper, we derive an upper bound on the probability of block error for MLCC. We use this bound to evaluate difference in performance for different decompositions of some codes. Examples given show that a significant reduction in complexity can be achieved when increasing number of stages of decoding. Resulting performance degradation varies for different decompositions. A guideline is given for finding good m-level decompositions.
To decode a long block code with a large minimum distance by maximum likelihood decoding is practically impossible because the decoding complexity is simply enormous. However, if a code can be decomposed into constituent codes with smaller dimensions and simpler structure, it is possible to devise a practical and yet efficient scheme to decode the code. This paper investigates a class of decomposable codes, their distance and structural properties. It is shown that this class includes several classes of well-known and efficient codes as subclasses. Several methods for constructing decomposable codes or decomposing codes are presented. A two-stage (soft-decision or hard-decision) decoding scheme for decomposable codes, their translates or unions of translates is devised, and its error performance is analyzed for an AWGN channel. The two-stage soft-decision decoding is suboptimum. Error performances of some specific decomposable codes based on the proposed two-stage soft-decision decoding are evaluated. It is shown that the proposed two-stage suboptimum decoding scheme provides an excellent trade-off between the error performance and decoding complexity for codes of moderate and long block length.>
An upper bound on the effective error coefficient of a two-level code with two-stage decoding is presented. This bound provides a guideline for constructing two-level codes to achieve a good trade-off between the error performance and decoding complexity. Based on this bound, good two-level decompositions of some Reed-Muller codes for two-stage decoding are found. Simulation results on the error performances of some Reed-Muller codes of lengths up to 64 with two-stage soft-decision suboptimum decoding based on their two-level decompositions are given.>
This article is focused on the performance evaluation of linear codes under optimal maximum-likelihood (ML) decoding. Though the ML decoding algorithm is prohibitively complex for most practical codes, their performance analysis under ML decoding allows to predict their performance without resorting to computer simulations. It also provides a benchmark for testing the sub-optimality of iterative (or other practical) decoding algorithms. This analysis also establishes the goodness of linear codes (or ensembles), determined by the gap between their achievable rates under optimal ML decoding and information theoretical limits. In this article, upper and lower bounds on the error probability of linear codes under ML decoding are surveyed and applied to codes and ensembles of codes on graphs. For upper bounds, we discuss various bounds where focus is put on Gallager bounding techniques and their relation to a variety of other reported bounds. Within the class of lower bounds, we address de Caen’s based bounds and their improvements, and also consider sphere-packing bounds with their recent improvements targeting codes of moderate block lengths.
Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial focuses on the performance evaluation of linear codes under optimal maximum-likelihood (ML) decoding. Though the ML decoding algorithm is prohibitively complex for most practical codes, their performance analysis under ML decoding allows to predict their performance without resorting to computer simulations. It also provides a benchmark for testing the sub-optimality of iterative (or other practical) decoding algorithms. This analysis also establishes the goodness of linear codes (or ensembles), determined by the gap between their achievable rates under optimal ML decoding and information theoretical limits. In Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial, upper and lower bounds on the error probability of linear codes under ML decoding are surveyed and applied to codes and ensembles of codes on graphs. For upper bounds, we discuss various bounds where focus is put on Gallager bounding techniques and their relation to a variety of other reported bounds. Within the class of lower bounds, we address de Caen's based bounds and their improvements, and also consider sphere-packing bounds with their recent improvements targeting codes of moderate block lengths. Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial is a comprehensive introduction to this important topic for students, practitioners and researchers working in communications and information theory.