Контрольный пример

Задание. Построить логическую схему последовательного компаратора для сравнения 2 двоичных чисел А, В произвольной длины, поступающих на вход, начиная с младших разрядов. По окончании подачи чисел А, В на вход компаратора на его выходе должны появиться сигналы: y ₀, если А=В, y ₁ если A< B, у ₂ если A> B, у ₃.

Решение.

1. Введем в рассмотрение входные буквы: x ₀₀, х ₁₁, x ₀₁, х ₁₀, где нижний первый индекс соответствует значению текущего разряда числа А, а второй — числа В. С точки зрения сравнения чисел А, В действие букв x ₀₀, х ₁₁ равносильно, что позволяет их рассматривать как одну букву, обозначаемую в дальнейшем x ₀.

2. Формализуем условия работы искомого автомата на языке регулярных выражений, эти условия приобретают вид:

(3.1)

(3.2)

(3.3)

Здесь итерационные скобки { }+={ }* e, где е – пустая буква,

введена для сокращения длины записи регулярных выражений.

Полученный граф — рис. 3.1 содержит три финитные вершины 1, 3, 4, соответствующие выходным реакциям у ₀, y ₁, y ₂.

Рис. 3.1. Обобщенный граф регулярных выражений (3.1) – (3.3)

«Нейтральная» вершина 2 помечена пустой буквой е. Каждая финитная вершина с помощью пустой стрелки замыкается на начальную вершину, что соответствует воспроизведению итерационных скобок { }+. Номера вершин, «переносимых» по пустым стрелкам выписаны через запятую слева относительно вершин 0 и 2.

3. Переходим к построению обобщенного графа регулярных выражений (3.1) – (3.3).

4. Применяя методику детерминизации графа регулярных выражений (раздел 1.1), приходим к табл. 3 I.

Таблица 3.1

Вых.	–
Сост.		1 2	2 3

x₀ 1 2 1 2 2 3 2 4

x₀₁ 2 3 2 3 2 3 2 3

x₁₀ 2 4 2 4 2 4 2 4

Отсутствие противоречий при определении дизъюнкций выходных сигналов в табл. 3.1 свидетельствует о том, что система регулярных выражений (3.1) – (3.3) является корректной.

В дальнейшем при определении реакций автомата y ₀, y ₁, y ₂ пустой символ, е можно не учитывать.

5. Переходим к эквивалентному автомату Мили, открывающему возможность получения абстрактной схемы наименьшей сложности (по числу состояний). Первоначальная модель содержит 4 состояния: . Так как разбиение не поддается расщеплению (совпадает с разбиением ), убеждаемся, что изображенный на рис. 1.2 – минимальный автомат.

6. Для проверки результатов абстрактного синтеза, а в случае неудачи (несоответствие поведения автомата техническому заданию, отсутствие видимых способов получения корректного описания), индуктивно воспроизводим дерево управления искомого автомата – рис. 1.1. Приняты следующие соглашения. Каждый «веер» ребер слева направо определяется входными буквами соответственно. Все ребра дерева помечены цифрами 0, 1, 2, соответствующими выходным реакциям . Дерево построено в предположении, что r =1, d =1, и потому имеет высоту h ==3.

На дереве ясно просматриваются 3 различимые вершины базиса. Остальные зачеркнутые на рис. 1.1 вершины не отличимы от вершин базиса. Свертки дерева управле­ния приводят к точной копии искомого автомата (рис. 1.2).

Заметим, что все дуги, входящие в каждое из его состояний, помечены одинаковыми реакциями. Следовательно, граф на рис. 1.2 можно также рассматривать и как автомат Мура (рис. 3.2), что может дать некоторые преимущества на этапе структурного синтеза.

Рис. 3.2. Кодированный граф переходов

