Every piece of data that travels over the internet — from paragraphs in an email to
3D graphics in a virtual reality environment — can be altered by the noise it encounters
along the way, such as electromagnetic interference from a microwave or Bluetooth device.
The data are coded so that when they arrive at their destination, a decoding algorithm
can undo the negative effects of that noise and retrieve the original data.
Since the 1950s, most error-correcting codes and decoding algorithms have been designed
together.
Each code had a structure that corresponded with a particular, highly complex decoding
algorithm, which often required the use of dedicated hardware.
Researchers at MIT, Boston University, and Maynooth University in Ireland have now created
the first silicon chip that is able to decode any code, regardless of its structure, with
maximum accuracy, using a universal decoding algorithm called Guessing Random Additive
Noise Decoding (GRAND).
By eliminating the need for multiple, computationally complex decoders, 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 will be presented at the European Solid-States Device Research and Circuits
Conference.
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.
The researcher says that 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 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.
Since GRAND 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.
Regulators ultimately chose to use two types of traditional codes for 5G infrastructure
in different situations.
Using GRAND could eliminate the need for that rigid standardization in the future.
The GRAND chip could even open the field of coding to a wave of innovation.