Through the Application of a Revolutionary Algorithm, a New Silicon Device can Decode any Error-Correcting Code

Noise, such as electromagnetic interference from a microwave or Bluetooth device, may affect every bit of data that goes over the internet, from words in an email to 3D images in a virtual reality environment. The data is encoded such that when it reaches its destination, a decoding program can reverse the effects of the noise and recover the original data.

Most error-correcting codes and decoding algorithms have been built simultaneously since the 1950s. Each code had a structure that matched to a specific, extremely complicated decoding method, which frequently necessitated the employment of specialized hardware.

Researchers from MIT, Boston University, and Maynooth University in Ireland have developed the first silicon device that can decode any code with maximum accuracy, independent of its structure, using a universal decoding technique dubbed Guessing Random Additive Noise Decoding (GRAND).

GRAND offers enhanced efficiency by reducing the need for several, computationally intensive decoders, which might have applications in augmented and virtual reality, gaming, 5G networks, and connected devices that need processing a large amount of data with little latency.

The research at MIT is led by Muriel Médard, the Cecil H. and Ida Green Professor in the Department of Electrical Engineering and Computer Science, and was co-authored by Amit Solomon and Wei Ann, both graduate students at MIT; Rabia Tugce Yazicigil, assistant professor of electrical and computer engineering at Boston University; Arslan Riaz and Vaibhav Bansal, both graduate students at Boston University; Ken R. Duffy, director of the Hamilton Institute at the National University of Ireland at Maynooth; and Kevin Galligan, a Maynooth graduate student. Next week, the findings will be presented at the European Solid-State Device Research and Circuits Conference.

Focus on noise

These codes can be thought of as redundant hashes (a series of 1s and 0s) appended to the end of the original data. A specific codebook contains the rules for generating that hash.

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?

Muriel Médard

Noise, or energy that interrupts the signal, is typically created by other electronic equipment, and it affects the encoded data as it travels through a network. When the coded data and the noise that influenced it to reach at their destination, the decoding algorithm consults its codebook and guesses what the stored information is based on the structure of the hash.

GRAND, on the other hand, works by predicting the noise that influenced the message and then deducing the original information from the noise pattern. GRAND creates a series of noise sequences in the order in which they are most likely to occur, subtracts them from the incoming data, and verifies whether the generated codeword is in a codebook.

Despite the fact that the noise appears to be random, it has a probabilistic structure that allows the algorithm to estimate what it is.

“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 has a three-tiered structure, with the first stage starting with the simplest conceivable solutions and progressing to longer and more complicated noise patterns in the second and third levels. Each step is self-contained, increasing system throughput while conserving energy.

The gadget can also effortlessly transition between two different codebooks. It has two static random-access memory chips, one of which can break codewords while the other loads a new codebook and immediately switches to decoding.

The GRAND chip was tested and determined to be capable of decoding any moderate redundancy code up to 128 bits in length with only a microsecond of delay.

Médard and her team have previously proved the algorithm’s success, but this new study is the first to establish GRAND’s efficacy and efficiency in hardware.

According to Médard, developing hardware for the innovative decoding method required the researchers to discard their previous beliefs first.

“We couldn’t go out and reuse things that had already been done. This was like a complete whiteboard. We had to really think about every single component from scratch. It was a journey of reconsideration. And I think when we do our next chip, there will be things with this first chip that we’ll realize we did out of habit or assumption that we can do better,” she says.

A chip for the future

Because GRAND only utilizes codebooks for verification, it may be used not just with historical codes but also with codes that haven’t been released yet.

Regulators and communications businesses failed to agree on which codes should be used in the new network in the run-up to 5G deployment. In the end, regulators decided to employ two distinct types of conventional codes for 5G infrastructure in various scenarios.

According to Médard, using GRAND might obviate the necessity for rigorous uniformity in the future. The GRAND chip may potentially usher in a new era of coding creativity.

“For reasons I’m not quite sure of, people approach coding with awe, like it is black magic. The process is mathematically nasty, so people just use codes that already exist. I’m hoping this will recast the discussion so it is not so standards-oriented, enabling people to use codes that already exist and create new codes,” she says.

Médard and her team want to use a retooled version of the GRAND chip to tackle the challenge of soft detection in the future. The obtained data are less exact in soft detection.

They also intend to evaluate GRAND’s potential to crack longer, more complicated codes and tweak the silicon chip’s structure to increase its energy efficiency. The Battelle Memorial Institute and the Science Foundation of Ireland financed the study.