Hispanopedia Wiki
Articulo de referencia

Código de bloque

En la teoría de la codificación , los códigos de bloques constituyen una familia amplia e importante de códigos correctores de errores que codifican datos en bloques. Existen nu...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría de la codificación , los códigos de bloques constituyen una familia amplia e importante de códigos correctores de errores que codifican datos en bloques. Existen numerosos ejemplos de códigos de bloques, muchos de los cuales tienen una amplia gama de aplicaciones prácticas. La definición abstracta de los códigos de bloques resulta conceptualmente útil, ya que permite a teóricos de la codificación, matemáticos e informáticos estudiar las limitaciones de todos los códigos de bloques de forma unificada. Dichas limitaciones suelen adoptar la forma de límites que relacionan diferentes parámetros del código de bloques entre sí, como su tasa y su capacidad para detectar y corregir errores.

Ejemplos de códigos de bloques son los códigos de Reed-Solomon , Hamming , Hadamard , Expander , Golay , Reed-Muller y Polar . Estos ejemplos también pertenecen a la clase de códigos lineales , por lo que se denominan códigos de bloques lineales . En particular, estos códigos se conocen como códigos de bloques algebraicos o cíclicos, ya que pueden generarse mediante polinomios booleanos.

Los códigos de bloques algebraicos se decodifican normalmente mediante decodificadores algebraicos.

El término código de bloque también puede referirse a cualquier código corrector de errores que actúe sobre un bloque dek{\displaystyle k}bits de datos de entrada para producirnorte{\displaystyle n}bits de datos de salida(norte,k){\displaystyle (n,k)}En consecuencia, el codificador de bloques es un dispositivo sin memoria . Según esta definición, códigos como los códigos turbo , los códigos convolucionales terminados y otros códigos decodificables iterativamente (códigos tipo turbo) también se considerarían códigos de bloques. Un codificador convolucional no terminado sería un ejemplo de código no de bloques (sin marco), que tiene memoria y se clasifica como código de árbol .

Este artículo trata sobre los "códigos de bloques algebraicos".

El código del bloque y sus parámetros

Los códigos de corrección de errores se utilizan para transmitir datos digitales de forma fiable a través de canales de comunicación inestables y con ruido . Cuando un emisor desea transmitir un flujo de datos, posiblemente muy largo, mediante un código de bloques, divide el flujo en fragmentos de tamaño fijo. Cada fragmento se denomina mensaje , y el procedimiento del código de bloques codifica cada mensaje individualmente en una palabra clave, también llamada bloque . A continuación, el emisor transmite todos los bloques al receptor, quien puede utilizar un mecanismo de decodificación para recuperar (con suerte) los mensajes originales a partir de los bloques recibidos, que podrían estar dañados. El rendimiento y el éxito de la transmisión dependen de los parámetros del canal y del código de bloques.

Formalmente, un código de bloque es una asignación inyectiva.

do:Σk→Σnorte{\displaystyle C:\Sigma ^{k}\to \Sigma ^{n}}.

Aquí,Σ{\displaystyle \Sigma }es un conjunto finito y no vacío yk{\displaystyle k}ynorte{\displaystyle n}son números enteros. El significado y la importancia de estos tres parámetros y otros parámetros relacionados con el código se describen a continuación.

El alfabeto Σ

El flujo de datos que se va a codificar se modela como una cadena sobre algún alfabeto.Σ{\displaystyle \Sigma }El tamaño|Σ|{\displaystyle |\Sigma |}del alfabeto se escribe a menudo comoq{\displaystyle q}. Siq=2{\displaystyle q=2}, entonces el código de bloque se llama código de bloque binario . En muchas aplicaciones es útil considerarq{\displaystyle q}ser una potencia principal y para identificarΣ{\displaystyle \Sigma }con el campo finitoFq{\displaystyle \mathbb {F} _{q}}.

La longitud del mensaje k

Los mensajes son elementosmetro{\displaystyle m}deΣk{\displaystyle \Sigma ^{k}}, es decir, cadenas de longitudk{\displaystyle k}. Por lo tanto, el númerok{\displaystyle k}Se denomina longitud o dimensión del mensaje de un código de bloque.

La longitud del bloque n

La longitud del bloquenorte{\displaystyle n}de un código de bloque es el número de símbolos en un bloque. Por lo tanto, los elementosdo{\displaystyle c}deΣnorte{\displaystyle \Sigma ^{n}}son cadenas de longitudnorte{\displaystyle n}y corresponden a bloques que pueden ser recibidos por el receptor. Por lo tanto, también se les llama palabras recibidas. Sido=do(metro){\displaystyle c=C(m)}para algún mensajemetro{\displaystyle m}, entoncesdo{\displaystyle c}se llama la palabra clave demetro{\displaystyle m}.

La tasa R

La tasa de un código de bloque se define como la relación entre la longitud de su mensaje y la longitud de su bloque:

R=k/norte{\displaystyle R=k/n}.

Una tasa alta significa que la cantidad de mensaje real por bloque transmitido es alta. En este sentido, la tasa mide la velocidad de transmisión y la cantidad1−R{\displaystyle 1-R}mide la sobrecarga que se produce debido a la codificación con el código de bloque. Es un hecho teórico de la información simple que la tasa no puede exceder1{\displaystyle 1}ya que los datos no se pueden comprimir sin pérdidas en general. Formalmente, esto se deduce del hecho de que el códigodo{\displaystyle C}es un mapa inyectivo.

La distancia d

La distancia o distancia mínima d de un código de bloque es el número mínimo de posiciones en las que difieren dos palabras clave distintas cualesquiera, y la distancia relativaδ{\displaystyle \delta }es la fracciónd/norte{\displaystyle d/n}Formalmente, para palabras recibidasdo1,do2∈Σnorte{\displaystyle c_{1},c_{2}\in \Sigma ^{n}}, dejarΔ(do1,do2){\displaystyle \Delta (c_{1},c_{2})}denota la distancia de Hamming entredo1{\displaystyle c_{1}}ydo2{\displaystyle c_{2}}, es decir, el número de posiciones en las quedo1{\displaystyle c_{1}}ydo2{\displaystyle c_{2}}difieren. Entonces la distancia mínimad{\displaystyle d}del códigodo{\displaystyle C}se define como

d:=minmetro1,metro2∈Σkmetro1≠metro2Δ[do(metro1),do(metro2)]{\displaystyle d:=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]}.

Dado que cualquier código debe ser inyectivo , dos palabras clave cualesquiera discreparán en al menos una posición, por lo que la distancia de cualquier código es al menos1{\displaystyle 1}Además, la distancia es igual al peso mínimo para los códigos de bloques lineales porque:

minmetro1,metro2∈Σkmetro1≠metro2Δ[do(metro1),do(metro2)]=minmetro1,metro2∈Σkmetro1≠metro2Δ[0,do(metro2)−do(metro1)]=minmetro∈Σkmetro≠0w[do(metro)]=wmin{\displaystyle \min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [\mathbf {0} ,C(m_{2})-C(m_{1})]=\min _{m\in \Sigma ^{k} \atop m\neq \mathbf {0} }w[C(m)]=w_{\min }}.

Una mayor distancia permite una mayor corrección y detección de errores. Por ejemplo, si solo consideramos los errores que pueden cambiar los símbolos de la palabra clave enviada, pero nunca borrarlos ni agregarlos, entonces el número de errores es el número de posiciones en las que la palabra clave enviada y la palabra recibida difieren. Un código con distancia d permite al receptor detectar hastad−1{\displaystyle d-1}errores de transmisión desde que se cambiód−1{\displaystyle d-1}Las posiciones de una palabra clave nunca pueden generar accidentalmente otra palabra clave. Además, si no más de(d−1)/2{\displaystyle (d-1)/2}Si se producen errores de transmisión, el receptor puede decodificar de forma única la palabra recibida en una palabra clave. Esto se debe a que cada palabra recibida tiene como máximo una palabra clave a distancia.(d−1)/2{\displaystyle (d-1)/2}Si más de .(d−1)/2{\displaystyle (d-1)/2}En caso de errores de transmisión, el receptor generalmente no puede decodificar de forma unívoca la palabra recibida, ya que puede haber varias palabras clave posibles. Una forma de que el receptor gestione esta situación es mediante la decodificación por lista , en la que el decodificador genera una lista con todas las palabras clave dentro de un radio determinado.

