KR100881002B1

KR100881002B1 - 통신 시스템에서 지그재그 코드를 이용한 저밀도 패리티 검사 부호 생성 장치 및 방법

Info

Publication number: KR100881002B1
Application number: KR1020050014732A
Authority: KR
Inventors: 신동준; 홍송남
Original assignee: 삼성전자주식회사; 재단법인서울대학교산학협력재단
Priority date: 2005-02-22
Filing date: 2005-02-22
Publication date: 2009-02-03
Also published as: US20060190801A1; KR20060093627A

Abstract

본 발명은 무선 통신 시스템에서 다양한 부호율을 지원할 수 있는 저밀도 패리티 검사 부호(LDPC: Low Density Parity Check) 생성 장치 및 방법에 관한 것이다. 이를 위해 본 발명은, 다양한 부호율을 지원하는 저밀도 패리티 검사(LDPC, Low Density Parity Check) 부호 생성 방법에 있어서, 소정의 부호율에 대하여 최적의 성능을 나타내는 다수개의 패리티 체크 행렬들을 구하는 과정과, 상기 구해진 다수개의 행렬들의 각 서브 매트릭스 단위로 행(row)당 1의 개수를 일치시키는 과정과, 상기 다수개의 행렬들을 하나의 행렬로 변환하고, 각 부호율마다 생성되는 천공된 지그재그 부호를 하나의 천공된 지그재그 부호로 결합하는 과정을 포함한다.

지그재그(zigzag), LDPC, 천공, 절단, 가변 부호율, 패리티 체크 행렬

Description

통신 시스템에서 지그재그 코드를 이용한 저밀도 패리티 검사 부호 생성 장치 및 방법{APPARATUS AND METHOD FOR GENERATION OF LOW DENSITY PARITY CHECK CODE USING ZIGZAG CODE IN COMMUNICATION SYSTEM}

도 1은 일반적인 지그재그 부호를 도시한 도면,

도 2는 일반적인 ICZZ 부호의 부호화기의 구조를 개략적으로 도시한 도면,

도 3은 일반적인 ICZZ 부호의 직렬 복호화기를 개략적으로 도시한 도면,

도 4는 일반적인 ICZZ 부호의 하이브리드 복호화기의 구조를 개략적으로 도시한 도면,

도 5는 일반적인 ICZZ 부호의 Tanner 그래프를 도시한 도면,

도 6은 본 발명에 따른 RC-LDPC 부호의 부호화기의 실시예를 개략적으로 도시한 도면,

도 7a 및 도 7b는 일반적인 천공된 지그재그 부호의 Tanner 그래프를 도시한 도면,

도 8a 및 도 8b는 본 발명에 따른 천공 패턴을 설명하기 위해 도시한 도면,

도 9는 본 발명에 따른 RC-LDPC 부호의 부호화기 구조를 개략적으로 도시한 도면,

도 10은 본 발명에 따른 천공기의 동작 구성을 설명하기 위해 도시한 도면.

본 발명은 통신 시스템에 관한 것으로서, 특히 무선 통신 시스템에서 다양한 부호율을 지원할 수 있는 저밀도 패리티 검사 부호(LDPC: Low Density Parity Check, 이하 'LDPC'라 칭하기로 한다) 생성 장치 및 방법에 관한 것이다.

일반적으로, 통신 시스템에서 가장 근본적인 문제는 채널(channel)을 통하여 얼마나 효율적이고 신뢰성 있게 데이터(data)를 전송할 수 있느냐 하는 것이다. 최근에 활발하게 연구되고 있는 차세대 멀티미디어 이동 통신 시스템에서는 초기의 음성 위주의 서비스를 벗어나 영상, 무선 데이터 등의 다양한 정보를 처리하고 전송할 수 있는 고속 통신 시스템이 요구됨에 따라 시스템에 적절한 채널 부호화 기법을 사용하여 시스템의 효율을 높이는 것이 필수적이다.

그런데, 이동통신 시스템에 존재하는 무선 채널 환경은 유선 채널 환경과는 달리 다중 경로 간섭(multipath interference)과, 쉐도잉(shadowing)과, 전파 감쇠와, 시변 잡음과, 간섭 및 페이딩(fading) 등과 같은 여러 요인들로 인해 불가피한 오류가 발생하여 정보 손실이 발생한다. 상기 정보 손실은 실제 송신 신호에 심한 왜곡을 발생시켜 상기 이동 통신 시스템 전체 성능을 저하시키는 요인으로 작용하 게 된다. 일반적으로 이러한 정보의 손실을 감소시키기 위해 채널의 성격에 따라 다양한 에러 제어 기법(error-control technique)을 이용하여 시스템의 신뢰도를 높이는데, 이러한 에러 제어 기법 중에 가장 기본적인 방법은 에러 정정 부호(error-correcting code)를 사용하는 것이다.

상기 에러 정정 부호의 대표적인 부호들로는 터보 부호(turbo code)와, LDPC 등이 있다.

상기 LDPC 부호는 종래 에러 정정을 위해 주로 사용되던 길쌈 부호(convolutional code)에 비하여 고속 데이터 전송시에 성능 이득이 우수한 것으로 알려져 있으며, 무선 채널에서 발생하는 잡음에 의한 오류를 효과적으로 정정하여 데이터 전송의 신뢰도를 높일 수 있다는 장점을 가진다. 또한, 상기 LDPC 부호는 팩터(factor) 그래프 상에서 합곱 알고리즘(sum-product algorithm)에 기반한 반복 복호(iterative decoding) 알고리즘을 사용하여 복호할 수 있다는 장점을 가진다. 상기 합곱 알고리즘에 기반한 반복 복호 알고리즘을 사용하는 복호 방법을 사용함으로써 LDPC 부호의 복호기(decoder)는 터보 부호의 복호기에 비해 낮은 복잡도를 가질 뿐만 아니라 병렬 처리 복호기를 구현함에 있어 용이하게 된다.

상기 터보 부호는 Shannon의 채널 부호화 이론의 채널 용량 한계에 근접하는 우수한 성능을 가지고 있으며, 지금까지 알려진 최고의 성능을 가지는 LDPC 부호는 블록 크기 10⁷을 사용하여 비트 에러율(BER: Bit Error Rate) 10^-5에서 Shannon의 채널 부호화의 채널 용량 한계에서 단지 0.04[dB] 정도의 차이를 가지는 성능을 나타낸다. 여기서, 상기 Shannon의 채널 부호화 이론(channel coding theorem)은 채널의 용량을 초과하지 않는 전송률(data rate)에 한해 신뢰성 있는 통신이 가능함을 나타내는 이론이다. 블록(block) 크기가 굉장히 큰 랜덤(random) 부호는 Shannon의 채널 부호화 이론에서 채널 용량 한계에 근접하는 성능을 보이지만, MAP(maximum a posteriori) 또는 ML(maximum likelihood) 복호를 적용할 경우 계산량에 있어 굉장한 로드(load)가 존재하여 실제 구현이 불가능하였다.

그런데, 상기 LDPC 부호는 대부분의 엘리먼트(element)들이 0(NULL)의 값을 가지며, 상기 0의 값을 가지는 엘리먼트들 이외의 극히 소수의 엘리먼트들이 1의 값을 가지는 패리티 검사 행렬에 의해 정의되기 때문에, 즉, 상기 LDPC 부호의 패리티 검사 행렬은 매우 적은 개수의 가중치(weight)들을 가지기 때문에, 비교적 긴 길이를 가지는 블록 부호(block code)에서도 반복 복호를 통해 복호가 가능하며, 블록 부호의 블록 길이를 계속 증가시켜 가면 터보 부호와 같이 Shannon의 채널 용량 한계에 근접하는 형태의 성능을 나타낸다. 따라서, 상기 차세대 통신 시스템에서는 상기 에러 정정 부호로서 상기 LDPC 부호를 적극적으로 사용하고 있는 추세에 있다.

그러나, 상기 LDPC 부호의 경우 시공간 부호와 같이 생성 행렬을 이용하여 부호화를 수행할 경우 우수한 성능을 보장할 수가 없다. 즉, 상기 LDPC 부호의 경우 상기에서 설명한 바와 같이 패리티 검사 행렬의 가중치가 적어 복호화시 그 복잡도가 낮다는 장점을 가지고 있으나, 상기 패리티 검사 행렬을 생성 행렬로 변환 할 경우 상기 생성 행렬의 가중치가 증가하여 부호화시 그 복잡도가 증가하게 된다.

이에, 차세대 이동통신 시스템에서는 새로운 방식의 부호화 및 복호화 기법들이 활발히 연구되어 왔다. 이러한 예로서, Ping에 의해 제안된 상기 연접 지그재그(CZZ: Concatenated Zigzag, 이하 "CZZ"라 칭하기로 한다) 부호는 터보 부호와 LDPC 부호의 장점을 적절하게 결합한 특징을 가진다. 또한, 상기 CZZ 부호는 합곱 알고리즘에 의해서 복호가 이루어지므로, 상기 터보 부호보다 낮은 복호화와 복잡성을 가진다. 또한 상기 CZZ 부호는 높은 부호율에서는 상기 터보 부호보다 낮은 BER에서 오류마루 현상이 일어난다는 장점을 가진다. 그리고 상기 LDPC 부호에 비하여 부호화 복잡도가 낮다는 장점을 가진다.

하지만, 상기 CZZ 부호의 경우에는 CZZ 부호 자체가 가지는 오류 정정 능력이 상기 터보 부호나 LDPC 부호에 비하여 떨어진다는 문제점이 있다.

다음으로, 이하에서는 다양한 호환성을 가지는 가변 부호율(rate-compatible)을 가진 채널 부호에 대하여 살펴보기로 한다. 먼저 상기 가변 부호율을 가지는 채널 부호가 중요한 이유에 대하여 살펴보면 다음과 같다.

첫째, 알고리즘과 하드웨어 구현상 낮은 복잡도의 부호화 및 복호화가 가능하다.

둘째, Type-II 복합 자동 재전송 요구(Hybrid Automatic Repeat request, 이하'HARQ'라 칭하기로 한다) 구현에 용이하다. 특히 중복분 증가(Incremental Redundancy, 이하 'IR'이라 칭하기로 한다) 스킴(scheme)에 기반한 방식을 사용할 경우 가변 부호율에 대한 천공 패턴(puncturing pattern)은 필수적인 요건이다.

셋째, 채널 상태에 따라서 변조 방식과 부호율을 변화시키는 적응적 변조 및 코딩(Adaptive Modulation and Coding, 이하 'AMC'라 칭하기로 한다) 구현에 용이하다.

먼저, 상기 HARQ에서 Type-I HARQ 기법은 오류정정에서 오류검출을 위해 FEC(Forward Error Correction)를 오류검출 부호로 사용하며, 자동 재전송 요구(Automatic Repeat request, 이하 'ARQ'라 칭하기로 한다) 기법을 이용하여 재전송을 요구한다. 상기 기법은 오류 패턴을 정정해야 하고 즉시 다른 오류 패턴을 검출해야 하기 때문에 각각의 전송에 오버헤드(overhead)가 증가하는 단점이 있다. 따라서 상기 Type-I HARQ의 단점을 보완하여 나온 기법이 상기 Type-II HARQ 기법이며, 이를 위한 가변 잉여 부호(Variable Redundancy Code)의 개념은 Mandelbaum에 의해 처음 소개 되었으며, 또한 이를 기반으로 구현한 Type-II HARQ 기법은 Lin과 Yu, Metzner, Wang과 Lin에 의해 제안 되었다.

즉, 통상적인 메시지는 오류 검출만을 위한 패리티 검사 비트들과 함께 부호화 된다. 이때, 수신기에서는 수신된 블록을 버퍼에 저장하고 오류를 검출한다. 상기 오류 검출 시 재전송 요청에 의해 송신기는 패리티 체크 비트(parity check bit)의 블록을 전송하게 되며, 상기 수신기는 이를 버퍼에 저장되어 있던 블록의 오류를 정정하기 위해 사용한다. 이때, 상기에서 오류가 성공적으로 정정되었다면 그 블록은 사용자에게 전송되고, 오류가 정정되지 못했다면 송신기 측에 다시 재전 송을 요구하게 된다.

상기와 같이, 오류정정을 위한 부호와 재전송의 방법을 적절하게 선택한다면 Type-I 보다 Type-II가 더 좋은 성능을 제공하게 된다. 이를 위해서 다양한 호환성을 위한 천공 패턴에 해당하는 패리티 체크 비트들을 순차적으로 이용하게 되면, 각각의 전송률에 해당하는 오류 정정 능력에 따라 처리율(throughput)이 높아지게 된다. 따라서 좋은 성능을 가진 가변 부호율 구현이 가능한 부호(Rate-Compatible Code)를 사용하는 것이 Type-II HARQ의 처리율을 높이는데 가장 중요하다.

다음으로, 상기 AMC(Adaptive Modulation and Coding)는 채널 환경에 따라서 다양한 변조 기법과 부호율을 적절하게 조합하여 사용하는 기법이다. 상기 AMC를 사용함으로써 원하는 프레임 에러율(FER; Frame Error Rate)에 대한 평균 처리율을 최대화시킬 수 있다. 3세대 시스템의 하향링크에서는 5Mbps까지의 데이터 전송률을 제공하고 HSDPA(High Speed Downlink Packet Access)는 최대 데이터 전송률 10.8Mbps를 제공하며, 이를 위한 핵심 기술로서 상기한 바와 같은 AMC 와 HARQ를 사용한다.

상기 차세대 이동통신 시스템에서는 HSDPA보다 높은 전송률이 요구되므로 차세대 이동통신을 위한 AMC 기법은 3세대나 HSDPA에서 사용된 방법보다 다양한 부호율과 변조기법의 조합으로 구성되어야 한다. 그러기 위해서 사용되는 채널 부호는 다양한 부호율이 필요하며, 하드웨어나 알고리즘상의 복잡도를 줄이기 위해서는 낮은 부호율의 원 부호(mother code)를 천공함으로써, 다양한 부호율을 구성하는 것이 가장 효과적이며, 다양한 프레임 길이에 대해서 좋은 성능을 가져야 한다.

한편, 가변 부호율 길쌈 부호는 가변 부호율 제한을 천공 방법에 추가하는 것으로 획득한다. 여기서, 상기 제한은 적당한 천공 패턴을 사용하여 낮은 부호율의 모든 부호들이 높은 부호율 부호의 모든 부호화된 비트들로 사용되는 방법으로 구성된 부호율을 필요로 한다. 이러한 개념은 터보 부호에 확장되었으며 RCTC(Rate Compatible Turbo Codes)라고 불린다. 상기한 터보 부호는 낮은 가중치 부호어(low-weight codewords)에 의한 적정한 신호대 잡음비(SNR; Signal to Noise Ratio) 범위에서의 오류 마루(error floor)를 가진다. 특히 높은 부호율과 짧은 프레임 길이에 대해서 상기 오류 마루의 영향은 보다 심각해지며, 신뢰성 있는 데이터 전송에 심각한 문제를 발생하게 된다. 즉, 종래 기술에서는 상술한 바와 같이 천공만으로 부호율을 조절함으로써, 천공 노드(puncturing node)의 비율이 너무 높아져서 성능의 저하가 크게 되며, 이로 인하여 오류 마루(error floor) 현상이 심각해지는 문제점을 가진다.

따라서, 현재 LDPC 부호를 이용한 가변 부호율을 갖는 채널 부호를 설계하는 연구가 활발히 진행 중이다.

따라서 본 발명은 상술한 종래 기술의 문제점을 해결하기 위하여 창안된 것으로서, 본 발명의 목적은, 통신 시스템에서 심볼 천공(puncturing) 및 절단(pruning)을 이용하여 다양한 부호율을 지원할 수 있는 가변 부호율 LDPC 부호 설계 방법 및 장치를 제공함에 있다.

본 발명의 다른 목적은, 각각의 특정 부호율에 대응하게 설계된 ICZZ 부호들과 동일한 성능을 나타내고, 가변 부호율의 지원에 따른 성능 열화를 제거할 수 있는 가변 부호율 LDPC 부호 설계 방법 및 장치를 제공함에 있다.

본 발명의 또 다른 목적은, 가능한 짧은 주기를 정하고, 상기 정해진 주기 내에서 천공되지 않은 패리티 비트들이 일정한 간격을 가질 수 있는 가변 부호율 LDPC 설계 방법 및 장치를 제공함에 있다.

본 발명의 또 다른 목적은, 통신 시스템에서 사용되는 채널 부호화 기법을 사용하여 시스템의 효율을 높일 수 있도록 하는 채널 부호화 방법 및 장치를 제공함에 있다.

본 발명의 또 다른 목적은, 통신 시스템에서 사용되는 부호의 성능 향상을 통해 부호율에 대해서 최상의 성능을 유지할 수 있도록 하고, 부호화 복잡도 및 복호 지연을 줄일 수 있도록 하는 채널 부호화 방법 및 장치를 제공함에 있다.

본 발명의 또 다른 목적은, 다양한 부호율에 관계없이 항상 최적의 성능 및 복호 지연을 유지할 수 있도록 하는 채널 부호화 방법 및 장치를 제공함에 있다.

상기와 같은 목적들을 달성하기 위한 본 발명의 방법은, 다양한 부호율을 지원하는 저밀도 패리티 검사(LDPC, Low Density Parity Check) 부호 생성 방법에 있어서, 소정의 부호율에 대하여 최적의 성능을 나타내는 다수개의 패리티 체크 행렬들을 구하는 과정과, 상기 구해진 다수개의 행렬들의 각 서브 매트릭스 단위로 행(row)당 1의 개수를 일치시키는 과정과, 상기 다수개의 행렬들을 하나의 행렬로 변환하고, 각 부호율마다 생성되는 천공된 지그재그 부호를 하나의 천공된 지그재그 부호로 결합하는 과정d을 포함한다.

상기와 같은 목적들을 달성하기 위한 본 발명의 다른 방법은, 다양한 부호율을 지원하는 저밀도 패리티 검사(LDPC, Low Density Parity Check) 부호 생성 방법에 있어서, 천공 패턴의 가장 짧은 주기를 결정하는 과정과, 상기 결정된 주기 내에서 천공되지 않은(unpunctured) 패리티 비트들이 일정한 간격을 가지도록 천공되지 않은 패리티 비트들의 위치를 결정하는 과정을 포함한다.

상기와 같은 목적들을 달성하기 위한 본 발명의 장치는, 다양한 부호율을 지원하는 저밀도 패리티 검사(LDPC, Low Density Parity Check) 부호 생성 장치에 있어서, 지그재그 부호화기와, 입력 정보 비트들을 분할하는 디바이더를 포함하며, 상기 디바이더를 통해 분리된 정보 비트들을 입력하고, 상기 입력 정보 비트들에 대하여 천공 패턴이 0(Null)인 상기 지그재그 부호화기로의 입력을 절단(pruning)하는 절단기와, 상기 지그재그 부호화기를 통한 지그재그 부호들에 대하여 행(row)당 1의 개수를 일치시키기 위한 천공(puncturing)을 수행하는 천공기를 포함한다.

이하 첨부된 도면을 참조하여 본 발명의 바람직한 실시예를 상세히 설명하기로 한다. 그리고 하기에서 본 발명을 설명함에 있어서, 관련된 공지 기능 또는 구성에 대한 구체적인 설명이 본 발명의 요지를 불필요하게 흐릴 수 있다고 판단되는 경우에는 그 상세한 설명을 생략한다.

