Código de convolución

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 27 de septiembre de 2018; las comprobaciones requieren 8 ediciones .

Un código convolucional es un código de corrección de errores en el que

en cada ciclo de reloj del codificador, los símbolos de la secuencia semi-infinita de entrada se convierten en símbolos de la secuencia de salida $k$ $n > k$
los personajes anteriores también están involucrados en la conversión $metro$
se cumple la propiedad de linealidad (si dos secuencias codificadas y corresponden a secuencias de código y , entonces la secuencia codificada corresponde a ). ${\matemáticas x}$ ${\matemáticas}$ $\mathbf X$ $\mathbf Y$ $a\mathbf x+b\mathbf y$ $a\mathbf X+b\mathbf Y$

Un código convolucional es un caso especial de los códigos de árbol y Trellis .

Orígenes

En 1955, L. M. Fink , quien en ese momento era el jefe del departamento de la Academia de Comunicaciones de Leningrado, propuso el primer código recurrente.

En 1959, el especialista occidental Hegelberger ( Hegelbeger ), que no tenía idea del trabajo de los científicos soviéticos en el campo de la codificación, "redescubrió" el código recurrente y lo nombró en su honor.

El propio Fink en su monografía “La teoría de la transmisión de mensajes discretos” [1] escribió: “En este código, la secuencia de símbolos de código no se divide en combinaciones de código separadas. Los símbolos de corrección se incluyen en el flujo de símbolos de información de manera que se coloca un símbolo de corrección entre cada dos símbolos de información. Denotando caracteres informativos mediante , y correctivos mediante , obtenemos la siguiente secuencia de caracteres: $ai}$ $bi}$

$a_{1}b_{1}\,a_{2}b_{2}\,a_{3}b_{3}\,\puntos \,a_{k}b_{k}\,a_{k +1}b_{k+1}\,\puntos$

Los símbolos de información están determinados por el mensaje transmitido, y los símbolos correctivos se forman de acuerdo con la siguiente regla:

$b_{i}=\left(a_{ks}+a_{k+s+1}\right)\mod 2$ (1.1)

donde es un entero arbitrario llamado paso de código ( ). Obviamente, si se recibe por error algún símbolo correctivo bi , la relación (1.1) en la secuencia recibida no se cumplirá para . En el caso de recepción errónea del símbolo de información, la relación (1.1) no se cumplirá para dos valores de , a saber, para y para . A partir de aquí es fácil derivar una regla de corrección de errores de decodificación. En la secuencia de código aceptada , se comprueba la relación (1.1) para cada uno . Si no se conforma con dos valores ( y ), y al mismo tiempo $s$ $s=0,1,2\puntos$ ${\ estilo de visualización i = k}$ $ai}$ $k_i$ $k_{1}=es-1$ $k_{2}=yo+s$ $b_{k}$ $k$ $k=k_{1}$ $k=k_{2}$

$k_{2}-k_{1}=2s+1$ (1.2)

entonces el elemento de información debe invertirse. $a_{k_{1}+s+1}$

Obviamente, la redundancia de código es . Te permite corregir todos los caracteres recibidos erróneamente, excepto algunas malas combinaciones. Entonces, si , proporciona una decodificación correcta cuando hay al menos tres (y en algunos casos dos) símbolos recibidos correctamente entre dos símbolos recibidos erróneamente (se tienen en cuenta tanto los símbolos de información como los de prueba). $1/2$ $s=0$

Esquema general de un codificador no recursivo

El diagrama del codificador de un código convolucional no recursivo se muestra en la Fig . 1 . Consiste en registros de desplazamiento -ary con longitudes . Algunas (quizás todas) las entradas y salidas de registro de algunas celdas de memoria están conectadas a varios módulos sumadores . El número de sumadores es mayor que el número de registros de desplazamiento: $k$ $q$ $m_1. m_2,...,m_k$ $norte$ $q$ $n > k$

