7.Macierze H i G ver 3

Macierze H i G – TUTORIAL

by z++

Metodą (wielu) prób i błędów odnaleźliśmy całkiem sprawny algorytm wyznaczania macierzy G na podstawie macierzy H i na odwrót. Radzę przejść od razu do metody nr 3 i ewentualnie doczytać. Weźmy układ równań opisujący kod: (z braku lepszego znaczka pod ręką stosowałem

)

Sposób 1. Na podstawie tego układu rozpisujemy macierz parzystości (polega to na tym że macierz ma taką szerokość ile wynosi maksymalny x (w tym wypadku 7) a wysokość tyle ile jest równań. Jak w równaniu występuje xi to w i-tej kolumnie wpisujemy 1, jak nie to 0:

Po pierwsze musimy pamiętać to że część bitów w kodzie jest bitami informacyjnymi a część służy sprawdzaniu parzystości (bity kontrolne, parzystości – różnie to nazywają). Zazwyczaj (czyli wg wszelkiej dostępnej i niedostępnej literatury i Wikipedii) bity parzystości znajdują się na 2i-tej pozycji, ale nie zawsze. W tym przypadku tak jest, ale na zadaniach z kolokwium. Zaznaczmy kolumny w których znajduje się tylko jedna jedynka:

Numery tych kolumn czyli 1, 2 i 4 to pozycje bitów kontrolnych. W tym przypadku patrząc tylko na zielone pola mamy do czynienia z macierzą jednostkową. Jeśli nie to należy tak pozamieniać wiersze, żeby była. Są inne, mniej chamskie metody, ale – jak nauczyła mnie praktyka i zadanie z kolokwium – nie zawsze działają. Ten algorytm na razie zawsze się sprawdził. Żółte kolumny to pozycje bitów informacyjnych. Jest ich jak widać 4. Taka będzie ilość wierszy macierzy G. Tworząc macierz generującą trzeba patrzeć na zaznaczony i niezaznaczony obszar jako dwie niezależne macierze, pamiętając przy tym że kolumny muszą pozostać na swoich miejscach (wszak pozycje bitów pozostają te same. Nie ma zamieniania). Rysujemy macierz G o wspomnianej wcześniej ilości wierszy równej ilości bitów informacyjnych i ilości kolumn jak wcześniej. W kolumnach o numerach takich jak pozycje bitów informacyjnych (czyli żółtych) wpisujemy macierz jednostkową, zielone pola zostawiamy puste.

Teraz musimy się wrócić do (UWAGA) informacyjnej (ŻÓŁTEJ) części macierzy H i ją przetransponować

Następnie to co powstalo nam w wyniku transponowania wpisujemy do zielonej części macierzy G

Prawda że proste? Dokładnie tym samym sposobem można z macierzy G otrzymać macierz H. Wynika to z tego że

Sposób 2. Ta metoda jest oparta o to co znalazłem w książce Wesołowskiego. Też nie jestem na 100% pewien dlatego bracia studenci, kontrolujta co się dzieje. Korzystałem z niej na samym początku. Równanie przekształcamy w ten sposób że bity kontrolne (czyli te które w układzie równań pojawią się tylko raz) przerzucamy na drugą stronę



Najzwyczajniej w świecie: bez zmiany znaków czy coś. To jest xor! Wypisujemy macierz jednostkową na pozycjach informacyjnych: (warto nad macierzą wypisać sobie numery kolumn)

Zaczynamy od x3, ponieważ w pierwszym wierszu dla niego jest ‘1’. A potem patrząc do równania po prawej patrzymy: x3 pojawiło się w rówaniu na x1 i x2 więc tam wpisujemy 1, a w równaniu na x4 się nie pojawiło więc 0.

Analogicznie dla pozostałych bitów informacyjnych:



Jakbyśmy potrzebowali stworzyć macierz H na podstawie macierzy G przekształcamy równania w drugą stronę



I na podstawie układu równań po lewej, rozpisujemy macierz (opisaną w sposobie I dość trywialną metodą) H. Sposób 3. Kanoniczny (wbrew pozorom - najszybszy) Podobny jak sposób drugi tyle że x1, x2 i x4 wyliczamy bezpośrednio z równań: Dla wiersza 1:

Analogicznie pozostałe wiersze.

Długość Hamminga Mając macierz generującą H możemy wyznaczyć odległość Hamminga, potrzebną do wyznaczenia minimalnej ilości detekcji i korekcji błędów. Odległość Hamminga (DH) dla dwóch ciągów jest ilością bitów (lub znaków) na których różnią się te ciągi, czyli mówiąc trudniej dla ciągów binarnych a i b DH jest równa ilości jedynek wyrażenia . Dla macierzy opisujących kod Hamminga sprawa jest trochę trudniejsza, bowiem jest to minimalna liczba kolumn która po zxorowaniu da nam wektor zerowy. Jeśli mamy dwie kolumny takie same to DH=2. Jeśli nie, musimy sumować (ekskluzywnie oczywiście). W większości przypadków odległość jest równa 3. Jeśli weźmiemy kolumny 1, 4 i 5 i zxorujmy wierszami: (xorowanie jest łączne więc po prostu xorujemy po kolei)

3 kolumny => DH= 3 Możliwą ilość detekcji oznaczmy przez eD a możliwą ilość korekcji przez eK. Wg Wikipedii

Co zasadniczo zgadza się z wynikami z zadań. Dla DH=3 możliwa ilość detekcji jest mniejsza od 3 czyli maksymalna ilość detekcji jest równa 2, z kolei możliwa ilość korekcji jest mniejsza od 1.5 czyli maksymalna ilość korekcji jest równa 1.