본 발명의 상세한 설명에 앞서, 본 발명의 실시예에 따른 지그재그(Zigzag) 부호를 이용한 구조화된(structured) 저밀도 패리티 검사(Low Density Parity Check, 이하 'LDPC'라 칭하기로 한다) 부호 즉, 불규칙한 연접 지그재그(Irregular Concatenated Zigzag, 이하 'ICZZ'라 칭하기로 한다) 부호에 대하여 살펴보기로 한다.

먼저, LDPC 부호의 부호화 계산량을 줄이는 방법 중의 하나로 패리티 체크(parity-check) 행렬 H에서, 패리티 비트(parity bits)에 상응하는 부분을 이중 사선(Dual Diagonal) 형태로 나타낼 수 있다. 상기와 같이 패리티 체크 행렬 H의 패리티 비트에 상응하는 부분을 이중 사선 형태로 나타내면, 패리티 생성 블록을 누적기(Accumulate)로 나타낼 수 있다. 상기 행렬 H 중 불규칙하게 결정되는 규칙적인 데이터(systematic data) 부분은 반복 부호(repetition code)와 인터리버(interleaver)의 결합으로 나타낼 수 있다. 일반적으로 LDPC 부호 중에서 H 행렬 구조에 제한을 두어서 부호화 계산량을 줄이는 LDPC 부호군을 구조화된 LDPC(structured-LDPC) 부호라고 한다. 이하, 상기 ICZZ 부호에 대하여 설명한다.

상기 ICZZ 부호는 일반적인 LDPC 부호에 비하여 2 방향 스케줄링(two-way scheduling)을 적용할 수 있으므로, 적은 수의 반복(iteration)으로 좋은 성능을 보여줄 수 있는 장점이 있다. 또한, 상기 ICZZ 부호는 상기 구조화된 LDPC 부호의 한 예로서 부호화 계산량이 적다는 장점을 갖는다. 또한 상기 ICZZ 부호는

와

로 규정되며, 여기서, R_i는 i번째 지그재그 부호화기에 입력되는 정보 비트의 비율을 나타내고, 상기 d_c(i)는 i번째 지그재그 부호화기에 사용되는 지그재그 부호의 파라미터 값을 나타낸다. 즉, 상기 ICZZ 부호는 지그재그 부호화기에 입력되는 정보 비트의 비율(R_i)과 상기 지그재그 부호화기가 사용하는 부호의 파라미터(d_c(i)-2)에 의하여 규정된다. 예를 1번째 지그재그 부호화기에서 후술하는 도 2에 도시된 지그재그 부호를 사용하면 상기 d_c(1)=4가 된다. 예컨대, d_c(i)-2는 i번째 지그재그 부호화기가 (d_c(i)-2)-지그재그 부호를 사용한다는 것을 의미한다. 이하, 첨부한 도면을 참조하여 상기 지그재그 부호 및 ICZZ 부호에 대하여 살펴보기로 한다.

도 1은 일반적인 지그재그 부호를 나타내는 도면이며, 도 2는 일반적인 ICZZ 부호의 부호화기의 구조를 개략적으로 도시한 도면이다.

상기 도 1을 참조하면, 상기 도 1은 지그재그 부호를 도시한 도면으로서, 파라미터 값으로 2를 가지는 지그재그 부호를 나타낸 것이다. 상기 도 2에 도시한 바와 같이, 흰색 원 예컨대, 참조부호 101은 정보 비트(information bits)를 나타내고, 검은색 원 예컨대, 참조부호 103은 패리티 비트(parity bits)를 나타내며, 점선 원 예컨대, 참조부호 105는 세그먼트(segment)로 정의된다. 또한 상기 패리티 비트들은 상기 도 1에 나타낸 바와 같이 상기 세그먼트에 속해있는 비트들이 짝수 패리티를 만족시키도록 결정된다.

상기 도 1의 예에서와 같이, 상기 파라미터 값이 2인 것은 상기 정보 비트 2개의 비트마다 패리티 비트가 1개씩 생성된다는 것을 의미한다.

다음으로, 상기 ICZZ 부호의 부호화기의 구조는 상기 도 2에 나타낸 바와 같다. 상기 도 2는 지그재그 부호의 수(N_s)가 4개 즉, N_s=4인 경우의 ICZZ 부호화기를 나타낸 것이다.

도 2를 참조하면, 정보 비트 블록(201)과, 디바이더(Divider)(203)와, 서브 블록(205)과, 인터리버(interleaver)(207) 및 지그재그 부호화기(209)를 포함한다. 상기 인터리버(207)와 지그재그 부호화기(209)는 일반적으로 시스템 설정에 상응하여 구성되며, 여기서는 상기 지그재그 부호의 수(N_s)에 상응하여 4개씩 구성된다.

상기 도 2에 나타낸 바와 같이 지그재그 부호의 수가 4개인 경우의 ICZZ 부호화기를 예로한 부호화 과정을 살펴보면 다음과 같다.

(1) 길이 n_I인 정보 비트 블록(201)은 상기 디바이더(203)에 입력되고, 상기 디바이더(203)에서는 상기 지그재그 부호화기(209)에 입력되는 정보비트의 수 R(i)의 값에 따라서 각 지그재그 부호에 입력되는 지그재그 부호의 수 N_s개의 서브 블록들(205)을 결정한다.

(2) 상기 N_s개의 서브 블록들(205) 각각은 해당되는 인터리버(207)에 입력된다. 이때, 상기 N_s개의 인터리버들(207)의 크기는 해당하는 상기 서브 블록들(205)의 크기와 일치한다.

(3) 상기 인터리버들(207)을 통해 각각 인터리빙된 서브 블록들(205)은 자신에게 해당되는 지그재그 부호화기(209)에 각각 입력된다. 여기서, 상기 지그재그 부호화기(209)의 부호화 과정은 하기 <수학식 1>과 같이 나타낼 수 있다.

상기 <수학식 1>에서 상기 I(j)는 j번째 정보 비트를 나타내며, 상기 d_c(i)는 i번째 지그재그 부호화기에 사용되는 지그재그 부호의 파라미터 값을 나타낸다.

이상에서는 ICZZ 부호 부호화기에 대하여 살펴보았다. 이하에서는 상기 ICZZ 부호의 복호화기에 대하여 설명한다.

먼저, ICZZ 부호는 불규칙(irregular) LDPC 부호의 한 예로서 일반적으로 LDPC 부호의 복호화(decoding)에 이용되는 합곱(sum-product) 알고리즘에 의해서 복호 될 수 있다. 또한 ICZZ 부호의 각 서브 매트릭스(sub-matrix)들은 사이클(cycle)이 없는 트리(Tree) 구조를 이루고 있으므로, 직렬 복호화기(Serial decoder) 형태로 복호 될 수 있다.

상기 직렬 복호화기는 상기 합곱 알고리즘을 사용할 때와 비교하여 적은 수의 연산량에 의해 같은 성능을 보여줄 수 있는 장점을 갖는다. 하지만 복호 지연 시간이 상기한 합곱 알고리즘에 비하여 긴 단점을 갖는다. 따라서, 시스템에서 필요한 요구 조건에 상응하여 복호 지연 시간과 연산량 중에서 그 중요도에 따라서 적응적으로 복호 알고리즘을 선택하여 사용하는 것이 바람직하다.

그러면, Ping에 의해서 제안된 상기 직렬 복호화기와 합곱 알고리즘이 혼합 된 형태의 복호 알고리즘에 대하여 살펴보기로 한다.

가) 합곱 알고리즘, 즉 병렬 복호화기(Parallel decoder)에 대하여 설명한다.

일반적으로, ICZZ 부호는 검사 노드와 변수 노드로 구성되는 Tanner 그래프로 표현될 수 있으므로 합곱 알고리즘에 의하여 복호화 될 수 있다. 즉, 한번의 반복(One iteration)동안 상기 변수 노드는 상기 검사 노드로 메시지를 전달하고, 상기 검사 노드는 상기 변수 노드로부터 입력된 메시지를 이용하여 검사 노드에서의 프로세싱(processing)을 수행한다. 이어서, 상기 프로세싱을 통한 새로운 메시지를 상기 변수 노드로 전달한다. 그러면, 상기 변수 노드는 상기 검사 노드로부터 전달받은 새로운 메시지를 이용하여 변수 노드에서의 프로세싱을 수행한 후 다시 상기 검사 노드로 전달한다. 이러한 과정은 단지 직접 연결된 노드들 사이에서만 이루어지고 각 변수 노드마다 동시에 진행된다. 따라서, 상기 합곱 알고리즘을 이용한 복호는 한번의 반복동안 필요한 복호 시간이 짧다는 장점을 가진다. 하지만, 상기와 같이 단지 직접 연결된 노드들에 의해서만 메시지들이 업데이트(update)되므로 수렴 속도(convergence speed)가 느리다는 단점이 있다.

나) 직렬 복호화기에 대하여 설명한다.

직렬 복호화기를 이용하는 방법은 일반적인 LDPC 부호에는 적용할 수 없으며 상기한 ICZZ 부호와 같이, 서브 매트릭스가 사이클이 없는 트리 구조를 이루고 있는 LDPC 부호에만 적용할 수 있다. 여기서, 상기 도 2에 대응되는 ICZZ 부호의 직렬 복호화기의 구조를 살펴보면 하기 도 3과 같다.

도 3은 일반적인 ICZZ 부호의 직렬 복호화기를 개략적으로 도시한 도면이다.

상기 도 3을 참조하면, 파라미터

는 정보 비트들(information bits)에 해당하는 초기 선험적 LLR(initial a priori LLR) 벡터(vector)를 나타내며, 파라미터

는 m번째 복호화기에서 정보 비트들에 해당하는 선험적 LLR 벡터를 나타내며, 파라미터

