KR100913876B1

KR100913876B1 - 저밀도 패리티 검사 부호의 생성 방법 및 장치

Info

Publication number: KR100913876B1
Application number: KR1020040100039A
Authority: KR
Inventors: 김상효; 김한주; 김민구; 구영모
Original assignee: 삼성전자주식회사
Priority date: 2004-12-01
Filing date: 2004-12-01
Publication date: 2009-08-26
Also published as: JP4168055B2; US20060156183A1; EP1667328A1; DE602005002815T2; CN1783730A; DE602005002815D1; CN100505556C; KR20060061145A; US7536623B2; AU2005239662A1; JP2006157926A; AU2005239662B2; EP1667328B1

Abstract

본 발명은 데이터의 부호화에 관한 것으로, 특히 저밀도 패리티 검사(LDPC) 부호의 생성 방법 및 장치에 관한 것이다. LDPC 부호의 생성 방법은, 길이 K의 정보 시퀀스를 길이 N의 부호어로 부호화하기 위해, 검사 노드들에 대한 (N-K)개의 행들과 변수 노드들에 대한 N개의 열들을 가지는 패리티 검사 행렬을 구성하는 과정과, 상기 패리티 검사 행렬을 K개의 열들을 가지는 정보 부분 행렬과 (N-K)개의 열들을 가지는 패리티 부분 행렬로 분할하는 과정과, 상기 패리티 부분 행렬을 P*P의 크기를 가지는 부블록들로 분할하는 과정과, 상기 패리티 부분 행렬의 제1 대각 부분과, 상기 제1 대각 부분으로부터 부블록 천이량 f만큼 천이된 제2 대각 부분을 결정하는 과정과, 상기 제1 대각 부분과 제2 대각 부분의 부블록들에 천이 인덱스들을 가지는 천이된 단위행렬들을 각각 배치하는 과정과, 상기 제1 및 제2 대각 부분들을 제외한 나머지 부블록들을 영행렬로 채우는 과정과, 상기 패리티 부분 행렬의 하나의 부블록 열에, 하나의 1만을 포함하고 나머지 원소들은 모두 0인 델타 행렬들을 배치하는 과정과, 상기 패리티 검사 행렬을 저장하는 과정을 포함한다.

LDPC codes, Parity Check Matrices, Identity matrix, delta matrix, degree, encoding

Description

저밀도 패리티 검사 부호의 생성 방법 및 장치{METHOD AND APPARATUS FOR GENERATING LOW DENSITY PARITY CHECK CODES}

도 1은 일반적인 (10, 5) LDPC 부호의 일 예를 나타내는 패리티 검사 행렬을 도시한 도면.

도 2는 상기 도 1에 도시한 LDPC 부호의 팩터 그래프를 도시한 도면.

도 3a와 도 3b는 LDPC 부호의 복호 동작을 나타낸 개념도.

도 4는 LDPC 코드의 효율적인 부호화를 위한 패리티 검사 행렬의 일 예.

도 5는 GDM LDPC 부호를 나타내는 블록 구조를 가지는 패리티 검사 행렬을 설명하는 도면.

도 6은 GDM LDPC 부호를 생성하기 위한 기저 패리티 검사 행렬의 패리티 부분 및 부호화 과정을 나타낸 도면.

도 7은 도 6과 같은 패리티 부분으로부터 확장되어 만들어진 블록 구조의 패리티 부분을 나타낸 도면.

도 8은 P=3이고, N-K=15인 GDM LDPC 부호의 패리티 검사 행렬 및 부호화 과정을 나타낸 도면.

도 9는 본 발명의 바람직한 실시예에 따른 패리티 검사 행렬의 패리티 부분 의 구조를 나타낸 도면.

도 10은 본 발명의 바람직한 실시예에서 제안하는 LDPC 부호의 예 및 부호화 방법을 도시한 도면.

도 11은 본 발명의 바람직한 실시예에 따라 LDPC 부호를 생성하는 장치를 나타낸 구조도.

도 12는 본 발명의 바람직한 실시예에 따른 LDPC 부호를 생성하는 절차를 나타낸 흐름도.

도 13은 본 발명의 바람직한 실시예에서 제안하는 LDPC 부호의 패리티 부분의 구현 예를 나타낸 도면.

도 14는 본 발명의 바람직한 실시예에 따른 패리티 검사 행렬에서 P=3인 경우의 예.

도 15는 블록 LDPC 부호를 복호화하는 복호화 장치의 내부 구조도.

본 발명은 데이터의 부호화에 관한 것으로, 특히 저밀도 패리티 검사(Low-Density Parity Check: 이하 LDPC라 칭함) 부호의 생성 방법 및 장치에 관한 것이다.

통상적으로 통신 시스템에서는 데이터의 전송 시, 전송되는 데이터를 부호화 하여 전송함으로써, 전송의 안정성은 높이며, 많은 재전송이 이루어지지 않도록 함으로써 전송 효율을 높이도록 하고 있다. 이러한 부호화 방법 중 이동통신 시스템에서는 컨벌루셔널 부호화 방법, 터보 부호화 등의 방법 등이 사용되고 있다. 상기한 방법들을 사용하는 경우 데이터 전송의 안정성 및 전송 효율을 증대시킬 수 있다는 장점 때문이다.

무선 통신 기술이 급속도로 발전함에 따라 매우 고속의 데이터들을 전송할 수 있는 무선 통신 시스템들이 등장하고 있다. 이러한 무선 통신 시스템에서 보다 더 고속의 데이터들을 전송할 수 있기를 원하고 있다. 따라서 현재 제공되고 있는 상기한 방법들의 부호화 방법보다 높은 효율을 얻을 수 있는 부호화 방법이 요구되고 있다.

이러한 요구에 발맞춰 새로운 대안으로 떠오르고 있는 부호화 방법으로 저밀도 패리티 검사(LDPC) 부호가 있다. LDPC 부호는 1960년대 초 Gallager에 의해 최초로 제안되었으며, 1990년대 이후 MacKay 등에 의해 재조명되었다. 상기 MacKay 등에 의해 재조명된 LDPC 부호는 합-곱(sum-product) 알고리즘을 이용한 복호방법에 기반하고 있다. 또한 LDPC 부호는 신뢰도 전파 복호(belief propagation decoding)를 사용함으로서 샤논(Shannon)의 용량 한계(capacity limit)에 근접하는 우수한 성능을 보일 부호로 관심을 모으기 시작하였다.

이후 Richardson과 Chung 등은 LDPC 부호를 구성하는 펙터 그래프(factor graph) 상에서 복호 과정에서 생성, 갱신되는 메시지들의 확률 분포(probability distribution)가 반복(iteration)에 따라 변화하는 것을 추적하는 밀도 진화(density evolution) 기법을 제안하였다. 상기 밀도 진화 기법을 이용하고 펙터 그래프 상에서 무한대의 반복을 가정하였을 때, 오류 확률(probability of error)이 "0"으로 수렴하게 할 수 있는 채널 파라미터(channel parameter)가 발명되었다. 즉, 펙터 그래프 상에서 채널 파라미터를 최대화할 수 있도록 가변 노드(variable node)들과 검사 노드(check node)들의 차수 분포(degree distribution)를 제안하였다. 그리고 이러한 경우가 사이클(cycle)이 존재하는 유한한 길이의 LDPC 부호에 대해서도 적용 가능함을 이론적으로 보였다. 이러한 밀도 진화 기법을 이용하면 불균일(irregular) LDPC 부호의 채널 용량이 이론적인 샤논 한계에 불과 0.0045dB까지 근접할 수 있다.

