Soft-decision decoding of binary linear block codes based on an iterative search algorithm

This article presents a suboptimum soft-decision decoding scheme for binary linear block codes based on an iterative search algorithm. The scheme uses an algebraic decoder to iteratively generate a sequence of candidate codewords one at a time using a set of test error patterns that are constructed...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 1997-05, Vol.43 (3), p.1030-1040
Main Authors: Moorthy, H.T., Shu Lin, Kasami, T.
Format: Article
Language:English
Subjects:
Algorithms
Binary system
Block codes
Codes
Computational complexity
Computer Programming And Software
Information technology
Iterative algorithms
Iterative decoding
Maximum likelihood decoding
NASA
Nearest neighbor searches
Test pattern generators
Testing
Viterbi algorithm
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This article presents a suboptimum soft-decision decoding scheme for binary linear block codes based on an iterative search algorithm. The scheme uses an algebraic decoder to iteratively generate a sequence of candidate codewords one at a time using a set of test error patterns that are constructed based on the reliability information of the received symbols. When a candidate codeword is generated, it is tested based on an optimality condition. If it satisfies the optimality condition, then it is the most likely (ML) codeword and the decoding stops. If it fails the optimality test, a search for the ML codeword is conducted in a region which contains the ML codeword. The search region is determined by the current candidate codeword and the reliability of the received symbols. The search is conducted through a purged trellis diagram for the given code using the Viterbi algorithm. If the search fails to find the ML codeword, a new candidate is generated using a new test error pattern, and the optimality test and search are renewed. The process of testing and search continues until either the ML codeword is found or all the test error patterns are exhausted and the decoding process is terminated. Numerical results show that the proposed decoding scheme achieves either practically optimal performance or a performance only a fraction of a decibel away from the optimal maximum-likelihood decoding with a significant reduction in decoding complexity compared with the Viterbi decoding based on the full trellis diagram of the codes.
ISSN:0018-9448
1557-9654
DOI:10.1109/18.568717