Тема 1. Математическое введение в цифровую технику.

1-1. Системы счисления, используемые в цифровой технике.

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

В непозиционной системе счисления значение символа (цифры, буквы, знака или иероглифа) постоянно и не зависит от позиции этого символа в изображаемом числе. В позиционных системах наоборот, значение символа зависит от позиции этого символа в изображаемом числе. Непозиционные системы, как более простые, появились исторически гораздо более раньше позиционных систем. Ими пользовались древние славяне, китайцы и другие народы. До наших дней дошла одна из разновидностей непозиционных систем - римская система счисления. В ней используются так называемые римские цифры: I - 1, V - 5, X - 10, L - 50, C - 100, D - 500, M - 1000. Значение числа вычисляется суммированием всех чисел с учетом правила, что если цифра меньшего веса стоит слева от следующей за ней цифрой большего веса, то она имеет знак минус, а если справа - то знак плюс. Например, число MCCXXXIV определяется следующим образом:

1000 + 100 + 100 + 10 + 10 + 10 - 1 + 5 = 1234

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

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

В позиционных системах счисления любое число X изображается в виде полинома

. (1.1)

B этом выражении a_j называются разрядными коэффициентами, S - основанием системы счисления, а S^j – весовыми коэффициентами. Значение любого разрядного коэффициента в изображаемом числе может лежать в диапазоне от 0 до S-1. В настоящее время во всех странах мира используется десятичная система счисления, представляющая собой позиционную систему счисления с основанием S=10. Разрядные коэффициенты при изображении чисел в десятичной системе счисления могут принимать значения в диапазоне от 0 до 9. Для краткости вместо записи числа в виде полинома записывают только последовательность разрядных коэффициентов этого полинома. Когда мы пишем десятичное число X₁₀=163,28, то подразумеваем величину

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

.

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

То же самое десятичное число 247₁₀ можно записать в виде 11110111₂ двоичного числа. Действительно

247:2=123+1 (X₀=1)

123:2=61+1 (Х₁=1)

61:2=30+1 (Х₂=1)

30:2=15+0 (Х₃=0)

15:2=7+1 (Х₄=1)

7:2=3+1 (Х₅=1)

3:2=1+1 (Х₆=1)

1:2=0+1 (Х₇=1)

Записываем число в новой системе счисления с последнего результата деления: 11110111₂.

Осуществим перевод дробного десятичного числа 125,48₁₀ в двоичное. Переведем сначала целую часть:

125:2=62+1 (Х₀=1)

62:2=31+0 (Х₁=0)

31:2=15+1 (Х₂=1)

15:2=7+1 (Х₃=1)

7:2=3+1 (Х₄=1)

3:2=1+1 (Х₅=1)

1:2=0+1 (Х₆=1)

Записываем целую часть: 125₁₀=1111101₂.

Переведем теперь дробную часть:

0,482=0+0,96 (Х_-1=0)

0,962=1+0,92 (Х_-2=1)

0,922=1+0,84 (Х_-3=1)

0,842=1+0,68 (Х_-4=1)

0,682=1+0,36 (Х_-5=1)

0,362=0+0,72 (Х_-6=0)

0,722=1+0,44 (Х_-7=1)

и т.д.

Следует иметь в виду, что дробная часть числа в новой системе счисления может иметь большое количество разрядов и даже оказаться бесконечной. Поэтому нет необходимости находить все разряды, а можно ограничиться лишь их частью исходя из требований точности представления числа. В нашем случае ограничимся семью разрядами дробной части и запишем ее с первого результата умножения 0,48₁₀=0,0111101₂. Окончательно получается 125,48₁₀=1111101,0111101₂.

Для представления числа с основанием системы счисления S средствами цифровой вычислительной техники необходимо, чтобы электронное устройство могло формировать на выходе и воспринимать на входе S различных состояний электрических сигналов. При этом каждый разряд должен обрабатываться своим отдельным узлом данного устройства. Поэтому, чем выше основание системы счисления, в которой представляются обрабатываемые числа, тем меньше требуется разрядов и, следовательно, узлов электронного устройства. С другой стороны, количество различных состояний электрических сигналов возрастает. Так для представления десятичных чисел средствами электронной техники необходимо, чтобы электронный узел был способен различать десять состояний (уровней напряжения или тока) электрического сигнала. Реализация такого устройства является достаточно сложной технической задачей. Кроме того, такое устройство будет помехонезащищенным из-за сложности идентификации одного из десяти параметров электрического сигнала, что повысит вероятность ошибочного результата обработки. Требования помехоустойчивости в вычислительных устройствах имеют больший приоритет перед аппаратными затратами и, поэтому, наибольшее распространение получила двоичная система счисления, оперирующая с двумя разрядными коэффициентами 0 и 1. Один разряд двоичного кода носит название бит. Группа разрядов из восьми бит называется байтом. Логическому нулю в цифровых вычислительных устройствах обычно соответствует электрический сигнал с низким уровнем напряжения (тока), а логической единице – с высоким.

Кроме двоичной в цифровых вычислительных устройствах часто применяются восьмеричная, шестнадцатеричная и десятичная системы счисления. В десятичной системе счисления осуществляется, как правило, ввод и вывод информации в цифровые вычислительные устройства с помощью специальных преобразователей с целью упрощения человеко-машинного взаимодействия. Восьмеричная и шестнадцатеричная системы счисления используются в основном из-за компактности записи чисел и удобства перевода двоичных кодов в восьми- и шестнадцатеричные. Для записи шестнадцатеричных чисел используются шестнадцать знаков - десять арабских цифр от 0 до 9 для записи первых десяти цифр и символы латинского алфавита от A до F для записи оставшихся шести цифр от 10 до 15 (A соответствует цифре 10, В - 11, C - 12, D - 13, E - 14, F - 15). Так, например, шестнадцатеричное число 4D₁₆ соответствует десятичному числу 77₁₀, так как .

Достоинство восьмеричной и шестнадцатеричной форм записи числа – это легкость перевода из двоичной формы в восьмеричную (шестнадцатеричную) и наоборот. Так как 8=2³ и 16=2⁴, то для записи одного разряда восьмеричного числа требуются три разряда двоичного, а одного разряда шестнадцатеричного – четыре разряда двоичного. Например, чтобы перевести шестнадцатеричное число 1ED9,0A₁₆ в двоичную форму, необходимо каждую шестнадцатеричную цифру представить эквивалентным четырехразрядным двоичным числом: 1₁₆=0001₂, E₁₆=1110₂, D₁₆=1101₂, 9₁₆=1001₂, 0₁₆=0000₂, A₁₆=1010₂. В итоге, отбросив три незначащих нуля перед первой единицей, получим число 1111011011001,00001010₂.

Для ввода и вывода десятичной информации в цифровые вычислительные устройства обычно используется не сама десятичная система счисления, а двоично-десятичная, которая позволяет представить десятичные числа с использованием двоичных кодов. В этой форме каждая цифра десятичной записи числа изображается в виде четырехразрядного двоичного числа (двоичной тетрады). Таким образом, двоично-десятичная система счисления является как бы ограниченным до первых десяти символов вариантом шестнадцатеричной системы. Например, чтобы представить десятичное число 174,83₁₀ в двоично-десятичной форме необходимо, как и в случае с шестнадцатеричной системой счисления, каждый разряд десятичного числа перевести в четырехразрядный двоичный код: 1₁₀=0001₂, 7₁₀=0111₂, 4₁₀=0100₂, 8₁₀=1000₂, 3₁₀=0011₂. Окончательно число будет иметь вид 000101110100,10000011_2-10. В записи двоично-десятичного числа незначащие нули принято оставлять, поскольку оно всегда является формой представления десятичного числа и обрабатывается по группам из четырех разрядов. В связи с этим, нельзя путать двоично-десятичную форму записи числа с двоичной записью того же числа. В первом случае основание системы счисления остается равным десяти - только разрядные коэффициенты при основании выражены в двоичной форме. Для удобства в таблице 1.1 приведены различные формы записи двадцати чисел натурального ряда.

Таблица 1.1.

Десятичное число	Двоичное число	Восьмеричное число	Шестнадцате-ричное число	Двоично-десятичное число
0	0	0	0	0000
1	1	1	1	0001
2	10	2	2	0010
3	11	3	3	0011
4	100	4	4	0100
5	101	5	5	0101
6	110	6	6	0110
7	111	7	7	0111
8	1000	10	8	1000
9	1001	11	9	1001

Продолжение таблицы 1.1.

Десятичное число	Двоичное число	Восьмеричное число	Шестнадцате-ричное число	Двоично-десятичное число
10	1010	12	A	00010000
11	1011	13	B	00010001
12	1100	14	C	00010010
13	1101	15	D	00010011
14	1110	16	E	00010100
15	1111	17	F	00010101
16	10000	20	10	00010110
17	10001	21	11	00010111
18	10010	22	12	00011000
19	10011	23	13	00011001
20	10100	24	14	00100000

1-2. Числовые коды, представление отрицательных чисел.

Кодом называется любое обозначение, отличное от общепринятого. Общепринято, например, положительные числа отмечать знаком «+» (или вообще не указывать знак), а отрицательные числа отмечать знаком «-». Числа разного знака необходимо уметь изображать состояниями элементов цифровой электроники. Для изображения знака числа вводится дополнительный знаковый разряд, причем состоянию «0» этого разряда соответствует знак «+», а состоянию «1» - знак «-».Такое изображение чисел со знаком называется прямым кодом [X]_пр числа Х. Поскольку разрядность цифровых вычислительных устройств обычно кратна одному байту, то под знаковый разряд отводится крайний левый бит в старшем байте. Таким образом, если для представления чисел в цифровом устройстве предусмотрен один байт (8 бит), то знаковым будет восьмой разряд байта, а оставшиеся семь будут отведены для значащих разрядов числа, что сделает возможным оперировать с целыми числами в диапазоне от –127 до +127. Если же разрядность цифрового устройства 2 байта (16 бит), то знаковым будет шестнадцатый разряд, а значащими окажутся разряды с первого по пятнадцатый и т.д. Таким образом, прямой код целого числа образуется по правилу: если число X положительно, то [X]_пр=0, X₁, X₂, ... X_n; если число X отрицательно, то [X]_пр=1, X₁, X₂, ... X_n, где n =8, 16 и т.д.

Обратный код числа образуется инвертированием всех разрядов прямого кода числа, кроме знакового. Операция инвертирования заключается в поразрядной замене нулей на единицы и единиц на нули. Таким образом, если число X положительно, то [X]_обр=0, , , ... ; если число X отрицательно, то [X]_обр=1, , , ... , где n = 8, 16 и т.д.

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

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

записывают обратный код исходного числа;

прибавляют единицу к младшему разряду.

Дополнительный код числа будем обозначать как [X]_доп. При этом, если в результате вычитания в знаковом разряде получается единица, то результат отрицательный и представлен в дополнительном коде, а если нуль – то положительный и представлен в прямом коде. В таблице 1.2 приводится пример кодов некоторых положительных и отрицательных десятичных чисел.

Таблица 1.2.

Десятичное представление	Двоичное представление	Представление в прямом коде [X]пр	Представление в обратном коде [X]обр	Представление в дополнительном коде [X]доп
23	10111	00010111	01101000	00010111
-1	-1	10000001	11111110	11111111
-17	-10001	10010001	11101110	11101111
-70	-1000110	11000110	10111001	10111010

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

В принципе, логика выполнения арифметических операций в двоичной системе счисления наиболее проста. Это наглядно видно на примере сравнения таблиц умножения десятичных цифр с одной единственной таблицей умножения двоичных цифр, имеющей вид: 0´0=0; 0´1=0; 1´0=0; 1´1=1.

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

В цифровых вычислительных устройствах для реализации операций быстрого деления и умножения числа на 2ⁿ, где n – целое положительное число, используются операции сдвига двоичного кода числа вправо или влево. Сдвинуть двоичный код влево на один разряд соответствует умножению его на 2, а вправо – делению на 2. Например, десятичному числу 8 соответствует двоичный код 00001000, а десятичному числу 16, равному удвоенному значению 8, двоичный код 00010000. Очевиден сдвиг кода влево на один разряд. Десятичному же числу 4, вдвое меньшему 8, соответствует двоичный код 00000100. Налицо сдвиг вправо на один разряд двоичного кода. При проектировании цифровых умножителей на произвольный коэффициент используется алгоритм традиционного умножения столбиком.

1-3. Определение функции алгебры логики.

Для анализа и синтеза цифровых электронных схем широко используется математический аппарат алгебры логики, или булевой алгебры, разработанной в середине XIX века ирландским математиком Дж. Булем. Основным понятием алгебры логики является понятие переключательной функции или булевой функции алгебры логики (ФАЛ). Функцией алгебры логики n переменных называется такая функция, которая принимает только два возможных значения - 0 или 1, как и переменные, от которых эта функция зависит. Для n переменных возможно 2ⁿ различных значений переключательной функции f. Если заданы все 2ⁿ значений функции, то она называется полностью определенной. Если же часть значений функции f не задана, то такая функция носит название неопределенной или частично определенной.

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

Таблица 1.3.

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	0
5	1	0	1	0
6	1	1	0	0
7	1	1	1	1

Конкретная комбинация значений аргументов носит название набора. Каждый набор имеет индекс j, численно равный десятичному эквиваленту двоичного числа.

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

Таблица 1.4.

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	X×Y; X&Y; XÙY
f2		0	0	1	0	функция запрета по Y	XDY
f3		0	0	1	1	переменная X	X
f4		0	1	0	0	функция запрета по X	YDX
f5		0	1	0	1	переменная Y	Y
f6		0	1	1	0	функция неравнозначности (сложение по модулю два)	XÅY
f7		0	1	1	1	дизъюнкция X и Y	XÚY, X+Y
f8		1	0	0	0	стрелка Пирса	X¯Y
f9		1	0	0	1	функция равнозначности	X~Y
f10		1	0	1	0	инверсия Y
f11		1	0	1	1	импликация от X к Y	X®Y
f12		1	1	0	0	инверсия X
f13		1	1	0	1	импликация от Y к X	Y®X
f14		1	1	1	0	штрих Шеффера	XïY
f15		1	1	1	1	константа 1	1

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

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

,

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

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

,

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

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

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

Формула для любой СКНФ функции 3-х переменных будет иметь вид:

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

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

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

• переместительный закон XÚY=YÚX, X×Y=Y×X;

• сочетательный закон XÚ(YÚZ)=(XÚY)ÚZ, X×(Y×Z)=(X×Y)×Z;

• распределительный закон X×(YÚZ)=X×YÚX×Z, X×YÚZ=(XÚZ)×(YÚZ);

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

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

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

X×X=X, 1×X=X, 0×X=0;

• закон склеивания XÚ , ;

• закон поглощения Y×XÚX=X; (YÚX)×X=X;

• константы

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

f(A,B,C)= (0,2,3,7)= (0,2,3,7);

f(A,B,C)= (1,4,5,6)= (1,4,5,6).

В случае автоматизированного проектирования логических схем электронных цифровых устройств на ЭВМ ФАЛ удобно записывать в виде кубических комплексов. Такая форма в силу ограниченного числа символов позволяет формализовать запись логических функций большого числа переменных. Каждый набор переменных представляется в виде n-мерного вектора, где n – количество входных переменных. Вершины этого вектора образуют вершины n-мерного куба. Если функция задана тремя переменными, то она образует трехмерный куб, который легко представляется геометрически в виде объемной фигуры. Все единичные вершины куба, в которых функция f принимает значение «1», образуют множество нулевых кубов, называемое нулевым кубическим комплексом К₀. Нулевой кубический комплекс записывается набором двоичных кодов входных переменных, для которых функция принимает единичные значения. Вершины, расположенные на концах ребер куба, называются соседними и отличаются только одной переменной. Если два куба, для которых функция равна «1», являются соседними, то они образуют куб более высокого порядка. Так, если два нулевых куба комплекса К₀ являются соседними, т.е. отличаются только одной переменной, то они образуют единичный куб, геометрически представляющий ребро исходного n-мерного куба. Набор единичных кубов образуют единичный кубический комплекс К₁. Записывается единичный кубический комплекс в виде набора двоичных кодов совпадающих переменных, а вместо несовпадающих проставляются прочерки. Аналогично соседние единичные кубы, отличающиеся только одной переменной, образуют двоичные кубы, набор которых в свою очередь образуют двоичный кубический комплекс К₂ и т.д.

Рассмотрим запись ФАЛ в виде кубических комплексов на примере функции, заданной таблицей 1.3. Поскольку функция определяется тремя переменными, то ее можно представить трехмерным кубом (рис. 1.1). Вершины этого куба сформированы таким образом, чтобы каждая переменная, входящая в уравнение, располагалась в одной оси базиса трехмерного пространства X-Y-Z. В оси Х располагается переменная А, в оси Y – переменная В и в оси Z – переменная С. Окружностями отмечаем вершины куба, в которых функция принимает значения единицы. Эти вершины (нулевые кубы) образуют нулевой кубический комплекс К₀=(000, 010, 011, 111). Из рисунка наглядно видны соседние вершины, в которых нулевые кубы отличаются только одной переменной. Ребро исходного куба, образованное соседними вершинами, выделяем толстой линией. Эти ребра образуют единичные кубы, в записи которых вместо несовпадающих переменных ставятся прочерки. Набор единичных кубов образует единичный кубический комплекс К₁=(0-0, 01-, -11).

Рис. 1.1. Кубические комплексы функции, заданной таблицей 1.3.

Единичный кубический комплекс для рассмотренного выше примера является максимально возможным. Для некоторых произвольных функций трех переменных может оказаться возможным выделение двоичных кубов, образующих двоичный кубический комплекс К₂. Геометрически такие кубы образовывают грани исходного трехмерного куба. В записи двоичных кубов будет присутствовать значение одной совпадающей переменной и два прочерка для несовпадающих, например, (-1-). Для функции n переменных существует теоретическая вероятность нахождения (n-1) кубических комплексов. Совокупность всех кубических комплексов образует кубический комплекс ФАЛ: К(f)= (К₀, К₁, …, К_m), где m – максимально возможный кубический комплекс функции n переменных.

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

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

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

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

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

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

• стрелка Пирса;

• штрих Шеффера.

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

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

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

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

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

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

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

Поскольку для ФАЛ трех переменных диаграмма представляет как бы развертку цилиндра, разрезанного по , поэтому единицы, расположенные по краям диаграммы (например, как это изображено на рис. 1.3) считаются расположенными рядом.

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

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

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

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

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

В качестве примера найдем МДНФ функции, заданной таблицей 1.3. Диаграмма Вейча этой функции представлена на рис. 1.4. Из рисунка видно, что в результате склеивания образовались две простые импликанты: и . Импликанта участвует в склеивании с конъюнкциями и и поэтому не является простой. Таким образом, полученная МДНФ имеет вид . В истинности полученного выражения можно убедиться путем подстановки всех наборов переменных А, В и С.

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

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

Минимизация ФАЛ методом диаграмм Вейча и карт Карно в силу своей наглядности широко используется при ручном процессе минимизации логических функций от небольшого количества переменных, обычно не превышающего пяти. В случае, когда количество переменных больше, необходимо использовать методы, характеризующиеся однозначностью алгоритма, что позволяет автоматизировать процесс минимизации на ЭВМ. Одним из таких методов является метод Квайна и Мак-Класки. Суть метода состоит в следующем:

• все конституенты единицы, записанные в виде двоичных кодов, разбиваются на группы, содержащие одинаковое количество единиц;

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

• все склеенные конституенты, образующие импликанты, отмечают каким-либо признаком, например звездочкой;

• не отмеченные при склеивании импликанты являются простыми и заносятся в импликантную матрицу, в первой строке которой записываются все конституенты единицы функции f, а в первом столбце – все простые импликанты;

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

• ищутся столбцы импликантной матрицы, имеющие только по одной звездочке;

• соответствующие этим звездочкам простые импликанты называются базисными и образуют ядро функции f и обязательно входят в МДНФ;

• рассматриваются столбцы импликантной матрицы и выделяются те, которые содержат более одной звездочки;

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

Рассмотрим пример минимизации функции f, заданной таблицей 1.3 методом Квайна и Мак-Класски. Функция принимает единичные значения при следующих значениях переменных А, В и С - 000, 010, 011, 111, которые и образуют конституенты единицы. Эти конституенты можно записать в четыре группы по количеству в них единиц:

группа 0: 000 *;

группа 1: 010 *;

группа 2: 011 *;

группа 3: 111 *.

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

группа 1: 0-0;

группа 2: 01-;

группа 3: -11.

Дальнейшее склеивание соседних импликант возможно только при наличии прочерка в одинаковых позициях. В нашем примере это условие не выполняется и, поэтому, образованные импликанты являются простыми. Из полученных простых импликант составляется импликантная матрица, в первой строке которой записываются все конституенты единицы, а в первом столбце – все простые импликанты. Звездочкой отмечаются все пересечения строк и столбцов, в которых импликанты покрывают конституенты единицы.

Простые импликанты	Контституены единицы
	000	010	011	111
0-0	*	*
01-		*	*
-11			*	*

В матрице находим столбцы, содержащие по одной звездочке. Это столбцы с конституентами 000 и 111. Одиночным звездочкам в них соответствуют импликанты 0-0 и –11. Эти импликанты являются базисными, образуют ядро логической функции и обязательно входят в состав МДНФ. Далее выделяются столбцы, содержащие более одной звездочки. Такими столбцами являются столбцы с контитуентами 010 и 011. Поскольку эти конституенты покрываются импликантами 0-0 и –11 из ядра функции, то импликанта 01- является лишней и в МДНФ не входит. В результате имеем в составе МДНФ импликанты 0-0 и-11. Заменив двоичные коды полученных импликант на обозначения переменных в прямом и инверсном виде, получим окончательную запись МДНФ функции: , что соответствует результату минимизации методом диаграмм Вейча.

Рассмотрим пример минимизации ФАЛ четырех переменных методом Квайна и Мак-Класски. Пусть задана функция в виде последовательности десятичных чисел:

.

Запишем конституенты единицы функции f в виде двоичных кодов:

.

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

группа 0: ;

группа 1: 0001 **, 0010 ***;

группа 2: 0011 ****, 0101 **, 0110 **, 1010 ***;

группа 3: 0111 ****, 1011 ***, 1110 **;

группа 4: 1111 ***.

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

группа 1: 00-1 *, 0-01 *, 001- **, 0-10 **, -010*;

группа 2: 0-11 ***, -011 **, 01-1 *, 011- **, 101- *, 1-10 **;

группа 3: -111 *, 1-11 **, 111- *.

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

группа 1: 0--1, 0--1, 0-1-, -01-, 0-1-, --10, -01-;

группа 2: --11, --11, -11-, 1-1-, 1-1-.

Перепишем, оставив только неповторяющиеся импликанты:

группа 1: 0--1, 0-1- *, -01- *, --10 *;

группа 2: --11 *, -11- *, 1-1- *.

Продолжим склеивание:

Группа 1: --1-, --1-, --1-.

Не отмеченные звездочками импликанты являются простыми: 0--1 и --1-. Построим импликантную матрицу:

Простые импликанты	Контституены единицы
	0001	0010	0011	0101	0110	0111	1010	1011	1110	1111
0--1	*		*	*		*
--1-		*	*		*	*	*	*	*	*

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

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

а) б)

Рис. 1.5. Пример минимизации частично определенной ФАЛ.

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

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

2. Отнимите из числа 57₁₀ число 83₁₀ и из числа 83₁₀ число 57₁₀ по правилам двоичной арифметики, используя дополнительные коды и операцию сложения.

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

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

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