# XBUP - Dokumentace: Kódování čísel

### Úvod

Tento dokument je součástí dokumentace projektu eXtensible Binary Universal Protocol. Obsahuje popis používaných typů kódování čísel a jejich vývoj.

O úroveň výše

### Obsah

1. Kódování čísel
1.1. Stanovené podmínky
1.2. Unární kódování
1.3. Binární kódování
1.4. Prokládané kódování
1.5. Souvislé kódování
1.6. Redundantní a neredundantní varianta
1.7. Rekurzivní kódování
1.7.1. Nelineární rekurzivní kódování
1.7.2. Modifikované rekurzivní kódování LRUB
1.7.3. Korigované rekurzivní kódování SLRUB
1.8. Formy kódování UBNumber
1.8.1. Kódování UBNatural
1.8.2. Kódování UBENatural
1.8.3. Kódování UBInteger
1.8.4. Kódování UBEInteger
1.8.5. Kódování UBReal
1.8.6. Kódování UBEReal
1.8.7. Kódování UBRatio
1.8.7.1. Kódování s reverzí
1.8.7.2. Přímé kódování
1.8.8. Další zvažovaná kódování
1.9. Argumentace správnosti
1.9.1. Otevřené otázky
2. Reference

### 1. Kódování čísel

Specifické kódování čísel je základním stavebním kamenem celého protokolu, které jej odlišuje od většiny současných binárních formátů. Jde o variantu gama kódování, prozatím označováno jako rekurzivní unárně-binární kódování. Je vysoce pravděpodobné, že použité kódování už bylo někým dříve popsáno a pojmenováno.

Základním postupem je kombinace tří technik: Kódování na fixní počet bitů, použití zarážky (rekurze) a uvození hodnoty délkou.

Na splnění základního požadavku, umožnit kódování libovolného čísla, je dostačující i pravděpodobně nejjednodušší unární kódování alfa. Toto kódování je však naprosto nevyhovující díky své neúspornosti. Na opačné straně, co se úspornosti týče, se nachází binární kódování beta, kódující jednotlivé bity jako hodnoty při exponentu o základu 2. Toto kódování však vyžaduje vymezení délky a nelze jej přímo použít. Výsledné kódování tak vznikalo postupně různými kombinacemi obou uvedených variant a vylučováním nevhodných či nepraktických kódů. Z několika vhodných varian byla vybrána ta, která se jevila být pro potřeby protokolu nejvýhodnější.

### 1.1. Stanovené podmínky

Byly stanoveny požadavky, které má navrhované kódování splňovat.

Stanovené požadavky:

- Kódování libovolně velkého čísla
  Základním požadavkem je umožnit vyjádření libovolně velkého čísla. Nelze uvažovat pouze dostatečně velkou rezervu, neboť by tak formát ztrácel svoji univerzálnost.
- Kódování do posloupnosti bitů
  Data jsou kódována do potenciálně nekonečné posloupnosti bitů. Posloupnost dvoustatových nosičů informace je zvolena díky své minimálnosti. Ukládání do posloupnosti stavových údajů různých rozsahů v podstatě není z datového hlediska kódování a volba více než dvoustavových nosičů nemá žádné logické opodstatnění.
- Slučitelnost s unárním kódováním
  Součástí protokolu měla být původně varianta, realizující ukládání pomocí posloupností bitů 1, ukončená bitem 0, tedy obdoba unárního kódování alfa. Domníval jsem se, že toto kódování je natolik základní, že by mělo být vhodné jej umožnit v protokolu použít. Jeho negativní vlastnosti, především lineární závislost délky kódu vzhledem k hodnotě, jsou dosti nepříjemné. Nicméně se jeví vhodné požadovat od vlastního kódování, aby v něm bylo unární kódování v nějaké variantě zahrnuto.
- Efektivita
  Cílem je se co nejvíce přiblížit binární reprezentaci čísla, konkrétně samotné unární kódování je velmi neefektivní. Stejně tak další druhy kódování, jako je například čistě unárně binární kódování (gama) nebo Fibonachiho kódování, jsou stále nedostatečně efektivní. Rekurzivní unárně-binární kódování je prozatím dle mého názoru ta nejlepší volba.
- Determinizmus (Efektivita)
  Ačkoli jednoznačné vyjádření čísla není nutností, je vhodné s ohledem na algoritmizaci, vynutit jedinou možnou variantu reprezentace dané hodnoty. Je také nutné s ohledem na již zmíněnou efektivitu kódování. Proti tomuto sice hovoří některé výhody, které redundantní kódování má, přesto však jsem se rozhodl tento požadavek dodržet.
- Zpracovatelnost (Efektivita)
  Tento požadavek se snaží vynutit co nejjednodušší zpracování dat a skrývá se pod ním hned několik věcí. Mělo by být například co nejméně potřebných instrukcí pro kódování, minimum binárních posuvů při čtení a zápisu čísla, nebo požadavek na kompaktnost čísla - vlastní hodnota je tvořena souvislou posloupností bitů.
- Organizace bitů po kvantech (Efektivita)
  Tento požadavek je zaveden kvůli organizace bitů na bajty při zpracování na současných počítačích. Čísla jsou kódována místo do posloupnosti jednotlivých bitů, do bitových skupin, nejlépe o délce exponentu o základu 2. Prozatím používám organizaci po osmicích (oktetech), tedy známých bajtech.

### 1.2. Unární kódování

Unární kódování je staré, jako lidstvo samo (kolik prstů, taková hodnota, kolik čárek na stěně jeskyně, tolik zabitých mamutů :-) ). Nejznámější variantou pro kódování v nekonečném bitovém proudu je kódování alfa, kdy hodnotu nese počet stejných bitů zakončených bitem opačným. Toto kódování však kóduje přirozená čísla bez hodnoty 0, která je však potřebná, a proto je použita obdoba s počáteční hodnotou 0. Tuto posloupnost lze interpretovat i jinými způsoby, například: Čísla patří do jazyka (1*0), realizují algebru celých čísel s konstantou (0) a operací následník (1), nebo také jako binární kód jednobitových hodnot ukončených zarážkou hodnoty 0. Ze vstupního proudu se čtou bity a pokud je bit 1, čte se následník, jinak se čtení zastaví a vrátí se počet přečtených bitů 1. Čísla v tomto tvaru by měla být při vlastním zpracování souboru převedena na data ve vnitřní paměti počítače, realizována ve tvaru, který lze efektivněji zpracovávat, například v binárním kódování, které je uvedeno jako další.

