**How does CRC work?**

**Chapter 8 What if we shifted by 8 bits?**

**Chapter 8.1 Introduction**

You will find that

**8-bit shifts**are very similar to the

**2-bit shifts**from the previous

**chapter**. The ratio is almost

**1:1**, i.e. instead of

**2-bit shifts**, they are

**8-bit**, and the

**CRC**itself can be

**8**,

**16**or

**32**bits. We will replace the

**4×8**array with a

**256×8, 256×16 or 256×32**array. Due to their large size, it is difficult to animate them. However, thanks to the analogy with

**2-bit**shifts, the incomplete animation of

**8-bit**shifts that I will propose will easily allow us to imagine how the system works.

**Chapter 8.2 What is the CRC after an 8-bit shift?**

This is equivalent to **Chapter 7.3 What is the CRC after a 2-bit shift**

Fig. 8-1

Fig. 8-1

What is the

**CRC**after an

**8-bit**shift?

**ANIMATION**

In

**Chapter 7.3**we examined the state of the

**8-bit CRC**after a

**2-bit shift**for all

**4**possible

**combinations**of the

**2**initial states of the

**CRC register**:

**00.01, 10**or

**11**. Here these combinations will be

**00000000, 00000001, 00000010….11111110 and 11111111**. In total

**256**combinations, so our array should have a size of

**256×8**.

So let’s start determining these

**final states**. The bottom line of the

**array**in

**Fig. 8-1**is the

**8**lower

**bits**of the

**“divisor”=1 10010101**. On its basis, a

**256×8**array for

**8-bit shifts**will be built.

We start with the

**easiest initial state**, i.e.

**00000000**. It is obvious that the

**abcdefgh**bits will only be

**shifted**, i.e. their final state will be

**abcdefgh**, otherwise

**abcdefgh xor 00000000**.

This way we have designated the

**first**row of our

**array=00000000**.

And how to determine the

**rows**for the remaining

**255**combinations? For obvious reasons, we will not do this and will limit ourselves to only

**one**initial combination, e.g.

**10111010**, i.e. for the

**array**row with the

**binary**number

**10111010**. The remaining

**254**array

**rows**can be determined in the same way.

To the final state after

**8**shifts:

**CRC=abcdefgh xor 00111000**–>see

**Note**

that is, we can get to the line with the binary number

**10111010**of our array in two ways:

**– trus**t our animation machine, which always works the same as before and after

**8 clicks**we will reach the state

**CRC=00111000**

**– numericall**y, i.e. move the

**red**lines to the right and

**xor**-row the content between the

**red**lines by:

**–>00000000**when previous

**BS=0**

**–>10010101**when previous

**BS=1**

Initial

**BS=1**as the

**first**bit of the

**initial**state

**CRC=10010101**

Next

**BS**is the

**xor**of the column at the

**left red**line.

Phew! It sounds quite confusing and complicated, but it’s best if you figure it out yourself by clicking on the clock!

**Note:**

**00111000**is

**xor 8**lines between the

**red**lines that will appear at the end of the animation.

**Chapter 8.3 32-bit CRC with 8-bit shift**

Fig. 8-2**32 bit CRC** with **8** bit **shift** **ANIMATION**

From **Chapter 6**, we know that the **error detection** ability depends on the** size** of the** CRC**. Commonly used on the Internet, **32-bit CRC** has much greater error detection power than **8-bit CRC**. Shifts, however, remain** 8-bit**.

The generator of our **CRC** (i.e. the **“divisor”** without the first **bit=1**) is the bottom row of the array, i.e.:**generator=array(1)=01101100 10000001 00011101 10110111**

The** initial** state of the system is:**CRC=01100101 a0b0c0d0e0f0g0h0 a1b1c1d1e1f1g1h1 a2b2c2d2e2f2g2h2**

and the** first byte** of memory **A** “waiting” for an **8-bit shift**, i.e. **A=a3b3c3d3e3f3g3h3**

Using** bytes** and **hex numbers****65=01100101 C0=a0b0c0d0e0f0g0h0 C1=a1b1c1d1e1f1g1h1 C2=a2b2c2d2e2f2g2h2 C3=a3b3c3d3e3f3g3h3**

