KR102104937B1

KR102104937B1 - Ldpc 부호의 부호화 장치, 그의 부호화 방법, 복호화 장치 및 그의 복호화 방법

Info

Publication number: KR102104937B1
Application number: KR1020140058599A
Authority: KR
Inventors: 정홍실; 명세호; 김경중
Original assignee: 삼성전자주식회사
Priority date: 2013-06-14
Filing date: 2014-05-15
Publication date: 2020-04-27
Anticipated expiration: 2034-05-15
Also published as: CN105284053A; BR112015031113A2; US10411736B2; KR102227467B1; CA2915740C; KR20210030323A; MX2019010132A; US20240048158A1; US20190349008A1; KR20140145978A; EP3008826A4; KR102303818B1; US20220209792A1; CA3103110C; MX2015017052A; WO2014200304A1; EP3008826A1; CN112968708B; MX367512B; CN112968708A

Abstract

부호화 장치가 개시된다. 본 부호화 장치는 패리티 검사 행렬에 기초하여 입력 비트들에 대해 LDPC 부호화를 수행하여 64800 개의 비트로 구성된 LDPC 부호어를 생성하는 LDPC 인코더를 포함하며, 패리티 검사 행렬은, 정보어 부분 행렬과 패리티 부분 행렬을 포함하며, 정보어 부분 행렬은, 각각 360 개의 열을 포함하는 복수의 열 그룹으로 구성되며, 매 360 번째 열에 존재하는 1 값의 위치를 나타내는 테이블로 정의된다.

Description

LDPC 부호의 부호화 장치, 그의 부호화 방법, 복호화 장치 및 그의 복호화 방법 {METHOD AND APPARATUS FOR ENCODING AND DECODING OF LOW DENSITY PARITY CHECK CODES}

본 발명은 LDPC 부호의 부호화 장치, 그의 부호화 방법, 복호화 장치 및 그의 복호화 방법에 관한 것으로, 보다 상세하게는 패리티 검사 행렬에 기초하여 LDPC 부호화 및 복호화를 수행하는 LDPC 부호의 부호화 장치, 그의 부호화 방법, 복호화 장치 및 그의 복호화 방법에 관한 것이다.

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

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

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

이하에서는 도 1을 참조하여 시스테메틱(systematic) LDPC 부호어를 설명하고자 한다. 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에서, 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와 관계가 있음을 의미한다.

한편, 패리티 검사 행렬에 따라 LDPC 부호의 성능이 결정될 수 있다. 따라서, 우수한 성능을 갖는 LDPC 부호를 위해 패리티 검사 행렬을 설계하는 것이 필요하다.

본 발명은 상술한 필요성에 따른 것으로, LDPC 부호화 및 복호화 성능을 향상시킬 수 있는 LDPC 부호의 부호화 장치, 그의 부호화 방법, 복호화 장치 및 그의 복호화 방법을 제공함에 있다.

이상과 같은 목적을 달성하기 위한 본 발명의 일 실시 예에 따른 부호화 장치는 패리티 검사 행렬에 기초하여 입력 비트들에 대해 LDPC 부호화를 수행하여 64800 개의 비트로 구성된 LDPC 부호어를 생성하는 LDPC 인코더를 포함하며, 상기 패리티 검사 행렬은, 정보어 부분 행렬과 패리티 부분 행렬을 포함하며, 상기 정보어 부분 행렬은, 각각 360 개의 열을 포함하는 복수의 열 그룹으로 구성되며, 매 360 번째 열에 존재하는 1 값의 위치를 나타내는 테이블로 정의된다.

여기에서, 상기 LDPC 인코더는, 부호율이 6/15인 경우, 표 17과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행할 수 있다.

또한, 상기 LDPC 인코더는, 부호율이 8/15인 경우, 표 14와 같은 테이블로 정의되는 패리티 검사 행렬을 이용하는 LDPC 부호화를 수행할 수 있다.

그리고, 상기 LDPC 인코더는, 부호율이 10/15인 경우, 표 18과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행할 수 있다.

또한, 상기 LDPC 인코더는, 부호율이 12/15 인 경우, 표 16과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행할 수 있다.

한편, 본 발명의 일 실시 예에 따른 부호화 방법은 패리티 검사 행렬에 기초하여 입력 비트들에 대해 LDPC 부호화를 수행하여 64800 개의 비트로 구성된 LDPC 부호어를 생성하는 단계를 포함하며, 상기 패리티 검사 행렬은, 정보어 부분 행렬과 패리티 부분 행렬을 포함하며, 상기 정보어 부분 행렬은, 각각 360 개의 열을 포함하는 복수의 열 그룹으로 구성되며, 매 360 번째 열에 존재하는 1 값의 위치를 나타내는 테이블로 정의된다.

여기에서, 상기 LDPC 부호어를 생성하는 단계는, 부호율이 6/15인 경우, 표 17과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행할 수 있다.

또한, 상기 LDPC 부호어를 생성하는 단계는, 부호율이 8/15인 경우, 표 14와 같은 테이블로 정의되는 패리티 검사 행렬을 이용하는 LDPC 부호화를 수행할 수 있다.

그리고, 상기 LDPC 부호어를 생성하는 단계는, 부호율이 10/15인 경우, 표 18과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행할 수 있다.

또한, 상기 LDPC 부호어를 생성하는 단계는, 부호율이 12/15 인 경우, 표 16과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행할 수 있다.

이상과 같은 목적을 달성하기 위한 본 발명의 일 실시 예에 따른 부호화 장치는 패리티 검사 행렬에 기초하여 64800 개의 비트로 구성된 LDPC 부호어에 대해 LDPC 복호화를 수행하는 LDPC 디코더를 포함하며, 상기 패리티 검사 행렬은, 정보어 부분 행렬과 패리티 부분 행렬을 포함하며, 상기 정보어 부분 행렬은, 각각 360 개의 열을 포함하는 복수의 열 그룹으로 구성되며, 매 360 번째 열에 존재하는 1 값의 위치를 나타내는 테이블로 정의된다.

여기에서, 상기 LDPC 디코더는, 부호율이 6/15인 경우, 표 17과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC복호화를 수행할 수 있다.

또한, 상기 LDPC 디코더는, 부호율이 8/15인 경우, 표 14와 같은 테이블로 정의되는 패리티 검사 행렬을 이용하는 LDPC 복호화를 수행할 수 있다.

그리고, 상기 LDPC 디코더는, 부호율이 10/15인 경우, 표 18과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 복호화를 수행할 수 있다.

또한, 상기 LDPC 디코더는, 부호율이 12/15 인 경우, 표 16과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 복호화를 수행할 수 있다.

한편, 본 발명의 일 실시 예에 따른 부호화 방법은 패리티 검사 행렬에 기초하여 64800 개의 비트로 구성된 LDPC 부호어에 대해 LDPC 복호화를 수행하는 단계를 포함하며, 상기 패리티 검사 행렬은, 정보어 부분 행렬과 패리티 부분 행렬을 포함하며, 상기 정보어 부분 행렬은, 각각 360 개의 열을 포함하는 복수의 열 그룹으로 구성되며, 매 360 번째 열에 존재하는 1 값의 위치를 나타내는 테이블로 정의된다.

여기에서, 상기 LDPC 복호화를 수행하는 단계는 부호율이 6/15인 경우, 표 17과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 복호화를 수행할 수 있다.

또한, 상기 LDPC 복호화를 수행하는 단계는 부호율이 8/15인 경우, 표 14와 같은 테이블로 정의되는 패리티 검사 행렬을 이용하는 LDPC 복호화를 수행할 수 있다.

그리고, 상기 LDPC 복호화를 수행하는 단계는, 부호율이 10/15인 경우, 표 18과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 복호화를 수행할 수 있다.

또한, 상기 LDPC 복호화를 수행하는 단계는, 부호율이 12/15 인 경우, 표 16과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 복호화를 수행할 수 있다.

이상과 같은 본 발명의 다양한 실시 예에 따르면 LDPC 부호화 및 복호화 성능이 향상될 수 있다.

도 1은 시스테메틱 LDPC 부호의 부호어를 도시한 도면,
도 2는 일반적인 (8,2,4) LDPC 부호의 패리티 검사 행렬과 팩터 그래프를 도시한 도면,
도 3은 본 발명의 일 실시 예에 따른 패리티 검사 행렬을 도시한 도면,
도 4는 본 발명의 일 실시 예에 따른 도 3의 패리티 검사 행렬의 행과 열을 퍼뮤테이션하여 생성된 패리티 검사 행렬을 도시한 도면,
도 5는 LDPC 복호화에 이용되는 검사 노드와 변수 노드를 도시한 도면,
도 6은 본 발명의 일 실시 예에 따른 부호화 장치의 구성을 설명하기 위한 블록도,
도 7은 본 발명의 일 실시 예에 따른 송신 장치의 구성을 설명하기 위한 블록도,
도 8은 본 발명의 일 실시 예에 따른 복호화 장치의 구성을 설명하기 위한 블록도,
도 9는 본 발명의 일 실시 예에 따른 복호화 장치를 설명하기 위한 블록도,
도 10은 본 발명의 일 실시 예에 따른 수신 장치의 구성을 설명하기 위한 블록도,
도 11 및 도 12는 본 발명의 일 실시 예에 따른 LDPC 부호화 수행 시 발생되는 효과를 설명하기 위한 도면들,
도 13은 본 발명의 일 실시 예에 따른 부호화 방법을 설명하기 위한 흐름도, 그리고,
도 14는 본 발명의 일 실시 예에 따른 복호화 방법을 설명하기 위한 흐름도이다.

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

이하 본 발명은 통신/방송 시스템에서 LDPC 부호화 및 LDPC 복호화 기술에 대하여 설명한다.

이하, 본 발명은 유럽 디지털 방송 표준(standard)의 하나인 DVB-T2(Digital Video Broadcasting the 2nd Generation Terrestrial) 시스템 및 표준 제정 중인 북미 디지털 방송 표준 시스템 ATSC 3.0 (Advanced Television Systems Committee) 에서 정의하고 있는 용어 및 명칭들을 사용한다. 하지만, 본 발명이 용어 및 명칭들에 의해 한정되는 것은 아니며, 다른 시스템에도 동일하게 적용될 수 있다.

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

도 2는 4 개의 행(row)과 8 개의 열(column)로 이루어진 LDPC 부호의 패리티 검사 행렬 H₁의 일 예와 이를 터너 그래프(tanner graph)로 도시한 도면이다. 도 2를 참조하면, 패리티 검사 행렬 H₁은 열이 8개 있기 때문에 길이가 8인 부호어(codeword)를 생성하며, H₁을 통해 생성된 부호는 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)의 일종이며, 메시지 패싱 알고리즘이라 함은 bipartite 그래프 상에서 에지를 통해 메시지들을 교환하고, 변수 노드 혹은 검사 노드로 입력되는 메시지들로부터 출력 메시지를 계산하여 업데이트하는 알고리즘을 나타낸다.

