Hispanopedia Wiki
Articulo de referencia

Código Justesen

n "},"message_length":{"wt":" k "},"rate":{"wt":"= \\frac{R}{2}=\\frac{k}{2n} "},"distance":{"wt":" \\delta n where \\delta\\geq \\Big(1-R-\\epsilon\\Big) H^{-1}_2\\big(\\frac{1...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría de la codificación , los códigos de Justesen forman una clase de códigos correctores de errores que tienen una tasa constante, una distancia relativa constante y un tamaño de alfabeto constante.

Antes del descubrimiento del código de corrección de errores de Justesen, no se conocía ningún código de corrección de errores que tuviera estos tres parámetros como constantes.

Posteriormente, se han descubierto otros códigos ECC con esta propiedad, por ejemplo, los códigos expansores . Estos códigos tienen aplicaciones importantes en informática, como en la construcción de espacios muestrales con sesgo pequeño .

Los códigos de Justesen se derivan de la concatenación de un código de Reed-Solomon y el conjunto de Wozencraft .

Los códigos Reed-Solomon utilizados logran una tasa constante y una distancia relativa constante a costa de un tamaño de alfabeto que es lineal con respecto a la longitud del mensaje.

El conjunto de códigos Wozencraft es una familia de códigos que logran una tasa constante y un tamaño de alfabeto constante, pero la distancia relativa solo es constante para la mayoría de los códigos de la familia.

La concatenación de los dos códigos primero codifica el mensaje utilizando el código Reed-Solomon, y luego codifica cada símbolo de la palabra clave utilizando un código del conjunto Wozencraft , empleando un código diferente del conjunto en cada posición de la palabra clave.

Esto difiere de la concatenación de códigos habitual, donde los códigos internos son los mismos para cada posición. El código de Justesen se puede construir de forma muy eficiente utilizando únicamente espacio logarítmico .

Definición

El código Justesen es la concatenación de un(norte,K,D)qk{\displaystyle (N,K,D)_{q^{k}}}código externodootút{\displaystyle C_{out}}y diferentes(norte,k,d)q{\displaystyle (n,k,d)_{q}}códigos internosdoinortei{\displaystyle C_{in}^{i}}, para1≤i≤norte{\displaystyle 1\leq i\leq N}.

Más precisamente, la concatenación de estos códigos, denotada pordootút∘(doinorte1,...,doinortenorte){\displaystyle C_{out}\circ (C_{in}^{1},...,C_{in}^{N})}, se define de la siguiente manera. Dado un mensajemetro∈[qk]K{\displaystyle m\in [q^{k}]^{K}}, calculamos la palabra clave producida por un código externodootút{\displaystyle C_{out}}:dootút(metro)=(do1,do2,..,donorte){\displaystyle C_{out}(m)=(c_{1},c_{2},..,c_{N})}.

Luego aplicamos cada código de N códigos internos lineales a cada coordenada de esa palabra clave para producir la palabra clave final; es decir,dootút∘(doinorte1,..,doinortenorte)(metro)=(doinorte1(do1),doinorte2(do2),..,doinortenorte(donorte)){\displaystyle C_{out}\circ (C_{in}^{1},..,C_{in}^{N})(m)=(C_{in}^{1}(c_{1}),C_{in}^{2}(c_{2}),..,C_{in}^{N}(c_{N}))}.

Si volvemos a la definición del código externo y los códigos internos lineales, esta definición del código de Justesen tiene sentido porque la palabra clave del código externo es un vector connorte{\displaystyle N}elementos, y tenemosnorte{\displaystyle N}códigos internos lineales que se aplicarán para aquellosnorte{\displaystyle N}elementos.

Aquí está el código de Justesen, el código externo.dootút{\displaystyle C_{out}}se elige para ser el código Reed Solomon sobre un campoFqk{\displaystyle \mathbb {F} _{q^{k}}}evaluado duranteFqk−{0}{\displaystyle \mathbb {F} _{q^{k}}-\{0\}}tasa​R{\displaystyle R},0{\displaystyle 0}<R{\displaystyle R}<1{\displaystyle 1}.

El código exteriordootút{\displaystyle C_{out}}tener la distancia relativaδotút=1−R{\displaystyle \delta _{out}=1-R}y longitud del bloque denorte=qk−1{\displaystyle N=q^{k}-1}El conjunto de códigos internos es el conjunto Wozencraft .{doinorteα}α∈Fqk∗{\displaystyle \{C_{in}^{\alpha }\}_{\alpha \in \mathbb {F} _{q^{k}}^{*}}}.

Propiedad del código de Justesen

Como los códigos lineales en el conjunto de Wonzencraft tienen la tasa12{\displaystyle {\frac {1}{2}}}, el código Justesen es el código concatenadodo∗=dootút∘(doinorte1,doinorte2,..,doinortenorte){\displaystyle C^{*}=C_{out}\circ (C_{in}^{1},C_{in}^{2},..,C_{in}^{N})}con la tasaR2{\displaystyle {\frac {R}{2}}}Tenemos el siguiente teorema que estima la distancia del código concatenado.do∗{\displaystyle C^{*}}.

Teorema

Dejarε>0.{\displaystyle \varepsilon >0.}Entoncesdo∗{\displaystyle C^{*}}tiene una distancia relativa de al menos(1−R−ε)Hq−1(12−ε).{\displaystyle (1-R-\varepsilon )H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right).}

Prueba

Para demostrar una cota inferior para la distancia de un códigodo∗{\displaystyle C^{*}}Demostramos que la distancia de Hamming de un par de palabras clave arbitrarias pero distintas tiene una cota inferior. Entonces, seaΔ(do1,do2){\displaystyle \Delta (c^{1},c^{2})}sea ​​la distancia de Hamming de dos palabras clavedo1{\displaystyle c^{1}}ydo2{\displaystyle c^{2}}. Para cualquier dado

metro1≠metro2∈(Fqk)K,{\displaystyle m_{1}\neq m_{2}\in \left(\mathbb {F} _{q^{k}}\right)^{K},}

queremos un límite inferior paraΔ(do∗(metro1),do∗(metro2)).{\displaystyle \Delta (C^{*}(m_{1}),C^{*}(m_{2})).}

Observa que sidootút(metro)=(do1,⋯,donorte){\displaystyle C_{out}(m)=(c_{1},\cdots ,c_{N})}, entoncesdo∗(metro)=(doinorte1(do1),⋯,doinortenorte(donorte)){\displaystyle C^{*}(m)=(C_{in}^{1}(c_{1}),\cdots ,C_{in}^{N}(c_{N}))}. Entonces, para el límite inferiorΔ(do∗(metro1),do∗(metro2)){\displaystyle \Delta (C^{*}(m_{1}),C^{*}(m_{2}))}, necesitamos tener en cuenta la distancia dedoinorte1,⋯,doinortenorte.{\displaystyle C_{in}^{1},\cdots ,C_{in}^{N}.}

Suponer

dootút(metro1)=(do11,⋯,donorte1)dootút(metro2)=(do12,⋯,donorte2){\displaystyle {\begin{aligned}C_{out}(m_{1})&=\left(c_{1}^{1},\cdots ,c_{N}^{1}\right)\\C_{out}(m_{2})&=\left(c_{1}^{2},\cdots ,c_{N}^{2}\right)\end{aligned}}}

Recuerda que{doinorte1,⋯,doinortenorte}{\displaystyle \left\{C_{in}^{1},\cdots ,C_{in}^{N}\right\}}es un conjunto de Wozencraft . Debido al "teorema del conjunto de Wonzencraft", hay al menos(1−ε)norte{\displaystyle (1-\varepsilon)N}códigos linealesdoinortei{\displaystyle C_{in}^{i}}que tienen distanciaHq−1(12−ε)⋅2k.{\displaystyle H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.}Entonces, si para algunos1⩽i⩽norte,doi1≠doi2{\displaystyle 1\leqslant i\leqslant N,c_{i}^{1}\neq c_{i}^{2}}y el códigodoinortei{\displaystyle C_{in}^{i}}tiene distancia⩾Hq−1(12−ε)⋅2k,{\displaystyle \geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k,}entonces

Δ(doinortei(doi1),doinortei(doi2))⩾Hq−1(12−ε)⋅2k.{\displaystyle \Delta \left(C_{in}^{i}\left(c_{i}^{1}\right),C_{in}^{i}\left(c_{i}^{2}\right)\right)\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.}

Además, si tenemosT{\displaystyle T}números1⩽i⩽norte{\displaystyle 1\leqslant i\leqslant N}de tal manera quedoi1≠doi2{\displaystyle c_{i}^{1}\neq c_{i}^{2}}y el códigodoinortei{\displaystyle C_{in}^{i}}tiene distancia⩾Hq−1(12−ε)⋅2k,{\displaystyle \geqslant H_{q}^{-1}({\tfrac {1}{2}}-\varepsilon )\cdot 2k,}entonces

Δ(do∗(metro1),do∗(metro2))⩾Hq−1(12−ε)⋅2k⋅T.{\displaystyle \Delta \left(C^{*}(m_{1}),C^{*}(m_{2})\right)\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k\cdot T.}

Así que ahora la tarea final es encontrar un límite inferior paraT{\displaystyle T}. Definir:

S={i : 1⩽i⩽norte,doi1≠doi2}.{\displaystyle S=\left\{i\ :\ 1\leqslant i\leqslant N,c_{i}^{1}\neq c_{i}^{2}\right\}.}

EntoncesT{\displaystyle T}es el número de códigos linealesdoinortei,i∈S{\displaystyle C_{in}^{i},i\in S}tener la distanciaHq−1(12−ε)⋅2k.{\displaystyle H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k.}

Ahora queremos estimar|S|.{\displaystyle |S|.}Obviamente|S|=Δ(dootút(metro1),dootút(metro2))⩾(1−R)norte{\displaystyle |S|=\Delta (C_{out}(m_{1}),C_{out}(m_{2}))\geqslant (1-R)N}.

Debido al Teorema del Conjunto de Wozencraft , hay como máximoεnorte{\displaystyle \varepsilon N}códigos lineales que tienen una distancia menor queHq−1(12−ε)⋅2k,{\displaystyle H_{q}^{-1}({\tfrac {1}{2}}-\varepsilon )\cdot 2k,}entonces

T⩾|S|−εnorte⩾(1−R)norte−εnorte=(1−R−ε)norte.{\displaystyle T\geqslant |S|-\varepsilon N\geqslant (1-R)N-\varepsilon N=(1-R-\varepsilon )N.}

Finalmente, tenemos

Δ(do∗(metro1),do∗(metro2))⩾Hq−1(12−ε)⋅2k⋅T⩾Hq−1(12−ε)⋅2k⋅(1−R−ε)⋅norte.{\displaystyle \Delta (C^{*}(m_{1}),C^{*}(m_{2}))\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k\cdot T\geqslant H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right)\cdot 2k\cdot (1-R-\varepsilon )\cdot N.}

