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

На правах рукописи

КОРОБКОВА Елена Николаевна 4

ООЗ171638

МЕТОДЫ И АЛГОРИТМЫ АНАЛИЗА И СИНТЕЗА ЦИФРОВЫХ УСТРОЙСТВ, ОСНОВАННЫЕ НА ПРЕДСТАВЛЕНИИ ЛОГИЧЕСКИХ ФУНКЦИЙ В ОБОБЩЕННОЙ ФОРМЕ

Специальность 05.13 05 - «Элементы и устройства вычислительной техники и систем управления»

Автореферат диссертации на соисканне ученой степени кандидата технических наук

0 5кючда

Курск-2008

003171638

Работа выполнена на кафедре технической кибернетики в ГОУ ВПО «Белгородский государственный технологический университет им. В Г Шухова»

Научный руководитель

заслуженный деятель науки РФ, доктор технических наук, профессор Рубанов В Г.

Официальные оппоненты

доктор технических наук, профессор Лопин В Н

кандидат технических наук Жуковский Д В

Ведущая организация Тульский государственный технический университет

Зашита состоится « 27 » июня 2008 г в 14-00 часов на заседании диссертационного совета Д 212.105 02 при Курском государственном техническом университете по адресу. 305040, г. Курск, ул 50 лет Октября, 94 (конференц - зал)

Заверенные отзывы на автореферат в двух экземплярах направлять по адресу' 305040, г. Курск, ул 50 лет Октября, 94 Учёному секретарю диссертационного совета Д 212.105 02.

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

Автореферат разослан «26» мая 2008 г

Ученый секретарь диссертационного совета Д 212 105 02

ОБЩАЯ ХАРАКТЕРИСТИКА РА ЮТЫ

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

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

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

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

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

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

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

Работа выполнялась в рамках фундаментального исследования «Информационные технологии в управлении проюводственно-технологическими процессами в ПСМ» (Белгородский государственный технологический университет им В Г Шухова, № ГР 0120031 1387, г Белгород, 2003-2007 гг) в соответствии с планами и программами научно-исследовательских работ при непосредственном участии автора

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

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

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

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

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

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

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

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

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

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

- разработать инженерную методику нахождения булевых производных, осно-

ванную на сжатии области определения логических функций

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

народных и региональных научно-технических конференциях

Личный вклад соискателя Работы [3,12-15] написаны автором лично Вклад соискателя в работы, написанные в соавторстве, состоит в разработке основных версий алгоритма сжатия области определения логических функций [1,8,9] их программной реализации [17], анализе методов минимизации ОЛФ [11,16] и оценке достоверности её результатов [2,53, в разработке методов синтеза цифровых устройств [3,4,6], анализе методики нахождения булевых производных [7,10]

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

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

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

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

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

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

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

Структура и объем работы Диссертация состоит из введения, четырех разделов и заключения, изложенных на 229 страницах, содержит 80 рисунков, 5 таблиц, список литературы из 102 наименований и 13 приложений

ОСНОВНОЕСОДЕРЖАНИЕ РАБОТЫ

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

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

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

Второй раздел работы посвящён развитию нетрадиционного представления функций в форме ОЛФ и разработке методов их минимизации Отправным моментом вводимого понятия ОЛФ является более широкая трактовка канонического представления логических функций 2/-1

Р(Х,Р)= V К /,

| ■ о

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

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

При выборе оптимального варианта покрытия массивы каждого из параметров могут доопределяться массивами не только недоопределённых точек (если они имеются), но и единичных, поскольку единицу можно представить как 1V р1

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

Суть первого подхода состоит в представлении каждой функции 20), оп-

ределяющей исходные параметры в точках области определения, в минимальной ДНФ с последующим включением всех простых импликанг, входящих в представления / в минимально возможное число массивов (правильных конфигураций) с максимально возможным числом точек, кратным степени двойки, покрываемых простыми импликан-

ми, образуемыми литералами переменных множества X Достоинство подхода - компактность как при аналитических методах минимизации, так и программных, основанных на представлении простых импликант в виде т - мерных кубов При выделении правильных массивов, образованных т - мерными кубами, в них могут входить также точки, принадлежащие другим массивам, причем не только с данной размерностью кубов (от), но и любой большей размерности, а также точки, содержащие скрытые консен-сусные произведения Это обстоятельство обуславливает зависимость сложности процедуры выделения массивов от характера минимизируемых функций

С целью унификации метода предложен втором подход, суть которого сводится к представлению функций /(г^,, '„) в виде логической суммы минтермов, образуемых литералами к переменных (иг, = г4_,, г„), определяющих эти параметры (в СДНФ), с последующим покрытием множества минтермов минимальным числом простых импликант минимального ранга Покрытие точек области определения, содержащих логические суммы минтермов, осуществляется с учетом операции склеивания смежных минтермов, позволяя представить логическую сумму 2' минтермов произведением (к - г)-го ранга и покрыть его одной простой импликантой Для упрощения нахождения групп смежных минтермов и результата их склеивания предложено размещение минтермов, определяющих параметры в точках области определения, в форме упорядоченной дизъюнктивной матрицы с соседним размещением ее элементов (в коде Грея)

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

Суть предлагаемого алгоритма состоит в преобразовании исходной области определения функции Г(Х) в область меньшего размера путем разбиения множества всех переменных Х = [х. а,г л Л, определяющих исходную область, на два подмножества Хх с X и Х2 = X \ .V, Переменные подмножества X г трактуются как первичные, определяющие координаты точек сжатой области на данном разбиении, а переменные подмножества Х\. ~ как вторичные, определяющие значения функции в точках этой области Операцию этого преобразования будем называть сжатием исходной области определения заданной функции по переменным, включенным в подмножество Х\

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

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

Третий вариант основан на представлении заданной функции в декомпозиционной карте Декомпозиционная карта состоит из 21 столбцов и 2"~' строк Строки карты размечаются (раскрашиваются) интервалами значений переменных подмножества

Х2 > а столбцы - интервалами значений переменных подмножества Xi

Представленную таким образом карту предтагается рассматривать как упорядоченное множество, состоящее из 2"~к элементов (строк), каждый из которых представляет собой двоичный вектор длины 2к = {a^,},aJt е (0,1), j = 0,2""*-1, /=0,2'-1

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

В пятом варианте алгоритма исходным является задание единичных наборов в двоичной системе Каждое п- разрядное двоичное число рассматривается как кортеж, состоящий из двух двоичных чисел, одно из которых образовано значениями переменных подмножества Xi > а второе -Хг

Если в подмножество Xi включено к переменных с младшими индексами, то для нахождения координат точек сжатой области определения и значений функций в них необходимо поставить метку между разрядами переменных множества X, разделяя его на два подмножества - Хг и Х\, что соответствует делению исходного набора на 21 Двоичное число, образованное значениями п-к старших разрядов (частное), дает номер точки в сжатой области определения, а двоичные числа, образованные значениями к младших разрядов (остатки), дают индексы минтермов, логическая сумма которых определяет значение функции в этой точке При сжатии области определения по любым переменным необходимо выполнить перестановку разрядов, разместив переменные подмножества Xi в позиции младших, а переменные Хг ~ в позиции старших разрядов Рассмотренная версия алгоритма предпочтительна при программной реализации, как наиболее быстродействующая, поскольку операция двоичного деления сводится к сдвигу двоичных чисел, соответствующих единичным наборам, на к разрядов

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

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

На основе предложенных вариантов алгоритма разработаны программные средства реализации алгоритма сжатия области определения логических функций Средой разработки был выбран Borland Delphi 7

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

ложении к решению конкретных задач анализа и синтеза цифровых устройств

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

Предложен и исследован метод многовариантной минимизации ЛФ, основанный на сжатии области определения функции по комплементарным подмножествам А', с X и Х2 = с последующей минимизацией в каждой из полученных областей

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

Кроме того, по полученным результатам двух вариантов сжатия значение одной и той же простой импликанты (1,) можно вычислить четырьмя способами

/,=1^! П'^!, /,=!>,е-Ч ПЛ^!

Для оценки достоверности полученных результатов достаточно провести вычисления двумя способами в любом их сочетании При этом несовпадение результатов свидетельствует об ошибке, допущенной в процессе вычислений

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

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

В качестве иллюстрации в работе проведен синтез параллельного сравнивающего

устройства для сравнения двух четырехразрядных слов А = аъага^ог„ и В = Ь3ЬгЬхЬ0, трактуя минтермы к, = а]ага1а0, как координаты точек области определения функции выхода а минтермы т, = ЬфгЬ^Ьа - как параметры, определяющие единичные значения функции выхода в этих точках В результате синтеза получили список простых импли-кант, определяющих функцию К, /, = Ь1ЬгЬ1Ь1.а„, /2 = Ь,Ь1Ь1а1, I, =Ь,Ь2Ь„а[а1,,

/4 = 6,62а,, /5 = ЩЬ0а2а(1, /6 = й,¿,а2а,, /7 = Ща^а,,, /8 = ¿3а3, = 62я,а2, /ю = ¿Да^а,,

/,, =^ага,а0, /|2 = Ь11аха2а,а„, /,, = ЬгЬ,Ь„а,а„, /м = бДа,а,, /„ = ¿Дода,,

Список получен на основе представления функции в области определения, содержащей 16 точек, против 256, как это имело бы место при традиционном методе синтеза.

В силу симметрии операции сравнения двух слов для нахождения простых им-пликант, определяющих функцию /•",., достаточно в прслставлении каждой из импли-кант, определяющих функцию К,, литералы а, заменить на 6,, а литералы 6, - на а,

Однако, в целях обеспечения контроля достоверности полученных результатов при синтезе компараторов (как и других ЦУ с симметричным характером выполняемой операции над двумя входными словами) рекомендуется проделать аналогичные операции в обратной трактовке подмножеств переменных, т е в данном случае трактуя минтермы т,=Ьф2Ь\Ъа как координаты точек области определения а минтермы А, = а3йг2д,о0 - как параметры, определяющие единичные значения ^ в этих точках

Проведен синтезе многофункционального триггера, имеющего пять режимов хранения, синхронном установки в нулевое (Я), единичное (5) состояния, мультиплексной загрузки информации (£>,-£>,) по заданному трехразрядному адресу (А.А.А,,) и режим счета (Т) Решение задачи традиционным методом с представлением функции в таблице истинности, довольно громоздко, поскольку таблица будет содержать 2м наборов Представление сигналов К, 5,Т как первичных переменных, а адресных сигналов Л4 4, и сигналов £>,-£>? - как вторичных, с выбором в качестве независимых параметров переменных [),,0",(}", а зависимых - минтермов, образуемых литералами адресных переменных (ш, = Л2ДД,), позволило определить функцию возбуждения триггера

П = ЯТО"т„ V КТ()"ти V Д т, RvRS = Л[(£>" ® Т)т0 V О,т, V 5],

сведя число точек области определения до 8, чго существенно сократило время синтеза.

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

ГУ = ЖТ(2" V ШТ(Г V ТИП V Л? V Ж>, = Л\jLiQ©Т) V Ю V5] V 5Д

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

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

Существующие методы основаны на переборе и аналше возможных вариантов, различающихся привязкой режимов настройки к состояниям автомата во всех их сочетаниях Число вариантов, зависящее от числа состояний автомата к, числа режимов настройки Д, определяемого настроечными переменными агЛ о0, довольно велико даже при относительно небольших значениях к и Я В частности, для циклических формирователей временных интервалов с перестраиваемой длительностью в диапазоне от Г до Л Т это число равно к", для формирователей одиночных импульсов с тем же самым диапазоном перестройки это число равно кЩ-Яу Представление функции выхода в форме ОЛФ позволяет обеспечить выбор оптимального по сложности варианта схемной реализации функции выхода из значительно меньшего их числа

Суть предлагаемого метода Точки области определения функции выхода автомата отождествляются с его состояниями, азначение функции в каждой точке отмечается минтермом, образуемым литералами настроечных переменных {т1 = аг_,, а0), если эта точка входит во множество состояний автомата, определяющих единичные значения функции выхода для варианта настройки, определяемого этим минтермом

Такой подход позволяет режимы настройки, исходно заданные в виде формируемых временных интервалов, оптимальным образом разместить в точках области определения функции выхода (привязать к состояниям автомата)

На первом этапе размещение мингермов, определяющих режимы настройки, в точках области определения функции выхода выполняется без их конкретизации, а только лишь исходя из условия образования групп смежных минтермов с максимально возможным их числом в каждой группе, кратным степени двойки, покрываемых минимально возможным числом простых импликанг, образуемых переменными <2пА (?0, определяющими состояния автомата, с представлением минимальной ДНФ функции выхода в символьной форме для каждого варианта привязки Затем выполняется анализ полученных вариантов размещения и выбор из них оптимальною по сложности вариан-тас последующей конкретизацией (кодированием)минтермов

Ключевым моментом предложенного размещения является разбиение множества всех режимов настройки на два подмножества подмножество интервалов четной кратности и подмножество интервалов нечетной кратности, с привязкой начала формирования интервалов чётной кратности к одному из состояния автомата, а интервалов нечётной кратности - к следующему (логически соседнему) состоянию

При реализации автомата на суммирующих счетчиках интервалы четной кратности привязываются к чётному состоянию, а интервалы нечётной кратности - к следую-

щему нечётному состоянию При использовании вычитающих счётчиков - наоборот

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

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

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

1 Формирователь периодической последовательности временных интервалов с длиной цикла /с =16 и перестраиваемой длительностью, кратной периоду тактирующих импульсов (Г), в диапазоне перестройки Я от зтчения, равного Г, до 8Г

Г = ШШ V V & V & V б, V V а2дз02 V а2а&

2 Формирователь с длиной цикла к=16 и перестраиваемой длительностью, кратной Г/2, в диапазоне перестройки И отзначения, равного Г/2, до 16Г/2

р = Ч V с)ёД ёд va|QQlgQ) V С&&Д V V V ^ЙОД V а^Ш V

3 Формирователь периодической последовательности временных интервалов с длиной цикла £=10 и перестраиваемой длительностью в диапазоне й от Г до 8 Г

р=шш V «о^у&уе, V а,а&й V а,а&

4 Формирователь периодической последовательности временных интервалов с длиной цикла ¿=10 и перестраиваемой длительностью в диапазоне Л от Г до 6 Г

5 Формирователь одиночных импульсов с перестраиваемой длительностью, кратной периоду тактирующих импульсов, в диапазоне перестройки Л от Г до 8Г

«ой Vа2 02 VVаА 0

6 Формирователь одиночных импульсов с перестраиваемой длительностью, кратной Г/2, в диапазоне перестройки Л отзначения, равного Г/2, до 16Г/2

р = «ой V Щ V а£г<2@й V аг V язез V а2а, V а3а2 V а3а, Й20 V а3а2 <7,0,

7 Универсальный программируемый интервальный таймер с перестраиваемым числом состояний с программируемой длительностью

р = а&аа * я„ааа V * V V

V a2valvQ3vQl V о^я^а^а V V о^^уд^а-

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

Порядковый номер схемы автомата 1 2 3 4 5 6 7

Число анализируемых вариантов при традиционных методах синтеза 168 168 108 106 16!/8! 16!/8! 1б8

Число анализируемых вариантов при предложенном методе синтеза 8 8 8 5 5 4 8

Относительное время анализа вариантов привязки 8/16® 8/16® 8/10" 5/106 5/(16!/8!) 4/(1б!/8!) 8/16е

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

Проведено компьютерное моделирование схемы универсального программируемого таймера (рис. 1) в САПР Quartos - 2 фирмы Altera, которое подтвердило достоверность результатов синтеза и кодирования режимов настройки полученной схемы.

Результаты моделирования одного ш вариантов настройки, обеспечивающего четырёхкратное расширение длительности 14, 15, 0 - Знго состояний, показаны на рис. 2.

Рис. 1. Схема программируемого интервального таймера

Name

CLKJ

И a

S DJ S Q_01 Ш Q_02

Value at ia4m

eo

В 1011

из ui uo

7pt <apm .aapm 120,0»« isqora 200,0»» г<о,ота гвдог» зго,ог» ЗЕО,Ом

134г» -,1

л гиштлллжшг^^

ГЮр-1—

~TS—Х "0~ У"

Рис 2 Результаты моделирования четырехкратного расширения 14,15,0-3-го состояний

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

{Т1 = W4, V Wq vDi^Laj vE^La, vglvD^Qa, vE^ffa, ^mffa,

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

В ходе проведенного исследования установлено, что исходным шагом для нахождения значений частных производных функции F(X) по переменной * в точках её области определения является сжатие исходной области определения по этой переменной с последующими перечисленными ниже заменам и полученных значений функции F(X) в каждой точке сжатой области

-для нахождения значений убывающей частной булевой производной необходимо в представлении F{X) значения, равные 1, заменить 0, не изменяя других значений,

- для возрастающей -1 заменить 0, азначения литералов ^заменить инверсными (х,),

- для неориентированной - 1 заменить 0, азначения литералов заменить 1,

-для конъюнктивной частной булевой производной значения литералов заменить О,

- для двойственной - 0 и 1 заменить на противоположные, литералы заменить О,

- для неориентированной конъюнктивьой - 0 заменить 1, литералы заменить О

При нахождения убывающей и конъюнктивной векторных булевых производных область определения функции F(X) необходимо сжать по вектору переменных Л-,, по которому необходимо найти производную В точках сжатой области определения логическую сумму минтермов, образуемых литералами переменных подмножества Л-,, разделить на две группы - группу пар противоположных мшггермов, определяющих неориентированную конъюнктивную векторную булеву производную и группу оставшихся непарных мшггермов, определяющих убывающую векторную булеву производную

Для нахождения двойственной и возрастающей конъюнктивной векторных булевых производных необходимо перечисленные операции выполнить по отношению к единичным точкам инверсного значения функции (F(X))

В заключении приведены результаты и выводы проведенного исследования

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Рубанов В Г, Коробкова Е.Н Разработка алгоритма сжатия области определения логических функций // Труды современного гуманитарного университета Белго-родскийфилиал -Белгород 2000 -Вып 18 -С 105-112

2 Рубанов В Г, Коробкова ЕН Оценка достоверности минимизации логических функций//Телекоммуникации -2008 -№1 - С 44-48

3. Коробкова ЕН Приложение свойств обобщённых логических функций к синтезу многофункциональных триггерных устройств // XVIII научные чтения БГТУ им В Г Шухова Часть 6 - Белгород - 2007 - С 4042

4 Рубанов В Г, Коробкова ЕН Синтез универсальных логических модулей // XVIII научные чтения БГТУ им В Г Шухова Часть 6 -Белгород -2007 - С 108-111

5 Рубанов В Г, Коробкова ЕН Контроль достоверности минимизации логических функций //Методы и средства систем обработки информации Сборник научных статей Вып 4 Курский государственный технический университет -2007 -С 76-89

6 Рубанов В Г, Коробкова ЕН Разработка и анализ способов реализация логических функций на мультиплексорах // Сборник докладов на региональной научно-практической конференции «Современные проблемы технического, естественнонаучного и гуманитарного знания» - Губкин -2004 -С 194-198

7. Рубанов В Г, Коробкова Е Н Об одном способе нахождения булевых функций чувствительности // Радиоэлектронные и компьютерные системы — X НАКУ «ХАИ» -2003 -Вып 4 - С 139-144

8 Рубанов В Г, Коробкова ЕН Анализ основных форм алгоритма сжатия области определения логических функций // Тезисы докладов МНТК «Проектирование и производство самолетов и вертолетов» (г Алушта) - X • НАКУ «ХАИ» - 2003 - С 42

9 Рубанов В Г, Коробкова ЕН Два способа сжатия формы представления логических функций и их приложение к нахождению минимальных ДНФ // Тезисы докладов участников 16-й МНТК «Информационно-управляюшие системы на железнодорожном транспорте» (г Алушта)- X Украинская ГАЖТ -2003 -Вып 5 (43) - С 35-36

10 Рубанов В Г, Коробкова ЕН Метод нахождения аналитических форм некоторого класса булевых дифференциальных операторов // Тезисы докладов участников 15-й МНТК «Информационно-управляюшие системы на ЖД транспорте» (г Алушта). - X Украинская ГАЖТ -2002 -Вып 4, 5 (37) - С 19

11 Рубанов В Г, Коробкова ЕН Графоаналитический метод нахождения минимальных дизъюнктивных нормальных форм обобщённых логических функций // Системы обработки информации -X .НАНУ, ПАНМ,ХВУ -2002 -Вып 3(19).-С.46-53

12 Коробкова ЕН О применении метода сжатия области определения логических функций к нахождению булевых производных // Открытые информационные и компьютерные интегрированные технологии-X НАКУ -2003 -Вып 18-С 177-186

13 Коробкова ЕН Представление и минимизация недоопределенных логических функций в сжатых картах //Системы обработки информации -X ХВУ.-2003 -Вып 4 -С 35-50

14. Коробкова Е Н Нахождение кратных булевых производных с использованием операции сжатия их области определения И Открытые информационные и компьютерные интегрированные технологии - X НАКУ «ХАИ» - 2003 - Вып 20 - С 62-69

15 Коробкова ЕН Об одном алгоритме нахождения векторных булевых производных // Информационно-управляющие системы на железнодорожном транспорте -X . Украинская ГАЖТ - 2003 - Вып 6 -С. 3-7

16 Рубанов ВГ, Коробкова ЕН Визуально-агасбраичесгаш атоооб минимизации логических функций // Радиоэлехтроюжа и информатика. - Х„ ХНУРЭ - 20Ö4 -№2 -С 112-115

17 Коробкова Е Н, Шпак А С К программной реализации алгоритма сжатия области определения логических функций // Системы обработки информации - X • ХВУ -2006 - Вып 2(51).-С 51-61

Соискатель ' Коробкова Е.Н.

Уел печ л 1 0 Тираж 100 экз Заказ № Ъ Отпечатано в Белгородском государственном технологическом университете им В Г Шухова 308012, г Белгород, ул Костюкова, 46

ПЕРЕЧЕНЬ СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

РАЗДЕЛ 1. АНАЛИЗ МЕТОДОВ СИНТЕЗА ЦИФРОВЫХ УСТРОЙСТВ. ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЯ.

1.1. Краткий обзор и анализ методов синтеза цифровых устройств.

1.2. Постановка задачи исследования.

РАЗДЕЛ 2 ОСНОВНЫЕ СПОСОБЫ ПРЕДСТАВЛЕНИЯ И ПРЕОБРАЗОВАНИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ В ОБОБЩЕННОЙ ФОРМЕ.

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

2.2. Канонические формы представления ОЛФ.

2.3. Разработка и анализ алгоритма минимизации основных типов ОЛФ с независимыми параметрами в классе ДНФ.

2.4. Анализ алгоритма минимизации основных типов ОЛФ с зависимыми параметрами в классе ДНФ.

2.5. Представление и минимизация недоопределенных ОЛФ с зависимыми параметрами.

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

РАЗДЕЛ 3. РАЗРАБОТКА И АНАЛИЗ АЛГОРИТМА СЖАТИЯ

ОБЛАСТИ ОПРЕДЕЛЕНИЯ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ И ИХ-ПРЕДСТАВЛНИЕ В ФОРМЕ ОБОБЩЕННЫХ ФУНКЦИЙ С ЗАВИСИМЫМИ ПАРАМЕТРАМИ.

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

3.2. Неполное разложения Шеннона и его приложение к представлению функций в обобщенной форме.

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

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

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

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

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

3.8. Принцип двойственности алгоритма сжатия области определения логических функций.

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

РАЗДЕЛ 4. МЕТОДЫ СИНТЕЗА И АНАЛИЗА ЦИФРОВЫХ УСТРОЙСТВ, ОСНОВАННЫЕ НА ПРЕДСТАВЛЕНИИ ФУНКЦИЙ В ОБОБЩЁННОЙ ФОРМЕ.

4.1. Разработка и анализ метода многоверсионной минимизации.

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

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

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

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

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

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

Работа выполнялась в рамках фундаментального исследования «Информационные технологии в управлении производственно-технологическими процессами в ПСМ» (Белгородский государственный технологический университете им. В .Г. Шухова, № ГР 01200311387, г. Белгород, 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. Основные теоретические положения и результаты, полученные в работе, могут найти дальнейшее продолжение и развитие при разработке и преобразовании алгоритмов, используя предложенный в работе подход с разбиением множества условий на два подмножества и сжатием исходной области определения алгоритма по одному из подмножеств с последующим представлением заданного алгоритма в каждой точке сжатой области определения в виде произведения соответствующих операторов и логических условий.

1. Бибило П.Н. Синтез комбинационных ПЛМ-структур для СБИС. Минск: Наука и техника, 1992. - 232с.

2. Биргер А.Г. Многозначное дедуктивное моделирование цифровых устройств // Автоматика и вычислительная техника. 1982. №4. С.77-82.

3. Бохманн Д., Постхоф X. Двоичные динамические системы.- М.: Энергоатомиздат, 1986,- 400с.

4. Виленкин Н.Я. Популярная комбинаторика.- М.: Наука, 1975. 208 с.

5. Глушков В.М. Некоторые проблемы синтеза цифровых автоматов /г Вычислительная математика и математическая физика, 1961, т.1, №3. — С. 371-411.

6. Глушков В.М. Об одном алгоритме синтеза конечных автоматов // Украинский математический журнал, 1960, т. 12, №2. С. 147-156.

7. Глушков В.М. Об одном методе анализа абстрактных автоматов // ДАН УССР, 1960, т. 12, №9. С. 1151-1154.

8. Глушков В.М. Синтез цифровых автоматов.- М.:Физматгиз, 1962.-476 с.

9. Гольдберг Е.И. Метод оптимальной реализации на ПЛМ цифровых устройств, описываемых многозначными функциями.- Дис.канд.техн.наук: 05.13.12.-Минск, Институт технической кибернетики АН Беларуси, 1995.177 с.

10. Девятков В.В. Методы реализации конечных автоматов на сдвиговых, регистрах. М.: Энергия, 1974. - 80 с.

11. Денисенко Е. Л. Иерархический синтез асинхронных автоматах на программируемых логических интегральных схемах (ПЛИС) с учетом ограничений // УСиМ, 1997, №1/3, С.72-77.

12. Денисенко Е.Л. Сеть параллельных автоматов // УСиМ, 1998, №3. -С. 3436.

13. Дж.Ф.Уэйкерли. Проектирование цифровых устройств. М.: Постмаркет, 2002. т. 1 - 544 е., т. II-528 с.

14. Закревский А.Д. Алгоритмы синтеза дискретных автоматов. Москва: Наука, 1971.-512 с.

15. Закревский А.Д. Логический синтез каскадных схем. Москва: Наука, 1981.-416 с.

16. Коробкова Е.Н. Приложение свойств обобщённых логических функций к синтезу многофункциональных триггерных устройств // XVIII научные чтения. БГТУ им. В.Г. Шухова. Часть 6. Белгород. - 2007. - С. 40-42.

17. Коробкова Е.Н. О применении метода сжатия области определений логических функций к нахождению булевых производных // Открытые информационные и компьютерные интегрированные технологии-Харьков: НАКУ. -2003. Вып. 18.- С. 177-186.

18. Коробкова Е.Н. Представление и минимизация недоопределенных логических функций в сжатых картах // Системы обработки информации. —19