Kodowanie korekcyjne Reeda-Solomona
Korekcja błędów Reed-Solomon jest kodem korekcji błędów typu forward. Działa ona poprzez nadpróbkowanie wielomianu skonstruowanego z danych. Wielomian ten jest oceniany w kilku punktach, a wartości te są przesyłane lub zapisywane. Próbkowanie wielomianu częściej niż jest to konieczne powoduje, że wielomian jest nadpróbkowany. Tak długo, jak otrzymuje "wiele" punktów poprawnie, odbiornik może odzyskać oryginalny wielomian nawet w obecności "kilku" złych punktów.
Kody Reed-Solomon są używane w wielu różnych rodzajach zastosowań komercyjnych, na przykład w płytach CD, DVD i Blu-ray, w technologiach transmisji danych, takich jak DSL i WiMAX oraz w systemach nadawczych, takich jak DVB i ATSC.
Przegląd
Kody Reeda-Solomona są kodami blokowymi. Oznacza to, że stały blok danych wejściowych jest przetwarzany na stały blok danych wyjściowych. W przypadku najczęściej używanego kodu R-S (255, 223) - 223 wejściowe symbole Reed-Solomona (każdy o długości ośmiu bitów) są kodowane w 255 symboli wyjściowych.
- Większość schematów R-S ECC jest systematyczna. Oznacza to, że pewna część wyjściowego słowa kodowego zawiera dane wejściowe w ich oryginalnej postaci.
- Rozmiar symbolu Reed-Solomon równy 8 bitom został wybrany, ponieważ dekodery dla większych rozmiarów symboli byłyby trudne do zaimplementowania w obecnej technologii. Ten wybór projektowy wymusza, aby najdłuższe słowo kodowe miało długość 255 symboli.
- Standardowy (255, 223) kod Reeda-Solomona jest w stanie skorygować do 16 błędów symbolu Reeda-Solomona w każdym słowie kodowym. Ponieważ każdy symbol składa się z ośmiu bitów, oznacza to, że kod może skorygować do 16 krótkich błędów spowodowanych przez wewnętrzny dekoder konwolucyjny.
Kod Reeda-Solomona, podobnie jak kod konwolucyjny, jest kodem przezroczystym. Oznacza to, że jeśli symbole kanału zostały odwrócone gdzieś na linii, dekodery będą nadal działać. Wynik będzie uzupełnieniem oryginalnych danych. Kod Reed-Solomon traci jednak swoją przejrzystość, jeśli stosowane jest wypełnienie wirtualnym zerem. Z tego powodu jest obowiązkowe, aby sens danych (tzn. prawdziwy lub uzupełniony) został rozstrzygnięty przed dekodowaniem Reed-Solomon.
W przypadku programu Voyager kody R-S osiągają prawie optymalną wydajność, gdy są konkatenowane z wewnętrznym kodem (7, 1/2) konwolucyjnym (Viterbiego). Ponieważ dla każdego korygowanego błędu wymagane są dwa symbole kontrolne, daje to w sumie 32 symbole kontrolne i 223 symbole informacyjne na słowo kodowe.
Dodatkowo, słowa kodowe Reed-Solomon mogą być przeplatane na podstawie symboli przed zakodowaniem konwencjonalnym. Ponieważ to rozdziela symbole w słowie kodowym, staje się mniej prawdopodobne, że wybuch z dekodera Viterbiego zakłóca więcej niż jeden symbol Reed-Solomon w jednym słowie kodowym.
Podstawowa idea
Kluczową ideą kodu Reeda-Solomona jest to, że zakodowane dane są najpierw wizualizowane jako wielomian. Kod ten opiera się na twierdzeniu z algebry, które mówi, że dowolne k różnych punktów jednoznacznie określa wielomian stopnia co najwyżej k-1.
Nadawca określa wielomian stopnia k - 1 {displaystyle k-1}
, w skończonym polu, który reprezentuje k {displaystyle k} punktów danych
. Wielomian jest następnie "zakodowany" przez jego ocenę w różnych punktach, a te wartości są tym, co jest faktycznie wysyłane. Podczas transmisji, niektóre z tych wartości mogą zostać uszkodzone. Dlatego też w rzeczywistości wysyłanych jest więcej niż k punktów. Tak długo, jak wystarczająco dużo wartości są odbierane poprawnie, odbiornik może wydedukować, co było oryginalnym wielomianem i zdekodować oryginalne dane.
W tym samym sensie, że można poprawić krzywą przez interpolację obok luki, kod Reeda-Solomona może pokonać serię błędów w bloku danych, aby odzyskać współczynniki wielomianu, który narysował oryginalną krzywą.
Historia
Kod ten został wynaleziony w 1960 roku przez Irvinga S. Reeda i Gustave'a Solomona, którzy byli wówczas członkami MIT Lincoln Laboratory. Ich przełomowy artykuł nosił tytuł "Polynomial Codes over Certain Finite Fields". Gdy go pisali, technologia cyfrowa nie była jeszcze na tyle zaawansowana, by zaimplementować tę koncepcję. Pierwszym zastosowaniem kodów RS w masowej produkcji była w 1982 roku płyta kompaktowa, na której zastosowano dwa przeplatane kody RS. W 1969 roku Elwyn Berlekamp i James Massey opracowali efektywny algorytm dekodowania dla kodów RS o dużych odległościach. Obecnie kody RS są stosowane w dyskach twardych, płytach DVD, telekomunikacji i protokołach transmisji cyfrowych.
