Reed–Solomon error correction (tsz. Reed–Solomon error corrections)
A Reed–Solomon kódok egy adatblokkon működnek, amelyeket véges mezős elemek halmazaként kezelnek, amelyeket szimbólumoknak neveznek. A Reed–Solomon kódok képesek több szimbólumhibát észlelni és kijavítani. Ha t = n − k ellenőrző szimbólumot adunk az adatokhoz, a Reed–Solomon kód legfeljebb t hibás szimbólum bármely kombinációját képes észlelni (de nem korrigálni), vagy akár ⌊ t /2⌋ hibás szimbólumot is megkeresni és kijavítani ismeretlen helyeken. Törlési kódként legfeljebb t törlést tud kijavítani az ismert és az algoritmus számára biztosított helyeken, vagy képes észlelni és kijavítani a hibák és törlések kombinációit. A Reed–Solomon kódok alkalmasak többszörös burst bithiba-javító kódként is, mivel a b + 1 egymást követő bithiba sorozat legfeljebb két b méretű szimbólumot érinthet . A t választása a kód tervezőjén múlik, és tág határok között választható.
A Reed–Solomon kódoknak két alapvető típusa van – az eredeti nézet és a BCH nézet –, amelyek közül a BCH nézet a leggyakoribb, mivel a BCH nézet dekódolói gyorsabbak és kevesebb tárhelyet igényelnek, mint az eredeti nézet dekódolói.
Történelem A Reed–Solomon kódokat 1960-ban Irving S. Reed és Gustave Solomon fejlesztette ki , akik akkoriban az MIT Lincoln Laboratory munkatársai voltak . Alapvető cikkük a „Polinomiális kódok bizonyos véges mezők felett” címet viselte. A Reed és Solomon cikkben leírt eredeti kódolási séma a kódolandó üzeneten alapuló változó polinomot használt, ahol a kódoló és a dekódoló csak egy rögzített értékkészletet (kiértékelési pontokat) ismer, amelyeket kódolni kell. Az eredeti elméleti dekóder potenciális polinomokat generált a fogadott üzenet n értékéből ( kódolatlan üzenethossz) k részhalmazai alapján (kódolt üzenethossz), a legnépszerűbb polinomot választotta helyesnek, ami a legegyszerűbb esetek kivételével minden esetben nem volt praktikus. Ezt kezdetben úgy oldották meg, hogy az eredeti sémát egy BCH-kódszerű sémára változtatták, amely egy rögzített polinomon alapult, amelyet mind a kódoló, mind a dekódoló ismer, de később az eredeti sémán alapuló gyakorlati dekódolókat fejlesztettek ki, bár lassabbak voltak, mint a BCH sémák. Ennek az az eredménye, hogy a Reed–Solomon kódoknak két fő típusa van: az egyik az eredeti kódolási sémát és a másik a BCH kódolási sémát használja.
Szintén 1960-ban egy Daniel Gorenstein és Neal Zierler által kifejlesztett , gyakorlatias rögzített polinomiális dekódert BCH kódokhoz írt le az MIT Lincoln Laboratory Zierler 1960. januári jelentésében, majd egy 1961. júniusi cikkben. A Gorenstein–Zierler dekódert és a kapcsolódó munkákat a BCH Codes "orreccer" című könyvében ismerteti . Wesley Peterson (1961). 1963-ra (vagy esetleg korábban) JJ Stone (és mások) felismerte, hogy a Reed–Solomon kódok használhatják a rögzített generátorpolinom BCH sémáját, így az ilyen kódok a BCH kódok speciális osztályává válnak, de az eredeti kódolási sémán alapuló Reed–Solomon kódok nem a BCH kódok osztályai, és a kiértékelési pontok halmazától függően nem is ciklikus kódok .
1969-ben egy továbbfejlesztett BCH séma dekódert fejlesztettek ki Elwyn Berlekamp és James Massey által, és azóta Berlekamp–Massey dekódoló algoritmusként ismerték .
1975-ben Yasuo Sugiyama egy másik továbbfejlesztett BCH séma dekódert fejlesztett ki a kiterjesztett euklideszi algoritmus alapján .
1977-ben a Reed–Solomon kódokat a Voyager programban összefűzött hibajavító kódok formájában implementálták . A tömeggyártású fogyasztói termékek első kereskedelmi alkalmazása 1982-ben jelent meg a CD-vel , ahol két egymásba lapozott Reed–Solomon kódot használnak. Ma a Reed–Solomon kódokat széles körben alkalmazzák a digitális tárolóeszközökben és a digitális kommunikációs szabványokban, bár lassan felváltják őket a Bose–Chaudhuri–Hocquenghem (BCH) kódok . Például a Reed–Solomon kódokat a Digital Video Broadcasting (DVB) DVB-S szabványa használja egy konvolúciós belső kóddal együtt , de a BCH kódokat az LDPC utódjában, a DVB-S2- ben használják .
1986-ban kifejlesztettek egy eredeti sémadekódert, amely Berlekamp–Welch algoritmus néven ismert.
1996-ban Madhu Sudan és mások az eredeti sémadekóderek listás dekódereknek vagy soft dekódereknek nevezett változatait fejlesztették ki, és a munka folytatódik az ilyen típusú dekódereken (lásd Guruswami–Sudan listadekódoló algoritmus ).
2002-ben egy másik eredeti sémadekódolót fejlesztett ki Shuhong Gao, amely a kiterjesztett euklideszi algoritmuson alapul .
Alkalmazások Adattárolás A Reed–Solomon kódolást nagyon széles körben használják a tömegtároló rendszerekben az adathordozó hibáihoz kapcsolódó burst hibák kijavítására.
A Reed–Solomon kódolás a CD kulcsfontosságú eleme . Ez volt az első erős hibajavító kódolás alkalmazása tömeggyártású fogyasztói termékekben, és a DAT és a DVD hasonló sémákat használ. A CD-n a Reed–Solomon kódolás két rétege, amelyeket egy 28 irányú konvolúciós interleaver választ el egymástól, a Cross-Interleaved Reed–Solomon Coding ( CIRC ) elnevezésű sémát eredményezi . A CIRC dekóder első eleme egy viszonylag gyenge belső (32,28) Reed–Solomon kód, amely egy (255,251) kódból van lerövidítve 8 bites szimbólumokkal. Ez a kód legfeljebb 2 bájtos hibát javíthat 32 bájtos blokkonként. Ennél is fontosabb, hogy törli a nem javítható blokkokat, azaz a 2 bájtnál több hibával rendelkező blokkokat. A dekódolt 28 bájtos blokkokat a törlési jelzésekkel ezután a deinterleaver szétosztja a (28,24) külső kód különböző blokkjaira. A deinterleavingnek köszönhetően a belső kódból törölt 28 bájtos blokk egyetlen törölt bájttá válik a 28 külső kódblokk mindegyikében. A külső kód ezt könnyen kijavítja, mivel blokkonként legfeljebb 4 ilyen törlést tud kezelni.
Az eredmény egy CIRC, amely képes teljesen kijavítani a 4000 bites hibákat, vagyis körülbelül 2,5 mm-t a lemez felületén. Ez a kód olyan erős, hogy a legtöbb CD-lejátszási hibát szinte bizonyosan olyan követési hibák okozzák, amelyek miatt a lézer ugrál a pályán, nem pedig a javíthatatlan hibakitörések.
A DVD-k hasonló sémát használnak, de sokkal nagyobb blokkokkal, (208 192) belső kóddal és (182 172) külső kóddal.
A Reed–Solomon hibajavítást olyan parchiv fájlokban is használják, amelyeket általában a kísérő multimédiás fájlokhoz tesznek közzé a USENET- en . A Wuala (2015-ben megszűnt) elosztott online tárhelyszolgáltatás is a Reed–Solomont használta a fájlok felosztására.
Vonalkód Szinte minden kétdimenziós vonalkód, mint például a PDF-417 , MaxiCode , Datamatrix , QR Code , Azec Code és Han Xin kód Reed–Solomon hibajavítást használ, hogy lehetővé tegye a helyes leolvasást még akkor is, ha a vonalkód egy része sérült. Ha a vonalkód-leolvasó nem ismeri fel a vonalkód szimbólumot, azt törlésként kezeli.
A Reed–Solomon kódolás kevésbé elterjedt az egydimenziós vonalkódokban, de a PostBar szimbólumok használják.
Adatátvitel A Reed–Solomon kódok speciális formái, különösen a Cauchy -RS és a Vandermonde -RS, használhatók a törlési csatornákon keresztüli adatátvitel megbízhatatlan jellegének leküzdésére . A kódolási folyamat egy RS( N , K ) kódot feltételez, amely N darab N szimbólum hosszúságú kódszót eredményez , amelyek mindegyike K adatszimbólumot tárol, amelyeket azután egy törlési csatornán küldenek el.
A másik végén kapott K kódszó bármilyen kombinációja elegendő az összes N kódszó rekonstruálásához. A kódsebesség általában 1/2-re van állítva, kivéve, ha a csatorna törlési valószínűsége megfelelően modellezhető és kisebbnek látszik. Összefoglalva, N általában 2 K , ami azt jelenti, hogy az elküldött kódszavak legalább felének meg kell érkeznie ahhoz, hogy az összes elküldött kódszót rekonstruálhassuk.
A Reed–Solomon kódokat az xDSL rendszerek és a CCSDS Space Communications Protocol Specifications is használják a továbbítási hibajavítás egyik formájaként .
Térátvitel
Mélytér-összefűzött kódrendszer. Jelölés: RS(255, 223) + CC ("korláthossz" = 7, kódsebesség = 1/2). A Reed–Solomon kódolás egyik jelentős alkalmazása a Voyager program által visszaküldött digitális képek kódolása volt .
A Voyager bevezette a konvolúciós kódokkal összefűzött Reed –Solomon kódolást , amely gyakorlat azóta nagyon elterjedt a mélyűrben és a műholdas (pl. közvetlen digitális műsorszórás) kommunikációban.
A Viterbi dekóderek általában rövid sorozatokban produkálnak hibákat. Ezeket a sorozathibákat a legjobban rövid vagy egyszerűsített Reed–Solomon kóddal lehet kijavítani.
Az összefűzött Reed–Solomon/Viterbi-dekódolt konvolúciós kódolás modern változatait a Mars Pathfinder , a Galileo , a Mars Exploration Rover és a Cassini küldetéseken használták és használják , ahol a végső határ, a Shannon-kapacitás 1–1,5 dB -en belül teljesítenek .
Ezeket az összefűzött kódokat most erősebb turbókódok váltják fel :
A NASA küldetései által használt csatornakódolási sémák Évek Kód Küldetés(ek) 1958 – napjainkig Kódolatlan Explorer, Mariner és még sokan mások 1968–1978 konvolúciós kódok (CC) (25, 1/2) Úttörő, Vénusz 1969–1975 Reed-Muller kód (32, 6) Tengerész, viking 1977 – napjainkig Bináris Golay kód Voyager 1977 – napjainkig RS(255, 223) + CC(7, 1/2) Voyager, Galileo és még sokan mások 1989–2003 RS(255, 223) + CC(7, 1/3) Voyager 1989–2003 RS(255, 223) + CC(14, 1/4) Galileo 1996 – napjainkig RS + CC (15, 1/6) Cassini, Mars Pathfinder és mások 2004 – napjainkig Turbó kódok Messenger, Stereo, MRO, mások becslések szerint 2009 LDPC kódok Csillagkép, MSL