Transistors

Semiconductors

Semiconductor: Sillicon, Germanium. stable at room temperature, allowing a small current.

Impurities: n-type: group 15 (Phosphrous), p-type: group 13 (Boron).

Doping: adding impurities to semiconductors.

n-type semiconductor has extra electron, while p-type semiconductor has holes.

When bringing p-type and n-type together, the electrons will mix with the holes, creating a depletion layer (diffusion), and corresponding electric field (drift). These two currents reach equilibrium.

Forward bias: (the arrow represents direction of electron)

+ | p-type | n-type | -
       < diffusion
       drift >
       < bias

Narrows the depletion layer and increase diffusion rate, short circuit.

Reverse bias: the contrary of forward bias, open circuit.

Transistors

MOSFET: Metal Oxide Semiconductor Field Effect Transistor

n-channel MOSFET

               G
           +-------+
           | Metal |
           +-------+
      S    | Oxide |     D
+--+-----+-+-------+-+-----+--+
|  |  N  |     P     |  N  |  |
|  +-----+           +-----+  |
+-----------------------------+ < substrate

V_BS: Substrate bias

  • S: Source
  • D: Drain
  • G: Gate

At rest, at least one reverse bias is created. Therefore, no current.

If a voltage is applied on the gate, a layer of negative charge (in the reverse-bias region of P-type) will be attracted to the surface of p-type material, creating a n-channel.

V_DS V_GS V_DS
0 0 0
0 1 0
1 0 0
1 1 0

p-channel MOSFET

Same as n-channel, except that N and P are exchanged, and a logic zero voltage is applied on the gate.

Gates

Not connecting the output to high voltage is not the same as connecting it to low voltage.

Data: V_cc=5V, GND=0V, switching time 120picosecond, switching interval 10ns.

NAND is the most common logic gate.

               V_cc
                 |
         +----------------+
         | Positive logic |
Input -> +----------------+ -> Output
         | Negative logic |
         +----------------+
                 |
                GND

Positive logic connects IFF Input leads to high Output.

Negative logic connects IFF Input leads to low Output.

Should be disjoint and cover every case.

Circuit Creation

Minterm and Maxterm

  • minterm an AND expression with every input present in true or complemented form.

m_x = AB(~C)D: Every output is low, except when A=1, B=1, C=0, D=1. (x is the row in truth table.)

  • maxterm an OR expression with every input present in true or complemented form.

M_x = A+B+~C+D Every output is high, except when A=0, B=0, C=1, D=0.

Combining the Terms

  • SOM: Sum-of-Minterms (union of high outputs)
  • POM: Product-of-Maxterms (intersection of high outputs)

Reducing Circuits

Gate cost

  • G: number of gates.
  • GN: number of gates, with NOT gates included.

Karnaugh maps

Grid of minterms (maxterms), arranged so that adjancent minterms (maxterms) differ by a single literal IFF.

Note: the 2d grid wraps around. ie, the left most column is adjancent to the right most column.

Don’t care values: can be either 0 or 1.

Two’s Complement

  • One’s complement: ~x. (x + ~x = -1)
  • Two’s complement: ~x + 1.

Range:

  • Unsigned: 0 ~ 2^n - 1
  • Signed: -2^(n - 1) ~ 2^(n - 1) - 1

Flip-flops

Latches

  • ~S~R latch: Two interconnected NAND gates.
  • SR latch: Two interconnected NOR gates.

S: Set, R: Reset, ~S~R: Keep, SR: Forbidden.

Clock signals

  • Latency of transistors: setup and hold time.
  • Setup time for clock signal.

Clocked latches

  • Clocked SR latch: two nand gates connected with ~S~R latch, with ~S = ~(SC) and ~R = ~(RC).

Only allows S and R signals to affect the state when C is high.

  • D latch: Clocked SR latch, with S = D, C = ~D.

Prevents forbidden space, but is transparent: any change to D when C is high is visible immediately.

  • SR master-slave flip-flop: two clocked SR latch, with a not gate on the clock of the second one.

A flip-flop is a latched circuit whose output is triggered with the edge of a clock pulse.

  • Edge-triggered D flip-flop: connect D latch to the input of a clocked SR latch, with a not gate on the clock of the clocked SR latch.

Negative-edge triggered changes value when clock goes down.

  • T flip-flop: toggles the value with T goes high.

  • JK flip-flop: ~J~K maintain, (~J)K reset, J(~K) set, JK toggle.

Timing

Input should NOT be changing at the same time as the active edge.

  • Setup time: Input should be stable before the active edge.
  • Hold time: Input should be stable after the active edge.

Time period between two active edges cannot be shorter than the longest propogation delay and setup time.