이러한 LDPC 부호는 차세대 이동 통신 시스템에서 터보 부호(turbo code)를 대체할 수 있는 강력한 대안으로 거론되고 있다. 이는 LDPC 부호가 갖고 있는 복호기 구현상의 병렬 구조(parallel structure)와 낮은 복잡도(low complexity), 그리고 성능상의 낮은 오류 마루(low error floor), 양호한 프레임 오류율(good frame error rate) 등의 요인 때문이다. 따라서 앞으로도 많은 연구가 진행되면 보다 우수한 특성들을 갖는 LDPC 부호들이 등장할 것으로 기대되고 있다.

그러나 종래의 LDPC 부호를 구현하는데 문제점은 터보 부호(turbo code)에 비해 부호화(encoding) 과정이 복잡하고, 짧은 프레임 크기(frame size)에서 터보 부호보다 우수한 성능을 낼 수 있는 최적화된 부호의 구조를 결정하기가 용이하지 않으며, 부호를 표현하는데 많은 메모리를 필요로 하다는 점이다. 따라서 부호의 표현을 쉽게 하면서, 프레임 길이에 유연성(flexibility)을 가지는 형태를 갖는 보다 효율적인 LDPC 부호에 대한 필요가 발생하게 되었다.

따라서 상기한 바와 같이 동작되는 종래 기술의 문제점을 해결하기 위하여 창안된 본 발명은 부호화 과정이 단순한 저밀도 패리티 검사 부호의 생성 방법 및 장치를 제공한다.

또한 본 발명은 부호화 과정이 단순하며, 블록 형태의 구조적인 저밀도 패리티 검사 부호의 생성 방법 및 장치를 제공한다.

본 발명에 따른 저밀도 패리티 검사 부호의 생성 방법은, 길이 K의 정보 시퀀스를 길이 N의 부호어로 부호화하기 위해, 검사 노드들에 대한 (N-K)개의 행들과 변수 노드들에 대한 N개의 열들을 가지는 패리티 검사 행렬을 구성하는 과정과, 상기 패리티 검사 행렬을 K개의 열들을 가지는 정보 부분 행렬과 (N-K)개의 열들을 가지는 패리티 부분 행렬로 분할하는 과정과, 상기 패리티 부분 행렬을 P*P의 크기를 가지는 부블록들로 분할하는 과정과, 여기서 P는 (N-K)의 약수이고, 상기 패리티 부분 행렬의 제1 대각 부분과, 상기 제1 대각 부분으로부터 부블록 천이량 f만큼 천이된 제2 대각 부분을 결정하는 과정과, 상기 제1 대각 부분과 제2 대각 부분의 부블록들에 천이 인덱스들을 가지는 천이된 단위행렬들을 각각 배치하는 과정과, 상기 제1 및 제2 대각 부분들을 제외한 나머지 부블록들을 영행렬로 채우는 과정과, 상기 패리티 부분 행렬의 하나의 부블록 열에, 하나의 1만을 포함하고 나머지 원소들은 모두 0인 홀수 개의 델타 행렬들을 배치하는 과정과, 상기 패리티 검사 행렬을 저장하는 과정을 포함한다.

또한 본 발명에 따른 저밀도 패리티 검사 부호의 생성 장치는, 저밀도 패리티 검사 부호를 정의하는 패리티 검사 행렬을 생성하는 프로그램 코드와 상기 생성된 패리티 검사 행렬을 저장하는 메모리 시스템과, 상기 프로그램 코드를 실행하여 상기 패리티 검사 행렬을 생성하는 프로세서로 구성되고, 상기 프로세서는, 길이 K의 정보 시퀀스를 길이 N의 부호어로 부호화하기 위해, 검사 노드들에 대한 (N-K)개의 행들과 변수 노드들에 대한 N개의 열들을 가지는 패리티 검사 행렬을 구성하는 과정과, 상기 패리티 검사 행렬을 K개의 열들을 가지는 정보 부분 행렬과 (N-K)개의 열들을 가지는 패리티 부분 행렬로 분할하는 과정과, 상기 패리티 부분 행렬을 P*P의 크기를 가지는 부블록들로 분할하는 과정과, 여기서 P는 (N-K)의 약수이고, 상기 패리티 부분 행렬의 제1 대각 부분과, 상기 제1 대각 부분으로부터 부블록 천이량 f만큼 천이된 제2 대각 부분을 결정하는 과정과, 상기 제1 대각 부분과 제2 대각 부분의 부블록들에 천이 인덱스들을 가지는 천이된 단위행렬들을 각각 배치하는 과정과, 상기 제1 및 제2 대각 부분들을 제외한 나머지 부블록들을 영행렬로 채우는 과정과, 상기 패리티 부분 행렬의 하나의 부블록 열에, 하나의 1만을 포함하고 나머지 원소들은 모두 0인 홀수 개의 델타 행렬들을 배치하는 과정과, 상기 패리티 검사 행렬을 저장하는 과정을 실행하는 것을 포함한다.

삭제

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

저밀도 패리티 검사(LDPC) 부호는 선형 블록 부호의 일종으로, 대부분의 원소들이 0의 값을 가지며 상기 0의 값을 가지는 원소들 이외의 극히 소수의 원소들이 1의 값을 가지는 패리티 검사 행렬(parity check matrix)에 의해 그 구조가 정의된다. 일 예로, K비트의 정보비트를 위한 (N, K) LDPC 부호는 블록 크기가 N인 선형 블록 부호(linear block code)로서, 1의 값을 가지는 원소들을 제외한 원소들은 모두 0의 값을 가지는 성긴(sparse) 구조의 (N-K)*N 패리티 검사 행렬에 의해 정의된다. 여기서 각 행 또는 각 열에 포함되는 1의 개수를 차수(degree)라 한다.

상기 패리티 검사 행렬 내 열들의 차수가 일정하며 행들의 차수가 일정한 LDPC 부호를 균일(regular) LDPC 부호라고 칭한다. 이와는 달리, 패리티 검사 행렬내 열들의 차수와 행들의 차수가 일정하지 않은 LDPC 부호를 불균일(irregular) LDPC 부호라고 칭한다. 일반적으로 균일 LDPC 부호의 성능에 비해서 불균일 LDPC 부호의 성능이 더 우수하다고 알려져 있다. 그러나 불균일 LDPC 부호의 경우 패리티 검사 행렬내 열들의 차수와 행들의 차수가 일정하지 않기 때문에 패리티 검사 행렬내 열들의 차수와 행들의 차수를 적절하게 조절해야지만 우수한 성능을 보장받을 수 있다.

길이 N인 부호어는 벡터 C로 표현되며, 정보 비트의 길이가 K일 때 2^K개 중 하나의 부호어를 나타내는 (N, K) 부호가 사용된다. (N, K) LDPC 부호는 (N-K)*N 패리티 검사 행렬 H를 갖게 되며, 하기 <수학식 1>이 만족된다.

도 1은 일반적인 (10, 5) LDPC 부호의 일 예를 나타내는 패리티 검사 행렬을 도시한 도면이다.

상기 도 1을 참조하면, LDPC 부호의 패리티 검사 행렬 H는 10개의 열들과 5 개의 행들로 구성되어 있으며, 열들의 차수는 2로 균일하고 행들의 차수는 4로 균일하다. 이렇게 열들의 차수와 행들의 차수가 균일하므로 상기 (10, 5) LDPC 부호는 균일 LDPC 부호가 된다.