En cada ciclo de reloj del codificador, los símbolos de información se envían a su entrada, ellos, junto con los símbolos almacenados en los registros de desplazamiento, se envían a las entradas de aquellos sumadores con los que existe una conexión. El resultado de la suma son símbolos de código listos para la transmisión. Luego se produce un desplazamiento en cada registro de desplazamiento: todas las celdas se desplazan un bit hacia la derecha, mientras que las celdas más a la izquierda se llenan con caracteres de entrada y las celdas más a la derecha se borran. Después de eso, se repite el ritmo. El estado inicial de los registros se conoce de antemano (normalmente cero). $k$ $norte$

La longitud total de todos los registros de desplazamiento se denomina límite de código y la longitud máxima se denomina retardo . $m = \sum_{i=1}^k m_i$ $w = \max\{m_1,...,m_k\}$

Los valores de los registros de desplazamiento en cada momento se denominan estado del codificador.

Codificadores convolucionales binarios

Para mayor claridad de presentación, describiremos la codificación convolucional según la acción del dispositivo de codificación correspondiente.

Un codificador convolucional es un dispositivo que generalmente recibe k símbolos de información de entrada en cada ciclo de operación y emite n símbolos de salida en la salida de cada ciclo. El número se denomina tasa de código relativa. k es el número de símbolos de información, n es el número de símbolos transmitidos al canal de comunicación en un ciclo de llegada al codificador del símbolo de información. Los símbolos de salida del ciclo bajo consideración dependen de m símbolos de información que llegan a este ciclo y a los anteriores, es decir, los símbolos de salida del código convolucional están determinados únicamente por sus símbolos de entrada y el estado, que depende de m - k símbolos de información anteriores . Los elementos principales del código convolucional son: registro de desplazamiento, sumador módulo 2, conmutador. $R={\frac{k}{n}}$

El registro de desplazamiento es un dispositivo de almacenamiento dinámico que almacena los caracteres binarios 0 y 1. La memoria de código determina el número de celdas de activación m en el registro de desplazamiento. Cuando llega un nuevo carácter de información a la entrada del registro de desplazamiento, el carácter almacenado en el bit más a la derecha se elimina del registro y se reinicia. Los caracteres restantes se mueven un dígito a la derecha y, por lo tanto, se libera el dígito más a la izquierda, donde llegará el nuevo carácter de información.

El sumador módulo 2 suma los símbolos que llegan a él 1 y 0. La regla de la suma módulo 2 es la siguiente: la suma de los símbolos binarios es 0 si el número de unos entre los símbolos que entran en las entradas es par, y es igual a 1 si este número es impar.

El interruptor lee secuencialmente los símbolos que llegan a sus entradas y establece la secuencia de símbolos de código en el canal de comunicación en la salida. Por analogía con los códigos de bloque, los códigos convolucionales se pueden clasificar en sistemáticos y no sistemáticos.

Un código convolucional sistemático es un código que contiene en su secuencia de salida de símbolos de código la secuencia de símbolos de información que lo generó. De lo contrario, el código se llama no sistemático.

Parámetros y características de los códigos convolucionales

Con la codificación convolucional, la transformación de secuencias de información en secuencias de código y de salida se produce de forma continua. El codificador convolucional binario contiene un registro de desplazamiento de m bits y sumadores de módulo 2 para generar símbolos de código en la secuencia de salida. Las entradas de los sumadores están conectadas a ciertos bits del registro. El interruptor de salida determina el orden en que los símbolos de código se envían al canal de comunicación. Entonces la estructura del código está determinada por las siguientes características.

