Compression - CRC and checksum

Author

CRC and checksum

chainastole

2005-11-01, 3:55 am

In my VLSI design work I need to implement CRC32, CRC32c, CRC16,
CRC16c, checksum 8b, checksum 16b, checksum 32b, T10 DIF for the data
buses of 32 and 64 bits.

The first problem that I faced with is how to find the official
definitions of all this stuff - I mean standards, RFCs, etc.

I may paraphrase the question: the CRC polynomial - is it the single
thing I need to know to make hardware implementation of the function.

Willem

2005-11-01, 3:55 am

chainastole wrote:
) In my VLSI design work I need to implement CRC32, CRC32c, CRC16,
) CRC16c, checksum 8b, checksum 16b, checksum 32b, T10 DIF for the data
) buses of 32 and 64 bits.
)
) The first problem that I faced with is how to find the official
) definitions of all this stuff - I mean standards, RFCs, etc.
)
) I may paraphrase the question: the CRC polynomial - is it the single
) thing I need to know to make hardware implementation of the function.

No, you also need the initial value for the accumulator,
and sometimes another value is XORed into the final value.
Oh, and the order in which the bits are processed may also matter.

I once saw a software implementation where you could tune all those
variables, and it also had a very nice explanation of how stuff works.
I think It was called something like 'crc tutorial' but I'm not sure.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Nir Halowani

2005-11-01, 7:56 am

The basic principel is as follow:

- Serial hardware CRC: Starting with a zero register, the message is
shifted in (<-M), followed by 4 zeros (<-0). Whenever the MSB is 1, the
register is XORed with the generator (XOR). The low-order four bits of
the register are then the CRC to be added.
The hardware view is to process a bit stream bit-by-bit, resulting in a
series of check digits which are appended to the original message.
During this process, the CRC engine only needs to keep b+1 bits of
state, independent of the message length.
- Sending: For the initial generation, the message is first considered
to be padded with b zeros. These imaginary appended zeros are then
replaced by the calculated CRC. The message (with the check digits
appended) is then sent over the transmission channel to the recipient.
- Reception is even simpler: The entire message including check
sequence is passed through the same circuit that was used to generate
the check sequence. The result of the circuit should then be all-zeros,
indicating that the CRC verification succeeded.1
The actual operation is illustrated in the image to the left. We assume
an imaginary four-bit CRC, whose generator is 10011. Yes, you are
right: These are five bits. But the most significant bit (MSB) is not
really of interest, and is therefore not counted. First, the generator
MSB is always 1. Second, whenever the register MSB becomes 1, the
generator is XORed against the register, clearing the MSB. As a result,
the MSB does not need to be transmitted.
Also, magically (at least for now), the resulting message-plus-CRC
sequence, when passed through the CRC hardware, will clear the
register.

CRC hardware Operation
Generator: 1 0 0 1 1

Operation Register Message
0 0 0 0 0 0110111
<-M 0 0 0 0 0 110111
<-M 0 0 0 0 1 10111
<-M 0 0 0 1 1 0111
<-M 0 0 1 1 0 111
<-M 0 1 1 0 1 11
<-M 1 1 0 1 1 1
XOR 0 1 0 0 0 1
<-M 1 0 0 0 1
XOR 0 0 0 1 0
<-0 0 0 1 0 0
<-0 0 1 0 0 0
<-0 1 0 0 0 0
XOR 0 0 0 1 1
<-0 0 0 1 1 0

- Nir

Mark Adler

2005-11-01, 6:55 pm

Willem wrote:
> I once saw a software implementation where you could tune all those
> variables, and it also had a very nice explanation of how stuff works.
> I think It was called something like 'crc tutorial' but I'm not sure.

http://www.ross.net/crc/download/crc_v3.txt

mark

Sponsored Links