Fibonacci and Galois Representations of Feedback with Carry Shift Registers

IEEE Transactions on Information Theory 48 (2002) 2826-2836.

Andrew Klapper, 779A Anderson Hall, Dept. of Computer Science, University of Kentucky, Lexington, KY, 40506-0046, klapper at
Mark Goresky, Institute for Advanced Study

Abstract Feedback with carry shift registers (FCSRs) are a class of finite state devices that are similar to linear feedback shift registers (LFSRs) in their simplicity and statistical randomness, and in that they have algebraic tools for the analysis of their output. In this paper we describe and analyze an alternative architecture for FCSRs that is similar to the Galois architecture for LFSRs. We also explore architectural considerations for $d$-FCSRs, a natural generalization of FCSRs. Finally, we describe a general framework for algebraically modeling LFSRs, FCSRs, and $d$-FCSRs in both their Fibonacci and Galois architectures.