Detecting more than one bit set
Yves Tchapda
I have a 512-bit vector, and I'm trying to detect a condition where
exactly 2 bits are set, or alternatively detect when more than one bit
is set. Does any one know of an optimal way of doing it without using
adders
Thanks for your help
Yves
sweir
implementation. An SOP implementation would be enormous.
Regards,
"Yves Tchapda" <yves.t...@phyworks-ic.com> wrote in message
news:434d10fb.02062...@posting.google.com...
Rezza Moieni
can use Type conversion ... first convert the Bit_vector to a simple
array of integers then use traditional solutions to detect the set bit
.... would this work?
i hope so ;)
David Jones
This is a cool application for recursive hardware.
Consider a block B that has N inputs and three outputs:
eq1: Exactly one input is set
eq2: Exactly two inputs are set
ge3: Three or more inputs are set
Obviously, the eq2 output is what you are interested in. Now, how to
implement? Partition the inputs into two roughly equal groups, and
have two instances of block B take the census for each group. Then:
eq1 <= (eq1_a and not e2q_b and not ge3_b) or
(eq1_b and not eq2_a and not ge3_a);
eq2 <= (eq1_a and eq1_b) or (eq2_a and not eq1_b and not ge3_b) or
(eq2_b and not eq1_a and not ge3_a);
ge3 <= ge3_a or ge3_b or (eq1_a and eq2_b) or (eq2_a and eq1_b);
You next need to figure out eq1, eq2 and ge3 for the boundary case of two
or three inputs. This should be easy. Finally, create the recursive
instantiation. Hint: use if-generate.
--
Petter Gustad
> Hi,
> I have a 512-bit vector, and I'm trying to detect a condition where
> exactly 2 bits are set, or alternatively detect when more than one bit
> is set. Does any one know of an optimal way of doing it without using
> adders
Do you mean optimal in terms of speed or resources? Is it possible to
do it serially in your application? If yes, shift until you have seen
two bits set or have completed all 512 (or pad your shift register
with two set bits at the end so you don't need a counter). This is of
course impossible if you have data coming in faster than 512b/cycle.
Petter
--
________________________________________________________________________
Petter Gustad 8'h2B | (~8'h2B) - Hamlet in Verilog http://gustad.com
Egbert Molenkamp
"David Jones" <d...@coup.inode.org> wrote in message
news:_rYR8.2750$ZM3.6...@news20.bellglobal.com...
> In article <434d10fb.02062...@posting.google.com>,
> Yves Tchapda <yves.t...@phyworks-ic.com> wrote:
> >Hi,
> >I have a 512-bit vector, and I'm trying to detect a condition where
> >exactly 2 bits are set, or alternatively detect when more than one bit
> >is set. Does any one know of an optimal way of doing it without using
> >adders
> >Thanks for your help
> >Yves
>
> This is a cool application for recursive hardware.
>
> Consider a block B that has N inputs and three outputs:
>
> eq1: Exactly one input is set
> eq2: Exactly two inputs are set
> ge3: Three or more inputs are set
>
> Obviously, the eq2 output is what you are interested in. Now, how to
> implement? Partition the inputs into two roughly equal groups, and
> have two instances of block B take the census for each group. Then:
>
> eq1 <= (eq1_a and not e2q_b and not ge3_b) or
> (eq1_b and not eq2_a and not ge3_a);
Nice solution. But should this not be
eq1 <= (eq1_a AND NOT EQ1_B and not eq2_b and not ge3_b) or
(eq1_b AND NOT EQ1_A and not eq2_a and not ge3_a);
Egbert Molenkamp
Egbert Molenkamp
Egbert Molenkamp
LIBRARY ieee;
USE ieee.std_logic_1164.ALL;
USE ieee.numeric_std.ALL;
ENTITY two_ones IS
GENERIC (w : natural := 512);
PORT (data : IN std_logic_vector(w-1 downto 0);
res : OUT boolean);
END two_ones;
ARCHITECTURE behaviour OF two_ones IS
FUNCTION cnt (a:std_logic_vector) RETURN integer IS
VARIABLE nmb : INTEGER RANGE 0 TO a'LENGTH;
VARIABLE ai : std_logic_vector(a'LENGTH-1 DOWNTO 0);
CONSTANT middle : integer := a'LENGTH/2;
BEGIN
ai := a;
IF ai'LENGTH>=2 THEN
nmb := cnt(ai(ai'LENGTH-1 DOWNTO middle))
+ cnt(ai(middle-1 DOWNTO 0));
ELSE
IF ai(0)='1' THEN nmb:=1; ELSE nmb:=0; END IF;
END IF;
RETURN nmb;
END cnt;
BEGIN
res <= cnt(data)=2;
END behaviour;
The function cnt is recursive to force a tree like structure.
On a Virtex v1000efg900 is needed 551 Slice (of 12288).
path delay 40 ns.
Egbert Molenkamp
"Yves Tchapda" <yves.t...@phyworks-ic.com> wrote in message
news:434d10fb.02062...@posting.google.com...