Encoding and decoding of BCH codes using light and short codewords

It is shown that every q-ary primitive Bose-Chaudhuri-Hocquenghen code of designed distance δ and sufficiently large length n contains a codeword c₀ of weight w=O(δ) and degree deg( c₀)=o(n). Here, the standard asymptotic notation O(δ) is used for a function f(δ) bounded above by λδ for some constant λ, and o(n) for a function h(n) such that lim_n→∞ h(n)/n=O. These so-called light and short codewords are used to describe encoding and decoding algorithms which run on sequential machines in time O(δn), i.e., linear in n for fixed δ. For high-rate primitive BCH codes this is faster than the commonly used algorithms, which are nonlinear in n when run on sequential machines