Digital logic

The big picture: bits, signals and two kinds of circuits

A [[bit|short for binary digit: the smallest piece of information, a 0 or a 1]] is the answer to one yes/no question, like a light switch. In a real circuit, 1 is usually a high voltage and 0 is a low voltage. A wire carries one bit, and a group of wires carries a group of bits.

Why only two values? Because it is very easy to tell "high" from "low" even when the signal is a bit noisy. Telling ten different voltage levels apart would be much harder and would make mistakes.

Digital circuits come in two families. A [[combinational circuit|a circuit whose output depends only on the inputs it has right now]] is like a calculator button: press 2 + 3 and you get 5, whatever you did before. A [[sequential circuit|a circuit whose output depends on the inputs and also on what happened before, which it keeps as a stored state]] is like a game score: it depends on the past, because it remembers.

The rest of the summary follows a ladder. First the numbers and codes that the bits represent, then gates and the algebra that describes them, then combinational blocks (adders, selectors), then memory (flip-flops, registers, counters), and finally the bridge to the analogue world.

Number systems and base conversion

We count in tens because we have ten fingers. The number 347 means 3 hundreds, 4 tens and 7 ones: each place is worth ten times the place to its right. This is called a [[positional system|a way of writing numbers where the value of a digit depends on the place where it stands]], and the number 10 is its base.

A computer has two states, so it uses base 2, called binary. The places are worth 1, 2, 4, 8, 16 and so on, doubling at each step to the left. Counting places always starts at 0 from the right.

To read a binary number, add the weights of the places that hold a 1. So 10011 is 16 + 2 + 1 = 19. The leftmost bit has the biggest weight and is called the MSB (most significant bit). The rightmost has the smallest and is the LSB (least significant bit). A group of 4 bits is a nibble and a group of 8 bits is a byte.

With n bits there are 2^n different patterns. Starting at 0, the biggest unsigned number is 2^n − 1, where every bit is 1. For a byte, that is 255. To store N different values you need the smallest n with 2^n ≥ N.

Converting decimal to binary

Divide by 2 again and again, write down each remainder, and read the remainders from the last to the first.

25 / 2 = 12 remainder 1   <- LSB
12 / 2 =  6 remainder 0
 6 / 2 =  3 remainder 0
 3 / 2 =  1 remainder 1
 1 / 2 =  0 remainder 1   <- MSB

read upwards: 11001  (16 + 8 + 1 = 25)

Octal and hexadecimal

Long strings of bits are hard for people to read. So we group them. Octal (base 8) uses digits 0 to 7, and one digit is exactly 3 bits. Hexadecimal (base 16) uses 0 to 9 and then A to F, which are worth 10 to 15. One hex digit is exactly 4 bits, so a byte is always two hex digits.

binary   1101 0110
          |    |
hex       D    6      -> D6

D6 = 13 x 16 + 6 = 214

binary 1010011 -> group by 3 from the right: 001 010 011 -> octal 123

Memory addresses are written in hex. If locations go from address 0000 to 0FFF, there are 0FFF + 1 = 1000 in hex, which is 16^3 = 4,096 locations. A range that starts at zero and ends at X holds X + 1 locations.

Fractions

After the binary point the weights halve: 1/2, 1/4, 1/8, 1/16. So 110.01 is 4 + 2 + 0.25 = 6.25. A decimal fraction can be written exactly in binary only if its denominator, in lowest terms, is a power of 2. That is why 0.375 (3/8) is exact, but 0.1 (1/10) repeats forever in binary and gets rounded.

Codes: BCD, Gray, ASCII and two's complement

A bit pattern means nothing until we agree on a code: a rule that says what each pattern stands for. The same 8 bits can be a number, a letter or a colour. Here are the codes every student should know.

BCD: one decimal digit at a time

