Глава 12. ПРОЕКТИРОВАНИЕ ЦИФРОВЫХ АВТОМАТОВ С ПАМЯТЬЮ

12.1. КАНОНИЧЕСКИЙ МЕТОД СТРУКТУРНОГО СИНТЕЗА АВТОМАТОВ С ПАМЯТЬЮ

Общие сведения

Если синтез комбинационных схем сводится к реализации аналитических выражений булевых функций с помощью логических элементов, то синтез цифровых автоматов с памятью не столь очевиден. В общем случае задача структурного синтеза автоматов с памятью сводится к нахождению общих приемов построения структурных схем сложных автоматов на основе композиции некоторых элементарных автоматов, т. е. поиску определенных способов их соединения между собой. Следует подчеркнуть, что далеко не при всяком выборе системы элементарных автоматов можно построить (путем их композиции) любой структурный автомат. В том случае, если это возможно, говорят, что заданная система элементарных автоматов структурно полна. Однако и на основе структурно полных систем элементарных автоматов эффективно решить задачу структурного синтеза произвольного автомата с памятью пока удается только для структурно полных систем элементарных автоматов некоторого специального вида. Рассмотрим один из таких методов синтеза, позволяющий свести задачу структурного синтеза произвольного автомата с памятью к задаче синтеза комбинационных схем. Метод синтеза, в основу которого положен указанный принцип, получил название канонического метода структурного синтеза автоматов с памятью. Канонический метод структурного синтеза оперирует с элементарными автоматами, разделяющимися на два больших класса. Первый класс составляют элементарные автоматы с памятью, называемые элементами памяти. Второй класс составляют элементарные комбинационные автоматы — логические элементы. Для сведения задачи структурного синтеза произвольного автомата с памятью к задаче синтеза комбинационных схем накладывают ограничения на тип элементов памяти. Результатом работы метода являются уравнения булевых функций автомата в канонической форме представления. Исходным данным для начала работы метода служит абстрактный цифровой автомат с памятью. Канонический метод структурного синтеза условно можно разделить на следующие этапы:

1) кодирование;

2) выбор элементов памяти автомата;

3) выбор структурно-полной системы элементов;

4) построение уравнений булевых функций выходов и возбуждения автомата;

5) построение функциональной схемы автомата.

Рассмотрим каждый из перечисленных этапов подробно.

Кодирование

Как отмечалось выше (см, гл, 10), произвольный цифровой автомат с памятью А на абстрактном уровне представления может быть описан в виде При переходе на структурный уровень представления каждая буква входного алфавита X автомата представляется как двоичный вектор или двоичный набор, число компонентов которого равно числу физически реализованных входных каналов структурного автомата. Иными словами, каждая буква кодируется двоичным вектором. Очевидно, минимальное число физически реализованных входных каналов в автомате может быть подсчитано по формуле где — мощность алфавита входов X. Например, если то 2. Иными словами каждую букву можно закодировать двоичным вектором, состоящим не менее чем из двух компонент, например Каждая буква выходного алфавита автомата также представляется как двоичный вектор, число компонент которого равно числу физически реализованных выходных каналов автомата. По аналогии минимальное число компонент двоичного вектора выходов автомата определяется по формуле Каждая буква алфавита состояний автомата представляется двоичным вектором, минимальное число компонент которого определяется по формуле Процесс замены букв алфавитов X, К, 5 абстрактного автомата двоичными векторами носит название кодирования и может быть описан таблицами кодирования. Таблица кодирования составляется следующим образом: в левой ее части перечисляются все буквы (например, входного алфавита абстрактного автомата), а в правой — двоичные векторы, которые ставятся в соответствие этим буквам.

Пример. Абстрактный автомат Мили задан совмещенной таблицей переходов — выходов (табл. 12.1). Кодирование букв алфавитов представлено соответствующими таблицами кодирования (табл. 12.2; 12.3; 12.4). При этом, так как то

Таблица 12.1

Таблица 12.2

Таблица 12.3

Таблица 12.4

