Rīda-Solomona kļūdu korekcija
Rīda-Solomona kļūdu korekcija ir tiešais kļūdu korekcijas kods. Tā darbojas, pārlasot no datiem konstruētu polinomu. Polinomu novērtē vairākos punktos, un šīs vērtības nosūta vai ieraksta. Paraugu ņemšana biežāk, nekā nepieciešams, padara polinomu pārdefinētu. Kamēr uztvērējs "daudzus" punktus saņem pareizi, tas var atjaunot sākotnējo polinomu pat tad, ja ir "daži" slikti punkti.
Rīda-Solomona kodus izmanto daudzos dažādos komerciālos lietojumos, piemēram, CD, DVD un Blu-ray diskos, datu pārraides tehnoloģijās, piemēram, DSL un WiMAX, un apraides sistēmās, piemēram, DVB un ATSC.
Pārskats
Rīda-Solomona kodi ir bloku kodi. Tas nozīmē, ka fiksēts ieejas datu bloks tiek apstrādāts fiksētā izejas datu blokā. Visbiežāk izmantotā R-S koda (255, 223) gadījumā 223 Rīda-Solomona ieejas simboli (katrs astoņu bitu garš) tiek kodēti 255 izejas simbolos.
- Lielākā daļa R-S ECC shēmu ir sistemātiskas. Tas nozīmē, ka daļa izejas koda vārda satur ieejas datus to sākotnējā formā.
- Trīda-Solomona simbolu izmērs ir astoņi biti, jo dekodētājus lielākiem simbolu izmēriem būtu grūti realizēt ar pašreizējo tehnoloģiju. Šāda konstrukcijas izvēle nosaka, ka visgarākais koda vārda garums ir 255 simboli.
- Standarta (255, 223) Rīda-Solomona kods spēj izlabot līdz 16 Rīda-Solomona simbolu kļūdas katrā koda vārdā. Tā kā katrs simbols faktiski ir astoņi biti, tas nozīmē, ka kods var labot līdz 16 īsiem kļūdu sērijām, ko rada iekšējais konvolūcijas dekoders.
Rīda-Solomona kods, tāpat kā konvolūcijas kods, ir pārredzams kods. Tas nozīmē, ka, ja kanāla simboli ir apvērsti kaut kur pa līniju, dekoderi joprojām darbosies. Rezultāts būs sākotnējo datu papildinājums. Tomēr Rīda-Solomona kods zaudē caurspīdīgumu, ja izmanto virtuālo nulles aizpildījumu. Šā iemesla dēļ pirms Rīda-Solomona dekodēšanas ir obligāti jānosaka datu jēga (t. i., patiesa vai papildināta).
Voyager programmas gadījumā R-S kodi sasniedz gandrīz optimālu veiktspēju, ja tos apvieno ar (7, 1/2) konvolūcijas (Viterbi) iekšējo kodu. Tā kā katrai labojamai kļūdai ir nepieciešami divi pārbaudes simboli, tad vienā koda vārdā kopā ir 32 pārbaudes simboli un 223 informācijas simboli.
Turklāt pirms konvolūcijas kodēšanas Rīda-Solomona koda vārdus var pārklāt pa simboliem. Tā kā šādi tiek nodalīti simboli vienā koda vārdā, ir mazāka iespēja, ka Viterbi dekodera pārrāvums izjauc vairāk nekā vienu Rīda-Solomona simbolu jebkurā vienā koda vārdā.
Pamatideja
Rīda-Solomona koda galvenā ideja ir tāda, ka kodētie dati vispirms tiek vizualizēti kā polinoms. Kods balstās uz teorēmu no algebras, kas nosaka, ka jebkurš k dažādu punktu viennozīmīgi nosaka polinomu, kura pakāpe ir ne lielāka par k-1.
Sūtītājs nosaka k - 1 pakāpes {\displaystyle k-1}
polinomu, kas ir galīgais lauks un kas atspoguļo k {\displaystyle k}
datu punktus. Pēc tam polinoms tiek "kodēts", novērtējot to dažādos punktos, un šīs vērtības ir tās, ko faktiski nosūta. Pārraides laikā dažas no šīm vērtībām var tikt bojātas. Tāpēc faktiski tiek nosūtīti vairāk nekā k punktu. Kamēr ir saņemts pietiekami daudz vērtību pareizi, uztvērējs var secināt, kāds bija sākotnējais polinoms, un atšifrēt sākotnējos datus.
Tādā pašā nozīmē, kā var labot līkni, interpolējot garām spraugai, Rīda-Solomona kods var pārvarēt virkni kļūdu datu blokā, lai atjaunotu polinoma koeficientus, kas zīmēja sākotnējo līkni.
Vēsture
Šo kodu 1960. gadā izgudroja Irvings S. Rīds (Irving S. Reed) un Gustavs Solomons (Gustave Solomon), kas tolaik strādāja MIT Linkolna laboratorijā. Viņu raksta nosaukums bija "Polynomial Codes over Certain Finite Fields" ("Polinomiālie kodi pār noteiktiem galīgajiem laukiem"). Kad tas tika uzrakstīts, digitālās tehnoloģijas nebija pietiekami attīstītas, lai īstenotu šo koncepciju. Pirmais RS kodu pielietojums masveidā ražotos produktos 1982. gadā bija kompaktdisks, kurā izmantoti divi RS kodi, kas izkārtoti viens ar otru. Efektīvu dekodēšanas algoritmu lielas distances RS kodiem 1969. gadā izstrādāja Elvins Berlekamps un Džeimss Masejs. Mūsdienās RS kodus izmanto cietajos diskdziņos, DVD, telekomunikācijās un ciparu apraides protokolos.
