Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.misc > #17801

Re: Thoughts in combinatorial logic

Show all headers | View raw

On 5/04/2019 8:48 pm, Bruce Horrocks wrote:
> On 01/04/2019 06:11, Sylvia Else wrote:
>> As part of a personal project I'm working on, I needed a combinatorial 
>> logic way of obtaining the lowest set bit from a collection of bits. 
>> That is, taking n inputs in some order, and by using only and/or/not 
>> gates, produce n outputs of which only one is set, being that which 
>> corresponds to the lowest order set input bit
>>
>> It's not especially difficult.
>>
>> But suppose the requirement is not the lowest set bit, just any of the 
>> set bits.
>>
>> Clearly, the solution to the first requirement is also a solution to 
>> the second requirement, but is the second requirement amenable to a 
>> simpler (as in, using fewer gates) solution.
>>
>> My intuition is that it's not, but I haven't been able to prove it.
>>
>> Sylvia.
> 
> I passed this message on to some friends and received the following 
> replies.
> 
> 
> Dan:
>> My first thought is that there probably isn’t any saving in gates
>> for the “don’t care which” version. But that it can be subdivided
>> and paralleled so that its worst-case propagation delay will be
>> better.
> 
> 
> Hugh:
>> First test for zero, otherwise least bit is;
>>
>> (v & (v-1)) ^ v Implement the decrement using a per-bit borrow network.
>>
>> same answer for any bit.
> 
> 
> Tony:
>> Off the top of my head : Let I(0)..I(n-1) be the n inputs and 
>> O(0)..O(n-1) be the n outputs.
>>
>> O(0)=I(0) ; pass input 0 anyway, if it happens to be 1 then it is the
>> lowest set bit. O(k) = I(k) AND NOT (OR(I(k-1)...I(0))) ; Pass bit k
>> iff all lower bits are 0's
>>
>> If propagation delays don't matter you can implement the OR as a chain 
>> of 2 input gates :
>>
>> Thus O(1) = I(1) AND NOT I(0) INH(1) = I(1) OR I(0) O(2) = I(2) AND 
>> NOT (INH(1)) INH(2) = I(2) OR INH(1) O(3) = I(3) AND NOT (INH(2))
>> and so on
>>
>> I saw Hugh's solution, and have come across it before. It's neat in 
>> programming languages with bitwise operations on n-bit variables,
>> but IMHO less good in hardware where increment and decrement use a
>> lot of gates.
> 
> and re your intuition...
> 
>> My intuition is the same. Whatever bit you pass on you still have to
>> mask out all the others.
> 
> 
> Frank:
>  > I have this bit of code in production silicon (with these actual
>  > comments) where I needed the lowest bit. In Verilog we can obviously
>  > write the expression or a for loop and synthesis works out how to
>  > optimize it, but sometimes it's just safer to write it in a simple
>  > way. In this example the x-1 in the comment may end up being
>  > expensive when x is very wide but would optimize to exactly the same
>  > 4-input logic tree.
> 
>> // returns lowest non-zero bit in input
>> function automatic [3:0] LowestBit(input [3:0] x);
>>    return x[0] ? 1 : x[1] ? 2 : x[2] ? 4 : x[3] ? 8 : 0;    // return 
>> (x & ~(x&(x-1))) if we were showing off
>> endfunction
>>
>> // returns highest non-zero bit in input
>> function automatic [3:0] HighestBit(input [3:0] x);
>>    return x[3] ? 8 : x[2] ? 4 : x[1] ? 2 : x[0] ? 1 : 0;    // again 
>> not showing off our 1337 SKILLZ
>> endfunction
>>
> 
> But suppose the requirement is not the lowest set bit, just any of the 
> set bits.
> 
>> Hmm,     output = input gives any (and all) of the set bits.
>>
> 
>> Or what's the real requirement? Any single one? In that case it would
>> be possible to bisect halves, which may end up faster in terms of
>> gate delays when there are a lot of inputs. I'd probably use that
>> method if I was looking at 64 or more inputs. But then I'm used to
>> nanometer scale silicon gates which run at tens of ps gate delays,
>> and I can still have 50 or 100 gates between clock cycles even at GHz
>> rates.
> 
> 
> HTH

Thanks for that.

Sylvia.

Back to comp.misc | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Thoughts in combinatorial logic Sylvia Else <sylvia@email.invalid> - 2019-04-01 16:11 +1100
  Re: Thoughts in combinatorial logic Marko Rauhamaa <marko@pacujo.net> - 2019-04-01 16:28 +0300
  Re: Thoughts in combinatorial logic not@telling.you.invalid (Computer Nerd Kev) - 2019-04-02 22:08 +0000
    Re: Thoughts in combinatorial logic not@telling.you.invalid (Computer Nerd Kev) - 2019-04-03 07:47 +0000
  Re: Thoughts in combinatorial logic Bruce Horrocks <07.013@scorecrow.com> - 2019-04-02 23:11 +0100
    Re: Thoughts in combinatorial logic Sylvia Else <sylvia@email.invalid> - 2019-04-03 09:34 +1100
  Re: Thoughts in combinatorial logic Bruce Horrocks <07.013@scorecrow.com> - 2019-04-05 10:48 +0100
    Re: Thoughts in combinatorial logic Sylvia Else <sylvia@email.invalid> - 2019-04-11 20:33 +1000

csiph-web