Синтез в базисе ФПТ при помощи генетических алгоритмов

Размещено на http://www.allbest.ru/

Синтез в базисе ФПТ при помощи генетических алгоритмов

А.Н. Шляков

Аннотация

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

Ключевые слова: генетический алгоритм; эвристический алгоритм; функционально-полный толерантный элемент (ФПТ); избыточный базис, синтез.

Введение

© Шляков А.Н., 2013Для оптимального синтеза дискретных логических устройств приходится обращаться к алгоритмам переборного характера, что сопровождается большим объемом вычислительной работы или невозможно. Классические методы позволяют получать оптимальное решение "вручную" только для задач небольшой размерности. На практике синтез осуществляется при помощи эвристических алгоритмов, которые ищут неоптимальное, но удовлетворяющее поставленным требованиям решение [1]. алгоритм оптимизация моделирование

Предлагается способ синтеза схем при помощи генетических алгоритмов. Синтез осуществлялся в избыточных базисах (в базисах так называемых функционально-полных толерантных элементов [2]).

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

Функционально полный толерантный (ФПТ) элемент - это комбинационный элемент с избыточным базисом. ФПТ элемент обеспечивает сохранение базиса с точки зрения теоремы Поста при однократных константных отказах в транзисторах, следовательно, реализация функций на его основе эффективней, чем на основе классических элементов. Базис ФПТ имеет вид ().

Описание алгоритма

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

В данной реализации биты с 1 по 12 описывают первый ФПТ элемент, биты 13-24 - второй и так далее.

Рассмотрим часть хромосомы, описывающую первый ФПТ элемент. Биты 1, 4, 7, 10 обозначают, что именно подается на каждый вход - переменная (1) или выход другого элемента (0). В оставшихся битах закодирована переменная или ФПТ элемент. Пусть первые 3 бита имеют значение 100, тогда на первый вход подается переменная A.

Недостаток такой хромосомы состоит в том, что большинство двоичных строк не соответствуют допустимой схеме. Следо-вательно, необходимо выполнять проверку хромосомы на корректность.

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

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

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

Затем осуществляется расчет таблиц истинности полученных корректных хромосом и сравнение их с заданной. В случае их совпадения полученная хромосома является вариантом реализации заданной функции в базисе ФПТ.

В данной реализации условием завершения алгоритма является повторение его заданное количество раз.

Была выполнена проверка программного продукта и рассчитана вероятность нахождения результата для функций от 1 до 4 переменных. Алгоритм завершался после прохождения 20 поколений. Использовались функции , , , . Для первой и второй функций результат получен в 19 случаях, третьей - в 18, четвертой - в 15. Результат показан на рис. 1.

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

Синтез схем

Рассмотрим синтез схемы с использова-нием созданного программного продукта на примере функции (abacbc), таблица истинности которой имеет вид (табл. 1):

Таблица 1. Обобщенная таблица истинности заданной функции

При помощи созданного программного продукта для функции (abacbc) получена хромосома (110110100101 101110100100 000110001111 000000110001), в которой закодирована следующая схема (рис. 2).

Рис. 2. Синтезированная схема функции (abacbc)

Выполним проверку данной схемы, ис-пользуя таблицу истинности (табл. 2).

Таблица 2. Таблица истинности получившейся схемы

Получившаяся таблица совпадает с за-данной изначально, следовательно синтезированная схема является реализацией заданной функции в базисе ФПТ 2. Сложность схемы - 3 (количество ФПТ элементов), задержка - 2 (количество элементов на самом длинном пути прохождения сигнала).

Аналитически можно найти оптимальную схему (рис. 3):

Размещено на http://www.allbest.ru/

Рис. 3. Аналитически найденная оптимальная схема функции (abacbc)

Сложность такой схемы - 3, задержка - 2.

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

Для решения практических задач необходимо использовать системный синтез для оптимизации получаемых схем [3].

Выполним системный синтез для функций (abacbc) и (). Результат для первой функции получен выше. С помощью программного продукта для второй функции получен результат (рис. 4).

Рис. 4. Синтезированная схема функции ()

Сложность такой схемы - 1, задержка - 1.

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

Можно заметить, что в реализации данных двух функций используется одинаковый ФПТ-элемент, следовательно, можно выполнить системный синтез, объединив эти схемы (рис. 5).

Размещено на http://www.allbest.ru/

Рис. 5. Объединенная схема функций (abacbc) и ()

В полученной схеме верхний выход соответствует функции (abacbc), нижний - функции (). Сложность схемы - 3, задержка - 2. Следовательно, использование системного синтеза предпочтительнее "прямой" реализации схемы.

Заключение

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

Список литературы

1. Чебурахин И.Ф. Математическое моделирование и синтез вычислительных и управляющих логических устройств: дис. …д.т.н: 05.13.17. МАТИ-РГТУ, 2004. 323с.

2. Тюрин С.Ф. Проблема сохранения функциональной полноты булевых функций при "отказах" аргументов //Автоматика и телемеханика. 1999. № 9. С. 176-186.

3. Тюрин С.Ф., Аляев Ю.А. Дискретная математика. Практическая дискретная математика и математическая логика. М.: Финансы и статистика, 2010.

Размещено на Allbest.ru