La notación(norte,k,d)q{\displaystyle (n,k,d)_{q}}describe un código de bloques sobre un alfabetoΣ{\displaystyle \Sigma }de tamañoq{\displaystyle q}, con una longitud de bloquenorte{\displaystyle n}longitud del mensajek{\displaystyle k}y distanciad{\displaystyle d}. Si el código de bloque es un código de bloque lineal, entonces los corchetes en la notación[norte,k,d]q{\displaystyle [n,k,d]_{q}}se utilizan para representar ese hecho. Para códigos binarios conq=2{\displaystyle q=2}, a veces se omite el índice. Para códigos separables de distancia máxima , la distancia siempre esd=norte−k+1{\displaystyle d=n-k+1}, pero a veces la distancia precisa no se conoce, no es trivial de probar o afirmar, o no es necesaria. En tales casos, lad{\displaystyle d}-Puede que falte algún componente.

A veces, especialmente para códigos que no son de bloques, la notación(norte,METRO,d)q{\displaystyle (n,M,d)_{q}}se utiliza para códigos que contienenMETRO{\displaystyle M}palabras clave de longitudnorte{\displaystyle n}. Para códigos de bloque con mensajes de longitudk{\displaystyle k}sobre un alfabeto de tamañoq{\displaystyle q}, este número seríaMETRO=qk{\displaystyle M=q^{k}}.

Ejemplos

Como se mencionó anteriormente, existe una gran cantidad de códigos correctores de errores que en realidad son códigos de bloques. El primer código corrector de errores fue el código Hamming(7,4) , desarrollado por Richard W. Hamming en 1950. Este código transforma un mensaje que consta de 4 bits en una palabra clave de 7 bits agregando 3 bits de paridad. Por lo tanto, este código es un código de bloques. Resulta que también es un código lineal y que tiene una distancia de 3. En la notación abreviada anterior, esto significa que el código Hamming(7,4) es un[7,4,3]2{\displaystyle [7,4,3]_{2}}código.

Los códigos Reed-Solomon son una familia de códigos.[norte,k,d]q{\displaystyle [n,k,d]_{q}}códigos cond=norte−k+1{\displaystyle d=n-k+1}yq{\displaystyle q}ser una potencia principal . Los códigos de rango son una familia de[norte,k,d]q{\displaystyle [n,k,d]_{q}}códigos cond≤norte−k+1{\displaystyle d\leq n-k+1}. Los códigos de Hadamard son una familia de[norte,k,d]2{\displaystyle [n,k,d]_{2}}códigos connorte=2k−1{\displaystyle n=2^{k-1}}yd=2k−2{\displaystyle d=2^{k-2}}.

Propiedades de detección y corrección de errores