we can write it more **concisely**:**generator=array(1)=6C 81 1D B**

The **initial** state of the system is:**CRC=65 C0 C1 C2****A=C3**What will be the

**CRC**after

**8 bi**t shifts with the starting byte

**CRC=01100101**as in

**Fig. 8-2**?

From the

**animation**and

**independently**from the

**“xor**ing

**“**between

**red**lines” it follows that it will be:

**CRC=C0 C1 C2 C3 xor D7 71 76 8C**

Where:

**D7 71 76 8C is 11010111 01110001 01110110 10001100**

**C0 C1 C2 C3**then see above.

And this means that for generator=

**6C 81 1D B7**

**array(65)=D7 71 76 8C**

**array(00)=00 00 00 00**–>obvious because

**BS=0,**so there are only

**shifts!**

In a

**similar**way, we will determine the remaining

**254 rows**of the

**256×32**array.

**Chapter 8.4 Direct array method for 8-bit shifts**

Before you start examining the system, go back to** Chapter 7.3** and recall how this method works for** 2-bit shifts**.

Fig. 8-3**Direct** **array** method for **8-bit** shifts **ANIMATION**

Even **Fig. 8-3** is similar to** Fig. 7-3** from **Chapter 7.3**!

The analogies are as follows:**Fig. 7-3**

– **CRC** is **1 byte**

–** 2** byte **A** memory divided into **4 quarter bytes** in each of **2** lines**– the** **first** quarter **byte** of the **first** line of memory** A** is **10****– single**-byte **B** memory with **4 zero quarter bytes****– 4 byte** array, each **byte** divided into **4 quarter-bytes****Fig. 8-4****– CRC** is **4 bytes****– 8-byte A** memory divided into **4 bytes** in each of **2 lines****– the first** byte of the **first** line of memory **A** is **0x65**, i.e. **011001010****– 4 byte B** memory with **4** **zero bytes****– 256×4** **byte array** in which each of the **256** lines is divided into **4 bytes**

From **Chapter 8.3** shows that in the array at address:**– 0x00 is 00 00 00 00** (4 zero bytes)**– 0x65 is D7 71 76 8C**

The remaining **254** **4 byte** rows of the **array** can of course be calculated, but I gave up.

The animation shows that the waveforms are similar to those in **Chapter 7.4** only **shifts** are **byte**, not** quarter byte**. The animation finished on the **7th** clock **pulse**, then returns to the** initial** state. The **first 4** states are simple **shifts** because **BS=00**. In the **fifth** state, the **4-byte CRC** is **xor**ed, the content indicated by** BS=65**, i.e. by **D7 71 76 8C**. Therefore, bytes **A1 A2 A3** and** A4** of the **CRC** register will change to **A1* A2* A3* A4***. This is where the animation ends and returns to its initial state. The remaining states of the animation, i.e.** 7** **double xor**s through the contents of the table indicated by **BS** and “pushing” the **CRC** with **4** zero **bytes**, you must imagine using** chapter 7.4**. Just remember that the equivalent of **bytes** here are **quarterbytes**, i.e. **2 bits**.

**Chapter 8.5 Left-hand double-xored array method for 8-bit shifts**

Return to** Chapter 7.4** and recall how this method works for **2-bit shifts**. The operations in both methods are similar.

Fig. 8-4**“Left” double-xored array** method for **8-bit** shifts **ANIMATION****Fig. 8-4** is similar to** Fig. 7-4** from **Chapter 7.5**!

In this method, the next **BS** byte value i.e.** BSnext** is calculated as the starting **A** **byte** xor **the starting CRC byte**. This **avoids** the initial “empty” pushing of messages from **A** through the **CRC** register, and there is no **zero 4-byte B** memory, which we remember was “pushed” at the end of the cycle by the **CRC** register.

The **animation** shows only the** initial** state and the first “double xoring”. You must imagine the remaining animation states, i.e.** 7 “double xor-ings”**, using** 2-bit shifts** in **chapter 7.5**.

Unlike the direct method in **Chapter 8.4**, the message from **A** does not pass through the **CRC** serially, i.e. the** starting byte** from **A** is not inserted into the **lowest byte** of the **CRC**.

**Chapter 8.6 Double-xored “right” array method for 8-bit shifts**

