Código de corrección de errores de clasificación

En teoría de la codificación , los códigos de rango (también llamados códigos de Gabidulin ) son códigos de corrección de errores lineales no binarios ^{[ 1 ]} que no se basan en la métrica de Hamming , sino en la métrica de rango . Describen una forma sistemática de construir códigos que pueden detectar y corregir múltiples errores de rango aleatorios . Al agregar redundancia codificando una palabra de k símbolos a una palabra de n símbolos, un código de rango puede corregir cualquier error de rango hasta t = ⌊ ( d − 1) / 2 ⌋, donde d es una distancia de código. Como código de borrado , puede corregir hasta d − 1 borrados conocidos.        

Un código de rango es un código lineal algebraico sobre el campo finito.${\displaystyle GF(q^{N})}$similar al código Reed-Solomon .

El rango del vector sobre${\displaystyle GF(q^{N})}$es el número máximo de componentes linealmente independientes sobre${\displaystyle GF(q)}$. La distancia de rango entre dos vectores sobre${\displaystyle GF(q^{N})}$es el rango de la diferencia de estos vectores.

El código de rango corrige todos los errores cuyo rango del vector de error no sea mayor que t . 

Dejar${\displaystyle X^{n}}$sea ​​un espacio vectorial n -dimensional sobre el campo finito${\displaystyle GF\left({q^{N}}\right)}$, dónde${\displaystyle q}$es un poder de un primo y${\displaystyle N}$es un número entero positivo . Sea ${\displaystyle \left(u_{1},u_{2},\dots ,u_{N}\right)}$, con${\displaystyle u_{i}\in GF(q^{N})}$, ser una base de${\displaystyle GF\left({q^{N}}\right)}$como un espacio vectorial sobre el campo${\displaystyle GF\left({q}\right)}$.

Cada elemento${\displaystyle x_{i}\in GF\left({q^{N}}\right)}$puede representarse como${\displaystyle x_{i}=a_{1i}u_{1}+a_{2i}u_{2}+\dots +a_{Ni}u_{N}}$. Por lo tanto, cada vector${\displaystyle {\vec {x}}=\left({x_{1},x_{2},\dots ,x_{n}}\right)}$encima${\displaystyle GF\left({q^{N}}\right)}$se puede escribir como una matriz:

${\displaystyle {\vec {x}}=\left\|{\begin{array}{*{20}c}a_{1,1}&a_{1,2}&\ldots &a_{1,n}\\a_{2,1}&a_{2,2}&\ldots &a_{2,n}\\\ldots &\ldots &\ldots &\ldots \\a_{N,1}&a_{N,2}&\ldots &a_{N,n}\end{array}}\right\|}$

Rango del vector${\displaystyle {\vec {x}}}$sobre el campo${\displaystyle GF\left({q^{N}}\right)}$es un rango de la matriz correspondiente ${\displaystyle A\left({\vec {x}}\right)}$sobre el campo${\displaystyle GF\left({q}\right)}$denotado por${\displaystyle r\left({{\vec {x}};q}\right)}$.

El conjunto de todos los vectores${\displaystyle {\vec {x}}}$es un espacio${\displaystyle X^{n}=A_{N}^{n}}$El mapa${\displaystyle {\vec {x}}\to r\left({\vec {x}};q\right)}$) define una norma sobre${\displaystyle X^{n}}$y una métrica de clasificación :

${\displaystyle d\left({{\vec {x}};{\vec {y}}}\right)=r\left({{\vec {x}}-{\vec {y}};q}\right)}$

Un conjunto${\displaystyle \{x_{1},x_{2},\dots ,x_{n}\}}$de vectores de${\displaystyle X^{n}}$se denomina código con distancia de código ${\displaystyle d=\min d\left(x_{i},x_{j}\right)}$. Si el conjunto también forma un subespacio k -dimensional de${\displaystyle X^{n}}$, entonces se le llama un código lineal ( n , k ) con distancia${\displaystyle d}$Dicho código métrico de rango lineal siempre satisface la cota Singleton.${\displaystyle d\leq n-k+1}$con igualdad.

Existen varias construcciones conocidas de códigos de rango, que son códigos de distancia de rango máximo (o MRD) con d  = n − k + 1. El más fácil de construir se conoce como el código de Gabidulin (generalizado), fue descubierto primero por Delsarte (quien lo llamó un sistema Singleton ) y más tarde por Gabidulin ^{[ 2 ]} (y Kshevetskiy ^{[ 3 ]} ).     

Definamos una potencia de Frobenius.${\displaystyle [i]}$del elemento${\displaystyle x\in GF(q^{N})}$como

${\displaystyle x^{[i]}=x^{q^{i\mod N}}.\,}$

Entonces, cada vector${\displaystyle {\vec {g}}=(g_{1},g_{2},\dots ,g_{n}),~g_{i}\in GF(q^{N}),~n\leq N}$, linealmente independientes sobre${\displaystyle GF(q)}$, define una matriz generadora del código MRD ( n , k , d  = n − k + 1).     

${\displaystyle G=\left\|{\begin{array}{*{20}c}g_{1}&g_{2}&\dots &g_{n}\\g_{1}^{[m]}&g_{2}^{[m]}&\dots &g_{n}^{[m]}\\g_{1}^{[2m]}&g_{2}^{[2m]}&\dots &g_{n}^{[2m]}\\\dots &\dots &\dots &\dots \\g_{1}^{[(k-1)m]}&g_{2}^{[(k-1)m]}&\dots &g_{n}^{[(k-1)m]}\end{array}}\right\|,}$

dónde${\displaystyle \gcd(m,N)=1}$.

Existen varias propuestas de criptosistemas de clave pública basados ​​en códigos de rango. Sin embargo, la mayoría de ellos han demostrado ser inseguros (véase, por ejemplo, Journal of Cryptology, abril de 2008 ^{[ 4 ]} ).

Los códigos de rango también son útiles para la corrección de errores y borrados en la codificación de redes .

• Código lineal
• Corrección de errores de Reed-Solomon
• Algoritmo de Berlekamp-Massey
• Codificación de red

• Gabidulin, Ernst M. ( 1985), "Teoría de códigos con distancia de rango máxima" , Problemas de transmisión de información , 21 (1): 1–12
• Kshevetskiy, Alexander; Gabidulin, Ernst M. (4–9 de septiembre de 2005). «La nueva construcción de códigos de rango». Actas del Simposio Internacional sobre Teoría de la Información, 2005. ISIT 2005. págs. 2105–2108 . doi : 10.1109/ISIT.2005.1523717 . ISBN  978-0-7803-9151-2. S2CID 11679865 . 
• Gabidulin, Ernst M.; Pilipchuk, Nina I. (29 de junio - 4 de julio de 2003). «Un nuevo método de corrección de borrado mediante códigos de rango». Simposio Internacional IEEE sobre Teoría de la Información, 2003. Actas . pág.  423. doi : 10.1109/ISIT.2003.1228440 . ISBN 978-0-7803-7728-8. S2CID 122552232 . 

• Implementación en MATLAB de un códec Rank-metric