CCITT CRC X1021 parallel calc

N

Niv

Guest
I have to verify the CCITT CRC (X1021 polynomial) on incoming parallel
data (bytes).
Is there a simple way to create a function that calcs the CRC from
the algorithm a byte at a time.

The only way that occurs to me is to think what the equation is for
1 clk cycle, then 2 & so on for 8 clock cycles against the 8 bits of
the byte.

This will probably result in a large equation, so is there a better
way?
 
"Niv" <kev.parsons@mbda.co.uk> wrote in message
news:1146225220.323569.112610@u72g2000cwu.googlegroups.com...
I have to verify the CCITT CRC (X1021 polynomial) on incoming parallel
data (bytes).
Is there a simple way to create a function that calcs the CRC from
the algorithm a byte at a time.
Click to expand...
Yes.

http://www.google.com/search?q=CRC+bytewise
 
Niv wrote:
I have to verify the CCITT CRC (X1021 polynomial) on incoming parallel
data (bytes).
Click to expand...
http://groups.google.com/groups/search?q=vhdl+parallel+crc_shift

-- Mike Treseler
 
OK, I've come up with the following solution for crc calc on whole
bytes,
Would anyone care to say how good, bad or otherwise this is?

(Comment field needs courier font to view properly)

--------------------------------------------------------------------------------------

ARCHITECTURE rtl OF crc_1021 IS

--* Declarations:

SIGNAL calc : STD_LOGIC_VECTOR (15 DOWNTO 0);
SIGNAL h7 : STD_LOGIC;
SIGNAL g6 : STD_LOGIC;
SIGNAL f5 : STD_LOGIC;
SIGNAL e4 : STD_LOGIC;
SIGNAL d3 : STD_LOGIC;
SIGNAL c2 : STD_LOGIC;
SIGNAL b1 : STD_LOGIC;
SIGNAL a0 : STD_LOGIC;

BEGIN

--* Activity Statements:
-- Assign output to calculated CRC.
CRC <= calc;
-- Assign input byte bits to individual signals
-- (shorten equation visually).
h7 <= d_byte(7);
g6 <= d_byte(6);
f5 <= d_byte(5);
e4 <= d_byte(4);
d3 <= d_byte(3);
c2 <= d_byte(2);
b1 <= d_byte(1);
a0 <= d_byte(0);
--------------------------------------------------------------------------------
-- CRC polynomial is X^16 + X^12 + X^5 + 1 (CCITT $1021)
--
-- Byte data is shifted id serially, msb (h7) first, into the LFSR.
-- If byte is bits (abcdefgh)
--
-- d_in(msb-first)---->X<-15-14-13-12-X-11-10-9-8-7-6-5-X-4-3-2-1-0
-- | ^ ^ ^
-- | | | |
-- |______________|_________________|_________|
--
--------------------------------------------------------------------------------
-- This process performs the CRC calculation for a whole byte input.
-- The algorithm is effectively 8 clock cycles of the LFSR, inputing
the byte
-- msb first, etc.
-- The 6 variables, x1, x2 etc, are used to reduce the total number of
XOR gates
-- where a common XOR function has been identified.
--------------------------------------------------------------------------------
crc_calc : PROCESS (clk, reset_n)

VARIABLE x1 : STD_LOGIC;
VARIABLE x2 : STD_LOGIC;
VARIABLE x3 : STD_LOGIC;
VARIABLE x4 : STD_LOGIC;
VARIABLE x7 : STD_LOGIC;
VARIABLE x8 : STD_LOGIC;

BEGIN
IF reset_n = '0' THEN
calc <= (OTHERS => '0');
x1 := '0';
x2 := '0';
x3 := '0';
x4 := '0';
x7 := '0';
x8 := '0';
ELSIF rising_edge(clk) THEN

IF c_clk_en = '1' THEN

