An Algorithm for Generating Stable Feedback Shift Registers of Order n

ABSTRACT

It is shown in this paper that the stable feedback shift registers, when classified according to Hamming weight (the number of fundamental product terms in expanded sum of products form), are binomially distributed, i.e., are (2n - n - 1 w) stable feedback shift registers of order n with Hamming weight equal to w. Using this relationship, a recursive algorithm is established which will generate all stable feedback shift registers of order n. Formulas are also given for determining the number of stable feedback shift registers which have j + 1 starting states and j + 1 branch states, 0 ≤ j ≤ 2n-1 - 1.

REFERENCES

• 1: MOWLE, F.J. Relations between PN cycles and stable feedback shift registem. IEEE Trans. EC-15, 3 (June 1966), 375-378.
• 2: GILL, A. Introduction to the Theory of Finite State Machines. McGraw-Hill, New York, 1962.
• 3: MASSEY, J., AND LILY, R. Application of Lyapunov's direct method to the error-propagation effect in convolutional codes. IEEE Trans. IT-iO, 3 (July 1964), 248-250.
• 4: ---- AND ---- Monotone feedback shift registers. Proc. Second Annual Allerton Conf. on Circuit and System Theory, U. of Illinois, Urbana, Ill., Sept. 1964, pp. 860-874.
• 5: MAGLEBY, K. B. The Synthesis of Nonlinear Feedback Shift Registers. Stanford Electronics Laboratory, Rep. 6207-1, Stanford, Cal., Oct. 1963.
• 6: MOWLE, F .J . Enumeration and Classification of Stable Feedback Shift Registers. Ph.D. dissertation submitted to Dep. of Elec. Eng., U. of Notre Dame, Notre Dame, Ind., Jan. 1966; also U. of Notre Dame Elec. Eng. Dep. Tech. Rep. No. 661, Notre Dame, Ind., Jan. 12, 1966.
• 7: DEBauIJN, N. G. A combinatorial problem. Proc. Koninl. Ned. Akad. Wetenschap. 49, Pt. 2 (1'946), 758-764.
• 8: GooD, I .G . Normal recurring decimals. J. London Math. Soc. 21, Pt. 3 (1946), 167-169.
• 9: Solomon W. Golomb , Soloman Golomb, Shift Register Sequences, Aegean Park Press, Laguna Hills, CA, 1981

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

General Terms:
Algorithms, Design, Measurement, Performance, Theory