Return to **Chapter 7.6** and recall how this method works for **2-bit shifts**. The operations in both methods are similar.

**Fig. 8-5****Double-xored “right” array** method for **8-bit** shifts **ANIMATION****Fig. 8-5** is similar to** Fig. 7-5** from **Chapter 7.4**! The main advantage of the **“right”** method is the ability to send** bytes** to the network in the most natural form possible. I.e. one in which the **left bit** is **higher**. More on this topic in **chapter 7.6** in which the** left bit** in the **quarter byte** is **higher**. Sum sumarum- bits in bytes do not need to be reversed before being sent to the network.

For this to happen in the “**right”** method, the following conditions must be met:**– bytes A0 A1 …A7** are set in the opposite positions than in **Fig. 8-4** so that they are sent in the same order as in **Fig. 8-4****– the bits** in bytes** A0 A1 …A7**, however, have the same order as in **Fig. 8-4**!**– 32 bits** in the array are “rotated” relative to the **center axis** of the array. In this way, for example, the** 8 left** bits** D7=11000111** in the array in **Fig. 8-4** become the right “rotated” **bits D7i=11100011**. This note also applies to bytes **71 76 8C** which also become “rotated” **71i 76i 8Ci.****– the initial** state of the **CRC** should also be “rotated”. It doesn’t matter here because the **initial** state is **zero**. But it can also be **non-zero** and then it matters.

Only the **initial state** and the first **“double xoring”** are included in the animation. You must imagine the remaining animation states, i.e. **3 “double xor**ing**“** using **2-bit** shifts in** chapter 7.6**.

**Chapter 8.7 Software, i.e. a program that calculates CRC**

This **chapter** is equivalent to **Chapter 7.7**. The only difference is **byte shifts** instead of **quarter-byte** (two-bit) **shifts**. Just replace the expression **“2 bits”** with **“8 bits”** in the instructions. Also remember that the arrays have different sizes.**Chapter 8.7.1 Program for the direct array method with 8-bit shifts**

The **BS CRC A B** registers in **Fig.8-3** form the common** shift register** **BS_CRC_A_B**. The **Write 8 bits from A to CRC left** instruction of our **pseudo-language** not only writes the initial** 8 bits** from **A** to **CRC**, but also shifts the entire **BS_CRC_A_B** register **8 bits** to the left. The** CRC** is then** xor**ed by the array row pointed to by the** BS**.**A program** in a pseudo-language**Write a message to A****Put zeros in B****As long as A is not empty****{ Write 8 bits from A to CRC to the left****CRC=CRC xor array(BS) }**

After exiting the loop, the **CRC** will contain the calculated **“remainder”**.**Chapter 8.7.2 Program for the “left” array method with double xoring and 8-bit shifts**

There is no **zero B byte**. The common **left shift register** is formed only by **BS_A**. So **A** does not pass through **CRC** as in the previous example, but the** CRC** itself is also, of course, **shifted 8** bits to the **left**.

After each **8-bit** **left** shift of the common register **BS_A**, the **BS** is calculated:**BS=8** starting bits** A xor 8 **starting** CRC bits**.

The **CRC** is then **xor**-ed by the **array** row pointed to by the **BS**.

**A program** in a pseudo-language**Write a message to A****As long as A is not empty****{ Shift BS_A 8 bits left****BS=8 starting bits A xor 8 starting CRC bits****CRC=CRC xor array(BS) }**

After exiting the loop, the** CRC** will contain the calculated** “remainder”**.**Chapter 8.7.3 Program for the “right” array method with double xoring and 8-bit shifts**

The program** differs** from the previous one only by **shifting** to the **right**. However, remember the notes regarding the** array** and **CRC** in **Fig. 8-5**! Also the bytes in **A** are **“rotated”** about the **central axis,** but the **bits** in the** bytes** are not! This saves the programmer from having to “rotate” each **byte** before sending it to the** UART**.

A program in a** pseudo-language**

Write a message to **A****As long as A is not empty****{ Shift BS_A 8 bits to the right****BS=8 starting bits A xor 8 starting CRC bits****CRC=CRC xor array(BS) }****Rotate CRC**After exiting the loop, you need to rotate the

**CRC**again.