Dom / Problemy/ Kodowanie w pętli. Centrum edukacyjno-metodyczne szkolenia językowego avtf kc

Kodowanie w pętli. Centrum edukacyjno-metodyczne szkolenia językowego avtf kc

Najprostszy kod cykliczny z możliwością wykrywania pojedynczych błędów oraz błędów o nieparzystej wielokrotności. Wielomian generujący tego kodu ma postać Spośród wielomianów nierozkładalnych wchodzących w skład rozwinięcia wielomian ten jest wielomianem najmniejszego stopnia, a więc dla dowolnej liczby bitów informacyjnych potrzebny jest tylko jeden bit kontrolny. Wartość znakowa tego bitu zapewnia parzystość liczby jedynek w dowolnej dozwolonej kombinacji kodu. Powstały cykliczny kod kontroli parzystości jest w stanie wykryć nie tylko pojedyncze błędy w poszczególnych bitach, ale także błędy w dowolnej nieparzystej liczbie bitów.

Przykład. Skonstruuj kod cykliczny dla Ponieważ wielomian generujący jest wielomianem pierwszego stopnia, liczba bitów kontrolnych W konsekwencji, Aby skonstruować kod cykliczny, konstruujemy macierz generującą

Aby skonstruować dodatkową macierz, znajdujemy resztę z dzielenia ostatniego wiersza macierzy transponowanej jednostki, uzupełnionej zerami, przez wybrany wielomian:

Zatem dodatkowa macierz C, k ma postać

Teraz budujemy macierz generowania

Wiersze tej macierzy to pierwsze trzy kombinacje kodu. Pozostałe dozwolone kombinacje można uzyskać sumując modulo dwa wszystkie możliwe kombinacje wierszy macierzy. Wynikowe kombinacje zniszczonych kodów podano w tabeli. 39.

Tabela 39 (patrz skan)

Interesujące jest rozważenie następującego najprostszego kodu z wielomianu nierozkładalnego drugiego stopnia

Ogólny widok macierzy generowania kodu cyklicznego utworzonego przez wielomian różni się budową macierzy dodatkowej posiadającej dwie kolumny.

Łatwo jest zweryfikować, że przy podzieleniu przez dany generator wielomiany wyrażające wiersze

macierz identyczności (aby znaleźć dodatkową macierz, tworzone są trzy rodzaje reszt: 11, 01 i 10. W konsekwencji waga każdej kombinacji otrzymanego kodu -wyniesie co najmniej dwa. Minimalna odległość kodu między dowolnymi dwiema kombinacjami wynosi również dwa. Ale najprostsze Jednak możliwości korekcyjne obu kodów nie są takie same.Rozważany kod ma dużą redundancję i pozwala wykryć nie tylko błędy o nieparzystej wielokrotności, ale także wszelkie sparowane błędy sąsiednie, a także wszystkie błędy odseparowane o jeden niezniekształcony element.

Klasa kodów liniowych, zwanych kody Cshaic... Nazwa pochodzi od głównej właściwości tych kodów: jeśli jakaś kombinacja kodów należy do kodu cyklicznego, to kombinacja uzyskana przez cykliczną permutację oryginalnej kombinacji (przesunięcie cykliczne) również należy do kodu cyklicznego. ten kod:

Drugą właściwością wszystkich dozwolonych kombinacji kodów cyklicznych jest ich podzielność bez reszty przez wybrany wielomian, zwany generującym.

Właściwości te są wykorzystywane w konstrukcji kodów do kodowania i dekodowania urządzeń, a także w wykrywaniu i korygowaniu błędów.

Kody cykliczne to cała rodzina kodów korygujących błędy (jedną z odmian są kody Hamminga), która zapewnia dużą elastyczność w zakresie możliwości implementacji kodów z niezbędną zdolnością do wykrywania i korygowania błędów, które pojawiają się podczas przesyłania kombinacji kodów przez kanał komunikacyjny. Kod cykliczny odnosi się do bloku systematycznego (l, &) - kody, w których Do pierwsze cyfry są kombinacją kodu podstawowego, a kolejne (l - Do) cyfry są sprawdzane.

Konstrukcja kodów cyklicznych polega na operacji dzielenia przesyłanego słowa kodowego przez generowanie nieredukowalnego wielomianu stopnia G. Pozostała część podziału służy do tworzenia cyfr kontrolnych. W tym przypadku operacja dzielenia poprzedzona jest operacją mnożenia, która wykonuje przesunięcie w lewo ^ -bitowej kombinacji kodów informacji o g zrzuty.

Podczas dekodowania odebranego n-bitowego słowa kodowego, ponownie przeprowadza się dzielenie przez wielomian generujący (generujący, generujący).

Syndromem błędu w tych kodach jest obecność pozostałej części dzielenia otrzymanego słowa kodowego przez wielomian generujący. Jeśli syndrom wynosi zero, uważa się, że nie ma błędów. W przeciwnym razie, korzystając z powstałego syndromu, można określić numer bitowy odebranego słowa kodowego, w którym wystąpił błąd i go poprawić.

Nie wyklucza się jednak wielokrotnych błędów w kombinacjach normowych, co może prowadzić do fałszywych poprawek i (lub) niewykrycia błędów podczas przekształcania jednej dozwolonej kombinacji w inną.

Niech łączna liczba bitów w bloku będzie równa i, z czego przydatna informacja nosić T bitów, to w przypadku błędu można poprawić j bitów. Zależność 5 na NS oraz T dla kodów można określić z tabeli. 2.6.

Tabela 2.6

Zależność całkowitej liczby cyfr kombinacji od liczby cyfr informacyjnych i poprawionych

Zwiększenie różnicy (n - t), możesz nie tylko zwiększyć liczbę korygowanych bitów s, ale także wykryć wiele błędów. W tabeli przedstawiono wartości procentowe wykrytych wielokrotnych błędów. 2.7.

Tabela 2.7

Procent wykrytych wielu błędów

Wygodnie jest opisywać kody cykliczne i ich budowę za pomocą wielomianów (lub wielomianów). Kombinacja jest zapisana w postaci wielomianu w celu przedstawienia w sformalizowany sposób operacji przesunięcia cyklicznego oryginalnego słowa kodowego. Tak więc kombinację kodu „-elementowego można opisać wielomianem (NS- 1) stopnie:

gdziea „_j =(0, 1) ia „_, =0 odpowiadają zerowym elementom kombinacji, q „_, = 1 - niezerowe;i- numer bitu kombinacji kodów.

Przedstawmy wielomiany dla konkretnych kombinacji 4-elementowych:

Operacje dodawania i odejmowania są równoważne i asocjacyjne i są wykonywane modulo 2:

Przykłady wykonywania operacji:

Operacja dzielenia jest zwykłym dzieleniem wielomianów, ale zamiast odejmowania stosuje się dodawanie modulo 2:

Cykliczne przesuwanie kombinacji kodowej - przesuwanie jej elementów od prawej do lewej bez naruszania ich kolejności, tak aby skrajny lewy element zajął miejsce skrajnego prawego.

Główne właściwości i nazwa kodów cyklicznych związane są z faktem, że wszystkie dozwolone kombinacje bitów w przesyłanym komunikacie (słowa kodowe) można uzyskać poprzez operację przesunięcia cyklicznego pewnego słowa kodowego źródłowego.

Załóżmy, że podano oryginalną kombinację kodu i odpowiadający jej wielomian:

Zwielokrotniać Oh) na NS:

