KR20030036227A

KR20030036227A - Ｌｄｐｃ 코드형 변조를 위한 시스템 및 방법

Info

Publication number: KR20030036227A
Application number: KR1020027017148A
Authority: KR
Inventors: 마르코스 씨. 티자네스; 아몬 프리드만; 토더 쿠크레브
Original assignee: 어웨어, 인크.
Priority date: 2000-06-16
Filing date: 2001-06-18
Publication date: 2003-05-09
Also published as: JP2004503979A; US20020042899A1; EP1290802A1; KR20100046063A; WO2001097387A1; US20050229088A1; US20100299573A1; US20090183048A1; CA2409179A1; AU2001267096A1; US20160204901A1; US20100299574A1

Abstract

전형적인 전방 에러 수정 방법은 트레리스 코드 변조를 이용한다. 합성 변조 및 엔코딩 프로시저의 일부와 같이 콘볼루션코드를 대시하여 저 밀도 패리티 체크코딩을 대신하여 바꿈으로서, 저밀도 패리티 체크코딩 및 변조가 실행될 수 있다. 저밀도 패리테체크는 에러 플로어를 없이, 순환없이, 정보비트 및 패리티비트에 대해 동등한 비트 에러 전송률을 가지며, 가변 코드워드 크기를 갖는 패리티체크 행렬 및 생성기행렬 모두의 적절한 구성이 가능하다.

Description

ＬＤＰＣ 코드형 변조를 위한 시스템 및 방법{System and Methods for LDPC Coded Modulation}

종래의 통신시스템에서, 격자 코드형 변조(trellis coded modulation :TCM)라 불리는 합성 변조 및 코딩 프로시저는 주로 DSL 시스템 성능을 개선하기 위해 이용된다. 언저베옥(ungerbeock)은 1976년에 TCM을 소개했으며, 그 다음 그것은 몇몇 무선통신 전송표준에 이용되어졌다. 구체적으로, 격자 코드는 정보 비트 스트림의 서브 세트와 신호 배열(constellation)부분을 서브세트, 즉, 코세트(coset)로 엔코딩하고, 코세트로 정보비트를 맵핑하기 위해 콘볼루션 코드(convolution code)를 이용한다. 표준 ADSL 시스템은 ITU 표준 G.992.1에 나타난 바와 같이 TCM을 이용하는데, 그 전체내용이 본 명세서에 참조문헌으로 이용된다.

저밀도 패리티 검사(low density parity check :LDPC) 역시 종래의 통신시스템에 이용된다. LDPC코드는 콘볼루션 코드와 비교했을 때 개선된 성능을 갖는 것으로 보여진다. LDPC코드는 예를 들면, 1999년에 정보이론상의 IEEE 보고서에서 D.J.C. 멕케이에 의해 발표된 "초 희소 행렬에 따른 올바른 오류-수정 코드(Good Error - Correctiong Codes Based on Very Sparse Matrices" 에서 설명되는데, 이 전체가 본 명세서에 참조문헌으로 인용된다. 종래의 LDPC코드형 통신 시스템에서, LDPC코드는 리드솔로몬 코드(Reed Solomon Codes) 또는 해밍 코드(Hamming Code)와 같은, 전형적인 블럭코드로 이용된다.

본 발명은 "LDPC 코드형 변조"라는 명칭으로 2000년 6월 16일에 출원된 미국 가출원번호 60/212,233과 "ADSL에 대한 저밀도 패리티 검사(low density parity check:LDPC) 코드형 변조"하는 명칭으로 2000년 10월 18일에 출원된 미국 가출원번호 60/241,468의 이점을 주장하는데, 본 명세서에 그들의 전체가 참조문헌으로 통합된다.

본 발명은 통신코드에 관한 것이다. 구체적으로, 본 발명은 다중 반송파에 대한 전방 에러 수정 코딩방법(forward error correction coding method)에 관한 것이다.

본 발명의 실시예들는 이하 도면(들)을 참조하여, 상세하게 설명될 수 있다.

도 1은 LDPC코드형 변조를 위한 실시예 시스템을 나타내는 기능적 블럭도이다.

도 2는 패리티 검사 행렬의 그래픽 표현의 실시예를 나타낸다.

도 3은 랜덤 패리티 검사 코드의 실시예를 나타낸다.

도 4는 패리티 검사 행렬의 실시예 구조를 나타낸다.

도 5는 LDPC코드를 결정하기 위한 실시예를 개략하는 흐름도이다.

도 6은 LDPC코드를 결정하기 위한 제2 실시예를 나타내는 흐름도이다.

도 7은 난수(randum number)를 결정하는 방법의 실시예를 나타내는 흐름도이다.

그러나, LDPC코드는 예를 들면, 격자 코드형 변조에서 행해진 것과 같이 합성 변조 및 코딩 프로시저의 일부처럼 종래 LDPC코드형 시스템에 이용되지는 않는다. 또한, 본 발명의 방법 및 시스템의 바람직한 실시예는 저밀도 패리티 검사 코드에 따라 통신하기 위해 전방 에러 수정 코딩방법을 제공한다. 구체적으로, 본 발명의 실시예는 합성 변조 및 코딩 프로시저의 일부와 같이 콘볼루션 코드를 대신하여 LDPC코드를 이용한다. 본 새로운 엔코딩 방법은 LDPC 코드형 변조(LDPC Coded Modulation: LDPCCM)라 지칭할 수 있다.

본 발명의 실시예에서, LDPCCM은 종래의 ADSL시스템의 성능을 개선하기 위해 이용된다. 종래에, ADSL시스템은 TCM을 이용했다. 그러나, 본 발명의 실시예에서, LDPCCM은 개선된 코딩 이득을 제공하도록 TCM을 교체한다. 그러나, 전술한 바와 같이, ADSL시스템에서 LDPCCM을 이용하기 위해, LDPC코드는 다수의 실시 조건을 만족할 수 있다. 이 조건들은 에러 최저값(error floor)과 사이클을 갖지 않는 코드를 포함할 수 있다. 또한, 코드는 정보 비트 및 패리티 비트에 대해 동일한 비트 에러 전송률, 가변 코드 워드 크기(variablr code word size)를 갖는 패리티 검사 행렬의 구조를 상대적으로 빨리 결정하기 위한 능력, 및 생성 행렬(generator matrix)을 가질 수 있다.

에러 최저값과 사이클을 갖지 않는 제1 조건을 만족하는 설계는, 2000년 통신분야의 IEEE 보고서에서, D.J.C.멕케이에 의해 "LDPC"에서 설명되어진 것과 같이, 알려져 있으며, 이는 본 명세서에 그 전체가 참조문헌으로 인용된다. 발표된 LDPC코드는 소정의 사이클 및 그로 인한 에러 최저값을 갖지 않는 9979의 코드워드 크기를 갖는다. 그러나, 예를 들면, 구조는 다른 코드 워드(예를 들면, 더 짧거나 더 긴 코드워드가 달성될 수 없는)에 연장될 수 없다.

따라서, 본 발명의 실시예에 따라, 전방 에러 수정(forward error correction : FEC) 코드형 비트 신호는 LDPC코드를 이용하는 데이터 비트 신호의 서브세트(subset)를 코딩하는 FEC에 의해 제공된다.

또한 본 발명의 측면은 다중 반송파 환경에서 LDPC코드를 이용하는 것에 관한 것이다.

본 발명의 측면은 DSL시스템의 개선된 성능을 제공하는 것에 관한 것이다.

본 발명의 측면은 저 밀도 패리티 체크 코드에 따라 ADSL시스템을 통해 통신을 위한 코딩방법을 제공하는 것에 관한 것이다.

또한 본 발명의 측면은 ADSL환경에서 합성 변조 및 코딩 프로시져의 일부와 같이 콘볼루션 코드를 대신하여 이용되는 저 밀도 검사 코드를 제공하는 것에 관한 것이다.

본 발명의 측면은 초기화 또는 구성상태 동안에 LDPC패리티 검사 행렬을 구성하는 것에 관한 것이다.

본 발명의 측면은 초기화 또는 구성상태 동안에 LDPC생성 행렬을 구성하는 것에 관한 것이다.

또한 본 발명의 측면은 통신시스템의 레이튼시 및 데이터 전송률 조건이 결정된후에 LDPC 패리티 검사 행렬을 구성하는 것에 관한 것이다.

또한 또한 본 발명의 측면은 통신시스템의 레이튼시 및 데이터 전송률 조건이 결정된 후에 LDPC생성기 매트릭스를 구성하는 것에 관한 것이다.

이들 및 다른 특징 및 본 발명의 장점은 이하 실시예의 구체적 설명에서 묘사되거나 실시예의 설명으로부터 나타난다.

에러 최저값(error floor) 및 사이클을 갖지 않는 LDPC코드의 제1 조건과 관련하여, ADSL 시스템은 비디오 정보와 같은, 비트 에러에 대해 아주 민감한 정보를 주로 운반하기 때문에, 아주 낮은 비트 에러 전송률(bit error rate : BER)에서 동작해야 한다. 이러한 이유로 인해, ADSL시스템은 주로 1E-7보다 적은 BER에서 동작하도록 규정된다. 전방 에러 수정 코드의 에러 최저값은 아주 높은 신호대 잡음비(signal-to-noise ratio : SNR)에서 제로가 아닌(non-zero) BER로 정의된다. 많은 코드는 에러 최저값을 갖지 않는다. 예를 들어, 채널의 신호대 잡음비 SNR이 증가되는 것(무한 접근(approach infinity))과 같이 BER은 감소로 진행한다(0으로 접근). 터버 코드는 에러 최저값을 표시하는 코딩 방법의 실시예이다. 이것은 아주 높은 SNR에서, 터버 코드(turbo code)에 대한 BER이 상수(constant)로 남을 수있다는 것을 의미한다. 그러므로, 본 발명의 측면에 따라, LDPC코드는 코드에서 t사이클이 없다는 것을 확실하게 함으로써 에러 최저값을 갖지 않도록 구성된다.

정보 비트 및 패리티 비트에 대해 동일한 비트 에러 전송률(BER)을 갖는 코드의 제2 조건과 관련하여, 전형적인 LDPC코드형 시스템에서, LDPC코드는 간단한 블럭 코드로 이용된다. 이 시스템에서, 패리티 비트는 채널을 통해 정보비트를 따라 코드워드의 일부처럼 전송된다. 수신기에서, 패리티 비트는 정보비트의 에러 수정을 디코딩하기 위해 이용된다. 디코딩 처리가 완료한 다음, 패리티 비트는 처분된다. 결론적으로, 패리티 비트의 실제 BER은 중요하지 않다. 이러한 이유로 인해, 전형적인 LDPC코드형 시스템은 주로 패리티 비트 및 정보비트상에서 상이한 BER을 갖는 코드를 이용한다.

본 발명의 실시예에 따라. 엔코딩된 비트, 즉, 정보 및 패리티 비트는, 배열 코세트(constellation coset)를 나타내는데 이용된다. 그러므로, 그것은 패리티 및 정보 비트는 둘다 코세트가 디코딩을 위해 이용되는 지를 결정하는 데 이용되기 때문에 모든 엔코딩된 비트는 동일한 BER을 갖는다는 것이 중요하다. 특히, LDPC코드는 패리티 노드를 갖는 정보 비트 및 패리티비트를 연결하는 동일한 브랜치 개수를 갖는 LDPC패리티 검사 행렬을 보증함으로써 적어도 정보 비트 및 패리티비트상에서 동등한 BER로 구성되며, 패리티 노드는 정보 비트 및 패리티 비트의 동일한 개수로 연결된다.

ADSL시스템은 가변 전송률(variable rate)과 가변 레이튼시 시스템(variable latency system)이다. 이것은 ADSL 송수신기가 많은 상이한 데이터 전송률로 동작하도록 구성될 수 있다는 것을 의미한다. 실시예로서, ITU 표준 G.992.1는 ADSL송수신기가 32kbps의 증가에서 64kbps로부터 6Mps까지의 전송률로 동작할 수 있음을 요청한다. 또한 ADSL시스템은 가변 레이튼시 시스템이다. 이것은 ADSL송수신기가 많은 다른 레이튼시, 즉, 지연, 레벨 등에서 동작할 수 있어야한다. 예를 들어, ITU 표준 G.992.1는 ADSL송수신기가 예를 들어, 1.5msecs 내지 20msecs의 레이튼시 레벨에서 동작할 수 있다.

