Cod ciclic - Cyclic code

În teoria codării , un cod ciclic este un cod de bloc , în care deplasările circulare ale fiecărei cuvinte de cod dau un alt cuvânt care aparține codului. Sunt coduri de corectare a erorilor care au proprietăți algebrice convenabile pentru detectarea și corectarea eficientă a erorilor .

Dacă 00010111 este un cuvânt de cod valid, aplicarea unei deplasări circulare la dreapta dă șirul 10001011. Dacă codul este ciclic, atunci 10001011 este din nou un cuvânt de cod valid. În general, aplicarea unei deplasări circulare dreapta mută bitul cel mai puțin semnificativ (LSB) în poziția cea mai stângă, astfel încât acesta să devină bitul cel mai semnificativ (MSB); celelalte poziții sunt deplasate cu 1 spre dreapta.

Definiție

Fie un cod liniar peste un câmp finit (numit și câmp Galois ) cu lungimea blocului . se numește un cod ciclic în cazul în care , pentru fiecare cuvânt de cod din , cuvântul în obținut printr - o deplasare dreapta ciclică a componentelor este din nou un cuvânt de cod. Deoarece o deplasare ciclică la dreapta este egală cu deplasările ciclice la stânga, un cod ciclic poate fi definit și prin deplasări ciclice la stânga. Prin urmare, codul liniar este ciclic exact atunci când este invariant sub toate deplasările ciclice. ${\ displaystyle {\ mathcal {C}}}$${\ displaystyle GF (q)}$ ${\ displaystyle n}$${\ displaystyle {\ mathcal {C}}}$ ${\ displaystyle c = (c_ {1}, \ ldots, c_ {n})}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle (c_ {n}, c_ {1}, \ ldots, c_ {n-1})}$${\ displaystyle GF (q) ^ {n}}$${\ displaystyle n-1}$${\ displaystyle {\ mathcal {C}}}$

Codurile ciclice au unele constrângeri structurale suplimentare asupra codurilor. Acestea se bazează pe câmpuri Galois și datorită proprietăților lor structurale sunt foarte utile pentru controlul erorilor. Structura lor este puternic legată de câmpurile Galois, din cauza cărora algoritmii de codificare și decodare pentru codurile ciclice sunt eficienți din punct de vedere al calculului.

Structura algebrică

Codurile ciclice pot fi legate de idealuri în anumite inele. Fie un inel polinomial peste câmpul finit . Identificați elementele codului ciclic cu polinoame astfel încât să se mapeze polinomul : astfel multiplicarea corespunde unei schimbări ciclice. Atunci este un ideal în și, prin urmare , principal , deoarece este un inel ideal principal . Idealul este generat de elementul monic unic în grad minim, polinomul generatorului . Acesta trebuie să fie un divizor al . Rezultă că fiecare cod ciclic este un cod polinomial . Dacă polinomul generatorului are grad, atunci rangul codului este . ${\ displaystyle R = A [x] / (x ^ {n} -1)}$${\ displaystyle A = GF (q)}$${\ displaystyle C}$${\ displaystyle R}$${\ displaystyle (c_ {0}, \ ldots, c_ {n-1})}$${\ displaystyle c_ {0} + c_ {1} x + \ cdots + c_ {n-1} x ^ {n-1}}$${\ displaystyle x}$${\ displaystyle C}$${\ displaystyle R}$${\ displaystyle R}$${\ displaystyle C}$ ${\ displaystyle g}$${\ displaystyle x ^ {n} -1}$${\ displaystyle g}$${\ displaystyle d}$${\ displaystyle C}$${\ displaystyle nd}$

Idempotente a este un cuvânt de cod astfel încât (adică, este un element de idempotente a ) și este o identitate pentru codul, adică pentru fiecare cuvânt de cod . Dacă și sunt coprimă, un astfel de cuvânt există întotdeauna și este unic; este un generator de cod. ${\ displaystyle C}$${\ displaystyle e}$${\ displaystyle e ^ {2} = e}$${\ displaystyle e}$${\ displaystyle C}$${\ displaystyle e}$${\ displaystyle e \ cdot c = c}$${\ displaystyle c}$${\ displaystyle n}$${\ displaystyle q}$

Un cod ireductibil este un cod ciclic în care codul, ca ideal este ireductibil, adică este minim , astfel încât polinomul său de verificare este un polinom ireductibil . ${\ displaystyle R}$

