Минимизация логических функций?

Question

[Turbo]

Здравствуте. Занимаюсь решением такой задачи. Есть большая нестандартняа логическяа многовходовая функция заданная таблицей истинности (пусть для определенности будет 16 бит на входе 8 бит на выходе). Дальше мы минимизируем таблицу истинности одним из способов (в нашем случае алгоритм Espresso). И генерим для каждого бита выхода следующую конструкцию:

assign X[2] = ( A[1]&~A[0]& B[1]) | ( A[1]& B[1]&~B[0]) | (~A[2]&~A[1]&~A[0]& B[2]) | ( A[2]&~A[0]&~B[2]&~B[1]) | ( A[2]& A[0]& B[2]& B[0]) | (~A[2]&~A[1]& B[2]&~B[0]) | ( A[2]&~B[2]&~B[1]&~B[0]) | (~A[2]&~A[1]& A[0]& B[1]& B[0]) | ( A[1]& A[0]&~B[2]&~B[1]& B[0]);

assign X[1] = ( A[2]&~A[0]& B[2]) | ( A[2]& B[2]&~B[0]) | (~A[2]&~A[1]&~A[0]& B[1]) | ( A[1]&~A[0]&~B[2]&~B[1]) | ( A[1]& A[0]& B[2]& B[0]) | ( A[2]& A[0]& B[1]& B[0]) | (~A[2]&~A[1]& B[1]&~B[0]) | ( A[1]&~B[2]&~B[1]&~B[0]) | (~A[2]&~A[1]& A[0]&~B[2]&~B[1]& B[0]);

assign X[0] = (~A[0]& B[0]) | ( A[0]&~B[0]);


Дальше моделируем полученный элемент в одной из САПР на предмет скорости работы, площади и мощности. Вот тут и возникает проблема. Со скоростью все замечательно, но площадь получается очень большой. Я провел небольшие эксперименты по уменьшению размера логических функций за счет введения дополнительных переменных и вынесения больших общих частей за скобку. И это работает — площадь уменьшается в два и более раз при сохранении скорости. Однако мне не хочется изобретать велосипед.

И теперь внимание вопрос, есть ли какие-то общеизвестные алгоритмы, которые решают подобную задачу, как они называются на русском или английском? Всем спасибо за помощь.

Answer 1

[Vest]

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

Comments

[Vest]

Я тут нагуглил, что Wolfram Alpha тоже умеет упрощать выражения, но ваши формулы длинные для неё :( Если нагуглю что-нибудь полезное, дам знать. Самому интересно

[pavelsh]

Человек написал что использует алгоритм Espresso для минимизации. Карты Карно — они уж очень неудобные для функций с кол-вом аргументов больше 4-х
en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer

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

В то время как я был студентом, у нас была несколько другая задача, каким образом минимизированную функцию преобразовать так, чтобы ее можно было легко реализовать на базовом элементе заданной логике. Например на ттл логике базовым элементом был 2и-не, соответственно ручками приводили формулы к этой системе. Если я не ошибаюсь, то ребята сами писали системы чтобы делать это не руками.

[Turbo]

Да, примерно так и есть. Отлично подошел бы алгоритм натягивания логики на заданную библиотеку логических элементов. Но такое ощущение возникает, что тут сплошная эвристика. )

Answer 2

[kruzhevnik]

Вообще-то Espresso вроде как умеет минимизировать системы булевых функций — соответственно, общие подвыражения, которые вы выделили в отдельные переменные, должны там использоваться. Но, возможно, Espresso посчитало такие варианты не идеальными. Можно попробовать как-то поиграть с опциями минимизации (не могу подсказать, не знаток Espresso).

Тут выше сказали, что карты Карно для большого количества переменных неудобны, но мне так не кажется ;) Приведите полностью вашу систему, а попробую что-нибудь с ней сделать. И сложность вашего решения по Квайну посчитайте, чтобы мне было на что ориентироваться.

Насчет карт Карно, и почему мне кажется, что они довольно удобны — я как раз автор одной из софтинок для Карт Карно, и думаю написать о ней статью — загляните пожалуйста в Q&A. В принципе, КК сейчас в реальной разработке малоактуальны, но мне интересно, могут ли они помочь в случаях, подобных этому.

Comments

[kruzhevnik]

Сложность по Квайну — она же цена схемы по Квайну — на мой взгляд, довольно подходящий критерий для оценки качества минимизации для ваших условий.

[Turbo]

Приведенные выражения уже минимизированы. Другое дело, что результат минимизации можно записать разными способами. Здесь оно записано как СДНФ. Одна и та же переменная повторяется много раз и сама длина выражения довольно большая.

[kruzhevnik]

Ну, минимальных форм много, и не все из них самые минимальные ;)
Если не затруднит, я все же хотел бы поработать с исходной системой, может что и получится хорошее

[Turbo]

Я делал таблицы истинности для сумматоров по модулю:
Исходные таблицы: vscripts.ru/res/files/Truth-table-sum-by-mod-450MB.7z
Сжатые Espresso: vscripts.ru/res/files/Truth-table-sum-by-mod-minimized.zip

Квайн и Карно для больших >128 модулей скорее всего не пройдут.

[Turbo]

Ну и Espresso почти всегда находит оптимальное решение, так что сжать серьезно лучше вряд ли удастся.

[kruzhevnik]

Согласен, Espresso отличный инструмент, но у карт Карно есть некоторое преимущество — наглядность, которое может помочь найти общие минтермы, входящие в состав нескольких функций, вот и хочу попробовать.

Файлы в формате — входы,, выходы, как я понимаю?
Это Espresso в таком формате принимает?

[Turbo]

Это если не ошибаюсь формат входных данных для Logic Friday: www.sontrak.com/
У Espresso чуток отличается: vscripts.ru/w/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Espresso

[kruzhevnik]

С предыдущим коментарием промазал ;)

Выражения действительно великоваты для карт Карно, и для моей программы тоже — с файлом sum_mod_255.csv работать тяжеловато — 16 входных переменных тормозят на моем i5 ;( Приемлемо работать можно начиная с sum_mod_64.csv и ниже (10 входов), но вручную решение искать также тяжеловато, так что нахрапом получить результат не удалось.

Но есть и хорошие новости ;)
Во-первых, нашел пару багов у себя, во-вторых — добавил импорт CSV от Logic Friday.

И есть еще одна идея, которую возможно, стоит реализовать — разделить данную систему на более мелкие системы — 4-8 входов с введением промежуточных функций.

Тут есть над чем подумать. Сейчас у меня в программе можно работать с произвольным количеством систем функций, которые (системы функций) никак не связаны между собой — что-то типа проектов. Можно разбить систему функций, подобную вашей, на некоторое число систем с меньшим количеством функций, и сказать, что данный набор систем функций является одним проектом и ввести более общую сущность — типа workspace, или solution, и работать уже с ней. Идея интересная, но требует времени на обдумывание, так что в самое ближайшее время вряд ли будет готовое решение, тем более, что вы, как я понимаю, уже со своей проблемой более или менее разобрались, судя по дате вопроса, и вопрос перешел в разряд академических.
Спасибо за интересную задачу ;)

[Turbo]

У меня задача все же больше связанная с микроэлектроникой )

Я написал програмку тестовую эвристическую, которая по заданным таблицам истинности выносит больше общие части за скобку и генерит Verilog: vscripts.ru/res/sources/2013/verilog-generator-from-tables-sum-by-mod-ver2.c

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

Далее в составе Logic Friday удалось обнаружить старенький (видимо фришный) синтезатор MIS: vscripts.ru/w/MIS:_A_multiple-level_logic_optimization_system, который натягивает логику на заданную систему функций. Logic Friday использует его для отрисовки логикина уровне вентилей. Но после его работы сильно выросла задержка у схем, а в этом случае сокращение площади уже не имеет значения.

В итоге чуток помучавшись отошел от этой задачки. )

[kruzhevnik]

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

Answer 3

[kruzhevnik]

Понятно, то-то я и смотрю, на Espresso не очень похоже. Вообщем, посмотрю, что можно сделать