i
i
i
i
i
i
i
i
Chapter 19
Computational Information Theory
19.1 Introduction
Since Shannon published his seminal paper “A Mathematical Theory of Communica-
tion” in 1948 [4], information theory has developed for more than 60 years. In Shan-
non’s time, the communications system was a simple end-to-end telegraph. There
were two fundamental problems to be solved. The first one was entropy-approached
source coding. This problem was solved early on with arithmetic coding. The sec-
ond problem was to study how to complete transmissions approaching the capacity
of a channel, especially an end-to-end channel. When Turbo code was invented in
1993 [18,19] and LDPC code was re-invented in 1996 [17], the problem of capacity-
approached channel codes was also solved.
W