10 июля в 15:53

Как проинвертировать три сигнала двумя инверторами или их роль в истории ЭВМ

Задачу «Можно ли проинвертировать три сигнала, если у вас есть только два инвертора, и неограниченное количество элементов „И“ и „ИЛИ“? мы решали в институте за одну пару. Сейчас ее решение ставит в тупик даже продвинутых специалистов. Давайте посмотрим как с ней справится geektimes-сообщество, а заодно попробую восстановить истории ее возникновения…

Преподаватель в институте рассказывал, что подобного рода задачи возникали в эру ламповых ЭВМ. Но расспросить подробности у нас студентов-бездарей ума не хватило, потому сейчас историю приходится восстанавливать по описанию старых машин и немного додумывать.
Первые электронные вычислительные машины строились на лампах. Так первая в СССР (1950 год) ЭВМ МЭСМ содержала около 6000 ламп, с помощью которых реализовывались логические функции „И“, „ИЛИ“ и „НЕ“ двоичной логики, которые лежат в основе и современных компьютеров. Реализацию классических вентилей на лампах можно посмотреть на картинке.



Логическая функция „И“ строилась на одной лампе, число входов определялось числом сеток в лампе. А для реализации элемента классического вентиля „2ИЛИ“ требовалось две лампы. И хотя в последствии появились так называемые компактроны, что то на подобии сборок из нескольких ламп в одной колбе, инженерами все же приходилось оптимизировать логические выражения для того, что бы в них преобладала функция „И“. Лампы были дорогими, не надежными (наработка на отказ 750 часов), выделяли много тепла, но самое главное они были огромными. В 1952 году появились первые отечественные полупроводниковые диоды для замены маломощных ламп. Их появление ознаменовало появление диодной логики, которая позволила значительно сократить размер логических вентилей. Реализация функции „И“ и „ИЛИ“ на диодной логике представлено на рисунке.



Но для реализации инвертора все еще требовалась лампа. Для построения машины БЭСМ-2 уже применялись полупроводниковые диоды, и она содержала уже 4000 ламп и 5000 полупроводниковых диодов. Сокращение размеров и потребления вентилей „И“ и „ИЛИ“ были значительными, и заставляло оптимизировать логических функций для уменьшении числа инверторов в схеме. Наверное именно тогда инженерам и пришлось впервые решить эту задачу.
Серийное производство транзисторов, позволивших полностью отказаться от ламп, началось в нашей стране в 1955 году. И в 1959 году первой транзисторной безламповой ЭВМ была машина „Сетунь“, хотя в ней все же было 20 ламп.

И все же вернемся к нашей задаче.

Если кто знает решение, давайте не портить удовольствие тем кто хочет решить ее сам. Ответы принимаются в комментариях, просьба оформлять их в виде записи на языке С или Verilog.
Вариант {nA,nB,nC} <= !{A,B,C}; не принимается, это три инвертора.

UPD:

Решение от @eatmore
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
image
Можно ли проинвертировать три сигнала, если у вас есть только два инвертора, и неограниченное количество элементов «И» и «ИЛИ»?
10%
(9)
Нельзя.
44%
(41)
Можно, я нагуглил ответ.
46%
(43)
Можно, я решил сам!

Проголосовало 93 человека. Воздержалось 124 человека.

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

Сергей @Sergei2405
карма
13,0
рейтинг 16,9
Самое читаемое