### 1.3. Binární kódování

Nejefektivnější známé binární kódování beta je určeno pro kódování dat na konečné posloupnosti bitů a není tak pro kódování do potenciálně nekonečné posloupnosti binární, neboť vyžaduje další údaj a tím je délka. Tu je možné realizovat například třetím symbolem, podobně, jako je například v morseově abecedě pro posloupnost teček a čárek s oddělovačem mezera. Každý další bit je vlastně další cifrou a přináší tak do výsledné hodnoty navýšení o hodnotu následujícího exponentu o základu 2. Z těchto důvodů nebylo možné použít přímo binární kódování a bylo nutné nějakým způsobem přidat i kódování délky. Nejvhodnější se mi jevila varianta kombinace unárního a binárního kódování.

### 1.3.1. Nárůstové binární kódy

Jednou z možností je použít postupně rostoucí binární kódy ukončené zarážkou. Příklad s lineárním nárůstem délky:

     0           = 0
     100         = 1
     101         = 2
     110         = 3
     111000      = 4
     111001      = 5
     111010      = 6
     111011      = 7
     111100      = 8
     111101      = 9
     111110      = 10
     1111110000  = 11
     ...

Délka kódu může růst i rychleji, například exponenciálně, či může být použita jiná základní délka, případně ani nemusí docházet k nárůstu délky.

### 1.4. Prokládané kódování

Tato varianta prokládaného unárně-binárního kódování je ukázkou nevhodné realizace. Pracuje tak, že pokud je nejvyšší bit v bajtu 1, rozšiřuje se hodnota o další bajt. Základní tvar čísla je jednobajtový, přičemž hodnota nejvyššího (prvního) bitu je 0. Pokud je nejvyšší bit 1, rozšiřuje se celková délka čísla o další bajt, přičemž se u nového bajtu znovu aplikuje stejné pravidlo. Pokud by se binární kódování rozšiřovalo po jednom bitu, odpovídala by tato varianta kódování gama.

Posloupnost hodnot vypadá takto (binární tvar = interval možných hodnot):

     0xxxxxxx                                = 0..7Fh
     1xxxxxxx 0xxxxxxx                       = 0..3FFFh
     1xxxxxxx 1xxxxxxx 0xxxxxxx              = 0..1FFFFFh
     1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx     = 0..0FFFFFFFh
     ...

binárně kódovaná hodnota může být interpretována jak redundantně tak neredundantně a při nulové šířce binárního kódu tato varianta odpovídá unárnímu kódování. Ačkoliv se tento způsob na první pohled může zdát vhodný, má ve skutečnosti několik nevýhod:

- Přeskočení čísla vyžaduje přečtení celé posloupnosti (zpracovatelnost)
- je nutné volit endianitu kódování mezi Big a Little Endian (determinizmus)
- při převodu se musí provádět množství bitových posunů, neboť je vlastní hodnota nesouvislá (zpracovatelnost)
- délku prostoru nutného pro alokaci lze zjistit pouze přečtením všech bajtů (zpracovatelnost)

### 1.5. Souvislé kódování

Toto kódování je rozděleno na dvě kompaktní části, unárně kódovanou délku a binárně kódovanou vlastní hodnotu. Délka musí být uvedena první, aby byla hodnota prefixová a tedy dekódovatelná ve stejném pořadí, jako je čtena. Toto kódování tak má stejný základní jednobajtový tvar, kde nejvyšší bit je 0 a ostatní bity určují číslo. Pokud je nejvyšší bit 1, rozšiřuje se číslo o další bit unárního kódování a bit nebo skupinu bitů kódovaných binárně. Počet těchto bitů může být v každém kroku konstantní a můžeme pro něj pak zavést proměnnou ClusterSize. Běžně budeme používat hodnotu ClusterSize = 7, jak jsme to udělali i v předchozím případě. Lépe snad půjde tento princip pochopit z příkladu posloupnosti.

Příklad (binární tvar = interval možných hodnot):

     0xxxxxxx                                = 0..7Fh
     10xxxxxx xxxxxxxx                       = 0..3FFFh
     110xxxxx xxxxxxxx xxxxxxxx              = 0..1FFFFFh
     1110xxxx xxxxxxxx xxxxxxxx xxxxxxxx     = 0..0FFFFFFFh
     ...
     11111110 xxxxxxxx .. xxxxxxxx           = 0..1FFFFFFFFFFFFh
     11111111 0xxxxxxx .. xxxxxxxx           = 0..0FFFFFFFFFFFFFFh
     ...

Tato varianta se zdála být mnohem přijatelnější, a to jak vzhledem k operaci přeskočení čísla, tak i vzhledem ke zjištění místa potřebného k alokaci. Navíc není třeba provádět tolik aritmetických posunů k určení hodnoty čísla. Stačí z čísla odstranit všechny nejvyšší bity až do prvního nulového. Tento způsob kódování je použit například u UTF-8, používaného k ukládání znaků ve standardu Unicode, nebo i v různých projektech binárních kódování XML. Požadavek zpracovatelnost v podstatě vynucuje pořadí hodnot bajtů od nejvyšší po nejnižší, tzv. Big Endian, neboť tím odpadává množství aritmetických posunů.

Tím, že se rezervují bity pro záznam délky, je toto kódování samozřejmě méně účinné než kódování beta, ale zato je opravdu binární. Tuto ztrátu lze vyjádřit například jako počet nevyužitých bitů na bajt. U obou předchozích variant je ztráta 1 bit na každý bajt, tedy pro lepší představu, z každého intervalu, který by mohl být realizován se ztrácí 1/(2^délka v bajtech/slovech). Konkrétně je to v tomto případě 1/2, což znamená, že místo intervalu 0..0FFh je možné v jednom bajtu uložit pouze polovinu, tedy 0..7Fh.

