17 Nov
2012
17 Nov
'12
5:15 p.m.
Another construction is this. Start with a binary error-correcting code X, each codeword n bits long, with min-distance = d. Now discard all codewords whose weight (number of one-bits) w disobeys wmin <= w <= wmax. The result will be a perfect-union-code, provided that 2*wmax < d + wmin. The cardinality of the perfect-union-code can in this way always be assured by suitable initial bitflipping to be at least as large as cardinality(X) * 2^(-n) * sum(k=a...b)of binomial(n,k). This fact in combination with Stirling formula and known Gilbert-Varshamov existence results for binary codes, will also prove a (different and probably stronger) EXPONENTIAL GROWTH THEOREM.