Elevii, studenții absolvenți, tinerii oameni de știință care folosesc baza de cunoștințe în studiile și activitatea lor vor fi foarte recunoscători.
Definiție 1. Codurile sistematice sunt cele în care simbolurile de informații și de control ocupă locuri strict definite în combinații de coduri.
Definiție 2. Codurile liniare sunt cele în care simbolurile de control sunt combinații liniare ale simbolurilor de informație:
Codurile binare lineare formează un grup algebric în ceea ce privește modulul de operare de adunare modulo 2, deoarece suma cuvintelor de cod ale codului liniar furnizează cuvântul de cod aparținând codului dat. Această proprietate face posibilă construirea tuturor combinațiilor admise de cod liniar, având doar un număr limitat de ele.
Definiția 3. Greutatea unui cuvânt de cod este numărul de elemente non-zero ale acestuia.
Observați proprietatea importantă a codurilor de grup: distanța minimă dintre codurile cuvintelor de cod din grup este egală cu greutatea minimă a cuvintelor de cod non-zero.
Construcția unui cod liniar se realizează cu ajutorul așa-numitei matrice generatoare (generatoare, generatoare).
Atunci când se construiește o matrice de generatoare, trebuie respectate următoarele reguli:
1) numărul de cuvinte cheie de coduri inițiale trebuie să fie egal cu numărul simbolurilor de informație;
2) toate codurile initiale trebuie sa fie diferite;
3) printre numerele de cod inițiale nu ar trebui să existe zero;
4) toate codurile initiale trebuie sa fie independente liniar;
5) numărul de unități din fiecare combinație inițială de cod nu trebuie să fie mai mic de;
6) distanța de cod între orice perechi de cuvinte de cod inițiale nu trebuie să fie mai mică.
Codurile inițiale alese în conformitate cu aceste reguli sunt scrise sub forma unei matrice de generatoare. care conține rânduri și coloane:
Codul generat de o anumită matrice se numește un cod.
Orice matrice generatoare poate fi redusă la așa-numita formă canonică stânga sau redusă
unde este submatria de comandă a unității. - Submatrice de verificare care conține rânduri și coloane.
Forma canonică a matricei de generare poate fi obținută prin preluarea ca cuvinte de cod inițiale a acelor cuvinte care conțin o unitate în partea de informație. În acest caz, rândurile submatricolei de verificare trebuie să fie combinații -bite cu numărul celor care nu sunt mai mici de. hamming codarea liniară de decodare
Metoda de codificare folosind matricea generatorului este următoarea: prima combinație - zero rând al matricei generatorului este o combinație a codului dorit, alte combinații sunt însumarea tuturor combinațiilor posibile de rânduri ale matricei generatorului.
Exemplul 1. Folosind o matrice de generatoare, construiți un cod liniar sistematic capabil să corecteze o singură eroare în transmiterea a 16 mesaje ().
Soluția. Este cunoscut acest lucru. Prin urmare, și.
Conform tabelului. determina numărul de caractere de control.
Conform regulii pentru construirea unei submatrice de testare, numărul de unități dintr-un rând nu trebuie să fie mai mic de. Din combinațiile cu trei elemente alegem doar acelea în care numărul de unități este mai mare sau egal cu două: 110, 101, 011, 111.
Construim matricea generatoare
Rândurile din matricea de verificare pot fi schimbate. În acest caz, obținem mai multe variante de generare de matrice și, prin urmare, mai multe variante de coduri liniare pentru exemplul examinat.
Algoritmul de generare a caracterelor de control din partea informațiilor cunoscute poate fi scris după cum urmează:
Simbolul de control este suma simbolurilor de informație corespunzătoare unităților din prima coloană a submatricei de testare. cel de-al doilea simbol de control este suma simbolurilor de informație corespunzătoare unităților din a doua coloană a submatricei de test și așa mai departe.
Exemplul 2. Se codifică într-un cod liniar o combinație a unui cod binar de patru cifre 1100 (.
Soluția. Numărul de simboluri de informații. Din tabel. 3.1.
Matricea (3) din Exemplul 3 poate servi ca matrice generatoare. Apoi, în conformitate cu (4)
Deci, combinația completă a codului este: 1100110.
Notă. Let - Simbolurile informațiilor, apoi cuvântul cod al codului liniar pot fi găsite prin formula
Codificăm combinația 1100 conform formulei (5):
Corecția erorilor se efectuează prin verificarea
Numărul de verificări este egal cu numărul simbolurilor de control ale codului de corecție.
Ca urmare a verificărilor, se formează o combinație de simboluri. numit un sindrom. Dacă greutatea sindromului este zero, atunci combinația acceptată este considerată fără erori, altfel combinația acceptată conține o eroare.
Corectarea erorilor se efectuează în funcție de tipul de sindrom cu ajutorul unei matrice de control. care constă din două submatricole: și o submatrică a unității de ordinul n:
Coloanele unei astfel de matrice reprezintă valoarea sindromului pentru descărcare corespunzătoare numărului de coloană al matricei.
Exemplul 3. Afișați procesul de fixare a unei erori într-un bit arbitrar al oricărei combinații de coduri a codului de corecție construit în exemplul 3.3.
Soluția. În conformitate cu principiul construirii unui sistem de verificări (6), sistemul de verificări pentru codul construit va arăta
Construim matricea de control:
Dacă biții sindromului corespund primei coloane a matricei. și anume atunci eroarea este în prima cifră a combinației primite, dacă sindromul are forma. care corespunde celei de a doua coloane a matricei. atunci eroarea este în a doua cifră, iar sindromul 001 corespunde unei erori în a treia cifră de control a combinației de coduri etc.
Pentru a verifica proprietățile corective ale codului, utilizați combinația la numărul 7: 1010101.
Trebuie să existe un eșec în a patra cifră, adică combinația este adoptată în următoarea formă: 1011101.
Sindromul 111 coincide cu a patra coloană a matricei de control, prin urmare, în a patra cifră, simbolul ar trebui înlocuit cu cel din urmă.
Notă. Fie - cuvântul cod al codului liniar, apoi sindromul poate fi găsit prin formula
Vom găsi sindromul combinației adoptate conform formulei (3.8):
Notă. Codificarea este posibilă cu ajutorul matricei de control: simbolul de control () este egal cu suma simbolurilor de informație corespunzătoare unităților din al treilea rând al matricei.
Cod Hamming
Codul Hamming este una dintre clasele importante de coduri liniare. S-a găsit o aplicație largă în practică, are un algoritm simplu și convenabil pentru implementarea tehnică pentru detectarea și corectarea unei singure erori ().
Hamming a sugerat aranjarea coloanelor matricei de control astfel încât numărul coloanei a matricei și numărul de biți al combinației de coduri să corespundă reprezentării binare a numărului. Apoi, sindromul, găsit cu ajutorul ecuațiilor de testare, va fi o reprezentare binară a cifrei combinației de coduri în care a apărut eroarea. Pentru aceasta, simbolurile de control nu trebuie să fie la sfârșitul combinației de coduri, ci pe numerele pozițiilor alese în conformitate cu legea. și anume pe numerele 1, 2, 4, 8, .... Astfel, o caracteristică caracteristică a matricei de control a codului Hamming este aceea că coloanele sale sunt simbolurile de cuvinte cod în codul binar de lungime.
Exemplu 4. Construiește un cod Hamming pentru una dintre combinațiile unui cod binar pe patru biți.
Soluția. Deoarece. înseamnă.
Combinația originală a patru simboluri de informații se bazează pe un formular. unde sunt simboluri de control; - simboluri de informare.
Construim matricea de control. coloanele sale sunt numerele simbolurilor de cod în codul binar format din trei cifre.
Notă. Numărul zecimal poate fi reprezentat în formular
unde pot lua două valori: 0 sau 1.
Apoi - este o reprezentare binară a unui număr.
De exemplu. prin urmare, 001 este o reprezentare binară de trei cifre de 1; 6 110, din moment ce. atunci
După rearanjarea coloanelor care au o unitate, matricea de control va lua forma
Simbolurile de control sunt definite prin formule
Sistemul de verificări are forma
Notă. Când transmiteți pe un canal de comunicații, poate apărea o eroare dublă sau mai mare în cuvântul de cod. În acest caz, sindromul poate lua orice valoare, inclusiv zero. Aceasta va corecta caracterul aleatoriu. Pentru a exclude o astfel de corecție automată, se introduce un alt caracter pentru a verifica întreaga combinație pentru paritate. Distanta de cod crește.
Exemplul 5. Codul din combinația de cod Hamming 1101.
Soluția. Prin condiție. Prin urmare. Caracterele de control vor fi. Simboluri de informare.
Pentru a găsi simbolurile de control, folosim matricea de control (3.9) din exemplul anterior.
Din sistem (10)
Cuvântul de cod va arăta ca 1010101.
Să presupunem că a apărut o eroare în timpul transferului și am luat combinația greșită: 101011 1 (a apărut o eroare în a șasea cifră).
Folosind sistemul de verificări (3.11), găsim valorile categoriilor de sindrom:
Sindromul indică o eroare în a șasea cifră a combinației primite ().
Dacă ar fi trebuit să construim un cod pentru a verifica erorile duble, atunci ar trebui să introducem un bit suplimentar zero:
Obțineți codul 01010101.
Fie ca codul să fie de forma 0101011 1 atunci când eroarea este transmisă și apărută.
O verificare în acest caz ar arăta că sindromul este de 110 și verificarea întregii combinații pentru paritate = 0 + 1 + 0 + 1 + 0 + 1 + 1 + 1 = 1. Aceasta indică o singură eroare. Corecția automată a erorilor este permisă.
Există următorul algoritm pentru decodarea codului Hamming cu distanța de cod (Tabelul 3.2).
Tabelul 3.2.
Pentru căutarea fuzzy pot fi folosite algoritmi bine cunoscuți și coduri Hamming. Codurile Hamming au fost utilizate cu mult timp și cu succes în codificarea și decodificarea informațiilor, permițând recuperarea cu succes a informațiilor pierdute.
Rețelele de reținere sunt, de asemenea, utilizate în mod activ pentru recunoașterea optică a caracterelor (OCR).
Cu toate acestea, algoritmii Hamming pot fi aplicați nu numai în teoria codării informațiilor, ci și în recuperarea informațiilor. În mod eficient, codurile Hamming funcționează împreună cu dispozitivul logic fuzzy.
Codurile Hamming sunt cele mai simple coduri liniare, cu o distanță minimă de 3, adică, capabile să corecteze o eroare [2].
Rețelele Hamming sunt unul dintre tipurile de rețele neuronale. Principiul funcționării rețelelor Hamming se bazează pe determinarea distanței Hamming între obiecte și găsirea celui mai apropiat.
Algoritmii Hamming utilizează în lucrarea lor codul liniar, care, în comparație cu alte coduri, permite implementarea unor algoritmi mai eficienți pentru codificarea și decodificarea informațiilor.
În procesul de căutare și de emitere a informațiilor, în mod inevitabil apar greșeli, prin urmare, controlul integrității datelor și corectarea erorilor sunt sarcini importante la multe niveluri de manipulare a informațiilor.
Sarcina reală este de a dezvolta un sistem de căutare fuzzy care să găsească un cuvânt în listă, chiar dacă este distorsionat sau conține caractere greșite și pierdute.
Pentru a detecta erorile în rețelele Hamming, se utilizează coduri de detectare a erorilor și se folosesc coduri de corecție pentru a le corecta.
Pentru a face acest lucru, atunci când scrieți și transferați informații către date utile, informațiile redundante structurate sunt adăugate într-un mod special, iar când citiți (recepționați), acestea sunt folosite pentru a detecta sau a corecta erorile. Bineînțeles, numărul de erori care pot fi corectate este limitat și depinde de codul specific utilizat.
Astfel, algoritmii Hamming pot fi utilizați pentru a căuta cuvinte care sunt introduse cu erori în interogarea inițială.
Să presupunem că avem un dicționar la intrare și că este necesar să găsim cuvântul de căutare în acest dicționar, chiar dacă a fost tastat cu o eroare. Pentru a face acest lucru, trebuie mai întâi să gândiți și să dezvoltați un sistem de codificare a informațiilor simbolice în vectori. Pentru fiecare caracter, am setat masca biți:
Când se codifică informațiile despre simbol, este necesar să se ia în considerare sursa pentru obținerea acestor informații. Dacă, de exemplu, introducem caractere folosind tastatura, este recomandat să setați codurile de caractere astfel încât simbolurile de lângă tastatură să aibă codurile apropiate de Hamming. Dacă sursa este un program de recunoaștere a imaginii (OCR), atunci codurile similare ar trebui să fie similare în caracterele de ortografie. După codare, astfel, furnizăm vectorii recepționați la intrarea rețelei neuronale.
Cu toate acestea, este necesar să se ia în considerare o caracteristică a rețelelor Hamming. Dacă scrisul a fost o greșeală de scriere sau două, algoritmul funcționează bine, dar în cazul în care caracterul a fost omis sau adăugat în plus, distanța Hemingovo poate fi prea mare. Pentru a rezolva acest neajuns, vom aduce la intrare ca un cuvânt de căutare în sine, și același cuvânt, cu excepția pe rând câte un caracter în fiecare poziție și adăugând o literă pentru fiecare poziție. O astfel de abordare va permite găsirea practică a tuturor cazurilor de eroare - o greșeală, un caracter lipsă, un simbol suplimentar.
Trebuie remarcat faptul că, în ciuda eficacității deosebite a codurilor Hamming, acestea nu au anumite dezavantaje. Codurile liniare, de regulă, se pot descurca foarte bine cu erori și erori rare și mari [4]. Cu toate acestea, eficacitatea acestora, cu erori relativ frecvente, dar mici, este mai puțin ridicată.
Datorită liniarității pentru memorarea sau enumerarea tuturor cuvintelor de cod, este suficient să se memoreze în memoria codorului sau decodorului o parte esențială mai mică, și anume numai acele cuvinte care formează baza spațiului liniar corespunzător. Acest lucru simplifică foarte mult implementarea dispozitivelor de codare și decodare și face ca codurile liniare să fie foarte atractive din punct de vedere al sarcinilor de recuperare a informațiilor practice.
Găzduit pe Allbest.ru
Articole similare
Trimiteți-le prietenilor: