Binární kódování čísel: Porovnání verzí

Z ZděchovNET
Skočit na navigaci Skočit na vyhledávání
Bez shrnutí editace
Bez shrnutí editace
 
(Není zobrazeno 31 mezilehlých verzí od stejného uživatele.)
Řádek 1: Řádek 1:
==Se statickou velikostí==
==Varianta A==


* Mají pevný rozsah daný svou bitovou délkou
===Bitová šířka 1===
* Snazší a efektivnější zpracování na počítači


{|
|
{| class="wikitable"
{| class="wikitable"
|+ Bitová šířka 1
! Číslice !! Kódování
|-
| 0 || 0
|-
| 1 || 1
|}
|
{| class="wikitable"
|+ Bitová šířka 2
! Číslice !! Kódování
|-
| 0 || 00
|-
| 1 || 01
|-
| 2 || 10
|-
| 3 || 11
|}
|
{| class="wikitable"
|+ Bitová šířka 3
! Číslice !! Kódování
|-
| 0 || 000
|-
| 1 || 001
|-
| 2 || 010
|-
| 3 || 011
|-
| 4 || 100
|-
| 5 || 101
|-
| 6 || 110
|-
| 7 || 111
|}
|
{| class="wikitable"
|+ Bitová šířka 4
! Číslice !! Kódování
|-
| 0 || 0000
|-
| 1 || 0001
|-
| 2 || 0010
|-
| 3 || 0011
|-
| 4 || 0100
|-
| 5 || 0101
|-
| 6 || 0110
|-
| 7 || 0111
|-
| 8 || 1000
|-
| 9 || 1001
|-
| 10 || 1010
|-
| 11 || 1011
|-
| 12 || 1100
|-
| 13 || 1101
|-
| 14 || 1110
|-
| 15 || 1111
|}
|}

==S dynamickou velikostí==

'''Požadavky:'''

* Malé režijní informace, vysoká efektivita uložení dat
* Výpočetní náročnost
* Schopnost efektivně kódovat krátké bitové sekvence (i jednobitové)
* Schopnost efektivně kódovat dlouhé bitové sekvence (až nekonečné)

Jedním ze základních kritérií pro výběr vhodného kódování je právě schopnost kódovat dynamická čísla s režijními informacemi menšími než 0,5 pro celou škálu hodnot. Obecně vzato kódování, která mají nízkou efektivitu pro malé hodnoty pak mají vyšší efektivitu pro velké a naopak. Závislost poměru režijní informace u jednoduchých kódování má lineární charakter a naklonění této přímky pak zálež na režii kódu pro počáteční hodnotu nul. U kódování s exponenciálním růstem některé složky či u kódování s využitím rekurze pak s růstem hodnot efektivita kódování roste s růstem hodnoty.


===Se značkou pro pokračování===

Vychází z kódování s pevnou šířkou, ale navíc určuje jednu hodnotu (zde nejvyšší číslo) jako ukončovací značku. Ve výsledku je tedy vždy obsažena na konci minimálně ukončovací značka.

* Mohou růst do nekončena
* Jejich generování i zpětná analýza je náročnější na výpočetní operace

{|
|
{| class="wikitable"
|+ Bitová šířka 1
! Číslice !! Kódování
! Číslice !! Kódování
|-
|-
Řádek 22: Řádek 128:
| 7 || 11111110
| 7 || 11111110
|-
|-
| 7 || 111111110
| 8 || 111111110
|-
| 9 || 1111111110
|-
| 10 || 11111111110
|-
| 11 || 111111111110
|-
| 12 || 1111111111110
|-
| 13 || 11111111111110
|-
| 14 || 111111111111110
|-
| 15 || 1111111111111110
|-
| ... || ...
|}
|
{| class="wikitable"
|+ Bitová šířka 2
! Číslice !! Kódování !! Režie
|-
| 0 || 00 || 0,5
|-
| 1 || 01 || 0,5
|-
| 2 || 10 || 0
|-
| 3 || 11 00 || 0,5
|-
| 4 || 11 01 || 0,25
|-
| 5 || 11 10 || 0,25
|-
| 6 || 11 11 00 || 0,5
|-
| 7 || 11 11 01 || 0,5
|-
| 8 || 11 11 10 || 0,33
|-
| 9 || 11 11 11 00 || 0,5
|-
| 10 || 11 11 11 01 || 0,5
|-
| 11 || 11 11 11 10 || 0,5
|-
| 12 || 11 11 11 11 00 || 0,6
|-
| 13 || 11 11 11 11 01 || 0,6
|-
| 14 || 11 11 11 11 10 || 0,6
|-
| 15 || 11 11 11 11 11 00 || 0,66
|-
| ... || ...
|}
|
{| class="wikitable"
|+ Bitová šířka 3
! Číslice !! Kódování !! Režie
|-
| 0 || 000 || 0,66
|-
| 1 || 001 || 0,66
|-
| 2 || 010 || 0,33
|-
| 3 || 011 || 0,33
|-
| 4 || 100 || 0
|-
| 5 || 101 || 0
|-
| 6 || 110 || 0
|-
| 7 || 111 000 || 0,5
|-
| 8 || 111 001 || 0,33
|-
| 9 || 111 010 || 0,33
|-
| 10 || 111 010 || 0,33
|-
| 11 || 111 011 || 0,33
|-
| 12 || 111 100 || 0,33
|-
| 13 || 111 101 || 0,33
|-
| 14 || 111 110 || 0,33
|-
| 15 || 111 111 000 || 0,55
|-
| ... || ...
|}
|
{| class="wikitable"
|+ Rostoucí šířka
! Číslice !! Kódování !! Režie
|-
| 0 || 0 || 0
|-
| 1 || 1 00 || 0,66
|-
| 2 || 1 01 || 0,33
|-
| 3 || 1 10 || 0,33
|-
| 4 || 1 11 000 || 0,5
|-
| 5 || 1 11 001 || 0,5
|-
| 6 || 1 11 010 || 0,5
|-
| 7 || 1 11 011 || 0,5
|-
| 8 || 1 11 100 || 0,33
|-
| 9 || 1 11 101 || 0,33
|-
| 10 || 1 11 110 || 0,33
|-
| 11 || 1 11 111 0000 || 0,6
|-
| 12 || 1 11 111 0001 || 0,6
|-
| 13 || 1 11 111 0010 || 0,6
|-
| 14 || 1 11 111 0011 || 0,6
|-
| 15 || 1 11 111 0100 || 0,6
|-
| ... || ...
|}
|}
|}


===Bitová šířka 2===
===Se značkou pro ukončení===


{|
|
{| class="wikitable"
|+ Bitová šířka 1
! Číslice !! Kódování !! Režie
|-
| 0 || 1 || 0
|-
| 1 || 01 || 0,5
|-
| 2 || 001 || 0,33
|-
| 3 || 0001 || 0,5
|-
| 4 || 00001 || 0,4
|-
| 5 || 000001 || 0,5
|-
| 6 || 0000001 || 0,57
|-
| 7 || 00000001 || 0,71
|-
| 8 || 000000001 || 0,55
|-
| 9 || 0000000001 || 0,6
|-
| 10 || 00000000001 || 0,63
|-
| 11 || 000000000001 || 0,66
|-
| 12 || 0000000000001 || 0,69
|-
| 13 || 00000000000001 || 0,71
|-
| 14 || 000000000000001 || 0,73
|-
| 15 || 0000000000000001 || 0,76
|-
| ... || ...
|}
|
{| class="wikitable"
|+ Bitová šířka 2
! Číslice !! Kódování !! Režie
|-
| 0 || 11 || 0,5
|-
| 1 || 00 11 || 0,75
|-
| 2 || 01 11 || 0,5
|-
| 3 || 10 11 || 0,5
|-
| 4 || 00 00 11 || 0,5
|-
| 5 || 00 01 11 || 0,5
|-
| 6 || 00 10 11 || 0,5
|-
| 7 || 01 00 11 || 0,5
|-
| 8 || 01 01 11 || 0,33
|-
| 9 || 01 10 11 || 0,33
|-
| 10 || 10 00 11 || 0,33
|-
| 11 || 10 01 11 || 0,33
|-
| 12 || 10 10 11 || 0,33
|-
| 13 || 00 00 00 11 || 0,5
|-
| 14 || 00 00 01 11 || 0,5
|-
| 15 || 00 00 10 11 || 0,5
|-
| ... || ...
|}
|
{| class="wikitable"
|+ Bitová šířka 3
! Číslice !! Kódování !! Režie
|-
| 0 || 111 || 0,66
|-
| 1 || 000 111 || 0,83
|-
| 2 || 001 111 || 0,66
|-
| 3 || 010 111 || 0,66
|-
| 4 || 011 111 || 0,5
|-
| 5 || 100 111 || 0,5
|-
| 6 || 101 111 || 0,5
|-
| 7 || 110 111 || 0,5
|-
| 8 || 000 000 111 || 0,55
|-
| 9 || 000 001 111 || 0,55
|-
| 10 || 000 010 111 || 0,55
|-
| 11 || 000 011 111 || 0,55
|-
| 12 || 000 100 111 || 0,55
|-
| 13 || 000 101 111 || 0,55
|-
| 14 || 000 110 111 || 0,55
|-
| 15 || 000 000 000 111 || 0,66
|-
| ... || ...
|}
|
{| class="wikitable"
|+ Rostoucí šířka
! Číslice !! Kódování !! Režie
|-
| 0 || 1 || 0
|-
| 1 || 0 11 || 0,66
|-
| 2 || 0 00 111 || 0,66
|-
| 3 || 0 01 111 || 0,66
|-
| 4 || 0 00 000 1111 || 0,7
|-
| 5 || 0 00 001 1111 || 0,7
|-
| 6 || 0 00 010 1111 || 0,7
|-
| 7 || 0 00 011 1111 || 0,7
|-
| 8 || 0 00 100 1111 || 0,6
|-
| 9 || 0 00 101 1111 || 0,6
|-
| 10 || 0 00 110 1111 || 0,6
|-
| 11 || 0 01 000 1111 || 0,6
|-
| 12 || 0 01 001 1111 || 0,6
|-
| 13 || 0 01 010 1111 || 0,6
|-
| 14 || 0 01 011 1111 || 0,6
|-
| 15 || 0 01 100 1111 || 0,6
|-
| ... || ...
|}
|}


===S ukončovací sekvencí bitů===

Je určena speciální sekvence bitů, která označuje konec čísla. Bity od začátku po tento konec jsou pak kódovány tak, aby se v nich daná sekvence nevyskytovala.

* Náročné na kódování a dekódování

{|
|
{| class="wikitable"
{| class="wikitable"
|+ Ukončovací sekvence 1
! Číslice !! Kódování
! Číslice !! Kódování !! Režie
|-
|-
| 0 || 00
| 0 || 1 || 0
|-
|-
| 1 || 01
| 1 || 01 || 0,5
|-
|-
| 2 || 10
| 2 || 001 || 0,33
|-
|-
| 3 || 11 00
| 3 || 0001 || 0,5
|-
|-
| 4 || 11 01
| 4 || 00001 || 0,4
|-
|-
| 5 || 11 10
| 5 || 000001 || 0,5
|-
|-
| 6 || 11 11 00
| 6 || 0000001 || 0,57
|-
|-
| 7 || 11 11 01
| 7 || 00000001 || 0,71
|-
|-
| 7 || 11 11 10
| 8 || 000000001 || 0,55
|-
| 9 || 0000000001 || 0,6
|-
| 10 || 00000000001 || 0,63
|-
| 11 || 000000000001 || 0,66
|-
| 12 || 0000000000001 || 0,69
|-
| 13 || 00000000000001 || 0,71
|-
| 14 || 000000000000001 || 0,73
|-
| 15 || 0000000000000001 || 0,76
|-
| ... || ...
|}
|
{| class="wikitable"
|+ Ukončovací sekvence 11
! Číslice !! Kódování !! Režie
|-
| 0 || 11 || 0,5
|-
| 1 || 011 || 0,66
|-
| 2 || 0011 || 0,5
|-
| 3 || 1011 || 0,5
|-
| 4 || 00011 || 0,4
|-
| 5 || 01011 || 0,4
|-
| 6 || 10011 || 0,4
|-
| 7 || 000011 || 0,5
|-
| 8 || 001011 || 0,3
|-
| 9 || 010011 || 0,3
|-
| 10 || 100011 || 0,3
|-
| 11 || 101011 || 0,3
|-
| 12 || 0000011 || 0,42
|-
| 13 || 0001011 || 0,42
|-
| 14 || 0010011 || 0,42
|-
| 15 || 0100011 || 0,42
|-
| ... || ...
|}
|
{| class="wikitable"
|+ Ukončovací sekvence 111
! Číslice !! Kódování !! Režie
|-
| 0 || 111 || 0,66
|-
| 1 || 0111 || 0,75
|-
| 2 || 00111 || 0,6
|-
| 3 || 10111 || 0,6
|-
| 4 || 000111 || 0,5
|-
| 5 || 010111 || 0,5
|-
| 6 || 100111 || 0,5
|-
| 7 || 110111 || 0,5
|-
| 8 || 0000111 || 0,43
|-
| 9 || 0010111 || 0,43
|-
| 10 || 0100111 || 0,43
|-
| 11 || 0110111 || 0,43
|-
| 12 || 1000111 || 043
|-
| 13 || 1010111 || 0,43
|-
| 14 || 1100111 || 0,43
|-
| 15 || 00000111 || 0,5
|-
| ... || ...
|}
|}
|}


==Složené tvary==
===Bitová šířka 3===


===Délka a hodnota===


{| class="wikitable"
{| class="wikitable"
| Délka || Hodnota
! Číslice !! Kódování
|}

===Unární délkou===

{|
|
{| class="wikitable"
|+ Statická délka 0 + n
! Číslice !! Kódování !! Režie
|-
|-
| 0 || 000
| 0 || 0 || 0
|-
|-
| 1 || 001
| 1 || 10 0 || 0,66
|-
|-
| 2 || 010
| 2 || 10 1 || 0,33
|-
|-
| 3 || 011
| 3 || 110 00 || 0,6
|-
|-
| 4 || 100
| 4 || 110 01 || 0,4
|-
|-
| 5 || 101
| 5 || 110 10 || 0,4
|-
|-
| 6 || 110
| 6 || 110 11 || 0,4
|-
|-
| 7 || 111 000
| 7 || 1110 000 || 0,57
|-
|-
| 8 || 111 001
| 8 || 1110 001 || 0,57
|-
| 9 || 1110 010 || 0,57
|-
| 10 || 1110 011 || 0,57
|-
| 11 || 1110 100 || 0,57
|-
| 12 || 1110 101 || 0,57
|-
| 13 || 1110 110 || 0,57
|-
| 14 || 1110 111 || 0,57
|-
| 15 || 11110 0000 || 0,55
|-
| ... || ...
|}
|}
|
{| class="wikitable"
|+ Statická délka 1 + n
! Číslice !! Kódování !! Režie
|-
| 0 || 0 0 || 0,5
|-
| 1 || 0 1 || 0,5
|-
| 2 || 10 00 || 0,5
|-
| 3 || 10 01 || 0,5
|-
| 4 || 10 10 || 0,25
|-
| 5 || 10 11 || 0,25
|-
| 6 || 110 000 || 0,5
|-
| 7 || 110 001 || 0,5
|-
| 8 || 110 010 || 0,33
|-
| 9 || 110 011 || 0,33
|-
| 10 || 110 100 || 0,33
|-
| 11 || 110 101 || 0,33
|-
| 12 || 110 110 || 0,33
|-
| 13 || 110 111 || 0,33
|-
| 14 || 1110 0000 || 0,5
|-
| 15 || 1110 0001 || 0,5
|-
| ... || ...
|}
|
{| class="wikitable"
|+ Statická délka 2 + n
! Číslice !! Kódování !! Režie
|-
| 0 || 0 00 || 0,66
|-
| 1 || 0 01 || 0,66
|-
| 2 || 0 10 || 0,33
|-
| 3 || 0 11 || 0,33
|-
| 4 || 10 000 || 0,4
|-
| 5 || 10 001 || 0,4
|-
| 6 || 10 010 || 0,4
|-
| 7 || 10 011 || 0,4
|-
| 8 || 10 100 || 0,2
|-
| 9 || 10 101 || 0,2
|-
| 10 || 10 110 || 0,2
|-
| 11 || 10 111 || 0,2
|-
| 12 || 110 0000 || 0,42
|-
| 13 || 110 0001 || 0,42
|-
| 14 || 110 0010 || 0,42
|-
| 15 || 110 0011 || 0,42
|-
| ... || ...
|}
|
{| class="wikitable"
|+ Statická délka exponenciální
! Číslice !! Kódování !! Režie
|-
| 0 || 0 || 0
|-
| 1 || 10 0 || 0,66
|-
| 2 || 10 1 || 0,33
|-
| 3 || 110 00 || 0,6
|-
| 4 || 110 01 || 0,4
|-
| 5 || 110 10 || 0,4
|-
| 6 || 110 11 || 0,4
|-
| 7 || 1110 0000 || 0,62
|-
| 8 || 1110 0001 || 0,5
|-
| 9 || 1110 0010 || 0,5
|-
| 10 || 1110 0011 || 0,5
|-
| 11 || 1110 0100 || 0,5
|-
| 12 || 1110 0101 || 0,5
|-
| 13 || 1110 0110 || 0,5
|-
| 14 || 1110 0111 || 0,5
|-
| 15 || 1110 1000 || 0,5
|-
| ... || ...
|}
|
{| class="wikitable"
|+ Statická délka exponenciální od šířky 1
! Číslice !! Kódování !! Režie
|-
| 0 || 0 0 || 0,5
|-
| 1 || 0 1 || 0,5
|-
| 2 || 10 00 || 0,5
|-
| 3 || 10 01 || 0,5
|-
| 4 || 10 10 || 0,25
|-
| 5 || 10 11 || 0,25
|-
| 6 || 110 0000 || 0,57
|-
| 7 || 110 0001 || 0,57
|-
| 8 || 110 0010 || 0,43
|-
| 9 || 110 0011 || 0,43
|-
| 10 || 110 0100 || 0,43
|-
| 11 || 110 0101 || 0,43
|-
| 12 || 110 0110 || 0,43
|-
| 13 || 110 0111 || 0,43
|-
| 14 || 110 1000 || 0,43
|-
| 15 || 110 1001 || 0,43
|-
| ... || ...
|}

|}


{| class="wikitable"
|+ Statická délka 1 + n s absolutní hodnotou
! Číslice !! Kódování !! Režie
|-
| 0 || 0 0 || 0,5
|-
| 1 || 0 1 || 0,5
|-
| 2 || 10 10 || 0,5
|-
| 3 || 10 11 || 0,5
|-
| 4 || 110 100 || 0,5
|-
| 5 || 110 101 || 0,5
|-
| 6 || 110 110 || 0,5
|-
| 7 || 110 111 || 0,5
|-
| 8 || 1110 1000 || 0,5
|-
| 9 || 1110 1001 || 0,5
|-
| 10 || 1110 1010 || 0,5
|-
| 11 || 1110 1011 || 0,5
|-
| 12 || 1110 1100 || 0,5
|-
| 13 || 1110 1101 || 0,5
|-
| 14 || 1110 1110 || 0,5
|-
| 15 || 1110 1111 || 0,5
|-
| ... || ...
|}


===S rekurzivně kódovanou délkou===

