Generador de secuencias pseudo-aleatorias y método asociado.

Un metodo para la generación de una secuencia de ruido pseudo-aleatoria de los valores generados por un polinomio de rotación,

dicho metodo que comprende los pasos de:

- formar un conjunto de elementos de memoria (102), cada elemento de memoria (104) del conjunto (102) para el almacenamiento de una palabra de una longitud de palabra seleccionada alli dentro;

- iniciar (108) cada uno de los elementos de memoria (104) formados durante dicho paso de formación con los valores de estado iniciales, los valores de estado iniciales con los que cada uno de los elementos de memoria (104) se inicia formando la palabra almacenada alli dentro; y

- seleccionar (112) al menos una de las palabras almacenadas en al menos uno de los elementos de memoria (104) para formar una secuencia de salida (Palabra de Salida), la secuencia de salida que forma una parte de la secuencia de ruido pseudo-aleatoria;

caracterizado porque el metodo ademas comprende el paso de:

- formar al menos una nueva palabra a ser almacenada en al menos uno de los elementos de memoria (104) del conjunto de elementos de memoria (102), la nueva palabra formada de una combinación seleccionada de palabras almacenadas en los elementos de memoria del conjunto de elementos de memoria, la al menos una nueva palabra que corresponde en longitud con la longitud de las palabras de memoria seleccionadas para formar la secuencia de salida.

Generador de secuencias pseudo-aleatorias y metodo asociado La presente invención se refiere en general a la generación de secuencias de numeros pseudo-aleatorios usados, por ejemplo, en los procedimientos de cifrado. Mas concretamente, la presente invención se refiere a un generador 5 de secuencias de numeros pseudo-aleatorios, y a un metodo asociado, por el cual generar una secuencia de numeros pseudo-aleatorios que corresponde a una secuencia generada por un polinomio de rotación seleccionado.

Los elementos de memoria orientados a palabras se usan para almacenar palabras que forman la secuencia de numeros pseudo-aleatorios. Los tamanos de las palabras de memoria se seleccionan de manera que los tamanos de las partes de la secuencia generados por el generador de rotación durante iteraciones sucesivas de operaciones se pueden aumentar rapidamente, segun se desea, para facilitar por ello la generación de la misma secuencia de numeros pseudo-aleatorios en tasas aumentadas, correspondiente a construcciones de generadores de rotación compatibles, alternativos.

La secuencia de numeros pseudo-aleatorios generada a traves del funcionamiento de una realización de la presente invención se utiliza ventajosamente como parte de un sistema para cifrar datos a ser comunicados sobre un enlace de radio, tal como un enlace de radio formado entre un terminal m6vil y una estación base de un sistema de comunicación celular. La secuencia de numeros pseudo-aleatorios generada a traves del funcionamiento de una realización de la presente invención se utiliza tambien ventajosamente en comunicaciones de espectro expandido (por ejemplo, Acceso Multiple por División de C6digo) , en sistemas fluctuantes automatizados, en metodos de comprensión de senal de voz, y en sistemas de radar.

Antecedentes de la invención Un sistema de comunicación es operable para comunicar información entre una estación de envio y una estación de recepción por medio de un canal de comunicación. En un sistema de comunicación cableado, el canal de comunicación esta formado de una conexión fija entre las estaciones de envio y de recepción. Y, en un sistema de radiocomunicación, el canal de comunicación forma una parte del espectro de frecuencia electromagnetico. Debido a que no se requiere una conexión fisica para formar el canal de comunicación entre las estaciones de envio y de recepción de un sistema de radiocomunicación, las comunicaciones son posibles cuando una conexión fija entre las estaciones de envio y de recepción seria poco practica.

Un sistema de comunicación digital es un sistema de comunicación en el que la información a ser comunicada por una estación de envio a una estación de recepción esta digitalizada. Un sistema de comunicación digital se puede implementar tanto en un sistema de comunicación cableado como en un sistema de comunicación radio. Un sistema de comunicación digital permite la utilización mas eficiente del canal de comunicación que se extiende entre las estaciones de envio y de recepción, permitiendo por ello que la capacidad de comunicación del sistema de comunicación sea aumentada sobre aquella de un sistema de comunicación analógico, convencional.

Las comunicaciones entre las estaciones de envio y de recepción algunas veces se desea que sean privadas en naturaleza. Es decir, las partes que envian y que reciben las senales de comunicación pretenden solamente que las partes de envio y de recepción sean capaces de acceder al contenido de la información de las senales de comunicación. Particularmente cuando el canal de comunicación es un canal de comunicación radio de un sistema de comunicación radio, la privacidad de las comunicaciones entre las estaciones de envio y de recepción llega a ser problematica. Como un canal de radio es inherentemente publico en naturaleza, se puede detectar una senal de comunicación transmitida en el canal de comunicación de radio por cualquier estación de recepción, dentro del alcance de la senal de comunicación, y sintonizar al canal de radio. Una parte no autorizada, por ejemplo, es capaz de sintonizar un receptor de radio a la frecuencia del canal de radio en la que se transmite la senal de comunicación, para recibir por ello la senal de comunicación. Analogos problemas de seguridad tambien son motivo de preocupación en los sistemas de comunicación cableados en el caso de que una parte no autorizada consiga 45 acceso al canal de comunicación cableado.