Další možností je, místo rozšiřování binární části čísla o konstantní délku, zvolit nárůst vyšší, například exponenciální. To by však vedlo k rostoucímu plýtvání.

### 1.6. Redundantní a neredundantní varianta

V obou předchozích variantách kódování můžeme binární část čísla interpretovat přímo jako binární kód bez dalších úprav, čímž však vzniká jistá nejednoznačnost - redundance. Například hodnotu 1 můžeme uložit v nekonečně mnoha tvarech různých délek.

Tvary čísla 1:

     00000001                                = 1
     10000000 00000001                       = 1
     11000000 00000000 00000001              = 1
     ...

Tato redundance má zřejmě i některé výhody. Především se s takto kódovanými čísly pracuje mnohem jednodušeji, a také lze pomocí této redundance v souboru dopředu rezervovat prostor pro větší interval hodnot, díky čemuž může dojít k omezení přístupu k souboru při zvětšování, či zmenšování této hodnoty. Například při zápisu čísla 200 místo jiného většího nemusí nutně dojít ke změně velikosti celého souboru. Na druhou stranu může tato redundance zvětšit velikost souboru bez zvýšení celkové informační hodnoty.

Při povolení redundance by bylo možné kódovat další typy hodnot, jako například čísla celá, reálná a další, následovně:

Jednotlivé typy jsou interpretováný takto (typ - popis):

Natural - Nese přirozené číslo nebo 0 (celé nezáporné číslo) na určeném počtu bitů
Integer - Nejlevější bit (nejvyšší) je znaménko. 0 - kladné, 1 - záporné a z důvodu redundace je v podstatě jedno, zda jsou záporná čísla v normálním, inverzním, nebo dvojkovém doplňkovém kódu
Real - Reálné číslo reprezentují dvě čísla typu Integer. První číslo je báze a druhé je mantisa, která udává index dvojkového, nebo jiného posunu
EReal - Reálné číslo se zvolenými konstantami pro +- ∞ nekonečno:

       00111111  00000000                    = +nekonečno
       01000000  00000000                    = -nekonečno

Jelikož hodnoty odpovídající těmto konfiguracím lze uvést i ve tvaru jiné délky, lze tyto konstanty takto zcela bez problému stanovit.
MultiBit - pole bitů indexovaných zprava od 0

Z požadavku na zpracovatelnost však plyne spíše využití neredundantní formy kódování. Hodnoty jednotlivých typů pak mají jednoznačné vyjádření a pokud se hodnota dostane mimo vyhrazený interval musí dojít k přepracování celého souboru, což může vést ke značné režii a vyžaduje zavedení dodatečných technik. Další nevýhodou je pak složitější převod čísel.

Velkou ztrátovost čísel, která je způsobena použitím unárního kódování pro representaci délky vlastní hodnoty, lze částečně snížit použitím rekurze.

### 1.7. Rekurzivní kódování

Zatím poslední navrhovanou variantou je jednoduchá úprava na rekurzivní neprokládané unárně binární kódování. Číslo je opět kódováno dvojicí Length a Value, přičemž hodnota Length je od jisté hodnoty kódována ve stejném kódování jako celé číslo. Rovnou použijeme neredundantní deterministickou variantu, díky níž je kódování jednoznačně dekódovatelné. Kromě toho, strukturu kódování opět ovlivňuje konstanta ClusterSize, která určuje způsob nárůstu délky hodnoty Value.

Nejprve je uvedena hodnota Length, která je typu přirozené číslo včetně 0. Je kódována jako jeden bit určujicího rekurzi, přičemž pokud je hodnota tohoto bitu 0 je i hodnota 0 a v případě, že je tento bit 1, jsou další bity intepretovány rekurzivně jako další hodnota ve stejném rekurzivním kódování a výsledná hodnota je zvětšena o 1.

Hodnota Value je kódována binárně na bitové posloupnosti délky závisející na Length tímto způsobem:

Je-li Length<ClusterSize + 1 pak délka Value je (Length+1)*ClusterSize jinak má Value délku Length*(ClusterSize+1)

Jak lze nyní vidět, v případě že je konstanta ClusterSize = -1, stává se z celého kódování prosté unární kódování, což lze vidět ze souvislosti rekurze a algebry s operací následník uvedené dříve. V ostatních případech ClusterSize + 1 určuje velikost shluků o které je rozšiřována délka čísla. To je velmi výhodné pro zarovnávání na n-tice bitů, jako jsou například bajtové oktety (osmice bitů), s odpovídající hodnotou ClusterSize = 7.

Nejlépe je to opět vidět na příkladě.

Příklad:

     0xxxxxxx                                = 0..7Fh
     10xxxxxx xxxxxxxx                       = 0..3FFFh
     110xxxxx xxxxxxxx xxxxxxxx              = 0..1FFFFFh
     1110xxxx xxxxxxxx xxxxxxxx xxxxxxxx     = 0..0FFFFFFFh
     ...
     11111110 xxxxxxxx .. xxxxxxxx           = 0..0FFFFFFFFFFFFFFh
              \_____ 7 krát _____/
     11111111 00000000 xxxxxxxx .. xxxxxxxx  = 0..0FFFFFFFFFFFFFFFFh
              \navíc_/ \_____ 8 krát _____/
     11111111 00000001 xxxxxxxx .. xxxxxxxx  = 0..0FFFFFFFFFFFFFFFFFFh
              \navíc_/ \_____ 9 krát _____/
     ...

    Obecně pro prefix 0FFh:

     11111111 N xxxxxxxx .. xxxxxxxx  = 0..2^( 8*(N + 8))
                \____ n+8 krát ____/

kde N je další číslo rekurzivního typu.

Mohlo by se zdát, že tato varianta je pouze zbytečným zesložitěním unárně binárního kódování a přináší výhody pouze pro velmi velká čísla, podle mého názoru však má smysl, a to především pro malé velikosti ClusterSize, nebo pro ukládání velkých čísel z důvodu přesnosti. Následující tabulka ukazuje ztrátu informace na jeden shluk oproti čistě binárnímu kódování na shlucích o stejném počtu (1- (Podíl max. hodnota rekurzivního a binárního na daném počtu bitů )/ počet shluků), příklad je pro ClusterSize = 7.

Průběh ztrát (počet bajtů vyjadřujících vlastní číslo = množství ztracené informace na bajt):

     1..7          = 0,500000
     8             = 0,670123
     9             = 0,635129
     10            = 0,603149
     ..
     14            = 0,500000
     15            = 0,478801
     ..
     127+8         = 0,077761
     127+9         = 0,112795
     127+10        = 0,112037
     ...

Ztráta postupně konverguje k nule na rozdíl od unárně-binárního kódování, kde je konstantně 0,5, konvergence k binárnímu kódu je tedy vyšší. Nejvyšší ztráta (limes superior) dosahuje hodnoty přibližně 0,67.

Pro použití rekurze hovoří pouze efektivita, ačkoliv existují i rychleji konvergující kódování, toto lze v jistém smyslu považovat za základní rekurzní. Pro použití této varianty tedy hovoří požadavek efektivity. Rekurzivní volání sebou obecně nese vyšší režii na uchovávání proměnných, ale v tomto případě je možné použít prostou iteraci. Proti hovoří vyšší složitost implementace a nelineárnost nárůstu délky kódu.

Toto kódování bylo stanoveno pro protokol XBUP jako základní. Struktura kódování vyžaduje determinizmus a vynucuje i pořadí interpretace bitů binárního kódování od nejvyššího po jednotku. Podobně, jako u předchozí varianty, je také vynucena endianita kódování díky požadavku na efektivitu. Toto kódování bude nadále v dokumentu označováno jako kódování UBNumber.

Pro názornost je přiložena tabulku hodnot rekurzivního kódování při ClusterSize = 0, tedy v nejnižší "neunární" variantě.

Kód a odpovídající hodnota

     0                                       = 0
     10 0                                    = 1
     10 1                                    = 2
     110 0 00                                = 3
     110 0 01                                = 4
     110 0 10                                = 5
     110 0 11                                = 6
     110 1 000                               = 7
     110 1 001                               = 8
     ...
     110 1 111                               = 14
     1110 0 00 0000                          = 15
     ...
     1110 0 00 1111                          = 30
     1110 0 01 00000                         = 31
     ...

### 1.7.1. Nelineární rekurzivní kódování

Jednou z možných úprav rekurzivního kódování je možná změna rychlosti růstu délky vlastní hodnoty. Ve výše uvedené variantě roste hodnota lineárně. Jedna z možných nevýhod je, že v případě přechodu při zvyšování zanoření rekurze, naroste celková délka čísla o větší kus než je základní jednotka (ClusterSize + 1). Omezením tohoto růstu by bylo možné dosáhnout růstu o jednotky, ale na druhé straně by to vedlo k znepřehlednění výpočtu hodnoty, ale především k selhání kódování pro variantu ClusterSize=0.

Jinou možnou úpravou by bylo naopak zrychlení růstu, nepříklad rozšiřování délky kvadraticky, nebo exponenciálně. To by však vedlo spíše k plýtvání prostorem bez žádného opodstatnitelného přínosu.

### 1.7.2. Modifikované rekurzivní kódování LRUB

Následující úprava (Linear-prolonging Recursive Unary-Binary encoding) se nabízí jako potenciální náhrada za prosté rekurzivní kódování v následujících verzích. Jedná se o úpravu, při které se ve vybraných případech snižuje rychlost růstu binární části čísla tak, aby se dosáhlo čistě lineárního nárůstu délky celého kódu. Kódování si tak zachovává rekurzivitu i jednoznačnost a přitom se řeší některé problémy, které se při použití čistě rekurzivního kódu mohou vyskytnout.

- Varianta kódování s hodnotou ClusterSize = 0 je kompatibilní s unárním kódováním.
- Snižuje se skokový nárůst délky hodnoty - viz. dále

Následuje příklad:

     00                                      = 0
     01                                      = 1
     10 00                                   = 2
     10 01                                   = 3
     10 10                                   = 4
     10 11                                   = 5
     11 00 00                                = 6 (omezený nárůst)
     11 00 01                                = 7
     11 00 10                                = 8
     11 00 11                                = 9
     11 01 00 00                             = 10
     ...
     11 01 11 11                             = 25
     11 10 00 00 00                          = 26
     11 10 00 00 01                          = 27
     ...

### 1.7.3. Korigované rekurzivní kódování SLRUB

Kódování SLRUB (Size-corrected Linear-prolonging Unary-Binary Encoding) je úprava předchozího kódování tak, aby v případě, kdy chceme definovat oblast pomocí její délky, mohli definovat velikost libovolně velké oblasti. Kódování se v tomto případě na úrovni interpretace hodnoty stává redundantní. Tato varianta bude spíše zavedena jako typ pro kódování LRUB jako takové (pro čistě rekurzivní kódování není realizace vhodná).

Jak bude vypadat interpretace stejného příkladu:

     00                                      = 0
     01                                      = 1
     10 00                                   = 1
     10 01                                   = 2
     10 10                                   = 3
     10 11                                   = 4
     11 00 00                                = 4
     11 00 01                                = 5
     11 00 10                                = 6
     11 00 11                                = 7
     11 01 00 00                             = 7
     ...
     11 01 11 11                             = 23
     11 10 00 00 00                          = 23
     11 10 00 00 01                          = 24
     ...

### 1.8. Formy kódování UBNumber

Na rozdíl od vlastního kódování bylo stanovení kódování dalších typů čísel víceméně automatickou záležitostí. Podobně jako v předchozím případě i nyní chceme kódovat celá, reálná a další čísla. Dodatečně byla stanovena podmínka, že pro ClusterSize >= 0, musí být vždy posloupnost bitů 0 vyjadřovat skutečnou hodnotu 0. Přesnější specifikaci a příklady převodních algoritmů je možné nalézt ve specifikaci protokolu. Následují kódování odvozené od UBNumber pro různé typy čísel.

Pozn. Převodní algoritmy jsou pro variantu rekuzivního kódování bez lineárního omezení, bude opraveno později

### 1.8.1. Kódování UBNatural