{|
|
{| class="wikitable"
|+ Zarovnání 2 bity
! Číslice !! Kódování !! Režie
|-
| 0 || 0 0 || 0,5
|-
| 1 || 0 1 || 0,5
|-
| 2 || 10 00 || 0,5
|-
| 3 || 10 01 || 0,5
|-
| 4 || 10 10 || 0,25
|-
| 5 || 10 11 || 0,25
|-
| 6 || 11 00 00 00 || 0,625
|-
| 7 || 11 00 00 01 || 0,625
|-
| 8 || 11 00 00 10 || 0,5
|-
| 9 || 11 00 00 11 || 0,5
|-
| 10 || 11 00 01 00 || 0,5
|-
| 11 || 11 00 01 01 || 0,5
|-
| 12 || 11 00 01 10 || 0,5
|-
| 13 || 11 00 01 11 || 0,5
|-
| 14 || 11 00 10 00 || 0,5
|-
| 15 || 11 00 10 01 || 0,5
|-
| ... || ...
|}
|
{| class="wikitable"
|+ Zarovnání 2 bity
menší růst
! Číslice !! Kódování !! Režie
|-
| 0 || 0 0 || 0,5
|-
| 1 || 0 1 || 0,5
|-
| 2 || 10 00 || 0,5
|-
| 3 || 10 01 || 0,5
|-
| 4 || 10 10 || 0,25
|-
| 5 || 10 11 || 0,25
|-
| 6 || 11 00 00 || 0,5
|-
| 7 || 11 00 01 || 0,5
|-
| 8 || 11 00 10 || 0,33
|-
| 9 || 11 00 11 || 0,33
|-
| 10 || 11 01 00 || 0,33
|-
| 11 || 11 01 01 || 0,33
|-
| 12 || 11 01 10 || 0,33
|-
| 13 || 11 01 11 || 0,33
|-
| 14 || 11 10 00 00 || 0,5
|-
| 15 || 11 10 00 01 || 0,5
|-
| ... || ...
|}
|}

Pro efektivnější zpracování na běžných počítačích je vhodné použít kódování s rekurzivní délkou zarovnané na 8 bitů. Následující tabulka ukazuje příklady kódování. '''x''' značí samotnou kódovanou hodnotu. '''d''' značí rekurzivně kódovanou délku.
* Některé hodnoty lze vyjádřit více kódy. Např. hodnota 0 lze zapsat jako '''00''' nebo jako '''FF 01 00''' nebo '''FF 02 00 00''' atd.
* V tomto kódování lze vyjádřit také blok dat o délce nula v nejkratším tvaru pomocí '''FF 00'''.
* Pomocí tohoto kódování a principu rekurze délky lze vyjádřit nekonečně dlouhé bloky.
* Stejný mechanizmus lze použít pro zarovnání na různé délky jako 2, 4, 8, 16, atd.

{| class="wikitable"
|+ Zarovnání 8 bitů (bajt)
! Číslice !! Kódování !! Bitová režie
|-
| 0 až 2<sup>7</sup>-1|| 0xxxxxxx || 0,125
|-
| 2<sup>7</sup> až 2<sup>14</sup>-1 || 10xxxxxx xxxxxxxx || 0,125
|-
| 2<sup>14</sup> až 2<sup>21</sup>-1 || 110xxxxx xxxxxxxx xxxxxxxx || 0,125
|-
| 2<sup>21</sup> až 2<sup>28</sup>-1 || 1110xxxx xxxxxxxx xxxxxxxx xxxxxxxx || 0,125
|-
| 2<sup>28</sup> až 2<sup>35</sup>-1 || 11110xxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx || 0,125
|-
| 2<sup>35</sup> až 2<sup>42</sup>-1 || 111110xx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx || 0,125
|-
| 2<sup>42</sup> až 2<sup>49</sup>-1 || 1111110x xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx || 0,125
|-
| 2<sup>49</sup> až 2<sup>56</sup>-1 || 11111110 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx || 0,125
|-
| 0 až 2<sup>d*8</sup>-1 || 11111111 dddddddd ... ||
|-
| nulová délka || 11111111 00000000 || 1
|-
| 0 až 2<sup>8</sup>-1 || 11111111 00000001 xxxxxxxx || 0,66
|-
| 2<sup>8</sup> až 2<sup>16</sup>-1 || 11111111 00000010 xxxxxxxx xxxxxxxx || 0,5
|-
| 2<sup>16</sup> až 2<sup>24</sup>-1 || 11111111 00000010 xxxxxxxx xxxxxxxx xxxxxxxx || 0,4
|-
| 2<sup>24</sup> až 2<sup>32</sup>-1 || 11111111 00000011 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx || 0,3
|-
| 2<sup>32</sup> až 2<sup>40</sup>-1 || 11111111 00000100 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx || 0,28
|-
| 2<sup>40</sup> až 2<sup>48</sup>-1 || 11111111 00000101 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx || 0,25
|-
| 2<sup>48</sup> až 2<sup>56</sup>-1 || 11111111 00000110 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx || 0,22
|-
| 2<sup>56</sup> až 2<sup>64</sup>-1 || 11111111 00000111 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx || 0,2
|-
|colspan="3"|...
|-
| 0 až 2<sup>d*8</sup>-1 || 11111111 dddddddd dddddddd ... ||
|-
| nulová délka || 11111111 10000000 00000000 || 1
|-
| 0 až 2<sup>8</sup>-1 || 11111111 10000000 00000001 xxxxxxxx || 0,75
|-
| 2<sup>8</sup> až 2<sup>16</sup>-1 || 11111111 10000000 00000010 xxxxxxxx xxxxxxxx || 0,6
|-
| 2<sup>8</sup> až 2<sup>16</sup>-1 || 11111111 10000000 00000011 xxxxxxxx xxxxxxxx xxxxxxxx || 0,5
|}

