рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

ТЕОРИЯ ЦИФРОВЫХ АВТОМАТОВ

ТЕОРИЯ ЦИФРОВЫХ АВТОМАТОВ - раздел Транспорт, Министерство Образов...

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

       
   
 
 

 


ЮЖНО–УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ


681.3(07)

Л561

 

ТЕОРИЯ ЦИФРОВЫХ АВТОМАТОВ

 

 


Челябинск

2010

 

А.Е.Гудилин, Т.А. Барбасова

Учебное пособие по курсу

«Цифровые автоматы»

Южно-Уральский государственный

университет

Приборостроительный факультет

Кафедра Автоматики и управления

Челябинск


СОДЕРЖАНИЕ

ВВЕДЕНИЕ........................................................................................................ 6

Глава 1................................................................................................................ 8

ЛОГИЧЕСКИЕ ОСНОВЫ ЦИФРОВЫХ АВТОМАТОВ........................... 8

1.1 Основные понятия алгебры логики....................................................... 8

1.2 Базис И, ИЛИ, НЕ. Свойства элементарных функций алгебры логики 11

1.3 Способы описания булевых функций................................................... 14

1.3.1 Табличное описание булевых функций....................................... 14

1.3.2 Аналитическое описание булевых функций............................... 16

1.3.3 Числовая форма представления булевых функций................... 18

1.3.4 Графическая форма представления булевых функций............. 18

1.3.5 Геометрическое представление булевых функций..................... 19

1.4 Минимизация функций алгебры логики.............................................. 24

1.4.1 Минимизация с помощью минимизирующих карт................... 24

1.4.2 Минимизация функций алгебры логики по методу Квайна.... 25

1.4.3 минимизация функций алгебры логики.................................... 32

по методу Квайна - Мак-Класки............................................................ 32

1.5 Элементная база для построения комбинационных схем............... 36

1.5.1 Логические элементы И, ИЛИ, НЕ............................................... 37

1.5.2 Примеры технической реализации булевых функций.............. 42

1.5.3 Программируемые логические матрицы (ПЛМ)....................... 44

Глава 2.............................................................................................................. 53

СИНТЕЗ ЦИФРОВЫХ АВТОМАТОВ....................................................... 53

2.1 Определение абстрактного цифрового автомата........................... 53

2.2 Методы описания цифровых автоматов............................................ 57

2.3 Синхронные и асинхронные цифровые автоматы........................... 61

2.4 Связь между математическими моделями......................................... 62

цифровых автоматов Мили и Мура......................................................... 62

2.5 Минимизация абстрактных цифровых автоматов.......................... 72

2.5.1 Минимизация абстрактного автомата Мили............................ 72

2.5.2 Минимизация абстрактного автомата Мура.............................. 81

2.6 Структурный синтез автоматов.......................................................... 86

2.6.1 Элементарные автоматы памяти................................................. 86

2.6.2 Синхронизация в цифровых автоматах..................................... 92

2.7 Структурный синтез цифровых автоматов по таблицам............... 96

2.8 Структурный синтез цифрового автомата по графу.................... 109

Глава 3............................................................................................................ 114

МИКРОПРОГРАММНЫЕ АВТОМАТЫ................................................. 114

3.1 Декомпозиция устройств обработки цифровой информации....... 114

3.2 Управляющие автоматы........................................................................ 117

3.3 Принцип действия управляющего автомата с хранимой в памяти логикой и микропрограммное управление.............................................................. 120

3.3.1 Горизонтальное микропрограммирование.............................. 124

3.3.2 Вертикальное микропрограммирование................................. 125

3.3.3 Смешанное микропрограммирование...................................... 126

3.4 Управляющие автоматы с «жёсткой логикой»............................... 128

3.5 Граф - схемы микропрограммных автоматов................................ 130

3.6 Синтез микропрограммных автоматов по граф - схеме алгоритма 137

3.6.1 Синтез микропрограммного автомата Мили........................... 137

3.6.2 Синтез микропрограммного автомата Мура............................... 142

3.6.3 Минимизация микропрограммных автоматов........................ 147

Заключение.................................................................................................... 148

ЛИТЕРАТУРА............................................................................................... 149

ВВЕДЕНИЕ

 

