Verificați matricea. Generarea de matrici de coduri bloc

Introducere

Descrierea procesului de comunicare digitală

Sursa furnizează un mesaj care reprezintă în general un semnal electric. Acest semnal este convertit în formă digitală, ceea ce este convenabil pentru procesarea ulterioară.

Apoi, informația este comprimată (codare sursă), ceea ce reduce la minimum redundanța mesajului. Codarea sursă reduce costurile de transmitere și stocare a informațiilor. După aceea, mesajul ar trebui transmis pe un canal zgomotos. Pentru ca mesajul să ajungă la consumator într-o formă nedistorsionată, se utilizează codificarea informațiilor imună la zgomot (codarea canalului). Pe partea de consumator, informațiile sunt decodificate. Decodorul de canal corectează erorile din cuvântul primit, iar decodorul sursă convertește cuvântul corectat într-o formă convenabilă pentru consumator.

Când vorbim despre coduri care controlează erorile, ar trebui să se distingă două strategii de utilizare a acestora.

1. Corectarea directă a erorilor din cauza redundanței (Forward Error Correction - FEC).
2. Detectarea erorilor cu cereri ulterioare de retransmitere a informațiilor primite eronat (Automatic Repeat Request - ARQ).

Atunci când alegeți metode de codificare și decodare, acestea sunt ghidate de mulți factori, a căror relație este prezentată în figură.

Complexitatea totală include costurile hardware și software pentru implementarea codificatorului și decodorului, costul stocării și transmiterii informațiilor etc. Debitul de date include transmiterea de informații utile, biți de verificare, precum și solicitări și repetiții pentru acestea. solicitările blocurilor de informații individuale.

Codare anti-interferență

Informatii generale

Sistemele reale de transmisie a datelor nu sunt perfecte. Aplicând tehnologia informației, trebuie să ținem cont de posibilitatea unor erori în transmiterea și stocarea informațiilor. Acest lucru se aplică în primul rând

• stocarea informațiilor pe medii de înaltă densitate (medii magnetice, CD-ROM, DVD);
• transmisie de date cu putere de semnal limitată (comunicații prin satelit și mobil);
• transmiterea de informații prin canale foarte zgomotoase (comunicații mobile, linii de comunicații prin fir de mare viteză);
• canale de comunicații cu cerințe sporite pentru fiabilitatea informațiilor (rețele de calculatoare, linii de transmisie cu compresie de date).

În toate cazurile de mai sus, sunt utilizate coduri de control al erorilor.

Luați în considerare cel mai simplu model de transmisie de date folosind codificarea de corectare a erorilor.

Lăsați codificatorul sursă să scoată secvențial cuvinte de informații cu lungime fixă. Codificatorul de canal înlocuiește fiecare cuvânt de informare u cu un cuvânt de cod v. Emițătorul generează semnale corespunzătoare cuvântului de cod v și le trimite către canal. Receptorul efectuează transformarea inversă, în urma căreia cuvântul binar primit r este trimis către decodor. Decodorul compară cuvântul primit r cu toate cuvintele de cod posibile ale codului utilizat. Dacă cuvântul r coincide cu unul dintre cuvintele cod, atunci cuvântul de informare corespunzător este livrat consumatorului. Dacă r diferă de toate cuvintele de cod, atunci a apărut o eroare detectabilă pe canal. Scopul utilizării codificării canalului este de a potrivi cuvântul informațional transmis u și cuvântul informațional primit u′.

Din această descriere se pot trage 2 concluzii:

• Dacă, în timpul transmisiei pe un canal zgomotos, un cuvânt de cod este mapat într-un alt cuvânt de cod care nu se potrivește cu cel transmis, apare o eroare nedetectabilă. Să o numim eroare reziduală de decodare.
• Este necesar să construiți coduri cu o anumită structură matematică care vă permite să recunoașteți eficient și, în unele cazuri, să corectați erorile care apar atunci când informațiile sunt transmise printr-un canal de comunicare.

Coduri de bloc liniare

Codurile bloc binare liniare formează o familie importantă de coduri. Aceste coduri sunt remarcabile prin faptul că, reprezentând informații și cuvinte de cod sub formă de vectori binari, putem descrie procesele de codificare și decodificare folosind aparatul algebrei liniare. În acest caz, componentele vectorilor și matricelor introduse sunt simbolurile 0 și 1. Operațiile pe componente binare se efectuează conform regulilor aritmetică modulo 2.

