**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:

**and the memory**

CRC=01100101 a0b0c0d0e0f0g0h0 a1b1c1d1e1f1g1h1 a2b2c2d2e2f2g2h2

CRC=01100101 a0b0c0d0e0f0g0h0 a1b1c1d1e1f1g1h1 a2b2c2d2e2f2g2h2

**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

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
**

**method**

**Direct table****shifts**

**for 8 bits**

**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:

**BS**next =

**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

**table method with**

**„Right”****for**

**double xor****bits shifts**

**8**

**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

**r**

**ight**. 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 reverse**d. 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.

Write message to CRC left

CRC=CRC xor table(BS)

}

**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 bitsxor

BS=8 initial BS bits

**8 initial BS bits**

**Shift 8 bits A left**

Shift 8 bits CRC left

CRC=CRCxor

Shift 8 bits CRC left

CRC=CRC

**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

**. Especially-The**

**Chapter 7.6****“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 bitsxor

{

BS=8 initial BS bits

**8 initial BS bits**

Shift 8 bits A right

Shift 8 bits CRC right

CRC=CRCxor

Shift 8 bits A right

Shift 8 bits CRC right

CRC=CRC

**table(BS)**

}

reverse CRC

When the loop is finished (i.e. A is empty)

}

reverse CRC

**CRC**contains ultimate value (calculated “remainder”)