Chapter 1: Binary Numbers and Arithmetic

Source files used: ELEC205 Week 1 slides (digital systems intro, number systems: slides 9-49), Week 2 slides (slides 2-22); textbook Chapter 1 as support. No worked examples are included.

1. Big Picture

Chapter 1 is about how a digital system writes numbers using only 0 and 1.

The real world is analog. A digital system samples it, stores the samples as bits, processes the bits, and converts back. Everything after this chapter assumes you can read, convert, and do arithmetic on those bit strings.

$$\boxed{\text{Represent a number in binary, convert between bases, and add/subtract/multiply it correctly (signed or unsigned).}}$$

New ideas in this chapter:

• positional number systems (binary, octal, hex) and base conversion,
• binary addition and subtraction with carries and borrows,
• three ways to represent negative numbers (signed-magnitude, 1’s complement, 2’s complement),
• overflow in 2’s complement,
• shift-and-add multiplication,
• BCD (binary-coded decimal).

Erzin’s course roadmap: combinational systems (no memory, output depends only on current input) come first, sequential systems (with memory, flip-flops) come later.

---

2. Core Ideas

2.1 Digital Abstraction

A digital signal is modeled with two discrete values: 0 or 1 (LOW/HIGH, FALSE/TRUE). The hardware is still analog; we only pretend it is not.

• Combinational circuit: gates only (AND, OR, NOT). Output depends only on current inputs.
• Sequential circuit: gates plus flip-flops. Output also depends on the past input sequence.
• Flip-flop: stores one bit; changes only at times set by a clock.

---

2.2 Positional Number Systems

A number in base (radix) $r$ is a weighted sum of its digits. The leftmost digit is the MSB, the rightmost is the LSB.

• Binary: digits 0-1, base 2.
• Octal: digits 0-7, one octal digit = 3 bits.
• Hexadecimal: digits 0-9, A-F, one hex digit = 4 bits. Two hex digits = one 8-bit byte.

Octal and hex are just shorthand for long binary strings.

---

2.3 Unsigned Arithmetic

Binary addition and subtraction work column by column, exactly like decimal, using a carry (addition) or borrow (subtraction) between columns.

Use subtraction to compare: if $X-Y$ produces a borrow out of the MSB, then $X<Y$.

---

2.4 Representing Negative Numbers

For an $n$-bit word $A=a_{n-1}a_{n-2}\dots a_1a_0$, the MSB carries the sign in all three systems (0 = positive, 1 = negative).

• Signed-magnitude: MSB is the sign, the rest is the magnitude. Two zeros ($+0$, $-0$).
• 1’s complement: negate by flipping every bit. Two zeros.
• 2’s complement: negate by flipping every bit and adding 1. One zero, one extra negative number.

Taking a complement is harder than flipping a sign bit, but in complement systems addition and subtraction become the same hardware operation. That is why 2’s complement is the standard.

---

2.5 The 2’s Complement “Clock”

With $n=4$, the 16 codes sit on a wheel: $0000=0$, $0111=+7$, $1000=-8$, $1111=-1$. Adding moves clockwise, subtracting moves counter-clockwise. Since $N+(-N)=2^n=10000_2$, the dropped 5th bit is why $-1+1=0$ works.

Subtracting $n$ is the same as adding $16-n$, and $16-n$ is exactly the 4-bit 2’s complement of $n$.

---

2.6 Overflow

Overflow happens when the true result is outside the representable range. In 2’s complement, $+5+6=+11$ gives $1011=-5$ in 4 bits: wrong sign, overflow.

Overflow can only happen when the two addends have the same sign.

---

2.7 BCD (Binary-Coded Decimal)

Each decimal digit 0-9 is stored as its own 4-bit code (0000-1001). The codes 1010-1111 are unused. One 8-bit byte holds 0-99.

BCD is not the same as converting the whole number to binary. $(937)_{10}$ in BCD is $1001\ 0011\ 0111$.

---

3. Main Governing Equations and Formulas

3.1 Base-$r$ to Decimal

$$D=\sum_{i=-n}^{p-1}d_i\,r^i$$

where:

• $r$: base (radix), integer $r>1$,
• $p$: number of digits left of the radix point,
• $n$: number of digits right of the radix point.

Use to convert any base to decimal. Example from the slides: $436.5_8=4\cdot8^2+3\cdot8^1+6\cdot8^0+5\cdot8^{-1}=286.625_{10}$.

---

3.2 Decimal to Base-$r$ (Integer Part)

Divide repeatedly by $r$ and keep the remainders:

$$179\div2=89\ \text{r}1\ (\text{LSB}),\ \dots,\ 1\div2=0\ \text{r}1\ (\text{MSB})\ \Rightarrow\ 179_{10}=10110011_2$$

The first remainder is the LSB. Read the remainders bottom-up.

For the fractional part, the textbook method is to multiply the fraction repeatedly by $r$ and keep the integer parts (first integer part = first digit after the point).

---

3.3 Binary to Octal / Hex

Group bits starting from the radix point: 3 bits per octal digit, 4 bits per hex digit. Pad with zeros on the outside ends (left of the integer part, right of the fraction).

$$100011001110_2=4316_8=8\text{CE}_{16}$$ $$10.1011001011_2=010.101\,100\,101\,100_2=2.5454_8=0010.1011\,0010\,1100_2=2.\text{B2C}_{16}$$

Use for fast conversion; never go through decimal.

---

3.4 One-Bit Addition and Subtraction

For a column with inputs $X$, $Y$ and incoming carry/borrow:

$$S=X\oplus Y\oplus C_{in},\qquad C_{out}=XY+C_{in}(X\oplus Y)$$ $$D=X\oplus Y\oplus B_{in},\qquad B_{out}=X'Y+X'B_{in}+YB_{in}$$

Sum and difference bits are identical; only the carry and borrow logic differ. The slides give these as an 8-row table (Cin/bin, X, Y, Cout, S, Bout, D). These become the full adder in Chapter 4.

---

3.5 Signed-Magnitude Range

$$-(2^{n-1}-1)\ \le\ A\ \le\ +(2^{n-1}-1)$$

Two representations of zero. Example (8-bit): $01010101=+85$, $11010101=-85$.

Addition rule: if signs match, add magnitudes and keep the sign; otherwise subtract the smaller magnitude from the larger and take the sign of the larger.

---

3.6 Diminished Radix (1’s) Complement

