complejidad lineal

Universidad Central Marta Abreu de Las Villas
Facultad Matemática- Física- Computación
Carrera de Licenciatura en Matemática








TRABAJO DE INVESTIGACIÓN

‘‘Complejidad lineal de sucesiones binarias aleatorias”

Autor: Frank E. Alvarez
Tutor: Evaristo José Madarro Capó

faclavijo@uclv.edu.cu


SANTA CLARA 2013
Introducción

Objetivo general
Analizar el método degeneración de sucesiones binarias aleatorias utilizado por los registros de desplazamientos con retroalimentación lineal y comprender el cálculo de la complejidad lineal de dichas sucesiones.
Objetivos de investigación
Analizar el método de generación de sucesiones binarias de los registros de desplazamiento con retroalimentación lineal.
Definir a que se llama complejidad lineal de unasucesión y analizar sus propiedades.
Calcular el grado de complejidad lineal de las sucesiones generadas por los registros de desplazamiento con retroalimentación lineal a partir de un algoritmo.
Comprender en que consiste el test estadístico que mide el grado de complejidad lineal de una sucesión.

Preguntas de investigación
¿Qué son los registros de desplazamiento con retroalimentaciónlineal?
¿A qué se le llama complejidad lineal de una sucesión binaria?
¿Qué propiedades tiene la complejidad lineal?
¿Cómo se calcula la complejidad lineal de una sucesión binaria?
¿Qué es y cómo trabaja el algoritmo de Berlekamp-Massey?
¿Qué es el test de aleatoriedad de Complejidad Lineal?

Palabras claves
Registros de desplazamiento con retroalimentación lineal
Sucesiones binariasComplejidad lineal
Algoritmo de Berlekamp-Massey
Test de aleatoriedad de Complejidad lineal


Desarrollo

Registros de desplazamiento con realimentación lineal

Los Registros de desplazamiento con realimentación lineal (LFSRs) por sus siglas en inglés, se utilizan en muchos de los generadores de corriente de clave que se han propuesto en la literatura. Hay varias razones para esto:
1. LosLFSRs son muy adecuados para la aplicación en hardware.
2. Pueden producir secuencias de un largo periodo.
3. Pueden producir secuencias con buenas propiedades estadísticas.
4. Debido a su estructura, pueden ser analizados fácilmente usando técnicas algebraicas.
1.1 Definición: Un registro de desplazamiento con realimentación lineal (LFSR) de longitud consiste en etapas (o elementos deretardo) numerados cada una capaz de almacenar un bit y tener una entrada y una salida; y un reloj que controla el movimiento de los datos. Durante cada unidad de tiempo se realizan las siguientes operaciones:
I. El contenido de la etapa es la salida y forma parte de la secuencia de salida.
II. El contenido de la etapa se pasa a la etapa para cada ,
III. Los nuevos contenidos de la etapa sonel bit el cual se calcula sumando juntos módulo 2, el contenido previo de un subconjunto determinado de etapas .

La Figura 1 representa un LFSR. Haciendo referencia a la figura, cada es o bien ó; los semicírculos cerrados son compuertas AND; y la retroalimentación bit es el módulo 2 suma de los contenidos de los estadios ,, de cada











Figura 1: Registro dedesplazamiento con realimentación lineal (LFSR) de longitud .

1.2 Definición: El LFSR de la figura 1 se denota , donde que es el polinomio de conexión. El LFSR se dice que es no singular si el grado de si (esto es, ). Si el contenido inicial de la etapa es para cada esto , se llama el estado inicial del LFSR.
Si el estado inicial del LFSR en la Figura 1 es , entonces la salida es lasecuencia se determina únicamente por la siguiente recursión:

Ejemplo 1(secuencia de salida de un LFSR)
Considere el LFSR representado en la Figura 1. Si el estado inicial del LFSR es , la secuencia de salida es la secuencia cero. Las siguientes tablas muestran el contenido de las etapas al final de cada unidad de tiempo cuando el estado inicial es .










0
0
1
1
0
8...