Query in 32 bit Parallel CRC...urgent

Discussion in 'VHDL' started by osr, Apr 11, 2007.

  1. osr

    osr Guest

    Hi,

    Can anyone plz tell me the theory behind 32bit parallel CRC? i m not
    getting the basis on which the 32 bit CRC is being calculated in the
    code below.This code is generated from the CRC tool of wesite www.easics.com.I
    refered many ieee papers even then i couldnt get the idea.Plz help me
    its urgent.


    library IEEE;
    use IEEE.std_logic_1164.all;

    package PCK_CRC32_D8 is

    -- polynomial: (0 1 2 4 5 7 8 10 11 12 16 22 23 26 32)
    -- data width: 8
    -- convention: the first serial data bit is D(7)
    function nextCRC32_D8
    ( Data: std_logic_vector(7 downto 0);
    CRC: std_logic_vector(31 downto 0) )
    return std_logic_vector;

    end PCK_CRC32_D8;

    library IEEE;
    use IEEE.std_logic_1164.all;

    package body PCK_CRC32_D8 is

    -- polynomial: (0 1 2 4 5 7 8 10 11 12 16 22 23 26 32)
    -- data width: 8
    -- convention: the first serial data bit is D(7)
    function nextCRC32_D8
    ( Data: std_logic_vector(7 downto 0);
    CRC: std_logic_vector(31 downto 0) )
    return std_logic_vector is

    variable D: std_logic_vector(7 downto 0);
    variable C: std_logic_vector(31 downto 0);
    variable NewCRC: std_logic_vector(31 downto 0);

    begin

    D := Data;
    C := CRC;

    NewCRC(0) := D(6) xor D(0) xor C(24) xor C(30);
    NewCRC(1) := D(7) xor D(6) xor D(1) xor D(0) xor C(24) xor C(25)
    xor
    C(30) xor C(31);
    NewCRC(2) := D(7) xor D(6) xor D(2) xor D(1) xor D(0) xor C(24)
    xor
    C(25) xor C(26) xor C(30) xor C(31);
    NewCRC(3) := D(7) xor D(3) xor D(2) xor D(1) xor C(25) xor C(26)
    xor
    C(27) xor C(31);
    NewCRC(4) := D(6) xor D(4) xor D(3) xor D(2) xor D(0) xor C(24)
    xor
    C(26) xor C(27) xor C(28) xor C(30);
    NewCRC(5) := D(7) xor D(6) xor D(5) xor D(4) xor D(3) xor D(1) xor
    D(0) xor C(24) xor C(25) xor C(27) xor C(28) xor C(29)
    xor
    C(30) xor C(31);
    NewCRC(6) := D(7) xor D(6) xor D(5) xor D(4) xor D(2) xor D(1) xor
    C(25) xor C(26) xor C(28) xor C(29) xor C(30) xor
    C(31);
    NewCRC(7) := D(7) xor D(5) xor D(3) xor D(2) xor D(0) xor C(24)
    xor
    C(26) xor C(27) xor C(29) xor C(31);
    NewCRC(8) := D(4) xor D(3) xor D(1) xor D(0) xor C(0) xor C(24)
    xor
    C(25) xor C(27) xor C(28);
    NewCRC(9) := D(5) xor D(4) xor D(2) xor D(1) xor C(1) xor C(25)
    xor
    C(26) xor C(28) xor C(29);
    NewCRC(10) := D(5) xor D(3) xor D(2) xor D(0) xor C(2) xor C(24)
    xor
    C(26) xor C(27) xor C(29);
    NewCRC(11) := D(4) xor D(3) xor D(1) xor D(0) xor C(3) xor C(24)
    xor
    C(25) xor C(27) xor C(28);
    NewCRC(12) := D(6) xor D(5) xor D(4) xor D(2) xor D(1) xor D(0)
    xor
    C(4) xor C(24) xor C(25) xor C(26) xor C(28) xor
    C(29) xor
    C(30);
    NewCRC(13) := D(7) xor D(6) xor D(5) xor D(3) xor D(2) xor D(1)
    xor
    C(5) xor C(25) xor C(26) xor C(27) xor C(29) xor
    C(30) xor
    C(31);
    NewCRC(14) := D(7) xor D(6) xor D(4) xor D(3) xor D(2) xor C(6)
    xor
    C(26) xor C(27) xor C(28) xor C(30) xor C(31);
    NewCRC(15) := D(7) xor D(5) xor D(4) xor D(3) xor C(7) xor C(27)
    xor
    C(28) xor C(29) xor C(31);
    NewCRC(16) := D(5) xor D(4) xor D(0) xor C(8) xor C(24) xor C(28)
    xor
    C(29);
    NewCRC(17) := D(6) xor D(5) xor D(1) xor C(9) xor C(25) xor C(29)
    xor
    C(30);
    NewCRC(18) := D(7) xor D(6) xor D(2) xor C(10) xor C(26) xor C(30)
    xor
    C(31);
    NewCRC(19) := D(7) xor D(3) xor C(11) xor C(27) xor C(31);
    NewCRC(20) := D(4) xor C(12) xor C(28);
    NewCRC(21) := D(5) xor C(13) xor C(29);
    NewCRC(22) := D(0) xor C(14) xor C(24);
    NewCRC(23) := D(6) xor D(1) xor D(0) xor C(15) xor C(24) xor C(25)
    xor
    C(30);
    NewCRC(24) := D(7) xor D(2) xor D(1) xor C(16) xor C(25) xor C(26)
    xor
    C(31);
    NewCRC(25) := D(3) xor D(2) xor C(17) xor C(26) xor C(27);
    NewCRC(26) := D(6) xor D(4) xor D(3) xor D(0) xor C(18) xor C(24)
    xor
    C(27) xor C(28) xor C(30);
    NewCRC(27) := D(7) xor D(5) xor D(4) xor D(1) xor C(19) xor C(25)
    xor
    C(28) xor C(29) xor C(31);
    NewCRC(28) := D(6) xor D(5) xor D(2) xor C(20) xor C(26) xor C(29)
    xor
    C(30);
    NewCRC(29) := D(7) xor D(6) xor D(3) xor C(21) xor C(27) xor C(30)
    xor
    C(31);
    NewCRC(30) := D(7) xor D(4) xor C(22) xor C(28) xor C(31);
    NewCRC(31) := D(5) xor C(23) xor C(29);

    return NewCRC;

    end nextCRC32_D8;

    end PCK_CRC32_D8;

    Thanks
     
    osr, Apr 11, 2007
    #1
    1. Advertising

  2. osr

    Ben Jones Guest

    "osr" <> wrote in message
    news:...
    > Hi,


    > Can anyone plz tell me the theory behind 32bit parallel CRC? i m not
    > getting the basis on which the 32 bit CRC is being calculated in the
    > code below.


    The CRC calculation is just an LFSR. Every time a new bit arrives, the
    register is shifted and some XORs are done. You can write down an equation
    for the new CRC state in terms of the old CRC state and the new input bit -
    it looks a lot like the "generator polynomial" that defines the CRC being
    used. Hopefully you know that much already, but if not, it's generally
    available knowledge.

    To develop a parallel CRC implementation, you just have to consider what
    happens when you update the CRC multiple times. This just means applying the
    simple "single-update" equation over and over again. The state of the CRC
    register after two updates is a function of the original state and the two
    input bits, nothing more. The equation for this can be derived from the
    single-update equation in a number of ways but it's a pretty easy thing to
    do once you know how the CRC works.

    Deriving the multiple-update equations for longer and longer look-aheads is
    not complicated, but it is tedious and error prone - hence there are tools
    (like the one you found) that do it for you.

    My suggestion would be to start with a very small LFSR with a simple
    polynomial, and derive these equations yourself for that reduced system - on
    paper, and/or with a little bit of programming. Once you've been through
    that process you'll understand a lot better.

    Cheers,

    -Ben-
     
    Ben Jones, Apr 11, 2007
    #2
    1. Advertising

  3. Ben Jones a écrit :
    > "osr" <> wrote in message
    > news:...
    >> Hi,

    >
    >> Can anyone plz tell me the theory behind 32bit parallel CRC? i m not
    >> getting the basis on which the 32 bit CRC is being calculated in the
    >> code below.

    >
    > The CRC calculation is just an LFSR. Every time a new bit arrives, the
    > register is shifted and some XORs are done.


    Hello,

    The mathematical theory is quite a bit more complex and the "shift / xor" is
    only the result of a mathematical simplification.

    The CRC of a block stream is the reminder of the divide of the number constitued
    by all bytes of the block following each other by the number used in the
    exclusive OR (the "CRC generator").

    As you can write in decimal that any number N= "...dcba" = a*10^0 + b*10^1 + ...
    You can consider your stream as a Base256 number, with a "byte" element :
    N = Byte0*256^0 + Byte1*256^1 + ... Byten*256^n,
    which is the same than consider it as a base 2 number with a "bit" element :
    N = Bit0*2^0 + Bit1*2^1 + Bit2*2^2 + ....

    Then you can divide that number N by the "CRC generator", a value that you
    choose for some properties, ie 0x110201 (= CCITT polynom = 2^16+2^12+2^5+2^0)
    and the CRC will be the reminder of the divide.


    When you can compute the CRC bit by bit in hardware in realtime, there are not
    any problem, the computation is quite simple and fast.

    But in a byte based stream, (or wider), the CRC computation needs too much time
    and resources, so the mathematicians have produced an equivalent result based on
    the modulo 2 theory that enable to compute the CRC with a significant less
    amount of time and ressources.

    Please refer to the excellent article "The Great CRC Mystery" from Terry Ritter,
    available on many web site like http://www.ciphersbyritter.com/ARTS/CRCMYST.HTM.

    Pascal
     
    Pascal Peyremorte, Apr 11, 2007
    #3
  4. osr

    Ben Jones Guest

    "Pascal Peyremorte" <> wrote in message
    news:461cdfbb$0$27403$...
    > Ben Jones a écrit :
    >> "osr" <> wrote in message
    >> news:...
    >>> Hi,

    >>
    >>> Can anyone plz tell me the theory behind 32bit parallel CRC? i m not
    >>> getting the basis on which the 32 bit CRC is being calculated in the
    >>> code below.

    >>
    >> The CRC calculation is just an LFSR. Every time a new bit arrives, the
    >> register is shifted and some XORs are done.

    >
    > The mathematical theory is quite a bit more complex and the "shift / xor"
    > is only the result of a mathematical simplification.


    Yes, that's almost true. The mathematics underlying *why* CRCs work as
    error-detecting codes is pretty complicated. However, to go from
    remainder-only modulo-2 division to shift/xor operations is not even a
    simplification - they are exactly the same thing! See for example Numerical
    Recipes in C, section 20.3 (p896+).

    The Ritter link is very useful background. It is definitely most important
    to understand the basic principles of serial CRC before considering parallel
    architectures!

    Cheers,

    -Ben-
     
    Ben Jones, Apr 11, 2007
    #4
  5. osr wrote:

    > Can anyone plz tell me the theory behind 32bit parallel CRC? i m not


    Google this group.
    This subject has been covered many times.

    -- Mike Treseler
     
    Mike Treseler, Apr 11, 2007
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Shukla, Sunil Kumar

    parallel CRC equation generator

    Shukla, Sunil Kumar, May 31, 2005, in forum: VHDL
    Replies:
    2
    Views:
    1,164
    Pete Fraser
    May 31, 2005
  2. Mamut

    crc-8 and crc-16 code...

    Mamut, Feb 21, 2007, in forum: C++
    Replies:
    5
    Views:
    4,062
    Victor Bazarov
    Feb 22, 2007
  3. `Zidane Tribal
    Replies:
    1
    Views:
    2,521
    Joe Smith
    Jul 28, 2007
  4. BING BANG
    Replies:
    3
    Views:
    393
    Bill Davy
    Mar 15, 2012
  5. `Zidane Tribal
    Replies:
    3
    Views:
    259
    Sisyphus
    Jul 27, 2007
Loading...

Share This Page