여기에서, i 번째 변수 노드의 메시지를 기반으로 i 번째 부호화 비트의 값을 결정할 수 있다. i 번째 부호화 비트의 값은 경판정과 연판정 모두 가능하다. 그러므로, LDPC 부호어의 i 번째 비트인 c_i의 성능은 터너 그래프의 i 번째 변수 노드의 성능에 대응되며, 이는 패리티 검사 행렬의 i 번째 열의 1의 위치 및 개수에 따라 결정될 수 있다. 즉, 부호어의 N_ldpc 개의 부호어 비트들의 성능은 패리티 검사 행렬의 1의 위치 및 개수에 의해 성능이 좌우된다.

이하에서는 특정한 구조를 가지는 LDPC 부호의 패리티 검사 행렬이 가지는 특성을 도 3을 참조하여 설명하기로 한다.

본 발명은 도 3에 도시된 바와 같은 구조의 패리티 검사 행렬을 고려한다. 도 3에 도시된 패리티 검사 행렬은 부호어가 정보어를 그대로 포함하는 시스테메틱 부호(systematic code)를 부호화 및 복호화할 수 있는 구조이다. 이하, 본 발명은 도 3의 패리티 검사 행렬을 기반으로 설명하나, 본 발명이 적용 가능한 범위가 도 3과 같은 패리티 검사 행렬에 제한되는 것은 아니다.

도 3에서, N_ldpc는 LDPC 부호어의 길이, K_ldpc는 정보어의 길이를 의미한다. 한편, 부호어 또는 정보어의 길이는 부호어 또는 정보어에 포함되는 비트들의 개수를 의미한다. M은 정보어에 대응되는 부분 행렬(310)(이하, 정보어 부분 행렬이라 함)에서 열의 패턴이 반복되는 간격, Q_ldpc는 정보어 부분 행렬(310)에서 각 열이 시클릭 쉬프트(cyclic shift)되는 크기로서, 정수 M 및 Q_ldpc의 값은 Q_ldpc=(N_ldpc-K_ldpc)/M이 성립하도록 결정된다. 이때, K_ldpc/M도 정수가 된다. M 및 Q_ldpc의 구체적인 값은 부호어 길이와 부호율(또는, 코딩 레이트)에 따라 달라질 수 있다.

도 3을 참조하면, 패리티 검사 행렬(300)은 정보어에 대응되는 정보어 부분 행렬(310)(또는, 정보어 행렬) 및 패리티에 대응되는 패리티 부분 행렬(320)(또는, 패리티 행렬)로 구분된다. 정보어 부분 행렬(310)은 K_ldpc 개의 열(column)들을 포함하고, 패리티 부분 행렬(320)은 N_parity=N_ldpc-K_ldpc 개의 열들을 포함한다. 패리티 검사 행렬(300)의 행(row)의 개수와 패리티 부분 행렬(320)의 열의 개수는 N_ldpc-K_ldpc로 동일하다.

패리티 검사 행렬(300)의 K_ldpc 번째 열(column)부터 N_ldpc-1 번째 열을 포함하는 패리티 부분 행렬(320)에서 무게-1(weight-1), 즉, 1 값을 가지는 원소들의 위치는 이중 대각(dual diagonal) 구조를 가진다. 따라서, 패리티 부분 행렬(320)에 포함되는 열들 중, N_ldpc-1 번째 열을 제외한 나머지 열들의 차수(degree)(여기에서, 차수는 각 열에 포함된 1의 개수이다)는 모두 2이며, N_ldpc-1 번째 열의 차수는 1이다.

한편, 정보어 부분 행렬(310), 즉, 0 번째 열부터 K_ldpc-1 번째 열을 포함하는 부분 행렬의 구조는 다음과 같은 규칙에 따른다.

첫째, 패리티 검사 행렬(300)에서 정보어에 대응되는 K_ldpc 개의 열들은 M 개씩 동일 열 그룹(column group)에 속하며, 정보어 부분 행렬(310)은 총 K_ldpc/M 개의 열 그룹들로 구분된다. 동일한 열 그룹 내에 속한 열들에서 1이 존재하는 행(row)의 위치는 서로 Q_ldpc만큼 시클릭 쉬프트된 관계를 가진다.

둘째, i 번째(i=0,1,..,K_ldpc/M-1) 열 그룹의 0 번째 열의 차수를 D_i라 하고, 1이 있는 각 행(row)의 위치를

이라 하면, i 번째 열 그룹 내의 j 번째 열에서 k 번째 무게-1이 위치한 행의 인덱스(즉, i 번째 열 그룹 내의 j 번째 열에서 k 번째 1이 위치한 행의 인덱스)

는 하기의 수학식 2와 같이 결정된다.

여기에서, k=0,1,2,...,D_i-1, i=0,1,...,K_ldpc/M-1, j=1,2,...,M-1이다.

한편, 수학식 2는 하기의 수학식 3과 같이 동일하게 표현될 수 있다.

여기에서, k=0,1,2,...,D_i-1, i=0,1,...,K_ldpc/M-1, j=1,2,...,M-1이다.

이들 수학식에서,

는 i 번째 열 그룹 내의 j 번째 열에서 k 번째 무게-1이 있는 행의 인덱스, N_ldpc는 LDPC 부호어의 길이, K_ldpc는 정보어의 길이, D_i는 i 번째 열 그룹에 속하는 열들의 차수, M은 하나의 열 그룹에 속하는 열 개수를 의미한다.

이들 수학식에 의하면,

값만을 알면 i 번째 열 그룹 내의 k 번째 무게-1이 있는 행의 인덱스를 알 수 있음이 나타난다. 그러므로, 각각의 열 그룹 내의 0 번째 열에서 k 번째 무게-1이 있는 행의 인덱스 값을 저장하면, 도 3의 구조를 갖는 패리티 검사 행렬(300)(즉, 패리티 검사 행렬(300)의 정보어 부분 행렬(310))에서 무게-1이 있는 열과 행의 위치가 파악될 수 있다.

한편, 상술한 규칙들에 따르면, i 번째 열 그룹에 속하는 열들의 차수는 모두 D_i로 동일하다. 상술한 규칙들에 따라 패리티 검사 행렬(300)에 대한 정보를 저장하고 있는 LDPC 부호는 다음과 같이 간략하게 표현될 수 있다.

구체적인 예로서, N_ldpc가 30, K_ldpc가 15, Q_ldpc가 3인 경우, 3 개의 열 그룹의 0 번째 열에서 무게-1이 위치한 행의 위치 정보는 하기의 수학식 4와 같은 수열들로 표현될 수 있다. 하기의 수학식 4와 같은 수열들은 '무게-1 위치 수열(weight-1 position sequence)'이라 지칭될 수 있다.

여기에서,

은 i 번째 열 그룹 내의 j 번째 열에서 k 번째 무게-1이 있는 행의 인덱스를 의미한다.

한편, 각 열 그룹의 0 번째 열에서 1이 위치한 행의 인덱스를 나타내는 수학식 4와 같은 무게-1 위치 수열들은 하기의 표 1과 같이 보다 간략하게 표현될 수 있다.

표 1은 패리티 검사 행렬에서 무게-1, 다시 말해, 1 값을 가지는 원소의 위치를 나타낸 것으로서, i 번째 무게-1 위치 수열은 i 번째 열 그룹에 속한 0 번째 열에서 무게-1이 있는 행의 인덱스들로 표현된다.

한편, 도 3에서 도시한 패리티 검사 행렬(300)을 열과 행을 이하의 수학식 5(로우 퍼뮤테이션)와 수학식 6(컬럼 퍼뮤테이션)에 의해 퍼뮤테이션(permutation)하면, 도 3에서 도시한 패리티 검사 행렬(300)은 도 4에서 도시한 패리티 검사 행렬(400)의 형태로 도시될 수 있다.

여기에서, 로우 퍼뮤테이션이라 함은 패리티 검사 행렬(300)의 행의 순서를 수학식 5를 이용하여 변경함을 의미한다. 그리고, 컬럼 퍼뮤테이션이라 함은 패리티 검사 행렬(300)의 열의 순서를 수학식 6을 이용하여 변경함을 의미한다.

한편, 수학식 5 및 수학식 6에 기초하여 퍼뮤테이션을 수행하는 방법은 다음과 같다. 여기에서, 컬럼 퍼뮤테이션은

에 의해 패리티 부분 행렬(320)에 대해서만 적용된다는 점을 제외하고, 로우 퍼뮤테이션과 동일한 원리가 적용된다. 이하에서는 로우 퍼뮤테이션을 일 예로 설명하도록 한다.

로우 퍼뮤테이션의 경우, X 번째 행에 대해 X= Q_ldpc×i+ j를 만족하는 i, j를 산출하고, 산출된 i, j를 M×j+ i에 대입하여 X 번째 행이 퍼뮤테이션되는 행을 산출하게 된다. 예를 들어, 7 번째 행의 경우, 7= 2×i+ j를 만족하는 i,j는 각각 3,1이 되므로, 7 번째 행은 10×1+ 3= 13 번째 행으로 퍼뮤테이션된다.

한편, 도 3의 패리티 검사 행렬이 수학식 5와 수학식 6에 의해 행과 열이 각각 퍼뮤테이션되면, 도 4에서 도시한 패리티 검사 행렬의 형태로 도시될 수 있다.

도 4를 참조하면, LDPC 부호의 패리티 검사 행렬(400)은 전체를 다수의 부분 블록(partial block)들로 분할하고, 부분 블록들 각각에 M×M 준순환 행렬(quasi-cyclic matrix)을 대응시키는 형태를 가진다.

도 4에 도시된 패리티 검사 행렬(400)은 M×M 준순환 행렬 단위로 구성되므로, M 개의 열(column)들을 column-block (또는, column group), M 개의 행(row)들을 row-block(또는, row group)이라 명명할 수 있다. 즉, 본 발명에서 사용하는 도 4의 형태의 패리티 검사 행렬(400)은 N_qc _{_} _column=N_ldpc/M 개의 column-block들과 N_{qc_row}=N_parity/M 개의 row-block들로 구성된다.

이하에서는 도 4의 형태의 패리티 검사 행렬(400)을 구성하는 M×M 행렬들에 대하여 상세히 설명하고자 한다.

첫째, 0 번째 행(row)의 (N_qc _{_} _column-1) 번째 열(column)의 M×M 행렬(440)은 하기의 수학식 7의 형태를 갖는다.

수학식 7의 M×M 행렬은 0 번째 행(row)과 (M-1) 번째 열(column)의 값들은 모두 '0'이다. 0≤i≤(M-2)에 대하여 i 번째 열(column)의 (i+1) 번째 행(row)은 '1'이며 그 외의 모든 값들은 '0'이다.

