7 votos

¿Qué es el diagrama de trellis para un código de bloque lineal?

Para el convolucional de los códigos no es el llamado diagrama de enrejado, para que la definición es bastante clara para mí, sin embargo, en sentido matemático no es.

He oído que puede ser definido por bloque lineal códigostambién. Códigos lineales tienen muy simple matemática significado - sólo los subespacios lineales en $(F_q)^n$. Así que supongo que el "enrejado" también debería ser algo simple.

Entonces, ¿cuál es el enrejado de un bloque lineal de código ?

12voto

Esta pregunta es estudiado muy a fondo en Alex Vardy del capítulo en el Manual de la Teoría de la Codificación. Puedo describir la idea a continuación.

Para obtener un enrejado para un bloque lineal de código $C$, tenemos que definir algo como un eje de tiempo para las posiciones de los símbolos individuales de todos los codewords. Así que, básicamente, un orden de los símbolos que ya está ahí: este es el primer símbolo, esta es la segunda,..., esta es la última. Más tarde lo desea, puede cambiar el orden, pero vamos a arreglar uno por ahora.

El enrejado recopila información acerca de los comienzos de codewords puede ser igualada con la que las terminaciones de tal manera que el resultado final será válida la palabra. En el caso de una línea de código, esto se traduce en una formulación algebraica de la siguiente manera.

Fijar un punto de $i,0<i<n,$ en el eje de tiempo. Considerar el llamado inicialmente el subespacio trivial $I_i(C)$ y finalmente el subespacio trivial $F_i(C)$ $C$ definido por $$ I_i(C)=\{\vec{c}=(c_1,c_2,\ldots,c_n)\C\mediados de c_j=0\ \text{para todo}\ j\le i\}. $$ y $$ F_i(C)=\{\vec{c}=(c_1,c_2,\ldots,c_n)\C\mediados de c_j=0\ \text{para todo}\ j> i\}. $$ Vamos a extender estas definiciones, al declarar que $F_0(C)=I_n(C)=\{0\}$ y $F_n(C)=I_0(C)=C$. La clave observaciones son que:

  1. La suma de subespacios $I_i(C)+F_i(C)$ es directo, es decir, se cruzan trivialmente.
  2. Si $\vec{c}\in C$, $\vec{c}_I\in I_i(C)$, $\vec{c}_F\in F_i(C)$ son arbitrarias, entonces el vector de $\vec{c}+\vec{c}_I$ es legal la palabra que está de acuerdo con $\vec{c}$ hasta e incluyendo el componente $c_i$, e $\vec{c}+\vec{c}_F$ es legal la palabra que está de acuerdo con $\vec{c}$ a partir de ese punto, es decir, en las posiciones $>i$. Además, todos los codewords con estas propiedades se incorporan de esta forma, porque si dos codewords de acuerdo hasta e incluyendo (resp. a partir de este punto), entonces su diferencia está en el principio trivial (resp. finalmente trivial) subcódigo.

