Cod ciclic

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 28 ianuarie 2021; verificările necesită 2 modificări .

Un cod ciclic este un cod bloc liniar care are proprietatea de ciclicitate, adică fiecare permutare ciclică a unui cuvânt de cod este, de asemenea, un cuvânt de cod. Folosit pentru a transforma informațiile pentru a le proteja de erori (consultați Detectarea și corectarea erorilor ).

Introducere

Fie un cuvânt de lungime n peste un alfabet de elemente dintr- un câmp finit și un polinom corespunzător acestui cuvânt într-o variabilă formală . Se poate observa că această corespondență este un izomorfism al spațiilor liniare. Deoarece „cuvintele” constau din litere din câmp, acestea pot fi adăugate și înmulțite (element cu element), iar rezultatul va fi în același câmp. Polinomul corespunzător combinației liniare a perechii de cuvinte și este egal cu combinația liniară a polinoamelor acestor cuvinte . ${\overline {y}}=(y_{0},y_{1},\dots,y_{n-1})\in L^{n}$ $L=GF(q)$ $y(x)=y_{0}+y_{1}x+y_{2}x^{2}+\dots +y_{n-1}x^{n-1)$ $X$ ${\overline {y}}=m_{1}{\overline {y_{1}}}+m_{2}{\overline {y_{2}}}$ ${\overline {y_{1}}}=(y_{1,0},\dots, y_{1,n-1})$ ${\overline {y_{2}}}=(y_{2,0},\dots, y_{2,n-1})$ ${y}(x)=\sum _{k=0}^{n-1}(m_{1}y_{1k}+m_{2}y_{2k})x^{k}=m_ {1}{\overline {y_{1}}}(x)+m_{2}{\overline {y_{2}}}(x)$

Acest lucru ne permite să considerăm mulțimea de cuvinte de lungime n peste un câmp finit ca un spațiu liniar de polinoame cu gradul cel mult n − 1 peste câmpul . $GF(q)$

Descriere algebrică

Dacă este un cuvânt cod obținut printr-o deplasare ciclică cu un bit la stânga față de cuvânt , atunci polinomul corespunzător acestuia se obține din cel anterior prin înmulțirea cu x : $\overrightarrow {c_{1}}$ $\overright arrow {c}$ $c_{1}(x)$

c_{1}(x)=xc(x)\mod (x^{n}-1)

, folosind faptul că

x^{n}\equiv 1\mod (x^{n}-1).

Schimbați la dreapta și, respectiv, la stânga, pe biți: $j$

c_{j}(x)=x^{j}c(x)\mod (x^{n}-1),

c_{-j}(x)x^{j}=c(x)\mod (x^{n}-1).

Dacă este un polinom arbitrar peste câmpul și este un cuvânt de cod al unui cod ciclic , atunci este și un cuvânt de cod al acestui cod. $m(x)$ $GF(q)$ $c(x)$ $(n,k)$ $m(x)c(x)\mod (x^{n}-1)$

Generarea polinomului

Definiție

Un polinom generator al unui cod ciclic este un astfel de polinom diferit de zero din , al cărui grad este cel mai mic și coeficientul la cel mai înalt grad . $(n,k)$ $C$ $g(x)=\sum \limits _{i=0}^{r}g_{i}x^{i)$ $C$ $g_{r}=1$

Teorema 1

Dacă este un cod ciclic și este polinomul său generator, atunci gradul este , iar fiecare cuvânt de cod poate fi reprezentat în mod unic ca $C$ $(n,k)$ $g(x)$ $g(x)$ $r=nk$

c(x)=m(x)g(x),

unde gradul este mai mic sau egal cu . $m(x)$ $k-1$

Teorema 2

$g(x)$ — polinom generator al codului ciclic — este un divizor al binomului . $(n,k)$ $x^{n}-1$

Consecințe

Astfel, orice polinom divizor poate fi ales ca polinom generator . Gradul polinomului selectat va determina numărul de simboluri de verificare , numărul de simboluri de informare . $x^{n}-1$ $r$ $k=nr$

Generarea matricei

Polinoamele sunt liniar independente, altfel pentru nenule , ceea ce este imposibil. $g(x),xg(x),x^{2}g(x),\dots ,x^{k-1}g(x)$ $m(x)g(x)=0$ $m(x)$

Deci, cuvintele cod pot fi scrise, ca și pentru codurile liniare, după cum urmează:

{\overline {m}}G=(m_{0},m_{1},\dots,m_{k-1}){\begin{bmatrix}g(x)\\xg(x)\ \\dots \\x^{k-1}g(x)\end{bmatrix}}=m(x)g(x),

unde este matricea generatoare , este polinomul informațional . $G$ $m(x)$

Matricea poate fi scrisă sub formă simbolică: $G$

G={\begin{bmatrix}g_{0}&g_{1}&\dots &g_{r-1}&g_{r}&0&\dots &0\\0&g_{0}&\dots &g_{r-2 }&g_{r-1}&g_{r}&\dots &0\\\vdots &\vdots &\ddots &\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&\dots &0&g_{0}&g_ {1}&\dots &g_{r}\end{bmatrix}}.

Verificați matricea

Pentru fiecare cuvânt de cod al unui cod ciclic, . Prin urmare, matricea de verificare poate fi scrisă ca $c(x)=0\mod g(x)$

H={\begin{bmatrix}1&x&x^{2}&\dots &x^{n-2}&x^{n-1}\\\end{bmatrix}}\mod g(x).

Apoi

{\overline {c}}H^{T}=\sum \limits _{i=0}^{n-1}c_{i}x^{i}=0\mod g(x).

Codificare

Nesistematic

Cu codificarea nesistematică, cuvântul de cod este obținut ca produs al unui polinom informațional de unul generator:

c(x)=m(x)g(x).

Se poate realiza prin înmulțirea polinoamelor.

Sistematic

Cu codificarea sistematică, cuvântul cod este format sub forma unui subbloc de informații și a unei verificări:

c(x)=[s(x)\;m(x)].

Lăsați cuvântul informațional să formeze cele mai mari puteri ale cuvântului cod, atunci

c(x)=x^{r}m(x)+s(x),\quad r=nk.

Apoi rezultă din condiție $c(x)=x^{r}m(x)+s(x)=0\mod g(x)$

s(x)=-x^{r}m(x)\mod g(x).

Această ecuație definește regula de codificare sistematică. Poate fi implementat folosind filtre liniare multiciclu (MLF) .

Exemple

Cod binar (7,4,3)

Ca divizor , alegem un polinom generator de gradul al treilea , apoi codul rezultat va avea lungimea , numărul de simboluri de verificare (gradul polinomului generator) , numărul de simboluri informaționale , distanța minimă . $x^{7}-1$ $g(x)=x^{3}+x+1$ $n=7$ $r=3$ $k = 4$ $d=3$

Generarea matricei de cod:

G={\begin{bmatrix}1&1&0&1&0&0&0\\0&1&1&0&1&0&0\\0&0&1&1&0&1&0\\0&0&0&1&1&0&1\end{bmatrix)),

unde prima linie este un polinom cu coeficienți în ordine crescătoare. $g(x)$

Liniile rămase sunt deplasări ciclice ale primei linii.

Verificați matricea :

H={\begin{bmatrix}1&0&0&1&0&1&1\\0&1&0&1&1&1&0\\0&0&1&0&1&1&1\end{bmatrix)),

unde coloana i -a, începând de la prima, este restul împărțirii după polinomul , scris în grade crescătoare, începând de sus. $x^{i-1}$ $g(x)$

Deci, de exemplu, a patra coloană este , sau în notație vectorială . $h_{4}(x)=x^{3}\mod g(x)=x+1$ $[110]$

Este ușor de verificat că . $GH^{T}=0$

Cod binar (15,7,5) BCH

Ca polinom generator , puteți alege produsul a doi divizori : $g(x)$ $x^{15}-1$

g(x)=g_{1}(x)g_{2}(x)=(x^{4}+x+1)(x^{4}+x^{3}+x^{ 2}+x+1)=x^{8}+x^{7}+x^{6}+x^{4}+1.

Apoi fiecare cuvânt de cod poate fi obținut folosind produsul polinomului informațional cu gradul în felul următor: $m(x)$ $k-1$

c(x)=m(x)g(x).

De exemplu, un cuvânt de informare corespunde unui polinom , apoi unui cuvânt cod sau în formă vectorială . ${\overline {m}}=[1000111]$ $m(x)=x^{6}+x^{5}+x^{4}+1$ $c(x)=(x^{6}+x^{5}+x^{4}+1)(x^{8}+x^{7}+x^{6}+x^ {4}+1)=x^{14}+x^{12}+x^{9}+x^{7}+x^{5}+1$ ${\overline {c}}=[100001010100101]$

Vezi și

Link -uri

Mecanisme de control al integrității datelor.