KR101162217B1

KR101162217B1 - 패리티 검사 행렬을 이용하여 ｌｄｐｃ 부호화를 수행하는방법

Info

Publication number: KR101162217B1
Application number: KR1020060114018A
Authority: KR
Inventors: 정지욱; 오민석; 조기형; 강승현; 윤영철; 김상국; 석지애; 이영섭; 김소연
Original assignee: 엘지전자 주식회사
Priority date: 2006-11-17
Filing date: 2006-11-17
Publication date: 2012-07-04
Anticipated expiration: 2026-11-17
Also published as: KR20080045020A

Abstract

본 발명은 LDPC(Low Density Parity Check) 부호화 방법에 관한 것으로서, 보다 상세하게는, 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행하는 방법에 관한 것이다.

본 발명은 상술한 목적을 달성하기 위해, 특정한 패리티 검사 행렬에 포함되는 복수의 행들을 하나의 행으로 조합하여 새로운 패리티 검사 행렬을 생성하는 단계; 및 상기 생성된 패리티 검사 행렬을 이용하여 수신 단으로 송신하려는 송신 정보에 대한 부호화를 수행하는 단계를 포함하여 이루어지되, 상기 조합되는 복수의 행들은, 정보어 부분에서 무게를 갖는 성분이 열 방향으로 중첩되지 않는 것을 특징으로 한다.

LDPC, 행, 조합, IR, HARQ, 정보어

Description

패리티 검사 행렬을 이용하여 ＬＤＰＣ 부호화를 수행하는 방법{Method of LDPC encoding using a parity check matrix}

도 1은 본 발명 및 종래 기술이 적용되는 이동통신 채널의 구조를 나타내는 도면이다.

도 2 내지 도 4는 종래 기술에 따른 재전송 기법을 나타내는 도면이다.

도 5 내지 도 6은 종래 및 본 발명에 따른 재전송 기법을 나타내는 도면이다.

도 7은 패리티 검사 행렬 상의 서브 블록의 개념을 나타내는 도면이다.

도 8은 종래에 제안된 모델 행렬의 일례이다.

도 9는 상술한 인덱스, 즉 쉬프트 수(shift number)에 따른 행렬의 표현 방법을 나타낸 도면이다.

도 10은 종래 기술 및 본 발명에 따른 LDPC 복호화 방법을 나타내는 도면이다.

도 11a는 상기 IR 기법을 지원하기 위한 두 번째 방법에서 사용되는 모 행렬의 일례를 모델 행렬로 나타낸 것이다.

도 11b는 하나의 모 행렬을 부호율에 따라 여러 개로 잘라서 사용하는 방법을 나타내는 블록도이다.

도 12는 본 실시예에서 사용하는 하나의 모 행렬(mother matrix)이다.

도 13a는 정보어 부분에서 무게를 갖지 성분이 열 방향으로 중첩되지 않는 두 개의 행(row)을 일례를 나타낸다.

도 13b는 정보어 부분에서 무게를 갖지 성분이 열 방향으로 중첩하는 두 개의 행(row)을 일례를 나타낸다.

도 14 내지 도 17은 도 12의 모델 행렬에서 중첩하지 않는 행들을 서로 조합한 일례이다.

도 18의 모델 행렬은 부호율이 5/6인 경우 LDPC 복호화에 사용되는 모델 행렬이다.

도 1은 본 발명 및 종래 기술이 적용되는 이동통신 채널의 구조를 나타내는 도면이다. 이하, 도 1을 참조하여 이동통신 채널의 구조를 설명한다. 송신 단(Transmitter)에서 전송할 데이터를 무선채널에서 손실이나 왜곡 없이 전송하기 위해 채널 코딩(channel coding) 절차를 거친다. 상기 채널 코딩 기법으로는, Convolutional Coding, Turbo Coding, LDPC Coding 등의 다양한 기술이 있다. 상기 채널 코딩(Channel coding) 절차를 거친 데이터(data)는 무선 채널로 전송될 때 여러 개의 비트들이 모여서 하나의 심볼로 전송될 수 있다. 이때, 여러 비트들을 하나의 심볼(symbol)로 매핑(mapping) 되는 절차를 변조(modulation)라 한다.

변조된 데이터는 다중화(Multiplexing) 과정 또는 다중 접속(Multiple Access) 방법을 거쳐 다중 전송을 위한 신호로 변환된다. 상기 다중화 방법으로는, CDM, TDM, FDM 등의 다양한 방법이 존재한다. 상기 다중화(Multiplexing) 블록을 거친 신호는 한 개 이상의 다중 안테나에 전송되기 적합한 구조로 변경되어 무선채널을 통해 수신 단(Receiver)에 전달된다. 무선 채널을 통과하는 과정에서 전송된 데이터는 페이딩(Fading)과 열 잡음을 겪게 되어 데이터에 왜곡이 발생할 수 있다.

상기 변조(Modulation)된 데이터는 무선 채널을 통해 수신 단(Receiver)에 전달된다. 이 과정에서 전송된 데이터는 페이딩(Fading)과 열 잡음 등을 겪게 되어 데이터에 왜곡이 발생할 수 있다. 수신 단에서는 상기 왜곡된 데이터를 수신한 후 상기 송신 단의 일련의 절차를 역순으로 수행한다. 상기 심볼로 매핑(mapping)된 데이터를 비트열로 바꾸는 복조(demodulation) 작업을 수행하고, 채널 디코딩(Channel Decoding) 절차를 거치며 왜곡된 데이터를 원래 데이터로 복원한다.

