Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
Форум программистов > Алгоритмы > Где достать алгоритм минимизации булевой функции |
Автор: neutrino 11.6.2003, 17:05 |
Приветствую! Не могли бы вы подсказать какой-нибудь ресурс, где можно достать алгоритм (программу), реализующий минимизацию булевой функции методом карт Карно. Буду очень признателен за любой Ваш ответ. Ваш покойный слуга ![]() |
Автор: akul 12.6.2003, 14:01 |
Ить Карты Карно - это для человека метод, графически-визуальный, чтобы удобнее было. Машинный метод - это построить дерево и применять к нему упрощающие подстановки рекурсивно, пока применяются. |
Автор: neutrino 12.6.2003, 15:54 |
Я все понимаю. Сам алгоритм составить могу, но времени нет. Вот я и спрашиваю Где достать а не Как сделать. |
Автор: stab 14.6.2003, 20:36 |
слушай, я тут нашел курсовик свой давнишний, чего-там про метод КМК ... не помню чего это, но кажется что-то близкое по теме, если надо могу выслать |
Автор: stab 14.6.2003, 20:37 |
ага, вот еще... там про импликанты и про кубы разные упоминается |
Автор: neutrino 18.6.2003, 12:29 |
Ой, давай, давай... Кубы? Это если количество булевых переменных больше 4-х.... |
Автор: <Spawn> 19.6.2003, 20:59 |
http://www.etel.dn.ua/~shurik/carno Если сайт не будет активным, то могу выслать прогу на мыло ![]() |
Автор: stab 20.6.2003, 10:01 |
neutrino выслал |
Автор: dm9 21.6.2003, 14:22 |
Как обычно, открываем Апорт. Делаем запрос "минимизация булевой функции методом карт Карно". http://kai4x03.narod.ru/files/files.html Правда, ссылка, которая на страничке, у меня не работает. Но можно связаться с автором... |
Автор: Zeriod 12.7.2007, 14:15 |
Помню когда-то давным давно (3 года назад) писал диплом. Одним из его пунктов было "создание алгоритма минимизации булевых функций". Метод был изобретён свой, адаптированный под вычислительные машины. Критерий минимизации - минимум операций. Базис: дизъюнкция, конъюнкция, отрицание и сложение по модулю два. Число булевых переменных и сложность функций - любая. Язык программирования quick basic. Есть исходники. Но хотелось бы переписать прогу на что-нибудь современное (C#, C++, php или delphi). У самого времени нет этим заниматься. Если кому интересно, могу выслать код (ICQ: 459-783-892). |
Автор: Scorp_Freeman 16.1.2008, 20:21 |
Привет! Помогите плиз)) Я тоже с этим столкнулся) только я не сс картами карно , а с Квайном)) Помжет кто нить чемто помочь? Интересует алгоритм (поиск покрытий) |
Автор: AndreyK 29.1.2008, 17:09 |
Надо исключить лишние операторы (дизьюнкцию и отрицание или сложение) и получишь одно из представлений: полином Жигалкина или совершенную дизъюнктивную нормальную форму (ДНф) - вот там базисы и ищи. |
Автор: Дамаскин 21.11.2008, 20:18 |
Наверно, не совсем то, что Вам нужно, но может пригодиться. Минимизация булевых функций по совпадению множеств В "Представление информации булевой формулой" ( 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 = 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) + f3(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-f1-x1-f3 (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. Подробнее: http://obdamaskin.livejournal.com/4035.html или http://moiidei.com/nauka-estestvennyie/minimizatsiya-bulevyih-funktsiy-po-sovpadeniyu-mnozhestv.html |
Автор: sNicker 22.11.2008, 01:21 |
<Spawn>, если не трудно и не стёр ешё програмку, может и мне пришлёш? ![]() |
Автор: BalmaR 22.11.2008, 01:22 |
оО помогли с прогой такая же беда была. |
Автор: sNicker 22.11.2008, 10:39 |
BalmaR, может ты поможешь? "плиз" ![]() |
Автор: x0123456789 28.7.2009, 14:13 |
Вот программа моего ![]() В программе реализован алгоритм минимизации булевых функций методом Харриса. В файле Harris.adb приведён исходный код на языке Ada. Программа выдаёт все лучшие варианты оптимизации. Максимальная разрядность комбинаций - 16. Максимальное число комбинаций - 2 ** 16 = 65536. О всех обнаруженных недостатках сообщать автору на е-mail: [email protected] Исходные данные --------------- Исходные данные для работы пометить в файл parm.txt. Там перечислить все комбинации для минимизации в десятичной системе счисления. В качестве разделителей использовать символ пробела или символ перевода строки. См. примеры в файлах parm0.txt, parm1.txt, parm2.txt. Например, пусть в файле parm.txt имеем строку: "1 3 4 6 9 11 12" В двоичной форме это комбинации: 0001, 0011, 0100, 0110, 1001, 1011, 1100. Число комбинаций - 7, разрядность комбинаций - 4. Программа автоматически определит число и разрядность комбинаций. Результат работы выдаётся на консоль в стандартный поток вывода. Если есть необходимость перенаправить вывод в файл, запустить программу так: harris.exe > filename.txt Интерпретация результатов ------------------------- qqq = 7 nnn = 4 mmm = 14 <----- qqq - число комбинаций, nnn - разрядность, mmm - размер стека для работы = qqq * 2 # fak ves cod img <----- демонстрация размещения исходных данных в стеке в стеке (#-позиция, fak-факультатив, ves-вес Хэминга, cod-код, img-двоичное представление) 0 0 1 1 0001 1 0 1 4 0100 2 0 2 3 0011 3 0 2 6 0110 4 0 2 9 1001 5 0 2 12 1100 6 0 3 11 1011 <----- Начало перебора 1100 1 01*0 2 *0*1 3[1100,01*0,*0*1] <----- 1-й результат оптимизации (*-отмечены факультативы) [в квадратных скобках выдаётся лучший на данный момент результат] 00*1 2 01*0 3 10*1 4 1001 1 1100 2 1011 3 00*1 4 01*0 5 0110 1 *100 2 *0*1 3(0110,*100,*0*1) <----- 2-й вариант оптимизации (в круглых скобках - результат не хуже чем в []-скобках) 00*1 2 *100 3 10*1 4 1001 2 1011 3 00*1 4 *100 5 0100 1 0110 2 1100 3 *0*1 4 00*1 4 10*1 5 1001 3 1100 4 1011 5 00*1 6 1100 1 01*0 2 *0*1 3(1100,01*0,*0*1) <----- 3-й вариант оптимизации *001 2 01*0 3 *011 4 0011 1 1100 2 1011 3 *001 4 01*0 5 0110 1 *100 2 *0*1 3(0110,*100,*0*1) <----- 4-й вариант оптимизации *001 2 *100 3 *011 4 0011 1 0110 2 1011 3 *001 4 *100 5 0100 1 0110 2 1100 3 *0*1 4 *001 4 *011 5 0011 2 0110 3 1100 4 1011 5 *001 6 0001 1 1001 2 1100 3 01*0 4 *011 5 0011 2 1100 3 01*0 4 10*1 5 1001 3 1100 4 1011 5 01*0 6 0110 2 1001 3 *100 4 *011 5 0011 2 0110 3 *100 4 10*1 5 1001 4 1011 5 *100 6 0100 2 0110 3 1001 4 1100 5 *011 6 0011 3 0110 4 1100 5 10*1 6 1001 5 1100 6 1011 7 Ok! <----- конец перебора |
Автор: x0123456789 28.7.2009, 14:33 |
На всякий случай, если ссылка не будет работать привожу полный теХст программы: with Interfaces; use Interfaces; with Ada.Text_IO; use Ada.Text_IO; ------------------- procedure Harris is ------------------- -- максимальная разрядность комбинации IMG_MAX : constant := 16; -- изображение комбинации type img_type is array (0 .. IMG_MAX-1) of character; -- комбинация type cmb_type is record ves : integer; -- вес Хеминга fak : integer; -- факультатив cod : integer; -- комбинация img : img_type; -- изображение end record; -- стек комбинаций type cmb_arr_type is array (natural range <>) of cmb_type; type cmb_arr_ref_type is access cmb_arr_type; cmb : cmb_arr_ref_type; -- стек результата type img_arr_type is array (natural range <>) of img_type; type img_arr_ref_type is access img_arr_type; img : img_arr_ref_type; qqq : integer; -- число комбинаций nnn : integer; -- разрядность сомбинации mmm : integer; -- р-р стека комбинаций cntBest : integer := 32767; -- лучшее число комбинаций -- отображение комбинации procedure put_img (img : img_type) is begin for i in reverse 0 .. nnn-1 loop put (img (i)); end loop; end put_img; -- дамп стека комбинаций procedure Dump (ttt : integer) is begin new_line; put ("#" & ascii.ht); put ("fak" & ascii.ht); put ("ves" & ascii.ht); put ("cod" & ascii.ht); put ("img" & ascii.ht); for i in 0 .. ttt-1 loop new_line; put (integer'image (i) & ascii.ht); put (integer'image (cmb (i).fak) & ascii.ht); put (integer'image (cmb (i).ves) & ascii.ht); put (integer'image (cmb (i).cod) & ascii.ht); put_img (cmb (i).img); end loop; new_line; end Dump; -- ввод исходных данных function Get_Data return boolean is e, emax : integer; f : Ada.Text_IO.file_type; package IIO is new Ada.Text_IO.Integer_IO (integer); begin -- 1-й проход, определение числа комбинаций и разрядности qqq := 0; emax := 0; Open (f, Ada.Text_IO.in_file, "parm.txt"); while not end_of_file (f) loop IIO.Get (f, e); if emax < e then emax := e; end if; qqq := qqq + 1; end loop; Close (f); -- р-р стека комбинаций mmm := 2 * qqq; -- разрядность nnn := 0; while 2 ** nnn < emax loop nnn := nnn + 1; end loop; new_line; put_line ("qqq =" & integer'image (qqq) & ascii.ht & "nnn =" & integer'image (nnn) & ascii.ht & "mmm =" & integer'image (mmm)); if IMG_MAX < nnn then put_line ("*** RANGE ERROR *** " & integer'image (IMG_MAX) & " < nnn"); return false; end if; -- размещение стека комбинаций cmb := new cmb_arr_type (0 .. mmm-1); -- размещение стека результата img := new img_arr_type (0 .. qqq-1); -- 2-й проход, загрузка стека Open (f, Ada.Text_IO.in_file, "parm.txt"); for i in 0 .. qqq-1 loop IIO.Get (f, e); cmb (i).cod := e; cmb (i).fak := 0; cmb (i).ves := 0; for j in 0 .. nnn-1 loop if (shift_right (unsigned_32 (e), j) and 1) = 0 then cmb (i).img (j) := '0'; else cmb (i).img (j) := '1'; cmb (i).ves := cmb (i).ves + 1; end if; end loop; end loop; Close (f); -- Dump (qqq); return true; end Get_Data; -- сортировка по весу Хеминга (внутри веса - по коду (хотя, по коду можно и не сортировать)) procedure Sortir is swap : cmb_type; nnn2p : integer; ives, jves, kves : integer; begin nnn2p := 2 ** nnn; for i in 0 .. qqq-2 loop ives := cmb (i).ves * nnn2p + cmb (i).cod; for j in i+1 .. qqq-1 loop jves := cmb (j).ves * nnn2p + cmb (j).cod; if jves < ives then kves := ives; ives := jves; jves := kves; swap := cmb (i); cmb (i) := cmb (j); cmb (j) := swap; end if; end loop; end loop; end Sortir; -- Дерево разбора procedure Tree (ott, doo, dno, cnt : integer) is -- от и до и дно и текущий счстчик стека результата p : integer; head : integer; -- голова стека комбинаций cntCmb : integer; -- голова стека результата begin head := dno; cntCmb := cnt; for i in ott .. doo-1 loop -- 1-й кандидат для склейки if 0 <= cmb (i).fak then -- если ещс не склеен for j in i+1 .. doo-1 loop -- 2-й кандидат для склейки if cmb (i).fak = cmb (j).fak then -- если одинаковые факультативы if abs (cmb (i).ves - cmb (j).ves) = 1 then -- если разница весов = 1 p := -1; for k in 0 .. nnn-1 loop -- поиск позиции для склейки if cmb (i).img (k) /= cmb (j).img (k) then if p = -1 then p := k; else p := -1; exit; end if; end if; end loop; if 0 <= p then -- склейка cmb (head).fak := cmb (i).fak + 2 ** p; -- конфигурация факультативов cmb (head).cod := cmb (i).cod; -- нафиг не нужно, но жалко выкинуть (был нужен при сортировке, но не особо) cmb (head).ves := cmb (i).ves; cmb (head).img := cmb (i).img; cmb (head).img (p) := '*'; -- позиция факультатива cmb (j).fak := -(cmb (j).fak + 1); -- выкидываю из рассмотрения Tree (i+1, doo, head+1, cntCmb); cmb (j).fak := -(cmb (j).fak + 1); -- возвращаю в строй end if; end if; end if; end loop; -- стек результата img (cntCmb) := cmb (i).img; cntCmb := cntCmb + 1; -- выдаю не склеевшиеся new_line; for j in 2 .. cntCmb loop put (ascii.ht); -- оЦтуп end loop; put_img (cmb (i).img); put (ascii.ht & integer'image (cntCmb)); end if; end loop; -- если была хоть одна склейка if doo < head then Tree (doo, head, head, cntCmb); -- начинаю новый уровень else -- не было склеек - конец цепочки if cntCmb < cntBest then cntBest := cntCmb; put ("["); -- лучше for i in 0 .. cntBest-1 loop if 0 < i then put (","); end if; put_img (img (i)); end loop; put_line ("]"); elsif cntCmb = cntBest then put ("("); -- не хуже for i in 0 .. cntBest-1 loop if 0 < i then put (","); end if; put_img (img (i)); end loop; put_line (")"); end if; end if; end Tree; ----- begin ----- if Get_Data then Sortir; Dump (qqq); Tree (0, qqq, qqq, 0); new_line; put ("Ok!"); end if; ---------- end Harris; ---------- |
Автор: x0123456789 30.7.2009, 18:41 |
![]() ![]() |
Автор: x0123456789 31.7.2009, 11:02 |
Исправил http://files.mail.ru/LZJ65O --- Краткое описание алгоритма --- Булевы комбинации сначала клеятся по 1 биту затем по 2, по 3 и т.д. И так до тех пор пока комбинации больше не клеятся. Затем стек комбинаций перетасовывается случайным образом и алгоритм склейки повторяется уже в ином порядке. Лучшие склейки помещаются в файл промежуточных результатов. Эти данные сортируются, исключаются повторения и выдаются в качестве конечного результата. --- qqq = 7 nnn = 4 mmm = 14 <----- qqq - число комбинаций, nnn - разрядность, mmm - размер стека для работы = qqq * 2 # fak ves cod img <----- размещение исходных данных в стеке (#-позиция, fak-факультатив, ves-вес Хэминга, cod-код, img-двоичное представление) 0 0 1 1 0001 1 0 2 3 0011 2 0 1 4 0100 3 0 2 6 0110 4 0 2 9 1001 5 0 3 11 1011 6 0 2 12 1100 + <----- Промежуточные результаты (*0*1,01*0,1100) (*0*1,01*0,1100) (*0*1,01*0,1100) (*0*1,01*0,1100) (*0*1,01*0,1100) (*0*1,01*0,1100) (*0*1,*100,0110) (*0*1,01*0,1100) (*0*1,*100,0110) (*0*1,*100,0110) (*0*1,*100,0110) ... (*0*1,01*0,1100) = <----- Итоговые результаты [*0*1,*100,0110] [*0*1,01*0,1100] Ok! <----- конец |
Автор: neutrino 2.8.2009, 10:58 |
А что за языk такой? |