디지털 통신 분야에서 전송 속도와 용량은 다중화와 다중 레벨 방식을 이용하는 변조 기법의 채택 및 주파수 대역폭의 확장을 통해 증가해 왔다. 그러나 물리 계층 잡음이나 삽입 손실과 같은 문제들 때문에 이러한 방법을 통해서는 더 이상의 추가 이익을 얻기가 힘든 상황에 이르렀다. 4세대 광대역 통신시스템은 광대역 데이터 및 고속 패킷 전송을 지원하기 위한 초고속의 오류 정정을 요구하고 있으며, 채널용량의 한계에 근접하는 높은 성능을 갖는 새로운 채널부호화 기법이 요구된다. 4세대 이동통신 시스템을 위한 차세대 오류정정 방식으로 로버트 갤러거(R.Gallager)에 의해 제안된 LDPC(Low Density Parity Check) 부호[1]가 많은 관심을 받고 있다. Shanon의 한계에 근접하는 또 다른 오류 정정 부호화 방식인 터보부호와 비교하여 오류들을 대부분 검출할 수 있으나 당시의 기술로는 구현이 어려워 관심을 받지 못하였다. LDPC 부호는 1990년대부터 재조명되고 있으며, 부호의 생성 및 복호에 대한 연구가 활발히 진행되고 있다[2,3].

LDPC 부호는 모바일 WiMAX 표준(IEEE 802.16e), 무선랜 표준(IEEE 802.11n), 10 Gbps 이더넷 표준(IEEE 802.3an), 유럽 디지털 위성방송 표준(DVB-S2), 중국 지상파 디지털방송 DTTB(digital television terrestrial broadcasting) 등에서 채널 부호화 방식으로 채택되고 있으며, LDPC 부호 및 복호기 설계기술은 차세대 고속 무선통신 시스템 및 단말기 구현의 핵심기술이 될 것이다. LDPC 부호의 복호는 기본적으로 반복복호를 기반으로 수행되며, 복호 알고리듬, 복호기 구조, 고정소수점 비트 수 등 다양한 요인들이 복호성능과 하드웨어 복잡도에 영향을 미친다.

본 논문에서는 INMS(improved normalized min-sum) 알고리듬 기반의 LDPC 복호기를 Matlab으로 모델링하고, 고정소수점 시뮬레이션을 통해 복호 수렴속도와 복호성능을 분석하였으며, 그 결과를 IEEE 802.16e 모바일 WiMAX 표준과 IEEE 802.11n WLAN 표준을 지원하는 LDPC 복호기에 적용하여 하드웨어를 최적화하고 복호성능을 향상 시켰다.

LDPC 부호는 원소의 대부분이 ‘0’으로 구성되는 패리티 검사 행렬(parity check matrix; PCM)에 의해 정의되는 선형 블록부호이며, PCM의 구성에 따라 여러 가지 형태로 구분된다. 구조화된 부호의 일종인 quasicyclic(QC) LDPC 부호는 m × n 크기의 PCM에 의해 정의되며, z_f × z_f의 치환행렬(permutation matrix) 또는 영 행렬(zero matrix)인 부행렬(sub-matrix)들로 구성되고, m_b × n_b 크기의 이진 기저행렬(binary base matrix)로부터 확장될 수 있다. 치환행렬은 단위행렬을 주어진 값만큼 오른쪽으로 순환 이동시킨 행렬을 나타낸다. IEEE 802.16e 표준[4]과 IEEE 802.11n 표준[5]에 정의된 LDPC 부호의 PCM 파라미터는 표 1과 같다. 802.16e의 LDPC 부호는 19가지 블록길이와 6가지 부호율에 대해 114가지의 PCM을 규정하며, 802.11n에서는 3가지의 블록길이와 4가지 부호율에 대해 12가지의 PCM을 규정하고 있다.

LDPC 부호는 Tanner 그래프 상의 검사노드(check node; CN)와 변수노드(variable node; VN) 사이에서 반복적인 정보전달 과정에 의한 belief propagation 알고리듬으로 복호될 수 있다. Tanner 그래프는 PCM의 행과 열을 검사노드와 변수노드로 매핑시킨 이분(bipartite) 그래프이며, 검사노드와 변수노드 사이의 연결은 PCM에서 1의 위치에 의해 결정된다. LDPC 복호기의 구조는 처리 방법에 따라 일반적으로 2단계 복호와 레이어드 복호로 구분된다. 2단계 복호는 태너 그래프 상의 연결을 그대로 회로로 구현한 것으로 PCM의 영(0) 행렬을 무시할 수 없으며, 행렬이 커질수록 많은 메모리 용량이 필요하다는 단점이 있다. 레이어드 복호는 2단계 복호를 다수의 레이어로 분할하여 처리하는 부분병렬 복호의 한 형태로 2단계 복호에 비해 수렴속도가 빠르며, 메모리를 적게 사용한다. 본 논문에서는 저면적 구 현과 영 행렬을 효과적으로 무시할 수 있는 레이어드 복호를 사용하여 LDPC 복호기를 설계하였다.

