Fast A soft decision decoding for binary block codes
0
Citation
0
Reference
20
Related Paper
Abstract:
A novel minimum sequential increase decoding is presented, which is equivalent to the minimum Euclidean distance decoding. A new generalized threshold is also built up for the test sequence. The decoding problem is converted into a search progress on a direct tree. Then A algorithm with the new generalized threshold is applied to search on this tree. With the ability of heuristic search, A decoding algorithm can improve the decoding speed while the decoding performance remains optimal. Our computer simulations show the great advantages in decoding speed of A decoding algorithm over other soft decision decoding algorithms.Keywords:
List decoding
Berlekamp–Welch algorithm
Sequence (biology)
Tree (set theory)
Cite
Comparing with hard decision decoding algorithms, soft decoding has a lower probability of bit error but a higher computational complexity. As a maximum-likelihood soft decoding method, the $A^{\ast }$ algorithm is the most basic and widely used to minimize bit error probability. However, its average computational complexity strongly depends on a seed codeword and a heuristic function utilized during the decoding process. To efficiently reduce the computational complexity while maintaining the decoding accuracy theoretically and practically, this paper proposes an improved $A^{\ast }$ decoding algorithm consisting of two phases. The first phase applies the greedy list decoding to the linear block code to obtain a seed codeword. According to the seed, the second phase applies the improved $A^{\ast }$ algorithm to obtain the final decoding output. The heuristic function used in the $A^{\ast }$ algorithm is modified in two aspects: 1) use more information of partial decoded symbols to improve the accuracy of the function and 2) take advantage of Hamming distance to reduce the search space. Simulations on the $RM(5,2)$ Reed–Muller codes and [128, 64] binary extended BCH code show that this improved $A^{\ast }$ algorithm is more efficient in average decoding complexity than many other algorithms while maintaining the decoding accuracy.
List decoding
Code (set theory)
Cite
Citations (0)
An improved maximum likelihood soft decision decoding (SDA),using the Dijkstra's algorithm,is presented.Compared with the decodings available,the proposed decoding algorithm has following new advantages:(1)using a new metric function,which reduces decoding calculation;(2)applying a more efficient search algorithm,called DA to the maximum likelihood soft decision decoding;(3)setting up a new general threshold for error patterns to speed up the decoding further.Our simulation results show that SDA is much faster in mean decoding speed than other soft decision decoding algorithms without any loss of decoding performance.Meanwhile,it is emphasized that usage of non optimal transmission signal will result in nearly 3dB loss of decoding performance.
List decoding
Iterative Viterbi decoding
Berlekamp–Welch algorithm
Cite
Citations (0)
This paper focuses on analysing the operational complexity of decoding the progressive-edge-growth-based (PEG-based) method for the extended grouping of radio frequency identification (RFID) tags using the improved hybrid iterative/Gaussian elimination decoding algorithm. In addition, the joint use of two decoding components is adapted based on the missing amounts of RFID tags and group sizes in order to avoid iterative decoding when the missing amounts is larger than a threshold and thus to save more decoding time. Various simulations have been carried out to analyse and evaluate the decoding complexity as well as the impact of the threshold value on decoding time. Simulation results are presented, demonstrating that the improved hybrid decoding algorithm achieves low decoding complexity and thus decoding time when compared to the full Gaussian elimination decoding algorithm.
List decoding
Berlekamp–Welch algorithm
Iterative Viterbi decoding
Cite
Citations (1)
The MAP algorithm is a trellis-based maximum a posteriori probability decoding algorithm. It is the heart of the turbo decoding or iterative decoding which can achieve an error performance near the Shannon limit. Unfortunately, the implementation of this algorithm requires large computation and storage. Furthermore, its forward and backward recursions cause long decoding delay. For practical applications, this decoding algorithm must be simplified and its decoding complexity and delay must be reduced. In this paper, the MAP and max-log-MAP algorithms are first applied to sectionalized trellises for linear block codes. Using the structural properties of properly sectionalized trellises, the decoding complexity and delay of the MAP algorithms can be reduced. Also presented in this paper are bi-directional and parallel MAP decoding.
Trellis (graph)
List decoding
Berlekamp–Welch algorithm
BCJR algorithm
Turbo code
Convolutional code
Difference-map algorithm
Noisy-channel coding theorem
Cite
Citations (7)
In this paper, soft-decision decoding is considered as an optimisation problem and a computationally efficient soft-decision decoding algorithm for block codes is developed using a compact Genetic Algorithm. The performance of this algorithm is investigated and compared with other decoding schemes. The results show the proposed algorithm gives large gains over the Generalised Minimum Distance (GMD) decoding algorithm and algebraic hard-decision decoding in flat Rayleigh fading. Further, the proposed algorithm achieves near maximum likelihood decoder (MLD) performance for the codes simulated. The complexity of this algorithm is also discussed and compared to the standard Order-l reprocessing algorithm.
Berlekamp–Welch algorithm
List decoding
BCJR algorithm
Cite
Citations (7)
We propose a two-dimensional modified min-sum algorithm for the LDPC codes in the fifth generation (5G) networks standard to approach the error performance of the sum-product algorithm (SPA). In the proposed decoding algorithm, we adopt a partial self-correction method followed by message amplification to improve the reliability of the variable-to-check (V2C) messages. To further approach the performance of the maximum likelihood decoding for 5G short LDPC codes, we propose an enhanced quasi-maximum likelihood (EQML) decoding method. The proposed decoding method performs multiple rounds of decoding tests once the first decoding attempt fails, where the decoder inputs of the selected unreliable variable nodes are modified in each decoding test. A novel node selection method based on the sign fluctuation of V2C messages is proposed for the EQML decoding method. We also present a partial pruning stopping (PPS) rule to reduce the decoding complexity by deactivating part of the decoding tests once a valid codeword is found. A lower bound on the error performance is also derived by using the semi-analytical method. Simulation results show that the EQML decoding method outperforms the SPA with the same decoding complexity and other QML decoding methods, and it approaches the Polyanskiy-Poor-Verdú bound within 0.4 dB.
List decoding
Berlekamp–Welch algorithm
Cite
Citations (14)
A new sequential decoding algorithm with an adjustable threshold and a new method of moving through the decoding tree is proposed.Instead ofthe path metric of the conventional sequential decoding algorithms,the proposed algorithm uses a branchmetric based on maximum-likelihood criterion.Two new parameters,the jumping-back distance and going-back distance,are also introduced.The performance of the algorithm for long constraint length convolutional codes is compared to those of the other sequential decoding algorithms and the Viterbi algorithm.The results show that the proposed algorithm is a good candidate for decoding of convolutional codes due to its fast decoding capability and good bit error rate(BER) performance.
Convolutional code
Iterative Viterbi decoding
List decoding
Viterbi algorithm
Berlekamp–Welch algorithm
Viterbi decoder
Cite
Citations (0)
We present an efficient soft decision maximum likelihood decoding algorithm for linear binary block codes. As in the Chase algorithms, test error patterns are generated, added to the received sequence and decoded, using a hard decision decoder. However, the set of test error sequences is adaptively chosen. This significantly reduces decoding complexity. Furthermore a sub-optimal decoding algorithm is developed by introducing constraints on the set of test error patterns used.
List decoding
Berlekamp–Welch algorithm
Sequence (biology)
Cite
Citations (0)
We introduce a new binary message-passing decoding method for low-density parity-check (LDPC) codes. The proposed decoding principle does not require the degree information of variable nodes and can be applied to both timeinvariant and time-variant decoding algorithms. We present the extrinsic error probability analysis and decoding threshold optimization for the new decoding method in both time-invariant and time-variant decoding scenarios. Both theoretical analysis and numerical results show that the proposed method provides the same performance as the existing methods for both time-invariant and time-variant decoding, while the proposed new method facilitates efficient circuit implementations of the LDPC decoder since it does not require the degree information.
List decoding
Berlekamp–Welch algorithm
Cite
Citations (9)
Trellis (graph)
List decoding
Iterative Viterbi decoding
Viterbi algorithm
Cite
Citations (8)