- **VHDL**
(*http://www.velocityreviews.com/forums/f18-vhdl.html*)

- - **determining of the position of the MSB**
(*http://www.velocityreviews.com/forums/t22702-determining-of-the-position-of-the-msb.html*)

determining of the position of the MSBI 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, xjohbex@xfoix.se |

Re: determining of the position of the MSBHi 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 > |

Re: determining of the position of the MSBOn Tue, 27 Jul 2004 14:20:32 +0200, Johan Bernspång <xjohbex@xfoix.se>
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:jonathan.bromley@doulos.com 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. |

Re: determining of the position of the MSBJonathan 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, xjohbex@xfoix.se |

Re: determining of the position of the MSBOn Tue, 27 Jul 2004 17:08:04 +0200, Johan
Bernspång <xjohbex@xfoix.se> 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:jonathan.bromley@doulos.com 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. |

Re: determining of the position of the MSBOn Tue, 27 Jul 2004 14:20:32 +0200, Johan Bernspång
<xjohbex@xfoix.se> 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:jonathan.bromley@doulos.com 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. |

Re: determining of the position of the MSBHi 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 <xjohbex@xfoix.se> 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, xjohbex@xfoix.se 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; |

Re: determining of the position of the MSBHi,
Jonathan Bromley wrote: > On Tue, 27 Jul 2004 14:20:32 +0200, Johan Bernspång > <xjohbex@xfoix.se> 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 |

Re: determining of the position of the MSBHi,
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 |

Re: determining of the position of the MSBHi 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" <jonathan.bromley@doulos.com> wrote in message news:9nocg0933dhad1mjqh62rufpvgtodceuk2@4ax.com... > 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. |

All times are GMT. The time now is 10:20 PM. |

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.