efficient therm-2-bin algorithm

[vishallko31]

Hello

I am trying to implement a 'thermometric to binary' converter. I have a
vector of length 95.

I read each bit of it, then use 'conv_integer' function to convert the
bit into integer then add the integers together and finally convert the
resultant integer into std_logic using 'conv_std_logic_vector'
function.

This scheme is giving me a huge area...

Just wanted to know if there exists a better way to do this which is
more area-efficient...

Please advise

Regard
Vishal

 

[Ben Jones]

Hello

I am trying to implement a 'thermometric to binary' converter. I have a
vector of length 95.

What is "thermometric" number representation? I guess it looks like a
thermometer (a bunch of 1s, followed by a bunch of 0s)? So are you just
counting the bits in the input vector, or is it something else?

I read each bit of it, then use 'conv_integer' function to convert the
bit into integer then add the integers together and finally convert the
resultant integer into std_logic using 'conv_std_logic_vector'
function.
This scheme is giving me a huge area...

If you're doing what I think you're doing, the result will depend greatly on
the quality of your synthesis tool. I know Synplify Pro is reasonably good
at mapping something like this, but YMMV.

Just wanted to know if there exists a better way to do this which is
more area-efficient...

How quickly do you need your result to be produced?

If it's acceptable to take 95 clock cycles, then you can make a sequential
circuit based around a shift register (for the input data) and an
accumulator (which increments by 1 every time a '1' is seen in the input).
This will be pretty small.

If you need your result immediately (or at least you need to start a new
conversion every clock cycle), you might do better by initially re-coding
groups of input bits. For example, for a 4-input LUT-based FPGA architecture
you might have a number of small ROMs that contain a bit-count for a 4-bit
chunk of input, i.e.:

Addr Binary Bitcount
-----------------------
0 0000 0
1 0001 1
2 0010 1
3 0011 2
4 0100 1
5 0101 2
6 0110 2
7 0111 3
8 1000 1
9 1001 2
10 1010 2
11 1011 3
12 1100 2
13 1101 3
14 1110 3
15 1111 4

Then you can sum all these 3-bit integers as before. The most efficient
solution would use a tree of adders, rather than a chain (but your synthesis
tool may need some prodding in order to achieve that).

Good luck with your circuit!

-Ben-

 

[Andy]

You might try a brute force method to find the last one, and just see
how well your synthesis tool opitimizes logic, without adding.
Sometimes synthesis tools don't like to optimize adders too well, and
decoding the position of the last one (or the first zero) may be more
noise immune.

-- normalize input range:
variable vector : std_logic_vector(input'length downto 1);
....
vector := input;
output <= (others => '0'); -- initialize output
for i in vector'reverse_range loop -- assuming 'left is msb
if vector(i) = '1' then
output<= std_logic_vector(to_unsigned(i,output'length);
end if;
end loop;

Andy

 

[vishallko31]

Hi Ben

Thanks a lot for the mail...Yes thermometric representation means a
sequence of 1s followed by 0s.

What I need to do here is to count number of 1s in the given vector.

I need the output to be available as quickly as possible.

Right now the synthesis tool is giving me a delay of 8.5ns (which is
acceptable) and an areas of abt 6550 (including flip-flops from which
the vector is being generated).

I just wanted to know if I can implement it in a better way than what I
have done here..

I shall try what uve said...Actually, Im not targetting this onto an
FPGA...this is going to be clubbed into the Digital PLL that weve been
designing here.

Thanks for your reply anyways

regards
Vishal

 

[Ben Jones]

Hi Vishal,

Hi Ben

Thanks a lot for the mail...Yes thermometric representation means a
sequence of 1s followed by 0s.
What I need to do here is to count number of 1s in the given vector.
I need the output to be available as quickly as possible.

I had an interesting idea about this. Given the constraint that the input
vector has no "holes" in it (i.e. you get "11111000000" or "110000000" but
never "111001111"), you can do a very efficient parallel bit-count without
any adders.

First notice this: if you XOR together all the bits, this tells you whether
the bitcount is even (0) or odd (1). That gives you bit 0 of your result.

Now, if you XOR together every second bit, starting with the second bit,
you'll get bit 1 of your result. (When the thermometer reaches '2', the
value goes to 1; when it reaches '4', it goes back to 0; when it reaches
'6', it goes back to 1 again). Here I'm assuming the input vector starts at
1 - this makes more sense, since "1000" = 1, "1100" = 2, "1110" = 3, and so
on.

Carrying this pattern forward, you can XOR together every fourth bit
(starting with the fourth) to get bit 2, every eighth bit to get bit 3, and
so on until you have enough bits to represent the maximum value. The total
size of the circuit is roughly 2N xor gates (where N is the vector length).

The low-order bits take the most logic (and time) to implement. Still, while
a 96-bit XOR operation isn't free, it is pretty cheap and fast in most
technologies. The benefit of this scheme is that there are no carries
involved; each bit can be calculated in parallel, so it can go pretty fast.

Whatever you choose to do, good luck with your design!

-Ben-

 

[vishallko31]

Dear Ben

Many thanks for the great idea...I shall try it out...I think that my
application meets all the constraints you mentioned...

are you on orkut by any chance??


thanks again

Regards
Vishal

 

[vishallko31]

Hello

This time Im stuck with a similar problem where I need to do the
opposite.

I am designing a binary to thermometric bit converter.
Just to emphasise:

for example: If I have a binary number 011 then I would want 3 bit to
go one. ie. 111. If the number is five(101) then five bits should be
set to 1 (11111).

Can someone suggest an area-efficient scheme to achieve the same?

Regards
Vishal