Connect with us

Special AND-gate

Discussion in 'Electronic Design' started by Bernd Schneider, Apr 6, 2008.

Scroll to continue with content
  1. 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.

  2. Rich Webb

    Rich Webb Guest

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

    Jamie Guest

    Did I miss something?"
  4. krw

    krw Guest

    The "maybe gate", the digital kin of the "inoperational amplifier".
  5. 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
  6. Joerg

    Joerg Guest

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

    DJ Delorie Guest

    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 :)
  8. JeffM

    JeffM Guest

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

  10. Yes, multiple outputs are definitly allowed to solve this problem... but I
    am not so sure how it can help.
  11. 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.

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

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

  15. It is. Odd parity.

    petrus bitbyter
  16. 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
  17. DJ Delorie

    DJ Delorie Guest

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

    YD Guest

    Late at night, by candle light, Bernd Schneider
    Noise generator, zero crossing detector, buffer as fit.

    - YD.
  19. Guest

    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"
Ask a Question
Want to reply to this thread or ask your own question?
You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.
Electronics Point Logo
Continue to site
Quote of the day