Decoding by Guessing Noise II

Technology

The GRAND™ method decodes data based on identifying the noise effect, rather than attempting to extract codewords directly from the noise impacted encoded data as existing methods do. The GRAND™ approach contains three main processes that are repeated until a decoding is obtained. Noise effect sequences are sequentially generated in decreasing order of likelihood either a priori based on a statistical channel model or using soft information, such as can be obtained in reception of communication signals. In order, GRAND™ takes a noise effect sequence, inverts its effect from a possibly noise-corrupted signal (e.g., by subtracting or using some other method of operational inversion), and queries whether the resulting data are a valid codeword, using the code merely as a validator or hash. The first instance of code-word identification is the decoding. By mirroring the noisy channel, GRAND™ provides optimally accurate maximum likelihood decoding of arbitrary codes with moderate redundancy that can be chosen to perfectly match system characteristics.

Problem Addressed

Digital data is subjected to errors when stored or transmitted owing to the effects of noise on the medium or communication channel. The solution is to add redundancy to the data on storage or transmission via an error correction code so that, at the time of retrieval of the data, decoding can undo the noise effect and correctly recover the original data.

Traditional decoding methods require highly specialized, restricted codebooks and corresponding code-specific decoders. These codebooks are compilations of codewords that are used to encode the data amidst the noise. The system designer must give careful consideration in choosing codebook/decoder pairs. A poor choice will result in wasted bandwidth, time, energy or memory, or catastrophic decoding failures resulting in loss of data. Furthermore, these decoding methods generally require entirely bespoke architectures that have a high level of computational complexity. By being able to error-correct any code, even ubiquitously deployed error detection codes, grand removes the inefficiencies of code restriction and standardization.

Advantages

• Decodes any moderate redundancy code, regardless of structure and length, with provably maximal accuracy
• Variants have been established for both soft and hard detection systems
• Is inherently highly parallelizable, resulting in desirably low latency
• Can be used in channels experiencing noise bursts without the need for interleaving
• A hard detection implementation in silicon has proven energy efficient universality