[[Kategorie:Programování]]

Aktuální verze z 29. 9. 2015, 07:09

Se statickou velikostí

  • Mají pevný rozsah daný svou bitovou délkou
  • Snazší a efektivnější zpracování na počítači
Bitová šířka 1
Číslice Kódování
0 0
1 1
Bitová šířka 2
Číslice Kódování
0 00
1 01
2 10
3 11
Bitová šířka 3
Číslice Kódování
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111
Bitová šířka 4
Číslice Kódování
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
10 1010
11 1011
12 1100
13 1101
14 1110
15 1111

S dynamickou velikostí

Požadavky:

  • Malé režijní informace, vysoká efektivita uložení dat
  • Výpočetní náročnost
  • Schopnost efektivně kódovat krátké bitové sekvence (i jednobitové)
  • Schopnost efektivně kódovat dlouhé bitové sekvence (až nekonečné)

Jedním ze základních kritérií pro výběr vhodného kódování je právě schopnost kódovat dynamická čísla s režijními informacemi menšími než 0,5 pro celou škálu hodnot. Obecně vzato kódování, která mají nízkou efektivitu pro malé hodnoty pak mají vyšší efektivitu pro velké a naopak. Závislost poměru režijní informace u jednoduchých kódování má lineární charakter a naklonění této přímky pak zálež na režii kódu pro počáteční hodnotu nul. U kódování s exponenciálním růstem některé složky či u kódování s využitím rekurze pak s růstem hodnot efektivita kódování roste s růstem hodnoty.


Se značkou pro pokračování

Vychází z kódování s pevnou šířkou, ale navíc určuje jednu hodnotu (zde nejvyšší číslo) jako ukončovací značku. Ve výsledku je tedy vždy obsažena na konci minimálně ukončovací značka.

  • Mohou růst do nekončena
  • Jejich generování i zpětná analýza je náročnější na výpočetní operace
Bitová šířka 1
Číslice Kódování
0 0
1 10
2 110
3 1110
4 11110
5 111110
6 1111110
7 11111110
8 111111110
9 1111111110
10 11111111110
11 111111111110
12 1111111111110
13 11111111111110
14 111111111111110
15 1111111111111110
... ...
Bitová šířka 2
Číslice Kódování Režie
0 00 0,5
1 01 0,5
2 10 0
3 11 00 0,5
4 11 01 0,25
5 11 10 0,25
6 11 11 00 0,5
7 11 11 01 0,5
8 11 11 10 0,33
9 11 11 11 00 0,5
10 11 11 11 01 0,5
11 11 11 11 10 0,5
12 11 11 11 11 00 0,6
13 11 11 11 11 01 0,6
14 11 11 11 11 10 0,6
15 11 11 11 11 11 00 0,66
... ...
Bitová šířka 3
Číslice Kódování Režie
0 000 0,66
1 001 0,66
2 010 0,33
3 011 0,33
4 100 0
5 101 0
6 110 0
7 111 000 0,5
8 111 001 0,33
9 111 010 0,33
10 111 010 0,33
11 111 011 0,33
12 111 100 0,33
13 111 101 0,33
14 111 110 0,33
15 111 111 000 0,55
... ...
Rostoucí šířka
Číslice Kódování Režie
0 0 0
1 1 00 0,66
2 1 01 0,33
3 1 10 0,33
4 1 11 000 0,5
5 1 11 001 0,5
6 1 11 010 0,5
7 1 11 011 0,5
8 1 11 100 0,33
9 1 11 101 0,33
10 1 11 110 0,33
11 1 11 111 0000 0,6
12 1 11 111 0001 0,6
13 1 11 111 0010 0,6
14 1 11 111 0011 0,6
15 1 11 111 0100 0,6
... ...

Se značkou pro ukončení