El número de símbolos de información que llegan a la entrada del codificador en un ciclo es k.
El número de símbolos a la salida del codificador es n, correspondientes a los k símbolos de entrada durante el ciclo.
La tasa de código está determinada por la relación R=k/n y caracteriza la redundancia introducida durante la codificación.
Redundancia de código $\vartheta = 1 - R$
La memoria de código (la longitud de entrada de la restricción de código o la longitud de información de la palabra de código) está determinada por el grado máximo del polinomio generador en la matriz generadora G(X): $l = k \underset{i,j}{\max} \mathcal {b} \deg g _{i,j}(x)+1 \mathcal {c}$
La marca del código convolucional se denota en la mayoría de los casos (n, k, l), pero son posibles variaciones.
El peso w de las secuencias de código binario está determinado por el número de "unidades" incluidas en esta secuencia o palabras de código.
La distancia del código muestra el grado de diferencia entre las combinaciones de códigos i-th y j-th, siempre que tengan la misma longitud. Para cualquier combinación de dos códigos binarios, la distancia del código es igual al número de caracteres que no coinciden en ellos. En general, la distancia de código puede definirse como el resultado total de la suma módulo 2 de los bits del mismo nombre de combinaciones de código , donde y son los k-ésimos símbolos de las combinaciones de código i y j; L es la longitud de la combinación de códigos. $d$
$d_{i,j} = \sum_{k=1}^L k_{i,k} \oplus k_{j,k}$ $k_{i,j}$ $k_{jk}$
La distancia de código mínima es la distancia de Hamming más pequeña para un conjunto de palabras de código de longitud constante. Para encontrarlo, es necesario enumerar todos los posibles pares de combinaciones de códigos. Entonces obtenemos . $d_{min}$ $d_{min} = \min d_{ij}$

¡Pero! Esta definición es válida para códigos de bloque que tienen una longitud constante. Los códigos convolucionales son continuos y se caracterizan por muchas distancias mínimas determinadas por las longitudes de los segmentos iniciales de las secuencias de código, entre las cuales se toma la distancia mínima. El número de símbolos en la longitud de segmento L recibidos para procesamiento determina, en el lado receptor, el número de celdas en el decodificador.

Vista general de un codificador convolucional binario

Deje que el registro de desplazamiento contenga m celdas, es decir, la memoria del código es igual a m, el interruptor realiza un ciclo de sondeo, pasando los valores de los símbolos de información, donde m es un múltiplo de k , mientras que en un ciclo sondea n 2 salidas de codificador. El número de símbolos de código de salida afectados por un cambio en un símbolo de información de entrada es . El valor I all se denomina longitud total de la restricción de código . $1\lek<m$ $\geq$ $I_{todas}=\frac{mn}{k}$

Dado que las propiedades correctivas de un código convolucional particular están determinadas por la longitud de la restricción del código y la elección de los enlaces del registro de desplazamiento al sumador de módulo 2 ( XOR ), entonces para especificar la estructura del codificador convolucional , es necesario especificar qué bits del registro de desplazamiento están asociados con cada uno de los sumadores de módulo 2 ( XOR ).

La conexión del j-ésimo sumador módulo 2 se describe mediante la j-ésima secuencia generadora:

gj =( gj0 , gj1 , gj2 ,…, gjm -1 ), (4.1)

donde (4.2) $g_{ij} = \begin{cases} 1,&\text{si la etapa i del registro está vinculada con la puerta XOR}\\ 0,&\text{en otros casos} \end{cases}$

Parámetros típicos de códigos convolucionales: k, n= 1,2,…,8; R=k/n=1/4,…,7/8; m=2,…,10.

Método de establecimiento de códigos convolucionales

Es conveniente especificar un código convolucional usando polinomios generadores, los cuales están determinados por la forma de la fórmula (4.1) por analogía con cómo se hace esto para los códigos cíclicos de bloques lineales . [2]

El polinomio generador define completamente la estructura del codificador binario del código convolucional. A diferencia de los códigos de bloque , cada uno de los cuales se describe mediante un solo polinomio generador , un código convolucional se describe mediante varios polinomios generadores. El número de polinomios que describen el código convolucional está determinado por el número de símbolos de salida n . Representemos la secuencia de símbolos de información que llegan a la entrada del codificador como un polinomio

A(X)=a_{0}+a_{1}X+a_{2}X^{2}+\puntos,

donde X i es el símbolo del operador de retardo para i ciclos del registro de desplazamiento, e i = {0, 1} son símbolos binarios informativos. Los polinomios que describen n secuencias de símbolos de código que ingresan a la entrada del interruptor del codificador y luego al canal de comunicación tienen la forma

B_{j}(X)=b_{0}^{j}+b_{1}^{j}X+b_{2}^{j}X^{2}+\puntos,

donde están los símbolos de código binario en la j -ésima entrada del interruptor del codificador. ${\displaystyle b_{i}^{j}=\izquierda\{{0;1}\derecha\))$

