===== 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. 

==== Cyklické kódy ====

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

==== Známe triedy kódov ====

pozri: 
http://en.wikipedia.org/wiki/Linear_code#Example:_Hamming_codes
http://en.wikipedia.org/wiki/Linear_code#Example:_Hadamard_codes
===== Předměty =====
  * [[https://is.muni.cz/auth/predmet/fi/IV054|IV054 Kódování, kryptografie a kryptografické protokoly]]
  * [[https://is.muni.cz/auth/predmet/sci/M8170|M8170 Teorie kódování]]

===== Zdroje =====
  * http://www.fi.muni.cz/usr/gruska/crypto12/
  * [Paseka] https://is.muni.cz/el/1431/jaro2011/M8170/um/PREDLAwideboc.pdf
  * [Gruska] http://www.fi.muni.cz/usr/gruska/crypto12/crypto_02.pdf
  * [Gruska1] http://www.fi.muni.cz/usr/gruska/crypto12/crypto_03.pdf

===== Související otázky =====
  * [[mgr-szz:in-psk:3-psk]]
  * [[mgr-szz:in-bit:1-bit]]

===== Vypracoval =====

Michal Abaffy
Moja spokojnosť s vypracovaním: 75%. Ešte treba viac k cyklickým kódom z [Gruska1]