Na zestawie binarnych słów o długości m odległość d(a,b) między słowami aib to liczba niepasujących pozycji tych słów, np.: odległość między słowami a = 01101 i b = 00111 wynosi 2.

Tak zdefiniowane pojęcie nazywa się odległością Hamminga.

Spełnia następujące aksjomaty odległości:

1) d(a,b)  0 i d(a,b)=0 wtedy i tylko wtedy, gdy a = b;

2) d(a,b) = d(b,a) ;

3) d(a,b) + d(b,c)  d(a,c) (nierówność trójkąta).

Waga w(a) słowa a to liczba jedynek wśród jego współrzędnych. Wtedy odległość między słowami a i b jest wagą ich sumy a b: d(a,b)=w(a b) , gdzie symbol  oznacza operację dodawania współrzędnych modulo 2. Intuicyjnie im bardziej różnią się słowa kodowe, tym lepiej nadaje się on do wykrywania i korygowania błędów. Koncepcja odległości Hamminga pozwala nam to wyjaśnić.

Twierdzenie Aby kod wykrywał błędy w k (lub mniejszej) pozycji, konieczne i wystarczające jest, aby najmniejsza odległość między słowami kodowymi wynosiła  k + 1.

Dowód tego twierdzenia jest podobny do dowodu poniższego twierdzenia.

Twierdzenie. Aby kod poprawił wszystkie błędy na k (lub mniej) pozycjach, konieczne i wystarczające jest, aby najmniejsza odległość między słowami kodowymi wynosiła  2k + 1.

32. Twierdzenie o zdolności korygującej kodów.

Kody, które mogą automatycznie korygować błędy, nazywane są samokorygującymi. Aby zbudować kod samokorygujący przeznaczony do korygowania pojedynczych błędów, jedna cyfra kontrolna nie wystarczy. Jak widać, liczbę bitów kontrolnych k należy tak dobrać, aby spełniona była nierówność 2k≥k+m+1or k≥log2(k+m+1), gdzie m jest liczbą podstawowych bitów binarnych słowa kodowego. Obecnie największym zainteresowaniem cieszą się kody korekcji bloków binarnych. Przy zastosowaniu takich kodów informacja przesyłana jest w postaci bloków o tej samej długości, a każdy blok jest kodowany i dekodowany niezależnie od siebie. W prawie wszystkich kodach blokowych znaki można podzielić na informacyjne i weryfikacyjne.

Główne cechy kodów samokorygujących to:

1. Liczba dozwolonych i zabronionych kombinacji. Jeżeli n jest liczbą symboli w bloku, r jest liczbą symboli kontrolnych w bloku, k jest liczbą symboli informacyjnych, to 2n jest liczbą możliwych kombinacji kodowych, 2k jest liczbą dozwolonych kombinacji kodowych, 2n −2k to liczba zabronionych kombinacji.

2. Redundancja kodu. Wartość rn nazywana jest redundancją kodu korekcyjnego.

3. Minimalna odległość kodu. Minimalna odległość kodu d to minimalna liczba zniekształconych symboli wymaganych do przejścia z jednej dozwolonej kombinacji do drugiej.

4. Liczba wykrytych i poprawionych błędów. Jeżeli g jest liczbą błędów, które kod może poprawić, to konieczne i wystarczające jest, aby d≥2g+1

5. Możliwości korekcyjne kodów.

33. Kodowanie macierzowe. Kody grupowe.

Kiedy jawnie określasz schemat kodowania w ( kod m, n) powinien określać 2 m słów kodowych, co jest bardzo nieefektywne.

Jednym z ekonomicznych sposobów opisania schematu kodowania jest technika kodowania macierzowego.

Poprzednio każdy schemat kodowania był opisywany za pomocą tabel określających długość słowa kodowego N dla każdego słowa źródłowego o długości M. Do bloków długa długość metoda ta wymaga dużej ilości pamięci i dlatego jest niepraktyczna. Na przykład dla ( 16, 33 ) kod będzie wymagał 33 * 2 16 = 2 162 688 bitów.

Wymaga znacznie mniej pamięci kodowanie matrycowe. Pozwalać mi macierz wymiarów m×n, składający się z elementów e ij , gdzie I jest numerem linii, oraz J - numer kolumny. Każdy z elementów macierzy mi ja może wynosić 0 lub 1. Kodowanie jest realizowane przez operację b = aE czy gdzie słowa kodowe są traktowane jako wektory, tj. jako rzędowe macierze wielkości 1×n.

Kodowanie nie powinno przypisywać tego samego słowa kodowego do różnych komunikatów źródłowych. Prostym sposobem na osiągnięcie tego jest M kolumny macierzy utworzył macierz jednostkową. Gdy dowolny wektor zostanie pomnożony przez macierz tożsamości, otrzymamy ten sam wektor, dlatego różnym wektorom kodu systematycznego będą odpowiadać różne wektory wiadomości.

