Вычислительная техника в измерительных информационных системах

Рассмотрим следующие примеры.

0 0 , 1 1 0 1

+ 0 0 , 1 0 0 1

0 1 , 0 1 1 0

1 1 , 0 0 1 1

+ 1 1 , 0 1 1 1

1 1 0 , 1 0 1 0

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

Разрядная сетка ЭВМ и форма представления числовой информации однозначно определяет диапазон представляемых в ЭВМ чисел и как следствие, точность получаемых результатов.

Если числовая информация представлена в естественной форме, то диапазоны представляемых чисел лежат в пределах: (для случая, когда запятая фиксирована левее самого старшего цифрового разряда).

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

n	m		n	m
0,11…1	2-11…1	X	0,11…1	2+11…1

0(или 1)	m	0 (или 1)	n
Знак порядка	Порядок	Знак мантиссы	Мантисса

Кодирование алфавитно-цифровой информации

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

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

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

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

При выборе способа кодирования необходимо учитывать объем алфавита символов, а также требования, связанные с облегчением автоматической обработки информации. Наибольшее распространение получило представление алфавитно-цифровой информации с помощью 8-разрядных слогов-байтов. С помощью байта можно кодировать 256 различных символов. Совокупность всех символов, используемых в ЭВМ, представляет собой ее алфавит. Каждый символ в ЭВМ с помощью устройства ввода преобразуется в соответствующий двоичный код.

Элементы алгебры логики

Для анализа и синтеза электронных схем ЭВМ широко используется математический аппарат алгебры логики, или булевой алгебры, разработанной в середине XIX века ирландским математиком Дж. Булем.

Основным понятием алгебры логики является понятие переключательной функции или булевой функции.

Переключательной функцией n переменных называется такая функция, которая принимает только два возможных значения - 0 или 1, так же как и переменные, от которых эта функция зависит.

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

В таблице 4.5. приведен произвольный пример табличного задания некоторой функции трех переменных f=f(A,B,C).

Таблица 4.5.

j	A	B	C	f
0	0	0	0	1
1	0	0	1	0
2	0	1	0	1
3	0	1	1	1
4	1	0	0	1
5	1	0	1	0
6	1	1	0	0
7	1	1	1	0

Конкретная комбинация значений аргументов носит название набора. Каждый набор имеет индекс j, численно равный десятичному эквиваленту двоичного числа. Очевидно, что функция от n переменных определена на 2ⁿ наборах их изображений. Количество различных переключательных функций от n переменных равно 2²ⁿ. Переключательные функции от одной и двух переменных принято называть элементарными. Эти функции имеют специальные названия и обозначения и используются при воспроизведении более сложных переключательных функций.

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

Таблица 4.6.

fj	X:	0	0	1	1	Название функции	Обозначение функции
	Y:	0	1	0	1
f0		0	0	0	0	константа 0	0
f1		0	0	0	1	конъюнкция X и Y	XY; X&Y; XY
f2		0	0	1	0	функция запрета по Y	XY
f3		0	0	1	1	переменная X	X
f4		0	1	0	0	функция запрета по X	YX
f5		0	1	0	1	переменная Y	Y
f6		0	1	1	0	функция неравнозначности	XY
f7		0	1	1	1	дизъюнкция X и Y	XY
f8		1	0	0	0	стрелка Пирса	XY
f9		1	0	0	1	функция равнозначности	XY
f10		1	0	1	0	инверсия Y
f11		1	0	1	1	импликация от X к Y	XY
f12		1	1	0	0	инверсия X
f13		1	1	0	1	импликация от Y к X	YX
f14		1	1	1	0	штрих Шеффера	XY
f15		1	1	1	1	константа 1	1

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

1) конъюнкция, дизъюнкция, инверсия;

2) конъюнкция, инверсия;

3) дизъюнкция, инверсия;

4) стрелка Пирса;

5) штрих Шеффера.

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

Для аналитической записи переключательных функций используется вспомогательная функция, называемая конституэнтой единицы. Конституэнтой единицы n переменных называется такое булево произведение (конъюнкция) этих переменных, в которое каждая переменная входит только один раз в прямой или инверсной форме. Отличительной особенностью конституэнты единицы является то, что она равна “1” только на одном, вполне определенном наборе значений переменных. Будем обозначать конституэнту единицы символом m_j, где индекс j указывает на номер набора, на котором конституэнта единицы становится равной “1”, аналогично функция конституэнты нуля обращается в “0” лишь при одном наборе аргументов.

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

переместительный закон XY=YX, XY=YX;

сочетательный закон X(YZ)=(XY)Z, X(YZ)=(XY)Z;

распределительный закон X(YZ)=XYXZ, XYZ=(XZ)(YZ);

закон отрицания (правило де Моргана) , ;

закон двойного отрицания ;

закон идемпотентности XX=X, 1X=1, 0X=X,

XX=X, 1X=X, 0X=0;

закон исключенного третьего склеивания X, ;

закон поглощения XXY=X;

константы

Аналитическая запись функции осуществляется по таблице истинности. Непосредственно из данных таблицы находится так называемая совершенная дизъюнктивная форма булевой функции (СДНФ) по выражению:

,

где f_j - значение функции на j-ом наборе, m_j - конституэнта единицы, равная “1” только на одном j-ом наборе, - символ логического сложения (дизъюнкции), аналогичный символу алгебраического сложения .

Для записи выражений в совершенной конъюктивной нормальной форме используют формулу:

,

где f_j - значение функции на j-ом наборе, n_j - конституэнта нуля, равная “0” только на одном j-ом наборе, - символ логического произведения (конъюнкции), аналогичный символу алгебраического произведения .

Проиллюстрируем СДНФ переключательной функции на примере булевой функции 3-х переменных, заданной ранее таблицей .

Подставляя из таблицы значения функций f₀f₇, получаем:

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

Функционально полные системы

Как показано выше, любая функция алгебры логики может быть записана в виде СДНФ или СКНФ. Следовательно, любую функцию аргументов можно представить с помощью системы только из трех элементарных функций: инверсия, дизъюнкции и конъюнкции. Возможны и другие системы функций, с помощью которых может быть выражена произвольная функция.

Система функций алгебры логики f₁, f₂, …, f_m называется полной, если любая функция от произвольного числа аргументов n может быть представлена суперпозицией функций f₁, f₂, …, f_m. Полная система функций называется базисом. Максимальным базисом называется такой базис f₁, f₂, …, f_m, для которого удаление хотя бы одной из функций f_j, образующих этот базис, превращает систему функций в неполную. Так, полная система из дизъюнкции, конъюнкции и инверсии может быть сокращена, поскольку с помощью формул де Моргана можно представить либо конъюнкцию через инверсию и дизъюнкцию, либо дизъюнкцию через инверсию и конъюнкцию. Таким образом, базис из дизъюнкции, конъюнкции и инверсии не является минимальным. Поскольку ни дизъюнкция, ни конъюнкция не могут быть выражены через инверсию и наоборот, и инверсия не может быть выражена ни через конъюнкцию, ни через дизъюнкцию, то следовательно, базисы, состоящие из инверсии и дизъюнкции, а так же из инверсии и конъюнкции, являются минимальными. Возможны различные базисы и минимальные базисы, отличающиеся числом входящих в них функций и их видом.

Для определения полноты заданной системы функций используются следующие свойства функций алгебры логики:

свойство сохранения нуля: функция обладает этим свойством, если для нее выполняется условие f(0, 0, ..., 0)=0, т.е. если функция на нулевом наборе аргументов равна 0;

свойство сохранения единицы: этим свойством обладают функции, для которых выполняются условия f(1, 1, ..., 1)=1, т.е. на единичном наборе аргументов значение функции равно 1.

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

,

