В булевой логике , А разложение Рида-Мюллер (или расширение Давио ) представляет собой разложение из булевой функции .
Для логической функции мы называем
положительные и отрицательные алгебраические из относительно , а также
логический вывод относительно , где обозначает оператор XOR .
Тогда у нас есть для Рида – Мюллера или положительного разложения Давио :
Описание
Это уравнение записывается таким образом , что она напоминает разложение в ряд Тейлора из о . Аналогичное разложение соответствует разложению около( отрицательное расширение Давио ):
Повторное применение разложения Рида – Маллера приводит к полиному исключающее ИЛИ от :
Это представление уникально и иногда также называется разложением Рида – Мюллера. [1]
Например, для результат будет
где
- .
Для результат будет
где
- .
Геометрическая интерпретация
Этот случаю можно дать кубико-геометрическую интерпретацию (или теоретико-графическую интерпретацию) следующим образом: при движении по ребру из к , Выполните XOR функций двух конечных вершин ребра, чтобы получить коэффициент при . Чтобы перейти от к есть два кратчайших пути: один - путь с двумя ребрами, проходящий через а другой - двухреберный путь, проходящий через . Эти два пути охватывают четыре вершины квадрата, и операция XOR по функциям этих четырех вершин дает коэффициент при. Наконец, чтобы перейти от к есть шесть кратчайших путей, которые являются путями с тремя ребрами, и эти шесть путей охватывают все вершины куба, поэтому коэффициент может быть получен путем XOR функций всех восьми вершин. (Другие, не упомянутые коэффициенты могут быть получены путем симметрии.)
Пути
Все кратчайшие пути включают монотонные изменения значений переменных, тогда как все некратчайшие пути включают немонотонные изменения таких переменных; или, другими словами, все кратчайшие пути имеют длину, равную расстоянию Хэмминга между начальной и конечной вершинами. Это означает, что должно быть легко обобщить алгоритм получения коэффициентов из таблицы истинности путем выполнения операции XOR по значениям функции из соответствующих строк таблицы истинности, даже для гиперпространственных случаев (и выше). Между начальными и конечными строками таблицы истинности значения некоторых переменных остаются фиксированными: найдите все строки таблицы истинности, чтобы эти переменные также оставались фиксированными на этих заданных значениях, затем выполните XOR для их функций, и результат должен быть равен коэффициент для одночлена, соответствующего целевой строке. (В таком мономе включите любую переменную, значение которой равно 1 (в этой строке), и исключите любую переменную, значение которой равно 0 (в этой строке), вместо включения отрицания переменной, значение которой равно 0, как в стиле minterm. )
Подобно диаграммам двоичных решений (BDD), где узлы представляют собой расширение Шеннона относительно соответствующей переменной, мы можем определить диаграмму решений на основе расширения Рида – Мюллера. Эти диаграммы решений называются функциональными BDD (FBDD).
Производные
Разложение Рида – Маллера может быть получено из XOR-формы разложения Шеннона, используя тождество :
Вывод разложения для :
Вывод булевой производной второго порядка:
Смотрите также
Рекомендации
- ^ Кебшулл, Удо; Шуберт, Эндрик; Розенштиль, Вольфганг (1992). «Многоуровневый логический синтез на основе схем функциональных решений». Материалы 3-й Европейской конференции по автоматизации проектирования .
дальнейшее чтение
- Жега́лкин [Жегалкин], Ива́н Ива́нович [Иван Иванович] (1927). "О Технике Вычисления Предложений в Символической Логике"О технике вычислений предложений в символической логике[О технике вычисления предложений в символической логике (Sur le Calcul des propositions dans la logique symbolique)]. Математический сборник . Москва, Россия. 34 (1): 9–28. Mi msb7433 . Архивировано 12 октября 2017 года . Проверено 12 октября 2017 .
- Рид, Ирвинг Стой (сентябрь 1954 г.). «Класс кодов с исправлением множественных ошибок и схема декодирования». Сделки IRE по теории информации . ИТ-4 : 38–49.
- Мюллер, Дэвид Юджин (сентябрь 1954 г.). «Применение булевой алгебры для проектирования коммутационных схем и обнаружения ошибок». Операции IRE на электронных компьютерах . ИС-3 : 6–12.
- Кебшулл, Удо; Розенштиль, Вольфганг (1993). «Эффективное вычисление на основе графов и манипулирование диаграммами функциональных решений». Материалы 4-й Европейской конференции по автоматизации проектирования : 278–282.
- Максфилд, Клайв «Макс» (29 ноября 2006 г.). «Логика Рида-Мюллера» . Логика 101 . EETimes . Часть 3. Архивировано 19.04.2017 . Проверено 19 апреля 2017 .
- Штейнбах, Бернд ; Постхофф, Кристиан (2009). "Предисловие". Логические функции и уравнения - Примеры и упражнения (1-е изд.). Springer Science + Business Media BV с. XV. ISBN 978-1-4020-9594-8. LCCN 2008941076 .
- Perkowski, Marek A .; Григель, Станислав (1995-11-20). «6. Исторический обзор исследований разложения». Обзор литературы по разложению функций . Версия IV. Группа функциональной декомпозиции, Департамент электротехники, Портлендский университет, Портленд, Орегон, США. С. 21–22. CiteSeerX 10.1.1.64.1129 . (188 стр.)