Kody matrycowe są również nazywane kody liniowe. Dla liniowego (n - r, rz) - kody z minimalną odległością Hamminga D istnieje Dolna granica Plotkina (Plotkin) dla minimalnej liczby bitów kontrolnych R Na n³ 2d - 1,

Binarny ( Kod m, n) nazywany jest kodem grupowym, jeśli jego słowa kodowe tworzą grupę.

Należy zauważyć, że zbiór wszystkich słów binarnych o długości m tworzy grupę przemienną z operacją dodawania współrzędnych modulo 2, w której zachodzi relacja a a. W konsekwencji zbiór słów komunikatu a o długości m jest grupą przemienną.

Nazywa się kod blokowy Grupa, jeśli jego słowa kodowe tworzą grupę.

Jeżeli kod jest kodem grupowym, wówczas najmniejsza odległość pomiędzy dwoma słowami kodowymi jest równa najmniejszej wadze niezerowego słowa.

To wynika z zależności d(ur I , B J ) = w(b I + B J ).

Podczas używania kodu wieloznacznego te i tylko te błędy, które odpowiadają ciągom błędów dokładnie równym słowom kodowym, pozostają niewykryte.

Takie linie błędów tłumaczą jedno słowo kodowe na drugie.

Dlatego prawdopodobieństwo, że błąd pozostanie niewykryty, jest równe sumie prawdopodobieństw wszystkich ciągów błędów równych słowom kodowym.

Zestaw wszystkich słów binarnych a = a 1 ... A M długość M tworzy grupę abelową (przemienną) w odniesieniu do dodawania bitowego.

Pozwalać mi - kodowanie m×n-macierz, która ma M × M- podmacierz z niezerowym wyznacznikiem, na przykład tożsamością. Potem mapowanie a → a E tłumaczy grupę wszystkich słów binarnych o długości M do grupy słów kodowych o długości N.

Załóżmy, że Wtedy dostajemy

tj. Dlatego mapowanie jeden do jednego grupy słów binarnych o długości M przy użyciu danej matrycy mi zachowuje właściwości operacji grupowej, co oznacza, że ​​słowa kodowe tworzą grupę.

Właściwość kodu grupowego: minimalna odległość kodu między wektorami kodu jest równa minimalnej wadze niezerowych wektorów. Waga wektora kodu jest równa liczbie jedynek w kombinacji kodu.

Wygodnie jest określić kody grupowe za pomocą macierzy, których wymiar określają parametry k i n. Liczba wierszy wynosi k, a liczba kolumn wynosi n = k+m.

Kody generowane przez te macierze nazywane są kodami (n, k), a odpowiadające im macierze nazywane są generatorami (generatorami).

W tym artykule porozmawiamy na temat algorytmu HEngine i implementacji rozwiązania problemu obliczania odległości Hamminga na dużych ilościach danych.

Wstęp

Odległość Hamminga to liczba różnych położeń strun o tej samej długości. Na przykład HD(100, 001) = 2.

Problem obliczenia odległości Hamminga po raz pierwszy postawili Minsky i Papert w 1969 roku, gdy problemem było znalezienie wszystkich wierszy w bazie danych, które znajdują się w danej odległości Hamminga od odległości zapytania.

Takie zadanie jest niezwykle proste, ale znalezienie go skuteczne rozwiązanie jest nadal w porządku obrad.

Odległość Hamminga jest już dość powszechnie stosowana różne zadania, takie jak wyszukiwanie bliskich duplikatów, rozpoznawanie wzorców, klasyfikacja dokumentów, korekcja błędów, wykrywanie wirusów itp.

Na przykład Manku i współpracownicy zaproponowali rozwiązanie problemu grupowania duplikatów w indeksowaniu dokumentów internetowych w oparciu o obliczanie odległości Hamminga.
Miller i przyjaciele zaproponowali także koncepcję wyszukiwania utworów na podstawie danego fragmentu audio.
Podobne rozwiązania zastosowano w problematyce odzyskiwania obrazu, rozpoznawania siatkówki itp.

opis problemu

Jest baza danych ciągi binarne T, rozmiar N, gdzie długość każdej linii M. Żądany ciąg A i wymaganą odległość Hamminga k.

Zadanie sprowadza się do odnalezienia wszystkich sznurków znajdujących się w odległości k.

Oryginalna koncepcja algorytmu uwzględnia dwa warianty problemu: statyczny i dynamiczny.

W problemie statycznym odległość k jest z góry określona.
- W przypadku dynamiki natomiast wymagana odległość nie jest z góry znana.

W artykule opisano rozwiązanie jedynie problemu statycznego.

Opis algorytmu HEngine dla zadania statycznego

Ta implementacja koncentruje się na wyszukiwaniu ciągów znaków k <= 10.

