задачка, компьютерное

[avva]

Убил на нее немало времени сегодня, но очень понравилась:

Придумайте схему, у которой есть три входа A, B, C и три выхода not-A, not-B, not-C. Можно пользоваться элементами AND, OR и NOT, но AND и OR сколько угодно, а NOT не более двух штук.

Я на время постараюсь скрывать правильные ответы. Но у меня есть предложение: если вы уже знаете решение, или нашли его компьютерным перебором, не пишите его в комментах - напишите просто, что нашли, например. Нет ничего плохого в компьютерном переборе, но не всем интересно. Мне хотелось именно найти решение самому аналитическим путем.

Comments

[(Anonymous)]

Любую логическую схему можно реализовать на двух NOT.

[(Anonymous)]

Ну то есть да, конечно. Если три инвертора можно построить из двух, то и больше тоже можно. Duh.

[adp.myopenid.com (from livejournal.com)]

Нет, не любую. Например, чтобы реализовать 4 функции NOT нужно уже минимум 3 инвертора (докажите).

[(Anonymous)]

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

[adp.myopenid.com (from livejournal.com)]

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

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

[(Anonymous)]

Ну как. Есть схема, состоящая из четырех инверторов. Заменяем три инвертора на два инвертора плюс много элементов И и ИЛИ. Потом опять заменяем три инвертора на два инвертора плюс много элементов И и ИЛИ. Вторая замена в теории незаконна, потому что в общей схеме выход элемента после нескольких преобразований попадает на его же вход.

[adp.myopenid.com (from livejournal.com)]

Она и в практике незаконна :-) Никаких обратных связей суперпозиция схем не даёт ни в теории, ни в практике.

Теперь почему нельзя 4 заменить на 2. Допустим, у вас есть схема, вычисляющая NOT x, NOT y, NOT z с двумя инверторами. Внутри этой схемы инверторы стоят на выходах подсхем, вычисляющих какие-то функции от x, y, z: f(x, y, z) и g(x, y, z). Теперь вы хотите объединить эту схему со схемой, вычисляющей NOT u, где u - четвёртая переменная. То, что вы можете получить с двумя инверторами, будет схемой, вычисляющей NOT f(x, y, z), NOT g(x, y, z) и NOT u. Но никак не схему, вычисляющую четыре отрицания входных переменных :-)

[adp.myopenid.com (from livejournal.com)]

Она и в практике незаконна :-) Никаких обратных связей суперпозиция схем не даёт ни в теории, ни в практике.

Теперь почему нельзя 4 заменить на 2. Допустим, у вас есть схема, вычисляющая NOT x, NOT y, NOT z с двумя инверторами. Внутри этой схемы инверторы стоят на выходах подсхем, вычисляющих какие-то функции от x, y, z: f(x, y, z) и g(x, y, z). Теперь вы хотите объединить эту схему со схемой, вычисляющей NOT u, где u - четвёртая переменная. То, что вы можете получить с двумя инверторами, будет схемой, вычисляющей NOT f(x, y, z), NOT g(x, y, z) и NOT u. Но никак не схему, вычисляющую четыре отрицания входных переменных :-)

[adp.myopenid.com (from livejournal.com)]

Понял, кажется, что вы имели в виду. Получится некорректная суперпозиция, да. То, что сигналы физической схемы стабилизируются, не факт. Есть много примеров, когда схема начинает реализовывать клок или постоянный низкий потенциал.

[alexeybobkov]

Неправильно (или я не понял, о чём вы пишете).
Есть два инвертора.
Строим из них три.
Потом выбираем из получившихся трёх любые два и опять строим из них три.
Итого становится четыре :)
Процесс продолжаем до бесконечности.

[adp.myopenid.com (from livejournal.com)]

Попробуйте нарисовать схему для 4 отрицаний с двумя инверторами, и вы обнаружите в ней комбинационный цикл, недопустимый в схеме функциональных элементов. В теории они просто запрещены, а на практике могут привести к незатухающим периодическим колебаниям.

[alexeybobkov]

Хм. Да, вы правы, будет цикл.
Интересно бы промоделировать.

P.S.Вообще надо переходить на Haskell. Сейчас написал бы уравнения 4 инверторов, построенных на двух, а потом бы написал монаду с задержкой сигнала, вот и всё моделирование :)

[adp.myopenid.com (from livejournal.com)]

:-)

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

С современной высокой частотой работы железа это принесло бы невероятные трудности. Уже сейчас время переключения вполне легального гейта уже одного порядка с временем одного периода клок-цикла. Приходится долго сводить дизайн, чтобы схема корректно работала. Если же ещё допустить большие циклы из гейтов, в которых будут такие колебания, то работать с таким дизайном будет уже невозможно. Каждый гейт в цикле имеет собственную задержку + задержки в проводах, да ещё это всё должно будет несколько раз прокрутиться до тех пор, пока не установятся стабильные сигналы. Чем это всё рассчитывать, просто запрещают комбинационные циклы в дизайне. И совсем уж сумасшедший дом получится при переходе с одной библиотеки реализаций гейтов на другую, с новыми задержками. Там вообще всё пересчитывать заново, потому что легальные циклы могут стать нелегальными. (Пересчитывать заново и кучу всего переписывать приходится и так, но это уже другая тема :-)