The low-density parity-check(LDPC) code has been adopted in many communication standards due to its error correcting performance, and the quasi-cyclic LDPC(QC-LDPC) is widely used because of implementation easiness. In the QC-LDPC decoder, a cyclic-shifter is required to rotate data in various sizes. This kind of cyclic-shifters are called multi-size circular shifter(MSCS), and this paper proposes a low-complexity structure for MSCS. In the conventional serially-placed two barrel-rotators, the unnecessary multiplexers are revealed and removed, leading to low-complexity. The experimental results show that the area is reduced by about 12%.
Low-density parity-check (LDPC) 코드는 우수한 에러 정정 능력과 병렬화가 가능한 복호 알고리즘으로 인해 최근 많은 통신 표준에 채택되고 있는 에러 정정코드이다. LDPC 코드에는 여러 하위 부류가 있으며 그 중에서 많이 사용되는 것이 quasi-cyclic LDPC(QC-LDPC) 코드이다[1].
QC-LDPC 코드는 parity-check 행렬이 여러 개의 작은 부행렬로 이루어져 있으며, 각각의 부행렬은 identity 행렬의 cyclic shift이다. 이러한 QC-LDPC 코드의 복호기 설계에 있어서 부행렬에 따라 데이터를 rotation시키는 cyclic-shifter가 필수적이다. 일반적인 cyclic-shifter는 rotation 크기가 정해져 있어서 barrel-rotator와 같은 구조로 만들 수 있으나, QC-LDPC 복호기에서 요구되는 cyclic-shifter는 rotation 크기를 바꿀 수 있어야 하므로 일반적인 barrel-rotator 구조로는 만들기 어려운 면이 있다. 이러한 cyclic-shifter는 multi-size cyclic shifter(MSCS)라 불리며 이에 대해 많은 연구가 이루어져 왔다[2]. 대표적인 구조로는 두 개의 barrel-rotator를 이용하는 구조가 있으며, 두 barrel-rotator를 논문 [3]과 같이 병렬로 배치하거나 논문 [4]와 같이 직렬로 배치하여 이용한다. 다른 구조로는 Benes 네트워크를 이용하는 방법이 있다[5]. Benes 네트워크는 N개의 입력을 permutation하여 출력하는 회로이므로 다양한 크기의 cyclic-shift를 실행할 수 있다.
이러한 기존 구조들 중에 두 개의 barrel-rotator를 직렬로 배치하는 방법은 병렬로 배치하는 방법에 비해 rotation 크기의 특성을 이용하여 회로의 크기를 줄일 수 있는 장점이 있다. 직렬로 배치된 barrel-rotator 중 앞쪽의 barrel-rotator는 일반적인 barrel-rotator를 사용하고, 뒤쪽의 barrel-rotator는 요구되는 rotation 크기에 따라 최적화가 이루어진다. 그리고 두 barrel-rotator의 결과 중에서 원하는 부분을 선택하여 최종 결과를 만들어내는 멀티플렉서들이 마지막에 배치된다.
이 논문에서는 이러한 cyclic-shifter에 있어서 직렬로 배치된 barrel-rotator 회로의 크기를 줄일 수 있는 방법을 제시한다. 직렬로 배치된 barrel-rotator 중 뒤쪽의 barrel-rotator의 경우, 그 결과가 모두 뒷단의 멀티플렉서에 의해 선택되지는 않는다. 일부는 어느 경우에도 필요하지 않는 것들이 있으며, 이 결과들에 대한 회로를 제거함으로써 회로의 크기를 더 줄일 수 있다.
이 논문은 다음과 같이 구성되어 있다. 2장에서는 MSCS의 기본 동작에 대해 살펴 본 뒤 기존 구조들에 대해 설명한다. 그리고 3장에서는 MSCS의 동작에 대해 기술한 뒤, 기존의 MSCS 구조들을 설명한다. 4장에서 개선된 구조를 제안하고, 5장에서 기존 구조와 비교한 뒤, 6장에서 결론을 맺는다.
Ⅱ. QC-LDPC 복호기의 multi-size cyclic shifter
이 장에서는 QC-LDPC 코드의 복호기에서 사용되는 multi-size cyclic-shifter와 그 구조에 대해 설명한다.
2.1. Multi-size cyclic shifter (MSCS)
QC-LDPC 코드의 복호기에서 사용되는 multi-size cyclic shifter는, 각각이
출력 데이터 중
MSCS의 구조는 크게 barrel-rotator를 이용하는 구조와 Benes 네트워크를 이용하는 구조로 나눌 수 있다. Barrel-rotator를 이용하는 구조는 다시 병렬적으로 배치하는 구조와 직렬적으로 배치하는 구조가 있다. 병렬적으로 배치하는 구조의 경우 한 barrel-rotator는 원래 방향대로
최종 출력은 다음과 같이 선택한다.
이러한 과정을 도식화하여 설명한 것이 그림 1과 그림 2이다.
Barrel-rotator를 직렬로 배치하는 구조는 크기가 N인 barrel-rotator로 입력 데이터를 우선
이 때
이 두 결과,
이러한 과정을 도식화하여 설명한 것이 그림 3과 그림 4이다.
직렬로 배치한 구조의 경우, rotation 크기의 특성을 이용하여 회로의 크기를 줄일 수 있다. 예를 들어, IEEE 802.16e에서 사용되는 QC-LDPC의 경우,
Ⅲ. 제안하는 multi-size cyclic shifter 구조
이 논문에서 제안하는 MSCS 구조는 직렬로 배치한 barrel-rotator를 기본으로 한다. 식(8)을 보면
이것을 barrel-rotator의 각 단계별로 적용하면 다음과 같다. Barrel-rotator가 총
만일 두 번째 barrel-rotator의 입력인
이고
이 된다. 마지막으로 출력은 다음과 같이 정의된다.
이제
이를 바꿔 적으면 다음과 같이 된다.
그런데 앞에서 설명했듯이
이렇게 필요 없을 데이터들은 정확히 선택할 필요가 없으므로 이를 이용하면 멀티플렉서를 줄일 수 있다. 식(11)에서 아래 부분의 식은
이렇게 되면
그림 5의 (a)는 두 번째 barrel rotator의
제안하는 구조와 기존의 구조를 비교하기 위해 두 구조를 RTL 수준에서 구현한 뒤 합성하여 비교하였다. 합성 라이브러리는 0.18㎛ 공정을 이용하였으며 Cadence사의 RTL Compiler로 합성하였다. 입력 데이터의 데이터 폭은 8bit로 설계하였고 802.16e WiMAX 표준을 위한 MSCS를 구현하였다.
합성 결과는 표 1에 제시하였다. 표의 두 번째 열이 논문 [4]에서 제안된 구조를 합성했을 때의 면적이며 세번째 열이 이 논문에서 제안하는 구조를 적용했을 때의 면적이다. 면적은 ㎛2 단위로 제시하였다. 표를 보면 이 논문에서 제안하는 구조를 적용했을 때 지연시간도 약간 줄어들면서 약 12.4% 정도 면적이 줄어들었음을 확인할 수 있다.
[표 1.] 그림 3 구조의 기존 방식과 제안하는 방식의 비교
그림 3 구조의 기존 방식과 제안하는 방식의 비교
이 논문에서는 QC-LDPC 코드의 복호기에서 사용되는 MSCS를 위한 새로운 구조를 제안하였다. 이 구조에서는 기존의 직렬 barrel-rotator 구조를 개선하여, 필요없는 멀티플렉서를 제거함으로써 면적을 줄일 수 있다. 본 논문에서는 802.16e WiMAX에 대해서만 비교하였으나 QC-LDPC를 사용하는 다른 통신 표준의 복호기에 대해서도 사용될 수 있다.