Cod bloc - Block code

În teoria codificării , codurile de blocuri sunt o familie mare și importantă de coduri de corectare a erorilor care codifică date în blocuri. Există un număr mare de exemple pentru coduri bloc, dintre care multe au o gamă largă de aplicații practice. Definiția abstractă a codurilor de blocuri este utilă din punct de vedere conceptual, deoarece permite teoreticienilor de codificare, matematicienilor și informaticienilor să studieze limitările tuturor codurilor de blocuri într-un mod unificat. Astfel de limitări iau adesea forma unor limite care leagă diferiți parametri ai codului blocului, cum ar fi rata și capacitatea sa de a detecta și corecta erorile.

Exemple de coduri bloc sunt coduri Reed-Solomon , coduri Hamming , coduri Hadamard , coduri de largire , codurile Golay și coduri Reed-Muller . Aceste exemple aparțin, de asemenea, clasei de coduri liniare și, prin urmare, sunt numite coduri de bloc liniare . Mai precis, aceste coduri sunt cunoscute sub numele de coduri de bloc algebric sau coduri de bloc ciclice, deoarece pot fi generate folosind polinoame booleene.

Codurile blocului algebric sunt de obicei decodificate greu folosind decodoare algebrice.

Termenul de cod de bloc se poate referi, de asemenea, la orice cod de corectare a erorilor care acționează asupra unui bloc de biți de date de intrare pentru a produce biți de date de ieșire . În consecință, codificatorul de blocuri este un dispozitiv fără memorie . Conform acestei definiții, codurile cum ar fi codurile turbo , codurile convoluționale terminate și alte coduri iterativ decodabile (coduri asemănătoare turbo) ar fi, de asemenea, considerate coduri bloc. Un codificator convoluțional non-terminat ar fi un exemplu de cod non-bloc (fără cadru), care are memorie și este în schimb clasificat ca un cod arbore . ${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle (n, k)}$

Acest articol tratează „codurile blocului algebric”.

Codul blocului și parametrii săi

Codurile de corectare a erorilor sunt utilizate pentru a transmite în mod fiabil date digitale pe canale de comunicare nesigure , supuse zgomotului canalului . Când un expeditor dorește să transmită un flux de date posibil foarte lung folosind un cod de bloc, expeditorul împarte fluxul în bucăți de o anumită dimensiune fixă. Fiecare astfel de piesă se numește mesaj și procedura dată de codul de bloc codifică fiecare mesaj în mod individual într-un cuvânt de cod, numit și bloc în contextul codurilor de bloc. Expeditorul transmite apoi toate blocurile către receptor, care, la rândul său, poate folosi un mecanism de decodare pentru (sperăm) să recupereze mesajele originale din blocurile primite, eventual corupte. Performanța și succesul transmisiei generale depind de parametrii canalului și de codul blocului.

În mod formal, un cod de bloc este o mapare injectivă

${\ displaystyle C: \ Sigma ^ {k} \ to \ Sigma ^ {n}}$ .

Aici, este un finit și nevid set și și sunt numere întregi. Semnificația și semnificația acestor trei parametri și a altor parametri legați de cod sunt descrise mai jos. ${\ displaystyle \ Sigma}$${\ displaystyle k}$${\ displaystyle n}$

Alfabetul Σ

Fluxul de date care trebuie codat este modelat ca un șir peste un anumit alfabet . Dimensiunea a alfabetului este de multe ori scris ca . Dacă , atunci codul de bloc se numește cod de bloc binar . În multe aplicații este util să se considere a fi o putere primă și să se identifice cu câmpul finit . ${\ displaystyle \ Sigma}$${\ displaystyle | \ Sigma |}$${\ displaystyle q}$${\ displaystyle q = 2}$${\ displaystyle q}$${\ displaystyle \ Sigma}$ ${\ displaystyle \ mathbb {F} _ {q}}$

Lungimea mesajului k

