KR20170075627A

KR20170075627A - 통신 또는 방송 시스템에서 채널 부호화/복호화 방법 및 장치

Info

Publication number: KR20170075627A
Application number: KR1020160066749A
Authority: KR
Inventors: 명세호; 김경중; 장민; 정홍실
Original assignee: 삼성전자주식회사
Priority date: 2015-12-23
Filing date: 2016-05-30
Publication date: 2017-07-03
Also published as: KR102678457B1; US20200092038A1; US20190334652A1; US10887047B2; KR20180088423A; CN108476026A; US11044042B2

Abstract

본 개시는 LTE와 같은 4G 통신 시스템 이후 보다 높은 데이터 전송률을 지원하기 위한 5G 또는 pre-5G 통신 시스템에 관련된 것이다. 본 발명은 다양한 크기의 패리티 검사 행렬을 지원하는 통신 또는 방송 시스템에서 채널 부호화 방법 및 채널 부호화 장치로, 패리티 검사 행렬의 블록 크기를 결정하는 과정; 상기 패리티 검사 행렬을 생성하기 위한 수열을 독출하는 과정; 상기 결정된 블록 크기에 따라 사전에 정의된 연산을 상기 수열에 적용하여 수열을 변환하는 과정을 포함한다.

Description

통신 또는 방송 시스템에서 채널 부호화/복호화 방법 및 장치{APPARATUS AND METHOD FOR ENCODING AND DECODING IN COMMUNICATION OR BROADCASTING SYSTEM}

본 발명은 통신 또는 방송 시스템에서 채널 부호화/복호화 방법 및 장치에 관한 것이다.

4G 통신 시스템 상용화 이후 증가 추세에 있는 무선 데이터 트래픽 수요를 충족시키기 위해, 개선된 5G 통신 시스템 또는 pre-5G 통신 시스템을 개발하기 위한 노력이 이루어지고 있다. 이러한 이유로, 5G 통신 시스템 또는 pre-5G 통신 시스템은 4G 네트워크 이후 (Beyond 4G Network) 통신 시스템 또는 LTE 시스템 이후 (Post LTE) 이후의 시스템이라 불리어지고 있다.

높은 데이터 전송률을 달성하기 위해, 5G 통신 시스템은 초고주파(mmWave) 대역 (예를 들어, 60기가(60GHz) 대역과 같은)에서의 구현이 고려되고 있다. 초고주파 대역에서의 전파의 경로손실 완화 및 전파의 전달 거리를 증가시키기 위해, 5G 통신 시스템에서는 빔포밍(beamforming), 거대 배열 다중 입출력(massive MIMO), 전차원 다중입출력(Full Dimensional MIMO: FD-MIMO), 어레이 안테나(array antenna), 아날로그 빔형성(analog beam-forming), 및 대규모 안테나 (large scale antenna) 기술들이 논의되고 있다.

또한 시스템의 네트워크 개선을 위해, 5G 통신 시스템에서는 진화된 소형 셀, 개선된 소형 셀 (advanced small cell), 클라우드 무선 액세스 네트워크 (cloud radio access network: cloud RAN), 초고밀도 네트워크 (ultra-dense network), 기기 간 통신 (Device to Device communication: D2D), 무선 백홀 (wireless backhaul), 이동 네트워크 (moving network), 협력 통신 (cooperative communication), CoMP (Coordinated Multi-Points), 및 수신 간섭제거 (interference cancellation) 등의 기술 개발이 이루어지고 있다.

이 밖에도, 5G 시스템에서는 진보된 코딩 변조(Advanced Coding Modulation: ACM) 방식인 FQAM (Hybrid FSK and QAM Modulation) 및 SWSC (Sliding Window Superposition Coding)과, 진보된 접속 기술인 FBMC(Filter Bank Multi Carrier), NOMA(non-orthogonal multiple access), 및SCMA(sparse code multiple access) 등이 개발되고 있다.

통신/방송 시스템에서, 링크(link) 성능은 채널의 여러 가지 잡음(noise), 페이딩(fading) 현상 및 심벌 간 간섭(inter-symbol interference, ISI)에 의해 현저히 저하될 수 있다. 따라서 차세대 이동 통신, 디지털 방송 및 휴대 인터넷과 같이 높은 데이터 처리량과 신뢰도를 요구하는 고속 디지털 통신/방송 시스템들을 구현하기 위해서 잡음, 페이딩 및 심벌 간 간섭을 극복하기 위한 기술을 개발하는 것이 요구된다. 잡음 등을 극복하기 위한 연구의 일환으로 최근에는 정보의 왜곡을 효율적으로 복원하여 통신의 신뢰도를 높이기 위한 방법으로서 오류정정부호 (error correcting code)에 대한 연구가 활발히 이루어지고 있다.

본 발명은 다양한 입력 길이와 부호율을 지원 할 수 있는 LDPC 부호화/복호화 방법 및 장치를 제공한다. 또한 본 발명은 설계된 패리티 검사 행렬로부터 다양한 부호어 길이를 지원하는 LDPC 부호화/복호화 방법 및 장치를 제공한다.

상기와 같은 문제점을 해결하기 위한 본 발명은, 채널 부호화 방법에 있어서, 패리티 검사 행렬의 블록 크기를 결정하는 단계; 상기 패리티 검사 행렬을 생성하기 위한 수열을 독출하는 단계; 상기 결정된 블록 크기에 기초하여 상기 수열을 변환하는 단계; 상기 변환된 수열에 기초하여 정보어 비트에 대한 패리티 비트를 생성하는 것을 특징으로 한다.

본 발명은 가변 길이와 가변 레이트에 대해 적용할 수 있는 LDPC 부호를 지원할 수 있다.

도 1은 시스테메틱(systematic) LDPC 부호어 구조도를 도시한 도면이다.
도 2는 4 개의 행(row)와 8 개의 열(column)로 이루어진 LDPC 부호의 패리티 검사 행렬 H1의 일 예와 이를 태너 그래프(tanner graph)로 도시한 도면이다.
도 3은 본 발명에서 제안하는 패리티 검사 행렬의 기본적인 구조를 도시한 도면이다.
도 4는 본 발명의 일 실시 예에 따른 송신 장치의 블록 구성도이다.
도 5 는 본 발명의 일 실시 예에 따른 수신 장치의 블록 구성도이다.
도 6은 표 2의 패리티 검사 행렬에 대해 Z= 12, 24, 36, 48, 60, 72, 84, 96를 적용하여 수행한 성능 분석 결과를 도시한 도면이다
도 7a 및 7b는 LDPC 복호화를 위해 임의의 검사 노드와 변수 노드에서 메시지 패싱 동작을 나타낸 메시지 구조도이다.
도 8은 본 발명의 일 실시 예에 따른 LDPC 인코더의 구성을 설명하기 위한 블록도이다.
도 9은 본 발명의 일 실시 예에 따른 LDPC 디코더 구조도이다.
도 10은 본 발명의 다른 실시 예에 따른 LDPC 디코더 구조도이다.
도 11a 및 도 11b는 본 발명의 일 실시 예에 따른 패리티 검사 행렬을 도시한 도면이다.
도 12a 및 도 12b는 본 발명의 일 실시 예에 따른 패리티 검사 행렬을 도시한 도면이다.
도 13a 및 도 13b는 본 발명의 일 실시 예에 따른 패리티 검사 행렬을 도시한 도면이다.
도 14a 및 도 14b는 본 발명의 일 실시 예에 따른 패리티 검사 행렬을 도시한 도면이다.
도 15a 및 도 15b는 본 발명의 일 실시 예에 따른 패리티 검사 행렬을 도시한 도면이다.
도 16a 및 도 16b는 본 발명의 일 실시 예에 따른 패리티 검사 행렬을 도시한 도면이다.
도 17a 및 도 17b는 본 발명의 일 실시 예에 따른 패리티 검사 행렬을 도시한 도면이다.
도 18은 본 발명의 세그멘테이션 방법에 대해 상세히 도시한 도면이다.

이하 본 발명의 바람직한 실시 예를 첨부된 도면의 참조와 함께 상세히 설명한다. 그리고, 본 발명을 설명함에 있어서, 관련된 공지 기능 혹은 구성에 대한 구체적인 설명이 본 발명의 요지를 불필요하게 흐릴 수 있다고 판단된 경우, 그 상세한 설명은 생략한다. 그리고 후술되는 용어들은 본 발명에서의 기능을 고려하여 정의된 용어들로서 이는 사용자, 운용자의 의도 또는 관례 등에 따라 달라질 수 있다. 그러므로 그 정의는 본 명세서 전반에 걸친 내용을 토대로 내려져야 할 것이다.

본 발명의 주요한 요지는 유사한 기술적 배경을 가지는 여타의 시스템에도 본 발명의 범위를 크게 벗어나지 아니하는 범위에서 약간의 변형으로 적용 가능하며, 이는 본 발명의 기술분야에서 숙련된 기술적 지식을 가진 자의 판단으로 가능할 것이다.

본 발명의 이점 및 특징, 그리고 그것들을 달성하는 방법은 첨부되는 도면과 함께 상세하게 후술되어 있는 실시 예들을 참조하면 명확해질 것이다. 그러나 본 발명은 이하에서 개시되는 실시 예들에 한정되는 것이 아니라 서로 다른 다양한 형태로 구현될 수 있으며, 단지 본 실시 예들은 본 발명의 개시가 완전하도록 하고, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자에게 발명의 범주를 완전하게 알려주기 위해 제공되는 것이며, 본 발명은 청구항의 범주에 의해 정의될 뿐이다. 명세서 전체에 걸쳐 동일 참조 부호는 동일 구성 요소를 지칭한다.

1960년대에 Gallager에 의해서 처음 소개된 저밀도 패리티 체크(Low Density Parity Check, 이하 LDPC) 부호는 당시 기술 수준에서 구현하기 어려운 복잡도로 인해 오랫동안 잊혀져 왔다. 하지만, 1993년 Berrou와 Glavieux, Thitimajshima에 의해 제안된 터보(turbo) 부호가 셰논(Shannon)의 채널 용량에 근접하는 성능을 보임에 따라 터보 부호의 성능과 특성에 대한 많은 해석이 이루어지면서 반복 복호(iterative decoding)와 그래프를 기반으로 하는 채널 부호화에 대한 많은 연구가 진행되었다. 이를 계기로 1990년대 후반에 LDPC 부호가 재연구되면서 LDPC 부호에 대응되는 태너(Tanner) 그래프 상에서 합-곱(sum-product) 알고리즘에 기반한 반복 복호(iterative decoding)를 적용하여 복호화를 수행하면 LDPC 부호 또한 셰논의 채널 용량에 근접하는 성능을 가지게 됨이 밝혀졌다.

LDPC 부호는 일반적으로 패리티 검사 행렬(parity-check matrix)로 정의되며 태너 그래프로 통칭되는 이분(bipartite) 그래프를 이용하여 표현될 수 있다.

도 1은 시스테메틱(systematic) LDPC 부호어 구조도를 도시한 도면이다.

도 1에 따르면, LDPC 부호는 K_ldpc 개 비트 혹은 심볼로 구성되어 있는 정보어(102)를 입력받아 LDPC 부호화를 하여 N_ldpc 개 비트 혹은 심볼로 구성되어 있는 부호어(100)(codeword)를 생성한다. 이하 설명의 편의를 위해, K_ldpc 개 비트를 포함하는 정보어(102)를 입력받아 N_ldpc 개 비트로 구성되는 부호어(100)가 생성되는 것으로 가정한다. 즉, K_ldpc 개의 입력 비트인 정보어

(102)를 LDPC 부호화하면, 부호어

(100)가 생성된다. 즉, 부호어는 다수의 비트로 구성되어 있는 비트열이며, 부호어 비트는 부호어를 구성하는 각각의 비트를 의미한다. 또한, 정보어는 다수의 비트로 구성되어 있는 비트열이며, 정보어 비트는 정보어를 구성하는 각각의 비트를 의미한다. 이때, 시스테메틱 부호인 경우, 부호어

로 구성된다. 여기에서,

