Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
НГТУ каф ВСТ
Теория автоматов
П.И. Уваров
2013
Оглавление
Литература:
К.Фрике. Вводный курс цифровой электроники. М.: Техносфера, 2003 – 432с.
Угрюмов Е.П. Цифровая схемотехника. – СПб.: БХВ-Петербург, 2004.-528 с.: ил.
Теория автоматов / Ю.Г. Карпов –СПб.: Питер, 2002. – 224 с.: ил.
Организация ЭВМ. 5-у изд. / К. Хамахер, З. Вранешич, С. Заки. – СПб.: Питер; Киев: Издательская группа BHV, 2003.– 848 с.: ил. – (Серия «Классика computer science»)
Схемотехника ЭВМ – это свод правил и методик, позволяющий эффективно проектировать цифровые схемы и устройства любой сложности.
В основе построения любой цифровой (дискретной, бинарной...) схемы лежит умение:
Формально первые три пункта можно объединить с четвёртым, но в действительности это невозможно из-за громадной длины таблиц, описывающих работу блоков и элементов. Реальный синтез можно выполнить только для ЭБ. Этот синтез представляет собой основу построения схем и выполняется в соответствии со сводом правил. Изучение и систематизация этих правил синтеза выполняется в курсе «Теория автоматов».
В основе любой деятельности лежит преобразование и обработка информации. Информация имеет разнообразные представления и в общем преобразование (обработку) информации можно представить (рис.1.2.1) в виде существования:
Преобразователь Ф формирует по определённым правилам выходной поток В, базируясь на данных потока А, т.е. выполняет преобразование АВ.
Потоки А и В могут иметь произвольный вид, например, быть аналоговыми, частотными и т.д. Конечно, можно выполнять преобразования информационных потоков (ИП) именно в том виде, в котором они представлены, но при этом преобразования носят частный характер и не отличаются сложностью и разнообразием. Отсутствует возможность накопления информации, сложно реализовать временные зависимости, входные и выходные ИП могут иметь различную природу.
Для решения этих проблем необходим некоторый универсальный преобразователь ИП АВ, в качестве которого используются цифровые преобразователи информации. Эти преобразователи представляются в виде конечных автоматов (КА) и их место в общем преобразовании показано на рис.1.2.2. Здесь преобразователь информации Ф разбит на три блока:
КА в виду его цифровой (бинарной) природы обладает возможностями:
Отметим, что, если потоки А и В цифровые с аналогичными параметрами, то входной и выходной преобразователи могут отсутствовать.
Структура самого КА представлена на рис.1.2.3. В КА можно выделить два основных блока:
Основное назначение блока элементов памяти – хранение кода текущего состояния КА.
Блок логической схемы предназначен для:
Работа КА синхронизируется во времени серией синхросигналов, которые представляют собой последовательность синхронизирующих импульсов (СИ). При поступлении одного СИ происходит переход в новое состояние КА и вырабатывается одно слово выходного ИП.
Существуют асинхронные КА, но они сложно синтезируемы, неустойчиво работают и не получили широкого распространения.
Логические (комбинационные) схемы (ЛС или КС) – преобразователи бинарной информации, реализующие функциональное преобразование конечных множеств на базе теории двоичных булевых функций – булевой алгебре.
Функциональная схема преобразования ИП в ЛС представлена на рис.1.3.1. На этой схеме:
В данном случае множества элементов входной информации А и выходной информации В имеют цифровую природу. Эти множества состоят из элементов:
А – a0, a1, … , aj, … , aL;
B – b0, b1, … , bc, … , bV;
Элементы множеств А и В кодируются двоичными кодами:
aj = x0j, x1j, … , xij, … , xmj – элемент aj входного множества А, представленный в кодированном виде вектором бинарных переменных. Здесь xij – значение i-ой переменной при кодировке j-го входного состояния.
bj = y0j, y1j, … , ykj, … , ynj – элемент bi выходного множества B, представленный в кодированном виде вектором бинарных переменных. Здесь ykj – значение k-ой переменной при кодировке j-го выходного состояния.
Входные состояния однозначно преобразуются в выходные, т.е. каждому входному состоянию всегда соответствует одно и то же выходное состояние, поэтому индекс j указан одинаковый. Хотя в принципе выходных состояний может быть меньше, чем входных (нескольким входным будет соответствовать одно и то же выходное состояние). НО! Выходных состояний не может быть больше, чем входных.
Число двоичных векторов длины n равно 2n.
т.е. имея n переменных невозможно закодировать количество состояний, большее, чем 2n.
Обычно количество, как входных, так и выходных шин превышает минимально необходимое значение, т.е. длина входных/выходных векторов может быть избыточной.
Обратно, если количество состояний равно S, то
► Минимальная длина вектора, кодирующая S состояний равна
M = [log2S], ●
здесь – округление в большую сторону до ближайшего целого числа (см. таблицу рис.1.3.4).
Если длина входного вектора превышает минимальную, то в выходном векторе некоторые значения при кодировании устанавливаются неопределёнными.
Пусть m и n –длины двоичных векторов для кодирования состояний входных и выходных множеств А и В. Тогда кодирование – это построение отображения A{0,1}m, построение отображения {0,1}nB, а функциональное отображение F сопоставляет каждому вектору из {0,1}m определённый вектор из {0,1}n.
Пример.
Пусть входное множество имеет пять состояний A ={ a0, a1, a2, a3, a4}, а выходное множество имеет три состояния B={ b0, b1, b2}. Отображение F задаётся таблицей рис.1.3.5. В данном примере длина входного вектора не менее трёх, а выходного не менее двух.
Произвольно выберем функцию кодирования (рис.1.3.6 а) и декодирования (рис.1.3.6 б) отображение F строим в соответствии с таблицей отображения рис.1.3.5 (рис.1.3.6 в).
Проблема построения произвольного преобразователя F:{0,1}m{0,1}n довольно сложна. Для упрощения этой проблемы используют простой приём: вместо одной функции F:{0,1}m{0,1}n строится n одноразрядных по выходу функций fi:{0,1}m{0,1} так, чтобы реализация этих функций дала искомый преобразователь F. Структура ЛС с явно выделенными fi представлена на рис.1.3.2. Для удобства чтения схем используются шины, в которых объединяются некоторые соединения, а входы и выходы соединений в шину именуются. Шинная организация структуры ЛС показана на рис.1.3.3.
► Функции вида fi:{0,1}m{0,1}, сопоставляющие двоичным векторам одноразрядные двоичные значения, называются двоичными (или булевыми) функциями.●
Булевы функции определены на конечном множестве аргументов, каждый из которых принимает только два значения, 0 или 1. Булевы функции представляются таблицей, перечисляющей для каждого набора значений входных аргументов значение функции. Для булевых функций разработаны методики эффективной обработки. Представление таблиц примера через булевы функции показано на рис.1.3.7.
Выделенная часть таблицы (прямой шрифт) может быть реализована совокупностью ЛС (рис.1.3.8.а). Каждый блок ЛС реализует свою БФ (f0, f1). Выходы блоков ЛС представляют собой физическую реализацию булевых переменных и выражаются, как
, .
Выделенную часть таблицы рис.1.3.7 называют таблицей истинности (ТИ). Но с учётом того, что ЛС имеют выходами булевы переменные, таблицу истинности обычно представляют в виде, показанном на рис.1.3.8.б (но можно и как в 1.3.7).
В ТИ в строках указываются:
Если по тем или иным причинам состояние выходной булевой переменной в строке безразлично (т.е. может принимать значение как 0, так и 1), то для данной выходной переменной в строке проставляется прочерк.
Для сокращения размеров структурных схем допускается представление структуры рис.1.3.8.а в виде рис. 1.3.8.в. Просто надо помнить, что каждая выходная переменная реализуется своей БФ.
Длина ТИ определяется 4количеством входных переменных. Для n входных переменных длина M таблицы составляет
M = 2n .
Максимальное количество ТИ длиной M от n переменных составляет
N = 2M = .
► Таблица истинности – алгоритм работы логической схемы.●
16 час.
Основной задачей теории булевых функций (БФ) является разработка систематических методов построения сложных функций из более простых. Булевых функций от заданного числа m двоичных переменных – конечное число. Изучим свойства булевых функций.
Рассмотрим все возможные БФ от одной переменной. Этих функций четыре:
Представляя эти функции в табличном виде, получим ТИ, представленные на рис. 1.4.1. С целью сокращения текста в одной таблице можно отражать несколько БФ от одного и того же сочетания переменных. Объединённая таблица истинности БФ от одной переменной представлена на рис.1.4.2.
Основные БФ от двух переменных представлены в объединённой ТИ рис.1.4.3. На рисунке приведены функции:
С нулевой по восьмую БФ являются основными все остальные функции можно выразить через их суперпозицию (т.е. различного рода их сочетания) в виде логического выражения (логической формулы).
►Логическое выражение – символьная формула, представляющая собой суперпозицию двоичных (булевых) функций.●
Например, логическая формула
или, перепишем это же выражение с другим обозначением операции
задаёт функцию от трёх переменных как суперпозицию функций от одной и двух переменных.
Логическое выражение даёт возможность построить соответствующий функциональный преобразователь, если имеются «базисные» преобразователи. Для реализации преобразователя F примера необходимо иметь элементы, реализующие отрицание, дизъюнкцию, конъюнкцию и сложение по модулю два. Синтаксическая структура формулы примера показана на рис. 1.4.4. Табличное представление суперпозиции функции F показано на рис 1.4.5.
Примечание. Реализацию БФ в виде ЛС на логических элементах (рассматривается в дальнейшем) следует начинать «сверху - вниз» от выхода к входам. Так на рис.1.4.4 сначала реализуется сумма по модулю два и т.д. На последний уровень подаются входные сигналы (входные переменные).
Для уменьшения числа скобок вводятся приоритеты операций:
С остальными функциями проблемы с приоритетами.
►Желаемый порядок выполнения операций можно установить скобками.●
При возникновении сомнений в порядке выполнения операций лучше всего в выражении использовать скобки.
Суперпозицией фиксированного набора функций можно представить любую БФ от любого количества переменных.
► Любая БФ может быть представлена как суперпозиция следующих наборов двоичных функций:
Каждый из этих наборов функций называется полным базисом. ●
►Функционально полный базис – множество двоичных функций, суперпозицией которых могут быть выражены любые БФ●
16+6=22 час.
Свойства БФ достаточно просты и легко проверяются с помощью таблиц истинности. Основные свойства БФ приведены в таблице на рис.1.5.1.
Проиллюстрируем некоторые свойства.
Свойство 3 – коммутативность представим в графическом виде на двух (правда, не двоичных) множествах на рис.1.5.2.
Двоичное множество имеет две ипостаси (рис.1.5.3):
Представим эти множества в виде заполнения некоторой области вписанной в границы прямоугольника:
БФ будут представлять собой для соответствующих текущих состояний переменных:
Проиллюстрируем операции с константами для БФ:
Можно подобным образом проиллюстрировать и другие свойства БФ, но для выражений это трудоёмко, т.к. следует рисовать множества для всех сочетаний входных переменных, поэтому следует использовать ТИ. Графическое отображение приведено только для лучшего понимания материала.
Свойство 12 – склеивание можно подтвердить выкладками:
.
Свойство 11 – законы поглощения:
Для закрепления материала самостоятельно составьте ТИ для выражений свойств БФ.
►Две БФ равны, если их значения совпадают на всех наборах аргументов.●
Определения.
►Терм БФ (конъюнкт) представляет собой конъюнкцию взятых с отрицаниями или без них двоичных переменных функции.●
►Дизъюнктивная нормальная форма (ДНФ) – представление БФ в виде дизъюнкции конъюнктов:
,
где Ki – терм БФ.●
►Совершенная дизъюнктивная нормальная форма (СДНФ) – ДНФ, каждый конъюнкт которой содержит в точности по одной двоичные переменные функции.●
►В СДНФ может быть представлена любая БФ за исключением тождественного нуля.●
►Представление БФ в СДНФ единственно.●
►Любая аналитическая запись БФ может быть преобразована в нормальную форму с использованием законов де Моргана и раскрытием скобок ●
Примеры.
Определения.
►Терм БФ (дизъюнкт) представляет собой дизъюнкцию взятых с отрицаниями или без них двоичных переменных функции.●
►Конъюнктивная нормальная форма (КНФ) – представление БФ в виде конъюнкции дизнъюнктов:
,
где Di – терм БФ.●
►Совершенная конъюнктивная нормальная форма (СКНФ) – КНФ, каждый дизъюнкт которой содержит в точности по одной двоичные переменные функции.●
►В СКНФ может быть представлена любая БФ за исключением тождественной единицы.●
►Представление БФ в СДНФ единственно.●
Примеры.
►Любая аналитическая запись БФ может быть преобразована в нормальную форму с использованием законов де Моргана и раскрытием скобок ●
22+9=31 час.
Для реализации двоичных функций необходимо адекватно представить дискретные (бинарные) значения с помощью физических величин (например: токов, напряжений). Распространено представление логических значений бинарных величин уровнями напряжений. Например:
Рассмотрим реализации БФ в виде релейных моделей рис.1.7.1. Здесь ЭМ – электромагнит реле, который при подаче на его вход высокого напряжения (единицы) вызывает замыкание ключа.
Элемент НЕ при подаче на его вход 1 вырабатывает на выходе 0, а при подаче нуля – 1.
Элемент 3ИЛИ-НЕ вырабатывает на выходе 1, если только на все его входы поступают нули. При подаче хотя бы одной единицы на его выходе выдаётся 0.
Элемент 3И-не вырабатывает на выходе 0, если на все его входы подаются единицы, иначе на выходе 1.
Принятые изображения этих элементов показаны на рис. 1.7.2. Внутри каждого элемента (обязательно!) проставляется вид БФ. Инверсия показывается кружочком.
Элементы БФ могут иметь разнообразный вид, быть составными, но принцип должен быть понятен.
В современных схемах нет механических деталей, и роль ключа выполняет электронный вентиль, принципиальная схема которого для серии ТТЛ показана на рис.1.7.3. Наибольшее распространение получили вентили, выполненные по канальным технологиям. В одном кристалле электронного устройства могут располагаться десятки миллионов вентилей.
31+3=34 час
СДНФ используются в основном для составления исходных БФ, но с точки зрения затрат по количеству вентилей эти формы не идеальны. Минимизация (упрощение) БФ производится на основании свойств БФ.
Рассмотрим в качестве иллюстрации сказанного пример БФ:
.
Реализация fСДНФ показана на рис.1.8.1.а.
Выполним минимизацию БФ
.
В результате склеивания минимизированная БФ не имеет ни одного логического элемента (!) и, соответственно, проще в реализации. Схема fmin представлена на рис.1.8.1.б.
Применение свойств БФ к их выражениям для минимизации довольно трудоёмко для функций имеющих несколько входных переменных. Распространена минимизация с использованием графического представление процесса минимизации. Для этого применяются диаграммы Вейча (ДВ) и карты Карно (КК), которые в принципе представляют собой одно и то же, но КК более формализованы и их использование позволяет избежать множества ошибок при минимизации.
При минимизации с помощью ДВ и КК скрытым образом используется такое свойство БФ как склеивание:
.
Исходными данными для ДВ и КК являются таблицы истинности, описывающие БФ.
Рассмотрим минимизацию с использованием ДВ.
ДВ представляет собой прямоугольную таблицу, количество клеток (M) которой зависит от количества входных переменных БФ (n) и равно:
.
Для n=1 минимизация тривиальна, поэтому рассмотрим минимизацию БФ, начиная с двух переменных.
На рис.1.8.2.а показан общий вид диаграммы Вейча, а на рис 1.8.2.б нумерованные поля диаграммы:
На рис. 1.8.в выделена область, соответствующая полям заполнения в которую вносятся соответствующие значения БФ из ТИ. Для того, чтобы найти клетку для внесения значения из ТИ следует определить положение значения БФ в области заполнения (рис.1.8.2.в). Для этого область заполнения разделена на области p, , q, , видимые на рис 1.8.2.г-ж. Так, следует проставить единицы в клетках области заполнения, если БФ принимает единичное значение для комбинаций входных переменных:
Рассмотрим заполнение диаграмм Вейча на примере некоторых БФ, заданных ТИ (рис.1.8.3) в соответствии с последовательностью действий:
Рассмотрим заполнение диаграммы Вейча для БФ f0:
Самостоятельно рассмотрите заполнение диаграмм Вейча для БФ f1-f5. БФ f6 диаграмму Вейча заполненную одними единицами.
Для минимизации необходимо выполнить накрытия единичных клеток диаграммы прямоугольниками, имеющими площадь, равную целой степени двух, т.е. для БФ от двух переменных можно накрывать одну, 2 или 4 клетки.
Одну и ту же клетку можно накрывать сколько угодно раз.
Необходимо стремиться, чтобы накрытия имели как можно большую площадь, так для БФ f6 будут накрыты все четыре клетки.
Минимизация БФ основывается на многократном применении свойства БФ – склеивании.
Так для функций примера f0, f3 и f6:
;
Подобные вычисления для диаграмм Вейча не делаются. Минимизация выполняется непосредственно при исследовании каждого накрытия в соответствии с последовательностью действий:
Рассмотрим БФ примеров рис. 1.8.3:
.
34+4=38 час
Диаграмма Вейча на три переменных имеет вид, показанный на рис. 1.8.4, на котором показаны:
На рисунке показано, левый и правый края диаграммы являются соседними, т.е. диаграмма представляет собой кольцо.
Заполнение диаграммы производится аналогично заполнению диаграммы Вейча от двух переменных:
Накрытие осуществляется минимальным количеством прямоугольников максимальной площади, равной целой степени двух.
Примеры минимизации БФ f0–f3 показаны на рис. 1.8.5.
38+2=40 час
Диаграммы Вейча для БФ от четырёх переменных аналогичным образом заполняются из ТИ БФ с использованием конституент единиц посредством установки единиц в, соответствующие пересечению областей, клетки поля заполнения. Диаграмма Вейча для БФ от четырёх переменных образно можно представить в виде тора, т.к. соседними являются клетки:
Минимизация БФ традиционно выполняется с использованием четырёхугольных накрытий, максимальной площади, равной целой степени двух. Импликанты, соответствующие накрытиям собираются через «ИЛИ».
Заполнение диаграмм тривиально, поэтому рассмотрим минимизацию БФ на примерах уже заполненных диаграмм (рис.1.8.6).
Сложность работы с диаграммами Вейча заключается в необходимости промежуточного формирования из кода строки ТИ конституенты, а затем определения клетки диаграммы, соответствующей пересечению областей. В этом отношении карты Карно более формализованы, в следствии чего, заполнение их выполняется значительно проще. Это позволяет избежать множества ошибок при определении клетки пересечения областей существования переменной из конституенты единицы. В остальном диаграммы Вейча и карты Карно практически совпадают.
В картах Карно области существования переменных представлены в кодированном виде. Соответствие карты Карно и диаграммы Вейча для четырёх переменных показано на рис.1.8.7. Здесь области действия значений переменных указаны скобками и приведены колированные значения областей:
Кодировка областей существования переменных выполняется в коде Грея, характеризующемся тем, что каждая соседняя пара кодов отличается инверсией только одного разряда.
На рис.1.8.7.б приведены эквиваленты клеток и конституент (в левом столбце даны шестнадцатиричные значения кодов клеток).
40+7=47 час
Заполняется карта Карно из ТИ БФ. При заполнении карты в ТИ берётся очередная строка и минуя преобразование в конституенту производится установка значения в соответствующую клетку карты.
Рассмотрим в качестве примера минимизацию БФ f0–f4. ТИ этих БФ приведена на рис.1.8.8.а, а минимизация показана на рис.1.8.8.б-е. Определение склеивания какой либо переменной в минимизированной БФ производится при анализе поведения этой переменной. Если при анализе обнаружено, что накрытая область проходит и через единичное и через нулевое значение переменной, то переменная в минимизированной БФ склеивается (исчезает).
Накрытия следует выполнять:
Карты Карно практически применимы для БФ, количество переменных которых не более шести. На рис.1.8.9. показаны карты Карно для различного количества входных переменных БФ. Для построения БФ от большего количества переменных следует либо использовать постоянные запоминающие устройства (ПЗУ), либо применять методики понижения порядка (уменьшения числа переменных) БФ.
На рис.1.8.9 под латинскими буквами подразумеваются единичные значения некоторых БФ и выполнена минимизация этих функций. Видно, что для БФ от пяти и шести переменных код Грея, записанный в рамках представляет собой зеркальное отражение.
Для контроля правильности минимизации следует использовать правило:
► Если площадь накрытия составляет N клеток то в минимизированной импликанте, относительно исходного количества переменных БФ, должно исчезнуть переменных●
Например, для БФ от 6 переменных при накрытии 8 клеток исчезнет 3 переменных, а останется 3, при накрытии 16 клеток исчезнет 4, а останется 2. Поэтому, если при накрытии 32-х клеток вы обнаружили, что какая-то переменная для этого накрытия не меняется, то выписываем её, а остальные нет смысла и проверять. Но, если накрыто 8 клеток, а импликанта содержит четыре переменных, то одна переменная явно пропущена (д.б. пять!).
При формировании накрытия для 5, или 6 переменных, если накрытия располагаются в нескольких квадрантах, то накрытие должно быть симметрично относительно квадрантов. Например, для БФ от пяти переменных при формировании накрытия в 8 клеток, располагаемого в двух квадрантах, в каждом квадранте должно располагаться по четыре клетки, а не 2 и 6.
47+3=50 час
При формировании ТИ БФ вследствие объективных причин может получиться так, сто в некоторых строках значение БФ будет не определено. Этих причин может быть множество и вы сами убедитесь в этом в дальнейшем.
Рассмотрим пример рис 1.8.10. Пусть входные воздействия на ЛС формируются с выхода другой входной ЛС (ВЛС) (рис.1.8.10.а), а зависимости БФ выхода ВЛС xi(p,q) имеют вид показанный на рис.1.8.10.б. Тогда реализация ВЛС имеет вид показанный на рис.1.8.10.в. ТИ, соответствующая заданным зависимостям показана на рис.1.8.10.г, на котором видно, что БФ ВЛС принимают только четыре значения. Вследствие этого ТИ ЛС, представленная на рис.1.8.10.д, имеет определёнными только четыре строки выделенные в колонках (x0, x1, x2). Значения (x0, x1, x2) в колонках, выделенных курсивом, не могут существовать в принципе, поэтому в этих строках выходы БФ (y0, y1) не определены и там проставлен прочерк. Предположим, что в выделенных колонках (y0, y1) принимают значения показанные в ТИ (рис.1.8.10.д).
► Неопределённые значения БФ при минимизации можно доопределять произвольным образом, как нулём, так и единицей с целю получения наиболее минимизированного выражения БФ.●
Доопределение выполняется непосредственно в карте Карно так, чтобы получить минимальное количество накрытий максимальной площади.
Накрытие с оптимальным доопределением показано на рис.1.8.10.е. Там же приведены минимизированные выражения БФ ЛС, которые имеют более простой вид, чем при доопределении всех неопределённых значений нулями.
►Элемент памяти (ЭП) – это устройство позволяющее сохранять своё значение в течение произвольного отрезка времени.●
►Простейший ЭП в цифровой технике – триггер.●
Существует множество разновидностей триггеров которые можно разбить на две основные группы:
В свою очередь синхронные триггера подразделяются на:
Триггера строятся наращиванием возможностей:
Асинхронные триггера изменяют своё состояние при определённом изменении информационных сигналов.
Для изменения состояния синхронных триггеров требуется не только изменение входных информационных сигналов, но и обязательное наличие специального активизирующего (синхронизирующего) работу триггера сигнала – синхроимпульса (СИ).
Однотактные триггера изменяют своё состояние при активном уровне СИ, фактически превращаясь при этом в асинхронные триггера.
Двухтактные изменяют своё состояние только при прохождении обоих фронтов СИ.
Структура триггера при сохранении его функциональных возможностей может быть различной. Рассматриваемые структуры выбраны только с целью пояснения различия между типами триггеров и пояснения их работы.
Основой любого триггера является RS-триггер. А уже на его базе путем добавления входной логики формируются все остальные типы триггеров (преобразование триггеров рассматривается в дальнейшем).
50+4=54 час
PAGE 19