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

Código de corrección de errores

En la teoría de la codificación , los códigos de rango (también llamados códigos Gabidulin ) son códigos de corrección de errores lineales no binarios ^[1] no sobre Hamming sino sobre métricas de rango . Describieron una forma sistemática de crear códigos que pudieran detectar y corregir múltiples errores de clasificación aleatorios . Al agregar redundancia con la codificación de una palabra de k -símbolo a una palabra de n -símbolo, 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 similar al código Reed-Solomon . ${\displaystyle GF(q^{N})}$

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

El código de clasificación corrige todos los errores con una clasificación del vector de error no mayor que  t .

Métrica de clasificación

Sea un espacio vectorial de n dimensiones sobre el campo finito , donde es una potencia de un primo y es un número entero positivo. Sea , con , una base de como espacio vectorial sobre el campo . ${\displaystyle X^{n}}$ ${\displaystyle GF\left({q^{N}}\right)}$ ${\displaystyle q}$ ${\displaystyle N}$ ${\displaystyle \left(u_{1},u_{2},\dots ,u_{N}\right)}$ ${\displaystyle u_{i}\in GF(q^{N})}$ ${\displaystyle GF\left({q^{N}}\right)}$ ${\displaystyle GF\left({q}\right)}$

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

${\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\|}$

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

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

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

código de clasificación

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

Matriz generadora

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

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

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

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

${\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}$

Aplicaciones

Existen varias propuestas para criptosistemas de clave pública basados ​​en códigos de clasificación. Sin embargo, se ha demostrado que la mayoría de ellos son inseguros (ver, por ejemplo, Journal of Cryptology, abril de 2008 ^[4] ).

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

Ver también

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

Notas

1. Códigos para los cuales cada símbolo de entrada proviene de un conjunto de tamaño mayor que 2.
2. Gabidulin, Ernst M. (1985). "Teoría de códigos con máxima distancia de rango". Problemas de Transmisión de Información . 21 (1): 1–12.
3. Kshevetskiy, Alejandro; Gabidulin, Ernst M. (4 a 9 de septiembre de 2005). "La nueva construcción de códigos de rango". Actas. 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.
4. Overbeck, R. (2008). "Ataques estructurales a criptosistemas de clave pública basados ​​​​en códigos Gabidulin". Revista de criptología . 21 (2): 280–301. doi : 10.1007/s00145-007-9003-9 . S2CID  2393853.

Referencias

• Gabidulin, Ernst M. (1985), "Teoría de los códigos con distancia de rango máxima", Problemas de transmisión de información , 21 (1): 1–12
• Kshevetskiy, Alejandro; Gabidulin, Ernst M. (4 a 9 de septiembre de 2005). "La nueva construcción de códigos de rango". Actas. 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 clasificación". Simposio internacional IEEE sobre teoría de la información, 2003. Actas . pag. 423. doi :10.1109/ISIT.2003.1228440. ISBN 978-0-7803-7728-8. S2CID  122552232.

enlaces externos

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