© The Institution of Electrical Engineers
A windmill generator is a high-speed sequence generator capable of producing blocks of v consecutive symbols in parallel. It consists of v feedback-shift registers linked into a ring. The sequences are identical to those produced by a linear feedback-shift register with feedback polynomial of the special (‘windmill’) form f(t) = α(tv) − tLβ(t−v), where α(t) and β(t) are polynomials of degree less than L/v. Here L (relatively prime to v) is the degree of the polynomial, and is also the sum of the lengths of the registers making up the windmill. The connections of the windmill generator are directly specificed by the coefficients of α(t) and β(t). The polynomial f(t) must be primitive if the output sequence is to be of maximal period. We have devised a search for windmill polynomials over the binary field that can generate sequences of period 2L − 1 in blocks of size v = 4, 8, and 16, for L ranging over the odd values from 7 to 127. When L ≡ ±3 mod 8, no irreducible windmill polynomials at all were found. For the other odd values of L, primitive windmill polynomials seem to occur about twice as frequently as would be expected from probabilistic considerations, so that they are in fact very common. For such values of L, roughly 2/L of all windmill polynomials with given v appear to be primitive.
References
-
-
1)
-
R. Eier ,
H. Malleck
.
Anwendungen von multiplextechniken bei der erzeugung von schnellen pseudozufallsfolgen.
NTZ
,
227 -
231
-
2)
-
A.C. Arvillias ,
D.G. Maritsas
.
Combinational logicfree realisations for high-speed m-sequence generation.
Electron. Lett.
,
500 -
502
-
3)
-
R. Lidl ,
H. Niederreiter
.
(1983)
, Finite Fields, Encyclopedia of Mathematics and its Applications.
-
4)
-
D.E. Knuth
.
(1981)
, The Art of Computer Programming, Vol. 2, Semi-numerical Algorithms.
-
5)
-
COHEN, S.D.: ‘Windmill polynomials over fields of characteristic two’. preprint (to be published).
-
6)
-
W.W. Warlick ,
J.E. Hershey
.
High-speed m-sequence generators.
IEEE Trans.
,
398 -
400
-
7)
-
J.D. Alanen ,
D.E. Knuth
.
Tables of finite fields.
Sankhya Ser. (A)
,
305 -
328
-
8)
-
J. Brillhart ,
D.H. Lehmer ,
J.L. Selfridge ,
B. Tuckerman ,
S.S. Wagstaff
.
(1983)
, Factorisation of .
-
9)
-
Smeets, B.J.M.: `On linear recurring sequences', 1987, PhD dissertation, University of Lund.
-
10)
-
K.H. Mörmann
.
Erzeugung von binären quasi-zufallsfolgen hoher takt-frequenzen durch multiplexen.
Siemens Forsch.-u. Entwickl. Ber.
,
218 -
224
-
11)
-
A. Lempel ,
W.L. Eastman
.
High-speed generation of maximal length sequences.
IEEE Trans.
,
227 -
229
-
12)
-
N. Weste ,
K. Eshragian
.
(1985)
, Principles of CMOS VLSI Design.
-
13)
-
F. Surbock ,
H. Weinrichter
.
Interlacing properties of shift-register sequences with generator polynomials irreducible over GF(p).
IEEE Trans.
,
386 -
389
-
14)
-
W.J. Hurd
.
Efficient generation of statistical good pseudonoise by linearly interconnected shift registers.
IEEE Trans.
,
146 -
152
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-e.1989.0054
Related content
content/journals/10.1049/ip-e.1989.0054
pub_keyword,iet_inspecKeyword,pub_concept
6
6