Explained: Gallager codes
This is the second part of a two-part Explained about information theory. The first part, on the Shannon limit, appeared on Tuesday.In the 1948 paper that created the field of information theory, MIT grad (and future professor) Claude Shannon threw down the gauntlet to future generations of researchers. In those predigital days, communications channels — such as phone lines or radio bands — were particularly susceptible to the electrical or electromagnetic disruptions known as “noise.” Shannon proved the counterintuitive result that no matter how noisy a channel, information could be sent over it error free. All you needed was a way to add enough redundancy to the information so that errors could be corrected. He also demonstrated that there was a hard limit on how efficient those error-correcting codes could be — a minimum amount of extra information that would guarantee near-zero error. Since longer codes take longer to send,...