Velocity Reviews > VHDL > Parity Check

# Parity Check

Ed
Guest
Posts: n/a

 09-30-2004
Hi,

I have a 36 bit bus for which I need to generate an even parity bit. The
only way I can think to do this, is to use a loop and check each bit
individually. Is that the best way to do it? Does anyone know any better
techniques for generating the parity bit?

Thanks for any help,

Georg Acher
Guest
Posts: n/a

 10-01-2004
"Ed" <(E-Mail Removed)> writes:
>Hi,
>
>I have a 36 bit bus for which I need to generate an even parity bit. The

Smells like PCI...

>only way I can think to do this, is to use a loop and check each bit
>individually. Is that the best way to do it? Does anyone know any better
>techniques for generating the parity bit?

The loop will work and synthesize, but depending on the tool it may get
quite slow in a chip

You can write a function which calculates the parity for 4 bits, and combine the
9 outputs of 9 functions calls in two more similar stages. The function itself
maps easily to the usual FPGA logic elements and the cascading gives a balanced
and short path for all bits.

--
Georg Acher, http://www.velocityreviews.com/forums/(E-Mail Removed)
http://wwwbode.in.tum.de/~acher
"Oh no, not again !" The bowl of petunias

David Bishop
Guest
Posts: n/a

 10-01-2004
Georg Acher wrote:

> "Ed" <(E-Mail Removed)> writes:
>
>>Hi,
>>
>>I have a 36 bit bus for which I need to generate an even parity bit. The

Better to do it recursively