Por lo que podemos particionar el código de $C$ en cosets de la subespacio $I_i(C)+F_i(C)$. Nos deja seleccionar una secuencia de puntos de división $0=i_0<i_1<i_2<\cdots<i_k=n$. Tenga en cuenta que no podemos usar todos los puntos como puntos de división. Con estos datos en la mano podemos construir un enrejado para $C$ como sigue. En punto de división $i_t$ tenemos el espacio de estado $$V_t(C)=C/(I_{i_t}(C)\oplus F_{i_t}(C).$$ We observe $V_0(C)$ and $V_k(C)$ son tanto trivial 0-espacios dimensionales. Estos nos dará un único inicial y el estado final, respectivamente.

El diagrama de enrejado es un grafo dirigido. Tiene un vértice para cada orden par $(t,a)$, con $0\le t\le k$ $a\in V_t(C).$ Para cada intervalo de $t,t+1$, podemos definir el subespacio $T_t=I_{i_{t+1}}(C)\oplus F_{i_t}(C)$. A continuación definimos un conjunto de aristas que conecta el vértice $(t,a)$ y el vértice $(t+1,a')$. Estos están en un bijective correspondencia con cosets $\vec{c}+T_t$ tal que $\vec{c}\in a\cap a'$. El número de aristas es lo $|a\cap a'|/|T_t|.$ Los bordes de la gráfica son etiquetados, y el borde está etiquetado con el secuencia de símbolos $c_{i_t+1},c_{i_t+2},\ldots,c_{i_{t+1}}$. Observar que: 1) si $a\cap a'=\emptyset$ no habrá bordes de$(t,a)$$(t+1,a')$, 2) todos los codewords en el coset $\vec{c}+T_t$ dar la misma secuencia de etiquetas.

Esto equivale a que por cada palabra clave $\vec{c}\in C$ hay un único camino de $(0,V_0(C))$ $(k,V_k(C))$de manera tal que en cada punto de división $i_t$ la ruta pasa a través de el vértice $(t,\vec{c}+I_{i_t}(C)\oplus F_{i_t}(C))$, y que se sigue por el borde asociados con $\vec{c}+T_t$ entre esos dos vértices. Podemos leer los componentes de la palabra $\vec{c}$ mediante la concatenación de las etiquetas de los bordes a lo largo de la ruta. Además, no es difícil mostrar que todos los caminos a través del enrejado de madera representan válido codewords.

Podemos descodificar, a continuación, utilizando el algoritmo de Viterbi tomar ventaja parcial de codewords compartida por muchas de las palabras - exactamente como en el caso de convolucional códigos.

El problema es que el número de cualquiera de los estados o de los bordes puede fácilmente ser muy grande. Por ejemplo, si sistemático se utiliza la codificación con un $k$-dimensiones código, entonces no hay ningún compartido secuencias de $k$ primeros símbolos entre los codewords (porque todos esos símbolos son una carga, y puede ser elegido libremente por el usuario). Esto significa que este punto de división el principio de subespacios triviales son todos trivial, y, en consecuencia, el espacio de estado pueden ser muy grandes (hasta $k$-dimensional, posiblemente más pequeños). Podemos probar y jugar el juego de permuting el símbolo de posiciones. Esta es una especie de "arte negro", y no es garantizado para reducir el tamaño de la espaldera significativamente. Por lo tanto, esta no es una herramienta mágica que nos permite de manera eficiente decodificar cualquier lineal de código con el algoritmo de Viterbi. Four section trellis of (16,11,4) extended Hamming code

Lo siento por los residuos de la basura en el fondo. La figura muestra un enrejado de madera de la extensión lineal binaria código de Hamming de longitud de 16, rango de 11 y una distancia mínima de 4. Los puntos de separación son en$i_0=0,i_1=4,i_2=8,i_3=12$$i_4=16$. El código está definido por la matriz de comprobación de paridad $$ H=\pmatrix{1111&1111&1111&1111\cr 1111&1111&0000&0000\cr 1111&0000&1111&0000\cr 1100&1100&1100&1100\cr 1010&1010&1010&1010\cr}. $$ Como en todos los enrejado del eje de tiempo se ejecuta de izquierda a derecha. Los vértices asociados con un determinado punto de división se apilan en la parte superior de uno al otro. Aquí todos los bordes son en realidad el doble bordes, es decir, dos bordes paralelos que va de un vértice a otro, las etiquetas de los dos bordes paralelos son siempre bit a bit de los complementos de cada uno de los otros. Finalmente trivial subcódigos se extendió por $$ F_4=\langle 1111 0000 0000 0000\rangle, $$ $$ F_8=F_4\oplus \langle 0000 1111 0000 0000, 0011 0011 0000 0000, 0101 0101 0000 0000\rangle, $$ $$ F_{12}=F_8\oplus\langle 0000 0000 1111 0000, 1100 1010 0110 0000, 1010 0110 1100 0000\rangle, $$ y han respectivas dimensiones 1,4,7. El principio trivial subcódigos son $$ I_{12}=\langle 0000 0000 0000 1111\rangle, $$ $$ I_8=I_{12}\oplus\langle 0000 0000 1111 0000, 0000 0000 1100 1100, 0000 0000 1010 1010\rangle, $$ $$ I_4=I_8\oplus\langle 0000 1111 0000 0000, 0000 0110 0101 0011, 0000 0011 0110 0101\rangle, $$ con dimensión complementaria tal que $\dim I_i\oplus F_i=8$ todos los $i\in\{4,8,12\}$. Las palabras de este código son de la forma $(a|b|c|d|)$, donde cada letra representa un vector en $\mathbb{F}_2^4$, es decir, un grupo de 4 bits. Las limitaciones son: $a+b+c+d$ debe ser $0000$ o $1111$. Las paridades de las ponderaciones de los grupos son de todos los impares o incluso todas.

0voto

rschwieb Puntos 60669

Estoy un poco oxidado en esto pero te voy a dar un tiro.

Bloque de códigos y convolucional códigos son fundamentalmente diferentes. Bloque de códigos generalmente no tienen "memoria", es decir, la codificación de los futuros palabras no depende de la codificación de las anteriores palabras.

Esta "memoria" es una de las cosas que hace convolucional códigos diferentes. La segunda cosa es que la codificación convolucional se lleva a cabo, básicamente, "bit a bit", pero el bloque de códigos necesita un bloque completo para llevar a cabo la etapa de codificación.

Un enrejado diagrama pretende capturar el proceso de bit a bit de codificación mediante la grabación de las transiciones entre estados, y la salida que se obtiene como una función del estado y la de entrada.

Desde el bloque de códigos lineales no tienen "estados" y no están codificados bit a bit, no veo (o no recuerdo) ¿cómo se puede formular un enrejado diagrama de bloque lineal de código.

Un diagrama de Hasse de la red de subespacios de $F_q^n$ está bien, pero no veo ninguna conexión real con enrejado de diagramas.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X