ES2673513T3

ES2673513T3 - Procedimientos que emplean códigos de FEC con inactivación permanente de símbolos para procesos de codificación y decodificación

Info

Publication number: ES2673513T3
Application number: ES10749950.1T
Authority: ES
Inventors: Michael G. Luby; Mohammad Amin SHOKROLLAHI; Lorenz Christoph Minder
Original assignee: Qualcomm Inc
Current assignee: Qualcomm Inc
Priority date: 2009-08-19
Filing date: 2010-08-19
Publication date: 2018-06-22
Anticipated expiration: 2030-08-19
Also published as: US9419749B2; BR112012003688B1; KR20120058556A; TWI437422B; WO2011022555A3; JP5819495B2; CA2982574A1; TW201430555A; RU2012110248A; CA2771622C; US9660763B2; RU2013139729A; CN102640422A; CA2982574C; KR20130111650A; RU2554556C2; EP2467942B1; KR101421286B1; ZA201201843B; CA2771622A1

Abstract

Un procedimiento de transmisión electrónica de datos a través de uno o más transmisores capaces de emitir una señal electrónica, en donde los datos a transmitir están representados por un conjunto ordenado de símbolos de origen y los datos son transmitidos como una secuencia de símbolos codificados que representan al menos una parte de la señal electrónica, comprendiendo el procedimiento: obtener, en una forma legible electrónicamente, el conjunto ordenado de símbolos de origen; generar un conjunto de símbolos intermedios a partir del conjunto ordenado de símbolos de origen, en 10 donde los símbolos de origen pueden regenerarse a partir del conjunto de símbolos intermedios; designar conjuntos de los símbolos intermedios, antes de la transmisión, de modo que cada símbolo intermedio sea designado como un miembro de uno de los conjuntos de símbolos intermedios y que haya al menos un primer conjunto de símbolos intermedios y un segundo conjunto de símbolos intermedios, y en donde cada conjunto de símbolos intermedios tenga como miembros al menos un símbolo intermedio, en donde el primer conjunto de símbolos intermedios sea designado como no permanentemente inactivado, LT, para la decodificación de propagación de creencias, y el segundo conjunto de símbolos intermedios sea designado como símbolos para ser permanentemente inactivados para la decodificación de propagación de creencias, en donde los símbolos permanentemente inactivados, PI, son símbolos a 20 despejar por separado de la decodificación de propagación de creencias; y generar una pluralidad de símbolos codificados, en donde un símbolo codificado se genera a partir de uno o más de los símbolos intermedios, en donde al menos un símbolo codificado se genera, directa o indirectamente, a partir de una pluralidad de símbolos intermedios seleccionados entre una pluralidad de los conjuntos de símbolos intermedios; en donde generar la pluralidad de símbolos codificados comprende la codificación dinámica de los símbolos intermedios PI con un codificador PI, la codificación dinámica de los símbolos intermedios LT con un codificador LT y la combinación de los símbolos intermedios PI y LT codificados en un combinador para generar dicha pluralidad de símbolos codificados.

Description

5

10

15

20

25

30

35

40

45

50

55

60

65

DESCRIPCION

Procedimientos que emplean códigos de FEC con inactivación permanente de símbolos para procesos de codificación y decodificación

REFERENCIAS CRUZADAS

[1] Esta solicitud es una continuación en parte de la Solicitud de Patente Estadounidense N° 12 / 604.773, presentada el 23 de octubre de 2009, que nombra a M. Amin Shokrollahi, et al., y titulada "Method and Apparatus Employing FEC Codes with Permanent Inactivation of Symbols for Encoding and Decoding Processes" ["Procedimiento y aparato que emplea códigos de FEC con inactivación permanente de símbolos para procesos de codificación y decodificación"] y además reivindica prioridad sobre las siguientes solicitudes provisionales, cada una de las cuales nombra a M. Amin Shokrollahi, et al., y cada una titulada "Method and Apparatus Employing FEC Codes with Permanent Inactivation of Symbols for Encoding and Decoding Processes" ["Procedimiento y aparato que emplea códigos de FEC con inactivación permanente de símbolos para procesos de codificación y decodificación"]: la Solicitud de Patente Provisoria Estadounidense N° 61 / 353.910, presentada el 11 de junio de 2010, la Solicitud de Patente Provisoria Estadounidense N° 61 / 257.146, presentada el 2 de noviembre de 2009, y la Solicitud de Patente Provisoria Estadounidense N° 61 / 235.285, presentada el 19 de agosto de 2009.

[2] Se hacen en este documento las siguientes referencias:

1) Patente Estadounidense N° 6.307.487 concedida a Michael G. Luby, titulada "Information Additive Code Generator and Decoder for Communication Systems" ["Generador y decodificador de código por adición de información para sistemas de comunicación"] (en lo sucesivo, "Luby I");

2) Patente Estadounidense N° 6.320.520 concedida a Michael G. Luby, titulada "Information Additive Group Code Generator and Decoder for Communication Systems" ["Generador y decodificador de código grupal por adición de información para sistemas de comunicación"] (en lo sucesivo, "Luby II");

3) Patente Estadounidense N° 7.068.729 concedida a M. Amin Shokrollahi, titulada "Multi-Stage Code Generator and Decoder for Communication Systems" ["Generador y decodificador de código en múltiples etapas para sistemas de comunicación"] (en lo sucesivo, "Shokrollahi I");

4) Patente Estadounidense N° 6.856.263 concedida a M. Amin Shokrollahi, titulada "Systems and Processes for Decoding a Chain Reaction Code Through Inactivation" ["Sistemas y procesos para decodificar un código por reacción en cadena mediante la inactivación"] (en lo sucesivo, "Shokrollahi II");

5) Patente Estadounidense N° 6.909.383, concedida a M. Amin Shokrollahi, titulada "Systematic Encoding and Decoding of Chain Reaction Codes" ["Codificación y decodificación sistemáticas de códigos por reacción en cadena"] (en lo sucesivo, "Shokrollahi III");

6) Publicación de Patente Estadounidense N° 2006/0280254 que nombra a Michael G. Luby ya M. Amin Shokrollahi, y titulada "In-Place Transformations with Applications to Encoding and Decoding Various Classes of Codes" ["Transformaciones in situ con aplicaciones para codificar y decodificar diversas clases de códigos"] (en lo sucesivo, "Luby III");

7) Publicación de Patente Estadounidense N° 2007/0195894 que nombra a M. Amin Shokrollahi, y titulada "Multiple-Field Based Code Generator and Decoder for Communications Systems" ["Generador y decodificador de código basado en campos múltiples para sistemas de comunicaciones"] (en lo sucesivo, "Shokrollahi IV").

CAMPO DE LA INVENCIÓN

[3] La presente invención se refiere a la codificación y decodificación de datos en sistemas de comunicaciones y, más específicamente, a sistemas de comunicación que codifican y decodifican datos para dar cuenta de errores y brechas en datos comunicados de una manera eficaz.

ANTECEDENTES DE LA INVENCIÓN

[4] Las técnicas para la transmisión de ficheros entre un emisor y un destinatario por un canal de comunicaciones son el tema de mucha bibliografía. Preferiblemente, un destinatario desea recibir una copia exacta de datos transmitidos por un canal por un emisor con cierto nivel de certeza. Cuando el canal no tiene fidelidad perfecta (lo que abarca la mayoría de los sistemas físicamente realizables), una preocupación es cómo tratar los datos perdidos o distorsionados en la transmisión. Los datos perdidos (borrados) a menudo son más fáciles de tratar que los datos corrompidos (errores) porque el destinatario no siempre puede decir cuándo los datos corrompidos son datos recibidos con errores. Se han desarrollado muchos códigos de corrección de errores para corregir borrados y / o errores. Normalmente, el código particular utilizado se elige en función de cierta información sobre las

5

10

15

20

25

30

35

40

45

50

55

60

65

infidelidades del canal por el cual se transmiten los datos y la naturaleza de los datos que se transmiten. Por ejemplo, cuando se sabe que el canal tiene largos períodos de infidelidad, un código de error de ráfaga podría ser el más adecuado para esa aplicación. Donde solo se esperan errores cortos e infrecuentes, un código de paridad simple podría ser el mejor.

[5] Tal como se usa en el presente documento, "datos de origen" se refiere a datos que están disponibles en uno o más remitentes y para obtener los cuales, por recuperación de una secuencia transmitida con o sin errores y / o borraduras, etc., se utiliza un receptor. Tal como se usa en el presente documento, "datos codificados" se refiere a los datos que se transmiten y se pueden utilizar para recuperar u obtener los datos de origen. En un caso sencillo, los datos codificados son una copia de los datos de origen, pero si los datos codificados recibidos difieren (debido a errores y / o borrados) de los datos codificados transmitidos, en este caso sencillo los datos de origen podrían no ser completamente recuperables, en ausencia de datos adicionales sobre los datos de origen. La transmisión puede ser a través del espacio o del tiempo. En un caso más complejo, los datos codificados se generan basándose en datos de origen en una transformación y se transmiten desde uno o más remitentes a los receptores. Se dice que la codificación es "sistemática" si se encuentra que los datos de origen son parte de los datos codificados. En un ejemplo sencillo de codificación sistemática, se agrega información redundante sobre los datos de origen al final de los datos de origen para formar los datos codificados.

[6] También como se usa en el presente documento, los "datos de entrada" se refieren a datos que están presentes en una entrada de un aparato codificador de FEC (corrección anticipada de errores) o un módulo, componente, etapa, etc., del codificador de FEC ("codificador de FEC") y los "datos de salida" se refieren a datos que están presentes en una salida de un codificador de FEC. En consecuencia, se esperaría que los datos de salida estuvieran presentes en una entrada de un decodificador de FEC y se esperaría que el decodificador de FEC emitiera los datos de entrada, o una correspondencia de los mismos, basándose en los datos de salida por él procesados. En algunos casos, los datos de entrada son, o incluyen, los datos de origen y, en algunos casos, los datos de salida son, o incluyen, los datos codificados. En otros casos, un dispositivo emisor o un código de programa emisor puede comprender más de un codificador de FEC, es decir, los datos de origen se transforman en datos codificados en una serie de una pluralidad de codificadores de FEC. De forma similar, en el receptor, puede haber más de un decodificador de FEC aplicado para generar datos de origen a partir de datos codificados recibidos.

[7] Se puede pensar que los datos están divididos en símbolos. Un codificador es un sistema informático, dispositivo, circuito electrónico o similar, que genera símbolos codificados o símbolos de salida a partir de una secuencia de símbolos de origen o símbolos de entrada y un decodificador es la contraparte que recupera una secuencia de símbolos de origen o símbolos de entrada recibidos, o símbolos codificados recuperados o símbolos de salida. El codificador y el decodificador están separados en tiempo y / o espacio por el canal y símbolos codificados recibidos podrían no ser exactamente iguales a los correspondientes símbolos codificados transmitidos, y podrían no ser recibidos exactamente en la misma secuencia en que se transmitieron. El "tamaño" de un símbolo se puede medir en bits, independientemente de que el símbolo se descomponga o no efectivamente en un flujo de bits, donde un símbolo tiene un tamaño de M bits cuando el símbolo se selecciona de un alfabeto de 2M símbolos. En muchos de los ejemplos en este documento, los símbolos se miden en octetos y los códigos podrían estar en un campo de 256 posibilidades (hay 256 patrones posibles de 8 bits), pero debería entenderse que se pueden usar diferentes unidades de medida de datos, y es bien conocido medir datos de varias maneras.

[8] El documento Luby I describe el uso de códigos, tales como códigos de reacción en cadena, para abordar la corrección de errores de una manera eficaz en términos informáticos, eficaz en términos de memoria y eficaz en términos de ancho de banda. Una propiedad de los símbolos codificados producidos por un codificador de reacción en cadena es que un receptor puede recuperar el fichero original tan pronto como se hayan recibido suficientes símbolos codificados. Específicamente, para recuperar los K símbolos originales de origen con una alta probabilidad, el receptor necesita aproximadamente K + A símbolos codificados.

[9] La "sobrecarga de recepción absoluta" para una situación dada está representada por el valor A, mientras que una "sobrecarga de recepción relativa" puede calcularse como la razón A / K. La sobrecarga de recepción absoluta es una medida de la cantidad de datos adicionales que se necesita recibir, más allá de la cantidad mínima de datos de la teoría de la información, y puede depender de la fiabilidad del decodificador y puede variar en función del número, K, de los símbolos de origen. Del mismo modo, la sobrecarga de recepción relativa, A / K, es una medida de la cantidad de datos adicionales que se necesita recibir, más allá de la cantidad mínima de datos de la teoría de la información, relativa al tamaño de los datos de origen que se recuperan, y también puede depender de la fiabilidad del decodificador y puede variar en función del número K de símbolos de origen.

[10] Los códigos de reacción en cadena son extremadamente útiles para la comunicación a través de una red basada en paquetes. Sin embargo, a veces pueden ser bastante intensivos en términos de cálculo. Un decodificador podría ser capaz de decodificar más a menudo, o más fácilmente, si los símbolos de origen están codificados usando un codificador estático antes de un codificador dinámico que codifica usando una reacción en cadena u otro código sin tasa. Tales decodificadores se muestran en el documento Shokrollahi I, por ejemplo. En los ejemplos que se muestran allí, los símbolos de origen son símbolos de entrada a un codificador estático que produce símbolos de salida, que son símbolos de entrada a un codificador dinámico que produce símbolos de salida que son los símbolos

5

10

15

20

25

30

35

40

45

50

55

60

65

codificados, en donde el codificador dinámico es un codificador sin tasa que puede generar un cierto número de símbolos de salida, en una cantidad que no es una tasa fija en relación con el número de símbolos de entrada. El codificador estático podría incluir más de un codificador de tasa fija. Por ejemplo, un codificador estático podría incluir un codificador de Hamming, un codificador de comprobación de paridad de baja densidad ("LDPC"), un codificador de comprobación de paridad de alta densidad ("HDPC") y / o similares.

[11] Los códigos de reacción en cadena tienen la propiedad de que, según algunos símbolos se recuperan en el decodificador a partir de los símbolos recibidos, esos símbolos podrían usarse para recuperar símbolos adicionales, que a su vez podrían usarse para recuperar aún más símbolos. Preferiblemente, la reacción en cadena de la resolución de símbolos en el decodificador puede continuar de manera que todos los símbolos deseados se recuperen antes de que se consuma el fondo común de símbolos recibidos. Preferiblemente, la complejidad de cálculo de la realización de procesos de codificación y decodificación de reacción en cadena es baja.

[12] Un proceso de recuperación en el decodificador podría implicar determinar qué símbolos se recibieron, crear una matriz que correlacionaría los símbolos de entrada originales con aquellos símbolos codificados que se recibieron, luego invertir la matriz y realizar una multiplicación matricial de la matriz invertida y un vector de los símbolos codificados recibidos. En un sistema típico, una implementación de fuerza bruta de esto puede consumir excesivos requisitos de esfuerzo de cálculo y de memoria. Por supuesto, para un conjunto particular de símbolos codificados recibidos, podría ser imposible recuperar todos los símbolos de entrada originales, pero incluso cuando sea posible, puede ser muy costoso informáticamente calcular el resultado.

[13] El documento Shokrollahi II describe un enfoque llamado "inactivación", en el que la decodificación se produce en dos etapas. En la primera etapa, el decodificador hace un inventario de los símbolos codificados recibidos que tiene disponibles y de cómo se vería la matriz y determina, al menos aproximadamente, una secuencia de etapas de decodificación que permitiría completar el proceso de reacción en cadena, dados los símbolos codificados recibidos. En la segunda etapa, el decodificador ejecuta la decodificación por reacción en cadena de acuerdo a la secuencia determinada de etapas de decodificación. Esto se puede hacer de una manera eficaz en términos de memoria (es decir, una manera que requiere menos almacenamiento de memoria para el funcionamiento que un proceso más ineficaz en términos de memoria).

[14] En un enfoque de inactivación, la primera etapa de decodificación implica manipular la matriz, o su equivalente, para determinar cierto número de símbolos de entrada que se pueden despejar y, cuando la determinación se estanca, designar uno de los símbolos de entrada como un "símbolo inactivado" y continuar el proceso de determinación suponiendo que el símbolo inactivado está realmente despejado y luego, al final, despejar los símbolos inactivados utilizando la eliminación Gaussiana o algún otro procedimiento para invertir una matriz que es mucho más pequeña que la matriz decodificadora original. Usando esa determinación, la secuencia de reacción en cadena se puede realizar en los símbolos codificados recibidos para llegar a los símbolos de entrada recuperados, que pueden ser todos los símbolos de entrada originales o un conjunto adecuado de los símbolos de entrada originales.

[15] Para algunas aplicaciones que imponen restricciones estrictas al decodificador, tales como cuando el decodificador está en un dispositivo de baja potencia con memoria y potencia de cálculo limitadas, o tales como cuando hay restricciones estrictas en la sobrecarga de recepción absoluta o relativa permisible, los procedimientos mejorados podrían estar indicado en relación con el enfoque de inactivación descrito anteriormente.

[16] Además, podrían ser útiles los procedimientos para dividir un fichero o un gran bloque de datos en el menor número posible de bloques de origen, sujetos a una restricción en el tamaño de sub-símbolo más pequeño, y luego sujetos a esta división en el menor número posible de sub-bloques, sujetos a una restricción en el tamaño máximo de sub-bloque.

BREVE SUMARIO DE LA INVENCIÓN

[17] Según un ejemplo de un codificador de acuerdo a aspectos de la presente invención, un codificador, en, o para, un emisor que transmite un conjunto ordenado de símbolos de origen desde uno o más emisores a uno o más receptores por un canal de comunicaciones, en el que el codificador genera datos a enviar que incluyen una pluralidad de símbolos codificados generados a partir de los símbolos de origen. En una primera etapa, símbolos intermedios se generan a partir de los símbolos de origen usando un procedimiento que es invertible, es decir, también existe un procedimiento inverso para generar los símbolos de origen a partir de los símbolos intermedios. En otra etapa, los símbolos intermedios se dividen en un primer conjunto de símbolos intermedios y un segundo conjunto de símbolos intermedios, donde hay al menos un símbolo intermedio en el primer conjunto de símbolos intermedios y hay al menos un símbolo intermedio en el segundo un conjunto de símbolos intermedios y al menos un símbolo codificado se genera a partir de al menos un símbolo intermedio de cada uno de los dos conjuntos. En algunas variaciones, hay más de dos conjuntos.

[18] En algunos ejemplos, se generan valores para un primer conjunto y un segundo conjunto de símbolos temporales, en donde los valores del primer conjunto de símbolos temporales dependen de los valores del primer

5

10

15

20

25

30

35

40

45

50

55

60

65

conjunto de símbolos intermedios y los valores para el segundo conjunto de símbolos temporales dependen de los valores del segundo conjunto de símbolos intermedios. Los valores para los símbolos codificados se generan a partir del primer conjunto y el segundo conjunto de símbolos temporales.

[19] En algunas variaciones, el número de símbolos codificados que se pueden generar es independiente del número de símbolos de origen.

[20] También se proporcionan realizaciones de decodificador. De acuerdo a un ejemplo de un decodificador de acuerdo a aspectos de la presente invención, un decodificador, en, o para, un receptor, recibe símbolos codificados generados a partir de símbolos intermedios, en donde los símbolos intermedios se generan a partir de símbolos de origen usando un procedimiento que es invertible, es decir, también hay un procedimiento inverso para generar los símbolos de origen a partir de los símbolos intermedios, y en donde al menos uno de los símbolos intermedios se designa como un símbolo permanentemente inactivado y en donde hay al menos otro de los símbolos intermedios que no está entre los símbolos intermedios permanentemente inactivados. El decodificador decodifica, a partir de los símbolos codificados recibidos, un conjunto de símbolos intermedios y el decodificador tiene en cuenta al menos un símbolo permanentemente inactivado, y genera símbolos de origen a partir del conjunto decodificado de símbolos intermedios, usando el procedimiento inverso.

[21] En la decodificación, las etapas de decodificación están planificadas, dejando de lado la planificación de símbolos permanentemente inactivados. Los símbolos permanentemente inactivados se pueden despejar usando procedimientos novedosos o convencionales, y luego se usan para despejar los otros símbolos intermedios. Un enfoque para despejar los símbolos desactivados permanentes (y otras inactivaciones sobre la marcha, si se usan) podría ser mediante la aplicación de la eliminación Gaussiana para despejar los símbolos inactivados. Algunos de los símbolos intermedios restantes se recuperan basándose en los valores de los símbolos inactivados permanentemente recuperados y los símbolos codificados recibidos.

[22] En algunas variaciones del procedimiento de decodificación, los símbolos permanentemente inactivados comprenden el segundo conjunto de símbolos intermedios provenientes de las realizaciones de codificación. En algunas variaciones del procedimiento de decodificación, los símbolos permanentemente inactivados comprenden un subconjunto de los símbolos intermedios en donde el procedimiento de codificación correspondiente no es un código de reacción en cadena de múltiples etapas. Tales procedimientos de codificación podrían incluir uno o más entre un código Tornado, un código de Reed-Solomon, un código de reacción en cadena (ejemplos descritos en el documento Luby I) o similares, para el subconjunto de los símbolos intermedios.

[23] Los símbolos intermedios se usan para la codificación y decodificación, en donde el procedimiento para generar símbolos intermedios a partir de símbolos de origen y el procedimiento inverso correspondiente se indican para un conjunto deseado de características de rendimiento, tales como capacidad de decodificación. En algunas realizaciones, los símbolos intermedios comprenden los símbolos de origen. En algunas realizaciones, los símbolos intermedios comprenden los símbolos de origen, junto con símbolos redundantes que se generan a partir de los símbolos de origen, donde los símbolos redundantes podrían ser símbolos de reacción en cadena, símbolos de LDPC, símbolos de HDPC u otros tipos de símbolos redundantes. Alternativamente, los símbolos intermedios podrían basarse en relaciones prescritas entre símbolos, por ejemplo, relaciones entre los símbolos intermedios y los símbolos de origen, y relaciones adicionales de LDPC y HDPC entre los símbolos intermedios, en donde se usa un procedimiento de decodificación para generar los símbolos intermedios a partir de los símbolos de origen, basándose en las relaciones prescritas.

[24] Los procedimientos y sistemas pueden implementarse mediante circuitos electrónicos o mediante un dispositivo de procesamiento que ejecuta instrucciones de programación y tiene el código de programa de instrucciones adecuadas para implementar la codificación y / o la decodificación.

[25] Numerosos beneficios se logran por medio de la presente invención. Por ejemplo, en una realización específica, se reduce el gasto de cálculo de la codificación de datos para su transmisión por un canal. En otra realización específica, se reduce el gasto de cálculo de la decodificación de tales datos. En otra realización específica, la sobrecarga de recepción absoluta y relativa se reduce significativamente. Según la realización, se pueden lograr uno o más de estos beneficios. Estos y otros beneficios se proporcionan con más detalle a lo largo de la presente especificación y, más particularmente, a continuación.

[26] Una comprensión adicional de la naturaleza y las ventajas de las invenciones divulgadas en la presente memoria se puede realizar por referencia a las partes restantes de la memoria descriptiva y los dibujos adjuntos.

BREVE DESCRIPCIÓN DE LOS DIBUJOS

[27]

La figura 1 es un diagrama de bloques de un sistema de comunicaciones que usa codificación de múltiples etapas que incluye inactivación permanente, junto con otras características y elementos.

5

10

15

20

25

30

35

40

45

50

55

60

65

La figura 2 es una tabla de variables, matrices y similares, que se usan en otras varias figuras en este documento.

La figura 3 es un diagrama de bloques de una realización específica del codificador que se muestra en la figura 1.

La figura 4 es un diagrama de bloques que muestra el codificador dinámico de la figura 3 en mayor detalle.

La figura 5 es un diagrama de flujo que ilustra un proceso de codificación de inactivación permanente (PI).

La figura 6 es un diagrama de flujo que ilustra un proceso de codificación dinámica.

La figura 7 es un diagrama de flujo de una operación de cálculo de una ponderación para un cálculo de símbolos.

La figura 8 ilustra una tabla que podría almacenarse en la memoria, utilizable para determinar el grado de un símbolo en función de un valor de consulta.

La figura 9 muestra una matriz utilizada en un proceso de codificación o decodificación.

La figura 10 muestra una ecuación que representa partes de la matriz mostrada en la figura 9, para un polinomio mínimo específico.

La figura 11 es un diagrama de flujo que ilustra un proceso para configurar una matriz para su uso en codificación o decodificación.

La figura 12 ilustra una representación matricial de un conjunto de ecuaciones para ser resuelto por un

decodificador para recuperar una formación, C(), que representa símbolos de origen recuperados de una

formación, D(), que representa símbolos codificados recibidos, usando una sub-matriz SE que representa R símbolos estáticos o ecuaciones conocidas por el decodificador.

La figura 13 ilustra una matriz que resulta de las permutaciones de fila / columna de la matriz de la figura 12, usando la inactivación OTF (sobre la marcha).

La figura 14 es un diagrama de bloques que describe un proceso para generar la matriz en la figura 12.

La figura 15 ilustra una representación matricial de un conjunto de ecuaciones para ser resuelto por un

formación, D(), que representa símbolos codificados recibidos, usando una submatriz SE y una submatriz correspondiente a símbolos permanentemente inactivados.

La figura 16 es un diagrama de flujo que ilustra un proceso para generar una submatriz LT que podría usarse en la matriz de la figura 12 o la matriz de la figura 15.

La figura 17 es un diagrama de flujo que ilustra un proceso para generar una submatriz PI, como se podría usar en la matriz de la figura 15.

La figura 18 es un diagrama de bloques de un generador matricial.

La figura 19 es un diagrama de flujo que ilustra un proceso para generar una submatriz SE.

La figura 20 es un diagrama de flujo que ilustra un proceso para generar una submatriz PI.

La figura 21 es un diagrama de flujo que ilustra un proceso para despejar los símbolos recuperados en un decodificador.

La figura 22 ilustra una representación matricial de un conjunto de ecuaciones para ser resuelto por un

formación, D(), que representa símbolos codificados recibidos, después de permutaciones.

La figura 23 ilustra una representación matricial de un conjunto de ecuaciones para ser resuelto por un decodificador y que corresponde a la matriz mostrada en la figura 26.

La figura 24 ilustra una representación matricial utilizable como parte de un proceso de decodificación.

La figura 25 ilustra una representación matricial utilizable como otra parte de un proceso de decodificación.

5

10

15

20

25

30

35

40

45

50

55

60

65

La figura 26 ilustra una representación matricial de un conjunto de ecuaciones para ser resuelto por un decodificador después de una solución parcial.

La figura 27 es un diagrama de flujo que ilustra otro proceso para despejar los símbolos recuperados en un decodificador.

La figura 28 ilustra una representación matricial de un conjunto de ecuaciones para ser resuelto por un decodificador.

La figura 29 ilustra una representación matricial de un conjunto de ecuaciones para ser resuelto por un decodificador.

La figura 30 ilustra un sistema de codificación ejemplar que podría implementarse como módulos de hardware, módulos de software o partes de código de programa almacenadas en un almacén de programas y ejecutadas por un procesador, posiblemente como una unidad colectiva de código, no separada como se muestra en la figura.

La figura 31 ilustra un sistema de decodificación ejemplar que podría implementarse como módulos de hardware, módulos de software o partes de código de programa almacenado en un almacén de programas y ejecutado por un procesador, posiblemente como una unidad colectiva de código, no separada como se muestra en la figura.

[28] Adjunto como Apéndice A está una especificación de código para una realización específica de un sistema codificador / decodificador, un esquema de corrección de errores y aplicaciones para la entrega confiable de objetos de datos, a veces con detalles de la presente invención utilizada, que también incluye una especificación de cómo un codificador / decodificador sistemático podría usarse en el transporte de entrega de objetos. Debería entenderse que las realizaciones específicas descritas en el Apéndice A no son ejemplos limitadores de la invención y que algunos aspectos de la invención podrían usar las enseñanzas del Apéndice A, mientras que otros no podrían. También debería entenderse que las declaraciones limitadoras en el Apéndice A pueden ser limitadoras en cuanto a los requisitos de realizaciones específicas y que tales declaraciones limitadoras podrían o no corresponder a las invenciones reivindicadas y, por lo tanto, el lenguaje de la reivindicación no necesita estar limitado por tales declaraciones limitadoras.

DESCRIPCIÓN DETALLADA DE MODOS DE REALIZACIÓN ESPECÍFICOS

[29] Los detalles para implementar partes de codificadores y decodificadores que se mencionan en este documento son proporcionados por los documentos Luby I, Luby II, Shokrollahi I, Shokrollahi II, Shokrollahi III, Luby III y Shokrollahi IV y no se repiten aquí por razones de brevedad.

[30] La codificación de múltiples etapas, como se describe en el presente documento, codifica los datos de origen en una pluralidad de etapas. Habitualmente, pero no siempre, una primera etapa agrega una cantidad predeterminada de redundancia a los datos de origen. Una segunda etapa utiliza entonces un código de reacción en cadena, o similar, para producir símbolos codificados a partir de los datos de origen originales y los símbolos redundantes calculados por la primera etapa de la codificación. En una realización específica, los datos recibidos se decodifican primero usando un proceso de decodificación de reacción en cadena. Si ese proceso no tiene éxito en la recuperación de los datos originales por completo, se puede aplicar una segunda etapa de decodificación.

[31] Algunas de las formas de realización enseñadas en este documento pueden aplicarse a muchos otros tipos de códigos, por ejemplo, a los códigos según lo descrito en la Solicitud de Comentarios (RFC) 5170 del Grupo de tareas de ingeniería de Internet (IETF) (en adelante, "códigos de LDPC del IETF"), y a los códigos descritos en las patentes estadounidenses con números 6.073.250, 6.081.909 y 6.163.870 (en lo sucesivo, "códigos Tornado"), que dan como resultado mejoras en la fiabilidad y / o el rendimiento de la CPU y / o la memoria para esos tipos de códigos.

[32] Una ventaja de algunas realizaciones enseñadas en este documento es que son necesarias menos operaciones aritméticas para producir símbolos codificados, en comparación con la sola codificación de reacción en cadena. Otra ventaja de algunas realizaciones específicas que incluyen una primera etapa de codificación y una segunda etapa de codificación es que la primera etapa de codificación y la segunda etapa de codificación pueden realizarse en momentos distintos y / o por dispositivos distintos, dividiendo así la carga de cálculo y minimizando la carga de cálculo general y también el tamaño de la memoria y los requisitos de patrones de acceso. En realizaciones de codificación de múltiples etapas, se generan símbolos redundantes a partir del fichero de entrada durante la primera etapa de codificación. En estas realizaciones, en la segunda etapa de codificación, los símbolos codificados se generan a partir de la combinación del fichero de entrada y los símbolos redundantes. En algunas de estas realizaciones, los símbolos codificados se pueden generar según sea necesario. En realizaciones en las que la segunda etapa comprende la codificación de reacción en cadena, cada símbolo codificado se puede generar sin tener en cuenta cómo se generan otros símbolos codificados. Una vez generados, estos símbolos codificados

5

10

15

20

25

30

35

40

45

50

55

60

65

pueden colocarse luego en paquetes y transmitirse a su destino, conteniendo cada paquete uno o más símbolos codificados. Las técnicas de transmisión no paquetizadas pueden usarse, en cambio o además.

[33] Tal como se usa en el presente documento, el término "fichero" se refiere a cualquier dato que se almacena en uno o más orígenes y que ha de entregarse como una unidad a uno o más destinos. Por lo tanto, un documento, una imagen y un fichero de un servidor de ficheros o dispositivo de almacenamiento de ordenador son todos ejemplos de "ficheros" que pueden entregarse. Los ficheros pueden ser de tamaño conocido (tal como una imagen de un megaocteto almacenada en un disco duro) o pueden ser de un tamaño desconocido (tal como un fichero tomado de la salida de un origen de transmisión por flujo). De cualquier manera, el fichero es una secuencia de símbolos de origen, donde cada símbolo de origen tiene una posición en el fichero y un valor. Un "fichero" también se puede usar para referirse a una parte corta de un origen de transmisión por flujo, es decir, la secuencia de datos se puede dividir en intervalos de un segundo, y el bloque de datos de origen dentro de cada intervalo de un segundo de ese tipo se puede considerar como un "fichero". Como otro ejemplo, los bloques de datos desde un origen de transmisión por flujo de vídeo pueden dividirse adicionalmente en varias partes, basándose en las prioridades de esos datos, definidas, por ejemplo, por un sistema de vídeo que puede reproducir el flujo de vídeo, y cada parte de cada bloque puede considerarse como un "fichero". Por lo tanto, el término "fichero" se usa generalmente y no pretende ser extensamente limitador.

[34] Tal como se usa en este documento, los símbolos de origen representan los datos que han de transmitirse o transportarse, y los símbolos codificados representan los datos generados basándose en símbolos de origen que se transmiten por una red de comunicaciones, o se almacenan, para permitir la recepción y / o regeneración de los símbolos de origen. Los símbolos intermedios representan símbolos que se usan o generan durante una etapa intermedia de los procesos de codificación o decodificación, en donde habitualmente hay un procedimiento para generar símbolos intermedios a partir de símbolos de origen y un procedimiento inverso correspondiente para generar los símbolos de origen a partir de los símbolos intermedios. Los símbolos de entrada representan datos que se introducen en una o más etapas durante el proceso de codificación o decodificación, y los símbolos de salida representan datos que se emiten desde una o más etapas durante el proceso de codificación o decodificación.

[35] En muchas realizaciones, estos diferentes tipos o etiquetas de símbolos pueden ser iguales a, o estar comprendidos por, al menos parcialmente, otros tipos de símbolos y, en algunos ejemplos, los términos se usan de forma intercambiable. En un ejemplo, supongamos que un fichero que se va a transmitir es un fichero de texto de 1.000 caracteres, cada uno de los cuales se considera un símbolo de origen. Si esos 1.000 símbolos de origen se proporcionan como están a un codificador, que a su vez emite símbolos codificados que se transmiten, los símbolos de origen también son símbolos de entrada. Sin embargo, en realizaciones donde los 1.000 símbolos de origen se convierten, en una primera etapa, en 1.000 (o más o menos) símbolos intermedios y los símbolos intermedios se proporcionan al codificador para generar símbolos codificados en una segunda etapa, los símbolos de origen son los símbolos de entrada y los símbolos intermedios son los símbolos de salida en la primera etapa, y los símbolos intermedios son los símbolos de entrada y los símbolos codificados son los símbolos de salida en la segunda etapa, mientras que los símbolos de origen son los símbolos de entrada globales a este codificador de dos etapas y los símbolos codificados son los símbolos de salida globales de este codificador de dos etapas. Si, en este ejemplo, el codificador es un codificador sistemático, entonces los símbolos codificados pueden comprender los símbolos de origen junto con símbolos de reparación generados a partir de los símbolos intermedios, mientras que los símbolos intermedios son distintos tanto de los símbolos de origen como de los símbolos codificados. Si, en cambio, en este ejemplo, el codificador es un codificador no sistemático, entonces los símbolos intermedios pueden comprender los símbolos de origen junto con símbolos redundantes generados a partir de los símbolos de origen, usando, por ejemplo, un codificador de LDPC y / o HDPC en la primera etapa, mientras que los símbolos codificados son distintos tanto de los símbolos de origen como de los símbolos intermedios.

[36] En otros ejemplos, hay más símbolos y cada símbolo representa más de un carácter. En cualquier caso, cuando hay una conversión de símbolo, de origen a intermedio, en un transmisor, el receptor podría tener una correspondiente conversión de símbolo, de intermediario a origen, como la inversa.

[37] La transmisión es el proceso de transmitir datos desde uno o más remitentes a uno o más destinatarios a través de un canal para entregar un fichero. Un remitente también se menciona a veces como el codificador. Si un remitente está conectado a cualquier número de destinatarios por un canal perfecto, los datos recibidos pueden ser una copia exacta del fichero de origen, ya que todos los datos se recibirán correctamente. Aquí, suponemos que el canal no es perfecto, que es el caso para la mayoría de los canales del mundo real. De las muchas imperfecciones de canal, dos imperfecciones de interés son el borrado de datos y la incompletitud de los datos (que puede tratarse como un caso especial de borrado de datos). El borrado de datos ocurre cuando el canal pierde o descarta datos. La incompletitud de los datos ocurre cuando un destinatario no comienza a recibir datos hasta que algunos de los datos ya lo han pasado por alto, el destinatario deja de recibir datos antes de que termine la transmisión, el destinatario elige recibir solo una parte de los datos transmitidos y / o el destinatario, de forma intermitente, se detiene y comienza nuevamente a recibir datos. Como ejemplo de incompletitud de datos, un emisor de satélite en movimiento podría estar transmitiendo datos que representan un fichero de origen e iniciar la transmisión antes de que un receptor se encuentre dentro del alcance. Una vez que el destinatario está dentro del alcance, los datos pueden recibirse hasta que el satélite se salga del alcance, momento en el que el destinatario puede redirigir su antena

5

10

15

20

25

30

35

40

45

50

55

60

65

parabólica (tiempo durante el cual no recibe datos) para comenzar a recibir los datos sobre el mismo fichero de entrada, transmitido por otro satélite que se ha desplazado dentro del alcance. Como debería ser evidente al leer esta descripción, la incompletitud de datos es un caso especial de borrado de datos, ya que el destinatario puede tratar la incompletitud de los datos (y el destinatario tiene los mismos problemas) que si el destinatario estuviese dentro del alcance todo el tiempo, pero el canal perdió todos los datos hasta el punto donde el destinatario comenzó a recibir datos. Además, como es bien sabido en el diseño de sistemas de comunicación, los errores detectables se pueden considerar equivalentes a los borrados, simplemente descartando todos los bloques de datos o símbolos que tienen errores detectables.

[38] En algunos sistemas de comunicación, un destinatario recibe datos generados por múltiples remitentes, o por un remitente que usa conexiones múltiples. Por ejemplo, para acelerar una descarga, un destinatario podría conectarse simultáneamente a más de un emisor para transmitir datos relativos al mismo fichero. Como otro ejemplo, en una transmisión de multidifusión, podrían transmitirse múltiples flujos de datos de multidifusión para permitir que los destinatarios se conecten a una o más de estas secuencias para hacer coincidir la velocidad de transmisión agrupada con el ancho de banda del canal que los conecta al remitente. En todos estos casos, una preocupación es garantizar que todos los datos transmitidos sean de uso independiente para el destinatario, es decir, que los múltiples datos de origen no sean redundantes entre las transmisiones, incluso cuando las velocidades de transmisión sean muy diferentes para las diferentes secuencias, y cuando hay patrones arbitrarios de pérdida.

[39] En general, un canal de comunicación es el que conecta al emisor y al destinatario para la transmisión de datos. El canal de comunicación podría ser un canal en tiempo real, donde el canal lleva los datos del remitente al destinatario a medida que el canal obtiene los datos, o el canal de comunicación podría ser un canal de almacenamiento que almacena algunos de, o todos, los datos en su tránsito desde el remitente al destinatario. Un ejemplo de esto último es el almacenamiento en disco u otro dispositivo de almacenamiento. En ese ejemplo, un programa o dispositivo que genera datos se puede considerar como el emisor, transmitiendo los datos a un dispositivo de almacenamiento. El destinatario es el programa o dispositivo que lee los datos del dispositivo de almacenamiento. Los mecanismos que utiliza el remitente para obtener los datos en el dispositivo de almacenamiento, el dispositivo de almacenamiento en sí y los mecanismos que utiliza el destinatario para obtener los datos del dispositivo de almacenamiento forman colectivamente el canal. Si existe la posibilidad de que esos mecanismos o el dispositivo de almacenamiento puedan perder datos, entonces eso se trataría como borrado de datos en el canal de comunicación.

[40] Cuando el emisor y el destinatario están separados por un canal de comunicación en el que se pueden borrar símbolos, es preferible no transmitir una copia exacta de un fichero de entrada, sino transmitir datos generados a partir del fichero de entrada que ayuda a recuperar los borrados. Un codificador es un circuito, dispositivo, módulo o segmento de código que gestiona esa tarea. Una forma de ver el funcionamiento del codificador es que el codificador genera símbolos codificados a partir de símbolos de origen, donde una secuencia de valores de símbolos de origen representa el fichero de entrada. Cada símbolo de origen tendría por tanto una posición, en el fichero de entrada, y un valor. Un decodificador es un circuito, dispositivo, módulo o segmento de código que reconstruye los símbolos de origen a partir de los símbolos codificados recibidos por el destinatario. En la codificación de múltiples etapas, el codificador y el decodificador a veces se dividen adicionalmente en submódulos, realizando cada uno una tarea diferente.

[41] En realizaciones de sistemas de codificación de múltiples etapas, el codificador y el decodificador se pueden dividir adicionalmente en submódulos, cada uno realizando una tarea diferente. Por ejemplo, en algunas realizaciones, el codificador comprende lo que se denomina aquí codificador estático y codificador dinámico. Tal como se usa en el presente documento, un "codificador estático" es un codificador que genera un cierto número de símbolos redundantes a partir de un conjunto de símbolos de origen, en donde el número de símbolos redundantes se determina antes de la codificación. Cuando se usa la codificación estática en un sistema de codificación de múltiples etapas, la combinación de los símbolos de origen y los símbolos redundantes generados a partir de los símbolos de origen que usan un codificador estático a menudo se denominan símbolos intermedios. Ejemplos de códigos de codificación estática potenciales incluyen códigos de Reed-Solomon, códigos Tornado, códigos de Hamming, códigos de LDPC tales como los códigos LDPC de la IETF, etc. El término "decodificador estático" se usa en este documento para referirse a un decodificador que puede decodificar datos que fueron codificados por un codificador estático.

[42] Tal como se usa en este documento, un "codificador dinámico" es un codificador que genera símbolos codificados a partir de un conjunto de símbolos de entrada, donde el número de símbolos codificados posibles es independiente del número de símbolos de entrada, y donde el número de símbolos codificados a generar no necesariamente ha de estar fijado. A menudo, en un código de múltiples etapas, los símbolos de entrada son los símbolos intermedios generados usando un código estático y los símbolos codificados se generan a partir de símbolos intermedios usando un codificador dinámico. Un ejemplo de un codificador dinámico es un codificador de reacción en cadena, tal como los codificadores que se enseñan en los documentos Luby I y Luby II. El término "decodificador dinámico" se usa en el presente documento para referirse a un decodificador que puede decodificar datos que fueron codificados por un codificador dinámico.

5

10

15

20

25

30

35

40

45

50

55

60

65

[43] En algunas realizaciones, la codificación que es de código de múltiples etapas y sistemática usa un proceso de decodificación aplicado a los símbolos de origen para obtener los valores intermedios de símbolos basándose en las relaciones definidas por el codificador estático entre los símbolos intermedios y las definidas por el codificador dinámico entre los símbolos intermedios y los símbolos de origen, y luego un codificador dinámico se usa para generar símbolos codificados adicionales, o símbolos de reparación, de los símbolos intermedios. De manera similar, un decodificador correspondiente tiene un proceso de decodificación para recibir símbolos codificados y decodificar de ellos los valores de símbolos intermedios, basándose en las relaciones definidas por el codificador estático entre los símbolos intermedios y las definidas por el codificador dinámico entre los símbolos intermedios y los símbolos codificados recibidos, y luego se utiliza un codificador dinámico para generar cualquier símbolo de origen faltante entre los símbolos intermedios.

[44] Las formas de realización de la codificación de múltiples etapas no necesariamente deben estar limitadas a algún tipo particular de símbolo. Habitualmente, los valores para los símbolos se seleccionan a partir de un alfabeto de 2m símbolos, para algún entero positivo M. En tales casos, un símbolo de origen puede representarse mediante una secuencia de M bits de datos del fichero de entrada. El valor de M a menudo se determina basándose, por ejemplo, en los usos de la aplicación, el canal de comunicación y / o el tamaño de los símbolos codificados. Además, el tamaño de un símbolo codificado a menudo se determina en función de la aplicación, el canal y / o el tamaño de los símbolos de origen. En algunos casos, el proceso de codificación podría simplificarse si los valores del símbolo codificado y los valores del símbolo de origen fueran del mismo tamaño (es decir, representables por el mismo número de bits o seleccionados del mismo alfabeto). Si ese es el caso, entonces el tamaño del valor del símbolo de origen está limitado cuando el tamaño del valor del símbolo codificado es limitado. Por ejemplo, puede desearse poner símbolos codificados en paquetes de tamaño limitado. Si se transmitieran algunos datos acerca de una clave asociada a los símbolos codificados para recuperar la clave en el receptor, el símbolo codificado sería, preferiblemente, lo suficientemente pequeño para asimilar, en un paquete, el valor del símbolo codificado y los datos sobre la clave.

[45] Como ejemplo, si un fichero de entrada es un fichero de múltiples megaoctetos, el fichero de entrada se podría dividir en miles, decenas de miles o cientos de miles de símbolos de origen, codificando cada símbolo de origen miles, cientos o solo unos pocos octetos. Como otro ejemplo, para un canal de Internet basado en paquetes, un paquete con una carga útil con un tamaño de 1024 octetos podría ser adecuado (un octeto tiene 8 bits). En este ejemplo, suponiendo que cada paquete contiene un símbolo codificado y 8 octetos de información auxiliar, sería adecuado un tamaño de símbolo codificado de 8128 bits ((1024 - 8) * 8). Por lo tanto, el tamaño del símbolo de origen podría elegirse como M = (1024 - 8) * 8 u 8128 bits. Como otro ejemplo, algunos sistemas satelitales usan la norma de paquetes de MPEG, donde la carga útil de cada paquete comprende 188 octetos. En ese ejemplo, suponiendo que cada paquete contiene un símbolo codificado y 4 octetos de información auxiliar, sería adecuado un tamaño de símbolo codificado de 1472 bits ((188 - 4) * 8). Por lo tanto, el tamaño del símbolo de origen podría elegirse como M = (188 - 4) * 8, o 1472 bits. En un sistema de comunicación de propósito general que utiliza codificación de múltiples etapas, los parámetros específicos de la aplicación, como el tamaño del símbolo de origen (es decir, M, el número de bits codificados por un símbolo de origen), pueden ser variables establecidas por la aplicación.

[46] Cada símbolo codificado tiene un valor. En una realización preferida, que consideramos a continuación,

cada símbolo codificado también tiene asociado al mismo un identificador llamado su "clave". Preferiblemente, la clave de cada símbolo codificado puede ser determinada fácilmente por el destinatario para permitir que el destinatario distinga un símbolo codificado de otros símbolos codificados. Preferiblemente, la clave de un símbolo codificado es distinta de las claves de todos los demás símbolos codificados. Hay varias formas de formación de claves expuestas en la técnica anterior. Por ejemplo, el documento Luby I describe diversas formas de formación de claves que pueden emplearse en realizaciones de la presente invención. En otras realizaciones preferidas, tales

como la descrita en el Apéndice A, la clave para un símbolo codificado se denomina "identificador de símbolo

codificado" o "identificador de símbolo de codificación" o, más simplemente, "ESI".

[47] La codificación de múltiples etapas es particularmente útil cuando existe una expectativa de borrado de

datos o cuando el destinatario no comienza y termina la recepción exactamente cuando comienza y finaliza una transmisión. La última condición se denomina en el presente documento "incompletitud de datos". En cuanto a los sucesos de borrado, la codificación de múltiples etapas comparte muchos de los beneficios de la codificación de reacción en cadena enseñada en el documento Luby I. En particular, los símbolos codificados en múltiples etapas son aditivos en términos de información, por lo que se puede usar cualquier cantidad adecuada de paquetes para recuperar un fichero de entrada, con un grado de precisión deseado. Estas condiciones no afectan adversamente al proceso de comunicación cuando se usa codificación de múltiples etapas, porque los símbolos codificados generados con codificación de múltiples etapas son aditivos en términos de información. Por ejemplo, si se pierden cien paquetes debido a una ráfaga de ruido que causa el borrado de datos, se pueden recoger cientos de paquetes

adicionales después de la ráfaga para reemplazar la pérdida de los paquetes borrados. Si se pierden miles de

paquetes porque un receptor no sintonizó un transmisor cuando comenzó a transmitir, el receptor podría simplemente recoger esos miles de paquetes de cualquier otro período de transmisión, o incluso de otro transmisor. Con la codificación de múltiples etapas, un receptor no está obligado a recoger ningún conjunto particular de paquetes, por lo que puede recibir algunos paquetes de un transmisor, cambiar a otro transmisor, perder algunos

5

10

15

20

25

30

35

40

45

50

55

60

65

paquetes, perder el comienzo o el final de una transmisión dada y aún recuperar un fichero de entrada. La capacidad de incorporarse a, y abandonar, una transmisión sin coordinación receptor-transmisor ayuda a simplificar el proceso de comunicación.

[48] En algunas realizaciones, transmitir un fichero usando codificación de múltiples etapas puede incluir generar, formar o extraer símbolos de origen de un fichero de entrada, calcular símbolos redundantes, codificar símbolos de origen y redundantes en uno o más símbolos codificados, donde cada símbolo codificado se genera en base a su clave, independientemente de todos los demás símbolos codificados, y transmitir los símbolos codificados a uno o más destinatarios por un canal. Adicionalmente, en algunas realizaciones, la recepción (y reconstrucción) de una copia del fichero de entrada usando codificación de múltiples etapas puede incluir la recepción de algún conjunto o subconjunto de símbolos codificados desde uno o más flujos de datos, y la decodificación de los símbolos de origen a partir de los valores y claves de los símbolos codificados recibidos.

Códigos sistemáticos y códigos no sistemáticos

[49] Un código sistemático es un código donde los símbolos de origen están entre los símbolos codificados que pueden transmitirse. En este caso, los símbolos codificados están compuestos por símbolos de origen y símbolos redundantes, también llamados símbolos de reparación, generados a partir de los símbolos de origen. Un código sistemático es preferible a un código no sistemático para muchas aplicaciones, por varias razones. Por ejemplo, en una aplicación de entrega de ficheros, es útil poder comenzar a transmitir datos en orden secuencial mientras los datos se utilizan para generar datos de reparación, donde el proceso de generar datos de reparación puede tomar algo de tiempo. Como otro ejemplo, muchas aplicaciones prefieren enviar los datos de origen originales en orden secuencial en su forma no modificada a un canal y enviar datos de reparación a otro canal. Una razón habitual para esto es tanto prestar soporte a receptores heredados que no incorporan la decodificación de FEC como proporcionar al mismo tiempo una mejor experiencia a los receptores mejorados que sí incorporan la decodificación de FEC, en donde los receptores heredados se incorporan solo al canal de datos de origen y los receptores mejorados se incorporan tanto al canal de datos de origen como al canal de datos de reparación.

[50] En estos y otros tipos relacionados de aplicaciones, a veces puede darse el caso de que los patrones de pérdida y la fracción de pérdida entre los símbolos de origen recibidos por un receptor sean bastante diferentes a los experimentados entre los símbolos de reparación recibidos. Por ejemplo, cuando se envían símbolos de origen antes de símbolos de reparación, debido a las condiciones de pérdida por ráfagas del canal, la fracción y el patrón de pérdidas entre símbolos de origen pueden ser bastante diferentes a la fracción correspondiente y al patrón de pérdidas entre símbolos de reparación, y el patrón de pérdidas entre los símbolos de origen puede estar lejos de lo que podría ser habitual, si la pérdida fuera uniformemente aleatoria. Como otro ejemplo, cuando los datos de origen se envían en un canal y los datos de reparación en otro canal, podría haber condiciones de pérdida bastante diferentes en los dos canales. Por lo tanto, es deseable tener un código de FEC sistemático que funcione bien en diferentes tipos de condiciones de pérdida.

[51] Aunque los ejemplos en este documento se refieren a códigos sistemáticos (donde la salida o los símbolos codificados incluyen los símbolos de origen o de entrada) o a códigos no sistemáticos, se debería suponer que las enseñanzas en este documento son aplicables a ambos, a menos que se indique lo contrario. El documento Shokrollahi III enseña procedimientos para convertir un código de reacción en cadena, no sistemático, a un código sistemático de tal manera que las propiedades de robustez del código no sistemático sean mantenidas por el código sistemático así construido.

[52] En particular, utilizando los procedimientos enseñados en el documento Shokrollahi III, el código sistemático construido tiene la propiedad de que hay poca diferenciación, en términos de capacidad de recuperación por el decodificador, entre símbolos de origen perdidos y símbolos de reparación perdidos, es decir, la probabilidad de recuperación de la decodificación es esencialmente la misma para una magnitud dada de pérdida total, casi independiente de la proporción de la pérdida entre los símbolos de origen en comparación con la proporción de la pérdida entre los símbolos de reparación. Además, el patrón de pérdida entre los símbolos codificados no afecta significativamente a la probabilidad de recuperación de la decodificación. En comparación, para las construcciones de otros códigos sistemáticos, como los descritos para los códigos Tornado o para los códigos de LDPC de la IETF, en muchos casos existe una fuerte diferenciación en términos de capacidad de recuperación por el decodificador entre los símbolos de origen perdidos y los símbolos de reparación perdidos, es decir, la probabilidad de recuperación de la decodificación puede variar ampliamente, lo mismo para una magnitud dada de pérdida total, según la proporción de la pérdida entre los símbolos de origen, en comparación con la proporción de la pérdida entre los símbolos de reparación. Además, el patrón de pérdida entre los símbolos codificados puede tener un fuerte efecto en la probabilidad de recuperación de la decodificación. Los códigos Tornado y los códigos de LDPC de la IETF tienen propiedades de recuperación razonablemente buenas si las pérdidas de símbolos codificados son uniformemente aleatorias entre todos los símbolos codificados, pero las propiedades de recuperación se deterioran a medida que el modelo de pérdida se desvía de la pérdida aleatoria uniforme. Por lo tanto, en este sentido, las realizaciones enseñadas en el documento Shokrollahi III tienen ventajas sobre otras construcciones de códigos sistemáticos.

5

10

15

20

25

30

35

40

45

50

55

60

65

[53] Para un código de FEC con la propiedad de que existe un fuerte efecto en términos de capacidad de recuperación por el decodificador, según la proporción de símbolos de origen perdidos y símbolos de reparación perdidos y, según los patrones de pérdida, un enfoque para superar esta propiedad, cuando es aplicable, es enviar los símbolos codificados en un orden uniformemente aleatorio, es decir, la combinación de símbolos de origen y de reparación se envía en orden uniformemente aleatorio, y así los símbolos de origen se intercalan aleatoriamente entre los símbolos de reparación. Enviar los símbolos codificados en orden aleatorio tiene la ventaja de que sea cual sea el modelo de pérdida de canal, ya sea que las pérdidas sean por ráfagas o uniformemente aleatorias o de algún otro tipo de pérdidas, las pérdidas para los símbolos codificados siguen siendo aleatorias. Sin embargo, como se ha señalado anteriormente, este enfoque no es deseable para algunas aplicaciones, por ejemplo, para aplicaciones donde es deseable enviar los símbolos de origen en secuencia antes de los símbolos de reparación, o donde los símbolos de origen se envían en un canal diferente al de los símbolos de reparación.

[54] En tales casos, se desean construcciones de códigos sistemáticos en los que el patrón de pérdida entre los símbolos codificados no afecte en gran medida a las propiedades de recuperación del decodificador, y se proporcionan aquí algunos ejemplos.

[55] Tal como se usan en el presente documento, "aleatorio" y "seudo-aleatorio" a menudo son equivalentes y / o intercambiables y pueden depender del contexto. Por ejemplo, las pérdidas aleatorias pueden referirse a qué símbolos son perdidos por un canal, lo que pueden ser realmente un evento aleatorio, mientras que una selección aleatoria de vecinos de símbolos podría ser efectivamente una selección seudo-aleatoria repetible según un proceso no aleatorio, pero que tiene iguales, o similares, propiedades o comportamientos, como sería el caso con una selección verdaderamente aleatoria. A menos que se indique lo contrario explícitamente, o por contexto, caracterizar algo como aleatorio no significa excluir la seudo-aleatoriedad.

[56] En una aproximación a dicho codificador de FEC sistemático, los símbolos de origen son obtenidos por un codificador que incluye múltiples sub-bloques o sub-procesos de codificador, uno de los cuales funciona como un decodificador para generar símbolos intermedios que son símbolos de entrada para otro sub-bloque o sub-proceso. Los símbolos intermedios se aplican entonces a otro sub-bloque o sub-proceso que codifica los símbolos intermedios en los símbolos codificados, de modo que los símbolos codificados incluyan los símbolos de origen (junto con símbolos redundantes adicionales) generados a partir de un proceso coherente, proporcionando de tal modo beneficios de robustez y otras ventajas sobre un codificador que es un codificador sistemático que utiliza un proceso (por ejemplo, la copia) para obtener los símbolos de origen para el conjunto de símbolos codificados y otro proceso para obtener los símbolos redundantes para el conjunto de símbolos codificados.

[57] La codificación de salida puede ser un codificador de reacción en cadena, un codificador estático u otras variaciones. El Apéndice A describe una realización de código sistemático. Después de leer la presente divulgación, alguien medianamente experto en la materia debería ser capaz de extender fácilmente las enseñanzas del documento Shokrollahi III para aplicarlas a códigos sistemáticos tales como los códigos Tornado y los códigos de LDPC de la IETF, para producir nuevas versiones de estos códigos que también sean códigos sistemáticos, pero que tengan mejores propiedades de recuperación. En particular, las nuevas versiones de estos códigos, obtenidas aplicando el procedimiento general descrito a continuación, se mejoran para tener la propiedad de que la proporción de pérdida entre los símbolos de origen, en comparación con la proporción de pérdida entre los símbolos de reparación, no afecte significativamente la probabilidad de recuperación de la decodificación y, además, que el patrón de pérdida no afecte significativamente la probabilidad de recuperación de la decodificación. Por lo tanto, estos códigos se pueden usar de manera efectiva en las aplicaciones descritas anteriormente que requieren el uso de códigos de FEC sistemáticos con propiedades de recuperación que no se ven fuertemente afectadas por diferentes magnitudes de pérdida fraccional entre los símbolos de origen y de reparación, o por diferentes patrones de pérdida.

[58] El nuevo procedimiento de codificación puede aplicarse generalmente a la codificación para códigos de FEC sistemáticos, códigos de FEC no sistemáticos, códigos de FEC de tasa fija y códigos de FEC de reacción en cadena, para producir un procedimiento de codificación global para nuevos códigos de FEC sistemáticos mejorados. También hay un correspondiente procedimiento nuevo de decodificación que se puede aplicar.

Ejemplo de decodificador en el codificador

[59] Ahora se proporcionará un ejemplo de un decodificador en un codificador.

[60] Sea el procedimiento de codificación E sea un procedimiento de codificación utilizado por un codificador (en un transmisor o en otra parte) para un código E de FEC de tasa fija (no sistemático o sistemático) que genere N símbolos codificados a partir de K símbolos de origen, donde N es al menos K. De manera similar, sea el procedimiento de decodificación E el correspondiente procedimiento de decodificación para el código E de FEC, utilizado por un decodificador en un receptor o en otro lugar.

[61] Supongamos que el código E de FEC tiene la propiedad de que un conjunto aleatorio de K, entre los N, símbolos codificados es suficiente para recuperar los K símbolos de origen originales con una probabilidad

5

10

15

20

25

30

35

40

45

50

55

60

65

razonable utilizando el procedimiento de decodificación E, donde la probabilidad razonable podría ser, por ejemplo, la probabilidad de 1/2. La probabilidad razonable puede ser algún requisito establecido por el uso o la aplicación, y podría ser un valor distinto a 1/2. Debería entenderse que la construcción de un código particular no necesita ser específica para una probabilidad de recuperación particular, sino que las aplicaciones y sistemas se pueden diseñar para su nivel particular de robustez. En algunos casos, la probabilidad de recuperación se puede aumentar al considerar más de K símbolos, y luego determinar el uso de un proceso de decodificación de un conjunto de K símbolos entre estos símbolos considerados que permita una decodificación exitosa.

[62] Supongamos que para el código E de FEC, se asocia un ESI (identificador de símbolo codificado) a cada símbolo codificado y que el ESI identifica ese símbolo codificado. Sin pérdida de generalidad, los ESI se etiquetan aquí con 0, 1,2, ..., N-1.

[63] En una realización de un procedimiento F de codificación sistemática para un código F de FEC sistemático, generado usando los procedimientos para el código E de FEC, K y N son parámetros de entrada. Los símbolos de origen para el código F de FEC tendrán los ESI 0, ..., K-1 y los símbolos de reparación para el código F de FEC F tendrán los ESI K, ..., N-1. El procedimiento F de codificación sistemática para el código F de FEC genera N símbolos codificados a partir de K símbolos de origen C (0), ..., C (K-1), usando el procedimiento de codificación E y el procedimiento de decodificación E para el código E de FEC, realizado por hardware y / o software, de la siguiente manera:

(1) permutar aleatoriamente los N ESI asociadas al código E de FEC para llegar al conjunto permutado X(0), ..., X(N-1) de ESI del código E de FEC, en donde este conjunto permutado de ESI está organizado de tal forma que los K símbolos de origen del código E de FEC se pueden decodificar a partir de los primeros K símbolos codificados del código E de FEC, con respecto al orden de permutación de los ESI X(0) X(K-1),

(2) para cada i = 0, ..., N-1, asociar el ESI i del código F de FEC al ESI X (i) del código E de FEC,

(3) para cada i = 0, ..., K-1, fijar el valor del símbolo codificado del código E de FEC con ESI X(i) en el valor del símbolo de origen C(i),

(4) aplicar el procedimiento de decodificación E a los símbolos de origen C(0), ..., C(K-1) con los correspondientes ESI X(0), ..., X(K-1) del código E de FEC para generar los símbolos decodificados E(0), ..., E(K- 1) y

(5) aplicar el procedimiento de codificación E a los símbolos decodificados E(0), ..., E(K-1) para generar los símbolos codificados D(0), ..., D(N-1) del código E de FEC con los ESI 0, ..., N-1 asociados del código de FEC,

(6) los símbolos codificados para el procedimiento de codificación F con los ESI 0, 1, ..., N-1 son D(X(0)), D(X(1)), ..., D(X(N-1)).

[64] Obsérvese que la salida del procedimiento de codificación F es N símbolos codificados, de los cuales los primeros K son los símbolos de origen C(0), ..., C(K-1) con los ESI asociados 0, 1, ..., K-1. Por lo tanto, el procedimiento de codificación F produce una codificación sistemática de los datos de origen.

[65] Una realización de un procedimiento de decodificación F que corresponde al procedimiento de codificación F que se acaba de describir es la siguiente, donde K y N son parámetros de entrada para este procedimiento que se utilizan en toda su extensión. Este procedimiento de decodificación F recupera K símbolos de origen C(0), ..., C(K-1) a partir de K símbolos codificados D(0), ..., D(K-1) recibidos, con los ESI asociados Y(0), ..., Y(K-1) del código F de FEC. Los símbolos recibidos no necesitan ser exactamente los símbolos enviados. El procedimiento, realizado por hardware y / o software, es el siguiente:

(1) permutar aleatoriamente los N ESI asociados al código E de FEC para llegar al conjunto de los ESI permutados X(0), ..., X(N-1) del código E de FEC, en donde este conjunto de ESI permutados está organizado de tal forma que los K símbolos de origen del código E de FEC se pueden decodificar a partir de los primeros K símbolos codificados del código E de FEC, con respecto al orden de permutación de los ESI X(0), ..., X(K-1),

(2) aplicar el procedimiento de decodificación E a los símbolos codificados D(0), ..., D(K-1) con los ESI X(Y(0)), ..., X(Y(K-1)) asociados del código E de FEC, para generar los símbolos decodificados E(0), ..., E(K-1),

(3) utilizando el procedimiento de codificación E, generar los símbolos codificados C(0), ..., C(K-1) con los ESI X(0), ..., X(K-1) del código E de FEC, a partir de E(0), ... , E(K-1),

(4) los símbolos de origen decodificados del código F de FEC con los ESI 0, ..., K-1 son C(0), ..., C(K-1).

[66] Los procedimientos y aparatos que funcionan como se acaba de describir tienen algunas propiedades deseables. Por ejemplo, considérese un código E de FEC que es un código sistemático y que tiene la propiedad de

5

10

15

20

25

30

35

40

45

50

55

60

65

que un conjunto aleatorio de K símbolos codificados recibidos puede decodificarse con alta probabilidad, pero también tiene la propiedad de que cuando se reciben K símbolos codificados y la proporción de símbolos de origen entre los símbolos codificados recibidos no está cerca de K / N, entonces no se pueden decodificar con alta probabilidad. En este caso, la realización describe un nuevo código F de FEC que usa los procedimientos de codificación y decodificación del código E de FEC, y el nuevo código F de FEC tiene la propiedad deseable de que decodificará con alta probabilidad, a partir de un conjunto de K símbolos codificados recibidos, independiente de la proporción de los símbolos codificados recibidos que sean símbolos de origen.

[67] Hay muchas variantes de la realización anterior. Por ejemplo, en la etapa (1) del procedimiento de codificación F, la permutación aleatoria de los ESI podría ser seudo-aleatoria o basarse en algún otro procedimiento que produzca una buena selección de los ESI pero que no sea aleatorio ni seudo-aleatorio. En el caso de que el código E de FEC sea un código sistemático, es preferible que la fracción de los K primeros ESI en la permutación seleccionada en la etapa (1) entre los ESI sistemáticos sea proporcional a la tasa del código E de FEC, es decir, proporcional a K / N. Es preferible que las elecciones aleatorias de los ESI, realizadas mediante el nuevo procedimiento de codificación F en la etapa (1), puedan representarse mediante una cantidad sucinta de datos, por ejemplo, por una semilla para un generador seudo-aleatorio bien conocido o acordado, junto con un procedimiento acordado para elegir los ESI basándose en la semilla y en cómo funciona el generador seudo-aleatorio, de modo que el nuevo procedimiento de decodificación F pueda hacer exactamente la misma elección de permutación de los ESI en la etapa (1) basándose en la misma semilla y en el mismo generador seudo-aleatorio, y en los procedimientos para generar los ESI. En general, es preferible si tanto el proceso utilizado en el nuevo procedimiento de codificación F en la etapa (1) para generar la secuencia de los ESI, como el proceso utilizado en el nuevo procedimiento de decodificación F en la etapa (1) para generar la secuencia de los ESI, generan la misma secuencia de los ESI, para garantizar que el nuevo procedimiento de decodificación F sea el inverso del nuevo procedimiento de codificación F.

[68] También existen otras variantes, donde, por ejemplo, no se usan los ESI explícitos, sino que, en cambio, el identificador único de un símbolo codificado lo es por su posición con respecto a otros símbolos codificados, o por otros medios.

[69] En la descripción anterior, los ESI originales del código E de FEC se vuelven a correlacionar mediante el código F de FEC, de modo que al conjunto ordenado de símbolos de origen se les asignan los ESI 0, ..., K-1 en orden consecutivo, y a los símbolos de reparación se asignan los ESI K, ..., N-1. Son posibles otras variantes, por ejemplo, la re-correlación de los ESI puede ocurrir en un emisor justo después de que el procedimiento de codificación F haya generado los símbolos codificados, pero antes de que se transmitan los símbolos codificados, y la re-correlación inversa de los ESI puede ocurrir en un receptor según los símbolos codificados son recibidos, pero antes de que los símbolos codificados sean procesados para la recuperación de los símbolos de origen originales mediante el procedimiento de decodificación F.

[70] Como otra variante, en la etapa (1) del nuevo procedimiento de codificación F la permutación podría seleccionarse seleccionando primero los K+A ESI del código E de FEC, donde A es un valor que se elige para asegurar la capacidad de decodificación con alta probabilidad y luego, durante una simulación del proceso de decodificación, se determina cuáles K, entre los K + A ESI, se utilizan realmente durante la decodificación, y la permutación seleccionada podría seleccionar los K ESI realmente utilizados durante la decodificación entre el conjunto inicial de los K+A ESI para que sean los K primeros ESI de la permutación. Variantes similares se aplican al nuevo procedimiento de decodificación F.

[71] Como otra variante del procedimiento de codificación F, una semilla que se usa para generar la permutación aleatoria se calcula previamente para un valor de K, para garantizar que los primeros K símbolos codificados del código E de FEC, asociados a la permutación de los ESI producidos en la etapa (1), sean decodificables, y luego esta semilla siempre se usa para K en la etapa (1) del procedimiento de codificación F y el correspondiente procedimiento de decodificación F, para generar la permutación en la etapa (1). Los procedimientos para elegir tal semilla incluyen elegir aleatoriamente las semillas hasta que se encuentre una que asegure la capacidad de decodificación en la etapa (1), y luego seleccionar esta semilla. Alternativamente, la semilla podría generarse dinámicamente con estas propiedades mediante el procedimiento de codificación F, y luego esta semilla podría comunicarse al procedimiento de decodificación F.

[72] Como otra variante del procedimiento de codificación F, podría seleccionarse una permutación parcial en la etapa (1), es decir, no es necesario generar todos los ESI en la etapa (1) del nuevo procedimiento de codificación F, y no todos los símbolos codificados deben necesariamente ser generados si no son necesarios en las etapas (5) y (6), por ejemplo, porque corresponden a símbolos de origen que son parte de los símbolos codificados, o porque se necesita generar menos de N símbolos codificados. En otras variantes, no todos los símbolos codificados en las etapas (3) y (4) del nuevo procedimiento de decodificación F necesitan ser recalculados, ya que algunos de los símbolos codificados recibidos pueden corresponder a algunos de los símbolos de origen que se están recuperando. De forma similar, en la etapa (2) del nuevo procedimiento de decodificación F, no es necesario decodificar todos los K símbolos E(0), ..., E(K-1), por ejemplo, si algunos de los símbolos decodificados en la etapa (2) no son necesarios. en pasos posteriores para generar símbolos codificados.

5

10

15

20

25

30

35

40

45

50

55

60

65

[73] Los procedimientos y realizaciones descritos anteriormente tienen muchas aplicaciones. Por ejemplo, el procedimiento de codificación F y el procedimiento de decodificación F, y sus variantes, se pueden aplicar a los códigos Tornado y a los códigos de lDpC de la IETF para proporcionar una sobrecarga de recepción mejorada y un rendimiento mejorado de la probabilidad de fallo de decodificación. En general, estos nuevos procedimientos se aplican a cualquier código de FEC de tasa fija. Las variantes de estos nuevos procedimientos también se pueden aplicar a códigos de FEC que no tienen ninguna tasa fija, es decir, a códigos de FEC tales como los códigos de reacción en cadena, donde el número de símbolos codificados que se pueden generar es independiente del número de símbolos de origen.

[74] El documento Shokrollahi III contiene enseñanzas similares para crear procedimientos de codificación y decodificación sistemáticos para códigos de reacción en cadena. En algunas realizaciones, los procedimientos de codificación y decodificación E usados para estos códigos son los que se enseñan en los documentos Luby I, Luby II, Shokrollahi I, Shokrollahi II, Luby III y Shokrollahi IV. Para describir codificadores sistemáticos, a menudo es suficiente describir el procedimiento de codificación E y el procedimiento de decodificación E y usar los principios generales descritos anteriormente y conocidos a partir de esas referencias, para transformar estos procedimientos en procedimientos de codificación sistemática F y en procedimientos de decodificación sistemática F. Debería por tanto ser evidente para alguien medianamente experto en la técnica, tras leer esta divulgación y las referencias citadas, cómo adoptar las enseñanzas que describen los procedimientos de codificación E y los procedimientos de decodificación E y aplicar los mismos a los procedimientos de codificación sistemática F y los procedimientos de decodificación sistemática F, o similares.

Inactivación

[75] La decodificación de la inactivación, como se enseña en el documento Shokrollahi II, es un procedimiento general que se puede aplicar en combinación con la propagación de creencias toda vez se despeja un conjunto de variables desconocidas a partir de un conjunto de valores conocidos de ecuaciones lineales, y es particularmente beneficioso cuando se implementan procedimientos eficaces de codificación y decodificación que se basan en conjuntos de ecuaciones lineales. Para distinguir entre la decodificación de inactivación, como se describe en el documento Shokrollahi II, y la decodificación de inactivación permanente, como se describe a continuación, se usa la inactivación "sobre la marcha" (abreviada a "inactivación OTF" en algunos lugares) para referirse a los procedimientos y enseñanzas del documento Shokrollahi II, mientras que la "inactivación permanente" se usa para referirse a los procedimientos y enseñanzas en el presente documento, donde las inactivaciones se seleccionan de antemano.

[76] Un principio de la decodificación de propagación de creencias es que, siempre que sea posible durante el proceso de decodificación, el decodificador debería usar una ecuación (posiblemente reducida) que depende de una variable desconocida restante para despejar esa variable, y esa ecuación se asocia por tanto a esa variable, y luego reducir las ecuaciones restantes sin usar eliminando la dependencia de esas ecuaciones de la variable despejada. Tal proceso sencillo de decodificación basado en propagación de creencias se ha usado, por ejemplo, en algunas de las realizaciones de códigos Tornado, los códigos de reacción en cadena descritos en los documentos Luby I, Luby II, Shokrollahi I, Shokrollahi II, Luby III, Shokrollahi IV, y los códigos de LDPC de la IETF.

[77] La decodificación de inactivación OTF se realiza en múltiples fases. En una primera fase de un procedimiento de decodificación de inactivación OTF, siempre que el proceso de decodificación de propagación de creencias no pueda continuar porque no hay ninguna ecuación restante que dependa de una sola variable desconocida restante, el decodificador "desactivará OTF" una o más variables desconocidas y las considerará "despejadas" con respecto al proceso de propagación de creencias y "eliminadas" de las ecuaciones restantes (incluso aunque en realidad no lo sean), permitiendo así posiblemente que continúe el proceso de decodificación de propagación de creencias. Las variables que son inactivadas OTF durante la primera fase se despejan luego, por ejemplo, usando la eliminación Gaussiana o procedimientos más eficaces en términos de cálculo, en, por ejemplo, una segunda fase, y luego, en una tercera fase, los valores de estas variables inactivadas OTF se usan para despejar completamente la variable asociada a las ecuaciones durante la primera fase de decodificación.

[78] La decodificación de inactivación OTF, como se enseña con mayor detalle en el documento Shokrollahi II, se puede aplicar a muchos otros tipos de códigos además de los códigos de reacción en cadena. Por ejemplo, puede aplicarse a la clase general de códigos LDPC y LDGM, en particular, a los códigos de LDPC de la IETF y a los códigos Tornado, lo que resulta en mejoras en la fiabilidad (disminuyendo la probabilidad de no lograr decodificar) y / o en el rendimiento de la CPU y / o la memoria (aumentando la velocidad de codificación y / o decodificación y / o disminuyendo el tamaño de memoria requerido y / o los requisitos de patrones de acceso) para esos tipos de códigos.

[79] Algunas de las variantes de las realizaciones del código de reacción en cadena en combinación con la decodificación de inactivación OTF se describen en el documento Shokrollahi IV. Se describen otras variantes en la presente solicitud.

5

10

15

20

25

30

35

40

45

50

55

60

65

Resumen del sistema

[80] La figura 1 es un diagrama de bloques de un sistema de comunicaciones 100 que usa la codificación de múltiples etapas. Es similar a la mostrada en el documento Shokrollahi I, pero en este caso el codificador 115 tiene en cuenta una designación de cuáles símbolos intermedios están "permanentemente inactivados" y funciona de manera diferente en esos símbolos intermedios que en los símbolos intermedios que no están permanentemente inactivados durante el proceso de codificación dinámica. Asimismo, el decodificador 155 también tiene en cuenta los símbolos intermedios permanentemente inactivados al decodificar.

[81] Como se ilustra en la figura 1, los K símbolos de origen (C(0), ..., C(K-1)) se introducen en el codificador 115 y, si la decodificación es exitosa con los símbolos que están disponibles para el decodificador 155, entonces el decodificador 115 puede emitir una copia de esos K símbolos de origen. En algunas realizaciones, un flujo se analiza sintácticamente en bloques de K símbolos y, en algunas realizaciones, un fichero de cierto número de símbolos de origen mayor que K se divide en bloques de símbolos de tamaño K y así se transmite. En algunas realizaciones, cuando se prefiere un tamaño de bloque de K '> K, pueden añadirse K' - K símbolos de relleno a los K símbolos de origen. Estos símbolos de relleno pueden tener valores 0, o cualquier otro valor fijo que sea conocido tanto por el codificador 115 como por el decodificador 155 (o que de otro modo pueda determinarse en el decodificador 155). Se debería entender que el codificador 115 podría comprender múltiples codificadores, módulos o similares, y ese también puede ser el caso para el decodificador 155.

[82] Como se ilustra, el codificador 115 también recibe una secuencia de claves dinámicas desde un generador de claves dinámicas 120 y una secuencia de claves estáticas desde un generador de claves estáticas 130, cada uno de las cuales puede ser accionado por un generador de números aleatorios 135. La salida del generador de claves dinámicas 120 podría ser simplemente una secuencia de números cardinales, pero ese no necesariamente tiene que ser el caso. El funcionamiento de los generadores de claves podría ser como se muestra en el documento Shokrollahi I.

[83] Debería entenderse que varios bloques funcionales mostrados en las figuras pueden implementarse como hardware con las entradas especificadas proporcionadas como señales de entrada, o pueden implementarse mediante un procesador que ejecuta instrucciones que están almacenadas en una memoria de instrucciones y son ejecutadas en el orden adecuado para realizar la función correspondiente. En algunos casos, se usa hardware especializado para realizar las funciones y / o ejecutar el código del programa. El código de programa y el procesador no siempre se muestran, pero alguien medianamente experto en la materia sabrá cómo implementar dichos detalles al leer esta divulgación.

[84] El codificador 115 también recibe entradas desde un designador de inactivación 125 y otros parámetros introducidos en el sistema 100 al estilo descrito en otra parte del presente documento. Las salidas del designador de inactivación 125 pueden incluir un valor, P, que representa el número de símbolos intermedios que se designan como "inactivados permanentemente" con fines de decodificación (la "lista PI" indica cuáles P de los símbolos intermedios están en la lista). Como se explica en otra parte, los símbolos intermedios usados para procesos de codificación son solo los K símbolos de origen en algunas realizaciones, pero, en otras realizaciones, hay algún tipo de procesamiento, conversión, codificación, decodificación, etc., que genera los símbolos intermedios de los K símbolos de origen, más allá de simplemente copiarlos.

[85] Los parámetros de entrada podrían incluir semillas aleatorias utilizadas por los generadores de claves y / o los procesos de codificación del codificador (descritos más detalladamente a continuación), la cantidad de símbolos codificados a generar, el número de símbolos de LDPC a generar, el número de símbolos de HDPC a generar, el número de símbolos intermedios a generar, el número de símbolos redundantes a generar, etc., y / o algunos de estos valores se calculan a partir de otros valores disponibles para el codificador 115. Por ejemplo, el número de símbolos de LDPC a generar podría calcularse completamente a partir de una fórmula fija y del valor de K.

[86] El codificador 115 genera, a partir de sus entradas, una secuencia de símbolos codificados (B(Iü), B(h), B(I2), ...) y los proporciona a un módulo de transmisión 140 que también recibe los valores de la clave dinámica (I0, I 1, I2, ...) desde el generador de claves dinámicas 120, pero esto podría no ser necesario si hay otro procedimiento para transmitir esa información. El módulo de transmisión 140 transmite lo que se le da a un canal 145, posiblemente, de una manera convencional que no necesita ser descrita aquí con más detalle. Un módulo de recepción 150 recibe los símbolos codificados y los valores de clave dinámicos (cuando sea necesario). El canal 145 puede ser un canal a través del espacio (para transmitir desde un lugar para ser recibido en otro lugar) o un canal a través del tiempo (para grabar en medios, por ejemplo, para reproducir en otro momento). El canal 145 puede causar la pérdida de algunos de los símbolos codificados. Por lo tanto, los símbolos codificados B(Ia), B(Ib), ... que el decodificador 115 recibe desde el módulo de recepción 150 podrían no ser iguales a los símbolos codificados que enviaron los módulos de transmisión. Esto se indica mediante los diferentes sub-índices.

[87] El decodificador 155 es preferiblemente capaz de regenerar las claves usadas para los símbolos recibidos (claves estas que podrían diferir), utilizando el regenerador dinámico de claves 160, el generador de números aleatorios 163 y el generador de claves estáticas 165, y de recibir como entradas diversos parámetros de

5

10

15

20

25

30

35

40

45

50

55

60

65

decodificación. Algunas de estas entradas podrían estar codificadas permanentemente (es decir, ingresadas durante la construcción de un dispositivo) y algunas pueden ser entradas variables.

[88] La figura 2 es una tabla de variables, formaciones y similares, con un resumen de la notación que se usa con mayor frecuencia en las otras figuras y a lo largo de esta divulgación. A menos que se indique lo contrario, K indica el número de símbolos de origen para el codificador, R indica el número de símbolos redundantes generados por un codificador estático y L es el número de "símbolos intermedios", es decir, la combinación de símbolos de origen y redundantes, y así L = K + R.

[89] Como se explica a continuación, en algunas realizaciones de un codificador estático, se generan dos tipos de símbolos redundantes. En una realización específica, utilizada aquí en muchos ejemplos, el primer conjunto comprende símbolos de LDPC y el segundo conjunto comprende símbolos de HDPC. Sin pérdida de generalidad, muchos ejemplos en este documento se refieren a S como el número de símbolos de LDPC y a H como el número de símbolos de HDPC. Podría haber más de dos tipos de símbolos redundantes, por lo que no es necesario que R = S+H. Los símbolos de LDPC y los símbolos de HDPC tienen diferentes distribuciones de grados y una persona con experiencia normal en la materia, al leer esta divulgación, vería cómo usar símbolos redundantes que no son símbolos de LDPC o HDPC, pero donde los símbolos redundantes comprenden dos (o más) conjuntos de símbolos en los que cada conjunto tiene una distribución de grados distinta a las distribuciones de grados de los otros conjuntos. Como es bien sabido, la distribución de grados de un conjunto de símbolos redundantes se refiere a la distribución de grados, en la que el grado de un símbolo redundante se refiere al número de símbolos de origen de los que depende el símbolo redundante.

[90] P indica el número de símbolos permanentemente inactivos entre los símbolos intermedios. Los símbolos permanentemente inactivos son aquellos que están designados para un tratamiento particular, a saber, ser "apartados" o "inactivados" en una red de propagación de creencias para continuar la propagación de creencias (y luego volver a despejar después de despejar los símbolos inactivados), en donde los símbolos inactivados permanentemente se distinguen de otros símbolos inactivados en que los símbolos permanentemente inactivados están designados en el codificador para dicho tratamiento.

[91] N indica el número de símbolos recibidos en los que se realiza un intento de decodificación por parte del decodificador 155, y A es el número de símbolos de "sobrecarga", es decir, el número de símbolos codificados recibidos más allá de K. Por lo tanto, A = N-K.

[92] K, R, S, H, P, N y A son números enteros, habitualmente todos mayores o iguales a uno, pero, en realizaciones específicas, algunos de ellos pueden ser uno o cero (por ejemplo, R = 0 es el caso donde no hay símbolos redundantes y P = 0 se reduce al caso del documento Shokrollahi II, donde solo hay inactivación OTF).

[93] El vector de símbolos de origen se indica con (C(0), ..., C(K-1)) y el vector de símbolos redundantes se indica con (C(K), ..., C(L-1)). Por lo tanto, (C(0), ..., C(L-1)) indica el vector de símbolos intermedios, en el caso sistemático. Un cierto número, P, de esos símbolos intermedios son designados como "permanentemente inactivos". Una "lista PI" indica cuáles de los símbolos intermedios son los permanentemente inactivos. En muchas realizaciones, la lista PI simplemente apunta a los últimos P símbolos intermedios, es decir, C(L-P), ..., C(L-1), pero esto no es un requisito. Se supone que ese caso solo simplifica las partes restantes de esta descripción.

[94] Los símbolos intermedios que no están en la lista PI se denominan "símbolos intermedios LT" en este documento. En el ejemplo, los símbolos intermedios LT serían C(0), ..., C(L-P-1). D(0), ..., D(N-1) indican los símbolos codificados recibidos.

[95] Cabe señalar que cuando una formación de valores se describe como "N(0), ..., N(x)" o similar, no se debería suponer que esto requiere al menos tres valores, ya que no se pretende excluir el caso donde solo hay uno o dos valores.

Procedimiento de codificación que utiliza la inactivación permanente

[96] La figura 3 es un diagrama de bloques de una realización específica del codificador 115 que se muestra en la figura 1. Como se ilustra allí, los símbolos de origen se almacenan en una memoria temporal de entrada 205 y se proporcionan a un codificador estático 210 y a un codificador dinámico 220, que también reciben entradas de claves y otras entradas. El codificador estático 210 podría incluir el almacenamiento interno 215 (memoria, memoria intermedia, memoria virtual, almacenamiento de registros, etc.) para almacenar valores internos e instrucciones de programa. Asimismo, el codificador dinámico 220 podría incluir el almacenamiento interno 225 (memoria, memoria intermedia, memoria virtual, almacenamiento de registros, etc.) para almacenar valores internos e instrucciones de programa.

[97] En algunas realizaciones, un calculador de redundancia 230 determina el número R de símbolos redundantes a crear. En algunas realizaciones, el codificador estático 210 genera dos conjuntos distintos de símbolos redundantes y, en una realización específica, el primer conjunto son los primeros S símbolos redundantes,

5

10

15

20

25

30

35

40

45

50

55

60

65

es decir, los símbolos C(K), C (K+S-1) y son símbolos de LDPC, mientras que el segundo conjunto son los H siguientes símbolos redundantes, es decir, C(L-H), ..., C (L-1), y son símbolos de HDPC. Si la lista PI son los últimos P símbolos redundantes, entonces todos los H símbolos redundantes pueden estar en la lista PI (si P > H) o todos los P símbolos redundantes pueden ser símbolos de HDPC (si P < H).

[98] Las operaciones que conducen a la generación de estos dos conjuntos de símbolos pueden ser bastante diferentes. Por ejemplo, en algunas realizaciones descritas a continuación, las operaciones para generar los símbolos redundantes de LDPC son operaciones binarias y las operaciones para generar los símbolos de HDPC son no binarias.

[99] El funcionamiento del codificador dinámico 220 se explica con más detalle en la figura 4. De acuerdo a una realización, el codificador dinámico 220 comprende dos codificadores, un codificador PI 240 y un codificador LT 250. En algunas realizaciones, el codificador LT 250 es un codificador de reacción en cadena y el codificador PI 240 es un codificador de reacción en cadena de un tipo particular. En otras realizaciones, estos dos codificadores pueden ser muy similares, o el codificador PI 240 no es un codificador de reacción en cadena. No importa cómo se definan estos codificadores, generan símbolos, en donde el codificador LT 250 genera sus símbolos a partir de los símbolos intermedios LT C (0), ..., C(L-P-1) que están designados como no permanentemente inactivos, y mientras el codificador PI 240 genera sus símbolos a partir de los símbolos intermedios permanentemente inactivos C(L-P), ..., C(L-1). Estos dos símbolos generados entran al combinador 260 que genera el símbolo codificado final 270.

[100] En algunas realizaciones de la presente invención, algunos de los símbolos permanentemente inactivados pueden participar en el proceso de codificación LT, y algunos de los símbolos que no son símbolos permanentemente inactivados pueden participar en el proceso de codificación PI. En otras palabras, la lista PI y el conjunto de símbolos que comprende los símbolos intermedios LT no necesitan ser disjuntos.

[101] En realizaciones preferidas, los símbolos proporcionados al combinador 260 pueden tener la misma longitud, y la función realizada por el combinador 260 es una operación lógica XOR en estos símbolos para generar el símbolo codificado 270. Sin embargo, esto no es necesario para el funcionamiento de esta invención. Se pueden prever otros tipos de combinadores que podrían conducir a resultados similares.

[102] En otras realizaciones, los símbolos intermedios se subdividen en más de dos conjuntos, por ejemplo, un conjunto de símbolos LT y varios (más de uno) conjuntos de símbolos PI, cada uno con su codificador asociado 240. Por supuesto, cada codificador asociado podría implementarse como un elemento informático común o elemento de hardware que opera sobre diferentes instrucciones de acuerdo a un proceso de codificación al actuar como un codificador diferente para diferentes conjuntos.

[103] Una operación ejemplar del proceso de codificación PI 241, como podría ser realizada por el codificador PI 240, se ejemplifica en la figura 5. Usando la clave I_a correspondiente a un símbolo codificado a generar, en la etapa 261, el codificador determina una ponderación positiva, WP, y una lista, ALP, que contiene WP enteros entre L-P y L-1, inclusive. En la etapa 263, si la lista ALP = (t(0), ..., t(WP-1)), entonces el valor de un símbolo X se establece en X = C(t(0))© C(t(1))© ... © C(t(WP-1)), en donde© indica la operación lógica XOR.

[104] En algunas realizaciones, la ponderación WP se fija en algún número, tal como 3 o 4 o algún otro número fijo. En otras realizaciones, la ponderación WP puede pertenecer a un pequeño conjunto de tales números posibles, tales como los elegidos por ser iguales a 2 o 3. Por ejemplo, como se muestra en la realización del Apéndice A, la ponderación WP depende de la ponderación del símbolo generado por el proceso de codificación LT 251, como podría ser realizado por el codificador LT 250. Si la ponderación generada por el codificador LT 250 es 2, entonces se elige WP igual a 2 o 3, según la clave I_a, en donde la proporción de veces en que WP es 2 o 3 es aproximadamente igual; si la ponderación generada por el codificador LT 250 es mayor que 3, entonces se elige WP igual a 2.

[105] La figura 6 es un ejemplo de un proceso de codificación LT 251 de acuerdo a una de las realizaciones de la presente invención, y que usa las enseñanzas de los documentos Luby I y Shokrollahi I. En la etapa 267, la clave I_a se usa para generar una ponderación, WL y una lista, AL, respectivamente. En la etapa 269, si lista ALP = (j(0), ..., j(WL-1)), entonces el valor de un símbolo X se establece en X = C(j(0))© C(j(1))© ... © C(j(WL-1)).

[106] La figura 7 ilustra una operación de cálculo de la ponderación WL. Como se muestra allí, en la etapa 272, se crea un número, v, que está asociado al símbolo codificado a generar y que se puede calcular basándose en la clave I_a para ese símbolo codificado. Puede ser el índice, la etiqueta representativa, etc. del símbolo codificado, o un número distinto, siempre que los codificadores y decodificadores puedan ser coherentes. En este ejemplo, v está entre 0 y 220, pero, en otros ejemplos, son posibles otros rangos (tales como 0 a 232). La generación de v se puede hacer de forma explícita usando tablas generadoras de aleatoriedad, pero la operación exacta de cómo generar estos números aleatorios puede variar.

[107] Se supone que el codificador tiene acceso a una tabla M, de la que se proporciona un ejemplo en la figura 8. La Tabla M, llamada tabla de "consulta de distribución de grados", contiene dos columnas y múltiples filas. La

5

10

15

20

25

30

35

40

45

50

55

columna de la izquierda está etiquetada con valores posibles de la ponderación WL, y la columna de la derecha está etiquetada con números enteros entre 0 y 220, inclusive. Para cualquier valor de v, hay exactamente una célula en la columna M[d] de la tabla de consulta de distribución de grados, en donde M[d-1] < v <M[d] es verdad. Para esa única célula, hay un valor correspondiente en la columna d, y el codificador usa eso como la ponderación WL para el símbolo codificado. Por ejemplo, cuando un símbolo codificado tiene v = 900.000, la ponderación para ese símbolo codificado sería WL = 7.

[108] El codificador estático 210 tiene acceso a los elementos SE(k, j) donde k = 0, ..., R-1 y j = 0, ..., L-1. Estos elementos pueden pertenecer a cualquier campo finito para el que exista una operación * entre los elementos a del campo y los símbolos X, de manera que a * X sea un símbolo y a*(X© Y) = a*X© a*Y, donde© indica la operación lógica XOR. Dichos campos y operaciones se han detallado en el documento Shokrollahi IV. El funcionamiento del codificador estático 210 se puede describir como calcular, para una secuencia dada de símbolos de origen C(0) C(K- 1), una secuencia de símbolos redundantes C(K), ..., C(L-1) que satisface la relación mostrada en la Ecuación 1, en la que Z(0), ..., Z(R-1) son valores conocidos por el codificador y el decodificador (por ejemplo, 0).

( C(0) ^

r 5B{0,0): SElUj) , . SEÍ0.L-2) 3¡E«U 1) 1 CtflT-1) r Z(U) '

jñ L 1 | ': SE(R- U) . skr u-n, C(K)

Lcu-uj

(Ec. 1).

[109] En la Ecuación 1, las entradas SE (k, j) pueden ser todas binarias, o algunas de ellas pueden pertenecer al campo GF(2), mientras que otras pertenecen a otros campos. Por ejemplo, la matriz correspondiente de la realización del Apéndice A se da en la figura 9. Comprende dos sub-matrices, una con filas S y una con H filas. La sub-matriz superior comprende dos partes: comprendiendo la sub-matriz las últimas P columnas en las que cada fila tiene dos consecutivas (donde las posiciones se cuentan módulo P). Las primeras W = L-P columnas de esta matriz comprenden matrices circulantes seguidas por una matriz de identidad SxS. Las matrices circulantes comprenden B de las columnas y cada una (excepto posiblemente la última) tiene S filas. El número de estas matrices circulantes es ceil (B / S). Las columnas en estas matrices circulantes tienen, cada una, exactamente 3 unos. La primera columna de la k-ésima matriz circulante tiene unos en las posiciones 0, (k+1) mod S y (2k+1) mod S. Las otras columnas son desplazamientos cíclicos de la primera. Las H filas inferiores en la figura 9 comprenden una matriz Q con entradas en GF (256), seguida de una matriz de identidad de tamaño HxH.

[110] Si a indica un elemento de GF (256) con polinomio mínimo x8+x4+x3+x2+1, entonces la matriz Q es igual a la matriz dada en la figura 10. Aquí, A1, ..., Ak+s-1 son columnas de ponderación 2 para las cuales las posiciones de las 2 entradas distintas de cero se determinan seudo-aleatoriamente de acuerdo al procedimiento esbozado en la Sección 5.3.3.3. del Apéndice A. Para elecciones juiciosas de los valores de S, P y H (tales como los provistos en el Apéndice A), la matriz en la figura 10 conduce a excelentes propiedades de recuperación del código correspondiente. El procedimiento descrito anteriormente se ejemplifica en la figura 11. En la etapa 276, la matriz SE se inicializa en 0. En la etapa 278, se proporciona una variable de entrada S, igual al número de símbolos de LDPC, al proceso, y los valores de SE(i, j) se fijan en 1 para los pares (i, j) tales que i = j mod S, o i = (1 + floor(j/S)) + j mod S, o i = 2*(1+floor(j/S))+j mod S. Esta etapa se ocupa de las matrices circulantes en la figura 9.

[111] En la etapa 280, las posiciones correspondientes a la matriz de identidad Is en la figura 9 se fijan en uno. En la etapa 282, las posiciones correspondientes a la parte PI de la matriz en la figura 9 se fijan en 1. Estas posiciones son de la forma (i,1) y (i,t), donde 1 = i mod P y t = (i+1) mod P. En la etapa 284, se fijan las posiciones correspondientes a la matriz Q en la figura 9. En consecuencia, la matriz Q se proporciona como una entrada adicional para esta etapa. En la etapa 286, las posiciones correspondientes a la matriz de identidad Ih en la matriz de la figura 9 se fijan en uno.

[112] Otras opciones para la matriz SE son posibles y dependen de la aplicación particular y de los requisitos exigidos al código general. No importa cómo se elija la matriz en la Ecuación 1, la tarea del codificador estático 210 se puede cumplir de varias maneras. Por ejemplo, la eliminación Gaussiana puede usarse como un proceso para recuperar los valores desconocidos C(K), ..., C(L-1), como sería evidente para alguien medianamente experto en la técnica después de leer esta divulgación.

Decodificación e inactivación permanente

[113] El problema de la decodificación puede enunciarse de la siguiente manera: el decodificador 155 tiene N símbolos codificados B(Ia), B(Ib), ... con las claves correspondientes Ia, Ib, ... El conjunto completo de estos símbolos

5

10

15

20

25

30

35

40

45

50

55

60

65

codificados, o un subconjunto de los mismos, puede haber sido recibido por el decodificador, mientras que los otros símbolos codificados pueden haber sido dados al decodificador por otros medios. El objetivo del decodificador es recuperar los símbolos de origen C(0), ..., C(K-1). Para simplificar la presentación, indicamos los símbolos codificados recibidos con D(0), ..., D(N-1).

[114] Muchas de las operaciones de decodificación se pueden describir sucintamente utilizando el lenguaje de matrices y operaciones sobre tales matrices, en particular, resolviendo sistemas de ecuaciones con tales matrices. En la siguiente descripción, las ecuaciones pueden corresponder a los símbolos codificados recibidos y las variables pueden corresponder a los símbolos de origen o a un conjunto combinado de símbolos de origen y símbolos redundantes, generados a partir de los símbolos de origen, a menudo denominados símbolos intermedios, que se deben despejar basándose en codificados recibidos símbolos. En la especificación proporcionada como Apéndice A, los símbolos codificados podrían denominarse "símbolos de codificación" (y existen otras variaciones), pero debería ser evidente, después de leer toda la especificación y el apéndice, cómo se relacionan las referencias. También debería entenderse que las matrices y operaciones y las soluciones de ecuaciones pueden implementarse como instrucciones de ordenador correspondientes a esas operaciones matemáticas, y de hecho no es práctico hacer tales operaciones sin un ordenador, procesador, hardware o algún elemento electrónico.

[115] La inactivación permanente se utiliza para determinar en el decodificador un conjunto de variables a inactivar, denominadas símbolos o variables permanentemente inactivados, antes de que se inicie la primera fase del proceso de decodificación. Los procedimientos de decodificación de inactivación permanente, descritos a continuación, se pueden aplicar a los códigos existentes, o bien los códigos se pueden diseñar especialmente para funcionar aún mejor junto con la decodificación de inactivación permanente. Los procedimientos de decodificación de inactivación permanente se pueden aplicar a la resolución de cualquier sistema de ecuaciones lineales y, en particular, se pueden aplicar a códigos de reacción en cadena, códigos de LDPC de la IETF y códigos Tornado.

[116] La decodificación de inactivación permanente es un procedimiento general que puede aplicarse en combinación con la decodificación de propagación de creencias y / o la decodificación de inactivación OTF, siempre que se despeja un conjunto de variables desconocidas de un conjunto de valores de ecuación lineal conocidos, y es particularmente beneficioso al implementar procedimientos eficaces de codificación y decodificación que se basan en conjuntos de ecuaciones lineales. En una primera fase, basada en la estructura del procedimiento de codificación conocido, o basada en las ecuaciones recibidas, se declara que un conjunto de variables desconocidas está permanentemente inactivado, y las variables permanentemente inactivadas se eliminan de las ecuaciones lineales y se consideran "despejadas" en la segunda fase del proceso de decodificación (excepto que, a medida que se reducen las ecuaciones lineales de la segunda fase, se realizan las mismas reducciones en las variables permanentemente inactivadas).

[117] En la segunda fase, la decodificación de propagación de creencias se aplica a las variables desconocidas que no se inactivan permanentemente utilizando la decodificación de propagación de creencias descrita previamente, o bien la decodificación de inactivación OTF se aplica a las variables desconocidas que no están permanentemente inactivadas, de manera similar a la descrita para la primera fase del procedimiento de decodificación por inactivación OTF, produciendo así un conjunto de símbolos o ecuaciones codificados reducidos. Los símbolos o ecuaciones codificados reducidos que resultan de la segunda fase tienen la propiedad de que su dependencia de las variables o símbolos que no están inactivados ha sido eliminada, y así los símbolos o ecuaciones codificados reducidos dependen solo de las variables o símbolos inactivados. Téngase en cuenta que también se pueden conservar símbolos o ecuaciones codificados originales, de modo que tanto los símbolos codificados originales como los símbolos codificados reducidos puedan estar disponibles en algunas implementaciones.

[118] En una tercera fase, las variables permanentemente inactivadas, junto con cualquier otra variable inactivada OTF generada en la segunda fase usando la decodificación de inactivación OTF, se despejan usando los símbolos o ecuaciones codificados reducidos, por ejemplo, usando la eliminación Gaussiana o, si existe, una estructura especial de las relaciones entre las variables permanentemente inactivadas y las ecuaciones lineales se usan para despejar de manera más eficaz que usando la eliminación Gaussiana.

[119] En una cuarta fase, los valores de las variables inactivadas despejadas, ya sean variables desactivadas de OTF o variables inactivadas permanentemente, se utilizan junto con los símbolos o ecuaciones codificadas originales (o símbolos o ecuaciones codificadas originales nuevamente obtenidos) para despejar las variables que no fueron inactivadas.

[120] Una de las ventajas de los procedimientos de decodificación de inactivación permanente es que el número w de inactivaciones OTF distintas de las inactivaciones permanentes puede ser generalmente pequeño o cero, y puede ser en gran parte independiente de qué símbolos codificados se reciben. Esto puede hacer que la complejidad de decodificación sea consistentemente pequeña, independientemente de cuáles símbolos codificados se reciban, permitir una decodificación más confiable y permitir accesos de memoria más predecibles y más escasos, que se puedan planificar de manera más eficaz. Debido a que hay solo un pequeño número de inactivaciones OTF en la segunda fase, y debido a que las inactivaciones OTF en la segunda fase generalmente

5

10

15

20

25

30

35

40

45

50

55

60

65

solo se determinan durante el proceso de decodificación que puede hacer que el patrón de operaciones de símbolos sea algo impredecible, los patrones de acceso a memoria son más predecibles durante la decodificación, permitiendo, en general, procesos de decodificación eficaces más predecibles.

[121] Hay muchas variantes de lo anterior. Por ejemplo, las fases se pueden ejecutar en orden intercalado no secuencial. Como otro ejemplo, los símbolos inactivados pueden a su vez despejarse en la tercera fase usando la decodificación de inactivación OTF o la decodificación de inactivación permanente en múltiples fases adicionales. Como otro ejemplo, la decodificación de inactivación permanente se puede aplicar a un sistema lineal de ecuaciones y variables que pueden usarse para códigos de corrección de errores, o códigos de corrección de borrado, o para otras aplicaciones que se pueden resolver usando sistemas lineales de ecuaciones. Como otro ejemplo, estos procedimientos se pueden aplicar tanto a códigos sistemáticos como a códigos no sistemáticos. Como otro ejemplo, estos procedimientos también se pueden aplicar durante un proceso de codificación, por ejemplo, al codificar utilizando los procedimientos que se enseñan en el documento Shokrollahi III para generar códigos sistemáticos a partir de códigos no sistemáticos.

