Matematyka cyklicznych kontroli redundancji

Cykliczna kontrola redundancji (CRC) opiera się na dzieleniu w pierścieniu wielomianów po ciele skończonym GF(2) (liczby całkowite modulo 2 ), czyli zbiorze wielomianów , w których każdy współczynnik jest równy zero lub jeden, oraz operacjach arytmetycznych owinąć.

Dowolny ciąg bitów można zinterpretować jako współczynniki wielomianu wiadomości tego rodzaju i aby znaleźć CRC, mnożymy wielomian wiadomości przez, a następnie znajdujemy resztę z dzielenia przez ${\ displaystyle x ^ {n}}$ stopień - generator wielomianu ${\ displaystyle n}$ . Współczynniki reszty wielomianu to bity CRC.

Matematyka

Ogólnie rzecz biorąc, obliczenie CRC odpowiada euklidesowemu podziałowi wielomianów przez GF(2) :

${\ Displaystyle M (x) \ cdot x ^ {n} = Q (x) \ cdot G (x) + R (x).}$

Tutaj $n$$displaystyle$ oryginalnej wiadomości $,$ a wielomianem Bity $_$ oryginalną $_$ _ „Suma kontrolna” CRC jest tworzona przez współczynniki reszty wielomianu ${\ Displaystyle R (x)}$ , którego stopień jest ściśle mniejszy niż ${\ displaystyle n}$ . $_$ ilorazowy nie Korzystając z operacji modulo , można stwierdzić, że

${\ Displaystyle R (x) = M (x) \ cdot x ^ {n} \, {\ bmod {\,}} G (x).}$

W komunikacji nadawca dołącza $bity R$ oryginalnych bitach M, co można wykazać jako równoważne z wysłaniem ${\ Displaystyle M (x) \ cdot x ^ {n} -R (x)}$ (słowo kodowe ). Odbiorca, wiedząc, ${\ Displaystyle G (x)}$ i dlatego ${\ Displaystyle n}$ , oddziela M od R i powtarza obliczenia, sprawdzając, czy otrzymane i obliczone R są równe. Jeśli tak, to odbiorca zakłada, że ​​otrzymane bity wiadomości są poprawne.

W praktyce obliczenia CRC najbardziej przypominają długie dzielenie w systemie binarnym, z wyjątkiem tego, że odejmowania nie zapożyczają się z bardziej znaczących cyfr, a tym samym stają się wyłącznymi lub operacjami.

CRC jest sumą kontrolną w ścisłym sensie matematycznym, ponieważ można ją wyrazić jako ważoną sumę modulo-2 syndromów na bit , ale to słowo jest ogólnie zarezerwowane bardziej konkretnie dla sum obliczanych przy użyciu większych modułów, takich jak 10, 256, lub 65535.

CRC mogą być również wykorzystywane jako część kodów korekcji błędów , które umożliwiają nie tylko wykrycie błędów transmisji, ale także odtworzenie poprawnej wiadomości. Kody te są oparte na ściśle powiązanych zasadach matematycznych.

Wielomian arytmetyczny modulo 2

Ponieważ współczynniki są ograniczone do jednego bitu, każda operacja matematyczna na wielomianach CRC musi odwzorować współczynniki wyniku na zero lub jeden. Na przykład dodatkowo:

${\ Displaystyle (x ^ {3} + x) + (x + 1) = x ^ {3} + 2x + 1 \ równoważnik x ^ {3} + 1 {\ pmod {2}}.}$

Zauważ, że w powyższym $2$ jest równoważne zeru, ponieważ dodawanie współczynników odbywa się modulo

${\ Displaystyle 2x = x + x = x \ razy (1 + 1) \ równoważnik x \ razy 0 = 0 {\ pmod {2}}.}$

Dodawanie wielomianów modulo 2 jest tym samym, co bitowe XOR . Ponieważ XOR jest odwrotnością samego siebie, odejmowanie wielomianowe modulo 2 jest takie samo jak bitowe XOR.

Mnożenie jest podobne (iloczyn bez przenoszenia ):

${\ Displaystyle (x ^ {2} + x) (x + 1) = x ^ {3} + 2x ^ {2} + x \ równoważnik x ^ {3} + x {\ pmod {2}}.}$

