J ul 1 99 9 Cascading Parity-Check Error-Correcting Codes
A method for improving the performance of sparse-matrix based parity check codes is proposed, based on insight gained from methods of statistical physics. The advantages of the new approach are demonstrated on an existing encoding/decoding paradigm suggested by Sourlas. We also discuss the application of the same method to more advanced codes of a similar type. Error-correcting codes are commonly used in most means of information transmission. The coding efficiency, measured in the percentage of informative transmitted bits, plays a crucial role in determining the speed of communication channels and the effective storage space on hard-disks. The question of channel capacity of noisy communication channels was addressed by Shannon [1] in his pioneering work from 1948. Rigorous bounds have been derived for the maximal transmission rate for which codes, capable of achieving arbitrarily small error probability, can be found. In a typical scenario, a message comprising N binary bits is transmitted through a noisy communication channel; the received string differs from the transmitted one due to noise (for instance, background radiation, defects in magnetic materials, thermal noise etc) the result of which is the flipping of some bits. Here, we denote the flipping rate of a bit in a binary symmetric channel (i.e., from 0 to 1 or from 1 to 0) by f ∈ [0 : 1]; other types of noise may also be considered, which may be more realistic in some scenarios. Error-correcting codes have been devised for retrieving the original message at the receiving end. The receiver can correct the flipped bits (or some fraction of them) in a retrieved message of length N only if the source transmits M(f) >N bits; the ratio between the original number of bits and those of the transmitted message R ≡ N/M is termed the code-rate. Shannon [1] obtained the optimal trade-off between the following three quantities in the thermodynamic limit: the maximal code rate Rc (termed channel capacity), the flip rate f (due to noise) and the coded bit error probability pb, given explicitly by