ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 06.12.2023
Просмотров: 451
Скачиваний: 5
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
1
0
57 рядом расположенных клетках, но и те, которые находятся в крайних клетках строк и столбцов. При п = 5 правила определения соседних конституент единицы в каждой из половин ДВ таковы же, как при п
= 4. Однако при определении соседних конституент единицы, распо- ложенных в левой и правой частях ДВ, следует учесть, что соседними являются конституенты, находящиеся в столбцах с одинаковым но- мером, если его отсчитывать от левого края каждой половины.
Следует стремиться к образованию возможно меньшего количе- ства групп соседних конъюнкций (конституент единицы) с возможно большим числом, конституент единицы в группе.
Для каждой группы соседних конституент единицы пишутся конъюнкции, образуемые в результате склеивания, они образуются только на тех переменных, которые одинаковым образом (с инверси- ей или без инверсии) входят во все исходные конституенты единицы в каждой группе.
Находятся дизъюнкции конъюнкций, полученных при склеива- нии конституент единицы в каждой группе.
Применяя указанные правила, найдем МДНФ для ПФ, заданной на рисунке 1.6:
1 2
3 2
3 1
2 0
x
x
x
x
x
x
x
x
y
⋅
⋅
∨
⋅
∨
⋅
∨
=
Это выражение значительно проще выражения (1.7).
Группы соседних конституент единицы можно образовать по- разному. Поэтому в итоге описанной выше процедуры могут полу- чаться различные выражения ПФ, являющиеся тупиковыми ДНФ.
Одна из таких ДНФ может содержать наименьшее число вхождений переменных, именно эта тупиковая ДНФ и является минимальной.
1.5.4 Минимизация неполностью определенных переключа- тельных функций и представленных в форме СКНФ
Под неполностью определенными ПФ понимаются такие, кото- рые описывают работу логических схем (ЛС) при условии, что на их входах некоторые наборы переменных никогда не появляются и функции на них не определены. Поэтому при заполнении ДВ такой
ПФ некоторые клетки остаются пустыми. В процессе минимизации таких ПФ целесообразно доопределить их на отсутствующих наборах переменных, расставив в пустых клетках 1 и 0 так, чтобы образова- лись группы соседних конституент единицы с максимальным числом единиц, а количество таких групп было наименьшим.
58
В качестве примера рассмотрим синтез ЛС, предназначенной для выделения пяти старших цифр десятичной системы счисления, представленных четырехразрядными двоичными кодами:
3 2 1 0
A
x x x x
=
В данном случае номер набора A совпадает с числом, выражаемым данным кодом. Поскольку число различных наборов переменных равно 2 4
=16, а цифр десятичной системы всего десять, то на наборах с номерами 10, 11, 12, 13, 14, 15 ПФ оказывается неопределенной. В соответствии с заданием на наборах с номерами 0, 1, 2, 3, 4 (пять младших цифр) ПФ должна быть равна 0, а на наборах 5, 6, 7, 8, 9
(пять старших цифр) она должна быть равна 1.
На рисунке 1.7, а приведена ДВ заданной ПФ, а на рисунке 1.7,б указан способ доопределения ПФ, приводящий к минимальной ДНФ:
3 2
0 2 1
y
x
x x
x x
= ∨
∨
Для сравнения, минимизированная ПФ без доопределения неоп- ределенных наборов имеет вид:
3 2 1 3 2 0
3 2 1
y
x x x
x x x
x x x
=
∨
∨
Сложность этого выражения значительно выше, хотя и в этом случае удалось исключить из каждой конъюнкции по одной переменной, а число слагаемых уменьшить с пяти до трех.
2
х
2
х
2
х
2
х
1 1 1
х
1* 1* 1 1 1
х
3
х
3
х
1* 1* 1* 1*
1
х
1
х
1 1 0 0 1 1 0 0 3
х
3
х
0 1 0 0 1
х
0 1 0 0 1
х
0
х
0
х
0
х
0
х
0
х
0
х
а) б)
Рисунок 1.7
Кроме того, вместо групп соседних конституент единицы сле- дует образовывать группы соседних конституент нуля. В качестве примера на рисунке 1.8 показана ДВ для ПФ, заданной на рисунке
1.7,б. По этой диаграмме находим:
59
(
)
3 2
3 1
0
(
)
y
x
x
x
x
x
=
∨
∧
∨ ∨
2
х
2
х
1 1 1 1 1
х
3
х
1 1 1 1 1
х
1 1 0 0 3
х
0 1 0 0 1
х
0
х
0
х
0
х
Рисунок 1.8
Задания
для самостоятельной работы
Выполнить минимизацию переключательной функции методом тождественных преобразований и методом диаграмм Вейча
Значения выходного сигнала Y по вари- антам
Номер набора
Х
3
Х
2
Х
1
Х
0
Зада- ние 1
Зада- ние 2
Зада- ние 3
За- дани е 4
Зада- ние 5
За- дани е 6 0
0 0
0 0
0 0
0 0
0 0
1 0
0 0
1 1
0 0
0 0
0 2
0 0
1 0
1 1
0 1
0 1
3 0
0 1
1 1
1 1
1 0
0 4
0 1
0 0
0 1
1 1
0 0
5 0
1 0
1 0
0 0
0 1
1 6
0 1
1 0
0 0
0 1
1 1
7 0
1 1
1 0
0 0
0 1
1 8
1 0
0 0
1 0
0 0
0 0
9 1
0 0
1 1
0 0
0 0
0 10 1
0 1
0 0
1 0
0 0
1 11 1
0 1
1 1
1 1
0 0
1 12 1
1 0
0 1
1 1
1 1
0 13 1
1 0
1 0
0 1
1 0
0 14 1
1 1
0 0
0 0
1 1
0 15 1
1 1
1 0
0 0
0 1
0
60
Глава
2.
СХЕМОТЕХНИЧЕСКИЕ
ОСНОВЫ
ПОСТРОЕНИЯ
БОРТОВЫХ ВЫЧИСЛИТЕЛЬНЫХ МАШИН
2.1 Синтез цифровых автоматов
Методы описания и проектирования столь сложных объектов, какими являются ЭВМ, базируются на основополагающих принци- пах, сформулированных в общей теории систем. Поэтому, прежде чем приступить к рассмотрению способов построения и функционирова- ния БВМ, раскроем смысл основных понятий и принципов, которые относятся к общей теории систем и широко используются для борто- вых вычислительных машин.
Система — это совокупность элементов, объединенных в одно целое для достижения определенной цели. При этом под целью пони- мается множество результатов, определяемых назначением системы.
Вычислительная система в смысле указанного определения является системой, предназначенной для автоматизации вычислений на основе алгоритмов. Следует отметить, что понятие система приложимо как к
ЭВМ в целом, так и к отдельным частям ЭВМ, например к устройст- вам БВМ.
Чтобы описать систему, необходимо определить функции сис- темы и структуру системы.
Функция системы — правило получения результатов, опреде- ляемых назначением системы. Иначе говоря, функция системы — это описание процессов, которые имеют место в системе. Функции сис- тем стремятся описывать в математической форме ввиду компактно- сти и четкости, хотя может быть использована и другая форма, на- пример, словесная или табличная. Функции вычислительных систем чаще всего описываются в форме алгоритмов.
Структура системы — фиксированная совокупность элементов и связей между ними. Структура наглядно изображает, как устроена система — из каких частей она состоит и как эти части связаны друг с другом. Математической, а в этом смысле наиболее абстрактной и универсальной, формой изображения структуры является граф. Граф есть совокупность вершин и дуг (ребер), представляющих oднo- или двунаправленные связи между вершинами. Вершины графа отожде- ствляются с элементами (минимальными частями) системы, а дуги и ребра графа — со связями между соответствующими элементами.
61
Инженерная форма отображения структуры — схема. Схема и граф тождественны по своему содержанию и различаются лишь по форме. В схемах для обозначения элементов используются различные геометрические фигуры — условные графические обозначения, раз- нообразие форм которых облегчает чтение схем.
Система описана, если заданы ее функция и структура. Функция определяет порядок процессов в системе, а структура — состав и взаимосвязь частей (элементов, из которых состоит система). Систе- мам присуще следующее качество. Свойства совокупности элементов, объединенных в одну систему, не являются простой суммой свойств элементов, а имеют новое качество, отсутствующее в элементах. На- пример, в совокупности электронных элементов (транзисторов, рези- сторов и т. и.), определенным образом соединенных между собой, по- является эффект, который отождествляется с операциями математи- ческой логики, т. е. совокупность электрических элементов превра- щается в систему, функции которой описываются не законами элек- тротехники, а законами математической логики. Такого рода система из электронных элементов приобретает новое свойство и становится логическим элементом. В свою очередь, объединение логических элементов, каждый из которых реализует логическую операцию, при- водит к схеме, которая обладает свойством складывать числа. Прин- цип (способ), по которому объединение элементов приводит к появ- лению новых свойств, отличных от свойств элементов, называется принципом организации. Другими словами, организация - способ объединения элементов с целью осуществления определенных функ- ций в системах, состоящих из большого числа элементов.
Организация — понятие более высокого ранга, чем функция и структура. Конкретный принцип организации — это способ построе- ния различных систем, обладающих одинаковыми свойствами, т. е. один принцип организации, применяемый к различным случаям, при- водит к системам с различными функциями и структурами. Так что функция и структура — это конкретизация принципа организации, всего лишь один вариант организации
В свою очередь, различные принципы организации приводят к системам, различающимся своими функциями и структурами, и тож- дественным по своим свойствам, своему назначению. Когда речь идет о принципе порождения функций, необходимых и достаточных для обеспечения определенных свойств систем пользуются термином
62 функциональная организация. Функциональная организация — это принципы построения абстрактных систем, заданных своими функ- циями. Об абстрактной системе известно только ее назначение и не известно, как она устроена, из каких элементов состоит, т. е. абст- рактная система — это лишь описание, существующее на бумаге. Ко- гда речь идет о принципе порождения структур, необходимых и дос- таточных для реализации заданных функций, используется термин структурная организация. Структурная организация — это принципы перевода абстрактных систем, заданных в виде функций, в матери- альные системы, состоящие из физически существующих элементов.
Элементы бортовых цифровых вычислительных систем называют также цифровыми автоматами (ЦА).
2.1.1 Основные понятия из теории цифровых автоматов
В общем (абстрактном) виде цифровой автомат представляется как устройство с одним входом и одним выходом (рисунок 2.1), пред- назначенное для преобразования входной информации, отображаемой сигналами Х, в выходную информацию, отображаемую сигналами Y.
Рисунок 2.1
Основным качеством, выделяющим ЦА с памятью из других преобразователей информации, является наличие в ЦА дискретного множества внутренних состояний
ψ
. Это свойство ЦА определяется использованием в нем элементов памяти. Будем рассматривать только
ЦА с конечным числом L
ψ
внутренних состояний (конечные ЦА).
Каждому состоянию присвоен определенный номер
( )
β ψ
, где
0,1, 2,...,
1
L
ψ
β
=
−
В теории автоматов принят алфавитный способ задания инфор- мации. Алфавитом называется конечная совокупность символов, на- зываемых словами. Число букв в слове определяет длину слова.
{
}
0 1
1
,
,...,
m
Y
y
y
y
−
=
{
}
0 1
1
,
,...,
n
X
x x
x
−
=
{
}
0 1
1
,
,...
s
Q Q
Q
ψ
−
=
ЦА
63
Входной сигнал Х может принимать одно из
x
L различных зна- чений, каждое из этих значений принимается за букву. Совокупность всех значений составляет входной алфавит ЦА. Выходные сигналы могут принимать одно из
y
L различных значений, составляющих вы- ходной алфавит ЦА.
Алфавит внутренних состояний содержит L
ψ
букв. Буквы вход- ного, выходного алфавита и алфавита состояний могут принимать только два значения: 0 и 1.
Поэтому
2 ;
2 ;
2 ,
n
m
s
x
y
L
L
L
ψ
=
=
=
где n - количество разрядов входного сигнала,
m
- количество разрядов выходного сигнала,
s
- количество элементов памяти.
В общем случае поведение ЦА (см. рисунок 2.1) в момент вре- мени t описывается зависимостью выходного сигнала
( )
Y t
от значе- ний входных сигналов
( ),
(
1),
(
2)...
X t
X t
X t
−
−
, т.е. в данный и преды- дущие моменты времени ,
t
(
1), (
2)
t
t
−
−
и т.д.
При этом возможны два случая:
1) значение выходного сигнала
( )
Y t
в момент времени одно- значно определяется сигналами на входе
( )
X t
в тот же момент вре- мени. В этом случае техническая реализация ЦА соответствует схеме без элементов памяти, которая называется комбинационной схемой
(КС). В качестве математического аппарата анализа и синтеза КС ис- пользуется теория логических (переключательных) функций;
2) значение выходного канала
( )
Y t
в момент времени t опреде- ляется значениями сигнала на входе
( ),
(
1),
(
2)
X t
X t
X t
−
−
и т.д.
Техническая реализация ЦА для этого случая соответствует схеме с элементами памяти.
Рассмотрим некоторые особенности функционирования конеч- ных ЦА. Закон преобразования информации в конечном ЦА описыва- ется функцией переходов
(
1)
t
ψ
+
и функцией выходов
( )
Y t
В зависимости от характера этих функций различают ЦА двух родов, которые нашли наибольшее применение в цифровых устройст- вах.
ЦА первого рода (автоматы Мили). Функция переходов
[
]
(
1)
( ),
( )
t
F
t X t
ψ
ψ
+ =
64 определяет внутреннее состояние ЦА в момент
(
1)
t
+
в зависимости от входного сигнала
( )
X t
и внутреннего состояния
( )
t
ψ
Функ- ция выходов
[
]
( )
( ),
( )
Y t
f
t X t
ψ
=
определяет выходной сигнал в момент времени t при условии, что
ЦА находится в состоянии ( )
t
ψ
и подвергается воздействию входного сигнала
( )
X t .
ЦА второго рода (автоматы Мура).
Функция выходов
[
]
( )
( )
Y t
f
t
ψ
=
описывает выходной сигнал в момент времени t , который определя- ется только внутренним состоянием ЦА ( )
t
ψ
и не зависит от входно- го воздействия.
Функции переходов ЦА второго и первого родов совпадают.
Различают три способа описания функций (
1)
t
ψ
+
и
( )
Y t : анали- тический, графический, табличный.
Аналитический способ является наиболее универсальным, но не очень наглядным. Наибольшей наглядностью обладают другие два способа. Графически автомат задают ориентированным графом, вер- шины которого отождествляют с состояниями автомата, а ребра (ду- ги) – с переходами из одного состояния в другое. Ребра графа автома- та Мили отмечают входными и выходными сигналами (буквами), со- ответствующими данному переходу. В графе автомата Мура ребра отмечают входными сигналами, а вершины – состояниями и соответ- ствующим им выходными сигналами.
На рисунке 2.2 приведен граф автомата Мура. Графическое представление имеет наибольшую наглядность, но с увеличением числа состояний автомата наглядность теряется. Кроме того, автома- тизированные методы синтеза ЦА представленных графами в на- стоящее время не нашли широкого распространения в виду слабой формализации алгоритмов.
Рисунок 2.2 0
ψ
1
ψ
0
Y
1
Y
1
X
2
X
0
X
0
X
65
В дальнейшем будет использоваться табличный способ описа- ния функций
(
1)
t
ψ
+
и
( )
Y t
с помощью таблиц переходов и выходов, соответственно, таблицы 2.1 и 2.2.
Таблица 2.1- Таблица переходов ЦА
( )
t
ψ
( )
X t
0
ψ
1
ψ
2
ψ
…
2
L
ψ
ψ
−
1
L
ψ
ψ
−
0
X
2
ψ
5
ψ
4
ψ
…
3
L
ψ
ψ
−
6
ψ
1
X
1
X
L
ψ
−
1
ψ
5
ψ
…
3
ψ
2
ψ
…
…
…
…
…
…
…
2
X
L
X
−
4
ψ
1
X
L
ψ
−
0
ψ
…
0
ψ
6
ψ
1
X
L
X
−
1
ψ
0
ψ
2
ψ
…
4
ψ
8
ψ
Таблица 2.2 – Таблица выходов ЦА
( )
t
ψ
( )
X t
0
ψ
1
ψ
2
ψ
…
3
L
ψ
ψ
−
2
L
ψ
ψ
−
1
L
ψ
ψ
−
0
X
3
Y
1
Y
4
Y
L
Y
−
…
0
Y
6
Y
7
Y
X
3
Y
0
Y
4
Y
…
1
Y
1
L
Y
ψ −
5
Y
…
…
…
…
…
…
…
…
2
X
L
X
−
0
Y
6
Y
0
Y
…
5
Y
4
Y
1
Y
1
X
L
X
−
1
Y
7
Y
8
Y
…
7
Y
7
Y
0
Y
При построении таблицы переходов (см. таблицу 2.1) в левом крайнем столбце записываются все входные сигналы из входного ал- фавита
(
)
1 0
,...
X
L
X
X
−
, а в верхней строке – все возможные состояния
ЦА
(
)
1 0
,...,
L
ψ
ψ
ψ
−
. Если в момент t ЦА находится в состоянии
(
)
1
( )
0
t
L
β
ψ
ψ
ψ
β
−
=
≤ ≤
и на него действует входной сигнал
( )
X t
, то в момент
1
t
+
ЦА перейдет в состояние
(
1)
t
ψ
+
, являющееся элемен- том алфавита состояний. Новое состояние
(
1)
t
ψ
+
записывается в клетку таблицы, расположенную на пересечении столбца и строки, соответствующих
( )
X t
и
( )
t
ψ
0
57 рядом расположенных клетках, но и те, которые находятся в крайних клетках строк и столбцов. При п = 5 правила определения соседних конституент единицы в каждой из половин ДВ таковы же, как при п
= 4. Однако при определении соседних конституент единицы, распо- ложенных в левой и правой частях ДВ, следует учесть, что соседними являются конституенты, находящиеся в столбцах с одинаковым но- мером, если его отсчитывать от левого края каждой половины.
Следует стремиться к образованию возможно меньшего количе- ства групп соседних конъюнкций (конституент единицы) с возможно большим числом, конституент единицы в группе.
Для каждой группы соседних конституент единицы пишутся конъюнкции, образуемые в результате склеивания, они образуются только на тех переменных, которые одинаковым образом (с инверси- ей или без инверсии) входят во все исходные конституенты единицы в каждой группе.
Находятся дизъюнкции конъюнкций, полученных при склеива- нии конституент единицы в каждой группе.
Применяя указанные правила, найдем МДНФ для ПФ, заданной на рисунке 1.6:
1 2
3 2
3 1
2 0
x
x
x
x
x
x
x
x
y
⋅
⋅
∨
⋅
∨
⋅
∨
=
Это выражение значительно проще выражения (1.7).
Группы соседних конституент единицы можно образовать по- разному. Поэтому в итоге описанной выше процедуры могут полу- чаться различные выражения ПФ, являющиеся тупиковыми ДНФ.
Одна из таких ДНФ может содержать наименьшее число вхождений переменных, именно эта тупиковая ДНФ и является минимальной.
1.5.4 Минимизация неполностью определенных переключа- тельных функций и представленных в форме СКНФ
Под неполностью определенными ПФ понимаются такие, кото- рые описывают работу логических схем (ЛС) при условии, что на их входах некоторые наборы переменных никогда не появляются и функции на них не определены. Поэтому при заполнении ДВ такой
ПФ некоторые клетки остаются пустыми. В процессе минимизации таких ПФ целесообразно доопределить их на отсутствующих наборах переменных, расставив в пустых клетках 1 и 0 так, чтобы образова- лись группы соседних конституент единицы с максимальным числом единиц, а количество таких групп было наименьшим.
58
В качестве примера рассмотрим синтез ЛС, предназначенной для выделения пяти старших цифр десятичной системы счисления, представленных четырехразрядными двоичными кодами:
3 2 1 0
A
x x x x
=
В данном случае номер набора A совпадает с числом, выражаемым данным кодом. Поскольку число различных наборов переменных равно 2 4
=16, а цифр десятичной системы всего десять, то на наборах с номерами 10, 11, 12, 13, 14, 15 ПФ оказывается неопределенной. В соответствии с заданием на наборах с номерами 0, 1, 2, 3, 4 (пять младших цифр) ПФ должна быть равна 0, а на наборах 5, 6, 7, 8, 9
(пять старших цифр) она должна быть равна 1.
На рисунке 1.7, а приведена ДВ заданной ПФ, а на рисунке 1.7,б указан способ доопределения ПФ, приводящий к минимальной ДНФ:
3 2
0 2 1
y
x
x x
x x
= ∨
∨
Для сравнения, минимизированная ПФ без доопределения неоп- ределенных наборов имеет вид:
3 2 1 3 2 0
3 2 1
y
x x x
x x x
x x x
=
∨
∨
Сложность этого выражения значительно выше, хотя и в этом случае удалось исключить из каждой конъюнкции по одной переменной, а число слагаемых уменьшить с пяти до трех.
2
х
2
х
2
х
2
х
1 1 1
х
1* 1* 1 1 1
х
3
х
3
х
1* 1* 1* 1*
1
х
1
х
1 1 0 0 1 1 0 0 3
х
3
х
0 1 0 0 1
х
0 1 0 0 1
х
0
х
0
х
0
х
0
х
0
х
0
х
а) б)
Рисунок 1.7
Кроме того, вместо групп соседних конституент единицы сле- дует образовывать группы соседних конституент нуля. В качестве примера на рисунке 1.8 показана ДВ для ПФ, заданной на рисунке
1.7,б. По этой диаграмме находим:
59
(
)
3 2
3 1
0
(
)
y
x
x
x
x
x
=
∨
∧
∨ ∨
2
х
2
х
1 1 1 1 1
х
3
х
1 1 1 1 1
х
1 1 0 0 3
х
0 1 0 0 1
х
0
х
0
х
0
х
Рисунок 1.8
Задания
для самостоятельной работы
Выполнить минимизацию переключательной функции методом тождественных преобразований и методом диаграмм Вейча
Значения выходного сигнала Y по вари- антам
Номер набора
Х
3
Х
2
Х
1
Х
0
Зада- ние 1
Зада- ние 2
Зада- ние 3
За- дани е 4
Зада- ние 5
За- дани е 6 0
0 0
0 0
0 0
0 0
0 0
1 0
0 0
1 1
0 0
0 0
0 2
0 0
1 0
1 1
0 1
0 1
3 0
0 1
1 1
1 1
1 0
0 4
0 1
0 0
0 1
1 1
0 0
5 0
1 0
1 0
0 0
0 1
1 6
0 1
1 0
0 0
0 1
1 1
7 0
1 1
1 0
0 0
0 1
1 8
1 0
0 0
1 0
0 0
0 0
9 1
0 0
1 1
0 0
0 0
0 10 1
0 1
0 0
1 0
0 0
1 11 1
0 1
1 1
1 1
0 0
1 12 1
1 0
0 1
1 1
1 1
0 13 1
1 0
1 0
0 1
1 0
0 14 1
1 1
0 0
0 0
1 1
0 15 1
1 1
1 0
0 0
0 1
0
60
Глава
2.
СХЕМОТЕХНИЧЕСКИЕ
ОСНОВЫ
ПОСТРОЕНИЯ
БОРТОВЫХ ВЫЧИСЛИТЕЛЬНЫХ МАШИН
2.1 Синтез цифровых автоматов
Методы описания и проектирования столь сложных объектов, какими являются ЭВМ, базируются на основополагающих принци- пах, сформулированных в общей теории систем. Поэтому, прежде чем приступить к рассмотрению способов построения и функционирова- ния БВМ, раскроем смысл основных понятий и принципов, которые относятся к общей теории систем и широко используются для борто- вых вычислительных машин.
Система — это совокупность элементов, объединенных в одно целое для достижения определенной цели. При этом под целью пони- мается множество результатов, определяемых назначением системы.
Вычислительная система в смысле указанного определения является системой, предназначенной для автоматизации вычислений на основе алгоритмов. Следует отметить, что понятие система приложимо как к
ЭВМ в целом, так и к отдельным частям ЭВМ, например к устройст- вам БВМ.
Чтобы описать систему, необходимо определить функции сис- темы и структуру системы.
Функция системы — правило получения результатов, опреде- ляемых назначением системы. Иначе говоря, функция системы — это описание процессов, которые имеют место в системе. Функции сис- тем стремятся описывать в математической форме ввиду компактно- сти и четкости, хотя может быть использована и другая форма, на- пример, словесная или табличная. Функции вычислительных систем чаще всего описываются в форме алгоритмов.
Структура системы — фиксированная совокупность элементов и связей между ними. Структура наглядно изображает, как устроена система — из каких частей она состоит и как эти части связаны друг с другом. Математической, а в этом смысле наиболее абстрактной и универсальной, формой изображения структуры является граф. Граф есть совокупность вершин и дуг (ребер), представляющих oднo- или двунаправленные связи между вершинами. Вершины графа отожде- ствляются с элементами (минимальными частями) системы, а дуги и ребра графа — со связями между соответствующими элементами.
61
Инженерная форма отображения структуры — схема. Схема и граф тождественны по своему содержанию и различаются лишь по форме. В схемах для обозначения элементов используются различные геометрические фигуры — условные графические обозначения, раз- нообразие форм которых облегчает чтение схем.
Система описана, если заданы ее функция и структура. Функция определяет порядок процессов в системе, а структура — состав и взаимосвязь частей (элементов, из которых состоит система). Систе- мам присуще следующее качество. Свойства совокупности элементов, объединенных в одну систему, не являются простой суммой свойств элементов, а имеют новое качество, отсутствующее в элементах. На- пример, в совокупности электронных элементов (транзисторов, рези- сторов и т. и.), определенным образом соединенных между собой, по- является эффект, который отождествляется с операциями математи- ческой логики, т. е. совокупность электрических элементов превра- щается в систему, функции которой описываются не законами элек- тротехники, а законами математической логики. Такого рода система из электронных элементов приобретает новое свойство и становится логическим элементом. В свою очередь, объединение логических элементов, каждый из которых реализует логическую операцию, при- водит к схеме, которая обладает свойством складывать числа. Прин- цип (способ), по которому объединение элементов приводит к появ- лению новых свойств, отличных от свойств элементов, называется принципом организации. Другими словами, организация - способ объединения элементов с целью осуществления определенных функ- ций в системах, состоящих из большого числа элементов.
Организация — понятие более высокого ранга, чем функция и структура. Конкретный принцип организации — это способ построе- ния различных систем, обладающих одинаковыми свойствами, т. е. один принцип организации, применяемый к различным случаям, при- водит к системам с различными функциями и структурами. Так что функция и структура — это конкретизация принципа организации, всего лишь один вариант организации
В свою очередь, различные принципы организации приводят к системам, различающимся своими функциями и структурами, и тож- дественным по своим свойствам, своему назначению. Когда речь идет о принципе порождения функций, необходимых и достаточных для обеспечения определенных свойств систем пользуются термином
62 функциональная организация. Функциональная организация — это принципы построения абстрактных систем, заданных своими функ- циями. Об абстрактной системе известно только ее назначение и не известно, как она устроена, из каких элементов состоит, т. е. абст- рактная система — это лишь описание, существующее на бумаге. Ко- гда речь идет о принципе порождения структур, необходимых и дос- таточных для реализации заданных функций, используется термин структурная организация. Структурная организация — это принципы перевода абстрактных систем, заданных в виде функций, в матери- альные системы, состоящие из физически существующих элементов.
Элементы бортовых цифровых вычислительных систем называют также цифровыми автоматами (ЦА).
2.1.1 Основные понятия из теории цифровых автоматов
В общем (абстрактном) виде цифровой автомат представляется как устройство с одним входом и одним выходом (рисунок 2.1), пред- назначенное для преобразования входной информации, отображаемой сигналами Х, в выходную информацию, отображаемую сигналами Y.
Рисунок 2.1
Основным качеством, выделяющим ЦА с памятью из других преобразователей информации, является наличие в ЦА дискретного множества внутренних состояний
ψ
. Это свойство ЦА определяется использованием в нем элементов памяти. Будем рассматривать только
ЦА с конечным числом L
ψ
внутренних состояний (конечные ЦА).
Каждому состоянию присвоен определенный номер
( )
β ψ
, где
0,1, 2,...,
1
L
ψ
β
=
−
В теории автоматов принят алфавитный способ задания инфор- мации. Алфавитом называется конечная совокупность символов, на- зываемых словами. Число букв в слове определяет длину слова.
{
}
0 1
1
,
,...,
m
Y
y
y
y
−
=
{
}
0 1
1
,
,...,
n
X
x x
x
−
=
{
}
0 1
1
,
,...
s
Q Q
Q
ψ
−
=
ЦА
63
Входной сигнал Х может принимать одно из
x
L различных зна- чений, каждое из этих значений принимается за букву. Совокупность всех значений составляет входной алфавит ЦА. Выходные сигналы могут принимать одно из
y
L различных значений, составляющих вы- ходной алфавит ЦА.
Алфавит внутренних состояний содержит L
ψ
букв. Буквы вход- ного, выходного алфавита и алфавита состояний могут принимать только два значения: 0 и 1.
Поэтому
2 ;
2 ;
2 ,
n
m
s
x
y
L
L
L
ψ
=
=
=
где n - количество разрядов входного сигнала,
m
- количество разрядов выходного сигнала,
s
- количество элементов памяти.
В общем случае поведение ЦА (см. рисунок 2.1) в момент вре- мени t описывается зависимостью выходного сигнала
( )
Y t
от значе- ний входных сигналов
( ),
(
1),
(
2)...
X t
X t
X t
−
−
, т.е. в данный и преды- дущие моменты времени ,
t
(
1), (
2)
t
t
−
−
и т.д.
При этом возможны два случая:
1) значение выходного сигнала
( )
Y t
в момент времени одно- значно определяется сигналами на входе
( )
X t
в тот же момент вре- мени. В этом случае техническая реализация ЦА соответствует схеме без элементов памяти, которая называется комбинационной схемой
(КС). В качестве математического аппарата анализа и синтеза КС ис- пользуется теория логических (переключательных) функций;
2) значение выходного канала
( )
Y t
в момент времени t опреде- ляется значениями сигнала на входе
( ),
(
1),
(
2)
X t
X t
X t
−
−
и т.д.
Техническая реализация ЦА для этого случая соответствует схеме с элементами памяти.
Рассмотрим некоторые особенности функционирования конеч- ных ЦА. Закон преобразования информации в конечном ЦА описыва- ется функцией переходов
(
1)
t
ψ
+
и функцией выходов
( )
Y t
В зависимости от характера этих функций различают ЦА двух родов, которые нашли наибольшее применение в цифровых устройст- вах.
ЦА первого рода (автоматы Мили). Функция переходов
[
]
(
1)
( ),
( )
t
F
t X t
ψ
ψ
+ =
64 определяет внутреннее состояние ЦА в момент
(
1)
t
+
в зависимости от входного сигнала
( )
X t
и внутреннего состояния
( )
t
ψ
Функ- ция выходов
[
]
( )
( ),
( )
Y t
f
t X t
ψ
=
определяет выходной сигнал в момент времени t при условии, что
ЦА находится в состоянии ( )
t
ψ
и подвергается воздействию входного сигнала
( )
X t .
ЦА второго рода (автоматы Мура).
Функция выходов
[
]
( )
( )
Y t
f
t
ψ
=
описывает выходной сигнал в момент времени t , который определя- ется только внутренним состоянием ЦА ( )
t
ψ
и не зависит от входно- го воздействия.
Функции переходов ЦА второго и первого родов совпадают.
Различают три способа описания функций (
1)
t
ψ
+
и
( )
Y t : анали- тический, графический, табличный.
Аналитический способ является наиболее универсальным, но не очень наглядным. Наибольшей наглядностью обладают другие два способа. Графически автомат задают ориентированным графом, вер- шины которого отождествляют с состояниями автомата, а ребра (ду- ги) – с переходами из одного состояния в другое. Ребра графа автома- та Мили отмечают входными и выходными сигналами (буквами), со- ответствующими данному переходу. В графе автомата Мура ребра отмечают входными сигналами, а вершины – состояниями и соответ- ствующим им выходными сигналами.
На рисунке 2.2 приведен граф автомата Мура. Графическое представление имеет наибольшую наглядность, но с увеличением числа состояний автомата наглядность теряется. Кроме того, автома- тизированные методы синтеза ЦА представленных графами в на- стоящее время не нашли широкого распространения в виду слабой формализации алгоритмов.
Рисунок 2.2 0
ψ
1
ψ
0
Y
1
Y
1
X
2
X
0
X
0
X
65
В дальнейшем будет использоваться табличный способ описа- ния функций
(
1)
t
ψ
+
и
( )
Y t
с помощью таблиц переходов и выходов, соответственно, таблицы 2.1 и 2.2.
Таблица 2.1- Таблица переходов ЦА
( )
t
ψ
( )
X t
0
ψ
1
ψ
2
ψ
…
2
L
ψ
ψ
−
1
L
ψ
ψ
−
0
X
2
ψ
5
ψ
4
ψ
…
3
L
ψ
ψ
−
6
ψ
1
X
1
X
L
ψ
−
1
ψ
5
ψ
…
3
ψ
2
ψ
…
…
…
…
…
…
…
2
X
L
X
−
4
ψ
1
X
L
ψ
−
0
ψ
…
0
ψ
6
ψ
1
X
L
X
−
1
ψ
0
ψ
2
ψ
…
4
ψ
8
ψ
Таблица 2.2 – Таблица выходов ЦА
( )
t
ψ
( )
X t
0
ψ
1
ψ
2
ψ
…
3
L
ψ
ψ
−
2
L
ψ
ψ
−
1
L
ψ
ψ
−
0
X
3
Y
1
Y
4
Y
L
Y
−
…
0
Y
6
Y
7
Y
X
3
Y
0
Y
4
Y
…
1
Y
1
L
Y
ψ −
5
Y
…
…
…
…
…
…
…
…
2
X
L
X
−
0
Y
6
Y
0
Y
…
5
Y
4
Y
1
Y
1
X
L
X
−
1
Y
7
Y
8
Y
…
7
Y
7
Y
0
Y
При построении таблицы переходов (см. таблицу 2.1) в левом крайнем столбце записываются все входные сигналы из входного ал- фавита
(
)
1 0
,...
X
L
X
X
−
, а в верхней строке – все возможные состояния
ЦА
(
)
1 0
,...,
L
ψ
ψ
ψ
−
. Если в момент t ЦА находится в состоянии
(
)
1
( )
0
t
L
β
ψ
ψ
ψ
β
−
=
≤ ≤
и на него действует входной сигнал
( )
X t
, то в момент
1
t
+
ЦА перейдет в состояние
(
1)
t
ψ
+
, являющееся элемен- том алфавита состояний. Новое состояние
(
1)
t
ψ
+
записывается в клетку таблицы, расположенную на пересечении столбца и строки, соответствующих
( )
X t
и
( )
t
ψ