Special AND-gate

Hi,

I am looking for a way to design a boolean AND-gate (with possibly many
inputs) that consists of several standard AND, XOR, NOT, randomness gates
and has the following properties:
1. On input a,b it output a AND b
2. The encoding to present a AND b has the same probability as NOT(a AND b)

Note that the second property is for instance not satisfied for the
standard binary encodiding because the output 1 has only probability 1/4
where 0 has 3/4. What I would like to have is that both outputs have the
same probability.

The only way I can think of to solve this problem is to use some kind of
dynamic encoding, i.e. sometimes the 1 is used to represent a 0 and
sometimes a 0 is used to represent the 1.

Regards,
Bernd

 

I'm not quite certain that randomness gates qualify as standard parts.

Absent any other constraints, just alternate between presenting a and
!a at the output, since !(a && b) is equivalent to (!a || !b) and
that's satisfied by !a.

 

FPGA
PIC
AVR
PLC
PGA
Did I miss something?


http://webpages.charter.net/jamie_5"

 

The "maybe gate", the digital kin of the "inoperational amplifier".

 

The function of an AND-gate is fully specified. Its output depends only on
the inputs. So the probability of its output depends on the probability of
its inputs. In other words, you do not want an AND-gate but something else.
As you reasoning is unclear to me, I can only guess you to want an
XNOR-gate. Out of four possible input combinations it makes two times true
and two times false. See truth table below.

a b aXNORb
0 0 1
0 1 0
1 0 0
1 1 1

This function is also determined. The probability of the output still
depends on the inputs.

petrus bitbyter

 

Yep, MSP430 for example. Or if Bernd wants the leather-seat deluxe
edition maybe an ARM core.

 

Are you sure this is what your homework assignment said? Maybe it
said "same probability of 1's and 0's" in which case you can use
multiple outputs for the encoding.

As for the big list, add CPLD

 

The George W. Bush flip-flop by Mark Zenier
http://groups.google.com/group/sci.electronics.design/msg/02894d934dc75be0?dmode=source

I kept thinking *fuzzy logic*.
http://www.google.com/images?q=tribble

 

What is a combinatorial circuit? And what is with the XOR function? for two
random bit inputs it outputs 1 with probability 1/2

What I acutually try to achieve is an AND gate that flips its output with
probability 1/2 for random input. So assume in the first clock cylce you
input two random bits to the AND gate. The output will be 1 with
probability 1/4 and 0 with probability 3/4. Now, for the next clock cycle,
again for random input we have with probability 1/4 an output of 1 and with
probability 3/4 an output of 0. The probability that at the output wire we
have a flip is 6/16, but what I acutally want to achieve is that the output
wire flips with probability 1/2.
If I consider for instance an XOR gate than the probability that the output
flips is always 1/2. Can I achieve the same probability also for an AND-
gate without losing the functionality of the AND-gate?

Cheers,
Bernd

 

Yes, multiple outputs are definitly allowed to solve this problem... but I
am not so sure how it can help.

 

The "maybe gate", the digital kin of the "inoperational amplifier".
Probably the secification of my problem was not very well stated.

I hope my second post makes things a bit more clear, although I am still
not sure if it is possible at all to achieve something as I mentioned in my
post from below.

Cheers,
Bernd

 

So, there is no way of designing an AND gate such that the probability of a
flip at the output is 1/2?

 

No, because then it wouldn't be an "AND" gate...

Drop the "AND" from your specification and tell us the truth table, or
output as a probability FUNCTION OF THE INPUTS and maybe we can help
you design this bernd-gate.

 

So there is no possibility by applying some special encoding such as
presenting every bit by two bits etc.? Note that the functionality of the
AND has still to be kept.

Cheers,
Bernd

 

It is. Odd parity.

petrus bitbyter

 

It can't. An AND-gate behaves according to its function s=a*b. If not, it is
not an AND-gate anymore. The probabilty of its output depends on the
probabilty of its inputs. If the inputs are unrelated and have a probality
of 50% true (and so 50% false) THEN the probability of the output is 25%
true (and 75% false). You cannot change this by changing the AND-gate as - I
repeat - if you do so it is not an AND-gate anymore. So if you want both an
AND-gate AND a probability of 50/50 on the output the only thing you can do
is changing the probability of the inputs. If you have no information of the
inputs other then that they are random AND you want an AND-gate AND a 50/50
output THEN you're lost. I'm sorry to say but if you don't understand it by
now, you better can go and do anything but electronics design.

petrus bitbyter

 

In this case, the solution is obvious, but I won't give it away. You
need to show your own work on this one.

 

Late at night, by candle light, Bernd Schneider

Noise generator, zero crossing detector, buffer as fit.

- YD.

 

Oh, I like it. Took me a while, but I like it. And it's even a
common technique...

But I don't think the problem is very well stated.
Why is it desired that the probability of the outputs be 50/50?
The real reason may be the clue to the "solution"