Asymptotic Analysis of Blind Reconstruction of BCH Codes and A New Method Based on Single-Error Correction

Abstract

This dissertation contains the following two contributions to the research on the blind reconstruction of Bose-Chaudhuri-Hocquenghem (BCH) and Reed-Solomon (RS) codes: Asymptotic Analysis of Blind Reconstruction of BCH Codes Based on Consecutive Roots of Generator Polynomials. A new blind Reconstruction of BCH and RS Codes Using Single-Error Correction.

First, in the military surveillance and security information systems, correct blind reconstruction of signal parameters from unknown signals is very important. Especially, many blind reconstruction methods of error-correcting codes have been proposed, and their theoretical performance analysis is essential for both the defender who wants to prevent information leakage and the challenger who wants to extract information from the intercepted signals. However, a proper performance analysis of most blind reconstruction methods has not been performed yet. Among many blind reconstruction methods of BCH codes proposed so far, the blind reconstruction method in \cite{Daemin paper} based on consecutive roots of generator polynomials proposed by Jo, Kwon, and Shin, called the JKS method, shows the best performance under the unknown channel information. However, the performance of the JKS method is only evaluated through simulation without performing theoretical analysis. In this dissertation, the JKS method is asymptotically analyzed under the binary symmetric channel with the cross-over probability $p$. Since the blind reconstruction performance heavily depends on how many and which received codewords are used even for the same channel environment, sufficiently many codewords are assumed to perform asymptotic analysis. More specifically, an asymptotic threshold on $p$, up to which blind reconstruction is successful, is derived when the number of received codewords is sufficiently large, which can be used as a new performance metric for blind reconstruction methods. Finally, the validity of the asymptotic analysis is confirmed through simulation.

Second, a blind reconstruction method of BCH and RS codes is proposed, which aims to reconstruct the generator polynomials of BCH and RS codes from the intercepted noisy bitstream in non-cooperative environments such as electronic warfare, military surveillance, communication intelligence, and cognitive radio. The previous blind reconstruction methods focus on selecting correct (or noiseless) codewords from the received bitstream without trying any error correction and then reconstructing a generator polynomial by using these presumably correct codewords. Therefore, all the previous methods are highly dependent on the channel conditions because a sufficient number of correct codewords should be available for achieving good reconstruction performance; that, however, becomes more difficult as the channel gets worse. In order to overcome such high dependency on channel conditions, the proposed blind reconstruction method utilizes both the correct codewords and the corrected codewords through the proposed single-error correction method (SCM). Initially, the correct codewords are selected based on the algebraic property of BCH and RS codes that codeword polynomials have consecutive roots. At the same time, the codewords presumably having a single error are selected by using the algebraic property that all the single-error polynomials do not have a non-zero root. Specifically, it is shown that the most of BCH and RS codeword polynomials with a single error do not have consecutive roots. Based on this results, SCM is derived, which selects and corrects the codewords with a single error with high probability. Finally, it is shown that the proposed blind reconstruction method shows much better reconstruction performance with only one-tenth of the received codewords compared to the existing best methods even under harsh channel conditions.