Help: Implementing 4 bit CRC Circuit

How we implement computing 4 bit crc code for 8 bit serial data

on fully digital gates ? (without programming)

Hi, I noticed no-one has repsonded to your question, so I'll give it a go

I'll be honest, I haven't ever implemented a CRC checksum, in software OR hardware, but I'm aware of the methods/maths involved.

on fully digital gates

Click to expand...

Good to know other people like to make stuff using basic gates, IMO things like this done in 'pure hardware' are generally far more efficient, and cheaper.

Google has much info on CRC's, and how to implement them, in hardware/software/paper etc.. I suggest you do a bit of research. The maths can be daunting, but hardware implementation is pretty straight forward. In case you haven't done any research, heres what I know.

try here:
https://www.erg.abdn.ac.uk/users/gorry/course/dl-pages/crc.html

The second two diagrams show pretty much what you want, although they're for 16 and 32-bit CRC encoders/decoders. Its a cyclic thing using 'linear feedback shift registers' (LFSR), pretty simple really. But, for any CRC you need to know the polynomial. Off the top of my head, for a 4-bit CRCI think you'll need:

X^4+X+1. You probably know exactly what this means, but I'll explain anyway...

Putting the maths aside (I'm a hardware man mainly) all the above equation really means, is that we have a 4-bit shift register (X^4, the highest 'X' value, gives us the total number of registers in the LFSR) that is 'tapped' at X, and '1'. Each tap is the output of an XOR gate. One input from the previous register in the shift register (or the input) and the other XOR input comes from X^4.

If you want some sort of crude schem, here goes ASCII:

<- D3 <- D2 <- D1 <- XOR <- D0 <- XOR <------ INPUT
|__________________|__________|

With this (4 registers, 2 XOR gates) you clock in your byte that requires the checksum, followed by 4 0's. After all the 12-bits from the data have been clocked in (12 clk's later) your check sum will be in the four registers. So then you just read the 4-bits from D3-D0. If you want to send it all serially, with the data first, then the CRC right after it, you could just switch the output of your encoder to the output after you've sent your data byte, and just clock out the CRC. Sorry if I'm over complicating this.

Anyway, as you can see, its pretty simple. And doesn't really get that complicated for 16 and 32-bit encoders, you just have a longer shift-register, and more XOR's.
As far as I know, if you're doing this purely with logic gates, then this is the only way, but I could be wrong. For software encoders, for a 4-bit CRC, its probably easier to use a look-up table.

Sorry if you know all this already, you didn't say how much you know about CRC's, eletronics, gates etc...but it doesn't hurt to give too much information.


Good luck.

BuriedCode.

well i already knew that but thanks anyway!!

the things i confused was about :

We had a serial input bit... we define each data block consist of 8 bit data. In order to used LFSR we need to add 4 bit sequence of 0's. Hence one frame consist of 12 bit (8 data + 4 bit 0 = augmented message)

After the frame passes the LFSR we need to drop 4
bit 0's and replace it w/ the 4 bit CRC (last LFSR condition)

How to implement that thing on fully digital circuit was a matter for me....

OK, firstly, I simply answered your question. It mentioned nothing about you knowing anything about anything, so I assumed you were a layman. Next time, be more specific about what you are doing, what you know, and what you want to find out.

To be honest I don't really understand what you're asking. You mentioned 'pure digital', which to me means dealling with CMOS/TLL 74, 4000 series chips. Are you using a CPLD? FPGA? Simulated software?

If you are really just after a circuit, where you clock in 8 data bits, and get out:

<databyte><CRC>

Then its simple. Clock in your data into the CRC encoder, and at the same time clock it in to another 4-bit shift register, which acts as a 4-bit delay. The output from these shift registers (both the CRC LFSR, and the plain SR) are connected to a 2-1 MUX. The MUX starts with the input from the 'plain' Shift register, and after 12 clocks, it switches to the output of the CRC encoder. Also, when the MUX switches inputs, you should block the output of the last register in the enncoder from the 2 XOR gates. - Otherwise, your CRC checksum could change while you're shifting it out, because of the feedback.

This way requires a total of 16 clocks, from the loading in the first data byte, to getting out the last CRC check bit. And you only need a small combinatorial circuit to switch the mux after 12 clocks. But I guess you know all this......


Good Luck,

Buriedcode.

Ps. There are no less that 7 webpages that have a complete schematic of what you are talking about. If you ask nicely, I'll draw up my own schem, and post it here.

Next time, be more specific about what you are doing, what you know, and what you want to find out.

Click to expand...

Thanks for the suggestion.....
i need to be more practice on explaining

.....means dealling with CMOS/TLL 74, 4000 series chips. Are you using a CPLD? FPGA? Simulated software?

Click to expand...

YEs you're right..it's using CMOS/TLL 74. I do hope its using micro,CPLD or FPGA...but its forbidden....( well sometimes we got confused going onto the ground)

Clock in your data into the CRC encoder, and at the same time clock it in to another 4-bit shift register, which acts as a 4-bit delay.

Click to expand...

that's give me an enlightment .. i never think that way
thanks

But lets talk bit by bit
on your explanation you consider my input has 12 bit while actually don't
here is the illustration :

we had 8 bit serial input says 0000 1111. In order to have 4 bit crc checksum we need to augment the message by adding 4 bit 0's. Hence the output are now 0000 1111 0000.

That 12 bit now became the input of LFSR.After all the 12 bit had passed the LFSR we've got the 4 bit CRC checksum (for example the crc is 1010)

at the very last output we need to drop the last 0000 of LFSR input and replace it with the crc checksum. So we get 0000 1111 1010 at the very last output. after adding the crc checksum we need to reset the LFSR circuit to 0000 condition. before the next 12 bit come up.

i think your scheme will have 16 bit output. without dropping the last 4 bit 0's

7 webpages that have a complete schematic...

Click to expand...

7 webpages? are u sure? what are they? i must missed that

If you ask nicely, I'll draw up my own schem, and post it here.

Click to expand...

COme On...Show Up your idea sir :roll:
Would you please draw it. ( Hope i asked well and correct)

adedia.

Sorry for being a bit 'short' with you. Sometimes I get frustrated when I spend time explaining something that doesn't need to be explained.

COme On...Show Up your idea sir, Would you please draw it. ( Hope i asked well and correct)

Click to expand...

...You see, now I feel guilty. You did indeed ask correctly So here it is.

I think *some* explaination is probably needed, I'll try and keep it brief.
Right, the two inputs to the circuit are 'DATA IN' and 'CLOCK' and the only real output is 'DATA OUT'. Points *A* are all connected, as are points *B*.

The data input goes through an AND gate. When the other input to this gate (DATA_EN) is low, only 0's are inputed, and your data is ignored, giving us the 'four 0's after data'. The CRC encoder also has an enable line (CRC ENABLE), which, when '1' will allow the encoder to do its job, when '0' the encoder simply behaves like a standard shift register. The 4-bit counter is used to provide these controls, it also switches the MUX, so you can send your data, then the CRC checksum straight afterwards automatically. The top box 'Shift register' is simply a 4-bit delay.

Here's what should happen (haven't tested it yet):
After the first 4 clock's, the first 4 bits are in the shift register, and the CRC encoder is doing its job (CRC_ENABLE = 1, DATA_EN = 1). The next clock will send out the first bit of your data from the shift-register to the 'DATA OUT' because the MUX is switched to that.

After 8 clocks, you've inputted all 8 bits of your data, and the 'DATA_EN' line is pulled low, preventing any 1's getting in, so the input after this will just be 0's.
Also, we've sent 4 bits out of the shift register, and it still contains the last 4 bits of our data.

After 12 clocks, all our data has passed through the shift register, through the MUX, and to the output. The shift register now simply contains '0000'. And the CRC encoder should have the 4-bit checksum in its registers. So, we disable the CRC encoder (pull 'CRC_ENABLE' low) so it acts like a basic shift register. We also switch the 'DATA OUT' to the output of the CRC encoder, by changing the MUX's input from 1 to 0. Then the next 4 clocks just shift out the 4-bit CRC checksum to the 'DATA OUT'.

So, after 16 clocks in total, we've read in our 8 bits of data, and sent out our data, followed directly by its 4-bit CRC checksum.

So heres a crude I/O map:

CLK: T T T T T T T T T T T T T T T T
_IN d d d d d d d d X X X X X X X X
OUT 0 0 0 0 d d d d d d d d C C C C

Where 'T' is a clock tick, 'd' is a data bit, 'C@ is a checksum bit, and 'X' is 'don't care'

Hope you understand, and I hope it helps. I did a similar thing for a 12,8 Hamming encoder for error correction, although it was a tad more complicated.

Exhausted,

BuriedCode.
[/img]