Możemy również podzielić wielomiany mod 2 i znaleźć iloraz i resztę. Załóżmy na przykład, że dzielimy przez ${\ displaystyle x ^ {3} + x ^ {2} + x}$ przez ${\ displaystyle x + 1}$ . Znaleźlibyśmy to

${\ Displaystyle {\ Frac {x ^ {3} + x ^ {2} + x} {x + 1}} = (x ^ {2} + 1) - {\ Frac {1} {x + 1}} .}$

Innymi słowy,

${\ Displaystyle (x ^ {3} + x ^ {2} + x) = (x ^ {2} + 1) (x + 1) -1 \ równoważnik (x ^ {2} + 1) (x + 1 )+1{\pmod {2}}.}$

Dzielenie daje iloraz x ² + 1 z resztą -1, który, ponieważ jest nieparzysty, ma ostatni bit równy 1.

W powyższych równaniach ${\ Displaystyle x ^ {3} + x ^ {2} + x}$ reprezentuje oryginalne bity wiadomości 111 , ${\ Displaystyle x + 1}$ jest wielomianem generatora $,$ a reszta $)$ równoważnie to CRC pomnożyliśmy wiadomość przez $\ displaystyle x ^ {1}}$${\ Displaystyle x ^ {3} + x ^ {2} + x}$ .

Wariacje

Istnieje kilka standardowych odmian CRC, z których każda lub wszystkie mogą być używane z dowolnym wielomianem CRC. Odmiany implementacji, takie jak endianowość i prezentacja CRC, wpływają tylko na mapowanie ciągów bitów na współczynniki i nie wpływają na ${\ Displaystyle M (x)}$ i ${\ Displaystyle R (x)}$ właściwości algorytmu.

• Aby sprawdzić CRC, zamiast obliczania CRC w wiadomości i porównywania go z CRC, można uruchomić obliczenie CRC na całym słowie kodowym. Jeśli wynik (nazywany resztą) wynosi zero, kontrola przechodzi pomyślnie. To działa, ponieważ słowo kodowe to ${\ Displaystyle M (x) \ cdot x ^ {n} -R (x) = Q ( x)\cdot G(x)}$ , która jest zawsze podzielna przez ${\ Displaystyle G (x)}$ .

Upraszcza to wiele implementacji, unikając konieczności specjalnego traktowania ostatnich kilku bajtów wiadomości podczas sprawdzania CRC.

• Rejestr przesuwny może być inicjowany jedynkami zamiast zerami. Jest to $równoznaczne$ z odwróceniem pierwszych wiadomości przed podaniem ich do algorytmu. Równanie CRC przyjmuje postać ${\ Displaystyle M (x) \ cdot x ^ {n} + \ suma _ {i = m} ^ {m + n-1} x ^ {i} = Q (x) \ cdot G (x) + R (x)}$ , gdzie ${\ Displaystyle m> \ deg (M (x))}$ to długość wiadomości w bitach. Zmiana, jaką to nakłada na ${\ Displaystyle R (x)}$ jest funkcją wielomianu generującego i długości wiadomości ${\ Displaystyle \ lewo (\ suma _ {i = m} ^ {m + n- 1}x^{i}\right)\,{\bmod {\,}}G(x)}$ .

Powodem zastosowania tej metody jest to, że niezmodyfikowany CRC nie rozróżnia dwóch komunikatów, które różnią się jedynie liczbą wiodących zer, ponieważ wiodące zera nie wpływają na wartość ${\ Displaystyle M (x)}$ . Kiedy ta inwersja jest wykonywana, CRC rozróżnia takie komunikaty.

• CRC można odwrócić przed dołączeniem do strumienia komunikatów. Chociaż niezmodyfikowany CRC rozróżnia komunikaty z różną liczbą końcowych $zer$ , nie wykrywa końcowych zer dodanych po Dzieje się tak, ponieważ wszystkie prawidłowe słowa kodowe są wielokrotnościami , więc sol $}$$(x)$ razy to słowo kodowe jest również wielokrotnością. (W rzeczywistości właśnie dlatego pierwszy opisany powyżej wariant działa).

W praktyce dwie ostatnie odmiany są niezmiennie używane razem. Zmieniają transmitowany CRC, więc muszą być zaimplementowane zarówno po stronie nadajnika, jak i odbiornika. Chociaż ustawienie rejestru przesuwnego na jedynki jest łatwe do wykonania na obu końcach, odwrócenie wpływa na odbiorniki wdrażające pierwszą odmianę, ponieważ CRC pełnego słowa kodowego, które już zawiera CRC, nie wynosi już zero. Zamiast tego jest to stały niezerowy wzór, CRC wzorca $inwersji$ .

CRC można zatem sprawdzić albo za pomocą oczywistej metody obliczania CRC w wiadomości, odwrócenia jej i porównania z CRC w strumieniu wiadomości, albo przez obliczenie CRC na całym słowie kodowym i porównanie go z oczekiwaną stałą wartością ${\ Displaystyle C (x)}$ , zwany wielomianem kontrolnym, resztą lub magiczną liczbą . Można to obliczyć jako ${\ Displaystyle C (x) = \ lewo (\ suma _ {i = n} ^ {2n-1} x ^ {i} \ prawej) \, {\ bmod {\,}} G ( x)}$ lub równoważnie przez obliczenie niezmodyfikowanego CRC wiadomości składającej się z $i$ , $=0}^{n-1}x^{i}}$${\ Displaystyle M (x) = \ suma _ {$ .

Te inwersje są niezwykle powszechne, ale nie są powszechnie wykonywane, nawet w przypadku wielomianów CRC-32 lub CRC-16-CCITT.

Reprezentacje odwrotne i wielomiany odwrotne

Reprezentacje wielomianowe

Przykład 16-bitowego wielomianu CCITT w opisanych postaciach (bity w nawiasach kwadratowych są zawarte w reprezentacji słowa; bity na zewnątrz oznaczają 1 bit; pionowe kreski wyznaczają granice nibble ):

16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 współczynnik 1 [0 0 0 1 |0 0 0 0 |0 0 1 0 |0 0 0 1] Normalny [ 1 | 0 | 2 | 1 ] Nibbles of Normal 0x1021 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 [1 0 0 0 |0 1 0 0 |0 0 0 0 |1 0 0 0] 1 Odwrotny [ 8 | 4 | 0 | 8 ] Nibbles of Reverse 0x8408 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 1 [0 0 0 0 |1 0 0 0 |0 0 0 1 |0 0 0 1] Odwrotność [ 0 | 8 | 1 | 1 ] Nibbles odwrotności 0x0811 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Odwrotność odwrotności 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Koopman [1 0 0 0 |1 0 0 0 |0 0 0 1 |0 0 0 0] 1 [ 8 | 8 | 1 | 0 ] Nibbles 0x8810

Wszystkie dobrze znane wielomiany generatora CRC stopnia $szesnastkowe$ . W obu $.$ współczynnik jest i rozumiany jako 1

• Reprezentacja msbit-first to liczba szesnastkowa z $1.$ Najbardziej znaczący bit reprezentuje współczynnik ${\ displaystyle x ^ {n-1} }$ , a najmniej znaczący bit reprezentuje współczynnik ${\ displaystyle x ^ {0}}$ .
• Reprezentacja pierwszego bitu to liczba szesnastkowa z $x$ , z których najbardziej znaczącym bitem jest zawsze 1. Najbardziej znaczący bit reprezentuje współczynnik i najmniej znaczący bit $\ displaystyle x ^ {0}}$ bit reprezentuje współczynnik ${\ displaystyle x ^ {n-1}}$ .

Forma msbit-first jest często określana w literaturze jako normalna reprezentacja, podczas gdy lsbit-first jest nazywana reprezentacją odwróconą . Przy wdrażaniu CRC konieczne jest użycie poprawnej formy. Jeśli współczynnik $bit$ pierwszy rzut oka, widząc, który koniec ma

Aby jeszcze bardziej zagmatwać sprawę, artykuł P. Koopmana i T. Chakravarty'ego konwertuje wielomiany generatora CRC na liczby szesnastkowe w jeszcze inny sposób: najpierw msbit, ale z uwzględnieniem współczynnika i pomijając ${\ displaystyle x ^ {n}}$${\ displaystyle x ^ {0}}$ współczynnik. Ta reprezentacja „Koopmana” ma tę zaletę, że stopień można określić na podstawie postaci szesnastkowej, a współczynniki można łatwo odczytać w kolejności od lewej do prawej. Jednak nigdzie indziej nie jest używany i nie jest zalecany ze względu na ryzyko pomyłki.

Wielomiany odwrotne

Odwrotny wielomian jest tworzony przez przypisanie współczynników $}$ wielomianu do $}$$\ displaystyle x ^ {i$ do ${ \displaystyle x^{i}}$ współczynniki nowego wielomianu. Oznacza to ${\ displaystyle G (x)}$ że odwrotność wielomianu stopnia wynosi $n}$ sol x ${\ Displaystyle x ^ {n} G (x ^ {- 1})}$ .

Najbardziej interesującą właściwością wielomianów odwrotnych, gdy są używane w CRC, jest to, że mają one dokładnie taką samą siłę wykrywania błędów, jak wielomiany, których są odwrotnościami. Odwrotność wielomianu generuje te same słowa kodowe , tylko odwrócone bity - to znaczy, jeśli wszystkie oprócz pierwszych bitów słowa kodowego pod oryginalnym wielomianem są pobierane, odwracane i używane jako nowa wiadomość, CRC z n {\ displaystyle $n$ ta wiadomość pod wielomianem odwrotnym jest równa odwrotności pierwszego ${\ displaystyle n}$ bitów oryginalnego słowa kodowego. Ale wielomian odwrotny nie jest tym samym, co oryginalny wielomian, a CRC wygenerowane przy jego użyciu nie są takie same (nawet odwrócenie bitów modulo), jak te wygenerowane przez oryginalny wielomian.

Siła wykrywania błędów

Zdolność CRC do wykrywania błędów zależy od stopnia jego kluczowego wielomianu i od konkretnego zastosowanego kluczowego wielomianu. „Wielomian błędu” to symetryczna różnica słowa kodowego odebranej wiadomości i $.$ Błąd pozostanie niewykryty przez algorytm CRC wtedy i tylko wtedy, gdy wielomian błędu jest podzielny przez wielomian CRC.

• Ponieważ CRC opiera się na dzieleniu, żaden wielomian nie może wykryć błędów składających się z ciągu zer dołączonego do danych lub brakujących zer wiodących. Jednak zobacz Wariacje .
• Wszystkie błędy pojedynczego bitu zostaną wykryte przez dowolny wielomian z co najmniej dwoma wyrazami o niezerowych współczynnikach. Wielomian błędu to i $}$ podzielny tylko przez wielomiany ${$${\ displaystyle x ^$ gdzie $\ styl wyświetlania i\leq k}$ .
• Wykryte zostaną wszystkie dwa błędy bitowe oddalone od siebie o odległość mniejszą niż rząd pierwotnego wielomianu, który jest współczynnikiem wielomianu generatora . Wielomian błędu w przypadku dwubitowym to ${\ Displaystyle E (x) = x ^ {i} + x ^{k}=x^{k}\cdot (x^{ik}+1),\;i>k}$ . $pozostawia$$wspomniano$ powyżej, będzie podzielny przez który $,$ definicji najmniejszą wartością że wielomian $.$ . Wielomiany o największym rzędzie nazywane są wielomianami pierwotnymi , a dla wielomianów stopnia ze współczynnikami binarnymi mają rząd $2$$\ displaystyle 2 ^ {n} -1$ .
• $.$ nieparzystej liczbie bitów zostaną wykryte przez wielomian, który Jest to równoważne z wielomianem mającym parzystą liczbę wyrazów o niezerowych współczynnikach. Ta pojemność zakłada, że ​​​​generator wielomianu jest iloczynem wielomianu pierwotnego stopnia, $Displaystyle$$x + 1$${$ oprócz mają nieparzystą liczbę niezerowych współczynników.
• Wszystkie błędy serii $o$ długości wykryte przez dowolny wielomian stopnia $lub$$, który$ ma niezerowy .

(Nawiasem mówiąc, nigdy nie ma powodu, aby używać wielomianu z terminem zerowym $x ^ {n} }$ Przypomnijmy, że CRC to reszta wielomianu wiadomości razy $displaystyle$$x)}$ przez wielomian CRC. Wielomian z terminem zerowym $zawsze$ czynnik jako czynnik. Więc jeśli $Displaystyle K$ ( oryginalny wielomian CRC i ${\ Displaystyle K (x) = x \ cdot K '(x)}$ , wtedy

${\ Displaystyle M (x) \ cdot x ^ {n-1} = Q (x) \ cdot K ' (x)+R(x)}$

${\ Displaystyle M (x) \ cdot x ^ {n} = Q (x) \ cdot x \ cdot K '(x) + x \ cdot R (x)}$

${\ Displaystyle M (x) \ cdot x ^ {n} = Q (x) \ cdot K (x) + x \ cdot R (x)}$

${$ to, że suma kontrolna dowolnej wiadomości z wielomianem $}$ x ) dopisane zero. To tylko trochę strata.)

Połączenie tych czynników oznacza, że ​​dobre wielomiany CRC to często prymitywne wielomiany (które mają najlepsze 2-bitowe wykrywanie błędów) lub prymitywne wielomiany stopnia $displaystyle$$x +1}$ + (który wykrywa wszystkie nieparzyste liczby błędów bitowych i ma połowę dwubitowej zdolności wykrywania błędów pierwotnego wielomianu $)$ .

filtry bitowe

Technika analizy z wykorzystaniem filtrów bitowych pozwala na bardzo efektywne wyznaczenie własności danego wielomianu generatora. Wyniki są następujące:

1. $serii (oprócz jednego) o$ generatora można wykryć za pomocą . Obejmuje to błędy 1-bitowe (wybuch długości 1). Maksymalna długość to $displaystyle n + 1}$$\$ , gdy jest wielomianu generatora (który sam ma długość ${\ displaystyle n + 1} ).$ ). Wyjątkiem od tego wyniku jest wzorzec bitowy taki sam jak w przypadku wielomianu generatora.
2. Wszystkie błędy nieparzystych bitów są wykrywane przez wielomiany generatora o parzystej liczbie wyrazów.
3. 2-bitowe błędy w (wielokrotnej) odległości najdłuższego filtra bitowego o parzystości do wielomianu generatora nie są wykrywane; wszystkie inne są wykrywane. Dla stopni do 32 istnieje optymalny wielomian generatora o tym stopniu i parzystej liczbie wyrazów; w tym przypadku wspomniany powyżej okres to ${\ Displaystyle 2 ^ {n-1} -1}$ . Dla ${\ displaystyle n = 16}$ oznacza to, że bloki o długości 32 767 bitów nie zawierają nieodkrytych błędów 2-bitowych. Dla nieparzystej liczby wyrazów w wielomianie generatora może istnieć kropka ${\ Displaystyle 2 ^ {n} -1}$ ; jednak te wielomiany generatora (z nieparzystą liczbą wyrazów) nie wykrywają wszystkich nieparzystych liczb błędów, dlatego należy ich unikać. Listę odpowiednich generatorów z parzystą liczbą terminów można znaleźć w linku wymienionym na początku tej sekcji.
4. Wszystkie pojedyncze błędy bitowe we wspomnianym powyżej okresie filtra bitów (dla parzystych wyrazów w wielomianie generatora) można jednoznacznie zidentyfikować na podstawie ich pozostałości. Tak więc metodą CRC można również korygować błędy jednobitowe (w tych granicach np. 32 767 bitów przy optymalnym generatorze wielomianów stopnia 16). Ponieważ wszystkie nieparzyste błędy pozostawiają nieparzystą resztę, można rozróżnić wszystkie parzyste błędy resztkowe, błędy 1-bitowe i błędy 2-bitowe. Jednak, podobnie jak inne SECDED , CRC nie zawsze mogą odróżnić błędy 1-bitowe od błędów 3-bitowych. Gdy w bloku wystąpią 3 lub więcej błędów bitowych, bitowa korekcja błędów CRC sama w sobie będzie błędna i spowoduje więcej błędów.

Zobacz też

• redukcja Barretta
• Kod poprawiający błąd
• Lista algorytmów sum kontrolnych
• Parzystość (telekomunikacja)
• Wielomianowe reprezentacje cyklicznych kontroli redundancji

Linki zewnętrzne

• Koopman, Phil. „Blog: suma kontrolna i CRC Central” . — wymienia wielomiany CRC dające najlepsze odległości Hamminga .