Registers and shift registers

Why it exists

A single flip-flop stores one bit. A processor stores words: the program counter, the instruction register, the accumulator. A register is a row of flip-flops that are loaded and read together. A shift register moves its contents one position on each clock pulse, which is how data is converted between serial and parallel form (a keyboard, a serial port, a network interface), how a processor multiplies and divides by powers of two, and how many arithmetic units step through the bits of an operand. GATE asks for the contents after some clock pulses, the number of pulses needed, the type of shift register for a task, and what shifts do to a number.

Prerequisites

You need the D flip-flop from latches and flip-flops.

Precise definitions

Register. $n$ D flip-flops with a common clock. Loading a word means putting it on the $D$ inputs before the clock edge; after the edge the flip-flops hold it. To keep the old value when not loading, add a load control $L$: each stage has a 2:1 multiplexer $D_i = L\,I_i + L'\,Q_i$ (new data when $L = 1$, own output when $L = 0$). An $n$-bit loadable register is $n$ flip-flops and $n$ 2:1 multiplexers.

Shift register. A register whose stages are connected in a chain: each stage's $D$ input is the previous stage's $Q$. At every clock edge all stages copy their neighbour simultaneously, so the data moves one position. In this page shift left means toward the more significant end, so $Q_i \leftarrow Q_{i-1}$ and the serial input enters $Q_0$ (as in the animation below), and shift right means $Q_i \leftarrow Q_{i+1}$.

Types by how data enters and leaves:

SIPO converts serial data to parallel in $n$ clock pulses; PISO converts parallel data to serial in $n$ pulses. A word shifted in serially emerges in the same order after $n$ more pulses (first in, first out).

Universal shift register. One register that can hold, shift left, shift right and load in parallel, selected by a 2-bit mode input $S_1 S_0$. Each stage has a 4:1 multiplexer in front of its flip-flop: input 0 is the stage's own $Q$ (hold), input 1 is the upper neighbour $Q_{i+1}$ (shift right), input 2 is the lower neighbour $Q_{i-1}$ (shift left), input 3 is the parallel input. An $n$-bit universal shift register is $n$ flip-flops and $n$ 4:1 multiplexers.

Shifts as arithmetic. For an $n$-bit register:

• Logical shift left by one: a 0 enters at the bottom, the top bit goes to the carry. For an unsigned number this multiplies by 2, correct if the carry out is 0.
• Logical shift right: a 0 enters at the top. For an unsigned number this is integer division by 2 ($\lfloor x / 2 \rfloor$).
• Arithmetic shift right: the sign bit is copied back into the top. For a 2's complement number this is $\lfloor x / 2 \rfloor$, rounding toward minus infinity (so $-74 \to -37$ and $-5 \to -3$).
• Arithmetic shift left: the same as logical shift left; the result is correct unless the sign bit changes (overflow).
• Rotate (circular shift): the bit that leaves one end enters at the other. $n$ rotations in one direction restore the register.

Serial adder. Two shift registers hold the operands, one full adder adds one pair of bits per clock pulse starting from the least significant bit, and a carry flip-flop keeps the carry for the next pulse. The sum bits are shifted into one of the registers. It needs $n$ pulses and one full adder, against one step and $n$ full adders for a parallel adder: slower but much cheaper.

Clocking. All stages share one clock, so every stage changes at the same instant (a synchronous shift register). The data that a stage copies is the neighbour's value just before the edge; it is not the new value, which is why the data advances one stage per pulse and not all the way through.

How it works

Step through four clock pulses shifting in the serial input 1, 0, 1, 1. At each rising edge every stage takes the value of its left neighbour (the serial input for $Q_0$), so the first bit entered ends up in $Q_3$ after four pulses.

The data-path view of the same hardware: what shifts and rotates do to the value in an 8-bit register, read as an unsigned number and as a 2's complement number.

register = 1011 0110

Worked examples

#include <stdio.h>
#include <stdint.h>
 
static void show(const char *what, uint8_t x) {
    printf("%-24s", what);
    for (int i = 7; i >= 0; i--) putchar(((x >> i) & 1) ? '1' : '0');
    printf("  unsigned %3u  signed %4d\n", x, (int8_t)x);
}
 
/* serial adder: one full adder and one carry flip-flop, least significant bits first */
static unsigned serial_add(unsigned a, unsigned b, int n, int *carry_out) {
    int carry = 0;
    unsigned s = 0;
    for (int i = 0; i < n; i++) {
        int x = (a >> i) & 1, y = (b >> i) & 1;
        s |= (unsigned)(x ^ y ^ carry) << i;
        carry = (x & y) | (carry & (x ^ y));
    }
    *carry_out = carry;
    return s;
}
 
int main(void) {
    uint8_t v = 0xB6;
    show("start", v);
    show("logical shift left", (uint8_t)(v << 1));
    show("logical shift right", (uint8_t)(v >> 1));
    show("arithmetic shift right", (uint8_t)(((int8_t)v) >> 1));
    show("rotate left", (uint8_t)((v << 1) | (v >> 7)));
    show("rotate right", (uint8_t)((v >> 1) | (v << 7)));
    int c;
    unsigned s = serial_add(11, 6, 4, &c);
    printf("serial adder, 4 clock pulses: 1011 + 0110 gives sum bits %u and carry %d\n", s, c);
    int bad = 0;
    for (unsigned a = 0; a < 16; a++)
        for (unsigned b = 0; b < 16; b++) {
            unsigned r = serial_add(a, b, 4, &c);
            bad += r + ((unsigned)c << 4) != a + b;
        }
    printf("serial adder wrong on %d of 256 pairs\n", bad);
    return 0;
}

start                   10110110  unsigned 182  signed  -74
logical shift left      01101100  unsigned 108  signed  108
logical shift right     01011011  unsigned  91  signed   91
arithmetic shift right  11011011  unsigned 219  signed  -37
rotate left             01101101  unsigned 109  signed  109
rotate right            01011011  unsigned  91  signed   91
serial adder, 4 clock pulses: 1011 + 0110 gives sum bits 1 and carry 1
serial adder wrong on 0 of 256 pairs

Cheat box

Traps and GATE patterns

Connections

A shift register with feedback is a counter (ring and Johnson). Each stage of a universal shift register is a multiplexer in front of a flip-flop. A serial adder is the full adder of adders and subtractors used once per bit. The shift microoperations of the processor rely on signed number representation, and the registers in the datapath are the state elements of the instruction cycle.

PYQs

Consider the given sequential circuit designed
using D-Flip-flops. The circuit is initialized with
some value (initial state). The number of distinct
states the circuit will go through before returning to
the initial state is . (Answer in integer)

Consider the sequential circuit shown in the figure,
where both flip-flops used are positive edge-triggered
D flip-flops. The number of states in the state
transition diagram of this circuit that have a transition
back to the same state on some value of "in" is ______

What is the final value stored in the linear feedback
shift register if the input is 1011101?

Consider the circuit in the diagram. The operator
represents Ex-OR. The D flip-flops are initialized
to zeroes (cleared)

The following data: is supplied to the "data"
terminal in nine clock cycles. After that the values of
q2q1qo are:

Self-check

Revision card

References