Как построить ворота XOR, используя только 4 шлюза NAND?

17

xorворота, теперь мне нужно построить эти ворота, используя только 4 nandворот

a b out
0 0 0
0 1 1
1 0 1
1 1 0

the xor = (a and not b) or (not a and b), который является

A¯B+AB¯

Я знаю ответ, но как получить диаграмму ворот из формулы?

Xor Gate

РЕДАКТИРОВАТЬ

Я имею в виду интуитивно, для меня, я должен получить это, если я делаю это шаг за шагом, а затем определение xor = (a and not b) or (not a and b).

A¯B¯AB¯¯¯

и xorбудет построен с 5 nandворотами (первое изображение №1 ниже)

xor gate 2

мой вопрос больше похож на: представьте, что первый человек в истории nandвыяснит эту формулу, как он или она (процесс мышления) могут получить 4 решения из этой формулы, шаг за шагом.

A¯B+AB¯
вневременный
источник
Я уверен, что вы знаете, как взять XOR (или любую другую функцию) и преобразовать его в эквивалентную схему, которая использует только NAND (что всегда возможно, так как NAND завершен ). Однако, если вы спросите, как сократить эту формулу до использования только 4 NAND, или вообще меньше NAND, и возможно ли получить эквивалентную схему с k NAND - я не уверен, что ответь за это. kk
Ран Г.
Ниже приведены два ответа на проблему. Мое совершенно откровенно говорит о том, что вы можете разработать (апостериорно) способ найти желаемую конструкцию, заранее зная конечный результат, который был дан в вопросе и доступен в Интернете. Это явно более простой способ сделать что-то, абсурдно, как может показаться, если не дать общей процедуры, на которую нет ответа. Следовательно, мне интересно знать, почему избиратели предпочитают один ответ другому, если они делают ... если вы уделите время для короткого комментария. Заранее спасибо.
Бабу
Этот вопрос закрыт потому, что неясен. Я думаю, что было бы довольно ясно, о чем спрашивает ОП, и еще более интересно, если ОП удосужился реагировать на различных пользователей, которые пытаются на него ответить,
Бабу
electronics.stackexchange.com/questions/84714/… - этот вопрос носит более общий характер, ответы дают больше информации об общем подходе к решению этой проблемы, и этот ответ electronics.stackexchange.com/a/84803 показывает, как получить NAND представление для оператора XOR
Антон Трунов
Я поиграл с некоторыми похожими проблемами и просто написал программу, которая систематически пробовала все ... Хорошо для четырех входов, где есть только 65 536 возможных функций. Для немного более сложных схем это также позволило мне оптимизировать задержки и найти оптимальные схемы, если один или два входа были доступны позже, чем другие. Схемы с 5 входами = 2 ^ 32 возможных функций, вероятно, были бы выполнимы с использованием грубой силы.
gnasher729

Ответы:

13

Из этой формулы? Это может быть сделано. Но проще начать с этого: (здесь используется другая запись)

a ^ b = ~(a & b) & (a | b)

Хорошо, что теперь? В конце концов мы должны получить ~(~(~(a & b) & a) & ~(~(a & b) & b))(что выглядит так, как будто у него 5 NAND, но так же, как у принципиальной схемы, есть подвыражение, которое используется дважды)

Так что сделайте что-то похожее ~(a & b) & a(и то же самое, но с символом « bв конце») и надейтесь, что оно останется: ( andраздаёт or)

(~(a & b) & a) | (~(a & b) & b)

Довольно близко, просто примените DeMorgan, чтобы превратить эту середину orв and:

~(~(~(a & b) & a) & ~(~(a & b) & b))

Вот и все.

Гарольд
источник
9

Я думаю, что вы просите это доказательство:

A^B = (!A)B + A(!B)
    = !!((!A)B) + !!(A(!B))
    = !(!!A + !B) + !(!A + !!B)
    = !(A + !B) + !(!A + B)
    = !((A + !B)(!A + B))
    = !(A(!A) + AB + (!A)(!B) + B(!B))
    = !(AB + (!A)(!B))
    = !(AB)(!(!A)(!B))
    = !(AB)(!!A + !!B)
    = !(AB)(A+B)
    = !(AB)A + !(AB)B
    = !!(!(AB)A + !(AB)B)
    = !((!(!(AB)A))(!(!(AB)B)))

