An official website of the United States government
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
Bounds on the List Size of Successive Cancellation List Decoding
Successive cancellation list decoding of polar codes provides very good performance for short to moderate block lengths. However, the list size required to approach the performance of maximum-likelihood decoding is still not well understood theoretically. This work identifies information-theoretic quantities that are closely related to this required list size. It also provides a natural approximation for these quantities that can be computed efficiently even for very long codes. Simulation results are provided for the binary erasure channel as well as the binary-input additive white Gaussian noise channel.
more »
« less
- Award ID(s):
- 1718494
- PAR ID:
- 10303734
- Date Published:
- Journal Name:
- 2020 International Conference on Signal Processing and Communications (SPCOM)
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
List-decodability of Reed-Solomon codes has received a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focus on the case where the list-decoding radius is of the form r=1−ε for ε tending to zero. Our main result states that there exist Reed-Solomon codes with rate Ω(ε) which are (1−ε,O(1/ε)) -list-decodable, meaning that any Hamming ball of radius 1−ε contains at most O(1/ε) codewords. This trade-off between rate and list-decoding radius is best-possible for any code with list size less than exponential in the block length. By achieving this trade-off between rate and list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and Wootters, and resolve the main motivating question of their work. Moreover, while their result requires the field to be exponentially large in the block length, we only need the field size to be polynomially large (and in fact, almost-linear suffices). We deduce our main result from a more general theorem, in which we prove good list-decodability properties of random puncturings of any given code with very large distance.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
-
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
-
Lapidoth, Amos; Moser, Stefan M (Ed.)This paper introduces extensions to data-driven polar decoders, enabling list decoding and accommodating asymmetric input distributions. These are crucial steps to develop data-driven codes that 1) achieve capacity and 2) are competitive in moderate block lengths. We commence by integrating list de- coding into the data-driven polar codes, which significantly alleviates the inherent error propagation issues associated with successive cancellation decoding. Secondly, we expand the applicability of these codes to channels with stationary, non-uniform input distributions by incorporating the Honda-Yamamoto scheme. Both modifications are computationally efficient and do not require an explicit channel model. Numerical results validate the efficacy of our contributions, which offer a robust and versatile coding mechanism for various channel conditions.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/SPCOM50965.2020.9179593