도 2는 상기 도 1에 도시한 LDPC 부호의 팩터 그래프를 도시한 도면이다.

상기 도 2를 참조하면, 상기 LDPC 부호의 팩터 그래프는 10개의 변수 노드들(variable nodes)(20), 즉 V₁ 내지 V₁₀과, 5개의 검사 노드들(check nodes)(22)로 구성된다. 상기 LDPC 부호의 패리티 검사 행렬의 i번째 열과 j번째 행이 교차하는 지점에 1의 값을 가지는 원소가 존재할 경우 i번째 변수 노드 V_i와 j번째 검사 노드 C_i 사이에 브랜치(branch, 에지(edge)라고도 칭함)(24)가 형성된다.

상기에서 설명한 바와 같이 LDPC 부호의 패리티 검사 행렬은 매우 적은 값의 차수를 가지기 때문에, 비교적 긴 크기를 가지는 블록 부호에 대해서도 합-곱 알고리즘을 이용한 메시지 전달 반복 복호화가 가능하며, 블록 부호의 블록 크기를 계속 증가시켜 가면 터보 부호와 같이 샤논의 채널 용량 한계에 근접하는 형태의 성능을 나타낸다.

LDPC의 복호화는 펙터 그래프상의 변수 노드와 검사 노드들이 각 노드별로 생성 및 업데이트 한 메시지들을 서로 교환하는 과정을 반복하여 이루어진다. 이때, 각 노드에서는 합-곱 알고리즘을 이용하여 메시지들을 업데이트하게 된다. 이에 기초한 LDPC 부호의 반복복호 동작을 도 3a와 도 3b에 나타내었다.

도 3a를 참조하면, 검사노드(22a)는 연결된 변수 노드들(20b) 중 한 변수노드를 위한 검사노드 메시지(28)를, 연결된 나머지 변수노드들로부터 수신한 변수노드 값들을 합산하여 생성한다. 도 3b를 참조하면, 변수노드(20a)는 연결된 검사 노드들(22b) 중 한 검사 노드를 위한 검사노드 메시지(26)를, 연결된 나머지 검사노드들로부터 수신한 검사노드 값들을 곱하여 생성한다.

상기와 같이 합-곱 알고리즘을 적용할 때 검사노드 및 변수노드 메시지들은 변수 노드들과 검사 노드들을 연결하는 에지를 통하여 전달된다. 그러므로 패리티 검사 행렬의 1의 개수가 적을수록 전달해야 하는 메시지들의 개수가 줄어들며, 이는 복호기의 계산량 및 기억 공간을 줄이는 효과를 얻는다.

LDPC 부호의 효율적인 부호화를 위한 다양한 방법들이 연구되고 있다. 일반적으로 길이 K의 정보 시퀀스 C_I와 (N-K)*N 패리티 검사 행렬을 이용하여, (N-K)개의 패리티 비트들로 이루어진 패리티 시퀀스 C_P를 생성하는 방법들이 사용된다. 이때, 패리티 검사 행렬은 (N-K)*K 정보부분 행렬인 H_I와 (N-K)*(N-K) 패리티 부분 행렬인 H_P의 연접으로 하기 <수학식 2>과 같이 표현된다.

이때 C=[C_I : C_P]이며, C_I=[c₀, c₁, ... c _K-1], C_P=[p₀, p₁, ... p_N-K-1]이다.

패리티 검사 행렬의 정보 부분은 LDPC 부호의 사이클 특성 및 밀도 진화 특성을 고려하여 설계되는 것으로 본 발명의 주요한 요지와 관련이 없으므로, 본 명 세서에서는 더 이상 상세하게 언급하지 않을 것이다.

도 4는 LDPC 코드의 효율적인 부호화를 위한 패리티 검사 행렬의 일 예이다.

도 4를 참조하면, 패리티 검사 행렬(100)은 정보 부분(102)과 패리티 부분(104)으로 이루어진다. 도시한 바와 같이 정방 행렬인 패리티 부분(104)의 최초 행과 최초 열의 원소로부터 최종 행과 최종 열의 원소까지로 형성되는 첫 번째 대각 부분은 모두 1로 구성된다. 두 번째 대각 부분은 최초 행의 두 번째 열로부터 시작하는 모두 1인 원소들로 구성된다. 그러면 두 번째 대각 부분은 첫 번째 대각 부분으로부터 1만큼 순환 천이된 것으로 이해될 수 있다.

상기 패리티 검사 행렬(100)은 차수가 1인 열을 제거하면서 패리티 비트들을 순차적으로 생성할 수 있도록, 첫 번째 열(106)이 홀수 개의 1들을 포함하도록 구성되었다. 상기 패리티 부분(104)의 1로 표기된 원소들을 제외한 원소들은 모두 0이다.

상기 패리티 검사 행렬(100)의 모든 행을 원소 단위로 더하면, 모든 행을 더해서 만들어진 벡터 S=[S_I : S_P]와 부호어 벡터 C의 내적이 0이 되어야 하는 것은 앞서 언급한 <수학식 1>로부터 자명하다. 참고로 본 명세서 전반에 걸쳐서 더함이란 갈로아 필드(Galois Field) 덧셈을 의미한다. 패리티 부분(104)에서 첫 번째 패리티 비트를 제외한 나머지 패리티 비트들에 대응하는 변수 노드들은 항상 차수가 2이므로, S_P는 [1, 0, 0, ..., 0]과 같이 맨 첫 번째 비트를 제외하면 모두 0이 된다. 그러므로 <수학식 1>로부터 하기 <수학식 3>이 얻어지게 되어 첫 번째 패리티 비트 p₀이 계산된다.

패리티 검사 행렬(100)의 각 행을 하기 <수학식 4>라 할 때, 하기 <수학식 5>가 성립됨은 자명하다.

여기서 j는 0과 (N-K-1) 사이의 정수이다.

그러므로 하기 <수학식 6>으로부터 p₁이 구해지며, 이와 같이 순차적으로 패리티 비트들을 구할 수 있다.

먼저 모든 행에 대하여 h_j ^IC_I ^T를 구하고, 상기 구해진 값들을 누적해가면서 z+1번 패리티 비트를 구하는 방법은 다음과 같다. h_j ^P(z)를 h_j ^P의 z번째 요소라 하 고, H_P의 첫 번째 열인 벡터 g를 하기 <수학식 7>과 같이 나타낼 때, 하기 <수학식 8>이 구해진다.

도 4의 패리티 검사 행렬(100)에서 1로 표기된 각 원소들을 소정 크기 P를 가지는 단위행렬(Identity Matrix)로 치환하게 되면, 패리티 부분(104)을 P배의 크기를 가지는 패리티 부분으로 확장하는 것이 가능하다. 여기서 P는 (N-K)의 약수가 됨은 물론이다. 이러한 확장된 패리티 부분을 가지는 블록 타입 LDPC 부호는, 불규칙적으로 생성된 LDPC 부호에 비해 적은 메모리 용량으로 LDPC 부호를 표현할 수 있으며, 프레임 길이에 유연성을 가질 수 있고, 복호기의 구현이 비교적 간단한 장점이 있다. 블록 타입 LDPC 부호는 벡터 LDPC 부호, 블록 LDPC 부호, 혹은 GDM(Generalized Dual-diagonal) LDPC 부호 등으로 칭해진다.

