Конечный автомат может использоваться для определения факта вхождения заданных последовательностей значений в последовательность двоичных значений
Конечный автомат может использоваться для определения факта вхождения заданных последовательностей значений в последовательность двоичных значений, подаваемых на вход автомата. Такой автомат называется распознающим конечным автоматом. Предположим, что в ответ на вторую единицу в каждой последовательности 011, поступившей на вход автомата, он выдает 1 на выходе.
а) Нарисуйте диаграмму состояний такого автомата.
б) Обозначьте состояния автомата, составьте таблицу состояний и нарисуйте схему его реализации. Предполагается, что для решения задачи применяются D-триггеры.
в) Повторите задачу, сформулированную в упражнении 38 а, для автомата, распознающего входные последовательности 011 и 010, включая также случаи их пересечения. Например, для входной последовательности 110101011… должна генерироваться выходная последовательность 000010101….
Красным цветом рядом с каждой вершиной графа показан выходной сигнал.
У 4-разрядного сдвигового регистра имеется два управляющих входных сигнала
У 4-разрядного сдвигового регистра имеется два управляющих входных сигнала: INITIALIZE и RIGHT/LEFT. Когда на вход INITIALIZE подается значение 1, в регистр независимо от тактового сигнала загружается число 1000. Когда значение на входе INITIALIZE равно 0, сигналы на тактовом входе должны сдвигать содержимое регистра. Данные смещаются вправо или влево, когда значение RIGHT/LEFT равно соответственно 1 или 0. Нарисуйте схему такого регистра на основе D-триггеров со входами установки и очистки, как показано на рис. 32.
а
б
Рис. 32. Двухступенчатый D-триггер с входами установки и очистки:
схема (а); графическое обозначение (б)
Составьте таблицу истинности для схемы на основе вентилей И-НЕ
Составьте таблицу истинности для схемы на основе вентилей И-НЕ, которую вы видите на рис. 5. Сравните ее с таблицей истинности, приведенной на рис. 24, б, а затем выясните, можно ли считать эквивалентными схемы, представленные на рис. 25, а и 26.
Рис. 5. Схема защелки И-НЕ
Таблица истинности триггера:
а б
рис. 24
Схемы эквивалентны, однако входы и выходы одной схемы инверсны по сравнению с соответствующими входами и выходами другой.
Рис. 25а
Рис.26
Схемы на рисунках 25а и 26 функционируют как RS-триггеры только когда сигнал CLK=1. В противном случае схема не реагирует на входные сигналы.
Система кодирования чисел согласно которой последовательные числа
Система кодирования чисел, согласно которой последовательные числа, представленные двоичными кодами, отличаются только одним битом, называется кодом Грея. Таблица истинности 3-разрядного кода Грея для конвертора двоичного кода приведена на рис. 2, а.
а) Реализуйте функции f1, f2 и f3 с использованием только вентилей И–НЕ.
б) Чтобы минимизировать стоимость результирующей схемы, нужно выделить такие соответствия между входными и выходными переменными
f1=а
f2=f1b
f3= f2 с
Используя эти отношения, выделите ту часть схемы N, которую можно повторить, как показано на рис. 2,б. Сравните общее количество вентилей И–НЕ, необходимое для реализации операции преобразования в данной форме схемы, с количеством вентилей в схеме, которая у вас получилась в упражнении 14, а.
а
б
Рис. 2. Преобразование двоичных чисел в код Грея для упражнения 14: 3-разрядный код Грея для преобразования двоичного кода (а); схема преобразования кода (б)
В первоначальном варианте схема состоит из 6 двухвходовых элементов, 4 трёхвходовых и одного четырёхвходового, всего 11 элементов и 28 входов.
Во втором варианте — 10 двухвходовых элементов, 10 элементов и 20 входов.
а) Каково общее количество разных функций f(x1
а) Каково общее количество разных функций f(x1, х2, x3) трех двоичных переменных?
б) Сколько этих функций можно реализовать в виде ПМЛ-схемы того же типа, что и представленная на рис. 43?
в) Какое минимальное изменение в схеме на рис. 43 позволит реализовать функцию трех переменных в виде единственной схемы ПМЛ?
а) В таблице истинности функции трёх переменных 8 строк. В каждой строке может быть либо 0, либо 1. Следовательно, полное количество функций трёх переменных, включая тривиальные, равно 28 = 256.
Рис. 43
б) (23+22+21)2 = (8+4+2)2 = 142 = 196.
в) Добавить четвёртую переменную такого же типа как x1…x3.
В разделе 13 для создания синхронной последовательной схемы использовались D-триггеры
В разделе 13 для создания синхронной последовательной схемы использовались D-триггеры. Это простейшее решение, поскольку значения логической функции для входа D определяются следующим состоянием, указанным в таблице состояний. Предположим, что вместо D-триггеров для создания той же схемы будут использованы JK-триггеры. Составив таблицу состояний, покажите, как определить значения для входов J и К в виде функции от каждого возможного перехода из текущего состояния триггера в следующее. (Подсказка: таблица должна содержать четыре строки, по одной для каждого перехода: 00, 01, 10, 11; значениями входов J и К должны быть 0,1 или «безразлично»). Примените информацию этой таблицы для синтеза отдельных логических функций для обоих входов каждого из двух триггеров 2-разрядного двоичного счетчика из упражнения 33. Как вы считаете, данная реализация проще или, наоборот, сложнее по сравнению с реализацией счетчика на основе D-триггеров?
Переход 0→0
С одной стороны, триггер переходит в состояние 0, значит JK=10.
С другой стороны, триггер не меняет состояние, значит JK=00.
В результате: JK = (10 или 00) = ×0.
Переход 0→1
С одной стороны, триггер переходит в состояние 1, значит JK=01.
С другой стороны, триггер меняет состояние, значит JK=11.
В результате: JK = (01 или 11) = ×1.
Переход 1→0
С одной стороны, триггер переходит в состояние 0, значит JK=10.
С другой стороны, триггер меняет состояние, значит JK=11.
В результате: JK = (10 или 11) = 1×.
Переход 1→1
С одной стороны, триггер переходит в состояние 1, значит JK=01.
С другой стороны, триггер не меняет состояние, значит JK=00.
В результате: JK = (01 или 00) = 0×.
Таблица переходов JK-триггера
Строим счётчик из задачи 33 на JK-триггерах
Имеется функция f(x1 … x4) = (x1 x3) + (x1 x3+13 ) x4 +x12 а) С помощью карты Карно найдите для этой функции сумму произведений с минимальной стоимост
Имеется функция
f(x1,…,x4) = (x1 x3) + (x1 x3+13 ) x4 +x12
а) С помощью карты Карно найдите для этой функции сумму произведений с минимальной стоимостью.
Восстанавливаем по выражению карту Карно:
По карте Карно минимизируем выражение:
б) Найдите сумму произведений с минимальной стоимостью для ,то есть для дополнения функции f. Затем с помощью закона де Моргана образуйте дополнение этого выражения, чтобы получить выражение для f в форме суммы произведений. Сравните его стоимость со стоимостью выражения для вычисления суммы произведений, полученной при выполнении задания 5, а. Можете ли вы сделать на основании данного результата какое-либо общее заключение?
Строим карту Карно для дополнения, меня нули на единицы и наоборот.
Записываем минимальное выражение
В торговом автомате описанном в разделе 13
В торговом автомате, описанном в разделе 13.4, выдача товара ассоциировалась со значением на двоичном выходе z. Сдачу автомат не возвращал. Усовершенствуйте эту модель автомата так, чтобы он правильно возвращал сдачу. Предполагается, что он может получать монеты достоинством 10 и 25 центов в следующей последовательности: 10-10-10, 10-25, 25-10, 25-25. После того как в автомат будет опущена последняя монета, он должен вернуть соответственно 0, 5, 5 или 20 центов. Добавьте в него два новых двоичных выхода, z2 и z3, для представления трех различных выходных сигналов.
а) Составьте таблицу состояний, включающую новые выходы.
б) Составьте логические выражения для новых выходов z2 и z3.
в) Имеются ли в новой таблице эквивалентные состояния?
a)
б)
в) Все состояния, в которых определены выходные сигналы, имеют разные выходные сигналы, поэтому не могут быть эквивалентными.
Все состояния, где выходные сигналы не определены, могут быть эквивалентными, однако каждое состояние имеет индивидуальную численную характеристику — сумму денег, внесённую пользователем прежде чем автомат достиг данного состояния. У всех состояний эта характеристика различна, поэтому состояния не могут быть эквивалентными.
На рис 33 показан 3-разрядный счетчик прямого счета
На рис. 33 показан 3-разрядный счетчик прямого счета. Счетчик, считающий в порядке 7, 6, …, 1, 0, 7, …, называется счетчиком обратного счета. Счетчик, который может считать в любом из направлений в зависимости от сигнала UP/DOWN, называется счетчиком прямого/обратного счета. Приведите логическую схему трехразрядного счетчика прямого/обратного счета, который можно установить в любое из состояний путем параллельной загрузки его триггеров из внешнего источника. Управляющий вход LOAD/COUNT должен определять, какая операция — загрузка счетчика или счет — будет выполняться.