LDPC 복호 알고리듬으로는 합곱(sum-product; SP) 알고리듬[6], 합곱 알고리듬의 연산 복잡도를 감소시킨 LLR(log-likelihood ratio)-SP 알고리듬[7], 최소합(minsum; MS) 알고리듬[8] 등이 있다. 최소합 알고리듬은 식(1) ~ 식(3)으로 표현되며, LLR-SP 알고리듬의 검사 노드와 변수노드 연산 중 검사노드 연산에서의 함수 Φ(x)를 근사화한 알고리듬이다. 최소합 알고리듬은 검사노드 연산에서 근사화에 의해 LLR-SP 알고리듬에 비해 복호성능이 떨어진다.

(i) 검사노드 연산

(ii) 변수노드 연산

본 논문에서 사용된 개선된 정규화 최소합(INMS) 알고리듬[9]은 최소합 알고리듬의 검사노드 연산에 정규화 인수 α₁,α₂를 곱하여 근사화에 의한 값을 보상하여 복호성능을 향상시킨다. INMS 알고리듬의 검사노드 연산은 식(4)~식(5)로 표현되며, 최솟값에 α₁ = 0.75를 곱하고 준최솟값에 α₂ = 0.875를 곱하여 복호성능을 높인다.

INMS 복호 알고리듬의 복호성능을 분석하고 최적 하드웨어 설계조건을 찾기 위해 Matlab을 이용하여 LDPC 복호기의 고정소수점 모델링을 하였다. 입력 데이터의 E_b/N_o를 1.5~3.0 dB 범위에서 0.3 dB 단위로 가변시키고, 고정소수점 비트를 (4.3), (5.3)으로 설정하여 시뮬레이션 하였다. (m⋅n)의 표현에서 m은 정수부분의 비트 수를 나타내며, n은 소수부분의 비트 수를 나타낸다. 최대 반복복호 회수를 8로 설정했으며, 100프레임의 데이터를 시뮬레이션 하여 평균 비트오율(bit error rate; BER)를 구했다. 그림 1은 부호율이 1/2이고, 블록길이가 2304 비트인 경우의 시뮬레이션 결과이다. INMS 복호 알고리듬과 최소합 복호 알고리듬에 고정 소수점 비트 폭 (4.3), (5.3)을 적용하여 복호 성능을 비교한 결과, INMS 복호 알고리듬을 적용한 LDPC 복호 기가 고정소수점 비트 폭 (4.3)인 경우에 복호성능이 우수함을 알 수 있다. 이와 같은 고정소수점 시뮬레이션 결과를 토대로, INMS 복호 알고리듬과 고정소수점 비트 폭 (4.3)을 회로설계에 적용했다.

본 논문에서 설계된 LDPC 복호기는 2단계 복호방식보다 복호 수렴속도가 우수하며, 하드웨어 구조의 융통성이 좋은 레이어드 복호방식을 적용하였다.

설계된 복호기의 구조는 그림 2와 같다. SM(signmagnitude) 수체계를 기반으로 INMS 복호 알고리듬을 연산하는 DFU(decoding function unit) 뱅크, PCM 정보를 저장하는 H-ROM, 결정변수 값을 저장하는 APP 메모리, 결정변수의 부호 값을 저장하는 부호 메모리, 입력 데이터를 SM 수체계로 변환시켜주는 TC_SM, 변환된 데이터를 부행렬 단위로 모아주는 입력버퍼, 부행렬 단위의 복호 완료 데이터를 27비트 단위로 나누어 출력하는 출력버퍼, 경판정을 실행하는 경판정 블록, 그리고 제어회로 등으로 구성된다.

