KR100543154B1

KR100543154B1 - 저밀도 패리티 검사 코드 생성 방법 및 시스템

Info

Publication number: KR100543154B1
Application number: KR1020030039765A
Authority: KR
Inventors: 에로즈무스타파; 선펭-웬; 이린-난
Original assignee: 휴우즈 일렉트로닉스 코오포레이션
Priority date: 2002-07-26
Filing date: 2003-06-19
Publication date: 2006-01-20
Anticipated expiration: 2023-06-19
Also published as: DE60313832D1; DK1385270T3; EP1385270A2; JP2010050994A; ES2285049T3; JP2004064756A; CN1481130A; EP1385270B1; DE60313832T2; KR20040010116A; ATE362675T1; EP1385270A3; JP4422436B2

Abstract

구조화된 저밀도 패리티 검사(LDPC) 코드의 생성 방법이 제공된다. 이러한 LDPC 코드 구조는 패리티 검사 매트릭스의 일부분이 하부 삼각형이 되도록 제한함으로써, 코드 생성 매트릭스를 필요로 하지 않는 매우 간단한 부호화 방법을 가능하게 한다. 또한, 본 방법은 전송된 비트에 대한 LDPC 코드의 비균등한 에러 보호 능력을 적극 이용하여, 고차 변조 집합(예컨대, 8-PSK(Phase Shift Keying))의 더욱 취약한 비트에 대한 추가의 에러 보호를 제공한다. 또한, 비트 노드와 검사 노드 양자를 그룹으로 분할하고 있는 효과적인 복호화 방식이 제안된다. 각 그룹과 관련된 에지 값들은 비트 노드 그룹 및 검사 노드 그룹별로 동시에 메모리 내에 함께 기억된다. 이러한 구조로 인해, 다중의 에지들이 메모리로부터 1 클록 주기 내에 인출(fetch)될 수 있다. 일군의 비트 노드 또는 검사 노드에 대한 모든 인접 에지가 수 클록 주기 내에 인출될 수 있는 패리티 매트릭스의 설계 방법이 제안된다. 전술한 방법은 구체적으로 고속 데이터 레이트를 요하는 대역폭 제한 통신 시스템에 적용될 수 있다.

대역폭 제한 통신, 저밀도 패리티 검사(LDPC), 고차원 변조 방식, 희소 패리티 검사 매트릭스, LDPC 복호기

Description

저밀도 패리티 검사 코드 생성 방법 및 시스템{METHOD AND SYSTEM FOR GENERATING LOW DENSITY PARITY CHECK CODES}

도 1은 본 발명의 실시예에 따른, 저밀도 패리티 검사(Low Density Parity Check; LDPC) 코드를 사용하도록 구성된 통신 시스템을 나타내는 도면.

도 2는 도 1의 시스템에서의 예시적인 송신기를 나타내는 도면.

도 3은 도 1의 시스템에서의 예시적인 수신기를 나타내는 도면.

도 4는 본 발명의 실시예에 따른, 희소 패리티 검사 매트릭스(sparse parity check matrix)의 설명도.

도 5는 도 4의 매트릭스의 LDPC 코드의 이분 그래프를 나타내는 도면.

도 6은 본 발명의 실시예에 따른, 희소 패리티 검사 매트릭스의 서브 매트릭스(sub-matrix)의 설명도이며, 여기에서 서브 매트릭스는 하부 삼각형 부분에 한정된 패리티 검사 값을 포함하는 도면.

도 7은 도 6에서와 같은 서브 매트릭스를 가지는 비제한적인 패리티 검사 매트릭스(H matrix)를 사용하는 코드와 제한적인 H 매트릭스를 사용하는 코드 간의 성능을 나타내는 그래프.

도 8a와 도 8b는, 각각, 도 1의 시스템에서 사용될 수 있는, 비 그레이 8-PSK 변조 방식(non Grey 8-PSK modulation scheme)과 그레이 8-PSK 변조 방식(Grey 8-PSK modulation scheme)의 설명도.

도 9는 그레이 레이블링(Gray labeling)을 사용하는 코드와 비 그레이 레이블링(non-Gray labeling)을 사용하는 코드 간의 성능을 나타내는 그래프.

도 10은, 본 발명의 실시예에 따른, 비 그레이 매핑을 사용하는 LDPC 복호기의 동작 흐름도.

도 11은, 본 발명의 실시예에 따른, 그레이 매핑을 사용하는 도 3의 LDPC 복호기의 동작의 흐름도.

도 12a-도 12c는, 본 발명에 따른, 검사 노드(check node)와 비트 노드(bit node) 간의 상호 작용의 설명도.

도 13a-도 13c는 본 발명의 여러 실시예에 따라서 생성된 LDPC의 시뮬레이션 결과를 나타내는 그래프.

도 14a와 도 14b는 각각, 본 발명의 실시예에 따라서, LDPC 코딩에서 무작위성을 구현할 수 있도록 하는 구조적인 접근을 지원하기 위하여 구성된 메모리의 상단 에지(top edge)와 하단 에지(bottom edge)의 설명도.

도 15는 본 발명의 실시예에 따라서, 부호화와 복호화를 수행할 수 있는 컴퓨터 시스템의 설명도.

<도면의 주요 부분에 대한 부호의 설명>

101, 200 : 송신기

103 : 채널

105, 300 : 수신기

201 : 소스

203 : LDPC 부호기

205 : 변조기

207, 303 : 안테나

301 : 복조기

305 : LDPC 복호기

307 : 비트 매트릭스 생성기

1500 : 컴퓨터 시스템

1501 : 버스

1503 : 프로세서

1505 : 주 메모리

1507 : ROM

1509 : 저장 장치

1511 : 디스플레이

1513 : 입력 장치

1517 : 통신 인터페이스

1519 : 네트워크 링크

<관련 출원에 대한 기재>

본 출원은 하기의 미국 가출원들에 대해 35 USC §119(e)에 따라서 이전 출원일에 대한 우선권을 주장한다. 즉, 본 출원은 미국 가출원 번호 60/398,760(2002.7.26 출원)(관리 번호: PD-202101)의 "Code Design and Implementation Improvements for Low Density Parity Check Codes"; 미국 가출원 번호 60/403,812(2002.8.15 출원)(관리 번호: PD-202105)의 "Power and Bandwithd Efficient Modulation and Coding Scheme for Direct Broadcast Satellite and Broadcast Satellite Communications"; 미국 가출원 번호 60/421,505(2002.10.25 출원)(관리 번호: PD-202101)의 "Method and System for Generating Low Density Parity Check Codes"; 미국 가출원 번호 60/421,999(2002.10.29 출원)(관리 번호: PD-202105)의 "Satellite Communication System Utilizing Low Density Parity Check Codes"; 및 미국 가출원 번호 60/423,710(2002.11.4 출원)(관리 번호: PD-202101)의 "Code Design and Implementation Improvements for Low Density Parity Check Codes"와 관련된다.

본 출원은 통신 시스템에 관한 것으로, 구체적으로는 코딩된 시스템에 관한 것이다.

통신 시스템은 잡음이 많은 통신 채널에서의 신뢰성있는 통신을 보장하기 위하여 부호화를 채용하고 있다. 이들 통신 채널은 이론적 상한(섀넌 한계(Shannon limit))을 규정하고 있는, 소정의 신호 대 잡음비(SNR)에서의 심볼당 비트수로서 표현될 수 있는 고정된 용량을 갖는다. 그 결과, 코딩의 설계에 있어서, 이 섀넌 한계에 근접하는 속도를 달성하는 것을 목표로 하고 있다. 이 섀넌 한계에 근접하고 있는 코드로는 저밀도 패리티 검사(LDPC) 코드가 있다.

종래, LDPC 코드는 단점이 많기 때문에 널리 사용되지 못했다. 그 단점의 하나로는 LDPC 부호화 기술이 매우 복잡하다는 것이다. 생성 매트릭스를 사용하여 LDPC 코드를 부호화하는 데에는 대규모의 비희소 매트릭스(non-sparse matrix)를 저장할 필요가 있다. 또한, LDPC 코드는 유효한 다수의 블록을 필요로 하며, 따라서 LDPC 코드의 패리티 검사 매트릭스가 희소하다고 하더라도, 이들 매트릭스를 저장하는 데에는 문제가 따른다. 구현의 관점에서, 용량은 LDPC 코드가 실제로 널리 이용되지 못한 중요한 원인이다. LDPC 코드의 구현에 있어서 주요한 과제는, 복호기 내의 수개의 프로세싱 엔진(노드)들 사이의 접속 네트워크를 어떻게 달성할 것인가였다.

따라서, 간단한 부호화 및 복호화 프로세스를 채용한 LDPC 통신 시스템이 필요하게 되었다. 또한, 큰 복잡성을 야기하지 않으면서, LDPC 코드를 사용하여 고속 데이터 레이트를 효과적으로 지원할 필요가 있다. 또한, LDPC 코딩의 구현에 있어서 용량 요건을 최소화할 필요가 있다. 또한, LDPC 복호기 내의 프로세싱 노드들 사이의 통신을 단순화시킨 방식이 필요하다.

전술한 과제들은 구조화된 저밀도 패리티 검사(LDPC) 코드를 생성하는 방법을 제공하고 있는 본 발명에 의해 달성된다. 이러한 LDPC 코드 구조는 패리티 검사 매트릭스의 일부분을 삼각형의 하부가 되도록 제한하며, 또한/또는 복호기의 프로세싱 노드들 사이의 통신이 매우 간단하게 되도록 다른 요건을 만족시키도록 함으로써 제공된다. 또한, 이 방법에서는 전송된 비트에 대한 LDPC 코드의 비균등한 에러 보호 능력을 적극 이용하여, 고차 변조 집합(예컨대, 8-PSK(Phase Shift Keying))의 더욱 취약한 비트에 대한 추가의 에러 보호를 제공한다. 또한, 패리티 검사 매트릭스는 미리 기억된 상수와 비트당 연산을 이용하는 알고리즘에 의해 생성될 수 있다.

본 발명의 실시예의 일 태양에 따르면, 저밀도 패리티 검사(LDPC) 코드의 생성 방법이 제공된다. 이 방법은, 수신된 입력 메시지를, LDPC 코드의 생성 매트릭스를 이용하지 않고, LDPC 코드의 패리티 검사 매트릭스만을 이용하여, LDPC 코드워드로 변환하는 단계와; 이 LDPC 코드워드를 출력하는 단계를 포함한다.

본 발명의 실시예의 또 다른 일 태양에 따르면, 선형 블록 코드의 부호화를 지원하는 방법이 제공된다. 이 방법은, 고차 신호 집합 비트를 선형 블록 코드에 대응하는 패리티 검사 매트릭스의 비트 노드에 매핑하는 단계를 포함한다. 그 신호 집합의 취약한 비트들은 적어도 3개의 에지를 갖는 비트 노드에 매핑된다.

본 발명의 실시예의 또 다른 일 태양에 따르면, 선형 블록 코드의 부호화를 지원하는 방법이 제공된다. 이 방법은, 고차 신호 집합 비트를 선형 블록 코드에 대응하는 패리티 검사 매트릭스의 비트 노드에 매핑하는 단계를 포함한다. 그 신호 집합의 취약한 비트들은 더 신뢰할 수 있는 비트의 수보다 많은 수의 에지를 갖 는 비트 노드에 매핑된다.

본 발명의 실시예의 또 다른 일 태양에 따르면, 저밀도 패리티 검사(LDPC) 코드의 생성 방법이 제공된다. 이 방법은, 수신된 입력 메시지를, LDPC 코드의 생성 매트릭스를 이용하지 않고, LDPC 코드의 패리티 검사 매트릭스만을 이용하여, LDPC 코드워드로 변환하는 단계를 포함한다. 이 방법은, 또한 LDPC 코드워드에 외부(outer) 코드를 부가하는 단계와; 부가된 외부 코드와 함께 LDPC 코드워드를 출력하는 단계를 포함한다.

본 발명의 실시예의 또 다른 일 태양에 따르면, 저밀도 패리티 검사(LDPC) 코드의 생성 방법이 제공된다. 이 방법은, 서로 인접하는 일군의 비트 노드에 대한 에지의 콘텐츠를 메모리에 기억시키는 단계를 포함한다. 이 방법은, 또한 서로 인접하는 일군의 검사 노드에 대한 에지의 콘텐츠를 동시에 메모리에 기억시키는 단계를 포함한다.

본 발명의 실시예의 또 다른 일 태양에 따르면, 저밀도 패리티 검사(LDPC) 코드를 생성하기 위한 시스템이 제공된다. 이 시스템은, 수신된 입력 메시지를, LDPC 코드의 생성 매트릭스를 이용하지 않고, LDPC 코드의 패리티 검사 매트릭스만을 이용하여, LDPC 코드워드로 변환하는 수단을 포함한다. 이 시스템은, 또한 LDPC 코드워드를 출력하는 수단을 구비한다.

본 발명의 실시예의 또 다른 일 태양에 따르면, 저밀도 패리티 검사(LDPC) 코드의 프로세싱 방법이 제공된다. 이 방법은, 수신된 LDPC 코드를 LDPC 복호기를 경유하여 복호화하는 단계를 포함한다. 이 방법은, 또한 매회 또는 수회의 LDPC 복호기의 반복 연산 후에, 신호 집합 비트 매트릭스를 LDPC 복호기에 반복적으로 재생성하는 단계를 포함한다.

본 발명의 다른 태양, 특징 및 장점들은, 본 발명의 최적의 실시예를 포함하여, 다수의 특정 실시예 및 구현예를 예시하고 있는, 하기의 상세한 설명을 통해 쉽게 알 수 있게 될 것이다. 또한, 본 발명의 사상 및 범주를 일탈하지 않는 범위 내에서, 그 일부 상세를 변형함으로써, 각종의 다른 실시예들이 가능하다. 따라서, 첨부된 도면 및 상세한 설명은 예시를 위한 것일 뿐, 이것에 국한되는 것으로 이해되어서는 안된다. 또한, 첨부 도면과 명세서 전반에 걸쳐 동일한 참조 부호를 사용하여 유사한 부분을 나타내고 있다.

<실시예>

구조화된 저밀도 패리티 검사(LDPC) 코드를 효율적으로 생성하는 시스템, 방법, 그리고 소프트웨어가 설명된다. 아래의 설명에서, 설명을 위한 목적으로, 본 발명에 대한 깊은 이해를 제공하기 위하여 많은 특정한 세부 사항들이 설명된다. 하지만, 당업자에게는 본 발명이 이러한 특정 세부 사항들 없이 또는 균등한 구성으로 실시될 수 있다는 것은 명백하다. 다른 예에서는, 본 발명을 필요 없이 애매하게 나타내는 것을 피하기 위하여 잘 알려진 구조와 장치들을 블록 선도 형식으로 나타낸다.

도 1은 본 발명의 실시예에 따른 저밀도 패리티 검사(LDPC) 코드를 사용하도록 구성된 통신 시스템의 설명도이다. 디지털 통신 시스템(100)은 통신 채널(103)을 통하여 수신기(105)에 전해지는 신호를 생성하는 송신기(101)를 포함한다. 이 이산 통신 시스템(discrete communication system)(100)에서, 송신기(101)는 가능한 메시지의 이산 집합을 생성하는 메시지 소스를 가지고 있으며, 각각의 가능한 메시지는 그에 상응하는 신호 파형(signal waveform)이 있다. 이들 신호 파형은 통신 채널(103)에 의하여 감쇄되거나, 또는 변경된다. 이 잡음 채널(103)을 극복하기 위해서, LDPC 코드가 사용된다.

