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

Groups > comp.misc > #17715 > unrolled thread

Thoughts in combinatorial logic

Back to article view | Back to comp.misc

Contents

  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

#17715 — Thoughts in combinatorial logic

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.

[toc] | [next] | [standalone]

#17716

Sylvia Else <sylvia@email.invalid>:

> 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.

Are we talking about SKI, JK or iota calculus?


Marko

[toc] | [prev] | [next] | [standalone]

#17726

Sylvia Else <sylvia@email.invalid> 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.

A mathematical proof is beyond me, but after mulling over it for a
while I can't think of a way in which the latter problem would have
a simpler solution to the former.

For the lowest set bit, you need for the set bits following the
first one to be cleared. For "any set bit", you need all the set bits
but one to be cleared. Clearing the bits in both "directions" is
harder than only in one direction, as far as I can see.

Another approach would be something like an address decoder
arrangement, and that would be more complicated than clearing the
following bits. In fact I think the second problem may be directly
implying something that would equate to an address decoder.

-- 
__          __
#_ < |\| |< _#

[toc] | [prev] | [next] | [standalone]

#17732

Computer Nerd Kev <not@telling.you.invalid> wrote:
> 
> Another approach would be something like an address decoder
> arrangement, and that would be more complicated than clearing the
> following bits. In fact I think the second problem may be directly
> implying something that would equate to an address decoder.

Of course both problems equate to an address decoder. But having
established that one bit is set, it seems to me that comparisons
between other bits in order to provide a different output state
than would be given if that were the only bit set, could only add
complexity.

-- 
__          __
#_ < |\| |< _#

[toc] | [prev] | [next] | [standalone]

#17727

Can you explain a bit more, please?


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

So a filter that allows the lowest set bit through and clears any higher 
set bits?

> 
> It's not especially difficult.
> 
> But suppose the requirement is not the lowest set bit, just any of the 
> set bits.

What do you mean by 'any'? A filter that randomly selects one of the set 
bits to be allowed through?

> 
> 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.


-- 
Bruce Horrocks
Surrey
England
(bruce at scorecrow dot com)

[toc] | [prev] | [next] | [standalone]

#17728

On 3/04/2019 9:11 am, Bruce Horrocks wrote:
> Can you explain a bit more, please?
> 
> 
> 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
> 
> So a filter that allows the lowest set bit through and clears any higher 
> set bits?

Yes.

> 
>>
>> It's not especially difficult.
>>
>> But suppose the requirement is not the lowest set bit, just any of the 
>> set bits.
> 
> What do you mean by 'any'? A filter that randomly selects one of the set 
> bits to be allowed through?

It could be random, in principle, though combinatorial logic is unlike 
to have that outcome.

Rather stating the obvious, if one assumes that a simpler solution 
exists to the second requirement, then there must be situations where 
changes to the inputs produces changes to the outputs that differ for 
the solution to the first require and the second requirement. I've put 
some thought into a reductio-ad-absurdum proof based on that, but made 
little progress.

Of course, a proof is not going to be forthcoming if my intuition is 
just wrong.

Sylvia.

[toc] | [prev] | [next] | [standalone]

#17761

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
-- 
Bruce Horrocks
Surrey
England
(bruce at scorecrow dot com)

[toc] | [prev] | [next] | [standalone]

#17801

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.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.misc

csiph-web