분수 코드

Fountain code

코딩 이론에서,분수 코드(또는 무레이트 소거 코드)는 주어진 소스 기호 집합에서 잠재적으로 무한한 인코딩 기호 시퀀스를 생성할 수 있다는 특성을 가진 소거 코드의 클래스로, 원래 소스 기호는 l과 같거나 약간만 크기의 인코딩 기호의 하위 집합에서 이상적으로 복구될 수 있습니다.소스 기호 수보다 큼.분수 또는 무레이트라는 용어는 이러한 코드가 고정된 코드 속도를 나타내지 않는다는 사실을 나타냅니다.

원본 k 소스 기호를 수신한 모든 k 인코딩 기호에서 복구할 수 있는 경우(즉, 삭제된 것은 제외) 분수 코드가 최적입니다.분수 코드는 효율적인 인코딩 및 디코딩 알고리즘을 가지고 있으며 k'가 k보다 약간 큰 높은 확률의 인코딩 기호 중 임의의 k'에서 원래 k 소스 기호를 복구할 수 있는 것으로 알려져 있습니다.

LT 코드는 분수 코드의 최초의 실용적인 구현이었습니다.랩터 코드와 온라인 코드는 이후 도입되었으며 입력 기호의 사전 코딩 단계를 통해 선형 시간 인코딩 및 디코딩 복잡성을 달성합니다.

적용들

분수 코드는 고정 코드 속도 또는 고정 코드 속도를 사전에 결정할 수 없는 경우, 대량의 데이터의 효율적인 인코딩 및 디코딩이 필요한 경우에 유연하게 적용할 수 있습니다.

한 가지 예로 데이터 회전 장치(Data carusel)를 들 수 있는데, 여기서 일부 대용량 파일이 [1]수신기 세트에 지속적으로 브로드캐스트됩니다.고정 속도 삭제 코드를 사용하면 전송 오류로 인해 소스 기호가 누락된 수신기가 쿠폰 수집기의 문제에 직면합니다. 수신기는 아직 가지고 있지 않은 인코딩 기호를 성공적으로 수신해야 합니다.이 문제는 기존의 짧은 길이의 삭제 코드를 사용할 때 훨씬 더 명확해집니다. 파일을 여러 블록으로 분할하여 각각 별도로 인코딩해야 하기 때문입니다. 이제 수신기는 각 블록에 대해 필요한 수의 누락된 인코딩 기호를 수집해야 합니다.수신기는 분수 코드를 사용하여 소스 기호 집합보다 약간 큰 크기의 인코딩 기호의 하위 집합을 검색하기만 하면 됩니다.(실제로, 브로드캐스트는 일반적으로 네트워크 및 수신기의 특성과 원하는 전송 신뢰성에 기초하여 운영자에 의해 고정된 시간 동안 예약되므로 파일의 브로드캐스트가 예약된 시간에 동적으로 결정되는 코드 속도로 사용됩니다.)

또 다른 응용 프로그램은 신뢰할 수 있는 멀티캐스트 시나리오에서의 하이브리드 ARQ입니다. 수신기가 요청하는 패리티 정보는 잠재적으로 멀티캐스트 그룹의 모든 수신기에 유용할 수 있습니다.

표준 분수 코드

랩터 코드는 현재 [2]가장 효율적인 분수 코드이며 매우 효율적인 선형 시간 인코딩 및 디코딩 알고리즘을 가지고 있으며 인코딩 및 디코딩 [3]모두에 대해 생성된 기호당 소수의 일정한 수의 XOR 작업만 필요합니다.IETF RFC 5053은 브로드캐스트 파일 전달 및 스트리밍 서비스를 위한 3GPP MBMS 표준, DVB 네트워크를 통한 IP 서비스 제공을 위한 DVB-HIPDC 표준 등 IETF를 넘어 여러 표준으로 채택된 체계적인 Raptor 코드를 상세하게 규정하고 있습니다.및 IP 네트워크를 통해 상용 TV 서비스를 제공하기 위한 DVB-IPTV.이 코드는 소스 블록에서 최대 8,192개의 소스 기호와 소스 블록에 대해 생성된 총 65,536개의 인코딩 기호와 함께 사용할 수 있습니다.이 코드는 소스 기호가 1,000개인 소스 블록에 적용될 때 평균 상대 수신 오버헤드가 0.2%이며, 확률 99.9999%[4]로 상대 수신 오버헤드가 2% 미만입니다.상대 수신 오버헤드는 원본 데이터를 복구하는 데 원본 데이터의 길이를 초과하여 필요한 추가 인코딩 데이터로 정의되며, 원본 데이터 크기의 백분율로 측정됩니다.예를 들어 상대 수신 오버헤드가 0.2%이면 1.002MB 인코딩 데이터에서 1MB 크기의 소스 데이터를 복구할 수 있습니다.

