An official website of the United States government
Maximum-likelihood (ML) decoding of tail-biting convolutional codes (TBCCs) with S=2v states traditionally requires a separate S-state trellis for each of the S possible starting/ending states, resulting in complexity proportional to S2. Lower-complexity ML decoders for TBCCs have complexity proportional to S log S. This high complexity motivates the use of the wrap-around Viterbi algorithm, which sacrifices ML performance for complexity proportional to S.This paper presents an ML decoder for TBCCs that uses list decoding to achieve an average complexity proportional to S at operational signal-to-noise ratios where the expected list size is close to one. The new decoder uses parallel list Viterbi decoding with a progressively growing list size operating on a single S-state trellis. Decoding does not terminate until the most likely tailbiting codeword has been identified. This approach is extended to ML decoding of tail-biting convolutional codes concatenated with a cyclic redundancy check code as explored recently by Yang et al. and King et al. Constraining the maximum list size further reduces complexity but sacrifices guaranteed ML performance, increasing errors and introducing erasures.
more »
« less
This content will become publicly available on August 18, 2026
Action-List Reinforcement Learning Decoders
This paper explores the application of reinforcement learning techniques to enhance the performance of decoding based on flipping bits and finding optimal decisions. We begin by providing an overview of bit-flipping-based decoders and reinforcement learning algorithms. We then describe the methodology for mapping the iterative decoding process into Markov Decision Processes (MDPs) and propose a general action list decoding method for reinforcement learning based decoders, irrespective of the class of codes, to improve the performance of decoders. We design an action-list decoder based on the Deep-Q network values that substantially enhance performance. We also get the benefit of the automorphism group of the code to further improve code performance. Finally, we present experimental results for the Binary Symmetric Channel (BSC) to demonstrate the efficiency of the proposed methods.
more »
« less
- Award ID(s):
- 2420424
- PAR ID:
- 10645543
- Publisher / Repository:
- IEEE
- Date Published:
- Page Range / eLocation ID:
- 1 to 5
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We consider autocorrelation-based low-complexity decoders for identifying Binary Chirp codewords from noisy signals in N = 2^m dimensions. The underlying algebraic structure enables dimensionality reduction from N complex to m binary dimensions, which can be used to reduce decoding complexity, when decoding is successively performed in the m binary dimensions. Existing low-complexity decoders suffer from poor performance in scenarios with strong noise. This is problematic especially in a vector quantization scenario, where quantization noise power cannot be controlled in the system. We construct two improvements to existing algorithms; a geometrically inspired algorithm based on successive projections, and an algorithm based on adaptive decoding order selection. When combined with a breadth-first list decoder, these algorithms make it possible to approach the performance of exhaustive search with low complexity.more » « less
-
Convolutional codes have been widely studied and used in many systems. As the number of memory elements increases, frame error rate (FER) improves but computational complexity increases exponentially. Recently, decoders that achieve reduced average complexity through list decoding have been demonstrated when the convolutional encoder polynomials share a common factor that can be understood as a CRC or more generally an expurgating linear function (ELF). However, classical convolutional codes avoid such common factors because they result in a catastrophic encoder. This paper provides a way to access the complexity reduction possible with list decoding even when the convolutional encoder polynomials do not share a common factor. Decomposing the original code into component encoders that fully exclude some polynomials can allow an ELF to be factored from each component. Dual list decoding of the component encoders can often find the ML codeword. Including a fallback to regular Viterbi decoding yields excellent FER performance while requiring less average complexity than always performing Viterbi on the original trellis. A best effort dual list decoder that avoids Viterbi has performance similar to the ML decoder. Component encoders that have a shared polynomial allow for even greater complexity reduction.more » « less
-
This work develops a novel design of joint detection and decoding receiver for multiple-input multiple output (MIMO) wireless transmissions that utilizes polar codes in forward error correction (FEC). To optimize the overall receiver performance, we integrate the polar code constraints during signal detection by relaxing and transforming FEC code constraints from the original Galois field to the real field. We propose a novel joint linear programming (LP) optimization formulation that takes into consideration the transformed polar code constraints when designing a novel receiver robust against practical obstacles including channel state information (CSI) errors, additive noises, co-channel interferences, and pilot contamination. Our newly proposed joint LP formulation can also be integrated with reduced complexity polar decoders such as successive cancellation (SC) and successive cancellation list (SCL) decoders to deliver superior receiver performance at low cost.more » « less
-
In the short blocklength regime, serial list decoding of tail-biting (TB) convolutional codes concatenated with an expurgating linear function (ELF) can approach the random coding union bound on frame error rate (FER) performance. Decoding complexity for a particular received word depends on how deep in the list the decoder must search to find a valid TB-ELF codeword. The average list size is close to one at low-FER operating points such as 10^−6, and serial list decoding provides a favorable average complexity compared to other decoders with similar performance for these cases. However, the average list size can be on the order of a hundred or a thousand at higher, but still practically important, FER operating points such as 10−3. It is useful to study the tradeoff between how deep the decoder is willing to search and the proximity to the frame error rate (FER) achieved by an ML decoder. Often, this tradeoff is framed in terms of a maximum list depth. However, this paper frames the tradeoff in terms of a maximum allowable metric between the received word and the trellis paths on the list. We consider metrics of Euclidean distance and angle. This new approach draws on the wealth of existing literature on bounded-metric decoding to provide characterizations of how the choice of maximum allowable metric controls the tradeoffs between FER performance and both decoding complexity and undetected error rate. These characterizations lead to an example of an ELF-TB convolutional code that outperforms recent results for polar codes in terms of the lowest SNR that simultaneously achieves both a total error rate less than T = 10^−3 and an undetected error rate below U = 10^−5.more » « less
