Przykład
Procedurę dekodowania metodą polowania na błędy zilustrujemy na przykładzie binarnego systematycznego kodu BCH o parametrach(15,7,2), generowanego przez wielomian
Załóżmy, że ciąg nadany c, ciąg błędów e i ciąg odebrany y mają postać:
Przyjęliśmy więc, że podczas transmisji wystąpiły dwa błędy, na pozycjach: dziewiątej i trzynastej. Pozycje błędne w odebranym ciągu pogrubiono.
Obliczymy najpierw resztę z podziału wielomianu odebranego y(x) przez wielomian generujący kod g(x):
1111101
101101101101010 : 111010001
111010001
101111001
111010001
101010000
111010001
100000011
111010001
110100100
111010001
111010110
111010001
111
Waga reszty
jest większa od krotności korygowalnych błędów t = 2, błędy nie wystąpiły więc na pozycjach kontrolnych.
Pominiemy kolejne przesunięcia ciągu y, ponieważ wiemy, gdzie wystąpiły błędy. Przesunięcie odebranego ciągu o sześć pozycji w lewo powoduje, że błędy znajdą się na pozycjach
y(6) = 101101010101101.
Sprawdzimy wagę reszty z podziału y(6) przez g(x):
1111100
101101010101101 : 111010001
111010001
101110111
111010001
101001100
111010001
100111011
111010001
111010101
111010001
10001
Waga reszty jest równa krotności błędów korygowalnych t = 2, co oznacza, że błędy znalazły się na pozycjach kontrolnych. Możemy więc skorygować błędy przez dodanie do y(6) reszty
r = 10001 przesuniętej o sześć pozycji w lewo, a następnie dokonanie odwrotnego przesunięcia skorygowanego ciągu:
y(6) |
= |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1, |
r(6) |
= |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1, |
c*(6) |
= |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0, |
c* |
= |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0, |
przy czym c* = [c*(6)](-6). Ciąg odtworzony c* jest taki sam jak ciąg nadany, a więc korekcja błędów została przeprowadzona poprawnie.
Przykład
Przeanalizujemy proces dekodowania większościowego opartego na rozdzielnych (nie związanych) testach ortogonalnych na przykładzie binarnego systematycznego kodu BCH o parametrach(15,7,2), generowanego przez wielomian Macierz kontrolna kodu ma postać
Oznaczmy wiersze macierzy H liczbami rzymskimi od I do VIII. Z macierzy H tworzymy macierz testów ortogonalnych względem pozycji , tak aby pozycja ta wchodziła do wszystkich testów, otrzymujemy wówczas
przy czym wiersze macierzy zostały utworzone z wierszy macierzy H następująco:
a = II + VI + VIII,
b = III + VII,
c = V,
d = I.
Jawna postać testów ortogonalnych jest następująca:
Reguła korekcyjna dla rozpatrywanego kodu ma postać:
przy czym Nl oznacza liczbę niezerowych testów.
Dekoder działający według opisanej reguły pokazano na rysunku. Po wprowadzeniu odebranego ciągu y do rejestru wyznacza się wartości testów a, b, c i d, których podstawie element progowy podejmuje decyzję o pozycji s14 nadanego ciągu kodowego. Po zdekodowaniu pozycji y14 następuje przepisanie skorygowanej wartości (ewentualnie) y14 do pierwszej komórki rejestru (o numerze 0) z jednoczesnym przepisaniem zawartości komórek o numerach od 0 do n - 2 do komórek o numerach od 1 do n - 1. Następuje dekodowanie pozycji yn-2. Proces dekodowania kończy się po zdekodowaniu w analogiczny sposób pozostałych pozycji odebranego ciągu, aż do pozycji y0 włącznie.
Niech ciąg nadany c, ciąg błędów z i ciąg odebrany y mają postać:
Działanie dekodera przedstawiono w tabeli
Tabela
Działanie dekodera systematycznego binarnego kodu BCH (15,7,2), pracującego według reguły dekodowania większościowego ortogonalizowanego jednoetapowo
Pozycja rejestru |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
Nl |
|
y |
= |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
y(1) |
= |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
3 |
y(2) |
= |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
y(3) |
= |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
y(4) |
= |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
y(5) |
= |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
4 |
y(6) |
= |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
y(7) |
= |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
y(8) |
= |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
y(9) |
= |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
y(10) |
= |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
y(11) |
= |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
y(12) |
= |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
y(13) |
= |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
y(14) |
= |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
y(15) |
= |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
POLOWANIE NA BŁĘDY
1111101
101101101101010 : 111010001
111010001
101111000
111010001
101010010
111010001
100000111
111010001
110101100
111010001
111110110
111010001
100111
y(6) = 101101010101101.
1111100
101101010101101 : 111010001
111010001
101110111
111010001
101001100
111010001
100111011
111010001
111010101
111010001
10001
y(6) |
= |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1, |
r(6) |
= |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1, |
s*(6) |
= |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0, |
s* |
= |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0, |
DEKODOWNIE WIĘKSZOŚCIOWE
Pozycja rejestru |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
Nl |
|
y |
= |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
y(1) |
= |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
3 |
y(2) |
= |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
y(3) |
= |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
y(4) |
= |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
y(5) |
= |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
4 |
y(6) |
= |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
y(7) |
= |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
y(8) |
= |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
y(9) |
= |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
y(10) |
= |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
y(11) |
= |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
y(12) |
= |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
y(13) |
= |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
y(14) |
= |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
y(15) |
= |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
Stany rejestru kodera systematycznego kodu cyklicznego (15,10),
generowanego przez wielomian 
Takt |
Wejście |
Stan komórek rejestru |
|
|
|
|
|
Wyjście |
|
|
P |
P |
P |
P |
P |
P |
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
2 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
3 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
4 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
5 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
6 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
7 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
8 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
9 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
10 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
11 |
|
|
0 |
1 |
1 |
0 |
0 |
0 |
12 |
|
|
0 |
0 |
1 |
1 |
0 |
0 |
13 |
|
|
0 |
0 |
0 |
1 |
1 |
0 |
14 |
|
|
0 |
0 |
0 |
0 |
1 |
1 |
15 |
|
|
0 |
0 |
0 |
0 |
0 |
1 |
Wyszukiwarka
Podobne podstrony:
Kody blokowe, 1 - Transmisja danych, 2
Kody blokowe, Elementy algebry, ELEMENTY ALGEBRY
Kody blokowe, 3 - Kody cykliczne-1, 6
Kody blokowe, 2 - Blokowe kody liniowe, 6
Kody blokowe, Wykaz oznaczeń, WYKAZ OZNACZE˙
Kody blokowe, 4 - Kody splotowe, 4
Przyk┼éadowe pytania na egzamin z LA (2) , Przykładowe pytania na egzamin z LA
ef i przyklady produkty blokowe
Przykadowe wyliczenia niekt˘rych wska«nik˘w wykorzystywanych przy ocenie sytuacji finansowej , Przy
Tragizm pokolenia Kolumbów na przykładzie wybranych wierszy K.K.Baczyńskiego, Tragizm pokolenia Kolu
SYSTEMOWE PRZYK üADY, SYSTEMOWE PRZYKŁADY ROZWIĄZAŃ PODŁÓG
PRZYKŁADOWE KODY PISMA
Asembler ARM przyklady II
Sily przyklady
Przykłady roli biologicznej białek
style poznawcze jako przykład preferencji poznawczych
więcej podobnych podstron