Файл: Основы бортовых вычислительных машин.pdf

66
Цифровой автомат обладает полной системой переходов, если для любой пары его состояний
1
β
ψ
и
(
)
2 1
2 0
,
1
L
β
ψ
ψ
β β
≤
≥
−
найдет- ся хотя бы один входной сигнал X
α
, который переводит ЦА из со- стояния
1
β
ψ
в состояние
2
β
ψ
. При выполнении этого условия в каж- дом столбце таблицы переходов содержатся символы всех состояний
ЦА.
Таблица выходов (см. таблицу 2.2) строится аналогично таблице переходов, при этом в клетку, лежащую на пересечении столбца и строки, соответствующих
β
ψ
и
X
α
, записывается выходной сигнал
( )
( ),
( )
Y t
f
t X
t
β
α
ψ


=

 .
Цифровой автомат обладает полной системой выходов, если в каждом состоянии он формирует сигнал, отличающийся от выходного сигнала, соответствующего любому другому состоянию.
По содержимому таблиц переходов и выходов могут быть полу- чены аналитические выражения логических функций переходов и вы- ходов, соответственно.
2.1.2 Этапы синтеза схем автоматов
При синтезе схем автоматов выделяют этапы абстрактного син- теза, структурного синтеза, технического проектирования. Целью аб- страктного синтеза является задание автомата графом или таблицей переходов и минимизация числа состояний автомата. Задачей струк- турного синтеза является построение структурной схемы автомата из заданного набора комбинационных и запоминающих элементов.
Этапы абстрактного и структурного синтеза объединяют в один этап – этап логического проектирования, в результате которого схему автомата можно представить состоящей из двух частей – комбинаци- онной схемы и памяти в виде набора запоминающих элементов (ЗЭ).
В этой схеме можно выделить входные двоичные сигналы
{
}
0 1
1
,
,...,
n
X
x x
x
−
=
, выходные двоичные сигналы
{
}
0 1
1
,
,...,
m
Y
y
y
y
−
=
, двоичные сигналы состояния памяти
0 1
,...,
s
Q
Q
−
, двоичные сигналы возбуждения памяти, переключающие состояния элементарных авто- матов,
0 1
,...,
s
g
g
−
(рисунок 2.3).
На этапе технического проектирования разрабатываются функ- циональные, принципиальные и монтажные схемы, составляется тех-

67 ническая документация, выполняется электрический расчет, проверя- ется работоспособность автомата и т.д.
Рисунок 2.3
Для разработки функциональной схемы необходимо: определить число запоминающих элементов и их тип; представить переключательную функцию комбинационной схе- мы в форме СДНФ или СКНФ; выполнить минимизацию ПФ; преобразовать ПФ к виду удобному для реализации на заданном базисе логических элементов; выполнить техническую реализацию полученной ПФ.
Комбинационная схема может быть разделена на две части.
Первая по логическим функциям переходов производит изменение состояния автомата, а вторая по функциям выходов обеспечивает формирование выходных сигналов.
Синтез комбинационных схем возбуждения памяти автомата и формирования выходных сигналов (или одной обобщенной комбина- ционной схемы см. рисунок 2.3) осуществляется в несколько этапов.
На первом этапе осуществляется словесное или табличное зада- ние свойств логической схемы. Для обеспечения однозначности вы- полняемых операций при словесном задании устройства необходимо выполнить переход к табличной форме.
На втором этапе получают совершенную дизъюнктивную или конъюнктивную нормальную форму переключательной функции.
1
m
y
−
1
n
x
−
0
x
Комбинационная схема
ЗЭ
ЗЭ
ЗЭ
Память
⋮
0
y
0
Q
1
Q
1
s
Q
−
0
g
1
g
1
s
g
−