Od maksymalnego stopnia NS w słowie kodowym o długości NS nie przekracza (n - 1), następnie z prawej strony wynikowego wyrażenia, aby uzyskać oryginalny wielomian, należy odjąć Oh"- 1). Odejmowanie Oh"- 1) nazywa się braniem reszty modulo (x n - 1).

Przesunięcie oryginalnej kombinacji o / takty można przedstawić w następujący sposób: a (x)? T- Oh"- 1), tj. mnożenie Oh) nah "i biorąc resztę modulo (x" - 1). Wzięcie reszty jest konieczne w przypadku uzyskania wielomianu stopnia większego lub równego NS.

Idea konstruowania kodów cyklicznych opiera się na wykorzystaniu wielomiany nierozkładalne. Wielomian nierozkładalny to wielomian, którego nie można przedstawić jako iloczyn wielomianów o niższych stopniach, tj. podzielna tylko przez siebie lub przez jeden i niepodzielna przez żaden inny wielomian. Wielomiany (x "+ 1) są podzielne przez taki wielomian bez reszty. Wielomiany nierozkładalne w teorii kodów cyklicznych pełnią rolę generowania wielomianów.

Wracając do definicji kodu cyklicznego i uwzględniając zapis operacji przesunięcia cyklicznego kombinacji kodów, możemy zapisać macierz generowania kodu cyklicznego w postaci:

gdzieP (x)- oryginalna kombinacja kodów, na podstawie której wszystkie pozostałe(T- 1) podstawowe kombinacje;

С, = 0 lubCj =1 („O”, jeśli wynikowy stopień wielomianuP(x)-x ‘nie przekracza (l - 1) lub "1" - jeśli tak).

Połączenie P (x) nazywana jest kombinacją generującą (generator). Aby skonstruować kod cykliczny wystarczy odpowiednio dobrać P(x). Wtedy wszystkie inne kombinacje norm są takie same jak w normie grupowej.

Wielomian generujący musi spełniać następujące wymagania:

P (x) musi być niezerowe;
waga P (x) nie może być mniejsza niż minimalna odległość kodu: V(P(x))>dmm;
P (x) musi mieć maksymalny stopień k (k - liczba zbędnych elementów w kodzie);
P (x) musi być dzielnikiem wielomianu (x "- 1).

Spełnienie ostatniego warunku prowadzi do tego, że wszystkie działające kombinacje kodowe kodu cyklicznego uzyskują własność podzielności przez P (x) bez reszty. Biorąc to pod uwagę, możemy podać inną definicję kodu cyklicznego: kod cykliczny to kod, którego wszystkie kombinacje robocze są podzielne przez wielomian generujący bez reszty.

Do określenia stopnia wielomianu generującego można posłużyć się wyrażeniem r> log 2 (i + 1), gdzie NS- wielkość przesyłanego pakietu na raz, tj. długość skonstruowanego kodu cyklicznego.

Przykłady generowania wielomianów podano w tabeli. 2.8.

Tabela 2.8

Przykłady wielomianów generujących

Algorytm uzyskiwania dozwolonej kombinacji kodu cyklicznego z kombinacji kodu prostego jest następujący.

Niech zostanie podany wielomian P (x) = a z _ (x z + a z _ 2 x r ~ 1 + ... + 1, który określa możliwości korekcyjne kodu, oraz liczbę bitów kontrolnych Do, a także oryginalne połączenie prostego kodu od elementu i bitów informacyjnych w postaci wielomianu m(x).

Wymagane jest określenie dozwolonej kombinacji kodowej kodu cyklicznego (oraz Do).

1. Reprezentujemy oryginalną kombinację kodową w postaci wielomianu m(x). Mnożymy wielomian oryginalnego słowa kodowego przez x g: A t (x) x re. Stopień generowania wielomianu g równa wartości najbardziej znaczącego bitu oryginalnego słowa kodowego.
2. Określ cyfry kontrolne, które uzupełniają oryginalną kombinację informacji do dozwolonej, jako pozostałość z dzielenia iloczynu uzyskanego w poprzednim akapicie przez generator

wielomian:

Pozostała część podziału jest oznaczona jako R(x).

3. W końcu rozwiązany wzór cykliczny

kod jest zdefiniowany jako = A t(x)? xr + R(x).

Aby określić błędy w otrzymanym słowie kodowym, wystarczy podzielić je przez wielomian generujący. Jeśli zaakceptowana kombinacja jest prawidłowa, to pozostała część dzielenia będzie wynosić zero. Reszta niezerowa wskazuje, że zaakceptowana kombinacja zawiera błędy. Według rodzaju reszty (syndromu), w niektórych przypadkach możliwe jest również wyciągnięcie wniosków na temat natury błędu i jego lokalizacji oraz poprawienie błędu.

Algorytm określania błędu jest następujący.

Niech zostaną podane "-elementowe kombinacje ( n = k + t).

1. Identyfikujemy fakt obecności błędu. Otrzymujemy pozostałą część dzielenia przyjętej kombinacji A n - (x) do wielomianu generującego P (x): A(NS)
--- = Rq (x). Obecność pozostałych R 0 (x) dla (A 0 (x) f 0) wskazuje P (x)

o błędzie.

2. Podziel wynikowy wielomian # (x) = „_,(NS) 0 Rq (x) na generator Rg (x): W-1 = R(x), gdzie R (x)- saldo bieżące.

3. Porównaj LDx) i R(x). Jeśli są równe, to błąd wystąpił w najbardziej znaczącym bicie. Jeśli nie, to zwiększamy stopień przyjętego wielomianu o x i dzielimy ponownie:

4. Porównaj otrzymane saldo z Rq(x). Jeśli są równe, błąd wystąpił w drugim bicie. Jeśli nie są równe, to mnożymy Szx) x 2 i powtarzaj te operacje, aż otrzymamy

R(x) = piekło.

Błąd będzie w cyfrze odpowiadającej liczbie, o którą zwiększono stopień Szx), plus 1. Na przykład w przypadku równości R (x) i LDx)

