Prüfen ob Wert teil eines LFSR

nach jedem schiebevorgang die folge mit diesem wert vergleichen...

Die Aufgabenstellung ist eine Theoriefrage. Ich bezweifle stark, dass 
der Lektor von uns verlangt einen 28Bit breiten Vektor händisch 
durchzuschieben, bis wir den gesuchten Wert erreichen...

In meiner Simulation wird der Wert trotz 100MHz Takt erst nach ~2,4s 
erreicht. Das wäre also wohl eine Lebensaufgabe.

Vincent Hamp schrieb:

>>Ich bezweifle stark, dass
> der Lektor von uns verlangt einen 28Bit breiten Vektor händisch
> durchzuschieben, bis wir den gesuchten Wert erreichen...

Kann man ja einen Rechner machen lassen. Der Wert 0x2b0638b wird 
erreicht und zwar nach 358655852 Runden.

> In meiner Simulation wird der Wert trotz 100MHz Takt erst nach ~2,4s
> erreicht. Das wäre also wohl eine Lebensaufgabe.

Meine desktop Gurke braucht für die komplette Lösung nen paar Sekunden. 
Das Polynom produziert allerdings keine maximum length sequence 
http://de.wikipedia.org/wiki/Maximum_Length_Sequence. MLS bis 168er 
Ordnung gibts hier:
http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf

allerdings mit 0 als Startwert und XNOR Rückkopllung.

> Die Aufgabenstellung ist eine Theoriefrage.

Dann würde mich die Lösung dazu sehr interessieren. Ich bin leider nicht 
in der Lage zu bestimmen, ob ein Polynom eine MLS liefert oder nicht 
(außer duch Probieren, das geht aber bei z.B. 168er Ordnung nicht mehr).

math rulez!
Cheers
Detlef

PS. Ich hoffe, dass ich mich nicht verdaddelt habe, ist aber nicht 
auszuschließen.


/*******************************************************************/
int main(int  argc , char ** argv)
/*******************************************************************/
{
   unsigned char *f,c;
   unsigned long k,p;

f=(char *)malloc(1<<26);
if(f==NULL){printf("geht nich \n"); return;}

for(k=0;k<(1<<26);k++) {
  if((k&((1<<16)-1))==0) printf("%d \n",k);
  f[k]=0;
}

p=0xffffffff;

for(k=0;k<(1<<29);k++) {
  if((k&((1<<19)-1))==0) printf("%d \n",(1<<29)-k);
  p=p&((1<<29)-1);
  if(p==0x2b0638b) { printf("yo %d %x %x \n",k,p,f[p>>3]); return;}
  c=f[p>>3]&(unsigned char)(1<<(p&7));
  if(c) { printf("gibbs schon %d %x %x \n",k,p,f[p>>3]); return;}
  f[p>>3] |= (unsigned char)(1<<(p&7));
  p = (p<<1)|(((p>>28)&1)^((p>>3)&1));
}

for(k=0;k<(1<<26);k++) {
  if((k&((1<<16)-1))==0) printf("%d \n",k);
  //if(f[k] != 0xff)
  printf("xxxxxxxxxxxxxxxxxxxx %d %x \n",k,f[k]);
}
return 0;
}

Hallo

Danke für deine Antwort.
Die Xilinx Note hab ich auch bereits gelesen.

Weiters hab ich dann folgendes Dokument entdeckt:
http://jaja.kn.vutbr.cz/~kajan/lfsr.pdf

Interessanterweise gibt es da eine Tabelle, in der 28 und 3 als 
"Polynomial 1-Terms (Xn)" sehr wohl gelistet ist. Kurz dacht ich dann, 
dass XOR und XNOR Verknüpfungen unterschiedliche Polynome erfordern... 
das dürft aber leider auch nicht der Fall sein:
"The polynomial used to generate the maximum length sequence is the same 
for
Fibonacci/Galois implementations, and with XOR or XNOR gates for 
feedback."

Jetzt bin ich beim Überfliegen des Dokuments nicht wirklich schlau 
geworden, was der Tabelleneintrag "Polynomial 1-Terms (Xn)" überhaupt 
ist...


Hab meine Antwort aber vorerst mal so begründet, dass 28/3 sehr wohl MSL 
taps sind, sonst wär die Frage imho nicht zu beantworten.

Also mein Wissen hier is auch sehr lückenhaft, jedoch weiß ich, dass ein 
LFSR ausschließlich in Kombinationen mit den richtigen Feedback Taps 
(bzw. dem richtigen Feedback Polynom) eine sogenannte Maximal Sequence, 
sprich 2^n-1 states annimmt.

Was ich bisher so mitbekommen hab gibt es aber für jede Bitbreite 
etliche "richtige" Feedback Taps, die dieses Maximum erzeugen.

/edit
Hier eine der bisher besten Seiten, die ich diesbezüglich ergoogled hab:
http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm

/edit2
Abhängig von der Art der Verknüpfung (XOR / XNOR) kann auch ein mit 
lauter 1ern befülltes LFSR ein gelockter State sein.

bzw.

"irreducible and primitive polynom"


falls du was mit PASCAL Code anfangen kannst hier mein Source:

Gruß Hagen

1

{ follow procedures create and check suitable Polynoms for above

2

  Linear Feedback Shift Registers.

3

  Such polynoms must be primitive, irreducible to produce maximal

4

  length LFSR's. }

5

6

7

type

8

  TFactors = array[0..6] of Cardinal;

9

10

function FactorOrder(var Factors: TFactors; Degree: Integer): Integer;

11

// find factors of 2^Degree-1 = possible Order of Polynom

12

// can be surrely more optimized, but the runtime here is not important yet

13

// as example:

14

//   For all orders from 2^0 -1 upto 2^32-1 exists only 33 possible primefactors.

15

//   Instead to looping trough all odd numbers as factors we could reduce the

16

//   loopcount if we use a lookuptable of all the 33 possible primefactors.

17

var

18

  Order,Rest,Prime,Bound,Factor,LastFactor: Cardinal;

19

begin

20

  Result := 0;

21

  LastFactor := 0;

22

  Prime := 3;

23

  Order := $FFFFFFFF shr (32 - Degree);

24

  Rest := Order;

25

  Bound := Round(Sqrt(Rest));

26

  while (Rest <> 1) and (Prime < Bound) do

27

    if Rest mod Prime = 0 then

28

    begin

29

      Rest := Rest div Prime;

30

      Factor := Order div Prime;

31

      if Factor <> LastFactor then

32

      begin

33

        LastFactor := Factor;

34

        Factors[Result] := Factor;

35

        Inc(Result);

36

      end;

37

      Bound := Round(Sqrt(Rest));

38

    end else Inc(Prime, 2);

39

  if Result > 0 then

40

  begin // only if 2^Degree-1 it self isn't prime

41

    Factors[Result] := Order div Rest;

42

    Inc(Result);

43

  end;

44

end;

45

46

function PolyIsPrimitive(Poly: Cardinal; Degree: Integer; const Factors: TFactors; FactorCount: Integer): Boolean;

47

// small, clean and efficient for small Degrees upto 32

48

// for larger Degrees we should go with real GF(2) arithmetic

49

type

50

  TPolyMatrix = array[0..31] of Cardinal;

51

52

  procedure PolyCopy(var D: TPolyMatrix; const S: TPolyMatrix);

53

  {$IFDEF ASM}

54

  asm

55

         XCHG  EAX,EDI

56

         XCHG  EDX,ESI

57

         MOV   ECX,32

58

         REP   MOVSD

59

         MOV   EDI,EAX

60

         MOV   ESI,EDX

61

  end;

62

  {$ELSE}

63

  begin

64

    Move(S, D, SizeOf(S));

65

  end;

66

  {$ENDIF}

67

68

  procedure PolyInit(var M: TPolyMatrix; Poly: Cardinal; Degree: Integer);

69

  var

70

    L: Cardinal;

71

    I: Integer;

72

  begin

73

    L := $80000000;

74

    M[Degree -1] := L;

75

    for I := 0 to Degree -2 do

76

    begin

77

      L    := L shr 1;

78

      M[I] := L;

79

    end;

80

    for I := 0 to Degree -2 do

81

    begin

82

      if Odd(Poly) then M[I] := M[I] or $80000000;

83

      Poly := Poly shr 1;

84

    end;

85

  end;

86

87

  procedure PolyMul(var R: TPolyMatrix; const M: TPolyMatrix; Degree: Integer);

88

  {$IFDEF ASM}

89

  // speedup >40% over all, and of course follow asm is nothing important or special tricky

90

  asm

91

         PUSH  EDI

92

         PUSH  ESI

93

         PUSH  EBX                       

94

         PUSH  EBP

95

         LEA   EDI,[EAX + ECX * 4]  // on top of R, eg @R[Degree]

96

         LEA   ESI,[EDX + ECX * 4]  // on top of M

97

         NEG   ECX                  // -Degree, we loop from -Degree upto 0

98

         MOV   EBP,ECX

99

  @@1:   MOV   EDX,[ESI + EBP * 4]  // outerloop

100

         XOR   EAX,EAX

101

         PUSH  ECX                  // save -Degree, eg. loopcounter

102

  @@2:   ADD   EDX,EDX              // inner loop, branchfree xor'ing is important for speed

103

         SBB   EBX,EBX

104

         AND   EBX,[EDI + ECX * 4]

105

         XOR   EAX,EBX

106

         INC   ECX

107

         JNZ   @@2

108

         POP   ECX                  // restore loopcounter

109

         INC   EBP

110

         PUSH  EAX                  // push T[] on stack

111

         JNZ   @@1

112

         SUB   EDI,4

113

  @@3:   POP   DWord Ptr [EDI]      // R[] = T[]

114

         SUB   EDI,4

115

         INC   ECX

116

         JNZ   @@3

117

         POP   EBP

118

         POP   EBX

119

         POP   ESI

120

         POP   EDI

121

  end;

122

  {$ELSE}

123

  var

124

    T: TPolyMatrix;

125

    I,J: Integer;

126

    N,D: Cardinal;

127

  begin

128

    for I := 0 to Degree -1 do

129

    begin

130

      N := M[I];

131

      D := 0;

132

      for J := 0 to Degree -1 do

133

      begin

134

        if N and $80000000 <> 0 then D := D xor R[J];

135

        N := N shl 1;

136

      end;

137

      T[I] := D;

138

    end;

139

    PolyCopy(R, T);

140

  end;

141

  {$ENDIF}

142

143

  procedure PolyPowMod(var R: TPolyMatrix; const M: TPolyMatrix; N: Cardinal; Degree: Integer);

144

  var

145

    L: Cardinal;

146

  begin

147

    PolyCopy(R, M);

148

    L := $80000000;

149

    while N and L = 0 do L := L shr 1;

150

    while L > 1 do

151

    begin

152

      L := L shr 1;

153

      PolyMul(R, R, Degree);

154

      if L and N <> 0 then PolyMul(R, M, Degree);

155

    end;

156

  end;

157

158

var

159

  P,M: TPolyMatrix;

160

  I,J: Integer;

161

  State: Cardinal;

162

begin

163

  Result := False;

164

  PolyInit(M, Poly, Degree);

165

  PolyCopy(P, M);

166

  State := P[0];

167

  for I := 1 to Degree do

168

  begin

169

    PolyMul(P, P, Degree);

170

    if P[0] = State then

171

      if I = Degree then

172

      begin

173

        for J := 0 to FactorCount -1 do

174

        begin

175

          PolyPowMod(P, M, Factors[J], Degree);

176

          if P[0] = $80000000 then Exit;

177

        end;

178

        Result := True;

179

        Exit;

180

      end else Exit;  

181

  end;    

182

end;

183

184

function FindPrimitivePolynom(Poly: Cardinal; Degree: Integer): Cardinal;

185

// on PIV 1.5 GHz

186

// 4.95 ms (asm) 6.97 ms (pascal) on degree 32 searches

187

// 0.41 ms (asm) 0.60 ms (pascal) on degree 16 searches

188

// on random input about 1/16 are primitive polynoms

189

// Poly / 2, means Result *2 +1 = real polynom

190

191

  function EvenParity(Poly: Cardinal): Boolean;

192

  // returns TRUE if count of bits set to 1 in Poly is even

193

  {$IFDEF ASM}

194

  asm

195

       MOVZX  EDX,AX

196

       SHR    EAX,16

197

       XOR    EAX,EDX

198

       XOR     AH,AL

199

       SETP    AL

200

  end;

201

  {$ELSE}

202

  var

203

    I: Cardinal;

204

  begin

205

    I := 0;

206

    while Poly <> 0 do

207

    begin

208

      Inc(I, Poly and 1);

209

      Poly := Poly shr 1;

210

    end;

211

    Result := not Odd(I);

212

  end;

213

  {$ENDIF}

214

215

var

216

  Factors: TFactors;

217

  Mask: Cardinal;

218

  FactorCount: Integer;

219

begin

220

  if Degree > 0 then

221

  begin

222

    Mask := $FFFFFFFF shr (32 - Degree);   // eg. 2^Degree -1

223

    Poly := Poly and Mask or 1 shl (Degree -1);

224

    FactorCount := FactorOrder(Factors, Degree);

225

    while Poly <= Mask do

226

      if PolyIsPrimitive(Poly, Degree, Factors, FactorCount) then

227

      begin

228

        Result := Poly;

229

        Exit;

230

      end else

231

      repeat

232

        Inc(Poly);

233

      until (Poly > Mask) or EvenParity(Poly);

234

  end;

235

  Result := 0;

236

end;

237

238

function IsPolynomPrimitive(Poly: Cardinal): Boolean;

239

// on PIV 1.5 GHz

240

// ~0.446 ms on random polys with degree 32

241

// ~0.052 ms on random polys with degree 16

242

var

243

  Factors: TFactors;

244

  FactorCount,Degree: Integer;

245

  P: Cardinal;

246

begin

247

  Degree := 0;

248

  P := Poly;

249

  while P <> 0 do

250

  begin

251

    P := P shr 1;

252

    Inc(Degree);

253

  end;

254

  if Degree > 0 then

255

  begin

256

    FactorCount := FactorOrder(Factors, Degree);

257

    Result := PolyIsPrimitive(Poly, Degree, Factors, FactorCount);

258

  end else Result := False;

259

end;

um nun zu prüfen ob eine "zahl" durch ein Polynom in GF(2) erzeugbar ist 
muß man das Polynom und diese Zahl in nicht mehr reduzierebare und 
primitive Polynome zerlegen, quasi das gleiche machen wie eine 
natürliche Zahl in deren Primzahlpotenzen zu zerlegen. Zwei natürliche 
Zahlen sind dann teilerfremd wenn sie eine Primzahlpotenz enthalten die 
nicht in beiden Primzahlpotenzzerlegungen der beiden Zahlen vorkommt. 
Gleiches gilt für GF(2).

Ist das gewählte Polynom des LFSRs also primitiv und nicht reduzierbar 
(quasi wie eine Primzahl in N) dann gilt: wenn die "Zahl" kleiner der 
Order -1 des Polynoms und nicht Null ist dann ist sie Bestandteil der 
Menge der erzeugbaren "Zahlen" des LFSRs => MLS.

Gruß hagen

Lattice User schrieb:
> 1.) Hast du das Programm auch ohne ASM Einlagen?

Ist PASCAL und Assembler, dieser steht in DEFINES gekapselt da, also 
immer mit dem dazugehörigen PASCAL Source. Leider mit der Forensoftware 
hier nicht so gut ersichtlich.

Lattice User schrieb:
> Ein primitives Polynom ist immer nicht
> reduzierbar, aber der Umkehrschluss gilt nicht:

Das ist "korrekt" weswegen ich

Hmm schrieb:
> Ich lese da: "primitiv und nicht reduzierbar"

geschrieben habe ;)
Es gibt aber auch primitive Polynome die reduzierbar sind, aber soweit 
ich weiß nicht in GF(p^m). Man müsste also auch das gewählte Field mit 
angeben damit die Aussage "primitiv heist immer auch nicht reduzierbar" 
stimmt, es gibt ja nicht nur Polynome in GF(x).

siehe http://de.wikipedia.org/wiki/Primitives_Polynom
und dann http://de.wikipedia.org/wiki/Inhalt_%28Polynom%29

Gruß hagen

Lattice User schrieb:
> Hagen Re schrieb:
>> Ist PASCAL und Assembler, dieser steht in DEFINES gekapselt da, also
>> immer mit dem dazugehörigen PASCAL Source. Leider mit der Forensoftware
>> hier nicht so gut ersichtlich.
>
> Ich meinte pures Pascal, dann wäre es leichter es in eine gängigere
> Sprache zz übersetzen. So ist das mir zuviel Arbeit.

Nochmal anders formuliert: es ist pures PASCAL, ignoriere doch einfach 
alls zwischen {$IFDEF ASM} und {$ELSE} dann bleibt das gewünschte pure 
PASCAL übrig. Oder noch anders formuliert: der Source ist je nach 
Compiler Defines reines PASCAL oder gemischt mit Assembler. Oder soll 
ich dir das jetzt noch raus löschen aus dem Source ?

Lattice User schrieb:
> Hmm, Wolfram ist anderer Meinung, gkeich der erste Satz.

Nö sind sie nicht. Ich sagte doch das die Angabe worauf sich die 
Polynomarithmetik bezieht wichtig ist damit diese Aussage stimmt. Auch 
Wolfram bezieht sich auf Polynome in Galois Feldern. Es gibt aber auch 
andere Polynome in anderen Domains, und bei denen muß diese Aussage 
nicht zwangsläufig stimmen. Ich gebe aber zu das es auch ein Tick von 
mir ist aussagenlogisch darauf zu bestehen das das Polynom "nicht 
reduzierbar und primitiv" sein muß. In GF(p^m) heist dies das ein 
primitives Polynom zangsläufig auch nicht reduzierbar sein wird, das muß 
aber für andere Polynomarithmetiken nicht stimmen. Ich habe es eben so 
gelernt es so zu formulieren, mein Lehrer war da auch sehr eigensinnig 
und penibel mit seinen Formulierungen. Letzendlich ist das egal, meine 
Ausage ist ansich richtig und wir fangen über Trivialitäten einen 
Glaubenskrieg an, es sind nur Worte und wir wissen was gemeint war.

Gruß Hagen

Lattice User schrieb:
> Ich meinte pures Pascal, dann wäre es leichter es in eine gängigere
> Sprache zz übersetzen.

PASCAL ist eine sehr gängige Sprache, was sonst ;)

Lattice User schrieb:
> Steht übrigens auch in deinem ersten Link:
> "In der Ringtheorie wird der Begriff primitives Polynom anders
> verwendet."

Ich weiß, das war ja auch der Grund warum ich es explizit verlinkt habe 
;)

Lattice User schrieb:
> Hagen Re schrieb:
>> PASCAL ist eine sehr gängige Sprache, was sonst ;)
>
> Vor 30 Jahren :-)

naja, ich arbeite für einige deutsche SW-Buden mit markanten 
Marktanteilen die mit Delphi arbeiten und das ist nichts anderes als 
PASCAL, übrigens ist der Source von mir da oben ebenfalls in 
Wirklichkeit ein Delphi Source.

Gruß hagen

Wen's interessiert: Angehängt das korrigierte Programm, auch mit XNOR 
Rückkopplung. Es probiert aus, ob ein gegebenes Polynom die MLS erzeugt. 
Das Polynom, das der TO genannt hatte, produziert eine MLS, also kommt 
auch der gesuchte Wert vor.

Danke an die Beteiligten, wieder was dabeigelernt.

Cheers
Detlef

/*******************************************************************/
int main(int  argc , char ** argv)
/*******************************************************************/
{

   unsigned char *f,c;
   unsigned long k,p;

#define NN (28)

f=(char *)malloc(1<<(NN-3));
if(f==NULL){printf("geht nich \n"); return;}

for(k=0;k<(1<<(NN-3));k++) {
  if((k&((1<<16)-1))==0) printf("%d \n",k);
  f[k]=0;
}

//p=0xffffffff;
p=0x0;

for(k=0;k<(1<<NN);k++) {
  if((k&((1<<21)-1))==0) printf("%d \n",(1<<NN)-k);
  p=p&((1<<NN)-1);
  if(p==0x2b0638b) { printf("yo %d %x %x \n",k,p,f[p>>3]); }
  c=f[p>>3]&(unsigned char)(1<<(p&7));
  if(c) { printf("gibbs schon %d %x %x \n",k,p,f[p>>3]); return;}
  f[p>>3] |= (unsigned char)(1<<(p&7));
  //p = (p<<1)|(((p>>27)&1)^((p>>2)&1));
  p = (p<<1)|((~(((p>>27)&1)^((p>>2)&1)))&1);
}

return 0;





}

>>(*) The Great Trinomial Hunt (Richard P. Brent, Paul Zimmermann)

Das liest sich spannend, der Zusammenhang zwischen Trinomials und 
Mersenne Primes ist ja auch erstaunlich (für mich zumindest).

x^43112609+x^4463337+1 ist auch primitiv, das gibt schon ordentliche 
Periodenlängen.

math rulez!
Cheers
Detlef