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
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 1 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(1)=1001 as 4 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
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.
LFSR as Register CRC Calculator realization ANIMATION
1. Write 1001 as poly bits
2. Locate D type flip-flops under 1001. (D3 D2 D1 D0 flip-flops located)
3. Locate xor gate before the D flip-flop “with 1 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
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 3 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.
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.
Transmitter–>Receiver transmission when “CRC” appended ANIMATION
Strangely! The initial register B=0000, but it should be B=1001 as the initial B 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-N, CRC-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- C 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(1)=1001,<–poly i.e. the 4 lower 1 1001 factor bits
Program in pseudolanguage
Write “0000” to B
While CRC isn’t empty
CRC=CRC xor table(BS) }
The program is finished when when A 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 “0000” to B
While CRC isn’t empty
if BS=1 then CRC=CRC xor poly}