Хотя, очевидно, NANDв полученном уравнении используются 5 с, но дубликат !(AB)будет использоваться только один раз, когда вы проектируете его схему.

Мунтасир
источник
Извините, но разве А ^ Б не означает А И Б? Кажется, вы намеревались доказать XOR, какой символ должен быть ⊕ или ⊻. Однако это доказательство было то, что я действительно искал, спасибо!
osiixy
5

Поскольку у вас уже есть ответ на диаграмме, который можно легко получить из википедии , введя название вопроса в Google в виде диаграммы .png, идентичной вашей, вам будет легко найти формулу, извлекая ее из этой диаграммы. Учитывая NAND определения , как NAND(A,B)=AB¯:

  • Крайний левый затвор дает ;C=AB¯

  • Верхние ворота дают ;D1=AC¯

  • Верхний вентиль дает , поскольку NAND коммутативен, как AND;D2=BC¯

  • Крайний правый затвор дает .E=D1D2¯

Собирая все это вместе, мы сначала отметим, что

C=AB¯=A¯+B¯

D1¯=AC=A(A¯+B¯)=AA¯+AB¯=0+AB¯=AB¯

Аналогично: D2¯=BA¯

Таким образом,
E=D1D2¯=D1¯+D2¯=AB¯+BA¯

Какое именно определение XOR. Вы можете просто отменить все это, если хотите начать с исходных данных, а не просто проверить ответ.

Поиск ответа без предварительного знания

Это предназначено, чтобы ответить на явный запрос, добавленный как изменение к вопросу, для способа найти решение с нуля. Учитывая, что речь идет о мыслительном процессе, я даю все детали.

AB

XOR(A,B)=AB¯+BA¯,

Таким образом, мы можем попытаться угадать, какой тип ввода для этих элементов даст желаемый результат.

NAND(X,Y)=XY¯=X¯+Y¯

Объединяя эту последнюю формулу с результатом, который мы должны получить, мы получаем:

  • X¯=AB¯X=AB¯¯=A¯+B,

  • Y=A¯B¯=A+B¯,

Обратите внимание, что это только самая простая возможность. Существуют и другие пары входных данных, которые дают желаемый результат, потому что мы не объединяемся в свободной алгебре, поскольку NAND обладает эквациональными свойствами. Но мы попробуем это для начала.

XYAB

Мы могли бы попытаться повторить процедуру объединения (я это сделал), но это, естественно, приведет нас к использованию еще четырех ворот, а значит, к решению с 5 воротами.

XYZAB

XYZABAB

AB

Z=NAND(A,B)=AB¯=A¯+B¯

ZABXY

AB

Это легко проверить

NAND(Z,A)=ZA¯=AB¯A¯=(A¯+B¯)A¯=A¯A+B¯A¯=0+B¯A¯=B¯A¯=AB¯¯=X

Similarly NAND(Z,B)=Y

Hence we can compose these four gates to get the desired result, i.e., the XOR function.

babou
источник
Not in a reverse way to prove that they are equal. But image that you don't know the diagram but to construct the gate using minimum nand gate.
Timeless
1
What do you expect as an answer? A systematic technique for doing that. I do not know that there is any that is tractable enough to be worth using in complex cases. Given that I know the answer I can just lie to you and pretend to have found by reasonning what I discovered by checking the answer. This said, looking at what I get with NAND(A,B) is all that seems useful for a start. Then NANDing the result with one argument A or B, is also one thing to look at, to get a view of where I am. From there, one is pretty close to the final answer.
babou
1
@Timeless Another way to go about it is backward from the answer, knowing that the answer is fron a NAND gate. If you assume that the solution is symmetrical in A and B, it gives you a likely form of the inputs to the last NAND gate. There are many way to go about it, either to find the answer, or to justify finding it a posteriory. But a proof is a proof, whether found by your ingenuity, or given by some oracle or a good friend. And at some point no one can tell the difference. Actually, the backward proof I give could be the best proof, even if the solution was found some other way.
babou
Actually, it is quite common in math to have an analysis part to find a solution, then a synthesis part where you prove it is the solution. One usually gives both, but only the second part is really necessary.
babou
@Timeless Both answers were based on the knowledge of a formula to obtain, deduced from the diagram to be obtained. Your edit asked for a plausible intuitive scenario to find the answer without any prior knowledge of the result. I did add that to my answer, but it would be nice to know whether it fits what you expected.
babou
0

