The Enumeration of Information Symbols in BCH Codes

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,limm → ∞\ q⁻ᵐˢ I(q,qᵐ\ -\ 1, uqᵐ)=1where 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.