Расширение Рида – Мюллера

В булевой логике расширение Рида-Мюллера (или расширение Давио ) представляет собой разложение функции булевой .

Для булевой функции $f(x_{1},\ldots ,x_{n}):\mathbb {B} ^{n}\to \mathbb {B}$ мы звоним

${\begin{aligned}f_{x_{i}}(x)&=f(x_{1},\ldots ,x_{i-1},1,x_{i+1},\ldots ,x_{n})\\f_{{\overline {x}}_{i}}(x)&=f(x_{1},\ldots ,x_{i-1},0,x_{i+1},\ldots ,x_{n})\end{aligned}}$

положительные и кофакторы отрицательные $f$ относительно $x_{i}$, и

${\begin{aligned}{\frac {\partial f}{\partial x_{i}}}&=f_{x_{i}}(x)\oplus f_{{\overline {x}}_{i}}(x)\end{aligned}}$

логический вывод $f$ относительно $x_{i}$, где ${\oplus }$ обозначает оператор XOR .

Тогда мы имеем для расширения Рида-Мюллера или положительного расширения Давио :

$f=f_{{\overline {x}}_{i}}\oplus x_{i}{\frac {\partial f}{\partial x_{i}}}.$

Описание

Это уравнение записано таким образом, что оно напоминает разложение Тейлора $f$ о $x_{i}=0$. Аналогичное разложение соответствует разложению о $x_{i}=1$ ( отрицательное расширение Давио ):

$f=f_{x_{i}}\oplus {\overline {x}}_{i}{\frac {\partial f}{\partial x_{i}}}.$

Повторное применение расширения Рида – Мюллера приводит к полиному XOR в $x_{1},\ldots ,x_{n}$:

$f=a_{1}\oplus a_{2}x_{1}\oplus a_{3}x_{2}\oplus a_{4}x_{1}x_{2}\oplus \ldots \oplus a_{2^{n}}x_{1}\cdots x_{n}$

Это представление уникально и иногда его также называют расширением Рида – Мюллера.

Например, для $n=2$ результат будет

$f(x_{1},x_{2})=f_{{\overline {x}}_{1}{\overline {x}}_{2}}\oplus {\frac {\partial f_{{\overline {x}}_{2}}}{\partial x_{1}}}x_{1}\oplus {\frac {\partial f_{{\overline {x}}_{1}}}{\partial x_{2}}}x_{2}\oplus {\frac {\partial ^{2}f}{\partial x_{1}\partial x_{2}}}x_{1}x_{2}$

где

${\partial ^{2}f \over \partial x_{1}\partial x_{2}}=f_{{\bar {x}}_{1}{\bar {x}}_{2}}\oplus f_{{\bar {x}}_{1}x_{2}}\oplus f_{x_{1}{\bar {x}}_{2}}\oplus f_{x_{1}x_{2}}$.

Для $n=3$ результат будет

$f(x_{1},x_{2},x_{3})=f_{{\bar {x}}_{1}{\bar {x}}_{2}{\bar {x}}_{3}}\oplus {\partial f_{{\bar {x}}_{2}{\bar {x}}_{3}} \over \partial x_{1}}x_{1}\oplus {\partial f_{{\bar {x}}_{1}{\bar {x}}_{3}} \over \partial x_{2}}x_{2}\oplus {\partial f_{{\bar {x}}_{1}{\bar {x}}_{2}} \over \partial x_{3}}x_{3}\oplus {\partial ^{2}f_{{\bar {x}}_{3}} \over \partial x_{1}\partial x_{2}}x_{1}x_{2}\oplus {\partial ^{2}f_{{\bar {x}}_{2}} \over \partial x_{1}\partial x_{3}}x_{1}x_{3}\oplus {\partial ^{2}f_{{\bar {x}}_{1}} \over \partial x_{2}\partial x_{3}}x_{2}x_{3}\oplus {\partial ^{3}f \over \partial x_{1}\partial x_{2}\partial x_{3}}x_{1}x_{2}x_{3}$

где

