Search

We establish that it is possible to extract accurate blockwise and bitwise soft output from Guessing Codeword Decoding with minimal additional computational complexity by considering it as a variant of Guessing Random Additive Noise Decoding. Blockwise soft output can be used to control decoding misdetection rate while bitwise soft output results in a soft-input soft-output decoder that can be used for efficient iterative decoding of long, high redundancy codes.

We present a framework that can exploit the tradeoff between the undetected error rate (UER) and block error rate (BLER) of polar-like codes. It is compatible with all successive cancellation (SC)-based decoding methods and relies on a novel approximation that we call codebook probability. This approximation is based on an auxiliary distribution that mimics the dynamics of decoding algorithms following an SC decoding schedule. Simulation results demonstrates that, in the case of SC list (SCL) decoding, the proposed framework outperforms the state-of-art approximations from Forney's generalized decoding rule for polar-like codes with dynamic frozen bits. In addition, dynamic Reed-Muller (RM) codes using the proposed generalized decoding significantly outperform CRC-concatenated polar codes decoded using SCL in both BLER and UER. Finally, we briefly discuss three potential applications of the approximated codebook probability: coded pilot-free channel estimation; bitwise soft-output decoding; and improved turbo product decoding., Comment: being published at IEEE ISIT 2024

For a multiple-input multiple-output (MIMO) system with unknown channel state information (CSI), a novel low-density parity check (LDPC)-coded transmission (LCT) scheme with joint pilot and data channel estimation is proposed. To fine-tune the CSI, a method based on the constraints introduced by the coded data from an LDPC code is designed such that the MIMO detector exploits the fine-tuned CSI. For reducing the computational burden, a coordinate ascent algorithm is employed along with several approximation methods, effectively reducing the required times of MIMO detection and computational complexity to achieve a satisfying performance. Simulation results utilizing WiMAX standard LDPC codes and quadrature phase-shift keying (QPSK) modulation demonstrate gains of up to 1.3 dB at a frame error rate (FER) of $10^{-4}$ compared to pilot-assisted transmission (PAT) over Rayleigh block-fading channels., Comment: This paper has been accepted by IEEE Wireless Communications Letters

We establish that a large, flexible class of long, high redundancy error correcting codes can be efficiently and accurately decoded with guessing random additive noise decoding (GRAND). Performance evaluation demonstrates that it is possible to construct simple concatenated codes that outperform low-density parity-check (LDPC) codes found in the 5G New Radio standard in both additive white Gaussian noise (AWGN) and fading channels. The concatenated structure enables many desirable features, including: low-complexity hardware-friendly encoding and decoding; significant flexibility in length and rate through modularity; and high levels of parallelism in encoding and decoding that enable low latency. Central is the development of a method through which any soft-input (SI) GRAND algorithm can provide soft-output (SO) in the form of an accurate a-posteriori estimate of the likelihood that a decoding is correct or, in the case of list decoding, the likelihood that each element of the list is correct. The distinguishing feature of soft-output GRAND (SOGRAND) is the provision of an estimate that the correct decoding has not been found, even when providing a single decoding. That per-block SO can be converted into accurate per-bit SO by a weighted sum that includes a term for the SI. Implementing SOGRAND adds negligible computation and memory to the existing decoding process, and using it results in a practical, low-latency alternative to LDPC codes., Comment: arXiv admin note: substantial text overlap with arXiv:2305.05777

Guessing Random Additive Noise Decoding (GRAND) is a family of hard- and soft-detection error correction decoding algorithms that provide accurate decoding of any moderate redundancy code of any length. Here we establish a method through which any soft-input GRAND algorithm can provide soft output in the form of an accurate a posteriori estimate of the likelihood that a decoding is correct or, in the case of list decoding, the likelihood that the correct decoding is an element of the list. Implementing the method adds negligible additional computation and memory to the existing decoding process. The output permits tuning the balance between undetected errors and block errors for arbitrary moderate redundancy codes including CRCs

