Re: [usb] crc algorithm

[nanda.kumar@wipro.com]

----- Original Message ----- 
From: "kw@nie" <kwanie@p... > 
To: <usb@o... > 
Date: Fri, 22 Feb 2002 11:03:23 +0800 
Subject: Re: [usb] crc algorithm 

> 
> 
> Hi Tambunan, 
> 
> > Do you know the explanation of algorithm below and 
> > those modules ( e.g usbf_crc5.v)? 
> 
> usbf_crc5.v and usbf_crc16.v use parallel approach instead or 
> bit-serial 
> approach, i.e. CRC5 and CRC16 generators take one cycle to process 
> 11 bits 
> and 8 bits respectively. This is usually done for speed. 
> 
> Let say you want to process x bits at each clock, then the crc 
> register's 
> combination logic (based on input and crc register's present state) 
> have to 
> be worked out. The combination logic output will the equivalent of 
> the crc 
> register's value after x bits is shifted into a bit-serial crc 
> generator. In 
> this manner, you will have the result in 1 cycle instead of x 
> cycle. 
> 
> cheers, 
> kwanie 
> 
> 
> 
> ----- Original Message ----- 
> From: "RE Tambunan" <kebloo@m... > 
> To: <usb@o... > 
> Sent: Friday, February 22, 2002 8:12 AM 
> Subject: Re: [usb] crc algorithm 
> 
> 
> > Hallo Bo... 
> > 
> > Have you checked usb 2.0 core by Mr. Rudolf Usselman? 
> > especially at usbf_crc5.v and usbf_crc16.v ? 
> > Do you know the explanation of algorithm below and 
> > those modules ( e.g usbf_crc5.v)? 
> > Btw... algorithm I've shown you is based on Tom Coonan's 
> > in verilog, please check at 
> > ftp://www.mindspring.com/users/tcoonan/gencrc.v 
> > 
> > 
> > Best Regard, 
> > 
> > 
> > 
> > RE Tambunan 
> > 
> > On 21 Feb 2002 at 11:55, Bo wrote: 
> > 
> > > Hi Tambunan, 
> > >      I don't think that's a right way to 
> > > implement CRC check sum. 
> > >      There are two ways to implement it. Please 
> > > refer to Kwanie's post and his recently corrected one. 
> > > The second way is the prefer one in hardware design. 
> > > Because it saves time and easier to implement for 
> > > hardware acceleration. 
> > > 
> > > Assume you have M-bit input, and N-bit CRC, 
> > > then you need M+N cycle to calculate CRC (without 
> > > hardware acceleration). M for input, N for "one's 
> > > complement of calculated CRC", then you can get the 
> > > fix remainder which is 01100. 
> > > 
> > > datain for M is input, last N cycle is ~CRC. 
> > > 
> > > 
> > > assign crc0 = datain ^ crc[4]; 
> > > 
> > > crc[4] <= crc[3]; 
> > > crc[3] <= crc[2]; 
> > > crc[2] <= crc[4] ^ crc[1]; 
> > > crc[1] <= crc[0]; 
> > > crc[0] <= crc[4] ^ datain; 
> > > 
> > > Good Luck. 
> > > 
> > > bo 
> > > 
> > > 
> > > --- RE Tambunan <kebloo@m... > wrote: 
> > > > On 20 Feb 2002 at 16:16, Bo wrote: 
> > > > 
> > > > > Hi Tambunan, 
> > > > >     For my understanding, it really doesn't 
> > > > > matter what pattern you should fill during the 
> > > > > initialization. As far as you use the same 
> > > > > pattern on both encode and decode part, it 
> should 
> > > > > come out the same result. You can check it use 
> > > > > math calculation, C or even verilog. 
> > > > 
> > > > Hi Bo... I've checked the CRC calculation when CRC 
> > > > register initial value filled with 0 and 1 with some 
> > > > examples 
> > > > and I found that the result are different. 
> > > > I follow the rules from USB 1.1 specification and 
> > > > here is 
> > > > the algorithm for 5-bit CRC (CMIIW...): 
> > > > 
> > > > // from 2nd paragraph section 8.3.5 
> > > > integer         i; 
> > > > reg [4..0]      crc5out, crc5poly; 
> > > > reg [11..0]    data; 
> > > > 
> > > > crc5out = 'b11111; // or crc5out = 'b00000; 
> > > > crc5poly = 'b00101; 
> > > > for (i=0; i<12; i=i+1) begin 
> > > >     msb = crc5out[4]; 
> > > >     crc5out = crc5out << 1; 
> > > >     if ( (msb XOR data[i]) = 1) then begin 
> > > >         crc5out = crc5out XOR crc5poly; 
> > > >     end 
> > > > end 
> > > > 
> > > > // from 3rd paragraph section 8.3.5 for CRC 
> > > > generator 
> > > > crc5out = ~crc5out; 
> > > > 
> > > > 
> > > > There are some examples in "CRC in USB" whitepaper 
> > > > I used to check above algorithm. 
> > > > 
> > > > - setup addr 15 endp e 
> > > >   data = 'b10101000111 
> > > >   crc5out = 'b10111     ; for initial = 'b11111 
> > > >   crc5out = 'b00000     ; for initial = 'b00000 
> > > > 
> > > > - out addr 3a endp a 
> > > >   data = 'b01011100101 
> > > >   crc5out = 'b11100     ; for initial = 'b11111 
> > > >   crc5out = 'b10100     ; for initial = 'b00000 
> > > > 
> > > > - in addr 70 endp 4 
> > > >   data = 'b00001110010 
> > > >   crc5out = 'b01110     ; for initial = 'b11111 
> > > >   crc5out = 'b11001     ; for initial = 'b00000 
> > > > 
> > > > Also have you check Mr. Rudi's core ? 
> > > > He also prefills crc5 and crc16 register with '1' 
> > > > (check usbf_pa.v and usb_pd.v). 
> > > > Btw... there is also an online document, which 
> > > > is a thesis of Mr. Myilone Anandarajah, that 
> > > > uses '0' to prefill CRC initial value. 
> > > > Any comment for this :-).... 
> > > > 
> > > > Best regard, 
> > > > 
> > > > 
> > > > RE Tambunan 
> > > > 
> > > 
> > > __________________________________________________ 
> > 
> > 
> 
--
To unsubscribe from usb mailing list please visit http://www.opencores.org/mailinglists.shtml