Kod fontanny

W teorii kodowania kody fontannowe (znane również jako kody wymazywania bez współczynnika ) to klasa kodów wymazywania , których właściwość polega na tym, że z danego zestawu symboli źródłowych można wygenerować potencjalnie nieograniczoną sekwencję symboli kodowania , tak że oryginalne symbole źródłowe mogą być idealnie odzyskane z dowolnego podzbioru symboli kodowania o rozmiarze równym lub tylko nieznacznie większym niż liczba symboli źródłowych. Termin fontanna lub bez raty odnosi się do faktu, że te kody nie wykazują stałej szybkości kodowania .

Kod źródłowy jest optymalny, jeśli oryginalne k symboli źródłowych można odzyskać z dowolnych k pomyślnie odebranych symboli kodowania (tj. z wyłączeniem tych, które zostały wymazane). Znane są kody fontannowe, które mają wydajne algorytmy kodowania i dekodowania i które umożliwiają odzyskanie oryginalnych k symboli źródłowych z dowolnego k' symboli kodowania z dużym prawdopodobieństwem, gdzie k' jest tylko trochę większe niż k .

Kody LT były pierwszą praktyczną realizacją kodów fontannowych. Następnie wprowadzono kody Raptor i kody online , które osiągnęły złożoność kodowania i dekodowania w czasie liniowym poprzez etap wstępnego kodowania symboli wejściowych.

Aplikacje

Kody fontannowe można elastycznie stosować przy stałym współczynniku kodowania lub tam, gdzie nie można określić stałego współczynnika kodowania a priori i gdzie wymagane jest wydajne kodowanie i dekodowanie dużych ilości danych.

Jednym z przykładów jest karuzela danych , w której duży plik jest stale transmitowany do zestawu odbiorników. Korzystając z kodu kasowania o stałej stopie procentowej, odbiorca, któremu brakuje symbolu źródłowego (z powodu błędu transmisji), napotyka problem zbieracza kuponów : musi pomyślnie odebrać symbol kodowania, którego jeszcze nie ma. Problem ten staje się znacznie bardziej widoczny w przypadku stosowania tradycyjnego kodu wymazywania o krótkiej długości, ponieważ plik musi zostać podzielony na kilka bloków, z których każdy jest oddzielnie kodowany: odbiornik musi teraz zebrać wymaganą liczbę brakujących symboli kodowania dla każdego bloku . Używając kodu fontannowego, wystarczy, aby odbiornik odzyskał dowolny podzbiór symboli kodowania o rozmiarze nieco większym niż zestaw symboli źródłowych. (W praktyce transmisja jest zwykle planowana przez operatora na określony czas w oparciu o charakterystykę sieci i odbiorników oraz pożądaną niezawodność dostarczania, dlatego kod fontannowy jest używany z szybkością kodowania, która jest ustalana dynamicznie w momencie plik ma być wyemitowany).

Innym zastosowaniem jest hybrydowe ARQ w niezawodnych scenariuszach multiemisji: informacje o parzystości, których żąda odbiornik, mogą potencjalnie być przydatne dla wszystkich odbiorników w grupie multiemisji.

Kody fontannowe w normach

Kody Raptor są obecnie najbardziej wydajnymi kodami fontannowymi, posiadającymi bardzo wydajne algorytmy kodowania i dekodowania w czasie liniowym i wymagającymi tylko niewielkiej stałej liczby operacji XOR na wygenerowany symbol zarówno do kodowania, jak i dekodowania. IETF RFC 5053 szczegółowo określa systematyczny kod Raptor, który został przyjęty w wielu standardach poza IETF, takich jak standard 3GPP MBMS dla dostarczania plików i usług przesyłania strumieniowego, standard DVB-H IPDC dla dostarczania usług IP przez sieci DVB oraz DVB-IPTV do dostarczania komercyjnych usług telewizyjnych przez sieć IP. Ten kod może być używany z maksymalnie 8192 symbolami źródłowymi w bloku źródłowym i łącznie do 65536 zakodowanych symboli wygenerowanych dla bloku źródłowego. Ten kod ma średni względny narzut odbioru wynoszący 0,2% po zastosowaniu do bloków źródłowych z 1000 symboli źródłowych i ma względny narzut odbioru mniejszy niż 2% z prawdopodobieństwem 99,9999%. Względny narzut odbioru definiuje się jako dodatkowe dane kodowania wymagane poza długością danych źródłowych do odzyskania oryginalnych danych źródłowych, mierzone jako procent rozmiaru danych źródłowych. Na przykład, jeśli względny narzut odbioru wynosi 0,2%, oznacza to, że dane źródłowe o rozmiarze 1 megabajta można odzyskać z 1,002 megabajta kodowanych danych.

Bardziej zaawansowany kod Raptor o większej elastyczności i ulepszonym obciążeniu odbioru, nazwany RaptorQ, został określony w IETF RFC 6330. Określony kod RaptorQ może być używany z maksymalnie 56 403 symbolami źródłowymi w bloku źródłowym i łącznie do 16 777 216 zakodowanych symbole generowane dla bloku źródłowego. Ten kod jest w stanie odzyskać blok źródłowy z dowolnego zestawu zakodowanych symboli równej liczbie symboli źródłowych w bloku źródłowym z dużym prawdopodobieństwem, aw rzadkich przypadkach z nieco większej liczby symboli źródłowych w bloku źródłowym. Kod RaptorQ jest integralną częścią instancji ROUTE określonej w ATSC A-331 (ATSC 3.0)

Kody fontannowe do przechowywania danych

Kody wymazywania są używane w aplikacjach do przechowywania danych ze względu na ogromne oszczędności na liczbie jednostek pamięci dla danego poziomu redundancji i niezawodności. Wymagania dotyczące projektowania kodu wymazywania do przechowywania danych, szczególnie w przypadku aplikacji do przechowywania rozproszonego, mogą być zupełnie inne w zależności od scenariuszy komunikacji lub strumieniowego przesyłania danych. Jednym z wymogów kodowania systemów przechowywania danych jest systematyka, tzn. oryginalne symbole wiadomości są częścią zakodowanych symboli. [ potrzebne źródło ] Systematyczna forma umożliwia odczytanie symboli komunikatu bez dekodowania z jednostki pamięci. Ponadto, ponieważ przepustowość i obciążenie komunikacyjne między węzłami pamięci masowej mogą stanowić wąskie gardło, kody umożliwiające minimalną komunikację są bardzo korzystne, zwłaszcza w przypadku awarii węzła i konieczności przebudowy systemu w celu osiągnięcia początkowego poziomu nadmiarowości. Pod tym względem oczekuje się, że kody fontannowe umożliwią skuteczny proces naprawy w przypadku awarii: gdy pojedynczy zakodowany symbol zostanie utracony, nie powinno to wymagać zbyt dużej komunikacji i obliczeń między innymi zakodowanymi symbolami w celu wskrzeszenia utraconego symbolu. W rzeczywistości opóźnienie naprawy może być czasami ważniejsze niż oszczędność miejsca w pamięci masowej. Nadające się do naprawy kody toniczne mają na celu rozwiązanie celów projektowych kodu tonalnego dla systemów pamięci masowej. Szczegółową ankietę na temat kodów fontannowych i ich zastosowań można znaleźć pod adresem.

Inne podejście do rozproszonej pamięci masowej przy użyciu kodów fontannowych zostało zaproponowane w Liquid Cloud Storage. Liquid Cloud Storage opiera się na użyciu dużego kodu wymazywania, takiego jak kod RaptorQ określony w IETF RFC 6330 (który zapewnia znacznie lepszą ochronę danych niż inne systemy), użyciu procesu naprawy w tle (co znacznie zmniejsza wymagania dotyczące przepustowości naprawy w porównaniu z innymi systemami ) oraz przy użyciu organizacji danych strumieniowych (która umożliwia szybki dostęp do danych, nawet gdy nie wszystkie zakodowane symbole są dostępne).

Zobacz też

Notatki

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Fountain_code&oldid=1140626846 ”