Standardowa tablica

W teorii kodowania $lub$ tablica ( tablica Slepiana) to $,$ listę określonego ${\ Displaystyle \ mathbb {F} _ {q} ^ {n}}$ przestrzeń wektorowa . Tablice standardowe służą do dekodowania kodów liniowych ; tzn. znaleźć odpowiednie słowo kodowe dla dowolnego odebranego wektora.

Definicja

Standardowa tablica dla kodu [ n , k $}$ to tablica, w której: n $displaystyle q ^ {nk}$

1. 0 Pierwszy wiersz zawiera listę wszystkich słów kodowych (ze słowem kodowym po lewej stronie)
2. Każdy rząd to coset z liderem coset w pierwszej kolumnie
3. Wpis w i-tym wierszu i j-tej kolumnie jest sumą i-tego lidera cosetu i j-tego słowa kodowego.

Na przykład [ 5 , 2 ] -kod ma standardową tablicę w następujący sposób: do ${\ displaystyle C_ {3}}$ { 01101, 10110, 11011} 0

0	01101	10110	11011
10000	11101	00110	01011
01000	00101	11110	10011
00100	01001	10010	11111
00010	01111	10100	11001
00001	01100	10111	11010
11000	10101	01110	00011
10001	11100	00111	01010

Powyższe jest tylko jedną z możliwości dla tablicy standardowej; gdyby 00011 zostało wybrane jako pierwszy lider zestawu o wadze drugiej, zostałaby skonstruowana inna standardowa tablica reprezentująca kod.

00 Pierwszy wiersz zawiera $wektor$ słowa kodowe ( samo w sobie słowem kodowym). Ponadto skrajna lewa kolumna zawiera wektory o minimalnej wadze , wyliczając najpierw wektory o wadze 1, a następnie wykorzystując wektory o wadze 2. Również każdy możliwy wektor w przestrzeni wektorowej pojawia się dokładnie raz.

Konstruowanie standardowej tablicy

Ponieważ każdy możliwy wektor może wystąpić tylko raz w standardowej tablicy, należy zachować ostrożność podczas konstruowania. Standardową tablicę można utworzyć w następujący sposób:

1. 0 Wymień słowa kodowe $,$ zaczynając od jako pierwszy wiersz
2. Wybierz dowolny wektor o minimalnej wadze, którego nie ma jeszcze w tablicy. Wpisz to jako pierwszy wpis w następnym wierszu. Ten wektor jest oznaczony jako „ lider coset” .
3. Wypełnij wiersz, dodając lidera zestawu do słowa kodowego u góry każdej kolumny. Suma i-tego lidera cosetu i j-tego słowa kodowego staje się wpisem w wierszu i, kolumnie j.
4. Powtarzaj kroki 2 i 3, aż zostaną wyświetlone wszystkie wiersze/cosets, a każdy wektor pojawi się dokładnie raz.

Dodawanie wektorów odbywa się mod q. Na przykład kody binarne są dodawane mod 2 (co odpowiada bitowemu dodawaniu XOR). Na przykład w ${\ Displaystyle Z_ {2}}$ , 11000 + 11011 = 00011.

To, że wybranie różnych liderów cosetu stworzy nieco inną, ale równoważną tablicę standardową i nie wpłynie na wyniki podczas dekodowania.

Przykład konstrukcji

Niech będzie kodem binarnym [4,2] $do {\ displaystyle C$ . tj. C = {0000, 1011, 0101, 1110}. Aby skonstruować tablicę standardową, najpierw wymieniamy słowa kodowe w rzędzie.

0000

1011

0101

1110

Następnie wybieramy wektor o minimalnej wadze (w tym przypadku o wadze 1), który nie był używany. Ten wektor staje się liderem cosetu dla drugiego rzędu.

0000	1011	0101	1110
1000

Po kroku 3 uzupełniamy wiersz, dodając lider coset do każdego słowa kodowego.

0000	1011	0101	1110
1000	0011	1101	0110

Następnie powtarzamy kroki 2 i 3, aż wszystkie rzędy zostaną zakończone. Zatrzymujemy się, gdy osiągnęliśmy ${\ Displaystyle q ^ {nk} = 2 ^ {4-2} = 2 ^ {2} = 4}$ wierszy.

0000	1011	0101	1110
1000	0011	1101	0110
0100	1111	0001	1010
0010	1001	0111	1100

W tym przykładzie nie mogliśmy wybrać wektora 0001 jako lidera cosetu ostatniego rzędu, mimo że spełnia on kryterium minimalnej wagi (1), ponieważ wektor był już obecny w tablicy. Mogliśmy jednak wybrać go jako pierwszego lidera cosetu i skonstruować inną standardową tablicę.

Dekodowanie za pomocą standardowej tablicy

Aby zdekodować wektor przy użyciu standardowej tablicy, odejmij wektor błędu – lub lider coset – od otrzymanego wektora. Rezultatem będzie jedno ze słów kodowych $.$ Załóżmy na przykład, że używamy kodu C = {0000, 1011, 0101, 1110} i skonstruowaliśmy odpowiednią tablicę standardową, jak pokazano w powyższym przykładzie. Jeśli otrzymamy wektor 0110 jako wiadomość, znajdziemy ten wektor w tablicy standardowej. Następnie odejmujemy lidera coset wektora, czyli 1000, aby otrzymać wynik 1110. Otrzymaliśmy słowo kodowe 1110.

Dekodowanie za pomocą standardowej tablicy jest formą dekodowania najbliższego sąsiada . W praktyce dekodowanie $za$ pomocą standardowej tablicy wymaga dużej ilości pamięci - kod z 32 słowami kodowymi wymaga standardowej tablicy . Inne formy dekodowania, takie jak dekodowanie syndromowe , są bardziej wydajne.

Dekodowanie za pomocą standardowej tablicy nie gwarantuje, że wszystkie wektory zostaną zdekodowane poprawnie. Jeśli otrzymamy wektor 1010, użycie powyższej standardowej tablicy zdekoduje wiadomość jako 1110, odległość słowa kodowego wynosi 1. Jednak 1010 jest również oddalone o 1 od słowa kodowego 1011. W takim przypadku niektóre implementacje mogą wymagać ponownego wysłania wiadomości lub niejednoznaczny bit może zostać oznaczony jako wymazanie, a następujący po nim kod zewnętrzny może go poprawić . Ta niejednoznaczność jest kolejnym powodem, dla którego czasami stosuje się różne metody dekodowania.

Zobacz też

• Kod liniowy

•   Hill, Raymond (1986). Pierwszy kurs teorii kodowania . Seria Oxford Applied Mathematics and Computing Science. Oxford University Press . ISBN 978-0-19-853803-5 .