В курсе «Цифровая схемотехника» рассматриваются теоретические основы построения цифровых автоматов как преобразователей двоичных цифровых сигналов. Все системы обработки цифровой информации (в том числе и цифровые вычислительные машины - ЭВМ) могут в общем виде представлены как кодопреобразователи (рис. 1) .

 

 

Особенностью цифрового автомата является зависимость оператора преобразования А от предыдущих состояний кодопреобразователя, то есть наличие памяти у цифрового автомата. В частном случае отсутствия памяти у цифрового автомата, он является логической схемой. Таким образом, предметами исследования в теории цифровых автоматов являются как собственно цифровые автоматы (системы с памятью), так и автоматы без памяти или логические схемы.

Наиболее разработана теория цифровых автоматов применительно к канонической структуре цифрового автомата, представленной на рис.2. Для дальнейшего рассмотрения используется только эта структура цифрового автомата.

 

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

 

Глава 1

ЛОГИЧЕСКИЕ ОСНОВЫ ЦИФРОВЫХ АВТОМАТОВ

Основные понятия алгебры логики

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

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

В алгебре логики применительно к описанию цифровых автоматов, работающих в двоичном представлении кодов (или цифровой информации) основными понятиями являются логическая (булева) переменная и логическая функция (функция алгебры логики - ФАЛ).

Логическая (булева) переменная - такая величина x, которая может принимать только два значения : x = {0,1}.

Логическая функция (функция алгебры логики - ФАЛ) - функция многих аргументов f(xn-1, xn-2,, ..., x0), принимающая значения равные нулю или единице на наборах логических переменных xn-1, xn-2,, ..., x0.

В дальнейшем в формальных описаниях наборов переменных и логических функций сами наборы переменных интерпретируются как двоичные коды (числа). В двоичных кодах расположение логических переменных упорядочено в порядке уменьшения индекса слева направо и каждая логическая переменная имеет вес в зависимости от позиции в коде, увеличивающийся справа налево. Вес каждой i - той логической переменной, являющейся значением разряда двоичного числа равен 2i (i = 0, ... , n-1).

Для n - разрядного кода общее количество уникальных наборов переменных

N = 2n; (1)

Максимальное числовое значение двоичного кода равно

Aмакс = 2n-1; (2)

Значения всех логических функций от одной переменной представлены в таблице 1.Таблица 1

 

x f0(x) f1(x) f2(x) f3(x)

 

Функция f0(x) называется константой нуля, а функция f3(x) - константой единицы. Функция f1(x), повторяющая значения логической переменной, -тождественная функция (f1(x) º x), а функция f2(x), принимающая значения, обратные значениям переменной x, - логическое отрицание или инверсия (НЕ) (f2(x) = ).

Значения всех логических функций от двух переменных представлены в таблице 2. Для функции двух переменных, согласно ф.(1), существует четыре уникальных набора переменных. Функции отличаются друг от друга набором значений 0 и 1 в четырех разрядах кода значений функции. Общее количество функций на n - местном или n - разрядном наборе переменных равно

; (3)

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

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

Аналитически это свойство описывается следующей формулой:

 

f1 (xn-1, xn-2,, ..., x0) = f2 (xn-1, xn-2,, ..., x0); (4)

 

Обе функции в ф.(4) могут иметь разные формы аналитической записи, но практически наиболее выгодной будет самая простая форма записи.

 

Система булевых функций W называется функционально полной, если для любой булевой функции n - переменных f(xn-1, xn-2,, ..., x0) может быть построена равносильная ей функция комбинированием булевых переменных xn-1, xn-2,, ..., x0 и функций системы W, взятых в любом конечном количестве экземпляров каждая. Такая система булевых функций (W) называется базисом.

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

Базисом является система функций И ( конъюнкция), ИЛИ ( дизъюнкция), НЕ ( инверсия), свойства которых были впервые изучены Дж. Булем.

Базисами являются системы:

- И,НЕ;

- ИЛИ,НЕ;

- функция Шеффера И-НЕ;

- функция Пирса ИЛИ-НЕ.

Базис является минимальным, если удаление из него хотя бы одной функции превращает систему ФАЛ в неполную. Базис И, ИЛИ, НЕ - избыточный.

 

Базис И, ИЛИ, НЕ. Свойства элементарных функций алгебры логики

Пусть x - некоторая логическая переменная. Тогда: 1. , что означает возможность исключения из логического выражения всех членов,… 2. - правила подобных преобразований, которые позволяют сокращать длину логических выражений;

