Each day, titanic amounts of data flow between billions of connected devices around the world. Very little of it goes astray — thanks in part to the work of Professor Frank Kschischang (ECE).
Next year, Kschischang will be awarded the 2023 Richard W. Hamming Medal from IEEE, the world’s largest professional technical organization. The honour recognizes his contributions to the theory of error-correcting codes (ECCs), which ensure that digital signals can recover lost bits of information when they travel from a transmitter to a receiver.
ECCs play a critical role in modern information technology. For example, they are used in the signals that travel between a satellite and a ground station, or a laptop and Wi-Fi access point, or two smartphones on opposite sides of the city.
“Error-correcting codes are like putting information in a padded envelope,” says Kschischang. “The envelope protects it against the rigours of travel. It might arrive all ripped up, but the inside is protected.”
Such protection is needed because at some point along their journey, all signals travel through a physical medium (such as a fibre-optic channel) and must be detected by a receiver in which the thermal agitation of charge-carriers corrupts them. This is what researchers call noise. Noise can cause bits to randomly flip their value (a zero read as a one, or vice versa), interfering with the exchange.
“We’ve all seen this firsthand when a TV screen pixelates,” says Kschischang.
“Those pixelation artifacts are caused by bits becoming corrupted. The signal’s not so far gone that you’ve lost it entirely, but corrupting even a few bits becomes compounded when the video is decompressed, and it affects bigger data blocks.”
One of the most basic ECCs, called a ‘repetition code,’ duplicates each bit several times and is decoded by a simple majority vote at the receiver. But the added redundancy is very large relative to the length of the message and this method is considered quite inefficient.
The ongoing challenge in the field is to devise coding schemes that reliably recover the output message of a noisy channel using as little redundancy and decoding computation as possible.
“We’ve learned to add redundancy in very clever ways,” says Kschischang. “We had to. We routinely decode codes protecting messages of millions of bits. That’s two to the power of a million possible code words that we need a code book for. To say that number is astronomical, even, is a vast understatement.
“Yet we can pick out from the noise-corrupted received signal exactly which one of these code words was transmitted while processing hundreds of gigabits per second.”
The success of today’s error-control coding approaches is a result of a shift in thinking around 20 years ago. At that time, researchers had been applying optimal, minimum probability of error decoding algorithms, but that approach restricted them to relatively simple codes.
Kschischang was among those who realized that instead of applying optimal algorithms, the designers of ECCs could instead apply approximate ones. It was a revolutionary insight, he says.
“Low-complexity suboptimal algorithms can be designed to handle the great majority of conditions. And they allow us to move from simple codes to much, much more complicated ones. Despite not being decoded optimally, such codes are able to come very close to the theoretical limit, called ‘the Shannon limit’ for the founder of information theory.”
Kschischang’s own factor-graph approach to describing codes and decoding algorithms that was part of this revolution is now a mainstay in textbooks. It’s a model that brings together probability theory and graph theory in a visual way to illustrate the space of possible inference algorithms.
Other career highlights include a subspace coding method for network communications that has spawned its own subdiscipline within the field. His more recent work on ‘staircase’ codes for fibre-optic communications is now embedded within a number of international data communication standards.
The approach is so ubiquitous that a staircase code quite likely delivered this web page, somewhere on its journey from the server, to your device.
Winning the Richard W. Hamming Medal is “a fantastic honour,” says Kschischang.
“Hamming is considered by many to be the father of coding theory. He was such a colourful character, too, in his signature plaid jacket,” he says. “When I was an undergrad, our IEEE student branch showed us Hamming’s video on how to do research, which had a big influence on my decision to continue to graduate studies myself.
“It’s that kind of inspiration that I look to instill in my own students.”