GDM LDPC 부호의 패리티 검사 행렬은 배열 부호(Array codes)와 같이 P*P 단위행렬(Identity matrix) I의 각 행들을 s만큼 순환 천이한 행렬들을 부블록(subblock)으로 갖는다. 여기서 s는 천이 인덱스(shift index)이다.

하기에서는 도 5를 참조하여, 특히 GDM LDPC 부호를 나타내는 블록 구조를 가지는 패리티 검사 행렬을 설명한다. 여기에서는 (27, 15) GDM LDPC 부호의 일 예를 나타내었다.

도 5에서 n은 N/P이고 k는 K/P로 정의하면, 도시된 패리티 검사 행렬(110)의 경우 P=3, n=9, k=5이다. 패리티 검사 행렬(110)은 정보 부분(112)과 패리티 부분(114)으로 이루어지고 상기 패리티 부분(114)은 3*3 크기의 행렬들을 포함하는 부블록들로 분할된다. 따라서 상기 패리티 부분(114)은 4개의 부블록 행들(subblock rows)과 4개의 부블록 열들(subblock columns)을 갖는다. 도시하고 있지 않으나, 정보부분(112)은 영(zero)행렬이나 천이된(shifted) 단위행렬만으로 구성되며, 영행렬이 아닌(넌제로, non-zero) 부블록들의 위치 및 천이된 단위행렬들의 천이 인덱스 s는 부호의 밀도 진화 및 사이클 특성들을 고려하여 설계된다.

패리티 부분(114)의 최초 부블록 행(subblock row)과 최초 부블록 열(subblock column)의 부블록으로부터 최종 부블록 행과 최종 부블록 열의 부블록까지로 형성되는 첫 번째 대각 부분은 모두 천이된 단위행렬들로 구성된다. 단 패리티 부분(114)은 천이된 단위행렬에서 하나의 1을 천공한 하나의 블록(116)을 갖는다. 두 번째 대각 부분은 최초 부블록 행의 두 번째 부블록 열로부터 시작하는 부블록들로 구성되며, 마찬가지로 천이된 단위행렬들로 구성된다. 그러면 두 번째 대각 부분은 첫 번째 대각 부분으로부터 1만큼 천이된 것으로 이해될 수 있다. 패리티 부분(114)에서 비어있는 부블록들은 영행렬이다.

부블록들에 포함되는 행렬들은 단위행렬 I를 대각 방향으로 천이한 행렬, 즉 천이된 행렬로 표현될 수 있다. 하기 <수학식 9>에 천이된 단위행렬의 일 예를 나타내었다.

천이 인덱스 s에 따른 천이된 단위행렬

는 단위행렬을 s번 천이한 구조를 가지므로,

= I이다. 도 5에 나타낸 패리티 부분(114)의 대각 부분들 전체는

의 부블록들로 구성된다. 상기 천이된 단위행렬은 단위행렬의 각 열을 순환 이동(cyclic shift)한 순환 순열 행렬(cyclic permutation matrix)이 된다.

GDM LDPC 부호는 도 6과 같은 패리티 검사 행렬의 패리티 부분으로부터 확장되어 만들어진다. 도 6의 이진 행렬에서 직선으로 표시한 대각 부분들(30a, 30b, 32)은 모두 1이다. 도 6의 이중-대각 행렬은 두 번째 대각 부분(30a, 30b)을 첫 번째 대각 부분(32)으로부터 f만큼 천이(shift)시킨 구조이며, 두 번째 대각부분(30a)의 첫 번째 원소를 0으로 만들어 주면(즉 천공하면) p₀의 부호화가 가능해지고, 나머지 패리티 비트들은 도 4의 패리티 검사 행렬(100)과 유사한 방식으로 순차적으로 부호화된다. 상기 p₀으로부터 도시된 화살표들에 따라 순차적으로 모든 패리티 비트들이 부호화된다. 여기서 r=n-k=(N-K)/P이다.

도 7은 도 6과 같은 패리티 부분으로부터 확장되어 만들어진 블록 구조의 패리티 부분을 나타낸 것이다.

도 7을 참조하면, 도시된 패리티 부분은 첫 번째 및 두 번째 대각 부분들(40, 42a, 42b)에 배치된 천이된 단위행렬들

와 나머지 부블록들에 배치된 영행렬들로 이루어진다. 첫 번째 대각 부분(40)은 천이 인덱스들 0, 2, ... 2(r-f-1), 2(r-f), ... 2(r-1)를 가지는 천이된 단위행렬들로 이루어진다. 상기 첫 번째 대각 부분(40)으로부터 부블록 천이량 f만큼 천이된 두 번째 대각 부분(42a, 42b)은 천이 인덱스들 1, 3, ... 2(r-f-1)+1, ... 2(r-f)+1, ... 2(r-1)+1을 가지는 천이된 단위행렬들로 이루어진다. 상기 천이된 단위행렬들 각각은 P*P의 크기를 가지므로, 두 번째 대각 부분(42a)은 첫 번째 대각 부분(42)으로부터 P*f개의 열만큼 이격된다.

상기 패리티 부분에서, 두 번째 대각 부분(32)의 첫 번째 천이된 단위행렬

을 영행렬로 만드는 것이 아니라,

의 첫 번째 행의 1만 0으로 바꾸어주면, 전체 0이 아닌(Non-zero, 넌제로) 원소들을 순환하면서 모든 패리티 비트들이 부호화 될 수 있다.

다시 도 5를 참조하면, 패리티 부분(114)은 도 7에 도시한 패리티 부분에 부블록 천이량 f=3을 적용하여 구성된 것이다. 패리티 비트들의 치환(permutation)을 통해서 j₀=j₁=0 으로 하고 부블록(116)의

의 첫 번째 행만 모두 0으로 바꾼다 하더라도, 일반성을 잃지 않는다.

각 부블록의 천이 인덱스 j_i는 모든 패리티 비트들이 순차적으로 부호화 될 수 있도록 결정된다. 즉, 두 대각 부분에 해당되는 모든 천이 인덱스들을 더한 값을 P로 모듈로(modulo)한 값이, P와 서로 소가 되도록, 하기 <수학식 10>에 따라 상기 j_i가 결정된다.

여기서 gcd는 최대공약수(great common divisor)를 나타낸다.

도 8은 P=3이고, N-K=15인 GDM LDPC 부호의 패리티 검사 행렬을 나타낸 것이다. 도시한 패리티 검사 행렬(120)은 정보 부분(122)과 패리티 부분(124)으로 이루어지고, 패리티 부분(124)은 두 개의 대각 부분들을 제외한 나머지 부분들이 모두 영행렬로 채워진다. 첫 번째 대각 부분은 패리티 부분(124)의 최초 부블록 행과 최초 부블록 열의 부블록으로부터 최종 부블록 행과 최종 부블록 열의 부블록까지로 형성되며, 두 번째 대각 부분은 상기 첫 번째 대각 부분으로부터 2만큼 천이된다. 상기 두 대각 부분들의 부블록들은 천이된 단위행렬들로 채워진다.

여기서, 상기 패리티 부분(124)의 첫 번째 행/첫 번째 열의 원소(130)를 천공하면, 앞서 언급한 <수학식 5>로부터 최초로 부호화 되는 패리티 비트는 첫 번째 행의 7번째 원소(126)에 의해 얻어진다. 다음 패리티 비트들은 화살표를 따라서 부 호화가 진행되며, 첫 번째 열의 12번째 원소(128)에 의해 마지막 패리티 비트가 얻어진다.

