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

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


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

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

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

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

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

Войти через центр авторизации
Похожие вопросы
CSort Барнаул
от 40 000 до 90 000 руб.
HttpLab Ростов-на-Дону
от 60 000 до 120 000 руб.
Avtoapp Москва
До 120 000 руб.
26 мая 2019, в 11:23
20000 руб./за проект
26 мая 2019, в 04:47
3000 руб./за проект
26 мая 2019, в 01:44
5000 руб./за проект