Teorema Shannon directă pentru o sursă de formă generală. Teoreme de codare de bază

Codificarea informațiilor

Noțiuni de bază

Teoremele lui Shannon privind codificarea mesajelor au fost menționate mai sus. Este intuitiv clar că codificarea este operația de conversie a informațiilor în forma necesară procesării ulterioare (transmitere printr-un canal de comunicare, stocare în memorie sistem de calcul, utilizarea pentru luarea deciziilor etc.). De asemenea, este clar că la construirea oricăruia Sistem informatic Este imposibil să faci fără codificare: orice prezentare de informație implică utilizarea unui fel de coduri. Prin urmare, vom analiza în continuare în detaliu baza teoretica codificarea informațiilor.

Lăsa A– alfabet arbitrar. Elemente alfabetice A sunt numite litere (sau simboluri), iar secvențele finite formate din litere sunt numite cuvinte în A. Se crede că în orice alfabet există un cuvânt gol care nu conține litere.

Cuvânt α 1 se numește începutul (prefixul) unui cuvânt α , dacă cuvântul există α 2, astfel încât α = α 1 α 2; în acelaşi timp cuvântul α 1 se numește începutul propriu al unui cuvânt α , Dacă α 2 nu este un cuvânt gol. Lungimea cuvântului este numărul de litere din cuvânt (un cuvânt gol are lungimea 0). Record α 1 α 2 denotă legătura (concatenarea) cuvintelor α 1 și α 2. Cuvânt α 2 se numește terminația (sufixul) unui cuvânt α , dacă cuvântul există α 1, astfel încât α = α 1 α 2; în acelaşi timp cuvântul α 2 se numește finalul propriu al unui cuvânt α , Dacă α 1 nu este un cuvânt gol. Un cuvânt gol este, prin definiție, considerat începutul și sfârșitul oricărui cuvânt α .

Luați în considerare alfabetul B = {0, 1, …, D– 1), unde D≥ 2 și o mulțime arbitrară C. Afișarea arbitrară a unui set Cîn multe cuvinte din alfabet B numit D-ar set codificare C(la D= 2 codificarea va fi binară). Maparea inversă se numește decodare. Să dăm exemple de codificări.

1. Codificarea mulţimii numerelor naturale, în care numărul n= 0 se potrivește cu cuvântul e(0) = 0 și numărul n ≥ 1 cuvânt binar

e(n) = b 1 b 2 … b l (n)

cea mai mică lungime care satisface condiția

Este evident că b 1 = 1, 2l (n) – 1 ≤ n < 2l (n) prin urmare