Mesajele sunt elemente ale , adică, șiruri de lungime . Prin urmare, numărul se numește lungimea mesajului sau dimensiunea unui cod de bloc. ${\ displaystyle m}$${\ displaystyle \ Sigma ^ {k}}$${\ displaystyle k}$${\ displaystyle k}$

Lungimea blocului n

Lungimea blocului unui cod bloc este numărul de simboluri într - un bloc. Prin urmare, elementele de sunt șiruri de lungime și corespund blocurilor care pot fi recepționate de către receptor. Prin urmare, ele sunt numite și cuvinte primite. Dacă pentru un mesaj , atunci se numește cuvântul cod al . ${\ displaystyle n}$${\ displaystyle c}$${\ displaystyle \ Sigma ^ {n}}$${\ displaystyle n}$${\ displaystyle c = C (m)}$${\ displaystyle m}$${\ displaystyle c}$${\ displaystyle m}$

Rata R

Rata unui cod bloc este definit ca raportul dintre lungimea ei mesaj și lungimea acestuia bloc:

${\ displaystyle R = k / n}$ .

O rată mare înseamnă că cantitatea de mesaj real pe bloc transmis este mare. În acest sens, rata măsoară viteza de transmisie, iar cantitatea măsoară cheltuielile generale care apar datorită codificării cu codul de bloc. Este o simplă informație teoretică pe care rata nu o poate depăși, deoarece datele nu pot fi, în general, comprimate fără pierderi. În mod formal, acest lucru rezultă din faptul că codul este o hartă injectivă. ${\ displaystyle 1-R}$${\ displaystyle 1}$${\ displaystyle C}$

Distanța d

Distanța sau distanța minimă d a unui cod bloc este numărul minim de poziții în care oricare două codewords distincte diferă, iar distanța relativă este fracția . În mod formal, pentru cuvintele primite , să denotăm distanța Hamming între și , adică, numărul de poziții în care și diferă. Apoi distanța minimă a codului este definită ca ${\ displaystyle \ delta}$${\ displaystyle d / n}$${\ displaystyle c_ {1}, c_ {2} \ in \ Sigma ^ {n}}$${\ displaystyle \ Delta (c_ {1}, c_ {2})}$${\ displaystyle c_ {1}}$${\ displaystyle c_ {2}}$${\ displaystyle c_ {1}}$${\ displaystyle c_ {2}}$${\ displaystyle d}$${\ displaystyle C}$

${\ displaystyle d: = \ min _ {m_ {1}, m_ {2} \ in \ Sigma ^ {k} \ atop m_ {1} \ neq m_ {2}} \ Delta [C (m_ {1}) , C (m_ {2})]}$ .

Deoarece orice cod trebuie să fie injectiv , orice două cuvinte de cod nu vor fi de acord în cel puțin o poziție, deci distanța oricărui cod este de cel puțin . În plus, distanța este egală cu greutatea minimă pentru codurile de bloc liniare, deoarece: ${\ displaystyle 1}$

${\ displaystyle \ min _ {m_ {1}, m_ {2} \ in \ Sigma ^ {k} \ atop m_ {1} \ neq m_ {2}} \ Delta [C (m_ {1}), C ( m_ {2})] = \ min _ {m_ {1}, m_ {2} \ in \ Sigma ^ {k} \ atop m_ {1} \ neq m_ {2}} \ Delta [\ mathbf {0}, C (m_ {1}) + C (m_ {2})] = \ min _ {m \ in \ Sigma ^ {k} \ atop m \ neq \ mathbf {0}} w [C (m)] = w_ {\ min}}$ .

