Universal GRAND Decoder

Digital data often suffers corruption from noise during transmission or storage. The addition of redundancy by an error correction code seeks to combat the damaging effects of corruption. Codes require reconstruction of the original data through decoding. GRAND™ is a novel approach to decoding that improves on existing methods. Traditional decoders are narrowly tailored to exclusively work with specific codes, resulting in a proliferation of decoding hardware. For reasons of decoding complexity, existing codes are generally excessively redundant, making them wasteful and unsuitable for low energy, low latency or high throughput systems such as IoT, 5G, and optical networks. Exceptionally, GRAND™ can efficiently and precisely decode all moderate to low redundancy codes. GRAND™ obviates the need for multiple decoders. It enables backward compatibility with legacy codes and unfettered innovation in introducing new codes. GRAND™ has been shown in silicon to be energy efficient. GRAND™ is applicable in many different industries including AR/VR, low latency gaming, IoT, 5G networks, optical networks, and many others.

Researchers

Kenneth Duffy / Rabia Yazicigil Kirby / Amit Solomon / Vaibhav Bansal / Wei An / Muriel Medard

Departments: Dept of Electrical Engineering & Computer Science
Technology Areas: Artificial Intelligence (AI) and Machine Learning (ML) / Computer Science: Cybersecurity

  • universal guessing random additive noise decoding (grand) decoder
    United States of America | Granted | 11,870,459

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

License this technology

Interested in this technology? Connect with our experienced licensing team to initiate the process.

Sign up for technology updates

Sign up now to receive the latest updates on cutting-edge technologies and innovations.