Bell System Technical Journal · 1967 · 62 citations · 3 references
EngineeringComputer ScienceMathematicsCryptographyInformation TheoryRepresentation TheoryChannel CodingCoding TheoryError-correcting CodesFinite Blocklength Information TheoryBch CodesBose-chaudhuri-hocquenghem CodesHamming DistanceLinear Recurrence RelationsRecurrence
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 = q <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> − 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, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\lim\limits_{m \rightarrow \infty}\ q^{-ms} I(q,q^{m}\ -\ 1, uq^{m})=1$</tex> 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.
3
R. G. Gallager, W. W. Peterson · Mathematics of Computation · 1962 · 2.1K citations
J. H. Abbott, W. W. Peterson · American Mathematical Monthly · 1962 · 228 citations