Forward Error Correction (FEC) scheme for a fishing radio-buoy system

Abstract

Introducción. Es innegable el efecto que, de un tiempo a esta parte, está teniendo la pesca masiva para nuestros océanos. Esto se debe a que una gran parte de todos los peces capturados que inicialmente van destinados al consumo humano se ve desperdiciada por dos principales motivos: no hay espacio suficiente para almacenar semejantes cantidades, o simplemente no termina por consumirse. Todo ello ha llevado a que en las últimas décadas hayan aparecido técnicas cuyo fin es realizar la pesca de una manera eficiente que, al mismo tiempo, cumpla con las demandas de la población y respete el medioambiente. Una de estas técnicas es la pesca mediante palangres. Esta técnica consiste en el uso de un sedal kilométrico, plagado de anzuelos, que va a la deriva por el mar. Para poder llevar a cabo la recogida de la pesca, es necesario tener un sistema radio-boya que permita obtener la posición de dicho palangre desde un barco.

El Proyecto. El objetivo principal que persigue este Proyecto de Fin de Grado no es otro que el de aumentar el rendimiento de un sistema radio-boya, como el previamente descrito, diseñado y fabricado por la compañía Enisa. Para ello, se estudiarán diferentes códigos basados en técnicas de corrección de errores (FEC). Al tratar de aumentar dicho rendimiento, los resultados que se esperan conseguir son variados. Uno de ellos es lograr una mejora en la respuesta frente a diferentes entornos donde la posibilidad de que se produzcan errores en la transmisión de los datos sea diferente. Del mismo modo, se pretende también conseguir un aumento en la cantidad de información enviada por transmisión y en el alcance que esta pueda llegar a tener.

Descripción del algoritmo. Debido a las limitaciones que presenta el microchip PIC16F18326 empleado en el sistema de radio-boya, se van a diseñar y estudiar unos códigos de corrección de errores para la transmisión y recepción de una cadena similares a los códigos Hamming. Como el microchip utiliza bytes de ocho bits, los tres casos a estudiar utilizarán todos los bits disponibles para cada uno de los bytes transmitidos. Hay dos tipos de bits posibles: los que contienen el mensaje que se pretende transmitir y aquellos conocidos como bits de paridad [1], cuya misión es la de ayudar a poder recuperar la información de manera fiable y con buen resultado. La tasa de información enviada, R, se basa en el número de bits que contienen el mensaje, k, y el número de bits total en un byte, n. Así: R = k/n Actualmente este valor se encuentra en un 20%, esto es, hay un 80% de la transmisión destinada a la recuperación del mensaje exclusivamente. Para poder aumentar estas cifras, se ha decidido estudiar tres códigos diferentes. El primero, caso (2, 8), utiliza dos bits por cada byte como mensaje R=25%, el segundo, caso (3, 8), utiliza tres bits por cada byte como mensaje R=37.5% y, finalmente, el último caso (4, 8), ha utilizado cuatro bits por cada byte como mensaje R=50%. Para llevar a cabo la codificación en cada caso, se ha seleccionado un conjunto de bytes tales que maximicen la mínima distancia Hamming entre ellos. La distancia Hamming [2] es el número de bits en los que difieren dos bytes distintos. Estos grupos de bytes serán asignados a cada uno de los posibles mensajes que se pueden enviar, es decir, en el caso (2, 8) habrá cuatro posibles mensajes a enviar, en el (3, 8) habrá ocho y en el (4, 8) habrá dieciséis. En el transmisor se dividirá cada byte de la cadena según el caso empleado, y a cada una de las partes resultantes se le asignará su correspondiente código antes de transmitir la información. Ya en el receptor, el algoritmo empleado se ayudará de una matriz H cuya finalidad es la de poder detectar y ubicar los errores que puedan aparecer durante el proceso de transmisión. Este proceso se lleva a cabo mediante la multiplicación de dicha matrix con el byte. Si el resultado de dicha operación es cero no se habría producido ningún error, pero si por el contrario sí que hubiese uno o más errores, el resultado identificaría inequívocamente cuales son los bits erróneos hasta el número de bits que cada algoritmo puede corregir. Así, solo habría que cambiar el valor de dichos bits y la información estaría recuperada.

Simulación y resultados. Para poder llevar a cabo una simulación y una comparación fiable de los nuevos algoritmos con el antiguo, se ha creado un código en Python que simula con fidelidad la transmisión y recepción de la información enviada por la boya. El entorno consta de tres funciones, una que simula la transmisión, otra la recepción y una tercera que modela una inclusión de bits de manera aleatoria en base a una probabilidad previamente establecida conocida como BER (Bit Error Rate). Los resultados obtenidos mostraron como se obtenía una gran mejora del rendimiento del algoritmo en comparación a las simulaciones del código previo, y la implementación cumplía con las especificaciones de tiempo requeridas para que pudiera aplicarse en un entorno real en los microcontroladores que se utilizan en el hardware actual.

