Siguiente: Códigos de Reed-Muller Arriba: Códigos de Reed-Muller Anterior: Funciones booleanas

Formas algebraicas

Sean $X_0,\ldots,X_{n-1}$ $n$ símbolos de variables. Estas son pues entes sintácticos. A cada variable $X_j$ se le asocia con la proyección $\pi_j$. Así la connotación de la variable $X_j$ es el valor de la $j$-ésima entrada en cada punto de $\mathbb{F}_2^n$. Los monomios son productos de variables (distintas a pares) y los polinomios son combinaciones lineales de monomios. El grado de un monomio es el número de variables, distintas a pares, que aparecen en él como factores, y el grado de un polinomio es el mayor de los grados de los monomios que aparecen en él como sumandos. Un polinomio $P(X_0,\ldots,X_{n-1})\in \mathbb{F}_2[X_0,\ldots,X_{n-1}]$ define la función $\mathbb{F}_2^n\to\mathbb{F}_2$, $\mbox{\boldmath$\varepsilon$}\mapsto P(\varepsilon_0,\ldots,\varepsilon_{n-1}).$

Definición 7.2   Para cada función booleana $f\in\mathbb{F}_2^{\mathbb{F}_2^{n}}$, su soporte es $\mbox{\rm Spt}(f) = f^{-1}(1) = \{\mbox{\boldmath$\varepsilon$}\in\mathbb{F}_2^{n}\vert\, f(\mbox{\boldmath$\varepsilon$})=1\}$ y su parte nula es $\mbox{\rm Nul}(f) = f^{-1}(0) = \{\mbox{\boldmath$\varepsilon$}\in\mathbb{F}_2^{n}\vert\, f(\mbox{\boldmath$\varepsilon$})=0\}.$ Así, $\left\lbrace\mbox{\rm Nul}(f),\mbox{\rm Spt}(f)\right\rbrace$ es una partición de $\mathbb{F}_2^{n}$.

Definición 7.3   Las siguientes nociones son convencionales:

• Para cada variable $X_j$, se hace $X_j^1=X_j$ y $X_j^0=1$.
• Para cada $\mbox{\boldmath$\varepsilon$}=(\varepsilon_0,\ldots,\varepsilon_{n-1})\in\mathbb{F}_2^n$ su monomio característico es $\mu(\mbox{\boldmath$\varepsilon$}) = \prod_{j=0}^{n-1} X_j^{\varepsilon_j}$.

Observación 7.2   Las siguientes aseveraciones se cumplen para cada $n\in\mathbb{N}$:

• Toda función booleana es equivalente a un polinomio. O si se quiere, toda palabra-$2^n$ es equivalente a un polinomio.
• Toda función es lineal o afín cuando y sólo cuando sea de grado a lo sumo $1$.
• El máximo grado posible es $n$.

En efecto, puede verse que si $f\in\mathbb{F}_2^{\mathbb{F}_2^{n}}$ entonces ella coincide con la función

$$A_{fn}:({\bf x},x_{n-1}) \mapsto A_{fn}({\bf x},x_{n-1}) = (1+x_{n-1})f({\bf x},0) + x_{n-1}f({\bf x},1).$$ (14)

Al representar a las funciones $\mathbb{F}_2^{n-1}\to\mathbb{F}_2$, ${\bf x} \mapsto f({\bf x},0)$, ${\bf x} \mapsto f({\bf x},1)$ también como polinomios, de (14) se encuentra el polinomio equivalente a $f$. $\Box$

Definición 7.4   El polinomio equivalente a $f\in\mathbb{F}_2^{\mathbb{F}_2^{n}}$ se dice ser la forma normal algebraica $\mbox{\rm FNA}(f)$ de $f$.

Una manera alternativa de calcular $\mbox{\rm FNA}(f)$ es la siguiente: Inicialmente hágase $g(X_0,\ldots,X_{n-1})=0$, y luego, para cada $\mbox{\boldmath$\varepsilon$}\in\mathbb{F}^n_2$, si acaso $g(\mbox{\boldmath$\varepsilon$})\not=f(\mbox{\boldmath$\varepsilon$})$ actualícese $g(X_0,\ldots,X_{n-1}):=g(X_0,\ldots,X_{n-1}) + \mu(\mbox{\boldmath$\varepsilon$})$ donde $\mu(\mbox{\boldmath$\varepsilon$})$ es el monomio característico de $\mbox{\boldmath$\varepsilon$}$ (véase la definición 7.3). $\Box$

Ahora bien, al ser $\mathbb{F}_2$ un campo, se tiene, por el Teorema Fundamental del Algebra, que cualquier polinomio en $\mathbb{F}_2[X]$ que sea no-nulo a lo más posee un número de raíces igual a su grado. De aquí se sigue:

Observación 7.3   La colección $\left\lbrace\mu(\mbox{\boldmath$\varepsilon$})\right\rbrace_{\mbox{\scriptsize\boldmath$\varepsilon$}\in\mathbb{F}_2^{n}}$ es linealmente independiente y por tanto es una base de $\mathbb{F}_2^{\mathbb{F}_2^{n}}$ sobre $\mathbb{F}_2$.

Observamos también que si $\mbox{\boldmath$\varepsilon$}_0\in\mathbb{F}_2^n$ tiene un peso de Hamming $k=w(\mbox{\boldmath$\varepsilon$}_0)$ y es precisamente en los índices $j_1,\ldots,j_k$ que $\varepsilon_{0j_\kappa}=1$ entonces para cualquier $\mbox{\boldmath$\varepsilon$}_1\in\mathbb{F}_2^n$ se tiene

$$\mu(\mbox{\boldmath $\varepsilon$}_0)(\mbox{\boldmath $\varep... ...row\ \ \forall \kappa\in[\![1,k]\!]: \varepsilon_{0j_\kappa}=1.$$

Es decir $\mbox{Spt}\left(\mu(\mbox{\boldmath$\varepsilon$}_0)\right) = \prod_{j=0}^{n-1} F_j$ donde $F_j=\{1\}$ si $\exists\kappa\in[\![1,k]\!]$: $j=j_\kappa$, o $F_j=\{0,1\}$ en otro caso.

Observación 7.4   El soporte de cada monomio $\mu(\mbox{\boldmath$\varepsilon$})$ es una variedad lineal de dimensión $n-w(\mbox{\boldmath$\varepsilon$})$ en $\mathbb{F}_2^{n}$. Posee, por tanto, $2^{n-w(\mbox{\scriptsize\boldmath$\varepsilon$})}$ elementos.

Siguiente: Códigos de Reed-Muller Arriba: Códigos de Reed-Muller Anterior: Funciones booleanas