ScienceWeek

COMPUTER SCIENCE: ON ERROR-CORRECTION IN MESSAGE TRANSFER

The following points are made by Marc Mézard (Science 2003 301:1685):

1) Complex behaviors can emerge in systems in which many "atoms" -- such as real atoms, economic agents, logical variables, or neurons -- locally exchange messages. Recent independent studies of such systems in different subject areas have shown that message passing is extremely powerful as an algorithmic framework, as well as a conceptual one. Three archetypal problems illustrate this utility: error correction in information theory, satisfiability in discrete optimization, and spin glasses in statistical physics.

2) Error correction is important for the transmission of information. To transmit a signal -- for example, a string of 0's and 1's -- through a noisy channel, one first encodes the signal by adding some redundant bits to it. These bits enable the decoding of the received string even if it has been degraded by errors during transmission.

3) In the 1940s, Claude Shannon (1916-2001) predicted that, for a given degree of redundancy, there exist error-correcting codes that can correct all distortions induced by a channel below a threshold noise level. However, practical codes coming close to Shannon's prediction have only recently been found. The main difficulty was to find fast decoding procedures. A clever message-passing procedure called "belief propagation" (BP) (a name borrowed from computer science studies of inference problems) recently allowed these problems to be overcome.

4) In low-density parity check codes, redundancy is added through a number of parity checks. These checks are constraints such that, for instance, the sum of bits B1, B2, B3, and B5 is even. If the received string does not satisfy this constraint, at least one of these four bits has been corrupted. With several such checks one can identify the bits of the received string that have been corrupted during transmission. The more noisy the channel, the more checks are required.

5) This decoding process can be very slow, because an N-bit message can be garbled in 2N ways. This is where the BP algorithm comes to the rescue. It works by exchanging messages along a graph in which the vertices, or nodes, are bits and parity checks. The edges of the graph connect each check to the bits that it involves.

Science http://www.sciencemag.org

--------------------------------

ON CLAUDE SHANNON (1916-2001)

The following points are made by M. Mitchell Waldrop (Technol. Rev. 2001 August):

1) The entire science of information theory grew out of one electrifying paper that Shannon published in 1948, when he was a 32-year-old researcher at Bell Laboratories. Shannon demonstrated how the once vague notion of information could be defined and quantified with absolute precision. He demonstrated the essential unity of all information media, pointing out that text, telephone signals, radio waves, pictures, film, and every other mode of communication could be encoded in the universal language of binary digits, or "bits" -- a term that first appeared in that Shannon 1948 paper.

2) Shannon proposed the idea that once information becomes digital, it can be transmitted without error. This was a great conceptual leap that led directly to modern information-storage technologies, and Shannon is thus considered to have provided a blueprint for the digital age.

3) After graduating from the University of Michigan in 1936, Shannon went directly to the Massachusetts Institute of Technology to take up a work-study position he had seen advertised on a postcard tacked to a campus bulletin board. The arrangement was that Shannon was to spend half his time pursuing a master's degree in electrical engineering and the other half working as a laboratory assistant to computer pioneer Vannevar Bush. Shannon was soon given responsibility for the Differential Analyzer, at that time the most powerful computing machine in existence. When Shannon died in February 2001, he was completely debilitated with Alzheimer's disease, the symptoms of which first appeared around 1985. He was a professor of physics at the Massachusetts Institute of Technology from 1958 to 1978.

Technology Review http://www.techreview.com

ScienceWeek http://scienceweek.com