Maximum-likelihood soft decision decoding of BCH codes

Abstract

The problem of efficient maximum-likelihood soft decision decoding of binary BCH codes is considered. It is known that those primitive BCH codes whose designed distance is one less than a power of two, contain subcodes of high dimension which consist of a direct sum of several identical codes. We show that the same kind of direct-sum structure exists in all the primitive BCH codes, as well as in the BCH codes of composite block length. We also introduce a related structure termed the 'concurring-sum', and then establish its existence in the primitive binary BCH codes. Both structures are employed to upper bound the number of states in the proper minimal trellis of BCH codes, and develop efficient algorithms for maximum-likelihood soft decision decoding of these codes.