Hardware
Logic gates and circuits, main memory, and the devices attached to a computer.
AND| A | B | Output |
|---|---|---|
| 0 | 0 | |
| 0 | 1 | |
| 1 | 0 | |
| 1 | 1 |
//Everything IGCSE taught you still applies
AS asks the same four questions about logic that IGCSE does — expression to circuit, circuit to truth table, circuit to expression, table to expression — and the full method for each is written out on the IGCSE Boolean Logic page. Two things are new here, and both are about making a circuit SMALLER: Boolean algebra, and Karnaugh maps. A question that says 'simplify' will not accept the long sum-of-products answer, however correct it is.
NEW NOTATION AT AS LEVEL
A.B means A AND B (sometimes written AB, with nothing between)
A+B means A OR B
A' means NOT A (also written as a bar over the A)
So Q = A.B + A'.C is Q = (A AND B) OR ((NOT A) AND C)
The dot binds tighter than the plus, exactly like multiply and add in
maths — which is why the method is called SUM (+) OF PRODUCTS (.).//Boolean identities worth memorising
These are the moves you are allowed to make when simplifying. Most of them are obvious once you read them aloud with 1 as true and 0 as false — 'A or true is always true' — but they have to be instant, because a simplification question is marked on reaching the shortest form rather than on how long it took.
A + 0 = A A . 1 = A
A + 1 = 1 A . 0 = 0
A + A = A A . A = A
A + A' = 1 A . A' = 0
(A')' = A
Absorption: A + A.B = A A . (A + B) = A
Distribution: A.(B + C) = A.B + A.C
A + B.C = (A + B).(A + C)
De Morgan: (A . B)' = A' + B'
(A + B)' = A' . B'//Simplifying, step by step
Write one line per step and name the rule you used on the right. Examiners give method marks for the steps, so a wrong final answer with correct working still scores — and a right answer with no working can lose marks on a 'show that' question. The move to look for first is always a common factor.
SIMPLIFY Q = A.B + A.B' + A'.B
Q = A.(B + B') + A'.B take A out of the first two [distribution]
= A.1 + A'.B B + B' = 1
= A + A'.B A.1 = A
= (A + A').(A + B) A + B.C = (A+B).(A+C)
= 1.(A + B) A + A' = 1
= A + B 1.X = X
Q = A + B three gates and two inverters become ONE gate.
CHECK IT with a truth table — this is worth doing every time, because a
slip in the algebra is invisible otherwise:
A B | A.B A.B' A'.B | sum | A + B
----+------------------+-----+-------
0 0 | 0 0 0 | 0 | 0
0 1 | 0 0 1 | 1 | 1
1 0 | 0 1 0 | 1 | 1
1 1 | 1 0 0 | 1 | 1//Karnaugh maps — the method
A Karnaugh map does the same job as the algebra, but by eye. It is a truth table folded into a grid whose neighbouring cells differ in exactly one variable, so a group of adjacent 1s is exactly a term with a variable missing. The order along each edge is 00, 01, 11, 10 — NOT binary counting order — and getting that order wrong is the single commonest mistake, because the map still looks plausible.
METHOD
1. Draw the grid. Label the edges 00, 01, 11, 10 (one bit changes at a time).
2. Copy the 1s from the truth table into the matching cells.
3. Group the 1s into rectangles of 1, 2, 4, 8 - as FEW and as LARGE as
possible. Groups may overlap. Groups wrap round the edges.
4. Read each group: keep the variables that are the SAME across the whole
group, drop the ones that change. A variable that is 0 gets a NOT.
5. OR the groups together.
WORKED Q = 1 for A.B.C' , A.B.C , A'.B.C , A.B'.C
C=0 C=1
+-----+-----+
A'B' | 0 | 0 |
A'B | 0 | 1 |
AB | 1 | 1 |
AB' | 0 | 1 |
+-----+-----+
group 1: the AB row, both cells -> A and B are the same, C changes
-> term is A.B
group 2: the C=1 column, middle
two cells (A'B and AB) -> B and C are the same, A changes
-> term is B.C
group 3: the C=1 column, AB and
AB' cells -> A and C are the same, B changes
-> term is A.C
Q = A.B + B.C + A.C
Every 1 must be inside at least one group. A 1 that is on its own is a
group of one and keeps all three variables.//Why the groups must be powers of two
A group of two cells means one variable changed and made no difference, so that variable drops out. A group of four means two variables dropped out, eight means three. A group of three has no such meaning — there is no term that covers exactly three cells — which is why groups of 1, 2, 4 and 8 are the only ones allowed, and why the exam mark scheme can say 'three terms' with confidence.
group size variables dropped term length (from 3 variables)
1 0 3 letters A.B.C
2 1 2 letters A.B
4 2 1 letter A
8 3 the whole map is 1, so Q = 1
Bigger groups are always better: they produce shorter terms.
That is why step 3 says as FEW and as LARGE as possible, in that order.//SRAM vs DRAM
SRAM uses flip-flops, is fast, needs no refreshing, but is expensive and bulky — so it is used for cache. DRAM uses capacitors that leak, so it must be refreshed thousands of times a second; it is slower but cheap and dense — so it is used for main memory.
CHECK YOURSELF
1.Apply De Morgan's law: what is (A · B)' equal to?
2.Why is SRAM used for cache rather than DRAM?
3.In a Karnaugh map, why are the columns ordered 00, 01, 11, 10?