Most error-correcting codes and decoding algorithms have been designed together. Each code had a structure that corresponded with a highly complex decoding algorithm, which often require the use of dedicated hardware.
Researchers at MIT, Boston University, and Maynooth University in Ireland have discovered the first silicon chip that is able to decode any code, regardless of the structure, with maximum accuracy and the help of a universal decoding algorithm called Guessing Random Additive Noise Decoding (GRAND).
GRAND enables increased efficiency that could have applications in augmented and virtual reality, gaming, 5G networks, and connected devices that rely on processing a high volume of data with minimal delay.
The research at MIT is led by Muriel Médard, the Cecil H. and Ida Green Professor, and was co-authored by Amit Solomon and Wei Ann, both graduate students at MIT; Rabia Tugce Yazicigil, assistant professor at Boston University; Arslan Riaz and Vaibhav Bansal, graduate students at Boston University; Ken R. Duffy, director of the Hamilton Institute at the National University of Ireland; and Kevin Galligan, a Maynooth graduate student.
One way to think of these codes is as redundant hashes 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. 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.
GRAND works by guessing the noise that affected the message and using the noise pattern to deduce the original information. It generates a series of noise sequences in the order they are likely to occur. Médard says:
“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?”.
The 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 where each stage operates independently.
The GRAND chip is found that it could effectively decode any moderate redundancy code up to 128 bits in length, with only about a microsecond of latency. Since the chip only uses codebooks for verification, the chip not only works with legacy codes but could also be used with codes that haven’t even been introduced yet.
In the lead-up to 5G implementation, regulators and communications companies struggled to find consensus as to which codes should be used in the new network.
Moving forward, Médard and her collaborators plan to tackle the problem of soft detection with a retooled version of the GRAND chip. In soft detection, the received data are less precise.
They also plan to test the ability of GRAND to crack longer, more complex codes and adjust the structure of the silicon chip to improve its energy efficiency.
The research was funded by the Battelle Memorial Institute and Science Foundation of Ireland.