Se usan los códigos convolucionales extensivamente en las telecomunicaciones, en parte por la facilidad en que corrigen errores y en parte por la existencia de algoritmos rápidos de descodificación. Un código convolucional binario utiliza una matriz $r \times n$ binaria (las entradas son ceros o unos) y una secuencia de bits $x_0,x_1,x_2,\ldots$ que corresponde al mensaje por enviar. Sean $u_i=(x_i,x_{i+1},\ldots,x_{i+r})$ vectores de longitud $r$, y $v_i=u_iG$ vectores de longitud $n$. Observamos que todos los cálculos se hacen módulo $2$. Se envian los vectores $v_0,v_k,v_{2k},\ldots$, donde $k$ es un número entre $1$ y $r-1$. Supongamos que se reciben los vectores $w_i=v_i+e_i$, donde $e_i$ es el error que ha ocurrido durante la transmisión. El algoritmo de Viterbi considera todas las posibilidades de descodificación y cuando empiezan a ocurrir errores se siguen todas las posibilidades hasta un límite de errores fijado. Se rechazan los caminos que llevan demasiados errores y se sigue hasta que se hayan rechazado todos los caminos excepto uno. Las matrices $G$ que se usan en la práctica han sido elegidas heurísticamente. O sea,se han probado varias matrices $G$ y se han elegido las matrices que son las más fiables para corregir errores. En esta propuesta, se propone encontrar una manera de predecir cuantos errores (dependiendo de alguna distribución de probabilidad) se pueden corregir utilizando una matriz determinada. Se sabe que para los códigos de bloques de longitud $n$ y distancia mínima $d$ se corrigen hasta $\lfloor \frac{d-1}{2} \rfloor$ errores en cada $n$ bits de una palabra con probabilidad $1$. Nos gustaría hallar matrices $G$ con la siguiente propiedad. Cuando un error ocurre, el número de errores en una posible (pero incorrecta) descodificación crece rápido, y por lo tanto, se puede descartar en poco tiempo. Sea $G$ una matriz $r \times n$ de rango $n$. Si $xG=yG$ y la distancia entre $x$ y $y$ es grande, y además $x$ corresponde a la codificación que queremos descodificar, escogiendo la descodificación de $y$ se espera que el número de errores crezca rápido. Por lo tanto, puede que sea deseable utilizar matrices $G$ con la propiedad que $uG=0$ implica que $u$ tiene peso grande. (Si $xG=yG$ entonces $(x-y)G=0$ y por lo tanto la distancia entre $x$ y $y$ es grande.) Sea $H$ la matrix $(r-n) \times r$ con la propiedad $HG=0$. Queremos probar matrices $G$ para las cuales la matriz $H$ tiene la propiedad que los vectores del subespacio generado por las filas de $H$ no tienen peso peque\~no. {\bf Primer Objetivo} Escribir un programa que nos deja probar la hipótesis. Sea $G$ una matriz binario $10 \times 5$. \\ Generar secuencia $v$ de $100$ bits, a\~nadiendo 10 bits de ceros al inicio y al final de la secuencia. Sea $k=3$. De los 120 bits generamos $5 \times 120/3= 200$ bits (por lo tanto la tasa de información es $100/200=1/2$.) Genera una secuencia $e$ de 200 bits de peso $Bin(200, \frac{1}{10})$ de errores. Descodifica $v+e$ con el algoritmo de Viterbi rechazando caminos que llevan más de dos/tres errores. Comprueba la descodificación. Aplica el progama 30 veces para una matriz aleatoria $G$ de rango $5$ y una matriz $G$ que es una matriz comprobadora de paridad para un código bloque de longitud $10$, dimensión $5$ y distancia mínima $4$. {\bf Segundo Objetivo} Análisis de los datos obtenidos para ver si en la práctica es mejor utilizar matrices $G$ que son matrices comprobadoras de paridad para códigos de bloques. Análisis de los datos para predecir cuantos errores se pueden corregir (depende de una probabilidad) utilizando una matriz determinada. |