UPP - Hammingova vzdálenost, typy kodu

up:: UPP x:: x

Resource

• skripta (p21)

---

Teorie

• Kód
  • Definice
    • Kód je způsob reprezentace dat pomocí znaků podle určitého pravidla. Např. binární kód (0 a 1) slouží k ukládání a přenosu dat.
  • Typy
    • prostý $\ge 1$ | zabezpečující $\ge 2$ | samoopravný $\ge 3$
  • Princip konstrukce
    • Zabezpečující: Přidáváme paritní bity, které označují sudou nebo lichou paritu (podle zvolené metody)
    • Samoopravný: Na pozice mocnin dvou (např. 1, 2, 4, 8, …) přidáváme paritní bity, které kontrolují různé kombinace ostatních bitů.
• Nadbytečnost
  • Proč nadbytečnost (redundance)?
    • Jsou to nadbytečné informace, které můžou zvýšit h-vzdálenost a zabezpečit tím data před chybami.
  • nadbytečnost v %,
    • ($\ge 2$): 8+1 (parita) = 1/9 = 11.11 %.
    • ($\ge 3$): 8+4 (1,2,4,8) = 4/12 = 33.33 %.
• Vzdálenost
  • Hamingeova - Počet bitů, ve kterých se liší dvě kódová slova.
  • Minimální - Hammingova vzdálenost mezi všemi dvojicemi kódových slov v daném kódu.
    • Udává schopnost kódu detekovat nebo opravovat chyby.
  • H-Váha - počet bitů, které mají hodnotu 1 v binárním řetězci

Princip

Vzdálenost

• 3b kód: A: (1,0,0) B: (1,1,1) a C: (1,0,1)
• Hammingova vzdálenost ⇒ d(A,B)=2 d(A,C)=1 d(B,C)=1
  • V čem se liší?
  • Postup
    • 1. Vypsat všechny kombinace
    • 2. Spočítat vzdálenost
      • počet rozdílných (1/0)
• minimální kódová vzdálenost (Hammingova) (váha kódu)
  • 3. nejmenší číslo v Hammingovoje seznamu ⇒ $d_{min}=$ 1
• Typy kódu
  • prostý ( $d_{min}\ge 1$ )
  • zabezpečující ( $d_{min}\ge 2$ ) ⇒ detekuje $(d_{min}-1)$ chyb
  • samoopravný ( $d_{min}\ge 3$ ) ⇒ detekuje $(d_{min}-1)÷2$ chyb

Prostoru

Zabezpečení

• Parita
  • Why: $d_{min}=1$ + parita ⇒ $d_{min}=2$
  • How:
    • výsledný počet jedniček (sudý/lichý)
    • na konec se přidá bit aby byl (sudy) počet 1
  • Např:
    • 
• SEC (single error correction)
  • ( každý paritní bit je vypočítán z některých datových bitů )
  • Why: $d_{min}=1$ + SEC ⇒ $d_{min}=3$
  • How:
  • Pozice parit
    • 1. označím pozice mocniny 2
    • 2. vložím tam paritní bit
    • 3. zbytek je datový
  • Hodnoty parit
    • vezmu x vynechám (1,3,5,…)
      • x = pozice parity
      • začínám na pozici 1
    • p1=3⇔5⇔.. ⇒ tabulka znaků
    • spočítám 1 na označených místech
      • sudý ⇒ 1
    • (opakuji u další parity)
      • skončím když už nemam datové bity
• SEC-DEC (SEC – Double Error Detecting)
  • Why: $d_{min}=1$ + SEC + parita ⇒ $d_{min}=4$
    • SEC kód rozšířený o bit celkové parity.

Oprava kódu

• todo
  • excel 
• Pozice parit
  • 1. označím pozice mocniny 2
  • 2. vložím tam paritní bit
  • 3. zbytek je datový
• Hodnoty parit
  • vezmu x vynechám (1,3,5,…)
    • x = pozice parity
    • začínám na pozici 1
  • p1=3⇔5⇔.. ⇒ tabulka znaků
  • spočítám 1 na označených místech
    • sudý ⇒ 1
  • (opakuji u další parity)
    • skončím když už nemam datové bity

Image

• paritní se nepočítaj, počítají

Příklad

10b slovo - max slov k uložení v typech

Q-Full

• Pro kódové slovo je vyhrazeno 10 bitů. Kolik kódových slov maximálně lze v tomto kódu zobrazit tak, aby:
  • a)se jednalo o kód
  • b)kód byl samoopravný
  • c)kód byl zabezpečující

• $2^{10}$ = prostý: bez ochrany, nic necháme 10
• $2^9$ = zabezpečený: přidáme paritu -1b -> 10-1=9
• $2^6$ = samoopravný: přidáme SEC (1,2,4,8)=4x -> 10-4=6
• ( $2^5$ = Sec-Dec: SEC+parita=5 10-5=5 )

11000 → kombinace, dmin

V 5ti místním kódu máš 2x bit s hodnotou 1 a 3x bit s hodnotou 0. Definuj kolik kódových objektů lze zakódovat?

• Kombinace: $\genfrac{}{}{0ex}{}{Slots}{Active}$ = $(\genfrac{}{}{0ex}{}{5}{2}$) = 10

  • 11000 – 01100 – 00110 – ...

Jaká bude minimální Hammingova vzdálenost těchto kódů, o jaký typ kódu se jedná (zabezpečovací, samoopravný)?

• $d_{min}=2$ ⇒ zabezpečovací
  • protože minimální změna mezi dvěma slovy je změna dvou bitů (11000 ↔ 10100)

-

• Kódování dat (reprezentace)
  • dat: čísel, textů, barev, …
  • Kód
    • Kód je proces, které převádí data z jednoho formátu do jiného.
      • {objekty} → {kódová slova}
        • "A" => 101101
      • ( k odkodování je třeba znát kod kterým byl objekt zakodován)

Fixed?

10b slovo - max slov k uložení v typech wrong

Q-Full

• Pro kódové slovo je vyhrazeno 10 bitů. Kolik kódových slov maximálně lze v tomto kódu zobrazit tak, aby:
  • a)se jednalo o kód
  • b)kód byl samoopravný
  • c)kód byl zabezpečující

• $2^{10}$ = prostý: bez ochrany, nic necháme 10
• $2^9$ = zabezpečený: přidáme paritu -1b -> 10-1=9
• $2^6$ = samoopravný: přidáme SEC (10/2)-1=4 -> 10-4=6
• ( $2^5$ = Sec-Dec: SEC+parita=5 10-5=5 )

• nadbytečnost v %,
  • ($\ge 2$): 3/8 = 37,5 %
  • ($\ge 3$): 2/8 = 25 %
  • (dmin/1B)