Registrador de Deslocamento

Um Registrador de Deslocamento é um circuito que desloca de uma posição os elementos de um vetor de bits. O registrador de deslocamento tem uma entrada (um bit) e uma saída (também um bit), e é comandado por um pulso de relógio. Quando o pulso ocorre, o bit de entrada se transforma no bit mais significativo do vetor, o bit menos significativo é jogado na saída do registrador, e todos os outros bits são deslocados de uma posção em direção ao bit mais significativo do vetor (em direção à saída).

Um Registrador de Deslocamento com Retroalimentação Linear (em inglês, lfsr) é um registrador de deslocamento no qual o bit de entrada é determinado pelo valor do ou-exclusivo de alguns dos bits do registrador antes do pulso de relógio. Os bits que são utilizados na retroalimentação do registrador são chamados de torneiras. A figura abaixo mostra um lfsr de 16 bits, com quatro torneiras (bits 11, 13 , 14 e 16).

Fonte: http://br.spoj.pl/problems/REGISTRA/

A configuração das torneiras para a retroalimentação pode ser expressa como um polinômio mod 2. Isso significa que os coeficientes do polinômio pode ser  0 ou 1. Este polinômio é chamado de polinômio de retroalimentação ou polinômio característico. Por exemplo, a configuração das torneiras acima pode ser expressa como o seguinte polinômio mod 2:

$x^{16} + x^{14} + x^{13} + x^{11} + 1$

Este registrador de deslocamento com retroalimentação linear pode ser utilizado para a geração de números pseudo-aleatórios. Um registrador de deslocamento com retroalimentação maximal gera uma sequência pseudo-aleatória periódica e maximal. O polinômio de retroalimentação que gera uma sequência pseudo-aleatória com comprimento maximal é chamado de polinômio primitivo.

Tabela de polinômio primitivos

Considere o seguinte exemplo:

n = 3

O resultado do xor dos bits 2 e 3 será 1. O resultado será deslocado 1 bit para a direita e o bit mais a esquerda será o resultado do xor dos bits 2 e 3.

 unsigned lfsr = 1u;
 unsigned period = 1u;
 unsigned bit;
 
 do {
  
  /* taps: 3 2; characteristic polynomial: x^3 + x^2 + 1 */
  bit  = ((lfsr >> 0) ^ (lfsr >> 1)  ) & 1;
  printf("bit %u\n",bit);
  lfsr =  (lfsr >> 1) | (bit  << 2);
  printf("period %u lfsr %u\n",period, lfsr);
  period++;
 } while(lfsr != 1u);

Saída:

bit 1
period 1 lfsr 4
bit 0
period 2 lfsr 2
bit 1
period 3 lfsr 5
bit 1
period 4 lfsr 6
bit 1
period 5 lfsr 7
bit 0
period 6 lfsr 3
bit 0
period 7 lfsr 1