[122] En algunos casos, es posible diseñar el proceso de codificación para que los procedimientos de decodificación de inactivación permanente sean especialmente efectivos. Por ejemplo, se sabe que la decodificación de propagación de creencias es eficaz en términos de cálculo siempre que pueda aplicarse, pero también se sabe que no puede proporcionar una decodificación de alta fiabilidad cuando se usa sola. Cuando se utiliza la decodificación de propagación de creencias dentro de la decodificación de inactivación OTF, las etapas de propagación de creencias pueden procesarse de manera muy eficaz, pero las etapas de inactivación OTF, intercaladas dentro de las etapas de propagación de creencias, pueden ralentizar la decodificación, y cuantas más etapas de inactivación OTF hay, más lento es el proceso de decodificación.

[123] En realizaciones típicas de decodificación de inactivación OTF, cuando se intenta despejar K + R variables desconocidas usando N + R valores de ecuación lineal, el número de etapas de inactivación OTF es habitualmente máximo cuando N = K, es decir, cuando se intenta despejar las variables usando sobrecarga cero. Por otro lado, según N crece más que K, es habitualmente el caso en que la complejidad de la decodificación de inactivación OTF disminuye debido a menos etapas de inactivación OTF, hasta que N sea lo suficientemente grande, por lo que en algunos casos no existen etapas de inactivación OTF, y la decodificación de inactivación es tan eficaz o casi, en términos de cálculo, como la decodificación de propagación de creencias. En otras realizaciones de decodificación de inactivación OTF, el número de inactivaciones OTF puede seguir siendo grande incluso cuando N es considerablemente mayor que K.

[124] En una realización preferida de decodificación de inactivación permanente, el número P de variables inactivadas permanentemente y la estructura de las ecuaciones lineales están diseñados de modo que cuando se despejan las L-P variables que no están inactivadas permanentemente usando la decodificación de inactivación OTF a partir de K+R valores de ecuaciones lineales, el número de etapas de inactivación OTF durante la decodificación de inactivación OTF es pequeño y, en algunos casos, cero y, por lo tanto, la etapa de decodificación de inactivación OTF es casi tan eficaz en términos de cálculo como la propagación de creencias.

[125] En realizaciones preferidas, la estructura de las ecuaciones lineales se diseña de manera que la fase de decodificación de inactivación OTF sea casi tan eficaz como la decodificación de propagación de creencias. En tales realizaciones preferidas, las relaciones de las variables inactivadas permanentemente para las ecuaciones lineales es tal que la fase de despejar las variables inactivadas, compuesta por las variables inactivadas permanentemente junto con cualquier variable inactivada OTF a partir de la fase de decodificación de inactivación OTF, puede realizarse eficazmente. Además, en realizaciones preferidas, la estructura de los símbolos permanentemente inactivados es tal que la fase de completar la solución de las variables que no están inactivadas a partir de las variables inactivadas despejadas es eficaz en términos de cálculo.

Decodificación de códigos de reacción en cadena con inactivación permanente

[126] La figura 12 ilustra una representación matricial de un conjunto de variables a despejar usando N símbolos o ecuaciones codificados recibidos y R símbolos o ecuaciones estáticos conocidos por el decodificador. La tarea del decodificador es resolver el sistema de ecuaciones lineales dado en esta figura. Habitualmente, los símbolos / ecuaciones están representados por valores almacenados en la memoria o el almacenamiento accesible por el decodificador y las operaciones matriciales descritas a continuación están implementadas por instrucciones ejecutables por el decodificador.

[127] La matriz que se muestra en la figura 12 comprende L = K + R columnas y N + R filas. La sub-matriz LT representa las relaciones entre los N símbolos codificados y los L-P símbolos LT de los L símbolos intermedios determinados por el proceso de codificación LT 251. La sub-matriz PI representa las relaciones entre los N símbolos codificados y los P símbolos PI de los L símbolos intermedios determinados por el proceso de codificación PI 241. La matriz SE de la ecuación 1 representa las relaciones entre los símbolos intermedios determinados por el codificador estático 210. El decodificador puede determinar estas relaciones basándose en las claves para los símbolos codificados recibidos y a partir de la construcción del código.

5

10

15

20

25

30

35

40

45

50

55

60

[128] El sistema de ecuaciones lineales de la figura 12 se resuelve mediante permutaciones de fila / columna de la matriz anterior, utilizando los procedimientos de inactivación OTF enseñados en el documento Shokrollahi II para transformarla en una forma mostrada en la figura 13. Comprende una matriz triangular inferior LO 310, un cierto número de columnas que comprende la matriz 320 (denominada OTFI) correspondiente a inactivaciones OTF, una matriz PI 330 correspondiente al conjunto de símbolos intermedios permanentemente inactivos o a un subconjunto de los mismos, y una matriz 340 EL correspondiente a símbolos codificados o estáticos no utilizados en el proceso de triangulación que conduce a la matriz LO.

[129] La figura 14 es un diagrama de bloques que describe elementos que podrían llevar a cabo un proceso que conduce a la matriz en la figura 12. Comprende un generador de matriz LT 347, un generador de matriz PI 349 y un generador de matriz estática 350. Al recibir las claves Ia, Ib, ... el generador de matrices LT crea la matriz LT en la figura 12, mientras que el generador matricial PI crea la matriz PI de la figura 12. La concatenación de estas dos matrices se remite al generador de matriz estática 350, que puede tomar como pistas adicionales las claves estáticas S_0, S_1, ... La tarea del generador de matriz estática es la creación de la matriz SE, y su salida es la matriz completa dada en la figura 12.

[130] Las operaciones del generador de matriz LT 347 y el generador de matriz PI 349 están estrechamente acopladas con las operaciones del codificador de LT 250 y el codificador de PI 240 en la figura 15, respectivamente. La operación del generador de matriz estática 350 es la recreación de la matriz SE de la ecuación 1, utilizada para la codificación estática.

[131] El generador de matriz LT 347, el generador de matriz PI 349 y el generador de matriz estática se describirán ahora en más detalle con referencia a las operaciones que podrían realizar.

[132] La figura 16 es un diagrama de flujo que ilustra una realización 500 de un procedimiento empleado por el generador de matriz LT 347. En la etapa 505, el generador de matriz LT 347 inicializa una matriz LT de formato N x (L-P) con todos ceros. A continuación, en la etapa 510, las claves Ia, Ib, ... se utilizan para generar las ponderaciones WL(0), ..., WL(N-1) y las listas AL(0), ..., AL(N -1), respectivamente. Cada una de las listas AL (i) comprende WL(i) enteros (j(0), ..., j(WL(i) -1)) en el rango 0, ..., L-P-1. En la etapa 515, estos enteros se usan para fijar las entradas LT(i, j(0)), ..., LT(i, j(WL(i) -1)) en 1. Como se ha explicado anteriormente, la matriz LT contribuye a un sistema de ecuaciones para las incógnitas (C(0), ..., C(L-1)) en términos de los símbolos recibidos (D(0), ..., D(N-1)).

[133] Como pueden apreciar los expertos en la técnica, la operación del generador de matriz LT, como se describe aquí, es similar a la operación del proceso de codificación LT 251 de la figura 6.

[134] La figura 17 es un diagrama de flujo que ilustra una realización 600 de un procedimiento empleado por el generador de matriz PI 349. En la etapa 610, el generador de matriz PI 349 inicializa una matriz PI de formato N x P con todos ceros. A continuación, en la etapa 615, las claves Ia, Ib, ... se utilizan para generar ponderaciones WP (0), ..., WP (N-1) y las listas ALP(0), ..., ALp(n- 1), respectivamente. Cada una de las listas aLp(í) comprende WP(i) enteros (j(0), ..., j(WP(i) -1)) en el rango 0, ..., P-1. En la etapa 620, estos enteros se usan para fijar las entradas PI(i,j(0)), ..., PI(i,j(WP(i) -1)) en 1. La operación del generador de matriz PI es similar a la operación del proceso de codificación PI 241 en la figura 5.

[135] Como se ha explicado anteriormente, las matrices LT y PI contribuyen a un sistema de ecuaciones con las incógnitas (C(0), ..., C(L-1)) en términos de los símbolos recibidos (D(0), ..., D(N -1)). La razón es la siguiente: una vez que el codificador LT elige la ponderación WL(i) y la lista asociada AL(i) = (j(0), ..., j(WL(i) -1)), y el codificador PI elige la ponderación WP( i) y la lista asociada ALP(i) = (t(0), ..., t(WP(i) -1)), el correspondiente símbolo codificado D(i) se obtiene como se muestra a continuación. Estas ecuaciones, acumuladas para todos los valores de i entre 0 y N-1, dan lugar al sistema de ecuaciones deseado, representado en la ecuación 2.

D(í) = C(¡(0))@ ... @C(j(WL<i>]))©C(t{0))e ... ®C(t(WP(i)-l» (Ec.2).

[136] Las ponderaciones WL se pueden calcular usando un procedimiento similar al que se da en la figura 7. Una persona medianamente experta en la materia, al revisar esta divulgación, vería cómo extender esto al caso donde hay más de dos codificadores, cada uno funcionando con una distribución de grados diferente.

[137] En la figura 18 se proporciona un diagrama de flujo ligeramente diferente de un generador de matriz. Comprende un generador de matriz LT 710, un generador de matriz estática 715 y un generador de matriz PI 720. Tras recibir las claves Ia, Ib, ..., el generador de matriz LT 710 crea la matriz LT ilustrada en la figura 15, mientras que el generador de matriz estática 715 crea la matriz SE ilustrada en la figura 15 y puede tomar las claves estáticas adicionales S_0 , S_1, ... como su entrada adicional. La concatenación de estas dos matrices se remite al generador de matriz PI 720 que crea la matriz PI. El funcionamiento del generador de matriz LT 710 puede ser exactamente el mismo que el funcionamiento del generador de matriz LT 347 detallado en la figura 16. El funcionamiento del

5

10

15

20

25

30

35

40

45

50

55

60

generador de matriz estática 715 puede ser diferente al funcionamiento del generador de matriz estática 350 en la figura 14. Específicamente, la figura 19 detalla una realización ejemplar de tal funcionamiento.

[138] En la etapa 725, la matriz SE se inicializa en 0. En la etapa 730, se proporciona una variable de entrada S, igual al número de símbolos de LDPC, al proceso, y los valores de SE(i,j) se fijan en 1 para los pares (i, j) cuando i = j mod S , i = (1+floor(j/S))+j mod S, o i = 2*(1+floor(j/S))+j mod S. En la etapa 735, las posiciones correspondientes a la matriz de identidad IS en la figura 9 se fijan en uno. En la etapa 740, las posiciones correspondientes a una matriz T se proporcionan como una entrada adicional a esta etapa. Esta matriz puede tener entradas en múltiples campos finitos y puede ser diferente para diferentes aplicaciones. Se puede elegir según los requisitos exigidos del código.

[139] La figura 20 es un diagrama de flujo simplificado que ilustra una realización de un procedimiento empleado por el generador de matriz PI 720. En la etapa 745, el generador de matriz PI 349 inicializa una matriz PI de formato (N+R) x P en todos ceros. A continuación, en la etapa 750, las claves I_a, I_b, ... se utilizan para generar las ponderaciones WP(0), ..., WP(N-1) y las listas ALP(0), ..., ALP(N-1), respectivamente. Cada una de las listas ALP(i) comprende WP(i) enteros (j(0), ..., j(WP(i) -1)) en el rango 0, ..., P-1. En la etapa 755, estos enteros se usan para fijar las entradas PI(i,j(0)), ..., PI(i,j(WP(i) -1)) en 1. El funcionamiento del generador de matriz PI en la figura 20 es similar al funcionamiento del generador de matriz PI de la figura 17, con la excepción de que este generador de matriz crea una matriz con R filas más y está estrechamente acoplado con la matriz en la figura 15.

[140] El sistema de ecuaciones en la figura 12 o en la figura 15 es habitualmente ralo, es decir, el número de entradas distintas de cero en las matrices implicadas es habitualmente mucho más pequeño que la mitad de las entradas posibles. En tal caso, las matrices podrían no necesitar ser almacenadas directamente, pero se puede almacenar una indicación que ayude a recrear cada entrada individual de estas matrices. Por ejemplo, para cada una de las filas de las matrices LT o PI, un proceso puede querer almacenar la ponderación y la lista de vecinos según lo calculado en las figuras 5 a 6. También son posibles otros procedimientos y muchos de ellos se han explicado en el presente documento o en las divulgaciones incorporadas en la presente memoria como referencia.

[141] Una vez que el generador de matriz ha creado un sistema de ecuaciones en la forma dada por la figura 12 o la figura 15, la tarea del decodificador es resolver este sistema para los valores desconocidos de C(0), ..., C(L- 1). Se pueden aplicar varios procedimientos diferentes para lograr este objetivo, incluyendo, pero sin limitarse a, la eliminación Gaussiana o cualquiera de los procedimientos descritos en los documentos Luby I, Luby II, Shokrollahi I, II, III, IV o V.

[142] Un posible procedimiento para resolver el sistema de ecuaciones en la figura 12 o la figura 15 se esboza ahora con referencia a las figuras 21 a 26. Un diagrama de flujo de una operación del decodificador de acuerdo a algunas de las realizaciones de la presente invención se proporciona en la figura 21. En la etapa 1305, la matriz de decodificación se crea usando alguno de los procedimientos descritos anteriormente. En la etapa 1310, esta matriz se reorganiza usando permutaciones de fila y columna. Como se ha mencionado anteriormente, dicha matriz se puede obtener a partir de cualquiera de las matrices en la figura 12 o la figura 15 aplicando permutaciones de fila y columna. La decodificación de reacción en cadena, en combinación con la decodificación de inactivación sobre la marcha del documento Shokrollahi II, se puede usar para lograr esto. Por lo tanto, hay permutaciones pi operando en el conjunto {0, 1, ..., L-1} y tau operando en el conjunto {0, 1, ..., N+R-1}, de modo que se cumpla la ecuación en la figura 22.

[143] Aquí, w indica el número de filas y columnas de la matriz LO en la figura 13, es decir, el número de símbolos intermedios que no están inactivados, ni permanentemente, ni OTF. En la etapa 1315, la matriz LO de la figura 13 se usa para poner en cero todas las entradas de la matriz LO por debajo de la diagonal. Al hacerlo, el conjunto de símbolos a la derecha de la ecuación de la figura 23 necesita respetar las mismas operaciones, de modo que el nuevo lado derecho del sistema de ecuaciones se obtenga mediante operaciones lógicas XOR de algunos de los D(tau(i)).

[144] Como se ilustra en la figura 24, después de esta operación, la matriz 810 se convierte en una matriz de identidad, la matriz EL en 840 quedará intacta y las matrices OTFI y PI cambiarán a OTFI-2 en 820 y a PI-2 en 830, porque el proceso de decodificación necesita realizar la operación lógica XOR conjuntamente sobre las filas de estas matrices, de acuerdo a las operaciones que fueron necesarias para reducir la matriz LO a la matriz de identidad.

[145] Una etapa siguiente del proceso de decodificación puede ser la etapa 1320, en la que se elimina el resto de la matriz restante por debajo de LO para obtener una matriz de la forma indicada en la figura 25. Indicando los valores permutados y reducidos de los símbolos originales D(0), ..., D(N_R-1) después de esta etapa con E(0), ..., E(N+R-1), con u el número de filas de la matriz EL_2 y con g el número de columnas de EL_2, la estructura de la matriz en la figura 25 da como resultado un sistema más pequeño de u ecuaciones lineales para los valores de C(pi(L-g)), ..., C(pi(L-1)) de acuerdo a la Ecuación 3.

5

10

15

20

25

30

35

40

45

50

55

imagen1

'EiN + R-up

*

¿(N + R-1),

Ec. 3

[146] Un proceso de decodificación como el descrito en la figura 21 puede resolver este sistema de ecuaciones en la etapa 1330 por varios medios, por ejemplo, usando un proceso de eliminación Gaussiana, o una combinación de codificación de reacción en cadena y eliminación Gaussiana, o por otra aplicación de la decodificación de inactivación, o por otros medios. La eliminación Gaussiana puede modificarse a fin de separar cálculos en GF(2) de aquellos en campos más grandes, como GF(256), si la matriz EL tiene elementos que pertenecen a múltiples campos, como se enseñó en el documento Shokrollahi IV, por ejemplo.

[147] Si el sistema de ecuaciones en la ecuación 3 no es resoluble utilizando los procesos empleados por el decodificador, entonces el decodificador puede aplicar contramedidas en la etapa 1335. Tales contramedidas podrían incluir marcar un error y detener el proceso, o podrían incluir la solicitud de más símbolos codificados, o podrían detener el proceso y devolver a la aplicación, usando el decodificador, una lista de símbolos intermedios o símbolos de origen que ha sido capaz de recuperar hasta ahora. Si el sistema es resoluble, entonces el decodificador puede recuperar los valores de los símbolos intermedios inactivados C(pi(L-g)), ..., C(pi(L-1)). En algunas variantes, puede ser también que algunos otros símbolos intermedios, además de los símbolos intermedios inactivados, se recuperen en la etapa 1330.

[148] Una vez que se recuperan los valores de estos símbolos, el decodificador avanza a la etapa 1340 que implica una retro-sustitución. La recuperación de los valores de C(pi(L-g)), ..., C(pi(L-1)) da como resultado un sistema de ecuaciones del tipo dado en la figura 26. Este sistema es más fácil de resolver que un sistema general. Por ejemplo, un decodificador puede usar el proceso indicado en la figura 23 para hacerlo. El proceso de obtención del primer vector en el lado derecho de la figura 23 se puede denominar retro-sustitución, ya que es el proceso de sustitución de los valores de los símbolos conocidos en el sistema de ecuaciones. Como puede ver una persona medianamente experta en la técnica después de leer esta divulgación, los sistemas dados en las figuras 23 y 26 son matemáticamente equivalentes.

[149] En la figura 23, el decodificador obtiene los valores desconocidos C(pi(0)), ..., C(pi(L-g-1)) implementando un proceso en el que las entradas de la matriz en el lado derecho se multiplican por las entradas del vector ya despejado C(pi(L-g)), ..., C(pi(L-1)) usando las reglas de la multiplicación matricial y realizando la operación lógica XOR de las entradas obtenidas con E(0), .. ., E(L-g-1). El proceso de realizar la operación lógica XOR de las entradas obtenidas con E(0), ..., E(L-g-1) y así recuperar los valores de C(pi(0)), ..., C(pi(L-g-1)) comprende la etapa 1345 del decodificador en la figura 21.

[150] Aunque es útil en algunas aplicaciones, este procedimiento puede conducir a una gran sobrecarga de cálculo en algunas realizaciones preferidas, ya que la matriz en el lado derecho de la figura 23, habitualmente, no es rala y, por lo tanto, para obtener uno de los elementos C(pi(j)) se debe realizar un cierto número de operaciones lógicas XOR que es proporcional a g. En algunas realizaciones, este número puede ser grande, por ejemplo, porque el número P de inactivaciones permanentes se eligió grande para empezar, y g puede ser al menos tan grande como P. Esto puede poner limitaciones severas sobre el valor de P, el número de símbolos permanentemente inactivados y, si se usa un valor más pequeño de P, entonces esto podría conducir a un aumento en el número de símbolos intermedios inactivados OTF.

[151] La figura 27 describe un proceso de decodificación modificado que puede ser más eficaz en términos de cálculo que el proceso descrito en la figura 21. Las etapas 1405 a 1435 de este proceso pueden ser las mismas que las etapas correspondientes del proceso en la figura 14. Optativamente, este proceso puede mantener una copia de la matriz original en la figura 12 o la figura 15, o partes relevantes de esta matriz, así como los símbolos originales D(0), ..., D(N+R-1) en una ubicación de memoria adicional para uso futuro. Esto no es necesario para el funcionamiento de este proceso, pero puede conducir a mayores ventajas de velocidad si la aplicación tiene suficientes recursos de memoria para guardar estas copias. Alternativamente, el proceso solo puede conservar una copia de los símbolos originales D(0), ..., D(N + R-1) y no la matriz, y volver a crear la matriz cuando la necesite. La etapa 1440 usa la copia almacenada de la matriz o deshace el proceso en la etapa 1415 para obtener de vuelta el sistema original de ecuaciones en la figura 22, o solo la parte superior de este sistema dado en la figura 28. En este momento, la matriz 1510 dada en la figura 29 es rala, y los valores C(pi(w)), ..., C(pi(L-1)) son conocidos, donde w =

L-g.

[152] Como es bien sabido, el lado derecho de la ecuación en la figura 29 se puede calcular mediante un proceso eficaz en términos de cálculo que implica un pequeño número de operaciones lógicas XOR de símbolos, es decir, igual al número de entradas distintas de cero en la matriz OTFI más el número de entradas distintas de cero en la

5

10

15

20

25

30

35

40

45

50

55

60

65

matriz PI. Esta etapa del proceso se indica por 1445 en la figura 27. Después de completar esta etapa, se ha calculado el lado derecho de la ecuación en la figura 29, y se debe resolver un sistema de ecuaciones en el que las incógnitas son los valores de C(pi(0)), ..., C(pi(w-1)). Este sistema puede resolverse en la etapa 1450 usando la decodificación de reacción en cadena, ya que la matriz LO triangular inferior en el lado derecho es rala, es decir, el número de operaciones lógicas XOR de símbolos para resolver este sistema de ecuaciones es igual al número de entradas distintas de cero en la matriz LO y este número es habitualmente mucho más pequeño que w*w, la cantidad máxima de entradas posibles distintas de cero.

Elección del número de inactivaciones permanentes

[153] La elección del número de inactivaciones permanentes puede afectar al rendimiento general, por lo que puede ser importante. Por un lado, este número debe elegirse lo más grande posible: si este número es grande, entonces el número de inactivaciones OTF se puede reducir a un número muy pequeño, a veces incluso cero. Esto se debe a que la combinación de las matrices LT y SE en la figura 15 (o sus variantes correspondientes en la figura 23) es efectivamente la matriz de decodificación de un código de reacción en cadena con una gran sobrecarga. Este hecho hace que el número de inactivaciones de OTF sea muy pequeño. Las inactivaciones de OTF pueden ser más difíciles de gestionar en ciertas realizaciones, por lo tanto, reducir su número puede conducir a ventajas en términos de velocidad y / o memoria.

[154] Por otro lado, aumentar el número de inactivaciones permanentes puede tener un efecto adverso en el tiempo de ejecución: por ejemplo, la etapa 1330 en el proceso de decodificación de la figura 21, y la etapa correspondiente 1430 en el proceso de la figura 27, requieren resolver un sistema de ecuaciones que tiene al menos P filas y columnas. Una forma de hacerlo sería identificar una sub-matriz invertible de la matriz EL-2 en la figura 25, invertir esa matriz y usar la matriz invertida para obtener los valores de los símbolos intermedios C(pi(L-g-1)). ..., C(pi(L-1)). Dado que la matriz EL-2 puede no ser rala en muchas de las realizaciones, la obtención de los valores de los símbolos intermedios puede incurrir en el orden de g veces g las operaciones lógicas XOR de símbolos. Como g es al menos P, el número de las operaciones lógicas XOR de símbolos puede ser al menos P veces P, por lo que si el número total de las operaciones lógicas XOR de símbolos se debe mantener lineal en K, una buena opción es fijar el número P para que sea proporcional a la raíz cuadrada de K. La realización específica del Apéndice A elige que P sea del orden de 2,5*sqrt (K) y se mantiene en línea con esta observación. Esta es una buena opción para P, ya que con esta opción de P, normalmente el número de inactivaciones OTF es bastante pequeño, variando desde alrededor de P hasta muy cerca de, o igual a, cero.

[155] Otra cantidad de interés es el número promedio, I, de vecinos de símbolos intermedios inactivados que hay para un símbolo codificado, o para un símbolo estático. La etapa 1445 del proceso de decodificación en la figura 27 puede necesitar tantas como I operaciones lógicas XOR de símbolos en promedio por símbolos intermedios no recuperados para cumplir esta etapa. Si I es grande, entonces este número de operaciones lógicas XOR puede ser demasiado para la memoria y los recursos de cálculo de los procesos que ejecutan la decodificación o el proceso de codificación. Por otro lado, si I es demasiado pequeño, entonces la matriz EL-2 de la figura 25 puede no tener rango completo, y la capacidad de decodificación puede verse comprometida.

[156] Un análisis más detallado revela que un aspecto importante de la inactivación permanente es hacer que la matriz PI de la figura 15 se comporte de tal manera que las columnas sean linealmente independientes entre sí, es decir, que la matriz tenga rango completo tanto como sea posible. Es bien sabido por los expertos en la técnica que si PI es una matriz binaria aleatoria, entonces se puede lograr un rango completo hasta los límites posibles. Por otro lado, PI puede tener, en promedio en cada columna, una fracción de unos que es inversamente proporcional a la raíz cuadrada de K y satisfacer todavía las mismas propiedades de rango que las de una matriz puramente aleatoria. Por esta razón, la realización específica en el Apéndice A elige que I sea un número entre 2 y 3, y así, con la opción de P proporcional a la raíz cuadrada de K, esto significa que el número de unos en cada columna de PI es en promedio inversamente proporcional a la raíz cuadrada de K.

[157] Existen muchas variantes de estos procedimientos, como reconocerá un experto en la materia al leer esta divulgación. Por ejemplo, el operador lógico XOR puede ser reemplazado por otros operadores, por ejemplo, operadores lineales sobre campos finitos más grandes, o los operadores pueden ser una mezcla de diferentes operadores, por ejemplo, algunos operadores lineales sobre campos finitos más grandes para algunas operaciones y otros operadores lineales sobre campos finitos pequeños más grandes para otras operaciones.

Ejemplo específico con referencia al Apéndice A

[158] Como se ha detallado anteriormente, sin inactivaciones permanentes (es decir, decisiones predeterminadas sobre qué símbolos codificados no serían parte de una manipulación matricial que sería parte de la determinación de una secuencia para una decodificación de reacción en cadena), el número de inactivaciones OTF podría ser bastante aleatorio y causar problemas potenciales en términos de consumo de memoria. Cuando el número de símbolos de origen es muy grande y la sobrecarga es muy pequeña, la probabilidad de error puede estar inaceptablemente cercana a 1.

5

10

15

20

25

30

35

40

45

50

55

60

65

[159] Debido a la alta probabilidad de error para pequeñas sobrecargas, puede ser cada vez más difícil encontrar buena información sistemática cuando el número de símbolos de origen es grande. Aquí, la información sistemática se refiere a la información necesaria a proporcionar al codificador y al decodificador a fin de poder construir un código sistemático en el sentido del documento Shokrollahi III. Además, cada vez que se obtiene información sistemática, es de esperar que el comportamiento del código esté muy lejos de su comportamiento promedio, porque en "promedio" el código debería fallar en sobrecarga cero.

[160] Algunos de los parámetros para la construcción de un código de reacción en cadena con inactivación permanente pueden incluir la distribución de grados O utilizada para el codificador LT 250 de la figura 4, los parámetros para el codificador PI 240, la determinación del número de símbolos permanentemente inactivados, la determinación del número de símbolos estáticos redundantes y su estructura, y la manera particular en que se pueden generar y compartir números aleatorios entre el codificador 115 y el decodificador 155 en la figura 1.

Codificadores y decodificadores que usan el código RQ

[161] Una realización preferida de un código, denominado en lo sucesivo "el código RQ", que utiliza los procedimientos descritos en este documento, se especifica con gran detalle en la Sección 5 del Apéndice A. El resto del Apéndice A describe un procedimiento para aplicar el código RQ a la entrega fiable de objetos a través de redes de difusión o multidifusión.

[162] El código RQ utiliza los procedimientos descritos anteriormente y posteriormente para implementar un código sistemático, lo que significa que todos los símbolos de origen se encuentran entre los símbolos codificados que se pueden generar, y por tanto los símbolos codificados pueden considerarse una combinación de los símbolos de origen originales y los símbolos de reparación generados por el codificador.

[163] Aunque algunos de los códigos anteriores tienen buenas propiedades, hay algunas mejoras que aumentarían su aplicación práctica. Dos posibles mejoras de importancia son una curva de fallos de sobrecarga más pronunciada y una mayor cantidad de símbolos de origen con soporte por bloque de origen. La sobrecarga es la diferencia entre el número de símbolos codificados recibidos y el número de símbolos de origen en el bloque de origen, por ejemplo, una sobrecarga de 2 significa que se reciben K+2 símbolos codificados para decodificar un bloque de origen con K símbolos de origen. La probabilidad de falla en una sobrecarga dada es la probabilidad de que el decodificador no logre recuperar completamente el bloque de origen cuando el número de símbolos codificados recibidos corresponde a esa sobrecarga. La curva de falla de sobrecarga es un gráfico de cómo la probabilidad de falla disminuye en función del aumento de la sobrecarga, comenzando en la sobrecarga cero. Una curva de falla de sobrecarga es mejor si la probabilidad de falla del decodificador desciende rápidamente o de manera abrupta como función de la sobrecarga.

[164] Un código binario aleatorio tiene una curva de probabilidad de falla de sobrecarga donde la probabilidad de falla cae esencialmente en un factor de dos para cada símbolo de sobrecarga adicional, con complejidad de cálculo inviable, pero el tema de la exposición actual se limita a la curva de probabilidad de falla de sobrecarga, y no a la complejidad de cálculo). En algunas aplicaciones, esta es una curva de falla de sobrecarga suficiente, pero para algunas otras aplicaciones, se prefiere una curva de falla de sobrecarga más pronunciada. Por ejemplo, en una aplicación de transmisión por flujo, el rango del número de símbolos de origen en un bloque de origen puede ser amplio, por ejemplo, K = 40, K = 200, K = 1.000, K = 10.000. Para proporcionar una buena experiencia de transmisión por flujo, puede requerirse que la probabilidad de falla sea baja, por ejemplo, una probabilidad de falla de 10-5 o 10-6. Dado que el ancho de banda a menudo es un bien escaso para las aplicaciones de transmisión por flujo, el porcentaje de símbolos de reparación enviados como una fracción de los símbolos de origen debería minimizarse. Supongamos, por ejemplo, que la red a través de la cual se envía el flujo debería estar protegida contra una pérdida de paquetes de hasta el 10% cuando se usan bloques de origen con K = 200, y que se requiere que la probabilidad de falla sea como máximo 10-6. Un código binario aleatorio requiere una sobrecarga de al menos 20 para lograr una probabilidad de falla de 10-6, es decir, el receptor necesita 220 símbolos codificados para decodificar con esta probabilidad de falla. Es necesario enviar un total de 245 símbolos codificados para que cada bloque de origen cumpla con los requisitos, dado que ceil(220/(1 -0,1)) = 245. Por lo tanto, los símbolos de reparación agregan un 22,5% extra a los requisitos de ancho de banda para el flujo.

[165] El código RQ descrito en la presente memoria y en la Sección 5 del Apéndice A logra una probabilidad de falla que es menor que 10"2, 10"4 y 10"6 para las sobrecargas generales 0, 1 y 2, respectivamente, para valores de K = K' para todos los valores con soporte de K' y para valores de K = 1 y K = K' + 1 para todos menos el valor final con soporte de K. Se han realizado pruebas para unas varias probabilidades de pérdida, por ejemplo, probabilidades de pérdida del 10%, 20%, 50%, 70%, 90% y 95%.

[166] Para el ejemplo anterior, utilizando el código RQ, una sobrecarga de 2 es suficiente para lograr una probabilidad de falla de 10-6 y, por lo tanto, solo deben enviarse un total de 225 símbolos codificados por cada bloque de origen, para cumplir los requisitos, dado que ceil(202/(1 -0,1)) = 225. En este caso, los símbolos de reparación agregan un 12.5% adicional a los requisitos de ancho de banda para el flujo, es decir, un 10% menos de sobrecarga de ancho de banda que lo requerido por un código binario aleatorio. Por lo tanto, la curva de fallas de

5

10

15

20

25

30

35

40

45

50

55

60

65

sobrecarga mejorada del código RQ tiene algunas consecuencias prácticas muy positivas.

[167] Hay aplicaciones en las que es deseable el soporte para una gran cantidad de símbolos de origen por bloque de origen. Por ejemplo, en una aplicación móvil de difusión de ficheros, es ventajoso, desde el punto de vista de la eficacia de la red, codificar el fichero como un solo bloque de origen o, más generalmente, dividir el fichero en tan pocos bloques de origen como sea práctico. Supongamos, por ejemplo, que se va a difundir un fichero de 50 millones de octetos y que el tamaño disponible dentro de cada paquete para transportar un símbolo codificado es de mil octetos. Para codificar el fichero como un único bloque de origen, se requiere soporte para un valor de K = 50.000. (Téngase en cuenta que existen técnicas de sub-bloqueo, como se ha descrito anteriormente, que permiten la decodificación utilizando significativamente menos memoria).

[168] Hay unas pocas razones por las cuales la cantidad de símbolos de origen con soporte para un código podría estar limitada. Una razón típica es que la complejidad de cálculo se vuelve irracional a medida que aumenta K, como en el caso de los códigos de Reed-Solomon, pero este no es el caso para códigos tales como los códigos de reacción en cadena. Otra razón podría ser que la probabilidad de falla en sobrecarga cero aumenta hasta casi 1 a medida que K aumenta, haciendo que sea más difícil encontrar índices sistemáticos que produzcan una buena construcción sistemática de código. La probabilidad de falla en sobrecarga cero puede dictaminar la dificultad de obtener una buena construcción de código, porque esta es esencialmente la probabilidad de que, cuando se elige aleatoriamente un índice sistemático, la construcción de código sistemática resultante tenga la propiedad de que los primeros K símbolos codificados puedan decodificar los K símbolos de origen.

[169] Como la curva de falla de sobrecarga para el diseño del código RQ es tan pronunciada para todos los valores de K, es posible encontrar fácilmente buenos índices sistemáticos y, por lo tanto, dar soporte a valores mucho mayores de K. El código RQ, según se describe en la Sección 5 del Apéndice A, presta soporte a valores de K hasta 56.403, y también presta soporte a un número total de símbolos codificados de hasta 16.777.216 por bloque de origen. Estos límites en los valores con soporte para el código RQ se establecieron debido a consideraciones prácticas basadas en los requisitos de aplicación percibidos, y no debido a las limitaciones del diseño del código RQ. Otras realizaciones más allá de las mostradas en el Apéndice A podrían tener valores diferentes.

[170] El código RQ limita el número de diferentes tamaños de bloques de origen con soporte, de la siguiente manera. Dado un bloque de origen con símbolos de origen K a codificar o decodificar, se selecciona un valor K' basándose en la tabla que se muestra en la Sección 5.6 del Apéndice A. La primera columna en la tabla enumera los valores posibles para K'. El valor de K' seleccionado es el valor más pequeño entre las posibilidades, tal que K < K'. Los K símbolos de origen C'(0), ..., C'(K-1) se rellenan con los K'-K símbolos C'(K), ..., C'(K'-1), con valores fijados en ceros para producir un bloque de origen que comprende K' símbolos de origen C'(0), ..., C'(K'-1), y luego la codificación y la decodificación se realizan en este bloque de origen rellenado.

