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

arXiv:1408.5674

Performance and analysis of Quadratic Residue Codes of lengths less than 100

Yong Li, Qianbin Chen, Hongqing Liu, Trieu‐Kien Truong

Published Aug 25, 2014• 4 citations
arXivHTMLPDF

Abstract

In this paper, the performance of quadratic residue (QR) codes of lengths within 100 is given and analyzed when the hard decoding, soft decoding, and linear programming decoding algorithms are utilized. We develop a simple method to estimate the soft decoding performance, which avoids extensive simulations. Also, a simulation-based algorithm is proposed to obtain the maximum likelihood decoding performance of QR codes of lengths within 100. Moreover, four important theorems are proposed to predict the performance of the hard decoding and the maximum-likelihood decoding in which they can explore some internal properties of QR codes. It is shown that such four theorems can be applied to the QR codes with lengths less than 100 for predicting the decoding performance. In contrast, they can be straightforwardly generalized to longer QR codes. The result is never seen in the literature, to our knowledge. Simulation results show that the estimated hard decoding performance is very accurate in the whole signal-to-noise ratio (SNR) regimes, whereas the derived upper bounds of the maximum likelihood decoding are only tight for moderate to high SNR regions. For each of the considered QR codes, the soft decoding is approximately 1.5 dB better than the hard decoding. By using powerful redundant parity-check cuts, the linear programming-based decoding algorithm, i.e., the ACG-ALP decoding algorithm performs very well for any QR code. Sometimes, it is even superior to the Chase-based soft decoding algorithm significantly, and hence is only a few tenths of dB away from the maximum likelihood decoding.

DOI
10.48550/arxiv.1408.5674

Related papers

On Decoding of the (89, 45, 17) Quadratic Residue Code

Lin Wang, Yong Li, Trieu‐Kien Truong +1 more

In this paper, Three decoding methods of the (89, 45, 17) binary quadratic residue (QR) code to be presented are hard, soft and linear programming decoding algorithms. Firstly, a new hybrid algebraic decoding algorithm for the (89, 45, 17) QR code is proposed. It uses the Laplace formula to obtain the primary unknown syndromes, as done in Lin et al.'s algorithm when the number of errors v is less than or equal to 5, whereas Gaussian elimination is adopted to compute the unknown syndromes when v ≥ 6. Secondly, an appropriate modification to the algorithm developed by Chase is also given in this paper. Therefore, combining the proposed algebraic decoding algorithm with the modified Chase-II algorithm, called a new soft-decision decoding algorithm, becomes a complete soft decoding of QR codes. Thirdly, in order to further improve the error-correcting performance of the code, linear programming (LP) is utilized to decode the (89, 45, 17) QR code. Simulation results show that the proposed algebraic decoding algorithm reduces the decoding time when compared with Lin et al.'s hard decoding algorithm, and thus significantly reduces the decoding complexity of soft decoding while maintaining the same bit error rate (BER) performance. Moreover, the LP-based decoding improves the error-rate performance almost without increasing the decoding complexity, when compared with the new soft-decision decoding algorithm. It provides a coding gain of 0.2 dB at BER = 2 × 10-6.

IEEE Transactions on Communications•Jan 8, 2013•11 citations

On Decoding of the (73, 37, 13) Quadratic Residue Code

Yong Li, Hongqing Liu, Qianbin Chen +1 more

In this paper, a method to search the set of syndromes' indices needed in computing the unknown syndromes for the (73, 37, 13) quadratic residue (QR) code is proposed. According to the resulting index sets, one computes the unknown syndromes and thus finds the corresponding error-locator polynomial by using an inverse-free Berlekamp-Massey (BM) algorithm. Based on the modified Chase-II algorithm, the performance of soft-decision decoding for the (73, 37, 13) QR code is given. This result is new. Moreover, the error-rate performance of linear programming (LP) decoding for the (73, 37, 13) QR code is also investigated, and LP-based decoding is shown to be significantly superior in performance to the algebraic soft-decision decoding while requiring almost the same computational complexity. In fact, the algebraic hard-decision and soft-decision decoding of the (89, 45, 17) QR code outperforms that of the (73, 37, 13) QR code because the former has a larger minimal distance. However, experimental results indicate that the (73, 37, 13) QR code outperforms the (89, 45, 17) QR code with much fewer arithmetic operations when using the LP-based decoding algorithms. The pseudocodewords analysis partially explains this seemingly strange phenomenon.

IEEE Transactions on Communications•Jun 27, 2014•5 citations

Asymptotically optimum soft decision decoding

Nandakumar Nityananda Tendolkar