Exemple

De exemplu, dacă și , setul de cuvinte de cod conținute în codul ciclic generat de este exact ${\ displaystyle A = \ mathbb {F} _ {2}}$${\ displaystyle n = 3}$${\ displaystyle (1,1,0)}$

${\ displaystyle ((0,0,0), (1,1,0), (0,1,1), (1,0,1))}$.

Corespunde idealului în generat de . ${\ displaystyle \ mathbb {F} _ {2} [x] / (x ^ {3} -1)}$${\ displaystyle (1 + x)}$

Polinomul este ireductibil în inelul polinomial și, prin urmare, codul este un cod ireductibil. ${\ displaystyle (1 + x)}$

Idemotentul acestui cod este polinomul , care corespunde cuvântului de cod . ${\ displaystyle x + x ^ {2}}$${\ displaystyle (0,1,1)}$

Exemple banale

Exemple banale de coduri ciclice sunt ele însele și codul care conține doar cuvântul cod zero. Acestea corespund generatoarelor și respectiv: aceste două polinoame trebuie să fie întotdeauna factori de . ${\ displaystyle A ^ {n}}$${\ displaystyle 1}$${\ displaystyle x ^ {n} -1}$${\ displaystyle x ^ {n} -1}$

De-a lungul biți de paritate codul, format din toate cuvintele de greutate chiar, corespunde la generator . Din nou, acest lucru trebuie să fie întotdeauna un factor al . ${\ displaystyle GF (2)}$${\ displaystyle x + 1}$${\ displaystyle GF (2)}$${\ displaystyle x ^ {n} -1}$

Coduri cvasiciclice și coduri scurtate

Înainte de a aprofunda detaliile codurilor ciclice, vom discuta mai întâi despre codurile cvasiciclice și scurtate, care sunt strâns legate de codurile ciclice și toate pot fi convertite între ele.

Definiție

Coduri cvasiciclice:

Un cod cvasiciclic este un cod de bloc liniar astfel încât, pentru unii care este coprimă , polinomul este un polinom de cuvânt de cod ori de câte ori este un polinom de cuvânt de cod. ${\ displaystyle (n, k)}$ ${\ displaystyle b}$${\ displaystyle n}$${\ displaystyle x ^ {b} c (x) {\ pmod {x ^ {n} -1}}}$${\ displaystyle c (x)}$

Aici, polinomul cuvântului de cod este un element al unui cod liniar ale cărui cuvinte de cod sunt polinoame care sunt divizibile cu un polinom de lungime mai mică numit polinomul generatorului . Fiecare polinom de cuvânt de cod poate fi exprimat sub forma , unde este polinomul generatorului. Orice cuvânt cod al unui cod ciclic poate fi asociat cu un polinom cuvânt cod, și anume . Un cod cvasiciclic egal cu este un cod ciclic. ${\ displaystyle c (x) = a (x) g (x)}$${\ displaystyle g (x)}$${\ displaystyle (c_ {0}, .., c_ {n-1})}$${\ displaystyle C}$${\ displaystyle \ sum _ {i = 0} ^ {n-1} c_ {i} * x ^ {i}}$${\ displaystyle b}$${\ displaystyle 1}$

Definiție

Coduri scurtate:

Un cod liniar se numește cod ciclic adecvat scurtat dacă poate fi obținut prin ștergerea pozițiilor dintr-un cod ciclic. ${\ displaystyle [n, k]}$${\ displaystyle b}$${\ displaystyle (nb, kb)}$

În codurile scurtate, simbolurile informaționale sunt șterse pentru a obține o lungime de bloc dorită mai mică decât lungimea blocului de proiectare. Simbolurile informaționale lipsă sunt de obicei imaginate a fi la începutul cuvântului cod și sunt considerate a fi 0. Prin urmare, - este fixat, și apoi este scăzut, care în cele din urmă scade . Nu este necesar să ștergeți simbolurile de pornire. În funcție de aplicație, uneori pozițiile consecutive sunt considerate 0 și sunt șterse. ${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle n}$

