Blog

Vize dokonalého uložení čísla

Posted on Wednesday 23rd of October 2002 12:00:00 PM

Existuje jednoduchý způsob, jak uložit číslo nezávisle na velikosti slova

       Jako hlavní princip mého nového digitálního formátu XBFF slouží jistý systém ukládání čísel, známý většině programátorů z kódování znaků UTF8. Princip je tudíž jednoduchý a již dlouho známý.

       Základem celého systému je BIT. Bit je základní jednotka informace, která je zcela logická a nevyvratitelná. Běžně se 8 bitů seskupí do bajtu, což je v současné době nejpoužívanější základní jednotka počítačové informace. Jeden bajt přenáší hodnotu z intervalu <0..255>. Kdo však určil, že bitů bude zrovna 8? Proč ne 4? Nebo 16, či ještě více? Ačkoli se zdá být 8  bitů akorát, není možné vyloučit, že by se toto mohlo někdy změnit. Abstrahujeme-li od organizace bitů do bajtů, lze ukládat čísla jistým jednoduchým způsobem.

       Uvažujme jako základní interval přirozená čísla včetně 0. Uvažujme nyní nekonečný bitový proud, který nese číslo. Způsob je prostý – číslo je určeno počtem bitů jednoho druhu. Zvolme například bit 1 jako nositel informace a 0 jako terminální bit. Pak čísla vypadají takto…

0          0
1          10
2          110
3          1110
4          11110
…

       Lze vidět, že tento způsob, jakkoli je prostý, zbytečně plýtvá místem (možná vám to připomene něco z oblasti komprese). Domnívám se, že tento způsob je ale naprosto logický, zatím bez formálního důkazu. Možná je na čase, abych si zapsal předmět, kde se přednáší teorie informace. Možná tu totiž plácám něco, co je již dávno světu známé. Pro své účely jsem tento způsob ukládání označil jako BNatural datové šířky 0. Ačkoli zde na první pohled není vidět žádná souvislost (alespoň já jsem ji neviděl), jedná se skutečně o platné označení. Připomenu princip ukládání čísla BNatural v jeho základní šířce 7 v pohledu, který více osvětlí podobnost.

0xxxxxxx
10xxxxxx xxxxxxxx
110xxxxx xxxxxxxx xxxxxxxx
…

       Základní tvar je 0xxxxxxx, kde x představují datové bity určené pro uložení vlastní hodnoty. Další tvar je 10xxxxxx xxxxxxxx, přičemž k hodnotě určené bity x se přičítá 80h. Podstatné je v tomto případě rekurzivní rozšiřování, tedy 11111111 nnnnnnnn ((N+9)*7)x a přičítá se Sum{I in 1..<N+9>} (2^(7*I)). N představuje další číslo typu BNatural stejné šířky vyjádřené pomocí bitů “n”, které se mohou také rozšiřovat. Tento výpočet lze zobecnit na libovolnou datovou šířku a to takto:

DŠ – datová šířka
PB – počet bitů 1 shora v prvním slově délky (DŠ+1) bitů
RH – rozšiřující hodnota

- počet datových bitů: (DŠ*(PB+1+N))
- přičítaná hodnota: Sum{I in <1.. PB+1+N >} (2^(DŠ*I))

Pro PB =< DŠ není RH přítomna a její hodnota je 0. Když nyní zvolíme DŠ = 0, lze vidět, že pokud je první bit 1, rozšiřuje se číslo o další bit díky RH a hodnota se zvyšuje o 1.

       Existuje mnohem jednodušší způsob, který je také „ve své nulové variantě“ schodný. Mě se ale nelíbí:

0xxxxxxx
1xxxxxxx 0xxxxxxx
1xxxxxxx 1xxxxxxx 0xxxxxxx
1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx
…

Nelíbí se mi proto, že se musí provádět datové posuny. Srovnejte pro datovou šířku 1:

Způsob jedna: 0          00 1          01 2          1000 3          1001 4          1010 5          1011 6          110000 7          110001 8          110010 9          110011 10        110100 11        110101 12        110110 13        110111 …

Způsob dvě: 0          00 1          01 2          1000 3          1001 4          1100 5          1101 6          101000 7          101001 8          101100 9          101101 10        111000 11        111001 12        111100 13        111101 …

No vidíte to? Ne? Tak dobře – moc to vidět nejde, ale těch posunů je tam fakt víc. Honba za dokonalostí pokračuje…

<< Previous post  Next post >>