[[BCD|binary-coded decimal: each decimal digit is written on its own with 4 bits]] (weights 8-4-2-1) is handy for clocks and calculators, because each digit goes straight to a display. The decimal number 83 is 1000 0011 in BCD, a digit at a time. Pure binary would be 101 0011.

BCD wastes space: the patterns 1010 to 1111 never appear. When an ordinary 4-bit adder adds two BCD digits and the result is above 9 (or it produces a carry), add 6 to skip the six unused patterns. For 7 + 6: the adder gives 1101, adding 0110 gives 1 0011, which reads as digits 1 and 3, that is 13.

Gray code: only one bit changes

In binary, going from 0111 to 1000 changes four bits at once. If a sensor reads while they change, it may catch a wrong value in the middle. In the Gray code each step changes exactly one bit, so a reading is never more than one step wrong.

To convert binary to Gray, keep the first bit and XOR each pair of neighbouring bits. Another way: Gray = n XOR (n shifted right by one place). For 1100: 1100 XOR 0110 = 1010. Gray code is used in position encoders and to label the Karnaugh map.

ASCII and parity

ASCII gives a number to letters, digits, punctuation and control characters. Standard ASCII has 7 bits, so 2^7 = 128 characters. The 8th bit of the byte was left free. It is often used as a parity bit: an extra bit chosen so that the total number of 1s is even (even parity) or odd (odd parity).

The letter E is 100 0101, which has three 1s. With even parity the parity bit is 1, and the byte sent is 1100 0101. If one bit flips on the way, the receiver counts an odd number of 1s and knows something is wrong. But parity cannot tell which bit changed, and two flips cancel each other.

Two's complement: negative numbers

In two's complement the leftmost bit has a negative weight. In 8 bits the weights are −128, 64, 32, 16, 8, 4, 2, 1. So 1011 0100 = −128 + 32 + 16 + 4 = −76. The leftmost bit is 1 for negative numbers, and there is a single zero.

• To negate a number: invert every bit, then add 1. For 5 = 0000 0101: invert to 1111 1010, add 1 to get 1111 1011, which is −5.
• Quick check: the negative of a magnitude m in n bits is 2^n − m. In 8 bits, 256 − 5 = 251 = 1111 1011.
• Range with n bits: from −2^(n−1) to 2^(n−1) − 1. In 8 bits, −128 to 127.
• To widen a number (4 bits to 8 bits) without changing its value, copy the sign bit into all the new left bits: 1010 (−6) becomes 1111 1010.

Logic gates and truth tables

A logic gate is a decision-maker with a very short rule. Think of a door guarded by two children: the AND door opens only if both have the key, the OR door opens if at least one has it.

A [[truth table|a list of every possible combination of the inputs, with the output for each one]] describes a gate completely. With n inputs there are 2^n rows, usually listed in binary counting order. Two inputs give 4 rows, three give 8, four give 16.

• NOT flips its single input: 0 becomes 1 and 1 becomes 0. It is written A'.
• AND (written A·B) is 1 only when all inputs are 1. It is a product.
• OR (written A + B) is 1 when at least one input is 1. It is a sum.
• XOR is 1 when the inputs are different. It is the sum of two bits without the carry: A'·B + A·B'.
• NAND, NOR, XNOR are AND, OR and XOR followed by a NOT. So NAND is 0 only in the single row where every input is 1, and an n-input NAND is 1 in the other 2^n − 1 rows.

To recognise a gate from its table, look at the odd row out. AND and NOR have a single 1. NAND and OR have a single 0.

Reading a circuit and a timing diagram

To find the table of a circuit, name every wire and write what it carries, step by step. In this circuit, X = A·B, W = C' and Y = X + W.

A ----+
      AND ---- X ----+
B ----+              OR ---- Y
                     |
C ---- NOT ---- W ---+

A timing diagram shows signals over time, one column per instant. Without delays, you apply the truth table to each column. For NAND the output is 0 exactly at the instants where all inputs are 1.

Universal gates

