Okruh 12 - Minimální kódy

[michalmuzicek]

12. - Minimální kódy

[michalmuzicek]

tady si nejsem jist do jake hloubky to az saha, nikde sem primo nenasel definici minimalnich kodu a co vsechno pod ne spada. To co tam je momentalne napsany je moje pochopeni pro toto tema, idealne kdyz to nekdo zkritizuje

[johnymachine]

nepatri to asi sem podle popisu otazky, ale nekam by se melo jeste nacpat crc a hamming

[mpi77]

crc a hamming jsou bezpečnostní kódy, ne minimální. proto bych je zde neuváděl.

[johnymachine]

no nejsou v žádné otázce, jen si myslím, že by na ně mohla přijít řeč... (stejně jako na ad prevodniky)

[johnymachine]

doplnil bych ještě teorii kodovani

[johnymachine]

plus mozna kraft a mcmillen
https://cs.wikipedia.org/wiki/Kraftova_nerovnost

[michalmuzicek]

nepodařilo se mi najít nikde definici kódování, tak jsem tam dal vlastní

[johnymachine]

Nevim ohledne tech prikladu, je to kvuli strucnosti zjednoduse a nevim jestli to je dobre. Zrovna na tohle by se mohli hodne ptat...

Prikladam slidy z MT, autor byva u SZZ
P06.pdf

Není to taky dokonalé, spíse inspirace a jiny priklad zase

[nicki-krizek]

• Hammingovo kodovani: detekuje dve chyby, opravuje jednu - ano, ale pouze pokud je nejake konretni delky, co je tu pouzita. Existuji i Hammingova kodovani jinych delek a ty pak maji jine vlastnosti.
• V sesite z DIM jsem jeste nasel k zabezpecovacim kodum linearni kodovani - jsou tu takove ty generujici a kontrolni matice... Ale to je doufam nad ramec otazky.
• U CRC bych mozna uvedl, kolik dovedou detekovat chyb a pripadne jestli dokazou chyby i opravit.

[michalmuzicek]

• jn, tam to bylo mam pocit ze opravuje 1 pokud je (7,4) a detekuje 2 pokud je (8,4)
• nestras, to tam uz snad nebude
• ok, dopisu

[johnymachine]

Jsem z toho pořád takový zmatený, chtělo by to tam nějak poladit co je tedy kterým kódem a pro huffmana a aritmetické tam udělat ten příklad nějak pořádně a jednoduše. Obrázky jsou takové naflákané všechny kroky do sebe

[johnymachine]

Když tam bude koucký, tak by to možná chtělo trochu odbornější definice. Jako třeba, že kódování je v podstatě zobrazení...

Skrypta_Brno.pdf

Zde mi přišlo, že bylo pár zajímavých postřehů

[tomaskounovsky]

Ten příklad Huffmana je napsaný trochu krkolomně, ale je to správně - řetězec s vyšší pravděpodobností dostává vždycky 0 a řetězec s nižší pravděpodobností dostává 1.

Na tohle bych ještě rád upozornil, pamatuju si že na DIMu se to řešilo a Koucký nerad slyší cokoliv jiného (nechtěl bych být v kůži toho, kdo prohlásí že "pro řetězec s vyšší pravděpodobností bych dal 1 a důležitý je jenom udržet konzistentní postup").

[johnymachine]

@tomaskounovsky jak je to pokud znaky maji stejnou cestnost? Podle abecedy?

[tomaskounovsky]

Popravdě to v sešitě nemám, ale očekával bych že to tak bude.

[johnymachine]

v tom prikladu od Chudoby to tak neni pravě

[michalmuzicek]

osobně bych navrhnul abysme tyhle výpočty (hamming,huffman, ale i ostatni matiku) udělali v pondělí ve škole, a vypočítané příkaldy ofotili a dali sem

[johnymachine]

Příklad: znakový řetězec ABRAKADABRA

1. Zjistím jednotlivé četnosti: A (5x – 0,46), B (2x – 0,18), R (2x – 0,18), D (1x – 0,09), K (1x – 0,09)
2. Sestrojím tabulku četností:
   • Levý sloupec seřazeno dle četnosti, dále pak podle abecedy. (závislé na implementaci)
   • Posledním dvou nejméně četným znakům přiřadím 0 a 1. (pořadí opět závislé na implementaci)
   • Do dalšího sloupce přesunu vyhodnocené znaky jako jeden složený a zbytek jen opíšu.
   • Opět vše seřadím a kroky opakuji analogicky až do konce.
3. Výsledný kód je spojením dílčích kódů vzniklých během slučování. (čteno odzadu)
4. A(1), B(01), R(001), D(0000), K(0001)

Četnost	Kód	Četnost	Kód	Četnost	Kód	Četnost	Kód
A 0,46		A 0,46		A 0,46		DKRB 0,54	0
B 0,18		B 0,18		DKR 0,36	0	A 0,46	1
R 0,18		DK 0,18	0	B 0,18	1
D 0,09	0	R 0,18	1
K 0,09	1

Výsledný řetězec: ABRAKADABRA (11 znaků - 88 bitů) = 1 01 001 1 0001 1 0000 1 01 001 1 = 10100110001100001010011 (23 bitů)

Výsledek je distribuován spolu s tabulkou kódu, díky prefixovosti je pak možné řetězec jednoznačné rekonstruovat opětovným přepsáním zpět.

Kompresní poměr: (nový počet bitů) / (původní počet bitů) = 23 / 88 = 0,26 = 26%

Já bych to viděl takhle, nikde jsem to nenašel naspecifikované. Ale jak říká Tomáš, hlavně konzistentně.

[johnymachine]

Tímhle bych ty obrázky nahradil a obdobně by to bylo ideální udělat i to aritmeticke...

[johnymachine]

Příklad: znakový řetězec AAAAFFFFCHHH

Kódování:

1. Postupně čteme znaky na vstupu a ukládáme si počet jejich opakování.
2. Když se znak změní, zapíšeme na výstup hodnotu čítače a opakovaný znak.
3. Čítač resetujeme na jedničku a pokračujeme pro nový znak od opět od bodu jedna.

A	A	A	A	F	F	F	F	C	H	H	H
			4A				4F	1C			3H

Výsledek: AAAAFFFFCHHH (12 znaků) => 4A4F1C3H (8 znaků)

Kompresní poměr: (nová délka) / (stará délka) = 8 / 12 = 0.66 => 66%

Dekódování:
Postup dekódování je obdobný, čteme vstup a jakmile narazíme na číslo tak ho přepíšeme jako rozvinutý tvar opakujících se znaků za číslem.

Tento postup není specifický pro textové soubory, lze ho s úpravami aplikovat i pro binární reprezentaci.

V některých případech může dojít i ke zvětšení celkového objemu dat.

[nicki-krizek]

Koucky zavadel pojem standardni Huffmanova konstrukce. Ovsem z prikladu z DIM co man v sesite neodpovida, ze vyssi cetnost vzdy dostane 0. Seradili jsme si cetnosti sestupne a potom se to spojovalo. Spojeni vzdycky zustalo na te vyssi ze dvou urovni. Potom se horni vetvi priradila 0 a spodni 1. Ve vetsine pripadu to tedy odpobidalo tomu, ze vyssi cetnost mela prirazenou 0, ale byly i pripady, kdt to dopadlo opacne.

[michalmuzicek]

Já mám v sešitě u Standardizované Huff. konstrukce
Zpětný chod provádíme : Znak s vyšším PST (pravěpodobnowt) dostane 0, nižší 1

[johnymachine]

Myslím, že je to fuk :)

[tomaskounovsky]

Vynechal jsem to, že se to vztahuje ke zpětnému chodu, což mi přišlo jasný, protože nikde jinde nuly a jedničky nepřiřazujeme. A ve zpětném chodu se vždycky jedná o porovnání pravděpodobností dvou řetězců, kde řetězec s vyšší pravděpodobností vždy dostane 0.

EDIT: Wait, už to vidím. @tomaskrizek má pravdu, pravděpodobnosti ve zpětným chodu nemaj žádnej význam. Jedná se skutečně o horní větev, ne větev s vyšší pravděpodobností.

@johnymachine tohle řekni Kouckýmu do očí a máš u mě pětikilo :D

[johnymachine]

@tomaskounovsky Domluveno, ale ne že vycouváš! =)