15. Linear Sequential Machines

15.1 Logical Signals

An important class of signals is comprised of those carrying digital information, corresponding to the time variation of a logical variable x(t). The value of the signal is of course restricted to only two values, 0 and 1. In a synchronous system the value of the signal is sensed only at clock times t_n=n/f_c. Thus the process is equivalent to sampling to create a discrete time logical signal, often referred to as a bit stream since it is an ordered series of ones and zeros recording the values of the logical variable at successive clock times. The bit stream thus constitutes an ordered series, x_n, corresponding to x(t_n).

A special member of this class is the series which is zero except for n = 0, which acts as a type of delta function. This will be designated by

where d_n0 is the Kronecker delta, and can be considered to be a sampling of D(t).

A new series, y_n may be generated from x_n by operating with the delay operator D according to the definition

Operation on D leads to

where it is clear that repetitive operations with the delay operator results in repetitive translation. In analogy with the general concepts of signal analysis, one can write a discrete signal in the form

The delay operation is realized in a shift register, where the value of each bit corresponds to that of the neighbouring bit of higher significance one clock pulse earlier, assuming shifting to the right. Thus the output of the m^th stage of such a shift register is related to the register input by the operation D^m.

15.2 Modulo 2 Arithmetic

In what follows the operations performed will be the AND and XOR operations. Formally the AND operation is equivalent to multiplication. The XOR operation is equivalent to the mod 2 sum. It should be pointed out that certain mathematical operations lead to a subtraction, which must also be interpreted as an XOR. This is consistent with the normal truth table except in the instance 0-1=1 which is necessary since negative one is not in the binary set. The AND and XOR operators are more conveniently represented by the arithmetic equivalents in what follows. In all mathematical expressions + or - is interpreted as the mod 2 sum. The subject of the behaviour and mathematical representation of modified shift register structures is of importance in several applications as will become apparent in what follows.

15.3 Feed-Forward Structures

Consider the modified 3-bit shift register shown above. The clock connections are not shown. If one labels the output of flip flop number i as x_i(t), where the FFS are labelled from right to left, then

where

A similar relation holds for each flip flop, namely

Combining the above leads to the input output relation

The quantity T is an operator created as a polynomial in D, and plays the role of a transfer function. With the input written explicitly as a bit stream the output becomes

The second form of the equation corresponds to the explicit relation between input and output bit streams,

This relationship indicates that the current output bit is a combination of the current and 3 previous bits in the input stream. In essence this structure "scrambles" the data, the details of the scrambling being determined by the set of coefficients a_r,r=0,3. This procedure may be used in cryptography, where coded messages may be created and the code changed frequently by changing the set of coefficients. The formulation is easily extended to an N-bit register. In the formalism the bit stream is represented as an infinite sequence. A finite message may be represented as an infinite sequence by assuming all zeros preceding and following the message.

The form of the process is such that the input-output relation for a pair of linear sequential circuits in series with transfer functions T₁ and T₂ is that for a transfer function T₁T₂.

15.4 Feedback Structures

The linear sequential machine with feedback structure is shown above. The transfer function can be ascertained by following through the circuit. The output from FF3 is

while that from FF2 is

Analysing FF1 gives

Recalling the equivalence between subtraction and addition in this arithmetic, the second equation can be solved to give

If the input to this system were itself the output of a feed forward device with a₀=1 and a_i=b_i,i=1,3 then the output would be the unscrambled message delayed 3 clock pulses. Thus a matched sender and receiver constitutes a secure information channel.

13.5 Autonomous Linear Sequential Machines

The structures described so far operate on an input bit stream. Feedback arrangements do not necessarily need inputs however, and an alternate arrangement shown in the accompanying diagram constitutes a system acting solely as a source.

Let the output of FFs 1 and 2 be y₁ and y₂ respectively. Then

Combined with

the three equations combine to give

This result is interpreted as a recursion relation of the form

and is written so that it is easily generalized to a system with N stages merely by replacing the upper limit of the sum.

The quantity

is referred to as the characteristic polynomial of the system. In principle analysis of the properties of this polynomial reveal the system behaviour. To proceed further without pursuing this rather erudite approach insight may be obtained with a specific example,

The corresponding circuit is shown in the figure. Comparison with the general N=3 configuration indicates c₁=c₃=1, while c₂=0. Since each FF receives the content of the immediate neighbour to the left, analysis of the behaviour of any one of the elements delineates the behaviour. The bit sequence for each FF therefore obeys the same recursive relation, in this case

In order to proceed further it is necessary to assume an initial configuration, referred to as a seed. It should be clear that the behaviour for a seed of 000 is uninteresting, since the system will simply remain in this state. Consider instead, the complement, 111.

The ensuing states may be determined by inspection. The input is the exclusive or of the first and third bits, which is a zero initially. Thus on clock pulse #1, FF1 goes to zero, and the first two bits of the previous configuration shift right. The input now becomes 1,so at the next clock pulse the 01 shifts right and FF1 is set low.

The following observations can be made.

1. Any FF is characterized by a sequence of period 7, ie 2^N-1, corresponding to the non-zero states of the register set R_N with N=3.

2. Any non-zero state acts as a seed.

3. The sequence is not obviously predictable.

It is noteworthy that the function G(z)=1/f(z) acts as a generating function. For example, for f(z)=1-z-z³, G(z)=1+z+z²+z⁴. Thus identifying z=D, this corresponds to the bit stream

which is 1110100 when the coefficients in the general expression are identified. This is the output sequence of the system. In general, sequences starting at different points can be generated by using a more detailed analysis of the relationship between G(D) and the seed. The sequence generated above corresponds to the set of previous values y_-3=y_-2=0 and y_-1=1. It is easily verified that the recursion relation also produces the sequence.

It is not guaranteed that the system will cycle through the complete set of non-zero states for any characteristic polynomial. Determining the general properties required is difficult, but a factorable polynomial will not meet the criterion. For example. consider the polynomial

with recursion relation y_n=y_n-3. For the initial configuration y_-3=y_-2=0 and y_-1=1, the sequence is 001001001001..., ie a period 3 sequence of 001. For the initial configuration 011, the sequence generated is 011011011..., again a period 3 sequence repeating the original configuration 011. Finally for an initial configuration 111, the output is constant at 1. For the first sequence the register cycles through the three states of unit weight according to 100,010,001. In the second the states of weight 2 are cycled through as 110,011,101. In the third the register is trapped in the state of weight 3, 111. This behaviour occurs because there is no weight-breaking transition as in the previous structure, where it was induced by the exclusive or operation.

The apparent unpredictability of the sequence is the property of most interest for these devices which are used to generate pseudo-random sequences in order to simulate noise. In general, these devices fall under the general category of (pseudo)random noise or number generators. Such devices, referred to in brief as random number generators play an important role in modern computational analysis of complex stochastic processes by simulation. This approach is generally described as the Monte Carlo method.

The generation of random noise signals is important in testing other devices. Actual random noise could be generated using Johnson noise in a resistor. The use of pseudo-random signals has a decided advantage however in that, unlike natural noise, they can be made to exactly replicate, by restarting from the same seed. This can be important when detailed comparisons of performance under modification or other variation is to be performed. The output bit stream corresponds to the binary random signal y(t), and as it is produced has a mean of 1/2, which is not consistent with the general definition. An improved version, r(t) is obtained from the transformation

This signal oscillates between the values 1 and -1 and hence should have a zero average if it is a proper noise simulator. To calculate the average consider the properties of the integers represented by the register states. For the full set of 2^N states there are an equal number of even and odd integers. Since the null state is not allowed, the set of integers contains an unpaired odd integer. The signal is generated from the LSB, the odd integers generating -1 and the even integers generating +1. If the period of the sequence is designated p=2^N-1, then the average is -1/p, which becomes vanishingly small if a large period sequence is used.

A second very important property is the autocorrelation function. It will be recalled that this is d(t) for white noise. The determination of the discrete version for the signal r(t) requires some rather delicate manoeuvring. First note that for an N-bit register with a non-degenerate characteristic polynomial, each of the p=2^N-1 non-zero seeds generates a sequence of period p. Thus there are a total of p such sequences, comprising a complete set. Each sequence constitutes a binary word of length p, X_r={y_ir,i=1,p}. This specially defined set, consisting of p words each of length p, is a very small subset of the set of all p-bit words, R_p.

A second method of generating sequences is by the method of translation as depicted in the accompanying diagram, for the N=3 case. By successive translations the complete set of p words is obtained. Consider the set of p+1 words consisting of all the sequences including that consisting of all zeros, designated X₀. This set has the special characteristic of being a group. The group operation is mod 2 addition or XOR. The identity element is X₀. Thus X_rrX₀=X_r. A word is its own inverse, X_rrX_r=X₀ since the XOR of a variable with itself is always 0. To complete the description, the illustrative example above will be used. The generating function for any infinite sequence can be written

Then since the recursion relation is y_n=y_n-1+y_n-3, then substituting gives

This leads to the solution for a general initial state as

Clearly the generating function for the sum (XOR)of two sequences is the sum of the generating functions of the sequences. The denominator of the sum will be the generating function and the terms in the numerator will be the same polynomial in D with the coefficients replaced by the XOR of the three corresponding bits of the initial states. Since the sum of any two 3-bit words remains a three bit word, the generating function corresponds to that for another of the set of sequences. Thus the sum of any two sequences is a member of the group, ie if X_r and X_s belong to the group so does X_rrX_s. It now remains to point out that the transformation from the sequence y to r=1-2y maps the XOR operation into the multiplication operation. To see this consider the corresponding tables shown.

The autocorrelation for the discrete signal is given by

The terms in the sum are products of the components of two series which correspond to the exclusive or between two of the binary sequences. Provided n is not zero the terms in the sum correspond to one of the p sequences of the set and hence the value of the autocorrelation is just the average value -1/p. On the other hand for n=0, then the two sequences are identical and the binary series is X₀. This corresponds to the r sequence consisting of all 1's so the autocorrelation function is 1. Hence, for large p, the approximate relation

is satisfied, corresponding to the discrete form of a white noise signal.