Введение
1. Методы минимизации функций одной переменной 6
1.1 Понятие оптимизации функций 6
1.1.1 Определение границ объекта оптимизации 7
1.1.2 Выбор управляемых переменных 8
1.1.3 Определение ограничений на управляемые переменные 8
1.1.4 Выбор числового критерия оптимизации 9
1.1.5 Формулировка математической задачи оптимизации 10
1.2 Постановка задачи на проектирование 15
2 Выбор средств разработки и проектирование программного средства 16
2.1 Выбор языка и среды программирования 16
2.2 Описание основных алгоритмов 24
2.2.1 Алгоритм оптимизации центральной силы 24
2.2.2 Гармонический поиск 24
2.2.3 Гравитационный поиск 27
2.3 Разработка структуры программы 30
2.3.1 Класс «TFunctionVariable» 33
2.3.2 Класс «TCustomFunction» 34
2.3.3 Класс «TCustomFunction» 35
2.3.4 Класс «TParticleBasedSearchEngine» 37
2.3.5 Класс «TCentralForceOptimizationEngine» 38
2.3.6 Класс «THarmonySearchEngine» 39
2.3.7 Класс «TGravitationalSearchEngine» 39
3 Анализ полученного решения 41
3.1 Описание работы программы 41
3.2 Сравнительный анализ рассмотренных методов 48
Заключение 50
Список использованной литературы 53
Приложение
Широкое внедрение вычислительной техники и систем управления во все сферы человеческой деятельности и усложнение задач, решаемых этими системами, требуют совершенствования существующих методов логического проектирования цифровых устройств и разработки новых. Логическое проектирование при этом понимается в широком смысле, включая не только статику систем, т.е. их структуру и функциональные связи, но и анализ динамики как на уровне структуры, а также на уровне переходных процессов, связанную с изменением временными характеристиками элементов и переменных. Поэтому исследования, направленные на развитие методов логического проектирования цифровых устройств, обеспечивающих упрощение процедуры проектирования, улучшение основных характеристик ЦУ, а также снижение времени и стоимости разработки никогда не потеряют своей актуальности. [1, 2]
Проблеме логического проектирования цифровых устройств посвящено большое число работ, большинство из них основано на представлении логических функций (ЛФ) в точках области их определении значениями логического 0 или 1.
В то же время со многими положительными сторонами такого представления оно имеет и ряд отрицательных, а именно при большом числе переменных, так как при возрастании числа переменных происходит обвальное увеличением количества точек области определения и, как следствие, затруднение в процедуре синтеза и анализа, связанное с решением объёмных совмещенных задач. Эти недостатки существенны не только при аналитических методах, но также при использований программных средств анализа и синтеза. [2, 12-15]
А так же многие исследователи пошли по пути нестандартных подходов к преобразованию и представлению логических функций, основанном на концепции многозначного алфавита, конечных логических
К предлагаемому нетрадиционному способу можно отнести представление функций одной переменной в форме обобщённых, когда значения функции в точках её области определения заданы не только значением логического 0 и 1, но и независимыми или зависимыми параметрами. В частности, к такой форме можно отнести неполное разложение Шеннона. Вместе с тем, коэффициенты, образуемые литералами переменных, по которым выполняется разложение, можно рассмотреть как координаты точек области определения, а остаточные функции — как параметра определяющие значения функции в этих точках. Такой подход ведёт к существенному уменьшению числа точек области определения, что служит облегчению процедуры логического проектирования цифровых устройств, учитывая, связанные с представлением и минимизацией функций, синтезом комбинационных схем и автоматов с памятью, решением задач динамики цифровых устройств, связанных с анализом состязаний в комбинационных схемах, а также нахождением булевых производных.
Цель работы — разработка методов и алгоритмов логического проектирования цифровых устройств, обеспечивающих упрощение процедуры и снижение времени проектирования, основанных на представлении и преобразовании функций одной переменной в обобщённой форме.
Поставленная цель работы предполагает решение следующих задач:
- провести анализ современного состояния методов логического проектирования цифровых устройств;
- разработать программное обеспечение для сравнения
эвристических методов минимизации функций.
В дипломной работе выполнено теоретическое обобщение и получены новые решения научно-прикладных задач, которые состоят в развитии известных и разработке новых методов и алгоритмов анализа и синтеза цифровых устройств вычислительной техники и систем управления.
Предложен и исследован метод многоверсионной минимизации традиционных переключательных функций, основанный на сжатии области определения функции по комплементарным подмножествам с последующей минимизацией в каждой из полученных областей. В ходе исследования установлено, что при корректном выделении массива минтермов, которому соответствует простая импликанта минимально возможного ранга, номера точек, образующие такой массив в области определения, сжатой по одному из подмножеств переменных, совпадают с индексами минтермов, образующих массив в области определения, сжатой по комплементарному подмножеству переменных. Несовпадение результатов свидетельствует об ошибке, допущенной на этапе выделения правильных конфигураций, результатов их описания или процедуре минимизации.
Предложен и исследован метод анализа состязаний в комбинационных схемах, основанный на последовательном сжатии области определения функции по каждой из переменных. При этом установлено, что представление функций в форме ОЛФ в этом случае выступает как значительно большее, чем простое сокращение числа точек области определения, поскольку позволяет определить наличие или отсутствие состязаний по каждой из переменных непосредственно по характеру полученных значений функции в точках сжатой области определения.
При синтезе комбинационных схем (многоразрядных параллельных сравнивающих устройств), а также многофункциональных триггерных устройств представление функций в форме ОЛФ позволяет уменьшить число точек области определения, что упрощает процедуру проектирования за счёт
При проектировании конечных автоматов Мили, в частности, формирователей временных интервалов с перестраиваемыми параметрами выходных сигналов, основной проблемой является не собственно синтез автомата как такового, а нахождение оптимального по сложности представления функций выхода автомата. Представление функций в форме ОЛФ, обеспечило не только уменьшение числа точек области определения, что привело к упрощению процедуры проектирования, но и позволило оптимальным образом привязать режимы настройки формирователей к его состояниям, что обеспечило выбор оптимального варианта.
Проведенное компьютерное моделирование одного из вариантов программируемого интервального таймера с перестраиваемой длительностью тактов, подтвердило достоверность полученных результатов его синтеза.
При синтезе универсальных логических модулей с памятью, реализующего программируемый список функций от двух переменных, выполненного в виде триггера Эрла, представление функций в форме ОЛФ позволило выполнить оптимальное их размещение в точках области определения, которому соответствует минимальное число простых импликант, определяющих структуру УЛМ с памятью, исключив процедуру перебора.
Представление функций в форме ОЛФ дало возможность упростить инженерную методику нахождения частных, кратных и векторных булевых производных, используемых при моделировании неисправностей, декомпозиции булевых функций, задачи обнаружения статических и динамических ошибок в комбинационных схемах, и т.д., за счёт исключения аналитических представлений к связанных с ними преобразований.
Практическая ценность работы заключается в доведении полученных теоретических результатов до конкретных алгоритмов, методов, программ и схем цифровых устройств, проиллюстрированных примерами. Основные практические результаты сводятся к следующему:
- представление традиционных функций одной переменной в форме ОЛФ позволяет упростить процедуру минимизации, а разработанные программные средства сжатия области определения дают возможность использования их в пакетах систем автоматизированного проектирования;
- предложенный метод многовариантной минимизации функций одной переменной позволяет обеспечить контроль достоверности проведенных преобразований и минимальность полученных результатов.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
