PROCEDIMIENTO Y DISPOSITIVO DE COMUNICACIÓN DE DATOS A TRAVÉS DE MEDIOS RUIDOSOS.

Procedimiento y dispositivo de comunicación de datos a través de medios ruidosos.

Que se aplica para mejorar la protección frente a errores en la transmisión de información a través de un canal medio de transmisión ruidoso. El procedimiento y dispositivo asociado consiste en la utilización de un nuevo tipo de estructura de la matriz de paridad para la tecnología de códigos de paridad de baja densidad (Low Density Parity Check Codes) en la codificación y decodificación de datos, que mejora las prestaciones de corrección de errores sin aumentar la complejidad de la implementación hardware.

Procedimiento y dispositivo de comunicación de datos a través de medios ruidosos.

Objeto de la invención La presente invención, tal y como se expresa en el enunciado de esta memoria descriptiva se refiere a un procedimiento y dispositivo para la comunicación de datos a través de medios ruidosos, esto es, para la transmisión y recepción de datos a través de medios de comunicación o canales que pueden introducir errores en la comunicación.

La ventaja principal de este procedimiento y dispositivo de la invención es que se incrementa la robustez de la corrección de errores de las transmisiones sin con ello aumentar la complejidad del hardware en la implementación del dispositivo de protección frente a errores.

Antecedentes de la invención En entornos de comunicación es usual que el medio de transmisión o señales externas introduzcan errores en la señal. Dichos errores deben ser detectados y, si es posible, corregidos en recepción para recuperar la información correcta. Existen múltiples formas de incluir detección y corrección de errores en el estado del arte, siendo una de ellas la codificación y decodificación de la información basada en códigos de paridad de baja densidad (Low-Density Parity-Check codes) para la corrección de errores.

Los códigos de paridad de baja densidad (denominados LDPC o low-density parity-check code) son códigos de corrección de errores que se utilizan en la transmisión de mensajes sobre canales de transmisión ruidosos. Estos códigos introducen cierta redundancia en el mensaje (se envía un número de bits mayor que el del mensaje original) , pero de tal forma que en recepción es posible detectar si hay errores en el mensaje recibido y corregirlos.

Un código LDPC es un código cuya matriz de paridad es poco densa, es decir la gran mayoría de los elementos de la misma son ceros. Este tipo de códigos fueron publicados por primera vez a principios de la década de los sesenta, por Robert G. Gallager "Low Density Parity Check Codes", M.I.T. Press, 1963, y demostraron tener prestaciones muy cerca del conocido límite de Shannon (máximo teórico de la tasa de transmisión de datos) . Sin embargo, con la definición original de los códigos y la tecnología de la época no era posible una implementación asequible con una complejidad adecuada. Recientemente, gracias a la evolución de los circuitos integrados y a la invención de matrices estructuradas, estos códigos han vuelto a ser de gran interés.

En el estado del arte existen múltiples métodos para realizar la codificación y decodificación frente a errores. Algunos métodos son los publicados en la patentes US 7, 343, 548B2 y US 7, 203, 897B2, ambas de título "Method and apparatus for encoding and decoding data" que presenta sendos métodos para mejorar la protección frente a errores en la transmisión de datos. También se puede relacionar la invención con los estándares IEEE802.16e y 802.11n, que presentan codificación y decodificación para reducción de errores. En cualquier caso, las patentes y estándares mencionados utilizan la estructura de doble diagonal, que es conocida en el estado del arte, mientas que la estructura presentada en este documento resulta novedosa y permite una implementación con mejores prestaciones sin aumentar el nivel de complejidad (y por tanto con menor coste) de la protección frente a errores en la comunicación de información a través de medios ruidosos. Es conocido en el estado del arte que tener columnas con peso Hamming igual o menor que 2 en la matriz de paridad restringe las prestaciones de los códigos LDPC. Sin embargo, por causas de complejidad de implementación del codificador, matrices con una sección Hb1 de doble diagonal han sido usadas en el estado del arte. La nueva estructura presentada en este documento, al añadir una tercera diagonal a la sección Hb1 de la matriz modelo binaria H0, permite que el número total de columnas de la matriz de paridad con peso Hamming menor, o igual a 2 sea menor y por lo tanto se pueden alcanzar mejores prestaciones. Esta tercera diagonal, ha sido seleccionada de tal forma que el aumento de la complejidad de implementación del codificador es prácticamente despreciable.

Los documentos anteriormente presentados no interfieren con la novedad ni altura inventiva de la presente invención. Aunque todos se basan en la utilización de la tecnología LDPC (Low-Density Parity-Check code, esto es, códigos de paridad de baja densidad) que son conocidos en el estado del arte, el procedimiento y dispositivo de la invención en este documento utiliza un tipo de código quasi-cíclico (Quasi-Cyclic Low Density Parity Check Code, o QC-LDPC) , y aplica una matriz de paridad con estructura diferente como punto central de la invención.

A lo largo de este documento se utiliza una nomenclatura específica para diferenciar los elementos utilizados a lo largo de la descripción de la invención. Una letra mayúscula y en negrita (por ejemplo, A) indica que el elemento es una matriz; una letra minúscula y negrita (por ejemplo, a) indica que el elemento es un vector, mientras que una letra minúscula y sin negrita (ejemplo a) indica que el elemento es un valor escalar. Por otra parte, los elementos escalares que componen una matriz de dimensiones M × N se indican de la forma a (i, j) , donde la tupla (i, j) es la posición de dicho elemento dentro de la matriz siendo 0≤i≤M-1 el número de fila y 0≤j≤N-1 el número de columna. Los elementos que componen un vector de dimensión M se anotan de la forma a (i) , siendo (i) la posición del elemento en el vector (0≤i≤M-1) .

Además, a lo largo de la invención se utiliza el término rotación cíclica, que se define a continuación. Una rotación cíclica z sobre un vector a =[a (0) , a (1) , ..., a (M-2) , a (M-1) ] consiste en rotar cíclicamente sus elementos hacia la derecha obteniendo el vector [a ( (M-z) %M) , ..., a ( (M-z-1) %M) ] como resultado, siendo % el operador "módulo". De la misma forma, una rotación cíclica z aplicada sobre una matriz A =[a (0) , ..., a (N-1) ] opera sobre sus columnas obteniendo la matriz [a ( (N-z) %N) , ..., a ( (N-z-1) %N) ] como resultado. La rotación cíclica también puede definirse en el sentido contrario (hacia la izquierda) de forma que una rotación cíclica z hacia la derecha es equivalente a una rotación cíclica M-z y N-z respectivamente para vector y matriz hacia la izquierda.

Descripción de la invención Para lograr los objetivos y evitar los inconvenientes indicados en anteriores apartados, la invención consiste en un procedimiento y dispositivo para la comunicación de datos a través de medios ruidosos. Concretamente, la invención presenta un procedimiento de codificación de datos utilizado en transmisión, su dispositivo de codificación asociado, un procedimiento de decodificación, y su dispositivo de decodificación asociado. Este grupo de invenciones forman un único concepto inventivo, que se describe a continuación. Si el procedimiento o dispositivo se utiliza en transmisión, el equivalente también deberá utilizarse en recepción, y viceversa, para poder recuperar la información enviada.

El procedimiento de codificación de datos se aplica en transmisión y genera bits de paridad sobre un bloque de información de forma que de una palabra de K bits se genera una palabra código de N bits (N>K) que incluye la protección frente a errores. Dicho procedimiento comprende múltiples pasos. Primero se selecciona un factor b que es un número natural entre 1 y K de forma que la división deNyK entre el factor b sean números naturales (n=N/b; k=K/b) . A continuación se define una matriz modelo binaria H0=[Ha|Hb] de tamaño (n-k) x n como la combinación de una submatriz correspondiente a las posiciones de los bits de información Ha y de una submatriz correspondiente a los bits de paridad Hb, donde dicha segunda submatriz Hb=[hb0|Hb1] se compone de un vector columna de n-k posiciones hb0 y una matriz Hb1 con estructura triple diagonal, esto es, donde los elementos de las dos diagonales centrales hb1 (i, i) , hb1 (i+1, i) , 0≤i≤n-k-2 y de la diagonal de la última fila hb1 (n-k-1, 0) son iguales a 1, siendo n-k el número de filas y columnas de la matriz Hb, y el resto de elementos son iguales a cero. Después, se genera la matriz compacta H1ya partir de ella la matriz de paridad H. A partir de ahí se toma un bloque de información y se utiliza la matriz de paridad H sobre el bloque de información para determinar los bits de paridad correspondientes a dicho bloque. Finalmente se transmiten los bits de paridad junto con el bloque de información.

