Informații comună privind construcția codurilor 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, și anume, dacă un anumit cuvânt de cod aparține unui cod ciclic, combinația obținută prin permutarea ciclică a combinației inițiale (deplasare 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.
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.
Codurile Cyclic - este o întreagă familie de coduri corectoare de erori, care include unul dintre soiurile de coduri Hamming, dar oferă, în general, o mai mare flexibilitate în ceea ce privește fezabilitatea codului cu capacitatea necesară pentru a detecta și corecta erorile care apar în timpul transmiterii codewords printr-un canal de comunicare. Codul Cyclic se referă la blocul sistematic -codurile, unde k primi biți sunt o combinație a codului primar, iar ulterior (n k.) (n - k) biții sunt o paritate.
Baza construcției codurilor ciclice este o operațiune de divizare pe cuvântul de cod transmis generează un polinom ireductibil de grad r. Restul diviziunii este folosită în formarea de biți de paritate. În această operațiune diviziune este precedată de operația de înmulțire, efectuează o deplasare k-bit cuvânt de cod informațional stânga la r biți.
Atunci când decodificarea n-biți a primit din nou împărțirea cuvântului de cod de polinomul generator de.
sindrom de eroare în prezența acestor coduri este restul împărțirii primit în generarea cuvântului de cod polinomial. În cazul în care sindromul este zero, se consideră că nu există erori. In caz contrar, folosind sindromul primit poate determina numărul de descărcare primit în care a cuvintelor de cod a apărut o eroare și corectați-l.
Cu toate acestea, nu este exclusă posibilitatea de a mai multor codewords din greșeală, care pot provoca corecturi false și / sau erori de detecție atunci când transformarea uneia combinații permise la alta.
Fie numărul total de biți din blocul este egal cu n. inclusiv informații utile transporta m biți, apoi, în caz de eșec este posibil să se stabilească s biți. Dependența s poate fi găsit [6] n și m pentru codurile din tabel:
n. numărul total de biți
m. numărul de biți utili
s. numărul de biți corectate
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). Înregistrarea combinație ca un polinom necesar pentru a afișa un mod formal operațiune deplasare ciclică cuvântului de cod original. Astfel, n -Element poate fi cuvânt-cod este descris de un polinom de (n - 1) măsura în forma:
A n -1 (x) = a n -1 x n -1 + o -2 x n n -2 + ... + 1 x + un 0.
în cazul în care un i =, și i = 0 corespunde la zero elemente ale combinației, o i = 1 - nenul.
Scriem polinoamele pentru combinații specifice de 4 elemente:
1101 ↔ A 1 (x) = x 3 + x 2 + 1
1010 ↔ A 2 (x) = x 3 + x
operații de adunare și scădere sunt efectuate modulo 2. Ele sunt echivalente și asociative:
Operațiunea este polinoamele convenționale diviziune divizare, ci utilizează modulo scădere 2 plus:
Ciclică schimbare Cuvântul de cod
Ciclic model de cod de deplasare - se deplasează de la dreapta la stânga a elementelor sale, fără a perturba ordinea lor, astfel încât stânga element ia locul extremei drepte.
Proprietățile de bază și denumirea codurilor ciclice asociate cu faptul că toate combinațiile permise de biți în mesajul transmis (cuvintele cod) pot fi obținute printr-o operație de schimbare de pornire cuvânt de cod ciclic.
Să presupunem că dat inițial și cuvânt de cod polinomul corespunzător:
a (x) = a n x n -1 + a n -1 x n -2 + ... + a 2 x + 1
Multiplicând a (x) la x:
a (x) = a · x n x n + a n -1 x n -1 + ... + a 2 x 2 + a 1 x
Deoarece măsura maximă în x lungime n este nume de cod nu este mai mare decât (n - 1), este necesar să se scade un n (x n - 1) din partea dreaptă a expresiei obținute pentru polinomul original. Scadere unui n (x n - 1) este de a lua modulo reziduu (x n - 1).
Deplasarea combinației originale la i cicluri pot fi reprezentate după cum urmează: a (x) · x i - a n (x n - 1), adică prin multiplicarea unei (x) la x i și luând modulo reziduu (x n - 1). Luând echilibrul necesar în obținerea polinomul de grad mai mare sau egal cu n.
generatoare de polinomul
Ideea construcției codurilor ciclice, bazate pe utilizarea polinoame ireductibile. Se numește polinom ireductibil care nu poate fi reprezentat ca un produs de polinoame de grad mai mic, m. E. Un polinom divizibil numai prin ea însăși sau de către o unitate care nu este divizibil cu nici un alt polinom. La un polinom divizibil binom x n + 1. Polinoamele ireductibile în teoria codurilor ciclice acționează ca generatoare polinoame.
Revenind la definiția dată de cod ciclic și operațiunile de înregistrare a combinațiilor de coduri de deplasare ciclice, este posibil să se înregistreze o matrice generator de cod ciclic, după cum urmează:
p (x)
p (x) · x - C 2 (x n - 1)
p (x) · x 2 - C 3 (x n - 1)
...
p (x) · x m -1 - C m (x n - 1)
unde p (x) - cuvântul de cod inițial, pe baza căreia a obținut tot restul de (m - 1) combinația de bază, C i = 0 sau C i = 1 ( "0" în cazul în care gradul de rezultat al polinomiale p (x) · xi să nu depășească (n - 1), "1" dacă este mai mare).
Combinația de p (x) numit un generator de (generator, generator) combinație. adevărat suficient pentru construirea unui cod ciclic pentru a selecta p (x). Apoi, toate celelalte sunt obținute cuvintele de cod fel ca în codul de grup.
Generarea polinomului trebuie să îndeplinească următoarele cerințe:
- p (x) trebuie să fie nenul;
- p greutate (x) nu trebuie să fie mai mică decât distanța minimă de cod: v (p (x)) ≥ d min;
- p (x) ar trebui să aibă un grad maximă k (k - numărul de elemente redundante în cod);
- p (x) ar trebui să fie un divizor al polinomului (x n - 1).
Rularea condiție 4 conduce la faptul că toate codurile de combinatii de coduri ciclice de lucru dobândesc divizibilitatea proprietăți de p (x), fără rest. În acest sens, putem da o altă definiție a unui cod ciclic. Codul Cyclic - cod toate combinațiile de lucru, care sunt împărțite de către generatorul fără urmă.
Pentru a determina gradul de polinomului generator de poate folosi expresia r ≥ log2 (n + 1), unde n - mărimea pachetului transmis la un moment dat, adică o lungime de cod ciclic în construcție ...
Exemple de generare a polinoame pot fi găsite [5] în tabel:
r. gradul de polinomului
P (x), polinomul generator de
111100111, 100011101, 101100011
Algoritmul pentru permis combinația cod ciclic nume de cod al unui cod simplu
Să polinomul P (x) = r x r -1 + r -2 x r -1 + ... + 1, care definește capacitatea de corecție a codului și r numărul de biți de verificare. și combinația inițială simplu k cod -Element sub forma polinomului A k -1 (x).
Este necesar să se determine combinația cod permis unui cod ciclic (n. K).
- Inmultiti polinomul original x cuvânt de cod r.
A k -1 (x) · x r
A k -1 (x) · x r / P r (x) → R (x)
A n -1 (x) = A k -1 (x) · x r + R (x)
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.
Exemplu. Să fie necesar pentru a codifica secvența de tip 1101, ceea ce corespunde A (x) = x 3 + x 2 + 1.
Se determină numărul de simboluri pilot r = 3. Din tabelul ia polinomul P (x) = x 3 + x + 1, t. E. 1011.
Multiplicând A (x) în x r.
A (x) · x = r (x 3 + x 2 + 1) · x 3 = x 6 + x 5 + x 3 → 11010000
Divizarea produsului rezultat prin polinomului generator g (x):
A (x) · xr / P (x) = (x 6 + x 5 + x 3) / (x 3 + x + 1) = x 3 + x 2 + x + 1 + 1 / (x 3 + x + 1) → 1111 + 001/1011
Când împărțirea, să fie conștienți de faptul că scăderea se face modulo 2 însumează echilibrul cu h (x) · x r. Rezultatul este un mesaj codat:
F (x) = (x 3 + x 2 + 1) · (x 3 + x + 1) = (x 3 + x 2 + 1) · x 3 + 1 → 1101001
Cuvântul de cod primit de informații de cod ciclic simbolurile A (x) = 1101 și control al R (x) = 001. Mesajul codificat este împărțit de polinomul generator de fără reziduuri.
Algoritmul de detectare a erorilor
Să presupunem că avem combinație n -Element (n = k + r) atunci:
- Un rest prin divizarea E (x), care corespunde unei erori de biți ridicată [1000000000], prin polinomului generator P r (x):
- Dacă acestea sunt egale, atunci a apărut o eroare în cifre semnificative.
- Dacă nu, crește gradul de acceptare a polinomului de x și apoi efectuați diviziune:
H (x) · x / P r (x) = R (x)
- Dacă acestea sunt egale, atunci eroarea din a doua categorie.
- Dacă nu, atunci înmulțim h (x) · x 2 și repetarea acestor operații până când R (x) nu este egal cu 0 R (x).
Eroarea va fi într-o descărcare corespunzătoare numărului la care gradul ridicat de h (x), plus unu.
De exemplu: H (x) · x 3 P r / (x) = R 0 (x)
om de știință franceză A. Hokvingem (1959) și americanii R. K. Bouz și DK-Roy Chowdhury (1960) a găsit o mare clasă de coduri, care oferă o distanță arbitrară d minimă min ≥ 5. Acestea sunt numite CCB ( Bose-Chaudhuri-Hocquenghem). polinoamele Generator pentru astfel de coduri, în funcție de cerințele lor, pot fi găsite [7] în tabelul de mai jos:
În cazul în care n - numărul total de elemente, m - numărul de elemente de informație, k - numărul de elemente redundante (n = m + k).
Procedeul de construire a codului BCH de dat M și d min.
- găsit de valoare min d, la care a furnizat numărul necesar de elemente informaționale m la redundanță minimă k min;
- găsit în tabelul corespunzător unui polinom generator de;
- dacă d min este chiar, polinomul înmulțiți găsit la (x + 1);
- dacă este specificat m >> Table m. este posibil să se deplaseze într-un cod ciclic scurtat, lovind în cod matrice sursă generatoare cu parametrii m Tabel. k min (m Tabele - m set) coloane pe stânga și același număr de rânduri de mai sus.
Visualizer
Vezi Visualizer o metodă de construire a codului ciclic aici.
Privire de ansamblu asupra surselor
În [1], [2] și la [3] și [4] prezintă detaliile teoretice, metodele de construcție, precum și exemple de coduri ciclice.
Pe site-urile web, [5], [6], [7], în principal, pentru investigații practice, unele dintre ele, în funcție de masa de interese și coduri ciclice.
literatură
Există câteva note despre erorile.
>>> Tabelul BCH, preluate de pe site-ul de mai sus.
25 31 11 5 11 5423325 101100010011011010101
probabil să conțină o eroare într-un prim număr de - în loc de 25 ar trebui să fie de 20 (prin definiție, k = kolichestvo_bit_v_polinome - 1, și, de asemenea, trebuie să îndeplinească condiția k + m = n).