1. CODURI LINEARE DE BLOCK
Exemplele din secțiunea anterioară arată că problema construirii de coduri bune cu o anumită distanță de cod este destul de complexă și pentru o lungime suficient de lungă a codului de cod nu poate fi rezolvată printr-o căutare completă chiar și cu utilizarea facilităților moderne de calculatoare. Pentru a reduce căutarea pentru construirea de coduri bune, se folosește aparatul de algebră generală. Majoritatea codurilor utilizate în practică sunt codurile liniare.
1.1. Structura codurilor de bloc liniar
Rețineți că spațiul boolean B n. B =, este un set de vectori binari de lungime n. operație Å modulul adițional 2 este o operație de grup, iar setul B n este un spațiu liniar cu funcționare Å și înmulțirea cu un scalar din set.
Un cod binar sau de grup liniar este un subspațiu al spațiului liniar B n.
Astfel, un cod liniar este un set non-gol de cuvinte binare de lungime n, numite cuvinte de cod. astfel încât suma celor două cuvinte de cod este un cuvânt de cod. În orice cod liniar cuvântul zero 0 = 0. 0 îndeplinește rolul de zero. Mai mult, într-un cod binar liniar fiecare cuvânt este opus față de el însuși, deoarece c Å c = 0. 0 pentru orice cÎB n. Vom analiza în principal codurile binare liniare. Prin urmare, cuvântul "binar" va fi omis, iar operația Å Adăugările modulo 2 vor fi numite pur și simplu operațiunea de adăugare și notate cu +.
Un exemplu. Luați în considerare setul V =. O verificare directă arată că suma oricăror două cuvinte ale setului este un element al setului, adică V este un cod liniar.
Reamintim că într-un cod liniar (n, k) numărul k este dimensiunea blocului de simboluri de informație, care, atunci când este codificat, este transformat într-un bloc de n simboluri, unde n> k. Simbolurile n-k adăugate sunt numite caractere de verificare. Rețineți că nu este întotdeauna posibil să se spună ce caractere sunt informaționale și care sunt simbolurile de testare.
De exemplu, într-un cod liniar (5,3) V = baza este un set. Vectorul 01010 este reprezentat ca o combinație liniară 01010 = 1 × 10011 + 1 × 11001 + 1 × 11100. O verificare directă poate verifica dacă distanța de cod este de 3.
În general, pentru a găsi distanța de cod, cuvintele de cod sunt comparate între ele. Cu toate acestea, în codul liniar, distanța de cod este aceeași cu greutatea minimă a cuvântului de cod diferit de zero.
Teorema 1.1. Distanța de cod a codului liniar este egală cu greutatea minimă a cuvântului de cod diferit de zero.
Dovada. Fie distanța de cod să fie aceeași cu distanța dintre cuvintele de cod x și y. Deoarece V este un cod liniar, x + y = z, de asemenea, face parte din codul V; t. aproximativ. dV = w (z). Deoarece cuvântul zero aparține codului V, codul nu conține cuvinte non-zero cu o greutate mai mică decât dV.
Dovada. Fiecare cuvânt cod este o combinație liniară de cuvinte de cod de bază. Numărul de combinații liniare diferite este egal, adică, | V | ≤ 2 k. Două combinații liniare cu coeficienți diferiți nu coincid, deoarece vectorii de bază sunt liniar independenți. Prin urmare | V | = 2 k.
Articole similare
Trimiteți-le prietenilor: