efficient therm-2-bin algorithm

Discussion in 'VHDL' started by vishallko31@gmail.com, May 22, 2006.

  1. Guest

    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
    , May 22, 2006
    #1
    1. Advertising

  2. Ben Jones Guest

    <> wrote in message
    news:...
    > 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-
    Ben Jones, May 22, 2006
    #2
    1. Advertising

  3. Andy Guest

    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
    Andy, May 22, 2006
    #3
  4. Guest

    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
    , May 23, 2006
    #4
  5. Ben Jones Guest

    Hi Vishal,

    <> wrote in message
    news:...
    > 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-
    Ben Jones, May 23, 2006
    #5
  6. Guest

    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
    , May 27, 2006
    #6
  7. Guest

    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




    wrote:
    > 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
    , Jun 13, 2006
    #7
    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. Kevin Mitchell

    Can "bin" be changed to "cgi-bin" for asp.net

    Kevin Mitchell, Oct 19, 2003, in forum: ASP .Net
    Replies:
    3
    Views:
    815
    Wim Hollebrandse
    Oct 19, 2003
  2. John Salerno
    Replies:
    30
    Views:
    1,951
    Stephan Kuhagen
    Aug 10, 2006
  3. sweety
    Replies:
    9
    Views:
    1,022
    Richard Heathfield
    Feb 7, 2006
  4. Yves Dorfsman

    #!/usr/bin/env python vs. #!/usr/bin/python

    Yves Dorfsman, May 2, 2008, in forum: Python
    Replies:
    27
    Views:
    1,990
    Tim Roberts
    May 10, 2008
  5. anne001
    Replies:
    1
    Views:
    439
Loading...

Share This Page