O distanță mai mare permite mai multe corecții și detectare a erorilor. De exemplu, dacă luăm în considerare numai erorile care pot schimba simbolurile cuvântului cod trimis, dar niciodată nu le șterg sau le adaugă, atunci numărul de erori este numărul de poziții în care cuvântul cod trimis și cuvântul primit diferă. Un cod cu distanța d permite receptorului să detecteze până la erori de transmisie, deoarece schimbarea pozițiilor unui cuvânt de cod nu poate produce niciodată din greșeală un alt cuvânt de cod. Mai mult, dacă nu apar mai mult de erori de transmisie, receptorul poate decoda în mod unic cuvântul primit într-un cuvânt de cod. Acest lucru se datorează faptului că fiecare cuvânt primit are cel mult un cuvânt de cod la distanță . Dacă apar mai mult de erori de transmisie, receptorul nu poate decoda în mod unic cuvântul primit în general, deoarece ar putea exista mai multe cuvinte de cod posibile. O modalitate prin care receptorul poate face față acestei situații este utilizarea decodificării listei , în care decodorul scoate o listă a tuturor cuvintelor de cod într-o anumită rază. ${\ displaystyle d-1}$${\ displaystyle d-1}$${\ displaystyle (d-1) / 2}$${\ displaystyle (d-1) / 2}$${\ displaystyle (d-1) / 2}$

Notare populară

Notarea descrie un cod de bloc peste un alfabet de dimensiune , cu lungimea blocului , lungimea mesajului și distanța . Dacă codul de bloc este un cod de bloc liniar, atunci parantezele pătrate din notație sunt utilizate pentru a reprezenta acest fapt. Pentru codurile binare cu , indexul este uneori abandonat. Pentru codurile de distanță maximă separabile , distanța este întotdeauna , dar uneori distanța exactă nu este cunoscută, ne-banală de dovedit sau menționată sau nu este necesară. În astfel de cazuri, componenta-poate lipsi. ${\ displaystyle (n, k, d) _ {q}}$${\ displaystyle \ Sigma}$${\ displaystyle q}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle d}$${\ displaystyle [n, k, d] _ {q}}$${\ displaystyle q = 2}$${\ displaystyle d = n-k + 1}$${\ displaystyle d}$

Uneori, în special pentru codurile non-bloc, notația este utilizată pentru codurile care conțin cuvinte de cod de lungime . Pentru codurile bloc cu mesaje de lungime peste un alfabet de dimensiune , acest număr ar fi . ${\ displaystyle (n, M, d) _ {q}}$${\ displaystyle M}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle q}$${\ displaystyle M = q ^ {k}}$

Exemple

Așa cum am menționat mai sus, există un număr mare de coduri de corectare a erorilor care sunt de fapt coduri bloc. Primul cod de corectare a erorilor a fost codul Hamming (7,4) , dezvoltat de Richard W. Hamming în 1950. Acest cod transformă un mesaj format din 4 biți într-un cuvânt de cod de 7 biți prin adăugarea a 3 biți de paritate. Prin urmare, acest cod este un cod bloc. Se pare că este și un cod liniar și că are distanța 3. În notația de mai jos, aceasta înseamnă că codul Hamming (7,4) este un cod. ${\ displaystyle [7,4,3] _ {2}}$

Codurile Reed – Solomon sunt o familie de coduri cu și care sunt o putere primară . Codurile de rang sunt o familie de coduri cu . Codurile Hadamard sunt o familie de coduri cu și . ${\ displaystyle [n, k, d] _ {q}}$${\ displaystyle d = n-k + 1}$${\ displaystyle q}$${\ displaystyle [n, k, d] _ {q}}$${\ displaystyle d \ leq n-k + 1}$${\ displaystyle [n, k, d] _ {2}}$${\ displaystyle n = 2 ^ {k-1}}$${\ displaystyle d = 2 ^ {k-2}}$

Proprietăți de detectare și corectare a erorilor