$$(r-1)\text{'s complement of }N=(r^n-1)-N$$

For binary:

$$-N=(2^n-1)-N=\text{bitwise NOT of }N$$

Range: $-(2^{n-1}-1)$ to $+(2^{n-1}-1)$, two zeros. Example ($n=4$): $-0101=1111-0101=1010$.

---

3.7 Radix (2’s) Complement

$$-N=r^n-N$$

For binary:

$$-N=2^n-N=\big[(2^n-1)-N\big]+1=\text{flip all bits, then add 1}$$

Example: $17_{10}=00010001_2\Rightarrow-17=11101110+1=11101111_2$.

Negating 0 gives $2^n$, which is $(n+1)$ bits; dropping the extra bit gives 0 again, so there is only one zero.

---

3.8 2’s Complement Value and Range

$$A=-2^{n-1}a_{n-1}+2^{n-2}a_{n-2}+\dots+2^1a_1+2^0a_0$$ $$-2^{n-1}\ \le\ A\ \le\ 2^{n-1}-1$$

Read a 2’s complement number like an unsigned one, except the MSB weight is $-2^{n-1}$. A number is negative if and only if its MSB is 1. For 4 bits the range is $[-8,7]$.

---

3.9 Sign Extension

To widen an $n$-bit 2’s complement number to $n+1$ (or more) bits, copy the MSB to the left:

$$0110\to00110,\qquad 1010\to11010$$

Use whenever operands of different widths are added, and for partial products in signed multiplication.

---

3.10 2’s Complement Addition and Subtraction

$$X-Y=X+(-Y)=X+Y'+1$$

Add all $n$ bits, including the sign bits, and discard the carry out of the MSB. Example: $+4-3$: $0100+1100=1\,0001\Rightarrow0001=+1$.

---

3.11 Overflow Rule (Sign Test)

$$\text{Overflow}\iff\text{both addends have the same sign AND the sum has the other sign}$$

Use whenever an addition result in 2’s complement looks suspicious. Adding numbers of opposite sign can never overflow. Chapter 4 gives the hardware version ($V=C_n\oplus C_{n-1}$).

---

3.12 Binary Multiplication

Unsigned: shift and add. Each 1 in the multiplier adds a shifted copy of the multiplicand.

2’s complement (Erzin’s method): shift and 2’s complement add, using sign-extended partial products, except for the last step. The multiplier’s MSB has weight $-2^{n-1}$, so its partial product is subtracted (add its 2’s complement) instead of added.

Example from the slides: $(-5)\times(-3)=1011\times1101=00001111=+15$.

---

3.13 Binary Division

Unsigned: shift and subtract. There is no other easy way.

Signed: handle the signs separately, divide the magnitudes with shift-and-subtract, then fix the sign.

---

3.14 BCD Addition

Add the 4-bit digits as binary. For each digit:

$$\text{if digit sum}>9\ \text{or a carry is produced}\ \Rightarrow\ \text{add }0110\ (6)\ \text{and pass the carry to the next digit}$$

Example: $448+489$: middle and low digits give $1101$ and $10001$, both corrected by $+0110$, final result $1001\ 0011\ 0111=937$.

Adding 6 skips the six unused codes 1010-1111.

---

4. Problem-Solving Workflow

4.1 Base Conversion

1. Binary, octal, hex among themselves: group bits (3 or 4) from the radix point.
2. Any base to decimal: weighted sum (Section 3.1).
3. Decimal to base $r$: repeated division for the integer part, repeated multiplication for the fraction.
4. Decimal to octal/hex: convert to binary first if it is easier, then group.

4.2 Signed Arithmetic in $n$ Bits

1. Check both operands fit in the range for $n$ bits.
2. Convert negatives to 2’s complement (flip and add 1).
3. For subtraction, negate the subtrahend and add.
4. Add all bits; drop the carry out of the MSB.
5. Check overflow with the sign test.
6. Convert back: if MSB is 1, negate to get the magnitude, or use the $-2^{n-1}$ weight.

4.3 Reading a Bit Pattern

1. Identify the system (unsigned, signed-magnitude, 1’s, 2’s, BCD).
2. Apply that system’s rule. The same pattern means different numbers in each system (Section 6.2).

---

5. Decision Rules / Decision Trees

5.1 Which Negative-Number System?

Want the simplest add/subtract hardware and a single zero? → 2’s complement

Question says “signed-magnitude”? → sign bit + magnitude, two zeros, symmetric range

Question says “1’s complement”? → bitwise NOT, two zeros, symmetric range

5.2 Is There Overflow?

Addends have different signs? → no overflow possible

Addends have the same sign AND the sum’s sign differs from theirs? → overflow

Unsigned subtraction $X-Y$ gives a borrow out of the MSB? → $X<Y$

5.3 BCD Digit Correction

Digit sum $\le 9$ and no carry? → keep it

Digit sum $>9$ or carry out of the digit? → add 0110, propagate carry

---

6. Important Tables / Correlations Needed

6.1 Range Summary ($n$ bits)

System	Range	Zeros	Negation
Unsigned	$0$ to $2^n-1$	one	n/a
Signed-magnitude	$-(2^{n-1}-1)$ to $2^{n-1}-1$	two	flip MSB
1’s complement	$-(2^{n-1}-1)$ to $2^{n-1}-1$	two	flip all bits
2’s complement	$-2^{n-1}$ to $2^{n-1}-1$	one	flip all bits, add 1

6.2 3-Bit Numbers in Every System

Bits	Unsigned	Signed-magnitude	1’s complement	2’s complement
000	0	0	0	0
001	1	1	1	1
010	2	2	2	2
011	3	3	3	3
100	4	-0	-3	-4
101	5	-1	-2	-3
110	6	-2	-1	-2
111	7	-3	-0	-1

6.3 Bit Grouping

Base	Bits per digit	Digits
8 (octal)	3	0-7
16 (hex)	4	0-9, A-F
BCD	4 per decimal digit	0000-1001 only

---

7. Key Takeaways

• A base-$r$ number is $\sum d_i r^i$; octal and hex are 3-bit and 4-bit groupings of binary.
• Decimal to binary: repeated division by 2; first remainder is the LSB.
• 2’s complement negation: flip all bits, add 1.
• 2’s complement range is $[-2^{n-1},\,2^{n-1}-1]$; the MSB has weight $-2^{n-1}$.
• Signed-magnitude and 1’s complement both have two zeros; 2’s complement has one.
• Subtraction is $X+Y'+1$; discard the final carry.
• Overflow only when same-sign addends give an opposite-sign sum.
• Sign-extend by copying the MSB.
• Signed multiplication: add sign-extended partial products, but subtract the last one.
• BCD addition: add 0110 when a digit sum exceeds 9 or carries.