Toate simbolurile care sunt scăpate nu trebuie transmise și la capătul de recepție pot fi reintroduse. Pentru a converti codul ciclic în cod scurtat, setați simbolurile la zero și aruncați-le din fiecare cuvânt de cod. Orice cod ciclic poate fi convertit în coduri cvasiciclice prin scăderea fiecărui simbol în care este un factor de . Dacă simbolurile abandonate nu sunt simboluri de verificare, atunci acest cod ciclic este, de asemenea, un cod scurtat. ${\ displaystyle (n, k)}$${\ displaystyle (nb, kb)}$${\ displaystyle b}$${\ displaystyle b}$${\ displaystyle b}$${\ displaystyle n}$

Coduri ciclice pentru corectarea erorilor

Acum, vom începe discuția codurilor ciclice în mod explicit cu detectarea și corectarea erorilor . Codurile ciclice pot fi utilizate pentru a corecta erorile, cum ar fi codurile Hamming, deoarece codurile ciclice pot fi utilizate pentru corectarea unei singure erori. De asemenea, sunt utilizate și pentru corectarea erorilor duble și a erorilor de rafală. Toate tipurile de corecții ale erorilor sunt prezentate pe scurt în subsecțiunile ulterioare.

Codul (7,4) Hamming are un polinom generator . Acest polinom are un zero în câmpul de extensie Galois la elementul primitiv și toate cuvintele de cod se satisfac . Codurile ciclice pot fi, de asemenea, utilizate pentru a corecta erorile duble pe teren . Lungimea blocului va fi egală cu elementele primitive și ca zerouri în deoarece considerăm cazul a două erori aici, deci fiecare va reprezenta o eroare. ${\ displaystyle g (x) = x ^ {3} + x + 1}$ ${\ displaystyle GF (8)}$${\ displaystyle \ alpha}$${\ displaystyle {\ mathcal {C}} (\ alpha) = 0}$${\ displaystyle GF (2)}$${\ displaystyle n}$${\ displaystyle 2 ^ {m} -1}$${\ displaystyle \ alpha}$${\ displaystyle \ alpha ^ {3}}$${\ displaystyle GF (2 ^ {m})}$

Cuvântul primit este un polinom de grad dat ca ${\ displaystyle n-1}$${\ displaystyle v (x) = a (x) g (x) + e (x)}$

unde poate avea cel mult doi coeficienți diferiți de zero care corespund la 2 erori. ${\ displaystyle e (x)}$

Definim polinomul sindromului , ca restul polinomului atunci când este împărțit la polinomul generatorului, adică ${\ displaystyle S (x)}$${\ displaystyle v (x)}$${\ displaystyle g (x)}$

${\ displaystyle S (x) \ equiv v (x) \ equiv (a (x) g (x) + e (x)) \ equiv e (x) \ mod g (x)}$ca . ${\ displaystyle (a (x) g (x)) \ equiv 0 \ mod g (x)}$

Pentru corectarea a două erori

Lăsați elementele de câmp și să fie cele două numere de locație de eroare. Dacă apare o singură eroare, atunci este egal cu zero și dacă nu apare niciuna, ambele sunt zero. ${\ displaystyle X_ {1}}$${\ displaystyle X_ {2}}$${\ displaystyle X_ {2}}$

Să și . ${\ displaystyle S_ {1} = {v} (\ alpha)}$${\ displaystyle S_ {3} = {v} (\ alpha ^ {3})}$

Aceste elemente de câmp se numesc „sindroame”. Acum, pentru că este zero la elementele primitive și , deci putem scrie și . Dacă spunem că apar două erori, atunci ${\ displaystyle g (x)}$${\ displaystyle \ alpha}$${\ displaystyle \ alpha ^ {3}}$${\ displaystyle S_ {1} = e (\ alpha)}$${\ displaystyle S_ {3} = e (\ alpha ^ {3})}$

${\ displaystyle S_ {1} = \ alpha ^ {i} + \ alpha ^ {i '}}$și . ${\ displaystyle S_ {3} = \ alpha ^ {3i} + \ alpha ^ {3i '}}$

Și aceste două pot fi considerate ca două perechi de ecuații cu două necunoscute și, prin urmare, putem scrie ${\ displaystyle GF (2 ^ {m})}$

${\ displaystyle S_ {1} = X_ {1} + X_ {2}}$și . ${\ displaystyle S_ {3} = (X_ {1}) ^ {3} + (X_ {2}) ^ {3}}$

Prin urmare, dacă cele două perechi de ecuații neliniare pot fi rezolvate, codurile ciclice pot fi utilizate pentru a corecta două erori.

