Prin ASAP este de obicei necesară nu numai pentru a transmite mesaje cu o rată de biți dat, dar în același timp, oferă certitudinea necesară.
După primirea mesajului, utilizatorul trebuie să fie foarte sigur că trimiterea acelui mesaj.
Interferența curent în canal este cunoscută pentru a duce la erori. Probabilitatea inițială a unei erori în canalele de comunicare, de obicei, nu se poate atinge un grad ridicat de fiabilitate, fără măsuri suplimentare. Aceste activități, care oferă protecție împotriva erorilor, includ utilizarea codurilor corectoare de erori.
În diagrama structurală generală ASAP sarcină efectuează codificator de protecție de eroare și un decodor de canal, care este uneori denumit RCD.
5.1. Conceptul de coduri de corectare
Să fie o sursă de mesaje cu volumul alfabetului K.
Cu fiecare post n - secvență binară elementară. secvență totală de n - elemente pot fi.
Dacă se utilizează toate secvențele (sau codewords) pentru codificarea mesajului, adică Acestea vor fi permise.
Astfel obținut se numește un simplu cod. el nu este capabil să detecteze și să corecteze erorile.
Pentru ceea ce ar fi codul poate detecta și corecta erorile, următoarea condiție, în timp ce nu este utilizat pentru combinația de transmisie (N0 -K) numite interzise.
apariție eroare într-un cuvânt de cod este detectată în cazul în care combinația juridică a trecut va intra într-unul dintre interzise.
Hamming distanță - caracterizează gradul de diferență este codewords determinată, și numărul de biți nepotrivite în ele.
După ce a trecut prin toate combinațiile posibile de perechi permise în conformitate cu codul de revizuire poate găsi D0 distanța minimă Hamming.
D0 distanța minimă - numită distanța minimă
Distanța minimă determină capacitatea de cod pentru a detecta și corecta erorile.
Un simplu cod D0 = 1 - nu detecta și corecta erorile. Ca orice greșeală se traduce o combinație admisibilă la alta.
În, următoarele relații generale
- să prezinte capacitatea de a # 9, # 9;
coduri liniare
Codul de bloc binar este liniar dacă modulo 2 suma a două cuvinte cod este, de asemenea, un cuvânt de cod.
Codurile liniare numitului grup.
Multitudinea de elemente din operațiuni de grup definit pe ea se numește un grup, dacă sunt îndeplinite următoarele condiții:
1. Închiderea g j = Gi gk G, ca urmare a funcționării cu cele două elemente ale treilea grup este obținut, de asemenea, aparținând acestui grup.
2. Asociativitatea (asociativitate) (Gi gj) gk = Gi (gj gk)
3. Prezența elementului neutru gj e = gj
4. Prezența elementului invers. Gi (Gl) -1 = e
În cazul în care starea Gl = gj gj Gl. grupul se numește comutativ.
O pluralitate de cod codewords n-element este un grup închis într-o operație de grup predeterminat modulo 2.
Prin urmare, folosind proprietatea de închidere în ceea ce privește funcționarea 2, mulțimea tuturor elementelor pot fi setate nu listează toate elementele și generarea matricei.
Toate celelalte elemente, cu excepția 0, pot fi preparate prin adăugarea modulo 2 linii generatoare de matrice în diferite combinații.
În general, matricea generator de linie poate fi orice liniar independentă, dar este mai ușor și mai convenabil de a lua ca o matrice generator de - unitate.
5.2. coduri ciclice
Practica larg răspândită a fost clasa de coduri liniare, care sunt numite ciclice. Acest nume este derivat din proprietățile de bază ale acestor coduri:
în cazul în care unele aparține unui cuvânt de cod cod ciclic, combinația obținută prin permutare ciclică a combinației inițiale (schimbare ciclică), de asemenea, face parte din acest cod.
O a doua proprietate a tuturor combinațiilor de coduri ciclice permise este divizibilitatea lor fără urmă pe un polinom selectat, numit de generare.
sindrom de eroare în prezența acestor coduri este restul împărțirii primit în generarea cuvântului de cod polinomial.
Aceste proprietăți sunt utilizate în construcția dispozitivelor de codare de cod și de decodare, precum și, de asemenea, pentru detectarea și corectarea erorilor.
Introducere în polinomul cuvânt de cod sub forma
Descrierea codurilor ciclice și construcția acestora este efectuată în mod convenabil utilizând un polinom (sau polinoame).
În teoria codurilor ciclice codewords sunt de obicei prezentate ca un polinom. Astfel, n-elementar poate fi descris cuvânt-cod de un polinom de (n-1), în măsura în forma
in care =, și = 0 corespunde la zero elemente ale combinației a = 1 - nenuli.
Scriem polinoamele pentru combinații specifice 4 elemente
Acțiuni privind polinoame
În formarea combinațiilor de coduri ciclice sunt utilizate adesea operații de polinoame adiție și polinoame diviziune într-un altul. De exemplu,
Trebuie remarcat faptul, că acțiunile privind coeficienții polinomului (plus și de multiplicare) sunt realizate de-modulo 2.
Luați în considerare funcționarea de divizare prin exemplul următor:
Divizarea se efectuează ca de obicei, dar se înlocuiește cu substracție modulo doi.
Rețineți că intrarea în forma polinomial nume de cod, nu determină întotdeauna lungimea cuvântului de cod. De exemplu, când n = 5, polinomul corespunzător este cuvântul de cod 00011.
Algoritmul pentru permis combinația cod ciclic nume de cod al unui cod simplu
Să un polinom care definește capacitatea de corecție a codului și numărul de biți de verificare r, precum combinația originală a unui simplu cod element k sub forma unui polinom.
Este necesar să se determine combinația cod permis unui cod ciclic (n, k).
Pentru a detecta erorile în cuvântul de cod primit este de ajuns să-l împartă în generarea polinom. Dacă se adoptă printr-o combinație de - a autorizat, restul diviziei va fi zero. Un rest nenulă indică faptul că combinația primită conține erori. Conform soldului de spirit (sindrom) poate, în unele cazuri, de asemenea, la concluzia despre natura erorii, locația și rezolva problema.
Formarea bazei (matricea generatoare) codul ciclic
Formarea baza unui cod ciclic este posibilă în cel puțin două moduri.
- Crearea unei matrice de identitate pentru sursa simpla.
- Se determină pentru fiecare element de grup paritate de cod ale cuvântului de cod sursă și pentru a le adăuga la rândurile corespunzătoare ale matricei.
Matricea rezultată este o bază și un cod ciclic. Mai mult decât atât, în acest caz, combinațiile permise în mod clar separabile (adică, elementele de informare și verificare identificate în mod unic).
- Anexați la stânga de QA corespunzător generatorului de cod zerourile polinomului ciclic, astfel încât lungimea permisă a unui cuvânt de cod este egal cu n.
În acest caz, codul va fi inseparabile.
După ce a primit baza de CC, puteți obține toate combinațiile permise, efectuarea modulo 2 codewords de bază în diverse combinații, plus ZERO.
Codurile Cyclic sunt destul de simplu să pună în aplicare, să aibă o capacitate de corecție ridicată (capacitatea de a detecta și corecta eroarea) și acest lucru este recomandat de ITU-T pentru utilizare în PD aparat. Conform recomandării V.41 sistemelor PD cu sistem de operare cod recomandat cu generarea polinomul
Construirea unui cod de codificator ciclic
Luați în considerare codul (9,5), format de polinomul
combinație admisibilă a unui cod ciclic este format din combinația cod simplu (sursă), prin multiplicarea și adăugându-l la R restul (x) prin împărțirea polinomul generatorului.
Pentru a pune în aplicare operațiunea de adăugare utilizează zerouri registru întârziere r-biți.
După cum se poate observa din exemplul, procedura de divizare a unui număr de către un alt binar reduce la adăugarea succesivă de mod2 de compas [10011] cu membrii corespunzători divizibile [10101] și apoi cu un număr binar obținut prin adăugarea prima, cu un al doilea rezultat suplimentar adăugării, etc. . în timp ce numărul de membri ai numărului binar rezultat este mai mic decât numărul de membri ai divizorului.
Acest număr binar va fi restul.
Construcția unui reziduu generator de cod ciclic
Structura dispozitivului efectuează o împărțire polinom de complet determinat de forma polinomului. Există reguli care permit construirea de unic.
Formulăm regulile de construcție din fig.
- Numărul de celule de memorie este un generator de putere polinom r.
- Numărul de sumatoare este una mai mică decât greutatea generatorului polinomului combinație de codificare.
- sumatoare Montarea determinate de polinomul formă generatorului.
Sumatoare pus după fiecare celulă de memorie (de la zero), pentru care există un nenulă termen polinomului. Nu pune după celulă, pentru care nu există nici un polinom corespunzător în elementul și după celula MSB.
4. În bucla de feedback este necesar pentru a pune o cheie furnizează corect elementele sursa de intrare și scoate rezultatele diviziune.
Structurală ciclică de circuit cod encoder (9,5)
Schema bloc completă a codorului este prezentată în următoarea figură. Acesta conține un grup registru întârziere și generator de paritate menționat mai sus.
Luați în considerare activitatea acestui sistem
1. În prima etapă K1 - K2 este închis - deschis. Există o umplere simultană a registrelor de deplasare întârziere și Inf. elemente (senior înainte!) și după 4 cicluri de MSB în celula №4
2. În timpul al cincilea ciclu de ceas K2 - K1 este închis și - din acest punct se deschide reziduu format în fig. În același timp, de ieșire RE este forțat reținerea de biți de date.
5 cicluri (5 până la 9 inclusiv) în linia 5 lăsa toate element de informație. Până în acest moment, în format reziduu fig
3. K2 - se deschide, K1 - și închise în urma informațiilor din elementele rând vor părăsi grupul de control.
4. În același timp, umplerea noua combinație de registre.
A doua variantă de construcție a Comitetului Central al codorului
Cele de mai sus reflectă foarte clar procesul de codificare de divizare numere binare. Cu toate acestea, codorul poate construi conține un număr minim de elemente și anume mai economic.
Aparat pentru divizarea unui polinom de generare poate fi pusă în aplicare în forma următoare:
Pe parcursul a cinci cicluri de aceleași celule în restul de divizare va fi format ca în grupul de paritate formatorului de mai sus. (FPG).
De-a lungul aceleași 5 ceasurile biții de date sunt emise direct la modulator.
În plus, informațiile de cale pentru verificarea celulelor du-te dispozitive de divizare.
Dar este important să dezactivați feedback-ul la momentul retragerii elementelor dovedite, în caz contrar ele vor fi distorsionate.
În cele din urmă, o diagramă bloc a unui codor economic pare.
- În primul ciclu, SW1 și Kl.3 închis, elementele de informare sunt pe codificatorul și elementele de verificare sunt formate în același timp.
- Odată ce o linie părăsește al cincilea element de informație, vor forma un dispozitiv de verificare divizare;
- pe tastele de ceas al șaselea 1 și 3 sunt deschise (feedback-ul rupt), iar cheia 2 este închisă și se lasă nivelul liniei de control.
Celulele sunt umplute cu zerouri, iar circuitul este resetat.
Determinarea unei descărcări eronate în CC
Fie A (x) este un polinom transmis corespunzător cuvintelor de cod.
H (x), - polinomul care corespunde cuvântului de cod recepționat.
Apoi, adăugarea de date polinoame modulo doi va da eroarea polinomial.
Atunci când o singură eroare E (x) va conține doar un singur membru al descărcării eronate corespunzătoare.
Reziduul este - obținut prin împărțirea H polinomul primit (x) pentru generarea Pr (x) egal cu restul obținut prin împărțirea corespunzătoare eroarea E polinomul (x) Pr (x)
Când această eroare în fiecare cifră va corespunde unui rest R (x), (de asemenea, cunoscut sub numele de sindrom), și, prin urmare, a primit sindrom poate determina în mod unic locația unei descărcări eronate.
Algoritmul de detectare a erorilor
Să presupunem că avem un combinații de elemente n (n = k + r) atunci:
1. Ia restul diviziunii E (x), care corespunde unei erori de biți ridicată [1000000000], pentru formarea unui Pr log (x)
2. Se împarte rezultante h polinomul (x) Pr (x) și se obține curent rest R (x).
3. Compara R0 (x) și R (x).
- Dacă acestea sunt egale, atunci a apărut o eroare în cifre semnificative.
- Dacă „nu“, atunci vom crește gradul de acceptare al polinomului pe X și apoi efectuați diviziunea
c) Din nou pentru a compara reziduul obținut R0 (x)
- Dacă acestea sunt egale, atunci eroarea din a doua categorie.
- Dacă nu, atunci se multiplica h (x) 2 și repetarea acestor operații până când R (X) nu este egal cu R0 (x).
Eroarea va fi într-o descărcare corespunzătoare numărului la care gradul ridicat de h (x) plus unu.
De exemplu: numărul de descărcare eronate 3 + 1 = 4
Combinații de decodificare EXEMPLU CC
Să presupunem că combinația obținută H (x) = 111011010
Să-l analizăm, în conformitate cu algoritmul de mai sus.
Prin implementarea algoritmului de detectare a erorilor, determinăm restul vectorului eroare divizare corespunzătoare bit high X 8 proizvodyashy polinomului P (x) = X 4 + X + 1
X 8 + X + 5 x 4 x 4 + x + 1
Se împarte secvența primită de polinomul generator de
S-a obținut în fragmentul ciclu de 9 așa cum se vede nu este egal cu R0 (X). Mijloacele trebuie să fie multiplicate cu secvența primită la diviziunea X și se repetă. Cu toate acestea, fisiunea de la 5 până la 9 cicluri inclusive sunt aceleași, de aceea este necesar să se continue să se împartă după ciclul de ceas al nouălea, atâta timp cât soldul nu este R0 (X). În cazul nostru, acest lucru va avea loc la un ciclu de ceas de 10, în cazul în care creșterea eroarea la 1. Apoi, în a doua descărcare.
cod ciclic decodor de corectare a erorilor
Dacă eroarea în prima cifră, apoi reziduul R0 (X) = 10101 apariție după ciclul nouă în celulele smochinelor.
În cazul în care al doilea cel mai mare după al 10-lea;
a treia cea mai mare-după 11-lea;
a patra cea mai mare după-al 12-lea
a cincea cea mai mare după 13-lea
în al șaselea cel mai mare după a 14-a
în a șaptea, cea mai mare după data de 15
în a opta cea mai mare după a 16-a
în cea mai mare nouă după-the 17-lea.
La ciclu de ceas 10 lăsând registru semnificativ bit întârziere și trece printr-un modulo-2 vipera.
Dacă acest timp reziduul în fig = R0 (X), logica 1 ieșire de la decodorul merge la o a doua intrare a sumatorului și MSB este inversat.
În cazul nostru, inversat de-al doilea ciclu de ceas 11 de descărcare.
5.3. Alegerea polinomului generator
Să considerăm alegerea polinomului generator, care definește proprietățile corective ale codului ciclic. În teoria codurilor ciclice arătat că polinomul generatorului este un produs al așa-numitului mi (x) polinoamelor minimale. sunt factorii principali (care este divizibil doar prin ele însele și 1) din binomial x n + 1:
Există tabele speciale de polinoame minime, dintre care una este prezentată mai jos. In plus polinomului generator trebuie găsit și numărul de biți de paritate r. Acesta este determinat din următoarea proprietate de coduri ciclice:
pentru toate valorile l și ti.osh există un cod ciclic de lungime n = 2 l - 1, corectarea tuturor erorilor ti.osh multiplicitate sau mai puțin și care nu conțin mai multe elemente de screening.
Deoarece, atunci de la # 9 ;. (**)
Evident, în scopul de a reduce codewords timp de transmisie, r trebuie să fie ales cât mai mic posibil. Să presupunem, de exemplu, lungimea codului n = 7 combinații multiplicitatea erorilor corectate ti.osh = 1. Din (**) randamentele r = 1. log2 (1 + 7) = 3.
După determinarea numărului de biți de paritate r. calcularea polinomul generatorului care se realizează cu ajutorul tabelului de minim polinoame prezentate în forma următoare:
Tabelul polinoame minimal