토네이도 코드

Tornado code

코딩 이론에서 토네이도 코드는 오류 수정을 지원하는 삭제 코드의 한 종류다. 토네이도 코드는 데이터 효율이 높은 리드-솔로몬 삭제 코드보다 지속적인 C의 중복 블록이 필요하지만 생성 속도가 훨씬 빠르며 소거를 더 빨리 해결할 수 있다. 소프트웨어 기반 토네이도 코드 구현은 리드-솔로몬 삭제 코드보다 작은 길이에서는 약 100배, 큰 길이에서는 약 10,000배 빠르다.[1] 토네이도 코드 도입 이후 많은 유사한 삭제 코드가 등장했는데, 가장 두드러진 것은 온라인 코드, LT 코드, 랩터 코드 등이다.

토네이도 코드는 레이어드 접근법을 사용한다. 마지막을 제외한 모든 계층은 속도가 빠르지만 실패할 가능성이 있는 LDPC 오류 수정 코드를 사용한다. 최종 레이어는 리드-솔로몬 보정 코드를 사용하며, 속도는 느리지만 고장 복구 측면에서는 최적이다. 토네이도 코드는 레벨 수, 각 레벨의 복구 블록 수, 그리고 최종 계층에 대한 블록 생성에 사용된 분포를 지시한다.

개요

입력 데이터는 블록으로 나뉜다. 블록은 크기가 모두 같은 비트 시퀀스다. 복구 데이터는 입력 데이터와 동일한 블록 크기를 사용한다. 블록(입력 또는 복구)의 삭제는 다른 수단에 의해 감지된다. (예를 들어, 디스크의 블록은 CRC 검사를 통과하지 못하거나 지정된 시퀀스 번호를 가진 네트워크 패킷이 도착하지 않는다.)

사용자가 제공한 복구 블록 수입니다. 그런 다음 각 레벨의 블럭 수와 함께 레벨 수가 결정된다. 각 수준의 숫자는 1보다 작은 요인 B에 의해 결정된다. 입력 블록이 N개인 경우, 첫 번째 복구 레벨은 B*N 블록, 두 번째 복구 레벨은 B*B*N, 세 번째 복구 레벨은 B*B*B*N 등의 블록을 가진다.

최종 복구 수준을 제외한 모든 수준의 복구는 xor(독점)에 의해 작동하는 LDPC를 사용한다. Xor는 1초와 0초라는 이진수 값으로 작동한다. A와 B의 값이 다르면 1이고 A와 B의 값이 같으면 0이다. (A xor B)와 (A xor B)의 결과가 주어지는 경우, B의 값을 결정할 수 있다.(A xor B xor A = B) 마찬가지로 (A xor B)와 B의 결과가 주어지면 A의 값을 결정할 수 있다. 이 값은 여러 값으로 확장되므로 (A xor B xor C xor D)의 결과와 3개의 값 중 어떤 값이라도 결측값을 복구할 수 있다.

따라서 레벨 1의 복구 블록은 일부 입력 블록 집합의 xor일 뿐이다. 마찬가지로 레벨 2의 복구 블록은 레벨 1의 일부 블록 집합에서 각각 xor이다. xor에 사용된 블록은 반복 없이 임의로 선택된다. 그러나 복구 블록을 만들기 위해 xor'ed된 블록 수는 각 수준에 대한 매우 구체적인 분포에서 선택된다.

xor는 빠른 작업이고 복구 블록은 입력(또는 더 낮은 복구 수준에서)에 있는 블록 중 일부만 xor이므로 복구 블록을 빠르게 생성할 수 있다.

마지막 단계는 리드-솔로몬 코드다. 리드-솔로몬 코드는 고장 복구 측면에서 최적이지만 생성 및 복구 속도는 느리다. 각 레벨은 이전 레벨보다 블록 수가 적기 때문에 Reed-Solomon 코드는 생성 및 복구에 사용할 복구 블록 수가 적다. 그래서 리드-솔로몬은 느리지만 취급할 데이터는 소량밖에 없다.

복구 중에는 리드-솔로몬 코드가 먼저 복구된다. 이는 다음에서 최종까지의 단계에서 누락된 블록 수가 최종 수준의 현재 블록보다 적을 경우 효과가 보장된다.

더 낮아지면, 모든 복구 블록이 존재하고 그 아래의 레벨이 복구 레벨보다 최대 C' 적은 블록에서 누락된 경우, LDPC(xor) 복구 레벨을 사용하여 높은 확률로 그 아래의 레벨을 복구할 수 있다. 복구 알고리즘은 하위 수준에서 생성 집합 중 하나만 누락된 일부 복구 블록을 찾는 것이다. 그러면 존재하는 모든 블록이 있는 복구 블록의 xor는 누락된 블록과 동일하다.

특허권발행

토네이도 코드는 이전에 미국 내에서 특허를 받았다.[2] 특허 US6163870 A(1997년 11월 6일)와 US 6081909년 A(1997년 11월 6일)는 토네이도 코드를 기술하고 있으며 2017년 11월 6일 현재 만료되었다. 특허 US6307487 B1(1999년 2월 5일)과 US6320520 B1(1999년 9월 17일)도 토네이도 코드를 언급하고 있으며, 2019년 2월 5일과 2019년 9월 17일 현재 각각 만료되었다.

인용구

마이클 루비는 토네이도 코드를 만들었다.[3][4]

외부 링크

CMU (PostScript)[1] 및 국제 컴퓨터 과학 연구소 (PostScript)의 Luby (PostScript)[2]에서 읽을 수 있는 설명.

참고 항목

메모들

  1. ^ 대용량 데이터의 안정적인 배포에 대한 디지털 분수 접근 방식. http://portal.acm.org/citation.cfm?id=285243.285258
  2. ^ 미첸마허 2004
  3. ^ 루비 1997
  4. ^ 루비 1998

참조

  • M. Mitzenmacher (2004). "Digital Fountains: A Survey and Look Forward". Proc. 2004 IEEE Information Theory Workshop (ITW).
  • M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Spielman, V. Stemann (1997). "Practical Loss-Resilient Codes". Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing: 150–159.{{cite journal}}: CS1 maint : 복수이름 : 작성자 목록(링크)
  • M. Luby, M. Mitzenmacher, A. Shokrollahi (1998). "Analysis of Random Processes via And-Or Tree Evaluation". Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms: 364–373.{{cite journal}}: CS1 maint : 복수이름 : 작성자 목록(링크)