Метод синтеза дискретных схем на базе программируемых логических матриц (ПЛМ ) с помощью эволюционных вычислений

 

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

Для представления ПЛМ в виде хромосомы введены следующие обозначения:

N– число входных наборов по таблице истинности, n – номер входного набора,

K– число входных переменных, k - номер входной переменной, M – число выходных переменных,

I – число вертикальных (промежуточных) шин, i – номер вертикальной шины,

J – число горизонтальных шин матрицы ИЛИ, j– номер горизонтальной шины.

C учетом введенных обозначений общий вид таблицы истинности представлен на рис. 2.11.

 

Таблица истинности
xK1 … xk1 … x21x11	… …
xK2 … xk2 … x22x12	… …
........	........
xKn … xkn … x2nx1n	… …
........	........
xKN … xkN … x2N x1N	… …

 

Рисунок 2.11 – Общий вид таблицы истинности

 

 

Структура и способ кодирования ПЛМ представлены на рис. 2.12.

x2n

Матрица элементов И

x1n

xkn

xKn

...

...

...

...

f1n

fjn

fJn

. .   .   .   .

. . .

. . .

Матрица элементов ИЛИ

. .   .   .   .

. .   .   .   .

{ 1...i...I }

{ 1...j...J }

 

 

Рисунок 2.12 – Структура ПЛМ и способ кодирования

 

Представление матрицы элементов И: описываются узлы промежуточных шин (сверху вниз и слева направо). Каждый узел матрицы И описывается 2 генами: первый ген определяет наличие соединения в анализируемом узле (1 – соединение есть, 0 – отсутствует), второй ген определяет тип входа (1 – прямой вход, 0 – инверсный).

Представление матрицы элементов ИЛИ: описываются узлы выходных шин матрицы ИЛИ – слева направо и сверху вниз. На каждый узел матрицы ИЛИ отводится 1 ген (1 – наличие соединения, 0 – отсутствие).Число горизонтальных шин матрицы равно числу выходных переменных таблицы истинности.

В хромосоме представляются все элементы И, затем ИЛИ. Хромосома имеет следующий вид:

Алгоритм разработанного метода синтеза дискретных схем на базе ПЛМ, представлен ниже.

Исходными данными для алгоритма являются:

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

· Параметры структуры ПЛМ:

· I – число промежуточных шин.Максимально возможное число промежуточных шин равно числу строк таблицы истинности (2^K).

· J – число выходных горизонтальных шин.

 

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

2. Оценка каждой хромосомы в популяции по формуле 2.28.

Синтезированные логические схемы оцениваются с помощью fitness- функций (F₁ и F₂), которые определяются следующим образом. На первом этапе находится схема, функционирующая в соответствии с заданной таблицей истинности (F₁).

F₁ определяет процент совпадений значений выходов полученной схемы в соответствии с заданной таблицей истинности и равен:

 

(2.11)

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

Если F₁=100%, то полученная схема функционирует в соответствии с таблицей истинности, и ее можно оптимизировать согласно выбранным критериям. Далее вычисляется F_2.

После получения схемы, функционирующей в соответствии с таблицей истинности (F₁=100%) происходит процесс оптимизации промежуточных шин (или максимизация числа неиспользуемых промежуточных шин ПЛМ).

, (2.12)

где I – заданное число промежуточных шин;

I_vacant – число неиспользованных промежуточных шин в синтезированной ПЛМ:

(2.13)

3. Определение значения вероятности мутации для каждого узла ПЛМ.

Значение вероятности мутации для каждого узла ПЛМ определяется вероятностью включения анализируемого узла. Если вероятность близка к 1, то узел включается. Определение значений вероятности мутации зависит от типа генов хромосомы. Хромосома описывается тремя типами генов: наличие соединения в узле матрицы И, использование прямого или инверсного входа, наличие соединения в матрице ИЛИ. Соответственно, предложено для каждого гена, в зависимости от его типа использовать динамическое значение вероятности мутации. Значение вероятностей мутации для каждого гена определяется на основании значений генов в хромосоме, значений входных переменных и значений функции в таблице истинности.

– вероятность нахождения узла во включенном состоянии матрицы ИЛИ.

(2.31)

 

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

(2.14)

– вероятность использования значения прямого или инверсного входа.

(2.15)

4. Селекция: на основе значений fitness- функции выбираются хромосомы-кандидаты для мутации.

5. Мутация: в выбранных ранее хромосомах п.4 с вероятностью по п.3 меняются значения генов.

6. Вычисляется fitness- функции для каждой хромосомы.

7. Если число генераций N_gen не превышает заданного значения, то оно увеличивается на единицу. Сформированная новая популяция рассматривается как текущая, после чего алгоритм продолжается с пункта 3. В противном случае – с пункта 8.

8. Результат: в последней популяции определяется хромосома с F₁=100% и максимальным значением F₂, что и является решением задачи.

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

 

2 Контрольные вопросы

1. Чем отличаются комбинационные схемы и цифровые автоматы?

2. Перечислите основные функционально полные наборы переключательных функций.

3. Назовите основные законы алгебры логики.

4. Какие основные методы минимизации переключательных функций используются на практике?

5. Что лежит в основе метода синтеза дискретных схем с помощью эволюционных вычислений?

 

3 ОБЕСПЕЧЕНИЕ ФУНКЦИОНИРОВАНИЯ СИСТЕМ БЕЗОПАСНОСТИ