06576-4T TECHNICAL REPORT NO. 165 STUDY OF LINEAR SEQUENCE GENERATORS by: C. C. Hoopes R. N. Randall Approved by:eT. G. Birdsall for COOLEY ELECTRONICS LABORATORY Department of Electrical Engineering The University of Michigan Ann Arbor, Michigan Contract No. DA-28-043 AMC-00Q080(E) U. S. Army Electronics Materiej Agency Fort Monmouth, New Jersey June 1966 DISTRIBUTION STATEMENT This document is subject to special export controls and each transmittal to foreign governments or foreign nationals may be made only with prior approval of CG, U. S. Army Electronics Command, Fort Monmouth, N. J. Attn: AMSEL-WL-C

TABLE OF CONTENTS Page FOREWORD v LIST OF ILLUSTRATIONS vi LIST OF SYMBOLS vii LIST OF APPENDICES xii ABSTRACT xiii 1. INTRODUCTION1 2. GENERAL PROPERTIES 3 2. 1 The A Matrix 3 2. 2 Characteristic Polynomial and Sequence Law 4 2. 3 Maximal Sequences and Generators 8 2. 4 Nonmaximal Sequences and Generators 9 2. 4. 1 Irreducible Characteristic Polynomials 10 2. 4. 2 Factorable Characteristic Polynomials 10 2. 5 The BA Matrix 13 2. 6 Equivalence of Two Linear Sequence Generators 15 3. THE SIMPLE SHIFT-REGISTER GENERATOR 16 3. 1 Definition 16 3.2 The A Matrix 17 3. 3 Characteristic Polynomial, Sequence Law, and Feedback Equation 18 3. 4 Initial Loading 21 3. 5 Interstage Relationships 23 3. 6 Output Adder Circuit 23 4. THE MODULAR SHIFT-REGISTER GENERATOR 27 4. 1 Definition 27 4. 2 The "A" Matrix 29 4. 3 Characteristic Polynomial, Sequence Law, and Feedback Equation 30 4. 4 Initial Loading 32 4. 5 Interstage Relationships 34 4. 5. 1 Maximal MSRG 34 4. 5. 2 Nonmaximal MSRG 39 4. 6 A BA Matrix Generator 39 4. 7 Output Adder Circuit 44 5. THE SIMPLE COMPLEMENT REGISTER GENERATOR 47 5. 1 Definition 48 5.2 The A Matrix 49 5.3 Prefatory Note 50 5. 3. 1 The Mod-2 Binomial Coefficients, (d.) 50 5. 3. 2 I*, Ri Matrices T k51 5. 4 Characteristic Polynomial and Feedback Equation 56 5. 5 Initial Loading 61 iii

TABLE OF CONTENTS (Cont.) Page 5. 6 Interstage Relationships 64 5. 6. 1 Maximal SCRG 66 5. 6. 2 Nonmaximal, Irreducible Characteristic Polynomials 67 5. 6. 3 Nonmaximal, Factorable Characteristic Polynomials 68 5. 7 Output Adder Circuit 70 6. THE MODULAR COMPLEMENT-REGISTER GENERATOR 75 6. 1 Definition 75 6. 2 The A Matrix 75 6. 3 Characteristic Polynomial and Feedback Equation 77 6. 4 Initial Loading 80 6. 5 Interstage Relationships 84 6. 5. 1 Maximal MCRG 84 6. 5. 2 Nonmaximal MCRG with Irreducible Characteristic Polynomial 90 6. 5. 3 Nonmaximal MCRG with Factorable Characteristic Polynomial 90 6. 6 The Output Adder Circuit 92 7. THE JACOBIAN HYBRID GENERATOR 96 7.1 Definition 96 7. 2 The A Matrix 97 7. 3 Characteristic Polynomial and Feedback Equation 98 7.4 Initial Loading 104 7. 5 Interstage Relationships 107 7. 6 Output Adder Circuit 109 8. COMPARISON AND SUMMARY OF GENERATORS 111 8. 1 Advantages and Disadvantages of Different Generators 111 8. 2 Mathematical Relationships for the Different Generators (Summary) 114 8. 3 Equivalent Maximal Generators 121 8. 4 Interstage Shift for Maximal Generators 128 REFERENCES 166 DISTRIBUTION LIST 167 iv

FOREWORD This report was prepared by the Cooley Electronics Laboratory, The University of Michigan, Ann Arbor, on Contract No. DA-28-043 AMC-00080(E). The work was administered under the direction of the U. S. Army Electronics Materiel Agency, Fort Monmouth, New Jersey. This report completes one phase of the work performed on this contract during the period 1 May 1964 to 31 August 1965. Messrs. Joseph H. Davis and John F. Dickson served as the technical representatives for the U. S. Army Electronics Command. Their assistance and guidance are gratefully acknowledged. The chief contributors and their fields of activity were: T. G. Birdsall, technical director; C. C. Hoopes, supervisor; R. N. Randall, analysis and experimental implementation. The JHG generator was originated by T. G. Birdsall. v

LIST OF ILLUSTRATIONS Figure Title Page 1 A five-stage multiple return shift-register generator 4 2 (a) Physical interpretation of a generator whose polynomial is factorable, (b) concept of "beating" the factor generators when the factors are nonrepeating. 11 3 (a) An n-stage simple shift-register generator, (b) a six-stage SSRG with feedback taps c5 and c3 closed. 17 4 Circuitry for generating a desired initial n-tuple using an SSRG. 26 5 General representations of SRG's: (a) general representation of an SSRG, (b) general representation of an MSRG. 28 6 Schematic representation of MSRG: (a) building blocks and corresponding symbol, (b) general representation of MSRG with feedback switches c1 and c3 closed, (c) schematic representation of (b). 28 7 The [4, 3, 0]MS MSRG and the associated BA matrix. 37 8 A BA matrix computer. 43 9 An MSRG with an output adder circuit. 45 10 A shift stage and a complement stage. 47 11 Two representations of the same multiple return generator. 48 12 a) The general form of an SCRG, b) a [6, 5, 0]SC SCRG. 49 13 The [4, 3, 0]C SCRG, the successive content vectors, and the associated BA matrix. 68 14 An SCRG with an output adder circuit. 71 15 An n-stage MCRG, (a) general representation, (b) schematic representation of a six-stage MCRG with feedback taps c1 and c0 closed. 76 16 A [5, 3, 0] C MCRG and the first five content vectors for the initia loading U(j)T = [1, 0, 1, 1, 1]. 84 17 The [4, 1, 0]MC MCRG, the successive content vectors, and the associated BA matrix, 89 18 A six- stage MCRG with a factorable characteristic polynomial and one period of successive content vectors. 92 vi

LIST OF ILLUSTRATIONS (Cont.) Figure Title Page 19 The [8, 6, 5, 4, 3, 2, 0]Mc MCRG and one period of consecutive content vectors. 92 20 An MCRG with an output adder circuit. 94 21 A seven-stage JHG, 98 22 The [5, 4, 3, 2, 1]JH and the successive content vectors. 103 23 A six-stage JHG with an output adder circuit, 110 vii

LIST OF SYMBOLS A nx n matrix applying to the interstage connections of a linear sequence generator A "A" matrix of an SCRG c A "A" matrix for an MSRG m AR 180~ rotation of the A matrix A "A" matrix for an SSRG s a.. element of the A matrix B (n+ 1)x 1 column vector composed of the coefficients b. of the characteristic polynomial associated with an SCRG or MCRG BA an f x n matrix related to the A matrix which expresses all the powers of A in terms of the first n- 1 powers b. binary coefficient of the i term in the characteristic polynomial f(Q) b.. binary elements of the BA matrix C an (n+1)x 1 column vector composed of the feedback coefficients ci of an SCRG or MCRG Cf companion matrix for f( ) Cf companion matrix for f'(Q) CRG complement register generator c. coefficient from the field mod-2 corresponding to the feedback taps of an SSRG, MSRG, SCRG, MCRG, or the shift and complement stages of a JHG c. coefficient from the field mod-2 corresponding to the feedback taps of an SSRG, T1 MSRG. SCRG, MCRG, or the shift and complement stages of a JHG c.. element of matrix R l,J 1 k (di) mod-2 binomial coefficient in the expansion (x+l)k = (di) xi (mod-2) k i=0 k (di) = ( ) (mod- 2) k EA nx n matrix of successive content vectors after E1(0) EA = [E1(0), E1(l),..., E1(n-l)] E.(0) i-th elementary load of a generator consisting of a 1 in the i-th stage and zeros in all other stages viii

LIST OF SYMBOLS (Cont.) Ei(k) content vector of a generator after k shifts when the initial content was E (0) ej j-th element of the column vector Ei(0) FA feedback matrix, nx n matrix derived from the feedback equation of an SSRG or an SCRG FM feedback matrix, nxn matrix derived from the feedback equation of an MSRG or an MCRG f.. element of matrix FA i,3 A f(O) characteristic polynomial of the A matrix associated with a linear sequence generator f'( ) factors of f(A) f i() characteristic polynomial associated with the i stage JHG composed of the first i stages of a given n stage JHG G an nx n matrix which commutes between the output sequences produced by adjacent stages of an SCRG for which c = 1 g.. element of matrix G g(O) characteristic polynomial associated with the G matrix H an nx n matrix which commutes between the output sequences produced by adjacent stages of an SCRG h.. element of the matrix H l,J h(Q) characteristic polynomial associated with the H matrix I identity matrix 1* the 90~ rotation of the identity matrix i, j, k, m, n, p, q, r, s,I integers, index, used to denote stages of a generator, feedback taps, number of shift pulses elements of the matrix I* lj,k J. k time shifts between the sequences produced by the i-th and k-th stages of a maximal generator JHG Jacobian-hybrid generator K time shift between the sequences produced by adjacent stages of an SCRG, or between adjacent stages of an MCRG which are not separated by an adder, time index L number of digits in a maximal length sequence, L = 2n-1 length of a sequence, usually reserved for the length of the impulse response sequence of a nonmaximal generator ix

LIST OF SYMBOLS (Cont.) MCRG modular- complement-register generator MSRG modular- shift-register generator m number of different nonmaximal sequences which can be produced by a particular nonmaximal generator n integer, number of stages in a linear sequence generator P. nxn matrix, the inverse of the nxn matrix E oT Ei(O) Ei(n- 1)T when such an inverse exists. p, Pi length of a sequence, usually one of several nonmaximal sequences which can be generated by a given nonmaximal generator p.. element of matrix which is the product of R2 FA; elements of matrix R3 element of matrix (I*)T qj, k element of matrix (I*)2, K R. a square matrix (usually nx n) composed of the mod-2 binomial coefficients (i= 1,2,3,4) r jk element of matrix Ri (i = 1, 2, 3, 4) SCRG simple- complement- register generator SRG shift-register generator SSRG simple- shift- register generator s.. element of matrix R T symbol used to denote the transpose of a matrix T A = transpose of A t.. element of matrix which is the product of H' G U' transient content vectors U'' U(j) content vector of generator at time j ui(j) content of the i-th stage of a generator at time j Vi(j) an nx 1 column vector of consecutive digits produced by the i-th stage of a generator; an n-tuple of digits from sequence xi(j) V'i(j) an (n-k)x 1 column vector consisting of the elements ui(j+k),..., ui(j+n- 1) X(j) lx n row vector made up of the first n digits of output from a grand mod-2 adder; a linear binary sequence x

LIST OF SYMBOLS (Cont.) Xi(j) linear binary sequence produced by the i-th stage of a linear-sequence generator, with time reference j; any indexed sequence x general indeterminant x. element of row vector X(j), x. = x(i-1) x(j) digit of sequence X(j); output digit from grand mod-2 adder at time j xi(j) element of Xi(j) Y(j) content vector of an SSRG at time j Yi(j) content of the i-th stage of an SSRG at time j ~a lxn row vector representing the tap connections for a grand mod-2 adder a. binary digit corresponding to the i-th switch connection for a grand mod-2 adder 6.. Kronecker delta 6. = 1when i = j,6. = 0 otherwise t ~general indeterminant T an operator which operates on a sequence X.(j) and performs the function of shifting that sequence ahead one digit 4/ ~ general indeterminant k k k (i) coefficient in the binomial expansion (x+l) = S (k) x x' ii=O xi

LIST OF APPENDICES Page APPENDIX A 135 APPENDIX B 140 APPENDIX C 160 APPENDIX D 164 xii

ABSTRACT This report treats techniques for generating linear binary sequences. The basic properties of sequence generators, maximal sequences, and non maximal sequences are reviewed. Five specific types of generators, each representing a "canonical form, " are considered. Two forms of shift-register generators are studied: the simple-shift-register generator and the modular-shift-register generator. Two forms of complement-register generators are considered: the simple-complement-register generator and the modularcomplement-register generator. A hybrid generator consisting of both shift and complement stages is discussed. Included in the discussion for each generator are: (1) the relationship between the characteristic polynomial and the feedback connections, (2) the relationship between sequences produced by different stages of the same generator, (3) the initial loading required for the generator to produce a particular n-tuple from the output stage, and (4) an output adder technique to obtain the desired starting conditions for a sequence obeying the law of the generator. The advantages and disadvantages of each of the five generators are given. Also tables of equivalent generators for all maximal characteristic polynomials of degree 2 < n < 12 are included. Matrix theory is used throughout the report to prove necessary theorems, and it is used in the development of mathematical descriptions of the generators. Short proofs and derivations are presented in the text; more complex proofs and derivations are usually reserved for the appendices. xiii

1. INTRODUCTION In recent years the application of digital sequences in communications, radar, and guidance systems has increased. Considerable attention in the literature has been given to the properties and characteristics of digital sequences. This report considers techniques for generating periodic, deterministic, linear, binary sequences (only linear techniques will be treated). The binary states, for convenience in this report, will consist of O's and 1. One common technique, used extensively in the past for generating binary sequences, is the shift-register generator which essentially consists of a basic shift register to which modulo-two adders have been added. These adders are connected to various stages of the register. The outputs from the register stages form the inputs to the modulotwo adders, and outputs of the adders are fed back to some other stage of the register so that one or more closed loops are formed. When the shift register is then pulsed in the normal manner, the output from any stage of the register forms a digital sequence. In the general case, depending upon both the feedback connections and upon the initial loading of the shift register, the ensuring digital sequence has a period much longer than the number of stages in the register. Digital sequences can also be generated using a "complement register" around which some form of modulo-two adder feedback loop is employed rather than by using a shift register. The "complement register" consists of a cascading of complement stages (a ONE input causes the stage contents to change) rather than the cascading of shift stages (the input is stored directly) found in the shift-register. Combinations of complement and shift stages can also be employed to form "hybrid" generators. This report presents in one volume a basic treatment of linear generation techniques, and discusses some of the more important properties and advantages of the different types of generators. No attempt will be made here to treat the application of such sequences to practical systems.

In Section 2, the basic properties of linear sequence generators and linear sequences are reviewed to introduce the terminology and notation to be used throughout the report. In Sections 3 and 4, we review the properties of the simple-shift-register generator (SSRG) and of the modular-shift-register generator (MSRG). These types of generators have been treated extensively in earlier reports (see Refs. 1, 2), but are included in this report for completeness. The theory of the simple-complement-register generator (SCRG) and the modularcomplement-register generator (MCRG) is developed in Sections 5 and 6 in a manner similar to the discussion of shift-register generators. Section 7 presents an introduction to the "Jacobian-hybrid generator" (JHG) which is a form of hybrid generator that employs both complement and shift stages. Section 8 concludes the report with a comparison of the properties, and of the advantages and disadvantages of the different types of generators we have discussed. The notation used in this report follows that of Refs. 1 and 2. The properties and theorems developed in these references are often duplicated in this report without proof. 2

2. GENERAL PROPERTIES In this section the basic properties of linear sequences and of linear generators are reviewed. These properties are generally true, regardless of the type of linear generator being discussed. Basic definitions and notations are also developed to use in the remainder of this report. 2. 1 The A Matrix The A matrix, which we define below, performs this function: if one multiplies on the left the n-row column content vector, which represents the n contents of an n stage generator, by this matrix, then one obtains the contents of the generator after one shift. This matrix is equivalent in function to running the generator one step at a time. Let ui(j) be the content of the i-th stage of the generator at time j. The content vector U(j) is the n x 1 column vector u1(j) U(j) = u2(j) (1) un(j) where ui(j) = 1 or 0 depending upon the binary content of the i-th stage at time j. The content vector one shift later, U(j + 1), becomes U(j + 1) = A U(j) (mod-2) (2) or, for any number of shifts k U(j + k) = Ak U(j) (mod-2) (3) The n x n matrix A is defined as A = Fa.] nxn where (4) a. = 1 if stage j feeds stage i = 0 if stage j does not feed stage i. 3

For example, the A matrix, using Eq. 4, for the multiple return shift-register generator in Fig. 1 is 0 1 0 0 1 0 01 0 A = 0 0 0 0 1 (5) 11100 001 1 (5) 0 1 1 1 0 1 0 0 1 0 1 2 3 - + ^ + r- 4 1 J ~ Fig. 1. A five-stage multiple return shift-register generator.1 1 denotes modulo-2 addition. A "mod-2 adder," or "exclusive or" circuit produces a "ONE" output if, aiid only if, the inputs are different. ] denotes a shift register stage. In Section 5, complement register generators are considered for which each stage is a complement stage and denoted as. 2. 2 Characteristic Polynomial and Sequence Law Let f(5) be the characteristic polynomial of the A matrix for a given generator. By definition, the characteristic polynomial is the determinate IA - Il. Since (-1) and (+1) are the same in modulo-2 arithmetic, f(t) = A + Ii. (mod-2) (6) Further, let bi represent the coefficients of this nth degree polynomial f()), that is n f(s) = bi 1 (mod-2) (7) i=0 where bn is always one, and the other bi coefficients are either zero or one. Associated with every characteristic polynomial f(5) is the "companion matrix, " Cf, 4

0 1 0.... 0 0 0 0 1.... 0 0 Cf = companion matrix =. ) 0 0 0.... 1 0 0 0 0.... 0 1 b b, b b b, bo 1 b2.... n-2 bn-1 Note that the companion matrix is nonsingular whenever b = 1; this can be seen by expanding the determinate, I Cf, by minors by the first column Cf = bo (9) The characteristic equation is defined as f( ) = 0 that is, n E bi i = 0 (mod-2) (10) i= 0 By the Hamilton-Cayley Theorem (see Ref. 3), a matrix satisfies its own characteristic equation, thus n f(A) = I b.A' = 0 (mod-2) (11) i=0 Using Eqs. 3 and 11: f(A) U(j) = ~ biA1 U(j) = 0 (mod-2) i=0 n i bi U(j+i) = 0 (mod-2) (12) i=0 By changing the time index and because (+1) equals (-1) for mod- 2 addition, Eq. 12 can be rewritten as f' n bn U(j) = U(j) = b U(j-i) (mod-2) (13) n n-i The characteristic sequence law is derived from Eq. 13 n uk(j) = bn-i k(i ) (mod-2) (14) i=l for k = 1, 2,..., n. 5

The characteristic sequence law relates the present contents of any stage of a generator to the previous n contents of the same stage. Notice that the sequences produced by each stage of the generator obey the characteristic sequence law for the generator. Let the column vector Vi(j) represent an n-tuple of successive bits from the ith stage of a linear generator starting at time j, that is ui(j) ui(j+l) Vi(j) =: (15) ui(j +n- 1) The companion matrix, Cf, corresponding to the characteristic polynomial, f(Q), for the generator can be used to find Vi(j+k) by Vi(j+k) = Cfk V(j) (mod-2) (16) where ui(j+k) ui(j+k+1) Vi(j+k) = ui(j+k+n- 1) and Cf is as defined in Eq. 8. To verify Eq. 16, consider the product Cfvi(j) (mod-2) (17) The first n-l rows of product in Eq. 17 are ui(j+l), ui(j+2),..., ui(j+n-1), respectively. The nth row of the product is b ui(j) + b1ui(j+l) +.. + bn 1ui(j+n-1), (mod-2) (18) From Eq. 14, the characteristic sequence law, the sum in Eq. 18 reduces to ui(j+n). The product in Eq. 17 is, therefore, Vi(j+l) = CfVi(j) (mod-2) (19) 6

Equation 16 readily follows from Eq. 19 by repeated application of Eq. 19. Let X(j) = x(j), x(j+l), x(j+2),..., represent a sequence with time reference j. The individual digits of X(j), x(j+k), are the successive outputs from some stage of a sequence generator. The mod- 2 sum of two sequences X (j) + X2(j) by definition becomes X(j) + X2(j) = x(j) + x2(j), xl(j+l) + x2(j+l),... (mod-2) (20) Theorem 1: If Xl(j), X2(j),..., X (j) are sequences, all of which have the same characteristic sequence n law, E bni xk(j-i) = 0 (mod-2), then their sum i=0 m X(j) = Z Xi(j) (mod-2) i=l also obeys the same characteristic sequence law. Proof: For k = 1, 2,..., m, the individual digits of Xk(j) are determined by the sequence law n xk(j+s) = i1 bni xk(+s-i) (mod-2) s = 0, + 1, + 2,... (21) The sum sequence X(j) is composed of x(j+s), where m x(j+s) = Z xk(j+s) (mod-2), s = 0, + 1, + 2,... k= 1 m n = Z b ni Xk(j+s-i) (mod-2) k=l i=l n m = n- i k xk(j+s-i) (mod- 2) i=l k=l n = bni x(j+s-i) (mod- 2) (22) i=l n1 Comparing Eqs. 21 and 22 we can see that the sum sequence X(j) obeys the same sequence law that Xl(j), X2(j),..., X (j) obey. 7

In the remainder of this report the following notational convention will be used for the characteristic polynomial: (n, a,..., b) means f( ) = + a +. + b (mod-2) (23) For example, from Eqs. 5, 6, and 23 the characteristic polynomial for the generator in Fig. 1 is the determinate 1001 o 0 o 1 0 f( ) = IA + = 0 0 0 1 = 5+4+ + 1 = (5,4,1,0) (mod-2) 0 1 1 1+ 0 10 0 1 2. 3 Maximal Sequences and Generators Under certain conditions, sequence generators produce sequences that begin with a number of binary digits which are not part of the periodic portion of the sequence. These bits which are not a part of the periodic sequence will be referred to as transient bits. (Transient bits are discussed further in Section 2. 4. 2. ) Given any n consecutive bits of a periodic sequence from an n-stage generator, the entire periodic sequence is uniquely determined by application of the characteristic sequence law. As a result, any given n-tuple of consecutive bits of a sequence can appear in only one periodic sequence produced by the generator. For a transient free generator, every possible n-tuple will appear in one and only one of the periodic sequences. It should be noted that to obtain all of the periodic sequences produced by a generator various initial conditions may be required. Consider an n-tuple of consecutive binary digits (bits) of a sequence (x(j), x(j+l),..., x(j + n - 1)}. There are 2 possible binary n-tuples. One of these, however, is all O's. If x(j + i) = 0 for i = 0, 1,..., n-l, then from the characteristic sequence law x(j+n) = bnix(j+n-i) = 0 (mod-2) i=l n and every following bit will also be zero. Consequently, the all zero n-tuple will appear only in the all-zero sequence (null sequence) with a period of one bit. This particular sequence 8

will not be considered in the remaining portions of this report. There remain 2n- 1 nonzero n-tuples which can appear in a sequence or sequences from a generator. Consequently, the maximum number of digits in a periodic sequence generated by an n-stage linear generator is 2n- 1 before the sequence begins to repeat itself. Therefore, any sequence of length L 2n- 1 (24) will be defined as a maximal sequence if every n-tuple except the all zero n-tuple appear in it. An important property of maximal sequences is the shift-and-add property: if a maximal sequence is shifted in time and added to itself, then the resulting sequence will be the same maximal sequence shifted in time, or all zeros. That is, if X(j) is a maximal sequence, then X(j) + X(j + k) = X(j + r) (mod-2) (25) where k and r are non zero integer constants mod- L = 2 - 1. The shift-and-add property follows from (1) Theorem 1; (2) the fact that any n-tuple and the sequence law completely determines the sequence; and, (3) the fact that a maximal sequence contains every non zero n-tuple of binary digits. Another property of maximal sequence generators is: Theorem 2: Every stage of a maximal sequence generator produces the same sequence, but the sequence (except for the null sequence) from any stage will be shifted in time from the sequence produced by any other stage. The proof of this theorem appears in Appendix A. 2. 4 Nonmaximal Sequences and Generators Since any sequence of length L - 2 - 1, where n is the number of stages in the generator, has been termed a maximal sequence, any sequence of length p < L = 2 will be termed a nonmaximal sequence. Furthermore, if a transient free n-stage generator produces m different nonzero periodic sequences (obtained by using different initial loadings in the generator) with periods, Pl, P2,.. * * Pm then m p. = 2P1 - 1 = L (26) i=l 9

Non maximal sequences can be separated into two categories: (1) those associated with irreducible characteristic polynomials and, (2) those associated with factorable characteristic polynomials. 2. 4.1 Irreducible Characteristic Polynomials. If the characteristic polynomial associated with a non maximal sequence law is irreducible, it has been found (see Ref. 1) that there are m sequences of the same length, 2, which obey that sequence law, and by Eq. 26 mf = L (27) 2 where 2 is called the impulse response length. Non maximal sequences corresponding to irreducible characteristic polynomials exhibit a partial shift-and-add property. That is, for certain shifts the mod-2 sum will give back the same non maximal sequence and the shift-and-add property holds. 2. 4. 2 Factorable Characteristic Polynomials. It has been shown in Ref. 1 that if the characteristic polynomial, f(Q ), of a generator is factorable such that f( ) = f'( ) f"( )... f"' (Q) (mod-2) then the generator is non maximal. Further, the sequences that obey the sequence laws associated with the factors of the characteristic polynomial are among the sequences that obey the sequence law of the generator. For example, if the characteristic polynomial for a five -stage generator is (5, 4, 0) = (2, 1, 0)(3,1, 0) (mod-2) (28) then the generator is non maximal. The sequences associated with a (2, 1, 0) characteristic polynomial and the (3, 1,0) characteristic polynomial are among the sequences associated with a (5, 4, 0) characteristic polynomial. This property suggests a useful physical representation of a non maximal generator with a characteristic polynomial that is factorable(Ref. 1). This representation consists of 2The impulse response length, Q, is defined for any transient free generator as the length of that periodic sequence (produced by that generator) which contains n-l successive'zeros" preceded and followed by a "one". 3 For a more complete discussion, see Ref. 1. 10

a consideration of each factor as representing a separate generator, and a cascading of the resulting generators, as the factors themselves are cascaded in the equation. Figure 2a illustrates this representation of a generator with a polynomial that is factorable. Each generator in the cascaded group has its feedback connnections constructed according to the terms in the corresponding factor. The object of this representation is to be able to view the generation of the entire set of sequences from the total generator as stemming from different combinations of factor generator sequences. In this process, the indivdual generators are allowed to take on all their possible sequences, including the all-zero sequence. This representation has been shown to be always valid. It also serves as a useful means for considering the set of sequences from a factorable non maximal generator. polynomial = (n,j,.o.) = (km,.. )(p,r,.. )(s,t,..) k Stage Gen. -- pStage Gen. -- s Stage Gen. (a) (n,j,.oo) = (k,m,. o.) (p,r,.. ) (s,t,o..) k Stage Gen. p Stage Gen. I Output of Nonmaximal Generator s Stage Gen. (b) Fig. 2. (a) Physical interpretation of a generator whose polynomial is factorable, (b) concept of "beating" the factor generators when the factors are nonrepeating. In addition to the interpretation of Fig. 2a, another physical interpretation can be given for non repeated factors (Ref. 1). This interpretation views the sequences from the factors as "beating" to form the sequences of the total generator (whereas, the conception of Fig. 2a considers the factors as cascaded generators). "Beating" means operating the factor generators independently, and mod-2 adding the outputs. The word "beating" comes from the frequency spectrum analysis of the result, which contains the sum and difference of "the beats" of the individual sequence spectral lines. For a general polynomial, this 11

concept is depicted in Fig. 2b. This beating concept applies only when the factors of the polynomial are non repeating. It does not work when there are repeated factors. There are two particular types of factorable characteristic polynomials which rate special mention. The first is the characteristic polynomial that has (5 +1) as a factor. Theorem 3: The term ( + 1) is a factor of the characteristic polynomial n f() = Z bi i (b =1) (mod-2) i=0 n if, and only if, n Z b. = 0 (mod-2) i=0 That is, there is an even number of terms in f(Q ). This theorem is proved in Ref. 1, p. 104. An immediate consequence of Theorem 3 is that the characteristic polynomial for a maximal sequence generator has an odd number of terms. The second factorable characteristic polynomial that is a special case of interest is one which has 5 k as a factor. Theorem 4: Let the characteristic polynomial f(Q) have the form f() = Z bi i-k (mod-2) i=k whereb = b = 1 n k then (1) the sequence obtained from any stage of the generator may begin with a transient of k or fewer bits (not part of the periodic sequence), after which the sequence becomes periodic and obeys the sequence law of an n-k stage generator with characteristic polynomial n i-k f'() = E bi (mod-2) i=k 12

(Note: the sequence may start out with up to k transient bits and then produce the null sequence. ) (2) There is at least one non zero content vector, U', so that if the generator is initially loaded with U', there will be one transient content vector before every stage produces the null sequence. (3) If the generator is capable of producing any non zero periodic sequence, (k<n), then there is at least one non zero content vector, U", so if the generator is initially loaded with U" there will be exactly one transient content vector before the generator output becomes periodic and at least one stage produces a non zero sequence. The proof of Theorem 4 is found in Appendix A. The most important consequences of Theorem 4, for the purpose of this report, are (1) that a generator is transient free, if and only if, b - 1, and (2) any periodic sequence that can be produced by a generator with a characteristic polynomial that has k as a factor (i. e., b. = 0, 0 < i < k), can be produced by a generator of n - k stages. For these reasons the remainder of this report will deal primarily with generators having characteristic polynomials with a nonzero constant term (b - 1). 2. 5 The BA Matrix The BA matrix is a matrix associated with the A matrix of a sequence generator and is derived by using the characteristic equation of the A matrix. Each power of A can be expressed in terms of powers of A no larger than n-l (where n is the number of stages in the generator). The BA matrix represents a "table" of these expressions. The BA matrix is defined by the equation B = [bi j] (29) where the elements b.. are the coefficients in the equation i, n Al = b. An-j (mod-2) (30) j=l 1' The coefficients b.. will form either an L by n or anJ by n matrix. The BA matrix is essentially constructed by successively raising the powers in an equation, starting with 13

= L the identity A = A, and ending with A = I or AL = I. Whenever the power of n appears on the right hand side, it is replaced by use of the characteristic equation. For example, given a generator with a characteristic polynomial of (4, 2, 0) or equivalently A4 A2 + I, the BA matrix is derived as follows: A = A A2 A2 (mod- 2) A A3 (mod- 2) A4 A2 +I (mod-2) 5 4 3 A A A =A + A (mod-2) A6= A A5=A4+A2=A2+ I+A2= I (mod-2) and the BA matrix becomes powers ofA 3 2 1 0 1 O O 1 0 20100 2 O 1 0 0 BA= 31 0 0 0 4 0 1 01 5 1 0 1 0 600 01 For any non singular (transient free) A matrix (b0 = 1) the last row of the BA matrix will be n-l "zeros" followed by a "one", like the above example. This row then represents the smallest power 2 so that 4 A = I (mod-2) (31) Every sequence produced by that generator will be periodic every 2 bits. Therefore, if the nonmaximal generator produces any sequences of length p < 2, then 2 must be some integral multiple of p. A formal proof of this can be found in Ref. 1, p. 95. The BA matrix is obtained by application of the characteristic polynomial of the A matrix. Thus, two different A matrices with identical characteristic polynomials have identical BA matrices. 4 The impulse response length 2 is defined in Section 2. 4. 1. 14

2. 6 Equivalence of Two Linear Sequence Generators Two linear sequence generators are said to be equivalent if every sequence produced by one can be produced by the other, and vice versa. Since the sequences produced by a generator depend entirely upon the characteristic sequence law, necessary and sufficient conditions for equivalence are: (1) The linear sequence generators must have the same characteristic polynomials; (2) For every n-tuple of consecutive bits of a sequence obtainable from one generator, there exists an initial loading for the other generator which will generate the required n-tuple at the selected output stage of the generator. The properties and relationships developed in this sectioon are vaild for any linear sequence generator. In the following section, specific types of linear generators are considered and some of the more important properties of each type of generator are discussed. 15

3. THE SIMPLE SHIFT-REGISTER GENERATOR A linear shift-register generator (SRG) is any device using a binary memory register, that produces an output binary sequence when successively triggered by a "shift" command. A linear generator means that the changes in the register contents are those of a time-invariant linear operator. The shift register may include sets of storage units in which a particular content does not necessarily move to an adjacent position, but may move to various other positions depending upon the connections between the units (see Fig. 1). To form a shift-register generator, modulo-two adders are attached to a basic memory register to form feedback and/or feedforward loops. In this section, one standard form of shift-register generator (SRG) is considered, namely the "simple-shift-register generator" (SSRG). The SSRG is defined; and, the A matrix, characteristic polynomial, and characteristic sequence law for it are discussed. The treatment given to the SSRG in this section and that given to the "modularshift register," in the next section, are included in this report only for the sake of completeness. More detailed discussions of these two types of SRG's are given in Refs. 1 and 2. 3. 1 Definition In a simple shift register, each stage is fed by its immediate predecessor. In an SSRG, the contents of certain stages are added (mod-two) to feed the first stage. The switches, denoted as ci, represent the "feedback taps" of the SSRG in Fig. 3a. c. = 1 if the ith stage of the SSRG feeds the 1st stage (32) = 0 if the ith stage of the SSRG does not feed the 1st stage By convention c0 - 1, and normally c = 1. (See p. 20 where cn g 1.) In the SSRG there are only feedback loops to the first stage. No interstage adders are present. If the sequences themselves were the only item of interest there would be no loss in generality by considering only this type of SRG. Every linear generator can 16

be shown to have an equivalent SSRG, (Section 3. 4). The block diagram of Fig. 3b will be used to represent an SSRG without showing interstage connections as in Fig. 3a. + + + <^+ ~- ~ co - 1 2 n- n= 1 1X 2 - n-i1 n X =2 3 4 5 6 (a) (b) Fig. 3. (a) An n-stage simple shift-register generator, (b) a six-stage SSRG with feedback taps c5 and c3 closed. 3. 2 The A Matrix From Section 2. 1, the A matrix is defined by the following relation: A = [aij] where a.. = 1 if the jth stage of the SRG feeds into the ith stage of the SRG,J = 0 otherwise. From Fig. 3 it is obvious that the content of the ith stage of the SSRG at time j, ui(j), is given by the relationships: n ul(j) = j ckUk(- 1) (mod-2) _~~k=1~~~ \>~ ~(33) ui(j) = ui_(- 1), 2 i < n 17

For the SSRG with feedback taps cj, the A matrix becomes A =[ai,] where a 1 = c, j = 1,2,..,n (34) aii-1 = 1, i1 a.. =0 otherwise 1,J c1 C2 c3... c cn 1 2 3 n-1 1 0... 0 0 0 1 0... 0 0 A = (35) 0 0 0... 0 0 0 0 0... 1 0 3. 3 Characteristic Polynomial, Sequence Law, and Feedback Equation The characteristic polynomial for the SSRG, from Eq. 7, is defined as n f(~) = IA + II = b.1 (mod-2) i= 1 where b 1 n If the A matrix of Eq. 35 is rotated 180~, one obtains 0 1 0... 0 0 0 0 1... 0 0 AR = A rotated 180~ = *.. (36) 0 0 0... 1 0 0 0 0... 0 c c c... c2 c1 n n-1 n-2 2 1 18

which by comparing Eq. 8 is the companion matrix for the characteristic polynomial n f(~) = n + L c n-j j=l J By defining co - 1, the characteristic polynomial for an SSRG is f(~) = IA+ II n = L c. n-j (mod-2) (37) j=0 where c. are the feedback taps of the SSRG C=1 c. = 1 if the jth stage is in the feedback loops = 0 otherwise By comparing Eqs. 7 and 37, the characteristic polynomial for the SSRG is determined by the relationship b = cn-i i = 0,1,2,...,n (38) where the b.'s are the coefficients in the characteristic polynomial Eq. 7, and the ci's are the feedback taps of the SSRG. From Eqs. 14 and 38, the characteristic sequence law for an SSRG becomes n ui(j) = ck ui(j-k) (mod-2) k=l for i = 1,2,...,n (39) A shorthand notation for describing an SSRG is feedback equation which specifies an [n, a,..., b, 0]: SSRG with feedback taps n,a,...,b (40) closed. Note that O has been placed in the feedback equation for convenience to indicate that c, - 1. Also the n-th stage is included in the feedback loop. 19

From Eqs. 23, 38, and 40 we can see that the characteristic polynomial and the feedback equation for the SSRG are "simple reverses" of each other. That is characteristic polynomial < feedback equation (n,a,b,...,c,0) <> [n,n-c,...,n-b,n-a, 0]s (41) Example: The six-stage SSRG in Fig. 3b with feedback taps c6, c5, and c3 closed has the feedback equation and the characteristic polynomial [6,5,3,0]ss <= (6,3,1,0) The relationship between the feedback taps and the coefficients in the characteristic polynomial point out these two important properties of SSRG's: (1) Theorem 4 states that any sequence, from a generator with a characteristic polynomial having no constant term (b0 = 0), can be generated by a generator with less than n stages (disregarding transients). Therefore, since c = bo, any periodic sequence from an SSRG in which cn = 0 can be generated by a transient free SSRG with fewer than n stages. Such generators will not be considered in this report and the condition c 1 will be implied for all n stage SSRG's. (2) Theorem 3 states that if n b. = 0 (mod-2) i=O then, (5 + 1) is a factor of f(~) and the generator is nonmaximal. For the SSRG b. = c i, thus, 1 nn n n S b =, cn = C ci (mod-2) i=0 i=0 i=0 20

and if, n z ci 0 (mod-2) i=O 1 then, (5 + 1) is a factor of f(~). Therefore, for a maximal SSRG, n L i = 1 (mod-2) (42) i=0 Every maximal SSRG must have an even number of feedback taps (not counting c, - 1). A table of all maximal SSRG's of length 2 < n < 12 is presented in Section 8. 3. 3. 4 Initial Loading The initial loading problem is one of determining the initial content vector U(j) for a generator to obtain a desired n-tuple of consecutive bits from the last stage of the generator. (Since any n consecutive bits of a sequence along with the characteristic sequence law uniquely determine the sequence, the initial loading problem is equivalent to finding the initial loading of a generator necessary to obtain a particular sequence from the last stage starting at a given place in the sequence. ) Let { u(j), un(j + 1),..., un(j + n - 1)} be the desired n-tuple of bits from the last stage starting at time j. Then from Eq. 33 Ui(j) = i+l(j+ 1) and by successive application of Eq. 33, ui(j) = un(j+n- i) (43) Equation 43 specifies the necessary initial loading to obtain the desired n-tuple output. Let the column vector Vi(j) represent n consecutive output bits from the i-th 21

stage of the SSRG as in Eq. 15, that is ui(j) ui(j + 1) ui(j + 2) Vi(j) = u(j + n- 1) where ui(j) = contents of the i-th stage of the SSRG at time j. Let 0 0 0... 0 0 1 0 0 0... 0 1 0 0 0 0... 1 0 0 I* =...... (44) 0 0 1... 0 O 0 0 1 0... 0 O 0 1 0 0... 0 O 0 then the initial tuple loading U(j) for a desired n-tuple output from the last stage, V (j), is found from the relationship U(j) = I* Vn(j) (45) where u(jj) U(j) = un(j) 22

For any n-stage linear sequence generator, the characteristic polynomial and sequence law can be found from the A matrix. Given the characteristic sequence law, any n-tuple of consecutive bits completely determines the sequence. From either Eq. 39 or 41, the feedback equation for an SSRG can be found for any sequence law or characteristic polynomial. From either Eq. 43 or 45, the necessary initial loading for the SSRG can be determined to generate a desired n-tuple of consecutive bits as the starting output of the last stage. Hence, Theorem 5 Any sequence that can be generated by a linear sequence generator can be generated by an SSRG. Theorem 5 can be restated as follows: Every linear sequence generator has an equivalent SSRG. 3. 5 Interstage Relationships The relationship between the output sequences obtained from the different stages is particularly uncomplicated for a simple shift-register generator. From Eq. 33 Ui+l(j) = ui(j- 1) or Ui+k(j) = ui(j- k) (46) That is, the contents of the (i+k)-th stage are the same as the contents of the i-th stage k shifts earlier. Thus, if Xi(j) denotes the output sequence produced at the i-th stage, then from Eq. 46 Xi+k(j) = Xi(j - k) (47) or equivalently, for periodic sequences Xi(j) = Xi+k(j+k) (48) 3. 6 Output Adder Circuit As contrasted with the direct technique of loading the generator with the proper initial conditions (Section 3. 4), a technique is described in this section for using an output 23

adder to obtain a desired sequence initiation. In generating a desired initial n-tuple using an SSRG a "grand mod-2 adder" is used. This adder takes the outputs of selected stages and mod-2 adds them together to produce the total mod-2 sum. The grand adder has as many inputs as there are stages in the generator and the adder taps, ai's, determine which stages are fed to the adder (see Fig. 4). If we let a. = 1 if the i-th stage is fed to the adder (49) = 0 otherwise and let x(j) be the output of the adder at time j, then n x(j) = ai ui(j) (mod-2) (50) i=1 where ui(j) = contents of the i-th stage at time j. Define X(j) = [x(j), x(j+ ),...,x(j+n- 1)] (51) where x(j) = adder output at time j, and a =(al 2,... an) (52) then Eq. 50 can be written as x(j) = a U(j) (mod-2) (53) and Eq. 51 becomes X(j) = a [U(j), U(j+ 1),..,U(j+n- 1)]nxn (mod-2) (54) Assume that the output X(j) is desired when the contents of the generator consist of a single one in the first stage and zeros in all remaining stages. This special initial condition has been denoted E1(0) and is called the "first elementary load" (see Ref. 1). Therefore, U(j) = E1(0) (55) 24

where 1 0 E1(0) = 0 (56) 0 and U(j+1) = AU(j) = AE1(0) = E1(1) (mod-2) Equation 54 becomes X(j) = a[E (0), E(1),...,E (n- 1)] (mod-2) (57) In Ref. 1, the n x n matrix on the right in Eq. 57 has been denoted as the EA matrix associated with the SSRG, that is, EA = [E1(0) E1(1),...,E1(n- 1)] (58) Also in Ref. 1, a "feedback matrix, " FA, is defined for an SSRG. It has the form c0 C1 C2 * n- 3 C n-3 n2 n-1 O Co C1 *- Cn-4 Cn-3 n-2 0 o c....Cn~S c c O 0 c 0. cn-5 Cn-4 n-3 FA=.. (59) O 0... c0 c1 c2 O 0 0... 0 c c 0 0 0... 0 0 c where c. = feedback taps of the SSRG Co 1. 25

+F +)^+ ~) C1 C2 3 Cn-l 1 2 3 n- 1 n a1 a2 3 3 an- an Grand Mod-2 Adder e Output x(j) Figo 4. Circuitry for generating a desired initial n-tuple using an SSRG. Furthermore, the EA and FA matrices are nonsingular matrices and are inverses, E - FA (60) From Eqs. 57, 58, and 60, X(j) FA = a EA FA = a (mod-2) (61) In algebraic form, Eq. 61 becomes m m= m-k (j+k- 1) (mod-2) (62) m k mThe solution (Eq. 62) guarantees that the output sequence starts with the desired n bits. The sequences produced by each stage of a linear sequence generator obey the characteristic sequence law of the generator. Theorem 1 states that a sum sequence (consisting of the mod-2 sum of sequences each of which obey the same sequence law) obeys the same sequence law. Therefore, the output sequence X(j) from the grand adder in Fig. 4 obeys the sequence law of the generator and is determined by its first n bits. Consequently, by using the output adder circuit we can generate any desired sequence that obeys the characteristic sequence law of the generator. In a maximal SSRG, the adder output sequence X(j) will be the maximal sequence. In a nonmaximal generator, X(j) may be a completely different periodic sequence from that obtained as an output from any one of the stages of the generator. 26

4. THE MODULAR SHIFT-REGISTER GENERATOR The modular shift-register generator (MSRG) was developed because of difficulty in the reliability of the SSRG at high frequencies. These high frequency problems of the SSRG arise from: (1) the unbalanced inputs to the mod-2 adders, and (2) from both time and propagation path delays. The treatment of the MSRG in this section will parallel the treatment given the SSRG in Section 3. 4. 1 Definition An SSRG is shown in Fig. 5(a). A "Modular Shift-Register Generator" (MSRG) is illustrated in Fig. 5(b). The term "Modular" stems from picturing the shift register of Fig. 5(b) as being composed of two types of modules (building blocks) sandwiched together. These modules are: (1) a single flip-flop capable of driving a single input, and (2) a flip-flop and mod-2 adder combination, capable of driving a single input. Figure 6(a) shows the building blocks and also the symbol which will be used to denote each. Using this representation, the MSRG of Fig. 5(b) with feedback switches co, c1, and c3 closed is depicted in Fig. 6(b). As shown, an amplifier for the final stage capable of driving n inputs is needed, since the modules (building blocks) are capable of driving only one input. For simplicity, the amplifier shown in Fig. 6(b) will be understood to be included and the representation for an MSRG will be as in Fig. 6(c). The MSRG was developed to eliminate the difficulty encountered with SSRG's in experimental work because of unbalanced inputs; and at high frequencies because of the propagation time delay through feedback adders. The MSRG also permits a simplified method of interstage mod-2 addition (see Ref. 2). Since, as will be shown later, every linear generator has an equivalent MSRG, this new type of generator is important to consider. As shown in Fig. 5(b), the switch c0 is always closed (identically equal to one). This will be the only case considered in the following discussion on MSRG's because it is necessary for transient free operation (see Section 4. 3). Also, the feedback switches have been numbered to correspond to the number of the shift stage directly preceding the switch. 27

c 1 l 2 /3 C4'5 c5 0 1 ~c~t~-cl 2 5t ~ 3 ~-) —c( 4 ~t-~l 5 t~f~-cl 6 (a) c = 1 if switch is closed = 0 if switch is open co 1 c1 2 /C3 c4 c5 /cn i1 + 2 +-< 3 + 4 +- -7~ 5 (+ — 6 (b) c. = 1 if switch is closed = 0 if switch is open Fig. 5. General representations of SRG's: (a) general representation of an SSRG, (b) general representation of an MSRG. -~ FF i 1 2 3 4 5 6 - Output Flip- Flop Symbol (b) (a) -FF ) 2 3 4 5 6 Flip-Flop and Adder Symbol (c) Fig. 6. Schematic representation of MSRG: (a) building blocks and corresponding symbol, (b) general representation of MSRG with feedback switches c1 and c3 closed, (c) schematic representation of (b). 28

That is, if c = 1 is a feedback tap, then this convention implies that the switch on the mod-2 adder following the m-th stage is closed. In Fig. 5(b) the switches, denoted as ci, represent the "feedback taps" of the MSRG. c. = 1 if both the i-th and the last stage feed the (i+ 1)-th stage = 0 if only the i-th stage feeds the (63) (i+ 1)-th stage and c0 = c 1 O n4. 2 The "A" Matrix From the feedback arrangement of the MSRG (Fig. 5b), it is obvious that the content of the i-th stage at time j, ui(j) is determined by the relationship u,(j-) = C u (j-) = Un(j-1) and j (64) i(j) = i-1( 1) + Ci-l un(j 1) (mod-2) for i = 2,3,...,n By the definition of the A matrix in Eqs. 4 and 64, the A matrix for the MSRG has the form 0 0... 0 O cO 1 0... 0 0 c A= 0 1... 00 c2 (65) 0 0... 1 0 Cn 0... 0 1 c 29

That is, A = [aij] where a. c > (66) a.. 1, n ia. = 0, otherwise 4. 3 Characteristic Polynomial, Sequence Law, and Feedback Equation From Eqs. 6 and 7, the characteristic polynomial is the determinate n f(Q) = IA + I = bi (mod-2) i=0 where b - 1. n For the MSRG, the transpose of the A matrix, AT, is a companion matrix having the form 0 1 0... 0 0 O 0 1... 0 0 A =::: (67) 0 0 0... 1 0 0 0 0... 0 1 c0 c1 C2 Cn-2 cn- Comparing Eq. 67 with Eq. 8, the characteristic polynomial of an MSRG is n f() = ci ci (mod-2) (68) i=0 From Eqs. 7 and 68, the characteristic polynomial for an MSRG is determined by the relationship b. = Ci i = 0,1,2,...,n (69) where the bi are the coefficients in the characteristic polynomial and the ci are the feedback taps of the MSRG. 30

From Eqs. 14 and 69, the characteristic sequence law for an MSRG becomes n i(j) cn kui(j-k) (mod-2) for i = 1,2,...,n. (70) 1 k=l1 The feedback equation for an MSRG is defined similar to the feedback equation for an SSRG. Feedback equation for an MSRG n a by d s with feedback taps a,b,..,d, (71) [n,a, b,...,d, 0]MS and 0 closed. By convention n is always closed. Note that n, as well as 0, has been placed in the feedback equation to indicate that c c = 1. 0 n From Eqs. 23, 69, and 71, the characteristic polynomial and the feedback equation for an MSRG, are the same, that is characteristic polynomial 4===> feedback equation (72) (n,a,b,...,c,0) < —> [n,a,b,...,c,0]MS For example, the six stage MSRG in Fig. 6(c) with feedback taps co, cl, and c3 closed has the feedback equation and the characteristic polynomial [6,3, 1, 0]MS A= (6,3,1,0) The relationship between the feedback taps and the coefficients in the characteristic polynomial points out two important properties of MSRG's: (1) Theorem 4 states that any periodic sequence from a generator with a characteristic polynomial having no constant term (b0 = 0) can be generated by a generator with fewer than n stages. Therefore, since co = b0, any periodic sequence, from an MSRG for which co = 0., can be generated by a generator with fewer than n stages. 31

(2) Theorem 3 states that if n L b. = 0 (mod-2) i=O then (4 + 1) is a factor of f(4) and the generator is nonmaximal. For the MSRG b. = c., thus 1 n n bi = L c (mod-2) i=O i=O and if, n E c. = 0 (mod-2) i=0 then, (4 + 1) is a factor of f(4). Hence, for a maximal MSRG n L c. = 1 (mod-2) (73) i=O and every maximal MSRG must have an even number of feedback taps (not counting cn 1). 4. 4 Initial Loading Like the SSRG, it is possible to find the initial loading of an MSRG so that a specified n-tuple of consecutive digits u (j), un(j + 1),..., un(j +n- 1) will be generated at the output of the n-th stage. From Eq. 64, but increasing all indices by k + 1, i+k+l(j+k+l) = Ui+k(j+k) + ci+k n(j+k) (md-2) (74) for 1- i < k < n-i- As long as we hold i to the range 1 < i < n - 1, we may sum both sides over k, from k = 0 through k = n - i - 1 n-i-1 n-i-1 n-i-1 3 ui+k+l(j+k+1) = ui+k(j+k) + 2 ci+k n(j+k) (mod-2) (75) k=0 k=O k=0 The first two sums have many terms in common. Subtracting these we obtain n-i-1 un(j+n-i) = ui(j)+ C+k un(jk) (mod-2) (76) k=0 32

Because c = 1 for a nontransient generator, we see that the left-hand side can be absorbed by the sum for the index k = n - i n-i ui(J) = Z c+k (+k) 1 < i < n- 1 (mod-2) (77) k=0 Now Eq. 77 trivially holds for i = n, since the sum will then only be the k = 0 term c u (j). We, therefore, have the desired result n-i ui(j) = Ci+u(j+k) 1 < i < n (mod-2) (78) k=0 which relates the initial load u1(j), u2(j),... un(j) to the initial output n-tuple un(j), Un(j+l),., un(j+n- 1). If FM is defined by the equation c1 c2 c3 n-2 1 n "2 ^ " ** S- n-i n c2 c3 c4... cn c 0 c3 c4 c5 c.. C 0 0 FM =. (79) Cn-2 Cn- 1 Cn. ~ ~ ~ cni c... 0 0 n-1 n c 0 0... 0 0 0 n then Eq. 78 can be written in matrix form as U(j) = FM Vn(j) (mod-2) (80) where U(j) and V (j) are as defined in Eqs. 1 and 15, respectively, and Vn(j) is the desired initial output n-tuple. From Eq. 70 or 72, the feedback equation for an MSRG can be found for any sequence law or characteristic polynomial. From Eq. 78 or 80, the necessary initial loading for the MSRG can be determined to generate a desired n-tuple of consecutive bits as the starting output of the last stage. Hence, by Section 2. 6 33

Theorem 6 Any sequence that can be generated by an n-stage linear sequence generator can be generated by an n-stage MSRG. Corollary Every SSRG has an equivalent MSRG, and vice versa. From Eqs. 41 and 72, the relationship between the equivalent SSRG and MSRG becomes [n,a,b,...,d, 0]MS < [n,n- d,...,n- b,n- a, 0]SS or (81) [n,a,b,...,d,O0]SS < [nn-d,...,n-b,n-a,O]MS Notice that the equivalence relationship in Eq. 81 is a simple reverse of the feedback equation. 4. 5 Interstage Relationships The relationship between the output sequences from different stages of an MSRG differs from that of an SSRG in that there exists a jump or change in the sequences whenever two stages are separated by an interstage mod-2 adder. This phenomenon is related to the shift-and-add property of sequences, consequently, it is convenient to consider maximal and nonmaximal MSRG's separately. 4. 5. 1 Maximal MSRG. In a maximal MSRG every stage produces the same maximal sequence but they are shifted in time from one another. If two successive stages, say the i-th and the (i+ 1)-th, are not separated by an interstage adder, and if Xi(j) represents the sequence produced by the i-th stage, then Xi(j) = Xi+l(j+l) (82) If the two stages are separated by an interstage adder, then Xi(j) = Xi+(j+l) + Xn(j) (mod-2) (83) X.(j) - X (j+J ) I (8 X i(j) = Xi+( +Ji, i+l) where Ji l is a time shift related to the shift-and-add property of maximal sequences. 34

The following discussion develops one method for determining the shift J.n 1, n between the sequences from the i-th stage and the n-th stage of a maximal MSRG. Let V.(j) be an n-tuple of digits from the sequence X.(j) with time reference j, that is ui(j) u(j + 1) Vi(j) = ui(j + n- 1) From Eq. 16, repeated here, C Vi(j) = Vi(j+k) (mod-2) (16) f 1 1 where Cf is the companion matrix associated with the characteristic polynomial of the MSRG. From Eq. 64, we can write u.(j) = ui+(j + 1) + ci Un(j) (mod-2) for i = 1,2,...,n- from which follows Vi(j) = Vi+(j+ 1) + ci Vn(j) (mod-2) 1 < i < n-1 (84) Let J. be the time shift between the sequences produced by the i-th stage and the n-th i, n stage so that Vi(j) = Vn( +Ji, n) (85) then using Eqs. 85, 84, and 16 Vn-1() = Vn(j+Jn-l,n) JC (mod= Cf-l' Vn(j) (mod-2) Vn(j+ 1) + Cn Vn(j) (mod-2) = (Cf + cn_ 1 I) Vn(j) (mod-2) 35

Jn n is the solution to the equation n-l,n Cfn = C + c I (mod-2) (86) f f + Cn-l Similarly, Vn_2(j) = Vn(J+Jn-2,n) = C n-2'n V (j) (mod-2) = Vnil(j+ l) + Cn-2 Vn(j) (mod-2) = [Cf(Cf + cn1 I) + Cn-2 I] Vn(j) (mod-2) = (Cf + cn Cf + cn2 I) Vn(j) (mod-2) and Jn is the solution to the equation n-2, n Cf n-"2n = Cf2 + cn Cf + 2 I (mod-2) (87) Assume that for some arbitrary value of i, J. is the solution to the equation n-i, n CfJn i n c + c-1 Cf +. + + C + I (mod-2) (88) then Vni-1(j) = Vn(J + Jn-i-,n) - - n-i-1 n = Cf n-l-ln Vn(j) (mod-2) = Vni(j+ 1+ n-i-1 Vn() (mod-2) = V(+ Jn-in+ 1) + i Vn() (mod-2) J. = (Cf Cf n'in + cii I) Vn(j) (mod-2) i+i i = Cf + 1 + * * * + Cn-i Cf + n-i- I) Vn(j) (mod-2) and J. is the solution to the equation C n-i-l,n C n-i-ln = c Cf + c +. + ci Cf + c (mod-2) (89) 36

From Eq. 89, if Eq. 88 is true for some particular value of i, then it is true for the next larger value of i. From Eqs. 86 and 87, Eq. 88 is true for i = 1 and i = 2 since c = 1. Therefore, by induction, Eq. 88 is true for 1 < i < n - 1. The solution to Eq. 88 can be determined from the BA matrix for the characteristic polynomial. Since the characteristic polynomial for Cf is the same as that for the A matrix of the MSRG, Jn ncan be conf n-i, n sidered as the solution to the equation J. A nin + cA + + C..+ A + c I (mod-2) (90) n n-1 n-i As an example consider a [4, 3,0] MS maximal MSRG. Figure 7 shows this generator and its periodic sequences along with its associated BA matrix. BA Matrix 1 2 3 4 A 1 0 0 0 Powers of A -3 2 1 0 0 1 0 0 1 0 1 0 0 0 1 0 2 0 1 0 0 000 1 31000 1 0 1 4 1 0 0 1 1 1 0 1 5 1 0 1 1 1 1 1 6 1 1 1 1 1 1 1 0 7 0 1 1 1 0 1 1 1 8 1 1 1 0 1 0 0 9 0 1 0 1 1 0 1 10 1 0 1 0 1 0 1 1 11 1 1 0 1 1 1 0 0 12 0 0 1 1 0 1 1 0 13 0 1 1 0 0 0 1 1 14 1 1 0 0 1 0 0 0 15 0 0 0 1 Fig. 7. The [4,3,0] MS MSRG and the associated BA matrix. Applying Eq. 90 and the BA matrix J34 12 A =4A + 3 I = A + I = A (mod-2) A 4 = c4 A + c A + c2 I = A + A = A (mod-2) 3 2 3 2 14 A 1'4 = c4 A + c 2 AI +A cA = (mod-2) 37

so J14= 14 1,4 J2 4 = 13 3,4 = 12 and X1(j) = X4(j + 14) = X(j - 1) X2(j) = X4(j + 13) = X4(j - 2) X3(j) = X4(j + 12) = X4(j - 3) These shifts are verified from the sequences shown in Fig. 7. The shift between successive stages Ji i+1 can be obtained from the values of J. in the following manner: if, in J. < J. < i<n-2 i+l,n i,n - - then, J..i = J. - J. (91) ii+1 1i,n Ji+l, n However, if Ji+l,n > Ji, n then, J. L - J + J. (92) i, i li+1, n +i,n ( where L = 2n - 1 = the length of the maximal sequence X. 38

For the above example, 1,2 = 1 1 = 1 2,3 = 12 J3,4 =12 or X1(j) = X2(j + 1) X2(j) = X3(j + 1) X3(j) = X4(j + 12) That is, the shift between sequences not separated by an adder is 1, as predicted by Eq. 82. The shift between sequences separated by an interstage adder is some value Ji i+1 determined by the shift-and-add property of maximal sequences, as predicted by Eq. 83. Tables of the shift between sequences from adjacent stages for all maximal MSRG's of length 2 < n < 12 are given in Section 8. 4. 4. 5. 2 Nonmaximal MSRG. Like the maximal MSRG, if two stages of a nonmaximal MSRG are not separated by an interstage adder then they will produce the same sequence. However, the time index will be shifted by one, that is, Xi(j) = Xi+ (j +1). If the two stages are separated by an adder, then they may produce the same sequence shifted in time. Or they may produce completely different sequences, depending upon the partial shift-and-add property of the nonmaximal sequence. 4.6 A BA Matrix Generator -A The relationship between the stage contents of an MSRG and the BA matrix associated with the characteristic polynomial of that MSRG is useful and interesting. Let the characteristic polynomial of the MSRG be f() = bn +n + b?1 n-1 + + bi ~ + b (mod-2) (93) n n-1S where b -- 1. (The coefficients have primes to help avoid confusion with the elements of Ref. 2, p. 25. 39

the BA matrix. ) From the Cayley-Hamilton Theorem, (Ref. 3) a matrix satisfies its own characteristic equation so that n An = b'. An-j (mod-2) (94) j=l n-J From the definition of the BA matrix (Section 2. 5), Eqs. 29 and 30 BA = [bi,j]xn (29) where the b.'s are the coefficients in the equation 1, j n A = Z b. An-j (mod-2) (30) j=1 1J k+ 1 Consider A, applying Eq. 30 Ak+l= bk+1 j An- (mod-2) j=l n-1 =L bk AlAn-j + I (mod-2) (95) =1 bk+lj k+1 n k+ 1 also consider A k+in the following manner, from Eqs. 30 and 94: k+1 k Ak = A. A (mod-2) n-i n L= A j b., A n-j (mod-2) =t b An-j + b l An (mod-2) j=2? z b A^1 An-j + bk 1 b?. An-j (mod-2) n-1 - (bk, lbbj+l + bk, 1 bj) A + 1 bo I (mod-2) (96) j=1 Equating Eqs. 95 and 96, the following relationship is obtained b. = b, + bk b'.. (mod-2) 1 < j < n- 1 bk+l,j bk,j++ bk, 1 n-) 1 nk > 1 ( ~ (97) bk+l,n = bk, b 40

Consider now an n-stage MSRG with the characteristic polynomial given in Eq. 93. For an MSRG, from Eq. 69 Ci = b,, i =,,n where the c.'s are the feedback taps and the b!'s are the coefficients in the characteristic polynomial. Equation 64 can be rewritten ul(k+1) = b' un(k) (98) Uj+l(k+1) = u (k) + b'j Un(k) (mod-2) 1 < j < n-1 n-j+1 n-j n-j n From the definition of the BA matrix 1 nn-j A = L b1 Anj = A (mod-2) j=1 J which requires bl,n-1 1 (99) blj = 0 for j / n-1 Assume that the MSRG is initially loaded at time k = 0 with a one in the first stage and zeros in all remaining stages; that is, = 1 when j = n n-j+l(O) =, n-j (100) = 0 when j ~ n From Eqs. 98, 99, and 100, for n > 1 41

u1(1) = b un(0) = b 60 n1 = 0 = b n-j+l(1) = un_(j+l)+l(0) + b' u (0) (mod-2) n-j n 0, n-j-1 + bj 0,n-1 (mod-2) (101) =6 +0 0,n-j-1+ 0 =5n. 1 < j < n-1 l,n-j - n=b - bl, 1,j Thus, Unj+l(l) = blj for j = 1,2,...,n or Unj+1(k) = bkj for k = 1; 1 < j n (102) Equation 102 can be shown by induction to be true for all k > 1 in the following manner: Assume that Eq. 102 is true for k = m, then from Eqs. 97 and 98, unj+ (m+1) = Un_(j+l)+l(m) + b'. u (m) (mod-2) n-j+1 n-(j+l)+l / n-j n = b + + b' b 1 (mod-2) m,j+l n-j m, 1 =bm+,j for 1 < j< n-1 (103) and ul(m+l) = b) u (m) - b' b 0 m, 1 = m+1 n (104) 42

Combining Eqs. 103 and 104 u n-j+(m+l) = bm+l, for 1 < j < n (105) We have shown that if Eq. 102 is true for some value of k, then by Eq. 105 it is also true for the next larger value of k, and, therefore, by induction Un jl(k) = bkj; for 1 < j < n and k > 1 (106) From Eq. 106, it is seen that if the MSRG is initially loaded at time k = 0 with ul(l) = 1 ui(l) = 0 for i / 1 then at time k > 1, the contents of the MSRG are the elements of the k-th row of the BA matrix read as indicated in Eq. 106. A BA matrix computer can be constructed as shown in Fig. 8 by applying this result: The computer operates in this way: The pulser shifts the MSRG, and at the same time, shifts the "line advance" for the printer. The printer records the digital contents of each stage for each shift. The net effect is to print the BA matrix one row at a time. For work in which the BA matrix is required (n large), such a computer is a great labor saving device, since writing out the BA matrix by hand is lengthy for large n. Line Advance -k Printer Shift Pulse k n + n — - +t --- 2 +f 1 Pulser -- c 1 cn-l Cn-2 c Cl = 1 Fig. 8. A BA matrix computer. 43

4. 7 Output Adder Circuit An output adder circuit can be used with an MSRG in the same manner that it is used with an SSRG to obtain a particular sequence or, equivalently, a particular initial n-tuple as an output from the adder. The MSRG and the output grand mod-2 adder are shown in Fig. 9. It is assumed the n-tuple output is desired when the MSRG contents are the elementary load E1(0) (see Eq. 56). Suppose that the MSRG is loaded at time j with a one in the first stage and zeros in all the remaining stages; that is i(j) = 6 i- = 1 when i- 1 = 0 = 0 otherwise For this initial loading, using Eq. 106, ui(j+k) = bk,n-i for k 1 where bk, is the element of the k-th row and the j-th column of the BA matrix. For k < n- 1, k n Ak = b An- = A (mod-2) j=1 and, thus, bk j = 6k = 1 when j = n-k, k <n-1 k,j k^n-j = 0 when j - n-k and for k < n- 1 ui(+k) = bk n-i 6 i = 1 when i- 1 = k (107) = 0 when i- 1 k The output x(j +k) of the adder in Fig. 9 is given by n x(j+k) = ai ui(j+k) (mod-2) i=l 44

C =1 |\ c1 \ C\2 Cn-2 Cn Cnl 1 a1 \da2 n-1 an Grand Mod-2 Adder ~ Output x(j) Figo 9. An MSRG with an output adder circuit. From Eq. 107, for k < n- 1 n x(j+k) = a i6 (mod-2) i=1 ki-1 k+1 If x(j), x(j + 1),...., x(j + n - 1) are the first n digits of the sequence desired as an output of the adder when U(j) = E1(0), the adder taps which should be closed can be found from the equation Ok = x(j+k- 1) for k = 1,2,...,n (108) If this is written in matrix form using the notation X(j) = [x(j), x(j + ),...,x(j+n- 1)] and a = [a1, a22..., an] Eq. 108 becomes a = X(j) (109) 45

6 This section completes the discussion of shift-register generators. As we pointed out in Section 1, "complement stages" can be employed rather than shift stages to form complement-register generators. Two forms of complement-register generators will now be considered: the simple complement-register generator which has a form similar to the SSRG; and the modular complement-register generator, which is analogous to the MSRG. 6Except for Section 8. In Section 8 some of the advantages of the various types of generators are discussed and a comparison is made of the properties of each. 46

5. THE SIMPLE COMPLEMENT REGISTER GENERATOR A linear sequence generator can be constructed using complement stages (binary counter stages) rather than the shift stages used in the SSRG and MSRG. The difference in operation between the shift stage and complement stage is: the shift stage directly stores its input, whereas the content of a complement stage remains unchanged when its input is a "0" and is changed or "complemented" when its input is "1". The operation of a complement stage is equivalent to adding (mod-2) the input to the complement stage to its present content. This sum then forms the new contents of the complement stage. Consequently, the complement stage can be considered as a shift stage which has a feedback loop from its output to its input as shown in Fig. 10. We will use this analogy in this report in discussing the development of the theory of complement-register generators. Input - Output Shift Stage Input Output \ Input i Output Complement Stage Fig. 10o A shift stage and a complement stage. A linear sequence generator which is made up entirely of complement stages instead of shift stages will be called a complement-register generator (CRG). Figure 11(a) shows an arbitrary multiple return CRG. Figure 11(b) shows an equivalent generator using shift stages. Why consider other types of generators when, as shown in Sections 3 and 4, any linear sequence can be generated by either an SSRG or an MSRG? There are two reasons 47