Bitová šířka 1
Číslice Kódování Režie
0 1 0
1 01 0,5
2 001 0,33
3 0001 0,5
4 00001 0,4
5 000001 0,5
6 0000001 0,57
7 00000001 0,71
8 000000001 0,55
9 0000000001 0,6
10 00000000001 0,63
11 000000000001 0,66
12 0000000000001 0,69
13 00000000000001 0,71
14 000000000000001 0,73
15 0000000000000001 0,76
... ...
Bitová šířka 2
Číslice Kódování Režie
0 11 0,5
1 00 11 0,75
2 01 11 0,5
3 10 11 0,5
4 00 00 11 0,5
5 00 01 11 0,5
6 00 10 11 0,5
7 01 00 11 0,5
8 01 01 11 0,33
9 01 10 11 0,33
10 10 00 11 0,33
11 10 01 11 0,33
12 10 10 11 0,33
13 00 00 00 11 0,5
14 00 00 01 11 0,5
15 00 00 10 11 0,5
... ...
Bitová šířka 3
Číslice Kódování Režie
0 111 0,66
1 000 111 0,83
2 001 111 0,66
3 010 111 0,66
4 011 111 0,5
5 100 111 0,5
6 101 111 0,5
7 110 111 0,5
8 000 000 111 0,55
9 000 001 111 0,55
10 000 010 111 0,55
11 000 011 111 0,55
12 000 100 111 0,55
13 000 101 111 0,55
14 000 110 111 0,55
15 000 000 000 111 0,66
... ...
Rostoucí šířka
Číslice Kódování Režie
0 1 0
1 0 11 0,66
2 0 00 111 0,66
3 0 01 111 0,66
4 0 00 000 1111 0,7
5 0 00 001 1111 0,7
6 0 00 010 1111 0,7
7 0 00 011 1111 0,7
8 0 00 100 1111 0,6
9 0 00 101 1111 0,6
10 0 00 110 1111 0,6
11 0 01 000 1111 0,6
12 0 01 001 1111 0,6
13 0 01 010 1111 0,6
14 0 01 011 1111 0,6
15 0 01 100 1111 0,6
... ...

S ukončovací sekvencí bitů

Je určena speciální sekvence bitů, která označuje konec čísla. Bity od začátku po tento konec jsou pak kódovány tak, aby se v nich daná sekvence nevyskytovala.

  • Náročné na kódování a dekódování
Ukončovací sekvence 1
Číslice Kódování Režie
0 1 0
1 01 0,5
2 001 0,33
3 0001 0,5
4 00001 0,4
5 000001 0,5
6 0000001 0,57
7 00000001 0,71
8 000000001 0,55
9 0000000001 0,6
10 00000000001 0,63
11 000000000001 0,66
12 0000000000001 0,69
13 00000000000001 0,71
14 000000000000001 0,73
15 0000000000000001 0,76
... ...
Ukončovací sekvence 11
Číslice Kódování Režie
0 11 0,5
1 011 0,66
2 0011 0,5
3 1011 0,5
4 00011 0,4
5 01011 0,4
6 10011 0,4
7 000011 0,5
8 001011 0,3
9 010011 0,3
10 100011 0,3
11 101011 0,3
12 0000011 0,42
13 0001011 0,42
14 0010011 0,42
15 0100011 0,42
... ...
Ukončovací sekvence 111
Číslice Kódování Režie
0 111 0,66
1 0111 0,75
2 00111 0,6
3 10111 0,6
4 000111 0,5
5 010111 0,5
6 100111 0,5
7 110111 0,5
8 0000111 0,43
9 0010111 0,43
10 0100111 0,43
11 0110111 0,43
12 1000111 043
13 1010111 0,43
14 1100111 0,43
15 00000111 0,5
... ...

Složené tvary

Délka a hodnota

Délka Hodnota

Unární délkou

Statická délka 0 + n
Číslice Kódování Režie
0 0 0
1 10 0 0,66
2 10 1 0,33
3 110 00 0,6
4 110 01 0,4
5 110 10 0,4
6 110 11 0,4
7 1110 000 0,57
8 1110 001 0,57
9 1110 010 0,57
10 1110 011 0,57
11 1110 100 0,57
12 1110 101 0,57
13 1110 110 0,57
14 1110 111 0,57
15 11110 0000 0,55
... ...
Statická délka 1 + n
Číslice Kódování Režie
0 0 0 0,5
1 0 1 0,5
2 10 00 0,5
3 10 01 0,5
4 10 10 0,25
5 10 11 0,25
6 110 000 0,5
7 110 001 0,5
8 110 010 0,33
9 110 011 0,33
10 110 100 0,33
11 110 101 0,33
12 110 110 0,33
13 110 111 0,33
14 1110 0000 0,5
15 1110 0001 0,5
... ...
Statická délka 2 + n
Číslice Kódování Režie
0 0 00 0,66
1 0 01 0,66
2 0 10 0,33
3 0 11 0,33
4 10 000 0,4
5 10 001 0,4
6 10 010 0,4
7 10 011 0,4
8 10 100 0,2
9 10 101 0,2
10 10 110 0,2
11 10 111 0,2
12 110 0000 0,42
13 110 0001 0,42
14 110 0010 0,42
15 110 0011 0,42
... ...
Statická délka exponenciální
Číslice Kódování Režie
0 0 0
1 10 0 0,66
2 10 1 0,33
3 110 00 0,6
4 110 01 0,4
5 110 10 0,4
6 110 11 0,4
7 1110 0000 0,62
8 1110 0001 0,5
9 1110 0010 0,5
10 1110 0011 0,5
11 1110 0100 0,5
12 1110 0101 0,5
13 1110 0110 0,5
14 1110 0111 0,5
15 1110 1000 0,5
... ...
Statická délka exponenciální od šířky 1
Číslice Kódování Režie
0 0 0 0,5
1 0 1 0,5
2 10 00 0,5
3 10 01 0,5
4 10 10 0,25
5 10 11 0,25
6 110 0000 0,57
7 110 0001 0,57
8 110 0010 0,43
9 110 0011 0,43
10 110 0100 0,43
11 110 0101 0,43
12 110 0110 0,43
13 110 0111 0,43
14 110 1000 0,43
15 110 1001 0,43
... ...


