**How does CRC work?**

**Chapter 5 Calculating CRC on registers**

**Chapter 5.1 Introduction**You already know how to

**calculate**

**CRC**and it is much easier than simple

**decimal division**. The

**algorithm**is only

**shifts**and possibly

**xor-ing**. They can therefore be easily implemented on

**shift registers**supported by

**simple**logic based on

**xoring**.

**ig. 5-1**

**Chapter 5.2 CRC Calculation System**

** Rys. 5-1**

**CRC**Calculation System

**ANIMATION**

The system consists of

**“left” shift**registers

**BS**

**CRC A B**and a

**2×4 table register**used to modify the

**CRC**after the

**shift**. This is an electronic implementation of calculating the “remainder” of the “division”

**10101101:11001**i.e. the arithmetic of which is described in

**Chapter 4.4**. I would like to remind you that the

**A**register contains the “

**divisive**“, i.e. transmitted

**message**. It can be of

**any**length. Enter the

**animation**and figure out the action yourself. For your convenience, each

**state**of

**CRC**calculation is shown. But honestly, you can ignore it.

Each

**clock pulse**(“zegar”) shifts the contents of the

**BS CRC A B**registers to the

**left**.

The

**divider 11001**, or more precisely, only its

**4**lower bits

**1001**, is placed in the

**2**-element

**ROM**permanent

**memory**at address

**1**.

**At**address

**0**there is

**0000**.

After each shift, the

**xor**operation is performed:

When

**BS=1**then

**CRC=CRC xor 1001**

When

**BS=0**,

**CRC=CRC xor 0000**, i.e.

**CRC**is only

**shifted**

The

**CRC**is finally calculated when the

**A**and

**B**registers are

**empty**.

**Experiment**until everything is clear to you.

**Note:**

The

**animation**here is very precise, i.e. the

**shifting**and

**xoring**stages are separated. In the

**next**course

**examples**they are already

only

**one**common stage, which is, however, somewhat

**difficult**. Therefore, I appeal to you to

**thoroughly**understand the

**principle**of operation so as not to go into

**details**that are already

**understandable**later.

**Chapter 5.3 Shift register with linear feedback**

Otherwise known as **LFSR** Linear-Feedback Shift Register

This is a different implementation of the system from **Chapter 5.2**

Where does this name come from?** Shift** register because it **shifts**. **Feedback** because the signal in the register **reverses**. And linear?

Let it be like a old **riddle**.

What is this? It hangs on the wall, green and singing.

It’s obvious that a **herring**.

He **hangs** because they hanged him**Green** because they painted it

And he** sings** to make it harder to guess.

But seriously. This is a **shift register** in which the state **D3 D2 D1 D0** is a **linear** function of the previous state **D3 D2 D1 D0**. And the **linear** function is **xor**. And why is** xor** a linear function? Let’s give it a rest here.

Fig. 5-2**CRC** Calculation System as **LFSR** **ANIMATION**

How to build an **LFSR**?**1. Write** all the bits of the “divisor” except the highest one. Here **1001** because the “divisor” **is 11001****2. Under** each digit **1001**, place a **D-flip-flop-**memory element (you placed **D3 D2 D1 D0**)**3. Place** an **XOR** gate behind each **flip-flop** that has a **1** above it**4. Connect** everything as in **Fig. 5-2**

This is how you designed the **LFSR** register. Enter the animation and after subsequent** clicks** – clock pulses, the** LFSR** register will calculate the “remainder of division” **10101101**, i.e. the number located in register **A**. That is, **LFSR** calculates the** CRC** from the message located in register **A** of any **length** – usually a **multiple** of a **byte**.

Similarly, you build registers for other than **1001** “dividers”.

The beginning of the animation is easy, because the “lower” **xor** inputs are **0**. The data is only moved. Then, this pleasant analysis is disturbed by **1** states that may appear at the inputs of the **xors**.**Note** that the **animation **comments in the clouds of that make it easier to analyze the action are in the **future**:

– I’ll just move it because **D3=0**

– I will **shift** and **xor** because **D3=1**

Try to predict the next state **D3 D2 D1 D0** after clicking the** clock**.

**Chapter 5.4 Transmitter-Receiver transmission example**There is an implementation of the algorithm from

**Chapter 4.4**when we add

**0000**to the dividend

