Member of The Internet Defense League Últimos cambios
Últimos Cambios
Blog personal: El hilo del laberinto Geocaching

Linear Feedback Shift Registers

Ú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         |   1
Dado 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?.

Polinomios primitivos

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.

Propiedades

Algunas de las propiedades de los LFSR:

  • El periodo de la secuencia es 2m-1.

  • El número de unos generados es 2m-1.

  • El número de ceros generados es 2m-1-1.

Aplicaciones

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.


Generación de secuencias LFSR por software

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


Secuencias PRN y LFSR

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".


Historia

  • 23/Ene/03: Secuencias PRN y LFSR.

  • 23/Ene/03: Generación de secuencias LFSR por software.

  • 04/Sep/02: Primera versión de este documento.



Python Zope ©2002-2003 jcea@jcea.es

Más información sobre los OpenBadges

Donación BitCoin: 19niBN42ac2pqDQFx6GJZxry2JQSFvwAfS