В Логическая логика, а Разложение Рида – Мюллера (или же Расширение Давио) это разложение из Логическая функция.
Для булевой функции мы называем
положительное и отрицательное кофакторы из относительно , и
логический вывод относительно , куда обозначает XOR оператор.
Тогда у нас есть для Рида – Мюллера или положительное расширение Давио:
Описание
Это уравнение записано так, что оно напоминает Расширение Тейлора из о . Аналогичное разложение соответствует разложению около (отрицательное расширение Давио):
Повторное применение разложения Рида – Маллера приводит к полиному исключающего ИЛИ от :
Это представление уникально и иногда также называется разложением Рида – Маллера.[1]
Например. за результат будет
куда
- .
За результат будет
куда
- .
Геометрическая интерпретация
Этот случаю можно дать кубико-геометрическую интерпретацию (или теоретико-графическую интерпретацию) следующим образом: при движении по ребру из к , XOR функций двух конечных вершин ребра, чтобы получить коэффициент при . Чтобы перейти от к есть два кратчайших пути: один - путь с двумя ребрами, проходящий через а другой - двухреберный путь, проходящий через . Эти два пути охватывают четыре вершины квадрата, и операция XOR по функциям этих четырех вершин дает коэффициент при . Наконец, чтобы перейти от к есть шесть кратчайших путей, которые являются путями с тремя ребрами, и эти шесть путей охватывают все вершины куба, поэтому коэффициент может быть получен операцией XOR для функций всех восьми вершин. (Остальные, не упомянутые коэффициенты могут быть получены симметрией.)
Пути
Все кратчайшие пути включают монотонные изменения значений переменных, тогда как все некратчайшие пути включают немонотонные изменения таких переменных; или, другими словами, все кратчайшие пути имеют длину, равную расстоянию Хэмминга между начальной и конечной вершинами. Это означает, что должно быть легко обобщить алгоритм получения коэффициентов из таблицы истинности путем выполнения операции исключающего ИЛИ значений функции из соответствующих строк таблицы истинности даже для гиперпространственных случаев ( и выше). Между начальными и конечными строками таблицы истинности значения некоторых переменных остаются фиксированными: найдите все строки таблицы истинности, чтобы эти переменные также оставались фиксированными на этих заданных значениях, затем выполните XOR для их функций, и результат должен быть равен коэффициент для одночлена, соответствующего целевой строке. (В таком мономе включите любую переменную, значение которой равно 1 (в этой строке), и исключите любую переменную, значение которой равно 0 (в этой строке), вместо включения отрицания переменной, значение которой равно 0, как в стиле minterm. )
Похожий на диаграммы бинарных решений (BDD), где узлы представляют Расширение Шеннона относительно соответствующей переменной, мы можем определить диаграмма решений на основе разложения Рида – Мюллера. Эти диаграммы решений называются функциональными BDD (FBDD).
Производные
Разложение Рида – Маллера может быть получено из XOR-формы разложения Шеннона, используя тождество :
Вывод разложения для :
Вывод булевой производной второго порядка:
Смотрите также
Рекомендации
- ^ Kebschull, U .; Schubert, E .; Розенштиль, В. (1992). «Многоуровневый логический синтез на основе схем функциональных решений». Труды 3-й Европейской конференции по автоматизации проектирования.
дальнейшее чтение