Fig. 5-3**Transmitter-Receiver** Transmission **ANIMATION**

Our goals are to transfer information from the **RN** in the **transmitter** to the **RO** in the **receiver**. In addition, the **receiver** must know that **most likely** there were **no** errors during **transmission**. For this purpose, there are **CRC-N** and **CRC-O** registers in the **transmitter** and **receiver**, which calculate the **CRC** independently of each other. It can be implemented as **CRC**, **BS** and **ROM** (Read Only Memory) of **Fig. 5-1** or **LFSR** of **Fig. 5-2**. By the way. Messages such as **RN–>CRC-N** or** RN–>CRC**-0 appear in the animation clouds. However, this is not a simple transfer, but a transfer plus calculation of a new** CRC** as in **Fig.** **5-1** or **Fig. 5-2**!**Stage 1** **RN–>RO** transmission + **CRC calculation** in **CRC-N** and** CRC-O**.**Step 2 completes** the **CRC calculation** in **CRC-N** and **CRC-O** (“pushing” **0000** into these registers).**Stage 3** **CRC-N –> CRC-O** transmission and their comparison. If they are the same, the transmission is correct.**Note**

In a real **transmission**, the message being sent, i.e. the content of the **RN**, can be **thousands of bytes** long!

**Chapter 5.5 Example of Transmitter-Receiver transmission “with the remainder added”**

There is an implementation of the algorithm from **Chapter 4.5** when we add **1001** to the dividend, i.e. the final **remainder**

Fig. 5-4

Fig. 5-4

**Transmitter-Receiver**transmission “with the rest added”

**ANIMATION**

Weird? Register

**B=0000**and it should be

**B=1001**because this is the rest added! What’s more, the drawing is the same as

**Fig. 5-3**! The matter is obvious.

**Stage 1**is exactly the same as in the

**previous**chapter. In the initial state

**B =0000**because the transmitter does not yet know what the

**CRC**is. Until these

**zeros**“reach”

**CRC-N**and

**CRC-0**, they have no effect on

**CRC-N**and

**CRC-0**. At the end of

**stage 1**, the receiver will remember the

**CRC**-state

**O**in the copy

**register**in order to “remember” it at the end of stage 2. You will see the copy register in the animation. The algorithm will continue as in

**Chapter 4.5**, as if it had been

**B=1001**from the very beginning. The final state will be

**CRC-O=0000**, i.e. the transmission was

**error-free**.

**Chapter 5.6 Software, i.e. a program that calculates CRC**If you are not a programmer, you can skip this chapter. But at least try

The program is written in a

**pseudo-language**that is understandable to everyone. The

**reader-programmer**can easily replace it with his favorite language, e.g.

**C**or

**assembler**. This note also applies to the

**following chapters**.

The **BS CRC A B** registers in **Fig. 5-1** form the common** shift register** **BS_CRC_A_B**. The **Write A to CRC Left** instruction of our **pseudo-language** not only writes the initial bit from **A** to the **CRC**, but also shifts the entire **BS_CRC_A_B** register by **1** bit to the left. After each **shift**, the **one-bit BS** register is examined and the **CRC** is **xor**-ed with the **table row** pointed to by the **BS**. After entering the last bit from **A** to the** CRC**, register **A** is empty and this means that the program ends. Then the **CRC** contains the calculated **remainder.**

**Table** memory description:**Array(0)=0000****Array(1)=1001=generator** i.e. all the “divisor”** bits** except the **oldest** one.

In our case, also concerning **chapter 4.4**, **“divisor”=1 1001** i.e. **generator=1001.**

A program in a **pseudo-language****Write a message to A****Put zeros in B****Until CRC is not empty****{ Write A into CRC left****CRC=CRC xor array(BS) }**

For **BS=0** we have **CRC=CRC xor array(BS=0)=CRCxor0000=CRC** so there is only an **byte move**.**Therefore**, the **program** can also be presented in the **equivalent** form:

**Write a message to A****Put zeros in B****Until CRC is not empty****{ Enter A into CRC****if BS=1 then CRC=CRC xor generator }**

This version is probably even more clear.

The program will end when it exits the loop.

Then all bits **A B** will go through the** CRC** and **A** will become “empty”*****. This means that the **CRC** contains the calculated “remainder”.***Note** “Empty” **A **that’s not necessarily **0000**! They’re just bits that don’t matter to us anymore.