Hogyan kell megoldani az alábbi képen látható kódolási feladatokat? CRC kódolás. Szindróma dekódolás.

Jó, az első feladatot megcsináltam:

A kódszó: 101, polinomalakja: M(x) = x^2 + 1

A generátorpolinom bináris képe: 1 1 1

Eltolás: M(x)*x^n = 1 0 1 0 0 0

Ezt le kell osztani P(x)-szel.

Az eredmény felírható Q(x) + R(x) /P(x) alakban:

111 + 001/(111)

Tehát az üzenet: T(x) = x^n*M(x) + R(x) = 101000 + 001 = 101001.

----

110111 : 111 = 1111

A maradék nem 0, hanem 101, tehát ez nem lehet kódszó.

6)

CRC kódolás. A generátor-polinom:

g(x) = x² + x + 1

Hmm, azt írja, n=6 hosszú. Ez másodfokú, szóval csak 2 hosszú. Szokatlan így megadni a generátor polinomot, jó lenne látni a jegyzeteteket. Arra tudok csak gondolni, hogy hozzá kell még adni x⁶-t, de egyáltalán nem vagyok benne biztos. (A generátor polinom legnagyobb helyiértékű tagjának együtthatója 1 kell legyen.)

G(x) = x⁶ + x² + x + 1

Amit az elején írok, az nem kell a feladat megoldásához, mondjuk magamnak írom magyarázatként...

A fenti G(x) azt jelenti, hogy 6 bit hosszú a shift regiszter. Bemeneteinek jele 1, x, x², x³ ... x⁵, kimenetének elnevezése x⁶. Az alsó helyiértéken (1) megy be az adat, a túlsó vége pedig (x⁶) vissza van csatolva egy-egy XOR kapuval az 1, x és x² bemenetein is.

Vagyis ilyesmi:

  1       x        x²     x³  x⁴  x⁵  x⁶

−⊕−⊲−⊕−⊲−⊕−⊲−⊲−⊲−⊲−

  |         |        |                       |

  ^−−−−^−−−^−−−−−−−−−−−

(A ⊲ jelöli a shift regisztereket, a ⊕ az xor kaput.)

Az üzenetet bitenként bevezetjük balról, aztán amikor belement az utolsó bit is, akkor még 6 darab nullás bitet is belevezetünk, és ami 6 bit a shift regiszter végén ekkor kijön, (a polinomosztás maradéka), az lesz a CRC kód. Azt a 6 bitet is az üzenet mögött elküldjük.

Vételkor ugyanúgy bemegy a vett bitsorozat a regiszterekbe, majd a végen bemegy a 6 CRC bit is. Ha ezek után a shift regiszterekben nem csupa 0 marad, akkor hibás volt az átvitel. (Hisz ha M(x)-et osztva G(x)-szel a maradék R(x), akkor M(x)+R(x) osztható G(x)-szel modulo 2.)

- - - - - - - - -

Most már a feladat megoldása jön:

Az üzenet most 101. Nem értem, hogy miért írja a feladat, hogy a bal oldalon van a legkisebb helyiértékű bit, én több helyen is úgy látom, hogy fordítva kezelik. (Most nem számít, mert szimmetrikus az üzenet, de a ZH-n lehet más is.) Jó lenne látni, hogy a ti jegyzetetek hogyan csinálja a polinomokat... Nem biztos, hogy úgy, ahogy én fogom.

- A generátor polinom x⁶+x²+x+1, számértékben 1000111. Ez 7 bites, nem 6, nem írtam el!

- Az üzenet 101. (Ha komolyan vesszük, hogy bal oldalon van a kis helyiérték, akkor meg kell fordítani...)

Ennek polinomja 1·x²+0·x+1·1, vagyis x²+1. (Nem muszáj felírni polinomként...)

- A generátor hatodfokú, tehát 6-tal kell el-shiftelni az üzenetet. Ez x⁶-nal való szorzást jelent: M(x)=x⁸+x⁶

Számértékben ez 101000000 lesz (hozzáírtam 6 darab nullát)

- Elvileg el kell osztani M(x)-et G(x)-szel modulo 2. Valójában egyszerűbb az 101000000-t elosztani 1000111-gyel:

101000000 : 1000111

Modulo 2 osztáskor azonos hosszú sorozatokat osztunk és csak az első bit számít. Vagyis ha 1xx..-et osztunk 1yy..-nal, akkor megvan 1-szer. Ha 0xx..-et osztunk 1yy..-nal, akkor 0-szor, akármi is xx.. és yy...

- 1010000-ben megvan 1-szer, a maradék kijön, ha kivonjuk belőle az 1000111-et. Modulo 2-ben ez xor-olást jelent, vagyis ott lesz 1, ahol a bitek különböznek. Írd alá, akkor gyorsan látszik a különbség:

  1000111

A maradék:

  0010111

A maradék felső bitje tuti, hogy mindig 0 lesz. Azt el is kell hagyni, tehát most a maradék 010111 lett. (A második bitet már nem kellene elhagyni, hiába 0!)

A következő bitet a kibővített üzenetből (0) hozzárakjuk:

- 0101110-ban megvan 0-szor.

A maradék ugyanaz, az első nullát elhagyva 101110

A következő bitet (0) hozzárakjuk:

- 1011100-ban az

  1000111 megvan 1-szer

A maradék:

  0011011, vagyis 011011

Nincs több bit, kész vagyunk. Ez a CRC kód.

(polinom alakban x⁴+x³+x+1, de ez sem kell igazán most.)

Kódszó-e az 110111?

- Ez 6 hosszú. A kódszó az eredeti üzenet plusz mögötte a CRC kód, ami önmaga 6 bites. Ez tehát csak akkor lehetne kódszó, ha üres lenne az üzenet. Üres üzenet CRC-je (000000 osztva 1000111 maradéka) viszont 000000, nem ez.

Brr, a szépen összerakott shift regiszteremet elrontotta a honlap...

Megpróbálom kicsit máshogy:

  1         x         x²                     x⁶

--⊕--⊲--⊕--⊲--⊕--⊲--⊲--⊲--⊲-

   |          |          |                       |

  ^- - - - ^ - - - - ^ - - - - - - - - - -

Ha most se sikeül, nem próbálkozom tovább :)

Igy első blikkre az üzenetpolinom kisebb mint a generátorpolinom, vagyis osztó nagyobb mint az osztandó. Ez szívás, mert ilyenkor az osztási maradék maga az osztandó.

Például kettőben a három megvan nullaszor és még marad kettő, vagyis a crc is kettő lesz.