задачка, компьютерное
Feb. 14th, 2010 02:18 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaУбил на нее немало времени сегодня, но очень понравилась:
Придумайте схему, у которой есть три входа A, B, C и три выхода not-A, not-B, not-C. Можно пользоваться элементами AND, OR и NOT, но AND и OR сколько угодно, а NOT не более двух штук.
Я на время постараюсь скрывать правильные ответы. Но у меня есть предложение: если вы уже знаете решение, или нашли его компьютерным перебором, не пишите его в комментах - напишите просто, что нашли, например. Нет ничего плохого в компьютерном переборе, но не всем интересно. Мне хотелось именно найти решение самому аналитическим путем.
Придумайте схему, у которой есть три входа A, B, C и три выхода not-A, not-B, not-C. Можно пользоваться элементами AND, OR и NOT, но AND и OR сколько угодно, а NOT не более двух штук.
Я на время постараюсь скрывать правильные ответы. Но у меня есть предложение: если вы уже знаете решение, или нашли его компьютерным перебором, не пишите его в комментах - напишите просто, что нашли, например. Нет ничего плохого в компьютерном переборе, но не всем интересно. Мне хотелось именно найти решение самому аналитическим путем.
no subject
Date: 2010-02-15 03:39 pm (UTC)Интересно бы промоделировать.
P.S.Вообще надо переходить на Haskell. Сейчас написал бы уравнения 4 инверторов, построенных на двух, а потом бы написал монаду с задержкой сигнала, вот и всё моделирование :)
no subject
Date: 2010-02-15 03:58 pm (UTC)Вообще, проработав 4 года в индустрии, из них 2 в исследовательском подразделении, могу с уверенностью утверждать, что схемы с комбинационными циклами между гейтами, реализующими полноценные булевы функции, избегаются практически во всех промышленных мэйнстримных методологиях (по разговорам со старшими товарищами), сам я ни разу с такими не сталкивался.
С современной высокой частотой работы железа это принесло бы невероятные трудности. Уже сейчас время переключения вполне легального гейта уже одного порядка с временем одного периода клок-цикла. Приходится долго сводить дизайн, чтобы схема корректно работала. Если же ещё допустить большие циклы из гейтов, в которых будут такие колебания, то работать с таким дизайном будет уже невозможно. Каждый гейт в цикле имеет собственную задержку + задержки в проводах, да ещё это всё должно будет несколько раз прокрутиться до тех пор, пока не установятся стабильные сигналы. Чем это всё рассчитывать, просто запрещают комбинационные циклы в дизайне. И совсем уж сумасшедший дом получится при переходе с одной библиотеки реализаций гейтов на другую, с новыми задержками. Там вообще всё пересчитывать заново, потому что легальные циклы могут стать нелегальными. (Пересчитывать заново и кучу всего переписывать приходится и так, но это уже другая тема :-)