свойство монотонности: функция обладает этим свойством, если для любых двух наборов аргументов (a₁, a₂, ..., a_n) и (a₁', a₂', ..., a_n'), в которых а₁a₁', a₂a₂', ...., a_na_n', где а и а' принимают значение либо 0, либо 1, выполняется условие f(a₁, a₂, ..., a_n) f(a₁', a₂', ..., a_n'). Например, набор 1011 не меньше набора 1010. Таким образом, функция является монотонной, если ее значение не убывает при переходе от любого набора значений аргументов к любому другому из возможных наборов, в котором значение соответствующих аргументов не меньше, чем в первом наборе;

свойство линейности: функция f(x₁, x₂, ..., x_n) является линейной, если ее можно представить с помощью элементарной функции сложения по модулю два в следующем виде:

f(x₁, x₂, ..., x_n)=a₀a₁x₁a₂x₂...a_nx_n,

где a_j - константы, имеющие значения нуля и единицы.

Определим, каким из этих свойств обладают элементарные функции. Для этого рассмотрим таблицу истинности функций двух аргументов (табл. 4.7.)

Таблица 4.7.

x1	x2	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0

Из приведенных в таблице элементарных функций свойством сохранения нуля обладают функции f₀, f₁, …, f₇, значение которых на нулевом наборе аргументов (x₁=0, x₂=0) равны 0. Свойством сохранения единицы обладают все функции с нечетными индексами f₁, f₃, ..., f₁₃, f₁₅, значения которых на единичном наборе аргументов (x₁=1, x₂=1) равны 1.

Среди элементарных функций двух аргументов самодвойственными являются функции, значение которых инвертируется при переходе от набора аргументов x₁=0, x₂=0 к набору x₁=1, x₂=1 и от набора x₁=0, x₂=1 к набору x₁=1, x₂=0. Свойством самодвойственности обладают функции f₃, f₅, f₁₀, f₁₂. Свойством монотонности обладают те из функций, значение которых не убывает при переходе от набора x₁=0, x₂=0 к наборам x₁=0, x₂=1; x₁=1, x₂=0; x₁=1, x₂=1, а так же от набора x₁=0, x₂=1 к набору x₁=1, x₂=1 и от набора x₁=1, x₂=0 к набору x₁=1, x₂=1. Свойством монотонности обладают функции f₀, f₁, f₃, f₅, f₇ и f₁₅.

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

f(x₁,x₂)=a₀a₁x₁a₂x₂.

При этом для различных наборов значения функции будут следующие:

f(0,0)=a₀, f(0,1)=a₀a₂, f(1,0)=a₀a₁, f(1,1)=a₀a₁a₂.

Первые три выражения позволяют определить коэффициенты a₀, a₁, a₂:

a₀=f(0,0), a₁=f(0,0)f(1,0), a₂=f(0,0)f(0,1).

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

f(1,1)=a₀a₁a₂,

то такая функция является линейной.

Свойства элементарных функций сведены в таблицу 4.8, где знаком `+` показано, какими из свойств обладают элементарные функции.

Таблица 4.8.

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

f0

f1

f2

f3

f4

f5

f6

f7

f8

f9

f10

f11

f12

f13

f14

f15

Сохранение 0

+

+

+

+

+

+

+

+

Сохранение 1

+

+

+

+

+

+

+

+

Самодвойственность

+

+

+

+

Монотонность

+

+

+

+

+

+

Линейность

+

+

+

+

+

+

+

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

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

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

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

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

Рассмотрим один из алгоритмов минимизации, предложенный американский ученым Вейчем. Вейч предложил специальные диаграммы-карты, в которые можно записать все конституэнты единицы, входящие в СДНФ той или иной булевой функции. На рис. 4.7.1 в качестве примера приведены диаграммы для минимизаций функций двух, трех и четырех переменных соответственно.

Рис. 4.7.1. Диаграммы Вейча для функций 2-х, 3-х и 4-х переменных.

Каждой клетке диаграммы соответствует определенная конситуэнта единицы. Метод минимизации с помощью диаграмм Вейча заключается в следующем. Конституэнты единицы, входящие в СДНФ булевой функции, заносятся в соответствующие клетки диаграммы. Удобно наличие соответствующей конституэнты единицы изображать в клетке диаграммы цифрой 1, а отсутствие - 0. Все диаграммы построены таким образом, что рядом расположенные единицы по горизонтали или вертикали соответствуют конституэнтам единицы, склеивающимися между собой в соответствии с законом об исключенном третьем склеивании. Одну и ту же конституэнту единицы можно использовать для склеивания с несколькими другими конституэнтами единицы с целью получения наиболее простого окончательного выражения. Цель всех операций - получить как можно меньшее число прямоугольников (в том числе квадратов), чтобы число членов СДНФ уменьшилось, получив в итоге МДНФ.

Формировать прямоугольники можно только при включении в них хотя бы одного нового члена, в том числе используя и склеивание путем замыкания крайних ребер в «бочку». На рис. 4.7.2 приведены некоторые правила склеивания конституэнт единицы для функций 2-х и 3-х переменных.

Рис. 4.7.2. Примеры для иллюстрации правил склеивания

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

Метод минимизации с помощью диаграмм Вейча включает в себя следующие шаги:

производиться занесение в соответствующую диаграмму конституэнт единицы, входящих в СДНФ минимизируемой функции;

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

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

В качестве примера найдем МДНФ функции, заданной табл. 4.5. Диаграмма Вейча этой функции представлена на рис. 4.7.3.

Рис. 4.7.3. Пример минимизации функции, заданной таблицей.

Контрольные вопросы

1. Перечислите основные системы счисления. Приведите примеры.

2. Определите порядок выполнения вычислений на ЭВМ.

3. Перечислите характеристики естественной формы представления информации.

4. Каковы особенности использования полулогарифмической формы?

5. Дайте определение переключательной функции от n переменных.

6. Перечислите элементарные функции.

7. Сформулируйте основные законы алгебры логики.

8. Перечислите свойства функций алгебры логики.

9. На примере объясните понятие минимизации логической функции.

Комбинационные цифровые устройства

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

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

ЦУ, выходные сигналы у которых в некоторый момент времени t_n зависят только от совокупности (комбинации) сигналов Х, присутствующих на их входах в тот же момент времени t_n, и не зависят от входных сигналов, поступивших в предшествующие моменты времени. Иными словами, ЦУ этого класса “не помнит” предыстории поступления сигналов на его входы. Такие ЦУ принято называть комбинационными (КЦУ);

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

Правила функционирования КЦУ могут быть заданы различными способами: словесно, таблицами истинности, булевыми выражениями. Реализация КЦУ предполагает выбор определенных логических элементов из заданного набора и их соединение таким образом, чтобы обеспечивалась зависимость цифровых выходных сигналов от входных с заданными правилами функционирования.

Базовые интегральные логические элементы

Элементной базой, используемой при построении КЦУ, являются интегральные логические элементы (ИЛЭ). В настоящее время выпускается широкая номенклатура ИЛЭ в составе различных серий интегральных микросхем на основе биполярных и полевых транзисторов.

При построении КЦУ с заданными характеристиками выбор необходимых ИЛЭ производится в соответствии с определенным набором их параметров. Рассмотрим важнейшие из них.

Коэффициент разветвления по входу К_раз - определяет число входов однотипных ИЛЭ, которые одновременно могут быть подключены к выходу данного логического элемента при сохранении его работоспособности в заданных условиях эксплуатации. Для различных элементов К_раз составляет от нескольких единиц до нескольких десятков.

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

Статические характеристики: входная, определяющая зависимость входного тока от входного напряжения; выходная, задающая связь между выходными напряжениями и током; передаточная, которая определяет зависимость выходного напряжения от входного.

Временные (динамические) параметры. От них зависит быстродействие логического элемента. Чаще всего оценивается время перехода элемента из состояния единицы в состояние нуля t^1.,0 и перехода в обратное состояние t^0,1. Указанные временные интервалы измеряются на уровнях 0,10,9 от установившихся значений в цепочке из однотипных элементов. Другим важнейшим параметром, определяющим быстродействие, являются время задержки распространения сигнала при включении t^1,0_здр и выключении t^0,1_здр логического элемента (рис 5.2.1.).

