Минимизиране на булеви функции
Здравейте. Занимавам се с решаването на такъв проблем. Има голяма нестандартна логическа многовходна функция, дефинирана от таблицата на истината (да кажем за определеност ще има 16 бита на входа, 8 бита на изхода). След това минимизираме таблицата на истината по един от начините (в нашия случай алгоритъмът на еспресо). И ще генерираме следната конструкция за всеки изходен бит:
След това симулираме получения елемент в една от CAD системите по отношение на скорост, площ и мощност. Тук възниква проблемът. Всичко е наред със скоростта, но площта е много голяма. Направих няколко малки експеримента за намаляване на размера на логическите функции чрез въвеждане на допълнителни променливи и поставяне на големи общи части извън скобите. И работи - площта се намалява с фактор два или повече, като същевременно се поддържа скорост. Не ми се иска обаче да преоткривам колелото.
И сега въпросът е, има ли известни алгоритми, които решават подобен проблем, както се наричат на руски или английски? Благодаря на всички за вашата помощ.
Човекът е написал, че използва алгоритъма еспресо за минимизиране. Карти на Karnaugh - те са много неудобни за функции с повече от 4 аргумента
en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer
В този случай човек пише за система, която ще вземе общата част от логическите изрази, за да намали броя на използваните порти.
Веднага ще кажа - не познавам такава система, но според мен една проста система е достатъчно лесна за писане.
Докато бях студент, имахме малко по-различен проблем, как да трансформираме минимизираната функция, така че тя да може лесно да бъде приложена върху основния елемент на дадената логика. Например в логиката на TTL основният елемент е бил 2, а не съответно писалките са били използвани за привеждане на формулите в тази система. Ако не се лъжа, тогава самите момчета са написали системите да го правят не на ръка.
Всъщност Espresso изглежда е в състояние да минимизира системите на булеви функции - съответно, общите подекспресии, които сте разпределили за отделни променливи, трябва да се използват там. Но еспресото може да е смятало подобни опции за не идеални. Можете да опитате по някакъв начин да играете с опциите за минимизиране (не мога да кажа, не съм експерт по еспресо).