Esto es cierto para cualquier arbitrariometro1≠metro2{\displaystyle m_{1}\neq m_{2}}. Entoncesdo∗{\displaystyle C^{*}}tiene la distancia relativa al menos(1−R−ε)Hq−1(12−ε),{\displaystyle (1-R-\varepsilon )H_{q}^{-1}\left({\tfrac {1}{2}}-\varepsilon \right),}con lo cual se completa la demostración.

Comentarios

Queremos analizar el "código fuertemente explícito". La pregunta es, entonces, qué es el "código fuertemente explícito". En términos generales, para el código lineal, la propiedad "explícita" está relacionada con la complejidad de construir su matriz generadora G.

En efecto, eso significa que podemos calcular la matriz en el espacio logarítmico sin utilizar el algoritmo de fuerza bruta para verificar que un código tiene una distancia dada que cumple.

Para los demás códigos que no son lineales, podemos considerar la complejidad del algoritmo de codificación.

Así pues, podemos ver claramente que los códigos de Wonzencraft y Reed-Solomon son muy explícitos. Por lo tanto, tenemos el siguiente resultado:

Corolario: El código concatenadodo∗{\displaystyle C^{*}}es un código asintóticamente bueno (es decir, tasaR{\displaystyle R}> 0 y distancia relativaδ{\displaystyle \delta }> 0 para q pequeño) y tiene una construcción fuertemente explícita.

