Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Conference on Information Sciences and Systems

On the determination of GRAND noise sequences by employing integer compositions

Steven Jones, A. Brinton Cooper

Published Mar 22, 2023• 2 citations
Publisher

Abstract

Guessing Random Additive Noise Decoding (GRAND) has been proposed as an efficient and universal decoding technique for linear block codes [1]. A necessary element of the GRAND decoder is a set of noise sequences of length$n$equal to the code length. The decoded codeword is taken as the first valid codeword that results from the binary addition of the noise sequences, in order of likelihood, with the received word. For a binary code of length$\boldsymbol{n}$there are$2^{n}$such noise sequences. When$\boldsymbol{n}$is large, it will typically be intractable to add every noise sequence during decoding. Moreover, these sequences exhibit a number of error bursts$(\boldsymbol{m})$and a total number of bit flips$(\boldsymbol{l})$. In [1] the authors provide expressions to determine the probability of each error burst sequence for a two-state Markov channel model. The resulting decoder is called GRAND-Markov Order (GRAND-MO). The authors of [1] describe a GRAND-MO error pattern generator for the two-state Markov channel based upon sequential transition between$(\boldsymbol{m},\boldsymbol{l})$pairs, incrementing$\boldsymbol{m}$first, and then treating each value of l. In this paper we address a method of constructing the n-length noise sequences based upon integer compositions on the required$l$bit flips as well as the$\boldsymbol{n}-\boldsymbol{l}$non-errors in the sequence. This method allows one to construct noise sequences in order of probability without the need to construct less likely noise sequences. A GRAND decoder may employ a limited number of noise sequences and abandon decoding upon finding a valid code word, or upon reaching an abandonment threshold without decoding success. In this way the most likely noise sequences can be prioritized in decoding.

DOI
10.1109/ciss56502.2023.10089775

Related papers

High-Throughput VLSI Architecture for GRAND Markov Order

Syed Mohsin Abbas, Marwan Jalaleddine, Warren J. Gross

Guessing Random Additive Noise Decoding (GRAND) is a recently proposed Maximum Likelihood (ML) decoding technique. Irrespective of the structure of the error correcting code, GRAND tries to guess the noise that corrupted the codeword in order to decode any linear error-correcting block code. GRAND Markov Order (GRAND-MO) is a variant of GRAND that is useful to decode error correcting code transmitted over communication channels with memory which are vulnerable to burst noise. Usually, interleavers and de-interleavers are used in communication systems to mitigate the effects of channel memory. Interleaving and de-interleaving introduce undesirable latency, which increases with channel memory. To prevent this added latency penalty, GRAND-MO can be directly used on the hard demodulated channel signals. This work reports the first GRAND-MO hardware architecture which achieves an average throughput of up to 52 Gbps and 64 Gbps for a code length of 128 and 79 respectively. Compared to the GRANDAB, hard-input variant of GRAND, the proposed architecture achieves 3 dB gain in decoding performance for a target FER of 10−5. Similarly, comparing the GRAND-MO decoder with a decoder tailored for a (79,64) BCH code showed that the proposed architecture achieves 33% higher worst case throughput and 2 dB gain in decoding performance.

arXiv:2108.12563•SiPS ... design and implementation - IEEE Workshop on Signal Processing Systems•Oct 1, 2021•20 citations

Ordered Reliability Bits Guessing Random Additive Noise Decoding

Ken R. Duffy

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.

arXiv:2001.00546•IEEE International Conference on Acoustics Speech and Signal Processing•May 13, 2021•78 citations

Quantum Error Correction Via Noise Guessing Decoding

Diogo Cruz, Francisco A. Monteiro, Bruno Coelho Coutinho

Quantum error correction codes (QECCs) play a central role in both quantum communications and quantum computation. Practical quantum error correction codes, such as stabilizer codes, are generally structured to suit a specific use, and present rigid code lengths and code rates. This paper shows that it is possible to both construct and decode QECCs that can attain the maximum performance of the finite blocklength regime, for any chosen code length when the code rate is sufficiently high. A recently proposed strategy for decoding classical codes called GRAND (guessing random additive noise decoding) opened doors to efficiently decode classical random linear codes (RLCs) performing near the maximum rate of the finite blocklength regime. By using noise statistics, GRAND is a noise-centric efficient universal decoder for classical codes, provided that a simple code membership test exists. These conditions are particularly suitable for quantum systems, and therefore the paper extends these concepts to quantum random linear codes (QRLCs), which were known to be possible to construct but whose decoding was not yet feasible. By combining QRLCs and a newly proposed quantum-GRAND, this work shows it is possible to decode QECCs that are easy to adapt to changing conditions. The paper starts by assessing the minimum number of gates in the coding circuit needed to reach the QRLCs’ asymptotic performance, and subsequently proposes a quantum-GRAND algorithm that makes use of quantum noise statistics, not only to build an adaptive code membership test, but also to efficiently implement syndrome decoding.

arXiv:2208.02744•IEEE Access•Jan 1, 2023•21 citations

Codes

Edward F. Assmus, Jennifer D. Key

Introduction Error-correcting codes were introduced in the 1940s in order to implement a theorem of Shannon's [260] which guaranteed that virtually error-free communication could be obtained even over a noisy channel. The message to be communicated is first “encoded”, i.e. turned into a codeword, by adding "redundancy". The codeword is then sent through the channel and the received message is “decoded” by the receiver into a message resembling, as closely as possible, the original message. The degree of resemblance will depend on how good the code is in relation to the channel. The usual pictorial representation of this communication link is shown in the schematic diagram Figure 2.1. Here a message is first given by the source to the encoder that turns the message into a codeword, i.e. a string of letters from some alphabet, chosen according to the code used; the encoded message is then sent through the channel, where it may be subjected to noise and hence altered; this possibly-altered message, when it arrives at the decoder belonging to the receiver, is, first of all, equated with the most likely codeword, i.e. the one (should that exist) that, in a probabilistic sense depending on the channel, was probably sent; finally this “most likely” codeword is decoded and the message is passed on to the receiver. Example 2.1.1 Suppose we use an alphabet of just two symbols, 0 and 1, and we have only two messages, for example “no” corresponding to 0, and "yes” corresponding to 1. We wish to send the message “no”, and we add redundancy by simply repeating the message five times. Thus we encode the message as the codeword (00000). The channel interferes, perhaps, with the message and could, for example, change it to (01100). The decoder assesses the message and decides that of the two possible codewords, i.e. (00000) and (11111), the former is the more likely, and hence the message is decoded, correctly, as “no”. Notice that we have made several assumptions here: for example we have assumed that the probability of an error at any position in the word is less than, that each codeword is equally likely to be sent, and that the receiver is aware of the code used.

Cambridge University Press eBooks•Aug 28, 1992•0 citations

Performance of Multistage Universal Decoder for Given Linear Codes over Additive Noise Channels

友彦 植松, Tomohiko UYEMATSU

•Jan 1, 2004•0 citations

Guessing Random Additive Noise Decoding

Syed Mohsin Abbas, Marwan Jalaleddine, Warren J. Gross

