Siguiente: Formas algebraicas Arriba: Códigos de Reed-Muller Anterior: Códigos de Reed-Muller

Funciones booleanas

Definición 7.1 (Funciones booleanas)   Para cada $n\in\mathbb{N}$ sea $\mathbb{F}_2^{\mathbb{F}_2^{n}} = \left\lbrace f:\mathbb{F}_2^{n}\to\mathbb{F}_2\vert\, f \mbox{ es funci\'on}\right\rbrace$ la colección de funciones booleanas.

Naturalmente, $\mathbb{F}_2^{\mathbb{F}_2^{n}}$ posee una estructura de álgebra booleana con ${\bf0}$ como elemento mínimo y ${\bf 1}$ como elemento máximo. También, visto como un espacio vectorial sobre su campo primo $\mathbb{F}_2$, la colección $\mathbb{F}_2^{\mathbb{F}_2^{n}}$ posee una estructura de espacio vectorial de dimensión $2^n$. Una base del espacio está dada por las funciones $\left(\delta_{\mbox{\scriptsize\boldmath$\varepsilon$}_0}\right)_{\mbox{\scriptsize\boldmath$\varepsilon$}_0\in \mathbb{F}_2^n}$ donde $\delta_{\mbox{\scriptsize\boldmath$\varepsilon$}_0}:\mbox{\boldmath$\varepsilon... ...\scriptsize\boldmath$\varepsilon$}_0\mbox{\scriptsize\boldmath$\varepsilon$}_1}$ y esta última es la delta de Kroenecker.

Observación 7.1   Las siguientas son identificaciones naturales entre respectivos conjuntos:

• La correspondencia $\iota_n:i\mapsto (i)_2$, que a cada entero le asocia su representación en base $2$ de longitud $n$, identifica a $[\![0,2^n-1]\!]$ con $\mathbb{F}_2^n$.
• La correspondencia $I_n:f\mapsto \left[f(\iota_n(i))\right]_{i\in[\![0,2^n-1]\!]}$, que a cada función booleana le asocia la cadena de sus valores de acuerdo con el orden de $[\![0,2^n-1]\!]$, identifica a $\mathbb{F}_2^{\mathbb{F}_2^{n}}$ con $\mathbb{F}_2^{2^n}$. Mediante tal identificación se dice que toda función booleana es una palabra-$2^n$.

Las funciones proyecciones $\pi_j:\mbox{\boldmath$\varepsilon$}\mapsto \varepsilon_j$, $j\in[\![0,n-1]\!]$, son funciones booleanas, y al formar un conjunto de $n$ funciones linealmente independientes, ellas mismas generan un espacio vectorial $\mbox{Lin}(\mathbb{F}_2^{n})$ en $\mathbb{F}_2^{\mathbb{F}_2^{n}}$, llamado de las funciones lineales, isomorfo a $\mathbb{F}_2^{n}$. De hecho, para cada $f\in\mbox{Lin}(\mathbb{F}_2^{n})$ existe un único $\mbox{\boldmath$\delta$}\in\mathbb{F}_2^{n}$ tal que $f(\mbox{\boldmath$\varepsilon$}) = \langle\mbox{\boldmath$\delta$}\vert\mbox{\boldmath$\varepsilon$}\rangle = \sum_{j=0}^{n-1}\delta_j\varepsilon_j$, para toda $\mbox{\boldmath$\varepsilon$}\in\mathbb{F}_2^{n}$. Escribiremos $f=\lambda_{\mbox{\scriptsize\boldmath$\delta$}}$.

El complemento de una función booleana $f\in\mathbb{F}_2^{\mathbb{F}_2^{n}}$ es $\overline{f}=1+f:\mbox{\boldmath$\varepsilon$}\mapsto 1+f(\mbox{\boldmath$\varepsilon$})$.

Los complementos de las funciones lineales son las funciones afines: $\mbox{Af\'\i n}(\mathbb{F}_2^{n}) = \{\overline{f}\vert\, f\in\mbox{Lin}(\mathbb{F}_2^{n})\}.$

Recordamos que el producto en $\mathbb{F}_2$ es idempotente, $x^2=x$, y la suma es de orden 2: $x+x=0$.

Siguiente: Formas algebraicas Arriba: Códigos de Reed-Muller Anterior: Códigos de Reed-Muller