By the end of this chapter you should be able to:
- Draw a shift register built from D flip-flops and explain why one common clock, not a chain of clocks, is what makes the word move exactly one place per edge.
- Distinguish the SISO, SIPO, PISO and PIPO organisations, and read a timing diagram in which the data pattern advances one stage per clock.
- State the mode-control table of a universal shift register and trace its contents through a sequence of hold, shift-right, shift-left and parallel-load operations.
- Derive the state sequence of a ring counter and of a Johnson counter, and explain why the Johnson counter has \(2n\) states while the ring counter has only \(n\).
- Show that every state of a Johnson counter can be decoded by a two-input gate, and identify the illegal-state loop that makes an uncorrected design unusable.
- Design a sequence generator from a shift register with feedback, and explain why a maximal-length linear feedback shift register produces \(2^n - 1\) states rather than \(2^n\).
- Apply left and right shifting as multiplication and division by two, and state the conditions under which each of them gives a wrong answer.
Chapter 24 wired a group of flip-flops together so that their outputs, read as a binary number, advanced by one on every clock. A shift register uses the same flip-flops and the same common clock but a different interconnection: the output of each stage drives the input of the next, so that on every active edge the whole stored word slides one position sideways. Nothing is added and nothing is counted; the bits simply move.
That sounds like a smaller idea than a counter, and it is a much larger one. Moving a word one place at a time is how a parallel word is turned into a serial bit stream and back again, which is what every serial link in a system does at each end. It is also how a binary number is multiplied or divided by two, which is the operation at the heart of the multiplier of Chapter 17. And if the bit that falls out of the end is fed back into the front, the register stops being a data path and becomes a counter with a sequence you choose — a ring counter, a Johnson counter or a pseudo-random generator, depending only on what the feedback does to the bit on its way round. This chapter takes those in order: the four data paths first, then the universal register that offers all of them, then the three counters that feedback produces, then the applications that justify the whole arrangement.
1 Registers, Shifting and the Four Data Paths
A register is nothing more than a set of flip-flops sharing a clock, used to hold a word of \(n\) bits. Chapter 21 showed that an edge-triggered D flip-flop copies its input to its output at the active edge and ignores it at all other times, so \(n\) of them driven together store an \(n\)-bit word and change it only when told to. A shift register is that same set with one extra rule about where each D input comes from: the D input of stage \(i\) is the Q output of stage \(i-1\).
Everything that follows rests on why this does not simply copy the same bit into every stage at once. All the flip-flops see the same edge, and every one of them samples its input at that edge and produces its new output a propagation delay \(t_{pd}\) later. Stage \(i\) therefore captures the old output of stage \(i-1\), the value that was there before the edge, not the new one. The word moves one place, not all the way along, provided that the propagation delay of a stage exceeds the hold time of the stage it feeds — and in any real flip-flop family it does, by design. This is exactly the race condition Chapter 21 raised in connection with the master–slave arrangement, and it is why a shift register must never be built from level-sensitive latches: with transparent latches a single clock pulse would let a bit ripple through the entire chain.
Data can enter this structure in two ways and leave it in two ways, giving four named organisations. In serial-in, serial-out (SISO) operation one bit is presented at the serial input per clock and one bit is taken from the last stage per clock; the register is a delay element. In serial-in, parallel-out (SIPO) the bits go in one at a time but all \(n\) outputs are read at once after \(n\) clocks; this is a serial-to-parallel converter. Parallel-in, serial-out (PISO) reverses it, using a load input that presets every flip-flop simultaneously and then shifting the word out one bit per clock. Parallel-in, parallel-out (PIPO) loads and reads in parallel and does not shift at all — it is an ordinary storage register, included in the list for completeness. Notice that the same four flip-flops of Figure 25.1 support SISO and SIPO simultaneously: the parallel outputs are simply the Q pins, brought out to pads. Only parallel input needs extra hardware.
A four-bit register is cleared and the serial input is driven with 1, 1, 0 and 1 on clocks 1 to 4, then held at 0. Follow the contents.
| Clock | Serial in | Q₀ | Q₁ | Q₂ | Q₃ | Serial out |
|---|---|---|---|---|---|---|
| — | — | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 2 | 1 | 1 | 1 | 0 | 0 | 0 |
| 3 | 0 | 0 | 1 | 1 | 0 | 0 |
| 4 | 1 | 1 | 0 | 1 | 1 | 1 |
| 5 | 0 | 0 | 1 | 0 | 1 | 1 |
| 6 | 0 | 0 | 0 | 1 | 0 | 0 |
| 7 | 0 | 0 | 0 | 0 | 1 | 1 |
| 8 | 0 | 0 | 0 | 0 | 0 | 0 |
Two facts are worth extracting. First, after four clocks the register holds \(Q_0Q_1Q_2Q_3 = 1011\), and the bit that was applied first has travelled furthest — it now sits in \(Q_3\), not \(Q_0\). Second, that first bit appears at the serial output on clock 4 and not before, so the SISO path has delayed the stream by exactly four clock periods. Read the last column downwards from clock 4 and you recover 1, 1, 0, 1: the input sequence, unaltered and four clocks late.
All \(n\) flip-flops are clocked by the same edge, so stage \(i\) samples what stage \(i-1\) was holding before that edge. The requirement is \(t_{pd(\min)} \ge t_{h}\) — a stage must not change its output until its neighbour has finished capturing it. Level-sensitive latches violate this and let a bit run the length of the register in one clock pulse.
2 The Universal Shift Register and Bidirectional Shifting
Building four different registers because a system needs four different data paths is wasteful, and the standard MSI answer is a single device that can be told which path to use. A universal shift register puts a four-to-one multiplexer of the kind designed in Chapter 19 in front of every flip-flop, and drives all the multiplexers from a common pair of mode lines \(S_1S_0\). Each multiplexer chooses between four sources: the stage’s own output, the output of its left-hand neighbour, the output of its right-hand neighbour, and an external parallel input.
The four selections give the four operations, and because the same code is applied to every stage at once the whole register behaves consistently:
| \(S_1\) | \(S_0\) | Multiplexer input selected | Operation on the next clock |
|---|---|---|---|
| 0 | 0 | 0 — the stage’s own \(Q\) | Hold: contents unchanged |
| 0 | 1 | 1 — \(Q\) of stage \(i-1\) | Shift right: \(Q_i \leftarrow Q_{i-1}\), serial input enters \(Q_0\) |
| 1 | 0 | 2 — \(Q\) of stage \(i+1\) | Shift left: \(Q_i \leftarrow Q_{i+1}\), serial input enters \(Q_{n-1}\) |
| 1 | 1 | 3 — parallel input \(P_i\) | Parallel load: \(Q_i \leftarrow P_i\) |
The hold mode deserves a comment, because it is the reason the multiplexer has four inputs rather than three. It would be possible to hold the data by stopping the clock, and beginners often propose exactly that. Gating a clock is one of the few genuinely dangerous things one can do in synchronous design: the gate’s propagation delay skews that clock relative to every other clock in the system, and a glitch on the gating signal produces a spurious edge that the flip-flops cannot distinguish from a real one. Recirculating the data through the multiplexer holds the contents while leaving the clock untouched, and the 74194 four-bit bidirectional universal shift register — the classic part — does exactly this.
Bidirectional shifting is the pair of modes 01 and 10. Which direction is "right" is purely a labelling convention: if \(Q_0\) is drawn as the most significant bit, then a shift towards \(Q_3\) moves each bit towards a lower significance and is a right shift in the arithmetic sense. What matters electrically is that the two modes need different serial inputs at opposite ends of the register, so a bidirectional device has two serial input pins, one for each direction, and only the one belonging to the selected mode has any effect.
Starting from 0000, apply the mode codes 11 (with \(P = 1011\)), then 01 twice with the right-shift serial input tied to 0, then 00, then 10 twice with the left-shift serial input tied to 1. Follow \(Q_0Q_1Q_2Q_3\).
| Clock | \(S_1S_0\) | Operation | Contents after the edge |
|---|---|---|---|
| — | — | initial | 0000 |
| 1 | 11 | parallel load 1011 | 1011 |
| 2 | 01 | shift right, 0 in | 0101 |
| 3 | 01 | shift right, 0 in | 0010 |
| 4 | 00 | hold | 0010 |
| 5 | 10 | shift left, 1 in | 0101 |
| 6 | 10 | shift left, 1 in | 1011 |
The two right shifts have pushed the two least significant bits out of the end and lost them; the two left shifts bring in the 1s supplied on the left-shift serial input and happen to restore the original pattern only because that input was chosen to match the bits that fell out. Shifting is not reversible unless something remembers what left the register — which is precisely what the feedback of the next two sections provides.
3 The Ring Counter
Take the register of Figure 25.1 and connect \(Q_{n-1}\) back to the serial input, so that the bit falling out of the end re-enters the front. Nothing is lost and nothing is created: whatever pattern is loaded circulates for ever, returning to its starting position after \(n\) clocks. That is a ring counter, and its modulus is \(n\) — one state per flip-flop.
The pattern normally loaded is a single 1 among \(n-1\) zeros, which makes the outputs a one-hot code: exactly one output is high in each state, and the high output moves one place per clock. For \(n = 4\), preset to 1000:
| Clock | \(Q_0\) | \(Q_1\) | \(Q_2\) | \(Q_3\) | Meaning |
|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | phase 0 |
| 1 | 0 | 1 | 0 | 0 | phase 1 |
| 2 | 0 | 0 | 1 | 0 | phase 2 |
| 3 | 0 | 0 | 0 | 1 | phase 3 |
| 4 | 1 | 0 | 0 | 0 | back to phase 0 |
Compare this with the four-bit synchronous binary counter of Chapter 24, which also divides by four if only two of its stages are used. The binary counter is far more economical of flip-flops: \(n\) flip-flops give \(2^n\) states rather than \(n\). What the ring counter buys with those extra flip-flops is that no decoding is needed at all. To know that a binary counter is in state 6 you must build an AND gate on \(Q_2Q_1'Q_0'\), and Chapter 23 showed that such a gate produces a decoding glitch whenever two counter bits change at slightly different times. In a ring counter the flip-flop output is the decoded signal, so there is no decoding gate and therefore no decoding glitch. That is why ring counters survive in timing generators and in the sequencers that produce the non-overlapping phase signals a multi-phase system needs, where a glitch of a few nanoseconds would be fatal.
The weakness is the other \(2^n - n\) states. Four flip-flops have sixteen states and the ring counter uses four of them, so twelve are illegal, and the plain feedback connection does nothing to escape them. Loading 1100 by accident gives the closed loop 1100 → 0110 → 0011 → 1001 → 1100, a perfectly stable four-state cycle that is not the intended one; 0000 is a fixed point from which nothing ever moves. A ring counter is therefore useless without an initialisation that guarantees a legal state, normally an asynchronous preset on one flip-flop and clears on the rest, asserted at power-up.
4 The Johnson (Twisted-Ring) Counter
The ring counter wastes flip-flops because each of them is used to represent only one state. The Johnson counter, also called the twisted-ring or switch-tail counter, doubles the return for a single inverter: instead of feeding \(Q_{n-1}\) back to the serial input, it feeds back \(Q_{n-1}'\). Starting from all zeros, 1s march in from the left until the register is full, at which point the complemented feedback starts sending 0s and they march in behind them.
| Clock | \(Q_0\) | \(Q_1\) | \(Q_2\) | \(Q_3\) | Decoding gate |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | \(Q_0'Q_3'\) |
| 1 | 1 | 0 | 0 | 0 | \(Q_0Q_1'\) |
| 2 | 1 | 1 | 0 | 0 | \(Q_1Q_2'\) |
| 3 | 1 | 1 | 1 | 0 | \(Q_2Q_3'\) |
| 4 | 1 | 1 | 1 | 1 | \(Q_0Q_3\) |
| 5 | 0 | 1 | 1 | 1 | \(Q_0'Q_1\) |
| 6 | 0 | 0 | 1 | 1 | \(Q_1'Q_2\) |
| 7 | 0 | 0 | 0 | 1 | \(Q_2'Q_3\) |
| 8 | 0 | 0 | 0 | 0 | sequence repeats |
Eight states from four flip-flops, against the ring counter’s four. The count is \(2n\) in general, and the reason is easy to see once stated: the register can hold any pattern consisting of a block of 1s followed by a block of 0s, or a block of 0s followed by a block of 1s, and there are \(n+1\) of the first kind and \(n-1\) further distinct ones of the second, giving \(2n\) altogether. Every state has a single boundary between the two runs, and each clock moves that boundary one place along.
That structure is what gives the Johnson counter its decoding advantage. Because every state is a run of 1s followed by a run of 0s or the reverse, the position of the boundary identifies the state completely, and a boundary is visible in two adjacent outputs. State 1100 is the only state in which \(Q_1 = 1\) and \(Q_2 = 0\); state 0011 is the only one with \(Q_1 = 0\) and \(Q_2 = 1\). Every state therefore falls out of a single two-input AND gate, whatever the length of the counter, and the two states at the ends of the sequence use the pair \(Q_0, Q_{n-1}\). The decoding column of the table above lists all eight gates for \(n = 4\), and each has been checked against the other seven states to confirm that it is unique.
A modulo-8 binary counter needs 3 flip-flops but eight three-input decoding gates, and its decoded outputs glitch whenever two bits change together. A modulo-8 ring counter needs 8 flip-flops and no gates at all. A modulo-8 Johnson counter needs 4 flip-flops and eight two-input gates, and cannot glitch because only one flip-flop changes between consecutive states — the same unit-distance property that made Gray code useful in Chapter 4.
Four flip-flops give sixteen states and the Johnson sequence uses eight. Trace the other eight and they are found to form a second closed loop of their own length: 0010 → 1001 → 0100 → 1010 → 1101 → 0110 → 1011 → 0101 → 0010. A counter that powers up anywhere in this loop stays in it for ever, producing eight outputs that all look plausible and are all wrong.
The cure is to modify one stage’s excitation so that the legal cycle is untouched but every illegal state is steered out of the illegal loop. Every illegal state contains the pattern \(0\,1\) somewhere with a 1 further along — equivalently, the run structure is broken. Replacing the input of stage 1 by
rather than the plain \(D_1 = Q_0\) leaves all eight legal transitions unchanged, because in every legal state either \(Q_1 = 1\) or \(Q_3 = 0\), so the bracket is 1 whenever \(Q_0\) is being passed on.
Checking all sixteen states shows that each of the eight illegal ones now reaches the legal sequence within five clocks; the longest path is 0100 → 1010 → 1101 → 0110 → 1011 → 0001, and 0001 is a legal state. One two-input OR gate and one two-input AND gate have converted a counter that can fail permanently into one that recovers by itself, which is the same self-starting requirement Chapter 24 imposed on synchronous counters with unused states.
5 Sequence Generators and the LFSR
Ring and Johnson counters are two points on a continuum. In general, put any combinational function of the register outputs into the serial input and you have a sequence generator: a machine whose output is a fixed, repeating bit pattern of a length you choose. The design question is the reverse of the analysis so far — given the sequence, what feedback produces it?
Two constraints fix the size of the register. A sequence of length \(L\) needs \(L\) distinct states, so \(2^n \ge L\) and \(n \ge \lceil \log_2 L \rceil\). And because the state of the register is the last \(n\) bits emitted, no two positions in the sequence may present the same \(n\)-bit window followed by different next bits — if they do, the register cannot tell them apart and \(n\) must be increased. Once \(n\) is settled, the required next bit is tabulated against the \(L\) states and the feedback function is minimised on a Karnaugh map exactly as in Chapter 8, with the \(2^n - L\) unused states entered as don’t-cares.
The most useful special case takes the feedback to be an exclusive-OR of two or more taps, which makes the machine a linear feedback shift register (LFSR). Its behaviour is remarkable: with the right taps an \(n\)-stage LFSR visits every state except all-zeros before repeating, giving a period of \(2^n - 1\). All-zeros is excluded because exclusive-OR of zeros is zero, so that state feeds itself and the register locks up — the one lock-out condition an LFSR always has, and the reason a real design forces a non-zero seed at reset.
Take a four-bit right-shifting register with the feedback
and seed it with 1000. Following the register through gives the states
1000 0100 0010 1001 1100 0110 1011 0101 1010 1101 1110 1111 0111 0011 0001
and then 1000 again: fifteen distinct states, which is \(2^4 - 1\), so the taps are maximal. Reading the last flip-flop \(Q_3\) down that list gives the output stream
0 0 0 1 0 0 1 1 0 1 0 1 1 1 1
which repeats with period 15. The stream contains eight 1s and seven 0s, has runs of every length from 1 to 4, and its autocorrelation is flat — the properties that make it a pseudo-random binary sequence. It is entirely deterministic, which is what makes it useful: a receiver running an identical LFSR in step can predict every bit. Three widely used applications follow directly — built-in self test, where an LFSR generates test patterns and a second one compresses the responses into a signature; data scrambling on serial links, to break up long runs that would starve a clock-recovery loop; and cyclic redundancy checking, where the same shift-and-exclusive-OR structure computes the check word.
The all-zero state is not in the list, and must not be allowed to occur: with 0000 loaded, \(D_0 = 0 \oplus 0 = 0\) and the register stays there for ever. A reset that presets any single flip-flop is sufficient.
6 Applications: Conversion, Delay and Arithmetic Shifting
Three applications justify the effort, and each of them is a place where the shift register is not a convenience but the only sensible structure.
Serial-to-parallel and parallel-to-serial conversion. A parallel bus of \(n\) lines costs \(n\) conductors, \(n\) drivers and \(n\) receivers, and its skew grows with length until the bits of one word no longer arrive together. A serial link costs one conductor and pays for it in time. A PISO register at the transmitter is loaded in parallel from the bus and clocked out one bit at a time; a SIPO register at the receiver clocks the bits in and presents the reassembled word in parallel after \(n\) clocks. This is the core of every UART, of SPI and of the serialiser in a high-speed link, and the only additional machinery is the framing that tells the receiver where a word starts — itself usually a state machine of the kind Chapter 26 designs.
Digital delay lines. Worked Example 25.1 showed a SISO register delaying a bit stream by exactly four clock periods. In general an \(n\)-stage register delays by
so an eight-stage register clocked at 10 MHz delays by 800 ns, and a sixteen-stage register at 25 MHz by 640 ns. The delay is set by counting, not by a propagation time, so it is exact, temperature-independent and adjustable by changing the clock — none of which is true of a delay built from cascaded gates. Digital filters use the same structure to hold the past samples that a difference equation needs.
Arithmetic shifting. Shifting a binary number one place left multiplies it by two and shifting it one place right divides it by two, because both operations move every digit one position in a positional notation of radix 2. A shifter is therefore a multiplier by two that costs no gates at all, and the array multiplier of Chapter 17 is built from shifted additions for exactly this reason.
Two rules govern the signed case of Chapter 3. On a right shift the vacated most significant position must be filled with a copy of the sign bit, not with a zero: this is an arithmetic right shift, and it is what distinguishes division from a logical right shift that always brings in 0. On a left shift there is no fill to choose — a 0 enters at the bottom — but the result overflows whenever the sign bit changes, because the true product no longer fits.
| Word (4-bit 2’s complement) | Value | Left shift | Arithmetic right shift | Logical right shift |
|---|---|---|---|---|
0011 | +3 | 0110 = +6 ✓ | 0001 = +1 ✓ | 0001 = +1 |
0110 | +6 | 1100 = −4 ✗ overflow | 0011 = +3 ✓ | 0011 = +3 |
1110 | −2 | 1100 = −4 ✓ | 1111 = −1 ✓ | 0111 = +7 ✗ |
1010 | −6 | 0100 = +4 ✗ overflow | 1101 = −3 ✓ | 0101 = +5 ✗ |
The arithmetic right shift column reproduces \(\lfloor v/2 \rfloor\) in every row, including the negative ones: \(-6\) becomes \(-3\) and \(-2\) becomes \(-1\). The logical column is wrong for both negative values, and the left-shift column overflows in the two cases where doubling leaves the range \([-8, +7]\), detected by the sign bit changing. In a universal shift register the arithmetic right shift is obtained simply by tying the right-shift serial input to \(Q_0\), the sign bit, instead of to ground.
Shifting by more than one place per clock needs a barrel shifter, a purely combinational network of multiplexers that moves a word by any amount in one gate delay; that structure is a natural exercise in the multiplexer techniques of Chapter 19 and appears again in the arithmetic unit of Chapter 20.
7 Summary and Key Results
| Arrangement | Feedback or control | Sequence or function |
|---|---|---|
| SISO register | none; serial input driven externally | Delays a bit stream by \(n\) clock periods exactly |
| SIPO / PISO register | none; parallel outputs or a load input | Serial-to-parallel and parallel-to-serial conversion in \(n\) clocks |
| Universal register | \(S_1S_0\) selecting a 4-to-1 MUX per stage | 00 hold, 01 shift right, 10 shift left, 11 parallel load |
| Ring counter | \(D_0 = Q_{n-1}\) | \(n\) states, one-hot, needs no decoding gates at all |
| Johnson counter | \(D_0 = Q_{n-1}'\) | \(2n\) states, each decoded by one two-input gate |
| LFSR | \(D_0 = Q_i \oplus Q_j\) with maximal taps | \(2^n - 1\) states; all-zeros locks up and must be avoided |
| Arithmetic shifter | left shift, or right shift with sign fill | \(\times 2\) with overflow if the sign changes; \(\lfloor v/2 \rfloor\) exactly |
8 Common Mistakes
A transparent latch passes its input straight to its output while the clock is high, so a single wide clock pulse lets one bit run the whole length of the chain instead of advancing by one stage. The register must be built from edge-triggered or master–slave flip-flops, and the design condition is that the minimum propagation delay of a stage is at least the hold time of the stage it drives. This is the same race that Chapter 21 used to justify the master–slave arrangement in the first place.
Stopping the clock looks like the obvious way to freeze a register, and it introduces a gate delay into the clock path of that register alone, skewing it against every other clocked element in the system, while any glitch on the gating signal becomes a spurious clock edge. The correct hold mode recirculates each output back to its own input through the mode multiplexer and leaves the clock running untouched, which is why mode 00 exists on the 74194.
Both counters use far fewer states than their flip-flops provide, and in both cases the unused states form closed loops of their own: twelve unused states for a four-bit ring counter, and a complete eight-state parallel loop for a four-bit Johnson counter. Nothing in the plain feedback connection ever leaves those loops. Either force a legal state with an asynchronous preset at power-up, or modify one stage’s excitation as in Worked Example 25.3 so that the counter corrects itself.
9 Chapter Review
1. A four-bit SIPO register is cleared and then fed the serial sequence 1, 0, 1, 1 on four successive clocks. What does it hold afterwards, and which flip-flop contains the bit that was applied first?
After clock 1 the contents are 1000, after clock 2 they are 0100, after clock 3 1010 and after clock 4 \(Q_0Q_1Q_2Q_3 = 1101\). The bit applied first has been shifted by three further clocks and now sits in \(Q_3\), the last stage. The general rule is that the earliest bit ends up furthest along, so a word clocked in most-significant-bit-first is read out of the parallel pins with its most significant bit at the far end of the register — a wiring detail that decides whether the parallel output needs reversing.
2. Why does a Johnson counter have \(2n\) states rather than the \(2^n\) that \(n\) flip-flops could in principle support, and what does it get in exchange for the states it gives up?
Because the only patterns reachable from a legal state are those consisting of one run of 1s and one run of 0s. Each clock moves the single boundary between the two runs one place along, and after \(n\) clocks the register is full of 1s, after another \(n\) it is full of 0s, so the cycle closes at \(2n\). What it buys is decoding: because exactly one flip-flop changes per clock and every state has a unique run boundary, each of the \(2n\) states is identified by a two-input AND gate on an adjacent pair of outputs, with no possibility of a decoding glitch. A binary counter of the same modulus would need \(\log_2 2n\)-input gates and would glitch.
3. A four-bit Johnson counter powers up holding 0110. Show that it never reaches its intended sequence, and give a modification that repairs the fault.
With \(D_0 = Q_3'\) the successor of 0110 is 1011, then 0101, then 0010, then 1001, then 0100, then 1010, then 1101, then 0110 again — a closed loop of eight illegal states that never touches the legal sequence 0000, 1000, 1100, 1110, 1111, 0111, 0011, 0001. Replacing the input of the second stage by \(D_1 = Q_0(Q_1 + Q_3')\) leaves every legal transition unaltered, because in each legal state either \(Q_1 = 1\) or \(Q_3 = 0\), while steering all eight illegal states into the legal cycle within at most five clocks. The cost is one OR gate and one AND gate.
4. A four-bit register with \(D_0 = Q_2 \oplus Q_3\) is seeded with 0001. How many distinct states does it pass through, what happens if it is seeded with 0000, and why?
Fifteen. The taps are maximal, so the register visits every four-bit pattern except 0000 before returning to its seed, giving a period of \(2^4 - 1 = 15\). Seeded with 0000 the feedback is \(0 \oplus 0 = 0\), so 0000 is a fixed point and the register never leaves it. The all-zero state is excluded from every LFSR cycle for this reason, which is why the period is \(2^n - 1\) and not \(2^n\), and why a practical design forces a non-zero seed at reset rather than relying on a general clear.
5. An eight-bit register holds \(11011000\), interpreted as a two’s complement number. Give the result of one arithmetic right shift and of one left shift, and say whether either is arithmetically correct.
\(11011000\) has its sign bit set, so its value is \(11011000_2 - 2^8 = 216 - 256 = -40\). An arithmetic right shift copies the sign bit into the vacated position, giving \(11101100 = 236 - 256 = -20\), which is \(-40/2\) exactly — correct. A logical right shift would give \(01101100 = +108\), which is not. The left shift gives \(10110000 = 176 - 256 = -80\), which is \(2 \times (-40)\) and is also correct; the sign bit stayed at 1, and it is precisely when the sign bit changes on a left shift that the doubled value has left the representable range and the result must be rejected as an overflow.