Códigos Perfectos

En Códigos, sea $A$ un alfabeto con $|A|=q$, $v\in A^n$, $r\in \mathbb{R}$, y $r\ge 0$ tal que:

$S_q(v,r)=\{w\in A^n/d(v,w)\le r\}$

Donde $S_q$ es una esfera de radio $r$ y centro $v$ con volumen $|S_q(v,r)|=V_q(n,r)={\sum }_{k=0}^r\left(\genfrac{}{}{0ex}{}{n}{k}\right)(q-1{)}^k$.

Teniendo $C\subseteq A^n$, se define el radio de empaquetamiento de $C$ como el mayor entero $r$ tal que todas las esferas de radio $r$ son disjuntas. El radio de recubrimiento es el menor entero $s$ tal que la unión de todas las esferas de radio $s$ es $A^n$. Se tiene $r=\text{pr}(C)$ y $s=\text{cr}(C)$.

• $C$ es $t$-corrector $⟺$ las esferas $S_q(v,t)$ de radio$t$ con $v\in C$ son disjuntas.
• $C$ es exactamente $t$-corrector $⟺t=\text{pr}(C)$.
• $C$ es perfecto $⟺\text{pr}(C)=\text{cr}(C)$, es decir, existe un $r$ tal que $S_q$ son disjuntas y recubren $A^n$.

Condición de Empaquetamiento de Esferas: sea $C$ un $(n,m,d)$-código $q$-ario. $C$ es perfecto sí y solo si $d=2t+1$ (es impar) y $n\cdot V_q(n,t)=q^n$.

Tasa de Corrección de Errores: sea $C$ un $(n,m,d)$-código: $\delta (C)=\frac{\lfloor \frac{d-1}{2}\rfloor }{n}$. La tasa de corrección de errores $\delta$ es el número de errores que se corrigen en relación a la longitud de las palabras.

Sea $A_q(n,d)=\text{max}\{m/\exists (n,m,d)\text{-coˊdigo}q\text{-ario}\}$ tal que un $(n,A_q(n,d),d)$-código es optimable.

Problema Principal de la Teoría de Códigos: determinar la cota de Singleton $A_q(n,d)\le q^{n-d+1}$.

Teorema del Canal Ruidoso: nos dice que existen buenos códigos, pero no nos dice cómo obtenerlos.

La capacidad de un BSC con probabilidad de paso $p$ es $C(p)=1+p\cdot {\log }_{2}p+(1-p)\cdot {\log }_2(1-p)$. Si $R(C)<C(p)⟹\forall \epsilon >0\exists$ un $(n,m)$-código $C^{\prime }/R(C^{\prime })\ge R(C)\wedge p_{C^{\prime }}<\epsilon$. Podemos mejorar la tasa de transmisión hasta alcanzar la capacidad del BSC.