Statistical Blind Classification and Reconstruction of Error-Correcting Codes in a Non-Cooperative Context

Abstract

This dissertation contains the following three contributions to the research topics on blind detection of error-correcting codes (ECCs): • Blind classification scheme of ECCs, which classifies whether the received bit-stream is encoded by an ECC or not, and if it is determined that the received bit-stream is encoded, the proposed scheme further classifies whether the used ECC is a block code or a non-block code. • Blind reconstruction scheme of BCH codes, which uses the property that all the codeword polynomial of a t-error correcting BCH code have the same 2t consecutive roots over Galois field. • The theoretical lower-bound on the success probability of blind reconstruction of BCH codes. ECCs are essential to improve the reliability of digital communication systems. ECCs can detect or correct the errors by introducing and utilizing the systematic parity check bits, which however deteriorate the spectral efficiency of digital communication systems. In order to enhance the spectral efficiency, the used ECC may be blindly detected at the receiver. Also, blind detection of ECCs is important in the broadcasting systems, electronic warfare but it is a hard problem. Recently, blind detection schemes of ECCs have been actively studied and most of them assume that the receiver knows which type of ECC, a block code or a non-block code, is used. However, in real situations, blind classification about whether the ECC is a block code or a non-block code should be performed first. First, in this dissertation, a blind classification scheme of ECCs in a noisy environment is proposed, which classifies whether the received bitstream is encoded by an ECC or not, and if it is determined that the received bit-stream is encoded, the proposed scheme further classifies whether the used ECC is a block code or a non-block code. Also, a novel rank calculation scheme of the intercepted matrix is proposed by performing a probabilistic analysis of random row permutation for the intercepted matrix. Based on this analysis, the minimum number of random row permutations is theoretically derived for guaranteeing correct rank calculation with probability at least β. Next, a blind reconstruction method of BCH codes is proposed, which uses the property that all the codeword polynomials of a t-error correcting BCH code have the same 2t consecutive roots over Galois field. The proposed method inherently eliminates most of the erroneous codewords from the received codewords by utilizing the information about the starting position and length of consecutive roots of each received codeword. Finally, the theoretical lower-bound on the success probability of blind reconstruction of BCH codes is derived. In order to derive a performance lower-bound, the theoretical analysis of BCH codes on the aspects of blind reconstruction is performed. Furthermore, the analysis results can be applied not only to the binary BCH codes but also to the non-binary BCH codes including Reed–Solomon (RS) codes. By comparing the derived lower-bound with the simulation results, it is confirmed that the success probability of the blind reconstruction of BCH codes based on the consecutive roots of generator polynomials is well bounded by the proposed lower-bound.|본 논문에서는 오류정정부호(Error-correcting codes)의 암맹 판별(Blind detection)에 대한 연구에 관하여 다음의 세 가지 기여를 포함한다. • 미지의 비트스트림에 오류정정부호가 사용되었는지에 대한 암맹 판별 및 오류정정부호가 사용되었다면 사용된 오류정정부호의 종류를 블록 부호(Block codes) 또는 논블록 부호(Non-block codes)로 암맹 구별(Blind classification)하는 기법 • 미지의 비트스트림이 BCH (Bose–Chaudhuri–Hocquenghem) 부호로 부호화(Encoding)된 경우 사용된 BCH 부호의 생성다항식(Generator polynomial)을 암맹 재구성(Blind reconstruction)하는 기법 • BCH 부호의 생성다항식에 대한 암맹 재구성 기법의 이론적 분석을 통한 암맹 재구성 성공 확률의 하한(Lower-bound) 유도 오류정정부호는 디지털 통신 시스템의 신뢰도(Reliability)를 높이기 위해서 필수적으로 사용된다. 오류정정부호는 채널에 의해 발생하는 오류를 검출(Detection) 및 정정(Correction)하기 위해서 패리티 비트(Parity bits)를 사용하지만, 이는 디지털 통신 시스템의 스펙트럼 효율(Spectral efficiency) 감소시킨다. 스펙트럼 효율을 향상시키기 위해서는, 사용된 오류정정부호의 암맹 판별이 필요하다. 또한, 오류정정부호의 암맹 판별은 브로드캐스팅 시스템(Broadcasting system), 전자전(Electronic warfare) 등에서 매우 중요하다. 최근, 오류정정부호의 암맹 판별에 대한 연구가 활발히 진행되고 있지만 대부분의 연구는 사용된 오류정정부호의 종류를 알고 있다는 가정에서 연구가진행되고 있다. 하지만 실제 환경에서는 수신된 미지의 비트스트림에 오류정정부호가 사용되었는지, 사용되었다면 블록 부호와 논블록 부호 중 어떠한부호가 사용되었는지 암맹 구별해야 한다. 본 논문에서는 먼저 미지의 비트스트림에 오류정정부호가 사용되었는지, 만약 오류정정부호가 사용되었다면 블록 부호와 논블록 부호 중 어떠한 종류의 부호가 사용되었는지 암맹 구별할 수 있는 오류정정부호의 암맹 구별기법을 제안한다. 또한, 인터셉트 행렬(Intercepted matrix)의 랜덤 행 교환(Random row permutation)에 대한 확률적 분석을 통하여 인터셉트 행렬의 랭크(Rank)을 계산하는 기법을 소개한다. 이러한 분석을 통하여 인터셉트 행렬의 랭크를 정확히 계산할 확률이 β 이상이 되는 최소 랜덤 행 교환 횟수를 유도한다. 다음으로, 미지의 비트스트림이 BCH 부호로 부호화된 경우 사용된 생성다항식을 재구성할 수 있는 기법을 t개의 오류를 고칠 수 있는 BCH 부호의 생성다항식은 유한체(Galois field)상에서 2t개의 연속근을 가진다는 성질을 이용하여 제안한다. 수신된 미지의 비트스트림 각각의 연속근의 시작점과 길이를 이용하여 대부분의 오류가 있는 부호어를 제외할 수 있고 이를 통하여 BCH 부호의 생성다항식에 대한 암맹 재구성 확률을 향상시켰다. 마지막으로, 제안된 BCH 부호의 생성다항식의 암맹 재구성 기법에 대한 이론적 분석을 진행하고 이를 기반으로 BCH 부호의 생성다항식의 암맹 재구성 성공 확률에 대한 하한을 유도한다. 성능의 하한을 구하기 위하여, BCH 부호를 암맹 판별 측면으로 분석한다. 분석된 결과는 이진(Binary) BCH 부호뿐만 아니라 RS (Reed-Solomon) 부호와 같은 일반적인 BCH 부호에도 적용할 수 있다. 이론적으로 구한 하한을 시뮬레이션 결과와 비교하여 BCH 부호의 생성다항식의 암맹 재구성 성공 확률이 잘 바운드되었음을 확인한다.