199046. lajstromszámú szabadalom • Eljárás és berendezés hibajavító kódolárú kódjelek dekódolására

5

HU 199046 F

6

vett kimenő kódjel továbbítható vagy rögzíthető pl. egy (nem ábrázolt) mágnesfejjel ellátott mágnesszalagos egységre. Ez esetben lehetőség van arra, hogy a kimenő kódjelet visszaírjuk a 4 RAM jnemóriába, és hogy más 5 sorrendben olvassuk ki rögzítés céljából.

A 2. ábra a fent leírt kódoló által kialakított kódjelek egy konfigurációját mutatja.

Az információs szimbólum jelek egy (ki x k2) méretű, kétdimenziós alakzatban vannak el- 10 rendezve. A vízszintes irányban elrendezett k2 információs szimbólum jelek, azaz a kétdimenziós elrendezés minden sora, alá van vetve a C2 kód szerinti kódolási eljárásának. A függőleges irányban elrendezett ki informá- 15 ciós szimbólum jelek, azaz a kétdimenziós elrendezés minden oszlopa, alá van vetve a Cl kód szerinti kódolási eljárásnak. A Cl kód szerinti kódolásban a Cz paritás adatok is résztvesznek. A Cl kód pl. egy (ni, ki) 20 Reed-Solomon kód, amellyel maximum (rn - - ki)/2 szimbólum jel hibáját lehet javítani.

A Reed-Solomon kód dekódolásának általános módszere az alábbi. Az (n, k) Reed-Solomon kód - ahol n jelöli a kód hosszát és k 25 jelöli az információs szimbólum jelek számát - Hamming-távolságát egy GF(2") Galois mezőben d = n - k + 1 alakban lehet kifejezni, a generátor polinom (x + of4) alakú. Ha a

vett szavakat ro, n, r2,...rn-i betűkkel je- 30 löljük, akkor a szindrómát a következő kifejezés meghatározásával kaphatjuk meg: n-1

Sj = rice« (j = 0, l,...d-2) (1)

i=0 35

Egy cf (z) hibahely meghatározó polinomot és egy w (z) hibaértékeló polinomot nyerünk az Sj szindróma alkalmazásával. Ezen eljárás céljaira az Euklidesz féle kölcsönös osztási eljárást, a Varlay-Camp féle eljárást, 40 a Peterson-módszert stb. javasolják.

A cT(z) = 0 egyenlet megoldásával az Xi hibahely meghatározható. Erre a célra a Chien féle keresési módszert alkalmazzák.

Ezt kővetően az Xj hibahely és az w (z) 45 hibaértékeló polinom alapján az Yi hibaérték megkapható.

A dekódolás)' lépések során felmerülő fenti műveleteket az Xi hibahely (i = 1, 2,...e; ahol e jelöli a hibák számát) és az Yi hibaér- jq ték felvételével világítjuk meg. Mivel a Reed-Solomon kód egy lineáris kód, a szindrómát kifejezhetjük az alábbi módon: e

Sj

Yi XP (j = 1, 2,...d-2).

(2)

55

i=l

(3)

Ha a szindrómát egy d-2

S(z> = ^ | Sj z.J

j=0 60

alakú polinommal fejezzük ki, a következő kifejezéshez jutunk:

e d-2

S(z) = ^ ' Yi y (Xi z)i =

211Yi 22Ix'

i^r j^o

65

Yi

(mod. zd'1).

(4)

i=l 1 - Xi z

Ha a hibahely meghatározó polinomot és a hiba irtékelő polinomot

cf lz) = T!’ (1 - Xj z) J=1

w(z) - cf (z) S (z)

(5)

(6)

ah kban definiáljuk, akkor w(z) az alábbi ah kra hozható:

6 Y ®

1 - Xi z - Xjz) =

i=l J=l

e e

Yi XT (1 - Xj z) j=i

(mod. zd-M

(7)

Az Yi hibaértéket úgy kaphatjuk meg, hogy

7. helyébe Xf1 értéket helyettesítünk és a kifejezést a következőképpen transzformáljuk:

e

Yi = wtXr1)/ TT (1 - XjXfM. (8)

i=l

Példaként egy cf°,.,.cf7 gyökökkel rendelkező (32, 24) Reed-Solomon kódot ismertetünk. Mivel ezen kód Hamming-távolsága d = = 9, lehetőséget, biztosit maximum négy szimbólum javítására. Ha a négy szimbólum hibahflye Xi,...X4 és a hibaértékek Yi,...Y4, a szindrómát a következő kifejezésből nyerjük: 4

Sj ' YiXP (j = 0, 1,2, 3).

A négy szindróma közül az So szindróma:

4

So = ' Yi.

i=1

Ha az Yi, Y2 és Y3 hibaértékeket meghatároztuk, a fennmaradó Y4 hibaérték bonyolultabb számítások nélkül meghatározható:

Y4 = So - Yi - Y2 - Y3.

A GF(2“) kódoknál a kivonás megfelel ery modulo 2 összeadásnak.

A 3. ábra egy ilyen kiviteli alak szerinti d« kóder felépítését, mutatja be. A 3. ábrán a le )1 vásott kódjelek 11 vevő szervről, amely a? ábrázolt, kivitelben egy bemeneti kapocs, Ci kódot dekódoló 12 dekóder bemenetére jutnak. A 12 dekóderben történik meg a Cl kódolású kódjelek dekódolása, ennek során az összes, de legfeljebb (ni - ki)/2 hiba javításra kerül. Ahhan az esetben azonban, ariikor a kódjelek egyetlen sorozatában a hilw k száma nagyobb vagy egyenlő az (ni - - ki)/2 mennyiségnél, ezen sorozat Ci pointer jelét .1 ' értékre, a többi pointer jelet .O' értékre állítjuk be. A 2. és 3. ábrán látható pointer 13 memória n2 bitet tartalmaz és a Cl kódolású kódjelek pointer jeleit tárolja. A 12 dekóder kimenetét átmenetileg a 14 RAM

5