송신기(101)에 의하여 생성된 LDPC 코드는 성능의 손실없이 고속 구현을 가능하게 한다. 송신기(101)의 출력인 이들 구조화된 LDPC 코드는 적은 수의 검사 노드(check node)를 이미 변조 방식(예를 들어 8-PSK)에 의하여 채널 오류에 취약한 비트 노드(bit node)로의 할당을 피한다.

이런 LDPC 코드는 (터보 코드(turbo code)와는 다른) 병렬화 할 수 있는 복호(decoding) 알고리즘(algorithm)을 가지고 있으며, 이것은 유리하게 더하기, 비교, 표 검사(table look-up) 등의 간단한 동작을 포함한다. 또한, 주의 깊게 설계된 LDPC 코드는 오류 층(error floor)의 어떤 조짐(sign)도 나타내지 않는다.

본 발명의 실시예에 따르면, 송신기(101)는, 비교적 간단한 부호화 기술을 이용하여, (복호화하는 도중에 효율적 메모리 접근을 용이하게 하는) 패리티 검사 매트릭스(parity check matrix)에 근거하여 수신기(105)와 통신하기 위하여 LDPC 코드를 생성한다. 송신기(101)는, 블록 길이가 충분히 크다면, 연결된 터보+RS(Reed Solomon) 코드의 성능을 능가할 수 있는 LDPC 코드를 사용한다.

도 2는 도 1의 시스템에서의 대표적인 송신기의 설명도이다. 송신기(200)는 정보 소스(201)로부터 입력을 받고 수신기(105)에서 오류 정정 처리에 적합한 높은 중복성의 코드화된 스트림(stream)을 출력하는 LDPC 부호기(203)를 갖추고 있다. 정보 소스(201)는 이산 알파벳, X에서 k 신호를 생성한다. LDPC 코드는 패리티 검사 매트릭스로 지정되어있다. 한편으로, LDPC 코드를 부호화하는 것은, 일반적으로, 생성 매트릭스를 지정하는 것을 요구한다. 비록 가우시안(Gaussian) 제거를 사용하여 패리티 검사 매트릭스에서 생성 매트릭스를 얻는 것이 가능하더라도, 결과로서 나온 매트릭스는 더 이상 희소(sparse)가 아니며 큰 생성 매트릭스를 저장하는 것은 매우 복잡할 수 있다.

부호기(203)는 패리티 검사 매트릭스에 구조를 부과함으로써 오직 패리티 검사 매트릭스를 사용하는 간단한 부호화 기술을 사용하여 알파벳 Y에서 변조기(205)로 신호를 생성한다. 특히, 매트릭스의 어떤 부분이 삼각형이 되야 한다는 제한을 둠으로써 패리티 검사 매트릭스에 제한이 주어진다. 이러한 패리티 검사 매트릭스의 구조는 아래의 도 6에서 더 자세히 설명된다. 이러한 제한은 무시할 수 있는 정도의 성능 손실을 가져오며, 그러므로, 매력적인 트래이드오프(trade off)가 될 수 있다.

변조기(205)는 부호기(203)에서의 부호화된 메시지를 전송 안테나(207)에 전송이 되는 신호 파형으로 매핑(map)하며, 이들 파형은 통신 채널(103)을 통해 방출된다. 따라서, 부호화된 메시지는 변조되며 전송 안테나(207)로 분배된다. 전송 안테나(207)에서의 전송은, 아래에 설명한 것 같이, 수신기로 전파된다.

도 3은 도 1의 시스템에서의 대표적인 수신기의 설명도이다. 수신하는 쪽에서는, 수신기(300)는 송신기(200)에서 수신된 신호의 복조를 수행하는 복조기(301) 를 포함한다. 이들 신호들은 복조를 위하여 수신 안테나(303)에서 수신된다. 복조 후, 수신된 신호는, 비트 매트릭스 생성기(307)와 연결하여, 메시지 X'를 생성함으로써 원래 소스 메시지를 재구성하는 것을 시도하는, 복호기(305)로 전달된다. 비 그레이 매핑(non Grey mapping)을 사용한 경우, 비트 매트릭스 생성기(307)는, 도 10에 자세히 나타낸 바와 같이, 복호화 처리 도중에 반복적으로 복호기(305)와 확률 정보를 교환한다. 이와 달리, 만약 그레이 매핑(Grey mapping)이 (본 발명의 한 실시예에 따라서) 사용된 경우, 비트 매트릭스 생성기의 전달이 한번이면 충분하며, 여기서 각 LDPC 복호기 반복 이후 비트 매트릭스 생성 시도는 제한된 성능 향상을 가져올 수 있다. 이 방법은 도 11과 관련하여 더 자세히 설명된다. 본 발명에 의하여 제공된 장점을 인식하기 위해서는, 도 4에서 설명한 바와 같이 LDPC 코드가 생성되는 방법을 실험하는 것이 도움이 된다.

도 4는, 본 발명의 한 실시예에 따른, 희소 패리티 검사 매트릭스의 설명도이다. LDPC 코드는 희소 패리티 검사 매트릭스 H _(n-k)xn 을 가지는 긴, 선형 블록 코드이다. 일반적으로 블록 길이, n, 은 수천에서 수만 비트까지 될 수 있다. 예를 들어, 길이 n = 8 그리고 비 1/2인 LDPC 코드를 위한 패리티 검사 매트릭스가 도 4에 나타나 있다. 같은 코드는 도 5와 같이 이분 그래프로 동등하게 나타날 수 있다.

도 5는 도 4의 매트릭스의 LDPC의 이분 그래프(bipartite graph)의 설명도이다. 패리티 검사 방정식은 각 검사 노드에서, 모든 접하는 비트 노드의 합(GF(Galois Field)(2)에서)이 0임을 암시한다. 도면에서 나타낸 바와 같이, 비트 노드는 그래프의 왼쪽에 위치하며, 미리 정해진 관계에 따라, 하나 또는 그 이상의 검사 노트와 연결되어 있다. 예를 들어, m1에 상응하여, 비트 노드에 관련하여 n ₁ + n ₄ + n ₅ + n ₈ = 0과 같은 방정식이 존재한다.

수신기(303)로 돌아가서, LDPC 복호기(305)는 메시지 전달 복호기로 간주되며, 여기서 복호기(305)는 비트 노드들의 값을 찾는 것을 목표로 한다. 이 작업을 완수하기 위해서, 비트 노드와 검사 노드는 반복적으로 서로와 통신한다. 이 통신의 본질이 아래에 설명된다.

검사 노드에서 비트 노드까지, 각 검사 노드는 인접하는 비트 노드에게 다른 인접하는 비트 노드에게서 오는 정보를 근거로 그 비트 노트의 값에 관한 추정(의견)을 제공한다. 예를 들어, 위의 예에서 만약 n4, n5 그리고 n8의 합이 m1에게 0처럼 보인다면, m1은 n1에게 n1의 값이 0일거라고 알려준다(n1 + n4 + n5 + n8 = 0이므로); 그렇지 않다면, m1은 n1에게 n1의 값이 1일거라고 알려준다. 거기에 더하여, 소프트(soft) 결정 복호화를 위하여, 안정성 측정(reliability measure)이 추가된다.

비트 노드에서 검사 노드까지, 각 비트 노드는 다른 인접 검사 노드로부터 오는 피드백(feedback)에 근거하여 자기 자신의 값에 관한 추정을 인접 검사 노드에 전달한다. 위의 예에서, n1은 오직 m1 과 m3 두개의 인접 검사 노드가 있다. 만약 m3에서 n1로 오는 피드백이 n1의 값이 아마 0이라고 지시한다면, n1은 m1에게 n1의 값이 0일거라는 추정을 알려준다. 비트 노드가 두개 이상의 검사 노드를 가진 경우에는, 비트 노드는 통신하는 검사 노드에게 결정을 보고하기 전에 다른 인접 검사 노드로부터 오는 피드백에 의한 다수결 표결(소프트 결정)을 수행한다. 위의 프로세스는 모든 비트 노드가 옳다고(예를 들어, 모든 패리티 검사 방정식이 만족된 경우) 간주될 때까지 또는, 복호화 실패가 선언되는, 미리 정한 반복의 횟수에 도달할 때까지 반복된다.

