El canal de eliminación: resultados, algoritmos y aproximaciones

Abstract

Las fallas en la transmisión de datos pueden afectar a cualquier persona, desde el que envía un mensaje de texto en un chat, hasta el que guarda datos en una memoria USB. ¿Si se pierden datos, se podrán recuperar? ¿Fue culpa del canal utilizado? El canal de eliminación es el canal de comunicación punto a punto más simple que modela la falta de sincronización, (aparición o pérdida de datos). A pesar de importantes esfuerzos, poco se sabe sobre su capacidad, y menos aún sobre los esquemas de codificación y algoritmos óptimos. Para este trabajo se realizó un estudio sistemático de este problema, se efectuó una revisión de la teoría actual presentando algunos avances recientes y se propuso un esquema de codificación por repetición, basado en las cotas de Chernoff, que incluye las funciones de codificación y decodificación apropiadas y eficientes junto con su implementación en Matlab, todo en un canal artificial llamado canal de Ω-eliminación, así se implementó un algoritmo que simula el canal y se estableció la relación de capacidad entre el canal de eliminación y el canal artificial y como al desarrollar la teoría para este nuevo canal, se pueden conseguir avances significativos en el problema de calcular la capacidad del canal de eliminación, problema aun abierto al día de hoy.

Abstract. The communication failures can affect anyone, from sending a text message on a chat, to which stores data on a USB stick. If data is lost, they can be recovered? Was it the fault of the channel used? The binary deletion channel is the communication channel simpler point to point modeling synchronization errors (appearance or loss of data). Despite significant efforts, little is known about their capacity, and even less about the optimal coding schemes and algorithms. For this work, a systematic study of this problem was performed, a review of current theory was made by presenting some recent developments and a coding scheme by repetition, based on the Chernoff bounds, including the functions of encoding and decoding appropriate and efficient proposed with their implementation in Matlab , all in an artificial channel called Ω- deletion channel and an algorithm that simulates the channel was implemented and the relationship between the channel capacity and the deletion artificial channel was established to develop and as theory for this new channel, can make significant progress on the problem of calculating the deletion channel capacity problem still open today.