는 m번째 복호화기에서 정보 비트들에 해당하는 후험적 LLR(a posteriori LLR) 벡터를 나타내며, 파라미터

는 m번째 복호화기에서 패리티 비트들(parity bits)에 해당하는 선험적 LLR 벡터를 나타내며, 파라미터

는 m번째 복호화기에서 전달하는 외적 LLR(extrinsic LLR) 벡터를 나타낸다.

상기의 파라미터들 중에서 m번째 복호화기에서 전달하는 외적 LLR 벡터인 상기

은 하기 <수학식 2>와 같이 정의할 수 있다.

상기 <수학식 2>에서 상기

은 바로 이전의 반복(iteration)에서 계산된 외적 LLR 벡터를 나타낸다.

또한 상기 직렬 복호화기를 이용하는 ICZZ 부호의 복호화 알고리즘은 하기 <수학식 3> 및 <수학식 4>와 같이 나타낼 수 있다.

첫 번째 반복(iteration):

첫 번째 반복(iteration) 후:

상기 <수학식 4>에서 상기

은 m번째 복호화기(Dec-m)에서 계산된다. 여기서, 상기 값은 실제 m번째 복호화기에서는 사용되는 값이 아니므로 상기 도 3에 나타낸 바와 같이 상기

을 빼주는 부분이 존재한다.

다) 하이브리드 복호화기(Hybrid Decoder)에 대하여 설명한다.

하이브리드 복호화기의 각 서브 복호화기에서 연산하는 과정은 상술한 직렬 복호화기의 서브 복호화기에서와 동일한 연산 과정을 수행한다. 하지만, 상기 하이브리드 복호화기는 상기 각 서브 복호화기들의 배치를 병렬(parallel)로 연결함으로써, 상기한 직렬 복호화기보다 복호 지연 시간을 줄일 수 있도록 구현된다. 이를 통해, 상기 직렬 복호화기가 서브 복호화기의 수에 비례하여 지연 시간이 길어지는 반면에, 상기 하이브리드 복호화기는 서브 복호화기의 수와 관계없이 지연 시간이 일정하다는 장점을 가진다. 그러므로 많은 서브 복호화기를 필요로 하는 경우에는 상기 직렬 복호화기에 비하여 하이브리드 복호화기가 더 효율적이다. 하지만 상기 직렬 복호화기와 동일한 성능을 보여주기 위한 연산량은 상기 직렬 복호화기에 비하여 좀 더 필요하다. 하기 도 4는 상기 도 3에 대응되는 하이브리드 복호화기의 구조를 나타낸 것이다.

도 4는 일반적인 ICZZ 부호의 하이브리드 복호화기의 구조를 개략적으로 도시한 도면이다.

도 4를 참조하면, 상기 하이브리드 복호화기는 병렬 연결 구조를 가지는 다수개의 서브 복호화기 즉, Dec-1 내지 Dec-4와, LLR 벡터 연산부(410)를 포함한다. 상기 LLR 벡터 연산부(410)는 외적 LLR 벡터(a extrinsic LLR)를 연산하는 역할을 담당한다.

한편, 상기 하이브리드 복호화기를 이용하는 복호화(decoding) 알고리즘은 상기한 직렬 복호화기에서와 유사하다. 다만, 상기 하이브리드 복호화기에서는 하기 <수학식 5>에 나타낸 바와 같이 후험적 LLR 벡터(a posterior LLR vector)를 연산하는 과정에서 그 차이를 가진다.

상기 <수학식 5>에 나타낸 바와 같이, 상기 하이브리드 복호화기는 단지 이전의 반복(previous iteration)에서 구해진 상기 외적 LLR 벡터를 이용한다. 따라서, 현재의 반복(current iteration)에서 구해지는 외적 LLR 벡터를 이용하는 상기 직렬 복호화기에 비하여 수렴 속도(convergence speed)가 느림을 알 수 있다. 즉, 더 많은 반복(iteration)이 필요함을 알 수 있다.

그러면 이하에서는, 상기에서 살펴본 바와 같은 ICZZ 부호에 대한 설계 방법에 대하여 살펴보기로 한다.

먼저, 상기 ICZZ 부호는 상술한 바와 같이 구조화된 LDPC(structured-LDPC) 부호의 한 가지 형태로서, 하기 <수학식 6>과 같이 패리티 체크(parity check) 행렬로 나타낼 수 있다.

상기 <수학식 6>에 나타낸 바와 같이, 상기 ICZZ 부호의 패리티 체크 행렬은 N_s개의 서브 매트릭스로 나누어져 있으며, 각각의 서브 매트릭스는 제로 매트릭스(all-zero matrix)와 두 개의 비제로 매트릭스(non-zero matrix)

와

로 나누어진다. ICZZ 부호는 규칙적인(systematic) 부호로서 패리티 체크 행렬에서 정보 비트에 해당되는 부분과 패리티 비트에 해당되는 부분이 구분되어 있다. 즉, 상기 <수학식 6>에서 상기

는 선택된 정보 비트들에 해당되는 부분을 나타내고, 상기

는 패리티 비트들에 해당되는 부분을 나타낸다.

또한, 패리티 비트인 상기

는 항상 일정한 형태(Accumulate Form)를 가지는데, 이를 표현하면 하기 <수학식 7>과 같이 나타낼 수 있다.

한편, 상기에서 살펴본 ICZZ 부호의 파라미터인 R(i)와 d_c(i)는 상기 패리티 체크 행렬을 구성함에 있어서 각각 다음과 같은 역할을 한다.

즉, 상기 R(i)는 i 번째 서브 매트릭스에서 비제로 열(non-zero column)의 비율을 나타낸다. 만약 상기 R(i)가 1보다 작은 경우, 상기 비제로 열들은 상기 선택된 정보 비트인

의 오른쪽에 위치하게 된다. 그리고 상기 비제로 열에서 1의 위치는 부호화기에서 사용된 인터리버에 의하여 결정된다. 또한 상기 d_c(i)는 행렬 S_i의 각 행(row)에서 1의 개수를 나타내며, 상기 d_c(i)는 부호화기에서 사용된 지그재그(zigzag) 부호의 파라미터 값에 의하여 정해진다.

상기 ICZZ 부호의 패리티 체크 행렬 H의 크기는

와 같이 나타내며, 상기 n_P는 패리티 비트들의 수를 나타낸다. 이를 이용하여 상기 패리티 체크 행렬 H의 서브 매트릭스인

와

의 크기 및 상기 ICZZ 부호의 부호율(R)을 나타내면, 각각 하기 <수학식 8> 및 <수학식 9>와 같이 정의할 수 있다.

삭제

상기 <수학식 9>에 나타낸 부호율 식에서 알 수 있듯이 정해진 부호율에 대하여 상기 R(i)와 d_c(i)를 변화시키면서 다양한 ICZZ 부호의 구조를 설계할 수 있다. 이때, 상기와 같은 구조들 중에서 그 성능이 가장 좋은 부호를 찾는 것은 매우 중요한 문제이다.

한편, 상기 ICZZ 부호를 설계하는 과정은, 일반적으로 LDPC 부호에 적용되는 밀도 진화(Density Evolution) 기법을 이용하며, 상기한 파라미터 R(i)와 d_c(i)를 이용하여 첨부한 도면 도 5와 같은 Tanner 그래프를 구성할 수 있다.

도 5는 일반적인 ICZZ 부호의 간단한 Tanner 그래프를 도시한 도면이다.

도 5를 참조하면, 상기 ICZZ 부호는 체크 노드들(Check nodes)과, 정보 노드들(information nodes)을 가진다. 즉, 상기 도 5에서 사각 형태로 표시된 체크 노드와 원 형태로 표시된 정보 노드를 가지며, 상기 정보 노드는 상기 체크 노드와 연결되는 가변 노드를 선택한다.

도 5를 수식으로 나타내면, 하기 <수학식 10>과 <수학식 11>과 같은 귀납(recursion) 식으로 정의할 수 있다.

또한, 상기 <수학식 11>에서 상기

는 하기 <수학식 12>와 같이 나타낼 수 있다.

,

한편, 상기 <수학식 10> 내지 <수학식 12> 과 각각의 파라미터를 구하는 과정은 일반적인 LDPC 부호에서 사용되는 이론과 동일하므로 이하에서는 그에 대한 설명은 생략하기로 한다. 다만, 본 발명의 실시예에서 적용되는 ICZZ 부호에 상응하는 <수학식 10> 내지 <수학식 12>를 구한 것만 차이를 가진다.

상기 <수학식 10> 내지 <수학식 12>에서 상기

와

는 Type-j 검사 노드에서 정보 노드와 패리티 노드로 지나는 메시지의 평균값으로 정의한다. 상기

는 Type-k 정보 노드에서 Type-j 검사 노드로 지나는 메시지의 평균으로 정의한다. 상기

는 Type-j 검사 노드에 연결된 모든 정보 노드 중에서 Type-k 정보 노드에 연결된 선의 비율로 정의된다. 상기

는 멀티 에지(multi-edge) 차수를 나타내는 파라미터를 의미한다. 마지막으로, 상기

는 Type-i 정보 노드와 Type-k 검사 노드 사이에 연결된 에지(edge)의 수를 나타낸다.

그러면, 이하 상기 <수학식 10> 내지 <수학식 12>를 참조하여 상기한 바와 같은 좋은 파라미터를 계산하는 과정에 대하여 살펴보기로 한다.

즉, 좋은 파라미터를 계산하는 과정은 먼저, 정해진 부호율에 대하여 가장 작은 m₀에서 상기

와

가 무한대의 값으로 수렴할 수 있는 파라미터

,

및

를 각각 구한다. 다음으로, 상기

와

로부터 부호화 과정에서 사용되는 파라미터 R(i)로 변화시킨다. 여기서, 상기

로부터 하기 <수학식 13>에 의하여 f_k를 구할 수 있다.

또한, 상기 R(i) 값은 하기 <수학식 14> 및 <수학식 15>에 의하여 계산한다.

, 이고

,

상기 <수학식 14> 또는 <수학식 15>에서 상기

와

는 집합

에서 대표적인 엘리먼트(element) 값과 엘리먼트의 수를 각각 나타낸다. 상기 집합

의 모든 엘리먼트는 동일한 값을 가지며, 그 값을 상기

라 한다. 또한 상기 집합

의 엘리먼트 수를 상기

라고 한다. 상기와 같이, 상기의 수학식들에 의하여 주어진 상기

와

로부터 집합

를 구할 수 있으며, 상기 집합 로부터 R(i)를 구할 수 있다. 이를 예를 들어 살펴보면 다음과 같다.

먼저, 제1 실시예로서, 상기 집합

에 대하여

,

인 경우를 가정하면, 원하는 파라미터 R(i)는 하기 <수학식 16>과 같이 정의할 수 있다.

다음으로, 제2 실시예로서, 부호율 1/2인 ICZZ 부호를 가정하면 다음과 같다.

먼저, 상기에서 살펴본 바와 같은 방법으로 구한 부호율 1/2에서 최적의 성능을 보여주는 ICZZ 부호의 파라미터는 하기 <표 1>과 같이 나타낼 수 있다.

상기 <표 1>에 나타낸 바와 같이, 상기 <표 1>의 상기 각 파라미터를 이용하여 상기한 <수학식 13> 내지 <수학식 15>에 대입하면 부호화기에서 사용되는 파라미터를 구할 수 있다. 상기 부호화기에서 사용되는 파라미터는 하기 <표 2>와 같이 나타낼 수 있다.

이상에서는 본 발명의 실시예에 따른 ICZZ 부호에 대한 정의를 살펴보았다. 그러면 이하에서는 가변 부호율(RC; Rate compatible) LDPC 부호에 대하여 설명한다.

먼저, 본 발명에 따른 상기 가변 부호율(rate-compatible) LDPC 부호는 하나의 부호화기를 사용하여 다양한 부호율을 지원할 수 있는 부호를 의미한다. 즉, 낮은 부호율을 지원하는 경우에 복호 과정에서 사용되는 천공되지 않은 패리티 비트들(unpunctured parity bits)은 그 보다 높은 부호율을 지원한 경우에 사용되었던 천공되지 않은 패리티 비트들을 포함하여야 한다. 이러한 특징은 가변 부호율 LDPC 부호가 IR를 기반으로 하는 Type-II HARQ 시스템에 적합함을 의미한다.

이하에서는, 심볼 천공(puncturing)이나 절단(pruning)을 이용하여 다양한 부호율을 지원할 수 있는 제안하는 본 발명에 따른 가변 부호율 LDPC(rate compatible LDPC, 이하 'RC-LDPC'라 칭하기로 한다) 부호를 설계하는 방법에 대하여 설명한다. 상기와 같이 제안하는 본 발명은 각각의 특정 부호율에 맞게 설계된 ICZZ 부호들과 거의 동일한 성능을 보여주는 구조이므로, 가변 부호율의 지원에 따른 성능 열화가 거의 없다는 장점을 갖는다. 상기에서 높은 부호율은 미리 설정된 부호율보다 높은 부호율을 가지는 부호율을 의미하고, 상기 낮은 부호율은 미리 설정된 부호율보다 낮은 부호율을 가지는 부호율을 의미한다.

도 6은 본 발명에 따른 RC-LDPC 부호의 부호화기의 실시예를 개략적으로 도시한 도면이다.

도 6을 참조하면, 도 6은 본 발명의 실시예에 따른 RC-LDPC 부호화기를 나타낸 것이다. 특히 상기 도 6에서는 각각의 지그재그 부호화기(zigzag encoder)의 출력 값들을 천공하기 위한 천공기를 포함하는 설계 구조의 예를 나타낸 것으로서, 정보 비트 블록(601)과, 디바이더(Divider)(603)와, 서브 블록(605)과, 절단기(pruner)(607)와, 인터리버(interleaver)(609)와, 지그재그 부호화기(611) 및 천공기(puncturer)(613)를 포함한다.

삭제

도 6에 도시한 바와 같이, 상기 천공기(613)는 각 지그재그 부호화기(611) 별로 각각 설계된다. 즉, 상기 도 6에서 상기 각각의 지그재그 부호화기(611)에 상응하여 천공기 P₁, P₂, P₃, P₄가 일대일로 각각 설계된다.

이하, N_R개의 부호율

(

)을 지원하는 RC-LDPC 부호를 설계하는 경우를 고려하여 상기 RC-LDPC 부호를 설계하는 과정을 살펴보면, 크게 다음과 같이 세 부분으로 나누어진다.

(1) 상기 N_R개의 부호율에 대하여 각각 좋은 성능을 보여주는 패리티 체크 행렬 H_i(

)을 상기 ICZZ 부호에서 살펴본 방법에 의하여 구하면 하기 <수학식 17>과 같이 정의할 수 있다.

단, 본 발명에서는 파라미터를 구하는 과정에 있어서 하기 <수학식 18>과 같은 조건을 만족시키도록 한다.

상기 <수학식 18>에서 상기 R^k(i)는 상기 <수학식 17>에 나타낸 바와 같은 패리티 체크 행렬 H_i에서 상기

의 비제로 열(non-zero column)의 비율을 나타내며, 상기 R^j(i)는 시스템 설정에 따른 부호율(code rate)에 해당하는 패리티 체크 행렬의 i번째 서브 매트릭스를 나타내고, 상기 k, j 및 i는 임의의 변수를 나타 낸다.

(2) 일반적인 천공비트 이론(Theorem)에 의하여 상기

(

)들의 행(row)당 1의 개수를 일치시킨다. 상기 과정은 지그재그 부호를 가능한 다른 체크 노드 차수(degree)를 가진 천공된 지그재그(punctured zigzag) 부호로 대체하는 것이다. 여기서 상기 천공비트 이론은 후술되므로, 여기서는 그 설명을 생략하기로 한다.

(3) 행렬 H를 구성하기 위해 상기 (2)에서 얻어진 구성 지그재그 부호에 해당하는 천공 패턴은 가변 부호율의 제약 조건을 만족하도록 수정되어야 한다.

한편, 상기 (1)에서

(

) 는 후술하는 도 7a 및 도 7b에서처럼 설계 될 수 있으며, 다음 절 A 와 B에서 상기 (2) 와 (3)을 설명한다. 또한, 이하에서는 후술하는 도 7a 및 도 7b에서와 같이 지그재그 부호화기로부터 매 p 개 패리티 비트의 마지막 p - 1 비트를 천공하기 위해 천공 패턴으로 (p) 라는 표기를 사용하기로 한다.

A. 이하, 상기 (2)를 상세하게 설명하겠다. 먼저,

를 사용한 RC-LDPC 부호의 패리티 채크 행렬 H 를 구성하기 위해

의 행에서 1의 개수는 상기 (2)에서 가정했던 것처럼 일정하도록 만들어야한다. 상기 패리티 체크 행렬 H 의 i번째 서브 매트릭스 S_i는

를 사용하여 구성된다. 여기서

는

-지그재그 부호를 말한다. 만약

면

는 S_i의 구성에 영향을 주지 않는다. 천공비트 이론으로부터 각 지그재그 부호는 성능 열화 없이 적절한 천공된 지그재그 부호로 대체 할 수 있다. 다시 말해서,

의 행에서 1의 개수는 다음과 같은 절차에 의해 일치 시킬 수 있다.

1. d_c(i)는 패리티 체크 행렬 H 의 i번째 서브 매트릭스의 행에서 1의 개수를 나타내며, 다음의 계산식

로 계산 된다. 여기서, 상기 gcd는 최대 공약수를 나타낸다. 만약 상기

가 어떤 n 에 대해 정의 되지 않으면 상기 gcd 연산에서 제외 한다. 또한, 상기 수학식은 행(row)당 1의 개수를 일치하기 위해서 만족할 수 있는 최대의 값을 나타내며, 천공되는 비트의 수를 줄이기 위해 최대의 값을 가진다.

2. 천공비트 이론으로부터 (

)-지그재그 부호는

패턴으로 천공된

-지그재그 부호로 대체 될 수 있다. 오류 마루가 천공 노드수가 증가 할수록 심해지기 때문에, 가변 부호율 조건을 만족하는 동안에, 상기 1에서 d_c(i)가 천공 노드 수를 최소화 하도록 선택한다.

B. 상기에서 절차 1을 수행함으로써 각 행의 1의 개수가 일정해지기 때문에 H 는 천공 패턴에 다음의 가변 부호율 조건을 넣음으로써 구성될 수 있다.

조건:

의 주기는

주기의 인수이다.

만약 상기 조건이

에서 만족 하면 가변 부호율 천공 패턴은 성능 열화 없이 얻어진다.

이하, 상기 도 7a 및 도 7b를 참조하여 상술한 천공 비트 이론에 대하여 설명한다.

도 7a 및 도 7b는 일반적인 천공된 지그재그 부호의 Tanner 그래프를 도시한 도면으로서, 상기 도 7a는 천공 패턴 (p)의 지그재그 부호의 Tanner 그래프를 나타낸 것이고, 상기 도 7b는 천공 패턴 (q)의 지그재그 부호의 Tanner 그래프를 나타낸 것이다.

상기 도 7a 및 도 7b에서, 만약

라 가정하면, 천공 패턴 (p)에서 천공되는 (n1,0)-지그재그 부호가 동일한 에러 정정 성능을 유지하는 천공 패턴 (q)에서 (n2,0)-지그재그 부호에 의해 대체 가능하다. 이러한 이론에 대한 증명은 다음과 같다.

