Bazele teoriei informației
Lucrare practică № 4
"Codarea informațiilor pentru transmiterea pe un canal discret cu interferențe"
Scop. să consolideze cunoștințele teoretice și să obțină abilități practice de codificare a informațiilor pe un canal discret cu interferențe prin aplicarea unui cod Hamming anti-bruiaj. Aflați pentru a determina erorile uniforme și ciudate în mesaje, simple. Obțineți abilitățile pentru a corecta singurele erori în mesaje.
Codul Hamming - un algoritm de auto-monitorizare și un cod de auto-corectare care vă permite să codifica orice mesaj de informații într-un anumit fel, și după transfer (de exemplu, printr-o rețea) pentru a determina dacă a apărut o eroare în mesajul (cel-o măsură a interferenței) și , dacă este posibil, restaurați acest mesaj. În exemplul descris, CA meu Hamming algoritm simplu, care poate corecta doar o singură eroare (există modificări mai avansate a algoritmului, care poate detecta (și corect, dacă este posibil) mai multe erori).
Codul Hamming este alcătuit din două părți. Prima parte codifică mesajul original, introducând în el anumite biti de control (calculate într-un mod special). Partea a doua primește mesajul de intrare și recalculează biții de control (folosind același algoritm ca prima parte). Dacă toți biții de control noi sunt aceiași ca cei primiți, atunci mesajul este primit fără erori. În caz contrar, este afișat un mesaj de eroare și, dacă este posibil, eroarea este corectată.
Să presupunem că avem un mesaj "habr" care trebuie transmis fără erori. Pentru a face acest lucru, trebuie mai întâi să codificați mesajul nostru cu ajutorul Codului Hamming. Trebuie să o prezentăm în formă binară.
În acest stadiu este necesară determinarea așa-numitei lungimi a cuvântului de informație, adică lungimea unui șir de zerouri și a celor pe care le vom codifica. Să presupunem că avem o lungime de 16 cuvinte. Deci, trebuie să împărțim mesajul nostru inițial ("horn") în blocuri de 16 biți, pe care apoi vom codifica separat unele de altele. Deoarece un caracter are 8 biți în memorie, exact două caractere ASCII sunt plasate într-un singur cuvânt codificat. Deci, avem două șiruri binare de 16 biți fiecare:
sunt codificate independent una de cealaltă. Luați în considerare modul în care se face acest lucru în exemplul primei părți.
Mai întâi de toate, trebuie să introduceți biți de control. Ele sunt inserate în locuri strict definite - acestea sunt poziții cu numere egale cu puterile a două. În acest caz (când lungimea cuvântului infor-infor de 16 biți) este de a fi poziția 1 (2 0), 2 (2 1), 4 (2 2), 8 (2 3), 16 (2 4). În consecință, am obținut 5 biți de control (subliniat):
Astfel, lungimea întregului mesaj a crescut cu 5 biți. Înainte de a calcula singuri biții de control, le-am atribuit o valoare de "0".
Calcularea biților de control
Acum trebuie să calculați valoarea fiecărui bit de control. Valoarea fiecărui bit de control depinde de valorile biților de informații, dar nu de toate, ci numai de cele pe care le controlează acest bit de control. Pentru a înțelege care biți corespund fiecărui bit de control, este necesar să înțelegem o regularitate foarte simplă: bitul de control cu numărul N controlează toți biți N următori, fiecare biți N începând din poziția N:
Aici semnul "X" denotă acele biți pe care le controlează bitul de control, al cărui număr este pe partea dreaptă. Aceasta este, de exemplu, numărul de biți de 12 biți este controlată cu numerele 4 și 8. Este clar că, pentru a afla ce biți de controlat de numărul de biți N trebuie pur și simplu se descompun N în puteri de două.
Apoi vom calcula valoarea fiecărui bit de control: să ia fiecare bit de control și a vedea cât de multe dintre unitățile sale controlate de biți, se obține un număr întreg, iar dacă este chiar, atunci setați zero off, în caz contrar unitatea set. Este cu siguranță posibil, și invers, în cazul în care numărul este chiar, atunci pune unitatea, în caz contrar, setat la 0. Principalul lucru este că în „codificare“ și „decodificare“ parte a algoritmului a fost același. (Vom aplica prima opțiune).
Prin calcularea biților de control pentru cuvântul nostru informativ, obținem următoarele: