Metode de decodare - Decoding methods

În teoria codificării , decodarea este procesul de traducere a mesajelor primite în cuvinte de cod ale unui cod dat . Au existat multe metode comune de mapare a mesajelor la cuvinte de cod. Acestea sunt adesea folosite pentru a recupera mesajele trimise pe un canal zgomotos , cum ar fi un canal binar simetric .

Notaţie

${\ displaystyle C \ subset \ mathbb {F} _ {2} ^ {n}}$ este considerat un cod binar cu lungimea ; vor fi elemente ale ; și este distanța dintre acele elemente. ${\ displaystyle n}$ ${\ displaystyle x, y}$ ${\ displaystyle \ mathbb {F} _ {2} ^ {n}}$ ${\ displaystyle d (x, y)}$

Decodare ideală a observatorului

Unul poate primi mesajul , apoi decodarea ideală a observatorului generează cuvântul de cod . Procesul are ca rezultat această soluție: ${\ displaystyle x \ in \ mathbb {F} _ {2} ^ {n}}$ ${\ displaystyle y \ în C}$

{\ displaystyle \ mathbb {P} (y {\ mbox {sent}} \ mid x {\ mbox {primit}})}

De exemplu, o persoană poate alege cuvântul de cod care este cel mai probabil să fie primit ca mesaj după transmisie. ${\ displaystyle y}$ ${\ displaystyle x}$

Convenții de decodare

Fiecare cuvânt de cod nu are o posibilitate așteptată: poate exista mai mult de un cuvânt de cod cu o probabilitate egală de a muta în mesajul primit. Într-un astfel de caz, expeditorul și receptorul (receptorii) trebuie să fie de acord din timp cu privire la o convenție de decodare. Convențiile populare includ:

Solicitați ca cuvântul cod să fie retrimis - cerere repetată automată .
Alegeți orice cuvânt de cod aleatoriu din setul de cuvinte de cod cel mai probabil care este mai aproape de acesta.
Dacă urmează un alt cod , marcați biții ambigui ai cuvântului cod ca ștergeri și sperați că codul exterior îi dezambiguizează

Decodare cu probabilitate maximă

Dat fiind un vector primit, decodificarea cu probabilitate maximă alege un cuvânt de cod care maximizează ${\ displaystyle x \ in \ mathbb {F} _ {2} ^ {n}}$ ${\ displaystyle y \ în C}$

{\ displaystyle \ mathbb {P} (x {\ mbox {received}} \ mid y {\ mbox {sent}})}

,

adică cuvântul de cod care maximizează probabilitatea de primire, având în vedere că a fost trimis. Dacă toate cuvintele de cod sunt la fel de probabil să fie trimise, atunci această schemă este echivalentă cu decodarea ideală a observatorului. De fapt, prin teorema lui Bayes , ${\ displaystyle y}$ ${\ displaystyle x}$ ${\ displaystyle y}$

