ABSTRACT
The starting point is the observation that codes constructed by the bipartite graph method possess effective simple decoding algorithms. The best known variant of these algorithms is known nowadays as belief propagation. It is important that the number of edges is small. In the simplest and most effective variant, the inner code is the sum zero code, so each right vertex simply describes a parity check. In order to have a small number of edges, the degree of the vertices is seen as a small constant. Such codes are known as low density parity check codes or short low density parity check codes. The theory of sphere packings in Euclidean space can be seen in analogy to coding theory, in a different context. Both settings of the problem of reliable information transmission are discussed right from the start, in Shannon’s treatise.