둘째, 도 4의 패리티 검사 행렬(400)의 패리티 부분 행렬(420)에서 0≤i≤(N_ldpc-K_ldpc)/M-1에 대하여 (K_ldpc/M+i) 번째 column-block의 i 번째 row-block은 단위 행렬 I_M _×M(460)들로 구성된다. 또한, 0≤i≤(N_ldpc-K_ldpc)/M-2에 대하여 (K_ldpc/M+i) 번째 column-block의 (i+1)번째 row-block은 단위 행렬 I_M _×M(460)들로 구성된다.

셋째, 정보어 부분 행렬(410)은 준순환 행렬 P가 시클릭 쉬프트된 형태인

, 혹은 준순환 행렬 P가 시클릭 쉬프트된 행렬

가 결합된 형태가 될 수 있다.

한편, 준순환 행렬 P는 하기의 수학식 8과 같다.

수학식 8의 준순환 행렬 P는 M×M크기를 가지는 정사각 행렬로서, 준순환 행렬 P를 구성하는 M 개의 행들 및 열들 각각의 차수는 1인 행렬이다.

한편, 준순환 행렬 P의 위첨자 a_ij가 0일 때, 즉 준순환 행렬 P⁰는 단위 행렬 I_M×M를 나타내며, 준순환 행렬 P의 위첨자 a_ij가 ∞일 때, 즉 준순환 행렬 P^∞는 영(zero) 행렬을 나타낸다. 도 4에서 LDPC 부호의 전체 패리티 검사 행렬은 전체 열의 개수가 N_ldpc=M×N_qc _{_} _column이고, 전체 행의 개수가 N_parity=M×N_qc _{_} _row이다. 즉, 도 4의 패리티 검사 행렬(400)은 N_qc _{_} _column 개의 'column-block'들과 N_qc _{_} _row 개의 'row block'들로 구성된다.

도 4의 형태의 패리티 검사 행렬(400)은 non-zero quasi-cycle 행렬의 위치와 해당 위치에서의 지수 값들로 표현된다.

LDPC 부호의 경우 패리티 검사 행렬에 따라 부호어 성능이 결정된다. 그러므로, 패리티 검사 행렬을 어떻게 설계하느냐는 중요하다. 일반적으로 열과 행의 무게 분포와 사이클 분포에 의하여 성능이 결정될 수 있다.

열의 무게 분포는 N_ldpc 개의 각각의 열(column)에 대하여 몇 개의 열에 몇 개의 1이 존재하는지를 의미한다. 또한, 행의 무게 분포는 N_ldpc-K_ldpc 개의 각각의 행(row)에 대하여 몇 개의 행에 몇 개의 1이 존재하는지를 의미한다. 또한 1의 무게 혹은 디그리는 각 열 및 행의 1의 개수를 의미 한다.

여기에서, 열과 행의 무게 분포는 density evolution(reference: Richardson, T., and URBANKE, R.: 'The capacity of low-density parity-check codes under message-passing decoding', IEEE Trans. Inf. Theory, 2001, 47, (2), pp. 599-618)이라는 방법에 기반하여 결정될 수 있다.

구체적으로, density evolution 방법을 이용할 경우, 주어진 디그리 분포를 가지는 패리티 검사 행렬을 기반으로 LDPC 부호화/복호화하였을 경우, 임의의 SNR(signal to noise ratio)에서 iteration을 몇 번 수행하였을 때 부호화 오류 확률이 '0'이 되는지 추정할 수 있다. density evolution의 경우, 부호어 길이가 무한대인 경우를 가정하여 부호화 오류 확률이 '0'이 되는지 추정하기 때문에 유한 길이를 갖는 부호에 대한 패리티 검사 행렬을 설계할 경우에는 density evolution만을 가지고 패리티 검사 행렬의 차수 분포를 결정할 수는 없다.

또한, 패리티 검사 행렬의 차수 분포에 따른 1의 개수는 부호화/복호화 복잡도에 영향을 주므로 density evolution이라는 이론적 접근 방법뿐만 아니라 실제 부호화/복호화 복잡도 및 설계된 패리티 검사 행렬을 기반으로 한 부호 성능을 검증을 기반으로 패리티 검사 행렬을 설계하도록 한다.

이하에서는 본 발명에서 사용하고자 하는 패리티 검사 행렬의 설계 방법에 대하여 상세히 설명하고자 한다.

패리티 검사 행렬의 형태는 매우 다양하게 존재할 수 있으나, 본 발명에서는 도 3에서 도시한 특정 형태를 갖는 패리티 검사 행렬을 설계하고자 한다. 또한, 패리티 검사 행렬은 density evolution을 기반하여 coding gain이 최대가 될 수 있는 디그리 분포를 결정하도록 하며, cycle 제거 방법에 의하여 error floor가 BER/FER이 낮은 영역에서 발생하도록 한다. 상술한 바와 같이, 도 3의 형태의 패리티 검사 행렬(300)은 열과 행의 퍼뮤테이션에 의해 도 4의 형태를 갖는 패리티 검사 행렬(400)이 된다. 도 4의 형태인 경우 M×M 행렬을 기반으로 설계하므로 설계가 용이하다. 그러므로, 본 발명에서는 도 4의 형태를 갖는 패리티 검사 행렬(400)의 형태로 패리티 검사 행렬을 설계 한 후 행과 열의 퍼뮤테이션을 통하여 도 3의 형태를 갖는 패리티 검사 행렬(300)을 설계하고자 한다.

이하에서는 본 발명에서 사용하고자 하는 패리티 검사 행렬을 설계하는 방법에 대하여 상세히 설명하고자 한다.

단계 1) 설계하고자 하는 패리티 검사 행렬의 크기 (N_ldpc, K_ldpc), M 및 Q_ldpc 값을 결정한다.

본 발명에서는 상술한 패리티 검사 행렬의 파라미터들은 하기의 표 2와 같이 결정할 수 있다.

도 4의 형태를 갖는 패리티 검사 행렬(400)의 경우, 패리티 부분 행렬(420)은 고정되어 있으므로 정보어 부분 행렬(410)에 대해서만 1의 위치와 분포를 결정하면 된다. 또한, 정보어 부분 행렬(410)에서 1의 위치와 분포는 M×M quasi-cyclic 행렬들 단위로 구성되므로, zero 행렬이 아닌 quasi-cyclic(준순환) 행렬의 개수, 위치 그리고 준순환 행렬의 지수 값인 cyclic shift 값을 결정하면 된다.

이하 단계 2에서는 zero 행렬이 아닌 quasi-cyclic 행렬의 개수를 결정하도록 한다.

단계 2) Density evolution 방법을 이용하여 패리티 검사 행렬의 디그리 분포를 결정한다.

상술한 바와 같이, 패리티 검사 행렬의 1의 분포는 LDPC 부호의 성능을 좌우한다. 그러므로, 본 발명에서는 density evolution 방법에 의하여 패리티 검사 행렬의 1의 분포를 결정하도록 한다. 즉, 가능한 모든 디그리 분포들 중에서 소정의 횟수만큼의 반복 복호를 통해 에러 확률이 소정의 값으로 수렴할 확률이 높은 즉, SNR이 가장 낮은 디그리 분포를 선택하도록 한다.

이때 제한해야 할 사항은 이하와 같다.

1) LDPC 부호의 1의 개수는 부호화 및 복호화의 복잡도에 영향 미치므로 1의 개수를 한정하도록 하도록 한다.

2) 각 열(column)당 존재하는 1의 개수가 다양할 경우 복호화 복잡도가 증가할 수 있으므로 1의 개수의 종류는 한정하도록 한다.

우선, 표 2의 파라미터를 갖는 패리티 검사 행렬을 기반으로 상술한 제한 사항을 고려하여 가능한 모든 디그리 분포들(리스트)를 결정하도록 한다. 이후 각 부호율 별로 target SNR을 결정한 후, density evolution에 의하여 target SNR에서 리스트에 있는 디그리 분포들을 갖는 패리티 검사 행렬을 기반으로 부호화/복호화되는 LDPC 부호는 복호화 시 몇 번 iteration 했을 때 error 확률이 소정의 값으로 수렴하는지 산출한다.

이때, 리스트에 있는 모든 디그리 분포에 대해, 특정 값보다 작은 iteration 내에 에러 확률이 소정 값 이하로 수렴할 경우, target SNR 값을 작게 조정하고 디그리 분포에 대한 density evolution을 재차 수행한다.

다만, 특정 값보다 많은 iteration 내에서도 모든 디그리 분포들에 대한 density evolution 결과 값이 수렴하지 않는 경우, SNR 값을 크게 조정하여 degree distribution에 대한 density evolution을 재차 수행하도록 한다.

이러한 과정을 반복하여 리스트에 존재하는 모든 디그리 분포 중에서 낮은 SNR과 작은 반복 복호(즉, iteration 횟수)에서 에러 확률이 소정 값 이하로 수렴하는 디그리 분포를 단계 1의 결과로 결정한다.

단계 3) 단계 2에서 결정된 디그리 분포를 기반으로 non-zero quasi-cyclic 행렬의 위치를 결정하도록 한다.

이때 non-zero quasi-cyclic 행렬의 위치는 잘 알려진 PEG 알고리즘을 이용하도록 한다(X.-Y. Hu, E. Eleftheriou, and D.-M. Arnold, "Regular and irregular progressive edge-growth tanner graphs", IEEE Trans. Inf. Theory, vol. 51, no. 1, pp. 386-398, Jan. 2005.). 이때, 본 발명에서 제시하는 추가적인 제약 조건은 각 행(row)별로 1의 개수를 최대한 균일할 수 있도록 하는 것이다.

단계 4) error floor가 발생하지 않도록 상기 quasi-cycle 행렬의 지수들을 조정하도록 한다.

이때 패리티 부분 행렬의 경우 고정되어 있으므로 고려하지 않도록 한다. 정보어 부분 행렬에서 열 디그리(column degree)가 가장 작은 열들부터 소정의 행(row)에 위치한 non-zero quasi-cycle 행렬의 지수 값들만 변경하도록 한다.

이때 동일한 행에 위치한 non-zero quasi-cycle 행렬의 지수 값은 모두 다른 값으로 하도록 한다. 이때, 패리티 부분 행렬(420)의 경우는 예외로 한다.

이때, 지수 값을 변경하는 행의 순서는 다양할 수 있다. 지수 값의 변경은 더 이상 minimum cycle의 cycle 값이 증가하거나 minimum cycle을 갖는 variable node 개수가 개선되지 않을 때까지 반복한다. 본 발명에서는 단계 4를 리프팅이라 한다.

단계 5) 도 4를 기반으로 설계된 패리티 검사 행렬을 도 3의 형태로 로우 퍼뮤테이션(row permutation)과 컬럼 퍼뮤테이션(column permutation)을 통해 변형하도록 한다.

