Chien Search algorithm is a one of the BCH code decoding algorithm and it is used to find the error-location in the received signal from the error-location polynomial. Chien Search algorithm has been implemented in hardware, but its structure is iterative and has a lot of power consumption when the code length is getting longer or the architecture selects much more parallel structure.
In this thesis, to improve the power consumption of conventional Chien Search architecture and keep the high throughput, new Chien Search architecture - power-efficient 2-step Chien Search is proposed and implemented. Let the Chien Search structure check the low-part of the output. If the low-bit of output is same as 1, there is possibility of finding the error. If not, there exists absolutely no error. By separating the Chien Search algorithm to 2-step, early detection of ‘not the error’ is available and if ‘not the error’ is determined, $2^{nd}$ step is bypassed and power saving is achieved.
Furthermore, to save the power consumption more, the $2^{nd}$ stage is converted to the conventional iterative structure. The iterative structure has less gates than parallel one, so the power saving can be achieved. Even the throughput can be little bit lost, the number of access to $2^{nd}$ stage also can be reduced by increasing the check-bit of $1^{st}$ stage. So throughput loss would be smaller.
The implementation results is that with 0.13-μm CMOS technology working frequency is 200 MHz and power consumption improvement is maximally 35 % better than conventional parallel Chien Search architecture for full-parallel architecture, 50% better for serial-parallel hybrid architecture.
치엔 서치 (Chien Search) 알고리즘은 BCH 코드의 디코딩 알고리즘의 일부이다. BCH 코드의 디코딩 알고리즘 중에서는 통신 채널에서 전달 받은 신호의 에러 비트를 찾기 위해 에러 위치 다항식 (Error-location Polynomial)을 구하는데 치엔 서치는 그 다항식의 해를 구하는 알고리즘이다. 치엔 서치 알고리즘은 반복적 방법을 이용한 하드웨어를 사용했기 때문에 코드의 길이가 길어지게 되면 치엔 서치에 걸리는 시간이 길어지는 문제점이 있었다. 이에 하드웨어의 스루풋 (Throughput)을 향상시키기 위해 하드웨어를 병렬로 추가로 구성하는 방법이 고려되었다.
본 논문에서는 하드웨어를 병렬로 구성하였을 때 발생하는 많은 전력 소모를 줄이면서 높은 스루풋을 유지하는 새로운 치엔 서치 아키텍처를 제안하고 구현하였다. 이 구조는 치엔 서치 알고리즘을 두 파트로 나눈다. 첫 번째 파트에서는 치엔 서치 알고리즘의 아웃풋의 낮은 비트를 먼저 계산하여 그 값이 1이라면 두 번째 파트에서 아웃풋의 높은 비트를 마저 계산하여 에러의 존재 여부를 결정한다. 만일 첫 번째 파트의 결과가 1이 아니라면 에러는 반드시 존재하지 않기 때문에 두 번째 파트의 연산을 거치지 않는다. 이와 같은 바이패스(Bypass) 구조를 통해 전력 소모를 줄일 수 있다. 이 두 파트는 파이프 라인 구조로 구현되어 동작 속도를 높였다.
이와 더불어 첫 번째 파트에서 연산하는 비트 수를 늘리면 두 번째 파트에 접근하는 횟수를 줄일 수 있는 점에서 착안하여 두 번째 파트의 병렬 구조를 반복적 구조로 변경하여 스루풋의 손해를 최소화 하면서 전체 하드웨어 크기를 줄일 수 있는 구조를 추가로 제안하였다. 이를 통해 전력 소모를 다시 한 번 줄일 수 있었다.
이 하드웨어는 0.13-μm CMOS 공정을 사용하여 200 MHz의 동작 속도를 갖도록 구현되었고, 병렬로 구성된 2단계 치엔 서치 구조는 최대 35 %의 전력 감소를 가져왔고 병렬-순차가 복합적으로 구성된 2단계 치엔 서치 구조는 최대 50 %의 전력 감소를 이루었다.