Pro kódování přirozeným čísel s nulou, neboli také množinu omega, slouží právě toto kódování, které je pouze přímým odvozením UBNumber. Umožňuje kódovat právě libovolně velké přirozené číslo.

Příklady hodnot typu UBNatural

     00000000                              = 0
     00000001                              = 1
     ...
     01111111                              = 7Fh
     10000000 00000000                     = 80h
     10000000 00000001                     = 81h
     ...
     10111111 11111111                     = 407Fh
     11000000 00000000 00000000            = 4080h
     ...

Kódování hodnoty (hodnota >> datový proud)

`Value := Hodnota
Length := 0
dokud platí Length <= ByteSize+1 a zároveň Value>=2^(ByteSize*(Length+1)) proveď (
Length := Length + 1
Value := Value - 2^(ByteSize*(Length+1))
)
Je-li Length = 8 potom (
ExtLength := 0
dokud platí Value>=2^((ByteSize+1)*(ExtLength+ByteSize+1)) proveď (
ExtLength := ExtLength + 1
Value := Value - 2^((ByteSize+1)*(ExtLength+ByteSize+1))
)
Zapiš prefix
Zapiš ExtLength
) jinak Zapiš unárně Length
Zapiš binárně Value`

Dekódování hodnoty (datový proud >> hodnota)

`Přečti prefix nebo Length
Je-li prefix potom (
Length := ByteSize + 1
Přečti ExtLength
)
Přečti Value
Hodnota := Value
Je-li prefix potom (
Pro každé I z intervalu <1..ExtLength> Hodnota := Hodnota + (2^((I+ByteSize) * (ByteSize+1)))
)
Pro každé I z intervalu <1..Length> Hodnota := Hodnota + (2^(I * ByteSize))`

### 1.8.2. Kódování UBENatural

Pro přírozené čísla se speciální konstantou pro nekonečno je určeno toto kódování. Bude využíváno především později u blokové struktury pro reprezentaci délek a nekonečno zde bude vyjadřovat neznámou, potenciálně nekonečnou délku. Při realizaci byla hodnota pro nekonečno umístěna na nejvyšší hodnotu v základním tvaru. Jinou možností bylo umístit nekonečno na hodnotu 0, ale to by bylo v rozporu s dříve stanoveným pravidlem pevné nuly.

Příklady hodnot typu UBENatural

     ...
    0111110                              = 7Eh
    0111111                              = ∞
    1000000 00000000                     = 7Fh
    1000000 00000001                     = 80h
    ..

Konverze hodnoty UBNatural

`Je-li Hodnota>(2^ByteSize) potom Hodnota := Hodnota - 1 jinak
Je-li Hodnota=(2^ByteSize)-1 potom Hodnota := ∞`

### 1.8.3. Kódování UBInteger

Toto kódování slouží pro ukládání celých čísel. Binární část je interpretována jako kód ve dvojkovém doplňkovém kódu s nejvyšším bitem určujícím znaménko. Zřejmě jiný způsob kódování ani není možné použít z důvodů efektivity a úspornosti, navíc znaménko musí být uvedeno jako první, protože je důležitější než hodnota (ovlivňuje zpracování).

Příklady hodnot typu UBInteger

     ...
     11011111 11111111 11111111            = -2041h
     10100000 00000000                     = -2040h
     ...
     10111111 11111110                     = -42h
     10111111 11111111                     = -41h
     01000000                              = -40h
     ...
     01111110                              = -2
     01111111                              = -1
     00000000                              = 0
     00000001                              = 1
     ...
     00111111                              = 3Fh
     10000000 00000000                     = 40h
     10000000 00000001                     = 41h
     ...
     10011111 11111111                     = 203Fh
     11000000 00000000 00000000            = 2040h
     ...

Kódování hodnoty

`Value := Abs(Hodnota)
Je-li Hodnota<0 potom Value := Value + 1
Length := 0
Dokud platí Length <= ByteSize+1 a zároveň Value>=2^(ByteSize*(Length+1)) proveď (
Length := Length + 1
Value := Value - 2^(ByteSize*Length-1)
)
Je-li Length = 8 potom (
ExtLength := 0
dokud platí Value>=2^((ByteSize+1)*(ExtLength+ByteSize+1)) proveď (
ExtLength := ExtLength + 1
Value := Value - 2^((ByteSize+1)*(ExtLength+ByteSize+1))
)
Zapiš prefix
Zapiš ExtLength
) jinak Zapiš unárně Length
Je-li Hodnota<0 potom Value := Neg(Value)
Zapiš binárně Value`

Kde operace Neg je inverze nejnižších ByteSize*(Length+1) bitů hodnoty Value (včetně znaménka) a Abs je funkce absolutní hodnoty.

Dekódování hodnoty

`Přečti prefix nebo Length
Je-li prefix potom (
Length := ByteSize + 1
Přečti ExtLength
)
Přečti Value
Hodnota := Value
Je-li prefix potom BitLength := ByteSize*(ExtLength+8)+7 jinak BitLength := Length*ByteSize+(7-Length)
Je-li (Value and 2^(BitLength))>0 potom ( // Test na záporné znaménko
Hodnota := ( - Neg(Hodnota) ) - 1
Pro každé I celé z intervalu <1..Length> Hodnota := Hodnota - (2^(I*ByteSize-1))
Je-li prefix potom (
Pro každé I z intervalu <1..ExtLength> Hodnota := Hodnota - (2^((I+ByteSize) * (ByteSize+1)))
)
) jinak (
Pro každé I celé z intervalu <1..Length> Hodnota := Hodnota + (2^(I*ByteSize-1))
Je-li prefix potom (
Pro každé I z intervalu <1..ExtLength> Hodnota := Hodnota + (2^((I+ByteSize) * (ByteSize+1)))
)
`

### 1.8.4. Kódování UBEInteger

Podobně jako v případě UBENatural i tentokrát se jedná o rozšíření čísla o konstanty pro nekonečno, tentokrát navíc i záporné. Umístěny jsou stejným způsobem.

Příklady hodnot typu UBEInteger

     ...
     10111111 11111111                     = -40h
     01000000                              = -∞
     01000001                              = -3fh
     ...
     00111110                              = 3Eh
     00111111                              = ∞
     10000000 00000000                     = 3Fh
     ...

