KR101330132B1

KR101330132B1 - 랩터 코드의 디코딩

Info

Publication number: KR101330132B1
Application number: KR1020087017334A
Authority: KR
Inventors: 웬 가오
Original assignee: 톰슨 라이센싱
Priority date: 2006-02-08
Filing date: 2007-01-31
Publication date: 2013-11-18
Anticipated expiration: 2027-01-31
Also published as: EP1985022A1; JP2009526476A; KR20080099243A; US8239727B2; EP1985022B1; JP5237119B2; CN101379712A; CN101379712B; US20090055705A1; WO2007092214A1

Abstract

랩터 코드로 인코딩된 패킷의 시퀀스를 디코딩하는 방법(200) 및 디코더(14)가 제공된다. 인코딩된 심벌과 중간 심벌(215) 사이의 관계를 확립하는 행렬의 랭크에 따라 손실되거나 손상된 패킷(225)을 회복시키는 방법에 대한 결정이 이루어진다. 행렬이 풀 랭크의 것이라면, 모든 중간 심벌이 역추적 동작(250)에 의해 회복되고, 풀 디코딩 또는 회복이 수행될 수 있다(255). 행렬이 풀 랭크가 아니지만 그것의 랭크가 임계값 위에 있다면, 부분적인 회복이 수행되고(235) 디코딩이 완전히 수행될 수 없다(240). 하지만 행렬의 랭크가 임계값 아래에 있다면, 어떠한 회복 또는 디코딩도 수행되지 않는다(230, 299).

Description

랩터 코드의 디코딩{DECODING OF RAPTOR CODES}

관련 출원에 대한 상호 참조

본 출원은 2006년 2월 8일 출원된 미국 가 출원 일련 번호 60/771,377호의 이익을 주장하고, 그 전문은 본 명세서에 참조로 통합되어 있다.

본 발명의 원리는 일반적으로 파운틴 코드(fountain code)에 관한 것으로, 랩터(raptor) 코드를 디코딩하는 방법 및 장치에 관한 것이다.

3세대 파트너십 프로젝트(3GPP: 3rd Generation Partnership Project)는 1998년 12월 설립된 제휴 협정이다. 이 제휴 협정은 조직상의 파트너라고 알려지는 다수의 원격통신 표준체를 모은다. 3GPP의 원리의 범주는 진화된 이동 통신용 글로벌 시스템(GSM: Global Systems for Mobile communication) 코어 네트워크와 그것들이 지원하는 무선 접속 기술{즉, 주파수 분할 이중통신(FDD: Frequency Division Duplex)와 시분할 이중통신(TDD: Time Division Duplex) 모드 모두를 포함하는 포괄적인 지상파 무선 접속(UTRA: Universal Terrestrial Radio Access)}에 기초한 3세대 이동 모바일 시스템에 대한 글로벌하게 적용할 수 있는 기술 규격과 기술 보고서를 만들어내는 것이었다. 그 후 그 범주는 GSM 기술 규격의 유지 및 개발과, 진화된 무선 접속 기술을 포함하는 기술 보고서를 포함하도록 개정되었다{즉, 일반 적인 패킷 무선 서비스(GPRS: General Packet Radio Service)와 GSM 진화를 위한 강화된 데이터 속도(EDGE)}.

체계적인 랩터 코드는 3GPP 멀티미디어 방송/멀티미디어 서비스(MBMS)를 위한 응용 층 순방향 에러 정정(FEC) 코드로서 채택된다. 랩터 코드를 디코딩하기 위해, 디코더는 통상 선형 수학식의 시스템을 구성하고, 그 수학식을 풀기 위해 가우스 소거법(Gaussian elimination)을 사용한다. 하지만, 그 시스템이 풀 랭크(full rank)의 것이 아닐 때에는(즉, 수신된 소스와 패리티 패킷이 완전한 디코딩에는 적당하지 않는), 디코더가 보통 실패를 선언하고 수신된 소스 패킷만을 출력한다.

종래 기술의 이들 및 다른 결점과 단점은 본 발명의 원리에 의해 다루어지고, 이러한 본 발명의 원리는 랩터 코드를 디코딩하는 방법 및 장치에 관한 것이다.

본 발명의 원리의 일 양상에 따르면, 장치가 제공된다. 이 장치는 인코딩 심벌의 시퀀스를 나타내는 패킷의 시퀀스를 디코딩하는 디코더를 포함한다. 이 디코더는 랩터 코드를 사용하여 시퀀스의 적어도 일부 손실되거나 손상된 패킷을 적어도 부분적으로 회복시킨다.

본 발명의 원리의 또다른 양상에 따르면, 방법이 제공된다. 이 방법은 인코딩 심벌의 시퀀스를 나타내는 패킷의 시퀀스를 디코딩하는 단계를 포함한다. 이 디코딩 단계는 랩터 코드를 사용하여 시퀀스의 적어도 일부 손실되거나 손상된 패킷을 적어도 부분적으로 회복시킨다.