Способы описания булевых функций

 

Известно несколько способов описания булевых функций и выбор конкретного для практического применения определяется в соответствии с условиями решаемой задачи. Теория ФАЛ позволяет получить немедленный практический результат в виде принципиальных схем, ориентированных на заданную элементную базу (серию интегральных схем и типы логических элементов) и именно это определяет условия применения того или иного описания ФАЛ и последующие действия по их упрощению с целью получения

экономичной реализации в виде конструкции для установки в радиоэлектронную аппаратуру.

 

Табличное описание булевых функций

Вследствие конечности множества наборов заданного количества логических переменных, простейшим и самым естественным способом описания ФАЛ является… Одна ФАЛ описывается одной таблицей, но для функций одинакового количества… Для примера выбраны функции (система функций):

Аналитическое описание булевых функций

; (15) где: ,если соответствующий разряд кода равен 0; ,если соответствующий разряд… Конституента 0 может быть описана в виде элементарной дизъюнкции переменных:

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

 

Используя представление наборов переменных как числовых двоичных или восьмеричных кодов, запишем и минтермы функции F (таблица 3) как числа:

(21)

В числовой СДНФ форме ФАЛ имеет самую компактную запись и позволяет при необходимости перейти к любому другому описанию этой функции.

 

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

 

График функция F, приведенной в таблице 3, представлен на рис.3.

График конституенты 1 F12 (таблица 3) представлен на рис.4.

График конституенты 0 Ф14 (таблица 3) представлен на рис.5.

Из графического представления конституент непосредственно следуют описания ФАЛ в СДНФ и СКНФ (фф(19) и (20)).

 

Геометрическое представление булевых функций

В геометрическом представлении ФАЛ значения входных переменных n - местного набора интерпретируются как координаты в n - мерной декартовой системе…

Минимизация функций алгебры логики

Минимизация с помощью минимизирующих карт

Как было отмечено выше, одним из способов представления ФАЛ от небольшого числа переменных (обычно не больше 5) являются диаграммы Карно или Вейча,… Пример диаграммы Вейча функции пяти переменных представлен на рис.9. По этим… F=Ú Ú . (24)

Минимизация функций алгебры логики по методу Квайна

При минимизации по методу Квайна в базисе И, ИЛИ, НЕ исходная ФАЛ задаётся в СДНФ. Целью минимизации является нахождение всех первичных импликант и… Импликанта функции - некоторая логическая функция, обращаемая в нуль при… Поэтому любой конъюнктивный терм, входящий в состав СДНФ, или группа термов, соединённых знаками дизъюнкции являются…

Минимизация функций алгебры логики

По методу Квайна - Мак-Класки

Недостаток метода Квайна - необходимость исчерпывающего попарного сравнения или сопоставления всех минтермов на этапе нахождения первичных… Числовое представление ФАЛ позволяет упростить самый трудоёмкий этап 1. Все… Минтермы, подлежащие склеиванию, различаются только по одной переменной, а их коды - только в одном разряде. По этой…

Элементная база для построения комбинационных схем

 

Для технической реализации Функций Алгебры Логики, то есть для построения устройства, входные и выходные сигналы которого связаны между собой такой же функциональной зависимостью, как и переменные в ФАЛ с соответствующими выходными значениями, применяются электронные (иногда и неэлектронные - оптические, пневматические, гидравлические, механические) узлы - логические элементы. Обычно логические элементы соответствуют простейшим логическим операциям - конъюнкции (И), дизъюнкции (ИЛИ), инверсии (НЕ), сложению по модулю 2 (исключающее ИЛИ) и другим.

 

Логические элементы И, ИЛИ, НЕ

Логические элементы И и И-НЕ

Схема логического элемента И, построенного на полупроводниковых диодах и резисторе, приведена на рис.10а).  

Логические элементы ИЛИ, ИЛИ-НЕ

Схема логического элемента ИЛИ, построенного на полупроводниковых диодах и резисторе, приведена на рис.12а). Рис.12. Схема логического элемента ИЛИ

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

Функция ИСКЛЮЧАЮЩЕЕ-ИЛИ

(Сложение по модулю 2)

ФАЛ сложение по mod2 описывается уравнением:

Таблица истинности этой ФАЛ приведена на рис.15б). Эта функция используется для описания работы арифметико-логических устройств (АЛУ) процессоров и имеет отдельное применение как управляемый инвертор. Из таблицы истинности видно, что при фиксированном значении одной переменной, например, при x1 =0, выходная переменная y повторяет значения входной переменной x2 , а при x1 =1 выходная переменная y имеет инверсные значения переменной x2 . Таким образом, изменяя значения одной переменной, мы изменяем свойства логического элемента как технического устройства.

Рис.15. Схемная реализация функции ИСКЛЮЧАЮЩЕЕ-ИЛИ

 

Минимизированная функция алгебры логики ф.(27)

(Дешифратор второго рода)

ФАЛ, имеющая значения, определённые на нескольких наборах входных переменных этим отличается от дешифраторов, имеющих выходные значения, определённые только на одном наборе входных переменных. Поэтому она иногда называется дешифратором второго рода.

Минимизированная ФАЛ, рассмотренная выше, записана в аналитической форме:

F =

По этой формуле тотчас же можно изобразить принципиальную схему устройства, реализующего эту ФАЛ (рис.16).

Рис.16. Принципиальная схема физической реализации ФАЛ

 

Программируемые логические матрицы (ПЛМ)

Программируемая логическая матрица [2] представляет собой функциональный блок, созданный на базе интегральной полупроводниковой технологии и… ПЛМ первого типа строятся по двухуровневой структуре рис.17а). Условное обозначение ПЛМ с указанием параметров s, t и q приведено на рис.17б).

Примеры ПЛМ

Промышленностью выпускаются микросхемы ПЛМ 556РТ1 и 556РТ2, отличающиеся параметрами выходных программируемых усилителей. Микросхема 556РТ1 имеет выход с открытым коллектором, 556РТ2 - с тремя состояниями. Условные обозначения микросхем приведены на рис.18.

 

Рис.18. Условные обозначения ПЛМ

 

Логическая схема ПЛМ приведена на рис.19 [3].

Рис.19. Логическая схема ПЛМ

 

Микросхемы реализуют восемь функций от 16 входных переменных. При этом логические функции представляются в дизъюнктивной нормальной форме и общее число конъюнкций для всех функций не должно превышать 48. Микросхемы имеют инверсный вход разрешения выборки кристалла CE и линию разрешения программирования FE.

Логическая схема ПЛМ содержит два уровня программируемой логики.

Первый логический уровень включает матрицу из 48 схем И (конъюнкторов), организующую логические произведения (конъюнкции) Pi от входных переменных Аm и их инверсий . Инвертирование логических переменных Am осуществляется входными буферными усилителями.

В исходном состоянии все плавкие связи сохранены (aim==1, i={0,47} m={0,15}), что обеспечивает нулевое значений всех конъюнкций. С помощью выплавляемых связей aim и каждый i-конънктор может быть соединён либо с входной переменной Am либо с её инверсией . Удаление перемычек (aim==0) устанавливает независимость конъюнкции Pi от переменной Am. Не допускается в рабочем i-конъюнкторе ПЛМ оставлять одновременно обе парные перемычки (aim==1) для неиспользуемого входа Am, так как это влечёт за собой тождественно нулевое значение Pi . Все перемычки резервных схем И, как правило оставляют целыми.

Второй логический уровень образует матрица из восьми 48-входовых схем ИЛИ (дизъюнкторов), по одной на каждый выход ПЛМ. Плавкие перемычки bji позволяют организовать выборочную дизъюнкцию конъюнкций Pi . В исходном состоянии, когда все перемычки целы (bji=1, j={0,7}, i={0,47}) и Pi=0, все дизъюнкции Sj =0. В рабочей ПЛМ допускается оставлять перемычки bji для каждого неиспользуемого (резервного) i-конъюнктора, если его выход равен нулю. Эта связь может в дальнейшем потребоваться при редактировании рабочей ПЛМ, так же как и все другие резервные связи микросхемы.

На выходах схем ИЛИ находится слой программируемых инверторов, построенный на схемах двухвходовых логических элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, и ряд буферных элементов, открываемых сигналом CE. Удалением перемычек gj можно выборочно изменить значение уровня выходного сигнала. В исходном состоянии gj =1 и при выбранной схеме (CE=0), на всех выходах считывается нуль.

 

Процедуры программирования ПЛМ

В процессе эксплуатации ПЛМ могут возникнуть следующие задачи: - начальное программирование «чистой» ПЛМ; - повторное программирование (редактирование) ПЛМ.