{\ displaystyle {\ begin {align} \ mathbb {P} (x {\ mbox {primit}} \ mid y {\ mbox {sent}}) și {} = {\ frac {\ mathbb {P} (x { \ mbox {primit}}, y {\ mbox {trimis}}) {\ mathbb {P} (y {\ mbox {trimis}})} \\ & {} = \ mathbb {P} (y {\ mbox {trimis}} \ mid x {\ mbox {primit}}) \ cdot {\ frac {\ mathbb {P} (x {\ mbox {primit}})} {\ mathbb {P} (y {\ mbox { trimis}})}}. \ end {align}}}

După remediere , este restructurat și este constant, deoarece toate cuvintele de cod sunt la fel de susceptibile de a fi trimise. Prin urmare, este maximizată în funcție de variabilă exact atunci când este maximizată, iar revendicarea urmează. ${\ displaystyle \ mathbb {P} (x {\ mbox {primit}})}$ ${\ displaystyle x}$ ${\ displaystyle \ mathbb {P} (y {\ mbox {sent}})}$ ${\ displaystyle \ mathbb {P} (x {\ mbox {received}} \ mid y {\ mbox {sent}})}$ ${\ displaystyle y}$ ${\ displaystyle \ mathbb {P} (y {\ mbox {sent}} \ mid x {\ mbox {primit}})}$

Ca și în cazul decodării observatorului ideal, trebuie convenită o convenție pentru decodarea non-unică.

Problema de decodare a probabilității maxime poate fi, de asemenea, modelată ca o problemă de programare întreagă .

Algoritmul de decodare a probabilității maxime este o instanță a problemei „marginalizați o funcție de produs” care este rezolvată prin aplicarea legii distributive generalizate .

Decodare la distanță minimă

Având în vedere un cuvânt de cod primit , decodarea la distanță minimă alege un cuvânt de cod pentru a minimiza distanța de Hamming : ${\ displaystyle x \ in \ mathbb {F} _ {2} ^ {n}}$ ${\ displaystyle y \ în C}$

{\ displaystyle d (x, y) = \ # \ {i: x_ {i} \ not = y_ {i} \}}

adică alegeți cuvântul de cod cât mai aproape de . ${\ displaystyle y}$ ${\ displaystyle x}$

Rețineți că, dacă probabilitatea de eroare pe un canal discret fără memorie este strict mai mică de jumătate, atunci decodarea distanței minime este echivalentă cu decodarea probabilității maxime , deoarece dacă ${\ displaystyle p}$

{\ displaystyle d (x, y) = d, \,}

atunci:

{\ displaystyle {\ begin {align} \ mathbb {P} (y {\ mbox {primit}} \ mid x {\ mbox {sent}}) & {} = (1-p) ^ {nd} \ cdot p ^ {d} \\ & {} = (1-p) ^ {n} \ cdot \ left ({\ frac {p} {1-p}} \ right) ^ {d} \\\ end {align} }}

care (deoarece p este mai mic de jumătate) este maximizat prin minimizarea d .

Decodarea la distanță minimă este, de asemenea, cunoscută sub numele de decodare a celui mai apropiat vecin . Poate fi asistat sau automatizat folosind o matrice standard . Decodarea la distanță minimă este o metodă rezonabilă de decodificare atunci când sunt îndeplinite următoarele condiții:

Probabilitatea apariției unei erori este independentă de poziția simbolului. ${\ displaystyle p}$
Erorile sunt evenimente independente - o eroare la o poziție din mesaj nu afectează alte poziții.

Aceste ipoteze pot fi rezonabile pentru transmisiile pe un canal binar simetric . Ele pot fi nerezonabile pentru alte suporturi, cum ar fi un DVD, unde o singură zgârietură pe disc poate provoca o eroare în multe simboluri sau cuvinte de cod învecinate.

Ca și în cazul altor metode de decodificare, trebuie convenită o convenție pentru decodarea non-unică.

Decodarea sindromului

Decodarea sindromului este o metodă extrem de eficientă de decodare a unui cod liniar pe un canal zgomotos , adică unul pe care se fac erori. În esență, decodarea sindromului este decodarea la distanță minimă utilizând un tabel de căutare redus. Acest lucru este permis de liniaritatea codului.

Să presupunem că acesta este un cod liniar de lungime și distanță minimă cu matricea de verificare a parității . Atunci este clar că este capabil să corecteze până la ${\ displaystyle C \ subset \ mathbb {F} _ {2} ^ {n}}$ ${\ displaystyle n}$ ${\ displaystyle d}$ ${\ displaystyle H}$ ${\ displaystyle C}$

{\ displaystyle t = \ left \ lfloor {\ frac {d-1} {2}} \ right \ rfloor}

erorile făcute de canal (deoarece dacă nu se fac mai mult decât erori, atunci decodarea la distanță minimă va decoda în mod corect cuvântul de cod transmis incorect). ${\ displaystyle t}$

Acum, să presupunem că un cuvânt de cod este trimis pe canal și că apare modelul de eroare . Apoi este primit. Decodarea la distanță minimă obișnuită ar căuta vectorul într-un tabel de dimensiuni pentru cea mai apropiată potrivire - adică un element (nu neapărat unic) cu ${\ displaystyle x \ in \ mathbb {F} _ {2} ^ {n}}$ ${\ displaystyle e \ in \ mathbb {F} _ {2} ^ {n}}$ ${\ displaystyle z = x + e}$ ${\ displaystyle z}$ ${\ displaystyle | C |}$ ${\ displaystyle c \ în C}$

{\ displaystyle d (c, z) \ leq d (y, z)}

pentru toți . Decodarea sindromului profită de proprietatea matricei de paritate care: ${\ displaystyle y \ în C}$

{\ displaystyle Hx = 0}

pentru toți . Sindromul de Received este definit ca fiind: ${\ displaystyle x \ în C}$ ${\ displaystyle z = x + e}$

{\ displaystyle Hz = H (x + e) ​​= Hx + He = 0 + He = He}

Pentru a efectua decodarea ML într-un canal binar simetric , trebuie să căutați un tabel precomputat de dimensiuni , mapat la . ${\ displaystyle 2 ^ {nk}}$ ${\ displaystyle He}$ ${\ displaystyle e}$

Rețineți că aceasta are deja o complexitate semnificativ mai mică decât cea a unei decodificări standard a matricei .

Cu toate acestea, în ipoteza că nu s-au făcut mai multe erori în timpul transmisiei, receptorul poate căuta valoarea într-un tabel redus de dimensiuni. ${\ displaystyle t}$ ${\ displaystyle He}$

{\ displaystyle {\ begin {matrix} \ sum _ {i = 0} ^ {t} {\ binom {n} {i}} \\\ end {matrix}}}

Listă decodare

Decodarea setului de informații

Aceasta este o familie de metode probabiliste din Las Vegas , toate bazate pe observația că este mai ușor să ghiciți destule poziții fără erori decât să ghiciți toate pozițiile de eroare.

Cea mai simplă formă se datorează Pdomeniului: Să fie generatorul matricea utilizată pentru codificare. Selectați coloane ale la întâmplare și indicați prin submatricea corespunzătoare a . Cu o probabilitate rezonabilă va avea rang complet, ceea ce înseamnă că , dacă vom lăsa să fie sub-vector pentru pozițiile corespunzătoare ale oricărui cuvânt de cod al unui mesaj , putem recupera ca . Prin urmare, dacă am avea norocul că aceste poziții ale cuvântului primit nu conțin erori și, prin urmare, au egalat pozițiile cuvântului cod trimis, atunci putem decoda. ${\ displaystyle G}$ ${\ displaystyle k \ times n}$ ${\ displaystyle C}$ ${\ displaystyle k}$ ${\ displaystyle G}$ ${\ displaystyle G '}$ ${\ displaystyle G}$ ${\ displaystyle G '}$ ${\ displaystyle c '}$ ${\ displaystyle c = mG}$ ${\ displaystyle C}$ ${\ displaystyle m}$ ${\ displaystyle m}$ ${\ displaystyle m = c'G '^ {- 1}}$ ${\ displaystyle k}$ ${\ displaystyle y}$

Dacă au apărut erori, probabilitatea unei astfel de selecții norocoase de coloane este dată de . ${\ displaystyle t}$ ${\ displaystyle \ textstyle {\ binom {nt} {k}} / {\ binom {n} {k}}}$

Această metodă a fost îmbunătățită în diferite moduri, de exemplu de Stern și Canteaut și Sendrier.

Probabilitate maximă de răspuns parțial

Probabilitatea maximă de răspuns parțial ( PRML ) este o metodă de conversie a semnalului analogic slab de la capul unui disc magnetic sau unitate de bandă într-un semnal digital.

Decodor Viterbi

Un decodor Viterbi folosește algoritmul Viterbi pentru decodarea unui flux de biți care a fost codificat folosind corecția de eroare directă pe baza unui cod convoluțional. Distanța Hamming este utilizată ca metrică pentru decodoarele Viterbi cu decizie dificilă. Distanța euclidiană pătrată este utilizată ca metrică pentru decodoarele de decizie soft.

Vezi si

Referințe

Lecturi suplimentare

Hill, Raymond (1986). Un prim curs în teoria codificării . Seria Oxford Mathematics Applied and Computing Science. Oxford University Press . ISBN 978-0-19-853803-5 .
Pless, Vera (1982). Introducere în teoria codurilor de corectare a erorilor . Seria Wiley-Interscience în matematică discretă. John Wiley & Sons . ISBN 978-0-471-08684-0 .
van Lint, Jacobus H. (1992). Introducere în teoria codării . Texte postuniversitare în matematică (GTM). 86 (2 ed.). Springer-Verlag . ISBN 978-3-540-54894-2 .

Languages

In other projects