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 |