Registros de cambio de retroalimentación generalizada

Question

Me parece confuso algunos ejemplos que he visto. Tal vez usted me puede ayudar a determinar lo que está pasando con ellos.

Un Generalizada Feedback Shift Register (GFSR), la secuencia se define una secuencia $\{W_{i}\}$ que satisface la ecuación

$$W_{k+p}=c_{0}W_{k}\bigoplus c_{1}W_{k+1}\bigoplus...\bigoplus c_{p-1}W_{k+p-1} \qquad \qquad (1)$$

donde $\bigoplus$ es el binario en exclusiva o en operación.

Si el polinomio $f(x)=c_{0}+c_{1}x+c_{2}x^{2}+...+c_{p-1}x^{p-1}+x^{p}$ es un polinomio primitivo $GF(2)$, entonces la secuencia de $\{W_{i}\}$ tendrá la máxima secuencia $2^{p}-1$.

Ejemplo 1: consideremos el trinomio $1+x+x^{4}$ y una secuencia de bits $1, 0, 1, 0$. Para el polinomio tenemos $c_{0}=1$, $c_{1}=1$, $c_{2}=0$, $c_{3}=0$ y $p=4$. Por lo tanto, la ecuación de $(1)$ debe $W_{k+4}=W_{k}\bigoplus W_{k+1}$. De acuerdo a esto, podemos calcular los valores de $W_{5}, W_{6},...$ etc (que ya sabemos que $W_{1}=1, W_{2}=0, W_{3}=1, W_{4}=0$).

Este procedimiento genera la siguiente secuencia

$$1,0,1,0,1,1,1,1,0,0,0,1,0,0,1$$

A continuación, el ejemplo de la toma de 4 bits en trozos (cambiando a la representación decimal):

$1010=10, 1111=15, 0001=1, 0011=3, 1010+1111=0101=5, 0001+0011=0010=2$ y así sucesivamente. Así, un '4-sabio aniquilación' el uso de la recurrencia de los rendimientos de los números

$$10, 15, 1, 3, 5, 2, ...$$

Es esta una forma estándar para generar una mayor secuencia?

Ejemplo 2:

Por el uso de la secuencia de bits de la trinomio $1+x+x^{4}$ y la secuencia de arranque $1,0,1,0$, y... la formación de 4-bits de palabras poniendo los bits en un fijo de posición binaria con un retraso de 3 entre binario de las posiciones, tenemos $$1010=10, 1110=14, 0011=3, 0101=5, 1111=15, 0001 = 1, 0010=2, 0111=7,...$$

Bueno, ambos son ejemplos de tratar con exactamente el mismo problema. Sin embargo, conducen a diferentes secuencias. Yo no sé ni cómo el segundo ejemplo, se genera una secuencia (que parece que es tomar el primer bit de la secuencia de $1, 0, 1, 0$ y la aplicación de los binarios en exclusiva o en funcionamiento de los dos primeros términos de $1 \bigoplus 0 = 1$ cual es el primer término de la siguiente secuencia de bits, a continuación, tomar el segundo y tercer términos $0 \bigoplus 1=1$ que es el segundo término de la nueva secuencia y así sucesivamente). Sin embargo, no sé cómo se pone el último término. Este patrón funciona para todas las secuencias del Ejemplo 2, que me hace lo que yo no estoy viendo el cuadro completo.

Ideas?

Answer 1

Acabo de leer "Generalizado Feedback Shift Register Pseudoaleatoria Número Algoritmo" por T. G. Lewis y W. H. Payne. Creo que el papel se asienta la pregunta que me estaba planteando (ir a la fuente, a la derecha?). En esencia, la pregunta es "¿Cuál es el procedimiento correcto para el uso Generalizado de Feedback Shift Register Algoritmo (GFSR)?".

1.- Empezar con una secuencia y un polinomio primitivo $x^{p}+x^{q}+1$. Por ejemplo, $a_{0}=a_{1}=a_{2}=a_{3}=a_{4}=1$$x^{5}+x^{2}+1$.

2.- Elementos de la secuencia siga $a_{k}=a_{k-p+q}\bigoplus a_{k-p}$$k=p, p+1,...$. En este ejemplo, ya tenemos los 5 primeros elementos de la secuencia y de acuerdo con el polinomio, se nos da ese $p=5, q=2$. Por lo tanto, podemos conocer el próximo elementos de la secuencia

\begin{matrix} a_{6}=a_{3}\bigoplus a_{1}=0 \\ a_{7}=a_{4}\bigoplus a_{2}=0 \\ a_{8}=a_{5}\bigoplus a_{3}=1 \\ a_{9}=a_{6}\bigoplus a_{4}=1 \\ ... \\ \end{de la matriz}

Así, de esta manera se construye el resto de la secuencia:

$\{a_{i}\}_{0}^{30}={1111100011011101010000100101100}$

Con el fin de producir una mejor secuencia aleatoria, se aplica de Kendall algoritmo. Aunque hay varias variaciones de Kendall del algoritmo, el punto es que a cambio de la secuencia original $1111100011011101010000100|101100$ adelante por 6 bits, que es, $1011001111100011011101010|000100$. Y de nuevo tres veces más (hasta que estemos de vuelta con la secuencia original). Este proceso se da de la siguiente secuencia

\begin{matrix} \text{Key} & \text{Sequence} \\ 0 & \|11111\|00011011101010000100|101100\\ 1 & 1011001111100011011101010|000100\\ 2 & 0001001011001111100011011|101010\\ 3 & 101010000100101100111100|011011\\ 4 & 0110111010100001001011001|111100 \end{de la matriz}

Finalmente, tomamos la n-tuplas (en este ejemplo, el 5-tuplas) que se posicionan como las columnas de una matriz nueva:

\begin{matrix} W_{0}: & \|1\|1010 & W_{10}: & 01001& W_{20}: & 00111\\ W_{1}: & \|1\|0001 & W_{11}: & 10000& W_{21}: & 01111\\ W_{2}: & \|1\|1011 & W_{12}:& 10110& W_{22}: & 10010\\ W_{3}: & \|1\|1100 & W_{13}:& 10100& W_{23}: & 01100\\ W_{4}: & \|1\|0011 & W_{14}:& 01110& W_{24}: & 00101\\ W_{5}: & 00001 & W_{15}:& 11111& W_{25}: & 10101\\ W_{6}: & 01101 & W_{16}:& 00100& W_{26}: & 00011\\ W_{7}: & 01000 & W_{17}:& 11000& W_{27}: & 10111\\ W_{8}: & 11101 & W_{18}:& 01011& W_{28}: & 11001\\ W_{9}: & 11110 & W_{19}:& 01010& W_{29}: & 00110 \end{de la matriz}

Cada una de las $W_{i}$ se llama una 'palabra'.

Ya que cada columna obedece a la recurrencia $a_{k}=a_{k-p+q}\bigoplus a_{k-p}$, cada palabra debe obedecer $W_{k}=W_{k-p+q}\bigoplus W_{k-p}$.

Hasta donde yo sé, ese es el procedimiento correcto para el uso de la GFSR algoritmo.

Correcciones o comentarios serán apreciados.