H-ROM은 IEEE 802.11n의 블록길이와 부호율에 대한 PCM 정보 12가지와 IEEE 802.16e 블록길이 2304에 대한 부호율 6가지의 PCM 정보 저장한다. PCM을 구성하는 부 행렬들의 대다수가 영(0) 행렬로 이루어져 있으며, 영이 아닌 부행렬의 수는 부호율에 따라 6~22개로 가변적이다. 영 행렬은 검사노드와 변수노드 사이에 정보를 전달하지 않아 연산이 존재하지 않는다. 본 논문에서는 PCM의 모든 정보를 저장하는 대신에, 영 행렬을 제외한 영이 아닌 부행렬들의 위치 정보와 순환 시프트 정보만을 H-ROM에 저장하는 방법을 적용함으로써 하드웨어가 최소화되도록 하였다.

IEEE 802.16e 표준에는 블록길이 2304에 대한 6가지 기본 PCM을 정의하고 있으며, 나머지 블록길이와 부호화율에 대한 PCM은 6개의 기본 PCM을 이용하여 생성할 수 있다. 본 논문에서는 식 (6)과 식(7)의 연산을 수행하는 SVG(shifting value generator)[10]을 이용해 블록길이와 부호율에 따른 PCM 정보가 효율적으로 생성되도록 설계하였다.

LDPC 복호기의 검사노드 메모리에는 수평단계의 연산결과 L_j→i가 저장된다. 일반적인 방식에서는 w-비트로 표현되는 L_j′→i를 각 레이어의 유효 부행렬 개수 l_c만큼 저장하므로, 레이어 당 {(w × l_c) × z_f}-비트의 메모리 용량이 필요하다. z_f는 부행렬의 크기이며, 블록 길이에 따라 달라진다. 본 논문에서는 각 레이어의 최솟값(min0), 준최솟값(min1)과 함께 L_j′→i의 부호와 최솟값 여부를 나타낸 2비트 신호 SM 을 저장하는 방식 [10]을 사용하여, 레이어 당 {(w × 2 + 2 ×l_c) × z_f}-비트의 메모리 용량만 필요하므로 검사노드 메모리를 크게 감소시킬 수 있다.

LDPC 복호기는 복호가 완료되었을 시 복호과정을 중단시켜 불필요한 클록 주기 소모를 줄일 필요가 있다. 본 논문에서는 반복 복호 연산이 진행된 결정변수의 부호 값과 이전 반복 복호 연산이 완료된 결정변수의 부호 값을 서로 비교하여 복호완료 여부를 판단하는 방법 [11]을 이용해 그림 3과 같은 경판정 블록을 설계하였다. 두 값을 비교하기 위해 2-입력 XOR 게이트 96개로 비트별 XOR 연산을 수행한 후, 출력된 96 비트 값을 2-입력 OR 게이트와 4-입력 OR 게이트가 트리 형태로 구성된 OR 게이트를 이용하여 연산하여 결과값을 레지스터에 저장한다. 각 유효 서브블록마다 비교하며, 1회의 반복복호가 종료되었을 시 복호완료 여부를 판단하여 복호를 종료시킨다.

설계된 복호기의 동작 타이밍 도는 그림 4와 같다. 28비트 단위로 입력되는 2의 보수 수체계의 부호어는 TC_SM 블록에 의해 SM 수체계로 변환된 후, 부행렬 크기(z_f × 7) 단위로 모아져 APP 메모리에 저장되며, 입력된 부호어는 부행렬 단위로 DFU에 의해 복호가 이루어진다. DFU는 이전 레이어의 복호결과 값을 APP 메모리에서 읽어와 복호연산을 수행한 후, 그 결과를 다음 레이어 연산과 다음 반복복호 연산을 위해 메모리에 저장하는 동작을 수행한다. 동작 속도를 향상시키기 위한 방안으로써, 지연이 많이 발생한 부분에는 파이프라인 레지스터를 사용하였다. 파이프라인 레지스터가 적용된 복호기에서 한 레이어의 유효블록 수가 6인 경우에 대한 동작 타이밍 도는 그림 5와 같다. H-ROM에서 나온 시프트 정보는 SVG를 통하여 블록길이와 부효율에 따른 시프트 정보 값을 계산하고 레지스터에 저장한 후, Permuter_left 블록에 입력되어 APP 메모리에서 출력된 결정변수 값을 부행렬 단위로 왼쪽으로 시프트를 시키고, 시프트 된 결정변수 값은 레지스터에 저장되었다가 DFU에서 복호연산을 한다. 이를 통해 새로 갱신된 결정변수 값은 레지스터를 거쳐 Permuter_right 블록에 입력되어 시프트 되기 전의 위치로 되돌린 후 APP 메모리에 저장된다.

한 레이어의 복호에는 l_c + 4 (단, l_c는 유효 부행렬 수를 나타냄) 클록 주기가 소요되며, 1회의 반복복호에는 (l_c + 4) × m_b (단, m_b는 레이어 수를 나타냄) 클록 주기가 소요된다.

DFU는 입력 부호어에 포함되어 있는 오류를 정정하기 위해 자신을 제외한 나머지 부호어들의 LLR(loglikelihood rato) 값을 취합하여 원래의 부호어에 가장 가까운 LLR 값을 예측하는 기능을 수행하며, INMS 복호 알고리듬에 의한 검사노드 연산과 변수노드 연산을 수행하여 결정변수 값과 검사노드 값을 계산한다. 부행렬 (sub-matrix)단위로 복호연산을 처리하는 블록직렬 방식의 복호기에는 부행렬 최대 크기만큼의 DFU 배열이 사용된다. 본 논문의 LDPC 복호기는 다중표준(IEEE 802.11n과 IEEE 802.16e)의 블록길이에 따른 다중모드를 지원하도록 설계되었으며, 이를 위해 802.11n 모드에서는 부행렬의 크기에 따라 27/54/81개의 DFU가 선택적으로 사용되며, 802.16e 모드에서는 부행렬의 크기에 따라 24~96개의 DFU가 선택적으로 사용된다.

INMS 복호 알고리듬 기반의 복호연산을 수행하는 DFU의 구조는 그림 6과 같으며, DFU 내부의 모든 연산을 SM 수체계로 처리하여 수체계 변환 블록을 사용하지 않는 것을 특징으로 한다. 변수노드 값을 구하기 위한 SM 감산기(SM_Sub), 최솟값 검출기(Min_det), 부호비트 누산기, 검사노드 연산 후의 결정변수 값을 구하기 위한 SM 가산기(SM_Add), 그리고 최솟값과 준 최솟값에 정규화 인수를 연산하여 복호성능을 향상시키는 개선된 정규화 인수(improved normalized factor; INF) 연산기(INF_sum) 등으로 구성된다. 설계된 DFU 내부의 LLR 값들은 7비트로 근사화 되어 연산되며, 부호와 크기를 분리하여 계산된다.

DFU에서 복호가 이루어지는 과정은 다음과 같다. 검사노드 값 와 결정변수 는 SM_Sub 블록을 통해 변수노드 으로 계산된다. 계산된 변수노드 값 은 부호와 크기로 분리되고 부호는 순차적으로 입력되어 곱셈 연산된다. 그리고 분리된 변수노드 값의 크기는 는 최솟값 검출기(Min_det)를 통해 순차적으로 입력되는 들과 비교되어 최솟값과 준최솟값이 검출된 후 INF_sum에서 INF 연산을 수행하고 레지스터에 저장된다. SM_Sub 블록에 의해 계산된 변수 노드 값 은 DFU의 외부로 보내져 FIFO 메모리에 순차적으로 저장된다. 한 레이어의 유효 서브블록 수만 큼의 연산이 완료되면 FIFO에 저장된 변수노드 값이 순차적으로 DFU에 입력된다. FIFO에서 입력된 변수노드 값의 크기 는 Min_det 블록을 통해 검출된 최솟값과 비교되어 두 값이 같으면 준최솟값 min1이 새로운 검사노드 값의 크기 로 결정된다. 그리고 FIFO로부터 입력되는 변수노드 값 의 부호와 누적곱셈 을 거친 부호가 곱셈연산을 거쳐 검사노드 값 의 부호로 결정된다. 부호의 누적곱셈은 XOR 연산으로 이루어진다. 결정된 검사노드 값 과 FIFO에서 들어 오는 변수노드 값 은 SM_Add에서 가산되어 결정 변수 값이 구해지고 결정변수 메모리에 저장된다. 한편 누적곱셈을 통해 얻어진 검사노드 값의 부호 1비트와 비교기를 통해 얻은 mag_type 1비트 그리고 최솟값 검출기를 통해 얻어진 최솟값과 준최솟값은 검사노드 메모리에 저장된다. INMS 복호 알고리듬이 적용된 DFU의 핵심적인 블록인 INF_sum의 구조는 그림 7과 같다.

최솟값과 준최솟값에 다중 정규화 인수를 곱하는 연산 대신에 최솟값과 준최솟값을 오른쪽으로 시프팅시켜 가산하는 연산을 통해 곱셈기 대신에 가산기만을 사용하여 하드웨어를 최적화하였다. 가산기는 비트 수가 6비트로 작으므로 면적의 최소화를 위해 리플캐리 가산기(RCA)를 사용하였다.

설계된 LDPC 복호기는 Matlab을 이용한 랜덤 소스 벡터 생성, LDPC 부호화, QPSK 변조, 채널잡음 삽입 그리고 복조 등을 통해 Eb/No=1.5dB~3dB(0.3dB 간격)의 시뮬레이션 벡터를 생성하였다. 8 비트로 양자화된 벡터를 이용하여 Verilog HDL로 설계된 복호기의 ModelSim 시뮬레이션을 수행하였으며, 벡터와의 비교를 통해 정정되지 못한 오류 비트들을 찾아 복호성능을 분석하였다. 설계된 복호기는 그림 8(a)의 방법으로 하드웨어 동작을 검증하였다. Eb/No=3.0 dB로 생성된 테스트 벡터를 입력 데이터로 사용한 FPGA 검증결과는 그림 8(b)와 같으며, 복호된 데이터가 ModelSim 시뮬레이션 결과와 일치하여 설계된 LDPC 복호기의 정상 동작을 확인하였다.

설계된 복호기는 그림 9(a)와 같은 Simulink-HDL 연동 검증을 통해 복호성능을 분석하였다. Simulink를 이용하여 복호기의 HDL 모델을 Xilinx Blockset으로 연동시키고, Matlab을 통해 생성된 테스트 벡터를 입력 데이터로 사용하여 Simulink-HDL 연동 검증을 하였다. 최대 반복복호를 8회로 설정하였으며, 100 프레임의 데이터를 시뮬레이션에 사용하여 평균 BER를 구하였다. 그림 9(b)는 IEEE 802.11n의 블록길이 1944에 대한 부호율 1/2, 2/3과 IEEE 802.16e의 블록길이 2304에 대한 부호율 1/2, 2/3A인 경우의 BER 성능 그래프이다.

검증이 완료된 복호기는 0.18-μm CMOS 표준셀을 이용하여 100 MHz 동작주파수의 조건으로 논리합성을 하였으며, 입력 및 출력 버퍼와 경판정 회로를 포함하여 284,409 게이트와 62,976 비트의 메모리로 구현되었다. 설계된 LDPC 복호기의 복호성능은 부호율과 블록 길이와 반복복호 횟수 등에 따라 달라진다. 데이터 입력 및 출력 버퍼링에 소요되는 시간을 포함시켜 복호성능을 예측한 결과, 반복복호 횟수가 4인 경우에 블록길이 2,304비트, 부호율 5/6인 동작모드는 최대 218 Mbps의 복호성능이 예상되며, 블록길이 576비트, 부호율 1/2인 동작모드는 82 Mbps의 성능이 예상된다.

표 2는 본 논문의 설계 결과와 문헌에 발표된 WLAN 및 WiMAX용 LDPC 복호기의 성능 비교를 보이고 있다. WiMAX와 WLAN을 모두 지원하는 본 논문의 LDPC 복호기가 단일 표준만 지원하는 문헌 [12]~[15]의 복호기에 비해 게이트 수와 메모리 크기가 가장 작게 구현되었다. 입출력 버퍼링에 소요되는 시간을 제외하고 복호 프로세싱 구간의 성능만 고려하면, 문헌 [12], [14] 보다 높은 성능을 갖는 것으로 평가된다. 본 논문의 복호기는 동작주파수가 낮아 문헌 [13], [15]에 비해 출력율이 낮게 평가되었으나, 내부에 파이프라인 스테이지를 삽입하고, 미세 공정을 적용하여 동작주파수를 높이면 우수한 성능을 보일 것으로 예상된다.

INMS 복호 알고리듬을 적용하여 IEEE 802.16e의 19가지 블록길이와 6가지 부호율 그리고 IEEE 802.11n의 3가지 블록길이와 4가지 부호율을 지원하는 LDPC 복호기를 설계하고 검증하였다. Matlab으로 복호기를 모델링하여 INMS 복호 알고리듬의 복호성능을 검증하고 최적설계조건을 도출하였다. 설계된 복호기는 입력 LLR 비트 수를 (4.3)으로 적용하여 하드웨어를 최적화 하였으며, 복호성능을 향상시켰다. 또한 경판정을 수행하는 블록을 설계함으로써 불필요한 클럭주기 소모를 제거하였다. 설계된 LDPC 복호기는 284,409 게이트와 62,976 비트의 RAM으로 구현되었다. 1.8V 전원전압에서 100 MHz로 동작 가능할 것으로 평가되며, 약 82~218 Mbps의 성능을 가질 것으로 예상된다.