[TOC]

## Chapter 4

### Combinational circuit

Has logic gates with no feedback paths or memory elements.

### Design procedure

1. From the specifications of the circuit, determine the required number of inputs and outputs and assign a symbol to each.
2. Derive the truth table that defines the required relationship between inputs and outputs.
3. Obtain the simplified Boolean functions for each output as a function of the input variables.(e.g. K-map)
4. Draw the logic diagram and verify the correctness of the design (manually or by simulation).

### Half adder

Two input$(x,y)$, two output$(S,C)$.

$S=x\oplus y$
$C=xy$

### Full adder

Three input$(x,y,z)$, two output $(S,C)$.
Can be implement by two half adder.

$S=x\oplus y\oplus z$
$C=xy+xz+yz$

### Binary adder

Can be constructed with full adders connected in cascade.

### Carry Propagation

The total propagation time is equal to the propagation delay of a typical gate, times the number of gate levels in the circuit.
The longest propagation delay time in an adder is the time it takes **the carry** to propagate through the full adders.

### Carry look-ahead

There are two binary number $A,B$ added by a binary adder which is implemented by adders with carry look-ahead.

let
$P_i=A_i+B_i$
$G_i=A_iB_i$

then
$C_0=\text{input carry}$
$C_1=G_0+P_0C_0$
$C_2=G_1+P_1C_1=G_1+P_1(G_0+P_0C_0)=G_1+P_1G_0+P_1P_0C_0$
...

Each function can be implemented with one two-level gate, therefore this circuit can add in less time than the one without carrying look-ahead.

### Binary subtractor

Basically use the same circuit as adder.

**The input carry $C_0$ must be equal to $1$ when subtraction is performed.**

The operation thus becomes $A$, plus the 2's complement of $B$ (1's complement +1).

### Overflow

An overflow condition ca be detected by observing the **carry into** the sign bit position and the **carry out** of the sign bit position.
If the two carries are **not equal**, an overflow has occurred.

### BCD adder

$C=K+Z_8Z_4+Z_8Z_2$
When $C=1$, it is necessary to add 0110 to the binary sum and provide an output carry for the next stage(the decimal carry).

### Binary multiplier

Multiplication of binary numbers is performed in the same way as multiplication of decimal numbers(i.e. long multiplication).

Mainly use Adder and AND gate.

### Magnitude comparator

A magnitude comparator is a combinational circuit that compares two numbers $A$ and $B$ and determines their relative magnitudes.

### Decoders

Convert binary information from $n$ input to a maximum of $2^n$ unique output lines.
If the $n$-bit coded information has unused combinations, **the decoder may have fewer than $2^n$ outputs**.

### Encoders

An encoder is a digital circuit that performs the inverse operation of a decoder.
The basic encoder has the limitation that **only one input can be active at any given time**.

#### Priority encoder

A priority encoder is an encoder circuit that include the priority function, and handles the possibility that inputs might be in contention.

### Multiplexer

A multiplexer is a combinational circuit that selects binary information from one of many input lines and directs it to a single output line.
Normally, there are **$2^n$ input lines and $n$ selection lines** whose bit combinations determine which input is selected.

#### Boolean function implementation with multiplexers

A Boolean function of $n$ variables can be implemented with a multiplexer that has $n-1$ selection inputs.

## Chapter 5

### Sequential circuit

A sequential circuit is specified by a time sequence of inputs, outputs, and internal states.

### Latches vs Flip-flops

Storage elements that operate **with signal levels** (rather than signal transitions) are referred to as **latches**; those controlled by a **clock transition** are **flip-flops**.

### Latches

#### SR latch

S for set, R for reset.

**NOR gate version**

Setting both inputs to 1 is forbidden.

**NAND gate version**

Setting both inputs to 0 is forbidden.

#### D latch (Transparent latch)

To ensure inputs S and R are never equal to 1 at the same time.
D for Data, En for enable.


### Flip-flops

The key to the proper operation of a flip-flop is to trigger it only during a signal transition.

#### Edge-triggered D flip-flop

Use two D latches.


#### JK flip-flop

J for set, K for reset, when both are enabled, the output is complemented.


#### T flip-flop

T for toggle, when T is enabled, the output is complemented, otherwise remains unchange.

### Characteristic tables

A characteristic table defines the logical properties of a flip-flop by describing its operation in tabular form.

e.g.
| D | Q(t+1) |
|:--- |:--------- |
| 0 | 0 (Reset) |
| 1 | 1 (Set) |

### Characteristic equations

The logical properties of a flip-flop, as described in the characteristic table, can be expressed algebraically with a characteristic equation.

e.g.
$Q(t+1)=D$

### Direct inputs

Some flip-flops have asynchronous inputs that are used to force the flip-flop to a particular state independently of the clock.
The input that sets the flip-flop to 1 is called **preset** or **direct set**.
The input that clears the flip-flop to 0 is called **clear** or **direct reset**.

### State equations

The behavior of a clocked sequential circuit can be described algebraically by means of state equations.

e.g.
$A(t+1)=A(t)x(t)+B(t)x(t)$
$B(t+1)=A'(t)x(t)$

or in the more compact form
$A(t+1)=Ax+Bx$
$B(t+1)=A'x$

### State table (Transition table)

The time sequence of inputs, outputs, and flip-flop states can be enumerated in a state table.

e.g.

| Present State(A/B) | Input(x) | Next State(A/B) | Output(y) |
|:------------------:|:--------:|:---------------:|:---------:|
| 0/0 | 0 | 0/0 | 0 |
| 0/0 | 1 | 0/1 | 0 |
| 0/1 | 0 | 0/0 | 1 |
| 0/1 | 1 | 1/1 | 0 |
| 1/0 | 0 | 0/0 | 1 |
| 1/0 | 1 | 1/0 | 0 |
| 1/1 | 0 | 0/0 | 1 |
| 1/1 | 1 | 1/0 | 0 |

### State diagram

The information available in a state table can be represented graphically in the form of a state diagram.

e.g.

### Flip-flop input equations

The interconnections among the gates form a combinational circuit and may be specified algebraically with Boolean expressions.

e.g.
$D_Q=x+y$

while $D_Q$ is the input $D$ of a D type flip-flop whose output is labeled with the symbol $Q$.

### Mealy and Moore models of finite state machines

They differ only in the way the output is generated.
The two models of a sequential circuit are commonly referred to as a **finite state machine**, abbreviated **FSM**.