2. Декомпозиционные методы синтеза и анализа клс

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

Рис. 2.1. Комбинационная логическая схема

Каждый входной сигнал принимает одно из двух возможных значений – «0» или «1», выходные сигналы тоже имеют значения «0» или «1», Это логические переменные, поэтому схема называется логической. Состояние каждого выхода однозначно определяется комбинацией состояний на входе. Именно поэтому такие схемы называются комбинационными. Выходные функции называются собственными функциями комбинационных логических схем. Изображённой на рис. 2.1 КЛС соответствует система из собственных функций от аргументов.

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

Таким образом, последовательность входных сигналов определяет последовательность смены внутренних состояний и выходных сигналов, поэтому такие схемы часто называют последовательностными.

Структурно АП отличаются от комбинационных схем наличием обратных связей, что приводит к появлению свойств запоминания состояний. В каноническом представлении АП разделяются на две части: комбинированную логическую схему (КЛС) и память (П) (рис. 2.2). На входы КЛС подаются входные сигналы и сигналы состояния АП , а на её выходах вырабатываются выходные сигналы и сигналы для перевода АП в новое состояние .

Рис. 2.2. Структурная схема АП

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

2.1. Формальное описание комбинационных устройств числовыми последовательностями

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

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

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

Пусть задана система логических функций (2.1):

(2.1)

Указанные функции описывают двоичный сумматор (рис. 2.3.).

Рис. 2.3. Двоичный сумматор

– функция переноса в старший разряд,

– функция суммы.

Определим все значения функций и , подставив в алгебраические выражения (2.1) все возможные значения аргументов (табл. 1).

Таблица 2.1

Таблица истинности двоичного сумматора

0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

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

,

а логическая последовательность функции суммы двоичного сумматора – в виде:

.

Для более удобного восприятия в логическую последовательность через каждые четыре элемента можно вставлять служебный символ – пробел.

В общем случае рассмотрим числовую последовательность, содержащую элементов:

. (2.2)

Индекс последовательно принимает значения от 0 до . Значение индекса можно представить в двоичной позиционной системе счисления с естественными весовыми коэффициентами разрядов (самый младший разряд имеет весовой коэффициент 1, следующий – 2, затем – 4 и так далее).

Пусть являются двоичной записью индекса . Тогда

.

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

Для того, чтобы определить значение логической функции на наборе значений аргументов , необходимо двоичное число перевести в десятичную систему счисления и отсчитать нужный элемент в двоичной последовательности, причём счёт начинается с нуля. Пусть, например, требуется найти значение логической функции из табл. 2.1 на наборе значений аргументов (110), которому соответствует десятичное число 6. Шестым элементом в числовой последовательности является «1». Это и есть искомое значение функции .

Числовая последовательность не несёт никакой информации об именах аргументов логической функции. Но для целей синтеза это не важно. Важен лишь порядок старшинства входных переменных, а этот порядок устанавливается весами соответствующих разрядов во входном двоичном наборе. Поэтому аргументами мы будем считать весовые коэффициенты соответствующих им разрядов. В рассмотренном примере входную переменную можно обозначить как , – , а – . Для удобства старшинство переменных следует отсчитывать сверху вниз. Индекс «0» в обозначении переменной свидетельствует о том, что рассматриваемые сигналы являются входными для схемы.

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

В рассмотренном выше примере мы имеем систему (2.1) логических функций и от одних и тех же аргументов. Каждая из рассматриваемых функций может быть представлена двоичной последовательностью и обе эти последовательности имеют одинаковую длину. Записав указанные последовательности одна под другой, мы получим двоичную матрицу (2.3):

. (2.3)

Столбцы этой матрицы можно рассматривать как двоичные числа, которые для более компактной записи удобно перевести, например, в шестнадцатеричную систему счисления. Тогда матрица (2.3) запишется в виде числовой последовательности (2.4), которая полностью описывает функционирование двоичного сумматора:

. (2.4)

Запись (2.4) компактнее минимальной дизъюнктивной нормальной формы (2.1).

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

не определена на наборах 011 и 101, так как третьему и пятому элементам указанной последовательности соответствуют звёздочки.

Числовая последовательность, представляющая систему логических функций, не указывает имён этих функций. Поэтому порядок (старшинство) функций в системе можно характеризовать весами разрядов в двоичном представлении чисел последовательности. В последовательности (2.3), например, логическая функция имеет вес 2, а функция – вес 1. Информация о старшинстве функций и их аргументов необходима при выполнении процедур логического синтеза.