Registro de desplazamiento de retroalimentación Propiedades del registro de desplazamiento de retroalimentación

La función de retroalimentación f (a1, a2, a3,...an) es una función booleana de n elementos. Durante el pulso de reloj, si el estado del registro de desplazamiento de retroalimentación es si=(ai,…..ai+n-1) entonces

ai+n=f(ai,ai+1,… , ai+n-1), (2.1)

Este ai+n es la entrada del registro de desplazamiento. Impulsado por ai+n, cada dato del registro de desplazamiento avanza un bit, de modo que el estado se convierte en si+1=(ai+1,…..ai+n). todo el registro de turnos es ai. La serie de datos resultante: a1, a2, a3,…,an,…. Esta secuencia se denomina secuencia de registro de desplazamiento de retroalimentación que satisface la relación (2.1).

Por ejemplo, el registro de desplazamiento de retroalimentación lineal supone f(a1,a2,a3,…an)=cna1⊕cn-1a2⊕….⊕c2an-1⊕c1an,

Salida La secuencia {ai} satisface an+i= cnai⊕cn-1ai+1⊕….⊕c2an-2+i⊕c1an-1+i, donde i es un entero no negativo. Entonces la secuencia {ai} se llama secuencia de registro de desplazamiento de retroalimentación. Para un registro de desplazamiento de retroalimentación de nivel n, puede haber hasta 2n estados. Para un registro de desplazamiento de retroalimentación lineal, todos los estados "0" no se transferirán a otros estados, por lo que la secuencia del registro de desplazamiento lineal tiene el período más largo. 2n-1. Cuando el período de la secuencia {ai} generada por el registro de desplazamiento lineal de n etapas es T = 2n-1, {ai} se denomina secuencia m de n etapas.

Se ha demostrado que la secuencia m de n niveles {ai} tiene las siguientes propiedades:

En un ciclo, el número de apariciones de 0 y 1 es 2n-1- 1 veces y 2n-1 veces respectivamente;

En un círculo periódico, el número total de ejecuciones (refiriéndose al número de apariciones consecutivas de un elemento) es 2n-1. -2, el número de tramos de longitud i es 2n- i-1, y la mitad de los tramos 0 y 1, 1 0 tramo de longitud n-1 y 1 1 tramo de longitud n;

Entonces Se puede ver que la secuencia satisface el postulado tres A de Golomb con buenas propiedades estocásticas.

Cuando la función de retroalimentación f (a1, a2, a3,...an) es una función no lineal, se forma un registro de desplazamiento no lineal y su secuencia de salida es una secuencia no lineal. El período máximo de la secuencia de salida puede ser 2n, y la secuencia de registro de desplazamiento no lineal con el período máximo se denomina secuencia m. En un ciclo de la secuencia m, el número de ceros y unos es el mismo. En un círculo periódico, el número total de ejecuciones es 2n-1. Para 1≤i≤n-2, hay 2n-i-1 ejecuciones de longitud i, y la mitad de las ejecuciones son 0 y 1, y la longitud es. n-1. La ejecución no existe, hay una ejecución 0 y una ejecución 1 de longitud n. Para la secuencia de salida {ai} del registro de desplazamiento de retroalimentación lineal, satisface la relación de recursividad an+i= cnai⊕cn-1ai+1⊕….⊕c2an-2+i⊕c1an-1+i, lo cual es cierto para cualquier i≥1. Entre ellos, c0 = 1 se convierte en el polinomio característico del registro de desplazamiento lineal o la relación de recursividad. Cuando cn≠0, el registro de desplazamiento lineal no es singular. A veces se dice que el registro de desplazamiento lineal no singular no es degenerado. .