Guessing Random Additive Noise Decoding

 Prof. Muriel Médard, Guessing Random Additive Noise Decoding (GRAND), Rice U ECE, 2020年9月7日

Ken R. Duffy, Jiange Li, Muriel Médard, Capacity-achieving Guessing Random Additive Noise Decoding (GRAND),  arXiv:1802.07010v5.

We introduce a new algorithm for realizing Maximum Likelihood (ML) decoding in discrete channels with or without memory. In it, the receiver rank orders noise sequences from most likely to least likely. Subtracting noise from the received signal in that order, the first instance that results in a member of the code-book is the ML decoding.

MIT, GRAND.

Adam Zewe, A universal system for decoding any type of data sent across a network, MIT News Office, September 9, 2021.

Focus on noise

One way to think of these codes is as redundant hashes (in this case, a series of 1s and 0s) added to the end of the original data. The rules for the creation of that hash are stored in a specific codebook.

As the encoded data travel over a network, they are affected by noise, or energy that disrupts the signal, which is often generated by other electronic devices. When that coded data and the noise that affected them arrive at their destination, the decoding algorithm consults its codebook and uses the structure of the hash to guess what the stored information is.

Instead, GRAND works by guessing the noise that affected the message, and uses the noise pattern to deduce the original information. GRAND generates a series of noise sequences in the order they are likely to occur, subtracts them from the received data, and checks to see if the resulting codeword is in a codebook.

While the noise appears random in nature, it has a probabilistic structure that allows the algorithm to guess what it might be.

“In a way, it is similar to troubleshooting. If someone brings their car into the shop, the mechanic doesn’t start by mapping the entire car to blueprints. Instead, they start by asking, ‘What is the most likely thing to go wrong?’ Maybe it just needs gas. If that doesn’t work, what’s next? Maybe the battery is dead?” Médard says.

Novel hardware

The GRAND chip uses a three-tiered structure, starting with the simplest possible solutions in the first stage and working up to longer and more complex noise patterns in the two subsequent stages. Each stage operates independently, which increases the throughput of the system and saves power.

The device is also designed to switch seamlessly between two codebooks. It contains two static random-access memory chips, one that can crack codewords, while the other loads a new codebook and then switches to decoding without any downtime.

The researchers tested the GRAND chip and found it could effectively decode any moderate redundancy code up to 128 bits in length, with only about a microsecond of latency.