68
На третьем этапе выполняется минимизация переключательной функции. Цель минимизации - упростить выражение ПФ для умень- шения числа элементов, реализующих ЦУ. Минимизация осуществ- ляется одним из возможных методов, чаще всего методом тождест- венных преобразований или методом диаграмм Вейча.Поскольку техническая реализация, полученная переключательной функцией, возможна разными логическими элементами, то на четвертом этапе выполняется преобразование полученной ПФ к виду, удобному для реализации на заданном (выбранном) базисе логических элементов.
И на заключительном пятом этапе логические операции ПФ за- меняются операционными элементами, реализующими эти функции.
Применение разных базисов логических элементов обусловлено понятием функциональной полноты различных базисов логических функций.
2.1.3 Функционально полные системы логических функций
Как было указано ранее, любую ПФ можно представить в виде
СДНФ (СКНФ), содержащей в общем случае переменные (х
1
, х
2
,…,
х
m
) и только три логические функции - инверсию (НЕ), конъюнкцию
(И) и дизъюнкцию (ИЛИ).
Набор элементарных логических функций, суперпозициями ко- торых может быть записана любая ПФ,
называют функционально полным.
Функциональной полнотой обладают следующие системы логи- ческих функций:
И, ИЛИ, НЕ (функции алгебры Буля);
И-НЕ (функция Шеффера);
ИЛИ-НЕ (функция Пирса);
И, сумма по модулю 2 (функции алгебры Жегалкина).
Наиболее разработанными и удобными являются функции буле- вой алгебры, в то же время эта система обладает избыточной полно- той, т.е. для реализации любой ПФ достаточно взять только две из указанных функций: либо "И", "НЕ", либо "ИЛИ", "НЕ".

69
Пример:
1) С помощью функции "И", "НЕ" реализуется функция "ИЛИ"
(рисунок 2.4).
1 2
1 2
1 2
x
x
x
x
x
x
y
∧
=
∨
=
∨
=
Рисунок 2.4 2) С помощью функции "ИЛИ", "НЕ" реализуется функция "И"
(рисунок 2.5).
1 2
1 2
1 2
x
x
x
x
x
x
y
∨
=
∧
=
∧
=
Рисунок 2.5
Как следствием этого, является утверждение о том, что функ- циональной полнотой обладают отдельно взятыефункция Шеффера
(И-НЕ) и функция Пирса (ИЛИ-НЕ).
Реализация функций "НЕ", "И", "ИЛИ" посредством функции "И-HЕ" представлена на рисунках 2.6, 2.7, 2.8.
Рисунок 2.6 - Функция "НЕ" на базисе логических функций Шеффера

70 1
2 1
2 1
2
x
x
x
x
x
x
y
∧
=
∨
=
∨
=
Рисунок 2.7-Функция "ИЛИ" на базисе логических функций Шеффера
1 2
1 2
x
x
x
x
y
∧
=
∧
=
Рисунок 2.8 - Функция "И" на базисе логических функций Шеффера
Реализация функций "НЕ", "И", "ИЛИ" посредством функции "ИЛИ-НЕ" представлена на рисунках 2.9, 2.10, 2.11.
Рисунок 2.9 - Функция "НЕ" на базисе логических функций Пирса
1 2
1 2
x
x
x
x
y
∨
=
∨
=
Рисунок 2.10 - Функция "ИЛИ"на базисе логических функций Пирса

71 1
2 1
2 1
2
х
х
x
x
x
x
y
∨
=
∧
=
∧
=
Рисунок 2.11 -Функция "И" на базисе логических функций Пирса
Реализация некоторой ПФ набором функций алгебры Жегалки- на заключается в выполнении следующих этапов: в СДНФ функции знаков дизъюнкции заменяются знаками сум- ма по модулю два; в конституентах единицы функции всех инверсий аргументов заменяются согласно тождества
1
⊕
=
x
x
; раскрываются скобки и упрощается полученное выражение со- гласно тождества
0
=
⊕
x
x
В соответствии с перечисленными этапами реализованные по- средством функций алгебры Жегалкина функции "НЕ" и "ИЛИ" пред- ставлены на рисунках 2.12, 2.13.
x
x
x
x
x
x
y
=
⋅
∨
⋅
=
⋅
∨
⋅
=
⊕
=
1 0
1 1
1
Рисунок 2.12 - Функция "НЕ" на базисе функций Жегалкина
.
x
x
x
x
x
x
x
x
x
x
x
x
)
x
(
x
)
x
(
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
)
x
x
(
x
)
x
x
(
x
x
x
y
1 0
1 0
1 0
1 0
1 0
1 0
0 1
1 0
1 0
0 1
1 0
1 0
0 1
0 1
1 0
1 0
0 0
1 1
1 0
1 0
1 1
⊕
⊕
=
⊕
⊕
⊕
⊕
=
=
⊕
⊕
⊕
⊕
=
⊕
⊕
=
=
∨
∨
∨
=
∨
⋅
∨
∨
⋅
=
∨
=
Рисунок 2.13 -Функция "ИЛИ" на базисе функций Жегалкина

72 2.1.4 Техническая реализация переключательных функций
Технический синтез логических схем заключается в замене опе- раций минимизированной и преобразованной к заданному виду пере- ключательной функции логическими элементами заданного базиса.
Пусть, минимизированная ПФ имеет вид:
3 1 2 0
y
x x
x x
=
∨
Выполним синтез данного выражения, используя широко рас- пространенный набор логических функций алгебры Шеффера (эле- менты 2И-НЕ, где цифра 2 соответствует числу входов логического элемента). Для этого вначале выполним преобразование полученного логического выражения. Используя правило де Моргана, получим:
3 1 2 0 3 1 2 0
y
x x
x x
x x
x x
=
∨
=
∧
Реализация данного выражения, полученная последовательной заменой логических операций соответствующими устройствами, представлена на рисунке 2.14.
Рисунок 2.14 – Функциональная схема синтезированного уст- ройства
Для реализации принципиальной схемы устройства по справоч- ной литературе находят соответствующую интегральную схему. На- пример, для рассматриваемого примера это может быть интегральная микросхема К155ЛА3 (рисунок 2.15). На рисунке 2.15,а показаны но- мера выводов интегральной микросхемы и их назначение. Питание обеспечивается подачей на 14 вывод микросхемы +5 В и соединения
7 вывода с минусом источника питания (общим проводом). Корпус микросхемы керамический с двумя рядами выводов изображен на ри-

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

74 2.2
Особенности синтеза цифровых автоматов с памятью
2.2.1 Общие сведения о триггере как элементе памяти
Один из этапов синтеза цифровых автоматов с памятью заклю- чается в выборе элементов памяти, определении их количества и ха- рактеристик.
Число элементов памяти S, нужное для реализации ЦА, имею- щего
Ψ
L
состояний, выбирается из условия
)
int(log
2
Ψ
≥
L
S
, где операция int означает округление до ближайшего большего цело- го числа.
Каждый элемент памяти должен сколь угодно долго находиться в одном из двух состоянии - 0 или 1, иметь возможность изменения этого состояния на противоположное под действием внешнего управ- ляющего сигнала.
Перечисленным требованиям удовлетворяют триггеры.
Триггером называется устройство, имеющее два устойчивых со- стояния равновесия и способное скачкообразно переходить из одного состояния в другое под воздействием управляющих сигналов.
Состояние и выходной сигнал триггера кодируют цифрами 1 и 0 и обозначают одной и той же двоичной переменной
=
Q
{0, 1}. Кроме выходного сигнала
Q
триггер обычно имеет и инверсный выходной сигнал
Q
Триггер в общем случае сам является элементарным цифровым автоматом с памятью и может быть задан функцией переходов:
)
,...,
,
(
)
(
0
)
(
1
)
(
)
1
(
)
1
(
t
t
n
t
t
t
x
x
Q
F
Q
−
+
+
=
=
Ψ
Возможны пять типов перехода триггера в новое состояние:
1.
)
(
)
1
(
t
t
Q
Q
=
+
- триггер не меняет своего состояния (режим хра- нения информации.
2.
0
)
1
(
=
+
t
Q
- установка в нуль.
3.
1
)
1
(
=
+
t
Q
- установка в единицу.
4.
)
(
)
1
(
t
t
Q
Q
=
+
- триггер устанавливается в противоположное состояние.
5.
X
Q
t
=
+
)
1
(
- неопределенное состояние при котором обычно наступает логическое противоречие
)
1
(
)
1
(
+
+
=
t
t
Q
Q