Teoria de codificare de corectare a erorilor se bazează pe rezultatele studiilor efectuate de Claude Shannon. El a formulat teorema pentru canal discret cu zgomot: pentru orice transmitere a simbolurilor binare viteză mai mică decât capacitatea de canal, există un cod în care probabilitatea de decodare este arbitrar mic.
Construirea de astfel de cod este atins prin introducerea redundanță. Aceasta este, prin aplicarea codului de a transmite informații, care nu utilizează toate combinațiile posibile, dar numai unele dintre ele, vă puteți îmbunătăți imunitatea de zgomot de la recepție.
Aceste coduri sunt numite redundante sau de corecție. Proprietăți corective Regulile privind codul de redundanță depinde de construcția acestor coduri și parametrii de cod (durata simbolurilor, numărul de biți, disponibilizare etc.).
Tot soiul utilizat în practica codurilor corectoare de erori pot fi împărțite în două clase fundamental diferite [4]:
1. Bloc (sau bloc) coduri. La utilizarea codurilor bloc, informațiile digitale sunt transmise sub formă de codewords individuale (bloc) de lungime egală. Codificarea și decodificarea fiecărui bloc este realizată în mod independent, adică fiecare literă corespunde mesaj bloc de n simboluri. Codul de bloc se numește uniform. în cazul în care n (atomicitate) rămâne aceeași pentru toate literele mesajului.
2. Codurile continue (adesea numite recurente, dendritic), a căror folosire o secvență de simboluri de informație este prelucrată în codor, fără nici o partiție prealabilă în fragmente separate.
Distinge între codurile bloc separabile și inseparabile.
Atunci când codifică coduri separabile Opcodes constau din două părți separabile: Informații și verificări. Informații și a codului de verificare biți în toate combinațiile de cod separabile ocupă aceeași poziție.
Când codifică codurile inseparabile diviza simboluri ale secvenței de ieșire a informațiilor și verificarea imposibilă.
Codurile Vnepreryvnyh care administrează simboluri redundante în secvența codificată a simbolurilor de informație este realizată în mod continuu, fără împărțire în blocuri separate. Codurile continue pot fi, de asemenea separabile și inseparabile.
Principii generale de utilizare a redundanței. Capacitatea de cod pentru a detecta și corecta erorile datorită prezenței simbolurilor redundante. La intrarea în codificatorul primește o secvență de simboluri de informații k binare. La ieșire corespunde unei secvențe de n simboluri binare, în care n> k. Pot exista mai multe secvențe și diferite secvențe de ieșire de intrare. Doar secvențe corespund intrare din numărul total de secvențe de ieșire. Budemnazyvat combinațiile lor cod valid. sunt utilizate secvențele posibile de ieșire pentru transmisie - Restul de (). Acestea vor fi numite interzise cuvintele de cod.
Eronată a informațiilor, în timpul transmiterii se reduce la faptul că unele dintre personajele de transmisie sunt înlocuite cu altele - necredincioși. Fiecare dintre combinațiile permise ca rezultat al interferenței pot fi transformate în orice alta. Pot exista cazuri · posibile. Acest număr include:
- cazuri de transmitere fără erori;
- · (-1) cazuri de transfer de alte combinații permise care corespunde erori nedetectabile;
- · - cazuri nerezolvate, tranziția în combinațiile care pot fi detectate ().
Este găsit de multe ori modele de coduri de defecte din numărul total de cazuri posibile de transmitere corespunde:
Să considerăm, de exemplu, prezintă abilitatea de a codifica fiecare dintre acestea cuprinde o combinație de un singur simbol redundant (n = k + 1). Numărul total de secvențe de ieșire va fi. adică de două ori numărul total de secvențe de intrare codificate. Pentru un subset al codewords poate fi permis să ia, de exemplu, un subset de combinații care conțin un număr par de cele (sau zerouri).
Când codifică un simbol (0 sau 1) se adaugă la fiecare secvență de simboluri de informații k, astfel încât numărul celor în chiar cuvântul codificat. Denaturarea orice număr par de caractere permise într-un cuvânt de cod se traduce subset interzise combinații, care este detectat la sfârșitul primirea număr impar de cele. O parte din erorile detectate sunt:
EXEMPLU de verificare a parității codificator este prezentată în Fig. 15.
Principalii parametri ai codurilor corectoare de erori. Parametrii majore ce caracterizează proprietățile codurilor de corecție sunt redundanța codului. distanta de cod. numărul de erori detectate și corectate. Luați în considerare esența acestor parametri.
Redundanța cod corectare poate fi absolută și relativă. Prin redundanță absolută înțelege numărul de biți de intrare suplimentar
Figura 15 - Un codificator cu paritate de control
Corectarea valorii relative redundanța codului se numește
. Această valoare indică cât de mult din numărul total de combinații de simboluri este de simboluri de informații. Este, de asemenea, numit viteza relativă de transmitere a informațiilor.
Dacă performanța sursă este N simboluri pe secundă, atunci rata de transmisie după codificarea acestor informații este egal cu
ca și în secvența de n k caractere numai informații.
În cazul în care numărul de erori care trebuie să fie detectate sau corectate în mod semnificativ, trebuie să aveți un cod cu un număr mare de simboluri de verificare. Viteza de transfer de date va fi redus în același timp există o informație de întârziere de sincronizare. Este mai mare, codarea mai complexă.
Distanța de cod Gradul caracterizează diferența dintre oricare două cuvinte de cod. Este exprimată prin numărul de caractere care sunt o combinație de diferite una de alta.
Pentru a obține distanța minimă între două combinații de cod binar, este suficient pentru a contoriza numărul de unități din valoarea acestor combinații este un modulo-2.
Distanța minimă poate fi diferită. Astfel, în distanța fizică primară cod breakeven pentru diferite combinații poate varia de la unu la n. cod egal cu valori.
Numărul de erori detectate este determinată de distanța minimă dintre codewords. Această distanță se numește Hamming.
toate combinațiile sunt permise în codul nonredundant,
= 1. Ai distorsionat doar un singur caracter, și există o eroare în mesaj.
Teorema. Pentru cod are proprietăți pentru a detecta erorile unice, trebuie să introduceți redundanța care ar asigura o distanță minimă între oricare două combinații permise de cel puțin două.
Dovada. Ia codul Atomicitate n = 3. Combinații posibile de cod formă naturală următoarele set: 000, 001, 010, 011, 100, 101, 110, 111. Orice singură eroare transformă această secvență într-o altă secvență permisă. Eroarea nu este detectată și nu sunt corectate, ca = 1. Dacă = 2, nici unul dintre cuvintele de cod permise atunci când o singură eroare nu este transferat într-o altă combinație legală.
Lăsați un subset al combinațiilor permise formate pe principiul parității numărului de unități. Apoi, un subset de combinații permise și interzise sunt după cum urmează:
000, 011, 101, 110 - combinații permise;
001, 010, 100, 111 - interzis combinație.
Este evident că obstacolul denaturare a descărcării (o singură eroare) are ca rezultat o tranziție în combinații interzise combinație subset. Aceasta este, codul detectează toate erorile singulare.
In general, multitudinea erorilor de detecție, dacă este necesar - distanța minimă Hamming trebuie să fie de cel puțin o mai mare. care este
În acest caz, nici o multiplicitate de eroare poate să traducă o combinație admisibilă la alta.
Erori nu numai că poate detecta, dar, de asemenea, corectă.
Teorema. Pentru a corecta o singură eroare fiecare combinație de cod permis pe care doriți să hartă un subset de combinații de coduri ilicite. Pentru aceste subseturi nu se suprapun, distanța Hamming ar trebui să fie de cel puțin trei.
Dovada. Să presupunem, ca și în exemplul anterior, n = 3. Să presupunem combinațiile permise 000 și 111 (cod la distanță este între ele egală cu 3). Combinații permise de 000 asociem un subset de combinații interzise 001, 010, 100. Aceste combinații interzise sunt formate ca urmare a unei singure erori în combinația 000.
permisă în mod similar combinație 111 trebuie să fie pus în corespondență cu un subset al combinațiilor interzise 110, 011, 101. Dacă vom compara aceste subseturi de combinații interzise, este evident că acestea nu se suprapun:
In general, multiplicitate erori corectabile asociate cu raportul de cod la distanță
Pentru a determina orientarea necesară pentru un anumit cod de cod de redundanță distanța d poate utiliza estimarea limită superioară pentru r = n - k. numita evaluare Hamming:
în care - combinația dintre cele n elemente ale t (număr de posibile erori în lungimea combinației de multiplicitate t n-bit).
Trebuie remarcat faptul că fiecare cod de corecție specifică nu garantează corectarea oricărei combinații de eroare. Codurile sunt destinate pentru a corecta erorile de combinații, cel mai probabil pentru un anumit link.