Como os LFSRs são usados ​​em aplicativos reais como PRNGs?

Estou programando um LFSR (Linear Feedback Shift Register) em software para fins de aprendizado e encontrei algumas limitações em seu uso como um gerador de números pseudo-aleatórios (PRNG).

• Se a semente tem poucos bits '1' e poucos toques são usados, é necessário um grande "tempo de inicialização" para produzir uma saída aparentemente aleatória, com distribuição quase igual entre as execuções '1 e' 0 'ou' 0 'curto. Eu acho que com mais toques, essa inicialização seria muito mais rápida, mas todas as tabelas pré-calculadas que encontro dão dois ou quatro toques.
• Os números sequenciais são altamente correlacionados, o que é de se esperar, dado que, se o bit de saída for 0, o próximo número será metade do número anterior. Para um LFSR de 15 bits com toques [15, 14], plotar um par de números seqüenciais como pontos em um plano fornece o seguinte. Um PRNG ideal deve espalhar esses pontos por todo o lugar.

Eu sei que os LFSRs são usados ​​como contador de hardware rápido, mas também vi que é usado como um PRNG para criar ruído branco. Como é usado em aplicações do mundo real com qualidade tão ruim?

Uma excelente fonte para tudo o que o PRNG é "Sequências de registros de turno" de Solomon Golomb. Ele discute as várias classes e técnicas.

Iniciar reiniciando todos os registros é uma maneira. Ou uma carga paralela de uma semente é outra. Mas lembre-se de que uma picada de todos os zeros 'é um estado válido.

A escolha dos códigos corretos é importante, pois nem todas as configurações de feedback em um registro de turnos garantem uma seqüência máxima de PRNG.

Como você opera um PRNG afeta seu desempenho.

Para um registro de 15 bits e procurando os códigos, [15,4] é o máximo que é [15,1], mas [15,14] não está listado. -> Fonte - "Sistemas e aplicações de espectro de expansão" - Robert Dixon 3rd Ed. Página 94. Este livro é uma referência muito boa sobre implementação.

Em geral, os LFSRs fazem PRNGs ruins e a prática geral é usar apenas os bits mais baixos. Como alternativa, você pode gerar dois PRNGs de diferentes comprimentos e códigos e xor os bits mais baixos para gerar o novo código. Provavelmente, deve ser usado menos de 1/2 do comprimento do bit. Portanto, um registro de comprimento de 30 e 31 bits e XOR os 15 LSBs.

O NIST tem um excelente código de teste aqui . Então, sim, é péssimo para os PRNGs.

Os números sequenciais são altamente correlacionados, o que é de se esperar, dado que, se o bit de saída for 0, o próximo número será metade do número anterior. Para um LFSR de 15 bits com toques [15, 14], plotar um par de números seqüenciais como pontos em um plano fornece o seguinte. Um PRNG ideal deve espalhar esses pontos por todo o lugar.

Se você deseja gerar números aleatórios com um LFSR de 15 bits, não extrai um novo número aleatório a cada ciclo do relógio. Como você disse, já que está adicionando apenas um novo bit ao registro a cada ciclo do relógio, o valor em ciclo NeN+1 será fortemente correlacionado. Se você deseja gerar valores aleatórios (supondo que você possua toques adequados), precisará extrair apenas um novo valor a cada 15 relógios.

Um LFSR garante apenas um bit aleatório a cada ciclo, não 15 bits aleatórios.

Um exemplo do mundo real pode ser encontrado no manual de referência da família de microprocessadores MPC7450 RISC. O 7450 usou um pRNG para substituição de L2 e L3 que é composto por 16 travas com três registradores de deslocamento simples com os bits 0 a 4, bits 5 a 9 e bits 10 a 15. O bit 0 vem de um XOR dos bits 4 e 15, o bit 5 vem de um XOR dos bits 4 e 9 e o bit 10 vem de um XOR dos bits 6 e 15. A maneira de substituição nos caches de 8 vias é indicada pelos bits 4, 9 e 15 para L2 e pelos bits 0 , 5 e 10 para L3. Os bits eram trocados a cada ciclo, mas obviamente as substituições de cache não ocorriam com tanta frequência. (Um mecanismo alternativo de substituição baseado em contador também foi fornecido.)

Isso foi reconhecido como potencialmente problemático:

Devido à latência da pesquisa do cache L2, há 3 ciclos de relógio entre uma falha de leitura e a alocação da linha de substituição. Assim, seria possível que a mesma maneira possa ser escolhida para substituir duas ou mesmo três falhas de leitura consecutivas com o algoritmo, conforme descrito acima. Para evitar isso, o algoritmo real compara uma linha de substituição selecionada com as três linhas de substituição anteriores. Se a linha selecionada corresponder a uma das três anteriores, um valor de um, dois ou três será automaticamente adicionado ao valor que seleciona o caminho para a substituição.