Any Boolean function can be made from AND, OR and NOT. A set of gates that can make those three is universal. NAND alone is universal, and so is NOR alone. If you tie both inputs of a NAND together, A·A = A, so it computes A' and works as a NOT. NAND followed by that NOT makes AND. And OR is built with De Morgan's law, seen in the next section.

NOT A    = NAND(A, A)
A AND B  = NOT( NAND(A, B) )
A OR B   = NAND( NOT A, NOT B )

XOR with 4 NANDs:  M = NAND(A, B)
                   XOR = NAND( NAND(A, M), NAND(B, M) )

Boolean algebra and De Morgan's laws

Boolean algebra is the arithmetic of 0 and 1. It lets us write a circuit as a formula and then make the formula shorter, which means a cheaper circuit. Each gate becomes a symbol: the apostrophe is NOT, the dot is AND and the plus is OR.

The order of priority is the same as in school maths: NOT first, then AND (like multiplication), then OR (like addition). So A + B·C means A + (B·C).

Notice that the second distributive law, A + B·C = (A + B)·(A + C), does not exist in ordinary arithmetic. In Boolean algebra both directions work.

De Morgan's laws

To negate an expression, negate each variable and swap AND with OR. In symbols, (A·B)' = A' + B' and (A + B)' = A'·B'. Picture a rule: "you cannot have both cake and ice cream" means "no cake, or no ice cream".