도 6은 희소 패리티 검사 매트릭스의 서브 매트릭스의 설명도이며, 여기에서 서브 매트릭스는, 본 발명에 따른, 하부 삼각 지역에 한정된 패리티 검사 값을 포함한다. 앞에서 설명했듯이, (도 2의) 부호기(203)는 패리티 검사 매트릭스의 하부 삼각 부분의 값을 제한함으로써 간단한 부호 기술을 사용할 수 있다. 본 발명의 실시예에 따르면, 패리티 검사 매트릭스에 부과된 제한은 다음과 같은 모양이다.

여기서 B는 하부 삼각이다.

어떠한 정보 블록 i = (i₀, i₁, , i_k-1)는 Hc^T = 0를 사용하여 코드워드 c = (i₀, i₁, , i_k-1, p ₀, p ₁,..,p _n-k-1)로 부호화되고, 다음과 같은 패리티 비트를 반복적 으로 푼다.

그리고 p ₂, p ₃,, p _n-k-1도 같은 방법으로 푼다.

도 7은 비제한적인 패리티 검사 매트릭스(H matrix)를 사용하는 코드와 도 6의 제한적인 H 매트릭스를 사용하는 코드 간의 성능을 나타내는 그래프이다. 이 그래프는 두 LDPC 코드, 일반적인 패리티 검사 매트릭스를 가지는 것과 부호화를 간단하게 하기 위하여 패리티 검사 매트릭스를 하부 삼각에 제한한 것, 간의 성능 비교를 보여준다. 이 시뮬레이션을 위한 변조는 8-PSK이다. 성능 손실은 0.1dB이다. 그러므로, 하부 삼각 H 매트릭스에 근거한 성능 손실은 무시할 정도이며, 부호화 기술의 단순성에서의 이득은 대단하다. 따라서, 어떠한 하부 삼각 또는 열 및/또는 행 순열 아래의 상부 삼각과 동등한 패리티 검사 매트릭스가 같은 목적으로 사용될 수 있다.

도 8a와 도 8b는, 각각, 도 1a의 시스템에서 각각 사용될 수 있는, 비 그레이 8-PSK 변조 방식과 그레이 8-PSK 변조(Grey 8-PSK modulation)의 설명도이다. 도 8a의 비 그레이 8-PSK 변조 방식은 매우 낮은 프레임 삭제 비(frame erasure rate(FER))를 요구하는 시스템을 제공하기 위하여 도 3의 수신기에 사용될 수 있다. 이 요구 사항은, 도 8b에 보여진 바와 같이, BCH(Bose, Chaudhuri, and Hocquenghem), 해밍(Hamming), 또는 리드-솔로몬(Reed-Solomon; RS) 코드와 같은, 외부 코드와 연결하여 그레이 8-PSK 방식을 사용함으로써 만족시킬 수 있다.

또는, 도 8b의 그레이 8-PSK 방식은 외부 코드로 구현될 수 있다. 이 방법에 의하면, 8-PSK 변조를 사용할 수도 있는, LDPC 복호기(305)(도 3)와 비트 매트릭스 생성기(307) 간의 반복이 필요 없다. 외부 코드가 없다면, 도 9에서 보여진 것과 같이, 그레이 레이블링(Grey labeling)을 사용하는 LDPC 복호기(305)는 전의 오류 플로어(floor)를 나타낸다.

도 9는 그레이 레이블링(Gray labeling)을 사용하는 코드와 도 8a와 도 8b의 비 그레이 레이블링(non-Gray labeling)을 사용하는 코드 간의 성능을 나타내는 그래프이다. 오류 플로어는, LDPC 복호기(305)에서의 피드백이 옳다고 가정하면, 알려진 2 비트를 가진 두개의 8-PSK가 비 그레이 레이블링과 더 떨어져 있기 때문에 비 그레이 레이블링으로 하는 8-PSK의 비트 매트릭스의 재생성이 더 정확하다는 것에서 기인한다. 이것은 동등하게 더 높은 신호 대 잡음비(SNR)에서 동작하는 것으로 볼 수 있다. 그러므로, 비록 그레이 또는 비 그레이 레이블링을 사용하는 LDPC 코드의 오류 점근선이 같은 기울기(서로 평행)를 가진다 할 지라도, 비 그레이 레이블링을 가진 것이 어떠한 SNR에서나 더 낮은 FER를 지난다.

한편으로는, 매우 낮은 FER을 요구하지 않는 시스템에서는, 매 LDPC 복호기 반복에 앞서 8-PSK 비트 매트릭스를 재생성하는 것이 추가적인 복잡성을 가져올 수 있으므로, LDPC 복호기(305)와 8-PSK 비트 매트릭스 생성기(307) 간의 반복이 없는 그레이 레이블링이 더 적합할 수 있다. 거기에 더하여, 그레이 레이블링이 사용되었을 경우, 매 LDPC 복호기 반복에 앞서 8-PSK 비트 매트릭스를 재생성하는 것은 단지 아주 적은 성능 향상을 가져온다. 앞서 언급한 바와 같이, 반복 없는 그레이 레이블링은, 외부 코드가 설치된 경우에, 매우 낮은 FER을 요구하는 시스템에서 사용될 수 있다.

그레이 레이블링과 비 그레이 레이블링 간의 선택은 LDPC 코드 특징에도 의존한다. 일반적으로, 비트 또는 검사 노드의 차원이 증가할수록, 높은 노드 차원에서는 LDPC 복호기(305)에서 8-PSK (또는 비슷한 고차원 변조) 비트 매트릭스 생성기(307)로의 초기 피드백이 비 그레이 레이블링에서 더 악화되기 때문에 그레이 레이블링이 더 좋다.

8-PSK (또는 비슷한 고차원) 변조가 이진 복호기와 같이 사용된 경우에는, 기호의 3 (또는 그 이상) 개의 비트가 똑같이 잡음을 가지고 수신되지 않는 다는 것은 알려져 있다. 예를 들어 그레이 8-PSK 레이블링에서는, 기호의 3번째 비트가 다른 2개의 비트들 보다 복호기에게 더 잡음이 많다고 간주된다. 그러므로, LDPC 코드 설계는 8-PSK 기호의 더 잡음이 많은 3번째 비트로 대변되는 그들 비트 노드들에게 그들 비트들이 2번 페널티를 받지 않게 하기 위해서 적은 수의 에지(edge)를 할당하지 않는다.

도 10은, 본 발명에 따라서, 비 그레이 매핑(non-gray mapping)을 사용하는 도 3의 LDPC 복호기의 동작 흐름도이다. 이 방법에 의하면, LDPC 복호기와 비트 매트릭스 생성기는 번갈아 반복한다. 이 예에서는, 8-PSK 변조가 사용되었다; 하지만, 같은 원리가 다른 고차원 변조 방식에도 적용된다. 이 시나리오에서, 변조기(301)가 수신된 잡음이 있는 기호점들과 비트 매트릭스 생성기(307)로의 8-PSK 기호점 간의 거리를 나타내는 거리 벡터 d를 출력한다고 가정하며, 여기서 벡터 요소들은 다음과 같다:

8-PSK 비트 매트릭스 생성기(307)는 선행 확률 정보(priori probability information)와 후행 확률 정보(posteriori probability information)를 교환하기 위하여 LDPC 복호기(305)와 통신하며, 이것들은 각각, u와 a로 표현된다. 이것은, 벡터 u와 a는 각각 부호화된 비트의 로그 가능성 비(log likelihood ratio)의 선행 및 후행 확률을 나타낸다.

8-PSK 비트 매트릭스 생성기(307)는 3 비트의 각 그룹에 대하여 선행 가능성 비(priori likelihood ratio)를 다음과 같이 생성한다. 먼저, 부호화된 비트들의 관한 외부 정보가 얻어진다:

e_j = a_j - h_j _j = 0, 1, 2.

다음으로, 8-PSK 기호 확률들, p _i i = 0,1,,7이 결정된다.

