Skip to main content

The Enumeration of Information Symbols in BCH Codes

01 October 1967

New Image

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, m ·o -- o Vim q~m"I(q, qm -- 1, uqm) = 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(l) = 0. For q = 2, s{u) is plotted in Fig. 1. Any cyclic code of block length n over GF(q) may be defined by its generator polynomial, g(x), which is some factor of xn -- 1 over GF(q), or by its check polynomial, h(x) = (xn -- 1 )/g{x). The number of check digits in the code is given by the degree of g{x) the number of information digits, by the degree of h{x). We assume that n and q are relatively prime. It is most convenient to work in a particular extension field of GF(q), namely GF(q"), where m is the multiplicative order of q mod n. In this field, a-" -- 1 factors into distinct linear factors: .r" - 1 = n (x - «