So implementieren Sie ein 128-Bit-Schieberegister mit linearer Rückkopplung und einem Byte-Element-Array in C.

Question

Ich habe ein Array wie folgt:

unsigned char A[16]

Ich verwende dieses Array, um ein 128-Bit-Hardwareregister darzustellen.Jetzt möchte ich ein lineares Rückkopplungsschieberegister (LFSR, Fibonacci-Implementierung) unter Verwendung dieses langen Registers implementieren.Die Polynome (oder Abgriffe), die mit dem Rückkopplungs-Xnor-Gate dieses LFSR verbunden sind, sind [128, 29, 27, 2, 1].

Die Implementierung eines 16-Bit-LFSR (Abgriffe bei [16, 14, 13, 11]) kann von Wikipedia wie folgt.

  unsigned short lfsr = 0xACE1u;
  unsigned bit;

  unsigned rand()
  {
    bit  = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;
    return lfsr =  (lfsr >> 1) | (bit << 15);
  }

In meinem Fall muss ich jedoch Bits von einem Byteelement zu einem anderen verschieben, z.Die msb oder A [0] müssen auf die lsb von A 1 verschoben werden.Was ist die Mindestcodierung für diese Verschiebung? Vielen Dank!

Answer 1

Um das zu verschiebende Bit zu berechnen, müssen Sie nicht jedes Mal das gesamte Array verschieben, da Sie nur an einem Bit interessiert sind (beachten Sie den & 1 am Ende der bit =-Zeile von Wikipedia).

Die richtigen Verschiebungsbeträge sind:

128 - 128 =   0   => byte  0 bit 0
128 -  29 =  99   => byte 12 bit 3
128 -  27 = 101   => byte 12 bit 5
128 -   2 = 126   => byte 15 bit 6
128 -   1 = 127   => byte 15 bit 7

Also

bit = ((A[0] >> 0) 
    ^  (A[12] >> 3) 
    ^  (A[12] >> 5) 
    ^  (A[15] >> 6) 
    ^  (A[15) >> 7)) & 1;

Jetzt müssen Sie wirklich das Bit verschieben:

A[0] = (A[0] >> 1) | (A[1] << 7);
A[1] = (A[1] >> 1) | (A[2] << 7);
// and so on, until
A[14] = (A[14] >> 1) | (A[15] << 7);
A[15] = (A[15] >> 1) | (bit << 7);

Sie können dies etwas effizienter gestalten, indem Sie uint32_t oder uint64_t anstelle von vorzeichenlosen Zeichen (abhängig von der Größe Ihres Prozessorworts) verwenden. Das Prinzip ist jedoch dasselbe.