상기 채널 코딩을 수행하는 장치는, 입력된 데이터(Information bits 또는 Systematic Bits)에 첨가될 패리티 비트(Parity Bits)을 발생시키는 사용되는 패리티 검사 행렬(Parity Check Matrix)인 H 행렬 또는 H행렬로부터 유도되는 생성행렬(Generation Matrix) G 행렬을 저장하고 있다. 즉, 상기 송신 단은, 상기 H 또는 G 행렬과 상기 입력된 데이터를 통해 패리티 비트(Parity Bit)들을 발생하는 인코 더(Encoder)를 포함한다. 채널 디코딩(Channel Decoding)을 수행하는 장치는, 수신된 데이터(왜곡된 Systematic Bits + Parity Bits)를 H행렬과 연산을 통하여 상기 입력된 데이터(Systematic Bits)들이 제대로 복구되는지 확인하고 복구 실패시 연산을 재수행한다.

상기 변조(Modulation)는 BPSK(Binary Phase Shift Keying), QPSK(Quadrature Phase Shift Keying), 16-QAM(Quadrature Amplitude Modulation), 64-QAM, 256-QAM 등이 사용된다. 예를 들어, 16-QAM은 변조(Modulation)시 채널 인코딩(Channel Encoding) 절차를 거친 데이터 열을 4 비트 단위로 하나의 심볼에 매핑(mapping)한다. 16-QAM은 복조(Demodulation) 시 무선 채널을 거쳐 수신된 데이터의 하나의 심볼을 4개의 bit로 디매핑(demapping) 한다.

이하, 본 발명과 함께 사용될 수 있는 데이터 재전송 기법에 관하여 설명한다. 상기 데이터 재전송 기법의 종류는 다양한바, 이하 HARQ(Hybrid Automatic Repeat reQuest) 기법에 대하여 설명한다. HARQ는 통신시스템에서 재전송 기법인 ARQ(Automatic Repeat reQuest)와 FEC(Forward Error Correction) 부호를 결합한 기술이다. ARQ 기법은, 수신단에서 수신된 데이터에서 에러(error)가 검출된 경우, 상기 수신 단(Receiver)은 송신 단(Transmitter)으로 재전송을 요청하는 방법이다. ARQ 기법에는 재전송 방법에 따라, Stop-And-Wait, Selective Repeat, Go-Back-N 등이 있다. 상기 Stop-And-Wait 기법은 도 2와 같이 송신 단은 데이터를 송신하고, 수신 단에서 데이터가 성공적으로 수신되었음을 알리는 ACK(Acknowledgement) 메시지를 송신 단이 받으면, 다음 데이터를 송신하고, 송신단 이 수신 단으로부터 데이 터가 성공적으로 수신되지 않았다는 NACK 메시지를 받으면, 전송에 실패한 데이터를 다시 보내는 방법이다.

한편, Go-Back-N 방법에서는 송신 단은 N개의 데이터를 우선 보내고, 수신 단으로부터 ACK메시지를 차례대로 수신한다. 도 3은 N=7인 경우를 나타내는데, 이때, ACK을 받지 않고 보내는 데이터의 개수(N)를 윈도우 크기(window size)라고 한다. 송신단은 k 번째 데이터에 대한 NACK 메시지를 받으면, k번째 데이터부터 순차적으로 데이터를 전송한다

도 4는 Selective Repeat 방법을 나타낸다. 상기 Selective Repeat 방법에서는, 상기 Go-Back-N 방법에서와 같이 ACK 또는 NACK 메시지를 받지 않고, 윈도우 크기(Window Size)를 N으로 하여 데이터를 전송하고, NACK 메시지를 받은 데이터에 대해서만 선택적으로 재전송을 수행한다.

상술한 HARQ 기법은 상기 ARQ 방식에서 재전송을 하는 경우에, 먼저 전송된 데이터와 재전송된 데이터를 결합하여, FEC 부호를 통해 복구하는 방법이며, 두 데이터를 결합하는 방법에 따라, Chase Combining과 Incremental Redundancy로 나뉘어진다. Chase Combining 기법은 도 5와 같이 수신단에서 전송 데이터와 재전송 데이터를 결합하여 수신 SNR(Signal to Noise Ratio)를 높여 수신단에서 데이터에 대한 수신 성공율을 높이는 방법이다.

한편, Incremental Redundancy 기법(이하, 'IR 기법'이라 칭함)은 도 6와 같이 송신단에서 재전송 시, Chase Combining 방법과는 달리, 처음 전송에 사용되지 않았던 부호화된 데이터의 일부를 전송하여 수신단에서 수신된 데이터의 부호율(code rate)을 낮추는 방법을 통해 수신 성공률을 높이는 방법이다.

이하 LDPC 부호에 관하여 설명한다. LDPC 부호의 개념을 설명하면 다음과 같다.

선형 부호는 생성행렬 G 또는 패리티 체크 행렬 H로 기술될 수 있다. 선형 부호의 특징은 모든 코드워드 c 에 대하여,

을 만족하도록 부호가 구성된다는 점이다. 이 선형 부호의 일종으로서, 최근에 주목받는 LDPC 부호는 1962년 Gallager에 의하여 처음 제안되었다. 이 부호의 특징으로는 패리티 체크 행렬의 원소가 대부분 0으로 이루어지고, 0이 아닌 원소의 수는 부호 길이에 비하여 적은 수를 가지도록 하여 확률을 기반으로 한 반복적 복호가 가능한 점이다. 처음 제안된 LDPC 부호는 패리티 체크 행렬을 비체계적인(non-systematic) 형태로 정의하였고, 그것의 행과 열에 균일하게 적은 무게(weight)를 갖도록 설계되었다.

여기서, 무게(weight)란 행렬에서 열(column) 또는 행(row)에 포함된 1의 개수를 의미한다.

LDPC 부호의 패리티 체크 행렬 H 상에 0이 아닌 원소의 밀도가 적기 때문에 낮은 복호 복잡도를 가지게 된다. 아울러, 복호 성능도 기존의 부호들보다 우수하여 Shannon의 이론적인 한계에 근접하는 좋은 성능을 보인다. 하지만 LDPC 부호는 당시 하드웨어 기술로서 구현이 어려워서 30여 년이 넘게 많은 사람의 관심을 끌지 못하였다. 1980년대 초반 그래프를 이용하여 반복적 복호를 하는 방법이 개발되어, 이를 이용하여 LDPC 부호를 실제로 복호할 수 있는 여러 알고리즘들이 개발되었다. 이를 대표하는 알고리즘으로 합곱 알고리즘(sum-product Algorithm)을 뽑을 수 있다.

이하, LDPC 부호의 특징을 설명한다. LDPC 부호는 높은 오류 정정 성능을 갖고 있으며, 이로 인해 통신 속도와 용량의 개선을 가능하게 한다. 상기 LDPC 부호는 MIMO(Multiple Input Multiple Output) 시스템과 결합하여 수백 Mbit/s의 전송이 가능한 고속 무선 LAN에 적용될 수 있고, 또한 250km/h에서 1Mbit/s 이상의 전송 속도를 갖는 고속 이동 통신에 적용될 수 있고, 또한 40Gbits/s 이상의 광통신에 적용될 수 있다. 또한, 상기 LDPC 부호의 높은 오류 정정 성능으로 인해 전송 품질이 개선되어 저품질의 통신 경로에서 재전송의 회수를 감소시키는 양자 암호화 통신을 가능하게 할 수 있다. 또한, LDPC 부호의 낮은 복잡도와 뛰어난 손실 보상으로 인해, 유실된 패킷을 용이하게 복원할 수 있으며, 이는 인터넷과 이동 통신을 통해 TV 품질과 동일한 품질의 컨텐츠를 전송할 수 있게 한다. LDPC의 장점인 넓은 적용 범위와 큰 용량으로 인하여, 전에는 불가능한 것으로 여겨졌던 100m 범위까지의 10GBASE-T 전송이 LDPC 부호를 통해 실현 가능하다. 동시에 36MHz 대역의 단일 위성 송신기의 전송 용량을 1.3배 늘어난 80M비트/s까지 늘릴 수 있다.

이하, 구조화된(structured) LDPC를 설명한다.

LDPC 부호를 사용하기 위해서는 패리티 체크 행렬 H를 사용하는데, 사용하는 행렬 H는 대부분의 0과 일부의 1을 원소(elemnet)로 포함하는데, H 행렬의 크기가 10⁵ 비트 이상으로 크기 때문에 H 행렬을 표현하는데 큰 크기의 메모리가 필요하다. 상기 구조화된 LDPC 기법은 LDPC 부호화 및 복호화에 사용되는 상기 H 행렬의 원소들을 도 7과 같이 일정한 크기의 서브 블록(sub-block)으로 표현하는 방법이다. IEEE802.16e에서는 상기 서브 블록을 하나의 정수 인덱스(index)로 표시하여, 상기 H 행렬을 저장하는데 필요한 메모리의 크기를 줄인다. 상기 서브 블록은 다양한 행렬일 수 있는바, 예를 들어 일정한 크기의 퍼뮤테이션 행렬(Permutation Matrix)일 수도 있다.

상기 구조화된 LDPC 기법을 사용하게 되면 특정한 메모리에 1 또는 0으로 구성되는 일정 크기의 행렬을 저장하는 대신, 하나의 정수(즉, 인덱스)만 저장하면 되기 때문에 상기 H 행렬을 표시하는데 필요한 메모리의 크기를 줄일 수 있다.

일례로, IEEE802.16e 표준에 반영된 코드워드(codeword)의 크기가 2304이고, 부호율(code rate)이 2/3인 경우에, LDPC 부호화/복호화를 위해 사용되는 모델 행렬(model matrix)은 도 8과 같다. 모델 행렬은, 이하에서 설명하는 쉬프트 수로 표현되는 적어도 하나의 서브 블록으로 구성된 패리티 검사 행렬을 의미한다. 상기 모델 행렬은 이하에서 설명하는 방법에 의해 패리티 검사 행렬로 확장되어 생성될 수 있다. 따라서 특정한 모델 행렬로 부호화 및 복호화를 수행한다는 의미는 해당 모델 행렬에서 확장되어 생성된 패리티 검사 행렬로 부호화 및 복호화를 수행한다는 의미와 동일하다.

