In natural logarithms, Fano's inequality for a uniform index among alternatives states . The mutual information is at most the average Kullback-Leibler divergence to any fixed reference law. With the supplied packing, nearest-neighbour decoding turns partition error below half the separation into correct decoding. Thus the packing alone proves a bound at radius , with the unavoidable term. It does not automatically prove the much larger printed radius.
A list-decoding Fano inequality supplies the intended near-half error threshold. Assume , since otherwise that threshold is nonpositive and its event is automatic. Take a uniform prior on all unlabelled balanced partitions, and let . A Hamming ball of radius less than around any estimated partition contains at most such partitions. This follows by selecting the representative closer to the estimated group; each unlabelled partition contributes at most one such representative because . The entropy bound for a Hamming ball gives , where is the binary entropy function measured in natural logarithms. Its curvature gives . Also , so
Use the all- independent-edge law as a reference. Only the crossing pairs differ; the preceding Bernoulli distribution divergence estimate gives . Hence . Whenever the denominator is positive, the list-decoding Fano inequality proves the finite-sample answer
For , this is at least . If in addition , it implies the intended form with . This proves the claimed information-theoretic scale with its needed finite-sample qualifications.
As a uniform finite-sample assertion for every positive , the printed form is false. At every partition has the same data law, and a uniformly random balanced guess has a positive chance of being correct, giving error strictly below one. Such randomness can also be extracted from the finite graph sample: assign distinct graph outcomes to the finitely many balanced partitions; under the common law every selected outcome has positive probability. The worst error remains strictly below one for sufficiently small positive , by continuity. The printed lower bound tends to one as for any fixed universal , which contradicts this. The entropy correction cannot be dropped without an asymptotic or signal-size condition.
Let and let be the parity-check matrix whose columns are the distinct nonzero vectors of the finite field vector space . The binary Hamming code is
A perfect code has Hamming balls of radius about its codewords partitioning the whole ambient space, where is its minimum Hamming distance of a linear code.
No column of is zero and no two columns agree, so has no word of Hamming weight one or two. Three suitable columns sum to zero, so . For any received word , its syndrome is either zero or is the unique column of equal to that syndrome. In the first case ; in the second,
so is at Hamming distance one from a codeword. Uniqueness follows from . Thus the radius-one balls partition , and the code is perfect.
For , the dual code is the binary simplex code of length seven. Every nonzero dual word evaluates a nonzero linear functional on the seven nonzero vectors of , and exactly four of those evaluations are one. Hence every nonzero word of has weight
Perfect code 2026-10-03
A code of minimum distance is perfect if its Hamming balls of radius partition the ambient word space. Every word then has a unique nearest codeword within the code's error-correction radius.
Random coding 2026-10-31
Random coding constructs a channel code by sampling its codewords from a specified probability distribution and bounding the expected decoding error over that ensemble. If the expected average error is at most , at least one deterministic codebook has average error at most ; otherwise every book would exceed the expectation bound. This is the probabilistic method applied to communication codes.
For independently uniform binary codewords, a fixed competing word falls in any received word's radius- Hamming ball with probability . The union bound over competing messages, together with a bound on excessive channel noise, yields the basic random-coding error estimate. Expurgation of a codebook can then convert average-error control to maximal decoding error probability with negligible loss of asymptotic rate.