Kraftas nilīgibi

Iz Prūsiska Wikipēdija
Sākais en: nawigaciōni, laukīsna

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

\sum_i p^{-n_i} \le 1,

kwēi ni 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 ni 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 pN 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} \le 1,

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

\sum_{j\le n} k_j p^{-m_j} \le 1.

Iz šan reducītan nilīgibin mazzimai izwestun nilīgibin per kn:

k_n \le 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 kn − 1 < f(n − 1), staddan k_n \ge 0 be kn < 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 mn \square

En kitēimans billins
Persōniskas pagaptis