Istnieją trzy rozwiązania problemu statycznego: skanowanie liniowe, rozszerzanie zapytań i rozwijanie tabeli.

W tym przypadku pod rozszerzenie zapytania Odnosi się to do generowania wszystkich możliwych wariantów ciągu, które mieszczą się w danej odległości dla oryginalnego ciągu.
Rozbudowa bazy dane implikują utworzenie wielu kopii tej bazy danych, gdzie albo generowane są również wszystkie możliwe opcje spełniające wymagania wymaganej odległości, albo dane są przetwarzane w inny sposób (więcej o tym nieco później.).

HEngine wykorzystuje kombinację tych trzech technik, aby skutecznie zrównoważyć pamięć i czas wykonania.

Trochę teorii

Algorytm opiera się na małym twierdzeniu, które stwierdza, co następuje:

Jeśli dla dwóch linii A I B odległośćHD( A, B) <= k, to jeśli podzielimy linie A I B na podciągi przy użyciu metody przeciąć za pomocą współczynnik segmentacji
R >= ⌊k/2⌋ + 1
na pewno będzie przynajmniej Q= R − ⌊k/2⌋ podciągi, gdy ich odległość nie przekracza jedności, HD( A I, B I)<= 1.

Wyodrębnianie podciągów z ciągu podstawowego przy użyciu metody przeciąć odbywa się według następujących zasad:
Nazwana wartość współczynnik segmentacji, co spełnia warunek
R >= ⌊k/2⌋ + 1

Pierwsza długość R − (M mod R) podciąg będzie miał długość ⌊ M / R⌋ i ostatnie M mod R podciągi ⌈ M/R⌉. Gdzie M jest długością sznurka, ⌊ zaokrągla się do najbliższego dołu, a ⌉ zaokrągla do najbliższej góry.

Teraz to samo, tylko z przykładem:

Biorąc pod uwagę dwa ciągi binarne o długości M= 8 bitów: A = 11110000 i B = 11010001, odległość między nimi k = 2.
Wybór współczynnika segmentacji R= 2/2 + 1 = 2, tj. w sumie będą miały długość 2 podciągów M/R= 4 bity.

a1 = 1111, a2 = 0000
b1 = 1101, b2 = 0001

Jeśli teraz obliczymy odległość między odpowiednimi podciągami, to przynajmniej Q= 2 - 2/2 = 1, jeden podciąg będzie pasował lub ich odległość nie będzie większa niż jeden.

Co widzimy:
HD(a1, b1) = HD(1111, 1101) = 1
I
HD(a2, b2) = HD(0000, 0001) = 1

Podciągi łańcucha bazowego zostały nazwane podpisy.
Podpisy lub podciągi a1 i b1 (a2 i b2, a3 i b3 ..., a R oraz b R) są nazywane zgodny ze sobą, a jeśli ich liczba różnych bitów jest nie większa niż jeden, wówczas wywoływane są te podpisy dopasowanie.

A główną ideą algorytmu HEngine jest takie przygotowanie bazy danych, aby znaleźć pasujące sygnatury, a następnie wybrać te wiersze, które mieszczą się w wymaganej odległości Hamminga.

Wstępne przetwarzanie bazy danych

Wiemy już, że jeśli poprawnie podzielimy ciąg na podciągi, to przynajmniej jeden podciąg będzie pasował do odpowiedniego podciągu lub liczba różnych bitów nie będzie większa niż jeden (sygnatury będą się zgadzać).

Oznacza to, że nie musimy przeprowadzać pełnego przeszukiwania wszystkich wierszy z bazy, ale najpierw znaleźć te podpisy, które pasują, tj. podciągi będą się różnić maksymalnie o jeden.

Ale jak wyszukiwać według podciągów?

Metoda wyszukiwania binarnego powinna sobie z tym poradzić. Wymaga to jednak posortowania listy ciągów. Ale z jednej linii otrzymujemy kilka podciągów. Aby przeprowadzić wyszukiwanie binarne na liście podciągów, każda taka lista musi zostać wcześniej posortowana.
Sugeruje to zatem metodę rozbudowy bazy danych, tj. utworzenie kilku tabel, każda dla własnego podciągu lub podpisu. (Ta tabela nazywa się tabela podpisów. A kolekcja takich tabel jest zestaw podpisów).

Oryginalna wersja algorytmu opisuje również przestawianie podciągów tak, aby wybrane podciągi znajdowały się na pierwszym miejscu. Odbywa się to bardziej dla ułatwienia implementacji i dalszej optymalizacji algorytmu:

Istnieje ciąg A, który jest podzielony na 3 podciągi, a1, a2, a3, pełna lista permutacji będzie odpowiednio:
a1, a2, a3
a2, a1, a3
a3, a1, a2

Te tabele podpisów są następnie sortowane.

Implementacja wyszukiwania

