Содержание к диссертации
Введение
Раздел 1. Анализ методов синтеза цифровых устройств. постановка задачи исследования 13
1. 1. Краткий обзор и анализ методов синтеза цифровых устройств 13
1.2. Постановка задачи исследования 19
Раздел 2 Основные способы представления и преобразования логических функций в обобщенной форме 23
2.1. Исходные замечания к представлению традиционных функций алгебры логики в форме обобщенных, область определения, способы представления и типы обобщенных логических функций 23
2.2. Канонические формы представления ОЛФ 29
2.3. Разработка и анализ алгоритма минимизации основных типов ОЛФ с независимыми параметрами в классе ДНФ 35
2.4. Анализ алгоритма минимизации основных типов ОЛФ с зависимыми параметрами в классе ДНФ 40
2.5. Представление и минимизация недоопределенных ОЛФ с зависимыми параметрами 47
2.6. Выводы по разделу 50
Раздел 3. Разработка и анализ алгоритма сжатия области определения функций алгебры логики и их- представлние в форме обобщенных функций с зависимыми параметрами 51
3.1. Вводные замечания к проблеме сжатия и представления области определения традиционных функций алгебры логики в форме ОЛФ 51
3.2. Неполное разложения Шеннона и его приложение к представлению функций в обобщенной форме 54
3.3. Разработка и анализ алгоритма сжатия области определения функций, заданных таблицами истинности 55
3.4 Алгоритм сжатия области определения функций, представленных в картах декомпозиции 58
3.5. Версия алгоритма сжатия области определения функций, заданных списком минтермов 61
3.6. Алгоритм сжатия области определения функций, заданных номерами наборов, представленными в двоичной системе 63
3.7. Особенности алгоритма сжатия области определения функций, заданных номерами наборов, представленными в десятичной системе 65
3.8. Принцип двойственности алгоритма сжатия области определения логических функций 68
3.9. Выводы по разделу 69
Раздел 4. Методы синтеза и анализа цифровых устройств, основанные на представлении функций в обобщённой форме 71
4.1. Разработка и анализ метода многоверсионной минимизации 73
4.2. Приложение операции сжатия области определения логических функций к анализу состязаний в комбинационных схемах 84
4.3. Приложение свойств обобщённых логических функций к синтезу быстродействующих многоразрядных компараторов 97
4.4. Разработка методов и практических рекомендаций по использованию свойств ОЛФ при синтезе цифровых устройств с перестраиваемыми параметрами 104
4.4.1. Вводные замечания 104
4.4.2. Анализ алгоритма привязки и размещения диапазона перестройки ЦА ПП с программируемой длительностью временных интервалов 106
4.4.3. Представление диапазона перестройки в картах с соседним кодированием, оптимизация его размещения 110
4.4.4. Разработка алгоритма оптимального кодирования минтермов, обеспечивающего минимизацию схемной реализации функции выхода 128
4.4.5. Приложение свойств ОЛФ с недоопределенными параметрами к синтезу НА с перестраиваемой длительностью формируемых временных интервалов 138
4.4.6. Алгоритм размещения и кодирования состояний при кратности формируемых интервалов пропорциональной половине периода синхронизирующих импульсов 145
4.4.7. Синтез многофункционального ЦА ПП (универсального программируемого интервального таймера) 150
4.4.8. Формирователь одиночных импульсов с перестраиваемой длительностью в заданном временном интервале 159
4.4.9. Формирователь одиночных интервалов времени с перестраиваемой длительностью, кратной половине периода тактирующих импульсов... 170
4.4.10. Приложение свойств ОЛФ к синтезу УЛМ с памятью, используемых в конвейерных устройствах обработки информации 178
4.4.11. Синтез многофункциональных триггерных устройств 187
4.5. Разработка и анализ метода нахождения ориентированных и неориентированных частных булевых производных 193
4.6. Разработка и анализ метода нахождения кратных булевых производных 201
4.7. Разработка и анализ метода нахождения функционально-полного класса векторных булевых производных 206
4.8. Выводы по разделу 216
Заключение 218
Список литературы 223
- Краткий обзор и анализ методов синтеза цифровых устройств
- Разработка и анализ алгоритма минимизации основных типов ОЛФ с независимыми параметрами в классе ДНФ
- Неполное разложения Шеннона и его приложение к представлению функций в обобщенной форме
- Приложение свойств обобщённых логических функций к синтезу быстродействующих многоразрядных компараторов
Введение к работе
Актуальность темы. Широкое внедрение вычислительной техники и систем управления во все сферы человеческой деятельности и усложнение задач, решаемых этими системами, требуют разработки новых и совершенствования существующих методов логического проектирования цифровых устройств. Логическое проектирование при этом понимается в широком смысле, включая не только статику систем, т.е. их структуру и функциональные связи, но и анализ динамики как на уровне структуры, а также на уровне переходных процессов, связанную с из7 менением переменных и временными характеристиками элементов. В связи с этим исследования, направленные на развитие методов логического проектирования цифровых устройств, обеспечивающих упрощение процедуры проектирования, улучшение основных характеристик ЦУ, а также снижение времени и стоимости разработки никогда не потеряют своей актуальности.
Проблеме логического проектирования цифровых устройств посвящено большое число работ, среди которых фундаментальными являются работы, выполненные В.М. Глушковым, А.Д. Закревским, СИ. Барановым, Д.А. Поспеловым, СВ. Новиковым, Е.П. Угрюмовым, В.В. Соловьёвым, Е. Вейчем, М. Карпе, В. Квайном, Г. Мили, Е. Муром, К. Шенноном и др. Большинство из этих работ основано на представлении логическихфункций (ЛФ) в точках области их определении значениями логического 0 или 1.
Наряду со многими достоинствами такого представления оно имеет и ряд недостатков, особенно при большом числе переменных, поскольку при увеличении числа переменных происходит лавинообразное увеличением количества точек области определения и, как следствие, усложнение процедуры анализа и синтеза, связанное с решением объёмных комбинаторных задач. Эти недостатки су,-щественны не только при аналитических методах, но также и при использование программных средств анализа и синтеза.
В то же время многие исследователи: СВ. Яблонский, В.П. Сигорский, В.П. Тарасенко, П.Н. Бибило, А.А. Шалыто, Е. Мак-Класки, Р. Брайтон и др. - пошли
7 по пути нетрадиционных подходов к представлению и преобразованию логических функций, основанном на концепции многозначного алфавита, конечных предикатов, логических шкал, интерполяционных и арифметических полиномов, спектрального представления и др., которые в ряде случаев дали положительный эффект как при анализе, а также синтезе цифровых устройств.
К предлагаемому нетрадиционному способу можно отнести представление логических функций в форме обобщённых, когда значения функции в точках её области определения заданы не только значением логического 0 и 1, но и независимыми или зависимыми параметрами. В частности, к такой форме можно отнести неполное разложение Шеннона. При этом, коэффициенты, образуемые литералами переменных, по которым выполняется разложение, можно трактовать как координаты точек области определения, а остаточные функции — как параметры определяющие значения функции в этих точках. Такой подход ведёт к существенному уменьшению числа точек области определения, обеспечивая упрощение процедуры логического проектирования цифровых устройств, включая вопросы, связанные с представлением и минимизацией функций, синтезом комбинационных схем и автоматов с памятью, решением задач динамики цифровых устройств, связанных с анализом состязаний в комбинационных схемах, а также нахождением булевых производных.
На основании изложенного можно заключить, что тема диссертационного исследования, направленного на разработку новых и дальнейшее развитие суще ствующих методов и алгоритмов логического проектирования, основанных на представлении логических функций в точках области определения в обобщённой форме в виде независимых или зависимых параметров является актуальной.
Работа выполнялась в рамках фундаментального исследования «Информационные технологии в управлении производственно-технологическими процессами в ПСМ» (Белгородский государственный технологический университете им. В.Г. Шухова, № ГР 01200311387, г. Белгород, 2003-2007 гг.), в соответствии и планами и программами научно-исследовательских работ при непосредственном участии автора.
8 Объект исследования — процессы разработки методов, алгоритмов, а также
программно-технических средств логического проектирования цифровых устройств вычислительной техники и систем управления.
Предмет исследования - методы и алгоритмы анализа и синтеза цифровых устройств вычислительной техники и систем управления на основе обобщённо1»! формы представления логических функций.
Цель диссертации — разработка методов и алгоритмов логического проектирования цифровых устройств, обеспечивающих упрощение процедуры и снижение времени проектирования, основанных на представлении и преобразовании логических функций в обобщённой форме.
Поставленная цель работы предполагает решение следующих задач:
- провести- анализ современного состояния методов логического проектиро
вания цифровых устройств;
- разработать методы минимизации обобщённых логических функции
(ОЛФ) с независимыми и зависимыми параметрами;
разработать алгоритм и программные средства преобразования традиционных логических функций в форму ОЛФ с зависимыми параметрами, основанные на сжатии их области определения;
разработать метод многовариантной минимизации логических функций, основанный на сжатия их области определения по комплементарным подмножествам переменных, определяющих заданную функцию, обеспечивающий контроль достоверности результата минимизации;
разработать и исследовать метод анализа состязаний в комбинационных схемах, основанный на последовательном сжатии области определения функции по каждой из переменных, позволяющий упростить процедуру нахождения ситуаций риска с последующим их устранением;
разработать методы синтеза комбинационных схем, многофункциональных триггерных устройств, УЛМ с памятью, а также методы нахождение оптимального представления функций выхода автоматов Мили с перестраиваемыми параметрами, основанные на представлении логических функций в форме ОЛФ;
9 - разработать инженерную методику нахождения булевых производных,
основанную на сжатии области определения логических функций.
Методы и математический аппарат исследования базируются на теории множеств, теории переключательных функций, комбинаторике, теории алгоритмов и программирования, теории цифровых автоматов, теории булевого дифференциального исчисления.
Научная новизна работы состоит в следующем:
Впервые предложена расширенная трактовка канонического представления логических функций (СДНФ) в форме ОЛФ, разработаны и исследованы методы минимизации различных типов обобщённых логических функций с независимыми и зависимыми параметрами.
Впервые разработан алгоритм преобразования традиционных логических функций в форму обобщённых функций с зависимыми параметрами, основанный на разбиении множества всех переменных на два подмножества, одно из которыу определяет координаты точек сжатой области, а второе - значения функции в этих точках, обеспечивая уменьшение числа точек области определения, и, как следствие, сокращение времени их обработки.
На основе сжатия области определения функций по комплементарным подмножествам переменных разработан метод многовариантной минимизации с различными исходными данными в каждом из вариантов, что позволяет обеспечить контроль достоверности полученного результата минимизации.
Предложен и исследован метод анализа состязаний в комбинационных схемах, основанный на последовательном сжатии области определения функциг по каждой из переменных, определяющих заданную функцию, что позволяет упростить процедуру нахождения ситуаций риска с последующим их устранением.
Впервые разработаны методы синтеза комбинационных схем, многофункциональных триггерных устройств, универсальных логических модулей с памятью, методы нахождение оптимального представления функций выхода автоматов Мили с перестраиваемыми параметрами, основанные на представлении и преобразовании функций в форме ОЛФ, обеспечивающие уменьшение числа то-
10 чек области определения, что позволило уменьшить размер таблиц функционирования проектируемых устройств, а также сократить перебор вариантов и, как следствие, сократить время проектирования в целом.
6. Впервые разработана и исследована инженерная методика нахождения
функционально полного класса булевых производных, основанная на сжатии об
ласти определения заданной функции, позволившая полностью исключить анали
тические представления и связанные с ними преобразования, что упростило прс
цедуру и сократило время их нахождения. ,
Практическая ценность диссертации заключается в доведении полученных теоретических результатов до конкретных алгоритмов, методов, программ и схем цифровых устройств, проиллюстрированных примерами. Основные практические результаты сводятся к следующему:
представление традиционных логических функций в форме обобщённых позволяет упростить процедуру минимизации, а разработанные программные средства сжатия области определения дают возможность использования их в пакетах САПР;
предложенный метод многовариантной минимизации логических функг ций позволяет обеспечить контроль достоверности проведенных преобразований и минимальность полученных результатов;
-метод анализа состязаний в комбинационных схемах, основанный на сжатия области определения логических функций, позволяет упростить процедуру нахождения ситуаций риска с последующим их устранением;
представление функций в форме ОЛФ при синтезе комбинационных схем и многофункциональных триггерных устройств позволило упростить процедуру синтеза за счёт сокращения числа точек области определения (таблиц функционирования) и, как следствие, сократить время проектирования; ч
использование представления логических функций в форме ОЛФ при нахождении оптимального по сложности представления функций выхода цифровых автоматов с перестраиваемыми параметрами позволило упростить процедуру синтеза за счёт сокращения числа точек области определения, а также обеспечить
целенаправленный выбор вариантов, существенно сократив перебор и, как след.: ствие, сократить время проектирования в целом;
представление функций в форме ОЛФ при синтезе универсальных логических модулей с памятью, реализующих программируемый список функций, позволило выполнить оптимальную реализацию настройки модулей на выполнение списка функций за счёт оптимального размещения функций в области определения, исключив процедуру перебора вариантов настройки;
применение свойств ОЛФ к нахождению булевых производных позволило исключить их аналитические представления и связанные с ними преобразования, что позволило упростить процедуру и сократить время нахождения.
Разработанные методы, алгоритмы, программные средства и предложенные схемы цифровых автоматов с перестраиваемыми параметрами имеют признаки новизны, существенные отличия и могут быть рекомендованы для использования в НИР, НИОКР, учебном процессе студентов соответствующих специальностей.
Апробация работы. Основные положения диссертации и её научные результаты докладывались и получили положительную оценку: на международной научно-практической конференции «Научные исследования, наносистемы и ре сурсосберегающие технологии в стройиндустрии» (г. Белгород, 2007 г.); на региональной НТК «Современные проблемы технического, естественно - научного и гуманитарного знания» (г. Губкин, 2004 г.); на 15 и 16-й МНТК «Информацион-но-управляюшие системы на железнодорожном транспорте» (г. Алушта, 2002, 2003 гг.); на МНТК «Проектирование и производство самолетов и вертолетов» (г. Алушта, 2003 г.); на 1-й, 2-й и 3-й МНТК «Гарантоспособные системы, сервисы и технологии» (г. Полтава, 2006 г., г. Кировоград, 2007, 2008 гг.).
Реализация и внедрение. Результаты работы внедрены на предприятии ЗАО «Сокол-АТС», г. Белгород, Россия; в ГНПП "Объединение Коммунар" НТ СКБ "ПОЛИСВИТ", г. Харьков, Украина, а также используются в БГТУ им. В.Г. Шухова на кафедре технической кибернетики в учебных дисциплинах: «Теорй.. цифровых автоматов», «Архитектура ЭВМ и систем», «Схемотехника электронных устройств», «Микропроцессорная техника».
12 Публикации. Результаты, полученные в диссертационной работе, отражены в 22 статьях и в 3 опубликованных тезисах докладов на всероссийских, международных и региональных научно-технических конференциях.
Личный вклад соискателя. Работы [16-24] написаны автором лично. Вклад соискателя в работы, написанные в соавторстве, состоит: в разработке основных вариантов алгоритма сжатия области определения ЛФ [40,46,47] их программной реализации [25], анализе методов минимизации ОЛФ [49-51] и оценке достоверности её результатов [41,43], в разработке методов синтеза ЦУ [42,44], анализе методики нахождения булевых производных [26,45,48,53]. На защиту выносятся:
Представление логических функций в форме ОЛФ с независимыми и зависимыми параметрами, методы их минимизации.
Алгоритм преобразования традиционных логических функций в форму обобщённых логических функций с зависимыми параметрами.
Метод многовариантной минимизации логических функций, основанный на сжатия их области определения.
Метод анализа состязаний в комбинационных схемах, основанный на сжатия области определения логических функций.
Методы синтеза комбинационных схем, многофункциональных триггер-ных устройств, универсальных логических модулей с памятью, а также автоматов Мили с перестраиваемыми параметрами выходных сигналов, основанные на представлении функций в форме ОЛФ.
Инженерная методика нахождения булевых производных, основанная на сжатии области определения заданной функции
Автор выражает свою признательность научному руководителю, Заслуженному деятелю науки и техники РФ, доктору технических наук, профессору Рубанову Василию Григорьевичу за всестороннюю поддержку, консультации, ценные замечания и рекомендации, а также коллективу кафедры технической кибернетик ки Белгородского государственного технологического университета им. В.Г. Шу-хова за помощь при проведении исследований и обсуждении результатов.
Краткий обзор и анализ методов синтеза цифровых устройств
Проектирование цифровых устройств, всё множество которых условно разделяют на комбинационнве схемы и автоматы с памаятью тесно связано с реше-нием задач анализа, синтеза, контроля и диагностики.
Проблеме анализа и синтеза цифровых устройств посвящено огромное число работ, среди которых наиболее фундаментальными являются исследования, проведенные В.М. Глушковым, СМ. Вавиловым, А.А. Шалыто, А.Д. Закревским, СВ. Новиковым, СИ. Барановым, Д.А. Поспеловым, Е.П. Угрюмовым, В.В. Соловьёвым, К. Шенноном, Е. Вейчем, М. Карно, В. Квайном, Г. Мили, Е. Муром и рядом других учёных. Традиционно методы синтеза комбинационных схем принято делить на два больших класса: двухуровневый и многоуровневый. Двухуровневый синтез ориентирован на представление логических функции в дизъюнктивной нормальной форме (ДНФ), которая предполагает прохождение сигналов со входов на выходы через два уровня элементов (И,ИЛИ), что соответствует структуре современных программируемых интегральных схем (ПЛИС) типа PLD (Programmable Logic Devices) или CPLD (Complex Programmable Logic Devices). Многоуровневый синтез схем ориентирован на представление логических функций в скобочной форме, т.е. предполагает прохождение сигналов со входов на выходы через несколько узлов логической сети, что соответствует структуре программируемых интегральных схем типа FPGA (Field Programmable Gate Array).
Главной задачей двухуровневого синтеза является минимизация булевых функций в классе ДНФ. Первые решения этой задачи [87,91] принято считать классическими. Число работ, посвященных решению задачи синтеза цифровых устройств вообще минимизации в частности настолько велико, что даже простое перечисление их далеко не тривиально. Достаточно полный обзор работ приведем в [56]. Ограничимся указанием и краткой характеристикой основных направление данных исследований: точные алгоритмы [15,79,83]; эвристические алгоритмы [14,34]; минимизация частично определенных функций [32,86]; минимизация слабо определенных функций [15,85]; минимизация системы булевых функций [55]; графический метод минимизации [81]. Большинство из этих исследований основано на представлении функций в точках их области определении в виде логического нуля и логической единицы, что позволило использовать основные постулаты двузначной булевой алгебры являющейся теоретической базой большинства методов. :" Наряду со многими достоинствами такого представления оно имеет и ря недостатков, особенно при большом числе переменных, поскольку при увеличении числа переменных происходит лавинообразное увеличением количества точек области определения и, как следствие, усложнение процедуры анализа и синтеза, связанное с решением объёмных комбинаторных задач. Эти недостатки существенны не только при аналитических методах, но также и при использовании программных средств анализа и синтеза.
В то же самое время многие исследователи: СВ. Яблонский, В.П. Сигор ский, В.П. Тарасенко, С.Ф. Тюрин, П.Н. Бибило, А.А. Шалыто, Е. Мак-Класки, Р. Брайтон и др. - пошли по пути нетрадиционного подхода к представлению и прс образованию логических функций, основанном на концепции многозначных булевых функций [1,9,57], конечных предикатов [1], толерантных булевых функций [82], на задании функций с помощью порождающих представлений [76]; минимизация, основанная на использовании диаграммы двоичных решений, а также их модификации [76]; метод минимизации, основанный на неявном представлении простых импликант [78]; методы минимизации, основанные; символический метод минимизации [80] и др., которые в ряде случаев дали положительный эффек. как при анализе, а также синтезе цифровых устройств.
Поскольку для реализации комбинационных схем в настоящее время ВСІ чаше используются CPLD и FPGA, то большинство разрабатываемых методов синтеза [56] ориентировано на данную элементную базу. Любые логические элементы, входящие в состав цифрового устройства, обладают некоторой инерцией, выражающейся соответствующим временем задержки переключения элемента. Это приводит к тому, что при технической реализации булевых функций некоторой комбинационной схемы каждая из выходных переменных получает своё новое значение, соответствующее реализуемой функции, лишь спустя некоторое время после того, как на входах схемы произойдёт установка значений всех переменных. Значения задержек, как правило, различны для разных путей распространения сигналов, определяющих эти переменные. При таких условиях возникают своего рода гонки (состязания) между изменениями переменных, приводящие к появлению кратковременных значений сигналов, не предусмотренных заданным алгоритмом функционирования схемы (так называемые риски), которые часто приводят к сбоям в работе ЦУ [30].
Для- исключения возможных сбоев необходимо выявить источники рисков с последующим их устранением. Условия отсутствия состязаний в комбинационных схемах определяются методами, рассмотренными в работах Мак-Класки [30] и Хаффмена [102]. Метод Мак-Класки основан на анализе логических функций и поэтому он может быть назван аналитическим. В соответствии с этим методом логическая функция должна быть предварительно представлена в форме, содер-жащей единичные или нулевые наборы, что аналогично представлению в совер: шенной дизъюнктивной нормальной форме (СДНФ) или совершенной конъюнктивной нормальной форме (СКНФ). Метод же Хаффмена основан на анализе покрытий логических функций, представленных в картах Карно, поэтому его можно трактовать как графический.
В отдельную группу выделим работы, посвященные программной минимизации функций. Среди большого числа программ двухуровневого синтеза комбинационных схем наиболее известными являются пакеты ESPRESSO [74], PRESTO [75], МС BOOLE [79] и MINI [82]. Точное решение позволяет получить только программа МС BOOLE, а остальные решают задачу минимизации булевых функций приближенно.
Среди названных программ наибольшей популярностью пользуется программа ESPRESSO, разработанная в лаборатории электронных исследований Калифорнийского университета в Беркли (США). В основу программы ESPRESSO были положены алгоритмы минимизации, предложение в работах [90], которые г, значительной степени были развиты в [74,93].
Поскольку предметом наших исследований является представление и преобразование функций в классе ДНФ, то вопросы, связанные с анализом работ, посвященные многоуровневому синтезу, не рассматриваем.
Разработка и анализ алгоритма минимизации основных типов ОЛФ с независимыми параметрами в классе ДНФ
Как уже отмечалось, все множество значений ОЛФ можно разбить на пересекающиеся подмножества, содержащие элементы двух типов, с общим элементом пересечения равным нулю (рис. 2.1). Такое разбиение дает возможности представить любую ОЛФ в виде дизъюнкции нескольких составляющих.
Способы нахождения минимальной формы составляющей функции, соответствующей единичным точкам ( min) общеизвестны, поэтому на них останавливаться не будем. Вопросом нашего рассмотрения является разработка алгоритма минимизации ОЛФ, заданных параметрами (составляющихFam-m,Fbmin...), и его анализ. Если функция задана несколькими параметрами (а, Ь, с ...), то достаточно рассмотреть алгоритм минимизации одной из составляющих функции, поскольку для остальных он будет аналогичен. В основу предлагаемого алгоритма положен ряд очевидных утверждений. Сформулируем и докажем эти утверждения.
Умножая результат минимизации на независимый параметр, получаем ми-нимальнкую форму составляющей функции (Famia), заданной парметром а, что и требовалось доказать.
Утверждение 2. Если обобщенная логическая функция содержит множест-во недоопределнных наборов (d), то их можно использовать для доопределпия любым из параметров.
Это утверждение не требует особого доказательства, поскольку из сущности недоопределенного (избыточного, несущественного, фиктивного) набора следует, что это такой набор, значение функции на котором безразлично, следовательно, его можно доопределять не только значением нуля или единицы, но также и любым параметром.
При этом, один и тот же недоопределенный набор может „одновременно" доопределяться значениями нескольких параметров, т.е. его можно включать в подмножнества как одного, а также и нескольких параметров сразу.
Утверждение 3. Любой единичный -набор можно использовать для доопре-делния наборов, определяемых параметром, т.е. включать его в подмножества любых параметров.
Второе, третье и т.д. слагаемые можно трактовать как произведения, соответствующие наборам, на которых функция равна параметру, следовательно, и можно включать в соответствующие подмножества наборов, на которых функция равна параметру, что и требовалось доказать.
Утверждение 4. Любой набор, на котором функция равна логической сумме двух или более параметров, должен быть обязательно включен в подмножества всех параметров, входящих в эту сумму.
Справедливость этого утверждения следует из того, что логическая сумма параметров, определяющих значение функции на этом наборе, равна нулю в том и только том случае, если равны нулю все параметры, входящие в неё.
Утверждение 5. Любые наборы, на которых функция равна произведению двух или более параметров, рассматриваются как отдельные подмножества. При этом каждое из таких подмножеств может быть доопределено любыми наборами, на которых функция недоопределена, равна единице; равна параметру, входящему в это произведение; равна произведению меньшего ранга, из множества, образующих исходное произведение.
Доказательство первого и второго пунктов данного утверждения аналогичны утверждениям 2,3.
Справедливость третьего пункта следует из того, что любой параметр, входящий в произведение, на основании обратного правила поглощения можно представить в виде логической суммы этого параметра и произведения, в которое входит этот параметр, т.е. а = а\/ abc..., b = bv abc, c = cv abc... , откуда следует, что наборы, на которых функция равна произведению независимых параметров можно доопределять наборами, на которых функция равна любому из параметров, входящих в это произведение.
Справедливость четвертого пункта доказывается аналогично, поскольку произведение меньшего ранга всегда можно представить в виде логической суммы этого произведения и произведения большего ранга, куда входит исходное произведение и еще один или несколько параметров, например: ab-abv abc, ас = acv abed и так далее.
Предложенный алгоритм, основанный на разбиении множества значений обобщенной логической функции на пересекающиеся подмножества, и сформу лированные и доказанные утверждения достаточны для нахождения минимальной формы обобщенной логической функции с постоянными параметрами любого к., приведенных выше типов.
Анализ процедуры минимизации основных типов ОЛФ с независимыми параметрами рассмотрим на конкретных примерах функций от четырех первичных переменных с представлением и минимизацией их в картах Карно.
Ограничиваясь анализом алгоритма минимизации, используя карты Карно и только лишь функции от четырех первичных переменных, мы преследовали только лишь одну цель - упростить иллюстрацию предложенного алгоритма, что отнюдь не ограничивает его общности для функции от любого числа первичных переменных и для любого способа минимизации.
Традиционные логические функции, множество значений которых состоит из подмножества нулей, единиц и( возможного подмножества недоопределенных значений, можно трактовать как частный случай ОЛФ.
Методы нахождения минимальных форм этих функций общеизвестны, поэтому отдельно мы их рассматривать не будем. В нашем случае они подпадают под пункт нахождения минимальной формы составляющей Fj тт (если она есть).
Предметом нашего дальнейшего исследования является анализ процедуры минимизации ОЛФ с независимыми параметрами.
В соответствии с утверждением 1 и общим алгоритмом минимизации классических функций в картах можем заключить, что суть алгоритма минимизации абсолютно-параметрических функций в картах [4] состоит в покрытии множества параметров минимально возможным числом правильных конфигураций (булевых прямоугольников) максимально возможной площади с последующей записью простых импликант, которые определяют как произведения логической координаты правильной конфигурации, образуемой литерами первичных переменных, покрывающих стороны правильной конфигурации, на значение функции (параметр) в покрываемом массиве.
Выполняя логическое суммирование полученных таким образом простых импликант, находим минимальную дизъюнктивную нормальную форму (МДНФ) абсолютно-параметрической ОЛФ.
Поскольку параметры независимы, то выделение правильных конфигурации можно начать с любых из них, однако, во избежание появления лишних импли-кант начинать рекомендуется с тех параметров, включение которых в правильную конфигурацию единственно возможное (рис. А. 1 - приложение А). При минимизации параметрических функций общего типа во множество значений функции этого класса входят не только параметры, но и единицы, следовательно, при образовании правильных конфигураций, покрывающих множест-во параметров, предоставляется возможность оптимального доопределения их наборами, на которых функция равна единице (рис. А.2 - приложение А).
Кроме того, в минимальную форму будет входить составляющая F/ „„„, соответствующая массиву единичных значений функции. Минимизация обобщенных логических функций, содержащих параметры, единичные, нулевые и недоопределенные наборы аналогична.
Во избежание появления лишних импликант при выполнении процедуры минимизации обобщенных логических функций, содержащих наборы, на которыг логическая функция равна дизъюнкции независимых параметров, выделение правильных конфигураций рекомендуется начинать с параметров, которые покрываются единственно возможным способом (рис. А.З - приложение А).
Неполное разложения Шеннона и его приложение к представлению функций в обобщенной форме
Исходной позицией алгоррітма является задание функции F(X) в любой аналитической форме. Если в подмножество Х включить любые к переменных множествах, то для сжатия области определения функции по этим переменным достаточно рас-ложить ее по переменным подмножества Х2 =Х\ХХ, представляя заданную функцию в виде логической суммы произведений коэффициентов разложения, представляющих собой минтермы (М, ), образуемые литералами переменных подмножества X,, на значение остаточных функций в этих точках (FJ [40] :
Трактуя каждый коэффициент разложения М, как логическую координату точки в области, определяемой переменными подмножества Х2, а остаточные функции F,, определяемые переменными подмножества Хх, как значения функции в этих точках, получаем представление заданной классической функции алгебры логики в форме ОЛФ с зависимыми параметрами.
В некоторых случаях, исходя из требований дальнейших преобразований, более удобна форма представления ОЛФ в виде списка координат ненулевых точек сжатой области и значений функции в этих точках.
Для перехода к такой форме представления необходимо логические координаты, образуемые литералами переменных подмножеств X,, представить двоичными, а затем десятичными эквивалентами. При переходе от логической координаты к двоичному эквиваленту достаточно в записи логической координаты вместо литерала Зё( записать ноль, а вместо х, - единицу.
Рассмотренный способ сжатия области определения функции можно считать классическим. Причем применение его возможно не только при аналитической форме исходного задания функции, но и при любой другой, выполнив предварительные её преобразования. Однако такой способ довольно громоздкий, поскольку нахождение остаточных функций (Ft) осуществляется методом подстановки значений переменных подмножества Хг в исходную функцию F{X) в каждой точке разложения, что при ручной реализации неизбежно сопровождается ошибками, которые трудно обнаружить, а при программных способах требует большого числа преобразований.
Поэтому данный способ мы привели больше в качестве исходного теоретического обоснования операции сжатия области определения функций, нежели для практического его использования. Анализ рассмотренной версии алгоритма приведен в разделе Б.1 приложения Б.
Исходной позицией рассматриваемой версии алгоритма является функция от п переменных, представленная полной таблицей истинности. Таблица, содержит 2" строк, каждую из которых можно трактовать как точку исходной области определения функции.
Как-и в предыдущем варианте, всё множество переменных разбиваем на две группы. В одну группу включаем к переменных, которые трактуем как в і ори ч-ные переменные на данном разбиении, а во вторую - оставшиеся п - к переменных, которые трактуем как первичные переменные на этом разбиении.
В результате такого представления все 2" строк исходной таблицы можно рассматривать в виде отдельных групп, содержащих по 2к строк в каждой из них.
Первая группа строк будет соответствовать нулевому набору старших переменных, следующая - первому и т.д. вплоть до значения набора, равного 2" к -1.
Каждую из представленных таким образом групп строк рассматриваем ка отдельную независимую таблицу истинности, определяющую значение функции от к переменных второй группы на каждом из 2" к наборов переменных первой группы. Это дает возможность представить каждую такую независимую таблицу в одной из аналитических форм, в частности в СДНФ. В результате получаем но вую таблицу с числом наборов (строк), равным 2" к и значением функции на ка ждом наборе, представленным в виде логической суммы минтермов, образуемых литералами переменных второй группы, соответствующих единичным значениям заданной функции (таблица Б.2 - приложение Б). По сути, получаем область определения обобщенной логической функции, координаты точек которой определяются значением переменных, включенных в подмножество вторичных. ч
Если возникает необходимость в сжатии исходной области определения функции по любым переменным, то алгоритм преобразования несколько усложняется. Это усложнение связано, во-первых с тем, что сначала необходимо в исходной таблице истинности сделать перестановку столбцов, включая в старшую группу (п — к) столбцов, соответствующих выбранным первичным переменным, а в младшую группу - к столбцов, соответствующих вторичным переменным, затем сделать перестановку строк, расположив их так, что в первую группу войду і 2к строк, соответствующих нулевому набору выбранных первичных переменных, во - вторую группу войдут 2к строк, соответствующих первому набору, и т.д. вплоть до набора, равного 2" к -1. При выполнении перестановок строки в каждой группе располагают в порядке возрастания номеров наборов, образуемых переменными, включенными во множество вторичных, т.е. начиная от нулевого набо ра вторичных переменных до набора, равного 2 -1. Проделав эти преобразования, получаем таблицу, которую можно рассматривать, как и выше, состоящей и» отдельных таблиц истинности, определяющих значения функции от к переменных, включенных в подмножество вторичных.
Алгоритм получается довольно громоздким. При его ручной реализации неизбежно возникают ошибки, поэтому этот алгоритм можно рекомендовать только для наиболее простой его версии сжатия по переменным с младшими индексами, а также в качестве исходного при разработке программного способа реализации.
Приложение свойств обобщённых логических функций к синтезу быстродействующих многоразрядных компараторов
Цифровые компараторы (сравнивающие устройства) определяют отношение между двумя n-разрядными двоичными словами. Основными отношения, через которые можно выразить остальные являются два.
Всё множество цифровых компараторов в зависимости от выполняемых функций можно разделить на пять групп: определяющие отношения А В, А=В; определяющие отношения А В, А=В; определяющие отношения А В, А В; определяющие отношения Л Д А В; определяющие отношения Л Д Л Д Л =В. Эти отношения используются как логические условия при выполнении микропрограмм, в устройствах контроля и диагностики и т.д.
Поскольку компаратор относится к классу устройств с симметричным алгоритмом функционирования относительно входных слов, то определение (обозначение) того или другого выхода чисто условно. Всё зависит от того, относительно какого слова определяется функция выхода.
При таком подходе к проектированию возможна реализация компаратора любой размерности. Однако при этом задержка в выполнении операции сравнения растёт пропорционально числу разрядов компаратора.
Максимально возможное быстродействие имеют компараторы с параллельной организацией операции сравнения. Однако, такая организация влечёт за собой усложнение структуры и процедуры синтеза, особенно при большом числе разря дов сравниваемых двоичных слов.
Решение задачи синтеза многоразрядных компараторов с параллельной организацией формальным методом, представляя функции выхода в таблицах истинности, вызывает большие затруднения, поскольку при синтезе п-разрядного компаратора таблица будет содержать 22" наборов.
Предлагается компромиссное решение структуры многоразрядного компаратора, выполненного по схеме многоступенчатого сравнения с параллельно последовательной организацией. Первая ступень выполняется на четырёхразрядных компараторах с параллельной организацией.
Значение функции в каждой точке сжатой области определения есть результат сравнения четырёхразрядных слов А и В и оно равно единице если А В Каждому значению четырехразрядного слова aia2ala0 ставим в соответствие минтерм, образуемый литералами этих переменных (kt - а2а а{а0), а каждому значению четырехразрядного слова b3b2blb0 ставим в соответствие минтерм, образуемый литералами переменных В {mt- ЬЪЬ2ЪХЬ0). Если минтермы kl = а3а2а{а0 трактовать как кородинаты точек области определения функции выхода F y а минтермы т1 -ЬъЪгЬр - как параметры, определяющие единичные значения функции выхода F в точках области определения, то СДНФ функции можно будет представить следующим образом.
Если же минтермы т, = b3b2bxb0 трактовать как координаты точек области определения функции выхода F , а минтермы kt = а3а2а}а0 - как параметры, определяющие единичные значения функции выхода F в точках области опреде ления, то можно воспользоваться тем же самым размещением минтермов в клет ках карты, заменяя минтермы т1 = Ьфф на к1 (рис. 4.3.3).
Анализируя размещение минтеромов в карте, выделяем правильные конфигурации, покрывающие множество всех минтермов, записывая номера клеток, об -разующие эти конфигурации и соответствующие им простые импликанты (/).
Анализируя полученные результаты, не трудно заметить, что для нахождения минимальной ДНФ функции F нет необходимости выполнения подобных операций, поскольку в силу симметрии алгоритма функционирования компаратора, для нахождения простых импликант, определяющих функцию выхода FK достаточно в представлении каждой импликант, определяющих функцию F , заменить на bt, а литералы bt заменить на at. Однако, с целью обеспеченния контроля достоверности полученных результатов, при синтезе цифровых устройств с симметричным алгоритмом функционирования рекомендуется проделать как первую, а также вторую процедуру.