Springer eBooks•Jan 1, 2023•3 citations
Guessing Random Additive Noise Decoding (GRAND) has been proposed as an efficient and universal decoding technique for linear block codes [1]. A necessary element of the GRAND decoder is a set of noise sequences of lengthnnnequal to the code length. The decoded codeword is taken as the first valid codeword that results from the binary addition of the noise sequences, in order of likelihood, with the received word. For a binary code of lengthn\boldsymbol{n}nthere are2n2^{n}2nsuch noise sequences. Whenn\boldsymbol{n}nis large, it will typically be intractable to add every noise sequence during decoding. Moreover, these sequences exhibit a number of error bursts(m)(\boldsymbol{m})(m)and a total number of bit flips(l)(\boldsymbol{l})(l). In [1] the authors provide expressions to determine the probability of each error burst sequence for a two-state Markov channel model. The resulting decoder is called GRAND-Markov Order (GRAND-MO). The authors of [1] describe a GRAND-MO error pattern generator for the two-state Markov channel based upon sequential transition between(m,l)(\boldsymbol{m},\boldsymbol{l})(m,l)pairs, incrementingm\boldsymbol{m}mfirst, and then treating each value of l. In this paper we address a method of constructing the n-length noise sequences based upon integer compositions on the requiredlllbit flips as well as then−l\boldsymbol{n}-\boldsymbol{l}n−lnon-errors in the sequence. This method allows one to construct noise sequences in order of probability without the need to construct less likely noise sequences. A GRAND decoder may employ a limited number of noise sequences and abandon decoding upon finding a valid code word, or upon reaching an abandonment threshold without decoding success. In this way the most likely noise sequences can be prioritized in decoding.
Guessing Random Additive Noise Decoding (GRAND) is a recently proposed Maximum Likelihood (ML) decoding technique. Irrespective of the structure of the error correcting code, GRAND tries to guess the noise that corrupted the codeword in order to decode any linear error-correcting block code. GRAND Markov Order (GRAND-MO) is a variant of GRAND that is useful to decode error correcting code transmitted over communication channels with memory which are vulnerable to burst noise. Usually, interleavers and de-interleavers are used in communication systems to mitigate the effects of channel memory. Interleaving and de-interleaving introduce undesirable latency, which increases with channel memory. To prevent this added latency penalty, GRAND-MO can be directly used on the hard demodulated channel signals. This work reports the first GRAND-MO hardware architecture which achieves an average throughput of up to 52 Gbps and 64 Gbps for a code length of 128 and 79 respectively. Compared to the GRANDAB, hard-input variant of GRAND, the proposed architecture achieves 3 dB gain in decoding performance for a target FER of 10−5. Similarly, comparing the GRAND-MO decoder with a decoder tailored for a (79,64) BCH code showed that the proposed architecture achieves 33% higher worst case throughput and 2 dB gain in decoding performance.
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.
Quantum error correction codes (QECCs) play a central role in both quantum communications and quantum computation. Practical quantum error correction codes, such as stabilizer codes, are generally structured to suit a specific use, and present rigid code lengths and code rates. This paper shows that it is possible to both construct and decode QECCs that can attain the maximum performance of the finite blocklength regime, for any chosen code length when the code rate is sufficiently high. A recently proposed strategy for decoding classical codes called GRAND (guessing random additive noise decoding) opened doors to efficiently decode classical random linear codes (RLCs) performing near the maximum rate of the finite blocklength regime. By using noise statistics, GRAND is a noise-centric efficient universal decoder for classical codes, provided that a simple code membership test exists. These conditions are particularly suitable for quantum systems, and therefore the paper extends these concepts to quantum random linear codes (QRLCs), which were known to be possible to construct but whose decoding was not yet feasible. By combining QRLCs and a newly proposed quantum-GRAND, this work shows it is possible to decode QECCs that are easy to adapt to changing conditions. The paper starts by assessing the minimum number of gates in the coding circuit needed to reach the QRLCs’ asymptotic performance, and subsequently proposes a quantum-GRAND algorithm that makes use of quantum noise statistics, not only to build an adaptive code membership test, but also to efficiently implement syndrome decoding.
Introduction Error-correcting codes were introduced in the 1940s in order to implement a theorem of Shannon's [260] which guaranteed that virtually error-free communication could be obtained even over a noisy channel. The message to be communicated is first “encoded”, i.e. turned into a codeword, by adding "redundancy". The codeword is then sent through the channel and the received message is “decoded” by the receiver into a message resembling, as closely as possible, the original message. The degree of resemblance will depend on how good the code is in relation to the channel. The usual pictorial representation of this communication link is shown in the schematic diagram Figure 2.1. Here a message is first given by the source to the encoder that turns the message into a codeword, i.e. a string of letters from some alphabet, chosen according to the code used; the encoded message is then sent through the channel, where it may be subjected to noise and hence altered; this possibly-altered message, when it arrives at the decoder belonging to the receiver, is, first of all, equated with the most likely codeword, i.e. the one (should that exist) that, in a probabilistic sense depending on the channel, was probably sent; finally this “most likely” codeword is decoded and the message is passed on to the receiver. Example 2.1.1 Suppose we use an alphabet of just two symbols, 0 and 1, and we have only two messages, for example “no” corresponding to 0, and "yes” corresponding to 1. We wish to send the message “no”, and we add redundancy by simply repeating the message five times. Thus we encode the message as the codeword (00000). The channel interferes, perhaps, with the message and could, for example, change it to (01100). The decoder assesses the message and decides that of the two possible codewords, i.e. (00000) and (11111), the former is the more likely, and hence the message is decoded, correctly, as “no”. Notice that we have made several assumptions here: for example we have assumed that the probability of an error at any position in the word is less than, that each codeword is equally likely to be sent, and that the receiver is aware of the code used.