Cod Hamming

Codul Hamming (7,4) poate fi scris ca un cod ciclic peste GF (2) cu generator . De fapt, orice cod binar Hamming de forma Ham (r, 2) este echivalent cu un cod ciclic, iar orice cod Hamming de forma Ham (r, q) cu r si q-1 relativ prim este, de asemenea, echivalent cu un ciclic cod. Având în vedere un cod Hamming de forma Ham (r, 2) cu , setul de cuvinte cod formează un cod ciclic . ${\ displaystyle 1 + x + x ^ {3}}$${\ displaystyle r \ geq 3}$${\ displaystyle [2 ^ {r} -1,2 ^ {r} -r-2,4]}$

Cod Hamming pentru corectarea erorilor individuale

Un cod a cărui distanță minimă este de cel puțin 3, are o matrice de verificare ale cărei coloane sunt distincte și diferite de zero. Dacă o matrice de verificare pentru un cod binar are rânduri, atunci fiecare coloană este un număr binar pe biți. Există posibile coloane. Prin urmare, dacă o matrice de verificare a unui cod binar cu cel puțin 3 are rânduri, atunci poate avea doar coloane, nu mai mult de atât. Aceasta definește un cod, numit cod Hamming. ${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle 2 ^ {m} -1}$${\ displaystyle d_ {min}}$${\ displaystyle m}$${\ displaystyle 2 ^ {m} -1}$${\ displaystyle (2 ^ {m} -1,2 ^ {m} -1-m)}$

Este ușor să definiți codurile Hamming pentru alfabete mari de dimensiuni . Trebuie să definim o matrice cu coloane liniar independente. Pentru orice cuvânt de dimensiune vor exista coloane care sunt multiple între ele. Deci, pentru a obține independență liniară, toate opțiunile non-zero cu unul ca element cel mai non-zero vor fi alese ca coloane. Apoi, două coloane nu vor fi niciodată dependente liniar, deoarece trei coloane ar putea fi liniar dependente, cu distanța minimă a codului ca 3. ${\ displaystyle q}$${\ displaystyle H}$${\ displaystyle q}$${\ displaystyle m}$

Deci, există coloane diferite de zero cu unul ca element cel mai diferit de zero. Prin urmare, un cod Hamming este un cod. ${\ displaystyle (q ^ {m} -1) / (q-1)}$${\ displaystyle [(q ^ {m} -1) / (q-1), (q ^ {m} -1) / (q-1) -m]}$

Acum, pentru codurile ciclice, Să fie element primitiv în și să fie . Atunci și astfel este un zero al polinomului și este un polinom generator pentru codul ciclic de lungime a blocului . ${\ displaystyle \ alpha}$${\ displaystyle GF (q ^ {m})}$${\ displaystyle \ beta = \ alpha ^ {q-1}}$${\ displaystyle \ beta ^ {(q ^ {m} -1) / (q-1)} = 1}$${\ displaystyle \ beta}$${\ displaystyle x ^ {(q ^ {m} -1) / (q-1)} - 1}$${\ displaystyle n = (q ^ {m} -1) / (q-1)}$

Dar pentru , . Și cuvântul primit este un polinom de grad dat ca ${\ displaystyle q = 2}$${\ displaystyle \ alpha = \ beta}$${\ displaystyle n-1}$

${\ displaystyle v (x) = a (x) g (x) + e (x)}$

unde sau unde reprezintă locațiile erorii. ${\ displaystyle e (x) = 0}$${\ displaystyle x ^ {i}}$${\ displaystyle i}$

Dar putem folosi și ca element de indexare a locației erorii. Pentru că avem și toate puterile de la to sunt distincte. Prin urmare , putem determina cu ușurință locația de eroare la excepția cazului în care reprezintă nici o eroare. Deci, un cod Hamming este o singură eroare care corectează codul cu și . ${\ displaystyle \ alpha ^ {i}}$${\ displaystyle GF (2 ^ {m})}$${\ displaystyle g (\ alpha) = 0}$${\ displaystyle v (\ alpha) = \ alpha ^ {i}}$${\ displaystyle \ alpha}$${\ displaystyle 0}$${\ displaystyle 2 ^ {m} -2}$${\ displaystyle i}$${\ displaystyle \ alpha ^ {i}}$${\ displaystyle v (\ alpha) = 0}$${\ displaystyle GF (2)}$${\ displaystyle n = 2 ^ {m} -1}$${\ displaystyle k = nm}$