본 발명의 원리의 이들 및 다른 양상, 특성 및 장점은, 첨부 도면과 함께 읽어질 다음에 나오는 예시적인 실시예의 상세한 설명으로부터 분명해진다.

본 발명의 원리는 다음에 나오는 예시적인 도면에 따라 더 잘 이해될 수 있다.

도 1은 본 발명의 원리의 일 실시예에 따라, 본 발명의 원리가 적용될 수 있는 예시적인 비디오 인코딩/디코딩 환경에 대한 블록도.

도 2는 본 발명의 원리의 일 실시예에 따라, 랩터 코드를 디코딩하는 예시적인 방법에 대한 흐름도.

본 발명의 원리는 랩터 코드를 디코딩하는 방법 및 장치에 관한 것이다.

본 설명은 본 발명의 원리를 예시한다. 그러므로 당업자라면, 비록 본 명세서에서 명백히 설명되거나 도시되지 않더라도, 본 발명의 원리를 구현하고 본 발명의 원리의 사상과 범주 내에 포함되는 다양한 장치를 고안할 수 있을 것이라는 점을 알게 된다.

본 명세서에서 인용된 모든 예와 조건부 언어는, 읽는 사람이 본 발명의 발명자에 의해 관련 분야에 제공된 본 발명의 원리와 개념을 이해하는 것을 돕기 위한 교육학적인 목적을 위해 의도되고, 그러한 특별히 인용된 예와 조건에 제한되지 않는 것으로 여겨져야 한다.

게다가, 특별한 예들과 함께 본 명세서에서 원리, 양상 및 본 발명의 원리의 실시예를 인용하는 모든 문장은 그 구조상 및 기능상 등가물을 망라하는 것으로 의도된다. 추가로, 그러한 등가물은 앞으로 개발된 등가물과 함께 현재 알려진 등가물, 즉 그 구조와 관계없이 동일한 기능을 수행하는 임의의 개발된 요소들 모두를 포함하는 것으로 의도된다.

그러므로, 예컨대 당업자라면 본 명세서에서 표현된 블록도가 본 발명의 원리를 구현하는 예시적인 회로의 개념도를 나타낸다는 것을 알게 된다. 유사하게, 임의의 흐름 차트, 흐름도, 상태 전이도, 의사코드 등이 컴퓨터 판독 가능 매체에서 실질적으로 표현될 수 있고 명백히 도시되거나 도시되지 않은 컴퓨터나 프로세서에 의해 실행될 수 있는 다양한 프로세스를 나타낸다는 것을 알게 된다.

도면에 도시된 다양한 요소들의 기능은, 적절한 소프트웨어와 관련하여 소프트웨어를 실행할 수 있는 하드웨어와 함께 전용 하드웨어의 사용을 통해 제공될 수 있다. 프로세서에 의해 제공될 때, 그 기능은 단일 전용 프로세서, 단일 공유된 프로세서 또는 복수의 개별 프로세서에 의해 제공될 수 있고, 그들 중 일부는 공유될 수 있다. 게다가, "프로세서" 또는 "제어기"와 같은 용어의 명시된 사용은, 소프트웨어를 실행할 수 있는 하드웨어만을 가리키는 것으로 여겨져서는 안 되고, 디지털 신호 프로세서("DSP") 하드웨어, 소프트웨어를 저장하기 위한 읽기 전용 메모리("ROM"), 랜덤 액세스 메모리("RAM") 및 비휘발성 저장기를, 제한 없이 암시적으로 포함할 수 있다.

종래의 및/또는 일상적인 다른 하드웨어가 또한 포함될 수 있다. 유사하게, 도면에 도시된 임의의 스위치는 단지 개념상의 것이다. 그것들의 기능은 프로그램 로직의 동작, 적용 로직, 프로그램 제어와 전용 로직의 상호 작용을 통해 실행될 수 있거나 심지어 수동식으로는 상황에 따라 더 특별히 이해되듯이 그 구현자에 의한 특별한 기술이 선택 가능하다.

청구항에서, 특정된 기능을 수행하기 위한 수단으로서 표현된 임의의 요소는, 예컨대 a) 그 기능을 수행하는 회로 요소들의 조합 또는 b) 그 기능을 수행하기 위해 소프트웨어를 실행하기 위한 적절한 회로와 결합된 펌웨어, 마이크로코드 등을 포함하는 임의의 형태의 소프트웨어를 포함하는 것과 같이 그 기능을 수행하는 임의의 방식을 망라하는 것으로 의도된다. 청구항에 의해 한정된 것과 같은 본 발명의 원리는 다양한 인용된 수단에 의해 제공된 기능들이, 청구항이 주장하는 방식으로 결합되고 모아진다는 사실에 그 성질에 존재한다. 그러므로 그러한 기능들을 제공할 수 있는 임의의 수단은 본 명세서에 도시된 것들과 등가인 것으로 간주된다.

