DFWLD
Dyadic fraction with least denominator (zkráceně DFWLD) je druhem aritmetického kódu, který je bezeztrátový nultého řádu.
Kódování
Pro zdrojovou abecedu \(A = \left(\begin{array}{cccccc}a & b & c & \ldots \\ p_1 & p_2 & p_3 & \ldots \end{array}\right)\), kde první řádek jsou znaky zdrojové abecedy a druhý řádek jsou pravděpodobnosti znaků kódujeme pomocí DFWLD následujícím způsobem:
- Spočítáme si kumulativní pravděpodobnosti znaků - Předpokládáme, že zdrojová abeceda je seřazena od nejvyšší pravděpodobnosti po tu nejmenší. Pak kumulativní pravděpodobnost \(C(x)\) počítáme jako ostře menší, takže se pravděpodobnost toho konkrétního znaku nepočítá.
- Pro každý znak slova spočítáme novou dolní a horní mez
- dolní mez \(a_i = a_{i-1} + l_{i-1} \cdot C(p_i)\)
- délka intervalu \(l_i = l_{i-1} \cdot p_{i}\)
- Určení parametru \(t \in \mathbb{N}^+\) - Ten spočítáme z nerovnice \(t \ge \left\lceil-\frac{\ln{l_n}}{\ln{2}}\right\rceil \gt -t + 1\)
- Určení parametru \(s \in \mathbb{N}\) - Ten spočítáme z nerovnice \(a_n \cdot 2^t \le s \lt (a_n + l_n) \cdot 2^t\). V případě, že nám výjdou dva výsledky, volíme ten sudý.
- Sestavení dyadického zlomku \(R = \frac{s}{2^t}\)
- Zakódování do binární podoby - Výsledné číslo bude mít \(t\) znaků. Pokud má číslo méně bitů než \(t\), tak se doplní nulami zleva.