KR101405962B1

KR101405962B1 - Ｌｄｐｃ 코드를 이용한 복호화 방법

Info

Publication number: KR101405962B1
Application number: KR1020080018116A
Authority: KR
Inventors: 정지욱; 이석우; 오민석
Original assignee: 엘지전자 주식회사
Priority date: 2008-02-28
Filing date: 2008-02-28
Publication date: 2014-06-12
Anticipated expiration: 2028-02-28
Also published as: US20110010602A1; WO2009108025A3; WO2009108025A2; KR20090092892A; US8347170B2

Abstract

본 발명은 저밀도 패리티 검사(LDPC: Low Density Parity Check) 코드를 이용한 복호화 방법에 관한 것이다. 본 발명의 일 양상에 의한 LDPC 코드를 이용한 복호화 방법은, 패리티 검사 행렬을 이용하여 부호화된 코드워드를 복호화하는 방법에 있어서, 상기 코드워드를 상기 패리티 검사 행렬을 이용하여 복호화하는 단계를 포함하되, 상기 패리티 검사 행렬은 각각 기본 패리티 검사 행렬의 특정 행으로부터 배타적으로 분리된 적어도 하나 이상의 행(row)을 포함하는 다수의 레이어들을 포함하는 것을 특징으로 한다.

복호화, 병렬 처리, 패리티 검사 행렬, 행 분할

Description

ＬＤＰＣ 코드를 이용한 복호화 방법{Method of performing decoding using LDPC code}

본 발명은 복호화(decoding) 방법에 관한 것이다. 보다 구체적으로는, 저밀도 패리티 검사(LDPC: Low Density Parity Check) 코드를 이용한 복호화 방법에 관한 것이다.

최근에 LDPC 코드를 이용한 부호화 방법이 부각되고 있다. LDPC 코드는 패리티 검사 행렬(parity check matrix) Η의 원소들의 대부분이 0이어서 저밀도(low density)인 선형 블록 부호(linear block code)로서 1962년 갤러거(Gallager)에 의해 제안되었다. LDPC 부호는 매우 복잡하여 제안 당시의 기술로는 구현이 불가능하였기 때문에 잊혀져 있다가 1995년에 재발견되어 성능이 매우 우수함이 입증된 이래로 최근에 그에 관한 연구가 활발히 진행되고 있는 상황이다. (참고문헌: [1] Robert G. Gallager, "Low-Density Parity-Check Codes", The MIT Press, September 15, 1963. [2] D.J.C.Mackay, Good error-correcting codes based on very sparse matrices, IEEE Trans. Inform. Theory, IT-45, pp.399-431(1999))

LDPC 코드의 패리티 검사 행렬은 1의 개수가 매우 적기 때문에 매우 큰 블록 크기에서도 반복 복호를 통하여 복호가 가능하여 블록 크기가 매우 커지면 터보 코드처럼 섀넌(Shannon)의 채널 용량 한계에 근접하는 성능을 보인다. 상기 패리티 검사 행렬에서 행(row) 또는 열(column)에 포함된 1의 개수를 무게(weight)라 한다.

LDPC 코드는 (n-k)×n 패리티 검사 행렬 Η에 의해 설명될 수 있다. 상기 패리티 검사 행렬 Η에 대응하는 생성 행렬(generator matrix) Ｇ는 다음의 수학식1에 의해 구할 수 있다.

ΗㆍＧ = 0

LDPC 코드를 이용한 부호화 및 복호화 방법에 있어서는 송신측에서 상기 패리티 검사 행렬 Η와 수학식 1의 관계에 있는 상기 생성 행렬 Ｇ를 이용하여 다음의 수학식 2에 의해 입력 데이터를 부호화 할 수 있다.

ｃ = Ｇㆍx (여기서, c는 코드워드(codework)이고, x는 정보 비트이다)

이하 종래 기술에 따라 상기 H 행렬을 이용하는 복호화 방법을 설명한다.

수신 단의 디코더(decoder)는 송신단의 부호화(Encoding) 결과인 코드워드(c)에서 정보 비트(x)를 구해야 하는데, Hc=0인 성질을 이용하여 찾아낸다. 즉, 수신된 codeword를 c'이라 할 때, Hc'의 값을 계산하여 결과가 0 이면, c'의 앞의 k개의 bit를 디코딩(decoding)된 정보 비트(information bit)로 결정한다. Hc'의 값이 0이 아닌 경우, 그래프(graph)를 통한 합 곱(sum-product) 알고리즘, 신뢰도 전파(belief propagation) 알고리즘 등을 사용하여, Hc'의 값이 0을 만족하는 c'를 찾아 x를 복구한다. 상기 검사식(Hc'=0는, 상기 정보 비트와 상기 G 행렬 간의 관계에 따라 c'H^T=0로 바뀔 수 있는바, 상기 검사식은 상기 정보 비트와 상기 G 행렬 간의 관계에 따라 변할 수 있다.)

도 1은 패리티 검사 행렬 H를 이분법 그래프(Bipartite graph)를 통해 나타낸 도면이다. 도 1에서, CNU는 검사 노드 유닛(Check Node Unit)을 나타내고, VNU는 비트 노드 유닛(Variable Node Unit)을 나타낸다. 이분법 그래프 상에서 알고리즘을 적용하여 복호화하는 과정은 크게 3개의 과정으로 설명될 수 있다.

1. 검사 노드(check node)에서 비트 노드(variable node)로의 확률값 갱신

2. 비트 노드에서 검사 노드로의 확률값 갱신

3. 비트 노드의 확률을 통한 복호값 결정

우선 상기 제1 과정을 수행하기 위해서, 채널로부터 수신된 확률 값이 입력되는 초기화(initialization)단계를 거쳐, 상기 검사 노드(check node)의 갱신(update)을 수행하는 제1 과정이 수행된다. 상기 제1 과정 수행 이후, 상기 비트 노드(variable node)에서 검사 노드(check node)로의 확률 값이 갱신되면 제2 과정이 수행된다. 상기 제1, 제2 과정을 수행한 이후, 상기 채널로부터 수신된 확률 값과 상기 제1 및 제2 과정을 통해 갱신된 확률 값을 이용하여 복호 값을 결정한다.

복호화 과정은 제1, 2의 과정을 거친 후 제3 과정에서 상기 결정된 복호 값(c')이 검사식 Hc'=0 을 만족하는 경우, 상기 값(c')을 정확히 수신된 복호값으 로 결정하고, 그렇지 않을 경우 일정한 횟수만큼 상기 검사식을 만족할 때까지 상기 제1, 2의 과정을 반복(iteration)하게 된다. 상기 제1, 2의 과정에서 이루어지는 확률 값의 갱신 과정은 패리티 검사 행렬의 각 행 혹은 열에 속한 영이 아닌(nonzero) 성분의 개수, 즉 1의 개수만큼 각각의 갱신과정을 반복하게 된다. 즉, 상기 패리티 검사 행렬 H의 무게(weight)에 해당하는 위치에서 상기 제1 과정의 갱신(check to variable update)과 상기 제2 과정의 갱신(variable to check update)이 수행된다. 상기 제1, 2의 과정을 반복할수록 검사 노드와 비트 노드간의 확률값의 신뢰도가 높아지고, 결과적으로 구하고자하는 코드워드(codeword)의 참값에 근접하게 된다.

최근에는 LDPC 부호화에 있어서, 상기 생성 행렬 Ｇ에 의하지 않고 상기 패리티 검사 행렬 Η를 이용하여 입력 데이터를 부호화하는 방법이 일반적으로 사용되고 있다. 따라서, 상기한 바와 같이, LDPC 코드를 이용한 부호화 방법에서는 상기 패리티 검사 행렬 Η가 가장 중요한 요소라 할 수 있다. 상기 패리티 검사 행렬 Η는 대략 1000×2000 이상의 크기를 갖기 때문에 부호화 및 복호화 과정에서 많은 연산이 요구되고, 구현이 매우 복잡하며, 많은 저장 공간을 요구하는 문제점이 있다.

본 발명은 상기한 바와 같은 종래기술을 개선하기 위해 제안된 것으로, 본 발명의 목적은 LDPC 코드를 이용한 복호화 시에 복호화 성능을 개선시키고 복호화 지연(latency)을 감소시킬 수 있는 복호화 방법을 제공하는 것이다.

본 발명의 일 양상에 의한 LDPC 코드를 이용한 복호화 방법은, 패리티 검사 행렬을 이용하여 부호화된 코드워드를 복호화하는 방법에 있어서, 상기 코드워드를 상기 패리티 검사 행렬을 이용하여 복호화하는 단계를 포함하되, 상기 패리티 검사 행렬은 각각 기본 패리티 검사 행렬의 특정 행으로부터 배타적으로 분리된 적어도 하나 이상의 행(row)을 포함하는 다수의 레이어들을 포함하는 것을 특징으로 한다.

본 발명에 따르면 LDPC 코드를 이용한 복호화 시에 복호화 성능을 개선시킬 수 있고, 효율적인 병렬처리가 가능하여 복호화 지연을 감소시킬 수 있는 효과가 있다.

이하에서 첨부된 도면을 참조하여 설명되는 본 발명의 실시예들에 의해 본 발명의 구성, 작용 및 다른 특징들이 용이하게 이해될 수 있을 것이다.

본 발명의 실시예들은 구조화된(structured) LDPC 부호화 및 복호화 방법을 전제로 하므로, 이하에서 구조화된 LDPC 부호화 및 복호화 방법에 대해 설명하도록 한다.

LDPC 코드를 사용하기 위해서는 패리티 검사 행렬을 사용한다. 전술한 바와 같이, 패리티 검사 행렬은 이진 행렬(binary matrix)로서 대부분의 원소(element)는 '0'이고, 일부는 '1'이다. 실제 부호화 또는 복호화에 사용되는 패리티 검사 행렬의 크기는 10⁵ 비트 이상이기 때문에 패리티 검사 행렬을 저장하기 위해 대용량의 메모리가 필요하다.

구조화된 LDPC 부호화 기법에서는 패리티 검사 행렬은 모델 행렬(model matrix)의 형식으로 저장된다. 모델 행렬은 각각 특정 서브 행렬(sub-matrix)을 지시하는 다수의 인덱스들(indexes)로 이루어진다. 즉, 각 서브 행렬은 일정 크기(z×z)의 행렬로서 특정 인덱스에 의해 표현된다. 부호화 또는 복호화 수행 시에 상기 모델 행렬의 각 인덱스를 그 인덱스가 지시하는 서브 행렬로 대체함으로써 패리티 검사 행렬로 확장되어 사용된다.

도 2는 모델 행렬의 일 예를 도시한 것이다. 도 2에서, 각 정수는 해당 서브 행렬의 인덱스를 의미한다. 예를 들어, 인덱스가 '-1'인 경우는 특정한 크기의 영 행렬(zero matrix)을 의미하며, 인덱스가 '0'인 경우는 특정한 크기의 단위 행렬(identity matrix)을 의미한다. '-1'과 '0'을 제외한 양의 정수인 인덱스는 해당 서브 행렬이 생성된 소정 규칙을 의미할 수 있다. 예를 들어, 양의 정수인 인덱스는 쉬프트 수(shift number)를 나타낸다. 즉, 각 서브 행렬이 단위 행렬의 각 행 또는 열을 일정 방향으로 쉬프트시켜 생성된 퍼뮤테이션 행렬이라고 할 경우, 상기 쉬프트 수를 해당 서브 행렬의 인덱스로 할 수 있다. 예를 들어, 서브 행렬을 '1'이라는 인덱스로 표현하는 경우, 해당 서브 행렬은 단위 행렬의 각 행 또는 열을 특정한 방향으로 한 칸(행 또는 열)씩 쉬프트함으로써 생성된 것이다. 모델 행렬 내에서 영 행렬인 서브 행렬을 표시하기 위해 아무런 인덱스를 사용하지 않을 수도 있다. 이하의 실시예들에 있어서는 영 행렬인 서브 행렬를 표시하기 위해서 인덱스를 사용하지 않을 수 있다.

도 3은 상술한 인덱스, 즉 쉬프트 수(shift number)에 따른 행렬의 표현 방법을 설명하기 위한 도면이다. 특정한 패리티 검사 행렬을 4×4 크기의 행렬(즉, 서브 행렬)로 구조화하여 표현하는 경우, '3'이라는 인덱스를 갖는 서브 행렬은 4×4 크기의 기본 퍼뮤테이션 행렬, 즉 단위 행렬의 각 열을 오른쪽으로 세 개의 열만큼 쉬프트시킴으로써 생성된 퍼뮤테이션 행렬이 된다.

부호화된 구조화된 LDPC 기법에 따라 각 서브 행렬을 하나의 인덱스로 표현한 모델 행렬을 저장하고 부호화 또는 복호화 시에 저장된 모델 행렬을 원래의 패리티 검사 행렬로 확장하여 사용함으로써 패리티 검사 행렬을 저장하기 위한 메모리 용량을 절약할 수 있다.

이하, 패리티 검사 행렬을 이용하여 LDPC 부호를 복호화하는 방법을 설명한다. 종래의 LDPC 부호의 복호화는 주로 패리티 검사 행렬의 다른 표현인 이분법 그래프 상에서 검사 노드와 비트 노드 사이의 확률 값의 갱신으로 신뢰도를 높이는 과정의 반복을 통해 이루어진다. 패리티 검사 행렬의 다른 표현인 이분법 그래프를 이용해 복호화하는 방법은, 갱신된 확률 값을 통해 코드워드(codeword)를 결정하게 되므로, 코드워드를 결정하게 되는 확률 값의 갱신 과정이 복호기(decoder)의 성능에 직접적인 영향을 미치게 된다.

신뢰도의 갱신 과정은 크게 검사 노드에서 비트 노드로의 확률 값 갱신 과정과 비트 노드에서 검사 노드로의 확률 값 갱신 과정으로 나누어 생각할 수 있다. 상기 검사 노드에서 비트 노드로의 확률 값을 갱신하거나, 상기 비트 노드에서 검사 노드로의 확률 값을 갱신하는 경우에는, 확률 값이 갱신되는 자신의 값을 제외한 같은 열(column)에 놓인 확률 값이나, 같은 행(row)에 놓인 확률 값을 사용하여 자신의 확률 값을 갱신한다. 이때, 사용하게 되는 확률 값은 얼마나 많이 갱신되었는가에 따라서 좀 더 신뢰도가 높은 결과, 즉 보다 긍정적인 영향을 복호기에 미치게 된다.

본 발명의 일 실시예는, LDPC 부호화된 수신 신호를 상기 패리티 검사 행렬을 이용하여 복호하는 경우에, 상기 패리티 검사 행렬의 행(row)의 묶음인 레이어(layer) 단위로 수신 신호를 복호화하는 방법(이하 'Layered decoding'이라 칭함)을 이용한다. 상기 Layered decoding은 비트 노드에서 검사 노드로의 확률 값을 갱신하는 경우, 패리티 검사 행렬의 같은 열 속에서 이미 갱신된 값이 있을 때, 그 갱신된 값을 사용하여 확률 값을 갱신하는 특징이 있다.

상기 Layered decoding은 LDPC 부호의 부호화 및 복호화에 사용하는 패리티 검사 행렬의 행을 여러 레이어(layer) 단위로 나누어 반복 복호하는 방법이다. 상기 레이어는 상기 패리티 검사 행렬의 행을 그룹화하여 구분하는 경우, 각각의 행의 그룹을 나타낸다. 즉, 패리티 검사 행렬의 행들을 몇 개의 그룹으로 묶을 때, 하나의 그룹을 레이어라 할 수 있다. 상기 레이어는 하나의 행일 수도 있다.

도 4는 레이어 단위로 구분된 모델 행렬을 나타내는 도면이다. 도시된 모델 행렬은 상기 Layered decoding 방법을 설명하기 위한 하나의 예로서, 도 4의 각 정수는 특정 서브 행렬을 지시하는 인덱스를 의미한다.

상기 Layered decoding은 패리티 검사 행렬 H의 같은 행에서의 신뢰도 갱신에 있어서, 모두 같은 정도의 갱신 과정을 거친 확률 값을 사용하여 신뢰도를 갱신한다. 즉, 종래의 LDPC 복호 방법과 같이 이분법 그래프 상에서 검사 노드와 비트 노드 간의 확률 값 갱신을 수행한다. 그러나, 비트 노드에서 검사 노드로 향하는 확률 값의 갱신 과정(즉, 상기 패리티 검사 행렬 H의 열의 확률 값 갱신 과정)에 있어서는, 레이어 단위로 확률 값이 갱신되며, 특정 레이어에 포함된 확률 값을 갱신하는 경우, 이미 갱신이 이루어진 레이어에 포함된 확률 값을 사용하는 특징이 있다. 상기 Layered decoding은, 레이어 단위로 복호화를 수행하는 바, 상기 패리티 검사 행렬에 포함된 레이어 전부에 대하여 확률 값이 갱신되면 LDPC 복호화를 위한 한 번의 반복(iteration)을 수행하는 것이 된다. 상기 Layered decoding은, 이미 하나의 레이어에 대하여 확률 값 갱신을 위한 연산을 수행하고 다음 레이어에 대하여 확률 값 갱신을 위한 연산을 수행하는 경우에, 상기 하나의 레이어에서 연산된 결과, 즉 신뢰도가 갱신된 메시지 결과를, 상기 다음 레이어의 연산에 사용함으로써, 좀 더 신뢰도가 높은 메시지를 복호 과정 즉, 확률 값 갱신 과정에 사용한다. 결국, 이러한 확률 값 갱신이 반복되는 경우, 좀 더 신뢰도가 높은 메시지가 확률 값 갱신에 사용되어, 검사 노드와 비트 노드 간의 확률 값의 신뢰도가 높아져 서, 복호기의 성능이 좋아지게 된다. 도 4의 행렬은 일반적인 모델 행렬이다. 도 4의 행렬은 Layered decoding 방법에 의하여 각각의 레이어를 순차적으로 복호 될 수 있는 바, 예를 들어 Layer 1 -> Layer 2 -> Layer 3 -> Layer 4 -> Layer 5 -> Layer 6 -> Layer 7 -> Layer 8 순서로 복호를 수행할 수 있다.

이하, 본 발명의 일 실시예에서 사용되는 복호화 시의 병렬처리의 기본 개념과 Layered decoding을 병렬처리 방식으로 수행하기 위한 전제 조건을 설명한다.

도 5a는 병렬처리(parallel processing)의 개념을 도식화하여 나타낸 도면이다. 병렬처리는 하나의 작업을 수행함에 있어서, 하나의 연산 장치가 처리하던 작업을 복수의 연산 장치가 나누어 처리하는 것을 의미한다. 병렬처리의 결과, 하나의 작업을 수행하는데 소요되는 시간이 병렬처리에 사용한 연산 블록의 수에 비례하여 감소하는 긍정적인 효과가 발생한다.

도 5b는 병렬처리에 따른 메모리 충돌(memory contention)의 개념을 나타내는 도면이다. 직렬 처리 방법의 경우 하나의 연산 유닛이 메모리 블록을 사용하므로 연산할 값을 읽어오거나 연산 결과를 저장함에 있어 문제가 발생하지 않는다. 하지만 여러 개의 연산 유닛이 동시에 작동하는 병렬처리 방법에 있어서는, 두 개 이상의 연산 유닛이 동시에 같은 위치의 메모리 블록에 접근(access)하려 하는 경우에 메모리의 충돌(collision)이 일어날 수 있다. 만약, LDPC 복호를 위한 확률 값 갱신 유닛들이 동시에 같은 위치의 메모리에 접근하는 경우 상기 메모리 충돌이 발생할 수 있다.

LDPC 복호화에 병렬처리 방법을 적용하기 위해서는 메모리 블록에 대한 동시 접근의 문제뿐만 아니라, 동시에 처리하고자 하는 데이터 사이의 의존성이 없어야 한다. 즉, 복수 개의 연산 블록들 중 어느 하나의 연산 블록의 출력 값이 동시에 다른 연산블록의 입력 값이 되어야 한다면, 동시에 처리하는 것이 아니라 그 의존성에 따라 순차적으로 연산을 해야 한다.

본 발명의 일 실시예는, 상기 특정한 레이어들에 대하여 병렬 처리 방식으로 데이터 처리를 수행하기 위하여 특정한 레이어들 사이에 중첩(되는 부분이 없는 패리티 검사 행렬을 제공한다. 본 발명의 일 실시예에 따른 패리티 검사 행렬은, 상기 패리티 검사 행렬의 특정 레이어의 영 행렬이 아닌 서브 행렬은 열 방향으로 서로 다른 위치에 존재한다. 즉, 특정한 레이어에 대해서는 상기 패리티 검사 행렬의 무게가 존재하는 위치가 열 방향으로 서로 다르게 된다.

전술한 바와 같이, 일반적인 LDPC 코드에 의한 복호는, 패리티 검사 행렬의 모든 행 내에서의 확률 값 갱신이 이루어지고, 이어서 각각의 모든 열에 대해 확률 값의 갱신이 이루어진다. 반면, 상기 Layered decoding은 각각의 행의 확률 값을 갱신할 때 미리 나누어 놓은 그룹 단위(즉, layer 단위)로 확률 값을 갱신한다. 이러한 복호 방법은 두 번째 이후의 그룹에 해당하는 확률 값을 갱신할 때에는, 이전의 그룹에서 이미 갱신된 보다 신뢰도가 높은 확률 값을 사용하여 계산함으로써, 복호 성능이 좋아지게 되는 것이다. 상기 Layered decoding에는 이러한 유리한 점이 있으나, 상기 종래의 패리티 검사 행렬을 특정한 레이어 단위로 구분하고 상기 특정한 레이어에 대하여 병렬 처리 방식으로 데이터를 처리하면, 상기 특정한 레이어의 병렬 처리 과정에서 상술한 메모리 충돌의 문제와 병렬처리하는 데이터 간의 의존성에 따른 문제 등을 피하기 위해, 동시에 하나의 레이어만을 처리해야 하므로 복호에 지연이 발생한다. 그러나, 본 발명의 일 실시예에서 제안하는 바에 따라, 특정한 레이어 간에 열의 무게가 존재하는 위치가 중첩되지 않도록 상기 패리티 검사 행렬을 설계한다면, 동시에 다수 개의 레이어에 대한 병렬처리를 할 수 있다.

이하에서 특정 레이어에 대하여 중첩되지 않는 패리티 검사 행렬을 이용하여 layered decoding을 병렬로 처리하는 방법을 설명한다.

도 6은 코드 레이트가 1/2인 경우의 모델 행렬의 일 예이다. 상기 예는, 도 6의 모델 행렬에 의해 생성되는 패리티 검사 행렬의 행을, 상기 모델 행렬에 대한 기본 퍼뮤테이션 행렬의 크기에 따라, 하나의 레이어로 그룹화한다. 즉, 상기 예는, 도 6의 모델 행렬과 상기 기본 퍼뮤테이션을 이용하여 생성되는 패리티 검사 행렬의 레이어가, 상기 기본 퍼뮤테이션 행렬의 행의 개수만큼의 행으로 이루어지는 경우의 일례이다. 결과적으로, 도 6에서 하나의 레이어에 포함되는 행의 개수는, 도 6의 모델 행렬에 따른 기본 퍼뮤테이션 행렬의 행의 개수와 동일하다. 도 6의 모델 행렬은, 효과적인 병렬처리를 위해 제안된 것이다. Layered decoding에 있어서, 도 6의 모델 행렬(base matrix)의 행의 순서(row order)를 (1 → 7 → 2 → 8 → 3 → 9 → 4 → 10 → 5 → 11 → 6 → 12)로 정하는 경우, 상기 모델 행렬의 임의의 두 행(예를 들어, 1번째 행과 7번째 행)에 대해서 서로 'non-zero' 성분(element)들은 임의의 열 방향으로 중첩하지 않는다. 상기 모델 행렬에서는, 임의의 두 행(예를 들어, 1번째 행과 7번째 행)에 대하여 0 이상의 쉬프수 수를 갖는 성분이 열 방향으로 중첩하지 않는다. 예를 들어, 여덟 번째 행은 두 번째 행 또는 세 번째 행과 비교했을 때 임의의 열 방향으로 0 이상의 쉬프수 수를 갖는 성분 서로 중첩하지 않는 것을 알 수 있다. 또한, 도 6의 모델 행렬에 의해 생성되는 패리티 검사 행렬을 기준으로 설명하면, 상기 모델 행렬의 하나의 행은 상기 생성된 패리티 검사 행렬의 하나의 레이어를 나타내는바, 상기 생성된 패리티 검사 행렬의 각각의 레이어 간에는 무게가 존재하는 위치가 열 방향으로 중첩하지 않는다.

도 7은 코드 레이트가 1/2인 경우의 모델 행렬의 또 다른 예이다. 도 7의 모델 행렬은 보다 효과적인 병렬처리를 위하여 제안된 것이다. 도 7의 모델 행렬은, 다음과 같은 두 행의 쌍(1, 7), (2, 8), (3, 9), (4, 10), (5, 11), (6, 12)에 대해서 0 이상의 쉬프수 수를 갖는 성분이 임의의 열 방향으로 중첩되지 않도록 디자인되었다.

이하에서는 패리티 검사 행렬을 이용한 복화화 과정에서 효율적인 병렬처리를 수행하기 위한 패리티 검사 행렬을 생성하는 방법에 대해 설명하도록 한다. 상기한 바와 같이, 다수의 레이어들에 대한 병렬처리를 수행하기 위해서는 상기 다수의 레이어들 상호 간에 열의 무게(weight)가 존재하는 위치가 중첩되지 않는 패리티 검사 행렬을 설계해야 한다. 이를 위해 본 발명의 일 실시예에서는 기본 모델 행렬의 적어도 하나 이상의 행을 둘 이상의 행들로 분리(split)하여 새로운 모델 행렬을 생성하되, 분리되는 행에서 열의 무게를 갖는 성분은 배타적으로 분리된다. 여기서, 무게를 갖는 성분이 배타적으로 분리된다 함은 분리된 이후의 두 행들의 대응하는 열들은 동시에 무게를 갖지 않도록 분리되는 것을 의미한다.

도 8a 내지 도 8d는 본 발명의 일 실시예에 따라 기본 패리티 검사 행렬의 적어도 하나 이상의 행을 적어도 둘 이상의 행들로 배타적으로 분리함으로써 복호화 시에 효율적인 병렬처리가 가능하도록 할 수 있는 패리티 검사 행렬 생성 방법을 설명하기 위한 도면들이다.

도 8a는 본 발명의 일 실시예에 따른 기본 패리티 검사 행렬의 일 예를 도시한 것으로서, 4×24의 차원(dimension)을 갖는다. 도 8b는 도 8a의 기본 패리티 검사 행렬의 각 행을 두 개의 행들로 분리하고 두 개의 행들을 별도로 추가함으로써 생성된 10×30 크기의 패리티 검사 행렬을 도시한 것이다. 도 8b에서 첫 번째 행 및 두 번째 행, 세 번째 행 및 네 번째 행, 다섯 번째 행 및 여섯 번째 행, 일곱 번째 행 및 여덟 번째 행은 각각 도 8a의 첫 번째 행, 두 번째 행, 세 번째 행 및 네 번째 힝이 분리되어 생성된 것이고, 도 8b의 아홉 번째 행 및 열 번째 행은 별도로 추가된 행들이다.

분리되는 행에서 열의 무게를 갖는 성분은 배타적으로 분리된다. 즉, 분리된 이후의 두 행들의 대응하는 열들은 동시에 무게를 갖지 않도록 분리된다. 보다 구체적으로 설명하면, 도 8a의 첫 번째 행에서 홀수 번째 무게를 갖는 성분들은 도 8b의 분리된 두 행들 중 첫 번째 행의 대응하는 열에 위치하고, 짝수 번째 무게를 갖는 성분들은 도 8b의 분리된 행들 중 두 번째 행의 대응하는 열에 위치하도록 분리된다. 도 8a의 첫 번째 행에서 무게를 갖지 않는 성분들(인덱스 '-1')의 경우, 도 8b의 분리된 두 행들의 대응하는 열들이 무게를 갖지 않도록 분리된다. 즉, 분리되기 전에 무게를 갖지 않는 성분에 대응하는 열은 분리된 후에도 무게를 갖지 않게 된다. 이하에서, 특정 행을 둘 이상의 행들로 분리하는 경우 분리되는 행의 열이 무게를 갖는 성분이 배타적으로 분리된다는 특징은 동일하게 적용된다.

또한, 분리된 두 행들의 패리티 부분에는 새로운 패리티 부분이 추가된다. 이때, 하나 이상의 행을 분리하여 새로운 패리티 검사 행렬을 생성하는 경우 새로 생성된 패리티 검사 행렬의 패리티 부분의 행과 열의 개수가 동일하게 되도록 새로운 패리티 부분이 추가된다. 예를 들어, 행의 분리에 의해 새로운 패리티 검사 행렬에 두 개의 행들이 추가되는 경우 패리티 부분에는 두 개의 열들을 갖는 추가 패리티 부분을 추가한다.

도 8c는 도 8b의 패리티 검사 행렬의 각 행을 두 개의 행들로 분리함으로써 생성된 20×40 차원의 새로운 패리티 검사 행렬의 일부를 도시한 것이다. 즉, 도 8c는 도 8b의 첫 번째 행 및 두 번째 행이 각각 두 개의 행들로 분리된 것을 도시한 것이다.

도 8d는 도 8c에 따라 생성된 패리티 검사 행렬의 각 행을 두 개의 행들로 분리함으로써 생성된 40×60 차원의 새로운 패리티 검사 행렬의 일부를 도시한 것이다. 도 8d는 도 8c에 도시된 네 개의 행들의 각각을 두 개의 행들로 분리하여 여덟 개의 행들을 생성한 것을 나타낸다.

도 8a 내지 도 8d에서, 도 8a의 첫 번째 행은, 도 8b, 도 8c 및 도 8d를 통해 설명된 바와 같이, 순차적인 분리 과정을 거쳐 총 여덟 개의 행들로 분리되었다. 이때, 도 8b의 첫 번째 및 두 번째 행들은 첫 번째 분리에 의해 생성된 행들로서 제1 검사 노드 세트(C_S1)라 하고, 도 8c의 첫 번째 내지 네 번째 행들은 두 번째 분리에 의해 생성된 행들로서 제2 검사 노드 세트(C_S2)라 하며, 도 8d의 첫 번째 내지 여덟 번째 행들은 세 번째 분리에 의해 생성된 행들로서 제3 검사 노드 세트(C_S3)라 하기로 한다. 이러한 과정을 일반화하여 기본 패리티 검사 행렬의 특정 행을 N번 반복하여 분리함으로써 생성된 행들을 제N 검사 노드 세트(C_SN)라 할 수 있다.

상기의 예에서 하나의 행을 분리하여 두 개의 행들을 생성하는 경우 분리되는 행의 열이 무게를 갖는 성분이 배타적으로 분리된다는 특징을 유지했기 때문에, 제N 검사 노드 세트(C_SN)에 속하는 연속하는 두 개의 행들을 하나의 그룹으로 하는 경우 특정 그룹에 속하는 임의의 행, 즉 임의의 검사 노드(check node)는 다른 그룹에 속하는 임의의 검사 노드와 충돌 문제를 발생시키지 않는다. 예를 들어, 도 8d에서, 두 개의 연속하는 행들(검사 노드들)을 하나의 그룹으로 하는 경우 총 네 개의 그룹들로 나눠지고, 첫 번째 그룹의 임의의 검사 노드는 다른 그룹의 임의의 검사 노드와 충돌 문제를 발생시키지 않는다.

패리티 검사 행렬을 이용한 복호화 과정에서 병렬적으로 복호화를 수행할 수 있는 프로세싱의 개수를 병렬 인자(parallel factor)라 할 경우, 도 8d에서 병렬 인자는 4가 된다. 다시 말해서, 네 개의 그룹들의 각각에 속하는 임의의 검사 노드에 대한 복호화 과정은 병렬적으로 동시에 처리할 수 있다. 각 그룹에 속하는 첫 번째 검사 노드를 '1'로 표시하고, 두 번째 검사 노드를 '0'으로 표시하는 경우 디코딩 프로세서(decoding processor)를 병렬적으로 처리하기 위해 스케쥴링할 수 있 는 경우의 수는 다음의 표 1과 같다.

제1그룹	제2그룹	제3그룹	제4그룹
0	0	0	0
0	0	0	1
0	0	1	0
0	0	1	1
0	1	0	0
0	1	0	1
0	1	1	0
0	1	1	1
1	0	0	0
1	0	0	1
1	0	1	0
1	0	1	1
1	1	0	0
1	1	0	1
1	1	1	0
1	1	1	1

상기한 바와 같이, 본 발명의 일 실시예에 따라 기본 패리티 검사 행렬의 행들을 분리함으로써 생성된 패리티 검사 행렬을 사용하여 복호화를 수행하게 되면 복호화 성능을 개선시킬 수 있을 뿐만 아니라, 효율적인 병렬처리가 가능하게 되어 복호화 지연을 감소시킬 수 있다.

이하, 본 발명에의 실시예에 따른 패리티 검사 행렬을 이용하여 복호화를 수행하는 복호기에 대해 설명한다. 도 9는 본 발명의 일 실시예에 따른 LDPC 복호기의 일 실시예를 나타내는 블록도이다. 상기 LDPC 복호기(1000)는 CNU(Check Node Update Unit) 블록(1100)과 제어 블록(1200)과 VNU(Variable Node Update Unit) 블록(1300)과 메모리 블록(1400)을 포함하여 이루어진다. 상기 CNU(Check Node Update Unit) 블록(1100)은 검사 노드의 확률 값 갱신(check node update)을 수행하며, 적어도 하나 이상의 CNU(Check Node Update Unit)(1110)를 구비한다. 상기 CNU(1110)는 상기 검사 노드의 확률 값 갱신을 수행하는 연산 유닛(processing unit)이다. 상기 제어 블록(1200)은, 상기 복호기(1000)의 각 유닛에 대한 동작을 제어하는 제어 유닛(1210)과, 패리티 검사 행렬의 구조에 따라 상기 CNU 블록(1100)과 상기 메모리 블록(1400)을 제어하는 CNU 라우팅 네트워크(1220)와, 상기 VNU 블록(1100)과 상기 메모리 블록(1400)을 제어하는 VNU 라우팅 네트워크(1230)와, 패리티 검사 행렬의 구조에 관한 정보 등을 저장하는 패리티 검사 행렬 인덱스 저장부(1240)와, 갱신된 확률 값을 이용하여 복호 값을 결정하고 결정된 복호 값을 검사하는 경판정부(Hard decision unit)(1250)를 포함한다. 상기 VNU(Variable Node Update Unit) 블록(1100)은 비트 노드의 확률 값 갱신(variable node update)을 수행하며, 적어도 하나 이상의 VNU(Variable Node Update Unit)(1310)를 구비한다. 상기 VNU(1310)는 상기 검사 노드의 확률 값 갱신을 수행하는 연산 유닛(processing unit)이다. 상기 제어블록(1200)에 의해 제어되는 CNU(1110)와 VNU(1310)는 상기 H 행렬의 0이 아닌 성분에 대하여 확률 값을 계산하여 갱신하는바, 상기 계산된 확률 값은 상기 메모리 부(1400)에 저장된다. 상기 메모리 부(1400)는, 검사 노드에서 비트 노드로의 확률 값 갱신을 위해 계산된 확률 값을 저장하는 R-메모리(1410)와, 비트 노드에서 검사 노드로의 확률 값 갱신을 위해 계산된 확률 값(예를 들어, 무선 채널로부터 수신되는 Log Likelihood Ratio 값)을 저장하는 수신 LLR 메모리(Received LLR memory)(1420) 및 비트 노드에서 검사 노드로의 확률 값 갱신을 위한 계산된 확률 값을 저장하는 Q-메모리(1430)를 포함한다.

상기 각각의 유닛을 설명하면 다음과 같다. 상기 수신 LLR 메모리(Received LLR memory)(1420)는 복호해야 하는 수신 신호에 대한 확률 값, 예를 들어 수신 신호의 코드워드(codeword)에 대한 LLR 값을 저장할 수 있는 메모리이다. 또한, 상기 R-메모리(1410)는 특정한 검사 노드에서의 확률 값 갱신(check node update)의 결과(

)를 저장하며, 상기 Q-메모리(1430)는 특정한 비트 노드에서의 확률 값 갱신(variable node update)의 결과(

)를 저장한다. 상기 제어유닛(1210)은 각 유닛의 동작 순서 및 각 유닛의 동작 타이밍을 제어하며, 상기 패리티 검사 행렬 인덱스 저장부(1240)는 상기 패리티 검사 행렬의 무게(weight)의 위치 등에 관한 정보를 저장한다. 또한, 상기 CNU 라우팅 네트워크(1220)는, 상기 패리티 검사 행렬 인덱스 저장부(1240)로부터 상기 패리티 검사 행렬에 관한 정보를 획득하여, 상기 CNU(1110)와 상기 메모리부(1400)의 메모리들을 적절히 연결한다. 또한, 상기 VNU 라우팅 네트워크(1230)는, 상기 패리티 검사 행렬 인덱스 저장부(1240)로부터 상기 패리티 검사 행렬에 관한 정보를 획득하여, 상기 VNU(1310)와 상기 메모리부(1400)의 메모리들을 적절히 연결한다. 상기 경판정부(1250)는, 상기 Q-메모리(1430)를 이용하여 복호 값을 결정하고, 상기 결정된 복호 값(c')을 검사하는 유닛으로, 상기 복호 값(c')이

의 검사식을 만족하는 경우 상기 복호 값(c')을 참값으로 출력하고, 만약 상기 검사식을 만족하지 못하는 경우 일정한 최대 반복 복호 횟수 이내에서 복호를 반복한다.

도 9의 복호기(1000)는 별도의 메모리(미도시) 또는 상기 패리티 검사 행렬 인덱스 저장부(1240)에 저장된 패리티 검사 행렬을 이용하여 수신 신호를 복호화하거나, 모델 행렬과 기본 퍼뮤테이션 행렬을 통해 생성된 패리티 검사 행렬을 이용하여 수신 신호를 복호화할 수 있다. 상기 모델 행렬과 기본 퍼뮤테이션 행렬을 통해 패리티 검사 행렬을 생성하는 경우, 상기 복호기(1000)는 상기 기본행렬과 기본 퍼뮤테이션 행렬을 저장하는 저장부(미도시)와 상기 기본행렬과 기본 퍼뮤테이션 행렬을 이용하여 상기 패리티 검사 행렬을 생성하는 패리티 검사 행렬 생성부(미도시)를 포함하는 것이 바람직하다. 또한, 도 9의 복호기(1000)는 패리티 검사 행렬의 행의 순서(예를 들어, layer의 순서)를 조정하여, 새로운 패리티 검사 행렬을 생성할 수 있다. 이 경우, 상기 복호기(1000)는 패리티 검사 행렬의 행의 순서를 조정하는 패리티 검사 행렬 조정부(미도시)를 포함하는 것이 바람직하다.

이하 상기 LDPC 복호기(1000)의 동작을 설명한다. 상기 LDPC 복호기(1000)는 LDPC 복호 알고리즘의 하나인 Log BP(Log Belief Propagation) 알고리즘을 이용하여 복호를 수행할 수 있다. 상기 복호기(1000)는 초기화 단계와, 검사 노드 갱신(check node update) 단계와 비트 노드 갱신(variable node update)단계 및 경 판정(hard decision) 단계에 따라 동작을 수행한다. 상기 초기화 단계는, 송신 측으로부터 전송되는 수신 신호에 대한 확률 값을 상기 수신 LLR 메모리(1420)에 저장하고, 상기 수신 LLR 메모리(1420)에 저장된 확률 값을 상기 패리티 검사 행렬 인덱스 저장부(1240)에 저장된 패리티 검사 행렬의 무게(weight)에 관한 정보를 이용하여 상기 Q-메모리(1430)의 특정위치에 저장하는 단계를 포함한다. 상기 검사 노드 갱신(check node update) 단계는, 상기 Q-메모리(1430)에 저장된 확률 값을 이용하여 검사 노드 갱신, 즉 검사 노드로부터 비트 노드로의 갱신을 수행하고, 그 결과를 상기 R-메모리(1410)에 저장하는 단계를 포함한다. 상기 비트 노드 갱신(variable node update) 단계는, 상기 R-메모리(1410)에 저장된 확률 값을 이용하여 비트 노드 갱신, 즉 비트 노드로부터 검사 노드로의 갱신을 수행하고, 그 결과를 상기 Q-메모리(1430)에 저장하는 단계를 포함한다. 상기 경 판정 단계는, 상기 Q-메모리(1430)에 저장된 확률 값을 이용하여 임시로 복호 값(c')을 결정하고, 상기 결정된 복호 값(c')을 검사하고, 검사 결과에 따라 상기 복호 값(c')이 참값인 경우 상기 참값을 출력하고, 만약 참값이 아닌 경우 특정한 반복 복호 횟수 이내에서 상기 검사 노드 갱신(check node update) 단계와 비트 노드 갱신(variable node update)단계를 반복하는 단계를 포함한다.

상기 복호기(1000)에서 사용하는 패리티 검사 행렬(H)이 상기 수학식 3과 같을 때, 상기 R-메모리(1410)와 상기 Q-메모리(1430)는 상기 패리티 검사 행렬의 0이 아닌 성분, 즉 1이 존재하는 성분의 위치의 값을 저장하는 역할을 한다. 따라서, 상기 R-메모리(1410)와 상기 Q-메모리(1430)는 다음과 같은 위치의 값을 저장하는 역할을 수행한다.

다만, 상기 R-메모리(1410)와 상기 Q-메모리(1430)는 상기 0이 아닌 성분의 위치에 해당하는 값만을 저장하면 되기 때문에, 도 10과 같은 구조로 상기 확률 값 갱신을 위한 연산의 결과를 저장할 수 있다. 따라서, LDPC 복호화를 위해 필요한 메모리는 H 행렬의 무게(weight)에 비례한다. 도 10에 도시된 패리티 검사 행렬의 무게(weight)에 관한 위치 정보는 상기 패리티 검사 행렬 인덱스 저장부(1240)에 저장된다. 상술한 바와 같이, 상기 복호기(1000)는, 모델 행렬과 기본 퍼뮤테이션 행렬을 이용하여 패리티 검사 행렬을 생성하여 복호화 작업을 수행하거나, 특정한 메모리에 저장된 패리티 검사 행렬을 이용하여 복호화 작업을 수행하거나, 임의의 방법에 의해 생성된 패리티 검사 행렬을 이용하여 복호화 작업을 수행할 수 있다. 이하, 설명되는 패리티 검사 행렬은 모델 행렬이 아닌, 실제 패리티 검사 행렬을 의미한다. 상기 패리티 검사 행렬이 생성되는 방법에는 제한이 없으며, 모델 행렬과 기본 퍼뮤테이션 행렬을 이용하여 생성되거나, 특정 메모리나 외부 장치에 저장된 패리티 검사 행렬을 획득하여 생성될 수 있다.

도 11은 상기 수학식 3의 패리티 검사 행렬을 이용하여 복호화를 수행하는 복호기의 CNU, VNU, 메모리의 연결 형태의 일례를 나타내는 도면이다. 도 11의 복호기는 4개의 CNU와, 8개의 VNU를 구비한 경우의 일례이다. 12a 내지 12h는 도 11에 도시된 복호기를 이용하여 복호화를 수행하는 경우, 수신 신호에 대한 확률 값 이 입력되는 초기화 과정에서 한 번의 반복 복호(one iteration)를 수행하는 과정까지를 나타내는 도면이다. 도 12a 내지 12h의 상기 R-메모리(1410)와 상기 Q-메모리(1430)에 표시된 좌표는, 상기 메모리를 도 10과 같은 형태로 하였을 때의, 메모리 어드레스를 나타낸다.

도 12a는 LDPC 복호에 있어 초기화 단계를 나타내는 도면이다. 상기 도면에 표시된 성분은 패리티 검사 행렬에서 0이 아닌 성분을 나타내는바, 송신 측으로부터 수신된 확률 값이 상기 0이 아닌 성분에 해당하는 메모리 어드레스에 입력된다.

도 12b 내지 12e은 검사 노드에서 비트 노드로의 확률 값 갱신을 나타내는 도면이다. 상기 특정 위치의 확률 값 갱신은, 특정한 행에 있어서 자신의 성분을 제외한 나머지 성분들을 이용하여 자신의 성분을 갱신하는 작업이다. 도 12f 내지 12h는 비트 노드에서 검사 노드로의 확률 값 갱신을 나타내는 도면이다. 상기 특정 위치의 확률 값 갱신은, 특정한 열에 있어서 자신의 성분을 제외한 나머지 성분들을 이용하여 자신의 성분을 갱신하는 작업이다.

도 12h까지의 과정을 수행한 후 상기 Q-메모리(1430)를 참조하여 코드워드를 임시로 결정하고, 임시로 결정된 코드워드(c')가 검사식(Hc'=0)을 만족하는지 여부를 확인한다. 상기 검사식을 만족하지 못하는 경우 도 12b 내지 도 12h의 과정을 반복하게 된다. 만약 기 설정된 횟수만큼의 반복이 있거나, 상기 검사식을 만족하는 코드워드를 얻은 경우 상기 과정은 종료된다.

이하 병렬 처리가 적용된 Layered decoding을 병렬로 처리하는 LDPC 복호기(1000)의 동작을 설명한다.

본 발명의 일 실시예에 따라, 상기 LDPC 복호기(1000)의 CNU(1110)와 VNU(1310)는 하기 수학식 4과 같은 연산을 통하여 확률 값을 갱신한다. 하기 수학식 4는 한 번의 반복 복호를 수행함에 있어 사용되는 수식이다.

상기 수학식에서 사용되는 변수는 다음과 같다.

: m번째 variable node에서 j번째 check node로 연결된 LLR(Log Likelihood Ratio) 값

: j번째 variable node의 사후 LLR 값 (a posterior LLR value)

: j번째 check node에서 m번째 variable node로 연결된 LLR 값

: j번째 check node에서 m번째 variable node로 연결된 LLR 값을 계산 하기 위한 중간변수(dummy variable)

: j번째 check node에서 m번째 variable node로 연결된 LLR 값들의 부호를 계산하기 위한 중간변수(dummy variable)

:check node Index of Parity check matrix

: Variable node index of Parity check matrix

하기 수학식 5는 수신 신호의 LLR(Log Likelihood Ratio)의 일례이고, 하기 수학식 6은 본 발명의 일 실시예에 따른 복호기(1000)가 사용하는 패리티 검사 행렬의 일례이다.

상기 수학식 6의 행렬은 본 발명의 일 실시예에 의한 복호기(1000)에서 사용하는 패리티 검사 행렬의 일례이다. 상기 행렬에서, 상기 패리티 검사 행렬의 하나의 행은 하나의 레이어를 나타낸다. 상기 각각의 레이어는 서로 인접하는 레이어와 서로 중첩하지 않는다. 상기 복호기(1000)의 CNU(1110)와 VNU(1310)의 개수는 상기 패리티 검사 행렬의 구조에 따라 정해지는 것이 바람직하다. 또한, 중첩하지 않는 레이어는 병렬처리되는바, 상기 CNU(1110)의 개수는 병렬처리되는 레이어에 포함되는 행의 개수인 것이 더욱 바람직하며, 상기 VNU(1310)의 개수는 상기 패리티 검사 행렬의 열의 개수인 것이 더욱 바람직하다. 따라서, 상기 수학식 6을 이용하는 상기 복호기(1000)의 CNU(1110)는 2개인 것이 바람직하며, VNU(1310)는 24개인 것이 바람직하다.

도 13a 내지 도 13i는 본 발명의 일 실시예에 따라 LDPC 복호 방법으로 복호화를 수행하는 경우, 한 번의 반복 복호를 수행하는 과정을 나타내는 도면이다. 상기 도 13a 내지 도 13i의 Q와 R은 상기 수학식 4의

,

값을 저장하는 메모리의 상태를 나타내며, '###'는 아직 특정한 값으로 정해지지 않은 임의의 값을 나타낸다. 상기 도 13a 내지 도 13i의 Q-메모리(1430)와 R-메모리(1410)는, 도 10에 도시된 형태와 같이 0이 아닌 성분의 위치에 해당하는 연산 값만을 저장할 수 있다.

도 13a는 본 발명의 일 실시예에 따른 LDPC 복호에 있어서 초기화 단계를 나타내는 도면이다. 채널로부터 수신된 확률 값(예를 들어, LLR 값)은 상기 수신 LLR 메모리(1420)에 저장되며, 상기 수신된 확률 값은 상기 패리티 검사 행렬 인덱스 저장부(1240)에 저장된 패리티 검사 행렬의 무게(wegiht)에 관한 위치 정보에 따라 상기 Q-메모리(1430)에 입력된다. 도 20a는 상기 초기화 단계를 통해 Q 메모리에 입력된 확률 값을 나타낸다.

도 13b는 상기 패리티 검사 행렬의 Layer 0과 Layer 3에 대하여 검사 노드에서 비트 노드로의 확률 값 갱신 과정을 나타낸다. 상기 CNU(1110)는 상기 패리티 검사 행렬의 Layer 0과 Layer 3에 대하여 검사 노드에서 비트 노드로의 확률 값을 갱신하는 연산을 수행한다. 상술한 바와 같이, 상기 CNU(1110)는 2개가 구비되어 동작하는바, 2개의 CNU(1110)는 상기 Layer 0과 3에 대한 검사 노드 갱신과정을 수행한다. 상기 연산의 결과는 상기 R-메모리(1410)에 저장된다.

도 13c는 상기 H행렬의 Layer 0과 Layer 3에 대하여 비트 노드에서 검사 노드로의 확률 값 갱신 과정을 나타낸다. 상기 비트 노드에서 검사 노드로의 확률 값 갱신 과정은, 종래의 LDPC 복호화 과정과 달리, 동일한 반복 단계에서 이미 갱신된 레이어의 확률 값을 이용하여 현재 레이어의 확률 값을 갱신한다. 상기 Layer 0과 Layer 3는 서로 중첩되지 않으므로, 병렬처리에 따른 메모리 충돌이나 병렬처리하는 데이터 간의 의존성 문제가 발생하지 않는다. 따라서 상기 Layer 0에 대한 비트 노드에서 검사 노드로의 확률 값 갱신 과정과, Layer 3에 대한 비트 노드에서 검사 노드로의 확률 값 갱신 과정은 병렬처리될 수 있다. 상술한 바와 같이, 상기 복호기는 24개의 VNU(1310)을 이용하여 상기 Layer0과 Layer 3에 대한 연산을 수행한다. 도 13c는 상기 Layer 0과 Layer 3에 대하여 비트 노드에서 검사 노드로의 확률 값 갱신이 수행된 결과와 함께, Layer 6과 Layer 1에 대한 검사 노드에서 비트 노드로의 확률 값 갱신을 위한 확률 값이 입력되는 설정 단계가 수행된 결과를 나타낸다.

도 13d는 상기 패리티 검사 행렬의 Layer 6과 Layer 1에 대하여 검사 노드에서 비트 노드로의 확률 값 갱신 과정을 나타내고, 도 13e는 상기 패리티 검사 행렬의 Layer 6과 Layer 1에 대하여 비트 노드에서 검사 노드로의 확률 값 갱신 과정을 나타내고, 도 13f는 상기 패리티 검사 행렬의 Layer 4와 Layer 7에 대하여 검사 노드에서 비트 노드로의 확률 값 갱신 과정을 나타내고, 도 13g는 상기 패리티 검사 행렬의 Layer 4와 Layer 7에 대하여 비트 노드에서 검사 노드로의 확률 값 갱신 과정을 나타내고, 도 13h는 상기 패리티 검사 행렬의 Layer 2와 Layer 5에 대하여 검사 노드에서 비트 노드로의 확률 값 갱신 과정을 나타내고, 도 13i는 상기 패리티 검사 행렬의 Layer 2과 Layer 5에 대하여 비트 노드에서 검사 노드로의 확률 값 갱신 과정을 나타낸다. 상기 Q-메모리(1430)에 저장된 값이 1번의 반복을 통해 얻은 연산 값이다. 상기 경 판정부(1250)는, 도 13i 까지의 과정을 수행한 후 상기 Q-메모리(1430)를 참조하여 임시로 코드워드(c') 결정하고, 상기 코드워드(c')가 검사식(Hc'=0)을 만족하는지 여부를 확인한다. 상기 검사식을 만족하지 못하는 경우에는, 상기 복호기는 도 13b 내지 도 13i의 과정을 반복하게 된다. 만약, 최대 반복 횟수만큼의 반복이 있거나, 상기 검사식을 만족하는 코드워드를 얻은 경우 상기 과정은 종료되며 상기 코드워드(c')은 외부로 출력된다.

도 13에 도시된 복호화 방법은 도 12에 도시된 복호화 방법에 비하여 다음과 같은 차이가 있다. 도 12에 도시된 복호화 방법은 패리티 검사 행렬의 크기에 따라 최대한의 CNU 및 VNU를 이용하여 한번의 검사 노드 갱신 과정과 비트 노드 갱신을 수행하지만, 도 13에 도시된 복호화 방법은, 데이터 의존성이 없는 Layer의 수, 즉 패리티 검사 행렬에서 서로 중첩하지 않는 레이어의 개수 만큼의 CNU를 구비하고, 상기 데이터 의존성이 없는 레이어의 개수에 따라 상기 검사 노드 갱신 과정을 병렬 처리 할 수 있다.

또한, 도 12에 도시된 복호화 방법은 수신 신호에 대한 확률 값을 이용하여 Q-메모리(1430)의 전 영역을 초기화하는 반면, 도 13에 도시된 복호화 방법은 동시에 병렬 처리가 가능한 레이어에 대한 초기화를 하고, 그 레이어들에 대한 결과값을 다음 레이어에 대한 초기 값으로 사용한다.

본 발명은 본 발명의 정신 및 필수적 특징을 벗어나지 않는 범위에서 다른 특정한 형태로 구체화될 수 있음은 당업자에게 자명하다. 따라서, 상기의 상세한 설명은 모든 면에서 제한적으로 해석되어서는 아니되고 예시적인 것으로 고려되어야 한다. 본 발명의 범위는 첨부된 청구항의 합리적 해석에 의해 결정되어야 하고, 본 발명의 등가적 범위 내에서의 모든 변경은 본 발명의 범위에 포함된다.

도 1은 패리티 검사 행렬 H를 이분법 그래프(Bipartite graph)를 통해 나타낸 도면이다.

도 2는 모델 행렬의 일 예를 도시한 것이다.

도 3은 상술한 인덱스, 즉 쉬프트 수(shift number)에 따른 행렬의 표현 방법을 설명하기 위한 도면이다.

도 4는 레이어(layer) 단위로 구분된 모델 행렬을 나타내는 도면이다.

도 5a는 병렬처리(parallel processing)의 개념을 나타내는 도면이다.

도 5b는 병렬처리에 따른 메모리 접근 출동(memory access collision)의 개념을 나타내는 도면이다.

도 6은 코드 레이트가 1/2인 경우의 기본 행렬의 또 다른 실시예이다.

도 7는 코드 레이트가 1/2인 경우의 상기 기본 행렬의 또 다른 실시예이다.

도 9는 본 발명의 일 실시예에 따른 LDPC 복호기의 일 실시예를 나타내는 블록도이다.

도 10은 본 발명의 일 실시예에 따른 LDPC 복호기의 메모리 구조를 나타내는 도면이다.

도 11은 본 발명의 일 실시예에 따른 LDPC 복호기의 하드웨어 간의 연결 형태를 나타내는 도면이다.

도 12a 내지 12h는 LDPC 복호화를 수행하는 경우, 초기화 과정에서 한 번의 반복 복호(one iteration)를 수행하는 과정을 나타내는 도면이다.

도 13a 내지 13h는 병렬 처리를 적용한 LDPC 복호화를 수행하는 경우, 초기화 과정에서 한 번의 반복 복호(one iteration)를 수행하는 과정을 나타내는 도면이다.

Claims

패리티 검사 행렬을 이용하여 부호화된 코드워드를 복호화하는 방법에 있어서,

상기 코드워드를 상기 패리티 검사 행렬을 이용하여 복호화하는 단계를 포함하되,

상기 패리티 검사 행렬은 모델 행렬에 포함된 각 인덱스를 해당 인덱스가 지시하는 서브 행렬로 대체시킴으로써 생성되고,

상기 모델 행렬은 기본 모델 행렬의 적어도 하나 이상의 행(row)의 각각을 다수의 행들로 배타적으로 분리하여 분리된 이후 상기 다수의 행들의 대응하는 열들이 동시에 무게(weight)를 갖지 않도록 분리함으로써 생성되며,

상기 패리티 검사 행렬은 각 레이어가 상기 모델 행렬의 행 단위로 이루어지는 다수의 레이어들을 포함하는, LDPC 코드를 이용한 복호화 방법.
제1항에 있어서,

상기 복호화 단계에서 상기 다수의 레이어들의 각각에 포함되는 하나씩의 행은 병렬적으로 처리되는 것을 특징으로 하는 LDPC 코드를 이용한 복호화 방법.
제2항에 있어서,

상기 다수의 레이어들의 각각에 포함되는 하나씩의 행을 병렬적으로 처리하기 위해 각 레이어 별 복호 프로세서(decoding processor)를 스케쥴링하는 단계를 더 포함하는, LDPC 코드를 이용한 복호화 방법.
패리티 검사 행렬을 이용하여 부호화된 코드워드를 복호화하는 장치에 있어서,

상기 코드워드를 상기 패리티 검사 행렬을 이용하여 복호화하는 복호기(decoder)를 포함하되,

상기 패리티 검사 행렬은 모델 행렬에 포함된 각 인덱스를 해당 인덱스가 지시하는 서브 행렬로 대체시킴으로써 생성되고,

상기 모델 행렬은 기본 모델 행렬의 적어도 하나 이상의 행(row)의 각각을 다수의 행들로 배타적으로 분리하되 분리된 이후 상기 다수의 행들의 대응하는 열들이 동시에 무게(weight)를 갖지 않도록 분리함으로써 생성되며,

상기 패리티 검사 행렬은 각 레이어가 상기 모델 행렬의 행 단위로 이루어지는 다수의 레이어들을 포함하는, LDPC 코드를 이용한 복호화 장치.
제4항에 있어서,

상기 복호기는 상기 다수의 레이어들의 각각에 포함되는 하나씩의 행을 병렬적으로 처리되는 것을 특징으로 하는 LDPC 코드를 이용한 복호화 장치.
제5항에 있어서,

상기 복호기는 상기 다수의 레이어들의 각각에 포함되는 하나씩의 행을 병렬적으로 처리하기 위해 각 레이어 별 복호 프로세서를 스케쥴링하는 하는 것을 특징으로 하는, LDPC 코드를 이용한 복호화 장치.