Dopasowanie tego słowa ze zmiennej formalnej x... Widać, że ta korespondencja jest nie tylko jeden do jednego, ale także izomorficzna. Ponieważ „słowa” składają się z liter z pola, można je dodawać i mnożyć (element po elemencie), a wynik będzie w tym samym polu. Wielomian odpowiadający liniowej kombinacji pary słów i jest równy liniowej kombinacji wielomianów tych słów

To pozwala nam traktować zbiór słów o długości n nad ciałem skończonym jako liniową przestrzeń wielomianów o stopniu co najwyżej n-1 nad ciałem

Opis algebraiczny

Gdyby słowo kodowe uzyskany przez cykliczne przesuwanie jednego bitu w prawo od słowa, a następnie odpowiedniego wielomianu C 1 (x) otrzymujemy z poprzedniego mnożąc przez x:

Korzystając z faktu, że

Przesuń odpowiednio w prawo i w lewo o J cyfry:

Gdyby m(x) jest dowolnym wielomianem nad ciałem gF(Q) oraz C(x) jest słowem kodowym cyklicznego ( n,k) kod, to m(x)C(x)moD(x n − 1) jest również słowem kodowym tego kodu.

Generowanie wielomianu

Definicja Wielomian generujący cyklicznego ( n,k) kod C nazywa się takim niezerowym wielomianem z C, którego stopień jest najmniejszy, a współczynnik w najwyższym stopniu g r = 1 .

Twierdzenie 1