그런데, 도 8과 같이 구성되는 GDM LDPC 부호는 차수가 1인 하나의 원소가 존재하게 된다. 차수가 1인 원소는 반복 복호의 영향을 충분히 받지 못하기 때문에 LDPC 부호의 성능 열화의 원인이 된다. 구체적으로 도 8의 경우, 원소(130)의 천공으로 인하여 원소(128)는 다른 행들의 영향을 받지 못하게 된다. 따라서 LDPC 부호에서 차수가 1인 부호 비트를 없앰으로써 성능 향상을 얻도록 하기 위한 방안을 설명하기로 한다.

도 9는 본 발명의 바람직한 실시예에 따른 패리티 검사 행렬의 패리티 부분의 구조를 나타낸 것이다. 여기서 상기 패리티 검사 행렬의 정보부분은 본 발명의 주요한 요지와는 관련이 없으므로 도시하지 않았다.

도 9를 참조하면, 패리티 부분은 대각 부분들(50, 50a, 50b)에 배치된 천이된 단위행렬들

와 나머지 부블록들에 배치된 영행렬들로 이루어진다. 여기서 j는 0과 2(r-1) 사이의 정수이고, r은 n-k를 의미한다. 첫 번째 대각 부분(50)은 짝수의 천이 인덱스들, 0, 2, ... 2(r-f-1), 2(r-f), ... 2(r-1)를 가지는 천이된 단위행렬들로 이루어진다. 상기 첫 번째 대각 부분(50)으로부터 부블록 천이량 f만큼 천이된 두 번째 대각 부분(52a, 52b)은 홀수의 천이 인덱스들, 1, 3, ... 2(r-f-1)+1, ... 2(r-f)+1, ... 2(r-1)+1을 가지는 천이된 단위행렬들로 이루어진다. 상기 천이된 단위행렬들의 천이 인덱스들은 LDPC 코드의 성능을 최대화하고 복호기 구조를 간단히 할 수 있도록 결정되나, 상기 천이 인덱스들의 결정은 본 발명의 주요한 요지와는 관련이 없으므로 상세한 설명을 생략할 것이다.

특히, 차수가 1인 열을 포함하는 부블록 열(54)에는 하나의 1만을 포함하는 행렬들(이하 델타 행렬,

라 칭함)가 삽입된다. 상기 델타 행렬들

은 천이된 단위행렬들과 마찬가지로 P*P의 크기를 가지며, 첫 번째 열의 i번째 비트만이 1인 행렬이다. 여기서 i는 0과 (P-1) 사이의 정수이며,

은 영행렬이다. 하기 <수학식 11>에 4*4

을 도시하였다.

패리티 부분의 크기는 (N-K)*(N-K)이고 n=N/P와 k=K/P를 고려하면, 상기 부블록 열(54)에는 (n-k-2)개의 델타 행렬들이 삽입된다. 여기서 영행렬이 아닌 델타 행렬들의 개수는 홀수 개다. 상기 부블록 열(54)에서 델타 행렬들이 삽입되는 위치는 임의로 정해질 수 있다.

도 9의 행렬의 모든 행을 더하면, 첫 번째 패리티 비트에 해당되는 원소만 1이고 나머지 원소들은 모두 0이 된다. 따라서 이미 설명한 바와 마찬가지로 순차적으로 패리티 비트들의 부호화가 가능해진다.

도 10은 본 발명의 바람직한 실시예에서 제안하는 LDPC 부호의 예 및 부호화 방법을 도시한 것이다. 기재된 숫자는 패리티 비트들의 부호화되는 순서를 의미한다.

도 10을 참조하면, 패리티 검사행렬 H(140)는 정보 부분 H_I(142)와 패리티 부분 H_P(144)로 구성되며,(H=[H_I : H_P]) 패리티 부분(144)은 2개의 대각 부분들(154a, 156a, 156b)을 포함한다. 패리티 부분(144)의 첫 번째 부블록 열(150)은 2개의 천이된 단위행렬들(154, 156)과 1개의 델타 행렬(152)을 포함한다.

앞서 언급한 바와 같이 패리티 검사 행렬 H(140)의 모든 행을 더한 벡터를 S=[S_I:S_P]라 한다. 그러면 HC^T=0으로부터 SC^T=p₀+S_IC_I ^T=0이 되는 것은 자명하여, p₀=S_IC_I ^T와 같이 원소(146)에 의해 p₀이 구해진다. 이후 h₀ ^IC_I ^T+p₀+p₁=0으로부터 p ₁이 부호화 되고, 도 10에 나타낸 화살표의 순서에 따라 모든 패리티 비트들이 부호화된다. 마지막 패리티 비트는 원소(148)에 의해 부호화된다. 다만, 델타 행렬이 존재하는 부블록(152)의 경우는 해당 부블록(152)의 1이 존재하는 열에 해당되는 패리티 비트를 부호화하기 위해 추가의 p₀이 고려된다. 즉 부호화 순서에 따라 배열된(ordering) 패리티 비트들을 p₀', p₁', ... p_(N-K-1)'이라 하고, h _t'는 p_t'의 순서에 맞게 재배열된(reordering) 행이라 할 때, 패리티 비트는 다음 <수학식 12>에 따라 부호화된다.

도 11은 본 발명의 바람직한 실시예에 따라 LDPC 부호를 생성하는 장치를 나타낸 것이다.

도시한 바와 같이, 컴퓨터 시스템(200)은 시스템 버스(230)를 통해 메모리 시스템(218)과 결합되는 프로세서(212)를 포함한다. 프로세서(212)는 메모리 시스템(218)으로부터 필요한 파라미터들을 읽어내어 LDPC 부호를 생성하고 상기 메모리 시스템(218)에 저장한다. 상기 LDPC 부호의 생성 동작을 실행하기 위하여, 프로세서(212)는 시스템 버스(230)를 통해 주 메모리(210)와 입력 장치(214) 및 출력 장치(216)에 연결될 수 있다.

사용자는 입력 장치(214)를 조작하여 시스템 버스(230)를 통해 프로세서(212)로 명령어 신호를 입력한다. 프로세서(212)는 상기 명령어 신호에 따른 동작을 수행하고 그 결과를 출력 장치(216)를 통해 사용자에게 표시한다. 상기 결과는 사용자의 요구에 따라 메모리 시스템(218)에 저장될 수 있다.

본 발명의 바람직한 실시예에 따른 LDPC 부호의 생성 동작은 알려진 컴퓨터 프로그램 코드의 형태로 메모리 시스템(218)에 저장되거나 하드웨어 로직으로 구현된다. 상기 LDPC 부호의 생성에 필요한 파라미터들 또는 상기 파라미터들을 계산하는데 필요한 프로그램 코드가 상기 메모리 시스템(218)에 저장된다. 프로세서(212)에 의해 생성된 LDPC 부호는 상기 메모리 시스템(218)에 부블록별로 저장된다.

도 12는 본 발명의 바람직한 실시예에 따른 LDPC 부호를 생성하는 절차를 나타낸 흐름도이다. 여기에서는 LDPC 부호를 정의하는 패리티 검사 행렬을 생성하는 절차를 도시하였다.

도 12를 참조하면, 과정(300)에서 길이 K의 정보 시퀀스를 길이 N의 부호어로 부호화하기 위해 검사 노드들에 대한 (N-K)개의 행들과 변수 노드들에 대한 N개의 열들을 가지는 패리티 검사 행렬이 구성된다. 과정(302)에서 상기 패리티 검사 행렬은 K개의 열들을 가지는 정보 부분 행렬과 (N-K)개의 열들을 가지는 패리티 부분 행렬로 분할된다. 과정(304)에서 상기 패리티 부분 행렬은 P*P의 크기를 가지는 부블록들로 분할된다. 상기 P는 (N-K)의 약수이며, 상기 패리티 부분 행렬은 (N-K)/P=(n-k)개의 부블록 행들과 부블록 열들을 가지게 된다.

