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

Códigos de Reed-Muller

Sea $\mathbb{F}_2[X_0,\ldots,X_{n-1}]^{\leq r}$ la colección de polinomios con grado a lo sumo $r$, el cual es un subespacio lineal de $\mathbb{F}_2[X_0,\ldots,X_{n-1}]$. Por la observación 7.3, una base de ella es $\left\lbrace\mu(\mbox{\boldmath$\varepsilon$})\right\rbrace_{w(\mbox{\scriptsize\boldmath$\varepsilon$})\leq r}$, y es, por tanto, de dimensión

$$k_{nr}=\sum_{j=0}^r {n\choose j}.$$ (15)

Definición 7.5 (Reed-Muller)   Para $m,r\in\mathbb{N}$, sea

$${\cal R}(m,r) = \left\lbrace \left[f(\mbox{\boldmath $\vareps... ...t\, f\in \mathbb{F}_2[X_0,\ldots,X_{m-1}]^{\leq r}\right\rbrace$$

la colección de palabras de código resultantes como evaluaciones de los polinomios de grado a lo sumo $r$ en el espacio $\mathbb{F}_2^m$ de dimensión $m$.

Se tiene, naturalmente, que ${\cal R}(m,r)$ es un código- $\left[2^m,k_{mr}\right]$, donde $k_{mr}$ está dado por la ec. (15). Así pues sus palabras de código son de longitud $2^m$ y poseen $k_{mr}$ bits de información. Una generatriz de él es la matriz de orden $2^m\times k_{mr}$:

$$R_{mr} = \left[\mu(\mbox{\boldmath $\delta$}_j)(\mbox{\boldma... ..._i)\right]_{(i,j) \in [\![0,2^m-1]\!]\times[\![0,k_{mr}-1]\!]},$$

donde $\left\lbrace\mbox{\boldmath$\delta$}_j\right\rbrace_{j\in[\![0,k_{mr}-1]\!]}$ es una enumeración de los puntos en $\mathbb{F}_2^m$ con peso de Hamming a lo sumo $r$.

Por ejemplo, para $m=4$, el código ${\cal R}(m,m-1)$ posee como generatriz a

$$R_{43}= \left( \begin{array}{l\vert llll\vert llllll\vert lll... ... & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{array}\right)$$

La primera columna contiene los valores, en $\mathbb{F}_2^4$, del único polinomio de grado 0 a saber la constante 1, las siguientes 4 los de las variables $X_i$, $i\in[\![0,3]\!]$, las siguientes 6 los de las cuadráticas $X_iX_j$, $\{i,j\}\in[\![0,3]\!]^{(2)}$, y las últimas 4 los de las cúbicas $X_iX_jX_k$, $\{i,j,k\}\in[\![0,3]\!]^{(3)}$. La primera columna contiene $16=2^{4-0}$ 1's, cada una de las 4 siguientes $8=2^{4-1}$, cada una de las 6 siguientes $4=2^{4-2}$, y cada una de las 4 últimas $2=2^{4-3}$.

De la observación 7.4 se sigue:

Observación 7.5   El código ${\cal R}(m,r)$ tiene peso mínimo $2^{m-r}$.

Proposición 7.1   El dual del código ${\cal R}(m,r)$ es el código de Reed-Muller ${\cal R}(m,m-r-1)$, es decir

$${\cal R}(m,r)^{\perp} = {\cal R}(m,m-r-1).$$

En efecto, primero se tiene que la dimensión del dual ${\cal R}(m,r)^{\perp}$ es

$$2^m-k_{mr} = \sum_{j=0}^{m} {m\choose j}-\sum_{j=0}^r {m\choo... ...} {m\choose j} = \sum_{j=0}^{m-r-1} {m\choose j} = k_{m,m-r-1}.$$

Así, al ver que ${\cal R}(m,m-r-1) \subset {\cal R}(m,r)^{\perp}$ se tendrá que estos espacios coinciden. Para ello si se toma a dos palabras en los códigos $\mbox{\boldmath$\varepsilon$}\in{\cal R}(m,r)$ y $\mbox{\boldmath$\delta$}\in{\cal R}(m,m-r-1)$, entonces han de existir dos polinomios $f,g\in\mathbb{F}_2[X_0,\ldots,X_{m-1}]$ de grados respectivos $e\in[\![0,r]\!]$, $d\in[\![0,m-r-1]\!]$, que producen $\mbox{\boldmath$\varepsilon$}$ y $\mbox{\boldmath$\delta$}$ al evaluarlos en $\mathbb{F}_2^m$. El producto $h = fg$ es un polinomio de grado a lo sumo $e+d\leq r+(m-r-1)=m-1$. Por tanto $\left[h(\mbox{\boldmath$\eta$})\right]_{\mbox{\scriptsize\boldmath$\eta$}\in\mathbb{F}_2^m}$ es una palabra en el código ${\cal R}(m,m-1)$ el cual consiste sólo de palabras de peso de Hamming par. Con esto resulta que necesariamente $\langle\mbox{\boldmath$\varepsilon$}\vert\mbox{\boldmath$\delta$}\rangle=0$, es decir, esas dos palabras de código son ortogonales. $\Box$

Definición 7.6   Para cualquier conjunto $A\subset\mathbb{F}_2^m$ su función característica es $\xi_A:\mbox{\boldmath$\varepsilon$} \mapsto \xi_A(\mbox{\boldmath$\varepsilon$})$ donde

$$\xi_A(\mbox{\boldmath $\varepsilon$}) = \left\lbrace \begin{a... ...\mbox{\boldmath $\varepsilon$}\not\in A %\\ \end{array}\right.$$

Así, $\xi_A\in\mathbb{F}_2^{\mathbb{F}_2^m}$.

Observación 7.6   Sea $\mbox{\boldmath$\delta$}\in\mathbb{F}_2^n$ un punto en el hipercubo y sea $J_0=\mbox{\boldmath$\delta$}^{-1}\subset[\![0,n-1]\!]$ el conjunto de índices con entradas 1 en $\mbox{\boldmath$\delta$}$. Entonces

$$\forall\mbox{\boldmath$\varepsilon$}\in\mathbb{F}_2^n:\ \ \x... ...J_0\subset J\subset[\![0,n-1]\!]}\prod_{j\in J}\varepsilon_j.$$ (16)

Así pues, la función característica de la mónada $\{\mbox{\boldmath$\delta$}\}$ está dada por el polinomio $\sum\left\{\mu(\mbox{\boldmath$\eta$})\vert\,\mbox{\boldmath$\delta$}\preceq\mbox{\boldmath$\eta$}\right\}$, donde $\preceq$ es el orden del hipercubo.

Se tiene entonces que para cualquier función booleana $f\in\mathbb{F}_2^{\mathbb{F}_2^n}$:

$$\begin{eqnarray*} f &=& \sum\left\{f(\mbox{\boldmath$\delta$})\xi_{\{\mbox{\bold... ...th$\eta$})\vert\,\mbox{\boldmath$\eta$}\in\mathbb{F}_2^n\right\} \end{eqnarray*}$$

donde $g_f(\mbox{\boldmath$\eta$})=\sum\left\{f(\mbox{\boldmath$\delta$})\vert\,\mbox{\boldmath$\delta$}\preceq\mbox{\boldmath$\eta$}\right\}$.

De manera más precisa:

Observación 7.7   Si $A=\mbox{\boldmath$\varepsilon$}+V$ es un conjunto afín, es decir $V$ es un espacio lineal en $\mathbb{F}_2^m$, de dimensión $r$, entonces existe un polinomio $f_A\in\mathbb{F}_2[X_0,\ldots,X_{m-1}]$ de grado $m-r$ tal que $f_A=\xi_A$.

En efecto, $A$ puede ser visto como el conjunto de soluciones de un sistema lineal $A{\bf x} = {\bf b}$ de $m$ incógnitas y $m-r$ ecuaciones, que puede reescribirse como uno de la forma $A{\bf x} + {\bf b} + {\bf 1} = {\bf 1}$. Entonces

$$\xi_A({\bf x}) = \prod_{i=0}^{m-r-1} \sum_{j=0}^{m-1} \left(a_{ij} x_j+b_i+1\right).$$

Esta última expresión determina al polinomio $f_A$. $\Box$

De aquí se siguen sin más:

Observación 7.8   El código de Reed-Muller ${\cal R}(m,r)$ es el espacio generado por las funciones características de las variedades afines de dimensión al menos $m-r$:

$${\cal R}(m,r)={\cal L}\left\{\xi_A\vert\ A=\mbox{\boldmath $\... ...-r\,,\,\mbox{\boldmath $\varepsilon$}\in\mathbb{F}_2^m\right\}.$$

Observación 7.9   La función característica de cualquier variedad afín de dimensión $r+1$ está en el código dual de ${\cal R}(m,r)$. Por tanto,

$$A=\mbox{\boldmath$\varepsilon$}+V\,,\,\dim V=r+1\ \Longrightarrow\ \xi_A^TR_{mr} = {\bf0}.$$ (17)

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