Últimos Cambios |
||
Blog personal: El hilo del laberinto |
Última Actualización: 23 de Enero de 2003 - Jueves
Los circuitos LFSR se utilizan en infinidad de sistemas electrónicos para generar secuencias pseudoaleatorias con un período garantizado arbitrariamente largo, de forma simple y eficiente.
El esquema más habitual de un circuito LFSR es el siguiente:
+---+ +---+ +---+ +---+ +->| R +---+--->| R |---+--->| R +---+--->| R +---+---> Salida | +---+ | +---+ | +---+ | +---+ | | | | | | | v v v | | +---+ +---+ +---+ | +--------| X |<-------| X |<-------| X |<---------+ +---+ +---+ +---+
Las cajas R son biestables, y las cajas X son funciones XOR. Como se puede ver, un registro de desplazamiento con realimentación lineal consta de un sencillo registro de desplazamiento cuyos bits se van desplazando hacia la derecha, en el dibujo, y el último de los cuales proporciona la salida binaria del registro. Al mismo tiempo, por la izquierda en el dibujo, se van inyectando bits cuyo valor es una combinación lineal (módulo 2) de los bits que forman el estado interno del registro.
Aunque en el dibujo se ha dibujado un XOR para cada bit de estado, en la práctica sólo se emplean algunos de ellos. La forma de elegir cuáles se usan no es arbitraria, sino que se basa en principios matemáticos bien definidos. Se verá con detalle más adelante.
Veamos un ejemplo de un circuito concreto:
+---+ +---+ +---+ +->| R +------->| R +---+--->| R +---+---> Salida | +---+ +---+ | +---+ | | | | | v | | +---+ +---+ | +--------| X |<-------| X |<---------+ +---+ +---+
Supongamos que, de izquierda a derecha, los biestables contienen el valor 001. La tabla con la evolución de estados a partir de ese punto sería:
Estado Interno | Salida ----------------+------- 001 | 1 100 | 0 010 | 0 101 | 1 110 | 0 111 | 1 011 | 1Dado que el estado interno de un registro de desplazamiento tiene m bits, la longitud máxima de la salida de un LFSR es de 2m-1 bits, ya que el estado "todo ceros" no es válido (genera una salida continua a cero). ¿Cómo debemos elegir las posiciones de los XOR para asegurarnos alcanzar la lóngitud máxima 2m-1 bits?.
Un LFSR tendrá longitud máxima si su polinomio característico (polinomio de realimentación) es primitivo en GF(2n).
Un polinomio de grado m es primitivo en GF(2n) si y solo si a) es irreducible (no es factorizable en polinomios menores) y b) su orden es 2m-1 (divide exactamente a x2m-1+1 en GF(2n)). Por definición, todos los polinomios primitivos de grado m tienen la forma xm+...+1.
Algunos polinomios primitivos en GF(2n):
Grado 1 x 2 x2+x+1 3 x3+x2+1, x3+x+1 4 x4+x3+1, x4+x+1
El número de polinomios primitivos de grado m en GF(bn) está definido por la fórmula Q(bm-1)/m, donde Q es la función COCIENTE de Euler (número de enteros menores que su argumento que son coprimos con su argumento).
No existe una fórmula sencilla para obtener polinomios primitivos de grado arbitrario, recurriéndose típicamente a manuales de referencia con tablas o a búsqueda exhaustiva mediante programas informáticos.
Por ejemplo, el siguiente código en Python nos proporciona un listado de todos los polinomios primitivos en GF(2n) para un grado determinado:
def polinomios_primitivos(m) : rango=pow(2,m)-1 pol2=pow(2,rango)+1 p=pow(2,m+1) for i in xrange(pow(2,m)+1,pow(2,m+1),2) : v=2 # generador for j in xrange(rango-1) : v*=2 if v>=p : v^=2*i if v==2 : break if v!=2 : print i
La salida de este programa, convertida a código binario, nos indica la presencia o ausencia de cada potencia de x. Por ejemplo, según este programa, un polinomio primitivo de grado 8 sería el 285 que, pasado a binario, es 100011101. Dicho valor representa el polinomo x8+ x4+ x3+ x2+1.
Una propiedad interesante de los polinomios primitivos GF(2n) es que el escribirlos al revés también genera un polinomio primitivo. Es decir, si tomamos el polinomio primitivo 100011101 y lo escribimos al revés, 101110001, el polinomio resultante, x8+x6+x5+x4+1, también es primitivo.
Algunas de las propiedades de los LFSR:
La principal aplicación de los circuitos LFSR es la generación de una secuencia de bits pseudoaleatoria, con buenas propiedades matemáticas. La correlación cruzada, por ejemplo, es óptima a medida que el período de la secuencia crece.
Los LFSR NO deben ser utilizados en criptografía como fuentes de cifrado stream, ya que es posible deducir el estado interno y el polinomio característico del LFSR resolviendo una ecuación obtenida a partir de observar 2m bits de salida. Esta técnica ha sido utilizada, por ejemplo, para atacar numerosos sistemas de cifrado analógico de video.
El esquema hardware mostrado al principio de este documento es muy eficiente... en hardware. Pero a menos que seamos ingenieros electrónicos, normalmente las secuencias LFSR se generan mediante software, y una traducción directa del esquema es muy ineficiente.
La siguiente rutina, en Python 2.2.*, nos proporciona un "generador" LFSR, dado un número que, en binario, nos indica la presencia o ausencia de un coeficiente:
from __future__ import generators def LFSR(polinomio) : p,p2=1,polinomio while p2 : p2>>=1 p<<=1 semilla=2 polinomio*=2 while True : semilla*=2 if semilla>=p : semilla^=polinomio yield 1 else : yield 0
Aunque típicamente se asocia PRN con LFSR, no son lo mismo. Un código LFSR es un código PRN, pero la vía inversa no se cumple necesariamente. No obstante, es muy habitual encontrar códigos LFSR cuando se busca PRN en Google, por ejemplo. PRN significa "Pseudo Random Noise".
Más información sobre los OpenBadges
Donación BitCoin: 19niBN42ac2pqDQFx6GJZxry2JQSFvwAfS