Conclusiones. Tras todo el estudio llevado a cabo, se concluye que el algoritmo está listo para ser empleado en pruebas marítimas y comprobar su rendimiento en una situación real. Como trabajo futuro se abre la puerta a la implementación y estudio de técnicas más sofisticadas en el caso de que se empleara otro microprocesador con una capacidad mayor para operaciones complejas.

Referencias.

[1] Mary K. Wootters, Any errors in this dissertation are probably fixable: topics in probability and error correcting codes. PhD Thesis, Department of Mathematics, University of Michigan 2014.

[2] Richard W. Hamming, Error Detecting and Error Correcting Codes. The Bell System Technical Journal, Vol. 29, April 195Introduction. It is undeniable the effect that, for some time now, massive fishing is having on our oceans. This is due to the fact that a big part of all the fishes captured which are initially destined for human consumption is wasted for two main reasons: there is not enough space to store these huge amounts, or just because nobody finally consumes it. All of this has encouraged the development of new techniques whose primary goal is to create a more efficient way of fishing such that it can meet the demands of our society while being environmentally friendly. One of these techniques is called longline fishing. This technique consists in the use of a long line several kilometers in length, riddled with fishhooks and drifting through the sea. In order to being able to locate the longline, it is necessary to have a radio-buoy system that allows to obtain its position.

The Project. The main goal pursued by this Final Degree Project is no other than to increase the performance of a radio-buoy system, similar to the one previously described, designed and manufactured by Enisa. To this effect, a study will be carried out about different forward error correction (FEC) techniques and codes. Whilst trying to increase the performance, the results expected are diverse. One of them is to obtain an improvement in the response against different environments where the probability of errors during the transmission varies. Similarly, this project also aims to obtain a increase in the information sent per transmission and in the distance which it may travel.

Description of the algorithm. Due to the limitations of the microchip PIC16F18326 used for the radio-buoy system, the FEC codes which are going to be studied and designed are very similar to the Hamming codes. As the microchip uses eight bit bytes, the three cases that will be studied will use all the bits available for each of the bytes transmitted. There are two kinds of bits: the ones that compose the message which has to be transmitted and the ones known as parity bits [1], which have the purpose of helping the receiver to recover the information in a reliable way. The code rate, R, is based on the number of bits that has the message, k, and the total number of bits per byte, n. Thus: R = k/n Currently, this value is 20%, this means that 80% of the transmission is destined exclusively to recovering the message. In order to increase this value, the project will be focused on the study of three different error correction cases. First, case (2, 8), it uses two bits per byte as the message R = 25%, second, case(3, 8), uses three bits per byte as the message R=37.5%, and, finally, case (4, 8), which uses four bits per byte as the message R=50%. To carry out the encoding in every case, a set of bytes, known as codewords, was selected with the criterion of maximizing the minimum Hamming distance between them. The Hamming distance \cite{hamming50} is the number of bits that differ from one byte to another. This sets will be assigned to each of the possible message that can be sent, that is to say, in case (2, 8) there will be four possible messages to transmit, in case (3, 8) there will be eight and in case (4, 8) there will be sixteen. In the transmitter each byte of the string will be divided depending on the case used and each of the resultant parts will be assigned to its corresponding codeword before transmitting the information. At the receiver, the algorithm will use the so-called parity matrix H which has the primary mission of detecting and finding errors that may appear during the transmission process. This process will happen by multiplying the parity matrix and the codeword received. If the result of the operation is zero there would be no error, but if one or more errors happened, the resulting parity value would uniquely identify which bits are in error up to the number of bits that each algorithm can correct. Flipping precisely those identified bits would recover the correct information.

Simulation and results. To ensure that the simulation and comparison between the current algorithm and the ones developed in this project is carried out with reliability, a Python simulation environment has been developed in order to represent with fidelity the transmission and reception of the information sent by the buoy. This environment has three main functions, one that simulates the transmission, one that simulates how the receiver works and another one that randomly models and includes error bits in the information using different BERs (Bit Error Rate). The results obtained showed a significant improvement of the performance in comparison with the simulations of the previous algorithm. Also the implementation met with the specifications of time needed to be able to use this algorithm in a real-life environment using the actual microcontrollers used in the hardware.

Conclusions After all the study carried out, the conclusion is that the algorithm is ready to be used in sea trials to ensure its performance in a real-life situation. As future work, there is room for the implementation and study of more sophisticated techniques in case that another microprocessor with capacity for achieving more complex operations will be used.

References.

[1] Mary K. Wootters, Any errors in this dissertation are probably fixable: topics in probability and error correcting codes. PhD Thesis, Department of Mathematics, University of Michigan 2014.

[2] Richard W. Hamming, Error Detecting and Error Correcting Codes. The Bell System Technical Journal, Vol. 29, April 1950.