* y_j = -f(0,e_j) j = 0, 1, 2

여기서 f(a,b) = max(a,b) + LUT _f (a,b)이며

LUT _f (a,b) = ln(1+e^-｜a-b｜)

다음으로, 비트 매트릭스 생성기(307)가 LDPC 복호기(305)의 입력으로써 부호화된 비트들의 선행 로그 가능성 비(priori log likelihood ratio)를 다음과 같이 결정한다:

두 개 이상의 변수가 있는 함수 f(.)는 재귀적으로 개산할 수 있음을 주지해야한다; 예를 들어, f(a, b, c) = f(f(a, b), c).

비 그레이 매핑(non Gray mapping)을 이용하는 LDPC 복호기(305)의 동작이 설명된다. 단계(1001)에서, LDPC 복호기(305)는 다음과 같은 (그리고 도 12a에 보여진 것과 같이) 첫번째 반복 전에 부호화된 비트의 로그 가능성 비, v를 초기화한다.

v_n→ki = u_n, n=0,1,...,N-1, u=1,2,..., deg (비트 노드 n)

여기서, v_n→ki는 비트 노트 n에서 그것의 인접 검사 노드 k_i로 가는 메시지를 나타내며, u_n은 비트 n을 위한 복조기 출력을, 그리고 N은 코드워드(codeword)의 크기를 나타낸다.

단계(1003)에서 검사 노드( k)가 업데이트되며, 여기서 입력(v)이 출력(w)를 야기한다. 도 12b에서 보았듯이, 인접하는 비트 노드(dc)에서 검사 노드(k)로 들어오는 메시지는 v_n1→k, v_n2→k,.., v_nde→k로 나타난다. 여기서 목표는 검사 노드k에서 인접 비트 노드dc로 나가는 메시지를 계산하는 것이다. 이들 메시지는 w_k→ni, w_k→n2, w_k→nde로 나타나며, 여기서

함수 g()는 다음과 같이 정의된다:

g(a,b) = sign(a)×sign(b)×{min(｜a｜,｜b｜)} + LUT_g(a,b) 이고,

여기서, LUT_g(a,b) = ln(1+e^-｜a+b｜) - ln(1+e^-｜a-b｜) 이다.

함수 f와 마찬가지로, 두개 이상의 변수를 가지는 함수 g는 재귀적으로 계산할 수 있다.

다음에는, 복호기(305)는, 단계(1205)에서, 다음과 같은 후행 확률 정보(도 12c)를 출력한다.

단계(1007)에서는, 모든 패리티 검사 방정식이 만족되었는지를 판정한다. 만약, 이들 패리티 검사 방정식들이 만족되지 않았다면, 복호기(305)는, 단계(1009)에서, 8-PSK 비트 매트릭스와 채널 입력 un을 다시 불러낸다. 그 다음으로, 단계(1011)에서, 비트 노드가 업데이트된다. 도 13c에 보여진 것과 같이, 인접하는 검사 노드(dv)에서 비트 노드(n)로 들어오는 메시지는 w_k1→n, w_k2→n,.., w_kdv→n로 나타난다. 비트 노드(n)에서 나가는 메시지는 인접하는 검사 노드(dv)로 계산되고, 이러한 메시지는 v_n→k1, v_n→k2,.., v_n→kdv로 표현되며, 다음과 같이 계산된다:

단계(1013)에서, 복호기(305)는 (모든 패리티 검사 방정식이 만족된 경우) 경판정(hard decision)을 출력한다.

위의 방법은 비 그레이 레이블링이 사용되었을 경우에 적합하다. 그러나, 그레이 레이블링이 사용된 경우에는, 도 11의 프로세스가 실행된다.

도 11은, 본 발명에 따른, 그레이 매핑(gray mapping)을 사용하는 도 3의 LDPC 복호기(decoder)의 동작의 흐름도이다. 그레이 레이블링이 사용된 경우, LDPC 복호기의 매 반복 이후에 재생성하는 비트 매트릭스가 아주 적은 성능 향상을 가져올 수도 있으므로, 비트 매트릭스는 유리하게 LDPC 복호기 앞에서 오직 한번만 생성된다. 도 10의 단계 1001과 단계 1003에서, 부호화된 비트의 로그 가능성 비(log likelihood ratio)의 초기화(v)가 수행되며, 단계 1101와 단계 1103에서 검사 노드가 업데이트된다. 다음으로, 단계 1105에서, 비트 노드(n)가 업데이트된다. 그 이후, 복호기는 후행 확률 정보(단계 1107)를 출력한다. 단계(1109)에서, 모든 패리티 검사 방정식이 만족되었는지 판정한다; 만약 그렇다면, 복호기는 경판정(hard decision)을 출력한다(단계 1111). 그렇지 않다면, 단계 1103 1107이 반복된다.

도 13a-도 13c는 본 발명의 여러 가지 실시예에 따라서 생성된 LDPC의 모의실험결과를 나타내는 그래프이다. 특히, 도 13a-도13c는 고차원 변조와 3/4(QPSK, 1.485 bits/symbol), 2/3(8-PSK, 1.980 bits/symbol), 그리고 5/6(8-PSK, 2.474 bits/symbol)을 사용한 LDPC 코드의 성능을 보여준다.

검사 노드와 비트 노드 간의 상호 연결을 구현하기 위한 일반적인 방법은 두개 존재한다: (1) 완전히 평행 방법, 그리고 (2) 부분 평행 방법. 완전 평행 구조에서는, 모든 노드와 그들의 상호 연결이 물리적으로 구현된다. 이 구조의 장점은 속도이다.

하지만, 완전 평행 구조는 모든 노드와 그들의 연결을 구현하는데 더 큰 복잡성을 내포한다. 그러므로 완전 평행 구조에서는, 복잡성을 줄이기 위하여 좀 더 작은 블록 크기가 요구될 수 있다. 이러한 경우, 같은 클록 주파수(clock frequency)에 대해, 처리량의 비례적인 감소와 FER 대 Es/No 성능의 퇴보가 초래될 수 있다.

LDPC 코드를 구현하는 두 번째 방법은 노드의 전체 수 중 일부만 물리적으로 구현하고 이 수적으로 제한된 물리적 노드만 사용하여 코드의 기능적인 노드를 처리하는 것이다. 비록 LDPC 복호기 동작이 매우 간단하게 만들어질 수 있고 병렬로 수행될 수 있어도, 설계에 있어서 여기에 대한 도전은 어떻게 무작위로 분배된 비트 노드와 검사 노드 간의 통신이 수립되었는가 이다. 본 발명의 한 실시예에 따르면, 도 3의 복호기(305)는, 겉으로 보기에 무작위인 코드를 구현하기 위하여, 메모리를 구조화된 방식으로 접근함으로써 이 문제를 설명한다. 이 방법은 도 14a와 도 14b와 연관지어 설명한다.

도 14a와 도 14b는 각각, 본 발명에 따라서, LDPC 코딩에서 무작위성을 구현할 수 있도록 하는 구조적인 접근을 지원하기 위하여 구성된 메모리의 상단 에지(top edge)와 하단 에지(bottom edge)의 설명도이다. 패리티 검사 매트릭스의 생성에 초점을 맞춤으로써 진짜 무작위 코드의 성능을 손상하지 않고 구조화된 접근을 얻을 수 있다. 일반적으로, 패리티 검사 매트릭스는 검사 노드와 비트 노드간의 연결에 의하여 지정될 수 있다. 예를 들어, 비트 노드는 (예를 들어) 392의 그룹으로 나누어질 수 있다. 거기에 더하여, 예를 들어, 3 수준(degree)의 첫번째 비트 노드에 연결된 검사 노드가 a, b, 그리고 c로 번호가 붙었다고 가정하면, 두 번째 비트 노드에 연결된 검사 노드는 a + p, b + p, 그리고 c + p로 번호가 붙으며, 세 번째 비트 노드에 연결된 검사 노드는 a + 2p, b +2 p, 그리고 c +2 p로 번호가 붙는다. 다음 392 비트 노드의 그룹에 대해서는, 첫번째 비트 노드에 연결된 검사 노드는 a, b, 그리고 c와 다르며 적당한 p의 선택으로 모든 검사 노드가 같은 수준을 갖는다. 결과로 나오는 LDPC 코드가 사이클-4 그리고 사이클 6이 없도록 자유 상수(free constant)를 무작위 검색한다.