In this work, we investigate guessing random additive noise decoding (GRAND) with quantized soft input. First, we analyze the achievable rate of ordered reliability bits GRAND (ORBGRAND), which uses the rank order of the reliability as quantized soft information. We show that multi-line ORBGRAND can approach capacity for any signal-to-noise ratio (SNR). We then introduce discretized soft GRAND (DSGRAND), which uses information from a conventional quantizer. Simulation results show that DSGRAND well approximates maximum-likelihood (ML) decoding with a number of quantization bits that is in line with current soft decoding implementations. For a (128,106) CRC-concatenated polar code, the basic ORBGRAND is able to match or outperform CRC-aided successive cancellation list (CA-SCL) decoding with codeword list size of 64 and 3 bits of quantized soft information, while DSGRAND outperforms CA-SCL decoding with a list size of 128 codewords. Both ORBGRAND and DSGRAND exhibit approximately an order of magnitude less average complexity and two orders of magnitude smaller memory requirements than CA-SCL.

A tree search algorithm called successive cancellation ordered search (SCOS) is proposed for $\boldsymbol{G}_N$-coset codes that implements maximum-likelihood (ML) decoding with adaptive complexity for transmission over binary-input AWGN channels. Unlike bit-flip decoders, no outer code is needed to terminate decoding; therefore, SCOS also applies to $\boldsymbol{G}_N$-coset codes modified with dynamic frozen bits. The average complexity is close to that of successive cancellation (SC) decoding at practical frame error rates (FERs) for codes with wide ranges of rate and lengths up to $512$ bits, which perform within $0.25$ dB or less from the random coding union bound and outperform Reed--Muller codes under ML decoding by up to $0.5$ dB. Simulations illustrate simultaneous gains for SCOS over SC-Fano, SC stack (SCS) and SC list (SCL) decoding in FER and the average complexity at various SNR regimes. SCOS is further extended by forcing it to look for candidates satisfying a threshold, thereby outperforming basic SCOS under complexity constraints. The modified SCOS enables strong error-detection capability without the need for an outer code. In particular, the $(128, 64)$ polarization-adjusted convolutional code under modified SCOS provides gains in overall and undetected FER compared to CRC-aided polar codes under SCL/dynamic SC flip decoding at high SNR., Comment: 13 pages, 9 figures, 4 tables. To appear in IEEE TCOM. arXiv admin note: text overlap with arXiv:2105.04048

A complexity-adaptive tree search algorithm is proposed for $\boldsymbol{G}_N$-coset codes that implements maximum-likelihood (ML) decoding by using a successive decoding schedule. The average complexity is close to that of the successive cancellation (SC) decoding for practical error rates when applied to polar codes and short Reed-Muller (RM) codes, e.g., block lengths up to $N=128$. By modifying the algorithm to limit the worst-case complexity, one obtains a near-ML decoder for longer RM codes and their subcodes. Unlike other bit-flip decoders, no outer code is needed to terminate decoding. The algorithm can thus be applied to modified $\boldsymbol{G}_N$-coset code constructions with dynamic frozen bits. One advantage over sequential decoders is that there is no need to optimize a separate parameter., Comment: Accepted for a presentation at ITW2021

A polar-coded transmission (PCT) scheme with joint channel estimation and decoding is proposed for channels with unknown channel state information (CSI). The CSI is estimated via successive cancellation (SC) decoding and the constraints imposed by the frozen bits. SC list decoding with an outer code improves performance, including resolving a phase ambiguity when using quadrature phase-shift keying (QPSK) and Gray labeling. Simulations with 5G polar codes and QPSK show gains of up to $2$~dB at a frame error rate (FER) of $10^{-4}$ over pilot-assisted transmission for various non-coherent models. Moreover, PCT performs within a few tenths of a dB to a coherent receiver with perfect CSI. For Rayleigh block-fading channels, PCT outperforms an FER upper bound based on random coding and within one dB of a lower bound., Comment: Accepted for publication in IEEE Communications Letters