Coduri ciclice pentru corectarea erorilor de explozie

Din conceptul de distanță Hamming , un cod cu distanță minimă poate corecta orice erori. Dar în multe canale tiparul de eroare nu este foarte arbitrar, apare în segmentul foarte scurt al mesajului. Astfel de erori se numesc erori de explozie . Deci, pentru corectarea unor astfel de erori, vom obține un cod mai eficient cu o rată mai mare din cauza constrângerilor mai puține. Codurile ciclice sunt utilizate pentru corectarea erorilor de explozie. De fapt, codurile ciclice pot corecta și erorile de explozie ciclică, împreună cu erorile de explozie. Erorile de explozie ciclică sunt definite ca ${\ displaystyle 2t + 1}$${\ displaystyle t}$

O explozie ciclică de lungime este un vector ale cărui componente nenule se numără printre componente (ciclice) consecutive, dintre care prima și ultima sunt diferite de zero. ${\ displaystyle t}$${\ displaystyle t}$

In forma polinomială burst ciclică de lungime poate fi descrisă ca cu un polinom de grad cu coeficient nenul . Aici definește modelul și definește punctul de pornire al erorii. Lungimea modelului este dată de deg . Polinomul sindromului este unic pentru fiecare tipar și este dat de ${\ displaystyle t}$${\ displaystyle e (x) = x ^ {i} b (x) \ mod (x ^ {n} -1)}$${\ displaystyle b (x)}$${\ displaystyle t-1}$${\ displaystyle b_ {0}}$${\ displaystyle b (x)}$${\ displaystyle x ^ {i}}$${\ displaystyle b (x) +1}$

${\ displaystyle s (x) = e (x) \ mod g (x)}$

Un cod de bloc liniar care corectează toate erorile de rafală de lungime sau mai puțin trebuie să aibă cel puțin simboluri de verificare. Dovadă: Deoarece orice cod liniar care poate corecta tipul de rafală de lungime sau mai puțin nu poate avea o rafală de lungime sau mai puțin ca cuvânt de cod deoarece, dacă ar avea, o rafală de lungime ar putea schimba cuvântul de cod în model de rafală de lungime , care, de asemenea, ar putea fi obținut făcând o eroare de lungime în toate cuvintele de cod zero. Acum, orice doi vectori care sunt diferiți de zero în primele componente trebuie să provină din co-seturi diferite ale unei matrice pentru a evita diferența lor să fie un cuvânt de cod al rafalelor de lungime . Prin urmare, numărul acestor co-seturi este egal cu numărul de astfel de vectori care sunt . Prin urmare, cel puțin co-seturi și, prin urmare, cel puțin verificați simbolul. ${\ displaystyle t}$${\ displaystyle 2t}$${\ displaystyle t}$${\ displaystyle 2t}$${\ displaystyle t}$${\ displaystyle t}$${\ displaystyle t}$${\ displaystyle 2t}$${\ displaystyle 2t}$${\ displaystyle q ^ {2t}}$${\ displaystyle q ^ {2t}}$${\ displaystyle 2t}$

Această proprietate este cunoscută și sub denumirea de Rieger și este similară cu legătura Singleton pentru corectarea aleatorie a erorilor.

Codurile de incendiu ca limite ciclice

În 1959, Philip Fire a prezentat o construcție de coduri ciclice generate de un produs al unui binom și al unui polinom primitiv. Binomul are forma pentru un număr întreg pozitiv impar . Codul de incendiu este o eroare de explozie ciclică care corectează codul cu polinomul generatorului ${\ displaystyle x ^ {c} +1}$${\ displaystyle c}$${\ displaystyle GF (q)}$

${\ displaystyle g (x) = (x ^ {2t-1} -1) p (x)}$

unde este un polinom prim cu gradul nu mai mic decât și nu se împarte . Lungimea blocului codului de incendiu este cel mai mic număr întreg care împarte . ${\ displaystyle p (x)}$${\ displaystyle m}$${\ displaystyle t}$${\ displaystyle p (x)}$${\ displaystyle x ^ {2t-1} -1}$${\ displaystyle n}$${\ displaystyle g (x)}$${\ displaystyle x ^ {n} -1}$

