A Fast Method for Estimating Generator Matrixes of BCH Codes

The existing methods used for estimating generator matrixes of BCH codes, which are based on Galois Field Fourier transforms, need to exhaustively test all the possible codeword lengths and corresponding primitive polynomials. With the increase of codeword length, the search space exponentially expands. Consequently, the computational complexity of the estimation scheme becomes very high. To overcome this limitation, a fast estimation method is proposed based on Gaussian elimination. Firstly, the encoded bit stream is reshaped into a matrix according to the assumed codeword length. Then, by using Gaussian elimination, the bit matrix is simplified as the upper triangle form. By testing the independent columns of the upper triangle matrix, the assumed codeword length is judged to be right or not. Simultaneously, by using an augmented matrix, the parity check matrix of a BCH code can be estimated from the simplification result in the procedure of Gaussian elimination. Furthermore, the generator matrix is estimated by using the orthogonality between the generator matrix and parity check matrix. To improve the performance of the proposed method in resisting bit errors, soft-decision data is adopted to evaluate the reliability of received bits, and reliable bits are selected to construct the matrix to be analyzed. Experimental results indicate that the proposed method can recognize BCH codes effectively. The robustness of our method is acceptable for application, and the computation required is much less than the existing methods.