Kraftas nilīgibi

Kraftas nilīgibi (Kraftas-McMillanas nilīgibi) - nilīgibi:

$\sum _{i}p^{-n_{i}}\leq 1$,

kwēi $n_{i}$ ast $i$-tas wāngiskas wīrsas gillisku en $p$-āriskasmu garrin. Tūls, per eraīnan senrīnksenin stēisan gīrbin $\{n_{1},\dots ,n_{N}\}$ sātwintan Kraftas nilīgibin ast mazīngi teīktun stawīdan $p$-āriskan garrin, kāi šai gīrbjai ast tenēisan wāngiskan wīrsun gilliskwas.

Nilīgibi mazzi būtwei ainawīdai iztarītan en billai stēisan kōdan: Ik $\{n_{1},\dots ,n_{N}\}$ ast ilgāi stēisan wīrdan en prefiksiskas kōds kīrsa $p$-elamēntin alfabētan, staddan tenēi sātwina Kraftas nilīgibin. Ik Kraftas nilīgibi ast sātwintan pēr ainuntan senrīnksenin stēisan gīrbin $\{n_{1},\dots ,n_{N}\}$, staddan ast mazīngi teīktun prefiksiskan kōdan kīrsa $p$-elamēntin alfabētan, per kawīdan šai gīrbjai ast ilgāi stēisan wīrdan.

Nilīgibi pastāi padrūktintan en 1949 m. ezze L.G. Kraftan. En 1956 m. B.McMillan ast padrūktinuns šan nilīgibin en spārtaišai fōrmulisnan - tenā ast sātwintan ni tēr per prefiksiskans kōdans, adder dīgi per ainazentliskai dekōdaminans kōdans.

Padrūktinsenis

Padrūktinsenis per $p$-āriskans garrins.

Per dātan $p$-āriskan garrin, etrīnkimai gīrbin $N$ mūiseskan adder līgu wisēimans gilliskwans stēisan wāngiskan wīrsun. En eraīnasmu wāngiskan wīrsun sen gilliskwan mazzan nikāi $N$ preidāimai pilnan $p$-āriskan garrin. Iz $i$-tan wāngiskan wīrsun sen gilliskwan $n_{i}$ en ōriginālasmu garrin turrimai en nawwasmu garrin $p^{N-n_{i}}$ wāngiskans wīrsuns. Garrin, kawīdan asmai zēidusis turri $\sum _{i}p^{N-n_{i}}$ wāngiskans wīrsuns be turri gilliskwan $N$, tītan tennan ni mazzi tūritun tūls nikāi $p^{N}$ wāngiskans wīrsuns $\square$

En āntran pāusan, padrūktinimai kāi Kraftas nilīgibi ast sātwintan per gīrbins $\{n_{1},\dots ,n_{N}\}$. Peisāimai nilīgibin sen summan praēntin wissans gilliskwas wērtibins:

$\sum _{j}k_{j}p^{-m_{j}}\leq 1$,

kwēi $k_{j}$ ast $j$-tas gilliskwas wārstisku. Nilīgibi ast dīgi arwi, ik immimai tennan tēr per pirmans $n$ gilliskwans:

$\sum _{j\leq n}k_{j}p^{-m_{j}}\leq 1$.

Iz šan reducītan nilīgibin mazzimai izwestun nilīgibin per $k_{n}$:

$k_{n}\leq p^{m_{n}-m_{n-1}}(p^{m_{n-1}}(1-\sum _{i<n-1}k_{i}p^{-m_{i}})-k_{n-1})$,

tītat ik $k_{n-1}<f(n-1)$, staddan $k_{n}\geq 0$ be $k_{n}<f(n)$, per rekursīskai definītan funkciōnin:

$f(n)=p^{m_{n}-m_{n-1}}(f(n-1)-k_{j}),f(1)=p^{m_{1}}$.

Asmai padrūktinusis, kāi $\forall n>0\ k_{n}>f(n)$. Teinū sūit pazinātun, kāi funkciōni $f(n)$ pertreppa gīrbin stēisan wīrsun en gilliskwai $m_{n}$ $\square$