먼저, 상기 이론은 상기 도 7a 및 도 7b와, CZZ 부호의 구성 부호로서 가정하고, 부호 1 즉, 상기 천공 패턴 (p)의 지그재그 부호와 부호 2 즉, 상기 천공 패턴 (q)의 지그재그 부호가 동일한 인터리버에 접속되는 것으로 증명할 수 있다.

상기 도 7a 및 도 7b를 참조하면, 상기 도 7a 및 도 7b는 천공된 지그재그 부호의 Tanner 그래프를 도시한 것으로, 도면에 나타낸 검은색 원은 천공되지 않는 비트를 나타내고, 흰색 원은 천공된 비트를 나타낸다.

한편 밀도 진화 분석에서, 체크 노드로부터 정보 노드들로 전송되는 메시지들의 평균이 동일하다면, 두 개의 지그재그 부호들은, 자신들이 CZZ 부호들의 구성 부호들로 사용될 경우, 동일한 에러 정정 성능을 보인다. 따라서,

와

가 동일하다는 것을 보여줄 필요가 있다. 여기서, 상기 도 7a 및 도 7b에서의 상기

와

는 상기한 부호 1과 부호 2 각각을 위한 l번째 반복에서 체크 노드로부터 j번째 정보 노드로 전송되는 메시지의 평균을 나타낸다. 한편, 이하 N은 전체 정보 노드들의 수라 한다. 상기 도 7a와 도 7b에서, 천공 주기 p와 q를 고려함에 있어서, 상기 N 정보 노드들은

과

그룹들로 각각 분리되고, 상기 부호 1을 위한 상기 그룹의 크기는 n₁p, 상기 부호 2를 위한 그룹의 크기는 n₂q가 된다. 여기서, 상기 부호 1의 그룹 크기 n₁p와 상기 부호 2의 그룹 크기 n₂q는 상기한 바와 같이 동일(

)하다. 이때, 정보 노드의 인덱스 j는 계산식

또는

(

,

)로 표현될 수 있다. 이는 j번째 정보 노드가 상기 부호 1과 부호 2 모두에서, a번째 그룹에서 k번째 노드로 적용될 수 있다.

한편, 이하 m_L과 m_R을 왼쪽과 오른쪽 패리티 노드들로부터 j번째 정보 노드에 연결되는 체크 노드로 전송되는 메시지의 평균이라 하고, 또한

는 j번째 체크 노드로부터 j번째 반복에서의 정보 노드로 전송되는 메시지의 평균이라 가정한다.

먼저, 상기 도 7a에서 상기 부호 1을 위한 m_L, m_R 및

를 유도하면, 각각 하기 <수학식 19>, <수학식 20> 및 <수학식 21>과 같이 정의할 수 있다.

a-1 terms

(N/pn₁- a) terms

다음으로, 상기 도 7b에서 상기 부호 2를 위한 m_L, m_R 및

를 유도하면, 각각 하기 <수학식 22>, <수학식 23> 및 <수학식 24>와 같이 정의할 수 있다.

a-1 terms

(N/qn₂- a) terms

상기 <수학식 19> 내지 <수학식 24>에 나타낸 바와 같이, 상기

와

는

에 의하여 동일함을 알 수 있다.

다음으로, 상기 (3)의 과정 즉, 상기한 과정에서 생성된 천공 패턴들에 대하여 가변 부호율을 적용시키는 과정에 대하여 설명한다.

상기한 과정에서 상기

들의 행(row)당 1의 개수를 일치시켰기 때문에 야기되는 천공 패턴들에 대하여 가변 부호율을 만족하도록 구성만 하면 RC-LDPC 부호의 패리티 체크 행렬 H의 서브 매트릭스 S_i가 구성된다. 이와 같이 설계되는 RC-LDPC 부호의 i번째 지그재그 부호화기인 S_i에서 생성되는 패리티 비트 스트림을 Pa(j)(

)라고 가정하자.

이때, 가변 부호율(Rate-compatibility)을 고려하지 않으면, 상기

들에 해당되는 천공되지 않은 패리티 비트들은 다음과 같이 구할 수 있다.

즉, 상기

의 천공되지 않은(unpunctured) 패리티 비트들은 상기 생성되는 패리티 비트 스트림 Pa(j) 중에서 j가

의 배수에 해당하는 패리티 비트들, 예를 들어서,

와

의 천공되지 않은 패리티 비트들을 고려하면 다음과 같다.

: 상기 Pa(j) 중에서 j가 상기

의 배수에 해당하는 패리티 비트들을 천공되지 않은 패리티 비트들로 사용.

: 상기 Pa(j) 중에서 j가 상기

상기와 같은 경우에 가변 부호율을 만족시키기 위해서는 상기

의 천공되지 않은 패리티 비트들은 상기

의 천공되지 않은 패리티 비트들을 포함하여야 한다. 상기 조건을 만족시키기 위해서는 상기

는 상기

의 원소이어야 한다. 상기의 과정을 일반화 시키면 하기 <수학식 25>과 같이 나타낼 수 있다.

상기 <수학식 25>과 같은 조건이 만족되는 경우에는 각각의 부호율에 맞게 설계된 ICZZ 부호로부터 RC-LDPC 부호를 설계하는 과정에서 가변 부호율을 만족시켜야 한다는 제약 조건을 주었지만 성능 저하는 전혀 발생하지 않는다.

한편, 통상적으로 RC-LDPC 부호가 지원하는 부호율들이 넓은 범위가 아닌 경우는 상기와 같은 조건을 만족시키는 경우가 많다. 하지만 일반적으로 설계하는 과정에서 상기의 조건은 항상 만족될 수 없으므로, 성능 저하를 최소화시키면서 RC-LDPC 부호를 설계하는 방법이 필요하다.

따라서, 제안하는 본 발명에서는 가능한 짧은 주기를 결정하고, 그 결정된 주기 내에서 천공되지 않은 패리티 비트들이 일정한 간격을 가질 수 있는 설계 방안을 제안한다. 즉, 상기에서 구해진 천공된 지그재그 부호의 천공 패턴들은 모든 천공되지 않은 패리티 비트들이 일정한 간격으로 떨어져 있다(이는 주기를 가장 짧게 정하는 것과 일치한다). 이때, 상기 패턴들에 가변 부호율의 제약 조건을 주면서 일정한 간격으로 떨어져 있는 천공되지 않은 패리티 비트들의 형태를 유지시켜 주기 위한 방법으로, 상기와 같이 가능한 짧은 주기를 갖게 하면서, 주기 내에서 일정한 간격이 될 수 있도록 천공되지 않은 패리티 비트들의 위치를 정해주는 것이다.

모든 천공 패턴을 지원할 수 있으면서, 천공 패턴의 가장 짧은 주기를 가지는 천공 주기 P는 하기 <수학식 26>와 같이 정의할 수 있다.

상기 <수학식 26>에서, 상기 LCM은 최소공배수를 나타낸다. 상기 <수학식 26>에 의하여 구해지는 천공 주기 P는 모든 천공 패턴들을 표현할 수 있는 가장 짧은 주기를 나타낸다.

상기한 바와 같이, 비트를 천공할 때 상기에서와 같이 정해진 주기 내에 천공되지 않은 패리티 비트들이 가능한 일정한 간격을 위치하도록 비트를 천공한다. 그러므로 설계하는 과정에서는, 상기 천공되지 않은 패리티 비트들의 위치를 결정해야하는 것이다. 이때, 상기 결정하는 방법은 상기 천공되지 않은 패리티 비트들의 위치가 일정한 간격이 되도록 한다.

한편, 천공 패턴 P_i(j)를 갖는 상기 천공된 지그재그 부호는 상기 주기 P안에 P/P_i(j)개의 천공되지 않은 패리티 비트들이 존재해야 한다. 이때, 상기 천공되지 않는 패리티 비트들의 위치를 결정하는 방법은 다음과 같다.

A. 먼저, 낮은 부호율이 가장 성능에 영향을 많이 주는 시스템일 경우, 예컨대, IR에 기반하는 Type-II HARQ 방식을 사용하는 시스템일 경우에 있어서, 천공되지 않은 패리티 비트들의 위치를 정하는 방법은, 높은 부호율에서만 사용되는 패리티 비트들부터 가능한 일정한 거리가 유지되도록 정한다. 즉, 상기 주기 P안에 P/P_i(1)개의 천공되지 않은 패리티 비트를 P_i(1)만큼 거리를 두도록 그 위치를 결정하고, 그 다음 P/P_i(2)-P/P_i(1)개의 천공되지 않은 패리티 비트를 비어 있는 위치들 중에서 그 위치를 결정한다. 이때, 상기 P/P_i(2)-P/P_i(1)개의 천공되지 않은 패리티 비트의 위치 결정은 기존의 천공되지 않은 패리티 비트들도 고려하면서 가능한 일정한 거리가 유지되도록 그 위치를 결정한다. 또한 j번째 부호율에 대해서는

의 천공되지 않은 패리티 비트들을 기존의 천공되지 않은 패리티 비트들도 고려하면서 가능한 일정한 거리가 유지되도록 위치를 결정한다.

B. 다음으로, 각 부호율마다 중요도가 정해져 있는 경우에 있어서, 가장 중요도가 높은 부호율의 천공되지 않은 패리티 비트들이 주기 내에 일정한 간격으로 위치하도록 한다. 즉, 중요도의 순서에 따라서 가능한 천공되지 않은 패리티 비트들이 일정한 간격이 될 수 있도록 위치를 결정한다.

이하에서는, 이상에서 살펴본 바와 같은 본 발명에 따른 상기 RC-LDPC 부호의 실시예들 예컨대, 부호율 3/4, 3/8, 1/6을 지원하는 RC-LDPC 부호를 설계하는 방법에 대하여 설명한다.

먼저, 하기 <표 3>, <표 4> 및 <표 5>는 각각 부호율 3/4, 3/8, 1/6에서 최적의 성능을 보여주는 ICZZ 부호의 파라미터를 나타낸다. 상기 각 부호율에 해당하는 성능이 우수한 ICZZ 부호의 파라미터들은 상술한 바와 같은 밀도 진화 기법을 사용하는 방법과 상기한 (1)의 과정에서 제시한 <수학식 18>의 조건을 만족시키면서 구해진 것이다.

상기 <표 3> 내지 <표 5>에 나타낸 파라미터를 이용하여 각 부호율에 해당하는 패리티 체크 행렬의 서브 매트릭스들을 구성하면 다음과 같다.

1. 부호율 3/4

2. 부호율 3/8

3. 부호율 1/6

다음으로, 상기에서 나타낸 바와 같은 지그재그 부호들을 행(row)당 1의 개수를 일치시키기 위해서 상기한 (2)의 과정에 의하여 다음과 같이 천공된 지그재그 부호들로 변환시킨다.

가) 첫 번째 서브 매트릭스

RC-LDPC 부호의 첫 번째 서브 매트릭스는

,

으로부터 구해진다. 또한, 상기에서 살펴본 계산식

에 의해서

으로 구해지고, 상기한 천공 패턴 이론에 의하여 상기

,

은 성능의 변화 없이

,

으로 대체된다. 이를 나타내면 하기 <수학식 27>과 같이 정의할 수 있다.

상기 <수학식 27>에서 천공 패턴들 (12), (3), (1)에 가변 부호율의 제약 조건만 주어지면 RC-LDPC 부호의 패리티 체크 행렬의 첫 번째 서브 매트릭스에 대한 설계가 완료된다. 이때, 주기 P=LCM(1,3,12)=12이고, 상기 예제에서 상기 1은 3과 12의 원소이고, 상기 3은 12의 원소이므로 가변 부호율의 제약 조건을 적용하는 경우에 성능 저하가 전혀 발생하지 않는다. 상기에서는 첫 번째 서브 매트릭스에 대하여 살펴보았으나, 두 번째, 세 번째, 네 번째 서브 매트릭스도 상기 첫 번째 서브 매트릭스와 같은 방법으로 구할 수 있음은 자명하다. 또한 상기 가변 부호율의 제약조건을 만족시키는 천공 패턴은 도 8a와 같이 나타낼 수 있으며, 상기 도 8a에서, 검은색 원은 천공되지 않은 패리티 비트를 나타내고, 흰색 원은 천공된 패리티 비트를 나타낸다.

나) 다섯 번째 서브 매트릭스

RC-LDPC 부호의 다섯 번째 서브 매트릭스는

,

으로부터 구해진다. 또한, 상기에서 살펴본 계산식

에 의해서

으로 구해지고, 상기한 천공 패턴 이론에 의하여 상기

,

은 성능의 변화 없이

,

로 대체된다. 이를 나타내면 하기 <수학식 28>과 같이 정의할 수 있다.

상기 <수학식 28>에서 천공 패턴들 (3), (1)에 가변 부호율의 제약 조건만 주어지면 RC-LDPC 부호의 패리티 체크 행렬의 다섯 번째 서브 매트릭스에 대한 설계가 완료된다. 이때, 주기 P=LCM(1,3)=3이고, 상기 예제에서 상기 1은 3의 원소이므로 가변부호율의 제약조건을 적용하는 경우에 성능저하가 전혀 발생하지 않는다. 상기에서는 다섯 번째 서브 매트릭스에 대하여 살펴보았으나, 여섯 번째, 일곱 번째 서브 매트릭스도 상기 다섯 번째 서브 매트릭스와 같은 방법으로 구할 수 있음은 자명하다. 또한, 상기 가변 부호율의 제약조건을 만족시키는 천공 패턴은 도 8b와 같이 나타낼 수 있으며, 상기 도 8b에서 검은색 원은 천공되지 않은 패리티 비트를 나타내고, 흰색 원은 천공된 패리티 비트를 나타낸다.

한편, 이상에서와 같은 방법으로 구해진 RC-LDPC 부호의 천공 패턴을 나타내면, 하기 <표 6>과 나타낼 수 있다.

상기 <표 6>에 나타낸 바와 같이, 상기 <표 6>은 한 주기 동안의 천공 패턴을 나타내는 것이며, 상기 1은 천공되지 않은 패리티 비트를, 상기 0은 천공된 패리티 비트를 각각 나타낸다.

상기 <표 6>을 참조하면, 상기 부호율 3/4일 때 서브 매트릭스 5, 6, 7번 지그재그 부호화기에 해당하는 천공 패턴은 모두 0이기 때문에, 상기 5, 6, 7번 지그재그 부호화기는 사용되지 않는다. 즉, 천공 패턴이 모두 0이기 때문에 지그재그 부호화기를 사용하지 않는 경우를 나타내며, 이를 절단(pruning)이라 한다.

상기에서와 같이 본 발명에서 제안된 RC-LDPC 부호는 천공과 절단에 의하여 부호율이 조절되므로, 천공에만 의존하여 부호율이 조절되는 일반적인 가변 부호율 부호들에 비해서 더 넓은 부호율을 지원할 수 있는 장점을 갖게 된다. 다시 말해, 상기와 같이 천공만으로 부호율을 조절하는 경우에는 천공 노드(puncturing node)의 비율이 너무 높아져서 성능의 저하가 크게 되며, 이로 인하여 오류 마루(error floor) 현상이 심각해지는 문제점을 갖게 된다.

이상에서와 같이, 상기 <표 3> 내지 <표 5>의 R(i) 값들과 상기 <표 6>의 천공 패턴을 이용하여 RC-LDPC 부호를 설계할 수 있다. 이하, 상기 설계와 같은 RC-LDPC 부호와 일치하는 부호화기와 복호화기의 구조에 대하여 살펴보기로 한다.

도 9는 본 발명의 실시예에 따른 RC-LDPC 부호의 부호화기 구조를 개략적으로 도시한 도면이고, 도 10은 본 발명의 실시예에 따른 상기 도 9에 따른 천공기(puncturer) 동작 구성을 설명하기 위해 도시한 도면이다.
먼저, 상기 도 9를 참조하면, 상기 도 9는 본 발명의 실시예에 따른 RC-LDPC 부호화기의 예를 나타낸 것으로, 특히 상기 도 9에서는 상기 도 6에 나타낸 바와 같이 각각의 지그재그 부호화기(zigzag encoder)의 출력 값들을 천공하기 위한 천공기를 포함하는 부호율 3/4의 경우를 예로 나타낸 것이다. 상기 도 9에 도시한 바와 같이, 정보 비트 블록(1001)과, 디바이더(Divider)(1003)와, 서브 블록(1005)과, 절단기(pruner)와, 인터리버(interleaver)(1007)와, 지그재그 부호화기(1009) 및 천공기(puncturer)(1011)를 포함한다. 상기 천공기(1011)는 각 지그재그 부호화기(1009) 별로 각각 설계된다. 즉, 상기 도 9에서 상기 각각의 지그재그 부호화기(1009)에 상응하여 천공기 P₁, P₂, P₃, P₄, P₅, P₆, P₇가 일대일로 각각 설계된다.

먼저, 상기 도 10에서와 같이 P⁽¹⁾(101101101000)을 첫 번째 지그재그 부호 부호화기에서 생성된 임의의 패리티 비트라고 가정한다.

또한, 상기 도 10에서 참조부호 Tr1은 부호율 3/4일 때 천공되지 않은 패리티 비트를 나타내며, 참조부호 Tr2는 부호율 3/8일 때 천공되지 않은 패리티 비트를 나타내며, 참조부호 Tr3은 부호율 1/6일 때 천공되지 않은 패리티 비트를 각각 나타낸다. 상기 Tr1, Tr2 및 Tr3의 관계를 살펴보면, 낮은 부호율에서 전송되는 패리티 비트는 높은 부호율에서 전송된 패리티 비트를 포함한다는 것을 알 수 있다. 즉, 부호율 3/4일 때 상기 Tr1은 (1)이 전송되고, 부호율 3/8일 때 상기 Tr2는 (1110) 비트들 중에서 상기 Tr1에서 첫 번째 비트 1이 이미 전송되어 있으므로, 상기 전송된 1을 제외한 (110)만 전송하면 된다. 상기와 같은 방법으로 부호율 1/6일 때에는 Tr3은 (101101101000) 비트들 중에서 상기 Tr1 및 Tr2에서 이미 전송된 비트들을 제외하고 (01010100)만 전송하면 된다.

상기와 같은 특징들로 인하여 RC-LDPC 부호는 IR 기법에 기반을 둔 Type-II HARQ 방식에 적용할 수 있다. 상기와 마찬가지로, 천공기 P2 내지 P7에서도 동일한 방법으로 구성됨은 자명하다.

이상에서는 RC-LDPC 부호의 부호화기 구조에 대하여 살펴보았다. 이하에서는 상기 RC-LDPC 부호의 복호화기 구조에 대하여 간략하게 설명한다. 즉, 상기 RC-LDPC 부호는 상기에서 살펴본 바와 같은 3 종류의 복호 방법 즉, 병렬 복호화기를 이용한 복호와 직렬 복호화기를 이용한 복호 및 하이브리드 복호화기를 이용한 복호 방법에 의하여 복호 될 수 있다. 다만, 본 발명에서는 상기 복호 과정을 초기화 하는 과정에서 천공된 패리티 노드에 해당하는 변수 노드의 초기값을 0 즉, 널(NULL) 값을 대입함으로써, 복호가 이루어진다는 것에 차이를 가진다.

이상과 같이, 본 발명은 비록 한정된 실시예와 도면에 의해 설명되었으나, 본 발명은 이것에 의해 한정되지 않으며 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자에 의해 본 발명의 기술사상과 아래에 기재될 특허청구범위의 균등범위 내에서 다양한 수정 및 변형이 가능함은 물론이다.