Una manera mediante la cual mejorar la seguridad de las comunicaciones en un sistema de comunicación es cifrar la información que forma una senal de comunicación en forma cifrada. Si solamente las partes autorizadas son capaces de descifrar la senal de comunicación cifrada, una parte no autorizada es incapaz de discernir el contenido de información de la senal de comunicación transmitida en el canal de comunicación. Por ello, la privacidad de las 50 comunicaciones se asegura mejor.

Una senal de información digital es particularmente susceptible de un proceso de cifrado. Una senal de información digital esta formada de secuencias de bits, y cada bit, si se desea, de la senal de información se puede codificar en forma cifrada en la estación de envio antes de su transmisión en el canal de comunicación. Una parte no autorizada, sin conocimiento de la manera por la que la senal de información se cifra es incapaz de descifrar una senal de 55 recepción para recuperar el contenido de información de la senal transmitida. Solamente una estación de recepción capaz de descifrar la senal cifrada es capaz de recuperar el contenido de información de la senal de recepción.

Se usan varias maneras mediante las cuales cifrar la senal de información digital. Un esquema de cifrado tipico, tal

como aquel usado en comunicaciones celulares, utiliza un proceso de cifrado por el cual los bit digitalizados de una senal de información se combinan con los bit de una secuencia pseudo-aleatoria generada por un generador de secuencias pseudo-aleatorias. El generador de las secuencias pseudo-aleatorias es operable en conjunto con una clave secreta que, en una tecnica de cifrado simetrico, se conoce en la estación de envio y en una estación de recepción autorizada. La clave secreta se usa en la estación de recepción autorizada para descifrar la senal cifrada recibida en ese lugar, para recuperar por ello el contenido de información de la senal transmitida.

Las secuencias de numeros pseudo-aleatorios se derivan algunas veces mediante el calculo de un polinomio de rotación. Las construcciones, si estan implementadas en componentes fisicos y componentes lógicos, que forman las secuencias de numeros pseudo-aleatorios de esta manera se conocen algunas veces como generadores de rotación. Los bit de salida generados por un generador de rotación forman las secuencias de numeros pseudoaleatorios que se usan, entre atras casas, para cifrar una senal de información. Un generador de rotación se refiere directamente a un polinomio primario, seleccionado sobre algun campo finito GF (q) . Cuando q=2, el campo finito GF (2) se conoce como el caso binario y es de importancia particularmente en comunicaciones digitales. El numero de polinomios primarios desde el cual un generador de rotación se puede derivar es limitado debido a muchas restricciones situadas en el polinomio. Especialmente en el caso binario cuando se requiere el polinomio para exhibir, para minimizar las operaciones de procesamiento necesarias para generar las salidas de alli, solamente unos pocos coeficientes distintos de cero, el numero de polinomios adecuados que se pueden usar para formar un polinomio de rotación es limitado. El numero de coeficientes distintos de cero de un polinomio se conoce como el peso del polinomio.

Existen tablas que enumeran polinomios primarios, tales como, para el caso binario de GF (2) , los polinomios primarios con treo o cinco coeficientes distintos de cero y con grados de hasta cinco mil.

La aleatoriedad de las salidas, algunas veces conocidas aqui dentro como "n-tuplas", generadas por un polinomio de rotación binario de peso=3 generalmente es pobre, de manera que para aumentar la aleatoriedad de las salidas, se requiere un polinomio de peso elevado. Pero, tal aleatoriedad mejorada sucede a costa del aumento de los requerimientos de procesamiento. Las tablas existentes no siempre se pueden usar para seleccionar un polinomio de rotación adecuado desde el cual derivar una secuencia de numeros pseudo-aleatorios ya que tales tablas existentes no muestran necesariamente todos los polinomios primarios con un numero de coeficientes distintos de cero, por ejemplo, tres o cinco,... [Seguir leyendo]

1. Un metodo para la generación de una secuencia de ruido pseudo-aleatoria de los valores generados por un polinomio de rotación, dicho metodo que comprende los pasos de:

- formar un conjunto de elementos de memoria (102) , cada elemento de memoria (104) del conjunto (102) para el 5 almacenamiento de una palabra de una longitud de palabra seleccionada alli dentro;

- iniciar (108) cada uno de los elementos de memoria (104) formados durante dicho paso de formación con los valores de estado iniciales, los valores de estado iniciales con los que cada uno de los elementos de memoria

(104) se inicia formando la palabra almacenada alli dentro; y

- seleccionar (112) al menos una de las palabras almacenadas en al menos uno de los elementos de memoria

(104) para formar una secuencia de salida (Palabra de Salida) , la secuencia de salida que forma una parte de la secuencia de ruido pseudo-aleatoria;

caracterizado porque el metodo ademas comprende el paso de:

