Generarea de matrici de coduri bloc. Construirea matricei de verificare

Să denotăm biții de informații codificați într-un cuvânt de cod. În acest capitol, urmăm convențiile stabilite pentru reprezentarea cuvintelor de cod ca vectori. Astfel, un vector de biți de informații la intrarea codificatorului este notat după cum urmează:

,

iar ieșirea codificatorului este un vector de caractere

.

Operația de codificare efectuată într-un cod de bloc binar liniar poate fi reprezentată printr-un set de ecuații de forma

(8.1.2)

unde sau , și reprezintă produsul lui și . Ecuații liniare (8.1.2)

poate fi reprezentat și sub formă de matrice

unde este matricea generatoare a codului, egala cu

(8.1.4)

Rețineți că un cuvânt de cod arbitrar este pur și simplu o combinație liniară de vectori din ,

Deoarece un cod liniar cu cuvinte de cod este un subspațiu de dimensiune, vectorii matricei generatoare trebuie să fie liniar independenți, adică. ele trebuie să formeze un spaţiu de dimensiune. Cu alte cuvinte, ele ar trebui să formeze baza codului. Rețineți că ansamblul vectorilor de bază nu este unic și, prin urmare, nu este unic. Vom observa, de asemenea, că, deoarece spațiul are dimensiune, rangul matricei este.

Orice matrice generatoare de cod poate fi redusă la o „formă sistematică” prin efectuarea de operații pe rânduri (și rearanjarea coloanelor):

, (8.1.6)

Unde - matrice de identitate, a este o matrice care definește caractere redundante sau de verificare. Rețineți că matricea generatoare a unui cod sistematic produce un cod bloc liniar în care primii biți ai oricărui cuvânt de cod sunt identici cu biții de informație, iar biții rămași ai oricărui cuvânt de cod sunt combinații liniare biți de informații. Acești biți redundanți sunt numiți biți de paritate. Codul rezultat este numit în acest caz cod sistematic.

Dacă un cod este generat de o matrice care nu are o formă sistematică (8.1.6), se numește nesistematic. Cu toate acestea, o astfel de matrice este echivalentă cu o matrice în formă sistematică, în sensul că una poate fi obținută de la cealaltă prin operații elementare pe rânduri și deplasarea coloanelor. Două coduri liniare generate de două matrice generatoare echivalente sunt numite echivalente și unul poate fi obținut din celălalt prin rearanjarea elementelor. Astfel, fiecare cod liniar este echivalent cu un cod sistematic liniar.

Exemplul 8.1.1. Luați în considerare codul (7, 4) cu matricea generatoare

. (8.1.7)

Un cuvânt cod tipic poate fi exprimat după cum urmează:

unde reprezintă patru biți de informație, a reprezintă trei biți de paritate, definiți după cum urmează:

Un codificator de bloc binar sistematic liniar poate fi implementat utilizând un registru de deplasare de -bit, sumatori asociați cu celulele registrului de deplasare corespunzătoare și generând simboluri de paritate, care sunt apoi localizate temporar într-un registru de deplasare de a doua lungime. Apoi biții de informație, urmați de biții de verificare, părăsesc secvențial cele două registre și sunt alimentați la modulator. Această codificare este ilustrată în Fig. 8.1.1 pentru codul (7, 4) din exemplul (8.1.1).

Orez. 8.1.1. Registrul cu deplasare liniară pentru cod binar (7,4)

Orice cod liniar este asociat cu un cod dublu de dimensiune.

Un cod dual este un cod liniar cu vectori de cod care formează un spațiu nul în raport cu codul. Matricea generatoare pentru codul dual, notată , constă din vectori de cod independenți liniar aleși în spațiu nul. Orice cuvânt de cod din cod este ortogonal cu orice cuvânt de cod al codului dual. În consecință, orice cuvânt de cod al codului este ortogonal cu orice rând al matricei, adică.

unde înseamnă un vector coloană format din zerouri și este cuvântul de cod al codului. Deoarece (8.1.9) este valabilă pentru orice cuvânt cod al codului, urmează

unde este acum o matrice cu toate elementele zero.

Acum să presupunem că codul liniar este sistematic și matricea sa generatoare este dată în formă sistematică (8.1.6). Apoi, din moment ce , rezultă că

(8.1.11)

Semnul negativ din (8.1.11) poate fi omis atunci când lucrați cu coduri binare, deoarece scăderea prin este identică cu adunarea cu .

Exemplu (8.1.2). Pentru codul sistematic (7, 4), generat de matricea definită de (8.1.7), avem, conform (8.1.11), o matrice sub forma

(8.1.12)

Acum, ecuația se descompune în trei ecuații

(8.1.13)

Astfel, vedem că produsul este echivalent cu însumarea simbolurilor de test cu combinațiile liniare corespunzătoare de simboluri de informații utilizate pentru calcul. Aceasta înseamnă că (8.1.13) este echivalent cu (8.1.8).

Matricea poate fi utilizată într-un decodor pentru a verifica dacă cuvântul de cod primit îndeplinește condiția (8.1.13), adică . Astfel, decodorul verifică simbolurile de paritate recepționate cu combinația liniară corespunzătoare de simboluri și , care formează simbolurile de paritate la transmisie. Prin urmare, este obișnuit să o numim o matrice de verificare asociată cu codul.

Să ne exprimăm o idee cu privire la legătura dintre distanța minimă de cod și matricea ei de verificare. Produsul cu reprezintă o combinație liniară de coloane. Deoarece , vectorii coloană sunt dependenți liniar. Să spunem ce înseamnă cuvântul de cod cu greutatea minimă a unui cod liniar. Trebuie să îndeplinească condiția. Deoarece greutatea minimă este egală cu distanța minimă, rezultă că coloanele sunt dependente liniar. Alternativ, putem spune că cel mult coloanele sunt liniar independente. Deoarece rangul matricei nu este mai mare decât , avem . Prin urmare, are o limită superioară. Numim codul simbolurilor informaționale (în toate combinațiile de coduri) zero. Aceste. Codul scurtat este format din cuvinte cod. Distanța minimă a acestor cuvinte de cod de-a lungul macar nu mai puțin decât distanța minimă a codului sursă.

Să considerăm un cod liniar sistematic specificat de matricea generatoare și să construim o matrice de forma

unde superscriptul semnifică transpunerea matricei. Rolul unei astfel de matrice devine cel mai evident dacă luăm în considerare că pentru orice vector de cod

Din (6.6) rezultă că înmulțirea oricărui vector de cod cu o matrice transpusă dă zero, prin urmare, se numește matricea (6.5). matricea de verificare. În plus, se spune că codul liniar este spațiul nul al matricei de verificare sau că codul este ortogonal cu matricea de verificare.

Pe baza relațiilor (6.4) și (6.6) avem

de unde se obţine uşor că simbolurile de verificare ale cuvântului cod sunt definite ca

Astfel, un cod liniar poate fi specificat atât prin matricele generatoare (6.3) şi verificare (6.5), cât şi prin relaţiile (6.7) care stabilesc legătura dintre simbolurile de verificare şi informare ale cuvintelor cod.

Teorema 6.4.1. Un cod liniar are o distanță minimă egală cu , dacă și numai dacă matricea de verificare conține un set de coloane dependente liniar și orice set de coloane matrice este liniar independent.

Dovada: Să luăm în considerare un cod liniar specificat de o matrice de verificare a dimensiunii în formă

unde este vectorul coloană component al matricei de verificare. Apoi, pe baza teoremei 6.3.1, există cel puțin un vector de cod având componente diferite de zero pentru care

unde sunt pozițiile componentelor nenule ale vectorului . Astfel, printre coloanele matricei vor exista întotdeauna acelea care, cu scalari nenuli, dau o sumă nulă și, prin urmare, sunt dependente liniar.

Pe de altă parte, să presupunem că din matricea de verificare este posibil să se selecteze un set de coloane dependente liniar pentru care este valabilă următoarea relație:

unde sunt numerele coloanelor matricei de verificare incluse în setul menționat. Să construim un vector în care , și pozițiile rămase sunt umplute cu zerouri. Este evident că

