• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Nierówność Krafta-McMillana

    Przeczytaj także...
    Warunek konieczny – wniosek wypływający z danego faktu. Jeżeli fakt ma zaistnieć, to zaistnieć (koniecznie) musi również fakt będący wnioskiem.Nierówność to, w uproszczeniu, stwierdzenie że jeden obiekt jest większy od drugiego, czyli dwa wyrażenia połączone relacją porządkującą:
    Kod prefiksowy lub przedrostkowy, także bezprefiksowy (ang. prefix code) – kod, w którym żadne ze słów kodowych nie jest przedrostkiem innego słowa; taki kod jest jednoznacznie dekodowalny. Dodatkowo każdy kod prefiksowy można reprezentować w formie drzew (dla kodów dwójkowych drzewo binarne).

    Nierówność Krafta-McMillana jest warunkiem koniecznym, który musi spełniać kod, aby był jednoznacznie dekodowalny. Dodatkowo jest to warunek konieczny, ale nie wystarczający, aby kod był dekodowalny bez opóźnień; tak więc istnieją kody które spełniają tą nierówność, lecz nie są jednoznacznie dekodowalne bez opóźnienia (są jednoznacznie dekodowalne, ale z opóźnieniami).

    Dwójkowy system liczbowy, system binarny, bin – pozycyjny system liczbowy, w którym podstawą jest liczba 2. Do zapisu liczb potrzebne są tylko dwie cyfry: 0 i 1.Przedrostek, prefiks – w językoznawstwie jest to fragment wyrazu (tzw. morfem) dodawany po lewej stronie do słowa podstawowego lub jego rdzenia (czyli do podstawy słowotwórczej), służący tworzeniu wyrazów pochodnych. Wyraz może nie posiadać żadnego prefiksu, może posiadać jeden lub więcej prefiksów.
    ,

    gdzie: r – wartościowość kodu (np. dla kodu trenrnego r=3), K – liczba sygnałów elementarnych, li – długość i-tego sygnału elementarnego.

    Warunek wystarczający (inaczej warunek dostateczny) – każdy warunek, z którego dany fakt wynika. Jeżeli warunek wystarczający zachodzi (wystarczy, by zachodził), wówczas zachodzi dany fakt.Kod (łac. codex – spis) – ciąg składników sygnału (kombinacji sygnałów elementarnych, np. kropek i kresek, impulsów prądu, symboli) oraz reguła ich przyporządkowania składnikom wiadomości (np. znakom pisma). W niektórych zastosowaniach, głównie przy przesyłaniu informacji podlegających utajnieniu, zwany jest szyfrem. Kody są stosowane m.in. w telegrafii, w technice cyfrowej.

    Przykład[]

    W tym przypadku dla wszystkich kodów r=2, gdyż zastosowano wszędzie kod binarny, natomiast K=4, gdyż kody mają czteroelementowy alfabet wiadomość a1, a2, a3, a4. Obliczając lewą stronę nierówności dla kodu , otrzymuje się 1, więc nierówność jest spełniona. Dodatkowo widać, że ma on wszystkie ciągi kodowe o stałej długości i do tego każdy z nich jest inny. Na tej podstawie wnioskuje się, że jest to kod jednoznacznie dekodowalny, bez opóźnienia.

    Teoria informacji – dyscyplina zajmująca się problematyką informacji oraz metodami przetwarzania informacji, np. w celu transmisji lub kompresji. Naukowo teoria informacji jest blisko powiązana z matematyką dyskretną, a z jej osiągnięć czerpią takie dyscypliny jak informatyka i telekomunikacja.

    Dla kodu lewa strona wynosi 1, więc ponownie spełniona jest nierówność Krafta-McMillana, lecz widać, że czwarte słowo kodowe jest przedrostkiem słowa trzeciego, co eliminuje go z tych rozważań.

    Natomiast dla kodu lewa strona wynosi 9/8, czyli nierówność nie jest spełniona, można więc bezwzględnie określić, że nie jest to kod jednoznacznie dekodowalny bez opóźnienia.

    Zobacz też[]

  • kod prefiksowy
  • teoria informacji
  • teoria kodów



  • w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.024 sek.