How does CRC work?

Chapter 5 Register CRC Calculators

Chapter 5.1 Introduction
It’s easy to realise the known CRC algorithm (see Chapter 4) with the aid of registers. There are shifts and xor operation only!

Chapter 5.2 Register CRC Calculator


Fig. 5-1
Register CRC Calculator   ANIMATION
System consists of the shift left registers BS CRC A B and the table 2×4 for CRC modification.  Treat BS CRC A B as a common shift left register. It’s accurate electronical CRC calculation method realization–>see Chapter 4.5. The added CRC “shif and xor” calculations form the evidence for it.
Please work algorithm out yourself.
The table description:
table(0)=0000
table(1)=1001 as last 11001 factor. The other 1001 name is a poly.

Every “clock-zegar” pulse shifts left the BS CRC A B registers.
The xor operation is done after each pulse:
if BS=1 then CRC=CRC xor 1001
if BS=0 then CRC=CRC xor 0000 other words CRC is shifted only
Attention:
Animation is very accurate. I.e. shift and xor phases are separated now. These phases will be combined in the next animations.

Chapter 5.3 LFSR Linear-Feedback Shift Register
This is other Chapter 5.2 realization.


Fig. 5-2
LFSR
as Register CRC Calculator realization   ANIMATION
1. Write 1001 as poly bits
2. Locate type flip-flops under 1001. (D3 D2 D1 D0 flip-flops located)
3. Locate xor gate before the flip-flop “with bit” (xor located before D3 D0)
4. Connect all the elements by lines as in Fig. 5-2
System calculates CRC.
Clouds comments facilitate system work analysis.  They predict the future D3 D2 D1 D0 state.
– Next state shift only because D3=0
– Next state shift and xor because D3=1
Try to predict the next D3 D2 D1 D0 state after “zegar-clok” clicking.

Chapter 5.4 Transmitter–>Receiver transmission when “0000” appended
This is Chapter 4.4 transmission realization


Fig. 5-3
Transmitter–>Receiver transmission when “0000” appended   ANIMATION
The appropriate information from the RN transmitter register will be sent to the the RO receiver register.  The receiver should know that the received information in the RO receiver is probably the same as send by RN. I bring the word probably out. There aren’t absolutely sure methods. The better is CRC method, the probability is near 100%, but is never equal 100%! The CRC-N and CRC-O are registers CRC calculators and  realized as chapter 5.2 or chapter 5.3. They work independently.
The “clouds” statements RN–>CRC-N or RN–>CRC-0 isn’t common  transfer but transfer + new CRC value update.
There are transmission phases.
Phase 1-RN–>RO transmission and CRC-N and CRC-O actualizations.
Phase 2 CRC-N and CRC-O actualization completion (“0000” is forced to CRC-N and CRC-O)
Phase 3 CRC-N –> CRC-O transmission and comparison.
Note
The real send message i.e. RN contents are thousands bytes!

Chapter 5.5 Transmitter–>Receiver transmission when “CRC” appended
This is Chapter 4.5 transmission realization when the calculated “rest”=CRC is appended.


Fig. 5-4
Transmitter–>Receiver transmission when “CRC” appended  ANIMATION
Strangely! The initial register B=0000, but it should be B=1001 as the initial in the Chapter 4.5. What is more. The Fig. 5-4 is identical as  Fig. 5-3. It’s obvious. Phase 1 is identical as in the  Chapter 4.5. The initial B=0000 because transmitter doesn’t know yet the ultimate calculated CRC value! The phase 1 is identical as in the previous chapter because four zeroes “0000” haven’t reached CRC-NCRC-O yet. The receiver remembers the CRC-O state in his copy register at the end of the phase 1. Why? This value will be necessary at the end of the phase 2. The algorithm will go as in the Chapter 4.5 then.  It looks like the initial register B=1001. The ultimate CRC-O=0000 means that transmission was ok.

Chapter. 5.6 Software i.e CRC program.
Program has to be easy for everybody so the pseudolanguage is used. The reader-programmer changes it without any trouble for his favourite lanuage- or assembler for example.
Registers  BS CRC A B –> Fig. 5-1 form common BS_CRC_A_B shift register .
Write_message_A_to_CRC command shifts left all the BS_CRC_A_B shift register.
Other commands are obvious.

The BS 1 bit register is tested and:
if BS=0 then CRC=CRC xor table(0)
if BS=1
then CRC=CRC xor table(1)
table
description
dimension 2×4
table(0)=0000
table(1)=1001,<–poly i.e. the lower 1 1001 factor bits

Program in pseudolanguage
Write_message_A_to_CRC
Write “0000” to B
While CRC isn’t empty
{ Write_message_A_to_CRC
CRC=CRC xor table(BS) }
The  program is finished when when  is empty. CRC contains ultimate calculated “rest” then.

For BS=0 CRC= CRC xor  tablica(BS=0) = CRC xor 0000 = CRC. There is shift only.
So the equivalent simpler version:
Write_message_A_to_CRC
Write “0000” to B
While CRC isn’t empty
{ Write_message_A_to_CRC
if BS=1 then CRC=CRC xor poly} 

(poly=1001)

Leave a Reply

Your email address will not be published. Required fields are marked *