ADSL시스템의 가변 전송률 및 가변 레이튼시 조건은 이용될 수 있는 FEC코딩의 형태에서 어려운 설계 구속(constraint)을 갖는데(place), 왜냐하면, 예를 들어, 임의의 특정 데이터 전송률에 대해서, 시스템이 많은 다른 레이튼시 레벨을 지원해야만하기 때문이다. 예를 들면, 데이터 전송률이 예를 들어, 64kps로 낮고, 레이튼시 조건이 예를 들어 1.5msecs로 낮은 경우에는, 아주 낮은 레이튼시 FEC코드가 이용되어야 한다.

낮은 레이튼시 FEC블럭 코드는 짧은 코드워드 길이를 이용하여 설계된다. 일반적으로, 코드워드가 더 길고, FEC코드의 코딩 이득을 더 높게한다. ADSL시스템에 대해 잘 설계된 FEC코드는 레이튼시 및 데이터 전송률 조건에 따라 코드워드 길이를 적용할 수 있어야 한다는 것을 따른다. 이런 방식에서, FEC코드는 레이튼시 및 데이터 전송률 조건에 따라 최대 가능 코딩 이득을 제공할 수 있다.

그러므로, 본 발명의 바람직한 실시예에 따라, LDPC코드는 가변 코드워드 길이를 가질 수 있도록 구성된다. 이 가변 코드워드 길이 LPDC코드, 즉, 패리티 검사행렬은 데이터 전송률 및 레이튼시 조건이 규정된 다음에 결정된다. 이런 방식에서, 예를 들면, 단일 송수신기는 상이한 코드워드 길이를 갖는 다수의 LDPC코드를 저장하기 위해 구비하지 않고 데이터 전송률 및 레이튼시 레벨의 큰 어레이(large array)에 대해 구성될 수 있다. 그러므로, 일단 레이튼시 및 데이터 전송률 조건이 구체화되면, LDPC코드의 구성은 데이터 전송률 및 레이튼시 조건에 대응하는 동안 코딩 이득을 최대화하는 코드워드 길이를 결정한다. 예를 들어, ADSL송수신기는 가변 데이터 전송률 및 가변 레이튼시 시스템이다. 이것은 그들이 예를 들어, 서비스의 레벨(서비스제공자에 의해 제공되는 것처럼), 어플리케이션, 전화선의 질 등에 따라 다른 데이터 전송률 및 레이튼시로 동작하도록 구성될 수 있다는 것을 의미한다. 예를 들면, 소비자가 ADSL서비스 제공자로부터 ADSL서비스를 사는 경우, 소비자는 데이터 전송률 성능에 의해 규정된 서비스레벨을 살 수 있다. 예를 들면, 소비자는 중앙국으로부터 소비자 거지주까지 384-1536kbps를 보장했던 ADSL서비스를 살 수 있다. 전화선의 조건 및 중앙국으로부터의 거리에 따라, 소비자는 384- 1536kbps의 범위에서 다소간의 데이터 전송률을 얻을 수 있다. 또한 소비자는 서비스의 레벨(예를 들면, 5msecs)에 따라 소정의 레이튼시를 보장할 수 있다. 그러므로 ADSL송수신기이 데이터 전송률로 설치된(install) 다음에, 언급된 팩터에 따라 데이터 전송률이 결정될 수 있다. 데이터 전송률 및 서비스 레이튼시 조건에 따라 LDPC코드는 코딩 이득(즉, 데이터 전송률 및 레이튼시에 대한 코드워드 크기)을 최대화할 수 있게 구성될 수 있다. 우선, ADSL 송수신기는 예를 들면 초기화 또는 연습 상태 동안에, 전화선의 데이터 전송률 성능을 측정할 수 있으며, ADSL서비스에 의해 허용되는 데이터 전송률에 따라 ADSL송수신기는 데이터전송률 동작을 결정할 수 있다. 데이터 전송률 동작이 결정된 다음 서비스 레이튼시 조건에 따라 ADSL송수신기는 LDPC코드를 구성할 수 있다.

대안적으로 레이튼시 및/또는 데이터 전송률 조건은 또한 ADSL연결(비디오와 같은)을 통해 동작할 수 있도록 예측되는 어플리케이션에 따라 설정될 수 있으며, LDPC코드가 구성될 수 있는 경우 어플리케이션 조건은 데이터 전송률 및 레이튼시를 결정하여 제공된다.

패리티 검사 행렬의 적절한 구성을 확인하기 위해, 구성은 초기화 또는 송수신기의 구성상태동안에 완료될 수 있도록 간단하게 실행될 수 있다. 예를 들면, ADSL송수신는 초기화동안 채널(즉, 전화선)의 신호대잡음비를 측정하고 이 SNR에 따라 동작 데이터 전송률을 설치한다. 대안적으로, 전술한 바와 같이, ADSL서비스레벨 및 어플리케이션은 데이터 전송률의 결정에서의 팩터일 수 있다. 또한 레이튼시는 초기화 상태 또는 송수신기의 구성 상태동안, 즉, ADSL서비스가 우선 설치되는 경우에 결정된다. 데이터 전송률 및 레이튼시가 규정된 다음 LDPC는 구성된다.

생성 행렬의 구성과 관련하여, LDPC코드의 생성 행렬은 LDPC엔코더에서 LDPC코드워드를 생성하는데 이용된다. 생성 행렬은 일반적으로 패리티 검사 행렬에서 가우시안 소거법(gaussian elimination)을 실행함으로써 패리티 검사로부터 도출된다(derive). 전술한 바와 같이 가변 코드워드 크기를 갖는 패리티 검사 행렬의 결정과 관련하여, ADSL시스템에서 LDPC코드는 가변 코드워드 크기를 갖도록 적절하게 생성되어야 한다. 이에 따라, 생성 행렬 역시 "접촉식(on-the-fly)"와 같은 적절한 방식 또는 데이터 전송률 및 레이튼시 조건이 구체화된 다음에 생성된다.