I take the input (0,0) as an example.

For XOR, the desired output is 0. However, NAND(0,0)=1.

  • Because the only way to get a 0 using NAND is (at the last layer) NAND(1,1)=0, you should first produce two 1's.

    • According to NAND(0,1)=1 or NAND(1,0)=1, you produce a 1 using one NAND(0,0) at the first layer and feed it, along with one input 0, into a second layer NAND.

Only four NANDs are involved. But it is only correct for the input (0,0) so far. So you need to check other inputs (0,1),(1,0), and (1,1) against the solution and find that it just works. Lucky.

hengxin
источник
0

I tried my best to give the answer using formula as asked.Hope you appreciate it.
Z=AB'+A'B
Z=AA'+AB'+BB'+A'B --->BB'=AA'=0
Z=A(A'+B')+B(B'+A')
Z=A(AB)'+B(AB)' --> Hint
so now (AB)' can get through 1st NAND gate,then in 2nd and third NAND gate the output of 1st NAND gate pass through with one of the input as A and B.After this we need one more complement so use fourth NAND gate.
NAND(1st)=(AB)'=A'+B'
NAND(2nd)=(A(AB)')'=(A(A'+B'))'=(AB')'=A'+B
NAND(3rd)=(B(AB)')'=(B(A'+B'))'=(A'B)'=A+B'
NAND(4th)=[(A'+B)(A+B')]' =[A'B'+AB]'=(A+B)(A'+B')=AB'+A'B

Happy!

MANVENDRA SINGH MANOHAR
источник
0

The formula: XOR = (a and not b) or (not a and b).

Thats' not what you want, you want a formula that is a NAND. Remember that not (a or b) = not a and not b, and therefore (a or b) = not (not a and not b). Therefore

(a and not b) or (not a and b) =

not (not (a and not b) and not (not a and b)) =

not ((not a or b) and (a or not b)) =

NAND (not a or b, a or not b).

So we used one NAND gate, and have to calculate (not a or b) and (a or not b) using three NANDs. We turn each expression into a NAND:

not a or b = not (a and not b) = NAND (a, not b)

a or not b = not (not a and b) = NAND (not a, b)

Now we observe that (x and y) = x and (not x or y): If x is false then both sides are false. If x is true then (not x or y) = (false or y) = y. This is true for NAND just as it's true for AND. Therefore

NAND (a, not b) = NAND (a, not a or not b) = NAND (a, NAND (a, b))

NAND (b, not a) = NAND (b, not b or not a) = NAND (b, NAND (a, b)).

So we first find mid = NAND (a, b), left = NAND (a, mid) and right = NAND (b, mid), finally XOR = NAND (left, right).

gnasher729
источник
-2

*From left to right--D1,D2,D3,D4 ** D1=(A.B)' OR(A'+B')

suppose

(A.B)'=C

D2=(A.C)'=A'+C'

D3=(B.C)'=B'+C' then

D4=(D2.D3)'

D4=((A.C)'.(B.C)')'

D4=(A.C)''+(B.C)''

D4=(A.C)+(B.C)

D4=A.(A'+B')+B.(A'+B')

D4=AB'+BA' {A.A'=B.B'=0}**

Bivash
источник
2
I find it hard to follow this answer or understand what process you are using. Can you add some text sentences to explain the approach, so this isn't just a sequence of equations?
D.W.