# XBUP - 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í SLRUB
1.1. Formalizace podmínek
2. Formalizace kódování
2.1. Kódování UBReal
3. Reference

### 1. Kódování SLRUB

Jako základní kódování přirozených čísel je v protokolu použito kódování SLRUB. Jde o variantu gama kódování, prozatím označováno jako rekurzivní unárně-binární kódování, které vzniklo aplikováním požadavků projektu na vlastnosti kódu. Vznik kódování je popsán v dokumentu kódování čísel. Rozšířením uvedené argumentace by mělo být možné formalizovat toto kódování jakožto nejvhodnější variantu reprezentace přirozených čísel.

### 1.1 Formalizace podmínek

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.
  To lze shrnout v následujícím tvrzení:
  Tvrzení: Univerzální protokol musí umožňovat kódování libovolně velkého konečného čísla
  Důkaz sporem: Předpokládejme, že formát umí kódovat číslo do maximální hodnoty n. Pak formát neumí zakódovat číslo n+1, a proto není univerzální. :-)
  Použití neomezeně velkých čísel je už implementováno v několika programovacích jazycích a jejich hlavní nevýhodou je větší náročnost výkon počítače, v běžných případech se však lze při zpracování protokolu omezit na standardní rozsahy hodnot. Ještě je vhodné zmínit, že nelze kódovat reálná čísla s nekonečným desetinným rozvojem, protože máme dostupný pouze konečný paměťový prostor. Tyto čísla je však možné realizovat algoritmicky, což však nespadá do základního kódování.
- Kódování do posloupnosti bitů
  Data jsou kódována do potenciálně nekonečné posloupnosti bitů. Posloupnost dvoustavový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í. To lze shrnout v následujícím tvrzení:
  Tvrzení: Kódování do posloupnosti bitů je dostačující a minimální
  Argumentace: Podle Churchovy teze je možné zakódovat libovolné data pomocí Turingova stroje. Ten je možné minimalizovat tak, že vstup je posloupnost dvoustavových hodnot (abeceda nad dvěma znaky).

### 2. Formalizace kódování

.

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

Je celkem snadné ukázat, že každé hodnotě s konečným dvojkovým rozvojem odpovídá právě jeden kód. Důkaz v opačném směru je obdobný.

Tvrzení: Každému číslu s konečným dvojkovým rozvojem odpovídá právě jeden kód v kódování UBReal. Tvrzení platí za předpokladu, že stejné tvrzení platí pro kódování UBInteger (bez uvedení důkazu)

Důkaz: (sporem) Předpokládejme, že danému číslu odpovídají dva rozdílné tvary v kódu UBReal. Pak se tyto kódy liší:
a) V hodnotě Base, nebo obou: Všechny bity hodnoty Value musejí být přítomny i v binárním kódu hodnoty Base. Pak z předpokladu, že kódování UBInteger splňuje stejnou podmínku plyne i rovnost kódu pro Base - spor
b) V hodnotě Mantisa: V binárním kódu je vždy posloupnost bitů hodnoty Value zakončena bitem 1 (neviditelná jednička) a všechny nižší bity mají hodnodu 0. Pokud vezmeme hodnotu s menším číslem Mantisa, pak se bit na pozici zakončovacího bitu této hodnoty liší v obou vstupních číslech - spor.

### 3. Reference

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

Churchova teze - Church Thesis http://en.wikipedia.org/wiki/Church_thesis]
Turingův stroj - Turing Machine [http://en.wikipedia.org/wiki/Turing_machine]

Homepage: http://xbup.sf.net
License: GNU Free Documentation License (FDL)
Latest update: 2008-11-09