McEliece and Swanson offerred an upper bound on the decorder error probability of Reed-Solomon codes. In this paper, we investigate the decorder error probability of binary linear block codes and verify its properties, and apply it to binary primitive BCH codes. It is shown that the decorder error probability of an (n,k,t) binary linear block code is determined by PE uniquely if it is a constant. We derive the decorder error probability of (n,k,t) binary primitive BCH codes with n=2m-1 and +1 and show that the decorder error probabilities of those codes are close to PE if codelengh is large and coderate is high. We also compute and analyze the decorder error probabilities of some binary primitive BCH codes.

This letter is concerned with the evaluation of the average computational complexity of the maximum likelihood decoding of a linear block code using its trellis diagram. Each section of the L-section minimal trellis diagram for a linear block code consists of parallel components which are structurally identical subgraphs without cross connection between them. A parallel component is also known to be decomposed into subgraphs, and a decoding algorithm by using the structure of the subgraphs of parallel components was proposed, and an upper bound on the worst case computational complexity was derived. In this letter, the average computational complexity of the decoding algorithm is evaluated by computer simulation. We evaluated the average numbers of additions and comparisons performed in the decoding algorithm for example codes, (64,45) extended and permuted binary primitive BCH code, the third order Reed-Muller (64,42) code and its (64,40) subcode. It is shown that the average numbers are much smaller than those for the worst case, and hence the decoding algorithm is efficient when the number of sections, L, is small, say 4 or 8, for the example codes. Especially, for the (64,45) extended binary primitive BCH code with L4, the average numbers of additions and comparisons in the decoding algorithm for finding the survivor's metric of each state after finding the smallest metric among parallel branches are about 1/50 and 17/100 of those in the conventional exhaustive search, respectively. The number of additions and comparisons by the conventional search for all the example codes is smallest when L is 4. As a result, the decoding algorithm with L4 gives the smallest number of operations among those decoding methods considered here.

A method is presented for computing the number of codewords of weight less than or equal to a given integer in a binary block code by using its trellis diagram. The time and space complexities are analyzed. It is also shown that this method is very efficient for the codes which have relatively simple trellis diagram, say some BCH codes. By using this method, the weight distribution of (128,36) extended BCH code is computed efficiently.

In this paper, we provide an efficient algorithm for GMD (Generalized Minimum Distance) decoding of BCH codes over q-valued logic, when q is pl (p: prime number, l: positive integer). An algebraic errors-and-erasures decoding procedure is required to execute only one time, whereas in a conventional GMD decoding at mostd/2algebraic decodings are necessary, where d is the design distance of the code. In our algorithm, Welch-Berlekamp's iterative method is efficiently employed to reduce the number of algebraic decoding procedures. We also show a method for hardware implementation of this GMD decoding based on q-valued logic.