function xor_reduce (arg : std_logic_vector )
return std_logic is
variable Upper, Lower : std_logic;
variable Half : integer;
variable BUS_int : std_logic_vector ( arg'length - 1 downto 0 );
variable Result : std_logic;
begin
if (arg'LENGTH < 1) then -- In the case of a NULL range
Result := '0';
else
BUS_int := to_ux01 (arg);
if ( BUS_int'length = 1 ) then
Result := BUS_int ( BUS_int'left );
elsif ( BUS_int'length = 2 ) then
Result := BUS_int ( BUS_int'right ) xor BUS_int ( BUS_int'left);
else
Half := ( BUS_int'length + 1 ) / 2 + BUS_int'right;
Upper := xor_reduce ( BUS_int ( BUS_int'left downto Half ));
Lower := xor_reduce ( BUS_int ( Half - 1 downto BUS_int'right));
Result := Upper xor Lower;
end if;
end if;
return Result;
end;

This code is from the VHDL-200X-ft packages, and a form of it will
appear in the VHDL-2005 std_logic_1164 and numeric_std packages.
http://www.eda.org/vhdl-200x/vhdl-200x-ft/

Kai Harrekilde-Petersen
Guest
Posts: n/a

 10-01-2004
David Bishop <(E-Mail Removed)> writes:

> Georg Acher wrote:
>
>> "Ed" <(E-Mail Removed)> writes:
>>
>>>Hi,
>>>
>>>I have a 36 bit bus for which I need to generate an even parity bit. The

>
> Better to do it recursively

[snip function]

I can highly recommend this. A for-loop will elaborate into a linear
chain of XOR gates in Synopsys DC, while the recursive function
elaborates directly to a balanced binary tree.

Simulation time, however, will suffer.

Regards,

Kai
--
Kai Harrekilde-Petersen <khp(at)harrekilde(dot)dk>

Ed
Guest
Posts: n/a

 10-01-2004

"Ed" <(E-Mail Removed)> wrote in message news:cji1df\$4lc\$(E-Mail Removed)...
> Hi,
>
> I have a 36 bit bus for which I need to generate an even parity bit. The
> only way I can think to do this, is to use a loop and check each bit
> individually. Is that the best way to do it? Does anyone know any better
> techniques for generating the parity bit?
>
> Thanks for any help,
>
>

Thanks for the replies.

Yes it is for PCI. Well spotted.

The following seems like a simple (and I guess quick) way of doing it (din
is the 36 bit bus and parity is the output):

int1 <= din(0) xor din(1);
int2 <= int1 xor din(2);
int3 <= int2 xor din(3);
int4 <= int3 xor din(4);
int5 <= int4 xor din(5);
int6 <= int5 xor din(6);
int7 <= int6 xor din(7);
int8 <= int7 xor din(;
int9 <= int8 xor din(9);
int10 <= int9 xor din(10);
int11 <= int10 xor din(11);
int12 <= int11 xor din(12);
int13 <= int12 xor din(13);
int14 <= int13 xor din(14);
int15 <= int14 xor din(15);
int16 <= int15 xor din(16);
int17 <= int16 xor din(17);
int18 <= int17 xor din(1;
int19 <= int18 xor din(19);
int20 <= int19 xor din(20);
int21 <= int20 xor din(21);
int22 <= int21 xor din(22);
int23 <= int22 xor din(23);
int24 <= int23 xor din(24);
int25 <= int24 xor din(25);
int26 <= int25 xor din(26);
int27 <= int26 xor din(27);
int28 <= int27 xor din(2;
int29 <= int28 xor din(29);
int30 <= int29 xor din(30);
int31 <= int30 xor din(31);
int32 <= int31 xor din(32);
int33 <= int32 xor din(33);
int34 <= int33 xor din(34);
parity <= int34 xor din(35);

How does this compare to other ways of doing it? I can't see any real
disadvantage to doing it this way.

Thanks again.

Nicolas Matringe
Guest
Posts: n/a

 10-01-2004
Ed a écrit:

> The following seems like a simple (and I guess quick) way of doing it (din
> is the 36 bit bus and parity is the output):
>
> int1 <= din(0) xor din(1);
> int2 <= int1 xor din(2);

[...]
> int34 <= int33 xor din(34);
> parity <= int34 xor din(35);
>
> How does this compare to other ways of doing it? I can't see any real
> disadvantage to doing it this way.

First, it's very long to type. You could have used a for... loop )
Second, this creates a cascade of gates, with a big delay. Delay from
din(0) to parity is 36 times longer than delay from din(35) to parity.
Suppose a gate delay of 1ns, you end up with 36ns which is not PCI-33
compliant.
Balanced binary trees (such as created by the recursive function given
earlier) have constant delays for every input.

--
____ _ __ ___
| _ \_)/ _|/ _ \ Adresse de retour invalide: retirez le -
| | | | | (_| |_| | Invalid return address: remove the -
|_| |_|_|\__|\___/

Ed
Guest
Posts: n/a

 10-01-2004

"Ed" <(E-Mail Removed)> wrote in message news:cji1df\$4lc\$(E-Mail Removed)...
> Hi,
>
> I have a 36 bit bus for which I need to generate an even parity bit. The
> only way I can think to do this, is to use a loop and check each bit
> individually. Is that the best way to do it? Does anyone know any better
> techniques for generating the parity bit?
>
> Thanks for any help,
>
>

I've tried using the recursive function, but I get the following error:

ERROR:Xst:831 - C:/XilinxTest/Test/parity_gen.vhd (Line 29). Recursion
detected in function 'xor_reduce'.

So I guess my software (ISE 4.2i) doesn't allow it.

I've synthesized the following code:

parity <= (din(35) xor din(34) xor din(33) xor din(32)) xor
(din(31) xor din(30) xor din(29) xor din(2) xor
(din(27) xor din(26) xor din(25) xor din(24)) xor
(din(23) xor din(22) xor din(21) xor din(20)) xor
(din(19) xor din(1 xor din(17) xor din(16)) xor
(din(15) xor din(14) xor din(13) xor din(12)) xor
(din(11) xor din(10) xor din(9) xor din() xor
(din(7) xor din(6) xor din(5) xor din(4)) xor
(din(3) xor din(2) xor din(1) xor din(0));

And the synthesis report shows:

Maximum combinational path delay: 10.483ns

Which I think is good enough for the 33MHz PCI bus.

ivailokroumov
Guest
Posts: n/a

 10-01-2004
Dear Ed,
you some suggestions:
1. Because you use WebPack from Xilinx, you should go to the
http://www.xilinx.com/xlnx/xebiz/des...DS-ISE-WEBPACK
2. If you wish to use cascade chacking of parity like this:
int1 <= din(0) xor din(1);
int2 <= int1 xor din(2);
int3 <= int2 xor din(3);
int4 <= int3 xor din(4);
int5 <= int4 xor din(5);
int6 <= int5 xor din(6);
int7 <= int6 xor din(7);
int8 <= int7 xor din(;
int9 <= int8 xor din(9);
int10 <= int9 xor din(10);
int11 <= int10 xor din(11);
int12 <= int11 xor din(12);
int13 <= int12 xor din(13);
int14 <= int13 xor din(14);
int15 <= int14 xor din(15);
int16 <= int15 xor din(16);
int17 <= int16 xor din(17);
int18 <= int17 xor din(1;
int19 <= int18 xor din(19);
int20 <= int19 xor din(20);
int21 <= int20 xor din(21);
int22 <= int21 xor din(22);
int23 <= int22 xor din(23);
int24 <= int23 xor din(24);
int25 <= int24 xor din(25);
int26 <= int25 xor din(26);
int27 <= int26 xor din(27);
int28 <= int27 xor din(2;
int29 <= int28 xor din(29);
int30 <= int29 xor din(30);
int31 <= int30 xor din(31);
int32 <= int31 xor din(32);
int33 <= int32 xor din(33);
int34 <= int33 xor din(34);
parity <= int34 xor din(35);

you should know that if, you are going to put it otu of process, it will
have behaviour like paralel assignment, and believe me, you and your
compiler would be confused.

3. If you decide to use "for loop" your compiler will generate much
feedbacks, and the circuit will slowly.

4. If you decide to use recursion, the circuit will be faster, however you
shoud be 100% sure that every thing work properly.

I guess that the manner which will give you the best productiveness will
be recirsion ot the example which (E-Mail Removed) (Georg Acher) gave
you.
Best Regards
Ivaylo Krumov

rickman
Guest
Posts: n/a

 10-02-2004
Ed wrote:
>
> "Ed" <(E-Mail Removed)> wrote in message news:cji1df\$4lc\$(E-Mail Removed)...
> > Hi,
> >
> > I have a 36 bit bus for which I need to generate an even parity bit. The
> > only way I can think to do this, is to use a loop and check each bit
> > individually. Is that the best way to do it? Does anyone know any better
> > techniques for generating the parity bit?
> >
> > Thanks for any help,
> >
> >

>
> I've tried using the recursive function, but I get the following error:
>
> ERROR:Xst:831 - C:/XilinxTest/Test/parity_gen.vhd (Line 29). Recursion
> detected in function 'xor_reduce'.
>
> So I guess my software (ISE 4.2i) doesn't allow it.
>
> I've synthesized the following code:
>
> parity <= (din(35) xor din(34) xor din(33) xor din(32)) xor
> (din(31) xor din(30) xor din(29) xor din(2) xor
> (din(27) xor din(26) xor din(25) xor din(24)) xor
> (din(23) xor din(22) xor din(21) xor din(20)) xor
> (din(19) xor din(1 xor din(17) xor din(16)) xor
> (din(15) xor din(14) xor din(13) xor din(12)) xor
> (din(11) xor din(10) xor din(9) xor din() xor
> (din(7) xor din(6) xor din(5) xor din(4)) xor
> (din(3) xor din(2) xor din(1) xor din(0));
>
> And the synthesis report shows:
>
> Maximum combinational path delay: 10.483ns
>
> Which I think is good enough for the 33MHz PCI bus.

This looks ok to me. I belive that Georg was saying that you could
define a 4 input function that would make the code more readable and
produce the same result. I am not sure that your original code would
create anything different in the end since the logic is the same in
either case. Since the tools have the freedom to reorganize
combinatorial logic the structure of the code is not always reflected in
the resulting chip level implementation.

--

Rick "rickman" Collins

(E-Mail Removed)
removed.

Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design URL http://www.arius.com
4 King Ave 301-682-7772 Voice
Frederick, MD 21701-3110 301-682-7666 FAX

Marcus Harnisch
Guest
Posts: n/a

 10-02-2004
Kai Harrekilde-Petersen <(E-Mail Removed)> writes:
> I can highly recommend this. A for-loop will elaborate into a linear
> chain of XOR gates in Synopsys DC, while the recursive function
> elaborates directly to a balanced binary tree.

While I agree that recursive solutions are most elegant and *will* be
synthesized into a binary tree, I found that Synopsys DC is actually
pretty good at turning loops into trees all by itself. At least for
low-level functions such as AND, OR, XOR, etc.

In fact, a couple of months ago, I synthesized an iterative XOR-reduce
function and got a nice tree of gates in return. Can't remember if I
had VHDL-Presto (Synopsys' new VHDL compiler) enabled or not and

Best regards,
Marcus