코드의 패리티 검사 행렬은 소정의 코드워드가 모두-제로 벡터를 생성하는 경우의 행렬이다. 수학적으로 이것은 다음과 같이 쓸 수 있다.

H는 코드의 패리티 검사 행렬이고, c는 코드 C에서 소정의 코드워드이다.

코드의 생성 행렬은 입력 벡터에 의해 곱해진 코드워드의 결과이다. 수학적으로 이것은 다음과 같이 쓸수 있다.

G는 코드의 패리티 검사행렬이고, a는 소정의 데이터 벡터이다.

여기서 C는 모든 코드워드의 세트이다. 예를 들면, 소정의 패리티 검사 행렬

H =

1	0	0	1	0	1	1
0	1	0	1	0	1	0
0	0	1	0	1	1	1

이고 생성 행렬은 G =

1	1	0	1	0	0	0
0	1	1	0	1	0	0
1	1	1	0	0	1	0
1	0	1	0	0	0	1

이때, 입력 벡터 a = {0,1,0,0}, 합성 코드워드는

c = aG = {0,1,1,0,1,0,0}.

이것은 또한

,

요구된대로 산출된다.

본 실시예에서, 패리티 검사 행렬 및 생성 행렬은 모두 체계적이다, 즉, 항등 행렬(identity matrix)은 행렬식의 일부로 나타난다.

및

이 경우에이다.

LDPC코드에 대한 패리티 검사는 패리티 검사 행렬에서 행(row)에 랜덤하게 할당함으로써 생성된다. 다수의 컬럼은 정보 비트 K의 개수에 패리티비트를 더한 것과 동일하다. 행의 개수는 패리티 비트의 개수와 동일한다.

도 1은 패리티 검사 행렬의 실시례를 나타내는데, 여기서 원형은 정보비트(100)를 나타내고 사각형은 패리티비트(110)을 나타낸다. 정보비트 및 패리티비트를 연결하는 라인(115)은 패리티 검사 행렬 중 하나로 나타나며, 또한 코드워드로 만족되는 패리티 검사 행렬을 나타낸다. 사각형(120)의 하부 행(row)을 참조하면, 하부 행(row)을 따라 사각형에 연결하는 모든 비트의 합(모듈로 2)은 코드워드에 대해 0과 같게 표시해야 한다.

도 2는 랜덤한 패리티 검사 코드(130)의 실시예를 나타낸다. 본 실시예에서는 세개의 정보비트(100) 및 세개의 패리티 비트(110)가 있다. 상부 행(row)을 따르는 각 비트로부터 하부 행(row)을 따르는 체크 노드(120)까지 두 개의 연결(115)이 있다. 다만 세개의 검사노드(check node:120)가 있으므로, 각 검사노드는 정보 및 패리티 비트에 대해 네 개의 연결을 갖는다. 또한 패리티 검사 코드(130)에 대한 패리티 검사 행렬(H)(140)이 도시된다. 패리티 검사 행렬(140)의 각열(column)은 두개이고, 각 행(row)은 네개를 갖는다. 이것은 패리티 검사 코드(130)의 그래픽 표현과 유사하다.

도 1 및 도 2는 둘 다 각 열(column)에서 동일한 개수가 있으며, 패리티검사의 각 행에서 동일한 개수가 있다는 것을 의미하는 정규 패리티 검사 행렬을 나타낸다. 또한 도 2는 각 패리티 검사노드(120)가 정보 및 패리티 비트의 동일한 개수와 연결되는 경우를 도시한다.

생성 행렬을 찾는 것에 대한 마지막 포인트는 LDPC코드의 구성을 고려하는 경우가 중요하다. 구체적으로, 일반 패리티 검사 행렬로 설명되는 코드에 대해 생성기 행렬을 얻기 위하여, 가우시안 소거법(gaussian elimination)은 계통 패리티 검사 행렬(sytemtic parity check matrix)을 형성하기 위해 패리티 검사 행렬로 실행되는데 그 다음 생성 행렬은 행렬(H)의 전치를 행함으로써 얻어진다. 그러나, 불규칙하게 구성된 H 행렬은 "완전 계수(full rank)"일 수가 없으며 그러므로 패리티 검사 행렬로부터 길이 N 코드를 형성할 수 없다. 실제, 코드워드 길이는 주로 N보다 약간 적으며, 보통 3 비트이내이다.

도 3은 본 발명에 따른 LDPC코더의 실시예를 도시한다. ADSL송수신기 구성은 잘 알려져 있으며 예를 들면, ITU표준 G.992.1에서 찾을 수 없으므로, ADSL통신에 대한 하드웨어 및 소프트웨어의 나머지(remainder)는 본 명세서에 설명되지 않을 것이다. LDPC코더(300)는 LDPC엔코더 모듈(310), 코세트 맵 결정 모듈(coset map determination module:320), QAM엔코더(330), 및 변조기(340)를 포함한다. 입력 정보 스트림B'_M은 코드형 정보비트가 될 입력(incoming)을 나타낸다. 스트림 C_N에서의 정보는 LDPC코드형 비트를 나타낸다. 또한 LDPC코더(300)와 연관된 생성 행렬 모듈(400)이 있다.

코드 전송률(code rate)은 다음식으로 표시될 수 있다.

LDPCCM수신기는 도 3의 역함수(inverse function)를 포함하는데, LDPC 패리티 검사 행렬을 이용하여 실행되는 LDPC디코딩을 갖는다. 패리티 검사 행렬은 수신기에 존재하는 패리티 검사 구성 모듈을 이용하여 구성된다.

전술한 바와 같이, LDPC패리티 검사 행렬은 데이터 날짜 및 레이튼시 파라미터가 최기화 또는 구성 상태 동안에 구체화되어진 다음 구성된다. LDPC패리티검사 행렬의 구성은 수신기에서 실행되며, 각 정보 및 각 패리티 비트부터 각 패리티노드까지 브랜치 개수 및 코드전송률을 선택함으로써 전송률 및 브랜치 결정모듈(미도시)을 개시한다. 이 브랜치의 개수는 t로 표시된다. 예를 들면, 의사-랜덤 이동 레지스터(pseudo-random shift register)와 같은, 난수 모듈(random number module)에서 결정된 난수에 따라 브랜치는 정보 및 패리티 비트를 통해 사이클의 개수 t에 따라 각 비트로부터 패리티노드까지 불규칙하게 할당된다. 이것은 t 브랜치가 각각의 정보 및 패리티비트로 나타낸다는 것을 확실히 한다. 브랜치는 초기의 반복(iteration)과 같이, 동일한 비트부터 동일한 패리티 노드까지 할당되면, 새로운 난수가 선택되서 새로운 브랜치가 선택된다.

두 개의 옵션은 모든 노드가 완전하게 존재된다는(populate) 것을 보장하는데 이용할 수 있다. 구체적으로, 시스템은 모든 패리티노드로부터 브랜치의 동일한 개수 또는, 대안적으로 패리티비트 및 정보비트 둘다에서 모든 패리티노드와 동일한 연결을 결정할 수 있다. 모든 패리티 노드에서 동일한 개수의 브랜치에 대해, 카운터(counter:미도시)는 각 패리티노드에 할당되며 브랜치가 그 노드에 연결될때 마다 증가된다. 카운더가 2t에 도달하면, 더이상 다른 연결이 그 노드에 만들어지는 것이 허용되지 않는다. 불규칙하게 생성된 브랜치가 "전(full)"노드를 선택하면, 불규칙한 수는 폐기되고 새로운 브랜치가 선택된다. 이에 대한 효율적인 방법은 범위 1-(N-k-f)에서 난수를 선택하는데 여기서 f는 "전"노드의 개수이다. 그러나, 브랜치거주(poppulation)의 단부를 향하게 되면, 브랜치 중복을 피하기는 어렵게 되서, 프로세스가 재시작될 수 있거나 몇몇 비트가 브랜치 t보다 적게 구비되도록 선택될 수 있다.

패리티노드로부터 패리티 비트 및 정보비트 둘다까지 동일한 연결에 대해, 두개의 카운터는 패리티 비트 및 정보비트 브랜치를 카운트하기 위해 각 패리티노드 각각에 할당된다. 그 다음 브랜치는 정보 또는 패리티비트에 할당되는 연결개수를 초과하도록 허용하지 않도록 선택된다. 이것은 실시예와 관련하여 전술된 바와 같이 동일한 방식에서 달성될수 있는데 여기서 동일한 브랜치는 모든 패리티노드에 나타난다. 그러나, 이러한 실시예 시나리오에서, "전"노드를 갖는 것 대신 "전 정보"노드 및 "전 패리티"노드를 갖는다.

다음, 임의의 길이일 수 있는 사이클은 패리티 검사 행렬을 통해 검색하고다른 브랜치를 갖는 사이클을 형성하는 브랜치를 재할당함으로써 소거될 수 있으므로, 사이클이 제거된다. 그러나, 전술된 루핑단계(looping step)를 갖는 조화된 방식에서 브랜치를 재할당이 복소 연산할 수 있으므로, 사이클로부터 브랜치를 간단하게 제거할 수 있으며, 시스템의 성능에 나쁜영향을 주지않고 동일하지 않은 연결 개수를 갖도록 노드 및 비트의 일부를 허용할 수 있다.

전송에서, 생성 행렬은 데이터 전송률 및 레이튼시 파라미터가 초기화 또는 구성상태 동안 구체화된다음 생성기 행렬 모듈(400)로 결정된다. 구체적으로, 가우시안 소거법을 이용하여, 계통 패리티 검사 행렬이 생성된다. 조직 행렬로부터, 생성 행렬은 전술한 바와 같이 생성된다. 패리티 검사 행렬이 코드워드 길이가 원하는 것보다 적을 수 있다는 것을 나타내는 전계수(full rank)가 아니면, 두개의 옵션이 있다. 첫째, 전술한 바와 같이 루핑은 재실행될 수 있다. 대안적으로, 원하는 코드 전송률에 대해서 요구되는 것보다 많은 정보 비트가 선택될 수 있으며 남아있는 단계가 순서대로 실행된다. 그러나, 이것은 패리티노드에 대해 동일하지 않게 따른다.

행렬이 전계수가 아니면, 하나이상의 행(row)은 필수적으로 소거될 수 있다. 합성 코드가 추가 정보비트를 가지면, 이 추가 비트는 엔코딩 및 디코딩의 목적으로 0으로 추정될 수 있으며, 반면 전송될 필요는 없다.

대안적으로, LDPC코드를 생성하기 위한 제2실시예 방법은 모든 코드 구조의 다수의 특징의 비용면에서 전술한 방법보다 빠르다. LDPC코드를 발생하는 바람직한 방법의 중요한 차이는 패리티 검사 행렬이 구속될 수 있다는 것이며 따라서 행렬의 패리티 비트 구간을 형성하는 열(column)은 구조에서 더 적은 삼각행렬(triangular)일 수 있다. 만약 더 적은 삼각 행렬 구간이 항등 행렬(identity matrix)인 것으로 알려지면, 생성 행렬을 결정하는 것은 상대적으로 복잡하지 않다. 생성된 것과 같이, 패리티 비트 구간은 사실상 더 적은 삼각이 될 수 있다.

도 4는 이 구조에 대한 패리티 검사 행렬 실시예의 구조를 나타낸다. 더 낮은 삼각 행렬은 사각 행렬을 제공하는데 여기서 임의 및 모든 비-제로항은 1,1 에서부터 N,N,까지 주 대각(diagonal) 또는 그 아래이다(즉, 상기 주 대각 모두는 0이다). 이 실시예의 경우에, 패리티비트인 패리티 검사 행렬의 구간은 마지막 N-K칼럼은 크기 N-K x N-K의 사각 행렬을 형성한다. 이거은 더 적은 삼각 행렬로 될 필요가 되는 구간이다. 정보비트에 대한 구간은 구성되지 않는다. 이에 따라, 구간은 항등 행렬인 N-K x N-K 항등 행렬을 만들 수 있는 패리티구간으로 칭한다. 그러므로, 항등 행렬(또는 임의의 대각선 행렬)은 더 적은 삼각 행렬의 서브세트이다.