This dissertation develops a set of new algorithms for soft decision decoding of binary linear block codes. The performance (i.e. the probability of error) of these algorithms is asymptotically optimum for high signal-to-noise ratio for binary linear block codes transmitted over the additive white gaussian (AWGN) channel using antipodal signalling. Among the algorithms proposed are the generalized Chase algorithms. In contrast to Chase algorithms, which require a {(d-1)/2} hard error-correcting decoder for decoding a binary linear block code of minimum distance d, the generalized Chase algorithms can use a binary decoder that can correct less than {(d-1)/2} hard errors. The Chase algorithms are particular cases of the generalized Chase algorithms. Modified generalized Chase algorithm 2 and 3 are proposed for codes that have an overall parity check. These algorithms use fewer test patterns than the generalized Chase algorithms and they also have asymptotically optimum performance for high signal-to-noise ratio. The erasure information decoding algorithm of Tanaka and Kakigahara is generalized so that any hard decoder that corrects only up to t errors, 0 (LESSTHEQ) t (LESSTHEQ) {(d-1)/2} can be used to obtain asymptotically optimal performance for high signal-to-noise ratio. The modified erasure information decoding algorithm is proposed for codes that have an overall parity check. The modified erasure information decoding algorithm requires fewer test patterns than the erasure information decoding algorithm and its performance is also asymptotically optimum for high signal-to-noise ratio. The algorithms proposed by Dorsch and, Baumert and McEliece are analyzed to determine the conditions under which their performance would be asymptotically optimum for high signal-to-noise ratio. Simulation results for the (47,23) Quadratic Residue code are shown to demonstrate the performance of the algorithms. The results indicate that even for low signal-to-noise ratio the performance of a maximum likelihood decoder can be approached by a relatively simple decoding procedure.

•Jan 1, 1983•1 citation

Efficient Decoder for Turbo Product Codes Based on Quadratic Residue Codes

Jie Dong, Yong Li, Rui Liu +2 more

In this letter, we study turbo product codes with quadratic residue codes (called QR-TPCs) as the component codes. We propose an efficient decoder based on Chase-II algorithm with two convergence conditions for the iterative decoding of QR-TPCs. For each row and column, the Chase-II decoder will stop immediately when one of the conditions is met. The simulation results show that the proposed algorithm has a lower computational complexity compared with existing decoding methods. Moreover, a comparison with 5G low-density parity-check codes shows that the proposed turbo product codes have better performance for short code lengths.

Electronics•Nov 3, 2022•3 citations

Generalization of chase algorithms for soft decision decoding of binary linear codes

Nandakumar Nityananda Tendolkar, Carlos R. P. Hartmann

Soft decision decoding of binary linear block codes transmitted over the additive white Gaussian channel (AWGN) using antipodal signaling is considered. A set of decoding algorithms called generalized Chase algorithms is proposed. In contrast to Chase algorithms, which require a\lfloor (d- 1)/2 \rfloorbinary error-correcting decoder for decoding a binary linear block code of minimum distanced, the generalized Chase algorithms can use a binary decoder that can correct less than\lfloor ( d - 1)/2 \rfloorhard errors. The Chase algorithms are particular cases of the generalized Chase algorithms. The performance of all proposed algorithms is asymptotically optimum for high signal-to-noise ratio (SNR). Simulation results for the(47, 23)quadratic residue code indicate that even for low SNR the performance level of a maximum likelihood decoder can be approached by a relatively simple decoding procedure.

IEEE Transactions on Information Theory•Sep 1, 1984•29 citations

Hard- and soft-decision decoding beyond the half minimum distance---An algorithm for linear codes (Corresp.)

Martin Bossert, F. Hergert

A decoding algorithm for linear codes that uses the minimum weight words of the dual code as parity checks is defined. This algorithm is able to correct beyond the half minimum distance and has the capability of including soft-decision decoding. Results on applying this algorithm to quadratic residue (QR) codes, BCH codes, and the Golay codes (with and without soft-decision decoding) are presented.

