Desde el punto de vista de la implementación, ¿cuánto tiempo tomará la generación de números pseudoaleatorios por el Registro de Cambio de Retroalimentación Lineal (LFSR) cuando se implemente en, por ejemplo, el Procesador de Señal Digital? Se supone que la semilla es 4 bit larga. ¿Cómo se puede calcular el tiempo de implementación antes de implementar LFSR?
Cualquier ayuda / sugerencia es apreciada!
Hay dos formas del algoritmo LSFR.
Hay una implementación de hardware, que calcula la paridad = (bitcount (estado y máscara)) y 1, y desplaza el bit de paridad al final de la palabra. Esto se asigna bien a los registros de cambio de hardware, pero no es eficiente en software. Es el cálculo de la paridad que no tendrá una operación de bitcount () de un solo ciclo disponible.
Luego está la implementación del software, que funciona en una palabra completa a la vez. Seudocódigo para esto es
if (state&1 == 1)
state = state XOR mask;
state = state >> 1;
Todos los bits de estado que corresponden a la máscara se condicionan XOR condicionalmente al mismo tiempo, cuando el LSB es 1, y se deja sin alterar cuando es 0. Esto solo funciona fácilmente para longitudes de palabra hasta la longitud de palabra nativa del procesador , pero la extensión a la operación de múltiples palabras es trivial.
La máscara para el tipo de software es la misma que para el tipo de hardware, a excepción de ser un bit invertido, es decir, el MSB de uno es el LSB del otro.
El tiempo de ejecución para un solo bit cambia dependiendo de si un 0 o 1 está presente en el LSB, esto puede o no ser aceptable dependiendo de sus requisitos precisos. Si se requiere un tiempo determinista, entonces necesitará una instrucción else rellenada con uno o más NOP de acuerdo con su procesador particular. Como el número total de 0 y 1 bits es determinista, puede calcular el tiempo de ejecución para un total de 2 ^ m-1 bits, y así el tiempo promedio para un bit.
Si está intentando obtener una cuenta regresiva de las operaciones, tal vez incluso pensando en el ensamblador, entonces tenga en cuenta que en muchos procesadores, una operación de cambio a la derecha coloca el LSB en uno de los bits de bandera, a menudo el acarreo, para que esté disponible para turnos de varias palabras. Este bit a menudo se puede probar directamente, evitando así la necesidad de enmascarar el LSB como una operación separada.
Una implementación de software de un LFSR es algo así como:
unsigned int LFSR(unsigned int* state, unsigned int mask){
int resbit = state & 1;
unsigned int parity = bitcount(*state & mask) & 1;
*state = (*state >> 1) | parity << 31;
return resbit;
}