Na tym etapie, po wstępnym przetworzeniu bazy danych, mamy kilka kopii posortowanych tabel, każda dla własnego podwiersza.

Oczywiście, jeśli chcemy najpierw znaleźć podciągi, musimy uzyskać podpisy z żądanego ciągu w taki sam sposób, jak został użyty do utworzenia tablic sygnatur.

Wiemy również, że wymagane podciągi różnią się co najwyżej jednym elementem. Aby je znaleźć, będziesz musiał skorzystać z metody rozszerzania zapytania.

Innymi słowy dla wybranego podciągu należy wygenerować wszystkie kombinacje łącznie z samym podciągiem, w których różnica będzie wynosić co najwyżej jeden element. Liczba takich kombinacji będzie równa długości podciągu + 1.

Takie działania należy wykonać dla wszystkich podwierszy i wszystkich tabel.

Na samym końcu będziesz musiał odfiltrować te linie, które nie mieszczą się w określonym limicie odległości Hamminga. Te. wykonaj przeszukiwanie liniowe znalezionych ciągów i pozostaw tylko te ciągi, które spełniają warunek HD( A, B) <= k.

Filtr Blooma

Jeśli przed binarnym wyszukiwaniem podciągu w tabeli filtr zwróci informację, że podciągu nie ma w tej tabeli, to nie ma sensu przeprowadzać wyszukiwania.

W związku z tym należy utworzyć jeden filtr dla każdej tabeli podpisów.

Autorzy zauważają również, że zastosowanie w ten sposób filtra Blooma skraca czas przetwarzania zapytań średnio o 57,8%. Na moich testowych egzemplarzach taki filtr nie ma praktycznie żadnego wpływu na uzyskany czas pracy. Znaczące tylko w przypadku losowo wygenerowanej bazy danych.

Teraz to samo, tylko z przykładem

Istnieje baza danych ciągów binarnych o długości 8 bitów:
11111111
10000001
00111110

Zadanie polega na odnalezieniu wszystkich linii, w których liczba różnych bitów nie przekracza 2, do linii docelowej 10111111.

Czyli wymagana odległość k = 2.

1. Wybierz współczynnik segmentacji.

Na podstawie wzoru wybieramy współczynnik segmentacji R= 2, co oznacza, że ​​w jednej linii będą tylko dwa podciągi.

2. Utwórz zestaw podpisów.

Ponieważ liczba podciągów wynosi 2, należy utworzyć tylko 2 tabele:

3. Podciągi zapisujemy w odpowiednich tabelach zachowując powiązanie z oryginalnym źródłem.

T1 T2
1111 1111 => 11111111
1000 0001 => 10000001
0011 1110 => 00111110

4. Posortuj tabele. Każdy osobno.

T1
0011 => 00111110
1000 => 10000001
1111 => 11111111

T2
0001 => 10000001
1110 => 00111110
1111=> 11111111

Na tym kończy się obróbka wstępna. I zacznijmy poszukiwania.

5. Otrzymujemy podpisy żądanego ciągu.

Szukany ciąg 10111110 jest podzielony na sygnatury. Okazuje się, że odpowiednio 1011 i 1100, pierwszy dla pierwszego stołu, a drugi dla drugiego.

6. Wygeneruj wszystkie kombinacje różniące się o jeden.
Liczba opcji będzie wynosić 5.

6.1 Dla pierwszego podciągu 1011:
1011
0 011
11 11
100 1
1010

6.2 Dla drugiego podciągu 1100:
1100
0 100
10 00
111 0
1101

7. Wyszukiwanie binarne.

7.1 Dla wszystkich wygenerowanych wariantów pierwszego podciągu 1011 przeprowadzamy wyszukiwanie binarne w pierwszej tabeli w celu uzyskania pełnego dopasowania.

1011
0011 == 0011 => 00111110
1111 == 1111 => 11111111
1001
1010

Znaleziono dwa podciągi.

7.2 Teraz dla wszystkich wariantów drugiego podciągu 1100 przeprowadzamy wyszukiwanie binarne w drugiej tabeli.

1100
0100
1000
1110 == 1110 => 00111110
1101

Znaleziono jeden podciąg.

8. Łączenie wyników w jedną listę:
00111110
11111111

9. Liniowo sprawdź zgodność i odfiltruj te, które nie spełniają warunku<= 2:

HD(10111110, 00111110) = 1
HD(10111110, 11111111) = 2

Obydwa ciągi spełniają warunek, że różnią się nie więcej niż dwa elementy.

Chociaż na tym etapie przeprowadzane jest wyszukiwanie liniowe, oczekuje się, że lista ciągów kandydujących nie będzie wcale duża.
W warunkach, w których liczba kandydatów jest duża, proponuje się użycie rekursywnej wersji HEngine.

Wyraźnie