IF c_start = '1' THEN
calc <= (OTHERS => '0');
x1 := '0';
x2 := '0';
x3 := '0';
x4 := '0';
x7 := '0';
x8 := '0';
ELSIF c_strobe = '1' THEN -- Calc the crc on the incoming byte

x1 := h7 XOR calc(11);
x2 := g6 XOR calc(10);
x3 := f5 XOR calc(9);
x4 := e4 XOR calc(8);
x7 := e4 XOR calc(12);
x8 := a0 XOR calc(12);

calc(15) <= d3 XOR calc(7) XOR x1;
calc(14) <= c2 XOR calc(6) XOR x2;
calc(13) <= b1 XOR calc(5) XOR x3;
-- calc(12) <= a0 XOR calc(4) XOR x4 XOR h7 XOR calc(12);
calc(12) <= x8 XOR calc(4) XOR x4 XOR h7;
calc(11) <= g6 XOR calc(3);
calc(10) <= f5 XOR calc(2);
calc(9) <= x7 XOR calc(1);
calc(8) <= d3 XOR calc(0) XOR x1;
calc(7) <= c2 XOR calc(15) XOR x2 XOR h7;
calc(6) <= b1 XOR calc(14) XOR x3 XOR g6;
-- calc(5) <= a0 XOR calc(13) XOR x4 XOR f5 XOR calc(12);
calc(5) <= x8 XOR calc(13) XOR x4 XOR f5;
calc(4) <= x7;
calc(3) <= d3 XOR x1;
calc(2) <= c2 XOR x2;
calc(1) <= b1 XOR x3;
-- calc(0) <= a0 XOR x4 XOR calc(12);
calc(0) <= x8 XOR x4;

END IF;
END IF;
END IF;
END PROCESS crc_calc;
------------------------------------------------------
END ARCHITECTURE rtl;
 
I've come up with this for CCITT CRC byte parallel algorithm.
Anyone care to comment how good,bad or otherwise please?

Essentially, it's a 16 bit LFSR (15:0) with stages 5 & 12 fed with the
XOR of its previous stage & d_in & stage 15,
and stage 0 fed with just the XOR of d_in & stage 15. This has then
been shifted 8 times, once per input byte bit,
to produce the large XOR tree (some common term simplification).

(Note, comment field needs courier font to align OK).

ARCHITECTURE rtl OF crc_1021 IS

--* Declarations:

SIGNAL calc : STD_LOGIC_VECTOR (15 DOWNTO 0);
SIGNAL h7 : STD_LOGIC;
SIGNAL g6 : STD_LOGIC;
SIGNAL f5 : STD_LOGIC;
SIGNAL e4 : STD_LOGIC;
SIGNAL d3 : STD_LOGIC;
SIGNAL c2 : STD_LOGIC;
SIGNAL b1 : STD_LOGIC;
SIGNAL a0 : STD_LOGIC;

BEGIN

--* Activity Statements:
-- Assign output to calculated CRC.
d_CRC <= calc;
-- Assign input byte bits to individual signals
-- (shorten equation visually).
h7 <= d_byte(7);
g6 <= d_byte(6);
f5 <= d_byte(5);
e4 <= d_byte(4);
d3 <= d_byte(3);
c2 <= d_byte(2);
b1 <= d_byte(1);
a0 <= d_byte(0);
--------------------------------------------------------------------------------
-- CRC polynomial is X^16 + X^12 + X^5 + 1 (CCITT $1021)
--
-- Byte data is shifted id serially, msb (h7) first, into the LFSR.
-- If byte is bits (abcdefgh)
--
-- d_in(msb-first)---->X<-15-14-13-12-X-11-10-9-8-7-6-5-X-4-3-2-1-0
-- | ^ ^ ^
-- | | | |
-- |______________|_________________|_________|
--
--------------------------------------------------------------------------------
-- This process performs the CRC calculation for a whole byte input.
-- The algorithm is effectively 8 clock cycles of the LFSR, inputing
the byte
-- msb first, etc.
-- The 6 variables, x1, x2 etc, are used to reduce the total number of
XOR gates
-- where a common XOR function has been identified.
--------------------------------------------------------------------------------
crc_calc : PROCESS (clk, reset_n)

