Abstract:

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.