Data Types, Number Systems and Boolean Algebra
Two's complement, floating point, bitwise operations, character sets, and Boolean algebra including De Morgan's laws and Karnaugh maps.
Number representation
Two's complement
The standard representation for signed integers. The most significant bit has a negative place value.
For 8 bits: -128, 64, 32, 16, 8, 4, 2, 1
11101100 = -128 + 64 + 32 + 8 + 4 = -20
To negate a number: invert every bit, then add one.
20 = 00010100 invert 11101011 add 1 11101100 = -20
Range for n bits: -2^(n-1)^ to 2^(n-1)^ - 1. For 8 bits that is -128 to 127.
Subtraction becomes addition of the negative, which is why hardware needs only an adder.
Floating point
A number is stored as a mantissa and an exponent, both in two's complement.
value = mantissa x 2^exponent
Normalisation maximises precision by ensuring the mantissa begins with 01 for a positive number or 10 for a negative one, so no significant bits are wasted on leading duplicates.
Example with a 6 bit mantissa and a 4 bit exponent:
0.1101 0 0011 -> mantissa 0.1101, exponent 3 -> 110.1 = 6.5
The trade off. For a fixed total number of bits, more mantissa bits give greater precision and more exponent bits give greater range. You cannot increase both.
Fixed point places the binary point at a set position. It is faster and always has the same absolute accuracy, but a far smaller range.
Bitwise operations
| Operation | Effect |
|---|---|
AND | Masking: x AND 00001111 keeps only the low nibble |
OR | Setting bits: x OR 10000000 forces the top bit on |
XOR | Toggling, and a simple reversible cipher, since (x XOR k) XOR k = x |
| Left shift | Multiplies by 2 per place |
| Right shift | Divides by 2 per place, losing the bits shifted out |
Character sets
ASCII uses 7 bits for 128 characters. Unicode uses 16 or more bits for over a million, covering all major writing systems, at the cost of larger files.
Number base converter
Convert between denary, binary and hexadecimal, with every step of the working written out. This tool needs JavaScript, so turn it on to use it. Everything you need to answer the exam question is explained in the text above.
- The leftmost bit has a negative place value, -128. Add up the columns that hold a 1.
- To negate a number: write it in binary, flip every bit, then add 1.
- Eight bits hold -128 to 127. There is one more negative number than positive.
- Mantissa times two to the power of the exponent. The binary point sits after the first mantissa bit.
- The exponent moves the point: 0.1101000 moved 3 places right is 110.1000, which is 6.5.
- Normalise so the first two bits differ. More mantissa bits give precision, more exponent bits give range.
Boolean algebra
The operations
| Notation | Meaning |
|---|---|
A.B or A AND B | Conjunction |
A+B or A OR B | Disjunction |
A' or NOT A | Negation |
A XOR B | Exclusive or, true when exactly one input is true |
The laws you must know
| Law | Form |
|---|---|
| Identity | A + 0 = A, A . 1 = A |
| Null | A + 1 = 1, A . 0 = 0 |
| Idempotent | A + A = A, A . A = A |
| Inverse | A + A' = 1, A . A' = 0 |
| Commutative | A + B = B + A |
| Associative | A + (B + C) = (A + B) + C |
| Distributive | A . (B + C) = A.B + A.C |
| Absorption | A + A.B = A, A . (A + B) = A |
| De Morgan's | (A.B)' = A' + B' and (A+B)' = A' . B' |
De Morgan's laws in words: break the bar and change the operator. The negation of an AND is the OR of the negations, and vice versa. This is examined almost every year.
Simplifying an expression
Simplify A.B + A.B'
A.B + A.B' = A.(B + B') distributive = A.1 inverse law = A identity law
Simplify (A + B).(A + B')
= A.A + A.B' + B.A + B.B' distributive = A + A.B' + A.B + 0 idempotent and inverse = A(1 + B' + B) factorise = A
Karnaugh maps
A visual method of simplification. Adjacent cells differ by exactly one variable, so grouping them eliminates that variable.
For two variables:
| B'=0 | B=1 | |
|---|---|---|
| A'=0 | 1 | 0 |
| A=1 | 1 | 1 |
Rules:
- Group only 1s, in rectangular groups of 1, 2, 4, 8 and so on
- Make groups as large as possible, since a larger group eliminates more variables
- Groups may overlap
- Groups wrap around the edges of the map
- Every 1 must be covered by at least one group
Here the left column groups vertically to give B', and the bottom row groups horizontally to give A, so the expression simplifies to A + B'.
Why simplify
Fewer terms means fewer logic gates, which means lower cost to manufacture, less power consumed, less heat produced, less physical space used and a shorter propagation delay through the circuit.
Logic gate simulator
Build a circuit from gates, wire it up, and see the truth table fill in as you go. This tool needs JavaScript, so turn it on to use it. Everything you need to answer the exam question is explained in the text above.
- Two inputs, one AND gate, one NOT gate, one output.
- A = 1 and B = 0. AND needs both, so it gives 0.
- NOT flips it, so Q becomes 1.
- A = 1 and B = 1. AND gives 1, NOT flips it, Q is 0.
- Q = NOT (A AND B). That is a NAND gate, written out.
Key terms you must be able to define
- Two's complement
- A signed integer representation where the most significant bit carries a negative place value.
- Mantissa
- The significant digits of a floating point number.
- Exponent
- The power of two by which the mantissa is multiplied in floating point representation.
- Normalisation
- Adjusting a floating point number so the mantissa begins 01 or 10, maximising precision.
- Precision
- How finely a value can be represented, determined by the number of mantissa bits.
- Range
- The span of values representable, determined by the number of exponent bits.
- Bit mask
- A pattern combined with a value using AND or OR to isolate or set particular bits.
- De Morgan's laws
- The rules that the negation of an AND is the OR of the negations, and vice versa.
- Karnaugh map
- A grid method for simplifying Boolean expressions by grouping adjacent ones.
- Propagation delay
- The time taken for a signal to pass through the gates of a circuit.
Flashcards
Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.
Reach the top grade on this topic
- Convert to and from two's complement in both directions, and state the range for n bits
- Explain normalisation as maximising precision by removing wasted leading bits
- State the precision against range trade off explicitly whenever floating point is discussed
- Apply De Morgan's laws confidently in both directions
- Show every step of a Boolean simplification, naming the law used
- Justify simplification by cost, power, heat, space and propagation delay
Mistakes that cost marks here
- Forgetting that the most significant bit in two's complement has a negative place value.
- Forgetting the add one step when negating a two's complement number.
- Saying more bits give both greater precision and greater range for a fixed total.
- Applying De Morgan's law without changing the operator.
- Making Karnaugh map groups that are not a power of two in size.
- Simplifying without stating which law justified each step.
Floating point cannot represent 0.1 exactly, for the same reason denary cannot represent one third exactly. This is why financial systems store money as an integer number of pence rather than as a floating point value.
Knowledge check
x AND 00001111 achieve?Exam-style questions
Five written questions in the style of the real paper. Write a full answer, then let the marker check it against the mark scheme.
- LConverts 45 to binary as 00101101
- LInverts all the bits to give 11010010
- LAdds one to give 11010011
First convert 45 into 8 bit binary: 32 + 8 + 4 + 1 = 45, giving 00101101. Then invert every bit, which produces 11010010. Finally add one, giving 11010011. Checking the result confirms it: -128 + 64 + 16 + 2 + 1 = -45.
- LNormalisation adjusts the mantissa so it begins 01 for positive or 10 for negative
- LThis removes leading duplicate bits that carry no information
- LThe greatest possible precision is obtained from the available mantissa bits
A floating point value can be written in many equivalent ways by shifting the mantissa and adjusting the exponent to compensate, and most of those forms waste bits. Normalisation adjusts the number so that the mantissa begins with 01 for a positive value or 10 for a negative one, which guarantees that the leading bits actually carry information rather than simply repeating the sign. Because no mantissa bits are wasted on redundant leading zeros or ones, the maximum possible precision is obtained from the fixed number of bits available. Normalisation also gives every value a single unique representation, which makes comparison and arithmetic in hardware much simpler.
- LThe mantissa determines precision
- LThe exponent determines range
- LThe total number of bits is fixed
- LIncreasing one necessarily reduces the other
In a floating point representation the mantissa holds the significant digits of the value and therefore determines how precisely a number can be represented, while the exponent determines how far the binary point can be shifted and therefore how large or small a magnitude can be expressed, which is the range. Because the total number of bits available for a value is fixed, every bit allocated to the exponent is a bit taken from the mantissa and vice versa. Increasing the exponent field allows very large and very small numbers to be represented but leaves fewer mantissa bits, so values are stored to fewer significant figures and rounding errors become larger. Increasing the mantissa gives greater accuracy for each stored value but restricts the magnitudes that can be represented at all. A designer must therefore choose the split according to whether the application needs to handle extreme magnitudes or to represent moderate values very accurately.
- LFactorises A from the first two terms
- LApplies the inverse law that B + B' equals 1
- LSimplifies A.1 to A using the identity law
- LReaches A + A'.B
- LSimplifies to A + B using the absorption or distributive law
Starting with A.B + A.B' + A'.B, factorise A out of the first two terms to give A.(B + B') + A'.B. By the inverse law B + B' equals 1, so this becomes A.1 + A'.B, and by the identity law A.1 is simply A, leaving A + A'.B. Applying the distributive law gives (A + A').(A + B), and since A + A' equals 1 by the inverse law this becomes 1.(A + B), which by the identity law simplifies to A + B. The final simplified expression is therefore A + B, reduced from three AND terms and two OR operations to a single OR gate.
- LStates that the negation of an AND is the OR of the negations
- LStates that the negation of an OR is the AND of the negations
- LSimplification reduces the number of logic gates required
- LThis lowers manufacturing cost and reduces power consumption and heat
- LIt also reduces propagation delay so the circuit operates faster
De Morgan's laws state that the complement of a conjunction equals the disjunction of the complements, written (A.B)' = A' + B', and that the complement of a disjunction equals the conjunction of the complements, written (A+B)' = A'.B'. In words, breaking the negation bar over an expression requires changing AND to OR or OR to AND. Simplification matters in circuit design because every term and every operator in a Boolean expression corresponds to physical logic gates on a chip. Reducing an expression from six gates to two directly reduces the number of transistors required, which lowers the manufacturing cost of every unit produced and reduces the physical area occupied on the die, allowing more circuitry in the same space. Fewer gates also draw less current, so the circuit consumes less power and generates less heat, which matters greatly in battery powered and densely packed devices. Finally, each gate a signal passes through introduces a small propagation delay, so a shallower simplified circuit produces its output sooner and can therefore be clocked at a higher frequency.