Rysunek 1 pokazuje przykład działania algorytmu wyszukiwania.
Dla długości linii wynoszącej 64 i limitu odległości wynoszącego 4 współczynnik segmentacji wynosi 3, co odpowiada tylko 3 podciągom w linii.
Gdzie T1, T2 i T3 to tablice sygnatur zawierające tylko podciągi B1, B2, B3.

Żądany ciąg jest podzielony na podciągi. Następnie generowany jest zakres podpisów dla odpowiednich podciągów. Na koniec przeprowadzane jest wyszukiwanie binarne.

Rys. 1. Uproszczona wersja przetwarzania zapytań do tablic sygnatur.

wyniki

Złożoność średnioprzypadkowa takiego algorytmu O(M(dziennik N+ 1)), gdzie N to całkowita liczba wierszy w bazie danych, M to liczba wyszukiwań binarnych, a log N+ 1 wyszukiwanie binarne.
W skrajnych przypadkach może przekraczać liniowość. Na przykład pod warunkiem Q= 1 i gdy wszystkie wiersze ze wszystkich tabel podpisów, z wyjątkiem ostatniej, pasują do żądanego, to się okazuje O((R - 1)MN(dziennik N + 1)).

Należy zauważyć, że to podejście zużywa 4,65 mniej pamięci i jest o 16% szybsze niż poprzednia praca opisana w .

Realizacja

Wszystko to z pewnością kusi, ale dopóki się tego nie dotknie, trudno ocenić skalę.
Stworzono prototyp HEngine i przetestowano go na dostępnych rzeczywistych danych.

Tests$ ./matches 7 data/db/table.txt data/query/face2.txt Odczyt zbioru danych ...... zakończone. 752420 skrótów db i 343 skrótów zapytań. Budynek z 7 odległościami Hamminga....... zrobione. Czas tworzenia: 12,964 sekundy Wyszukiwanie dopasowań HEngine ....... znaleziono łącznie 100 dopasowań. Czas zapytania silnika: 0,228 sekundy. Wyszukiwanie dopasowań liniowych....... znaleziono łącznie 100 dopasowań. Liniowy czas zapytania: 6,828 sekundy

Wyniki były zachęcające, ponieważ wyszukiwanie 343 skrótów z bazy danych 752420 zajmuje ~0,2 sekundy, czyli 30 razy szybciej niż wyszukiwanie liniowe.

Wydawałoby się, że na tym moglibyśmy się zatrzymać. Ale naprawdę chciałem spróbować to jakoś wykorzystać w prawdziwym projekcie.

Jedno kliknięcie przed prawdziwą aplikacją

Istnieje baza danych skrótów obrazów i backend w PHP.
Zadanie polegało na powiązaniu w jakiś sposób funkcjonalności HEngine i PHP.
Zdecydowano się użyć FastCGI, posty habrahabr.ru/post/154187/ i habrahabr.ru/post/61532/ bardzo mi w tym pomogły.

Z PHP po prostu zadzwoń:

$list = file_get_contents("http://fcgi.local/?" .$hashes);

Co za około 0,5 sekundy zwraca wynik. Gdy wyszukiwanie liniowe wymaga 9 sekund, a zapytania do MySQL co najmniej 20 sekund.

Dziękuję wszystkim, którzy go ukończyli.

) w przestrzeni wektorowej ciągów kodu, w tym przypadku odległość Hamminga pomiędzy dwoma ciągami binarnymi (wektorami) a długość to liczba pozycji, w których są one różne - w tym sformułowaniu odległość Hamminga zawarta jest w Słowniku Algorytmów i Struktury danych Narodowego Instytutu Standardów Stanów Zjednoczonych (eng. Słownik algorytmów i struktur danych NIST ).

Zatem odległość Hamminga pomiędzy wektorami 0 011 1 i 1 010 1 wynosi 2 (różne bity zaznaczono na czerwono). Następnie metrykę uogólniono na ciągi q-ary: dla pary ciągów „wybór” i „ogrodzenie” odległość Hamminga jest równa trzy.

Ogólnie rzecz biorąc, odległość Hamminga dla obiektów i wymiarów jest określona funkcją:

Odległość Hamminga ma właściwości metryki, spełniając następujące warunki:

Dystans Hamminga w bioinformatyce i genomice

Literatura

• Richarda W. Hamminga. Kody wykrywania i korygowania błędów, Bell System Technical Journal 29 (2): 147-160, 1950.
• Ryszarda Bleichuta. Teoria i praktyka kodów kontroli błędów. M., „Mir”, 1986

Spinki do mankietów

• Richard Hamming i początki teorii kodowania // Wirtualne Muzeum Komputerów

Fundacja Wikimedia. 2010.

Zobacz, co oznacza „odległość Hamminga” w innych słownikach:

Odległość Hamminga- Odległość Hamminga Odległość d (u, v) pomiędzy dwoma ciągami kodowymi u i v o tej samej długości, równa liczbie symboli, którymi się różnią. Kod blokowy z minimalną odległością Hamminga d pozwala wykryć (d 1) i... ...

odległość kodu- Minimalna odległość Hamminga przejęta przez wszystkie lary różnych słów kodowych w jednolitym kodzie. [Zbiór zalecanych terminów. Zeszyt 94. Teoria przekazywania informacji. Akademia Nauk ZSRR. Komitet Terminologii Technicznej. 1979] Teoria tematów... ... Przewodnik tłumacza technicznego

W dziedzinie matematyki i teorii informacji kod liniowy jest ważnym typem kodu blokowego stosowanym w schematach wykrywania i korygowania błędów. Kody liniowe, w porównaniu do innych kodów, pozwalają na realizację wydajniejszych algorytmów... ...Wikipedia

W dziedzinie matematyki i teorii informacji kod liniowy jest ważnym typem kodu blokowego stosowanym w schematach wykrywania i korygowania błędów. Kody liniowe, w porównaniu do innych kodów, pozwalają na realizację wydajniejszych algorytmów... ...Wikipedia

Wykrywanie błędów w technologii komunikacyjnej to działanie mające na celu monitorowanie integralności danych podczas zapisywania/odtwarzania informacji lub przesyłania ich liniami komunikacyjnymi. Procedura odzyskiwania korekcji błędów (korekty błędów)... ... Wikipedia

Wykrywanie błędów w technologii komunikacyjnej to działanie mające na celu monitorowanie integralności danych podczas zapisywania/odtwarzania informacji lub przesyłania ich liniami komunikacyjnymi. Procedura korekcji błędów (korekty błędów) służąca do przywracania informacji po... ...Wikipedii

Wykrywanie błędów w technologii komunikacyjnej to działanie mające na celu monitorowanie integralności danych podczas zapisywania/odtwarzania informacji lub przesyłania ich liniami komunikacyjnymi. Procedura korekcji błędów (korekty błędów) służąca do przywracania informacji po... ...Wikipedii

Wykrywanie błędów w technologii komunikacyjnej to działanie mające na celu monitorowanie integralności danych podczas zapisywania/odtwarzania informacji lub przesyłania ich liniami komunikacyjnymi. Procedura korekcji błędów (korekty błędów) służąca do przywracania informacji po... ...Wikipedii

Odległość Hamminga

Amerykański matematyk Hamming badał, od czego zależy ten kod, czy wykryje błędy i kiedy będzie mógł je poprawić. Intuicyjnie widać, że zależy to od tego, w jaki sposób słowa kodowe są od siebie oddzielone i ile błędów może pojawić się w przesyłanym słowie. Sformalizujemy teraz następujący pomysł. Podczas kodowania konieczne jest skoordynowanie liczby możliwych błędów w przesyłanym słowie kodowym, tak aby po zmianie przesyłanego słowa kodowego pozostawało ono bliższe oryginalnemu słowu kodowemu niż jakiemukolwiek innemu słowu kodowemu.

Definicja 13.1. Rozważmy zbiór wszystkich słów binarnych w alfabecie W= (0,1) długość T dystans D(X, Na), która jest równa liczbie niepasujących pozycji tych słów. Na przykład: Dla słów X = 011101, Na= 101010 odległość wynosi D(X, y) = 5. Odległość ta nazywa się Odległość Hamminga .

Można wykazać, że odległość Hamminga spełnia aksjomaty przestrzeni metrycznej:

1) D(X, Na) ≥ 0, D(X, Na) = 0 wtedy i tylko wtedy, gdy X = y;

2) D(X, y) = D(y, X);

3) D(X, Na) ≤ D(X, z) + re(z, Na) - nierówność trójkąta.

Twierdzenie 13.1(o kodzie wykrywającym). Kod wykrywa w przypadku, gdy przesyłane słowo zawiera nie więcej niż k

D(B 1, B 2) ≥ k+ 1.

Twierdzenie 13.2(o kodzie korekcyjnym.). Kod koryguje wszystkie błędy w przypadku, gdy przesyłane słowo zawiera nie więcej niż k błędów, wtedy i tylko wtedy, gdy najmniejsza odległość między słowami kodowymi

D(B 1, B 2) ≥ 2k+ 1.

Dowód. Dowody tych twierdzeń są podobne. Dlatego udowodnimy tylko ostatnie twierdzenie.

Adekwatność. Niech to będą dowolne słowa kodowe, jakie mamy D(B 1, B 2) ≥ 2k+ 1. Jeżeli podczas przesyłania słowa kodowego B 1 nic więcej się nie wydarzyło k błędy, a następnie zaakceptowane słowo z mamy D(B 1, C) ≤ k. Ale z nierówności trójkąta dla dowolnego innego słowa kodowego B 2 mamy D(B 1, Z) + D(C, B 2) ≥ D(B 1, B 2) ≥ 2 k+ 1. Zatem odległość od otrzymanego słowa do dowolnego innego słowa kodowego wynosi D(C, B 2) ≥ k + 1, czyli więcej niż dotychczas B 1. Dlatego zgodnie z przyjętym słowem Z z pewnością znajdziesz najbliższe słowo kodowe B 1 i następnie go rozszyfrować.

