The Enumeration of Information Symbols in BCH Codes
Elwyn R. Berlekamp · Bell System Technical Journal · 1967
This paper presents certain formulas for I(q, n, d), the number of information symbols in the q-ary Bose-Chaudhuri-Hocquenghem code of block length n = qm− 1 and designed distance d. By appropriate manipulations on the m-digit q-ary representation of d, we derive a simple linear recurrence for a sequence whose mth term is the number of information symbols in the BCH code. In addition to an exact solution of all finite cases, we obtain exact asymptotic results, as n and d go to infinity while their ratio n/d remains fixed. In this limit, the number of information symbols increases as n'. Specifically, we show that for fixed u, 0 ≦ u ≦ 1,$\lim\limits_{m \rightarrow \infty}\ q^{-ms} I(q,q^{m}\ -\ 1, uq^{m})=1$where s is a singular function of u. The function s(u) is continuous and monotonic nonincreasing; it has derivative zero almost everywhere. Yet s(0) = 1 and s(1) = 0. For q = 2, s(u) is plotted in Fig. 1.