Kod liniowy - Linear code

W teorii kodowania , A kod liniowy jest kod korekcji błędów dla których każda kombinacja liniowa od słów kodowych jest słowo kodowe. Kody liniowe są tradycyjnie podzielone na kody blokowe i kody splotowe , chociaż kody turbo można postrzegać jako hybrydę tych dwóch typów. Kody liniowe pozwalają na bardziej wydajne algorytmy kodowania i dekodowania niż inne kody (por. dekodowanie syndromów ).

Kody liniowe są używane w korekcji błędów w przód i są stosowane w sposobach przesyłania symboli (np. bitów ) w kanale komunikacyjnym tak, że jeśli wystąpią błędy w komunikacji, niektóre błędy mogą zostać poprawione lub wykryte przez odbiorcę bloku wiadomości. Słowa kodowe w liniowym kodzie blokowym to bloki symboli, które są zakodowane przy użyciu większej liczby symboli niż oryginalna wartość do wysłania. Kod liniowy o długości n przesyła bloki zawierające n symboli. Na przykład [7,4,3] kod Hamminga jest liniowym kodem binarnym, który reprezentuje 4-bitowe wiadomości przy użyciu 7-bitowych słów kodowych. Dwa różne słowa kodowe różnią się co najmniej trzema bitami. W konsekwencji można wykryć do dwóch błędów na słowo kodowe, a jeden błąd można poprawić. Ten kod zawiera 2 ⁴ =16 słów kodowych.

Definicja i parametry

Kod liniowy o długości n i pozycjonowanie k jest liniowy podprzestrzeń C z wymiar k części przestrzeni wektorowej , gdzie jest skończonego z q elementów. Taki kod nazywamy kodem q- arnym. Jeśli q  = 2 lub q  = 3, kod jest opisany odpowiednio jako kod binarny lub kod trójskładnikowy . Wektory w C nazywane są słowami kodowymi . Rozmiar z kodem jest liczba słów kodowych i wynosi q ^k . ${\ Displaystyle \ mathbb {F} _ {q} ^ {n}}$${\ Displaystyle \ mathbb {F} _ {q}}$

Ciężar słowa kodowego jest liczba jego elementów, które są różne od zera, a odległość pomiędzy dwoma kodowych pada odległość Hamminga pomiędzy nimi, to znaczy liczbę elementów, które różnią się. Odległość d kodu liniowego jest minimalną wagą jego niezerowych słów kodowych lub równoważnie minimalną odległością między różnymi słowami kodowymi. Kod liniowy o długości n , wymiarze k i odległości d jest nazywany kodem [ n , k , d ].

Chcemy podać podstawę standardową, ponieważ każda współrzędna reprezentuje „bit”, który jest przesyłany przez „zaszumiony kanał” z pewnym małym prawdopodobieństwem błędu transmisji ( binarny kanał symetryczny ). Jeśli zastosuje się jakąś inną podstawę, to tego modelu nie da się zastosować, a metryka Hamminga nie mierzy liczby błędów w transmisji, tak jak tego chcemy. ${\ Displaystyle \ mathbb {F} _ {q} ^ {n}}$

Generator i macierze kontrolne

W liniowej podprzestrzeni w kod cała C (co może być bardzo duża) może być przedstawiony jako rozpiętość zbioru słów kodowych (znany jako podstawa w liniowym Algebra ). Te podstawowe słowa kodowe są często zestawiane w rzędach macierzy G znanej jako macierz generująca kod C . Gdy G ma postać macierzy blokowej , gdzie oznacza macierz jednostkową, a P jest pewną macierzą, wtedy mówimy, że G ma postać standardową . ${\ Displaystyle \ mathbb {F} _ {q} ^ {n}}$${\displaystyle k}$${\ Displaystyle {\ boldsymbol {G}} = [I_ {k} | P]}$${\ Displaystyle I_ {k}}$${\displaystyle k\razy k}$${\displaystyle k\times (nk)}$