Konieczność. Z odwrotności. Załóżmy, że minimalna odległość między słowami kodowymi jest mniejsza niż 2 k+ 1. Następnie są dwa słowa kodowe, odległość między nimi będzie wynosić D(B 1, B 2) ≤ 2 k. Niech podczas przekazywania słowa B 1 zaakceptowane słowo Z znajduje się pomiędzy słowami B 1, B 2i ma dokładnie k błędy. Następnie D(C, B 1) = k, D (C, B 2) = D(B 1, B 2) – D(C, B 1) ≤ k. Zatem ze słowa c nie da się jednoznacznie zrekonstruować przesłanego słowa kodowego, B 1lub B 2. Doszliśmy do sprzeczności.

Przykład 13.3 . Rozważmy następujące pięciobitowe kody dla słów o długości 2 w alfabecie W = {0,1}:

B 1= K(00) = 00000, B 2= K(01) = 01011,

B 3= K(10) = 10101, B 4= k(11) =11110.

Minimalna odległość między różnymi słowami kodowymi wynosi D(bi, bj) = 3. Na mocy pierwszego twierdzenia o kodzie detekcyjnym kod ten jest w stanie wykryć w jednym słowie nie więcej niż dwa błędy. Na mocy drugiego twierdzenia kod jest w stanie poprawić co najwyżej jeden błąd w słowie.

Kody grupowe

Przyjrzyjmy się bliżej kodom słów w alfabecie W= (0, 1). Jeśli chodzi o słowa długości T używane są słowa kodowe określające długość N, wtedy nazwiemy takie kody ( T , P)-kody. Całkowita długość słów M równa się 2 M. Ustawić ( T , P)-code, możesz wyświetlić listę słów kodowych dla wszystkich możliwych słów o długości M, jak w poprzednim przykładzie. Bardziej ekonomicznym sposobem określenia słów kodowych jest zadanie macierzowe.

W tym przypadku określona jest macierz generująca G= ∣∣ gij∣∣ porządek T × P od 0 do 1. Słowa kodowe ustalane są każdorazowo po słowie A = A 1A 2... Na mnożąc to słowo po lewej stronie jako wektor przez macierz generującą

Tutaj zdefiniowano dodawanie modulo 2. Aby różne słowa odpowiadały różnym słowom kodowym, wystarczy mieć w macierzy G podstawa jednostkowa mniejszego rzędu T, na przykład ten skrajnie lewy.

Przykład 13.4 . Rozważ macierz generującą

Ta macierz definiuje kod (3, 4). W tym przypadku pierwsze trzy znaki słowa kodowego mają charakter informacyjny, a czwarty to znak kontrolny. Jest równa 0, jeśli w słowie źródłowym jest parzysta liczba jedynek, i 1, jeśli w słowie jest nieparzysta liczba jedynek. Na przykład za słowo A= 101 kod będzie B= aG= 1010. Minimalna odległość Hamminga pomiędzy słowami kodowymi wynosi D(bi, bj) = 2. Jest to zatem kod wykrywający jednorazowy błąd.

Definicja 13.2. Kod nazywa się Grupa , jeśli zbiór wszystkich słów kodowych tworzy grupę. Nazywa się liczbę jednostek w słowie a waga słowa i jest oznaczone jako If B- słowo kodowe i słowo odebrane w kanale komunikacyjnym Z = b + mi, potem słowo mi zwany wektor błędów .

Twierdzenie 13.3. Niech będzie grupa ( T , P)-kod. Następnie grupa przemienna DO wszystkich słów kodowych jest podgrupą grupy przemiennej Z wszystkie słowa o długości P, które można odebrać w kanale komunikacyjnym. Najmniejsza odległość między słowami kodowymi jest równa najmniejszej wadze niezerowego słowa kodowego i

Rozważ grupę czynników S/K. Łóżeczka tutaj zostaną określone przez zmianę mi + b, B∈ K.

Jako przedstawiciel klasy coset wybieramy element o najmniejszej wadze. Nazwiemy takie elementy liderzy sąsiednich klas .

Jeśli liderów interpretować jako wektory błędów, to każda sąsiadująca klasa jest zbiorem zniekształconych słów w kanale komunikacyjnym o ustalonym wektorze błędu, w szczególności gdy mi= 0 mamy sąsiadującą klasę słów bez zniekształceń, czyli zbiór wszystkich słów kodowych. Proces poprawiania i dekodowania słów Z polega na wyszukaniu sąsiedniej klasy, do której należy dane słowo Z = mi + B. Wektor błędu mi określa liczbę i lokalizację błędów, słowo kodowe B określa korektę odebranego słowa.

