A good way to encode a 1024 one-hot vector into binary?

[Ryan]

I have a 1024 one-hot input that I am trying to encode. I've looked at
examples converting the 1024 to an unsigned integer, but 2^1024 seems
to not be working with the synthesis tool. I'm wondering if anyone has
a good loop for encoding a one-hot number without sending the whole
thing to an integer.

(I may piecemeal it, creating a modulus into more managable ranges and
then shift it back up, but I'm sure there's a better way. I'm also
afraid of getting too far from the hardware and doing it like a
software algorithm.)

I'm also concerned about going through all 1024 bits, since this will
priority encode it, when I know the output is one-hot.
Thanks for any suggestions.

 

[Weng Tianxiang]

Ryan,
Can you tell what conditions lead you to encode 1024 one-hot inputs.
1024 one-hot inputs mean that on any clock only one input is 1 and all
others 0.

If it can be avoided, you don't have to do it.

Weng

 

[Neo]

Ryan,
If what you have is the one hot vector, then I dont see how any
encoding can be done without going through all the 1024 bits. and also
priority is implicit when its looped.

 

[Jonathan Bromley]

I have a 1024 one-hot input that I am trying to encode. I've looked at
examples converting the 1024 to an unsigned integer, but 2^1024 seems
to not be working with the synthesis tool. I'm wondering if anyone has
a good loop for encoding a one-hot number without sending the whole
thing to an integer.
[...]
I'm also concerned about going through all 1024 bits, since this will
priority encode it, when I know the output is one-hot.

It's easy in principle; onehot-to-binary is just a tree of OR
gates for each of the 10 output bits. However, you'll make
rather a lot of OR gates... but you should get at most 10
levels of logic, probably fewer in a LUT-based FPGA.
I think we've done this one already here.

Here's a VHDL solution (I'm sure I've posted this one before).
It makes no attempt to check that the onehot code is valid,
but from your post I guess you know that's OK already.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity coder is
port (onehot: in std_logic_vector(1023 downto 0);
binary: out std_logic_vector(9 downto 0) );
end;

architecture proc of coder is
begin
process (onehot)
variable code: std_logic_vector(binary'RANGE);
begin
code := (others => '0');
for N in onehot'RANGE loop
if onehot(N) = '1' then
code := code OR std_logic_vector(to_unsigned(N, code'LENGTH));
end if;
end loop;
binary <= code;
end process;
end;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL, Verilog, SystemC, Perl, Tcl/Tk, Verification, Project Services

Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, BH24 1AW, UK
Tel: +44 (0)1425 471223 mail:[email protected]
Fax: +44 (0)1425 471573 Web: http://www.doulos.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Brian Drummond]

I have a 1024 one-hot input that I am trying to encode. I've looked at
examples converting the 1024 to an unsigned integer, but 2^1024 seems
to not be working with the synthesis tool. I'm wondering if anyone has
a good loop for encoding a one-hot number without sending the whole
thing to an integer.

(I may piecemeal it, creating a modulus into more managable ranges and
then shift it back up, but I'm sure there's a better way. I'm also
afraid of getting too far from the hardware and doing it like a
software algorithm.)

I'm also concerned about going through all 1024 bits, since this will
priority encode it, when I know the output is one-hot.
Thanks for any suggestions.

Looks like a recursive tree of gates (LUTs) with 512 inputs, for each of
ten output bits.

One LUT will encode 4 bits, 4+1=5 LUTs will encode 16, 4*5+1 = 21 LUTs
will encode 64 bits, and so on. I make it 171 LUTs per output bit, 1710
total, with a logic depth of 5 LUTs (and a LOT of routing!) to give you
a rough estimate of speed.

If it needs to run much over 50 MHz you may need to pipeline it...

If the synthesis tool doesn't generate something like this from
Jonathan's little loop, you may need a recursive solution using
"generate" statements.

- Brian

 

[Neo]

but jonathan, I didnt get the or logic in the loop. why cant we just
convert that N when the bit is '1' to std_logic??

 

[Jonathan Bromley]

but jonathan, I didnt get the or logic in the loop. why cant we just
convert that N when the bit is '1' to std_logic??

sorry, I am not clear what you're asking!

I suggest you take my design, shrink its ports to something
nice and small (8 bits in, 3 bits out?) and then simulate
and synthesise it so you can see how it works. I promise
you, it DOES work! As Brian said, there may be synthesis
optimisation issues - but my experience with mainstream
synth tools has been that they generally get it right.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL, Verilog, SystemC, Perl, Tcl/Tk, Verification, Project Services

Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, BH24 1AW, UK
Tel: +44 (0)1425 471223 mail:[email protected]
Fax: +44 (0)1425 471573 Web: http://www.doulos.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Neo]

yes it simulates and also synthesizes but what I asked is- why is the
code 'or' ed inside the for loop. why cant we just take the expression
std_logic_vector(to_unsigned(N, code'LENGTH)).
I tried without that oring, it still simulates properly and also
synthesizes the same way except for a few more gates.(I used 32 bit
vector)

 

[Jonathan Bromley]

yes it simulates and also synthesizes but what I asked is- why is the
code 'or' ed inside the for loop. why cant we just take the expression
std_logic_vector(to_unsigned(N, code'LENGTH)).
I tried without that oring, it still simulates properly and also
synthesizes the same way except for a few more gates.(I used 32 bit
vector)

OK, I see what you mean.

Without the OR operator, you get priority logic. If more than one
bit is set, each new '1' bit that the logic sees must override the
effect of other '1' bits and you get the binary code corresponding
to the highest-numbered bit that is set. The overhead of that
extra priority logic would be huge in a 1K-bit encoder.

With the OR operator, you get a fully parallel implementation.
If more than one bit in the input is set, the output will be
garbage. But we don't care about that, because we know that
the input code is one-hot.

Hope this helps
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL, Verilog, SystemC, Perl, Tcl/Tk, Verification, Project Services

Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, BH24 1AW, UK
Tel: +44 (0)1425 471223 mail:[email protected]
Fax: +44 (0)1425 471573 Web: http://www.doulos.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Ryan]

I haven't tried it yet, but just looking at it, I'm certain it will
work. I kept approaching this from the perspective of the math being
accomplished, which kept giving me priority encoding. Thanks for
providing me the elegant solution made from the perspective of the
logic.

For what I'm working with, I have an application that writes serially
into many small RAMs(only one at a time), and reads from each RAM in
parallel and combines them as one big word(1024 bits). The nature of
the writing ensures the data read is always one-hot. It all worked
nicely except for this conversion.

Many thanks.