Information compression and Varshamov-Gilbert bound (Q1099128)

The program complexity to enumerate a finite set of words is found. The complexity is either an exponential or a linear function of the word length depending on whether the redundancy is either less or more than 100 \%. A corollary: the Varshamov-Gilbert bound of the group error correcting code cardinality is tight for almost any channel with additive noise. The proofs are based on the concept of the collision index.