Таблица 12.5

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

Выбор элементов памяти автомата

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

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

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

Полнота системы выходов означает, что различным состояниям автомата соответствуют различные выходные сигналы. Обычно нулевому состоянию элементарного автомата соответствует нулевой выходной сигнал, единичному — единичный.

Очевидно, что число элементов памяти структурного автомата равно числу компонент вектора его состояний.

В качестве элементов памяти структурного автомата обычно используются D-триггеры; T-триггеры; RS-триггеры; JK-триггеры, удовлетворяющие требованиям относительно полноты переходов и выходов. Таблицы их переходов представлены табл. 12,6; 12.7; 12.8 и 12.9 соответственно, а условные изображения триггеров — рис. 12.1; 12.2; 12.3

Рис. 12.1

Рис. 12.2

Рис. 12.3

Рис. 12.4

Таблица 12.6

Таблица 12.7

Таблица 12.8

Таблица 12.9

и 12.4/ Входы называются информационными. Таблицы переходов триггеров составляются только для информационных входов. Остальные входы являются вспомогательными. В частности, вход -триггера — вход его установки в ноль, вход — вход установки триггера в единицу, а вход С — вход для подключения синхросерии (о чем будет сказано ниже). Каждый из триггеров имеет два выхода. Появление единичного сигнала на выходе, помеченном на рисунках символом а, означает, что триггер находится в единичном состоянии. Появление единичного сигнала на выходе а говорит о нулевом состоянии. Для -триггера входная комбинация является запрещенной, так как может привести к неоднозначной работе триггера. Каждый из приведенных триггеров является автоматом Мура с полной системой переходов (последнее следует из таблиц переходов триггера) и полной системой выходов (каждое состояние триггера является его выходным сигналом).

Выбор структурно-полной системы элементов

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

Рис. 12.5

Рис. 12.6

систему логических элементов. Теоретическим фундаментом канонического метода структурного синтеза автоматов с памятью является теорема о структурной полноте: всякая система, содержащая элементарные автоматы Мура с нетривиальной памятью, обладающие полной системой переходов и полной системой выходов и какую-либо функционально-полную систему логических элементов, является структурно-полной, т. е. позволяет синтезировать произвольный цифровой автомате памятью. Таким образом, для построения структурного автомата необходимо кроме элементов памяти иметь комбинационную схему, реализующую булевы функции возбуждения элементов памяти автомата, а для выработки выходных сигналов структурного автомата — специальную комбинационную схему формирования выходных сигналов автомата. Функция возбуждения структурного автомата является векторной. Ее аргументами являются пары двоичных векторов , а значением функции — двоичный вектор, каждая компонента которого есть значение булевой функции возбуждения элемента памяти автомата, определяющая тот двоичный сигнал, который необходимо подать на вход элемента памяти для обеспечения его переключения в соответствии с требованиями структурной таблицы переходов. Если векторная функция переходов задает переход из одного вектора состояния структурного автомата в другой вектор состояния под воздействием двоичного вектора входного сигнала, то векторная функция возбуждения автомата задает двоичный вектор, который нужно подать на входы элементов памяти автомата, чтобы обеспечить требуемый переход (в соответствии с векторной функцией переходов автомата). Последнее означает, что переменными, от которых зависит векторная функция возбуждения, являются те же переменные, что и для векторной функции переходов автомата, т. е. выходы всех элементов памяти автомата и входы автомата. Поэтому структурный автомат Мура, в общем случае, может быть представлен структурной схемой (рис. 12.5), а

структурный автомат Мили — структурной схемой (рис. 12.6). Буквами на рисунках обозначены выходы элементов памяти, где число элементов памяти. Буквами , обозначены булевы функции возбуждения элементов памяти. Для простоты положим, что каждый элемент памяти структурного автомата имеет один информационный вход. Буквами обозначены выходные каналы автомата, где - число выходных каналов автомата. В результате получаем: для построения структурного автомата необходимо взять два элемента памяти (так как двоичные векторы состояний — двухкомпоненты), два выходных и один входной каналы (см. табл. 12.1)

Построение уравнений булевых функций возбуждения и выходов автомата

Кодирование и выбор системы элементов однозначно определяют комбинационную часть автомата: вначале строится таблица истинности функций возбуждения элементов памяти автомата, получившая название таблицы функций возбуждения; канонические уравнения функций возбуждения выписываются исходя из построенной таблицы. Полученная аналитическая запись булевой функции возбуждения (для каждого элемента памяти автомата) может быть минимизирована любым из известных методов. Исходными данными для построения таблицы функций возбуждения являются структурная таблица переходов автомата и таблица переходов элемента памяти. Обрамление таблицы функций возбуждения, т. е. идентификация ее строк и столбцов полностью совпадает с обрамлением структурной таблицы переходов синтезируемого автомата. Клетки, расположенные внутри таблицы функций возбуждения, полняются специальным образом. Для упрощения объяснения обратимся к примеру (табл. 12.5), считая, что в качестве элементов памяти автомата используются Г-триггеры (рис. 12.2), Рассмотрим фрагмент структурной таблицы переходов автомата (табл. 12.10). В приведенном фрагменте выходные сигналы автомата не рассматриваются; каждой компоненте вектора состояний структурного автомата поставлен в соответствие выход триггера (обозначено буквой а с индексом); отсутствие сигнала во входном канале структурного автомата обозначено символом а наличие — символом Как следует из фрагмента, триггер под воздействием входного сигнала из состояния 1 должен перейти в состояние 1. В аналогичном фрагменте

Таблица 12.10

Таблица 12.11

Таблица 12.12

Таблица 12.13

Таблица 12.14

таблицы функций возбуждения автомата внутри клетки, находящейся на пересечении столбца, помеченного символом и строки, помеченной вектором состояния для триггера необходимо указать сигнал» который нужно подать на его вход для обеспечения перехода Для того чтобы найти значение этого сигнала, обратимся к таблице переходов Г-триггера (табл. 12.7). Как следует из таблицы, переход Г-триггера вида 1 1 осуществляется только под воздействием сигнала 0. Следовательно, в соответствующем месте таблицы функций возбуждения следует поставить 0. Рассмотрим переход триггера из состояния 1 в состояние 0 под воздействием входного сигнала (табл. 12.10). Для его реализации на вход Г-триггера нужно подать сигнал 1 (табл. 12.7). Фрагмент таблицы функций возбуждения структурного автомата, соответствующий фрагменту структурной таблицы переходов автомата, представлен втабл. 12.11. Полная таблица функций возбуждения автомата (для случая использования в качестве элементе» памяти Г-триггеров) представлена в табл. 12.12. Символами в таблице обозначены функции возбуждения элементов памяти Формально, для случая использования Г-триггеров таблица функций возбуждения автомата может быть получена покомпонентной суммой по модулю 2 двоичных векторов состояний автомата при условии, что вектор состояния есть результат перехода автомата из вектора состояния Аналогично может быть составлена таблица функций возбуждения автомата и для случая использования D-триггеров в качестве его элементов памяти. Таблица функций возбуждения автомата пр» этом полностью совпадает со структурной таблицей его переходов. Последнее связано с особенностями функционирования D-триггера, Возвращаясь к примеру, получаем следующую таблицу функций возбуждения автомата (табл. 12.13).

Составление таблицы функций возбуждения автомата в случае использования или -триггеров в качестве элементов памяти имеет ряд отличительных особенностей, связанных с тем, что указанные триггеры имеют по два информационных входа. Для рассматриваемого примера таблицы функций возбуждения структурного автомата представ? лены: табл. 12.14 — при использовании -триггеров и табл. 12.16 —?; при использовании -триггеров. Функции возбуждения элемента памяти отмечены в таблицах символами

Поясним составление таблиц на примере перехода автомата из состояния в состояние под воздействием входного сигнала

Таблица 12.15

Таблица 12.16

Здесь имеет место для первого триггера переход 0 0, для второго — переход , Как следует из таблицы переходов -триггера (табл. 12.8), для перехода триггера на его входа необходимо подать Знак означает, что на вход можно подавать либо 0 либо 1, значение результата перехода RS-триггера при этом не изменится; на вход 5 обязательно нужно подать 0. Для перехода RS-триггера вида на его -входы нужно подать сигнал Аналогично заполняются и клетки таблицы функций возбуждения при использовании -триггеров в качестве элементов памяти автомата. Таким образом, становится понятным, что функции возбуждения элементов памяти структурного автомата при использовании RS и JK-триггеров будут частично определенными. Полученные таблицы функций возбуадения (табл. 12.12; 12.13; 12.14; 12.15) есть таблицы истинности булевых функций возбуждения элементов памяти автомата. Напомним, что переменными, от которых зависит булева функция возбуждения элемента памяти структурного автомата, являются компоненты двоичных векторов состояний и компоненты двоичных векторов входных сигналов структурного автомата. В связи с этим булевы функции возбуждения структурного автомата в СДНФ могут быть представлены следующими уравнениями:

а) для случая использования Т-триггеров в качестве элементов памяти автомата:

б) для случая использования D-триггеров

в) для случая использования RS-трнггеров

г) для случая использования JK-триггеров

Таблица 12.17

Таблица 12.18

Таблица 12.19

Получение канонических уравнений булевых функций выходов структурного автомата проще и может быть сделано непосредственно по структурной таблице выходов автомата. Структурная таблица выходов автомата есть таблица истинности булевых функций выходов автомата. Иными словами, уравнения булевых функций выходов автомата не зависят от типа используемых элементов памяти, однако зависят от их количества. Выделим структурную таблицу выходов автомата Мили (табл. 12.16) из структурной таблицы переходов — выходов (табл. 12.5). Тогда уравнения булевых функций выходов синтезируемого структурного автомата будут иметь вид:

Уравнения для и не изменяются при переходе от синтеза автомата на триггерах одного типа к синтезу автомата на триггерах другого типа.

Если синтезируемый автомат является автоматом Мура, то задача построения уравнений булевых функций возбуждения решается так же. Уравнения булевых функций выходов автомата Мура строятся несколько иначе. Последнее связано с различиями в способах построения структурных таблиц выходов автомата Мили и Мура. Таблица выходов абстрактного автомата Мура имеет вид (табл. 12.17). Приведенная таблица выходов представлена для конкретного автомата Мура. После проведения этапа кодирования состояний автомата (табл. 12.3) и кодирования выходных сигналов (табл. 12.18) получаем структурную таблицу выходов автомата Мура (табл. 12.19), являющейся таблицей истинности булевых функций выходов автомата (в данном случае функции ). Уравнение для в соответствии с таблицей истинности может быть записано в виде

Построение функциональной схемы автомата

На основании полученных выражений для булевых функций возбуждения элементов памяти автомата и булевых функций выходов автомата строятся комбинационная схема функций возбуждения и

Рис. 12.7

Рис. 12.8

комбинационная схема формирования выходных сигналов автомата. Элементы памяти подключаются к построенным комбинационным схемам, как показано на рис. 12.5; 12.6. Функциональная схема такого соединения в автомате Мили для случая использования Т-триггеров представлена на рис. 12.7, для случая использования D-триггеров — на рис. 12.10, для случая использования RS-триггеров — на рис. 12.9, для случая использования JK-триггеров — на рис. 12,8. Функциональная схема автомата Мура отлична только комбинационной схемой формирования выходных сигналов, которая строится на основании уравнений для булевых функций выходов. Отметим, что реализация комбинационных схем (рис. 12.7; 12.8; 12.9; 12.10) произведена в булевом базисе, а задача получения минимальных комбинационных схем не ставилась. На рисунках лишь иллюстрируется заключительный этап структурного синтеза автоматов с памятью, без анализа вопросов устойчивости их работы. 7

Рис. 12.9

Рис. 12.10