과정(306)에서 상기 패리티 부분 행렬의 첫 번째 부블록 행/첫 번째 부블록 열로부터 마지막 부블록 행/마지막 부블록 행을 포함하는 제1 대각 부분과, 상기 제1 대각 부분으로부터 부블록 천이량 f만큼의 옵셋을 가지는 제2 대각 부분이 결정된다. 과정(308)에서 상기 제1 대각 부분과 제2 대각 부분의 부블록들에는 소정 천이 인덱스들 j_i를 가지는 천이된 단위행렬들이 각각 배치된다. 상기 부블록 천이량과 천이 인덱스들은 상기 패리티 검사 행렬의 부호화 성능을 최대화할 수 있도록 결정될 수 있다. 이때 일반적인 GDM LDPC 부호와는 달리 상기 제1 및 제2 대각 부분의 어느 원소도 0으로 천공되지 않는다.

과정(310)에서 상기 제1 및 제2 대각 부분들을 제외한 나머지 부블록들은 영 행렬로 채워진다. 그러면, 과정(312)에서 상기 패리티 부분 행렬에서 차수가 1인 열을 포함하는 부블록 열의 홀수개의 영행렬들을 델타 행렬들로 치환한다. 상기 델타 행렬들은 앞서 언급한 바와 같이 단지 하나의 1만을 포함하고 나머지 원소들은 모두 0인 행렬을 의미한다. 과정(314)에서 상기와 같이 생성된 패리티 검사 행렬이 메모리 시스템에 저장된다.

도 13은 본 발명의 바람직한 실시예에서 제안하는 LDPC 부호의 패리티 부분의 구현 예를 나타낸 것이다.

도 13을 참조하면, 패리티 부분 H_P에서 이중 대각 부분들은 모두 단위행렬 I이며, 첫 번째 부블록 열에서 2개의 부블록들은 델타행렬

와 천이된 단위행렬

이다. 상기 천이된 단위행렬

는 단위행렬 I를 s 만큼 천이한 구조이다. 이와 같이, 첫 번째 부블록 열에 델타 행렬

만을 삽입하여 차수가 1인 열를 없애면서 간단한 부호화가 가능하도록 하였다. 여기서 s는 부블록 크기인 P와 서로 소인 값이다. 이와 같은 LDPC 코드는 패리티 구조의 표현이 매우 단순해지며, 패리티 비트들의 부호화 또한 매우 규칙적으로 이루어진다.

s=1인 경우에 부호화 순서는 다음 <수학식 13>과 같다.

도 14는 본 발명의 바람직한 실시예에 따른 패리티 검사 행렬에서 P=3인 경우의 예이다.

도 14를 참조하면, 패리티 검사 행렬(160)은 정보 부분(162)과 패리티 부분(164)으로 이루어지며, 패리티 부분(164)의 이중 대각 부분들(170, 172a, 172b)에는 3*3 단위행렬들이 배치된다. 또한 첫 번째 부블록 열은 부블록(168)의 1만큼 천이된 단위행렬 이외에 하나의 1만을 포함하는 델타 행렬(166)을 포함한다.

이상에서 설명한 조직적 형태의 LDPC 부호는 천이된 단위행렬 형태의 부블록들 및 하나의 1만을 가지는 델타행렬 형태의 부블록들(델타블록들)을 갖는다. 메모리 시스템은 블록화된 LDPC 부호를 표현하기 위해서 각 검사 노드의 차수, 각 변수 노드의 차수, 각 행에서의 넌제로 행렬들의 위치, 그리고 각 넌제로 행렬들의 천이 인덱스들 s를 가진다. 상기 값들은 양의 정수로 표현된다. 본 발명의 바람직한 실시예에 따라 메모리 시스템은, 델타행렬을 포함하는 부블록들을 다른 부블록들과 구분하여 저장한다.

일 실시예로서 메모리 시스템은 영행렬이 아닌 각 부블록에 대해 델타행렬을 포함하는지 또는 천이된 단위행렬을 포함하는지를 나타내는 1비트의 부블록 정보를 관리한다. 천이된 단위행렬을 포함하는 부블록의 s는 상기 천이된 단위행렬의 천이 인덱스를 나타내며, 델타행렬을 포함하는 부블록의 s는 상기 델타행렬에 포함되는 1의 위치를 나타낸다.

다른 실시예로서, 메모리 시스템은 영행렬이 아닌 각 부블록에 대해 천이 인 덱스 s로 델타행렬인지의 여부를 표시한다. s는 0보다 크거나 같고 P보다 작으므로 s를 표현하는 데에는 b=[log₂P] 비트가 필요하다. 여기서 [ ]는 반올림(ceiling) 함수를 의미한다. 그러므로 메모리 시스템은 천이 인덱스 s에 대해 b보다 크거나 같은 비트 수를 할당하고, 델타블록들에 대해서는 P보다 크거나 같은 s 값들을 표시한다.

상기와 같이 저장된 패리티 검사 행렬은 LDPC 부호를 부호화하는 부호화 장치 및 복호화 장치로 제공된다. 부호화 장치는 입력되는 정보 시퀀스 C_I와 본 발명의 패리티 검사 행렬을 이용하여 앞서 언급한 <수학식 12>와 같이 패리티 시퀀스 C_P를 구하고, C_I와 C_P를 연접한 부호어 C를 생성한다. 상기 생성된 부호어는 변조기 및 RF(Radio Frequency) 유닛 등을 거쳐 수신측으로 전송된다.

다음으로 도 15를 참조하여 본 발명의 바람직한 실시예에 따른 패리티 검사 행렬을 사용하여 블록 타입 LDPC 부호를 복호화하는 복호화 장치 내부 구조에 대해서 설명하기로 한다.

상기 도 15를 참조하면, 상기 복호화 장치는 블록 제어기(block controller)(410)와, 변수 노드 파트(400)와, 가산기(415)와, 디인터리버(de-interleaver)(417)와, 인터리버(interleaver)(419)와, 제어기(421)와, 메모리(423)와, 가산기(425)와, 검사 노드 파트(450)와, 경판정기(429)로 구성된다. 상기 변수 노드 파트(400)는 변수 노드 프로세서(411)와, 스위치들(413,414)로 구성되고, 상기 검사 노드 파트(450)는 검사 노드 프로세서(427)로 구성된다. 상기 메모리(423)는 각 검사 노드의 차수, 각 변수 노드의 차수, 각 행에서의 넌제로 행렬들의 위치, 그리고 각 넌제로 행렬들의 천이 인덱스들 s를 이용하여 패리티 검사 행렬을 표현한다. 추가적으로 상기 메모리(423)는 영행렬이 아닌 각 부블록에 대해 델타행렬을 포함하는지 또는 천이된 단위행렬을 포함하는지를 나타내는 1비트의 부블록 정보를 더 가질 수 있다.

먼저, 무선 채널을 통해 수신되는 수신 신호는 상기 블록 제어기(410)로 입력된다. 상기 블록 제어기(410)는 상기 수신 신호의 블록 크기를 결정하며, 또한 상기 복호화 장치에 대응하는 부호화 장치에서 천공된 정보어 부분이 존재할 경우, 상기 천공된 정보어 부분에 0을 삽입하여 전체 블록 크기를 조정한 후 상기 변수 노드 프로세서(411)로 출력한다.