Глава 2

СИНТЕЗ ЦИФРОВЫХ АВТОМАТОВ

Определение абстрактного цифрового автомата

С помощью импульсов синхронизации исключается возможность некорректной работы цифрового автомата во время протекания переходных процессов в…  

Методы описания цифровых автоматов

Чтобы задать цифровой автомат S, необходимо описать все элементы множества S = { A, X ,Y, d, l, a1}, то есть входной и выходной алфавиты и алфавит… Пример общего описания автоматов Мили таблицами переходов и выходов дан в…  

Синхронные и асинхронные цифровые автоматы

Автомат S называется асинхронным, если каждое его состояние as ÎA - устойчиво. Автомат S называется синхронным, если он не является… Созданные для практических применений цифровые автоматы всегда являются… Таким образом, оказывается, что техническая терминология противоречит математической терминологии, так как, согласно…

Связь между математическими моделями

Цифровых автоматов Мили и Мура

На вход этого автомата, установленного в начальное состояние a1, поступает шестибуквенное (шеститактное) слово x=z1z1z2z1z2z2. Проследив по таблицам переходов и выходов или непосредственно по графу…

Минимизация абстрактных цифровых автоматов

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

Два полностью определённых автомата называются эквивалентными, если они индуцируют (производят) одно и то же отображение множества входных слов во множество выходных слов.

Частичный цифровой автомат индуцирует лишь частичное отображение множества входных с лов в выходные слова.

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

Полностью определённый автомат является частным случаем частичного автомата.

 

Минимизация абстрактного автомата Мили

Для табличного описания процедура минимизации цифровых автоматов алгоритмизирована и выполняется в несколько шагов.   Шаг 1 Распространение неопределённости таблицы выходов на таблицу переходов. Если для некоторой пары (am, zf) выходной…

Минимизация абстрактного автомата Мура

  Шаг 1 Распространение неопределённости выходов на таблицу переходов. Если в…  

Структурный синтез автоматов

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

- элементарные автоматы памяти (запоминающие элементы);

- элементарные автоматы без памяти (элементарные комбинационные схемы или логические элементы).

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

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

 

Элементарные автоматы памяти

Комбинационная схема с обратными связями, имеющая два устойчивых состояния и предназначенная для хранения одного бита информации, называется… Триггер типа RS. Название триггера происходит от аббревиатур двух английских…  

Синхронизация в цифровых автоматах

Смена состояний в синхронизированных автоматах происходит в определённые моменты времени, задаваемые по цепям синхронизации внешним тактовым… Схема цифрового автомата, построенная из элементарных автоматов является… аs(t+1)=d(am(t), zf(t)),

Структурный синтез цифровых автоматов по таблицам

Если автомат имеет М состояний, то для двоичного структурного алфавита количество триггеров в блоке памяти этого автомата

n=]log2M[ ,

где ]...[ - ближайшее большее целое число.

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

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

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

Кодированные таблицы переходов и выходов изображаются в наиболее удобном расположении, либо поперёк страницы, либо вдоль в том случае, если размерность таблицы велика.

Рассмотрим пример синтеза цифрового автомата Мили S18, заданного таблицей 39 переходов и таблицей 40 выходов. Структурный алфавит для выходных сигналов и состояний - двоичный. Для кодирования трёх входных и трёх выходных сигналов двоичными кодами достаточно двухразрядного кода, а три состояния можно реализовать двумя триггерами. Таким образом, структурный автомат будет иметь две входных и две выходных линии, а память его будет состоять из двух триггеров.

 

Очевидно, что при кодировании переходов и выходов можно придерживаться двух принципов описания булевых функций. Если желательно получить табличное описание функций выходов с наименьшим количеством единичных значений, то для кодирования часто встречающихся в таблице выходов сигналов следует использовать коды с максимально возможным количеством нулей в коде, а для кодирования следующих по количеству ссылок в таблице выходов сигналов использовать коды с увеличивающимся количеством единиц в кодовых комбинациях. Для кодирования состояний блока памяти на D триггерах также можно использовать этот принцип кодирования, поскольку таблица возбуждений для них совпадает с таблицей переходов. Рекомендовать этот принцип для всеобщего применения при синтезе автоматов нельзя, так как при минимизации булевых функций возможно получение более простых результирующих форм представления функций, имеющих более сложную запись в СДНФ. Этот принцип можно использовать только в том случае, если ФАЛ выходов и ФАЛ возбуждений для D триггеров не подлежат минимизации, поскольку реализуются на мультиплексорах, дешифраторах или постоянных запоминающих устройствах.

Второй принцип кодирования соответствует противоположному подходу и ориентирован на возможность получения значительных упрощений ФАЛ в результате минимизации. Для кодирования выходных сигналов с максимальным количеством ссылок в таблице выходов используется код с максимальным количеством единиц, а для кодирования следующих по количеству ссылок в таблице выходных сигналов использовать коды с уменьшающимся количеством единиц в кодовых комбинациях. Этот принцип также без оговорок применим для кодирования состояний блока памяти на D триггерах для случая применения элементной базы, требующей минимизации для своей реализации. Минимальный по материальным затратам вариант кодирования выбирается из конечных результатов при использовании всевозможных вариантов кодирования.

Для второго принципа кодирования по изложенной выше методике построим кодированные таблицы переходов, выходов и возбуждений для JK триггера с использованием матрицы переходов на рис.40в). Кодирование входных, выходных сигналов и состояний автомата выполним следующим образом:

