Jak działa CRC?

Rozdział 8 A gdyby tak przesuwać o 8 bitów?

Rozdz. 8.1 Wstęp
Przekonasz się, że przesunięcia 8-bitowe są bardzo podobne do 2-bitowych z poprzedniego rozdziału. Przełożenie jest prawie 1:1 tzn. zamiast przesunięć 2-bitowych są 8-bitowe zaś samo CRC może mieć 816 lub 32 bity.  Tablicę 4x8 zastąpimy tablicą 256×8, 256×16 lub 256×32. Właśnie ze względu na ich duże rozmiary trudno jest realizować ich animację. Jednak dzięki analogii z przesunięciami 2-bitowymi, niepełna animacja przesunięć 8-bitowych którą zaproponuje, bez problemu pozwoli nam wyobrazić działanie systemu.

Rozdz. 8.2 Jakie jest CRC po przesunięciu 8-bitowym?
Jest to odpowiednik Rozdz. 7.3 Jakie jest CRC po przesunięciu 2-bitowym?

Rys. 8-1
Jakie jest CRC po przesunięciu 8-bitowym?   ANIMACJA
W Rozdz. 7.3 badaliśmy stan 8-bitowego CRC po przesunięciu 2-bitowym dla wszystkich 4 możliwych kombinacji 2 początkowych stanów rejestru CRC: 00,01, 10 lub 11. Tu tymi kombinacjami będą 00000000, 00000001, 00000010….11111110 i 11111111. W sumie 256 kombinacji, czyli nasza tablica powinna mieć rozmiar 256×8.
No to zaczynamy wyznaczanie tych końcowych stanów. Dolny wiersz tablicy na Rys. 8-1 to 8 młodszych bitów “dzielnika”=1 10010101. Na jego podstawie będzie budowana tablica 256×8 dla przesunięć 8-bitowych.
Zaczynamy od najłatwiejszego stanu początkowego tj.  00000000. Jest oczywiste, że bity abcdefgh będą tylko przesunięto czyli ich stanem końcowym będzie abcdefgh inaczej abcdefgh xor 00000000.
W ten sposób wyznaczyliśmy pierwszy wiersz  naszej tablicy=00000000.
A jak wyznaczyć wiersze dla pozostałych 255 kombinacji? Z oczywistych powodów nie będziemy tego robić i ograniczymy się tylko dla jednej kombinacji początkowej np. dla 10111010 czyli dla wiersza tablicy o numerze binarnym 10111010. W ten sam sposób można wyznaczyć pozostałe 254 wiersze tablicy.
Do stanu końcowego po przesunięciach:
CRC=abcdefgh xor 00111000–>patrz Uwaga
czyli do wiersza o numerze binarnym 10111010 naszej tablicy możemy dojść na 2 sposoby:
zaufać naszej maszynce w animacji, która działa zawsze tak samo jak dotychczas i po 8 kliknięciach dojść do stanu CRC=00111000
– rachunkowo
tj. przesuwać czerwone kreski w prawo i xor-rować zawartość między czerwonymi kreskami przez:
–>00000000 gdy poprzednie BS=0
–>10010101 gdy poprzednie BS=1
Początkowe BS=1 jako pierwszy bit stanu początkowego CRC=10010101
Następne BS czyli next BS to xor kolumny przy lewej czerwonej kresce.
Uff! Brzmi to dosyć mętnie i skomplikowanie, ale najlepiej gdybyś sam do tego doszedł klikając zegar!
Uwaga:
00111000 to xor 8 wierszy miedzy czerwonymi kreskami które pojawią się na końcu animacji.

Rozdz. 8.3 CRC 32 bitowe z przesunięciem 8-bitowym

Rys. 8-2
CRC 32 bitowe z przesunięciem 8-bitowym   ANIMACJA
Z Rozdz. 6 wiemy, że zdolność wykrywania błędów zależy od wielkości CRC. Powszechnie stosowane w internecie CRC 32-bitowe ma dużo większą moc wykrywania błędów niż CRC 8-bitowe. Skoki pozostają jednak 8-bitowe.

Generatorem naszego CRC (czyli “dzielnikiem” bez pierwszego bitu=1) jest dolny wiersz tablicy czyli:
generator=tablica(1)=01101100 10000001 00011101 10110111
Stan początkowy systemu to:
CRC=01100101 a0b0c0d0e0f0g0h0 a1b1c1d1e1f1g1h1 a2b2c2d2e2f2g2h2
oraz pierwszy bajt pamięci A “czekający” na przesunięcie 8-bitowe czyli A=a3b3c3d3e3f3g3h3

Używając bajtów i liczb hexa
65=01100101 C0=a0b0c0d0e0f0g0h0 C1=a1b1c1d1e1f1g1h1 C2=a2b2c2d2e2f2g2h2 C3=a3b3c3d3e3f3g3h3
możemy to zapisać bardziej zwięźle:

generator=tablica(1)=6C 81 1D B
Stan początkowy systemu to:
CRC=65 C0 C1 C2
A
=C3                                     

Jakie będzie CRC po 8 przesunięciach bitowych przy początkowym bajcie CRC=01100101 jak na Rys. 8-2?
Z animacji oraz niezależnie od tego z “xor-owania między czerwonymi kreskami” wynika, że będzie to:
CRC=C0 C1 C2 C3 xor D7 71 76 8C
gdzie:
D7 71 76 8C 
to 11010111 01110001 01110110 10001100
C0 C1 C2 C3 to patrz wyżej.
A to oznacza, że dla generator=6C 81 1D B7
tablica(65)=D7 71 76 8C
tablica(00)
=00 00 00 00–>oczywista oczywistość bo BS=0 czyli są tylko przesunięcia!

W podobny sposób wyznaczymy pozostałe 254 wierszy tablicy o wymiarach 256×32.

Rozdz. 8.4 Metoda tablicowa bezpośrednia dla przesunięć 8-bitowych
Zanim zaczniesz badać system to wróć na chwilę do Rozdz. 7.3 i przypomnij sobie jak działa ta metoda dla przesunięć 2-bitowych.

Rys. 8-3
Metoda tablicowa bezpośrednia dla przesunięć 8-bitowych    ANIMACJA
Nawet Rys. 8-3 jest podobny do Rys. 7-3 z Rozdz. 7.3!
Analogie są następujące:
Rys. 7-3
– CRC 
jest 1-bajtowe
pamięć A 2-bajtowa podzielona na 4 ćwierćbajty w każdym z 2 wierszy
pierwszym ćwierćbajtem pierwszego wiersza pamięci A jest 10
pamięć B jednobajtowa z 4 zerowymi ćwierćbajtami
tablica 4 bajtowa z których każdy bajt podzielony jest na 4 ćwierćbajty
Rys. 8-4
– CRC 
jest 4-bajtowe
pamięć A 8-bajtowa podzielona na 4 bajty w każdym z 2 wierszy
pierwszym bajtem pierwszego wiersza pamięci A jest 0x65 czyli 011001010
pamięć B 4-bajtowa z 4 zerowymi bajtami
tablica 256×4 bajtowa w której każdy z 256 wierszy podzielony jest na 4 bajty
Z Rozdz. 8.3 wynika, że w tablicy po adresem:
0x00 jest 00 00 00 00  (4 zerowe bajty)
– 0x65 
jest D7 71 76 8C
Pozostałe 254  4-bajtowe wiersze tablicy można oczywiście obliczyć, ale dałem sobie spokój.

Z animacji wynika, że przebiegi są podobne do  z Rozdz. 7.4 tylko skoki są bajtowe, a nie ćwierćbajtowe. Animacja została zakończona na 7 impulsie zegarowym, potem wraca do stanu początkowego. Pierwsze 4 stany to zwykłe przesunięcia, bo BS=00. W piątym stanie następuje xor-owanie 4-bajtowego CRC zawartość wskazaną przez BS=65 czyli przez D7 71 76 8C. Dlatego bajty A1 A2 A3 i A4 rejestru CRC zmienią się na  A1* A2* A3* A4*. Na tym animacja się kończy i wraca do stanu początkowego. Pozostałe stany animacji tj. 7 podwónych  xor-owań przez zawartość tablicy wskazaną przez BS oraz “przepychanie” CRC 4 zerowymi bajtami musisz sobie wyobrazić korzystając z rozdz. 7.4.  Pamiętaj tylko, że tu odpowiednikiem bajtów ćwierćbajty czyli 2 bity.

Rozdz. 8.5 Metoda tablicowa „lewa” z podwójnym xor-owaniem dla przesunięć 8-bitowych
Wróć do Rozdz. 7.4 i przypomnij sobie jak działa ta metoda dla przesunięć 2-bitowych. Działania w obu metodach są podobne.

Rys. 8-4
Metoda tablicowa „lewa” z podwójnym xor-owaniem dla przesunięć 8-bitowych    ANIMACJA
Rys. 8-4 jest podobny do Rys. 7-4 z Rozdz. 7.5!
W tej metodzie następna wartość bajtu BS czyli BSnext obliczana jest jako początkowy bajt A xor początkowy bajt CRC. Dzięki temu unikamy początkowego  “pustego” przepychania wiadomości z A przez rejestr CRC oraz nie występuje zerowa 4-bajtowa  pamięć B, która jak pamiętamy, była “przepychana” na końcu cyklu przez rejestr CRC.
Animacja przedstawia tylko stan początkowy oraz pierwsze “podwójne xor-owanie”. Pozostałe stany animacji tj.  7 “podwójnych xor-owań” musisz sobie wyobrazić korzystając z przesunięć 2-bitowych w rozdz. 7.5.
W odróżnieniu od metody bezpośredniej w rozdz. 8.4, wiadomość z A nie przechodzi szeregowo przez CRC, czyli początkowy bajt z A nie jest wprowadzany do najmłodszego bajtu CRC.

Rozdz. 8.6 Metoda tablicowa „prawa” z podwójnym xor-owaniem dla przesunięć 8-bitowych
Wróć do Rozdz. 7.6 i przypomnij sobie jak działa ta metoda dla przesunięć 2-bitowych. Działania w obu metodach są podobne.