Un cuvânt de cod ar putea fi considerat ca un punct din spațiul -dimension și codul este subsetul de . Un cod are distanță înseamnă că nu există o altă cuvânt de cod în bila Hamming centrată cu raza , care este definită ca o colecție de cuvinte -dimensionare a căror distanță Hamming până la nu este mai mare de . În mod similar, cu distanța (minimă) are următoarele proprietăți: ${\ displaystyle c \ in \ Sigma ^ {n}}$${\ displaystyle n}$${\ displaystyle \ Sigma ^ {n}}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle \ Sigma ^ {n}}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle d}$${\ displaystyle \ forall c \ in {\ mathcal {C}}}$${\ displaystyle c}$${\ displaystyle d-1}$${\ displaystyle n}$${\ displaystyle c}$${\ displaystyle d-1}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle d}$

• ${\ displaystyle {\ mathcal {C}}}$ poate detecta erori: Deoarece un cuvânt de cod este singurul cuvânt de cod din bila Hamming centrat la sine cu raza , nici un model de eroare sau mai puține erori nu ar putea schimba un cuvânt de cod la altul. Atunci când receptorul detectează că vectorul recepționat nu este un cuvânt cod , erorile sunt detectate (dar nu există nicio garanție de corectare). ${\ displaystyle d-1}$${\ displaystyle c}$${\ displaystyle d-1}$${\ displaystyle d-1}$${\ displaystyle {\ mathcal {C}}}$
• ${\ displaystyle {\ mathcal {C}}}$ poate corecta erorile. Deoarece un cuvânt de cod este singura cuvânt de cod din bila Hamming centrată la sine cu raza , cele două bile Hamming centrate la două cuvinte de cod diferite, respectiv cu ambele raze , nu se suprapun între ele. Prin urmare, dacă considerăm corectarea erorilor ca fiind găsirea cuvântului de cod cel mai apropiat de cuvântul primit , atâta timp cât numărul de erori nu depășește , există o singură cuvânt de cod în bila de ciocănire centrată cu raza , prin urmare toate erorile ar putea fi corectate . ${\ displaystyle \ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor}$${\ displaystyle c}$${\ displaystyle d-1}$${\ displaystyle \ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor}$${\ displaystyle y}$${\ displaystyle \ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor}$${\ displaystyle y}$${\ displaystyle \ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor}$
• Pentru a decoda în prezența a mai mult decât erori, se poate utiliza decodarea listei sau decodarea cu probabilitate maximă . ${\ displaystyle (d-1) / 2}$
• ${\ displaystyle {\ mathcal {C}}}$ poate corecta ștergerile . Prin ștergere înseamnă că este cunoscută poziția simbolului șters. Corectarea ar putea fi realizată prin trecerea decodării: la trecere, poziția ștearsă este umplută cu simbolul și se efectuează corectarea erorilor. Trebuie să existe o trecere prin care numărul de erori nu depășește și, prin urmare, ștergerile ar putea fi corectate. ${\ displaystyle d-1}$ ${\ displaystyle q}$${\ displaystyle i ^ {th}}$${\ displaystyle i ^ {th}}$${\ displaystyle \ textstyle \ left \ lfloor {{d-1} \ over 2} \ right \ rfloor}$

Limitele inferioare și superioare ale codurilor de bloc

Limita de lovire

Există limite teoretice (cum ar fi limita Hamming), dar o altă întrebare este ce coduri pot fi construite de fapt. Este ca ambalarea sferelor într-o cutie în multe dimensiuni. Această diagramă prezintă codurile construibile, care sunt liniare și binare. Cele x axă arată numărul de simboluri protejate k , y axa numărul de simboluri de verificare necesare n-k . Plotate sunt limitele pentru diferite distanțe Hamming de la 1 (neprotejat) la 34. Marcate cu puncte sunt coduri perfecte:

• portocaliu deschis pe axa x : coduri banale neprotejate
• portocaliu pe axa y : coduri de repetare banale
• portocaliu închis pe setul de date d = 3: coduri Hamming clasice perfecte
• roșu închis și mai mare: singurul cod Golay binar perfect

Familia de coduri

${\ displaystyle C = \ {C_ {i} \} _ {i \ geq 1}}$ se numește familie de coduri , unde este un cod cu creștere monotonă . ${\ displaystyle C_ {i}}$${\ displaystyle (n_ {i}, k_ {i}, d_ {i}) _ {q}}$${\ displaystyle n_ {i}}$