Konverze hodnoty UBInteger

`Je-li Hodnota>(2^(ByteSize-1)) potom Hodnota := Hodnota - 1 jinak
Je-li Hodnota<(2^(ByteSize-1))+1 potom Hodnota := Hodnota + 1 jinak
Je-li Hodnota=(2^(ByteSize-1))-1 potom Hodnota := ∞ jinak
Je-li Hodnota=-(2^(ByteSize-1)) potom Hodnota := -∞`

### 1.8.5. Kódování UBReal

Cílem tohoto kódování je umožnit ukládání reálných čísel. Jelikož je však reálných čísel nespočetně mnoho, bylo nutné se omezit na podmnožinu. Zvoleným omezením byl konečný dvojkový rozvoj čísla, neboť nekonečné čísla není možné v konečném prostoru ukládat. Jako vhodná varianta se nabízí kódovat tyto čísla pomocí dvojice čísel typu UBInteger. První z nich určuje bázi a druhé mantisu. Báse nese vlastní hodnotu a mantisa určuje o kolik řádů je tato hodnota posunuta. Například u procesorů s architekturou intel jsou reálná čísla realizována pomocí standardu IEEE 754, který používá k odstranění redundance metodu neviditelné jedničky. Stejně tak i v tomto případě není možné povolit redundanci, aby nebylo porušeno pravidlo jednoznačnosti a je nutné nalézt způsob, jak se s takovýmto typem nejednoznačnosti vypořádat. Můžeme se například pokusit použít obdobu metody neviditelné jedničky. Je možné volit mezi umístěním jedničky před nejvyšší, nebo za nejnižší bit hodnoty Value. Mimo jiné je zde také možnost několika interpretací mantisy. Popišme tedy nejprve techniku umístění "neviditelné" jedničky před nejvyšší bit báze. Při interpretaci čísla je pak nutné, po případné negaci záporného čísla, přidat před platné bity jeden bit hodnoty 1. Už v této fázi je vidět jisté obtíže s přeskakováním znaménka. Dalším problémem je pak hned interpretace posunu řádové tečky. Běžný desítkový exponent zde asi nebude vhodné použít a místo toho bude lepší zvolit "polovinnou" (dvojkovou) tečku. Ukažme si tři způsoby umístění tečky v případě umístení neviditelné jedničky před nejvyšší bit:

- interpretace tečky k nejspodnějšímu bitu

        00000000  00000000                   = 64              [(1)000000.]

- interpretace tečky k nejvyššímu bity

        00000000  00000000                   = 1               [(1).000000]

- interpretace tečky před "neviditelnou" jedničku

        00000000  00000000                   = 0.5             [.(1)000000]

Výhodnější se jeví umístit tečku k nejvyššímu bitu, s čímž ale souvisí problémy s přepočtem mantisy v závislosti na délce vlastní hodnoty báze. Těm bychom se však nevyhnuli ani umístěním tečky na konec kódu, kdy by zase bylo nutné nějakým způsobem posouvat mantisu. Třetí způsob je v podstatě stejně nevhodný. Naštěstí nám zbývá ještě méně neobvyklá varianta přidání jedničky na konec čísla. Opět si uvedeme způsoby interpretace tečky:

- interpretace tečky k nejvyššímu bity

        00000000  00000000                   = 0.015625        [.000000(1)]

- interpretace tečky k nespodnějšímu bitu

        00000000  00000000                   = 0.5             [000000.(1)]

- interpretace tečky za "neviditelnou" jedničku

        00000000  00000000                   = 1               [000000(1).]

Nakonec byla vybrána právě třetí z těchto variant, neboť se zdála být nejvhodnější. Zbývalo už pouze vyřešit problém s interpretací hodnoty 0, nejjednoduššeji odsunutím jedničky. Uvedený přístup shrnuje následující algoritmus.

`Je-li (X=0 a zároveň Y=0) potom Hodnota := 0 jinak (
Hodnota := (X*2+1)*(2^Y)
Je-li (X>0 a zároveň Y=0) potom Hodnota := Hodnota - 2
)`

Zřejmě kódování čísla je technicky obtížnější. Vyžaduje totiž delení čísla dvěmi, dokud nebude zbytková část 1, nebo násobení, dokud nebude necelá část čísla rovna 1/2. Takto vzniklé celé číslo se pak uloží do báze a počet dělení, nebo negace početu násobení se poté uloží do mantisy. Tento postup bude vhodné v budoucnu co nejvíce optimalizovat (třeba by se mohla přidat do procesorů nějaká vhodná instrukce, nebo dvě :-) ).

K výhodám zvoleného tvaru kódování patří například to, že parita mantisy určuje, zda se jedná o celé číslo, nebo číslo, které má i necelou část. Stejně tak je možné z parity báze určit paritu celého čísla. Pokud tedy místo celého čísla uvedeme pouze jednu jeho část můžeme kódovat některé užitečné hodnoty. Pokud uvedeme například pouze bázi, pak je mantisa nulová a kódována jsou lichá čísla s nulou, což není až tak užitečné jako druhý případ, kdy je uvedena pouze mantisa a kódovány jsou dvojkové exponenty s vyjímkou hodnoty 1 nahrazenou hodnotou 0.

Čísla s nekonečným rozvojem bude možné ukládat pouze pomocí vyšších matematických a algoritmických bloků, tedy například pomocí rekurze. Dvojkový tvar čísla je prostě nejvhodnější pro bitový proud dat.

Příklady hodnot typu UBReal

- čísla s mantisou nula:

        ...
      10111111 11111111  00000000          = -81h
      01000000  00000000                   = -7Fh
      01000001  00000000                   = -7Dh
      ...
      01111110  00000000                   = -3
      01111111  00000000                   = -1
      00000000  00000000                   = 0 (1)
      00000001  00000000                   = 1 (3)
      00000010  00000000                   = 3 (5)
      ...
      00111111  00000000                   = 7Dh (7Fh)
      10000000 00000000  00000000          = 7Fh (81h)
      ...