는 패리티 비트(104)이고, 패리티 비트의 개수 N_parity는 N_parity=N_ldpc - K_ldpc이다.

LDPC 부호는 선형 블록 부호(linear block code)의 일종으로 아래의 수학식 1과 같은 조건을 만족하는 부호어를 결정하는 과정을 포함한다.

[수학식 1]

여기에서,

이다.

수학식 1에서, H는 패리티 검사 행렬, C는 부호어, c_i는 부호어의 i 번째 비트, N_ldpc는 부호어 길이를 의미한다. 여기서 h_i는 패리티 검사 행렬(H)의 i번째 열(column)을 의미한다.

패리티 검사 행렬 H는 LDPC 부호어의 비트 개수와 동일한 N_ldpc 개의 열(column)로 구성되어 있다. 수학식 1은 패리티 검사 행렬의 i 번째 열(h_i)과 i 번째 부호어 비트 c_i의 곱의 합이 '0'이 됨을 의미하므로, i 번째 열(h_i)은 i 번째 부호어 비트 c_i와 관계가 있음을 의미한다.

도 2를 참조하여 LDPC 부호의 그래프 표현 방법에 대해 설명하기로 한다.

도 2는 4 개의 행(row)와 8 개의 열(column)로 이루어진 LDPC 부호의 패리티 검사 행렬 H₁의 일 예와 이를 태너 그래프(Tanner graph)로 도시한 도면이다. 도 2를 참조하면, 패리티 검사 행렬 H₁은 열이 8개 있기 때문에 길이가 8인 부호어(codeword)를 생성하며, H1을 통해 생성된 부호는 LDPC 부호를 의미하며, 각 열은 부호화된 8 비트에 대응된다.

도 2를 참조하면, 패리티 검사 행렬 H₁을 기반으로 부호화 및 복호화하는　LDPC 부호의 태너 그래프는 8 개의 변수 노드(variable node)들 즉, x₁(202), x₂(204), x₃(206), x₄(208), x₅(210), x₆(212), x₇(214), x₈(216)와 4 개의 검사 노드(check node)(218, 220, 222, 224)들로 구성되어 있다. 여기서, LDPC 부호의 패리티 검사 행렬 H₁의 i 번째 열과 j 번째 행은 각각 변수 노드 x_i와 j 번째 검사 노드에 대응된다. 또한, LDPC 부호의 패리티 검사 행렬 H₁의 j 번째 열과 j 번째 행이 교차하는 지점의 1의 값, 즉 0이 아닌 값의 의미는, 도 2와 같이 태너 그래프 상에서 변수 노드 x_i와 j 번째 검사 노드를 연결하는 선분(edge)이 존재함을 의미한다.

LDPC 부호의 태너 그래프에서 변수 노드와 검사 노드의 차수(degree)는 각 노드들에 연결되어 있는 선분의 개수를 의미하며, 이는 LDPC 부호의 패리티 검사 행렬에서 해당 노드에 대응되는 열 또는 행에서 0이 아닌 원소(entry)들의 개수와 동일하다. 예를 들어, 도 2에서 변수 노드들 x₁(202), x₂(204), x₃(206), x₄(208), x₅(210), x₆(212), x₇(214), x₈(216)의 차수는 각각 순서대로 4, 3, 3, 3, 2, 2, 2, 2가 되며, 검사 노드들(218, 220, 222, 224)의 차수는 각각 순서대로 6, 5, 5, 5가 된다. 또한, 도 2의 변수 노드에 대응되는 도 2의 패리티 검사 행렬 H₁의 각각의 열에서 0이 아닌 원소들의 개수는 상술한 차수들 4, 3, 3, 3, 2, 2, 2, 2와 순서대로 일치하며, 도 2의 검사 노드들에 대응되는 도 2의 패리티 검사 행렬 H₁의 각각의 행에서 0이 아닌 원소들의 개수는 상술한 차수들 6, 5, 5, 5와 순서대로 일치한다.

LDPC 부호는 도 2에서 나열한 bipartite 그래프 상에서 합곱(sum-product) 알고리즘(algorithm)에 기반한 반복 복호(iterative decoding) 알고리즘을 사용하여 복호할 수 있다. 여기서, 합곱 알고리즘은 메시지 패싱 알고리즘(message passing algorithm)의 일종이며, 메시지 패싱 알고리즘이라 함은 이분 그래프 상에서 에지를 통해 메시지들을 교환하고, 변수 노드 혹은 검사 노드로 입력되는 메시지들로부터 출력 메시지를 계산하여 업데이트하는 알고리즘을 나타낸다.

여기에서, i 번째 변수 노드의 메시지를 기반으로 i 번째 부호화 비트의 값을 결정할 수 있다. i 번째 부호화 비트의 값은 경판정(hard decision)과 연판정(soft decision) 모두 가능하다. 그러므로, LDPC 부호어의 i 번째 비트인 c_i의 성능은 태너 그래프의 i 번째 변수 노드의 성능에 대응되며, 이는 패리티 검사 행렬의 i 번째 열의 1의 위치 및 개수에 따라 결정될 수 있다. 다시 말해, 부호어의 N_ldpc 개의 부호어 비트들의 성능은 패리티 검사 행렬의 1의 위치 및 개수에 의해 성능이 좌우 될 수 있으며, 이는 LDPC 부호의 성능은 패리티 검사 행렬에 따라 많은 영향을 받음을 의미한다. 따라서 우수한 성능을 갖는 LDPC 부호를 설계 하기 위해서는 좋은 패리티 검사 행렬을 설계하는 방법이 필요하다.

통신 및 방송 시스템에서 사용되는 패리티 검사 행렬은 구현의 용이성을 위해 통상적으로 준순환(quasi-cyclic) 형태의 패리티 검사 행렬을 사용하는 준순환 LDPC 부호(또는 QC-LDPC 부호, 이하 QC-LDPC 부호)가 많이 사용된다.

QC-LDPC 부호는 작은 정사각 행렬의 형태를 가지는 0-행렬(zero matrix)이나 순환 순열 행렬(circulant permutation matrices)로 구성된 패리티 검사 행렬을 가짐을 특징으로 한다.

다음과 같은 참조문헌 [Myung2006]을 참고하여 보다 구체적으로 QC-LDPC 부호에 대해서 설명한다.

Reference [Myung2006]

S. Myung, K. Yang, and Y. Kim, "Lifting Methods for Quasi-Cyclic LDPC Codes," IEEE Communications Letters. vol. 10, pp. 489-491, June 2006.

상기 참조문헌[Myung2006]을 살펴보면, 다음 수학식 2와 같이

크기의 순열 행렬(permutation matrix)

을 정의한다. 여기서

는 행렬 상기 행렬 P에서의 i번째 행(row), j번째 열(column)의 원소(entry)를 의미한다.(0 ≤i, j < L)

[수학식 2]

상기와 같이 정의된 순열 행렬 P에 대해서

(0 ≤ i < L)는

크기의 항등 행렬(identity matrix)의 각 원소들을 i 번 만큼 오른쪽 방향으로 순환 이동(circular shift) 시킨 형태의 순환 순열 행렬임을 알 수 있다.

가장 간단한 QC-LDPC 부호의 패리티 검사 행렬 H는 다음 수학식 3와 같은 형태로 나타낼 수 있다.

[수학식 3]

만일

을

크기의 0-행렬이라 정의할 경우, 상기 수학식 3에서 순환 순열 행렬 또는 0-행렬의 각 지수

는 {-1, 0, 1, 2, ..., L-1} 값 중에 하나를 가지게 된다. 또한 상기 수학식 3의 패리티 검사 행렬 H는 열 블록이 n개, 행 블록이 m개이므로,

크기를 가지게 됨을 알 수 있다.

통상적으로 상기 수학식 3의 패리티 검사 행렬에서 각 순환 순열 행렬 및 0-행렬을 각각 1과 0으로 치환(replace)하여 얻은

크기의 이진(binary) 행렬을 패리티 검사 행렬 H의 모행렬(mother matrix) M(H)라 하고, 각 순환 순열 행렬 또는 0-행렬의 지수만을 선택하여 수학식 4와 같이 얻은

크기의 정수 행렬을 패리티 검사 행렬 H의 지수 행렬 E(H)라 한다.

[수학식 4]

한편, 패리티 검사 행렬에 따라 LDPC 부호의 성능이 결정될 수 있다. 따라서, 우수한 성능을 갖는 LDPC 부호를 위해 패리티 검사 행렬을 설계하는 것이 필요하다. 또한 다양한 입력 길이와 부호율을 지원 할 수 있는 LDPC 부호화 및 복호화 방법이 필요하다.

상기 참조문헌[Myung2006]을 살펴보면, QC-LDPC 부호의 효율적인 설계를 위해서 리프팅(Lifting)이라 알려진 방법을 사용한다. 리프팅은 주어진 작은 모행렬로부터 순환 순열 행렬 또는 0-행렬의 크기를 결정하는 L 값을 특정한 규칙에 따라 설정함으로써 효율적으로 매우 큰 패리티 검사 행렬을 설계하는 방법이다. 기존 리프팅 방법과 이렇게 리프팅을 통해 설계된 QC-LDPC 부호의 특징을 간단히 정리하면 다음과 같다.

먼저 LDPC 부호 C₀가 주어져 있을 때 리프팅 방법을 통해 설계될 S개의 QC-LDPC 부호를 C₁, ..., C_S라 하고, 상기 각 QC-LDPC 부호의 패리티 검사 행렬의 행블록 및 열블록의 크기에 해당하는 값은 L_k라 한다. 여기서 C₀는 C₁, ..., C_S 부호의 모행렬을 패리티 검사 행렬로 가지는 가장 작은 LDPC 부호에 해당하며 행블록 및 열블록의 크기에 해당하는 L₀ 값은 1이다. 또, 편의상 각 부호 C_k의 패리티 검사 행렬

는

크기의 지수 행렬

을 가지며 각 지수

들은 {-1, 0, 1, 2, ..., L_k - 1} 값 중에 하나로 선택된다.

참조문헌[Myung2006]을 살펴보면, 리프팅은 C₀ → C₁ →...→ C_S와 같은 단계로 이루어지며 L_k ₊₁ = q_k ₊ ₁L_k (q_k ₊₁은 양의 정수, k=0,1,..., S-1)와 같은 특징을 가진다. 또한 리프팅 과정의 특성에 의해 C_S의 패리티 검사 행렬

만 저장하고 있으면 리프팅 방식에 따라 다음 수학식 5를 이용하여 상기 QC-LDPC 부호 C₀, C₁, ..., C_S를 모두 나타낼 수 있다.

[수학식 5]

[수학식 6]

상기 수학식 5 또는 6의 리프팅 방식은 각 QC-LDPC 부호 C_k의 패리티 검사 행렬에서 행블록 또는 열블록의 크기에 해당하는 L_k들이 서로 배수 관계(multiple)를 가지게 되어, 지수 행렬 또한 특정 방식에 의해 선택된다. 이와 같은 기존 리프팅 방식은 리프팅을 통해 설계된 각 패리티 검사 행렬의 대수적 또는 그래프 특성을 좋게 하여 오류 마루(error floor) 특성을 개선한 QC-LDPC 부호를 쉽게 설계할 수 있게 돕는다.

하지만, 각 L_k 값들이 서로 배수 관계에 있기 때문에 각 부호의 길이가 크게 제한되는 단점이 있다. 예를 들어 각 L_k 값들에 대해 L_k ₊₁ = 2×L_k와 같은 최소한의 리프팅 방식을 적용하였다고 가정시, 이 경우 각 QC-LDPC 부호의 패리티 검사 행렬의 크기는

만을 가질 수 있다. 즉, 리프팅을 10 단계 적용할 경우(S=10) 패리티 검사 행렬은 10개의 크기만을 가질 수 있게 된다.

이와 같은 이유로 기존 리프팅 방식은 다양한 길이를 지원하는 QC-LDPC 부호를 설계하는데 있어서 다소 불리한 특성을 가지고 있다. 하지만, 통상적으로 사용되는 이동 통신 시스템에서는 다양한 형태의 데이터 전송을 고려하여 매우 높은 수준의 길이 호환성(length compatibility)을 요구하게 된다. 이러한 이유로 기존 방식으로는 LDPC 부호를 이동 통신 시스템에서 적용하기 어려운 문제점이 있다.