명세서에서 본 발명의 원리의 "일 실시예" 또는 "실시예"를 참조한다는 것은, 그러한 실시예와 관련하여 설명된 특별한 특성, 구조, 특징 등이 본 발명의 원리의 적어도 일 실시예에 포함되는 것을 의미한다. 그러므로, 명세서 전반에 걸쳐 여러 곳에 등장하는 "일 실시예에서" 또는 "실시예에서"라는 어구의 등장은 반드시 동일한 실시예를 모두 가리키는 것은 아니다.

도 1을 참조하면, 본 발명의 원리가 적용될 수 있는 예시적인 비디오 인코딩/디코딩 환경이 일반적으로 참조 번호 100으로 표시되어 있다. 비디오 인코딩/디코딩 환경(100)은 패킷화 및 랩터 인코더(120)의 입력과의 교신에 연결된 출력을 가 지는 비디오 인코더(110)를 포함한다. 패킷화 및 랩터 인코더(120)의 출력은 무선/유선 네트워크(130)의 액세스 포인트와의 교신에 연결된다. 무선/유선 네트워크(130)의 또다른 액세스 포인트는 역-패킷화(de-packetization) 및 랩터 디코더(140)의 입력과의 교신에 연결된다. 역-패킷화 및 랩터 디코더의 출력은 비디오 인코더(150)의 입력과의 교신에 연결된다.

비디오 인코더(110)는 인코딩될 입력 비디오 신호를 수신하고 인코딩된 비트스트림을 출력한다. 패킷화 및 랩터 인코더(120)는 랩터 코드를 사용하여 비디오 인코더로부터 인코딩된 비트스트림 출력을 인코딩하고, 무선/유선 네트워크(130)를 통한 송신을 위해 그 결과 비트스트림을 패킷화한다. 역-패킷화 및 랩터 디코더(140)는 비디오 디코더(150)에 의한 다음 디코딩을 위한 비트스트림을 얻기 위해, 랩터 코드의 디코딩을 위해 송신된 비트스트림을 역-패킷화한다. 랩터 코드의 인코딩 및 디코딩은 아래에 더 상세히 설명된다.

일 실시예에서, 본 발명의 원리는 예컨대 역-패킷화 및 랩터 인코더(140)에 관해 구현될 수 있다는 것을 알아야 한다. 하지만, 도 1의 예시적인 비디오 인코딩/디코딩 환경(100)은 본 발명의 원리가 적용될 수 있는 많은 환경 및 애플리케이션 중 하나라는 점을 또한 알아야 한다. 즉, 본 명세서에서 제공된 본 발명의 원리의 가르침이 주어진다면 당업자가 본 발명의 원리의 범주를 유지하면서, 본 발명의 원리에 따라 랩터 코드의 디코딩이 적용될 수 있는 이러한 그리고 다양한 다른 환경 및 애플리케이션을 예상하게 된다. 예컨대, 본 발명의 원리는 파운틴 코드와 에러 정정 코드에 관해 이용될 수 있는 임의의 타입의 데이터에 관해 구현될 수 있다.

본 발명의 원리에 따르면, 랩터 코드를 디코딩하기 위한 방법 및 장치가 개시된다. 일 실시예에서 본 발명의 원리의 구현예는 심지어 수신된 소스와 패리티 패킷이 완전한 디코딩을 위해서는 부적당할 때에도{즉, 심지어 시스템이 풀 랭크(full rank)의 것이 아닐 때에도} 가능한 많이 패킷을 회복시킨다.

일 실시예에서, 랩터 코드는 다음과 같이 인코딩된다. 다음에서, 비트의 스트링인, 인코딩 프로세스에서의 패킷을 나타내기 위해 심벌을 사용한다. 체계적인 랩터 코드는 비-체계적인 랩터 코드에 기초하여 발생된다. 그러므로, 먼저 비-체계적인 랩터 코드를 도입한다.

비-체계적인 랩터 코드는, 예컨대 3GPP의 경우 3개의 층을 포함할 수 있는 계층적(layered) 코드이다. 물론, 상이한 개수의 층이 또한 이용될 수 있다. K개의 중간 심벌인 [C[0],C[1],...,C[K-1]]^T이 주어지면(이들 K개의 중간 심벌은 실제로 비-체계적인 랩터 코드에 대한 K개의 소스 심벌이고, 체계적인 랩터 코드에 대해서는 K개의 중간 심벌이 K개의 소스 심벌을 사용하여 얻어지며, 이는 또한 아래에 설명된다), 먼저 다음과 같이 고속의 LDPC 코드를 사용하는 S개의 저밀도 패리티 체크(LDPC: low density parity check) 심벌을 발생시킨다.

여기서, H_LDPC는 S ×K 저밀도 패리티 행렬을 나타낸다. 그 다음 그레이 시퀀 스(Gray sequence)를 이용하는 고밀도 패리티 체크 행렬을 사용하는 H개의 하프 심벌(half symbol)을 다음과 같이 발생시킨다.

여기서, H_half는 H ×(K+S) 고밀도 행렬이다. 그러므로, L=K+S+H개의 중간 심벌을 다음과 같이 얻는다.

H_LDPC와 H_half는 요소 0 또는 요소 1을 지닌 행렬이다는 점을 주목하라. 비트-크기의(bit-wise)의 XOR 연산은 행렬-벡터 곱셈에서 덧셈을 수행하기 위해 사용될 수 있다.

인코딩 심벌은 루비 변환(LT: Luby Transform) 행렬을 사용하여 다음과 같이 발생될 수 있다.

H_LT는 L개의 열을 지닌 저밀도 패리티 행렬이고, 행의 개수는 얼마나 많은 인코딩 심벌을 발생시키기를 원하는지에 따라 달라질 수 있다. 이론상으로는 만들어질 수 있는 인코딩 심벌의 개수는 무한하다. 또한, 한 행에서의 1들의 개수는 루비 변환 분포를 따른다. 루비 변환 분포는 도(degree)가 인코딩 심벌을 형성하기 위해 함께 XOR되는(XORed) 중간 심벌의 개수를 의미하는, 인코딩 심벌의 도의 분포이다. 루비 변환 분포는 표 1에 도시되어 있다.

도	P(도)
1	0.0098
2	0.4590
3	0.2110
4	0.1134
10	0.1113
11	0.0799
40	0.0156

실제로, 비-체계적인 랩터 코드에 대해서는 인코딩 심벌이 인코더에서 발생되고 수신기 측으로 송신된다. 채널의 불안정성으로 인해, 인코딩 심벌의 일부는 손실된다. 디코더의 과제는 수신된 인코딩 심벌이 주어질 때 소스 심벌인 [C[0],C[1],...,C[K-1]]^T를 회복시키는 것이다.

체계적 랩터 코드에 대해서, 첫 번째 K개의 인코딩 심벌은 통상적으로 소스 심벌이다. 나머지 인코딩 심벌을 생성하기 위해, 우리는 L개의 중간 심벌인 [C[0],C[1],...,C[L-1]]^T를 계산한다. 비-체계적인 랩터 코드의 구성 프로세스로부터 다음 관계를 가진다.

행렬{(H_LT)_{K ×(K+S+H)},H_LDPC,H_Half}은 행렬(A)이 풀 랭크의 것, 즉 L이 되도록 구성된다. 그러면, 중간 심벌인 [C[0],C[1],...,C[L-1]]^T가 위 수학식들을 풂으로써 계산될 수 있다. (H_LT)_{K ×(K+S+H)}는 반-무한(semi-infinite) 행렬(H_LT)의 첫 번째 K 행들을 포함한다는 것을 주목하라. 행렬(H_LT)의 다른 행들과, L개의 중간 심벌을 사용하여 모든 다른 인코딩 심벌이 발생될 수 있다. 행렬(I_S _×S,I_H _×H)은 각각 차원이 S ×S와 H ×H인 단위 행렬이다. 행렬(0_{S ×H})은 차원이 S ×H인 모두 0인 행렬이다.

그러므로, 전술한 바와 같이 체계적인 랩터 코드에 대해서는 인코딩 프로세스가 수학식 5마다 한 세트의 선형 수학식을 푸는 단계를 수반한다. 행렬(A)이 희소(sparse) 행렬이므로, 수학식 5를 푸는 복잡도는 비교적 낮다.

실제로, 체계적인 랩터 코드에 대해서, 디코더의 과제는 수신된 인코딩 심벌이 주어질 때 첫 번째 K개의 인코딩 심벌인 [E[0],E[1],...,E[K-1]]^T를 회복시키는 것이다.

통상적으로, 랩터 코드는 다음과 같이 디코딩된다. 그 디코딩 프로세스는 인코딩 프로세스와 유사하다. 인덱스가 {I₀, I₁,...,I_M _-1}인 M개의 인코딩 심벌을 수신한다고 가정한다. M개의 인코딩 심벌에 대응하는 H_LT 행렬의 행들은 차원이 M ×L인 새로운 행렬(

)을 형성한다. 따라서 디코딩 프로세스는 다음과 같은 선형 시스템을 푸는 단계를 수반한다.

실제로, 수학식 6의 선형 시스템은 행렬(B)이 랭크(L)의 것일 때, 풀 수 있다. 그렇지 않으면, 디코더는 수신된 소스 심벌, 즉 수신된 인코딩 심벌의 세트인 {E[I_i]|0 ≤I_i ≤(K-1)}만을 출력한다.

일 실시예에서, 랩터 코드는 다음과 같이 디코딩된다. 이 실시예는 가능한 많은 소스 심벌의 회복을 허용한다. 이 실시예는 일반적으로 처음에 설명되고, 그 다음 도 2에 관한 또다른 설명이 이어진다.

랩터 코드를 디코딩하기 위해, 수학식 6의 선형 시스템이 인덱스가 {I₀, I₁,...,I_M-1}인 수신된 M개의 인코딩 심벌에 기초하여 구성된다. 가우스 소거법이 행 렬(B)을 상삼각 행렬로 전환하기 위해 사용될 수 있다. 물론, 본 발명의 원리는 가우스 소거법의 사용에만 제한되지 않고 따라서 본 발명의 원리의 범주를 유지하면서, 다른 방법들이 행렬(B)을 상삼각 행렬로 전환하기 위해 사용될 수 있다. 삼각법(triangulation)이 성공하면, 즉 행렬(B)이 랭크가 L인 것이라면, 중간 심벌인 [C[0],C[1],...,C[L-1]]^T를 얻기 위해 역추적 접근법이 사용된다. 잃어버린 소스 심벌은 수학식 4를 사용하여 계산될 수 있다.

삼각법이 실패한다면, 즉 행렬(B)의 랭크가 L보다 작다면, 통상적인 결과는 디코딩 프로세스가 중단되는 것이다. 하지만, 본 발명의 원리의 일 실시예에 따르면 [C[p₀],C[p₁],...,C[p_W _-1]]^T과 같이 표현되는 중간 심벌의 서브세트를 얻기 위해 역추적 동작을 여전히 수행하는데, 여기서 p_i는 중간 심벌의 인덱스를 표시하고 W는 회복된 중간 심벌의 개수를 표시하며, 0 ≤p_i ≤L이고 W<L이다. 잃어버린 소스 심벌의 서브세트는 수학식 4와 [C[p₀],C[p₁],...,C[p_W _-1]]^T를 사용하여 계산될 수 있다.

예시를 위해, 부분적으로 회복된 중간 심벌을 사용하여 잃어버린 소스 심벌을 회복하는 것과 역추적 동작에 관한 일 예를 제공한다. 먼저, L=3이라고 가정하고 삼각법을 적용한 후, 다음 선형 시스템을 얻는다.

여기서, 행렬(B)은 풀 랭크의 것이다. 그러므로, 역추적 동작은 성공적으로 수행될 수 있는데, 즉 먼저 시스템의 세 번째 행으로부터, C[2]=1을 얻고 그러면 두 번째 행으로부터 C[1]

C[2]=0이 되고, C[1]=1을 얻으며, 마지막으로 첫 번째 행으로부터 C[0]

C[1]=1이 되고, C[0]=0을 얻는다. 모든 중간 심벌을 회복하였으므로 수학식 4를 사용하여 모든 잃어버린 소스 심벌을 계산할 수 있다.

이제, 부분적으로 회복된 중간 심벌을 사용하여 잃어버린 소스 심벌의 회복을 설명한다. 마찬가지로, L=3이라고 가정하면 소스 심벌인 E[0]를 잃어버리게 되고 E[0]=C[0]가 된다. 삼각법 적용 후, 다음과 같은 선형 시스템을 가진다.

행렬(B)의 랭크는 풀 랭크가 아닌 단지 2라는 점을 주목하라. 오직 2개의 중간 심벌을 회복시킬 수 있는데, 즉 먼저 시스템의 두 번째 행으로부터 C[1]=0을 얻게 되고, 시스템의 첫 번째 행으로부터 C[0]

C[1]=1이 되며, C[0]=1을 얻는다. 비록 중간 심벌인 C[2]가 회복되지 않을지라도, E[0]=C[0]이기 때문에 여전히 잃어버린 심벌인 E[0]=1을 계산할 수 있다.

일 실시예에서, 위에서 설명한 역추적 동작은 행렬(B)의 랭크가 미리 특정된 임계값보다 클 때에만 수행된다. 이는, 예컨대 행렬(B)의 랭크가 작을 때와 같이 일부 계산을 덜 수 있고, 중간 심벌의 얻어진 서브세트는 작은 세트이다. 일부 소스 심벌을 회복시키는 확률은 마찬가지로 낮다.

도 2를 참조하면, 랩터 코드를 디코딩하는 예시적인 방법이 일반적으로 참조 번호(200)로 표시되어 있다. 이 방법(200)은 제어를 기능 블록(210)으로 넘기는 시작 블록(205)을 포함한다. 기능 블록(210)은 인덱스{I₀, I₁,...,I_M _-1}를 지닌 인코딩 심벌을 수신하고, 제어를 기능 블록(215)에 넘긴다. 기능 블록(215)은 수학식 6을 사용하여 수신된 인코딩 심벌에 기초하여 수학식의 선형 시스템을 구성하고 제어를 기능 블록(220)에 넘긴다. 기능 블록(220)은, 예컨대 가우스 소거법을 사용하여 수학식 6에서 행렬(B)의 상삼각법을 수행하고 제어를 결정 블록(225)에 넘긴다. 결정 블록(225)은 행렬(B)의 랭크가 랭크(L)보다 작은지 여부를 결정한다. 만약 그렇다면 제어는 결정 블록(230)으로 넘어간다. 만약 그렇지 않다면 제어는 기능 블록(250)으로 넘어간다.

결정 블록(230)은 행렬(B)의 랭크가 임계값보다 큰지 여부를 결정한다. 만약 그렇다면, 제어는 기능 블록(235)으로 넘어간다. 만약 그렇지 않다면 제어는 종료 블록(299)으로 넘어간다.

기능 블록(235)은 인덱스{p(0), p(1), p(W-1)}를 지닌 중간 심벌을 회복하기 위해 역추적 동작을 사용하고, 여기서 W<L이며 제어를 기능 블록(240)으로 넘긴다. 기능 블록(240)은 인덱스{p(0), p(1), p(W-1)}를 지닌 중간 심벌과 수학식 4를 사용하여 잃어버린 소스 심벌의 서브세트를 얻고, 제어를 종료 블록(299)에 넘긴다.

기능 블록(250)은 모든 중간 심벌을 회복하기 위해 역추적 동작을 사용하고 제어를 기능 블록(255)에 넘긴다. 기능 블록(255)은 수학식 4를 사용하여 모든 잃 어버린 소스 심벌을 얻고, 제어를 종료 블록(299)에 넘긴다.

이제 본 발명의 많은 부수적인 장점/특성의 일부에 대한 설명이 주어지고, 그 중 일부는 위에서 언급된 것이다. 예컨대, 장치의 한 가지 장점/특성은 인코딩 심벌의 시퀀스를 나타내는 패킷의 시퀀스를 디코딩하기 위한 디코더를 포함한다는 점이다. 이 디코더는 랩터 코드를 사용하여 시퀀스의 손실되거나 손상된 패킷의 적어도 일부를 적어도 부분적으로 회복한다.

또다른 장점/특성은 전술한 바와 같은 디코더를 가지는 장치로서, 이 경우 디코더는 인코딩 심벌에 기초한 수학식의 선형 시스템을 구성하고, 이러한 수학식의 선형 시스템은

로 표현되며, 여기서 E는 인덱스{I₀, I₁,...,I_M-1}를 지닌 인코딩 심벌을 나타내고, M은 그 인코딩 심벌의 개수를 나타내며, C[0], C[1],...C[L-1]은 패킷의 시퀀스로 인코딩될 중간 심벌을 나타내고, K는 체계적이지 않은 랩터 코드를 사용할 때의 중간 심벌의 서브세트에 대응하거나 체계적인 랩터 코드를 사용할 때의 인코딩 심벌의 서브세트에 대응하는 소스 심벌의 개수를 나타내며, S는 중간 심벌로부터 발생된 저밀도 패리티 체크 심벌을 나타내고, H_LDPC는 저밀도 패리티 체크 심벌을 발생시키기 위해 사용된 행렬을 나타내며, H는 중간 심벌로부터 발생된 절반의 심벌을 나타내고, H_Half는 절반의 심벌을 발생시키기 위해 사용된 행렬을 나타내며,

는 인코딩 심벌을 발생시키기 위한 행렬을 나타내고, I_{S ×S}는 차원(S ×S)의 단위 행렬(identity matrix)을 나타내며, O_{S ×H}는 차원(S ×H)의 0(zero) 행렬을 나타내고, I_{H ×H}는 차원(H ×H)의 단위 행렬을 나타내며, B는 행렬을 나타내고, L은 중간 심벌의 개수를 나타낸다.

또다른 장점/특성은 전술한 바와 같은 수학식의 선형 시스템을 구현하는 디코더를 가지는 장치로서, 이 경우 디코더는 행렬(B)을 상삼각 행렬로 전환한다.

또한 또다른 장점/특성은 전술한 바와 같은 상삼각 행렬로 행렬(B)을 전환하고 수학식의 선형 시스템을 구성하는 디코더를 가지는 장치로서, 이 경우 디코더는 가우스 소거법을 사용하여 행렬(B)을 상삼각 행렬로 전환한다.

또한 또다른 장점/특성은 전술한 바와 같은 상삼각 행렬로 행렬(B)을 전환하고 수학식의 선형 시스템을 구성하는 디코더를 가지는 장치로서, 이 경우 디코더는 [C[p₀],C[p₁],...,C[p_W-1]]^T과 같이 표현되는 중간 심벌의 적어도 일부를 회복하기 위해 역추적 동작을 수행하고, 여기서 p_i는 적어도 일부의 중간 심벌 중 특정의 것의 인덱스를 표시하고 W는 적어도 일부의 중간 심벌의 개수를 표시하며, 0 ≤p_i ≤L이고 W<L이며, 행렬(B)의 상삼각 행렬로의 전환이 실패할 때,

를 사용하여 적어도 일부의 중간 심벌로부터 손실되거나 손상된 패킷에 대응하는 손실되거나 손상된 소스 심벌을 계산한다.

추가로, 또다른 장점/특성은 수학식의 선형 시스템을 구성하고, 행렬(B)을 상삼각 행렬로 전환하며, 전술한 바와 같은 역추적 동작을 수행하는 디코더를 가지는 장치로서, 이 경우 디코더는 행렬(B)의 랭크가 미리 특정된 임계값보다 클 때에만 역추적 동작을 수행한다.

