Двоичные числа
Цифровые устройства работают с двоичными числами. Двоичная система счисления или система с основанием 2
использует только цифры 0
или 1
. Эти двоичные числа называют битами (от binary digit
).
Система счисления - это код, в котором используют специальные символы для обозначения количества каких-либо объектов.
В повседневной деятельности мы пользуемся десятичной системой счисления, которая содержит десять цифр (от 0
до 9
). Такую систему ещё называют системой счисления с основанием 10
. Двоичную систему называют системой счисления с основанием 2
.
Системы счисления характеризуются таким понятием, как значение позиции или вес разряда. Например, десятичное число 2547
можно представить как сумму 2000+500+40+7=2547
. Составляющие этой суммы и являются весами разрядов.
Рассмотрим двоичное число 1101
("один - один - ноль - один"). В табл.10.1 приведены значения позиций и десятичный эквивалент двоичного числа.
Таблица 10.1. Значения позиций двоичных чисел
Бит единицы двоичного числа в табл.10.1 называется младшим битом (МБ), бит восьмёрки - старшим битом (СБ). Табл.10.1 даёт представление о том, как преобразовать двоичное число в его десятичный эквивалент: необходимо определить значение позиций (вес разряда) и просуммировать те из них, у которых соответствующее значение разряда двоичного числа равно 1
.
Преобразование двоичного числа 1011
0110
в его десятичный эквивалент показано в табл.10.2.
Таблица 10.2. Двоично-десятичное преобразование
Основания системы счисления называются индексами:
1011 01102=18210
.
Сделаем обратное преобразование: десятичное число преобразуем в его двоичный эквивалент.
Из рис.10.1 видно, что сначала десятичное число172
делится на 2
, что даёт число 86
и остаток 1
. Остаток 1
будет являться младшим битом (МБ) двоичного числа. Затем число 86
делится на 2
и т.д., пока не получится результат равным 0
. Последний получаемый остаток от деления будет являться старшим битом (СБ) двоичного эквивалента, т.о. 17310=1010 11012
.
Шестнадцатеричные числа
Шестнадцатеричная система счисления или система с основанием 16
, использует 16
символов от 0
до 9
и A, B, C, D, E, F. В табл.10.3 показаны десятичные числа от 0
до 15
, а также двоичные и шестнадцатеричные эквиваленты.
Таблица 10.3.
Десятичные числа и их двоичные и шестнадцатеричные эквиваленты
| Десятичное | Шестнадцатеричное | Двоичное |
| 0 | 0 | 0000 |
| 1 | 1 | 0001 |
| 2 | 2 | 0010 |
| 3 | 3 | 0011 |
| 4 | 4 | 0100 |
| 5 | 5 | 0101 |
| 6 | 6 | 0110 |
| 7 | 7 | 0111 |
| 8 | 8 | 1000 |
| 9 | 9 | 1001 |
| 10 | A | 1010 |
| 11 | B | 1011 |
| 12 | C | 1100 |
| 13 | D | 1101 |
| 14 | E | 1110 |
| 15 | F | 1111 |
Из табл.10.3 видно, что каждый шестнадцатеричный символ может быть представлен сочетанием четырех бит. Например, представлением двоичного числа 0111
1101
в шестнадцатеричной системе является число 7D
, поскольку первые четыре бита соответствуют 7
, а оставшиеся четыре бита равны D, то есть 0111 11012 = 7
D16
.
Из этого примера можно вывести общее правило перевода двоичных чисел в шестнадцатеричные: надо, начиная с младшего бита разделить двоичное число на группы из 4
бит, а затем заменить каждую такую группу шестнадцатеричной цифрой.
Например, задано двоичное число 101110
. Разделим это число на группы из 4
бит, начиная с младшего бита и на основании табл. 10.3 произведем замены этих групп шестнадцатеричными цифрами:
11102 =
E; 00102 = 2
;
1011102 = 2
E16
.
Рассмотрим обратное преобразование: шестнадцатеричное число преобразуем в двоичное. В таком преобразовании каждая шестнадцатеричная цифра заменяется своим двоичным эквивалентом из 4
бит на основании табл.10.3.
Например, шестнадцатеричное число 5
A преобразуется в число 010110102
, то есть 5
A16 = 10110102
.
Процедура преобразования шестнадцатеричного числа 3
A5
D в десятичное число показано в табл.10.4.
Таблица 10.4.
Преобразование шестнадцатеричного числа в десятичное
Из табл.10.4 видно, что получаемое десятичное число содержит: 13
(D16
) единиц, 5
чисел 16
, 10
(A16
) чисел 256
и 3
числа 4096
. Каждая цифра шестнадцатеричного числа умножается на соответствующее значение позиции и эти произведения складываются. Таким образом, 3
A5
D16
= 1494110
.
Сделаем обратное преобразование. Процесс преобразования десятичного числа в шестнадцатеричное похож на преобразование, полученное на рис.10.1.
Рис.10.2 показывает, что исходное десятичное число 1438210
делится на 16
, что дает результат 89810
и остаток 1410
, который преобразуется в шестнадцатеричный эквивалент 1410
= Е16
и является младшим разрядом (МР) получаемого числа. Процесс деления продолжается и последний остаток от деления 310 = 316
становится старшим разрядом (СР) результата.
Восьмеричные числа
Восьмеричная система содержит восемь цифр от 0
до 7
и является системой с основанием 8
. В табл.10.5 показаны десятичные, восьмеричные и двоичные числа.
Таблица 10.5. Десятичные, восьмеричные и двоичные числа
Рассмотрим различные преобразования. Преобразуем двоичное число 10 101 001 100
в восьмеричный эквивалент. Начиная с младшего бита двоичное число разделяем на группы из 3
бит. Затем используя табл.10.5, преобразуем каждую группу в восьмеричную цифру.
Двоичное число 010
101 001 100
Восьмеричное число 2
5 1 4
Таким образом 101010011002=25148
.
Осуществим обратное преобразование. При этом каждая восьмеричная цифра заменяется двоичным эквивалентом на основании табл.10.5.
Например, 57348=101 111 011 1002
.
Восьмеричное число 5 7 3 4
Двоичное число 101 111 011 100
Преобразование восьмеричного числа в десятичное показано в табл.10.6.
Таблица 10.6. Восьмерично-десятичные преобразования
В табл.10.6 восьмеричное число 3416
преобразуется в десятичное, которое содержит 6
единиц, 1
восьмерку, 4
числа 64
и 3
числа 512
. Каждая цифра восьмеричного числа умножается на соответствующее значение позиции и эти произведения складываются. В результате получаем 34168=180610
.
Преобразуем десятичное число 4518
в восьмеричный эквивалент. Сначала число 4518
делится на 8
. Что дает результат 564
и остаток 6
. Который ставится младшим разрядом (МР) восьмеричного числа (рис.10.3). Последний остаток от деления десятичного числа 1
на 8
дает остаток 1
, который является старшим разрядом (СР) восьмеричного эквивалента. Т.о. 451810=106468
.
Двоичные логические элементы
Используемые для обработки цифровых сигналов устройства называются логическими элементами. Те элементы, что оперируют с двоичными числами называются двоичными логическими элементами. Для идентификации логических элементов используют логические символы. В табл.10.7 приведены семь основных логических элементов цифровых схем.
Таблица 10.7. Основные логические элементы
В табл.10.7 для графического обозначения логических элементов приведены две системы - система, рекомендуемая Международной Электротехнической Комиссией (МЭК), и американская система milspec. Для описания связи входов и выходов логических элементов используются булевы функции. Основы математической логики были заложены английским математиком Дж. Булем (1815 - 1864). В табл.10.7 для задания булевых функций использовались четыре логические функции:
1) функция НЕ или инверсия (отрицание) Y=
2) функция И (конъюнкция) Y=A·B=AB
3) функция ИЛИ (дизъюнкция) Y=A+B=AB
4) функция исключающее или Y=AB
Для перечисленных логических функций справедлив ряд аксиом (тождеств) и законов, основные из которых приведены в табл.10.8.
Таблица 10.8. Основные аксиомы и законы булевой алгебры
<
С помощью аксиом и законов булевой алгебры (табл.10.8) можно упорядочивать и упрощать сложные логические функции сумм и произведений таким образом, что получается минимальная сумма или минимальное произведение.
Построение комбинационных логических схем
Комбинационными называются функциональные узлы, логическое состояние выходов которых зависит только от комбинации логических сигналов на входах в данный момент времени.
Состояние входов и выходов логической схемы может быть описано таблицей истинности или булевым выражением. В табл.10.7 были приведены таблицы истинности и булевы выражения для основных логических элементов.
Булево выражение в дизъюнктивной нормальной форме — это функция, представляющая собой сумму, каждое слагаемое которой является произведением всех входных переменных или их инверсий:
Данное выражение можно упростить, используя аксиомы и законы булевой алгебры (табл.10.8), и получить так называемую минимальную сумму:
поскольку и
Конъюнктивная нормальная форма - это функция, представляющая собой произведение членов, каждый из которых является суммой всех переменных или их инверсий:
Данное выражение можно упростить и получить минимальное произведение:
т.к. и
Рассмотрим как можно преобразовать информацию, представленную в форме таблицы истинности, в булево выражение. В табл.10.9 показаны все возможные комбинации трех входов (A,B,C) и выхода (Y). Из табл.10.9 видно, что только три из восьми возможных комбинаций двоичных сигналов на входах А,В,С дают на выходе логическую 1
. Эти комбинации представлены выражениями: (читается как: не С и не В и А), и . В булевом выражении эти три комбинации связываются логической функцией или т.о. булево выражение имеет вид:
Таблица 10.9. Таблица истинности
Заметим, что полученное булево выражение можно упростить:
Это выражение содержит две комбинации входов, но в столбце выхода (табл.10.9) имеется три логические 1
.
Легко произвести обратное преобразование - по булеву выражению построить таблицу истинности. Для выражения:
в табл.10.10, находим комбинации входов А,В,С и проставляем логические 1
в столбце значений выхода.
Таблица 10.10. Таблица истинности
Построим логическую схему для булева выражения, соответствующую табл.10.9. На выходе логической схемы должен быть логический элемент ИЛИ (OR). Кроме этого, схема (рис.10.4) содержит два элемента И (AND) и два инвертора (NOT).
На рис.10.5 представлена логическая схема для табл.10.10.
Рассмотрим булево выражение:
Для реализации логической схемы, соответствующей этому выражению, необходимы три элемента И, два инвертора и один элемент ИЛИ с тремя входами (рис.10.6).
Составим таблицу истинности для логической схемы, изображённой на рис.10.6.
Таблица 10.10. Таблица истинности
Анализ табл.10.10. показывает, что она соответствует таблице истинности логического элемента ИЛИ (табл.10.7). Булево выражение для элемента ИЛИ имеет вид: A+B=Y
, а логическая схема изображена на рис.10.7.
Приведённый пример показывает, что для реализации исходного булева выражения нет необходимости использовать шесть логических элементов (рис.10.6). Используя упрощения булева выражения можно получить более простую логическую схему (рис.10.7.). Для упрощения булевых выражений можно воспользоваться методами, использующими карты Карно.
Карты Карно
В 1953 г. Морис Карно предложил систему графического представления и упрощения булевых выражений. На рис.10.8 приведена карта Карно для двух входных переменных. Логические члены представлены в ней в отдельных клетках. Для двух переменных получается 22 = 4
комбинации, поэтому карта состоит из четырех клеток
На рисунке показано, какие поля карты относятся к переменным, а какие — к их дополнениям. Переменные размещаются на карте таким образом, что при переходе из одной клетки в соседнюю клетку, как по горизонтали так и по вертикали, меняется только одна переменная. Если требуется получить карту Карно для какого - либо выражения, то сначала это выражение записывается в дизьюктивной нормальной форме. Каждый член, который появляется в этой форме, задаётся на карте с помощью 1
в соответствующей клетки. Затем соседние единицы объединяются в один контур группами по две, четыре или восемь единиц. Построение контуров продолжается до тех пор пока все единицы не окажутся внутри контуров. При этом каждый контур представляет собой новый член упрощённого булева выражения.
Рассмотрим пример. Пусть исходное булево выражение имеет вид:
Заполним карту Карно (рис.10.9.), разместив логические единицы в тех квадратах, которым соответствуют произведению в исходном булевом выражении.
Объединим логические 1
в два контура. Это означает, что упрощённое выражение будет состоять из двух членов, связанных функцией ИЛИ. Рассмотрим верхний контур (рис.10.9). Заметим, что А здесь встречается в комбинации с В
и . Но в соответствии с аксиомами и законами булевой алгебры (табл.10.8.) В
и дополняют друг друга и их можно опустить. Т.о. верхний контур нам даст . Аналогично рассматриваем другой контур. В нём А
и дополняют друг друга и остаётся . В результате А
и объединяются функцией ИЛИ, что приводит к упрощённому булевому выражению:
При применении карт Карно для упрощения булевых выражений следует помнить, что каждый контур даёт в минимальную сумму один член, и при этом исключаются члены, дополняющие друг друга внутри контура.
Карта Карно для трех переменных приведена на рис.10.10.
Для трёх переменных имеется восемь квадратов, которые соответствуют восьми возможным комбинациям переменных. Для булева выражения:
заполненная карта Карно приведена на рис.10.10. Каждая группа из двух соседних единиц составляет один контур. Булево выражение в дизьюктивной нормальной форме будет содержать два члена. В нижний контур входят С
и , поэтому они опускаются. В верхнем контуре опускаются переменные В
и . Упрощенное булево выражение примет вид:
Карта Карно для четырёх переменных содержит 24 = 16
клеток (рис.10.12).
Рассмотрим булево выражение:
Заполненная карта Карно для данного выражения показана на рис.10.13. Группы из двух и четырёх единиц объединены конурами. Контур, содержащий две единицы, даёт возможность опустить D
и . В другом контуре, содержащем четыре единицы, есть возможность опустить D
, и А, . В результате упрощенное булево выражение примет вид:
Из рассмотренных примеров можно сделать вывод, что для упрощения булевых выражений с двумя, тремя и четырьмя переменными применяются одинаковые правила и чем больше размеры контуров, тем больше переменных можно опустить.
Рассмотрим основные правила объединения на картах Карно клеток, содержащих единицы, для булевых выражений не более чем с четырьмя переменными:
1) Объединяются две соседние клетки, в столбце или ряду (рис.10.9, 10.11, 10.13).
2) Объединяются четыре соседние клетки, составляющие квадраты (рис.10.13).
3) Объединяются клетки или пары клеток, крайние в столбце или рядах (рис.10.14). Для примера, на рис.10.14 исходное булево выражение имеет вид:
В результате упрощения получим:
4) Объединяются полные столбцы или ряды (рис.10.15). Для рис.10.15 исходное булево выражение:
Упрощённое выражение:
5) Объединяются пары рядом расположенных столбцов или рядов. Для рис.10.16 исходное булево выражение:
Упрощённое выражение: Y=A
.
6) Объединяются крайние столбцы или ряды. Для рис.10.17 исходное булево выражение:
Упрощённое выражение:
7) Объединяются угловые клетки. Рис.10.18. соответствует булеву выражению:
В результате упрощения получим:
Рассмотренные правила объединение клеток, содержащие 1
, показывают, что две смежные клетки уменьшают число переменных на одну (рис.10.9, 10.11, 10.13). Четыре клетки приводят к сокращению на две переменные (рис.10.15, 10.18). Для восьми клеток в минимальном члене остается только одна переменная (рис.10.16, 10.17). Объединение из 16
единиц уменьшает число переменных до нуля, т.е. в этом случае Y тождественно равен 1
. Единица, находящаяся в отдельной клетке, не приводит к сокращению числа переменных. (рис.10.19).
Следует обратить внимание, что при объединение клеток нужно охватывать наибольшее число 1
, причем получаемые контура могут пересекаться. Для рис.10.19 исходное булево выражение имеет вид:
Здесь можно построить три контура, что даст в упрощенном выражение три члена и одна единица не входит ни в один контур и поэтому даст ещё один член, содержащий четыре переменные. Упрощенное булево выражение примет вид:
Отметим, что существуют карты Карно для пяти и шести переменных, в которых помимо рассмотренных правил объединения клеток используются другие, дополнительные правила.