Комментарии (37)

  • 0
    В замечательной книге «Bebop to the Boolean Boogie, Third Edition: An Unconventional Guide to Electronics» решение приведено и очень хорошо показано его создание — после чтения забыть его невозможно.
  • 0
    Так это же элементарные законы де Моргана
  • +1
    nA = (!(A & B)) | B
    nB = (!(A & B)) | A
    nC = (!C)
    • +2
      nA = (!(A & B)) | B
      nA = !A | !B | B
      !B | B = 1
      nA всегда 1, так что пока мимо.

      Ответ гораздо интересней.
  • –1
    Ну тогда наоборот =)
    nA = (!(A | B)) & B
    nB = (!(A | B)) & A
    nC = (!C)
    • +2
      nA = (!(A | B)) & B
      nA = (!A & !B) & В
      nA = !A&B & !B&В
      !B&B = 0

      nA всегда 0

      Продолжаем поиск

    • +1
      А=1, B=0. nA=(!(1|0))&0=0&0=0 nB=(!(1|0))&1=0&1=0. не работает)
  • 0
    Про задачу не знал. Пришлось: 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 аналогично.
    • 0
      Давайте полный ответ.
      Там где очевидные ошибки, я на них указываю, а там где много букв придется проверять в симуляторе, боюсь ошибусь, если за вас буду додумывать…
  • 0
    Ок. Самому бы не запутаться… :)
    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 входных бит.
    Догадка или верна или нет. Частности — это просто время на проверки.
    — Что любопытно, число входных сигналов неважно. Вот только с практической точки зрения преобразователь может оказаться неадекватно сложным.
    • +1

      Я могу доказать, что в любом верном решении один из инверторов будет использовать выход другого (возможно, опосредовано). В вашем решении это не так, так что дальше можно не смотреть, оно неверное.

      • 0
        (… Заставили задуматься и внимательно пересмотреть нарисованные схемки...) Таки да, нашлись «ложные срабатывания».
        Вспомнил ГПиМРМ и задачки в купе в 8-й главе… Мда. :)
        А можно узнать, где описывается то, что «любом верном решении один из инверторов будет использовать выход другого»? Откуда такой частный вывод? Или для этого обязательно придется читать где-то все готовое решение?
        • 0

          Где описывается, не знаю, я это вывел сам. Идея такая: рассмотрим последовательность переходов 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, то есть хотя бы на одном из этих четырёх наборов входных значений выходные значения будут неправильные.


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

          • 0
            Спасибо за объяснение…
            К сожалению, ваш текст я вроде бы прочитать могу, но для меня это перебор — у меня не хватает базы для составления такой цепочки.
            Так что я пас, пожалуй… Я не могу объяснить для себя «на пальцах» математического смысла ваших выходов инверторов.
            Возможно, придется все же посмотреть готовое решение…
      • 0
        А вот это интересно. Еще и опосредовано. Не поленитесь?
    • +1
      D = !(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, продолжаем поиск.
      • +1
        Спасибо за проверку. Да, при более тщательном просмотре 4 комбинации из 8 обрабатываются «криво». Сам виноват, «положительная предвзятость». :)
  • +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)
    • 0
      Поздравляю!
    • 0
      Дабы чуть объяснить решение, отметим, что
      DE2 = 112 - A - B - C
    • +6
      Шайтан...

      • +2
        А что такую красоту генерирует, если не секрет?..
        • +2
          Это NI LabVIEW. Конкретно эта анимашка из LabVIEW NXG сделана.
      • +2
        Что это за программа для моделирования?
  • +2

    Зато лампу сэкономили.

    • 0

      В данном случае это сильно усложняет работу инженеров, что может привести к ошибкам, особенно при ручном проектировании..

  • 0
    Сейчас вечер и голова варит, но если из 2х инверторов можно «сделать три», то можно ли из тех двух что есть в этих трёх сделать опять три и таким образом получить 4, и так увеличивать до бесконечности? Я конечно в этом сильно сомневаюсь, и почти наверняка укускаю что-то очевидное…
    • +1
      Можно. Но каскадность схемы растет по експоненте. Т.е. схема 2->3 это уже 23 элемента (включая 2 инвертора) в каскаде 8 (т.е. критический путь это 8 каскадов). Если использовать эти инверторы, то каскадность вырастет: 6 + 8 + 8 = 22 (4 инвертора). Далее уже 6+22+8(неспользованный) = 36 (5 инверторов). Т.е. тут уже думать что важнее: скорость, сложность, надежность. Чем сложнее схема, тем больше схема и выше вероятность отказа.
      Да. Забыл еще про усилители сигнала. А это тоже лампы :)
  • –2
    Не до конца понимаю смысл, потом добавлю как надумаю, пока только вот так можно поменять местами значения.
    b:=a-b;
    a:=a-b;(a-a+b=b)
    b:=b+a;(a-b+b=a)
  • 0
    А я подумал что на входе дешифратор, а дальше шифратор.
    Не уверен, нужны ли там инверторы вообще.
  • 0
    Задачка интересная, но заголовок статьи — кликбейт «Это невероятно, даже ведущие специалисты заходят в тупик»
    не заходят, вероятно, если очень нужно будет, то даже посредственный электронщик найдет решение

    «я то в советские времена… !»
  • +2

    Проблема популярна и в англоязычном Интернет. Вот, например, статья на EETimes, описывающая решение :-) — http://www.eetimes.com/document.asp?doc_id=1274508&page_number=2

  • 0
    Существует ли несимметричное решение? Никак не могу придумать
  • 0

    XOR содержит один NOT. XOR = "^"


    D = A ^ B


    !A = D & B
    !B = D & A


    !C = !C

    • +1
      К сожалению не проходит уже при A=0,B=0,C=0;
      D=0;
      nA = 0, nB=0, nC = 1

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