Цифровые устройства (цифровые автоматы) обычно делятся на два
класса: автоматы без памяти (однотактные автоматы, комбинационные схемы) и автоматы с памятью (многотактные автоматы). Комбинационные схемы составляют основу дискретных вычислительных и
управляющих устройств. Они могут выполнять как самостоятельные
функции: преобразователи кодов, дешифраторы и т. п., – так и входить в
состав цифровых автоматов с памятью, реализуя функции переключения элементов памяти в новые состояния, выработку логических и управляющих сигналов. Сами элементы памяти могут быть построены в
виде комбинационных схем с обратными связями.
В настоящем учебном пособии в краткой форме изложены основные
понятия и методы построения однотактных цифровых устройств контроля и управления, логика работы которых описывается булевыми функциями. Булевы преобразования двоичных последовательностей выделены в самостоятельный раздел, в котором описаны возможные области применения булевых преобразований при решении некоторых задач
защиты информации.
класса: автоматы без памяти (однотактные автоматы, комбинационные схемы) и автоматы с памятью (многотактные автоматы). Комбинационные схемы составляют основу дискретных вычислительных и
управляющих устройств. Они могут выполнять как самостоятельные
функции: преобразователи кодов, дешифраторы и т. п., – так и входить в
состав цифровых автоматов с памятью, реализуя функции переключения элементов памяти в новые состояния, выработку логических и управляющих сигналов. Сами элементы памяти могут быть построены в
виде комбинационных схем с обратными связями.
В настоящем учебном пособии в краткой форме изложены основные
понятия и методы построения однотактных цифровых устройств контроля и управления, логика работы которых описывается булевыми функциями. Булевы преобразования двоичных последовательностей выделены в самостоятельный раздел, в котором описаны возможные области применения булевых преобразований при решении некоторых задач
защиты информации.
1. БУЛЕВЫ ФУНКЦИИ И КОМБИНАЦИОННЫЕ СХЕМЫ
1.1. Понятие о булевых функциях.
Булевы функции одного и двух аргументов
Булевыми функциями (функциями алгебры логики) называют функции, аргументы которых, так же как и сама функция, принимают
только два значения – 0 или 1. Алгебра логики является разделом
математической логики, в которой изучаются методы доказательства истинности (1) или ложности (0) сложных логических конструкций, составленных из простых высказываний, на основе истинности
или ложности последних.
Алгебра Буля оказалась очень удобным и эффективным математическим аппаратом для анализа и синтеза комбинационных схем.
Булевы функции определяют логику работы комбинационных схем
следующего вида:
x1
x2Комбинационная
x3
xn
. . .
схема
F(x1, x2, …, xn)
xn
. . .
схема
F(x1, x2, …, xn)
где x1– xn, F ? { 0, 1}. Рассмотрим частные случаи.
Пусть n = 1, тогда входной сигнал x может принимать только два
значения – 0 и 1, а выходной сигнал F(x) может обеспечивать четыре
различных реакции на выходе. Таблица, в которой каждому набору входных сигналов сопоставляется значение выходного сигнала, называется
таблицей истинности функции.
Для комбинационных схем с одним входом таблицы истинности
всех булевых функций, описывающих логику работы схемы, примут
вид (табл. 1).
4
Пусть n = 1, тогда входной сигнал x может принимать только два
значения – 0 и 1, а выходной сигнал F(x) может обеспечивать четыре
различных реакции на выходе. Таблица, в которой каждому набору входных сигналов сопоставляется значение выходного сигнала, называется
таблицей истинности функции.
Для комбинационных схем с одним входом таблицы истинности
всех булевых функций, описывающих логику работы схемы, примут
вид (табл. 1).
4
F1= const 0, F2 = x, функция повторения x,
F4 = const 1, F3– инверсия аргуменмента x,
обозначаемая ? x или x и называемая иногда “не x”, “отрицание x”.
При n = 2 получаем таблицу истинности
16 различных функций двух аргументов
(табл. 2).
Таблица 1
x F1F2F3F4
0 0 0 1 1
1 0 1 0 1
F4 = const 1, F3– инверсия аргуменмента x,
обозначаемая ? x или x и называемая иногда “не x”, “отрицание x”.
При n = 2 получаем таблицу истинности
16 различных функций двух аргументов
(табл. 2).
Таблица 1
x F1F2F3F4
0 0 0 1 1
1 0 1 0 1
Таблица 2
x1x2