다음으로 참조문헌 [Myung2005]을 참고하여 QC-LDPC 부호의 부호화 방법에 대해 더 자세히 설명한다.

Reference [Myung2005]

S. Myung, K. Yang, and J. Kim, " Quasi-Cyclic LDPC Codes for Fast Encoding," IEEE Transactions on Information Theory, vol. 51, No.8, pp. 2894-2901, Aug. 2005.

도 3은 본 발명에서 제안하는 패리티 검사 행렬의 기본적인 구조를 도시한 도면이다.

상기 참조문헌 [Myung2005]을 살펴보면, 도 3과 같이 순환 순열 행렬로 구성된 특수한 형태의 패리티 검사 행렬이 정의되어 있다. 또한 상기 도 3의 패리티 검사 행렬에서 다음 수학식 7 또는 수학식 8의 관계를 만족하면 효율적인 부호화가 가능함이 나타나 있다.

[수학식 7]

[수학식 8]

상기 수학식 7 및 수학식 8에서

값은

가 위치하고 있는 행(row)의 위치를 의미한다.

이와 같이 상기 수학식 7 및 수학식 8을 만족하게 되면, 참조문헌 [Myung2005] 상에서

로 정의된 행렬이 항등 행렬이 되어 부호화 과정에서 효율적인 부호화가 가능함이 잘 알려져 있다.

본 발명에서는 편의상 하나의 블록에 대응되는 순환 순열 행렬이 1 개인 경우만 설명하였으나 이하 하나의 블록에 여러 개의 순환 순열 행렬이 포함된 경우에도 동일한 발명을 적용할 수 있음을 밝혀둔다.

도 4는 본 발명의 일 실시 예에 따른 송신 장치의 블록 구성도이다.

구체적으로, 도 4와 같이 송신 장치(400)는 가변 길이 입력 비트들을 처리하기 위해, 세그멘터이션부(410), 제로 패딩부(420), LDPC 인코더(430), 레이트 매칭부(440), 변조부(450)를 포함할 수 있다.

여기에서 도 4에 도시된 구성요소는 가변 길이 입력 비트들에 대한 인코딩 및 변조(encoding and modulation)를 수행하는 구성요소로서, 이는 일 예일 뿐이며, 경우에 따라 도 4에 도시된 구성요소 중 일부는 생략 또는 변경될 수 있고, 다른 구성요소가 더 추가될 수도 있다.

도 5 는 본 발명의 일 실시 예에 따른 수신 장치의 블록 구성도이다.

구체적으로, 도 5와 같이 수신 장치(500)는 가변 길이 정보들을 처리하기 위해, 복조부(510), 레이트 디매칭부(520), LDPC 디코더(530), 제로 제거부(540) 및 디세그멘테이이션부(550)를 포함할 수 있다.

여기에서 도 5에 도시된 구성요소는 도 4에 도시된 구성요소에 대응되는 기능을 수행하는 구성요소로서, 이는 일 예일 뿐이고 경우에 따라 일부는 생략 또는 변경될 수 있고, 다른 구성요소가 더 추가될 수도 있다.

본 발명의 구체적인 실시예는 다음과 같다.

먼저 리프팅 방법을 통해 설계될 S개의 LDPC 부호를 C₁, ..., C_S라 하고, 상기 각 LDPC 부호의 패리티 검사 행렬 C_i의 행블록 및 열블록의 크기에 해당하는 값은 Z라 한다. 또, 편의상 각 부호 C_i의 패리티 검사 행렬

는

크기의 지수 행렬

을 가진다. 각 지수

들은 {-1, 0, 1, 2, ..., Z-1} 값 중에 하나로 선택된다. (본 발명에서는 편의상 0-행렬을 나타내는 지수를 -1로 표현하고 있지만 시스템의 편의에 따라 다른 값으로 변경될 수 있다.)

따라서 가장 큰 패리티 검사 행렬을 가지는 LDPC 부호 C_S의 지수 행렬은

라 한다. (여기서

는 Z 값 중 최대 값이라 한다) 이 때 Z값이

보다 작을 때에 대한 각 LDPC 부호의 패리티 검사 행렬을 구성하는 순환 순열 행렬 및 0-행렬을 나타내는 지수는 다음과 같은 수학식 9에 따라 결정될 수 있다.

[수학식 9]

[수학식 10]

수학식 9 또는 수학식 10에서

는

에 대해 Z로 나눈 나머지를 의미한다.

하지만, [Myung2006]에서는 Z의 값을 서로 배수 관계가 만족하도록 한정하므로, 다양한 길이를 지원하는데 적합하지 않다. 예를 들어 패리티 검사 행렬

의 지수 행렬

또는 모행렬

의 열의 개수 n이 36이라 하고, Z의 값을 1, 2, 4, 8, ……, 128과 같은 8 단계 리프팅을 통해 얻을 수 있는 길이의 종류는 36, 72, 144, ……, 4608

이 되어 가장 짧은 길이와 가장 긴 길이의 차이가 매우 크게 된다.

본 발명에서는 Z의 값이 서로 배수 관계가 아닌 경우에도 상기 수학식 9 또는 수학식 10에 적용한 지수 방법을 그대로 적용할 수 있으며 성능 열화가 거의 없는 패리티 검사 행렬을 설계하는 방법을 제시한다. 참고로 상기 수학식 9 또는 수학식 10에 제시한 방법은 모듈로 연산에 기반한 리프팅 방식을 적용하였을 경우에 지수 변환 방법으로서, 참조문헌 [Myung2006]에 나타낸 것처럼 플로어링(flooring) 연산 또는 다른 연산에 기초하여 다양한 방법이 존재할 수 있음은 자명하다. 다음 수학식 11 또는 수학식 12는 Z값이

보다 작을 때에 대해 플로어링 연산에 기반한 리프팅을 적용하여 설계한 패리티 검사 행렬의 지수 변환 방법을 나타낸다.

[수학식 11]

[수학식 12]

이하에서는 길이에 대한 호환성 문제가 있는 기존 리프팅 방식의 문제점을 해결하기 위한 패리티 검사 행렬의 설계 방법 및 그 이용 방법에 대해서 설명한다.

먼저 본 발명에서는 변형된 리프팅 과정을 다음과 같이 정의한다.

1) Z 값들 중 최대 값을 Z_max 라 한다.

2) Z_max 의 약수 중 하나를 D라 한다. (

)

3) Z는 D, 2D, 3D, …, SD (= Z_max) 값 중 하나를 가진다.

(편의상 Z = k×D에 대응되는 패리티 검사 행렬을 H_k, 상기 패리티 검사 행렬에 대응되는 LDPC 부호를 C_k라 한다.)

기존 리프팅 방식은 패리티 검사 행렬을 설계할 때 바로 직전 단계에서 리프팅을 통해 설계된 패리티 검사 행렬만 영향을 끼친다. 즉, 각 리프팅 단계에서 Z 값이 서로 배수 관계를 이루며, (k+1) 번째 패리티 검사 행렬을 설계하기 위해서는 k 번째 패리티 검사 행렬만이 영향을 미치며, (k-1)번째 패리티 검사 행렬은 더 이상 사용되지 않는다. 이는 Z 값 사이의 배수 관계 때문에 발생하는 일이며 그 자세한 사항은 참조문헌 [Myung2006]에 잘 나타나 있다.

하지만, 본 발명에서 제안하는 변형된 리프팅 방식은 일반적으로 Z 값이 서로 배수 관계가 아니기 때문에 참조문헌 [Myung2006]에 나타난 방식과 같이 최적화된 (optimal) 패리티 검사 행렬을 설계하는 것이 거의 불가능하다. 따라서 본 발명에서는 다음과 같이 준최적화(sub-optimal)된 패리티 검사 행렬의 설계 방법을 제안한다.

편의상 리프팅을 적용하기 위한 모행렬을 M(H)라 하고 모행렬에 대한 지수 행렬의 각 원소들을

라 한다. 또한 Z = k×D인 경우에 대한 Z 값을 Z_k라 하고, 그에 대응되는 지수 행렬의 원소들은

라 한다.

변형된 리프팅 방식에 따른 패리티 검사 행렬 설계 방법은 아래와 같다.

단계 1)

이면,

에 대해

(k = 1, 2, ……, S)

단계 2) k=1일 경우;

모행렬 M(H)로부터 참조문헌 [Myung2006]과 동일한 방식으로

를 구한다.

이 때

의 각 원소

는 0, 1, 2, ……,

값 중 하나를 가지며, 상기 각 원소

에 대해

의 태너 그래프에 대한 사이클 특성 프로파일을 분석한다. (여기서 단계 1)에 의해 0-행렬들의 위치는 먼저 결정되어 있음에 유의한다.)

상기 사이클 특성 프로파일은 다음을 의미한다.

i) 각 원소에 의해 생성되는 태너(Tanner) 그래프 상의 사이클 거스(girth)의 크기

ii) 각 원소에 의해 생성되며, 거스 크기의 사이클을 구성하는 변수 노드들의 차수 총합

iii) 각 원소에 의해 생성되며, 거스 크기의 사이클을 구성하는 변수 노드들의 개수

또한 상기 각 원소

는 가장 좋은 사이클 특성을 가지는 경우의 값으로 임시 결정한다. 여기서 사이클 특성이 좋다는 말의 의미는 다음과 같은 조건을 만족함을 의미한다.

iv) 태너(Tanner) 그래프 상에서 거스(girth)의 크기가 크다.

v) 거스를 가지는 사이클을 구성하는 변수 노드의 차수의 총 합이 크다.

vi) iv), v)가 동일할 경우 거스 크기 사이클을 구성하는 변수 노드의 개수가 작다.

상기 조건들을 만족하는 원소

는 복수 개 존재할 경우 모든 값들을 후보 값으로 임시 저장한다.

에 대해 다음 단계 3) 및 단계 4)의 과정을 반복한다.

단계 3)

의 각 원소

를 상기 단계 3)에서 임시 결정된

로 설정하여

에 대한 사이클 특성 프로파일을 분석한다. 이 때,

의 값은 0, 1, 2, ……,

중에 하나를 가짐에 유의한다. 다음으로

의 각 원소

에 대해 값을

로 변경하며 사이클 특성 프로파일을 분석한다.

상기 각 원소

는 가장 좋은 사이클 특성을 가지는 경우의 값을 선택한다.

단계 4) 단계 3)에서 선택된

들에 대해

(

)를 적용한 다음 모든

의 태너 그래프에 대해 사이클 특성이 개선되는 경우에 해당

값을

의 원소의 후보 값으로 임시 결정한다. 상기 임시로 결정되는

값들은 복수 개 존재할 수도 있음에 유의한다.

단계 5) 단계 4)의 최종 결과로부터

를 결정한다. 만일 단계 3), 4)의 과정에서

의 원소

에 대해 복수 개의 선택 가능성이 존재할 경우에는 후보 값들 중에서 가장 작은 값을 최종 값으로 결정한다.

위와 같은 설계 방법을 통해 설계된 패리티 검사 행렬의 실시 예를 다음 표 1 내지 표 6에 나타내었다. 상기 표 1 내지 표 6은 각 패리티 검사 행렬의 지수 행렬을 의미한다. (작은 빈 블록은 Z×Z 크기의 0-행렬을 의미한다.) 설계의 편의상 모행렬의 열의 개수는 모두 36으로 고정하였고, 표 1 및 표 2는 부호율 8/9, 표 3 및 표 4는 부호율 2/3, 표 5 및 표 6은 부호율 4/9로 설정하였다. 또한 리프팅을 위한 Z 값은 12, 24, 36, 48, 60, 72, 84, 96으로 설정하여 총 8 개의 길이에 대해 지원함을 가정하였다.

[표 1]

[표 2]

[표 3]

[표 4]

[표 5]

[표 6]

또 다른 설계된 패리티 검사 행렬의 실시 예를 다음 표 7 내지 표 12에 나타내었다. 상기 표 7 내지 표 12는 각 패리티 검사 행렬의 지수 행렬을 의미한다. (작은 빈 블록은

크기의 0-행렬에 대응된다.) 설계의 편의상 모행렬의 열의 개수는 모두 37으로 고정하였고, 표 7 및 표 8은 부호율 32/37, 표 9 및 표 10은 부호율 24/37, 표 11 및 표 12는 부호율 16/37로 설정하였다. 또한 리프팅을 위한 Z 값은 12, 24, 36, 48, 60, 72, 84, 96으로 설정하여 총 8 개의 길이에 대해 지원함을 가정하였다.

[표 7]

[표 8]

[표 9]

[표 10]

[표 11]

[표 12]

상기 표 7 내지 표 12에 나타낸 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행할 경우에 정보어에 대응되는 부분행렬 중에서 가장 첫 번째 열 블록(column block)에 대응되는 정보어 비트를 천공(puncturing)하여 전송을 할 경우에는 최종 부호율이 표 7 및 표 8은 부호율 8/9, 표 9 및 표 10은 부호율 2/3, 표 11 및 표 12는 부호율 4/9이 되어 마치 표 1 내지 6을 이용하는 경우와 동일함을 알 수 있다. 통상적으로 LDPC 부호는 정보어 천공을 적절히 적용할 경우에 성능을 개선할 수 있기 때문에 성능 개선을 위해 표 7 내지 표 12를 이용한 LDPC 부호화를 적용할 수 있다.

본 발명에서 제안한 패리티 검사 설계 방법을 통해 생성된 패리티 검사 행렬의 성능의 전산 실험 결과 일부를 도 6에 나타내었다. 도 6은 상기 표 3의 패리티 검사 행렬에 대해 Z= 12, 24, 36, 48, 60, 72, 84, 96를 적용하여 수행한 성능 분석 결과를 도시한 도면이다. 성능을 살펴보면 하나의 지수 행렬로부터 생성된 8개의 패리티 검사 행렬을 이용한 LDPC 부호화 기법이 잘 동작하고 있음을 알 수 있다. 특히 프레임 오율(frame error rate)이 1/1000 영역까지 오류 마루 현상 없이 좋은 성능을 보임을 확인할 수 있다.

상기 표 1 내지 표 12에서 나타낸 지수 행렬은 모듈로 리프팅을 가정하여 설계된 지수 행렬로서 각 지수에 대해 수학식 9 또는 수학식 10을 적용하여 각각의 Z 값에 대한 지수 행렬을 도출할 수 있다.

또 다른 설계된 패리티 검사 행렬의 실시 예를 다음 표 13 내지 표 16에 나타내었다. 상기 표 13 내지 표 16은 각 패리티 검사 행렬의 지수 행렬을 의미한다. (작은 빈 블록은 Z×Z 크기의 0-행렬에 대응된다.) 설계의 편의상 모행렬의 열의 개수는 모두 24로 고정하였고, 표 13은 부호율 5/6, 표 14는 부호율 3/4, 표 15는 부호율 2/3, 표 16은 부호율 1/2로 설정하였다. 또한 리프팅을 위한 Z 값은 81, 162, 324로 설정하여 최소한 상기 3 개의 Z 값에 대해 지원 가능한 LDPC 부호의 패리티 검사 행렬에 대한 지수 행렬을 의미한다.

[표 13]

[표 14]

[표 15]

[표 16]

또 다른 설계된 패리티 검사 행렬의 실시 예를 다음 표 17 내지 표 20에 나타내었다. 상기 표 17 내지 표 20은 각 패리티 검사 행렬의 지수 행렬을 의미한다. (작은 빈 블록은 Z×Z 크기의 0-행렬에 대응된다.) 설계의 편의상 모행렬의 열의 개수는 모두 24로 고정하였고, 표 17은 부호율 5/6, 표 18은 부호율 3/4, 표 19는 부호율 2/3, 표 20은 부호율 1/2로 설정하였다. 또한 리프팅을 위한 Z 값은 81, 162, 324, 648로 설정하여 최소한 상기 총 4 개의 Z 값에 대해 지원 가능한 LDPC 부호의 패리티 검사 행렬에 대한 지수 행렬을 의미한다.

[표 17]

[표 18]

[표 19]

[표 20]

참고로 상기 표 13 내지 표 20에서 나타낸 지수 행렬은 모듈로 리프팅을 가정하여 설계된 지수 행렬로서 각 지수에 대해 수학식 9 또는 수학식 10을 적용하여 각각의 Z 값에 대한 지수 행렬을 도출하여 부호화에 사용할 수 있다. 또한 상기 표 17 내지 표 20의 지수 행렬에 모듈로 324를 취하면 각각 표 13 내지 16의 지수 행렬을 얻을 수 있으며, 상기 표 13 내지 표 20의 지수 행렬에 모듈로 81을 취하면 표 13과 표 17, 표 14와 표 18, 표 15와 표 19, 표 16과 표 20이 각각 동일한 지수 행렬을 가짐을 확인할 수 있다. 즉, 다시 말하면, 표 17 내지 표 20에 나타낸 지수 행렬은 표 13 내지 표 16의 지수 행렬에 대한 정보를 포함하고 있으며, 모듈로 81을 취해 얻을 수 있는 동일한 지수 행렬을 이용하여 리프팅을 적용했음을 알 수 있다. 상기 표 13내지 표 20에 나타낸 지수 행렬에 대해 모듈로 81을 취해 얻을 수 있는 지수 행렬은 IEEE 802.11n 표준에서 정의된 패리티 검사 행렬과 동일한데, 이는 기존에 알려져 있는 패리티 검사 행렬을 이용하여 리프팅을 적용하면, 기존 패리티 검사 행렬의 특징은 그대로 유지하면서도 새로운 패리티 검사 행렬을 설계할 수 있음을 보여준다.

상기 표 1 내지 표 20의 지수 행렬은 모두 상기 수학식 7 또는 수학식 8을 만족시키기 위하여 상기 도 3에서 나타낸 패리티 검사 행렬의 포맷에서

로 설정되었다. 따라서 참조문헌 [Myung2005] 상에서

하지만, 본 발명의 또 다른 실시 예로서 부호화 방법을 표현하면 다음과 같다.

상기 도 3에서 패리티에 대응되는 부분 행렬에서의 순환 행렬의 지수 값을 다음 수학식 13과 같이 결정한다.

[수학식 13]

상기 수학식 13은 수학식 7에서 y 값에 대한 조건이 다르게 되어 참조문헌 [Myung2005] 상에서 정의된

행렬이 항등 행렬이 되지 않는다. 따라서 부호화 과정에서 다소 차이점이 존재하게 된다. 하지만, 일반적으로 LDPC 부호화 복잡도에서 복잡도 증가에 영향을 주는 부분은

에 존재하는 0이 아닌 원소의 개수이다. 상기 수학식 13에 의하면

는 순환 순열 행렬 P^a (a는 정수)가 되어

또한 단순히 순환 순열 행렬 P^-a가 됨은 자명하다. 따라서 부호화 복잡도 증가가 거의 없음을 예상할 수 있다.

실제로 참조문헌 [Myung2005]에 따르면 도 3의 제 1 패리티를 구하는 과정에서

연산이 필요한데 기존 수학식 7을 만족하는 패리티 검사행렬은

행렬이 항등 행렬이므로

연산이 필요없게 되어 효율적인 부호화가 가능하였다. 하지만, 도 3의 제 2 패리티를 구하는 과정에서 제 1 패리티에

관련 연산이 필요하게 되는데, 만일 이 연산을 간단히 하기 위해

을 항등 행렬, 즉, b₁을 0으로 설정할 경우에는 태그 그래프 상의 사이클 특성이 나빠지는 단점이 있다. 따라서 사이클 특성을 나빠지지 않기 위해서는 제 2 패리티를 구하기 위하여 제 1 패리티에

관련 연산을 수행하게 된다.

상기 수학식 13의 경우는 구체적인 실시 예를 들어 설명한다. 예를 들어 수학식 13을 만족하도록 도 3의 패리티에 대응되는 부분 행렬의 순환 순열들의 지수를

와 같이 설정하였다 하자. 이 경우에는

가 되어 제 1 패리티를 구하는 과정에서

연산이 필요하게 된다. 하지만, 반면에 b₁을 0으로 설정할 수 있으므로 제 2 패리티를 구하는 과정에서 제 1 패리티에 순환 순열 행렬에 관한 연산을 수행할 필요가 없게 된다. 또한 태너 그래프의 사이클 특성도 나빠지지 않도록 y 값을 설정할 수 있다. (통상적으로 사이클 특성을 좋게 하기 위해 y와 Z는 서로 소(relatively prime)가 되도록 y 값을 설정한다) 따라서 성능 열화 없이 실질적인 부호화 복잡도 증가량은 무시할 수 있게 된다. 추가로

로 설정할 경우에는 대부분 항등 행렬로 구성되어 있음을 의미하므로 복수 개의 패리티 검사 행렬을 하드웨어로 구현해야 할 때 큰 장점이 있다.

본 발명에서 제안한 설계 방법을 통해 설계된 또 다른 패리티 검사 행렬의 실시 예를 도 11a 및 11b 내지 도 16a 및 16b에 나타내었다. 상기 도 11a/11b 내지 도 16a/16b는 각 패리티 검사 행렬의 지수 행렬을 의미한다. 작은 빈 블록은 Z×Z 크기의 0-행렬을 의미하며, 리프팅을 위한 Z 값은 12, 24, 36, 48, 60, 72, 84, 96으로 설정하여 총 8 개의 길이에 대해 지원함을 가정하였다. 참고로 도 11의 37번째 열블록부터 마지막 열블록까지와 도 14의 38번째 열블록부터 마지막 열블록까지는 모두 차수가 1인 특징을 가지고 있는데 편의상 표에서는 일부를 생략하였다. 또한 상기 차수가 1인 열 블록들은 항등 행렬들로 구성되어 있다.

상기 도 11의 패리티 검사 행렬을 살펴보면, 전체 패리티 검사 행렬의 위 4개의 행 블록과 36 개의 열 블록으로 구성된 부분 행렬은 상기 표 2에 대응되는 패리티 검사 행렬과 일치함을 알 수 있다. 즉, 상기 도 11의 패리티 검사 행렬은 상기 표 2에 대응되는 패리티 검사 행렬에 복수 개의 단일 패리티 검사 (single parity-check) 부호를 연접하여 확장된(extended) 형태임을 알 수 있다. 또한 도 12 내지 도 16의 패리티 검사 행렬도 각각 상기 표 4, 표 6, 표 8, 표 10, 표 12의 패리티 검사 행렬로부터 확장된 형태임을 쉽게 알 수 있다.

본 발명에서 제안한 설계 방법을 통해 설계된 또 다른 패리티 검사 행렬의 실시 예를 도 17a 및 17b에 나타내었다. 상기 도 17a 및 17b는 각 패리티 검사 행렬의 지수 행렬을 의미한다. 작은 빈 블록은 Z×Z 크기의 0-행렬을 의미하며, 리프팅을 위한 Z 값은 27, 54, 81으로 설정하여 총 3 개의 길이에 대해 지원함을 가정하였다. 참고로 도 17의 25번째 열블록부터 마지막 열블록까지는 모두 차수가 1인 특징을 가지고 있다. 또한 상기 차수가 1인 열 블록들은 항등행렬들로 구성되어 있다.

단일 패리티 검사 부호와의 연접 방식을 적용한 패리티 검사 행렬은 확장성이 용이하기 때문에 IR(Incremental Redundancy) 기법을 적용하는데 장점이 있다. 상기 IR 기법은 HARQ (Hybrid Automatic Repeat reQuest) 지원을 위해 중요한 기술이기 때문에 효율적이면서 우수한 성능을 가지는 IR 기법은 HARQ 시스템의 효율성을 증가시킨다. 상기 패리티 검사 행렬들에 기초한 LDPC 부호들은 단일 패리티 검사 부호로 확장된 부분을 이용하여 새로운 패리티를 생성하여 전송함으로써 효율적이면서 우수한 성능의 IR 기법을 적용할 수 있다.

참고로 본 발명에서 제안한 설계 방법을 통해 설계된 패리티 검사 행렬들은 Z 값에 대한 지수 행렬을 의미하고 있으나, 해당 패리티 검사 행렬에 대응되는 LDPC 부호에 단축(shortening)과 천공(puncturing)을 적절히 적용하면 다양한 블록 길이와 부호율을 가지는 LDPC 부호화 기법을 적용할 수 있음은 자명하다. 다시 말해, 도 11내지 도 17에 표시한 도면들에 대응되는 패리티 검사 행렬에 대응되는 LDPC 부호에 적절한 단축을 적용하여 다양한 정보어 길이를 지원할 수 있으며, 천공을 적절히 적용하여 다양한 부호율을 지원할 수 있으며, 적절한 길이만큼 단일 패리티 검사 비트를 생성 및 전송 함으로써 효율적인 IR 기법을 적용할 수 있다.

한편, LDPC 부호는 도 2에서 나열한 이분 그래프 상에서 합곱 알고리즘에 기반한 반복 복호 알고리즘을 사용하여 복호될 수 있으며, 합곱 알고리즘은 메시지 패싱 알고리즘의 일종이다.

이하에서는 도 7a 및 7b를 참조하여 LDPC 복호화 시 일반적으로 사용되는 메시지 패싱 동작에 대해서 설명하기로 한다.

도 7a 및 7b는 LDPC 복호화를 위해 임의의 검사 노드와 변수 노드에서 수행되는 메시지 패싱 동작을 도시한 도면이다.

도 7a에는 검사 노드 m(700)과 검사 노드 m(700)에 연결되는 다수의 변수 노드들(710, 720, 730, 740)이 도시되어 있다. 또한, 도시되어 있는 T_n _',m은 변수 노드 n'(710)에서 검사 노드 m(700)으로 패싱되는 메시지를 나타내며, E_n,m은 검사 노드 m(700)에서 변수 노드 n(730)으로 패싱되는 메시지를 나타낸다. 여기서, 검사 노드 m(700)에 연결되어 있는 모든 변수 노드들의 집합을 N(m)이라고 정의하고, N(m)에서 변수 노드 n(730)을 제외한 집합을 N(m)＼n이라고 정의하기로 한다.

이 경우, 합곱 알고리즘에 기반한 메시지 업데이트(update) 규칙은 하기 수학식 14와 같이 나타낼 수 있다.

[수학식 14]

여기에서, Sign(E_n,m)은 메시지 E_n,m의 부호(sign)를 나타내고,　|E_n,m|은 메시지 E_n,m의 크기(magnitude)를 나타낸다. 한편, 함수

는 하기의 수학식 15와 같이 나타낼 수 있다.

[수학식 15]

한편, 도 7b에는 변수 노드 x(750)과 변수 노드 x(750)에 연결되는 다수의 검사 노드들(760, 770, 780, 790)이 도시되어 있다. 또한, 도시되어 있는 E_y _',x은 검사 노드 y'(760)에서 변수 노드 x(750)로 패싱되는 메시지를 나타내며, T_y,x은 변수 노드 x(750)에서 변수 노드 y(780)로 패싱되는 메시지를 나타낸다. 여기서, 변수 노드 x(750)에 연결되어 있는 모든 변수 노드들의 집합을 M(x)이라고 정의하고, M(x)에서 검사 노드 y(780)을 제외한 집합을 M(x)＼y라고 정의하기로 한다. 이 경우, 합곱 알고리즘에 기반한 메시지 업데이트(update) 규칙은 하기 수학식 16과 같이 나타낼 수 있다.

[수학식 16]

여기에서, E_x는 변수 노드 x의 초기 메시지 값을 의미한다.

또한, 노드 x의 비트 값을 판정할 경우에는 하기 수학식 17과 같이 나타낼 수 있다.

[수학식 17]

이 경우, P_x값에 따라 노드 x에 대응하는 부호화 비트를 판정할 수 있다.

도 7a 및 7b에서 상술한 방식은 일반적인 복호화 방법이라는 점에서 더 이상 구체적인 설명은 생략하도록 한다. 다만, 도 7a 및 7b에서 설명한 방법 외에도 변수 노드와 검사 노드에서의 패싱되는 메시지 값을 결정하는 데 있어 다른 방법이 적용될 수도 있다(Frank R. Kschischang, Brendan J. Frey, and Hans-Andrea Loeliger, "Factor Graphs and the Sum-Product Algorithm," IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 47, NO. 2, FEBRUARY 2001, pp498-519).

아래에서는 상기 도 4를 기반으로 송신기 동작에 대해 구체적으로 설명한다.

구체적으로, 도 4와 같이, 송신 장치(400)는 가변 길이 입력 비트들을 처리하기 위해, 세그먼테이션부(410), 제로 패딩부(420), LDPC 인코더(430), 레이트 매칭부(440) 및 변조부(450)를 포함할 수 있다.

여기에서, 도 4 에 도시된 구성요소는, 가변 길이 입력 비트들에 대한 인코딩 및 변조(encoding and modulation)를 수행하는 구성요소로서, 이는 일 예일 뿐이며, 경우에 따라 도 4 에 도시된 구성요소 중 일부는 생략 또는 변경될 수 있고, 다른 구성요소가 더 추가될 수도 있다.

한편, 도 4에 도시된 LDPC 인코더(430)는 도 8에 도시된 LDPC 인코더(810)가 수행하는 동작을 수행할 수 있다.

한편, 송신 장치(400)는 필요한 파라미터(가령, 입력 비트 길이, ModCod(modulation and code rate), 제로 패딩을 위한 파라미터, LDPC 코드의 코드 레이트/코드 길이, 인터리빙(interleaving)을 위한 파라미터, 리피티션(repetition)을 위한 파라미터, 펑처링(Puncturing)을 위한 파라미터 및 변조 방식 등)를 결정하고, 결정된 파라미터를 기초로 부호화하여 도 5의 수신 장치(500)로 전송할 수 있다.

입력 비트들의 수가 가변적이라는 점에서, 입력 비트들의 수가 기설정된 값보다 큰 경우, 입력 비트는 기설정된 값 이하의 길이를 갖도록 세그먼테이션(segmentation)될 수 있다. 또한 세그먼트된 블록 각각은 하나의 LDPC 코딩된 블록에 대응될 수 있다. 다만, 입력 비트들의 수가 기설정된 값보다 작거나 같은 경우, 입력 비트는 세그먼테이션되지 않는다. 입력 비트들은 하나의 LDPC 코딩된 블록에 대응될 수 있다.

이하에서는 상기 세그멘테이션 방법에 대하여 도 18을 기반으로 보다 상세히 서술하도록 한다. 입력 비트들의 개수가 B이고 상기 B가 기설정된 값인 K_max 보다 클 경우 세그멘테이션이 된다. 이하에서는 LDPC 부호의 최대 입력 비트 수와 블록의 개수를 기반으로 세그멘테이션이 수행된다. 상기 최대 입력 비트 수와 블록의 개수는 이하 표 21과 같을 수 있다.

[표 21]

상기 표 21에서 K_max는 가장 큰 LDPC 부호의 패리티 검사 행렬에 대응되는 LDPC 정보어 비트 수로서 가장 큰 하나의 LDPC 부호어를 생성하기 위해 필요한 최대 입력 비트 수이고, K_min은 가장 작은 LDPC 부호의 패리티 검사 행렬로부터 하나의 LDPC 부호어를 생성하기 위해 필요한 최대 LDPC 정보어 비트 수이다.

편의 상, K_max는 시스템에서 주어진 가장 큰 패리티 검사 행렬을 이용하여 부호화를 수행할 수 있는 최대 LDPC 입력 비트 (또는 정보 비트) 수, K_min은 시스템에서 주어진 가장 작은 패리티 검사 행렬을 이용하여 부호화를 수행할 수 있는 최대 LDPC 입력 비트(또는 정보 비트) 수라 명명한다.

K_min은 시스템에서 입력할 수 있는 최소 크기의 코드 블록의 비트 수를 의미하는 것이 아님에 유의한다. K_min 보다 작은 크기의 코드 블록은 상기 가장 작은 LDPC 부호 또는 패리티 검사 행렬에 대해 적절히 단축 방법을 적용하여 LDPC 부호화를 수행할 수 있다.

N_ldpc _{_b}는 패리티 검사 행렬의 열 블록 (column block)의 개수이며 K_ldpc _{_b}는 패리티 검사 행렬의 정보어 파트의 열 블록의 개수를 의미한다. 상기 수학식 3에서 n은 상기 N_ldpc _{_} _b와 동일 하며, m은 상기 (N_ldpc _{_b} - K_ldpc _{_b})와 동일하다.

세그멘테이션이 된 블록의 개수를 C라고 할 때 C값은 이하 수학식 18과 같이 나타낼 수 있다.

[수학식 18]

상기 수학식 18에서 K_max 값은 상기 LDPC 부호의 Z값이 최대일 경우로 LDPC 부호의 최대 입력 비트의 개수를 의미한다. 일 예로 상기 표 21과 같을 수 있다. K_max 값은 적용할 부호율에 따라 서로 다른 값을 가지는데, 통상적으로 시스템에서 데이터를 전송하기 위해서는 채널의 상황에 따라 MCS (modulation and coding scheme)가 결정하기 때문에 부호율 정보는 이미 정해져 있다고 가정할 수 있다. 따라서 해당 부호율에 해당되는 K_max 값을 사용한다.

코드블록(Codeblock) 세그멘테이션의 출력 비트들을

라고 할 때 상기 r은 r번째 코드블록을 의미하고, K_r은 r번째 코드블록의 비트의 개수를 의미한다. 상기 세그멘테이션 블록의 입력 비트개수 B와 상기 수학식 18의 C를 기반으로 하여 이하 수학식 19와 같이 J 값을 구하도록 한다. J값은 패딩 비트를 삽입하기 전의 코드블록의 길이를 임시로 구한 값이다.

[수학식 19]

이하에서는 상기 J가 LDPC 부호의 K_ldpc _{_b}와 가장 작은 Z값의 곱의 배수가 되는 수로 조정한다. 이하 수학식 20에서는 상기 가장 작은 Z값이 27이고, 다른 Z값은 27의 배수인 경우를 가정하였다.

[수학식 20]

또는

상기에서

는 상기 K_min과 동일하다. 상기 수학식 19 및 20은 LDPC 부호화를 적용할 정보 비트 수를 결정하는 과정으로서 부호화를 적용하게 될 LDPC 부호를 결정하는 것과 동일한 과정으로 간주할 수 있다.

위와 같은 수식에 의하여 소정의 개수의 ‘0’를 패딩하여 코드블록의 길이를 LDPC 부호의 정보어 비트 수와 동일하도록 한다.

이하 수학식 21를 기반으로 ‘0’이 패딩되는 비트들을 계산하도록 한다. 상기 패딩 비트는 코드블록의 개수(=C)와 LDPC 입력 비트의 개수의 배수가 되도록 한다. 패딩 비트의 개수는 이하 수학식 21과 같다.

[수학식 21]

상기 패딩 비트들을 각 코드블록에 최대한 균등하게 분포하게 하며, 각 코드블록의 개수를 동일하게 하기 위하여 수학식 22와 같이 패딩 비트가

가 되는 코드블록의 개수를 구하도록 한다.

[수학식 22]

이하에서는 상기 수학식 18, 19, 20, 21, 22를 기반으로 도출된 값들을 기반으로 각 코드블록의 길이(K_r)와 패딩 비트의 길이를 결정하도록 한다.

개의 코드블록은

개의 입력 비트들과

개의 패딩비트로 구성하도록 한다. 그러므로 코드블록의 비트 개수는 아래 수학식 23과 같다

[수학식 23]

개의 코드블록은

개의 입력 비트들과

개의 패딩비트로 구성하도록 한다. 그러므로 코드 블록의 비트 개수는 수학식 24와 같다.

[수학식 24]

상기에서 세그멘테이션이 필요없을 경우, 이하와 같다. 패딩 비트를 고려한 블록의 개수는 이하 수학식 25와 같다.

[수학식 25]

패딩 비트 F는 이하 수학식 26과 같이 구할 수 있다.

[수학식 26]

패딩 비트를 포함한 코드블록의 비트 수는 이하 수학식 27과 같다.

[수학식 27]

상기 동작은 이하와 같이 서술될 수 있다.

상기 과정에서

는 K_min으로 치환 가능함에 유의한다.

상기와 같이 세그멘테이션 할 경우 패딩된 코드블록의 길이는 모두 동일하다. 세그멘테이션 된 코드블록의 길이를 동일하게 함으로써, 각 코드블록의 LDPC 부호의 부호화 복호화 파라미터를 동일하게 하여 구현 복잡도를 낮출 수 있다. 또한 각 코드블록의 패딩되는 ‘0’비트들을 최대한 동일하게 함으로써 부호화 성능을 우수하게 할 수 있다. 상기 과정에서 패딩 비트의 차이는 1비트이다. 도 18에서는 상기 과정을 간략하게 도시하였다.

또한 LDPC 부호의 입력 비트 K_ldpc = K_r 이며, 서브 매트릭스의 크기인 Z는 이하 수학식 28과 같다.

[수학식 28]

상기 세그멘테이션 과정을 간단히 정리하면 다음과 같다.

먼저 시스템에서 주어진 가장 큰 패리티 검사 행렬을 이용하여 부호화를 수행할 수 있는 최대 LDPC 입력 비트(또는 정보 비트) 수(K_max)에 기반하여 코드 블록의 개수를 결정한다.

그 다음 시스템에서 주어진 가장 작은 패리티 검사 행렬을 이용하여 부호화를 수행할 수 있는 최대 입력 비트 (또는 정보 비트) 수(K_min)에 기반하여, 코드 블록의 크기를 결정하고, 상기 코드 블록의 크기에 기반하여 패딩 (또는 단축) 비트 수를 결정한다. 또한 실제 LDPC 부호화를 수행할 패리티 검사 행렬은 상기 코드 블록의 크기에 따라 결정할 수 있다.

그 다음으로 상기 결정된 패딩 (또는 단축) 비트 수 만큼 패딩 (또는 단축) 을 적용하여 코드 블록을 결정한 다음, 상기 결정된 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행한다.

상기 표 21과 수학식 18 내지 수학식 28에 기반한 세그멘테이션은 주어진 LDPC 부호어 비트 수 또는 LDPC 부호의 정보어 비트 수가 일정한 크기로 증가하는 경우에 적용할 수 있다. 예를 들면, 상기 표 21과 수학식 18 내지 수학식 28에 기반한 세그멘테이션을 적용하는 LDPC 부호의 경우에 3개의 부호어 비트 수 또는 정보어 비트 수가 주어져 있으며 부호어 비트 수는 각각 648, 1296, 1944와 같이 648 간격으로 일정하게 증가하고 있으며, 정보어 비트 수는 각각 부호율에 따라 K_min, 2×K_min, 3×K_min (= K_max)와 같이 K_min 간격으로 일정하게 증가한다.

이와 같이 주어진 LDPC 부호들의 정보 비트 수가 K_min과 같이 일정한 간격으로 증가할 경우에는 상기 세그멘테이션 과정에서 K_min에 기반하여 LDPC 부호의 패리티 검사 행렬을 결정하는 과정이 수학식 20과 같이 간단해진다. 즉, 상기 패리티 검사 행렬을 결정하는 과정은 상기 수학식 19 또는 20으로부터 결정되는 가장 큰 코드블록의 크기를 이용하여 결정됨을 알 수 있다.

다음은 주어진 LDPC 부호어 비트 수 또는 LDPC 부호의 정보어 비트 수가 일정한 크기로 증가하지 않는 경우에 대한 세그멘테이션 방법의 실시 예를 서술한다.

먼저 입력 비트들의 개수가 B이고 상기 B가 기설정된 값인 Kmax 보다 클 경우에 세그멘테이션이 적용 되는 것은 동일하며, 이하에서는 LDPC 부호의 최대 입력 비트 수를 기반으로 세그멘테이션이 수행되는 실시 예에 대해 설명한다.

먼저 LDPC 부호의 최대 입력 비트 수 K_max와 LDPC 부호의 최소 정보어 비트 수 K_min이 다음 표 22와 같다

[표 22]

설명의 편의를 위해 시스템에서 주어진 각 LDPC 부호의 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행할 수 있는 각각의 최대 정보 비트 수를 K_min, 2×K_min, 3×K_min, K_max와 같이 4 개라 하자. 즉, 4개의 주어진 LDPC 부호가 있으며, K_max는 12×K_min이기 때문에 일정한 간격으로 증가하는 경우가 아님을 쉽게 알 수 있다.

세그멘테이션이 된 블록의 개수를 C라고 할 때 C값은 수학식 18과 동일하게 나타낼 수 있다. 상기 수학식 18에서 K_max 값은 상기 LDPC 부호의 Z값이 최대일 경우에 대응되는 값으로 LDPC 부호에 대한 최대 입력 비트 수를 의미한다.

코드 블록 세그멘테이션의 출력 비트들을

라고 할 때 상기 r은 r번째 코드블록을 의미하고, K_r은 r번째 코드 블록의 비트의 개수를 의미한다. 상기 입력 비트 수 B와 상기 수학식 18의 C를 기반으로 하여 수학식 19와 같이 J 값을 구하도록 한다. J 값은 패딩 비트를 삽입하기 전의 코드블록의 길이를 임시로 구한 값이다.

위와 같은 조건에서의 세그멘테이션 과정을 간단히 정리하면 다음과 같다.

그 다음 시스템에서 주어진 가장 작은 패리티 검사 행렬을 이용하여 부호화를 수행할 수 있는 최대 입력 비트 (또는 정보 비트) 수(K_min)에 기반하여, 코드 블록의 크기를 결정하고, 상기 코드 블록의 크기에 기반하여 패딩 (또는 단축) 비트 수를 결정한다. 또한 실제 LDPC 부호화를 수행할 패리티 검사 행렬은 상기 코드블록의 크기에 따라 결정할 수 있다.

그 다음으로 상기 결정된 패딩 (또는 단축) 비트 수 만큼 패딩 (또는 단축)을 적용하여 코드 블록을 결정한 다음, 상기 결정된 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행한다.

상기 세그멘테이션 과정에서 코드 블록의 크기에 따라 LDPC 부호의 패리티 검사 행렬을 결정하는 과정은, 앞선 세그멘테이션 방법과 달리 상기 코드 블록 크기의 범위에 따라 서로 다른 결정 방법을 적용해야 함을 알 수 있다. 예를 들어, 상기 예에서는 J 값이 3×K_min보다 크거나 크지 않은 경우에 따라 K'을 결정하는 방식이 상이하다.

즉, 이와 같이 시스템에서 주어진 각 LDPC 부호의 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행할 수 있는 각각의 최대 정보 비트 수가 균일하게 증가되지 않는 경우에는 상기 가장 큰 코드블록의 크기 J 값의 범위에 따라 K' 또는 패리티 검사 행렬을 결정하기 위해 최소 2개 이상의 서로 다른 방법이 존재해야 함을 알 수 있다.

상기 세그멘테이션 과정은 다음과 같이 나타낼 수 있다.

복호화 과정은 상기 부호화 과정의 역과정을 통해 구현할 수 있다. 예를 들면, 먼저 수신기에서 수신 신호로부터 세그멘테이션이 적용되기 전의 입력 비트의 크기를 결정한다. 시스템에 따라 상기 세그멘테이션이 적용되기 전의 입력 비트들을 트랜스포트 블록(transport block, 또는 전송 블록)이라고 명명하기도 한다. 그 다음 시스템에서 주어진 가장 작은 패리티 검사 행렬을 이용하여 부호화를 수행할 수 있는 최대 입력 비트 (또는 정보 비트) 수(K_min)에 기반하여, 코드 블록의 크기를 결정하고, 상기 코드 블록의 크기에 기반하여 패딩 (또는 단축) 비트 수를 결정한다. LDPC 부호화를 수행할 패리티 검사 행렬은 상기 코드 블록의 크기에 기반하여 결정될 수도 있지만, 상기 트랜스포트 블록의 크기에 기반하여 결정될 수도 있다. 또한 통상적으로 상기 수신 신호에는 전송을 위한 MCS 정보와 주어진 시스템 자원(resource) 크기 정보가 포함되어 있기 때문에, 상기 MCS 정보 및/또는 시스템 자원 크기 정보에 기반해서도 상기 패리티 검사 행렬을 결정할 수도 있다.

상기 패리티 검사 행렬이 결정되면, 상기 결정된 패딩 (또는 단축) 비트 수 만큼 패딩 (또는 단축)을 적용하여 LDPC 복호화를 수행할 코드 블록을 결정하고, 상기 MCS 정보 및/또는 시스템 자원 크기 정보, 결정된 코드 블록의 크기에 기반하여 하나의 코드 블록을 전송하기 위한 총 부호화 비트 수를 결정하고 복호를 진행한다.

레이트매칭부(440)의 입력 비트들은 상기 LDPC 인코딩부 (430)의 출력 비트들로 C =(i ₀ , i ₁ , i ₂ , ... , i _Kldpc _-1, p ₀ , p ₁ , p ₂ , ... , p _Nldpc _- _Kldpc _-1 ) 이다. i _k (0≤k< K _ldpc )는 LDPC 인코딩부 (430)의 입력 비트들을 의미하며 p _k (0≤k< N _ldpc - K _ldpc )는 LDPC 패리티 비트들을 의미한다. 상기 레이트 매칭부(440)은 인터리버(441)와 펑처링/리피티션/제로 제거부(442)를 포함한다.

변조부(450)는 레이트매칭부(440)에서 출력되는 비트열을 변조하여 수신 장치(가령, 도 5의 500)로 전송한다.

구체적으로, 변조부(450)는 레이트매칭부(440)에서 출력되는 비트들을 디멀티플렉싱(demultiplexing)하고, 이를 성상도(constellation)에 맵핑할 수 있다.

즉, 변조부(450)는 레이트매칭부(440)에서 출력되는 비트들을 시리얼-투-패러렐(serial-to-parallel) 변환하여, 일정한 개수의 비트로 구성된 셀(cell)을 생성할 수 있다. 여기에서, 각 셀을 구성하는 비트의 개수는 성상도에 맵핑되는 변조 심볼을 구성하는 비트의 개수와 동일할 수 있다.

이후, 변조부(450)는 디멀티플렉싱된 비트들을 성상도에 맵핑할 수 있다. 즉, 변조부(450)는 디멀티플렉싱된 비트들을 QPSK, 16-QAM, 64-QAM, 256-QAM, 1024-QAM, 4096-QAM 등의 다양한 변조 방식을 통해 변조하여 변조 심볼을 생성하고, 이를 성상점(constellation point)에 맵핑할 수 있다. 이 경우, 디멀티플렉싱된 비트들은 변조 심볼 개수만큼의 비트를 포함하는 셀을 구성한다는 점에서, 각 셀이 순차적으로 성상점에 맵핑될 수 있다.

그리고, 변조부(450)는 성상도에 맵핑된 신호를 변조하여 수신 장치(500)로 전송할 수 있다. 예를 들어, 변조부(450)는 OFDM(Orthogonal Frequency Division Multiplexing) 방식으로 이용하여 성상도에 맵핑된 신호를 OFMD 프레임에 맵핑하고, 이를 할당된 채널을 통해 수신 장치(500)로 전송할 수 있다.