El j -ésimo polinomio generador del código convolucional tiene la forma Además, debido a la linealidad del código convolucional y la notación aceptada, obtenemos . ${\displaystyle G_{j}(X)=g_{0}+g_{1}X+g_{2}X^{2}+\dots +g_{m-1}X^{m-1))$ $g_{i}={0;1}$ $B_j(X) = G_j(X) A(X)$

Usando la representación de un código convolucional usando polinomios generadores, se puede especificar un código convolucional por medio de secuencias de coeficientes de polinomios generadores escritos en forma binaria u octal. La notación octal es más compacta y se usa cuando el registro de desplazamiento del codificador es largo.

En el caso general, la secuencia de coeficientes del polinomio generador j-ésimo tendrá la forma y coincide con la secuencia generadora de código (4.1). Entonces, si es una secuencia de símbolos codificados, y es una secuencia de símbolos de código en la j -ésima entrada del interruptor codificador, entonces para cualquiera de ellos que aparezca en la -ésima vez ( ), podemos escribir $G^{j}={g_{0}^{j},g_{1}^{j},\puntos,g_{m-1}^{j))$ ${\displaystyle A={a_{0},a_{1},a_{2},\puntos ))$ ${\displaystyle B_{j}={b_{0}^{j},b_{1}^{j},b_{2}^{j},\puntos ))$ $\mu$ ${\ estilo de visualización \ mu = 0,1,2, \ puntos}$

b_{\mu }^{j}=\sum _{i=0}^{m-1}a_{\mu -i}g_{i}^{j}.

Así, cada símbolo de código de la secuencia de salida del codificador del código convolucional está determinado por la convolución de la información codificada y la secuencia generadora, que determina el nombre de los códigos convolucionales. Los códigos convolucionales son un caso especial de códigos iterativos o recurrentes.

Aplicación

Los códigos convolucionales se utilizan para la transmisión confiable de datos: video, comunicaciones móviles, comunicaciones por satélite. Se utilizan junto con el código Reed-Solomon y otros códigos similares. Antes de la invención de los códigos turbo , estos diseños eran los más eficientes y satisfacían el límite de Shannon. Además, la codificación convolucional se utiliza en el protocolo 802.11a en la capa MAC física para lograr una distribución uniforme de 0 y 1 después de que la señal pasa por el codificador , como resultado de lo cual se duplica el número de símbolos transmitidos y, por lo tanto, puede lograr una recepción favorable en el dispositivo receptor.

Véase también

Notas

↑ Fink L. M. Teoría de la transmisión de mensajes discretos
↑ Sagalovich, 2014 , capítulos 4 y 5.

Literatura

Gallagher R. Teoría de la información y comunicación confiable. - M. : radio soviética, 1974. - 720 p.
Morelos-Zaragoza R. El arte de la codificación correctora de errores. Métodos, algoritmos, aplicación / per. De inglés. V. B. Afanasiev . - M. : Technosfera, 2006. - 320 p. — (Mundo de la comunicación). - 2000 copias. — ISBN 5-94836-035-0 .
Fink L. M. Teoría de la transmisión de mensajes discretos. - M . : Sov. radial, 1963. - 576 págs.
Nikitin GI Códigos convolucionales: Libro de texto. - San Petersburgo. : Búhos. radial, 2001. - 78 págs.
Sagalovich Yu. L. Introducción a los códigos algebraicos - 3ª ed., revisada. y adicional - M. : IPPI RAN , 2014. - 310 p. — ISBN 978-5-901158-24-1
Nikitin G.I. Códigos convolucionales Tutorial
Banquet, VL "Construcciones de código de señal en sistemas de telecomunicaciones". R: Fénix (2009).
Kolesnik VD, Poltyrev G. Sh. Curso de Teoría de la Información. - "Ciencia", Capítulo. edición literatura física y matemática, 1982.
Ngok DK Investigación de métodos de búsqueda de códigos convolucionales óptimos y convolucionales perforados: dis. – Disertación para el grado de candidato de ciencias técnicas. San Petersburgo: LETI, 2014.

diccionarios y enciclopedias	gran chino Britannica (en línea)