**How does CRC work?**

**Chapter 7 What if we shifted by 2 bits?****Chapter 7.1 Introduction**We know from the previous chapter that the actual

**CRC**register is

**1, 2,**or

**4**bytes long. And what else is it different from the one in

**chapter 5**? First of all,

**shifts**. In earlier chapters they were

**bit-based**, and the ones commonly used by programmers are

**byte-based**. Usually, when a program wants to send e.g.

**100**bytes, it enters them

**byte by byte**into the so-called

**UART**, which itself sends them

**bit**by

**bit**to the network. And how it does this is the

**job**of a

**UART**-type chip designed by some guy several

**dozen years ago**. This means that the program sending

**1**byte must also calculate the

**CRC**state after

**8**bit

**shifts**! The

**first**thing that comes to mind is a program that performed

**8**

**one-bit shifts**according to:

**Chapter 5.2**. This is rather a

**time-consuming**and transmission-delaying

**SIMPLE**method that is not used in practice. This

**disadvantage**does not have the commonly used so-called

**array methods**. Unfortunately, the large dimensions of these boards,

**256×8**and even

**256×32**, make it difficult to understand the principle of operation. Therefore, we will

**first**learn about

**CRC**methods for

**2-bit shifts**. The boards here are small in size

**4×8**and are easier to analyze. Then you will easily understand in

**Chapter**.

**8**“real” array

**CRC methods**.

**Chapter 7.2 Single Byte CRC Calculator with 1-bit Shift**

Fig. 7-1**Single Byte** Bit Shift **CRC** Calculator **ANIMATION**

This is a version of the system that is more close to reality in **Chapter 5.2**. Instead of a **4-bit CRC**, we have an **8-bit** one and instead of **1** byte of transmitted information (or “divisive”), there are **2** bytes in the **A** register. In real networked systems (and not just in this course), there can be** thousands** of these bytes in register** A**, not just **2**! The “**divisor**” is** 1 10010101**, of which the** 8** lower bits are, as usual, placed at address **1** in a **2×8** array. We see that the **CRC** calculation method we have learned so far is also an array! And with a pretty serious **2×8** array!

Click on the **animation** and see how** CRC** is calculated using the current **bit**-by-**bit** method, i.e. **SIMPLE **method. The next examples in this chapter will be a modification of it with a **2-bit** shift and an **8-bi**t shift in **Chapter 8**. In this chapter, “**Divisible**“, i.e. the information sent, and “**Divisor**” will be the same in all animations. So the final result should always be **CRC=11100110**.

However, in** Chapter 7.6** is a different **CRC** and I don’t know why! I’m counting on readers’ help here.

**Chapter 7.3 What is the CRC after a 2-bit shift?****Chapter 7.3.1 Introduction**

We already know what the** CRC** state will be after a **1-bit shift**. So we can also predict the state after the **next 1-bit** shift, i.e. after a total of **2 bit shifts**. Therefore, we will examine the **CRC** after a **2-bit shift** for all possible combinations of the **2 bits** of the initial** CRC** registers, i.e. **00, 01, 10** and **11**.**Chapter 7.3.2 CRC with 2-bit shift when the first 2 bits are 00**

Fig. 7-2

The initial state when the **first 2 CRC** bits are** 00** **ANIMATION**

In this case, the matter is trivial. The **abcdefgh** bits will only be **shifted** because after each shift **BS=0**.

This means that the **CRC** will be **xor-ed** with a **zero** value and this operation changes **nothing**.**Fig. 7-2a** shows the initial state of the **CRC** as the **bits** between the **red** lines. The animation shows that operations on registers are accompanied by appropriate **xor**izations with **zero** lines, the result of which is the **xor**ization of all lines between the **red** lines.**Fig. 7-2b** shows the principle that any logical **product** with **negations** can be represented as a **product** without negation **xor-ed** with the appropriate **bit** **number**. This number has **bit=1** in the position where the product has a **negated** (“capped”) value. Remember this rule!**Fig. 7-2c** shows the **CRC** status after **2** shifts as **CRC=abcdefgh xor 00000000**.**Ch. 7.3.3 CRC with 2-bit shift when the first 2 bits are 01**

Fig. 7-3

Fig. 7-3

**The initia**l state when the

**first 2 bits**of the

**CRC**are 01

**ANIMATION**

In

**Chapter 7.3.2**predicting the

**CRC state**was

**trivial**because there were only

**shifts**. Now the initial state is

**CRC=01abcdef**. The

**gh**bits are waiting in memory

**A**. The remaining bits of memory

**A**are of no interest to us for obvious reasons. After all, they will not affect the CRC status after

**2 shifts**.

Now the state of

**BS=1**will appear and it won’t be so nice. You can predict the state after

**2**shifts using

**2 methods**:

**1. Using animation**. And since you know the rules, you are able to do it “in your head”.

**2. By the calculating**method, i.e. “in your head”. Figure it out yourself using animations. If this fails, the method is as follows:

**– Write**

**01abcdefgh**. Separate the initial state of the

**CRC**register, i.e.

**01abcdef**, with red lines as in

**Fig. 7-3a**. Next

**BS=0**because the first

**CRC**bit is

**0**

**– Write**the shifted

**00000000**above the initial state because

**BS=0**. Now the new

**CRC**state is

**xor 2**lines between the

**red**lines. You don’t have to calculate it for now, but check for your own satisfaction whether it is like in the

**animation**. Next

**BS=1**as the

**xor**of the

**first**column between the

**red**lines

**– Write**the shifted

**1001010**1 because

**BS=1**. The new and final state of the CRC is

**xor 3 lines**between the red lines, i.e.

**CRC=abcdefgh**xor 10010101 as in

**Fig. 7-3b**

After

**2**shifts,

**CRC=abcdefgh xor 10010101**.

**Comments**:

– In the

**CRC**formula, the value

**10010101**after the

**xor**symbol is the xor

**2**lines above

**abcdefgh**after the

**second shift**

**– After**the second shift,

**“hats”**appeared over the symbols

**a, d, f**and

**h**–>

**Fig. 7-3b**, which means that these values have been

**negated**.

**Chapter 7.3.4 CRC with 2-bit shift when the first 2 bits are 10**

Fig. 7-4

The initial state when the **first 2 CRC** bits are **10** **ANIMATION**

After** 2** shifts, **CRC=abcdefgh xor 10111111**.**Ch. 7.3.5 CRC with 2-bit shift when the first 2 bits are 11**

Fig. 7-5

The** initial state** when the first **2 CRC** bits are **11** **ANIMATION**

After **2** shifts, **CRC=abcdefgh xor 00101010**

**Chapter 7.3.6 Table as a summary of this chapter**

The above

**subchapters**show that knowing the

**2**starting

**bits**of the

**CRC**, we can immediately

**calculate**its

**new state**after the

**shifts**using appropriate

**xoring**s.

**When**the first

**2 bits**:

**– 00**is the next

**CRC=CRC xor 00000000**

**– 01**is the next

**CRC=CRC xor 10010101**

**– 10**is the next

**CRC=CRC xor 10111111**

**– 11**is the next

**CRC=CRC xor 00101010**

This corresponds to a

**4×8 array**with

**4**addresses

**00, 01, 10**and

**11**in

**Fig. 7-6**. The

**current**state of the

**2-bit**

**BS**register indicates the line through which the

**CRC**should be

**xor**ed to hold the

**new state**after

**the 2-bit shift**. There is some analogy here to

**Fig. 7-1**with a

**1-bit**

**shift**and a

**2-row array**.

Chapter 7.4 Direct array method for 2-bit shifts

Chapter 7.4 Direct array method for 2-bit shifts

**First**, about the method name

**I**proposed.

**Array**-because it uses

**arrays**, just like the

**1-bi**t shift method, e.g. in

**Fig. 7-1**. And

**direct**? Because it is based on the

**arithmetic**from

**Chapter 4.4**with the

**addition**of

**zeros**and its register implementation in

**Fig. 7-1**. Another

**justification**may be

**single xoring**, and not

**double**as in

**chapters 7.5 and 7.6**.

Fig. 7-6**Direct** array method **for 2-bit** shifts **ANIMATION**

A** 2-byte message** from register **A** passes through the **CRC** register in **2-bit steps**. Finally, a **byte** with** zeros** from the **B** register is transferred in the same way. I would like to remind you that the **BS, CRC, A, B** registers can be treated as one **common** register **BS_CRC_A_B** in which the data is shifted by **2 bits** to the** left** in each **clock pulse**. Each** shift** is accompanied by **xori**ng of the data from the **CRC** with the data indicated by the **BS**. Even if **BS=00**, this is also **xor**ing, but this operation** does not** change anything.

In** chapter 8**, you will find that these actions closely resemble **8-bit** shifts. Except that **2** bits correspond perfectly to **8 bits** and the “ratio” is almost** 1:1**. And why “almost”? Because the array will have** 256** addresses as an **8-bit BS** gives **256** different bit combinations.**Chapter 7.5 “Left” array method with double xoring for 2-bit shifts** Array – you know,

**“left”**because the

**bits**shift to the

**left**, and “

**double xoring**” you will know in a moment.

Fig. 7-7**Double-xo**red **“left” array** method **for 2-bit** shifts **ANIMATION**

In the** direct** method, **2 bits** directly passed from** CRC** to **BS**. Here they also go from **CRC** to **BS** but are additionally **xor-ed** with the **initial 2** bits from memory **A**. Message** A** bypasses the **CRC** here, otherwise it does not go through the** CRC**. Note that thanks to this principle, the** B** register with **zeros** and the initial “empty” trace with zeros disappear as in **Chapter. 7.4**. This is probably “elegant”, although at the cost of additional **CRC** xoring through the** data** from message **A**. I have mixed feelings here. After all, register** A** is in practice **thousands** of **bytes**. This means that the “empty” trace and the **B** register have no effect on the **transmission**. Perhaps this additional xoring occurs in the same cycle as the single xoring from **Chapter 7.4** and therefore does not affect the transmission **speed**. And this is probably the case, because the **direct method** is not used in practice, or is used less often. In the **animation** you will see that the calculated final **CRC=11100110** is of course the same as in **Chapter 7.2** and** 7.4**!

Chapter 7.6 Double-xored “right” array method for 2-bit shifts

The name speaks for itself.

Fig. 7-8**“Right”** double-xored array method **for 2-bit shifts ANIMATION**

What’s the point if the previous method seems to be unchallenged? Return for a moment to **Chapter 7.1**. It was mentioned that all bits going outside, i.e. to the network, pass through the so-called** UART**. And this one most often (or maybe always?) treats the **right** bits as **more significan**t. So, for example, **byte =** **00000001** will be treated as **128,** and **byte = 10000000** as **1**. The opposite of what we are used to.** Too bad**, these **UARTs** were designed about **50 years** ago and there’s nothing we can do about it. And we want **00000001** to be treated as **1**. For example, you can modify the **“left”** method to “rotate” each byte before sending and everything will be** OK**. It turns out that, **first of all**, not every microprocessor has such a simple, seemingly **simple command**. And secondly, if you already have it, it takes some time to make it. And this **delays** the **transmission**! And that’s what the “**right”** method is for. Here, the data of the entered **quarter byte** is “human”, i.e. the **left** bit is more important than the **right** one. In the initial state in **Fig. 7-7**, the first **quarter byte** introduced to the network and to the** BS** modifying the **CRC** is **10**, i.e. **2**, not **1**! So the entire byte with **A=01101010** will be treated by** UART** as **10101001** from **Chapter 7.5**. And that’s what we wanted!

But **three** additional conditions must be met:**1. All row**s in the array must be** “rotated”** about the **central axis**.**2. The initia**l state of the **CRC** register must also be **“rotated”.****3. The calculated** final **CRC** is also **“rotated”**.**ad. 1,** for example, line **3** **11111101** is “rotated” relative to line **3** **10111111** from **Chapter 7.5****ad. 2** here the initial **CRC=00000000** is “rotated” relative to **CRC=00000000** from **Chapter7.5**. In the case of **zero** **CRC**, “rotating” changes nothing, but there are** CRC** algorithms that have a **non-zero** starting **CRC**.

Make an **animation** and you will see that the calculated** CRC** will be the same as in **Chapters 7.2** and **7.4**, i.e.** CRC=11100110**. After all, the input messages **A=10101001 00011001** are the same, and the arrays in **Chapter 7.4** and **7.5** were built on the same base–>**“divisor”=10010101** from **Chapter 7.2**!

But nothing like that!! **CRC=10010101** is different than in** Chapter** **7.2** and** 7.4**. And this is the **original sin** of this course. Now I’m counting on help from readers smarter than me. I give the first person who points out the error and calculates with the “right” method that** CRC=11100110** an eight-pack of good beer! Please just send your bank account number by email. It’s not a **Nobel Prize**, but this one had a bit more potential.

**Chapter 7.7 Software, i.e. a program that calculates CRC****Chapter 7.7.1 Introduction**

The message to be sent is in register **A**. The arrays were created based on **Chapter 7.4**, except that the **“right”** array (**chapter 7.6**) is slightly different than the **“left”** and **“direct”** arrays. I leave the **array building** programs themselves to more ambitious readers. A kind of** pseudo-language** is used that requires almost no comment.**Chapter 7.7.2 Program for the direct array method with 2-bit shifts**

The **BS CRC A B** registers in F**ig.7-6** form the common **shift register** **BS_CRC_A_B**. The **Write 2 bits from A to CRC left** instruction of our **pseudo-language** not only writes the **initial 2 bit**s from **A** to **CRC,** but also **shifts** the entire **BS_CRC_A_B** register **2 bits** to the** left**. The **CRC** is then **xor-ed** by the** array row** pointed to by the **BS**.**B=0****As long as A is not empty****{ Write 2 bits from A to CRC to the left****CRC=CRC xor array(BS) }**

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

There is no “zero”** B** register**As long as A is not empty****{****BS=2 starting bits A xor 2 starting CRC bits****Shift A 2 bits to the left****Shift CRC 2 bits to the left****CRC=CRC xor array(BS)**

}

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

Remember the notes regarding the **array** and** CRC** in **Chapter. 7.6**! Especially since the **quarter bytes** in** A** are “rotated”, but the bits in the **quarter bytes** are not! This saves the programmer from having to “rotate” each **quarter byte** before sending it to the UART.**As long as A is not empty****{****BS=2 starting bits A xor 2 starting CRC bits****Shift A 2 bits to the right****Shift CRC 2 bits to the right****CRC=CRC xor array(BS)****}****Rotate CRC****After exiting the loop, the CRC will contain the calculated CRC or “rest”.**