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

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

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

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

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

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

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

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

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

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

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

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

Таблица 4.5. Таблица истинности функции 3-х переменных

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

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

Таблица 4.6. Переключательные функции двух переменных

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

Формула для любой СДНФ функции 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. Таблица истинности функции двух аргументов

Из приведенных в таблице элементарных функций свойством сохранения нуля обладают функции 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. Свойства элементарных функций

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

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

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

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

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

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

 

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

 

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

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

 

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

 

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

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

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

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

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

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

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

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

 

 

	Рис. 4.7.4. Карты Карно для функций 3-х и 4-х переменных

 

 

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

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

 

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

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

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

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

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

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

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

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

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

 

Предыдущая12345678910111213141516Следующая