[171] El enfoque anterior tiene la ventaja de reducir el número de índices sistemáticos que necesitan soporte, es decir, solo unos pocos cientos en lugar de decenas de miles. No hay ninguna desventaja en términos de la probabilidad de falla de sobrecarga para K, ya que es la misma que la de la curva de falla de sobrecarga para el K' seleccionado: Dado el valor de K, el decodificador puede calcular el valor de K ', y fijar los valores de C'(K), ..., C'(K'- 1) en ceros y, por lo tanto, solo tiene que decodificar los K restantes entre los K' símbolos de origen del bloque de origen. Las únicas desventajas potenciales son que podría necesitarse un poco más de memoria o de recursos de cálculo para codificar y decodificar con un poco más de símbolos de origen. Sin embargo, la separación entre valores consecutivos de K ' es aproximadamente del 1% para valores mayores de K' y, por lo tanto, la desventaja potencial es insignificante.

[172] Debido al relleno del bloque de origen, de K a K ', el identificador para los símbolos codificados C'(0), C'(1), ... dentro del código RQ se llama Identificador de Símbolo Interno, abreviado como ISI, donde C'(0), ..., C'(K'-1) son los símbolos de origen y C'(K'), C'(K' + 1), ... son los símbolos de reparación.

[173] Las aplicaciones externas que emplean el codificador y el decodificador utilizan un identificador de símbolo codificado, también llamado Identificador de Símbolo de Codificación, abreviado como ESI, que va de 0 a K-1 para identificar los símbolos de origen originales C'(0), ..., C'(K-1) y que continúa con K, K+1, ... para identificar los símbolos de reparación C'(K'), C'(K' + 1), ... Por lo tanto, un símbolo de reparación C'(X) identificado con un ISI X dentro del código RQ se identifica externamente con un ESI X- (K'-K). Esto se describe con más detalle en la Sección 5.3.1 del Apéndice A.

[174] La codificación y decodificación para los códigos RQ está definida por dos tipos de relaciones: las relaciones de restricción entre los símbolos intermedios y las relaciones LT-PI entre los símbolos intermedios y los símbolos codificados. Las relaciones de restricción corresponden a las relaciones entre los símbolos intermedios definidos por la matriz SE como, por ejemplo, se muestra en la figura 12 o la figura 15. Las relaciones LT-PI corresponden a las relaciones entre los símbolos intermedios y los símbolos codificados definidos por la matriz LT y la matriz PI como se muestra, por ejemplo, en la figura 12 o la figura 15.

[175] La codificación prosigue determinando los valores de símbolos intermedios en función de: (1) los valores de

5

10

15

20

25

30

35

40

45

50

55

60

65

símbolos de origen; (2) relaciones LT-PI entre los símbolos de origen y los símbolos intermedios; y (3) las relaciones de restricción entre los símbolos intermedios. Los valores de los símbolos de reparación se pueden generar a partir de los símbolos intermedios basándose en las relaciones LT-PI entre los símbolos intermedios y los símbolos de reparación.

[176] De forma similar, la decodificación prosigue determinando los valores de símbolos intermedios basándose en: (1) los valores de símbolos codificados recibidos; (2) relaciones LT-PI entre los símbolos codificados recibidos y los símbolos intermedios; y (3) las relaciones de restricción entre los símbolos intermedios. Los valores de los símbolos de origen faltantes se pueden generar a partir de los símbolos intermedios basándose en las relaciones LT-PI entre los símbolos intermedios y los símbolos de origen faltantes. Por lo tanto, la codificación y la decodificación son procedimientos esencialmente simétricos.

Componentes de hardware ejemplares

[177] Las figuras 30 a 31 ilustran diagramas de bloques de hardware que podrían usarse para implementar los procedimientos descritos anteriormente. Cada elemento puede ser hardware, código de programa o instrucciones ejecutadas por un procesador de propósito general o personalizado, o una combinación.

[178] La figura 30 ilustra un sistema de codificación ejemplar 1000, que podría implementarse como módulos de hardware, módulos de software o partes de código de programa almacenado en un almacén de programas 1002 y ejecutado por un procesador 1004, posiblemente como una unidad colectiva de código no independiente, como se muestra en la figura. El sistema de codificación 1000 recibe una señal de entrada, que transmite símbolos de origen e información de parámetros, y emite una señal que transmite esa información.

[179] Una interfaz de entrada 1006 almacena los símbolos de origen entrantes en una memoria intermedia de símbolos de origen 1008. Un generador de símbolos de origen a intermedios 1010 genera símbolos intermedios a partir de los símbolos de origen. Esto puede ser una vía de paso en algunas realizaciones y un módulo decodificador en otras realizaciones (tal como una realización "sistemática").

[180] Un generador de símbolos redundantes 1012 genera símbolos redundantes a partir de los símbolos de origen. Esto puede implementarse como un codificador de reacción en cadena, un codificador de LDPC, un codificador de HDPC o similares. Un inactivador 1014 recibe los símbolos de origen, los símbolos intermedios y / o los símbolos redundantes, según sea el caso, y almacena algunos de ellos, los símbolos permanentemente inactivados, en una memoria intermedia PI 1018 y proporciona los otros a un codificador de salida 1016. Este proceso podría ser realizado lógicamente, en lugar de físicamente.

[181] Un operador 1020, tal como un operador XOR, opera sobre uno o más símbolos codificados procedentes del codificador de salida 1016 (uno, en ciertas realizaciones) y uno o más de los símbolos PI procedentes de la memoria intermedia PI 1018 (uno, en ciertas realizaciones), y el resultado de la operación se proporciona a una interfaz de transmisión 1030 que emite la señal desde el sistema 1000.

[182] La figura 31 ilustra un ejemplo de sistema de decodificación 1100, que podría implementarse como módulos de hardware, módulos de software o partes de código de programa almacenado en un almacén de programas 1102 y ejecutado por un procesador 1104, posiblemente como una unidad colectiva de código no independiente, como se muestra en la figura. Algún proceso podría ser implementado lógicamente, más que físicamente.

[183] El sistema de decodificación 1100 toma una señal de entrada y posiblemente otra información, y genera datos de origen, si es capaz de hacerlo. La señal de entrada se proporciona a una interfaz de recepción 1106 que almacena los símbolos recibidos en una memoria intermedia 1108. Los ESI de los símbolos recibidos se proporcionan a un generador de matriz 1110 que genera matrices como se ha descrito en la presente memoria, en dependencia de los símbolos particulares recibidos, y almacena los resultados en una memoria de matriz 1112.

[184] Un planificador 1114 puede leer detalles de la matriz desde la memoria de matriz 1112 y genera una planificación, almacenada en una memoria de planificación 1016. La planificación 1114 también podría generar una señal de terminación y transmitir una matriz PI a un solucionador PI 1118 cuando se complete. El solucionador PI 1118 proporciona valores de símbolos PI despejados a un solucionador 1120, que también utilizó la planificación, para decodificar los símbolos intermedios a partir de los símbolos, la planificación y los símbolos PI recibidos.

[185] Los símbolos intermedios se proporcionan a un generador de símbolos intermedios a símbolos de origen 1122, que podría ser un codificador o vía de paso. La salida del generador de símbolos intermedios a símbolos de origen 1122 se proporciona a una interfaz de salida 1124 que emite los datos de origen, o qué datos de origen están disponibles para la salida.

Otras Consideraciones

[186] En ciertas situaciones, podría ser necesario mejorar la capacidad de decodificación. En ejemplos

5

10

15

20

25

30

35

40

45

50

55

60

65

proporcionados en otra parte en el presente documento, aunque los símbolos codificados tenían tanto vecinos LT como vecinos PI, los símbolos de lDpC solo tenían vecinos lT o vecinos PI, que no estaban entre los símbolos de HDPC. En algunos casos, la capacidad de decodificación mejora si los símbolos de LDPC también tienen vecinos PI que incluyen los símbolos de HDPC. Con vecinos entre todos los símbolos PI, incluidos los símbolos HDPC, el valor de decodificación de los símbolos de LDPC podría ser más similar al de los símbolos codificados. Como se explica en otra parte en el presente documento, los símbolos que dependen de los símbolos LT (que pueden ser fáciles de codificar y decodificar) y también dependen de los símbolos PI, incluidos los símbolos de HDPC (que pueden proporcionar decodificación de alta fiabilidad), de modo que ambas ventajas pueden estar presentes.

[187] En un ejemplo, cada símbolo de LDPC tiene dos vecinos PI, es decir, el valor de un símbolo de LDPC depende de los valores de dos símbolos PI.

[188] La capacidad de decodificación también puede mejorarse, en algunas situaciones, reduciendo las apariciones de símbolos codificados duplicados, donde dos símbolos codificados son duplicados si tienen exactamente el mismo conjunto vecino general, donde el conjunto vecino general para un símbolo codificado está compuesto por el conjunto vecino LT y el conjunto vecino PI. Los símbolos codificados duplicados con el mismo conjunto global de vecinos llevan exactamente la misma información sobre el bloque de origen intermedio desde el que se generaron, y por lo tanto no hay mejor oportunidad de decodificación por haber recibido más de un símbolo codificado duplicado que por haber recibido uno de los símbolos duplicados codificados, es decir, la recepción de más de un símbolo duplicado se suma a la sobrecarga de recepción y solo uno de los símbolos codificados entre los duplicados es útil para la decodificación.

[189] Una propiedad preferible es que cada símbolo codificado recibido no sea un duplicado de ningún otro símbolo codificado recibido, ya que esto significa que cada símbolo codificado recibido puede ser útil para la decodificación. Por lo tanto, podría preferirse reducir el número de tales duplicaciones o reducir la probabilidad de ocurrencia de duplicados.

[190] Un enfoque es limitar el número de vecinos LT que puede tener cada símbolo codificado. Por ejemplo, si hay W vecinos posibles, la cantidad máxima de vecinos podría estar limitada a W-2. Esto reduce la posibilidad de que los conjuntos de vecindario generales se dupliquen, en algunos casos, porque el conjunto de vecindario que comprende todos los W posibles vecinos no sería permitido. Donde la restricción es Grado [v] = min (d, W-2), hay W * (W-1) / 2 conjuntos de vecindario diferentes de grado W-2. Por lo tanto, puede ser menos probable que se generen conjuntos de vecinos generales duplicados para símbolos codificados. En cambio, podrían usarse otras restricciones, tales como min (d, W-Wg) para algún Wg distinto a Wg = 2, o alguna otra restricción.

[191] Otra técnica, que puede usarse sola o con la técnica anterior de reducción de duplicados, es elegir más de un vecino PI para cada símbolo codificado, de modo que sea menos probable que haya vecinos PI duplicados para símbolos codificados y, por lo tanto, menos probable que se generen conjuntos vecinos generales duplicados para símbolos codificados. Los vecinos PI se pueden generar de maneras similares a como se generan los vecinos LT, por ejemplo, generando primero un (d1, a1, b1), como se muestra en el Apéndice A, Sección 5.3.5.4, de acuerdo al siguiente fragmento de código:

si (d < 4) entonces {d1 = 2 + Azar [y, 3, 2]}; en caso contrario {d1 = 2}; al = 1 + Azar [y, 4, P1-1]; b1 = Azar [y, 5, P1];

[192] Téngase en cuenta que, en este ejemplo, hay una distribución de grados aleatoria no trivial, definida sobre el número d1 de vecinos PI y esa distribución depende del número d elegido de vecinos LT, y es probable que el número de vecinos PI sea mayor cuando el número de vecinos LT es más pequeño. Esto brinda la propiedad de que el grado global del símbolo codificado sea tal que reduzca la posibilidad de que se generen y, por tanto, se reciban símbolos codificados duplicados.

[193] El valor del símbolo codificado se podría generar utilizando los vecinos definidos por (d1, a1, b1), como se muestra en el Apéndice A, Sección 5.3.5.3, y por el siguiente fragmento de código:

mientras (b1> = P) hacer {b1 = (b1 + a1)% P1};

resultado = resultados A C [W + b1];

Para j = 1, ..., d1-1 hacer

b1 = (b1 + a1)% P1;

mientras (b1> = P) hacer {b1 = (b1 + a1)% P1};

5

10

15

20

25

30

35

40

45

50

55

60

65

resultado = resultados A C [W + b1];

Devolver resultado;

[194] Para sustentar estas características de capacidad de decodificación o, por separado, para proporcionar capacidad de decodificación, podría utilizarse un índice sistemático diferente J(K') para los valores de K', tal como el que se muestra en la Tabla 2 de la Sección 5.6 en el Apéndice A.

[195] Un ejemplo de un proceso que es realizable en un sistema de transmisión y / o recepción para generar el índice sistemático J(K ') se ilustra de la siguiente manera. Para cada K' en la lista de posibles K', un proceso que podría realizarse, normalmente mediante un circuito o procesador adecuadamente programado, es verificar la idoneidad de varios índices. Por ejemplo, el circuito / procesador podría verificar, para J = 1 ... 1000 [o algún otro límite], si se cumplen los siguientes criterios con respecto al posible índice sistemático J:

(a) ¿Es posible la decodificación en sobrecarga cero a partir de los K' símbolos de origen?

En caso afirmativo, registrar la cantidad de inactivaciones sobre la marcha

(b) ¿Hay conjuntos vecinos generales duplicados entre los primeros K'/ 0,06 símbolos codificados posibles (con los ESI 0, ..., K' / 0,06)? [Se podrían usar otros umbrales en cambio.]

(c) ¿Está la probabilidad de falla de decodificación por debajo de 0,007 [o algún otro umbral] cuando se decodifica utilizando los primeros K' símbolos codificados recibidos dentro de 10,000 series [o alguna otra prueba] cuando cada símbolo codificado se pierde con probabilidad 0,93 [o algún otro umbral] en cada serie, independientemente de los otros símbolos codificados?

[196] El circuito / procesador luego elige entre los posibles índices sistemáticos J que satisfacen los criterios (a), (b) y (c) anteriores, eligiendo el índice sistemático que registró un número promedio de inactivaciones sobre la marcha en la etapa (a).

[197] Téngase en cuenta que hay muchas variaciones de los criterios de selección anteriores. Por ejemplo, en algunos casos podría ser preferible elegir el índice sistemático que satisfaga (a), (b) y (c) más arriba y que produzca el mínimo número de fallas de decodificación en la etapa (c) dentro del número especificado de series. Como otro ejemplo, una combinación del número de inactivaciones sobre la marcha y de la probabilidad de falla de decodificación se podría tener en cuenta al elegir un índice sistemático. Como otro ejemplo, podrían estar disponibles múltiples índices sistemáticos para cada valor K', y luego uno de ellos se elige al azar dentro de aplicaciones particulares.

[198] Los índices sistemáticos para los K' valores enumerados en la Tabla 2 en la Sección 5.6 del Apéndice A son una lista potencial de índices sistemáticos para el código descrito en el Apéndice A.

Variaciones de un proceso de sub-bloqueo

[199] El bloqueo secundario, que divide los bloques en unidades más pequeñas, física o lógicamente, para su posterior procesamiento, se conoce para diversos fines. Por ejemplo, se usa en el documento IETF RFC 5053. También se conoce a partir de la Patente Estadounidense N° 7.072.971. Uno de los principales usos del procedimiento de sub-bloqueo es permitir que un gran bloque de datos sea protegido como una entidad única mediante un código de FEC, mientras que al mismo tiempo se utiliza una cantidad de memoria mucho menor que el tamaño del bloque de datos en un receptor para recuperar el bloque de datos usando un decodificador de FEC.

[200] Un procedimiento para elegir el número de sub-bloques descrito en el documento IETF RFC 5053 proporciona una buena partición de bloques de origen y una partición de sub-bloques para muchas configuraciones razonables de parámetros, pero puede producir una solución en algunas circunstancias que puede no satisfacer estrictamente una cota superior sobre el tamaño de sub-bloque WS (aunque incluso en estos casos produce soluciones donde el tamaño de sub-bloque es un factor modesto mayor que la restricción dada WS en el tamaño de sub-bloque). Como otro ejemplo, en draft-luby-rmt-bb-fec-raptorg-object-00 (donde el número máximo de símbolos de origen en un bloque de origen es mucho mayor que en el documento IETF RFC 5053), en la Sección 4.2, se proporciona la siguiente receta para calcular T, Z y N, donde T es el tamaño del símbolo, Z es el número de bloques de origen en los que el fichero (o bloque de datos) está dividido y N es el número de sub-bloques. Además, P' es el tamaño de carga útil del paquete para símbolos, F es el tamaño del fichero en octetos, K'_max es el número máximo de símbolos de origen con soporte (por ejemplo, 56.404), Al es un factor de alineación que especifica que los símbolos o sub-símbolos deberían ser múltiplos de AI octetos en tamaño para permitir una decodificación más eficaz, por ejemplo, se prefiere Al = 4 para una CPU moderna, y WS es la cota superior deseada sobre el tamaño de sub-bloque en octetos.

5

10

15

20

25

30

35

40

45

50

55

60

65

[201] Téngase en cuenta que la obtención de los parámetros T, Z y N se puede hacer en un emisor o en un servidor alternativo en función de los valores de F, Al y P'. El receptor solo necesita conocer los valores de F, Al, T, Z y N para determinar el sub-bloque y la estructura del bloque de origen del fichero o bloque de datos en los paquetes recibidos correspondientes al fichero o bloque de datos. El receptor puede determinar P' a partir del tamaño de los paquetes recibidos. Téngase en cuenta que los paquetes enviados y recibidos también contienen habitualmente otra información que identifica el contenido del paquete, por ejemplo, un Identificador de carga útil de FEC que normalmente tiene 4 octetos de tamaño y que lleva el número de bloque de origen (SBN) y el identificador de símbolo codificado (ESI) ) del primer símbolo llevado en el paquete.

[202] Un procedimiento anterior descrito en la Sección 4.2 de draft-luby-rmt-bb-fec-raptorg-object-00 para calcular T, Z, N es fijarlos en los siguientes valores:

• T = P'

• Kt = ceil (F / T)

