통신 시스템에서 채널 인터리빙/디인터리빙 장치 및 방법 document_id A220623034567

무선 통신 시스템에서는 채널의 여러 가지 잡음(noise)과 페이딩(fading) 현상 및 심볼간 간섭(inter-symbol interference, ISI)에 의해 링크(link)의 성능이 현저히 떨어지게 된다. 따라서 차세대 이동 통신, 디지털 방송 및 휴대 인터넷과 같이 높은 데이터 처리량과 신뢰도를 요구하는 고속 디지털 통신 시스템들을 구현하기 위해서 잡음과 페이딩 및 ISI에 대한 극복 기술을 개발하는 것이 필수적이다. 최근에는 정보의 왜곡을 효율적으로 복원하여 통신의 신뢰도를 높이기 위한 방법으로서 오류정정부호(error-correcting code)에 대한 연구가 활발히 이루어지고 있다. 1960년대에 Gallager에 의해서 처음 소개된 LDPC 부호는 당시 기술을 훨씬 뛰어넘는 구현 복잡도로 인해 오랫동안 잊혀져 왔다. 하지만 1993년 Berrou와 Glavieux, Thitimajshima에 의해 발견된 터보(turbo) 부호가 새넌(Shannon)의 채널 용량에 근접하는 성능을 보임에 따라 터보 부호의 성능과 특성에 대한 많은 해석이 이루어지면서 반복 복호(iterative decoding)와 그래프를 기반으로 하는 채널 부호화의 많은 연구가 진행되었다. 이를 계기로 1990년대 후반에 상기 LDPC 부호에 대해 재연구되면서 상기 LDPC 부호에 대응되는 Tanner 그래프(factor 그래프의 특별한 경우) 상에서 합곱(sum-product) 알고리즘에 기반한 반복 복호(iterative decoding)를 적용하여 복호화를 수행하면 Shannon의 채널 용량에 근접하는 성능을 가짐이 밝혀졌다. 상기 LDPC 부호는 통상적으로 그래프 표현법을 이용하여 나타내며, 그래프 이론 및 대수학, 확률론에 기반한 방법들을 통해 많은 특성을 분석할 수 있다. 일반적으로 채널 부호의 그래프 모델은 부호의 묘사(descriptions)에 유용할 뿐만 아니라, 부호화 된 비트에 대한 정보를 그래프 내의 정점(vertex)에 대응시키고 각 비트들의 관계를 그래프 내에서 선분(edges)으로 대응시키면, 각 정점들이 각 선분들을 통해서 정해진 메시지(messages)를 주고받는 통신 네트워크로 간주할 수 있기 때문에 자연스런 복호 알고리즘을 이끌어 낼 수 있다. 예를 들면 그래프의 일종으로 볼 수 있는 트렐리스(trellis)에서 유도된 복호 알고리즘에는 잘 알려진 비터비(Viterbi) 알고리즘과 BCJR (Bahl, Cocke, Jelinek and Raviv) 알고리즘이 있다. 상기 LDPC 부호는 일반적으로 패리티 검사행렬(parity-check matrix)로 정의되며 Tanner 그래프로 통칭되는 이분(bipartite) 그래프를 이용하여 표현할 수 있다. 여기서 이분 그래프는 그래프를 구성하는 정점들이 서로 다른 2 종류로 나누어져 있음을 의미하며, 상기 LDPC 부호의 경우에는 변수 노드(variable node)와 검사 노드(check node)라 불리는 정점들로 이루어진 이분 그래프로 표현된다. 여기서 변수 노드는 부호화된 비트와 일대일 대응된다. 도 1과 2를 참조하여 상기 LDPC 부호의 그래프 표현 방법에 대해 설명한다. 도 1은 8개의 열(column)과 4개의 행(row)으로 이루어진 상기 LDPC 부호의 패리티 검사 행렬 H1의 예이다. 도 1을 참조하면, 열이 8개 있기 때문에 길이가 8인 부호어(codeword)를 생성하는 LDPC 부호를 의미하며, 각 열은 부호화된 8 비트와 대응된다. 도 2는 도 1의 H1에 대응하는 Tanner 그래프를 도시한 도면이다. 도 2를 참조하면, 상기 LDPC 부호의 상기 Tanner 그래프는 8개의 변수 노드들 x1(202), x2(204), x3(206), x4(208), x5(210), x6(212), x7(214), x8(216)과 4개의 검사 노드(check node)(218, 220, 222, 224)들로 구성되어 있다. 여기서 상기 LDPC 부호의 패리티 검사 행렬 H1의 i번째 열과 j번째 행은 각각 변수 노드 xi와 j 번째 검사 노드에 대응된다. 또한 상기 LDPC 부호의 패리티 검사 행렬 H1의 i번째 열과 j번째 행이 교차하는 지점의 1의 값, 즉 0이 아닌 값의 의미는, 상기 도 2와 같이 상기 Tanner 그래프 상에서 상기 변수 노드 xi와 j번째 검사 노드 사이에 선분(edge)이 존재함을 의미한다. 상기 LDPC 부호의 Tanner 그래프에서 변수 노드 및 검사 노드의 차수(degree)는 각 노드들에 연결되어 있는 선분의 개수를 의미하며, 이는 상기 LDPC 부호의 패리티 검사행렬에서 해당 노드에 대응되는 열 또는 행에서 0이 아닌 원소(entry)들의 개수와 동일하다. 예를 들어 상기 도 2에서 변수 노드들 x1(202), x2(204), x3(206), x4(208), x5(210), x6(212), x7(214), x8(216)의 차수는 각각 순서대로 4, 3, 3, 3, 2, 2, 2, 2가 되며, 검사 노드들(218, 220, 222, 224)의 차수는 각각 순서대로 6, 5, 5, 5가 된다. 또한 상기 도 2의 변수 노드들에 대응되는 상기 도 1의 패리티 검사 행렬 H1의 각각의 열에서 0이 아닌 원소들의 개수는 상기한 차수들 4, 3, 3, 3, 2, 2, 2, 2와 순서대로 일치하며, 상기 도 2의 검사 노드들에 대응되는 상기 도 1의 패리티 검사 행렬 H1의 각각의 행에서 0이 아닌 원소들의 개수는 상기한 차수들 6, 5, 5, 5와 순서대로 일치한다. LDPC 부호의 노드에 대한 차수 분포를 표현하기 위하여 차수가 i인 변수 노드의 개수와 변수 노드 총 개수와의 비율을 fi라 하고, 차수가 j인 검사 노드의 개수와 검사 노드 총 개수와의 비율을 gj라 하자. 예를 들어 상기 도 1과 도 2에 해당하는 LDPC 부호의 경우에는 f2=4/8 , f3=3/8 , f4=1/8 , i ≠ 2,3,4 에 대해서 fi=0 이며, g5=3/4 , g6=1/4 , j ≠ 5,6 에 대해서 gj=0 이다. LDPC 부호의 길이를 N, 즉 열의 개수를 N이라 하고, 행의 개수를 N/2이라 할 때, 상기 차수 분포를 가지는 패리티 검사 행렬 전체에서 0이 아닌 원소의 밀도는 다음 수학식 1과 같다. 여기서 N이 증가하게 되면 패리티 검사 행렬 내에서 1의 밀도는 계속해서 감소하게 된다. 일반적으로 LDPC 부호는 부호 길이 N에 대하여 0이 아닌 원소의 밀도가 반비례하며, 따라서 N이 큰 경우에는 매우 낮은 밀도를 가지게 된다. LDPC 부호의 명칭에서 저밀도(low-density)란 말은 이와 같은 이유로 유래되었다. LDPC 부호를 실제 통신 시스템에 적용하기 위해서는 부호의 전송 효율을 높이기 위해 고차 변조 방식과 결합하는 방법에 대한 연구가 선행되어야 한다. 고차 변조 방식에서는, 변조된 심볼(symbol)을 구성하는 각 비트들은 서로 다른 신뢰도(reliability)를 가지는데, LDPC 부호의 변수 노드를 신뢰도가 낮은 비트와 높은 비트들에 사상(mapping)시키는 방법에 따라서 LDPC 부호의 성능이 크게 변할 수 있다. 기존에는 국내 특허출원 10-2005-0020750호 "저밀도 패리티 검사 부호를 사용하는 통신 시스템에서 채널 인터리빙/디인터리빙 장치 및 그 제어 방법" 및 10-2005-0064364호 "저밀도 패리티 검사 부호를 사용하는 통신 시스템에서 채널 인터리빙/디인터리빙 장치 및 그 제어 방법"에 기재된 바와 같이 LDPC 부호의 변수 노드와 검사 노드의 차수에 따라 사상 방식을 결정하는 방법이 있었다. 그런데 이러한 방법은 특정 형태를 가지는 LDPC 부호의 성능은 개선할 수 있으나 일반적인 LDPC 부호의 성능은 개선되지 않거나 오히려 열화(degradation) 된다는 단점이 있다. 구체적으로, 10-2005-0020750호에서는 채널 인터리버/디인터리버를 사용하여 변조 심볼에서 낮은 신뢰도를 가지는 비트에 차수가 높은 변수 노드를 할당하고, 높은 신뢰도를 가지는 비트에 차수가 낮은 변수 노드를 할당하는 방법을 적용하였다. 일반적으로 LDPC 부호는 차수가 높은 변수 노드일수록 반복 복호 과정을 통해 차수가 낮은 변수 노드에 비하여 오류정정능력이 우수하기 때문에 오류 확률(error probability)이 감소하는 특성이 있다. 즉, 차수가 높은 변수 노드일수록 채널 오류에 강한(robust) 특성을 가진다. 상기 10-2005-0020750호에서는 이러한 특성을 이용하여 변조 심볼에서 신뢰도가 낮은 비트를 채널 오류에 강한 변수 노드에 할당하면 충분히 오류를 정정할 수 있을 것이라 예상하고 상기의 채널 인터리빙/디인터리빙 방식을 제안하였다. 하지만, 이러한 성질은 특수한 부호율과 구조를 가지는 LDPC 부호에만 국한되며 일반적으로는 성립하지 않는다. 즉, 변수 노드의 차수가 높다 하여도 채널 오류에 강한 정도가 모든 LDPC 부호들에 대해 같지 않기 때문에 LDPC 부호의 일반적인 채널 인터리빙 방식으로 적합하지 않다. 10-2005-0064364호에서는 상기 10-2005-0020750호에서 발생한 문제점을 극복하기 위해 보다 개선된 채널 인터리빙/디인터리빙 방식을 제안하였다. LDPC 부호의 검사 노드의 차수에 따라서 검사 노드의 차수가 사전에 정해 놓은 어떤 값 보다 작으면 상기 10-2005-0020750호와 같은 채널 인터리빙/디인터리빙 방식을 적용하고, 정해 놓은 어떤 값 보다 크거나 같으면 상기 10-2005-0020750호와 상반된 방식, 즉, 차수가 높은 변수 노드에 변조 심볼 내에서 높은 신뢰도의 비트를 할당하고 차수가 낮은 변수 노드에 낮은 신뢰도의 비트를 할당한다. 상기 10-2005-0064364호에서 제안된 방법은 상기 10-2005-0020750호에서 제안된 방법의 허점을 보완하였으나 특수한 형태의 LDPC 부호에 국한하여 성능이 개선된다는 문제점을 여전히 가지고 있다. 최적의 성능을 제공하는 LDPC 부호는 부호율에 따라서 패리티 검사행렬이 매우 상이한 구조를 가진다. 부호율에 따라 차수가 1인 변수 노드들이 사용되기도 하며, 부호율을 증가시키기 위하여 패리티를 천공(puncturing)하는 터보 부호와는 달리 정보어를 천공하여 전송하지 않기도 한다. 상기 10-2005-0020750호 및 10-2005-0064364호에서 제안된 채널 인터리빙/디인터리빙 방식은 다양한 구조를 가지는 LDPC 부호를 고려하지 않았기 때문에 상기 LDPC 부호의 채널 인터리빙/디인터리빙 방식으로는 많은 허점이 있다. 따라서 고차 변조 방식을 적용한 LDPC 부호에 적합한 채널 인터리빙/디인터리빙 방식을 도출하기 위해서는 부호율과 LDPC 부호의 구조를 동시에 고려하는 새로운 연구가 필요하다.