게다가, 또다른 장점/특성은 전술한 바와 같은 디코더를 가지는 장치로서, 이 경우 디코더는 인코딩 심벌에 대응하는 중간 심벌의 서브세트를 얻기 위해 역추적 동작을 수행하고, 중간 심벌의 서브세트로부터 적어도 일부의 손실되거나 손상된 패킷에 대응하는 잃어버리거나 손상된 소스 심벌을 계산한다.

본 발명의 원리의 이들 및 다른 특성 및 장점은, 본 명세서의 가르침에 기초하여 당업자에 의해 바로 확인될 수 있다. 본 발명의 원리의 가르침은 다양한 형태의 하드웨어, 소프트웨어, 펌웨어, 특별한 목적의 프로세서 또는 이들의 조합으로 구현될 수 있음이 이해되어야 한다.

가장 바람직하게는, 본 발명의 가르침이 하드웨어와 소프트웨어의 조합으로서 구현된다. 게다가, 그러한 소프트웨어는 프로그램 저장 유닛에서 실체적으로 구현된 애플리케이션 프로그램으로서 구현될 수 있다. 이 애플리케이션 프로그램은, 임의의 적합한 아키텍처를 포함하는 기계에 업로드되거나 그러한 기계에 의해 실행될 수 있다. 바람직하게, 그 기계는 하나 이상의 중앙 처리 장치("CPU"), 랜덤 액세스 메모리("RAM"), 입력/출력("I/O") 인터페이스와 같은 하드웨어를 가지는 컴퓨터 플랫폼에서 구현된다. 이 컴퓨터 플랫폼은 또한 운영 체제와 마이크로인스트럭션 코드를 포함할 수 있다. 본 명세서에서 설명된 다양한 프로세스와 기능은 마이크로인스트럭션 코드의 부분 또는 애플리케이션 프로그램의 부분 또는 CPU에 의해 실행될 수 있는 이들의 임의의 조합일 수 있다. 또한, 추가 데이터 저장 장치와 인쇄 장치와 같은 다양한 다른 주변 장치가 컴퓨터 플랫폼에 연결될 수 있다.

첨부 도면에 도시된 시스템 구성 성분과 방법의 일부가 바람직하게는 소프트웨어로 구현되기 때문에, 시스템 성분이나 프로세스 기능 블록 사이의 실제 연결은 본 발명의 원리가 프로그래밍되는 방식에 따라 상이할 수 있다는 점이 또한 이해되어야 한다. 당업자는 본 명세서에서의 가르침이 주어지면 본 발명의 원리의 이들 및 유사한 구현예 또는 구성예를 예상할 수 있다.

비록 본 명세서에서 첨부 도면을 참조하여 예시적인 실시예가 설명되었지만, 본 발명의 원리는 이들 정확한 실시예에 제한되지 않고, 본 발명의 원리의 범주 또는 사상으로부터 벗어나지 않으면서 당업자에 의해 다양한 변경과 수정이 이루어질 수 있음이 이해되어야 한다. 모든 그러한 변경 및 수정은 첨부된 청구항에서 전개된 본 발명의 원리의 범주 내에 포함되는 것으로 의도된다.

전술한 바와 같이, 본 발명은 파운틴 코드에 관한 것으로, 랩터 코드를 디코 딩하는 방법 및 장치에 이용 가능하다.

Claims

장치로서,

인코딩 심벌의 시퀀스를 나타내는 패킷의 시퀀스를 디코딩하는 디코더(140)를 포함하고,

디코더는 랩터 코드를 사용하여 시퀀스의 적어도 일부 손실되거나 손상된 패킷을 적어도 부분적으로 회복시키고, 디코더(140)는 인코딩 심벌에 기초한 수학식의 선형 시스템을 구성하고(215), 수학식의 선형 시스템은

로 표현되며, 여기서 E는 인덱스{I₀, I₁,...,I_M-1}를 지닌 인코딩 심벌을 나타내고, M은 그 인코딩 심벌의 개수를 나타내며, C[0], C[1],...C[L-1]은 패킷의 시퀀스로 인코딩될 중간 심벌을 나타내고, K는 체계적이지 않은 랩터 코드를 사용할 때의 중간 심벌의 서브세트에 대응하거나 체계적인 랩터 코드를 사용할 때의 인코딩 심벌의 서브세트에 대응하는 소스 심벌의 개수를 나타내며, S는 중간 심벌로부터 발생된 저밀도 패리티 체크 심벌을 나타내고, H_LDPC는 저밀도 패리티 체크 심벌을 발생시키기 위해 사용된 행렬을 나타내며, H는 중간 심벌로부터 발생된 절반의 심벌을 나타내고, H_Half는 절반의 심벌을 발생시키기 위해 사용된 행렬을 나타내며,
는 인코딩 심벌을 발생시키기 위한 행렬을 나타내고, I_{S ×S}는 차원(S ×S)의 단위 행렬(identity matrix)을 나타내며, O_{S ×H}는 차원(S ×H)의 0(zero) 행렬을 나타내고, I_{H ×H}는 차원(H ×H)의 단위 행렬을 나타내며, B는 행렬을 나타내고, L은 중간 심벌의 개수를 나타내는, 장치.
삭제
제 1항에 있어서, 디코더(140)는 행렬(B)을 상삼각 행렬(upper triangulation matrix)로 전환하는, 장치.
제 3항에 있어서, 디코더(140)는 행렬(B)을 가우스 소거법(Gaussian elimination method)을 사용하여 상삼각 행렬로 전환하는, 장치.
제 3항에 있어서, 디코더(140)는 [C[p₀],C[p₁],...,C[p_W-1]]^T로 표현된 중간 심벌의 적어도 일부를 회복하기 위해 역추적 동작(trace-back operation)을 수행하고, 여기서 p_i는 적어도 일부 중간 심벌 중 특별한 하나의 인덱스를 표시하고, W는 적어도 일부 중간 심벌의 개수를 나타내며, 0 ≤p_i≤L 및 W<L이고, 행렬(B)의 상삼각 행렬로의 전환이 실패할 때,