With several levels, work from the outside in, and let a double negation cancel. For example, (A + B'·C)' = A'·(B'·C)' = A'·(B + C').

Useful simplifications

• X·Y + X·Y' = X: two terms that differ in one variable merge, and that variable disappears.
• A + A'·B = A + B: if A is 1 the result is already 1, if A is 0 only B is left. Only the literal A' is removed, not the whole term.
• Consensus: A·B + A'·C + B·C = A·B + A'·C. The last term is redundant.
• Because X + X = X, the same term can be used in more than one grouping.

Canonical forms: minterms and maxterms

A [[minterm|a product that contains every variable of the function, plain or negated, and is 1 in exactly one row of the truth table]] has the index of its row. Read the row in binary with the first variable as the most significant bit. A variable is plain if its bit is 1 and negated if its bit is 0. For three variables, row 5 (101) is minterm A·B'·C.

The canonical sum of products adds the minterms of the rows where the function is 1, written Σm(...). A maxterm is a sum that is 0 in exactly one row. The canonical product of sums, ΠM(...), multiplies the maxterms of the rows where the function is 0, and in a maxterm the bits are used the other way round: a 0 gives the plain variable and a 1 gives the negated one.

Each row is a minterm or a maxterm, never both. So the number of minterms plus the number of maxterms is always 2^n. A function with few 0s has a short product of sums.

Karnaugh maps

Simplifying with algebra needs good eyes and luck. The Karnaugh map makes it a picture. It is a truth table redrawn as a grid, in such a way that two cells that touch differ in exactly one variable. And we already know that X·Y + X·Y' = X, so two touching 1s can merge into a shorter term.

To make touching cells differ in one variable, the labels of rows and columns follow the Gray code: 00, 01, 11, 10, and not the binary order. The map also wraps around: the first and the last column touch, and so do the first and the last row. A group may cross the edge, and the four corners are neighbours.

        BC
       00  01  11  10
A=0 |   1   0   0   1
A=1 |   1   1   0   1

The recipe is short. Cover every 1 with the biggest groups you can, using as few groups as possible. A cell may belong to several groups.

• A group is a rectangle with 1, 2, 4, 8 or 16 cells: always a power of 2. A region of 6 cells needs two groups, which may overlap.
• Each time a group doubles, one variable disappears. A group of 2^k cells in a map of n variables gives a term with n − k literals. In a 4-variable map: 2 cells give 3 literals, 4 cells give 2, 8 cells give 1.
• To write the term, keep only the variables that do not change inside the group. If the variable is 1 in the group, write it plain; if it is 0, write it negated.
• Add the terms of all groups: that is the minimal sum of products.

In the map above, the four cells of column 00 and column 10 (the wrapped columns) form a group with C = 0: the term is C'. The pair A=1, B=0 (cells 100 and 101) gives A·B'. So F = C' + A·B'.

      CD
     00  01  11  10
AB=00 | 1   0   0   1
AB=01 | 0   1   1   0
AB=11 | 0   1   1   0
AB=10 | 1   0   0   1

corners (00,00)(00,10)(10,00)(10,10)  -> B'·D'
centre block                          -> B·D
F = B'·D' + B·D   (XNOR of B and D)

Product of sums, don't-cares and prime implicants

• Product of sums: group the 0s instead. Each group gives a sum term in which the variable is plain when it is 0 and negated when it is 1. It is the same as simplifying F' and applying De Morgan.
• Don't-care (X): an input combination that never happens or whose output does not matter, for example the codes 1010 to 1111 in a BCD circuit. You may count an X as 1 to make a group bigger, or ignore it. Only the real 1s must be covered. Example: 1s at minterms 1, 3, 7 and an X at 5 give C, while without the X you would need two pairs.
• Prime implicant: a group that cannot be enlarged. It is essential when it covers a 1 that no other prime implicant covers. Take all the essential ones first, then add the fewest others to cover what is left. This is exactly what the Quine-McCluskey method does by procedure.
• Chessboard pattern: when the 1s never touch (like XOR of three variables, odd parity), nothing merges and the sum of products cannot shrink.

Arithmetic circuits: adders and subtractors

Adding in binary is just like adding on paper in decimal, but a carry appears as soon as a column reaches 2. The rules: 0+0 = 0, 0+1 = 1, 1+1 = 10 (write 0, carry 1) and 1+1+1 = 11 (write 1, carry 1).

  carries:  1 1 1
            0 1 1 0   (6)
          + 0 1 1 1   (7)
          ---------
            1 1 0 1   (13)

The half adder

Adding two bits gives a sum bit and a carry. The sum is 1 for 01 and 10, so it is XOR. The carry is 1 only for 11, so it is AND. This circuit is the half adder: S = A XOR B and C = A·B. It is "half" because it has no input for the carry that comes from the right.

The full adder

A column in the middle of a number has three bits to add: A, B and the carry-in Cin. The full adder takes all three. Its sum is the parity of the three bits, S = A XOR B XOR Cin. Its carry-out is 1 when at least two inputs are 1 (a majority): Cout = A·B + A·Cin + B·Cin. It can be built from two half adders and an OR.

The ripple-carry adder

To add n-bit numbers, chain n full adders: the carry-out of stage i goes into the carry-in of stage i + 1. This is the ripple-carry adder. It is the simplest design, but a carry may have to walk through every stage, like a bucket passed along a line of people. In the worst case (1111...1 + 1) the delay is proportional to n. With 3 ns per stage, 16 stages need 16 × 3 = 48 ns. Faster designs, such as the carry-lookahead adder, predict the carries to cut this time.

Subtraction with the same adder

In two's complement, A − B = A + B' + 1. In the circuit, one XOR gate on each bit of B is controlled by a SUB wire (XOR with 1 inverts, XOR with 0 passes). The same SUB wire goes to the first carry-in, which supplies the +1. With SUB = 0 the circuit adds, with SUB = 1 it subtracts.

6 - 2 with 4 bits:  A = 0110
                    B' = 1101   (2 = 0010 inverted)
                    Cin = 1
                    -----------
                    sum = 0100  carry-out = 1
6 - 2 = 4 and the carry-out is 1: no borrow

Carry-out and overflow are different things

• Unsigned subtraction: the carry-out works as the inverse of the borrow. Carry-out 1 means no borrow was needed (A ≥ B). Carry-out 0 means a borrow happened (A < B). This is how a processor compares two unsigned numbers: it subtracts and looks at the carry flag.
• Signed overflow: the result does not fit in n bits. It happens when two operands of the same sign give a result of the opposite sign. It is the same as the carry into the sign bit being different from the carry out of it. Example in 4 bits: 0111 + 0001 = 1000, that is 7 + 1 = −8.
• The carry-out alone only tells about overflow for unsigned numbers.

Multiplexers, demultiplexers, encoders and decoders

These are the "traffic controllers" of a circuit. They choose which signal goes where. All of them are combinational.

Multiplexer (mux): many in, one out

A multiplexer has several data inputs, one output and some select inputs. The select inputs form a binary number that says which data input is connected to the output. It is like a TV remote that picks one channel out of many.

To choose among 2^n data inputs, n select lines are needed: 1 for a 2:1 mux, 2 for 4:1, 3 for 8:1, 4 for 16:1. A processor uses muxes to pick which register feeds the ALU.

I0 --+
I1 --|  4:1
I2 --|  MUX ---- Y
I3 --+   |  |
        S1 S0

S1 S0 = 1 0  ->  Y = I2

Big muxes are built as a tree of small ones. A 16:1 mux with 4:1 parts: four muxes in the first level take the data and the two low select bits, and one mux in the second level picks among their outputs with the two high select bits. That is 4 + 1 = 5 components.

A mux can also compute a function. A mux with n select lines implements any function of n + 1 variables. Connect n of the variables to the selects. For each select value, the output can only be 0, 1, the remaining variable or its complement, and that is what you wire to the data input. Example: F = A XOR B with a 2:1 mux whose select is A: I0 = B (when A = 0, F = B) and I1 = B' (when A = 1, F = B').