for developing the theory of complement register generators: (1) the complement stage physically requires fewer components to construct than the shift stage; and, (2) the interconnection between the stages is simpler. Today, with emphasis placed on size, weight, and cost of generators, the advantages of the CRG are obvious. Also, the CRG has some additional properties which add to its usefulness. (See Section 8. ) (a) Complement-Register Generator (b) Shift-Register Generator Figo 11. Two representations of the same multiple return generator. In this section we will develop the theory for one particular type of complement register generator, namely, the simple-complement-register-generator (SCRG). The treatment we use follows closely that of Sections 3 and 4. In Section 6, we will treat the "modular-complement-register-generator" (MCRG). 5. 1 Definition A simple-complement-register generator (SCRG) is a linear sequence generator which is constructed in the same manner as the SSRG except that the shift stages are replaced by complement stages. The general form of the SCRG is shown in Fig. 12(a). Note that in the SCRG (as with the SSRG) all feedback is to the first stage. A particular six-stage SCRG is shown in Fig. 12(b). 48

co- 1 c1 2 c3 Cn-l Cn 1 2 3 n- n 1 2 3 4 5c C C C C C C C C C (a) (b) Fig. 12. a) The general form of an SCRG, (b) a [6, 5,0]SC SCRGo The operation of the SCRG is similar to that of the SSRG. Every stage except the first is fed by the previous stage, and the first stage is fed by the stages in the feedback loop. The ci's in Fig. 12 represent the feedback taps where c. = 1 if the i-th stage feeds the 1st stage 1) ((110) = 0 if the i-th stage does not feed the 1st stage ( 5.2 The A Matrix Let u.(j) represent the contents of the i-th stage of an SCRG at time j. Then, by inspection of the SCRG in Fig. 12, using the shift stage analogy of Fig. 10, ui(j) can be expressed as n u1(j) = l(j - 1) + ciui(j - 1) (mod-2) i~~~~=1 }f ~ ~ ~(111) ui(j) = u(j - 1) + u_(j - 1) (mod-2) 2 < i < n Using the definition of the A matrix (Eq. 4), the A matrix for an SCRG has the form 1 + c c2 c3... c c c c1 c2 3 Cn-2 n-1 n 1 1 0... 0 0 0 0 1 1... 0 0 0 A =...... (112) 0 0... 1 1 0 O O 0.. 0 1 1 49

A = [ai j] where a, 1 = + c1 (mod-2) aj= c 2 < j < n a.. = 1 2 <j <n (113) a j-1 = 1 2 < j < n otherwise, a.. = 0 i,J 5. 3 Prefatory Note Several special matrices are useful in developing the theory for CRG's. The "mod-2 binomial coefficients" also arise in this theory. These matrices and coefficients will be defined in this section to facilitate the subsequent presentation of the theory of CRG's. 5.3. 1 The Mod-2 Binomial Coefficients, (di)k. The coefficients in the mod-2 binomial expansion play an important role in the development of the theory of complementregister generators. A brief description of these coefficients follows: The expansion of the quantity (x+ 1)k can be expressed in terms of the binomial expansion: k k k k k- 1 k k (x+1) = ( k) + (k)x +... + ()x+ (0) where k kA = the binomial coefficient (114) 50

k 7 The binomial coefficients ( ) have the following properties: k k 1 k-i k+ 1 k k (i ) 9 1 Define (di)k to be the "mod-2 binomial coefficient"; that is, (d)k (i) (mod-2) (116) In other words, (di)k = 1 when (.) is odd i 1 i (117) 0 when (.) is even In terms of (d.)k, the mod-2 binomial expansion of the quantity (x+ 1) has the form k kK (x + 1) = (di)k x (mod-2) (118) i=O where (di)k has the properties8 (d)k = (d)k = 1 (di)k = (dk-i)k (119) (di)k+ = (di)k + (di-l)k (mod-2) 1 < i < k J 5. 3 2 I* R Matrices. There are four nonsingular matrices composed of the mod-2 binomial coefficients which are important in the development of the theory of complement-register generators. These matrices are denoted R1, R2, R3, and R4. Another matrix, denoted I*, arises in relating the R. matrices to each other. These matrices are introduced below and the relationships between them are given. A complete discussion of this is reserved for Appendix B. 7See Ref. 4, pp. 33 and 49. 8These properties follow directly from the definition of (di)k and from the properties of ( ) in Eq. 115. 51

Define I* as I* = I rotated 90~ = [i*.j ]n j,k nxn where (120) k j n+-k = 1 when j = n+ 1 - k j,k j, n+l-k = 0 when j n+ 1 - k That is, I* has the form 0 0... 0 1 0 0... 1 0 I* =:::: (121) 0 1... 0 1 0... 0 0 In Appendix B it is shown that9 * = (I*)1 = (*)T (122) Define R1 as R1 = [ri,]nxn where (2 " for < i (123) ri,j 0 for j > i That is, R1 has the form (d)0 0... 0 0 (d0o) (dl)... 0 0 R =... (124) (d0)n-2 (dl)n2... (dn-2)n-2 0 ( d)n- (d1)n-l.' (dn-2)n-1 (dn-)n9For. any matrix M, the "transpose of the matrix" is denoted MT. 52

In Appendix B it is shown that R1 is "involutory," that is, R = R (125) Define R2 as R = [r2*.] 2 = i,] nxn where (126) di- 1)j-1 for i < j v- -1 2 r i 0 for i > j That is, R2 has the form (d)o0 (do)l ** (dO)n-2 (d)no (d l)1 (d)n-2 (dl)n_1 R2 = (127) 0 O... (dn-2)n-2 (dn-2)n-1 o 0... 0 (dn-1)nIn Appendix B it is shown that R2 = R (128) In addition, note that R T 2 1 Define R3 as R3 = [r3ij] 3 1,] nxn where (129) (di)nj for i n+1-j r,j 0 for i >n+1-j 53

From Eq. 129 we can see that R3 has the form (d )n- 1 (dO)n-2 *' (d0)l (d)0 (d)n- 1 (dl)n-2 *. (d)1 R3 =.... (130) (dn2)n-1 (dn-2)n2 0 0 ^n-^-l 0... 0 0 (dn- 1)n- 1 It is shown in Appendix B that R3 = R2 I* and that R 1 [Pi xn = R rotated 1800 where (131) (dn-i)j i for j > n+l- i Pi,j = 0 for j < n + 1- i -~1 ~J In other words, R3 has the form 0 0... 0 (dn-1)n-1 ~~ ~ ** ~ (dn- )n 1 0... (dn-2)n-2 (dn-2)n-2 -1. R3 =.. (132) 0 (dl)1... (d)n2 (d)n 1 (do)o (do)1.' (dO)n-2 (do)n-l 54

