mgr-szz:in-tei:9-tei [Státnice na FI MUNI]

Obsah

Zadání
Vypracování
Předměty
Zdroje
Související otázky
Vypracoval

Zadání

9. Hlavní typy samoopravných kódů a jejich vlastnosti

Vypracování

Ako sa učiť túto otázku?
1) Preletieť toto vypracovanie: získanie prehľadu
2) Prejsť kapitolu o kódoch z Pasekových skrípt: pochopenie problematiky
3) Preletieť toto vypracovanie: získanie nadhľadu
4) Pozrieť sa na to z trocha iného pohľadu [Gruska, Gruska1] pre získanie väčšieho nadhľadu

Úvod

Iné spracovanie: http://statnice.dqd.cz/mgr-szz:in-psk:3-psk#kody_opravujici_chyby

Motivácia

Chceme poslať správu od A do B cez kanál so šumom. Chceme minimalizovať riziko spôsobované šumom, že odoslaná a prijatá správa sa nebudú zhodovať. Spravíme to pridaním informácie ku správam, ktorá nenesie žiadnu informačnú hodnotu, ale pomáha 1) detekovať chybu pri prenose alebo 2) opraviť chybu pri prenose.

Predpokladáme:
- Rovnakú abecedu správ a zakódovaných správ na strane príjemcu a odosielateľa. Značenie abecedy: E.
- Nezávislosť chyby na jednotlivých vysielaných znakoch (to, či nastane chyba v i-tom odoslanom znaku nezávisý na tom, či nastala chyba v j-tom odoslanom znaku). (Ak nebude neskôr jasné, kde sa táto druhá podmienka využíva, radsej to asi nespomínajte)

Blokové kódy

Kód C nad E je súbor(množina) postupností symbolov(slov) z E.
Blokový kód: Kód, ktorého všetky slová sú rovnakej dĺžky.
q-árny kód dĺžky n: |E|=q, slová z C sú dĺžky n.
Zakódovanie: Každej sekvencii znakov o dĺžke k nad E (zdrojovej správe) sa priradí jedno kódové slovo z C.
Dekódovanie: “Behem samotného dekódování se prijatá sekvence rozčlení na bloky délky n a každý se zpracovává samostatne. Jelikož prijaté n-bloky mohou mít díky chybám pri prenosu obecne jinou podobu než vysílaná kódová slova, musí dekodér rozhodovat, které slovo bylo vysláno.“ [Paseka]
Hammingova vzdialenosť: pre dve slová dĺžky n: počet znakov, kde sa líšia. (Slová sú usporiadané n-tice, takže záleží na poradí. Príklad: vzdialonost(01,10)=2 nie 0.)
C určí u chýb: minimálna(vzhľadom k výberu dvojice kódových slov) vzdialenosť medzi 2 kódovými slovami je väčšia(ostro) ako u.
C opraví v chýb: v < celá časť (minimálna vzdialenosť medzi 2 kódovými slovami / 2)
(n,M,d)-kód: (nad NEJAKOU ABECEDOU): n-dĺžka slov, M-počet slov, d-minimálna vzdialenosť medzi 2 slovami.

Ekvivalencia kódov

DEFINICIA (cez príklady)
Pozičná permutácia:
Kód 1: 001,110 —-mením 2. a 3. stĺpec —→ 010,101 : Kód 2
Symbolová permutácia:
Kód 1: 000,111 —-mením v 2. stĺpci 0 a 1 —→ 010,101 : Kód 2

DEFINICIA: Kódy C a C’ sú ekvivalentné ak idú jeden z druhého získať konečnou postupnosťou pozičných a symbolových permutácii.

DEFINICIA: Rozšírenie kódu. Definíciu nedávam, príkladom je Parity check.

Hlavní problém teorie kódování

“Definice. Bud dána prirozená císla d; n; q. Položme A_q(n; d) jakožto maximální M takové, že existuje q-ární (n;M; d)-kód. Každý takový q-ární (n;M; d)-kód nazýváme optimální.“ [Paseka]

PROBLEM: Najst A_q(n,d), pripadne ešte lepšie: (n,A_q(n,d),d)-kód.

VETA:
A_q(n,d) ⇐ q^n
A_q(n,1) = q^n
A_q(n,n)=q

Proof: Trivial.

Lineárne kódy

pozri http://statnice.dqd.cz/mgr-szz:in-psk:3-psk#linearni_kody.

Dodatok k dekódovaniu. Vo vyššie zmienenom odkaze je dekódovanie popisané veľmi vágne, v podstate len „čo chceme“, nie „ako to chceme“. Otázka „Ako to chceme“ je dobre popisaná v [Gruska]. Od tabuľkového dekódovania, cez dekódovania založenom na syndrómoch až po dekódovanie založené na syndrómoch v Hammingových kódoch.

Tu je čosi z toho, ale radšej si prečítajte [Gruska].

Definície:
Koset: „kód plus chyba“. a+C. Množina slov, ktoré vzniknú zo slov kódu C pripočítaním vektoru a.
Syndróm kosetu a+C: Ha^{T}. vektor dĺžky k.
Reprezentant kosetu: vektor e dĺžky n. Ak má minimálnu váhu zo všetkých vektorov v kosete e+C.

Algoritmus dekódovania: SYNDROME DECODING
0) spočítame tabuľky kosetov. Pre každý koset zvolíme reprezentanta. Spraví sa raz a môže sa kódovať donekonečna. Ďalšie kroky robím pri každom prijatí bloku dĺžky n.
1) pri prijatí vektoru y spočítam syndróm Hy^{T}.
2) z vypočítanej tabuľky nájdem reprezentanta (odpovedá najpravdepodobnejšej chybe pri prenose kanálom) z0 kosetu y-C.
3) Prijatý vektor y dekódujeme ako kódové slovo y-z0.
POZN: Ešte treba dekódovať z lineárneho kódu späť k pôvodnej správe pred zakódovaním do lineárneho kódu.