Weight Distribution of Cosets of Small Codes With Good Dual Properties

The bilateral minimum distance of a binary linear code is the maximum d such that all nonzero codewords have weights between d and n - d. Let Q ⊂ {0,1}ⁿ be a binary linear code whose dual has bilateral minimum distance at least d, where d is odd. Roughly speaking, we show that the average L_∞-distance-and consequently, the L₁-distance-between the weight distribution of a random cosets of Q and the binomial distribution decays quickly as the bilateral minimum distance d of the dual of Q increases. For d = ⊖(1), it decays like n^-⊖(d). On the other d = ⊖(n) extreme, it decays like and e^-⊖(d). It follows that, almost all cosets of Q have weight distributions very close to the to the binomial distribution. In particular, we establish the following bounds. If the dual of Q has bilateral minimum distance at least d = 2t + 1, where t ≥ 1 is an integer, then the average L_∞-distance is at most min{(e ln (n/2t))^t(2t/n)^(t/2), √2e^-(t/10)}. For the average L₁-distance, we conclude the bound min{(2t + 1)(e ln (n/2t))^t(2t/n)^(t/2)-1, √2(n + 1)e^-(t/10)}, which gives nontrivial results for t ≥ 3. We give applications to the weight distribution of cosets of extended Hadamard codes and extended dual BCH codes. Our argument is based on Fourier analysis, linear programming, and polynomial approximation techniques.