Statistical mechanics of error-correcting codes

Abstract

PACS. 89.90+n { Other areas of general interest to physicists. PACS. 89.70+c { Information science. PACS. 05.50+q { Lattice theory and statistics; Ising problems. Abstract. { We investigate the performance of error-correcting codes, where the code word comprises products of K bits selected from the original message and decoding is carried out utilizing a connectivity tensor with C connections per index. Shannon’s bound for the channel capacity is recovered for large K and zero temperature when the code rate K=C is nite. Close to optimal error-correcting capability is obtained for nite K and C. We examine the nite-temperature case to assess the use of simulated annealing for decoding and extend the analysis to accommodate other types of noisy channels. Error-correcting codes are of signicant practical importance as they provide mechanisms for retrieving the original message after possible corruption due to noise during transmission. They are being used extensively in most means of information transmission from satellite communication to the storage of information on hardware devices. The coding eciency, measured in the percentage of informative transmitted bits, plays a crucial role in determining