General Disclaimer

One or more of the Following Statements may affect this Document

This document has been reproduced from the best copy furnished by the 

organizational source. It is being released in the interest of making available as 

much information as possible.

This document may contain data, which exceeds the sheet parameters. It was 

furnished in this condition by the organizational source and is the best copy 

available.

This document may contain tone-on-tone or color graphs, charts and/or pictures, 

which have been reproduced in black and white.

This document is paginated as submitted by the original source.

Portions of this document are not fully legible due to the historical nature of some 

of the material. However, it is the best reproduction available from the original 

submission.

Produced by the NASA Center for Aerospace Information (CASI)

JPL Publication 85.7

Periodic Binary Sequence Generators:

Very Large Scale Int

Circuits Consideratic

Marvin Perlman

December 1984

P~

National Aeronautics and Space Administration

Jet Propulsion Laboratory

California Institute of Technology

Pasadena, California

a
The research described in this publication was carried out by the Jet Propulsion

Laboratory, California Institute of Technology, under contract with the

National Aeronautics and Space Administration, NASA Task RE-210.
ABSTRACT

Feedback shift registers have proven to be efficient periodic binary

sequence generators Polynomials of degree r over a Galois field

characteristic 2 (GF(2)) characterize the behavior of shift registers with

liner-logic feedback.

The object of this report is the algorithmic determination of the

trinomial of lowest degree, when it exists, that contains a given irreducible

polynomial over GF(2) as a factor. This corresponds to embedding the behavior

of an r-stage shift register with linear-logic feedback into that of an

n-stage shift register with a single two-input modulo 2 summer (i.e.,

Exclusive-0R gate) in its feedback. This leads to Very Large Scale Integrated

(VLSI) circuit architecture of maximal regularity (i.e., identical cells) with

intercell communications serialized to a maximal degree.
I PAGE BLANK NOW F f.S=

v

ACRONYMS

Cp clock pulse

CP Compatible Pair

CPI Clock Pulse Interval

FSR Feedback Shift Register

GF Galois Field

ISFSR shift register with interstage feedback

LCM Least Common Multiple

MOSFET Metal-Oxide-Semiconductor Field-Effect Transistor

NMOS N Channel Metal-Oxide Semiconductor

PN Pseudonoise

SSFSR shift register with single stage feedback

VLSI Very Large Scale Integrated circuits
CONTENTS

I. BACKGROUND . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-1

II. GENERATORS OF PERIODIC BINARY SEQUENCES . . . . . . . . . . . . . 2-1

A. FEEDBACK SHIFT REGISTERS . . . . . . . . . . . . . . . . . . 2-1

B. FEEDBACK SHIFT REGISTERS CHARACTERIZED BY

RECURRENCE RELATIONS . . . . . . . . . . . . . . . . . . . . 2-8

III. AN ISOMORPHISM BETWEEN THE STATES OF AN r—STAGE

SSFSR AND AN r—STAGE ISFSR . . . . . . . . . . . . . . . . . . . . 3-1

IV. THE EXISTENCE AND ALGORITHMIC DETERMINATION OF A TRINOMIAL

OF LEAST DEGREE THAT CONTAINS A GIVEN IRREDUCIBLE

POLYNOMIAL OVER GF(2) AS A FACTOR . . . . . . . . . . . . . . . . 4-1

A. PRIMITIVE POLYNOMIALS OVER GF(2) . . . . . . . . . . . . . . 4-1

B. IRREDUCIBLE NONPRIMITIVE POLYNOMIALS OVER GF(2) . . . . . . 4-33

V. VERY LARGE SCALE INTEGRATED CIRCUIT CONSIDERATIONS . . . . . . . . 5-1

VI. SUMMARY . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6-1

VII. REFERENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7-1

PRECMNO PADS BDANK NOT MMED

APPENDIXES

A. NUMBER—THEORETIC FUNCTIONS . . . . . . . . . . . . . . . . . A-1

B. TRINOMIAL OF LEAST DEGREE THAT CONTAINS A GIVEN

PRIMITIVE POLYNOMIAL OF DEGREE r OVER GF(2) AS A FACTOR B-1

C. TRINOMIAL OF LEAST DEGREE THAT CONTAINS A GIVEN

IRREDUCIBLE NONPRIMITIVE POLYNOMIAL OF DEGREE r OVER

GF(2) AS A FACTOR . . . . . . . . . . . . . . . . . . . . . C-1

vii
Figures

2-1. Functional Logic Diagram of a Feedback Shift

Register that Performs Multiplication by

a Modulo a6 + a5 + a2 + a + 1 . . . . . . . . . . . . . . . 2-2

2-2. Functional Logic Diagram of a Feedback Shift

Register that Performs Division by

a Modulo a6 + a5 + a2 + a + 1 . . . . . . . . . . . . . . . 2 -4

2-3. Functional Logic Diagram of an r-stage Shift Register

with Linear Logic Feedback (SSFSR) . . . . . . . . . . . . . 2-9

3-1. A 4-Stage SSFSR and a 4-Stage ISFSR with Isomorphic

State Spaces . . . . . . . . . . . . . . . . . . . . . . 3-5

3-2. The One 2 to-One Correspondence Between dk-ldk-2dk-3

and b 2 + b l y + 1 . . . . . . . . . . . . . . . . . . . . . 3-19

3-3. An SSFSR and its Corresponding ISFSR of Identical

Complexity . . . . . . . . . . . . . . . . . . . . . 3-37

4-1. (a) A 31-bit PN Sequence, (b) its Run Length Properties,

(c) Closure Illustrated in the Isomorphic Abelian Croup 4-6

5-1. Master-Slave O-Enable JK Flip-Flop . . . . . . . . . . . . . 5-2

5 -2. NMOS Circuit of a Static 0-Enable JK Flip-Flop . . . . . . . 5 -7

5-3. A Functional Logic Diagram of a n-Stage SSFSR

Characterized by Xn + Xa + 1 . . . . . . . . . . . . . . . . 5-8

Tables

1-1. GF(2 6 ) Generated b a, a Root of

f(x) - x6 + x5 + xi + x + 1, with a* Adjoined . . . . . . 1-3

6

1-2. Irreducible Factors of x2 -1 - 1 Over GF(2) . . . . . . . . 1-8

1-3. Elements Generated by /g a Root of

f(x)-x6 +x5 +x4 +xi + 1 . . . . . . . . . . . . . . . . 1-10

1-4. Irreducible Factors of x 21 - 1 Over GF(2) . . . . . . . . . 1-12

1-5. Irreducible Self-Reciprocal Factors of X513 - 1

Over GF(2) Enumerated by the Order of their Roots and

their Degree . . . . . . . . . . . . . . . . . . . . . . . . 1-19

2-1. Equal Length FSR Cycles of (nonzero) States Corresponding

to the Decomposition of a Multiplicative Group into a

