직렬 부호화를 위한 저밀도 패리티 검사 부호의 생성 장치및 방법 document_id A220623036889

차세대 이동통신 시스템에서는 데이터 전송시 필요한 고성능의 채널 부호가 필요하여 반복 복호를 통한 이진 오류 확률 성능이 우수한 저밀도 패리티 검사 부호의 연구 개발이 진행중이다. 이 저밀도 패리티 검사 부호는 패리티 검사 행렬 에 의해 정의되는데 이 행렬의 특성에 따라 부호의 성능이 결정된다. 따라서 우수한 특성을 가진 행렬 의 생성 방법은 최근 채널 부호 분야에서 큰 이슈로 연구되고 있다. 저밀도 패리티 검사 부호를 규격으로 사용하고자 하는 차세대 이동통신 시스템은 IEEE(Institute of Electrical and Electronics Engineers) 802.16e 및 IEEE 802.11n 등이 있다. 통신시스템은 정보를 보내고자 하는 송신단과 보낸 정보가 어느 정도 손실과 왜곡이 있어도 본래 정보를 복원하는 수신단으로 구성된다. 도 1은 디지털 통신 시스템의 송신단 및 수신단 구조의 개념도이다. 입력기(100)에 정보가 입력되었을 때 그 극 값을 벡터 형태로 라고 한다. 이때 정보 가 채널이라는 환경에 의해 왜곡이나 변형이 생길 경우를 대비해서 부가 정보를 더 추가하여 수신단에서 오류를 정정할 수 있도록 하는데, 이러한 수단으로서 채널 부호를 사용한다. 채널부호기(102)가 벡터 형태의 신호 를 신호 로 채널 부호화한다. 그리고 변조기(104)가 채널 부호화된 신호 를 높은 주파수의 전송 주파수에 실어 신호 으로 변조한다. 그리고 변조된 신호 이 안테나 등의 송신기(106)를 거쳐 신호 로 변환되어 채널로 송신된다. 여기서 입력기(100)에서 송신기(106)까지의 구성이 통신 시스템의 송신단이 된다. 채널(108)을 통과해서 오는 신호를 복원하는 수신단은 송신단의 역과정으로 구성된다. 수신 안테나와 같은 수신기(110)에서 채널(108)을 통과한 신호 을 수신하고, 수신기(110)를 통해 수신한 신호 을 복조기(112)를 통해 높은 주파수대의 신호에서 원하는 신호 로 복원한다. 그리고 채널 부호의 복호 방법에 따른 오류 정정을 이용해 채널복호기(114)가 원하는 정보 를 유추하게 된다. 그리고 출력기(116)를 통해 유추된 신호를 출력한다. 위의 디지털 통신 시스템의 송신단에서 사용되는 저밀도 패리티 검사 부호는 선형 부호의 일종으로 패리티 검사 행렬에 있어서 '0'이 아닌 원소의 개수가 '0'의 개수에 비해 상대적으로 적은 부호로 정의된다. 이 부호는 1960년대 초 갈라거(Gallager)에 의해 제안되었고 1990년대 후반 반복 복호가 가능한 부호의 관심과 더불어 재발견되어서 현재 여러 분야에서 연구가 수행되고 있다. 저밀도 패리티 검사 부호의 연구는 크게 부호의 생성에 관한 알고리즘과 복호에 관한 알고리즘으로 나뉜다. 반복 복호가 가능한 다른 예인 터보 부호(Turbo Code)와 비교할 때 저밀도 패리티 검사 부호는 복호의 복잡도가 상대적으로 낮다는 장점을 가지는 반면, 부호화가 어렵다는 단점을 가진다. 따라서 이러한 단점을 극복하기 위해 주로 부호화가 간단하거나 부호의 오류 정정 성능이 좋은 저밀도 패리티 검사 부호의 설계에 대한 연구가 활발하게 이루어지고 있다. 저밀도 패리티 검사 부호의 구조를 용이하게 기술하기 위해서 저밀도 패리티 검사 부호를 패리티 검사 행렬 로 표현한다. 한편, 패리티 검사 행렬 를 이분그래프(Bipartite Graph)로 표현할 경우에는 패리티 검사 행렬 의 행을 체크 노드(Check Nodes)에 대응시키고, 패리티 검사 행렬 의 열을 변수 노드(Variable Nodes)에 대응시키며, 행렬 안에서 '0'이 아닌 원소는, 해당 원소의 체크 노드와 변수 노드 간의 선(Edge)에 대응시켜 표현한다. 본 발명에서는 패리티 검사 행렬 의 행, 열 및 0이 아닌 원소를 이분그래프의 체크 노드, 변수 노드, 선과 같은 의미로 사용한다. 패리티 검사 행렬 를 이분그래프로 표현하는 경우, 일반적으로 패리티 검사 행렬 는 각 변수 노드 및 체크 노드들의 차수값이 어떻게 분포되는지와 각 변수 노드와 각 체크 노드 사이에 선들을 어떻게 배치하는가에 의해 정의되며, 이러한 2가지 사항에 의해 패리티 검사 행렬 의 생성 방법이 결정된다. 여기서 차수값이란, 각 변수 노드 또는 각 체크 노드에서 연결된 선의 개수를 의미한다. 즉 임의의 변수 노드에 있어서 그 변수 노드에 연결되어 있는 선이 2개이면 그 변수 노드의 차수는 2가 된다. 패리티 검사 행렬 는 일반적인 이진 부호의 경우에는 '0'과 '1'로만 구성된다. 패리티 검사 행렬 의 생성시, 먼저 밀도 진화 함수를 통해 각 변수 노드들의 차수를 정하고나서 '1'의 원소를 배치한다. 즉 선을 연결한다. 여기서 '1'의 원소를 배치하는 알고리즘으로서 PEG(Progressive Edge Growth) 알고리즘이 대표적이다. 이 알고리즘은 서브 그래프 상에서 변수 노드를 순서대로 추가해 가면서 선들을 연결하는데, 하나의 선을 연결하고 나서 이때 만들어지는 트리 구조에서 그 변수 노드를 지나는 사이클(Cycle)이 가장 크게 되도록 하는 선을 선택하여 연결한다. 여기서 사이클은 노드에서 출발하여 연결된 선들이 처음 출발한 노드로 들어오는 일련의 선들을 의미한다. 그리고 사이클의 길이는 사이클을 구성하는 선들의 개수를 의미한다. 이러한 사이클 개념을 이용하여, 작은 크기의 부호에서 되도록 큰 사이클을 가지도록 선들을 연결함으로써 부분 거스를 키울 수 있다. 여기서 거스는 여러 사이클들 중에 길이가 가장 짧은 사이클의 길이를 의미한다. 이 외에도 '1'을 배치는 방법으로는, 짧은 사이클이 생성되는 경우에 외부로 연결되는 선이 많도록 연결하는 ACE(Approximate Cycle Extrinsic) 알고리즘이 있다. 이처럼 기존의 PEG 알고리즘이나 이와 유사한 방법은 부분 싸이클의 길이가 커지도록 패리티 검사 행렬 를 생성하는 것을 목표로 한다. 기존의 방법으로 패리티 검사 행렬 를 생성할 경우 랜덤(Random)하게 생성한 것보다 사이클 특성이 좋아지며, 이는 합곱 알고리즘(Sum-Product Algorithm)을 사용하는 경우 메시지 간의 독립성이 초반 반복수에서 보장되기 때문에 부호 성능을 향상시킬 수 있게 된다. 한편, 복호 알고리즘은 변수 노드와 체크 노드처럼 두가지 종류의 노드로 구분하되 같은 변수 노드들 끼리 혹은 같은 체크 노드들 끼리는 연결하지 않고, 변수 노드와 체크 노드들 간에 서로 선으로 연결하는 이분 그래프 상에서 정의될 수 있다. 이때 병렬 복호인 플러딩 일정계획법(Flooding Scheduling)이 적용될 수 있다. 그러나 실제 복호 알고리즘을 구현하는데 있어서 병렬 복호는 복호가 복잡하다는 점에서 단점이 있으며, 상대적으로 복호가 덜 복잡한 직렬 복호의 방법을 사용한다. 이러한 단점은 몇 개의 부분 그래프로 나눈 복호를 사용시 일반 PEG 알고리즘으로 생성하는 경우 변수 분할에서 얻어지는 정보가 다음 부분 집합에서 얻는 정보 반영이 안되거나 적을 수 있기 때문이다. 따라서 직렬 복호를 고려하여 패리티 검사 행렬 를 설계한다면, 직렬 복호시에 복호화 성능의 향상을 기대할 수 있다.