Límite de Hamming

En la teoría de la codificación, el límite de Hamming define los límites de los valores posibles para los parámetros de un código de bloque arbitrario . También conocido como límite de empaquetamiento esférico . Los códigos que alcanzan el límite de Hamming se denominan códigos perfectos o compactos .

Redacción

Denotemos la cardinalidad máxima posible del código de longitud de bloque -ary y la distancia mínima ( el código de longitud de bloque -ary es un subconjunto de palabras con un alfabeto que consta de elementos). $A_q(n,\;d)$ $q$ $C$ $norte$ $d$ $q$ $norte$ $\mathcal{A}_q^n$ $\mathcal{A}_q$ $q$

Después

A_q(n,\;d)\leqslant\frac{q^n}{\displaystyle\sum_{k=0}^t\binom{n}{k}(q-1)^k},

dónde

t=\left\lpiso\frac{d-1}{2}\right\rpiso.

Prueba

Por definición , si la transmisión de la palabra clave ocurrió antes de los errores, con la ayuda de la decodificación limitada por la distancia mínima , podremos reconocer con precisión la palabra clave transmitida . $d$ $t=\left\lpiso\frac{d-1}{2}\right\rpiso$

Para una palabra clave dada , considere una esfera de radio alrededor de . Debido a que este código es capaz de corregir errores, ninguna esfera se cruza con otra y contiene $c\en C$ $t$ $C$ $t=\left\lpiso\frac{d-1}{2}\right\rpiso$

\sum_{k=0}^t \binom{n}{k}(q-1)^k

palabras, ya que podemos permitir que (o menos) caracteres (de todos los caracteres de una palabra) tomen uno de los posibles valores diferentes del valor del carácter correspondiente de una palabra dada (recordemos que el código en sí es -ic ).

t

norte

(q-1)

q

Deje denotar el número de palabras en . Al agrupar esferas alrededor de todas las palabras clave , notamos que el conjunto resultante está contenido en . Como las esferas son disjuntas, podemos sumar los elementos de cada una de ellas y obtener $METRO$ $C$ $\mathcal{A}_q^n$

M\times\sum_{k=0}^t\binom{n}{k}(q-1)^k\leqslant|\mathcal{A}_q^n|=q^n,

de donde para cualquier codigo $C$

M\leqslant\frac{q^n}{\displaystyle\sum_{k=0}^t\binom{n}{k}(q-1)^k},

y por lo tanto,

A_q(n,\;d)\leqslant\frac{q^n}{\displaystyle\sum_{k=0}^t\binom{n}{k}(q-1)^k}.

Códigos perfectos

Los códigos que alcanzan el límite de Hamming se llaman códigos perfectos . Se han descubierto los siguientes tipos de códigos perfectos: códigos Hamming y códigos Golay . También hay códigos perfectos triviales : códigos binarios de longitud impar, códigos con una palabra de código y códigos que incluyen el conjunto completo . $F_q^n$

Titvainen y Van Lint demostraron que cualquier código perfecto no trivial tiene los parámetros de un código Hamming o un código Golay [1] [2] .

Notas

↑ Tietavainen A., Perko A. No hay códigos binarios perfectos desconocidos. Anales Universitatis Turkuensis . Ser. A, I 148, 3-10[6], 1971.
↑ Lint van JH Teoremas de inexistencia para códigos de corrección de errores perfectos. — Computadoras en Álgebra y Teoría de Números . — vol. IV [6], 1971.

Literatura