Código de cobertura

En la teoría de codificación , un código de cobertura es un conjunto de elementos (llamados palabras de código ) en un espacio, con la propiedad de que cada elemento del espacio está dentro de una distancia fija de alguna palabra de código.

Sean , , enteros . Un código sobre un alfabeto Q de tamaño | Q | = q se llama código q -ario que cubre R de longitud n si para cada palabra hay una palabra de código tal que la distancia de Hamming . En otras palabras, las esferas (o bolas o dominios de torre) de radio R con respecto a la métrica de Hamming alrededor de las palabras de código de C tienen que agotar el espacio métrico finito . El radio de cobertura de un código C es el R más pequeño tal que C cubre R. Todo código perfecto es un código de cobertura de tamaño mínimo. ${\displaystyle q\geq 2}$${\displaystyle n\geq 1}$${\displaystyle R\geq 0}$ ${\displaystyle C\subseteq Q^{n}}$ ${\displaystyle y\in Q^{n}}$ ${\displaystyle x\en C}$ ${\displaystyle d_{H}(x,y)\leq R}$ ${\displaystyle Q^{n}}$

C = {0134,0223,1402,1431,1444,2123,2234,3002,3310,4010,4341} es un código 5-ario de 2 coberturas de longitud 4. ^[1]

La determinación del tamaño mínimo de un código q -ario R -cubriendo con longitud n es un problema muy difícil. En muchos casos, solo se conocen los límites superior e inferior con una gran brecha entre ellos. Cada construcción de un código de cubrimiento da un límite superior en K _q ( n ,  R ). Los límites inferiores incluyen el límite de cubrimiento de esfera y los límites de Rodemich y . ^[2] El problema de cubrimiento está estrechamente relacionado con el problema de empaquetamiento en , es decir, la determinación del tamaño máximo de un código q -ario e - corrección de errores de longitud n . $Estilo de visualización Kq(n,R)$${\displaystyle K_{q}(n,1)\geq q^{n-1}/(n-1)}$${\displaystyle K_{q}(n,n-2)\geq q^{2}/(n-1)}$${\displaystyle Q^{n}}$

Un caso particular es el problema de las quinielas , basado en las apuestas de fútbol , ​​en el que se pretende elaborar un sistema de apuestas sobre n partidos de fútbol que, independientemente del resultado, tenga como máximo R 'fallos'. Así, para n partidos con como máximo un 'fallo', se busca una cobertura ternaria, K ₃ ( n ,1).

Si entonces se necesitan 3 ^{n - k} , entonces para n = 4, k = 2, se necesitan 9; para n = 13, k = 3, se necesitan 59049. ^[3] Los mejores límites conocidos a partir de 2011 ^[4] son ${\displaystyle n={\tfrac {1}{2}}(3^{k}-1)}$

El trabajo estándar ^[5] sobre códigos de cobertura enumera las siguientes aplicaciones.

• Compresión con distorsión
• Compresión de datos
• Descifrando errores y borrados
• Radiodifusión en redes de interconexión
• Quinielas de fútbol ^[6]
• Recuerdos que se escriben una sola vez
• Partido Berlekamp-Gale
• Codificación de voz
• Telecomunicaciones celulares
• Sumas de subconjuntos y gráficos de Cayley

• Literatura sobre códigos de cobertura
• Límites en K q ( n , R ) {\displaystyle K_{q}(n,R)}