IEEE Transactions on Information Theory•Sep 1, 1986•38 citations
In this paper, the performance of quadratic residue (QR) codes of lengths within 100 is given and analyzed when the hard decoding, soft decoding, and linear programming decoding algorithms are utilized. We develop a simple method to estimate the soft decoding performance, which avoids extensive simulations. Also, a simulation-based algorithm is proposed to obtain the maximum likelihood decoding performance of QR codes of lengths within 100. Moreover, four important theorems are proposed to predict the performance of the hard decoding and the maximum-likelihood decoding in which they can explore some internal properties of QR codes. It is shown that such four theorems can be applied to the QR codes with lengths less than 100 for predicting the decoding performance. In contrast, they can be straightforwardly generalized to longer QR codes. The result is never seen in the literature, to our knowledge. Simulation results show that the estimated hard decoding performance is very accurate in the whole signal-to-noise ratio (SNR) regimes, whereas the derived upper bounds of the maximum likelihood decoding are only tight for moderate to high SNR regions. For each of the considered QR codes, the soft decoding is approximately 1.5 dB better than the hard decoding. By using powerful redundant parity-check cuts, the linear programming-based decoding algorithm, i.e., the ACG-ALP decoding algorithm performs very well for any QR code. Sometimes, it is even superior to the Chase-based soft decoding algorithm significantly, and hence is only a few tenths of dB away from the maximum likelihood decoding.
In this paper, Three decoding methods of the (89, 45, 17) binary quadratic residue (QR) code to be presented are hard, soft and linear programming decoding algorithms. Firstly, a new hybrid algebraic decoding algorithm for the (89, 45, 17) QR code is proposed. It uses the Laplace formula to obtain the primary unknown syndromes, as done in Lin et al.'s algorithm when the number of errors v is less than or equal to 5, whereas Gaussian elimination is adopted to compute the unknown syndromes when v ≥ 6. Secondly, an appropriate modification to the algorithm developed by Chase is also given in this paper. Therefore, combining the proposed algebraic decoding algorithm with the modified Chase-II algorithm, called a new soft-decision decoding algorithm, becomes a complete soft decoding of QR codes. Thirdly, in order to further improve the error-correcting performance of the code, linear programming (LP) is utilized to decode the (89, 45, 17) QR code. Simulation results show that the proposed algebraic decoding algorithm reduces the decoding time when compared with Lin et al.'s hard decoding algorithm, and thus significantly reduces the decoding complexity of soft decoding while maintaining the same bit error rate (BER) performance. Moreover, the LP-based decoding improves the error-rate performance almost without increasing the decoding complexity, when compared with the new soft-decision decoding algorithm. It provides a coding gain of 0.2 dB at BER = 2 × 10-6.
In this paper, a method to search the set of syndromes' indices needed in computing the unknown syndromes for the (73, 37, 13) quadratic residue (QR) code is proposed. According to the resulting index sets, one computes the unknown syndromes and thus finds the corresponding error-locator polynomial by using an inverse-free Berlekamp-Massey (BM) algorithm. Based on the modified Chase-II algorithm, the performance of soft-decision decoding for the (73, 37, 13) QR code is given. This result is new. Moreover, the error-rate performance of linear programming (LP) decoding for the (73, 37, 13) QR code is also investigated, and LP-based decoding is shown to be significantly superior in performance to the algebraic soft-decision decoding while requiring almost the same computational complexity. In fact, the algebraic hard-decision and soft-decision decoding of the (89, 45, 17) QR code outperforms that of the (73, 37, 13) QR code because the former has a larger minimal distance. However, experimental results indicate that the (73, 37, 13) QR code outperforms the (89, 45, 17) QR code with much fewer arithmetic operations when using the LP-based decoding algorithms. The pseudocodewords analysis partially explains this seemingly strange phenomenon.
This dissertation develops a set of new algorithms for soft decision decoding of binary linear block codes. The performance (i.e. the probability of error) of these algorithms is asymptotically optimum for high signal-to-noise ratio for binary linear block codes transmitted over the additive white gaussian (AWGN) channel using antipodal signalling. Among the algorithms proposed are the generalized Chase algorithms. In contrast to Chase algorithms, which require a {(d-1)/2} hard error-correcting decoder for decoding a binary linear block code of minimum distance d, the generalized Chase algorithms can use a binary decoder that can correct less than {(d-1)/2} hard errors. The Chase algorithms are particular cases of the generalized Chase algorithms. Modified generalized Chase algorithm 2 and 3 are proposed for codes that have an overall parity check. These algorithms use fewer test patterns than the generalized Chase algorithms and they also have asymptotically optimum performance for high signal-to-noise ratio. The erasure information decoding algorithm of Tanaka and Kakigahara is generalized so that any hard decoder that corrects only up to t errors, 0 (LESSTHEQ) t (LESSTHEQ) {(d-1)/2} can be used to obtain asymptotically optimal performance for high signal-to-noise ratio. The modified erasure information decoding algorithm is proposed for codes that have an overall parity check. The modified erasure information decoding algorithm requires fewer test patterns than the erasure information decoding algorithm and its performance is also asymptotically optimum for high signal-to-noise ratio. The algorithms proposed by Dorsch and, Baumert and McEliece are analyzed to determine the conditions under which their performance would be asymptotically optimum for high signal-to-noise ratio. Simulation results for the (47,23) Quadratic Residue code are shown to demonstrate the performance of the algorithms. The results indicate that even for low signal-to-noise ratio the performance of a maximum likelihood decoder can be approached by a relatively simple decoding procedure.
In this letter, we study turbo product codes with quadratic residue codes (called QR-TPCs) as the component codes. We propose an efficient decoder based on Chase-II algorithm with two convergence conditions for the iterative decoding of QR-TPCs. For each row and column, the Chase-II decoder will stop immediately when one of the conditions is met. The simulation results show that the proposed algorithm has a lower computational complexity compared with existing decoding methods. Moreover, a comparison with 5G low-density parity-check codes shows that the proposed turbo product codes have better performance for short code lengths.
Soft decision decoding of binary linear block codes transmitted over the additive white Gaussian channel (AWGN) using antipodal signaling is considered. A set of decoding algorithms called generalized Chase algorithms is proposed. In contrast to Chase algorithms, which require a\lfloor (d- 1)/2 \rfloorbinary error-correcting decoder for decoding a binary linear block code of minimum distanced, the generalized Chase algorithms can use a binary decoder that can correct less than\lfloor ( d - 1)/2 \rfloorhard errors. The Chase algorithms are particular cases of the generalized Chase algorithms. The performance of all proposed algorithms is asymptotically optimum for high signal-to-noise ratio (SNR). Simulation results for the(47, 23)quadratic residue code indicate that even for low SNR the performance level of a maximum likelihood decoder can be approached by a relatively simple decoding procedure.