Сложение двоично-десятичных чисел.

Так как в двоично-десятичном коде используются только 10 возможных комбинаций 4-х битового поля вместо 16, существуют запрещённые комбинации битов: 1010, 1011, 1100, 1101, 1110, 1111.

Поэтому, при сложении и вычитании действуют следующие правила:

• При сложении двоично-десятичных чисел каждый раз, когда происходит перенос бита в старший полубайт, необходимо к полубайту, от которого произошёл перенос, добавить корректирующее значение 0110 (= 6₁₀ = 16₁₀ — 10₁₀: разница количеств комбинаций полубайта и используемых значений).

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

• При вычитании двоично-десятичных чисел, для каждого полубайта, получившего заём из старшего полубайта, необходимо провести коррекцию, отняв значение 0110.

Глава 2. Логические основы цифровой схемотехники

И так, что же из себя представляют логические ноль(ложь) и единица(истина) на схеме? Это некоторый уровень напряжения, например, для КМОП логики 0 – что-то в районе 0 В, 1 – напряжение питания.

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

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

Булевой, или переключательной, функцией называется функция, принимающая значения из множества логических сигналов (0 и 1), аргументы которой также принадлежат данному множеству. Пусть имеется n переменных, каждая из которых может принимать значения 0 или 1, тогда общее количество комбинаций значений этих переменных равно 2ⁿ, а количество различных функций от n переменных ₂2ⁿ. Таким образом, для одной переменной Х существует 4 булевых функции (Х, не Х, константы 0, 1), для двух переменных – 16 возможных функций. Задавать булевы функции можно трёмя способами:

1. Табличный – перечисляются все возможные значения переменных и соответствующие им значения функции (таблица истинности)

X1	X2	X3	F(x1,x2,x3)
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	0

Рис. 3

2. Г рафический – рисуется многомерный куб (от одной переменной – отрезок, от двух – квадрат, от трёх – куб и тд.), на данном кубе отмечаются вершины, где функция равняется 1.

Рис. 4

3. Аналитический – формулой. .

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

Рис. 5

Р ис. 6

Рис. 7

На рис. 5 даны таблицы истинности булевых функций от двух переменных, на рис. 6 – условные схемотехнические обозначения наиболее популярных функций, рис. 7 – названия булевых функций от двух переменных и эквивалентные обозначения.

О сновы синтеза циф­ровых логических устройств

Рис. 8

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

Представление булевых функций

Любую булеву функцию можно представить в виде КНФ, ДНФ, СКНФ, СДНФ и полинома Жигалкина, доказательство данного утверждения выходит за рамки работы.

Простой конъюнкцией называется конъюнкция конечного набора переменных или их отрицаний, причём каждая переменная встречается не более одного раза.

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

Например:

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

Например:

КНФ — это конъюнкция простых дизъюнкций.

СКНФ относительно некоторого заданного конечного набора переменных, называется такая КНФ, у которой в каждую дизъюнкцию входят все переменные данного набора, причём в одном и том же порядке.

Получить из КНФ эквивалентную ДНФ можно раскрыв скобки, верно и обратное.

Полином Жегалкина — это форма представления логической функции в виде полинома с коэффициентами вида 0 и 1, в котором в качестве произведения используется операция конъюнкции («И», AND), а в качестве сложения — сложение по модулю 2 (исключающее «ИЛИ», XOR).

Построение СДНФ

1. Построение по таблице истинности

1. Найти строки в ТИ, где f = 1.

2. Переписать все переменные в виде конъюнкции, причём, те переменные, где в строке значится 1 включить в конъюнкцию без изменений, а те, что равны 0 – инвертировать.

3. Составить дизъюнкцию из конъюнкций п.2.

2. Получение из ДНФ.

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

Построение СКНФ (если в таблице истинности функция чаще принимает значение1, чем 0 – имеет смысл использовать СКНФ, т. к. получится короче).

1. Построение по таблице истинности

1. Найти строки в ТИ, где f = 0.

2. Переписать все переменные в виде дизъюнкции, причём, те переменные, где в строке значится 0 включить в конъюнкцию без изменений, а те, что равны 1 – инвертировать.

3. Составить конъюнкцию из дизъюнкций п.2.

2. Получение из КНФ.

Если некоторое произведение КНФ не содержит какой-либо переменной (пусть x_k), то необходимо дизъюнктивно добавить в нее произведение этой переменной и ее отрицания (т.е. ) и применить дистрибутивный закон.

Примеры:

Пример получения СДНФ по таблице – рис. 3 и ниже п.3 – формула.

Переход КНФ в ДНФ:

П ереход от ДНФ к СДНФ:

Получение полинома Жегалкина из ДНФ:

Учитывая 4 тождества:

Получим: