Statistical mechanics of error-correcting codes

¹ Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology - Yokohama 226, Japan
² The Neural Computing Research Group, Aston University, Birmingham B4 7ET, UK

Received: 8 June 1998
Accepted: 9 October 1998

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 finite. Close to optimal error-correcting capability is obtained for finite K and C. We examine the finite-temperature case to assess the use of simulated annealing for decoding and extend the analysis to accommodate other types of noisy channels.