Maximum Likelihood (ML) decoding of forward error correction codes is known to be optimally accurate, but is not used in practice as it proves too challenging to efficiently implement. Here we propose a development of a previously described hard detection ML decoder called Guessing Random Additive Noise Decoding (GRAND). We introduce Soft GRAND (SGRAND), a ML decoder that fully avails of soft detection information and is suitable for use with any arbitrary high-rate, short-length block code. We assess SGRAND's performance on Cyclic Redundancy Check (CRC)-aided Polar (CA-Polar) codes, which will be used for all control channel communication in 5G New Radio (NR), comparing its accuracy with CRC-Aided Successive Cancellation List decoding (CA-SCL), a state-of-the-art soft-information decoder specific to CA-Polar codes.
Maximum Likelihood (ML) decoding of forward error correction codes is known to be optimally accurate, but is not used in practice as it proves too challenging to efficiently implement. Here we propose a development of a previously described hard detection ML decoder called Guessing Random Additive Noise Decoding (GRAND). We introduce Soft GRAND (SGRAND), a ML decoder that fully avails of soft detection information and is suitable for use with any arbitrary high-rate, short-length block code. We assess SGRAND's performance on Cyclic Redundancy Check (CRC)-aided Polar (CA-Polar) codes, which will be used for all control channel communication in 5G New Radio (NR), comparing its accuracy with CRC-Aided Successive Cancellation List decoding (CA-SCL), a state-of-the-art soft-information decoder specific to CA-Polar codes.
Guessing random additive noise decoding (GRAND) is a recently proposed decoding algorithm which can achieve the error performance of maximum likelihood (ML) decoding. However, GRAND and its variants are only suitable for some short codes with high code rates and have large average query numbers. To mitigate these problems, we propose a successive cancellation list (SCL)-GRAND decoding algorithm for the cyclic redundancy check concatenated polar (CRC-polar) codes. The proposed decoder first divides the received sequence into two subblocks. Then SCL is used to decode the upper subblock and output several candidates into the candidate list. For each candidate, GRAND is used to decode the lower subblock and finally choose the most-likely codeword as the decoded result. Since the SCL is integrated into the SCL-GRAND algorithm, this algorithm can achieve lower complexity and better flexibility than the original GRAND.
Modern applications are driving demand for ultra-reliable low-latency communications, rekindling interest in the performance of short, high-rate error correcting codes. To that end, here we introduce a soft-detection variant of Guessing Random Additive Noise Decoding (GRAND) called Ordered Reliability Bits GRAND that can decode any moderate redundancy block-code. For a code of n bits, it avails of no more than ⎾log2(n)⏋ bits of code-book-independent quantized soft detection information per received bit to determine an accurate decoding while retaining the original algorithm’s suitability for a highly parallelized implementation in hardware. ORBGRAND is shown to provide similar block error performance for codes of distinct classes (BCH, CA-Polar and RLC) with low complexity, while providing better block error rate performance than CA-SCL, a state of the art soft detection CA-Polar decoder.
CRC codes have long since been adopted in a vast range of applications. The established notion that they are suitable primarily for error detection can be set aside through use of the recently proposed Guessing Random Additive Noise Decoding (GRAND). Hard-detection (GRAND-SOS) and soft-detection (ORBGRAND) variants can decode any short, high-rate block code, making them suitable for error correction of CRC-coded data. When decoded with GRAND, short CRC codes have error correction capability that is at least as good as popular codes such as BCH codes, but with no restriction on either code length or rate.The state-of-the-art CA-Polar codes are concatenated CRC and Polar codes. For error correction, we find that the CRC is a better short code than either Polar or CA-Polar codes. Moreover, the standard CA-SCL decoder only uses the CRC for error detection and therefore suffers severe performance degradation in short, high rate settings when compared with the performance GRAND provides, which uses all of the CA-Polar bits for error correction.Using GRAND, existing systems can be upgraded from error detection to low-latency error correction without re-engineering the encoder, and additional applications of CRCs can be found in IoT, Ultra-Reliable Low Latency Communication (URLLC), and beyond. The universality of GRAND, its ready parallelized implementation in hardware, and the good performance of CRC as codes make their combination a viable solution for low-latency applications.
Error correction techniques traditionally focus on the co-design of restricted code-structures in tandem with code-specific decoders that are computationally efficient when decoding long codes in hardware. Modern applications are, however, driving demand for ultra-reliable low-latency communications (URLLC), rekindling interest in the performance of shorter, higher-rate error correcting codes, and raising the possibility of revisiting universal, code-agnostic decoders. To that end, here we introduce a soft-detection variant of Guessing Random Additive Noise Decoding (GRAND) called Ordered Reliability Bits GRAND that can accurately decode any moderate redundancy block-code. It is designed with efficient circuit implementation in mind, and determines accurate decodings while retaining the original hard detection GRAND algorithm's suitability for a highly parallelized implementation in hardware. ORBGRAND is shown to provide excellent soft decision block error performance for codes of distinct classes (BCH, CA-Polar and RLC) with modest complexity, while providing better block error rate performance than CA-SCL, a state of the art soft detection CA-Polar decoder. ORBGRAND offers the possibility of an accurate, energy efficient soft detection decoder suitable for delivering URLLC in a single hardware realization.
To achieve ultra-high reliability and ultra-low latency required for Beyond 5G or 6G, low error rate decoding method is needed with short code lengths and high code rates. Additionally, a universal decoding method that can be applied to any code which appears in the future be desirable. The maximum likelihood decoding is the best decoding method in information theory, but it is considered difficult to implement due to its huge computational requirements. Recently, Soft GRAND (SGRAND) has been proposed as an effective decoding method for any high-rate, short code length block code in any continuous channel. This method obtains the same decoding result as the maximum likelihood decoding by checking the most likely noise sequantially. However, SGRAND has a problem in which the size of the noise candidate list held internally increases linearly with each noise check. This paper proposes a method to reduce the size of the candidate list in SGRAND, while maintaining the same decoding results as maximum likelihood decoding, by modifying the noise candidate generation algorithm in SGRAND.
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 product codes with lengths of approximately 200 to 4000 bits and rates between 0.2 and 0.8 that outperform low-density parity-check (LDPC) codes from the 5G New Radio standard in both 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. 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.