Kódy pro odstranění redundance, pro zabezpečení proti chybám
Demonstrační cvičení 5 INP
Princip kódování, pojmy Tady potřebujeme informaci zabezpečit, utajit apod.
zpráva 0 1 0...
000 111 000 kodér
dekodér Kódová slova
010
• zdrojová abeceda (abeceda zprávy) = {0, 1} • kódová abeceda (abeceda kódových slov) = {0, 1} • slovo nad danou abecedou – 0, 1 (ve zdrojové) – 000, 111 (v kódové); pozn. 001, 010, 011, 100, 101, 110 nejsou kódová slova
• kódovací předpis (např. 0→000, 1→111 v kódu ztrojení bitů)
O kódování Obecně je kódování předpis, který každému prvku konečné množiny A přiřazuje právě jedno slovo z konečné množiny B. Stručněji, kódování je zobrazení K: A→B*. Pojem slova v množině B znamená konečnou (a neprázdnou posloupnost) prvků této množiny. Množinu všech kódových slov označujeme B*. Množina A se nazývá zdrojová abeceda a její prvky zdrojové znaky, množina B se nazývá kódová abeceda a její prvky kódové znaky. Nejdůležitější je případ binárního kódování, které má dva kódové znaky, B={0, 1}. Množinu všech kódových slov K(a) pro všechna a∈A nazýváme kód. Význam mají jen prostá kódování, tj. taková, kdy různým zdrojovým znakům odpovídají vždy různá kódová slova. Prefixem slova b1b2…bk se rozumí každé ze slov b1, b1b2, …, b1b2…bk. Kódování se nazývá prefixové, jestliže je prosté a žádné kódové slovo není prefixem jiného kódového slova. Prefixové kódování je vždy jednoznačně dekódovatelné: pokud známe zprávu K*(a1a2…am), potom v ní najdeme nejmenší počet znaků (zleva), které tvoří kódové slovo, a ty jsou kódem znaku a1. Dekódované znaky umažeme a zase hledáme nejmenší počet znaků tvořících kódové slovo, to je kód znaku a2, atd. Příklad: prefixový kód 01 neprefixový kód 01 001 011 100 110 1100 1111 Nejkratším n-znakovým kódováním zdrojové abecedy a1, a2, …, ar s pravděpodobnostmi výskytu p1, p2, …, pr se rozumí prefixové kódování této abecedy pomocí n znaků, které má nejmenší možnou průměrnou délku slova. Nejkratší kód lze zkonstruovat pomocí Huffmanova algoritmu.
Typy kódů (podle účelu) • Pro odstranění redundance – Př. Huffmanovo kódování – Př. aplikace: komprese obrazu (JPG=kosinová transformace + Huffmanovo kódování, ztrátová komprese; GIF – LZW bezeztrátová komprese)
• Pro zabezpečení proti chybě – parita, ztrojení bitu – Hammingův kód – cyklické kódy, CRC, a další
• Pro utajení - šifrování – princip: zpráva xor klíč = zakódovaná zpráva – DES (symetrické šifrování) – RSA (asymetrické šifrování)
Huffmanovo kódování (pro odstranění redundance) • Lze sestrojit nejkratší možný kód • Potřebujeme znát četnosti výskytu jednotlivých kódovaných symbolů – Uděláme statistickou analýzu, popř. odhadneme
• Huffmanův kód - prefixový • V INP – např. pro instrukce (krátké značky pro nejčastější instrukce, delší pro méně časté) Příklad: Pomocí Huffmanova kódování zakódujte znaky 0-9 vyskytující se s uvedenou četností: Znak: 0 1 2 3 4 5 6 7 8 9 Četnost: 0.2 0.25 0.15 0.08 0.07 0.06 0.05 0.05 0.05 0.04 Poznámka: bez použití Huffmanova kódování potřebujeme 4 bity na znak a to chceme vylepšit.
Algoritmus: (1) sestavíme ohodnocený strom • Spojujeme uzly s nejnižším ohodnocením • Každým spojením redukujeme počet uzlů o jeden • Takto postupujeme až k jedinému uzlu s ohodnocením 1 znak
četnost
0
0.2
1
0.25
2
0.15
3
0.08
4
0.07
5
0.06
6
0.05
7
0.05
8
0.05
9
0.04
0.43 1.00 0.57 0.32 0.17 0.13 0.23 0.10
0.09
Algoritmus: (2) uzly systematicky očíslujeme • 0 k horním hranám, 1 ke spodním hranám • Cestou od vrcholu ke znakům vytvoříme kód kód
znak
četnost
00
0
0.2
10
1
0.25
110
2
0.15
1110
3
0.08
0100
4
0.07
0101
5
0.06
0110
6
0.05
0111
7
0.05
11110
8
0.05
11111
9
0.04
0
0.43
0 0.57
0
1 0 1 0 1
1
0.321
0 0
0
0.17 0.13 0 0.23
1 1
1 0.10 0.09
1
Pokud je číslování systematické, je kód prefixový, tj začátek každé značky je unikátní.
1.00
Příklad: dekódujte posloupnosti kód
znak
četnost
00
0
0.2
10
1
0.25
110
2
0.15
1110
3
0.08
0100
4
0.07
0101
5
0.06
0110
6
0.05
0111
7
0.05
11110
8
0.05
11111
9
0.04
Dekódujte tuto posloupnost 20 bitů: 00 10 00 10 1110 0110 00 00 0 1 0 1 3 6 0 0 Jedná se o 8 znaků. Při použití běžného kódování by bylo třeba 8x4=32bitů! (úspora) Posloupnost 9999 představuje v tomto Huffmanově kódu 4x5=20 jedniček (bitů). Při použití běžného kódování by bylo třeba jen 4x4=16 bitů. Výskyt této posloupnosti je však málo pravděpodobný.
Vlastnosti kódu kód
znak Li
fi
00
0
2
0.2
10
1
2
0.25
110
2
3
0.15
1110
3
4
0.08
0100
4
4
0.07
0101
5
4
0.06
0110
6
4
0.05
0111
7
4
0.05
11110
8
5
0.05
11111
9
5
0.04
průměrná délka značky:
Lp = ΣLi/n = 3.7 (i=0…9) střední dynamická délka značky: Lstř = ΣLi*fi = 2*0.2+…+5*0.04 = 3.04 teoretická optimální délka značky: Lopt = -Σ fi* log2 fi = 3.01 Redundance kódu: R = (Lstř-Lopt)/Lstř = 0.98%
Pozn.: log2 x = log10 x / log10 2
Kódy pro zabezpečení a opravu Př. Na 8 bitech zprávy (256 inf. kombin.) nelze detekovat chybu.
Pokud chceme umět zjišťovat chyby a opravovat je, musíme přidat nějakou redundanci!! Tj., k informačním bitům zprávy vhodně doplníme nějaké bity kontrolní. Separabilní kód
- lze oddělit kontrolní a informační bity
• Na tomto cvičení: – parita (redundance 1 bit, počet zabezpečených kombinací je 128, na 8 bitech), – ztrojení bitu, – Hammingův kód.
• Cyklické kódy a další - viz speciální kurz na FIT
Def: Hammingova vzdálenost d • Nejmenší počet bitů, v nichž se dvojice kódových kombinací liší (počítáno přes všechny možné dvojice) kód
d bez zabezpečení
1 SED SEC SEC - DED DEC
2 3 4 5
S/D = simple/double E = error D/C = detection/correction
Příklad SED - sudá parita • d=2 • vzniká doplněním jednoho bitu ke značce tak, aby počet jedniček byl sudý • odhalí chybu v jednom bitu, ale nedokáže určit její pozici (tj. opravit) Příklad: 8b informačních, 1b kontrolní (zabezpečovací) 0110 1010 0 při chybě 0110 00100 => lichý počet 1 => chyba při chybě 0110 00110 => sudý počet 1 => hlásí, že je vše OK, nepozná chybu
Příklad SEC - ztrojení bitu • d=3 • vzniká ztrojením každého bitu: 0→000, 1→111 • při výskytu jedné chyby v trojici dokáže odvodit původní hodnotu z majority • Kódové kombinace: 000, 111 • Nekódové kombinace: 001, 010, 011, 100, 101, 110 • Opravy: (001, 010, 100)→0, (011, 101, 110) →1 Příklad: Zpráva: 0 1 1 0 1 Zakódováno: 000 111 111 000 111 Při chybě: 000 111 101 001 111 se správně opraví na 0 1 1 0 1 Při chybě: 000 100 111 000 111 se chybně opraví na 0 0 1 0 1, tj. nedokáže detekovat dvojchybu
Příklad SEC - Hammingův kód (HK) • d=3 • kódové slovo obsahuje navíc kontrolní bity, jejichž umístění je dáno pozicí (indexem i) bitu ve slově • pokud je i mocnina 2, je bit kontrolní (C) - jinak je to bit informační (I) • kontrolní bity jsou tvořeny pomocí funkce XOR z informačních bitů • minimální možná redundance pro SEC • Hammingův kód je separovatelný
HK (n, k) • • • • • • •
n – délka kódového slova (v bitech) k – počet informačních bitů m – počet kontrolních bitů n = 2m – 1 n=m+k HK(7, 4), HK(15, 11) apod. pro větší n je poměr k/n příznivější
HK(7,4) – Jak určit informační a kontrolní bity? i binárně
Generující matice
1
1
1
1
0
0
0
C4
1 1 0 0 1 1 0 1 0 1 0 1 0 1 I7 I6 I5 C4 I3 C2 C1
C2
7 6
i
5 4
3 2
1
C1
Pokud je i mocnina 2, je bit kontrolní (C) jinak je to bit informační (I)
Hammingův kód (7,4) - kodér I(0) I(1) I(2) I(3)
C(1) C(2) I(3) C(4) I(5) I(6) I(7)
1 1
1 1
Generující rovnice (pro výpočet kontrolních bitů):
C1 = I3 xor I5 xor I7 C2 = I3 xor I6 xor I7 C4 = I5 xor I6 xor I7 0 0
0
C4
1 1 0 0 1 1 0 1 0 1 0 1 0 1 I7 I6 I5 C4 I3 C2 C1
C2
7 6
i
5 4
3 2
1
C1
Příklad Zakódujte v HK(7,4): 1001 Kódové slovo: I7I6I5C4I3C2C1 I3 = 1, I5 = 0, I6 = 0, I7 = 1 C1 = I3 xor I5 xor I7 = 1 xor 0 xor 1 = 0 C2 = I3 xor I6 xor I7 = 1 xor 0 xor 1 = 0 C4 = I5 xor I6 xor I7 = 0 xor 0 xor 1 = 1 1001 → 1001100
Hammingův kód (7,4) – kodér ve VHDL library IEEE; use IEEE.std_logic_1164.all; use IEEE.numeric_std.all; entity encHK4to7 is port ( input: in STD_LOGIC_VECTOR (3 downto 0); output: out STD_LOGIC_VECTOR (7 downto 1) ); end encHK4to7;
-- i7 i6 i5 i3 -- i7 i6 i5 c4 i3 c2 c1
architecture encHK4to7 of encHK4to7 is begin output(1) <= input(0) xor input(1) xor input(3); -- c1 = i3 xor i5 xor i7 output(2) <= input(0) xor input(2) xor input(3); -- c2 = i3 xor i6 xor i7 output(3) <= input(0); -- i3 = i3 output(4) <= input(1) xor input(2) xor input(3); -- c4 = i5 xor i6 xor i7 output(5) <= input(1); -- i5 = i5 output(6) <= input(2); -- i6 = i6 output(7) <= input(3); -- i7 = i7 end encHK4to7;
HK (7,4) - dekodér a oprava chyby Možné poškození
I7 I6 I5 I3 → I7 I6 I5 C4 I3 C2 C1 → I’7 I’6 I’5 C’4 I’3 C’2 C’1 → I’’7 I’’6 I’’5 I’’3
S je syndrom určující pozici chyby ve slově: I’7 I’6 I’5 C’4 I’3 C’2 C’1
C1 xor C1 = C1 xor I3 xor I5 xor I7 C2 xor C2 = C2 xor I3 xor I6 xor I7 C4 xor C4 = C4 xor I5 xor I6 xor I7 S1 = C’1 xor I’3 xor I’5 xor I’7 S2 = C’2 xor I’3 xor I’6 xor I’7 S4 = C’4 xor I’5 xor I’6 xor I’7
S1 S2 S4
0 1 2 DC 3 4 5 6 7
Vše OK
I3’ xor I5’ xor I6’ xor I7’ xor
I3’’ I5’’ I6’’ I7’’
Příklad • Bylo zakódováno: 1001 → 1001100 • Dekódujte a opravte: (a) Přijaté slovo: 1001100 S1 = C’1 xor I’3 xor I’5 xor I’7= 0 xor 1 xor 0 xor 1 = 0 S2 = C’2 xor I’3 xor I’6 xor I’7= 0 xor 1 xor 0 xor 1 = 0 S4 = C’4 xor I’5 xor I’6 xor I’7= 1 xor 0 xor 0 xor 1 = 0 S = 000 => nedošlo k chybě
(b) Přijaté slovo: 1001000 S1 = C’1 xor I’3 xor I’5 xor I’7= 0 xor 0 xor 0 xor 1 = 1 S2 = C’2 xor I’3 xor I’6 xor I’7= 0 xor 0 xor 0 xor 1 = 1 S4 = C’4 xor I’5 xor I’6 xor I’7= 1 xor 0 xor 0 xor 1 = 0 S = 011 = 3 > došlo k chybě na pozici 3, po opravě 1001100
Co se stane při dvojchybě?
HK(7,4) dekodér ve VHDL entita DEC3TO8 library IEEE; use IEEE.std_logic_1164.all; entity dec3to8 is port ( addr: in STD_LOGIC_VECTOR (2 downto 0); err: out STD_LOGIC_VECTOR (7 downto 0) ); end dec3to8; architecture dec3to8 of dec3to8 is begin with addr select err <= "10000000" when "111", "01000000" when "110", "00100000" when "101", "00010000" when "100", "00001000" when "011", "00000100" when "010", "00000010" when "001", "00000001" when others; end dec3to8;
HK (7,4) dekodér - VHDL (1) library IEEE; use IEEE.std_logic_1164.all; entity decHK7to4 is port ( input: in STD_LOGIC_VECTOR (7 downto 1); -- vstupni data correct: out STD_LOGIC_VECTOR (3 downto 0) -- opraveny vystup ); end decHK7to4; architecture decHK7to4 of decHK7to4 is component dec3to8 port ( addr: in STD_LOGIC_VECTOR (2 downto 0); err: out STD_LOGIC_VECTOR (7 downto 0) ); end component; signal s : STD_LOGIC_VECTOR (2 downto 0); signal fromDC : STD_LOGIC_VECTOR (7 downto 0);
-- syndrom -- vystup dekoderu
HK (7,4) dekodér -VHDL (2) begin -- s1 = s(0) <= -- s2 = s(1) <= -- s4 = s(2) <=
c1 xor i3 xor i5 xor i7 input(1) xor input(3) xor input(5) xor input(7); c2 xor i3 xor i6 xor i7 input(2) xor input(3) xor input(6) xor input(7); c4 xor i5 xor i6 xor i7 input(4) xor input(5) xor input(6) xor input(7);
DEC: dec3to8 port map ( addr => s, -- syndrom pripojime na adresove vstupy dekoderu err => fromDC -- vystup dekoderu ); correct(0) correct(1) correct(2) correct(3)
<= <= <= <=
end decHK7to4;
fromDC(3) fromDC(5) fromDC(6) fromDC(7)
xor xor xor xor
input(3); input(5); input(6); input(7);
-----
oprav oprav oprav oprav
i3 i5 i6 i7
Rozšířený Hammingův kód (8,4) • Stejný jako (7,4), ale je přidán jeden paritní bit pro všech 7 bitů. • SEC – DED – lze detekovat dvojchyby • d=4
Rozšířený HK (8,4) - kodér 1 1
1 1
1 1
1
1
C0
1 1
1 1
0 0
0
0
C4
C2 1 1 0 0 1 1 0 0 C1 1 0 1 0 1 0 1 0 I7 I6 I5 C4 I3 C2 C1 C0
7 6
5 4
3 2
1
0
Definujeme kontrolní bit: C0 = C1 xor C2 xor I3 xor C4 xor I5 xor I6 xor I7
Rozšířený HK (8,4) - dekodér Definujeme: S0 = C’0 xor C’1 xor C’2 xor I’3 xor C’4 xor I’5 xor I’6 xor I’7 S1 S2 S4 vypočteme stejně jako v HK(7,4) Definujeme syndrom chyby: S1 = C’1 xor I’3 xor I’5 xor I’7 S = S1 or S2 or S4 S2 = C’2 xor I’3 xor I’6 xor I’7 (detekce nenuloveho syndromu) S4 = C’4 xor I’5 xor I’6 xor I’7
Chyby klasifikujeme podle tabulky: S
S0
Význam
0
0
Bez chyby
0
1
Neopravitelná chyba (porucha hlídače, vícenásobná chyba)
1
0
Neopravitelná 2-chyba, 4-chyba, atd.
1
1
Opravitelná 1-chyba
Kód zbytkových tříd (KZT) • Převedeme binární čísla do KZT a tam budeme provádět aritmetické operace. • Proč? Protože tyto operace lze v KZT implementovat velmi jednoduše – bez přenosů, tj. budou rychlejší než konvenční. • Operace: sčítání, odčítání a násobení • Nefunguje dělení (nejednoznačný výsledek), jednoduché porovnání • Nepolyadická soustava: soustava modulů (prvočísel) • ci = (ai op bi) mod mi
Zakódování čísel a aritmetické operace m1m2m3 2 3 5 0 0 0 1 1 1 0 2 2 1 0 3 0 1 4 1 2 0 0 0 1 1 1 2 0 2 3 1 0 4 0 1 0 1 2 1 0 0 2 1 1 3 0 2 4 1 0 0
No 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ……… 29 1 2 4 30 0 0 0 Opakuje se 30 = 2*3*5
1 0 3 +0 1 4 1 1 2
(3) (4)
ci = (ai + bi) mod mi
bez přenosu!
0 0 1 (6) ci = (ai - bi) mod mi -1 2 0 (-5) 1 1 1 0 1 4 (4) *1 2 0 (5) 0 2 0 1 0 0 (15)
/1 2 0 (5) ? ? ?
ci = (ai * bi) mod mi
ci ≠ (ai / bi) mod mi
m1m2m3 2 3 5 0 0 0 1 1 1 0 2 2 1 0 3 0 1 4 1 2 0 0 0 1 1 1 2 0 2 3 1 0 4 0 1 0 1 2 1 0 0 2 1 1 3 0 2 4 1 0 0
No 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ……… 29 1 2 4 30 0 0 0 Opakuje se 30 = 2*3*5
Obvodová realizace: sčítačka Řád 2 Řád 3
A
=1
Řád 2
Řád 5
+
Řád 2
C
Řád 3 Řád 5
Řád 3
B
Řád 5
A2 0 0 1 1
B2 C2 0 0 1 1 0 1 1 0
Řád 2: XOR C2 = A2 XOR B2
m1m2m3 2 3 5 0 0 0 1 1 1 0 2 2 1 0 3 0 1 4 1 2 0 0 0 1 1 1 2 0 2 3 1 0 4 0 1 0 1 2 1 0 0 2 1 1 3 0 2 4 1 0 0
No 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ……… 29 1 2 4 30 0 0 0 Opakuje se 30 = 2*3*5
Obvodová realizace: sčítačka (2) Řád 2 Řád 3 Řád 5 Řád 2 Řád 3 Řád 5
A3
B3
C3
0 0 0 1 1 1 2 2 2
0 1 2 0 1 2 0 1 2
0 1 2 1 2 0 2 0 1
A3 ab 00 00 00 01 01 01 10 10 10
B3 cd 00 01 10 00 01 10 00 01 10
C3 uv 00 01 10 01 10 00 10 00 01
A
Řád 2
+ C
Řád 3 Řád 5
B Řád 3: u = f1(a,b,c,d) v = f2(a,b,c,d) Řád 5: obdobně jako řád 3 -,* obdobně jako +
library IEEE; use IEEE.std_logic_1164.all; entity KZT is port ( -- rad 2 A1 : in std_logic; B1 : in std_logic; C1 : out std_logic; -- rad 3 A2 : in std_logic_vector(1 B2 : in std_logic_vector(1 C2 : out std_logic_vector(1 -- rad 5 A3 : in std_logic_vector(2 B3 : in std_logic_vector(2 C3 : out std_logic_vector(2 end KZT; architecture A1 of KZT is begin C1 <= A1 xor B1; C2(0) <= (not A2(1) and (not A2(1) and (A2(1) and not C2(1) <= (not A2(1) and (not A2(1) and (A2(1) and not -- zde bude implementace radu 5 end A1;
Sčítačka KZT(5,3,2) ve VHDL downto 0); downto 0); downto 0); downto 0); downto 0); downto 0));
not A2(0) A2(0) and A2(0) and not A2(0) A2(0) and A2(0) and
and not B2(1) not B2(1) and B2(1) and not and B2(1) and not B2(1) and not B2(1) and
and B2(0)) or not B2(0)) or B2(0)); not B2(0)) or B2(0)) or not B2(0));
ALU v kódu zbytkových tříd A bin2kzt
ALU KZT
C kzt2bin
B bin2kzt
Vyplatí se to?
selektor funkce (+,-,*)
Literatura • Drábek, V.: Výstavba počítačů, skriptum VUT v Brně, 1995.
