Renormalization Group approach to error-correcting codes
| Citation: |
Yedidia, J.S.; Bouchaud, J-P., "Renormalization Group Approach to Error-Correcting Codes", Journal of Physics A: Mathematical and General, Vol. 36, pp. 1267-1288, January 2003 (IoP Electronic Journals) |
| MERL Report: | TR2001-19 |
We explain an algorithm that approximately but efficiently assesses parity-check error-correcting codes of large, but finite, blocklength. This algorithm is based on the "renormalization-group" approach from physics: the idea is to continually replace an error-correcting code with a simpler error-correcting code that has nearly identical performance, until the code is reduced to a small enough size so that its performance can be computed exactly. This assessment algorithm can be used as a subroutine in a more general algorithm to search for optimal or near-optimal error-correcting codes of specified blocklength and rate.
