determining of the position of the MSB

Discussion in 'VHDL' started by =?ISO-8859-1?Q?Johan_Bernsp=E5ng?=, Jul 27, 2004.

  1. I have a signal of an arbitrary width (say 16, but not necessarily a
    width that is a power of two) which is unsigned. I want to determine the
    position of the most significant (set) bit, i.e. the position of the
    highest '1'.

    The brute force method for this would be something like this, but I
    doubt it is the most efficient method. Any ideas what would improve the
    design in terms of device utilization?

    bitwidth_calc : process(clk) is
    begin
    if rising_edge(clk) then
    if new_data = '1' then
    for i in current_data'range loop
    if current_data(current_data'high - i) = '1' then
    bit_width <= (current_data'length - i);
    end if;
    end loop;
    else
    bit_width <= (others => '0');
    end if;
    end if;
    end process;

    regards
    johan

    --
    -----------------------------------------------
    Please remove the x's in the email address if
    replying to me personally.

    Johan Bernspång,
     
    =?ISO-8859-1?Q?Johan_Bernsp=E5ng?=, Jul 27, 2004
    #1
    1. Advertising

  2. Hi Johan,

    Look for project f-cpu on the net, someone have made a very powerfull
    design to solve this.
    I haven't the link to the given code page, but I can send it when I
    found it back.

    JaI

    Johan Bernspång wrote:

    > I have a signal of an arbitrary width (say 16, but not necessarily a
    > width that is a power of two) which is unsigned. I want to determine
    > the position of the most significant (set) bit, i.e. the position of
    > the highest '1'.
    >
    > The brute force method for this would be something like this, but I
    > doubt it is the most efficient method. Any ideas what would improve
    > the design in terms of device utilization?
    >
    > bitwidth_calc : process(clk) is
    > begin
    > if rising_edge(clk) then
    > if new_data = '1' then
    > for i in current_data'range loop
    > if current_data(current_data'high - i) = '1' then
    > bit_width <= (current_data'length - i);
    > end if;
    > end loop;
    > else
    > bit_width <= (others => '0');
    > end if;
    > end if;
    > end process;
    >
    > regards
    > johan
    >
     
    Just an Illusion, Jul 27, 2004
    #2
    1. Advertising

  3. On Tue, 27 Jul 2004 14:20:32 +0200, Johan Bernspång <>
    wrote:

    >I have a signal of an arbitrary width (say 16, but not necessarily a
    >width that is a power of two) which is unsigned. I want to determine the
    >position of the most significant (set) bit, i.e. the position of the
    >highest '1'.


    There's a recursive solution to this, which works fairly well
    for modest widths. The following description makes good sense
    if the number of bits is a power of 2; if not, you'll need to
    pad the width to an exact power of 2 with leading zeros.
    Synthesis tools would get rid of lots of unwanted logic
    in this case, because so many inputs are known to be zero.

    function top_bit_position(bunch_of_bits):
    if (N = 2)
    result := (upper bit of the two bits)
    elsif (any bit in the upper half is set)
    result := '1' & top_bit_position(upper_half_of_bunch_of_bits)
    else
    result := '0' & top_bit_position(lower_half_of_bunch_of_bits)

    This synthesises to piles of wide OR functions and a few
    multiplexers. Its speed is likely to be dominated by the
    speed of wide OR functions in your chosen technology -
    the multiplexers are small and simple.

    I'll post the code if anyone's interested.

    There *should* be some nice elegant solution based on using
    FPGA ripple carry chains, but I've not yet worked out how
    to do that. Any experts on Brand A / Brand X please speak up.
    --
    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, Jul 27, 2004
    #3
  4. Jonathan Bromley wrote:

    > I'll post the code if anyone's interested.

    I'm very interested, indeed. I think your solution looks interesting,
    it's going to be interesting to see if it requires less space on the
    device than my brute force method or not.

    >
    > There *should* be some nice elegant solution based on using
    > FPGA ripple carry chains, but I've not yet worked out how
    > to do that. Any experts on Brand A / Brand X please speak up.

    There always seem to be a more elegant solution, doesn't it?


    JaI, I couldn't find the specific code page you mentioned. I'd be happy
    if you could send me the link when you have some time to spare.

    /Johan

    --
    -----------------------------------------------
    Please remove the x's in the email address if
    replying to me personally.

    Johan Bernspång,
     
    =?ISO-8859-1?Q?Johan_Bernsp=E5ng?=, Jul 27, 2004
    #4
  5. On Tue, 27 Jul 2004 17:08:04 +0200, Johan
    Bernspång <> wrote:

    >Jonathan Bromley wrote:

    [recursive solution to find-the-topmost-1-bit]

    >> I'll post the code if anyone's interested.

    >I'm very interested, indeed. I think your solution looks interesting,
    >it's going to be interesting to see if it requires less space on the
    >device than my brute force method or not.


    Targeting Spartan-2 and using a well-known FPGA synthesis tool,
    the LUT count is as follows:

    number of number of
    input bits LUTs
    4 2
    8 6
    16 16
    32 35
    64 78
    128 167

    so you can see that, for reasonable-size input, the area
    is remarkably close to proportional to the number of inputs.
    Dunno how that compares with yours.

    Absolutely no promises that this code is 100% correct,
    and no promises that it compiles with all possible tools -
    for example, Synopsys DC chokes on the "while" loop in
    function bits_to_fit, even though that function is used
    only to compute constants.

    All the important work happens in function "topbit".
    At the end there's a very simple example of how you
    might use that function in a design.

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

    package topbit_pkg is
    function topbit (p : std_logic_vector) return std_logic_vector;
    end;


    package body topbit_pkg is

    --------------------------- Internal functions ---

    -- bits_to_fit:
    -- one of many possible ways to compute the number of bits
    -- required to represent N as an unsigned integer
    --
    function bits_to_fit(n: positive) return natural is
    variable nn: natural;
    variable bits: natural;
    begin
    nn := n;
    bits := 0;
    while nn > 0 loop
    bits := bits+1;
    nn := nn/2;
    end loop;
    return bits;
    end;

    -- or_all:
    -- given a std_logic_vector, OR all its bits together
    -- and return the single-bit result
    --
    function or_all(p: std_logic_vector) return std_logic is
    variable r: std_logic;
    begin
    r := '0';
    for i in p'range loop
    r := r or p(i);
    end loop;
    return r;
    end;

    ------------------------------- Public functions ---

    -- topbit:
    -- return the bit number of the most significant bit that is
    -- set in a std_logic_vector. Note that the bits are ALWAYS
    -- numbered so that the LSB is bit 0 and the MSB is bit n-1,
    -- regardless of the bit numbering scheme in your original vector.
    -- Note also that this function will return the result 0 in two
    -- different cases: when the LSB only is set, and when no bits
    -- at all are set. To disambiguate these two cases, you need to
    -- concatenate one extra bit on the LSB end of the input vector.
    --
    function topbit (p : std_logic_vector) return std_logic_vector is

    -- Number of bits required to represent the result
    constant wN: positive := bits_to_fit(p'length-1);

    -- Number of input bits, rounded up to an exact power of 2
    constant wP: positive := 2**wN;

    -- Input vector, widened to have wP bits, bit numbers normalised
    variable pv: std_logic_vector(wP-1 downto 0);

    -- Temporary variable for the result
    variable n: std_logic_vector(wN downto 1);

    begin

    if p'length <= 2 then

    -- Degenerate case of only 2 input bits: easy
    n(n'right) := p(p'left);

    else -- p'length > 2, we must divide it into pieces

    -- Make a normalised version of the input
    pv := (others => '0');
    pv(p'length-1 downto 0) := p;

    -- If any bits at all are set in the top half...
    if or_all(pv(wP-1 downto wP/2)) = '1' then

    -- MSB of result is '1', LSBs determined by upper half
    n := '1' & topbit(pv(wP-1 downto wP/2));

    else -- no bits in the top half are set

    -- MSB of result is '0', LSBs determined by lower half
    n := '0' & topbit(pv(wP/2-1 downto 0));

    end if;

    end if;

    return n;

    end;

    end;


    -------------------- Example entity that uses the function
    library ieee;
    use ieee.std_logic_1164.all;
    use work.topbit_pkg.all;

    entity nbits_e is
    port (
    p: in std_logic_vector(31 downto 0);
    q: out std_logic_vector(4 downto 0)
    );
    end;

    architecture a of nbits_e is
    begin
    q <= topbit(p);
    end;
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    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, Jul 27, 2004
    #5
  6. On Tue, 27 Jul 2004 14:20:32 +0200, Johan Bernspång
    <> wrote:

    >I have a signal of an arbitrary width (say 16, but not necessarily a
    >width that is a power of two) which is unsigned. I want to determine the
    >position of the most significant (set) bit, i.e. the position of the
    >highest '1'.


    Just a thought: There's a cutesy-tricksy method based on the fact
    that the logical AND of any binary number with its twos complement
    gives you a one-hot value with the "hot" bit at the position of
    the LEAST significant 1 bit of the original vector. For example:

    original value 101100100
    2s complement 010011100
    (logical AND) &&&&&&&&&
    000000100

    This value can then be fed into your favourite onehot-to-binary
    converter circuit (just a large bunch of OR gates) to get the
    required bit number.

    To solve your original problem - find the MOST significant bit -
    you need to reverse the original bit-pattern before doing this.

    This method is appealing because it automatically exploits
    the FPGA's fast carry chain to generate the 2s complement
    value (arithmetic negative). So it should be fast.

    However, when I tried it just now, on a 32-bit vector,
    it came out about twice as large as, and 30% slower than,
    the recursive solution I've posted. :-(

    It's still a pretty little property of binary numbers, though.
    --
    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, Jul 27, 2004
    #6
  7. Hi Jonathan and everybody else,

    My implementation (highly influenced by your earlier post) requires
    similar, but less impressive, figures as yours from my Virtex-II (I'm
    using XST for synthesis). I.e. 3 LUTs for 4 input bits and 21 LUTs for
    16 input bits and 223 LUTs for 128 input bits.

    It works almost as it should (I'll have a deeper look at it tomorrow)
    when I verify the functionality with ChipScope, but it seem to do some
    error in some places

    My code is attached if anyone's interested to look at it..

    johan

    Jonathan Bromley wrote:
    > On Tue, 27 Jul 2004 17:08:04 +0200, Johan
    > Bernspång <> wrote:
    >
    >
    >>Jonathan Bromley wrote:

    >
    > [recursive solution to find-the-topmost-1-bit]
    >
    >
    >>>I'll post the code if anyone's interested.

    >>
    >>I'm very interested, indeed. I think your solution looks interesting,
    >>it's going to be interesting to see if it requires less space on the
    >>device than my brute force method or not.

    >
    >
    > Targeting Spartan-2 and using a well-known FPGA synthesis tool,
    > the LUT count is as follows:
    >
    > number of number of
    > input bits LUTs
    > 4 2
    > 8 6
    > 16 16
    > 32 35
    > 64 78
    > 128 167
    >
    > so you can see that, for reasonable-size input, the area
    > is remarkably close to proportional to the number of inputs.
    > Dunno how that compares with yours.
    >
    > Absolutely no promises that this code is 100% correct,
    > and no promises that it compiles with all possible tools -
    > for example, Synopsys DC chokes on the "while" loop in
    > function bits_to_fit, even though that function is used
    > only to compute constants.
    >
    > All the important work happens in function "topbit".
    > At the end there's a very simple example of how you
    > might use that function in a design.
    >
    > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    > library ieee;
    > use ieee.std_logic_1164.all;
    >
    > package topbit_pkg is
    > function topbit (p : std_logic_vector) return std_logic_vector;
    > end;
    >
    >
    > package body topbit_pkg is
    >
    > --------------------------- Internal functions ---
    >
    > -- bits_to_fit:
    > -- one of many possible ways to compute the number of bits
    > -- required to represent N as an unsigned integer
    > --
    > function bits_to_fit(n: positive) return natural is
    > variable nn: natural;
    > variable bits: natural;
    > begin
    > nn := n;
    > bits := 0;
    > while nn > 0 loop
    > bits := bits+1;
    > nn := nn/2;
    > end loop;
    > return bits;
    > end;
    >
    > -- or_all:
    > -- given a std_logic_vector, OR all its bits together
    > -- and return the single-bit result
    > --
    > function or_all(p: std_logic_vector) return std_logic is
    > variable r: std_logic;
    > begin
    > r := '0';
    > for i in p'range loop
    > r := r or p(i);
    > end loop;
    > return r;
    > end;
    >
    > ------------------------------- Public functions ---
    >
    > -- topbit:
    > -- return the bit number of the most significant bit that is
    > -- set in a std_logic_vector. Note that the bits are ALWAYS
    > -- numbered so that the LSB is bit 0 and the MSB is bit n-1,
    > -- regardless of the bit numbering scheme in your original vector.
    > -- Note also that this function will return the result 0 in two
    > -- different cases: when the LSB only is set, and when no bits
    > -- at all are set. To disambiguate these two cases, you need to
    > -- concatenate one extra bit on the LSB end of the input vector.
    > --
    > function topbit (p : std_logic_vector) return std_logic_vector is
    >
    > -- Number of bits required to represent the result
    > constant wN: positive := bits_to_fit(p'length-1);
    >
    > -- Number of input bits, rounded up to an exact power of 2
    > constant wP: positive := 2**wN;
    >
    > -- Input vector, widened to have wP bits, bit numbers normalised
    > variable pv: std_logic_vector(wP-1 downto 0);
    >
    > -- Temporary variable for the result
    > variable n: std_logic_vector(wN downto 1);
    >
    > begin
    >
    > if p'length <= 2 then
    >
    > -- Degenerate case of only 2 input bits: easy
    > n(n'right) := p(p'left);
    >
    > else -- p'length > 2, we must divide it into pieces
    >
    > -- Make a normalised version of the input
    > pv := (others => '0');
    > pv(p'length-1 downto 0) := p;
    >
    > -- If any bits at all are set in the top half...
    > if or_all(pv(wP-1 downto wP/2)) = '1' then
    >
    > -- MSB of result is '1', LSBs determined by upper half
    > n := '1' & topbit(pv(wP-1 downto wP/2));
    >
    > else -- no bits in the top half are set
    >
    > -- MSB of result is '0', LSBs determined by lower half
    > n := '0' & topbit(pv(wP/2-1 downto 0));
    >
    > end if;
    >
    > end if;
    >
    > return n;
    >
    > end;
    >
    > end;
    >
    >
    > -------------------- Example entity that uses the function
    > library ieee;
    > use ieee.std_logic_1164.all;
    > use work.topbit_pkg.all;
    >
    > entity nbits_e is
    > port (
    > p: in std_logic_vector(31 downto 0);
    > q: out std_logic_vector(4 downto 0)
    > );
    > end;
    >
    > architecture a of nbits_e is
    > begin
    > q <= topbit(p);
    > end;
    > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    >
    > Hope this helps



    --
    -----------------------------------------------
    Please remove the x's in the email address if
    replying to me personally.

    Johan Bernspång,

    library IEEE;
    use IEEE.STD_LOGIC_1164.ALL;
    use IEEE.NUMERIC_STD.ALL;
    use IEEE.STD_LOGIC_UNSIGNED.ALL;

    entity bitwidth is
    generic (
    C_WIDTH : integer := 16
    );
    port (
    clk : in std_logic;
    rst : in std_logic;
    data : in std_logic_vector(C_WIDTH - 1 downto 0);
    dwidth : out std_logic_vector(3 downto 0)
    );
    end entity bitwidth;

    architecture imp of bitwidth is

    signal new_data : std_logic;
    signal current_data : std_logic_vector(C_WIDTH - 1 downto 0);
    signal new_bit_width : std_logic;
    signal bit_width : integer range 0 to C_WIDTH-1;
    signal max_bit_width : integer range 0 to C_WIDTH-1;

    function top_bit_position(data_in : in std_logic_vector) return integer is
    variable result : integer;
    begin
    if data_in'length = 2 then
    if data_in(data_in'high) = '1' then
    result := 1;
    else
    result := 0;
    end if;
    elsif data_in(data_in'high downto data_in'length/2) > 0 then
    result := (data_in'length/2 - 1) + top_bit_position(data_in(data_in'high downto data_in'length/2));
    else
    result := top_bit_position(data_in(data_in'length/2 - 1 downto 0));
    end if;
    return result;
    end;
    begin
    read_adc_proc : process(clk) is
    begin
    if rising_edge(clk) then
    if data(data'high) = '0' then --only look at positive samples
    current_data <= data;
    new_data <= '1';
    else
    current_data <= current_data;
    new_data <= '0';
    end if;
    end if;
    end process;

    bitwidth_calc : process(clk) is
    variable bit_pos : integer range 0 to C_WIDTH-1;
    begin
    if rising_edge(clk) then
    if new_data = '1' then
    bit_pos := top_bit_position(current_data);
    new_bit_width <= '1';
    else
    bit_pos := 0;
    new_bit_width <= '0';
    end if;
    bit_width <= bit_pos;
    end if;
    end process;

    dwidth <= std_logic_vector(to_unsigned(bit_width, 4));
    end architecture imp;
     
    =?ISO-8859-1?Q?Johan_Bernsp=E5ng?=, Jul 27, 2004
    #7
  8. Hi,

    Jonathan Bromley wrote:
    > On Tue, 27 Jul 2004 14:20:32 +0200, Johan Bernspång
    > <> wrote:
    >
    >
    >>I have a signal of an arbitrary width (say 16, but not necessarily a
    >>width that is a power of two) which is unsigned. I want to determine the
    >>position of the most significant (set) bit, i.e. the position of the
    >>highest '1'.

    >
    >
    > Just a thought: There's a cutesy-tricksy method based on the fact
    > that the logical AND of any binary number with its twos complement
    > gives you a one-hot value with the "hot" bit at the position of
    > the LEAST significant 1 bit of the original vector. For example:
    >
    > original value 101100100
    > 2s complement 010011100
    > (logical AND) &&&&&&&&&
    > 000000100
    >
    > This value can then be fed into your favourite onehot-to-binary
    > converter circuit (just a large bunch of OR gates) to get the
    > required bit number.
    >
    > To solve your original problem - find the MOST significant bit -
    > you need to reverse the original bit-pattern before doing this.
    >

    To Johan,
    If I well remember the solution take by f-cpu project is based on this
    approach

    ><snip>


    JaI
     
    Just an Illusion, Jul 27, 2004
    #8
  9. Hi,

    Johan Bernspång wrote:

    > Jonathan Bromley wrote:
    >
    ><snip>
    > JaI, I couldn't find the specific code page you mentioned. I'd be happy
    > if you could send me the link when you have some time to spare.
    >
    > /Johan
    >


    The web site address is www.f-cpu.org

    The vhdl source is in the directory new, but inside a snapshot archive.

    I don't remember exactly in which one, and unfortunately I haven't time
    to browse all of them to find who have made it.

    Try to see in mailing list archive http://archives.seul.org/f-cpu/f-cpu/
    Unfortunately this archive haven't search engine, but I think that you
    can found a comment into 2002 archives.

    Or keep solution by Johnatan Bromley.

    JaI
     
    Just an Illusion, Jul 27, 2004
    #9
  10. =?ISO-8859-1?Q?Johan_Bernsp=E5ng?=

    Symon Guest

    Hi Jonathan,
    You can implement the wide OR gates with the carry logic. Each four bit
    chunk of the OR gate is a 4 input NOR made in the CLB 4-LUT which feeds the
    select input of the MUXCY. The Ci input of the MUXCY comes from the previous
    four bit chunk, Lo goes to the next chunk. The Di input of the MUXCY is
    driven to '1'. If you do it this way, the total number of LUTs ~=
    0.25*number of bits in the OR gate.
    Cheers, Syms.
    p.s. See MUXCY_L in the Xilinx libraries guide

    "Jonathan Bromley" <> wrote in message
    news:...
    > There *should* be some nice elegant solution based on using
    > FPGA ripple carry chains, but I've not yet worked out how
    > to do that. Any experts on Brand A / Brand X please speak up.
     
    Symon, Jul 27, 2004
    #10
  11. On Tue, 27 Jul 2004 12:03:28 -0700, "Symon" <>
    wrote:

    >Hi Jonathan,
    >You can implement the wide OR gates with the carry logic.


    Yeah. Various other stuff can be done in the MUXCYs too;
    for example, converting the collection of bits into a
    thermometer code, which is very easy to re-code as binary.

    However, as I'm not a Xilinx synthesis guru I don't know how
    to persuade synthesis tools to do this (if it's possible at
    all). Any ideas? (I'd ask our Xilinx experts here in the
    office, but they're all away doing other stuff right now!)
    --
    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, Jul 28, 2004
    #11
  12. On Tue, 27 Jul 2004 19:37:07 +0200, Johan Bernspång <>
    wrote:

    >My code is attached if anyone's interested to look at it..


    and it contains the highly suggestive process name

    read_adc_proc:

    Is this a hint? Are you capturing the comparator outputs
    in a flash A/D converter? If so, your find-first-bit
    problem is MUCH simpler, because the flash A/D comparator
    outputs form a thermometer code: if a given bit is set
    then you know in advance that all lower bits are set.
    My solution still works, but the or_all() function is
    unnecessary; you need only look at the lowest bit of
    the value, instead of the OR of all its bits. This
    will give a much smaller and faster solution.
    --
    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, Jul 28, 2004
    #12
  13. On Wed, 28 Jul 2004 09:10:37 +0100, Jonathan Bromley
    <> wrote:

    >On Tue, 27 Jul 2004 12:03:28 -0700, "Symon" <>
    >wrote:
    >
    >>Hi Jonathan,
    >>You can implement the wide OR gates with the carry logic.

    >
    >Yeah. Various other stuff can be done in the MUXCYs too;
    >for example, converting the collection of bits into a
    >thermometer code, which is very easy to re-code as binary.
    >
    >However, as I'm not a Xilinx synthesis guru I don't know how
    >to persuade synthesis tools to do this (if it's possible at
    >all). Any ideas? (I'd ask our Xilinx experts here in the
    >office, but they're all away doing other stuff right now!)


    Easy: just instantiate the relevant Xilinx unisim primitives in the
    HDL source. It's portable over all synthesisers (except those that
    think they understand the primitives and try to "optimise" them - I've
    had problems with various versions of Synplify) and also simulates
    correctly (if slowly).

    Regards,
    Allan.
     
    Allan Herriman, Jul 28, 2004
    #13
  14. Yes, I'm looking at the data coming from an ADC. I do believe, though,
    that the data is coded as twos complement and not as thermometer code.
    Thus, it is not a flash ADC.

    Another idea I have is to use your recursive method and just calculate
    the number of zeros in the MSBs. What I want is a figure on the
    magnitude of the data to send to the software that receives the
    processed data. I'm not sure if it would require less logic to calculate
    the number of zeros instead of calculating the position of the first
    '1'. I guess I just have to try...

    I'm still interested in finding the optimal solution since the customer
    of the design wants to know the signal 'strenght' in different parts of
    the system, and there might be multiple systems on the same FPGA etc.

    /johan


    Jonathan Bromley wrote:

    > On Tue, 27 Jul 2004 19:37:07 +0200, Johan Bernspång <>
    > wrote:
    >
    >
    >>My code is attached if anyone's interested to look at it..

    >
    >
    > and it contains the highly suggestive process name
    >
    > read_adc_proc:
    >
    > Is this a hint? Are you capturing the comparator outputs
    > in a flash A/D converter? If so, your find-first-bit
    > problem is MUCH simpler, because the flash A/D comparator
    > outputs form a thermometer code: if a given bit is set
    > then you know in advance that all lower bits are set.
    > My solution still works, but the or_all() function is
    > unnecessary; you need only look at the lowest bit of
    > the value, instead of the OR of all its bits. This
    > will give a much smaller and faster solution.



    --
    -----------------------------------------------
    Please remove the x's in the email address if
    replying to me personally.

    Johan Bernspång,
     
    =?ISO-8859-1?Q?Johan_Bernsp=E5ng?=, Jul 28, 2004
    #14
  15. =?ISO-8859-1?Q?Johan_Bernsp=E5ng?=

    Symon Guest

    That's how I do it, by instantiation. As you say Allan, the major problem
    with this kinda stuff is the tool trying to be clever. FCS, if I've gone to
    the trouble of instantiating primitives, isn't it obvious I know what I
    want? Bloody software engineers. ;-)
    Cheers, Syms.
    "Allan Herriman" <> wrote in
    message news:...
    > On Wed, 28 Jul 2004 09:10:37 +0100, Jonathan Bromley
    > <> wrote:
    >
    >
    > Easy: just instantiate the relevant Xilinx unisim primitives in the
    > HDL source. It's portable over all synthesisers (except those that
    > think they understand the primitives and try to "optimise" them - I've
    > had problems with various versions of Synplify) and also simulates
    > correctly (if slowly).
    >
    > Regards,
    > Allan.
     
    Symon, Jul 29, 2004
    #15
  16. =?ISO-8859-1?Q?Johan_Bernsp=E5ng?=

    Symon Guest

    OK, I'll bite! Do you mean the 'fat tree' method? Convert the thermometer
    code to one hot, then use a tree of OR gates to get binary code?
    Cheers, Syms.
    "Jonathan Bromley" <> wrote in message
    news:...
    > for example, converting the collection of bits into a
    > thermometer code, which is very easy to re-code as binary.
    >
     
    Symon, Jul 29, 2004
    #16
  17. On Thu, 29 Jul 2004 10:42:38 -0700, "Symon" <>
    wrote:

    >OK, I'll bite! Do you mean the 'fat tree' method? Convert the thermometer
    >code to one hot, then use a tree of OR gates to get binary code?
    >Cheers, Syms.
    >"Jonathan Bromley" <> wrote in message
    >news:...
    >> for example, converting the collection of bits into a
    >> thermometer code, which is very easy to re-code as binary.


    That works, for sure. But I think ther'es an easier way
    (though I haven't done systematic investigations about the
    speed or size implications). What I had in mind was a tree
    of 2-to-1 multiplexers.

    Suppose we have a thermometer code of N bits, such that 2**B = M.
    And suppose those bits are numbered from 0 to N-1, so for any
    given encoded value X, bits 0..X inclusive are set and bits
    X+1..N-1 are zero. We need an unsigned integer with B bits to
    represent the encoded value; let's label those bits B-1 downto 0
    in the conventional way.

    To VHDL-ise these objects:
    constant B: positive := ...;
    variable thm_code: std_logic_vector(0 to 2**B-1); -- thermo code
    variable bin_code: std_logic_vector(B-1 downto 0); -- binary value

    The topmost bit of the result is precisely the value of
    thm_code(2**(B-1)), 'coz that bit will be set if and only if
    we're encoding a value >= 2**(B-1).

    The remaining bits of the result are
    EITHER
    the thermometer code represented by thm_code(2**(B-1) to 2**B-1)
    (the upper half of thm_code) if bit 2**(B-1) is set
    OR
    the thermometer code represented by thm_code(0 to 2**(B-1)-1)
    (the lower half of thm_code) if bit 2**(B-1) is clear

    And so on until you run out of code bits. My delight in recursive
    solutions is showing itself again :)

    function thermo_decoder ( thm_code: std_logic_vector )
    return std_logic_vector is
    variable s: std_logic_vector(0 to 0);
    constant N: positive := thm_code'length;
    constant mid: natural := N / 2;
    begin
    -- protect against goofs
    assert thm_code'ascending and thm_code'left = 0;
    assert N >= 2;
    assert [N is an exact power of 2];
    -- pick the bit of interest
    s(0) := thm_code(mid);
    if thm_code'length = 2 then
    return s;
    elsif s(0) = '1' then
    return s & thermo_decoder(thm_code(mid to N-1));
    else
    return s & thermo_decoder(thm_code(0 to mid-1));
    end if;
    end;

    Stopping the recursion at length=2 spares us the need to
    use null ranges, which are a nice feature of VHDL but
    poorly supported by synthesis tools.

    A very quick-and-dirty attempt at synthesis for this, with
    256-bit thermometer code and 8-bit output and targeting
    Spartan-2, gave:
    LUTs delay
    mux tree 199 10ns
    "fat tree" 367 15ns

    I would guess that your OR-gate version could easily
    be made much faster by constructing the OR gates
    from chains of MUXCYs, but I don't know for sure.

    Any other ideas?
    --
    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, Jul 30, 2004
    #17
  18. Hi.

    Jonathan Bromley wrote:
    [...]
    > The topmost bit of the result is precisely the value of
    > thm_code(2**(B-1)), 'coz that bit will be set if and only if
    > we're encoding a value >= 2**(B-1).
    >
    > The remaining bits of the result are
    > EITHER
    > the thermometer code represented by thm_code(2**(B-1) to 2**B-1)
    > (the upper half of thm_code) if bit 2**(B-1) is set
    > OR
    > the thermometer code represented by thm_code(0 to 2**(B-1)-1)
    > (the lower half of thm_code) if bit 2**(B-1) is clear
    >
    > And so on until you run out of code bits. My delight in recursive
    > solutions is showing itself again :)


    That's a nice solution, but probably the second best one. The problem is
    that you'll have to get the thermometer code first. But you can also
    process the original operand directly:

    function findmsb (X : in std_ulogic_vector) return std_ulogic_vector is
    constant N : natural := X'length; -- assume it's a power of two
    constant xx : std_ulogic_vector(N-1 downto 0);
    begin
    xx := to_X01(X); -- convert to something more useful
    if N = 2 then
    return xx(1 downto 1);
    elsif xx(N-1 downto N/2) = (N-1 downto N/2 => '0') then
    -- lower half
    return '0' & findmsb(xx(N/2-1 downto 0));
    else
    -- upper half
    return '1' & findmsb(xx(N-1 downto N/2));
    end if;
    end findmsb;

    This should result in a MUX tree interleaved with an OR tree. The only
    drawback is that a zero operand and an operand with only the LSB set
    will have the same result (others => '0'). But you can change that by
    adding another MUX at the output:

    function findmsb2 (X : in std_ulogic_vector) return std_ulogic_vector is
    constant N : natural := X'length; -- assume it's a power of two
    constant xx : std_ulogic_vector(N-1 downto 0);
    begin
    xx := to_X01(X); -- convert to something more useful
    if xx(N-1) = '1' then
    -- Note: findmsb will always return a zero vector here.
    -- But it's easier to call findmsb than to calculate
    -- the required number of bits :)
    return '1' & findmsb(std_ulogic_vector'(N-1 downto 0 => '0'));
    else
    return '0' & findmsb(xx(N-2 downto 0) & '1');
    end if;
    end findmsb2;

    Now a zero operand produces a zero result, while all other inputs result
    in the index number of the MSB, counted from N downto 1 (left to right,
    as usual).

    Note: The code is provided without any warranty. Use at your own risk.

    --
    Michael "Tired" Riepe <-hannover.de>
    "All I wanna do is have a little fun before I die"
     
    Michael Riepe, Jul 30, 2004
    #18
  19. =?ISO-8859-1?Q?Johan_Bernsp=E5ng?=

    Symon Guest

    Hi Guys,
    I'll try and think about this more over the weekend, in between time I found
    this paper about the 'fat tree' decoder.
    http://www.cse.psu.edu/~chip/final_mwscas02.pdf
    Bits of the tree aren't needed and can be 'liposuctioned' away!

    I wonder if the mux solutions work so well in terms of LUT efficiency in the
    Xilinx parts because of the muxf5s in the CLBs?
    Interesting stuff, cheers, Syms.

    "Michael Riepe" <-hannover.de> wrote in message
    news:cedtg8$6oo$-hannover.de...
    > Hi.
    >
    > Jonathan Bromley wrote:
    > [...]
    > > The topmost bit of the result is precisely the value of
    > > thm_code(2**(B-1)), 'coz that bit will be set if and only if
    > > we're encoding a value >= 2**(B-1).
    > >
    > > The remaining bits of the result are
    > > EITHER
    > > the thermometer code represented by thm_code(2**(B-1) to 2**B-1)
    > > (the upper half of thm_code) if bit 2**(B-1) is set
    > > OR
    > > the thermometer code represented by thm_code(0 to 2**(B-1)-1)
    > > (the lower half of thm_code) if bit 2**(B-1) is clear
    > >
    > > And so on until you run out of code bits. My delight in recursive
    > > solutions is showing itself again :)

    >
    > That's a nice solution, but probably the second best one. The problem is
    > that you'll have to get the thermometer code first. But you can also
    > process the original operand directly:
    >
    > function findmsb (X : in std_ulogic_vector) return std_ulogic_vector is
    > constant N : natural := X'length; -- assume it's a power of two
    > constant xx : std_ulogic_vector(N-1 downto 0);
    > begin
    > xx := to_X01(X); -- convert to something more useful
    > if N = 2 then
    > return xx(1 downto 1);
    > elsif xx(N-1 downto N/2) = (N-1 downto N/2 => '0') then
    > -- lower half
    > return '0' & findmsb(xx(N/2-1 downto 0));
    > else
    > -- upper half
    > return '1' & findmsb(xx(N-1 downto N/2));
    > end if;
    > end findmsb;
    >
    > This should result in a MUX tree interleaved with an OR tree. The only
    > drawback is that a zero operand and an operand with only the LSB set
    > will have the same result (others => '0'). But you can change that by
    > adding another MUX at the output:
    >
    > function findmsb2 (X : in std_ulogic_vector) return std_ulogic_vector is
    > constant N : natural := X'length; -- assume it's a power of two
    > constant xx : std_ulogic_vector(N-1 downto 0);
    > begin
    > xx := to_X01(X); -- convert to something more useful
    > if xx(N-1) = '1' then
    > -- Note: findmsb will always return a zero vector here.
    > -- But it's easier to call findmsb than to calculate
    > -- the required number of bits :)
    > return '1' & findmsb(std_ulogic_vector'(N-1 downto 0 => '0'));
    > else
    > return '0' & findmsb(xx(N-2 downto 0) & '1');
    > end if;
    > end findmsb2;
    >
    > Now a zero operand produces a zero result, while all other inputs result
    > in the index number of the MSB, counted from N downto 1 (left to right,
    > as usual).
    >
    > Note: The code is provided without any warranty. Use at your own risk.
    >
    > --
    > Michael "Tired" Riepe <-hannover.de>
    > "All I wanna do is have a little fun before I die"
     
    Symon, Jul 30, 2004
    #19
  20. On Fri, 30 Jul 2004 09:22:27 +0100, Jonathan Bromley
    <> wrote:

    >On Thu, 29 Jul 2004 10:42:38 -0700, "Symon" <>


    > function thermo_decoder ( thm_code: std_logic_vector )

    [...]
    > -- protect against goofs
    > assert thm_code'ascending and thm_code'left = 0;

    [...]
    > elsif s(0) = '1' then
    > return s & thermo_decoder(thm_code(mid to N-1));
    > else
    > return s & thermo_decoder(thm_code(0 to mid-1));


    whoops, obviously the assert will fail on the next recursive
    call if s(0) = '1'. Sorry, I was trying to strip my
    test code to its bare essentials and stripped away
    just a little too much.

    Here's the code I actually tried:

    library ieee;
    use ieee.std_logic_1164.all;

    package thermo_pkg is

    function bits_to_fit(n: positive) return positive;

    function thermo_decode(code: std_logic_vector) return
    std_logic_vector;

    end;


    package body thermo_pkg is

    function bits_to_fit(n: positive) return positive is
    begin
    if n=1 then
    return 1;
    else
    return 1 + bits_to_fit(n/2);
    end if;
    end;

    function thermo_decode(code: std_logic_vector) return
    std_logic_vector is
    -- ASSUME: leftmost bit represents 0
    constant b: positive := bits_to_fit(code'length-1);
    constant n: positive := 2**b;
    variable full_code: std_logic_vector(0 to n-1);
    variable top_bit: std_logic_vector(b-1 downto b-1);
    begin
    full_code := (others => '0');
    full_code(0 to code'length-1) := code;
    top_bit := full_code(n/2 to n/2);
    if b = 1 then
    return top_bit;
    elsif full_code(n/2) = '1' then
    return top_bit & thermo_decode(full_code(n/2 to n-1));
    else
    return top_bit & thermo_decode(full_code(0 to (n/2)-1));
    end if;
    end;

    end;

    Apologies
    --
    Jonathan Bromley

    Jonathan Bromley
     
    Jonathan Bromley, Aug 2, 2004
    #20
    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. Replies:
    0
    Views:
    651
  2. Andi Hotz

    How to get the MSB?

    Andi Hotz, Nov 21, 2003, in forum: C++
    Replies:
    3
    Views:
    349
    Mike Wahler
    Nov 21, 2003
  3. DanSteph

    convert a double keeping msb ?

    DanSteph, Jun 24, 2004, in forum: C++
    Replies:
    12
    Views:
    1,956
    marbac
    Jun 26, 2004
  4. Ernst Berg

    GMP and finding MSB of type mpz_t

    Ernst Berg, Dec 6, 2003, in forum: C Programming
    Replies:
    6
    Views:
    532
    Ernst Berg
    Dec 12, 2003
  5. no spam
    Replies:
    29
    Views:
    753
    Dave Thompson
    Jan 24, 2005
Loading...

Share This Page