Borde único
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 15 de octubre de 2016; las comprobaciones requieren 2 ediciones .El límite de Singleton (llamado así por R.C. Singleton) impone un límite a la potencia de un código con caracteres del campo de longitud y la distancia mínima de Hamming .
Denotemos la máxima cardinalidad posible del código de longitud -ary ( el código -ary es un código sobre un campo de elementos). Sea la distancia mínima de Hamming entre dos palabras de código , es decir, para dos palabras de código cualesquiera y .
Después
Prueba
En primer lugar, tenga en cuenta que el límite superior de la cardinalidad máxima de cualquier código de longitud -aria es igual a , ya que cada componente de una palabra de código dada puede tomar uno de los diferentes valores independientemente de los otros componentes.
Sea un código -ic. Entonces todas las palabras en el código son diferentes entre sí. Si borramos los primeros caracteres de cada palabra, todas las palabras clave restantes deben permanecer diferentes, ya que la distancia de Hamming entre las palabras clave es al menos . Por lo tanto, el poder del código después de la eliminación de caracteres se mantuvo igual.
Nueva longitud de palabra
y, por lo tanto, la máxima cardinalidad posible de tal código es
De aquí se sigue el límite superior de la potencia para el código original :
Códigos de línea
En el caso de los códigos de línea , se puede escribir el límite Singleton como
o
Los códigos lineales para los que se cumple la igualdad se denominan códigos separables con una distancia máxima o códigos MDS. Representantes bien conocidos de esta familia de códigos son el código Reed-Solomon y los códigos formados a partir de él.
Literatura
- RC Singleton. Códigos q-nary de distancia máxima. IEEE Transactions on Information Theory , 10:116-118 [1, 11], 1964.
- Y. Komamiya. Aplicación de las matemáticas lógicas a la teoría de la información. Actas del 3er Congreso Nacional Japonés de Matemáticas Aplicadas , 437 [1], 1953.