Una palabra clavedo∈Σnorte{\displaystyle c\in \Sigma ^{n}}podría considerarse como un punto en elnorte{\displaystyle n}-espacio dimensionalΣnorte{\displaystyle \Sigma ^{n}}y el códigodo{\displaystyle {\mathcal {C}}}es el subconjunto deΣnorte{\displaystyle \Sigma ^{n}}. Un códigodo{\displaystyle {\mathcal {C}}}tiene distanciad{\displaystyle d}significa que∀do∈do{\displaystyle \forall c\in {\mathcal {C}}}, no hay otra palabra clave en la bola de Hamming centrada endo{\displaystyle c}con radiod−1{\displaystyle d-1}, que se define como la colección denorte{\displaystyle n}-palabras de dimensión cuya distancia de Hamming ado{\displaystyle c}no es más qued−1{\displaystyle d-1}. Similarmente,do{\displaystyle {\mathcal {C}}}con distancia (mínima)d{\displaystyle d}tiene las siguientes propiedades:

  • do{\displaystyle {\mathcal {C}}}puede detectard−1{\displaystyle d-1}errores  : Porque una palabra clavedo{\displaystyle c}es la única palabra clave en la bola de Hamming centrada en sí misma con radiod−1{\displaystyle d-1}, ningún patrón de error ded−1{\displaystyle d-1}o menos errores podrían cambiar una palabra clave por otra. Cuando el receptor detecta que el vector recibido no es una palabra clave dedo{\displaystyle {\mathcal {C}}}Los errores se detectan (pero no hay garantía de que se corrijan).
  • do{\displaystyle {\mathcal {C}}}puede corregir⌊d−12⌋{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }errores. Porque es una palabra clavedo{\displaystyle c}es la única palabra clave en la bola de Hamming centrada en sí misma con radiod−1{\displaystyle d-1}, las dos bolas de Hamming centradas en dos palabras clave diferentes respectivamente con ambos radios⌊d−12⌋{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }no se superponen entre sí. Por lo tanto, si consideramos la corrección de errores como encontrar la palabra clave más cercana a la palabra recibiday{\displaystyle y}, siempre y cuando el número de errores no sea más de⌊d−12⌋{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }, solo hay una palabra clave en la bola de jamón centrada eny{\displaystyle y}con radio⌊d−12⌋{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }Por lo tanto, todos los errores podrían corregirse.
  • Para decodificar en presencia de más de(d−1)/2{\displaystyle (d-1)/2}Se pueden utilizar errores, decodificación de listas o decodificación de máxima verosimilitud .
  • do{\displaystyle {\mathcal {C}}}puede corregird−1{\displaystyle d-1}borrados . Por borrado se entiende que se conoce la posición del símbolo borrado. La corrección podría lograrse medianteq{\displaystyle q}-decodificación de paso  : Enith{\displaystyle i^{th}}Al pasar la posición borrada se llena con elith{\displaystyle i^{th}}Se lleva a cabo la corrección de símbolos y errores. Debe haber una pasada en la que el número de errores no sea mayor que⌊d−12⌋{\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }y por lo tanto, las borraduras podrían corregirse.

Límites inferior y superior de los códigos de bloque

límite de Hamming
Existen límites teóricos (como el límite de Hamming), pero otra cuestión es qué códigos se pueden construir realmente. Es como empaquetar esferas en una caja en múltiples dimensiones. Este diagrama muestra los códigos construibles, que son lineales y binarios. El eje x muestra el número de símbolos protegidos k , y el eje y el número de símbolos de verificación necesarios n–k . Se representan los límites para diferentes distancias de Hamming, desde 1 (sin protección) hasta 34. Los códigos perfectos están marcados con puntos.
  • naranja claro en el eje x : códigos triviales no protegidos
  • Naranja en el eje Y : códigos de repetición triviales
  • naranja oscuro en el conjunto de datos d = 3: códigos de Hamming perfectos clásicos
  • rojo oscuro y más grande: el único código Golay binario perfecto

Familia de códigos

do={doi}i≥1{\displaystyle C=\{C_{i}\}_{i\geq 1}}se llama familia de códigos , dondedoi{\displaystyle C_{i}}es un(nortei,ki,di)q{\displaystyle (n_{i},k_{i},d_{i})_{q}}código con incremento monótononortei{\displaystyle n_{i}}.

La tasa de la familia de códigos C se define comoR(do)=límitei→∞kinortei{\displaystyle R(C)=\lim _{i\to \infty }{k_{i} \over n_{i}}}

La distancia relativa de la familia de códigos C se define comoδ(do)=límitei→∞dinortei{\displaystyle \delta (C)=\lim _{i\to \infty }{d_{i} \over n_{i}}}

Para explorar la relación entreR(do){\displaystyle R(C)}yδ(do){\displaystyle \delta (C)}Se conoce un conjunto de límites inferiores y superiores de los códigos de bloque.

Hamming se dirigió

R≤1−1norte⋅registroq⋅[∑i=0⌊δ⋅norte−12⌋(nortei)(q−1)i]{\displaystyle R\leq 1-{1 \over n}\cdot \log _{q}\cdot \left[\sum _{i=0}^{\left\lfloor {{\delta \cdot n-1} \over 2}\right\rfloor }{\binom {n}{i}}(q-1)^{i}\right]}

Singleton