Rata familiei de coduri C este definită ca ${\ displaystyle R (C) = \ lim _ {i \ to \ infty} {k_ {i} \ over n_ {i}}}$

Distanța relativă a familiei de coduri C este definită ca ${\ displaystyle \ delta (C) = \ lim _ {i \ to \ infty} {d_ {i} \ over n_ {i}}}$

Pentru a explora relația dintre și , sunt cunoscute un set de limite inferioare și superioare ale codurilor de bloc. ${\ displaystyle R (C)}$${\ displaystyle \ delta (C)}$

Hamming legat

${\ displaystyle R \ leq 1- {1 \ over n} \ cdot \ log _ {q} \ cdot \ left [\ sum _ {i = 0} ^ {\ left \ lfloor {{\ delta \ cdot n-1 } \ over 2} \ right \ rfloor} {\ binom {n} {i}} (q-1) ^ {i} \ right]}$

Singleton legat

Limita Singleton este că suma ratei și distanța relativă a unui cod de bloc nu poate fi mult mai mare de 1:

${\ displaystyle R + \ delta \ leq 1 + {\ frac {1} {n}}}$ .

Cu alte cuvinte, fiecare cod de bloc satisface inegalitatea . Codurile Reed – Solomon sunt exemple non-banale de coduri care satisfac singletonul legat de egalitate. ${\ displaystyle k + d \ leq n + 1}$

Plotkin legat

Pentru , . Cu alte cuvinte ,. ${\ displaystyle q = 2}$${\ displaystyle R + 2 \ delta \ leq 1}$${\ displaystyle k + 2d \ leq n}$

Pentru cazul general, următoarele limite Plotkin sunt valabile pentru oricare cu distanța d : ${\ displaystyle C \ subseteq \ mathbb {F} _ {q} ^ {n}}$

1. Dacă ${\ displaystyle d = \ left (1- {1 \ peste q} \ right) n, | C | \ leq 2qn}$
2. Dacă ${\ displaystyle d> \ left (1- {1 \ over q} \ right) n, | C | \ leq {qd \ over {qd- \ left (q-1 \ right) n}}}$

Pentru orice cod q -ary cu distanță , ${\ displaystyle \ delta}$${\ displaystyle R \ leq 1- \ left ({q \ over {q-1}} \ right) \ delta + o \ left (1 \ right)}$

Gilbert – Varshamov legat

${\ displaystyle R \ geq 1-H_ {q} \ left (\ delta \ right) - \ epsilon}$ , unde , este funcția de entropie q -ary. ${\ displaystyle 0 \ leq \ delta \ leq 1- {1 \ over q}, 0 \ leq \ epsilon \ leq 1-H_ {q} \ left (\ delta \ right)}$${\ displaystyle H_ {q} \ left (x \ right) ~ {\ overset {\ underset {\ mathrm {def}} {}} {=}} ~ -x \ cdot \ log _ {q} {x \ over {q-1}} - \ left (1-x \ right) \ cdot \ log _ {q} {\ left (1-x \ right)}}$

Johnson legat

Definiți . Fie numărul maxim de cuvinte de cod dintr-o minge Hamming cu raza e pentru orice cod de distanță d . ${\ displaystyle J_ {q} \ left (\ delta \ right) ~ {\ overset {\ underset {\ mathrm {def}} {}} {=}} ~ \ left (1- {1 \ over q} \ right ) \ left (1 - {\ sqrt {1- {q \ delta \ over {q-1}}}} \ right)}$
${\ displaystyle J_ {q} \ left (n, d, e \ right)}$${\ displaystyle C \ subseteq \ mathbb {F} _ {q} ^ {n}}$

