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

International Journal of Communications Network and System Sciences

Majority Voting Procedure Allowing Soft Decision Decoding of Linear Block Codes on Binary Channels

Saïd Nouh, Achraf El Khatabi, Mostafa Belkasmi

Published Jan 1, 2012• 11 citations
Publisher

Abstract

In this paper we present an efficient algorithm to decode linear block codes on binary channels. The main idea consists in using a vote procedure in order to elaborate artificial reliabilities of the binary received word and to present the obtained real vector r as inputs of a SIHO decoder (Soft In/Hard Out). The goal of the latter is to try to find the closest codeword to r in terms of the Euclidean distance. A comparison of the proposed algorithm over the AWGN channel with the Majority logic decoder, Berlekamp-Massey, Bit Flipping, Hartman-Rudolf algorithms and others show that it is more efficient in terms of performance. The complexity of the proposed decoder depends on the weight of the error to decode, on the code structure and also on the used SIHO decoder.

DOI
10.4236/ijcns.2012.59066

Related papers

An efficient information set algorithm for soft-decision decoding of linear block codes

Dulte José de Barros, B.G. Dorsch

This paper presents an approach to soft-decision decoding for a (n, k) binary linear block code. This approach achieves near-optimal to optimal performance for any signal-to-noise ratio value. The proposed decoding is based on the reordering of the received symbols according to their reliability measure and can be applied to any binary linear code. The basic idea is to generate a sequence of codewords such that there will be a high probability that the next codeword is closer to the received vector. In this algorithm the information provided by the soft-decisions is used to generate information sets utilized in decoding. A fast procedure checks whether a given set of k positions is an information set. A sequence of codewords is reconstructed using a sequence of information sets. Each codeword reconstructed is compared with the received word and the closest one is selected. Hence, the decoding algorithm is an iterative procedure designed to enhance the performance of the usual soft-decision decoding, since with each iteration of the procedure, real vectors successively closer to the received vector are examined. A high performance stop rule is utilized to reduce the number of generated information sets, stopping the decoding process when a codeword is closest to the received sequence.

IEEE International Symposium on Information Theory (ISIT)•Nov 22, 2002•1 citation

Half-Chase Algorithm of Non-soft Decision Decoding Based on Majority

Chun-Fong Kuo, Hsin-Kun Lai, Erl‐Huei Lu

A non-soft decision decoding algorithm for binary linear block codes transmitted over AWGN channel is presented. Unlike soft decision decoding algorithms, the proposed algorithm does not computing weighted Hamming distances. Based on the majority of code word candidates from the hard decision decoding output, the proposed algorithm improves error-correcting performance by 1 dB of coding gain compared to that of hard decision decoding algorithms. Also, a schematic block diagram for finding the codeword of majority is developed. Furthermore, a comparison of hardware complexity is made between the computation of weighted Hamming distances and the finding of majority code word.

International Conference on Advanced Communication Technology•Feb 1, 2007•0 citations

Decoding of linear block codes based on ordered statistics

M.P.C. Fossorier

This dissertation presents a novel approach to soft decision decoding for binary linear block codes. The basic idea of this approach is to achieve a desired error performance progressively in a number of stages. For each decoding stage, the error performance is highly bounded and the decoding is terminated at the stage where either near-optimum error performance or a desired level of error performance is achieved. As a result, more flexibility in the trade-off between performance and decoding complexity is provided. The proposed decoding is based on the reordering of the received symbols according to their reliability measure. In the dissertation, we evaluate the statistics of the noise after ordering. Based on these statistics, we derive two monotonic properties which dictate the reprocessing strategy. Each codeword is decoded in two steps: (1) hard-decision decoding based on reliability information and (2) reprocessing of the hard-decision decoded codeword in successive stages until the desired performance is achieved. The reprocessing is based on the monotonic properties of the ordering and is carried out using a cost function. A new resource test highly related to the reprocessing strategy is introduced to reduce the number of computations for each reprocessing stage. For short codes of lengths N ≤ 32 or medium codes with 32 < N ≤ 64 with rate R ≥ 0.6, near-optimum bit error performance is achieved in two stages of reprocessing with at most a computation complexity of o(K2) constructed code-words, where K is the dimension of the code. For longer codes, three or more reprocessing stages are required to achieve near-optimum decoding. However, most of the coding gain is obtained within the first two reprocessing stages for error performances of practical interest. The proposed decoding algorithm applies to any binary linear code, does not require any data storage and is well suitable for parallel processing. Furthermore, the maximum number of computations required at each reprocessing stage is fixed, which prevents buffer overflow at low SNR. Further reductions of the number of computations based on probabilistic or decomposable properties of the code considered are also investigated. The generalization of the algorithm to other channels is discussed. Finally, the discrete time channel associated with the AWGN model after ordering is greatly simplified. This simplification allows an important reduction of the number of computations required to evaluate the theoretical error performance of any algorithm based on a partial or total ordering.

•Jan 1, 1994•0 citations

Half-ChaseAlgorithm ofNon-softDecision Decoding Based on Majority

Chun-Fong Kuo, Hsin-Kun Lai, Erl‐Huei Lu

Anon-soft decision decoding algorithm forbinary linear block codes transmitted overAWGN channel ispresented. Unlike soft decision decoding algorithms, theproposed algorithm doesnotcomputing weighted Hammingdistances. Basedonthe majority ofcodewordcandidates fromtheharddecision decodingoutput,the proposedalgorithmimproves error-correcting performance byldBofcoding gaincompared tothatofharddecision decoding algorithms. Also, aschematic block diagram forfinding thecodewordofmajority isdeveloped. Furthermore, a comparison ofhardware complexity ismade between thecomputation ofweighted Hammingdistances and thefinding ofmajority codeword.

•Jan 1, 2007•0 citations

On the reliability-order-based decoding algorithms for binary linear block codes

Yuansheng Tang, San Ling, Fang‐Wei Fu

In this correspondence, we consider the decoding of binary block codes over the additive white Gaussian noise (AWGN) channel with binary phase-shift keying (BPSK) signaling. By a reliability-order-based decoding algorithm (ROBDA), we mean a soft-decision decoding algorithm which decodes to the best (most likely) codeword of the form that is the sum of the hard-decision tuple and an error pattern in a set determined only by the order of the reliabilities of the hard decisions. Examples of ROBDAs include many well-known decoding algorithms, such as the generalized-minimum-distance (GMD) decoding algorithm, Chase decoding algorithms, and the reliability-based decoding algorithms proposed by Fossorier and Lin. It is known that the squared error-correction-radii of ROBDAs can be computed from the minimal squared Euclidean distances (MSEDs) between the all-one sequence and the polyhedra corresponding to the error patterns. For the computation of such MSEDs, we give a new method which is more compact than the one proposed by Fossorier and Lin. These results are further used to show that any bounded-distance ROBDA is asymptotically optimal: The ratio between the probability of decoding error of a bounded-distance ROBDA and that of the maximum-likelihood (ML) decoding approaches 1 when the signal-to-noise ratio (SNR) approaches infinity, provided that the minimum Hamming distance of the code is greater than 2.

IEEE Transactions on Information Theory•Dec 28, 2005•8 citations

Iterative Soft-Decision Decoding of Binary Cyclic Codes Based on Extended Parity-Check Transformation Algorithm

Oluwaseyi Paul Babalola, D.J.J. Versfeld

In this paper, an iterative soft-decision (SD) decoding algorithm for cyclic codes based on extended parity-check equations is developed. The algorithm does not necessarily utilize the algebraic properties of the code, but operates on transforming the systematic parity-check matrix using the soft reliability information matrix obtained from the received vector. Results show a significant performance gain when compared with the hard decision Berlekamp-Massey(B-M) and belief propagation (BP) algorithms, but present a similar bit error rate (BER) performance when compared to the adaptive belief propagation (ABP) algorithm. An important feature of the decoder is that it functions within a practical decoding time complexity, and can be generally implemented for the class of linear block codes.

Conference proceedings - Canadian Conference on Electrical and Computer Engineering•May 1, 2018•3 citations
In this paper we present an efficient algorithm to decode linear block codes on binary channels. The main idea consists in using a vote procedure in order to elaborate artificial reliabilities of the binary received word and to present the obtained real vector r as inputs of a SIHO decoder (Soft In/Hard Out). The goal of the latter is to try to find the closest codeword to r in terms of the Euclidean distance. A comparison of the proposed algorithm over the AWGN channel with the Majority logic decoder, Berlekamp-Massey, Bit Flipping, Hartman-Rudolf algorithms and others show that it is more efficient in terms of performance. The complexity of the proposed decoder depends on the weight of the error to decode, on the code structure and also on the used SIHO decoder.
This paper presents an approach to soft-decision decoding for a (n, k) binary linear block code. This approach achieves near-optimal to optimal performance for any signal-to-noise ratio value. The proposed decoding is based on the reordering of the received symbols according to their reliability measure and can be applied to any binary linear code. The basic idea is to generate a sequence of codewords such that there will be a high probability that the next codeword is closer to the received vector. In this algorithm the information provided by the soft-decisions is used to generate information sets utilized in decoding. A fast procedure checks whether a given set of k positions is an information set. A sequence of codewords is reconstructed using a sequence of information sets. Each codeword reconstructed is compared with the received word and the closest one is selected. Hence, the decoding algorithm is an iterative procedure designed to enhance the performance of the usual soft-decision decoding, since with each iteration of the procedure, real vectors successively closer to the received vector are examined. A high performance stop rule is utilized to reduce the number of generated information sets, stopping the decoding process when a codeword is closest to the received sequence.
A non-soft decision decoding algorithm for binary linear block codes transmitted over AWGN channel is presented. Unlike soft decision decoding algorithms, the proposed algorithm does not computing weighted Hamming distances. Based on the majority of code word candidates from the hard decision decoding output, the proposed algorithm improves error-correcting performance by 1 dB of coding gain compared to that of hard decision decoding algorithms. Also, a schematic block diagram for finding the codeword of majority is developed. Furthermore, a comparison of hardware complexity is made between the computation of weighted Hamming distances and the finding of majority code word.
This dissertation presents a novel approach to soft decision decoding for binary linear block codes. The basic idea of this approach is to achieve a desired error performance progressively in a number of stages. For each decoding stage, the error performance is highly bounded and the decoding is terminated at the stage where either near-optimum error performance or a desired level of error performance is achieved. As a result, more flexibility in the trade-off between performance and decoding complexity is provided. The proposed decoding is based on the reordering of the received symbols according to their reliability measure. In the dissertation, we evaluate the statistics of the noise after ordering. Based on these statistics, we derive two monotonic properties which dictate the reprocessing strategy. Each codeword is decoded in two steps: (1) hard-decision decoding based on reliability information and (2) reprocessing of the hard-decision decoded codeword in successive stages until the desired performance is achieved. The reprocessing is based on the monotonic properties of the ordering and is carried out using a cost function. A new resource test highly related to the reprocessing strategy is introduced to reduce the number of computations for each reprocessing stage. For short codes of lengths N ≤ 32 or medium codes with 32 < N ≤ 64 with rate R ≥ 0.6, near-optimum bit error performance is achieved in two stages of reprocessing with at most a computation complexity of o(K2) constructed code-words, where K is the dimension of the code. For longer codes, three or more reprocessing stages are required to achieve near-optimum decoding. However, most of the coding gain is obtained within the first two reprocessing stages for error performances of practical interest. The proposed decoding algorithm applies to any binary linear code, does not require any data storage and is well suitable for parallel processing. Furthermore, the maximum number of computations required at each reprocessing stage is fixed, which prevents buffer overflow at low SNR. Further reductions of the number of computations based on probabilistic or decomposable properties of the code considered are also investigated. The generalization of the algorithm to other channels is discussed. Finally, the discrete time channel associated with the AWGN model after ordering is greatly simplified. This simplification allows an important reduction of the number of computations required to evaluate the theoretical error performance of any algorithm based on a partial or total ordering.
Anon-soft decision decoding algorithm forbinary linear block codes transmitted overAWGN channel ispresented. Unlike soft decision decoding algorithms, theproposed algorithm doesnotcomputing weighted Hammingdistances. Basedonthe majority ofcodewordcandidates fromtheharddecision decodingoutput,the proposedalgorithmimproves error-correcting performance byldBofcoding gaincompared tothatofharddecision decoding algorithms. Also, aschematic block diagram forfinding thecodewordofmajority isdeveloped. Furthermore, a comparison ofhardware complexity ismade between thecomputation ofweighted Hammingdistances and thefinding ofmajority codeword.
In this correspondence, we consider the decoding of binary block codes over the additive white Gaussian noise (AWGN) channel with binary phase-shift keying (BPSK) signaling. By a reliability-order-based decoding algorithm (ROBDA), we mean a soft-decision decoding algorithm which decodes to the best (most likely) codeword of the form that is the sum of the hard-decision tuple and an error pattern in a set determined only by the order of the reliabilities of the hard decisions. Examples of ROBDAs include many well-known decoding algorithms, such as the generalized-minimum-distance (GMD) decoding algorithm, Chase decoding algorithms, and the reliability-based decoding algorithms proposed by Fossorier and Lin. It is known that the squared error-correction-radii of ROBDAs can be computed from the minimal squared Euclidean distances (MSEDs) between the all-one sequence and the polyhedra corresponding to the error patterns. For the computation of such MSEDs, we give a new method which is more compact than the one proposed by Fossorier and Lin. These results are further used to show that any bounded-distance ROBDA is asymptotically optimal: The ratio between the probability of decoding error of a bounded-distance ROBDA and that of the maximum-likelihood (ML) decoding approaches 1 when the signal-to-noise ratio (SNR) approaches infinity, provided that the minimum Hamming distance of the code is greater than 2.
In this paper, an iterative soft-decision (SD) decoding algorithm for cyclic codes based on extended parity-check equations is developed. The algorithm does not necessarily utilize the algebraic properties of the code, but operates on transforming the systematic parity-check matrix using the soft reliability information matrix obtained from the received vector. Results show a significant performance gain when compared with the hard decision Berlekamp-Massey(B-M) and belief propagation (BP) algorithms, but present a similar bit error rate (BER) performance when compared to the adaptive belief propagation (ABP) algorithm. An important feature of the decoder is that it functions within a practical decoding time complexity, and can be generally implemented for the class of linear block codes.