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

Discussion in 'VHDL' started by Ryan, Jan 27, 2005.

  1. Ryan

    Ryan Guest

    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.
     
    Ryan, Jan 27, 2005
    #1
    1. Advertising

  2. 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
     
    Weng Tianxiang, Jan 27, 2005
    #2
    1. Advertising

  3. Ryan

    Neo Guest

    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.
     
    Neo, Jan 28, 2005
    #3
  4. On 27 Jan 2005 13:43:27 -0800, "Ryan" <> wrote:

    >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:
    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.
     
    Jonathan Bromley, Jan 28, 2005
    #4
  5. On 27 Jan 2005 13:43:27 -0800, "Ryan" <> wrote:

    >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
     
    Brian Drummond, Jan 28, 2005
    #5
  6. Ryan

    Neo Guest

    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??
     
    Neo, Jan 28, 2005
    #6
  7. On 28 Jan 2005 06:27:25 -0800, "Neo" <> wrote:

    >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:
    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.
     
    Jonathan Bromley, Jan 28, 2005
    #7
  8. Ryan

    Neo Guest

    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)
     
    Neo, Jan 28, 2005
    #8
  9. On 28 Jan 2005 07:24:05 -0800, "Neo" <> wrote:

    >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:
    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.
     
    Jonathan Bromley, Jan 28, 2005
    #9
  10. Ryan

    Ryan Guest

    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.
     
    Ryan, Jan 31, 2005
    #10
    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. Anthony J Bybell
    Replies:
    0
    Views:
    714
    Anthony J Bybell
    Jan 28, 2005
  2. Tor Erik Sønvisen

    Most efficient way of storing 1024*1024 bits

    Tor Erik Sønvisen, Nov 2, 2005, in forum: Python
    Replies:
    15
    Views:
    524
    Alex Stapleton
    Nov 4, 2005
  3. Replies:
    8
    Views:
    1,939
    Csaba
    Feb 18, 2006
  4. mobi999
    Replies:
    0
    Views:
    763
    mobi999
    Jun 9, 2007
  5. Sandy Miller

    Java EE Developer-HOT HOT OPENINGS

    Sandy Miller, Jan 8, 2008, in forum: Java
    Replies:
    0
    Views:
    375
    Sandy Miller
    Jan 8, 2008
Loading...

Share This Page