VARIABLE x1 : STD_LOGIC;
VARIABLE x2 : STD_LOGIC;
VARIABLE x3 : STD_LOGIC;
VARIABLE x4 : STD_LOGIC;
VARIABLE x7 : STD_LOGIC;
VARIABLE x8 : STD_LOGIC;

BEGIN
IF reset_n = '0' THEN
calc <= (OTHERS => '0');
x1 := '0';
x2 := '0';
x3 := '0';
x4 := '0';
x7 := '0';
x8 := '0';
ELSIF rising_edge(clk) THEN

IF c_clk_en = '1' THEN

IF c_start = '1' THEN
calc <= (OTHERS => '0');
x1 := '0';
x2 := '0';
x3 := '0';
x4 := '0';
x7 := '0';
x8 := '0';
ELSIF c_strobe = '1' THEN -- Calc the crc on the incoming byte

x1 := h7 XOR calc(11);
x2 := g6 XOR calc(10);
x3 := f5 XOR calc(9);
x4 := e4 XOR calc(8);
x7 := e4 XOR calc(12);
x8 := a0 XOR calc(12);

calc(15) <= d3 XOR calc(7) XOR x1;
calc(14) <= c2 XOR calc(6) XOR x2;
calc(13) <= b1 XOR calc(5) XOR x3;
-- calc(12) <= a0 XOR calc(4) XOR x4 XOR h7 XOR calc(12);
calc(12) <= x8 XOR calc(4) XOR x4 XOR h7;
calc(11) <= g6 XOR calc(3);
calc(10) <= f5 XOR calc(2);
calc(9) <= x7 XOR calc(1);
calc(8) <= d3 XOR calc(0) XOR x1;
calc(7) <= c2 XOR calc(15) XOR x2 XOR h7;
calc(6) <= b1 XOR calc(14) XOR x3 XOR g6;
-- calc(5) <= a0 XOR calc(13) XOR x4 XOR f5 XOR calc(12);
calc(5) <= x8 XOR calc(13) XOR x4 XOR f5;
calc(4) <= x7;
calc(3) <= d3 XOR x1;
calc(2) <= c2 XOR x2;
calc(1) <= b1 XOR x3;
-- calc(0) <= a0 XOR x4 XOR calc(12);
calc(0) <= x8 XOR x4;

END IF;
END IF;
END IF;
END PROCESS crc_calc;
------------------------------------------------------
END ARCHITECTURE rtl;
 
Niv wrote:
I've come up with this for CCITT CRC byte parallel algorithm.
Anyone care to comment how good,bad or otherwise please?
Click to expand...
I suggest you run a sim on a known good packet
and see if you get the expected magic number.
That's really the only opinion that matters.

Essentially, it's a 16 bit LFSR (15:0) with stages 5 & 12 fed with the
XOR of its previous stage & d_in & stage 15,
and stage 0 fed with just the XOR of d_in & stage 15. This has then
been shifted 8 times, once per input byte bit,
to produce the large XOR tree (some common term simplification).
Click to expand...
The crc_shift functions I posted demonstrate a simpler method.

CCITT is used for PPP and frame relay packets
that specify least sig bit first except for the FCS.
Check your requirements.
I think you will find that the serial model you
are using requires an init of all ones to meet
the standards above.
Good luck.

-- Mike Treseler
 
OK, thanks mike.
My expanded XOR tree gives the same answers as your shift function,
and synthesised to remarkably similar structure, (not too surprising
really).

I've had the requirement placed on me, so perhaps its a variant of
CCITT,
as our systems dept have stated the CRC is initialised to all '0's, not
'1's
as you'd expect: a lot of '0's if the data is all '0's!, oh well,
that's systems for you.

Thanks again for the help; I was there, but my initial spreadsheet had
some
errors, the perils of cut & paste.
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top