를 사용하여 적어도 일부 중간 심벌로부터 손실되거나 손상된 패킷에 대응하는 손실되거나 손상된 소스 심벌을 계산하는, 장치.
제 5항에 있어서, 디코더(140)는 행렬(B)의 랭크가 미리 특정된 임계값보다 클 때에만 역추적 동작을 수행하는, 장치.
제 1항에 있어서, 디코더(140)는 인코딩 심벌에 대응하는 중간 심벌의 서브세트를 얻기 위해 역추적 동작을 수행하고, 중간 심벌의 서브세트로부터 적어도 일부의 손실되거나 손상된 패킷에 대응하는 손실되거나 손상된 소스 심벌을 계산하는, 장치.
방법으로서,

인코딩 심벌의 시퀀스를 나타내는 패킷의 시퀀스를 디코딩하는 단계(200)를 포함하고,

디코딩하는 단계는 랩터 코드를 사용하여 시퀀스의 적어도 일부 손실되거나 손상된 패킷을 적어도 부분적으로 회복시키고, 디코딩하는 단계는 인코딩 심벌에 기초한 수학식의 선형 시스템을 구성하고(215), 수학식의 선형 시스템은

로 표현되며, 여기서 E는 인덱스{I₀, I₁,...,I_M-1}를 구비한 인코딩 심벌을 나타내고, M은 그 인코딩 심벌의 개수를 나타내며, C는 패킷의 시퀀스로 인코딩될 소스 심벌을 나타내고, K는 소스 심벌의 개수를 나타내며, S는 소스 심벌로부터 발생된 저밀도 패리티 체크 심벌을 나타내고, H_LDPC는 저밀도 패리티 체크 심벌을 발생시키기 위해 사용된 행렬을 나타내며, H는 소스 심벌로부터 발생된 절반의 심벌을 나타내고, H_Half는 절반의 심벌을 발생시키기 위해 사용된 행렬을 나타내며,
는 인코딩 심벌을 발생시키기 위한 행렬을 나타내고, I_{S ×S}는 차원(S ×S)의 단위 행렬(identity matrix)을 나타내며, O_{S ×H}는 차원(S ×H)의 0(zero) 행렬을 나타내고, I_{H ×H}는 차원(H ×H)의 단위 행렬을 나타내며, B는 행렬을 나타내고, L은 중간 심벌의 개수를 나타내는, 방법.
삭제
제 8항에 있어서, 디코딩하는 단계는 행렬(B)을 상삼각 행렬로 전환하는(220), 방법.
제 10항에 있어서, 디코딩하는 단계는 행렬(B)을 가우스 소거법을 사용하여 상삼각 행렬로 전환하는(220), 방법.
제 10항에 있어서, 디코딩하는 단계는 [C[p₀],C[p₁],...,C[p_W-1]]^T로 표현된 중간 심벌의 적어도 일부를 회복하기 위해 역추적 동작(trace-back operation)을 수행하고, 여기서 p_i는 적어도 일부 중간 심벌 중 특별한 하나의 인덱스를 표시하고, W는 적어도 일부 중간 심벌의 개수를 나타내며, 0 ≤p_i≤L 및 W<L이고, 행렬(B)의 상삼각 행렬로의 전환이 실패할 때,

를 사용하여 적어도 일부 중간 심벌로부터 손실되거나 손상된 패킷에 대응하는 손실되거나 손상된 소스 심벌을 계산하는(235,240), 방법.
제 12항에 있어서, 디코딩하는 단계는 행렬(B)의 랭크가 미리 특정된 임계값보다 클 때에만 역추적 동작을 수행하는(230), 방법.
제 8항에 있어서, 디코딩하는 단계는 인코딩 심벌에 대응하는 중간 심벌의 서브세트를 얻기 위해 역추적 동작을 수행하고, 중간 심벌의 서브세트로부터 적어도 일부의 손실되거나 손상된 패킷에 대응하는 손실되거나 손상된 소스 심벌을 계산하는(235, 240), 방법.