Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- msz:kodovani_shannonova_veta_o_kodovani_bezpecnostni_kody [16. 06. 2012, 09.27:49] – [Shannonova věta o kódování] pitel
+++ msz:kodovani_shannonova_veta_o_kodovani_bezpecnostni_kody [04. 09. 2026, 20.19:30] (aktuální) – odstraněno - upraveno mimo DokuWiki (Neznámé datum) 127.0.0.1
@@ Řádek 1: / Řádek 1: @@
-====== Kódování, Shannonova věta o kódování, bezpečnostní kódy ======
-===== Kódování =====
-[[wp>Code]]
-Kódování převádí informace jednoho typu do jiné reprezentace. Například morseovka.
-Neplést si s šifrováním! U kódování je známo jak se to převádí, u šifrování ne.
-===== Shannonova věta o kódování =====
-[[wp>Shannon's source coding theorem]]
-Má-li diskrétní kanál kapacitu //C// > 0, pak použitím dostatečně dlouhých kódovaných úseků lze produkce informace //H//′(//X//) < //C// libovolně přiblížit k //C// a přitom učinit pravděpodobnost chyby libovolně malou.
-  * Rychlost produkce informace: //H//′(//X//) = //H//(//X//) / //T//
-    * //H//(//X//) -- množství informace připadající v průměru na jeden symbol
-    * //T// -- průměrný čas vysílání jednoho symbolu: //T// = 1 / //vₘ//
-      * //vₘ// -- modulační rychlost
-===== Bezpečnostní kódy =====
-[[wp>Forward error correction]]
-Pokud se zprávy posílají po nespolehlivém médi na kterém vznikají chyby, používají se bezpečnostní kódy. Tyto kódy umožňují chybu detekovat, a ideálně i opravit. Slovo s bezpečnostním kódem musí být vždy delší než původní slovo, dochází k redundanci.
-==== Lineární ====
-[[wp>Linear code]]
-Lineární bezpečnostní kód je takový kód, kde libovolná lineární kombinace kódových slov je také kódové slovo.
-==== Hammingovy ====
-{{ http://upload.wikimedia.org/wikipedia/commons/thumb/b/b0/Hamming%287%2C4%29.svg/300px-Hamming%287%2C4%29.svg.png}}
-[[wp>Hamming code]], [[wp>Hamming(7,4)]]
-Hammingův kód (7, 4) znamená že ze 4 bitů zprávy vytvoříme 7 bitů přídáním 3 paritních bitů. Tento kód umožňuje detekovat 2 chybné bity a 1 bit opravit. Paritní a datové pity jsou uspořádány: //PPDPDDD//.
-Potřebujeme generovací matici //G// a paritní matici //H//:
-<m>G = (matrix{7}{4}{1 1 0 1  1 0 1 1  1 0 0 0  0 1 1 1  0 1 0 0  0 0 1 0  0 0 0 1})</m>
-<m>H = (matrix{3}{7}{1 0 1 0 1 0 1  0 1 1 0 0 1 1  0 0 0 1 1 1 1})</m>
-Všimněte si u matice //G//, že řádky 3, 5, 6 a 7 reprezentují datové bity a obsahují jen jednu 1. Oproti tomu řádky 1, 2 a 4 jsou bity paritní, a označují ze kterých bitů se bude parita počítat.
-<note>Jak si zapamatovat který paritní bit pokrýva které datové nevím. :-(</note>
-Výslednou zprávu získáme vynásobením matice //G// zprávou (''1011''):
-<m>(matrix{7}{4}{1 1 0 1  1 0 1 1  1 0 0 0  0 1 1 1  0 1 0 0  0 0 1 0  0 0 0 1}) * (matrix{4}{1}{1 0 1 1}) = (matrix{7}{1}{0 1 1 0 0 1 1})</m>
-Výsledná zpráva tedy bude ''0110011''.
-<note tip>Místo celého násobení se stačí podívat na počet stejných jedniček. Např 1. řádek: ''__1__10__1__'' a ''__1__01__1__''. Pokud je jich sudý počet, bude výsledek ''0'', pokud lichý, tak ''1''.</note>
-----
-Při kontrole vynásobíme matici //H// zprávou:
-<m>(matrix{3}{7}{1 0 1 0 1 0 1  0 1 1 0 0 1 1  0 0 0 1 1 1 1}) * (matrix{7}{1}{0 1 1 0 0 1 1}) = (matrix{3}{1}{0 0 0})</m>
-Opět můžeme použít trik se stejnými jedničkami.
-Pokud vyjdou samé nuly, byla zpráva přijata v pořádku.
-Pokud ne, porovnáme matici se sloupci matice //H// a ten u kterého se shoduje je chybný bit. Stejně tak můžeme binární čislo přečíst odzhora. Například ''101'' = 5, a také je to 5. sloupec v matici //H//.
-==== Cyklické ====
-[[wp>Cyclic code]], [[wp>Cyclic redundancy check]], [[wp>Computation of CRC]]
-<note important>Hodnoty v obrázcích neodpovídají hodnotám v textu!</note>
-{{ http://upload.wikimedia.org/wikipedia/commons/0/02/CRC8-gen.gif}}
-Zakódování ''11010011101100'' polynomem //x//³ + //x// + 1:
-<code>
-11010011101100 000 <--- ke vstupu přidáme 3 bity
-               <--- dělitel (XOR) x³ + x + 1
-01100011101100 000 <--- výsledek
-              <--- dělitel…
-00111011101100 000
-00010111101100 000
-00000001101100 000
-00000000110100 000
-00000000011000 000
-00000000001110 000
-00000000000101 000
-1
------------------
-00000000000000 100 <---zbytek (3 bity)
-</code>
-Zbytek připojíme za zprávu: ''11010011101100 100''.
-----
-{{ http://upload.wikimedia.org/wikipedia/commons/1/17/CRC8-rx.gif}}
-Při kontrole postupujeme stejně, zbytek musí vyjít ''0'', jinak nastala chyba:
-<code>
-11010011101100 100 <--- vstup s CRC
-               <--- dělitel
-01100011101100 100 <--- vysledek
-              <--- dělitel…
-00111011101100 100
-......
-00000000001110 100
-00000000000101 100
-1
-------------------
-<--- zbytek
-</code>
-==== Konvoluční ====
-{{ http://upload.wikimedia.org/wikipedia/commons/2/21/Convolutional_encoder_non-recursive.png}}
-[[wp>Convolutional code]]
-U konvolučního kódu je každý bit nahrazen //n//-ticí bitů. Ke kódování potřebujeme paměťové buňky a ''XOR''y. Z buněk vytvoříme posuvný registr a napojíme na ně ''XOR''y.
-Na začátku obsahují všechny buňky ''0''. Přivedem na vstup slovo které chceme zakódovat. Jeho první bit dáme do první paměti, provedeme ''XOR''y a dostaneme //n//-tici. Shiftneme registr a do první buňky dáme druhý byt, ''XOR''ujeme, shiftneme, ... dokud nejsou v buňkých zase samé nuly.
-To je také možné reprezentovat konečným automatem. Stavy jsou možné stavy pamětí, přechody podle dalšího bitu generují //n//-tice.
-Průchod takovým automatem je mopžné vyjádřit Trellis diagramem.
-{{http://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/Convolutional_code_trellis_diagram.svg/300px-Convolutional_code_trellis_diagram.svg.png}}

Kalábovi

Uživatelské nástroje

Nástroje pro tento web

Rozdíly

Nástroje pro stránku