확장 Hamming 부호에 기반한 Turbo Product Code를 위한 Chase-Pyndiah 복호 알고리즘의 복잡도 감소 기법

Abstract

Turbo product codes (TPC)는 긴 부호의 길이와 높은 부호율에서 뛰어난 에러 정정 능력이 요구되는 애플리케이션에 적합하다. Chase 복호 알고리즘에서는 Chase가 정한 기준에 따라 p개의 최소 신뢰도 위치를 선택하게 되고, 선택된 p개의 위치로부터 2p개의 검사 배열 (test sequences)을 생성하게 된다. 본 논문에서는 Chase-Pyniah 복호 알고리즘의 복잡도를 감소시키기 위한 두 가지 방법을 제안한다. 첫 번째는 선택된 p개의 위치 중에서 상대적으로 에러 확률이 낮은 위치를 배제하여 검사 배열 군의 크기를 감소시키는 방법이다. 그리고 두 번째는 후보 부호어 군을 결정하는 과정에서 사용되는 모든 위치의 인덱스 정보를 기록하고, 이를 이용하여 이어지는 과정에서 연산을 최소화하는 방법이다. 제안하는 두 가지 방법을 통해 검사 배열 군의 크기를 줄이고, Chase-Pyndiah 복호 알고리즘에서 사용되는 연산량을 감소시킨다. 그럼으로써 전체 연산에 소요되는 시간이 절감되는 것을 실험 결과를 통해 확인하였다. 실험에는 (64,57,4)×(64,57,4) 확장 Hamming 부호 기반의 곱 부호가 사용되었다. 첫 번째 알고리즘을 사용하면, 10-6 BER에서 0.1dB의 에러 정정 능력 감소를 보이는 임계치 0.09를 사용했을 때 Eb/N0 5.0dB에서 첫 번째 반복에서의 평균 q는 절반으로 줄어든다. 두 번째 알고리즘을 적용하면 기초복호기의 총 64개 위치 중 46개 이상의 위치에서 연산량 절감이 가능한 것을 실험 결과를 통해 확인하였다. 또한 두 알고리즘을 동시에 적용하면 임계치 0.09를 사용했을 때 Eb/N0 5.0dB에서 56개 이상의 위치에 대해 연산량 절감이 가능한 것을 확인하였다. 이 때, PC를 이용하여 전체 복호 시간을 측정한 결과를 보면 4.0dB에서 복호 시간은 절반 가까이 감소하였다.

Turbo product codes (TPC) are very suitable for applications requiring a large code length, a high code-rate, and good error performance. In the Chase decoding algorithm, a few of least reliable positions that are chosen by the criterion Chase defined are selected and the test sequences are generated from these positions. This paper proposes two methods to lower the complexity of the Chase-Pyndiah decoding algorithm. The first scheme reduces the number of least reliable positions by excluding those having relatively low error probabilities. The other one records the indices of the positions used in the construction of an extended candidate cordword set, and minimizes the computations in the following procedure using the indices. With these methods, we can significantly reduce the number of test sequences and lower the number of utilized computations. In addition, the reduction on the operation time for the whole procedure of a decoder is confirmed. We show the simulation results with a squared (64, 57, 4) extended Hamming code-based TPC.