도 8에 도시된 바와 같이, 구조화된 LDPC 행렬은 '-1', '0' 과 양의 정수로 표현될 수 있다. 인덱스가 '-1'인 경우는 특정한 크기의 영 행렬(zero matrix)을 나타내며, 인덱스가 '0'인 경우는 특정한 크기의 단위 행렬(identity matrix)을 나 타낸다. '-1'과 '0'을 제외한 양의 정수를 갖는 인덱스는, 상기 인덱스가 쉬프트 수(shift number)를 나타낸다. 서브 블록을 '1'이라는 인덱스로 표현하는 경우, 해당 서브 블록은 단위 행렬에서 특정한 방향으로 '1'번 쉬프트된 것이다.

도 9는 상술한 인덱스, 즉 쉬프트 수(shift number)에 따른 행렬의 표현 방법을 나타낸 도면이다. 특정한 패리티 검사 행렬을 4*4 크기의 행렬(즉, 서브 블록)로 구조화하여 표현하는 경우, 상기 특정한 서브 블록을 '3'이라는 인덱스로 표시하면, 상기 서브 블록은 도 9의 행렬이 된다.

이하, LDPC 부호화 방법을 설명한다.

일반적인 LDPC 부호화(Encoding) 방법은, LDPC 패리티 검사행렬(Parity Check Matrix) H로부터 생성행렬(Generation Matrix) G를 유도해 내어, 정보 비트(information bit)를 부호화(encoding)한다. 상기 생성행렬 G를 유도하기 위해, 상기 검사행렬 H를 가우스 소거(Gaussian Reduction) 방법을 통해 [ P^T : I ] 형태로 구성한다. 상기 정보 비트(Information bit)의 수를 k이라 하고, 인코딩된 코드 워드(codeword)의 크기를 n이라고 할 때, 상기 P 행렬은 행의 개수가 k이고 열의 개수가 n-k인 행렬이고, 상기 I는 행 크기가 k 열 크기가 k인 단위 행렬(Identity Matrix)이다.

상기 생성행렬 G 는, 상기 검사행렬 H 가 [ P^T : I ]와 같이 표현되었을 때, [ I : P ] 행렬이 된다. 인코딩(Encoding) 되는 k 비트 크기의 정보 비트를 행렬로 표시하면, 행의 개수는 1이고 열의 개수는 k인 행렬 x로 표현할 수 있다. 이 경우 코드 워드 c는 다음과 같은 식으로 설명된다.

상기 수식에서, x는 정보어 부분(information part 또는 systematic part)을 나타내고, xP는 패리티 부분(parity part)을 나타낸다.

한편, 위와 같이 가우스 소거(Gaussian Reduction) 방법으로 부호화하는 경우에는 계산량이 많아, 상기 H 행렬의 형태를 특수한 구조로 디자인(design)하여 상기 G 행렬을 유도하지 않고, 상기 H 행렬에서 직접 부호화하는 방법을 사용한다. 즉, 상기 G 행렬과 상기 H 행렬에 대한 전치(Transpose) 형태의 H^T 간의 곱이 0 이라는 성질(즉,

)을 이용하여, 상기 수학식 1에서 H^T을 곱하면, 하기 수학식 2 같은 수학식을 얻을 수 있다. 하기 수학식 2에 부합하는 패리티 비트를 정보 비트(x) 뒤에 추가하여 코드워드 c를 얻을 수 있다.

이하, LDPC 복호화 방법에 대하여 설명한다.

통신시스템에서 부호화된 데이터는 도 1의 무선 채널을 통과하는 과정에서 잡음을 포함하게 되는데, 수신 단에서는 도 10과 같은 절차를 통해 데이터의 복호 과정을 나타낸다. 수신 단의 복호화 블록에서는 부호화된 코드워드(c)에 잡음이 첨 가된 수신신호(c')로부터 정보 비트(x)를 구하는데, cH^T=0인 성질을 이용하여 찾아낸다. 즉, 수신된 코드워드를 c'라 할 때, c'H^T의 값을 계산하여 결과가 0이면, c' 에서 처음 k개의 비트를 상기 정보 비트(x)로 결정한다. 만약, c'H^T의 값이 0이 아닌 경우, 그래프를 통한 합곱(sum-product) 알고리즘 등의 복호화 기법을 사용하여, c'H^T의 값이 0을 만족하는 c'을 찾아 상기 정보 비트(x)를 복구한다.

이하, LDPC 부호의 부호율(code rate)를 설명한다.

일반적으로, 부호율(R: code rate)은 상기 정보 비트의 크기가 k이고, 실제 전송되는 코드워드의 크기가 n일 때 다음과 같다.

R = k/n

LDPC 부호화 및 복호화에 필요한 상기 H 행렬의 행의 크기가 m, 열의 크기가 n인 경우, 부호율은 다음과 같다.

R = 1 - m/n

상술한 바와 같이, 종래의 LDPC 부호는 상기 H 행렬에 의해 부호화 및 복호화를 수행하는바 상기 H 행렬의 구조가 매우 중요하다. 즉, 부호화 및 복호화의 성능이 상기 H 행렬의 구조에 크게 영향을 받기 때문에, 상기 H 행렬의 설계가 무엇보다 중요하다.

이하, 종래 기술의 문제점을 설명한다.

상기 IR 기법에 따라 재전송하는 경우에는, 최초 전송시와 재전송시의 부호율이 달라져야 한다. 이 경우, 서로 다른 부호율을 적용하기 위해서는 서로 다른 모델 행렬을 사용하면 IR 기법을 지원하지 못하는 문제가 발생할 수 있다. 예를 들어, 최초 전송시에 사용했던 제1 모델 행렬과 NACK 신호를 수신한 이후에 사용하는 제2 모델 행렬이 서로 상이한 경우에는 상기 제1 모델 행렬에 의해 생성된 패리티 비트와 상기 제2 모델 행렬에 의해 생성된 패리티 비트가 상이하여 수신 단에서의 결합 수신이 불가능한 문제가 있다.

본 발명은 상술한 종래 기술의 문제점을 해결하기 위해 제안된 것으로, 본 발명의 목적은 다양한 H-ARQ 기법을 지원하는 LDPC 부호화 방법을 제안하는 것이다.

본 발명의 또 다른 목적은 개선된 성능의 모델 행렬을 제안하는 것이다.

본 발명의 또 다른 목적은 개선된 성능의 모델 행렬을 사용하는 재전송 기법을 제안하는 것이다.

발명의 개요

본 발명은 상술한 목적을 달성하기 위해, 특정한 패리티 검사 행렬에 포함되는 복수의 행들을 하나의 행으로 조합하여 새로운 패리티 검사 행렬을 생성하는 단계; 및 상기 생성된 패리티 검사 행렬을 이용하여 수신 단으로 송신하려는 송신 정 보에 대한 부호화를 수행하는 단계를 포함하여 이루어지되, 상기 조합되는 복수의 행들은, 정보어 부분에서 무게를 갖는 성분이 열 방향으로 중첩되지 않는 것을 특징으로 한다.

또한, 본 발명은, LDPC 부호를 이용하여 재전송을 수행하는 방법에 있어서, 복수의 행들이 조합한 행을 포함하는 패리티 검사 행렬을 이용하여 수신 단으로 송신하려는 송신 정보에 대한 제1 부호화를 수행하는 단계; 상기 부호화된 송신 정보를 상기 수신 단으로 송신하는 단계; 상기 수신 단으로부터 NACK 신호를 수신하는 경우, 상기 조합된 행을 상기 복수의 행들로 복원한 패리티 검사 행렬을 이용하여 상기 송신 정보에 대한 제2 부호화를 수행하는 단계; 및 상기 제2 부호화에 의해 추가로 생성된 패리티 비트를 상기 수신 단으로 송신하는 단계를 포함하여 이루어지되, 상기 조합된 복수의 행들은, 정보어 부분에서 무게를 갖는 성분이 열 방향으로 중첩되지 않는 것을 특징으로 한다.

발명의 일 실시예

본 발명의 구성 및 동작은 이하에서 설명되는 본 발명의 일 실시예에 의해 구체화될 것이다. 이하, 첨부된 도면을 참조하여 본 발명의 일 실시예를 설명한다.

일반적으로 상기 IR(Incremental Redundancy) 기법을 LDPC 부호에 지원하기 위해 2 가지 방법이 제안되었다.

첫 번째 방법은 LDPC 부호화 방법에 의해 생성된 LDPC 코드워드에 포함된 정보 비트와 패리티 비트 중 적어도 어느 하나를 천공하는 천공(puncturing) 방법이다. 상기 천공 방법은 패리티 비트에 대해 수행되는 것이 바람직하다.

상기 천공 기법을 수행하면 부호율을 조절할 수 있다. 즉 상기 수학식 4에 따라 부호율이 조정되므로, 천공을 많이 수행하면 높은 부호율을 얻을 수 있고, 천공을 적게 수행하면 낮은 부호율을 얻을 수 있다. 이러한 특징을 이용하여 상기 IR 기법을 수행할 수 있다.

상기 IR 기법을 지원하기 위한 두 번째 방법은, 모 행렬(mother matrix)를 잘라서 부호화에 사용하는 방법이다.

하나의 모 행렬은 도 11b와 같이 여러 개로 구분되어 사용될 수 있다. 도 11b는 하나의 모 행렬을 부호율에 따라 여러 개로 잘라서 사용하는 방법을 나타내는 블록도이다. 도 11b에 도시된 바와 같이, 하나의 모 행렬을 여러 개로 분리되어 사용될 수 있으며, 각각의 분리된 행렬은 특정한 부호율을 지원한다.

상기 두 번째 방법에 따르는 송신단은, 도 11a의 모델 행렬을 도 11b와 같이 잘라내서 원하는 부호율에 따라 통신할 수 있다.

본 실시예는 상술한 첫 번째 방법 또는 두 번째 방법과는 구별되는 별도의 방법을 제안한다.

보다 구체적으로, 본 실시예는 주어진 모 행렬(mother matrix)의 복수의 행(row)들을 조합할 것을 제안한다. 조합되는 행(row)은 정보어 부분에서 무게를 갖지 성분이 서로 열 방향으로 중첩되지 않는(non-overlapped) 것이 매우 바람직하다. 복수의 행들을 하나의 행으로 조합하면 새로운 모델 행렬들이 생성된다. 이렇 게 새롭게 생성된 복수의 행렬들은 복수의 부호율을 지원하므로, 상기 IR 기법을 지원할 수 있다.

도 12는 본 실시예에서 사용하는 하나의 모 행렬(mother matrix)이다. 도 12의 행렬은 모델 행렬로서 행렬의 각 서브 블록에 표시된 인덱스는 쉬프트 수를 나타낸다. 또한, 도 12에서 쉬프트 수가 표시되지 않은 서브 블록은 '-1'의 인덱스를 갖는 서브 블록이다. 즉, 쉬프트 수가 표시되지 않은 서브 블록은 영 행렬(zero matrix)을 나타낸다.

도시된 바와 같이 도 12의 모델 행렬은 8개의 행(row)과 28개의 열(columnm)로 구성된다. 상기 수학식 4에 의해, 도 12의 모델 행렬은 20/28의 부호율을 지원한다.

도 12의 모델 행렬은 정보 비트에 상응하는 정보어 부분과 패리티 비트에 상응하는 패리티 부분으로 구분된다. 도 12에서, 인덱스 0에 의해 표시되는 열(이하, '0번 열'이라 칭한다)부터 인덱스 19에 의해 표시된 열(이하, '19번 열'이라 칭한다)까지는 정보어 부분이다. 또한, 도 12에서, 인덱스 20에 의해 표시되는 열(이하, '20번 열'이라 칭한다)부터 인덱스 27에 의해 표시된 열(이하, '27번 열'이라 칭한다)까지는 패리티 부분이다.

본 실시예는 서로 다른 행(row)을 조합(combine)하는 특징이 있다.

이하, 본 실시예에 따라 행을 조합하는 방법을 설명한다.

본 실시예에 따라 조합되는 행들은 정보어 부분에서 무게를 갖는 성분이 열 방향으로 중첩되지 않는 특징이 있다. 달리 표현하면, 조합되는 복수의 행에서, 정 보어 부분의 영이 아닌 성분(non-zero element)은 동일한 열(column)에 위치할 수 없다.

도 13a는 정보어 부분에서 무게를 갖는 성분이 열 방향으로 중첩되지 않는 두 개의 행(row)을 일례를 나타낸다. 도 13a의 두 개의 행은 도 12a의 1201 행과 1202 행이다. 도 13a에서 쉬프트 수가 표시되지 않은 서브 블록은 '-1'의 인덱스를 갖는 서브 블록이다.

도 13a의 1201 행의 첫 번째 열은 '10'의 쉬프트 수를 갖지만, 1202 행의 첫 번째 열은 '-1'의 인덱스를 갖는다. 정보어 부분(0번 열부터 19번 열)에서 1201 행과 1202 행의 모든 성분을 비교하면 열 방향으로 무게를 갖는 성분이 중첩하지 않는다. 즉, 1201 행과 1202 행의 열 무게는 '1'을 초과하지 않는다.

패리티 부분에서는 무게를 갖는 성분이 열 방향으로 중첩해도 무관하다. 도 13a를 보면, 패리티 부분에서 '117'이라는 쉬프트 수가 열 방향으로 중첩하는 것을 알 수 있다.

본 실시예에 따라 도 13a의 1201 행과 1202 행을 조합(combine)하면 1301 행을 얻을 수 있다.

도 13b는 정보어 부분에서 무게를 갖지 성분이 열 방향으로 중첩하는 두 개의 행(row)을 일례를 나타낸다. 도 13b의 두 개의 행은 도 12a의 1202 행과 1203 행이다. 도 13b에서 쉬프트 수가 표시되지 않은 서브 블록은 '-1'의 인덱스를 갖는 서브 블록이다.

도 13b의 1202 행의 두 번째 열은 '82'의 쉬프트 수를 갖지만, 1203 행의 첫 번째 열은 '77'의 인덱스를 갖는다. 정보어 부분(0번 열부터 19번 열)에서 1201 행과 1202 행의 모든 성분을 비교하면 열 방향으로 무게를 갖는 성분이 중첩한다. 즉, 1202 행과 1203 행의 열 무게는 '1'을 초과한다.

따라서, 본 실시예에 따라 1202 행과 1203 행을 조합할 수 없다.

이하, 도 12의 모델 행렬에서 중첩하지 않는 행들을 서로 조합하여 새로운 모델 행렬을 만드는 방법을 설명한다. 이하, 도 14 내지 도 17은 도 12의 모델 행렬에서 중첩하지 않는 행들을 서로 조합한 일례이다.

도 14를 보면, 도 12의 1201 행과 1202 행을 조합하여 1301 행을 만드는 것을 알 수 있다. 도 14는 1201 행과 1202 행을 조합한 결과, 20/27의 부호율을 지원한다. 즉, 도 12의 부호율 보다 높은 부호율을 지원한다.

도 14의 일례를 보면 천공 없이도 다양한 부호율이 지원될 수 있음을 알 수 있다.

도 15를 보면, 도 14의 1203 행과 1204 행을 조합하여 1302 행을 만드는 것을 알 수 있다. 도 15는 1203 행과 1204 행을 조합한 결과, 20/26의 부호율을 지원한다. 즉, 도 12, 도 14의 부호율 보다 높은 부호율을 지원한다.

도 16을 보면, 도 15의 1205 행과 1206 행을 조합하여 1303 행을 만드는 것을 알 수 있다. 도 16은 1205 행과 1206 행을 조합한 결과, 4/5의 부호율을 지원한다. 즉, 도 12, 도 14, 도 15의 부호율 보다 높은 부호율을 지원한다.

도 17을 보면, 도 16의 1207 행과 1208 행을 조합하여 1304 행을 만드는 것을 알 수 있다. 도 17은 1207 행과 1208 행을 조합한 결과, 5/6의 부호율을 지원한 다. 즉, 가장 높은 부호율을 지원한다.

본 실시예에 따른 송신 단은 본 실시예에 제안하는 모 행렬을 사용하여 부호화를 수행하고 0부터 27까지의 '부호화 블록'을 생성한다. 상기 부호화 블록은 모델 행렬의 28개의 열에 상응하는 정보 비트 및 패리티 비트를 그룹화한 것을 말한다. 즉, 0번부터 27번 부호화 블록은 하나의 LDPC 코드워드에 상응한다. 또한, 정보어 부분에 상응하는 부호화 블록은 '정보어 블록'이라 칭하고, 패리티 부분에 상응하는 부호화 블록은 '패리티 블록'이라 칭한다.

도 12 내지 도 17의 모델 행렬은 본 실시예에 따른 행의 조합에 의해 생성된다. 따라서, 송신 단 또는 수신 단은 하나의 모델 행렬을 저장한 다음 본 실시예에서 제안하는 행의 조합에 따라 도 12 내지 도 17의 모델 행렬을 자유롭게 설계할 수 있다. 예를 들어, 송신 단 또는 수신 단은 도 12의 행렬만을 저장하고 있다가 부호율이 변화함에 따라 도 12의 행렬을 도 13 내지 도 17의 행렬 중 어느 하나로 변환할 수 있다.

이하, 본 실시예에 따른 첫 번째 IR 기법을 설명한다.

송신 단은 도 12의 모델 행렬을 사용하여 부호화를 수행할 수 있다. 도 12의 모델 행렬에 따라 부호화를 수행하면 28개의 열에 상응하는 부호화 블록이 생성된다. 달리 표현하면, 0번 열부터 19번 열에 상응하는 20개의 블록이 정보어 블록이 되고, 20번부터 27번 열에 상응하는 8개의 블록이 패리티 블록이 생성된다.

이 경우, 송신 단은 여러 가지 정보를 종합하여 5/6의 부호율에 따라 최초 전송을 수행할 것을 결정할 수 있다.

이때 송신 단은, 0번 열부터 19번 열까지에 상응하는 정보어 블록과, 21번, 23번, 25번, 27번 열에 상응하는 패리티 블록으로 이루어진 LDPC 코드워드를 생성하여 수신 단으로 송신한다.즉, 20개의 정보어 블록과 4개의 패리티 블록을 송신하여 5/6의 부호율을 지원할 수 있다.

본 실시예에 따른 수신 단은, 현재 사용하는 부호율이 5/6이므로 도 18의 모델 행렬을 이용하여 LDPC 복호화를 수행한다.

도 18의 모델 행렬은 부호율이 5/6인 경우 LDPC 복호화에 사용되는 모델 행렬이다. 도 18에 도시된 행렬은 도 17의 행렬에서 무게를 갖지 않는 열을 제거하는 것이다. 즉, 20, 22, 24, 26번 열을 제거한 모델 행렬이다.

도 17의 모델 행렬은 도 12의 모델 행렬의 행을 조합하여 생성한 것이다. 또한, 도 18의 모델 행렬은 도 17의 모델 행렬에서 일부 열(column)만을 선택하여 구성한 것이다.

도 18의 모델 행렬로 복호화한 이후 복호화에 실패하면, 수신 단은 NACK을 송신할 수 있다.

NACK을 수신한 송신 단은 부호율을 낮춰서 재전송을 수행한다. 예를 들어, 20/26 부호율로 재전송을 수행할 수 있다. 즉, 도 15의 모델 행렬에 따라 부호화를 수행할 수 있다. 이 경우, 24번 열과 26번 열에 상응하는 패리티 블록이 추가적으로 생성된다.

송신 단은 재전송을 수행하는 경우, 추가적으로 생성된 패리티 비트만을 송신 할 수 있다. 즉, 24번 열과 26번 열에 상응하는 패리티 블록만을 수신 단으로 송신할 수 있다.

수신 단은 24번 열과 26번 열에 상응하는 패리티 블록을 추가로 수신한 다음, 최초 전송된 24개의 데이터와 결합하여 복호화를 수행할 수 있다. 이 경우, 부호율을 20/26이기 때문에 수신 단은 도 19의 모델 행렬을 이용하여 복호화를 수행할 수 있다.

도 19의 모델 행렬은 수신 단이 재전송된 데이터를 복호화하기 위해 사용되는 모델 행렬의 일례이다. 수신 단은 추가적으로 수신되는 24번 열과 26번 열에 상응하는 패리티 블록과 이미 저장하고 있는 정보어 블록(0번 열부터 19번 열까지에 상응하는 정보어 블록) 및 패리티 블록(21번, 23번, 25번, 27번 열에 상응하는 패리티 블록)을 결합하여 복호화를 수행한다.

만약 20/26의 부호율에서 복호화에 성공하지 못한 경우, 수신 단은 NACK을 송신할 수 있다.

이 경우, 송신 단은 다시 20/27의 부호율로 부호화를 수행한다.

이 경우에는, 도 14의 22번째 열에 상응하는 패리티 블록이 추가로 생성된다. 따라서, 송신 단은 22번째 열에 상응하는 패리티 블록만을 추가로 재전송한다.

수신 단은, 재전송되는 22번째 열에 상응하는 패리티 블록과 이미 저장되어 있는 정보어 블록(0번 열부터 19번 열까지에 상응하는 정보어 블록) 및 패리티 블록(21번, 23번, 24번, 25번, 26번, 27번 열에 상응하는 패리티 블록)을 결합하여 복호화를 수행한다.

상술한 일례는 5/6의 부호율로 최초 전송을 수행하고, NACK이 수신되는 경우 20/26의 부호율로 재전송을 수행하고, 다시 NACK이 수신되는 경우, 20/27의 부호율로 재전송하는 경우의 일례이다. 또한, 부호율이 변화함에 따라 추가적으로 생성된 패리티 블록만을 추가적으로 재전송하는 방법에 관한 것이다.

이하, 본 실시예에 따른 두 번째 IR 기법을 설명한다.

우선 특정한 부호율, 예를 들어 5/6의 부호율에 따라 최초 전송을 수행할 수 있다. 즉, 도 17의 모델행렬에 따라 데이터를 전송한다.

도 17의 모델 행렬에 따라 부호화가 수행되면, 도 17의 0번 열부터 27번 열에 상응하는 부호화블록이 생성된다. 이 경우, 송신 단은 0번 열부터 19번 열까지에 상응하는 정보어 블록과, 21번, 23번, 25번, 27번 열에 상응하는 패리티 블록으로 이루어진 LDPC 코드워드를 생성하여 수신 단으로 송신한다.

한편, 도 18의 모델 행렬로 복호화한 이후 복호화에 실패하면, 수신 단은 NACK을 송신할 수 있다.

NACK을 수신한 송신 단은 부호율을 낮춰서 재전송을 수행한다. 예를 들어, 20/26 부호율로 재전송을 수행할 수 있다. 즉, 도 15의 모델 행렬에 따라 부호화를 수행할 수 있다. 이 경우, 24번 열과 26번 열에 상응하는 패리티 블록이 추가적으 로 생성된다.

수신 단은, 재전송되는 22번째 열에 상응하는 패리티 블록과 이미 저장되어 있는 정보어 블록(0번 열부터 19번 열까지에 상응하는 정보어 블록) 및 패리티 블 록(21번, 23번, 24번, 25번, 26번, 27번 열에 상응하는 패리티 블록)을 결합하여 복호화를 수행한다.

본 실시예에서 제안한 모델 행렬은 본 발명을 설명하기 위한 일례에 불과하다. 따라서, 본 발명은 본 실시예가 제안한 모델 행렬에 제한되지 아니한다.

또한, 본 실시예를 설명하기 위해 사용된 구체적인 부호율, 재전송의 수선 등은 본 실시예를 설명하기 위한 일례에 불과하므로, 본 발명이 이에 한정되지 않는다.

또한, 본 실시예에 따른 모델 행렬은 재전송 이외의 다양한 통신 기법에 사용될 수 있다.

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

이하, 본 발명에 따른 효과를 설명한다.

낮은 부호율을 지원하는 모델 행렬은 cycle-4와 cycle-6의 영향에 민감하다. 또한, 평균 column degree는 높은 부호율을 지원하는 모델 행렬에 비해 작다. 즉, 낮은 부호율의 모델 행렬은, nonzero weight가 높은 부호율의 모델 행렬에 비해 sparse한 성질을 가진다.

그러나 하나의 모 행렬로 다양한 부호율을 지원하기 위해서는 모 행렬의 위쪽은 dense하게, 모 행렬의 아래쪽은 sparse하게 구조적으로 설정을 해야 한다. 그러나 본 발명은 낮은 부호율에서 sparse한 nonzero weight을 지원하게 설계를 하고 높은 부호율에서 행들의 조합(combine) 기법을 이용하여 dense한 성질을 만족하게 하므로 보다 효율적으로 LDPC 부호를 설계 할 수 있다.

Claims

패리티 검사 행렬을 이용하여 LDPC 부호화를 수행하는 방법에 있어서,

특정한 패리티 검사 행렬에 포함되는 복수의 행들을 하나의 행으로 조합하여 새로운 패리티 검사 행렬을 생성하는 단계; 및

상기 생성된 패리티 검사 행렬을 이용하여 수신 단으로 송신하려는 송신 정보에 대한 부호화를 수행하는 단계

를 포함하여 이루어지되

상기 조합되는 복수의 행들은, 정보어 부분에서 무게를 갖는 성분이 열 방향으로 중첩되지 않는 것을 특징으로 하는

패리티 검사 행렬을 이용하여 LDPC 부호화를 수행하는 방법
LDPC 부호를 이용하여 재전송을 수행하는 방법에 있어서,

복수의 행들이 조합한 행을 포함하는 패리티 검사 행렬을 이용하여 수신 단으로 송신하려는 송신 정보에 대한 제1 부호화를 수행하는 단계;

상기 부호화된 송신 정보를 상기 수신 단으로 송신하는 단계;

상기 수신 단으로부터 NACK 신호를 수신하는 경우, 상기 조합된 행을 상기 복수의 행들로 복원한 패리티 검사 행렬을 이용하여 상기 송신 정보에 대한 제2 부호화를 수행하는 단계; 및

상기 제2 부호화에 의해 추가로 생성된 패리티 비트를 상기 수신 단으로 송 신하는 단계를 포함하여 이루어지되,

상기 조합된 복수의 행들은, 정보어 부분에서 무게를 갖는 성분이 열 방향으로 중첩되지 않는 것을 특징으로 하는

LDPC 부호를 이용하여 재전송을 수행하는 방법