Gdyby C- cykliczny ( n,k) kod i g(x) jest wielomianem generującym, to stopień g(x) jest równe r = n − k a każde słowo kodowe może być jednoznacznie reprezentowane jako

C(x) = m(x)g(x) ,

gdzie stopień? m(x) jest mniejsze lub równe k − 1 .

Twierdzenie 2

g(x) jest wielomianem generującym cyklicznego ( n,k) kodu jest dzielnikiem dwumianu x n − 1

Konsekwencje: tak więc, jako wielomian generujący, możesz wybrać dowolny wielomian, dzielnik x n- 1. Stopień wybranego wielomianu określi liczbę symboli kontrolnych r, liczba symboli informacyjnych k = n − r .

Macierz generatywna

Wielomiany są liniowo niezależne, w przeciwnym razie m(x)g(x) = 0 o wartości niezerowej m(x), co jest niemożliwe.

Oznacza to, że słowa kodowe można zapisać, podobnie jak w przypadku kodów liniowych, w następujący sposób:

, gdzie g jest generowanie macierzy, m(x) - Informacja wielomian.

Macierz g można zapisać w formie symbolicznej:

Sprawdź macierz

Dla każdego słowa kodowego kodu cyklicznego jest prawdziwe. Dlatego sprawdź macierz można zapisać jako:

Kodowanie

Niesystematyczny

Przy kodowaniu niesystematycznym słowo kodowe uzyskuje się w postaci iloczynu wielomianu informacyjnego przez generowanie

C(x) = m(x)g(x) .

Można go zaimplementować za pomocą mnożników wielomianowych.

Systematyczny

Przy systematycznym kodowaniu słowo kodowe tworzy się w postaci podbloku informacyjnego i czeku

Niech więc słowo informacyjne tworzy najwyższe potęgi słowa kodowego, więc

C(x) = x r m(x) + s(x),r = n − k

Następnie z warunku wynika

To równanie wyznacza zasadę systematycznego kodowania. Można go wdrożyć za pomocą wielocyklowych filtrów liniowych (MLF)

Przykłady

Kod binarny (7,4,3)

jako dzielnik x 7 - 1 wybieramy wielomian generujący trzeciego stopnia g(x) = x 3 + x + 1 , to otrzymany kod będzie miał długość n= 7, liczba symboli kontrolnych (stopień wielomianu generującego) r= 3, liczba symboli informacyjnych k= 4, minimalna odległość D = 3 .

Macierz generatywna kod:

gdzie pierwsza linia reprezentuje notację wielomianową g(x) współczynniki w rosnącym stopniu. Pozostałe wiersze to cykliczne przesunięcia pierwszego wiersza.

Sprawdź macierz:

gdzie i-ta kolumna, zaczynając od zera, jest pozostałą częścią dzielenia x i przez wielomian g(x), pisane w rosnących stopniach, zaczynając od góry.

Tak więc, na przykład, otrzymuje się trzecią kolumnę lub w notacji wektorowej.

Łatwo to zauważyć gh T = 0 .

Kod binarny (15.7.5) BCH

Jako wielomian generujący g(x) możesz wybrać iloczyn dwóch dzielników x 15 − 1 ^

g(x) = g 1 (x)g 2 (x) = (x 4 + x + 1)(x 4 + x 3 + x 2 + x + 1) = x 8 + x 7 + x 6 + x 4 + 1 .

Następnie każde słowo kodowe można otrzymać za pomocą iloczynu wielomianu informacyjnego m(x) ze stopniem k- 1 w ten sposób:

C(x) = m(x)g(x) .

Na przykład słowo informacyjne odpowiada wielomianowi m(x) = x 6 + x 5 + x 4 + 1 , to słowo kodowe C(x) = (x 6 + x 5 + x 4 + 1)(x 8 + x 7 + x 6 + x 4 + 1) = x 14 + x 12 + x 9 + x 7 + x 5 + 1 , lub w formie wektorowej

Zobacz też

Spinki do mankietów

Fundacja Wikimedia. 2010.

Formy cykliczne w muzyce
Cykliczne warunki brzegowe

Zobacz, jakie „Kody cykliczne” znajdują się w innych słownikach:

skrócone kody cykliczne- - [L.G. Sumenko. Angielsko-rosyjski słownik technologii informacyjnej. M.: GP TsNIIS, 2003.] Tematy technologia informacyjna ogólnie EN skrócone kody cykliczne ...

Kody Reeda-Solomona- niebinarne kody cykliczne do korygowania błędów w blokach danych. Elementami wektora kodu nie są bity, ale grupy bitów (bloki). Kody Reeda Solomona, które działają z bajtami (oktetami), są bardzo powszechne. Kod Reeda Solomona to ... Wikipedia

Kody Golay- Rodzina doskonałych liniowych kodów blokowych z korekcją błędów. Najbardziej przydatny jest kod binarny Golay. Znany jest również trójskładnikowy kod Golaya. Kody Golaya można traktować jako kody cykliczne. ... ... Poradnik tłumacza technicznego

Kody korekcji błędów

