care codifică inegale, - reprezentarea informațiilor într-un format standard, cu un roi elementar unități sintactice limba de afișare (literele alfabetului limbii) sunt secvențial mapate la codewords unui anumit alfabet predeterminat cerned caractere (aici a însemnat informații de înregistrare litere liniare). Un exemplu de C. a. poate servi ca un bine-cunoscut codul Morse, într-un cod de rom cuvinte literă cu literă, iar scrisoarea de cuvinte potrivite în alfabetul unde trei personaje - un spațiu.
Principalele rezultate cu caracter general poate fi formulată pentru cazul unei scrisori prin scrisoarea K. (Atunci când aparatul de codificare are o stare internă), generalizări ca bine-cunoscute nu au nici o importanță fundamentală, și de cercetare legate de alte modele, nu au primit încă teoretice semnificative. de dezvoltare. Considerăm următorul model al canalului de comunicare:
A = 1. și n> - .. canal de comunicare alfabet, adică o listă a semnalelor la- pot fi transmise prin canalul, t (a i) și -Duration semnal i. B = 1. b r> - alfabet limbă de afișare. În cel mai simplu caz, sursa de mesaj este un sistem de probabilistic. la ieșire la roiul în fiecare punct de timp discret apare într-una din literele, iar probabilitatea Pi = p (bi) apariția literelor nu depind de timp. Schema f arată literele de codificare BB a A * (A * - monoid generate de A), f (bi) = vi și cuvintele sunt codificate litera cu litera B *: f = F (BI1) (BI1 bik.). f (BIK). Astfel, maparea f este complet determinat de codul V = v1. . vm>. Dacă f este de unu la unu, sarcina circuitele de decodare - pentru a restabili mesajul transmis, de punere în aplicare o mapare f -1.
Modelele estimate sunt factori pentru rata de transmitere de informații și complexitatea de decodare este determinată de alegerea ratei de transmisie de cod V. se caracterizează cantitativ valoare matematică. timp de așteptare, pentru a-Roe este obligat să transmită o singură literă a mesajului: scrisorile de durata de transmisie a bi
(E f este numit. De asemenea, în valoare de codificare f). In general, E f este dependentă de structura de cod a cerului descris polinomială structural
- generatoare de funcții, care enumeră cuvintele cod în funcție de compoziția lor. În cazul special în care t (1) =. = T (și n) = t, t au. E. E f este determinat numai cuvânt cod cu spectru lungimi 1. l2 ,. 1 m), unde li - lungimea cuvântului vi. Pentru acest caz, problema optimă de selecție cod (.. Adică, minimizarea costului) pot fi rezolvate complet; Este dovedit [2] o condiție necesară și suficientă pentru existența spectrale decodificat în mod unic cod
Rezultate [4], care, împreună cu (1) condiția
Este necesară și suficientă pentru existența unui cod de spectru dat având așa-numitul. proprietate de auto-sincronizare, pentru a-Roe este faptul că eroarea de decodare este localizată în mod automat, cu probabilitate 1.
Pentru decodarea complexitate, din punct de vedere abstract, cea mai interesantă măsură calitativă: proprietăți de prezență creangă întârziere de decodare, ceea ce înseamnă posibilitatea de punere în aplicare a mașinii de stat de decodare (cantitative de circuit de evaluare a automatelor de implementare complexitate se extind dincolo de teoria de codificare). Așa-numitul. Codurile prefix (prefix proprietate este faptul că nici un cuvânt VNE este segmentul inițial al celelalte cuvinte ale V) toate au această proprietate. Sa arătat în [2] că orice cod pentru la- f bijectivă spectrally echivalent cu codul de prefix gât-rom. Clasa prefix coduri previzibil relativ bine, ceea ce explică eficacitatea studii de caz t (1) =. = T (a n).
În general cunoscute algoritmică. Proprietăți de recunoaștere a aborda bijectivity de codificare și de întârziere de decodare membrelor. Proprietatea bijectivity f poate fi considerată ca un nivel minim de cod de performanță V. Există algoritmică. soluție de calcul a codului real capacitatea de corecție arbitrară, în general, și cu cerința suplimentară întârzierea de decodare finită. Clasa tuturor codurilor disponibile (de ex. E. decodificate) este unic aranjat foarte dificil, dar cerințele extreme ale codurilor adesea conduc la restricții semnificative. Ex. arată că includerea de cod maximă (pentru care inegalitatea (1) devine o egalitate și, care sunt numite. completă, deoarece pentru ei și numai pentru ei alfabetul canal este utilizat în întregime, în sensul că fiecare cuvânt al lui A * face parte din proprietatea mesajului) întârziere final codificat cerned-gât deține, dacă și numai în acest caz, în cazul în care codul de prefix.
Lit. [1] C. Shannon, Lucrări pe teoria și ciberneticii informații, trans. din limba engleză. M. 1963; [2] McMillan B. "Kibernetich. Proc.", 1961, în. 3, p. 88-92; [3] D. Xaffmen ibid. 79-87; [4] Schützenberger M. P. "Informare și control", 1967, v. 11, p. 396-401; [5] Markov A L. A. "Probleme. Cibernetică" 1962, c. 8, p. 169-86; 1964. 12, p. 137-53; 1967. 19, p. 307-09; 1976 în. 31, p. 77-108.
Enciclopedia de Matematică. - M. sovietic Enciclopedia. I. M. Vinogradov. 1977-1985.