• Z = ceil (Kt / K'_max)

• N = min {ceil (ceil (Kt / Z) * T / WS), T / Al}

[203] En estos cálculos, ceil () es una función que genera el entero más pequeño mayor o igual a su entrada, y floor() es una función que genera el entero más grande menor o igual a su entrada. Además, min() es una función que genera el mínimo de sus entradas.

[204] Un problema para algunos ajustes de parámetros con esta forma de obtener bloques de origen y particiones de sub-bloques es que si T / Al es menor que ceil (ceil (Kt / Z) * T / WS), entonces la cota superior sobre el tamaño W de sub-bloque puede no ser respetado.

[205] Un posible problema secundario es que esto permite que los sub-símbolos sean tan pequeños como Al, que típicamente se fija en 4 octetos, y pueden ser demasiado pequeños para ser eficaces en la práctica. Habitualmente, cuanto más pequeño es el tamaño de los sub-símbolos, más sobrecarga de procesamiento hay para decodificar o codificar sub-bloques. Además, especialmente en un receptor, un tamaño de sub-símbolo más pequeño significa que se deben demultiplexar y decodificar más sub-bloques, y esto puede consumir recursos del receptor tales como ciclos de CPU y accesos a la memoria. Por otro lado, un tamaño admisible de sub-símbolo más pequeño significa que un bloque de origen puede dividirse en más sub-bloques que respeten una cota superior especificada WS sobre el tamaño del sub-bloque. Por lo tanto, los sub-símbolos más pequeños permiten que se dé soporte a un bloque de origen más grande, y así la protección de FEC proporcionada a través de este bloque de origen produce una mejor protección y una mejor eficacia de la red. En la práctica, en muchos casos es preferible garantizar que los sub-símbolos tengan al menos un tamaño mínimo específico, lo que brinda la oportunidad de un mejor equilibrio entre los requisitos de procesamiento y los requisitos de memoria en un receptor y el uso eficaz de los recursos de red.

[206] Como un ejemplo de los parámetros obtenidos utilizando el procedimiento anterior, descrito en la Sección 4.2 de draft-luby-rmtbb-fec-raptorg-object-00 para calcular T, Z, N:

[207] Entrada:

F = 56.404 KB P' = 1 KB = 1.024 octetos WS = 128 KB Al = 4

K'_max = 56.404

[208] Cálculos:

T = 1 KB Kt = 56.404 Z = 1

N = 256 (debido a la segunda entrada a la función min)

[209] En este ejemplo, habrá un bloque de origen, que comprende 256 sub-bloques, donde cada sub-bloque tiene aproximadamente 220 KB (más grande que WS), con al menos algunos sub-bloques que tienen un tamaño de símbolo secundario de 4 octetos (extremadamente pequeño).

[210] Un tercer problema es que una solución AL-FEC puede no prestar soporte a todos los números posibles de símbolos de origen, es decir, puede dar soporte solo a una lista seleccionada de valores K', donde K' es un número con soporte de símbolos de origen en un bloque de origen y, entonces, si el número real K de símbolos de origen, deseado en un bloque de origen, no está entre los K' valores, entonces K se rellena hasta el valor de K' más cercano, lo que significa que el tamaño del bloque de origen que se utiliza puede ser algo mayor que el valor K

5

10

15

20

25

30

35

40

45

50

55

60

65

calculado a partir de lo anterior.

[211] Ahora describimos nuevos procedimientos de sub-bloqueo, que son mejoras sobre los procedimientos anteriores descritos en lo que antecede. Para los fines de la descripción, un módulo para sub-bloqueo podría tomar como sus datos de entrada los datos a dividir, F, y valores que incluyen WS, Al, sS y P', donde el significado de esas variables se describe con más detalle a continuación.

[212] WS representa una restricción proporcionada sobre el sub-bloque de tamaño máximo, posiblemente en unidades de octetos, que se puede decodificar en la memoria de trabajo en un receptor. Al representa un parámetro de alineación de memoria. Dado que una memoria del receptor podría funcionar más eficazmente si los símbolos y sub-símbolos están alineados en la memoria a lo largo de los límites de alineación de la memoria, podría ser útil rastrear Al y almacenar valores en múltiplos de Al octetos. Por ejemplo, habitualmente Al = 4, ya que muchos dispositivos de memoria acceden naturalmente a los datos en la memoria en límites de cuatro octetos. Otros valores de Al también son posibles, por ejemplo, Al = 2 o Al = 8. Habitualmente, Al se podría fijar en la alineación de memoria múltiple menos común de todos los muchos receptores posibles. Por ejemplo, si algunos receptores prestan soporte a la alineación de memoria de 2 octetos, pero otros receptores prestan soporte a la alineación de memoria de 4 octetos, entonces se recomienda Al = 4.

[213] El parámetro SS se determina basándose en la cota inferior preferida sobre el tamaño de sub-símbolo, de modo que la cota inferior sobre el tamaño de sub-símbolo sea de SS * A1 octetos. Puede ser preferible que el tamaño de sub-símbolo sea un múltiplo de Al, ya que las operaciones de decodificación se realizan típicamente sobre sub-símbolos.

[214] Lo que sigue es una explicación detallada de un procedimiento para dividir los datos F en Z bloques de origen y luego la partición de esos Z bloques de origen en N sub-bloques. En esta descripción, P' se refiere a una variable almacenada en la memoria (o implícita) que representa los octetos disponibles dentro de los paquetes para los símbolos que deben enviarse, y se supone que P' es un múltiplo de Al. T es una variable que representa el tamaño de los símbolos que han de colocarse dentro de los paquetes enviados. Se pueden deducir otras variables del texto.

Nuevo procedimiento de sub-bloqueo para determinar T, Z y N

[215]

• T = P'

• Kt = ceil (F / T);

• N_max = floor (T / (SS * Al));

• Para todo n = 1, ..., N_max

o KL(n) es el valor máximo de K' con soporte como un posible número de símbolos de origen en un bloque de origen que satisface

■ K' < WS / (Al * (ceil (T / (Al * n))));

• Z = ceil (Kt / KL (N_max));

• N = mínimo n tal que ceil (Kt / Z) < KL (n);

[216] Una vez que se han determinado estos parámetros, el tamaño de cada uno de los Z bloques de origen y los tamaños de los sub-símbolos de los N sub-bloques de cada bloque de origen se pueden determinar cómo se describe en el documento IETF RFC 5053, es decir, Kt = ceil (F / T), (KL, KS, ZL, ZS) = Partición [Kt, Z], y (TL, TS, NL, NS) = Partición [T / Al, N].

[217] Kt es la cantidad de símbolos de origen en el fichero. En un módulo de sub-bloque, los Kt símbolos de origen se dividen en Z bloques de origen, ZL bloques de origen con KL símbolos de origen cada uno y ZS bloques de origen con KS símbolos de origen cada uno. Luego, KL se redondea hasta KL', donde KL' es el número con soporte más pequeño de símbolos de origen que es al menos KL (y unos KL' - KL símbolos adicionales de relleno con ceros se agregan al bloque de origen con fines de codificación y decodificación, pero estos símbolos adicionales normalmente no se envían ni se reciben) y, de forma similar, KS se redondea hasta KS', donde KS' es el número con soporte más pequeño de símbolos de origen que es al menos KS (y unos KS' - KS símbolos adicionales de relleno con ceros se agregan al bloque de origen con fines de codificación y decodificación, pero estos símbolos adicionales habitualmente no se envían ni se reciben).

5

10

15

20

25

30

35

40

45

50

55

60

65

[218] Estos cálculos (realizados por el módulo de sub-bloque, otro módulo de software o hardware) aseguran que los números de símbolos de origen para los bloques de origen sean tan iguales como sea posible, sujeto a la restricción de que sus números totalicen el número, Kt, de símbolos de origen en el fichero. Estos cálculos también aseguran que los tamaños de los sub-símbolos para los sub-bloques sean lo más iguales posible, sujetos a la restricción de que sean múltiplos de Al y que sus tamaños sumen el tamaño del símbolo.

[219] Luego, se calculan los parámetros de sub-símbolo TL, TS, NL y NS, donde hay NL sub-bloques que usan el tamaño de sub-símbolo más grande TL * Al y hay NS sub-bloques que usan el tamaño de sub-símbolo más pequeño TS * Al. La función Partición [I, J] se implementa en software o hardware y se define como la función con una salida que es una secuencia de cuatro enteros (IL, IS, JL, JS), donde IL = ceil (I / J), IS = floor (I / J), JL = I - IS * J y JS = J - JL.

[220] Algunas de las propiedades de estos nuevos procedimientos son dignas de mención. Un módulo de subbloque puede determinar una cota inferior obtenida del tamaño de sub-símbolo más pequeño utilizado. A partir de las ecuaciones anteriores, se sabe que TS = floor (T / (Al * N)), donde TS * Al es el tamaño de sub-símbolo más pequeño utilizado, dado que TS < TL. Téngase en cuenta que el sub-símbolo más pequeño se usa cuando N = N_max. Usando X / (floor (y)) > X / Y para X e Y positivos, TS es al menos floor (T / (Al * floor (T / (SS * Al)))), que a su vez es al menos floor (SS) = SS. Debido a estos hechos, el tamaño de sub-símbolo más pequeño producido por el procedimiento de partición descrito en la presente memoria será al menos TS * Al = SS * Al, según se desee.

[221] Un módulo de sub-bloque puede determinar una cota superior obtenida del tamaño de sub-bloque más grande. El tamaño de sub-bloque más grande utilizado es TL * Al * Kl', donde KL' es el valor más pequeño de K' en la tabla anterior que es al menos KL = ceil (Kt / Z). Téngase en cuenta que, por la definición de N, KL' < KL (N) y TL = ceil (T / (Al * N)). Dado que KL (N) < WS / (Al * (ceil (T / (Al * N)))), se deduce que WS > KL (N) * Al * ceil (T / (Al * N)) > KL' * Al * TL.

[222] Una variable N_max puede representar el máximo número de sub-símbolos en los que se puede dividir un símbolo de origen de tamaño T. Al fijar N_max en floor (T / (SS * Al)), se asegura que el tamaño del sub-símbolo más pequeño sea al menos SS * Al. KL(n) es la mayor cantidad de símbolos de origen en un bloque de origen que puede tener soporte cuando los símbolos del bloque de origen están divididos en n sub-símbolos cada uno, para asegurar que cada uno de los sub-bloques del bloque de origen tenga un tamaño de a lo sumo WS.

[223] El número Z de bloques de origen puede elegirse para que sea lo más pequeño posible, sujeto a la restricción de que el número de símbolos de origen en cada bloque de origen sea como máximo KL (N_max), lo que asegura que cada símbolo de origen se puede dividir en sub-símbolos de tamaño SS * A1 al menos, y que los subbloques resultantes sean de tamaño WS a lo sumo. El módulo de sub-bloque determina, a partir del valor de Z, el número de bloques de origen y los números de símbolos en cada uno de los bloques de origen Z.

[224] Téngase en cuenta que si se usa cualquier valor de Z menor que el producido por este procedimiento de partición, entonces o bien habría un sub-bloque de uno de los bloques de origen que es más grande que WS o bien habría un sub-bloque de uno de los bloques de origen que tendría un tamaño de símbolo secundario menor que SS * Al. Además, el más pequeño de los bloques de origen que produce este procedimiento de partición es lo más grande posible, sujeto a estas dos restricciones, es decir, no hay ningún otro procedimiento para dividir el fichero o bloque de datos en bloques de origen que respete ambas restricciones de modo que el bloque de origen más pequeño sea más grande que el bloque de origen más pequeño producido por este procedimiento de partición. Por lo tanto, en este sentido, el valor de Z producido por este procedimiento de partición es óptimo.

[225] El número N de sub-bloques en los que se divide un bloque de origen se puede elegir para que sea lo más pequeño posible, sujeto a la restricción de que, para cada sub-bloque, el tamaño de los sub-símbolos del subbloque, multiplicado por el número de los símbolos de origen en el bloque de origen que el sub-bloque divide, sea como máximo WS.

[226] Téngase en cuenta que, si se utiliza cualquier valor de N menor que el producido por este procedimiento de partición a partir del valor de Z, entonces habría al menos un sub-bloque cuyo tamaño superaría WS. Además, el tamaño de sub-símbolo más pequeño que este procedimiento de partición produce a partir del valor dado de Z es lo más grande posible, sujeto a la restricción de que el tamaño de sub-bloque más grande no debería superar WS, es decir, no hay ningún otro procedimiento para producir sub -bloques de los bloques de origen determinados por el valor de Z que respete la restricción de sub-bloque más grande, de manera que el tamaño de sub-símbolo más pequeño sea mayor que el tamaño de sub-símbolo más pequeño producido por este procedimiento de partición. Por lo tanto, en este sentido, el valor de N producido por este procedimiento de partición es óptimo.

[227] En los siguientes ejemplos, se supone que todos los posibles valores K ' tienen soporte como una cantidad de símbolos de origen en un bloque de origen.

Ejemplo 1

5

10

15

20

25

30

35

40

45

50

55

60

65

[228] Entradas:

SS = 5

Al = 4 octetos

(Tamaño de sub-símbolo mínimo = 20 octetos)

WS = 128 KB = 131.072 octetos P' = 1.240 octetos F = 6 MB = 6.291.456 octetos

[229] Cálculos:

T = 1.240 octetos Kt = 5.074 N_max = 62 KL (N_max) = 6.553 Z = 1

KL = ceil (Kt / Z) = 5.074 N = 52 (KL (N) = 5.461)

TL = 6, sub-símbolo más grande = 24 octetos TS = 5, sub-símbolo más pequeño = 20 octetos

TL * AL * KL = 121.776

Ejemplo 2 [230] Entradas:

SS = 8

Al = 4 octetos

(Tamaño de sub-símbolo mínimo = 32 octetos)

WS = 128 KB = 131.072 octetos P' = 1 KB = 1.024 octetos F = 56.404 KB = 57.757.696 octetos

[231] Cálculos:

T = 1.024 octetos

Kt = 56.404

N_max = 32

KL (N_max) = 4.096

Z = 14 KL = ceil (Kt / Z) = 4.029

N = 32 (KL (N) = 4.096)

TL = 8, sub-símbolo más grande = 32 octetos TS = 8, sub-símbolo más pequeño = 32 octetos

TL * AL * KL = 128.928

[232] Hay muchas variantes de los procedimientos anteriores. Por ejemplo, para algunos códigos de FEC, es deseable tener al menos un número mínimo de símbolos de origen en un bloque de origen para minimizar la sobrecarga de recepción del bloque de origen del código de FEC. Dado que, para tamaños de fichero realmente pequeños o tamaños de bloques de datos F, el tamaño del símbolo de origen podría ser demasiado pequeño, también podría haber un número máximo de símbolos de origen en los que se divide un paquete. Por ejemplo, en el documento IETF RFC 5053, el número mínimo deseado de símbolos de origen en un bloque de origen es Kmin = 1024 y el número máximo de símbolos de origen en los que se divide un paquete es Gmax = 10.

[233] A continuación se muestra otra variante del nuevo procedimiento de sub-bloqueo descrito anteriormente que tiene en cuenta los parámetros adicionales Kmin y Gmax que acabamos de describir, donde G es el número de símbolos, para un bloque de origen, transportado en cada paquete, realizable mediante un módulo de sub-bloqueo o, más generalmente, algún módulo o software o hardware en un codificador, decodificador, transmisor y / o receptor.

[234] En esta variante, cada paquete lleva el ESI del primer símbolo en el paquete y luego cada símbolo subsiguiente en el paquete tiene implícitamente un ESI que es uno mayor que el símbolo precedente en el paquete.

Nuevo procedimiento de sub-bloqueo para determinar G, T, Z y N

5

10

15

20

25

30

35

40

45

50

55

60

65

[235]

• G = min (ceil (P'* Kmin / F), ftoor (P' / (SS * Al)), Gmax);

• T = floor (P'/ (Al * G)) * Al;

• Kt = ceil (F / T);

• N_max = floor (T / (SS * Al));

• Para todo n = 1, ..., N_max

■ K' < WS / (Al * (ceil (T / (Al * n))));

• Z = ceil (Kt / KL (N_max));

• N = mínimo n tal que ceil (Kt / Z) < KL (n);

[236] Téngase en cuenta que, por la forma en que se calcula G, se garantiza que el tamaño del símbolo sea al menos SS * Al, es decir, que el tamaño del símbolo sea, al menos, el tamaño mínimo del sub-símbolo. Téngase en cuenta también que debería ser el caso de que SS * A1 sea al menos P' para asegurar que el tamaño del símbolo pueda ser al menos SS * A1 (y si no lo es, entonces G se evaluará como cero).

Ejemplo 3

[237] Entrada:

SS = 5

Al = 4 octetos

(Tamaño de sub-símbolo mínimo = 20 octetos)

WS = 256 KB = 262.144 octetos

P' = 1.240 octetos

F = 500 KB = 512.000 octetos

Kmin = 1.024

Gmax = 10

[238] Cálculos:

G = 3

T = 412

Kt = 1.243

N_max = 20

KL (N_max) = 10.992

Z = 1 KL = ceil (Kt / Z) = 1.243

N = 2 (KL (N) = 1.260)

TL = 52, sub-símbolo más grande = 208 octetos TS = 51, sub-símbolo más pequeño = 204 octetos

TL * AL * KL = 258.544

[239] Como se ha descrito ahora, estos nuevos procedimientos introducen una restricción en el tamaño de subsímbolo más pequeño utilizado para cualquier sub-bloque. Esta divulgación proporciona nuevos procedimientos para el sub-bloqueo que respetan esta restricción adicional, mientras que al mismo tiempo respetan estrictamente una restricción sobre el tamaño máximo de sub-bloque. Los procedimientos producen soluciones de bloqueo de origen y de sub-bloqueo que satisfacen los objetivos de dividir un fichero o bloque de datos en el menor número posible de bloques de origen, sujeto a una restricción sobre el tamaño de sub-símbolo más pequeño, y luego sujeto a esta división en tan pocos sub -bloques como sea posible, sujeto a una restricción sobre el tamaño máximo de subbloque.

Variaciones:

5

10

15

20

25

30

35

40

45

50

[240] En algunas aplicaciones, puede ser aceptable no poder decodificar todos los símbolos de origen, o ser capaz de decodificar todos los símbolos de origen, pero con una probabilidad relativamente baja. En tales aplicaciones, un receptor puede dejar de intentar decodificar todos los símbolos de origen después de recibir K+A símbolos codificados. O bien, el receptor puede dejar de recibir símbolos codificados después de recibir menos de K+A símbolos codificados. En algunas aplicaciones, el receptor incluso puede recibir K o menos símbolos codificados. Por lo tanto, ha de entenderse que, en algunas realizaciones de la presente invención, el grado de precisión deseado no necesita ser una recuperación completa de todos los símbolos de origen.

[241] Además, en algunas aplicaciones donde la recuperación incompleta es aceptable, los datos pueden codificarse de modo que no se puedan recuperar todos los símbolos de origen, o que la recuperación completa de los símbolos de origen requiera la recepción de muchos más símbolos codificados que la cantidad de símbolos de origen. Dicha codificación generalmente requeriría menos gasto de cálculo y, por lo tanto, puede ser una forma aceptable de disminuir el gasto de cálculo de la codificación.

[242] Ha de entenderse que los diversos bloques funcionales en las figuras descritas anteriormente pueden implementarse mediante una combinación de hardware y / o software, y que en implementaciones específicas se pueden combinar algunas de, o todas, las funcionalidades de algunos de los bloques. De manera similar, también ha de entenderse que los diversos procedimientos enseñados en la presente memoria pueden implementarse mediante una combinación de hardware y / o software.

[243] La descripción anterior es ilustrativa y no restrictiva. Muchas variaciones de la invención serán evidentes para los expertos en la técnica tras la revisión de esta divulgación. El alcance de la invención debería, por lo tanto, determinarse no con referencia a la descripción anterior, sino que, en cambio, debería determinarse con referencia a las reivindicaciones adjuntas junto con su ámbito completo de equivalentes.

APÉNDICE A.

[244]

Transporte de multidifusión

fiable M' Luby

Borrador-Internet Qualcomm Incorporated

Estado previsto: Pista de Normas . A. Shokrollahi

Vence: 12 de febrero de 2011 . EPFL

. M. Watson

. Qualcomm Incorporated

. T. Stockhammer

. Nomor Research

. L. Minder

Qualcomm . Incorporated

.. 11 de agosto de 2010

Esquema de Corrección Anticipada de Errores RaptorQ para Entrega de Objetos draft-ietf-rmt-bb-fee-raptorq-04

Resumen

[245] Este documento describe un esquema de FEC completamente especificado, correspondiente al Identificador 6 de Codificación de FEC (por confirmar (tbc)), para el código de corrección anticipada de errores RaptorQ y su aplicación para la entrega fiable de objetos de datos.

[246] Los códigos RaptorQ son una nueva familia de códigos que brindan una flexibilidad superior, soporte para tamaños mayores de bloque de origen y una mejor eficacia de codificación que los códigos Raptor en el documento RFC5053. RaptorQ también es un código fuente, es decir, el codificador puede generar tantos símbolos de codificación como sea necesario sobre la marcha a partir de los símbolos de origen de un bloque de origen de datos. El decodificador puede recuperar el bloque de origen a partir de cualquier conjunto de símbolos de codificación para la mayoría de los casos, igual al número de símbolos de origen y, en casos excepcionales, con un poco más que el número de símbolos de origen.

[247] El código RaptorQ descrito aquí es un código sistemático, lo que significa que todos los símbolos de origen se encuentran entre los símbolos de codificación que se pueden generar.

5

10

15

20

25

Estado de este Memorándum

[248] Este borrador de Internet se presenta en total conformidad con las disposiciones de BCP 78 y BCP 79.

[249] Los borradores de Internet son documentos de trabajo de la Fuerza de Tareas de ingeniería de Internet (IETF). Téngase en cuenta que otros grupos también pueden distribuir documentos de trabajo como borradores de Internet. La lista de borradores actuales de Internet se encuentra en
http://datatracker.ietf.org/drafts/current/.

[250] Los Borradores de Internet son borradores de documentos válidos por un máximo de seis meses y pueden ser actualizados, reemplazados o declarados como obsoletos por otros documentos en cualquier momento. No es adecuado usar Borradores de Internet como material de referencia o citarlos de otra manera que no sea "trabajo en marcha".

[251] Este borrador de Internet caducará el 12 de febrero de 2011.

Aviso de derechos de autor

[253] Este documento está sujeto a BCP 78 y a las disposiciones legales del Consorcio de IETF relacionadas con los documentos de IETF (
http://trustee.ietf.org/license-info) vigentes a la fecha de publicación de este documento. Por favor, revise estos documentos detenidamente, ya que describen sus derechos y restricciones con respecto a este documento. Los componentes de código extraídos de este documento deben incluir texto simplificado de licencia BSD, como se describe en la sección 4.e de las Disposiciones Legales del Consorcio, y se proporcionan sin garantía, tal como se describe en la licencia BSD simplificada.

5

10

15

20

25

30

35

40

45

50

55

60

65

Índice

1. - Introducción ....................................................................................................................................................................................5

2. Notación de requisitos .......................................................................................................................................................... 5

3. Formatos y códigos ..................................................................................................................................................................... 5

3.1. Identificadores de carga útil de FEC ....................................................................................................5

3.2. Información de transmisión de objetos de FEC ............................................................................. 6

3.2.1. Obligatorio ............................................................................................................................................................. 6

3.2.2. Común .............................................................................................................................................................................. 6

3.2.3. Esquema específico ......................................................................................................................................... 7

4. Procedimientos ................................................................................................................................................................................. 8

4.1. Introducción ........................................................................................................................................................................ 8

4.2. Requisitos del protocolo de entrega de contenido .................................................................. 8

4.3. Algoritmo ejemplar de obtención de parámetros .......................................................................... 8

4.4. Entrega de objetos .................................................................................................................................................... 10

4.4.1. Construcción del bloque de origen ........................................................................................... 10

4.4.2. Codificación de construcción de paquetes ....................................................................... 12

5. Especificación del código RaptorQ de FEC ....................................................................................................... 13

5.1. Definiciones, símbolos y abreviaturas ................................................................................................. 13

5.1.1. Definiciones ....................................................................................................................................................... 13

5.1.2. Símbolos .................................................................................................................................................................. 14

5.1.3. Abreviaturas ....................................................................................................................................................... 16

5.2. Visión general ................................................................................................................................................................ 17

5.3. Codificador RaptorQ sistemático ............................................................................................................... 18

5.3.1. Introducción ....................................................................................................................................................... 18

5.3.2. Visión general de la codificación ........................................................................................... 19

5.3.3. Primera etapa de codificación: Generación de Símbolo Intermedio. ... 21

5.3.4. Segunda etapa de codificación: Codificación ................................................................ 27

5.3.5. Generadores .......................................................................................................................................................... 27

5.4. Ejemplo de decodificador de FEC .................................................................................................................. 30

5.4.1. General ..................................................................................................................................................................... 30

5.4.2. Decodificación de un bloque de origen ampliado ...................................................... 31

5.5. Números aleatorios .................................................................................................................................................... 36

5.5.1. La tabla V0 .......................................................................................................................................................... 36

5.5.2. La tabla V1 .......................................................................................................................................................... 37

5.5.3. La tabla V2 .......................................................................................................................................................... 38

5.5.4. La tabla V3 .......................................................................................................................................................... 39

5.6. Índices sistemáticos y otros parámetros ........................................................................................ 40

5.7. Operaciones con Octetos, Símbolos y Matrices ............................................................................. 60

5.7.1. General ..................................................................................................................................................................... 60

5.7.2. Operaciones aritméticas en los octetos ................................................................................. 61

5.7.3. La tabla OCT_EXP ............................................................................................................................................ 62

5.7.4. La tabla OCT_LOG ............................................................................................................................................ 63

5.7.5. Operaciones con símbolos ........................................................................................................................ 63

5.7.6. Operaciones en matrices ........................................................................................................................ 64

5.8. Requisitos para un decodificador compatible ............................................................................. 64

6. Consideraciones de seguridad ................................................................................................................................. 65

7. Consideraciones de IANA .................................................................................................................................................... 65

8. Agradecimientos ........................................................................................................................................................................... 66

9. Referencias ...................................................................................................................................................................................... 66

9.1. Referencias normativas ......................................................................................................................................... 66

9.2. Referencias informativas ................................................................................................................................. 66

Direcciones de los autores .................................................................................................................................................... 66

1. Introducción

[254] Este documento especifica un Esquema de FEC para el código de corrección anticipada de errores RaptorQ para aplicaciones de entrega de objetos. El concepto de un Esquema de FEC se define en el documento RFC5052 [RFC5052] y este documento sigue el formato prescrito allí y utiliza la terminología de ese documento. El código RaptorQ descrito en la presente memoria es una próxima generación del código Raptor descrito en el documento RFC5053 [RFC5053]. El código RaptorQ proporciona fiabilidad superior, mejor eficacia de codificación y soporte para tamaños mayores de bloque de origen que el código Raptor del documento RFC5053 [RFC5053]. Estas mejoras simplifican el uso del código RaptorQ en un protocolo de entrega de contenido para entrega de objetos, en comparación con el documento RFC5053 [RFC5053].

5

10

15

20

25

30

35

40

45

50

55

60

[255] El Esquema RaptorQ de FEC es un Esquema de FEC Completamente Especificado correspondiente al Identificador 6 de codificación de FEC (tbc).

Nota del editor: El Identificador de codificación de FEC finalizada aún no se ha definido, pero '6 (tbc)' se utiliza como valor temporal en este Borrador de Internet, esperando el uso secuencial de los Identificadores de codificación de FEC en el proceso de registro de IANA.

[256] RaptorQ es un código de fuente, es decir, el codificador puede generar tantos símbolos de codificación como sea necesario sobre la marcha a partir de los símbolos de origen de un bloque. El decodificador puede recuperar el bloque de origen a partir de cualquier conjunto de símbolos de codificación, solo un poco más, en número, que el número de símbolos de origen.

[257] El código descrito en este documento es un código sistemático, es decir, los símbolos de origen originales pueden enviarse sin modificaciones desde el remitente al receptor, así como una serie de símbolos de reparación. Para obtener más información de fondo sobre el uso de los códigos de Corrección anticipada de errores en multidifusión fiable, véase el documento [RFC3453].

2. Notación de requisitos

[258] _ Las palabras clave "DEBE", "NO DEBE", "REQUERIDO", "DEBERÁ", "NO DEBERÁ", "DEBERÍA", "NO DEBERÍA", "RECOMENDADO", "PUEDE" y "OPTATIVO" en este documento han de ser interpretadas como se describe en el documento [RFC2119].

3. Formatos y Códigos

3.1. Identificadores de carga útil de FEC

[259] El Identificador de la carga útil de FEC DEBE ser un campo de 4 octetos definido de la siguiente manera:

imagen2

Figura 1: Formato de identificador de carga útil de FEC

o Número de bloque de origen (SBN), (8 bits, entero sin signo): Un identificador entero no negativo para el bloque de origen con el que se relacionan los símbolos de codificación dentro del paquete.

o Identificador de símbolo de codificación (ESI), (24 bits, entero sin signo): Un identificador entero no negativo para los símbolos de codificación dentro del paquete.

[260] La interpretación del número de bloque de origen y del Identificador de símbolo de codificación se define en

la Sección 4.

3.2. Información de transmisión de objetos de FEC

3.2.1. Obligatorio

[261] El valor del Identificador de codificación de FEC DEBE ser 6, según lo asignado por la IANA (véase la

Sección 7).

3.2.2. Común

[262] Los elementos comunes de información de transmisión de objetos de FEC utilizados por este esquema de

FEC son:

o Longitud de transferencia (F), (40 bits, entero sin signo): Un entero no negativo que es como máximo 946270874880. Esta es la longitud de transferencia del objeto en unidades de octetos.

o Tamaño del símbolo (T), (16 bits, entero sin signo): Un entero positivo que es menor que 2AA16. Este es el tamaño de un símbolo en unidades de octetos.

[263] El formato de Información de Transmisión de Objeto de FEC común codificada se muestra en la Figura 2.

5

10

15

20

25

30

35

40

45

50

55

■+

I

+•

I

0 12 3

m n í e t s 4 d i n u e t s 9 o t 2 h s ( t h o i

- + -*'-*-4-4-, + - + --,4-4_+'-,+"*-4-*-#- +-• + - + -#■ 4-4'- + -•+- + -4"*_+,"’, + -",*_*_4-'4-4

Longitud de oransferencia (7)

4-4^+-*-*-*-*^*-*-+-#- + -+—+-+-4^4’#^*-*-*-*-4^4- +

Reservad I Tamaño del sintióle [T>

#■-4-- *-*-4-4- + - + -4--4-*-4--*-*-*-4- + - + -*-*- + - +- +- +- *- *- +-+ -*-*-4-4“ +

Figura 2: FEC común codificada OTI para esquema de FEC RaptorQ

NOTA 1: El límite de 946270874880 en la longitud de transferencia es una consecuencia de la limitación en el tamaño del símbolo a 2AA16-1, de la limitación en el número de símbolos en un bloque de origen a 56.403 y de la limitación en el número de bloques de origen a 2^8.

3.2.3. Específico del esquema

[264] Los siguientes parámetros se transmiten en el elemento de Información de transmisión de objeto de FEC específico del esquema para este Esquema de FEC:

o El número de bloques de origen (Z) (12 bits, entero sin signo)

o El número de sub-bloques (N) (12 bits, entero sin signo)

o Un parámetro de alineación de símbolos (Al) (8 bits, entero sin signo)

[265] Estos parámetros son todos enteros positivos. La Información codificada de Transmisión de Objeto específica del Esquema es un campo de 4 octetos que consta de los parámetros Z, N y Al, como se muestra en la Figura 3.

0 12 3

01234567890123456789012345678901

I Z I N ! Al

+ -+-+-+- + -4 1 1 1 1 ! 1 1 1 1 1 1 1 - 4 I- - + - + -H I-- + - + -+- + -+-+-4 h

Figura 3: Información codificada de transmisión de objetos de FEC específica del

esquema

[266] La información codificada de transmisión de objetos de FEC es un campo de 12 octetos que consiste en la concatenación de la información común codificada de transmisión de objetos de FEC y la información codificada, específica del esquema, de transmisión de objetos de FEC.

[267] Estos tres parámetros definen la partición del bloque de origen según se describe en la Sección 4.4.1.2

4. Procedimientos

4.1. Introducción

[268] Para símbolos o funciones indefinidos cualesquiera, usados en esta sección, en particular, las funciones "ceil" y "floor", remítase a la Sección 5.1.

4.2. Requisitos del protocolo de entrega de contenido

[269] Esta sección describe el intercambio de información entre el Esquema RaptorQ de FEC y cualquier Protocolo de Entrega de Contenido (CDP) que haga uso del Esquema RaptorQ de FEC para la entrega de objetos.

[270] El esquema codificador de RaptorQ y el esquema decodificador de RaptorQ para la entrega de objetos requieren la siguiente información del CDP:

o La longitud de transferencia del objeto, F, en octetos

o Un parámetro de alineación de símbolos, Al

o El tamaño del símbolo, T, en octetos, que DEBE ser un múltiplo de Al

5

10

15

20

25

30

35

40

45

50

55

60

65

o La cantidad de bloques de origen, Z o El número de sub-bloques en cada bloque de origen, N

[271] El esquema codificador de RaptorQ para la entrega de objetos requiere adicionalmente:

- el objeto a codificar, F octetos

[272] El esquema codificador de RaptorQ proporciona al CDP la siguiente información para cada paquete que se enviará:

o Número de bloque de origen (SBN) o Identificador de símbolo de codificación (ESI) o Símbolo(s) de codificación

[273] El CDP DEBE comunicar esta información al receptor.

4.3. Algoritmo ejemplar de obtención de parámetros

[274] Esta sección proporciona recomendaciones para la obtención de los tres parámetros de transporte, T, Z y N. Esta recomendación se basa en los siguientes parámetros de entrada:

o F, la longitud de transferencia del objeto, en octetos

o WS, el bloque de tamaño máximo que se puede decodificar en la memoria de trabajo, en octetos o P', el tamaño máximo de carga útil en octetos, que se supone que es un múltiplo de Al o Al, el parámetro de alineación de símbolos, en octetos

o SS, un parámetro donde la cota inferior deseada sobre el tamaño del sub-símbolo es SS * A1 o K'_max, el número máximo de símbolos de origen por bloque de origen.

[275] Nota: La sección 5.1.2 define K'_max como 56403.

[276] Basándose en las entradas anteriores, los parámetros de transporte T, Z y N se calculan de la siguiente manera:

Sea

o T = P' o Kt = ceil (F / T) o N_max = floor (T / (SS * Al)) o para todo n = 1 ..., N_max

* KL (n) es el valor máximo de K' en la Tabla 2, en la Sección 5.6, tal que

K '<= WS / (Al * (ceil (T / (Al * n))))

o Z = ceil (Kt / KL (N_max))

o N es el mínimo n = 1, ..., N_max tal que ceil (Kt / Z) <= KL (n)

[277] Se RECOMIENDA que cada paquete contenga exactamente un símbolo. Sin embargo, los receptores DEBERÁN prestar soporte a la recepción de paquetes que contienen múltiples símbolos.

[278] El valor Kt es la cantidad total de símbolos necesarios para representar los datos de origen del objeto.

[279] El algoritmo anterior y el definido en la Sección 4.4.1.2 aseguran que los tamaños de los sub-símbolos son

5

10

15

20

25

30

35

40

45

50

55

60

65

un múltiplo del parámetro de alineación de símbolos, Al. Esto es útil porque las operaciones de suma utilizadas para codificar y decodificar se realizan generalmente sobre varios octetos a la vez, por ejemplo, al menos 4 octetos a la vez en un procesador de 32 bits. Por lo tanto, la codificación y la decodificación se pueden realizar más rápidamente si los tamaños de los sub-símbolos son un múltiplo de este número de octetos.

[280] La configuración recomendada para el parámetro de entrada Al es 4.

[281] El parámetro WS se puede usar para generar datos codificados que pueden decodificarse de manera eficaz con memoria de trabajo limitada en el decodificador. Téngase en cuenta que el requisito máximo real de memoria del decodificador para un valor dado de WS depende de la implementación, pero es posible implementar la decodificación utilizando una memoria de trabajo solo ligeramente mayor que WS.

4.4. Entrega de objetos

4.4.1. Construcción del bloque de origen

4.4.11. General

[282] Para aplicar el codificador RaptorQ a un objeto de origen, el objeto se puede dividir en Z > = 1 bloques, conocidos como bloques de origen. El codificador RaptorQ se aplica independientemente a cada bloque de origen. Cada bloque de origen se identifica por un único Número de bloque de origen (SBN), donde el primer bloque de origen tiene SBN cero, el segundo tiene SBN uno, etc. Cada bloque de origen se divide en un número, K, de símbolos de origen de T octetos de tamaño cada uno. Cada símbolo de origen se identifica mediante un identificador de símbolo de codificación (ESI) único, donde el primer símbolo de origen de un bloque de origen tiene ESI cero, el segundo tiene ESI uno, etc.

[283] Cada bloque de origen con K símbolos de origen se divide en N > = 1 sub-bloques, que son lo suficientemente pequeños como para ser decodificados en la memoria de trabajo. Cada sub-bloque se divide en K sub-símbolos de tamaño T'.

[284] Téngase en cuenta que el valor de K no es necesariamente el mismo para cada bloque de origen de un objeto y que el valor de T' puede no ser necesariamente el mismo para cada sub-bloque de un bloque de origen. Sin embargo, el tamaño T del símbolo es el mismo para todos los bloques de origen de un objeto y el número de símbolos, K, es el mismo para cada sub-bloque de un bloque de origen. La partición exacta del objeto en bloques de origen y sub-bloques se describe en la Sección 4.4.1.2 a continuación.

4.4.1.2. Bloque de origen y división en sub-bloques

[285] La construcción de bloques de origen y sub-bloques se determina basándose en cinco parámetros de entrada, F, Al, T, Z y N, y una función Partición[]. Los cinco parámetros de entrada se definen de la siguiente manera:

o F, la longitud de transferencia del objeto, en octetos o Al, un parámetro de alineación de símbolos, en octetos o T, el tamaño del símbolo, en octetos, que DEBE ser un múltiplo de Al o Z, la cantidad de bloques de origen o N, la cantidad de sub-bloques en cada bloque de origen

[286] Estos parámetros DEBEN fijarse de modo que ceil (ceil (F / T) / Z) <= K'_max. Las recomendaciones para la obtención de estos parámetros se proporcionan en la Sección 4.3.

[287] La función Partición[] toma un par de enteros positivos (I, J) como entrada y obtiene cuatro enteros no negativos (IL, IS, JL, JS) como salida. Específicamente, el valor de Partición[I, J] es la secuencia (IL, IS, JL, JS), donde IL = ceil (I / J), IS = floor (I / J), JL = I - IS * J y JS = J - JL. Partición[] obtiene los parámetros para dividir un bloque de tamaño I en J bloques de aproximadamente el mismo tamaño. Específicamente, JL bloques de longitud IL y JS bloques de longitud IS.

[288] El objeto de origen DEBE ser dividido en bloques de origen y sub-bloques de la siguiente manera:

Sean

o Kt = ceil (F / T),

5

10

15

20

25

30

35

40

45

50

55

60

65

o (KL, KS, ZL, ZS) Partición [Kt, Z], o (TL, TS, NL, NS) Partición [T / Al, N].

[289] Entonces, el objeto DEBE dividirse en Z = ZL + ZS bloques de origen contiguos, teniendo cada uno de los primeros ZL bloques de origen KL * T octetos, es decir, KL símbolos de origen de T octetos cada uno, y teniendo cada uno de los ZS bloques de origen restantes KS * T octetos, es decir, KS símbolos de origen de T octetos cada uno.

[290] Si Kt * T> F entonces, con fines de codificación, el último símbolo del último bloque de origen DEBE ser rellenado al final con Kt * TF octetos cero.

[291] A continuación, cada bloque de origen con K símbolos de origen DEBE dividirse en N = NL + NS subbloques contiguos, consistiendo cada uno de los primeros NL sub-bloques en K sub-símbolos contiguos de TL * Al octetos de tamaño, y consistiendo cada uno de los NS sub- bloques restantes en K sub-símbolos contiguos de TS * A1 octetos de tamaño. El parámetro Al de alineación de símbolos asegura que los sub-símbolos son siempre un múltiplo de Al octetos.

[292] Finalmente, el símbolo m-ésimo de un bloque de origen consiste en la concatenación del sub-símbolo m- ésimo de cada uno de los N sub-bloques. Téngase en cuenta que esto implica que cuando N > 1, entonces un símbolo NO es una parte contigua del objeto.

4.4.2. Construcción de paquetes de codificación

[293] Cada paquete de codificación contiene la siguiente información: o Número de bloque de origen (SBN)

o Identificador de símbolo de codificación (ESI) o símbolo(s) de codificación

[294] Cada bloque de origen está codificado independientemente de los demás. Los bloques de origen se numeran consecutivamente desde cero.

[295] Los valores del Identificador de símbolo de codificación de 0 a K-1 identifican los símbolos de origen de un bloque de origen en orden secuencial, donde K es el número de símbolos de origen en el bloque de origen. Los Identificadores de símbolos de codificación de K en adelante identifican los símbolos de reparación generados a partir de los símbolos de origen usando el codificador RaptorQ.

[296] Cada paquete de codificación consiste completamente en símbolos de origen (paquete de origen) o completamente de símbolos de reparación (paquete de reparación). Un paquete puede contener cualquier cantidad de símbolos del mismo bloque de origen. En el caso de que el último símbolo de origen en un paquete de origen incluya octetos de relleno agregados con fines de codificación de FEC, entonces estos octetos no necesitan ser incluidos en el paquete. De lo contrario, solo se DEBEN incluir símbolos completos.

[297] El Identificador de Símbolo de Codificación, X, transportado en cada paquete de origen es el Identificador de Símbolo de Codificación del primer símbolo de origen transportado en ese paquete. Los siguientes símbolos de origen en el paquete tienen Identificadores de símbolos de codificación, X + 1 a X + G-1, en orden secuencial, donde G es el número de símbolos en el paquete.

[298] De manera similar, el Identificador de Símbolo de Codificación, X, colocado en un paquete de reparación es el Identificador de Símbolo de Codificación del primer símbolo de reparación en el paquete de reparación, y los símbolos de reparación subsiguientes en el paquete tienen Identificadores de Símbolos de Codificación X + 1 a X + G-1 en orden secuencial, donde G es el número de símbolos en el paquete.

[299] Téngase en cuenta que no es necesario que el receptor conozca el número total de paquetes de reparación.

5. Especificación del código de RaptorQ de FEC

5.1. Definiciones, símbolos y abreviaturas

[300] Para los fines de la especificación del código de RaptorQ de FEC en esta sección, se aplican las siguientes definiciones, símbolos y abreviaturas.

5

10

15

20

25

30

35

40

45

50

55

60

65

5.1.1. Definiciones

[301]

o Bloque de origen: un bloque de K símbolos de origen que se consideran en conjunto para fines de codificación y decodificación de RaptorQ.

o Bloque de origen ampliado: un bloque de K' símbolos de origen', donde K' > = K construido a partir de un bloque de origen y cero o más símbolos de relleno.

o Símbolo: una unidad de datos. El tamaño, en octetos, de un símbolo se conoce como el tamaño del símbolo. El tamaño del símbolo siempre es un entero positivo.

o Símbolo de origen: la unidad de datos más pequeña utilizada durante el proceso de codificación. Todos los símbolos de origen dentro de un bloque de origen tienen el mismo tamaño.

o Símbolo de relleno: un símbolo con todos los bits cero que se agrega al bloque de origen para formar el bloque de origen extendido.

o Símbolo de codificación: un símbolo que se puede enviar como parte de la codificación de un bloque de origen. Los símbolos de codificación de un bloque de origen consisten en los símbolos de origen del bloque de origen y los símbolos de reparación generados a partir del bloque de origen. Los símbolos de reparación generados a partir de un bloque de origen tienen el mismo tamaño que los símbolos de origen de ese bloque de origen.

o Símbolo de reparación: los símbolos de codificación de un bloque de origen que no son símbolos de origen. Los símbolos de reparación se generan basándose en los símbolos de origen de un bloque de origen.

o Símbolos intermedios: símbolos generados a partir de los símbolos de origen utilizando un proceso de codificación inversa. Los símbolos de reparación se generan luego directamente a partir de los símbolos intermedios. Los símbolos de codificación no incluyen los símbolos intermedios, es decir, los símbolos intermedios no se envían como parte de la codificación de un bloque de origen. Los símbolos intermedios se dividen en símbolos LT y símbolos PI.

o Símbolos LT El subconjunto de los símbolos intermedios que pueden ser vecinos LT de un símbolo de codificación.

o Símbolos PI El subconjunto de los símbolos intermedios que pueden ser vecinos PI de un símbolo de codificación.

o Código sistemático: un código en el que todos los símbolos de origen se incluyen como parte de los símbolos de codificación de un bloque de origen. El código de RaptorQ, como se describe en la presente memoria, es un código sistemático.

o Identificador de símbolo de codificación (ESI): información que identifica de forma única cada símbolo de codificación asociado a un bloque de origen, con fines de envío y recepción.

o Identificador de símbolo interno (ISI): información que identifica de manera única cada símbolo asociado a un bloque de origen extendido con fines de codificación y decodificación.

o Operaciones aritméticas en octetos y símbolos y matrices: Las operaciones que se utilizan para producir símbolos de codificación a partir de símbolos de origen y viceversa. Véase la Sección 5.7.

5.1.2. Símbolos

[302]

i, j, u, v, h, d, a, b, dl, al, bl, v, m, x, y representan valores o variables de un tipo u otro, según el contexto.

X indica un valor entero no negativo que es un valor de ISI o bien un valor de ESI, según el contexto.

ceil (x) indica el entero más pequeño que es mayor o igual a x, donde x es un valor real.

floor (x) indica el entero más grande que es menor o igual a x, donde x es un valor real.

min (x, y) indica el valor mínimo de los valores x e y, y, en general, el valor mínimo de todos los valores de los

5

10

15

20

25

30

35

40

45

50

55

60

65

argumentos.

max (x, y) indica el valor máximo de los valores x e y, y, en general, el valor máximo de todos los valores de los argumentos.

i% j indica i módulo j.

i + j indica la suma de i y j. Si i y j son octetos, respectivamente símbolos, esto designa la aritmética en octetos, respectivamente símbolos, según se define en la sección 5.7. Si i y j son enteros, entonces indica la suma entera habitual.

i * j indica el producto de i y j. Si i y j son octetos, esto designa la aritmética en octetos, según se define en la sección 5.7. Si i es un octeto y j es un símbolo, esto indica la multiplicación de un símbolo por un octeto, como también se define en la Sección 5.7. Finalmente, si i y j son números enteros, i * j denota el producto habitual de números enteros.

a AA b indica la operación 'a elevada a la potencia b'. Si a es un octeto y b es un entero no negativo, se entiende que esto significa a * a * ... * a (b factores), siendo '*' el producto de octetos según se define en la sección 5.7.

u a v indica, para cadenas de bits u y v de igual longitud, la operación lógica de 'o' exclusivo bit por bit de u y v.

La traspuesta [A] indica la matriz traspuesta de la matriz A. En esta especificación, todas las matrices tienen entradas que son octetos.

AAA-1 indica la matriz inversa de la matriz A. En esta especificación, todas las matrices tienen octetos como entradas, por lo que se entiende que las operaciones de las entradas de la matriz se han de hacer como se establece en la Sección 5.7 y que Aaa-1 es la matriz inversa de A con respecto a la aritmética de octetos.

K indica la cantidad de símbolos en un solo bloque de origen.

K' indica la cantidad de símbolos de origen más relleno en un bloque de origen extendido. Para la mayor parte de esta especificación, los símbolos de relleno se consideran símbolos de origen adicionales.

K'_max indica la cantidad máxima de símbolos de origen que pueden estar en un solo bloque de origen. Fijada en 56403.

L indica el número de símbolos intermedios para un solo bloque de origen extendido.

S indica la cantidad de símbolos de LDPC para un único bloque de origen extendido. Estos son los símbolos LT. Para cada valor de K' que se muestra en la Tabla 2, en la Sección 5.6, el valor correspondiente de S es un número primo.

H indica la cantidad de símbolos de HDPC para un solo bloque de origen extendido. Estos son símbolos PI.

B indica el número de símbolos intermedios que son símbolos LT excluyendo los símbolos de LDPC.

W indica el número de símbolos intermedios que son símbolos LT. Para cada valor de K' en la Tabla 2 que se muestra en la Sección 5.6, el valor correspondiente de W es un número primo.

P indica el número de símbolos intermedios que son símbolos PI. Estos contienen todos los símbolos de HDPC. P1 indica el número primo más pequeño mayor o igual a P.

U indica el número de símbolos intermedios no de HDPC que son símbolos PI.

C indica una formación de símbolos intermedios, C[0], C[1], C[2], ..., C[L-1].

C' indica una formación de los símbolos del bloque de origen extendido, donde C'[0], C'[1], C'[2], ..., C'[K-1] son los símbolos de origen del bloque de origen y C'[K], C'[K + 1], ..., C'[K'-1] son símbolos de relleno.

V0, V1, V2, V3 indican cuatro formaciones de enteros sin signo de 32 bits, V0[0], V0[1], ..., V0[255]; V1[0], V1[1], ..., V1[255]; V2[0], V2[1], ..., V2[255]; y V3[0], V3[1], ..., V3[255], como se muestra en la Sección 5.5.

Azar[y, i, m] indica un generador de números seudo-aleatorios

Grado[v] indica un generador de grados

5

10

15

20

25

30

35

40

45

50

55

60

65

Enc [K', C, (d, a, b, dl, al, bl)] indica un generador de símbolos de codificación Tupla[K', X] indica una función generadora de tuplos T indica el tamaño del símbolo en octetos.

J(K') indica el índice sistemático asociado a K'.

G indica cualquier matriz generadora.

I_S indica la matriz de identidad SxS.

5.1.3. Abreviaturas

[303]

ESI Identificador de símbolo de codificación

HDPC Control de Paridad de Alta Densidad ISI Identificador de símbolo interno

LDPC Control de Paridad de Baja Densidad

LT Transformación de Luby

PI Permanentemente inactivo

SBN Número de bloque de origen

SBL Longitud del bloque de origen (en unidades de símbolos)

5.2. Visión general

[304] Esta sección define el código sistemático de FEC de RaptorQ.

[305] Los símbolos son las unidades de datos fundamentales del proceso de codificación y decodificación. Para cada bloque de origen, todos los símbolos tienen el mismo tamaño, denominado tamaño de símbolo T. Las operaciones atómicas realizadas en símbolos, tanto para la codificación como para la decodificación, son las operaciones aritméticas definidas en la Sección 5.7.

[306] El codificador básico se describe en la Sección 5.3. El codificador primero obtiene un bloque de símbolos intermedios a partir de los símbolos de origen de un bloque de origen. Este bloque intermedio tiene la propiedad de que los símbolos, tanto de origen como de reparación, se pueden generar a partir del mismo usando el mismo proceso. El codificador produce símbolos de reparación a partir del bloque intermedio usando un proceso eficaz, donde cada símbolo de reparación de ese tipo es el O exclusivo de un pequeño número de símbolos intermedios procedentes del bloque. Los símbolos de origen también se pueden reproducir a partir del bloque intermedio usando el mismo proceso. Los símbolos de codificación son la combinación de los símbolos de origen y de reparación.

[307] Un ejemplo de un decodificador se describe en la Sección 5.4. El proceso para producir símbolos de origen y de reparación a partir del bloque intermedio está diseñado de modo que el bloque intermedio pueda recuperarse desde cualquier conjunto de símbolos de codificación suficientemente grande, independientemente de la mezcla de símbolos de origen y de reparación en el conjunto. Una vez que se recupera el bloque intermedio, los símbolos de origen faltantes del bloque de origen se pueden recuperar usando el proceso de codificación.

[308] Los requisitos para un decodificador compatible con RaptorQ se proporcionan en la Sección 5.8. Una serie de algoritmos de decodificación son posibles para lograr estos requisitos. Un algoritmo de decodificación eficaz para lograr estos requisitos se proporciona en la Sección 5.4.

[309] La construcción de los símbolos intermedios y de reparación se basa, en parte, en un generador de números seudo-aleatorios descrito en la Sección 5.3. Este generador se basa en un conjunto fijo de 1024 números aleatorios que deben estar disponibles tanto para el emisor como para el receptor. Estos números se proporcionan en la Sección 5.5. Las operaciones de codificación y decodificación para RaptorQ usan operaciones en octetos. La Sección 5.7 describe cómo realizar estas operaciones.

5

10

15

20

25

30

35

40

45

50

55

[310] Finalmente, la construcción de los símbolos intermedios a partir de los símbolos de origen se rige por "índices sistemáticos", cuyos valores se proporcionan en la Sección 5.6 para tamaños específicos de bloques de origen extendidos, entre 6 y K'_max = 56403 símbolos de origen. Por lo tanto, el código de RaptorQ presta soporte a bloques de origen con entre 1 y 56403 símbolos de origen.

5.3. Codificador Sistemático de RaptorQ

5.3.1. Introducción

[311] Para un bloque de origen dado de K símbolos de origen, con fines de codificación y decodificación, el bloque de origen se aumenta con K-K' símbolos de relleno adicionales, donde K' es el valor más pequeño que es al menos K en el índice sistemático de la Tabla 2, de la Sección 5.6. La razón para rellenar un bloque de origen hasta un múltiplo de K' es permitir codificación y decodificación más rápidas, y minimizar la cantidad de información de la tabla que se debe almacenar en el codificador y el decodificador.

[312] Con el fin de transmitir y recibir datos, el valor de K se usa para determinar el número de símbolos de origen en un bloque de origen y, por lo tanto, K debe conocerse en el emisor y el receptor. En este caso, el emisor y el receptor pueden calcular K' a partir de K y los K-K' símbolos de relleno pueden agregarse automáticamente al bloque de origen sin ninguna comunicación adicional. El identificador de símbolo de codificación (ESI) es utilizado por un emisor y receptor para identificar los símbolos de codificación de un bloque de origen, donde los símbolos de codificación de un bloque de origen consisten en los símbolos de origen y los símbolos de reparación asociados al bloque de origen. Para un bloque de origen con K símbolos de origen, los ESI para los símbolos de origen son 0,1,2, ..., K-1 y los ESI para los símbolos de reparación son K, K + 1, K + 2, ... . El uso de los ESI para identificar símbolos de codificación en el transporte garantiza que los valores de ESI continúen consecutivamente entre los símbolos de origen y de reparación.

[313] Con fines de codificación y decodificación de datos, el valor de K' obtenido a partir de K se usa como el número de símbolos de origen del bloque de origen extendido sobre los que se realizan operaciones de codificación y decodificación, donde los K' símbolos de origen consisten en los K símbolos de origen originales y unos K'-K símbolos de relleno adicionales. El Identificador de símbolo interno (ISI) es utilizado por el codificador y el decodificador para identificar los símbolos asociados al bloque de origen extendido, es decir, para generar símbolos de codificación y para decodificar. Para un bloque de origen con K símbolos de origen originales, los ISI para los símbolos de origen originales son 0,1,2, ..., K-1, los ISI para los K-K' símbolos de relleno son K, K + 1, K +2, ..., K'-1 y los ISI para los símbolos de reparación son K ', K' + 1, K '+ 2, ... . El uso del ISI para codificar y decodificar permite que los símbolos de relleno del bloque de origen extendido se traten de la misma manera que otros símbolos de origen del bloque de origen extendido, y que un prefijo dado de símbolos de reparación se genere de manera coherente para un número determinado K' de los símbolos de origen en el bloque de origen extendido, independiente de K.

[314] La relación entre los ESI y los ISI es sencilla: los ESI y los ISI para los K símbolos de origen originales son los mismos, los K'-K símbolos de relleno tienen un ISI pero no tienen un ESI correspondiente (ya que son símbolos que no son ni enviados ni recibidos), y un ISI de símbolo de reparación es simplemente el ESI del símbolo de reparación más K'-K. La traducción entre los ESI utilizados para identificar los símbolos de codificación enviados y recibidos y los ISI correspondientes utilizados para la codificación y decodificación, y el correcto rellenado del bloque de origen extendido con símbolos de relleno utilizados para codificar y decodificar, es responsabilidad de la función de relleno en el codificador / decodificador de RaptorQ.

5.3.2. Visión general de la codificación

[315] El codificador sistemático de RaptorQ se utiliza para generar cualquier número de símbolos de reparación a partir de un bloque de origen que consiste en K símbolos de origen colocados en un bloque de origen extendido C'. La Figura 4 muestra la descripción general de la codificación.

[316] El primer paso de la codificación es construir un bloque de origen ampliado añadiendo cero o más símbolos de relleno de modo que el número total de símbolos, K', sea uno de los valores enumerados en la Sección 5.6. Cada símbolo de relleno consiste en T octetos, donde el valor de cada octeto es cero. K' DEBE seleccionarse como el valor más pequeño de K' de la tabla de la Sección 5.6 que sea mayor o igual que K.

5

10

15

20

25

30

35

40

45

imagen3

Figura 4: Visión general de la codificación

[317] Sean C'[0], C'[K-1] indicados como los K símbolos de origen.

[318] Sean C'[K], ..., C'[K'-1] indicados como los K'-K símbolos de relleno, que están todos fijados en bits cero. Entonces, C'[0], ..., C'[K'-1] son los símbolos del bloque de origen extendido sobre el cual se realizan la codificación y decodificación.

[319] En lo que resta de esta descripción, estos símbolos de relleno se considerarán como símbolos de origen adicionales y se mencionarán como tales. Sin embargo, estos símbolos de relleno no son parte de los símbolos de codificación, es decir, no se envían como parte de la codificación. En un receptor, el valor de K' puede calcularse basándose en K, luego el receptor puede insertar K'-K símbolos de relleno al final de un bloque de origen de K' símbolos de origen y recuperar los restantes K símbolos de origen del bloque de origen a partir de los símbolos de codificación recibidos.

[320] La segunda etapa de la codificación es generar un número, L > K', de símbolos intermedios a partir de los K' símbolos de origen. En esta etapa, K' tuplos de origen (d[0], a[0], b[0], d 1 [0], a1[0], b1[0]), ..., (d[K'- 1], a[K'-1], b[K'- 1], d1[K'-1], a1[K'-1], b1[K'-1]) se generan utilizando el generador Tupla[] como se describe en la Sección 5.3.5.4. Los K' tuplos de origen y los ISI asociados a los K' símbolos de origen se usan para determinar L símbolos intermedios C[0], ..., C[L-1] a partir de los símbolos de origen, usando un proceso de codificación inversa. Este proceso puede realizarse mediante un proceso de decodificación de RaptorQ.

[321] Ciertas "relaciones de precodificación" deben mantenerse dentro de los L símbolos intermedios. La Sección 5.3.3.3 describe estas relaciones. La Sección 5.3.3.4 describe cómo se generan los símbolos intermedios a partir de los símbolos de origen.

[322] Una vez que se han generado los símbolos intermedios, pueden producirse símbolos de reparación. Para un símbolo de reparación con ISI X > K', se puede generar el tuplo de enteros no negativos, (d, a, b, dl, al, bl), usando el generador Tupla[] como se describe en la Sección 5.3.5.4. Luego, el (d, a, b, dl, al, bl)-tuplo y el ISI X se utilizan para generar el símbolo de reparación correspondiente a partir de los símbolos intermedios utilizando el generador Enc[] descrito en la Sección 5.3.5.3. El ESI correspondiente para este símbolo de reparación es entonces X- (K'-K). Téngase en cuenta que los símbolos de origen del bloque de origen extendido también se pueden generar usando el mismo proceso, es decir, para cualquier X < K', el símbolo generado usando este proceso tiene el mismo valor que C'[X].

5.3.3. Primera etapa de codificación: Generación de Símbolo Intermedio

5.3.3.1. General

[323] Esta etapa de codificación es una etapa de precodificación para generar los L símbolos intermedios C[0], ..., C[L-1] a partir de los símbolos de origen C'[0], ..., C'[K'- 1], donde L > K' se define en la Sección 5.3.3.3. Los símbolos intermedios están definidos de forma única por dos conjuntos de restricciones:

1. Los símbolos intermedios están relacionados con los símbolos de origen por un conjunto de tuplos de símbolos de origen y por los ISI de los símbolos de origen. La generación de los tuplos de símbolos de origen se

5

10

15

20

25

30

35

40

45

50

55

60

65

define en la Sección 5.3.3.2 utilizando el generador Tupla[] como se describe en la Sección 5.3.5.4.

2. Varias relaciones de precodificación se mantienen dentro de los propios símbolos intermedios. Estos se definen en la Sección 5.3.3.3

[324] La generación de los L símbolos intermedios se define luego en la Sección 5.3.3.4.

5.3.3.2. Tuplos de símbolos de origen

[325] Cada uno de los K' símbolos de origen está asociado a un tuplo de símbolos de origen (d[X], a[X], b[X], d1[X], a1[X], b1[X]) para 0 <= X < K'. Los tuplos de símbolos de origen se determinan usando el generador Tupla definido en la Sección 5.3.5.4 como:

Para cada X, 0 <= X < K'

(d[X], a[X], b[X], d1[X], a1[X], b1[X]) = Tupla[K, X]

5.3.3.3. Relaciones de precodificación

[326] Las relaciones de precodificación entre los L símbolos intermedios se definen requiriendo que un conjunto de S + H combinaciones lineales de los símbolos intermedios se evalúe como cero. Hay símbolos S símbolos de LDPC y H símbolos de HDPC y, por lo tanto, L = K'+ S + H. Otra partición de los L símbolos intermedios es en dos conjuntos, un conjunto de W símbolos LT y otro conjunto de P símbolos PI, y así también es el caso que L = W + P. Los P símbolos Pi se tratan de manera diferente que los W símbolos lT en el proceso de codificación. Los P símbolos PI consisten en los H símbolos de HDPC junto con un conjunto de U = P-H de los otros K' símbolos intermedios. Los W símbolos LT consisten en los S símbolos de LDPc junto con W-S de los otros K' símbolos intermedios. Los valores de estos parámetros se determinan a partir de K' como se describe a continuación, donde H(K'), S(K') y W(K') se obtienen de la Tabla 2 en la Sección 5.6.

[327] Sean o S = S(K') o H = H(K') o W = W(K')

o L = K' + S + H o P = L - W

o P1 indica el número primo más pequeño mayor o igual a P o U = P - H o B = W - S

o C[0], ..., C[B-1] indican los símbolos intermedios que son símbolos LT pero no símbolos de LDPC. o C[B], ..., C[B + S-1] indican los S símbolos de LDPC que también son símbolos LT. o C[W], ..., C[W + U-1] indican los símbolos intermedios que son símbolos PI pero no símbolos de HDPC. o C[LH], ..., C[L-1] indican los H símbolos de HDPC que también son símbolos PI.

[328] El primer conjunto de relaciones de precodificación, denominadas relaciones de LDPC, se describe a continuación y requiere que, al final de este proceso, el conjunto de símbolos D[0], ..., D[S-1] sean todos cero:

o Inicializar los símbolos D[0] = C[B], ..., D[S-1] C[B + S-1].

o Para i = 0, ..., B-1 hacer

* a = 1 + floor (i / S)

* b = i% S

* D[b] = D[b] + C[i]

* b = (b + a)% S

5

10

15

20

25

30

35

40

45

50

55

60

65

* D[b] = D[b] + C[i]

* b = (b + a)% S

* D[b] = D[b] + C[i]

o Para i = 0, S-1 hacer

* a = i% P

* b = (i + 1) % P

* D[i] = D[i] + C[W + a] + C[W + b]

[329] Recuérdese que la adición de símbolos ha de llevarse a cabo como se especifica en la Sección 5.7.

[330] Téngase en cuenta que las relaciones de LDPC tal como se definen en el algoritmo anterior son lineales, por lo que existe una matriz G_LDPC,1 de tamaño S x B, y una matriz G_LDPC,2 de tamaño S x P, tal que

G_LDPC,1 * Traspuesta de [(C[0], C[B-1])] + G_LDPC,2 * Traspuesta de

[(C[W], C[W + P-1])] + Traspuesta de [(C[B], C[B + S-1])] = 0

(La matriz G_LDPC,1 está definida por el primer ciclo en el algoritmo anterior, y G_LDPC,2 puede deducirse del segundo ciclo).

[331] El segundo conjunto de relaciones entre los símbolos intermedios C[0], ..., C[L-1] son las relaciones de HDPC y se definen de la siguiente manera:

Sean

o alfa indicador del octeto representado por el entero 2, como se define en la Sección 5.7.

o MT indica una matriz de octetos de tamaño H x (K' + S) donde, para j = 0, ..., K' + S-2, la entrada MT[i, j] es el octeto representado por el entero 1 si i = Azar [j + 1,6, H] o i = (Azar [j + 1,6, H] + Azar [j + 1,7, H-1 ] + 1)% H y MT[i, j] es el elemento cero para todos los otros valores de i, y para j = K' + S-1, MT[i, j] = alfaAAi para i = 0, ..., H-1.

o GAMMA indica una matriz de octetos de tamaño (K' + S) x (K' + S), donde

GAMMA [i, j] =

alfa (i-j) para i > = j,

0 en caso contrario

[332] Luego, la relación entre los primeros K' + S símbolos intermedios C[0], ..., C[K' + S-1] y los H símbolos de HDPC C[K' + S], ..., C[K' + S + H-1] está dada por:

Traspuesta de [C[K' + S], C[K' + S + H-1]] + MT * GAMMA *

Traspuesta de [C[0], ..., C[K' + S-1 ]] = 0,

donde '*' representa la multiplicación matricial estándar utilizando la multiplicación de octetos para definir la multiplicación entre una matriz de octetos y una matriz de símbolos (en particular, el vector columna de símbolos) y '+' indica la adición sobre vectores de octetos.

5.3.3.4. Símbolos intermedios

5.3.3.4.1. Definición

[333] Dados los K' símbolos de origen C'[0], C'[1], ..., C'[K'-1], los L símbolos intermedios C[0], C[1], ..., C[ L-1] son los valores de símbolos definidos de forma única que cumplen las siguientes condiciones:

1. Los K' símbolos de origen C'[0], C'[1], ..., C'[K'-1] satisfacen las K' restricciones

C'[X] = Enc[K', (C[0], ..., C[L-1]), (d[X], a[X], b[X], d1[X], a1[X], b1[X])], para todos los X, 0 <= X < K',

donde (d[X], a[X], b[X], d1[X], a1[X], b1[X]) = Tupla[K', X], Tupla[] se define en la Sección 5.3.5.4 y Enc[] se describe en la Sección 5.3.5.3.

2. Los L símbolos intermedios C[0], C[1], ..., C[L-1] satisfacen las relaciones de precodificación definidas en la

5

10

15

20

25

30

35

40

45

50

55

Sección 5.3.3.3

5.3.3.4.2. Procedimiento ejemplar para el cálculo de símbolos intermedios

[334] Esta sección describe un procedimiento posible para el cálculo de los L símbolos intermedios C[0], C[1], ..., C[L-1] que satisfacen las restricciones en la Sección 5.3.3.4.1

[335] Los L símbolos intermedios se pueden calcular de la siguiente manera:

Sean

o C indicador del vector columna de los L símbolos intermedios C[0], C[1], ... , C[L-1].

o D indica el vector columna que consiste en S+H símbolos cero seguidos por los K¡ símbolos de origen C'[0], C'[1], ..., C'[K'-1].

[336] Entonces, las restricciones anteriores definen una matriz A de octetos de tamaño L x L, tal que:

A * C = D

[337] La matriz A se puede construir de la siguiente manera:

Sean:

o G_LDPC,1 y G_LDPC,2 matrices de tamaño S x B y S x P, según se define en la Sección 5.3.3.3. o Sea G_HDPC la matriz de tamaño H x (K' + S) tal que

G_HDPC * Traspuesta de [(C[0], C[K' + S-1])] = Traspuesta de C[K' + S],

C[L-1],

es decir, G_HDPC = MT * GAMMA o Sea I_S la matriz de identidad de tamaño S x S o Sea I_H la matriz de identidad de tamaño H x H o Sea G_ENC la matriz de tamaño K' x L tal que

G_ENC * Traspuesta [(C[0], C[L-1])] = Traspuesta de C'[0], C'[1],

C[K'-1],

es decir, G_ENC[i, j] = 1 si y solo si C[j] está incluido en los símbolos que se suman para producir Enc[K', (C[0], ...,

C[L-1]), (d[i], a[i], b[i], d 1 [i], a1[i], b1[i])] y G_ENC[i, j] = 0 en caso contrario.

[338] Entonces:

o Las primeras S filas de A son iguales a G_LDPC,1 | I-S | G_LDPC,2. o Las siguientes H filas de A son iguales a G_HDPC | I_H. o Las restantes K' filas de A son iguales a G_ENC.

[339] La matriz A se representa en la Figura (Figura 5) a continuación:

5

10

15

20

25

30

35

40

45

U

H

--------------------------------------------------------------------------------------------------------1 G_LDPC,1: — T_S h----- G_LDPC, 2

G_HDPC: — I_H —

G EMC

Figura 5: La matriz A

[340] Los símbolos intermedios se pueden calcular entonces como:

C = (AAA-1)*D

[341] Los tuplos de origen se generan de forma que, para cualquier matriz K', A tenga rango completo y, por lo tanto, sea invertible. Este cálculo se puede realizar aplicando un proceso de decodificación de RaptorQ a los K' símbolos de origen C'[0], C'[1], ..., C'[K'-1] para producir los L símbolos intermedios C[0], C[1], ..., C[L-1].

[342] Para generar eficazmente los símbolos intermedios a partir de los símbolos de origen, se recomienda que se use una implementación eficaz del decodificador, tal como la descrita en la Sección 5.4.

5.3.4. Segunda etapa de codificación: Codificación

[343] En la segunda etapa de codificación, el símbolo de reparación con ISI X (X > = K') se genera aplicando el generador Enc[K', (C[0], c[1], ..., C[L-1]), (d, a, b, d1, a1, b1)], definido en la Sección 5.3.5.3, a los L símbolos intermedios C[0], C[1], ..., C[L-1], utilizando el tuplo (d, a, b, d1, a1, b1) = Tupla[K', X].

5.3.5. Generadores

5.3.5.1. Generador de números aleatorios

[344] El generador de números aleatorios Azar[y, i, m] se define de la siguiente manera, donde y es un entero no negativo, i es un entero no negativo menor que 256 y m es un entero positivo y el valor producido es un número entero entre 0 y m-1. Sean V0, V1, V2 y V3 las formaciones proporcionadas en la Sección 5.5.

[345] Sean

o x0 = (y + i) mod 2 AA 8 o x1 = (floor (y / 2 aa 8) + i) mod 2 aa 8 o x2 = (floor (y / 2 aa 16) + i) mod 2 aa 8 o x3 = (floor (y / 2 aa 24) + i) mod 2 aa 8

[346] Entonces

Azar[y, i, m] = (V0 [x0] A V1[x1] A V2[x2] A V3[x3])% m

5.3.5.2. Generador de Grados

[347] El generador de grados Grado[v] se define de la siguiente manera, donde v es un entero no negativo que es menor que 2 aa 20 = 1048576. Dado v, hallar el índice d en la Tabla 1 tal que f[d-1 ] <= v < f[d], y fijar Grado[v] = min (d, W-2). Recuérdese que W se obtiene a partir de K' como se describe en la Sección 5.3.3.3.

5

10

15

20

25

30

índice d: f [d] índice d f [d]

0
0: 1 5243

2: 529531 3 704294

4: 791675 5 844104

6: 879057 7 904023

8: 922747 9 937311

10: 948962 11 958494

12: 966438 13 973160

14: 978921 15 983914

16: 988283 17 992138

18: 995565 19 998631

20: 1001391 21 1003887

22: 1006157 23 1008229

24: 1010129 25 1011876

26: 1013490 27 1014983

28: 1016370 29 1017662

30: 1048576

Tabla 1: Define la distribución de grados para los símbolos de codificación 5.3.5.3. Generador de símbolos de codificación

[348] El generador de símbolos de codificación Enc[K', (C[0], C[1], ..., C[L-1]), (d, a, b, dl, al, bl)] toma las siguientes entradas :

o K' es el número de símbolos de origen para el bloque de origen extendido. Sean L, W, B, S, P y P1 obtenidos a partir de K ' como se describe en la Sección 5.3.3.3.

o (C[0], C[1], ..., C[L-1]) es la formación de L símbolos intermedios (sub-símbolos) generados como se describe en la Sección 5.3.3.4

o (d, a, b, dl, al, b1) es un tuplo de origen determinado a partir del ISI X, utilizando el generador Tupla definido en la Sección 5.3.5.4, según lo cual

* d es un entero positivo que indica un grado LT de símbolo de codificación

* a es un número entero positivo entre 1 y W-1, inclusive

* b es un número entero no negativo entre 0 y W-1, inclusive

* dl es un entero positivo que tiene un valor de 2 o 3 inclusive, que indica un grado PI de símbolo de codificación

* al es un número entero positivo entre 1 y P1-1, inclusive

* bl es un número entero no negativo entre 0 y P1-1, inclusive

5

10

15

20

25

30

35

40

45

50

55

60

65

[349] El generador de símbolos de codificación produce un único símbolo de codificación como salida (denominado resultado), de acuerdo al siguiente algoritmo:

o resultado = C [b]

o Para j = 1, ..., d-1 hacer

* b = (b + a)% W

* resultado = resultado + C[b]

o Mientras (b1 > = P) hacer bl = (bl + al)% P1 o resultado = resultado + C[W + b1] o Para j = 1, ..., d1-1 hacer

* b1 = (b1 + a1) % P1

* Mientras (b1 > = P) hacer b1 = (b1 + a1)% P1

* resultado = resultado + C[W + b1] o Devolver resultado

5.3.5.4. Generador de Tuplo

[350] El generador de tuplos Tupla[K', X] toma las siguientes entradas: o K' - La cantidad de símbolos de origen en el bloque de origen extendido o X - Un ISI

[351] Sean

o L determinado a partir de K' como se describe en la Sección 5.3.3.3 o J = J(K') el índice sistemático asociado a K', como se define en la Tabla 2 en la Sección 5.6

[352] La salida del generador de tuplos es un tuplo, (d, a, b, dl, al, bl), determinado de la siguiente manera: o A = 53591 + J * 997

o si (A% 2 == 0) {A = A + 1} o B = 10267 * (J + 1) o y = (B + X * A)% 2 AA 32 o v = Azar [y, 0, 2 aa 20] o d = Grado [v] o a = 1 + Azar [y, 1, W-1] o b = Azar [y, 2, W]

o si (d <4) {d1 = 2 + Azar [X, 3, 2]}; en caso contrario {d1 = 2} o a1 = 1 + Azar [X, 4, P1-1] o b1 = Azar [X, 5, P1]

5.4. Ejemplo de decodificador de FEC

5.4.1. General

5

10

15

20

25

30

35

40

45

50

55

60

65

[353] Esta sección describe un algoritmo de decodificación eficaz para el código de RaptorQ introducido en esta especificación. Téngase en cuenta que cada símbolo de codificación recibido es una combinación lineal conocida de los símbolos intermedios. De modo que cada símbolo de codificación recibido proporciona una ecuación lineal entre los símbolos intermedios, lo que, junto con las relaciones de precodificación lineal conocidas entre los símbolos intermedios, proporciona un sistema de ecuaciones lineales. Por lo tanto, cualquier algoritmo para resolver sistemas de ecuaciones lineales puede decodificar con éxito los símbolos intermedios y, por lo tanto, los símbolos de origen. Sin embargo, el algoritmo elegido tiene un efecto importante en la eficacia de cálculo de la decodificación.

5.4.2. Decodificación de un bloque de origen extendido

5.4.2.1. General

[354] Se supone que el decodificador conoce la estructura del bloque de origen que ha de decodificar, incluido el tamaño del símbolo, T, y el número K de símbolos en el bloque de origen y el número K' de símbolos de origen en el bloque de origen extendido.

[355] A partir de los algoritmos descritos en la sección 5.3, el decodificador de RaptorQ puede calcular el número total L = K' + S + H de los símbolos intermedios y determinar cómo se generaron a partir del bloque de origen ampliado a decodificar. En esta descripción, se supone que los símbolos de codificación recibidos para el bloque de origen ampliado a decodificar se pasan al decodificador. Además, para cada uno de tales símbolos de codificación se supone que el número y el conjunto de símbolos intermedios, cuya suma es igual al símbolo de codificación, se pasan al decodificador. En el caso de los símbolos de origen, incluidos los símbolos de relleno, los tuplos de los símbolos de origen que se describen en la Sección 5.3.3.2 indican el número y el conjunto de símbolos intermedios que se suman para dar cada símbolo de origen.

[356] Sea N >= K' el número de símbolos de codificación recibidos para decodificar, incluidos los símbolos de relleno para un bloque de origen extendido y sea M = S + H + N. Luego, con la notación de la Sección 5.3.3.4.2, tenemos A * C = D.

[357] La decodificación de un bloque de origen extendido es equivalente a decodificar C a partir de A y D conocidos. Es claro que C puede decodificarse si y solo si el rango de A es L. Una vez que C ha sido decodificado, los símbolos de origen faltantes pueden obtenerse usando el los tuplos de símbolos de origen para determinar el número y el conjunto de símbolos intermedios que se deben sumar para obtener cada símbolo de origen faltante.

[358] La primera etapa para decodificar C es formar una planificación de decodificación. En esta etapa A se convierte, utilizando la eliminación Gaussiana (utilizando operaciones de fila y reordenamientos de fila y columna) y después de descartar M - L filas, en la matriz de identidad de tamaño L por L. La planificación de decodificación consiste en la secuencia de operaciones de filas y reordenamientos de filas y columnas durante el proceso de eliminación de Gauss, y solo depende de A y no de D. La decodificación de C a partir de D puede tener lugar simultáneamente con la formación de la planificación de decodificación , o la decodificación puede tener lugar después basándose en la planificación de decodificación.

[359] La correspondencia entre la planificación de decodificación y la decodificación de C es la siguiente. Sea c[0] = 0, c[1] = 1, ..., c [L-1] = L-1 y d [0] = 0, d [1] = 1, ..., d [ M-1] = M-1, inicialmente.

o Cada vez que se agrega un múltiplo, beta, de la fila i de A a la fila i' en la planificación de decodificación, luego, en el proceso de decodificación, el símbolo beta * D [d [i]] se agrega al símbolo D[d [i']].

o Cada vez que una fila i de A se multiplica por un octeto beta, en el proceso de decodificación, el símbolo D[d[i]] también se multiplica por beta.

o Cada vez que se intercambia la fila i con la fila i' en la planificación de decodificación, luego, en el proceso de decodificación, el valor de d[i] se intercambia con el valor de d[i'].

o Cada vez que la columna j se intercambia con la columna j' en la planificación de decodificación, luego, en el proceso de decodificación, el valor de c[j] se intercambia con el valor de c[j'].

[360] A partir de esta correspondencia, está claro que el número total de operaciones sobre símbolos en la decodificación del bloque de origen extendido es el número de operaciones en filas (no intercambios) en la eliminación Gaussiana. Como A es la matriz de identidad de tamaño L por L después de la eliminación Gaussiana y después de descartar las últimas M - L filas, es claro, al final de la decodificación exitosa, que los L símbolos D[d[0]], D[d[1] ], ..., D[d[L-1]] son los valores de los L símbolos C[c[0]], C[c[1]], ..., C[c[L-1]].

[361] El orden en el que se realiza la eliminación Gaussiana para formar la planificación de decodificación no influye en cuanto a si la decodificación es exitosa o no. Sin embargo, la velocidad de la decodificación depende en

5

10

15

20

25

30

35

40

45

gran medida del orden en que se realiza la eliminación Gaussiana. (Además, mantener una representación rala de A es crucial, aunque esto no se describe aquí). El resto de esta sección describe un orden en el cual la eliminación Gaussiana podría realizarse, que es relativamente eficaz.

5.4.2.2. Primera fase

[362] En la primera fase de la eliminación Gaussiana, la matriz A se divide conceptualmente en sub-matrices y, además, se crea una matriz X. Esta matriz tiene tantas filas y columnas como A, y será una matriz triangular inferior durante toda la primera fase. Al comienzo de esta fase, la matriz A se copia en la matriz X.

[363] Los tamaños de las sub-matrices están parametrizados por enteros no negativos i y u, que se inicializan en 0 y P, el número de símbolos PI, respectivamente. Las sub-matrices de A son:

1. La sub-matriz I definida por la intersección de las primeras i filas y las primeras i columnas. Esta es la matriz de identidad al final de cada etapa en la fase.

2. La sub-matriz definida por la intersección de las primeras i filas y todas menos las primeras i columnas y las últimas u columnas. Todas las entradas de esta sub-matriz son cero.

3. La sub-matriz definida por la intersección de las primeras i columnas y todas menos las primeras i filas. Todas las entradas de esta sub-matriz son cero.

4. La sub-matriz U definida por la intersección de todas las filas y las últimas u columnas.

5. La sub-matriz V formada por la intersección de todas menos las primeras i columnas y las últimas u columnas y todas menos las primeras i filas.

[364] La Figura 6 ilustra las sub-matrices de A. Al comienzo de la primera fase V = A. En cada etapa, se elige una fila de A.

imagen4

[365] El siguiente gráfico definido por la estructura de V se usa para determinar qué fila de A se elige. Las columnas que intersecan a V son los nodos en el gráfico, y las filas que tienen exactamente 2 entradas distintas de cero en V y no son filas de HDPC son los bordes del gráfico que conectan las dos columnas (nodos) en las posiciones de los dos unos. Un componente en este gráfico es un conjunto máximo de nodos (columnas) y bordes (filas) de manera que haya un trayecto entre cada par de nodos / bordes en el gráfico. El tamaño de un componente es la cantidad de nodos (columnas) en el componente.

[366] Hay a lo sumo L etapas en la primera fase. La fase finaliza exitosamente cuando i + u = L, es decir, cuando V y la sub-matriz de todos ceros por encima de V han desaparecido y A consiste en I, la sub-matriz de todos ceros debajo de I, y U. La fase termina sin éxito, con fallo de decodificación, si en alguna etapa anterior a la desaparición de V no existe ninguna fila distinta de cero en V para elegir en esa etapa. En cada paso, una fila de A se elige de la siguiente manera:

o Si todas las entradas de V son cero, entonces no se elige ninguna fila y la decodificación falla. o Sea r el entero mínimo tal que al menos una fila de A tenga exactamente r unos en V.

5

10

15

20

25

30

35

40

45

50

55

60

65

* Si r != 2, entonces elegir una fila con exactamente r unos en V con el grado original mínimo entre todas dichas filas, excepto que las filas de HDPC no deberían elegirse hasta que se hayan procesado todas las filas no de HDPC.

* Si r = 2, elegir cualquier fila con exactamente 2 unos en V que sea parte de un componente de tamaño máximo en el gráfico descrito anteriormente, que está definido por V.

[367] Después de elegir la fila en esta etapa, la primera fila de A que interseca a V se intercambia con la fila elegida de modo que la fila elegida sea la primera fila que interseca a V. Las columnas de A entre las que intersecan a V se reordenan de modo que uno de los r unos en la fila elegida aparezca en la primera columna de V y de modo que los restantes r-1 unos aparezcan en las últimas columnas de V. Las mismas operaciones de fila y columna también se realizan en la matriz X. Luego, un múltiplo adecuado de la fila elegida se agrega a todas las otras filas de A debajo de la fila elegida que tengan una entrada distinta de cero en la primera columna de V.

Específicamente, si una fila debajo de la fila elegida tiene una entrada beta en la primera columna de V, y la fila elegida tiene una entrada alfa en la primera columna de V, entonces beta / alfa, multiplicado por la fila elegida, se añade a esta fila para dejar un valor cero en la primera columna de V. Finalmente, i se incrementa en 1 y u se incrementa en r-1, lo que completa la etapa.

[368] Téngase en cuenta que la eficacia se puede mejorar si las operaciones de fila identificadas anteriormente no se realizan realmente hasta que la fila afectada se elija durante el proceso de decodificación. Esto evita el procesamiento de operaciones de filas para filas que no se utilizan eventualmente en el proceso de decodificación y, en particular, evita aquellas filas para las que beta != 1 hasta que realmente se requieran. Además, las operaciones de fila requeridas para las filas de HDPC pueden realizarse para todas dichas filas en un proceso, utilizando el algoritmo descrito en la Sección 5.3.3.3.

5.4.2.3. Segunda fase

[369] En este momento, todas las entradas de X fuera de las primeras i filas e i columnas se descartan, de modo que X tenga forma triangular inferior. Las últimas i filas y columnas de X se descartan, de modo que X ahora tiene i filas e i columnas. La sub-matriz U se subdivide adicionalmente en las primeras i filas, U_superior, y las restantes M - i filas, U_inferior. La eliminación Gaussiana se realiza en la segunda fase en U_inferior para determinar si su rango es menor que u (fallo de decodificación) o para convertirla en una matriz donde las primeras u filas son la matriz de identidad (éxito de la segunda fase). Llamemos I_u a esta matriz de identidad de tamaño u por u. Las M - L filas de A que intersecan a U_inferior - I_u se descartan. Después de esta fase A tiene L filas y L columnas.

5.4.2.4. Tercera fase

[370] Después de la segunda fase, la única parte de A que debe fijarse en cero para terminar la conversión de A en la matriz de identidad de tamaño L por L es U_superior. El número de filas i de la sub-matriz U_superior es generalmente mucho más grande que el número de columnas u de U_superior. Además, en este momento, la matriz U_superior es habitualmente densa, es decir, el número de entradas distintas de cero de esta matriz es grande. Para reducir esta matriz a una forma rala, la secuencia de operaciones realizadas para obtener la matriz U_inferior necesita invertirse. Con este fin, la matriz X se multiplica por la sub-matriz de A que consiste en las primeras i filas de A. Después de esta operación, la sub-matriz de A que consiste en la intersección de las primeras i filas y columnas es igual a X, mientras que la matriz U_superior está transformada en una forma rala.

5.4.2.5. Cuarta fase

[371] Para cada una de las primeras i filas de U_superior, hacer lo siguiente: si la fila tiene una entrada distinta de cero en la posición j, y si el valor de esa entrada distinta de cero es b, entonces añada a esta fila b veces la fila j de I_u. Después de esta etapa, la sub-matriz de A que consiste en la intersección de las primeras i filas y columnas es igual a X, la sub-matriz U_superior consiste en ceros, la sub-matriz que consiste en la intersección de las últimas u filas y las primeras i columnas consiste en ceros y la sub-matriz que consiste en las últimas u filas y columnas es la matriz I_u.

5.4.2.6. Quinta fase

[372] Para j de 1 a i, realizar las siguientes operaciones:

1. si A[j, j] no es uno, entonces dividir la fila j de A entre [A,j].

2. Para 1 de 1 a j-1, si A [j, 1] no es cero, entonces añadir A[j, 1 ] multiplicado por la fila 1 de A a la fila j de A.

[373] Después de esta fase A es la matriz de identidad de tamaño L por L y se ha formado con éxito una planificación de decodificación completa. Entonces, la decodificación correspondiente, que consiste en sumar

5

10

15

20

25

30

35

40

45

50

55

60

65

símbolos de codificación conocidos, se puede ejecutar para recuperar los símbolos intermedios en función de la planificación de decodificación. Los tuplos asociados a todos los símbolos de origen se calculan de acuerdo a la Sección 5.3.3.2. Los tuplos para los símbolos de origen recibidos se usan en la decodificación. Los tuplos para los símbolos de origen faltantes se utilizan para determinar qué símbolos intermedios deben sumarse para recuperar los símbolos de origen faltantes.

5.5. Números al azar

[374] Las cuatro formaciones V0, V1, V2 y V3 utilizadas en la Sección 5.3.5.1 se proporcionan a continuación. Hay 256 entradas en cada una de las cuatro formaciones. La indización en cada formación comienza en 0 y las entradas son enteros sin signo de 32 bits.

5.5.1. La tabla V0

[375] 251291136, 3952231631, 3370958628, 4070167936, 123631495, 3351110283, 3218676425, 2011642291, 774603218, 2402805061, 1004366930, 1843948209, 428891132, 3746331984, 1591258008, 3067016507, 1433388735, 504005498, 2032657933, 3419319784, 2805686246, 3102436986, 3808671154, 2501582075, 3978944421, 246043949, 4016898363, 649743608, 1974987508, 2651273766, 2357956801, 689605112, 715807172, 2722736134, 191939188, 3535520147, 3277019569, 1470435941, 3763101702, 3232409631, 122701163, 3920852693, 782246947, 372121310, 2995604341, 2045698575, 2332962102, 4005368743, 218596347, 3415381967, 4207612806, 861117671, 3676575285, 2581671944, 3312220480, 681232419, 307306866, 4112503940, 1158111502, 709227802, 2724140433, 4201101115, 4215970289, 4048876515, 3031661061, 1909085522, 510985033, 1361682810, 129243379, 3142379587, 2569842483, 3033268270, 1658118006, 932109358, 1982290045, 2983082771, 3007670818, 3448104768, 683749698, 778296777, 1399125101, 1939403708, 1692176003, 3868299200, 1422476658, 593 093658, 1878973865, 2526292949, 1591602827, 3986158854, 3964389521, 2695031039, 1942050155, 424618399, 1347204291, 2669179716, 2434425874, 2540801947, 1384069776, 4123580443, 1523670218, 2708475297, 1046771089, 2229796016, 1255426612, 4213663089, 1521339547, 3041843489, 420130494, 10677091, 515623176, 3457502702, 2115821274, 2720124766, 3242576090, 854310108, 425973987, 325832382, 1796851292, 2462744411, 1976681690, 1408671665, 1228817808, 3917210003, 263976645, 2593736473, 2471651269, 4291353919, 650792940, 1191583883, 3046561335, 2466530435, 2545983082, 969168436, 2019348792, 2268075521, 1169345068, 3250240009, 3963499681, 2560755113, 911182396, 760842409, 3569308693, 2687243553, 381854665, 2613828404, 2761078866, 1456668111, 883760091, 3294951678, 1604598575, 1985308198, 1014570543, 2724959607, 3062518035, 3115293053, 138853680, 4160398285, 3322241130, 2068983570, 2247491078, 3669524410, 1575146607, 828029864, 3732001371, 3422026452, 3370954177, 4006626915, 543812220, 1243116171, 39 28372514, 2791443445, 4081325272, 2280435605, 885616073, 616452097, 3188863436, 2780382310, 2340014831, 1208439576, 258356309, 3837963200, 2075009450, 3214181212, 3303882142, 880813252, 1355575717, 207231484, 2420803184, 358923368, 1617557768, 3272161958, 1771154147, 2842106362, 1751209208, 1421030790, 658316681, 194065839, 3241510581, 38625260, 301875395, 4176141739, 297312930, 2137802113, 1502984205, 3669376622, 3728477036, 234652930, 2213589897, 2734638932, 1129721478, 3187422815, 2859178611, 3284308411, 3819792700, 3557526733, 451874476, 1740576081, 3592838701, 1709429513, 3702918379, 3533351328, 1641660745, 179350258, 2380520112, 3936163904, 3685256204, 3156252216, 1854258901, 2861641019, 3176611298, 834787554, 331353807, 517858103, 3010168884, 4012642001, 2217188075, 3756943137, 3077882590, 2054995199, 3081443129, 3895398812, 1141097543, 2376261053, 2626898255, 2554703076, 401233789, 1460049922, 678083952, 1064990737, 940909784, 1673396780, 528881783, 1712547446,3629685652, 1358 307511

5.5.2. La tabla V1

[376] 807385413, 2043073223, 3336749796, 1302105833, 2278607931, 541015020, 1684564270

3508252125, 1768346005, 1270451292, 2603029534, 915180310, 3754787998, 700503826, 2131559305, 1679385496, 3431345226, 1779595665, 3068494238, 420600373, 2868446243, 311689386, 259047959,

3006865921, 4293710613, 3501256572, 998007483, 3044194711, 486690751, 2686640734, 2394526209, 415906198, 19296841, 2402488407, 2137119134,

2681403713, 1047144830, 2982173936, 910285038, 506322719, 176010738, 1865471968, 2619324712,

3618966336, 2111320126, 1093955153, 957978696, 2694156259, 1927339682, 1650555729, 183933047, 1595995433, 1780701372, 2463145963, 307281463, 522074127, 146352474, 4104915256, 3029415884,

3041418372, 2258059298, 2139377204, 3243642973, 1963216666, 3509855005, 2358481858, 747331248, 1888833893, 2914085525, 4161315584, 1273113343,

372709334,

2049387273, 3891424859, 2152948345, 4114760273, 1308908630, 224437350, 4065424007, 3638665944, 1424062773, 1033448464, 4050396853, 3302235057, 4057180909, 1575367248, 4151214153, 110249784,

499288295, 1205710710, 2997199489, 640417429,

2521660077, 49993987, 3843885867, 4201106668, 1744097284, 579965637, 2037662632, 852173610,

4187576520, 2589870048, 989448887, 3292758024, 564829442, 1996870325, 339697593, 4071072948,

892010560, 185460107 8, 1873407527, 2498544695, 3061444337, 2067387204, 228962564, 3904109414, 3237929991, 3852995239, 2398693510, 3754138664, 3545667983, 332038910, 976628269, 3123492423,

3226247917, 3674004636, 2698992189, 3453843574, 1957348676, 1097574450, 2435697214, 3870972145, 3269644828, 3681293816, 412536684, 1156034077,

5

10

15

20

25

30

35

40

45

50

55

60

65

3823026442, 1066971017, 3598330293, 1979273937, 2079029895, 1195045909, 1071986421, 2712821515, 3377754595, 2184151095, 750918864, 2585729879, 4249895712, 1832579367, 1192240192, 946734366, 31230688, 3174399083, 3549375728, 1642430184, 1904857554, 861877404, 3277825584, 4267074718, 3122860549, 666423581, 644189126, 226475395, 307789415, 1196105631, 3191691839, 782852669, 1608507813, 1847685900, 40697668 76, 3931548641, 2526471011, 766865139, 2115084288, 4259411376, 3323683436, 568512177, 3736601419, 1800276898, 4012458395, 1823982, 27980198, 2023839966, 869505096, 431161506, 1024804023, 1853869307, 3393537983, 1500703614, 3019471560, 1351086955, 3096933631, 3034634988, 2544598006, 1230942551, 3362230798, 159984793, 491590373, 3993872886, 3681855622, 903593547, 3535062472, 1799803217, 772984149, 895863112, 1899036275, 4187322100, 101856048, 234650315, 3183125617, 3190039692, 525584357, 1286834489, 455810374, 1869181575, 922673938, 3877430102, 3422391938, 1414347295, 1971054608, 3061798054, 830555096, 2822905141, 167033190, 1079139428, 4210126723, 3593797804, 429192890, 372093950, 1779187770, 3312189287, 204349348, 452421568, 2800540462, 3733109044, 1235082423, 1765319556, 3174729780, 3762994475, 3171962488, 442160826, 198349622, 45942637, 1324086311, 2901868599, 678860040, 3812229107, 19936821, 1119590141, 3640121682, 3545931032, 2102949142, 2828208598, 3603378023, 4135048896

5.5.3. La tabla V2

[377] 1629829892, 282540176, 2794583710, 496504798, 2990494426, 3070701851, 2575963183, 4094823972,

2775723650, 4079480416, 176028725, 2246241423, 3732217647, 2196843075, 1306949278, 4170992780,

4039345809, 3209664269, 3387499533, 293063229, 3660290503, 2648440860, 2531406539, 3537879412,

773374739, 4184691853, 1804207821, 3347126643, 3479377103, 3970515774, 1891731298, 2368003842,

3537588307, 2969158410, 4230745262, 831906319, 2935838131, 264029468, 120852739, 3200326460,

355445271, 2296305141, 1566296040, 1760127056, 20073893, 3427103620, 2866979760, 2359075957,

2025314291, 1725696734, 3346087406, 2690756527, 99815156, 4248519977, 2253762642, 3274144518,

598024568, 3299672435, 556579346, 4121041856, 2896948975, 3620123492, 918453629, 3249461198,

2231414958, 3803272287, 3657597946, 2588911389, 242262274, 1725007475, 2026427718, 46776484,

2873281403, 2919275846, 3177933051, 1918859160, 2517854537, 1857818511, 3234262050, 479353687,

200201308, 2801945841, 1621715769, 483977159, 423502325, 368 9396064, 1850168397, 3359959416,

3459831930, 841488699, 3570506095, 930267420, 1564520841, 2505122797, 593824107, 1116572080,

819179184, 3139123629, 1414339336, 1076360795, 512403845, 177759256, 1701060666, 2239736419,

515179302, 2935012727, 3821357612, 1376520851, 2700745271, 966853647, 1041862223, 715860553,

171592961, 1607044257, 1227236688, 3647136358, 1417559141, 4087067551, 2241705880, 4194136288,

1439041934, 20464430, 119668151, 2021257232, 2551262694, 1381539058, 4082839035, 498179069,

311508499, 3580908637, 2889149671, 142719814, 1232184754, 3356662582, 2973775623, 1469897084,

1728205304, 1415793613, 50111003, 3133413359, 4074115275, 2710540611, 2700083070, 2457757663,

2612845330, 3775943755, 2469309260, 2560142753, 3020996369, 1691667711, 4219602776, 1687672168,

1017921622, 2307642321, 368711460, 3282925988, 213208029, 4150757489, 3443211944, 2846101972,

4106826684, 4272438675, 2199416468, 3710621281, 497564971, 285138276, 765042313, 916220877,

3402623607, 2768784621, 1722849 097, 3386397442, 487920061, 3569027007, 3424544196, 217781973,

2356938519, 3252429414, 145109750, 2692588106, 2454747135, 1299493354, 4120241887, 2088917094,

932304329, 1442609203, 952586974, 3509186750, 753369054, 854421006, 1954046388, 2708927882,

4047539230, 3048925996, 1667505809, 805166441, 1182069088, 4265546268, 4215029527, 3374748959,

373532666, 2454243090, 2371530493, 3651087521, 2619878153, 1651809518, 1553646893, 1227452842,

703887512, 3696674163, 2552507603, 2635912901, 895130484, 3287782244, 3098973502, 990078774,

3780326506, 2290845203, 41729428, 1949580860, 2283959805, 1036946170, 1694887523, 4880696, 466000198, 2765355283, 3318686998, 1266458025, 3919578154, 3545413527, 2627009988, 3744680394, 1696890173,

3250684705, 4142417708, 915739411, 3308488877, 1289361460, 2942552331, 1169105979, 3342228712,

698560958, 1356041230, 2401944293, 107705232, 3701895363, 903928723, 3646581385, 844950914,

1944371367, 3863894844, 2946773319, 1972431613, 1706989237, 29917467, 3497665928

5.5.4. La tabla V3

[378] 1191369816, 744902811, 2539772235, 3213192037, 3286061266, 1200571165, 2463281260, 754888894, 714651270, 1968220972, 3628497775, 1277626456, 1493398934, 364289757, 2055487592, 3913468088, 2930259465, 902504567, 3967050355, 2056499403, 692132390, 186386657, 832834706, 859795816, 1283120926, 2253183716, 3003475205, 1755803552, 2239315142, 4271056352, 2184848469, 769228092, 1249230754, 1193269205, 2660094102, 642979613, 1687087994, 2726106182, 446402913, 4122186606, 3771347282, 37667136, 192775425, 3578702187, 1952659096, 3989584400, 3069013882, 2900516158, 4045316336, 3057163251, 1702104819, 4116613420, 3575472384, 2674023117, 1409126723, 3215095429, 1430726429, 2544497368, 1029565676, 1855801827, 4262184627, 1854326881, 2906728593, 3277836557, 2787697002, 2787333385, 3105430738, 2477073192, 748038573, 1088396515, 1611204853, 201964005, 3745818380, 3654683549, 3816120877, 3915783622, 2563198722, 1181149055, 33158084, 3723047845, 3790270906, 3832415204, 2959617497, 372900708, 1286738499, 1932439099, 3677748309, 2454711182, 2757856469, 2134027055, 2780052465, 3190347618, 3758510138, 3626329451, 1120743107, 1623585693, 1389834102, 2719230375, 3038609003, 462617590, 260254189, 3706349764, 2556762744, 2874272296,

5

10

15

20

25

30

2502399286, 4216263978, 2683431180, 2168560535, 3561507175, 668095726, 680412330, 3726693946, 4180630637, 3335170953, 942140968, 2711851085, 2059233412, 4265696278, 3204373534, 232855056, 881788313, 2258252172, 2043595984, 3758795150, 3615341325, 2138837681, 1351208537, 2923692473, 3402482785, 2105383425, 2346772751, 499245323, 3417846006, 2366116814, 2543090583, 1828551634, 3148696244, 3853884867, 1364737681, 2200687771, 2689775688, 232720625, 4071657318, 2671968983, 3531415031, 1212852141, 867923311, 3740109711, 1923146533, 3237071777, 3100729255, 3247856816, 906742566, 4047640575, 4007211572, 3495700105, 1171285262, 2835682655, 1634301229, 3115169925, 2289874706, 2252450179, 944880097, 371933491, 1649074501, 2208617414, 2524305981, 2496569844, 2667037160, 12575 50794, 3399219045, 3194894295, 1643249887, 342911473, 891025733, 3146861835, 3789181526, 938847812, 1854580183, 2112653794, 2960702988, 1238603378, 2205280635, 1666784014, 2520274614, 3355493726, 2310872278, 3153920489, 2745882591, 1200203158, 3033612415, 2311650167, 1048129133, 4206710184, 4209176741, 2640950279, 2096382177, 4116899089, 3631017851, 4104488173, 1857650503, 3801102932, 445806934, 3055654640, 897898279, 3234007399, 1325494930, 2982247189, 1619020475, 2720040856, 885096170, 3485255499, 2983202469, 3891011124, 546522756, 1524439205, 2644317889, 2170076800, 2969618716, 961183518, 1081831074, 1037015347, 3289016286, 2331748669, 620887395, 303042654, 3990027945, 1562756376, 3413341792, 2059647769, 2823844432, 674595301, 2457639984, 4076754716, 2447737904, 1583323324, 625627134, 3076006391, 345777990, 1684954145, 879227329, 3436182180, 1522273219, 3802543817, 1456017040, 1897819847, 2970081129, 1382576028, 3820044861, 1044428167, 612252599, 3340478395, 2150613904, 3397625662, 3573635640,3432275192

5.6. Indices sistemáticos y otros parámetros

[379] La Tabla 2 a continuación especifica los valores con soporte de K'. La tabla también especifica, para cada valor con soporte de K', el índice sistemático J(K'), el número H(K') de símbolos de HDPC, el número S(K') de símbolos de LDPC y el número W(K') de los símbolos LT. Para cada valor de K', los valores correspondientes de S(K') y W(K') son números primos.

[380] El índice sistemático J(K') está diseñado para tener la propiedad de que el conjunto de tuplos de símbolos de origen (d[0], a[0], b[0], d1[0], a1[0], b1 [0]), ..., (d[K'-1], a[K'-1], b[K'-1], d1[K'-1], a1[K'-1], b1[K'-1]) son tales que los L símbolos intermedios están definidos de forma única, es decir, la matriz A en la Figura 6 tiene rango completo y, por lo tanto, es invertible.

K': J(K’ ) S (K ’ ) H (K' > W(K' )

10: 254 7 10 17

12: 630 7 - “ + 10 - - + 19

—: — — - ~ + —
—

Claims

1. Un procedimiento de transmisión electrónica de datos a través de uno o más transmisores capaces de emitir una señal electrónica, en donde los datos a transmitir están representados por un conjunto ordenado de

5 símbolos de origen y los datos son transmitidos como una secuencia de símbolos codificados que

representan al menos una parte de la señal electrónica, comprendiendo el procedimiento:

obtener, en una forma legible electrónicamente, el conjunto ordenado de símbolos de origen;

10 generar un conjunto de símbolos intermedios a partir del conjunto ordenado de símbolos de origen, en

donde los símbolos de origen pueden regenerarse a partir del conjunto de símbolos intermedios;

designar conjuntos de los símbolos intermedios, antes de la transmisión, de modo que cada símbolo intermedio sea designado como un miembro de uno de los conjuntos de símbolos intermedios y que haya 15 al menos un primer conjunto de símbolos intermedios y un segundo conjunto de símbolos intermedios, y

en donde cada conjunto de símbolos intermedios tenga como miembros al menos un símbolo intermedio, en donde el primer conjunto de símbolos intermedios sea designado como no permanentemente inactivado, LT, para la decodificación de propagación de creencias, y el segundo conjunto de símbolos intermedios sea designado como símbolos para ser permanentemente inactivados para la decodificación 20 de propagación de creencias, en donde los símbolos permanentemente inactivados, PI, son símbolos a

despejar por separado de la decodificación de propagación de creencias; y

generar una pluralidad de símbolos codificados, en donde un símbolo codificado se genera a partir de uno o más de los símbolos intermedios, en donde al menos un símbolo codificado se genera, directa o 25 indirectamente, a partir de una pluralidad de símbolos intermedios seleccionados entre una pluralidad de

los conjuntos de símbolos intermedios;

en donde generar la pluralidad de símbolos codificados comprende la codificación dinámica de los símbolos intermedios PI con un codificador PI, la codificación dinámica de los símbolos intermedios LT 30 con un codificador LT y la combinación de los símbolos intermedios PI y LT codificados en un combinador

para generar dicha pluralidad de símbolos codificados.

2. El procedimiento de la reivindicación 1, en el que cada símbolo codificado se genera a partir de un O exclusivo ("XOR") de un primer símbolo generado a partir de uno o más entre el primer conjunto de símbolos

35 intermedios y un segundo símbolo generado a partir de uno o más del segundo conjunto de símbolos

intermedios en dicho combinador.

3. El procedimiento de la reivindicación 2, en el que cada conjunto de símbolos intermedios tiene asociados al mismo distintos parámetros de codificación que comprenden al menos distintas distribuciones de grados, de 40 modo que cada símbolo codificado se genere a partir de una combinación de un primer símbolo, generado a

partir de uno o más entre el primer conjunto de símbolos intermedios que tienen una distribución de primer grado, y un segundo símbolo, generado a partir de uno o más entre el segundo conjunto de símbolos intermedios que tienen una distribución de segundo grado, diferente a la distribución de primer grado.

45 4. El procedimiento de la reivindicación 1, en el que cada símbolo codificado se genera a partir de una

combinación de un primer símbolo generado a partir de uno o más entre el primer conjunto de símbolos intermedios, y un segundo símbolo, generado a partir de uno o más entre el segundo conjunto de símbolos intermedios, en donde el primer símbolo se genera utilizando un proceso de codificación de reacción en cadena aplicado al primer conjunto de símbolos intermedios, en donde el segundo símbolo es un O exclusivo 50 ("XOR") de un primer número de símbolos elegidos aleatoriamente entre el segundo conjunto de símbolos

intermedios, en donde el primer número depende de un segundo número igual a un número de símbolos elegidos entre el primer conjunto para generar el primer símbolo, y en donde la combinación es el XOR del primer símbolo y del segundo símbolo.

55 5. El procedimiento de la reivindicación 1, en el que los símbolos intermedios comprenden el conjunto ordenado

de símbolos de origen y un conjunto de símbolos de origen redundantes, generados a partir del conjunto ordenado de símbolos de origen.

6. El procedimiento de la reivindicación 5, en el que al menos algunos de los símbolos redundantes se generan

60 usando operaciones de GF [2] y se generan otros símbolos redundantes usando operaciones de GF [256].

7. El procedimiento de la reivindicación 1, en el que los símbolos intermedios se generan, durante la codificación, a partir de los símbolos de origen utilizando un proceso de decodificación, en donde el proceso de decodificación se basa en un conjunto lineal de relaciones entre los símbolos intermedios y los símbolos

65 de origen.

5

10

15

20

25

30

35

40

45

50

55

60

65

8. El procedimiento de la reivindicación 7, en el que al menos algunas de las relaciones lineales son relaciones sobre GF [2] y otras relaciones lineales son relaciones sobre GF [256].

9. El procedimiento de la reivindicación 1, en el que el número de símbolos codificados distintos que se pueden generar a partir de un conjunto ordenado de símbolos de origen dado es independiente del número de símbolos de origen en ese conjunto ordenado.

10. El procedimiento de la reivindicación 1, en el que un número promedio de operaciones de símbolos realizadas para generar un símbolo codificado está acotado por una constante independiente del número de símbolos de origen en ese conjunto ordenado.

11. Un procedimiento para recibir datos desde un origen, en el que los datos se reciben en un destino por un canal de comunicación por paquetes, y en el que los datos pueden ser representados por un conjunto de símbolos codificados obtenidos de un conjunto ordenado de símbolos de origen que representan los datos enviados desde el origen al destino, comprendiendo el procedimiento:

obtener el conjunto de símbolos codificados recibidos;

decodificar un conjunto de símbolos intermedios a partir del conjunto de símbolos codificados recibidos;

asociar cada uno de los símbolos intermedios a un conjunto de símbolos intermedios, en donde los símbolos intermedios están asociados en al menos dos conjuntos, y en donde un primer conjunto comprende símbolos que el origen designó como símbolos no permanentemente inactivados, LT, para la decodificación de propagación de creencias, y un segundo conjunto comprende símbolos que el origen designó como símbolos inactivados permanentemente, PI, para ser despejados por separado de la decodificación de propagación de creencias, con el fin de planificar un proceso de decodificación para recuperar los símbolos intermedios a partir de los símbolos codificados recibidos; y

recuperar al menos algunos de los símbolos de origen del conjunto ordenado de símbolos de origen a partir del conjunto de símbolos intermedios según el proceso de decodificación.

12. El procedimiento de la reivindicación 11, en el que el proceso de decodificación comprende al menos una primera fase de decodificación, en donde se genera un conjunto de símbolos codificados reducidos que dependen del segundo conjunto que comprende símbolos inactivados permanentemente, y un tercer conjunto de símbolos que comprende símbolos inactivados dinámicamente, siendo el tercer conjunto de símbolos un subconjunto del primer conjunto de símbolos, y una segunda fase de decodificación, en donde el conjunto de símbolos codificados reducidos se utiliza para decodificar el segundo conjunto de símbolos y el tercer conjunto de símbolos, y una tercera fase de decodificación, en la que el segundo conjunto decodificado de símbolos y el tercer conjunto de símbolos y el conjunto de símbolos codificados recibidos se usan para decodificar al menos algunos de los símbolos intermedios restantes que están en el primer conjunto de símbolos.

13. El procedimiento de la reivindicación 12, en el que la primera fase de decodificación usa decodificación de propagación de creencias combinada con decodificación de inactivación, y / o la segunda fase de decodificación usa eliminación Gaussiana.

14. El procedimiento de la reivindicación 12, en el que la tercera fase de decodificación utiliza la retro-sustitución o un retro-barrido seguido de un barrido de avance.

15. El procedimiento de la reivindicación 12, en el que el proceso de decodificación opera sobre el tercer conjunto de símbolos, considerando que el número de símbolos en el tercer conjunto de símbolos es menor que el 10% del número de símbolos de origen y / o menos del 10% del número de símbolos en el segundo conjunto de símbolos.

16. El procedimiento de la reivindicación 11, en el que se opera sobre los símbolos codificados recibidos como símbolos generados por el código de LDPC o símbolos generados por el código de Reed-Solomon.

17. El procedimiento de la reivindicación 11, en el que se opera sobre cada símbolo codificado recibido del conjunto de símbolos codificados recibidos como si fuera una combinación de un primer símbolo generado a partir de uno o más símbolos del primer conjunto de símbolos y un segundo símbolo generado a partir de uno o más símbolos del segundo conjunto de símbolos, en donde se opera sobre cada símbolo codificado recibido como si la combinación fuera un XOR del primer símbolo y un XOR de un número fijo de símbolos que se eligió al azar entre el segundo conjunto de símbolos, y en donde se opera sobre cada símbolo codificado recibido como si el segundo símbolo fuera un XOR de un primer número de símbolos que se eligió aleatoriamente entre el segundo conjunto de símbolos, y en donde el primer número de símbolos depende del segundo número de símbolos que se eligió entre el primer conjunto de símbolos para generar el primer

5

10

15

20

25

30

35

40

símbolo.

18. El procedimiento de la reivindicación 17, en el que el proceso de decodificación opera como si el primer símbolo se eligiera basándose en un código de reacción en cadena del primer conjunto de símbolos.

19. El procedimiento de la reivindicación 11, en el que el proceso de decodificación opera como si el tamaño del segundo conjunto de símbolos fuera proporcional a la raíz cuadrada del número de símbolos de origen.

20. El procedimiento de la reivindicación 11, en el que el proceso de decodificación opera como si los símbolos intermedios comprendieran el conjunto ordenado de símbolos de origen y un conjunto de símbolos redundantes generados a partir del conjunto ordenado de símbolos de origen, en donde el proceso de decodificación opera como si al menos algunos de los símbolos redundantes fueran generados utilizando operaciones de Gf [2] y otros símbolos redundantes fueran generados utilizando operaciones de GF [256].

21. El procedimiento de la reivindicación 11, en el que el proceso de decodificación opera como si los símbolos intermedios comprendieran el conjunto ordenado de símbolos de origen.

22. El procedimiento de la reivindicación 11, en el que el proceso de decodificación opera como si los símbolos intermedios fueran símbolos que fueran generados a partir de los símbolos de origen utilizando un proceso de decodificación basado en un conjunto lineal de relaciones entre los símbolos intermedios y los símbolos de origen, en donde el proceso de decodificación opera como si al menos algunas de las relaciones lineales son relaciones sobre GF [2] y otras relaciones lineales son relaciones sobre GF [256].

23. El procedimiento de la reivindicación 11, en el que el proceso de decodificación opera como si el número de diferentes símbolos codificados posibles que se pueden recibir fuera independiente del número de símbolos de origen en el conjunto ordenado.

24. El procedimiento de la reivindicación 11, en el que un número promedio de operaciones de símbolos realizadas para decodificar el conjunto de símbolos de origen a partir del conjunto de símbolos codificados recibidos está acotado por una constante multiplicada por el número de símbolos de origen, en donde la constante es independiente del número de símbolos de origen.

25. El procedimiento de la reivindicación 11, en el que el proceso de decodificación opera como si el número de símbolos en el primer conjunto de símbolos fuera más que un orden de magnitud mayor que el número de símbolos en el segundo conjunto de símbolos.

26. El procedimiento de la reivindicación 11, en el que el proceso de decodificación opera de tal manera que la recuperación de todo el conjunto de K símbolos de origen a partir de un conjunto de N = K + A símbolos codificados, para algunos K, N y A, tiene una probabilidad de éxito de al menos una cota inferior de 1 - (0,01) a (A + 1) para A = 0, 1 o 2, siendo la cota inferior independiente del número de símbolos de origen.

imagen1

135

GENERADOR

DE NUMEROS

ALEATOR OS

GENERADOR DINÁMICO DE CLAVES

GENERADOR ESTÁTICO DE CLAVES

So, S-i,

Símbolos de origen:

COD F CADOR

C 0........ CfK-1))

B lo , B I, , B(l2),

Otros parámetros K

de codificación

(Lista Pl, p R, A,

□ ESIGNADOR DE

140

NACT VAC ON

R lista

MODULO DE TRANSM S ON

de Pl

145

CANAL

150

MODULO DE RECEPC ON

Parametros de decodificacion

D(0),.... P, DN-1 ,..

(Lista Pl, P, R,A, etc.) —

155

Símbolos de origen:

jECODIFICÁDOR

C0........CK-1

160

GENERADOR

REGENERADOR

ESTATICO DE

DINAMICO DE CLAVES

CLAVES

GENERADOR

DE NUMEROS

ALEATOROS

VALORES DE DATOS UTILIZADOS

K Número de símbolos de origen

R Número de símbolos redundantes

L Número de símbolos intermedios (L = K + R)

S Número de símbolos de LDPC H Número de símbolos de HDPC P Número de símbolos permanentemente inactivos (Pl)

N Número de símbolos codificados recibidos A Número de símbolos de sobrecarga (A = N-K)

FORMACIONES DE SÍMBOLOS

(C(0),..: -,C(K-1))

(C(K), ..: ■> C(L-1))

(0(0),..: ■> C(L-1))

(C(0)......C(L-P-1))

(C(L-P)......C(L-1))

(□(0)......D(N-1))

Símbolos de origen

Símbolos redundantes

Símbolos intermedios

LT Símbolos Intermedios

Símbolos permanentemente inactivos (Pl)

(es decir, “Lista Pl”)

Símbolos codificados recibidos por el decodificador 155

Fig.2

imagen2

imagen3

imagen4

imagen5

d m[d]

30: 1043576

29: 1017662

28: 1016370

27: 1014983

26: 1013490

25: 1011876

24: 1010129

23: 1008229

22: 1006157

21: 1003887

20: 1001391

19: 998631

18: 995565

17: 992138

16: 988283

15: 983914

14: 978921

13: 973160

12: 966438

11: 958494

10: 948962

9: 937311

8: 922747

7: 904023

6: 879057

5: 844104

4: 791675

3: 704294

2: 529531

1: 5243

0
0

imagen6

imagen7

imagen8

imagen9

imagen10

imagen11

imagen12

imagen13

imagen14

imagen15

imagen16

C DI O

D tau O

C(pi 1)

Dítauíi))

N+R

C pi L-1

D tau N+R-1 )

Fig. 22

imagen17

0.0: T-

o..*-.: cp>

Q. O.: ■ _J

6 6: CL

: O

106

(-----------------------------------------1------------------------------------------>

í-------------------------w-------------------------»|i---------g---------)

820 830

imagen18

Fig.24

imagen19

imagen20

imagen21

imagen22

Fig. 26

109

imagen23

imagen24

imagen25

Fig. 27

imagen26

1410

1415

1420

1430

1440

1445

imagen27

CpiO

D(tau(ü))

Cpi1

Dtau 1))

C(pi(L-1))

D(tau(w-1))

Fig. 28

1310

Dítau(O)

Cfpi(1»

C(pl W

Dtau 1

C(pi(L-1))

Dítau(w-1))

C pl w-1

Fig. 29

112

Símbolos de origen:

(C(0), C(K-1)

Parámetros de entrada

Interfaz de entrada

Memoria intermedia de símbolos de origen

1008

Símbolos de origen

1010

1012

Generador de símbolos de origen a entrada

Símbolos de entrada

Generador de símbolos redundantes

Fig. 30

imagen28

113

Señal de entrada

imagen29

Fig. 31