Codul de corectare (de asemenea , codul de corectare a erorilor ) este un cod conceput pentru a detecta și corecta erorile .
Tehnica principală este de a adăuga informații redundante special structurate (de exemplu, numărul de verificare ) la sarcina utilă la scriere (transmitere) și la citire (recepție), folosind astfel de informații redundante pentru a detecta și corecta erorile. Numărul de erori care pot fi corectate este limitat și depinde de codul utilizat.
Codurile de detectare a erorilor (care pot stabili doar faptul unei erori) aparțin acelorași clase de coduri ca și codurile de corectare a erorilor. De fapt, orice cod de corectare a erorilor poate fi folosit și pentru a detecta erori (făcând acest lucru, va putea detecta mai multe erori decât a fost capabil să repare). Codurile de corectare a erorilor sunt utilizate în sistemele de comunicații digitale , inclusiv: satelit, releu radio, celular, transmisie de date prin canale telefonice, precum și în sistemele de stocare a informațiilor, inclusiv magnetice și optice. Codurile de detectare a erorilor sunt utilizate la diferite niveluri ale protocoalelor de rețea .
În funcție de modul în care lucrează cu datele, codurile de corectare a erorilor sunt împărțite în bloc , care împart informațiile în fragmente de lungime constantă și procesează fiecare dintre ele separat, și convoluționale , care lucrează cu datele ca un flux continuu. .
Un cod bloc care descompune informațiile în fragmente de lungime de biți și le convertește în cuvinte de cod de lungime de biți este de obicei notat ; numărul se numește rata de cod . Dacă codul lasă biții originali neschimbați și adaugă verificări, un astfel de cod se numește sistematic , în caz contrar - nesistematic .
Puteți seta codul de bloc în diferite moduri, inclusiv un tabel în care fiecare set de biți de informații este asociat cu un bit din cuvântul de cod. Cu toate acestea, un cod bun trebuie să îndeplinească cel puțin următoarele criterii:
Cerințele de mai sus se contrazic în general una pe cealaltă, așa că există un număr mare de coduri, fiecare dintre acestea fiind potrivit pentru o anumită gamă de sarcini. Aproape toate codurile utilizate sunt liniare , acest lucru se datorează faptului că codurile neliniare sunt mult mai dificil de studiat și este dificil pentru ele să ofere o ușurință acceptabilă de codare și decodare.
Un cod de bloc liniar este un astfel de cod încât setul cuvintelor sale de cod formează un subspațiu liniar -dimensional în spațiul liniar -dimensional , izomorf față de spațiul vectorilor -biți .
Aceasta înseamnă că operația de codificare corespunde înmulțirii vectorului original -bit cu o matrice nedegenerată , numită matrice generatoare.
Pentru un subspațiu ortogonal în raport cu și o matrice care definește baza acestui subspațiu și pentru orice vector , este adevărat:
. Distanța minimă și puterea corectivăDistanța Hamming (metrica Hamming) dintre două cuvinte de cod este numărul de biți diferiți în pozițiile corespunzătoare:
.Distanța minimă Hamming este o caracteristică importantă a unui cod de bloc liniar. Arată cât de „departe” sunt codurile unul de celălalt. Acesta definește o altă caracteristică, nu mai puțin importantă - capacitatea de corectare :
.Puterea corectivă determină câte erori de transmisie a codului (de tip ) pot fi garantate a fi corectate. Adică în jurul fiecărui cuvânt cod avem -neighborhood , care constă din toate opțiunile posibile pentru transmiterea cuvântului cod cu numărul de erori ( ) nu mai mare de . Nu se intersectează două vecinătăți a oricăror două cuvinte cod, deoarece distanța dintre cuvintele cod (adică, centrele acestor vecinătăți) este întotdeauna mai mare decât două din razele lor .
Astfel, după ce a primit o combinație de cod distorsionată de la , decodorul decide că combinația de cod originală a fost , corectând astfel erorile.
De exemplu, dacă există doar două cuvinte de cod și cu o distanță Hamming între ele egală cu 3, o eroare într-un bit al cuvântului poate fi corectată, deoarece chiar și în acest caz cuvântul primit este mai aproape de cuvântul de cod decât de . Dar dacă canalul a introdus erori în doi biți (în care diferă de ), atunci rezultatul unei transmisii eronate va fi mai aproape de , iar decodorul va decide că cuvântul a fost transmis .
Codurile HammingCodurile Hamming sunt cele mai simple coduri liniare cu o distanță minimă de 3, adică capabile să corecteze o eroare. Codul Hamming poate fi reprezentat în așa fel încât sindromul să fie:
,unde este vectorul primit, va fi egal cu numărul poziției în care a apărut eroarea. Această proprietate face decodarea foarte ușoară.
Metodă generală de decodare a codurilor de linieOrice cod (inclusiv neliniar) poate fi decodat folosind un tabel obișnuit, în care fiecare valoare a cuvântului primit corespunde cuvântului transmis cel mai probabil . Cu toate acestea, această metodă necesită utilizarea de tabele uriașe deja pentru cuvinte de cod relativ mici.
Pentru codurile liniare, această metodă poate fi simplificată semnificativ. În acest caz, pentru fiecare vector primit , sindromul este calculat . Deoarece , unde este cuvântul de cod și este vectorul de eroare, atunci . Apoi, folosind tabelul de sindrom, se determină un vector de eroare, cu ajutorul căruia se determină cuvântul de cod transmis. În acest caz, tabelul este mult mai mic decât atunci când utilizați metoda anterioară.
În ciuda faptului că decodarea codurilor liniare este mult mai ușoară decât decodarea majorității codurilor neliniare, pentru majoritatea codurilor acest proces este încă destul de complicat. Codurile ciclice , pe lângă decodarea mai simplă, au și alte proprietăți importante.
Un cod ciclic este un cod liniar cu următoarea proprietate: dacă este un cuvânt de cod, atunci permutarea sa ciclică este, de asemenea, un cuvânt de cod.
Cuvintele unui cod ciclic sunt reprezentate convenabil ca polinoame. De exemplu, un cuvânt de cod este reprezentat ca un polinom . În acest caz, deplasarea ciclică a cuvântului de cod este echivalentă cu înmulțirea polinomului cu modulo .
Cel mai adesea, se folosesc coduri ciclice binare (adică pot lua valorile 0 sau 1).
Generarea polinomuluiSe poate demonstra că toate cuvintele de cod ale unui anumit cod ciclic sunt multipli ai unui anumit polinom generator (generator) . Polinomul generator este un divizor .
Cu ajutorul unui polinom generator, codarea se realizează printr-un cod ciclic. În special:
Codurile CRC ( English cyclic redundancy check - cyclic redundant check ) sunt coduri sistematice concepute nu pentru a corecta erorile, ci pentru a le detecta. Ei folosesc metoda de codificare sistematică prezentată mai sus: „suma de control” se calculează prin împărțirea la . Deoarece nu este necesară corectarea erorilor, validarea transmisiei se poate face în același mod.
Astfel, forma polinomului specifică un cod CRC specific. Exemple ale celor mai populare polinoame:
Nume de cod | grad | Polinom |
---|---|---|
CRC-12 | 12 | |
CRC-16 | 16 | |
CRC- CCITT | 16 | |
CRC-32 | 32 |
Codurile Bose-Chowdhury-Hockwingham (BCH) sunt o subclasă de coduri ciclice. Caracteristica lor distinctivă este capacitatea de a construi un cod BCH cu o distanță minimă nu mai mică decât una dată. Acest lucru este important deoarece, în general, determinarea distanței minime de cod este o sarcină foarte dificilă.
Codurile de corectare a erorilor Reed-SolomonCodurile Reed-Solomon sunt coduri ciclice non-binare care vă permit să corectați erorile din blocurile de date. Elementele vectorului de cod nu sunt biți, ci grupuri de biți (blocuri). Codurile Reed-Solomon care operează pe octeți ( octeți ) sunt foarte comune.
Din punct de vedere matematic, codurile Reed-Solomon sunt coduri BCH .
Deși codurile bloc se descurcă în general bine cu explozii rare, dar mari de erori , ele sunt mai puțin eficiente pentru erori frecvente, dar mici (de exemplu, într-un canal AWGN ).
Codurile convoluționale, spre deosebire de codurile bloc, nu împart informațiile în fragmente și lucrează cu ea ca și cu un flux de date continuu. Astfel de coduri, de regulă, sunt generate de un sistem liniar discret invariant în timp . Prin urmare, spre deosebire de majoritatea codurilor bloc, codificarea convoluțională este o operație foarte simplă, despre care nu se poate spune despre decodare.
Codificarea codurilor convoluționale se realizează utilizând un registru de deplasare , ale cărui atingeri sunt însumate modulo doi. Pot exista două (cel mai adesea) sau mai multe astfel de sume.
Codurile convoluționale sunt decodificate de obicei folosind algoritmul Viterbi , care încearcă să recupereze secvența transmisă conform criteriului de maximă probabilitate .
Codurile convoluționale funcționează eficient într-un canal de zgomot alb, dar nu se descurcă bine cu exploziile de eroare. În plus, dacă decodorul face o greșeală, acesta produce întotdeauna o explozie de eroare la ieșire.
Avantajele diferitelor metode de codificare pot fi combinate prin aplicarea codării concatenate . În acest caz, informațiile sunt mai întâi codificate cu un cod, apoi cu altul, rezultând un cod de produs .
De exemplu, următoarea construcție este populară: datele sunt codificate cu codul Reed-Solomon, apoi intercalate (cu caractere situate aproape, plasate departe unele de altele) și codificate cu un cod convoluțional. La receptor, codul convoluțional este mai întâi decodificat, apoi se efectuează intercalarea inversă (în acest caz, exploziile de erori la ieșirea decodorului convoluțional se încadrează în diferite cuvinte de cod ale codului Reed-Solomon), iar apoi Reed- Codul Solomon este decodat.
Unele coduri de produs sunt concepute special pentru decodare iterativă, în care decodificarea se face în mai multe treceri, fiecare folosind informații din cea anterioară. Acest lucru permite o mare eficiență, dar decodarea necesită resurse intensive. Aceste coduri includ coduri turbo și coduri LDPC (coduri Gallager).
Eficiența codurilor este determinată de numărul de erori pe care le poate corecta, de cantitatea de informații redundante care trebuie adăugată și de complexitatea implementării codificării și decodării (atât hardware, cât și software de calculator ).
Să existe un cod bloc binar cu capacitate de corectare . Atunci inegalitatea (numită limită de Hamming) este valabilă:
Codurile care satisfac această limită de egalitate se numesc perfecte. Codurile perfecte includ, de exemplu, codurile Hamming . Codurile cu putere corectivă mare care sunt adesea folosite în practică (cum ar fi codurile Reed-Solomon ) nu sunt perfecte.