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

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

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

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

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

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

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

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

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

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

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

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

Таблица 4.5. Таблица истинности функции 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	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	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
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

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

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

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

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

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

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

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

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

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

• переместительный закон 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Ú , ;

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

• константы

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

,

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

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

,

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

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

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

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

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