Методы и алгоритмы анализа и синтеза цифровых устройств, основанные на представлении логических функций в обобщенной форме

Актуальность темы

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

Проблеме логического проектирования цифровых устройств посвящено большое число работ, среди которых фундаментальными являются работы, выполненные В. М. Глушковым, А. Д. Закревским, С. И. Барановым, Д. А. Поспеловым, С. В. Новиковым, Е. П. Угрюмовым, В. В. Соловьёвым, Е. Вейчем, М. Карнс, В. Квайном, Г. Мили, Е. Муром, К. Шенноном и др. Большинство из этих работ основано на представлении логическихфункций (ЛФ) в точках области их определении значениями логического 0 или 1.

Наряду со многими достоинствами такого представления оно имеет и ряд недостатков, особенно при большом числе переменных, поскольку при увеличении числа переменных происходит лавинообразное увеличением количества точек области определения и, как следствие, усложнение процедуры анализа и синтеза, связанное с решением объёмных комбинаторных задач. Эти недостатки су,-щественны не только при аналитических методах, но также и при использований программных средств анализа и синтеза.

В то же время многие исследователи: С. В. Яблонский, В. П. Сигорский, В. П. Тарасенко, П. Н. Бибило, А. А. Шалыто, Е. Мак-Класки, Р. Брайтон и др. — пошли по пути нетрадиционных подходов к представлению и преобразованию логичег ских функций, основанном на концепции многозначного алфавита, конечны>: предикатов, логических шкал, интерполяционных и арифметических полиномов, спектрального представления и др., которые в ряде случаев дали положительный эффект как при анализе, а также синтезе цифровых устройств.

К предлагаемому нетрадиционному способу можно отнести представление логических функций в форме обобщённых, когда значения функции в точках её области определения заданы не только значением логического 0 и 1, но и независимыми или зависимыми параметрами. В частности, к такой форме можно отнести неполное разложение Шеннона. При этом, коэффициенты, образуемые литералами переменных, по которым выполняется разложение, можно трактовать как координаты точек области определения, а остаточные функции — как параметра определяющие значения функции в этих точках. Такой подход ведёт к существенному уменьшению числа точек области определения, обеспечивая упрощение процедуры логического проектирования цифровых устройств, включая вопросы, связанные с представлением и минимизацией функций, синтезом комбинационных схем и автоматов с памятью, решением задач динамики цифровых устройств, связанных с анализом состязаний в комбинационных схемах, а также нахождением булевых производных.

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

Работа выполнялась в рамках фундаментального исследования «Информационные технологии в управлении производственно-технологическими процессами в ПСМ» (Белгородский государственный технологический университете им. В .Г. Шухова, № ГР 1 200 311 387, г. Белгород, 2003;2007 гг.), в соответствии L планами и программами научно-исследовательских работ при непосредственном участии автора.

Объект исследования — процессы разработки методов, алгоритмов, а также программно-технических средств логического проектирования цифровых устройств вычислительной техники и систем управления.

Предмет исследования — методы и алгоритмы анализа и синтеза цифровых устройств вычислительной техники и систем управления на основе обобщённой формы представления логических функций.

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

Поставленная цель работы предполагает решение следующих задач:

— провестианализ современного состояния методов логического проектирования цифровых устройств;

— разработать методы минимизации обобщённых логических функции (ОЛФ) с независимыми и зависимыми параметрами;

— разработать алгоритм и программные средства преобразования традиционных логических функций в форму ОЛФ с зависимыми параметрами, основанные на сжатии их области определения;

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

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

— разработать методы синтеза комбинационных схем, многофункциональных триггерных устройств, УЛМ с памятью, а также методы нахождение оптимального представления функций выхода автоматов Мили с перестраиваемыми параметрами, основанные на представлении логических функций в форме ОЛФ;

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

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

Научная новизна работы состоит в следующем:

1. Впервые предложена расширенная трактовка канонического представления логических функций (СДНФ) в форме ОЛФ, разработаны и исследованы методы минимизации различных типов обобщённых логических функций с независимыми и зависимыми параметрами.

2. Впервые разработан алгоритм преобразования традиционных логических функций в форму обобщённых функций с зависимыми параметрами, основанный на разбиении множества всех переменных на два подмножества, одно из K0T0pbiv определяет координаты точек сжатой области, а второе — значения функции в этих точках, обеспечивая уменьшение числа точек области определения, и, как следствие, сокращение времени их обработки.

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

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

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

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

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

— представление традиционных логических функций в форме обобщённых позволяет упростить процедуру минимизации, а разработанные программные средства сжатия области определения дают возможность использования их в пакетах САПР;

— предложенный метод многовариантной минимизации логических функ^ ций позволяет обеспечить контроль достоверности проведенных преобразований и минимальность полученных результатов;

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

— представление функций в форме ОЛФ при синтезе комбинационных схем и многофункциональных триггерных устройств позволило упростить процедуру синтеза за счёт сокращения числа точек области определения (таблиц функционирования) и, как следствие, сократить время проектированияч.

— использование представления логических функций в форме ОЛФ при нахождении оптимального по сложности представления функций выхода цифровых автоматов с перестраиваемыми параметрами позволило упростить процедуру синтеза за счёт сокращения числа точек области определения, а также обеспечить целенаправленный выбор вариантов, существенно сократив перебор и, как след.: ствие, сократить время проектирования в целом;

— представление функций в форме ОЛФ при синтезе универсальных логических модулей с памятью, реализующих программируемый список функций, позволило выполнить оптимальную реализацию настройки модулей на выполнение списка функций за счёт оптимального размещения функций в области определения, исключив процедуру перебора вариантов настройки;

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

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

Апробация работы. Основные положения диссертации и её научные результаты докладывались и получили положительную оценку: на международной научно-практической конференции «Научные исследования, наносистемы и ре сурсосберегающие технологии в стройиндустрии» (г. Белгород, 2007 г.) — на региональной НТК «Современные проблемы технического, естественно — научного и гуманитарного знания» (г. Губкин, 2004 г.) — на 15 и 16-й МНТК «Информацион-но-управляюшие системы на железнодорожном транспорте» (г. Алушта, 2002, 2003 гг.) — на МНТК «Проектирование и производство самолетов и вертолетов» (г. Алушта, 2003 г.) — на 1-й, 2-й и 3-й МНТК «Гарантоспособные системы, сервисы и технологии» (г. Полтава, 2006 г., г. Кировоград, 2007, 2008 гг.).

Реализация и внедрение. Результаты работы внедрены на предприятии ЗАО «Сокол-АТС», г. Белгород, Россияв ГНТТП «Объединение Коммунар» НТ СКБ «ПОЛИСВИТ», г. Харьков, Украина, а также используются в БГТУ им. В. Г. Шухова на кафедре технической кибернетики в учебных дисциплинах: «Теорй,. цифровых автоматов», «Архитектура ЭВМ и систем», «Схемотехника электронных устройств», «Микропроцессорная техника».

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

Личный вклад соискателя. Работы [16−24] написаны автором лично. Вклад соискателя в работы, написанные в соавторстве, состоит: в разработке основных вариантов алгоритма сжатия области определения ЛФ [40,46,47] их программной реализации [25], анализе методов минимизации ОЛФ [49−51] и оценке достоверности её результатов [41,43], в разработке методов синтеза ЦУ [42,44], анализе методики нахождения булевых производных [26,45,48,53].

На защиту выносятся:

1. Представление логических функций в форме ОЛФ с независимыми и зависимыми параметрами, методы их минимизации.

2. Алгоритм преобразования традиционных логических функций в форму обобщённых логических функций с зависимыми параметрами.

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

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

5. Методы синтеза комбинационных схем, многофункциональных триггер-ных устройств, универсальных логических модулей с памятью, а также автоматов Мили с перестраиваемыми параметрами выходных сигналов, основанные на представлении функций в форме ОЛФ.

6. Инженерная методика нахождения булевых производных, основанная на сжатии области определения заданной функции.

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

4.8. Выводы по разделу.

1. В ходе исследования, проведенного в этом разделе, установлено, что представление функций в форме ОЛФ в одних случаях выступает просто как способ уменьшения числа точек области определения, что само по себе немаловажно, поскольку позволило упростить процедуру проектировании за счёт сокращения размера таблиц функционирования устройств и, как следствие, сократить времл проектирования. В других случаях такое представление выступает как значительч ' но большее, чем простое сокращение числа точек, обеспечивая возможность анализа представленных функций с последующим упрощением процедуры их преобразования и оптимизации по заданному критерию.

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

3. При исследовании предложенного метода анализа состязаний в комбинационных схемах установлено, что схема, построенная в соответствии с минимальной ДНФ, не содержит состязания по переменной х, если функция в точках области определения, сжатой по переменной х, представлена не более чем тремя сочетаниями её значений. Если же функция представлена всеми значениями, то в схеме состязания возможны, однако только в том случае, если некоторые 1 покрыты её отдельными составляющими.

4. При синтезе комбинационных схем, а также многофункциональных триггеров представление функций в форме ОЛФ позволило обеспечить уменьшение числа точек области определения в 2 Г раз (г число переменных, принятых за параметры), избежать процедуры декомпозиции при нахождении функций и, как следствие, упростить процедуру синтеза в целом, что существенно сократило время их проектирования.

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

4. Представление функций настройки в форме ОЛФ при синтезе УЛМ с па мятью с последующим разбиением множества минтермов, определяющих эти функции, на несколько подмножеств, удовлетворяющих условиям, обеспечивак щих покрытие каждого из выделенных подмножеств произведением минимального ранга, позволило решить задачу, не прибегая к перебору вариантов.

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

