coduri corectoare de erori (coduri de corectare a erorilor codurilor corectoare coduri rezistente la zgomot ..) - coduri care servesc pentru a corecta erorile care apar în transmiterea de informații sub influența interferențelor, precum și stocarea.
În acest scop, înregistrarea (de transfer) în date utile adăuga structurate special informații redundante, și citirea (primirea) este utilizat pentru a detecta și corecta erorile. Desigur, numărul de erori care pot fi corectate este limitată și depinde de un anumit cod.
Cu cod, remedieri de erori strâns asociate coduri de detectare a erorilor. Spre deosebire de primul, acesta din urmă poate stabili numai că prezența unor erori în datele transmise, dar nu-l repara.
De fapt, codurile de detectare a erorilor utilizate să aparțină aceleiași clase de coduri ca coduri corectoare de erori. Mai mult decât atât, orice cod, repara bug-uri, și pot fi folosite pentru a detecta erori. Deci, este logic să ia în considerare aceste concepte împreună.
Conform unei metode de operare a codurilor corectoare de erori de date sunt împărțite în bloc. împărțirea informațiilor în fragmente de lungime constantă și mâner fiecare în mod individual, și sinuozitate. care lucrează cu date ca un flux continuu.
Ca un exemplu, un simplu bloc de cod, puteți specifica codul-repetarea. în care fiecare simbol sau bloc de informații sunt transmise de mai multe ori. Cu toate acestea, acest cod are o eficiență foarte scăzută (cm. De mai jos).
coduri bloc
Lăsați informația codificată este împărțit în fragmente de k biți, care sunt convertite în codewords de lungime n biți. Apoi, codul bloc corespunzător este, de obicei, notat cu (n, k). Mai mult decât atât, numărul \ Frac se numește rata de cod.
În cazul în care codul sursă de k biți la stânga intacte, și adaugă n - kproverochnyh. aceasta se numește un cod sistematic. în caz contrar nesistematică.
Cere un cod de bloc poate fi diferit, inclusiv masa, în cazul în care fiecare set de biți de informație k mapate la n biți ai cuvântului de cod. Cu toate acestea, un cod bun trebuie să îndeplinească cel puțin următoarele criterii:
- capacitatea de a corecta cât mai mult posibil numărul de erori,
- redundanța cât mai puțin posibil,
- ușurința de codare și decodare.
Este ușor de observat că cerințele de mai sus sunt contradictorii. Acesta este motivul pentru care există un număr mare de coduri, fiecare dintre care este potrivit pentru gama de aplicații.
Practic, toate codurile utilizate sunt liniare. Acest lucru se datorează faptului că codurile neliniare mult mai dificil de examinat și dificil pentru ei să asigure ușurința acceptabilă de codare și decodare.
Codurile liniare ale formei generale
Codul blocului liniar - codul astfel încât multitudinea sa de cuvinte cod formează un subspatiu liniar k-dimensional (numim C) în spațiul vectorial n-dimensional. izomorfe vectorii spațiu k biți.
Aceasta înseamnă că operația de codificare corespunde înmulțirea k-bit vector inițial printr-o matrice nesingular G. numită matricea generatorului.
Fie C ^ - ortogonali în raport subspațiul C. și H - matricea definind baza acestui subspațiu. Apoi, pentru orice vector \ overrightarrow \ în C este adevărată:
Distanța minimă și capacitatea de corecție
Distanta Hamming (metric Hamming) între două codewords \ overrightarrow și \ overrightarrow este numărul de biți diferite în poziții corespunzătoare, adică numărul de „unu“, într-un vector \ overrightarrow \ oplus \ overrightarrow.
Distanta Hamming minimă (dmin) este o caracteristică importantă a unui cod bloc liniar. Aceasta definește cealaltă, caracteristica nu mai puțin important - capacitatea de corectare:
- t = \ mathcal \ frac-1> \ mathcal. Aici parantezele unghiulare denotă rotunjirea „în jos“.
Capacitatea Corectarea determină cât de multe erori de cod poate fi garantată corect.
Aici este un exemplu. Să presupunem că există două cuvinte de cod A și B, distanța Hamming dintre ele este egală cu 3. În cazul în care un cuvânt a fost transferat, iar eroarea de canal introdus într-un singur bit, acesta poate fi corectată, deoarece chiar și în acest caz, cuvântul cel mai apropiat de primit cuvânt de cod A decât B. Dar, în cazul în care erorile de canal au fost făcute în două biți, decodorul poate calcula cuvântul B. a fost transmis
Hamming coduri
Hamming coduri - codurile liniare simple, cu o distanță minimă de 3, care este capabil să corecteze o eroare. Codul Hamming poate fi reprezentat într-o astfel de formă încât sindromul
- \ Overrightarrow = \ overrightarrow H ^ T. în cazul în care \ overrightarrow - vector primit,
implicit poziția în care a apărut eroarea. Această caracteristică vă permite să facă o decodare foarte simplu.
Metoda generală liniar Coduri decodare
Orice număr (inclusiv non-liniară) poate fi decodificat utilizând un tabel regulat în cazul în care fiecare valoare a cuvântului primit \ overrightarrow corespunde cel mai probabil transmis de cuvânt \ overrightarrow. Cu toate acestea, această metodă necesită o masă mare pentru codewords deja o lungime relativ mică.
Pentru codurile liniare, această metodă poate fi mult simplificată. Astfel, pentru fiecare sindrom calculat primit vector \ overrightarrow \ overrightarrow = \ overrightarrow H ^ T. Deoarece \ overrightarrow = \ overrightarrow + \ overrightarrow. unde \ overrightarrow - un cuvânt cod și \ overrightarrow - erori vectoriale, \ overrightarrow = \ overrightarrow H ^ T. Apoi, folosind tabelul de sindrom este determinat de vectorul eroare, este determinată folosind cuvântul de cod transmis. La aceeași masă este o mult mai mică decât cu metoda anterioară.
coduri ciclice liniare
În ciuda faptului că decodificarea codurilor liniare este deja mult mai ușor de a decoda majoritatea non-liniare, acest proces este încă destul de dificil pentru cele mai multe coduri. Codurile Cyclic, altele decât o simplă decodare posedă alte proprietăți importante.
Codul ciclica este un cod liniar, cu următoarea proprietate: dacă \ overrightarrow este un cuvânt de cod, acesta este, de asemenea, o permutare ciclică a cuvântului cod.
cuvinte cod ciclic prezentate convenabil sub formă de polinoame. De exemplu, cuvântul cod \ overrightarrow = (v_0, v_1. V_) este reprezentat ca v polinom (x) = V0 + v1x +. + Vn - 1xN - 1. în acest caz, trecerea ciclică a cuvântului de cod este echivalent cu multiplicarea polinomului de x modulo xn - 1.
În cele ce urmează, dacă nu se specifică altfel, presupunem că codul ciclic este binar. și anume v0, v1 ... poate lua valorile 0 sau 1.
generatoare de polinomul
Se poate arăta că toate cuvintele de cod ale unui cod ciclic particular sunt multipli ai unui anumit polinomug generatoare (x). Generarea polinom este un divizor de xn - 1.
Cu un polinom generator este realizată de codificare a unui cod ciclic. În special:
Codurile CRC (controlul redundanței ciclice - verificare a redundanței ciclice) coduri sunt sistematice, care nu sunt proiectate pentru a corecta erorile și pentru a le detecta. Acestea folosesc o metodă de codificare sistematică stabilită mai sus: „verifica suma“ se calculează prin împărțirea xn - ku (x) g (x). Datorită faptului că corectarea erorilor nu este necesară, validarea transmisiei poate fi efectuată în același mod.
Astfel, tipul de polinomul g (x) specifică un anumit CRC cod. Exemple de cele mai populare de polinoame:
Codurile Bose-Chaudhuri-Hocquenghem (BCH) sunt o subclasă de coduri ciclice binare. Caracteristica lor distinctiv - posibilitatea de a construi un cod BCH, cu o distanță minimă de cel puțin un specificat. Acest lucru este important, deoarece, în general vorbind, determinarea distanței minime a codului are o sarcină foarte dificilă.
Codurile Matematic BCH construcția și descompunerea lor decodificare folosind polinomului generator g (x), de factorii din domeniul Galois.
Codurile Reed-Solomon
Codurile Reed-Solomon (coduri RS) sunt coduri BCH practic non-binare, adică elementele vectorului de cod nu sunt biți și grupuri de biți. Codurile foarte frecvente Reed-Solomon, care lucrează cu octeți (octeții).
Avantaje și dezavantaje ale codurilor bloc
Deși codurile bloc au tendința de a face bine cu câteva, dar mari loturi de erori. eficacitatea lor la erori frecvente, dar mici (de exemplu, un canal cu zgomot alb), mai puțin ridicat.
codurile convoluționale
Codurile convoluționale, spre deosebire de bloc, nu împart informațiile în bucăți și să lucreze cu el ca și cu un flux continuu de date.
Codurile convoluțională. de obicei, generate de un sistem invariant in timp liniar discret. Prin urmare, spre deosebire de majoritatea codurilor bloc, codare convoluție - o operație foarte simplă, care nu este decodarea.
codificare cod convolutional este realizată folosind registrul de deplasare, robinetele de care sunt însumate modulo doi. Aceste sume pot fi două (cel mai adesea) sau mai mult.
Codurile convoluționale Decoding sunt de obicei realizate de algoritmul Viterbi, care încearcă să recupereze secvența transmisă a probabilității maxime.
Avantajele și dezavantajele de coduri convoluțional
Codurile convoluționale funcționează în mod eficient într-un canal cu zgomot alb, dar nu face față cu exploziile de erori. Mai mult decât atât, în cazul în care decodorul este greșit, producția sa este întotdeauna o eroare de explozie.
codificare concatenate. Turbo-coduri
Avantajele metode de codare diferite pot fi combinate prin aplicarea codificării concatenate. Atunci când această informație este mai întâi codificată printr-un singur cod, iar apoi celălalt, rezultatul este un cod de produs.
De exemplu, popular design-ul este urmatoarea: datele sunt codificate cod Reed-Solomon, apoi intercalat (cu simbolurile care sunt apropiate, sunt plasate departe unul de altul) și sunt codificate cu un cod convoluțional. La receptor decodifică primul cod convoluțional și apoi efectuat intercalare (erorile de spargere la ieșire de cădere decodor convoluțională în diferite codewords sunt codul Reed-Solomon) și apoi realizată din decodarea cod Reed-Solomon.
Unele coduri sunt proiectate produs special pentru decodare iterativ. în care decodificarea este efectuată în mai multe treceri, fiecare dintre care utilizează informația de cea anterioară. Astfel de coduri sunt numite „turbo-coduri“ și permite o mai mare eficiență, dar decodarea lor necesită o mulțime de resurse.
Evaluarea eficienței codurilor
Eficiența codurilor determinate de numarul de erori care pot corecta una, cantitatea de informații redundante, care necesită adăugarea, și complexitatea codare și decodare (atât un program de calculator hardware și).
Hamming de frontieră și coduri perfecte
Să fie un bloc binar (n, k) corecție cod capacitate t. Apoi, inegalitatea (numită Hamming în străinătate):
Codurile care îndeplinesc această limită cu egalitate, numită perfectă. Pentru coduri perfecte includ, de exemplu, coduri Hamming. De multe ori folosit în codul practică cu o capacitate ridicată de corectare a erorilor (cum ar fi codurile Reed-Solomon) nu sunt perfecte.
câștig de energie
Deoarece codificarea permite corecta erorile fără zgomot atunci când puterea emițătorului folosită poate fi redusă, lăsând rata de transmitere a datelor neschimbate. câștig de energie este definit ca valoarea diferenței \ Frac, în prezența și absența codului. Aici Eb - energie biți (semnal de putere, împărțit la viteza de transfer de informații), și N0 - zgomot densitate spectrală a puterii.
Utilizarea codurilor corectoare de erori
se utilizează coduri corectoare de erori:
Codurile, detectarea erorilor, sunt utilizate în protocoale de rețea de diferite niveluri.