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

Здравствуте. Занимаюсь решением такой задачи. Есть большая нестандартняа логическяа многовходовая функция заданная таблицей истинности (пусть для определенности будет 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]);


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

И теперь внимание вопрос, есть ли какие-то общеизвестные алгоритмы, которые решают подобную задачу, как они называются на русском или английском? Всем спасибо за помощь.
  • Вопрос задан
  • 7333 просмотра
Пригласить эксперта
Ответы на вопрос 3
Vest
@Vest
Если не ошибаюсь, то вам нужны Карты Карно, для упрощения логических операций.
Ответ написан
kruzhevnik
@kruzhevnik
Вообще-то Espresso вроде как умеет минимизировать системы булевых функций — соответственно, общие подвыражения, которые вы выделили в отдельные переменные, должны там использоваться. Но, возможно, Espresso посчитало такие варианты не идеальными. Можно попробовать как-то поиграть с опциями минимизации (не могу подсказать, не знаток Espresso).

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Syntacore Санкт-Петербург
от 100 000 руб.
CSort Барнаул
от 40 000 до 90 000 руб.
20 февр. 2019, в 02:03
1000 руб./за проект
20 февр. 2019, в 00:43
400 руб./в час
19 февр. 2019, в 22:04
300000 руб./за проект