Un cod de incendiu poate corecta toate erorile de rafală de lungime t sau mai mică dacă nu există două rafale și apar în același set. Acest lucru poate fi dovedit prin contradicție. Să presupunem că există două rafale diferite de zero și de lungime sau mai puțin și se află în același set de coduri. Deci, diferența lor este o cuvânt de cod. Deoarece diferența este un multiplu al acestuia, este și un multiplu al . Prin urmare, ${\ displaystyle b (x)}$${\ displaystyle x ^ {j} b '(x)}$${\ displaystyle b (x)}$${\ displaystyle x ^ {j} b '(x)}$${\ displaystyle t}$${\ displaystyle g (x)}$${\ displaystyle x ^ {2t-1} -1}$

${\ displaystyle b (x) = x ^ {j} b '(x) \ mod (x ^ {2t-1} -1)}$.

Acest lucru arată că este un multiplu de , Deci ${\ displaystyle j}$${\ displaystyle 2t-1}$

${\ displaystyle b (x) = x ^ {l (2t-1)} b '(x)}$

pentru unii . Acum, așa cum este mai puțin decât și este mai puțin decât așa este un cuvânt de cod. Prin urmare, ${\ displaystyle l}$${\ displaystyle l (2t-1)}$${\ displaystyle t}$${\ displaystyle l}$${\ displaystyle q ^ {m} -1}$${\ displaystyle (x ^ {l (2t-1)} - 1) b (x)}$

${\ displaystyle (x ^ {l (2t-1)} - 1) b (x) = a (x) (x ^ {2t-1} -1) p (x)}$.

Deoarece gradul este mai mic decât gradul de , nu se poate diviza . Dacă nu este zero, atunci nu se poate împărți așa cum este mai mic decât și, prin definiție , împarte nu mai puțin de . Prin urmare și este egal cu zero. Asta înseamnă ambele că ambele explozii sunt aceleași, contrar presupunerii. ${\ displaystyle b (x)}$${\ displaystyle p (x)}$${\ displaystyle p (x)}$${\ displaystyle b (x)}$${\ displaystyle l}$${\ displaystyle p (x)}$${\ displaystyle x ^ {l (2t-1)} - 1}$${\ displaystyle l}$${\ displaystyle q ^ {m} -1}$${\ displaystyle m}$${\ displaystyle p (x)}$${\ displaystyle x ^ {l (2t-1)} - 1}$${\ displaystyle l}$${\ displaystyle q ^ {m} -1}$${\ displaystyle l}$${\ displaystyle j}$

Codurile de incendiu sunt cele mai bune coduri de corectare a rafalelor cu o rată ridicată și sunt construite analitic. Ele au o rată foarte mare și când și sunt egale, redundanța este mai mică și egală cu . Prin utilizarea mai multor coduri de incendiu, erorile de rafală mai lungi pot fi, de asemenea, corectate. ${\ displaystyle m}$${\ displaystyle t}$${\ displaystyle 3t-1}$

Pentru detectarea erorilor, codurile ciclice sunt utilizate pe scară largă și se numesc coduri de redundanță ciclică . ${\ displaystyle t-1}$

Coduri ciclice pe transformata Fourier

Aplicațiile transformatei Fourier sunt răspândite în procesarea semnalului. Dar aplicațiile lor nu se limitează doar la câmpurile complexe; Transformatele Fourier există și în câmpul Galois . Codurile ciclice care utilizează transformata Fourier pot fi descrise într-un cadru mai apropiat de procesarea semnalului. ${\ displaystyle GF (q)}$

Transformată Fourier peste câmpuri finite

Transformată Fourier peste câmpuri finite

Transformata Fourier discretă a vectorului este dată de un vector în care, ${\ displaystyle v = v_ {0}, v_ {1}, ...., v_ {n-1}}$${\ displaystyle V = V_ {0}, V_ {1}, ....., V_ {n-1}}$

${\ displaystyle V_ {k}}$= unde, ${\ displaystyle \ Sigma _ {i = 0} ^ {n-1} e ^ {- j2 \ pi n ^ {- 1} ik} v_ {i}}$

${\ displaystyle k = 0, ....., n-1}$

unde exp ( ) este o rădăcină a unității. În mod similar, în câmpul finit, rădăcina unității este element de ordine . Prin urmare ${\ displaystyle -j2 \ pi / n}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle \ omega}$${\ displaystyle n}$

Dacă este un vector peste și este un element de ordine , atunci transformata Fourier a vectorului este vectorul și componentele sunt date de${\ displaystyle v = (v_ {0}, v_ {1}, ...., v_ {n-1})}$${\ displaystyle GF (q)}$${\ displaystyle \ omega}$${\ displaystyle GF (q)}$${\ displaystyle n}$${\ displaystyle v}$${\ displaystyle V = (V_ {0}, V_ {1}, ....., V_ {n-1})}$

${\ displaystyle V_ {j}}$= unde, ${\ displaystyle \ Sigma _ {i = 0} ^ {n-1} \ omega ^ {ij} v_ {i}}$

${\ displaystyle k = 0, ....., n-1}$

Aici este timpul indicele, este frecventa si este spectrul . O diferență importantă între transformata Fourier în câmpul complex și câmpul Galois este că câmpul complex există pentru fiecare valoare , în timp ce în câmpul Galois există doar dacă se împarte . În cazul câmpurilor de extensie, va exista o transformată Fourier în câmpul de extensie dacă se divide pentru unii . În câmpul Galois vectorul domeniului timp este peste câmp, dar spectrul poate fi peste câmpul de extensie . ${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle V}$${\ displaystyle \ omega}$${\ displaystyle n}$${\ displaystyle \ omega}$${\ displaystyle n}$${\ displaystyle q-1}$${\ displaystyle GF (q ^ {m})}$${\ displaystyle n}$${\ displaystyle q ^ {m} -1}$${\ displaystyle m}$${\ displaystyle v}$${\ displaystyle GF (q)}$${\ displaystyle V}$${\ displaystyle GF (q ^ {m})}$

Descrierea spectrală a codurilor ciclice

Orice cuvânt de cod al codului ciclic de lungime de bloc poate fi reprezentat de cel mult un polinom de grad . Codificator său poate fi scris ca . Prin urmare , în domeniul encoder de frecvență poate fi scris ca . Aici spectrul cuvintelor cod are o valoare în, dar toate componentele din domeniul timpului provin . Deoarece spectrul de date este arbitrar, rolul lui este de a specifica acele unde va fi zero. ${\ displaystyle n}$${\ displaystyle c (x)}$${\ displaystyle n-1}$${\ displaystyle c (x) = a (x) g (x)}$${\ displaystyle C_ {j} = A_ {j} G_ {j}}$ ${\ displaystyle C_ {j}}$${\ displaystyle GF (q ^ {m})}$${\ displaystyle GF (q)}$${\ displaystyle A_ {j}}$${\ displaystyle G_ {j}}$${\ displaystyle j}$${\ displaystyle C_ {j}}$

Astfel, codurile ciclice pot fi definite și ca

Având în vedere un set de indici spectrali , ale căror elemente se numesc frecvențe de verificare, codul ciclic este setul de cuvinte peste al căror spectru este zero în componentele indexate de . Orice astfel de spectru va avea componente ale formularului . ${\ displaystyle A = (j_ {1}, ...., j_ {nk})}$ ${\ displaystyle C}$ ${\ displaystyle GF (q)}$ ${\ displaystyle j_ {1}, ..., j_ {nk}}$ ${\ displaystyle C}$ ${\ displaystyle A_ {j} G_ {j}}$

Deci, codurile ciclice sunt vectori în câmp și spectrul dat de transformarea sa Fourier inversă este peste câmp și sunt constrânși să fie zero la anumite componente. Dar fiecare spectru din câmp și zero la anumite componente pot să nu aibă transformări inverse cu componente din câmp . Un astfel de spectru nu poate fi folosit ca coduri ciclice. ${\ displaystyle GF (q)}$${\ displaystyle GF (q ^ {m})}$${\ displaystyle GF (q ^ {m})}$${\ displaystyle GF (q)}$

Următoarele sunt câteva limite ale spectrului codurilor ciclice.

BCH legat

Dacă este un factor pentru unii . Singurul vector în greutate sau mai puțin care are componente consecutive ale spectrului său egal cu zero este vectorul complet zero. ${\ displaystyle n}$${\ displaystyle (q ^ {m} -1)}$${\ displaystyle m}$${\ displaystyle GF (q) ^ {n}}$${\ displaystyle d-1}$${\ displaystyle d-1}$

Hartmann-Tzeng legat

Dacă este un factor de pentru unii și un număr întreg care este coprimă cu . Singurul vector în greutate sau mai puțin ale cărui componente spectrale sunt egale cu zero pentru , unde și , este vectorul complet zero. ${\ displaystyle n}$${\ displaystyle (q ^ {m} -1)}$${\ displaystyle m}$${\ displaystyle b}$${\ displaystyle n}$${\ displaystyle v}$${\ displaystyle GF (q) ^ {n}}$${\ displaystyle d-1}$${\ displaystyle V_ {j}}$${\ displaystyle j = \ ell _ {1} + \ ell _ {2} b (\ mod n)}$${\ displaystyle \ ell _ {1} = 0, ...., ds-1}$${\ displaystyle \ ell _ {2} = 0, ...., s-1}$

Roos legat

Dacă este un factor de pentru unii și . Singurul vector în greutate sau mai puțin ale cărui componente spectrale egale cu zero pentru , unde și ia cel puțin valori în interval , este vectorul complet zero. ${\ displaystyle n}$${\ displaystyle q ^ {m} -1}$${\ displaystyle m}$${\ displaystyle GCD (n, b) = 1}$${\ displaystyle GF (q) ^ {n}}$${\ displaystyle d-1}$${\ displaystyle V_ {j}}$${\ displaystyle j = l_ {1} + l_ {2} b (\ mod n)}$${\ displaystyle l_ {1} = 0, ..., ds-2}$${\ displaystyle l_ {2}}$${\ displaystyle s + 1}$${\ displaystyle 0, ...., d-2}$

Coduri de reziduuri cuadratice

Când primul este un modulo rezidual pătratic primul există un cod rezidual pătratic care este un cod ciclic de lungime , dimensiune și greutate minimă cel puțin peste . ${\ displaystyle l}$${\ displaystyle p}$${\ displaystyle p}$${\ displaystyle (p + 1) / 2}$${\ displaystyle {\ sqrt {p}}}$${\ displaystyle GF (l)}$

Generalizări

Un cod constaciclic este un cod liniar cu proprietatea care pentru o constantă λ dacă ( c ₁ , c ₂ , ..., c _n ) este un cuvânt de cod, atunci așa este și (λ c _n , c ₁ , ..., c _{n -1} ). Un cod negaciclic este un cod constaciclic cu λ = -1. Un cod cvasiciclic are proprietatea că pentru unele s , orice deplasare ciclică a unui cuvânt de cod cu s locuri este din nou un cuvânt de cod. Un cod dublu circulant este un cod cvasiciclic cu lungime uniformă cu s = 2.

Vezi si

• Verificare redundanță ciclică
• Cod BCH
• Cod Reed – Muller
• Cod Golay binar
• Cod Ternary Golay
• Eugene Prange

Note

Referințe

• Blahut, Richard E. (2003), Algebraic Codes for Data Transmission (ediția a doua), Cambridge University Press , ISBN 0-521-55374-1
• Hill, Raymond (1988), Un prim curs în teoria codării , Oxford University Press , ISBN 0-19-853803-0
• MacWilliams, FJ ; Sloane, NJA (1977), Teoria codurilor de corectare a erorilor , New York: North-Holland Publishing, ISBN 0-444-85011-2
• Van Lint, JH (1998), Introducere în teoria codificării , texte postuniversitare în matematică 86 (ediția a 3-a), Springer Verlag , ISBN 3-540-64133-5

Lecturi suplimentare

• Ranjan Bose , Teoria informației, codificare și criptografie , ISBN  0-07-048297-7
• Irving S. Reed și Xuemin Chen, Codificare de control al erorilor pentru rețelele de date , Boston: Kluwer Academic Publishers, 1999, ISBN  0-7923-8528-4 .
• Scott A. Vanstone , Paul C. Van Oorschot , O introducere la corectarea codurilor de erori cu aplicații , ISBN  0-7923-9017-2

linkuri externe

• Note de curs ale lui John Gill (Stanford) - Note nr. 3, 8 octombrie, fișă nr. 9 , EE 387.
• Note de curs ale lui Jonathan Hall (MSU) - Capitolul 8. Coduri ciclice - pp. 100 - 123
• David Terr. „Cod ciclic” . MathWorld .

Acest articol încorporează material din codul ciclic de pe PlanetMath , care este licențiat sub licența Creative Commons Attribution / Share-Alike .