Prefiksiniai kodai ir Krafto–McMillano nelygybė
Dvejetainiame prefiksiniame kode nė vienas visas kodinis žodis nėra kito kodinio žodžio pradinis segmentas, todėl galima iš karto nuosekliai dekoduoti.
Esminės žinios
Dvejetainiame prefiksiniame kode nė vienas visas kodinis žodis nėra kito kodinio žodžio pradinis segmentas, todėl galima iš karto nuosekliai dekoduoti. Vienareikšmiškai dekoduojamo kodo kodinių žodžių ilgiai tenkina Σ2⁻ˡⁱ≤1; ir atvirkščiai, teigiami sveikieji ilgiai, tenkinantys šią nelygybę, leidžia sudaryti prefiksinį kodą. Tikėtinas ilgis yra ne mažesnis už šaltinio entropiją.
Sąlygos ir taikymo ribos
- Baigtinė abėcėlė ir po vieną netuščią dvejetainį kodinį žodį kiekvienam simboliui, todėl kiekvienas ilgis yra teigiamas sveikasis skaičius. Vien iš tuščiojo žodžio sudarytas kodas neįtraukiamas: juo negalima vienareikšmiškai užkoduoti nežinomo skaičiaus pasikartojimų.
- Vien atskirų žodžių injektyvumas negarantuoja vienareikšmio jų sujungimo.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaita 5: Krafto–McMillano teorema, atvirkštinis teiginys ir vidutinio ilgio apatinis rėžis; sujungimų skaičiavimu grindžiamame įrodyme naudojami teigiami ilgiai.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaityti visi glaustai suformuluoti teiginiai (241), hipotezės, pateiktos lygtys ir susitarimai bei visos kilmės semantinės sąsajos (596); peržiūrėta visa autoriaus sudaryta 241 įrašo tikslių šaltinių patikros matrica ir deklaruoti apribojimai. Siekiant aprėpti visą įrašų rinkinį, perskaityti 105 ankstesni faktiškai paveldėti matematikos ir informacijos įrašai. Toliau išvardyti tikslingai ir nepriklausomai peržiūrėti pirminių šaltinių skyriai; tuo NETEIGIAMA, kad kiekvieno cituojamo šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atlikta informacinio turinio peržiūra, o ne žmogaus eksperto patvirtinimas atitinkamoje mokslo srityje, išsamus vadovėlio atkūrimas ar eksperimentinis pakartojimas. Peržiūros įrašas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-prefix-kraft-codes
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra