En lógica booleana , una expansión de Reed-Muller (o expansión de Davio ) es una descomposición de una función booleana .
Para una función booleana nosotros llamamos
los cofactores positivos y negativos de con respecto a , y
la derivación booleana de con respecto a , dónde denota el operador XOR .
Luego tenemos para la expansión Reed-Muller o Davio positiva :
Descripción
Esta ecuación está escrita de una manera que se asemeja a una expansión de Taylor de acerca de . Hay una descomposición similar correspondiente a una expansión sobre( expansión negativa de Davio ):
La aplicación repetida de la expansión Reed-Muller da como resultado un polinomio XOR en :
Esta representación es única y, a veces, también se denomina expansión de Reed-Muller. [1]
Por ejemplo, para el resultado sería
dónde
- .
Para el resultado sería
dónde
- .
Interpretación geométrica
Esto caso se puede dar una interpretación geométrica cúbica (o una interpretación teórica de grafos) de la siguiente manera: cuando se mueve a lo largo del borde de a , XOR arriba las funciones de los dos vértices finales de la arista para obtener el coeficiente de . Para moverse de a hay dos caminos más cortos: uno es un camino de dos bordes que pasa por y el otro un camino de dos bordes que pasa por . Estos dos caminos abarcan cuatro vértices de un cuadrado, y XOR las funciones de estos cuatro vértices produce el coeficiente de. Finalmente, para pasar de a Hay seis caminos más cortos que son caminos de tres bordes, y estos seis caminos abarcan todos los vértices del cubo, por lo tanto, el coeficiente de se puede obtener XORing las funciones de los ocho vértices. (Los otros coeficientes no mencionados se pueden obtener por simetría).
Rutas
Todas las rutas más cortas implican cambios monótonos en los valores de las variables, mientras que las rutas no más cortas implican cambios no monótonos de dichas variables; o, para decirlo de otra manera, todos los caminos más cortos tienen longitudes iguales a la distancia de Hamming entre los vértices de inicio y de destino. Esto significa que debería ser fácil generalizar un algoritmo para obtener coeficientes de una tabla de verdad mediante XORing de los valores de la función de las filas apropiadas de una tabla de verdad, incluso para casos hiperdimensionales (y por encima). Entre las filas de inicio y destino de una tabla de verdad, algunas variables tienen sus valores fijos: busque todas las filas de la tabla de verdad de modo que esas variables permanezcan igualmente fijas en esos valores dados, luego XOR sus funciones y el resultado debería ser el coeficiente del monomio correspondiente a la fila de destino. (En tal monomio, incluya cualquier variable cuyo valor sea 1 (en esa fila) y excluya cualquier variable cuyo valor sea 0 (en esa fila), en lugar de incluir la negación de la variable cuyo valor es 0, como en el estilo de minitérmino. )
Similar a los diagramas de decisión binarios (BDD), donde los nodos representan la expansión de Shannon con respecto a la variable correspondiente, podemos definir un diagrama de decisión basado en la expansión de Reed-Muller. Estos diagramas de decisión se denominan BDD funcionales (FBDD).
Derivaciones
La expansión Reed-Muller se puede derivar de la forma XOR de la descomposición de Shannon, usando la identidad :
Derivación de la expansión para :
Derivación de la derivada booleana de segundo orden:
Ver también
Referencias
- ^ Kebschull, Udo; Schubert, Endric; Rosenstiel, Wolfgang (1992). "Síntesis lógica multinivel basada en diagramas de decisión funcional". Actas de la 3ª Conferencia Europea sobre Automatización del Diseño .
Otras lecturas
- Жега́лкин [Zhegalkin], Ива́н Ива́нович [Ivan Ivanovich] (1927). "O Tekhnyke Vychyslenyi Predlozhenyi v Symbolytscheskoi Logykye"О технике вычислений предложений в символической логике[Sobre la técnica de cálculo de proposiciones en lógica simbólica (Sur le calcul des propositions dans la logique symbolique)]. Matematicheskii Sbornik (en ruso y francés). Moscú, Rusia. 34 (1): 9-28. Mi msb7433 . Archivado desde el original el 12 de octubre de 2017 . Consultado el 12 de octubre de 2017 .
- Reed, Irving Stoy (septiembre de 1954). "Una clase de códigos de corrección de errores múltiples y el esquema de decodificación". Transacciones IRE sobre teoría de la información . IT-4 : 38–49.
- Muller, David Eugene (septiembre de 1954). "Aplicación del álgebra booleana al diseño de circuitos de conmutación y detección de errores". Transacciones IRE en computadoras electrónicas . EC-3 : 6-12.
- Kebschull, Udo; Rosenstiel, Wolfgang (1993). "Cálculo basado en gráficos y manipulación eficiente de diagramas de decisión funcional". Actas de la 4ª Conferencia Europea sobre Automatización del Diseño : 278–282.
- Maxfield, Clive "Max" (29 de noviembre de 2006). "Lógica Reed-Muller" . Lógica 101 . EETimes . Part 3. Archivado desde el original el 19 de abril de 2017 . Consultado el 19 de abril de 2017 .
- Steinbach, Bernd ; Posthoff, Christian (2009). "Prefacio". Funciones y ecuaciones lógicas - Ejemplos y ejercicios (1ª ed.). Springer Science + Business Media BV p. xv. ISBN 978-1-4020-9594-8. LCCN 2008941076 .
- Perkowski, Marek A .; Grygiel, Stanislaw (20 de noviembre de 1995). "6. Reseña histórica de la investigación sobre la descomposición". Un estudio de la literatura sobre la descomposición de funciones . Versión IV. Grupo de Descomposición Funcional, Departamento de Ingeniería Eléctrica, Universidad de Portland, Portland, Oregón, EE. UU. págs. 21-22. CiteSeerX 10.1.1.64.1129 . (188 páginas)