낮은 복잡도를 가지는 고속의 ＱＣ－ＬＤＰＣ 부호의 부호화 장치 및 방법 document_id A220623106444

일반적으로 유무선 통신 시스템이 디지털 시스템으로 발전하면서 송/수신되는 데이터는 부호화되어 전송된다. 이러한 부호화 방식들은 다양한 방면으로 발전하고 있으며, 순방향 오류 정정(FEC) 부호들을 이용하여 수신단에서 송신기로부터 전송된 데이터에 오류가 존재하여도 정정할 수 있는 부호화 방식들이 주류를 이루고 있다. 특히 무선 통신 시스템과 같이 무선 채널 환경에서 데이터의 오류가 빈번하게 발생하는 환경에서는 채널 부호화 방법으로 순방향 오류 정정 부호화 기법이 더욱 필요하게 되었다. 이러한 순방향 오류 정정 부호화 기법으로는 컨볼루션 코드와 터보 코드 및 LPDC 부호화 방법 등이 있고, 이중 현재 가장 주목받고 있는 부호화 방식으로 LDPC 부호화 방법이 있다. LDPC 부호화 방법은 Gallager에 의해 도입된 부호이다. LDPC 부호는 극소수의 원소들이 1의 값을 가지며, 나머지인 대부분의 원소들은 0의 값을 갖는 패리티 검사 행렬로 정의된다. LDPC 부호는 균일(regular) LDPC 부호와 비균일(irregular) LDPC 부호로 대별된다. 균일 LDPC 부호는 Gallager가 제안한 LDPC 부호로서, 패리티 검사 행렬내의 모든 행들은 동일한 개수의 1을 원소로 가지며, 모든 열들도 동일한 개수의 1을 원소로 갖는다. 이와는 달리, 비균일 LDPC 부호의 패리티 검사 행렬에는, 서로 다른 개수의 1을 포함하는 행들이 존재하거나, 서로 다른 개수의 1을 포함하는 열들이 존재한다. 일반적으로 비균일 LDPC 부호의 오류 정정 성능이 균일 LDPC 부호보다 우수하다고 알려져 있다. LDPC 부호화 방법을 간략히 살펴보면, 우선 시스테메틱(systematic)한 방식으로 부호화가 이루어진다는 것을 전제로 한다. 즉 패킷(packet)의 일부분은 입력된 비트(bit)와 동일한 형태로 출력되고, 패킷의 나머지 부분은 부호 검사 비트(parity bit)에 해당하는 부가정보가 이어서 붙여져 나가는 형태를 띠는 것이다. 따라서 입력신호가 부호화 기능을 담당하는 블록에 모두 입력이 되어야 부호화 작업이 이루어진다. 또한 부호율에 따라 패리티 비트(parity bit)가 전체 패킷(packet)에 해당하는 비율은 다르다. 따라서 H 행렬 에 의해 부호율은 고정이 되어있다. 그러면 도 1을 참조하여 부호화가 이루어지는 과정을 LDPC의 예를 들어 살펴보기로 한다. 도 1은 LPDC 부호화 방법의 개념을 설명하기 위한 블록 구성도이다. LDPC 부호는 선형 블록 부호로서, 기본적인 부호화는 생성행렬과 정보벡터의 곱으로 수행된다. 즉, 도 1에서 LDPC 부호화 되어 출력되는 부호어(codeword)(100)는 전송하고자 하는 정보(Information)(110)와 생성 매트릭스(Generator matrix)(120)의 행렬 곱의 형태로 표현된다. 또한 여기서 생성 매트릭스(120)는 패리티 매트릭스(122)를 포함하고 있다. 또한 LDPC 부호의 특징은 부호어(100)와 생성 매트릭스(120)의 패리티 매트릭스(122)의 곱은 영(zero) 행렬을 갖는 특성을 갖는다. 따라서 패리티 검사행렬을 이용하여 연관된 생성행렬을 구할 수 있다. 하지만 LDPC 부호의 부호화를 수행할 경우에는 일반적으로 복잡도로 인하여 위와 같은 방식으로 수행하지 않는다. 그 이유는 LDPC부호의 특징 중에 하나가 패리티 검사행렬(122)이 sparse한 형태를 가진다는 점 때문이다. 이러한 형태의 패리티 검사행렬(122)을 가지고 생성행렬(120)을 구해보면 생성행렬(120)의 많은 원소들이 1을 가지는 것을 알 수 있다. 1이 많다는 것은 부호화를 할 때 그만큼 정보벡터의 원소들과 연산을 많이 해야 된다는 것을 의미하고, 이를 처리하기 위한 하드웨어 복잡도가 증가한다는 뜻이다. 반대로 0이 많으면 해당 위치의 정보벡터 원소는 고려할 필요가 없어 복잡도 문제가 발생하지 않는다. 따라서 LDPC 부호의 부호화를 선형블록 부호와 같이 수행하게 되면 큰 복잡도를 유발되는 문제를 어느 정도 해결하기 위해 부호화를 수행할 때 생성 행렬(120)을 사용하지 않고 패리티 검사행렬(122)을 기반으로 하여 부호화를 수행할 수 있다는 것이다. 또한 생성 행렬(120)의 형태를 기준으로 하여 시스테메틱(systematic) 또는 넌시스테메틱(non-systematic) 생성 행렬(120)로 나눌 수 있다. 시스테메틱 생성 행렬의 역할은 정보벡터와 생성행렬을 곱하였을 때 얻어지는 부호어의 일정 부분이 정보 벡터와 동일하게 만들어 주는 것이다. 즉 부호어에 정보 벡터가 그대로 나타난다는 점이다. 반대로 넌시스테미틱(non-systematic) 생성 행렬은 부호어에 정보벡터가 나타나지 않는다. 이와 같이 부호어의 일정부분에 정보벡터가 나오게 하려면 systematic 생성행렬의 특정부분에 항등(identity) 행렬을 넣어주면 간단히 해결된다. 이를 수학식으로 도시하면, 하기 003c#수학식 1003e#과 같이 도시할 수 있다. 여기서 정보벡터(m)와 생성행렬(G)이 곱해져서 부호어(U)가 구해진다. 시스테메틱 생성 행렬은 이와 같이 일정부분은 P와 같은 부행렬(형태에 구속받지 않음, 어떤 행렬도 가능)로 되어 있고 나머지 일정부분은 정보벡터의 사이즈만큼 정방부행렬인 항등(identity) 행렬로 되어 있다. 이와 같이 항등 행렬이 뒤에 있으면 부호어의 뒷부분에 정보벡터가 보일 것이며 앞부분이 패리티 비트가 된다. 만약 P와 항등 행렬의 위치를 바꾸게 되면 앞부분에 정보벡터가 보일 것이며 뒷부분이 패리티 비트가 된다. 패리티 검사 행렬을 사용하는 경우 가장 쉽게 생성할 수 있는 방법으로 패리티 검사 행렬을 쉽게 생성하기 위한 형태로 가우시안 소거법(gaussian elimination)을 이용하여 패리티 검사 행렬을 생성하는 방법이 있다. 이러한 가우시안 소거법은 알 수 없는 값이 하나이며, 이를 방정식을 이용하여 풀이하는 방법으로 패리티 검사 행렬을 생성하는 기법이다. 그런데, 이와 같이 가우시안 소거법을 이용하는 경우에 소거 시에 많은 수의 방정식들을 계산해야 하므로, 많은 복잡도를 유발시킨다. 이를 해소하기 위한 LDPC 부호화 방법으로 리차드슨(Richardson) 부호화 방법이 있다. 리차드슨 부호화 방식은 LDPC 부호의 패리티 검사행렬을 블록화해서 나누고 연관된 행렬 방정식들을 통하여 패리티 비트들을 생성하는 기법으로서 H 행렬을 6개로 세분화하여 sub 행렬로 나눈 뒤 행렬의 연립 방정식으로 입력 벡터(vector)가 주어지면 출력 패리티 비트(parity bit)를 생성한다. 이와 같은 리차드슨 부호화 방식은 근사적 저밀도의 삼각형(approximate lower triangular) 형태이기만 하면 그 형태 내에서 각 행렬 원소들이 어떤 값을 가지든 간에 부호화를 수행할 수 있다. 즉, 리차드슨 부호화 방식은 approximate lower triangular 형태의 랜덤 패리티 검사 행렬에만 사용할 수 있다는 제약이 있다. 다음으로, Fossorier에 의해 제안된 QC-LDPC 부호화 방법에 대하여 살펴보기로 한다. QC-LDPC 부호화 방법은 준순환 매트릭을 이용하는 방식이다. 그러므로 먼저 순환 매트릭에 대하여 살펴보기로 한다. 순환 매트릭은 도 2에 도시한 바와 같은 NXN 정방 행렬에서 각 열에 하나씩의 1이 존재하며, 하나씩의 1은 각각 1비트씩 쉬프트될 수 있음을 의미한다. 도 2는 NXN 정방 행렬을 순환 매트릭으로 구성한 경우의 예를 도시한 도면이다. 먼저 A0(210)는 4X4의 정방 행렬로, 대각선에만 1이 존재하는 단위 행렬이며, A1(220)의 정방 행렬은 A0(210) 행렬의 1의 위치가 모두 오른쪽을 1씩 쉬프트되어 있는 정방 행렬이며, A2(230)의 정방 행렬은 A1(220) 행렬의 1의 위치가 다시 오른쪽으로 1씩 쉬프트되어 있는 정방 행렬이고, A3(240)의 정방 행렬은 A2(230)의 위치가 다시 오른쪽으로 1씩 쉬프트되어 있는 정방 행렬이다. 또한 A-(200)는 4X4 정방 행렬의 값이 모두 "0"인 영 행렬이다. Fossorier가 제안한 QC-LDPC 부호화 방법은 패리티 검사 행렬의 원소를 GF(2) 상의 원소인 0, 1이 아니라 순환 이동(cyclic shift)된 단위 행렬(identity matrix) 및 0 행렬로 나타내는 준 순환(Quasi-cyclic) LDPC 부호를 제안하였다. IEEE 802.16e나 802.11n에 채택된 LDPC 부호는 비균일 형태의 준순환 LDPC 부호이며, 패리티 비트 부분은 블록 타입의 이중 대각행렬(dual diagonal) 형태를 가진다. 도 3은 QC-LDPC 부호화를 수행하기 위한 이중 대각 행렬 구조를 가지는 패리티 검사 매트릭스의 구성과 부호어와의 관계도이다. 앞에서 설명한 바와 같이 부호어(330)는 두 부분으로 구성된 패리티 검사 매트릭스(310, 320)와 곱을 취하는 경우 영행렬(340)이 된다. 여기서 두 부분의 패리티 검사 매트릭스(310, 320) 중 뒤쪽(320)은 이중 대각 행렬 구조를 가지는 형태이다. 이러한 구조를 이용하여 QC-LDPC 부호화를 수행하기 때문에 실제로 구현 시 복잡도가 증가하게 된다. 또 다른 방식으로 Zongwang Li 등이 제안한 방식이 있다. 이 방식은 QC-LDPC 부호의 패리티 검사 행렬을 이용하여 얻은 생성 행렬과 정보 비트들과의 행렬 곱셈 연산을 순차적인 두 단계로 나누고 각 단계를 cyclic shift-register로 구현한 부호기를 통하여 패리티 비트들을 생성하는 기법을 제시하고 있다. 그러나 순환 쉬프트 레지스터를 이용함으로써 대기 시간이 길어지는 문제가 있다.