Browse Prior Art Database

Programmable Input Bus Width For CRC Calculation

IP.com Disclosure Number: IPCOM000187762D
Publication Date: 2009-Sep-18
Document File: 9 page(s) / 215K

Publishing Venue

The IP.com Prior Art Database

Abstract

If the system has k different sets of input bus width. The CRC circuit is able to select any set of this input bus without adding pad bits to the input bitstream.

This text was extracted from a Microsoft PowerPoint presentation.
This is the abbreviated version, containing approximately 48% of the total text.

Slide 1 of 9

Programmable Input Bus Width for CRC Calculation


Slide 2 of 9

The Needs

In the transceiver / receiver, the data bus width is programmable. User can configure the input/output channels to 8-bit, 16-bit, 24-bit, etc.

The CRC circuits can be built for the maximum bus width of the system, then adds the padding bits to the input bitstream if a shorter bus width is selected. But this will degrade the coverage of the CRC check due to

  The number of bits in the calculation is longer than the actual bits.

  Lost coverage for the burst error patterns.

So, the programmable bus-width for CRC calculation is needed.

2


Slide 3 of 9

CRC Calculation Overview

Polynomial representation for data bit stream of k bits (d0d1d2 …dk-1), where dk–1 is the first bit to be transmitted, is a polynomial of degree k – 1:

d(x) = d0 + d1x + d2x2 + … + dk–1xk–1

CRC calculation is the remainder of a polynomial division:

CRCexp = c(x) = xr d(x) mod g(x) = (c0c1…cr-1)

That means that multiply xr to the data stream d(x) before performing the polynomial division.

All registers are initialized to zero.

 

g1

 

g2

 

g3

gr-1

d(x)

1

2

3

4

r-1

r

CRCexp = c(x)

= xr d(x) mod g(x)

= (c0c1c2…cr-1)

(d0d1d2 … dk-1)

3


Slide 4 of 9

CRC Calculation Overview (cont’)

CRC calculation with initialization:

CRCexp = c(x) = xr [d(x) + xk I(x)] mod g(x) = (c0c1…cr-1)

Where k is the length of the input bitstream d(x), and

xk I(x) = (i0…ir-1) mod g(x)

in which (i0…ir-1) is the initialization value of the registers.

Typically, (i0…ir-1) is the sequence of all 1’s.

Registers are initialized to (i0…ir-1).

 

g1

 

g2

 

g3

gr-1

d(x)

1

2

3

4

r-1

r

(d0d1d2 … dk-1)

CRCexp = c(x)

= xr d(x) mod g(x)

= (c0c1c2…cr-1)

4


Slide 5 of 9

CRC Calculation Overview (cont’)

The read back bitstream, m(x) = (c0c1c2…cr-1v0v1…vk-1), including the expected CRC bits, feeds into the CRC decoder to calculate the syndrome.

S(x) = xr [m(x) + xk+r I(x)] mod g(x)

Where m(x) = c(x) + xr v(x) + E(x); E(x) is an error pattern.

The read back data and the original data are identical if S(x)=0 (the contents of the LFSR are all zeroes).

Mathematically, if v(x) = d(x) then

S(x) = xr [m(x) + xk+rI(x)] = xr(c(x) + xrd(x) + E(x) + xk+rI(x))

= xr(c(x) + E(x) + xrd(x) + xk+rI(x))

= xr (2 c(x) + E(x)) = xr E(x) mod g(x)

E(x)=0 if there is no error. Therefore, S(x) = 0.

c(x)

 

g1

 

g2

 

g3

gr-1

Registers are initialized to (i0…ir-1).

v(x)

1

2

3

4

r-1

r

CRC Error

(c0c1c2…cr-1 v0v1v2 … vk)

r-input OR gate

5


Slide 6 of 9

Parallel CRC Calculation Overview

To expedite the CRC computation, the input data path can be expanded to multi-bits at a time. That is so-called the parallel CRC calculation. The algorithm can be derived from the serial computation via its state equations.

     
 
   
 
   
       
 
 
       
 
 
     
       
 
 
   
 

1

2

3

4

r-1

 
           
 

g1

 

g2

 

g3

 

gr-1

       

din

r

 
   

qi and Qi, i=1…r, denotes the current states and next state of the LFSR, respectively.

ThenQi = qr + dinfor i = 1

Qi = qi-1 + (qr + din) gi-1,for i...