A Reed-Salamon kód egy véges, mezőn alapuló korrekciós kód, amelynek elve egy formális polinom felépítése a továbbítandó szimbólumokból és a mintavétel . Ezután elküldi az eredményt az eredeti szimbólumok helyett. Ennek a túlmintázásnak a redundanciája lehetővé teszi, hogy a kódolt üzenet vevője rekonstruálja a polinomot akkor is, ha az átvitel során hibák merültek fel .
Ezt a kódot Irving S. Reed és Gustave Salamon köszönheti . Különösen CD-k kódolására használták .
Legyen m , n , k , t szigorúan olyan pozitív egész szám, hogy . Általában m = 8 (néha m = 16), n = 255, k = 239, t = 8. A Reed-Salamon kódok blokk kódok. Valójában bemenetként rögzített méretű k blokkot vesznek , ahol minden egyes adat a véges mező elemszimbóluma, amelynek elemei vannak. Ehhez a blokkhoz 2 t vezérlőszimbólumot adunk , így egy fix nagyságú kimeneti blokk alakul ki, amely egyenlő n-vel . Így:
A vezérlő szimbólumok hozzáadásának köszönhetően ezek a kódok kétféle hiba kijavítását teszik lehetővé:
Megjegyezzük egy Reed-Salamon kódoló ill .
Ha a hiba lokalizációja nem ismert előre - ami a gyakorlatban is így van - a Reed-Salamon kódolás ismert módon korrigálja a t hibákat.
n mivel a gyakorlatban gyakran túl nagy, az információ egy része nullával helyettesíthető a kódolás előtt, és nem kerül továbbításra, de a dekódolás előtt hozzá kell adni. Ebben a rövidített Reed-Salamon kódok esetében beszélünk .
Bármelyik véges mezőben elképzelhető Reed-Salamon kódok is.
A Reed-Salamon kódnak számos változata van, amelyeket az elmúlt évtizedekben fejlesztettek ki azzal a céllal, hogy a kódolási és dekódolási folyamatokat egyre gyorsabbá tegyék. Az egyik lehetséges variációt itt mutatjuk be.
Legyen egy A üzenet, amely a véges mező k elemi szimbólumából áll . Ennek a mezőnek van 2 jellemzője , ami azt jelenti, hogy megfelel az 1 + 1 = 0, vagy akár 1 = -1 számítási szabálynak, vagy hogy nincs különbség az összeg és a különbség között. Van egy úgynevezett primitív eleme is, amelynek a következő tulajdonsága van:
Így a (z) nem nulla elemei felírhatók lineáris kombinációkként a (0,1) együtthatókkal, de 0 és 0 közötti hatványként is .
Az A üzenetet alkotó k szimbólumokat a k -1- nél kisebb vagy azzal egyenlő fokú polinom együtthatóinak tekintjük , vagyis annak egy elemét . Ez a polinom az továbbítandó információ, amelyet újra megjegyezünk .
Generátor polinomnak nevezzük a 2 t fokú polinomot , amelyet az alábbiak szerint határozunk meg:
Ez a polinom gyökereknek ismeri el a .
Meghatározzuk, hogy a vezérlő polinom az euklideszi osztás fennmaradó része . Ez a polinom fokozata szigorúan kevesebb, mint 2 t . Ennek a polinomnak az együtthatói alkotják az A információvezérlő kódot.
Ezután meghatározzuk a polinomot . Ez a polinom fokozata kisebb vagy egyenlő . Az a tulajdonsága, hogy lemondja magát . (emlékeztető: még mindig a 2. karakterisztikájú mezőn vagyunk, így a + és - ugyanaz a hatás)
A polinom együtthatóit továbbítjuk a befogadónak. Ezen átvitel során előfordulhatnak bizonyos együtthatókkal kapcsolatos hibák, és a címzett megkapja a polinomot alkotó együtthatókat .
Ezután a címzett teszteli, hogy az összes i esetén 1 és 2 t között van-e . Ha igen, úgy ítéli meg, hogy nem volt átviteli hiba, és ez . Az A információt a polinom legmagasabb fokú kifejezésének k -1 együtthatóiban találja meg .
Ha az egyik legalább nulla, akkor az együtthatók közül legalább az egyiken átviteli hiba lépett fel. A címzett azonban úgy véli, hogy az érintett együtthatók száma kisebb vagy egyenlő, mint t . Ezen feltételezés alapján képes lesz rekonstruálni a kezdeti C üzenetet.
Ha különbözik , azaz egy n- nél kisebb vagy azzal egyenlő fokú polinom , és számos nem nulla együtthatót tartalmaz. Hipotézisünk szerint feltételezzük, hogy kisebb vagy egyenlő t-vel . Pózoljunk:
, És , a jól elkülöníthetők indexek ami változhat 0 és n -1.jelenleg ismeretlen a címzett számára. Neki kell meghatároznia:
A hibák száma , a rangsor, ahol ezek a hibák találhatók, e hibák értékét .Miután ezt az információt rekonstruáltuk, a címzett képes lesz meghatározni a polinomot és rekonstruálni a kezdeti üzenetet . Ehhez a következő öt lépést követjük.
1) Szindrómák kiszámítása : Kiszámoljuk a 2 t mennyiséget , az úgynevezett szindrómákat . Mivel és hogy a nulla, nálunk is van:
Ez 2 t egyenletet eredményez, amelyek ismeretlenek és inkább a 2 t-ben vannak . A rendszer azonban nem lineáris és felbontása technikai.
2) A hibák számának meghatározása: Figyelembe vesszük azt a polinomot, amelynek gyökerei inverzei . Ez a polinom formában kibővül . Ellenőrizhetjük, hogy a fogadó számára ismeretlen együtthatók kielégítenek-e egy lineáris egyenletrendszert, ahol a j -edik egyenlet j esetén 1-től 1-ig változik :
valóban :
Ezenkívül a t- nél kisebb vagy azzal egyenlő legnagyobb érték , amelynél ennek a rendszernek a meghatározója nem nulla, pontosan az a szám, amely megegyezik az átvitt hibák számával. Ezért indulunk ki , és ha a determináns nulla, akkor csökkenünk, amíg nem nullától eltérő determinánst nem kapunk.
3) A hibák helyének meghatározása : Miután így meghatároztuk, a rendszer megoldódik, amely meghatározza a polinomot . Ennek a polinomnak a gyökereit keressük, amelyek inverzei megadják az értékeket . Minden r 1 és megnézzük az energia a úgyhogy . Így meghatározták az átvitt hibák sorait .
4) meghatározása az érték a hibák: Az , hogy ezentúl ismert, lehet megoldani a rendszer, amelynek általános egyenlete , és akiknek ismeretlenek a , amely lehetővé teszi, hogy meghatározza az itt megadott értékek ismeretlenek. Ezek az elkövetett hibák értékei.
5) A beérkezett üzenet javítása: A és a ismeretében ismerjük a polinomot és ezért a kezdeti üzenetet
Ha az információt olyan adathordozóra írják, mint CD vagy DVD, akkor törlési hibák léphetnek fel. A hiba pontosan megtalálható, de ott nem olvashatók információk. A törölt szimbólumokat azonban rekonstruálhatjuk a szindrómák által adott egyenletek segítségével. Mivel a helyek ismertek, hogy az ismeretlenek az egyedüli értékek és 2 t egyenletünk van, javíthatjuk a szimbólumok törlését .
A CD -hez 2 Reed-Salamon kódolást használnak (CIRC kód a keresztbe átlapolt Reed-Salamon kódhoz). Először kódolunk egy C1 = RS (28, 24) kóddal, majd összevonunk (ez lehetővé teszi az információk terjesztését annak érdekében, hogy jobban ellenállhassunk az egymást követő hibák vonatainak, amelyek karcolást okozhatnak, amely sok bájtot pusztít lokálisan). , akkor az összevont adatokat ismét C2 = RS kóddal kódoljuk (32, 28). Az ötlet az, hogy az első kód lehetővé teszi a környezeti zaj kiküszöbölését, de ha nem tudja kijavítani (például ha hibajelenség van), akkor törli a blokkot (mert kétszer annyit javíthatunk, hogy csak hamis karaktereket törölünk) majd a kódot átcsatolják . Így az információvesztés az adatok nagy tartományára hígul, ami lehetővé teszi a kód számára, hogy kijavítsa ezeket a törléseket.
A DVD esetében az elv ugyanaz, mint a CD esetében, van egy PI = RS (182, 172) és egy PO = RS (208, 192) kód.
A DVB , a kódolás RS (204, 188, t = 8)
Az ADSL / ADSL2 / ADSL2plus esetében a kódolás gyakran RS (240, 224, t = 8) vagy akár RS (255, 239, t = 8).
a DVB , a kódolás RS (204, 188, t = 8)
A bemeneten lévő 188 (= k) bájt esetében 16 (= 2 t ) hibajavító bájtot adunk hozzá , ami 204-et eredményez a kódoló kimenetén.
204-ből 8 bájt (= t) javítható.
Ha több mint 8 bájtot hibásnak észlel, a felhasználói adatblokkot hibásnak jelöli. Ezután nem javít ki hibát
A Reed-Salamon kódolás által kijavítható szimbólumok kis száma miatt ez a kódolás nagyon rossz hosszú ideig tartó impulzuszaj vagy rendszeres véletlenszerű zaj esetén.
Általánosságban elmondható, hogy átvitel közben egy modemben (ADSL, IDR / SMS műholdas modem, DVB-S stb.) A Reed-Salamon kódolást, amelyet egy interleaver erősít, konvolúciós kódoló kíséri. A vételkor a maradék hibákat, amelyeket a Viterbi dekóder nem javított ki, akkor az eredeti blokkokban interaktiválják, és a Reed-Salamon dekóderrel korrekciós erejének erejéig kijavítják.
A deinterlacer célja a vétel során egy csoportosított és sokszor nem kijavítható (impulzív zaj) hibaszakasz helyettesítése a Reed-Salamon dekóder számára elosztott és gyakran kijavítható hibák sokaságával.