Новые научные результаты, полученные в данном разделе, нашли отражс ние в работах [16, 17, 19, 20, 24, 26, 41−45, 15, 48, 52].

ЗАКЛЮЧЕНИЕ

.

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

В ходе решения поставленных в диссертационной работе задач были получены следующие результаты.

1. Введено понятие ОЛФ, отправным моментом которого является более широкая трактовка канонического представления логических функций, полагая что значения функции в точках области определения могут быть равны не только логическому 0 и 1, но и некоторым параметрам, которые, в свою очередь, могу** быть независимыми или зависимыми от других переменных.

2. Разработаны и исследованы методы минимизации ОЛФ. При разработке метода минимизации ОЛФ с независимыми параметрами предложено^{множество} значений заданной функции разбить на пересекающиеся подмножества, одно из которых содержит нулевые и все единичные значения, а каждое из остальных — нулевые значения и один из параметров, что позволило представить минимальную ДНФ заданной ОЛФ в виде логической суммы минимальных ДНФ состав' ляющих. При разработке и анализе метода минимизации ОЛФ с зависимыми параметрами предложено два подхода, один из которых состоит в представлений каждой функции, определяющей исходные параметры в точках области определения, в минимальной ДНФ, а второй — в представлении каждой функций в СДНФ, с последующим покрытием ненулевых значений функции минимальным числом простых импликант.

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

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

5. Предложен и исследован метод анализа состязаний в комбинационных схемах, основанный на последовательном сжатии области определения функции по каждой из переменных. При этом установлено, что представление функций в форме ОЛФ в этом случае выступает как значительно большее, чем простое сокращение числа точек области определения, поскольку позволяет определить наличие или отсутствие состязаний по каждой из переменных непосредственно по характеру полученных значений функции в точках сжатой области определения.

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

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

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

9. При синтезе универсальных логических модулей с памятью, реализующего программируемый список функций от двух переменных, выполненного в вид^ триггера Эрла, представление функций в форме ОЛФ позволило выполнить оптимальное их размещение в точках области определения, которому соответствуе'-' минимальное число простых импликант, определяющих структуру УЛМ с памятью, исключив процедуру перебора.

10. Представление функций в форме ОЛФ дало возможность упростить инженерную методику нахождения частных, кратных и векторных булевых производных, используемых при моделировании неисправностей, декомпозиции булевых функций, задачи обнаружения статических и динамических ошибок в комбинационных схемах, и т. д., за счёт исключения аналитических представлений L связанных с ними преобразований.

11. Практическая ценность диссертации заключается в доведении пол^ ченных теоретических результатов до конкретных алгоритмов, методов, программ и схем цифровых устройств, проиллюстрированных примерами. Основные практические результаты сводятся к следующему:

— представление традиционных логических функций в форме ОЛФ позволяет упростить процедуру минимизации, а разработанные программные средства сжатия области определения дают возможность использования их в пакетах систем автоматизированного проектирования;

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

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

— представление функций в форме ОЛФ при синтезе комбинационных схем и многофункциональных триггерных устройств позволило упростить процедуру синтеза путём сокращения числа точек области определения (таблиц функционирования) и, как следствие, сократить время проектирования;

— использование свойств ОЛФ при нахождении оптимального представления функций выхода цифровых автоматов с перестраиваемыми параметрами дало возможность не только сократить число точек области определения, но и обеспечить целенаправленный выбор вариантов, существенно сократив перебор их и анализ, и, как следствие, сократить время проектирования в целом;

— представление функций в форме ОЛФ при синтезе УЛМ с памятью, реализующих программируемый список функций, позволило выполнить оптимальную реализацию настройки модулей на выполнение списка функций за счёт оптимального размещения функций в области определения, исключив процедуру перебора;

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

12. Достоверность научных положений, выводов и рекомендаций, приведенных в диссертации, подтверждается:

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

— результатами, полученными при разработке универсального логического модуля с памятью, которые совпали с аналогичными результатами структуры многофункционального логического модуля, используемого в типовом АЛУ (микросхема 1533 ИПЗ), что также подтвердило достоверность полученных теоретических результатов проведенного исследования;

— результатами их практического внедрения на предприятии ЗАО «Сокол-АТС» г. Белгород при разработке инженерной методики контроля и диагностик" цифровых АТС «Квант-Е-Сокол», а также при решении задач синтеза цифровых устройств со встроенными блоками контроля работоспособности;

— результатами их практического внедрения при разработке программно-технического комплекса для системы контроля защиты и управления турбинами малой мощности (6−24 МВТ) — ПТК СКРЗТ-6(12 в организации ГНЛП «Объединение Коммунар» г. Харьков;

— результатами проведенного компьютерного моделирования многофункционального таймера, разработанного в рамках проекта ПТК СКРЗТ-6(12) в организации ГНПП «Объединение Коммунар» г. Харьков.

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