위의 구성은 검사 노드와 비트 노드 프로세싱 도중에 메모리 접근을 용이하게 한다. 이분 그래프에서 에지의 값들은 RAM과 같은 저장 매체에 저장할 수 있다. 검사 노드와 비트 노드 프로세싱 도중에 완전한 무작위 LDPC 코드를 위해서는 에지의 값들은 무작위 방식으로 하나씩 접근되어야 할 필요가 있다. 그러나, 이 접근 방식은 고속 데이터 레이트 응용(high data rate application)을 위해서는 너무 느릴 수 있다. 도 14a와 도 14b는 관계가 있는 에지들의 큰 그룹이 하나의 클록 사이클에 있는 방식으로 구성되어 있다; 그러므로, 이 값들은 메모리에 같이 위치한다. 실제에서는, 비록 완전 무작위 코드를 이용하더라도, 검사 노드의 그룹을 위해서( 그리고 각 비트 노드를 위해서), 관계가 있는 에지는 RAM에 나란히 위치할 수 있으나, 이렇게 되면 비트 노드 (각자 검사 노드)의 그룹에 인접한 관계가 있는 에지는 무작위적으로 RAM에 분산된다. 그러므로, 본 발명에 의한 일체감(togetherness)은 패리티 검사 매트릭스 자체의 디자인에서 유래한다. 이것은, 검사 매트릭스 디자인이 비트 노드와 검사 노드의 그룹을 위한 관계가 있는 에지를 RAM에 같이 동시에 위치하게끔 보장한다.

도 14a 및 도 14b에서 보였듯이, (예 6) 각각의 박스는 복수의 비트인 에지의 값을 포함한다. 본 발명의 한 실시예에 의하면, 에지 RAM은 두 부분으로 나뉜다: 상단 에지 RAM (도 14a)과 하단 에지 RAM (도 14b). 하단 에지 RAM은, 예를 들어, 2 수준의 비트 노드와 검사 노드 간의 에지를 포함한다. 상단 에지 RAM은 2 이상의 수준의 비트 노드와 검사 노드 간의 에지를 포함한다. 그러므로, 모든 검사 노드를 위해서, 2개의 인접 에지가 하단 RAM에 저장되며, 나머지 에지들은 상단 에지 RAM에 저장된다.

계속 위의 예에서, 392 비트 노드와 392 검사 노드의 그룹이 동시에 프로세싱을 위하여 선택된다. 392 검사 노드 프로세싱을 위해서, q 연속적인 열이 상단 에지 RAM에서, 그리고 2 연속적인 열이 하단 에지 RAM에서 접근이 된다. 이 예에서, 각 검사 노드의 수준은 q + 2이다. 비트 노드 프로세싱을 위해서는, 만약 392 비트 노드의 그룹이 2 수준이라면, 이들 에지는 하단 에지 RAM의 2 연속 열에 위치한다. 만약 비트 노드가 2보다 큰 d 수준이라면(d>2), 이들 에지는 상단 에지 RAM의 d 열에 위치한다. 이들 d 열의 어드레스는 ROM과 같은 비휘발성 메모리에 저장될 수 있다. 하나의 열의 에지가 392 비트 노드의 첫번째 에지에 상응하고, 다른 열의 에지가 392 비트 노드의 두 번째 에지에 상응한다. 게다가 각 열에 대하여, 392 그룹의 첫 번째 비트 노드에 속하는 에지의 행 인덱스 역시 ROM에 저장될 수 있다. 두 번째, 세 번째 비트 노드 등에 상응하는 에지는 둘러 싸이는(wrapped around) 방식으로 시작 행 인덱스를 따른다. 예를 들어, 만약 열의 j번째 에지가 첫번째 비트 노드에 속하면, (j+1) 번째 에지가 두 번째 비트 노드에 속하고, (j+2) 번째 에지가 세 번째 비트 노드에 속하고, …, 그리고 (j-1) 번째 에지가 392 번째 비트 노드에 속한다.

(도 14a와 도 14b에 나타난) 위의 구성에서, LDPC 코딩 중의 메모리 접근 속 도는 상당히 증가한다.

도 15는 본 발명에 따른 실시예가 구현될 수 있는 컴퓨터 시스템(1500)을 예시하고 있다. 컴퓨터 시스템(1500)은 정보의 통신을 위하여 버스(1501) 또는 다른 통신 방식을 포함하고, 정보 처리를 위하여 버스(1501)에 연결된 프로세서(1503)를 포함한다. 또한 컴퓨터 시스템(1500)은 프로세서(1503)에 의하여 처리될 정보와 명령을 저장하기 위한 버스(1501)에 연결된, RAM과 같은, 주 메모리(1505) 또는 다른 동적 저장 장치를 포함한다. 주 메모리(1505)는 프로세서(1503)에 의하여 처리될 명령의 수행 도중에 발생하는 임시 변수 또는 다른 중간의 정보를 저장하는데 사용될 수도 있다. 또한 컴퓨터 시스템(1500)은 정적 정보와 프로세서(1503)를 위한 명령을 저장하기 위한 버스(1501)에 연결된, ROM(1507) 또는 다른 정적 저장 장치를 포함한다. 자기 디스크 또는 광 디스크와 같은 저장 장치(1509)가 정보와 명령의 저장을 위하여 버스(1501)에 추가적으로 연결되어 있다.

컴퓨터 시스템(1500)은 컴퓨터 사용자에게 정보를 디스플레이하기 위하여 CRT, LCD, 액티브 매트릭스 디스플레이, 또는 플라즈마 디스플레이와 같은 디스플레이(1511)에 버스(1501)를 통하여 연결될 수 있다. 알파벳과 숫자, 그리고 다른 키를 포함하는 키보드와 같은 입력 장치(1513)가 프로세서에게 정보와 명령 선택을 통신하기 위하여 버스(1501)에 연결되어 있다. 다른 종류의 사용자 입력 장치에는 방향 정보와 명령 선택을 프로세서(1503)에게 통신하고 디스플레이(1511)에 커서 움직임을 제어하기 위한 마우스, 트랙 볼, 또는 커서 방향 키 등이 있다.

본 발명의 한 실시예에 따르면, 컴퓨터 시스템(1500)이 주 메모리(1505)에 있는 명령의 조합을 실행하는 프로세서(1503)에 대한 응답으로써 LDPC 코드를 생성한다. 이들 명령들은 저장 장치(1509)와 같은 다른 컴퓨터 판독 가능 매체로부터 주 메모리로 읽어 올 수 있다. 주 메모리(1505)에 있는 명령의 조합의 실행은 여기에 설명한 프로세스 단계를 프로세서(1503)가 수행하도록 한다. 주 메모리(1505)에 있는 명령을 실행시키기 위해 다른 처리 구조의 하나 이상의 프로세서가 이용될 수도 있다. 다른 실시예에서는, 하드 와이어 회로가 소프트웨어 명령을 대신 해서 또는 소프트웨어와 같이 본 발명의 실시예를 실현하기 위하여 사용될 수도 있다. 그러므로, 본 발명의 실시예는 어떤 하드웨어 회로와 소프트웨어의 특정 조합에 한정되지 않는다.