Cel mai faimos cod de linie este codul Hamming bloc. Mai mult, descrierea codurilor de bloc liniare se va face folosind acest cod ca exemplu. În special, va fi luat în considerare codul Hamming (7,4).

Codificatorul de cod de bloc binar (n, k) mapează un set de 2 k cuvinte de informații binare posibile într-un set de 2 k cuvinte de cod n-dimensionale. În teoria codificării, există întotdeauna o corespondență unu-la-unu între aceste mulțimi.

În loc de k biți ai vectorului de informații, n biți ai vectorului de cod sunt transmiși către canal. În acest caz, se vorbește de codificare redundantă la o rată: R = n ⁄ k.

Cu cât viteza este mai mică, cu atât este mai mare redundanța codului și cu atât posibilitățile de protecție împotriva erorilor sunt mai mari. Cu toate acestea, trebuie avut în vedere că odată cu creșterea redundanței crește și costul transferului de informații.

Descrierea proceselor de codificare și decodare

Materialul inițial pentru construirea construcțiilor de cod este un spațiu vectorial binar n-dimensional, în care sunt specificate operații aritmetice modulo 2. Un spațiu liniar k-dimensional care conține 2 k cuvinte de cod este încorporat în el. Codul C este format folosind 2 k combinații de k vectori de bază liniar independenți (g 1, ..., g k).

Acești vectori formează rândurile matricei generatoare a codului C.

Pentru un cod C, există un cod dual C d, astfel încât produsul scalar al oricărei perechi de vectori, dintre care unul aparține spațiului C și celălalt spațiului C d, este întotdeauna zero. Aceasta înseamnă că vectorii codului C d sunt ortogonali cu vectorii codului C. Pe de altă parte, dacă un vector este ortogonal cu toți vectorii codului C, atunci aparține codului C d și invers. . Subspațiul vectorial dual este „întins” de n - k vectori de bază liniar independenți (h 1,..., h n - k). Acești vectori formează rândurile matricei de verificare a parității.

Luați în considerare un exemplu de matrice de generare și verificare a parității pentru un cod Hamming (7,4):

O proprietate importantă trebuie remarcată: atât matricea generatoare, cât și matricea de paritate conțin matricea de identitate. Această proprietate este utilizată în procesele de codificare și decodare.

Codificarea

Cuvântul cod v și cuvântul informațional u sunt legate prin raportul:

unde G este matricea generatoare, a cărei structură a fost descrisă mai sus.

De exemplu, vectorul de informații u = (1010) se mapează la vectorul de cod după cum urmează:

Este ușor de observat că ultimii patru biți ai vectorului de cod coincid cu vectorul de informații. Această proprietate se numește consistența codului.

Codurile în care un cuvânt de informare poate fi extras direct din vectorul de cod corespunzător se numesc sistematice. Matricea generatoare a oricărui cod sistematic poate fi întotdeauna redusă la următoarea formă prin rearanjarea coloanelor:

G k × n = (P k × (n - k) I k),

unde I k este matricea de identitate k × k.

Astfel, este întotdeauna posibilă identificarea informațiilor și verificarea simbolurilor în vectorul de cod al codului sistematic.

Rolul caracterelor de verificare și utilizarea lor vor fi explicate în detaliu mai jos.

Decodare

Sarcina decodorului este de a restaura vectorul de informații transmis folosind structura codului, bazată pe cuvântul primit r. Pentru codul Hamming (7, 4) considerat mai sus, se poate propune următorul algoritm de detectare a erorilor. Deoarece codul considerat este sistematic, exprimăm fiecare dintre cele trei simboluri de paritate în termeni de simboluri vectoriale de informații:

V 0 = v 3 ⊕ v 5 ⊕ v 6
v 1 = v 3 ⊕ v 4 ⊕ v 5
v 2 = v 4 ⊕ v 5 ⊕ v 6

Dacă apare o eroare în canal, atunci în vectorul r primit cel puțin una dintre egalități nu va fi îndeplinită. Să scriem relațiile de test obținute sub forma unui sistem de ecuații pentru componentele vectorului r:

R 0 ⊕ r 3 ⊕ r 5 ⊕ r 6 = s 0
r 1 ⊕ r 3 ⊕ r 4 ⊕ r 5 = s 1
r 2 ⊕ r 4 ⊕ r 5 ⊕ r 6 = s 2