Demultiplexer (demux): one in, many out

The opposite of a mux. One data input is sent to the output chosen by the select lines, and all the other outputs stay at 0. It is a decoder where the data plays the role of the enable.

Decoder: a code becomes one line

A binary decoder with n inputs has 2^n outputs and exactly one of them is active: the one whose number equals the input code. Each output is one minterm of the inputs. It selects a memory location, a device, or the operation of an instruction.

Decoders with an enable input can be expanded. For a 3-to-8 decoder from two 2-to-4 ones, the two low bits go to both blocks, and the high bit A2 goes straight to the enable of one block and, through an inverter, to the enable of the other. Memory chips are selected from the upper address bits in the same way.

Encoder: one line becomes a code

The encoder does the opposite of a decoder: 2^n inputs, of which one is active, become the n-bit number of that input. A keypad uses one to turn the pressed key into a code. A plain encoder is just OR gates: each output bit is the OR of the inputs whose index has that bit at 1.

Trouble starts when two inputs are active. Suppose I1 and I2 are both active: the OR gates mix the codes 01 and 10 and the output is 11, which points at a third input. A priority encoder fixes this: it answers with the code of the active input of highest priority and ignores the others. With I3 I2 I1 I0 = 1010 and priority to the highest index, the output is 11. It decides which interrupt is served first.

Latches and flip-flops

Until now every circuit forgot everything the moment its inputs changed. To remember a bit we need feedback: an output wired back to an input. Two gates that listen to each other can hold a value, like two kids who keep repeating the same word to each other.

The RS latch

A [[latch|a basic memory cell that holds one bit and reacts to its inputs while it is enabled]] made of two cross-coupled gates has two outputs, Q and Q', which should always be opposites. It has a Set input (make Q = 1) and a Reset input (make Q = 0).

In the NOR latch an input at 1 forces its gate to 0. Asking for set and reset together makes both outputs 0, which breaks the rule that Q' is the opposite of Q. And if both inputs return to 0 at once, the final state depends on which gate is faster, so it is unpredictable. In the NAND latch the level that commands is 0, so its inputs are active low: it is the same behaviour with the levels turned upside down.

