Dados electronicos
Páginas: 18 (4254 palabras)
Publicado: 26 de marzo de 2011
Dados electrónicos más justos
Una buena forma de diseñar un dado electrónico es por medio de secuencias pseudoaleatorias binarias. Una secuencia pseudoaleatoria binaria se puede implementar a través de un LFSR (Linear Feedback Shift Register) de longitud máxima1. Un problema de estas secuencias es que al ser binarias generan todas las combinaciones para el tamaño de la misma. Por ejemplo: sila secuencia es de 3 bits se generarán los códigos binarios del 0 hasta el 7 y los dados solo tienen números del 1 al 6. La solución obvia a este problema es ignorar las salidas 0 y 7 del LFSR. Sin embargo, esto puede incrementar el número de apariciones de los demás códigos en la secuencia, afectando de esta forma la probabilidad de aparición de los códigos, la cual debe ser igual para asegurarla aleatoriedad de la secuencia.
El proyecto consiste en diseñar e implementar cuatro dados independientes usando LFSRs de longitud máxima y con aparición equi-probable de los números de cada dado. Cada estudiante en el grupo estará encargado de un generador pseudoaleatorio. El resultado de los dados debe ser observado por los Display 7-segmentos de la tarjeta. Un pulsador o un interruptorcontrolará cada dado y cada uno de estos deberá funcionar independientemente de los otros. En la Figura 1 se muestra un diagrama de bloques simplificado de este proyecto. Cada bloque Control de Dado deberá tener habilitador, longitud de LFSR y valor inicial de LFSR diferentes. La longitud mínima de los LFSR será de 8 bits.
Figura 1:
1. Ver Wakerly p. 730
LFSRsignifica linear feedback shift register, que se traduce como: registro de desplazamiento con retroalimentación lineal. Es un registro de desplazamiento en el cual la entrada es un bit proveniente de aplicar una función de transformación lineal a un estado anterior.
El valor inicial se denomina semilla y, como la forma de operar el registro es determinística, la secuencia de valores producidos estácompletamente determinada por el estado actual o el estado anterior. La secuencia tiene un periodo de repetición, es decir que la secuencia vuelve a generarse y se repite indefinidamente. Cuando el periodo de repetición es máximo, ese LFSR tiene interés criptográfico.
Contenido[ocultar] * 1 Cómo trabaja LFSR * 2 Propiedades del flujo de salida * 3 LFSR de Galois * 4 Usos criptográficos * 5Aplicaciones en comunicaciones * 6 Enlaces externos |
[editar] Cómo trabaja LFSR
Veamos un ejemplo, tenemos la secuencia [16,14,13,11].
La secuencia tap de un LFSR se puede representar como un polinomio mod 2. Esto significa que los coeficientes del polinomio deben ser 1's o 0's. Esto se llama polinomio de realimentación o característica polinomial.
Por ejemplo, si los taps están en lasposiciones de los bits: 16, 14, 13 y 11 ,el polinomio LFSR resultante es:
x11 + x13 + x14 + x16 + 1
Las salidas que influyen en la entrada, se denominan taps. Son las que aparecen en el polinomio. Y se indican en azul en el esquema inferior.
* Si el polinomio es primitivo, sí y solo sí, el LFSR es máximo, o lo que es lo mismo, tiene periodo máximo.
* El LFSR sólo será máximo si el número detaps es par.
* Los valores de tap en un LFSR máximo son coprimos.
* Puede haber más de una secuencia tap que haga máximo al LFSR para esa longitud determinada.
* Una vez encontrada una secuencia tap máxima, automáticamente sigue otra. Si la secuencia tap, en un LFSR n-bit, es [n,A,B,C], entonces la secuencia mirror correspondiente es [n,n-A,n-B,n-C]. Por ejemplo, la secuencia tap[32,3,2,1], tiene su homólogo [32,29,30,31]. Ambos dan como resultado periodo máximo.
[editar] Propiedades del flujo de salida
Un LFSR se puede caracterizar de forma polinómica según sean sus conexiones y los valores de los registros.
Se define el polinomio de Estado como:
El polinomio de estado muestra el valor de los registros.
De la misma forma se define el polinomio de Conexiones como:...
Una buena forma de diseñar un dado electrónico es por medio de secuencias pseudoaleatorias binarias. Una secuencia pseudoaleatoria binaria se puede implementar a través de un LFSR (Linear Feedback Shift Register) de longitud máxima1. Un problema de estas secuencias es que al ser binarias generan todas las combinaciones para el tamaño de la misma. Por ejemplo: sila secuencia es de 3 bits se generarán los códigos binarios del 0 hasta el 7 y los dados solo tienen números del 1 al 6. La solución obvia a este problema es ignorar las salidas 0 y 7 del LFSR. Sin embargo, esto puede incrementar el número de apariciones de los demás códigos en la secuencia, afectando de esta forma la probabilidad de aparición de los códigos, la cual debe ser igual para asegurarla aleatoriedad de la secuencia.
El proyecto consiste en diseñar e implementar cuatro dados independientes usando LFSRs de longitud máxima y con aparición equi-probable de los números de cada dado. Cada estudiante en el grupo estará encargado de un generador pseudoaleatorio. El resultado de los dados debe ser observado por los Display 7-segmentos de la tarjeta. Un pulsador o un interruptorcontrolará cada dado y cada uno de estos deberá funcionar independientemente de los otros. En la Figura 1 se muestra un diagrama de bloques simplificado de este proyecto. Cada bloque Control de Dado deberá tener habilitador, longitud de LFSR y valor inicial de LFSR diferentes. La longitud mínima de los LFSR será de 8 bits.
Figura 1:
1. Ver Wakerly p. 730
LFSRsignifica linear feedback shift register, que se traduce como: registro de desplazamiento con retroalimentación lineal. Es un registro de desplazamiento en el cual la entrada es un bit proveniente de aplicar una función de transformación lineal a un estado anterior.
El valor inicial se denomina semilla y, como la forma de operar el registro es determinística, la secuencia de valores producidos estácompletamente determinada por el estado actual o el estado anterior. La secuencia tiene un periodo de repetición, es decir que la secuencia vuelve a generarse y se repite indefinidamente. Cuando el periodo de repetición es máximo, ese LFSR tiene interés criptográfico.
Contenido[ocultar] * 1 Cómo trabaja LFSR * 2 Propiedades del flujo de salida * 3 LFSR de Galois * 4 Usos criptográficos * 5Aplicaciones en comunicaciones * 6 Enlaces externos |
[editar] Cómo trabaja LFSR
Veamos un ejemplo, tenemos la secuencia [16,14,13,11].
La secuencia tap de un LFSR se puede representar como un polinomio mod 2. Esto significa que los coeficientes del polinomio deben ser 1's o 0's. Esto se llama polinomio de realimentación o característica polinomial.
Por ejemplo, si los taps están en lasposiciones de los bits: 16, 14, 13 y 11 ,el polinomio LFSR resultante es:
x11 + x13 + x14 + x16 + 1
Las salidas que influyen en la entrada, se denominan taps. Son las que aparecen en el polinomio. Y se indican en azul en el esquema inferior.
* Si el polinomio es primitivo, sí y solo sí, el LFSR es máximo, o lo que es lo mismo, tiene periodo máximo.
* El LFSR sólo será máximo si el número detaps es par.
* Los valores de tap en un LFSR máximo son coprimos.
* Puede haber más de una secuencia tap que haga máximo al LFSR para esa longitud determinada.
* Una vez encontrada una secuencia tap máxima, automáticamente sigue otra. Si la secuencia tap, en un LFSR n-bit, es [n,A,B,C], entonces la secuencia mirror correspondiente es [n,n-A,n-B,n-C]. Por ejemplo, la secuencia tap[32,3,2,1], tiene su homólogo [32,29,30,31]. Ambos dan como resultado periodo máximo.
[editar] Propiedades del flujo de salida
Un LFSR se puede caracterizar de forma polinómica según sean sus conexiones y los valores de los registros.
Se define el polinomio de Estado como:
El polinomio de estado muestra el valor de los registros.
De la misma forma se define el polinomio de Conexiones como:...
Leer documento completo
Regístrate para leer el documento completo.