Astfel, din primele trei coloane ale matricei generatoare G, am obținut un sistem de trei ecuații de verificare. Dacă în sistemul de ecuații obținut cel puțin una dintre componente (s 0, s 1, s 2) nu este egală cu zero, atunci a apărut o eroare în canal.

Să scriem sistemul de ecuații de testare în formă generală. Pentru orice cod sistematic cu o matrice generatoare G, matricea de verificare a parității este definită după cum urmează:

H (n - k) × n = (I n - k P T k × (n - k)).

Apoi sistemul de ecuații de testare poate fi scris sub forma

Vectorul s este denumit în mod obișnuit sindrom. Astfel, o eroare va fi detectată dacă cel puțin una dintre componentele lui nu este zero.

Ca exemplu, luați în considerare decodificarea sindromică a codului Hamming (7, 4). Când se transmite un cuvânt de informare u = (1010) pe un canal fără zgomot, r = v = (0011010). Ne putem asigura că în acest caz sindromul este egal cu 0.

Dacă, de exemplu, apare o singură eroare în cuvântul de cod în a patra poziție (r = (0010010)), atunci al patrulea rând al matricei de verificare transpusă este sindromul.

După ce parcurgem toate pozițiile posibile ale unei singure erori, obținem un tabel complet al sindroamelor cu o singură eroare - un tabel de corespondențe ale numărului cifrei eronate cu sindromul rezultat.

Se poate observa că o eroare în poziția i-a a cuvântului de cod corespunde sindromului format de coloana i-a a matricei H. Deoarece toate coloanele matricei sunt diferite, putem folosi tabelul de sindrom pentru a corectează o singură eroare introdusă de canal.

Varietăți de erori

Codurile de bloc liniare au 3 tipuri de erori:

1. Eroare recunoscută și corectabilă
   • Sindromul este prezent în tabelul sindroamelor
   • Decodorul recunoaște și corectează eroarea și apoi transmite cuvântul corect către receptor
2. Eroare recunoscută
   • Cuvântul primit nu se potrivește cu niciunul dintre cuvintele de cod
   • Sindromul nu este prezent în tabelul sindroamelor
   • Decodorul recunoaște eroarea și trimite o solicitare de retransmitere a cuvântului de date.
3. Eroare de nerecunoscut
   • Cuvântul primit se potrivește cu unul dintre cuvintele de cod (nu se potrivește cu cuvântul de cod original)
   • Sindromul este 0
   • Decodorul nu recunoaște eroarea și emite un mesaj de informare eronat către consumator

Concluzie

Trebuie remarcat faptul că eficacitatea unui anumit cod depinde de zona de aplicare a acestuia și, în special, de canalul de comunicare. Dacă raportul semnal-zgomot în canal este suficient de mare, atunci probabilitatea unei singure erori este de multe ori mai mare decât probabilitatea unor erori de ordin superior, prin urmare, utilizarea codului Hamming cu corectarea unei singure erori într-un astfel de canal poate fi foarte eficient. Pe de altă parte, în canalele în care predomină erorile multiple (de exemplu, canalele cu estompare), corectarea erorilor individuale este lipsită de sens. În alegerea practică a unui cod specific de corectare a erorilor, este, de asemenea, necesar să se țină cont de viteza decodării acestuia și de complexitatea implementării sale tehnice.

Literatură

1. Werner M. Fundamentele codificării. - M .: Technosphere, 2004.
2. Bleihut R. Teoria și practica codurilor de control al erorilor. - M .: Mir, 1986.

Oleg Rybak

Într-adevăr, este dificil să găsești o explicație adecvată. Cel mai adesea, autorii presupun că cititorul știe multe dinainte și nu caută să explice puncte aparent simple care conțin esența. Sunt foarte bucuros că am dat peste acest material și am clarificat ceva pentru mine.

Codurile liniare au următoarea proprietate:

Dintre toată mulţimea 2 k dintre cuvintele de cod permise care formează un grup liniar, se pot distinge subseturile k cuvinte care au proprietatea de independență liniară.

Independența liniară înseamnă că niciunul dintre cuvintele incluse în subsetul de cuvinte de cod independente liniar nu poate fi obținut prin însumarea (folosind o expresie liniară) oricăror alte cuvinte incluse în acest subset.

În același timp, oricare dintre cuvintele de cod permise poate fi obținut prin însumarea anumitor cuvinte liniar independente.

Astfel, construcția combinațiilor de cod ale unui cod liniar este asociată cu operații liniare. Pentru a efectua astfel de operațiuni, este convenabil să utilizați un aparat de calcul matriceal bine dezvoltat.