IETF RFC 6330에는 RaptorQ라고 하는 유연성이 더 높고 수신 오버헤드가 개선된 고급 Raptor 코드가 명시되어 있습니다.지정된 RaptorQ 코드는 소스 블록에서 최대 56,403개의 소스 기호 및 소스 블록에 대해 생성된 총 16,777,216개의 인코딩 기호와 함께 사용할 수 있습니다.이 코드는 소스 블록의 소스 기호 수와 동일한 인코딩된 기호 집합에서 소스 블록을 높은 확률로 복구할 수 있으며, 드물게 소스 블록의 소스 기호 수보다 약간 많은 경우에도 복구할 수 있습니다.RaptorQ 코드는 ATSCA-331(ATSC 3.0)에 지정된 ROUTE 인스턴스화의 필수 부분입니다.

데이터 저장을 위한 분수 코드

데이터 스토리지 애플리케이션에서는 특정 수준의 중복성 및 안정성을 위해 스토리지 유닛 수를 대폭 절감하기 때문에 삭제 코드가 사용됩니다.데이터 스토리지, 특히 분산 스토리지 애플리케이션에 대한 삭제 코드 설계 요구 사항은 통신 또는 데이터 스트리밍 시나리오와 관련하여 상당히 다를 수 있습니다.데이터 스토리지 시스템의 코딩 요구 사항 중 하나는 체계적인 형태입니다. 즉, 원래 메시지 기호는 코드화된 [citation needed]기호의 일부입니다.체계적인 형식을 통해 저장 장치에서 디코딩하지 않고 메시지 기호를 읽을 수 있습니다.또한 스토리지 노드 간의 대역폭 및 통신 부하가 병목 현상이 될 수 있으므로, 특히 노드에 장애가 발생하여 초기 수준의 이중화를 달성하기 위해 시스템 재구성이 필요할 때 최소 통신을 허용하는 코드가 매우 유용합니다.그런 점에서 분수 코드를 사용하면 고장 시 효율적인 수리 프로세스를 수행할 수 있습니다.인코딩된 단일 기호가 손실된 경우, 손실된 기호를 부활시키기 위해 다른 인코딩된 기호 간의 통신과 계산이 너무 많이 필요하지 않아야 합니다.실제로 복구 대기 시간이 스토리지 공간 절약보다 더 중요한 경우도 있습니다.복구 가능한 분수[5] 코드는 스토리지 시스템의 분수 코드 설계 목표를 해결할 것으로 예상됩니다.분수 코드와 그 응용 프로그램에 대한 자세한 설문 조사는 [6]에서 확인할 수 있습니다.

분수 코드를 사용하는 분산 스토리지에 대한 다른 접근 방식이 Liquid Cloud [7][8]스토리지에서 제안되었습니다.Liquid Cloud 스토리지는 IETFRFC 6330에 지정된 RaptorQ 코드(다른 시스템보다 훨씬 우수한 데이터 보호 기능 제공)와 같은 대형 삭제 코드를 사용하는 것을 기반으로 하며, 백그라운드 복구 프로세스를 사용합니다(다른 시스템에 비해 복구 대역폭 요구사항이 상당히 감소함).스트림 데이터 조직(일부 인코딩된 기호를 사용할 수 없는 경우에도 데이터에 빠르게 액세스할 수 있음)을 사용할 수 있습니다.

참고 항목

메모들

  1. ^ J. Byers, M. Luby, M. Mitzenmacher, A. Rege (1998). "A Digital Fountain Approach to Reliable Distribution of Bulk Data" (PDF).{{cite web}}CS1 유지보수: 다중 이름: 작성자 목록(링크)
  2. ^ "Qualcomm Raptor Technology - Forward Error Correction". 2014-05-30.
  3. ^ (쇼크롤라히 2006)
  4. ^ T. Stockhammer, A. Shokrollahi, M. Watson, M. Luby, T. Gasiba (March 2008). Furht, B.; Ahson, S. (eds.). "Application Layer Forward Error Correction for Mobile Multimedia Broadcasting". Handbook of Mobile Broadcasting: DVB-H, DMB, ISDB-T and Media FLO. CRC Press.{{cite journal}}CS1 유지보수: 다중 이름: 작성자 목록(링크)
  5. ^ Asteris, Megasthenis; Dimakis, Alexandros G. (2012). "Repairable Fountain Codes". IEEE Journal on Selected Areas in Communications. 32 (5): 1037–1047. arXiv:1401.0734. doi:10.1109/JSAC.2014.140522. S2CID 1300984.
  6. ^ Arslan, Suayb S. (2014). "Incremental Redundancy, Fountain Codes and Advanced Topics". arXiv:1402.6016 [cs.IT].
  7. ^ Luby, Michael; Padovani, Roberto; Richardson, Thomas J.; Minder, Lorenz; Aggarwal, Pooja (2019). "Liquid Cloud Storage". ACM Transactions on Storage. 15: 1–49. arXiv:1705.07983. doi:10.1145/3281276. S2CID 738764.
  8. ^ Luby, M.; Padovani, R.; Richardson, T.; Minder, L.; Aggarwal, P. (2017). "Liquid Cloud Storage". arXiv:1705.07983v1 [cs.DC].

레퍼런스