У меня есть вопрос с экзамена, который мне не удалось решить:
Мне нужно построить цифровую логическую схему , который принимает 4 номер бита и возврат , true
если число 0
, 7
или 14
. У меня есть только один XOR
вентиль (2 входа), один NOR
(3 входа), один NAND
(2 входа) и один декодер 3-8.
Я думаю, что этот вопрос неразрешим, я не нашел ни одной комбинации, которая могла бы это сделать. Есть идеи как это решить?
Ответы:
Я написал алгоритм на C #, который пробует все возможные комбинации тех
Nor 3->1
Xor 2->1
Nand 2->1
иDecoder 3->8
.Проработав
7,5 миллионов лет2 часа, он вернул42False. Я считаю, что это доказывает, что на вопрос нет ответа, так как этот алгоритм проверяет каждую возможную комбинацию. :)Меня попросили описать это, поэтому следующая часть - это объяснение частей кода, часть за частью. TL; DR - вы можете просто пропустить код внизу в конце :)
Давайте поговорим о входных строках, они имеют 0 или 1 состояния и для каждого из возможных входов (от 0 до 15) они имеют разные значения:
для первой строки это выглядит так: 0 1 0 1 0 1 ... вторая: 0 0 1 1 0 0 1 1 ... третья: 0 0 0 0 1 1 1 1 .... как двоичная считая ... у тебя есть идея: P
Итак, я создал объект, который представляет каждую строку в каждом из его состояний:
Как говорится, bitLine.IsActiveWhenInputIs [5] возвращают, была ли линия активной, когда на входе было 5.
Это код, который создает строки ввода в целом:
Мы также создадим битовые строки «всегда верно» и «всегда ложно» - чтобы обеспечить постоянный ввод «0» или «1».
Теперь, если вы заметили, что мы ищем на самом деле конкретную битовую линию, которая истинна, когда ввод равен 0, 7, 14. Давайте представим ее в нашем классе:
Это сделало вещи действительно простыми: то, что мы на самом деле ищем, это способ «подделать» эту необходимуюBitLine из входной битовой строки (именно так я представляю своей программе то, что я хочу, чтобы мой вывод был).
Теперь, это то , как мы идем дальше: каждый раз , когда мы используем некоторый логический элемент на нашем bitLines как
Xor
,Nor
,Nand
или дажеDecoder
, мы на самом деле создаем новый bitLine \ с. Мы знаем значение каждой из строк в каждом возможном входе от 0 до 15, поэтому мы можем вычислить новое значение bitLine \ s также для каждого возможного ввода!Нанд Нор и Ксор все просты:
Для каждого возможного ввода он представляет, как будет действовать новый BitLine.
Обработка декодера немного сложна, но идея в том, что «если биты на входе представляют число x в двоичном виде, то x-я строка выходного бита будет истинной, тогда как все остальные будут ложными. В отличие от других функция, эта получает массив битовых линий и добавляет 8 новых битовых линий в массив.
Теперь у нас есть все наши основные элементы, поэтому давайте поговорим об алгоритме:
Мы собираемся сделать рекурсивный алгоритм, на каждой глубине он будет пытаться использовать другие элементы (ни \ nand \ xor \ decoder) на доступных в настоящее время линиях битов, а затем установить элемент на непригодный для использования на следующей рекурсивной глубине. Всякий раз, когда мы достигаем дна и у нас больше нет элементов для использования, мы будем проверять, есть ли у нас битлайн, который мы и искали.
Этот код проверяет в любой момент времени, содержит ли текущая группа строк строку, которую мы ищем:
Эта функция используется для проверки того, равны ли две строки:
Итак, теперь для основной части это основной алгоритм:
Эта функция получает список доступных битовых строк, длину списка, логическое значение, представляющее, доступен ли каждый элемент в данный момент (xor / nor / nand / decoder), и битовую линию, представляющую искомую битовую линию.
На каждом этапе он проверяет, есть ли у нас какие-либо элементы для использования, если нет - он проверяет, архивируем ли мы нашу необходимую битовую линию.
Если у нас все еще есть больше элементов, то для каждого элемента он вызывает функцию, которая должна обрабатывать создание новых битовых линий с использованием этих элементов и последующее обращение к следующей рекурсивной глубине.
Следующие функции-обработчики довольно просты, их можно перевести как «выберите 2 \ 3 из доступных битовых линий и объедините их, используя соответствующий элемент. Затем вызовите следующую глубину рекурсии, просто на этот раз она не будет содержать». этот элемент!
это функции:
И это все, мы просто вызываем эту функцию с нужной линией, которую мы ищем, и она проверяет каждую возможную комбинацию электрических частей, чтобы проверить, можно ли объединить их таким образом, чтобы в итоге одна строка была выводится с необходимыми значениями.
* обратите внимание, что я все время использую один и тот же список, поэтому мне не нужно постоянно создавать новые экземпляры битовых линий. По этой причине я даю ему буфер 200.
Это полная программа:
Надеюсь, на этот раз это веское объяснение: P
источник
Это не ответ, чтобы отказаться от наиболее очевидного решения.
Тем не менее, упрощение предыдущего выражения:
это не ожидаемое
По этой причине, я считаю вероятной ошибкой в этом вопросе «nand» gate a »или« one ».
источник
Действительным ответом на ваш вопрос будет любая схема, которая всегда возвращает true. Потому что он вернет истину также, если введенные числа 0,7 или 14.
Я думаю, что вопрос должен явно задавать вопрос о схеме, которая выводит истину, если входные числа равны 0,7 или 14. И в противном случае выводит ложь.
источник
Это выполнимо. Как подсказка, средние два бита равны для всех этих битовых комбинаций, поэтому их сохранение приведет к 0, который затем может быть входом для декодера с двумя другими битами. Остальные вентили применяются к трем выходам декодера для обеспечения правильного однобитового выхода.
источник