Pentru educatie n Cuvintele de cod de biți din cuvintele codificate de k biți (codificare) folosesc o matrice, care se numește generare (generare).

Matricea generatoare se obține prin scrierea k cuvinte liniar independente într-o coloană.

Să notăm secvența de informații codificate Xși o vom scrie sub forma unei matrice de rând || X || dimensiune 1* k, De exemplu:

|| X || = || 11001 ||, Unde k = 5.

Una dintre modalitățile de a construi o matrice generatoare (generatoare) este următoarea: Este construită din matricea de identitate || I || dimensiune k * kși matricea de cifre suplimentare (redundante) alocate acestuia din dreapta || MDR || dimensiuni k * r.

unde la k=4

Această structură a OM oferă un cod sistematic.

Procedura de construire a matricei MDS va fi discutată mai jos.

7.4 Ordinea de codificare

Cuvântul de cod KS se obține prin înmulțirea matricei secvenței informaționale || X || pe matricea generatoare || ОМ ||:

Înmulțirea se realizează după regulile înmulțirii matriceale: (SO pe SO)

Trebuie doar să rețineți că adăugarea aici este modulo 2.

de exemplu, matricea generatoare

|| ОМ || = 0010 011

și vectorul rând al secvenței de informații

Deoarece matricea de înmulțit are un singur rând, înmulțirea este simplificată. În acest caz, ar trebui să atribuiți rândurile matricei generatoare (generatoare). || OM || biți ai matricei secvenței informaționale || X ||și adăugați acele rânduri ale matricei generatoare (generatoare) care corespund cifrelor unității ale matricei || X ||.

observa asta || KC || = || X, ДР ||,

Unde || X || - secvență de informații (deoarece înmulțită cu matricea de identitate || I ||),

A || DR ||- cifre suplimentare, în funcție de matricea de cifre suplimentare || MDR ||:

|| DR || = || X || * || MDR ||

7.5 Ordinea de decodare

Ca rezultat al transmiterii cuvântului de cod prin canal, acesta poate fi distorsionat de interferență. Acest lucru va cauza cuvântul de cod acceptat || PKS || este posibil să nu se potrivească cu originalul || COP ||.

Distorsiunea poate fi descrisă folosind următoarea formulă:

|| PKS || = || KS || + || ÎN ||,

Unde || ÎN ||- vector de eroare - matrice-rând cu dimensiune 1* n, Cu 1 în acele poziții în care s-a produs distorsiunea.

Decodificarea se bazează pe găsirea așa-numitului sindrom de identificare sau matrice de eroare-rând || OP || lungimea r cifre ( r- numărul de biți suplimentari sau redundanți din cuvântul de cod).

Identificatorul este utilizat pentru a găsi vectorul de eroare estimat.

Identificatorul se găsește prin următoarea formulă:

|| OP || = || PCS || * || TPM ||,

Unde || buc || - cuvânt de cod primit și posibil corupt;

|| TPM ||, - matricea de paritate transpusă care se obține din matricea de umplutură || MDR || atribuindu-i matricea de unitati de mai jos:

Exemplu || TPM ||:

În măsura în care || PKS || = || KS || + || BO ||, ultima formula poate fi scrisa ca:

|| OP || = || KS || * || TPM || + || VO || * || TPM ||.

Luați în considerare primul termen.

|| KC || este o matrice de rând, iar prima k cifre – informative.

Să demonstrăm acum că produsul cuvântului de cod || COP || pe || TPM || rezultă o matrice zero ||0||.

În măsura în care || COP ||- matrice-rând, este posibilă o ordine simplificată de înmulțire a matricelor considerate mai sus.

Prin urmare, primul termen în

|| OP || = || KS || * || TPM || + || ÎN || * || TPM ||

întotdeauna egal cu zero și identificatorul este complet dependent de vectorul de eroare || ÎN ||.

Dacă alegem acum o astfel de matrice de verificare a parității TPMși, prin urmare MDR astfel încât diferiți vectori de eroare să corespundă unor identificatori diferiți OP, apoi din acești identificatori se va putea găsi vectorul de eroare ÎN,și, prin urmare, corectați aceste erori.

Corespondența identificatorilor cu vectorii de eroare se găsește în prealabil prin înmulțirea vectorilor erorilor corectabile cu TPM;

Astfel, capacitatea unui cod de a corecta erori este în întregime determinată de || MDR ||. Pentru constructie MDR pentru codurile care corectează erori individuale, aveți nevoie în fiecare linie MDR au cel putin 2 unitati. În acest caz, este, de asemenea, necesar să existe cel puțin o diferență între oricare două linii MDR.

Codul pe care l-am primit este incomod prin faptul că identificatorul, deși este asociat fără ambiguitate cu numărul bitului distorsionat, deoarece un număr nu este egal cu acesta. Pentru a căuta un bit distorsionat, trebuie să utilizați un tabel de corespondență suplimentar între identificator și acest număr. Au fost găsite codurile în care identificatorul ca număr determină poziția cifrei distorsionate și au primit numele Codurile de hamming.

Clădire MDR căci cazul corectării mai multor erori devine mult mai complicat. Diferiți autori au găsit diferiți algoritmi de construcție || MDR || pentru acest caz, iar codurile corespunzătoare sunt denumite după numele autorilor lor.

Doar ca exemplu, am luat în considerare cele mai simple coduri de corecție - un cod simplu de verificare a parității care detectează o singură eroare într-o secvență primită și un cod iterativ bloc și un cod cloud care corectează o singură eroare folosind un set de verificări de paritate. În toate codurile, în procesul de codificare de corectare a erorilor, s-au format biți suplimentari, adăugați la combinația de cod inițială.

Să stabilim regulile formale (de generare) conform cărora se realizează codificarea, adică. conversia secvenței de informații într-un cuvânt cod.

Cel mai simplu mod de a descrie sau de a atribui coduri de corecție este mod tabelar,în care fiecărei secvențe de informații i se atribuie pur și simplu un cuvânt de cod din tabelul de coduri. De exemplu, pentru cel mai simplu cod cu verificarea parității, tabelul de corespondență dintre combinațiile sursă și cod va fi următorul:

Acest mod de a descrie codurile este aplicabil pentru orice cod, nu doar pentru coduri liniare. Cu toate acestea, pentru mari La dimensiunea tabelului de coduri se dovedește a fi prea mare pentru a fi utilizată în practică.

O altă modalitate de a defini codurile de bloc liniare este utilizarea așa-numitelor sisteme de generare a ecuațiilor, definirea regulii conform căreia simbolurile secvenței informaționale sunt convertite în simboluri de cod. Pentru același exemplu, sistemul de generare a ecuațiilor va arăta astfel:

Cu toate acestea, cel mai convenabil și intuitiv mod de a descrie codurile bloc liniare este să le definiți folosind matrice generatoare, care este o formă compactă de reprezentare a sistemului de ecuații de testare.

Bloc liniar(l, / s) -codul este determinat complet de matricea G cu dimensiune La X P cu elemente matrice binare. Mai mult, fiecare cuvânt de cod este o combinație liniară a rândurilor matricei G și fiecare combinație liniară a rândurilor lui G este un cuvânt de cod.

Vor fi apelate coduri de bloc liniare definite prin generarea de matrici codurile matriceale. Reprezentarea obișnuită (canonică) a matricei generatoare arată astfel:

De exemplu, pentru cel mai simplu (4, 3) cod de verificare a parității, matricea generatoare va arăta astfel:

Lăsa T -(t 1; t 2, ..., t la) va fi blocul de mesaje care trebuie codificat folosind acest cod.

Apoi cuvântul de cod corespunzător U voi

Ținând cont de structura matricei G caractere de cuvinte de cod și va fi asa:

Cu alte cuvinte, La simbolurile cele mai din stânga ale cuvântului cod coincid cu simbolurile secvenței de informații codificate, iar restul (n - La) caracterele sunt combinații liniare de caractere secvențe de informații.

De exemplu, dacă secvența de intrare a codificatorului t == (10 1), apoi folosind matricea generatoare codul va fi construit după cum urmează:

8 Căpetenia a trimis trei cercetători pe primul drum, trei pe al doilea, doi pe al treilea și a mers el însuși pe al patrulea. Creați o matrice generatoare pentru un astfel de cod.

Răspuns: Potrivit complotului sarcinii, mesajul primit de comandant personal nu poate fi distorsionat. Prin urmare, ne vom restrânge la studiul informațiilor transmise de luptători. Într-un grup care pornește de-a lungul unuia dintre drumuri, fiecare soldat trebuie să raporteze comandantului fie despre detectarea unui obiect (vom desemna un astfel de raport drept „1”), fie despre absența unui obiect („0” ). În absența distorsiunii, rapoartele fiecărui luptător din aceeași grupă trebuie să fie aceleași. Prin urmare:

Matricea poate fi adusă la forma canonică prin renumerotarea luptătorilor, adică. pe primul drum, trimițând primul, al patrulea și al cincilea, pe al doilea drum - al doilea, al șaselea și al șaptelea, pe al treilea drum - al treilea și al optulea luptători. Obținem următoarea matrice generatoare:

Codul definit în acest fel este numit bloc liniar sistematic(P,/ cod cj cu verificări de paritate generalizate.

Matricea generativă codul liniar se numește o matrice de dimensiune, ale cărei rânduri sunt vectorii de bază.

De exemplu,

este matricea generatoare a codului de două cuvinte (000, 011).

este generatorul pentru codul B din exemplul 6.3.

Știm că cuvintele de cod sunt combinații liniare de vectori de bază, adică. rânduri ale matricei. Aceasta înseamnă că cuvintele pot fi obținute prin înmulțirea unui vector cu o matrice. Deci, mesajul este scris ca un vector iar cuvântul cod corespunzător mesajului se calculează prin formulă

Astfel, vectorul de biți este convertit într-o secvență de simboluri binare transmise pe canal sau scrise în memoria dispozitivului de stocare.

Să trecem la problema decodării.

Să presupunem că pentru un vector binar toate cuvintele de cod ale codului , satisface identitatea

în care denotă produsul scalar al vectorilor și.

Spunem despre un astfel de vector că este ortogonal. După ce am găsit un astfel de vector, am putut verifica, folosind identitatea (6.2), dacă secvența primită de la canal este un cuvânt de cod.

Rețineți că (6.2) este valabilă pentru toate cuvintele de cod dacă este valabilă pentru vectorii de bază, de exemplu. dacă

unde superscriptul T indică transpunerea.

Cu cât găsim mai multe astfel de „verificări”, cu atât mai multe erori vom putea detecta și corecta.

Exercițiul 6.4... Demonstrați că verificările formează un spațiu liniar.

Acest spațiu va fi numit spațiu ortogonal unui cod liniar sau spatiu de verificare.

Exercițiul 6.5... Aflați dimensiunea spațiului liniar al cecurilor.

Pentru a finaliza ultimul exercițiu, trebuie să observați că matricea are coloane exact liniar independente. Nici mai mult (de ce?) Și nici mai puțin (de ce?). Să reparăm lista de numere a acestor coloane și să numim acest set de numere set de informații... Puțin mai târziu, semnificația acestui nume va deveni mai clară. Să alegem în mod arbitrar valorile vectorului în poziții care nu sunt incluse în setul de informații. Care ar trebui să fie valorile la pozițiile setului de informații pentru (6.3) să fie îndeplinite? Pentru a răspunde la această întrebare, este necesar să se rezolve un sistem de ecuații liniare, iar sistemul are o soluție unică.

O consecință a acestui raționament este teorema

Teorema. Dimensiunea spațiului de verificare a unui cod liniar este egală cu.

Scriem baza spațiului de testare sub forma unei matrice

numit matricea de verificare cod.

Matricele de verificare și generatoare sunt legate prin relație

Din această relație vedem că pentru orice cuvânt de cod există

Această identitate poate fi folosită ca criteriu pentru ca o secvență arbitrară să aparțină unui cod, adică. pentru a detecta erorile.

Știind, se poate găsi. Pentru a înțelege cum se face acest lucru, rețineți că același cod poate fi specificat prin diferite matrice generatoare, alegând baza spațiului în moduri diferite. Mai mult, înlocuind în orice șir cu orice combinație liniară a acestui șir cu alte șiruri, obținem o nouă matrice generatoare a aceluiași cod.

Permutarea coloanelor matriceale, în general, duce la un cod diferit, dar acest alt cod nu diferă în caracteristicile sale de cel original. Se apelează coduri care diferă doar prin numerotarea pozițiilor echivalent.

Este clar că pentru fiecare cod există unul echivalent pentru care primele poziții formează un set de informații, adică. primele coloane formează o matrice de dimensiuni nedegenerate. Înlocuind rândurile cu combinații liniare de rânduri (metoda Gauss), matricea rezultată poate fi redusă la forma

unde este matricea de ordine unitară și este o matrice de dimensiune.

O matrice de forma (6.6) se numește matrice generatoare redusă la mod sistematicși se numește codul corespunzător sistematic... Codarea pentru codul sistematic este puțin mai ușoară decât pentru codul general:

, (6.7)

acestea. în cuvântul de cod, primele poziții sunt doar o copie a secvenței de informații, iar pozițiile rămase (de verificare) sunt obținute prin înmulțirea vectorului de informații cu o matrice de dimensiune, care este uneori semnificativ mai mică decât. În consecință, informațiile despre codul sistematic ocupă mult mai puțină memorie decât informațiile despre codul liniar general.

Pentru un cod sistematic cu o matrice generatoare în forma (6.6), matricea de verificare a parității poate fi calculată prin formula

Exercițiul 6.6... Verificați (6.7). Sugestie: pentru aceasta trebuie să înlocuiți (6.8) și (6.6) în (6.4).

Cum găsesc o matrice de verificare pentru un cod nesistematic?

Foarte simplu. Este necesară aducerea matricei într-o formă sistematică și utilizarea (6.7). Dacă primele coloane ale matricei generatoare formează o submatrice nedegenerată (primele poziții formează un set de informații), atunci operațiuni precum permutarea rândurilor și înlocuirea rândurilor cu combinații liniare de rânduri sunt suficiente pentru a o aduce la o formă sistematică. Dacă nu, mai întâi va trebui să găsiți setul de informații și să renumerotați pozițiile astfel încât primele poziții să devină informaționale.

Deoarece, conform definiției, codul liniar (l, / c) de lungime P de mai sus GF (q) este un subspațiu GF k (q) spațiu vectorial GF n (q), atunci trebuie să existe un complement ortogonal al subspațiului GF k (q) cod de linie (a se vedea paragraful 1.7.1).

Fie H o matrice ale cărei rânduri corespund vectorilor de bază ai complementului ortogonal al unui cod liniar g-ary C de lungime NS. Atunci, pentru orice vector c aparținând codului, este adevărat:

Condiția (2.10) face posibilă verificarea apartenenței unei n-secvențe arbitrare de elemente GF (q) un anumit cod liniar g-ary.

Dacă un vector al unui cod liniar are o greutate Hamming sho, atunci aceasta înseamnă că există simboluri sho diferite de zero în cuvântul de cod (conform definiției unei greutăți Hamming, vezi Subsecțiunea 2.1.4). Apoi, conform regulilor de înmulțire a matricei, produsul unui vector cu valoarea w0 a greutății Hamming cu matricea H t corespunde unei combinații liniare de coloane sho ale matricei N. Mai mult, egalitatea (2.10) este valabilă dacă și numai dacă nu există coloane ale matricei N sunt dependente liniar.

Astfel, condiția existenței în setul de cuvinte de cod a unui cod liniar al unui cuvânt de cod cu greutatea Hamming sho este prezența în matrice. N coloane dependente liniar în numărul de sho. Rezultă, de asemenea, că un cod liniar are o pondere minimă (vezi Subsecțiunea 2.1.4) cel puțin o valoare w0 dacă și numai dacă orice coloane w0 - 1 ale matricei H sunt liniar independente. Prin urmare, conform inegalității (2.6), pentru a găsi un cod liniar cu ponderea minimă w0, corectând t erori, este suficient să găsiți matricea H, cu cel puțin sho - 1 = 2 -t orice coloane erau liniar independente.

Să aruncăm o privire mai atentă asupra matricei N. După cum sa menționat mai sus, rândurile matricei N sunt vectorii de bază ai complementului ortogonal al codului liniar. Dacă mulţimea de n-secvenţe formează un subspaţiu de dimensiune La, atunci complementul ortogonal al acestui subspațiu va avea dimensiunea PC(a se vedea punctele 1.7.1 și 1.7.2). Dimensiunea subspațială P- La pentru multi PC vectori de bază. Prin urmare matricea N ar trebui să conțină PC linii liniar independente.

Deoarece matricele G și N aparțin aceluiași spațiu de n-secvențe, apoi numărul de coloane ale matricei N este egal cu numărul de coloane ale matricei G. Astfel, matricea N are dimensiunea (l - La) x l. Toate coloanele matricei H, după cum sa menționat deja, ei formează grupuri liniar independente în raport cu 2t coloane.

Conform relației (2.2), orice cuvânt de cod al unui cod liniar este o combinație liniară de rânduri a matricei generatoare G a codului. În acest caz, evident, fiecare rând al matricei G corespunde unui cuvânt de cod. Prin urmare, relația (2.10) poate fi rescrisă după cum urmează:

Produsul matricelor G de mărime La* dacă H t marimea l x (PC) este matricea dimensiunilor La x (l - La), format din zero elemente.

Matrice N mărimea ( n-k) x l, ale căror linii sunt vectorii de bază ai complementului ortogonal al subspațiului codului liniar, se numește matricea de verificare cod liniar.

Conform relației (2.4), matricea generatoare a codului liniar sistematic constă din matricea de identitate de ordin Lași matrice de simboluri de verificare a mărimii La x (l - La), care, la rândul său, este o extensie a matricei identitare. După cum se arată în Anexa 1, înmulțirea a două matrici poate fi efectuată prin împărțirea matricelor înmulțite în matrici (blocuri) mai mici și apoi înmulțirea blocurilor individuale ale matricelor multiplicate. Atunci pentru matricele G și N poti sa scrii:

Numărul de coloane în blocuri A și B matrici N 7 trebuie să se potrivească cu numărul de linii din blocuri Ekși R matricele G (după regulile înmulţirii matriceale). Matricea rezultată trebuie să aibă dimensiunea / s * (l - La). Evident, dacă punem A = -Rși V= El_ / s, apoi matricea N va satisface ecuația (2.11).

Deci matricea H t este o extensie a matricei -Rși pe lângă matrice - R matrice N conţine matricea identităţii de ordine P - La. Matrice H t este rezultatul transpunerii matricei N.

Rezultatul transpunerii repetate a matricei este matricea originală. Prin urmare matricea N se poate obţine prin transpunerea matricei N t. Deoarece pentru orice element a, câmpurile GF [ 2) a = - a este adevărat, atunci pentru un cod liniar binar este adevărat R - R.

Matrice N codul de linie binar va arăta astfel:

Matrice R, incluse în matricea G și care conțin simboluri de verificare, pot fi obținute prin transpunerea matricei P t, incluse în matrice N.

Astfel, construcția unui cod liniar se reduce la găsirea matricei N. Pentru o matrice dată N este ușor de găsit matricea G.

Exemplul 2.1.4. Luați în considerare construcția unui cod liniar binar - un cod peste GF (2) care corectează o eroare a unui cuvânt de cod cu o secvență de informații de dimensiune La= 3 biți.

Conform relației (2.9), pentru codul cu distanța maximă r = 2-t == 2. Atunci n = fc + r = 3 + 2 = 5. Totuși, așa cum va fi arătat în următorul subparagraf, un cod binar liniar (5,3) nu este capabil să corecteze o singură eroare de cuvânt de cod. În acest caz, numărul minim de simboluri redundante pentru acest caz este G= 3, iar codul luat în considerare este un cod binar liniar (6,3).

Astfel, în acest caz, matricea N conține o matrice de verificare de dimensiune / cx (n- / c) = 3 * 3 și o matrice de identitate de ordin n-k = 3.

Toate coloanele matricei N trebuie să formeze grupuri liniar independente de două coloane și grupuri liniar dependente de trei coloane. Această condiție este îndeplinită, de exemplu, de secvențele 101, 110 și 011 peste GF (2). Secvențele specificate formează coloanele matricei P t, incluse în matrice N. Restul elementelor matricei N corespund matricei identitare de ordinul 3:

Prin adăugarea la matricea de identitate de ordinul 3 a matricei P obţinută prin transpunerea matricei P t, obținem matricea G:

Să considerăm acum procesul de formare și structura unui cuvânt de cod al unui cod binar liniar (6, 3) cu o matrice generatoare de forma (2.12):

Primele trei caractere ale cuvântului cod (ci - Cs) conțin simboluri informaționale (/ 1 - g "s), formate ca urmare a înmulțirii matricei secvenței informaționale i pe matricea de identitate de ordinul 3, care face parte din matricea G. Simbolurile rămase ale cuvântului de cod (C4 - Cb) conțin simboluri de verificare (t ^ - tz), obţinută ca urmare a înmulţirii matricei secvenţei informaţionale cu matricea simbolurilor de verificare R, incluse de asemenea în matricea G.

Este ușor de verificat că în cazul codului (6, 3) din Exemplul 2.1.4, numărul minim de simboluri diferite de zero dintre toate cuvintele de cod este de trei (cuvinte de cod 001101, 010011, 100110 și 111000). În acest fel, d *= 3 și, conform relației (2.5), codul trebuie să corecteze o eroare de cuvânt de cod. După cum se va arăta în paragraful următor, acesta este într-adevăr cazul.