The probabilistic shaping scheme from Honda and Yamamoto (2013) for polar codes is used to enable power-efficient signaling for on-off keying (OOK). As OOK has a non-symmetric optimal input distribution, shaping approaches that are based on the concatenation of a distribution matcher followed by systematic encoding do not result in optimal signaling. Instead, these approaches represent a time sharing scheme where only a fraction of the codeword symbols is shaped. The proposed scheme uses a polar code for joint distribution matching and forward error correction which enables asymptotically optimal signaling. Numerical simulations show a gain of 1.8 dB compared to uniform transmission at a spectral efficiency of 0.25 bits/channel use for a blocklength of 65,536 bits., Comment: accepted for publication in IEEE Communications Letters

Polar codes are designed for parallel binary-input additive white Gaussian noise (BiAWGN) channels with an average power constraint. The two main design choices are: the mapping between codeword bits and channels of different quality, and the power allocation under the average power constraint. Information theory suggests to allocate power such that the sum of mutual information (MI) terms is maximized. However, a power allocation specific to polar codes shows significant gains., Comment: Will be presented at ISIT 2019

BMERA or convolutional polar codes are an extension of polar codes with a provably better error exponent than polar codes. A successive cancellation (SC) decoding algorithm for BMERA codes similar to SC polar decoders is introduced. A pseudocode description of the SC decoder that can be extended to SC list (SCL) decoding is provided. Simulation results with and without outer CRC codes under SC and SCL decoding are presented for QAM modulation over the AWGN channel to compare the performance of polar and BMERA codes. BMERA codes outperform polar codes by more than 0.5 dB under SCL decoding without outer CRC codes., Comment: submitted to ISTC 2018

Polar codes based on $2\times2$ non-binary kernels are discussed in this work. The kernel over $\text{GF}(q)$ is selected by maximizing the polarization effect and using Monte-Carlo simulation. Belief propagation (BP) and successive cancellation (SC) based decoding algorithms are extended to non-binary codes. Additionally, a successive cancellation list (SCL) decoding with a pruned tree is proposed. Simulation results show that the proposed decoder performs very close to a conventional SCL decoder with significantly lower complexity.

A flexible incremental redundancy hybrid auto- mated repeat request (IR-HARQ) scheme for polar codes is proposed based on dynamically frozen bits and the quasi-uniform puncturing (QUP) algorithm. The length of each transmission is not restricted to a power of two. It is applicable for the binary input additive white Gaussian noise (biAWGN) channel as well as higher-order modulation. Simulation results show that this scheme has similar performance as directly designed polar codes with QUP and outperforms LTE-turbo and 5G-LDPC codes with IR-HARQ., Comment: 6 pages, accepted to 2018 IEEE Wireless Communications and Networking Conference Workshops (WCNCW): Polar Coding for Future Networks: Theory and Practice, presented on 15. April

A heuristic construction of polar codes for successive cancellation list (SCL) decoding with a given list size is proposed to balance the trade-off between performance measured in frame error rate (FER) and decoding complexity. Furthermore, a construction based on dynamically frozen bits with constraints among the "low weight bits" (LWB) is presented. Simulation results show that the LWB-polar codes outperform the CRC-polar codes and the eBCH-polar codes under SCL decoding., Comment: 6 pages

An efficient algorithm for the construction of polar codes for higher-order modulation is presented based on information-theoretic principles. The bit reliabilities after successive demapping are estimated using the LM-rate, an achievable rate for mismatched decoding. The successive demapper bit channels are then replaced by binary input Additive White Gaussian Noise (biAWGN) surrogate channels and polar codes are constructed using the Gaussian approximation (GA). This LM-rate Demapper GA (LM-DGA) construction is used to construct polar codes for several demapping strategies proposed in literature. For all considered demappers, the LM-DGA constructed polar codes have the same performance as polar codes constructed by Monte Carlo (MC) simulation. The proposed LM-DGA construction is much faster than the MC construction. For 64-QAM, spectral efficiency 3 bits/s/Hz, and block length 1536 bits, simulation results show that LM-DGA constructed polar codes with cyclic redundancy check and successive cancellation list decoding are 1 dB more power efficient than state-of-the-art AR4JA low-density parity-check codes., Comment: 11 figures