이때, 로우 퍼뮤테이션은 하기의 수학식 9에 기초하여 수행되고, 컬럼 퍼뮤테이션을 하기의 수학식 10에 기초하여 수행될 수 있다.

이하에서는 부호율 10/15(=2/3)의 경우를 일 예로, 패리티 검사 행렬을 설계하는 과정을 보다 상세히 설명하고자 한다.

단계 1) 설계하고자 하는 패리티 검사 행렬의 크기와 관계되는 파라미터들 (N_ldpc, K_ldpc), M 및 Q_ldpc 값을 하기의 표 3과 같이 결정한다.

가능한 모든 디그리 분포(degree distribution) 중 density evolution 결과 가장 낮은 SNR에서 오류 확률이 소정의 값이 될 가능성이 높은 분포들을 선택한다. 예를 들어, 선택된 분포들에 대하여 SNR= 2.6dB일 경우 density evolution 방법에 의하여 BER=10^-5가 될 iteration 수를 구한다. 선택된 분포들과 선택된 분포들에 대한 density evolution로 얻어진 iteration 수는 하기의 표 4와 같다. 표 4에서 N(x_i)는 x_i의 degree를 갖는 열 그룹 (column group or column block)의 개수를 의미한다.

단계 3) 단계 2에서 결정된 degree distribution을 기반으로 non-zero quasi-cyclic 행렬의 위치를 결정하도록 한다.

본 발명에서는 표 4의 case 6의 degree distribution을 선택하도록 한다. 그리고, 선택된 degree distribution을 만족하도록 non-zero quasi-cycle 행렬의 위치를 결정한다.

한편, case 6을 결정한 이유는 상술한 바와 같이, 패리티 검사 행렬의 차수 분포에 따른 1의 개수는 부호화/복호화 복잡도에 영향을 주므로 density evolution이라는 이론적 접근 방법뿐만 아니라 실제 부호화/복호화 복잡도 및 설계된 패리티 검사 행렬을 기반으로 한 부호 성능을 기반으로 패리티 검사 행렬을 설계하도록 한다.

단계 4) error floor가 발생하지 않도록 quasi-cycle 행렬의 지수들을 조정하도록 한다.

하기의 표 5는 상술한 방법에 의해 결정된 도 4의 형태의 패리티 검사 행렬(400)의 quasi-cycle 행렬의 위치 및 지수 값을 나타낸다. 이 과정에서 사이클 특성을 고려한 리프팅(상술한 단계 4 참조)이라는 방법을 사용한다.

단계 5) 단계 4에서 도 4를 기반으로 설계된 패리티 검사 행렬을 로우 퍼뮤테이션(row permutation)과 컬럼 퍼뮤테이션(column permutation)을 통해 도 3의 형태로 변형하도록 한다.

이하에서는 상술한 패리티 검사 행렬을 설계하는 방법으로 설계된 패리티 검사 행렬의 일 예들을 서술하도록 한다.

임의의 패리티 검사 행렬(H₁)과 이를 로우 퍼뮤테이션 및 컬럼 퍼뮤테이션 한 패리티 검사 행렬(H₂)은 등가임은 잘 알려진 사실이다. 즉, 임의의 도 3의 형태를 갖는 패리티 검사 행렬과 이를 로우 퍼뮤테이션 및 컬럼 퍼뮤테이션한 도 4의 형태를 갖는 패리티 검사 행렬은 등가이다.

또한, 본 발명의 도 3의 형태의 패리티 검사 행렬에서 열 그룹의 순서를 변경한 패리티 검사 행렬도 서로 등가이다. 또한, i 번째 열 그룹의 0 번째 열에서 1이 위치한 행의 인덱스 값이 k₁,k₂,...,k_m(여기에서, m은 i 번째 열 그룹의 column degree)일 경우, i 번째 열 그룹의 0 번째 열에서 1이 위치한 행의 인덱스 값을 (K_x+Q_ldpc×y) mod (N_ldpc-K_ldpc) (1≤k≤m)로 변경할 경우에도 등가이다. Q_ldpc는 상술한 바와 같이 (N_ldpc-K_ldpc)/M이며, M은 열 그룹에 속하는 열의 개수를 의미한다. 또한 y는 임의의 상수이다.

구체적인 예로서, N_ldpc가 30, K_ldpc가 15, Qldpc가 3인 경우, 3 개의 열 그룹의 0 번째 열에서 무게-1이 위치한 행의 위치 정보를 아래 표 6과 같이 표현할 경우,

y가 2인 경우,

1 → (1+3x2) mod 15 = 7

2 → (2+3x2) mod 15 = 8

8 → (8+3x2) mod 15 = 14

10 → (10+3x2) mod 15 = 1

0 → (0+3x2) mod 15 = 6

9 → (9+3x2) mod 15 = 0

13 → (13+3x2) mod 15 = 4

0 → (0+3x2) mod 15 = 6

14 → (14+3x2) mod 15 = 5

이므로,

3 개의 열 그룹의 0 번째 열에서 무게-1이 위치한 행의 위치 정보를 아래 표 7과 같이 표현할 경우에도 등가이다.

또한, 열 그룹의 순서를 변경한 경우에도 등가이므로 아래 표 8로 표현되는 패리티 검사 행렬도 등가이다.

또한, 본 발명의 도 4의 형태를 갖는 패리티 검사 행렬의 경우, 동일 열 그룹 (column group or column block)에 존재하는 quasi-cycle 행렬의 지수 값들을 동일한 값으로 더하거나 뺄 경우 이전의 패리티 검사 행렬과 등가임은 당연하다. 또한, column-block들의 순서를 변경한 패리티 검사 행렬도 등가이다.

이하에서는 본 발명에서 서술한 패리티 검사 행렬의 설계 방법에 의하여 설계된 도 3의 형태를 갖는 패리티 검사 행렬의 일 예들을 서술하고자 한다.

일 예로, 부호어 길이 N_ldpc가 64800, 부호율 R이 6/15, M이 360, Q_ldpc가 108인 경우, 도 3의 구조의 패리티 검사 행렬의 i 번째 열 그룹의 0 번째 열에서 1이 위치한 행의 인덱스들은 아래 표 9와 같다.

즉, 표 9의 i 번째 열 그룹의 0 번째 열에서 1이 위치한 행의 인덱스에 의해 각 열 그룹의 0 번째 열에서 1이 존재하는 행의 위치가 정의되고, 각 열 그룹의 0 번째 열에서 1이 존재하는 행을 Q_ldpc만큼 쉬프트하여 해당 열 그룹의 다른 열에서 1이 위치한 행을 정의할 수 있다.

상술한 예의 경우, Q_ldpc=(64800- 25920)/360=108이고, 0 번째 열 그룹의 0 번째 열에서 1 이 위치한 행의 인덱스는 891, 2309, 3615,... 이므로, 0 번째 열 그룹의 1 번째 열에서 1이 위치한 행의 인덱스는 999(=891+108), 2417(=2309+108), 3723(=3615+108),...이고, 0 번째 열 그룹의 2 번째 열에서 1이 위치한 행의 인덱스는 1107(=999+108), 2525(=2417+108), 3831(=3723+108),...이 될 수 있다.

한편, 본 발명에서의 다른 패리티 검사 행렬도 표 9에서 상술한 방식으로 정의될 수 있다.

다른 예로, 부호어 길이 N_ldpc가 64800, 부호율 R이 8/15, M이 360, Q_ldpc가 84인 경우, 도 3의 구조의 패리티 검사 행렬의 i 번째 열 그룹의 0 번째 열에서 1이 위치한 행의 인덱스들은 하기의 표 10과 같다.

또 다른 예로, 부호어 길이 N_ldpc가 64800, 부호율 R이 10/15, M이 360, Q_ldpc가 60인 경우, 도 3의 구조의 패리티 검사 행렬의 i 번째 열 그룹의 0 번째 열에서 1이 위치한 행의 인덱스들은 하기의 표 11과 같다.

또 다른 예로, 부호어 길이 N_ldpc가 64800, 부호율 R이 12/15, M이 360, Q_ldpc가 36인 경우, 도 3의 구조의 패리티 검사 행렬의 i 번째 열 그룹의 0 번째 열에서 1이 위치한 행의 인덱스들은 하기의 표 12와 같다.

한편, 부호의 설계 과정에서 단계 4)의 과정은 사이클 특성을 고려한 리프팅 방법을 적용하였는데, 만일 사이클 특성뿐만 아니라 다양한 대수적 특성을 추가로 고려하면 더 좋은 성능을 가지는 부호를 설계할 수도 있다.

통상적으로 LDPC 부호의 성능은 사이클 특성뿐만 아니라 차수 분포(degree distribution)도 영향을 주기 때문에, 두 특성을 동시에 고려하여 더 좋은 성능을 가지는 부호를 설계할 수 있다.

본 발명에서는 가장 짧은 길이를 가지는 사이클과 이러한 사이클들에 포함되는 특정 차수를 가지는 변수 노드의 개수에 따라 파라미터를 결정하고 파라미터를 통해 결정되는 규칙에 따라 리프팅 단계에서 수열을 결정할 수 있다.

예를 들어, 차수가 A, B인 열 그룹에 대해 리프팅 과정을 적용할 경우, 차수가 A인 열 그룹의 리프팅을 진행하는 과정에서 사이클에 포함되는 변수 노드 중 차수가 A인 변수 노드의 개수는 x₁ 개 이하이고, 차수가 B인 열 그룹의 리프팅을 진행하는 과정에서 사이클에 포함되는 변수 노드에 대해서 (차수가 A인 변수 노드의 개수 + 차수가 B인 변수 노드의 개수 × C)의 값이 x₂ 개 이하인 사이클만을 고려할 수 있다.

단, 차수가 A 및 B가 아닌 열 그룹에 대해서 리프팅 과정을 적용할 경우에는 모든 사이클을 고려할 수 있다.

여기서, A는 2 이상인 양의 정수(positive integer), B는 A보다 크고 패리티 검사 행렬의 최대 차수(maximum degree) 보다는 작은 양의 정수이며, C는 무게 계수(weighting factor)로서 양의 정수 값을 가진다.

또한, 차수가 A 및 B가 아닌 열 그룹에 대해서 리프팅 과정을 적용할 경우에는 특정 사이클에 대한 구분 없이 모든 사이클을 고려한다.

구체적인 실시 예를 들면, A=3, B=4, C=2인 경우는 다음과 같다.

예를 들면, 리프팅 과정에서 차수가 3인 열 그룹들의 리프팅을 진행하는 과정에서 사이클에 포함되는 변수 노드 중 차수가 3인 변수 노드(열과 동치)가 x₁ 개 이하이며, 차수가 4인 열 그룹들의 리프팅을 진행하는 과정에서 사이클에 포함되는 변수 노드 중 (차수가 4인 변수 노드의 개수 × 2 + 차수가 3인 변수 노드의 개수)가 x₂ 개 이하인 사이클만을 고려하여 리프팅을 진행한다.

즉, 리프팅 과정에서 지수 값을 변경할 때 각각의 변수 노드의 차수에 따라 상기 조건에 해당하는 사이클만 고려하여 상기 사이클을 갖는 변수 노드의 개수가 개선되지 않을 때까지 반복하여 지수 값을 변경하도록 한다.

통상적으로 단순 리프팅은 사이클의 개수가 줄어들도록 패리티 검사 행렬을 설계하는데, 본 과정에서는 상술한 조건을 만족하는 사이클의 개수가 줄어들도록 패리티 검사 행렬을 설계한다.

상술한 조건이 더 좋은 성능을 가지는 LDPC 부호를 설계하는데 영향을 주는 이유는 LDPC 부호는 사이클의 영향뿐만 아니라 차수 분포에도 영향을 받는데 상술한 조건은 사이클과 차수 분포를 고려하였기 때문이다.

이러한 추가 조건을 고려하여 설계한 LDPC 부호의 일 예를 하기의 표 13 내지 표 18에 나타내었다. 참고로 표 9 내지 표 12에 나타낸 LDPC 부호와 동일한 길이와 부호율에 대해 설계하였으며, 표 13에서 고려한 x₁, x₂ 값은 (x₁, x₂)=(4, 5), 표 14에서 고려한 x₁, x₂ 값은 (x₁, x₂)=(4, 5), 표 15에서 고려한 x₁, x₂ 값은 (x₁, x₂)=(3, 4), 표 16에서 고려한 x₁, x₂ 값은 (x₁, x₂)=(3, 4)이다. 또한, 표 17에서 고려한 x₁, x₂ 값은 (x₁, x₂)=(8, 8), 표 18에서 고려한 x₁, x₂ 값은 (x₁, x₂)=(3, 4) 이다.

이와 같은 추가 조건을 고려하여 설계한 결과의 일 예로, 부호어 길이 N_ldpc가 64800, 부호율 R이 6/15, M이 360, Q_ldpc가 108인 경우, 도 3의 구조의 패리티 검사 행렬의 i 번째 열 그룹의 0 번째 열에서 1이 위치한 행의 인덱스들은 아래 표 13과 같다.

추가 조건을 고려하여 설계한 결과의 다른 예로, 부호어 길이 N_ldpc가 64800, 부호율 R이 8/15, M이 360, Q_ldpc가 84인 경우, 도 3의 구조의 패리티 검사 행렬의 i 번째 열 그룹의 0 번째 열에서 1이 위치한 행의 인덱스들은 하기의 표 14와 같다.

추가 조건을 고려하여 설계한 결과의 또 다른 예로, 부호어 길이 N_ldpc가 64800, 부호율 R이 10/15, M이 360, Q_ldpc가 60인 경우, 도 3의 구조의 패리티 검사 행렬의 i 번째 열 그룹의 0 번째 열에서 1이 위치한 행의 인덱스들은 하기의 표 15와 같다.

추가 조건을 고려하여 설계한 결과의 또 다른 예로, 부호어 길이 N_ldpc가 64800, 부호율 R이 12/15, M이 360, Q_ldpc가 36인 경우, 도 3의 구조의 패리티 검사 행렬의 i 번째 열 그룹의 0 번째 열에서 1이 위치한 행의 인덱스들은 하기의 표 16과 같다.

추가 조건을 고려하여 설계한 결과의 또 다른 예로, 부호어 길이 N_ldpc가 64800, 부호율 R이 6/15, M이 360, Q_ldpc가 108인 경우, 도 3의 구조의 패리티 검사 행렬의 i 번째 열 그룹의 0 번째 열에서 1이 위치한 행의 인덱스들은 하기의 표 17과 같다.

추가 조건을 고려하여 설계한 결과의 또 다른 예로, 부호어 길이 N_ldpc가 64800, 부호율 R이 10/15, M이 360, Q_ldpc가 60인 경우, 도 3의 구조의 패리티 검사 행렬의 i 번째 열 그룹의 0 번째 열에서 1이 위치한 행의 인덱스들은 하기의 표 18과 같다.

여기서 주의할 점은 상술한 표 9 내지 표 18에서 각 i 번째 열 그룹에 대한 수열 내의 숫자들의 순서는 바뀌어도 동일한 부호의 패리티 검사 행렬이라는 것이다.

예를 들어, 표 11에서 0 번째 열 그룹에 대응되는 수열을 114, 2135, 3045, 4635, 5512, 5681, 6571, 8943, 10053, 10109, 13161, 13668, 14218, 17417, 19328, 21140 순서로 나열되어 있는데 이 수열을 2135, 8943, 4635, 114, 3045, 10109, 13161, 21140, 5681, 6571, 5512, 19328, 14218, 13668, 17417, 10053과 같이 순서를 바꾸어도 동일한 부호의 패리티 검사 행렬을 나타낸다.

또한, 표 9 내지 표 18에서 각 열 그룹에 대응되는 수열들의 나열 순서를 바꿔도 부호의 그래프 상의 사이클 특성 및 차수 분포 등의 대수적 특성이 바뀌지 않기 때문에, 표 9 내지 표 18에서 나타낸 수열들의 나열 순서가 바뀐 경우도 본 발명에서 제안하는 부호의 설계 방법을 통해 도출할 수 있는 결과의 한 가지 일 예가 될 수 있다.

예를 들어, 표 11에서 0 번째 열 그룹에 대응되는 수열 114, 2135, 3045, 4635, 5512, 5681, 6571, 8943, 10053, 10109, 13161, 13668, 14218, 17417, 19328, 21140과 12번째 열 그룹에 대응되는 수열 19, 768, 1263, 3305, 6513, 7677, 7956, 9040, 13427, 16641, 17280, 18452, 18584, 18925, 19559, 20587의 나열 순서를 바꾸어 0 번째 열 그룹에 대응되는 수열을 19, 768, 1263, 3305, 6513, 7677, 7956, 9040, 13427, 16641, 17280, 18452, 18584, 18925, 19559, 20587로 설정하고, 12 번째 열 그룹에 대응되는 수열을 114, 2135, 3045, 4635, 5512, 5681, 6571, 8943, 10053, 10109, 13161, 13668, 14218, 17417, 19328, 21140으로 설정한 경우, 즉, 0 번째 열 그룹과 12 번째 열 그룹의 나열 순서를 변경하여도 부호의 그래프 상의 사이클 특성 및 차수 분포 등은 변화가 없다(실제로, 각 열 그룹에 대응되는 수열의 나열 순서를 바꾸는 것은 패리티 검사 행렬 내에서 열 그룹의 배치 순서만 바뀌는 것과 동일하기 때문에 주요 대수적 특성이 바뀌지 않는다).

또한, 표 9 내지 표 18에서 임의의 열 그룹에 대응되는 수열들에 대해 모두 동일하게 Q_ldpc의 배수를 더한 결과 또한 부호의 그래프 상의 사이클 특성이나 차수 분포 등의 대수적 특성이 바뀌지 않는 특성이 있기 때문에 본 발명에서 제안하는 부호의 설계 방법을 통해 도출할 수 있는 결과의 한 가지 일 예가 될 수 있다.

예를 들어, 표 11에서 24 번째 열 그룹에 대응되는 수열 12575, 15845, 18200에 대해 모두 동일한 60(즉, Q_ldpc=(N_ldpc-K_ldpc)/M= 60)의 배수를 더한 결과, 즉, 12635(=12575+60), 15905(=15845+60), 18260(=18200+60)과 같은 경우 또한 부호의 그래프 상의 사이클 특성이나 차수 분포 등의 대수적 특성이 바뀌지 않는다(실제로 Q_ldpc 배수를 임의의 수열에 더해진 결과 얻어진 수열은 마치 상기 해당 열 그룹 내에 있는 열들의 순서만 재배열된 것과 동일한 동작이기 때문에 주요 대수적 특성이 바뀌지 않는다).

여기서 주의해야 할 점은 주어진 수열에 Q_ldpc 배수만큼 더 했을 경우에 만일 그 값이 (N_ldpc-K_ldpc) 이상인 값이 나올 경우에는, 그 값에 (N_ldpc-K_ldpc)에 대한 모듈로(modulo) 연산을 적용한 값으로 바꾸어 적용한다는 것이다.

예를 들어, 표 11에서 24 번째 열 그룹에 대응되는 수열 12575, 15845, 18200에 대해 60×60만큼 모두 더한 결과는 16175, 19445, 21800이 되는데, (N_ldpc-K_ldpc)=21600이므로, 주어진 수열에 Q_ldpc 배수만큼 더한 결과에 모듈로-21600을 적용하여 16175, 19445, 200 또는 200, 16175, 19445와 같이 나타낼 수 있다.

이하에서는, 도 3과 같은 구조를 갖는 패리티 검사 행렬을 이용하여 LDPC 부호의 부호화 과정에 대하여 설명하도록 한다. 상술한 바와 같이, LDPC 부호의 부호화 과정은 패리티 검사 행렬과 부호어의 곱이 0가 되는 관계식을 만족하는 부호어 C를 결정하는 것이다. 즉, LDPC 부호화 과정은 HㆍC^T=0과 같이 표현될 수 있다. 여기에서, H는 패리티 검사 행렬이고, C는 LDPC 부호어를 나타낸다.

이하에서는, LDPC 부호화되는 정보어 비트들은 (i₀,i₁,...,

)이고, LDPC 부호화에 의해 생성된 LDPC 부호어 비트들은 (c₀,c₁,...,

)라 할 때, LDPC 부호어 비트들을 산출하는 방법을 설명하도록 한다.

먼저, LDPC 부호는 시스테메틱 부호이므로 0<k<K_ldpc-1에 대한 c_k는 i_k와 동일하게 설정한다. 그리고, 나머지 부호어 비트들에 대하여서는

로 설정한다. 여기에서, p_k는 패리티 비트들이며 이하에서 설명하는 바와 같이 산출될 수 있다.

한편, 본 발명의 일 실시 예에 따라 패리티 검사 행렬은 표 9 내지 표 18과 같이 정의된다는 점에서, 이하에서 설명하는 과정은 패리티 검사 행렬이 표 9 내지 표 18과 같이 정의되는 경우 적용될 수 있다.

먼저, 표 9 내지 표 18에서 i번째 행(row)의 j번째 표기된 값(entry)을 q(i,j,0)라 할 때, 0<l<360에 대해 q(i,j,l)=q(i,j,0)+Q_ldpcㆍl(mod N_ldpc-K_ldpc)라 한다. 여기에서, 더하기 연산 '+'(accumulation)은 모두 GF(Galois Field)(2)에서 정의되는 덧셈 연산을 의미한다(즉, additions in GF(2)). 그리고, Q_ldpc는 정보어 부분 행렬에서 각 열이 시클릭 쉬프트되는 크기로서, 표 9 내지 표 18 각각에서 정의된 값이 될 수 있다.

한편, q(i,j,0) 및 q(i,j,l)이 상기와 같이 정의될 때, 패리티 비트를 산출하는 과정은 하기와 같다.

단계 1) 패리티 비트들을 '0'으로 초기화한다. 즉, p_k=0 for 0<k<N_ldpc-K_ldpc

단계 2) 0<k<K_ldpc의 모든 k 값에 대하여 i와 l을

, l:=k (mod 360)로 설정한다. 여기에서,

는 x 보다 크지 않는 정수 중에서 가장 큰 정수 값이다. 즉,

이다. 이후, 설정된 i와 l값을 기반으로 이하와 같이 모든 j에 대하여 i_k를 p_q _(i,j,l)에 더한다. 즉, p_q(i,0,l)=p_q(i,0,l)+i_k,p_q(i,1,l)=p_q(i,1,l)+i_k,p_q(i,2,l)=p_q(i,2,l)+i_k,...,p_{q(i,w(i)-1,l)}=p_{q(i,w(i)-1,l)}+i_k를 산출한다.

여기에서, w(i)는 표 9 내지 표 18의 i 번째 행의 값들의 개수이며, 패리티 검사 행렬에서 i_k에 대응되는 열의 1의 개수를 의미한다. 또한, 표 9 내지 표 18에서 i 번째 행(row)의 j 번째 표기된 값(entry)인 q(i,j,0)은 패리티 비트의 인덱스이며, 패리티 검사 행렬에서 i_k에 대응되는 열에서 1이 존재하는 행의 위치를 나타낸다.

단계 3) 0<k<N_ldpc-K_ldpc를 만족하는 모든 k에 대해 p_k=p_k+p_k _- ₁를 산출하여 패리티 비트 p_k를 산출하게 된다.

상술한 방식에 의해 패리티 비트들이 산출되며, 결국, 모든 LDPC 부호어 비트들 c₀,c₁,...,

이 산출될 수 있다.

한편, LDPC 부호화 과정을 상술한 바와 같이 기술하는 것은 일 예에 불과하다. 즉, LDPC 부호화는 HㆍC^T=0를 만족하는 LDPC 부호어 C를 산출하는 과정이라는 점에서, 주어진 패리티 검사 행렬에 대해 다양한 부호화 방법이 존재할 수 있음은 물론이다.

예를 들어, DVB-T2 규격에서 적용된 방식이 패리티 검사 행렬이 표 9 내지 표 18과 같이 정의되는 경우에도 적용될 수 있다. 이하에서는, 패리티 검사 행렬이 표 11과 같이 정의되는 경우를 일 예로, DVB-T2 규격에서 기술된 방식에 따른 LDPC 부호화 과정을 개략적으로 설명하도록 한다.

먼저, 길이가 K_ldpc인 정보어 비트들을

라 하고, 길이가 N_ldpc-K_ldpc인 패리티 비트들을

라 할 때, 하기와 같은 과정에 의해 LDPC 부호화가 수행될 수 있다.

단계 1) 패리티 비트들을 '0'으로 초기화한다. 즉,

단계 2) 표 11의 첫 번째 행(즉, i=0인 행)에서 정의되는 패리티 비트의 어드레스를 패리티 비트의 인덱스로 갖는 패리티 비트에 0 번째 정보어 비트 i₀를 누적(accumulate)한다. 이는 아래의 수학식 11과 같이 표현될 수 있다.

여기에서, i₀는 0 번째 정보어 비트, p_i는 i 번째 패리티 비트,

는 바이너리 연산을 의미한다. 바이너리 연산에 의하면, 1

1은 0, 1

0은 1, 0

1은 1, 0

0은 0이다.

단계 3) 나머지 359 개의 정보어 비트들 i_m(m=1,2,...,359)을 패리티 비트에 누적한다. 여기에서, 나머지 정보어 비트들은 i₀와 동일한 열 그룹에 속하는 정보어 비트들일 수 있다. 이때, 패리티 비트의 어드레스는 하기의 수학식 12에 기초하여 결정될 수 있다.

여기에서, x는 정보어 비트 i₀에 대응되는 패리티 비트 누적기(parity bit accumulator)의 어드레스이고, Q_ldpc는 정보어에 대응되는 부분 행렬에서 각 열이 쉬프트되는 크기로 60이다.

결국, 수학식 12에 기초하여 산출된 패리티 비트의 어드레스를 인덱스로 하는 패리티 비트 각각에 정보어 비트들 i_m(m=1,2,...,359) 각각을 누적하며, 일 예로, 정보어 비트 i₁에 대해 하기의 수학식 13과 같은 연산이 수행될 수 있다.

여기에서, i₁는 1 번째 정보어 비트, p_i는 i 번째 패리티 비트,

는 바이너리 연산을 의미한다. 바이너리 연산에 의하면, 1

1은 0, 1

0은 1, 0

1은 1, 0

0은 0이다.

단계 4) 표 11의 두 번째 행(즉, i=1인 행)에서 정의되는 패리티 비트의 어드레스를 패리티 비트의 인덱스로 갖는 패리티 비트에 360 번째 정보어 비트 i₃₆₀를 누적한다.

단계 5) 정보어 비트 i₃₆₀과 동일한 그룹에 속하는 나머지 359 개의 정보어 비트들을 패리티 비트에 누적한다. 이때, 패리티 비트의 어드레스는 수학식 6에 기초하여 결정될 수 있다. 다만, 이 경우, x는 정보어 비트 i₃₆₀에 대응되는 패리티 비트 누적기의 어드레스가 된다.

단계 6) 상술한 단계 4 및 단계 5와 같은 과정을 표 5의 모든 열 그룹에 대해 반복한다.

단계 7) 결국, 하기와 같은 수학식 14에 기초하여 패리티 비트 p_i를 산출하게 된다. 이때, i는 1로 초기화된다.

수학식 8에서, p_i는 i 번째 패리티 비트, N_ldpc는 LDPC 부호어의 길이, K_ldpc는 LDPC 부호어 중 정보어의 길이,

는 바이너리 연산을 의미한다. 바이너리 연산에 의하면, 1

1은 0, 1

0은 1, 0

1은 1, 0

0은 0이다.

결국, 이와 같은 방식에 따라 패리티 비트들을 산출할 수 있게 된다.

한편, i 번째 열 그룹의 0 번째 열에 나타난 패리티 비트의 어드레스는 i 번째 열 그룹의 0 번째 열에서 1이 위치한 행의 인덱스와 동일하다. 그러므로, 표 9 내지 표 18의 i 번째 열 그룹의 0 번째 열에서 1이 위치한 행의 인덱스들은 부호화 과정에서 패리티 비트의 어드레스로 표현된다. 그러므로, 표 9 내지 표 18은 "addresses of parity bit accumulators"들을 의미할 수 있게 된다.

이와 같이, 본 발명에서는 다양한 방식을 이용하여 LDPC 부호화 과정을 수행하여 LDPC 부호어를 생성할 수 있게 된다.

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

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

도 5는 LDPC 복호화를 위해 임의의 검사 노드와 변수 노드에서 메시지 패싱 동작을 나타낸다.

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

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

여기에서, Sign(E_n _,m)은 메시지 E_n _,m의 부호(sign)를 나타내고,

은 메시지 E_n _,m의 크기(magnitude)를 나타낸다. 한편, 함수

는 하기의 수학식 16과 같이 나타낼 수 있다.

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

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

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

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

도 5에서 상술한 방식은 일반적인 복호화 방법이라는 점에서 더 이상 구체적인 설명은 생략하도록 한다. 다만, 도 5에서 설명한 방법 외에도 변수 노드와 검사 노드에서의 패싱되는 메시지 값을 결정하는 데 있어 다른 방법이 적용될 수도 있다(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, pp 498-519).

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

도 6에 따르면, 부호화 장치(600)는 LDPC 인코더(610)를 포함한다. LDPC 인코더(610)는 패리티 검사 행렬에 기초하여 입력 비트들에 대해 LDPC 부호화를 수행하여 LDPC 부호어를 생성할 수 있다. 이때, LDPC 부호어는 64800 개의 비트로 구성될 수 있다. 즉, LDPC 부호어의 길이는 64800이 될 수 있다.

여기에서, 패리티 검사 행렬은 도 3에서 도시한 패리티 검사 행렬(300)과 동일한 구조를 가질 수 있다.

구체적으로, 패리티 검사 행렬은 정보어 부분 행렬과 패리티 부분 행렬을 포함한다.

여기에서, 정보어 부분 행렬은 각각 M 개의 열을 포함하는 복수의 열 그룹으로 구성되며, 매 M 번째 열에 존재하는 1 값의 위치를 나타내는 테이블로 정의될 수 있다. 여기에서, M은 정보어 부분 행렬에서 열의 패턴이 반복되는 간격으로, 360이 될 수 있다. 그리고, 패리티 부분 행렬은 이중 대각 구조를 가질 수 있다.

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

예를 들어, LDPC 인코더(610)는 부호율이 6/15인 경우 표 9, 표 13 또는 표 17과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행하고, 부호율이 8/15인 경우 표 10 또는 표 14와 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행할 수 있다. 그리고, LDPC 인코더(610)는 부호율이 10/15인 경우 표 11, 표 15 또는 표 18과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행하고, 부호율이 12/15인 경우 표 12 또는 표 16과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행할 수 있다.

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

한편, 부호화 장치(600)는 LDPC 부호의 부호율, 부호어 길이, 패리티 검사 행렬에 대한 정보를 기저장하기 위한 메모리(미도시)를 더 포함할 수 있으며, LDPC 인코더(610)는 이러한 정보를 이용하여 LDPC 부호화를 수행할 수 있다. 여기에서, 패리티 검사 행렬에 대한 정보는 본 발명에서 제시하는 패리티 검사 행렬을 사용할 경우, 정보어 부분 행렬은 각각 M 개의 열을 포함하는 복수의 열 그룹으로 구성되며, 매 M 번째 열에 존재하는 1의 값의 위치를 나타내는 테이블을 포함할 수 있다.

도 7은 본 발명의 실시 예에 따른 송신 장치의 구성을 나타내기 위한 블록도이다. 도 7에 도시된 바와 같이, 송신 장치(700)는 BCH(Bose, Chaudhuri, Hocquenghem) 인코더(710), LDPC 인코더(720), 인터리버(730) 및 변조부(740)를 포함한다.

BCH 인코더(710)는 입력 비트들에 대해 BCH 부호화를 수행하고, BCH 부호화에 의해 생성된 BCH 부호어를 LDPC 인코더(720)로 출력한다.

