СПОСОБЫ ЗАДАНИЯ И ФОРМЫ ПРЕДСТАВЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ
В комбинационных схемах соответствие между наборами значений входных и выходных сигналов определяется системой, функций
1.2.
ПОСТРОЕНИЕ КРАТЧАЙШЕЙ ДИЗЪЮНКТИВНОЙНОРМАЛЬНОЙ ФОРМЫ
борами таблицы истинности. Полученную в результате сравнения наборов информацию представим в виде таблицы различий единичного набора, строкам которой сопоставлены нулевые наборы, а столбцам — буквы полной конъюнкции. Единичный элемент на пересечении строки и столбца таблицы указывает на то, что нулевой набор строки отличается от рассматриваемого единичного набора буквой, приписанной столбцу. Таблица различий набора mi приведена в табл. 1.4. Заметим, что содержимое строк этой таблицы можно рассматривать как результат суммирования по модулю два единичного набора с нулевыми наборами.
Любая импликанта, покрывающая единичный набор, состоит из совокупности букв, которой соответствуют столбцы, содержащие в каждой строке таблицы различий не менее одного единичного элемента. Например, набор mi покрывается импликантой Х\Х4, поскольку четвертый столбец табл. 1.4 имеет единицу в первой, а первый— во всех остальных строках. Для того чтобы найти другие импликанты, нужно проверить остальные совокупности столбцов. Сложность этой проверки состоит в том, что в общем случае единичный и нулевой наборы могут различаться значениями нескольких переменных и одна переменная, в свою очередь, может отличать единичный набор от целого ряда нулевых наборов.
Налицо необходимость решения комбинаторной задачи, которая носит название задачи покрытия. Напомним основной метод решения задачи покрытия и необходимые определения.Покрытием таблицы (в данном случае таблицы различий) назовем совокупность ее столбцов, которая в каждой строке таблицы содержит не менее одного единичного элемента.
Естественно, что совокупность всех столбцов таблицы различий является покрытием. Для табл. 1.4 пример покрытия, кото-
табл. 1.4, поэтому строку 8 можно удалить из таблицы. Будем говорить в таком случае, что строка 8 поглощается строкой 6. Возможны и более сложные случаи поглощения строк. Так, в табл. 1.4 строка 9 поглощается строкой 7, поскольку расположение единиц в строке 7 сохраняется в строке 9. Поглощаемые строки отмечены в табл. 1.4. знаком «*». Поглощаемые строки можно удалять из таблицы различий без потери вариантов ее покрытия. Удаляя из табл. 1.4 поглощаемые строки, получим табл. 1.5.
!в
Таблица 1.5
Таблица 1.6
Т я (л гг и тт я 1.10'
Таблица 1.12
1.3. СОСТЯЗАНИЯ в КОМБИНАЦИОННЫХ СХЕМАХ
рим г функционирование комбинационной схемы во времени. В стационарном или установившемся режиме значения сигналов в промежуточных точках и на выходе схемы совпадают со значениями соответствующих булевых переменных. При изменений входных сигналов внутри схемы и на ее выходе имеет место переходный процесс, отражающий реакцию элементов схемы на изменение входных сигналов.
Длительность переходного процесса, т. е. интервал времени между моментом поступления входного воздействия и моментом окончания изменения значений всех сигналов схемы, определяется внутренними (естественными) задержками элементов схемы. Величины этих задержек будем считать ненулевыми, ограниченными сверху некоторой максимальной величиной. Следующее входное воздействие может поступать лишь по окончании переходных процессов во всех точках схемы. Переходные процессы внутри схемы определяют вид переходного процесса на выходе схемы. В соответствии с таблицей истинности булевой функции требуется, чтобы выходной сигнал z либо оставался неизменным, либо изменял свое значение не более одного раза. Однако в действительности выходной сигнал комбинационной схемы может изменяться несколько раз в ответ на одно переключение входных сигналов. В этом случае говорят о неустойчивой работе схемы. Причиной не-
обладающую данным свойством, будем называть свободной от состязаний. Комбинационная схема, построенная по такой ДНФ„ не имеет логических состязаний для всех заданных переходов. Эта схема свободна также и от динамических состязаний, если все переходы между нулевыми и единичными наборами связаны; с изменением только одного входного сигнала.
Комбинационную схему, свободную от функциональных и логических состязаний, будем называть устойчивой комбинационной схемой. На выходе устойчивой комбинационной схемы отсутствуют ложные изменения выходного сигнала для всех заданных переходов между наборами значений входных сигналов при произвольном соотношении величин естественных задержек элементов схемы. Очевидно, что построение устойчивой схемы ведется с расчетом на «наихудший случай». Естественно предположить,, что учет реального разброса величин задержек может привести к меньшим аппаратурным затратам, однако на практике часто точное знание величин задержек в схеме не представляется возможным.
ДНФ, свободная от состязаний, используется непосредственно для построения комбинационной схемы на элементах И, ИЛИ,. НЕ без ограничения на число входов элементов. В случае использования элементов с ограниченным числом входов и других базисов элементов необходимо производить преобразования ДНФ, свободной от состязаний. Эти преобразования не должны выводить щолучаемую форму представления функции из класса форм, свободных от состязаний. К числу таких преобразований относятся упрощения вида
преобразования, основанные на законах де Моргана, а также факторизация, состоящая в вынесении за скобки одной или нескольких букв в членах ДНФ.