랩터 코드
Raptor code | 이 글은 인용 방식이 불분명하다. (2021년 1월)(이과 시기 |
|
컴퓨터 과학에서 랩터 코드(급속 토네이도;[1] 토네이도 코드 참조)는 선형 시간 인코딩과 디코딩이 있는 분수 코드의 첫 번째 등급이다. 그것들은 2000/2001년 아민 쇼크롤라히에 의해 발명되었고, 확장된 추상체로 2004년에 처음 출판되었다. 랩터 코드는 분수 코드의 첫 번째 실용 등급이었던 LT 코드에 비해 이론적이고 실질적인 개선이다.
일반적으로 분수 코드와 마찬가지로, 랩터 코드는 동일한 크기의 소스 기호의 숫자 k로 구성된 데이터의 특정 소스 블록을 k 또는 그 이상의 인코딩 기호의 수신이 0이 아닌 확률로 소스 블록을 복구할 수 있도록 잠재적으로 무제한 인코딩 기호의 시퀀스로 인코딩한다. 일단 수신된 인코딩 기호의 수가 k보다 매우 약간 크기만 하면 k보다 매우 약간 크면 k 위에 수신된 인코딩 기호의 수가 매우 1에 가까워질수록 소스 블록을 복구할 수 있는 확률은 증가한다. 예를 들어 최신 세대의 RaptorQ 코드인 RaptorQ 코드인 경우 k 인코딩 기호가 수신되었을 때 해독 실패 확률이 1% 미만이며, k+2 인코딩 기호가 수신되었을 때 해독 실패 확률이 백만분의 1 미만이다. 이에 대한 자세한 내용은 아래의 복구 확률 및 오버헤드 섹션을 참조하십시오. 기호는 단일 바이트에서 수백 또는 수천 바이트에 이르는 모든 크기를 가질 수 있다.
랩터 코드는 체계적이거나 비체계적일 수 있다. 체계적 경우, 원본 블록의 기호, 즉 원본 기호는 인코딩 기호의 집합 내에 포함된다. 체계적인 Raptor 코드의 일부 예는 모바일 무선 방송과 멀티캐스팅에서 제3세대 파트너십 프로젝트와 핸드헬드 장치에 대한 IP 데이터캐스트에 대한 DVB-H 표준에 의한 사용이다(외부 링크 참조). 이 표준에 사용된 Raptor 코드는 IETF RFC 5053에도 정의되어 있다.
온라인 코드는 비시스템적 분수 코드의 예다.
랩터Q 코드
Raptor의 가장 발전된 버전은 IETF RFC 6330에 정의된 RaptorQ 코드다. RaptorQ 코드는 체계적인 코드로, 선형 시간 인코딩과 디코딩 성능을 달성하기 위해 구현될 수 있으며, 복구 속성이 거의 최적화되어 있으며(자세한 내용은 아래의 복구 확률 및 오버헤드 섹션 참조), 최대 56,403개의 소스 기호를 지원하며, 기본적으로 무제한의 인코딩 기호를 지원할 수 있다.
IETF RFC 6330에 정의된 RaptorQ 코드는 고품질 방송 비디오 스트리밍(로봇 모바일 TV)과 효율적이고 신뢰할 수 있는 방송 파일 전송(데이터캐스팅)이 가능하도록 차세대 TV(ATSC 3.0) 표준의 일부로 명시되어 있다. 특히 RaptorQ 코드는 A/331: ATSC 3.0 내의 신호, 전달, 동기화 및 오류 보호에 지정되어 있다(ATSC 3.0 표준 부품 목록은 ATSC 표준 목록 참조). 차세대 TV(ATSC 3.0)는 일반적인 데이터 전송 서비스를 지원하는 브로드캐스트 인터넷을 제공하기 위해 기존 TV를 능가한다.
개요
랩터 코드는 두 개의 코드의 결합에 의해 형성된다.
고정금리삭제코드는 보통 상당히 높은 요율을 적용하며, '사전코드' 또는 '외부코드'로 적용한다. 이 프리코드 자체는 여러 코드의 결합일 수 있다. 예를 들어 3GPP에 의해 표준화 된 코드에서 바이너리 그레이 시퀀스에서 파생된 고밀도 패리티 체크 코드는 단순한 정기적인 저밀도 패리티 체크 코드로 결합된다. 또 다른 가능성은 저밀도 패리티 검사 코드를 가진 해밍 코드의 결합일 것이다.
내부 코드는 사전 코딩 작업의 결과를 취하여 일련의 인코딩 기호를 생성한다. 내부 코드는 LT 코드의 일종이다. 각 인코딩 기호는 사전 코드 출력에서 의사 임의로 선택한 기호 집합의 XOR이다. 출력 기호를 형성하기 위해 XOR를 함께 사용하는 기호의 수는 특정 확률 분포에 따라 각 출력 기호에 대해 의사 무작위로 선택된다.
이 분포는 이 분포의 표본 추출 및 XOR'ed 기호를 선택하기 위한 의사 난수 생성 메커니즘뿐만 아니라 송신자와 수신자 모두에게 알려져 있어야 한다. 하나의 접근법에서, 각 기호는 이 정보를 생성하기 위해 의사 난수 생성기의 씨앗으로 사용될 수 있는 식별자와 함께 수반되며, 송신자와 수신자 모두가 동일한 프로세스를 따르고 있다.
비시스템적 랩터 코드의 경우 인코딩할 소스 데이터를 코딩 전 단계에 대한 입력으로 사용한다.
체계적 Raptor 코드의 경우, 첫 번째 k 출력 기호를 생성하는 인코딩 작업의 역순을 소스 데이터에 먼저 적용하여 사전 코딩 단계의 입력을 얻는다. 따라서 결과 기호에 정상적인 인코딩 작업을 적용하면 원래 소스 기호가 코드의 첫 번째 k 출력 기호로 재생성된다. 첫 번째 k 출력 기호를 생성하는 의사 무작위 프로세스가 반전 가능한 연산을 생성하는지 확인할 필요가 있다.
디코딩
Raptor 코드 해독에는 두 가지 접근법이 가능하다. 연결된 접근방식에서 내부 코드는 LT 코드에 사용되는 믿음 전파 알고리즘을 사용하여 먼저 디코딩된다. 외부 코드가 해당 코드에 적합한 디코딩 알고리즘을 사용하여 나머지 기호를 복구할 수 있도록 이 작업이 충분한 수의 기호를 복구하는 경우 디코딩이 성공한다.
결합된 접근법에서 내부 코드와 외부 코드 모두에 의해 정의된 기호 사이의 관계는 일반적으로 가우스 제거에 의해 일반적인 수단으로 해결될 수 있는 단일의 동시 방정식 집합으로 간주된다.
계산 복잡성
랩터 코드는 소스 블록에서 인코딩 기호를 생성하는 데 O(심볼 크기) 시간이 필요하고, 최소 k 인코딩 기호로 부터 소스 블록을 복구하는 데 O(소스 블록 크기) 시간이 필요하다.
복구 확률 및 오버헤드
오버헤드는 소스 블록을 완전히 복구하기 위해 원본 블록의 소스 기호 수 k를 초과하여 추가 인코딩 기호를 얼마나 더 받아야 하는가를 의미한다.(초기 정보 이론상 k 소스 기호를 포함한 소스 블록의 완전한 복구는 k개 미만의 인코딩 기호를 recographing할 경우 가능하지 않다)복구 확률은 소스 블록에서 생성된 지정된 수의 임의 인코딩 기호를 수신했을 때 소스 블록이 완전히 복구될 확률이다.
IETF RFC 6330에 명시된 RaptorQ 코드는 복구 확률과 복구 오버헤드 간에 다음과 같은 절충이 있다.
- 오버헤드가 0인 경우 복구 확률이 99% 이상임(k 수신 인코딩 기호에서 복구)
- 오버헤드가 1개 기호일 때 복구 확률이 99.99% 이상임(k+1 수신 인코딩 기호에서 복구)
- 99.9999% 이상의 복구 확률로 2개 기호(k+2 수신 인코딩 기호로 복구)
이 문장은 IETF RFC 6330에서 지원되는 전체 k 범위(예: k=1, ...,56403)를 유지한다. 자세한 내용은 IETF RFC 6330을 참조하십시오.
법적현황
퀄컴은 IETF RFC 5053에 명시된 랩터 코드에 대한 IPR 문구와 IETF RFC 6330에 명시된 보다 발전된 랩터Q 코드에 대한 IPR 문구를 발표했다. 이러한 진술은 퀄컴이 MPEG DASH 표준과 관련하여 한 라이센스 약속을 반영한다. MPEG DASH 표준은 DASH Industry Forum 회원사를 포함한 다양한 기업들에 의해 배치되었다.
참고 항목
메모들
- ^ Amin Shokrollahi (31 January 2011). The Development of Raptor Codes (Speech). Invited talk at the Kungliga Tekniska högskolan. Retrieved 24 February 2012.
참조
- 쇼크롤라히, 아민, "랩터 코드", IEEE 정보이론 거래, vol. 52, 페이지 2551-2567, 2006. PDF(로그인 필요)
- ATSC 3.0(고급 텔레비전 표준 위원회 3.0)
- 3GPP(제3세대 파트너십 프로젝트)
- DVB(디지털 비디오 방송)
- IMT2000 3GPP - 멀티미디어 방송/멀티캐스트 서비스를 위한 3GPP 기술규격 : 프로토콜과 코덱
- 객체 전달을 위한 RFC5053 Raptor Forward 오류 수정 체계
- DVB-H IP 데이터캐스트 규격
- RFC6330 객체 전달을 위한 RaptorQ 전달 오류 수정 체계
- [1] RFC 5053에 대한 "IPR" 검색 결과, 일부 특허 소유자의 진술 포함
- [2] RFC 6330에 대한 "IPR" 검색 결과, 일부 특허 소유자의 진술 포함
