вход Вход Регистрация



 

 

 

Рис. 1.

 

 

 

 

 

 

 

Рис. 2.

 

 

 

Рис. 3.

 

 

 

 

 

 

Рис. 4.

 

Тема 8

Канонический метод структурного синтеза ЦА с памятью

 

Канонический метод структурного синтеза ЦА с памятью позволяет свести задачу структурного синтеза произвольного ЦА с памятью к задаче синтеза комбинационных схем. Этот метод оперирует с элементарными автоматами двух классов: элементарными автоматами с памятью (элементы памяти) и элементарными комбинационными автоматами (логические элементы).

Результатом работы метода являются уравнения булевых функций автомата в канонической форме представления. Исходными данными для начала работы служит абстрактный автомат ЦА с памятью. Канонический метод можно условно разделить на следующие этапы:

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

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

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

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

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

 

Кодирование

 

Абстрактный ЦА может быть описан в виде .

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

Процесс замены букв алфавита абстрактного автомата двоичными векторами называется кодированием и может быть описан таблицами кодирования.

Пример: Абстрактный автомат Мили задан совмещенной таблицей переходов-выходов 1. Кодирование букв алфавита , представлено таблицами 2, 3, 4. При этом , , , , , .

 

 

Таблица 1

 

 

 

 

Таблица 2

 

вх. сигн. код

 

 

 

Таблица 3

 

вых. сигн. код

 

 

 

Таблица 4

 

состояния код

 

 

 

 

 

Таблица 5

входные сигналы
состояния
01
10/00

 

 

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

 

 

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

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

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

Полнота системы переходов-выходов для любой пары состояний ЦА существует входной сигнал, переводящий ЦА из одного состояния в другое.

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

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

В качестве элементов памяти структурного автомата обычно используются D -, T -, RS - и JK - триггеры, удовлетворяющие требованиям относительно полноты переходов и выходов. Каждый из приведенных триггеров является автоматом Мура. Входы D, T, RS и JK называются информационными. Таблицы переходов триггеров составляются только для информационных входов. Остальные входы являются вспомогательными (C, R, S). Каждый триггер имеет два выхода и.

 


 

 

 

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

 

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

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

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

- выходы элементов памяти, где

- число элементов памяти;

- функции возбуждения элементов памяти;

- выходные каналы структурного автомата, где

- число выходных каналов.

Для автомата Мили, описанного табл. 1 получаем: необходимо два элемента памяти, т.к. векторы состояний – двухкомпонентные, необходимо два выходных и один входной каналы.

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

 

Кодирование и выбор системы элементов однозначно определяют комбинационную часть автомата. Вначале строится таблица истинности функций возбуждения элементов памяти автомата (таблицы функций возбуждения). По таблицам записываются уравнения функций возбуждения в СДНФ, которые могут быть минимизированы.

Исходными данными для построения таблицы возбуждения являются структурная таблица переходов ЦА (табл. 5) и таблица переходов элемента памяти (табл. 6-9). Идентификация столбцов и строк таблицы функции возбуждения совпадает со структурной таблицей переходов ЦА. Клетки внутри таблицы заполняются специальным образом. На пересечении строки и столбца ставится значение информационного сигнала, который переводит выбранный триггер из исходного состояния в состояние, записанное в этой клетке в структурной таблице переходов ЦА. При этом выходные сигналы автомата не рассматриваются. Каждой компоненте вектора состояний структурного автомата поставлен в соответствие выход триггера или . Таблицы функций возбуждения (табл. 10-13) - это таблицы истинности булевых функций возбуждения элементов памяти автомата. При использовании RS - и JK – триггеров функции возбуждения получились частично определенными.

 

 

Таблица 10 функций возбуждения D - триггера

Состояния автомата Входные сигналы
U1 U2 U1 U2
0 0 0 1 0 0
0 1 0 1 0 0
1 0 1 0 0 1

 

Таблица 10 функций возбуждения T - триггера

Состояния автомата Входные сигналы
U1 U2 U1 U2
0 0 0 1 0 0
0 1 0 0 0 1
1 0 0 0 1 1

Таблица 12 функций возбуждения RS-триггера

Состояния автомата Входные сигналы
0 0 * 0 0 1 * 0 * 0
0 1 * 0 0 * * 0 1 0
1 0 0 * * 0 1 0 0 1

 

Таблица 13 функций возбуждения JK-триггера

Состояния автомата Входные сигналы
0 0 0 * 1 * 0 * 0 *
0 1 0 * * 0 0 * * 1
1 0 * 0 0 * * 1 1 *

 

Т.к. булева функция возбуждения i-го элемента памяти автомата зависит от компонент векторов состояния и компонент векторов входных сигналов ЦА, то в СДНФ эти булевы функции возбуждения могут быть представлены такими уравнениями.

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

,

;

б) для D-триггеров:

,

;

в) для RS-триггеров:

, ,

, ;

г)для JK-триггеров

, ,

, .

Получение канонических уравнений булевых функций выходов структурного автомата может быть сделано по структурной таблице выходов (табл. 5) автомата, которая является таблицей истинности булевых функций выходов автомата. Уравнения булевых функций выходов автомата не зависят от типа используемых элементов памяти, но зависит от их количества. Выделим структурную таблицу выходов (табл. 14) выходов автомата Мили из табл. 5.

 

;

или

.

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

 

На основании полученных выражений для булевых функций возбуждений элементов памяти автомата и булевых функций выходов автомата строятся КС функций возбуждения и КС формирования выходных сигналов. Элементы памяти подключаются к построенным КС. Функциональная схема автомата Мили при использовании Т-триггера представлена на рис. 1, D-триггера – на рис. 2, RS-триггера – на рис. 3, JK-триггера – на рис.4.

 

 

Рис. 1.

 

 

 

 

 

 

 

Рис. 2.

 

 

 

Рис. 3.

 

 

 

 

 

 

Рис. 4.

 

© 2018
  • Сайт "Литературка"
  • мы собираем различную техническую, образовательную, научную литратуру