prin urmare, adică este un vector de cod. Aceasta din urmă înseamnă că distanța codului nu este mai mare de , deoarece , ceea ce contrazice condițiile teoremei. Astfel, orice set de coloane de matrice este liniar independent.

Având în vedere structura matricelor, se poate face următoarea concluzie. Ambele matrice constau din mulți vectori liniar independenți, deoarece prezența unei matrice de identitate în structura lor face imposibilă existența unei combinații liniare de rânduri cu sumă zero. În consecință, fiecare dintre matrice poate fi considerată ca bază a unui spațiu liniar. Mai mult, fiecare dintre aceste spații este un subspațiu al unui spațiu vectorial format din toți vectorii de lungime . Având în vedere cele de mai sus, le puteți „schimba rolurile” și le puteți folosi ca o matrice generatoare și o matrice de verificare a unui alt cod. Codurile asociate acestei conversii sunt numite dual reciproc. Astfel, dacă sursa a fost un cod, atunci codul va fi dual.

În plus, dintr-un anumit cod puteți obține unul nou cu aceiași parametri dacă schimbați caracterele în aceleași poziții în fiecare cuvânt de cod. Codul obținut prin acest algoritm este numit echivalent. Matricele generatoare și codurile echivalente sunt legate între ele transformare elementară. Astfel, schimbul de simboluri la aceleași poziții ale cuvintelor de cod (sau, ceea ce este același, o rearanjare a coordonatelor de cod) echivalează cu o rearanjare a coloanelor matricei. În consecință, două coduri sunt echivalente dacă și numai dacă matricele lor generatoare sunt obținute una de la alta prin rearanjarea coloanelor, sau ca urmare a unor operații elementare pe rânduri.

Se numește orice cod cu o relație care satisface distanța de cod (6.8). cod cu distanta maxima.

Cometariu. Limita Singleton (6.8) este inutilă pentru codurile binare, deoarece este semnificativ inferioară ca precizie față de limitele Plotkin și Hamming. Cu toate acestea, joacă un rol semnificativ în cazul codurilor -ary.

1.2.2. Matrice de verificare a codului liniar

Din moment ce codul liniar V este un subspațiu, atunci pentru el există complement ortogonal(sau subspațiu nul). Complement ortogonal V" (n, k) - cod V este format din toți vectorii de lungime n, ortogonal la fiecare vector vÎ V. Se numesc vectori ortogonală, dacă produsul lor scalar este 0. Pentru vectorii binari, produsul scalar este egal cu suma produselor componentelor corespunzătoare. De exemplu, produs scalar(00101, 10110) a vectorilor 00101 și 10110 este vectorul 00100 = 0×1 + + 0×0 + 1×1 + 0×1 + 1×0. Complementul ortogonal este, de asemenea, un subspațiu și astfel poate fi considerat un cod liniar. O multime de V" - numit cod dual sau dual La V.

Complement ortogonal V" (n, k) - cod V are dimensiune ( n-k); în consecință, oricare dintre bazele sale constă în ( n-k) vectori. Matricea generatoarelor N complement ortogonal se numește matricea de verificare cod V.

Deoarece matricea de verificare constă din vectori de bază ai complementului ortogonal, atunci vectorul binar Cu este un cuvânt de cod dacă și numai dacă cNT = 0. Astfel, verificarea erorilor la transmiterea unui cuvânt de cod se reduce la înmulțirea a două matrice în loc de a enumera toate cuvintele de cod. Înmulțirea matricelor, a căror dimensiune este de câteva mii, cu modern tehnologia calculatoarelor ruleaza foarte repede.

Matricea de verificare poate fi construită prin găsirea sistemului fundamental de soluții pentru sistemul de ecuații corespunzător. Matrice

din secțiunea anterioară generează următorul sistem ecuatii:

Matricea principală a sistemului coincide cu matricea G. Necunoscut X 1 , X 2 și X 3 pentru care există un minor care nu este egal cu 0 pot fi declarate necunoscute principale. Apoi necunoscutul X 4 și X 5 sunt gratuite. Alegem valori liniar independente 01 și 10 pentru ele și obținem sisteme de ecuații:

Și

Din primul sistem obținem X 1 = 1, X 2 = 0, X 3 = 1, adică soluția sistem original este vectorul 10101. Din al doilea sistem obținem X 1 = 1, X 2 = 1, X 3 = 0, adică a doua soluție din sistemul fundamental de soluții este vectorul 11010. Astfel, obținem matricea de verificare:

.

Rețineți că, ca și matricea generatorului, există diferite matrice de verificare pentru același cod.

Relația dintre distanța de cod a unui cod liniar și matricea de verificare a parității este stabilită prin următoarea teoremă:

Teorema 1.3. Fiecare cuvânt de cod diferit de zero are o pondere de cel puțin w, dacă și numai dacăorice colecție de w coloane matrici N

Dovada. Pentru orice cuvânt cod Cu egalitatea este valabilă cNT = 0. Lăsați cuvântul cod Cu are greutate u. Să excludem componentele zero ale vectorului din considerare. Egalitatea rezultată va fi relația dependență liniară u coloane din N. Prin urmare, N conţine multe dintre u coloane dependente liniar. Deci există un cuvânt de greutate în cod u, dacă și numai dacă în matrice N există o colecție de u coloane dependente liniar. Astfel, toate cuvintele de cod diferite de zero au o pondere de cel puțin w w-1 coloane matrice N este liniar independent.

Ca o consecință a teoremelor 1.1 și 1.3, următoarea afirmație este valabilă:

Consecinţă. Distanța codului liniar nu mai puțin de w, dacă și numai dacă orice colecție de w-1 coloane matrici N este liniar independent .

Conform afirmaţiilor formulate mai sus, pentru a constata (P,k) - cod care corectează t erori, este suficient să construiți o matrice N dimensiuni ( p - k) × n, în care orice 2 t coloanele sunt liniar independente.

Matricea generatoarelor 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).

se generează pentru codul B din Exemplul 6.3.

Știm că cuvintele de cod sunt combinații liniare de vectori de bază, adică. rânduri de matrice. 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 de mesaj corespunzător este calculat prin formulă

Astfel, un vector de biți se transformă într-o secvență de simboluri binare transmise pe un canal sau scrise în memoria unui dispozitiv de stocare.

Să trecem la problema decodării.

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

in care denota produsul scalar al vectorilor si .

Despre un astfel de vector vom spune că este ortogonal. După ce am găsit un astfel de vector, am putea 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, aparent, vom putea detecta și corecta.

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

Numim acest spațiu spațiu ortogonal cod liniar sau spațiu de testare.

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 exact liniară coloane independente. Nici mai mult (de ce?) și nici mai puțin (de ce?). Să reparăm o listă de numere din aceste coloane și să numim acest set de numere set de informații. Puțin mai târziu, sensul acestui nume va deveni mai clar. Să alegem în mod arbitrar valori vectoriale la poziții care nu sunt incluse în set de informații. Care ar trebui să fie valorile la pozițiile setului de informații pentru ca (6.3) să fie îndeplinită? Pentru a răspunde la această întrebare, va trebui să rezolvăm sistemul ecuatii lineare, iar sistemul are singura decizie.

Consecința acestor argumente este teorema

Teorema. Dimensiunea spațiului de verificare al 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 generare sunt legate prin relație

Din această relație vedem că pentru orice cuvânt cod pe care îl avem

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

Știind, poți 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 mod diferit. În plus, înlocuind orice linie cu orice combinație liniară a acestei linii cu alte linii, obținem o nouă matrice generatoare a aceluiași cod.

Rearanjarea coloanelor unei matrice, în general, duce la un cod diferit, dar acest cod diferit nu este diferit în caracteristicile sale de cel original. Sunt apelate coduri care diferă doar prin numerotarea poziției 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 nesingulară de dimensiune . Prin înlocuirea rândurilor cu combinații liniare de rânduri (metoda Gauss), matricea rezultată poate fi redusă la forma

unde este matricea de identitate de ordin și este o matrice de dimensiune.

O matrice de forma (6.6) se numește matrice generatoare redusă la formă sistematică, iar codul corespunzător este numit sistematic. Codarea pentru codul sistematic este puțin mai ușoară decât pentru cod vedere generala:

, (6.7)

acestea. într-un cuvânt de cod, primele poziții sunt pur și simplu 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 un cod sistematic ocupă mult mai puțină memorie decât informațiile despre un cod liniar general.

Pentru un cod sistematic cu o matrice generatoare sub forma (6.6), matricea de verificare a paritatii poate fi calculata folosind formula

Exercițiul 6.6. Verificați (6.7). Sugestie: pentru a face acest lucru, trebuie să înlocuiți (6.8) și (6.6) în (6.4).

Cum să găsiți matricea de verificare a parității pentru codul nesistematic?

Foarte simplu. Este necesară aducerea matricei într-o formă sistematică și utilizarea (6.7). Dacă primele coloane ale matricei generatoare formează o submatrice nesingulară (primele poziții formează un set de informații), atunci pentru a-l aduce într-o formă sistematică, sunt suficiente operațiuni precum rearanjarea rândurilor și înlocuirea rândurilor cu combinații liniare de rânduri. 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ții.

Tocmai ne-am uitat la cele mai simple coduri de corecție ca exemplu - un cod cu o verificare simplă de paritate care permite detectarea unei singure erori în secvența primită, precum și codul iterativ bloc și codul cloud care corectează o singură eroare folosind un set a controalelor de paritate. În toate codurile, în timpul procesului de codificare rezistentă la zgomot, s-au format biți suplimentari și au fost adăugați la combinația de cod inițială.

Să definim regulile formale (generative) prin care se realizează codificarea, i.e. conversia unei secvențe de informații într-un cuvânt cod.

Cel mai simplu mod de a descrie sau de a specifica codurile de corectare este metoda tabelarăîn care fiecărei secvențe de informații i se atribuie pur și simplu un cuvânt cod din tabelul de coduri. De exemplu, pentru cel mai simplu cod cu o verificare de paritate, tabelul de corespondență dintre combinațiile sursă și cod va fi după cum urmează:

Această metodă de descriere a codurilor este aplicabilă oricăror coduri, nu doar celor liniare. Cu toate acestea, în mare La mărimea tabelul de coduri se dovedește a fi prea mare pentru a fi folosit în practică.

O altă modalitate de a specifica coduri de bloc liniare este utilizarea așa-numitelor sisteme de generare a ecuațiilor, definirea regulii prin care simbolurile secvențelor de informații 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 mai vizual mod de a descrie codurile bloc liniare este să le specificați folosind matrice generatoare, care este o formă compactă de reprezentare a unui sistem de ecuații de testare.

Bloc liniar Codul (l, /c) este complet determinat de o matrice G de dimensiune La X P cu elemente matrice binare. În acest caz, fiecare cuvânt de cod este o combinație liniară de rânduri ale matricei G și fiecare combinație liniară de rânduri G este un cuvânt de cod.

Vom numi coduri 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 cu o verificare de paritate, matricea generatoare va arăta astfel:

Lăsa T -(t 1; t 2, ..., tk) 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 simboluri de cuvinte cod Și va fi asa:

Cu alte cuvinte, La simbolurile cele mai din stânga ale cuvântului de cod coincid cu simbolurile secvenței de informații codificate, iar restul (n - La) simbolurile sunt combinații liniare de simboluri de 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 el însuși a mers pe al patrulea. Construiți o matrice generatoare pentru un astfel de cod.

Răspuns: conform intrigii sarcinii, un mesaj primit de comandant personal nu poate fi denaturat. Prin urmare, ne vom limita la a studia informațiile transmise de luptători. Într-un grup pornit de-a lungul unuia dintre drumuri, fiecare luptător trebuie să raporteze comandantului fie despre descoperirea unui obiect (notăm un astfel de raport ca „1”), fie despre absența unui obiect („0”). În absența distorsiunilor, rapoartele fiecărui luptător din aceeași grupă ar trebui să se potrivească. Prin urmare:

Matricea poate fi redusă la formă canonică, renumerotarea luptătorilor, i.e. de-a lungul primului drum trimițând primul, al patrulea și al cincilea, de-a lungul celui de-al doilea drum - al doilea, al șaselea și al șaptelea, de-a lungul celui de-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,/cj cod cu verificări de paritate generalizate.