Un ejemplo de código Justesen

El siguiente código, ligeramente diferente, se conoce como código Justesen en MacWilliams/MacWilliams. Se trata del caso particular del código Justesen mencionado anteriormente para un conjunto Wonzencraft muy específico:

Sea R un código Reed-Solomon de longitud N = 2 m − 1, rango K y peso mínimo N − K + 1.      

Los símbolos de R son elementos de F = GF(2 m ) y las palabras clave se obtienen tomando cada polinomio ƒ sobre F de grado menor que K y enumerando los valores de ƒ en los elementos no nulos de F en algún orden predeterminado.

Sea α un elemento primitivo de F. Para una palabra clave a = ( a 1 ,  ..., a N ) de R , sea b el vector de longitud 2 N sobre F dado por 

b=(a1,a1,a2,α1a2,…,anorte,αnorte−1anorte){\displaystyle \mathbf {b} =\left(a_{1},a_{1},a_{2},\alpha ^{1}a_{2},\ldots ,a_{N},\alpha ^{N-1}a_{N}\right)}

y sea c el vector de longitud 2 N m obtenido de b expresando cada elemento de F como un vector binario de longitud m . El código de Justesen es el código lineal que contiene todos esos c .

Los parámetros de este código son longitud 2 m N , dimensión m K y distancia mínima al menos

∑i=1ℓi(2metroi),{\displaystyle \sum _{i=1}^{\ell }i{\binom {2m}{i}},}

dóndeℓ{\displaystyle \ell }es el mayor entero que satisface∑i=1ℓ(2metroi)≤norte−K+1{\displaystyle \sum _{i=1}^{\ell }{\binom {2m}{i}}\leq N-K+1}(Véase MacWilliams/MacWilliams para una demostración).

Véase también

Referencias

  • Lección 28: Código Justesen. Curso de teoría de la codificación. Prof. Atri Rudra .
  • Lección 6: Códigos concatenados. Códigos de Forney. Códigos de Justesen. Teoría esencial de la codificación .
  • J. Justesen (1972). "Una clase de códigos algebraicos constructivos asintóticamente buenos". IEEE Trans. Inf. Theory . 18 (5): 652– 656. doi : 10.1109/TIT.1972.1054893 .
  • FJ MacWilliams ; NJA Sloane (1977). La teoría de los códigos correctores de errores . North-Holland. págs. 306–316 . ISBN  0-444-85193-3.