Rīda–Solomona kodi: definīcija, darbības princips un pielietojums
Rīda-Solomona kodi: skaidra definīcija, darbības princips un reālie pielietojumi — kļūdu korekcija CD/DVD/Blu‑ray, DSL, WiMAX, DVB/ATSC datu drošībai.
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 (Reed–Solomon, RS) kodi ir plaši izmantoti praktiskos risinājumos, jo tie labi labo simbolu (parasti baitu) līmeņa kļūdas un ir izturīgi pret kļūdu kopām (burst errors). Tos 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.
Kas ir RS kods — pamatideja
RS kods darbojas laukā ar finišu daudzumu (galvenokārt galvenokārt Galois lauks GF(2^m)). Ziņojums tiek attēlots kā polinoms m(x) ar pakāpi mazāku par k (kur k ir informācijas simbolu skaits). Kodvārdu garums ir n simboli; parasti n = 2^m − 1 simboli, ja izmanto visu lauku bez nulles. Kodēšanā ziņojuma polinomam pieskaita paritātes simbolus, lai iegūtu n simbolu garu kodvārdu.
Parametri un kļūdu korekcijas spēja
- n — kopējais simbolu skaits kodvārdā.
- k — informācijas (datu) simbolu skaits.
- n − k — paritātes (kontroles) simbolu skaits.
- t — maksimālais koriģējamo simbolu kļūdu skaits, t = floor((n − k)/2).
Piemēram, RS(255,223) darbotos laukumā GF(2^8) ar n = 255, k = 223 un spētu koriģēt līdz t = 16 simbolu kļūdām kodvārdā.
Kodēšanas princips īsumā
Kodēšana parasti notiek šādi:
- Ziņas simbolus interpretē kā polinomu m(x) pakāpē <k.
- Polinomu reizinot ar x^(n−k) pārbīda paritātes vietām.
- Aprēķina atlikušo dalījumu, dalot x^(n−k)·m(x) ar ģeneratorpolinomu g(x); paritātes simboli ir šī dalījuma atlikums.
- Rezultāts ir kodvārds c(x) = x^(n−k)·m(x) − r(x), kas satur gan datus, gan paritātes.
Dekodēšana — darbības solis pa solim
Galvenie dekodēšanas soļi ir šādi:
- Sindromu aprēķins: novērtē c(x) noteiktos punktos; ja visi sindromi = 0, kļūdu nav.
- Kļūdu lokatora polinoma atrašana: izmantojot algoritmus kā Berlekamp–Massey vai Eiklīda algoritmu, tiek atrasts kļūdu lokatora polinoms σ(x), kura saknes norāda kļūdu pozīcijas (Chiena meklēšana ļauj ātri pārbaudīt visas pozīcijas).
- Kļūdu vērtību (magnitūdu) aprēķins: izmantojot Forney formulu vai kļūdu novērtētāja polinomu ω(x) un σ'(x) (lokatora polinoma atvasinājumu), aprēķina, cik jālabojas katrā atrastajā pozīcijā.
- Koriģēšana: katrā atrastajā pozīcijā noņem atbilstošo kļūdas vērtību, atjaunojot sākotnējo kodvārdu.
Algoritmi un optimizācijas
- Berlekamp–Massey: efektīvs algoritms kļūdu lokatora polinoma atrašanai, īpaši populārs praktiskā realizācijā.
- Eiklīda algoritms: lieto, lai atrisinātu vienādojumus starp polinomiem (piemēram, ātrai ārstēšanai ar lieliem m un n).
- Chien meklēšana: ātri pārbauda, kuras lauka elementu inversijas ir saknes lokatora polinomam — praksei piemērots gandrīz reāllaika meklēšanas paātrinājums.
- Forney formula: nodrošina kļūdu vērtību aprēķinu, izvairoties no tiešas lineāru vienādojumu risināšanas par katru kļūdu.
Erāziju (erasure) un starplīšanas (interleaving) izmantošana
Ja tiek zināmas kļūdu pozīcijas (erāzijas), RS kodi var koriģēt līdz n − k erāzijām bez papildus sarežģījumiem; kombinējot kļūdas un erāzijas, korekcijas spēja sadalās pēc formulas 2e + s ≤ n − k (kur e ir kļūdu skaits, s ir erāzijas skaits). Starplīšana (interleaving) tiek lietota, lai nošķirtu ilgstošus kļūdu blokus, pārvēršot tos par atsevišķām symboliskām kļūdām, ko RS kodi spēj labot efektīvāk.
Praktiskas piezīmes
- RS kodi bieži tiek izmantoti kopā ar citām līmeņa kodēšanas metodēm (piem., konvolūcijas kodi, turbo kodi) kā daļa no daudzslāņu kļūdu korekcijas sistēmām.
- Paritātes garums ietekmē gan korekcijas spēju, gan lieko datu apjomu; izvēle ir kompromiss starp drošību un efektivitāti.
- RS kodi ir simbolu līmeņa kodi — tāpēc tie ir īpaši piemēroti, ja datu kļūdas rodas baitu vai symbolu blokos (piem., atmiņas ierīcēs vai optiskajos diskos).
Vēsture
Rīda–Solomona kodus 1960. gadā izstrādāja Irving S. Reed un Gustave Solomon. Kopš tā laika tie kļuvuši par pamatu daudziem industriāliem risinājumiem, pateicoties to spējai atgūt datus pat pie salīdzinoši lielas kļūdu intensitātes.
Secinājums
Rīda–Solomona kodi ir universāls un spēcīgs kļūdu korekcijas līdzeklis, īpaši efektīvs simbolu līmeņa kļūdu un kļūdu bloku gadījumos. Zināšanas par tiem un to dekodēšanas algoritmiem ir būtiskas gan teorētiskajai informācijas aizsardzībai, gan praktisko datu pārsūtīšanas un glabāšanas sistēmu izstrādei.
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.
Meklēt