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.