Задать вопрос
@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]);


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

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

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

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

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

Войти через центр авторизации
Похожие вопросы
Вакансии с Хабр Карьеры
С developer (алгоритмист)
СберТех • Москва
от 350 000 ₽
Senior Java Developer, Database Engine
CedrusData
от 350 000 ₽
Senior Java Engineer (JavaSE, algorithms, optimization)
Brain Shells
от 6 000 $
Ещё вакансии
Заказы с Хабр Фриланса
Разработка проекта сайт-форум.
16 апр. 2024, в 16:59
50000 руб./за проект
Сделать верстку, в которой можно растягивать картинку
16 апр. 2024, в 16:52
10000 руб./за проект
Сделать лендинг, переработать существующий логистический сайт
16 апр. 2024, в 16:34
30000 руб./за проект
Ещё заказы