Chapter 11 of 39

Register Transfer & Micro-operations

On this page

Think of a processor as a busy kitchen. The registers are small bowls on the counter, each holding one ingredient. Every tick of the clock, the cook does a few simple things: pours one bowl into another, mixes two bowls, or shifts something to the side. A full recipe (an instruction like ADD R1, R2) is just a short sequence of these tiny steps.

In Sequential Circuits: Flip-Flops, Registers & Counters we built registers out of flip-flops. This chapter answers the next question: how do we describe, precisely and compactly, what happens to the data inside those registers on each clock pulse? The answer is Register Transfer Language (RTL) and the small operations it describes, called micro-operations.

A micro-operation is an elementary operation performed on the data stored in one or more registers during one clock pulse, such as transfer, add, AND, or shift.

Register Transfer Language (RTL) is a symbolic notation used to describe the micro-operations of a digital system and the control conditions under which they happen.

RTL is not a programming language you run. It is a precise shorthand that hardware designers (and exam papers) use to say "on this clock edge, if this condition is true, this register gets this value". Once you can read RTL, the later chapters on the instruction cycle, datapath and control unit become much easier.


Why We Need RTL

Any digital system, from a simple calculator to a CPU, can be described by three things:

  1. the set of registers it has and what each one holds,

  2. the micro-operations performed on the data in those registers, and

  3. the control signals that decide which micro-operation happens when.

Drawing gate-level circuits for all of this would be enormous. RTL lets us describe the same behaviour in a few lines, and each line maps directly to hardware: a register with a load input, a bus, an adder and a control signal. That direct mapping is why it is the standard language for describing processors at this level.


Naming Registers

Registers are written in capital letters, usually naming their job:

Name

Register

Holds

PC

Program Counter

Address of the next instruction

IR

Instruction Register

The instruction currently being executed

AR or MAR

(Memory) Address Register

The memory address being accessed

DR or MDR

Data Register / Memory Data Register

Data read from or written to memory

AC

Accumulator

The main working register in simple CPUs

R1, R2, ...

General-purpose registers

Any data

Parts of a register can be named too. For a 16-bit register R2, R2(0-7) or R2(L) is the low byte, R2(8-15) or R2(H) is the high byte, and R2(15) is the single most significant bit. Bits are numbered from 0 at the right (least significant end).

          R2 (16 bits)
 15                         8 7                          0
+-----------------------------+----------------------------+
|        R2(H) = R2(8-15)     |       R2(L) = R2(0-7)      |
+-----------------------------+----------------------------+

The Basic Register Transfer

The simplest micro-operation copies one register into another:

R2 ← R1

Read it as "R2 gets R1" or "load R2 with the contents of R1". Three facts hide in this little line:

  • The transfer is non-destructive for the source: R1 keeps its value. Only the destination changes.

  • In hardware there is a path (wires) from the outputs of R1 to the inputs of R2, and R2's load (enable) input is activated.

  • The change happens at a clock edge. Between edges, R2 holds its old value.

Conditional Transfer and Control Functions

Usually we only want a transfer to happen when some control condition is true. RTL writes the condition before a colon:

P: R2 ← R1          means:   if (P = 1) then R2 ← R1

Here P is a control function, a Boolean signal produced by the control unit. In hardware, P is simply wired to R2's load input. On the clock edge, if P = 1 the new value is loaded; if P = 0 nothing happens.

               +--------+
  P ---------->| Load   |
               |   R2   |<==== n wires ==== R1 outputs
 Clock ------->|>       |
               +--------+

  Timing:   clock edge at t:  P = 1  →  R2 takes R1's value
                              P = 0  →  R2 keeps its old value

Control functions can be any Boolean expression, for example T2·I': AR ← M[AR] or x'T0 + yT1: R1 ← 0. Here · (or simply writing symbols side by side) is AND, + in a control function is OR, and ' is NOT.

Simultaneous Transfers