- formar al menos una nueva palabra a ser almacenada en al menos uno de los elementos de memoria (104) del

conjunto de elementos de memoria (102) , la nueva palabra formada de una combinación seleccionada de palabras almacenadas en los elementos de memoria del conjunto de elementos de memoria, la al menos una nueva palabra que corresponde en longitud con la longitud de las palabras de memoria seleccionadas para formar la secuencia de salida.

2. El metodo de la reivindicación 1, en el que el polinomio de rotación es de un grado seleccionado, el grado seleccionado que es, al menos en parte, determinativo del numero de elementos de memoria (104) del conjunto de elementos de memoria (102) formado durante dicho paso de formación.

3. El metodo de la reivindicación 2 en el que el numero de elementos de memoria del conjunto de elementos de memoria (102) ademas es dependiente de la longitud de la palabra seleccionada de la que esta formada cada una de las palabras de memoria.

4. El metodo de la reivindicación 3 en el que el numero de elementos de memoria que forman el conjunto de elementos de memoria (102) es directamente proporcional al grado seleccionado y es inversamente proporcional a la longitud de la palabra seleccionada de la que esta formada cada una de las palabras.

5. El metodo de la reivindicación 2 en el que el conjunto de elementos de memoria (102) formado durante dicho paso de formación comprende un grupo contiguo lógicamente de elementos de memoria (104) , que forman una pila de palabras, al menos uno de los elementos de memoria (104) de la pila de elementos de memoria seleccionados para formar un elemento de memoria de salida, y en el que la al menos una de las palabras seleccionadas durante dicho paso de selección de la al menos una de las palabras comprende la al menos una palabra almacenada en el elemento de memoria de salida.

6. El metodo de la reivindicación 5 en el que los sucesivos del grupo contiguo lógicamente de elementos de memoria definen las columnas y en donde dicho metodo comprende el paso adicional de desplazar, en una forma por columnas, las palabras a traves de la pila de los elementos de memoria.

7. El metodo de la reivindicación 6 en el que la al menos una palabra seleccionada durante dicho paso de selección de la al menos una nueva palabra comprende una palabra de valores correspondientes a los valores de realimentación generados por el polinomio de rotación del grado seleccionado.

8. El metodo de la reivindicación 1 que comprende el paso adicional de asignar en al menos un puntero actualizable ciclicamente (148) a al menso los seleccionados de los elementos de memoria.

9. El metodo de la reivindicación 8 en el que el al menos un puntero actualizable ciclicamente (148) asignado durante dicho paso de asignación identifica el al menos un elemento de memoria en el cual se almacena al menos una de las palabras seleccionadas durante dicho paso de selección.

45 10. El metodo de la reivindicación 9 en el que el al menos un puntero actualizable ciclicamente (148) asignado durante dicho paso de asignación identifica el al menos un elemento de memoria, seleccionado durante dicho paso de selección de la al menos una nueva palabra, en el cual la al menos una nueva palabra va a ser almacenada.

11. El metodo de la reivindicación 2 en el que la longitud de palabra seleccionada de la que cada una de las palabras almacenadas en cada uno de los elementos de memoria formados durante dicho paso de formación se 50 selecciona de manera que al menos un multiplo de la longitud de palabra seleccionada forma una longitud de palabra compatible, y en el que la al menos una de las palabras seleccionadas durante dicho paso de selección comprende al menos un multiplo de una palabra unica.

12. El metodo de la reivindicación 1 en el que dichos pasos de selección de al menos una de las palabras para formar la secuencia de salida y seleccionar la al menos una nueva palabra se realizan iterativamente.

13. Un generador de ruido pseudo-aleatorio (100, 106) para la generación de una secuencia de ruido pseudi aleatoria de los valores generados por un polinomio de rotación, dicho generador de la secuencia de ruido pseudo5 aleatoria que comprende:

- un conjunto de elementos de memoria (102) , cada elemento de memoria (104) de dicho conjunto (102) para el almacenamiento de una palabra seleccionada de una longitud de palabra seleccionada alli dentro;

- un iniciador (108) para iniciar cada uno de los elementos dememoria (104) de dicho conjunto (102) con valores de estado iniciales, los valores de estado iniciales con los que cada uno de los elementos de memoria se inicia

formando la palabra almacenada alli dentro; y

- un selector de la secuencia de salida (112) para la selección de al menos una de las palabras almacenadas en al menos uno de los elementos de memoria de dicho conjunto para formar una secuencia de salida, la secuencia de salida que forma una parte de la secuencia de ruido pseudo-aleatoria;

caracterizado porque el generador de ruido pseudo-aleatorio (100, 106) ademas comprende -un selector de nuevas palabras (114) para formar al menos una nueva palabra a ser almacenada en al menos uno de los elementos de memoria de dicho conjunto, la nueva palabra formada de una combinación seleccionada de palabras almacenadas en los elementos de memoria del conjunto de elementos de memoria, la al menos una nueva palabra que corresponde en longitud con las palabras de longitud seleccionadas para formar la secuencia de salida.