Level or edge?

A D latch has one data input D and an enable input, usually driven by the clock. While the enable is 1 the latch is transparent: Q follows D. When the enable goes to 0, Q keeps the last value. It is level sensitive.

A flip-flop is edge sensitive: it looks at D only at the instant the clock rises (or falls), and keeps Q until the next edge. A D flip-flop can be made with two D latches in series with opposite enables (master-slave). The waveform shows the difference:

t:          0 1 2 3 4 5 6 7
clock:      0 1 1 0 0 1 1 0
D:          1 1 0 0 1 0 1 1
D latch:    0 1 0 0 0 0 1 1   <- follows D while clock = 1
flip-flop:  0 1 1 1 1 0 0 0   <- looks at D only at clock rises

Look at instant 6: the clock is 1 and D becomes 1, so the latch follows, but the flip-flop does not move because there is no new rising edge.

The flip-flop types

• D flip-flop: at the active edge Q takes the value of D, otherwise it holds. It is the basic cell of registers.
• JK flip-flop: J = K = 0 holds, J = 1 K = 0 sets, J = 0 K = 1 resets and J = K = 1 toggles (Q flips). Unlike the RS, it has no forbidden combination. Toggling divides the clock frequency by 2, which is the basis of counters.
• To follow a JK over time, apply the mode to the previous Q at each active edge. Between edges Q stands still.

Timing: setup, hold and the fastest clock

A flip-flop reads D correctly only if D is stable in a small window around the clock edge: the setup time (before the edge) and the hold time (after it). Breaking this window can leave the output in an unstable in-between state called metastability.

Between two flip-flops on the same clock, the data must leave the first (propagation delay), cross the logic and arrive at the second early enough (setup time). So the clock period must be at least the sum of the three, and the maximum frequency is 1 divided by that period (frequency is how many clock pulses fit in one second; 1 MHz is a million per second). For 6 ns + 10 ns + 4 ns = 20 ns the maximum frequency is 1 / 20 ns = 50 MHz.

Registers and counters

One flip-flop stores one bit. A bunch of them side by side stores a word, like a row of mailboxes that each hold one letter.

Registers

An n-bit register is n D flip-flops sharing the same clock, so all n bits are captured together. To make it keep its word even though the clock keeps ticking, a multiplexer in front of each flip-flop feeds the bit back to itself when the load signal is 0. Registers hold operands, results and addresses inside a processor.

Shift registers

In a shift register the output of each flip-flop goes to the input of its neighbour. At each clock pulse all bits move one place, a new bit comes in at one end and one leaves at the other. Loading n bits through the single serial input takes n pulses. In parallel transfer there is one wire per bit and one pulse loads the whole word.

shift right, serial input = 0
start   Q3 Q2 Q1 Q0 = 1 1 0 0   (12)
pulse 1               0 1 1 0   (6)
pulse 2               0 0 1 1   (3)

Counters

A counter is a register that goes through a sequence of states, one per clock pulse. An n-bit binary up counter has up to 2^n states and then starts again; that number of states is its modulus. A 4-bit counter has modulus 16: it goes 0, 1, ... 15, then 0 again. The program counter of a processor is a register like this, adding 1 at each instruction.

The least significant bit flips at every pulse, the next one every 2 pulses, then every 4. So bit k has the clock frequency divided by 2^(k+1), and an n-bit counter divides the frequency by 2^n at its last bit.

Asynchronous and synchronous

In an asynchronous (ripple) counter the output of each flip-flop is the clock of the next. They do not change together, and while the change ripples along the counter shows wrong in-between values. The settling time is the number of stages times the delay of one flip-flop. With 3 flip-flops of 5 ns the pulses must be at least 15 ns apart, so 1 / 15 ns ≈ 66.7 MHz at most. In a synchronous counter every flip-flop shares the clock and the delays do not add up.

Other moduli and the Johnson counter