컴퓨터 시스템(1500)은 또한 버스(1501)에 연결된 통신 인터페이스(1517)를 포함한다. 통신 인터페이스(1517)는 로컬 네트워크(1521)에 연결된 네트워크 링크(1519)와 연결된 양 방향 데이터 통신을 제공한다. 예를 들어, 통신 인터페이스(1517)는 전화선의 종류에 따라 데이터 통신 연결을 제공하는 DSL 카드 또는 모뎀, ISDN 카드, 케이블 모뎀, 또는 전화 모뎀이 될 수 있다. 다른 예로써, 통신 인터페이스(1517)는 호환성 있는 LAN으로의 데이터 통신 연결을 제공하기 위하여 구내 정보 통신망(LAN) 카드 (예를 들어, Ethernet^TM 또는 비동기 전송 방식(ATM)용)일 수 있다. 무선 연결 역시 구현될 수 있다. 위의 어느 구현에서나, 통신 인터페이스(1517)는 여러 가지 종류의 정보를 나타내는 디지털 데이터 스트림을 전달하는 전기적, 전자기적, 또는 광 신호를 주고 받는다. 더 나아가, 통신 인터페이 스(1517)는 Universal Serial Bus(USB), Personal Computer Memory Card International Association(PCMCIA) 인터페이스, 등과 같은 주변 인터페이스 장치를 포함할 수 있다.

네트워크 링크(1519)는 일반적으로 다른 데이터 장치에 하나 또는 그 이상의 네트워크를 통하여 데이터 통신을 제공한다. 예를 들어, 네트워크 링크(1519)는, 네트워크(1525)(예를 들어, 광역통신망(WAN) 또는 인터넷이라고 널리 알려진 글로벌 패킷 데이터 통신 네트워크) 또는 서비스 제공자에 의하여 운영되는 데이터 장치와 연결될 수 있는 로컬 네트워크(1521)를 통하여 호스트 컴퓨터(1523)로 연결을 제공할 수 있다. 구내 통신망(1521)과 네트워크(1525)는 모두 정보와 명령을 전달하기 위하여 전기, 전자기, 또는 광 신호를 사용한다. 여러 네트워크를 통하는 신호와 네트워크 링크(1519) 및 통신 인터페이스(1517)를 통한, 컴퓨터 시스템(1500)과 디지털 데이터를 통신하는, 신호들은 정보와 명령을 운반하는 반송파의 대표적인 형태이다.

컴퓨터 시스템(1500)은 네트워크(들), 네트워크 링크(1519), 그리고 통신 인터페이스(1517)를 통하여 메시지를 보낼 수 있고 프로그램 코드를 포함한 데이터를 받을 수 있다. 인터넷 예에서는, (나타나지 않은) 서버가 본 발명의 실시예를 구현하기 위한 응용 프로그램에 속하는 요구된 코드를 네트워크(1525), 로컬 네트워크(1521), 그리고 통신 인터페이스(1517)를 통해서 전송할 수 있다. 프로세서(1503)는 전송된 코드를 받는 도중에 실행시킬 수도 있고 나중에 실행하기 위해 저장 장치(1509) 또는 다른 비휘발성 저장 장치에 저장할 수 있다. 이러한 방법으로, 컴퓨터 시스템(1500)은 응용 코드를 반송파 형식으로 얻을 수 있다.

여기서 사용된 "컴퓨터 판독 가능 매체"라는 용어는 실행을 위하여 프로세서(1503)에 명령을 제공하는데 참여하는 어떠한 매체를 말한다. 이러한 매체는, 비휘발성 매체, 휘발성 매체, 그리고 전송 매체 등의 형식에 제한되지 않고 이들을 포함한다. 비휘발성 매체는, 예를 들어, 저장 장치(1509)와 같은 광 또는 자기 디스크를 포함한다. 휘발성 매체는 주 메모리(1505)와 같은 동적 메모리를 포함한다. 전송 매체는, 버스(1501)를 구성하는 와이어를 포함하여, 동축 케이블(coaxial cable), 구리 와이어(copper wire) 그리고 광섬유(fiber optic)를 포함한다. 전송 매체는 무선 주파수(radio frequency; RF) 그리고 적외선(infrared; IR) 데이터 통신 도중에 발생하는 음향파(acoustic), 광파(optical), 또는 전자기파의 형태를 취할 수 있다. 컴퓨터 판독 가능 매체의 일반적인 형태는, 예를 들어, 플로피 디스크, 플렉시블 디스크, 하드 디스크, 자기 테이프, 모든 자기 매체, CD-ROM, CDRW, DVD, 모든 광 매체, 펀치 카드, 종이 테이프, 광 마크 쉬트(optical mark sheet), 구멍의 패턴 또는 광적으로 인식할 수 있는 표시가 있는 물리적 매체, RAM, PROM, EPROM, FLASH-EPROM, 모든 메모리 칩 또는 카트리지(cartridge), 반송파, 또는, 컴퓨터가 읽을 수 있는 모든 다른 매체를 포함한다.

실행을 위하여 프로세서에게 명령을 제공하는 것에 여러 가지 형태의 컴퓨터 판독 가능 매체가 관여될 수 있다. 예를 들어, 본 발명의 적어도 일부를 수행하기 위한 명령은 초기에 원격 컴퓨터의 자기 디스크에 담겨질 수도 있다. 이러한 시나 리오에서는, 원격 컴퓨터가 명령을 주 메모리에 명령을 로드하고 모뎀을 사용하는 전화선을 통해 명령을 보낸다. 로컬 컴퓨터 시스템의 모뎀이 전화선 상의 데이터를 받고 적외선 송신기를 사용하여 데이터를 적외선 신호로 전환하며 적외선 신호를, 개인 휴대 정보 단말기(personal digital assistance; PDA)와 랩탑(laptop)과 같은, 휴대용 컴퓨팅 장치로 전송한다. 휴대용 컴퓨팅 장치에 있는 적외선 감지기가 적외선 신호에 내재된 정보와 명령을 받고 버스에 그 데이터를 올려놓는다. 버스는 그 데이터를 주 메모리로 전달하며, 여기서 프로세서는 명령을 검색하여 실행한다. 주 메모리로부터 얻은 명령은 프로세서의 실행 전 또는 후에 저장 장치에 저장될 수도 있다.

따라서, 본 발명의 여러 실시예들은, 부호기와 복호기를 간단히 하기 위해서, 구조화된 저밀도 패리티 검사(LDPC) 코드를 생성하는 방법을 제공한다. LDPC 코드의 구조는 패리티 검사 매트릭스가 하부 삼각형이 되도록 제한함으로써 제공된다. 또한, 이 방법은 (8-PSK와 같은) 고차원 변조 집합의 더욱 취약한 비트에게 추가적인 오류 보호를 제공하기 위하여 전송 비트들에 대한 LDPC 코드의 비동등 오류 보호 능력을 유리하게 이용할 수 있다. 거기에 더하여, 패리티 검사 매트릭스는 미리 저장된 상수들과 비트 방식 동작을 이용하여 알고리즘적으로 생성될 수 있다. LDPC의 효율적인 복호화는 패리티 검사 매트릭스의 검사 노드로부터 비트 노드까지의 연속적인 에지를 나타내는 정보를 연속적인 메모리 슬롯(slot)에 저장함으로써 얻을 수 있다. 위의 방식은 성능의 감소 없이 복잡성의 감소를 가져온다.

비록 본 발명이 여러 실시예와 구현에 연관되어 설명되었지만, 본 발명은 여기에 제한되지 아니하고, 첨부된 청구항의 범위에 포함되는, 여러 가지 명백한 변형 실시와 균등한 구성을 포함하는 것이다.

Claims

저밀도 패리티 검사(LDPC) 코드의 생성 방법으로서,

수신된 입력 메시지를, 상기 LDPC 코드의 생성 매트릭스를 이용하지 않고, 상기 LDPC 코드의 패리티 검사 매트릭스만을 이용하여, LDPC 코드워드로 변환하는 단계 - 상기 패리티 검사 매트릭스의 값은 인접하는 에지 값들을 그룹화하여 저장하는 것을 허용하는 구조화된 LDPC 코드를 제공하도록 미리 지정되어 있음 -; 및

상기 LDPC 코드워드를 출력하는 단계

를 포함하는 저밀도 패리티 검사 코드의 생성 방법.
제1항에 있어서,

상기 변환 단계에서 상기 패리티 검사 매트릭스의 소정의 삼각형 부분은 제로 값을 갖는 저밀도 패리티 검사 코드의 생성 방법.
제1항에 있어서,

상기 변환 단계에서 상기 패리티 검사 매트릭스의 소정의 삼각형 부분은 열 또는 행 교환 연산 후에 제로 값을 갖는 저밀도 패리티 검사 코드의 생성 방법.
제1항에 있어서,

상기 LDPC 코드를 8-PSK(Phase Shift Keying), 16-QAM(Quadrature Amplitude Modulation) 및 QPSK(Quadrature Phase Shift Keying) 중의 하나를 포함하는 변조 방식에 따라서 변조하는 단계를 더 포함하는 저밀도 패리티 검사 코드의 생성 방법.
선형 블록 코드를 생성하기 위한 명령을 기억하고 있는 컴퓨터 판독가능 기록 매체로서,

상기 명령은 실행시 청구항 1의 방법을 하나 또는 그 이상의 프로세서로 하여금 수행하도록 구성된 컴퓨터 판독가능 기록 매체.
선형 블록 코드의 부호화를 지원하는 방법으로서,

고차 신호 집합 비트를 상기 선형 블록 코드에 대응하는 패리티 검사 매트릭스와 관련된 이분 그래프의 비트 노드에 매핑하는 단계

를 포함하며,

상기 신호 집합의 취약한 비트는 적어도 3개의 에지를 갖는 비트 노드에 매핑되는 선형 블록 코드의 부호화를 지원하는 방법.
제6항에 있어서,

상기 신호 집합은 8-PSK(Phase Shift Keying), 16-QAM(Quadrature Amplitude Modulation) 및 QPSK(Quadrature Phase Shift Keying) 중의 하나를 포함하는 선형 블록 코드의 부호화를 지원하는 방법.
선형 블록 코드를 생성하기 위한 명령을 기억하고 있는 컴퓨터 판독가능 기록 매체로서,

상기 명령은 실행시 청구항 6의 방법을 하나 또는 그 이상의 프로세서로 하여금 수행하도록 구성된 컴퓨터 판독가능 기록 매체.
선형 블록 코드의 부호화를 지원하는 방법으로서,

고차 신호 집합 비트를 상기 선형 블록 코드에 대응하는 패리티 검사 매트릭스와 관련된 이분 그래프의 비트 노드에 매핑하는 단계

를 포함하며,

상기 신호 집합의 취약한 비트는 더 신뢰할 수 있는 비트의 수보다 많은 수의 에지를 갖는 비트 노드에 매핑되는 선형 블록 코드의 부호화를 지원하는 방법.
제9항에 있어서,

상기 신호 집합은 8-PSK(Phase Shift Keying), 16-QAM(Quadrature Amplitude Modulation) 및 QPSK(Quadrature Phase Shift Keying) 중의 하나를 포함하는 선형 블록 코드의 부호화를 지원하는 방법.
선형 블록 코드를 생성하기 위한 명령을 기억하고 있는 컴퓨터 판독가능 기록 매체로서,

상기 명령은 실행시 청구항 9의 방법을 하나 또는 그 이상의 프로세서로 하여금 수행하도록 구성된 컴퓨터 판독가능 기록 매체.
저밀도 패리티 검사(LDPC) 코드의 생성 방법으로서,

수신된 입력 메시지를, 상기 LDPC 코드의 생성 매트릭스를 이용하지 않고, 상기 LDPC 코드의 패리티 검사 매트릭스만을 이용하여, LDPC 코드워드로 변환하는 단계- 상기 패리티 검사 매트릭스의 값은 인접하는 에지 값들을 그룹화하여 저장하는 것을 허용하는 구조화된 LDPC 코드를 제공하도록 미리 지정되어 있음 -;

상기 LDPC 코드워드에 외부(outer) 코드를 부가하는 단계; 및

상기 LDPC 코드워드를 상기 부가된 외부 코드와 함께 출력하는 단계

를 포함하는 저밀도 패리티 검사 코드의 생성 방법.
제12항에 있어서,

상기 부가 단계에서의 상기 외부 코드는 BCH(Bose-Chaudhuri-Hocquenghem) 코드, RS(Reed-Solomon) 코드 및 해밍(Hamming) 코드 중의 하나를 포함하는 저밀도 패리티 검사 코드의 생성 방법.
저밀도 패리티 검사(LDPC) 코드의 생성 방법으로서,

서로 인접하는 일군의 비트 노드에 대한 에지 값들을 메모리 내의 연속한 위치에 기억시키는 단계; 및

이와 동시에, 서로 인접하는 일군의 검사 노드에 대한 에지 값들을 메모리 내의 연속한 위치에 기억시키는 단계

를 포함하며,

상기 메모리의 제1 부분은 n 이상의 수준(degree)의 비트 노드들에 인접한 에지의 에지 값들 용으로 지정되어 있으며, 상기 메모리의 제2 부분은 n 미만의 수준의 비트 노드들에 인접한 에지의 에지 값들 용으로 지정되어 있는 저밀도 패리티 검사 코드의 생성 방법.
제14항에 있어서,

상기 메모리를 액세스하여, 1 클록 주기 내의 일군의 비트 노드 또는 일군의 검사 노드와 관련된 에지 값들을 검색하는 단계를 더 포함하는 저밀도 패리티 검사 코드의 생성 방법.
선형 블록 코드를 생성하기 위한 명령을 기억하고 있는 컴퓨터 판독가능 기록 매체로서,

상기 명령은 실행시 청구항 14의 방법을 하나 또는 그 이상의 프로세서로 하여금 수행하도록 구성된 컴퓨터 판독가능 기록 매체.
저밀도 패리티 검사(LDPC) 코드를 생성하기 위한 시스템으로서,

수신된 입력 메시지를, LDPC 코드의 생성 매트릭스를 이용하지 않고, LDPC 코드의 패리티 검사 매트릭스만을 이용하여, LDPC 코드워드로 변환하는 수단 - 상기 패리티 검사 매트릭스의 값은 인접하는 에지 값들을 그룹화하여 저장하는 것을 허용하는 구조화된 LDPC 코드를 제공하도록 미리 지정되어 있음 -; 및

상기 LDPC 코드워드를 출력하는 수단

을 포함하는 저밀도 패리티 검사 코드 생성 시스템.
제17항에 있어서,

상기 패리티 검사 매트릭스의 소정의 삼각형 부분은 제로 값을 가지며,

상기 LDPC 코드와 관련된 상기 패리티 비트의 생성을 돕기 위하여, 상기 패리티 검사 매트릭스의 값들을 기억하기 위한 수단을 더 구비하는 저밀도 패리티 검사 코드 생성 시스템.
제17항에 있어서,

상기 패리티 검사 매트릭스의 소정의 삼각형 부분은 열 또는 행 교환 연산 후에 제로 값을 가지며,

상기 LDPC 코드와 관련된 상기 패리티 비트의 생성을 돕기 위하여, 상기 패리티 검사 매트릭스의 값들을 기억하기 위한 수단을 더 구비하는 저밀도 패리티 검사 코드 생성 시스템.
제17항에 있어서,

상기 LDPC 코드를 8-PSK(Phase Shift Keying), 16-QAM(Quadrature Amplitude Modulation) 및 QPSK(Quadrature Phase Shift Keying) 중의 하나를 포함하는 변조 방식에 따라서 변조하는 수단을 더 구비하는 저밀도 패리티 검사 코드 생성 시스템.
저밀도 패리티 검사(LDPC) 코드 프로세싱 방법으로서,

동시적인 메모리 액세스를 위해 인접하는 에지 값들을 그룹화하는 것을 허용하도록 구조화된 수신된 LDPC 코드를 LDPC 복호기를 경유하여 복호화하는 단계; 및

매회 또는 수회의 상기 LDPC 복호기의 반복 연산 후에, 신호 집합 비트 매트릭스를 상기 LDPC 복호기에 반복적으로 재생성하는 단계

를 포함하는 저밀도 패리티 검사 코드의 생성 방법.