Information compression and Varshamov-Gilbert bound

AbstractThe 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