Задание комбинационных схем числовыми последовательностями

Декомпозиционные методы синтеза и анализа КЛС

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

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

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

Выходные функции называются собственными функциями комбинационных логических схем. Изображённой на рис. 2.1 КЛС соответствует система из собственных функций от аргументов.

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

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

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

(2.1)

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

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

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

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

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

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