El límite de Singleton es que la suma de la tasa y la distancia relativa de un código de bloque no puede ser mucho mayor que 1:

R+δ≤1+1norte{\displaystyle R+\delta \leq 1+{\frac {1}{n}}}.

En otras palabras, cada código de bloque satisface la desigualdad.k+d≤norte+1{\displaystyle k+d\leq n+1}Los códigos de Reed-Solomon son ejemplos no triviales de códigos que satisfacen la cota unitaria con igualdad .

Plotkin estaba atado

Paraq=2{\displaystyle q=2},R+2δ≤1{\displaystyle R+2\delta \leq 1}. En otras palabras,k+2d≤norte{\displaystyle k+2d\leq n}.

Para el caso general, se cumplen las siguientes cotas de Plotkin para cualquierdo⊆Fqnorte{\displaystyle C\subseteq \mathbb {F} _{q}^{n}}con distancia d :

  1. Sid=(1−1q)norte,|do|≤2qnorte{\displaystyle d=\left(1-{1 \over q}\right)n,|C|\leq 2qn}
  2. Sid>(1−1q)norte,|do|≤qdqd−(q−1)norte{\displaystyle d>\left(1-{1 \over q}\right)n,|C|\leq {qd \over {qd-\left(q-1\right)n}}}

Para cualquier código q -ario con distanciaδ{\displaystyle \delta },R≤1−(qq−1)δ+o(1){\displaystyle R\leq 1-\left({q \over {q-1}}\right)\delta +o\left(1\right)}

Gilbert-Varshamov vinculado

R≥1−Hq(δ)−ϵ{\displaystyle R\geq 1-H_{q}\left(\delta \right)-\epsilon }, dónde0≤δ≤1−1q,0≤ϵ≤1−Hq(δ){\displaystyle 0\leq \delta \leq 1-{1 \over q},0\leq \epsilon \leq 1-H_{q}\left(\delta \right)}, Hq(incógnita) =dmiF −incógnita⋅registroq⁡incógnitaq−1−(1−incógnita)⋅registroq⁡(1−incógnita){\displaystyle H_{q}\left(x\right)~{\overset {\underset {\mathrm {def} }{}}{=}}~-x\cdot \log _{q}{x \over {q-1}}-\left(1-x\right)\cdot \log _{q}{\left(1-x\right)}}es la función de entropía q -aria.

Johnson se dirige

DefinirJq(δ) =dmiF (1−1q)(1−1−qδq−1){\displaystyle J_{q}\left(\delta \right)~{\overset {\underset {\mathrm {def} }{}}{=}}~\left(1-{1 \over q}\right)\left(1-{\sqrt {1-{q\delta \over {q-1}}}}\right)}. DejarJq(norte,d,mi){\displaystyle J_{q}\left(n,d,e\right)}sea ​​el número máximo de palabras clave en una bola de Hamming de radio e para cualquier códigodo⊆Fqnorte{\displaystyle C\subseteq \mathbb {F} _{q}^{n}}de distancia d .

Luego tenemos el Johnson Bound  :Jq(norte,d,mi)≤qnorted{\displaystyle J_{q}\left(n,d,e\right)\leq qnd}, siminorte≤q−1q(1−1−qq−1⋅dnorte)=Jq(dnorte){\displaystyle {e \over n}\leq {{q-1} \over q}\left({1-{\sqrt {1-{q \over {q-1}}\cdot {d \over n}}}}\,\right)=J_{q}\left({d \over n}\right)}

Elias-Basálygo

R=registroq⁡|do|norte≤1−Hq(Jq(δ))+o(1){\displaystyle R={\log _{q}{|C|} \over n}\leq 1-H_{q}\left(J_{q}\left(\delta \right)\right)+o\left(1\right)}

Empaquetamientos de esferas y redes

Los códigos de bloques están vinculados al problema del empaquetamiento de esferas , que ha recibido cierta atención a lo largo de los años. En dos dimensiones, es fácil visualizarlo. Imaginemos un puñado de monedas planas sobre una mesa, apretándolas entre sí. El resultado es un patrón hexagonal, similar a un panal de abejas. Sin embargo, los códigos de bloques se basan en más dimensiones, que no se visualizan fácilmente. El potente código Golay, utilizado en las comunicaciones del espacio profundo, emplea 24 dimensiones. Si se utiliza como código binario (que es lo habitual), las dimensiones se refieren a la longitud de la palabra clave, tal como se definió anteriormente.

