Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > VHDL > determining of the position of the MSB

Reply
Thread Tools

determining of the position of the MSB

 
 
Jonathan Bromley
Guest
Posts: n/a
 
      07-28-2004
On Tue, 27 Jul 2004 12:03:28 -0700, "Symon" <(E-Mail Removed)>
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:(E-Mail Removed)
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.
 
Reply With Quote
 
 
 
 
Jonathan Bromley
Guest
Posts: n/a
 
      07-28-2004
On Tue, 27 Jul 2004 19:37:07 +0200, Johan Bernspång <(E-Mail Removed)>
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:(E-Mail Removed)
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.
 
Reply With Quote
 
 
 
 
Allan Herriman
Guest
Posts: n/a
 
      07-28-2004
On Wed, 28 Jul 2004 09:10:37 +0100, Jonathan Bromley
<(E-Mail Removed)> wrote:

>On Tue, 27 Jul 2004 12:03:28 -0700, "Symon" <(E-Mail Removed)>
>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.
 
Reply With Quote
 
=?ISO-8859-1?Q?Johan_Bernsp=E5ng?=
Guest
Posts: n/a
 
      07-28-2004
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 <(E-Mail Removed)>
> 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, http://www.velocityreviews.com/forums/(E-Mail Removed)
 
Reply With Quote
 
Symon
Guest
Posts: n/a
 
      07-29-2004
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" <(E-Mail Removed)> wrote in
message news:(E-Mail Removed)...
> On Wed, 28 Jul 2004 09:10:37 +0100, Jonathan Bromley
> <(E-Mail Removed)> 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.



 
Reply With Quote
 
Symon
Guest
Posts: n/a
 
      07-29-2004
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" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> for example, converting the collection of bits into a
> thermometer code, which is very easy to re-code as binary.
>



 
Reply With Quote
 
Jonathan Bromley
Guest
Posts: n/a
 
      07-30-2004
On Thu, 29 Jul 2004 10:42:38 -0700, "Symon" <(E-Mail Removed)>
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" <(E-Mail Removed)> wrote in message
>news:(E-Mail Removed).. .
>> 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:(E-Mail Removed)
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.
 
Reply With Quote
 
Michael Riepe
Guest
Posts: n/a
 
      07-30-2004
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 <(E-Mail Removed)-hannover.de>
"All I wanna do is have a little fun before I die"
 
Reply With Quote
 
Symon
Guest
Posts: n/a
 
      07-30-2004
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" <(E-Mail Removed)-hannover.de> wrote in message
news:cedtg8$6oo$(E-Mail Removed)-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 <(E-Mail Removed)-hannover.de>
> "All I wanna do is have a little fun before I die"



 
Reply With Quote
 
Jonathan Bromley
Guest
Posts: n/a
 
      08-02-2004
On Fri, 30 Jul 2004 09:22:27 +0100, Jonathan Bromley
<(E-Mail Removed)> wrote:

>On Thu, 29 Jul 2004 10:42:38 -0700, "Symon" <(E-Mail Removed)>


> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Parsing long with MSB set using Long.parseLong() sameergn@gmail.com Java 0 06-07-2005 06:49 AM
Implemenation Indepdent Way to Move LSByte of Char to MSB of Int, etc no spam C Programming 29 01-24-2005 04:06 AM
convert a double keeping msb ? DanSteph C++ 12 06-26-2004 05:00 PM
GMP and finding MSB of type mpz_t Ernst Berg C Programming 6 12-12-2003 09:33 AM
How to get the MSB? Andi Hotz C++ 3 11-21-2003 07:30 PM



Advertisments