7. В качестве элементарного автомата выбираем D -триггер. Минимально возможное число D -триггеров – ] log 23[=2. Рассмотрим вариант неудачного кодирования состояний абстрактного автомата: , который приводит, во-первых, к усложнению КЛС, во-вторых, к возникновению состязаний ЭА. Так, при переключении из состояния в состояние под воздействием для промежуточного состояния на выходе автомата будет получен сигнал вместо требуемого сигнала . Значительно более удачным является вариант кодирования, представленный на рис. 3.2.

Каждому состоянию автомата приписано единичное значение одного из выходов . На рис. 3.2 также показаны: комбинации двоичных входов определяющие поразрядные значения чисел А и В; единичные значения функций возбуждения для 1-го и 2-го D -триггеров соответственно.

8. Как видно из кодированного графа переходов – рис. 3.2:

Нетрудно также получить функцию возбуждения

Функция V ₂ содержит 8 минитермов. Попытаемся ее минимизировать. Для этого воспользуемся диаграммой Вейча — рис. 3.3, где тонкими овалами выделены группы минитермов, образующих простые импликанты. В результате минимиза­ции ФАЛ V ₂ получаем

9. Взяв за основу микросхемы серии К155 (см. [6] или рис, 2.2), обеспечивающие реализацию полученных в п. 8 функций, получаем один из вариантов логической схемы искомого автомата – рис. 3.4. Здесь для обозримости схемы принят графический прием вложения всех соединений в некоторую гипотетическую магистраль (жирная линия на рис. 3.4) с установлением строгого соответствия между одинаково пронумерованными входами и выходами. Как видно из рис. 3.4, для реализации последовательного компаратора требуется 5 корпусов или кристаллов.

Рис. 3.3. Диаграмма Вейча для функции V ₂

Рис. 3.4. Логическая схема компаратора (Вариант - 1)

10. Проверим возможность повышения качества синтеза за счет использования ПЛМ. Для реализации функций возбуждения необходимо пять вертикальных шин матрицы Ml (по общему числу минитермов). Выходную логику также выгодно вложить в ПЛМ. Для этого перейдем к автоматной модели Мили (рис. 1.2), принимая представленный на рис. 3.4 вариант кодирования состояний входных сигналов автомата. В соответствии с п. 5 раздела 3 убеждаемся в том, что функция в точности совпадает с функцией . В свою очередь каждая из функций содержит по 5 минитермов и после минимизации приобретает вид:

Для реализации всех полученных функций необходима ПЛМ со структурой , . В результате настройки ПЛМ на указанные функции получаем 2-й вариант логической схемы — рис. 3.5, который легко размещается на 2 кристаллах.

Рис. 3.5. Логическая схема компаратора (Вариант - 2)

Итак, мы раскрыли многие тонкости сквозного проектирования управляющего автомата с конечным числом состояний. Для того чтобы получить и обосновать Ваш проект управляющего автомата необходимо рассмотреть, по меньшей мере, 2 – 3 варианта его абстрактной и структурной реализации. Многоальтернативный синтез рекомендуется проводить с использованием пакета программ, именуемого SANAR [9] и разработанного студентами потока кафедры ВМСиС.

ВАРИАНТЫ ТИПОВОГО ЗАДАНИЯ

1. Построить логическую схему последовательного компаратора для сравнения 2 двоичных чисел А, В произвольной длины, поступающих на вход, начиная со старших разрядов. По сигналу окончания подачи чисел — сигналу на выходе компаратора должны появиться сигналы 0, если А=В, 1, если А< В, 2, если А> В.

2. Построить накапливающий сумматор для формирования поразрядных сумм и переносов в темпе поступления на вход сумматора 2 двоичных чисел произвольной длины, начиная с младших разрядов.

Указание: При построении «тестового» дерева управления исходить из предположения, что .

3. Построить логическую схему последовательной свертки по mod 3 двоичного числа, которое поступает на вход схемы, начиная со старших разрядов. Для считывания результата (чисел 0, 1, 2) и автоматической установки схемы в начальное состояние ввести сигнал .

4. Построить логическую схему последовательной свертки по mod 7 двоичного числа, подаваемого на вход схемы со старших разрядов. Результат (числа от 0 до 6) должен появляться на выходе схемы в темпе поступления двоичного числа разряд за разрядом.

Указание: Воспользоваться методом свертки дерева управления, если известно, что

5. Построить автомат для управления освещением 2 комнат. Расположение комнат K 1, K 2 и дверей показано на рис. 4.1. Вход человека в K 1 и K 2 сопровождается выработкой входных сигналов а его выход из K 1, K 2 – сигналов соответственно . Предполагается, что двери не могут срабатывать одновременно. В K 1 и K 2 могут находиться n ₁ и n ₂ человек. Лампочки Л 1, Л 2 должны гореть лишь в том случае, если в K 1 или в К 2 находится хотя бы один человек. Вариант построения автомата выбрать из табл. 4.1.

Рис. 4.1. План расположения комнат и дверей

Таблица 4.1

Указание: Выходные сигналы автомата целесообразно представить следующим образом:

– Л 1 и Л 2 не горит,

– Л 1 горит, Л 2 не горит,

– Л 1 не горит, Л 2 горит,

– Л 1 и Л 2 горят

6. Построить логическую схему электронного кодового замка, который должен открываться (сигнал ) при нажатии заданного числа раз n ₁– первой, n ₂– второй, n ₃ – третьей кнопок. При неправильном нажатии кнопок должен вырабатываться сигнал тревоги (сигнал ). Учесть необходимость автоматической установки автомата в начальное состояние. Вариант нажатия кнопок выбрать из табл. 4.2.

Таблица 4.2

7. Автомат для продажи билетов работает при получении жетонов достоинством 5 и 10 руб. В 1-м случае автомат выдает билет, если жетонный накопитель, вмещающий m рублевых жетонов, не заполнен; в противном случае автомат жетонов не принимает и билета не выдает. При получении 10 рублевого жетона автомат выдает билет и 5 рублевый жетон сдачи, если в приемнике есть хотя бы один 5 рублевый жетон.

Синтезировать описанный автомат для одного из вариантов табл. 4.3.

Таблица 4.3

8. Построить логическую схему тренажера, предназначенного для обучения операторов работе на пульте. Пульт имеет 4 кнопки , которые должны включаться в строго определенной последовательности. При правильном нажатии кнопок вырабатывается сигнал W, при неправильном – сигнал N. По окончании сеанса схема должна автоматически устанавливаться в начальное состояние. Одну из последовательностей нажатия кнопок выбрать из табл. 4.4.

Таблица 4.4

Вариант	Последовательность
8.1
8.2
8.3
8.4

9. Построить логическую схему электронной игрушки, имитирующей выработку условного рефлекса () у животного в ответ на воздействие безусловного (буква b) и условного (буква u) раздражителей. Совместное воздействие указанных раздражителей определяется буквой с. Игрушка характеризуется следующими параметрами: k –минимально возможное число букв c, необходимых для выработки в процессе обучения, l, m —число несовпадений раздражителей (либо b, либо u), что приводит к потере полученного навыка соответственно в процессе обучения и по окончании такового. Вариант построения автомата выбрать из табл. 4.5.

Таблица 4.5

10. Построить охранный автомат, который каждый раз при поступлении серий из n, n+ 1 сигналов s 1 формирует на выходе сигнал («предупреждение»). В случае поступления сигнала s 2 после серии сигналов s 1, большей или равной m, на выходе появляется сигнал («тревога») и автомат устанавливается в начальное состояние. Вариант автомата выбрать из табл. 4.6.

Таблица 4.6

11. Синтезировать распознающий автомат для сортировки изделий, передвигающихся на конвейере, по их длине. Датчики вырабатывают сигналы а, b, с (инверсные сигналы ) в случае появления (исчезновения) изделия, проходящего мимо соответствующей опоры. Фрагмент выдачи сигналов а и b показан на рис. 4.2. Разбраковка изделий по длине определяется следующими выходными сигналами:

, если l < l ₀; , если l₀ ≤ l ≤ 2 l ₀; , если l > 2 l ₀.

Рис. 4.2. Схема расположения датчиков на конвейере

12. Синтезировать комплектующий автомат, принимающий блоки А, В, С,..., расположенные на конвейере l в случайном порядке, и пропускающий их на конвейер 2 с целью формирования сборочных комплектов K 1, K 2,..., так как это показано на рис. 4.3.

Рис. 4.3. Схема формирования комплектов деталей на конвейере

Сборочные комплекты состоят из заданного числа блоков каждого типа, расположенных в строго определенной последовательности. На выходе автомата вырабатываются сигналы соответственно обеспечивающие сброс ненужного блока в бункер или пропуск недостающего блока на конвейер 2. Вариант реализуемого автомата выбрать из табл. 4.7.

Таблица 4.7

13. Построить дешифратор, на выходе которого вырабатывается десятичный эквивалент в темпе поступления соответствующего двоичного числа, начиная со старших разрядов. Окончание поступления разрядов двоичного числа фиксируется сигналом . Один из вариантов построения дешифратора выбрать из табл. 4.8.

Таблица 4.8

14. Построить счетчик по mod k, на вход которого посту­пают одиночные единичные сигналы, соответствующие некоторому числу в унарном коде. Вариант счетчика выбрать из табл. 4.9.

Таблица 4.9

15. Построить счетчик, осуществляющий счет одиночных единичных сигналов либо по mod , либо по mod в зависимости от значения установочного сигнала u. Вариант счетчика выбрать из табл. 4.10.

Таблица 4.10

Вариант	mod	mod
15.1
15.2
15.3

Указание: Для описания работы счетчика построить объединенное дерево управления, поставив в соответствие каждой левой ветви отсутствие сигнала, средней ветви наличие сигнала по , правой ветви наличие сигнала по .

16. Построить реверсивный счетчик, осуществляющий либо сложение, либо вычитание одиночных единичных сигналов в зависимости от задания режима его работы, (Вариант построения счетчика выбрать по табл. 4.9).

17. Построить логическую схему торгующего автомата для выдачи товаров двух типов, имеющих стоимость либо c 1, либо c 2 в зависимости от значения установочного сигнала . На вход автомата могут поступать монеты достоинством 1, 2, 5. Вариант автомата выбрать из табл. 4.11.

Таблица 4.11

18. Синтезировать автомат, обеспечивающий выдачу товара как при точном совпадении суммы монет с заданной стоимостью с товара, так и при некотором превышении этой стоимости, если у покупателя не оказалось монет нужного достоинства d ={1, 2, 5}. Если же покупатель ввел (второпях) неверную последовательность, превосходящую стоимость с (несмотря на наличие нужных монет), автомат должен сформировать сигнал ус —сброса принятых монет. Вариант автомата выбрать из табл. 4.12.

Таблица 4.12

19. Синтезировать автомат, обеспечивающий выдачу товара как при точном совпадении суммы монет с заданной стоимостью с товара, так и при некотором превышении этой стоимости, если у покупателя не оказалось монет нужного достоинства d= {1, 2, 5}. Предусмотреть режим сброса неправильного набора монет при наличии «лишней» монеты, без которой стоимость товара и так обеспечивается. Вариант автомата выбрать из табл. 4.13.

Таблица 4.13

20. Синтезировать автомат для последовательного преобразования числа Х, подаваемого на вход автомата последовательно старшими разрядами, представленного в q –ичной системе СС, в n -разрядный двоичный код Грея (см. табл. 4.14). По окончании переработки двоичного числа автомат должен устанавливаться в начальное состояние.

Указание: Значения разрядов у, кода Грея могут быть определены по правилу: , где - значение разрядов двоичного числа для

Таблица 4.14

21. Синтезировать автомат для последовательного преобразования n -разрядного двоичного числа либо, либо в код Грея, либо в его представление в q -ичной СС в зависимости от выбранного режима работы (табл. 4.15).

Таблица 4.15

22. Построить кодовый преобразователь, обеспечивающий последовательное преобразование n -разрядного кода числа в k -ичной позиционной системе счисления с натуральным основанием в m-разрядный код того же числа в l -чной позиционной системе счисления, начиная с младших разрядов (табл. 4.16).

Таблица 4.16

Указание. Для получения автоматного отображения произвести выравнивание длин входного и выходного кодов путем добавления 0 в младшие разряды кода, если n> m; в старшие разряды кода, если n< m.

23. Построить тетрадный анализатор, который при поступлении на вход любого 4-разрядного двоичного числа, начиная с младших разрядов, в случае, если это число < 10, вырабатывает сигнал у ₁ («правильная тетрада»), а в противном случае, - у ₀ («неправильная тетрада»). По окончании подачи числа, анализатор должен автоматически устанавливаться в начальное состояние.

24. Синтезировать автомат, осуществляющий возведение в квадрат двоичных чисел в диапазоне [ O ]₂ – [ N ]₂, подаваемых на его вход последовательно, начиная с младших разрядов. Вариант автомата задается в табл. 4.17.

Таблица 4.17

Указание. Применить прием приведения таблицы соответствия «Вход - Выход» к автоматному выражению за счет добавления необходимого числа 0 в старшие разряды.

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

26. Построить автомат, осуществляющий управление грузовым лифтом посредством выполнения следующих действий: открытие дверей по сигналу x ₁, закрытие дверей по сигналу x ₂ от таймера, движение на 2, 3,..., N этаж при нажатии соответствующих кнопок Кн.1, Кн.2, …, Кн. N, открытие двери по сигналу x ₃ от таймера, закрытие двери по сигналу x ₄ от таймера, спуск вниз на 1 – ый этаж, стоп. Варианты задания в табл. 4.17.