Kody korekcji błędów- Wykrywanie błędów w technologii komunikacyjnej, działanie mające na celu monitorowanie integralności danych podczas nagrywania/odtwarzania informacji lub podczas ich przesyłania po liniach komunikacyjnych. Korekta błędów (korekta błędów) procedura przywracania informacji po ... ... Wikipedii

Jest to podklasa kodów liniowych, której właściwość polega na tym, że cykliczna permutacja symboli w zakodowanym bloku daje inny możliwy zakodowany blok tego samego kodu. Kody cykliczne opierają się na zastosowaniu idei z algebraicznej teorii pól Galois1.

Wiele z najważniejszych kodów przeciwzakłóceniowych systemów komunikacyjnych, -

w szczególności cykliczne, oparte na strukturach arytmetyki skończonej

Pola Galois. Przy polu nazywa się zbiorem elementów, które mają skończone ciało

nazwy operacji ujęto w cudzysłów, ponieważ nie zawsze są to ogólnie przyjęte operacje arytmetyczne. Pole zawsze zawiera element zero (0) lub zero i jeden element (1) lub jeden. Jeśli liczba Q elementy pola są ograniczone, wtedy pole nazywa się pole skończone, lub skończone pole Galois i oznaczony GF (q) y gdzie Q - kolejność polowa. Najmniejsze pole Galois to dwuelementowe iole GF ( 2), składający się tylko z dwóch elementów 1 i 0. Aby

1 Evariste Galois (1811 - 1832) - francuski matematyk, położył podwaliny pod współczesną algebrę.

wykonywanie operacji na elementach GF ( 2) nie doprowadziły do wyjścia poza to pole, są realizowane modulo 2 (na ogół określa to kolejność pola dla proste pola Galois).

Pole ma szereg określonych właściwości matematycznych. Dla elementów pola zdefiniowane są operacje dodawania i mnożenia, a wyniki tych operacji muszą należeć do tego samego zestawu.

W przypadku operacji dodawania i mnożenia przestrzegane są zwykłe zasady asocjacji matematycznej - a + (B + c) = (a + B)+ c, przemienność - a + b = b + a oraz a b = b a i dystrybucja - a (B+ s) = a b + a z.

Dla każdego elementu pola a musi istnieć odwrotne dodawanie (-a) i jeśli a niezerowy, odwrotny element mnożenia (th ').

Pole musi zawierać jednostka dodatku - element 0 taki, że a + 0 = a dla dowolnego elementu pola a.

Pole musi zawierać jednostka multiplikatywna - element 1 taki, że aL = a dla dowolnego elementu pola a.

Na przykład są pola liczby rzeczywiste, liczby wymierne, liczby zespolone. Pola te zawierają nieskończoną liczbę elementów.

W rzeczywistości wszystkie zestawy utworzone przez cykliczną permutację słowa kodowego są również słowami kodowymi. Na przykład cykliczne permutacje kombinacji 1000101 będą również kombinacjami kodów 0001011, 0010110, 0101100 itd. Ta właściwość umożliwia znaczne uproszczenie kodera i dekodera, zwłaszcza przy wykrywaniu błędów i korygowaniu pojedynczego błędu. Zwrócenie uwagi na kody cykliczne wynika z faktu, że ich nieodłączne wysokie właściwości korygujące są realizowane w oparciu o stosunkowo proste metody algebraiczne. Jednocześnie do dekodowania dowolnego liniowego kodu blokowego często stosuje się metody tabelaryczne, które wymagają dużej ilości pamięci dekodera.

Kod cykliczny nazywany jest blokiem liniowym (n, k) - kod, który jest cykliczny, tj. przesunięcie w lewo dowolnego dozwolonego słowa kodowego o jeden krok daje również dozwolone słowo kodowe należące do tego samego kodu, w którym zbiór słów kodowych jest reprezentowany przez zbiór wielomianów stopnia (NS- 1) lub mniej podzielne przez wielomian generujący g (x) stopień r = n-k y dwumianowy NS n +

W kodzie cyklicznym słowa kodowe są reprezentowane przez wielomiany (wielomiany)

gdzie NS - długość kodu; ja - Współczynniki pola Galois (wartości kombinacji norm).

Na przykład dla kombinacji kodów 101101 notacja wielomianowa ma postać

Przykładami kodów cyklicznych są kody parzyste, kody powtórzeń, kody Hamminga, kody PC i kody turbo.

Kod Hamminga... Możliwości korekcji błędów kodu Hamminga są związane z minimalną odległością kodowania d 0. Wszystkie błędy wielokrotności są naprawione Q= cnt (d 0- l) / 2 (tutaj cnt oznacza „część całkowitą”) i wykrywane są błędy wielokrotności d 0 - 1. Tak więc podczas sprawdzania dziwności d Q = 2 i wykryto pojedyncze błędy. W kodzie Hamminga d 0 = 3. Oprócz bitów informacyjnych, a L = log 2 Q nadmiarowych bitów kontrolnych, gdzie Q - liczba bitów informacyjnych. Parametr L zaokrąglona do najbliższej wyższej wartości całkowitej. L-bitowy kod sterujący jest odwróconym wynikiem bitowego dodawania (dodawania modulo 2) liczb tych bitów informacyjnych, których wartości są równe jeden.

Przykład 7.7

Załóżmy, że mamy kod główny 100110, czyli Q = 6. Zdefiniujmy dodatkowy kod.

Rozwiązanie

Znaleźliśmy to L= 3 i kod uzupełniający to

gdzie P jest symbolem operacji dodawania bitowego, a po odwróceniu mamy 000. Teraz zostanie przesłany kod dodatkowy z kodem głównym. W odbiorniku dodatkowy kod jest ponownie obliczany i porównywany z przesłanym. Kod porównania jest stały i jeśli jest różny od zera, to jego wartością jest numer błędnie odebranego bitu kodu głównego. Tak więc, jeśli otrzymany zostanie kod 100010, to obliczony kod dodatkowy jest równy inwersji 010SH10 = 100, tj. 011, co oznacza błąd w trzeciej cyfrze.

Uogólnieniem kodów Hamminga są cykliczne kody BCH, które umożliwiają korygowanie wielu błędów w odebranym słowie kodowym.

Reed - kody Salomona są oparte na polach Galois lub końcowych zerach. Operacje arytmetyczne to dodawanie, odejmowanie, mnożenie, dzielenie itp. nad elementami końcowego zera dają wynik, który jest również elementem tego zera. Te operacje musi wykonywać enkoder lub dekoder Reed-Solomon. Wszystkie operacje w celu wdrożenia kodu wymagają specjalny sprzęt lub specjalistyczne oprogramowanie.

Kody turbo. Kody nadmiarowe mogą być stosowane zarówno niezależnie, jak i w postaci pewnej kombinacji kilku kodów, gdy zbiory symboli jednego kodu nadmiarowego są uważane za elementarne symbole informacyjne innego kodu nadmiarowego. Taki związek zaczął się nazywać kaskadowe kod. Ogromną zaletą kodów łączonych jest to, że ich zastosowanie umożliwia uproszczenie kodera, a zwłaszcza dekodera, w porównaniu z podobnymi urządzeniami o kodach niesklejonych o tej samej długości i nadmiarowości. Połączone kodowanie doprowadziło do stworzenia kodów turbo. Turbokod nazywana jest równoległą strukturą sygnału składającą się z dwóch lub jeszcze kody systematyczne. Podstawową zasadą ich budowy jest wykorzystanie kilku koderów składowych pracujących równolegle. Jako kody składowe można stosować zarówno kody blokowe, jak i splotowe, kody Hamminga, kody PC, BCH itp. Zastosowanie perforacji (przebijania) pozwala zwiększyć względną prędkość kodu turbo, dostosowując jego zdolność korygowania do charakterystyk statystycznych kanał komunikacji. Zasada tworzenia kodu turbo jest następująca: sygnał wejściowy; NS, składający się z DO bit, podawany równolegle do n przekładki. Każdy z tych ostatnich to urządzenie, które permutuje elementy w bloku DO bity w kolejności pseudolosowej. Sygnał wyjściowy z przeplataczy - symbole o zmienionej kolejności - jest podawany do odpowiednich koderów elementarnych. Sekwencje binarne x p i= 1,2, ..., JV, na wyjściu kodera znajdują się symbole kontrolne, które razem z bitami informacyjnymi tworzą jedno słowo kodowe. Zastosowanie przeplotu umożliwia zapobieganie pojawianiu się sekwencji błędów skorelowanych podczas dekodowania turbokodów, co jest istotne w przypadku tradycyjnej w przetwarzaniu metody dekodowania rekurencyjnego. W zależności od wyboru kodu komponentu, kody turbo dzielą się na splotowe kody turbo i blokowe kody produktów.

Kody cykliczne są tak nazwane, ponieważ w nich część kombinacji kodów lub wszystkie kombinacje można uzyskać poprzez cykliczne przesuwanie jednej lub więcej kombinacji kodów. Przesunięcie cykliczne odbywa się od prawej do lewej, a znak skrajny lewy jest za każdym razem przenoszony na koniec kombinacji. Kody cykliczne praktycznie wszystkie odnoszą się do kodów systematycznych, w nich cyfry kontrolne i informacyjne znajdują się w ściśle określonych miejscach. Ponadto kody są klasyfikowane jako kody blokowe. Każdy blok (jedna litera to szczególny przypadek bloku) jest kodowany niezależnie.

Idea konstruowania kodów cyklicznych opiera się na wykorzystaniu wielomianów nieredukowalnych w zakresie liczb binarnych. Nieskracalny nazywa się wielomiany, które nie mogą być reprezentowane jako iloczyn wielomianów o niższych stopniach ze współczynnikami z tego samego pola, tak jak liczby pierwsze nie mogą być reprezentowane jako iloczyn innych liczb. Innymi słowy, wielomiany nieredukowalne są podzielne bez reszty tylko przez siebie lub przez jedność.

Wielomiany nierozkładalne w teorii kodów cyklicznych pełnią rolę generatorów wielomianów. Jeżeli dana kombinacja kodowa zostanie pomnożona przez wybrany wielomian nierozkładalny, to otrzymamy kod cykliczny, którego możliwości korekcyjne są określone przez wielomian nierozkładalny.

Załóżmy, że chcesz zakodować jedną z kombinacji czterech cyfr kod binarny... Załóżmy również, że ta kombinacja G (x) = x 3 + x 2 + 1 ® 1011. Nie uzasadniając naszego wyboru, bierzemy z tabeli wielomianów nierozkładalnych jako wielomian generujący P (x) = x 3 + x + 1 ® 1011. Następnie mnożymy G (x) przez jednomian w tym samym stopniu co wielomian generujący. Z pomnożenia wielomianu przez jednomian stopnia n stopień każdego wyrazu w wielomianu wzrośnie o n, co jest równoznaczne z przypisaniem n zera po stronie najmniej znaczących bitów wielomianu. Ponieważ stopień wybranego wielomianu nierozkładalnego jest równy trzy, oryginalna kombinacja informacji jest mnożona przez jednomian trzech stopni

G(x) x n =(x 3 + x 2 + 1) x 3 = x 6 + x 5 + x 3 = 1101000.

Dzieje się tak, aby później w miejsce tych zer można było wpisać cyfry korekcyjne.

Wartość cyfr korygujących znajduje się z wyników z dzielenia G(x) x n na P (x):

x 6 + x 5 + 0 + x 3 + 0 + 0 + 0 ½x 3 + x + 1

x 6 + 0 + x 4 + x 3

x 5 + x 4 + 0 + 0 x 3 + x 2 + x + 1 + x 5 + 0 + x 3 + x 2

x 4 + x 3 + x 2 +0

x 4 + 0 + x 2 + x

x 3 + 0 + x + 0

x 3 + 0 + x + 1

Zatem,

lub w ogólna perspektywa

gdzie P (x)¾ prywatny i R (x)¾ pozostała część dzielenia G (x) × x n na P(x).

Ponieważ w arytmetyce binarnej 1 Å 1 = 0, co oznacza -1 = 1, przy dodawaniu liczb binarnych można przenosić terminy z jednej części na drugą bez zmiany znaku (jeśli jest to wygodne), a zatem równość Formularz a Ł b = 0 można zapisać jako a = b, I jak a - b = 0. Wszystkie trzy równości w tym przypadku oznaczają, że albo a oraz b są równe 0, lub a oraz b są równe 1, tj. mają tę samą parzystość.

Zatem wyrażenie (5.1) można zapisać jako

F (x) = Q (x) P (x) = G (x) x n + R (x),

co w przypadku naszego przykładu da

F(x) =(x 3 + x 2 + x + 1) (x 3 + x + 1)= (x 3 + x 2 + 1)x 3 + 1,

F(x) = 1111 1011 = 1101000 + 001 = 1101001.

Wielomian 1101001 to pożądana kombinacja, gdzie 1101 to część informacyjna, a 001 to znaki kontrolne. Zauważ, że pożądaną kombinację otrzymalibyśmy zarówno w wyniku pomnożenia jednej z kombinacji pełnego czterocyfrowego kodu binarnego (w tym przypadku 1111) przez wielomian generujący, jak i pomnożenia danej kombinacji przez jednomian o tym samym stopniu jako wybrany wielomian generujący (w naszym przypadku uzyskano w ten sposób kombinację 1101000) z późniejszym dodawaniem do otrzymanego produktu reszty z dzielenia tego produktu przez wielomian generujący (w naszym przykładzie reszta ma postać 001 ).

I tutaj decydującą rolę odgrywają własności wielomianu generującego P (x)... Sposób konstruowania kodu cyklicznego polega na tym, że wielomian generujący bierze udział w tworzeniu każdej kombinacji kodów, dlatego każdy wielomian kodu cyklicznego jest dzielony przez generator bez reszty. Ale tylko te wielomiany, które należą do danego kodu, są podzielne bez reszty, czyli wielomian generujący pozwala wybrać dozwolone kombinacje ze wszystkich możliwych. Jeżeli przy dzieleniu kodu cyklicznego przez wielomian generujący otrzymamy resztę, to albo wystąpił błąd w kodzie, albo jest to kombinacja jakiegoś innego kodu (kombinacja zabroniona). W pozostałych przypadkach wykrywana jest obecność zabronionej kombinacji, to znaczy wykrywany jest błąd. Pozostała część podziału wielomianów to aparaty rozpoznawania błędów kodów cyklicznych.

Z drugiej strony, pozostałe z dzielenia jedynki przez zera przez wielomian generujący są wykorzystywane do konstruowania kodów cyklicznych.

Dzieląc jedynkę z zerami przez wielomian generujący, należy pamiętać, że długość reszty nie może być mniejsza niż liczba cyfr kontrolnych, dlatego w przypadku braku cyfr w reszcie potrzebna jest liczba zer przypisane na prawo od reszty.

01100 11111+

począwszy od ósmego, pozostałe zostaną powtórzone.

Pozostałe z dzielenia służą do konstruowania macierzy generujących, które ze względu na swoją klarowność i wygodę w uzyskiwaniu kombinacji pochodnych są szeroko stosowane do konstruowania kodów cyklicznych. Konstrukcja macierzy generującej sprowadza się do zestawienia przeniesionej jednostki i macierzy dodatkowej, której elementami są pozostałości z dzielenia jedynki przez zera przez wielomian generujący P (x)... Przypomnijmy, że transponowana macierz jednostkowa jest macierzą kwadratową, której wszystkie elementy są zerami, z wyjątkiem elementów położonych po przekątnej od prawej do lewej od góry do dołu (w macierzy nietransponowanej przekątna z elementami identycznymi jest od lewej do prawej od góry do dołu). Elementy dodatkowej macierzy są przyporządkowane na prawo od transponowanej macierzy tożsamości. Tylko te pozostałości, których waga wynosi W³d 0- 1, gdzie d 0 To minimalna odległość kodu. Długość reszt musi być co najmniej liczbą bitów kontrolnych, a liczba reszt musi być równa liczbie bitów informacyjnych.

Wiersze macierzy generującej są pierwszymi kombinacjami kod źródłowy... Pozostałe kombinacje kodu uzyskuje się przez zsumowanie modulo 2 wszystkich możliwych kombinacji wierszy macierzy generującej.

Przykład.

Skonstruuj kompletną macierz generowania kodu cyklicznego, która wykrywa wszystkie pojedyncze i podwójne błędy podczas przesyłania 10-bitowych kombinacji binarnych.

Rozwiązanie.

Zgodnie z tabelą 5.12 wybierz najbliższą wartość k³ 10.

Tabela 5.12 - Zależności między znakami informacyjnymi i kontrolnymi dla kodu o długości do 16 bitów

n	k	ρ	n	k	ρ

Zgodnie z tabelą ta wartość będzie k = 11, podczas gdy r = 4, a

n = 15. Wybieramy również wielomian generatora x 4 + x 3 +1.

Kompletna macierz generująca jest zbudowana z macierzy transpozycji jednostek w postaci kanonicznej oraz dodatkowej macierzy odpowiadającej cyfrom kontrolnym.

Transpozycja macierzy dla k = 11 wygląda tak:

Dodatkowa macierz może być skonstruowana z pozostałej części dzielenia kombinacji w postaci jedynki i zer (ostatni wiersz transponowanej macierzy identyczności) przez wybrany wielomian generujący.

Pełna macierz generatora będzie wyglądać tak:

Powyższa metoda konstruowania macierzy generowania nie jest jedyną. Macierz generująca może być zbudowana w wyniku bezpośredniego przemnożenia elementów macierzy jednostkowej przez wielomian generujący. Często jest to wygodniejsze niż znalezienie pozostałej części dywizji. Otrzymane kody nie różnią się w żaden sposób od kodów zbudowanych z macierzy generujących, w których dodatkowa macierz składa się z pozostałości z dzielenia jedynki przez zera przez wielomian generujący.

Macierz generująca może być skonstruowana w ten sam sposób poprzez cykliczne przesunięcie kombinacji otrzymanej w wyniku pomnożenia rzędu macierzy jednostkowej rangi k na wielomianu generującym.

Błędy w kodach cyklicznych są wykrywane przy użyciu pozostałości z dzielenia wynikowej kombinacji przez wielomian generujący. Pozostała część podziału to identyfikatory błędów, ale nie wskazują bezpośrednio lokalizacji błędu w kodzie cyklicznym.

Idea korekcji błędów polega na tym, że błędna kombinacja po określonej liczbie przesunięć cyklicznych jest „dopasowywana” do reszty w taki sposób, że wraz z resztą daje poprawione słowo kodowe. W tym przypadku reszta jest niczym innym jak różnicą między symbolami zniekształconymi i poprawnymi, jednostki w reszcie stoją dokładnie w miejscach bitów zniekształconych w kombinacji regulowanej przez przesunięcia cykliczne. Zniekształcona kombinacja jest korygowana, aż liczba jedynek w reszcie będzie równa liczbie błędów w kodzie. W tym przypadku oczywiście liczba jedynek może być równa liczbie błędów s, poprawiony tym kodem (kod koryguje 3 błędy i 3 błędy w zniekształconej kombinacji) lub mniej s(kod koryguje 3 błędy, aw przyjętej kombinacji 1 błąd).

Lokalizacja błędu w kombinacji kodowej nie ma znaczenia. Gdyby k³ (n / 2), to po określonej liczbie przesunięć wszystkie błędy znajdą się w strefie „jednorazowego” działania wielomianu generującego, czyli wystarczy uzyskać jedną resztę, której waga wynosi W £ s, a to już wystarczy, aby skorygować zniekształconą kombinację.

Proces korekcji błędów został szczegółowo omówiony poniżej na przykładach budowania konkretnych kodów.