저밀도 패리티 검사 부호의 복호 장치 및 방법 document_id A220623035430

저밀도 패리티 검사(LDPC : Lov Density Parity Check) 부호는 터보 부호보다 우수한 성능, 낮은 복호 복잡도, 병렬처리로 고속 처리가 가능하기 때문에 4세대 이동 통신 시스템에 적합한 부호화 방식으로 많은 관심을 받고 있다. LDPC부호는 1962년 Gallager에 의해 처음 제안되었으며, 패리티 검사 행렬(Parity Check Matrix) H의 원소들의 대부분 이 '0'인 선형 블록 부호(Linear block code)로서 당시의 기술력으로는 구현이 불가능한 부호 복잡도로 인해 잊혀져 왔다. 그러나 Mackay와 Neal은 이를 재발견하였고, Gallager의 간단한 확률적(Prababilistic) 복호법을 이용하여 성능이 매우 우수함을 보였다. 일반적인 LDPC 부호는 수십번 반복되는 BP(belief propagation) 알고리즘을 통해 복호된다. LDPC 부호의 대표적인 복호화 방법으로는 Standard BP, Shuffled BP 및, Replica shuffled BP 가 존재한다. 일반적인 LDPC부호의 복호 과정은 비트노드와 검사노드간의 병렬 반복 복호과정을 통해 이루어진다. LDPC 부호는 선형블락부호(linear block codes)의 일종으로, 하나의 LDPC 부호는 패리티 검사 행렬(parity check matrix)에 따라 결정된다. 또, 패리티 검사행렬은 이분그래프(bipartite)그래프와 1:1로 대응된다. 이때, 이분 그래프에 대응하는 두 가지 종류의 노드(비트노도(bit node). 검사노드(check node))를 가지게 되고 비트노드의 경우 패리티 검사행렬의 열(column)에, 검사노드의 경우 행(row)에 각각 대응된다. 따라서 NxM 패리티검사행렬이 주어졌을 때 비트노드의 개수는 N개, 검사노드의 개수는 M개이다. 이분그래프의 선(edge)는 비트노드와 검사노드간의 연결이 있을 때만 연결되고, 이 연결은 패리티검사행렬에서 1의 위치에 따라 결정되고, 선의 개수는 패리티 검사행렬 전체의 1의 개수와 동일하다. 도 1은 종래의 기술에 따른 Standard BP를 이용한 LDPC 부호의 복호과정을 도시한 흐름도이다. Standard BP를 이용한 LDPC 부호의 복호과정은 채널로부터 받은 LLR(log likelihood ratio)값을 이용하여 패리티검사행렬에 의해 정의된 이분 그래프상의 선으로 연결된 비트노드와 검사노드간의 확률값을 주고받아 복호하는 알고리즘으로, 상기 도 1을 참조하면 종래의 LDPC 부호의 복호 장치는 100단계에서 비트노드의 초기 확률값을 계산하여 에지(edge)로 연결된 검사노드로 제공한다. 상기 100단계는 AWGN Channel과 BPSK modulation을 가정했을 때 n번째 비트노드가 1일 확률 또는 0일 확률을 LLR형태로 표현한 초기 확률값을 계산하고, N개의 비트노드에 대한 초기 확률값을 에지로 연결된 각 검사노드로 제공하는 과정으로 이를 다음 003c#수학식 1003e#과 같이 표현할 수 있다. 여기서, Vmn(i)는 i번째 반복에서 n번째 비트노드에서 m번째 검사노드로 전달되는 확률값이고, Uch,n는 n번째 수신비트인 비트노드의 초기 확률값이고, N0는 노이즈 레벨이고, yn은 채널로부터 수신하는 n번째 수신비트이다. 이후 종례의 복호 장치는 102단계로 진행하여 수평단계(Horizontal step)를 수행한다. 상기 수평단계는 N개의 비트노드들의 확률값을 이용하여 아래 003c#수학식 2003e#를 만족하는 M개의 검사노드들의 확률값을 계산하여 다시 연결된 비트노드로 제공하여 정보를 업데이트(update)한다. 여기서, Umn(i)는 i번째 반복에서 m번째 검사노드에서 n번째 비트노드로 전달되는 확률값이고, N(m)는 m번째 검사노드에 연결된 비트노드의 집합이고, N(m)＼n은 N(m)으로 표현되는 집합에서 n번째 비트노드를 제외한 집합이고, Vmn(i)는 i번째 반복에서 n번째 비트노드에서 m번째 검사노드로 전달되는 확률값이다. 상기 102단계 이후 복호 장치는 104단계로 진행하여 수직단계(Vertical step)를 수행한다. 상기 수직단계는 M개의 검사노드들의 확률값을 이용하여 아래 003c#수학식 3003e#를 만족하는 비트노드들의 확률값을 계산하여 다시 연결된 검사노드로 제공하여 정보를 업데이트(update)한다. 이때 각 비트노드들의 사후 확률값은 아래 003c#수학식 4003e#와 같이 계산한다. 여기서, Vmn(i)는 i번째 반복에서 n번째 비트노드에서 m번째 검사노드로 전달되는 확률값이고, Uch,n는 n번째 수신비트인 비트노드의 초기 확률값이고, Umn(i)는 i번째 반복에서 m번째 검사노드에서 n번째 비트노드로 전달되는 확률값이고, M(n)는 n번째 비트노드에 연결된 검사노드의 집합이고, M(n)＼m은 M(n)으로 표현되는 집합에서 m번째 검사노드를 제외한 집합이다. Vn(i)는 i번째 반복에서 n번째 비트노드의 사후 확률값(posteriori LLR)이고, Uch,n는 n번째 수신비트인 비트노드의 초기 확률값이고, Umn(i)는 i번째 반복에서 m번째 검사노드에서 n번째 비트노드로 전달되는 확률값이고, M(n)는 n번째 비트노드에 연결된 검사노드의 집합이다. 상기 104단계 이후 복호 장치는 106단계로 진행하여 시험 복호(tentative decoding) 과정을 수행한다. 상기 시험 복호는 상기 104단계에서 계산한 비트노드들의 사후 확률값을 코드워드(codeword)라 가정하고 패리티검사행렬에 곱했을 때, 0이 나온다면 올바른 코드워드로 결정되었다고 판단하며 이를 아래 003c#수학식 5003e#와 같이 표현한다. 여기서, H는 패리티 검사 행렬이고, 는 i번째 반복에서 사후 확률값에 의해 추정한 코드워드(codeword)이다. 상기 106단계 이후 복호 장치는 108단계로 진행하여 오류가 검출되지 않은 올바른 코드워드이거나 기설정한 반복횟수를 초과하였는지 검사한다. 검사결과 올바른 코드워드이거나 기설정한 반복횟수를 초과하였으면 복호 알고리즘을 종료하고, 검사결과 올바른 코드워드가 아니고 기설정한 반복횟수를 초과하지 않았으면 상기 102단계로 돌아가서 102단계에서 108단계까지의 일련의 과정을 반복 수행한다. 도 2는 종래의 기술에 따른 LDPC 부호의 복호 방법인 Standard BP의 이분 그래프를 도시한 도면이다. 상기 도 2를 참조하면, H 행렬인 패리티 검사 행렬이 참조번호 200과 같이 표현될 때 이를 Standard BP의 이분 그래프로 표현하면 참조번호 210과 같이 표현된다. 상기 이분 그래프(210)에서 원은 비트노드로서 패리티 검사행렬의 열(column)에 대응하고, 사각형은 검사노드로서 패리티 검사행렬의 행(row)에 대응된다. 도 3은 종래의 기술에 따른 LDPC 부호의 복호 방법인 Shuffled BP의 이분 그래프를 도시한 도면이다. 상기 도 3을 참조하면, H 행렬인 패리티 검사 행렬이 참조번호 300과 같이 표현될 때 이를 두개의 비트노드 그룹을 가지는 Shuffled BP의 이분 그래프로 표현하면 참조번호 310과 같이 표현되며 업데이트(update) 순서는 참조번호 312, 314, 316, 318의 순서로 확률값이 계산되어 업데이트 된다. LDPC부호의 블록길이가 길어지게 되면 비트노드나 검사노드를 나누어서 구현해야 한다. 상기 도 3의 Shuffled BP 알고리듬의 경우, 비트노드를 나누었을 때 효율적으로 복호하는 방법에 관한 알고리듬으로 초기화 과정과 시험 복호과정은 상기 도1의 standard BP와 동일하다. 하지만 수평 단계와 수직 단계의 과정에 있어서 standard BP와 다르게 모든 비트노드에 대한 연산을 끝낸 후 검사노드에 업데이트하는게 아니라, 위에서 설명한 순서로 그룹별로 나눈 비트노드의 확률값만을 검사노드에 업데이트한다. 만약 비트노드를 t개의 그룹으로 나누었다면, 첫 번째 그룹에 해당하는 비트노드의 확률값을 검사노드로 업데이트한다. 검사노드쪽에서는 업데이트된 확률값을 이용해 각 검사노드가 만족될 확률값을 구하여 그 다음 그룹에 해당하는 두 번째 그룹의 비트노드를 업데이트 한다. 그러면 다시 두 번째 그룹에 해당하는 비트노드는 이 정보를 이용하여 다시 검사노드쪽으로 확률값 정보를 없데이트 한다. 이렇게 각 그룹에 해당하는 비트노드가 순차적으로 검사노드와 정보를 주고받음으로서 복호과정을 수행한다. t개의 비트노드 그룹이 모두 한번씩 검사노드와 정보를 주고받은 후에 1번의 반복복호가 끝난다. 도 4는 종래의 기술에 따른 LDPC 부호의 복호 방법인 Replica shuffled BP의 이분 그래프를 도시한 도면이다. 상기 도 4를 참조하면, H 행렬인 패리티 검사 행렬이 참조번호 400과 같이 표현될 때 이를 두개의 비트노드 그룹과 두개의 복호기를 가지는 Replica shuffled BP의 이분 그래프로 표현하면 참조번호 410과 같이 표현된다. Shuffled BP 알고리듬이 한 개의 복호기(decoder)를 이용하여 전체 비트노드를 t개의 그룹으로 나누어 순차적으로 복호를 진행하는 알고리듬이라면, 상기 도 4의 Replica shuffle BP 알고리듬의 경우 두개 이상의 복호기를 가지고 각각 다른 업데이트를 순서를 가지고 동시에 복호를 수행하는 알고리듬이다. 상술한 바와 같이 긴 길이의 LDPC 부호를 하드웨어로 구현하기 위해서는, 병렬 반복 복호 과정을 직렬 복호 과정으로 나누는 과정은 필수적이다. 종래기술의 경우 이러한 직렬 복호 과정을 효과적으로 해결하기 위해 비트노드를 그룹으로 묶어 (또는 검사노드를 그룹으로 묶어) 순차적으로 복호 과정을 수행하였다. 순차적인 복호과정 중에 먼저 업데이트된 정보를 이용하기 때문에 standarad BP의 반복복호 횟수보다 적은 복호횟수를 이용하여 동일한 성능을 얻을 수 있다. 이러한 경우, 그룹간의 복호 되는 순서에 따라 오류확률이 달라지게 된다. 다시 말해, 먼저 복호되는 그룹의 오류확률이 나중에 복호 되는 그룹의 오류확률보다 높게 된다. 이러한 문제해결을 위해 두 개의 decoder를 사용하는 replica shuffled decoding의 경우, shuffled BP 알고리듬보다 반복 복호 횟수를 더 줄일 수 있지만 전체적인 연산량은 두 배 이상으로 늘어나게 된다.