상기 변수 노드 프로세서(411)는 상기 블록 제어기(410)에서 출력한 신호를 입력받아 상기 신호의 확률값들을 계산하고, 상기 계산된 확률값들을 업데이트한 후 상기 스위치(413) 및 상기 스위치(414)로 출력한다. 여기서, 상기 변수 노드 프로세서(411)는 상기 복호화 장치에 미리 설정되어 있는 패리티 검사 행렬에 상응하게 변수 노드들과 변수 노드들을 연결하며, 상기 변수 노드들에 연결된 검사 노드들의 개수만큼의 입력값과 출력값을 갖는 업데이트 연산을 수행한다. 상기 변수 노드들 각각에 연결된 검사 노드들의 개수는 상기 패리티 검사 행렬을 구성하는 열들 각각의 웨이트, 즉 1의 개수와 동일하다. 따라서, 상기 패리티 검사 행렬을 구성하는 열들 각각의 웨이트에 따라 상기 변수 노드 프로세서(411)의 내부 연산이 수행된다. 상기 스위치(414)는 상기 스위치(413)가 스위칭 온되지 않을 경우에 스위칭 온되어 상기 변수 노드 프로세서(411)에서 출력하는 신호를 상기 가산기(415)로 전달한다.

상기 가산기(415)는 상기 변수 노드 프로세서(411)에서 출력한 신호와 이전 반복 복호화(iteration decoding) 사이클에서의 상기 인터리버(419)의 출력 신호를 입력하고, 상기 변수 노드 프로세서(411)에서 출력한 신호에서 상기 인터리버(419)의 출력 신호를 감산한 후 상기 디인터리버(417)로 출력한다. 여기서, 상기 복호화 과정이 최초의 복호화 과정일 경우, 상기 인터리버(419)의 출력 신호는 0으로 간주된다.

상기 디인터리버(417)는 상기 가산기(415)에서 출력한 신호를 입력받아 미리 설정되어 있는 설정 방식에 상응하게 디인터리빙(de-interleaving)한 후, 상기 가산기(425)와 상기 검사 노드 프로세서(427)로 출력한다. 여기서, 상기 디인터리버(417)의 내부 구조는 상기 패리티 검사 행렬에 상응하는 구조를 가지며, 그 이유는 상기 패리티 검사 행렬의 1의 값을 가지는 원소들의 위치에 따라 상기 디인터리버(417)에 대응하는 인터리버(419)의 동작이 상이해지기 때문이다.

상기 가산기(425)는 이전 반복 복호화 과정에서의 상기 검사 노드 프로세서(427)의 출력 신호와 상기 디인터리버(417)의 출력 신호를 입력받고, 상기 검사 노드 프로세서(427)의 출력 신호에서 상기 디인터리버(417)의 출력 신호를 감산한 후 상기 인터리버(419)로 출력한다. 상기 검사 노드 프로세서(427)는 상기 복호화 장치에 미리 설정되어 있는 패리티 검사 행렬에 상응하게 검사 노드들을 변수 노드들에 연결하며, 상기 검사 노드들에 연결된 변수 노드들의 개수에 따른 입력값과 출력값을 갖는 업데이트 연산이 수행된다. 상기 검사 노드들 각각에 연결된 변수 노드들의 개수는 상기 패리티 검사 행렬을 구성하는 행들 각각의 웨이트, 즉 차수와 동일하다. 따라서 상기 패리티 검사 행렬을 구성하는 행들 각각의 웨이트에 따라 상기 검사 노드 프로세서(427)의 내부 연산이 수행된다.

여기서, 상기 인터리버(419)는 상기 제어기(421)의 제어에 따라 미리 설정되어 있는 인터리빙 방식으로 상기 가산기(425)에서 출력한 신호를 인터리빙한 후 상기 가산기(415) 및 상기 변수 노드 프로세서(411)로 출력한다. 여기서, 상기 제어기(421)는 상기 메모리(423)에 저장되어 있는 인터리빙 방식에 관련된 정보를 읽어 상기 인터리버(419)의 인터리빙 방식을 제어하게 되는 것이다. 또한, 상기 복호화 과정이 최초의 복호화 과정일 경우에는 상기 디인터리버(417)의 출력 신호는 0이라고 간주해야함은 물론이다.

상기와 같은 과정들을 반복적으로 수행함으로써 복호화를 수행하며, 미리 설정한 설정 반복 회수에 해당하는 반복 복호화를 수행한 후 상기 스위치(414)는 상기 변수 노드 프로세서(411)와 가산기(415)간을 스위칭 오프(switching off)하고 상기 스위치(413)는 상기 변수 노드 프로세서(411)와 경판정기(429) 간을 스위칭 온한다. 그러면 상기 변수 노드 프로세서(411)에서 출력한 신호가 상기 경판정기(429)로 출력된다. 상기 경판정기(429)는 상기 변수 노드 프로세서(411)에서 출력한 신호를 입력받아 경판정한 후, 그 경판정 결과를 출력하게 된다. 상기 경판정기(429)의 출력값은 최종적으로 복호화된 비트들이 된다.

다른 경우, 상기 블록 제어기(410)로부터 제공된 신호에 대한 변수 노드 프로세싱과 검사 노드 프로세싱이 완료되면, 변수 노드 프로세서(411)에서 출력한 신 호가 스위치(413)에 의해 경판정기(429)로 전달된다. 상기 경판정기(429)에 의한 경판정 결과는 도시하지 않은 버퍼에 저장되고, 도시하지 않은 패리티 검사기는 상기 경판정 결과에 따른 패리티 검사를 수행한다. 여기서 상기 패리티 검사는 상기 제어기(421)에 의해 수행될 수도 있다. 상기 패리티 검사에 실패하면, 패리티 검사기는 제어기(421)로 반복 복호화가 필요함을 통지하게 되고, 상기 블록 제어기(410)로부터 제공된 신호에 대해 변수 노드 프로세싱과 검사 노드 프로세싱이 다시 수행된다. 상기 패리티 검사에 성공하면, 상기 버퍼에 저장된 경판정 결과는 복호 비트들로서 최종 출력된다.

한편 본 발명의 상세한 설명에서는 구체적인 실시예에 관해 설명하였으나, 본 발명의 범위에서 벗어나지 않는 한도 내에서 여러 가지 변형이 가능함은 물론이다. 그러므로 본 발명의 범위는 설명된 실시예에 국한되지 않으며, 후술되는 특허청구의 범위뿐만 아니라 이 특허청구의 범위와 균등한 것들에 의해 정해져야 한다.

이상에서 상세히 설명한 바와 같이 동작하는 본 발명에 있어서, 개시되는 발명중 대표적인 것에 의하여 얻어지는 효과를 간단히 설명하면 다음과 같다.

본 발명은, GDM LDPC 부호에서 차수가 1인 변수노드를 제거함으로써 모든 패리티 비트의 부호화시에 밀도 진화의 영향을 적용하여 부호화 성능의 향상을 기대할 수 있다. 또한 블록 구조를 유지하며 LDPC 부호를 표현하는데 필요한 메모리 용 량을 낭비하지 않으면서 효율적인 부호화가 가능한 효과가 있다.

Claims

저밀도 패리티 검사 부호의 생성 방법에 있어서,

