Inside a computer there are only two voltages, so there are only two symbols: 0 and 1. Everything else — your name, a photograph, a song, this sentence — is a pattern of those two symbols.

This unit teaches you to move between the number systems people use and the one machines use, to do arithmetic in binary, and then to describe and simplify the switching circuits that carry out that arithmetic.

It is the most mechanical unit in the course: almost every mark is earned by applying a procedure correctly, so practise until the procedures are automatic.

2.1 Decimal, Binary, Octal and Hexadecimal number systems and conversion

A number system is a way of writing numbers using a fixed set of symbols. The number of distinct symbols is the base (or radix) r. All four systems in the syllabus are positional: the value of a digit depends on where it stands.

In hexadecimal A = 10, B = 11, C = 12, D = 13, E = 14, F = 15.

Any base → decimal: positional expansion

Multiply each digit by the base raised to its position weight and add.

Fractions use negative powers: (11011.101)_2 = 16+8+2+1 + \frac12 + \frac18 = 27.625.

Decimal → any base: repeated division and multiplication

For the integer part, divide repeatedly by the base and read the remainders bottom to top. For the fraction part, multiply repeatedly by the base and read the carried integers top to bottom.

Binary ↔ octal ↔ hexadecimal: grouping

Because 8 = 2^3 and 16 = 2^4, each octal digit is exactly 3 bits and each hex digit exactly 4 bits. Group from the binary point outwards, padding with zeros at the ends.

2.2 Binary addition and subtraction

Binary arithmetic follows exactly the same column rules as decimal, with only two digits available.

   1111     <- carries
    1011    (11)
  + 1101    (13)
  -------
   11000    (24)

   11010    (26)
  - 01011   (11)
  --------
   01111    (15)

      1101        (13)
    x  101        ( 5)
    --------
      1101
     0000
    1101
    --------
    1000001       (65)

          1010        quotient = 1010 (10)
      ----------
 101 ) 110110
       101
       ---
        0111
         101
         ---
          0101 0
           101
           ---
             100    remainder = 100 (4)

2.3 One's and Two's complement methods of binary subtraction

Hardware has no subtractor. A computer subtracts by adding the complement, so the same adder circuit does both operations. This is why complements matter.

For example, with 4 bits: N = 0110 → 1's complement = 1001 → 2's complement = 1010.

Subtraction by 1's complement

To compute A - B:

1. Take the 1's complement of B (the subtrahend).
2. Add it to A.
3. If a carry comes out of the leftmost column, the answer is positive: add that carry back into the least significant bit (end-around carry). The result is the answer.
4. If there is no carry out, the answer is negative: take the 1's complement of the sum and put a minus sign in front.

     1010
   + 1001
   -------
   1 0011      carry out = 1  -> positive
       +1      end-around carry
   -------
     0100      = 4

     0110
   + 0101
   -------
     1011      no carry out -> negative

Subtraction by 2's complement

