MSc Computer Systems - Draft Teaching Plan
Hardware Section
The table below outlines a teaching plan for the MSc Computer Systems module. Please note that this is for guidance only and WILL change.
Week
|
Lecture Queens 0.17
|
Lab Queens 1.01 & 3.01/2
|
Reading/Self Study
|
29th Sep
|
Introduction To Number Systems
|
Introduction To Lab
|
Web notes on information representation
|
6th Oct
|
My First Computer
|
|
|
13th Oct
|
I/O Interrupts and DMA
|
|
|
20th Oct
|
Peripheral Devices
|
|
|
27th Oct
|
C Programming 1
|
|
|
3rd Nov
|
C Programming 2
|
|
|
10th Nov
|
|
|
|
17th Nov
|
|
|
|
24th Nov
|
|
|
|
1st Dec
|
|
|
|
8th Dec
|
|
|
|
15th Dec
|
|
|
|
I can be contacted on email eg@dmu.ac.uk
Substantial web based learning material can be found on Ian Sexton’s Web-Site www.cse.dmu.ac.uk/~sexton/WWWPages
They will be found under ELEC1099
The notes below were compiled from various sources, including Ian Sexton, Morteza Safazi, and Kath Garnett. Most of the originals can be found on their respective websites, or on Ian Sexton’s ELEC1099 WWWpages.
1 NUMBER REPRESENTATION
-
Decimal Numbers
In Europe we use the Latin alphabet to represent our diverse languages. However we ceased using Latin Numbers a long time ago. You are unlikely to see the date that I wrote these notes represented as -
XXVII:VI:MMIII Latin Numerals
Instead we use Arabic numerals – 0,1,2,3,4,5,6,7,8,9 – to represent our number systems, so our date looks like -
27:06:2003 Arabic Numerals
Our number system is based on powers on 10 – for no other reason than we have 10 fingers (and thumbs) to count up on. There are other number systems than ours; one lost Polynesian culture only recognised three numbers, One, Two and Many. Even today there is much debate as to whether or not Zero is a true number.
We represent our numbers as polynomials of powers of 10.
For example the number three-hundred-and-eight-six is written as 386. But this is just a convention, what we are really writing is
(3 x 100) + (8 x 10) + (6 x 1)
The first columns numbers are 1’s or 100
The second columns numbers are 10’s or 101
The third columns numbers are 100’s or 102
And so on
Numbers less than one are represented by –ve powers of 10. So 27.34 really means
(2 * 101) + (7 * 100) + (3 * 10-1) + (4 * 10-2)
Where 10-1 is 1/10, 10-2 is 1/100 etc.
We represent –ve numbers by placing a – or minus symbol in front of the numbers. This does not really make the numbers –ve, we just have a convention that tells us how to interpret that symbol.
Our everyday number system is infinite. We can create almost any number we like from the infinitely big to the infinitely small, they can positive or negative, they can even be imaginary. Computers are not so clever, as we will see.
-
Binary Numbers
Computers are not as clever as we are, they are made up of electronic circuits known as LOGIC GATES. These gates are either ON or OFF, and these states are used to represent just two numbers - 0 or 1.
Computers deal with groups of binary digits called words. A word is a string of binary digits that the computer regards as a single unit of data. An n-bit computer is one in which the length of the most frequently used word is n and the main data paths are parallel n-bit paths. The value of n depends on the computer's vintage, the purpose for which it was designed, and its cost. It varies from 4 (in some simple microprocessors) to 64 (e.g. a Pentium) and beyond.
We can build up a number system that is just as rich as our decimal numbers, with just two numbers. The trick is to line them up in columns, and assign different values based on the power of 2 to each column.
If we stick with 4 columns for now we can represent 16 different number –
23 22 21 20 ‘Binade’
‘8’ ‘4’ ‘2’ ‘1’ Equivalent Decade
0 0 0 0 0
0 0 0 1 1
0 0 1 0 2
0 0 1 1 3
0 1 0 0 4
0 1 0 1 5
0 1 1 0 6
0 1 1 1 7
1 0 0 0 8
1 0 0 1 9
1 0 1 0 10
1 0 1 1 11
1 1 0 0 12
1 1 0 1 13
1 1 1 0 14
1 1 1 1 15
We can extend our binary number if we wish, but for the moment we will stick with 4 bits of binary data – better known as a NIBBLE.
-
HEX Notation
Even though computers like binary, it is not easy for us to think in binary. Instead we use a compromise notation known as HEXADECIMAL. HEX arithmetic is a number system based on powers of 16 – therefore we need 16 characters to represent our numbers. For the first 10 numerals we use Arabic notation, for the additional 6 numerals we use Latin letters.
Binary Decimal HEX
0000 0 0
0001 1 1
0010 2 2
0011 3 3
0100 4 4
0101 5 5
0110 6 6
0111 7 7
1000 8 8
1001 9 9
1010 10 A
1011 11 B
1100 12 C
1101 13 D
1110 14 E
1111 15 F
We can now create larger numbers using multiple HEX digits. The first column will be powers of 1, the 2nd column powers of 16 and so on. As each HEX digit replaces 4 binary BITS, 4 HEX digits are the equivalent of 16 binary BITS.
For example the HEX number 3E7B is the same as –
Powers of 16 163 162 161 160
Equivalent decimal 4096 256 16 1
HEX Digits 3 E 7 B
Polynomial (3*4096) + (14*256) + (7*16) + (11*1)
-
Octal Notation
Octal notation is a number system based on powers of 8. It is rarely, if ever used these days, but you may come across it in old textbooks.
Binary Decimal OCTAL
000 0 0
001 1 1
010 2 2
011 3 3
100 4 4
101 5 5
110 6 6
111 7 7
-
Finite Number Sets
Our number system is infinite. However computers do not have infinite storage capacity, so computer number systems are finite.
A memory location is defined by its’ ‘width’, which is another way of saying how many binary bits can be stored in that memory location. Typical lengths are 1,4,8 & 16. These different lengths are also known as a BIT (1), NIBBLE (4), BYTE (8) and WORD (16).
If a memory location is only a byte wide, then the biggest number that it can store is 255 Decimal, or FF HEX. A word memory can go up 65535 Decimal or FFFF HEX. What happens if we overflow? Try it with a pocket calculator, enter the biggest number that you think of, say 99999999999 exp 99, and add 1 to it; the probable result is that the calculator displays ‘ERROR’ – why? Because computers are stupid. They have finite word lengths and cannot ‘think’ of numbers greater than the ability of their memory to store them.
If you add 1 to a byte memory holding FF, it rolls around back to zero. We will see later how computers handle overflows, by use of what is known as the CARRY FLAG.
-
NEGATIVE NUMBERS
In our infinite decimal system we use a ‘-‘ symbol to designate that a number is negative. Computers have no mechanism to prefix a fixed bit length value with a ‘-‘ symbol; so how do computers represent –ve numbers.
Consider our finite number system, using HEX notation. If we have 8 bits our number system is a RING –
00 01 02 03 .... FD FE FF
When we add one to FF it wraps back to 00.
If these are considered to be +ve numbers only, the decimal equivalents to above sequence are –
+0 +1 +2 .... +253 +254 +255
When we add 1 to 255 it goes back to zero. So if we subtract 1 from zero we get FF HEX
So 00 – 01 = FF
The HEX number FF therefore represents the negative number –1
Let us rearrange our RING
FD FE FF 00 01 02 03
Negative Positive
This notation is known as 2’s complement. The rule is that if the most significant binary bit is a ‘1’ then the value is –ve, otherwise it is +ve.
If we have 8 binary bits we can use the 256 available patterns to represent an UNSIGNED BYTE. The numeric range is 00 HEX to FF HEX, or 0 decimal to 255 decimal. Or we can use them to represent a SIGNED BYTE. The numeric range is 80 HEX to 7F HEX, or –128 decimal to +127 decimal.
Here is a simple proof that it works.
00 = 0
FF = -1
FE = -2
FD = -3
What is –3 +4 = ?
FD + 04 = 01
1.8 Converting +ve Numbers to –ve Numbers
There is a simple technique that allows us to switch a +ve number to a –ve number, and back again. Write out the number in binary, swap all the bits over, and then add 1.
Try it –
03 = 00000011 +3 decimal to binary
11111100 swap the bits
11111101 add 1
-3 = FD convert to HEX
It works the other way around as well –
FD = 11111101 -3 in binary
00000010 swap the bits
00000011 add 1
-
convert to HEX
1.9 Sign Extension
If we expand a signed byte, to a signed word, then we must maintain the status of the sign bit. This is known as sign extension.
So the number +3 is 00000011 in binary. If it is sign extended to a 16-bit value it becomes 0000000000000011. The sign bit is extended into the new bit fields.
Now consider –3, which is 11111101 in binary. When it is sign extended to 16 bits it becomes 111111111111111101.
-
Multiplication and Division
Start with the decimal number 37. To multiply it by 10 we simply add a zero to get 370. In effect we have shifted our number to the LEFT, in order to multiply it by 10.
The same is true for binary, but in this instance shifting left multiplies by 2. So if we start with 0011 (3 decimal), and shift it left we get 0110 (decimal 6).
Shifting right divides a number by the base power. So 370 become 37, and 0110 becomes 0011.
1.11 Arithmetic Shift, Logical Shift and Rotate
Most computers support three different types of rotate instruction. This is a generalisation, you must consult the computer’s Assembly Language Manual for the precise details of how that computer works.
‘Arithmetic shifts’ are used for signed numbers, and maintain the status of the sign bit. Consider the negative –6, which is 11111010. If we Arithmetically Shift Right we obtain
11111101 which is –3. Note that all the bits are shifted right, the least significant bit is lost, and the most significant bit remains unchanged. By maintaining the sign bit we can successfully divide signed –ve numbers by 2.
Arithmetic Shifts Left multiply by two. Some computers maintain the sign bit, others just allow the bit 6 to shift into the bit 7 position (such as the 6805). As long as our result does not exceed the available numeric range of –128 to +127, all will be OK
Logical Shifts simply shuffle all the bits left or right as required. If we shift left, bit 7 is lost, and bit 0 is set to 0. If we shift right then bit 0 is lost and bit 7 becomes 0. These instructions can be used to multiply & divide unsigned values, or just for bit manipulation.
Rotations consider the number as a ring, but with the addition of an extra bit called the CARRY FLAG. If we rotate left then bit 7 goes onto the carry flag, bit 6 goes into bit 7 and so on, and bit 0 is filled with the previous contents of the carry flag. Rotate right does it the other way around.
-
What is the Carry Flag
You have seen the carry flag mentioned a few times. Its role is to capture the bit that overflows (from bit 7) or underflows (from bit 0) as a result of any relevant arithmetic or logical operation. So if we add together two numbers, with a result greater than FF HEX then the carry flag is set to 1, else it is set to 0. It is in this case the ‘ninth’ bit. Similarly if we subtract a big number from a little number it is set to 1, to indicate a ‘borrow’.
It is also used to capture overflows for shifts and rotates.
Some instructions will use the carry flag. For example the OP-CODE ADD will add together two numbers, whereas the OP-CODE ADC will also add in the current value of the carry flag. In this way we can perform arithmetic on numbers that exceed the word width of our memory locations.
ADD16: LDA LOWBYTE1 ; Get low byte of 16-bit value 1
ADD LOWBYTE2 ; Add low byte of 16-bit value 2
STA LOWRESULT ; store the low byte of the result
LDA HIGHBYTE1 ; Get the high byte of 16 bit value 1
ADC HIGHBYTE2 ; Add high byte of 16 bit value 2, and carry
; from low byte addition
STA HIGHRESULT2 ; store the low byte of the result
Note that if our final answer is greater than FFFF HEX, then the carry flag is set.
All computers have a CARRY FLAG. They also have what is known as the ZERO FLAG, which is set whenever the result of the last arithmetic or logical operation resulted in a zero.
1.13 Ian Sexton’s Notes Including Floating Point Notation
Information Representation
Introduction
The logic circuits of digital computers are binary, that is, they can at any one time be in one of only two states. Thus, the only information that can be represented is that which is adequately represented with only two values - say whether a switch is on or of, a person is male or female.
The two states of a binary device are usually represented by the binary digits (bits) 0 and 1.
Computers deal with groups of binary digits called words. A word is a string of binary digits, which the computer regards as a single unit of data. An n-bit computer is one in which the length of the most frequently used word is n and the main data paths are parallel n-bit paths. The value of n depends on the computer's vintage, the purpose for which it was designed, and its cost. It varies from 4 (in some simple microprocessors) to 64 (e.g. a Pentium) and beyond.
The representation of Data in a Word
For simplicity, consider a pattern of eight bits, say a word containing eight binary digits. Within 8 bits the patterns which can be distinguished are:
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0
etc.
1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1
It can be seen that there are 2n (256) different patterns. Therefore in an 8-bit word, 256 different values can be distinguished. Generally an n-bit word can be in one of 2n different states. What information is being represented and what value a particular pattern has depends on the context and how the data is coded in binary. Before discussing how commonly needed information is represented for a computer and how it is coded, it is useful to explain some notational conventions for binary words.
Notations and Conventions
The n-bit binary word is often written as:
an-1 an-2 ... a0, where ai is either 0 or 1
Thus considering the 8 bit word:
0 1 1 0 1 0 1 0, a7, a4, a2, and a0 are 0 and a6, a5, a3, a1 are 1
Alternatively, we can describe the individual bits by their 'bit number'. Starting from the right - bit 0 and numbering each bit until bit 7 is reached.
In arithmetic contexts bit 0 is called the least significant bit (LSB) and bit 7 is called the most significant bit (MSB).
Considering an 8-bit word, if the patterns in a binary word are used straightforwardly to represent non-negative integers:
0 0 0 0 0 0 0 0 is 0
and
1 1 1 1 1 1 1 1 is 255
In general: X(10) = a727 + a626 + a525 +a424 + a323 + a222 +a121 +a020
Octal and Hexadecimal
Words written in binary notation are not convenient for human use; we are most adept with decimal (denary) notation, which is also shorter. The most common shorthand ways of writing binary information are called OCTAL and HEXADECIMAL. The conversions to and from binary (if necessary) are much simpler than with denary.
Octal, or Base 8
A given word is split into 3-bit groups starting with bit 0; the least significant bit. For example:
01 101 010 Binary word
is
1 5 2 Octal word
To get the denary equivalent:
X(10) = 1x82 + 5x81 + 2x80
Hexadecimal
Hexadecimal is more popular because 8 bits can be represented by only two 'Hex' digits. The notation is a trickier to master as alphabetic characters are used to represent the extra digits. The table below shows the equivalent representations.
Denary Binary Octal Hexadecimal
0 00000 0 0
1 00001 1 1
2 00010 2 2
3 00011 3 3
4 00100 4 4
5 00101 5 5
6 00110 6 6
7 00111 7 7
8 01000 10 8
9 01001 11 9
10 01010 12 A
11 01011 13 B
12 01100 14 C
13 01101 15 D
14 01110 16 E
15 01111 17 F
16 10000 20 10
Bytes
A byte is the universally accepted name for a group of eight bits. A group of four bits is sometimes called a 'nibble' being smaller than a byte!
Non-negative integers
Conceptually, the simplest interpretation of a bit pattern is as a non-negative integer and the numerical value can be calculated as shown previously. In practice this coding is not used very often but a particular use is in addressing memory locations in the computer where (in simple terms) the amount of real memory a computer can address is determined by the number of bits available on the Address Bus. For example, if the computer has a 16 bit address bus then it can address 65536 (216) memory locations.
The range of values represented by an n-bit word is: 0 to 2n - 1
Integers
A range of consecutive integers, which run from negative, through zero, and then positive, can be represented by a binary string. The most common convention for achieving this is called 2's complement.
Remember that in an n-bit string we can represent at most 2n different values. Thus if half of these values are negative then the maximum positive integer is reduced. Specifically, an 8-bit word interpreted as 2's complement integers can represent numbers in the range:
-128 to +127
To understand how the 2's complement system works, imagine a 6-digit 'mileometer' on a car, which is driven in reverse. The sequence of patterns on the meter as it passes through zero are:
000003
000002
000001
000000
999999
999998
999997
It is natural to think of 999999 as -1 etc. Since 999999 can not represent both -1 and +999999, a rule for interpreting the patterns must be used. If we were to say that:
000000 to 499999 represented positive integers
and
999999 to 500000 represented negative integers
we would have a decimal system exactly analogous to the 2's complement system for representing integer values with binary digits.
Using an n-bit pattern the range is -2n-1 to 2n-1 -1 and all patterns which begin with a 1 represent negative values. This left most bit is called the sign bit. With 2's complement notation the normal rules of addition apply. For example:
2 000002 00000010
+
-3 999997 11111101
= -1 999999 11111111
In order to find the additive inverse of any number i.e. the number to which it must be added to yield an answer of zero, the following rule applies. To help you understand the jargon just think of this technique as changing the sign - making a positive number negative, or a negative number positive.
Change all 0's to 1's and all 1's to 0's (i.e. invert or complement the number) and add 1.
Thus, the additive inverse of
00110010 (50 in decimal) is 11001110 Explanation:
11001101 (by complementing)
11001110 (by adding 1)
In general, in adding two numbers we treat them as unsigned integers and disregard any carry from the most significant bit. e.g.
01010101 85
+ 11001100 -52
= 00100001 33
Consider the addition
01000000 64
+ 01000010 66
= 10000010 130 ?????
Two positive numbers are added (the result should be 130 in decimal) but the answer appears to be negative (bit 7 is a 1). What's wrong? The explanation introduces the concept of an overflow. In an 8 bit pattern 127 is the largest positive integer that can be represented using 2's complement notation - so 130 is outside the range; an overflow has occurred. In essence an overflow occurs when a result is too 'big' for the available number of bits.
To represent a larger range of integers more than 8 bits are needed. If more than one word is used to give a large enough range it is called multiple precision. Most commonly, two words are used in double precision arithmetic.
Share with your friends: |