Aby ułatwić wyszukiwanie kosetu, a tym samym wektora błędu, Hamming zaproponował użycie kodów grupowych ze specjalnymi macierzami generującymi.

Kody Hamminga

Rozważmy konstrukcję Hamminga ( T , P) - kod o najmniejszej wadze słowa kodowego równej 3, czyli kod korygujący jeden błąd.

Włóżmy P = 2 R– 1 i niech każde słowo kodowe zawiera R znaki kontrolne i T postacie ( T = P – R= 2 R– 1– R) - informacyjny, R≥ 2, np. (1, 3) kod, (4, 7) kod itp. Ponadto w każdym słowie kodowym B= B 1B 2... b s symbole o indeksach równych potędze 2 będą symbolami kontrolnymi, a reszta będzie symbolami informacyjnymi. Na przykład dla kodu (4, 7) w słowie kodowym B= B 1B 2B 3B 4B 5B 6B 7 znaków B 1B 2B 4 będą symbolami kontrolnymi i symbolami B 3B 5B 6B 7- informacyjny. Aby określić macierz generatora G Hamminga ( T , P)-code, rozważ macierz pomocniczą M zamówienie R× P, Gdzie P = 2 R– 1, tak że w każdym J kolumna matrycy M będą symbole binarne J na przykład dla (4, 7) kod macierzy M będzie 3 × 7:

Zbiór wszystkich słów kodowych definiujemy jako zbiór rozwiązań jednorodnego układu liniowych równań algebraicznych postaci

bMT= 0.

Na przykład dla kodu (4, 7) takim systemem byłoby:

Wybierzmy naturalną bazę mollową układu bMT= 0, stojąc w kolumnach z liczbami równymi potędze 2. W ten sposób dzielimy zmienne na podstawowe (kod) i wolne (informacja). Teraz mając zdefiniowane zmienne swobodne, łatwo jest otrzymać zmienne podstawowe. Znajdźmy system podstawowy M= P – R rozwiązań tego jednorodnego układu. Zatem każde rozwiązanie układu jest ich liniową kombinacją M decyzje. Dlatego pisz wiersz po wierszu M rozwiązania układu podstawowego w postaci macierzy G rozmiar M× P, otrzymujemy macierz generującą grupy Hamminga ( T , P) kodu, np. dla kodu (4, 7), podstawowym systemem rozwiązań będzie 4 = 7 – 3 z następujących rozwiązań układu jednorodnego:

G 1= 1110000, G 2= 1001100, G 3= 0101010, G 4= 1101001.

Dowolna kombinacja liniowa tych rozwiązań będzie rozwiązaniem, czyli słowem kodowym. Z tych podstawowych rozwiązań ułóżmy macierz generującą

Teraz według dowolnego słowa A długość T= 4 łatwe do obliczenia słowo kodowe B długość P= 7 przy użyciu macierzy generatora B= aG. Jednocześnie symbole B 3, B 5, B 6, B 7 będzie miało charakter informacyjny. Zbiegają się z A 1, A 1, A 3, A 4.Symbole B 1, B 2, B 4 będzie kontrolowane.

Wniosek. Kody Hamminga są wygodne, ponieważ podczas dekodowania można łatwo określić kody. Niech będzie słowo otrzymane kanałem komunikacyjnym Z = mi + B, Gdzie mi- błąd, B- słowo kodowe. Następnie pomnóż go przez macierz pomocniczą cMT= (mi + B)MT= eM T. Jeśli eM T= 0, następnie słowo Z- kod i rozważamy: nie ma błędu. Jeśli eM T≠ 0, następnie słowo mi definiuje błąd.

Przypomnijmy, że skonstruowany Hammings ( T , P) -code identyfikuje jeden błąd. Dlatego wektor błędu mi zawiera jedną jednostkę w I pozycje. Co więcej, liczba I w rezultacie pozycja jest uzyskiwana w reprezentacji binarnej eM T, zbiega się z I kolumna matrycy M. Pozostaje zmienić symbol I w słowie c otrzymanym przez kanał przekreśl znaki kontrolne i zapisz zdekodowane słowo.

Niech na przykład będzie przyjęte słowo Z= 1100011 dla (4, 7) kodu Hamminga. Pomnóżmy to słowo przez macierz MT. Dostajemy

(1100011)M T=(010).

Dlatego w drugim znaku występuje błąd. Zatem słowem kodowym będzie B= 1000011. Przekreśl znaki kontrolne B 1, B 2, B 4. Zdekodowane słowo będzie A = 0011.

Oczywiście, jeśli błąd został popełniony w więcej niż jednym znaku, to ten kod go nie poprawi.