Внимание!
Предложения и заявки заказчиков

Размещение рекламных материалов

коммерческая реализация изобретений - ООО 'Адвансед Девелопмент Проджект' смотреть>>>

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

Требуются разработки по использованию низкопотенциальной энергии смотреть >>>

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

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

Minimization of Boolean Functions applying Equivalence of Sets

livejournal - http://obdamaskin.livejournal.com/4630.html


В "Представление информации булевой формулой" ( http://moiidei.com/nauka-estestvennyie/predstavlenie-informatsii-bulevoy-formuloy-2.html ) уже упоминалось, что одной из проблем представления информации булевой формулой является проблема формирования формулы по крайней мере с минимальным числом букв в ней.

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



"Существуют несколько способов минимизации булевых функций.Прежде всего,это аналитический символьный и аналитический кодовый методы,метод Квайна - Мак-Класки,

метод Блека - Порецкого, метод обобщенных кодов[11] и графическая минимизация с помощью карт Карно[12].

Пример для демонстрации аналитических методов:

z = x_y+xy_+xy = (x_y+xy)+(xy_+xy) = y(x_+x) + x(y_+y) = x+y.

z = 01+10+11 = (01+11)+(10+11) = -1+1- = x+y.

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

(http://ruslogic.narod.ru/lectures/3.htm )





Я бы добавил к этому высказыванию несколько субъективных замечений.

1. Большинство методов фактически минимизируют функцию только на уровне ДНФ (дизъюнктивной нормальной формы), т.е. в отсутствии скобок, которые то и дают реальное уменьшение числа букв в формуле.

2. Сокращение числа букв осуществляется по правилам булевой алгебры (метод Блейка) и зависит от от вашего опыта.

(http://www.sgu.ru/ie/mehmat/odfka/r3/R3-1.htm)

3. Практически нет гарантий, что полученная формула, если она достаточно сложна, является минимальной, что её нельзя сократить ещё.

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

Идеи, которые я хочу здесь представить, зародились именно в те времена.

Суть метода

Коротко, суть предлагаемого метода заключается в следующем.

На основании таблицы истинности, которая, как правило, является основой проектирования логической схемы, для искомой функции составляется множество из нулей и единиц. Множество разбивается на определённое число пар взаимнонепересекающихся подмножеств. Число пар равно числу входных переменных, и каждой паре сответствует пара букв, одна из которых обозначает переменную, а вторая её отрицание. Задача сводится к тому, чтобы на этом множестве сформировать множество, которое включает только единицы. Формула этого множества как раз и будет искомой функцией. Формирование множества осуществляется посредством пошаговой процедуры, на каждом шаге которой в формулу множества добавляется одна буква таким образом, чтобы полученное множество имело наибольшее совпадение с искомым множеством, т.е. имело бы как можно больше единиц и как можно меньше нулей. Величина совпадения определяется как sov(i) = s1(i)/s1 - s0(i)/s0
, где s1 и s0 - число единиц и нулей в исходном
множестве, а s1(i) и s0(i) - соответственно число единиц и нулей в
множестве, полученном на i - том шаге. Так как на каждом шаге в
формулу добавляется только одна буква, то на каждом i - том шаге мы
будем получать формулу из минимального числа i букв, определяющей
множество с максимальным совпадением. Процедура будет закончена, когда
будет получено множество с совпадением sov(i) =1. Формула будет иметь i
букв.



Результаты

Предлагаемый метод был применён при определения системы функций для
реализаций логической сети "Мышь в лабиринте" , синтез которых приведен
в книге "Н.Е. Кобринский и Б.А. Трахтенброт Введение в теорию
конечных автоматов. 1962 г." Всего надо найти 5 функций z1, z2,
f1(t+1), f2(t+1), f3(t+1) от 5 переменных x1, x2, f1(t), f2(t), f3(t)
, каждая из которых задаётся таблицей истинности. Таблица истинности
для всех пяти функций приведена на Рис. 1. Таблица взята из упомянутой
книги с некоторыми корректировками для удобства записи.



Таблица истинности для системы функций "Мышь в лабиринте"
   
№стр. код  входа  входн. состояния  код вых.  выходное состояние
            ---------------  -------------------------  ------------   ----------------------------
№ кол    1    2         3         4        5        6    7        8             9         10

             x1  x2        f1(t)   f2(t)     f3(t)     z1  z2      f1(t+1)   f2(t+1)   f3(t+1)
  0         0     0        0        0          0        0    0        0            1            0
  1         0     0        0        0          1        1    0        0            0            0
  2         0     0        0        1          0        1    0        0            0            0
  3         0     0        0        1          1        1    0        0            0            0
  4         0     0        1        0          0        1    0        0            0            0
  5         0     0        1        0          1        1    0        0            0            0     
  6         0     0        1        1          0        1    0        0            0            0
  7         0     0        1        1          1      ( 1)  (0)      (0)          (0)          (0)
  8         0     1        0        0          0        0    1        1            1            0
  9         0     1        0        0          1        0    0        1            1            0
 10        0     1        0        1          0        0    0        1            1            0
 11        0     1        0        1          1        0    0        1            0            1
 12        0     1        1        0          0        1    0        0            1            1
 13        0     1        1        0          1       (1)  (0)      (0)          (1)          (1)
 14        0     1        1        1          0        1    0        0             1            1
 15        0     1        1        1          1       (1)   (0)     (0)          (1)           (1)
 16        1     0        0        0          0        0     0        0            0             1
 17        1     0        0        0          1        0     0        1            1             0
 18        1     0        0        1          0        0     1        1            1             0
 19        1     0        0        1          1        0     0        1            0             0
 20        1     0        1        0          0        1     1        1            1             1
 21        1     0        1        0          1        0     1        1            1             0
 22        1     0        1        1          0        (1)  (1)     (1)          (1)          (1)           
 23        1     0        1        1          1         1     1       1             1             1   
 24        1     1        0        0          0         1     1       1             1             1
 25        1     1        0        0          1         (1)   (1)   ( 1)          (1)           (1)
 26        1     1        0        1          0         (1)   (1)   ( 1)          (1)           (1)          
 27        1     1        0        1          1         (1)   (1)   ( 1)          (1)           (1)
 28        1     1        1        0          0         (1)   (1)   ( 1)          (1)           (1)
 29        1     1        1        0          1         (1)   (1)   ( 1)          (1)           (1)
 30        1     1        1        1          0         (1)   (1)   ( 1)          (1)           (1)
 31        1     1        1        1          1          1     1       1             1             1
     
                                        
                                             Рис. 1




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



Система уравнений 1



z1 = -x1{-x2[f2(t) + f3(t)] + f1(t)} + x1{f1(t)[f2(t) +-f3(t)] + x2} (1) 10



z2 = x2[-f1(t)-f2(t)-f3(t) + x1] + x1[f2(t)-f3(t) +f1(t)] (2) 9



f1(t+1) = x2[x1 + -f1(t)] + x1[f1(t) + f2(t) +3(t)] (3) 7



f2(t+1) = -x1{x2[f1(t) + -f2(t) + -f3(t)] + -f1(t)-f2(t)-f3(t)} + x1[x2 + f1(t)+ -f2(t)f3(t) + f2(t)-f3(t)] (4) 15



f3(t+1) = -x1{x2[f2(t)f3(t) + f1(t)]} + x1{-f2(t)-f3(t) +f1(t)[f2(t)+f3(t)] +x2} (5) 12



Цифры, приведенные в конце каждой строки с формулами (1) - (5) показывают число букв (входных переменных) в каждой формуле



С помощью предлагаемого метода была получена

Система уравнений 2



z1 = f1(t)[-f3(t)+f2(t)] + -x1-x2[f2(t)+f3(t)] +x2x1 (6) 9



z2 = x1{f1(t)+ -f3(t)[x2+f2(t)]} +x2-f2(t)-f1(t)-f3(t) (7) 9



f1(t+1) = x1[f1(t)+f3(t)+f2(t)] +x2-f1(t) (8) 6



f2(t+1) = [x2+x1]{f1(t) + [-f2(t)+ -f3(t)][x2+f3(t)+f2(t)]} +-f2(t)-f1(t)-x1-f3(t) (9) 12



f3(t+1) = x2[f1(t)+f2(t)f3(t)] +x1[-f3(t)-f2(t)+f1(t)f2(t)] (10) 9



В этой системе уравнений (6) - (10), как и в системе уравнений 1 (1) -
(5), цифры в конце строк показывают число букв в каждой формуле. В
четырёх формулах из пяти предлагаемый метод позволил сократить число
букв. Общее число букв сократилось с 53 до 45.

                  Добавление 14.10.2011
На основе изложенных выше идей были разработаны методика,
включающая программу, которая позволяет по данным таблицы истинности
найти булеву функцию с минимальным числом букв в ней. http://moiidei.com/nauka-estestvennyie/prakticheskaya-minimizatsiya-bulevyih-funktsiy.html
Эта методика была применена к Таблице истинности для задачи "Мышь в лабиринте".
Результаты показаны ниже.
Для простоты  записи булевых формул введём следующие обозначения.

 x1 = u;  -x1 = h;  x2 = v; -x2 = i; f1(t) = w;  -f1(t) = j;  f2(t) = y; -f2(t) = l;

 f3(t) = z; -f3(t) = m.

 Ниже приведены полученные с помощью указанной методики формулы.

 z1 = ih(y+z) + w(m+y) +vu    (11)   9

 z2 = (ym+w)u + lvjm             (12)   8

 f1(t+1) = (z+w+y)u + vj          (13)   6

 f2(t+1) = (l+m)((y+z)u+v) +uw + ljhm    (14)   12

 f3(t+1) = (y+m)((l+w)u+v(w+z))             (15)   8

  Как видим, с помощью этой методики формулы для z2 (формула 12) и для
f3(t+1) (формула 15) удалось сократитить ещё на одну букву каждую.


     Этот адрес электронной почты защищен от спам-ботов. У вас должен быть включен JavaScript для просмотра.



   












Комментарии   

 
#1 Александр Литягин 09.10.2011 21:03
Советую Вам поскорее опубликовать это дело в какмнить журнале еждународном по какойнит лицензией открытой, чтобы вашу идею не прихватили какиенить товарищи из разработчиков ПЛИС и не оформили на нее патент.
Цитировать
 

Добавить комментарий


Защитный код
Обновить

Комментарии