KR100683084B1 - 저밀도 패리티 검사 부호화 신호의 전송을 지원하는 방법,인코더 및 송신기 - Google Patents

저밀도 패리티 검사 부호화 신호의 전송을 지원하는 방법,인코더 및 송신기 Download PDF

Info

Publication number
KR100683084B1
KR100683084B1 KR1020040070418A KR20040070418A KR100683084B1 KR 100683084 B1 KR100683084 B1 KR 100683084B1 KR 1020040070418 A KR1020040070418 A KR 1020040070418A KR 20040070418 A KR20040070418 A KR 20040070418A KR 100683084 B1 KR100683084 B1 KR 100683084B1
Authority
KR
South Korea
Prior art keywords
ldpc
encoder
code
parity check
tables
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Lifetime
Application number
KR1020040070418A
Other languages
English (en)
Other versions
KR20050025075A (ko
Inventor
무스타파 에로즈
린-난 리
펭-웬 선
Original Assignee
더 디렉티브 그룹, 인크.
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 더 디렉티브 그룹, 인크. filed Critical 더 디렉티브 그룹, 인크.
Publication of KR20050025075A publication Critical patent/KR20050025075A/ko
Application granted granted Critical
Publication of KR100683084B1 publication Critical patent/KR100683084B1/ko
Assigned to 디티브이지 라이센싱, 인크. reassignment 디티브이지 라이센싱, 인크. 권리의 전부이전등록 Assignors: 더 디렉티브 그룹, 인크.
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L27/00—Modulated-carrier systems
    • H04L27/18—Phase-modulated carrier systems, i.e. using phase-shift keying
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/25—Error detection or forward error correction by signal space coding, i.e. adding redundancy in the signal constellation, e.g. Trellis Coded Modulation [TCM]
    • H03M13/255—Error detection or forward error correction by signal space coding, i.e. adding redundancy in the signal constellation, e.g. Trellis Coded Modulation [TCM] with Low Density Parity Check [LDPC] codes
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1148—Structural properties of the code parity-check or generator matrix
    • H03M13/116—Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices
    • H03M13/1165—QC-LDPC codes as defined for the digital video broadcasting [DVB] specifications, e.g. DVB-Satellite [DVB-S2]
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1148—Structural properties of the code parity-check or generator matrix
    • H03M13/118—Parity check matrix structured for simplifying encoding, e.g. by having a triangular or an approximate triangular structure
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/29—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
    • H03M13/2906—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes using block codes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00—Arrangements for detecting or preventing errors in the information received
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1105—Decoding
    • H03M13/1131—Scheduling of bit node or check node processing
    • H03M13/1134—Full parallel processing, i.e. all bit nodes or check nodes are processed in parallel
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/13—Linear codes
    • H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
    • H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials
    • H03M13/152—Bose-Chaudhuri-Hocquenghem [BCH] codes

Landscapes

  • Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Probability & Statistics with Applications (AREA)
  • Mathematical Physics (AREA)
  • Multimedia (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • General Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Quality & Reliability (AREA)
  • Error Detection And Correction (AREA)
  • Detection And Prevention Of Errors In Transmission (AREA)
  • Digital Transmission Methods That Use Modulated Carrier Waves (AREA)
  • Radio Relay Systems (AREA)

Abstract

단 프레임(short frame) 길이의 저밀도 패리티 검사(Low Density Parity Check; LPDC) 부호를 인코딩하기 위한 어프로치가 제공된다. 인코더(203)는 외부 BCH(Bose Chaudhuri Hocquenghem) 부호를 갖는 LPDC 부호를 생성한다. 패리티 검사 매트릭스의 일부분을 하위 삼각형(lower triangular)으로 제한시키고/제한시키거나 디코더(305)의 비트 노드와 검사 노드 간의 통신을 간략화시킬 수 있는 다른 요건들을 만족시킴으로써 LDPC 부호가 구성된다. 또한, 순환 반복 검사(CRC) 인코더(209)가 제공되어 CRC 부호에 따른 입력 신호를 인코딩한다. 이러한 어프로치는 특히 위성을 통한 디지털 비디오 방송 서비스에 적용된다.
저밀도 패리티 검사(LDPC) 부호, 스파스 패리티 검사, 외부 BCH 부호, 패리티 검사 매트릭스

Description

저밀도 패리티 검사 부호화 신호의 전송을 지원하는 방법, 인코더 및 송신기{METHOD AND SYSTEM FOR PROVIDING SHORT BLOCK LENGTH LOW DENSITY PARITY CHECK(LDPC) CODES IN SUPPORT OF BROADBAND SATELLITE APPLICATIONS}
도 1은 본 발명의 실시예에 따라 저밀도 패리티 검사(Low Density Parity Check; LDPC) 부호를 활용하도록 구성된 통신 시스템의 도면.
도 2a 및 도 2b는 도 1의 송신기에 구현된 예시적인 LDPC 인코더(encoder)의 도면.
도 2c는 본 발명의 한 실시예에 따른 단 프레임 길이의 LDPC 부호(short frame length LDPC code)를 생성하는 도 2b의 LDPC 인코더의 인코딩 프로세스 흐름도.
도 3은 도 1의 시스템의 예시적인 수신기의 도면.
도 4는 본 발명의 실시예에 따른 스파스 패리티 검사 매트릭스(sparse parity check matrix)의 도면.
도 5는 도 4의 매트릭스의 LDPC 부호의 이분 그래프(bipartite graph) 도면.
도 6은 스파스 패리티 검사 매트릭스의 서브 매트릭스 도면으로서, 서브 매트릭스는 본 발명의 실시예에 따라, 하위 삼각형 영역(lower triangular region)에 제한된 패리티 검사 값을 포함하는 도면.
도 7은 본 발명의 실시예에 따라 LDPC 인코딩 프로세스를 수행할 수 있는 컴퓨터 시스템의 도면.
<도면의 주요 부분에 대한 부호의 설명>
701 : 버스
703 : 프로세서
705 : 주 메모리
707 : ROM
709 : 스토리지 장치
본 발명은 통신 시스템에 관한 것으로, 보다 구체적으로, 코드화 시스템에 관한 것이다.
통신 시스템은 노이즈가 있는 통신 채널을 통한 신뢰성 있는 통신을 보장하기 위한 코딩을 적용한다. 예를 들어, 위성 네트워크와 같은 무선(또는 라디오) 시스템에서, 노이즈 소스는 지리적, 환경적 요인들로부터 많이 있다. 이들 통신 채널은 이론적인 상한(쉐논 리미트(Shannon limit)라고 알려짐)을 정의하는 임의의 신호-대-노이즈 비율(signal to noise ratio; SNR)에서 심볼당 비트로 표현될 수 있는 고정된 용량을 나타낸다. 그 결과, 코딩 설계는 이러한 쉐논 리미트에 접근하는 비율을 달성하는 것이 목표가 되어 왔다. 이 목적은 특히 광대역 강제 위성 시스템에 밀접한 관계가 있다. 쉐논 리미트에 접근하는 코드들 중 이러한 하나의 클래스는 저밀도 패리티 검사(Low Density Parity Check; LDPC) 부호이다.
일반적으로, LDPC 부호는 많은 단점 때문에 널리 사용되지 못했다. 하나의 단점은 LDPC 인코딩 기술이 매우 복잡하다는 것이다. 생성원 매트릭스(generator matrix)를 이용하여 LDPC 부호를 인코딩하려면 매우 큰 비 스파스(non-sparse) 매트릭스 저장이 요구된다. 또한, LDPC 부호는 효율적인 큰 블록을 요구하여, 결과적으로 LDPC 부호의 패리티 매트릭스가 희박할(sparse)지라도, 이들 매트릭스를 저장하는 것이 어렵게 된다.
구현의 측면에서도 많은 난제들에 직면하게 된다. 예를 들어, 스토리지는 LDPC 부호가 실제 널리 사용되지 않는 중요한 이유가 된다. 따라서, 길이 LDPC 부호는 보다 큰 스토리지 공간을 필요로 한다. 또한, LDPC 부호 구현에서 핵심적인 난제는 디코더에서의 몇몇 처리 엔진(노드)들간에 연결 네트워크를 달성하는 방법에 관한 것이다. 게다가, 디코딩 프로세스에서 계산 로드, 특히 검사 노드 동작이 문제를 지니고 있다.
따라서, 간단한 인코딩 및 디코딩 프로세스를 적용하는 LDPC 통신 시스템에 대한 요구가 생기게 되었다. 또한, 더 복잡하게 하지 않고 높은 데이터 속도를 지원하기 위하여 LDPC 부호를 효율적으로 이용하는 요구가 생기게 되었다. 또한, LDPC 인코더 및 디코더의 성능을 개선할 필요가 생기게 되었다. 또한, LDPC 코딩을 구현하기 위한 스토리지 요구사항을 최소화할 필요가 생기게 되었다.
본 발명은 이들 및 다른 요구사항을 다루며, 또한 단 블록 길이의 저밀도 패리티 검사(LDPC) 부호를 인코딩하는 어프로치를 제공한다. 인코더는 LDPC 부호화 신호로서 전송을 위해 표 1-7 중 어느 하나에 따라 외부 Bose Chaudhuri Hocquenghem(BCH) 부호를 지니는 LDPC 부호를 생성한다. 표 1-7 각각은 패리티 비트 누산기(parity bit accumulator)의 어드레스를 지정한다. 패리티 검사 매트릭스의 일부분을 하위 삼각형으로 제한시키고/제한시키거나 디코더(305)의 비트 노드와 검사 노드 간의 통신을 간략화시킬 수 있는 다른 요건들을 만족시킴으로써 LDPC 부호가 구성된다. 또한, 순환 반복 검사(CRC) 인코더(209)가 제공되어 CRC 부호에 따른 입력 신호를 인코딩한다. 위의 어프로치는 스토리지 및 처리 리소스를 최소화하면서, 유익하게 LDPC 부호의 디코딩 뿐만 아니라 적절한 인코딩을 제공한다.
본 발명의 실시예의 또 다른 측면에 따르면, LDPC 부호는 8-PSK(Phase Shift Keying, 위상 시프팅 키잉), 16-QAM(Quadrature Amplitude Modulation, 직각 진폭 변조), QPSK(Quadrature Phase Shift Keying, 직각 위상 시프팅 키잉), 16-APSK(Amplitude Phase Shift Keying, 진폭 위상 시프팅 키잉), 및 32-APSK 중 하나를 포함하는 신호 컨스틸레이션(signal constellation)에 따라 피변조 신호에 의해 LDPC 부호가 표현된다.
본 발명의 실시예의 또 다른 측면에 따르면, 피변조 LDPC 부호화 신호는 광대역 위성 응용을 지원하는 위성 링크를 통해 전송된다.
본 발명의 실시예의 또 다른 측면에 따르면, BCH 외부 부호는 이하의 생성원 다항식(generator polynomial)에 기초한다:
Figure 112004040058443-pat00001
본 발명의 여전히 다른 측면, 특징 및 이점들은, 본 발명을 수행하기 위해 고려된 최선의 모드를 포함하는 많은 특정 실시예 및 구현을 단지 도시함으로써, 이하의 상세한 설명으로부터 명백할 것이다. 본 발명은 또한 기타 및 다른 실시예도 가능하며, 그 몇몇 세부사항은 본 발명의 정신 및 범위를 벗어나지 않고 각종 명백한 측면에서 수정될 수 있다. 따라서, 도면 및 설명은 본질적으로 도시적인 것이지, 제한적이지 않은 것으로 간주되어야 한다.
본 발명은 실례로서 도시되는 것으로 제한하고자 하는 것은 아니며, 첨부된 도면에서 도시되며, 첨부된 도면에서 유사한 참조 번호는 동일한 엘리먼트를 참조한다.
단 프레임 길이의 저밀도 패리티 검사(LDPC) 부호를 효과적으로 인코딩하는 시스템, 방법 및 소프트웨어가 설명된다. 이하의 설명에서, 설명을 위해, 본 발명의 철저한 이해를 제공하기 위해 많은 특정 상세사항이 설명될 것이다. 그러나, 본 발명이 이들 특정 상세사항 없이 또는 동등한 배열로 수행될 수 있다는 것이 당업자들에게 명백할 것이다. 다른 예에서, 불필요하게 본 발명을 애매하게 만드는 것을 피하기 위해 블록도 형태에서 잘 알려진 구조 및 장치들이 도시된다.
도 1은 본 발명의 실시예에 따라 저밀도 패리티 검사(LDPC) 부호를 활용하도록 구성된 통신 시스템의 도면이다. 디지털 통신 시스템(100)은 통신 채널(103)을 통해 수신기(105)로 신호 파형(signal waveforms)을 생성하는 송신기(101)를 포함한다. 이 이산 통신 시스템(100)에서, 송신기(101)는 가능한 메세지의 이산 세트를 생성하는 메세지 소스를 지니고 있다; 가능한 메세지 각각은 대응하는 신호 파형을 지닌다. 이들 신호 파형은 통신 채널(103)에 의해 약해지거나, 또는 변형된다. 잡음 채널(103)과 싸우기 위해, LDPC 부호가 활용된다.
실례로서, 채널(103)은 광대역 위성 응용을 지원하는 위성 터미널(예를 들어, 초소형 지구국(Very Small Aperture Terminals; VSATs))을 공급하는 위성 링크이다. 이러한 응용은 위성 방송 및 대화가능 서비스(interactive service)(및 디지털 비디오 방송(Digital Video Broadcast; DVB)과 호환되는 - S2 표준)를 포함한다. 위성(DVB-S) 표준을 통한 디지털 비디오 방송은 예를 들어, 디지털 위성 텔레비전 프로그래밍을 제공하기 위해 전세계에서 널리 적용되어오고 있다.
송신기(101)에 의해 생성된 LDPC 부호는 성능 손실 없이 고속 구현을 가능하게 한다. 송신기(101)로부터의 이들 구조화된 LDPC 부호 출력은 작은 수의 검사 노드를 변조 스킴(modulation scheme)(예를 들어, 8-PSK)에 의해 이미 채널 오류에 취약점이 있는 비트 노드로 할당하는 것을 피하게 해 준다.
이러한 LDPC 부호는 유익하게 덧셈, 비교 및 표 검색과 같이 간단한 연산을 포함하는 병렬 디코딩 알고리즘(parallelizable decodeing algorithm)(터보 부호와 달리)을 지닌다. 또한, 신중하게 설계된 LDPC 부호는 오류 층(error floor)의 어 떠한 징조도 보이지 않는다.
본 발명의 한 실시예에 따르면, 송신기(101)는 상대적으로 간단한 인코딩 기술을 사용하여 패리티 검사 매트릭스(디코딩동안 효율적인 메모리 액세스를 용이하게 함)에 기초한 LDPC 부호를 생성하여 수신기(105)와 통신한다. 송신기(101)는 만일 블록의 길이가 충분히 크다면, 연결된 터보+RS(Reed-Solomon) 부호의 성능을 능가할 수 있는 LDPC 부호를 적용한다.
도 2a 및 2b는 도 1의 송신기에 구현된 예시적인 LDPC 인코더의 도면이다. 도 2a에 도시된 바와 같이, 송신기(200)는 정보 소스(201)로부터 입력을 받아들이고 수신기(105)에서의 오류 정정 처리(error correction processing)에 적합한 상위 리던던시 부호화 스트림(coded stream of higher redundancy)을 출력하는 LDPC 인코더(203)를 갖추고 있다. 정보 소스(201)는 이산 알파벳 X로부터 k 신호를 생성한다. LDPC 부호는 패리티 검사 매트릭스로 지정된다. 한편, 인코딩 LDPC 부호는 일반적으로 생성원 매트릭스(generator matrices)를 지정할 필요가 있다. 가우스 소거법(Gaussian elimination)을 사용하여 패리티 검사 매트릭스로부터 생성원 매트릭스를 획득하는 것이 가능함에도 불구하고, 결과 매트릭스는 더 이상 희박하지(sparse) 않고 큰 생성원 매트릭스(large generator matrix)를 저장하는 것은 복잡할 수 있다.
인코더(203)는 패리티 검사 매트릭스상에 구조를 가함으로써 단지 패리티 검사 매트릭스만을 활용하는 간단한 인코딩 기술을 사용하여 알파벳 Y로부터 변조기(205)로 신호를 생성한다. 특히, 매트릭스의 일부 부분을 삼각형이 되도록 함으로 써 패리티 검사 매트릭스에 제한을 둘 수 있다. 이러한 패리티 검사 매트릭스의 구조는 이하의 도 6에 전부 설명되어 있다. 이러한 제한은 무시할 수 있는 성능 손실을 초래하고, 따라서 트레이드-오프(attractive trade-off)를 구성한다.
변조기(205)는 인코더(203)로부터의 인코딩된 메세지를 전송 안테나(207)로 전송된 신호 파형으로 매핑하고, 전송 안테나(207)는 통신 채널(103)을 통해 이 파형들을 방사한다. 따라서, 인코딩된 메세지는 변조되고 전송 안테나(207)로 분배된다. 전송 안테나(207)로부터의 전송은 이하에 설명된 대로 수신기로(도 3에 도시됨) 전파된다.
도 2b는 본 발명의 한 실시예에 따라, Bose Chaudhuri Hocquenghem(BCH) 인코더 및 순환 중복 검사(Cyclic Redundancy Check; CRC) 인코더로 활용된 LDPC 인코더를 보여준다. 이 시나리오에서, LDPC 인코더(203)에 의해 생성된 부호는 CRC 인코더(209) 및 BCH 인코더(211)와 함께, 연결된 외부 BCH 부호 및 내부 저밀도 패리티 검사(LDPC) 부호를 지닌다. 또한, 에러 검출이 CRC 부호를 사용하여 달성된다. CRC 인코더(209)는, 예시적인 실시예에서, 생성원 다항식
Figure 112004040058443-pat00002
을 갖는 8비트 부호를 사용하여 인코딩한다. CRC 부호는 BCH 인코더(211)로 출력된다.
도 2c는 본 발명의 한 실시예에 따라, 단 프레임 길이의 LDPC 부호를 생성하는 도 2b의 LDPC 인코더의 인코딩 프로세스 흐름도를 제공한다. 단계(221)에서, 정보 비트가 수신되고 인코더(209,211 및 203)의 회로로 처리된다. 그 결과, LDPC 인코더(203)는 단계(223)와 같이, 수신된 정보 비트에 기초하여 외부 BCH 부호로 LDPC 부호를 생성한다. 부호는 또한 CRC 부호를 포함한다. 그 다음, LDPC 부호는 단계(225)를 통해, 예시적인 실시예에서 하나 이상의 위성 단자로의 위성 링크(단계 227)인 채널(103)을 통한 전송을 위해 피변조 신호에 의해 표현된다.
LDPC 인코더(203)는 규칙적으로 크기 kldpc ,
Figure 112004040058443-pat00003
의 정보 블록을 크기 nldpc ,
Figure 112004040058443-pat00004
의 부호워드(codeword)로 인코딩한다. 부호워드의 전송은 io 에서부터 주어진 순서대로 시작되고, Pnldpc - kldpc - 1 , LDPC 부호 매개변수 (nldpc , kldpc )로 종료된다.
LDPC 인코더(203)의 태스크는 kldpc 정보 비트,
Figure 112004040058443-pat00005
의 모든 블록에 대해 nldpc - kldpc 패리티 비트
Figure 112004040058443-pat00006
를 결정하는 것이다. 프로시져는 이하와 같다. 먼저, 패리티 비트가 초기화된다;
Figure 112004040058443-pat00007
. 제1 정보 비트, io 는 표 1-7의 제1 행에 지정된 패리티 비트 어드레스에서 누산된다. 실례로서, kldpc 비트는 규칙적으로 인코딩되어 nldpc 를 생성한다. 본 발명의 한 실시예에 따르면, nldpc 는 16200 비트이고, 이것은 단 블록 길이이다. 이러한 상대적으로 단 길이의 부호가 주어지면, 대략 16200 비트의 길이 또는 그보다 작은 길이를 지니는 LDPC 부호는 "단(short)" 블록 길이의 부호로 간주된다. 본 발명의 한 실시예에 따르면, 단 프레임 길이의 부호의 매개변수가 표 8에 제공된다.
모든 정보 비트를 다 써버린 후, 최종 패리티 비트가 이하와 같이 획득된다. 먼저, i=1로 시작하여 이하의 연산이 수행된다.
Figure 112004040058443-pat00008
pi, i = 0,1,..., nldpc - kldpc - 1 의 최종 내용은 패리티 비트 p1 과 동일하다.
Figure 112004040058443-pat00009
Figure 112004040058443-pat00010
Figure 112004040058443-pat00011
Figure 112004040058443-pat00012
Figure 112004040058443-pat00013
Figure 112004040058443-pat00014
Figure 112004040058443-pat00015
표 8-10은 다른 예시적인 부호 속도, 16200 비트의 nldpc 에 대해 1/3, 1/5, 및 2/5 를 제공한다.
Figure 112004040058443-pat00016
Figure 112004040058443-pat00017
Figure 112004040058443-pat00018
모든 정보 비트를 다 써버린 후, 최종 패리티 비트가 이하와 같이 획득된다. 먼저, i=1로 시작하여 이하의 연산이 수행된다.
Figure 112004040058443-pat00019
pi, i = 0,1,..., nldpc - kldpc - 1 의 최종 내용은 패리티 비트 p1 과 동일하다.
BCH 인코더(211)에 대해, nldpc 가 16200과 동일하게 BCH 부호 매개변수가 표 11에 나열되어 있다.
BCH 인코더(211)에 의해 활용되는 BCH 부호의 생성원 다항식은 이하와 같다:
Figure 112004040058443-pat00021
정보 비트
Figure 112004040058443-pat00022
을 부호워드
Figure 112004040058443-pat00023
로 BCH 인코딩하는 것은 이하와 같이 달성된다. 메세지 다항식
Figure 112004040058443-pat00024
에 xnbch - kbch 를 곱한다. 다음, xnbch - kbch m(x)를 g(x)로 나눈다.
Figure 112004040058443-pat00025
를 나머지로 하여, 부호워드 다항식은 이하와 같이 설정된다:
Figure 112004040058443-pat00026
.
상술된 대로, LDPC 부호는 예시적인 실시예에서, MPEG(Motion Pictures Expert Group) 패킷 전송과 같은 각종 디지털 비디오 응용에 사용될 수 있다.
도 3은 도 1 시스템의 예시적인 수신기 도면이다. 수신측에서, 수신기(300)는 전송기(200)로부터 수신된 신호를 복조하는 복조기(301)를 포함한다. 이들 신호는 복조를 위해 수신 안테나(303)에서 수신된다. 복조 후, 수신된 신호는 인코더(305)로 전달되고, 인코더는 비트 매트릭 생성원(307)과 함께 메세지 X'를 생성함으로써 최초 소스 메세지 재구성을 시도한다. 비트 매트릭 생성원(307)은 디코딩 프로세스동안 이리저리(반복적으로) 디코더(305)와 정보를 교환할 수 있다. 이 디코더 어프로치는 제목이 "저밀도 패리티 검사(LDPC) 디코더에서 라우팅하는 방법 및 시스템(Method and System for Routing in Low Density Parity Check Decoders)"이고, 2003년 7월 3일 출원된 동시계속출원(Serial No. 10/613,824; Attorney Docket PD-203009)에 전부 설명되어 있으며, 그 전체 내용이 본 명세서에 참조된다. 본 발명에 의해 제공되는 이점을 이해하기 위해, 도 4에 설명된 LDPC 부호가 생성되는 방법을 알아보는 것이 유익할 것이다.
도 4는 본 발명의 실시예에 따른 스파스 패리티 검사 행렬의 도면이다. LDPC 부호는 스파스 패리티 검사 매트릭스 H(n-k)xn 이 있는 긴, 선형 블록 부호이다. 일반적으로 블록 길이 n은 그 범위가 수 천에서 수 만비트이다. 예를 들어, 길이 n=8 이고 속도 1/2인 LDPC 부호에 대한 패리티 검사 매트릭스가 도 4에 도시되어 있다. 동일한 부호를 동등하게 도 5를 통해 이분 그래프에 의해 나타낼 수 있다.
도 5는 도 4 매트릭스의 LDPC 부호의 이분 그래프 도면이다. 패리티 검사 방정식은 각 검사 노드에 대해, 모든 인접하는 비트 노드의 합(GF(Galois Field)(2)를 통해)이 0이라는 것을 의미한다. 도면에서 보여지는 바와 같이, 비트 노드는 그래프의 왼쪽 면을 차지하고 미리 결정된 관계에 의해 하나 이상의 검사 노드와 관련되어 있다. 예를 들어, 검사 노드 mi 에 대응하여, 비트 노드에 관해 n1 + n4 + n5 + n8 = 0 이라는 이하의 표현이 존재한다.
수신기(303)로 다시 돌아와서, LDPC 디코더(305)는 메세지 통과 디코더로 간주되고, 그것에 의해 디코더(305)는 비트 노드의 값을 찾는 것을 목적으로 한다. 이 태스크를 수행하기 위해, 비트 노드 및 검사 노드는 반복적으로 서로 통신한다. 이 통신의 본질이 이하에 설명되어 있다.
검사 노드에서 비트 노드까지, 각 검사 노드는 다른 인접 비트 노드로부터 온 정보에 기초하여 그 비트 노드의 값에 관한 추정("의견")을 인접 비트 노드에 제공한다. 예를 들어, 위의 예제에서 n4, n5, n8 의 합이 m 1에게 0처럼 보인다면, n1 에게 n1 의 값이 0일 것으로 생각된다(n1 + n4 + n5 + n8 = 0 이기 때문)는 것을 표시한다; 그렇지 않을 경우 m1 은 n1 에게 n1 의 값이 1일 것으로 생각된다는 것을 표시한다. 또한, 연판정 디코딩(soft decision decoding)에 대해, 신뢰성 측정이 추가된다.
비트 노드에서 검사 노드까지, 각 비트 노드는 다른 인접 검사 노드로부터 온 피드백에 기초하여 그 자체의 값에 대한 추정을 인접 검사 노드에 중계한다. 위의 예제에서, n1 은 단지 2개의 인접 검사 노드 m1 및 m3 을 지니고 있다. m3 으로부터의 피드백이 n1 에게 n1 의 값이 아마 0일 것이라는 것을 표시한다면, n1 은 n1 자기 자신의 값의 추정이 0이라는 것을 m1 에게 통보할 것이다. 비트 노드가 2개 이상의 인접 검사 노드를 지니는 이러한 경우에 대해, 비트 노드는 그 결정을 자신이 통신하는 검사 노드에게 보고하기 전에 다른 인접 검사 노드로부터 온 피드백에 다수결(연판정)을 수행한다. 위의 프로세스는 모든 비트 노드가 옳다고 간주될 때까지(즉, 모든 패리티 검사 방정식이 만족될 때까지) 또는 미리 결정된 최대 반복 수에 도달할 때까지 반복되며, 이것에 의해서 디코딩 실패가 선언된다.
도 6은 스파스 패리티 검사 매트릭스의 서브 매트릭스 도면이고, 여기서 서브 매트릭스는 본 발명의 한 실시예에 따라 하위 삼각형 영역에 제한된 패리티 검사 값을 포함한다. 이전에 설명되었듯이, (도 2a 및 도 2b의) 인코더(203)는 패리티 검사 매트릭스의 하위 삼각형 영역의 값을 제한함으로써 간단한 인코딩 기술을 적용할 수 있다. 본 발명의 실시예에 따라, 패리티 검사 매트릭스에 가해진 제한은 다음의 형태이다:
Figure 112004040058443-pat00027
여기서, B는 하위 삼각형이다.
임의의 정보 블록
Figure 112004040058443-pat00028
는
Figure 112004040058443-pat00029
를 사용하여 부호워드
Figure 112004040058443-pat00030
로 인코딩되고, 반복적으로 패리티 비트를 해결한다; 예를 들어, 아래와 같고,
Figure 112004040058443-pat00031
에 대해서도 유사하다.
Figure 112004040058443-pat00032
도 7는 본 발명에 따른 실시예가 수행되는 컴퓨터 시스템을 나타낸다. 컴퓨터 시스템(700)은 정보를 교환하기 위한 버스(701) 또는 기타 통신 메카니즘, 및 정보를 처리하기 위하여 버스(701)와 결합되는 프로세서(703)를 포함한다. 컴퓨터 시스템(700)은 또한 프로세서(703)에 의해 실행되는 명령어들과 정보를 저장하기 위하여 버스(701)에 결합되는, RAM 또는 기타 동적 스토리지 장치와 같은 주 메모리(705)를 포함한다. 주 메모리(705)는 또한 프로세서(703)에 의해 실행되는 명령 의 실행 중에 임시 변수 또는 기타 중간 정보를 저장하는 데 사용될 수 있다. 컴퓨터 시스템(700)은 또한 프로세서(703)에 대한 명령어들과 정적 정보를 저장하기 위하여 버스(701)에 결합되는 ROM(707) 또는 기타 정적 스토리지 장치를 더 포함한다. 광 디스크 또는 자기 디스크와 같은 스토리지 장치(709)는 정보 및 명령어들을 저장하기 위하여 추가로 버스(701)에 결합된다.
컴퓨터 시스템(700)은 버스(701)를 통하여 음극선관(CRT), 액정 디스플레이 장치, 능동매트릭스형 디스플레이 장치, 또는 플라즈마 디스플레이 장치와 같이 정보를 컴퓨터 사용자에게 디스플레이하기 위한 디스플레이(711)에 결합될 수 있다. 문자숫자키 및 기타 키들을 포함하는 키보드와 같은 입력장치(713)는 프로세서(703)로의 명령 선택 및 정보의 통신을 위하여 버스(701)에 결합된다. 다른 유형의 사용자 입력장치로서, 프로세서(703)로의 명령을 선택하고, 방향정보를 통신하며, 디스플레이(711)의 커서 움직임을 제어하기 위한 마우스, 트랙볼, 또는 커서 방향키와 같은 커서 제어기(715)가 있다.
본 발명의 실시예에 따르면, 주 메모리(705)내에 포함된 명령어들의 배치를 실행하는 프로세서(703)에 응답하여 컴퓨터 시스템(700)에 의해 LDPC 부호의 생성이 제공된다. 이러한 명령어들은 스토리지 장치(709)와 같은 기타의 컴퓨터 판독가능 매체로부터 주 메모리(705)로 판독될 수 있다. 주 메모리(705)내에 포함된 일련의 명령어의 실행은 프로세서(703)가 본 명세서에서 설명하는 프로세스 단계들을 수행하도록 한다. 멀티프로세싱 배치에서 또한 하나 이상의 프로세서들은 주 메모리(705)내에 포함된 명령어들을 실행하도록 적용될 수 있다. 대체 실시예로 서, 본 발명에 따른 실시예를 구현하기 위하여 소프트웨어 명령어 대신에 또는 이와 함께 하드 와이어드 회로(hard-wired circuitry)가 사용될 수 있다. 따라서, 본 발명의 실시예들은 하드웨어 회로 및 소프트웨어의 임의의 특정한 조합에 제한되지 않는다.
컴퓨터 시스템(700)은 또한 버스(701)에 결합되는 통신 인터페이스(717)를 포함한다. 통신 인터페이스(717)는 로컬 네트워크(721)에 접속된 네트워크 링크(719)로 2-웨이(two-way) 데이터통신 결합을 제공한다. 예를 들어, 통신 인터페이스(717)는 해당 유형의 전화선으로의 데이터통신 접속을 제공하기 위해 디지털 가입자 회선(digital subscriber line; DSL) 카드 또는 모뎀, 통합 서비스 디지털 네트워크(integrated services digital network; ISDN) 카드, 케이블 모뎀, 또는 전화모뎀 일 수 있다. 다른 예로서, 통신 인터페이스(717)는 호환가능한 LAN으로의 데이터 통신 접속을 제공하는 LAN 카드(예를 들어, EthernetTM 또는 비동기 전송 모델(Asyncronous Transfer Model; ATM) 네트워크) 일 수 있다. 무선 링크 또한 구현될 수 있다. 이러한 구현예에 있어서, 통신 인터페이스(717)는 다양한 형태의 정보를 나타내는 디지털 데이터 스트림을 운반하는 전기적, 전자기적, 광학적 신호들을 송수신한다. 또한, 통신 인터페이스(717)는 USB 인터페이스, PCMCIA 인터페이스 등의 주변 인터페이스 장치를 포함할 수 있다.
네트워크 링크(719)는 일반적으로 하나 이상의 네트워크를 통해 다른 데이터 장치로 데이터 통신을 제공한다. 예를 들어, 네트워크 링크(719)는 로컬 네트워크 (721)를 통해 호스트 컴퓨터(723)로의 접속을 제공하며, 호스트 컴퓨터(723)는 네트워크(725)(예컨대, 광대역 네트워크(WAN) 또는 현재 "Internet"으로 통상 불리우는 글로벌 패킷 데이터통신 네트워크)로 또는 서비스 제공자에 의해 동작되는 데이터 장비로의 접속을 갖는다. 로컬 네트워크(721) 및 네트워크(725) 모두 정보와 명령어들을 운반하기 위하여 전기적, 전자기적, 또는 광학적 신호를 사용한다. 각종 네트워크를 통한 신호들 및 네트워크 링크(719)상과 디지털 데이터를 컴퓨터 시스템(700)과 통신하는 통신 인터페이스(717)를 통과한 신호들은 정보와 명령어들을 담고 있는 반송파의 예시적인 형태들이다.
컴퓨터 시스템(700)은 네트워크, 네트워크 링크(719), 및 통신 인터페이스(717)를 통해 프로그램 코드를 포함하는 메세지를 전송하고 데이터를 수신할 수 있다. 인터넷의 예에서, 서버(도시 생략)는 본 발명의 실시예를 구현하기 위한 애플리케이션 프로그램에 속하는 요청 코드들을 네트워크(725), 로컬 네트워크(721), 및 통신 인터페이스(717)를 통하여 전송할 수 있다. 프로세서(703)는 수신하는 동안 전송된 코드를 실행하고, 및/또는 추후의 실행을 위하여 코드를 스토리지 장치치(709) 또는 기타 불휘발성 스토리지 장치에 저장할 수 있다. 이와 같이, 컴퓨터 시스템(700)은 반송파 형태로 애플리케이션 코드를 획득할 수 있다.
본 명세서에서 사용되는 "컴퓨터 판독가능 매체"라는 용어는 실행을 위하여 프로세서(703)로 명령어를 제공하는데 참여하는 임의의 매체를 말한다. 이러한 매체는 많은 형태를 취할 수 있는데, 불휘발성 매체, 휘발성 매체, 및 전송 매체를 포함하되, 이에 제한되지 않는다. 불휘발성 매체는 예를 들어 스토리지 장치(709) 와 같은 광 디스크 또는 자기 디스크를 포함한다. 휘발성 매체는 주 메모리(705)와 같은 동적 메모리를 포함한다. 전송 매체는 무선 주파수(RF) 및 적외선(IR) 데이터 통신 중에 발생되는 것과 같은, 음파적, 광학적, 또는 전자기적 파형의 형태를 또한 취할 수 있다. 컴퓨터 판독가능 매체의 공통적인 형태로는 예를 들어 플로피 디스크, 플렉시블(flexible) 디스크, 하드 디스크, 자기 테이프, 기타 자기 매체, CD-ROM, CDRW, DVD, 기타 광학 매체, 펀치 카드, 종이 테이프, 광학적 마크시트(mark sheet), 기타 홀의 패턴 또는 기타 광학적으로 인식가능한 표식을 갖는 물리적 매체, RAM, PROM, EPROM, FLASH-PROM, 기타 메모리 칩 또는 카트리지, 반송파, 또는 기타 컴퓨터가 판독할 수 있는 매체들을 포함한다.
실행을 위하여 명령어를 프로세서로 제공하기 위하여 각종 형태의 컴퓨터 판독가능 매체가 포함될 수 있다. 예컨대, 본 발명의 적어도 일부를 실행하기 위한 명령어들이 초기에는 원격 컴퓨터의 자기디스크에 포함된다. 이러한 시나리오에서는, 원격 컴퓨터가 명령어들을 주 메모리로 로드하고, 명령어들을 모뎀을 사용하는 전화선을 통해 전송한다. 로컬 컴퓨터 시스템의 모뎀은 전화선상의 데이터를 수신하고, 데이터를 적외선 신호로 변환하여 적외선 신호를 PDA 및 랩톱 컴퓨터와 같은 휴대용 컴퓨팅 장치로 전송하는 적외선 전송기를 사용한다. 휴대용 컴퓨터 장치의 적외선 검출기는 적외선 신호에 포함된 정보와 명령어들을 수신하고, 그 데이터를 버스상에 위치시킨다. 버스는 그 데이터를 주 메모리로 운반하며, 프로세서는 주 메모리로부터 명령어들을 검색하고 실행한다. 주 메모리에서 수신된 명령어들은 선택적으로 프로세서의 실행 전후에 스토리지 장치상에 저장될 수 있다.
따라서, 본 발명의 각종 실시예는 단 블록 길이의 저밀도 패리티 검사(LDPC) 부호를 인코딩하는 어프로치를 제공한다. 인코더는 LDPC 부호화 신호로서 전송을 위해 표 1-10 중 어느 하나에 따라 외부 Bose Chaudhuri Hocquenghem(BCH) 부호를 지니는 LDPC 부호를 생성한다. 표 1-10 각각은 패리티 비트 누산기의 어드레스를 지정한다. 패리티 검사 매트릭스의 일부분을 하위 삼각형으로 제한시키고/제한시키거나 디코더의 비트 노드와 검사 노드 간의 통신을 간략화시킬 수 있는 다른 요건들을 만족시킴으로써 LDPC 부호가 구성된다. 또한, 순환 반복 검사(CRC) 인코더가 제공되어 CRC 부호에 따른 입력 신호를 인코딩한다. 위의 어프로치는 유익하게 성능 손해 없이 복잡성을 감소시킨다.
본 발명이 많은 실시예와 구현과 함께 설명되었지만, 본 발명은 제한되지 않고 각종 명백한 수정 및 동등한 배열을 포함하고, 이것은 첨부된 청구항의 범위에 포함된다.
패리티 검사 매트릭스의 일부분을 하위 삼각형으로 제한시키고/제한시키거나 디코더의 비트 노드와 검사 노드 간의 통신을 간략화시킬 수 있는 다른 요건들을 만족시킴으로써 LDPC 부호가 구성된다. 또한, 순환 반복 검사(CRC) 인코더가 제공되어 CRC 부호에 따른 입력 신호를 인코딩한다. 이 어프로치를 통해 유익하게 성능 손해 없이 복잡성을 감소시킬 수 있다.

Claims (16)

  1. 저밀도 패리티 검사(Low Density Parity Check; LDPC) 부호화 신호의 전송을 지원하기 위한 방법에 있어서,
    정보 비트를 수신하는 단계와,
    상기 정보 비트에 기초하여, 후술되는 표 1 내지 10 중 하나에 따른 LDPC 부호를 생성하여 상기 LDPC 부호화 신호로서 전송하는 단계
    를 포함하며, 상기 표 1 내지 10의 각 행은 상기 정보 비트의 그룹이 누산되는 패리티 비트들의 어드레스를 추출하는데 사용되고, 상기 패리티 비트들은 각각의 행으로부터 추출된 상기 어드레스들에 누산된 상기 정보 비트들의 상기 그룹으로부터 추출되는 방법으로서,
    후술되는 표 1 내지 10으로서는,
    [표 1]
    Figure 112006054516708-pat00033
    [표 2]
    Figure 112006054516708-pat00034
    [표 3]
    Figure 112006054516708-pat00035
    [표 4]
    Figure 112006054516708-pat00036
    [표 5]
    Figure 112006054516708-pat00037
    [표 6]
    Figure 112006054516708-pat00038
    [표 7]
    Figure 112006054516708-pat00039
    [표 8]
    Figure 112006054516708-pat00040
    [표 9]
    Figure 112006054516708-pat00041
    [표 10]
    Figure 112006054516708-pat00042
    이 포함되는 방법.
  2. 제1항에 있어서,
    Figure 112004040058443-pat00043
    의 생성원 다항식(generator polynomial)에 기초하여 BCH(Bose Chaudhuri Hocquenghem) 외부 부호를 사용하는 방법.
  3. 제1항에 있어서,
    상기 LDPC 부호화 신호를 변조하는 단계와,
    상기 피변조 신호를 전송하는 단계를 더 포함하는 방법.
  4. 제3항에 있어서,
    상기 피변조 신호는 광대역 위성 응용을 지원하는 위성 링크(103)를 통해 전송되는 방법.
  5. 제3항에 있어서,
    상기 변조 단계는 8-PSK(위상 시프팅 키잉), 16-QAM(직각 진폭 변조), QPSK(직각 위상 시프팅 키잉), 16-APSK(진폭 위상 시프팅 키잉), 및 32-APSK 중 하나를 포함하는 신호 컨스틸레이션에 따라 수행되는 방법.
  6. 저밀도 패리티 검사(Low Density Parity Check; LPDC) 부호화 신호의 전송을 지원하기 위한 명령어들을 포함하는 컴퓨터 판독가능 매체로서, 상기 명령어는 실행 시에 구성되어 하나 이상의 프로세서로 하여금 제1항 기재의 방법을 수행하도록 하게 하는 컴퓨터 판독가능 매체.
  7. 저밀도 패리티 검사(Low Density Parity Check; LPDC) 부호화 신호의 전송을 지원하기 위한 인코더로서,
    정보 비트를 수신하기 위한 수단과,
    상기 정보 비트에 기초하여, 후술되는 표 1 내지 10 중 하나에 따른 LDPC 부호를 생성하여 상기 LDPC 부호화 신호로서 전송하기 위한 수단
    을 포함하며, 상기 표 1 내지 10의 각 행은 상기 정보 비트의 그룹이 누산되는 패리티 비트들의 어드레스를 추출하는데 사용되고, 상기 패리티 비트들은 각각의 행으로부터 추출된 상기 어드레스들에 누산된 상기 정보 비트들의 상기 그룹으로부터 추출되는 인코더로서,
    후술되는 표 1 내지 10으로서는,
    [표 1]
    Figure 112006054516708-pat00044
    [표 2]
    Figure 112006054516708-pat00045
    [표 4]
    Figure 112006054516708-pat00046
    [표 5]
    Figure 112006054516708-pat00047
    [표 6]
    Figure 112006054516708-pat00048
    [표 7]
    Figure 112006054516708-pat00049
    [표 8]
    Figure 112006054516708-pat00050
    [표 9]
    Figure 112006054516708-pat00051
    [표 10]
    Figure 112006054516708-pat00052
    이 포함되는 인코더(203).
  8. 제7항에 있어서,
    BCH(Bose Chaudhuri Hocquenghem) 외부 부호가
    Figure 112004040058443-pat00053
    의 생성원 다항식에 기초하는 인코더(203, 211).
  9. 제7항에 있어서,
    상기 LDPC 부호화 신호를 변조하기 위한 수단과,
    상기 피변조 신호를 전송하기 위한 수단을 더 포함하는 인코더(203, 211).
  10. 제9항에 있어서,
    상기 피변조 신호는 광대역 위성 응용을 지원하는 위성 링크(103)를 통해 전송되는 인코더(203, 211).
  11. 9항에 있어서,
    상기 변조 수단은 8-PSK(위상 시프팅 키잉), 16-QAM(직각 진폭 변조), QPSK(직각 위상 시프팅 키잉), 16-APSK(진폭 위상 시프팅 키잉), 및 32-APSK 중 하나를 포함하는 신호 컨스틸레이션에 따라 수행되는 인코더(203, 211).
  12. 저밀도 패리티 검사(Low Density Parity Check; LPDC) 부호화 신호의 전송을 지원하기 위한 송신기로서,
    정보 비트를 수신하도록 구성된 BCH(Bose Chaudhuri Hocquenghem) 인코더(211)와,
    상기 BCH 인코더(211)에 결합되고 상기 정보 비트에 기초하여, 아래 표 1 내지 10 중 하나에 따른 외부 BCH 부호를 포함하여 상기 LPDC 부호화 신호로서 전송하기 위한 LDPC 부호를 출력시키는 LDPC 인코더(203)
    를 포함하며, 상기 표 1 내지 10의 각 행은 상기 정보 비트의 그룹이 누산되는 패리티 비트들의 어드레스를 추출하는데 사용되고, 상기 패리티 비트들은 각각의 행으로부터 추출된 상기 어드레스들에 누산된 상기 정보 비트들의 상기 그룹으로부터 추출되는 송신기로서,
    후술되는 표 1 내지 10으로서는,
    [표 1]
    Figure 112006054516708-pat00054
    [표 2]
    Figure 112006054516708-pat00055
    [표 3]
    Figure 112006054516708-pat00056
    [표 4]
    Figure 112006054516708-pat00057
    [표 5]
    Figure 112006054516708-pat00058
    [표 6]
    Figure 112006054516708-pat00059
    [표 7]
    Figure 112006054516708-pat00060
    [표 8]
    Figure 112006054516708-pat00061
    [표 9]
    Figure 112006054516708-pat00062
    [표 10]
    Figure 112006054516708-pat00063
    이 포함되는 송신기(200).
  13. 제12항에 있어서,
    상기 BCH 외부 부호는
    Figure 112004040058443-pat00064
    의 생성원 다항식에 기초하는 송신기(200).
  14. 제12항에 있어서,
    상기 LDPC 부호화 신호를 변조하도록 구성된 변조기(205)를 더 포함하는 송신기(200).
  15. 제14항에 있어서,
    상기 피변조 신호는 광대역 위성 응용을 지원하는 위성 링크(103)를 통해 전송되는 송신기(200).
  16. 제14항에 있어서,
    상기 변조기는 8-PSK(위상 시프팅 키잉), 16-QAM(직각 진폭 변조), QPSK(직각 위상 시프팅 키잉), 16-APSK(진폭 위상 시프팅 키잉), 및 32-APSK 중 하나를 포함하는 신호 컨스틸레이션에 따라 수행되는 송신기(200).
KR1020040070418A 2003-09-04 2004-09-03 저밀도 패리티 검사 부호화 신호의 전송을 지원하는 방법,인코더 및 송신기 Expired - Lifetime KR100683084B1 (ko)

Applications Claiming Priority (6)

Application Number Priority Date Filing Date Title
US50010903P 2003-09-04 2003-09-04
US60/500,109 2003-09-04
US50591603P 2003-09-25 2003-09-25
US60/505,916 2003-09-25
US51819903P 2003-11-07 2003-11-07
US60/518,199 2003-11-07

Publications (2)

Publication Number Publication Date
KR20050025075A KR20050025075A (ko) 2005-03-11
KR100683084B1 true KR100683084B1 (ko) 2007-02-15

Family

ID=34139650

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020040070418A Expired - Lifetime KR100683084B1 (ko) 2003-09-04 2004-09-03 저밀도 패리티 검사 부호화 신호의 전송을 지원하는 방법,인코더 및 송신기

Country Status (6)

Country Link
US (4) US7237174B2 (ko)
EP (2) EP1513259A3 (ko)
JP (1) JP3936354B2 (ko)
KR (1) KR100683084B1 (ko)
CN (1) CN1612486A (ko)
CA (2) CA2685463C (ko)

Families Citing this family (53)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7864869B2 (en) 2002-07-26 2011-01-04 Dtvg Licensing, Inc. Satellite communication system utilizing low density parity check codes
GB2454195A (en) * 2007-10-30 2009-05-06 Sony Corp Address generation polynomial and permutation matrix for DVB-T2 16k OFDM sub-carrier mode interleaver
CN101341659B (zh) * 2004-08-13 2012-12-12 Dtvg许可公司 用于多输入多输出通道的低密度奇偶校验码的码设计与实现的改进
JP4551740B2 (ja) * 2004-11-08 2010-09-29 株式会社東芝 低密度パリティチェック符号復号器及び方法
JP2007288721A (ja) * 2006-04-20 2007-11-01 Mitsubishi Electric Corp 通信装置および誤り検出方法
US8230299B2 (en) 2006-09-18 2012-07-24 Availink, Inc. Interleaving scheme for an LDPC coded QPSK/8PSK system
US8369448B2 (en) * 2006-09-18 2013-02-05 Availink, Inc. Bit mapping scheme for an LDPC coded 32APSK system
US8689092B2 (en) 2006-09-18 2014-04-01 Availink, Inc. Family of LDPC codes for video broadcasting applications
US20100316144A1 (en) * 2006-09-18 2010-12-16 Availink, Inc. Efficient framing schemes for supporting vcm/acm in digital satellite transmission systems
WO2008034287A1 (en) 2006-09-18 2008-03-27 Juntan Zhang An interleaving scheme for an ldpc coded 32apsk system
US8630223B2 (en) * 2006-09-18 2014-01-14 Availink, Inc. Efficient frame structure for digital satellite communication
US20110173509A1 (en) * 2006-09-18 2011-07-14 Availink, Inc. Bit mapping scheme for an ldpc coded 16apsk system
KR101279283B1 (ko) * 2006-10-19 2013-06-26 조지아 테크 리서치 코오포레이션 블록 부호를 사용하는 통신 시스템에서 신호 송수신 장치및 방법
US20100122143A1 (en) 2007-03-27 2010-05-13 Hughes Network Systems, Llc Method and system for providing low density parity check (ldpc) coding for scrambled coded multiple access (scma)
CN101364809B (zh) * 2007-08-06 2011-09-07 美国博通公司 解码器
WO2009067181A2 (en) * 2007-11-16 2009-05-28 Broadcom Corporation Low density parity check (ldpc) encoded higher order modulation
CN100583653C (zh) * 2008-01-11 2010-01-20 北京大学 一种ldpc级联码的编码方法、译码方法及其译码器
KR100937430B1 (ko) * 2008-01-25 2010-01-18 엘지전자 주식회사 신호 송수신 방법 및 신호 송수신 장치
US8291282B2 (en) 2008-02-18 2012-10-16 Samsung Electronics Co., Ltd Apparatus and method for encoding and decoding channel in a communication system using low-density parity-check codes
CN101242188B (zh) * 2008-03-10 2011-05-11 清华大学 基于哈密尔顿图的低密度奇偶校验码的纠错编码方法
US8392786B2 (en) * 2008-05-07 2013-03-05 Broadcom Corporation LDPC coding systems for 60 GHz millimeter wave based physical layer extension
US8370711B2 (en) 2008-06-23 2013-02-05 Ramot At Tel Aviv University Ltd. Interruption criteria for block decoding
US20100162078A1 (en) * 2009-03-04 2010-06-24 Comtech Ef Data Corp. Telecommunication system and related methods
US8464123B2 (en) * 2009-05-07 2013-06-11 Ramot At Tel Aviv University Ltd. Matrix structure for block encoding
CN101902228B (zh) * 2009-05-25 2012-11-28 中兴通讯股份有限公司 快速循环冗余校验编码方法及装置
CN102460977A (zh) 2009-05-27 2012-05-16 诺沃尔赛特有限公司 具有迭代调度的ldpc码迭代解码
JP2011065599A (ja) * 2009-09-18 2011-03-31 Toshiba Corp メモリシステムおよびメモリシステムの制御方法
TWI415396B (zh) * 2009-11-23 2013-11-11 Nat Univ Tsing Hua 適用於根據里德-索羅門碼建立之低密度同位檢查碼的解碼器及解碼方法
US8402341B2 (en) * 2010-02-18 2013-03-19 Mustafa Eroz Method and system for providing low density parity check (LDPC) encoding and decoding
US8782489B2 (en) 2010-02-18 2014-07-15 Hughes Network Systems, Llc Method and system for providing Low Density Parity Check (LDPC) encoding and decoding
JP5601182B2 (ja) * 2010-12-07 2014-10-08 ソニー株式会社 データ処理装置、及びデータ処理方法
JP5637393B2 (ja) * 2011-04-28 2014-12-10 ソニー株式会社 データ処理装置、及び、データ処理方法
US8832524B2 (en) 2011-09-22 2014-09-09 Violin Memory, Inc. System and method for correcting errors in data using a compound code
US8972834B2 (en) 2012-08-28 2015-03-03 Hughes Network Systems, Llc System and method for communicating with low density parity check codes
US9264182B2 (en) 2012-09-13 2016-02-16 Novelsat Ltd. Iterative receiver loop
US9294131B2 (en) 2013-02-10 2016-03-22 Hughes Network Systems, Llc Apparatus and method for improved modulation and coding schemes for broadband satellite communications systems
US8887024B2 (en) 2013-02-10 2014-11-11 Hughes Network Systems, Llc Apparatus and method for improved modulation and coding schemes for broadband satellite communications systems
US9246634B2 (en) 2013-02-10 2016-01-26 Hughes Network Systems, Llc Apparatus and method for improved modulation and coding schemes for broadband satellite communications systems
WO2014145217A1 (en) 2013-03-15 2014-09-18 Hughes Network Systems, Llc Low density parity check (ldpc) encoding and decoding for small terminal applications
KR20150005853A (ko) 2013-07-05 2015-01-15 삼성전자주식회사 송신 장치 및 그의 신호 처리 방법
KR102002559B1 (ko) 2013-07-05 2019-07-22 삼성전자주식회사 송신 장치 및 그의 신호 처리 방법
EP2858249A1 (en) * 2013-10-07 2015-04-08 Electronics and Telecommunications Research Institute Low density parity check encoder
US9490846B2 (en) * 2014-08-14 2016-11-08 Electronics And Telecommunications Research Institute Low density parity check encoder having length of 16200 and code rate of 3/15, and low density parity check encoding method using the same
CN106856569B (zh) * 2015-12-09 2020-04-14 扬智科技股份有限公司 解码器、接收装置及其解码方法
CN105846953A (zh) * 2016-03-15 2016-08-10 雷欧尼斯（北京）信息技术有限公司 数字电影数据包传输方法及装置
CN106569906B (zh) * 2016-10-20 2019-12-31 北京航空航天大学 基于稀疏矩阵的编码写入方法及装置
JP6564964B2 (ja) * 2017-03-13 2019-08-21 ソニーセミコンダクタソリューションズ株式会社 送信装置及び送信方法、受信装置及び受信方法、並びに、プログラム
CN111066251B (zh) * 2017-08-18 2024-09-06 上海诺基亚贝尔股份有限公司 用于nr的ldpc基础图的使用
EP4220967A1 (en) * 2017-09-27 2023-08-02 Mitsubishi Electric Corporation Coding device and transmitter
US11016844B2 (en) * 2019-03-15 2021-05-25 Toshiba Memory Corporation Error correction code structure
CN109935263B (zh) * 2019-03-27 2021-06-04 翰顺联电子科技(南京)有限公司 非易失性存储器的编译码方法及存储系统
US11223372B2 (en) 2019-11-27 2022-01-11 Hughes Network Systems, Llc Communication throughput despite periodic blockages
US11838127B2 (en) 2022-03-11 2023-12-05 Hughes Network Systems, Llc Adaptive satellite communications

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7000174B2 (en) * 1999-12-20 2006-02-14 Research In Motion Limited Hybrid automatic repeat request system and method
US20020051501A1 (en) * 2000-04-28 2002-05-02 Victor Demjanenko Use of turbo-like codes for QAM modulation using independent I and Q decoding techniques and applications to xDSL systems
US6633856B2 (en) * 2001-06-15 2003-10-14 Flarion Technologies, Inc. Methods and apparatus for decoding LDPC codes
US6789227B2 (en) * 2001-07-05 2004-09-07 International Business Machines Corporation System and method for generating low density parity check codes using bit-filling
US6895547B2 (en) * 2001-07-11 2005-05-17 International Business Machines Corporation Method and apparatus for low density parity check encoding of data

Also Published As

Publication number Publication date
US20110060958A1 (en) 2011-03-10
KR20050025075A (ko) 2005-03-11
EP2270992A1 (en) 2011-01-05
CN1612486A (zh) 2005-05-04
US7237174B2 (en) 2007-06-26
US8181085B2 (en) 2012-05-15
CA2480208C (en) 2010-01-26
EP1513259A2 (en) 2005-03-09
CA2685463C (en) 2014-07-08
US20070234179A1 (en) 2007-10-04
US7461325B2 (en) 2008-12-02
US20050066262A1 (en) 2005-03-24
JP2005086824A (ja) 2005-03-31
CA2685463A1 (en) 2005-03-04
JP3936354B2 (ja) 2007-06-27
US20090044081A1 (en) 2009-02-12
CA2480208A1 (en) 2005-03-04
EP1513259A3 (en) 2005-03-30
US7856586B2 (en) 2010-12-21

Similar Documents

Publication Publication Date Title
KR100683084B1 (ko) 저밀도 패리티 검사 부호화 신호의 전송을 지원하는 방법,인코더 및 송신기
KR100619206B1 (ko) 단문 블록 길이의 저밀도 패리티 체크(ｌｄｐｃ) 코드를제공하는 방법 및 시스템
JP4109241B2 (ja) 減少されたメモリの低密度パリティチェック（ｌｄｐｃ）コードを提供する方法および装置
EP1528686B9 (en) Method and apparatus for encoding long and short block length low density parity check (LDPC) codes
CN100356697C (zh) 使用结构化奇偶校验矩阵的低密度奇偶校验码的编码
US20080065947A1 (en) Method and system for decoding low density parity check (ldpc) codes
CN101515804A (zh) 产生低密度奇偶校验码的方法和系统
HK1153054A (en) Method and system for providing short block length low density parity check (ldpc) codes.
HK1076673B (en) Method and system for providing short block length low density parity check (ldpc) codes
HK1076666A (en) Method and system for providing short block length low density parity check (ldpc) codes in support of broadband satellite applications

Legal Events

Date Code Title Description
A201 Request for examination
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 20040903

PA0201 Request for examination
PG1501 Laying open of application
E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20060428

Patent event code: PE09021S01D

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

Patent event code: PE07011S01D

Comment text: Decision to Grant Registration

Patent event date: 20061220

GRNT Written decision to grant
PR0701 Registration of establishment

Comment text: Registration of Establishment

Patent event date: 20070208

Patent event code: PR07011E01D

PR1002 Payment of registration fee

Payment date: 20070209

End annual number: 3

Start annual number: 1

PG1601 Publication of registration
PR1001 Payment of annual fee

Payment date: 20100203

Start annual number: 4

End annual number: 4

PR1001 Payment of annual fee

Payment date: 20110201

Start annual number: 5

End annual number: 5

PR1001 Payment of annual fee

Payment date: 20120130

Start annual number: 6

End annual number: 6

FPAY Annual fee payment

Payment date: 20130201

Year of fee payment: 7

PR1001 Payment of annual fee

Payment date: 20130201

Start annual number: 7

End annual number: 7

FPAY Annual fee payment

Payment date: 20140130

Year of fee payment: 8

PR1001 Payment of annual fee

Payment date: 20140130

Start annual number: 8

End annual number: 8

FPAY Annual fee payment

Payment date: 20150130

Year of fee payment: 9

PR1001 Payment of annual fee

Payment date: 20150130

Start annual number: 9

End annual number: 9

FPAY Annual fee payment

Payment date: 20160128

Year of fee payment: 10

PR1001 Payment of annual fee

Payment date: 20160128

Start annual number: 10

End annual number: 10

FPAY Annual fee payment

Payment date: 20161229

Year of fee payment: 11

PR1001 Payment of annual fee

Payment date: 20161229

Start annual number: 11

End annual number: 11

FPAY Annual fee payment

Payment date: 20171228

Year of fee payment: 12

PR1001 Payment of annual fee

Payment date: 20171228

Start annual number: 12

End annual number: 12

FPAY Annual fee payment

Payment date: 20181227

Year of fee payment: 13

PR1001 Payment of annual fee

Payment date: 20181227

Start annual number: 13

End annual number: 13

PR1001 Payment of annual fee

Payment date: 20211229

Start annual number: 16

End annual number: 16

PR1001 Payment of annual fee

Payment date: 20240130

Start annual number: 18

End annual number: 18

PC1801 Expiration of term

Termination date: 20250303

Termination category: Expiration of duration