Toward a theory of avalanche-creating and error-controlling encoding schemes
Grzegorz Greg Malewicz · 2005
This paper introduces a theory of avalanche-creating and error-controlling encoding schemes. We consider a Hamming space {0, 1}nand the problem of finding a bijection g : {0, 1}nrarr {0, 1}n, with inverse h = g-1, that creates avalanche and controls error. That is, for any vectors u and v that are at most b1apart, their images g(u) and g(v) are at least b2apart; and for any vectors v and e, the distance between h(g(v) + e) and v is at most the length of e (the distance from e to 0n) plus b3. It appears that the two objectives of achieving avalanche effect and error control simultaneously in a single encoding scheme are contradictory. This paper is the first attempt at understanding the tradeoffs. Toward this end, the paper determines nontrivial cases when desired encoding schemes can be efficiently constructed, cases when schemes exist but it is not known how to construct them efficiently, and cases when schemes do not exist at all