How does CRC work?
Chapter 8 What if we could do 8 bits shifts?
Chapter. 8.1 Introduction
The 8-bit shifts are very similar to 2-bit shifts from the previous chapter. The „gearing” is 1:1 almost . The 2-bit shifts–>8-bit shifts and 4×8 tables–>tables 256×8, 256×16 or 256×32. This last tables example is a reason of the word „almost”. These big tables cause difficulties with principle of operation understanding. But it will be child’s play for you after 2-bit shifts from the Chapter 7.
Chapter 8.2 What’s the CRC after eight bits shifts?
This is Chapter 7.3 counterpart.
Fig. 8-1
What’s the CRC after eight bits shifts? ANIMATION
We tested already CRC state after 2 bits shifts for all possible 4 initial CRC combinations shifts. These combinations were 00,01, 10 lub 11.
We do 8 bits shifts and there are 256 combinations now–> 00000000, 00000001, 00000010….11111110 i 11111111.
So the 256×8 table is now instead of 4×8 table as previously.
Let’s start the 256×8 table construction.
Initial CRC=00000000 state is the easiest. Bits abcdefgh are waiting in the A register.
There are shifts only because BS=0–>the new state after 8 shifts will be abcxdefgh=abcxdefgh xor 00000000.
Conclusion:
The Table(0)=00000000
How do calculate remaining 255 table rows?
I am a lazy man and I will calculate the CRC state for one initial combination CRC=10111010 only.
This is 65 number as hexa or 101 as decimal.
The animation shows 2 ways to the ultimate CRC=abcdedfgh xor 10111010
– We believe in our animation machine. It acts as for 2 shifts previously,
– Computationally. We shift right red lines between and xor the contents between red lines by:
–>00000000 when previously BS=0
–>10010101 when previously BS=1
Inital BS=1 as a first initial state bit CRC=10010101 (or a bit to the right of the left red line)
The next BS is a xor of the column to the right of the left red line.
Phew!!! It sounds terribly but please study the animation exactly and all will be clear.
We already know the table rows:
table(0)=00000000
table(65)=10111010 (65 is a hexa number or 105 as decimal)
The way to remaining 254 rows is the same.
Chapter 8.3 32 bit CRC with 8 bits shifts
Fig. 8-2
32 bit CRC with 8 bit shifts ANIMATION
You have read the chapter 6 and you know that CRC-32 (4 bytes long CRC) is much stronger as transmission correcter tester, than simple CRC-8 (1 byte long CRC). There are 8 bits shifts too as in the chapter 8.2.
Registers description:
Poly (i.e. „divisor” without the first bit=1) is a lower table row i.e.
Poly=table(1)=01101100 10000001 00011101 10110111
System initial state:
CRC=01100101 a0b0c0d0e0f0g0h0 a1b1c1d1e1f1g1h1 a2b2c2d2e2f2g2h2
and the memory A byte „waiting” for 8 bits shift i.e.
A=a3b3c3d3e3f3g3h3
When bytes and hexa numbers are used:
65=01100101 C0=a0b0c0d0e0f0g0h0 C1=a1b1c1d1e1f1g1h1 C2=a2b2c2d2e2f2g2h2 C3=a3b3c3d3e3f3g3h3
We can write it in a easy manner:
Registers description:
poly=table(1)=6C 81 1D B
System initial state:
CRC=65 C0 C1 C2
A=C3
What is the CRC after 8 bits shifts when CRC initial byte is 65=01100101 as in Fig. 8-2?
Animations and „between red lines calculus” confirms that:
CRC=C0 C1 C2 C3 xor D7 71 76 8C
I.e. We have calculated the table no 65 row=table(65)= D7 71 76 8C = 11010111 01110001 01110110 10001100–>Fig. 8-3
65 hexa = 101 decimal = 01100101 binary
FF hexa = 256 decimal =11111111
The table(00)=0 is obviously because there are CRC shifts only.
The remaining 254 table rows will be calculated with this method too. The table dimension is 256×32.
Chapter 8.4 Direct table method for 8 bits shifts
I propose to return to chapter 7.3 for starters, to remind about similar 2 bits shifts method.
Fig. 8-3
Direct table method for 8 bits shifts ANIMATION
This figure is even similar to Fig. 7-6 from chapter 7.3!
Analogies:
FIg-7-6
– CRC is 1-byte long
– A memory has 2 rows and every row has 4 „quarterbytes”
– The first „quarterbytes” of the first A row is 10
– B memory has 1 row with 4 „zeroes” „quarterbytes”
– table is 4×4 rows and each row has 4 „quarterbytes”
FIg-8-3
– CRC is 4-byte long
– A memory has 2 rows and every row has 4 bytes
– The first byte of the first A row is 0x65 i.e. 011001010
– B memory has 1 row with 4 „zeroes” bytes
– table is 256×4 rows and each row has 4 bytes (256 decimal=FF hexa)
We already know that:
table(00) = 00 00 00 00
table(65) =D7 71 76 8C
The remaining 254 table rows are possible to calculate with the method as for table(65) of course.
The animations Fig. 7-6 and Fig. 8-3 are similar but the shifts are 8 bits instead of 2 bits ( in other words 1 byte instead of quarterbyte). First 4 states are byte shifts only, because BS=0x00 (or BS=00000000 binary or BS=0 decimal). The fifth state–>BS=0x65 and CRC=CRC xor table(BS=65)=CRC xor D7 71 76 8C. Therefore CRC register bytes A1 A2 A3 i A4 change to A1* A2* A3* A4*. The animations is finished here and returns to initial state. You have to imagine the remaining animations states using chapter 7.3. Replace quarterbytes for bytes only. Theses 3 states are 3 bytes xor-ings and 4 „zeroes” B bytes „pushings”as 3 quarterbytes xor-ings and 4 „zeroes” B quarterbytes „pushings” in chapter 7.3.
Chapter 8.5 The „Left” table method with double xor for 8 bits shifts
I propose to return to chapter 7.4 for starters, to remind about similar 2 bits shifts method.
Fig. 8-4
The „Left” table method with double xor for 8 bits shifts ANIMATION
This figure is even similar to Fig. 7-7 from chapter 7.4!
Method is more concrete than „direct” table–>chapter8.3. There aren’t 4 „empty” initial shifts and 4 final „zeroes” B „pushings” through CRC register. Unfortunately, there aren’t unpaid lunches!
The cost is the next BS value calculation before A and CRC registers shifts:
BSnext = A initial byte xor CRC initial byte.
Note that there isn’t A message migration through CRC register and B register doesn’t exist.
Animation shows initial and first „double xor” state only. The remaining 7 „double xor” states imagine please only!
They are very similar (The „gearing” is 1:1 almost) to chapter 7.5.
Chapter 8.6 The „Right” table method with double xor for 8 bits shifts
I propose to return to chapter 7.4 for starters, to remind about similar 2 bits shifts method.
Fig. 8-5
The „Right” table method with double xor for 8 bits shifts ANIMATION
Fig. 8-5 is similar to Fig. 7-8 from chapter 7.4! The main „right” method advantage is the natural byte transmission. I.e. the left bit is older than the right. More–>chapter 7.6. The left bit of the quarterbyte is older than the right.
Conclusion. The bytes don’t need to be reverseed (swing around) before transmission.
But the other additional conditions must be fullfilled.
– A0 A1 …A7 bytes are reversed. So the transmission order is the same as in Fig. 8-4!
– The bits in A0 A1 …A7 bytes aren’t reversed
– 32 table bits are reversed towards bits in Fig. 8-4 table. For example The Fig. 8-4 left D7=11000111 byte converts to Fig. 8-5 right D7i=11100011. The remaining 71 76 8 bytes convert to reversed 71i 76i 8Ci analogously.
– initial CRC state is reversed too. It not mean diddly here because all CRC bits are 0.
Animation shows initial and first „double xor” state only. The remaining 7 „double xor” imagine please! The last state is „inverse CRC”. They are very similar to chapter 7.6.
Chapter. 8.7 CRC Software
Chapter 8.7.1 Introduction
The software is identical as Chapter. 7.7 CRC Software almost. The only difference is „8 bits instead of 2 bits”.
The message to send is in the A register. The tables were formed as in the chapter 8.3, but remember that the „right” table is some another than the „left” and „direct”. The table dimensions are 256×32 instead of. 4×8 as in Chapter. 7.7. I propose the tables program creation for more ambitious readers.
The certain pseudolanguage type will be used here.
Chapter 8.7.2 Direct table method for 8 bits shifts
BS CRC A B registers form common BS_CRC_A_B shift register.
Commands description:
Write message to CRC left – do 8 bits shifts left in BS_CRC_A_B (as in the animation)
While A is not empty – start of the loop
CRC=CRC xor table(BS) – CRC is xor-ed by the table value addressed by the BS
The program is very simple
B = 0
CRC=0
While A is not empty
{
Write message to CRC left
CRC=CRC xor table(BS)
}
When the loop is finished (i.e. A is empty) CRC contains ultimate value (calculated „remainder”)
Chapter 8.7.3 The „Left” table method with double xor for 8 bits shifts
The „zeroes” B register doesn’t exist here.
This program is some complicated than a previous-„direct”
CRC=0
While A is not empty
{
BS=8 initial BS bits xor 8 initial BS bits
Shift 8 bits A left
Shift 8 bits CRC left
CRC=CRC xor table(BS)
}
When the loop is finished (i.e. A is empty) CRC contains ultimate value (calculated „remainder”)
Chapter 8.7.4 The „Right” table method with double xor for 8 bits shifts
Remember about tables and CRC notes in the Chapter 7.6. Especially-The „quarter-bytes„ in A register are reversed but 2 bites in „quarter-bytes„ aren’t! In that programmer doesn’t need to reverse „quarter-bytes„ when send out via UART!
CRC=0
While A is not empty
{
BS=8 initial BS bits xor 8 initial BS bits
Shift 8 bits A right
Shift 8 bits CRC right
CRC=CRC xor table(BS)
}
reverse CRC
When the loop is finished (i.e. A is empty) CRC contains ultimate value (calculated „remainder”)