${\partial ^{3}f \over \partial x_{1}\partial x_{2}\partial x_{3}}=f_{{\bar {x}}_{1}{\bar {x}}_{2}{\bar {x}}_{3}}\oplus f_{{\bar {x}}_{1}{\bar {x}}_{2}x_{3}}\oplus f_{{\bar {x}}_{1}x_{2}{\bar {x}}_{3}}\oplus f_{{\bar {x}}_{1}x_{2}x_{3}}\oplus f_{x_{1}{\bar {x}}_{2}{\bar {x}}_{3}}\oplus f_{x_{1}{\bar {x}}_{2}x_{3}}\oplus f_{x_{1}x_{2}{\bar {x}}_{3}}\oplus f_{x_{1}x_{2}x_{3}}$.

Геометрическая интерпретация

Этот $n=3$ случае можно дать кубическую геометрическую интерпретацию (или теоретико-графовую интерпретацию) следующим образом: при движении по ребру из ${\bar {x}}_{1}{\bar {x}}_{2}{\bar {x}}_{3}$ к $x_{1}{\bar {x}}_{2}{\bar {x}}_{3}$, XOR вверх по функциям двух конечных вершин ребра, чтобы получить коэффициент $x_{1}$. Чтобы перейти от ${\bar {x}}_{1}{\bar {x}}_{2}{\bar {x}}_{3}$ к $x_{1}x_{2}{\bar {x}}_{3}$ существуют два кратчайших пути: один — двуреберный, проходящий через $x_{1}{\bar {x}}_{2}{\bar {x}}_{3}$ а другой — двусторонний путь, проходящий через ${\bar {x}}_{1}x_{2}{\bar {x}}_{3}$. Эти два пути охватывают четыре вершины квадрата, а операция XOR функций этих четырех вершин дает коэффициент $x_{1}x_{2}$. Наконец, чтобы перейти от ${\bar {x}}_{1}{\bar {x}}_{2}{\bar {x}}_{3}$ к $x_{1}x_{2}x_{3}$ существует шесть кратчайших путей, которые являются путями с тремя ребрами, и эти шесть путей охватывают все вершины куба, поэтому коэффициент $x_{1}x_{2}x_{3}$ может быть получено путем XOR функций всех восьми вершин. (Другие, не упомянутые коэффициенты, можно получить путем симметрии.)

Пути

Все кратчайшие пути включают монотонные изменения значений переменных, тогда как все некратчайшие пути включают немонотонные изменения таких переменных; или, другими словами, все кратчайшие пути имеют длину, равную расстоянию Хэмминга между начальной и конечной вершинами. Это означает, что должно быть легко обобщить алгоритм получения коэффициентов из таблицы истинности путем выполнения операции XOR значений функции из соответствующих строк таблицы истинности, даже для гиперразмерных случаев ( $n=4$ и выше). Между начальной и конечной строками таблицы истинности значения некоторых переменных остаются фиксированными: найдите все строки таблицы истинности, в которых эти переменные также остаются фиксированными с этими заданными значениями, затем выполните операцию XOR для их функций, и результат должен быть коэффициент для монома, соответствующего целевой строке. (В такой моном включите любую переменную, значение которой равно 1 (в этой строке), и исключите любую переменную, значение которой равно 0 (в этой строке), вместо включения отрицания переменной, значение которой равно 0, как в стиле минтерм. )

Подобно диаграммам двоичных решений (BDD), где узлы представляют разложение Шеннона по соответствующей переменной, мы можем определить диаграмма принятия решений на основе расширения Рида – Мюллера. Эти диаграммы решений называются функциональными BDD (FBDDD).

Выводы

Разложение Рида – Мюллера можно получить из XOR-формы разложения Шеннона, используя тождество ${\overline {x}}=1\oplus x$:

${\begin{aligned}f&=x_{i}f_{x_{i}}\oplus {\overline {x}}_{i}f_{{\overline {x}}_{i}}\\&=x_{i}f_{x_{i}}\oplus (1\oplus x_{i})f_{{\overline {x}}_{i}}\\&=x_{i}f_{x_{i}}\oplus f_{{\overline {x}}_{i}}\oplus x_{i}f_{{\overline {x}}_{i}}\\&=f_{{\overline {x}}_{i}}\oplus x_{i}{\frac {\partial f}{\partial x_{i}}}.\end{aligned}}$

Вывод разложения для $n=2$:

${\begin{aligned}f&=f_{{\bar {x}}_{1}}\oplus x_{1}{\partial f \over \partial x_{1}}\\&={\Big (}f_{{\bar {x}}_{2}}\oplus x_{2}{\partial f \over \partial x_{2}}{\Big )}_{{\bar {x}}_{1}}\oplus x_{1}{\partial {\Big (}f_{{\bar {x}}_{2}}\oplus x_{2}{\partial f \over \partial x_{2}}{\Big )} \over \partial x_{1}}\\&=f_{{\bar {x}}_{1}{\bar {x}}_{2}}\oplus x_{2}{\partial f_{{\bar {x}}_{1}} \over \partial x_{2}}\oplus x_{1}{\Big (}{\partial f_{{\bar {x}}_{2}} \over \partial x_{1}}\oplus x_{2}{\partial ^{2}f \over \partial x_{1}\partial x_{2}}{\Big )}\\&=f_{{\bar {x}}_{1}{\bar {x}}_{2}}\oplus x_{2}{\partial f_{{\bar {x}}_{1}} \over \partial x_{2}}\oplus x_{1}{\partial f_{{\bar {x}}_{2}} \over \partial x_{1}}\oplus x_{1}x_{2}{\partial ^{2}f \over \partial x_{1}\partial x_{2}}.\end{aligned}}$

Вывод булевой производной второго порядка:

${\begin{aligned}{\partial ^{2}f \over \partial x_{1}\partial x_{2}}&={\partial \over \partial x_{1}}{\Big (}{\partial f \over \partial x_{2}}{\Big )}={\partial \over \partial x_{1}}(f_{{\bar {x}}_{2}}\oplus f_{x_{2}})\\&=(f_{{\bar {x}}_{2}}\oplus f_{x_{2}})_{{\bar {x}}_{1}}\oplus (f_{{\bar {x}}_{2}}\oplus f_{x_{2}})_{x_{1}}\\&=f_{{\bar {x}}_{1}{\bar {x}}_{2}}\oplus f_{{\bar {x}}_{1}x_{2}}\oplus f_{x_{1}{\bar {x}}_{2}}\oplus f_{x_{1}x_{2}}.\end{aligned}}$

См. также

• Алгебраическая нормальная форма (АНФ)
• Нормальная форма кольцевой суммы (RSNF)
• Полином Жегалкина
• Карта Карно
• Ирвинг Стой Рид
• Дэвид Юджин Мюллер
• Код Рида – Мюллера

Дальнейшее чтение

• Жегалкин [Zhegalkin], Иван Иванович [Ivan Ivanovich] (1927). "О Технике Вычислении Предложенной в Symbolytscheskoy Logykye" О технике вычислений предложений в символической логике «О технике вычисления высказываний в символической логике». Математический сборник (на русском и французском языках). 34 (1). Москва, Россия: 9–28. Ми   msb7433 . Архивировано из оригинала 12 октября 2017 г. Проверено 12 октября 2017 г.
• Рид, Ирвинг Стой (сентябрь 1954 г.). «Класс кодов, исправляющих множественные ошибки, и схема декодирования». IRE Транзакции по теории информации . ИТ-4 : 38–49.
• Мюллер, Дэвид Юджин (сентябрь 1954 г.). «Применение булевой алгебры к проектированию коммутационных схем и обнаружению ошибок». IRE-транзакции на электронных компьютерах . ЭК-3 : 6–12.
• Кебшулл, Удо; Розенстиль, Вольфганг (1993). «Эффективные вычисления на основе графов и манипулирование функциональными диаграммами решений». Материалы 4-й Европейской конференции по автоматизации проектирования : 278–282.
• Максфилд, Клайв «Макс» (29 ноября 2006 г.). «Логика Рида-Мюллера» . Логика 101 . ЭТаймс . Часть 3. Архивировано из оригинала 19 апреля 2017 г. Проверено 19 апреля 2017 г.
• Штайнбах, Бернд [на немецком языке] ; Постхофф, Кристиан (2009). "Предисловие". Логические функции и уравнения - примеры и упражнения (1-е изд.). Springer Science + Business Media BV с. хв. ISBN  978-1-4020-9594-8 . LCCN   2008941076 .
• Перковский, Марек А.; Грыгель, Станислав (20 ноября 1995 г.). «6. Исторический обзор исследований разложения». Обзор литературы по функциональному разложению . Версия IV. Группа функциональной декомпозиции, факультет электротехники, Портлендский университет, Портленд, Орегон, США. стр. 21–22. CiteSeerX   10.1.1.64.1129 . (188 страниц)