l(n) = + 1 = ]log( n + 1)[,

Unde [ X] Și ] X[ indică cel mai mare număr întreg care nu depășește X, iar cel mai mic număr întreg mai mare decât X. Cuvânt e(n) se numește notația binară a unui număr n, iar această codificare este reprezentarea numerelor în sistem binar Socoteala Această codificare este unu-la-unu pentru că când n 1 ≠ n 2 cuvinte e(n 1) și e(n 2) sunt diferite. Tabelul 5.1 arată reprezentarea primelor 16 numere naturale din sistemul numeric binar.

Tabelul 5.1

Codificare e(n)

n	e(n)	n	e(n)	n	e(n)	n	e(n)

2. Codificarea primelor 2 k numere naturale, pentru care fiecare număr n (0 ≤ n < 2k) se potrivește cu cuvântul

e k(n) = 0k – l (n) e(n),

unde intrarea 0 k – l (n) denotă un cuvânt format din k – l(n) zerouri, e(n) – reprezentarea unui număr nîn sistemul de numere binar discutat mai sus. Această codificare este pentru primele 16 numere naturale ( k= 4) este dat în tabelul 5.2.

Tabelul 5.2

Codificare e k(n)

n	e k(n)	n	e k(n)	n	e k(n)	n	e k(n)

Lăsa A = {un i, i= 1, 2, ...) – un alfabet finit sau de numărare, ale cărui litere sunt numerotate numere naturale. În acest caz, codificarea literelor alfabetului A poate fi specificată prin succesiune D-cuvinte literale V = {v i, i= 1, 2, …), unde v i există o imagine a unei scrisori un i. Astfel de secvențe de cuvinte (din set V) se numesc coduri (ale alfabetului A). Dacă este dat codul V alfabet A, apoi codificarea cuvintelor, în care fiecare cuvânt un i 1 un i 2 …un ik se potrivește cu cuvântul v i 1 v i 2 …v ik, numită codificare literă cu literă.

Când treceți de la codificarea unu-la-unu a literelor alfabetului la codificarea literă cu literă a cuvintelor din alfabet, este posibil ca proprietatea unu-la-unu să nu fie păstrată. De exemplu, codificare e(n) nu salvează această proprietate, și codificare e k(n) îl salvează. Proprietatea unu-la-unu este păstrată prin coduri separabile. Cod V = {v i, i= 1, 2, …) se numește separabil dacă din fiecare egalitate a formei

v i 1 v i 2 …v ik = v j 1 v j 2 …vjl

urmează că l = kȘi v i 1 = v j 1 , v i 2 = v j 2 , … , v ik = vjl. Codurile separabile sunt numite și coduri unic decodabile.

Codurile de prefix aparțin clasei de coduri separabile. Cod V = {v i, i= 1, 2, …) se numește prefix dacă nu există un cuvânt vk nu este începutul (prefixul) niciunui cuvânt v l, l ≠ k. Dacă fiecare cuvânt al unui cod de prefix este înlocuit cu cel mai mic început, care nu este începutul altor cuvinte de cod, atunci codul rezultat va fi și un prefix. Această operație se numește trunchiere a codului de prefix.

Pentru cod arbitrar V, constând din cuvinte diferite, puteți construi un arbore de cod. Acesta este un grafic direcționat care nu conține cicluri, în care vârful β 1 conectat la partea de sus β 2 margine îndreptată din β 1 la β 2 dacă și numai dacă β 2 = β 1 b, Unde b Î B = {0, 1, …, D – 1}, D≥ 2. Pentru codurile de prefix (și numai pentru acestea), setul de cuvinte de cod coincide cu setul de vârfuri de sfârșit (vârfurile din care nu provin muchii) arborele de coduri.

Teoreme de codare de bază

Proprietăţile codurilor utile pentru acestea aplicație practică, sunt determinate de teoremele de codare de bază.

Teorema 5.1. Inegalitatea lui Kraft. Pentru existența unui cod unic decodabil (separabil) care conține N cuvinte de cod din set (0, 1, D– 1) cu lungimi n 1 , n 2 , …, n N, este necesar și suficient ca inegalitatea să se mențină

Dovada. Să ne imaginăm că avem un arbore de cod pentru un cod de prefix. Rădăcina arborelui de cod formează nivelul 0, vârfurile asociate cu forma rădăcină nivelul 1 etc. Numărul posibil de vârfuri per k-al-lea nivel îl notăm ca Dk. Fiecare vârf k nivelul apare exact Dn – k culmi n- al-lea nivel.

n 1 ≤ n 2 ≤…≤ n N = n.

Evident, cuvântul de cod al lungimii k interzice exact Dn – k posibile vârfuri de capăt (vârfurile ultimului nivel). Apoi toate cuvintele cod ale codului prefix interzic vârfurile de sfârșit. Deoarece numărul total vârfurile de capăt sunt egale Dn, atunci inegalitatea este adevărată

,

din care rezultă că

Astfel, inegalitatea lui Kraft este dovedită.

Ca rezultat al demonstrației teoremei 5.1, se ajunge la concluzia că există cel puțin coduri de prefix care sunt coduri unic decodabile cu lungimi de cuvinte de cod. n 1 , n 2 , …, n N, satisfăcând inegalitatea lui Kraft. Următoarea teoremă, numită afirmația lui McMillan, generalizează această concluzie pentru toate codurile unic decodabile.

Teorema 5.2. inegalitatea lui McMillan. Fiecare cod decodabil unic satisface inegalitatea lui Kraft.

Dovada. Să ridicăm suma la o putere L:

. (5.1)

Lăsa A k– numărul de combinaţii care conţin L cuvinte de cod cu lungime totală k. Atunci expresia (6.1) poate fi reprezentată ca

,

Unde L max – lungime maxima mesaje care conțin L cuvinte de cod. Dacă codul este unic decodabil, atunci toate secvențele de la L cuvinte cod de lungime totală k sunt diferite. Din moment ce există numai Dk secvențe posibile, atunci A k ≤ Dkși apoi

Deoarece L este numărul de cuvinte de cod independente care sunt folosite pentru a construi toate secvențele posibile de lungime care nu depășește L max. De aceea L ≤ L max si . Și de aici rezultă că

Deoarece raționamentul de mai sus este valabil pentru fiecare cod decodabil unic și nu doar pentru codurile de prefix, afirmația lui McMillan este dovedită.

Următoarele teoreme relaționează entropia unei surse de mesaj și lungimea medie cuvânt cod.

Teorema 5.3. Teorema codării sursei I. Pentru orice sursă discretă fără memorie X cu alfabet finit și entropie H(X) există D-ichny cod prefix, în care lungimea medie a cuvântului de cod satisface inegalitatea

. (5.2)

Dovada.În primul rând, să explicăm că o sursă discretă fără memorie este descrisă de un model care nu ține cont de conexiunile dintre simbolurile mesajelor. Acum demonstrăm partea stângă a inegalității (6.2):

Pentru a face acest lucru, folosim definiția entropiei și a inegalității lui Kraft:

Pentru a demonstra partea dreaptă a inegalității (6.2), rescriem inegalitatea lui Kraft în următoarea formă:

.

Apoi alegem pentru fiecare termen cel mai mic număr întreg n i, la care

Deoarece inegalitatea lui Kraft rămâne aceeași cu această alegere, putem construi codul de prefix corespunzător. Deoarece n i este cel mai mic număr întreg, atunci pentru n i– 1 este corect

Astfel, teorema de codificare a sursei I este demonstrată. Determină că lungimea medie a unui cuvânt cod nu poate fi mai mică decât entropia sursei mesajului. Rețineți că demonstrația teoremei a folosit aceeași notație ca atunci când ați luat în considerare inegalitatea lui Kraft.

Teorema 5.4. Teorema Codării Sursei II. Pentru lungimea blocului L există D-cod prefix-ary în care lungimea medie a unui cuvânt de cod pe caracter satisface inegalitatea

,

Unde .

Dovada. Aici, blocuri de personaje și H(X 1 , X 2 , …, X L) este entropia sursei mesajului pe bloc de L personaje. Pentru a demonstra teorema, puteți folosi teorema de codificare sursă I:

În plus, deoarece lungimea minimă realizabilă a unui cuvânt cod per simbol este valoarea , atunci când D= 2 redundanță de cod poate fi determinată prin formulă .

1 | |

Programul cursului

„Teoria informației și codării”

Prelegerile sunt susținute în anul 4, semestrul VII,

51 de ore, lector conf. univ

Conceptul de informație, entropie. Sisteme de comunicații. Surse discrete. Descrierea sursei folosind proces aleatoriu. Independenta statistica. surse Markov. Ergodicitatea. Ergodicitatea sursei Bernoulli.

Derivarea formulei entropiei (după Fadeev). Informații reciproce și proprietățile sale. Proprietățile entropiei. Teorema despre valoare maximă entropie. Entropia pe unitatea de timp a sursei mesajului.

Problema codificării unei surse discrete cu coduri lungime egală. Viteza de codare. Seturi de mare probabilitate. Teoreme directe și inverse pentru codificarea unei surse discrete cu coduri de lungime egală.

Problema codificării unei surse cu coduri de lungime inegală. Costul de codare. Coduri fără ambiguitate descifrabile. Coduri de prefix. Codare literă cu literă. O condiție necesară și suficientă pentru descifrabilitatea unică a unui cod. Codurile complete. Teoremă pentru codificarea unei surse discrete cu coduri de lungime inegală. Algoritmi pentru construirea codurilor optime (Fano, Shannon, Huffman). Construirea unui cod binar optim cu o distribuție de probabilitate egală a probabilităților de intrare. Aplicarea teoriei informațiilor are ca rezultat demonstrarea limitelor inferioare și superioare pentru complexitatea implementării Funcții booleeneîn unele clase de sisteme de control. O metodă pentru construirea unui cod optim cu condiția ca distribuția de probabilitate a literelor sursă să fie necunoscută. Teorema lui Markov privind descifrabilitatea unică a unui cod. Algoritmi adaptativi pentru compresia informatiilor.

Canal discret fără memorie. Binar canal simetric. Viteza de transmitere a informațiilor pe canal. Capacitatea canalului. Canalul extins și acesta debitului. Modele decisive și grupări de observații. Posibilitatea transmiterii eronate de informații. inegalitatea lui Feinstein. Teoremă directă pentru codificarea canalelor fără memorie. inegalitatea lui Fano. Teorema procesării informației. Inversarea teoremei de codificare.

Teoria codării rezistente la zgomot. Criteriul de maximă probabilitate. Distanța codului. Codurile de paritate. generativ și verificarea matricelor. Sindrom. Algoritm de decodare pentru codurile de verificare a parității. Codurile liniareși algoritmul lor de decodare. Hamming legat. Cod Hamming. Codurile ciclice. Codificarea și decodificarea codurilor ciclice.

LITERATURĂ

1. Gallagher R. Teoria informaţiei şi conexiune de încredere., M., Sov. Radio, 1979.

2. Krichevsky E. Prelegeri despre teorie și informație, Novosibirsk, NSU, 1966.

3. Kolesnik V., Poltyrev G. Curs de teoria informaţiei, Nauka, 1982.

4. Fainstein A. Fundamentals of Information Theory, M., IL, 1960.

5. Peterson V., Weldon F. Codurile de corectare a erorilor, M., Mir, 1976.

6. Teoria codificării algebrice Berlekamp, ​​M., Mir, 1971.

Lucrarea a fost adăugată pe site-ul site-ului: 2016-03-30

;color:#000000" xml:lang="ru-RU" lang="ru-RU">5. Codificarea informațiilor

;color:#000000" xml:lang="ru-RU" lang="ru-RU">5.1. Concepte de bază

Teoremele lui Shannon privind codificarea mesajelor au fost menționate mai sus. Este intuitiv clar că codificarea este operația de conversie a informațiilor în forma necesară procesării ulterioare (transmitere printr-un canal de comunicare, stocare în memoria unui sistem informatic, utilizare pentru luarea deciziilor etc.). De asemenea, este clar că atunci când se construiește orice sistem informațional este imposibil să se facă fără codificare: orice prezentare a informațiilor implică utilizarea unui fel de coduri. Prin urmare, în continuare vom analiza în detaliu fundamentele teoretice ale codificării informațiilor.

Fie A orice alfabet. Elemente alfabetice A sunt numite litere (sau simboluri), iar secvențele finite formate din litere sunt numite cuvinte în A . Se crede că în orice alfabet există un cuvânt gol care nu conține litere.

Cuvântul α 1 numit începutul (prefixul) unui cuvântα , dacă cuvântul existăα 2 astfel încât α = α 1 α 2 ; în acest caz, cuvântul α 1 numit începutul propriu al unui cuvântα dacă α 2 nu este un cuvânt gol. Lungimea cuvântului este numărul de litere din cuvânt (un cuvânt gol are lungimea 0). Recordα 1 α 2 denotă o legătură (concatenare) a cuvintelorα 1 și α 2. Cuvântul α 2 numită terminația (sufixul) unui cuvântα , dacă cuvântul există a 1 astfel încât a = a 1 a 2 ; în acest caz cuvântul α 2 numit sfârşitul propriu al unui cuvântα dacă α 1 nu este un cuvânt gol. Un cuvânt gol este, prin definiție, considerat începutul și sfârșitul oricărui cuvântα .

Luați în considerare alfabetul B = (0, 1, …, D 1), unde D ≥ 2 și o mulțime arbitrară C . Afișarea arbitrară a unui set C în multe cuvinte din alfabet B se numește D -ar set codificare C (la D = 2 codificarea va fi binară). Maparea inversă se numește decodare. Să dăm exemple de codificări.

1. Codificarea mulţimii numerelor naturale, în care numărul n = 0 se potrivește cu cuvântul e (0) = 0 și numărul n ≥ 1 cuvânt binar

e (n) = b 1 b 2 … b l (n)

cea mai mică lungime care satisface condiția

Este evident că b 1 = 1, 2 l (n) 1 ≤ n< 2 l (n ) prin urmare

l(n) = + 1 = ]log(n + 1)[,

unde [ x ] și ] x [ indică cel mai mare număr întreg care nu depășește X , iar cel mai mic număr întreg mai mare decât X. Cuvântul e(n ) se numește notația binară a unui număr n , iar această codificare este o reprezentare a numerelor în sistemul numeric binar. Această codificare este unu-la-unu pentru că când n 1 ≠ n 2 cuvinte e (n 1 ) și e (n 2 ) sunt diferite. Tabelul 5.1 arată reprezentarea primelor 16 numere naturale din sistemul numeric binar.

" xml:lang="ru-RU" lang="ru-RU">Tabelul 5.1

" xml:lang="ru-RU" lang="ru-RU"> Codificare" xml:lang="en-US" lang="en-US">e" xml:lang="ru-RU" lang="ru-RU">(" xml:lang="en-US" lang="en-US">n" xml:lang="ru-RU" lang="ru-RU">)

" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)
" xml:lang="en-US" lang="en-US">0	" xml:lang="en-US" lang="en-US">0	" xml:lang="en-US" lang="en-US">4	" xml:lang="en-US" lang="en-US">100	" xml:lang="en-US" lang="en-US">8	" xml:lang="en-US" lang="en-US">1000	" xml:lang="en-US" lang="en-US">12	" xml:lang="en-US" lang="en-US">1100
" xml:lang="en-US" lang="en-US">1	" xml:lang="en-US" lang="en-US">1	" xml:lang="en-US" lang="en-US">5	" xml:lang="en-US" lang="en-US">101	" xml:lang="en-US" lang="en-US">9	" xml:lang="en-US" lang="en-US">1001	" xml:lang="en-US" lang="en-US">13	" xml:lang="en-US" lang="en-US">1101
" xml:lang="en-US" lang="en-US">2	" xml:lang="en-US" lang="en-US">10	" xml:lang="en-US" lang="en-US">6	" xml:lang="en-US" lang="en-US">110	" xml:lang="en-US" lang="en-US">10	" xml:lang="en-US" lang="en-US">1010	" xml:lang="en-US" lang="en-US">14	" xml:lang="en-US" lang="en-US">1110
" xml:lang="en-US" lang="en-US">3	" xml:lang="en-US" lang="en-US">11	" xml:lang="en-US" lang="en-US">7	" xml:lang="en-US" lang="en-US">111	" xml:lang="en-US" lang="en-US">11	" xml:lang="en-US" lang="en-US">1011	" xml:lang="en-US" lang="en-US">15	" xml:lang="en-US" lang="en-US">1111

2. Codificarea primelor 2 k numere naturale, pentru care fiecare număr n (0 ≤ n< 2 k ) se potrivește cu cuvântul

e k (n) = 0 k l (n) e (n),

unde intrarea este 0 k l (n) înseamnă un cuvânt format din k l (n) zerouri, e (n ) reprezentarea numerelor n în sistemul de numere binar discutat mai sus. Această codificare este pentru primele 16 numere naturale ( k = 4) este dat în tabelul 5.2.

" xml:lang="ru-RU" lang="ru-RU">Tabelul 5." xml:lang="en-US" lang="en-US">2

" xml:lang="ru-RU" lang="ru-RU"> Codificare" xml:lang="en-US" lang="en-US">e;vertical-align:sub" xml:lang="en-US" lang="en-US">k" xml:lang="ru-RU" lang="ru-RU">(" xml:lang="en-US" lang="en-US">n" xml:lang="ru-RU" lang="ru-RU">)

" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e;vertical-align:sub" xml:lang="en-US" lang="en-US">k" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e;vertical-align:sub" xml:lang="en-US" lang="en-US">k" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e;vertical-align:sub" xml:lang="en-US" lang="en-US">k" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)	" xml:lang="en-US" lang="en-US">n	" xml:lang="en-US" lang="en-US">e;vertical-align:sub" xml:lang="en-US" lang="en-US">k" xml:lang="en-US" lang="en-US">(" xml:lang="en-US" lang="en-US">n" xml:lang="en-US" lang="en-US">)
" xml:lang="en-US" lang="en-US">0	" xml:lang="en-US" lang="en-US">0000	" xml:lang="en-US" lang="en-US">4	" xml:lang="en-US" lang="en-US">0100	" xml:lang="en-US" lang="en-US">8	" xml:lang="en-US" lang="en-US">1000	" xml:lang="en-US" lang="en-US">12	" xml:lang="en-US" lang="en-US">1100
" xml:lang="en-US" lang="en-US">1	" xml:lang="en-US" lang="en-US">0001	" xml:lang="en-US" lang="en-US">5	" xml:lang="en-US" lang="en-US">0101	" xml:lang="en-US" lang="en-US">9	" xml:lang="en-US" lang="en-US">1001	" xml:lang="en-US" lang="en-US">13	" xml:lang="en-US" lang="en-US">1101
" xml:lang="en-US" lang="en-US">2	" xml:lang="en-US" lang="en-US">0010	" xml:lang="en-US" lang="en-US">6	" xml:lang="en-US" lang="en-US">0110	" xml:lang="en-US" lang="en-US">10	" xml:lang="en-US" lang="en-US">1010	" xml:lang="en-US" lang="en-US">14	" xml:lang="en-US" lang="en-US">1110
" xml:lang="en-US" lang="en-US">3	" xml:lang="en-US" lang="en-US">0011	" xml:lang="en-US" lang="en-US">7	" xml:lang="en-US" lang="en-US">0111	" xml:lang="en-US" lang="en-US">11	" xml:lang="en-US" lang="en-US">1011	" xml:lang="en-US" lang="en-US">15	" xml:lang="en-US" lang="en-US">1111

Fie A = ( a i , i = 1, 2, ...) un alfabet finit sau numărabil, ale cărui litere sunt numerotate cu numere naturale. În acest caz, codificarea literelor alfabetului A poate fi specificată prin succesiune Cuvintele D-are V = (v i, i = 1, 2, …), unde v i există o imagine a unei scrisori un i . Astfel de secvențe de cuvinte (din set V ) se numesc coduri (ale alfabetului A ). Dacă este dat codul V al alfabetului A , apoi codificarea cuvintelor, în care fiecare cuvânt a i 1 a i 2 ... a ik se potrivește cu cuvântul v i 1 v i 2 … v ik , numită codificare literă cu literă.

Când treceți de la codificarea unu-la-unu a literelor alfabetului la codificarea literă cu literă a cuvintelor din alfabet, este posibil ca proprietatea unu-la-unu să nu fie păstrată. De exemplu, codificare e(n ) nu păstrează această proprietate, ci codificarea e k (n ) îl salvează. Proprietatea unu-la-unu este păstrată prin coduri separabile. Cod V = ( v i , i = 1, 2, …) se numește separabil dacă din fiecare egalitate a formei

v i 1 v i 2 … v ik = v j 1 v j 2 … v jl

rezultă că l = k și v i 1 = v j 1 , v i 2 = v j 2 , … , v ik = v jl . Codurile separabile sunt numite și coduri unic decodabile.

Codurile de prefix aparțin clasei de coduri separabile. Cod V = ( v i , i = 1, 2, …) se numește prefix dacă nu există un cuvânt vk nu este începutul (prefixul) niciunui cuvânt v l , l ≠ k . Dacă fiecare cuvânt al unui cod de prefix este înlocuit cu începutul său cel mai mic, care nu este începutul altor cuvinte de cod, atunci codul rezultat va fi, de asemenea, un prefix. Această operație se numește trunchiere a codului de prefix.

Pentru cod arbitrar V constând din cuvinte diferite, puteți construi un arbore de cod. Acesta este un grafic direcționat care nu conține cicluri, în care vârfulβ 1 conectat la vârfβ 2 marginea îndreptată departe deβ 1 până la β 2 , dacă și numai dacăβ 2 = β 1 b, unde b  B = (0, 1, …, D 1), D ≥ 2. Pentru codurile de prefix (și numai pentru acestea), setul de cuvinte de cod coincide cu setul de vârfuri terminale (vârfurile din care nu provin muchii) ale arborelui cod.

5.2. Teoreme de codare de bază

Proprietățile codurilor care sunt utile pentru aplicarea lor practică sunt determinate de teoremele de codare de bază.

Teorema 5.1. Inegalitatea lui Kraft.Pentru existența unui cod unic decodabil (separabil) care conține N cuvinte de cod din set (0, 1, D 1) cu lungimile n 1, n 2, …, n N , este necesar și suficient ca inegalitatea să se mențină

Dovada. Să ne imaginăm că avem un arbore de cod pentru un cod de prefix. Rădăcina arborelui de cod formează nivelul 0, vârfurile asociate cu forma rădăcină nivelul 1 etc. Numărul posibil de vârfuri per k -al-lea nivel îl notăm ca Dk. Fiecare vârf k nivelul apare exact D n k vârfuri ale nivelului al n-lea.

n 1 ≤ n 2 ≤…≤ n N = n .

Evident, cuvântul de cod al lungimii k interzice exact D n k posibile vârfuri de capăt (vârfurile ultimului nivel). Apoi toate cuvintele cod ale codului prefix interzic vârfurile de sfârșit. Deoarece numărul total de vârfuri de capăt este Dn , atunci inegalitatea este adevărată

din care rezultă că

Astfel, inegalitatea lui Kraft este dovedită.

Ca rezultat al demonstrației teoremei 5.1, se ajunge la concluzia că există cel puțin coduri de prefix care sunt coduri unic decodabile cu lungimi de cuvinte de cod. n 1, n 2, …, n N , satisfăcând inegalitatea lui Kraft. Următoarea teoremă, numită afirmația lui McMillan, generalizează această derivație la toate codurile decodabile în mod unic.

Teorema 5.2. inegalitatea lui McMillan.Fiecare cod decodabil unic satisface inegalitatea lui Kraft.

Dovada. Să ridicăm suma la o putere L:

. (5.1)

Fie A k număr de combinații care conțin L cuvinte de cod cu lungime totală k . Atunci expresia (6.1) poate fi reprezentată ca

unde Lmax lungimea maximă a unui mesaj care conține L cuvinte de cod. Dacă codul este unic decodabil, atunci toate secvențele de la L cuvinte cod de lungime totală k sunt diferite. Din moment ce există numai Dk secvențe posibile, atunci A k ≤ D k și apoi

Din moment ce L acesta este numărul de cuvinte de cod independente care sunt utilizate pentru a construi toate secvențele posibile de lungime care nu depășește Lmax. Prin urmare L ≤ L max Și. Și de aici rezultă că

Deoarece raționamentul de mai sus este valabil pentru fiecare cod decodabil unic și nu doar pentru codurile de prefix, afirmația lui McMillan este dovedită.

Următoarele teoreme relaționează entropia unei surse de mesaj și lungimea medie a unui cuvânt de cod.

Teorema 5.3. Teorema codării sursei eu. Pentru orice sursă discretă fără memorie X cu alfabet finit și entropie H(X) există D -cod prefix ary în care lungimea medie a cuvântului de cod satisface inegalitatea

. (5.2)

Dovada. În primul rând, să explicăm că o sursă discretă fără memorie este descrisă de un model care nu ține cont de conexiunile dintre simbolurile mesajelor. Acum demonstrăm partea stângă a inegalității (6.2):

Pentru a face acest lucru, folosim definiția entropiei și a inegalității lui Kraft:

Pentru a demonstra partea dreaptă a inegalității (6.2), rescriem inegalitatea lui Kraft în următoarea formă:

Apoi alegem pentru fiecare termen cel mai mic număr întreg n i , la care

Deoarece inegalitatea lui Kraft rămâne aceeași cu această alegere, putem construi codul de prefix corespunzător. Deoarece n i este cel mai mic număr întreg, atunci pentru n i 1 adevărat

Apoi

Astfel, teorema de codificare sursă eu dovedit. Determină că lungimea medie a unui cuvânt cod nu poate fi mai mică decât entropia sursei mesajului. Rețineți că demonstrația teoremei a folosit aceeași notație ca atunci când luați în considerare inegalitatea lui Kraft.

Teorema 5.4. Teorema codării sursei II. Pentru un bloc de lungime L există D -cod prefix-ary în care lungimea medie a unui cuvânt de cod pe caracter satisface inegalitatea

Unde.

Dovada. Aici, blocuri de personaje și H (X 1, X 2, …, X L ) este entropia sursei mesajului pe bloc de L personaje. Pentru a demonstra teorema, puteți folosi teorema de codificare sursă eu:

Teorema Codării Sursei II ne permite să afirmăm că există astfel de metode de codare pentru un mesaj suficient de lung încât lungimea medie a cuvântului de cod să poată fi făcută arbitrar aproape de valoare. Într-adevăr, când L  ∞, H L (X )  H , unde H entropia sursei mesajului pe caracter, următoarea inegalitate este adevărată:

, (5.3)

Unde. Aceasta poate fi interpretată și după cum urmează: pentru orice număr arbitrar micε , există o metodă de codificare a blocurilor care conțin simboluri în care inegalitatea (5.3) este valabilă pentru lungimea medie a cuvântului de cod per simbol.

În plus, deoarece lungimea minimă realizabilă a unui cuvânt de cod per simbol este valoarea, atunci când D = 2 redundanță de cod poate fi determinată prin formulă.

;color:#000000" xml:lang="ru-RU" lang="ru-RU">5.3. Codificare optimă

Problema construirii unui cod optim este de a găsi numere întregi pozitive n 1, n 2, …, n N , minimizând lungimea medie a cuvântului cod supus inegalității lui Kraft:

La construirea codurilor în cazul unui alfabet A = ( a i , i = 1, 2, …, N ) cu o distribuție de probabilitate cunoscută P = ( p i , i = 1, 2, …, N ) fără pierderea generalității putem presupune că literele alfabetului A sunt numerotate în ordinea descrescătoare a probabilităților lor, adică p 1 ≥ p 2 ≥ … ≥ p N . În plus, vom lua în considerare doar codurile binare.

Există două metode cunoscute (Fano și Shannon) pentru a construi coduri care sunt aproape de optim. Metoda lui Fano este următoarea. Lista de litere, ordonată în ordinea descrescătoare a probabilităților, este împărțită în două părți consecutive, astfel încât sumele probabilităților literelor incluse în ele să difere cât mai puțin una de cealaltă. Literelor din prima parte li se atribuie simbolul 0, iar literelor din a doua parte li se atribuie simbolul 1. Apoi, faceți același lucru cu fiecare dintre părțile rezultate, dacă conține, macar, două litere. Procesul continuă până când întreaga listă este împărțită în părți care conțin câte o literă fiecare. Fiecare literă este asociată cu o secvență de simboluri atribuite acelei litere ca rezultat al acestui proces. Este ușor de observat că codul rezultat este un cod prefix.

Metoda lui Shannon este aplicabilă numai atunci când toate probabilitățile sunt pozitive. Constă în faptul că scrisoarea un i , care are o probabilitate p i > 0, succesiunea de n i = ] log (1/ p i )[ primele cifre după punctul fracționar al descompunerii unui număr într-o fracție infinită (pentru a 1 presupunem că q 1 = 0). De cand l > k (datorită faptului că p l ≤ p k ) n l ≥ n k si atunci codul obtinut in acest fel este prefix. Pe baza codului de prefix obținut, se construiește un cod de prefix trunchiat, care este rezultatul codificării folosind metoda Shannon.

Să fie, de exemplu, un set de litere A = ( a 1 , a 2 , a 3 , a 4 , a 5 , a 6 , a 7 ) cu distribuție de probabilitate P = (0,2, 0,2, 0,19, 0,12, 0,11, 0,09, 0,09). Să codificăm literele folosind metoda Fano.

1. Să împărțim lista în două părți, astfel încât sumele probabilităților literelor incluse în ele să difere cât mai puțin una de cealaltă:

A1 = (a1, a2, a3), P1 = (0,2, 0,2, 0,19);

A 2 = (a 4, a 5, a 6, a 7), P 2 = (0,12, 0,11, 0,09, 0,09).

2. Să atribuim simbolul 0 literelor din prima parte și simbolul 1 literelor din a doua parte:

A1 = (a 1/0, a 2/0, a 3/0);

A 2 = (a 4 /1, a 5 /1, a 6 /1, a 7 /1).

3. Repetați succesiv actiuni specificate pentru fiecare parte separat. ÎN ca rezultat obținem:

A 1 1 = ( a 1 /00);

A 121 = (a 2/010);

A 122 = (a 3/011);

A 211 = (a 4/100);

A 212 = (a 5/101);

A 221 = (a 6/110);

A 222 = (a 7 /111).

Cuvintele cod obținute ca rezultat al codificării sunt date pentru fiecare literă din dreapta barei oblice. În acest caz, ordinea indicilor listelor rezultate cu o singură literă arată succesiunea de împărțire a listei originale de grupuri în părți.

Procesul de codificare folosind metoda Fano este prezentat convenabil sub forma unui tabel. Pentru exemplul luat în considerare, este prezentat în Tabelul 5.3.

" xml:lang="ru-RU" lang="ru-RU">Tabelul 5.3

" xml:lang="ru-RU" lang="ru-RU"> Codificare folosind metoda Fano

" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">0,20	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU"> 0	" xml:lang="ru-RU" lang="ru-RU"> 00
" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">2	" xml:lang="ru-RU" lang="ru-RU">0,20		" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU">010
" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">3	" xml:lang="ru-RU" lang="ru-RU">0,19			" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">011
" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">4	" xml:lang="ru-RU" lang="ru-RU">0.12	" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU">100
" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">5	" xml:lang="ru-RU" lang="ru-RU">0.11			" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">101
" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">6	" xml:lang="ru-RU" lang="ru-RU">0,09		" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">0	" xml:lang="ru-RU" lang="ru-RU">110
" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">7	" xml:lang="ru-RU" lang="ru-RU">0,09			" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="ru-RU" lang="ru-RU">111

Să determinăm lungimea medie a cuvântului de cod:

Acum să facem codificarea folosind metoda lui Shannon. Procesul de codificare este prezentat în Tabelul 5.4.

" xml:lang="ru-RU" lang="ru-RU">Tabelul 5.4

" xml:lang="ru-RU" lang="ru-RU"> Codificare folosind metoda Shannon

" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="en-US" lang="en-US">n;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="en-US" lang="en-US">q;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="ru-RU" lang="ru-RU">Cod" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="en-US" lang="en-US">i	" xml:lang="ru-RU" lang="ru-RU">Cod trunchiat" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="en-US" lang="en-US">i
" xml:lang="en-US" lang="en-US">a;vertical-align:sub" xml:lang="ru-RU" lang="ru-RU">1	" xml:lang="en-US" lang="en-US">]2.321…[ = 3	" xml:lang="en-US" lang="en-US">0	000	000
a2	]2.321…[ = 3	0.2	001	001
a3	]2.395…[ = 3	0.4	011	01
a4	]3.058…[ = 4	0,59	1001	100
a5	]3.183…[ = 4	0,71	1011	101
a6	]3.472…[ = 4	0,82	1101	110
a7	]3.472…[ = 4	0,91	1110	111

Ca și în cazul precedent, găsim lungimea medie a cuvântului de cod:

.

După cum puteți vedea, rezultatele codificării folosind metodele Fano și Shannon în ceea ce privește minimizarea lungimii medii a codului au coincis practic. Prin urmare, aceste metode sunt adesea considerate ca una (în formularea lui Fano) și numite metoda Shannon-Fano.

În 1952, David Huffman a propus o metodă optimă de codificare a prefixelor pentru surse discrete, care, spre deosebire de metodele lui Shannon și Fano, este încă folosită în practică. D. Huffman a demonstrat că lungimea medie a unui cuvânt cod obținut folosind metoda sa va fi minimă. Codarea Huffman se face în trei pași.

1. Ordonare: literele sunt aranjate în ordinea descrescătoare a probabilităţilor lor.

2. Reducere: două litere cu cele mai mici probabilități sunt combinate într-una cu probabilitate totală; lista de litere este reordonată conform pasului 1; procesul continuă până când toate literele sunt combinate într-una singură. În acest caz, este posibil să se realizeze egalizarea lungimilor cuvintelor cod folosind următoarea strategie: dacă mai multe litere au aceleași probabilități, atunci acele două dintre ele care anterior aveau cel mai mic număr de combinații sunt combinate (deși acest lucru nu va afecta lungimea medie a codului).

3. Codificare: pornind de la ultima combinație, simbolul 0 este alocat succesiv unei componente a literei compuse, iar simbolul 1 celui de-al doilea; procesul continuă până când toate literele originale au fost codificate.

Să executăm codificare folosind metoda Huffman pentru setul considerat în exemplele de utilizare a metodelor Fano și Shannon.

1. Lista inițială de litereA = { A1 , A2 , A3 , A4 , A5 , A6 , A7 ) este deja comandat, din moment ceP = {0.2, 0.2, 0.19, 0.12, 0.11, 0.09, 0.09}.

2. Să combinăm litereleA6 ȘiA7 într-o singură scrisoareA1 cu probabilitate0.18 Șireordoneazălistă:

P1 = {0.2, 0.2, 0.19, 0.18, 0.12, 0.11}, A1 = { A1 , A2 , A3 , A1 , A4 , A5 }.

3. Repetați pasul 2 până când rămâne o literă în listă:

P2 = {0.23, 0.2, 0.2, 0.19, 0.18}, A2 = { A2 , A1 , A2 , A3 , A1 };

P3 = {0.37, 0.23, 0.2, 0.2}, A3 = { A3 , A2 , A1 , A2 };

P4 = {0.4, 0.37, 0.23}, A4 = { A4 , A3 , A2 };

P5 = {0.6, 0.4}, A5 = { A5 , A4 };

P6 = {1}, A6 = { A6 }.

4. Să ne potrivimbinarcodurisimboluri:

A6 : A5 = 0, A4 = 1;

A5 : A3 = 00, A2 = 01;

A4 : A1 = 10, A2 = 11;

A3 : A3 = 000, A1 = 001;

A2 : A4 = 010, A5 = 011;

A1 : A6 = 0010, A7 = 0011.

Astfel, următoarele coduri binare sunt atribuite literelor inițiale:A1 = 10, A2 = 11, A3 = 000, A4 = 010, A5 = 011, A6 = 0010, A7 = 0011, ceea ce oferă o lungime medie a codului care este mai mică decât în ​​cazul codării Fano și Shannon.

Să determinăm redundanța codurilor primite. Pentru a face acest lucru, să găsim entropia sursei mesajului:

.

Atunci codurile au următoarea redundanță:

Cod Fano: ;

Cod Shannon: ;

Cod Huffman: .

Astfel, redundanța codului Huffman este minimă.

Pentru a reduce redundanța, de ex. Pentru a reduce lungimea medie a unui cuvânt de cod cu un simbol, puteți utiliza codarea în bloc, a cărei justificare este dată în teorema de codare sursă.II. În acest caz, este necesar să obțineți toate grupurile posibile de litere lungimea dată, găsiți probabilitățile grupurilor ca probabilitățile ca literele grupului să apară împreună în același timp și efectuați codificarea, tratând grupurile ca simboluri ale unui nou alfabet.

PAGINA 43