Cyclic Subgroup figil and Cosets {y$j F

 and 1 SQ J . . . . . . 2-7

viii
2-2. State Table of a 7-Stage SSFSR and Components of a

Decomposition for f(x) s 1 + x + x 3 + x4 + x7

(1+x2 +x 3 )(1+x+x2 +x 3 +x4 ) . . . . . . . . . . . 2-21

2-3. Initial States of a 7-Stage SSFSR that Map onto a g(x)

Coctaining x4 + x3 + x2 + x + 1 as a Factor . . . . . . . . 2-28

3-1. The One-to-One Correspondence Between the States of an

SSFSR and the g(x) Polynomials . . . . . . . . . . . . . 3-2

3-2. Cycle Structure and Isomorpism of SSFSR and ISFSR States

Whose Respective Next State Transformations are Affine . . . 3-23

4-1 A 63-State Cycle Associated with x6 + x5 + x2 + x + 1

a Factor of x ll + x8 + 1 . . . . . . . . . . . . . . . . . . 4-18
SECTION I

BACKGROUND

The root a of a primitive polynomial f(x) is a generator of the cyclic

group

a,a , ... ,a 2 2r-2 2r-1

, a = 1

The 2 r - 1 elements of the multipl.iLcAtive group with the element 0 adjoined

are members of a Galois Field of order 2 r (i.e., GF(2 r )). The elements 0

and 1 comprise GF(2), a subfield of GF(2 r ), and GF(2 r

)is a finite

extension of GF(2).

Each element in GF(2r ) satisfies

r r

x2 -x=x(x2-1-1) -0

The element 0 satisfies x - 0 and each of the nonzero elements satisfies 

x2r-1-1=0

Example 1

Consider the primitive polynomial GF(2)

f(x) `x6+x5 +x2 +x+ 1

with one of 6 distinct roots denoted by a. Every nonzero element in GF(2 6)

is expressible as an integer power of a.

a j - b5a5 + b4a4 + b 3 a 3 + b2a2 + b 1 a + b0

1-1
where b i E GF(2) and a is among the 2 r - 1 roots of unity. The

polynomial in a is of degree 5 or less since

ti 5 2

C1 -a +a +a + i

The element 0 is the constant zero polynomial denoted by

t

a*s0•a5 +0•a4+... +0

Members of GF(2 6 ), generated by a with a * adjoined, appear in Table 1-1.

The binary operation of "addition" defined on the field elements is

termwise sum modulo 2 (i.e., vector addition over GF(2)).

For example,

1 1 1 1 0 0 (a14)

1

+ 1 1 0 1 1 1 (a54 )

001011 (a19)

The binary operation of "multiplication" on the field elements is

defined as

(b5a5 + b4a4 +, ... , + b0 ) (d 5a5 + d4a +, ... , + d0)

F with the result reduced modulo

f(a) -a6+a5+a2+a+i

Since each element is expressible as a power of 0,

a iaj • a (i + j) mod 63

1-2 
Table 1-1. GF(26 )

With a

Generated by a,

* Adjoined

a Root of f(x) x6 + x5 + x2 + x + 1,

i of 1 b5 b4 b3 b2 b 1 b0 i of Q i b5 b4 b3 b2 b l b0

* 0 0 0 0 0 0 31 0 0 1 1 1 0

32 0 1 1 1 0 0

0 0 0 0 0 0 1 33 1 1 1 0 0 0

1 0 0 0 0 1 0 34 0 1 0 1 1 1

2 0 0 0 1 0 0 35 1 0 1 1 1 0

3 0 0 1 0 0 0 36 1 1 1 0 1 1

4 0 1 0 0 0 0 37 0 1 0 0 0 1

5 1 0 0 0 0 0 38 1 0 0 0 1 0

6 1 0 0 1 1 1 39 1 0 0 0 1 1

7 1 0 1 0 0 1 40 1 0 0 0 0 1

8 1 1 0 1 0 1 41 1 0 0 1 0 1

9 0 0 1 1 0 1 42 1 0 1 1 0 1

10 0 1 1 0 1 0 43 1 1 1 1 0 1

11 1 1 6 1 0 0 44 0 1 1 1 0 1

12 0 0 1 1 1 1 45 1 1 1 0 1 0

13 0 1 1 1 1 0 46 0 1 0 0 1 1

14 1 1 1 1 0 0 47 1 0 0 1 1 0

15 0 1 1 1 1 1 48 1 0 1 0 1 1

16 1 1 1 1 1 0 49 1 1 0 0 0 1

17 0 1 1 0 1 1 50 0 0 0 1 0 1

18 1 1 0 1 1 0 51 0 0 1 0 1 0

19 0 0 1 0 1 1 52 0 1 0 1 0 0

20 0 1 0 1 1 0 53 1 0 1 0 0 0

21 1 0 1 1 0 0 54 1 1 0 1 1 1

22 1 1 1 1 1 1 55 0 0 1 0 0 1

23 0 1 1 0 0 1 56 0 1 0 0 1 0

24 1 1 0 0 1 0 57 1 0 0 1 0 0

25 0 0 0 0 1 1 58 1 0 1 1 1 1

26 0 0 0 1 1 0 59 1 1 1 0 0 1

27 0 0 1 1 0 0 60 0 1 0 1 0 1

28 0 1 1 0 0 0 61 1 0 1 0 1 0

29 1 1 0 0 0 0 62 1 1 0 0 1 1

30 0 0 0 1 1 11

1-3
a 

Logarithms of field elements to the base a are provided by Table 1-1 to

simplify multiplication of nonzero elements as follows:

049 (1 1 0 0 0 1)

034 (010111)

a34 049 - 0 20 (0 1 0 1 1 0)

The (multiplicative) order of a nonzero element a in GF ( 2 r

)is the

least integer m for which a m - 1. Furthermore, m divides 2 r -• 1, the

order of the multiplicative group , , in accordance with a corollary of a

fundamental theorem due to Lagrange ( see Reference 1).

As presented in Reference 2, consider the operation Q which squares each

of the roots of

r

g(x) - FIX —ail

i- 1

any polynomial of degree r over GF(2). Noting that

-1 - 1 mod 2 and (a + b) 2 = a2 + b2 over GF(2),

then

r r

Ig(x)l - ^(x -(1 2) - FI(t2

i= 1 i=1

r r

2

t - a i) 2 ^(t -ad

i-1 i=1

(g(t)1 2 - g(t 2 ) = g(x)

1-4
W1

The substitution t 2 . x is appropriately employed in proving that g(x) over

GF(2) is invari .nt under the operation Q. The soot-squaring operation Q on

X(x) which leaves g(x) unchanged is termed an automorphism. If in particular

.

S(x) of degree r is irreducible, then g(x) has the following r distinct

automorphisms:

1, Cr, (r2 , ... , Qr-1

with respect to GF ( 2 r ). An operation on a root of g(x) is an automorphism

if and only if it is an integer power of Q, the root-squaring operation.

Consequently, g(x) has r distinct roots, namely,

2 ' a2 2 2r-1

Q,Q , ... ,Q

r r r

Since Qr maps C into Q2 and 

Q2

C1 (from Q

2 -1 • 1), 

_r 

is the identity

operation.

The product of all irreducible polynomials over GF(2) whose degrees

r

divide r is x x2 - x. Complete factorization is best illustrated by

arranging the 2 r - 1 roots of unity into cyclotomic cosets ( see References 2

and 3). Given a primitive polynomial Ox) of degre e, r over GF ( 2). Each

distinct rocs is of order 2 r - 1, hence, a primitive root of unity.

A fundamental property associated with'the multiplicative order of field

elements is as follows:

if 0 has order m, then

j9 3 has order m/(m,j)

where (m,j) denotes the greatest common divisor of m and j. Clearly m and

m/(m,j) divide 2 r - 1, the number of nonzero elements in GF ( 2 r). The

integer ( m,j) is called the index of the order of^Q 3 . A primitive rth

1-5
degree polynomial has a, a primitive root of unity, as a root. Each of the r

roots has order 2 r - 1 since (2 r - 1, 2 1 ) - 1 for all i.

The set of integers

jil - {1, 2, 4, ... , 2r-11

taken from the multiplicative group of integers modulo 2 r - 1 form a

subgroup. The corresponding set

r-1 )

lal^ - {a, a2 , a2 , ... , a2

contains the r distinct roots of f(x). The "generalized cosets"

I

iv I - {v, 2v, 4v, ... , ( 2 r - 1)v}

are nonoverlapping sets which together with the subgroup Ii}, the special

coset where v - 1, comprise the multiplicative group modulo 2 r - 1. if

(2 r - 1, v) = 1, then jiv^ is a coset as defined in group theory. The

elements of such a coset correspond to r (2 r - 1)st primitive roots of unity

whose minimal EolXnomial is a primitive polynomial over GF ( 2) (see

Reference 4). There are W ( 2 r - 1)/r such cosets ( including the subgroup)

and, therefore, W(2 r - 1) / r primitive polynomials of degree r over GF(2).

The number- theoretic function W(m), known as the Euler phi-function, is the

number of positive integers no greater than m ( a positive integer) that are

relatively prime to m (see Appendix A). The integers a and m are termed

relatively prime if (a, m) - 1.

An "improper coset" results for values of v where ( 2 r - 1, v) # 1. If

such a coset contains r distinct elements, the elements correspond to

r (2 r - 1 ) st nonprimitive roots of unity whose minimal polynomial is an

irreducible nonprimitive rth degree polynomial over GF(2). Whereas the

elements of a coset containing s < r distinct elements ( where s necessarily

divides r) correspond to s (2 s - 1)st roots of unity whose minimal

polynomial is an irreducible polynomial of degree s over GF(2).

1-6
1-7

The product of the minimal polynomials associated with each of the

cyclotomie cosets (i.e., generalized cosets which include improper cosets)

r

yields x2 -1 - 1. The set of minimal polynomials is comprised of all

irreducible polynomials over GF(2) whose degrees divide r.

Example 2

6

The irreducible factors of x2 -1 - 1 over GF(2) are given in Table 1-2.

The 63 roots of unity are generated by a, a root of

F(x) = x6

+x5 +x2

+x+ 1

Consider the conjugate roots (i.e., roots of the same minimal polynomial)

a 3 , a6 , ... ,

a33

corresponding to the cyclotomic coset

{1 . 3, 2 . 3, ... , 2 5. 31 mod 63 = ^3, 6, , 331

The minimal polynomial for these roots is determined as follows:

f(a3 ) _ (a3 ) 6 + d5(a3 ) 5 + d4(a3)4 + d3 (a3 ) 3 + d2 (a 3 ) 2+ d l (a3 ) + 1 = 0

= a 18 +d5a 1S +d4a12 +d3a9

+d2 a 6

+d1a3 + 1 =0

Substituting entries in Table 1 - 1 corresponding to the foregoing powers of a

gives

==1
Table 1-2. Irreducible Factors of x2 6_ 1 - 1 Over GF(2)

Order of

Cyclotomic Coset Minimal Polynomial f(x) Degree Index Roots of f(x)

0 x+ 1 1 63 1

1 2 4 8 16 32 x6

+x5 +x2

+x+1 6 1 63

3 6 12 24 48 33 x6

+x5 +x +x2

+1 6 3 21

5 10 20 40 17 34 x6

+x5

+x3 +x2 + 1 6 1 63

7 14 28 56 49 35 x6 + x3 + 1 6 7 9

3

9 18 36 x + x + 1 3 9 7

11 22 44 25 50 37 x6 + x5 + 1 6 1 63

6

13 26 52 41 19 38 x + x + 1 6 1 63

15 30 60 57 51 39 x6 +x4 +x2 +x+1 6 3 21

2142 x +x+1 2 21 3

23 46 29 58 53 43 x6 +x4 + x3 +x+ 1 6 1 63

27 54 45 x3 +x2+1 3 9 7

31 62 61 59 55 47 x6 +x5 +x4 +x+1 6 1 63

1-8
L

[ 1 1 0 1 1 0)

+ d5 [ 0 1 1 1 1 1]

+ d4 ( 0 0 1 1 1 1)

+ d3 ( 0 0 1 1 0 1]

+ d2 [ 1 0 0 1 1 1]

+ d 1

( 0 0 1 0 0 0]

+ [ 0 0 0 0 0 1]

[ 0 0 0 0 0 0]

The scalar multipliers, d l through d5 , are elements in GF ( 2). They

represent unknowns in determining the linearly independent set of polynomials

(i.e., field elements). In this example,

d5 = d4 = d2 = 1 and d3 = d l = 0

The minimal polynomial containing at3 as a root (as well as a6, ... a33)

is

x6+x5+x4+x2+ 1

The order of a! 3 (and its conjugates) is 21. Thus, at3 is a generator of 21

of the 63 roots of x63 - 1 - 0 and is a nonprimitive root of unity. The

minimal polynomial is, therefore, an irreducible nonprimitive polynomial of

degree 6.

a

The 21 elements generated by 9+-. a3 are tabulated in Table 1 - 3 where

06 = Q 5 + 04 + Q2 + l

A one-to-one correspondence exists between lei and ac 3i (see Table 1-1).

Furthermore,

Ai Qj = p( i+j)mod 21 ^,3 ( i+j)mod 63 = a3ia3j
Table 1-3. Elements Generated by 0, a Root of f(x) - x 6 + x 5 + x4 + x 2 + 1

i of ^1 c5 c4 c3 c2 c c0

0 0 0 0 0 0 1

1 0 0 0 0 1 0

2 0 0 0 1 0 0

3 0 0 1 0 0 0

4 0 1 0 0 0 0

5 1 0 0 0 0 0

6 1 1 0 1 0 1

7 0 1 1 1 1 1

8 1 1 1 1 1 0

9 0 0 1 0 0 1

10 0 1 0 0 1 0

11 1 0 0 1 0 0

12 1 1 1 1 0 1

13 0 0 1 1 1 1

14 0 1 1 1 1 0

15 1 1 1 1 0 0

16 0 0 1 1 0 1

17 0 1 1 0 1 0

18 1 1 0 1 0 0

19 0 1 1 1 0 1

20 1 1 1 0 1 0

and the two sets 104 and la 34 are isomorphic groups under the defined

operation of "multiplication." However, the 21 elements generated by

3

P—^ with 0 adjoined do not form a group under the defined operation of

addition. Clearly

.86 + 85 +p4 + p2 + 1 -Q21 - 1 - 0

and

x6+x5+x4+x2 + I divides x2l - 1

1-10
A fundamental theorem states that x - 1 divides x - 1 over any

field if and only if d divides n. Thus,

x21 - 1 divides x63 - 1

is another way of stating that the 21 roots of unity generated by 94--q

are among the 63 roots of unity in GF(26).

The roots of

x2r-1 - 1- 0

are the nonzero elements in GF ( 2 r ). If s divides r, 2 s - 1 divides

2 r - 1 and

s r

x2 -1 - 1 divides x2 -1 - 1

and the roots of

x28-1 - 1- 0

are the nonzero elements of the subfields GF(2 s ) in GF(2r).

In Example 2, GF(2 6 ) contains the subfields GF(2 2 ) and GF(23).

GF(2) is a subfield of GF ( 2 2 ) and GF(2 3 ) as well as of GF ( 2 6 ). Although

the 21 roots of unity with 0 adjoined do not form a finite field (i.e., 21 is

not of the form 2 s - 1), they contain GF(2), GF ( 2 2 ), and GF(23).

Example 3

The irreducible factors of x 21 - 1 are given in Table 1 -4. The set of

integers

fil _ ^1, 2, 4, 8, 16, 111

1-11

1
Table 1-4. Irreducible Factors of x 21 - 1 Over GF(2)

Cyclotomic Minimal Order of

Coset Polynomial f(x) Degree Index Roots of f(x)

0 x+ 1 1 21 1

1 2 4 8 16 11 x6+x5 +x4+x2+1 6 1 21

3

3 612 x + x + 1 3 3 7

5 10 20 19 17 13 x6+x4 +x2+x+1 6 1 21

7 14 F2 +x+ 1 2 7 3

9 18 15 x3+x2 +1 3 3 7

taken from the multiplicative group of integers modulo 21 form a subgroup.

The corresponding set

foil = fo,02 , R4 ' 08 - 016 ' Rill

are the six distinct roots of

f(x) =x6

+x5

+X4 +x2 + 1

The index of each of the 21 roots of unity fpjl 

is relative to 21, the order

of R—a3 (i.e., the generator in Table 1-3). Whereas the index of

corresponding elements in Ict 3j 

I (a subset of the 63 roots of unity) is

relative to 63, the order of a (i.e., the generator in Table 1-2).

The number of irreducible polynomials over GF(2) of degree 6 whose roots

have order 21 is

v(21)/6 v(3)tp(7)16 = 2

That is, the order of 12 of the 21 roots of unity are relatively prime to 21

(and, thus, have an index of 1). These elements correspond to two complete

1-12
-1

cyclotomic cosets with six members each. Each set of elements are roots of a

_ ! minimal, hence irreducible, polynomial of degree 6.

- In general, if 0 has order d < 2 r - 1 and d divides 2 k - 1 for

.. k - r, but does not divide 2 k - 1 for k < r, then Q is a root of a

nonprimitive irreducible polynomial over GF(2) of degree r.

s

Consider the two polynomials of degree r over GF(2): F

d

-.

f(x) - xr + br-lxr-1 + ... + br-ixr-1 + ... + b l x + 1

j g(x) s xr + b

1

x

r-1 + ... + b i x

r-i 

+ ... + b

i r-l x + 1

The coefficient string of one is the reverse of the other.

r r

f(x) _ E b ix i

g(x) _ E br-ixi

1-0 1-0

where b0 and br are necessarily equal to 1 and

f(0) = g(0) = 1

Thus, x - a - 0 is not a root of f(x) or g(x).

An equivalent expression for g(x) is

t

g(x) - xrf(1/x)

The polynomial g(x) is defined to be the reciprocal polynomial of f(x) and

vice versa. If a is a root of f(x), then a 1 (the multiplicative inverse

of a ) is a root of g(x).

g(D 1 ) - a r f(a) - 0

t 1-13
preserves the order of the roots as well as the degree. If a has order n,

then Q 1 = an-1 has order

n/(n - 1, n) - n

A polynomial f(x) of degree r over GF(2) where

f(x) = xrf(1/x)

is defined to be self-reciprocal.

Example 4

There are a total of nine irreducible polynomials of degree 6 over GF(2)

(see Table 1-2).

Six of the nine are primitive and comprised of three reciprocal pairs.

One such pair of polynomials and their corresponding roots are

x6 + x5 + x3 + x

2 + 1 a5 a10 a20 40 17 34

,a ,a ,a

6 + x4 + x 3 + x + 1 23 46 29 58 53 43 X n , a , a ,at ,a ,a

The multiplicative inverse of each root in one set is contained in the other,

e.g.,

(a5) -1 . 5 . a63-5 = a58

The two nonprimitive polynomials whose roots have order 21 are

reciprocal polynomials.

1-14
The nonprimitive polynomial whose roots have order 9, namely,

x6 +x3 + 1

is a self-reciprocal polynomial as implied by its corresponding cyclotomic

coset. (If a is a root, so is CC 1.)

{7, 14, 28, 56, 49, 35) - {7, 14, 28, -7, -14, -281

0

Reducible self-reciprocal polynomials contain as factors irrea•icible

self-reciprocal polynomial(s) and/or irreducible reciprocal pairs of

polynomials. The factors of x53 - 1, in particular, and x - 1, in

general, are examples. Irreducible self -reciprocal polynomials are of even

degree ( r - 2m) with one exception (i.e., x + 1). Their coefficient strings

are of the following form:

1 b b2 ... bM-l l bM_1 ..* b2 b 1 1

The coefficients of x 2m , x and x0 are 1 and each b US i < m) is 0 i

or 1 (an element of GF ( 2)). Such a coefficient string is of odd weight (i.e.,

contains an odd number of one's). Thus, the corresponding f(x) cannot contain

x + 1 as a factor. Being of even degree and having the foregoing coefficient

string are necessary, but not sufficient conditions for f ( x) to be an

irreducible self-reciprocal polynomial.

Assume the cyclotomic coset

(1, 2, ... , 2 1 , 2m , 2m+1 , ...

22m-1)

corresponds to the roots of a primitive polynomial of degree 2m. To be

self-reciprocal, the following congruence relationship must hold:

2m a -1 mod 22m - 1

1-15

---

`^ 
Applying rules of modulo arithmetic yields

(2m + 1) u 0 mod 2 2m - 1

(22 + 1)/(2 2m - 1) - q where q is an

integer

and

(2m + 1)/(2 2m - 1) - 1/(2 m - 1)

Thus, 22m - 1 divides 2 m + 1 only if m - 1. It follows that x ` + x + 1

is a self-reciprocal primitive polynomial with roots a and a2 -

d-1 of

order 3. The only other self-reciprocal primitive polynomial over GF(2) is

x + 1 whose root is a0 - (a0 )

-1 

- 1 of order 1.

Irreducible nonprimitive self-reciprocal polynomials over GF(2) exist

for every even degree greater than 2. Given a of order 2 2m - 1 in

GF(2 2m). The cyclotomic coset

fv, 2v, ... , 2m-1v, -v, -2v, ... , -2M-1v}

corresponds to the set of 2m distinct roots (which contain a v ) of an

irreducible self-reciprocal polynomial of degree 2m.

2 m v a -v mod 22m - 1

(2m + 1)v a 0 mod 22m - 1

• w 0 mod (2 2m - 1)/(2m + 1, 22m - 1)

•is0mod 2m - 1

1-16

sf; - ,, 
The 21" + 1 solutions are

v - s(2m - 1) where 0 S s < 2 m + 1

and 

av for each v satisfies

X2m+l - 1 0

The root Qv where v n 2m - 1 has order

(2 2m - 1)/(2m - 1, 2 2m - 1) - 2 m + 1

and is a multiplicative generator of the (2 m + 1)st roots of unity. Of

these, V(2m + 1) have order 2m + 1, and for mX , each is a root of one of

the 0(2m + 0/2m irreducible nonprimitive self-reciprocal polynomials. The

order of each of the remaining roots divides 2 m + 1 and is less than

2m + 1. Those corresponding to a complete coset (i.e., having 2m elements)

are roots of a degree 2m irreducible nonprimitive self-reciprocal polynomial.

Those corresponding to cosets containing fewer than 2m elements are roots of

an irreducible self-reciprocal polynomial whose degree divides 2m and is less

than 2m. Thus, every factor of

x - 1 where n - 2m + 1

is an irreducible self-reciprocal polynomial over GF(2).

Example S

Given m - 3 and 2 m - 1 = 7. The element 0!7 is a generator of the

-oots of

xn - 1 a 0 where n = 2 m + 1 -9

1-17
A 

contained in GF(2 6 ). Each of the roots is a root of an irreducible

self-reciprocal polynomial whose degree divides 2m 6. The 9 roots

represented as v of a are

{0, 7, 14, 21, 28, 35, 42, 4i, 561

Following are the minimal polynomials corresponding to each cyclotomic coast:

[DE

Cyclotomic Coast Minimal Polynomial

0 x + 1

7 14 28 56( -7) 49(-14) 35(-28) x6 + x3 + 1

21 42(-21) x2 + x + 1

For m - 9 and 2 m - 1 - 511, the element a511 is a generator of the

roots of x513 - 1 - 0 contained in GF(2 18 ). Included among these roots

are the 9 which satisfy

x9 - 1- (x+ 1)(x2 +x+ 1)(x6 +x3 + 1) -0

each of which is member of GF(2 18 ) and one, and only one, of the subfields

GF(2), GF(2 2 ), or GF(26). 

An enumeration of all the factors (i.e., irreducible self-reciprocal

polynomials) of x513 _ 1 by order of their roots and their degree is as

follows: Let t$ . a511 in GF(2 18 ). The order of 0 is

n - 513/0,513) where d - 0, 1, ... , 512

Those values of d that divide 513 - 3 3. 19 belong to distinct cyclotomic

cosets and may be chosen as representatives (refer to Table 1-5). The last

three entries correspond to factors whose roots are also members of a proper

subfield of GF(2 18 ) (as shown in the first portion of this example).

1-18
Table 1-5. Irreducible Self-Reciprocal Factors of X513 - 1 Over GF(2)

Enumerated by the Order of their Roots and their Degree

Order of ,9d in GF(2 18 ) Number of Elements r

d n - 513/(d, 513) in Cyclotomic Coset (v(n)/r

1 513 18 18

3 171 18 6

9 57 18 2

19 27 18 1

27 19 18 1

57 9 6 1

171 3 2 1

513 = 0 mod 513 1 1 1

(P(n)/r denotes the number of irreducible self-reciprocal factors of

degree r whose roots have order n. The total number of elements with

order n (i.e., 0h where (h, 513) - d) is equal to V(n).

Finite fields of the same order are isomorphic, and every finite field

is isomorphic to a Galois field (Reference 5). Thus, the study of finite

fields of order pr (namely, GF(pr )) where p is a prime integer and r a

nonzero positive integer. Each element in GF(p r ) is a polynomial of

degree r with coefficients in GF(p) - i.e., 0, 1, ... , or p - 1. Only

polynomials in GF(2 r ) are discussed due to considerations associated with

practical applications.

Example 6

Given Y, a root of the degree 3 primitive polynomial x3 + x + 1.

Thus, Y has order 7 and is a (multiplicative) generator of the nonzero

elements in GF(23).

1-19

s z ' 1 a
Refer to Table4 1-1 and 1 -2. The degree 6 primitive polynomial,

x6 + x5 + x2 + x + 1, has a whose order is 63 as a root. Thus, a 9 has

order 7 and is a generator of the nonzero elements in the subfield GF(23)

properly contained in GF ( 2 6 ). The minimal polynomial containing a9 and

its conjugates [ ( a9 ) 2 and ( x9 ) 4 1 as roots is x3 + x + 1.

Refer to Tables 1-3 and 1 -4. The element $—a 3 is a root of the

degree 6 irreducible nonprimitive polynomial x 6 + x5 + x4 + x2 + 1.

The order of Q is 21. Whereas, Q6 has order 7 and is a generator of the

nonzero elements of GF ( 2 3 ), a proper subset of the 21 roots of unity.

Furthermore, the minimal polynomial containing (193)2 and its conjugates

[193 and (s3)4 

1 as roots is x3 + x + 1.

Consider the set of elements generated by Y, a 9 , and /36,

respectively, with 0 adjoined to each set.

i of j of k of

Y' a2a1a0 aj b5b4b3b2b1b0 19k c5c4c3c2c1c0

* 0 0

_

0

r

* 0 0 0 0 0 0 * 0 0 0 0 0 0

0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0

1

1 0 1 0 9 0 0 1 1 0 1 6 1 1 0 1 0 1

2 100 18 110110 12 111 101

3 011 27 001100 18 110 100

4 1 1 0 36 1 1 1 0 1 1 3 0 0 1 0 0 0

5 1 1 1 45 1 1 1 0 1 0 9 0 0 1 0 0 1

6 1 0 1 54 1 1 0 1 1 1 15 1 1 1 1 0 0

Each set of 8 elements is a different representation of the elements in

GF(2 3 ). The one-to-one correspondence between elements of each set is

Yi^•..ya9i^196i mod 21

1-20
Multiplication defined on the nonzero elements of each set is as follows:

(i+j) mod 7

7 3 

+ y + 1 0

aiaj = (i+j) mod 63

4 63_ 6 5 2

C1 I = a + a + a + C1 + I = 0

(al ) 7 _ i = (a 9 ) 3 + a 9 + I = 0

ai ai a(i+j) mod 21

2 1 ^I + '81 + 'el + '62 

+ 1 0

(p 6 7 

-1 3 ) 7 - 11 

2 

= 0

(p3 ) 7

1 0

(p 6 3 + 0 6 + o93 3 + e 

3 + 1] 2

0

3 3 3

W ) + )9 + 1 0

The foregoing illustrates that IB3 and (g3)2 are two of the three

conjugate roots of x 3 + x + I a divisor of x 7 _ 1.

0

1-21
2-1

l

1

i

A

SECTION II

GENERATORS OF PERIODIC BINARY SEQUENCES

i

A. FEEDBACK SHIFT REGISTERS

The Feedback Shift Register (FSR) in Figure 2-1 stores a representation

of the coefficients of the polynomial

b 5 a 5 + b4a4 + b 3 a 3 + b 2 a + b 2 a + bla + b0

Upon the application of the clock pulse (by clocking circuitry not shown), the

FSR performs multiplication by a, a root of

x6+x5 +x2+x+1=0

and reduces the result modulo

a6 +a 5 +a 2 +a+ 1

The content of each register stage is shifted one stage to the left. Overflow

resulting when b5 = 1 prior to shifting, represents

a6= a5 +a2 +a+ 1

which is "vector added" over GF(2) to the shifted contents. Equivalently,

a6 = a 5 + a 2 + a+ 1 mod a6 + a5 + a2 + a+ i

The contents of the FSR during two successive Clock Pulse Intervals (CPIs)

(i.e., before and after the applicable of a clock pulse) is illustrated in the

following example:
4 f

f

1

{

[FtF

a 5 a4

i

L4

F

F

Figure 2-1. Functional Logic Diagram of a Feedback Shift Register that

Performs Multiplication by a Modulo a+ a +a

2

 + a + 1

Example 7

b5^ b4, b3^ b2, bl,

b/, f b3 ) b2 ) b 1 f b0 f

b5 f 0 , 0 , b5 f b5

b 5 +b4 , b3, b2, b5+b ls b5+b0,

b0 at CPI j

0

b5

b5 at CPI j+1

In particular,

1 1 0 1 0 1 at CPI j

1 0 1 0 1 0

1 0 0 1 1 1

001101 at CPI j+1

0 1 1 0 1 1 at CPI j

1 1 0 1 1 0

0 0 0 0 0 0

1 1 0 1 1 0 at CPI j+ 1

0

The FSR in Figure 2-1 can assume 2 6 or 64 distinct states. The FSR as

configured splits the state space into two branchless cycles of states where

distinct states have distinct successor states. One cycle is comprised of 63

2-2
nonzero states. The succession of these states are identical to those

appearing in Table 1-1 where the length of the cycle (i.e., its period) is

equal to the order of a. The all zeros state a is its own successor

state. Thus, it is the single member of a cycle of length 1.

Given a primitive polynomial f(x) over GF(2) of degree r > 2. The

number of terms in f(x) is necessarily odd (i.e., 2m + 1 where m > 1). The

FSR circuitry that realizes multiplication by a modulo f(a) splits the state

space of 2 r binary r-tuples into two disjoint branchless cycles of states.

One cycle contains 2 r - 1 nonzero states identical in representation and

sequence of those nonzero elements in GF(2 r) generated by a. The other

cycle consists of the singleton all zeros state a*. The FSR circuitry is

comprised of r delay elements (or register stages) and 2m-1 two-input modulo

2 summers (i.e., Exclusive-OR gates). See References 4 and 6.

Of particular interest are the binary sequences appearing at the output

of each register stage. Given the sequence appearing at the output of one

stage, the output of each of the other stages is a cyclic permutation of that

sequence. The sequence is termed a Pseudonoise (PN) sequence because of its

noise-like properties (see Reference 3 and Section IV.A.)

Consider the primitive polynomial

f(x) = x6

+x5 +x2

 +x+ 1

where

f(a) = a 6 + a5 + a2 + a+ 1 = o

and

a-1 = a5 + a4 + a+ 1

2-3

r."
The FSR in Figure 2-2 performs division by a (i.e., multiplication by a-1)

and reduces the result modulo

a 

6 + a 5 + a 2 

+ a+ 1

The FSR stores a representation of the coefficients of the polynomial

b 5 a5 + b4a4 + ... + b0

Upon application of a clock pulse, the content of each register stage is

shifted one stage to the right. Overflow resulting when b 0 = 1 prior to

shifting represents

a-1 =a5 +a4 + a+ 1

which is vector added over GF(2) to the shifted contents. In terms of

congruences

a-1= a5+a4+a+ 1 mod a 

6 + a5 + a 2 + a +1

Note that

-1 -1 63 -1 62

a 1• a = a = a

Figure 2-2. Functional Logic Diagram of a Feedback Shift Register that

Performs Division by a Modulo a6 + a 5 + a 2 + a + 1

2-4 
2 -5

, 

- - - -- -

is the the last entry in Table 1-1. Successive nonzero states appearing in the

i

register of the FSR in Figure 2-2 are in reverse order of those in Table 1-1.

The binary sequence appearing at the output of a given stage of the FSR in

Figure 2-2, initialized with a nonzero state, is a PN sequence. It is the

reverse of the output of the corresponding stage of the FSR in Figure 2-1,

initialized with the same nonzero state.

The element Q = ac-1 is a root of

g(x) = x6 +x5 +x4 +x+ 1

where g(x) is the reciprocal polynomial of

f(x) =x6+x5+x2+x+ 1

Thus, an FSR configured to perform multiplication by

0 modulo 

Q6 +0 5 + Q4 +P+ 1

(when initialized with a nonzero state) generates a PN sequence (at the

output of each stage). This PN sequence is the reverse of the one generated

by the FSR in Figure 2-1. If the FSR is configured to shift from left to

right, the states appear in reverse order (of those associated with the FSR in

Figure 2-1).

In Example 3, the 6 distinct roots of

f(x) 

=x6+x5+x4 +x2+1

have order 21, and f(x) is irreducible, but nonprimitive. The 21 roots of

unity generated by P. a root of f(x), appear in Table 1-3.

E
Given an FSR configured to multiply the representation of

c 50, +c4 8 4 + ... + c0

by .band reduce the result modulo Q6 + Q 5 + 

0

4 +Q2 + 1. The all

zeros state Q* (representing the constant zero polynomial) is its own

successor state and lies on a cycle of length 1. Each of the 63 nonzero

states lies on one of three disjoint cycles (of states) of length 21 (see

Table 2-1). One cycle corresponds to the 21 elements in Table 1-3 generated

by 9, a root of

f(x) -x6

+x5

+x4 +x2 + 1

The 63 nonzero states correspond to 63 nonzero polynomials over GF(2) which

comprise a noncyclic group under polynomial multiplication reduced

modulo fOg). The remaining two cycles of 21 states correspond to cosets in

the group of order 63 relative to the subgroup generated by Q. The polynomial

y=p+ 1

was arbitrarily selected as one coset leader. Each polynomial in this coset

is representable as y/3i where 0 < j < 21. The polynomial

8 . p2 + 1

serves as the other coset leader in a similar manner. Each element in the

latter coset is representable as SQk where 0 < k < 21.

Every polynomial over GF(2) is uniquely expressible except for order as

the product of powers of irreducible polynomials over GF(2). Irreducible

polynomials over any finite are building blocks or atoms as are the primes in

the field of integers of infinite order.

e le2 en

f(x) - [fl(x)] [f2(x)] ... •[fn(x)]

2-6
9'_

Table 2-1. Equal Length FSR Cycles of (nonzero) States Corresponding

to the Decomposition of a Multiplicative Group into a

Cyclic Subgroup { ^Q and Cosets

^rR,^

and Is$ k)

i of X9 1 c 0

c 5

c 4

c 3c 2c 1c 0

j of YRJ c 5 c4c 3 c 2 c 1c0 k of 80k

c 5c 4c 3c 2 c 1

0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1

1 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 1 0

2 0 0 0 1 0 0 2 0 0 1 1 0 0 2 0 1 0 1 0 0

3 0 0 1 0 0 0 3 0 1 1 0 0 0 3 1 0 1 0 0 0

4 0 1 0 0 0 0 4 1 1 0 0 0 0 4 1 0 0 1 0 1

5 1 0 0 0 0 0 5 0 1 0 1 0 1 5 1 1 1 1 1 1

6 1 1 0 1 0 1 6 1 0 1 0 1 0 6 0 0 1 0 1 1

- 7 0 1 1 1 1 1 7 1 0 0 0 0 1 7 0 1 0 1 1 0

8 1 1 1 1 1 0 8 1 1 0 1 1 1 8 1 0 1 1 0 0

9 0 0 1 0 0 1 9 0 1 1 0 1 1 9 1 0 1 1 0 1

10 0 1 0 0 0 1 10 1 1 0 1 1 0 10 1 0 1 1 1 1

11 100100 11 011001 11 101011

12 111101 12 110010 12 100011

13 0 0 1 1 1 1 13 0 1 0 0 0 1 13 1 1 0 0 1 1

14 011110 14 100010 14 010011

15 1 1 1 1 0 0 15 1 1 0 0 0 1 15 1 0 0 1 1 0

16 0 0 1 1 0 1 16 0 1 0 1 1 1 16 1 1 1 0 0 1

17 011010 17 101110 17 000111

18 110100 18 101001 18 0011.10

19 0 1 1 1 0 1 19 1 0 0 1 1 1 19 0 1 1 1 0 0

20 1 1 1 0 1 0 20 1 1 1 0 1 1 20 1 1 1 0 0 0

2-7

} ± r. 
f

where f.(x) of finite degree is irreducible over GF(2) and the integers

L

e i > 0 (1 < i < n). FSR cycles of states associated with reducible

polynomials over GF(2) are investigated in the next section.

B. FEEDBACK SHIFT REGISTERS CHALACTERIZED BY RECURRENCE RELATIONS

fi

F

r The behavior of the r•-stage shift register with linear-logic feedback,

;r = as shown in Figure 2-3, is characterized by the linear recurrence relation

r

s

ak L^ c iak- i

i=1

f

See Reference 3.

Hereafter, FSRs g as shown in Figures 2-1 and 2-2) will be called shift

registers with interstage feedback or ISFSRs. Whereas, those shown in

Figure 2-3 will be referred to as shift registers with single stage feedback

or SSFSRs.

The summation in the linear recurrence relation is to be considered a

modulo 2 summation throughout. The content of the i th stage at CPI k is

denoted by a _ Shifting is implied by the subscripts. The content of the

th k 1 • th i stage at CPI k becomes the content of the (i + 1) stage at CPI k + 1.

That is,

ak-i , a(k+l)-(i+l)

1 < i < r

The c i.'s are Boolean constant multipliers. The i th stage contributes to the

feedback if c - 1. The r th stage is necessarily connected to the feedback

(switching) network (i.e., c - 1). Otherwise, the FSR is using a shift

register comprised of less than r stages. The initial state of the

2-8 
°k-1 °k-2 ak -r+l ck- r

i = 1 ' - '

Figure 2-3. Functional Logic Diagram of an r-stage Shift Register

with Linear Logic Feedback (SSFSR)

i th stage is denoted by 

a_ i

(i.e., ak-i at CPI k - 0). The bit being

fed back at CPI k is dencted by a and a becomes the content of the

1 st stage at CPI k + 1.

a k ---- w a(k+l)-1

Given

00 00 r

G(x) 

E 

akxk = ciak- i xk

k= 0 k-0 i=1

2-9
a generating function where th-. sequence of feedback bits are coefficients of

ascending powers of x. Then,

r oo

G(x) ' Fa C i x i Eak-ixk-i

i-1 k-0

and

r 00

G(x) - EC i x i s-ix 1 + a- _ +l x i+l + ... + a-1x 1 + E

a k. x k.

i-1 k-0

Thus,

rr

1 - cixi

G(x) - Ec ix i ax-i +

a-i+lx-i+1 + ... + a-1xi

and

G(x) - (x) f x

The numerator

r

g(x) - Ecixi

a-ix+ a-i+lx-i+l + ... + a-ix

-

is of degree less than r and its form is dependent upon the initial state of

the FSR (a-1, a-2 , ... , a-r) and the feedback connections (cl, c2 ... cr).

Whereas the denominator

2-10
r r

f(x) ! 1 - cixl 1 + cixl

i'1 :mil

(since -1 = 1 mod 2) is of degree r (i.e., c = 1) and its form is dependent

upon the feedback connections only. Clearly, g(x) and f(x) are polynomials

over GF(2).

The polynomial f(x) is called the characteristic polynomial of the

SSFSR. The behavior of the SSFSR can be described by the periodic sequence

I a . 1 corresponding to a given initial state. Overlapping r-uit subsequences

of Sak i as seen when is k } is bit serially passed through ar r-bit window,

correspond to the state sequence (i.e., cycle of states) assumed by the

register portion of the SSFSR.

The period of the longest sequence is governed by the properties of

f(x). Given the initial state of the SSFSR in Figure 2-3

a_ l

a_2

... a_r+l s 0, a_ r s 1

Then, g(x) ' 1 and

G(x) f(x) 1

2-11
2-12

Since the SSFSR can only assume a finite number of states before

repeating, the sequence

a v } s

{a0 , a l ... a.1-1}

must have a finite period 1 5 2 r . Thus,

C(x) - Tr-x7- a0 + a l x + "' + aft-lx-1

+ x J ( a0 + a l x + ... + afi-1xi-1)

• X21 (a0 + s i x + ... + aI -1X1-1)

• XMI 

( a0 • + a 1 

X + ... + of-1 .9-1)

a0 + a 1 X + ... +

s

1-x-1

and f(x) divided 1-x-0 for some least integer value .9, the periodicity of

;ak }. conversely, if f(x) divided 1-x-I for some least value of 1, then

f(x) characterizes an SSFSR that generates a periodic sequence of length l

When initialized by the state 0 0 ... , 0 1. Following Reference 3

1-xi

f(x) sYo+rlx+ ... +%-1
3

for some least integer value -Q. Then,

1 YO + y1 x + .. , + Y^-lx -1

f 1-x^

(1+x1 +x2_Q

+ ... +x

ms + ... ) (yo + y1 x+ ... +YU

00

G(x) s ^akxk

k=0

Equating coefficients of like powers of x gives JYkf = jakf

Example 8

Given the linear recurrence relation

a = a

k-2 + ak-3

and the initial conditions a -1 = a-2 = 0 and a -3 = 1. The linear

recurrence relation of order 3 (a discrete analog of a linear differential

equation of degree 3 with constant coefficients) with three boundary values

(i.e., initial conditions) provides sufficient information to compute

a0 , a 1 , ... . The same information can be extracted from f(x) = 1 + x

2 + x3

as follows:
1 2 + x + x 3 _ 1 + x 2 + x 3+ x 4+ x 7 (1 + x 2 +

1

1+x2 +x3

2 3

x + x

2 4 5

x + x + x

X3 +x4

+x5

x3 + x 5 + x6

x4 + x6

x4 + x6 + X7

x7 + ...

and

i ak I = 11, 0, 1, 1, 1, 0, 0}

The importance of f(x) is that its properties provide information about the

periodicity of ja k i without the necessity of determining the components of

l

ak 1. Note that f(x) divides 1 - x 2 and is a primitive polynomial over

GF(2) of degree 3. 

It will be shown that an r-stage SSFSR and an r-stage ISFSR having

identical cycle structures are transformationally equivalent. An isomorphism

exists between the states of one and the other.

The generating function of an SSFSR lends itself to readily determining

the cycle length for a given initial state, especially when f(x) is

reducible. Consider the generating function

G(x) = (x) h(x)s(x)

2-14
associated with an r-stage SSFSR whose initial state is nonzero. The

characteristic polynomial, f(x), is of degree r and has distinct irreducible

factors h(x) and s(x) whose degree exceeds 0. An initial state corresponding

to a g(x) that has no common factor (of degree greater than 0) with f(x) lies

on a cycle of longest length. That is,

(g(x), f(x)) = (g(x), (h(x)s(x))) = 1

denoting that the greatest common divisor polynomial is 1, the nonzero

constant polynomial. The initial state 0 0 ... 0 1 corresponding to

g(x) = 1 always lies on a cycle of longest length. By partial fraction

expansion

G(x) =

1 = u(x) + y(x)

h(x)s(x) h(x) s(x)

and

u(x)s(x) + v(x)h(x) = 1

Unique solutions exist for u(x) and v(x) in the congiuential forms

u(x)s(x) 1 mod h(x)

v(x)h(x) = 1 mod s(x)

from finite field theory (see Reference 4). Since u(x) is of degree lower

than that of h(x) (an irreducible polynomial),

(u(x), h(x)) = 1

Similarly,

((v(x), s(x)) = 1

2-15

j
The coefficients of ascending powers of x of the generating function

u(x) v(x)

G(x) = h(x) + s(x)

has two components. Its period is the Least Common Multiple (LCM) of the

periods of the two components. Thus, if h(x) divides 1 - .9 1 , and s(x)

divides 1 - 12 (for least integer values of-21 and-92, respectively), then

fW - h(x)s(x) divides 1 - x-a

for the least integer value

I= LCMUlI A2)

_ Example 9

r

4

Given a :;even-stage SSFSR with a characteristic polynomial

f(x) = 1 +x+x3+x4+x7

= (1 + x 2 + x 3 ) (1+x+x2+x3+x4)

Corresponding to the initialization of 0 0 0 0 0 0 1 is the generating function

G(x) = 1 =

1

f(x)

1+x+x3+x4+x7

1

(1+x2 +x3 ) (l+x+x2+x3+x4)

u(x) + v(x)

1+x2 +x3 1+x +x2 +x3+x4

2-16
2-17

u%xi %L-A- X+x3+x4)+v(x) (1+x 2 2 +x3 ) = 1

and

U(X) (x4 + x3 + x2 + x + 1) = 1 mod (x 3 + x2 + 1)

U(X) (x 2 + 1) - 1 mod (x3 + x 2 + 1)

Also,

V(X) (x 3 + x2 + 1) - 1 mod (x4 + x3 + x2 + x + 1)

The polynomial u(a) is an element in GF(2 3 ) whose multiplicative generator

is a, a root of

h(x) = x 3 + x2 + 1

a primitive polynomial. The multiplicative inverse modulo x 3 + x 2 + 1 of

(x 2 + 1)++(a2 + 1) is u(x)•-.u(a)

Since

a7 = 1 and a 2 + 1 = a3

u(a) = a

4 = a2 + a + 1

U(X) = 1+x +x2

and
2-18

The polynomial v(Q) is an element in GF(2 4 ). Multiplication of polynomials

in the field is reduced modulo

s(R) = 04 + 0

3 + 92 

+ Q + i)-(x4 + x3 + x2 + x + 1) = s(x)

Since s(x) is a nonprimitive irreducible polynomial, its root Q is not a

multiplicative generator (of the nonzero elements) in GF(2 4 ), i.e.,

Q 5 = 1. It may be shown that Q + 1 is one of (p(15) = 8 multiplicative

generators in GF(2 4 ) where Q is a root of

s(x) =x4

+x 3 +x2 +x+ 1

as follows:

i of (P + 1) 1 c3c2c1c0 i of 0 + 1) 1 c3c2c1c0

0 0 0 0 1 8 1 0 0 1

1 0 0 1 1 9 0 1 0 0

2 0101 10 1 100

3 1 1 1 1 11 1 0 1 1

4 1 1 1 0 12 0 0 1 0

5 1 1 0 1 13 0 1 1 0

6 1 0 0 0 14 1 0 1 0

7 0 1 1 1

The nonzero polynomials in GF(2 4 ) are expressible as

c 30' + c 2^2 + c l/31 + c0 = (Q+ 1) 1 mod Q4

+Q3 +Q2 +Q+ 1

The multiplicative inverse modulo x4 + x3 + x2 + x + 1 of

(x3 + x2 + 1).-.p 3 +02 + 1 is v(x)+—v(o)
Since

(p+ 1) 1S = 1 and Q3 + a2 + 1 = (0+ 1)5

V(P) _ (P + 1)

10 = ^3 + Q2

k

and v(x) = x

2 + x3

A version of Euclid's method which is recursive and detailed in Reference 4 is

recommended for determining multiplicative inverses in finite fields of higher

order.

The partial fraction expansion is, thus, complete and

G(x) _ (x) = 1

f(x) 1+x+x3+x4+Y7

i

1 + x + x 2

x 2 + x 3

1+x2 +x3 1+x+x2+x3+x4

_ u(x) 

+ 

v(x)

h x s(x)

The seven-stage SSFSR may be viewed as being decomposed into a three-stage and

a four-stage SSFSR. Its state behavior can be determined from the linear

recurrence relation

a = a

k-1 + ak-3 + ak-4 + ak-7

with the initial conditions

a-1=a_2= ... a_6=0, a_7=1

2-19
corresponding to g(x) = 1. Successive states a

k-1 a k-2 "• a k-7 and a

are tabulated in Table 2-2 for the cycle of states containing the initial state

0 0 ... 0 1. Its generating function is

G(x) = 1

1 +x+x3+x4+x7

The state behavior of the 3-stage SSFSR is described by

bk = b

k-2 + bk-3

Its generating function, the first term of partial fraction expansion of G(x),

is

U(X) _ 1 + x + x2

h(x) 1 + 

x2 + x3

F{{

P

j ! The initial state is determined as follows:

b-2 + b_Ix

+ b-3 + b-2 x + b-1x2

1 + x + x2 = u(x)

Thus,

b_1 = 1 1 + b_ 2 = 1 0 + b_ 3 = 1

b_ 2 = 0 b_3 = 1

Successive states b

k-1 bk-2 bk-3 and b appear in Table 2-2 for b_I

b_ 2 b_3 - 1 0 1. Since its characteristic polynomial h(x) is of degree 3

and primitive, the periodicity of lbk( is 2 3 - 1 or 7 and b

k-1 b7k-1

2-20 
Table 2-2. State Table of a 7-Stage SSFSR and Components of a Decomposition for

f(x) - 1+x+x3

+x4 +x7

 - (1+x2+x3)(1+x+x2+x3+x4)

k ak-lak-Zak-3ak-4ak-5ak-6ak-7 a bk-lbk-2bk-3 b dk- ldk-2dk-3dk-4 d bk+dk ak

0 0 0 0 0 0 0 1 1 1 0 1 1 1 0 1 0 0 1

1 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 1 0 1

2 1 1 0 0 0 0 0 1 1 1 1 0 0 0 1 0 1 1

3 1 1 1 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0

4 0 1 1 1 0 0 0 0 0 0 1 1 0 1 0 0 1 0

5 0 0 1 1 1 0 0 0 1 0 0 0 1 0 1 0 0 0

6 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1

7 1 0 0 0 1 1 1 0 1 0 1 1 0 0 1 0 1 0

8 0 1 0 0 0 1 1 1 1 1 0 1 1 0 0 1 0 1

9 1 0 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 1

10 1 1 0 1 0 0 0 0 0 1 1 0 1 0 1 0 0 0

11 0 1 1 0 1 0 0 1 0 0 1 1 0 1 0 1 0 1

12 1 0 1 1 0 1 0 1 0 0 0 0 0 1 0 0 1 1

13 1 1 0 1 1 0 1 1 0 1 0 1 1 0 0 1 0 1

14 1 1 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0

15 0 1 1 1 0 1 1 1 1 1 0 1 1 0 1 0 0 1

16 1 0 1 1 1 0 1 0 1 1 1 0 0 1 0 1 0 0

17 0 1 0 1 1 1 0 1 0 1 1 0 0 0 1 0 1 1

18 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 1 0 1

19 1 1 0 1 0 1 1 1 1 0 0 0 0 1 0 0 1 1

20 1 1 1 0 1 0 1 1 0 1 0 1 i 0 1 0 0 1

21 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1

22 1 1 1 1 1 0 1 0 1 1 0 1 0 0 1. 0 1 0

23 0 1 1 1 1 0 0 1 1 ? 0 1 0 0 1 0 0

24 0 0 1 1 1 ' 1 1 0 1 1 0 0 1 0 0 1 1

25 1 0 0 1 1 1 1 1 0 0 1 1 1 0 1 0 0 1

26 1 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 0 0

27 0 1 1 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0

28 0 0 1 1 0 0 1 1 1 0 1 1 1 0 0 1 0 1

29 1 0 0 1 1 0 0 0 1 1 0 1 0 1 0 0 1 0

30 0 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 0 0

31 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 0

32 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 0 1 0

33 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0

34 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0

0 0 0 0 0 0 0 1 1 1 0 1 1 1 0 1 0 0 0

i

2-21

-
The behavior of the 4-stage SSFSR is described by

d = dk-1 + dk-2 + dk-3 + dk-4

Its generating function, the second term of the partial fraction expansion of

G(x), is

v(x) =

x2 + x3

s(x) 1+x+x2 +x3+x4

The feedback connections and the initial state uniquely determines v(x).

d-1

+ d_2 + d_1x

+ d -3 + d_2 x + d-1x2

+ d_4 + d_3 x 

+ d-2x2 + d-1x3

= x2 + x3 = v(x)

and d-1 d_ 2 d_3 d_4 = 1 0 1 0. Successive states dk-ldk-2dk-3dk-4 

and d appear

in Table 2-2 with the foregoing initial state. The characteristic polynomial

s(x) is of degree 4. It is a nonprimitive irreducible polynomial whose roots

have order 5, a divisor of 2 4 - 1. Equivalently, s(x) divides 1 - x for

the least integer value ,Q of 5. The periodicity of Id k i is, thus, 5 and

d k-i d5k-i'

As shown in Table 2-2

I a k} _ lb k} + Id J

2-22
and Iakf has period 35, the LCM of 7 (the period of 1, bk 1) and 5 (the

period of Idk }). The LCM of two nonnegative integers a and b is

[a,b) a--b7a + b >0

Two meshed gears, one with seven teeth (corresponding to the period of lbkP

and one with five teeth corresponding to the period of Id k 1, represent a

mechanical analog of the decomposed SSFSRs. A scribe line, joining the

centers of the gears before drive is applied to one, corresponds to the

initial state. Upon the application of drive, the scribe line of the

respective gears rotate (in opposite directions). Both scribe lines will

simultaneously first return to their original positions after the number of

distinct pairs of teeth that have passed through the point of contact is

[7, 51 = 35. Equivalently,

f(x) =1+x+x3 +x4 +x7 divides 1 -x-9

for the least value of I equal to 35, and the period of Iak} is 35. The

order of the roots of h(x), s(x), and f(x) is, respectively

a

7= 1,/3 5= 1 and 83S=1

where h(at) = s(/3) = f(S) = 0

Given

n

f(x) _ rl fi(x)

1=1

2-23

N
where each factor f i (x) is an irreducible polynomial of degree r > 0 over

GF(2) and f i (x) f^(x) `or i J. An irreducible polynomial f i (x) is

said to "belong to exponent .1 if f i (x) divides 1 - x1i but does not

divide 1 - x for s < Q i . Also, is the order of a where

f.(a) - 0. i

The "period of f(x)" is

= [ l 1 1 i 2 1 . .. , .9n]

the LCM of the exponents to which the distinct irreducible factors belong.

Every irreducible polynomial over GF(2) of degree r < 16 can be

determined from Table C.2 in Appendix C of Reference 6. The table contains a

partial list of irreducible polynomials for 16 < r < 34 where factors of

r —

x 2 -I - 1 belonging to all possible exponents are given. The octal equivalent

of the binary 7oefficient string represents each polynomial. Associated with

each polynomial is an integer power (corresponding to an element of a

cyclotomic coset) of a, a root of the first entry, a primitive polynomial with

a minimum number of terms. Each polynomial listed is the minimal polynomial

of the roots corresponding to a cyclotomic coset represented by the element of

least value. See Table 1-2 of this report, but note that the primitive

polynomial whose root is a (corresponding to 1 in the coset 11, 2, 4, 81, 16, 321)

differs from the one given in Reference 6. In Reference 6, only one of a pair

of reciprocal polynomials is listed. The order of the roots of a listed

polynomial (i.e., the exponent to which the polynomial belongs) must be

computed as shown in Section I.

Every irreducible polynomial over GF(2) through degree 19 can be

determined from Reference 7. As in Reference 6, an octal representation is

used for each irreducible polynomial. The octal representations are arranged

lexicographically, and the period of each listed polynomial is given. Only

the lower-valued octal representation of a reciprocal pair of polynomials is

listed. The table enables one to readily determine whether a given polynomial

is irreducible.

2-24

1 
Reference 8 lists one primitive polynomial over GF(2) with the minimum

possible number of terms for every degree through 168. Another list where the

numbers of terms is not, in general, a minimum appears in Reference 9 for

every degree through 100.

A method of deriving every primitive polynomial of degree r from a given

r th degree primitive polynomial appears in Reference 10. Also presented is

an outline of an approach to the much more difficult problem of synthesizing a

it

primitive polynomial.

Example 9 is illustrative of the relationship between the period of f(x)

and the exponents to which its distinct irreducible factors belong. The

period of f(x) corresponds to the period of the longest cycle(s) of states.

By initializing the SSFSR with a state corresponding to a g(x) that has a

factor in common with f(x), a minor cycle is generated.

Example 10

Consider the 7-stage SSFSR in Example 9. An initial state corresponding

to

g(x) - s(x) - 1 + x + x 2 + x 3 + x4

results in

G(x) s(x)_ .. 1 —

h(x)s(x) 1 + x

2 + x3

and a sequence lakr whose period is length 7. From

a

a + a + a + a

k

k-1 k-3 k-4 k-7

2-25
a_ 1 a_2

a_ is determined as follows:

a_1

+ a-3 + a-2 x + a-1x2

= a-4 + a-3x + a

-2x2 + a-1x3

5

+ a-7 + a••6 x + a-5x + a-4x + a -3 x + a-2x + a_Ixb

r3 4

1 + x + x` + x + x

•° g(x)

a_ 1 = a_,) = a-6 = 0, a_,; = a_4 a a_5 = a_7 = 1

and the states ak-1 ak-2 ••• 9 ak-7 and {ak iversus k are

k

ak-1 ak-2 ak-3 ak-4 ak-5 ak -6 ak -7 a 

0 0 0 1 1 1 0 1 1

1 1 0 0 1 1 1 U 0

2 0 1 0 0 1 1 1 1 

3 1 0 1 0 0 1 1 1

4 1 1 0 1 0 0 1 1

5 1 1 1 0 1 0 0 0

6 0 1 1 0 1 0 1

0 0 0 1 1 1 0 1 1

It may be verified that the successive states under any 3 adjacent columns

correspond to those generated by a 3-stage SSFSB described by the linear

recurrence relationship

a ak-Z ak -3

2-k6
2-27

and appropriately initialized. In particular, a

k-1 ak-2 ak-3 where

a_ 1 a_2 a_3 = 0 0 1 mimics the 3-stage SSFSR whose generating function is

G(x) = 1

1 +x2+x3

Refer to Table 2-3. Each of the states in the foregoing length 7 cycle is

treated as an initial state and mapped onto its corresponding g(x). Each g(x)

is nonzero, of degree 6 or less, and contains

SW = 1+x+x2+x3+x4

as a factor. The remaining factor g(x) for each g(x) must be nonzero and of

degree 2 or less. There are a total of 7 such g(x)'s where

n 2

g(x) = c 2 x + c 1 x + c0

and at leest one of the three coefficients is nonzero. Each of the 7 states

in the length 7 cycle (when used as an initial state) yields

g(x)

C(x) = 2 3

where (g(x), 1 + x 2 + x 3 ) = 1

1 + x + x

It can then be concluded that the 7-stage SSFSR generates one, and only one,

cycle of length 7.

An initial state corresponding to

g(x) g(x)h(x) = g(x)(1 + x2 + x3)

results in

g(x)h(x) g(x)

G(x) = _

h(x)s(x) 1 + x + x 2 + x 3 + x4

W-
Table 2-3. Initial States of a 7-Stage SSFSR that Map onto a

g(x) Containing x 4 + x 3 + x 2 + x + 1 as a Factor

t

Initial State g(x)

6

E

t a-1 a -2 a -3 a -4 a-5 a-6 a-7

x 6 x5 x4 x 3 x 2 x 1 8(x) =

4

g(x)(x 3 + x 2 + x + x + 1)

[* 0 0 1 1 1 0 1 0 0 1 1 1 1 1 ( 1)(x4 +x3 +x2+x+ 1)

1 0 0 1 1 1 0 1 0 0 0 0 1 0 (x 2 +x )(x4 +x3 +x2+x+ 1)

0 1 0 0 1 1 1 0 1 0 0 0 0 1 ( x+ 1)(x4

+x 3 +x 2

+x+ 1)

1 0 1 0 0 1 1 1 0 1 1 1 0 1 (x 2 +x+ 1)(x4

+x 3 +x 2

+x+ 1)

1 1 0 1 0 0 1 1 1 0 0 0 1 1 ( x ` + 1)(x4 +x3 +x2+x +1)

