În general, problema de codare poate fi reprezentat după cum urmează. Să două din alfabet A și B, constând dintr-un număr finit de caractere:
elemente ale alfabetului sunt numite litere. Ordonataın alfabetul este numit un cuvânt
în cazul în care. numărul n indică numărul de litere într-un cuvânt se numește lungimea cuvântului. notat cu n = l () = | |.
Cuvântul gol este notat cu:
a1 litere, numit începutul sau cuvinte prefixul. și litera o - end sau cuvinte postfix.
Cuvintele pot fi conectate. Pentru acest al doilea cuvânt prefix trebuie să urmeze imediat Postfix din prima, cu un cuvânt nou, în mod natural, își pierd statutul lor în cazul în care numai unul dintre cuvintele nu erau goale.
cuvinte compuse și notate. compus n cuvinte identice indicate. și.
Setul de toate cuvintele nevide în alfabetul A este notat A *:
Setul A este numit alfabetul mesajelor, și setul B - codificare alfabet. O mulțime de cuvinte compuse în alfabetul B, notată cu B *.
Fie F denota afișarea cuvintelor în alfabetul A la alfabetul B. Apoi, cuvântul este numit cuvinte cod.
metoda numita informație de afișare universală de codare în timpul sistemului de stocare, transmiterea și prelucrarea sub formă de corespondențelor între elementele de semnale de comunicații și prin intermediul cărora aceste elemente pot fi fixate. Astfel, codul - transformare în general lipsită de ambiguitate (adică funcția) mesaje de la o prezentare simbolică (sursă alfabet A) la altul (obiect alfabet B), de obicei, fără nici o pierdere de informație. Procesul de conversie F: A → B * * A cuvinte ale alfabetului sursei Vnazyvaetsya informații codificate în alfabetul.
Procesul de transformare inversă se numește cuvânt cu cuvânt de decodare. Astfel, decodarea - funcția inversă F, care F-1.
Deoarece pentru fiecare codare pentru a realiza decodarea operație, cartografierea trebuie să fie reversibil (bijectie).
Dacă | B | = m, atunci F este numit de ordinul m de codificare, cel mai frecvent caz de V - codarea binară. Acest caz este luat în considerare în viitor.
Dacă toate cuvintele de cod au aceeași lungime, este numit cod uniform, sau bloc.
Alfabetică (sau literă cu literă), puteți specifica tabelul de coduri de codificare. Codul sau funcția de codificare va servi ca o permutare. atunci
este indicată Această scrisoare de codificare scrisoare. O mulțime de coduri de litere se numește un set de coduri elementare. Alfabetică co-dirovanie poate fi folosit pentru orice set de mesaje. Astfel, codificarea alfabet este cea mai simplă, și este întotdeauna posibil pentru a introduce script-uri non-gol.
Să presupunem că alfabete
Apoi tabela de codificare poate fi de substituție:
Această codificare BCD, acesta este unul și, prin urmare, permite decodarea.
nu este unu-la-unu. De exemplu, un set de șase unități de 111111 pot corespunde cuvântului ca 333 și 77, precum și 111111, 137, 3311 sau 7111, plus orice permutare.
schema de codificare alfabetică numit prefix dacă elementar cod cu o singură literă este un prefix al unui alt cod de litere elementar.
schema de codificare alfabetice se numește separabil dacă orice cuvânt este alcătuit din cod elementar-ing este descompus în coduri elementare într-un mod unic.
schema de codificare alfabetice permite separabile de-codificare. Putem dovedi că schema de prefix este separabilă.
Pentru schema de codificare alfabetică a fost separabile, este necesar ca lungimile de cod elementare satisfac relația cunoscută sub numele de Macmillan inegalitate.