한편, 송신 장치(400)는 부호화, 인터리빙 및 변조에 이용되는 각종 파라미터를 기저장하고 있을 수 있다. 여기에서, 부호화에 이용되는 파라미터는 LDPC 부호의 부호율, 부호어 길이, 패리티 검사 행렬에 대한 정보가 될 수 있다. 그리고, 인터리빙에 이용되는 파리미터는 인터리빙 룰에 대한 정보가 될 수 있으며, 변조에 이용되는 파리미터는 변조 방식에 대한 정보가 될 수 있다. 또한 펑처링에 관한 정보는 펑처링 길이가 될 수 있다. 또한 리피티션에 관한 정보는 리피티션 길이가 될 수 있다. 상기 패리티 검사 행렬에 대한 정보는 본 발명에서 제시하는 패리티 행렬을 사용할 경우 상기 수학식 3과 수학식 4에 의한 순환 행렬의 지수 값을 저장할 수 있다.

이 경우, 송신 장치(400)를 구성하는 각 구성요소는 이러한 파라미터를 이용하여 동작을 수행할 수 있다.

한편, 도시하지 않았지만 경우에 따라 송신 장치(400)는 송신 장치(400)의 동작을 제어하기 위한 제어부(미도시)를 더 포함할 수도 있다.

도 8은 본 발명의 일 실시 예에 따른 부호화 장치의 구성을 나타내는 블록도이다. 이 경우, 부호화 장치(800)는 LDPC 부호화를 수행할 수 있다.

도 8에 따르면, 부호화 장치(800)는 LDPC 인코더(810)를 포함한다. LDPC 인코더(810)는 패리티 검사 행렬에 기초하여 입력 비트들에 대해 LDPC 부호화를 수행하여 LDPC 부호어를 생성할 수 있다.

K_ldpc 개의 비트들은 LDPC 인코더(810)를 위한 K_ldpc 개의 LDPC 정보어 비트들 I=(i₀,i₁,...,

)을 구성할 수 있다. LDPC 인코더(810)는 K_ldpc 개의 LDPC 정보어 비트들을 시스테매틱하게 LDPC 인코딩하여, N_ldpc 개의 비트들로 구성된 LDPC 코드워드 Λ=(c₀,c₁,...,

)=(i₀,i₁,...,

,p₀,p₁,...,

)를 생성할 수 있다. 상기 생성 과정은 상기 수학식 1에서 서술한 바와 같이 상기 LDPC 코드워드와 패리티 검사 행렬의 곱이 제로 벡터가 되도록 부호어를 결정하는 과정을 포함한다. 본 발명의 패리티 검사 행렬은 상기 도 3에서 정의한 패리티 검사 행렬과 동일한 구조를 가질 수 있다.

이 경우, LDPC 인코더(810)는 부호율(즉, LDPC 부호의 부호율)에 따라 서로 다르게 정의된 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행할 수 있다.

예를 들어, LDPC 인코더(810)는 부호율이 8/9인 경우 상기 표 1 같은 지수 행렬로 정의되는 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행하고, 부호율이 2/3인 경우 상기 표 2와 같은 지수 행렬로 정의되는 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행할 수 있다. 그리고, LDPC 인코더(810)는 부호율이 4/9인 경우 상기 표 3과 같은 지수 행렬 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행할 수 있다.

한편, LDPC 부호화를 수행하는 구체적인 방법에 대해서는 상술한 바 있다는 점에서 구체적인 중복 설명은 생략하도록 한다.

한편, 부호화 장치(800)는 LDPC 부호의 부호율, 부호어 길이, 패리티 검사 행렬에 대한 정보를 기저장하기 위한 메모리(미도시)를 더 포함할 수 있으며, LDPC 인코더(810)는 이러한 정보를 이용하여 LDPC 부호화를 수행할 수 있다. 상기 패리티 검사 행렬에 대한 정보는 본 발명에서 제시하는 패리티 행렬을 사용할 경우 순환 행렬의 지수 값에 대한 정보를 저장할 수 있다.

아래에서는 상기 도 5를 기반으로 수신기 동작에 대해 구체적으로 설명한다.

복조부(510)는 송신 장치(400)로부터 수신된 신호를 복조한다.

구체적으로, 복조부(510)는 도 4의 송신 장치(400)의 변조부(450)에 대응되는 구성요소로, 송신 장치(400)로부터 수신된 신호를 복조하여, 송신 장치(400)에서 전송한 비트들에 대응되는 값들을 생성할 수 있다.

이를 위해, 수신 장치(500)는 송신 장치(400)에서 모드에 따라 변조한 변조 방식에 대한 정보를 기저장할 수 있다. 이에 따라, 복조부(510)는 모드에 따라 송신 장치(400)로부터 수신된 신호를 복조하여, LDPC 코드워드 비트들에 대응되는 값들을 생성할 수 있다.

한편, 송신 장치(400)에서 전송한 비트들에 대응되는 값은 LLR(Log Likelihood Ratio) 값일 수 있다. 구체적으로, LLR 값은 송신 장치(400)에서 전송한 비트가 0일 확률과 1일 확률의 비율에 Log를 취한 값으로 나타낼 수 있다. 또는, LLR 값은 비트 값 자체가 될 수 있으며, 또한, LLR 값은 송신 장치(400)에서 전송한 비트가 0 또는 1일 확률이 속하는 구간에 따라 결정된 대표 값이 될 수도 있다.

상기 복조부(510)는 LLR 값에 대한 멀티플렉싱(multiplexing)(미도시)을 수행하는 과정을 포함한다. 구체적으로, 송신 장치(400)의 비트 디먹스(demux)(미도시)에 대응되는 구성요소로, 비트 디먹스(미도시)에 대응되는 동작을 수행할 수 있다.

이를 위해, 수신 장치(500)는 송신 장치(400)가 디멀티플렉싱 및 블록 인터리빙을 위해 이용하였던 파라미터에 대한 정보를 기저장하고 있을 수 있다. 이에 따라, 먹스(미도시)는 셀 워드에 대응되는 LLR 값에 대해 비트 디먹스(미도시)에서 수행된 디멀티플렉싱 및 블록 인터리빙 동작을 역으로 수행하여, 셀 워드에 대응되는 LLR 값을 비트 단위로 멀티플렉싱할 수 있다.

레이트 디매칭부(520)은 복조부(510)로부터 출력되는 LLR 값에 LLR 값을 삽입할 수 있다. 이 경우, 레이트 디매칭부(520)는 복조부(510)로부터 출력되는 LLR 값들의 사이에 미리 약속된 LLR 값들을 삽입할 수 있다.

구체적으로, 레이트 디매칭부(520)는 송신 장치(400)의 레이트 매칭부(440)에 대응되는 구성요소로, 인터리버(441), 제로 제거 및 펑처링/리피티션/제로 제거부(442)에 대응되는 동작을 수행할 수 있다.

먼저, 레이트 디매칭부(520)는 상기 송신기의 인터리버(441)에 상응하도록 디인터리빙(deinterleaving)(521) 하도록 한다. 디인터리빙(521)의 출력 값들은 LLR삽입부(522)에서 LDPC 코드워드에서 제로 비트들이 패딩되었던 위치에 제로 비트들에 대응되는 LLR 값을 삽입할 수 있다. 이 경우, 패딩되었던 제로 비트들 즉, 쇼트닝된 제로 비트들에 대응되는 LLR 값은 ∞ 또는 -∞가 될 수 있다. 하지만, ∞ 또는 -∞는 이론적인 값이며, 실질적으로는 수신 장치(500)에서 이용되는 LLR 값의 최대 값 또는 최소 값이 될 수 있다.

이를 위해, 수신 장치(500)는 송신 장치(400)가 제로 비트들을 패딩하기 위해 이용하였던 파라미터에 대한 정보를 기저장하고 있을 수 있다. 이에 따라, 레이트 디매칭부(520)는 LDPC 코드워드에서 제로 비트들이 패딩되었던 위치를 판단하고, 해당 위치에 쇼트닝된 제로 비트들에 대응되는 LLR 값을 삽입할 수 있다.

또한, 레이트 디매칭부(520)의 LLR 삽입부(522)에서는 LDPC 코드워드에서 펑처링된 비트들의 위치에 펑처링된 비트들에 대응되는 LLR 값을 삽입할 수 있다. 이 경우, 펑처링된 비트들에 대응되는 LLR 값은 0이 될 수 있다.

이를 위해, 수신 장치(500)는 송신 장치(400)에서 펑처링을 위해 이용한 파라미터에 대한 정보를 기저장할 수 있다. 이에 따라, LLR 삽입부(522)는 LDPC 패리티 비트들이 펑처링된 위치에 그에 대응되는 LLR 값을 삽입할 수 있다.

LLR 컴바이너(523)는 LLR 삽입부(522) 및 복조부(510)에서 출력되는 LLR 값을 컴바인(combine) 즉, 합산할 수 있다. 구체적으로, LLR 컴바이너(523)는 송신 장치(400)의 펑처링/리피티션/제로 제거부(442)에 대응되는 구성요소로, 리피티션부(442)에 대응되는 동작을 수행할 수 있다. 먼저, LLR 컴바이너(523)는 리피티션된 비트들에 대응되는 LLR 값을 다른 LLR 값과 컴바인할 수 있다. 여기에서, 다른 LLR 값은 송신 장치(400)에서 리피티션된 비트들 생성에 기초가 된 비트들 즉, 리피티션 대상으로 선택되었던 LDPC 패리티 비트들에 대한 LLR 값일 수 있다.

즉, 상술한 바와 같이, 송신 장치(400)는 LDPC 패리티 비트들에서 비트들을 선택하고, 이들을 LDPC 정보어 비트들 및 LDPC 패리티 비트들 사이에서 리피티션시켜 수신 장치(500)로 전송하게 된다.

이에 따라, LDPC 패리티 비트들에 대한 LLR 값은 리피티션된 LDPC 패리티 비트들에 대한 LLR 값 및 리피티션되지 않은 LDPC 패리티 비트들 즉, 인코딩에 의해 생성된 LDPC 패리티 비트들에 대한 LLR 값으로 구성될 수 있다. 따라서, LLR 컴바이너(523)는 동일한 LDPC 패리티 비트들에 LLR 값들을 컴바인할 수 있다.

이를 위해, 수신 장치(500)는 송신 장치(400)에서 리피티션을 위해 이용한 파라미터에 대한 정보를 기저장할 수 있다. 이에 따라, LLR 컴바이너(523)는 리피티션된 LDPC 패리티 비트들에 대한 LLR 값을 판단하고, 이를 리피티션의 기초가 된 LDPC 패리티 비트들에 대한 LLR 값과 컴바인할 수 있다.

또한, LLR 컴바이너(523)는 재전송 혹은 IR(Incremental Redundancy)된 비트들에 대응되는 LLR 값을 다른 LLR 값과 컴바인할 수 있다. 여기에서, 다른 LLR 값은 송신 장치(400)에서 재전송 혹은 IR된 비트들 생성에 기초가 된 LDPC 부호어 비트들 생성을 위해 선택되었던 비트들에 대한 LLR 값일 수 있다.

즉, 상술한 바와 같이, 송신 장치(400)는 HARQ를 위하여 NACK이 발생할 경우 부호어 비트들중 일부 비트들 혹은 모든 비트들을 수신 장치(500)로 전송할 수 있다.

이에 따라, LLR 컴바이너(523)는 재전송 혹은 IR을 통해 수신된 비트들에 대한 LLR 값을 이전 프레임을 통해 수신되는 LDPC 코드워드 비트들에 대한 LLR 값과 컴바인할 수 있다.

이를 위해, 수신 장치(500)는 송신 장치(400)에서 재전송 혹은 IR비트들 생성을 위해 이용한 파라미터에 대한 정보를 기저장할 수 있다. 이에 따라, LLR 컴바이너(523)는 재전송 혹은 IR비트들의 수에 대한 LLR 값을 판단하고, 이를 재전송 비트들의 생성에 기초가 된 LDPC 패리티 비트들에 대한 LLR 값과 컴바인할 수 있다.

디인터리버(524)는 LLR 컴바이너(523)에서 출력되는 LLR 값을 디인터리빙 할 수 있다.

구체적으로, 디인터리버부(524)는 송신 장치(400)의 인터리버(441)에 대응되는 구성요소로, 인터리버(441)에 대응되는 동작을 수행할 수 있다.

이를 위해, 수신 장치(500)는 송신 장치(100)가 인터리빙을 위해 이용하였던 파라미터에 대한 정보를 기저장하고 있을 수 있다. 이에 따라, 디인터리버(524)는 LDPC 코드워드 비트들에 대응되는 LLR 값에 대해 인터리버(441)에서 수행된 인터리빙 동작을 역으로 수행하여, LDPC 코드워드 비트들에 대응되는 LLR 값을 디인터리빙 할 수 있다.

LDPC 디코더(530)는 레이트 디매칭부(520)에서 출력되는 LLR 값에 기초하여 LDPC 디코딩을 수행할 수 있다.

구체적으로, LDPC 디코더(530)는 송신 장치(100)의 LDPC 인코더(430)에 대응되는 구성요소로, LDPC 인코더(430)에 대응되는 동작을 수행할 수 있다.

이를 위해, 수신 장치(500)는 송신 장치(400)에서 모드에 따라 LDPC 인코딩을 수행하기 위해 이용하였던 파라미터에 대한 정보를 기저장하고 있을 수 있다. 이에 따라, LDPC 디코더(530)는 모드에 따라 레이트 디매칭부(520)에서 출력되는 LLR 값에 기초하여 LDPC 디코딩을 수행할 수 있다.

예를 들어, LDPC 디코더(530)는 합곱 알고리즘(sum-product algorithm)에 기반한 반복 복호 방식에 기초하여 레이트 디매칭부(520)에서 출력되는 LLR 값에 기초하여 LDPC 디코딩을 수행하고, LDPC 디코딩에 따라 에러가 정정된 비트들을 출력할 수 있다.

제로 제거부(540)는 LDPC 디코더(2460, 2560)에서 출력되는 비트들에서 제로 비트들을 제거할 수 있다.

구체적으로, 제로 제거부(540)는 송신 장치(400)의 제로 패딩부(420)에 대응되는 구성요소로, 제로 패딩부(420)에 대응되는 동작을 수행할 수 있다.

이를 위해, 수신 장치(500)는 송신 장치(400)에서 제로 비트들을 패딩하기 위해 이용하였던 파라미터에 대한 정보를 기저장하고 있을 수 있다. 이에 따라, 제로 제거부(540)는 LDPC 디코더(530)에서 출력되는 비트들에서 제로 패딩부(420)에서 패딩되었던 제로 비트들을 제거할 수 있다.

디세그먼테이션부(550)는 송신 장치(400)의 세그먼테이션부(410)에 대응되는 구성요소로, 세그먼테이션부(410)에 대응되는 동작을 수행할 수 있다.

이를 위해, 수신 장치(500)는 송신 장치(400)가 세그먼테이션을 위해 이용하였던 파라미터에 대한 정보를 기저장하고 있을 수 있다. 이에 따라, 디세그먼테이션부(550)는 제로 제거부(540)에서 출력되는 비트들 즉, 가변 길이 입력 비트들에 대한 세그먼트들을 결합하여, 세그먼테이션 전의 비트들을 복원할 수 있다.

도 9는 본 발명의 일 실시 예에 따른 복호화 장치의 구성을 나타내는 블록도이다. 도 9에 따르면, 복호화 장치(900)는 LDPC 디코더(910)를 포함할 수 있다. 한편, 복호화 장치(900)는 LDPC 부호의 부호율, 부호어 길이, 패리티 검사 행렬에 대한 정보를 기저장하기 위한 메모리(미도시)를 더 포함할 수 있으며, LDPC 디코더(910)는 이러한 정보를 이용하여 LDPC 부호화를 수행할 수 있다. 하지만, 이는 일 예일 뿐, 해당 정보들은 송신 장치 측으로부터 제공될 수도 있다.

LDPC 디코더(910)는 패리티 검사 행렬에 기초하여 LDPC 부호어에 대해 LDPC 복호화를 수행한다.

예를 들어, LDPC 디코더(910)는 반복 복호 알고리즘을 통해 LDPC 부호어 비트들에 대응되는 LLR(Log Likelihood Ratio) 값을 패싱하여 LDPC 복호화를 수행하여 정보어 비트들을 생성할 수 있다.

여기에서, LLR 값은 LDPC 부호어 비트들에 대응되는 채널 값으로, 다양한 방법으로 표현될 수 있다.

예를 들어, LLR 값은 송신 측에서 채널을 통해 전송한 비트가 0일 확률과 1일 확률의 비율에 Log를 취한 값으로 나타낼 수 있다. 또한, LLR 값은 경판정에 따라 결정된 비트 값 자체가 될 수 있으며, 송신 측에서 에서 전송한 비트가 0 또는1일 확률이 속하는 구간에 따라 결정된 대표 값이 될 수도 있다.

이 경우, 송신 측은 도 8과 같은 LDPC 인코더(810)를 이용하여 LDPC 부호어를 생성할 수 있다.

한편, LDPC 복호화 시 이용되는 패리티 검사 행렬은 도 3에서 도시한 패리티 검사 행렬과 동일한 행태일 수 있다.

이 경우, LDPC 디코더(910)는 부호율(즉, LDPC 부호의 부호율)에 따라 서로 다르게 정의된 패리티 검사 행렬을 이용하여 LDPC 복호화를 수행할 수 있다.

예를 들어, LDPC 디코더(910)는 부호율이 8/9인 경우 표 1과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 복호화를 수행하고, 부호율이 2/3인 경우 표 2와 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 복호화를 수행할 수 있다. 그리고, LDPC 디코더(910)는 부호율이 4/9인 경우 표 3과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 복호화를 수행할 수 있다.

도 10은 본 발명의 다른 실시 예에 따른 LDPC 디코더 구조도를 나타낸다.

한편, 상술한 바와 같이 LDPC 디코더(910)는 반복 복호 알고리즘을 사용하여 LDPC 복호화를 수행할 수 있으며, 이 경우, LDPC 디코더(910)는 도 10과 같은 구조로 구성될 수 있다. 다만, 반복 복호 알고리즘의 경우 이미 공지된 사항이라는 점에서, 도 10에 도시된 세부 구성 역시 일 예일 뿐이다.

도 10에 따르면, 복호화 장치(1000)는 입력 처리기(1011), 메모리(1012), 변수 노드 연산기(1013), 제어기(1014), 검사 노드 연사기(1015) 및 출력 처리기(1016)를 포함한다.

입력처리기(1011)는 입력되는 값을 저장한다. 구체적으로, 입력 처리기(1011)는 무선 채널을 통해 수신되는 수신 신호의 LLR 값을 저장할 수 있다.

제어기(1014)는 무선 채널을 통해 수신되는 수신 신호의 블록의 크기(즉, 부호어의 길이), 부호율에 대응되는 패리티 검사 행렬을 기반으로 하여 변수 노드 연산기(1013)에 입력되는 값의 개수 및 메모리(1012)에서의 주소 값, 검사 노드 연산기(1015)에 입력되는 값의 개수 및 메모리(1012)에서의 주소 값 등을 결정한다.

본 발명의 일 실시 예에 따르면, i 번째 열 그룹의 0 번째 열에서 1이 위치한 행의 인덱스에 대응 되는 표 1 내지 표 3과 같은 지수 행렬에 의해서 결정되는 패리티 검사 행렬을 기반으로 하여 복호화를 수행할 수 있다.

메모리(1012)는 변수 노드 연산기(1013)와 검사 노드 연산기(1015)의 입력 데이터 및 출력 데이터를 저장한다.

변수 노드 연산기(1013)는 제어기(1014)에서 입력 받은 입력 데이터의 주소 정보 및 입력 데이터의 개수 정보에 따라 메모리(1012)에서 데이터들을 입력 받아 변수 노드 연산을 한다. 이후, 변수 노드 연산기(1013)는 제어기(1014)에서 입력 받은 출력 데이터의 주소 정보 및 출력 데이터의 개수 정보에 기초하여 변수 노드 연산 결과들을 메모리(1012)에 저장한다. 또한, 변수 노드 연산기(1013)에서는 입력 처리기(1011)와 메모리(1012)에서 입력 받은 데이터를 기반으로 하여 변수 노드 연산 결과를 출력 처리기(1016)에 입력한다. 여기에서, 변수 노드 연산은 도 8을 기반으로 상술한바 있다.

검사 노드 연산기(1015)는 제어기(1014)에서 입력받은 입력 데이터의 주소 정보 및 입력 데이터의 개수 정보에 기초하여 메모리(1012)에서 데이터들을 입력받아 검사 노드 연산을 한다. 이후, 검사 노드 연산기(1015)는 제어기(1014)에서 입력받은 출력 데이터의 주소 정보 및 출력 데이터의 개수 정보에 기초하여 변수 노드 연산 결과들을 메모리(1012)에 저장한다. 여기에서, 검사 노드 연산은 도 6을 기반으로 상술한바 있다.

출력 처리기(1016)는 변수 노드 연산기(1013)로부터 입력받은 데이터를 기반으로 하여 송신 측의 부호어의 정보어 비트들이 0이었는지 1이었는지 경판정한 후, 그 경판정 결과를 출력하게 되고, 출력 처리기(1016)의 출력 값이 최종적으로 복호화된 값이 되는 것이다. 이 경우, 도 6에서 하나의 변수 노드로 입력되는 모든 메시지 값(초기 메시지 값과 검사 노드로부터 입력되는 모든 메시지 값들)을 더한 값을 기반으로 경판정 할 수 있다.

Claims

채널 부호화 방법에 있어서,
가장 큰 패리티 검사 행렬에 대응되는 최대 정보 비트 수에 기반하여 코드 블록의 개수를 결정하는 과정;
가장 작은 패리티 검사 행렬에 대응되는 최대 정보 비트 수에 기반하여 코드 블록의 크기를 결정하는 과정;
상기 코드 블록의 크기에 따라 패딩 비트 수를 결정하는 과정;
상기 결정된 패딩 비트 수 만큼 패딩을 적용하여 코드 블록을 결정하는 과정;
상기 코드 블록의 크기에 따라 LDPC 부호화를 수행할 패리티 검사 행렬을 결정하는 과정;
상기 코드 블록에 대해 상기 LDPC 부호화를 수행하는 과정을 특징으로 하는 채널 부호화 방법.
제1항에 있어서,
상기 코드 블록 크기에 따라 LDPC 부호화를 수행할 패리티 검사 행렬을 결정함에 있어서,
상기 코드 블록 크기의 범위에 따라 서로 다른 패리티 검사 행렬 결정 방법을 적용함을 특징으로 하는 채널 부호화 방법.
채널 복호화 방법에 있어서,
수신 신호로부터 세그멘테이션이 적용되기 전의 입력 비트의 크기를 결정하는 과정;
가장 큰 패리티 검사 행렬에 대응되는 최대 정보 비트 수에 기반하여 코드 블록의 개수를 결정하는 과정;
가장 작은 패리티 검사 행렬에 대응되는 최대 정보 비트 수에 기반하여 코드 블록의 크기를 결정하는 과정;
상기 코드 블록의 크기 중 적어도 하나에 따라 패딩 비트 수를 결정하는 과정;
상기 결정된 패딩 비트 수 만큼 패딩을 적용하여 코드 블록을 결정하는 과정;
상기 코드 블록에 대응되는 부호화 비트 수를 결정하는 과정;
LDPC 부호화를 수행할 패리티 검사 행렬을 결정하는 과정;
상기 패리티 검사 행렬에 기반하여 상기 코드 블록에 대해 LDPC 복호화를 수행하는 과정을 특징으로 하는 채널 복호화 방법.
제3항에 있어서,
상기 코드 블록에 대응되는 부호화 비트 수를 결정하는 과정 및 상기 LDPC 부호화를 수행할 패리티 검사 행렬을 결정하는 과정은;
MCS (modulation and coding scheme) 정보 및 할당된 시스템 자원 크기 정보 중 적어도 하나에 기반하여 결정됨을 특징으로 하는 채널 복호화 방법.
제3항에 있어서,
상기 LDPC 부호화를 수행할 패리티 검사 행렬을 결정하는 과정은;
상기 세그멘테이션이 적용되기 전의 입력 비트의 크기 또는 코드 블록의 크기에 기반하여 결정됨을 특징으로 하는 채널 복호화 방법.