Rys. 8-5
Metoda tablicowa „prawa” z podwójnym xor-owaniem dla przesunięć 8-bitowych    ANIMACJA
Rys. 8-5 jest podobny do Rys. 7-5 z Rozdz. 7.4!  Główną zaletą metody “prawej” jest możliwość wysyłania bajtów do sieci w postaci jak najbardziej naturalnej. Tzn. takiej w której bit lewy  jest starszy. Więcej na ten temat w rozdz. 7.6 w którym  bit lewy w ćwierćbajcie jest starszy. Suma sumarum- bity w bajtach nie muszą być odwracane przed wysłaniem do sieci.
Aby tak było muszą być spełnione następujące warunki
:
bajty A0 A1 …A7 są ustawione w odwrotnych położeniach niż na Rys. 8-4 po to by były wysyłane w tej samej kolejności jak na Rys. 8-4
bity w bajtach A0 A1 …A7 mają jednak tę samą kolejność jak na Rys. 8-4!
32 bity w tablicy są “obrócone” względem osi środkowej tablicy. W ten sposób np. 8 lewych   bitów D7=11000111 w tablicy na Rys. 8-4 stają prawymi bitami “obróconymi” D7i=11100011. Uwaga ta dotyczy także bajtów 71 76 8C które też stają się “obróconymi”  71i 76i 8Ci.
stan początkowy CRC też powinien być “obrócony”. Tu akurat nie ma to znaczenia bo stan początkowy jest zerowy. Ale może być też niezerowy i wtedy ma to znaczenie.
W animacji ujęte są tylko stan początkowy oraz pierwsze “podwójne xor-owanie”. Pozostałe stany animacji tj.  3 “podwójnych xor-owaiamusisz sobie wyobrazić korzystając z przesunięć 2-bitowych w rozdz. 7.6.

Rozdz. 8.7 Software czyli program obliczający CRC
Rozdział jest odpowiednikiem Rozdz.7.7. Jedyna różnica to przesunięcia bajtowe zamiast ćwierćbajtowych (dwubitowych). Wystarczy w instrukcjach zamienić wyrażenie “2 bity” na “8 bitów”. Pamiętaj też o tym, że tablice mają inne rozmiary.

Rozdz. 8.7.1 Program dla metody tablicowej bezpośredniej z przesunięciami 8-bitowymi
Rejestry BS CRC A B z Rys.8-3 tworzą wspólny rejestr przesuwny BS_CRC_A_B. Instrukcja  Wpisz 8 bitów z A do CRC w lewo naszego pseudojęzyka, wpisuje nie tylko 8 początkowych bitów do CRC, ale przesuwa też cały rejestr BS_CRC_A_B o 8 bitów w lewo. Następnie CRC jest xor-owane przez wiersz tablicy wskazany przez BS.

Program w pseudojęzyku
Wpisz wiadomość do A
Wpisz zera do B
Dopóki A niepuste
Wpisz 8 bitów z A do CRC w lewo
CRC=CRC xor tablica(BS) }
Po wyjściu z pętli CRC będzie zawierało obliczoną “resztę”.

Rozdz. 8.7.2 Program dla metody tablicowej “lewej” z podwójnym xor-owaniem i przesunięciami 8-bitowymi
Nie ma  zerowego bajtu B.  Wspólny rejestr przesuwny w lewo tworzą tylko BS_A. Czyli A nie przechodzi przez CRC jak w poprzednim przykładzie, ale samo CRC też  jest oczywiście przesuwane o 8 bitów w lewo.
Po każdym 8-bitowym przesunięciu  w lewo wspólnego  rejestru BS_A, obliczane jest BS:
BS=8 początkowych bitów A xor 8 początkowych bitów CRC.
Następnie CRC jest xor-owane przez wiersz tablicy wskazany przez BS.

Program w pseudojęzyku
Wpisz wiadomość do A
Dopóki A niepuste
{ Przesuń BS_A o 8 bitów w lewo
BS=8 początkowych bitów A xor 8 początkowych bitów CRC
CRC=CRC 
xor tablica(BS) }
Po wyjściu z pętli CRC będzie zawierało obliczoną “resztę”.

Rozdz. 8.7.3 Program dla metody tablicowej “prawej” z podwójnym xor-owaniem i przesunięciami 8-bitowymi
Program różni się od poprzedniego tylko przesunięciem w prawo. Pamiętaj jednak o uwagach dotyczących tablicy CRC pod  Rys. 8-5! Także bajty w A “obrócone” względem środkowej osi, ale bity w bajtach już nie!
Dzięki temu programista nie musi “obracać” każdego bajtu przed wysłaniem go do UART-u.

Program w pseudojęzyku
Wpisz wiadomość do A
Dopóki A niepuste
{ Przesuń BS_A o 8 bitów w prawo
 BS=8 początkowych bitów A xor 8 początkowych bitów CRC
CRC=CRC 
xor tablica(BS) }
Obróć CRC

Po wyjściu z pętli należy jeszcze obrócić  CRC.