Рис. 5.2.1.

Измеряется на выходе по отношению ко входу на уровнях 0,5 от установившихся значений. Во многих случаях удобно пользоваться средним временем задержки распространения сигнала t_{здр. ср}, оцениваемым полусуммой t^1,0_здр и t^0,1_здр.

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

Основные электрические характеристики ИС различных серий приведены в таблице 5.1.

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

Кроме элементов, реализующих логическую операцию “штрих Шеффера” в состав большинства серий микросхем входят также логические элементы, реализующие логические операции: конъюнкцию (элементы “И”), дизъюнкцию (элементы “ИЛИ”) инверсию (элемент “НЕ”), и другие более сложные логические операции.

На рис. 5.2.2. представлены условные изображения наиболее распространенных логических элементов.

а) элемент “И” в) элемент “ИЛИ”

б) элемент “И-НЕ” г) элемент ”ИЛИ-НЕ”

д) элемент “НЕ” е) элемент “2И-ИЛИ”

ж) элемент “2И-ИЛИ-НЕ” з) элемент “2И-ИЛИ-НЕ” с инверсией по Х₃

Рис. 5.2.2. Условные обозначения логических элементов.

Синтез КЦУ

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

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

ЭТАП 1. Запись условий функционирования КЦУ. Как уже отмечалось ранее, эти условия могут быть заданы словесно, с помощью таблиц истинности или булевых выражений.

ЭТАП 2. Запись и минимизация булева выражения. Обычно производится на основе таблиц истинности. Если условия на этапе 1 заданы словесно, то на их основе предварительно составляется таблица истинности. Если булево выражение уже имеется на этапе 1, то выполняется его минимизация. В процессе минимизации широко используются преобразования с помощью соотношений булевой алгебры, а также алгебраические и графические методы.

ЭТАП 3. Запись минимизированной структурной формулы в заданном базисе. Так как реализация КЦУ на ИС предусматривает широкое использование элементов И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ, то часто возникает необходимость соответствующих преобразований структурных формул с учетом заданной элементной базы.

ЭТАП 4. Составление структурной схемы, т.е. изображение нужных логических элементов и связей между ними.

Проиллюстрируем этапы синтеза КЦУ примером.

Пример. Синтезировать на элементах И-НЕ КЦУ на три входа, выходной сигнал которого совпадает с большинством входных сигналов (мажоритарный элемент). Это словесное описание условий функционирования требуемого КЦУ. Ему соответствует таблица истинности (табл. 5.2.).

Таблица 5.2.

Номер набора	Х3	Х2	Х1	Y
0	0	0	0	0
1	0	0	1	0
2	0	1	0	0
3	0	1	1	1
4	1	0	0	0
5	1	0	1	1
6	1	1	0	1
7	1	1	1	1

Структурная формула в СДНФ имеет вид

информация вычислительный аналоговый преобразователь

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

. (5.1.)

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

(5.2.)

Структурная схема синтезированного на основе заданных условий КЦУ, соответствующего формуле (5.2.), приведена на рис. 5.3.1.

Рис. 5.3.1. Схема мажоритарного элемента.

Для его реализации требуется три двухвходовых логических элемента И-НЕ и один трехвходовый с суммарным числом входов 9.

На практике широко применяются КЦУ, имеющие несколько выходов. В наиболее общем виде можно рассматривать КЦУ как устройство, обеспечивающее преобразование m-разрядного входного кода в n-разрядный выходной, т.е. считать его кодопреобразователем. При проектировании таких устройств можно воспользоваться рассмотренным ранее аппаратом синтеза, если представить устройство в виде совокупности соответствующего числа КЦУ с общими входами. Этот подход будет применен далее при рассмотрении КЦУ, используемых в качестве структур цифровой техники.

Контрольные вопросы

1. Дайте определение КЦУ, определите классы цифровых устройств.

2. Перечислите параметры КЦУ. Дайте их определения.

3. Перечислите этапы синтеза КЦУ.

Типовые КЦУ

Дешифраторы.

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

Дешифратором (декодером) называется КЦУ с несколькими входами и выходами, у которого каждой комбинации входных сигналов соответствует активное значение только одного определенного выходного сигнала. Полный дешифратор с m входами имеет 2^m выходов.

Таблица истинности трехвходового полного дешифратора с единичными активными значениями выходных сигналов Y представлена в табл. 6.1.

Таблица 6.1.

X3	X2	X1	Y0	Y1	Y2	Y3	Y4	Y5
0	0	0	1	0	0	0	0	0
0	0	1	0	1	0	0	0	0
0	1	0	0	0	1	0	0
0	1	1	0	0	0	1	0
1	0	0	0	0	0	0	1
1	0	1	0	0	0	0	0
1	1	0	0	0	0	0	0
1	1	1	0	0	0	0	0

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

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

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

Рис. 6.1.1. Обозначение типового дешифратора.

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

Для увеличения функциональных возможностей устройств часто предусматривается использование нескольких сигналов управления и схем дешифрации. Вариант реализации такого дешифратора показан на рис. 6.1.1.б. На выходах двух дешифраторов формируются сигналы в соответствии с комбинациями входных сигналов X₁, X₂. Синхронизация процесса формирования выходных сигналов для каждого дешифратора задается комбинациями управляющих сигналов V. Для верхнего дешифратора разрешает формирование выходных сигналов комбинация , для нижнего . При отсутствии разрешающих комбинаций на каждом выходе Y устанавливается единичное значение сигнала. Введение такого управления расширяет возможности микросхемы при построении более сложных устройств, например, дешифраторов с увеличенным числом входов и выходов.

Шифраторы

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

Таблица 6.2.

X7	X6	X5	X4	X3	X2	X1	X0
0	1	1	1	1	1	1	1
1	0	1	1	1	1	1	1
1	1	0	1	1	1	1	1
1	1	1	0	1	1	1	1
1	1	1	1	0	1	1	1
1	1	1	1	1	0	1	1
1	1	1	1	1	1	0	1
1	1	1	1	1	1	1	0

На основе таблицы можно записать соответствующие структурные формулы для Y₃, Y₂, Y₁, а затем выполнить необходимые действия по их упрощению. Но в данном случае можно воспользоваться особенностью входных переменных, которые в интересующих нас комбинациях только в одном разряде имеют нулевое значение. Это позволяет, не прибегая к достаточно громоздкой в случае восьми входных переменных записи структурных формул в общем виде и их преобразований, представить значения входных переменных следующим образом:

Реализация рассматриваемого шифратора потребует трех ЛЭ 4И-НЕ. На практике может возникнуть необходимость построения и других вариантов шифраторов, например, использующих большое число разрядов входного сигнала.

Мультиплексоры

Мультиплексоры это устройства, которые обеспечивают коммутацию на выходе одного из нескольких информационных входных сигналов в соответствии с заданным кодом на управляющих входах. Условное графическое изображение одного из вариантов мультиплексора представлено на рис. 6.3.1. В зависимости от комбинации сигналов управления X₁, X₂, X₃ он обеспечивает коммутацию одного из восьми информационных входных сигналов D_i на выход Y. Сигнал синхронизации V в данном случае имеет нулевое активное значение, разрешающее передачу информации с одного из входов на выход.

Рис. 6.3.1. Обозначение мультиплексора на восемь входов с сигналом синхронизации.

Структурная формула, определяющая функционирование рассматриваемого восьмивходового мультиплексора, имеет вид:

Мультиплексор можно реализовать с помощью ЛЭ заданного базиса. В его структуру можно ввести и более сложные цифровые устройства. Сопоставляя формулы (6.1.) и (6.2.), можно заметить, что для каждого входа D комбинации сигналов управления X₁X₂X₃ в мультиплексоре такие же, как и в дешифраторе. Следовательно, составной частью мультиплексора с четырьмя информационными входами D является схема дешифратора, приведенная на рис. 6.3.2.

Рис. 6.3.2. Блок-схема синхронного мультиплексора на восемь входов.

Сумматоры

Сумматоры представляют собой цифровые устройства для сложения чисел. Рассмотрим сложение двух целых двоичных чисел без знаков А и В с формированием их суммы S:

А = 0 1 0 1 1

+

В = 0 0 0 1 1

S = 0 1 1 1 0

Из примера следует, что при формировании результата в любом i-ом разряде необходимо учесть значение чисел в этом разряде a_i и b_i, а так же перенос в этот разряд из предыдущего разряда P_i. Формируются значение суммы в этом разряде S_i и перенос в следующий разряд P_i+1. Сумматор может быть построен в виде комбинационного устройства, содержащего схемы для сложения отдельных разрядов (одноразрядные двоичные сумматоры). Условия функционирования одноразрядного сумматора определяются в таблице 6.3:

Таблица 6.3.

Pi	ai	bi	Si	Pi+1
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Булевы функции, описывающие работу одноразрядного двоичного сумматора, можно записать в виде (СДНФ):

(6.4.)

Используя различные варианты преобразования этих функций, можно реализовать большое число структур одноразрядных двоичных сумматоров. В качестве примера рассмотрим один из возможных вариантов построения сумматора на элементах И-НЕ. Выполним преобразование функции S_i:

Обозначим

Тогда

Перейдем с помощью формулы де Моргана к базису Шеффера:

(6.7.)

где . (6.8.)

Преобразование функции p_i+1 на основе склеивания и последующего использования формулы де Моргана дает:

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



Рис. 6.4.1. Вариант реализации схемы одноразрядного логического сумматора.

При построении КЦУ с несколькими выходами во многих случаях для уменьшения числа ЛЭ целесообразно использовать общие конструкции структурных формул. В данном примере применяется как в булевой формуле для S_i, так и в формуле для P_i+1.

Условное графическое обозначение одноразрядного двоичного сумматора приведено на рис. 6.4.2.

Рис. 6.4.2. Обозначение одноразрядного логического сумматора.

Перенос из младшего разряда здесь обозначен P₀, перенос в следующий разряд P₁.

Для обработки многоразрядных чисел объединяется соответствующее число одноразрядных сумматоров. При этом отдельные разряды обрабатываемых чисел А и В подаются на входы a_i и b_i. На вход P_i подается перенос из предыдущего, более младшего разряда. Формируемый в данном разряде перенос P_i+1 передается в следующий, более старший разряд. Такая организация процесса формирования переноса, называемая последовательным переносом, снижает быстродействие многоразрядного сумматора, так как полученный результат в старшем разряде сумматора обеспечивается только после завершения распространения переноса по всем разрядам. Поэтому иногда организуется параллельный перенос. Для этого в каждом одноразрядном двоичном сумматоре дополнительно формируются два сигнала: образование переноса g_i+1 и распространение переноса h_i+1:

(6.9.)

Действительно, при a_i=b_i=1 в i-ом разряде будет иметь место формирование переноса P_i+1 в следующий разряд независимо от результата переноса из предыдущего i-ого разряда. Следовательно, можно передавать сигнал переноса для обработки старших разрядов, не дожидаясь окончания формирования переноса из младших разрядов. Однако, если хотя бы один из сигналов a_i, b_i равен единице, то перенос в следующий разряд будет иметь место при наличии переноса из предыдущего разряда. Поэтому можно обеспечить формирование переноса P_i+1 с использованием специальной схемы ускоренного переноса, которая обрабатывает сигналы g и h из каждого разряда по следующему правилу:

(6.10.)

Для реализации ускоренного переноса в одноразрядные двоичные сумматоры необходимо ввести дополнительные ЛЭ для формирования сигналов g_i+1 и h_i+1 согласно формулам (6.9.).

Контрольные вопросы

1. Каково назначение дешифратора? Напишите таблицу истинности.

2. Каково назначение шифратора? Напишите таблицу истинности.

3. Что такое мультиплексор? Выведите структурную формулу функционирования восьмивходового мультиплексора.

4. Опишите работу одноразрядного и n-разрядного сумматора. Приведите таблицы истинности.

Анализ работы КЦУ.

Быстродействие КЦУ

Так как логические элементы, входящие в состав КЦУ, переключаются с задержкой t_здр, то при изменении в некоторый момент времени комбинации входных сигналов выходные сигналы устройства, если они изменяются в результате этого, примут установившиеся значения только после того, как закончатся переходные процессы в соответствующих логических элементах. На пути от входов устройства к его выходам отдельные логические элементы включены последовательно. Поэтому длительность переходных процессов будет зависеть от числа логических элементов, которые включены в такой цепочке. Применяемая в настоящее время методика определения t_здр в логических элементах, предусматривающая использование при измерении цепочки включенных друг за другом однотипных логических элементов, позволяет при оценке общей задержки в такой цепочке суммировать задержки отдельных логических элементов. При оценке быстродействия КЦУ необходимо выявить ту цепочку логических элементов между входами и выходами устройства, которая будет задавать наибольшую задержку, и сложить между собой задержки логических элементов этой цепочки. Обычно она содержит наибольшее число включенных друг за другом от входов до выходов логических элементов. Но могут быть исключения, связанные, например, с наличием в более короткой цепочки отдельных инерционных логических элементов с большим t_здр. Поэтому в общем случае необходимо проанализировать все цепочки логических элементов от входов до выходов и выявить такую, которая дает наибольшую задержку.

Пример. Синтезировать на логических элементах И-НЕ КЦУ, имеющее четыре входных сигнала X₁, X₂, X₃, X₄ и один выходной Y, заданное таблицей истинности (табл. 7.1.). Найти максимальную задержку, считая, что задержки во всех логических элементах одинаковы и составляют t_здр.

Табл. 7.1.

Номер набора	X4	X3	X2	X1	Y	Номер набора	X4	X3	X2
0	0	0	0	0	1	8	1	0	0
1	0	0	0	1	1	9	1	0	0
2	0	0	1	0	1	10	1	0	1
3	0	0	1	1	1	11	1	0	1
4	0	1	0	0	1	12	1	1	0
5	0	1	0	1	1	13	1	1	0
6	0	1	1	0	1	14	1	1	1
7	0	1	1	1	0	15	1	1	1

Карта Карно для рассматриваемого КЦУ, на основе которой получаем минимизированную структурную формулу

(7.1.)



Если поставить два знака инверсии над правой частью структурной формулы, то с помощью правила Моргана перейдем к формуле

(7.2.)

Структурная схема и временные диаграммы на основе этой формулы приведены на рис. 7.1.1. Цепочка логических элементов от входов до выхода содержит от двух до пяти элементов. В данном случае наибольшая задержка в 5t_здр связана с прохождением сигнала от входов до выхода по самой длинной цепочке. На временной диаграмме рассмотрено прохождение сигнала в схеме, когда на входе код 0001 изменяется на код 0011. Для упрощения картины переходных процессов предполагается, что сигналы в каждом элементе имеют одинаковую задержку t_здр, а сами сигналы прямоугольные. Задержка прохождения сигнала снижает быстродействие КЦУ, так как во многих случаях очередное изменение входных сигналов может быть допущено лишь после завершения переходных процессов и фиксации на выходе установившихся значений сигналов.



Рис. 7.1.1. Структурная схема и временные диаграммы КЦУ

Это ведет к образованию помехи в работе схемы, продолжительность которой в нашем случае равна 2t_здр. При синтезе можно постараться не допускать задержек и связанных с ними помех

Состязания в КЦУ

Неодинаковую задержку прохождения сигнала в отдельных частях КЦУ иногда ассоциируют с “состязаниями” в скорости переключения логических элементов. В результате этого явления на выходах некоторых элем...