1.3. Distanța minimă și corectarea erorilor
Unul dintre cei mai importanți parametri este distanța minimă de cod. Distanța de cod sau pur și simplu distanța cod V este distanța minimă între diferite cuvinte de cod, adică. E.
Pentru V binare sub Hamming distanta se refera la distanta.
Teorema 1.1. Codul V corectează toate combinațiile de t sau mai puține erori dacă și numai dacă distanța minimă nu este mai mică decât 2t +1, r. F. DV ≥ 2t +1.
Dovada se bazează pe construirea unei sfere de rază t în jurul fiecărui cuvânt de cod. Pentru fiecare dintre multiplicitate t eroare a fost corectată, cuvântul cu eroarea trebuie să fie conținută într-o sferă descrisă în jurul valorii de un singur cuvânt de cod. Astfel, distanța dintre centrele celor două sfere, t. E. diferite ar trebui să fie cuvintele de cod nu mai puțin de 2t +1. ilustrare geometrică prezentată în Fig. 3.
Teorema 1.2. Cod V detectează toate combinațiile de t sau mai puține erori dacă și numai dacă distanța minimă nu este mai mică t + 1, adică dV ≥ t +1.
Pentru fiecare eroare de multiplicitate t a fost detectată cuvânt cu eroarea nu ar trebui să fie codificate, t. E. Distanța dintre oricare codewords diferite trebuie să fie mai mare decât t.
Figura 3. Zonele de ale căror centre sunt codewords.
De exemplu, lungimea de cod 3 corectează toate erorile unice și detectează toate erorile-intrare dublu. Cod distanță 4 detectează toate erorile multiplicitate de 3 sau mai puțin; Cu toate acestea, acest cod este încă corect doar o eroare.
Problema construcția codului reale, adică. E. Lungimea cuvânt cod care ajunge la sute de simboluri, o distanță predeterminată de cod nu este rezolvată chiar forță brută cu ajutorul tehnologiei moderne de calculator. teoria codurilor oferă metode pentru construirea unor astfel de coduri.
Exemplu. Ca un exemplu, să încerce să construiască un cod cu cod de cuvânt lungime 5, care are trei simboluri de informație și corectă o eroare. Deoarece trei simboluri de informație, diferite ar trebui să fie 2 cuvintele de cod 3 = 8. Prin Teorema 1.1, distanța dintre două codewords diferite ar trebui să fie mai mică de 2 x 1 + 1 = 3. Sunt incluse în codul cuvântul V 00000. Apoi toate celelalte cuvintele de cod au o greutate de minimum 3. După includere în orice cuvinte cod de greutate V 3, nu se pot adăuga nici o greutate la cuvântul de cod 3, deoarece distanța dintre oricare două cuvinte 3 în greutate egale 2. pentru același motiv cuvântul 11111 de greutate 5, de asemenea, V. face parte din cuvintele de cod rămân 5 greutate 4, care nu este suficient pentru a avea 8 cuvinte de cod.