구체적으로, BCH 인코더(710)는 입력 비트들

에 대한 BCH 부호화를 수행함으로써 K_ldpc-K_bch 개의 BCH 패리티 비트들을 생성하고, BCH 부호어

를 생성한다.

BCH 부호어

는 LDPC 부호화를 위한 정보어로서, LDPC 인코더(720)로 입력된다. BCH 부호화는 널리 알려진 기술로서, "Bose, R. C.; Ray-Chaudhuri, D. K. (March 1960), "On A Class of Error Correcting Binary Group Codes", Information and Control 3 (1): 68-79, ISSN 0890-5401" 등의 문헌에 개시되어 있으므로, 본 발명에서 구체적인 설명을 생략한다.

한편, BCH 인코더(710)의 사용 여부는 변경 가능하다. 즉, 경우에 따라 BCH 인코더(710)는 생략될 수도 있다.

LDPC 인코더(720)는 BCH 인코더(710)에서 출력되는 BCH 부호어에 대해 LDPC 부호화를 수행하고, LDPC 부호화에 의해 생성된 LDPC 부호어를 인터리버(730)로 출력한다.

구체적으로, LDPC 인코더(720)는 BCH 인코더(710)에서 출력되는 BCH 부호어

를 정보어로 LDPC 부호화를 수행하여 N_ldpc-K_ldpc 개의 LDPC 패리티 비트들을 생성하고, LDPC 부호어

를 생성한다.

다만, BCH 인코더(710)가 생략되는 경우, LDPC 인코더(720)는 입력 비트들에 대해 LDPC 부호화를 수행할 수 있다.

한편, 도 7의 LDPC 인코더(720)는 도 6에서 설명한 LDPC 인코더(610)로 구현될 수 있다. 즉, LDPC 인코더(720)는 부호율에 따라 정보어 부분 행렬이 표 9 내지 표 18과 같이 정의되며 패리티 부분 행렬이 이중 대각 구조를 갖는 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행할 수 있다.

이를 위해, 송신 장치(700)는 패리티 검사 행렬에 대한 정보를 저장하기 위한 메모리(미도시)를 구비할 수 있다. 이 경우, 패리티 검사 행렬은 부호율에 따라 다양한 형태가 될 수 있으며, 표 9 내지 표 18에서 정의된 테이블이 일 예가 될 수 있다. 여기에서, 패리티 검사 행렬에 대한 정보는 본 발명에서 제시하는 패리티 검사 행렬을 사용할 경우 정보어 부분 행렬은 각각 M 개의 열을 포함하는 복수의 열 그룹으로 구성되며, 매 M 번째 열에 존재하는 1의 값의 위치를 나타내는 테이블을 포함할 수 있다.

인터리버(730)는 LDPC 인코더(720)에서 출력되는 LDPC 부호어에 대해 인터리빙을 수행하고, 인터리빙된 비트들을 변조부(740)로 출력한다.

이 경우, 인터리버(730)는 LDPC 인코더(720)에서 출력되는 LDPC 부호어 비트열을 입력받아 소정의 방식에 의하여 인터리빙을 수행한다. 인터리빙 방식은 다양하게 존재할 수 있으며, 인터리버(730)의 사용 여부는 가변일 수 있다.

변조부(740)는 인터리버(730)에서 출력되는 비트열을 변조하여 수신 장치(가령, 도 10의 1000)로 전송한다.

구체적으로, 변조부(740)는 인터리버(730)에서 출력되는 비트들을 디멀티플렉싱하고, 이를 성상도(constellation)에 맵핑할 수 있다.

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

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

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

한편, 송신 장치(700)는 부호화, 인터리빙 및 변조에 이용되는 각종 파라미터를 기저장하고 있을 수 있다. 여기에서, 부호화에 이용되는 파라미터는 BCH 부호의 부호율 및 부호어 길이, LDPC 부호의 부호율, 부호어 길이, 패리티 검사 행렬에 대한 정보가 될 수 있다. 그리고, 인터리빙에 이용되는 파리미터는 인터리빙 룰에 대한 정보가 될 수 있으며, 변조에 이용되는 파리미터는 변조 방식에 대한 정보가 될 수 있다. 여기에서, 패리티 검사 행렬에 대한 정보는 본 발명에서 제시하는 패리티 검사 행렬을 사용할 경우 정보어 부분 행렬은 각각 M 개의 열을 포함하는 복수의 열 그룹으로 구성되며, 매 M 번째 열에 존재하는 1의 값의 위치를 나타내는 테이블을 포함할 수 있다.

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

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

이 경우, 제어부(미도시)는 BCH 인코더(710)로 BCH 부호의 부호율 및 부호어 길이 에 대한 정보를 제공하며, LDPC 인코더(720)로 LDPC 부호의 부호율, 부호어 길이, 패리티 검사 행렬에 대한 정보를 제공할 수 있다. 또한, 제어부(미도시)는 인터리버(730)로 인터리빙 방식에 대한 정보를 제공하고, 변조부(740)로 변조 방식에 대한 정보를 제공할 수 있다. 여기에서, 패리티 검사 행렬에 대한 정보는 본 발명에서 제시하는 패리티 검사 행렬을 사용할 경우 정보어 부분 행렬은 각각 M개의 열을 포함하는 복수의 열 그룹으로 구성되며, 매 M번째 열에 존재 하는 1의 값의 위치를 나타내는 테이블을 포함할 수 있다.

도 8은 본 발명의 일 실시 예에 따른 복호화 장치의 구성을 나타내는 블록도이다. 도 8에 따르면, 복호화 장치(800)는 LDPC 디코더(810)를 포함할 수 있다.

LDPC 디코더(810)는 패리티 검사 행렬에 기초하여 LDPC 부호어에 대해 LDPC 복호화를 수행한다. 여기에서, LDPC 부호어는 64800 개의 비트로 구성될 수 있다. 즉, LDPC 부호어의 길이는 64800이 될 수 있다.

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

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

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

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

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

여기에서, 정보어 부분 행렬은 각각 M 개의 열을 포함하는 복수의 열 그룹으로 구성되며 매 M 번째 열에 존재하는 1 값의 위치를 나타내는 테이블로 정의된다. 여기에서, M은 정보어 부분 행렬에서 열의 패턴이 반복되는 간격으로, 360이 될 수 있다. 그리고, 패리티 부분 행렬은 이중 대각 구조를 가질 수 있다.

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

예를 들어, LDPC 디코더(810)는 부호율이 6/15인 경우 표 9, 표 13 또는 표 17과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 복호화를 수행하고, 부호율이 8/15인 경우 표 10 또는 표 14와 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 복호화를 수행할 수 있다. 그리고, LDPC 디코더(810)는 부호율이 10/15인 경우 표 11, 표 15 또는 표 18과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 복호화를 수행하고, 부호율이 12/15인 경우 표 12 또는 표 16과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 복호화를 수행할 수 있다.

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

도 9에 따르면, 복호화 장치(900)는 입력 처리기(911), 메모리(912), 변수 노드 연산기(913), 제어기(914), 검사 노드 연사기(915) 및 출력 처리기(916)를 포함한다.

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

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

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

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

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

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

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

한편, 복호화 장치(800)는 LDPC 부호의 부호율, 부호어 길이, 패리티 검사 행렬에 대한 정보를 기저장하기 위한 메모리(미도시)를 더 포함할 수 있으며, LDPC 디코더(810)는 이러한 정보를 이용하여 LDPC 부호화를 수행할 수 있다. 하지만, 이는 일 예일 뿐, 해당 정보들은 송신 측으로부터 제공될 수도 있다. 여기에서, 패리티 검사 행렬에 대한 정보는 본 발명에서 제시하는 패리티 검사 행렬을 사용할 경우 정보어 부분 행렬은 각각 M 개의 열을 포함하는 복수의 열 그룹으로 구성되며, 매 M 번째 열에 존재하는 1의 값의 위치를 나타내는 테이블을 포함할 수 있다.

도 10은 본 발명의 실시 예에 따른 수신 장치의 구성을 설명하기 위한 블록도이다. 도 10에 따르면, 수신 장치(1000)는 복조부(1010), 디인터리버(1020), LDPC 디코더(1030) 및 BCH 디코더(1040)를 포함한다.

복조부(1010)는 송신 장치(가령, 도 7의 700)에서 전송한 신호를 수신하여 복조한다. 구체적으로, 복조부(1010)는 수신된 신호를 복조하여 LDPC 부호어에 대응되는 값을 생성하고, 이를 디인터리버(1020)로 출력할 수 있다.

이 경우, LDPC 부호어에 대응되는 값은 수신된 신호에 대한 채널 값으로 표현될 수 있다. 여기에서, 채널 값을 결정하는 방법은 다양하게 존재할 수 있으며, 일 예로, LLR 값을 결정하는 방법이 될 수 있다.

디인터리버(1020)는 복조부(1010)의 출력 값들에 대해 디인터리빙을 수행하고, 이를 LDPC 디코더(1030)로 출력할 수 있다.

구체적으로, 디인터리버(1020)는 송신 장치(700)의 인터리버(730)에 대응되는 구성요소로, 인터리버(730)에 대응되는 동작을 수행할 수 있다. 즉, 디인터리버(1020)는 인터리버(730)에서 적용된 인터리빙 방식을 역으로 적용하여 복조부(1010)에서 출력되는 LLR 값들을 디인터리빙할 수 있다.

다만, 경우에 따라 송신 장치(700)에서 인터리버(730)가 생략되는 경우, 디인터리버(1020)는 생략될 수 있다.

LDPC 디코더(1030)는 디인터리버(1020)의 출력 값들을 이용하여 LDPC 복호화를 수행하고, LDPC 복호화된 비트들을 BCH 디코더(1040)로 출력할 수 있다. 여기에서, LDPC 복호화된 비트들은 BCH 부호어일 수 있다.

구체적으로, LDPC 디코더(1030)는 송신 장치(700)의 LDPC 인코더(720)에 대응되는 구성요소로, 패리티 검사 행렬에 기초하여 LDPC 복호화를 수행할 수 있다. 한편, 도 10의 LDPC 디코더(1030)는 도 8에서 설명한 LDPC 디코더(810)로 구현될 수 있다. 즉, LDPC 디코더(1030)는 부호율에 따라 정보어 부분 행렬이 표 9 내지 표 18과 같이 정의되며 패리티 부분 행렬이 이중 대각 구조를 갖는 패리티 검사 행렬을 이용하여 LDPC 복호화를 수행할 수 있다.

BCH 디코더(1040)는 LDPC 디코더(1030)에서 출력되는 값들에 대해 BCH 복호화를 수행할 수 있다.

구체적으로, BCH 디코더(1040)는 송신 장치(700)의 BCH 인코더(710)에 대응되는 구성요소로, LDPC 디코더(1030)에서 출력되는 BCH 부호어에 대해 BCH 복호화를 수행하여 송신 장치(700)에서 전송한 비트들을 생성할 수 있다. 다만, 경우에 따라 송신 장치(700)에서 BCH 인코더(710)가 생략되는 경우, BCH 디코더(1040)는 생략될 수 있다.

한편, 수신 장치(1000)는 복호화 및 디인터리빙에 이용되는 각종 파라미터를 기저장하고 있을 수 있다. 여기에서, 복호화에 이용되는 파라미터는 BCH 부호의 부호율 및 부호어 길이, LDPC 부호의 부호율, 부호어 길이, 패리티 검사 행렬에 대한 정보가 될 수 있다. 그리고, 디인터리빙에 이용되는 파리미터는 디인터리빙 룰에 대한 정보가 될 수 있다. 여기에서, 패리티 검사 행렬에 대한 정보는 본 발명에서 제시하는 패리티 검사 행렬을 사용할 경우 정보어 부분 행렬은 각각 M 개의 열을 포함하는 복수의 열 그룹으로 구성되며, 매 M 번째 열에 존재하는 1의 값의 위치를 나타내는 테이블을 포함할 수 있다.

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

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

이 경우, 제어부(미도시)는 BCH 디코더(1040)로 BCH 부호의 부호율 및 부호어 길이 에 대한 정보를 제공하며, LDPC 디코더(1030)로 LDPC 부호의 부호율, 부호어 길이, 패리티 검사 행렬에 대한 정보를 제공할 수 있다. 또한, 제어부(미도시)는 디인터리버(1020)로 인터리빙 방식에 대한 정보를 제공할 수도 있다. 여기에서, 패리티 검사 행렬에 대한 정보는 본 발명에서 제시하는 패리티 검사 행렬을 사용할 경우 정보어 부분 행렬은 각각 M 개의 열을 포함하는 복수의 열 그룹으로 구성되며, 매 M 번째 열에 존재하는 1의 값의 위치를 나타내는 테이블을 포함할 수 있다.

도 11 및 도 12는 본 발명의 일 실시 예에 따른 LDPC 부호의 성능을 설명하기 위한 도면들이다.

도 11 은 본 발명의 일 실시 예에 따른 LDPC 부호의 BER 성능을 나타낸 그래프이다. 구체적으로, 각 곡선은 표 9 내지 표 18을 기반으로 LDPC 부호화하였을 때 Es/No대 BER 성능을 나타낸다.

도 12는 본 발명의 일 실시 예에 따른 LDPC 부호의 FER 성능을 나타낸 그래프이다. 구체적으로, 각 곡선은 표 9 내지 표 18을 기반으로 부호화 하였을 때 Es/No대 FER 성능을 나타낸다.

이와 같이, 본 발명의 일 실시 예에 따라 정의된 패리티 검사 행렬을 기반으로LDPC 부호화를 수행한 경우, BER/FER 성능이 우수함을 알 수 있다.

도 13은 본 발명의 일 실시 예에 따른 부호화 방법을 설명하기 위한 흐름도이다. 구체적으로, 도 13은 LDPC(Low Density Parity Check) 부호화를 수행하는 부호화 장치의 부호화 방법을 설명하기 위한 도면이다.

먼저, 패리티 검사 행렬에 기초하여 입력 비트들에 대해 LDPC 부호화를 수행하여 LDPC 부호어를 생성한다(S1310). 이때, LDPC 부호어는 64800 개의 비트로 구성될 수 있다. 즉, LDPC 부호어의 길이는 64800이 될 수 있다.

한편, 패리티 검사 행렬은 도 3에서 도시한 패리티 검사 행렬(300)과 동일한 형태일 수 있다.

여기에서, 정보어 부분 행렬은 각각 M 개의 열을 포함하는 복수의 열 그룹으로 구성되며, 매 M 번째 열에 존재하는 1 값의 위치를 나타내는 테이블로 정의될 수 있다. 여기에서, M은 정보어 부분 행렬에서 열의 패턴이 반복되는 간격으로, 360이 될 수 있다. 그리고, 패리티 부분 행렬은 이중 대각 형태일 수 있다.

이 경우, S1310 단계는 부호율에 따라 서로 다르게 정의된 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행할 수 있다.

예를 들어, 부호율이 6/15인 경우 표 9, 표 13 또는 표 17과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행하고, 부호율이 8/15인 경우 표 10, 표 14와 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행할 수 있다. 그리고, 부호율이 10/15인 경우 표 11, 표 15 또는 표 18과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행하고, 부호율이 12/15인 경우 표 12, 표 16과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 부호화를 수행할 수 있다.

도 14는 본 발명의 일 실시 예에 따른 복호화 방법을 설명하기 위한 흐름도이다. 구체적으로, 도 14는 LDPC(Low Density Parity Check) 복호화를 수행하는 복호화 장치의 복호화 방법을 설명하기 위한 도면이다.

먼저, 패리티 검사 행렬에 기초하여 LDPC 부호어에 대해LDPC 복호화를 수행한다(S1410). 여기에서, LDPC 부호어는 64800 개의 비트로 구성될 수 있다. 즉, LDPC 부호어의 길이는 64800이 될 수 있다.

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

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

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

이 경우, S1410 단계는 부호율 R 에 따라 서로 다르게 정의된 패리티 검사 행렬을 이용하여 LDPC 복호화를 수행할 수 있다.

예를 들어, 부호율이 6/15인 경우 표 9, 표 13 또는 표 17과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 복호화를 수행하고, 부호율이 8/15인 경우 표 10, 표 14와 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 복호화를 수행할 수 있다. 그리고, 부호율이 10/15인 경우 표 11, 표 15 또는 표 18과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 복호화를 수행하고, 부호율이 12/15인 경우 표 12, 표 16과 같은 테이블로 정의되는 패리티 검사 행렬을 이용하여 LDPC 복호화를 수행할 수 있다.

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

한편, 본 발명에 따른 부호화 방법 및 복호화 방법을 순차적으로 수행하는 프로그램이 저장된 비일시적 판독 가능 매체(non-transitory computer readable medium)가 제공될 수 있다.

비일시적 판독 가능 매체란 레지스터, 캐쉬, 메모리 등과 같이 짧은 순간 동안 데이터를 저장하는 매체가 아니라 반영구적으로 데이터를 저장하며, 기기에 의해 판독(reading)이 가능한 매체를 의미한다. 구체적으로는, 상술한 다양한 어플리케이션 또는 프로그램들은 CD, DVD, 하드 디스크, 블루레이 디스크, USB, 메모리카드, ROM 등과 같은 비일시적 판독 가능 매체에 저장되어 제공될 수 있다.

또한, 부호화 장치, 복호화 장치, 송신 장치 및 수신 장치에 대해 도시한 상술한 블록도에서는 버스(bus)를 미도시하였으나, 부호화 장치, 복호화 장치, 송신 장치 및 수신 장치에서 각 구성요소 간의 통신은 버스를 통해 이루어질 수도 있다. 또한, 각 장치에는 상술한 다양한 단계를 수행하는 CPU, 마이크로 프로세서 등과 같은 프로세서가 더 포함될 수도 있다.

또한, 이상에서는 본 발명의 바람직한 실시 예에 대하여 도시하고 설명하였지만, 본 발명은 상술한 특정의 실시 예에 한정되지 아니하며, 청구범위에서 청구하는 본 발명의 요지를 벗어남이 없이 당해 발명이 속하는 기술분야에서 통상의 지식을 가진자에 의해 다양한 변형실시가 가능한 것은 물론이고, 이러한 변형실시들은 본 발명의 기술적 사상이나 전망으로부터 개별적으로 이해되어져서는 안될 것이다.

600 : 부호화 장치 610 : LDPC 인코더

Claims

송신 장치에 있어서,
매트릭스에 기초하여 입력 비트들을 인코딩하여 패리티 비트들을 생성하는 인코더;
상기 입력 비트들 및 상기 패리티 비트들을 포함하는 코드워드를 인터리빙하는 인터리버;
상기 인터리빙된 코드워드의 비트들을 성상점들에 맵핑하는 맵퍼;
OFDM 방식을 이용하여 성상점들에 기초하여 신호를 생성하는 신호 생성부; 및
상기 생성된 신호를 전송하는 송신부;를 포함하며,
상기 매트릭스는, 6/15의 코드 레이트 및 64800의 코드 길이를 갖는 LDPC(Low Density Parity Check) 코드의 패리티 인덱스들에 기초하여 얻어지고,
상기 패리티 인덱스들은, 하기의 테이블과 같이 나타내어지는 송신 장치:
제1항에 있어서,
상기 매트릭스는, 시클릭 구조를 갖는 송신 장치.
제1항에 있어서,
상기 패리티 비트들은
패리티 비트들을 초기화하고, 상기 매트릭스에 기초하여 상기 입력 비트들을 상기 초기화된 패리티 비트들에 누적(accumulate)하고, 패리티 인덱스 x를 갖는 누적된 패리티 비트와 패리티 인덱스 x-1를 갖는 누적된 패리티 비트에 기초한 비트 오퍼레이션을 수행하여 패리티 인덱스 x를 갖는 패리티 비트들을 출력함에 의해 생성되고,
상기 x는, 0 보다 크고 패리티 비트들의 수보다 작은 값들 중 어느 하나인 송신 장치.
제3항에 있어서,
상기 매트릭스는, 하기와 같은 관계식에 기초하여 생성되는 q(i,j,l)에 의해 나타내어지고,
q(i,j,l) = q(i,j,0) + Q_ldpc × l (mod M_inner) for 0 < l < 360
여기에서, Q_ldpc는 상기 LDPC 코드의 코드 레이트 및 코드 길이에 의해 결정되는 코딩 파라미터이고, M_inner는 패리티 비트들의 수이고, q(i,j,0)는 상기 테이블의 i 번째 로우의 j 번째 엔트리에 의해 나타내어지는 패리티 인덱스이고, i는 상기 테이블의 로우의 인덱스이고, j는 상기 로우에서 엔트리의 인덱스를 나타낸다.
제4항에 있어서,
상기 입력 비트들은, 하기와 같은 관계식에 기초하여 상기 초기화된 패리티 비트들에 누적되고,
p_{q(i, w(i), l)} = p_{q(i, w(i), l)} + s_k,
여기에서, s_k는 상기 입력 비트들 중 k 번째 비트를 나타내고, p_{q(i, w(i), l)}는 상기 초기화된 패리티 비트들 중 q(i, w(i), l) 번째 비트들을 나타내고, k는 0 이상이고 상기 입력 비트들의 수보다 작은 값들 중 어느 하나이고,
, l=k (mod 360), w(i) = j이다.
삭제
삭제
삭제
삭제
삭제
삭제
삭제
삭제
삭제
삭제
삭제
삭제
삭제
삭제
삭제