Efficient algorithms for searching multiple burst-error correcting cyclic and shortened cyclic codes
Ana Lucila Sandoval Orozco · Dialnet (Universidad de la Rioja) · 2014
En muchos canales de comunicacion, debido a fallos fisicos / mecanicos, el ruido aparece en forma de rafagas. Los canales modelados por Gilbert y Elliot entran dentro de esta categoria. Ejemplos de tales canales son los canales inalambricos, los canales de grabacion magnetica y, recientemente, los canales flash, que tienden a sufrir degradacion en los datos deteriorandose su fiabilidad significativamente con el tiempo hasta un grado que compromete la integridad de los mismos. Por tanto, a menudo los errores tienden a ocurrir en grupos. A medida que aumenten las velocidades de transmision o las densidades de almacenamiento cobraran mayor importancia si cabe. En este tipo de canales no es conveniente utilizar codigos de correccion de errores aleatorios, siendo los codigos capaces de corregir multiples rafagas de errores herramientas eficaces de control de errores para estos canales. El problema de corregir rafagas de errores es dificil. En la practica, los codigos de Reed-Solomon, intercalados o no, se utilizan para corregir multiples rafagas. Sin embargo, es de interes encontrar eficientes codigos correctores de multiples rafagas de errores que sean optimos en terminos de redundancia. Esta Tesis se centra en la busqueda de tales codigos. En primer lugar este trabajo presenta algunas nuevas cotas para codigos correctores de multiples rafagas de errores que extienden las conocidas cotas de Reiger y de Gallager, demostrandose que ambas coinciden para los codigos de bloque. Para algunos valores, las nuevas cotas mejoran la cota de Hamming extendida. Por otro lado, es bien conocido que los codigos binarios MDS correctores de errores aleatorios son triviales. Sin embargo, no sucede lo mismo con los codigos correctores de rafagas. En segundo lugar este trabajo presenta propiedades de los codigos MDS correctores de rafagas de errores que son la generalizacion de las propiedades de los codigos correctores de errores aleatorios. En tercer lugar este trabajo presenta diferentes algoritmos de busqueda de optimos codigos ciclicos (acortados) correctores de multiples rafagas de errores. Estos algoritmos extienden un algoritmo previo de busqueda de optimos codigos correctores de una rafaga. La eficiencia de tales algoritmos radica en el hecho de que no se calculan los sindromes repetidos mediante la utilizacion de codigos de Gray. En cuarto y ultimo lugar, este trabajo presenta tablas exhaustivas con optimos codigos ciclicos (acortados) correctores de rafagas de errores para diferentes valores de espacio de guarda. Los codigos encontrados mejoran la literatura existente.Palabras clave: Algoritmos, canal de Gilber-Elliot, codigos ciclicos, codigos ciclicos acortados, codigos correctores de errores, codigos correctores de rafagas de errores, codigos correctores de una rafaga de errores, codigos correctores de multiples rafagas de errores, codigos de Gray, cota de Gallager, cota de Hamming, cota de Reiger, cota de Singleton, distancia de rafaga, eficiencia, errores aleatorios, espacio de guarda, Maxima Distancia Separable (MDS), optimos codigos correctores de rafagas de errores, peso de rafaga, rafagas all-around (AA), rafagas ciclicas, rafagas de errores, rafagas non-all-around (NAA), rafagas wrap-around, sindromes.