길이 K의 정보 시퀀스를 길이 N의 부호어로 부호화하기 위해, 검사 노드들에 대한 (N-K)개의 행들과 변수 노드들에 대한 N개의 열들을 가지는 패리티 검사 행렬을 구성하는 과정과,

상기 패리티 검사 행렬을 K개의 열들을 가지는 정보 부분 행렬과 (N-K)개의 열들을 가지는 패리티 부분 행렬로 분할하는 과정과,

상기 패리티 부분 행렬을 P*P의 크기를 가지는 부블록들로 분할하는 과정과, 여기서 P는 (N-K)의 약수이고,

상기 패리티 부분 행렬의 제1 대각 부분과, 상기 제1 대각 부분으로부터 부블록 천이량 f만큼 천이된 제2 대각 부분을 결정하는 과정과,

상기 제1 대각 부분과 제2 대각 부분의 부블록들에 천이 인덱스들을 가지는 천이된 단위행렬들을 각각 배치하는 과정과,

상기 제1 및 제2 대각 부분들을 제외한 나머지 부블록들을 영행렬로 채우는 과정과,

상기 패리티 부분 행렬의 하나의 부블록 열에, 하나의 1만을 포함하고 나머지 원소들은 모두 0인 홀수 개의 델타 행렬들을 배치하는 과정과,

상기 패리티 검사 행렬을 저장하는 과정을 포함하는 것을 특징으로 하는 생성 방법.
제 1 항에 있어서, 상기 제1 대각 부분은,

첫 번째 부블록 행과 첫 번째 부블록 열로부터 마지막 부블록 행과 마지막 부블록 행의 부블록들로 구성되는 것을 특징으로 하는 생성 방법.
제 1 항에 있어서, 상기 천이 인덱스들은,

상기 제1 및 제2 대각 부분들의 모든 천이 인덱스들을 더한 값을 P로 모듈로한 값이 P와 서로 소가 되도록 결정되는 것을 특징으로 하는 생성 방법.
제 1 항에 있어서, 상기 델타 행렬들을 배치하는 과정과,

상기 패리티 부분 행렬에서 첫 번째 부블록 열의 하나의 영행렬을 델타 행렬로 치환하는 것을 특징으로 하는 생성 방법.
제 1 항에 있어서, 상기 델타 행렬들은,

첫 번째 열에 하나의 1을 포함하는 것을 특징으로 하는 생성 방법.
제 1 항에 있어서, 상기 저장하는 과정은,

각 검사 노드의 차수, 각 변수 노드의 차수, 각 행에서의 넌제로 행렬들의 위치, 각 넌제로 행렬들의 천이 인덱스들, 각 넌제로 행렬들이 상기 델타행렬인지의 여부를 나타내는 1비트의 부블록 정보를 저장하는 것을 특징으로 하는 생성 방법.
제 6 항에 있어서, 상기 델타행렬인 넌제로 행렬의 천이 인덱스는 상기 델타행렬에 포함되는 1의 위치를 나타냄을 특징으로 하는 생성 방법.
제 1 항에 있어서, 상기 저장하는 과정은,

각 검사 노드의 차수, 각 변수 노드의 차수, 각 행에서의 넌제로 행렬들의 위치, 각 넌제로 행렬들의 천이 인덱스들을 저장하며, 상기 넌제로 행렬들 중 델타행렬의 천이 인덱스는 상기 P보다 작거나 같은 값을 가지는 것을 특징으로 하는 생성 방법.
저밀도 패리티 검사 부호의 생성 장치에 있어서,

저밀도 패리티 검사 부호를 정의하는 패리티 검사 행렬을 생성하는 프로그램 코드와 상기 생성된 패리티 검사 행렬을 저장하는 메모리 시스템과,

상기 프로그램 코드를 실행하여 상기 패리티 검사 행렬을 생성하는 프로세서로 구성되고,

상기 프로세서는,

길이 K의 정보 시퀀스를 길이 N의 부호어로 부호화하기 위해, 검사 노드들에 대한 (N-K)개의 행들과 변수 노드들에 대한 N개의 열들을 가지는 패리티 검사 행렬을 구성하는 과정과,

상기 패리티 검사 행렬을 K개의 열들을 가지는 정보 부분 행렬과 (N-K)개의 열들을 가지는 패리티 부분 행렬로 분할하는 과정과,

상기 패리티 부분 행렬을 P*P의 크기를 가지는 부블록들로 분할하는 과정과, 여기서 P는 (N-K)의 약수이고,

상기 패리티 부분 행렬의 제1 대각 부분과, 상기 제1 대각 부분으로부터 부블록 천이량 f만큼 천이된 제2 대각 부분을 결정하는 과정과,

상기 제1 대각 부분과 제2 대각 부분의 부블록들에 천이 인덱스들을 가지는 천이된 단위행렬들을 각각 배치하는 과정과,

상기 제1 및 제2 대각 부분들을 제외한 나머지 부블록들을 영행렬로 채우는 과정과,

상기 패리티 부분 행렬의 하나의 부블록 열에, 하나의 1만을 포함하고 나머지 원소들은 모두 0인 홀수 개의 델타 행렬들을 배치하는 과정과,

상기 패리티 검사 행렬을 저장하는 과정을 실행하는 것을 특징으로 하는 생성 장치.
제 9 항에 있어서, 상기 제1 대각 부분은,

첫 번째 부블록 행과 첫 번째 부블록 열로부터 마지막 부블록 행과 마지막 부블록 행의 부블록들로 구성되는 것을 특징으로 하는 생성 장치.
제 9 항에 있어서, 상기 천이 인덱스들은,

상기 제1 및 제2 대각 부분들의 모든 천이 인덱스들을 더한 값을 P로 모듈로한 값이 P와 서로 소가 되도록 결정되는 것을 특징으로 하는 생성 장치.
제 9 항에 있어서, 상기 델타 행렬들을 배치하는 과정과,

상기 패리티 부분 행렬에서 첫 번째 부블록 열의 하나의 영행렬을 델타 행렬로 치환하는 것을 특징으로 하는 생성 장치.
제 9 항에 있어서, 상기 델타 행렬들은,

첫 번째 열에 하나의 1을 포함하는 것을 특징으로 하는 생성 장치.
제 9 항에 있어서, 상기 메모리 시스템은,

각 검사 노드의 차수, 각 변수 노드의 차수, 각 행에서의 넌제로 행렬들의 위치, 각 넌제로 행렬들의 천이 인덱스들, 각 넌제로 행렬들이 상기 델타행렬인지의 여부를 나타내는 1비트의 부블록 정보로서, 상기 패리티 검사 행렬을 표현하는 것을 특징으로 하는 생성 장치.
제 14 항에 있어서, 상기 델타행렬인 넌제로 행렬의 천이 인덱스는 상기 델타행렬에 포함되는 1의 위치를 나타냄을 특징으로 하는 생성 장치.
제 9 항에 있어서, 상기 메모리 시스템은,

각 검사 노드의 차수, 각 변수 노드의 차수, 각 행에서의 넌제로 행렬들의 위치, 각 넌제로 행렬들의 천이 인덱스들로서 상기 패리티 검사 행렬을 표현하며, 상기 넌제로 행렬들 중 델타행렬의 천이 인덱스는 상기 P보다 크거나 같은 값을 가지는 것을 특징으로 하는 생성 장치.
제 1 항에 있어서,

상기 패리티 검사 행렬은 차수가 1인 열이 존재하지 않도록 상기 부블록들 중 적어도 하나에 하나의 1을 포함하는 행렬을 포함하여 구성됨을 특징으로 하는 생성 방법.