1. Take the 2's complement of B.
2. Add it to A.
3. If there is a carry out, discard it; the result is positive.
4. If there is no carry out, the result is negative: take the 2's complement of the sum and put a minus sign in front.

     1010
   + 1010
   -------
   1 0100      discard the carry out
   -------
     0100      = +4

     00101101      (45)
   + 10110010      (2's complement of 78)
   -----------
     11011111      no carry out -> negative

2.4 Introduction to Boolean algebra

Boolean algebra is the algebra of two-valued logic, published by the English mathematician George Boole in An Investigation of the Laws of Thought (1854).

In 1938 Claude Shannon showed that it describes switching circuits exactly — a switch is either on or off — and that insight is the foundation of all digital design.

Here + means OR (read "A or B"), \cdot means AND (read "A and B"), and the bar means NOT. The 0 and 1 are not quantities; they are logic levels — false/true, off/on, low/high voltage.

2.5 Boolean values, truth table, Boolean expression and Boolean function

• A Boolean value (logic value) is either 0 (false, low) or 1 (true, high).
• A Boolean variable is a symbol, such as A, that can hold only a Boolean value. A literal is a variable or its complement: A and \bar{A} are two literals.
• A Boolean expression is variables combined by AND, OR and NOT, for example \bar{A}B + AC.
• A Boolean function assigns an output value to every combination of its input variables, written F(A,B,C) = \bar{A}B + AC.
• A truth table lists the output for every input combination. With n input variables it has 2^{n} rows.

For F(A,B,C) = \bar{A}B + AC:

2.6 Logic gates

The NOT gate (inverter) has one input: \bar{0} = 1 and \bar{1} = 0.

In words: AND gives 1 only when all inputs are 1. OR gives 1 when at least one input is 1. XOR gives 1 when the inputs are different — it is the "odd number of 1s" detector.

XNOR gives 1 when the inputs are the same, so it is an equality detector. NAND and NOR are the inverses of AND and OR.

(a) 7400 quad NAND gate IC

(b) 7474 flip-flop IC

(c) 7447 display decoder IC

(d) Breadboard for circuits

Drawing a circuit from an expression

Work from the innermost operation outwards: complements first, then AND terms, then the final OR.

Half adder and full adder

A half adder adds two single bits and produces a sum and a carry. Its two outputs are exactly XOR and AND of the inputs.

A half adder cannot be used for the second and later columns of an addition, because it has nowhere to take the carry in. A full adder adds three bits — A, B and a carry-in C_{in} — and is built from two half adders plus an OR gate.

Note the second distributive law, A + BC = (A+B)(A+C). It has no counterpart in ordinary algebra and is a favourite examination question.

Simplification using the laws

Simplification using Karnaugh maps

A Karnaugh map (K-map) is a truth table redrawn as a grid, with the rows and columns labelled in Gray code order (00, 01, 11, 10) so that any two neighbouring cells differ in exactly one variable. Then:

1. Write a 1 in every cell whose minterm is in the function.
2. Ring rectangular groups of 1s whose size is a power of two — 1, 2, 4, 8 — making each group as large as possible. Groups may overlap, and they wrap around the edges of the map.
3. For each group write the product of the variables that stay constant inside it; drop the variables that change.
4. OR the group terms together.

2.8 Verification of the laws of Boolean algebra using truth tables

To verify a law, build one column for the left-hand side and one for the right-hand side, fill in every row, and show the two columns are identical.

De Morgan's first theorem: \overline{A+B} = \bar{A}\cdot\bar{B}

Columns 4 and 7 agree in every row, so the theorem is proved.

De Morgan's second theorem: \overline{A\cdot B} = \bar{A} + \bar{B}

Distributive law: A + BC = (A+B)(A+C)

Absorption law: A + AB = A, and redundancy: A + \bar{A}B = A + B

Column 4 equals column 1 (absorption); column 6 equals column 7 (redundancy).

(a) A logic IC in a dual in-line package holds several gates

(b) 4-bit binary addition and two's complement subtraction

Practice questions

Group A — Multiple choice (1 mark each)

1. (1011)_2 in decimal is [1]a9b11c13d15
2. The hexadecimal equivalent of (11011110)_2 is [1]aDEbEDc9EdBE
3. The 2's complement of (0101)_2 is [1]a1010b1011c0110d1101
4. Which gate gives output 1 only when its two inputs are different? [1]aANDbNORcXORdXNOR
5. According to De Morgan's theorem, \overline{A\cdot B} equals [1]a\bar{A}\cdot\bar{B}b\bar{A}+\bar{B}cA+Bd\overline{A+B}
6. A + \bar{A}B simplifies to [1]aAbBcA+BdAB
7. Which pair of gates is called universal? [1]aAND and ORbNAND and NORcXOR and XNORdNOT and AND
8. The carry output of a half adder is [1]aA \oplus BbA + BcA\cdot Bd\overline{A\cdot B}

Group B — Short answer (5 marks each)

1. Convert(a) (347)_{10} to binary, octal and hexadecimal, and(b) (10110111)_2 to decimal, octal and hexadecimal. [5]
2. Perform the following binary operations:(a) 10110 + 1101,(b) 110100 - 10111,(c) 1011 \times 110,(d) 100101 \div 111. [5]
3. Subtract (0111)_2 from (1101)_2 using(a) the 1's complement method and(b) the 2's complement method. Show every step. [5]
4. State and verify De Morgan's two theorems using truth tables. [5]
5. Simplify F = \bar{A}\bar{B}C + \bar{A}BC + A\bar{B}C + ABC using the laws of Boolean algebra, and draw the logic circuit of the simplified expression. [5]
6. Draw the logic symbol and write the truth table and Boolean function of the NAND, NOR, XOR and XNOR gates. [5]

Group C — Long answer (8 marks each)

1. (a) Convert (2C5)_{16} to decimal, binary and octal. [3](b) Using the 2's complement method in 8 bits, evaluate 58 - 91 and verify your answer in decimal. [5]
2. (a) Define a logic gate. Draw the symbol and truth table of all seven basic gates. [4](b) Draw the logic circuit of a full adder using two half adders and one OR gate, write its truth table, and derive the expressions for the sum and the carry. [4]
3. Simplify F(A,B,C,D) = \sum m(0,1,2,3,8,9,10,11,13,15) using a Karnaugh map. Show the map, the groupings and the final simplified expression, and draw the resulting logic circuit. [8]

Group D — Long answer (10 marks each), with full model answers

1. What is a number system? Explain the binary, octal, decimal and hexadecimal systems and show how numbers are converted from one to another. [10]
2. What is a logic gate? Explain the seven basic gates with symbols and truth tables, and show why NAND is called a universal gate. [10]
3. What is an adder? Explain the half adder and the full adder with truth tables, expressions and circuits. [10]

Model answer D1: number systems and conversion (10 marks)

Introduction. A number system is a method of writing numbers with a fixed set of digits in which the value of a digit depends on its position and on the base (radix) of the system.

People count in decimal, but a computer is made of switches that are either off or on, so it stores every number, letter and picture in binary. Octal and hexadecimal are short forms of binary that humans can read more easily.

Conversions.

1. Any base to decimal (positional expansion). Multiply each digit by its place value and add. (10011100)_2 = 128+16+8+4 = 156. For a fraction, the places to the right of the point are \tfrac12, \tfrac14, \tfrac18: (1101.101)_2 = 8+4+1+0.5+0.125 = 13.625.
2. Decimal to binary (repeated division by 2). Divide 156 by 2 again and again and write the remainders: 0, 0, 1, 1, 1, 0, 0, 1 (for the quotients 78, 39, 19, 9, 4, 2, 1, 0). Read them from bottom to top: (10011100)_2.
3. Decimal fraction to binary (repeated multiplication by 2). For 0.625: 0.625\times2=1.25 (digit 1), 0.25\times2=0.5 (digit 0), 0.5\times2=1.0 (digit 1). Read the integer parts downwards: (0.101)_2.
4. Binary to octal. Group the bits in threes from the binary point: 010 011 100 becomes 2, 3, 4, so (234)_8.
5. Binary to hexadecimal. Group the bits in fours: 1001 1100 becomes 9 and C, so (9C)_{16}.
6. Octal or hexadecimal to binary. Replace each digit by its three-bit or four-bit code: (2C5)_{16} = 0010\ 1100\ 0101.
7. Decimal to octal or hexadecimal. Divide repeatedly by 8 or 16, or convert to binary first and then group the bits.

Uses. Binary suits electronic circuits; hexadecimal is used for colour codes such as

FF0000 (red), memory addresses and the MAC address of a network card; octal is used for

Linux file permissions such as 755.

Conclusion. All the systems represent the same quantity in different ways, and positional expansion and repeated division are the two tools that convert between them.

Model answer D2: logic gates and the universal gate (10 marks)

Introduction. A logic gate is an electronic circuit that takes one or more binary inputs and produces one binary output according to a fixed logical rule.

Gates are the building blocks of every processor, memory and adder; one chip such as the 7400 in Figure 2.L contains four of them. The rule of a gate is described by its truth table.

Explanation. AND, OR and NOT are the three basic gates; NAND and NOR are the AND and OR followed by a NOT, and XOR and XNOR are the "difference" and "equality" detectors.

A NOT gate has one input and a bubble at its output, and a bubble on any gate symbol means inversion.

Universal gates. NAND and NOR are called universal because any other gate, and so any digital circuit, can be built from only one of them. For NAND:

1. NOT: join both inputs, \overline{A\cdot A} = \bar{A}.
2. AND: follow a NAND by a NAND used as a NOT, \overline{\overline{A\cdot B}} = A\cdot B.
3. OR: invert both inputs and then NAND them, \overline{\bar{A}\cdot\bar{B}} = A+B by De Morgan's theorem.

Because a factory needs to make only one kind of gate, NAND-only designs are cheaper and smaller; the flash memory of a pen drive is built from NAND cells.

Conclusion. Seven gates cover every logical rule, and the two universal gates show that even these seven can be reduced to a single repeated gate.

Model answer D3: half adder and full adder (10 marks)

Introduction. An adder is a combinational circuit that adds binary digits. The arithmetic unit of every CPU is a chain of adders, and subtraction is done by adding the 2's complement. There are two kinds: the half adder and the full adder.

Half adder. It adds two bits A and B and gives a sum S and a carry C. It cannot accept a carry from an earlier position, hence the name "half".

From the table, S = A\oplus B and C = A\cdot B. The circuit is one XOR gate and one AND gate fed by the same two inputs.

Full adder. It adds three bits: A, B and the carry-in C_{in} from the position on the right, and gives S and a carry-out C_{out}.

The expressions are S = A\oplus B\oplus C_{in} and C_{out} = AB + C_{in}(A\oplus B).

Construction: the first half adder adds A and B giving S_1 = A\oplus B and C_1 = AB; the second half adder adds S_1 and C_{in} giving S and C_2 = C_{in}\cdot S_1; an OR gate joins the two carries, C_{out} = C_1 + C_2.

Check with 1+1+1: S_1 = 0, C_1 = 1, then S = 1, C_2 = 0, C_{out} = 1, so the answer is (11)_2 = 3 ✓

Use. A 4-bit ripple-carry adder is four full adders in a row, the carry-out of each feeding the carry-in of the next, and it adds 1011 + 0110 = 10001 (11 + 6 = 17).

Conclusion. The half adder is the simplest adding circuit, and joining two of them with an OR gate gives the full adder from which multi-bit adders are made.