Statická délka 1 + n s absolutní hodnotou
Číslice Kódování Režie
0 0 0 0,5
1 0 1 0,5
2 10 10 0,5
3 10 11 0,5
4 110 100 0,5
5 110 101 0,5
6 110 110 0,5
7 110 111 0,5
8 1110 1000 0,5
9 1110 1001 0,5
10 1110 1010 0,5
11 1110 1011 0,5
12 1110 1100 0,5
13 1110 1101 0,5
14 1110 1110 0,5
15 1110 1111 0,5
... ...


S rekurzivně kódovanou délkou

Zarovnání 2 bity
Číslice Kódování Režie
0 0 0 0,5
1 0 1 0,5
2 10 00 0,5
3 10 01 0,5
4 10 10 0,25
5 10 11 0,25
6 11 00 00 00 0,625
7 11 00 00 01 0,625
8 11 00 00 10 0,5
9 11 00 00 11 0,5
10 11 00 01 00 0,5
11 11 00 01 01 0,5
12 11 00 01 10 0,5
13 11 00 01 11 0,5
14 11 00 10 00 0,5
15 11 00 10 01 0,5
... ...
Zarovnání 2 bity menší růst
Číslice Kódování Režie
0 0 0 0,5
1 0 1 0,5
2 10 00 0,5
3 10 01 0,5
4 10 10 0,25
5 10 11 0,25
6 11 00 00 0,5
7 11 00 01 0,5
8 11 00 10 0,33
9 11 00 11 0,33
10 11 01 00 0,33
11 11 01 01 0,33
12 11 01 10 0,33
13 11 01 11 0,33
14 11 10 00 00 0,5
15 11 10 00 01 0,5
... ...

Pro efektivnější zpracování na běžných počítačích je vhodné použít kódování s rekurzivní délkou zarovnané na 8 bitů. Následující tabulka ukazuje příklady kódování. x značí samotnou kódovanou hodnotu. d značí rekurzivně kódovanou délku.

  • Některé hodnoty lze vyjádřit více kódy. Např. hodnota 0 lze zapsat jako 00 nebo jako FF 01 00 nebo FF 02 00 00 atd.
  • V tomto kódování lze vyjádřit také blok dat o délce nula v nejkratším tvaru pomocí FF 00.
  • Pomocí tohoto kódování a principu rekurze délky lze vyjádřit nekonečně dlouhé bloky.
  • Stejný mechanizmus lze použít pro zarovnání na různé délky jako 2, 4, 8, 16, atd.
Zarovnání 8 bitů (bajt)
Číslice Kódování Bitová režie
0 až 27-1 0xxxxxxx 0,125
27 až 214-1 10xxxxxx xxxxxxxx 0,125
214 až 221-1 110xxxxx xxxxxxxx xxxxxxxx 0,125
221 až 228-1 1110xxxx xxxxxxxx xxxxxxxx xxxxxxxx 0,125
228 až 235-1 11110xxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 0,125
235 až 242-1 111110xx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 0,125
242 až 249-1 1111110x xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 0,125
249 až 256-1 11111110 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 0,125
0 až 2d*8-1 11111111 dddddddd ...
nulová délka 11111111 00000000 1
0 až 28-1 11111111 00000001 xxxxxxxx 0,66
28 až 216-1 11111111 00000010 xxxxxxxx xxxxxxxx 0,5
216 až 224-1 11111111 00000010 xxxxxxxx xxxxxxxx xxxxxxxx 0,4
224 až 232-1 11111111 00000011 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 0,3
232 až 240-1 11111111 00000100 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 0,28
240 až 248-1 11111111 00000101 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 0,25
248 až 256-1 11111111 00000110 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 0,22
256 až 264-1 11111111 00000111 xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 0,2
...
0 až 2d*8-1 11111111 dddddddd dddddddd ...
nulová délka 11111111 10000000 00000000 1
0 až 28-1 11111111 10000000 00000001 xxxxxxxx 0,75
28 až 216-1 11111111 10000000 00000010 xxxxxxxx xxxxxxxx 0,6
28 až 216-1 11111111 10000000 00000011 xxxxxxxx xxxxxxxx xxxxxxxx 0,5
Citováno z „https://wiki.zdechov.net/index.php?title=Binární_kódování_čísel&oldid=1565“