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.