이하에 전술될 난수 생성으로 합성된 이 구성에 대한 이점은, 패리티 검사 행렬이나 생성 행렬 요구가 저장된다는 것이다. 엔코딩 또는 디코딩 동안에 임의의 시간에서 요구되는 브랜치는 필요한 PRBS에서 결정될 수 있다. 이것은 코드워드 크기가 증가하고 최대 크기가 증가하는 것과 같은 이점을 제공한다. 또한, 가우시간 소거법을 통해 LDPC를 생성하는 보통 방법은 비-희소(non-sparse)이고 엔코더에 대한 큰 저장량을 요구하는 생성 행렬을 생성한다.

엔코더의 이점에 대해 이 방법을 이용하는 방식은 0과 같게 모든 패리티 노드를 설정한다. 정보비트가 도달되는 것과 같이, 패리티 노드연결을 예를 들면, PRBS가 결정되며, 정보비트는 패리티 노트와 배타적OR(XOR)된다. 다음, 처음 패리티 비트는 우선 패리티노드의 값과 동등하게 설정되고, 이 값은 처음 패리티비트에 연결되는 다른 패리티노드와 XOR된다. 이 결정은 예를 들면 PBRS에 의해 다시 결정된다.

도 5는 본 발명에 따른 LDPC코드를 결정하는 방법의 제1실시예를 나타낸다. 구체적으로, 제어는 단계 (S100)에서 시작하고 단계 (S110)으로 진행한다. 단계 (S110)에서, 코드 전송률(code rate)이 결정된다. 다음 단계 (S120)에서, 브랜치(branch)(t)의 개수가 결정된다. 그 다음 제어는 단계 (S130)으로 진행한다.

단계 (S130)에서, 정보 또는 패리티 비트가 선택된다. 다음 단계 (S140)에서 난수(random number)가 결정된다. 그 다음 단계 (S150)에서 선택된 정보 또는 패리티 비트로부터 브랜치가 결정된다. 그 다음 제어는 단계 (S160)으로 진행한다.

단계 (S160)에서, 결정된 브랜치가 중복되는지를 결정한다. 브랜치가 중복되면, 제어는 단계 (S140)으로 되돌아가고, 그렇지 않으면 제어는 단계 (S170)으로 진행한다.

단계 (S170)에서, 브랜치는 패리티노드에 할당된다. 다음, 단계 (S180)에서, t는 선택된 비트에 대해 인덱싱된다(index). 다음 단계 (S190)에서, 할당된브랜치의 개수가 모든 정보 및 패리티 비트에 대해 t와 동일하다. 정보 및 패리티 비트는 할당된 브랜치(t)를 갖지 않으면, 제어는 단계 (S200)으로 진행한다. 그렇지 않으며, 제어는 단계 (S210)으로 진행한다.

단계 (S200)에서, 다음 정보 또는 패리티 비트가 선택된다. 다음 제어는 단계 (S140)으로 넘어간다.

단계 (S210)에서, 사이클(cycle)이 배제된다(eliminate). 다음 단계 (S220)에서, 생성 행렬이 결정된다. 다음 단계 (S230)에서는, 패리티 검사 행렬이 모든 계수(full rank)인지를 결정한다. 패리티 검사 행렬이 모든 계수가 아니면, 제어는 단계 (S240)으로 진행한다. 그렇지 않으면, 제어는 단계 (S250)으로 넘어가고 여기서 제어순서는 끝난다.

단계 (S240)에서 요구되는 것보다 더 많은 정보 비트가 선택되고, 제어는 단계 (S120)으로 넘어간다.

도 6은 본 발명에 따른 LDPC를 결정하는 제2실시예를 나타낸다. 구체적으로, 제어는 단계 (S300)에서 시작하고, 단계 (S310)으로 진행한다. 단계 (S310)에서는, 코드전송률이 결정된다. 다음, 단계 (S320)에서는, 브랜치(t) 개수가 결정된다. 다음, 단계 (S330)에서 정보 및/또는 패리티 비트가 선택된다. 다음 제어는 단계 (S340)으로 진행한다.

단계 (S340)에서, 난수(random number)가 결정된다. 다음 단계 (S350)에서는, 선택된 정보 또는 패리티 비트 및 패리티 노드 간의 브랜치기 결정된다. 다음 단계 (S360)에서, 브랜치가 중복되는지를 결정한다. 브랜치가 중복하면, 제어는단계 (S340)으로 되돌아간다. 그렇지 않으면, 제어는 단계 (S370)으로 진행한다. 단계 (S370)에서, 패리티 노드가 전부(full)인지를 결정한다. 패리티 노드가 전부이면, 제어는 단계 (S340)으로 되돌아간다. 그렇지 않으면 제어는 단계 (S380)으로 진행한다.

단계 (S380)에서, 브랜치는 패리티노드에 할당된다. 다음, 단계 (S390)에서, t는 선택된 정보 또는 패리티 비트에 대해 인덱싱된다(index). 다음, 단계 S400에서, 브랜치 t는 모든 정보 및 패리티 비트에 할당되는지를 결정한다. 브랜치 t가 모든 정보 및 패리티비트에 할당되지 않으면, 제어는 단계 (S400)으로 진행한다. 그렇지 않으면, 제어는 단계 (S420)으로 넘어가고 여기서 제어순서가 끝난다.

단계 (S400)에서, 다음 정보 또는 패리티비트가 선택된다. 다음 제어는 단계 (S350)으로 되돌아간다.

도 7은 단계 (S140) 및 (S340)에 표시되는 것과 같이 난수를 결정하는 방법의 실시예를 나타낸다. 구체적으로, 제어는 단계 (S500)에서 시작하며 단계 (S510)으로 진행한다. 단계 (S510)에서, 난수, 예를 들면, 긴 비-반복 순서(long non-repeating sequence)가 의사-무작위 이동 레지스터(pseudo-random shift register : PRBS)에서 선택된다. 다음, 단계 (S520)에서, N이 선택된다. 다음, 단계 (S530)에서, PRBS가 이동된다. 그 다음 제어는 단계 (S540)으로 진행한다.

단계 (S540)에서는, 레지스터 모듈로(register modulo)(N-K)의 값이 얻어진다. 다음, 단계 (S550)에서는, 난수가 출력된다, 다음, 제어는 단계 (S560)으로진행하고 여기서 제어순서가 끝난다.

도 3에 도시된 바와 같이, LDPC코드결정 시스템 및 관련 요소들은 VDSL 모뎀과 같은 DSL모뎀, 또는 통신장치를 갖는 프로그램화된 분리형 범용 컴퓨터로 구현될 수 있다. 그러나 LDPC코드 결정 시스템은 또한 특정 목적 컴퓨터, 프로그램화된 마이크로 프로세서 또는 마이크로-컨트롤러 및 주변 집적 회로 요소, ASIC 또는 다른 집적 회로, 디지탈 신호 프로세서, 하드 유선 전기 또는 이산 엘리먼트 회로와 같은 로직 회로, 하드 유선 전기 또는 이산 엘리먼트 회로와 같은 로직 회로, PLD, PLA, FPGA, PAL과 같은 프로그램화된 로직 디바이스상에서 구현될 수 있다. 일반적으로 도 5-7에 도시된 흐름도를 구현할 수 있는 유한 상태 장치(finite state machine)를 실현할 수 있는 어떠한 디바이스도 본 발명에 따라 LDPC코드 결정시스템을 구현하는데 이용될 수 있다. 또한, 본 명세서에 이용된 것과 같은 term 모듈은 임의 하드웨어 또는 소프트웨어, 또는 이들의 결합으로 encompass할 수 있다.

LDPCCM방법은 임의의 무선, 유선 또는 전형적인 통신시스테믈 통해 개선되는 코딩을 개선하기 위해 일반적인 임의의 통신에 이용될 수 있다. LDPCCM방법은 다중반송파 또는 단일 반송 변조를 이용하는 임의 통신시스템에 이용될 수 있다. 더우기, 이 LDPCCM방법은 가변데이터 전송률 및 레이튼시 조건을 갖는 임의 통신 시스템에서 이용될 수 있는데, 여기서 이 데이터 전송률 및 레이튼시 조건은 예를 들면 초기화 또는 구성 상태동안에 결정된다.

더우기, 개시된 방법은 다양한 컴퓨터 또는 워크스테이션, 또는 모뎀 하드웨어 및/또는 소프트웨어 플랫포옴상에서 이용될 수 있는 포터블(portable) 소스 코드를 제공하는 객체(object) 또는 객체-지향(object-oriented) 소프트웨어 개발 환경을 이용하여 소프트웨어로 구현될 수 있다. 대안적으로, 공개된 모뎀은 표준 로직 회로 또는 VLSI설계를 이용하여 부분적 또는 전체적 하드웨어로 구현될 수 있다. 다른 소프트웨어 또는 하드웨어가 시스템의 속도 및/또는 효율적인 조건, 특정 함수, 및 특정 소프트웨어 또는 하드웨어 시스템 또는 이용되는 마이크로프로세서 또는 마이크로컴퓨터 시스템에 의존하는 본 발명에 따라 시스템을 구현하기 위해 이용될 수 있다. 그러나, 본 상세한 설명에 개시된 LDPC코드 결정시스템은 이미 알려졌거나 향후 개발될 시스템 및 구조물을 이용하는 하드웨어 및/또는 소프트웨어, 본 명세서에 제공되는 기능적 설명 및 컴퓨터 및 무선통신 기술의 일반적인 기술로부터 당업자에 의해 적용할 수 있는 디바이스 및/또는 소프트웨어로 쉽게 실행될 수 있다.

더욱이, 개시된 방법은 프로그램화된 범용 컴퓨터, 특정 목적 컴퓨터, 마이크로프로세서상에서 실행되는 소프트웨어로 쉽게 구현될 것이다. 예를 들면, 본 발명의 방법 및 시스템은 DSL모뎀과 같은 모뎀상에서 구현되는 프로그램으로 수행될 수 있다. 또한 LDPC코드 결정 시스템은 본 시스템 및 방법을 ADSL 모뎀, VDSL 모뎀, 네트워크 인터페이스 카드 등과 같은 모뎀의 하드웨어 및 소프트웨어 시스템과 같은 하드웨어 시스템 및 소프트웨어 시스템에 물리적으로 통합시킴으로써 구현될 수 있다.

그러므로, 본 발명에 따라 제공되는 장치는 LDPC를 결정하기 위한 시스템 및방법이 제공된다. 본 발명은 다수의 실시예에 관하여 설명하고 있는데, 그것은 응용가능한 분야에서 당업자에 의해 다양한 형태, 수정 및 변경이 적용될 수 있다는 증거이다. 따라서, 그것은 본 발명의 정신 및 범주내에서의 모든 변경, 수정 및 등가물과 변형물을 포함한다.

Claims

통신 채널을 통해 전송하기 위한 데이터 비트 신호의 합성 변조(combined modulation) 및 전방 에러 수정 코딩(forward error correction(FEC) coding)방법에 있어서,

FEC 코딩형 비트 신호를 제공하기 위해 LDPC코드를 이용하여 상기 데이터비트신호의 서브세트(subset)를 FEC코딩하는 단계와,

하나이상의 비트신호를 포함하는 적어도 하나의 배열(constellation)을 이용하여 상기 데이터 비트 신호 및 상기 FEC코딩형 비트 신호를 변조시키는 단계와,

상기 FEC 코딩형 비트 신호를 이용하여 적어도 하나의 배열의 코-세트(coset)를 나타내는 단계

를 포함하는 합성 변조 및 전방 에러 수정 코딩방법.
제1항에 있어서,

상기 변조는 단일-반송파 또는 다중 반송파 변조인 합성 변조 및 전방 에러 수정 코딩방법.
제1항에 있어서,

상기 LDPC코드는 하나이상의 정보비트 및 하나이상의 패리티비트에 대해 동일한 BER을 갖는 합성 변조 및 전방 에러 수정 코딩방법.
제1항에 있어서,

상기 LDPC코드 패리티 검사 행렬(parity check matrix)은 초기화(initialization) 또는 구성 상태(configuration phase) 동안에 결정되는 합성 변조 및 전방 에러 수정 코딩방법.
제1항에 있어서,

상기 LDPC코드 생성 행렬(generator matrix)은 초기화 또는 구성 상태 동안 결정되는 합성 변조 및 전방 에러 수정 코딩방법.
제1항에 있어서,

상기 LDPC코드 패리티 검사 행렬은 레이튼시(latency) 및 데이터 전송률(data rwte)이 구체화된 다음에 결정되는 합성 변조 및 전방 에러 수정 코딩방법.
제1항에 있어서,

상기 LDPC코드 생성 행렬은 레이튼시 및 데이터 전송률이 구체화된 다음에 결정되는 합성 변조 및 전방 에러 수정 코딩방법.
제1항에 있어서,

상기 LDPC코드는 가변 코드워드 길이(variable codeword length)를 갖는 합성변조 및 전방 에러 수정 코딩방법.
제8항에 있어서,

상기 코드워드 길이는 데이터 전송률 및 레이튼시 중 하나이상에 의해 변화되는 합성 변조 및 전방 에러 수정 코딩방법.
제1항에 있어서,

상기 LDPC 코드는 소정의 사이클(cycle)을 갖지 않는 합성 변조 및 전방 에러 수정 코딩방법.
제1항에 있어서,

LDPC코드의 패리티 검사 행렬은 적어도 하나의 정보 비트 및 적어도 하나의 패리티 노드를 구비한 적어도 하나의 패리티 비트를 연결하는 동일한 개수의 브랜치(bramch)를 갖는 합성 변조 및 전방 에러 수정 코딩방법.
제1항에 있어서,

패리티 검사 행렬은 동일한 개수의 정보 비트 및 패리티 비트에 연결되는 적어도 하나의 패리티 노드를 포함하는 합성 변조 및 전방 에러 수정 코딩방법.
LDPC코드를 이용하여 데이터 비트 신호의 전방 에러 수정 코딩방법에 있어서,

데이터 전송률 및 레이튼시 중 적어도 하나를 결정하는 단계와,

데이터 비트 신호를 엔코딩하는(encode) LDPC 생성 행렬을 결정하는 단계

를 포함하는 전방 에러 수정 코딩방법.
제13항에 있어서,

상기 데이터 전송률 및 레이튼시 중 적어도 하나는 초기화 또는 구성 상태 동안 결정되는 전방 에러 수정 코딩방법.
제13항에 있어서,

상기 LDPC 생성 행렬은 데이터 전송률 및 레이튼시가 결정된 다음에 결정되는 전방 에러 수정 코딩방법.
재13항에 있어서,

상기 LDPC코드는 가변 코드워드 길이를 갖는 전방 에러 수정 코딩방법.
제16항에 있어서,

상기 코드워드 길이는 데이터 전송률 및 레이튼시 중 하나이상에 의해 변화되는 전방 에러 수정 코딩방법.
제13항에 있어서,

상기 LDPC코드는 소정의 사이클을 갖지 않는 전방 에러 수정 코딩방법.
LDPC코드를 이용하는 데이터 비트 신호의 전방 에러 수정 디코딩하는 방법에 있어서,

데이터 전송률 및 레이튼시 중 적어도 하나를 결정하는 단계와,

코딩된 비트 신호를 디코딩하는 LDPC 패리티 검사 행렬을 결정하는 단계

를 포함하는 전방 에러 수정 디코딩방법.
제19항에 있어서,

상기 데이터 전송률 및 레이튼시 중 적어도 하나는 초기화 또는 구성 상태 동안에 결정되는 전방 에러 수정 디코딩방법.
제19항에 있어서,

상기 LDPC 패리티 검사 행렬은 데이터 전송률 및 레이튼시가 결정된 다음에 결정되는 전방 에러 수정 디코딩방법.
재19항에 있어서,

상기 LDPC코드는 가변 코드워드 길이를 갖는 전방 에러 수정 디코딩방법.
제22항에 있어서,

상기 코드워드 길이는 데이터 전송률 및 레이튼시 중 적어도 하나에 의해 변화되는 전방 에러 수정 디코딩방법.
제19항에 있어서,

상기 LDPC코드는 임의의 사이클을 갖지 않는 전방 에러 수정 디코딩방법.
LDPC코드를 이용하여 데이터 비트 신호의 전방 에러 수정 코딩을 실행하는 정보를 포함하는 정보저장매체에 있어서,

데이터 전송률 및 레이튼시 중 적어도 하나를 결정하는 정보와,

데이터 비트 신호를 엔코딩하는 LDPC 생성 행렬을 결정하는 정보

를 포함하는 정보저장매체.
제25항에 있어서,

상기 데이터 전송률 및 레이튼시 중 적어도 하나는 초기화 또는 구성 상태 동안에 결정되는 정보저장매체.
제25항에 있어서,

상기 LDPC 생성 행렬은 데이터 전송률 및 레이튼시가 결정된 다음에 결정되는 정보저장매체.
재25항에 있어서,

상기 LDPC코드는 가변 코드워드 길이를 갖는 정보저장매체.
제28항에 있어서,

상기 코드워드 길이는 데이터 전송률 및 레이튼시 중 하나이상에 의해 변화되는 정보저장매체.
제25항에 있어서,

상기 LDPC코드는 소정의 사이클을 갖지 않는 정보저장매체.
LDPC코드를 이용하여 데이터 비트 신호의 전방 에러 수정 디코딩을 실행하는 정보를 포함하는 정보저장매체에 있어서,

데이터 전송률 및 레이튼시 중 적어도 하나를 결정하는 정보와,

데이터 비트 신호를 디코딩하는 LDPC 패리티 검사 행렬을 결정하는 정보

를 포함하는 정보저장매체.
제31항에 있어서,

데이터 전송률 및 레이튼시 중 적어도 하나는 초기화 또는 구성 상태 동안에결정되는 정보저장매체.
제31항에 있어서,

상기 LDPC 패리티 검사 행렬은 데이터 전송률 및 레이튼시가 결정된 다음에 결정되는 정보저장매체.
제31항에 있어서,

상기 LDPC코드는 가변 코드워드 길이를 갖는 정보저장매체.
제34항에 있어서,

상기 코드워드 길이는 데이터 전송률 및 레이튼시 중 하나이상에 의해 변화되는 정보저장매체.
제31항에 있어서,

상기 LDPC코드는 소정의 사이클을 갖지 않는 정보저장매체.