Задачу «Можно ли проинвертировать три сигнала, если у вас есть только два инвертора, и неограниченное количество элементов „И“ и „ИЛИ“? мы решали в институте за одну пару. Сейчас ее решение ставит в тупик даже продвинутых специалистов. Давайте посмотрим как с ней справится geektimes-сообщество, а заодно попробую восстановить истории ее возникновения…Преподаватель в институте рассказывал, что подобного рода задачи возникали в эру ламповых ЭВМ. Но расспросить подробности у нас студентов-бездарей ума не хватило, потому сейчас историю приходится восстанавливать по описанию старых машин и немного додумывать.
Первые электронные вычислительные машины строились на лампах. Так первая в СССР (1950 год) ЭВМ МЭСМ содержала около 6000 ламп, с помощью которых реализовывались логические функции „И“, „ИЛИ“ и „НЕ“ двоичной логики, которые лежат в основе и современных компьютеров. Реализацию классических вентилей на лампах можно посмотреть на картинке.
Логическая функция „И“ строилась на одной лампе, число входов определялось числом сеток в лампе. А для реализации элемента классического вентиля „2ИЛИ“ требовалось две лампы. И хотя в последствии появились так называемые компактроны, что то на подобии сборок из нескольких ламп в одной колбе, инженерами все же приходилось оптимизировать логические выражения для того, что бы в них преобладала функция „И“. Лампы были дорогими, не надежными (наработка на отказ 750 часов), выделяли много тепла, но самое главное они были огромными. В 1952 году появились первые отечественные полупроводниковые диоды для замены маломощных ламп. Их появление ознаменовало появление диодной логики, которая позволила значительно сократить размер логических вентилей. Реализация функции „И“ и „ИЛИ“ на диодной логике представлено на рисунке.
Но для реализации инвертора все еще требовалась лампа. Для построения машины БЭСМ-2 уже применялись полупроводниковые диоды, и она содержала уже 4000 ламп и 5000 полупроводниковых диодов. Сокращение размеров и потребления вентилей „И“ и „ИЛИ“ были значительными, и заставляло оптимизировать логических функций для уменьшении числа инверторов в схеме. Наверное именно тогда инженерам и пришлось впервые решить эту задачу.
Серийное производство транзисторов, позволивших полностью отказаться от ламп, началось в нашей стране в 1955 году. И в 1959 году первой
И все же вернемся к нашей задаче.
Если кто знает решение, давайте не портить удовольствие тем кто хочет решить ее сам. Ответы принимаются в комментариях, просьба оформлять их в виде записи на языке С или Verilog.
Вариант {nA,nB,nC} <= !{A,B,C}; не принимается, это три инвертора.
UPD:
E = !((D&(A|B|C))|(A&B&C))
nA = (D&E)|(D&(B|C))|(E&B&C)
nB = (D&E)|(D&(A|C))|(E&A&C)
nC = (D&E)|(D&(A|B))|(E&A&B)
| 10% (9) |
Нельзя. |
| 44% (41) |
Можно, я нагуглил ответ. |
| 46% (43) |
Можно, я решил сам! |
Проголосовало 93 человека. Воздержалось 124 человека.
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
Комментарии (37)
AKudinov
10.07.2017 16:31+1nA = (!(A & B)) | B
nB = (!(A & B)) | A
nC = (!C)Sergei2405
10.07.2017 16:34+2nA = (!(A & B)) | B
nA = !A | !B | B
!B | B = 1
nA всегда 1, так что пока мимо.
Ответ гораздо интересней.
Scalar
10.07.2017 17:06-1Ну тогда наоборот =)
nA = (!(A | B)) & B
nB = (!(A | B)) & A
nC = (!C)Sergei2405
10.07.2017 17:09+2nA = (!(A | B)) & B
nA = (!A & !B) & В
nA = !A&B & !B&В
!B&B = 0
nA всегда 0
Продолжаем поиск
AndrewCh
10.07.2017 18:03Про задачу не знал. Пришлось: 1. Порисовать. 2. Зарегистрироваться на GT. :)
Итак, предположительно что-то вроде:
D = !(A|B|C)
E = !(A&B&C)
Тогда:
nA = (B|C|D)&(B|D)&(C|D)&(D|E)
или
nA = (B&C&E)|(B&E)|(C&E)|(D&E)
Ну и для nB, nC аналогично.Sergei2405
10.07.2017 18:04Давайте полный ответ.
Там где очевидные ошибки, я на них указываю, а там где много букв придется проверять в симуляторе, боюсь ошибусь, если за вас буду додумывать…
AndrewCh
10.07.2017 18:17Ок. Самому бы не запутаться… :)
nB = (A|C|D)&(A|D)&(C|D)&(D|E)
или
nB = (A&C&E)|(A&E)|(C&E)|(D&E)
и для C:
nC = (A|B|D)&(A|D)&(B|D)&(D|E)
или
nC = (A&B&E)|(A&E)|(B&E)|(D&E)
Проверяйте.
— Но тут, по-моему — главное догадка, что два инвертора нужно использовать для инверсии («всего по и») и («всего по или»). А потом уже плясать от комбинаций из 5 входных бит.
Догадка или верна или нет. Частности — это просто время на проверки.
— Что любопытно, число входных сигналов неважно. Вот только с практической точки зрения преобразователь может оказаться неадекватно сложным.
eatmore
10.07.2017 18:31+1Я могу доказать, что в любом верном решении один из инверторов будет использовать выход другого (возможно, опосредовано). В вашем решении это не так, так что дальше можно не смотреть, оно неверное.
AndrewCh
10.07.2017 19:06(… Заставили задуматься и внимательно пересмотреть нарисованные схемки...) Таки да, нашлись «ложные срабатывания».
Вспомнил ГПиМРМ и задачки в купе в 8-й главе… Мда. :)
А можно узнать, где описывается то, что «любом верном решении один из инверторов будет использовать выход другого»? Откуда такой частный вывод? Или для этого обязательно придется читать где-то все готовое решение?eatmore
10.07.2017 19:43Где описывается, не знаю, я это вывел сам. Идея такая: рассмотрим последовательность переходов 000 > 100 > 110 > 111 (три цифры — значения A, B и C). Эта последовательность монотонная (это значит, что в ней 1 никогда не заменяется на 0). Последовательность значений любой функции, использующая только операции И и ИЛИ, также будет монотонной. Если ни один из инверторов не использует значение другого, то последовательность входных значений будет монотонной — или константой, или сколько-то нулей, затем сколько-то единиц. То есть, будет максимум один переход, где 0 заменяется на 1. На выходе, соответственно, максимум 1 переход, где 1 заменяется на 0.
Итоговые значения (nA, nB и nC) являются монотонными функциями от A, B, C и выходов инверторов. Чтобы монотонная функция изменила значение с 1 на 0, нужно, чтобы один из параметров изменил значение с 1 на 0. В данной последовательности на каждом из трёх переходов одно из значений nA, nB и nC меняется с 1 на 0, при этом A, B и C не меняют значение с 1 на 0. Значит, это должны делать выходы инверторов, но их всего 2, и каждый меняет значение выхода с 1 на 0 максимум на одном из переходов. То есть, на одном из трёх переходов ни один из двух инверторов не меняет значение выхода с 1 на 0, и на этом переходе значение результата не может измениться с 1 на 0, то есть хотя бы на одном из этих четырёх наборов входных значений выходные значения будут неправильные.
Если один из инверторов использует значение другого, то это доказательство не работает (вход инвертора уже не является монотонной функцией), и задачу можно решить.
AndrewCh
10.07.2017 20:14Спасибо за объяснение…
К сожалению, ваш текст я вроде бы прочитать могу, но для меня это перебор — у меня не хватает базы для составления такой цепочки.
Так что я пас, пожалуй… Я не могу объяснить для себя «на пальцах» математического смысла ваших выходов инверторов.
Возможно, придется все же посмотреть готовое решение…
Sergei2405
10.07.2017 18:52+1D = !(A|B|C);
E = !(A&B&C);
nA = (B|C|D)&(B|D)&(C|D)&(D|E);
nB = (A|C|D)&(A|D)&(C|D)&(D|E);
nC = (A|B|D)&(A|D)&(B|D)&(D|E);
При A=0,B=0,C=1 получается nA=0,nB=0,nC=0, продолжаем поиск.AndrewCh
10.07.2017 19:55+1Спасибо за проверку. Да, при более тщательном просмотре 4 комбинации из 8 обрабатываются «криво». Сам виноват, «положительная предвзятость». :)
eatmore
10.07.2017 18:22+7Решил сам.
РешениеD = !((A&B)|(B&C)|(A&C)) E = !((D&(A|B|C))|(A&B&C)) nA = (D&E)|(D&(B|C))|(E&B&C) nB = (D&E)|(D&(A|C))|(E&A&C) nC = (D&E)|(D&(A|B))|(E&A&B)
AndreyDmitriev
10.07.2017 20:43+6
Imposeren
10.07.2017 21:50Сейчас вечер и голова варит, но если из 2х инверторов можно «сделать три», то можно ли из тех двух что есть в этих трёх сделать опять три и таким образом получить 4, и так увеличивать до бесконечности? Я конечно в этом сильно сомневаюсь, и почти наверняка укускаю что-то очевидное…
QuaziKing
10.07.2017 22:35+1Можно. Но каскадность схемы растет по експоненте. Т.е. схема 2->3 это уже 23 элемента (включая 2 инвертора) в каскаде 8 (т.е. критический путь это 8 каскадов). Если использовать эти инверторы, то каскадность вырастет: 6 + 8 + 8 = 22 (4 инвертора). Далее уже 6+22+8(неспользованный) = 36 (5 инверторов). Т.е. тут уже думать что важнее: скорость, сложность, надежность. Чем сложнее схема, тем больше схема и выше вероятность отказа.
Да. Забыл еще про усилители сигнала. А это тоже лампы :)
ivanius
11.07.2017 07:45-2Не до конца понимаю смысл, потом добавлю как надумаю, пока только вот так можно поменять местами значения.
b:=a-b;
a:=a-b;(a-a+b=b)
b:=b+a;(a-b+b=a)
pulsatrix
11.07.2017 08:37А я подумал что на входе дешифратор, а дальше шифратор.
Не уверен, нужны ли там инверторы вообще.
uterr
11.07.2017 09:57Задачка интересная, но заголовок статьи — кликбейт «Это невероятно, даже ведущие специалисты заходят в тупик»
не заходят, вероятно, если очень нужно будет, то даже посредственный электронщик найдет решение
«я то в советские времена… !»
Alyoshka1976
11.07.2017 21:07+2Проблема популярна и в англоязычном Интернет. Вот, например, статья на EETimes, описывающая решение :-) — http://www.eetimes.com/document.asp?doc_id=1274508&page_number=2
GarryC
В замечательной книге «Bebop to the Boolean Boogie, Third Edition: An Unconventional Guide to Electronics» решение приведено и очень хорошо показано его создание — после чтения забыть его невозможно.