1. Procedimiento de comunicación de datos a través de medios ruidosos, que se aplica en la codificación de datos en transmisión y que genera bits de paridad sobre un bloque de información de forma que de una palabra de K bits se genera una palabra código de N bits; caracterizado porque comprende los pasos de:

- seleccionar un factor b que consiste en un número natural 1≤b≤K de forma que N/b=n y K/b=k sean números naturales;

- generar una matriz modelo binaria H0-[Ha|Hb] de tamaño (n-k) x n como la combinación de una submatriz correspondiente a las posiciones de los bits de información Ha y de una submatriz correspondiente a los bits de paridad Hb, donde dicha segunda submatriz Hb=[hb0|Hb1] se compone de un vector columna de n-k posiciones hb0 y una estructura Hb1 triple diagonal, en donde los elementos de las dos diagonales centrales hb1 (i, i) , hb1 (i+1, i) , 0≤i≤n-k-2 y de la diagonal de la última fila hb1 (n-k-1, 0) son iguales a 1, siendo n-k el número de filas y columnas de la matriz Hb, y el resto de elementos son iguales a cero;

- generar una matriz compacta H1 a partir de la matriz modelo binaria H0.

- generar la matriz de paridad H a partir de la matriz compacta H1;

- seleccionar un bloque de información;

- aplicar la matriz de paridad H sobre el bloque de información para determinar los bits de paridad correspondientes a dicho bloque; y

- transmitir los bits de paridad junto con el bloque de información.

2. Procedimiento de comunicación de datos a través de medios ruidosos, según reivindicación 1, caracterizado porque comprende se eliminar uno o más elementos de la palabra código antes de ser transmitidos, mediante la aplicación de una técnica de pinchado convencional, para que la palabra transmitida tenga un número de bits menor que la palabra código obtenida.

3. Dispositivo de comunicación de datos a través de medios ruidosos, que se aplica en la codificación de datos en transmisión, caracterizado porque el codificador comprende:

- medios para almacenar una matriz compacta H1 derivada de una matriz modelo binaria H0=[Ha|Hb] formada como la combinación de una submatriz correspondiente a las posiciones de los bits de información Ha y de una submatriz correspondiente a los bits de paridad Hb, donde dicha segunda submatriz Hb= [hb0|Hbi] se compone de un vector columna de n-k posiciones hb0 y una estructura Hb1 triple diagonal, en donde los elementos de las dos diagonales centrales hb1 (i, i) , hb1 (i+1, i) , 0≤i≤n-k-2 y de la diagonal de la última fila hb1 (n-k-1, 0) son iguales a 1, siendo n-k el número de filas y columnas de la matriz Hb, y el resto de elementos son iguales a cero;

- un microprocesador que comprende medios para seleccionar un bloque de información, aplicar la matriz compacta para generar la matriz de paridad H, aplicar la matriz de paridad H al bloque de información para obtener los bits de paridad correspondientes a dicho bloque y añadir los bits de paridad al bloque de información antes de ser transmitidos.

4. Dispositivo de comunicación de datos a través de medios ruidosos, según reivindicación 3, caracterizado porque el microprocesador comprende medios para tras añadir los bits de paridad al bloque de información se eliminar uno o más elementos de la palabra código antes de ser transmitidos, mediante la aplicación de una técnica de pinchado convencional, para que la palabra transmitida tenga un número de bits menor que la palabra código obtenida.

5. Procedimiento de comunicación de datos a través de medios ruidosos, que se aplica en la decodificación de datos en recepción y que estima el bloque de información a partir de un vector de señal recibida, de forma que de una palabra código recibida de N bits se obtiene una palabra de K bits; caracterizado porque comprende los pasos de:

- seleccionar un vector de señal del canal;

- calcular una matriz modelo binaria H0=[H|Hb] como la combinación de una submatriz correspondiente a las posiciones de los bits de información Ha y de una submatriz correspondiente a los bits de paridad Hb, donde dicha segunda submatriz Hb =[hb0|Hb1] se compone de un vector columna de n-k posiciones hb0 y una estructura Hb1 triple diagonal, en donde los elementos de las dos diagonales centrales hb1 (i, i) , hb1 (i+1, i) , 0≤i≤n-k-2 y de la diagonal de la última fila hb1 (n-k-1, 0) son iguales a 1, siendo n-k el número de filas y columnas de la matriz Hb, y el resto de elementos son iguales a cero;

- generar una matriz compacta H1 a partir de la matriz modelo binaria H0.

- generar la matriz de paridad H a partir de la matriz compacta H1;y

- estimar el bloque de información a partir del vector de señal recibido y de la matriz de paridad H.

6. Procedimiento de comunicación de datos a través de medios ruidosos, según reivindicación 5, caracterizado porque comprende insertar un valor indicador de posiciones eliminadas en trasmisión por una técnica de pinchado convencional, antes de realizar la estimación del bloque de información a partir del vector de señal recibido y de la matriz de paridad.

7. Dispositivo de comunicación de datos a través de medios ruidosos, que se aplica en la decodificación de datos en recepción; caracterizado porque el decodificador comprende:

- medios para almacenar una matriz compacta H1 derivada de una matriz modelo binaria H0=[Ha|Hb] formada como la combinación de una submatriz correspondiente a las posiciones de los bits de información Ha y de una submatriz correspondiente a los bits de paridad Hb, donde dicha segunda submatriz Hb= [hb0|Hb1] se compone de un vector columna de n-k posiciones hb0 y una estructura Hb1 triple diagonal, en donde los elementos de las dos diagonales centrales hb1 (i, i) , hb1 (i+1, i) , 0≤i≤n-k-2 y de la diagonal de la última fila hb1 (n-k-1, 0) son iguales a 1, siendo n-k el número de filas y columnas de la matriz Hb, y el resto de elementos son iguales a cero;

- un microprocesador que comprende medios para generar la matriz de paridad H a partir de la matriz compacta H1, aplicar dicha matriz de paridad H sobre el vector de señal recibido, y estimar el bloque de información recibido.

8. Dispositivo de comunicación de datos a través de medios ruidosos, según reivindicación 7, caracterizado porque el microprocesador comprende medios para antes de aplicar la matriz de paridad H sobre el vector de señal recibida insertar un valor indicador en las posiciones eliminadas por la técnica de pinchado en transmisión.

9. Procedimiento de comunicación de datos a través de medios ruidosos, según las reivindicaciones1º5, caracterizado porque se utiliza la siguiente matriz compacta H1 para obtener palabras código de 33 6 bits con una tasa de codificación de 1/2:

10. Procedimiento de comunicación de datos a través de medios ruidosos, según las reivindicaciones 1 o 5, caracterizado porque se utiliza la siguiente matriz compacta H1 para obtener palabras código 1920 bits con una tasa de codificación de 1/2:

11. Procedimiento de comunicación de datos a través de medios ruidosos, según las reivindicaciones 1 o 5, caracterizado porque se utiliza la siguiente matriz compacta H1 para obtener palabras código de 864 0 bits con una tasa de codificación de 1/2:

12. Procedimiento de comunicación de datos a través de medios ruidosos, según las reivindicaciones 1 o 5, caracterizado porque se utiliza la siguiente matriz compacta H1 para obtener palabras código de 1440 bits con una tasa de codificación de 2/3

13. Procedimiento de comunicación de datos a través de medios ruidosos, según las reivindicaciones 1 o 5, caracterizado porque se utiliza la siguiente matriz compacta H1 para obtener palabras código de 6480 bits con una tasa de codificación de 2/3:

14. Procedimiento de comunicación de datos a través de medios ruidosos, según las reivindicaciones 1 o 5, caracterizado porque se utiliza la siguiente matriz compacta H1 para obtener palabras código de 1152 bits con una tasa de codificación de 5/6:

15. Procedimiento de comunicación de datos a través de medios ruidosos, según las reivindicaciones 1 o 5, caracterizado porque se utiliza la siguiente matriz compacta H1 para obtener palabras código de 5184 bits con una tasa de codificación de 5/6:

16. Procedimiento de comunicación de datos a través de medios ruidosos, según la reivindicación 2, caracterizado porque partiendo de una palabra código con 1152 bits y tasa de codificación de 5/6 se utiliza el siguiente patrón de pinchado

para obtener una palabra código de 1080 bits y tasa de codificación de 16/18.

17. Procedimiento de comunicación de datos a través de medios ruidosos, según la reivindicación 2, caracterizado porque partiendo de una palabra código con 5184 bits y tasa de codificación de 5/6 se utiliza el siguiente patrón de pinchado para obtener una palabra código de 4860 bits y tasa de codificación de 16/18.

18. Procedimiento de comunicación de datos a través de medios ruidosos, según la reivindicación 2, caracterizado porque partiendo de una palabra código con 1152 bits y tasa de codificación de 5/6 se utiliza el siguiente patrón de pinchado

para obtener una palabra código de 1008 bits y tasa de codificación de 20/21.

19. Procedimiento de comunicación de datos a través de medios ruidosos, según la reivindicación 2, caracterizado porque partiendo de una palabra código con 5184 bits y tasa de codificación 5/6 se utiliza el siguiente patrón de pinchado

para obtener una palabra código de 4536 bits y tasa de codificación de 20/21.

20. Dispositivo de comunicación de datos a través de medios ruidosos, según las reivindicaciones3º7, caracterizado porque se utiliza la siguiente matriz compacta H1 para obtener palabras código de 336 bits con una tasa de codificación de 1/2:

21. Dispositivo de comunicación de datos a través de medios ruidosos, según las reivindicaciones3º7, caracterizado porque se utiliza la siguiente matriz compacta H1 para obtener palabras código 1920 bits con una tasa de codificación de 1/2:

22. Dispositivo de comunicación de datos a través de medios ruidosos, según las reivindicaciones 3 o 7, caracterizado porque se utiliza la siguiente matriz compacta H1 para obtener palabras código de 8640 bits con una tasa de codificación de 1/2:

23. Dispositivo de comunicación de datos a través de medios ruidosos, según las reivindicaciones 3 o 7, caracterizado porque se utiliza la siguiente matriz compacta H1 para obtener palabras código de 1440 bits con una tasa de codificación de 2/3:

24. Dispositivo de comunicación de datos a través de medios ruidosos, según las reivindicaciones 3 o 7, caracterizado porque se utiliza la siguiente matriz compacta H1 para obtener palabras código de 6480 bits con una tasa de codificación de 2/3:

25. Dispositivo de comunicación de datos a través de medios ruidosos, según las reivindicaciones 3 o 7, caracterizado porque se utiliza la siguiente matriz compacta H1 para obtener palabras código de 1152 bits con una tasa de codificación de 5/6:

26. Dispositivo de comunicación de datos a través de medios ruidosos, según las reivindicaciones 3 o 7, caracterizado porque se utiliza la siguiente matriz compacta H, para obtener palabras código de 5184 bits con una tasa de codificación de 5/6:

27. Dispositivo de comunicación de datos a través de medios ruidosos, según la reivindicación 4, caracterizado porque partiendo de una palabra código con 1152 bits y tasa de codificación de 5/6 se utiliza el siguiente patrón de pinchado

para obtener una palabra código de 1080 bits y tasa de codificación de 16/18.

28. Dispositivo de comunicación de datos a través de medios ruidosos, según la reivindicación 4, caracterizado porque partiendo de una palabra código con 5184 bits y tasa de codificación de 5/6 se utiliza el siguiente patrón de pinchado para obtener una palabra código de 4860 bits y tasa de codificación de 16/18.

29. Dispositivo de comunicación de datos a través de medios ruidosos, según la reivindicación 4, caracterizado porque partiendo de una palabra código con 1152 bits y tasa de codificación de 5/6 se utiliza el siguiente patrón de pinchado para obtener una palabra código de 1008 bits y tasa de codificación de 20/21.

30. Dispositivo de comunicación de datos a través de medios ruidosos, según la reivindicación 4, caracterizado porque partiendo de una palabra código con 5184 bits y tasa de codificación 5/6 se utiliza el siguiente patrón de pinchado para obtener una palabra código de 4536 bits y tasa de codificación de 20/21.