1 i 1 0 1 0 0 1 1 1 1 1 0 0 ( x 2 )(x4 + x 3 + x 2 + x+ 1)

( 0 1 1 1 0 1 0 0 1 1 1 1 1 0 ( x )(x4 + x 3 + x 2 + x+ 1)

Characteristic Polynomial f(x) - (1 + x

2 + x 3 )(1 + x + X2 + x 3 + x4)

Since g(x) is of degree 6 or less, g(x) is of degree 3 or less and

E

t(g(x), x4

+x3 +x2

+x+ 1) = 1

There are 15 nonzero initial states corresponding to

s

t

g(x) = (c 3 x3 + c 2 x 2 + c 1 + c0 )( x3 + x2 + 1)

r

where at least one c.i is nonzero. A simplified approach to determining one

initial state is as follows:

k ak-1 ak-2 ak

-3 ak-4 ak-5 ak-6 a

k-7 a 

0 0 0 0 1- - - 1

1 1 0 0 0( 1 - - 1

2 1 1 0 0 0 1 - 0

3 0 1 1 0 0 0 1 0

2 -28 
Embedded in the left four stages is the state-behavior of a 4-stage SSFSR

whose generating function is

G(x) 1

1 + x + x 2 +x3+x4

Furthermore,

a = a

k-1 + ak-2 + ak-3 + ak-4

a ak-1 + ak--3 + ak-4 + ak-7

and

0 a

k-2 + ak-7

ak-7 ak-2

is sufficient information to fill in the dashed entries.

One cycle of length 7 and 3 cycles of length 5 accounts for 22 states.

Each of the states, when viewed as an initial state, maps onto a g(x) where

(g(x), f(x)) = x4 + x3 + x2 + x + 1 or x 3 + x2 + 1

The all zeros state maps onto g(x) = 0 and

(0, f(x)) = f(x)

corresponds to

0 _ 0 = ii G(x) f(x) 1 0 - ^akf

with periodicity 1. The remaining 105 (2 s - 23) distinct nonzero states

when viewed as initial states map onto 105 distinct g(x)'s. The greatest

2--29
i

F

common divisor of each g(x) and

f(x) = h(x)s(x) = 1 + x + x

3 + x4 + x7

is 1. Each of the 105 states is contained in one and only one cycle of length

35. The number of length 35 cycles is 7. The cycle structure of the SSFSR is

summarized as follows:

Length of Number of Number of

Cycle Cycle(s) States

1 1 1

5 3 15

7 1 7

35 7 105

Total 128

Given that

f(x) = [s(x)l

e

where the integer e > 1

The length of the longest cycle is the least integer value for which

[B(x)le divides 1 - x

i

The exponent to which s(x) belongs is .9 1 and

s(x) divides 1 - xil

2-30
and

x

X1)1l21 21121

Cl - 

= 1 - x over GF(2)

for integer values i > 0. The period of [s(x)] e is thus

211 1

1 - x

where 2 i-1 < e < 2i

Example 11

Given a 9-stage SSFSR characterized by

f(x) = [s(x)]e = (1 + x2 + x3)3

The period of the s(x) is 7.

Since

2 <3 <22

2

f(x) has period 2 - 7 = 28 and the length of the longest cycle that the

9-stage SSFSR can generate is 28. Every state that maps onto a g(x) such that

(g(x), [s(x)] 3 ) = 1

2 -31
is contained in a cycle of length 28. Every state that maps onto a g(x) such

that

(g(x), [s(x)] 3 ) = s(x)

is contained in a cycle of length 2 • 7 = 14. Every state that maps onto a

g(x) such that

(g(x), [s(x)] 3 ) _ [s(x)j2

is contained in a cycle of length 7. The all zeros state maps onto g(x) = 0

and

(0, [s(x)] 3 ) = [s(x)l3

Thus, the all zeros state comprises a cycle of length 1.

n

An SSFSR characterized by 

n

e .

f(x) 1 1 [f j (x)] 3 e. > 1

E

j=111

where f.(x) has period . j when initialized with the state 0 0 ... , 0 1

generates a cycle of longest length

fl = [ 2 11Q 1 , 2 12 1 2 , ... , 21n.n]

1 -1 1

where 2 3 < e <_ 2 3 and the length of every cycle divides J1, the length

of the longest cycle.

2-32
SECTION III

AN ISOMORPHISM BETWEEN THE STATES OF AN r-STAGE SSFSR AND AN r-STAGE ISFSR

The sequence iak( emanating from a 4-stage SSFSR satisfies the linear

recurrence relation

a = a

k-1 + ak-2 + ak-4 (1)

The characteristic polynomial of (1) is

f(x) = 0+x+x2 +x4) =(1+x)(1+x2 +x3)(2)

The cycles of states and the corresponding Isk i are tabulated in Table 3-1.

Each state in a cycle may be viewed as an initial state that maps onto a

g(x). The coefficients of g(x) are linear functions of a_ 1 , a_2, a-3

and a_4 as follows:

a-1

+ a-2 + a-lx

+ a -4 + a -2x + a-2x2

+ a-1x 3

g(x) = (a_ 1 + a_ 2 + a_4 ) + (a_ 1 + a_ 3)x + a_ 2x2 + a_ 1x 3

(3)

The coefficients of g(x) are evaluated for each of the 16 states (when viewed

as an initial state) on the right side of Table 3-1. It may be noted by

inspection that distinct states map onto distinct g(x)'s. Thus, a one-to-one

correspondence exists between the 16 possible (initial) states and the 16

distinct g(x)'s. The states comprise a vector space over GF(2) of dimension 4

(see References 1 and S). The linearly independent unit vectors form a

natural basis and map onto g(x)'s in accordance with (3).

3-1
Table 3-1. The One-to-One Correspondence Between the States of

an SSFSR and the g(x) Polynomials

g(x)

k

ak-1 ak-2 a k-3 ak-4

a

3

x

2

x x 1

0 0 0 0 0 0 x* 0 0 0 0

0 0 0 0 0 0 x* 0 0 0 0

0 0 0 0 1 1 1 0 0 0 1

1 1 0 0 0 1 x6 1 0 1 1

2 1 1 0 0 0 x 5 1 1 1 0

3 0 1 1 0 1 x4 0 1 1 1

4 1 0 1 1 0 x3 1 0 0 0

5 0 1 0 1 0 x2 0 1 0 0

6 0 0 1 0 0 x 0 0 1 0

0 0 0 0 1 1 1 0 0 0 1

0 1 1 1 0 0 Y 1 1 0 0

1 0 1 1 1 0 Yx6 0 1 1 0

2 0 0 1 1 1 Yx5 0 0 1 1

3 1 0 0 1 0 Yx4 1 0 1 0

4 0 1 0 0 1 Yx3 0 1 0 1

5 1 0 1 0 1

Yx2 1 0 0 1

6 1 1 0 1 1 Yx 1 1 1 1

0 1 1 1 0 0 Y 1 1 0 0

0 1 1 1 1 1 g 1 1 0 1

0 1 1 1 1 1 S 1 1 0 1

a 

= a

k-1 + a k-2 + ak-4

x- 1 = x6 = x3 + x + 1 mod f(x)

f(x) = x4 + x 2

+ x + 1 Y = x3 + x2 = x2 (x + 1)

= (x+ 1)(x 3 +x 2 + 1) S=x3 +x2+ 1

3-2
a

-1 3-2 a-3 a-4

x3 x2 x 1

[ 1 0 0 0 J am --+[1 0 1 1]

[ 0 0 1 0 j-[0 0 1 01

( 0 0 0 1 ]-[0 0 0 1]

The vectors representing coefficients of corresponding g(x)'s are also

linearly independent and span a vector space over GF(2) of dimension 4. Two

vector spaces of the same dimension and over the same field are isomorphic.

The mapping from an SSFSR state to its corresponding ISFSR state is realized

by the linear transformation matrix

1 0 1 1

Ts 0 1 0 1

(4)

0 0 1 0

0 0 0 1

An SSFSR state a

k-1' ak-2' ak-3' ak-4 1 which need not be an initial

state - i.e., k > 0, maps onto a ISFSR state as follows:

[1

1

k-1' ak-2' a k-3' ak-4J

]T _ [b3' b 2' bl' b0

where [b 3 , b 2 , b l , b 0] is the vector representation of

b 

3 

x 3 + b 

2 

x 2 + b 

1 

x + b0 = g(x)

Let u and u denote any two SSFSR states (not necessarily distinct). Then T in

(4) yields

(dlu + d 2u)T = d 1 (uT) + d2tuT)

3-3
where c l , c 2 E GF(2) are scalar multipliers. The inverse of T,

1 0 1 1

_l

0101

T =

0 0 1 0

0 0 0 1

is the linear transformation matrix that maps every given g(x) to its

corresponding SSFSR state. The vectors in T-1 in (5) (top to bottom),

respectively, represent SSFSR states corresponding to the natural basis

(1, 0, 0, 01, (0, 1, 0, 01, (0, 0, 1, 01, and (0, 0, 0, 11, representing x3,

x2 , x, and 1.

The cycles of g(x)'s mathematically describe the behavior of a 4-stage

ISFSR that performs division by a root of f(x) in (2). Let be a root of

f(x). Then,

f(a) - 0 1 + a + a 2 + a4

1 =a4+a2+a

a -1 = a 3 + a + 1

Note that a has order 7, and !X- 1 = a 6 has order 7. The elements a and x

are equivalent, i.e., they are the same elements in GF(2 4 ) with different

labels. Thus, x4---tea and

-1 =63 x+ 1modx4

+x2

x x =x + +x+ 1

The 4-stage ISFSR performs division by x and reduces the result modulo

x4 + x2 + x + 1 (see Figure 3-1).

(5)

3-4
vO

C'7

.Y vNYv t O

3-S

v+

CV1

OC v

N +

UV)

N 1

_x

C7

I Iv

oc

Ln

U-

!n

m

Z +

O x

N +

> N

X

UO 

x

Z O

O J ^ oOc

J {x

cc1

tN

+ x

X +

+ ch N ..Xi

X ^_

+ +

NtX

x

11 I I X

mdua

a, uuNuaMOOu3aw

CAH

00 uyI dVC

cd a

CnWNN

CI

60mu

cn6N1

c7

4!NO

00

•.1w I 
follows:

[ ak-1' ak-2' ak-3' ak-4] 1 0 1 1 [a k-1' ak-2' ak-1 + ak-3'

0 1 0 1

0 0 1 0

ak-1 + ak-2 + ak-4J (6)

000 1 a 

T

The next SSFSR state (i.e., at CPI k + 1) is

[a k' ak-1' ak-2' ak-3,

where

a ak-1 + ak-2 + ak-4

and

18 k ' ak-1' ak-2' a

k-3] T , ['k- a

k-1' a + ak-2' a + ak-1 + ak-3]

The right hand side of matrix equations (6) and (7) represent successive

transformed SSFSR states appearing in the ISFSR in Figure 3-1 at CPI k and

CPI k + 1, respectively. Given that the ISFSR stores

ak-1' ak-2' ak-1 + ak-3' a at CPI k

Applying a clock pulse to the ISFSR results in

0 ' ak-1' ak-2' ak-1 + ak-3

ak , 0, ak,

a (8)

ak' a k-1' a + ak-1' a + ak-1 + ak-3

3-6
The ISFSR state (8) at CPI k + 1 is identical to the transformed SSFSR state its

(7) at CPI k + 1. Thus, the succession of corresponding SSFSR and ISFSR

states is preserved under the isomorphism. The next state mappings for the

SSFSR and ISFSR are one-to-one onto and described by the following,

respective, nonsingular transformation matri,.es:

1 1 0 0 0 1 0 0

NSS 1010 NIS = 0010

0 0 0 1 0 0 0 1

1 0 0 0 1 0 1 1

The unit vectors comprising the natural basis in an SSFSR vector space

do not, in general, belong to the same cycle. However, one cycle in an ISFSR

vector space always contains the unit vectors in consecutive positions. The

mapping of the unit vectors (in the natural basis) representing SSFSR states

is related to f(x) in (2) as follows:

f(x) = x4 + c 3 x 3 + c 

2 x 2 + c 1 x + 1

where c 3 = 0 and c 2 = c 1 = 1

ak-lak-2ak-3ak x3 x 2 x 1

( 1 0 0 0 0 1

c3 c 2 C j

( 0 1 0 0 0 0 1 c 3 c 2

]

[ 0 0 1 0) - -- ( 0 0 1 c 3 j

( 0 0 0 1 j —( 0 0 0 1]

The transformation matrix T in (4) is comprised of the foregoing image

vectors. The unit vectors (in the natural basis) representing ISFSR states

namely, x 3 , x 2 , x, and 1 are in consecutive positions (of a cycle). Their

images may be determined directly.

x4 f(1/x) = 1 + x 2 + x 3 + x4

3-7
is the reciprocal polynomial of f(x) in (2). It is the characterZt is

polynomial of the linear recurrence relation

b s bk-2 + bk-3 + bk-4

that describes the state behavior of a 4-stage SSFSR with the same cycle

structure as the SSFSR in Figure 3-1. Corresponding cycles will contain the

same states where successive states of one is the reverse of the other for a

configuration of the former illustrated as follows.

k bk-4bk-3bk-2bk-1 %-l'k-2%-3 k-4

0 0 0 0 1 0 0 0 1

1 0 0 1 0 1 0 0 0

2 0 1 0 1 1 1 0 0

3 1 0 1 1 0 1 1 0

4 0 1 1 0 1 0 1 1

5 1 1 0 0 0 1 0 1

6 1 0 0 0 0 0 1 0

0 0 0 0 1 0 0 0 1

Shifting (right to left) as .till as labeling (b k-4

bk-3 bk-2 bk-1) is

the reverse of the SSFSR in Figure 3-1. Since

ak-lac-2 ak-3 ak-4 x3 x ` x 1

[ 0 0 0 1 ] .6 [ 0 0 0 1 J

the additional images of interest are those corresponding to the images of

three successive predecessors of x 0[ 0 0 0 1 ], namely x, x 2 , and x3.

3-8
These are the three successor states of b

k-4 bk-3 bk-2 bk-1

- [ 0 0 0 1 ] in reverse order. Thus,

ak-l ak-Z ak-3ak-4 x3 x 2 x 1

( 1 0 1 1 ] [ 1 0 0 0]

( 0 1 0 1 0 1 0 0]

[ 0 0 1 0 0 0 1 0]

The transformation matrix T -1 in (5) is comprised of the foregoing image

vectors. Note that T in (4) and T 1 in (5) are equal for f(x) in (2).

However T and T-1 are not necessarily equal for other f(x)'s.

The significance of the methods presented for determ4.ning T and T

that they are applicable to every f(x) over GF(2). It obviates the need for

generating the corresponding SSFSR and ISFSR cycles which is prohibitive

except for small values of r.

The binary sequences in the feedback of the SSFSR and the ISFSR in

Figure 3-1 are identical under the isomorphism. That is, a equals the

coefficient of x0 for every pair of isomorphic states in Table 3-1.

Self-reciprocal f(x)'s characterize FSRs that generate palindromic

sequences.

Recall that the generating function

G(x) = f ( X )

(9)

3-9

T
where

r

g(x) _ cixl[a-ix

-i + a-i+lx-i+l + ... + a-I x

-11

(9a)

1=1 J

r

c r = 1 and f(x) = 1 - cixl (9b)

i=1

characterizes the behavior of an r-stage SSFSR. As previously discussed,

each possible SSFSR state may be viewed as an initial state that maps onto a

g(x) that represents an isomorphic ISFSR state. If f(x) in (9b) is reducible,

an ISFSR state that is a member of a cycle whose length equals the period of a

particular irreducible or reducible factor may be determined directly.

Furthermore, the length of the cycle to which any given ISFSR state belongs

can be readily determined.

Example 12

The SSFSR in Figure 3-1 is characterized by

f(x) = (x + 1)(x3 + x2 + 1)

The nonzero ISFSR state belonging to a cycle of length 1 is represented

V by

g(x) = x3 + x2 + 1 or 1 1 0 1

Since

G(x) = x + )( + 1 _.- a 1

7

(x+ 1)(x3 +x` + 1) x+ 1

is associated with its isomorphic SSFSR state, it is contained on a cycle of

length I equal to the period of x i- 1.

3-10
3-11

CPI x3 x2 x 1

k 1 1 0 1

0 1 1 0

k+ 1 1 1 0 1

and ISFSR state 1 1 0 1 is its own successor.

Example 13

Given an SSFSR described by

f(x) =x10+x9+x7+x5+x+1

= (x + 1) 3 (x3 + x2 + 1)(x4 + x3 + 1)

The period of (x + 1) 3 is 4, x3 + x2 + 1 has period 7, and x4 + x3 +1

has period 15. Therefore, the period of f(x) is

(4, 7, 151 = 420

The ISFSR state 1 1 0 0 1 1 1 0 0 1 corresponding to

g(x) =x9+x8+x5+x4+x3+1

= (x+ 1)(x4 +x3 + 1)(x4

+x3 +x2

+x+ 1)

is contained in a cycle whose length is equal to the period of

f(x)/(g(x), f(x))

m
Since

(g(x), f(x)) = (x + 1)(x 4 + x 3 + 1)

the period of

i

f(x)/((x + 1)(x4 + x 3 + 1)) = (x + 1) 2 (x3 + x2 + 1)

k

is [2, 7) or 14. Note that 14 divides 420, the length of the longest

cycle(s). The cycle of 14 states is

i of rx l x9 x8 x7 x5 x5 x4 x 3 x 2 x 1

0 1 1 0 0 1 1 1 0 0 1

419 (-1) 1 0 1 1 0 0 1 1 0 1

418 1 0 0 0 1 1 0 1 1 1

417 1 0 0 1 0 0 1 0 1 0

416 0 1 0 0 1 0 0 1 0 1

415 1 1 1 1 0 0 0 0 1 1

414 1 0 1 0 1 1 0 0 0 0

413 0 1 0 1 0 1 1 0 0 0

412 0 0 1 0 1 0 1 1 0 0

411 0 0 0 1 0 1 0 1 1 0

410 0 0 0 0 1 0 1 0 1 1

409 1 1 0 1 0 0 0 1 0 0

408 0 1 1 0 1 0 0 0 1 0

407 (-13) 0 0 1 1 0 1 0 0 0 .1

0 1 1 0 0 1 1 1 0 0 1

where

x-1 = x419 _ x9 + x8 + x6 + x4 + 1 mod f 

Y= 

x9 + x8 + x 5 + x4 + x 3 + 1

3-12
The SSFSR state isomorphic to the ISFSR state y (i.e., 1 1 0 0 1 1 1 0 0 1) is

y T 1= 1 0 0 1 0 0 0 0 1 1

where

1 1 1 0 1 1 0 0 1 1

W. 0 1 1 1 0 1 1 0 0 1

0 0 1 1 1 0 1 1 0 0

0 0 0 1 1 1 0 1 1 0

T l = 1 0 0 0 0 1 1 1 0 1 1

0 0 0 0 0 1 1 1 0 1

0 0 0 0 0 0 1 1 1 0

0 0 0 0 0 0 0 1 1 1

0 0 0 0 0 0 0 0 1 1

0 0 0 0 0 0 0 0 0 1

An SSFSR state (vector v) is transformed to its isomorphic ISFSR state by vT

where

1 1 0 1 0 1 0 0 0 1

D 1 1 0 1 0 1 0 0 0

D 0 1 1 0 1 0 1 0 0

D 0 0 1 1 0 1 0 1 0

T = I D 0 0 0 1 1 0 1 0 1

D 0 0 0 0 1 1 0 1 0

D 0 0 0 0 0 1 1 0 1

D 0 0 0 0 0 0 1 1 0

D 0 0 0 0 0 0 0 1 1

D 0 0 0 0 0 0 0 0 1

The matrices T and T 1 are upper triangular matrices where the elements in

the principal diagonal are all 1's. A right shift of the components in each

t row of T and T-1 yield the respective next row of each.

a

t

3-13
Consider the cycle structure of the SSFSR in Table 3

1. There are a

pair of length 1 cycles and a pair of length 7 cycles. The states in one

cycle of each pair are the 1's complement of those in the other. From

a = a

k-1 + ak-2 + ak-4

state

ak-1' ak-2' 

s

k-3' ak-4

is succeeded by

ak' ak-1' ak-2' ak-3

Whereas, state a

k-l' ak-2' ak-3' ak' or

1 + 

a

k-.' 1 

+ ak-2' 1 + ak-3' 1 + ak

is succeeded by ak'ak-l'ak-2'ak-3

since

(1 + ak-1) + (1 + ak_ 2 ) + 0 + ak-4 ) - 1 + a = a 

and

{ak) 11 1 0 1 0 0 0}

{1+ak} 10010 111

are complementary feedback sequences associated, respectively, with the

length 7 complementary cycles of states (see Reference 3).

3-14
state(s) of one cycle of each pail are of odd weight (i.e., contain an odd

number of 1's), whereas the state(s) of the other cycles are of even weight.

The sequence of g(x)'s, namely, I1, x6 , x 5 , ... xI represent the cycle

of ISFSR states which are isomorphic to the cycle of SSFSR states

characterized by

G(x) = 1 =

1

f(x) (x + 1)(x3 + x2 + 1)

The elements {1, x6 , x 5 , ... , x form a cyclic group under

multiplication. However, they with x* adjoined do not form a group under

vector addition. The vector addition of two distinct vectors of odd weight

t

res in a nonzero

1

vector of even weight. Thus, closure is not satisfied and

1, x 6 ,x5 , ... , x} with x* adjoined do not form a field. This is not

surprising since f(x) associated with the cycle of nonzero isomorphic states

I

is reducible, hence nonprimitive. The sequence of g(x)'s, namely,

r, r x6 , yx 5 , ... , r xIwhere r equals x3 + x2 represent the cycle of

ISFSR states which are isomorphic to the cycle of SSFSR states characterized by

3 2 2

G(x) = x + x = x

(x+ 1)(x3 +x2 + 1) x3+x2+1

(

whose denominator x 3 + x 2 + 1 is primitive. The elements

i Y , rx6 , yx5 , )I' x5 , ... , rx I with x* adjoined form a field. The

``

multiplicative identity is x3 + x2 or Y. i.e., r 2 = y mod f(x)

(x 3 + x 2 ) 2 = x 6 + x 4 = x 3 + x 2 mod x4+x2+x+1

The multiplicative inverse of rx i is rx I j.

(rx j )(rx l-j ) = r2xI

=r mod x 4 + x 2 + x + 1

3-15
s

The element x 3 + x2 + 1 or 8 with x

 adjo

ed oa ed otwo eeets.

Given the linear recurrence relation

r

a = c 0 + Eciak-i

(10)

i=1

where ci = 0,1 for 0 5 i< r and c r = 1

00 0o r

G(x) =Eakxk =E c 0 +Eciak-i xk

k=0 k=0 i=1

00 r 00

_ EcOxk + Ecix i

Ea k-i x k-i

k=0 i=1 k=0

The first term expressed in closed form is

C0

1 - X

The second term can be expressed as

r

g(x) + ^c ix l G(x)

i=1

3-16

- r

i
where g(x) is given in °(a). It follows that

c0

1 - x + g(x) G(x)

f(x)

c 0 + 0 - x)g(x)

(1-x fx

where f(x) is given in 9(b).

Fur co = 0

G(x) = 

g(x)

f 

as given in (9).

For c0=1

1 + (1 - x)g(x) gl(x)

G(x) _ 

—(1 - x)f(x) f1 W

Since

9 1

 (1) = 1 + (1 - 140) - 1.

9 1 (x) does not contain x + 1 as a factor. Hence, g l (x) has an odd number of

terms.

Example 14

d = 1 + dk-2 + dk-3

3-17

(11)
and

f1(x) _ (x + 1)(x 3 + x2 + 1)

describe the behavior of the SSFSR in Figure 3-2. The polynomial g,(x) in

(11) versus d_ 1d_2d_ 3 is derived as follows:

d_ 2

+ d_1x

+ d_ 3

+ d_2x + d_lx2

g(x)

d_2 + d_ 3 + (d_ I + d_ 2)x + d'lx2

and

gl(x) _ (1 + d_ 2 + d_ 3) + ( d_ 1 + d_ 3)x + d_2x2 + d-1x3

The successive 3-component SSFSR state vectors map onto the gI(x)

polynomials as shown in Figure 3-2. The two cycles of g 1W's of odd weight

are respectively identical to the two cycles of g(x)'s of odd weight appearing

in Table 3-1. Complementation takes place in the feedback path of the SSFSR

and the ISFSR in Figure 3-2. A one-to-one correspondence exists between the

SSFSR states and ISFSR states. The linear transformation matrix

1 1 0

T = 0 1 1

0 0 1

maps dk_Idk_2dk_2 

into b 

2 

b 

I 

b 

0 

representing b 2y 2 + b ly + b0.

The inverse of T is

1 1 1

T 1 0 1 1

0 0 1

3-18
d k-1 d k-2 dk-3

d = 1 +d k-2 + dk-3

f (x) _

1 0 +x) 0 +x2 +x3)

91(x)

k dk-ldk-2dk-3 dk x3 x2 x 1 y2 y 1

c

0 0 0 0 1 1 0 0 0 1 0 0 0

1 1 0 0 1 x6 1 0 1 1 1 1 0

2 1 1 0 0 x5 1 1 1 0 1 0 1

3 0 1 1 1 x4 0 1 1 1 0 1 0

4 1 0 1 0 x3 1 0 0 0 1 1 1

5 0 0 0 x2 0 1 0 0 0 1 1

6 0 0 1 0 x 0 0 1 0 0 0 1

0 0 0 0 1 1 0 0 0 1 0 0 0

0 1 1 1 1 S 1 1 0 1 1 0 0

0 1 1 1 1 S 1 1 0 1 1 0 0

S=x3+x2 +1

Figure 3 -2. The One-to-One Correspondence Between

dk-ldk-2dk-3

and b2 y 2 + b l y + 1

i

3-19
described by

sk = K-2 + K-3

and

f(x) =1+x2+x3

and an ISFSR that performs division by x modulo x 3 + x 2 + 1, i.e., where

complementation does not appear in the feedback of the SSFSR or of the ISFSR.

The next state mappings for the SSFSR and the ISFSR in Figure 3 -2 are

one to one described by affine transformations, a transformation followed by a

translation (see Reference 1). Let u denote the present state of the SSFSR

and u' the next state. Then

u' = UN SS

+ LSS

where

0 1 U

NSS 1 0 1 and LSS [ 1 0 0 J

1 0 0

Let v denote the present stare of the ISFSR and v' the next state. Then,

v' = vN

IS + LIS

where

0 1 0

N IS = 0 0 1 and LIS = [ 1 1 0 J

1 1 0

3-20
Figure 3-2 are identical under the isomorphism. That is, d equals 1 + b0

(where b0 is the coefficient of y0 ) for every pair of isomorphic states.

Example 15

The behavior of a 4-stage SSFSR is characterized by

_

k + d k-1 + 

d

4-2 + dk-4

and

fl (x) - (1 + x)f(x) - (1 + x) (1 + x + x 2 + x4)

- (1 + x)[0 + x)(1 + x2 + x3)J

_ (1 + x) 2 (1 + x 2 + x3)

One 1 + x factor is due to complementation in the feedback, and the generating

func_ion is

91W1 + (1 - x) (x) G(x) - f1 x =

(1 - X f x

Since gl (x) cannot contain 1 - x (i.e., x + 1) as a f p,ctor, the SSFSR splits

the state space into two cycles. One is of length 14 and contains state

0000. The other '_$ of length 2. For

d_ 1 = d_ 2 s d_ 3

d_4 = 0

G(x)

0+x) 2 (1 +x2+x3)

3-21

r i • . _
.1=12,71 =14.

For g l (x) = x3 + x2 + 1

G(x) -

1

(x + 1)1

and the state that maps onto g l (x) = x3 + x 2 + 1 is 0101 (see Table 3-2).

g(x) _ (d_ 1 + d_2 + d_4 ) + (d_ 1 + d_ 3 )x + d_2x2 + d_lx3

and

g1 (x) 1 + (1 - x)&(x)

2 2 4

= s0 + s 1 + 8 2x + 8 3 x + 64x

where

s0 = 1 + d

-1 + d-2 + d-4

s l = d,

-2 + d-3 + d -4

s 2

d_ 1,

+

d-2 + d-3

s 3

d_1 + d-2

s4 = d-1

Since (01) is the only periodic sequence of length 2, it could be deduced that

0 1 0 1 and 1 it 1 0

3-22
Whose Respective Next State Transformations are Affine

9l(x)

k dk-1 d k-2 d k-3 dk-4 d x 4x 3x 2 x 1 Y

y r 1

0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0

1 1 0 0 0 0 x13 1 1 1 0 0 1 0 1 1

2 0 1 0 0 0 x12 0 1 1 1 0 0 1 0 1

3 0 0 1 0 1 x11 0 0 1 1 1 0 0 1 0

4 1 0 0 1 1 x10 1 1 1 1 1 1 0 1 0

5 1 1 0 0 1 x9 1 0 0 1 1 1 1 1 0

6 1 1 1 0 1 x8 1 0 1 0 1 1 1 0 0

7 1 1 1 1 0 x7 1 0 1 1 0 1 1 0 1

8 0 1 1 1 1 x6 0 1 0 1 1 0 1 1 0

9 1 0 1 1 1 x5 1 1 0 0 1 1 0 0 0

-- 10 1 1 0 1 0 x4 1 0 0 0 0 1 1 1 1

11 0 1 1 0 0 x'

a

0 1 0 0 0 0 1 1 1

12 0 0 1 1 0 x2 0 0 1 0 0 0 0 1 1

13 0 0 0 1 0 x 0 0 0 1 0 0 0 0 1

0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 C

0 0 1 0 1 1 8 0 1 1 0 1 0 1 0 0

1 1 0 1 0 0 8x 1 1 0 1 0 1 0 0 1 

0 0 1 0 1 1 8 0 1 1 0 1 0 1 0 0

d k = l+dk— l +d k—" Ik—,', 8= x3 +x2+ 1

f 1 (x) = (1 + x)((I + x)(1 + x2 + x3)l

_ (1 + x) 1 (1 + x1 + x3)

3-23
are the SSFSR states comprising the cycle of length 2. State 0 1 0 1 maps onto

g l (x) = x3 + x2 + 1 = S

whereas state 1 0 1 0 maps onto

g l (x) =x4 +x3+x =Sx

Refer to Figure 3 -2 and Table 3-1. The cycle structure (i.e., two cycles of

length 7 and two of length 1) is changed to that of Table 3 -2 by incorporating

complemention into the feedback paths of the SSFSR and corresponding ISFSR.

Note that

1 0 1 1

0 1 0 1

T-T-1 - 00 10

0 0 0 1

is the same for both sets of isomorphic SSFSR and ISFSR states. The next

state mappings, however, are linear and affine transformations, respectively.

An r-stage SSFSR capable of generating la k } that satisfies the

recurrence relation

r

a - Ecia k-i c = 0,1 for 1 < i < r, c = 1 (12)

i=1

has a characteristic polynomial

f = 1 + c l x + c x2 2 + ... + cr-lxr-1 + X 

(13)

The recurrence relation (12) and f(x) in (13) are implied in the following

theorem.

3-24
THEOREM 1

Distinct r-stage SSFSR states when viewed as initial states map onto

4 distinct polynomials g(x)'s of degree less than r.

Proof

Expanding (9a) gives

g(x) = cla-1

+ C2 

(a

-2

+ aX)

+ c r-1 (a-r+1 + a_ r+2 x + .., + a x r-3 + a xr-2)

-2 -1

+ a-r

+ a-r+lx + ... + 

a-3x r-3 + a-2x r-2 + a-lxr-1

The 2 r state vectors of the SSFSR form a vector space U over GF(2) of

dimension r that is spanned by the linearly independent r unit vectors. The

mappings of the unit vectors which are a natural basis of the r-dimensional

vector space follows from (14).

(14)

a -1 a -2 ... a -r+l a-r

[1 0 ... 0

-2 + ... + cI) 01 x + cl xr-1 + cr-lxr

(0 1 ... 0 01

xr-2 +

+ c3x + c2

[0 0 ... 1 01 x + cr-1

[0 0 ... 0 11 1

3-25

(15)
The r images (i.e., g(x)'s are linearly independent polynomials chat span a

vector space V over GF(2) of dimension r. Thus, each of the 2 r distinct

linear combinations maps onto a distinct polynomial g(x) of degree less than r.

Q.E.D.

Each coefficient in

'

-1 + br

br-lxr-lxr

-2 + ... + b0 = g(x)

i

is a distinct linear combination of a_ 1 , a _

21 ... , and a_r

r

COROLLARY 1.1

ti

The ]in^ar transformation

i

i

xrxr -1 -2 xr-3

... x 1

c r-1 cr-2 c2 cl

0 1 c.r-1 ... c 3 c2

T =

0 ... 1

cr-1 ro 0

 0 0 ... 0 1

is an isomorphism of U onto V.

(16)

Proof

The linear transformation matrix T is the one - to-one mapping in (16)

where

uT = v u E U and v E V
Since the r row vectors of T are linearly independent, T is nonsingular and

its inverse T-1 exits.

The inverse T -1 is a linear transformation. Given (state) vectors v

and v in V and scalar multipliers e l and e 2 in GF(2).

(e I v + e2v)T-1 T = (e 01+ (e2v)I

= [e l (vT-1 ) + e2(vT-1)]T

Postmultiplying both sides by T-1 yields

(e 1 v + e2v)T

-1

 = e I (vT-1 ) + e2tvT-1)

thus, T 1 is a linear transformation.

The one-to-one onto linear transformation

T : U --► V

is an isomorphism. Every set of linearly independent vectors u l , u 2 , ...

um in U where m < r is map . ad onto a linearly independent set of vectors vl,

v 29 ... , vm in V. When m = r, the vector space U is spanned and the vector

space V is spanned. For u l = [1, 0, ... 01 u 2 = [0, 1, ... 01, ... ,

u r = [0, 0 11, a natural basis for V, every vector uEU has a unique

expression

u = a-I u 1 + a-2 u 2 + ... + a 

r 

u 

r

(17)

which is a linear combination of the u i 's. Given that u is expressible as

u = h l u l + h 

2 

u 2 + ... + h 

r 

u 

r

3-27
3-28

Then,

u - u = 0 - (a-1 - h l )u l + (a_ 2 - h2 )u2 + ... + (a-4 - hr)ur

and since u l , u2 , ... , ur are linearly independent

t

a - h. 0 and h. = a for all i.

Thus, (17) is unique and uniqueness of representation holds for every given

basis.

The respective images of u l , u2 , ... , ur_ l , ur are the

polynomials in (15) where

xr

-1 + cr-lxr + ... + c 2 x + c 

is the image of u l = [1, 0, ... , 0, 01. The components of the image vector

vl [1 '

cr-1' ... , c 2 , cl]

are the ordered coefficients of the polynomial g(x) of degree r-1 excluding

c0 resulting from the mapping of

[a-1' a_ 2 , ... a_4 ) [1, 0, 0, 01

in accordance with (15). The vectors v l , v 2 , ... v are linearly

independent and form a basis in V. Postmultiplying both sides of (17) by the

transformation matrix T in (lb) gives

uT = (a_lul + a_ 2 u 2 + ... + a_rur)T

= a-1 (u 1 T) + a_2(u2T) + ... + a-r(urT)
r

3-29

v = a_ 1 v l + a_ 2 v2 + ... + a-rv2 (18)

and every vector veV is uniquely expressible relative to the basis v 1 , v2,

... , v

r'

The a_ i 's in (17) and (18) are scalars in the field GF(2). From

Reference 1, each basis u l , u2 , ..., u in a vector space U over a field

F provides an isomorphism of U onto space U r M. The isomorphism Cu is

the correspondence which assigns to each vector uEU the r-tuple of its

coordinates relative to u as follows:

(a_ 1 u 1 + a_ 2 u2 + ... + a_ rur )Cu = ( a-1 , a_ 2 , ... , a_r)EUr(F)

where F, in this case, is GF(2). Since the number of vectors r in a basis is

determined by the dimension r, which is invariant (as proved in References 1

and 5), every finite-dimensional vector space over a field F is isomorphic to

one, and only one, space Ur(F).

Q.E.D.

A more convenient basis in V is

[xr-1

 0 ... 0, O)

[0 xr-2

... 0, 01

10 0 ... x, 0)

[0 0 ... 0, 11

and every element in V may be expressed as

br-lxr-1 + b_2x r-2

+ ... + b 

1 x + b0 = g(x)
From (14),

br-1 

a 

a-1

r-2 

a c

r-l a-1 + a-2

b l

c2 a_ 1 + c 3 a_ 2 + ... + c r-l a-r+2 + a-r+l

a0 = b0 = c 1 a_ 1 + c 2 a_2 + ... + cr-2 a-r+2 + c r-l a-r+l + a_

r

(19)

Given an r-stage SSFSR capable of generating ia k } that satisfies the linear

recurrence relation in (12) and has the characteristic polynomial f(x) given

in (13). The state

[a- P a_

2 , ... , a_r+l , a_r ] = [0, 0, ... , 0, 1]

always has [1, 0, . . ., 0, O] as its successo: state (which may be viewed as

another initial state). The corresponding ISFSR states represented as

polynomials are

[0, 0, ... 0, 1] 0 1

[1, 0, ... , 0, 01 --- o x

r-1 

+ cr-lxr-2 + ... + c 

2 

x + cl

Note that

1-x-1 = x-1 = (x r-1 + cr-lxr-2 + ... + c 

2 x + c l ) mod f(x)

and 1 divided by x reduced modulo f(x) in (13) is the polynomial representing

the ISFSR successor to 1 (the nonzero constant polynomial).

3-3G
THEOREM 2

Successor states of isomorphic SSFSR and ISFSR states are isomorphic.

Proof

[a-1' a_ 2 , ... , a_ r+l , a_ r IT - Ibr-1' br-2' ... , b l , b01

where T is given in (16) and each b is a distinct linear combination of the

a i s as shown in (19).

The next state transformation matrix NSS of the r-stage SSFSR is

c l1 0 ... 0 0

c 2 0 1 ... 0 0

NSS

cr_l 0 0 ... 0 1

1 0 0 ... 0 0 (20)

The next state transformation matrix N IS of the corresponding r-stage ISFSR

is

0 1 0 ... 0 0

0 0 1 ... 0 0

NIS

0 0 0 ... 0 1

1 c r-1 cr-2

... c 2

c 

3-31

r

(21)
u a [a_ 1 , a_ 2 , ... , a- r+1, a-r

by u' [al-1' a$_2' ... 1 a'-r+l' at_r^

and the successor to

v = [b r-1' br-2' ... , 

b i t b01

y

' ° , ' , ... ,

1

b y ['b r-1 b 

r-2

b l i p b e 0

Then,

W- 1. a'-2' ... / a'

-r+l' a'-r^

[a_ 11 a_ 2 , ...

a_r+l' a_rINSS

[a0 , a_ 11 ... , a_ 

r+21 

a_ 

r+11

(22)

and

[bt r-1' blr-2' ... , b

' 1 , be

[b r-1' br-2' ... , bit b0INis

[b0' c r-1 b0 + br-1' ... c 2 

b 0 + b2 , c l b0 + b 1 1 (23)

where a0 = b0 is expressed in (19). The assertion that

[al

-1' a'-2' ... , a'-r+l' 

atr[T = [bar-1' be r-2' ... , b ' 1 , b'0]

is shown as follows:

R' 3-32 Ys^

S.

gg^

x

^ • %^I r V 
In accordance with (19), (22), and (23)

k b' at

r r-1 -1

m a0

a 

b0

i ' ' + ,

b r-2 4 r-l a -1 a -2

cr-1a0 + a_1

= c r- 1 b0 + br-1

b' l= c2e'-1 + (c 3 a' -2 + + c r-l a$ -r+2 + a'-r+l)

C 

20

a + ( c a

3-1

+ ... + c

r-1 r 1

a - + + a-

)

r+2

c 2 b + b2 0

bl 0

cla'--1 + (c2a'-2 + ... + 

c r-L ,' -r+2 + c r-l ay -r+l + a' -:) 

c1a0 + (c 2

a

-1 + ... + 

c r-2 a-r+l + c r-l a-r+2 + 

a

-r 1)

c 

I 

b 0 + b 

Thus, if

uT = v

then

u'T = v'

Furthermore,

vT-1 a u and v'T-1 = u'

Q.E.D.

3-33
3-34

It may be concluded from THEOREM 2 that the cycle structure (i.e., the

number of cycles of a given length) is identical for an r-stage SSFSR and an

r-stage ISFSR with isomorphic state spaces. This is a consequence of the

pra_servation of the next-state operation under the isomorphism

T : U --m. V

COROLLARY 2.1

Matrices NSS in (20) and NIS in (21) are similar (see Reference 1).

Proof

NNSS)T - u'T - v' - u(NsaT)

where T is given in (16).

(uT)N is - vNIS I' - u(TNis)

NSST and TN is both map a given u e U onto the successor of the

corresponding v e V, namely v'. Therefore,

SS

TN IS

and

ySS - TNIST-1

Q.E.D.

Consider the affine transformation

u' - uN

SS + LSS

where LSS C ;1, 0, ... 01 a 1 x r vector.
Then,

u' T - WNSS A + LSST

and

LSST LIS - (1 ' cr-1' cr-2' ... , c 2 , C 1

From THEOREM 2,

(UN SS )T - v'

prior to the translation by L IST. Given that u f---w v and

v - (b

r-1' b

b

r-2' ... b l , OJ

represent:hq

r-1 r-2

br-ly + br-2y + ... + bl y + br

The successor to v, namely vN ls i.o the vector summation

r-1 r-2

y Y ... y i

10 ' br-1' ...

b 2 , b1J

+ 

b0 (1 ' cr-1' ...

c 2 , C 1

3-35
prior to translation by L is . The vector summation

yr-1 yr-2 ...

y 1

[0 ' br-1'

b2, b11

+ b0 [1, cr-1' ... c 2 , c11

(where b0 = 1 + b0 ) includes the effects of translation by L is . The

content of the rightmost ISFSR stage is b 0 , the scalar multiplier of the

feedback vector [1, c r-1 , ... , c 2 , c I ]. Translation by L TS is

realized by complementing b 0 which results in the fr: , ^duack vector

'0 11 ' cr-1' c c11

The implementation of the ISFSR in Figure 3-2 is an example.

Consider the logical circuitry associated with an SSFSR Whose

characteristic polynomial

f(x) - x + X + 1

is a trinomial. Let a be 3 root of f W. Then,

a-1 = a r-1 + as-1

represents the feedback of a corresponding r-stage ISFSP. The ISFSR performs

division by a mouulo f(a) on its contents. As shown in Figure 3-3, the FSRs

are topologically equivalent and of identical complexity (i.e., in the number

of switching elements and propagation delay in the feedback).

3-36
dk-1 dk-2 dk-a dk-a+l dk-r

d - dk-a + dk-r

f(x) X + x + 1

f(a)=ar+aa+1=0

a-1 = ar-1 + a -1 MODULO ar + a° + 1

Figure 3-3. An SSFSR and its Corresponding ISFSR of Identical Complexity

3-37
SECTION IV

THE EXISTENCE AND ALGORITHMIC DETERMINATION OF A TRINOMIAL

OF LEAST DEGREE THAT CONTAINS A GIVEN IRREDUCIBLE

POLYNOMIAL OVER GF(2) AS A FACTOR

A. PRIMITIVE POLYNOMIALS OVER GF(2)

Primitive polynomials of degree r over GF(2) correspond to r-stage SSFSRs

(and ISFSRs) capable of generating PN sequences. A PN sequence satisfies

three postulates of randomness as proven in Reference 3.

An example of a binary sequence that is random results from repeated

tosses of an ideal join. Associated with randomness are the following

properties:

(1) The number of heads and tails are approximately equal.

(2) Short runs of consecutive heads or consecutive tails occur more

frequently than long runs. Quantitatively, approximately 1/2 of the

runs are of length 1, 1/4 of length 2, ... , 1/2 1-1 of length i, ...

(3) The autocorrelation of random sequences is peaked in the middle and

sharply drops at the ends.

Consider the periodic binary sequence

A l = fa l , a2, 

a-9-1' 

aA where 2r -1

emanating from an r-stage SSFSR whose characteristic polynomial is an rth

are: 

degree primitive polynomial. The randomness postulates satisfied by I akj

4-1
4-2

P1. Balance

Let w0 and w denote the number of 0's and 1's, respectively, in

jakI. Then,

+w0-w11<1

The disparity is exactly 1 for a PN sequence.

P2. Runs and their lengths

Within a period with a., and a l appearing consecutively, there are:

(1) One run of length r comprised of r consecutive 1's and one run of

length r - 1 comprised of r - I consecutive 0's.

(2) Two runs of length L for each run of length L+1 for each value of L

where 115L<r- 1.

One-half of the runs of length L are comprised of 0's. Runs of 0's

alternate with runs of 1's, and the total number of the runs of 0's are equal

to the total number of runs of 1's.

P3. Two-valued autocorrelation

The set comprised of

A l = ja l , a2 , ... , a _1 , a^^

A2 = jag , a3 , ... , aj , ail

A 3 = ja 3 , a4 , ... , a l , a2l

A

I

Jag, a l , ... a

^-2' a _1r

and

A0 = 10, 0, ... , 0, 01
4-3

i

from an Abelian group G of order 2 r under the binary operation of "addition"

defined on G as termwise sum modulo 2.

Ai and A satisfy the same linear recurrence relation. Therefore,

Ai + 1, for all i and j satisfies the linear recurrence relation. Thus, G

is closed under " + " defined on G.

Denote a, b, and c over GF(2) as nrresponding terms or components of

Ai , Aj , and Ak , respectively. Since

(a+b) +c=a+(b+c) mod 

elements in G are associative under "+."

The unique identity element of G is A0.

A i + AO = A0 + Ai = Ai for all i

Every element A i in G has a unique (additive) inverse, namely, itself.

Ai + Ai = A0 for all i

The elements in G are commutative under "+" since

a + b = b + a mod 2

Thus, G under "+" defined on G is an Abelian group (see References 1, 3, 4,

and 5).

The PN sequence and each of it! • cyclic shifts can be uniquely identified

by its first r terms (i.e., components). Each corresponds to a unique initial

state of the r-stage SSFSR. Thus, only the first r terms of A i + A need

to be determined to identify the resulting sequence.
4-4

'A'

Again, consider the PN sequence

A l i 

Is,' 

a2 , ... a^-1' a. I

where I = 2 r - 1

Let

b. = 1 - 2a. for all i

I i

Then, replacing 0's by 1's and 1's by -1's in A0 , Al , ... , Al yields

B01 B 1 , ... , Bj , respectively. The two tables

a. b

J J

a i 0 1 b 1 -1

0 0 1 1 1 -1

1 1 0 -1 -1 1

reveal the isomorphism

(a i + a j ) mod 2--b ib j

Thus, Ai + A = A corresponds to B,B j = B where the product

BiB.

J 

is taken term-by-term.

The autocorrelation function C(T) is two-valued. Explicitly,

^for T=O

-JC(T) _ bkbk+T

k= 1 -1 for 0 < T <.Q

Note that C(T) is the dot product of one vector whose components are comprised

of 1's and -1's (corresponding to the 0's and 1's of a PN sequence), say B1,

and B 1 cyclically shifted by T components. Since B i B 

J. 

i__ B is a

vector corresponding to an element in the Abelian group G, it is comprised of

Jt 1's if i = j (i.e., Bk = BO ) or one more -1 than 1 if i # j. Thus, a

PN sequence is highly distinguishable from any phase shift of itself.
Example 16

A 31-bit PN sequence is generated by 5-stage SSFSR described by the

linear recurrence relation

a = a

k-1 + ak-2 + ak-3 + ak-5

whose characteristic polynomial is

f(x) = x5

+x3 +x2

+x+ 1

a primitive polynomial. A period of lakI appears in Figure 4-1(a).

Of the 31 bits in jak

balance is thus satisfied.

contain 2 r-1 1 ' s and 2r-1_

the all zeros state in the

15 are 0's and 16 1's. The postulate P1 on

In general, a PN sequence of period 2 r - 1 will

1 0's. The one less 0 is due to the absence of

cycle of the states of the PN generator.

The run length properties of the PN sequence are shown in Figures 4-1(a)

and (b). The distribution of runs is in accordance with postulate P2. In

general, a PN sequence of period 2 r - 1 contains one run of length r and one

of length r-1. For 1 < L < r - 1, there are 2r-1-L runs of length L, half

of which are 0's.

The closure of two distinct elements in ;B O , B 1 , ... B^} under

termwise multiplication is shown in Figure 4-1 ( c). In general,

air = a:9 -b:9 = bO since.9=0 mod 2 r - 1

Also,

1-1 for T : ° 0

-IC(T) = L.../ bkbk+T

k=0 -1 for 0<T<rQ

4-5
N ° N + +

+

Co ° N +

I 1

N °

+I 1 C14

N ^ N 1 +

I

N ° ( N + +

+

e N^

N

I

+ 1 {

M ^ N 1 + I N

N ° 

I N+

I

1

+

N

1

N °I N+I

I

o` I I +

^0O co+ +

+

N

^ O

~co ^ r 1 I

^o o 1 O ++

+

In

rm1

I

+

•'

1

+

^Z^

cn

J

Cn

I

+

1

°I

o

^++

+

^~

^

JZ

Ln -^r I'D co co I r

^ I I

+

M

°I

I+

O, '— O1

1

+

CO '—

NZ CO

1

+

I

r- LL

1I

+

O 

0 -O +

1 I

^ ° I (

z rr C,4 J Ln +

I

I

'—

I

ui

m U- NrII

+

j O

Cl 0

cY,

+ I I

N O

I

I

Z N + +

+

^

II

^ 1 + 1

O 

^ =ZJ

O

1 I +

_j

M — 

D

^/^ I.C)^MNr

Y Y-t:r aO

Z

U

JO

Y

+Y

11

Y

^O ,p

U

Y

w p,

GJ 7O

L w

$a

swd.^ a .^

Ai a

Cu

C1 • 4

a a

a e°0r

.e L d

N i p' N

CO M

Z .O4

a —4 u

• ,+v

IO

-4 to

M O

^t ^ U

v Dui 1d

1+OW

4-6
In normalized form,

1

C(T)

_ 1

2r-1

forT=O mod 2 r - 1

for TOO mod 2 1 - 1

Specifically, in Figure 4-1(c),

31C(4) = -1

since

bk+18 bkbk+4

is the same sequence as b cyclically shifted 18 places to the left. It,

thus, has one more -1 than +1 components.

M

There are four known classes of binary sequences which satisfy both

postulates P1 and P3. See Chapter 4 in Reference 11, which terms all sequence

in these classes as PN. Of these four classes, only the class of length

2 r - 1 sequences which can be generated by r-stage SSFSRs or ISFSRs satisfy

P2 as well. In this report, only the length 2 r - 1 sequences are referred

to as PN or maximal-length sequences.

Of particular interest are primitive trinomials over GF(2) that

characterize PN generators of minimal complexity. However, there are many

values of r for which no irreducible r th degree trinomial exists.

Furthermore, there are other values of r where irreducible r th degree

polynomials exist, but none are primitive. Irreducible trinomials over GF(2)

up to degree 1000 were determined by a sequence of four tests in References 12

and 13. The primitive trinomials are distinguished from the irreducible

nonprimitive trinomials. The period and/or the index is given for many of the

latter.

4-7
The only general nontrivial result on trinomials

Tr,k (x) x r + xk + 1

was proven in Reference 14. The aP rity (even or odd) of the number of factors

Tr,k (x) is deterministic (from Corollary 5, page 1105 in Reference 14).

Tr k (x) has an even number of irreducible factors and, thus, must be

factorable if, and only if:

(1) r is even, k is odd, r it 2k, and rk/2 = 0 or 1 mod 4

(2) r is odd, k is even, k does not divide 2r, and r + 3 mod 8

(3) r is odd, k is even, k divides 2r, and r =—+ 1 mod 8

In all other cases T r,k (x) has an odd number of factors. Note that if r and

k are both odd, the reciprocal trinomial Tr,r-k(x) is subjected to test (2)

or (3).

The foregoing test preceded by two simple tests were used in References

12 and 13 to speedily eliminate reducible trinomials before applying the

fourL„ test (based on an efficient method developed by Berlekamp for factoring

polynomia.s over a finite field). See Chapter 6 in Reference 4.

Example 17

The trinomials T8m k(x) over GF(2) are reducible. If k is even,

k = 2k 1 , and

2k k

x8m +x 1+1(x4m+x1+1)2

t

F;

If k is odd,

8m ;* 2k and 8mk/2 = 0 mod 4

Thus, T8m,k(x) has an even number of factors for k odd.

4-8
A trinomial Tr k (x) is square-free if, and only if, r and k are not

both even. If

Tr,k(x) x r + xk + 1

has a repeated factor, then its derivative

V k (x) _ (r mod 2)x r-1 + ( k mod 2)x 

k-1

is divisible by this factor. Then, Tr k (x) is either: (1) a power of x

which is relatively prime to T r,k(x) or (2) is of the form x

r-1 + xk-1.

However,, a divisor of both

x

r-1 + xk-1 and x + x + 1

must also be as divisor of

x + x + 1 + x(xr-1 + xk-1) = 1

Thus, T r k (x) where r and k are not both even is square-free (see

Reference 3). The period of such trinomials is the LCM of the periods of its

irreducible factors.

The periods of square-free trinomials over GF(2), their factors, and the

periods of their factors through degree 36 are given in Reference 3. Also,

the factor of lowest degree is listed for square-free trinomials of degree 37

through 45. The wide applicability of PN sequences has been an impetus in

searching for primitive trinomials.

The remainder of this subsection deals with finding trinomials which

contain a given primitive polynomial as a factor. The state-beha • :or of an

r-stage PN generator can, thus, be encapsulated by an n-stage SSFSR (or ISFSR)

where n r. Additional register stages are the cost of reducing the

complexity of the feedback to one 2-input Exclusive-OR gate.

4-9
GF(2 r ) is expressible as an integer power of a.

aj - br-lar-1 + br-2ar-2 + ... + b I a + b0 (24)

where b i f GF(2) and a is a root of a primitive polynomial f(x) of degree r

over GF(2). Two elements, a i and ak , are defined to be a Compatible Pair

(CP) if

ai + a - 1 (i.e., 00 ... 01) (25)

The CP a i and a in (25) correspond to states in an r-stage ISFSR which

differ only in b0 (the content of stage a0 - 1). From (24), the two

states are

br-lbr-2 ..* b 1 b 0 and br-lbr-2 ... b1b0

Lemma 3

Among the 2 r - 1 nonzero elements in GF(2 r), there are 2 1 compatible

pairs. Each of the 2 r - 1 binary r-tuples (br-lbr-2 " - b 1

be ), except

00 ... 01 is compatible with one and only one nonzero r-tuple. The 2 r - 2

such elements comprise 2 r-1 - 1 CPe.

THEOREM 3

Given any r th degree primitive polynomial f(x) over GF(2). Let a be a

root of f(x) - 0. Then, for every CP Q i and a (k > j),

f(a) divides ak + ai + 1

Thus,

f(x) divides x - x j + 1

4-10
Proof

R Since Cti and ak are a CP.

!i + ak = 1

and

`t f (CO = a + ai + 1 = 0

Thus, f(x) and x + x i + I have a common polynomial factor (since they

have a common root a in GF(2 

r)). 

Since f(x) is irreducible over GF(2),

f(x) divides x + x i + 1

This implies that k > r the degree of f(x). Consider the elements (i.e., the

polynomials) 1, a, ... and ar-1 where a is a root of

f(x) x + br-lxr-1 + br.-2xr-2 + ... + b 

1 x + 1

a primitive polynomial over GF(2).

j of ai br-1 br-2 ... b 1

1

0 0 0 ... 0 1

1 0 0 ... 1 0

r-2 0 1 ... 0 0

r-1 1 0 ... 0 0

4-11
1

f

No CP exists among l,a , ..., Ctr-1 and

at br-lar-1 + hr-tar-2 + ... + b l a + 1

is compatible with ai for one value of j < r if and only if f(x) is a

trinomial. If f(x) is not a trinomial, then the degree k of

ak+ai+1-0

exceeds r for all CPS a i and ak.

Q. E. D.

COROLLARY 3.1

If ai and a are a CP, then

2j mod 2r

a

-1 and a 

2 mod 2'--1

are a CP in GF(2r)

Proof

If 1 - a i + ak , then

1 - (ai + ak ) 2 - a2 j mod 2 r-1 + a 2 mod 2r-1

Q Z. D.

COROLLARY 3.2

A trinomial of degree r + 1 cannot contain an irreducible polynomial,

hence, a primitive polynomial of degree r as a factor.

4-I2

, I—_z-
Proof

For a trinomial,

T(x) = x r+l + x i + 1

to contain an r th degree irreducible polynomial, it must also have a degree

1 factor. However, since

T(0) = 0+0+ 1 = 1

x is not a factor of T(x), and since

T(1)=1+1+11

x + 1 is not a factor of T(x).

Q.E.D.

The trinomial of least degree (among 2 r-1 - 1 trinomials associated

with 2 r-1 - 1 CPs) that contains a given r th degree primitive polynomial

(with five or more odd number of terms) as a factor is of degree n ? r + 2.

Let P be a root of

h(x) =x2+x+1

Since h(x) divides x 3-1, Q is among the 3 roots of unity. Thus,

0 3 -

1 = 9

2 + 0+ 1 = 0
A trinomial

T(x) = x + x + 1

is divisible by h(x) if and only if T(Q) = 0. Thus, if

pn mod 3 +0a mod 3

+1 =Q2+Q+ 1

T(x) contains x 2 + x + 1 as a factor. It is, thus, possible for an rth

degree irreducible polynomial to be a factor of a square-free T(x) of degree

n = r + 2.

Example 18

The trinomial

T(x) = x 16 + x 5 + 1

_f

contains x + x + 1 as a factor since

t

Q16 mod 3 R5 mod 3 + 1 =P + 

z

+ Q + 1

It may be verified that a degree 14 primitive polynomial is the only other

factor.

a

Example 1'l

The trinomial of least degree that contains the primitive polynomial

f(x) = x6 +x5 +x2 +x+t

as a factor is determined algorithmically as follows:

i

R E

4-14

.1

i

s
(1) Initially, a,a 2 , ... a6 , and a7 are computed and stored as

a list of binary state-vectors (see Table 1-1).

i of al b5 b4 b3 b 2 b l b0

i

1 0 0 0 0 1 0

4 2 0 0 0 1 0 0

3 0 0 1 0 0 0

4 0 1 0 0 0 0

5 1 0 0 0 0 0

6 1 0 0 1 1 1

7 1 0 1 0 0 1

(2) a8 is computed and compared for compatibility with a, a2,

and a7.

(3) If a8 is compatible with an element in the initial list, stop. If

not, append a8 to the list and repeat step 2 for a computed a9

and the augmented list, and so on.

The first CP to be found is all and ab.

4-15
iofal b5 b4 b3 b2blbo

1 0 0 0 0 1 0

2 0 0 0 1 0 0

3 0 0 1 0 0 0

4 0 1 0 0 0 0

5 1 0 0 0 0 0

6 1 0 0 1 1 1

7 1 0 1 0 0 1

8 1 1 0 1 0 1

9 0 0 1 1 0 1

10 0 1 1 0 1 0

11 1 1 0 1 0 0

1 1 0 1 0 0

1 1 0 1 0 1

0 0 0 0 0 1

'+ 1 0 0 0 0 0 0

a5 + a2 + a+ 1 = all + a8 + 1 = 0

x 11 +x,

 + 1 = (x5

+x4 +x3

+ x + 1 ) ( x6

+x5 +x2

+ x + 1)

Consider an 11-stage ISFSR that performs multiplication by x and reduces

the result modulo x 11 + x8 + 1. Successive states represent polynomials

of degree less than 11 since

x 11 = x8 + 1 mod x 11 ; x8 + 1
E

The cycle in Table 4-1 of length 63 corresponding to the order of a, a coot of

f(x) = x6 + x5 + x2 + x + 1 0

contains the state y representing the factor

x 5 + x 4 + x 3 + x + 1 of x 11 +x8 + 1

Recall the isomorphism between SSFSR and ISFSR states where an SSFSR state

maps onto g(x) that represents the corresponding ISFSR state. The isomorphism

was established using f(x), the characteristic polynomial of the SSFSR and an

ISFSR that p^!rforms division by x and reduces the result modulo f(x) (see

Table 3-1). However, an ISFSR that performs multiplication by x and reduces

the result modulo the same f(x) has the same cycle structure with the order of

states reversed in each cycle. Thus, g(x)'s in a cycle of the former, appear

in reverse order in the corresponding cycle of the latter.

The 63-bit PN sequence under column heading b 0 in Table 1-1 is

identical to the partially listed sequence under column heading 1 (i.e., x0)

in Table 4-1.

COROLLARY 3.3

The trinomial of least degree that contains a given primitive polynomial

f(x) as a factor is square-free..._

Proof

Assume

x2n + x2a + 1 = (xn + xa + 1)2

is the trinomial of least degree that contains f(x) as a factor. From

COROLLARY 3.1, Ofn and as are compatible and

f(x) divides x + x a + 1

contradicting the assumption. Q.E.D.

4-17
Table 4-1. A 63-State Cycle Associated with

x6 + x5 + x2 + x + 1 a Factor of x 11 + x8 + 1

i of Yxl x10 x9 x8 x7 x6 x5 x4 x3 x2 x 1

0 0 0 0 0 0 1 1 1 0 1 1

1 0 0 0 0 1 1 1 0 1 1 0

2 0 0 0 1 1 1 0 1 1 0 0

3 0 0 1 1 1 0 1 1 0 0 0

4 0 1 1 1 0 1 1 0 0 0 0

5 1 1 1 0 1 1 0 0 0 0 0

6 1 1 1 1 1 0 0 0 0 0 1

7 1 1 0 1 0 0 0 0 0 1 1

8 1 0 0 0 0 0 0 0 1 1 1

9 0 0 i 0 0 0 0 1 1 1 1

10 0 1 0 0 0 0 1 1 1 1 0

11 1 0 0 0 0 1 1 1 1 0 0

12 0 0 1 0 1 1 1 1 0 0 1

13 0 1 0 1 1 1 1 0 0 1 0

14 1 0 1 1 1 1 0 0 1 0 0

15 0 1 0 1 1 0 0 1 0 0 1

16 1 0 1 1 0 0 1 0 0 1 0

17 0 1 0 0 0 1 0 0 1 0 1

18 1 0 0 0 1 0 0 1 0 1 0

19 0 0 1 1 0 0 1 0 1 0 1

20 0 1 1 0 0 1 0 1 0 1 0

21 1 1 0 0 1 0 1 0 1 0 0

60 0 1 1 0 1 1 0 0 1 1 1

61 1 1 0 1 1 0 0 1 1 1 0

62 1 0 0 1 0 0 1 1 1 0 1

Y'x5 +x4 +x3+x+1

4-18
The triromial of least degree that contains a given primitive polynomial

over GF(2) as a factor may be determined from Appendix B. One primitive

polynomial, f(x), of every reciprocal pair is listed for degrees 5 through

12. The octal equivalent of the binary coefficients in descending powers of x

represents f(x). in example 18, it was shown that

x 11 +x8 + 1 = (x 5 +x4 +x3 +x+ 1)( x6

+x5 +x2 +x+ 1)

The octal representations of the respective factors are 73 and 147. See

Appendix B for row entries associated degree r of 6 and f(x) represented by

147. Clearly,

x 11 +x3 + 1 = (x5 +x4 +x2 +x+ 1)(x6 +x5 +x4 +x+ 1)

The respective octal representations of the factors are 67 and 163. Since 147

and 163 represent a reciprocal pair of primitive pulynomials of degree 6, only

147 (with the lower octal representation) and T(x) (n = 11, a = 8) of lowest

degree containing 147 as a factor are listed.

Consider the entries in Appendix B associated with r of 9 (degrees ( 8rees of

f(x)) and 1243, the octal representation of f(x).

T(x) = x36 +x+ 1 ( n = 36, a = 1) 

The entries under the right-most four columns are as shown as follows:

Irreducible Factors Degree 

of T(x) in Octal of Factor Period Index

1243 9 511 1

2257* 10 341 3

540663* 17 131071 1

4-19

K E

t

_F

7
_20

All entries pertaining to f(x) represented as 1243 are in italics. The

asterisk (*) appended to the degree 10 factor (2257*) and the degree 17 factor

(540663*) indicate that

T(x) = x 36 + x + 1

is also the trinomial of least degree that contains each of foregoing

factors. The degree 10 factor is nonprimitive and has period 341 (i.e., the

order of its roots is 341) and index 3

(i.e., (2 10 - 0/3 = 341)

In terms of Galois Fields, let )9 be a primitive root n GF(2 10 ) of

210-1

x - 1 0

Thus, Q 3 has order 341 and is the root of an irreducible nonprimitive degree

10 polynomial whose period is 341 and index is (3, 2 10 - 1) or 3.

The independent parameters for all entries in Appendix B are r, the

degree of f(x), and f(x), the primitive polynomial. The f(x)'s of a given

degree r are listed in ascending order of u, the degree of the respective T(x)

of lowest degree which contains f(x) as a factor. T(x)'s of degree n < 70 are

factored if they are the lowest degree trinomial containing an f(x) of degree

12 or less. Factoring a T(x) (which was determined to be the trinomial of

lowest degree containing f(x) of degree r as a factor) often yields 

irreducible polynomials (primitive and nonprimitive) of degrees greater than r 

which are not contained in a trinomial of lower degree. The octal 

representation of these polynomials (as well as those of the same or lower

degree than r) are identified by art asterisk
Example 20

The primitive polynomial f(x) of degree 11 represented by 5023 is

contained as a factor in

T47,39 (x) = x47 + x39 + 1

t

T47,39(x) is the trinomial of least degree that contains 5023 as a factor as

determined by the algorithm presented in Example 19. Prior to dividing

T47,39(x) by 5023 and factoring the quotient polynomial, it is expedient to

extract factors of low degree as follows:

All irreducible factors of degree r are factors of

x 2 r-1 - 1

If

T (x) = x + xa + 1

n,a

contains an r th degree factor, then

r

a2

-1 _1 = an + as + 1 = 0

where a is a root of the r th degree factor. Let 2 r - 1 = w. Then,

a = 1 and if

an mod w 

+ as 

mod w + 1

contains an irreducible r th degree polynomial as a factor, so does

Tn a (x). Simplification in extracting factors results only if w < n.

Specifically,

a47 mod 3 + a39 mod 3 + 1 = a2

4-21
and T47,39(x) does not contain x2 + x + 1 (the only degree 2 irreducible

polynomial over GF(2)) as a factor.

a 47 mod 7 

+ a 

39 mod 7 +1 a5 +a4 + 1

and a3 + a + 1 is a factor of a 5 + a4 + 1. Thus, x 3 + x + 1 (13) is a

factor of T47,39W.

a 47 mod 15 +a39mod 15 + 1=(x2 +a9 + 1

and a 4 + a 3 + 1 is a factor of a 9 + a2 + 1 (see Reference 3). Thu.

x4 + x3 + 1 is a factor of 

T47,39(x)

a47 mod 31 + a 39 mod 31 + 1 : (a2 + a + 1)8

and T47,39(6) does not contain a degree 5 irreducible polynomial as a factor.

Since w = 2 - 1 > 47, the foregoing test of divisibility cannot be extended

beyond irreducible degree 5 factors. Dividing out the irreducible factors 13,

31, and 5023 yields the remaining degree 29 factor h(x) represented by

7036510105. It remains to determine if h(x) is irreducible. Since

229

a 0 a mod h (a) 0

h(x) is reducible. Repeated squaring

222

229

a,a,a ... ,a

where each result is reduced module h(a) is readily realizable on a digital

computer.

4-22
Squaring any field element in GF(2 r ) is equivalent to multiplying the

field element (i.e., an r-bit binary vector) by an rxr binary matrix M. Each

term (i.e., power of a) is squared modulo h(a). See Chapter 2 of Reference 4

and Example 21.

The aforementioned 29 th degree factor is then subjected to Berlekamp's

factorization algorithm over GF(2) which is amenable to programming on a

digital computer. Applying Berlekamp's factorization algorithm to the 29

degree factor 7036510105 (which is known to be reducible) reveals it has 2

factors. One is 1725 of degree 9 and the other is 4772721 of degree 20. The

foregoing results are used to complete the entries in Appendix B which are

factors of 

T47,39(x), 

the trinomial of least degree that contains f(x) of

degree 11 represented by 5023 as a factor. The entries are as follows:

Coefficient Irreducible

of f(x) in T(x) Factors of T(x) Degree

r Octal n a in Octal of Factor Period Index

11 5023 47 39 13 3 7 1

31 4 15 1

1725 9 511 1

5023 11 2047 1

4772721* 20 1048575 1

The irreducibility of a factor of degree 19 or less is verified in Reference 7.

The test for irreducibility for factors of degree greater than 19 is applied

(as illustrated in Example 21). The period of each irreLicible factor of

degree 19 or less can also be determined from Reference 7. The determination

of the period of an irreducible factor of degree m > 19 is subsequentially

discussed.

It remains to ascertain whether each of the factors of T47,39(x) 

other

than 5023 are factors of a trinomial of degree less than T47,39 

W. Of the

four factors, only 4772721* (as denoted by (*)) of degree 20 is not a factor

of a trinomial of degree less than T

47,39 W.

4-23

-
4-24

Factors 13 and 31 of degrees 3 and 4, respectively, are trinomials, and

T45,25(x) is the trinomial of least degree that contains factor 1725 of

degree 9.

A 47-stage SSFSR or a 47-stage ISFSR, each with a single 2-input

Exclusive-OR gate in the feedback, is characterized by T47,39 W. Properly

initialized, the SSFSR and the ISFSR can generate a PN sequence of length 7,

15, 511, 2047, or 1,048,575. Of these, lengths 2047 (2 11 - 1) and 1,048,575

(2 20 - 1) correspond to the most efficient use of the periodic binary

sequence generator. Furthermore, a binary sequence whose length is the LCM of

any subset of the five available periods could be generated. Initialization

is governed by the factors of T47,37 W.

Assume an ISFSR configuration where multiplication (or division) by CI,

a root of T47 39(x) s 0, is performed. To generate a PN sequence of length

1,048,575 (2 26 - 1), a suitable initial state corresponds to the product of

the polynomial factors of T47,39(x) excluding 4772721, the primitive

polynomial of degree 20. That is,

'Y- (13)(31)(1725)(5023)

a polynomial of degree 27 corresponds to a state in the desired cycle.

. 

Example 21

Given the polynomial

f(x) - x 8

+x7 +x4 +x3 +x2 +x+ 1

Testing whether f(x) is irreducible without resorting to tables may be done as

fellows:
Any element

b7 a7 + b6 a6 + ... + b 1a + b0

represented by [b 7 , b6 , ... , b l , b0 ) may oe squared by post

multiplication by M over GF(2).

a7 a6 a5 a4 a3 a2 a 1

1 0 1 1 0 1 1 1

0 1 0 0 1 0 1 0

1 1 U 1 1 1 0 1

M- 1 0 0 1 1 1 1 1

0 1 0 0 0 0 0 0

0 0 0 1 0 0 0 0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 1

where a is a root of f(x) - 0. Row 8, 7, ... , 1 in M correspond to

polynomials

(a0)2, (a' )2, ... , (a7 ) 2

mod f(a)

respectively. Starting with

a- [00000010),

am - a2

2

a 

2 

M a 4 - a2

a27M - a

256 - a28

Reducing each result modulo f(a), yields

4-25
a7 a a5 a4 a 3 a2 a 1

0

a2 0 0 0 0 0 0 1 0

1

a2 0 0 0 0 0 1 0 0

2 

2

a 0 0 0 1 0 0 0 0

3

a2 1 0 0 1 1 1 1 1

4

a2 0 1 1 1 1 1 0 1

5

a2 0 1 0 1 1 0 0 1

6

a2 1 0 0 1 0 1 0 0

a2 0 0 1 1 1 0 0 C

8

a2 0 0 0 0 0 0 1 0

n

Since a2 = a mod f(a)

for a least value of n of 8, the order of a is 2 8 - 1 s 255 or a divisor of

255. It may be concluded that f(x) is irreducible. However, its period is

yet to be determined.

M rth degree irreducible fix) polynomial over GF(2) has period d where

d divides 2 r - 1. Then, unique subsets of

Z

2r-1

a, a , ... I a

reduced modulo f(x) are multiplied to form x modulo f(x). The least value

of d for which

ad = 1 mod f(a)

4-26
2 + x + 1

M

is the period of f(x), i.e., the order of its roots. If the least value of d

is 2 r - 1, then f(x) is primitive.

Example 22

In Example 21, it was shown that

f(x) =x8+x7+x4+x3+x2+x+ 1

is irreducible. The divisors d > 1 of 255 are

3, 5, 15, 17, 51, 85, 255

The number of irreducible polynomials of degree 8 whose roots have order d is

cp(d)/8. Values of 3 and 5 for d can, thus, be ruled out. Clearly,

a d ^ 1 mod `f(a) for d = 3, 5.

Since

a16 x a mod f(a)

as shown in Example 21, a does not have order 15. Also, 

a 17 = a • a16 1 mod f(a)

rules out d = 17 which could also be deduced from the fact that f(x) is not a

self-reciprocal polynomial. The binary equivalent of 51 is 110011, and

a51 = a16 a8 a

2 a =_ 1 mod f(a)

Thus,
Given a primitive polynomial f(x) of degree r over GF(2) comprised of an

odd number of terms greater than 3. No method is known of predicting the

degree of T(x), a trinomial of lowest degree, which contains f(x) of degree r

as a factor. A lower bound was shown to be degree r + 2 where

Tr+2,a(x) _ (x 2 + x + 1)f(x)

Among

2 3

2r-1

a,a,a, ... ,a

there must be at least ore CP. Each of the corresponding 2 vectors

has at least one 1 in the first r - 1 components. Among these 2 r-1 r - 1

bit segments (where a* and (10 are excluded), there must be at least one

identical pair. Thus, an upper bound of the degree of T(x) is 2 r-l . From

entries in Appendix B for f(x)'s of degree r from 5 through 12, 2r-1

represents a crude upper bound. This is shown tabularly as follows:

Coefficient of T(x)

r f(x) in Octal n a

2r-1

5 57 8 3 16

6 147 11_ 8 32

7 313 21 18 64

8 607 27 8 128

9 163 61 39 256

10 3117 83 14 512

11 5667 143 12 1024

12 1417 171 42 2048
The following statistical model leads to a more reasonable disparity of

estimated and actual results. Every r-bit nonzero number appears once, and

only once, in an r-stage ISFSR (or SSFSR) cycle characterized by a primitive

polynomial of degree r over GF(2). The 2 r - 1 numbers are, thus, uniformly

distributed. Such an ISFSR generates random numbers although a strong

dependence exists between a number (i.e., vector state) and its predecessor

(see Reference 15).

i

The statistical model is comprised of cells into which random placing of

balls occurs until the first time occurrence of placing a ball into a cell

already occupied. The two balls correspond to a Compatible Pair (CP) of ISFSR

states. This occupancy model is lucidly presented in Section 7 of Chapter II

in Reference 16. Following Feller's approach, (j l' i 2' "' in)

_ denotes that the first, second, ... and n th ball are placed in cells

numbered 

j l' j 2' ...

in$ and the process terminates on the nth

step. The j are integers between 1 and m = 2 r - 1. For n, only the

values 2, 3, ... , and m + 1 are possible. Two balls cannot occupy the same

cell before the second step or after the (m + 1)st step.

Attributed to each sample point (j l , j 2' •.. i n ) involving exactly n

balls is the probability m n.

The aggregate of all sample points (j l , i 2 , ... , 1 n ) for a fixed n

corresponds to the event that the process terminates on the n th step.

= P(m, n - 1) • ( n - 1)

qn

m (26)

is the probability a CP is found on the n th step. The permutation of m

things taken n - 1 at a time is denoted by

P(m, n - 1) = m(m - 1) ... (m - n + 2)

4-29
The numbered cells j 1 j 2 , ... , and jn_ 1 can bL selected in P(m, n - 1)

ways. The probability q in ( 26) can be expressed as

qn = (1 - m)

\

1 - mI... ( - 

n 

m 

2 

A m 1 , (27)

where q l = 0 and q2 = 1/m

The probability that the process continues for more than n steps is

Pn = 1 - (q l + q2 + ... + qn)

where p l = 1. By induction,

pn __ P(mnn) I 1 m)(1 - m 1 ... ^1 - n m 1)

(28)

For n << m, cross products can be dropped and

zl_ 1+2+... +(n- 1)=1-n(n-1)

pn m 2m (29)

Since

Ln(1 - x) z -x for small x > 0

t

where Ln denotes the natural logarithm,

Lnp 1+2+

•

. +(n-1) =- n(n- 1)

n m 2m

and

R

-Ln pn x n2 /2m (30)

k

"r 4-30
4-31

Consider n for which

Pl+p2+ ... +Pn-1f'1/2

and

pl + p2 + ... + P > 1/2

This value of n is the median of the distribution of ;p n }. The first CP is

as likely to be found in n steps as for the process to continue beyond n steps

for the first CP to be found. The value of n corresponding to the median of

the distribution 1pn I is closely approximated by

n = (2m • Ln2) 0.5

(31)

(see Reference 16.) Each primitive polynomial of a given degree r in

Appendix B may be considered as corresponding to an experiment. Each

represents a different random number generator. The median of the value of n

of I Tn a (x)} in Appendix B associated with primitive polynomials of a given

degree r (5 throu^,h i2) is coiap,::red with n computed in (31). This is shown

tabularly as follows:

Median of n

r in ITn , a(x)t r(2m • Ln2)0.1

5 7 7

6 8 10

7 14 14

8 20 19

r 9 29 27

10 42 38

11 63 54

12 82 76
Note that m - 2 r - 1 and rxj denotes the smallest integer n 2:x. The

computed value of n corresponding to the median of the distribution ;p l

r

increases with the square root m = 2 r - 1. In determining n of T n a(x)

algorithmically, each r-stage ISFSR initially generates the identical ordered

set of r r-bit vectors, namely,

2 r-1 1, a, a ... , a

and a CP could not appear before step r + 3 [or r + 1 in the case where f(x)

is a trinomial of degree r]. The statistical model does not account for

this. Each initialization and succeeding numbers (i.e., vectors) are randomly

selected. The low value of n corresponding to he median of the distributions

of IT

n,

a(x)i and Ont compared to the crude upper bound of 2 r-1 for n is

encouraging. Among primitive polynomials of degree r > 12, one would expect

to find some contained in a T n a(x) where n < l0r. See Appendix B where

every Tn a (x) for values of n < 70 is factored if it contained a primitive

•

polynomial of degree 12 or less. Irreducible polynomial factors up to degree

55 were found.

A partial list of primitive polynomials from degree 13 through 19 appears

in Appendix B. Every (row) entry lists r, the degree of f(x), f(x) of index

1, its reciprocal x r f(1/x), and the powers of x (n and a) of T(x), the

trinomial of lowest degree containing f(x) (or its reciprocal) as a factor.

Another factor of T(x) is given if it is an entry that appears elsewhere in

Appendix B or Appendix C. If the degree of the second factor is 12 or less,

it serves as a cross reference. For example, consider the following row entry:

Factor of T(x)

Listed Elsewhere

f(x) of T(x) Coefficient

r Index 1 xrf(1/x) n a r in Octal Period Index

14 70767 73707 53 28 10 2305 1023 1

4-32
T53,28(x) was found to be the trinomial of lowest degree to contain the

degree 10 polynomial 2305 as a factor. The period of 2305 is 1023 and its

index is 1, hence, 2305 is primitive. Among the entries of degree 10 in

Appendix B, f(x) represented by 2305 is listed followed by n of 53 and a of 28

associated with T(x), i.e., 

T53 28(xW. The factors of T53 28(x) include

,

the polynomial 73707* of degree 14 whose period is 16,383 and index is 1. The

factorization of 

T53,28(x) 

led to the primitive degree 14 polynomial

73707*. Note that the degree 14 reciprocal polynomial has a lower octal

representation, namely, 70767. However, since 73707 is the factor of

T53,28(x), it is italicized in the foregoing example of a listing of a

degree 14 primitive polynomial.

There are entries in Appendix B of primitive polynomials of degree 14

through 19 for which no other factor of T n a (x) is given. Each of the other

,

irreducible factors are either a factor of a trinomial of degree less than n

or the degree of each exceeds 19. In the latter cases, the single factor of

T

n,a 

(x) -vas found in the table of factors of square-free trinomials through

degree 36 in Reference 3.

In Appendix B (as well as Appendix C), the period (and index) of

irreducible factors of T n,a (x) whose degrees exceed 19 were not determined

in many cases. These entries are blank.

B. IRREDUCIBLE NONPRIMITIVE POLYNOMIALS OVER GF(2)

Unlike primitive polynomials, there are irreducible nonprimitive

polynomials over GF(2) which are not factors of any trinomial. Irreducible

# nonprimitive polynomials over GF(2) from degree 6 through 12 that are factors

r

of trinomials are listed in Appendix C.

Every irreducible polynomial of degree r over GF(2) where 2 r - 1 is

prime is primitive (see Appendix A). Thus, every irreducible polynomial of

degree 2, 3, 5, 7, 13, 17, 19 or 31 are primitive. Primes of the form

M - 2 r - 1

r

4-33
are known as Mersenne primes. A necessary, but not a sufficient condition for

E

M

r 

to be prime, is that r is prime. See Chapter IX in Reference 3 for a

list of 27 of 30 known Mersenne primes.

The Mersenne number (Reference 4)

Mll = 211 - 1 = 2047 = 23.89

is composite through 11 is prime. Of the 186 irreducible polynomials of

degree 11, 176 are primitive and 10 are nonprimitive. None of the 10, degree

11 irreducible nonprimitive polynomials (2 of period 23 and 8 of period 89)

divide a trinomial.

Given h(x), a degree r irreducible nonprimitive polynomial over GF(2),

with an odd number of terms exceeding 3. The subset of elements of GF(2r)

generated by a, a root of h(x) = 0, are

a, a2 , ...

ad-1 , dd = 1

The order of a is dd where d< 2 r - 1 and d divides 2 k - 1 for k = r, but 

does not divide 2 r - 1 for r < k. Since

d - 1 = h(a) 0,

the r distinct roots of h(x) = 0 are among the d roote of unity. Assume

d = sv. Then

a , a2v , ...

a(-1)v, a

S ° 1

are among the d roots of unity. Substituting ft for av yields

p, f2 , ...

, .8

, 

J6 = 1

which comprise the s roots of unity. The s roots of unity are thus a subset

of the d roots of unity if s divides d. Furthermore, every element whose

4-34

E
order s divides 0 must be a power of a, since an element of order s is a

generator of the j roots of unity. If the integer a is of the form

s i 2" - 1 > 1

then

^v^ ^2v^ ^(s-1)v, asv 1

are roots of

x2u-1-1=0

and are the nonzero elements of GF(2 u ). Among the 2 u - 1 nonzero elements

of GF(2 u ), there are 2 0-1 - 1 Compatible Pairs (CPs). This means that

h(x), the irreducible nonprimitive polynomial of degree r, is a factor of a

trinomial if the order of a root of h(x) = 0, say d, is divisible by s of the

form

s = 2 u - 1

Example 23

The irreducible polynomial

h(x) =x6

+x5 +x4

+x 2 + 1,

as discussed in Examples 2 and 3, has period 21 (and index 3). Its roots are

among the 21 roots of unity. Thus,

Q 2i -

1=Q6+Q5+Q4+Q2+ 1=0

and h(x) divides x 21 - 1. The 21 roots of unity are a subset of GF(26)

and form a group under the defined operation of "multiplication." However,

4-35
the 21 rootri with 0 (9*) adjoined do not form a group under the defined

operation of "addition." Contained within the 21 roots of unity

Q, 92 , ... , 020 , 9= 1

are the nonzero elements of the subfields GF(2 2 ) and GF (23).

respectively. Each nonzero element of GF(2 2 ) is a root of

X 2 2-1- 1-X3- 1 -0

whereas, each nonzero element of GF(2 3 ) is a root of

x2 3-1 _ 1-x7 - 1-0

Let {0w } be the set of 3 roots of unity.

(9w ) 3 mod 21 - 1 -90

and

3w=0mod 21

w = 0 mod 21/(3,21)

we0mod 7

w Y 0, 7, 14

Thus,

i

. 

90 , 97 , 914 }

are the 3 solutions. From Table 1-3,

07 = 0 1 1 1 1 1 and 014 - 0 1 1 1 1 0

are a CP.

Similarly, let ;9 yl be the set of 7 roots of unity. Then,

W)7 mod 21 . 1 - 00

4-36
and

7y = 0 mod 21

y = 0 mod 21/(7,21)

y=0mod 3

y 3 for k • 0, 1, ... 6

Thus,

fo yj a J,o ' 16 3 , 166 , 169 , 16 12 , 1615, 16181

are the 7 solutions. Placing the nonzero y's into cyclotomic cosets yields

3 6 12

9 18 15

as shown in Tablt 1-4. Since each coset has an odd number of entries, each

member of a CP is associated with a different coset. This is a consequence of

Corollary 3.1. It may be verified in Table 1-3 that 16 3 and 169 are a CP.

Hence, 16 6 and 1618 as well as912 and 

1615 

(due to Corollary 3.1) are

c ps. 

Applying the algorithm described in Example 19 to 

h(x) = x6 +c5 + x 4 + x 2 + 1

in this example reveals that

T913 (x) = xg + x 3 + 1

is the trinomial of least degree that contains h(x) as a factor. It

corresponds to the CP p 3 and 0 9 in the subfield GF (2 3 ). The reciprocal

of h(x), namely, x6 h(1/x) represented by 127 contained in T 9,6 (x) is an

entry in Appendix C.

0

4- 37
P

4-38

Example 24

The order of the roots of the degree 12 irreducible nonprimitive

polyw vial

h(x) -x12+x10+x9 +x8+x7 +x3+x2+x+1

is 585. The prime factors of 585 are 3 2 , 5, and 13. Since 15 is a divisor

of 585, the nonzero elements of GF(2 4 ) are contained among the 585 roots of

unity. Letj$w l be the set of 15 roots of unity. Then

15w °- 0 mod 585

w = 0 mod 585/(15,585)

w a 0 mod 39

w-39k for k-0, 1, ... 14

The cyclotomic cosets containing the 14 nonzero values of w are as follows:

39 78 156 312

117 234 468 351

r - 195 390

273 546 507 429

Dividing each entry by 39 yields

1 2 4 8

3 6 12 9

t 5 10

F

7 14 13 11
which correspond to the 15 roots of unity (excluding a 0

1) in the

R

isomorphic GF(2 4 ) generated by a root of x 4 + x + 1 - 0 (or a root of its

'. reciprocal x4 + x3 + 1 = 0). Consider the 7 CPs in the 15 roots of unity

genc:, ated by a where a4 + a + 1 - 0, the CP a 4 and a correspond to the CP

0156, and 0

39 , respectively, and

0156 + 039 + 1 - h (R) - 0,

the CP a4 and a3 correspond to the CP 

0156 

and 0117, respectively, and

0156 

+0 

117 + 1 = 012 . hW12 ) -

0.

Thus, h(x) is a factor of 

T156,39(x) 

and x h(1/x) is a factor of

T156,117(x), the reciprocal of T156,39(x). There are

(Pp 585) i tp(32)^p(5)903) = 24

12 12

degree 12 irreducible nonprimitive polynomials over GF(2) of period 585 and

index 7. 

T156,39 (x) contains one of each reciprocal pair (12 total) as

factors and a degree 12 irreducible nonprimitive polynomial of period 45 (a

divisor of 585) and index 91. These are listed as follows:

Irreducible Factors Degree

of T156,39(x) in Octal of Factor Period Index

11001 12 45 91

10245 12 585 7

11433 12 585 7

11637 (h(x)) 12 585 7

12153 12 585 7

12673 12 585 7

13113 12 585 7

13145 12 585 7

13567 12 585

14043 12 585 7

14177 12 585 7

14315 12 585 7

17315 12 585 7

4-39
The reciprocal of each of the foregoing degree 12 factors of

T156,117(x), the reciprocal of T156,39 W.

Among the 15 roots of unity are go, p195' and p390 , the 3 roots of

unity. All 24 degree 12 irreducible nonprimitive polynomials whose roots have

order 585 are factors of T390,195(0.

Although T156,39(x) is the trinomial of lowest degree derived from the

7 CPs in the 15 roots of unity, it is not the trinomial of lowest degree to

contain h(x), whose octal representation is 116 37, as a factor. By applying

the algorithm illustrated in Example 19, the first CP is found to be Qll and

923 where

911 1 0 0 0 0 0 0 0 0 0 0 0

9 23 1 0 0 0 0 0 0 0 0 0 0 1

Thus,

x23 + x ll + 1 - T23.11(x)

is the trinomial of least degree to contain h(x) of degree 12 and period 585

(and index 7) reprejented by 11637 (see Appendix C). Note that 011 and 923

among the 585 roots of unity are no: members of GF(24).

6

Examplea 25

The order of the roots of the degree 8 irreducible nonprimitive polynomial

h(x)-x8

+x6

+x5 +x4

+x2

+x+ 1

is 85. The prim factors of 85 are 5 and 13, and 85 has no divisors of the

form 2 k - 1. It may be verified that

r_11 1. "5+1-T115(x)

4-40
contains h(x) represented by 567 as a factor, although no subset of 85 roots of

unity are the nonzero element of a Galois field. Furthermore, 

T11 5 (x) is

the trinomial of least degree containing h(x) as a factor (see Appendix C).

N

THEOREM 4

A sufficient but not a necessary condition for an irreducible

nonprimitive polynomial, h(x), over GF(2) with an odd number of terms

exceeding 3 to be a divisor of a trinomial is:

The order of its roots d contains a factor of the form s = 2 u - 1 > 1.

Proof

Given h(x) of degree r over GF(2) whose roots have order d where d < 2 r - 1

and d divides 2 k - 1 for k = r, but does not divide 2 k - 1 for k < r. Each

root of h(x) = 0 generates the d roots of unity. If d = sv and

s = 2u - 1>1,

then, a subset of the d roots of unity is comprised of the nonzero elements of

GF(2 u ). Each element is a polynomial of degree less than r representable by

an r-bit vector. These elements are isomorphic to the nonzero elements in

GF(2 u ) representable as u-bit vectors. Clearly, u divides r. The 2 u - 1

u-bit vectors contain 2 u-1 - 1 CPs. The isomorphic 2 u - 1 r-bit vectors

also contain 2 u-1 - 1 CPs where a compatible pair of r-bit vectors are

isomorphic to a compatible pair of u-bit vectors (see Example 6).

The d roots of unity can contain CPs and no subset of elements that

comprise a Galois field (see Example 25).

Q.E.D.

4-41
COROLLARY 4.1

If Q' and Qk 

are a CP among the d roots of unity, then

Q2 j mod d and 92k mod d

are a CP contained in the d roots of unity.

Proof

h(Q)1.3k + Qj + 1

and

h(x)lxk + x j + 1

Thus,

h(x)I(xk + xd + 1) 2 = x2k + x2j + 1

since

1

9(x) 1 2 = g(x2) 

where g(x) is any polynomial over GF(2). Then,

92k mod d and Q 2j mod d

are each members of the d roots of unity

0 1 12 , ... ,)9

X10 1

which form a group under "multiplication" where

Rw Qy = Q(w+v) mod d

4-42
Since

h(x),x2k + x 23 + 1

h(8) =02k mod d +02j mod d+ 1

= 0

and

k

c._ p2k mod d and p 2j mod d

are a CP. Q.E.D.

Example 26

The cyclotomic cosets associated with Q5 and pll , where Q is a root

of h(x) - 0 given in Example 25, respectively, are:

5 10 20 40 80 75 65 45

11 22 44 3 6 12 24 48

The entries in each cf the 8 columns are associated with a CP (Qk, ^3)

which corresponds to a trinomial divisible by

h(x) = x8

+x6 +x5

+x4

+x2

+x+ 1

representable by 567. The square-free trinomials divisible by 567 are listed

in ascending order of degree as follows:

x11+x5+1

F

x40x3+

+1

t.

48 45

x + x + 1

65 24 x + x + 1

75 12

x + x + 1

4-43

r.
4-44

The additional square-free trinomials a-e another source of trinomials of

lowest degree that contain an irred u cible polynomial of degree greater than

19, e.g., the factors of

X40+x3+1

are 567 (i.e., h(x) of degree 8 and period 85 and 54556457063, an irreducible

polynomial of degree 32. The factors of 2 32 -1 are

(2 2 - 1) (2 2 + 1) (24 + 1) (2 8 + 1) (2 16 + 1)

3 5 17 257 65,537

and the period of the degree 32 irreducible polynomial divides 2 32 - 1.

Each of the prime factors :iay be expressed as

F = 22 n + 1

n

for

n = 0, 1, 2, 3, 4

These are known as Fermat primes. Every F n Fermat number where n > 4, whose

character has been determined to date, is composite.

It may be verified that 

T40,3 

(x) is the trinomial of least degree that

contains the degree 32 irreducible polynomial 54556457063 over GF(2) as a

factor.

M

The following theorem and corollaries are due to Golomb (see Reference 3).
_ THEOREM 5

A self-reciprocal polynomial over GF(2), h(x), divides a trinomial only

if the three roots of unity 0 , Qa, and 9 for some a are a subset of

the elements generated by i3, a root of h(x) = 0.

Proof

Assume

h(x) I x + xa + 1

Then,

x h(l/x)ixn + xn-a + 1

Given

h(x) = x h(1/x)

Then,

Therefore,

and

h(x)I(xn + xa + 1) + (xn + xn-a +1) = x

n-a + xa

h(x)!xa(xn-a + xa ) + (xn + xa + 1) = x 2 + xa + 1

hW) = 

A la + pa + 1 = 0

4-45
I are a CP, and the 3 roots of unity

Qa Q2a 03a = 1

are a subset of the elements generated by )3. The period of h(x) must,

therefore, contain 3 (i.e., 2 2 - 1) as a factor.

Q.E.D

COROLLARY 5.1

No trinomial is divisible by both x 3 + x + 1 and x3 + x2 + 1.

Proof

U(X) = ( x3 +x+ 1) (x3 +x2 + 1) =x6

+x5 +x4 +x3 +x2 +x+ 1

a self-reciprocal polynomial whose roots have order 7, and 7 is not divisible

by 3.

The elements generated by R, a root of u(x) - 0 are

i of 'Q1 c5 c4 c3 c2 cl CO

0 0 0 0 0 0 1

1 0 0 0 0 1 0

2 0 0 0 1 0 0

3 0 0 1 0 0 0

4 0 1 0 0 0 0

5 1 0 0 0 0 0

6 1 1 1 1 1 1

0 0 0 0 0 0 1

and no CP is among them.

Q.E.D.

4-46
COROLLARY 5.2

No trinomial is divisible by

h(x) = x4

+x3 +x2

+x+ 1

an irreducible self- reciprocal polynomial whose roots have order 5.

Proof

Since 3 is not a divisor of 5,

3 5

x - 1 does not divide x - 1

and all 3 roots of unity are not a subset of the 5 roots of unity.

The 5 roots of unity generated by /3, a root of h ( x) 0, do not contain a

CP.

Q.E.D.

Example 27

There are 6 self- reciprocal irreducible polynomials of degree 18 whose

roots have order 171 ( and index 1533). See Table 1-5.

Let Ia 

at 

be the set of 3 roots of unity which are a subset of the 171

roots of unitfy.

(,,a)3 mod 171 = 1 = R0

and

3a ° 0 mod 171

a - 0 mod 171/(171/3)

a - 0 mod 54

a 0, 57, 114

4-47
I

5

Thus,

h(p) =0114 +0 57 + 1 s 0

and

h(x)Ix114 + x 57 + 1

where h(x) is any one of the 6 self-reciprocal irreducible polynomials of

degree 18. Thus, T114,57(x) has 6 degree 18 factors when multiplied

together over GF(2) yields a degree 108 polynomial.

The remaining degree 6 self-reciprocal polynomial is one of the following:

Self-Reciprocal Polynomials

Binary Coefficients of

x6 x5 x4 x3 x2 x 1 Factors

(1) 1 0 0 1 0 0 1 irreducible

(2) 1 0 1 1 1 0 1 ( 1 1 1)( 1 1 1 1 1)

(3) 1 1 0 1 0 1 1 ( 1 1 1)( 1 1 1 ) ( 1 1 1)

(4) 1 1 1 1 1 1 1 ( 1 0 1 1)( 1 1 0 1)

Polynomials (2) and (4) can be ruled out due to Corollaries 5.2 and 5.1,

respectively. Since T114,57(x) is square-free, polynomial (3) cannot be a

factor. Thus,

x 6 + x 3 + 1

with period 9 (and index 7) is the remaining factor. The irreducible factors

of T114,57(x) are listed as follows:

4-48
Irreducible Factors of Degree

T114,57 ( x) in Octal of Factor Period Index

111 6 9 7

1055321 18 171 1533

1167671 18 171 1533

1315315 18 171 1533

1331155 18 171 1533

1505213 18 171 1533

1635347 18 171 1533

Note that Q114 and^(3 57 is the only CP among the 171 roots of unity. This

is independent of the generation of the 171 roots of unity. Thus, applying

the algorithm to each of the 6 self-reciprocal polynomials of degree 12 yields

T114,54(x) as the trinomial of least degree containing the given

self-reciprocal polynomial as a factor.

The polynomial h 1 (x) represented by 1055321 is listed in Appendix C of

Reference 6 appended to its index 1533. The minimal pc,iy p omial h 1

('95

) = 0

was determined by a computer program to be h 2

( x)represented by 1167671,

etc. The 6 self-reciprocal polynomials of degree 18 given in the foregoing

table are listed in Reference 7. However, they are erroneously classified as

primitive.

8

Golomb, in Reference 17, discusses irreducible polynomials,

synchronization codes, and primitive necklaces in the context of cyclotomic

algebra.

4-49

`r 
SECTION V

VERY LARGE SCALE INTEGRATED CIRCUIT CONSIDERATIONS

Switching elements comprise less than 10% of the active chip area of a

Very Large Scale integrated (VLSI) circuit chip. Interconnections make up the

balance.

A static shift register is made up of identical stages or cells.

Identical cells lead to a maximally regular topology in a VLSI layout known as

a floor plan. The geometric design of one cell is replicated to a desired

number to form a cascade. Each cell is a clocked memory element called a

static flip- flop. The flip-flop is a bistable device capable of assuming one

of two state-values.

A functional logic diagram of a JK flip-flop is shown in Figure 5-1. The

state of the flip-flop is defined by its assertion output q at a particular

CPI. The negation output is q (the complement of q).

The logic inputs are J and K. A change in the state of the flip-flop can

only occur after the application of a clock pulse denoted by Cp. The logical

behavior of the JK flip-flop is reflected in the following state table:

J K q Q

0 0 0 1

0 0 1 0

0 1 0 1

0 1 1 1

1 0 0 0

1 0 1 0

1 1 0 0

1 1 1 1

5-1
S-2►. - m0

u4ic►.

astia

.r

.cam

r.iwdAidw

00
J and K represent Present inputs, and q represents there p sent

(assertion) output or state of the flip - flop. Let k denote a CPI, the time

between two consecutive clock pulses. Then,

q(k) ---+ q(k+l) - Q

where Q denotes the state the flip- flop assumes after the application of a

e cloc k pulse. Q is referred to as the next ( assertion) output or state of the

flip- flop. The next state Q is a Boolean function of J, K, and q. Expressed

in minimal ( logical) sum of ( logical) products form

Q - Jg V kq (31)

Juxtaposition denotes the logical product or the AND operation (e.g., K

AND q is expressed as Kq). The symbol V denotes the OR (i.e., Inclusive-OR

operation). A detailed presentation on switching (Boolean) functions and

clocked memory elements appears in Reference 18. The reader is cautioned to

note that the symbols for the OR and Exclusive-OR operations in Reference 18

differ from those in this report. Expression ( 31) is the characteristic

function of the JK fl.ip - flop. It is a Boolean difference equation where time

dependency is implied.

Let J K in (26). Then,

J - K

andQ - KgVKq - K

Thus, when inputs J and K are complementary, the next state Q, after the

application of a clock pulse Cp, is the state-value of K prior to application

of Cp. The assertion output, in effect, "copies" the state - value of K. The

behavior of the JK flip- flop under the condition J equals K is that of a D

flip-flop (i.c., a delay flip-flop). Let q i and q i denote the assertion

and negation output of the i th JK flip-flop in a cascade. Let J i+1 and

K i+l denote the respective inputs to the (i + 1)th JK flip-flop whose

..

5-3
i

assertion output is q i+l . Connecting q i to K i+l and qi to J i+l results in

shifting the content of the i th flip-flop (i.e., q i ) to the (i + 1)th

flip-flop upon the application of a Cp.

The JK flip-flop in Figure 5-1 is comprised of 8 NOR (OR-NOT) gates and

one inverter for developing a two-phase clock. The JK flip-flop is made up of

two clocked cross-coupled NOR gates called latches. One serves as a master

and is clocked by ^l = Cp. The slave is clocked by 402 - Cp (the

complement of Cp). The state of the master is determined by the J and K

inputs when Cp - 0, while the inputs to the slave are disabled Cp 1. 'Lbe

master (clocked latch) assumes a stable state prior to the time Cp becomes 1

as Cp becomes 0. The atate of the slave then assumes the state of the master

during which time the inputs to the master (J and K) are disabled. Feedback

from the assertion output q to the NOR gate, which has J and Cp as other

inputs and feedback from the negation output q to the NOR gate, which has K

and Cp as other inputs provide input gate steering. Gate steering allows a

state-value of 0 to'simultaneously be applied to the J and K input. , The J

input when at state-value 0 (and K - 1) is a set input which causes the

assertion output q to assume a state-value of 1 (via the slave). Whereas, the

K input when at state-value 0 (and J - 1) is a clear (or reset) input which

causes the assertion output, q, to assume a state-value of 0 ( v ia the slave).

When J and K are both at state-value 0, the state of the JK flip-flop

changes. From (26)

Q - JgVKq

-OgVOq q

Thus, J - K - 0 is a toggle input which is not employed in a shift register

configuration. A J - K - 1 cause no change in q. A condensed state table of

a O-enable JK flip-flop is listed as follows:

5-4
0 0 `q

0 1 1

1 0 0

1 1 q

The second and third entries where J and K are complementary correspond

to D flip-flop behavior where Q copies the K input. 

SDC; 

and 

RDC 

in

Figure 5-1 are asynch r onous set and clear inputs, respectively. 

SDC 

when at

state-value 1 sets the flip-flop, and 

RDC when at state-value 1 resets the

flip-flop.

SDCRDC 0

is a constraint. That is, a state -value of 1 should not be applied to SDC

and RDC simultaneously since q will assume an indeterminate state-value

(i.e., 0, a 0 or a 1). Both S DC and RDC override the clocked logical

inputs J and K. The S DC and RDC inputs with added control logic provide a

means for on-chip initia)ization of each flip-flop.

Another configuration of the 0 enable JK flip-flop where J - K - T is of

interest. From (25)

Q-Tq`VTq $ T +q

t.

- 1 + T + q (32)

The next state Q is the complement of the Exclusive-OR of the T input and

the present state q of the flip - flop. Connecting J and K inputs together

results in a trigger or T flip-flop whose characteristic function is linear.

In a subsequent report, it will be shown that the feedback of an SSFSR

characterized by a trinominal may be reluced to a wire when the register

5-5

F I ^ 6^' 
portion is made up of a combination of D and T flip-flops. The conditions

under which the properties and the length of a given periodic sequence is

preserved will be discussed.

An N channel Metal-Oxide-Semiconductor (NMOS) circuit of the 0-enable JK

flip-flop appears in Figure 5-2. Each transistor is an N channel

Metal-Oxide-Semiconductor Field-Effect Transistor (MOSFET). Those operating

in the depletion mode serve as pull-ups and are labeled MD. Those operating

in the enhancement mode are served as pull-downs and are labeled ME. The

optimal length-to-width ratios of the gate geometries are discussed in

Reference 19. The NOR gate configuration was chosen because its delay time

for falling transitions is decreased as more or its inputs are active. Added

stray capactance does, however, offset this decrease.

A functional logic diagram of an on-stage SSFSR characterized by

I i

T(X)=Xn+Xa+1 n,a

is given in Figure 5-3. Clock and initialization circuitry is omitted. The

two-level logic function comprised of three NOR gates is effectively a 2-input

Exclusive-OR circuit. Thirty transistors comprise the NMOS cell (i.e., JK

flip-flop) in Figure 5-2. Intrrcell connections are highly localized.

Whereas, intercell connections are simply two wires due to the fact that the

shift register is a serial device. The celluarity of a shift register and the

serialization of intercell connections leads to topological regularity

amenable to VLSI chip designs.

Introducing feedback to the shift register enchances its usefulness

beyond all expectations of the early 1950s when independent discoveries were

surfacing (Reference 3). The combinational logic in feedback of a shift

register, however, adversely affects the topological layout of a VLSI design.

This is particularly true in a SSFSR where a two-level linear-logic function

grows sharply with the number of arguments (Reference 18). A feedback network

with a single 2-input modulo 2 summer (i.e., Exclusive-OR gate) is the least

5-6

Z' 
5-7

,IM

a. 0

..-r W1

0.

UWW

r/./^

.0

Ir WuLm

41 W

tv w0L.4avH

.r4 u

U)OzNNH7

00

F*.

(ma

I< ^ o 0 0

a o o - -

a m

a

o ^ ^a

aWWVI

W 00 H

ow`

ow

W

0 r

O W Z

0 

v

J 

azW

< Wec

S C
IY

CC

IT cr

Itr

II

cr

II

c

II

c

cr IcmxGX

OJ N

•.aN

QI uU

^n

c^ tU

0GW

CA

0l

00

cc

^J

fnIGWO8

C0

$4

00

co

.4Au

00OacOLuC7Wd

,41

Qj H

00 W

c

cc

V

-^

Y

O

C'O

V^

C

IIC

cr I^

I

-^c

c

I II T 1 j

C

TT ^"

Z0

QH

^CW

a.O

ocO1 W

t/'f JUxWWF—

l/'1

I^FZW0tJOaoW

5-8
complex without resulting in cycles (of states) of trivial length. Isomorphic

SSFSR and ISFSR with such a feedback function are of identical complexity in

terms of transistor count and propagation delay.

This report discusses the embedding of the behavior of an r-stage shift

register with linear-logic feedback into that of an n-stage shift register

with a single 2-input modulo summer in its feedback in Section IV. The sole

purpose is to realize VLSI architecture of maximal regularity (i.e., identical

cells) with intercell communications serialized to a maximal dam.

5-9
SECTION VI

SUMMARY

Feedback shift registers have proven to be efficient periodic binary

sequence generators. Polynomials of degree r over a Galois Field

characteristic 2 (GF(2)) characterize the behavior of shift registers with

linear-logic feedback. Such FSRs are amenable to analysis and synthesis.

Furthermore, the synthesis of shift registers with nonlinear feedback is often

the result of "adding" nonlinear terms to a linear recurrence relation. See'

Reference 23 and Chapter VI entitled "Nonlinear Shift Register Sequences" in

Reference 3.

Application of periodic binary sequences include random number generation

(Reference 15), spread spectrum communications (Reference 20), and radar

ranging (a forerunner of spread spectrum communications (Reference 11)), and

VLSI testing (References 21 and 22).

Other applications of FSRs include encryption and decryption

(Reference 23), algebraic error-detection and error-correction encoding and

decoding (References 4 and 6), and FSR synthesis of sequential machines

(Reference 24).

The vast intrinsic combinatorics of an FSR accounts for its varied and

significant applications. This reports deals solely with shift registers with

linear-logic feedback (the SSFSR and ISFSR) characterized by polynominals over

GF(2). The objective is the algorithmic determination of the trinomial of

lowest degree, when its exists, that contains a given irreducible polynomial

over GF(2) as a factor. It was proven that every primitive polynomial of

degree r is a factor of 2 r-1 - 1 trinomials and the one of lowest degree is

square-free. A sufficient, but not a necessary condition, was proven for a

nonprimitive irreducible polynomial to be a factor of a trinomial. Methods

for determining the initial state of a SSFSR and ISFSR required to generate

the periodic sequence associated with a factor of the trinomial was given.

6-1
A measure of complexity of a binary periodic sequence is the length of

the shift register with linear-logic feedback which, when properly

initialized, can generate the sequence (see References 4 and 25). It is

proposed that a measure of complexity of an irreducible polynomial is the

degree of the trinomial of least degree, if it exists, that contains the

irreducible polynomial as a factor.

6-2

__,_ _-_ _ - _r ___ 
7-1

SECTION VII

REFERENCES

1. Birkoff, G., and MacLane, S., A Survey of Modern Algebra, Revised

Edition, The Macmillan Co., New York, 1953.

2. Golomb, S.W., "Theory of Transformation Groups of Polynomials over GF(2)

with Applications to Linear Shift Register Sequences," Information

Sciences, Vol. 1, pp. 87-109, 1968.

3. Golomb, S.W., Shift Register Sequences, Revised Edition, Aegean Park

Press, Laguna Hills, California, 1982.

4. Berlekamp, E.R., Algebraic Coding Theory, Revised 1984 Edition, Aegean

Park Press, Laguna Hills, California, 1984.

5. Dean, R.A., Elements of Abstract Algebra, John Wiley and Sons, Inc., 

New York, 1966.

6. Peterson, W.W., and Weldon, Jr., E.J., Error-Correcting Codes,

2nd Edition, The M.I.T. Press, Cambridge, Massachusetts, 1972.

7. Marsh, R.W., Table of Irreducible Polynomials over GF(2) through

Degree 19, distributed by the Office of Technical Services, Commerce

Department, Washington, D.C., October 1957.

8. Stahnke, W., "Primitive Binary Polynomials," Mathematics of Computation,

Vol. 27, No. 124, pp. 997-980, October 1973.

9. Watson, E.J., "Primitive Polynomials (Mod 2)," Mathematics of

Computation, Volume 16, pp. 368-369, 1962.
10. Lempel, A., "Analysis and Synthesis of Polynomials and Sequences over

GF(2)," IEEE Transactions on Information Theory, Vol. IT-17, pp. 297-303,

1971.

11. Golomb, S.W., Editor, Digital Communications with Space Applications,

Prentice Hall, Englewood Cliffs, New Jersey, 1964, Second Edition,

Peninsula Publishing, Los Altos, California, 1982.

12. Zierler, N. and Brillhart, J., "On Primitive Trinomials (Mod 2),"

Information and Control, Vol. 13, No.6, pp. 541-554, December, 1968.

13. Zierler, N., and Brillhart, J., "On Primitive Trinomials, (Mod 2) II,"

Information and Control, Vol. 14, No. 6, pp. 556-569, June 1969.

14. Swan, R.G., "Factorization of Polynomials over Finite Fields," Pacific

Journal of Mathematics, Vol. 12, pp. 1099-1106, 1962.

15. Tausworthe, R.C., "Random Numbers Generated by Linear Recurrence Modulo

Two," Mathematics of Computation, Vol. 19, pp. 201-209, 1965.

16. Feller, W., An Introduction to Probability Theory and Its Applications,

Vol. 1, Third Edition, John Wiley and Sons, Inc., New York, 1968.

17. Golomb, S.W., "Irreducible Polynomials, Synchronization Codes, Primitive

Necklaces, and the Cyclotomic Algebra," Combinatorial Mathematics and Its

Applications, Chapter 21, Proc. of the 1st U.N.C. Conference Conf. on

Combinatorial Mathematics and Its Applications., April, 1967, University

of North Carolina Press, pp. 358-370, 1969.

18. Perlman, M., "Abstract Algebra," Encyclopedia of Computer Science and

Technology, Marcel Dekker, Inc., New York, Vol. 1, pp. 1-102, 1975.

19. Mead, C., and Conway, L., Introduction to VLSI Systems, Addison-Wesley

Publishing Co., Reading, Massachusetts, 1980.

7-2
20. Holmes, J.K., Coherent Spread Spectrum Communications Systems, John Wiley

and Sons, Inc., New York, 1982.

21. Williams, T.W. and Parker, K.P., "Design for Testability - A Survey,"

Special Issue on VLSI Design: Problems and Tools, Proceedings of the

IEEE, Vol. 7, No. 1, pp. 98-112, January 1983.

22. Tang, D.T., and Chen, C.-L., "Logic Test Pattern Generation Using Linear

Codes," IEEE Transactions on Computers, Vol. C-33, No. 9, pp. 845-850,

September 1984.

23. Perlman, M., "Generation of Key in Cryptographic System for Secure

Communications," NASA Technical Brief No. B75-10278, October 1975.

24. Martin, R.L., Studies in Feedback Shift-Register Synthesis of Sequential

Machines, Research Monograph No. 50, The M.I.T. Press Cambridge,

Massachusetts, 1969.

25. Massey, J.L , "Shift Register Synthesis and BCH Decoding," IEEE

Transactions on Information Theory, IT15, pp. 122-127, 1969.

7-3
APPENDIX A

NUMBER, THEORETIC FUNCTIONS
APPENDIX A

NUMBER-THEORETIC FUNCTIONS

W , 5^

A number-theoretic function is any function that is defined over

f positive integral arguments. A number-theoretic function f(m) is

multiplicative if

f(ab) - f(a)f(b) whenever (a,b) - 1

The prime-power factorization of a positive integer m > 1 is

k

j^ e i

m

1 pi

i =111

f'.

where k and e are positive integers and p i prime integers. A prime is

defined as an integer p > 1 that is divisible by 1 and p only. Thus, a

multiplicative number-theoretic .unction over m may be expressed as

Hk e.k e

f(m) - f pii s H f pii

i = 1 i=1

since

i

e e

p i , p j i - 1 for i 0 j

The Euler-phi function cp(m) is defined as the number of positive

integers no greater than m that are relatively prime to m. Furthermore, cy(m)

A-1
is multiplicative. The integers no greater than p that are not relatively

prime to p are those that contain p as a factor, namely,

p . 2p j ...

opk-lp

There are a total of pk-1 such integers. Therefore,

^

P(pk ) = pk - pk-1 = pk- 1(p-1)

The integer 1 is neither a prime nor a composite. To be complete, v(1) is

defined to be 1.

In general,

1

p - 1

cP(m)

k e.-1

H Pi i (pi-1)

i=

form= 1

for m=p

k

e.

i

for m = pi

i=1

As discussed in Section I, the number of primitive polynomials of degree

r over GF(2) is

^P(2r - 1)/r

Also, the number of irreducible nonprimitive polynomials of degree r and

period d over GF(2) is ^p(d)/r. The value of d is such that d < 2k-1 and d

divides 2 k - 1 for k = c, but does not divide 2 k - 1 for k < r.

The set of all cosecs ( proper and improper) relative to the

multiplicative st..ibgroup

11, 2, 4, ..., 2 r-1 1J

A-2
correspond to the 2 r - 1 roots of unity arranged into cyclotomic cosets.

The number of cyclotomic cosets is

Nc - r 11: '0(d) 2r/d _ 1

Ldir

where djr denotes "d divides r." The summation is taken over all d > 1 that

divide r.

Another multiplicative number-theoretic function of interest is the

Mbbius function denoted by μ(m). The Mbbius function is defined by

1 ifm-1

μ(m) = 0 if a2 ) m for a > 1

(-1) k

if m = pl p2 ... Pk where p i are distinct primes

The Mbbius function shows u fr P

equently in number theo 9 Y ry, Y Pparticularly in the Y

Mbbius inversion formula. If f is any number-theoretic function, not

necessarily multiplicative, and

F(m) _ ^f(d)

dim

then

f(m) _ EF(d);L(n/d) _ ^F(n/d),^L(d)

di,n dim

The number of irreducible polynomials of degree r over GF(2) is I where

2 r = Ed Id

der

For r - 6, I 6 is determined recursively. Divisors of 6 are 1, 2, 3, and 6.

A-3
2 1 = 1 • I l

II 2

2 2= 2+2I2

12= 1

2 3= 2+313

I3=2

26= 2+2+6+616

I6=9

A closed form for I follows from applying the Mobius inversion formulas.

For

F(r) = 2 r and f(d) dId

rIr = E2r/ μ(d) and Ir = = E2r/d(d)

djrr djr

For r=6,

u(1) = 1, μ(2) _ -1, μ(3) _ -1, 4 (6) -1

I6 1 ( 26 - 2 3 - 2 2 + 21 = 9

The number-theoretic functions for determining the number of primitive

and irreducible polynomials over GF(2) is applicable to GF(p). The number of

primitive polynomials of degree r is a subset of I over GF(p). That is,

,,(p r - 1) < 1 Fpr/ ^(d)

r r y

der

Equality arises only for the case of GF(2) when 2 r - 1 is prime. The reader

iR invited to see References 3, 4, and 17 for detailed presentations on <p(m),

μ(d), and the Mobius inversion fo^mula.

A-4
:t

APPENDIX B

TRINOMIAL OF LEAST DEGREE THAT CONTAINS

A GIVEN PRIMITIVE POLYNOMIAL OF DEGREE

r OVER GF(2) AS A FACTOR
APPENDIX B

TRINOMIAL OF LEAST DEGREE THAT CONTAINS A GIVEN PRIMITIVE

POLYNOMIAL OF DEGREE r OVER GF(2) AS A FACTOR

COEFF. OF IRREDUCIBLE

r f(:) IN TW FACTORS OF T(:) DEGREE

OCTAL n a IN OCTAL OF FACTOR PERIOD INDEX

!a 1 2 41 1 11 1

7 2 7 2 3 1

!a 1 11 1

8 3 13 3 7 1

Ste, ¢ ,,,1 3 1

6 ^ ¢ 1 ^ ¢ ¢^ 1

} 8 7 7 2 3 1

1 33 6 61 1

X41 11 8 73 5 31 1

147 6 1

Z 30 1 1 203 Z 131 1

311 Z 3 311 1 112 1

2335 10 9 15 3 7 1

3u 1 127 1

377 13 3 133 6 63 1

277 1 127 1

247 14 13 7 2 3 1

45 5 31 1

347 Z 1__.Z 1

2 19 7 m Z 11Z 1

12067 • 12 4095 1

2^Z 19 13 al 1 127 1

10663 • 12 4095 1

1^1 19 17 7 2 3 1

m 1 m 1

2035 • 10 341 3

B-1
ODEFF. OF IRREDUCIBLE

r f(z) IN T( z) FACTORS OF T(z) DEGREE

OCTAL n a IN OCTAL OF FACTOR PERIOD INDEX

Z 1 21 18 Z 11r1 1

72127 • 14 381 43

$ 13 11 7 2 3 1

15 3 7 1

"Z $ 111 1

13 12 67 5 31 1

8

tu 16 15 W $ 1

675 0 8 85 3

543 20 9 13 3 7 1

m $ m 1

1055 • 9 0911 1

21 10 4u $. m 1

• 21615• 13 8191 1

_ 23 1 7 2 3 1

1u $ 1 1

34641 0 13 8191 1

7 17 27 2 13 3 7 1

ZlZ $ ^ 1 

375715 • 16 65535 1

27 8 $S 1

3745133 • 19 524287 1

Q 1021 1021 , 1

1533 11 7 7 2 3 1

1533 ^ ^1 1

133) 11 10 7 2 3 1

B_2

^^
COEFF. OF IRREDUCIBLE

r f(:) IN T( z) FACTORS OF T(:) DEGREE

OCTAL n a IN OCTAL OF FACTOR PERIOD INDEX

1157 13 6 23 4 15 1

1157 ^ ^

1

1473 15 13 147 6 63 1

1473 t m 1

1207 19 8 7 2 3 1

15 3 7 1

51 5 31 1

1207 Q ^ 1

1175 19 9 1175 511 1

2355 + 10 341 3

1055 20 9 13 3 7 1

S43 • 8 255 1

loss ^ ^ 1

1275 26 1 7 2 3 1

15 3 7 1

121 9- uI 1

125150 12 4095 1

1267 27 15 1267 p- S,_i l 1

1234653 • 18 1533 171

1517 29 4 7 2 3 1

313 7 127 1

1517 1 Ull 1

7723 • 11 2047 1

1437 29 7 7 2 3 1

75 5 31 1

1437 9- 511 1

32461 0 13 8191 1

1137 29 14 1137 4 LU 1

4533443 • 20 349525 1

1033 29 24 13 3 7 1

73 5 31 1

1033 Q. ^, 1

17233 • 12 1365 3

B-3 E .
ODEFF. OF IRREDUCIBLE

f(x) IN T( z) FACTORS OF T(z) DEGREE

OCTAL a a IN OCTAL OF FACTOR PERIOD INDEX

36 1

2257* 10 341 3

540663 • 17 131071 1

1 1 31 36 19 is 3 7 1

9- ul I

171611245 • 24 16777215 1

1225 39 16

7137• 11 2047 1

3411757 • 19 524287 1

1617 39 18

10011 12 45 91

1540753* 18 1533 171

116 7 41 33 325 7 127 2

1 1 6 7 Q 5 11

373334507 • 25 33554431 1

1423 44 41 13 3 7 1

31 4 15 1

1423 2- 1

3323 10 1023 2

1635423 • 18 262143 1

1217 45 20 Im 511 1

1205764323423 • 36 2555 26896077

im 55 50 7 2 3 1

23 4 15 1

31 4 15 1

1577 2- 511 1

1627006717343 • 36 2555 26896077

1217 37 49 1317 Q Mi 1

13555371 • 21

1004427273 • 27

1063 61 39 13 33 7 1

1063 i 511 1

11643 12 4095 1

2541445310153 0 37

B-4 
COEFF. OF IRREDUCIBLE

f(x) IN T(z) FACTORS OF T(x) DEGREE

OCTAL n a IN OCTAL OF FACTOR PERIOD IND

^Q 2011 14 3

13 9 13 3 7 

2627

2327 14 3 23 4 15 

im 10 1023 

947 5 17 8 13 3 7 

23 4 15 

2475 10 1023 

2617 17 13 7 2 3 

75 5 31 

10 1023

2157 23 7 7 2 3

2157 10 10 23 

6435 0 11 2047 

3 133 23 8 141 6 63 

247 7 127 

24 11 2767 101 1023 

55753 • 14 16683 

2773 26 3 75 5 31 

2773 IQ 1023 

7173 • 11 2047 

2707 32 31 7 2 3 

2707 10 1023 

3067 • 10 1023 

3607 • 10 341 

32 31 7 2 3 

2707 • 10 1023 

1-0 Im 

3607 • 10 341 

B-5
B-6

ODEFF. OF IRREDUCIBLE

r f W IN T(:) FACTORS OF T(s) DEGREE

OCTAL a a IN OCTAL OF FACTOR PERIOD INDEX

Iq 2347 35 22 7 2 3 1

141 6 63 1

2347 L4 LM 1

430005 • 17 131071 1

2443 37 18 243 iQ 1023 1

1272414137 • 27

2033 39 37 23 4 15 1

1321 9 511 1

1023 1

210435 • 16 65535 1

2213 40 11 7 2 3 1

13 3 7 1

2213 IQ 1023 1

347702607 0 25 33544431 1

2415 49 24 455 8 255 1

LIU 10 1023

27371170361 • 31 2147483647 1

2047 49 36 211 7 127 1

2047 10— ^ l

43207520343 • 32

2503 49 45 57 5 31 1

1151 9 511 1

2503 10 1023 1

4445 • 11 2047 1

46215 • 14 16383 1

3177 51 41 13 3 7 1

3177 10 1023 1

317313 16 21845 3

23644577 22

2305 53 28 7 2 3 1

23 05 lk 1023 1:

73707 • 14 16383 1

1321420701•27
ODEFF. OF IRREDUCIBLE

r f(:) IN T(s) FACTORS OF T(:) DEGREE

OCTAL n a IN OCTAL OF FACTOR PERIOD INDEX

1Q 3427 55 14 7 2 3 1

3427 1Q 1023 1

241461026171065 • 43

s

toss 55 28 2055 1Q 1023 1

15317555 0 21 2097152 1

164050421 0 24

57 30 1033 9 511 1

2527 l4 IO23 I

3465 0 10 341 3

3507 10 1023 1

1022707 • 18 1533 171

2553 57 51 111 6 9 7

235 7 127 1

2553 ik 1

3301 10 1023 1

3367 10 341 3

43445 • 14 381 43

_ 3023 60 41 15 3 7 1

1023 1 

544450717756184 3 • 47

2363 61 9 1207 9 511 1

_ 2623 IQ 1023 1 

53 623 0 14 16383 1

2310747647 0 28

2377 65 6 13 3 7 1

2377 10 1023 1

6227 0 11 2047 1

60575 • 14 16383 1

1062067767 4 27

2145 65 34 7 2 3 1

13 3 1

2145 lQ 1023 1

E 2605 10 1023 1

3573 10 341 3

111041 • 15 1057 31

F 135407• 15 1057 31

r ?

Yom`

t

B-7
B-8

i

f OF T(z)

r INDEX 1 n a

10 3337 79 73

F 3117 83 14

t

s

t COEFF. OF IRREDUCIBLE

r f(z) IN T(z) FACTORS OF T(z) DEGREE

OCTAL n a IN OCTAL OF FACTOR PERIOD INDEX

11 x}05 U 2 4005 11 2047 I

MI 13 5 7 2 3 1

on 11 1241 2

4S6S 16 9 45 S 31 1

IM 11 2041 1

323 20 7 7 2 7 1

357 7 127 1

SZ3S ^ 2047 1

22 13 31 4 15 1

325 7 127 1

#67S 11 2047 1

5613 23 16 7 2 3 1

3661 • 10 102.4 1

5¢13 ^ 1^4Z 1

3337 24 5 3337 2047

24703 0 13 8191 1

4237 25 24 163 6 63 1

561 8 255 1

Am 2041

26 5 4261 a 2047 1

105621 0 15 32767 1

6747 26 23 57 5 31 1

3375* 10 1023 1

fm 11 2047 1
OOEFF. OF IRREDUCIBLE

r f (x) IN T(:) FACTORS OF TU) DEGREE

OCTAL n a IN OCTAL OF FACTOR PERIOD INDEX

b27T 29 25 7 2 3 1

323 7 127 1

1713 • 9 511 1

6277 u 2047 l

4671 30 7 4671 11 2047 1

2313171 0 19 524287 1

¢54Z 31 20 7 2 3 1

11 Lm 1

1147625 • is 262143 1

5025 32 17 5025 11 2047 1

12575505 0 21 2097151 1

3733 33 14 23 4 15 1

5733 u 2047 1

1255515• 18 37449 7

5253 33 27 5253 11 2047 1

24246667 • 22 6141 683

4653 37 12 4653 lu z047 1

460401267 • 26

5373 37 33 163 6 63 1

217 7 127 1

SST u 2047 1

35147 • 13 8191 1

5575 38 3 235 7 127 1

455 8 255 1

5575 u 2047 1

13245 0 12 4095 1

7137 39 16 12250 9 511 1

7137 11 2_047 1

3411757 • 19 524287 1

B-9
WEFF. OF IRREDUCIBLE

r f(:) IN TU) FACTORS OF T(s) DEGREE

OCTAL a a IN OCTAL OF FACTOR PERIOD INDE

11 X77 39 19 13 3 7 

51 5 31 

247 7 127 

5477 11 2047 

20213 • 13 8191 

S6S7 39 24 111 6 9 

5657 11 1047 

24546213 + 22 6141 68

soo7 39 28 67 5 31 

2m 11 1047 

64425725 0 23 8388607 

41 5 551 8 255 

Im 11 2047 

24577263 • 22 4194303 

43 6 23 4 15 

155 6 63 

6013 U 2047 

24064321 • 22 60787 

4225 43 it 7 2 7 

75 5 31 

!UU 11 Un 

260330363 • 25 33554431 

6447 43 15 1207 9 511 

3417 10 341 

64.42 11 2047 

24637 4 13 8191 

4423 47 it 13 3 7 

412A 11 2047 

126643071475* 33

lam 47 39 13 3 7 

31 4 15 

1725 9 511 

Na 11 2047 

4772121 0 20 1048575 

'i-10
CDEFF. OF I:RREDUCIHLE

r f W IN T(:) FACTORS OF T(:) DEGREE

OCTAL a a IN OCTAL OF FACTOR PERIOD INDEX

IL 41u 48 21 67 5 31 1

3453 10 93 11

I u 2047 1

34424513 0 22 6141 683

557 48 29 23 4 15 1

155 6 63 1

5357 u 2047 1

1456104075 • 27

4365 49 17 ! 2 3 1

51 5 31 1

4m a 2047 1

12165 12 4095 1

3321023 • 19 524287 1

6307 4 30 67 5 31 1

613 8 85 3

765 8 255 1

UL1 a 2047 1

542667 • 17 131017 1

4505 49 39 4505 2047 1

117767 0 15 4681 7

42000367 0 23 8338607 1

4445 49 45 57 S 31 1

1151 9 511 1

2503' 10 1023 1

4441 11 2047 1

46215 0 14 16383 1

6557 53 17 23 4 15 1

§1 u zm 1

12727 0 12 4095 1

615627213 • 26

4107 54 25 13 3 7 1

2047 10 1023 1

4141 11 2047 1

51303 • 14 16383 1

232031 0 16 13107 5

B-11
ODEFF. OF IRREDUCIBLE

r f(:) IN T(:) FACTORS OF T(:) DEGREE

OCTAL a a IN OCTAL OF FACTOR PERIOD INDEX

u SSS7 55 10 LL 2047 1

577532413432723 • 44

4475 56 41 37 5 31 1

1725 3 511 1

44U u 2m 1

37157355273 0 31 2147483647 1

4347 51 11 • 23 4 13 1

4,^4Z 11 Z9^Z 1

112443714550031 0 42

r

7237 58 55 13 3 7 1

E 7237 u 2w 1

731154217564031• 44

Z 59 25 7 2 3 1

}_ 4317 11 1^Z 1

11103 • 12 1363 3

31200443 0753 • 34

59 29 13 3 7 1

AM 11 am 1

26761 0 13 8191 1

40561341405 0 32

4603 61 43 is 3 7 1

73 5 31 1

1563 9 511 1

4603 11 am 1

75273 0 14 16383 1

2041035 • 19 524287 1

^uZ 64 47 7 2 3 1

15 3 7 1

im 11 2047 1

17141473700110531 • 48

65 6 13 3 7 1

2377 0 10 1023 1

6227 u ;047 1

60575 0 14 16383 1

1062067767 • 27

4

ra

B-12
CDEFF. OF IRREDUCIBLE

f (z) IN Vx) FACrORS OF ME) DEGREE

OCrAL a a IN OCUL OF FACrOR PERIOD INDEX

65 7 7 2 3 2

771 8 85 3

cul u LQ41 1

514561* 17 131071 1

11OIA74323 0 27

65 28 7 2 3 1

4563 U

307036250332270-0 3 1* 52

65 40 7 2 3 1

23 4 is 1

31 4 is

lw u

404454203214625 0 44,

68 3

4520750 17 131071 1

225402401002 53 0 40

68 55 7 2 3 1

LM u

3751431316172617015 0 55

69 21 ill 6 9 7

Im 111 D-41 1.

20342647 0 22

10001101111 0 30

6') 41 271 7 127 1

Am u 2047 1

4361545 0 20 1

2662 2761641 0 31 2147483647

IF f

M .

f (1) of

INDEX I a a

f (1) of

r INDEX 1 n a

4055 71 14 11 5601 93 14

4173 71 47 5177 93 61

4415 72 56 6417 94 93

7047 71 68 5263 96 61

B-13
WEFF. OF IRREDUCIBLE

r f(1) IN T(1) FACTORS OF T(1) DEGREE

OCTAL a a IN OCTAL OF FACTOR PERIOD INDEX

12 12067 19 7 253* 7 127 1

12067 12 4095 1

10663 19 13 217* 7 127 1

10663 12 4095 1

12753 25 21 45 5 31 1

573 8 85 3

12753 12 4095 1

12515 26 1 7 2 3 1

15 3 7 1

1275* 9 511 1

1 2515 12 4095 1

_1 0353 31 29 7 2 3 1

13 3 7 1

10353 12 4095 1

60147* 14 16383 1

10175 34 S 7 2 3 1

51 S 31 1

10175 12 405, 1

163767* 15 32767 1

f(1) of f(1) of

r INDEX 1 a a r INDEX 1 a a

11 4251 72 15 11 4655 97 90

6153 73 17 6037 99 62

4451 73 34 4027 100 35

6163 73 40 5403 101 79

5155 75 72 4577 101 82

4617 79 39 5247 103 18

6507 79 61 6637 107 85

5747 81 38 5623 109 1

7317 82 17 4143 109 27

5265 82 23 4707 111 106

4533 86 9 5463 117 25

5513 88 75 6263 133 39

4745 89 87 6233 142 99

5667 143 12
COEFF. OF IRREDUCIBLE

r f(z) IN T(z) FACTORS OF T(z) DEGREE

OQ'AL a a IN OCTAL OF FACTOR PERIOD INDEX

12 12117 37 3 15 3 7 1

345 7 127 1

12117 12 4095 1

120403 + 15 32767 1

12165 37 30 12165 12 4095 1

250303445 + 25 33554431 1

12255 38 35 271 7 127 1

- 551 8 255 1

S75S • 11 2047 1

12255 12 4095 1

111 42 17 11177 12 4095 1

11066515603 + 30

10737 47 13 7 2 3 1

10737 12 4095 1

151421301615+ 33

11643 49 18 31 4 15 1

1713 9 511 1

7113 11 2047 1

11643 12 4095 1

31273 + 13 8191 1

11313 50 9

11313 12 4095 1

4502237720127* 38

- 11163 53 16 7 2 3 1

73 5 31 1

11163 12 4095 1

277357101057 + 34

12727 53 17 23 4 15 1

6557 + 11 2047 1

12722 12 4095 1

615627213 + 26

16311 55 1 357 7 127 1

16317 12 4095 1

f

1264522723457+ 36

B--15
ODEFF. OF IRREDU CIBLE

r f(z) IN T(x) FACTORS OF T(i) DEGREE

OCTAL u a IN OCTAL OF FACTOR PERIOD INDEX

12 11015 55 8 7 2 3 1

235 7 127 1

11015 U 4091 1

53043 14 5461 3

7054651 • 20 95325 11

19731 59 49 10731 a 4095 1

2161250565777231 • 46

11147 60 25 11147 12 4095 1

13223 12 819 5

13611 • 12 4095 1

14227 0 12 4095 1

16273 • 12 4095 1

14227 60 25 111470 12 4095 1

13223 22 819 5

13611 • 12 4095 1

14227 12 4095 1

16273 • 12 4095 1

11075 60 35 11075 12 4095 1

14455 12 819 5

15467 • 12 4095 1

16311 • 12 4095 1

16443 0 12 4095 1

15467 60 35 110750 12 4095 1

14455 12 819 5

15467 1-2 4095

16311 • 12 4095 1

16443 • 12 4095 1

11067 64 1 23 4 15 1

11045 12 1365 3

Ing 12 4-0-K 1

11441 • 12 4095 1

11463 12 819 5

11515* 12 4095 1

B-16
_ CDEFF. OF IRREDUCIBLE

r f(:) IN T(z) FACTORS OF T(z) DEGREE

OCTAL n a IN OCTAL OF FACTOR PERIOD INDEX

12 11515 64 1 23 4 15 1

11045 12 1365 3

11067 • 12 4095 1

11441* 12 4095 1

11463 12 819 5

11515 12 4095 1

- 12007 64 27 12007 12 4095 1

252442144723171333* 52

10231 64 63 31 4 15 1

10231 12 gods. 1

12211 12 1365 3

13131* 12 4095 1

14631 12 819 5

16611* 12 4095 1

10605 67 61 13 3 7 1

10605 12 4095 1

55317733* 23 8388608 1

4017247 741 * 29

F

f(z) of T(:) f(z) of T(z)

r INDEX 1 n a r INDEX 1 n a

12 16027 70 29 12 13275 103 56

15437 71 26 14433 103 57

13677 71 41 10527 104 43

11435 71 52 10123 107 97

17057 72 19 16047 109 76

12247 73 38 11477 109 91

12323 78 53 13503 115 2

12435 79 40 15033 117 80

10173 80 43 14357 119 44

15677 83 19 10407 125 94

14573 83 73 16237 129 48

10443 85 9 10473 135 53

10553 85 67 11271 136 1

14613 86 7 12735 145 108

13663 87 72 12135 7.52 37

14717 87 72 15527 153 75

B-17
f(x) of T(x) f(x) of T(x)

r INDEX 1 n a r INDEX 1 n a

12 10517 91 19 12 13107 161 84

10437 91 64 12147 161 107

11471 93 34 10321 162 151

10151 93 52 14127 163 143

12417 99 93 14747 164 113

15053 101 67 11417 171 42

12623 102 13

FACTOR OF T(x) LISTED ELSEWHERE

f(x) of T(x) COEFF. IN

r INDEX 1 xrf ( 1/ x) n a r OCTAL PERIOD INDEX

25627 35165 1.6 3

t

22637 37151 1$ 1 _ T

21135 27221 1Q 1

s 21615 26161 21 10 1

20547 34641 23 1 $ 515 25,E 1

ik 23737 37371 23 4

24703 30345 5377 2047 1

30057 36403 23 6 $ 113 33 Z

23005 2403.1 23 9 

' 24061 21405 27 1^

25775 27765_ 23 6 1^ii 266745 65535 1 

21453 32461 29 Z 1437 11 1

22075 2 7411 31 4 14 52547 5461 3.

20715 26341 31 3 16 337377 4369 13

24513 32245 31 111 10 3277 341 3

8-18
FACTOR OF T(z) LISTED ELSEWHERE

f(z) of T ( z) ODEFF. IN

r INDEX 1 :r f(1/x) n a r OCTAL PERIOD INDEX

L3 25333 33325 li I 14 60367 16383 1

34627 35147 5373 2047 1

20213 32101 }1 5477 1047 1

24637 37145 43 Ll 1,1 6A42 2047 1

31273 33523 42 1$ 12 11643 3095 1

21557 6661 ^0 31 12 16276 273 15

21755 26761 19 23 11 453 1 1

30357 36703 63 28 12 13377 $19 S

14 66673 63777 16 1

45627 27 351 17 2

SAS 53 65755 24 11 10 2767 102i 1

40275 57201 26 11 9- 1027 X11, i

¢0142 71403 31 29 12 10353 4095 1

42335 1_621 2 32 11 18 1206221 262143 1

6Q367 73603 35 4 13 25333 8191 1

51145 ^ 445 1 35 11 21 12624165 2097151 1

42645 51321 38 11

46215 54231 42 41 10 2503 1023 1

70767 73707 13 21 10 2305 1023 i

51303 60645 5A 21 11 4107 2047 1

53623 62365 61 10 2363 1023 1

67257 75273 61 43 11 4603 2047 1

B-19
FACTOR OF T(z) LISTED ELSEWHA

_ f(1) of T(z) CDEFF. IN

r

i

INDEX i :rf(1/2) a a r OCTAL PERIOD INDE

57503 60575 §,^ ¢ iQ ,, 2377 1023 1

40473 67101 ¢¢ 12 1,2315 Z

iS 100003 140001 Z

100021 100201 u ¢

100201 100401• Z

134567 167235 ^$ ¢

104657 172621 3 

103653 134741 23 $

121563 147305 12

104721 105621 4261 2047 1

163327 165547 31 14

117143 143171 $

153677 176753 33 8

163767 167747 3{ 12 11735

1

113625 124751 11 13 12 2257305 , 5Z4287 1

102643 142641 ¢ 20 7664741, 1048575 1

13 120403 140205 3Z 3 i2 1211 7 4095 1_

145453 51323 3

123453 14 2345 4a 12

e.

123433 154435 45 21

113637 17 1 41 41 12 11 737 1361 1

s

16 263677 375715 2Z 2 $ 73 255 1

B--20
11

11 1352111 262143 1

10 2231 1023 1

10 2257 1023 1

11 6307 2047 1

12 13773 1365 3

11 4053 2047 1

FACTOR OF T(s) LISTED RLSEWRERE

COEFF. IN

r OCf AL PERIOD INDEX

f(:) of T(:)

r INDEX 1 zrf(1/z) u a

if 366745 247555 3i ¢

306313 323143 21 13

210435 270421 223 K

274577 276475 49 13_

17 400011 440001 17 3

400041 410001 17

400101 404001 13 6

§66673 673333 19 3

4,31277 772461 22 3

454765 537151 22 7

443573 675611 23 it

437265 31 2761 28 10

431455 551461 27 3

436407 701361 34

441715 547411 33 $

4 0005 3 500061 33 22

540663 633015 36 1

542667 7 3215 3 49 30

437771 477761 so 17

452075 570271 68 3

It 10 0 01 1004001 18 7

1147625 1247631 31 20

11 27765 un It

16 372705 21845 3

10 3033 1023 1

it 6367 am 1

B-21
FACTOR OF J(z) LISTED ALMINERE

f(z) of T(x) COEFF. IN

INDEX 1 if f (1/ z) n a r OCTAL PERIOD INDE

1044604 1206221 a 11 U 52621 16383

1110535 1352211 V- t 27 547421. 131071

1037433 1543741 U 1 342043, 524287

1443347 1635423 p- LM in I

2713457 3647235 u I

2327423 3107531

2352103 3021271 27 7 8 477 85 3

3322477 3745133 27 8 8 607 255 1

2746112 3221475 28 11

2516543 3065625 V 21 10 2437 3

2313171 2363231 34 4671 2047

B-22 
APPENDIX C

TRINOMIAL OF LEAST DEGREE THAT CONTAINS

A GIVEN IRREDUCIBLE NONPRIMITIVE POLYNOMIAL

OF DEGREE r OVER GF(2) AS A FACTOR
APPENDIX C

TRINOMIAL OF LEAST DEGREE THAT CONTAINS

A GIVEN IRREDUCIBLE NONPRIMITIVE POLYNOMIAL

OF DEGREE r OVER GF(2) AS A FACTOR

COEFF. OF IRREDUCIBLE

r h(:) IN T(:) FACTARS OF T(:) DEGREE

OCTAL a a IN OCTAL OF FACTOR PERIOD INDEX

1$Z 9 6 13 3 7 1

lam. A u Z

$1 11 S 13 3 7 1

iff $ $L Z

16 1 55110 8 253 1

In 27 7 $

2352103 • 19 524287 1

JU 33 18 13 3 7 1

127 6 21 3

561 8 255 1

607 8 255 1

w it a Z

4 34 17 7 2 3 1

a• It 11 It

661 • 8 51 5

637 8 51 5

763 • 8 51 5

in 34 17 7 2 3 1

433* 8 51 5

661 • 8 51 5

.0I $ u I

763 • 8 51 5

t 1 1003 Z ZZ Z

17 10 1 2 3 1

147 6 63 1

1+.4^. Z Z^. Z

C-1
COEFF. OF IRREDUCIBLE

r h(:) IN T(:) FACTORS OF T(:) DEGREE

OcrAL n a IN OaAL OF FACTOR PERIOD INDEX

1113 25 6 1.5 3 7 

3112 ^ ZZ 

36403 0 13 8191 

1027 26 11 13 3 7 

3.41 ^ 7.^. 

57201 • 14 16383 

1Q 3247 is 6 73 S 31 

all 34 u u

2355 19 9 11750 9 511 

23 SS 3^ ^^ 

2035 19 17 7 2 3 

357 0 7 127 

x,413 21 15 57 5 31 

ill 6 9 

MU 14 u u

2251 22 11 7 2 3 

1111 14 it u

3043 0 10 33 3

X41 22 11 7 3 3 

2251• 10 33 3

3043 34 n 1

2065 24 15 13 3 7 

45 5 31 

127 6 21 

MEL 1A 21 u

2633 , 26 9 2633 1Q 341 

272107 • 16 21845 

2437 29 21 1u1 1Q L1 

2516543* 19 524287 

C-2
1

f

f 1

1

ODEFF. OF IRREDUCIBLE

r h(x) IN T(x) FACTORS OF T(x) DEGREE

OCTAL a a IN OCTAL OF FACTOR PERIOD INDEX

^Q 3277 31 21 537 8 255 1

3277 lk 341

32245 0 23 8191 1

3417 32 1 7 2 3 1

Ma L4 m

3435 • 10 1023 1

3543 0 10 1023 1

36 1 12430 9 511 1

2257 ^4 X41 ^

540663 • 17 131071 1

2017 48 23 13 3 7 1

_ 217 7 127 1

2017 l4

2654016113 0 28

2107 55 22 75 5 31 1

3107 IQ

2671 k0 341 3

3255 • 10 341 3

_ 3315 10 341

3367 0 10 341 3

3367 55 22 75 5 31 1

2107 + 10 341 3

2671 i0 341 3

3255 0 10 341 3

3313 10 341 3

3367 I4, 241 1

55 33 57 5 31 1

2355 10 341 3

2633 10 341 3

2w 19- M 3-

3421 0 10 341 3

3573 0 10 341 3

c-3
CDEFF. OF IRREMCME

r h(s) iii T(z) FACTORS OF 7'(:) DEGREE

OCTAL a a IN OCTAL OF FACTOR PERIOD INDEX

^,(► 2547 S? 27 1541 9 311 1

Lul 14 Lu 3

3427 10 1023 1

3525 0 10 1023 1

1616441 0 18 1333 171

^j 68 61 7 2 3 1

l3_ W X41. I

6421727313413061551 • 36

COEFF. OF h;:) TU)

r IN OCTAL PERIOD 24DEX a Y

10 2123

2231

CAEFF. OF

r h(s) IN T(:)

OCTAL a a

341 3

341 3

IRREMCIBLE

FACTORS OF T(:)

IN OCTAL

75

78

DEGREE

Or' FACTOR

62

19

PERIOD INDEX

LZ 10^ 12 3 looil p

10041 12 5 20041 U $^

13627 15 10 13 3 7 1

13627 11 v- 1^Z

1,4537 17 16 7 2 3 1

15 3 7 1

1453 7 M l

1 1637 23 it 51 5 31 1

133 6 63 1

11J.31 u m 1

13617 26 13 7 2 3 1

a^_.M V a M

17075 • 12 39 105

c -4
ODEFF. OF IRREDUCIBLE

h(x) IN T(z) FACTORS OF T(x) DEGREE

OCTAL n a IN OCTAL OF FACTOR PERIOD INDEX

10555 28 21 23 4 15 1

10555 12

11073* 12 105 39

1 1073 28 21 23 4 15 1

10555 0 12 105 39

11073

15457 29 s is 3 7 1

67 5 31 1

1541 0 9 511 1

25457 1365

14373 30 5 133 6 63

14373

15125 0 12 315 13

12513 30 25 iss 6 63 I

12513 22

15743 0 12 315 13

11727 33 31 11727 12 Uff 1

13554513* 21 2097151 1

13003 39 13 15 3 7 1

11721 0 12 91 45

13003 12 RL -41

13173 0 12 91 45

15173 39 13 is 3 7 1

11721 0 12 91 45

13003* 12 91 45

15 173 12 2-1

10571 39 26 13 3 7 7

105 7 1 a- 21 43-

140150 12 91 45

15713* 12 91 45

C-5
OOEFF. OF IRREDUCIBLE

r h(:) IN M) FACTORS OF T(z) DEGREE

OCf AL n a IN OaAL OF FACTOR PERIOD INDE

11105 40 5 7 2 3 

23 4 15 

31 4 15 

147 6 63 

11105 1 m i

16547 0 12 315 1

16327 40 35 7 2 3 

23 4 15 

31 4 15 

163 6 63 

12111 0 12 315 1

16327 a 1

12133 41 10 7 2 3 

12133 12 136

1601624601 0 27

11657 43 16 11657 u 1365 

23757171023 • 31 2147483647 

11045 44 35 221 7 127 

11045 12 1365 

202314645 0 25

13157 46 43 113157 12 ,,_,_ 5 85 

255372610323 • 34

11735 47 41 75 5 31 

163 6 63 

1707 9 511 

11735 12 1365 

174751 • 15 32767 

13773 50 17 13 3 7 

13773 12 1365 

477761* 17 131071 

1151665* 18 87381 

C-6
C-7

ODEFF. OF

r h(:) IN

OCTAL

T(:)

a a

InEDUCIBLE

FACTORS OF T(:)

IN OCTAL

DEGREE

OF FACTOR PERIOD INDEX

16267 50 31 7 2 3 1

13 3 7 1

16267 11 37

36661• 13 8191 1

6435053 0 20

11463 51 3 15 3 7 1

11463 U 1365

144SS • 12 819 S

17235 12 1365 3

17403 • 12 819 5

13223 51 48 13 3 7 1

111 6 9 7

127 6 21 3

13223 12 819 1

14037* 12 819 S

14631 0 12 819 5

14037 51 48 13 3 7 1

111 6 9 7

127 6 21 3

13223 • 12 819 S

14037 12 m I

14631 • 12 819 5

13143 51 49 313 7 127 1

13143 12

73716032155 • 32

10065 52 13 31 4 15 1

10065 U 195

15347 0 12 195 21

16701 0 12 195 21

17277 0 12 195 21

15347 52 13 31 4 15 1

1065 • 12 195 21

15347 12 LK U

16701 • 12 195 21

17277 0 12 195 21
r- -

ODEFF. OF

r h(:) IN

OCTAL

T(z)

n a

IRREDUCIBLE

FACTORS OF T(:)

IN OCTAL

DEGREE

OF FACTOR PERIOD INDEX

17277 52 13 31 4 15 1

10065 • 12 195 21

15347 • 12 195 21

16701• 12 195 21

17277 12 195 11

10167 52 39 23 4 15 1

10167 12 m

12601 • 12 195 21

16353 • 12 195 21

17657 • 12 195 21

10027 55 15 45 5 31 1

141 6 63 1

10027 12 115 13

17513 • 12 315 13

4454725 20 155 6765

15137 SS 40 51 5 31 1

103 6 63 1

15137 u 115 1$

16401 • 12 315 13

5271511 20 155 6765

16457 56 33 -357 7 127 1

16457 u 1365 1

2543750 16 4369 15

10416231 • 21

16017 57 14 16017 122 1365 3

1212717 • 18 87381 3

1601251105 ► 27

12673 59 17 12673 Z

5162322607102347 • 47

11103 59 25 7 2 3 1

43170 11 2047 1

11103 U 13 3

312004430753 • 34

C-8

Al

7 3 -r;w+
ODEFF. OF IRREDUCIBLE

r h(z) IN T(x) FACTORS OF T(z) DEGREE

OCTAL n a IN OCTAL OF FACTOR PERIOD INDEX

12 13377 63 38 13377 a $19 I

36703 0 13 8191 1

7210220000101 0 38

12315 66 37 15 3 7 1

765 8 235 1

1715 9 511 1

12315 12 585 Z

67101 • 14 16383 1

5267531 0 20

10312 67 20 7 2 3 1

15 3 7 1

10317 12 2

42527114525216661 0 50

COEFF OF h(i) T(z)

r IN OCTAL PERIOD INDEX n a

12 10467 819 5 70 3

13475 1365 3 76 69

10377 117 35 78 39

13413 117 35 78 39

16757 117 35 78 39

10063 819 5 78 65

10115 819 5 78 65

10243 819 5 78 65

11031 819 5 78 65

11673 819 5 82 33

10461 273 15 82 53

13077 273 15 83 46

13113 585 7 83 69

12265 1365 3 85 5

13033 1365 3 85 5

14667 1365 3 85 35

12153 585 7 89 21

12177 819 5 92 57

13563 585 7 93 61

10743 273 15 97 11

13303 819 5 97 69

11763 1365 3 99 29

C-9
C-10

CDEFF OF h(:) T(:) 

' 3 r IN OCTAL PERIOD INDEX n a 

12 11545 1365 3 102 53

13347 819 S 104 13

t 14 513 819 S 104 13

11265 819 S 107 14

_ 14177 585 7 107 96

13363 1365 3 109 81

11433 585 7 116 83

10245 585 7 118 87

14007 1365 3 122 35

13737 1365 3 125 103

13527 1365 3 126 115

10653 819 S 139 133

10077 1365 3 145 123

10355 1365 3 146 61

14043 585 7 156 39

10757 1365 3 160 109

10603 45S 9 195 65

11703 455 9 195 65

11765 455 9 195 65

12023 455 9 195 65

15617 455 9 195 65

10213 455 9 195 130

11023 455 9 195 130

12337 455 9 195 130

13517 455 9 195 130

14313 455 9 195 130

14557 455 9 195 130 

16137 455 9 195 130

14067 1365 3 217 201