Tema de codare și decodare a platformei de conținut de informații
A9Tema. Codificare și decodificare a informației.
Ce trebuie să știți:
· Codificare - este o traducere a informațiilor dintr-o limbă în alta (înregistrare într-un alt sistem de simboluri,
într-un alt alfabet)
· De obicei, numit de codificare transfer de informații din limba „uman“ la formală, de exemplu, în cod binar, și decodare - tranziție inversă
· Unul dintre pictograma mesajului original poate fi înlocuit cu un nou simbol de cod, sau mai multe simboluri, și poate invers - unele dintre simbolurile de mesaje originale sunt înlocuite cu un singur caracter în noul cod (caractere chinezești reprezintă cuvinte și concepte întregi)
· Codificare poate fi uniformă și neuniformă;
pentru o codificare uniformă a tuturor caracterelor codificate codurile de lungime egală;
la neuniforma codare de caractere diferite pot fi codificate coduri de lungimi diferite, este dificil să decodeze
· Mesaj codat poate fi decodificat în mod clar de la început. în cazul în care starea de Fano. nici un cuvânt de cod nu este începutul unui alt cuvânt de cod;
· Mesaj codat poate fi decodificat în mod clar la sfârșitul anului. în cazul în care starea inversa a Fano. nici un cuvânt de cod nu este sfârșitul unui alt cuvânt de cod;
· Starea Fano - aceasta este o condiție necesară, dar nu suficientă pentru decodare lipsită de ambiguitate.
E, H, G, T. Pentru a codifica litere E, H, O utilizare de 5 biți cuvinte cod:: - 00000 h - 00111, O - 11011. Pentru acest set de cod E peste un canal de comunicație mesaje care conțin doar patru litere transmise cuvinte o astfel de proprietate deține: oricare două cuvinte diferite dintr-un set de cel puțin trei poziții. Această proprietate este importantă pentru a decripta mesaje în prezența interferențelor. Care dintre următoarele cuvinte cod poate fi utilizat pentru litera T la proprietatea specificată este valabil pentru toate
patru codewords?
1) 1100ne se potrivește nici unul din cuvintele de mai sus
1) codul discutat în problema se referă la eroare de rectificare a codurilor, care pot detecta și corecta un anumit număr de erori cauzate de interferența în timpul transmisiei de date;
1) Numărul de poziții în care două codewords diferite de aceeași lungime, numită distanța Hamming
2) codul în care distanța Hamming între fiecare pereche de cuvinte cod este egal cu d. Acesta permite detectarea erorii d-1; r pentru a corecta erorile este necesară pentru a satisface condiția
totuși codul de la d = 3 poate detecta una sau două erori și corect una eroare.
3) este ușor de a verifica dacă un anumit cod (E - 00000 h - 00111, D - 11011), distanța Hamming este 3; Tabelul de biți alocate sunt diferite, cele trei E-H și H perechi și patru O
într-o pereche de E-O:
E - E 00000 - 00000 h - 00111
H - 00111 A - 11011 A - 11011
4) verifică acum distanța dintre codurile cunoscute și opțiunile de răspuns; pentru a obține un prim răspuns 11111 distanță minimă 1 (într-o pereche de O-T), aceasta nu este o opțiune:
E - 00000 h - 00111 A - 11011
T - T 11111 - 11111 T - 11111
5) pentru a obține un al doilea răspuns 11100 distanță de 3 (perechi minime E-T și G-T):
E - 00000 h - 00111 A - 11011
T - T 11100 - 11100 T - 11100
6) obținem distanța minimă 1 (într-o pereche de H-T) pentru al treilea răspuns 00011. acest lucru nu este o opțiune:
E - 00000 h - 00111 A - 11011
T - T 00011 - 00011 T - 00011
7), astfel încât distanța Hamming de 3, dar este reținut pentru răspunsul 2 A: 2.
Mai multe exemple:
Pentru a codifica o secvență constând din literele A, B, C și D, a folosit un cod binar inegala pentru a decodifica în mod unic bitstream rezultat. Iată codul: A-00, B-010, B-011, D-101, D-111. Este posibil de a reduce una dintre scrisorile din lungimea cuvintelor de cod, astfel încât codul poate fi în continuare decodificate fără ambiguități? Codurile alte litere nu ar trebui să se schimbe. Alegeți răspunsul corect.
1) pentru litera D este imposibil
3) Litera pentru litera D - 01
Soluția (1 modalitate condiții de verificare Fano):
8) pentru decodare lipsită de ambiguitate este suficientă pentru a satisface condiția Fano Fano sau condiție inversă;
9) Opțiuni de verificare secvențial 1, 3 și 4; în cazul în care nici unul dintre ei nu va funcționa, va trebui să alegeți opțiunea 2 ( „acest lucru este imposibil“);
Stare „directă“ Fano nu este îndeplinită (scrisoarea codul B coincide cu începutul literelor din codul);
„Reverse“ condiție Fano nu este îndeplinită (cod literă B coincide cu sfârșitul codului G litere); astfel încât aceasta nu este o opțiune;
Stare „directă“ Fano nu este mulțumit (cod de caractere coincide cu începutul codului litera B);
„Reverse“ condiție Fano nu este îndeplinită (cod de caractere coincide cu sfârșitul literei D cod); astfel încât aceasta nu este o opțiune;
Stare „directă“ Fano nu este îndeplinită (cod literă F coincide cu începutul literelor de cod B și C);
dar „inversă“ condiție este îndeplinită Fano (litere de cod T nu coincide cu sfârșitul restul codurilor de litere); astfel încât această opțiune este adecvată, răspunsul corect - 4.
Exemplu de referință: demo_12
Pentru a codifica o secvență constând din literele A, B, C, D și E, am decis să utilizeze un cod binar non-uniform pentru a decodifica în mod unic secvența binară care apare în partea de primire a canalului de comunicație. Noi folosim acest cod: A-1, B-000, B-001, G-011.
Se specifică modul în care cuvântul de cod care urmează să fie codificat litere D. Lungimea cuvântului de cod pentru a fi cel mai mic dintre toate. Codul ar trebui să satisfacă proprietatea de decodare lipsită de ambiguitate.
13), observăm că faimosul cod al condiției Fano executat - nici un cuvânt de cod nu este începutul unui alt cuvânt de cod
14) în cazul în care A = 00, astfel încât șirul de cod coincide cu începutul B = 000 și B = 001 nu poate fi unic string decodată 000000: poate fi un DDD sau BB; astfel încât prima opțiune nu este potrivit
15) în cazul în care A = 01 astfel de cod lanț coincide cu începutul T = 011 nu poate fi decodificat în mod unic șir 011: poate fi DA sau F; Prin urmare, a doua opțiune este, de asemenea, nu este adecvat
16) când L = 11. condiție Fano este încălcat și: A 1 = cuvânt de cod coincide cu literele de cod A, este imposibil să decodifice în mod unic lanț 111: poate fi DA sau AAA; a treia variantă de realizare
nu se potrivește
17) pentru al patrulea exemplu de realizare, D = 010, starea Fano nu este rupt; -4 răspuns corect.
Un alt exemplu de locuri de muncă:
Constând doar din literele A, B, C, D, au decis să utilizeze un non-uniform pe lungimea codului pentru transmisie peste un canal de comunicație de mesaje: A = 0, B = 10, B = 110. Cum de a codifica
litera T la codul cât mai scurt posibil și admite o descompunere unică a mesajelor codificate la scrisoarea?
Soluția (1 variantă de realizare, metoda de selecție):
1) ia în considerare toate opțiunile pentru a crește lungimea literelor de cod T
2) începe cu r = 1; în acest caz, se dovedește că mesajul „10“ poate fi decodificat în două moduri:
ca GA sau B, astfel încât aceasta nu este o opțiune
3) de-a lungul lungimii variantei următoare: D = 11; în acest caz, „110“ mesaj poate fi decodat
ca GA sau B, astfel încât această opțiune este, de asemenea, nu este adecvat 4) A treia opțiune, T = 111. Acesta oferă o decodare fără echivoc a tuturor combinațiilor de litere, așa că ... răspuns - 3.
Un alt exemplu de locuri de muncă:
Pentru a codifica literele A, B, C au decis să utilizeze două cifre numere binare consecutive (00 la 11, respectiv). În cazul în care o astfel de metodă pentru a codifica o secvență de caractere BAVG și scrie rezultatul în hexazecimal, veți obține
18) condițiilor de coduri litere sunt: A - 00, B -01, B - 10 și F - 11, un cod uniform
19) secvență BAVG codificate, astfel: = 1001011
20) pentru a împărți un drept de înregistrare tetradă la stânga și să traducă fiecare sistem hexazecimal tetradă (adică, mai întâi în zecimal, apoi înlocuiți toate numerele la 10 la 15 la literele A, B, C, D, E, F); 1001011 get = 0 = 4B16 răspuns corect - 1.
Un alt exemplu de locuri de muncă:
bitmap alb-negru cu coduri de linie de linie, începând cu colțul din stânga sus și se termină la colțul din dreapta jos. În codare 1 denotă negru și 0 - White.
4) tetradelor traducere într-un număr de sistem hexazecimal obține secvențial B (11), D (13), A (10) 9, D (13) 5, adică lanțul BDA9D5 răspunsul corect - 3.
Un alt exemplu de locuri de muncă:
Pentru a transfera numere pe interferența canal este utilizat paritate cod. Fiecare număr înregistrat în reprezentarea binară, adăugând zerouri care conduc la o lungime de 4, iar secvența rezultată este adăugată la suma modulyu2 sale elemente (de exemplu, dacă peredaom23, obținem posledovatelnost0010100110). Determina cât de multe au trecut prin canalul în vide0100011?
1) să înțeleagă mai întâi modul în care numerele codificate în exemplul; este evident că se utilizează lungimea codului uniform; 2 caractere codificate ca 10 cifre binare (biți) pentru fiecare cifră au 5 biți, adică 2 → 3 → 00101 și 00110
2) ca o consecință a stării, primii patru biți din fiecare secvență - o cifră binară, iar al cincilea bit (bitul de paritate) este utilizat pentru a testa și se calculează ca fiind „suma modulo doi“, adică restul împărțirea sumei de 2 biți; atunci
2 = 00102, bitul de paritate (0 + 0 + 1 + 0) mod 2 = 1
3 = 00112, bitul de paritate (0 + 0 + 1 + 1) mod 2 = 0
3), dar biții de paritate nu avem nevoie. Important: al cincilea bit din fiecare cinci pot fi eliminate!
4) separam secvență predeterminată în grupuri de câte 5 biți fiecare:
01010, 10010, 01111, 00011.
5) se debarasa de-a cincea ultima) bit din fiecare grupă (: 0101, 1001, 0111, 0001.
acest lucru este codurile binare transmise numere: 5 = = 01012 10012 9 01112 = 7, 00012 = 1.
6) au fost astfel transferate la numerele 5, 9, 7, 1, sau numărul 5971.
A9Zadachi pentru antrenament.
69) peste un canal de comunicație transmis mesaje care conțin doar patru litere: A, B, C, D. Pentru a codifica literele A, B, C, folosit cuvinte cod de 5 biți: A - 10000 B - 00101, B - 01010. În acest scop, un set de cuvinte cod o astfel de proprietate deține: oricare două cuvinte diferite dintr-un set de cel puțin trei poziții. Această proprietate este importantă pentru a decripta mesaje în prezența interferențelor. Care dintre următoarele cuvinte cod poate fi utilizat pentru litera D la proprietatea specificată este valabilă pentru toate cele patru codewords?
1) 0110ne se potrivește nici unul din cuvintele de mai sus
71) In conformitate cu mesajele canalului de comunicație sunt transmise care conțin numai 5 litere E, K, G, scrisori T. folosite pentru a codifica un cod binar neuniforme astfel codewords:
0-A, I-00, K-10, G-110, T-111.
Printre cuvintele enumerate mai jos indică un cod care poate fi decodat într-un singur fel. În cazul în care există mai multe cuvinte, introduceți prima în ordine alfabetică.
1) 2 KAA) Ikot 3) CAT 4) nici unul dintre mesajele nu este adecvat
1. Pentru a codifica literele A, B, C au decis să utilizeze două cifre numere binare consecutive (00 la 11, respectiv). În cazul în care o astfel de metodă pentru a codifica o secvență de caractere GBVA și scrie rezultatul în hexazecimal, veți obține:
2. Pentru cele 5 litere ale alfabetului sunt date codurile binare (pentru unele dintre litere - două
biți, pentru unii - din cele trei). Aceste coduri sunt prezentate în tabelul de mai jos:
Seama care set de litere codificat șir binar
1) Baade 2) badde 3) bacde 4) bacdb
3. Pentru a codifica mesajul constând doar din literele A, B, C, D și E, utilizând
non-uniformă de-a lungul lungimii codului binar:
Care este (singurul!) Din cele patru mesajul primit a fost transmis fără erori
și poate fi decodat:
4. Pentru transmisia peste mesajul de canal de comunicare care constă numai din literele A, B, C, D, au decis să utilizeze un non-uniform pe lungimea codului: A = 0, B = 100, B = 101. Cum se codifica litera T la codul cât mai scurt posibil și admite o descompunere unică a mesajelor codificate la scrisoarea?
5. bitmap negru și alb codificate linie cu linie, începând cu colțul din stânga sus și se termină la colțul din dreapta jos. În codare 1 denotă negru și 0 - White.
Pentru rezultate compactitatea înregistrate în octal. Selectați koda.1412 intrarea corectă
6. Pentru a transfera numerele de interferență canal utilizând paritate cod. Fiecare număr înregistrat în reprezentarea binară, adăugând zerouri care conduc la o lungime de 4, iar secvența rezultată este adăugată la suma elementelor sale, modulo 2 (de exemplu, dacă peredaom 23, obținem secvența). Determina cât de multe au trecut prin canalul în formă?
7. Pentru litere de codificare O, B, B, A, K coduri binare sunt utilizate numerele 0, 1, 2, 3 și 4, respectiv (reținere un zero nesemnificativ în cazul reprezentării one-bit). Dacă o astfel de metodă pentru a codifica o secvență de caractere
Zucchini și se înregistrează rezultatul în hexazecimal, veți obține:
1) 5434DA4 3) ABCD
8. Pentru a transfera mesajele canalului de comunicație, constând numai din literele A, B, C, D, a decis să utilizeze non-uniform pe lungimea codului: A = 01, B = 1, B = 001. Cum de a codifica
litera T la codul cât mai scurt posibil și admite o descompunere unică a mesajelor codificate la scrisoarea?
9. Pentru a transfera mesajele pe canalul de comunicație, constând numai din literele A, B, C, D, au decis să utilizeze un non-uniform pe lungimea codului: A = 0, B = 100, B = 110. Cum se codifica litera T la codul cât mai scurt posibil și admite o descompunere unică a mesajelor codificate la scrisoarea?