Unicitatea decodare poate fi realizată fără introducerea delimitator în cazul în care codul de construcție, astfel încât acesta îndeplinește condiția, cunoscut sub numele de „proprietate prefixul“. Acesta se află în faptul că nici o combinație de mai multe ori codul nu trebuie să coincidă cu începutul ( „prefixul“) al unui alt cuvânt de cod. Codurile care satisfac această condiție sunt numite coduri prefix. Aceste coduri oferă decodare fără echivoc a cuvintelor de cod primite fără a introduce informații suplimentare pentru separarea lor, adică. E. Fiecare secvență de simboluri de cod trebuie să fie împărțită în mod unic în codewords. Codurile în care această cerință este fezabilă, numit în mod unic decoda sau codurile fără virgulă.
În cazul în care codul este prefixul, apoi citind secvența primită într-un rând de la început până la sfârșit, puteți seta în cazul în care se termină un singur cuvânt cod și începe următorul. De exemplu, dacă codul de prefix și o secvență de cod întâlnit 110, este evident că acest cod nu trebuie să conțină cuvinte (1) la (11). Codul de prefix este codat cu a1 = (00), a2 = (01) = a3 (101), a4 = (100). Fig. 1 este un grafic (cod arbore) cu codul soobscheniema1 prefix = (0) a2 = (1) = a3 (11), a4 = (111). Fig. 1, rezultă că în cazul în care proprietatea de prefix nu este îndeplinită, atunci o parte din partea de sus a arborelui intermediar poate corespunde cu codul de cuvinte.
Fig. Codul neprefiksnogo cuvânt cheie
Exemple de coduri prefix sunt codurile Shannon-Fano și Huffman. cod Shannon-Fano
posturi sursă alfabet evacuate în ordinea probabilității de apariție a acestora descrescătoare. Apoi, împărțiți-le în două părți, astfel încât probabilitatea cumulativă de posturi în fiecare dintre aceste piese au fost aproape identice cu putință. VWN a raportat prima parte, primul caracter - 0, iar al doilea - 1 (poate fi vice-versa). Apoi, fiecare din aceste piese (atunci când conține mai mult de un mesaj) este împărțit în două părți cât mai mare echiprobabile, și ca al doilea caracter pentru primul dintre ele ia 0, iar al doilea - 1. Acest proces se repetă până când fiecare dintre părți nu este a lăsat un mesaj.
Fig. Codul copac Shannon - Fano
Metoda Shannon - Fano nu conduce întotdeauna la un cod unic de-Niju construcția, deoarece partiția de pe o parte poate fi făcută mai mare de ambele porțiuni superioară și inferioară Vero yatnosti. În plus, tehnica nu SECU-Chiva găsirea setului optim de codewords pentru codarea pluralitatea de mesaje. (Optimul se înțelege că nici o altă pluralitate decodificat în mod unic de codewords are o lungime medie mai mică decât nume de cod set predeterminat.) Metoda Huffman constructivă propusă este liberă de deficiențele constatate-TION.
codul Huffman
Litere ale alfabetului mesajele sunt descărcate în coloana principală tabelă de codificare, în ordinea descrescătoare a probabilității. Ultimele două litere sunt combinate într-un singur sub-literă, care este creditat cu probabilitatea totală. Probabilitatea de scrisori, nu a participat la unirea, iar cuvintele care rezultă suma de probabilitate sunt aranjate în ordinea descrescătoare a probabilității într-o coloană suplimentară, iar ultimele două sunt combinate. Procesul continuă până, până când se obține o singură pornire auxiliară cu unitatea de probabilitate.
Pentru a găsi cuvântul de cod este necesar pentru a urmări semnul calea de tranziție în rânduri și coloane din tabel. Acest lucru este cel mai clar fezabil pentru arborele de cod. Din punct, respectiv probabilitatea stvuyuschey 1-a transmis două ramuri, în care ramurile sunt mai susceptibile de a atribui un simbol 1, și într-o mai mică - 0. O astfel de ramificare-ing secvență continuă până când, până când vom ajunge la probabilitatea litere kazh-Doi. Mergând prin arborele de cod din partea de sus în jos, puteți înregistra pentru fiecare mesaj care îi corespunde codewords.
Fig. Cod copac cod Huffman