Reset

  • Synchronous reset: the output is resetted only on the active edge.
  • Asynchronous reset: the output is resetted immediately.

Sequential Circuit


Input -> Combinational Circuit -> Output
         ^                   |
         +- Storage Units <--+

Gate delay

(Propogation Delay) The length of time for an input change to result in output change.

Feedback circuits

  • and and or will lock.
  • nand and nor will oscillate.

ALU

ALU flags

  • C: Carry
  • Z: Zero
  • N: Negative
  • V: Overflow

Multiplication

  • Booth’s Algorithm

If [i:i-1] = “01”, the multiplicand is added at position i.

If [i:i-1] = “10”, the multiplicand is subtracted from position i.

def booth(a: Integer, b: Integer) -> Integer:
    assert len(a) == len(b)
    N = len(a) * 2
    a = a.extend(N)
    b = b.extend(N)
    print(a, b)
    cur = Integer(N)
    for i in range(N - 1, 0, -1):
        if b.content[i] == 0 and b.content[i - 1] == 1:
            nxt = a.sll(i)
        elif b.content[i] == 1 and b.content[i - 1] == 0:
            nxt = (-a).sll(i)
        else:
            continue
        print(f" {cur}\n+{nxt}\n={cur + nxt} ({i})\n")
        cur += nxt
    return cur

Memory

Read

Address:
                |< -RC------------------------------------------- >|
                | Address Valid                                    |
                |< OHA >|       |                                  |
                |< -AA-------- >|                                  |< OHA >|
Data Out:               |       |                                  |       |
Prev Data Valid         |       | Data Valid                               | ...
  • RC: Read Cycle Time, minimum time needed between two read cycles.
  • AA: Address Access Time, time needed for address to be stable before read.
  • OHA: Output Hold Time, time output data is held after change of address.

Write

Address:
                |< -WC-------------------------------------------- >|
                | Address Valid                                     |
Read/nWrite:    |< SA >| < -WP----------------------------- >|< HA >|
0                      | 1                                   | 0
Data In:                          |< -SD------------------- >|< -HD---- >|
                                  | Data Valid                           |
  • WC: Write Cycle Time.
  • SA: Address Setup Time, time needed for address to be stable before enabling write.
  • HA: Address Hold Time, time needed for address to be stable after enabling write.
  • WP: Write Pulse Width
  • SD: Data Setup Time (to Write End), time for data-in value to be setup at destination.
  • HD: Data Hold Time (from Write End), time for data-in value should stay unchanged after write signal changes.

General

  • Address need time to setup
  • Be conservative about timing

Endianess

Big endian:

|X     |X+1   |X+2   |X+3   |
| Byte | Byte | Byte | Byte |
^ MSB                       ^ LSB

Little endian:

|X     |X+1   |X+2   |X+3   |
|31  24|23  16|15   8|7    0|
| Byte | Byte | Byte | Byte |
^ LSB                       ^ MSB

Application Memory View

+-------------+
| Reserved    |
+-------------+
| .text       |
+-------------+
| .data       |
+-------------+
| Heap        |
+-------------+
| Unallocated |
+-------------+
| Stack       |
+-------------+
| OS          |
+-------------+

MIPS Instruction Types

R-type

Machine code:

|31    26|25 21|20 16|15 11|10    6|5     0|
| 6      | 5   | 5   | 5   | 5     | 6     | =32
| opcode | rs  | rt  | rd  | shmat | funct |

I-type

Machine code:

|31    26|25 21|20 16|15  0|
| 6      | 5   | 5   | 16  | =32
| opcode | rs  | rt  | IMM |

J-Type

Machine code:

|31    26|25             0|
| 6      | 26             | =32
| opcode | pseudo-address |

Actual address:

|31     28|27             2| 1         0|
| 4       | 26             | 2          | =32
| next PC | pseudo-address | word align |

MIPS Instructions

Arithmetic instructions

  • I-type: IMM is sign extended.
  • div?: lo = $rs / $rt, hi = $rs % $rt.
  • mult?: hi:lo = $s * $t.
  • (add|sub)?u: same as (add|sub)?, but does not trap on overflow.
  • (mult|div)u behaves differently from (mult|div).

Logical instructions

  • I-type: IMM is zero extended.

Shift instructions

  • sll* operations will always sign extend into a 64-bit register, then truncates the value into 32 bits.

Jump instructions

  • j: according to slides, pc = (pc & 0xF0000000) | (IMM << 2), which is different from the specification.

  • The range of j is 256 MBytes.

Branch instructions

  • The offset is i = (label - (next PC)) >> 2. This is different from the slides.

  • The range b* is +/- 128 KBytes.

Comparison instructions

References

mips-isa