To count fewer than 2^n states, detect the first unwanted state and use it to clear the counter. To count 0 to 5 (modulus 6), detect 0110 and clear. With an asynchronous clear, the state 0110 shows up only for an instant, as a short glitch, and the modulus is the detected value. This glitch is a drawback; synchronous designs prefer to detect the last valid state and clear on the next edge.

A Johnson (twisted-ring) counter is a shift register where the complement of the last flip-flop goes back to the first. It first fills with 1s, then empties, so n flip-flops give 2n states, and only one bit changes between neighbouring states.

3 flip-flops Q2 Q1 Q0, shifting right, Q0' enters Q2:
0 0 0 -> 1 0 0 -> 1 1 0 -> 1 1 1 -> 0 1 1 -> 0 0 1 -> 0 0 0
6 states = 2 x 3

Analogue to digital conversion

The real world is analogue: temperature, sound and light change smoothly. A digital circuit only understands bits. A D/A converter (DAC) turns a code into a voltage. An A/D converter (ADC) turns a voltage into a code. Your phone uses an ADC for every sound the microphone hears.

D/A converter and resolution

An N-bit DAC can output 2^N levels with equal steps. The resolution is the size of one step, the change of the output when the code goes up by 1 (the LSB). If the biggest code, 2^N − 1, gives the full-scale voltage, the step is that voltage divided by 2^N − 1. The output for any code is the step times the value of the code.

4-bit DAC, 0 V for 0000 and 3.0 V for 1111
step = 3.0 V / 15 = 0.2 V
code 0101 = 5  ->  5 x 0.2 V = 1.0 V

Three ways to build an ADC

All of them compare the input voltage with the output of an internal DAC or with fixed reference levels. A comparator is a circuit that tells whether one voltage is above another.

• Digital ramp: a counter goes up one step per clock until the internal DAC reaches the input. It is the simplest, but the time depends on the input, and the worst case is 2^N − 1 clock cycles. It doubles with each added bit. With 10 bits and a 1 MHz clock that is 1,023 cycles, about 1.023 ms.
• Successive approximation (SAR): a binary search. Try the most significant bit at 1, keep it only if the DAC output does not exceed the input, then go to the next bit. It always takes exactly N cycles, whatever the input.
• Flash: a resistor divider makes every reference level and one comparator per level tests the input at the same time. A priority encoder turns the result into a code. It is practically instant, but the cost doubles with each bit: 2^N − 1 comparators.

SAR, 4 bits, DAC step 0.5 V, input 4.7 V
try 1000 = 4.0 V  <= 4.7  keep   ->  1000
try 1100 = 6.0 V  >  4.7  drop   ->  1000
try 1010 = 5.0 V  >  4.7  drop   ->  1000
try 1001 = 4.5 V  <= 4.7  keep   ->  1001
result 1001 = 4.5 V, quantisation error 0.2 V

The leftover difference between the true input and the value of the final code is the quantisation error. It is always smaller than one step.

Putting it all together

Look at how the ideas stack, from the bottom to the top. Each level is made from the one before it.

bits and codes (binary, hex, two's complement, BCD, Gray)
   |
gates (AND, OR, NOT, NAND, NOR, XOR)
   |
Boolean algebra + Karnaugh maps  (make the circuit small)
   |
combinational blocks: adders, mux, decoder, encoder
   |
feedback -> latch -> flip-flop
   |
registers, shift registers, counters
   |
processor (ALU + registers + muxes + decoder)
   |
A/D and D/A converters connect it to the real world

A small processor is exactly this ladder: an adder with XOR gates becomes an ALU, flip-flops become registers and a program counter, muxes choose which register feeds the ALU, and a decoder turns the instruction into control signals. If you want to see it built from a single NAND gate, the mini-projects of this repository do that.

Mistakes that appear again and again

Two videos show this whole path, and then you can try it yourself in a simulator.