A comma separates micro-operations that happen in the same clock pulse:

T: R1 ← R2, R2 ← R1

This swaps R1 and R2 in a single clock cycle, with no temporary register. Why doesn't R2 just get the new value of R1? Because the registers are built from edge-triggered flip-flops. At the clock edge, both registers sample the values that were sitting on their inputs just before the edge, which are the old values. After the edge both update together. (In software, a = b; b = a; would not swap, because statements run one after another.)

RTL Symbols at a Glance

Symbol

Meaning

Example

Capital letters (and digits)

A register

AR, R2, PC

Parentheses

Part of a register

R2(0-7), R1(L)

Arrow ←

Transfer of information

R2 ← R1

Colon :

Ends a control condition

P: R2 ← R1

Comma ,

Separates simultaneous micro-operations

R1 ← R2, R2 ← R1

Square brackets

A memory word at an address

DR ← M[AR]


Bus Transfer: Sharing One Set of Wires

A CPU has many registers, and data must move between any pair of them. If we wired every register directly to every other one, the wiring would explode. With k registers there are k(k − 1) ordered source-destination pairs, each needing n wires.

For 8 registers of 16 bits: 8 × 7 = 56 paths, × 16 bits = 896 wires. Instead, we use a common bus: one set of n shared lines (16 wires here). At any moment one register puts its value on the bus and one or more registers load from it. We pay for this saving with a restriction: only one source can use the bus per clock cycle.

Bus Built with Multiplexers

One way to build the bus is with multiplexers (from Combinational Circuits: Adders, Multiplexers & Decoders). For k registers of n bits each:

  • we need n multiplexers, one per bus line (bit position),

  • each multiplexer is k × 1, choosing bit i from one of the k registers,

  • all multiplexers share the same log2k select lines, so they all pick the same register.

Example: 4 registers (A, B, C, D) of 4 bits each need 4 multiplexers of size 4 × 1 and 2 select lines S1 S0.

          MUX 3        MUX 2        MUX 1        MUX 0
        (4 x 1)      (4 x 1)      (4 x 1)      (4 x 1)
 in 0:   A3           A2           A1           A0
 in 1:   B3           B2           B1           B0
 in 2:   C3           C2           C1           C0
 in 3:   D3           D2           D1           D0
          |            |            |            |
 S1 S0 ---+------------+------------+------------+   (shared select lines)
          v            v            v            v
        bus 3        bus 2        bus 1        bus 0

  S1 S0 = 00 → A on bus,  01 → B,  10 → C,  11 → D

The transfer R2 ← C really takes two things in the same cycle: set S1 S0 = 10 (put C on the bus) and enable R2's load input (take it off the bus). RTL sometimes shows the bus explicitly: BUS ← C, R2 ← BUS.

Bus Built with Three-State Buffers

A three-state (tri-state) buffer has a normal input, an output and a control input. When the control is 1, the output equals the input (0 or 1). When the control is 0, the output goes into a high-impedance state: it behaves like a disconnected wire. So many buffer outputs can be tied to the same bus line, as long as only one is enabled at a time.

For k registers of n bits we need k × n buffers (one per bit per register) and a decoder with log2k inputs and k outputs, so exactly one register's buffers are enabled. An extra enable on the decoder lets us put nothing on the bus. This is how real shared buses are usually built, because adding a register only means adding buffers, not resizing multiplexers.

Worked Example: Sizing a Bus

Problem. A system has 16 registers of 32 bits each sharing a common bus. (a) How many multiplexers, of what size, and how many select lines? (b) If three-state buffers are used instead, how many buffers and what decoder?

Solution.

  • (a) One multiplexer per bit: 32 multiplexers, each 16 × 1. Select lines: log216 = 4, shared by all 32 multiplexers.

  • (b) One buffer per bit per register: 16 × 32 = 512 three-state buffers, controlled by a 4 × 16 decoder.


Memory Transfers

Memory is treated as an array of words, M, indexed by an address. The address always comes from the address register, and the data passes through the data register:

Read:   DR ← M[AR]        (word at address AR is copied into DR)
Write:  M[AR] ← R1        (R1 is stored at address AR)

A memory read is usually written as one micro-operation, even though in a real machine the memory may take several clock cycles to respond. How the processor waits for slow memory is handled by the bus protocol, covered in Bus Structure & Bus Arbitration.


The Four Types of Micro-operations

Type

What it does

Examples

Register transfer

Copies binary data from one register to another, unchanged

R2 ← R1, DR ← M[AR]

Arithmetic

Treats the bits as numbers

add, subtract, increment, decrement, negate

Logic

Works on each bit independently

AND, OR, XOR, complement

Shift

Moves the bits left or right

logical, circular, arithmetic shifts


Arithmetic Micro-operations

RTL

Description

R3 ← R1 + R2

Add R1 and R2, result in R3

R3 ← R1 − R2

Subtract R2 from R1

R2 ← R2'

Complement R2 (1's complement)

R2 ← R2' + 1

Negate R2 (2's complement)

R3 ← R1 + R2' + 1

R1 plus the 2's complement of R2, i.e. subtraction

R1 ← R1 + 1

Increment

R1 ← R1 − 1

Decrement

Notice that subtraction is not a separate kind of hardware. As we saw in Signed Numbers: Sign-Magnitude, 1's & 2's Complement, A − B = A + B' + 1. So one adder, plus a way to complement B and force a carry-in of 1, gives both addition and subtraction.

Multiplication and division are not basic micro-operations. They are carried out as a sequence of add/subtract and shift micro-operations (see Booth's Multiplication Algorithm and Division: Restoring & Non-Restoring), or by a dedicated multiplier circuit.

One Circuit for Eight Arithmetic Operations

Here is a neat trick. Take an n-bit parallel adder that computes D = A + Y + Cin. Feed its Y input through a 4 × 1 multiplexer per bit that chooses between B, B', all 0s and all 1s, using select lines S1 S0. Together with Cin = 0 or 1, this gives eight useful results:

  bit i of the circuit (repeated for every bit)

   B_i ----+----------> [0]
           +--[NOT]---> [1]   4x1        Y_i
   0 ----------------> [2]   MUX -----------+
   1 ----------------> [3]                  |
               S1 S0 --^                    v
   A_i -------------------------------> [ Full adder ] --> D_i
                         C_i (carry in) --^      |
                                                 +--> C_i+1 (carry to next bit)

S1

S0

Cin

Y

D = A + Y + Cin

Micro-operation

0

0

0

B

A + B

Add

0

0

1

B

A + B + 1

Add with carry

0

1

0

B'

A + B'

Subtract with borrow (A − B − 1)

0

1

1

B'

A + B' + 1

Subtract (A − B)

1

0

0

0

A

Transfer A

1

0

1

0

A + 1

Increment

1

1

0

all 1s

A − 1

Decrement

1

1

1

all 1s

A

Transfer A

Why is "A + all 1s" equal to A − 1? In n bits, all 1s is 2n − 1, which is −1 in 2's complement. Adding it and dropping the carry out gives A − 1. Adding one more (Cin = 1) brings us back to A.

Worked Example: Checking the Table

Let A = 0110 (6) and B = 0011 (3) in a 4-bit circuit. The output keeps 4 bits; any carry out of bit 3 is dropped.

S1 S0 Cin

Y

D (4 bits)

Decimal

Carry out

Check

0 0 0

0011

1001

9

0

6 + 3 = 9

0 0 1

0011

1010

10

0

6 + 3 + 1 = 10

0 1 0

1100

0010

2

1

6 − 3 − 1 = 2

0 1 1

1100

0011

3

1

6 − 3 = 3

1 0 0

0000

0110

6

0

A

1 0 1

0000

0111

7

0

6 + 1 = 7

1 1 0

1111

0101

5

1

6 − 1 = 5

1 1 1

1111

0110

6

1

A

Notice that in the subtract rows the carry out is 1. For unsigned subtraction A − B with this method, a carry out of 1 means A ≥ B (no borrow). This is the same "carry = 1 means no borrow" rule (the ARM convention) that we met in Binary Arithmetic & Overflow.


Logic Micro-operations

Logic micro-operations treat each bit separately, with no carries between bit positions. With two inputs per bit there are 24 = 16 possible logic functions (every possible truth table for two variables), including clear (all 0s), set (all 1s), AND, OR, XOR, NAND, NOR, XNOR, complement of A, transfer A, and so on. In practice, the four basic ones (AND, OR, XOR, complement) are enough to build the rest.

RTL

Operation

R1 ← R1 ∧ R2

AND

R1 ← R1 ∨ R2

OR

R1 ← R1 ⊕ R2

XOR

R1 ← R1'

Complement (NOT)

Why ∨ and not + for OR?

Inside a micro-operation, + always means arithmetic addition, so OR gets its own symbol ∨. In a control function (before the colon), however, + means OR. Both meanings can appear in one line:

P + Q: R1 ← R2 + R3, R4 ← R5 ∨ R6

Read it as: "if P OR Q is 1, then R1 gets the sum of R2 and R3, and at the same time R4 gets the bitwise OR of R5 and R6."

Practical Uses: Changing Selected Bits

The most common use of logic micro-operations is to change some bits of a register A while leaving the others alone. The second operand B acts as a pattern that says which bits to touch.

Operation

RTL

Effect on A where B has 1s

Where B has 0s

Selective set

A ← A ∨ B

Set to 1

Unchanged

Selective complement

A ← A ⊕ B

Flipped

Unchanged

Selective clear

A ← A ∧ B'

Cleared to 0

Unchanged

Mask

A ← A ∧ B

Unchanged

Cleared to 0

Two more operations are built from these:

  • Insert: put a new value into some bits of A. First mask those bits to 0, then OR in the new bits.

  • Clear (compare): A ← A ⊕ B gives all 0s exactly when A and B are equal. This is how equality comparison can be done with logic.

Worked Example

Let A = 1011 0011 and B = 1111 0000.

A                    = 1011 0011
B                    = 1111 0000
-----------------------------------
Selective set   A ∨ B  = 1111 0011    (upper 4 bits forced to 1)
Selective comp  A ⊕ B  = 0100 0011    (upper 4 bits flipped)
Selective clear A ∧ B' = 0000 0011    (upper 4 bits forced to 0)
Mask            A ∧ B  = 1011 0000    (lower 4 bits forced to 0)

Insert the pattern 0101 into the upper 4 bits of A = 1011 0011:

Step 1 (mask):   1011 0011 ∧ 0000 1111 = 0000 0011
Step 2 (insert): 0000 0011 ∨ 0101 0000 = 0101 0011

The lower 4 bits (0011) survived, and the upper 4 bits now hold 0101. This is exactly what a device driver does when it changes one field of a hardware control register.


Shift Micro-operations

Shifts move every bit one position left or right. The interesting question is: what enters the empty position, and what happens to the bit that falls off? The answer defines three kinds of shifts.

Type

RTL

Bit entering

Used for

Logical shift left

R ← shl R

0 at the right

Unsigned multiply by 2, bit packing

Logical shift right

R ← shr R

0 at the left

Unsigned divide by 2

Circular shift left (rotate)

R ← cil R

The bit that left at the left end

Rotations, serial transfer, checksums

Circular shift right (rotate)

R ← cir R

The bit that left at the right end

Same

Arithmetic shift left

R ← ashl R

0 at the right

Signed multiply by 2

Arithmetic shift right

R ← ashr R

Copy of the sign bit at the left

Signed divide by 2

Worked Example: All Six Shifts on One Register

Let R = 1011 0011 (8 bits). As an unsigned number it is 179; as a signed 2's complement number it is −77.

Shift

Result

Comment

shl

0110 0110

Leftmost 1 lost, 0 enters at right

shr

0101 1001

0 enters at left; 179 → 89 (floor of 179/2)

cil

0110 0111

Leftmost 1 wraps around to the right

cir

1101 1001

Rightmost 1 wraps around to the left

ashr

1101 1001

Sign bit (1) copied in; −77 → −39

ashl

0110 0110

Same bits as shl, but overflow: the sign changed

Two details here are classic exam traps.

Arithmetic Shift Right Rounds Down

−77 / 2 = −38.5, but ashr gives −39, not −38. Arithmetic shift right always rounds towards minus infinity (floor). For positive numbers this is the same as dropping the fraction; for negative odd numbers it is one less than truncation. (This is why C compilers add a small correction when they replace signed division by 2 with a shift.)

Overflow in Arithmetic Shift Left

Shifting left multiplies by 2, and the result may not fit. For a signed number, overflow happens when the sign bit changes during the shift, that is, when the two leftmost bits before the shift are different:

V = R(n−1) ⊕ R(n−2)       (V = 1 means overflow)

R (8-bit)

Value

R(7) ⊕ R(6)

ashl result

Result as signed

Correct?

0011 0101

53

0 ⊕ 0 = 0

0110 1010

106

Yes, 2 × 53

1101 0010

−46

1 ⊕ 1 = 0

1010 0100

−92

Yes, 2 × −46

0100 1101

77

0 ⊕ 1 = 1

1001 1010

−102

No: 154 does not fit in −128..127

1011 0011

−77

1 ⊕ 0 = 1

0110 0110

102

No: −154 does not fit

Some designs keep a separate overflow flip-flop V that captures this XOR on every ashl.


Putting It Together: Arithmetic Logic Shift Unit

Instead of a separate circuit for every micro-operation, processors combine them into one Arithmetic Logic Shift Unit (ALSU). A typical textbook design uses one stage per bit containing the arithmetic circuit, the logic circuit and shift connections, with a final multiplexer selecting which result to output:

  S3 S2 = 00 → arithmetic result (S1 S0 C_in choose which one, as in the table above)
  S3 S2 = 01 → logic result      (S1 S0 choose AND / OR / XOR / complement)
  S3 S2 = 10 → shift right       (bit i gets A(i+1))
  S3 S2 = 11 → shift left        (bit i gets A(i−1))

Five select inputs (S3, S2, S1, S0, Cin) choose among the operations. The control unit produces these select signals for each micro-operation. A full datapath built around such a unit is the topic of ALU & Datapath.


Worked Example: Tracing a Sequence of Micro-operations

Problem. Three 8-bit registers start with R1 = 5A16, R2 = 3C16, R3 = 0016. The following micro-operations run in successive clock cycles. Give each register's value after every step.

T1: R3 ← R1 + R2
T2: R1 ← R1 + R2' + 1
T3: R2 ← R2'
T4: R3 ← cir R3
T5: R1 ← R1 ∨ F0(hex)

Solution.

  • T1: 0101 1010 + 0011 1100 = 1001 0110, so R3 = 9616 (90 + 60 = 150).

  • T2: R1 − R2 = 90 − 60 = 30 = 0001 1110, so R1 = 1E16.

  • T3: complement of 0011 1100 is 1100 0011, so R2 = C316.

  • T4: rotate 1001 0110 right: the rightmost 0 moves to the left end, giving 0100 1011, so R3 = 4B16.

  • T5: 0001 1110 ∨ 1111 0000 = 1111 1110, so R1 = FE16.

After

R1

R2

R3

Start

5A

3C

00

T1

5A

3C

96

T2

1E

3C

96

T3

1E

C3

96

T4

1E

C3

4B

T5

FE

C3

4B


Common Mistakes

  • Thinking the source register is cleared. R2 ← R1 copies; R1 is unchanged.

  • Reading a comma as "then". R1 ← R2, R2 ← R1 is a swap in one clock, not two sequential copies.

  • Confusing the two meanings of +. Before the colon it is OR; after the colon it is addition. OR inside a micro-operation is written ∨.

  • Two sources on one bus in the same cycle. A single bus carries one value per clock. R1 ← R2, R3 ← R4 needs two separate paths and cannot be done on one bus in one cycle.

  • Mixing up logical and arithmetic shift right. shr always brings in 0; ashr copies the sign bit.

  • Forgetting overflow on ashl. If the two leftmost bits differ, doubling overflows.

  • Counting multiplexer select lines wrongly. The number of select lines depends on the number of registers (log2k), not on the number of bits.


GATE and Interview Questions

A bus connects 8 registers of 16 bits using multiplexers. How many multiplexers are needed, of what size, and how many select lines?

16 multiplexers (one per bit), each 8 × 1, sharing log28 = 3 select lines.

What does the statement x'T1: AR ← PC, PC ← PC + 1 mean?

When x = 0 and timing signal T1 = 1, at the next clock edge AR gets the current value of PC and PC is incremented, both in the same clock cycle. AR receives the old PC, because both registers sample their inputs before the edge.

How can an adder perform subtraction?

By computing A + B' + 1: complement every bit of B and set the carry-in to 1. This adds the 2's complement of B, which equals subtracting B.

Register A = 1100 1010. Which logic micro-operation and which B will clear the lower 4 bits of A and leave the rest unchanged?

Mask: A ← A ∧ B with B = 1111 0000, giving 1100 0000. (Equivalently, selective clear A ← A ∧ B' with B = 0000 1111.)

An 8-bit register holds 1001 1100. What is the result of ashr and of shr? What signed values are involved?

ashr gives 1100 1110 (−100 → −50). shr gives 0100 1110 (as unsigned, 156 → 78).

When does an arithmetic shift left cause overflow?

When the two most significant bits before the shift differ, i.e. V = R(n−1) ⊕ R(n−2) = 1. Then the sign bit would change, so the doubled value cannot be represented.

Why is a common bus preferred over dedicated paths between all registers?

Dedicated paths need k(k − 1) n-bit connections for k registers, which is far too many wires. A bus needs only n lines plus selection logic. The price is that only one transfer can use the bus per clock cycle.

Why are three-state buffers used to build buses?

A disabled three-state buffer goes into a high-impedance state, behaving like an open circuit. So many register outputs can share a wire, as long as a decoder enables exactly one at a time. Adding a register just adds buffers, without resizing a multiplexer.


Summary

  • A micro-operation is an elementary operation on register data in one clock pulse. RTL is the notation used to describe them.

  • P: R2 ← R1 means "if control function P is 1, load R2 from R1 at the clock edge". Commas separate operations done in the same clock pulse.

  • Registers share a common bus, built from n multiplexers of size k × 1 (log2k select lines) or from k × n three-state buffers plus a decoder. Only one source per cycle.

  • Memory transfers: DR ← M[AR] (read) and M[AR] ← R1 (write).

  • Four kinds of micro-operations: transfer, arithmetic, logic, shift.

  • An adder with a B/B'/0/1 multiplexer on one input gives add, subtract, increment, decrement and transfer from one circuit; A − B = A + B' + 1.

  • Logic micro-operations act bit by bit: selective set (OR), complement (XOR), clear (AND with B'), mask (AND), insert (mask then OR).

  • Shifts: logical (0 enters), circular (bit wraps around), arithmetic (sign preserved on right shift; overflow on left shift when the top two bits differ).

Every instruction a CPU runs, however complex, is carried out as a short, precisely timed sequence of these simple register transfers.