NMI TR18
Shift Registers with Feedback Configured as Counter-dividers
Greig W Small
© Commonwealth of Australia 2014
First edition — June 2014
Second edition — July 2016
National Measurement Institute
Bradfield Road, Lindfield, NSW 2070
PO Box 264, Lindfield, NSW 2070
T (61 2) 8467 3600
F (61 2) 8467 3610
W www.measurement.gov.au
CONTENTS
1 Introduction 4
2 Shift Registers with Feedback to the Input 4
2.1 Some Definitions 6
2.2 Some Observations 6
2.3 Corollary 6
3 Shift Registers of the Twisted-ring Configuration 6
3.1 Propositions 7
3.2 Examples of Loop Structures 8
3.3 Systematic Generation of Loop Sequences 9
4 Derived Counting Sequences 11
4.1 Combining Loops 11
4.2 Merging of Loops 11
4.3 Associated Sequences 13
4.4 Attachment of One Loop to Another 14
4.5 Modifying Maximum-length Sequences 14
4.6 Automated Design of Shift Register Counter-dividers 15
5 Some Examples of Counter Design 16
5.1 Modulo-158 Counter with Symmetrical Output 16
5.2 Non-integer Divider Modulo 101/27 18
6 Conclusion 19
7 References 19
ABSTRACT
Binary counters are conventionally adopted as counters and dividers. Where the natural binary sequence of counting states is the required output, such counters are obviously the most appropriate. In other applications, however, such as frequency scaling and shift register based waveform synthesis, counters based on shift registers with feedback may offer advantages of simplicity of programming and of modulating the count modulus. The implementation of shift registers with feedback to their input is particularly effective in programmable gate arrays, in which the coding of the feedback states is interpreted as a look-up table.
Keywords: shift registers, linear feedback shift registers, programmable dividers, modulated dividers, phase-locked loops.
1 Introduction
Conventional binary counters are the obvious choice for event counting, for sequential addressing of look-up tables in waveform synthesis and in many other applications. In frequency synthesis, however, where either fixed or programmable division ratios are required, binary counters are clumsy. Modifying the counting base of a binary counter usually implies resetting on carry overflow to the ones-complement of the required base. Either every bit must be reset or, if the counting base is fixed, the pattern of bits to be reset is specific to the base and requires a custom design. In either case the advantages of sequential binary counting are compromised by the loss of a number of counts starting from zero.
An alternative configuration that retains some semblance of the natural binary sequence is the rate-feedback binary counter [1], in which the output signals from several stages are combined with interlacing and caused to advance the count, and so to modify the count modulus.
The more effective tool in programmable frequency synthesis is the accumulator rate multiplier, better known by the term direct digital synthesis (DDS). Again, the natural binary sequence, or binary-coded decimal sequence, is to some extent retained.
In cases of fixed-frequency synthesis where the natural binary sequence is irrelevant, continued-fraction dividers offer accurate approximations to irrational ratios [2].
Another type of counter comprises a shift register with feedback to the input from one or more taps combined in the exclusive-OR (XOR) function. Known as linear feedback shift registers (LFSRs), these are able to generate long (2N – 1) pseudo-random sequences of output bits with a modest number (N) of shift-register stages. Usually the zero state is a persistent state and must be excluded, requiring additional logic or at least a power-up reset to a non-zero state.
If the feedback is inverting and from the output stage only, the counter is called a twisted-ring counter. An adaptation of this is the Johnson counter, where the shift register fills progressively with ones and, when full, progressively with zeros. Usually the output bits from the N stages are gated to generate 2N separate signals, changing in sequence to 1 (or 0) whilst all others are 0 (or 1). A 5-stage Johnson counter was popularly used with numerical displays based on glow discharge (Nixie) tubes, where each of the ten output signals of the counter enabled the selection of one of the ten cathodes. In the Johnson counter there is the possibility of entering an unintended loop on start-up or from some transient interference. This is counteracted with additional logic to count out of the unwanted loop or loops.
Although specific designs of shift-register counters may be found by searching the Internet, there appears to be no comprehensive theory of design in the literature. Here the theory and systematic design of shift registers as counter-dividers, with feedback exclusively to the input stage, is developed and their versatility and economy of design is demonstrated.
2 Shift Registers with Feedback to the Input
The configuration of an N-stage shift register counter with count control by feedback to the input stage is shown in Figure 1. The data-in signal is an explicit Boolean function of the N output signals of the shift register. A logic gate generates the carry-out signal from a designated terminal state of the shift register.
This configuration is particularly suited to implementation in a programmable gate array (PGA), which is comprised of a number of identical programmable combination logic blocks and a versatile programmable interconnection network between logic blocks and from logic blocks to input and output blocks. An example of a combination logic block, simplified as is appropriate and relevant to a shift-register counter, is shown in Figure 2.
Figure 1: Shift-register counter with control at the input stage
Figure 2: Simplified example of a PGA combination logic block
In Figure 2, L represents the combination logic and M is a programmable multiplexer. The logic is implemented as a look-up table and as such is capable of representing every possible one-bit Boolean function of the several input bits. In practice the combination logic block is usually presented as a schematic diagram of gates and D flip-flops. In compilation the look-up table is generated by evaluating the output of this gate array for all possible values of the several inputs. Consequently, the designer has the freedom to represent the logic in any form that generates the desired result, without regard to the complexity of that representation. For example, Figure 3 shows four different representations of the exclusive-or (XOR) function.
Figure 3: Different representations of the exclusive-or function
The upper diagrams are the conventional symbol and a construction from two-input NAND gates; the lower diagrams are the arithmetic functions of selective complement and addition of two bits. The designer is free to choose a representation that clarifies his intention.
2.1 Some Definitions
The number of stages in a shift register is denoted by N. The total number of possible states is then 2N.
The state of a shift register is denoted by S. In particular, S may be assigned a numerical value by regarding the pattern of bits of the shift register as a binary number. It is convenient to assign to the output of the final stage the most significant bit (msb) and accordingly to the output of the input stage the least significant bit (lsb). The 2N possible states then correspond to the numerical values 0, 1 … 2N – 1.
The ones-complement (cp) of S is denoted by S; cp(S) = S = (2N – 1) – S.
Both bits and states may be concatenated. Concatenation is denoted by { … }.
The rump R of S is a subset of S. Examples are S = {msb, R} and S = {R, lsb}.
The data-in bit is denoted by d.
One shift of the contents of the shift register is denoted by sh( ); sh(S) = {R, d}. Multiple shifts are defined by shn + 1(S) = sh(shn(S)).
Numerically, sh(S) = (2S + d) modulo 2N. That is, if S is of the form {0, R} then
sh(S) = 2S + d, and if S is of the form {1, R} then sh(S) = 2S + d – 2N.
2.2 Some Observations
Note that the result of a shift may be the same for either of a pair of precursor states. If the data-in bit is the same, the two states {0, R} and {1, R} both result in {R, d}. Such pairs of states shall be termed congruent pairs, since they are congruent modulo 2N – 1.
Note that sh(S) may result in either of two possible successor states, {R, 0} or {R, 1}, according to whether d is 0 or 1. Such pairs of states shall be termed sibling pairs.
Note that each of a sibling pair may have a precursor, or one may have two precursors in which case the other has none.
Note that exactly two states in a given shift register may be their own precursor/successor. These states are either when all N bits are 0 (S = 0) or when all are 1 (S = 2N – 1). No other state has this property.
2.3 Corollary
The only possible state sequences are loops, in which each state has exactly one precursor, or strings that begin with a state that has no precursor and must lead eventually to a loop, possibly entering into another string on the way. Since every state must have a successor, there can be no isolated string, although a string that leads to a state that is its own precursor/successor may appear to be an isolated string.
The bit values of a shift register constitute a record of the most recent N values of d. A succession of states may be identified either as a sequence of state values, or as a sequence of data-in bits. The two representations are equivalent.
3 Shift Registers of the Twisted-ring Configuration
As noted above, a shift register with inverting feedback from the output stage to the input stage is termed a twisted-ring shift register. Without additional logic, there will in general be multiple sequences of states, each of which accounts for a distinct subset of all possible states. Normally, in a Johnson ring counter all but one of these possible subsets are excluded by additional logic.
3.1 Propositions
Proposition 1: For every N there is at least one loop of length 2N
Proof
Let the initial state S1 be zero, corresponding to all bi = 0. At each shift the most significant zero is shifted out and its complement is shifted in as the least significant bit. Hence N shifts are required to replace S1 by its complement S1 (all bi = 1) and a further N shifts to restore the original state S1.
Proposition 2: For every odd N there is exactly one loop of length 2
Proof
Let the initial state be S1. For there to be a loop of length 2, it is necessary that:
sh(S1) = S1
so that sh(sh(S1)) = sh(S1) = S1
That is, in one shift each bit of S1 is replaced by its complement. Hence bi = bi+1 for all i, and so the bit pattern is an alternating sequence of ones and zeros. Further, since in one shift the msb is replaced by its complement as the lsb, the msb must be the same as the lsb. This can be true only for odd values of N.
The numerical value of S1 may be determined by evaluating the binary interpretation of the alternating sequence of zeros and ones. Alternatively it may be calculated directly.
Let S1 belong to the lower half (msb = 0) of the field of all possible state values. Then:
S1 = sh(S1) = 2S1 + 1
and S1 = (2N – 1) – S1 (ones complement of S1)
from which 3S1 = 2N – 2
Now the residues of 2N modulo 3 are 2, 1, 2, 1, 2 … for N = 1, 2, 3, 4, 5 … respectively. Hence for odd values only of N:
S1 = (2N – 2)/3
The solution is unique – there is only one such loop for each value of N.
Proposition 3: For every shift register of length (2n + 1)N there will be a loop of length 2N corresponding to each loop of length 2N in a shift register of length N
Proof
Let S(1) be a state of any loop of length 2N in an N-stage shift register. Generate the state S(2n + 1) by concatenating S(1), S(1), S(1) … for a total of 2n + 1 times. Then {S(1), S(1), S(1) …} is a state in a (2n + 1)N-stage shift register.
Since shN(S(1)) = S(1)
it follows that shN(S(2n + 1)) = shN{S (1), S(1), S(1) …}
= {S(1), S(1), S(1) …}
and sh2N(S(2n + 1)) = shN{S(1), S(1), S(1) …}
= {S(1), S(1), S(1) …}
Therefore the concatenated state is a state in a shift register of length (2n + 1)N that is periodic in 2N shifts; that is, it is a state of a loop of length 2N.
Corollary
The only loops of length 2N in a shift register of length (2n + 1)N are those corresponding to the loops of length 2N in a shift register of length N.
Consider an indefinitely long shift register with feedback from the output of the Nth stage, with an initial state {U, S(1)} where U signifies ‘undefined’ and S(1) is a state of a loop of length 2N in an N-stage shift register.