Apoi avem Johnson Bound  : , în cazul în care ${\ displaystyle J_ {q} \ left (n, d, e \ right) \ leq qnd}$${\ displaystyle {e \ over n} \ leq {{q-1} \ over q} \ left ({1 - {\ sqrt {1- {q \ over {q-1}} \ cdot {d \ over n }}}} \, \ right) = J_ {q} \ left ({d \ over n} \ right)}$

Elias – Bassalygo legat

${\ displaystyle R = {\ log _ {q} {| C |} \ over n} \ leq 1-H_ {q} \ left (J_ {q} \ left (\ delta \ right) \ right) + o \ stânga (1 \ dreapta)}$

Ambalaje sferice și zăbrele

Codurile bloc sunt legate de problema ambalării sferelor care a primit o oarecare atenție de-a lungul anilor. În două dimensiuni, este ușor de vizualizat. Luați o grămadă de bănuți pe masă și împingeți-i împreună. Rezultatul este un model hexagonal ca un cuib de albine. Dar codurile bloc se bazează pe mai multe dimensiuni care nu pot fi vizualizate cu ușurință. Puternicul cod Golay utilizat în comunicațiile spațiale profunde utilizează 24 de dimensiuni. Dacă sunt utilizate ca un cod binar (care este de obicei), dimensiunile se referă la lungimea cuvântului de cod, așa cum este definit mai sus.

Teoria codării folosește modelul de sfere N- dimensionale. De exemplu, câte bani pot fi ambalate într-un cerc pe o masă sau în 3 dimensiuni, câte marmuri pot fi ambalate într-un glob. Alte considerente includ alegerea unui cod. De exemplu, împachetarea hexagonală în constrângerea unei cutii dreptunghiulare va lăsa spațiu gol la colțuri. Pe măsură ce dimensiunile cresc, procentul de spațiu gol crește. Dar la anumite dimensiuni, ambalajul folosește tot spațiul și aceste coduri sunt așa-numitele coduri perfecte. Există foarte puține dintre aceste coduri.

O altă proprietate este numărul de vecini pe care poate avea un singur cuvânt de cod. Din nou, ia în considerare bănuții ca exemplu. Mai întâi împachetăm banii într-o rețea dreptunghiulară. Fiecare bănuț va avea 4 vecini apropiați (și 4 la colțurile care sunt mai departe). Într-un hexagon, fiecare bănuț va avea 6 vecini apropiați. Respectiv, în trei și patru dimensiuni, ambalajul maxim este dat de cele 12 fețe și cele 24 de celule cu 12 și respectiv 24 de vecini. Când mărim dimensiunile, numărul vecinilor din apropiere crește foarte rapid. În general, valoarea este dată de numerele de sărut .

Rezultatul este că crește și numărul de modalități prin care zgomotul îl determină pe receptor să aleagă un vecin (deci o eroare). Aceasta este o limitare fundamentală a codurilor de bloc și, într-adevăr, a tuturor codurilor. Poate fi mai greu să cauzezi o eroare unui singur vecin, dar numărul vecinilor poate fi suficient de mare, astfel încât probabilitatea totală de eroare să fie de fapt suferită.

Vezi si

• Capacitatea canalului
• Teorema Shannon – Hartley
• Canal zgomotos
• Listă decodare
• Ambalarea sferei

Referințe

• JH van Lint (1992). Introducere în teoria codării . GTM . 86 (ediția a II-a). Springer-Verlag. p.  31 . ISBN   3-540-54894-7 .
• FJ MacWilliams ; NJA Sloane (1977). Teoria codurilor de corectare a erorilor . Nordul Olandei. p.  35 . ISBN   0-444-85193-3 .
• W. Huffman; V.Pless (2003). Bazele codurilor de corectare a erorilor . Cambridge University Press. ISBN   978-0-521-78280-7 .
• S. Lin; DJ Jr. Costello (1983). Codificarea controlului erorilor: elemente de bază și aplicații . Prentice-Hall. ISBN   0-13-283796-X .

linkuri externe

• Charan Langton (2001) Concepte de codare și codare bloc