Рис.48 Таблицы кодирования входных сигналов, выходных сигналов

и состояний (по второму варианту)

 

В таблице выходов выходной сигнал w1 встречается 4 раза, выходной сигнал w3 - 3 раза, выходной сигнал w2 - 2 раза. В таблице переходов состояние a1 встречается 6 раз, состояние a3 - 2 раза, состояние a2 - 1 раз. В соответствии с количеством этих ссылок заполнены таблицы кодирования на рис.48.

Запрещённые наборы переменных x1x0Q1Q0

1100; 1101; 1110; 1111; 0000; 0100; 1000.

Где 11§§ - запрещённый код входных сигналов,

§§00 - запрещённый код состояний.

Рис.49 Кодированные таблицы переходов, выходов и возбуждений блока памяти на JK триггерах

 

Выполним конкатенацию кодов входных сигналов и кодов состояний по порядку следования переменных x1x0Q1Q0 и заполним таблицу истинности для функций выхода и возбуждений. В таблице на запрещённых наборах входных сигналов и состояний значения функций не определены и обозначены символом красного цвета §к .

Рис.50 Таблица истинности булевых функций входной и выходной схем цифрового автомата Мили S18

Рис.51 Минимизация функций выходов

Рис.52 Минимизация функций возбуждения

Минимизированные функции выходов в ДНФ:

Минимизированные функции возбуждений в ДНФ:

Для первого принципа кодирования по изложенной выше методике построим кодированные таблицы переходов, выходов и возбуждений для JK триггера с использованием матрицы переходов на рис.40в). Кодирование входных, выходных сигналов и состояний автомата выполним следующим образом:

 

Запрещённые коды x1x0Q1Q0

1100; 1101; 1110; 1111; 0011; 0111; 1011.

Где 11§§ - запрещённый код входных сигналов,

§§11 - запрещённый код состояний

Рис.53 Таблицы кодирования входных сигналов, выходных сигналов

и состояний (по первому варианту)

 

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

Рис.54 Кодированные таблицы переходов, выходов и возбуждений

Рис. 55 Минимизация функций выхода

Рис.56 Минимизаций функций возбуждения JK триггеров блока памяти

 

Сопоставим результаты синтеза комбинационных схем цифрового автомата по двум вариантам кодирования выходов и состояний (формулы А и Б). Рассмотрение минимизированных функций выходов и возбуждений не позволяет сделать вывод о преимуществе какого-то из способов кодирования. Очевидно, что для получения оптимального варианта кодирования нужно сопоставить результаты минимизации комбинационных схем при использовании всевозможных вариантов кодирования.

 

Минимизированные функции выходов в ДНФ:

Минимизированные функции возбуждений в ДНФ:

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

В формулах А и Б функции возбуждения JK триггеров блока памяти не содержат дизъюнкций, а количество переменных в конъюнкции не больше трёх. Для блока памяти следует использовать JK триггеры с встроенной логикой (трёхвходовые конъюнкторы в триггерах типа 155ТВ1). Такие схемы дают большую экономию и повышенную надёжность. Функция К0 «константа 1» задаётся подключением соответствующего входа через резистор сопротивлением 1 кОм к источнику питания схемы (для ТТЛ схем это напряжение равно +5В). Для соединения элементов схемы между собой использован «жгут». Соединены между собой проводники, имеющие одинаковую нумерацию входов в «жгут» и выходов из «жгута».

Рис.57 Принципиальная схема автомата Мили S18

 

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

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

Второй способ. Все триггеры, предназначенные для применения в составе блоков памяти цифровых автоматов, имеют отдельные несинхронизированные входы сброса или установки. Для всех запрещённых кодов входных сигналов и состояний выполняется дешифрирование и объединение выходных сигналов дешифраторов на входы сброса или установки триггеров в какое-то состояние с разрешённой кодировкой (обычно начальное). Таким образом синтезируется отдельная специальная система сброса и начальной установки цифрового автомата.

В обоих случаях усложняется принципиальная схема цифрового автомата. Иногда проектировщики ограничиваются упрощенной схемой начального сброса цифрового автомата при включении питающего напряжения. Для надёжной работы цифрового автомата такой схемы недостаточно.

 

Структурный синтез цифрового автомата по графу

Табличный и графический способы задания автоматов эквивалентны, поэтому граф автомата содержит всю необходимую информацию о функциях выходов и… Рис.58 Различные виды разметки графа автомата Мили S18

Глава 3

МИКРОПРОГРАММНЫЕ АВТОМАТЫ

Декомпозиция устройств обработки цифровой информации

В любом устройстве или системе обработки цифровой информации можно выделить два существенно различающихся блока (рис.63): - операционный блок (или операционный автомат); - управляющий блок (или управляющий автомат).

Управляющие автоматы

Интервал времени, отводимый на выполнение микрооперации, называется рабочим тактом или просто тактом устройства или системы обработки цифровой… Для реализации команды, операции или процедуры (микропрограммы) необходимо на… Часть устройства или системы обработки цифровой информации, предназначенная для выработки последовательностей…

Принцип действия управляющего автомата с хранимой в памяти логикой и микропрограммное управление

Хранимая в памяти микропрограмма должна содержать информацию о функциях переходов и выходов управляющего микропрограммного автомата. Рассматривая… Аргументами функций переходов и выходов автомата являются входные переменные… Воздействие управляющих сигналов W(t) на операционный блок синхронизируется сигналом CLK=1, обеспечивающим выдачу W(t)…

Горизонтальное микропрограммирование

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

Вертикальное микропрограммирование

При вертикальном микропрограммировании микрооперация определяется не состоянием одного из бит микрокоманды, а двоичным кодом, содержащимся в… Количество разрядов операционной части микрокоманды: nоч=]log2(m+1)[.

Смешанное микропрограммирование

При смешанном микропрограммировании множество микроопераций V разбивается на k непересекающихся подмножеств (или полей)

.

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

 

Вертикально - горизонтальное микропрограммирование

 

Всё множество микроопераций V разделяется на множество k подмножеств, в каждом из которых объединяют микрооперации, наиболее часто встречающиеся вместе в одном такте. Подмножества стремятся по возможности сделать равномощными, но если это не удаётся, то формат микрокоманды рассчитывается на множество максимальной мощности. Операционная часть микрокоманды (рис.65) состоит из двух частей (полей).

В первом поле, длина которого равна max |VL|, применён горизонтальный способ микропрограммирования, то есть каждый бит соответствует определённой микрооперации из подмножества VL, а другое поле, имеющее длину m=]log2k[, указывает, к какому из k подмножеств принадлежат микрооперации в первом поле микрокоманды.

 

Горизонтально - вертикальное микропрограммирование

В этом случае подмножества VL представляются горизонтальным способом , а микрооперации внутри каждого из подмножеств - вертикальным способом… Длина операционной части микрокоманды

Граф - схемы микропрограммных автоматов

Для описания микропрограмм необходимо знать и задавать последовательности микрокоманд и функции перехода, определяющие порядок выполнения… Граф-схема алгоритма (ГСА) - ориентированный связный граф, содержащий одну…

Синтез микропрограммных автоматов по граф - схеме алгоритма

Синтез микропрограммного автомата Мили

Конечный автомат, реализующий микропрограмму работы дискретного устройства, называется микропрограммным автоматом. Синтез микропрограммного автомата Мили по граф - схеме алгоритма… - получение отмеченной ГСА;

Синтез микропрограммного автомата Мура

- получение отмеченной ГСА; - построение графа автомата. На первом из этих этапов начальная, конечная и операторные вершины отмечаются символами a1 , ... , aM по следующим…

Минимизация микропрограммных автоматов

Изложенный ранее метод минимизации абстрактных автоматов применяется и для минимизации полностью определённых микропрограммных автоматов. Если два состояния автоматы Мили совместимы, то под действием одинаковых… Для минимизации микропрограммного автомата Мура необходимо предварительно найти разбиение состояний на классы 0 -…

Заключение

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

 

 

ЛИТЕРАТУРА

1. Савельев А.Я. Прикладная теория цифровых автоматов. -М.: Высшая школа, 1987.

2. Баранов С.И., Скляров В.А. Цифровые устройства на программируемых БИС с матричной структурой. -М.: Радио и Связь, 1986.

3. Щелкунов Н.Н., Дианов А.П. Процедуры программирования логических матриц, - Микропроцессорные средства и системы, 1986, №2.

4. Иванов В.И. Синтез цифровых автоматов для систем связи и управления.

Челябинск, ЧПИ, 1980.

5. Баранов С.И. Синтез микропрограммных автоматов. - Л.: Энергия, 1979.

 

– Конец работы –

Используемые теги: Теория, цифровых, автоматов0.068

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: ТЕОРИЯ ЦИФРОВЫХ АВТОМАТОВ

Что будем делать с полученным материалом:

Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Еще рефераты, курсовые, дипломные работы на эту тему:

Методичка для курсового проектирования по ПТЦА (прикладная теория цифровых автоматов)
Впредь на схемах УА не будем показывать цепей установки на- чальных значений. Для реализации в самом общем случае микропрограмм произ- вольной… Реализация именно этого момента яв- ляется основным предметом дальнейшего… Будем изучать работу управляющих автоматов различной структуры, демонстрирующие основные применяемые варианты ад-…

Прикладная теория цифровых автоматов
Заздалег дь пом тимооператорн? вершини в початкових ГСА, керуючись сл?дуючимиправилами 1 однаков вершини Yiв р зних ГСА в дм ча мооднаковими м тками… Формули переходу длявершин А3, А4, А5, А9, А10,А11, А13, А14, А15, А16,А18,… Для х усунення скориста мося сл?дуючимправилом додавання виразу PqАn не зм нить формулу, якщо наб р Pq невикористову…

КОМПЬЮТЕРНАЯ АРИФМЕТИКА. ПРИКЛАДНАЯ ТЕОРИЯ ЦИФРОВЫХ АВТОМАТОВ
запорожский национальный технический университет... ПРИКЛАДНАЯ ТЕОРИЯ ЦИФРОВЫХ АВТОМАТОВ...

ТЕОРИЯ ЭКСПЕРИМЕНТА В ОМД КОНСПЕКТ ЛЕКЦИЙ ПО КУРСУ «ТЕОРИЯ ЭКСПЕРИМЕНТА»
ДОНБАССКИЙ государственный... технический университет... В М ДАНЬКО...

Теория бухгалтерского учета: конспект лекций ЛЕКЦИЯ № 1. Теория бухгалтерского учета, его сущность и значение в системе управления
ЛЕКЦИЯ Теория бухгалтерского учета его сущность и значение в системе... ЛЕКЦИЯ Предмет метод и принципы бухгалтерского... ЛЕКЦИЯ Учетная политика организации Учредители и...

Встроенный контроль и диагностика цифровых устройств. Методы повышения контролепригодности цифровых устройств
Простейшее решение повышения качества контроля – это вывод некоторых внутренних точек изделия на внешний разъем. Однако число свободных контактов на… В результате такого сопоставления вырабатывается информация о правильном… С целью уменьшения объема дополнительной контрольной аппаратуры используют более простые контрольные устройства с…

ДОКЛАД по дисциплине Теория игр и исследование операций На тему: Теория игр, графический метод в теории игр
МИНОБРНАУКИ РОССИИ... ФГБОУ ВПО ВОСТОЧНО СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕХНОЛОГИЙИ УПРАВЛЕНИЯ...

Эволюционная теория Дарвина и теория креационизма
На сайте allrefs.net читайте: " Эволюционная теория Дарвина и теория креационизма"

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

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

0.037
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам