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 delta and sufficiently large length n contains a codeword c/sub 0/ of weight w=O( delta ) and degree deg(c/sub 0/)=o(n). Here, the standard asymptotic notation O( delta ) is used for a function f( delta ) bounded above by lambda delta for some constant lambda , and o(n) for a function h(n) such that lim/sub n/ to infinity h(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( delta n), i.e., linear in n for fixed delta . For high-rate primitive BCH codes this is faster than the commonly used algorithms, which are nonlinear in n when run on sequential machines.