Электронная библиотека Веда
Цели библиотеки
Скачать бесплатно
Доставка литературы
Доставка диссертаций
Размещение литературы
Контактные данные
Я ищу:
Библиотечный каталог российских и украинских диссертаций

Вы находитесь:
Диссертационные работы России
Технические науки
Элементы и устройства вычислительной техники и систем управления

Диссертационная работа:

Коробкова Елена Николаевна. Методы и алгоритмы анализа и синтеза цифровых устройств, основанные на представлении логических функций в обобщенной форме : диссертация ... кандидата технических наук : 05.13.05 / Коробкова Елена Николаевна; [Место защиты: Кур. гос. техн. ун-т]. - Белгород, 2008. - 229 с. : ил. + Прил. (146 с. :ил.). РГБ ОД, 61:08-5/933

смотреть содержание
смотреть введение
Содержание к работе:

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

ВВЕДЕНИЕ 6

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

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

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

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

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

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

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

с независимыми параметрами в классе ДНФ 35

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

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

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

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

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

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

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

.1

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

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

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

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

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

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

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

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

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

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

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

  3. Разработка методов и практических рекомендаций по использованию свойств ОЛФ при синтезе цифровых устройств с перестраиваемыми параметрами 104

  1. Вводные замечания 104

  2. Анализ алгоритма привязки и размещения диапазона перестройки

ЦА ПП с программируемой длительностью временных интервалов 106

4.4.3. Представление диапазона перестройки в картах с соседним коди-
рованием', оптимизация его размещения 110

4.4.4. Разработка алгоритма оптимального кодирования минтермов,

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

  1. Приложение свойств ОЛФ с недоопределенными параметрами к синтезу НА с перестраиваемой длительностью формируемых временных интервалов 138

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

  1. Синтез многофункционального ЦА ПП (универсального программируемого интервального таймера) 150

  2. Формирователь одиночных импульсов с перестраиваемой длительностью в заданном временном интервале 159

  3. Формирователь одиночных интервалов времени с перестраиваемой длительностью, кратной половине периода тактирующих импульсов... 170

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

  2. Синтез многофункциональных триггерных устройств 187

  1. Разработка и анализ метода нахождения ориентированных и неориентированных частных булевых производных 193

  2. Разработка и анализ метода нахождения кратных булевых производных 201

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

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

ЗАКЛЮЧЕНИЕ 218

СПИСОК ЛИТЕРАТУРЫ 223

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

БП - булевы производные

БФ - булевы функции

ДНФ - дизъюнктивная нормальная форма

ИС - интегральные схемы

ЛФ — логические функции

МДНФ - минимальная дизъюнктивная нормальная форма

МКНФ - минимальная конъюнктивная нормальная форма

ОЗУ — оперативное запоминающее устройство

ОЛФ - обобщённые логические функции

ПЛИС - программируемые логические интегральные схемы

ПИТ - программируемые интервальные таймеры

САПР - системы автоматизированного проектирования

СДНФ - совершенная дизъюнктивная нормальная форма

СКНФ - совершенная конъюнктивная нормальная форма

УЛМ - универсальный логический модуль <

ЦА — цифровой автомат

ЦА1111 - цифровой автомат с перестраиваемыми параметрами

DC - decoder

CPLD - Complex Programmable Logic Devices

FPGA - Field Programmable Gate Array

PLD — Programmable Logic Devices

Введение к работе:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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,5], в разработке методов синтеза цифровых устройств [3,4,6], анализе методики нахождения булевых производных [7,10].

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

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

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

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

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

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

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

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

Подобные работы
Петров Андрей Борисович
Методы и алгоритмы анализа элементов устройств вычислительной техники и систем управления на предсказуемость поведения
Амосов Владимир Владимирович
Машинный анализ и синтез доменных устройств
Гильмутдинов Анис Харисович
Анализ и синтез неоднородных резистивно-емкостных элементов с распределенными параметрами и их приложения в устройствах обработки информации
Калуцкий Игорь Владимирович
Метод, алгоритмы синтеза и структурно-функциональная организация отказоустойчивых нейросетевых логических устройств
Кокоулин Андрей Николаевич
Методы, алгоритмы и программы повышения надежности хранения информации на магнитных дисках
Плахов Александр Геннадьевич
Методы, алгоритмы и устройства для покадрового кодирования и передачи видеоданных по радиоканалам с низкой пропускной способностью
Панищев Владимир Славиевич
Методы, высокопроизводительные алгоритмы и устройства обработки изображений с использованием нейроподобных структур
Медведев Артем Викторович
Методы и алгоритмы адаптации и обеспечения многофункциональности системы технического зрения наземных подвижных объектов
Чжао Цзюньцай
Исследование, разработка и аппаратная реализация методов и алгоритмов построения трёхмерных изображений по непараллельным сечениям
Бойков Александр Юрьевич
Разработка метода и алгоритма функционирования интеллектуального устройства контроля влагосодержания светлых нефтепродуктов на основе некогерентных волоконно-оптических преобразователей

© Научная электронная библиотека «Веда», 2003-2013.
info@lib.ua-ru.net