A *finite state machine* (FSM) [Mealy, 1955] consists of finite sets of (internal) *states* {*s*}, *input* and *output* alphabets {*a*} and {*b*}, an *output* function *T* determining the output

and a *state* function Σ determining the *successor* state.

Given an *initial* internal state *s*_{0}, and sequence of input states *a*_{0}, *a*_{1}, …, the functions *T* and Σ determine the output sequence *b*_{0}, *b*_{1}, …, according to the recursion

Figure 8.1 depicts a *feedback shift register* (FSR) with *feedback function f*, an FSM with *null* input consisting of *N stages* (each capable of storing one bit), a feedback register, and a single output port, where

- The content of Stage
*i*at time*t*is*s*= 0 or 1,_{i}(t) - The output
*s*_{0}(*t*) is the content of Stage 0 at time*t*, - The state of the FSR at time
*t*is the*N*-vector*s*(*t*) = (*s*_{0}(*t*),*s*_{1}(*t*), …,*s*_{N−1}(*t*))*∈*(where is the set of 2^{N}vectors ...

Start Free Trial

No credit card required