La teoría de la codificación utiliza el modelo de esfera N- dimensional. Por ejemplo, ¿cuántas monedas caben en un círculo sobre una mesa? En tres dimensiones, ¿cuántas canicas caben en un globo terráqueo? Otros factores influyen en la elección de un código. Por ejemplo, al empaquetar hexágonos dentro de una caja rectangular, quedará espacio vacío en las esquinas. A medida que las dimensiones aumentan, el porcentaje de espacio vacío disminuye. Sin embargo, en ciertas dimensiones, el empaquetado aprovecha todo el espacio, y estos códigos se denominan códigos perfectos. Existen muy pocos de estos códigos.

Otra propiedad es el número de vecinos que puede tener una sola palabra clave. [ 1 ] De nuevo, consideremos las monedas de un centavo como ejemplo. Primero, colocamos las monedas en una cuadrícula rectangular. Cada moneda tendrá 4 vecinos cercanos (y 4 en las esquinas que están más lejos). En un hexágono, cada moneda tendrá 6 vecinos cercanos. Respectivamente, en tres y cuatro dimensiones, el empaquetamiento máximo viene dado por la cuadrícula de 12 caras y la de 24 celdas con 12 y 24 vecinos, respectivamente. Cuando aumentamos las dimensiones, el número de vecinos cercanos aumenta muy rápidamente. En general, el valor viene dado por los números de contacto .

El resultado es que también aumenta el número de maneras en que el ruido puede hacer que el receptor elija un vecino (y, por lo tanto, un error). Esta es una limitación fundamental de los códigos de bloques, y de hecho de todos los códigos. Puede ser más difícil causar un error a un solo vecino, pero el número de vecinos puede ser lo suficientemente grande como para que la probabilidad total de error se vea afectada. [ 1 ]

Véase también

Referencias

  1. 1 2 3 Christian Schlegel y Lance Pérez (2004). Trellis y codificación turbo . Wiley-IEEE. pág. 73. ISBN  978-0-471-22755-7.
  • JH van Lint (1992). Introducción a la teoría de la codificación . GTM . Vol.  86 (2.ª  ed.). Springer-Verlag. p. 31. ISBN  3-540-54894-7.
  • FJ MacWilliams ; NJA Sloane (1977). La teoría de los códigos correctores de errores . North-Holland. pág . 35. ISBN  0-444-85193-3.
  • W. Huffman; V. Pless (2003). Fundamentos de los códigos correctores de errores . Cambridge University Press. ISBN 978-0-521-78280-7.
  • S. Lin; DJ Jr. Costello (1983). Codificación de control de errores: Fundamentos y aplicaciones . Prentice-Hall. ISBN 0-13-283796-X.
  • Charan Langton (2001) Conceptos de codificación y codificación por bloques
Lecturas relacionadas
6 articulos
Teoría de la codificaciónTeoría de la codificaciónLa teoría de la codificación es el estudio de las propiedades de los códigos y su respectiva idoneidad para aplicaciones específicas. Los códigos s...Código de corrección de erroresCódigo de corrección de erroresEn informática , telecomunicaciones , teoría de la información y teoría de codificación , la corrección de errores hacia adelante ( FEC ) o codific...MatemáticoMatemáticoUn matemático es alguien que utiliza un amplio conocimiento de las matemáticas en su trabajo, generalmente para resolver problemas matemáticos . Lo...Científico informáticoCientífico informáticoUn científico informático es un científico que se especializa en el estudio académico de la informática . [1]Reed–Solomon error correctionReed–Solomon error correctionIn information theory and coding theory, Reed–Solomon codes are a group of error-correcting codes that were introduced by Irving S. Reed and Gustav...Código de HammingCódigo de HammingEn informática y telecomunicaciones , los códigos de Hamming son una familia de códigos de corrección de errores lineales . Los códigos de Hamming ...