이상 상술한 바와 같이 본 발명의 차세대 이동통신 시스템에서 지그재그 코드를 이용한 가변 부호율-저밀도 패리티 검사 부호 생성 장치 및 방법에 따르면, 심볼 천공(puncturing)이나 절단(pruning)을 이용하여 다양한 부호율을 지원할 수 있으며, 또한 각각의 특정 부호율에 맞게 설계된 ICZZ 부호들과 거의 동일한 성능을 가지며, 가변 부호율의 지원에 따른 성능 열화를 제거할 수 있는 이점을 가진 다.

또한, 천공과 절단에 의하여 부호율이 조절되므로, 천공에만 의존하여 부호율이 조절되는 일반적인 가변 부호율 부호들에 비해서 더 넓은 부호율을 지원할 수 있는 이점을 가진다.

Claims

저밀도 패리티 검사(LDPC, Low Density Parity Check) 부호 생성 방법에 있어서,

서로 다른 부호율 각각에 대하여 적어도 하나 이상의 패리티 체크 행렬을 결정하는 과정과,

상기 서로 다른 부호율별로 결정된 적어도 하나 이상의 패리티 체크 행렬 각각에서 동일한 행(row)에 대응하는 서브 매트릭스들간의 행에서의 1의 개수를 일치시키는 과정과,

상기 1의 개수를 일치시킨 부호율별로 결정된 적어도 하나 이상의 패리티 체크 행렬 각각에서 동일한 행(row)에 대응하는 서브 매트릭스들간을 결합하여 하나의 패리티 체크 행렬로 생성하는 과정을 포함하는 LDPC 부호 생성 방법
제1항에 있어서,

상기 적어도 하나 이상의 패리티 체크 행렬은 하기 조건을 만족하는 형태로 결정됨을 특징으로 하는 LDPC 부호 생성 방법.

R^k(i)는 패리티 체크 행렬에서 비제로 열(non-zero column)의 비율을 나타내며, R^j(i)는 시스템 설정 부호율(code rate)에 상응하는 패리티 체크 행렬의 i번째 서브 매트릭스를 나타내고, k, j 및 i는 각각 임의의 변수를 나타냄.
제1항에 있어서,

상기 결정된 적어도 하나 이상의 패리티 체크 행렬은 적어도 하나 이상의 서브 매트릭스로 이루어져 있고, 상기 적어도 하나 이상의 서브 매트릭스는 지그재그(zigzag) 부호 형태를 가짐을 특징으로 하는 LDPC 부호 생성 방법.
제1항에 있어서,

상기 서브 매트릭스들간은 각 서브 메트릭스의 적어도 하나의 엘리먼트(element)를 천공하여 결합됨을 특징으로 하는 LDPC 부호 생성 방법.
삭제
제1항에 있어서,

상기 각 서브 매트릭스 단위로 행(row)당 동일한 수의 1의 개수는 하기와 같이 산출함을 특징으로 하는 LDPC 부호 생성 방법.

d_c(i)는 가변 부호율 LDPC 부호의 패리티 체크 행렬에서 i번째 서브 매트릭스의 행(row)당 1의 개수를 나타내며, gcd()는 최대 공약수를 나타며, i는 임의의 변수를 나타냄.
삭제
제1항에 있어서,

상기 생성된 하나의 패리티 체크 행렬은 가변 부호율을 만족함을 특징으로 하는 LDPC 부호 생성 방법.
저밀도 패리티 검사(LDPC, Low Density Parity Check) 부호 생성 방법에 있어서,

천공 패턴의 가장 짧은 주기를 결정하는 과정과,

상기 결정된 주기 내에서 천공되지 않은(unpunctured) 패리티 비트들이 일정한 간격을 가지도록 천공되지 않은 패리티 비트들의 위치를 결정하는 과정을 포함하는 LDPC 부호 생성 방법.
제9항에 있어서,

상기 가장 짧은 주기를 가지는 천공 주기 P는 하기와 같이 산출함을 특징으로 하는 LDPC 부호 생성 방법.

LCM은 최소공배수를 나타내며, 천공 주기 P는 모든 천공 패턴들을 표현할 수 있는 가장 짧은 주기를 나타냄.
제9항에 있어서,

상기 천공되지 않는 패리티 비트들의 위치를 결정하는 과정은,

미리 설정된 기준 부호율보다 높은 부호율에 사용되는 패리티 비트들부터 가능한 일정한 거리가 유지되도록 위치를 결정하는 과정과,

천공되지 않은 패리티 비트들을 비어 있는 위치들 중에서 기존 천공되지 않은 패리티 비트들을 고려하여 가능한 일정한 거리가 유지되도록 위치를 결정하는 과정을 포함하는 LDPC 부호 생성 방법.
제9항에 있어서,

상기 천공되지 않는 패리티 비트들의 위치를 결정하는 과정은, 중요도의 순서에 상응하여 천공되지 않은 패리티 비트들이 일정한 간격을 유지하도록 위치를 결정함을 특징으로 하는 LDPC 부호 생성 방법.
제9항에 있어서,

상기 패리티 비트 중에서 미리 설정된 기준 부호율보다 낮은 부호율을 적용하여 전송되는 패리티 비트는 미리 설정된 기준 부호율보다 높은 부호율을 적용하여 전송되는 패리티 비트를 포함하는 LDPC 부호 생성 방법.
제9항에 있어서,

상기 LDPC 부호의 복호는, 초기화 과정에서 천공된 패리티 노드에 해당하는 변수 노드의 초기값을 널(Null) 값으로 삽입함을 특징으로 하는 LDPC 부호 생성 방법.
저밀도 패리티 검사(LDPC, Low Density Parity Check) 부호 생성 장치에 있어서,

지그재그 부호화기와,

입력 정보 비트들을 분할하는 디바이더를 포함하며,

상기 디바이더를 통해 분리된 정보 비트들을 입력하고, 상기 입력 정보 비트들에 대하여 천공 패턴이 0(Null)인 상기 지그재그 부호화기로의 입력을 절단(pruning)하는 절단기와,

상기 지그재그 부호화기를 통한 지그재그 부호들에 대하여 행(row)당 1의 개수를 일치시키기 위한 천공(puncturing)을 수행하는 천공기를 포함하는 LDPC 부호 생성 장치.
제15항에 있어서,

상기 천공 패턴은, 천공 패턴의 주기가 가장 짧은 주기를 결정하고, 상기 결정된 주기 내에서 천공되지 않은(unpunctured) 패리티 비트들이 일정한 간격을 가지도록 천공되지 않은 패리티 비트들의 위치를 결정함을 특징으로 하는 LDPC 부호 생성 장치.
제16항에 있어서,

상기 가장 짧은 주기를 가지는 천공 주기 P는 하기와 같이 산출함을 특징으로 하는 LDPC 부호 생성 장치.

LCM은 최소공배수를 나타내며, 천공 주기 P는 모든 천공 패턴들을 표현할 수 있는 가장 짧은 주기를 나타냄.
제16항에 있어서,

상기 천공되지 않는 패리티 비트들의 위치 결정은, 미리 설정된 기준 부호율보다 높은 부호율에 사용되는 패리티 비트들부터 가능한 일정한 거리가 유지되도록 위치를 결정하고, 천공되지 않은 패리티 비트들을 비어 있는 위치들 중에서 기존 천공되지 않은 패리티 비트들을 고려하여 가능한 일정한 거리가 유지되도록 위치를 결정함을 특징으로 하는 LDPC 부호 생성 장치.
제16항에 있어서,

상기 천공되지 않는 패리티 비트들의 위치 결정은, 중요도의 순서에 상응하여 천공되지 않은 패리티 비트들이 일정한 간격을 유지하도록 위치를 결정함을 특징으로 하는 LDPC 부호 생성 장치.
제16항에 있어서,

상기 패리티 비트 중에서 미리 설정된 기준 부호율보다 낮은 부호율을 적용하여 전송되는 패리티 비트는 미리 설정된 기준 부호율보다 높은 부호율을 적용하여 전송되는 패리티 비트를 포함하는 LDPC 부호 생성 장치.
제15항에 있어서,

상기 LDPC 부호 생성 장치는, 다수개의 패리티 체크 행렬들을 하나의 패리티 체크 행렬로 변환하고, 각 서브 매트릭스로 사용되는 지그재그 부호를 천공된 지그재그 부호로 대체하여 1의 개수를 일치시키는 것을 특징으로 하는 LDPC 부호 생성 장치.
제21항에 있어서,

상기 패리티 체크 행렬들에 해당되는 지그재그 부호들을 상기 패리티 체크 행렬들에 상응하여 천공된 지그재그 부호로 각각 변환함을 특징으로 하는 LDPC 부호 생성 장치.
제15항에 있어서,

상기 각 서브 매트릭스 단위로 행(row)당 동일한 수의 1의 개수는 하기와 같이 산출함을 특징으로 하는 LDPC 부호 생성 장치.

d_c(i)는 가변 부호율 LDPC 부호의 패리티 체크 행렬에서 i번째 서브 매트릭스의 행(row)당 1의 개수를 나타내며, gcd()는 최대 공약수를 나타며, i는 임의의 변수를 나타냄.
제15항에 있어서,

상기 LDPC 부호 생성 장치는, 각각의 천공 패턴들에 가변 부호율을 적용하여 천공된 지그재그 부호로 결합함을 특징으로 하는 LDPC 부호 생성 장치.
제24항에 있어서,

상기 가변 부호율을 만족하기 위해서 제1 서브 매트릭스의 천공되지 않은 패리티 비트들은 제2 서브 매트릭스의 천공되지 않은 패리티 비트들을 포함하며, 상기 제1 서브 매트릭스의 패리티 비트는 상기 제2 서브 매트릭스의 패리티 비트의 원소임을 특징으로 하는 LDPC 부호 생성 장치.