Macierz H reprezentujących funkcję liniową których jądro jest C jest nazywana macierzy kontroli z C (lub czasami macierzy kontroli parzystości). Równoważnie H jest macierzą, której zerową przestrzenią jest C . Jeśli C jest kodem z macierzą generującą G w postaci standardowej , to jest macierzą kontrolną dla C. Kod generowany przez H nazywa się kodem dualnym C. Można zweryfikować, że G jest macierzą, a H jest macierzą matryca. ${\ Displaystyle \ phi: \ mathbb {F} _ {q} ^ {n} \ do \ mathbb {F} _ {q} ^ {nk}}$${\ Displaystyle {\ boldsymbol {G}} = [I_ {k} | P]}$${\ Displaystyle {\ boldsymbol {H}} = [-P ^ {T} | I_ {nk}]}$${\displaystyle k\razy n}$${\displaystyle (nk)\razy n}$

Liniowość gwarantuje, że minimalna odległość Hamminga d między słowem kodowym c ₀ a dowolnym innym słowem kodowym c  ≠  c ₀ jest niezależna od c ₀ . Wynika to z własności, że różnica c  −  c ₀ dwóch słów kodowych w C jest również słowem kodowym (tj. elementem podprzestrzeni C ) oraz własności, że d ( c , c ₀ ) =  d ( c  −  c _{0 )} , 0). Te właściwości sugerują, że

${\ Displaystyle \ min _ {c \ w C \ c \ neq c_ {0}} d (c, c_ {0}) = \ min _ {c \ w C \ c \ neq c_ {0}} d (c-c_{0},0)=\min _{c\in C,\ c\neq 0}d(c,0)=d.}$

Innymi słowy, aby znaleźć minimalną odległość między słowami kodowymi kodu liniowego, wystarczy spojrzeć na niezerowe słowa kodowe. Niezerowe słowo kodowe o najmniejszej wadze ma wtedy minimalną odległość do zerowego słowa kodowego, a zatem określa minimalną odległość kodu.

Odległość d kodu liniowego C jest również równa minimalnej liczbie liniowo zależnych kolumn macierzy kontrolnej H .

Dowód: Ponieważ , który jest odpowiednikiem , gdzie jest kolumną . Usuń te elementy z , te z są liniowo zależne. Dlatego jest co najmniej minimalna liczba kolumn zależnych liniowo. Z drugiej strony rozważ minimalny zestaw kolumn zależnych liniowo, gdzie jest zestawem indeksu kolumny. . Rozważmy teraz wektor taki, że if . Uwaga, ponieważ . Dlatego mamy , który jest minimalną liczbą liniowo zależnych kolumn w . Twierdzona własność jest zatem udowodniona. ${\ Displaystyle {\ pogrubienie {H}} \ cdot {\ pogrubienie {c}} ^ {T} = {\ pogrubienie {0}}}$${\ Displaystyle \ suma _ {i = 1} ^ {n} (c_ {i} \ cdot {\ boldsymbol {H_ {i}}}) = {\ boldsymbol {0}}}$${\displaystyle {\boldsymbol {H_{i}}}}$${\ Displaystyle i ^ {th}}$${\displaystyle {\boldsymbol {H}}}$${\displaystyle c_{i}=0}$${\displaystyle {\boldsymbol {H_{i}}}}$${\displaystyle c_{i}\neq 0}$${\displaystyle d}$${\ Displaystyle \ {{\ pogrubienie {H_ {j}}} | j \ w S \}}$${\displaystyle S}$${\ Displaystyle \ suma _ {i = 1} ^ {n} (c_ {i} \ cdot {\ pogrubiony symbol {H_ {i}}}) = \ suma _ {j \ w S} (c_ {j} \ cdot {\boldsymbol {H_{j}}})+\sum _{j\notin S}(c_{j}\cdot {\boldsymbol {H_{j}}})={\boldsymbol {0}}}$${\displaystyle {\boldsymbol {c'}}}$${\displaystyle c_{j}'=0}$${\displaystyle j\notin S}$${\displaystyle {\boldsymbol {c'}}\w C}$${\ Displaystyle {\ boldsymbol {H}} \ cdot {\ boldsymbol {c'}} ^ {T} = {\ boldsymbol {0}}}$${\displaystyle d\leq wt({\boldsymbol {c'}})}$${\displaystyle {\boldsymbol {H}}}$

Przykład: kody Hamminga

Jako pierwsza klasa kodów liniowych opracowanych do celów korekcji błędów, kody Hamminga są szeroko stosowane w systemach komunikacji cyfrowej. Dla każdej dodatniej liczby całkowitej istnieje kod Hamminga. Ponieważ ten kod Hamminga może poprawić 1-bitowy błąd. ${\displaystyle r\geq 2}$${\ Displaystyle [2 ^ {r} -1,2 ^ {r} -r-1,3] _ {2}}$${\displaystyle d=3}$

Przykład: liniowy kod blokowy z następującą macierzą generatora i macierzą kontroli parzystości jest kodem Hamminga. ${\displaystyle [7,4,3]_{2}}$

${\ Displaystyle {\ boldsymbol {G}} = {\ zacząć {pmatrix} 1\ 0\ 0\ 0\ 1\ 1\ 0\\0\ 1\ 0\ 0\ 0\ 1\ 1\\0\ 0 \ 1\ 0\ 1\ 1\ 1\\0\ 0\ 0\ 1\ 1\ 0\ 1\end{pmatrix}},}$ ${\ Displaystyle {\ boldsymbol {H}} = {\ zacząć {pmatrix} 1\ 0\ 1\ 1\ 1\ 0\ 0\\1\ 1\ 1\ 0\ 0\ 1\ 0\\0\ 1 \ 1\ 1\ 0\ 0\ 1\end{pmatrix}}}$

Przykład: kody Hadamarda

Kod Hadamarda jest kodem liniowym i jest w stanie poprawić wiele błędów. Kod Hadamarda może być skonstruowany kolumna po kolumnie: kolumna to bity binarnej reprezentacji liczby całkowitej , jak pokazano w poniższym przykładzie. Kod Hadamarda ma minimalną odległość i dlatego może korygować błędy. ${\ Displaystyle [2 ^ {r}, r, 2 ^ {r-1}] _ {2}}$${\ Displaystyle i ^ {th}}$${\displaystyle i}$${\ Displaystyle 2 ^ {r-1}}$${\ Displaystyle 2 ^ {r-2} -1}$

Przykład: liniowy kod blokowy z następującą macierzą generatora to kod Hadamarda: . ${\displaystyle [8,3,4]_{2}}$${\ Displaystyle {\ boldsymbol {G}} _ {miał} = {\ zacząć {pmatrix} 0\ 0\ 0\ 0\ 1\ 1\ 1\\0\ 0\ 1\ 1\ 0\ 0\ 1\ 1\\0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\end{pmatrix}}}$

Kod Hadamarda jest szczególnym przypadkiem kodu Reeda-Mullera . Jeśli wyjmiemy pierwszą kolumnę (kolumnę całkowicie zerową) z , otrzymamy kod simpleksowy , który jest podwójnym kodem kodu Hamminga. ${\ Displaystyle {\ boldsymbol {G}} _ {miał}}$${\displaystyle [7,3,4]_{2}}$

Algorytm najbliższego sąsiada

Parametr d jest ściśle związany ze zdolnością kodu do korekcji błędów. Ilustruje to następująca konstrukcja/algorytm (nazywany algorytmem dekodowania najbliższego sąsiada):

Wejście: Odebrany wektor v w . ${\ Displaystyle \ mathbb {F} _ {q} ^ {n}}$

Wyjście: słowa kodowego w najbliżej , jeśli w ogóle. ${\ Displaystyle w}$${\displaystyle C}$${\displaystyle v}$

• Zaczynając od , powtórz następujące dwa kroki.${\displaystyle t=0}$
• Wymień elementy kuli o promieniu (Hamminga) wokół odebranego słowa , oznaczonej . ${\displaystyle t}$${\displaystyle v}$${\ Displaystyle B_ {t} (v)}$
  • Dla każdego w , sprawdź, czy w . Jeśli tak, wróć jako rozwiązanie.${\ Displaystyle w}$${\ Displaystyle B_ {t} (v)}$${\ Displaystyle w}$${\displaystyle C}$${\ Displaystyle w}$
• Przyrost . Niepowodzenie tylko wtedy , gdy wyliczanie jest kompletne i nie znaleziono rozwiązania.${\displaystyle t}$${\displaystyle t>(d-1)/2}$

Mówimy, że liniowa jest korekcją błędów, jeśli istnieje co najwyżej jedno słowo kodowe w , dla każdego w . ${\displaystyle C}$${\displaystyle t}$${\ Displaystyle B_ {t} (v)}$${\displaystyle v}$${\ Displaystyle \ mathbb {F} _ {q} ^ {n}}$

Popularna notacja

Kody w ogólności są często oznaczane literą C , a kod o długości n i randze k (tj. mający k słów kodowych w swojej podstawie i k wierszy w macierzy generowania ) jest ogólnie określany jako ( n ,  k ) kod. Kody blokowe liniowe są często oznaczane jako kody [ n ,  k ,  d ], gdzie d oznacza minimalną odległość Hamminga kodu między dowolnymi dwoma słowami kodu.

(Notacji [ n ,  k ,  d ] nie należy mylić z notacją ( n ,  M ,  d ) używaną do oznaczenia nieliniowego kodu o długości n , rozmiarze M (tj. posiadającego M słowa kodowe) i minimalnej wartości Hamminga odległość d .)

Wiązanie singletona

Lemat ( ograniczenie singletona ): Każdy liniowy [n,k,d] kod C spełnia . ${\displaystyle k+d\leq n+1}$

Kod C, którego parametry spełniają k+d=n+1, nazywany jest maksymalną możliwą do oddzielenia odległością lub MDS . Takie kody, jeśli istnieją, są w pewnym sensie najlepsze z możliwych.

Jeśli C ₁ i C ₂ są dwoma kodami o długości n i jeśli istnieje permutacja p w symetrycznej grupie S _n dla której (c ₁ ,...,c _n ) w C ₁ wtedy i tylko wtedy, gdy (c _{p(1 )} ,...,c _p(n) ) w C ₂ , wtedy mówimy, że C ₁ i C ₂ są równoważne permutacjom . Mówiąc bardziej ogólnie, jeśli istnieje macierz jednomianowa, która wysyła C ₁ izomorficznie do C _2, wtedy mówimy, że C ₁ i C ₂ są równoważne . ${\displaystyle n\razy n}$ ${\ Displaystyle M \ dwukropek \ mathbb {F} _ {q} ^ {n} \ do \ mathbb {F} _ {q} ^ {n}}$

Lemat : Każdy kod liniowy jest permutacyjnym odpowiednikiem kodu w standardowej formie.

Twierdzenie Bonisoli

Kod definiuje się jako równoodległy wtedy i tylko wtedy, gdy istnieje pewna stała d taka, że ​​odległość między dowolnymi dwoma różnymi słowami kodowymi kodu jest równa d . W 1984 Arrigo Bonisoli określił strukturę liniowych kodów jednowagowych nad ciałami skończonymi i udowodnił, że każdy równoodległy kod liniowy jest sekwencją podwójnych kodów Hamminga .

Przykłady

Niektóre przykłady kodów liniowych obejmują:

Uogólnienie

Rozważano również przestrzenie Hamminga nad alfabetami niepolowymi, zwłaszcza nad skończonymi pierścieniami (zwłaszcza nad Z ₄ ), co dało początek modułom zamiast przestrzeni wektorowych i kodom pierścieniowo-liniowym (identyfikowanym z submodułami ) zamiast kodów liniowych. Typowa metryka zastosowana w tym przypadku to odległość Lee . Istnieje izometria Graya pomiędzy (tj. GF(2 ^2m )) z odległością Hamminga i (oznaczoną również jako GR(4,m)) z odległością Lee; jego główną atrakcją jest to, że ustanawia zgodność między niektórymi „dobrymi” kodami, które nie są liniowe, jak obrazy kodów pierścieniowo-liniowych z . ${\ Displaystyle \ mathbb {Z} _ {2} ^ {2 m}}$${\ Displaystyle \ mathbb {Z} _ {4} ^ {m}}$${\ Displaystyle \ mathbb {Z} _ {2} ^ {2 m}}$${\ Displaystyle \ mathbb {Z} _ {4} ^ {m}}$

Niedawno niektórzy autorzy określali takie kody nad pierścieniami po prostu jako kody liniowe.

Zobacz też

• Metody dekodowania

Bibliografia

Bibliografia

• JF Humphreys; MÓJ Perst (2004). Liczby, grupy i kody (2nd ed.). Wydawnictwo Uniwersytetu Cambridge. Numer ISBN 978-0-511-19420-7. Rozdział 5 zawiera łagodniejsze wprowadzenie (niż ten artykuł) do tematyki kodów liniowych.

Zewnętrzne linki

• q program generatora kodu arowego
• Tabele kodów: Ograniczenia parametrów różnych typów kodów , IAKS, Fakultät für Informatik, Universität Karlsruhe (TH)] . Online, aktualna tabela optymalnych kodów binarnych, zawiera kody niebinarne.
• Baza kodów Z4 Online, aktualna baza optymalnych kodów Z4.