- další čísla s různými mantisami:

      01111111  00000001                   = -2
      00000000  00000001                   = 2
      00000001  00000001                   = 6
      00000010  00000001                   = 10
      00000000  00000010                   = 4
      00000000  00000011                   = 8
      00000000  01111111                   = 0.5
      00000001  01111111                   = 1.5

Kódování hodnoty

`Báze := 0
Mantisa := 0
Je-li not Hodnota=0 potom (
if Frac(Hodnota)=0 potom (
Dokud platí not Frac(Hodnota)=0.5 proveď (
Mantisa := Mantisa + 1
Báze := Báze / 2
)
) jinak (
Dokud platí not Frac(Hodnota)=0.5 proveď (
Mantisa := Mantisa - 1
Báze := Báze * 2
)
)
)
Zapiš UBInteger Báze
Zapiš UBInteger Mantisa`

Dekódování hodnoty

`Báze := Přečti UBInteger
Mantisa := Přečti UBInteger
Je-li (Báze=0 a zároveň Mantisa=0) potom Hodnota := 0 jinak (
Hodnota := (Báze*2+1)*(2^Mantisa)
Je-li (Báze>0 a zároveň Mantisa=0) potom Hodnota := Hodnota - 2
)`

### 1.8.5.1. UBReal jedním číslem

Reálné číslo s konečným desetinným rozvojem je zřejmě možno zakódovat i do jediné hodnoty UBNumber, neboť je stejně tak možné efektivně zakódovat libovolnou konečnou posloupnost celých čísel do jediného čísla přirozeného. Pro či proti použití tohoto kódování zatím nebyly nalezeny vhodné argumenty.

Jedno z možných řešení je diagonalizační metoda.

    (0,0)  (0,1)  (0,2)  (0,3)
          /      /      /
         /      /      /
    (1,0)  (1,1)  (1,2)  (1,3)
          /      /      /
         /      /      /
    (2,0)  (2,1)  (2,2)  (2,3)
          /      /      /
         /      /      /
    (3,0)  (3,1)  (3,2)  (3,3)

    ...

    (0,0) - (1,0) - (0,1) - (2,0) - (1,1) - (0,2) - ...

### 1.8.6. Kódování UBEReal

Opět dalším rozšířením je reálné číslo s konstantami pro +-nekonečno. V podstatě je pro mantisu s hodnotou 0 interpretována báze jako typ UBEInteger. To odpovídá konstantám:

       00111111 00000000                     = +nekonečno
       01000000 00000000                     = -nekonečno

Příklady hodnot typu UBEReal

     10111111 11111111  00000000           = -7Fh
     01000000  00000000                    = -∞
     01000001  00000000                    = -7Dh
     ...
     00111110  00000000                    = 7Bh
     00111111  00000000                    = ∞
     10000000 00000000  00000000           = 7Dh
     ...

Konverze hodnoty UBReal

`Je-li (Báze=0 a zároveň Mantisa=0) potom Hodnota := 0 jinak (
Je-li (Báze=(2^ByteSize)-1 a zároveň Mantisa=0) potom Hodnota := ∞ jinak
Je-li (Báze=-(2^ByteSize) a zároveň Mantisa=0) potom Hodnota := -∞ jinak (
Je-li (Mantisa=0) potom (
Je-li (Báze>0) potom Hodnota := Hodnota - 2
Je-li (Báze<(2^ByteSize)-1) potom Hodnota := Hodnota - 2 jinak
Je-li (Báze>-(2^ByteSize)) potom Hodnota := Hodnota - 2
)
)
)`

### 1.8.7. Kódování UBRatio

Poslední ze zatím schválených typů je typ pro kódování reálných čísel v intervalu <0,1> s konečným dvojkovým rozvojem. Tato množina už je spočetně velká, a proto je možné ji zakódovat jednou hodnotou UBNumber. Hodnota je v podstatě ukládána do hodnot dělených do hloubky na poloviční intervaly. Tento typ je možné použít na ukládání reálných čísel pro jakékoliv konstatní intervaly jeho rovnoměrným rozprostřením. Stejně tak pro ukládání intenzity a jiných fyzikálních veličin.

### 1.8.7.1. Kódování s reverzí

Základní úvaha vycházela z toho, že bude nutné kódovat posloupnost čísel s postupně prostoucím rozvojem. První hodnoty musí být samozřejmě 0 a 1, dále je předpokládáno pořadí postupně na poloviny dělených zlomků bez opakování, tedy 1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8, 1/16, 3/16 atd. Nakonec však bylo požadováno pouze to, aby byly skupiny zlomků se stejným zalomením v pořadí za sebou a bez opakování a použito bylo přidání tečky za celé číslo a otočení pořadí bitů, takže místo do vyšších hodnot porostou do vyšší přesnosti. Tento algoritmus vyžaduje použití netriviální operace reverze pořadí bitů.

Příklad převodu
`0010111 =>(-1) 0010110 =>(reverse order) 0110100 =>("0." add) 0.0110100 =>(calculate) 0.25 + 0.125 + 0,03125 = 0,40625`

Uveďme si příklady několika prvních hodnot ve formátu UBRatio:

kód, binární tvar skutečné hodnoty, zlomkový tvar

      00000000  0                          = 0
      00000001  1                          = 1
      00000010  0.1                        = 1/2
      00000011  0.01                       = 1/4
      00000100  0.11                       = 3/4
      00000101  0.001                      = 1/8
      00000110  0.101                      = 5/8
      00000111  0.011                      = 3/8
      00001000  0.111                      = 7/8
      00001001  0.0001                     = 1/16
      00001010  0.1001                     = 9/16
      00001011  0.0101                     = 5/16
      ...

Dekódování hodnoty

`Přečti UBNatural Value
Je-li (Value<2) potom ( Hodnota := Value ) jinak (
Hodnota := 0
Value := Value - 1
Pomocná := 1
Dokud platí (Value>0) proveď (
pokud platí (Value and 1) potom Hodnota := Hodnota + 1/Pomocná
Pomocná := Pomocná shl 1
Value := Value shr 1
)
)`

Kódování hodnoty

`Je-li (Hodnota=0 nebo Hodnota=1) potom ( Value := Hodnota ) jinak (
Value := 0
Pomocná := 0
Dokud platí (Hodnota>0) proveď (
Hodnota := Hodnota * 2
Je-li (Hodnota > 1) potom (
Value := Value + Pomocná
Hodnota := Hodnota - 1
)
Pomocná := Pomocná shl 1
Value := Value + 1
)
)
Zapiš UBNatural Value`

### 1.8.7.2. Přímé kódování

K dispozici je naštěstí varianta bez operace reverze pořadím bitů, která používá prostý posun. Navíc je zde přirozenější pořadí hodnot zlomků.

Příklad převodu

`0010111 =>(-1) 0010110 =>(*2+1) 00101101 =>(shift)001.01101 =>(-1) 0.01101 =>(calculate) 0.25 + 0.125 + 0,03125 = 0,40625 = 13/32`

Příklady hodnot typu UBRatio

      00000000  0                          = 0
      00000001  1                          = 1
      00000010  0.1                        = 1/2
      00000011  0.01                       = 1/4
      00000100  0.11                       = 3/4
      00000101  0.001                      = 1/8
      00000110  0.011                      = 3/8
      00000111  0.101                      = 5/8
      00001000  0.111                      = 7/8
      00001001  0.0001                     = 1/16
      00001010  0.0011                     = 3/16
      00001011  0.0101                     = 5/16
      ...

Kódování hodnoty

`Value := Hodnota
Je-li not (Value=0 nebo Value=1) potom (
Value := Value + 1
Dokud platí (Value = Trunc(Value)) proveď ( Value := Value * 2)
Value := Trunc(Value/2) + 1
)
Zapiš UBNatural Value`

Dekódování hodnoty

`Value := Přečti UBNatural
Je-li (Value<2) potom ( Hodnota := Value ) jinak (
Hodnota := Value*2 - 1
Dokud platí (Hodnota>2) proveď ( Hodnota := Hodnota / 2 )
Hodnota := Hodnota - 1
)
)`

### 1.8.8. Další zvažovaná kódování

Kromě výše uvedených byly zvažovány ještě některé další kódování některých častěji používaných typů.

UBNReal - nezáporné reálné číslo - báze je interpretována jako UBENatural/UBNatural
UBCReal - celé číslo s přesností - mantisa je interpretována jako UBNatural
UBComplex - komplexní číslo - dvě reálná čísla
UBKvat - kvaternion - čtyři reálná čísla, ale žádné praktické využití
UBFrag - zlomky
UBBits - pole logických hodnot - číslo je interpretováno jako pole hodnot 0/1, mělo by možná smysl definovat, pokud by byl formát redundantní. Takto bude realizováno pomocí datového bloku.

Případná další kódování se budou oběvovat v dalších částech dokumentace.

### 1.9. Argumentace správnosti

Pokusme se nyní shrnout, proč je zvolené kódování UBNumber nejvhodnější (později snad budu schopen tyto argumenty reformulovat do nějaké formy důkazu).

- Umožňuje kódovat libovolně velké konečné celé i reálné číslo
- Je jednoznačně dekódovatelné (deterministické, blokové, prefixové)
- Je možné jej zarovnávat na bitové shluky
- Efektivita se asymptoticky blížící binárnímu kódování
- Je relativně dobře implementovatelné (nízká složitost konverzí)

Jelikož je možné posloupnost celých čísel zakódovat jako jediné celém číslo, bude vhodné dokázat, že taková to operace je nevhodná.

### 1.9.1. Otevřené otázky

Zvláště následující otázky dosud nebyly uspokojivě podloženy:

- Umístění konstant pro nekonečno - stále se nabízí varianta umístění konstant pro nekonečno v rozšířených typech na nulovou hodnotu. V tuto chvíli jsem dokonce této variantě více nakloněn.
- Použití rekurzivní varianty - Argument efektivity pro použití rekurze se nezdá být příliš silný. Nerekurzivní varianta má naopak výhody ve své jednoduchosti. Navíc kódování LRUB je složitější na korekci. Přesto se stále rekurze jeví být výhodná v účinnějším využití pro malé hodnoty ClusterSize.
- Kódování hodnoty UBReal - stále není zřejmé, zda je výhodnější dvou nebo jednohodnotová varianta tohoto kódování. Výhodou jednohodnotové je možnost použítí pouze jediného atributu, ale za cenu hůře analyzovatelného kódu, s nižší efektivitou extrakce.

### 2. Reference

Seznam zdrojů, literatury a relevantních odkazů.

Inverzní tvar [http://en.wikipedia.org/wiki/Ones%27_complement]
Dvojkový doplňkový tvar [http://en.wikipedia.org/wiki/Two%27s_complement]
RFC - Request For Comment [http://www.ietf.org/rfc.html]
MIME - Multipurpose Internet Mail Extensions [http://en.wikipedia.org/wiki/MIME]
UNICODE - Systém kódování znaků [http://www.unicode.org]
UCS - [http://www.unicode.org]
UTF - Unicode Transformation Format [http://www.unicode.org]
INTEL - Intel Corporation © [http://www.intel.com]
IEEE - Institute of Electrical and Electronics Engineers, Inc. [http://www.ieee.com]
IEEE - IEEE Standard for Binary Floating-Point Arithmetic (ANSI/IEEE Std 754-1985) [http://en.wikipedia.org/wiki/IEEE754]
ISO - International Standartization Organization [http://www.iso.ch]
ANSI - American National Standartization Organization [http://www.ansi.org]
Alpha Coding - Alpha Unary Number Coding [http://en.wikipedia.org/wiki/Unary_coding]
Beta Coding - Beta Binary Coding [http://en.wikipedia.org/wiki/Binary_number]
Gama Coding - Elias Gamma Number Coding [http://en.wikipedia.org/wiki/Elias_Gamma_coding]
Convergence - Mathematical Convergence [http://en.wikipedia.org/wiki/Convergence]
Limes Superior - Mathematical Limes Superior [http://www.math.uni-sb.de/~ag-wittstock/lehre/WS00/analysis1/Vorlesung/node62.html]
Binary XML - XML Binary Characterization [http://www.w3.org/XML/Binary/]

Homepage: http://xbup.sf.net
License: GNU Free Documentation License (FDL)
Latest update: 2007-07-07