Define R4 as R [r 4 R4 - [ i,j]nxn where (133) (dj l)n-i for j <n+ 1-i r.. = - 1,J 0 for j >n+ 1-i From Eq. 133, R4 has the form (d0)n-1 (dl)n-1. (dn-2)n-1 (dn-1)n(do)n-2 (dl)n-2 (dn-2)n-2 4~R^~~~~ = ( ^~~~~~~.~.(134) (d0)1 (dl)... 0 0 (dg)o 0... 0 0 It is shown in Appendix B that R4= [Si, jnxn = R rotated 180~ where (135) (13 5) j (dn ~ for i > n+ 1- j S.. -- 0 for i < n+ 1- j -1 In other words, R4 has the form 0 0... 0 (d0) 0 0... (dl)1 (d0)1 -1.. R4 (136) 0 (dn_2)n_2 *. (dl)n-2 (dO)n-2 (dn-l)n1 (dn-2)n-1... (dl)n1 (d)n-1 55

The interrelationships between these equations are expressed by Eqs. 137 through 140 (see Appendix B). T T -2) R1 = R2 = I* R3 I* R4 (mod-2) (137) T T R2 = R = R3 I* = R4 I* (mod-2) (138) R = R1 I* = R2 I* = RT (mod-2) (139) = I* R = I* R = R (mod-2) (140) 5. 4 Characteristic Polynomial and Feedback Equation Let A be the "A" matrix for an SCRG and let A be the A matrix for an SSRG s having the same feedback taps. The "characteristic matrix" for the SCRG from Eq. 112 becomes c1 + (+1) C2 c3 n-2 Cn- Cn 1 ( +1) 0... 0 0 0 0 1 (+ 1)... 0 0 0 A + UI =... (141) 0 0 0... (+ 1) 0 0 0 0 0... 1 ( +1) 0 0 0 0... 0 1 (+1) If the substitution 4 = / + 1 is made in Eq. 141 A + (I = A + ( + 1) I = A + 4/I (mod-2) s s 56

using Eq. 37, the characteristic polynomial for an SCRG becomes f(5) = A + I (mod-2) = A + 4/I (mod-2) = c 4/n + c ln-1 +...+ c + c + (mod-2) = c0( + 1)n + 1( + )n- +... + cn1( + 1) + cn (mod-2) (142) where cO - 1. From Eqs. 142 and 118, n n f() = bk =, ci( + 1)n- (mod-2) k=O i=O n n-i = Ci 5 (dk)ni k (mod-2) (143) i=O k=0 Interchanging the summations in Eq. 143, we obtain n n-k k f( ) = i Zo (dk)ni c c (mod-2) (144) k=O i=0 Equating Eqs. 7 and 144, the coefficients of the characteristic polynomial, bi, are n-k bk = (dk)ni c. (mod-2) (145) i=0 In matrix form, Eq. 145 becomes B = R3 C (mod-2) (146) where B and C are defined to be b1 B = ( (147) n 57

co c1 C =. (148) n and where R3 is an (n + 1) x (n + 1) matrix defined in Eq. 129. It is shown in Appendix B that R3 is nonsingular. Therefore, from Eqs. 146 and 131 C = R3 B (mod-2) (149) where R1 = R3 rotated 180~ From Eqs. 149 and 131 n ck = (d nk)i bi (mod-2) (150) i=n-k Given the feedback taps of an n-stage SCRG, its characteristic polynomial can be found by Eq. 145 or 146. Conversely, given any n-th degree characteristic polynomial, the feedback taps of the associated n-stage SCRG can be found by Eq. 149 or 150. Equations 142 and 145 illustrate two important properties of SCRG's: (1) From Eq. 142, if c = 0, then + + 1 is a factor of the characteristic polynomial f(5); therefore, for every maximal SCRG cn = 1 (151) (2) Theorem 4 states that any periodic sequence from a generator with a characteristic polynomial having no constant term 58

(i. e., b0 = 0) can be generated by a generator with fewer than n stages. From Eq. 145, since (d0)ni = 1 n bo = c (mod-2) i=0 Therefore, any periodic sequence, from an SCRG for which n Z ci = 0 (the SCRG has an odd number of feedback taps not i=0 counting c0), can be generated by a generator with fewer than n stages. Because of Property 1, only those SCRG's will be considered for which c - 1. The feedback equation for an SCRG is defined like the feedback equation for an SSRG. feedback equation which specifies an [n,b,..., c,d, ]SC: SCRG with feedback taps n, b,...,c, (152) and d closed. Note that 0 has been included in the feedback equation to indicate that co - 1, even though there is no feedback tap from a zero stage; and, n is always present denoting c = 1. For example, consider the six-stage SCRG with feedback taps on stages 5 and 6 shown in Fig. 12(b). From Eqs. 146, 147, 148, and 129; C, B, and R3 become 1 0 0 C = 0 (153) 0 1 1 1 0 1 0 1 0 1 0 01010010 1 0 0 1 0 0 R3 = 0 1 0 0 0 1 1 1 0 0 0 0 0100000 1000000 59

B =R3. C = 0 (mod-2) (154) 1 0 and from Eqs. 152, 153, and 154, the feedback equation and characteristic polynomial are [6, 5,0]sc = -> (6,4,2,1,0) (155) Now assume a six-stage SCRG with feedback taps on Stages 1, 2, 4, and 6. R3 is the same as above. The feedback vector C becomes C = 0 (156) 1 0 and from Eq. 146 1 1 0 B = R3 C = 0 (mod-2) (157) 1 1 From Eqs. 156 and 157 [6,4,2,1, 0]SC (6,5,4,1,0) (158) 60

Note from Eqs. 155 and 158, that, in general, the SCRG with a feedback law corresponding to the characteristic polynomial of Eq. 155 does not have a characteristic polynomial corresponding to the feedback law of Eq. 155. For the SSRG and MSRG this property is true. That is, [6,5, 0] SS (6,1,0) [6, 5,0] MS --- (6,5,0) [6,1, 0]SS (6,5,0) [6,5,0] MS < (6,5,0) 5. 5 Initial Loading As with the SSRG and the MSRG one can find the necessary initial loading for an SCRG to produce a desired n-tuple as the first n-digits generated at the last stage. The relationship for the required initial loading for the SCRG is derived below. Through a change in time indices, Eq. 111 can be rewritten as il(j) = ui() + ui(+ 1) (mod-2) 2 < i < n (159) and with (d0)0 = 1, un(j) = (d0)0 Un(j) (160) In addition, since (do)k = (dk)k = 1 (see Eq. 119) n l(j) = Un(j) + Un(j+1) (mod-2) = (d0)1 un(j) + (d1)1 U(j+l) (mod-2) (161) Assume the relationship k n-k(j) = (di)k n(j+i) (mod-2) (162) i=0 is true for some arbitrary value of k. Then for k + 1 from Eq. 159, k + 1 < n - 1 n-(k+l)() = Un-k(j) + n(j+ 1) (mod-2) 61

k k = (di)k Un(j+i) + 3 (di) un(j+i+1) (mod-2) i=0 i=0 k k+l = (di)k Un(+i) + L (di- l)k Un(+i) (mod-2) i=0 i=l k =(dO)k Un(j) + [(di)k + (dil)k] u (j +i) 1=1 + (dk)k un(j+k+l) (mod-2) (163) From Eq. 119 (dm)m = (d)m =1 and (di)k+ = (di)k + (di-l)k (mod-2) Thus, Eq. 163 can be written k Un-(k+l)(j) = (do)k+1 Un() + (di)k+1 Un(j+i) + (dk+)k+1 Un(j+k+ 1) (mod-2) (k+1) = (di)k+ Un(j+ i) (mod-2) (164) i=0 From Eqs. 160 and 161, 162 holds for k = 0, 1; and from Eq. 164, 162 holds for k + 1, k arbitrary. Thus, by induction Eq. 162 applies for k = 0, 1, 2,..., n - 1. Through a change in subscript, Eq. 162 becomes n-k uk(j) = E (di)n-k un(j+i) (mod-2) (165) i=0 Equation 165 is the desired relationship for the initial loading uk(j) to produce at the n-th stage the n-tuple [un(j), un(j + 1),..., un(j + n- 1)]. Equation 165 can be written in matrix form, using U(j), Vi(j), and R4, defined in Eqs. 1, 15, and 133 respectively, as follows U(j) = R4 Vn(j) (mod-2) (166) 62

where u1(j) u2(j) U(j) =. = the required initial loading un() ui( ) ui(j+l) V.(j) =. = the desired n-tupleoutput ui(j+n- 1) and R~ = [r4 4 i,] nxn where for j n+ 1- i rij = (dj-)n-i 0 for j > n+ 1-i Note that in Eq. 166 the initial loading for the SCRG is independent of the feedback taps of the generator. This property is also true for the SSRG. For a given n stage SCRG, the initial loading necessary to produce a particular output n-tuplecan be determined from either Eq. 165 or 166. Furthermore, it was shown in Section 5. 4 that there exists an n stage SCRG associated with any n-th degree characteristic polynomial (and, hence, for any n-th degree sequence law). This results in the following theorem: Theorem 7: Every n stage linear sequence generator has an equivalent n stage SCRG. 63

As a special case of the above theorem, for every SSRG there is an equivalent SCRG, and vice versa. For every MSRG there is an equivalent SCRG, and vice versa. 5. 6 Interstage Relationships For every SCRG there is a matrix, H, (see Appendix B) which commutes between the output sequences produced at adjacent stages of the SCRG. In other words, if Vi(j) is defined as in Eq. 15 to be an n-tuple of consecutive digits produced by the i-th stage, that is ui(j) ui(j+l) Vi(J) = ui(j+n- 1) then H ~ Vi(j) = V (j) (mod-2) 2 i < n (167) Mathematically, the matrix H is defined as H = [hi]nxn where h. = for 1 < i < n- 1 (168) h., for 1 < i < n- 1 i i+l 1 h. = b for 1 < i < n- 1 n,i i-1 - - hn, = b + 1 (mod-2) n,n n-1 h.. = 0 otherwise 1,3 and the b'Is are the coefficients of the characteristic polynomial associated with the SCRG. From Eq. 168, the H matrix has the form 64

1 1 0 0... 0 0 0 1 1 0.. 0 0 0 1 1... 0 0 H = (169) 0 0... 1 1 b b b2 b... bn2 l+b 1 o 1 2 3 n-2 n-1 Furthermore, for every SCRG in which c = 1, there exists a matrix, G, (see Appendix B) such that G = H (170) and thus from Eq. 167 G * Vi1(j) = Vi(j) (mod-2) 2 < i < n (171) Mathematically, the matrix G is defined as G = [ nxn where j-1 > (172) gi 1 + Z bk (mod-2) for i < j k=0 j-1 g. j = Z bk (mod-2) for i > j 1'J k=0 A complete derivation of the G and H matrices and also Eqs. 167 and 171 can be found in Appendix B. Letting Xi(j) be the sequence generated at the i-th stage of the SCRG with time reference j as defined in Section 2. 2, Eq. 159 leads to the relationship Xi (j) = X.i() + X(j+1) (mod-2) 2 < i < n (173) which means that the sequence from the (i- l)-th stage is equal to the sequence from the i-th stage, shifted once and added to itself. Consequently, the interstage relationships of an 65

SCRG depend upon the shift-and-add property of the sequence produced. For this reason it is convenient to consider separately maximal generators, nonmaximal generators with irreducible characteristic polynomials, and nonmaximal generators with factorable characteristic polynomials. 5. 6. 1 Maximal SCRG. Theorem 2 states that every stage of a maximal generator produces the same sequence, but that there will be a time shift between the sequences produced by any two stages. From Eqs. 25 and 173 X l(j) = Xi(j) + Xi(j+1) (mod-2) = Xi(j+K) (174) where K is a time shift determined by the shift-and-add property of the maximal sequence. This constant, K, can be found, using the BA matrix associated with the generator, as the solution to the equation AK = A + I (mod-2) (175) where A is the "A" matrix of the SCRG. To justify the above statements, let V.(j) represent an n-tupleof the sequence Xi(j). Then from Eq. 173 Vi(j) = Vi(j) + Vi(j + 1) (mod-2) 2 < i < n (176) Let K be the time shift between the sequence produced by the (i - 1)-th stage and the i-th stage, that is, from Eq. 174 Vil(j) = Vi(j+K) (177) 1.(177) then, from Eqs. 176, 177, and 16 Vi (j) = Vi(j+K) = V(j) + V(j + 1) (mod-2) = Cf Vi(j) = (I+Cf) Vi(j) (mod-2) cf i(rod-2) Thus, K is the solution to the equation CK = Cf + I (mod-2) (178) 66

Equation 178 is solved from the BA matrix for the characteristic polynomial, and since the characteristic polynomial for Cf is the same as that for the A matrix of the SCRG, K can be considered as the solution to the equation A =A + I (mod-2) Note that in Eq. 175 the shift for a maximal SCRG is the same for each stage since Eq. 176 is valid for all i, 2 < i < n. As an example, consider a [4,3, O]SC maximal SCRG. Figure 13 shows this generator and its periodic maximal sequences along with the generator associated BA matrix. Applying Eq. 175 A = A + I (mod-2) or K = (4) Thus, Xi(j) = X2(j+4) X2(j) = X3(j+4) Xn-(j) = X(j +4) The shift K = 4 between each stage is verified from the sequences shown in Fig. 13. Additional values of K are tabulated in Table 2, Section 8. 4 for all maximal SCRG's of length 2 < n < 12. 5. 6. 2 Nonmaximal, Irreducible Characteristic Polynomials. In Section 2. 4. 1 we mentioned that when a nonmaximal generator has an irreducible characteristic polynomial all the sequences produced by the generator have the same length f. Because of the partial shift-and-add property of nonmaximal generators there are certain shifts for which the shiftand-add property is exhibited, for other shifts, however, a different sequence of the same 67

1 c 2c 3c 4 BA Matrix Time 1 0 0 0 Powers of A -- 3 2 1 0 1 1 1 ~ 0 1 00 O 1 0 2 0 1 0 0 0 1 1 0 0 0 1 0 0 4 0 0 1 1 o 1 0 5 0 1 1 0 104 1 6 1 1 0 0 0 1 8 0 1 0 1 1 0 1 9 15 0 1 0 1 10 1 10 0 1 1 1 1 0 0 1 11 1 1 1 0 0 1 17 13 1 1 0 1 1 0 1 1 114 1 0 0 1 1 0 0 0 15 0 1 0 1 Fig. 13. The [4,3,0]SC SCRG, the successive content vectors, and the associated BA matrixo generator is obtained. Since X1(j) = Xi(j) + X(j+1) (mod-2) if "1" is a shift for which the shift-and-add property holds, then the sequence produced by the (i- 1)-th stage will be a shifted version of the sequence produced by the i-th stage. If, on the other hand, the shift-and-add property does not hold for a shift of "1," then the sequence produced by the (i- 1)-th stage will be different from the sequence produced by the i-th stage. Further, if there are m different sequences, then it can be shown that when m < n, every set of m consecutive stages of the generator will produce all m of the possible sequences, and that when m > n, every stage will produce a different sequence. 5. 6. 3 Nonmaximal, Factorable Characteristic Polynomials. It was pointed out in Theorem 4 that any periodic sequence from a generator with a characteristic polynomial that has k as a factor can be generated by a generator with n-k stages. Therefore, only generators with a characteristic polynomial that has a constant term will be considered, that 68

is, b0 = 1; and since (see Eq. 145) n bo = c (mod-2) i=O only those generators for which n c. = 1 (mod-2) i=O 1 will be considered. The conclusion follows directly from Eq. 142 that ( + 1)k is a factor of f(5), if and only if, c. = 0 for i > n-k. For these generators, Eqs. 167 and 173 hold, but the G matrix is not defined so that Eq. 171 does not hold. n For all the remaining SCRG's, cn = 1 and L c. = 1. For these generators i=0 1 the matrices H and G exist and the following theorems apply. Theorem 8: n Consider an n-stage SCRG, for which c = 1, and L c. = 1, with a i= 1 characteristic polynomial, f(5), which is factorable. If any stage of the SCRG is producing a sequence corresponding to a polynomial of degree less than n, f'(5), where f(Q) = f"(V) * f'(), then the sequences from every stage of the generator correspond to the same polynomial f'(I). Theorem 9: n Consider an n-stage SCRG with c = 1 and, c. = 1, with a chari=0 1 acteristic polynomial, f(Q), which is factorable, f(Q) = f'()... f"( ). If any p consecutive stages of the generator (p < n) contain zeros at any time j, then none of the sequences being produced by the generator can be produced by a generator of p or fewer stages, unless every stage is producing all zeros. Both Theorems 8 and 9 are proved in Appendix B. As an application of Theorems 8 and 9, consider the eight-stage SCRG with feedback law and characteristic equation 69

[8,6,5,4,3,2, 0]S (8,6, 5,4,3,2,0) = (31, 0) (3, 2, 0)(2,1, 0) = (6, 5, 43,2,1, 0)(2,1, 0) We discussed in Section 2. 4. 2 that the sequences of a (3, 1, 0) generator, a (3, 2, 0) generator, and a (2, 1, 0) can be produced by an (8, 6, 5, 4, 3,2, 0) generator. Theorem 8 states that if any stage is generating a sequence which follows, for example, the (6, 5, 4, 3,2, 1, 0) sequence law and not a law of degree less than 6, then every stage is generating a sequence that follows this sequence law. Consequently, no stage will be generating a sequence corresponding to any of the irreducible factors. On the other hand if, for example, any stage of the generator is generating the (3, 1, 0) sequence then every stage is generating the (3, 1, 0) sequence. No stage is generating a sequence corresponding to (3,2, 0) or (2, 1, 0). Theorem 9 states that if the SCRG is initially loaded with a content vector containing at least three consecutive zeros, such as 1 0 0 0 0 0 0 00 U(0) = or U(0) = or U(0) = 10 0 10 0 1 then the generator cannot produce the (3, 1,0) sequence, the (3,2, 0) sequence, or the (2, 1, 0) sequence. A consequence of Theorem 8 is that if one stage of the SCRG is producing a sequence that corresponds to an irreducible factor of the characteristic polynomial, then every stage is producing a sequence that corresponds to the same factor. The interstage relationships found in Sections 5. 6. 1 and 5. 6. 2 for maximal and irreducible nonmaximal sequences are true if the specific factor involved is taken to be the characteristic polynomial. 5. 7 Output Adder Circuit An output adder circuit can be used with the SCRG to generate a shifted version of the same sequence or a new sequence in a manner similar to the adder for the SSRG and MSRG. Figure 14 shows an SCRG with an output adder. 70

o 1 C2 l3 V n- Cn go l 1_ 2 3 n-i n C C C C C Ya1 a2 Yan-1 Grand Mod-2 Adder - Output x(j) Fig. 14. An SCRG with an output adder circuit. Let a, X(j), FA, and R2 be defined as in Eqs. 52, 51, 59, and 126, that is = [al'... an] where a. = 1 if the i-th adder in Fig. 13 is closed = 0 if the i-th adder in Fig. 13 is open X(j) = [x(j),...,x(j+n- 1)] = the initial n-tuple of output digits desired from the adder, when U(j) = E1(O) A =[fi, jnxn where f. = c. for i < j = 0 for i > j and 2= [r,j]nxn where 2 r. = (di-1).1 for i < j 0 for i > j 71

Then a = X(j) ~ R2 FA (mod-2) (179) or, expressed in series form i i- m a. (dm )i-l- ck] x(j +m- 1) (mod-2) (180) m-1 k=0 -k The derivation of Eqs. 179 and 180 requires the following theorem which is proved in Appendix B. Theorem 10: Consider an n-stage SSRG and an n-stage SCRG which have the same feedback (not characteristic) equation. Let Y(j) represent the content vector of the SSRG at time j, and let U(j) represent the content vector of the SCRG at time j. If U(K) = Y(K) at some time K, then [(KU(K),U(K+),...,U(K+n-1)] = [Y(K),Y(K+1),..., Y(K+n-l)] * R2 (mod-2) (181) and [Y(K),Y(K+1),...,Y(K+n-l)] = [U(K),U(K+1),...,U(K+n-l)] * R2 (mod-2) (182) Returning to the derivation of Eq. 179, let U(j) be the content vector of the SCRG in Fig. 14. Then the output of the adder at time j is n x(j) = L ai ui(j) (mod-2) i=1 or x(j) = a * U(j) (mod-2) and X(j) = [a U(j), a U(j+l),..., * U(j+n-l)] (mod-2) = * [U(j), U(j+l),...,U(j+n-1)] (mod-2) (183) 72

Consider an SSRG with the same feedback equation as the SCRG, let Y(j) represent the content vector of the SSRG at time j, and let 0 Y(j) = E(0) = Then for the SSRG, from Eq. 58 [Y(j), Y(j+l),..., Y(j+n-1)] = [E1(0), Ei(1),...,E(n-1)] EA (184) and from Eqs. 60 and 59 EA1 = FA where F.: [f. ] FA fi,j nxn fi.j = c.. i j 0 i>j If the SCRG is initially loaded at time j with U(j) = E1(0) then U(j) = Y(j) and from Eq. 181 and 184 [U(j), U(j+l),...,U(j+n-1)] = [Y(j), Y(j+1),...,(j+n-1)]. R2 (mod-2) EA R2 (mod-2) (185) 73

Using Eqs. 183, 185, 128, and 60 X(j) = * EA * R2 (mod-2) and -1 -1 a = X(j) ~ R21 E1 (mod-2) = X(j) ~ RZ FA (mod-2) (179) In series form, R2 FA = [rj] [fi j] = [Pi ] (mod-2) where n i, z ri,k fk j (mod-2) k=l1 J = (di-1)k-1 Cj-k (mod-2) for i j = 0 (mod-2) for i >j then letting x. = x(j + i- 1) [a] = [xi] [Pi ] (mod-2) n a. = p. (mod-2) 1 m im, m=l i i = X (dm l)k-1 Ci-k (mod-2) m=l k=m i i-m k] i = m-l [1 (d m 1)- k kj x(j+m- 1) (mod-2) (180) m=l [.k=0 Either Eq. 179 or 180 can be used to find the proper adder taps to close to get x(j),...,x(j + n- 1) as the initial output of the adder when the elementary load E (0) is present in the generator. 74

6. THE MODULAR COMPLEMENT-REGISTER GENERATOR In Section 5 we discussed the fact that a linear-sequence generator can be constructed by replacing the shift stages of an SSRG by complement stages. Similarly, another type of linear-sequence generator can be constructed by replacing the shift stages of an MSRG by complement stages. The resulting generator becomes a "modular complement register generator" (MCRG), and is the subject of this section. The MCRG is developed in a manner parallel to the development of the MSRG. 6. 1 Definition The general form of the modular complement register is shown in Fig. 15(a). The operation of the MCRG is similar to the operation of the MSRG. Every stage (except the first) is fed by the previous stage and by the n-th stage if the feedback tap preceding that stage is closed. The ci's in Fig. 15 represent the feedback taps, c. = 1 if the n-th stage feeds the i + 1-th stage = 0 if the n-th stage does not feed the i + 1-th stage (186) c - 1 n 6. 2 The A Matrix From Section 2. 1 the A matrix is defined by the following relation A = [a ]nxn where a.. = 1 if the j-th stage of the generator feeds the i-th stage = 0 otherwise. It is obvious from Fig. 15 for the MCRG and from Fig. 10 for the equivalent operation of a complement stage that the content of the i-th stage at time j is given by 75

II''' I II C C C C El 0 1 2 n-2 n- 1n (a) 1 2 3 4 5 6 c c I c c c (b) Fig. 15. An n-stage MCRG, (a) general representation, (b) schematic representation of a six-stage MCRG with feedback taps c1 and cO closed. ul(j) = Ul(j- 1) + co un(j- 1) (mod-2) (187) Ui(j) = ui(j (j - 1) + i1(j- + ci_ un(j-l) (mod-2) 2 < i < n Thus, for the MCRG the A matrix becomes [ai,j]nxn where a.. =1 for 1 < i < n-1 1,1 _ (188) a1i+, = 1 for 1 < i< n-1 a = ~ c 1 for I < i < n- 1 n = i-1 for 1<icn-1 ann = 1 + c (mod-2) a. = 0 otherwise 1, J that is, the A matrix for the MCRG has the form 76

1 0 0. 0 0 cO 1 1 0... 0 c 0 1 1... 0 0 c2 A =...... (189) 0 0 0... 1 1 cn2 n-2 0 0 0... 0 1 (l+c 1) 6. 3 Characteristic Polynomial and Feedback Equation Let A be the "A" matrix for an MCRG and let A be the A matrix for the MSRG which has the same feedback taps. A comparison of Eqs. 65 and 189 shows that A = A + I (mod-2) (190) By comparison with Eq. 68, the characteristic polynomial for the MCRG becomes f( ) = Z bk k (mod-2) k=0 = IA + II (mod-2) = Am + (+1) I (mod-2) n n i = ci(+t 1) = E Ci (dk) l (mod-2) (191) i=0 i=O k=O i Interchanging the summations in Eq. 191, the characteristic polynomial for an MCRG becomes n n ] kf() L V (d k) c k (mod-2) (192) k=0 i=k i and the coefficients of the characteristic polynomial, bk, become n k = (dk) ci (mod-2) (193) i=k i Defining the column vectors B and C as in Eqs. 147 and 148, Eq. 193 in matrix 77

form becomes B = R2 C (mod-2) (194) where b c b c bn Cn and where R2 is an (n+ 1) x (n+ 1) matrix defined in Eq. 126. Furthermore, since R2 is an involuntary matrix (R2 = R2) C = R2 B (mod-2) (195) which can be written n ck = Z (dk). bi (mod-2) (196) i=k 1 Given the feedback taps of an n-stage MCRG, its characteristic polynomial can be found by either Eq. 194 or 193. Conversely, given any n-th degree characteristic polynomial the feedback taps of the associated n-stage MCRG can be found by either Eq. 195 or 196. Equations 191 and 193 illustrate two important properties of MCRG's: 1. From Eq. 191, if co = 0, then ( + 1) is a factor of f(5); therefore, for every maximal MCRG, c = 1. (197) 2. From Eq. 193, since (do) = 1, n b = c. (mod-2) 0 i=0 1 Therefore, applying Theorem 4, any periodic sequence from n an n-stage MCRG for which L c. = 0 (the MCRG has an odd i=0 number of feedback taps, not counting cn) can be generated by a generator having fewer than n-stages. 78

Because of Property 1 the convention c = c - 1 will be made for this report. The feedback equation for an MCRG is defined in the same way as the feedback equation for an SSRG. feedback equation which nr ab,...c O] specifies an MCRG with ( [na, M,...,c MC feedback taps a, b,..., c, 0 closed. Note that n has been included in the feedback equation to indicate that cn 1 even though there is no feedback to an n+ 1-th stage, and 0 is always present denoting c = 1. For example, to find the characteristic polynomial of the [6,, 0] MC MCRG shown in Fig. 15(b), Eq. 194 is used, B = R C (mod-2) 111 1 1 1 1 " 0 1 0 1 0 1 B= 0 001000 0 0 (mod-2) 0 0 0 11 1 1 00000 0 1 0 0 0 0 0 0 0 1 1 That is, [6, 1, 0] MC ~ (6, 4, 2, 1, 0) Note that by comparison of this example with the example of Page 60, for the same characteristic polynomial, the MCRG and SCRG feedback equations are simple reverses. This property is also exhibited by the SSRG and the MSRG. Formally, from Eqs. 196 and 150 repeated below c = k (dk) b. (mod-2) for MCRG (196) k i=k 1 n Ck = LE (d-ik). bi (mod-2) for SCRG (150) i=n-k 1 79

Replacing k by n-k in Eq. 196 and equating, one obtains c = cT n-k k or, in other words, the feedback taps are a simple reverse if the characteristic polynomial is identical (bi). 6. 4 Initial Loading Like the SSRG, the MSRG, and the SCRG, it is possible to find the required initial loading of the MCRG to produce a desired n-tuple as the first n output digits of the last stage of the generator. It follows that by proper loading, every sequence which obeys the sequence law of the generator can be obtained from the last stage. Let u (j),..., un(j + n- 1) be the desired initial n-tuple from the last stage starting at time j, and let c. represent the feedback taps of the MCRG. Then the initial loading of the generator at time j is given by the following equation: n-p n u(j) = O E L (dm)k ck Un(J+m) (mod-2) (199) m=0 =p+m -P In matrix form Eq. 199 can be written U(j) = FM. R1 Vn(j) (mod-2) (200) where U(j), Vi(j), R1, and FM are defined as in Eqs. 1, 15, 123, and 79. The derivation of Eqs. 199 and 200 proceeds as follows: Equation 187 can be written Uil(j) = Ui(j) + ui(j+l) + ci- un(j) (mod-2) 2 < i < n (201) With c 1, and by definition (do) = (di) - 1. ~n ~'(o i i 80

and un-(j) = n(j) + un(j+l) + cn un(j) (mod-2) = [(d0) c + (d) cnl] Un(j) + (dl) cn n(j+1) (mod-2) (203) Assume that for some particular integer k, where 1 < k < n- 2, the following equation holds: k (m 2 unk(j) = ( k-m) n n( +k - m) (mod-2) (204) Then using Eqs. 201, 204, and 119 un(k+l)(j) = u (j) + Unk(j+ 1) + Cn-(k+l) Un() (mod-2) k m m L (id m) c i u(j+ k - m) m=O 0 k-i n -i k m m+ O dk - k i cUn-i n(j+k+ 1-m) + Cn-(k+l) Un(j) (mod-2) k-l m Fk k z=3 13 (d -k_ m Um(j) + - (d c + ).O i=o - k-i n- u L 0 n-j tm=0 kl-in k. =L 0 k-i ( u j) ~ ~k m-l1 3+ z (duk-m) in- i un(j +k+ 1- m) m=l Li=0 k- n k~__ __,, J O + (dk-m) -m u (j+k+l-m) + c (k+) un(j) (mod-2) m=0 k-i n-m n-k) 81

By reindexing, ) becomes k m-1 m- JL-o (dk+l-m) i Ci Un(j +k+ 1- m) (mod-2) (205) m=1 LiO k-i Combining Eq. 205 and ) and using (di) = (di) + (dil), one obtains k+1 k k k m-1 m L (dk+l-m) Ci Un( +k+ - m) (mod-2) (206) m=1 Li=o k+l-i - Using the relation (do) = (do) =1, G) becomes k k+ k (do) C- un(j) (mod-2) (207) i=o k+1-i nEquations 206 and 207 combine to give k+1 m-1 U th Z (dk+im) cc n U (j+k+l-m) (mod-2) (208) m=l i=0 k+-i nUsing the relationship (dkm) = (dk+l1m) =, ( can be written k-m k+l-m k ~ (dk+1-m) n-m u(j+k+1- m) (mod-2) (209) m=0 k+l-m and then combining Eq. 209 with ) one gets k+1 (dk+l-m) Cn-m n(j +k+ 1- m) (mod-2) (210) m=0 k+1- m Then combining Eq. 208 and 210 one obtains the result k+1 m Un-(k+l)(j)= m LZ kd.kl-m) n-i Un(j+k+ 1-m) (mod-2) (211) m=0 i=0 k+l-i Equation 204 reduces to Eqs. 202 and 203 when k = 0 and k = 1, respectively. Equation 211 shows that if Eq. 204 is true for a particular value of k where 1 < k < n- 2, then it is true for the next higher value of k. Thus, by induction, Eq. 204 holds for 82

0 < k < n- 1. Letting p = n-k, Eq. 204 becomes n-p r u (j ) d= j Z (dnp_) - n(j +n- p- r) (mod-2) (212) r=0 i=0 n-p-i then letting m = n-p- r, Eq. 212 can be written as n-p fn-p-m l u (j) = (dm) c Un- (j +m) (mod-2) (213) p m=0 i=0 n-p-i nand letting k = n- i, Eq. 213 becomes n-p n u (j) = Z (dm) n (j + m) (mod-2) (199) m=0 k=p+m k-p Equation 200 is simply Eq. 199 written in matrix form and follows from inspection. For T example, suppose the n-tuple Vn(j) = [1 0 1 1 0] is desired as the first five digits from the last stage of a five stage MCRG with the feedback law and associated characteristic polynomial [5,3,0]MC < (5,4,3,2,0) Applying Eq. 200 U(j) = FM R V (j) 00101 10000 1 01010 11000 0 0 1 0 1 0 1 1 0 0 0 O U(j) = 1 0 1 0 0 1 0 1 0 1 (mod-2) 0 1 0 0 0 1 1 1 1 0 1 10 0 0 0 1 0 001 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 =1 (mod-2) 01000 1 1 1 0 0 0 10_ 1.l 83

1 2 3 4c 5[ 1C G C4C5 C Time j 1 0 1 1 1 I j+1 0 1 1 1 0 j+2 0 1 0 0 1 j+3 1 1 1 1 1 j+4 0 0 0 1 0 Fig. 16. A [ 5,3, 0] MC MCRG and the first five content vectors for the initial loading U(j)T = [1,0, 1, 1, 1]. The first n content vectors of a [5, 3, 0] MC MCRG beginning with the initial T loading U(j) = [1 0 1 1 1] is shown in Fig. 16. The desired output n-tuple is generated at the last stage of the generator. 6. 5 Interstage Relationships Equation 187 can be rewritten as ui(j) = ui+(j) + i+l(j+ 1) + ci Un(j) (mod-2) (214) Letting X.(j) represent the sequence produced by the i-th stage with time reference j, and applying the definition of sequence addition from Section 2. 2, the following relationship results: Xi(j) = +l(j) + Xi+(j+l) + ci Xn(j) (mod-2) (215) Equation 215 is a general relationship for any MCRG. Since the interstage sequence relationships depend on the shift-and-add properties of the sequence produced, it is convenient to individually consider maximal generators, nonmaximal generators with irreducible characteristic polynomials, and nonmaximal generators with factorable characteristic polynomials. 6. 5. 1 Maximal MCRG. Theorem 2 states that every stage of a maximal MCRG produces the same sequence, but the sequence from each stage will be shifted in time from the sequence from every other stage. If two adjacent stages are not separated by an interstage mod-2 adder, ci = 0, Eq. 215 reduces to 84

Xi(j) = Xi+(j) + Xi+l(j + 1) (mod-2) (216) This is the same relationship that exists between adjacent stages of a maximal SCRG, which is, from the shift-and-add property of maximal sequences, Xi(j) = Xi+(j+K) (217) where K is a time shift determined by the solution of the equation AK = A + I (mod-2) where A is the "A" matrix for the MCRG. When two adjacent stages are separated by an adder, ci = 1, Eq. 215 becomes X.(j) = Xi+(j) + Xi+l(j+l) + X (j) (mod-2) Let J. be the time shift between the sequences produced by the i-th and k-th stages so that i,k Xi(j) = Xk(J+Jik) and Xi(j) = Xi+l(j + Ji i+) The following discussion develops one method for determining the shift J n 1, n between the i-th stage and the n-th stage: From Eq. 16 Vi(j+k) = Cf V(j) (mod-2) where Cf is the companion matrix for the characteristic polynomial of the generator and Vi(j) is an n-tuple of digits from the i-th stage of the MCRG with time reference j, ui(j) ui(j + 1) V.(j) = ui(j+n- 1) 85

It follows from Eq. 214 that Vi() = Vi+(j) + Vi+(j+ 1) + ci V (j) (mod-2) Letting J. n be the shift between the sequence from the i-th stage and the sequence from 1, n the n-th stage, Vi(j) - Vn(+Ji, n) Then Vn_(j) = Vn(+Jn- n) n-, = Cfn-1,n v (j) (mod-2) f n = Vn(j) + Vn(j+ 1)+ C 1 Vn(j) (mod-2) = (Cf+I+cn_ I) Vn(j) (mod-2) (218) and -Jn-l,n Cf = cn(Cf+I) + Cn_1 I (mod-2) (219) where c - 1. n Similarly, n-2() = Vn(j+Jn-2,n) = Cf2n V (j) (mod-2) f n = Vnl1(j) + Vn l(j+l) + Cn_2 Vn(j) (mod-2) = (Cf+I) Vn () + Cn-2 Vn(j) (mod-2) 86

using Eq. 218 Vn_2(j) = (Cf+I) [c(Cf+I) + cn_1 I] Vn(j) + Cn2 Vn(j) (mod-2) [Cn(Cf+I)2 + Cn_(Cf+I) + Cn_2 I] Vn(j) (mod-2) and -2,n = c (Cf+I)2 + c (C +I) + I (mod-2) (220) I n l C n-2 f n~2 Assume for some arbitrary value of i, 1 < i < n- 2 that J. cf n-,n = Cn(Cf+I) + cn_ (Cf+I) +...+ cn i I (mod-2) (221) then for the n-i- 1st stage Vn-i-l() = n(+n-i-l,n) in-i-i = Cn-i- n V (j) (mod-2) V -i(j) + Vn_.(j + 1) + ni_ Vn(j) (mod-2) = (Cf+I) Vni(j) + Cn_i_ V(j) (mod-2) = (Cf+I) [C(Cf+I)i + Cn (Cf+I) i-.+ c I] Vn(j) + Cn-i Vn() (mod-2) i+1 f n- 1 f n-1 n n-i-1 = [cn(Cf+I)+ + Cn-(Cf+I)i +. c + C fi(Cf+I) + Cni_ I] Vn(j) (mod-2) and f n = cn(Cf+I) + l (CfI)i +... + i(C f+I) + ni I (mod-2) (222) Equation 222 shows that if Eq. 221 is true for some arbitrary value of i, then it is true for the next larger value of i. Equations 219 and 220 show that Eq. 221 is true for i = 1 and i = 2; thus by induction Eq. 221 is true for 1 < i < n- 1. Equation 221 can be solved for Jni, n by use of the BA matrix associated with the characteristic polynomial. However, 87

since Cf and the A matrix for the MCRG have the same characteristic polynomial they also have the same BA matrix and J. can be considered to be the solution to the equation A n-i,n J i i A n-in = ck(A + ) (mod-2) (223) k=O which can be solved for Jn n using the associated BA matrix. As an example, consider the [4, 1, 0] MC MCRG which has the characteristic polynomial (4, 1, 0). Figure 17 shows this generator, its output for one period, and its associated BA matrix. For the MCRG in Fig. 17, using Eq. 223 J3 4 A' = c4(A+ I) + c3 I (mod-2) = A + I (mod-2) J2 4 A = c(A+ I)2 + c(A + I) + c I (mod-2) = A2 + I (mod-2) A 1,4 = c4(A + I)3 + c3(A + I)2 + c2(A + I) + c1 I (mod-2) = A3 + A2 + A + I + I (mod-2) = A3 + A2 + A (mod-2) and from the BA matrix 1 4 =11 2,4 = 8 J3,4 = 4 which means that X1(j) = X4(j + 11) X2(j) = X4(j + 8) X3(j) = X4(j + 4) 88

which can be readily verified from the sequences shown in Fig. 17. Using Eqs. 91 and 92, the shift between stages of the MCRG in Fig. 17 is found to be J1,2 = 3 1,2 4 2,3 = 4 J3,4 4 or X1(j) = X2(j + 3) X2(j) = X3(j + 4) X3(j) = X4(j + 4) The shift between sequences not separated by an adder is the same, as predicted by Eq. 217. The shift between sequences separated by an interstage adder is some 1 2 3 4 B Matrix i -c 2C BA Matrix Time 1 0 0 0 Powersof A - 3 2 1 0 1 1 0 0 1 0 1 0 1 0 1 0 2 1 O 0 0 1 1 1 1 31000 1 0 0 3 1 0 0 0 0 1 0 0 0 10 0 1 i 0 15 1 00 1 0 1 1 7 1 0 1 0 0 1 0 801 0 1 0 I 1 1 1 0 1 1 0 0 1 10 1 1 1 0 0 0 1 1 1 1 1 1 1 0 1 12 1 1 1 1 0 1 1 1 13 0 i 0 1 1 0 0 0 14 1 0 0 1 89 12 i i F~~~~ig 7 h 4,jI MR t scesv otn 0etos In th soIatdB ar 8913iI

value determined by the shift-and-add property of maximal sequences. The shift between sequences without an interstage adder (4 in the example above) is identical to the shift between stages of the equivalent SCRG (see the example on Page 67 ). Tables of the shift between sequences from adjacent stages for all maximal MCRG's of length 2 < n < 12 are given in Section 8. 4. 6. 5. 2 Nonmaximal MCRG with Irreducible Characteristic Polynomial. All the sequences produced by a generator with an irreducible characteristic polynomial have the same length, B. A partial shift-and-add property exists. That is, for certain shifts, the shift-and-add property holds. However, for all other shifts different sequences are obtained. The relationship between the sequences produced by adjacent stages not separated by an adder is given by Eq. 216. Xi() = Xi+(j) + Xi+(j+ 1) (mod-2) If the shift-and-add property holds for the particular characteristic polynomial for a shift of "one, " then both stages of the generator will produce the same sequence but shifted in time, that is, Xi(j) = Xi+(j + K) (224) where K is the solution to the equation AK = A + I (mod-2) If the shift-and-add property does not hold for a shift of "one," then the two stages will produce different sequences. When two adjacent stages are separated by an adder, ci = 1, then the problem becomes much more complicated and will not be considered further in this report. 6. 5. 3 Nonmaximal MCRG with Factorable Characteristic Polynomial. If two adjacent stages are not separated by an adder, then from Eq. 216 Xi(j) = Xi+(j) + Xi+(j + 1) (mod-2) and the sequence from the i-th stage will be the same as the sequence from (i+ l)-th stage 90

shifted in time, if and only if, the shift-and-add property holds for the sequence Xi+ (j) for a shift of "1. " When the stages are separated by an adder, the relationship becomes more complicated. It was pointed out in Section 2. 4. 2 that when the characteristic polynomial of a generator is factorable, f(W) = f'(V) f"()... f"'(. ) (mod-2) the sequences associated with each of the factors are among the sequences that can be produced by that generator. Unlike the SCRG, it is possible for one stage of the MCRG to produce a maximal sequence which corresponds to one of the factors of the characteristic polynomial while other stages are producing different sequences. However, the following theorem still holds: Theorem 11: Given an n stage MCRG with a factorable characteristic polynomial, f( ) = f'( ) f"()... f"'(.) (mod-2) The sequences produced by each stage of the MCRG follow the same sequence law as is followed by the sequence produced by the last stage. (Note: some stages may produce the all-zero sequence.) Theorem 11 is proved in Appendix C. One consequence of Theorem 11 is that if the last stage of an n stage MCRG is producing a maximal sequence associated with a particular factor, then every stage of the MCRG is producing either the same sequence or the all-zero sequence. This is demonstrated in Fig. 18 for a [6, 5, 4, 3,] ]MC generator with a characteristic polynomial factorable by (6, 5, 4, 3, 0) = (2, 1, 0) (4, 1, 0). The sequence being produced by the last stage corresponds to the (2, 1, 0) factor which is associated with a maximal sequence of length L = 3. Every other stage of the generator is also producing the (2, 1, 0) maximal sequence except the 4th stage which is producing the all-zero sequence. An example of an MCRG with a factorable characteristic polynomial simultaneously producing sequences which correspond to different factors is shown in Fig. 19. In Fig. 19, the [8,6, 5,4,3,2, 0] MC MCRG with a characteristic polynomial that is 91

1 2 3 4 5 6 Time I 0 1 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 0 1 0 1 0 1 1 Figo 18. A six-stage MCRG with a factorable characteristic polynomial and one period of successive content vectors. (8,6,5,4,3,2,0) = (2, 1,0) (3,1,0) (3,2,0) = (2,1,0) (6, 5,4,3,2,1,0) is shown along with a period of successive stage contents. The 4th stage is producing the maximal sequence associated with the (3, 2, 0) characteristic polynomial and at the same time the 5th stage is producing the maximal sequence associated with the (3, 1, 0) characteristic polynomial. Theorem 11 is still satisfied, however, because the last stage is producing a (6, 5, 4,3,2, 1, 0) sequence which both the (3, 1, 0) and the (3,2, 0) sequences obey. 1 23 3 ^ 4^ 5^ 6^ rj 8 I CC|C C C C C C Time 1 0 0 1 0 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0 1 0 0 1 1 1 0 1 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 1 1 1 1 0 O0 0 1 0 0 1 0 0 0 0 / t t (3,2, 0) sequence (6, 5, 4, 3,2, 1, 0) sequence (3, 1, 0) sequence Fig. 19. The [8, 6, 5, 4, 3,2, 0] Mc MCRG and one period of consecutive content vectors. 6. 6 The Output Adder Circuit An output adder circuit can be used effectively with an MCRG to obtain a sequence starting with any desired n-tuple of digits as the output of the adder when the MCRG is initially loaded at time j with U(j) = E1(0). Let X(j) = [x(j), x(j+l),...,x(j+n- 1)] 92

represent the desired initial n-tuple of digits from the adder, and a= [, 2,..., an] be the row vector of adder taps where a. = 1 if the i-th adder tap is closed = 0 otherwise then a = X(j) ~ R2 (mod-2) (225) where R2 is defined as in Eq. 126. Expressed in series form Eq. 225 becomes i-1 ai = 3 (d ) x(j + m) (mod-2) (226) m=0 i-l The derivation of Eqs. 225 and 226 is simplified by the application of the following theorem: Theorem 12: Given an n stage MCRG, if u1(j) = 1 and u(j) = 0 for 2 < i < n at some time j, then ui(j+k) = (dil) for 1 < i < k+1, 0 k < n- 1 k and ui(j+k) = 0 for k+2 < i < n, 0 < k < n-2 The proof of Theorem 12 is given in Appendix C. The output of the adder in Fig. 20, given by Eq. 50, is n x(j+k) = ai ui(j+k) (mod-2) (50) i=l 93

\C \ C1 \ C \ Cn I Cn - 1 T'lcO 1 c 1I N"2 \Vl n C1 cn - 1c n a1 a2 an-I an 1 2 an-i Grand Mod-2 Adder -- Output x(j) Fig. 20. An MCRG with an output adder circuit. Applying Theorem 12, Eq. 50 becomes k+1 x(j+k) = j (dii1) i (mod-2) 0 < k < n-1 (227) i=l k Expressed in matrix form, Eq. 227 becomes X(j) = a R2 (mod-2) where R2 is defined in Eq. 126 to be 2= [rij] nxn r.2 = (di) for i < j r,3 (( j-1) =0 for i >j -1 Since R2 is an involutory matrix, R2 R2 X(j) * R2 = a R2 R2 (mod-2) = R2 R2 (mod-2) = C (225) which expressed in series form becomes 94

i- 1 a. = (dm) x(j + m) (mod-2) (226) m=O i- 1 In this section and in the one previous, we have considered complement-register generators. In particular, we have examined two canonical forms: the SCRG and the MCRG. In the next section a "hybrid" generator is considered which employs both complement stages and shift stages. 95

7. THE JACOBIAN HYBRID GENERATOR In the linear sequence generators we have previously discussed, problems arise at high frequencies because of propagation times and time delays. (See Section 8. 1.) One way to reduce propagation time is to build MSRG's in a circle to bring the last stage adjacent to the first and, thereby, make all feedback paths short. However, because of the operation of SRG's and CRG's all shifting and transfers must be completed before the next pulse can be introduced. If some form of generator could be constructed which consists entirely of balanced loads and symmetric localized feedback (all paths the same and no long feedback paths), it would be useful for high frequency applications. The "Jacobian Hybrid Generator" (JHG), discussed in this section, satisfies these conditions. The JHG is composed of both shift stages and complement stages (a hybrid). It contains only localized feedback and feedforward paths. This section will present a brief treatment of the properties of the JHG. 7. 1 Definition Figure 21 shows a 7-stage JHG composed of both shift stages and complement stages. It operates as follows: the input to each stage, except the first and last stages, consists of the mod-2 sum of the output of the two adjacent stages. The input to the first stage is simply the output of the second: The input to the last stage is simply the output of the next-to-last stage. All feedback and feedforward paths are to adjacent stages so that there are no long propagation times. Each stage (except the first and last) drives two adder inputs and has a single input. In Fig. 21, stages 2, 3, 5, and 7 are complement stages, and stages 1, 4, and 6 are shift stages. The sequence obtained from any stage of the JHG is a function of those stages of the generator that are shift stages and those stages that are complement stages. It is also a function of the initial loading. 96

7. 2 The A Matrix Let c. designate whether the i-th stage of a JHG is a shift stage or a complement stage, as follows c. = 1 if the i-th stage is a complement stage (228) = 0 if the i-th stage is a shift stage By inspection of Fig. 21 the content of the i-th stage at time j becomes ul(j) = cl u1(j- 1) + u2(j- 1) (mod-2) ui(j) = U1(j-l1) + ci u(j- 1) + u+l(j-1) (mod-2) 2 < i n-1 (229) u (j) = - l(j -1) + cn u(j -1) (mod-2) and the A matrix defined in Eq. 4 becomes A = [ai, j] where a.i =1 if j = i 1 (230) 1,J a.. = c. 1,1 1 a.. = 0 otherwise 1,J From Eq. 230 the A matrix for the JHG has the form C1 1 0... 0 0 0 1 c2 1... 0 0 0 1 c3... 0 0 0 A =.... (231) 00 0... c 1 0 n-2 0 0 0... 1 C- 1 n-1 0 0 0... 0 1 c 97

Note that in Eq. 231 the A matrix for the JHG consists of all zeros except for the main diagonal and the two "off diagonals. " This matrix is a "matrix of Jacobi" which is the reason for the name "Jacobian" hybrid generator. [-*(+* 2c t )- 4 ~~^)*~ 6 "^~^n Fig. 21. A seven-stage JHG. 7. 3 Characteristic Polynomial and Feedback Equation Let fk () be the characteristic polynomial for a k-stage JHG for which c, c2,..., ck designate the shift and complement stages according to Eq. 228. Then by defintion fk( ) is the determinate (c1+) 1... 0 0 1 (c2 +)... 0 0 fk() = |.. (mod-2) (232) 0 0... (Ck_ +) 1 0 0... 1 (Ck+For a 1-stage generator f1()= IC1 + | = c1 + i (mod-2) (233) For a 2-stage generator (cl+) 1 f2(~) = = + (c1+C2) + (c1 c2 + 1) (mod-2) (234) 1 (C2++) 98

For an n-stage generator, n > 3, (c1+0) 1 O... 0 0 0 1 (c2+ ) 1... 0 0 0 f (, =. I (mod-2) (235) 0 0 0... (Cn 2+) 1 0 0 0 0... 1 (c +n +) 1 o 0 0... 0 1 (cn+ ) Expansion of the determinate in Eq. 235 by minors along the last row gives (c+ ) 1... 0 0 1 (c2+ )... 0 0 n( ) = (Cn+ O) 0 0... (c ) 1 0 0... 1 (Cn-+ ) (c1+) 1... 0 0 1 (c2+ )... 0 0 1 (C2+ ) * *. O O +.... (mod-2) (236) 0 0... (c 2+) 0 0... 1 1 Further expansion of the second determinant in Eq. 236 in the last column gives (c1+ ) 1... 0 1 (c2+ )... 0 f() (cn: + ) n.n.. 0 0... (Cn2+) 1 0 0... 1 (c 1 ) 99O O.. 1 ( 99

(c1+ ) 1... 0 1 (c2+ )... +.. (mod-2) 0 0... (Cn2+) (c + ) fn-1() + fn-2() (mod-2) (237) Equations 233, 234, and 237 form a recursion relationship from which the characteristic polynomial of an n-stage JHG can be determined. Unfortunately the solution of this recursion relationship requires knowledge of all 2 smaller characteristic polynomials to find all 2n n-th order characteristic polynomials. The feedback equation for a JHG is defined as follows: feedback equation for an n-stage [n;a,b,...,c] JH: JHG in which stages a,b,...,c (238) are complement stages. For example, the feedback equation for the 7-stage JHG in Fig. 21 is [7;7, 5,3, 2] JH; the feedback equation for an n-stage JHG in which every stage is a shift stage is simply [n; -]JH' Because of the symmetry of the "A" matrix of the JHG, if the A matrix is rotated 1800 and the resulting matrix denoted A R, then AR is the "A" matrix for the same JHG if the numbering of the stages increases from right to left. However, rotating a matrix 180~ does not change the characteristic polynomial, so that A and AR have the same characteristic polynomial. This property is also evident from Fig. 21 because reversing the numbering of the stages does not change the operation of the generator. One consequence of this is that two n-stage JHG's have the same characteristic polynomial, and produce the same sequences. For example, [3; 2, 1]JH and [3; 3,2]JH, both 3-stage JHG's have the same (3,1, 0) characteristic polynomial. The feedback equation may be purely symmetric and the two feedback equations are consequently identical. For example, reversing the numbering of a [3; 3, 2, 1]JH gives [3; 3, 2, 1]JH. Another consequence is that for n > 2 there will be n-th degree characteristic polynomials for which no n-stage JHG exists. 100

For example, this listing gives all the possible characteristic polynomials of degree 1 < n < 3 and the feedback equations of the n-stage JHG associated with the polynomial, Polynomial Feedback Equation (1) [1;-]jH (1,0) [1;1]JH (2) [2;2,1]JH (2,0) [2;-]JH (2,1) none (2,1,0) [2;1]JH or [2;2]JH (3) [3;-]JH (3, 0) none (3,1) [3;3,1]JH (3,2) [3;2]JH (3,1,0) [3;2,1]JH or [3;3,2]JH (3,2,0) [3;1]JH or [3;3]JH (3, 2, 1) none (3,2,1,0) [3;3,2,1]JH From this list we can see that no JHG exists which corresponds to a (2, 1) or (3, 0) or (3,2, 1). Unlike the SRG's and the CRG's described in previous sections, no simple relationship or transformation between the characteristic polynomial and the feedback equation has been found for the JHG. Equations 233, 234, and 237 represent one way of determining the characteristic polynomial of an n-stage JHG. This method is well suited for compiling a table of all possible JHG's and their characteristic polynomials starting with a 1-stage generator and progressing through the n-stages. However, to find the characteristic polynomial of a particular n-stage generator for large n, when f n1() and f 2(i) are not known, a n-1l n- n second procedure is more suitable. This method for determining the characteristic polynomial of a JHG is based on: 101

Theorem 13: If an n-stage JHG is initially loaded with U(j) = E1(0), that is u(j) = 1 ui(j) = 0 for 2 < i < n then uk(j+k- 1) = 1 for 1 < k < n and ui(j+k-1) = 0 for 2< k + < i n Theorem 13 is proved in Appendix D. By reindexing Eq. 14, and assuming bn - 1, the characteristic sequence law can be written as n L bk Ui(j+k) = 0 (mod-2) (239) k=O If the JHG is initially loaded with the first elementary load, U(j) = E1(0), then by Theorem 13, ui(j+k) = 0 for k < i- 1 and ui(j+i- 1) = 1 Equation 239 becomes n n L b ui(j+k) = Z b ui(j+k) + bi 1 = 0 (mod-2) k=i- 1 k=i k or n bi l L bk u(j+k) (mod-2) (240) i-i k=i 102

As an illustration, consider a [5;4,3,2, 1]JH 5-stage JHG. The generator and its successive stage contents for an initial loading of U(j) = E1(0) are shown in Fig. 22. Applying Eq. 240 with n = 5 and b5 = 1 b4 = b5 u5(j+5) = 0 (mod-2) b3 = b4 u4(j+4) + b5 u4(j+5) = 0+ 0 = 0 (mod-2) b2 = b3 u3(j+3) + b4 u3(j+4) + b5 u3(j+5) = 0 + 0 + 1 = 1 (mod-2) 1= b2 u2(j+2) + b3 u2(j+3) + b4 u2(j+4) + b5 u2(j+5) = 0+ 0+ 0+ 0 = 0 (mod-2) b0 = bl ul(j+l) + b2 ul(j+2) + b3 ul(j+3) + b4 ul(j+4) + b5 ul(j+5) (mod-2) = 0+ 0+ 0+ 0 + 1 = 1 (mod-2) c ^(+) ^ -*(+)^- 5 Time 1 0 i 1 1 0 0 0 0 0 1 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 Fig. 22. The [5, 4, 3, 2, 1]JH and the successive content vectors. Thus, the characteristic polynomial for the [5;4,3,2, 1]JH 5-stage JHG is (5,2,0). Since reverse feedback equations give the same characteristic polynomial, the [5;5,4,3,2]JH 5-stage JHG is also associated with the (5,2, 0) characteristic polynomial. A complete tabulation of all maximal JHG's is given in Section 8. 3 for 2 < n < 12. As yet no practical method has been found for determining the feedback equation of a JHG associated with a given characteristic polynomial (the reverse process of above). In fact, as shown above, some characteristic polynomials do not even have an associated feedback equation. It should be noted that if a JHG exists for every irreducible characteristic polynomial, then from Section 2. 4. 2 every polynomial can be obtained by employing cascaded 103

JHG'so Or it can be obtained by beating JHG's, in which the individual generators correspond to the irreducible factors of the original polynomial. 7. 4 Initial Loading Like the generators we have discussed, it is possible to find the proper initial loading for an n-stage JHG to obtain any desired n-tuple of digits from some stage of the generator. Let U(j) be the content vector of the JHG at time j, and let Vi(j) be defined as in Eq. 15 ui(j) ui(j+ 1) Vi(j) = ui(j + n- 1) Let Ei(0) represent the i-th elementary load and be defined as the column content vector consisting of a single 1 in the i-th row, that is E(0) = [ej] (241) where e. = 1, j = i ej = 0, j / i 1 < j n Let A be the "A" matrix for the JHG, then k Ei(k) = A Ei(0) (mod-2) 104

By inspection, this identity is true ui(j) ul(j) ui(j)... Un(j) 0 ui(j+1) ul(j+l)... ui(j+l)... u(j+) 0 0. | |... | * | 1 | 4row i (mod-2) ui(j+n-1) ul(j+n-1)... ui(j+n-l)... u (j+n-1) 0 (242) Equation 242 can be written I )T U(j) U(j)T I U(j+l)T U(j) AT Vi(j) =. Ei(0) =. ~ E(0) U(j+n- 1)T U(j)T (A" ) U(j)T I Ei(0) U(j)T * AT * Ei(0) (mod-2) (243) U(j)T (A- 1)T E (0) Since the A matrix for a JHG is symmetric about the main dingonal T A = A and Eq. 243 becomes 105

U(j) I Ei(0) U(j) * A * Ei(0) Vi(j) = (mod-2) U(j)T An-1 E(O) U(j)T Ei(O) U(j)T E(1) (mod-2) (244) U(j) E.(n-1) However, U(j)T Ei(k) is simply a row vector times a column vector, so U(j)T Ei(k) = Ei(k) U(j) (mod-2) and Eq. 244 becomes Ei(O)T U(j) Ei(1)Z U(j) Vi(j) =. (mod-2) Ei(n- 1) U(j) T Ei(O) Ei(l)T U(j) (mod-2) E(n- 1)T 106

Assume the above n x n matrix has an inverse, Pi, that is ( -1 Ei(0)T Ei(l)T P =. (245) Ei(n-1)T then U(j) = Pi Vi(j) (mod-2) (246) Applying Theorem 14, it is found that for i = 1, the n x n matrix E1(O)T T E (n-1) is a triangular matrix with all ones on the main diagonal and all zeros above, hence it is nonsingular and P1 exists. Consequently, it is always possible to get any particular n-tuple of digits, V1(j), from the 1st stage of the JHG using the initial loading U(j) = P1 V(j) (mod-2) (247) Unfortunately, an explicit expression for the initial loading in terms of the stage coefficients, Ci, has not been found. The important point of this section is that an initial loading does exist for any desired output. 7. 5 Interstage Relationships For the JHG, from Eq. 229 u2(j) = c1 u1(j) + ul(j+l) (mod-2) 4 (248) ui(j) = i-1 Ui-l(j) + uil(j+l) + ui_2(j) (mod-2) 3 < i n(248) 107

From the definition of sequence addition and Eq. 248 it follows that X2(j) = c1 X1(j) + Xl(j+i) (mod-2) (249) Xi(j) = i-1 Xi_(j) + Xi_ (j+l) + Xi_2(j) (mod-2) 3 < i < n where Xi(j) is the sequence produced by the i-th stage of the JHG. Define an operator T which operates on an entire sequence Xi(j) and performs the function of shifting that sequence by one digit, that is T Xi(j) = Xi(j+l) and (250) T Xi(j) = X(j+k) Then X2(j) = (cl + T) X(j) (mod-2) (251) X3(j) = (c2 + T) X2(j) + X1(j) (mod-2) = [(c2 + T) (c1 + T) + 1] X1(j) (mod-2) = [T2 + (C1 + c2) T + (ClC2 + 1)] X1(j) (mod-2) (252) Xi(j) = (ci-1 + T) Xi(j) + Xi-2(j) (mod-2) (253) Comparing Eqs. 251 and 252 with Eqs. 233 and 234 we see that X2(j) = f1(T) X(j) (mod-2) and (254) X3(j) = f2(T) X(j) (mod-2) where fk(Q) is defined to be the characteristic polynomial of a k-stage JHG for which cl,..., ck designate the shift and complement stages as in Eq. 232. Assume for some arbitrary value of k, 3 < k < n- 1 that Xk(j) = fk(T) X(j) (mod-2) ( and (255) Xk1(j) = fk_2(T) Xl(j) (mod-2) 108

then from Eqs. 253, 255, and 237, Xk+l(j) = (ck + T) Xk(j) + Xkl(j) (mod-2) = [(ck + 7) fk-l(T) + fk-2()] Xl(j) (mod-2) = fk(T) X(j) (mod-2) (256) Equation 254 shows that Eq. 255 holds for k = 3, and Eq. 256 shows that if Eq. 255 is true for any arbitrary value of k such that 3 < k < n- 1, then it holds for the next larger value of k. Therefore by induction k(j) = fkl(T) X(j) (mod-2) for 2 < k < n (257) Either Eq. 249 or Eq. 257 can be used to give the interstage relationships between the sequences produced by different stages of a JHG. In the case of a maximal JHG, every stage will produce the same sequence, but the sequence from each stage will be shifted in time from the sequence produced by every other stage. In the case of a nonmaximal JHG, different stages may produce different sequences, and, as with the MCRG and the MSRG, it is possible under some circumstances for one or more of the stages to be producing the null sequence (all zeros) while other stages are producing nonzero sequences. 7. 6 Output Adder Circuit An output adder can be used with a JHG in the same manner that an output adder can be used with the previously discussed generators. Figure 23 shows a 6-stage [6;5, 3,2] JH JHG with an output adder. The output of the adder is given by n x(j+k)= ai ui(j+k) (mod-2) i=l With X(j) and a defined as in Eqs. 51 and 52, and the content vector U(j), x(j+k) = - U(j+k) (mod-2) X(j) = a [U(j),U(j+l),...,U(j+n-l)] (mod-2) (258) 109

If the JHG is initially loaded with U(j) = E1(0) then Eq. 258 becomes X(j) = a [E1(0), E 1(),...,E(n-1)] (mod-2) a1 a2 a3 a4 5 a6 Grand Mod-2 Adder Output x(j) Fig. 23. A six-stage JHG with an output adder circuit. Applying Theorem 13, the n x n matrix above is a triangular matrix with all ones on the main diagonal and all zeros below. Hence it is nonsingular and its inverse exists, therefore a = X(j) [E1(0), E1(l),...,E1(n-l)]- (mod-2) (259) Equation 259 can be used to determine the proper adder taps to close to obtain any desired n-tuple, X(j), as the initial output of the adder when the elementary load is present. Although an explicit expression for a has not been obtained, a solution has been shown to exist. Thus this technique can always be employed. 110

8. COMPARISON AND SUMMARY OF GENERATORS In the preceding sections of this report, techniques for generating periodic linear binary sequences using the SSRG, MSRG, SCRG, MCRG, and the JHG were considered. We have shown that all of these generators (except the JHG) are equivalent; that is, for any characteristic polynomial an SSRG, MSRG, SCRG, or MCRG can be found which is associated with that polynomial. Any desired starting point of a sequence can be obtained by properly loading the generator. The output adder technique for obtaining a desired starting point applies to each type of generator. We discussed the relationship between the sequences produced by different stages of the same generator. Finally, each of the generators discussed in this report represents a "canonical" or standard form of generator. In this section we will discuss the advantages and disadvantages of the various types of generators and summarize the mathematical relationships which described their operation. Also, two tables are presented: one showing the feedback connections for all the equivalent maximal SSRG, MSRG, SCRG, MCRG, and JHG of 2 < n < 12 stages and another showing the shifts between the sequences produced by adjacent stages of maximal MSRG, SCRG, and MCRG of 2 < n < 12 stages. 8. 1 Advantages and Disadvantages of Different Generators Each of the generators discussed in this report has features which makes it suitable for particular applications. Cost, high speed operation, simplicity of wiring, simplicity of the mathematics associated with the operation and availability of component parts will determine which of the generators is most practical. In the following section we will discuss some of the advantages and disadvantages of the specific types of generators we have previously reviewed. The SSRG Advantages The SSRG is popular largely because of the easy mathematics which describe its operation. Hardware for it is readily available. It is 111

similar to the shift register used in digital computers. The starting conditions for "resetting" the SSRG are trivially determined. The SSRG can be easily modified for different characteristic polynomials since all feedback is external to the shift register which requires only changing the outputs of the stages. The SSRG is also useful for "digital filteringtechniques" (Ref. 2) because of the simple one-bit delay between stages of the SSRG. Disadvantages The interstage wiring is two-wire logic consisting of either the "setreset" type of bistable elements or the "shift-destruct" type of bistable elements. Since mod-2 adders in the feedback loop must be cascaded, long propagation and delay times may exist for the feedback signal which limits the upper frequency of operation. With multiple adder networks in the feedback loop, the shift register stages drive unbalanced loads. This imbalance can be overcome by using buffered adders; however, this increases the delay time through the adders. Because of ths shifting and feedback path return, all transfers of the register must be completed before the next shifting pulse can occur. The MSRG Advantages Because the feedback adders are not cascaded, the time delay for the feedback signal is held down. The MSRG uses modular-type construction requiring two basic elements: (1) a shift stage, and (2) a shift stage and adder. The adders for the MSRG can be gate control circuits instead of conventional adders (Ref. 2). Every stage except the last has balanced loading. The MSRG is an ideal form of generator for generating sequences in a digital computer. A check of the low-order bit is required. If it is "zero, " the contents of the accumulator in the computer are simply right shifted. If it is a "one," then bit-wise exclusive OR the feedback taps to the accumulator and right shift the contents. The MSRG is a common form of storage register for error correcting codes (Ref. 5). As an added feature, the MSRG can be used as a BA matrix computer (see Section 4. 6). Disadvantages Like the SSRG, the interstage wiring of the MSRG is two-wire logic. The starting conditions for "resetting" the MSRG are more complicated than for the SSRG. The MSRG cannot be easily modified for different characteristic polynomials because the adder network is interstage. The last stage of the generator may be required to drive many adder inputs. The return path of the generator may be physically long requiring long propagation times. Because of the shifting and feedback path return of the MSRG, all transfers of the register must be completed before the next shifting pulse can occur. The SCRG Advantages The interstage connections utilize one-wire logic which is simpler than the two-wire logic used with the SRG's. In some forms, the complement stage requires fewer components to construct than the 112

shift stage. The feedback connections can be easily modified for different characteristic polynomials since all feedback is external to the complement register. It is possible to obtain large uniform delays between the sequences obtained from adjacent stages of the SCRG. Also, in many instances the SCRG for a given characteristic polynomial requires fewer feedback adders than does the equivalent SSRG or MSRG. As an example, for the maximal characteristic polynomial (7, 6, 5, 4,3,2, 0) the feedback equation for the SCRG is [7, 6, 0] SC requiring one mod-2 adder while the equivalent SSRG and MSRG have the feedback equations [7, 5,4, 3, 2, 1,0] SS and [7, 6, 5,4, 3, 2, 0] MS, respectively, both requiring five mod-2 adders. On the other hand, some SCRG's require more adders than the equivalent SSRG or MSRG. Disadvantages The mathematics of the SCRG deals with polynomials in the variable (1 + 5)k bringing in the mod-2 binomial coefficients which complicate the equations that describe its operation. Consequently, the starting condition for "resetting" the SCRG is more difficult than for the SSRG. Since the mod-2 adders in the feedback loop must be cascaded, long propagation time may have a feedback signal which limits the upper frequency of operation. The complement register stages drive unbalanced loads because of multiple adder networks in the feedback loop. Because of the shifting and feedback path return of the SCRG, all transfers of the register must be completed before the next shifting pulse can occur. The MCRG Advantages The MCRG uses one-wire logic in its interstage connections like the SCRG. In some forms, the complement stage requires fewer components to construct than does the shift stage. The feedback adders are not cascaded, so that the time delay for the feedback signal is reduced in comparison with the time delay for the SSRG and the SCRG. Every stage except the last has balanced loading. The MCRG uses modulartype construction requiring two basic elements: (1) a complement stage, and (2) a complement stage and adder. Another feature which may be useful is the variable interstage delay between successive stages of the MCRG. Disadvantages The mathematics of the MCRG deals with polynomials in the variable (1 + ~)k bringing in the mod-2 binomial coefficients which complicate the equations describing its operation. The starting conditions for "resetting" the MCRG are more complicated than those for the SSRG, MSRG, or SCRG. The feedback connections cannot easily be modified for different characteristic polynomials because the adder network is interstage. The last stage of the generator may be required to drive many adder inputs. The return path of the generator may also be physically long requiring long propagation time. Because of the shifting and feedback path return of the MCRG, all transfers of the register must be completed before the next shifting pulse can occur. 113

The JHG Advantages In the JHG generator, all feedback loops are localized and extend only to adjacent stages. Thus there are no long return propagation paths. Because the shifting and feedback paths are localized, the JHG is ideal for high-frequency operation. For long JHG's, the final stages can operate independently of the first stages. This feature allows the pulsing of the generator at a rate higher than the propagation time required for the pulses to propagate to the end of the generator. All of the inputs and loadings of the JHG are balanced. It is the most "modular" of all generators. Disadvantages We do not understand the mathematics underlying the operation of the JHG. It cannot easily be modified to a different sequence generator because the characteristic polynomial is a function of the type of stages employed. Not all of the characteristic polynomials are associated with a JHG. The minimum number of adders required is always the maximum number of adders that can be used. 8. 2 Mathematical Relationships for the Different Generators (Summary) A summary of the relationships developed for the different types of generators is given below. 1. The A Matrix: A = [a j]nxn SSRG a, = a... 1 2 < i < n (34) 1, 1- 1 - ai = 0 otherwise where c. are the feedback taps, cn = cO - 1. 1 n MSRG a. = Ci 1 in i -1 a. - 1 2 < i < n (66) i, i-1 - -i a. = 0 otherwise where c. are the feedback taps, co = c = 1. 114

SCRG a 1 = c1 + 1 (mod-2) aI I = c. 2 j < n a.. = 1 2 < j < n (113) j,] a.. 0 =1 2 < j _< n j,j-1 a.. = 0 otherwise 1,] where c. are the feedback taps, c = c 1. 1 n] 0MCRG a.. =1 1 j < n-1 aj+.,j = 1 1<j n-1 ~a. = c. 1 < i < n- 1_ (188) a = cn- + 1 (mod-2) a.. = 0 otherwise 1,J where c. are the feedback taps, cO = c - 1. JHG a 1 1<i <n-1 a.. - c. 1,1i 1ci (230) a.. = 1 2 < i < n a.. = 0 otherwise where c. = 1 if the i-th stage is a complement stage, c. = 0 otherwise. 1 2. The Characteristic Polynomial: the coefficients, bk, of the characteristic polynomial are given in terms of the feedback taps, ck. SSRG bk = cnk (38) MSRG bk = ck (69) 115

n-k SCRG bk = j (d)n-i i (mod-2) (145) i= k B = R3 * C (mod-2) (146) n MCRG bk = j (d )ci i (mod-2) (193) i=k B = R2 * C (mod-2) (194) JHG no generalized equation; the characteristic polynomial may be determined by evaluating the determinant f(4) = IA+ II (mod-2) (6) from the recursion relation fn() = (cn + ) fn-1() + fn-2(5) (mod-2) (237) or by the method described in Section 7. 3. 3. The Feedback Equation: the feedback taps, ck, are determined from the coefficients, bk, of the characteristic polynomial SSRG ck = bn-k (38) MSRG ck = bk (69) n SCRG k = - (dnk)i bi (mod-2) (150) i=n-k C = R 1 B (mod-2) (149) n MCRG ck = L (dk)i bi (mod-2) (196) i=k C = R 2 B (mod-2) (195) JHG neither an equation nor a practical method has yet been determined for finding the feedback taps of the JHG associated with a particular characteristic polynomial. 116

See Section 8. 3 for a table of all equivalent maximal generators of length 2 < n < 12. 4. Initial Loading: the initial contents of the generator at time j, {ul(j), u2(j),...,un(j)}, necessary to obtain a desired n-tuple of consecutive bits {un(j), Un(j+1),...,u (j+n-1)} as the starting output of the n-th stage can be determined as follows: SSRG Ui(j) = un(j+n-i) (43) U(j) = I* * V (j) (mod-2) (45) n-i MSRG u.(j) = Ci+k n(j+k) (mod-2) (78) 1 k=0 U(j) = FM Vn(j) (mod-2) (80) n-i SCRG ui(j) = 3 (dk)n-i Un(j+k) (mod-2) (165) k=0 U(j) = R4 Vn(j) (mod-2) (166) n-i n MCRG ui(j) = L (d)k i ck un(+m) (mod-2) (199) m=0 k=i+m U(j) FM * R1 ~ Vn(j) (mod-2) (200) JHG (desired output at first stage) U(j) = P1 V1(j) (mod-2) (247) where P1 defined by Eq. 245 is T -1 E (1)T E 1 E (n-1)T 117

5. Interstage Relationships: depending upon the type of generator used and upon whether it is maximal, two different stages, i and k, may produce (1) the same sequence, Xi(j) = Xk(j); (2) the same sequence but shifted in time, Xi(j) = Xk(j+Jik); (3) entirely different sequences. Regardless of the relationship, every sequence produced by a generator will obey the sequence law of the generator. A summary of these relationships for the generators discussed in this report is given below. SSRG: For every SSRG, Xi(j) = Xi+k(j+k) (48) MSRG: (1) The maximal MSRG, If two adjacent stages, i and i+1, are not separated by an interstage adder, then Xi(j) = Xi+l(j+l) (82) If the two stages are separated by an interstage adder, then Xi(j) = Xi+(j+Ji i+) (83) The shift Ji i+. between the i-th stage and the (i+l)-th stage can be determined from the BA matrix for the generator using the procedure described in Section 4. 5. 1. (2) The nonmaximal MSRG, If two adjacent stages, i and i+l, are not separated by an interstage adder, then as in the maximal case Xi(j) = Xi+l(j+l) If the two stages are separated by an interstage adder, then they may produce the same sequences 118

shifted in time or they may produce different sequences depending on the partial shift-and-add property of the nonmaximal sequence. SCRG: For every SCRG, Vil(j) = H * Vi(j) (mod-2) 2 < i < n (167) and if c = 1, then n Vi(j) = G Vi_(j) (mod-2) 2 < i < n (171) (1) Maximal SCRG: Xi1(j) = Xi(j+K) (174) where K can be found from the BA matrix as the solution to the equation A = A + I (mod-2) (175) (2) Nonmaximal SCRG with irreducible characteristic polynomial, if the shift-and-add property holds for a shift of 1, then every stage produces the same sequence shifted in time; otherwise, if there are m different sequences that obey the characteristic sequence law of the generator, then every set of k consecutive stages of the SCRG (k < m) will produce k different sequences. (3) Nonmaximal SCRG with factorable characteristic n polynomial, if c = 1 and 3 c = 1, then the n i=O 1 sequences produced by every stage of the SCRG will obey the same sequence law (Theorem 8). MCRG: (1) Maximal MCRG, If: two adjacent stages are not separated by an interstage adder, Xi(j) = Xi+l(j+K) (217) 119

where K can be determined from the BA matrix as the solution to the equation A = A + I (mod-2) If two adjacent stages are separated by an interstage adder, then Xi(j) = Xi+l(j+Ji i+ ) and Ji i+1 can be determined by the method discussed in Section 6. 5. 1. (2) Nonmaximal MCRG with irreducible characteristic polynomial, for two stages, i and i+1, not separated by an interstage adder, if the shift-and-add property holds for a shift of 1 then Xi(j) = Xi+i(j+K) (224) where K is the solution to the equation A =A + I (mod-2) otherwise, the two sequences will be different. (3) Maximal MCRG with factorable characteristic polynomial, the sequence produced by each stage of the MCRG obeys the same sequence law as the sequence produced by the last stage (Theorem 11). See Section 8. 4 for a table of interstage shifts for all maximal generators, except the JHG, of length 2 < n < 12. 6. Output Adder Circuit: the adder taps, a, which must be closed to obtain a specific n-tuple [x(j), x(j+l),...,x(j+n-1)], as the initial output of the adder when the generator is initially loaded with U(j) = E1(0) can be determined from the following equations. 120

i SSRG: a = L cik x(j+k-1) (mod-2) (62) 1 k=1 a = X(j) * FA (mod-2) (61) MSRG: a. = x(j+i-1) (108) a = X(j) (109) i i-m SCRG: a. = m1 (d - ) 1-k ck x(j+m-1) (mod-2) (180) 1G mi [k=0 m-1 -11-k K m=l k=O a = X(j) * R2 FA (mod-2) (179) i-1 MCRG: ai = (d ).1 x(j+m) (mod-2) (226) 1 m=0 a = X(j) * R2 (mod-2) (225) JHG: a = X(j) [E1(0), E (1),..,E1(n-1)]] (mod-2) (259) = X(j) P (mod-2) 8. 3 Equivalent Maximal Generators Table I shows all the maximal characteristic polynomials of degree 2 < n < 12 and their associated SSRG, MSRG, SCRG, MCRG, and JHG's. The polynomials and feedback equations are given in octal form to conserve space. An example is given below to illustrate the use of the table. Example Consider the (7,5, 4, 3, 0) maximal characteristic polynomial. To find the octal representation of this polynomial, write the coefficients in descending order as a sequence of ones and zeros, i. e., exponent - 7 6 5 4 3 2 10 polynomial - 1 0 1 1 i 0 0 1 Group the binary representation by threes, adding zeros on the left if necessary. The above polynomial then becomes 121

0 1 0, 1 1 1, 0 0 1 This is a binary number which can be converted to an octal number using the following conversions: Binary = Octal 000 = 0 001 = 1 010 = 2 011 = 3 100 = 4 101 = 5 110 = 6 1 1 = 7 Under this transformation 010-2 111-7 1 1 1 -7 001- 1 and the octal representation of the polynomial is 271. Looking in Table I under N = 7 (for a 7-stage register), the characteristic polynomial, 271, is found in the first column labeled POLY. Reading across the row, the octal representations of the feedback equations associated with this polynomial are given. POLY SSRG MSRG SCRG MCRG JHG 271 235 271- 313 323 211 310 The feedback equations for the SSRG, MSRG, SCRG, and MCRG are found by expanding the octal numbers. That is, For the SSRG, feedback taps - 7 6, 5 4 3, 2 1 0 235 = 0 1 0, 0 1 1, 1 0 1 - [7,4,3,2,0]SS 122

Table I EQUIVALENT GENERATORS FOR N 4 2 1 EQUIVALENT GENERATORS FOR N 8 POLY SSRG MSRG SCRG MCRG JHG POLY SSRG MSRG SCRG MCRGJHG 00007 00007 00007 00007 00007 00005 00006 00435 00561 00435 00661 00433 00406 00540 00007 00007 00007 00007 00007 00005 00006 00453 00651 00453 00771 00477 00537 00772 00455 00551 00455 00471 00471 00567 00756 00515 00545 00515 00765 00537 00466 00554 00537 00765 00537 00545 00515 00623 00711 00543 00615 00543 00515 00545 00513 00722 00545 00515 00545 00615 00543 00455 00664 I EQUIVALENT GENERATORS FOR N = 3 00551 00455 00551 00455 00551 00417 00760 00561 00435 00561 00735 00567 00471 00634 POLY SSRG MSRG SCRG MCRG JHG 00607 00703 00607 00477 00771 00757 00767 00615 00543 00615 00537 00765 00452 00524 00013 00015 00001 00013 00015 00013 00016 00651 00453 00651 00607 00703 00505 00642 00015 00013 00015 00015 00013 00011 00014 00703 00607 00703 00453 00651 00535 00672 00717 00747 00717 00613 00643 00533 00732 00747 00717 00747 00763 00637 00713 00723 00765 00537 00765 00543 00615 00653 00725 1 EQUIVALENT GENERATORS FOR N: 4 POLY SSRG MSRG SCRG MCRG JHG 1 — --- ---- 1EQUIVALENT GENERATORS FOR N =9 00023 000.31 00023 00031 00023 00025 00032 00031 00023 00031 00037 00037 00033 00035 POLY SSRG MSRG SCRG MCRG JHG 01021 01041 01021 01443 01423 01162 01234 01033 01541 01033 01743 01437 01056 01350 01041 01021 01041 01063 01461 01431 01461 01055 01321 01055 01563 01473 01415 01541 1 EQUIVALENT GENERATORS FOR N = 5 01063 01461 01063 01423 01443 01152 01254 )7 01131 01151 01131 01113 01511 01243 01612 CAD POLY SSRG MSRG SCRG MCRG JHG 01137 01751 01137 01713 01517 01145 01514 01151 01131 01151 01533 U1553 01341 01416 00045 00051 00045 00073 00067 00057 00076 01157 01731 01157 01333 01555 01047 01710 00051 00045 00051 00057 00075 00046 00')54 01167 01671 01167 01473 01563 01377 01776 00057 00075 00057 00067 00073 00043 00070 01175 01371 01175 01773 01577 01035 01560 00067 00073 00067 00051 00045 00041 00060 01207 01605 01207 01577 01773 01276 01372 00073 00067 00073 00075 00057 00047 00074 01225 01245 01225 01137 01751 01006 01300 00075 00057 00075 00045 00051 00063 00071 01243 01425 01243 01317 01715 01633 01663 01245 01225 01245 01517 01713 01475 01571 01257 01725 01257 01617 01707 01044 01110 01267 01665 01267 01157 01731 01547 01715 01275 01365 01275 01257 01725 01517 01745 01317 01715 01317 01027 01641 01327 01726 1 ECJIVALENT GENERATORS FOR N = 6 01321 01055 01321 01167 01671 01201 01402 01333 01555 01333 01267 01665 01365 01536 POLY SSRG MSRG SCRG MCRG -JHG 01365 01275 01365 01707 01617 01173 01674 01371 01175 01371 01207 01605 01137 01764 00103 00141 00103 00165 00127 00106 00130 01423 01443 01423 01041 01021 01543 01615 00133 00155 00133 00111 00111 00135 00156 01425 01243 01425 01641 01027 01433 01661 00141 00103 00141 00163 00147 00126 00132 01437 01743 01437 01541 01033 01427 0171 00147 00163 00147 00103 00141 00145 00151 01443 01423 01443 01461 01063 01523 01625 00155 00133 00155 00133 00155 00125 00152 01461 01063 01461 01,021 01041 0131 01346 00367- 00147 00163 00127 00165 00101 00140 01473 01563 01473 01321 01055 01236 01362 01517 01713 01517 01751 01137 01263 01632 01533 01553 01533 01511 01113 01315 01546 01541 01033 01541 01231 01145 01057 01750 01553 01533 01553 C1131 01151 01361 01436 1 EQUIVALENT GENERATORS FOR N = 7 01555 01333 01555 01731 01157 01067 01730 01563 01473 01563 01671 01167 01001 01400 01577 01773 01577 01371 01175 01217 0742 POLY SSRG MSRG SCRG MCRG JHG 01605 01207 01605 01175 01371 01013 01640 --- 00301 00203 00277 00375 00315 00101617 01707 01617 01275 01365 01103 01604 00203 00301 00203 00277 00375 00315 00331 01665 01267 01665 01555 01333 01241 01412 00211 00221 00211 00217 00361 00256 00272 01671 01167 01671 01055 01321 01375 01576 00217 00361 00217 00357 00367 00307 00361 01707 01617 01707 01725 01257 01667 01733 00221 00211 00221 00367 00357 00227 00364 01713 01517 01713 01225 01245 01206 01302 00235 00271 00235 00247 00345 00253 00352 01715 01317 01715 01425 01243 01114 01144 00247 00345 07247 00323 00313 00222 00244 01725 01257 01725 01365 01275 01032 01260 00253 00325 00253 00203 00301. 00357 00373 01731 01157 01731 01665 01267 01062 01230 00271 00235 00271 00313 00323 00211 00310 01743 01437 01743 01145 01231 01016 01340 00277 00375 00277 00253 00325 00241 00302 01751 01137 01751 01245 01225 01477 01771 00301 00203 00301 00325 00253 00204 00220 01773 01577 01773 01605 01207 01405 01501 00313 00323 00313 00345 00247 00333 00355 $ 00323 00313 00323 00235 00271 00267 00366 00325 00253 00325 00375 00277 00275 00336 00345 00247 00345 00271 00235 00225 00324 00357 00367 00357 00211 00221 00213 00350 00361 00217 00361 00221 00211 00305 00321 00367 00357 00367 00361 00217 00216 00270 00375 00277 00375 00301 00203 00246 00262

Table I (Cont.) 1 EQUIVALENT GENERATORS FOR N = 10 N =11 (Cont. POLY SSRG MSRG SCRG MCRG JHG POLY SSRG MSRG SCRG MCRG JHG 02011 02201 02011 03205 02413 03417 03703 04365 05361 04365 06037 07603 06367 07571 02033 03301 02033 02305 02431 03165 03271 04415 05411 04415 05007 07005 05735 06736 02047 03441 02047 02145 02461 03247 03625 04423 06211 04423 05607 07035 04063 07140 02055 02641 02055 02745 02475 03127 03651 04445 05111 04445 04707 07071 05051 06242 02145 02461 02145 03465 02547 03073 03561 04451 04511 04451 06307 07063 04047 07440 02157 03661 02157 03265 02553 02102 02410 04473 06711 04473 04107 07041 05105 06422 02201 02011 02201 03375 02773 02077 03760 04475 05711 C4475 07107 07047'04407 07404 02213 03211 02213 03575 02767 02731 03156 C4505 05051 04505 07647 07137 05557 07666 02305 02431 02305 03255 02653 02173 03570 04511 04451 04511 05247 07125 05567 07566 02327 03531 02327 02355. 02671 02317 03714 04521 04251 04521 06447 07013 05007 07402 02347 03471 02347 03315 02633 02743 03436 04533 06651 04533 07047 07007 04161 06160 02363 03171 02363 03615 02617 02437 03742 04563 06351 04563 06747 07173 05403 07006 02377 03771 02377 02415 02605 02371 03174 04565 05351 04565 05747 07175 05357 07672 02415 02605 02415 03601 02017 03015 03301 04577 07751 04577 04347 07161 04251 06250 02431 02305 02431 03301 02033 02506 02612 04603 06031 04603 06367 07363 04213 07210 02443 03045 02443 02541 02065 02246 02624 04617 07431 04617 04767 07371 05501 06026 02461 02145 02461 03441 02047 02152 02530 0465 06531 04653 07467 07317 05421 06106 02475 02745 02475 02641 02055 02126 02650 04655 05531 04655 04467 07311 04677 07754 02503 03025 02503 03121 02123 02452 02522 04671 04731 04671 05667 07335 05141 06062 02527 03525 02527 03421 02107 03657 03727 04707 07071 04707 06127 07243 04311 06230 02553 03265 02553 03661 02157 03367 03675 04731 04671 04731 06727 07273 05103 07022 02605 02415 02605 03771 02377 02603 03406 04745 05171 04745 06227 07223 04321 06130 02617 03615 02617 03171 02363 02035 03340 04767 07371 04767 04027 07201 04115 06620 02627 03515 02627 02671 02355 02161 03070 05001 04005 05001 C5403 06015 07677 07757 02641 02055 02641 U2231 02311 02451 0312205007 07005 05007 06403 0601" 06171 06361 02707 03435 02707 02251 02251 02231 03144 05023 06205 05023 07603 06037 05136 05722 02745 02475 02745 02311 02231 02641 03026 05025 05205 05025 04603 06031 04204 04410 02767 03575 02767 03211 02213 02621 03046 05051 04505 05051 04303 06061 06465 06545 02773 03375 02773 02011 02201 02017 03700 05111 04445 05111 07243 06127 06147 07461 03023 03103 03023 02503 03025 03457 03723 05141 04145 05141 06543 06153 04556 05664 03025 02503 03025 03103 03023 02054 02320 05155 05545 05155 04143 06141 04656 05654 03045 02443 03045 02143 03061 02142 02'30 05171 04745 05171 05343 06165 04732 05334 03067 03543 03067 03043 03043 03003 03401 05177 07745 05177 06343 06163 06073 07341 03103 03023 03103 02123 03121 02112 02510 05205 05025 05205 07363 06367 04030 04300 03117 03623 03117 03323 03133 02212 02504 05221 04225 05221 06163 06343 05326 05532 03133 03323 03133 03623 03117 03273 03565 05235 05625 05235 04563 06351 04014 04600 03171 0.2363 03171 03763 03177 03335 03355 05247 07125 05247 07063 06307 06435 06705 03177 03763 u3177 02363 03171 02422 02442 05253 06525 05253 05463 06315 05272 05352 03211 02213 03211 03573 03367 02673 03566 05263 06325 05263 06263 06323 06135 06721 03265 02553 03265 03733 03337 02735 03356 05265 05325 05265 05263 06325 06315 06631 03301 02033 03301 02653 03255 02501 03012 05325 05265 05325 06323 06263 06233 07311 03323 03133 03323 03753 03277 02277 03764 05337 07665 05337 07723 06277 06313 07231 03337 03733 03337 02553 03265 02421 03042 05351 04565 05351 06623 06233 06613 07215 03375 02773 03375 02413 03205 02763 03476 05357 07565 05357 05623 06235 06643 07055 03427 03507 03427 02107 03421 02307 03614 05361 04365 05361 05023 06205 06153 07261 03435 02707 03435 02707 03435 02343 03434 05371 06765 05373 04423 06211 04006 05400 03441 02047 03441 02547 03465 02513 0351205403 06015 05403 07413 06417 05227 07512 03471 02347 03471 03247 03453 02607 03606 05411 04415 05411 06013 06403 04655 06654 03507 03427 03507 02527 03525 02623 03446 05421 04215 05421 05613 06435 05777 07776 CI. 03515 02627 03515 02327 03531 02155 03330 05463 06315 05463 05513 06455 04175 06760 03525 02527 03525 03427 03507 02331 03154 05477 07715 05477 07113 06447 05323 07132 03531 02327 03535 02627 03515 02447 03622 05501 04055 05501 04653 06531 05455 06646 03543 03067 03543 03C67 03543 02525 03252 05513 06455 05513 05253 06525 04137 07720 03575 02767 03575 03367 03573 02661 03066 05531 04655 05531 07053 06507 05315 06632 03615 02617 03615 03177 03763 03407 03603 05537 07655 05537 04053 06501 04527 07524 03623 03117 03623 03277 03753 02526 02652 05545 05155 05545 07553 06557 05645 06456 03661 02157 03661 03337 03733 02346 02634 05557 07555 05557 06153 06543 04553 07264 03733 03337 03733 02157 U3661 03143 03431 05575 05755 05575 04353 06561 05235 06712 03763 0 3 1'77 03763 02617 03615 02174 02370 05607 07U35 05607 05373 06765 04355 06670 03771 02377 03771 02017 03601 02626 02646 05613 06435 05613 07773 06777 04751 06274 05623 06235 05623 04173 06741 04041 06040 05625 05235 05625 07173 06747 04201 06010 05657 07535 05657 04473 06711 05253 07252 05667 07335 05667 07273 06727 05643 07056 05675 05735 05675 06673 06733 05067 07542 ~1 ~~~EQUIVALENT GENERATORS FOR N = 11 05711 04475 05711 04533 06651 04447 07554 05733 06675 C573A 06733 06673 04473 07344 POLY SSRG MSRG SCRG MCRG JHG 05735 056775 0735 05733 06675 04257 07650 05747 07175 05747 06233 06623 04517 07624 04005 05001 04005 06417 07413 05032 05302 05795 05575 05755 07633 06637 04457 07644 04027 07201 04027 04617 07431 07257 07653 06013 06403 06013 07005 05007 05416 05606 04053 06501 04053 04317 C7461 05062 05142 06015 05403 06015 04005 05001 04020 04100 04055 05501 04055 07317 07467 05576 05766 06031 04603 06031 05205 05025 07367 07573 04107 07041 04107 05657 07535 04622 05114 06037 07603 06037 06205 05023 06055 06641 04143 06141 04143 06557 07553 06103 07021 06127 07243 06127 04445 05011 04316 05630 04145 05141 04145 05557 07555 04642 05054 06141 04143 06141 05545 05155 06123 07121 04161 04341 04161 04757 07571 04262 05150 06153 06543 06153 04145 05141 06113 07221 04173 06741 04173 05357 07565 04426 05504 06163 06343 06163 07745 05177 04436 05704 04215 05421 04215 06777 07773 07517 0762706205 05023 06205 04365 05361 04516 05624 04225 05221 04225 05177 07745 04314 04630 06211 04423 06211 06765 05373 06377 07771 04237 07621 04237 04577 07751 06205 06411 06227 07223 06227 06165 05343 04326 05530 04251 04521 04251 05477 07715 07467 07547 06233 06623 06233 04565 05351 04562 05164 04261 04321 04261 06277 07723 04344 04470 06235 05623 06235 07565 05357 04722 05134 04317 07461 04317 05537 07655 04116 05620 06263 06323 06263 05265 05325 04466 05544 04321 04261 04321 05337 07665 04162 05160 06277 07723 06277 07665 05337 04546 05464 04341 04161 04341 07237 07627 04452 05344 06307 07063 06307 07125 05247 05072 05342 04347 07161 04547 04237 07621 04522 05124 063.15 05463 06315 06525 05253 06425 06505 04353 06561 04353 06637 07633 04146 05460 06323 06263 06323 06325 05263 05056 05642 06325 05263 06325 05325 05265 05146 05462

Table I (Cont.) N = 11 (Cont.) N =12 (Cont.) POLY S5RG MSRG CRG& MCRG JHG POLYO SSRG MSRS SCR MOCRG JHG 06343 06163 06343 04225 05221 06245 06451 10541 10321 10541 16701 10167 16757 17373 06351 04563 06351 05625 05235 07177 C7763 10553 15321 10353 157 1 10173 14315 1546 06367 07363 06367 05025 05205 07477 07747 10605 12061 10605 15341 10353 14643 16131 06403 06013 06403 04415 05411 05123 07122 1o663 14661 10663 17141 10317 15443 16115 06417 07413 06417 06015 05403 04265 06550 10731 11561 1-J731 12241 10245 10356 13560 06435 05613 06435 04215 05421 04001 06'00 10737 17561 10737 14241 10243 11552 12554 06447 07113 06447 07715 05477 04645 06454 11015 13011 11015 11411 11031 10437 17610 06455 05513 06455 06315 05463 C05017 07602 11067 16611 11067 16611 11067 12525 15252 06501 04053 36501 07655 05537 04253 07250 11075 13611 11075 15611 11073 11037 17604 0657 07053 06507 04655 05531 05145 06462 11147 16311 11147 14711 11163 13451 14516 06525 05253 06525 06455 0551? 04057 07640 11163 14711 11163 16311 11147 13261 14326 06531 04653 06531 04055 05501 05131 06322 11177 17711 11177 13311 11155 10363 16360 U654- 06153 06543 07555 05557 04513 07224 11271 11651 11271 10151 11301 11515 15554 U6557 07553 06557 05155 05545 05321 06132 11301 10051 11301 i1651 11271 12323 16262 06561 04353 06561 05755 05575 05065 06542 11313 15151 11313 12651 11265 10055 15550 06623 06233 06623 07175 05747 04153 07260 11417 17031 11417 15431 11433 11507 17054 06637 07633 06637 05575 05755 04133 07320 11415 13431 11435 11031 11411 10563 16350 06651 04533 06651 04475 05711 04323 07130 11441 10231 11441 10231 11441 11073 16704 06673 06733 06673 06675 05733 04433 07304 11471 11631 11471 17631 11477 11343 16164 06675 05733 06675 "5675 05735 04127 C7520 11477 17631 11477 11631 11471 11613 16434 06711 04473 06711 07535 05657 04525 06524 11515 13131 11515 13131 11515 12255 15522 06727 07273 06727 07335 05667 04721 06134 11561 10731 11561 12331 11545 12551 14552 06733 06673 06733 05735 05675 04275 06710 11631 11471 11631 14771 11763 11075 15704 06741 04173 06741 06235 05623 05737 07736 11643 14271 11643 13571 11735 10335 1566,0 0674' 07173 06747 05235 05625 05767 07576 11651 11271 11651 10571 11721 11721 14274 06765 05373 06765 07C35 05607 05107 07422 12007 16005 12007 14405 12023 12122 12242 07005 05007 7005 05411 04415 05041 06042 12061 10605 12061 16605 12067 10344 11160 07035 05607 07035 06211 04423 04637 07714 12067 16605 12067 1605 12061 16617 17433 07041 04107 07041 06711 04473 05365 06672 121(7 16305 12147 12705 12165 16437 17613 07047 07107 07047 05711 04475 04373 07370 12165 12705 12165 16305 12147 10164 11340 07053 06507 07053 07311 04467 05761 06176 12247 16245 12247 17545 12337 11242 12124 07063 06307 7763 04511 04451 04337 =7730 12255 13245 12255 14545 12323 11212 12424 07071 04707 07071 05111 04445 05535 06726 12323 14545 12323 13245 12255 15353 16565 07107 07047 07107 06651 04533 05617 07616 12417 17000 12417 13425 12435 13176 13746 07113 06447 07113 04251 04521 04375 06770 12435 13425 12430 17o25 12417 14031 14601 07 25 05247 07 25 04451 04551 04211 06210 12515 13125 123l 1-'i25 12313 16333 16663 to 07537 07647 G0737 05051 04505 04111 06220 12623 14466 12623 11765 12771 10152 12540 CA C7161 04347 07161 07751 04577 05527 07526 12705 12165 12765 15665 12673 11206 13024 C7 73 06747 07173 06351 04563 04771 06374 12727 16565 12727 11265 12651 10542 12150 07175 05747 07175 05351 04565 04105 06420 12735 1356o 12730 1226t 12645 15563 16355 C7201 04027 07701 07371 04767 C5157 07662 12753 1536s 12733 1j65 12601 15137 17645 07223 06227 o72723 5171 04745 05647 07456 13011 11015 13011 11435 13431 12537 17552 C7737 07627 C7237 07571 04757 05457 07646 13107 16115 13107 12135 13505 12657 17s32 07243 06127 07243 07071 04707 05547 07466 13125 125 1251 13125 16535 13527 10611 14430 07273 06727 07273 04671 04731 04755 06574 13131 11516 13131 13535 13535 12727 17272 07317 07467 07317 06531 04653 05671 06356 13245 12255 13245 17575 13737 10443 16110 07335 05667 47335 =4731 04671 0575 36636 13275 1365) 1327 1u175 13701 13761 14376 07363 06367 C07363 060?1 04603 04567 07564 13425 12435 13425 14ul1 13003 13237 17626 07371 04767 07371 07431 04617 05751 06276 13431 11435 13431 11015 13011 10125 15240 07413 06417 07413 05=5 04005 06475 06745 13503 14135 13503 10115 13101 11111 14444 07431 04617 07431 07201 04027 04124 04520 13505 12135 13505 16115 13107 10245 15120 Li7461 04317 07461 06501 04053 06635 06715 13565 12735 13565 12315 13145 1333 16366 07467 07317 07467 0551o 04.55 06011 06201 1365 1 13075 13611 16365 13347 12405 15012 07535 05657 075?5 37L4 04107 06663 037155 13655 13270 13605 1555 13321 12771 14772 C7553 06557 07553 06141 04143 04756 05674 13663 14675 13663 11155 13311 12211 14422 07555 05557 07555 5 14 0414 06723 07135 13677 17675 13677 14155 13303 12221 14222 07565 05357 C7565 06741 04173 06273 07351 1 3701 10175 13701 13655 13275 13401 14016 07603 06C37 C07603 5346 1 04365 04206 05410 14127 16503 14127 13517 17135 14715 15471 07621 C04237 07621 07161 04347 06653 07255. 14135 13503 14'135 lu517 17121 16227 17223 07627 07237 07627 04161 04341 06533 07325 14221 10440 14221 10757 17361 10502 12050 07633 06637 07633 06561 04353 06317 07631 1422'7 1644, 14227 16767 17367 10212 12420 07647 07137 07647 06u61 s4303 G6167 07561 14271 11643 14271 1315 17315 112U2 12024 C7655 05537 07655 07461 04317 06157 07661 14357 17343 14357 1.7057 17217 14077 17701 C7665 05337 07605 04261 04321 06617 07615 14433 15423 14433 14037 17403 14707 17071 07715 05477 u775 045?1 (042.51 04230 34310 14465 10623 14465 11-637 17471 11752 12574 07723 06277 07723 04321 04261 07307 07433 14501 50523 145=1 15137 17513 10026 13200 07745 05177 07745 05221 04225 07147 07463 14545 10323 14545 13:737 17575 11656 13534 07751 04577 07751 07621 04237 05366 05572 214573 15723 14573.12337 17545 15323 i6265 12117 171U5 12117 11105 12111 17057 17507 14613 15563 14613 13377 17755 11014 11404 12135 13506 12135 15505 12133 15270 15725 14661 10663 14661 14177 17703 16217 17423 14675 13663 14675 11107 17711 10774 11770 14711' lllo 14711 15677 17673 12476 13712 14717 1716 14717 13677 17675 14555 15551 14747 1l363 14747 1lu77 17601 16453 16513 15035 15417 15C53 10077 16401 10405 15010 1 ECJIVALENT GENERATORS FOR N = 12 15053 15213 15C03 14227 16443 12257 17522 15063 14613 15063 13627 16475 10501 14050 POLY 3SRG MSRG 3SC5RG MCRG JHG 15151 11313 15131 12727 16565 12713 16472 15213 15053 15213 17367 16757 12365 15362 10123 14501 10123 16521 10527 13066 133u6 15321 10563 15321 16267 16647 11533 16654 1=151 11301 10151 11721 10571 14545 15151 15341 16353 16341 12067 16605 11707 17074 10173 15701 10173 15321 10553 12316 13462 15365 10273 15365 10467 16621 12335 15662 10175 13700 1I175 13321 1C055 10104 11040 15413 15033 15413 10407 16021 11363 16364 10231 11441 10231 10761 10761 14523 16251 15423 14433 15423 17007 16017 13435 15616 10325 10541 10321 15261 10653 11472 12714 15477 17433 15437 12007 16005 10177 17740 10353 15341 10353 12061 10605 11646 13134 15527 16533 15527 17507 16137 13471 14716 10407 16021 10407 16401 10027 15125 15245 15621 10473 15621 14747 16363 12237 17622 10437 17421 10437 11001 100 Ol 16053 16503 15647 16273 15647 16547 16327 13217 17426 10443 14221 10443 10201 10041 14435 15611 15677 17673 15677 11147 16311 13427 17216 10473 15621 10473 17601 10077 10754 11570 15701 10u73 15701 16647 16267 10675 15730 10517 17121 10517 13101 10115 17357 17567 15723 14573 15723 12247 1624-5 12653 16532 10527 16521 10527 14501 10123 14471 147111 16005 12007 16005 17433 15437 10037 17600

Table I (Cont.) N = 12 (Cont.) POLY SSRG MSRG SCRG MCRG JHG 16021.10407 16021 15033 15413 11413 16414 16027 16407 16027 13033 15415 11773 16774 16047 16207 16047 17233 15457 12505 15052 16115 13107 16115 12133 15505 12445 15112 16207 16047 16207 14373 15743 11611 14434 16237 17447 16237 13773 15775 10135 15640 16245 12247 16245 14573 15723 11245 15124 16273 15647 16273 15173 15713 10331 14660 16305 12147 16305 12673 15665 10631 14630 16311 11147 16311 17673 15677 10561 14350 16317 17147 16317 11673 15671 13103 16046 16363 14747 16363 10473 15621 10155 15540 16407 16027 16407 13413 15035 13753 16576 16443 14227 16443 152153 15 10255 15520 16503 14127 16503 13113 15115 10515 15450 16521 10527 16521 17513 15137 11261 14324 16533 15527 16533 14513 15123 11521 14254 16565 12727 16565 11313 15151 11305 15064 16605 12067 16605 10353 15341 10703 16070 16611 11067 16611 15353 15353- 10343 16160 17025 12417 17025 13003 14015 13376 13766 17031 11417 17031 16003 14007 17267 17327 17057 17217 17057 14203 14043 12216 13422 17105 12117 17105 11103 14111 12776 13772 17121 10517 17121 13503 14135 10554 11550 17147 16317 17147 11703 14171 14451 14511 17163 14717 17163 13303 14155 160t3 16403 17217 17057 17217 17343 14357 10076 13700 17343 14357 17343 14043 14203 11072 12704 17421 10437 17421 11023 14411 14423 16211 17433 15437 17433 12023 14405 10526 13250 17447 16237 17447 13223 14455 11416 13414 17561 10737 17561 17323 14557 11132 12644 17631 11477 17631 11763 14771 12262 12322 17673 15677 17673 11163 14711 14065 15301 17675 13677 17675 17163 14717 12226 13222 1771' 11177 17711 13663 14675 16007 17003 $

For the MSRG, feedback taps - 7 6, 5 4 3, 2 1 0 271 = 0 10, 0, 1 1 1, 0 0 1 - [7,5,4,3,0]MS For the SCRG, feedback taps - 7 6, 5 4 3, 2 1 0 313 = 0 1 1, 0 0 1, 0 1 1 - [7,6,3,1,0]SC For the MCRG, feedback taps - 7 6, 5 4 3, 2 1 0 323 = 0 1 1, 0 0, 0 1 1 - [7,6,4,1,0]MC To find the feedback equations for the JHG, remember that there is no zero term in the feedback equation. The conversion from the octal representation proceeds as follows: from the table, the two JHG equations which are associated with the 271 characteristic polynomial are represented by the octal numbers 211 and 310. Begin numbering the feedback taps starting on the far right with 1 instead of 0 and neglect the leading 1 on the left. The transformation of octal number 211 then becomes feedback taps - 7, 6 5 4, 3 2 1 211 = 0 1 0, 0 0 1, 0 01 [7;4,1]JH - neglect and feedback taps - 7, 6 5 4, 3 2 1 310 = 0 0 1, 0 0 0 - [7;7,)4] - neglect The leading 1 in the octal representation of the feedback law for the JHG permits defining the length n of the generator and also makes each octal feedback equation unique. This leading 1 represents the "n"; in the feedback equation of the JHG. 127

It should be noticed that the two equivalent JHG's, the [7;4, 1]JH and the [7;7, 4]JH are simply reverses of each other as explained in Section 7.3. The reverse polynomial of the POLY entry in Table I is the same as the SSRG octal feedback equation if it is considered as a characteristic polynomial. Note that the MSRG feedback law is identical to the characteristic polynomial, however, it has been included in Table I for completeness. The maximal JHG entries in Table I were determined by considering every possible 2n feedback equations and finding the corresponding characteristic polynomial using Eqs. 233, 234, and 237. A list of all maximal characteristic polynomials was compiled and a search procedure was used to select those feedback equations which correspond to maximal characteristic polynomials. Note that every maximal characteristic polynomial has two corresponding JHG's and the tendency is to conclude that every maximal polynomial has a JHG; however, this statement has not been proved. 8. 4 Interstage Shift for Maximal Generators Table II gives the time shifts between the sequences produced by adjacent stages for all maximal MSRG, SCRG, and MCRG of length 2 < n < 12. For an SSRG the shift is always 1 between stages and is not shown in the table. The following example illustrates the use of Table II. Example Consider the (5, 3,2, 1, 0) maximal characteristic polynomial. The octal representation of this polynomial is 57. From Table II under N = 5^ one finds POLY SCRG MSRG MCRG 57 12 1,20,17,23 12, 1,26, 1 For the SCRG the shift between adjacent stages is always the same and from Table II this shift is found to be K = 12. Thus Xi(j) = Xi+l(j+12) 1 < i < n-1 The feedback law for the MSRG (from Table I) is [5, 3, 2, 1, 0] MS and there are interstage adders between Stages 1 and 2, 2 and 3, and 3 and 4. The first entry under "MSRG" in Table II is 1. This "1" indicates that there is a shift of 1 between stages that 128

Table HII SHIFT BETWEEN SECUENCES FROM SHIFT BETWEEN SECUENCES FROM ADJACENT STAGES WHICF' ARE SEPARATED ADJACENT STAGES WHICH ARE SEPARATED BY AN ADDER FOR GENERATORS OF LENGTH N=2 BY AN ADDER FOR GENERATORS OF LENGTH N=8 POLY SCRG MSRG MCRG POLY SCRG MSRG MCRG 00007 2 1,T2 2,1, 00435 25 1,206A,202,7, 25,24o177,184, 00007 2 1,2~ 291, 00453 243 1,13,172,659, 243,2429,165,64,226,104, 00455 240 1,31,A183,3, 240,186,60,84, 00515 23 1,210,250,L5, 23,22,196,103,141,234, 00537 122 1,134,197,71,117,243, 122,120,155,135, 00543 197 1.59,53,13f, 197,195,35,60, SHIFT BETWEEN SEQUENCES FROM 00545 233 1,45,25UO,20, 233,232109,24, ADJACENT STAGES WHICH ARE SEPARATED 00551 16 1,36,183,3], 16,66,1239241, BY AN ADDER FOR GENERATORS OF LENGTH N=3 00561 231 1~97,202,2C6A 231.230,173,135,18,269 00607 99 1T157,249,99 99,247,218 1 52,105,1 POLY SCRG MSRG MCRG 00615 59 1S138,53 5957,810914 --- --- -~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~~~~~~~~~~~~OS — 00651 13 1 65,172~13~ 13~12,177,1, 00013 3 1,5, 3,1, 00703 157 1,99,249,157, 15795,22991, 0OU15 5 15, 5 4, 00717 141 1,1T5,235,NT50, 21141 141,140*174,1, 00747 115 1,141,21,2.J,235, 115, 115,11421,207,771T 00765 134 1,243,117,71,197,134, 134,132,217,1, SHIFT BETWEEN SECUENCES FROM ADJACFNT STAGFS WHICH ARE SFPARATED BY AN ADDER FOR GENERATORS OF LENGTH N=4 SHIFT ETWEEN ECUENCES FROM ADJACENT STAGES WHICF' ARE SEPARATED POLY SCRG MSRG MCRG BY AN ADDER FOR GENERATORS OF LENGTH N=9 00023 4 1T12T 4,3, POLY SCRG MSRG MCRG 00031 TT 12 1,12 121,6,1, 01021 TAT 1,S503, 130T12911299, 01033 197 1,315,218,L83, 197 196 72,320,156,1T 01041 382 1,503, 382,378,395,1, 01055 275 1,473,468,75, 275,27491939150,326,1, i(_*...A~~ ~ SHIFT BETWEEN SECUENCES FROM 01063 104 1,408,195,413, 104,103.294,1, ADJACENT STAGES WHICH' ARE SEPARATED 01131 140 ],170,506,T40, 140,448,244T1, BY AN ADDER FOR GENERATORS OF LENGTH N=5 01137 53 1,459A3o2,?5,429,234, 53,52,382A233,1T2T 01151 372 1,34C,506,]70, 372,371,244,398,53,1, POLY SCRG t;SRG MCRG 01157 93 1,419,436.-,2,12,260, 93,91,481,46,31, 01167 443 1,69,163,374,241,211T 443,442,501,381,480,1, 00045 18 1,27, 18 17,8,1, 01175 234 ],44,63,239,27,134, 234,233,333,133.185,481,210,1, 00051 14 1,27, 14,12,21,1, 01207 194 1,318,31'1,287, 194,193,161,342,446,94 00J57 12 1,20,17239, 12,11,26,1, 01225 226 1,60,505,4T1, 226,251,75.,4A4,1 00067 19 1,13A28,19, 19,17, 01243 36 1,476,469,71, 36,34330,243270,T 00073 13 1,19,2813, 13,o12,4,20, 01245 286 T61,451,505 0, 286.285,T0146,27,1 00075 20 1923,17,20, 20,13, T01257 453 1,59,288,3 1,447,394, 453,452,2889348.165,1, 01267 461 1,51,S288,3?3,447,410, 461,286,422,340,173,1, 01275 26 1,460,442,470,106T,1, 26,24,380,179,334,1 0131.7 441 1,71,263,3'0,435,370, 441T241,178,1, 0131 2037 1,75,468,473, 237,440,3969464,306,1T SHIFT BETWEEN SECUENCES FROM 01333 501 1,11,341,5C6,181,490, 501,499,129,247,186,1, ADJACENT STAGES WHICH ARE SEPARATED 01365 486 151106,470,442,460, 486R485,309,150,177,1 BY AN ADDER FOR GENERATORS OF LENGTH N=6 01371 278 1,134,27,2O9,63,44, 278,276,99,1, 01423 114 1,398,504,114, 114,110, POLY SCRG MSRG MCRG 01425 476 1, 7 1 469, 47 6, 476,475235,11, 01437 428 1,84,156,12,338,428, 428,427,302,280, 00103 6 1,58A 6,5,44,59, 01443 398 1,114,504,A98, 398.397,449,343 00133 56 1,a8,4,40, 56,35, 01461 4U8 1,413,195,'A J8, 408,313, 00141 58 1,58, 58,57,20,1, 01473 249 1,263,23,47,436,249, 249,247,24,279, 00147 25 1,39.59,25, 25,1 01517 135 1,377,470,784,263,135, 1359134,470,309,724 00155 8 1,48,4,8, 8,6,32,1, 01533 126 ],386,18,308,160,126, 126,125,351,301 00163 39 1925,59,39, 39,37,34,1, 01541 315 1,483,218,215, 315.313,83.269, 01553 386 1,126,160,728,18,386,.386,424,114,212 01555 1 11,490, 181 5J6 341,11, 11,10,197,334,132,305, 01563 263 1,249,436,L7,23,263, 263,262,456,461,19,305A 01577 404 1,108 139,77,134,144,14,404, 404,402,413,488,177,481, SHIFT BETWEEN SECUENCES FROM 01605 318 1,387,311,'18, 318,199,410A374105, ADJACENT STAGES WHICH ARE SEPARATED 01617 327 1,185,376,s55 Js,136,327 7, 37325425,39043,16, BY AN ADDER FOR GENERATORS OF LENGTH N=7 01665 51 1,410,447, 33,288T5 1 51,50,17,256,33,46 01671 69 1,211,241,34,163,69R 69,65,99,444, POLY SCRG MSRG MCRG 01707 185 1,327,136,J05,376,.185, 185,184,136,3,424.32, 01713 377 1,135,263,284,470,377, 377,375,293,136, 00203 7 1,121, 7,5,105,74,55.1, 01715 71 1,370,4359,90,263,71, 7170,84,442 00211 31 1*1210 31.027, 1020.1. 01725 59 1,394,447,341O288,59. 59,57,17,136,12,454, 0021 87 1.41,118,91, 87,86,118,33,96,1, 01731 419 1,260,U12,4C2,436,419, 419,418,76,24,6794 00221 97 1,121,o 97,96,72,120,25,1, 01743 84 1,428,338,]2,156,84, 84,354.246,429, 00235 118 1,19,68,36. 118,116,46,1, 01751 459 1,234,429,25,382,459, 459,457,312,54, 00247 114 1,14,9,10C, 114.113,65,1, 01773 l10 1,404,14,144,134,77,139,108, 108,107,373.405, 00253 21 1,107,102,41, 21,1, 00271'10 1,36,68,19, 10,9,77,1, 00277 19 1,109,26,65,15, 37, 19,17,33,1, 00301 121 1,121, 121.120,23,8, 00313 39 i,89,122,39, 39,38,97,90, 00323 89 1,39,122,8A 9,29,83,40, 00325 107 1,41.102~1C7, 107,106,t11597,81,22, 00345 14 1,100,9l14, 14,12,63,123, 00357 55 1,73,23,12?,105,55, 55,51, 00361 41 1,91,118,41, 41,8, 00367 73 1T55,105,123,23,73, 73,72,105,39, 00.375 109 1,937,15,65,26,109, 109,108, B *

Table E (Cont.) N = 11 (Cont.) SHIFT BETWEEN SECUENCES FROM POLY SCRG MSRG MCRG ADJACENT STAGES WHICH ARE SEPARATED BY AN ADDER FOR GENERATORS OF LENGTH N=10 0 A IT7 BY AN ADDER FOR GENERATORS UF LENGTH M=1004347~~~13921,656,1568,205,188,1471,.1392.1388,492,178.1871,1, 04353 1192 1,856,1962,14,585,671, 1192,1191D161,995,,170623,226,1, POLY SCRG MSRG MCRG 04365 959 1,D3,1247,1405,1567,1786, 959,958,1473,1714,335,1, 04415 433 1,1182,227,630,433.431,198,1, 02011 77 1,1014, 77,76,483,948, 04423 18oUu 1,248,44,B4, 47 1800,1798,1030,752,1995,1, 02033 493 1,531,433.T2, 493,445,687,532, 04445 1524 1,1047,1677,1362, 1524,1683,1493,122,1886,1, 02047 85 1,939,742.,58, 85,81,430,940, 04451 789 1,167,240,1879, 789,788,706,868,1091,1, 02055 181 1,662,159,195, 181,179,810,372,982,844, 04473 1764 1, 24 892, 798,1757,14o4, 1764,575,1688,1, 02145 687 1,t673,667,99, 687,686,582,551,546,336, 04475 72.7 1,594,1364,1969,1792,416, 727,726,1037,3251737,1, 02157 575 14,449,406,02,443,251, 575,574,49,381,786,450, 04505 1680 1,735,1957,1394, 1680,1679,1965,1393,1134,1722,1762,1, 02201 947 1,1014. 947,946,247,554,42,731,699,78, 04511 1259 1,879,204(,167, 1259,1257,1394,1120,956,1, 02213 967 1,57.72,887, 967,966,23,1015,2S0,079,316.58, 04521 1670 1,1509,201,329, 16701669,478,1454,707,1 02305 84 1,856,267,T16, 84,83,874.519,232,941, 04533 1673 1,375,1423,944,1666,1727, 1673,1]672,1618,945,559,1 02327 945 1,79854,13,983,12, 945,852,310,115,56,80, 04563 B98 1,950 1733,18,402, 985, 1098,1097,938,1368,1271,1280,19351, 02347 474 1,55,43,6,538,904, 474,473,290,225,183,551. 04565 1152 1,1 791,2u1,52,206,1295, 1152,1150,1191,191,1340,1610,144,1, 02363 R944 1,80,323,1(C18 41.9,201, 9A4,9143,A6,2050,555481, N04577145B 1.597 5UU,94 30, 9 70,4945, 354 1451,1447537,640,951,1 0233 77 586 1,43,629,247,23,212,975,542, 586,584,1013,439, 04603 842 1,12U6A1B2E,1555, 842,841,8R1672,*771,813,714,1 02415 921 1,205,1B16,818, 921,920,686,131, 04617 889 1, 1159,1883,45,717,1941, 8891881,535,232,.128b,1689,1053,1, 02431 94R 1.916,2A67,.56, 940,939869,799, A04653 1945 1,103,1926,1205, 335, 519 A19451944,1323,518,762,1379T,622,1, 02443 220 1,804.796,39, 220,218,422,889, 046551357 1 1 1381146,176,66,J 925, 1357,1786,411,326,1616,1, 02461 337 1A699A667,673A 337.336,442,955, 04671 10.3 1,A654,124,1532,406,392, 1003,1001,779,380,123,4551437,1, 02475 13U 1T764R954T79,808,259, 130,B128,210,798, 04707 365 A T 1,6831R8P,626,1050,1488, 365,364,899R,1563,1124',1, 02503 756 1,268,260,R88, 756,755,309,805, 04731 1045 1,392,46,1532,104,1654, 1045,1044,1269,209,706,169,610A1, 02527 747 1277,354N,24B316,470, 747,746,354,332, 04745 980T,88O,1361,1899,15O,725, 980,979,239,1343,1793,1, 02553 290 1,734,911,,834T,579, 290,289,95,483,595,157, 04767 625 1 1423,15 79,6,7 5,5A9,1868,1234, 625,530,610,1, 02605 10D 1,818,1016,205 103,102,338,889,323,353,171,5A4, 050C1 1019 1,2037, 1019,1017,1065s], 0A267 764 1,26A,147B'73,757,504, 764,763,229,272,940,114, 050C7 5 3 195198,105, N53,52,1570,1, 02627 765:,259,9b3,E74,442,506, 765,763,841,905,527,300, 05023 251 11797,178F,51 251,250,1870,677,1837,1. 02641 843 1,195,159,652, 843,307,57,896, 05025 lU88 1,1919,203,128 1088,1018.512,1, 02707 992 1,32,628,2L8,173,96, R992,626,186,428, 05U51 368 1,1394,1957,735, 368,364,785,1,.02745 894 1,259,88,,279,954,764 894,142,7749100, 05111 524, 1362,1677,1047, 524,523363696,1414,1, 02767 274 1.75N,164,77T,U118,81,652,547, 274 273,291,58, 05141 1448 1,260,931AT 48, 1448A447,294,215,16D67,1, 02773 848 1,176,764,235,834,973,435,672, 848,552, 05155 112 11824,127T,847,196",223, 112,673,477,1, 03023 355 1,669,1015,355, 355,353,230,1, 05171 1068 1,725,15,I139,1361,88, 1068,1066,56[A,1734,406,1, 03025 268 1,488,260,268, 268,267,92591, 05177 190 1,1858,53,1116,12,153T,1125,379, 190,189,65,311,341,1, 03045 80 4 1R4A9,796FO4, 804,800R732,1 05205 96A 1,128,20A971919, 960,959,1028,18C7,422,647,15311, 03067 992 1,32,595,672,773,992, 992,991,24891, 05221 75 1,127 5,14 2, 1409, 705,704,565,1962,726,1, 03103 669 1,355,1015,669, 669,665.789,1 05235 1114 1,1867,152,41,1848, 18, 1114,98,1582,1629,241,1 03117 712 l'1 12, 76,5 8,T,797, 77712,711,584,202,,, 57,1,052471822 1 226,112 1 1339,1 853,1 596 1822,1821,1121,344,110,1, 03133 898 1,126,6S6,325,36,898, 898,897,730,41,1002,1, 05253 997 1,1,1 3,'a61, 78, T993, 997, 995, 11 53, 1 555,549,1, 03171 80 1,201,41, ]J18,I23,80, 8079,361,820,7701,21846,1, 05263 824 1,1224,2J17,83J,417s,1647, 824,8232017,713,1737,1, 03177 422 1,602,q38.2SA-,175,678,]C08,422, 422,936,862,95~,247,1 N05265 1072 1 195 1,1849,2041,1 98,96 1072,170,778,1362,5921, 03211 57 1,887,72,57, 15756A10015451.342,,E97N5, 6N0 325976 1,96,19R,2C41,1649,11, 951 976,975,706T,1242,1455,1, 03265 734 1,57A,834,,911,734,734,733,929,537,617,9S,16,, 05337 573 1,147 5,19 1, 1036, 222, 7 8,2 67,1145, 573,572,1914,1277t,1704,77,351,1, 03301 531 1,52,433,51, 53],s529,?UO0,06,824,1, 05351 896 1 1295,26 28,2015, 179 1, 896t,895,857,10J77,2029,1, 03323 126 tA9d,36,3-5,6A6,126, 126,125,294, 979,430,15,704,1, 05357 815,1 233,2017,453,1674,1113,69,1629, 815.,813,1372,40,703,1, 03337 623 1.,401,772,:,T766,22,2/2,623, 623,621,9S1,669,811.1, 05361 1089 1,1766,1567,1405,1247,130, 1089,1087,435,1, 03375 176',672,43A, 73,834,235,764,176, l76 174,639, 05373 1527 2. 521,81,f58,12G,746,11P8,]06, 1527,428,1684,1,. L 03427 699 1.325,7-,!,1'16,8774,699, 699,695,549,1, 054O 3 9 1 1 1197,112FA1821, 911,910,1242,578,2038,1, C 3 03435 32 1,96,17,;48,628,372, 32,30,421,775,659,1, 05411 1615 1,63T,227,1182, 1615,1614,1841,1, 0 03441 939 1,35A,742,T39, 939,937,648,223,657,1, 05421 875 1,595,1742,1749, 875,873,1479,16,569,1, 03471 550 1,904,58,,43,550, 550,549,27,173,592,1, 05463 619 1,1429,52,1100,1849,1237, 619,617,1628,1808,420.1 03507 325 1,699,874,l3'16,150,325, 325,323,400,246,474,1, 05477 1696 1,352,87U,1881A137,1603,1997,1344, 1696s,1695870,1989,1645,1, 03515 259 1,506,447,874,983,A59, 259,39,893T623,218,1, 055 1 159,649 73317 159641,4,1224,1231717 03525 277 1,475 -116,(24,B54T277. 277,276,670,107,630.1, 05513 335 1,1713,9632040,750,669, 335,333,1566,11'7,1084,1, 03531 79 1,12,983,113,854,79, 79,77,136,505,932,1, 05531 691 1,925,660,l]706,1463,1381, 691,690,260,938,106,1, 03543 32:,_311992477.2,472,595~12,329.31,184,21,~6265,1,05537107 1 1,941,923,912 810,1989,1396S,213, 107,735S,1502,1, 03575 750 1,547,652F.,10o18.877,164,750, 750,749,925,6&3,408,2O,913,1, 05545 1936,223,1967,847,1274,1824, 1936,1935,1751,72,2038,1673,1162,1, 03615 260 15,04,757,073,147,60s, 260,259,192,374,488,619,406,1, 75557199 5 1950,5.132,582,202,1429.1832, 129903,1989,12631 T37,1,. 03623 312 1,712 39, 48,76,312, 12,311,22,34,740,6 b0,367,1, 05575 1992,1I1 612,05.,T,39 1447,637,1936, 1992,1988,577,1277,581A1, 03661 449 1,251,44,LT92,406,4,49, 449,448,391,674,206,171,54,1, 05607 664 1 1384,172,892,8J8,1327, 664,662,737,2017,1790,901 1471,1, 03733 4ol 1,623,272,~J276,,766,30,772,401, 401,397,664,876,1491, 05613 897 1,1151,192B,~240,12'2,1793, 897,896,1951,18889461,13941.752~2024,121,1 03763 642,422,1~u,T678,175,266,9386602, 602,600,479,509,516,1, 05623 109 1,1939,186;2,862,125,217, 109,590,1223,263,1363,1, 03771 438 1,542,975,212,23,247,629,438, 438,982,43.1, 05625 934,18o91848,41.152,1867, 934,933,1948,839,630,1063,1085,1' *$ 05657 555 1,1493,1362,1524,1158,259,1179,1109, 555,1360,763,1001,1733,1, 05667 1399 1,64,1]2?8,527,2041,q8T2,2Oc,750, 1399,1398,1228,857,334,1508,1360,1, 05675 473,1152,121t,1424,145,722,T85,45 473,472,741,1080,1256,1289,1457,1, 05711 1321 1,416,1792,1969,1364,594,1321,1009,261,A0,637,1, SHIFT BETWEEN SECUENCES.FROM 05733 1636 1,412,2b9,]586,65 3919123,1224, 1636,1635,1534,1152,419128A,178A,1, ADJACENT STAGES 1WHICH ARE SEPARATED 05735 1575 1 945T985A,22,]45 1424,12714,1102, 1575,1573,1307,1725,25,610,741,1 BY AN ADDER FOR GENERATORS OF LENGTH N=11 05747 9o9 1,1139,256,1725,1245,567,1435,1617, 909,908,32,1497,296A1, 05755 56 1,1936,637,1447,539,855,612,111, 56,55,148,2009, 1803,1234,667,1, POLY SCRG MSRG MCRG 06013 3=9 1,1739,203E,30qt, 309,308,1621,1740, 06015 1137 1,1821,112,l1137, 1137,912, 04005 1029 1,2037, 1029,1028,983.554,1495,1, 06031 12U6 1,1555,132T,12.6, 1206,1204,587,843t, 04027 846 1,12u2,394,443, 846,392,670,1597,452,1 06037 1207 1,841,1296,386,358s,1207, 1207,1206~,78,842, 04053 441 1,167,3J1,131S 441,437,1008,376,1673,1, 06127 1504 1,544,1450,767,1870,1504, 1504,1448,304,545 04055 1889 1,317107,t649, 1889,1888,1405,a815,16622,1b55,404,1, 06141 1188,s1,1794 7,1188l, 1188,1186,779,119,159, A86, 04107 218 1,1830,117,92, 218,216,1147,1193,663,1948,101,1, 06153 827 1,1221, 159;,1763,732,827, 827.85,265,1222, 04143 860 1,1188,170,1194, 860,859,1269,113,457,438,1611,1, 06163 1476 1,572,1 78, 58, 1801, 1476 1476,14751522o 1428,558,49,383,573, 04145 600 1,848,93] ~2.50, 600,5981754,1,1, 1797 1,501,1788,1797, 1797,1793,1274,834,1441,252, 04161 874 ]~599,65,1B75* 874,1411,1879,1501,1945,541,1508,1 06211 248 1,1747,44,248, 248,247,R10181471,2025,778,1903,1801, 04173 1109 1.939,487A]A 1730.l323~ 1109,1107,782,2023,1884,862,1187,1, 06227 8U1 1,1247,547,275,1218,801, 801R,8002,46,1381,1754,1248, 04215 1173 1,1749,1742,595. 1173,1172,569,1702,203,262,1931,1976473,1 06233 1172 l876.1374A1292,I1421s1172 1172,913,1933,138,1389,877, 04225 1343 1149,1914,1275, 1343,1341,189,1649,181,384,1665,16, 06235 1939 1,217,1255,862 1862,1939, 1939,1938,1625,204,1391,569736B110, 04237 2023 1,25,1741t,56,18,1948, 2023,1739,1884,1284,1327,1767,282,1, 06263 237 1,1811,1515,1633,939,237, 237,235,1892*625,155,1812, 04251 378 1,329,201,]509, 378,376,1570,22,611,709,1340,1, 06277 1529 1,519,1343,1742,1632,1U54,365,1529, 1529,1528,1343,1713,1683,536,890,520, 04261 706 1,1271,204],774, 706.7059,1815,1063,1778,1652397,1, 063071210 1,8381296,699.45210, 1210,1209.1296,1013,665,839, 04317 869 1,1179,10lJ,1152,1172,1426, 869,867,1300,773,1769,339,1710,1, 06315 1429 1,1237,184,1100, 520,1429, 1429,1428,420,316,924,620, 04321 1342 1,774,2041,1271, 1342,1340,89,279,1109,399,1650,1, 06323 1811 1.237,939,]633t,1515,1811, 181I1810,939,632,1891,238, 04341 1174 1,1375,659,99, 1174,1173,635,1025,656,1510,539,1, 06325 1224 1,1647,417,83U,2017,1224, 1224,1222,1241,844,806 825

Table II (Cont.) N = 11 (Cont.) N = 12 (Cont.) POLY SCRG MSRG MCRG POLY 5CRG MSRG MCRG 06343 572 1.1476.1801,508.1778.572, 572.568.1567,1477, 10553 2596 1.1500,2421,3914.2252.2191, 2596,2595,2055.1037,130113505. 06351 950 1..985,4U2.18.1733,950, 950,948,1110.57,1321.1099. 10605 1412 1,1272.126,1550, 1412,1411.3296,284,2937.2663, 06367 548 1,1500,419,1535,1992,425,1765,548, 548,546,1757,1501, 10663 2325 1,1771,1 0 1,1973,2318,1107. 2325,2324,2610,2038.1368,4050, 06403 1739 1.309.2038,1739. 1739,425,1729,310, 10731 448.,3219,3695,511.3064,1789. 448,446,130,3582, 06417 373 1.1675,644,659,737,373. 373,372,1109,1676, 10737 1000 1,3096,385&,2338,1395,1668,27,3997, 1000,999,1868.418. 06435 1151 1,1793,1272,2040,1926,1151. 1151,1147.1029,898, 11015 3590 1,1011,1290,1776, 3590,1306,4040,3294, 06447 1353 1.695,85,1259,596,1353. 1353,1352.85,572,1131.1086,1948,696. 11067 64 1,4032,162',2037,1987,2597, 64,63,1625,3423.223.2408, 06455 1713 1,669.750,2040,963.1713t 1713,1712,305,1060,628.336t 51075 156 1,3784,14,;720,2359,2401, 156,155,3953,2301,2848,1936, 06501 1607 l1l,31301,1607, 1607,160601233,1979,18259566,1907,442, 11147 082 1,3014,3792,937,2069,2466, 1002.1081.2297,3958,2247, 3318 06507 1496 1,552,30,1053,957,1496, 1496,28.706,1614,405.553' 11163 1263 1,2813,2748,314,21,2289, 1283,1282,276,2336,967,2538, 06525 1051 1,1993.78.1861,1152,1051. 1051.1050.895,831.155.998, 11177 074 1,3022,2550,3485,3977,1141,2603,3683, 1074,1072,2520,1111,3695.464. 06531 103 1,519,335,1205,1926,103, 103,1343,2028,1946, 11271 36 1,15801735,3917,2532,3936, 136.720,2715,3531, 06543 1221 1,827,732,1763,1592,1221, 1221,1220,1499,941,313,1832,765.828. 11300 271 0.2655,2760,2766, 271,1868,3355,902,2307,1956, 06557 627 1,1421,685,110,498,907,1889,627, 627,625,1015,896,468,1422, 11313 3530 1,566,2086,7,100,1329, 3530,3528,3835, 1737,18,3027, 06561 856 1,671,585,14,1962,856, 856,854,1887,1101.809.197.770.1193, 10417 3514 0,582,1726,3533,1136,1206, 3514,3513,464,679,554.2952, 06623 876 1,1172,1421,1292.1374,876, 876,875,1133,414,1616,1318,202,1173, 11435 2615 0,2961,3155,2725,1036,2401, 2615,2826.3650,2749, 06637 329 1,1719,1611,1827,1604,680,414,329, 329,327,779,1159,1289,856.742,1720, 11441 64 11553.2796.3832, 64,1112,2859,3643. 06651 375 1,1727,166e,944,1423,375, 375,428.584,1455,179791674. 11471 997 0,1693,103,3362,624,2401, 997,996.3687,2400,2794.485,1620.3508, 06673 767 1,1281,1600,1327,2040,1755,1460,767, 767,766,587,544,727,1035,179,1282, 11477 3253 1,843,3651,2130,2077,1130,3690,2854, 3253,3649,3364,2936,2847,1288, 06675 412 1,1224,123,391,65,1586,289,412, 412,410,514,1656.377,1246,700,1637, 11515 64 1,3968,1280,7,2341,582, 64,62,340,448,2404,393. 06711 284 1,1404,1757,1798,892,284, 284,283,1972,641,1352,1911.1175,1765, 10561 3648 1,789,306,511,3695,3219, 3648,3646.3055.903,3247,468. 06727 477 1,1571,314,1436,1699.819,1868,477. 477,476,314,1645,1232,744,297,1572, 11631 3099 1,2401,624,33620103,1693. 3099,3098,1302,797,1719,2464,3200,589, 06733 1281 1,767,1460,1755,2041,1327,1600,1281, 1281,1279,1461,267,1515,1035,833,768, 11643 3018 0,1078,791,1510,2232,2571, 3018,3016,2740,624,2366,1965,0054,1710, 06741 939 1,1320.30.1317.482,939. 939,938,280,853,1420,1110. 11651 3960 1,3936,2537.3917,1735,158, 3960,3956,4085,3024,1599,566, 06747 1155 1,893,287,614,965,1612,411,1155. 1155,1153,1466,274,1565.894, 12007 1728 0.2368.2356,3455, 1728,1727.827,2369, 06765 521 1,1006,1186.746,0205,658,813,521, 521,520,1618,63,1333,1528, 12061 2684 1,1550,1266,1272, 2684,2683,3288,194,2299,413, 07005 1995 1,105,1986.1995. 1995,1993,478,2039. 12067 1454 1,2642,1887,3616.1226,2907, 1454,1450.3296.2643. 03035 1384 1,1327,808,892,1724,1384, 1384,1383,1533,341, 12117 2587 1,0509,104?,1975,2578,1078, 2587,1041,2831,1510, 07041 1830 1,92.117.1P30. 1830,1829,901.811,1520,335. 12035 579 0,2938,274C,0576,3867,1157, 579.578,2161,2994,3076.3508. 07047 718 1,1330,1505.2039,543,718, 718,716,886,1312,.1140,1873. 12147 239 0,3857,3493,3938,513,477, 239,237,2652,3540,325,3858. 07053 552 1,1496,957,1053,30,552, 552,551,2018,1537,1291,1526, 12165 1919 1.258,3198,3 750,1295,3837, 19191918.3647,1747,1647.2078. 07063 838 1,1210,45,899,1296,838, 838,750,275,459, 12247 3852 1.244.1958,3156,3312,3608, 3852,3851.1958,1649,3332,2209.256,245. 07071 1683 1.1488,1056,626.1288.1683, 1683,1681,1625,1653, 12255 2488 1.3215.2956,174,4051,880, 2488,2487,349,1036,1673,1609, 07107 1330 1,718,543,2039,1505,1330, 1330.1329,1162,709.926,1769 12323 502 1.3594,3770,7,371,1003, 502,500,2526,3763,2482,3595, 07113 695 1,1353,596,1359,85,695, 695.691.499.1438. 12417 1621 1,2475,1242,3708,1612,3241, 1621,1619,443.1358,3232,2476, 07125 226 1,1596.1850,1339,1121,226, 226,925,465.896. 02435 2746 0.2699,263,2618,1207,1396, 2746,2745,3492,1998,3952,1351, 07137 898 1,1150.56,197.973.871.1992,898. 898,896,1060,1095, 12515 26 0,4044,3986,2555,1642,51, 26,25,3960.2380,1667,4071, 07161 656 1.1471,188,205,1568,656 656,655,480.830.1257.1750.1726.913, 02623 918 0,3178,1307,3386,2572,1835, 918,760,3639,1570,2029,0219.3489,3079. 07173 893 1.1155.411,1612.9658014,287,893, 893,892,37.0745,761.0442. 12705 2177 0,3837,1230,3750,3198,258, 2177,2176,1783,841,2392,3294,0279,1920, 07175 1139 1,1817.1430.567,1245.1725,256,1139, 1139,1137,398,1472,1276,0165, 12727 1325 1,2771,284C,2192.7,3425,2511,2649, 1325 2838,3357,2493,3835,2772. 07201 1202 1,443,394,1202 1202:1201*1654,1959,1403,240,1824,1240, 12735 1842 0,412,1149,1593,3132,195,2116,3683, 1842,1840,179,3445,3957,2255. 07223 1247 1,801.1218,275,547.1247. 1247,1245,204,1721,282,1348, 12753 3066 1,0030,923,3958,4089,3486,853.2036, 3066,217,3918,1031, 07237 69 1,1979,194,0717,426,1945,1854,69, 69,68,194,1989,1252.1765.858,1786, 13000 506 1,1776,1290,1011, 506,2786,56,2930,3475,3590. 07243 544 1,1504,187C,767,1450,544, 544,543,598,742,87,907, 03107 418 1,3678,3274,3038,1453,835, 418,4)16,2976,3568,2815,3679, 07273 1571 1,477,1868,819,1699,1436,314,1571, 1571,1732,1209,1547,1671.791, 03125 4070 0,51,1642,2555.3986,4044, 4070,4069,2869,1335,175,1739.2096,27. 07317 1465 1,583,1733,1480,715,1893,315,1465, 1465,1464,824,811,1542,898, 13031 4032 1,582,2341,7,1285,3968, 4032,4030,2875,818,3654,8831275,65. 07335 649 1,750.2009,980,2041,527,1228,649, 649,818,1992,1473,1478.580. 13245 16-8 1.88,4501,1174,2958,3215, 1608,1607,3179,35,3747,3066,3545.828,0250,2489 07363 1500 0,548,1765,425,1992,1535,419,1500, 1500,1499.1910,967, 03275 1678 I.74o.1800,3614,1530,141,1100,3355, 1678,2548,3402,2900,1555,2419, 07371 1423 1,1234,1868,569,759,269,15,1423, 1423.1422,2033,811,885.640, 13425 135, 1,1396,1207,2618,263,2699, 1350.1349,134,2747, 07413 1675 1.373,737,(59,644,1675, 1675,1673, 134310 1481 1,2401,1038,2725,3155,2961, 1481,1266,3264,2616, 07431 1159 1,1941,717,435,1883,1159, 159.1158,165,1687, 135o3 210,5 1,1991,761,3490,10827,114, 2105,308,3325,1992, 07461 1179 1,1426,1170,1152,1206,1179, 1179,1178,748,924, 13505 3517 1,1157.3860,1576,2740,2938, 3517,3516,3613,791,3736,580, 07467 583 1,1465,315,1893.715,1480,1733,583. 583,581,1224,1719, 13565 2254 1,3683.210 I,195,3132,1593,1149,412, 2254,2252,3536,262,899,1843. 07535 1493 1,0109,1170,259,1158,1624,1362,1493, 1493,1492,686,207, 03611 3940 1,2401,2156,3720,14,3784, 3940,3939,2091,2209.2658,2824.3577.057..07553 1421 1,627,1889,907,498,110,685,1421, 1421,1420,1830,1758, 03655 2418 1,3355,1100,141,1530,3614,1800,740. 2418,2414,1435,2476,3735.1679. 07555 58 1,1932,1420,2020,582,1632,531,58, 58,56,776.751, 13663 978 1,3118,160L,2676,2958,2442,1622.1955, 978,2878,2320,272,945.3119. 07565 1233 1,1629,69,1013,1674,453,2013,1233, 1233,1232,676,590,144,195, 13677 4010 1,86,1070,7197,3288,2947,3320,2536,104.3924 4010,4009,1662,474,2553,87. 07603 841 1,1207,358,386,1296,841, 841,839,663,486,1626.1575, 13701 2887 1,1456,1766.2120,1165,1678,2887,2885.45,3653,2700.1662.2075,120, 07621 25 1,1948,18,396,1741,25, 25,24,307,1031,606,1976, 14127 792 0,3304,1292,3468,3422,792, 792,790,2105,143,1189.502.3595.1. 07627 1979 1,69,1854,0945,426,1717,194,1979, 1979,662,1721,208, 14135 1991 1,114,0827,3490,761,1991. 1991,1987,453,2946,1151,1. 07633 1719 10329,414,680,1604,1827,1611,1719, 1719,1718,1269,1549,538,986, 142210 1760 1,1147,117e,1761, 1761,1757,904,1901,3010,1895.2202.1. 07647 1150 1.898,1992,871,973,197,56,1150, 1150,1149,1285,648, 14227 14UU 1,2696,259,867,2961,1400, 1400,1399,259,3414,13'3,649,2228,2956.1141.0 07655 19411,213,1396,1989,810,912,923,1941, 1941,1940,1125,708,635,322, 14271 I078 1,2571,2232,1511,791,1078, 1078,1076,3750,3632,2529,3651.446.0. 07665 1475 1.1145,267,78,222,1036,1914.1475, 1475,1471.1385,1720, 14357 2738 1,1358,3526,3283,925,1869,2674,2738, 2738,2737,3528,1946,2666,792.3305. 07715 352 011344,1997,1603,137,1881,870,352, 352,1176,1154.995, 14433 940 1,3156,1488,2870,3824,940, 940,939,668,1204,2893,.1, 07723 519 1,1529,365,1054,1632,1742,1343,519. 519,515,980,494, 14465 3178 0,1835,2570,3386,1307,3178. 3178,3332,457,404,389.158.3935.0. 07745 1858 1.379,1125,1530.1623,1116,553,1858, 1858,1856,1132,571, 14501 1937 1,3114,3130,1937, 1937,1936,2435,1350,971.1449,2648.1. 07751 597 1,354,945,.70,30,694,500,597, 597,596,1548,1691,511,260, 04545 3594 1,1OC3,371,7.3208,3594, 3594,3592,3130,2034,0735,588.2706,2905.1192,1 14573 387 1,3709.3372,2124,3487,3360,4031.387. 387,385,536,914,322,1789,2308. 14613 1990 1,2106,224,855,3008,1990, 1990,1988,225,1911,2599,2782.902.2255,0842.1. SHIFT 5608065 366065063 FROM 14661 1771 1,1107,231F,1973.1014,17710 1771,1770,1087,1881,2784,3812.285.1. ADJACENT STASES WHICE ARESE6 6RAT86 14675 3118 1,1955,1622,2442,2958,2676,1604,3118, 3118,1214,3959,3178,626,2095.1902.1. 868A58A0CEN STAGES ATORS OF LEP5TD 5=12 14711 2803 1,2289,21,714,2746,2813, 2813,2812,3418,3213,509,608,1463.0009.3088,1 14717 3476 0,620,2416,2919,1232.1054,563.3476. 3476,3474,1144,2696,610,2177,4038.3037.1060.1 14747 2532 1,1564,115E.988,7,310,1626,2532. 2532,2686,62,2723,1374.1, POLY SCR_ ____ 15MCRG033 3224 1,872,233102109.3742,3224, 3224,3216,527,1, 15053 281,3815,3921 3171,1090.281 281,280.756,2022,316491, 101232159 1,1937,3130.3114, 2159,2158,712,31061764,1717,5063 2106,1990,300F,855,224,2106, 2106.2104,2529,3448,1638,2067,2253.1. 10151 3825 1,2766,2760,2655, 13825,2224,741,3591.2710,814, 15151 566 1,1329,100,7,2086,566. 566,564,261.2580,3962,3982.2200.1. 10173 601 1,3495,246 10.797,3851.1675, 601,600,1296,1784,2102,2296, 15213 3815 1,281,1090,3171,3921,3815. 3815.3814,288496499467,1906,3577 1, 10175 1209 1,1678,116,2120,176451456.1209,1207,3285,1658,1295,472. 15321 1500 1,2191,2252,3914,2421.1500, 1500.1499,359813669,1786,11 10231 4032 1~3832~2796.1553, 4032,4028,3787,1386,3332,193, 15341 2063 1,289,411,4072,1348,2063,2063*2061.2623,2813o26311 10321 3130 1,3861,2372,1948, 3130,3129.104,3239,1479,2899, 15365 1030 1,2036,853.3486.4089,3958.923,1030. 1030,1026.3124,321,603,1. 10353 2033 1,2063,134F.4072,411,289, 2033.2031.2147,2095, 15413 872.,3224,3742.2109,2331,872, 872,868,3568,1, 10407 2288 1,1808,1310,959, 2288,2287,1319,372, 15423 3156, 1940,3824,2870,1488,3156,3155,1954926191202-1 10437 1729 1.2367,145e,3276.2359,2818, 1729,1456, 15437 3322 1,774,3781,1862,3773,480,2383,3322, 3322,3320,3636,1. 10443 2335 1,1761.1176,1147, 2335,2980, 15527 1161 1,2935,1480~ 1496,271,883,4051~1161, 1161,1160,1483,837,2799.522.3773.1. 10473 2292 1,1804,868,1518,3018,975, 2292.2291.2874,1708.2812.2936. 15621 1804 1975,3018,1518,868,1804. 1804.1803#1284.2320*343,1027.582. 10517 3335 1.761,3676,1941,753,1052, 3335,3333,385,3122, 15647 1846 1,2250.2977,1873,2619,2891,1919,1846. 1846~lC45,2977,3314.1208,3031,2964.1. 10527 404 1.3692,998,1754,126,1613,. 404,403,3260,891, 15677 2879 1,1217,2981,3548,3241,2721,1108,3591.3281.2879 2879,2979,2521,3113.3993.1* 10541 966 1,1948.237?,3861, 966,965,1664,3292,1729,1968, 1.5701 3495 6.1675,3851,797,2460,3495.3495,3494.3733,2560.3599~2136~3857.1~

Table H (Cont.) N = 12 (Cont,) POLY SCRG MSRGMCRG 15723 3709 1t387,4U31,33609348792124,3372.3709 370993707,3303,209491787.1l 16005 2368 134559235e923689 236892367917389299693269.232593491. 16021 18081,959,1319,1808, 1808.-1807 9596,6277693,19 16027 1401 12695,220?,4086ol89391401 140191399,3279,1077.81791. 16047 3498 1,59892615,4086,1481,3498 3498.3497,2615928493296928939268491. 16115 3678 1,835,1453,3038,3274,3678. 3678,3676,62,1578,1697,1. 16207 598 1,3498,14814086,261595989 598,597,1305,2556,2220,3039,3672,1. 16237 1266 128309226~933919263792155,1827912669 1266,1264,2555,1355.3920916791492.287,1541.1 16245 244 1.3608,3312,3156,1958,2449 244924397649840931639228693768919 16273 2250 I.1846.1919.289192619.18739297792250. 2250.2249.3744942293926980292176.91 16305 3857 1.477.513.3938,3493.38579 3857,385591444930699161293751,3838.1. 16311 3014 12466,206%-993793792,3014, 301493013,304,1627,179992904,2087.189.3604,1 16317 55 1.40419142C,2559,36629196292668,559 55 91426,1161,33292326.138691283.1. 16363 1564 1925329162693109799889115891564t 156491560927129314792107 919 16407 2695 1~1401189?,4086,2203,2695, 2695.26939502,30109359491 16443 2696 1,1400,2961,867,25992696, 269692695918219275192525919 16503 3304 1.79293422,3468,1292 93304, 3304.3302.2640.2233.1456.1. 16521 3692 191613,12691754,998936929 3692.369193098.189983693330~315591. _ 16533 2935 1.1161,405198839271,1496,1483,2935 2935.293491297,3844944.1. ^ 16565 2771 1.2649,2511,340597,2192,2840,2771, 27719125492735,3017,2261.1, 16605 2642 1.2907,1226s,36169,1887,2642, 2642.186896879659.2861.91 16611 4032 1,2597,1987,2037,1625,4032, 4032,403193205,552936549152793725,1, 17025 2475 1,3241.161293708,1242,2475, 2475.2473.3916919 17031 582 1,1206,113(935339172695829 582.581,2370919 17057 2219 1,1877,365r,999408793997,441922199 2219,2218~2380919 17105 1509 1910789257F9197591043915099 15099305193842 919 17121 761 1.1052.753,1941.3676.761, 761,759.2142,2330.1726.1. 17147 4041 1,55,2668,]96293662,2559,1428,40419 404192666.2935,2904.62.91 17163 620 1.3476.56391054.1232,2919,2416,620, 620.618,3732,266'1,933.1, 17217 1877 1,2219,441,3997,4087,99,3655,1877, 18771876,44193311,4040,279392723,1. 17343 1358 1 92738,267t, 1869,92593283,3528,1358, 1358,135792800.91 17421 2367 1,2818,2359,3276,1458,2367, 2367,2636,630,19 17433 774 193322923839480,3773,1862,37819774, 77497729451919 17447 283U 1.1266.18279215592637,3391.2269.28309 2830.2828914529320391371.91 17561 3096 1.3997,27.166891395,2338,3854,3096t 309693095,242,1853,829,26759395919 17631 843 192854,3690 91130,2077,2130,36519843, 843,443,73292618918639358992919919 17673 1217 1.28799328]9359191108.272193241935489298191217 1217,1113,987,13039362,1, 17675 86 1.3924910492536.3320.2947932889319791070986 86,8593026.1239,3577.55493373919 17711 3022 1.3683,260>~1141,3977,3485,2559930229 302293020,4064,534,3786,3342.290391. XS.

are not separated by an interstage adder. The second number is 20, this indicates that there is a jump of 20 across the first interstage adder which is between Stages 1 and 2. The third number, 17, indicates a jump of 17 across the second interstage adder which is between Stages 2 and 3, the fourth number, 23, indicates a jump of 23 across the third interstage adder which is between Stages 3 and 4. Thus for the [5, 3,2, 1,0] MS MSRG X (j) = X2(j+20) X2(j) = X3(j+17) X3(j) = X4(j+23) X4(j) = X5(j+1) (Note: the first entry under MSRG is always 1 even though every stage of the MSRG is separated by an adder. For example for the [2, 1, 0] MS MSRG, the leading entry should be ignored. ) For the MCRG the feedback law (from Table I) is [5, 4, 3, 1, 0]MC and there are interstage adders between Stages 1 and 2, 3 and 4, and 4 and 5. The first entry under MCRG is 12, indicating a jump of 12 between stages not separated by an interstage adder. The next three numbers, 11, 26, and 1, indicate jumps of 11, 26, and 1 across the first, second and third interstage adders which in this case occur between Stages 1 and 2, 3 and 4, and 4 and 5, respectively. Thus for the [5,4,3, 1,0]MC MCRG X1(j) = X2(j+11) X2(j) = X3(j+12) X3(j) = X4(j+26) X4(j) = X5(j+1) (Note: the first entry under MCRG always indicates the jumps between stages not separated by an adder even though every stage in the generator is separated by an adder, as with the [4, 3,2, 1, 0] MC MCRG. In this case the leading entry should be ignored. ) For the MCRG the shift between stages not separated by an adder is the same as the shift between stages of the SCRG having the same characteristic polynomial. This is 133

analogous to the shift of 1 between stages not separated by an adder in the MSRG and the shift of 1 between stages in the SSRG. 134

APPENDIX A The following theorems which deal with the general properties of linear binary sequence generators, were presented without proof in Section 2. Theorem 2: Every stage of a maximal sequence generator produces the same sequence, but the sequence (except for the null sequence) from any stage will be shifted in time from the sequence produced by any other stage. Proof Since, by definition, a maximal sequence from an n-stage generator contains every nonzero, n-tuple of binary digits, and since any n-tuple of digits from a sequence and the characteristic sequence law completely determine the sequence, there is one and only one nonzero sequence which obeys the sequence law of a maximal generator. By Eq. 14 in the text, the sequences produced by every stage of a generator obey the same sequence law. Therefore, every stage of a maximal generator must be producing the same sequence (or the all-zero sequence). Finally, suppose two different stages, i and k, are producing the same nonzero sequences with no time shift. There occur at most 2n- 2 different content vectors and hence the period is at most 2n- 2. But this contradicts our assumption that we were producing maximal sequences. Theorem 4: Let the characteristic polynomial f(~) have the form f(t) = Z b. Kik (mod-2) i=k where b = b = 1 n k 135

then: a) The sequence obtained from any stage of the generator may begin with a transient of k or fewer bits (not part of the periodic sequence) after which the sequence becomes periodic and obeys the sequence law of an n- k stage generator with characteristic polynomial n i-k fO) = Z bi i (mod-2) i=k (Note: the sequence may start out with up to k transient bits and then produce the null sequence. ) b) There is at least one nonzero content vector, U', so that if the generator is initially loaded with U', there will be one transient content vector before every stage produces the null sequence. c) If the generator is capable of producing any nonzero periodic sequence (k < n), then there is at least one nonzero content vector, U", so that if the generator is initially loaded with U" there will be exactly one transient content vector before the generator output becomes periodic and at least one stage produces a nonzero sequence. Proof a) Let A be the "A" matrix for a generator whose characteristic polynomial is f() = (bn k + bn1 n +.. + bk+i + + bk) (mod-2) (A-i) where b= b =b 1 k n Let U(j+m), m > 0, be the content vector of this generator which is initially loaded with U(j). From Eq. 3 Ar U(j) = U(j+r) (mod-2) 136

and by Eqs. 11 and A-1 f(A) = An + b An 1 +... + b A 1 + bk A = 0 (mod-2) and for m > 0 f(A) U(j+m) = U(j+m+n) + bn_1 U(j+m+n-1) +... + bk+i U(j+m+k+l) + bk U(j+m+k) = 0 (mod-2) or for m > 0 U(j+m+n) = bn U(j+m+n-1) +.. + bk+ U(j+m+k+l) + bk U(j+m+k) (mod-2) from which follows ui(j+m+n) = b ni ui(j+m+n-1) +. + bk+1 ui(j+m+k+l) + bk ui(j+m+k) (mod-2) (A-2) Let V!(j+m) represent an (n-k)-tuple of successive output bits from the i-th stage of the generator ui(j+m+k) ui(j+m+k+l) V(j+m) =. m > 0 (A-3) ui(j+m+n- 1) 1 J (n-k)x 1 and let C' be the companion matrix corresponding to the polynomial f b n-k + bn nk +...+ b + b k (mod-2) (A-4) 0 1 0... 0 0 0 0 1... 0 0 Cf=::::: (A-5) 0 0 0... 1 0 0 0 0... 0 1 b, b, i b, r~ b bn _ k k+1 bk+2 n-2 bn-1 (n-k) x (n-k) 137

Then by Eq. A-2, (see Section 2. 2 of text), with m = 0 CT Vi(j) = VI(j+1) (mod-2) (A-6) and by successive application of Eq. A-6 (C))m Vi(j) = V?(j+m) (mod-2) Expanding Cp by minors along the 1st column, remembering that bk = 1, it is seen that |C;| = bk = 1 (mod-2) ~~~-1 ~f hence (Ci) exists and Vi(j) = (C) -m V!(j+m) (mod-2) (A-7) From Eq. A-7 it is seen that V!(j) can be uniquely determined from V!(j+m) for any m > 0; consequently, there can be no transient bits in V(j). But Vi(j) is made up of bits u.(j+k),...,ui(j+n), so that the only possible transient bits are the k bits ui(j), ui(j+l),... u.(j+k-1). Note from Eq. A-2 that after the first n bits have been produced, the remaining portions of the sequence obey the characteristic sequence law, n-k ui(j+p) = i b ui(j+p-i) (mod-2) p > n i1 ^ n-il which is the sequence law for an n - k stage generator whose characteristic polynomial is n-k n-k-1 f'(~) = bn + bn 1 k + + bk+1 + bk (mod-2) b) If k is a factor of f(~), then the determinant of the A matrix for the generator with characteristic polynomial f(l) is (Ref. 3) IAI = b0 = 0 (mod-2) and there is at least one vector, U', such that AU' = 0 (mod-2) (U' can be any nonzero vector in the kernel of the linear transformation represented by the 138

matrix A; Ref. 3. ) If the generator is initially loaded with U(j) = U', then for r > 1 U(j+r) = Ar U(j) = A'1 A U' = Ar-1 0 =0 (mod-2) and every stage of the generator is seen to produce the null sequence. c) Assume the generator is capable of producing a nonzero periodic sequence after all transient bits have passed. Let U(j+s) be one of the nonzero periodic content vectors. Let U" = U(j+s) + U' where U' is a nonzero vector defined as in Part b) of this theorem. Then AU" = AU(j+s) + AU' = AU(j+s) = U(j+s+l) (mod-2) which is the content vector which normally follows U(j+s) in periodic sequence. Since U(j+s+l) is preceded by U(j+s) in the periodic sequence, and U" / U(j+s), then U" is not a part of the periodic sequence of content vectors and is therefore by definition a transient. 139

APPENDIX B The following theorems and derivations were presented without proof or full justification in Section 5. They deal with the simple complement-register generators. I* and R. Matrices 1 Define I* as I* =rotated 90~ [i* jk]n where (B-l) i* =. -1 whenj =n+1-k j,k j,n+l-k w = 0 otherwise Any matrix Q such that Q2 = I is called involutory; an involutory matrix is its own inverse. It will now be shown that I* is involutory: Let (I*)2 = [q k] (mod-2) nxn where n qj.k m = i jm mk (mod-2) n = 1 n+1-m m, n+1-k (mod-2) = 6 = 1 when j = k jk = 0 otherwise Thus (1*)2 = I (mod-2) (B-2) 140

and (I*) = I* (B-3) T (I*)T = [Pk j] P nxn where Pk j j,k j,n+l-k k, n+l-j k j so (I*) = I* (B-4) Define R as R, = [rli j] 1 nxn where r.. = (d )i for j < i (B-5) 0 for j > i That is, R1 has the form (d0)0 0 0... 0 0 0 (d )1 (dl)1 0... 0 0 0 (d)2 (dl)2 (d2)2 0 0 0 R = |. | (B-6) (d0)n-3 (dl)n-3 (d2-3 * 3) 3 0 0 (d0)n-2 (dl)n2 (d2)n-2 (dn3)n-2 (dn2)n-2 0 (d0)n-1 (dl)n-1 (2)1 *** d-3)-1 )n- 1 n-1n n _.^~ ~ — "~1 nxn 141

2 -1 It will now be shown that R= I, and hence, R1 = R1. Let R1 R1 = [ci ] (mod-2) J nxn then n i ci = k r i k r k i (mod-2) k=l Now r i, = 0 for i < k ik and r k, = 0 for k < j Therefore, for i < j 1 j-i n c = L ri *k 0 +E 0+ j r (mod-2) - k-=l 1k k=i+ 1 k=j kJ = 0 (B-7) For i > j j-1 1 n k= 1j ( )i- 1 (dj- l)k-i (mod-2) k=j When i = j this becomes c..= (d,) (d)i- 1 (mod-2) =1- 1 = 1 (B-8) For i > j, let i = j + m where m = 1,2,...,n-j, then 142

j+m cj = Cj+m, j X, (dkl)j+m- 1 (dj l1)k- 1 (mod-2) k=j and by reindexing m c. i= k (dj_l+k)j-l+m (dj_ )j- +k (mod-2) (B-9) j+m, j -1j1+k (mod-2) From Ref. 4, p. 61, for positive integers n, k k 3 (_1)V (n) (n-v = 0 (B-10) v0 Considering Eq. B-10 in mod-2 arithmetic the term (-1)v becomes simply 1 and k L (n) (nV-) = 0 (mod-2) (B-l1) L0 v k-v Reversing the order of summation in Eq. B-ll k n n-k+v 0 Z (ksv) ( ) = 0 (mod-2) (B-12) v=0 Using the relationship ( ) = (n) Eq. B-12 becomes (n-k+ ( n-k ) = 0 (mod-2) (B-13) V=0 Let j = n-k+1 so that k = n-j+1 and j < n, Eq. B-13 becomes n-j+l Z= j-l+v) ( j-l ) = 0 (mod-2) and letting m = n-j+1 so that n = j-l+m and m > 1 m (j-l+ ) (j-l ) = 0 (mod-2) (B-14) Since mod-2 arithmetic is being used Eq. B-14 can be written for m > 1 m (dj l+v)j-l+m (dj _l)j = 0 (mod-2) (B-15) 143

Comparing Eqs. B-15 and B-9 it is seen that for m > 1 c.. = 0 J+m, j or c. = 0 for i > j (B-16) Summarizing Eqs. B-7, B-8, and B-16 c.. = 1 when i = j = 0 otherwise Hence 2 Ri = I (mod-2) and R1 = R1 (B-17) Define R2 as T 2 R2 = R1 = 1[r i] 2 i J nxn where (B-18) r = (di- )j- 1 for i < j = 0 for i > j From Eq. B-18 it is seen that R2 has the form (d0)0 (d0)1 (d0)2... (d0)n-3 (dO)n_2 (d0)n 1 0 (dl)1 (dl)2... (dl)n 3 (dl)n-2 (dl)n 1 0 0 (d2)2... (d2)n- 3 (d2)n- 2 (d2)n- 1 R2 =.... (B- 19) 0 0 0... (dn 3)n_3 (3)-2 (d-3)n-1 0 0 0... 0 (d2)2 (d-21 0 0 0... ~ 0 (dn-)n- 1 nxn 144

The inverse of R2, R2 becomes R21 = (R1)-1 = (R1)T = (R1 = R2 (B-20) Define R3 as 3 R3 [ri, ]nxn where (B-21) r (d i < n+l- j = i-i n-j = 0 for i > n+l-j (dO)n- 1 (dO)n_2 (d0)n_-3 *** (d0)2 (do0)1 (d 0)0 (dl)n-1 (d)n-2 (d)n3 (d)2 (dl)1 0 (d2)n- 1 (d2)n_2 (d2)n3 * (d2)2 0 0 R = * * (B-22) ( dn3)n-1 (dn-3)n-2 (n-3)n-3 0 0 0 (dn-2)n- 1 (dn-2)n-2 0 0 0 0 (d n-1)n- 0 0... 0 0 nxn Consider the product R2 * I* R2 I* [ = k = k ] * [ik ] (mod-2) qk j = L r km mj (mod-2) n X (dk-l)m-l mn+l-j (mod-2) m=k = dk 1)n-j for k < n+l-j = 0 for k > n+l-j 3 =r kr 145

so R3 = R * I* (mod-2) (B-23) R3 = (R2 * I*)1 = (I*)1 *R 1 I* R (mod-2) = [i* k * [r2 k] = [ k] (mod-2) (B-24) J nxn J nxn, nxn where n P; k = i* ~ 2 r k (mod-2) k m= i, n+l-m' (dm-1)k-1 (mod-2) -= dnj)kl for k > n+l-j 0 for k < n+l-j (B-25) From Eq. B-25 R3 has the form 0o o 0... 0 0 (dn- )n- o O 0... 0 (dn-2)n-2 (dn-2)n- 1 0 0.. * ( n-3)3 (dn-3)n2 (dn3)n- 1 R31 =...' (B-26) 0 0 (d (d (d (d o 2)2 *@ (d2)n-3 (d2)n2 (d2) 1 0 (dl)1 (dl)2... (d)n-3 (dl)n_2 (d1)n 1 (d0)0 (d0)1 (d0)2... (d0)n_3 (dO)n_2 (d0)n 1 nxn Comparing Eqs. B-22 and B-26 it is seen that R31 = R3 rotated 180~ (B-27) 146

Define R4 as R4 = R3 = [r j] where 4 (B-28) r ij (d lni for j < n+l-i 0 for j > n+l-i (d0)n-1 (dl)n-1 (d 2)n-1 * (dn-3)n-1 (dn-2)n-1 (dn-1)n-1 (d O)n-2 (dl)n-2 (d2)n2... (dn-3)n-2 (dn-2)n-2 0 (d)n3 (dl)n3 (d2)n * (dn_3)n_3 0 0 R4 =...... (B-29) (d0)2 (dl)2 (d2)2.. 0 0 0 (d0)1 (dl)l 0... 0 0 0 (d0)0 0 0...0 0 nxn The inverse of R4, R4 becomes 4' 4 R4 = (R3)-1 = (R31)T = [p T [= (B-30) where Sj, k = Pk j Using Eq. B-25 Sj.k = (d n-k)j 1 for j > n+l-k (B-31) = 0 for j < n+l-k 147

and R4 has the form 0 0 0... 0 0 (d0)0 0 0 0... 0 (dl)1 (d0)1 0 0 0... (d2)2 (dl)2 (d0)2 R =.. (B-32) 0 0 (d3)-3 *.. (d2)n-3 (dl)n-3 (d0)n 3 0 (dn 2)n-2 (dn-3)n2 *.* (d2)n-2 (1)n- 2 ( O)n-2 (dn- 1)n-1 (dn-2)n- (dn-3)n- 1 *** (d2)n- 1 (d)n-1 (dO)nnxn Comparing Eq5. B-29 and D-32 it i Beern that -1 R4 = R4 rotated 180~ (B-33) From Eqs. D-23 and B-18 R = R2 I* = R1. I* (mod-2) (B-34) From Eq. B-28 T R3 R4 3 4 so T TT R4 =(R3 = R3 (B-35) Combining Eqs. B-34 and B-35 T T R3 =R I* R2 I * = R4 (mod-2) (B-36) From Eqs. B-36 and B-4 T T T = R4 = (R)T = (Rr I*)T = (I*)T (R)T = I* R (mod-2) = (R2 I*) = (I*)T R = I* RT (mod-2) 148

or R4 = I* R1 = I* R2 = R3 (mod-2) (B-37) From Eqs. B-2 and B-37 R = I* ** * R1 = I* R (mod-2) = I* R3 (mod-2) (B-38) and from Eqs. B- 18 and B-38 T R1 = R2 so R1 = R2 = I* R3 = I* R4 (mod-2) (B-39) From Eqs. B-39 and B-4 TT T 2 = (R2 ) = R1 = (I* RTT) = (R3)T (I*)T = R3 I* (mod-2) = (I* R4) = R4 (I*) = R4 I* (mod-2) or T T R2 = R1 R3 I* = R4I* (mod-2) (B-40) G and H Matrices Consider an n-stage SCRG with feedback taps, ci, and characteristic polynomial n f() = bi. From Eq. 16 i=O Cf Vi(j) = Vi(j+1) (mod-2) where Cf is the companion matrix associated with the characteristic polynomial f(F). From Eq. 159, for an SCRG u l(j) = ui(j) + ui(j+1) (mod-2) 149

which leads to the equation Vi l(j) = Vi(j) + Vi(Ji+) (mod-2) = (Cf + I) Vi(j) (mod-2) (B-41) If a matrix H is defined as H Cf + I (mod-2) (B-42) then H = [h. ]] ^J nxn where (B-43) h = 5i + 56 (mod-2) for 1 < j < n, 1 < i < n- 1 h.= n + bj (mod-2) for 1 < j < n and Eq. B-41 becomes V:i- (j) = H Vi(j) (mod-2) (B-44) If H is nonsingular then its inverse exists. The determinate of a matrix is equal to the constant term of the characteristic polynomial of the matrix (see Refo 3, p. 87). The characteristic polynomial of H, h(~), is found as follows; let 4 = + 1 then by definition h(Q) = IH + Ij| (mod-2) = |Cf + ( + 1) II (mod-2) = ICf + 4Ii (mod-2) n = L bi 4,i (mod-2) i=O n = ~ bi( + 1) (mod-2) i=O 150

Applying Eq. 118, this becomes n i h() = L bi L (dk)i (mod-2) (B-45) i=0 k=O Interchanging summations, Eq. B-45 can be written as h(o) = k [ (dk)i b 1k (mod-2) k=0 i=k k From Eq. 150, n cnk = (dk)i b (mod-2) and the characteristic polynomial of H becomes h() = n c k n = cn +c n-l n 2 * + c-20 n (mod-2) (B-46) n The determinant of H, I H I, is therefore IHI = c (mod-2) and H has in inverse, H, if and only if c = lo Whenever c = 1 in the SCRG or equivalently, from Eq. 150 n L b. = 1 (mod-2) define a matrix G as follows i=O 1 G = [g, ]n i, i nxn where j-1 1 (B-47) g i j 1 + L bk (mod-2) for i < j k=0 j-1 = bk (mod-2) for i > j k=0 k It will now be shown that G, in the above equation, is the inverse of H. Consider the matrix product H * G = [h ] * [g ] = [t ] (mod-2) ix nxn nJ nxn 1, nxn n t. = 3 h. g (mod-2), j m-l im m, j 151

For 1 < i < n- 1, all j n J mi, m- 1] m,j (mod- 2) = + I (mod-2) when j > i this becomes j-1 j-1 tW = (1 + kLO bk)+ (1 + kO bk) = 0 (mod-2) k=0 k=0 when j = i this becomes i-1 i-1. = 1 + Z bk + Z bk = 1 (rnod-2) =0 k =O k k and when j < i, it becomes j-l j-1 ti = L bk + k bk = 0 (mod-2)'J k= O k= so for 1 < i < n-, all j t. = 1 when i = j = 0 otherwise For i = n n t = h, g (mod-2) n, ih n, m- modn n =m [n, m + b m-] gmj g n,j bm -1 gmj (mod-2) m=1 m=1 when j < n- 1 this becomes j-_ i - j-l - n j-l tn = X bk + L bm. 1 + kJ 1 bm-l Z bk (mod-2) n, bk + E bm-1+ bk + m- bi bk (mod-2) k=0 m=1 m=l m=j+n k =0 152

j-1 j-1 n j-1 = bk + Z bk + Z bm-1 bk (mod-2) k=0 k= m=l k= n-1 j-1 j-1 n-1 = bm Z bk = Z bk Z bm (mod-2) (B-48) m=O k= k=O m=0 m From the definition of the characteristic polynomial, an nxn matrix has b - 1. In addition for the SCRG, cn has been assumed 1 which implies n n-1 n-1 Z b= b + Z b = 1 + Z b. = 1 (mod-2) i=0 1 n i=0 1 i=0 1 or n-1 L b. = 0 (mod-2) i=0 1 Thus Eq. B-48 is equal to zero. For i = j = n n t =, h g (mod- 2) n,n m=i n,m m,n n n-1 = m1 (6 + b ) ( + k bk) (mod-2) m n m m-1) (mod-2) m=l k= n (1 + b 1 ) (mod-2) m=1 n-1 1 + m bm (mod-2) m=0 m = 1 (mod-2) Summarizing, t.. = 1 when i =j = 0 when i / j 153

and H - G = [t.] = I (mod-2) 1J nxn Therefore, when c = 1 n G = H1 (B-49) and from Eqs. B-44 and B-49 Vi(j) = G Vi_ (j) (mod-2) (B-50) The characteristic polynomial of G will be found for the sake of completeness. Let A be any non-singular n x n matrix with characteristic polynomial n f()= A- If = E b i i=O then it can be shown that the characteristic polynomial of A is given by f1(_ ) = A- - ~I, = (-1)nb0 1 L bni In mod-2 arithmetic -1 and +1 are the same, and if A is non-singular, then b 1 = A 1 = I A1 = l (mod-2) so n f-(t =, bn i (mod-2) i=0O and we see that f 1 ( ) is the reverse of f( ). Applying this result to the G and H matrices we get the characteristic polynomial of G n g(!) = IG+ Ii = ci 4i (mod-2) (B-51) i=0 154

Theorem 8: n Consider an n-stage SCRG for which c = 1 and L c. = 1, with ~n i=0 1 a characteristic polynomial, f(~), which is factorable. If any stage of the SCRG is producing a sequence corresponding to a polynomial of degree less than n, f'(~), where f(Q) = f"() f'(), then the sequences from every stage of the generator correspond to the same polynomial f'( ). Proof Let Xi(j) denote the sequence produced by the i-th stage of the SCRG. Assume that Xi(j) obeys the sequence law associated with one of the factors, f'(Q), of the characteristic polynomial f(~). From Eq. 173 Xi.l(j) = Xi(j) + Xi(j+l) (mod-2) and from Theorem 1, since X.(j) and X.(j+l) obey the same sequence law (they are shifted versions of the same sequence), their sum, Xi_ (j), obeys the same sequence law. Similarly, X (j), m < i, obeys the sequence law associated with f'(~). Since c = 1, the G matrix defined by Eq. 172 exists and Eq. 171 holds, that is Vi+1(j) = G Vi(j) (mod-2) or equivalently n ui+l(j) = gl k ui(j+k- 1) (mod-2) k=l' which leads to n Xi+1(j) = gl k Xi(j+k-1) (mod-2) (B-52) Applying Theorem 1 to Eq. B-52, X i+1(j) obeys the same sequence law that X.(j) obeys. Similarly X (j) for i < m < n obeys the sequence law associated with the factor f'(N). Theorem 8 is obtained by combining these two results. Before considering Theorem 9, the following lemma will be established. 155

Lemma If an n-stage SCRG contains "O's" in p consecutive stages (say Stages m through m+p- 1) at any time j, then the output sequence from Stage m+p-1 starting at time j will contain p consecutive "O's." Proof From Eq. 111 for an SCRG Ui+l(j+l) = ui+l(j) + ui(j) (mod-2) for i > 1 Given that u+k(j) = 0 for 0 < k < p- 1 (B-53) then m+l+k(j+l) = u m+k+(j) + um+k(j) (mod-2) = 0 for 0 < k < p-2 (B-54) Suppose that for some value of q um+q+k(j+q) = 0 for < k < p-q-1, q < p-2 (B-55) thenfor 0 < k < p-q-2, q+l < p-1 m+q+l+k(j+q+l) = Um+q+k(j+q) + um+q+k+l(jq) (mod-2) = 0+0 = 0 (B-56) From inspection of Eqs. B-53 and B-54, Eq. B-55 is true for q = 0, and q = 1. Also by Eq. B-56, if Eq. B-55 is true for any value of q such that q < p- 2 then it is true for the next larger value of q, thus by induction Um+q+k(j +q)= 0 for 0 < k < p-q-1, q < p- (B-57) In particular, when k = p-q- 1 Um+p-l(j+q) = ~ for 0 < q < p- 1 (B-58) 156

Theorem 9: n Consider an n-stage SCRG with cn = 1 and L c = 1, with a characi=0 teristic polynomial, f(~), which is factorable, f(f) = f'( ),..,f"(). If any p consecutive stages of the generator (p < n) contain zeros at any time j, then none of the sequences being produced by the generator can be produced by a generator of p or fewer stages, unless every stage is producing all zeros. Proof From the above lemma, if p consecutive stages of the generator contain zeros at some time j, then the output sequence from one of the stages will contain p consecutive t"O'So It is impossible to generate a linear sequence, using a p-stage generator, that contains p zeros except the all-zero sequence. If the i-th stage were producing all zeros then every stage would be producing all zeros because, by repeated application of Eqs. 167 and 171, Vik(j) = Hk Vi(j) = 0 (mod-2) and Vi+k(j) = Gk Vi(j) = 0 (mod-2) If this is not true, then some stage of the SCRG is producing a nontrivial sequence which cannot be generated by a generator of p stages or less. Theorem 9 states that if one stage of an SCRG is producing a sequence that can be produced by an m-stage generator, then every stage of the generator is producing a sequence which can be produced by the same m-stage generator. Therefore, m must be greater than p. Theorem 10: Consider an n-stage SSRG and an n-stage SCRG which have the same feedback (not characteristic) equation. Let Y.(j) represent the content vector of the SSRG at time j, and let U(j) represent the content vector of the SCRG at time j. If U(K) = Y(K) at some time K, then [U(K),U(K+1),..o,U(K+n-1)] = [Y(K),Y(K+1),...,Y(K+n-1)] * R2 (mod-2) and [Y(K),Y(K+1),...,Y(K+n-1)] = [U(K),U(K+1),..., U(K+n-1)] ~ R2 (mod-2) 157

Proof Let A be the "A" matrix for the SSRG and let A be the A matrix for the SCRG. s c If both generators have the same feedback equation, then A = A + I (mod-2) C s Applying Eq. 118 k k A = (A + I) (mod-2) for k > 0 c s k = 2 (d)k A (mod-2) i=0 ik s If at some time K U(K) = Y(K) then U(K + k) = Ak U(K) (mod-2) C = A k Y(K) (mod- 2) k (d A Y(K) (mod-2) i k = 2 (d)k A Y(K + i) (mod-2) i=0 k k u (K+k) = 2 yp(K+i) (di)k (mod-2) for k > 0 (B-59) In matrix form Eq. B-59 becomes for 0 < k < n- 1 158

u1(K) ul(K+l)... ul(K+n- 1) u2(K) u2(K+1)... u2(K+n- 1) * *2 un- (K) u 1(K+l)... un (K+n- 1) Un(K) un(K+l)... un(K+n- 1) yl(K) yl(K+1)... yl(K+n-1) (d0)0 (d0)1... (d0)n2 (d0)n- Y2(K) y2(K+l)... y2(K+n-l) 0 (d)1... (dl)n-2 (d1)n-1........ (mod-2) Yn-(K) y (K) Yn(K+n) *0 0. (dn2)n- 2 (dn- 2)n- 1 Yn(K) yn(K+l)... yn(K+n- 1) 0 0... 0 (dn )n- (B-60) The matrix on the far right in Eq. B-60 is recognized as the R2 matrix, thus [U(K),U(K+1),..,U(K+n-1)] = [Y(K),Y(K+1),...,Y(K+n-1)] * R2 (mod-2) -1 and since R2 = R2 [Y(K),Y(K+1),...,Y(K+n-1)] = [U(K),U(K+1),...,U(K+n-1)] * R2 (mod-2) 159

APPENDIX C These theorems were presented without proof in Section 6. They deal with the modular-complement-register generator. Theorem 11: Given an n-stage MCRG with a factorable characteristic polynomial f(0) = f'(V), f"()... f'"(W) (mod-2) The sequences produced by each stage of the MCRG follow the same sequence law as is followed by the sequence produced by the last stage. (Note: some stages may produce the all-zero sequence. ) Proof Let Xi(j) be the sequence produced by the i-th stage with time reference j. For an MCRG ui_1(j) = ui(j) + ui(j+l) + ci1 u(j) (mod-2) or X.i(j) = Xi(j) + Xi(J+l) + ci 1 Xn(j) (mod-2) Let i = n, then Xn-l() = (l+c ni) Xn(j) + Xn(jl) (mod-2) By Theorem 1, Xn l(j) obeys the same sequence law that X (j) obeys. Suppose that for some value of k, 2 < k < n, that Xk(j) obeys the same sequence law as X (j) obeys, then Xkl(i) = Xk(j) + Xk(+l) + Ck_ Xn(j) (mod-2) and by Theorem 1, Xk l(j) follows the same sequence law that X (j) follows. 160

We have seen that Xk(j) follows the sequence law that X (j) follows when k = n- 1 and it is obviously true for k = n. Also, if Xk(j) obeys the law of Xn(j), then Xk-l(j) obeys the law of X (j). Therefore, by induction, for all k such that 1 < k < n, Xk(j) follows the n - - same sequence law that X (j) follows. Theorem 12: Given an n-stage MCRG; if ul(j) = 1 and ui(j) = 0 for 2 < i < n at some time j, then ui(j+k) = (dil)k for 1 < i < k+1, 0 < k < n- 1 and (C-l) u.i(j+k) = 0 for k+2 < i < n, O < k < n- 2 Proof From Eq. 187 for an MCRG ul(p+l) = u1(p) + c0 un(p) (mod-2) ui(p+l) = ui_l(p) + ui(p) + ci 1 un(P) (mod-2) By hypothesis ui(j) = 1 = (d0)0 for i = 1 =0 for 2 < i < n Therefore ul(j+l) = ul(j) + c0 Un(j) (mod-2) = 1 = (dO) Similarly u2(j+l) = ul(j) + u2(j) + cI un(j) (mod-2) = 1 = (dl) 161

and ui(j+l) = uil(j) + ui(j) + cil1 u (j) (mod-2) = 0 for 3 < i < n Thus for k = 0, 1 ui(j+k) = (dil)k for 1 < i < k+1 (C-2) = 0 for k+2 < i < n Assume that Eq. C-1 is true for some aribtrary value of k such that 1 < k < n-2, then u1(j+k+l) = ul(j+k) + co un(j+k) (mod-2) = (dO)k + 0 = (dO)k+ ui(j+k+1) = uil(j+k) + ui(j+k) + ci_1 u(j+k) (mod-2) = (d_2)k + (di- l)k (mod-2) = (di-l)k+1l for 2 < i < k+l Uk+2(j+k+l1) = uk+I(j+k) + uk+2(j+k) + ck+ un(j+k) (mod-2) = (dk)k = (dk+l)k+l ui(j+k+l) = uil(j+k) + ui(j+k) + c_1 u(j +k) (mod-2) = 0 for k+3 < i < n 162

so ui(j+k+l) = (di l)k+1 for 1 < i < (k+1) + 1 = 0 for (k+1)+ 2 < i < n if k+l < n-2 If Eq. C-1 is true for any particular value of k such that 1 < k < n- 2, then it is true for the next larger value of k. Equation C-2 shows that Eq. C-1 is true for k = 0, 1, thus by induction Eq. C-1 is true for all k such that 0 < k < n- 1. 163

APPENDIX D This theorem, dealing with the Jacobian-hybrid generator, was presented without proof in Section 7. Theorem 13: If an n-stage JHG is initially loaded with U(j) = E1(0)G that is u1(j) = 1 ui(j) = 0 for 2 < i < n then uk(j+k-1) = 1 for 1 < k < n and ui(j+k-1) = 0 for 2 < k+l < i < n Proof From Eq. 229 ui(j+k) = ui_1(j+k-1) + ci ui(j+k-1) + ui+.(j+k-1) (mod-2) 2 < i < n- 1 un(j+k) = u 1(j+k- 1) + cn un(j+k- 1) (mod- 2) Assume for some arbitrary k such that 1 < k < n- 2 that uk(j+k-1) = 1 and (D- 1) ui(j+k-1) = 0 where k < i < n then 164

Uk+l(j+k) = uk(j+k-1) + Ck+1 uk+l(J+k 1) + uk+2(j+k-l) (mod-2) (D-2) = 1 and ui(j+k) = ui 1(j+k-1) + ci ui(j+k-1) + ui+1(j+k-1) (mod-2) (D-3) =0 for k+1 < i < n- 1 un(j+k) = un (j+k-1) + cn un(j+k-1) (mod-2) (D-4) = 0 By hypothesis, Eq. D-1 is true for k = 1. From Eqs. D-2, D-3, and D-4, if Eq. D-1 is true for any arbitrary value of k such that 1 < k < n- 2, then Eq. D-1 is valid for the next larger value of k. Thus by induction uk(j+k-1) = 1 and ui(j+k-1) = 0 for 1 < k < n- 1 (D-5) and k+1 < i < n From Eq. D-5, u(j+n-1) = u 1(j+n-2) + cn un(j+n-2) (mod-2) = 1 Therefore uk(j+k-1) = 1 for 1 < k < n ui(j+k-1) = 0 for 1 < k < n- 1 and k+1 < i < n 165

REFERENCES 1. Birdsall, To G. Ristenbatt, M. P. Introduction to linear shift-register generated sequences. Technical Report No. 90. (2262-189-T). Ann Arbor: Cooley Electronics Laboratory, The University of Michigan, October, 1958. 2. Birdsall, T. G. Hoopes, C. Extensions of linear shift-register generated sequences. (U) Technical Report No. 113. (2899-46-T). Ann Arbor: Cooley Electronics Laboratory, The University of Michigan, February, 1962. (SECRET). 3. Nering, E. D. Linear algebra and matrix theory. New York: Wiley, 1964. 4. Feller, W. An introduction to probability theory and its applications. Vol. I. New York: Wiley, 1957. (2nd Ed.). 5. Peterson, W.W. Error-correcting codes. New York: Wiley, 1961. 166

(U) DISTRIBUTION LIST No. of No. of Copies Copies 1 Office of Assistant Secretary of 16 Commanding General Defense U. S. Army Materiel Command (R&E) Room 3E1065 Washington, D. C. 20315 The Pentagon ATTN: R&D Directorate Washington, D. C. 2031 ATTN: Technical Library 17 Chief U. S. Army Electronics 2-3 Chief of Research and Development Laboratories Department of the Army Mountain View Office Washington, D. C. 20310 P. 0. Box 205 Mountain View, California 4 Commanding General U. S. Army Security Agency 18 Director Arlington Hall Station U. S. Army Electronics Arlington, Virginia 22212 Laboratories ATTN: ACofS, G3 Fort Monmouth, New Jersey 07703 ATTN: AMSEL-RD-ADO-RHA 5 Commanding General U. S. Army Security Agency 19 Director Arlington Hall Station U. S. Army Electronics Arlington, Virginia 22212 Laboratories ATTN: ACofS, G4 Fort Monmouth, New Jersey 07703 ATTN: AMSEL-RD-ADO-ADT 6 Deputy President U. S. Army Security Agency Board 20 Director Arlington Hall Station U. S. Army Electronics Arlington, Virginia 22212 Laboratories Fort Monmouth, New Jersey 07703 7-10 Commanding General ATTN: AMSEL-RD-DR U. S. Army Security Agency Arlington Hall Station 21-40 Commander Arlington, Virginia 22212 Defense Documentation Center ATTN: IADEV-SR Cameron Station, Bldg. 5 Alexandria, Virginia 20315 11 Commanding General ATTN: TISIA U. S. Army Security Agency Arlington Hall Station 41 Commanding General Arlington, Virginia 22212 U. S. Army Electronics Command ATTN: IACON Fort Monmouth, New Jersey 07703 ATTN: AMSEL- EW 12 USASA Technical Representative U. S. Army Electronics 42 Technical Director Laboratories U. S. Army Electronics Command Evans Area Fort Monmouth, New Jersey 07703 Belmar, New Jersey 07703 43-47 Director 13-15 Director National Security Agency U. S. Army Electronics Fort George C. Meade, Maryland Laboratories 20755 Fort Monmouth, New Jersey 07703 ATTN: R-3, Mr. M. H. Klein ATTN: AMSEL-RD-SEE 167

(U) DISTRIBUTION LIST (Cont.) No. of No. of Copies Copies 48 Commanding Officer 51 Dr. T. W. Butler, Director 52d USASA Special Operations Cooley Electronics Laboratory Command The University of Michigan Fort Huachuca, Arizona 85613 Ann Arbor, Michigan 49 Director U. S. Army Electronics L 52-70 Cooley Electronics Laboratory Laboratories The University of Michigan Fort Monmouth, New Jersey 07703 Ann Arbor, Michigan ATTN: AMSEL-RD-SE 71 Remote Area Conflict Information 50 Commander Center Rome Air Development Center Battelle Memorial Institute Griffis Air Force Base, New York 505 King Avenue ATTN:EMIAP Columbus, Ohio 43201 168

Unclassified Security Classification DOCUMENT CONTROL DATA - R&D (Security classification of title, body of abstract and indexing annotation must be entered when the overall report is classified) 1. ORIGINATIN G ACTIVITY (Corporate author) 2a. REPORT SECURITY C LASSIFICATION Cooley Electronics Laboratory Unclassified The University of Michigan 2b GROUP Ann Arbor; Michigin. 3. REPORT TITLE Study of Linear Sequence Generators 4. DESCRIPTIVE NOTES (Type of report and inclusive date.) Technical Report No. 165 5. AUTHOR(S) (Let name. first name, initial) C. C. Hoopes R. N. Randall 6. REPORT DATE 7a. TOTAL NO. OF PAGES 7b. NO. OF REFS June 1966 181 5 8a. CONTRACT OR GRANT NO. 90. ORIGINATOR'S REPORT NUMBER(S) DA-28-043 AMC-00080(E) 6576-4-T b. PROJECT NO. 6576 c. *b. OTHER RE'PORT NO(s) (Any other numberes hat may be aseinoed this report) d. Technical Report 165 10. A VA IL ABILITY/LIMITATION NOTICES This document is subject to special export controls and each transmittal to foreign nationals or foreign givernments may be made only with prior approval of CG, U. S. Army Electronics Command, Fort Monmouth, N. J. ATTN: AMSEL- L-C 11. SUPPLEMENTARY NOTES 12. SPONSORING MILITARY ACTIVITY Commanding General U. S. Army Electronics Command ___Fort Monmouth, New Jersey AMSEL-WL C 13. ABSTRACT This report treats techniques for generating linear binary sequences. The basic properties of sequence generators, maximal sequences, and non maximal sequences are reviewed. Five specific types of generators, each representing a "canonical form," are considered. Two forms of shift-register generators are studied: the simple-shift-register generator and the modular-shift-register generator. Two forms of complement-register generators are considered: the simple-complement-register generator and the modular-complement-register generator. A hybrid generator consisting of both shift and complement stages is discussed. Included in the discussion for each generator are: (1) the relationship between the characteristic polynomial and the feedback connections, (2) the relati nship between sequences produced by different stages of the same generator, (3) the initial loading required for the generator to produce a particular n-tuple from the output stage, and (4) an output adder technique to obtain the desired starting conditions for a sequence obeying the law of the generator. The advantages and disadvantages of each of the five generators are given. Also tables of equivalent generators for all maximal characteristic polynomials of degree 2 K n < 12 are included. Matrix theory is used throughout the report to prove necessary theorem, and it is used in the development of mathematical descriptions of the generators. D,JAN4 1473 Unclassified Security Classification

Unclassified Security Classification _ 14. LINK A LINK B LINK C KEY WORDS —, ROLE WT ROLE WT ROLE WT Algebra Binary Arithmetic Computer Logic Determinants Equations Factor Analysis Feedback Generators Generators Equivalent Generators Linear Sequences Mathematical Analysis Matrix Algebra Polynomials INSTRUCTIONS 1. ORIGINATING ACTIVITY: Enter the name and address imposed by security classification, using standard statements of the contractor, subcontractor, grantee, Department of De- such as: fense activity or other organization (corporate author) issuing (1) "Qualified requesters may obtain copies of this the report. report from DDC " 2a. REPORT SECUITY CLASSIFICATION: Enter the over- (2) "Foreign announcement and dissemination of this all security classification of the report. Indicate whether report by DDC is not authorized. "Restricted Data" is included. Marking is to be in accord- report by DDC is not authorized ance with appropriate security regulations. (3) "U. S. Government agencies may obtain copies of this report directly from DDC. Other qualified DDC 2b. GROUP: Automatic downgrading is specified in DoD Di- users shall request through rective 5200.10 and Armed Forces Industrial Manual. Enter users shall request through the group number. Also, when applicable, show that optional." markings have been used for Group 3 and Group 4 as author- (4) "U. S. military agencies may obtain copies of this ized. report directly from DDC Other qualified users 3. REPORT TITLE: Enter the complete report title in all shall request through capital letters. Titles in all cases should be unclassified. If a meaningful title cannot be selected without classification, show title classification in all capitals in parenthesis (5) "All distribution of this report is controlled. Qualimmediately following the title. ified DDC users shall request through 4. DESCRIPTIVE NOTES: If appropriate, enter the type of.___b_.... report, e.g., interim, progress, summary, annual, or final. If the report has been furnished to the Office of Technical Give the inclusive dates when a specific reporting period is Services, Department of Commerce, for sale to the public, indicovered. cate this fact and enter the price, if known. 5. AUTHOR(S): Enter the name(s) of author(s) as shown on 11. SUPPLEMENTARY NOTES: Use for additional explanaor in the report. Enter last name, first name, middle initial. tory notes. If military, show rank and branch of service. The name of the principal au.thor is an absolute minimum requirement. 12. SPONSORING MILITARY ACTIVITY: Enter the name of the departmental project office or laboratory sponsoring (pay6. REPORT DATE: Enter the date of the report as day, ing for) the research and development. Include address. month, year; or month, year. If more than one date appears on the report, use date of publication. 13. ABSTRACT: Enter an abstract giving a brief and factual summary of the document indicative of the report, even though 7a. TOTAL NUMBER OF PAGES: The total page count it may also appear elsewhere in the body of the technical reshould follow normal pagination procedures, i.e., enter the port. If additional space is required, a continuation sheet shall number of pages containing information, be attached. 7b. NUMBER OF REFERENCES: Enter the total number of It is highly desirable that the abstract of classified reports references cited in the report. be unclassified. Each paragraph of the abstract shall end with 8a. CONTRACT OR GRANT NUMBER: If appropriate, enter an indication of the military security classification of the inthe applicable number of the contract or grant under which formation in the paragraph, represented as (TS), (S). (C), or (U) the report was written. There is no limitation on the length of the abstract. How8b, 8c, & 8d. PROJECT NUMBER: Enter the appropriate ever, the suggested length is from 150 to 225 words. military department identification, such as project number,. KEY WORDS: Key words are technically meaningful terms subproject number, system numbers, task number, etc. 14. KEYWORDS: Key words are technically meaningful terms or short phrases that characterize a report and may be used as 9a. ORIGINATOR'S REPORT NUMBER(S): Enter the offi- index entries for cataloging the report. Key words must be cial report number by which the document will be identified selected so that no security classification is required. Identiand controlled by the originating activity. This number must fiers, such as equipment model designation, trade name, military be unique to this report. project code name, geographic location, may be used as key 9b. OTHER REPORT NUMBER(S): If the report has been words but will be followed by an indication of technical conassigned any other report numbers (either by the originator text. The assignment of links, rules, and weights is optional. or by the sponsor), also enter this number(s). 10. AVAILABILITY/LIMITATION NOTICES: Enter any limitations on further dissemination of the report, other than those Unclassified Security Classification