A-level Computing/Print version

From

(Difference between revisions)
Jump to: navigation, search
m (null edit)
m (1 revision: From WIKIBOOKS)
 

Current revision as of 14:56, 9 April 2009

Contents


A-level Computing is an A-level course run for students in the UK

Note: current version of this book can be found at http://en.wikibooks.org/wiki/A-level_Computing

Table of contents

Introduction

Overview

AS modules

Computer Systems, Programming and Network Concepts
Introduction to Computer Systems
Introduction to Programming
Introduction to Information and Data Representation
Introduction to Communication and Networking
Principles of Hardware, Software and Applications
Practical Systems Development (Short practical project)

A2 modules

Processing and Programming Techniques
Data Representation in Computers
Questions
Machine Level Structure
Machine Operation and Assembly Language
Programming Concepts
Operating Systems
Advanced Systems Development
The Practical Project

Answers

Data Representation in Computers


Authors

Contributors

  • Mr. P. Kemp - East London
  • Mr. A. McPherson - West London
  • Mr. J. Edwards - Isle of Man

Thanks for helping out!


License

GNU Free Documentation License

  1. REDIRECT Wikibooks:GNU Free Documentation License

Overview

Introduction

This is a book about A-Level Computing. It aims to fit in with the AQA GCE A-Level Computing syllabus but is not endorsed by AQA. It should be useful as a revision guide or to find alternative explanations to the ones in your textbook. If you haven't heard of an A-Level then this book probably won't be of much interest to you but you can find out about them at Wikipedia.

If any part of this book is unclear or even wrong then please post a comment on the discussion page or simply fix it yourself! In particular, please say if the book assumes any knowledge or skills which not all A-Level Computing students have.

Course Structure

  • To be awarded an AS (Advanced Subsidiary) Level qualification in Computing, a student must take the 3 AS modules.
  • To be awarded an A (Advanced) Level qualification in Computing, a student must take all 6 modules.

Modules

Please note all modules have complementary question and answer sections

AS modules

A2 modules

Appendix


Not a book title page. Please remove Template:Tlx from this page.

Computer Systems, Programming and Network Concepts

This is the Computer Systems, Programming and Network Concepts module of the A-level Computing Book. This module consists of four chapters listed below with their short summaries. Please follow the links to learn out more about each section.

Contents

  1. Introduction to Computer SystemsFile:75%.svg(Sep 24, 2006)
    An introduction to the hardware components of a computer system and the different types of software. Overview of the interaction between software and hardware, binary notation in computers and execution of the processor.
  2. Introduction to ProgrammingFile:50%.svg(Sep 25, 2006)
  3. Introduction to Information and Data RepresentationFile:25%.svg(Sep 26, 2006)
  4. Introduction to Communication and Networking

Introduction to Computer Systems

Definition of this section is available at [1], page 16. This text will be expanded shortly

What is Hardware and Software?

At the highest level, a computer system is composed of hardware and software components. Hardware consists of all the physical devices. All the programs (code) that run on the computer system form the software part. The hardware and software are tightly coupled and they complement each other. Hardware is useless without software and software requires hardware to carry out computations.

Different Types of Software

System Software

System software is anything that is an essential part of the computer system; or in other words a software is the artificial intelligence which dictate the rules of operation within its systems.

Operating system software

An operating system is the low-level software that acts as an interface between the user and the hardware. The OS provides a "virtual machine" where the user is safe to execute their applications and program code.

File:Os stack.png

Common operating systems include Microsoft Windows, Mac OS X and GNU/Linux derivatives.

Utility programs

Utility software helps manage and tune the computer hardware, OS or application software. It usually performs a single task or small range of tasks. Good examples include:

  • Archive: utilities take a file or collection of files and output a single file or stream.
  • Disk defragmenters: reorganise file structure so that all file fragments are contiguous on the disk. Modern filesystems, such as those used by Mac OS X and GNU/Linux, do not need explicit defragmenting.
  • Encryption: utilities use a specific algorithm to encrypt/decrypt the contents of a file or stream using an encryption key.
  • Virus scanners: scan for malicious computer program code in files and storage devices.

Library programs

A collection of subprograms used to develop software and hardware compatibilities. Libraries contain "helper" code and data for other programs to use in a modular way; they are usually not executable and exist purely to provide services to other programs.

Compilers, assemblers and interpreters

A compiler is a computer program that translates code written in a high level language to a lower level language, e.g. assembly language or machine language. The most common reason for translating source code is to create an executable program (converting from a high level language into machine language).

Advantages of using a compiler

  • Source code cannot be stolen/copied
  • Tends to be faster than interpreting source code
  • Produces an executable file, and therefore the program can be run without need of the source code

Disadvantages of using a compiler

  • Object code needs to be produced before a final executable file
  • The source code must be 100% correct for the executable file to be produced

An assembler translates assembly language into machine language. Assembly language consists of mnemonics for machine opcodes so assemblers perform a 1:1 translation from mnemonic to a direct instruction. Conversely, one instruction in a high level language will translate to one or more instructions at machine level.

Advantages of using an assembler

  • Assembly code is often very efficient (and therefore fast) because it is a low level language
  • It is fairly easy to understand due to the use of English-like mnemonics

Disadvantages of using an assembler

  • Lots of assembly code is needed to do relatively simple tasks, and complex programs require lots of programming time
  • Assembly tends to be optimised for the hardware it's designed for, meaning it is often incompatible with different hardware

An interpreter program executes other programs directly, running through program code and executing it line-by-line. This is slower than running compiled code but it can take less time to interpret program code than to compile in then run it — this is very useful when prototyping and testing code.

Advantages of using an interpreter

  • Useful for prototyping software and testing basic program logic
  • Easy to find errors in source code because the translation will stop when an error is encountered

Disadvantages of using an interpreter

  • Source code is required for the program to be executed
  • Interpreters are generally slower than compiled programs due to the per-line translation method

Application Software

Application software is designed for the user to allow them to solve a task. These may include Word processors, spreadsheets and database packages. (NOTE: do not use brand names in the exam, unless asked to, it is better to use the type of software instead, e.g. Excel Spreadsheet package)

General purpose

General purpose application software is designed to solve a wide range of tasks, for example:

  • Word processor
  • Spreadsheet package
  • Presentation package

Special purpose

Special purpose application software performs a specific task or set of tasks, for example:

  • Media player
  • Accounting
  • Vector drawing

Bespoke

Bespoke application software has been written specifically for the needs of a user or company. It is "tailored" to their exact requirements. Some examples might be:

  • Air traffic control
  • Factory robot
  • Tourist kiosk
  • etc

Introduction to how computers store data

Computers can't understand colours, words and sounds like humans. Even if you use digital cameras and voice recognition, a computer has to translate these inputs into the only language it does understand, that is the language of 1 and 0. This is called binary.

Binary is different from our own decimal numbering system. Instead of having 10 different values like decimals: 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9 (this can also be referred to as denary or base 10), binary (or base 2) only has 2 values: 0 and 1. A binary digit, or bit as it is more commonly known, can either be set to 0 (off) or 1 (on).

By combining many bits together, we create what are known as "bit patterns". Inside the computer, all data is transmitted and manipulated in bit patterns. Apart from individual bits, the two other most important bit patterns are:

  • Byte: This is a quantity of bits that computers tend to use as the smallest sequence of bits to store data, e.g. 10110110. This is eight bits wide on most types of computer, but can vary on more obscure machines.
  • Word: This is sometimes called a 'manipulation unit'. It is a set length of bits that varies between types of computers, but is usually 32 or 64 bits long in most modern computers.
  • Program: A program is a set of instructions that are processed by the computer to do a specific operation. This could be anything, from adding two numbers and outputting the result, to the complex instructions in the program of a computer game.
  • Data: Data (the singular is datum) are raw numbers that have no meaning by themselves. Data could be stored about parts of a video clip, an image, a sound, text or a number.

What parts make up a computer?

These components are found in virtually every computer:

  • Processor: The 'brain' of the computer. It executes instructions sequentially and processes data. The processor is usually divided up into the Arithmetic and Logic Unit (ALU), and the Control Unit. The ALU carries out logical evaluations (for example comparisons), and mathematical expressions (such as addition and subtraction). The Control Unit carries out the functions that organise instructions and co-ordinates all the data and instructions, similar to traffic lights controlling the flow of cars. The processor is also called a Central Processing Unit (CPU).
  • Clock: A piece of hardware used to keep the processor (and some other integrated circuits) in time by generating an oscillating signal with a steady frequency.
  • Main Memory: This is temporary storage that stores data currently being worked on. It is accessible to the processor directly, without going through any input/output channels. It does, however, need to connect to the processor via the data, address, and control buses. When power is lost, all data stored in main memory is lost, therefore meaning it is volatile. Main memory is also known as Immediate Access Storage (IAS).
  • Address Bus: A collection of wires between the processor and main memory used to communicate the physical location (address) of data in main memory.
  • Data Bus: A collection of wires between the processor and all internal devices, and is used to send and receive both data and instructions.
  • Control Bus: A collection of wires between the processor and devices used to send commands and get status signals from the devices. For example, it could show whether the computer was reading or writing to memory.
  • I/O Port: An interface and physical connector that allows peripherals, such as a keyboard, mouse or monitor, to communicate with the 'heart' of the computer system — the processor and main memory. I/O stands for Input/Output.
  • Secondary Storage: This is computer memory that is not directly accessible to the processor but uses the I/O channels. It is for storing data not in active use and preserves data even without power, meaning it is non-volatile.

diagram is needed here

How to run programs

All programs are stored as a series of bit patterns ready to be executed (or "run") by the processor. All modern computer systems use the "stored program concept". This is where program instructions are loaded into main memory for the fetch and execute cycle.

The stored program concept basically states that both instructions and data to be operated on can be loaded into memory at the same time, as opposed to having the instructions pre-programmed into the hardware, and then passing this hardware the data to be processed.

The fetch-execute cycle is the retrieval of data and instructions from main memory through the data bus, and then executing the data or instructions using the processor.

An example of these ideas working together would be when a computer system was required to add two numbers together. A program that adds numbers is loaded into main memory. Then each instruction of the program is fetched and executed one after the other by the processor, along with any data required (in this case the numbers to be added). The processor stores the current instruction in a special register and uses its Arithmetic and Logic Unit to process the instruction.

Introduction to Programming

What is Programming?

Programming is the ability to get a computer to perform tasks by writing instructions that a computer can understand and execute. You must remember that the only language a computer understands is binary, a combination of 1s and 0s. This section looks at how we can write instructions and get the computer to understand those instructions.

Programming Languages

When computers were first developed in the 1940s the only way to send instructions to them was by sending them 1s and 0s through flick switches and buttons. Even though the process of sending a computer instructions got better evolving through punch cards, paper tape, magnetic tape and disks, the language computers understand has not changed from the pattern of 1s and 0s, machine code. However the way humans construct these 1s and 0s has gotten easier.

Levels of Programming Language

High/Low level programming languages are terms used to describe how abstracted the language is from the raw machine code and hardware manipulation. Whether a language is high or low level is purely subjective towards the comparison made. Assembly is considered a low level language but is a higher level language than machine code as it resembles English more closely. B.A.S.I.C is even further abstracted and can thus be considered a high level language.

Machine Language - First Generation

The 1s and 0s that a computer can understand and execute

100100101110101000101011010010100101

It is very difficult for humans to understand and difficult to write unaided. Machine code tends to be produced for a specific hardware set up and thus it is not portable to different machines.

Low Level Language - Second Generation

In a low level language the programmer controls and specifies the specifics of how to handle the data, where to store it, how to access it and so on. Assembly is said to be a low level language. Here is a source extract to print "Hello World!" to the screen

; This program displays "Hello, World!"
dosseg
.model small
.stack 100h

.data
hello_message db 'Hello, World!',0dh,0ah,' '

.code
main  proc
      mov    ax,@data
      mov    ds,ax

      mov    ah,9
      mov    dx,offset hello_message
      int    21h

      mov    ax,4C00h
      int    21h
main  endp
end   main
File:B plus.svg easier to write and understand when compared to machine code
File:B plus.svg allows low level access to hardware features
File:B plus.svg can produce small program sizes
File:B plus.svg can produce very fast code
File:B minus.svg not as easy to understand and write when compared to high level language
File:B minus.svg may be written specifically for a certain hardware set up and will therefore not be portable

High Level Language - Third Generation

A high level programming language is one in which the specifics of data handling and manipulation is abstracted away (more so than in a low level language). A high level language generally has more built in functionality than a lower level language and is closer to English for a person to understand. C++ is considered a high language. Here is the source to print "Hello World!".

#include <iostream.h>
using namespace std; 
int main()
{
    cout << "Hello World!";
    return 0;
}
//Note: This code may or may not be compilable, as it varies between compilers and platforms.
File:B plus.svg easy to write and understand
File:B plus.svg built in libraries to perform routine tasks
File:B plus.svg can be ported to multiple hardware setups from same code
File:B minus.svg may be slower than second generation languages
File:B minus.svg may produce larger program files for same functionality than second generation language
File:B minus.svg may not allow for low level hardware access

Program Translators

We already know that computers can only execute Machine Code, so we need a way to convert from 2nd and 3rd generation languages to 1st generation, machine code.

There are three different methods that you may have to use. Assemblers, Compilers and Interpreters

Assemblers

When using Assembly language you will have to use an Assembler. The Assembler will take the assembly code and convert it into the corresponding Machine Code 1s and 0s (actually current flowing and current off). There is a one to one correspondence between a single assembly language instruction and a machine code instruction. In general there will be one line of Machine code produced per line of assembly language. This translation or conversion is called 'assembling' and is performed by a piece of software called an assembler before execution of the code can take place.

Compilers

When using a high level language you will have to use a compiler to turn your code into the corresponding machine code. This is done using a compiler and performed before the execution of the code. A program like a Playstation computer game will be written in a High level language and compiled into machine code. This code will then be burnt to disk at the factory and sent to the shops, when you buy it and place it in the DVD drive of the PS2, the processor will execute the machine code.

Interpreters

Another way of running code written in High level languages is to use an interpreter. This will convert the code you write in machine code for the processor to execute. However the difference here is that the code is converted into machine code as you are running the program, so the code is interpreted only when you need to run it, line by line. This can be much slower than compilation but allows for you to correct errors in the code (debugging) when you meet them. It is also used in common languages like Java and allows you to run the same code on multiple hardware set ups as long as you have an interpreter for that hardware. Think along the lines of running the same Java Application on Linux, Windows and your mobile phone.

Comparisons

You may be asked in the exam which translator you would recommend, here are a few things to think about

  • If the code is in Assembly Language (2nd Generation), then you will use an Assembler
  • If you want the fastest code you will use a compiler
  • If you want the code to be able to run on multiple machines you will need an Interpreter
  • If you want to debug code and not have to recompile with every change you make, you want to pick an Interpreter


Programming Concepts

In this module we will be looking at Imperative languages, Imperative languages are languages that execute one line after another, take this example for instance

int x = 1;
x=x+1;
x=x+1;
x=x+1;
cout << "x = " << x; // print x

output:

x = 4

Declaring a variable then assigning a value to that variable is called Assignment

int x;
x = 45;  // this is assigning the value 45 to the variable x

There are other sorts of languages that you will meet in module 4, but for the moment you only need to know about imperative languages. You will not need to know a particular language for the exam but knowing the concepts behind them and how to understand the pseudo code is essential - pseudo code is close to a third generation language, which is understandable what it should do to you and me, but probably wouldn't run on a computer. This section will now outline a few of the concepts you need to understand

Type Definitions

You may have met datatypes in GCSE when using databases or spreadsheets. The idea behind them is to use a type of data to store information that best matches the data you want to store. In computers this is incredibly important as you are trying to make the best use of the computing resources available, so picking the data type that matches the information you are declaring will be the most efficient way of storing the data. For example if you want to store a number you don't want to use a data type that can also store letters and other characters as this would be a waste of space. e.g.

3 stored in ASCII is 0010 0011
3 stored in pure binary is 0011, thus saving 4 bits

In any programming language you generally have 4 different data types.

  • Integers
    Integers are whole positive numbers, but unlike in maths the integer range will have limitations to the maximum number. The limitations can vary greatly.
    e.g. 104
int x = 45;  //declares an integer called x and sets the value to 45
  • Strings (Characters)
    Strings are a collection of single block characters. e.g.
    e.g. as54sfgjf/.dfg4
string x = "herman";
  • Booleans
    Booleans are variables that are like on/off switches and generally can only equal two values.
    e.g. TRUE/FALSE ON/OFF 1/0
bool x = TRUE;
  • Pointers
    Pointers are an advanced variable type. A Pointer is a 32bit or 16bit or 64bit number (depending on the environment), this number represents a single block in your computer memory. In essence it points to this memory block because you know that it is the nth memory block. Pointers are probably the most useful variable type however you may or may not come across them depending on what language you are using and how high/low level it is. You do not need to know about pointers for module 1.

There are also other datatypes that languages may possess, such as:

  • Character
    The Character data type is a single character.
    e.g. g
char x = 'g';
  • Real
    Real is a more advanced number system than integer, allowing for rational and irrational numbers, decimal places and negatives
    e.g. -12.3231
real x = -23.432;
  • Array
    Arrays are collections of other datatypes, generally able to store only one datatype, for example an array of type string may look like this:
    (red, green, orange, blue, brown)
array x = new array ("red", "green", "orange", "blue", "brown")// declare array with five elements, each of type string.  
  • Think of an array as a spreadsheet; you have the array (x), which is like a spreadsheet file, and you have the columns inside, e.g. x[2] (array x, 'column' 2). This is a one dimensional array. A two dimensional array would be where you have rows; e.g. x[2,3] (array x, column 2, row three). One can have, in theory, as many dimensions in an array as one likes.

Variables

In mathematics the idea of variables are introduced. Variables in a program are very similar EXCEPT that they may equal different values at different times of the program (this is why indeed they are called variables, they vary). They are used to store values that may be needed for the program, you can declare variables of any of the data type declared above. Think of them as a box with a name, you can change the contents of the box and look inside to see the value at any time:

int x = 5;
print x;
x = 104;
print x;
x = 32;
print x;

output:

5 104 32

Depending on the programming language you may or may not have to declare variables (in Basic you don't in C you have to). Declaring variables is simply telling the compiler/interpreter that you want to use a variable with that name.

Global and Local Variable

Dependent on where a variable is declared,the variable can be seen by other elements of the program code. There are two types of variable declarations, that is the Global and the Local variables.

Global variables are declared in the root area of the program code, that may be right at the beginning of the code (in C for example). The values stored in these variables will be accessible from any area of the code. This can be useful if you need to access a variable from anywhere in the program, but if you declare global variables when you don't need to access them all the time, they will sit and take up main memory, thus wasting precious computing resources. Use with care.

Local variables are declared in a sub area of the program code, this may be in a function or procedure. The values stored in these variables will only be accessible from the sub program they are declared in. This can be friendly on computing resources as they are declared when the sub program is called, used, and when the sub program is exited, destroyed. So you only use main memory when you need to store the variable and it does not waste main memory like global variables do. However if you think you will need to variable outside the sub program you should think of using a global variable.

An easy way to think about local and global variables is to think of them as local and global tv channels. Global channels such as Fox and MTV can be accessed from anywhere in the world, but local tv channels such as Channel 5 or Yorkshire TV, can only be accessed in certain areas.

Special cases could be where you declare a global variable called holder, if you then call a sub routine and in this routine there is a local variable declaration of another holder, you do not overwrite the global variable. What happens is for the duration of the sub routine the local variable holder is in charge, when the sub routine exits, the local variable is destroyed and the original value of the global variable now becomes dominant. Take this code for example

code:

main program code
 int holder = 4
 print holder
 ...
 subroutine caller
    int holder = 9
    print holder
 end subroutine
 ...
 run caller
 print holder
end main

output:

4 9 4

[[Rule of thumb:]] If you want to quickly tell the difference between a global and a local variable use these quick rules.

  • If a variable is declared inside a function or a procedure it is a local variable
  • If a variable is declared inside a iterative or selective statement it is local
  • If the declaration is indented from the left hand boundary it probably meets one of the above criteria and is local
  • If it meets none of the above statements and is declared in the main body of code it is a global variable

Constants

Constants are like variables in their declarations and the ability to look at the value stored inside them, however you can not change the values, the value of a constant remains, constant.

constant int x = 34;
print x

output:

34

Order of Operation

Program Design

There are several very useful programming statements that you can use. You probably use these in your everyday lives with out even thinking about it

Selection

An important part of programming is the use of selection, that is the ability to do something if a certain criteria is met. This may be as simple as increasing your health bar in a computer game if you eat a chicken drumstick or inserting the cooling rods into the nuclear reactor if the temperature exceeds a certain value.

File:If-Then-Else-diagram.svg The most common selection statement is the if statement, the idea is that you compare a value to some criteria, if the value and criteria match then you proceed in a certain way, otherwise you do something else. For example:

If Hungry Then
Eat
Else
'Go Out'
End

File:CASE-IF-THEN-END flowchart.png The other type is the Case statement, this can be summarised by several if statements where the value is compared to several criteria and the action of first criteria matched is performed, otherwise a default action may be performed.

Case Enter Restaurant and pick up menu
If Egg and Chips available Then
Order Egg and Chips
End If
If Pie and Chips available Then
Order Pie and Chips
End If
If Curry and Chips available Then
Order Curry and Chips
End If
If Pizza and Chips available Then
Order Pizza and Chips
End If
Default
Leave hungry
End

Iteration

An incredibly important part of computing is the idea of iteration, that is repeating the same thing again and again. You probably use iteration every day. Take writing lines in a detention for example; you write some lines, check to see if you have met the line limit, and if you haven't you write some more lines, check if you have met the line limit and so on, until you do meet the line limit and then you can stop. There are three main sorts of iteration.

File:While-loop-diagram.svg The while loop: For example:

While Hungry Do
Eat
End

File:Do-while-loop-diagram.svg Another type of while loop is a Do-While loop. This is slightly different from the While loop in that you perform the task before you check that you have to perform the task:

Do
Eat
While Hungry
End

File:For-loop-diagram.png The most complicated tool you may meet is the for loop. This is a glorified While loop and don't be put off by how complicated it looks.

For (start with Empty stomach, Is stomach empty?, Eat)
 Wipe mouth

Procedural Code

Procedures and Functions are very slightly different. Functions return a value whilst Procedures do not. An easy way to remember this is by saying that functions are fun, if you call them they will send you something back, procedures return nothing.

Functions - note the return value

code:
a = addtogether(2,3) + 4
print (a)
output: 
9

Procedure - note the lack of value returned by the procedure

code:
addtogether(2,3)
proc addtogether(a,b)
 {
  print(a+b)
 }
output: 
5


To communicate between different parts of the program and to pass variables to the the functions and procedures we use Parameters. For example

Function addtogether (number1, number2)
 {
  return: number1+number2
 }

where this code will add together the numbers 1 & 2.

Object Oriented Code

Structural Concepts

Methods

Objects

Call Stack

FIXME Expand this article. NB I cannot guarantee the accuracy of the information here, nor how relevant it is to the A Level Syllabus. It is worth knowing, anyhow. if it makes no sense to you then there are plenty of tutorials out there!

Object Orientated code is code which forms resides in blocks. An object, such as a class is declared, similar to how one would declare a variable.


   class myClass {
     
     public:
     
     void SayHello(string text) {
       cout << text;
       return void;
     }
   
   } anInstanceofmyClass myClass;


The above code declares an object (of type class) called myClass.

Within myClass a function is declared called SayHello(text), with protection level public (as opposed to protected, or private. Protection layers are effectively the same thing as local and global terms as used for variables. 'Public' means that the function is global, and can be accessed wherever an instance (creation) of the class exists. An object (by which I mean a variable, class, structure or any defined thing in memory) declared with modifier 'private' can only be used, called or accessed by something in that class, e.g. if I declared a private variable in myClass called text it could only be accessed by another Object within myClass, such as the SayHello() function. Protected is the protection modifier inbetween public and private. It can only be accessed by something within the same class, or by an object within a class derived from its class. Derivation, or Inheritance, as it is more often called, is a powerful feature or Object Orientated Programming (OOP), which basically means passing on the objects in one class to a 'child' class. The child class can have its own objects, as well as the objects it received from as many 'parent' classes as required. It can also redefine these objects within itself, e.g. SayHello() no longer takes a variable, it prints the text "hello" on the screen without input. I hope this is all making sense to you!

After the class is defined, as instance (Object) of the class is created, called anInstanceofmyClass. One can create as many instances of a class as one likes, e.g. anInstanceofmyClass1, anInstanceofmyClass2, anInstanceofmyClass3 myClass; To call the SayHello() function, one would type anInstanceofmyClass.SayHello("Hello Text"); anInstanceofmyClass1.SayHello("") and anInstanceofmyClass2.SayHello("") both do the same thing.

Introduction to Information and Data Representation

What is Data and Information?

You may have used the words data and information to mean the same thing in everyday conversation, but it is very important that you know the difference between the two when it comes to computers. Roughly speaking data is the raw stream of 1s and 0s inside the computer and information is when the computer makes sense of this stream. It is interpretation of data in computers and different ways of storing information, that we shall now cover.

Consider data as an encoded form of information and information as any form of communication that provides understandable and useful knowledge to the recipient. - AQA[2]

Data

"Data consists of the raw facts and figures that a computer will process into useful information"

Sources of Data

Data can come from a wide variety of areas, but a good way to think about it is data comes from anywhere where there is an input into a computer. This may be from a keyboard, a scanner, a microphone or a disk drive, amongst many others.

Direct and Indirect Data

Data may be collected with a desired purpose in mind, for example collecting data from a weather station. This kind of data collection is called direct data collection. Other times data may become useful for reasons that it was not originally collected for. This is called indirect data collection. An example of this could be, "The data collected above is used to record where a particular video is" this would be an example of direct data and and example of indirect data would be "The data collected is used to build up a profile of the members for targeted advertising".

Information

Information is meaningful data




Denary Binary BCD ASCII
0 00000000 0000 0100 0000
1 00000001 0001 0100 0001
2 00000010 0010 0100 0010
3 00000011 0011 0100 0011
4 00000100 0100 0100 0100
5 00000101 0101 0100 0101
6 00000110 0110 0100 0110
7 00000111 0111 0100 0111
8 00001000 1000 0100 1000
9 00001001 1001 0100 1001
10 00001010 0001 0000 0100 0001 0100 0000
11 00001011 0001 0001 0100 0001 0100 0001
12 00001100 0001 0010 0100 0001 0100 0010

Consider data as an encoded form of information and information as any form of communication that provides understandable and useful knowledge to the recipient.

Number Representation Systems

Binary number system

Describe the representation of unsigned decimal integers in binary. Perform conversion from decimal to binary and vice-versa. Pure binary representation of decimal integers

Binary-coded decimal (BCD) representation

Describe the representation of unsigned decimal integers in binary-coded decimal. Perform conversions from decimal to BCD and vice versa. Explain advantages of BCD.

Information Coding Schemes

ASCII EBCDIC Unicode

Describe standard coding systems for coding information expressed in character form and other text-based forms. Differentiate between the character code representation of a decimal integer and its pure binary representation.

Introduction to Communication and Networking

Definition of this section is available at [3], page 19.


Communication Methods

Serial

Like a single lane road, all the cars arrive one after another. There is only ever one car going through the check point at any one time.


Parallel

Define both serial and parallel methods and illustrate where they are appropriate. Consider the effect of distance on the transmission of data.

Baud rate

The speed at which telecommunicated data is transmitted, measured in bytes-per-second (BPS).

Bit rate

The rate at which bits are transmitted over a communication path. Normally expressed in bits per second (bps). The bit rate should not be confused with the data signaling rate (baud), which measures the rate of a signal changes being transmitted.

bandwidth

A measure of information or carrying capacity of a signal, expressed as the width of the spectrum of that signal in Hertz.. OR THE DIFFERENCE BETWEEN MAXIMUM AND MINIMUM FREQUENCIES IN A GIVEN SPECTRUM IS CALLED THE BANDWIDTH OF THAT SPECTRUM.

Asynchronous data transmission

The ASYNCHRONOUS (ASYNC) format for data transmission is a procedure or protocol in which each information CHARACTER or BYTE is may be transmitted and received at irregular and independent time intervals. The characters or bytes may also be transmitted as a contiguous stream or series of characters.

Start and stop bits

Describe the purpose of start and stop bits in asynchronous data transmission.

Parity Bits

Parity is a system in which we use a parity bit to check for errors in a communicating system. Parity bits are generally the most simple way of checking for errors. At the end of a byte sent, an extra bit will be added to the end of the byte. We use two different types of parity bits. These are called even and odd parity bits. If we are using even parity, the bit on the end will ensure that the number of ones sent in the previous data is even. If we are using odd parity, then the bit on the end will ensure that the amount of ones in the sent data is odd.

Handshaking

Handshaking is an automated process of negotiation that dynamically sets parameters of a communications channel established between two entities before normal communication over the channel begins. It follows the physical establishment of the channel and precedes normal information transfer.

Protocol

A protocol is a set of rules which computers use to allow them to communicate. There are many different communications protocols, including WiFi (a low level protocol that stipulates how bits should be converted into radio signals), and IP (a higher level protocol which provides addresses for different locations on a WAN, such as the internet).

Modem

A modem is a piece of electronic equipment that takes data from computers and superimposes it onto the carrier signals of public telecommunications systems. This process is called modulation. The equipment also takes previously modulated data from the public telecommunications system and returns them to state that can be read by computers. This process is called demodulation. Modems can be either built-in units or plugged-in units

Networking

Local area network (LAN)

Bus

File:Netzwerktopologie Bus.png

Ring

File:Netzwerktopologie Ring.png

Star

File:Netzwerktopologie Stern.png

Wide area network (WAN)

The Internet

Intranet

Network adapter

Leased line

==Dial up== networking Candidates should be familiar with LAN topologies but will not be required to know details of their operation. Candidates should be aware of the advantages and disadvantages of each LAN topology. Candidates should be able to compare local area networking with standalone operation.

Uniform Resource Locator (URL)

Describe the term URL in the context of Internetworking. .

Domain names

IP addresses

Explain the term domain name and IP address. Describe how domain names are organised

Principles of Hardware, Software and Applications

A-level Computing/Principles of Hardware, Software and Applications

Practical Systems Development (Short practical project)

CPT3 as is the course reference is a practical based project, normally based upon a database of some description but a pure-coding or part-coding, part-database project are also acceptable. This is examined in the summer of the first year of study.

Processing and Programming Techniques

Contents

Data Representation in Computers

Hexadecimal

As you know, the number system we normally count in is base 10, and the number system that computers use, binary, is base 2. Hexadecimal is a base 16 number system. In hexadecimal, the numbers 0-9 are used, just like in denary, but the letters A-F are also used to represent the numbers 10-15. The table below shows the numbers 0-16 in denary, and their binary and hexadecimal equivalents:

Hexadecimal Binary Denary
0 0000 0
1 0001 1
2 0010 2
3 0011 3
4 0100 4
5 0101 5
6 0110 6
7 0111 7
8 1000 8
9 1001 9
A 1010 10
B 1011 11
C 1100 12
D 1101 13
E 1110 14
F 1111 15
10 10000 16

You may notice from the table that one hexadecimal digit can represent exactly 4 binary bits. Hexadecimal is useful to us as a shorthand way of writing binary, and makes it easier to work with long binary numbers.

Converting Between Bases

Since 4 binary bits are represented by one hexadecimal digit, it is simple to convert between the two. You can group binary bits into groups of 4, starting from the right, and adding extra 0's to the left if required, and then convert each group to their hexadecimal equivalent. For example, the number 110110011110101 can be written like this:

0110 1100 1111 0101

and then by using the table above, you can convert each group of 4 bits into hexadecimal:

6 C F 5.

So the binary number 0110110011110101 is 6CF5 in hexadecimal. We can check this by converting both to denary. First we'll convert the binary number, since you already know how to do this:

32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1
0 1 1 0 1 1 0 0 1 1 1 1 0 1 0 1

By multiplying the columns and then adding the results, the answer is 27893.

Notice that the column headings are all 2 raised to a power, 1 = 20, 2 = 21, 4 = 22, 8 = 23, and so on. To convert from hexadecimal to denary, we must use column headings that are powers with the base 16, like this:

163 = 4096 162 = 256 161 = 16 160 = 1
6 C F 5

(You should memorize the values A-F)

Totalling them all up gives us 27893, showing that 0110110011110101 is equal to 6CF5.

To convert from denary to hexadecimal, it is recommended to just convert the number to binary first, and then use the simple method above to convert from binary to hexadecimal.

NOTE: Hexadecimal is used as it is easier for people to understand than pure binary. It DOES NOT take up less space in memory, only on paper!

Negative Binary Numbers

A computer works purely in binary. That means that it only uses ones and zeros, and there's no - or + symbol that the computer can use. The computer must represent negative numbers in a different way.

Twos Complement

We can represent a negative number in binary by making the most significant bit a sign bit, which will tell us whether the number is positive or negative. The column headings for an 8 bit number will look like this:

-128 64 32 16 8 4 2 1
1 0 1 1 1 1 0 1

Here, the most significant bit is negative, and the other bits are positive. You start with -128, and add the other bits as normal. The example above is -67 in denary. -1 in binary is 11111111.

Note that you only use the most significant bit as a sign bit if the number is specified as signed. If the number is unsigned, then the msb is positive.

Converting Negative Numbers

To find out the value of a two's complement number we must first make note of its sign bit (the most significant, left most bit). If 0 then the number is positive, if 1 then the number is negative.

0000 0101 (positive)
1111 1011 (negative)

To find the value of the negative number we must find and keep the right most 1 and all bits to its right, and then flip everything to its left. Here is an example:

1111 1011 find the right most one

1111 1011 
0000 0101 flip all the bits to its left

We can now work out the value of this new number which is:

128  64  32  16   8   4   2   1 
  0   0   0   0   0   1   0   1
                      4   +   1 = −5   (remember the sign you worked out earlier!)

How about a more complex example?

1111 1100 find the right most one

1111 1100
0000 0100 flip all the bits to its left
128  64  32  16   8   4   2   1 
  0   0   0   0   0   1   0   0
                      4         = −4   (remember the sign you worked out earlier!)


So we know how to work out the value of a negative number that has been given to us. How do we go about working out the negative version of a positive number? Like this, that's how...

Take the binary version of the postive number

0000 0101 (5)
0000 0101 find the right most one

0000 0101 
1111 1011 flip all the bits to its left

So now we can see the difference between a positive and a negative number

0000 0101 (5)
1111 1011 (−5)

Binary Subtraction

When it comes to subracting one number from another in binary things can get very messy.

X (82 denary) 0101 0010
Y (78 denary) 0100 1110 −

An easier way to subtract Y from X is to add the negative value of Y to the value of X

X−Y = X+(−Y)

To do this we first need to find the negative value of Y

0100 1110 find the right most one

0100 1110 
1011 0010 flip all the bits to its left

Now try the sum again

   0101 0010     X( 82 denary) 
   1011 0010 +   Y(−78 denary)
   0000 0100
(¹)¹¹¹   ¹       the one carried over the bit 9 is ignored

Which comes out as

128  64  32  16   8   4   2   1 
  0   0   0   0   0   1   0   0
                      4         = 4 = 82-78

Binary Fractions

Up until now, we have only been working with whole numbers, or integers. We need a way to store real numbers on a computer system.

Fixed Point Numbers

First, we should have a look at one of the ways that we can represent fractions in denary:

10 1
1 2 . 7 5

As you can see, the column headings have been extended to and . We can do the same thing in binary with the column headings , , and so on. The number 12.75 in binary is therfore:

8 4 2 1
1 1 0 0 . 1 1

Notice that for the same number of bits after the point, the binary number is less accurate. It can only take 4 different values, wheras the denary number can have 100 different divisions with two digits.

Floating Point Numbers

If you study other subjects such as Physics or Chemistry, you may come across Floating Point numbers like this

  (Planck's constant)

The first bit defines the non-zero part of the number and is called the Mantissa, the second part defines how many positions we want to move the decinal point, this is known as the Exponent and can be positive when moving the decimal point to the right and negative when moving to the left.

If you wanted to write out that number in full you would have to move the decimal point in the exponent 34 places to the left, resulting in:


Which would take a lot of time to write and is very hard for the human eye to see how many zeros there are. There for, when we can accept a certain level of accuracy (6.63 = 3 significant figures), we can store a many digit number like planks constant in a small number of digits. You are always weighing up the scope (or range) of the number against its accuracy (number of significant bits).

The same is true with binary numbers and is even more important. When you are dealing with numbers and their computational representation you must always be aware of how much space the numbers will take up in memory. As we saw with the above example, the non floating point representation of a number can take up an unfeasible number of digits, imagine how many digits you would need to store. in binary? (don't worry this question is rhetorical)

A binary floating point number may consist of 2, 3 or 4 bytes, however the only ones you need to worry about are the 2 byte (16 bit) variety. The first 10 bits are the the Mantissa, the last 6 bits are the exponent.

File:Binary-floating-point-diagram.png

Just like the denary floating point representation, a binary floating point number will have a mantissa and an exponent, though as you are dealing with binary (base 2) you must remember that that instead of having you will have to use


Fixed point binary allows a computer to hold fractions but due to its nature is very limited in its scope. Even using 4 bytes to hold each number, with 8 bits for the fractional part after the point, the largest number that can be held is just over 8 million. Another format is needed for holding very large numbers.

In decimal, very large numbers can be shown with a mantissa and an exponent. ie 0.12² Here the 0.12 is the mantissa and the ² is the exponent. the mantissa holds the main digits and the exponents defines where the decimal point should be placed.

The same technique can be used for binary numbers. For example two bytes could be split so that 10 bits are used for the mantissa and the remaining 6 for the exponent. This allows a much greater scope of numbers to be used.

There are several stages to take when working out a floating point number in binary. Infact it is much like a disco dance routine - known on this page as the Noorgat Dance, Kemp variation (but you wont be tested on name but it should help you to remember)

  1. Sign - find the sign of the mantissa (make a note of this)
  2. Slide - find the value of the exponent and whether it is positive or negative
  3. Bounce - move the decimal the distance the exponent asks, left for a negative exponent, right for a positive
  4. Flip - If the mantissa is negative perform twos complement on it
  5. Swim - starting at the decimal point work out the values of the mantissa. Now make sure you refer back to the sign you recorded on the sign move.

Lets try it out. We are given the following 16 bit floating point number, with 10 bits for the mantissa, and 6 bits for the exponent. Remember the decimal point is between the first and second most significant bits



The first action we need to perform is the sign, find out the sign of the exponent


It is 0 so the mantissa is positive

The second step in the Noorgat dance is the slide, we need to find the value of the exponent, that is the last 6 bits of the number



So we know that the exponent is of size positive one and we will have to move the decimal point 
one place to the right.

The third step in the Noorgat dance is the bounce that is moving the decimal point of the Mantissa the number of positions specified by the slide, which was one position to the right. Like so:



The fourth step is the optional flip. Check back to the sign stage and see if the Mantissa is negative. It isn't? Oh well you can skip past this stage then as we only flip the number if the mantissa is negative.

The fifth and final step is the swim. Taking the mantissa on its own we can now work out the value of the floating point number. Start at the centre and label each number to the left 1,2,4,8,16 and so on. The each number on the right and so on.



Voila! the answer is 1

Normalising Numbers

When dealing with Floating point numbers in binary you must make sure that the first two bits are different. That is:

0.1
1.0

And most definitely NOT

1.1
0.0

This is because we must make sure the space we are using is being used the greatest efficiency. For instance if we take a denary floating point number such as

  (Planck's constant)

If we were to rewrite it as:

  (Planck's constant)

Then you can see the representation takes up an extra 2 characters, the two extra 0's, even though it represents exactly the same number. This may be acceptable when you are not worried about how many characters a number makes up, but in binary and with computers the space that numbers take up is very important, and we need the most efficient representation we can. With a fixed number of bits, a normalised representation of a number will display the number to the greatest accuracy possible. You must make sure that your normalisation does not change the sign of the mantissa. Taking a binary floating point number:


We can see that the number starts with 0.01. We need to change this to 0.1 for it be normalised. To do this we need to move the decimal place one position to the right, and to retain the same number represented by the unnormalised number we need to change the exponent accordingly. With a movement one place right to normalise the number we need to change the exponent to move the decimal point one place left to compensate. Thus negating one from the current exponent.


To make sure you have normalised it correctly, check that


Lets try a more complicated example:


To get the mantissa normalised we need to move the decimal point two places to the right. To maintain the same value as the original floating point number we need to adjust the exponent to be two smaller.


Now check that the new normalised value has the same value as the original.

Data Representation Questions

This page contains questions to assist the reader in understanding the course material. These questions should not be taken as an indication of examination quesions, and the reader should make reference to previous exams to get an idea of these.

Hexadecimal

Help is available here

  1. Convert the following bases to their equivalent hexadecimal values
    1. 8 dec
    2. 10 dec
    3. 16 dec
    4. 0001 bin
    5. 0101 bin
    6. 1111 bin
    7. 1010 1011 bin
    8. 128 dec
    9. 7485 dec
    10. 1010 1111 0000 1011 1110 bin
  2. Convert the following hexadecimal values to the given base
    1. E - decimal
    2. E3 - binary
    3. 73 - decimal
    4. BEE5 - binary
    5. BEEF - decimal
  3. The binary value of the ASCII word Bat is . What is the hexadecimal equivalent?
  4. Why is hexadecimal used on computer displays instead of decimal or binary?

Negative Binary Numbers

Help is available here

  1. What are the denary values of the following twos complement numbers?
    1. 0001 1011
    2. 1111 1111
    3. 0111 1101
    4. 1001 1001
    5. 1011 1000
  2. Convert the following numbers into negative numbers written in binary
    1. 0000 0001
    2. 0110 0000
    3. 0111 1111
    4. 12 (denary)
    5. 67 (denary)
    6. 34 (hexadecimal)
    7. 7E (hexadecimal)
  3. Convert the following negative binary numbers into decimal
    1. 1111 1101
    2. 1111 0100
  4. Find the answers to the following sums in binary, show your working
    1. 0110 1100 - 0000 0111 = 0110 0101 => 101
    2. 0001 1111 - 0001 0011 = 0000 1100 => 12
    3. 0111 0111 - 0101 1011 = 0001 1100 => 28
    4. 23 (hex) - 1F (hex) = 0000 0100 => 4
    5. 0001 0010 - 1111 1101 =

Binary Fractions

Help is available here

  1. What are the values of the following numbers where there are 4 numbers before the decimal point?
    1. 00111000
    2. 01010111
    3. 01101100
    4. EF
    5. 10010011
    6. 11001101 (note: this number is a two's complement number)
  2. Using 1 byte for each number, with a fixed unsigned decimal point between bits 4 and 5, convert the following denary/decimal numbers into binary or get as close as you can
    1. 1.5
    2. 8.75
    3. 9.1875
    4. 0.5625
    5. 13.60
  3. What are the values of the following 16 bit floating point numbers, where the exponent is 6 bits
    1. 0111 0100 1100 1110
    2. 0110 0000 0011 1010
    3. 1011 1100 0100 0001
    4. 1110 0000 0011 1101
  4. Normalise the following 16 bit floating point numbers, where the exponent is 6 bits
    1. 0011 0000 0000 0001
    2. 0001 1100 0000 1110
    3. 1101 0110 0100 0010
    4. 1111 0111 1111 1001

Machine Level Structure

Inside the CPU

The CPU contains an arithmetic-logic unit (ALU), where arithmetic functions are carried out, a control unit, which sends control signals to the memory and peripherals, the system clock, which keeps the various components in correct time with each other, and several registers, which are special memory locations that each have a specific purpose.

Registers

The registers inside a typical processor are:

  • Accumulator, also called general purpose register
The accumulator is a temporary storage space for arithmetic operations. Without it, the result of every operation would have to be written to main memory, and then read back into the ALU, which is very slow. For example, to add up a list of numbers, they are loaded one by one from main memory and added into the accumulator. The final answer is then copied back to main memory.
  • Current instruction register
The current instruction register stores the instruction that is currently being executed.
  • Memory address register
The memory address register stores the address of data or instructions that are to be accessed from main memory.
  • Memory data register
The memory data register stores data that has been read from, or is about to be written to, the main memory.
  • Program counter, also called sequence control register
The program counter stores the address of the next instruction to be fetched from main memory.
  • Status register
The status register contains flag bits that are set or cleared depending on the result of the last instruction. The overflow bit is an example of a status flag in the status register.

The Fetch-Excecute Cycle

When the processor fetches and executes an instruction, it makes use of the registers. The steps that the CPU follows for the assembly language instruction LDA A3 (Load the number at address A3 into the accumulator) are:

1. First, the program counter is read for the address of the next instruction to be executed.
2. The contents of the program counter are copied to the memory address register.
3. The required address in main memory is found, and the contents of that are copied to the memory data register.
4. The program counter is incremented by one, since the old value has already been fetched.
5. The contents of the memory data register are copied to the current instruction register.
6. The instruction in the current instruction register is decoded. The instruction is "load the contents of memory location A3 into the accumulator".
7. "A3" is copied into the memory address register, and the correct memory location is found. The contents of A3 are copied to the memory data register, and then into the accumulator. The instruction has been executed.
8. The program counter is read for the next instruction to be executed...

This process may seem very slow and cumbersome, but a modern computer can do this cycle millions of times per second.

Interrupts

CPU Performance

There are three main factors of a processor that affect its performance.

Clock Speed

The system clock measures time in beats and most operations can be carried out in one beat. The clock speed measures the number of beats per second. A CPU with a clock speed of 1GHz would measure 1,000,000,000 beats per second.

Word Length

The word size of a computer is the number of bits that the CPU can process simultaneously.

Bits may be grouped into 8-, 16-, 32-, 64- or 128-bit 'words', and processed as a unit during input and output, arithmetic and logic instructions.

A processor that has a larger word size will operate faster than a processor with a smaller one.

Bus Width

Both the addresses of data and instructions, and the data and instructions, are transmitted along buses.

The width of the address bus determines the maximum address that can be directly referenced.

The width of the data bus determines how many bits can be transferred simultaneously. This is usually, but not always, the same word size of the computer. For example, not all computers which have a 32-bit word length will have a 32-bit data bus, and so the data may have to be fetched in two groups of 16 bits.

Machine Operation and Assembly Language

Machine Code

Machine code is a binary programming language and is the form most easily processed by a CPU. Each line of code contains an operator (a binary representation of an instruction) and an operand (the data to be opererated on by the given instruction).

Assembly Language Instructions

Assembly language is an intermediate stage between machine code and high-level language and can usually be converted to machine code by a direct translation. Like machine code, an assembly language instruction contains an operator and one or more operands.

The exact range of instructions available to a processor will vary for each processor. However there are four different types of instructions available to any given processor:

Data Transfer Instructions

Data transfer instructions are used to move data between registers and between registers and main memory.

Arithmetic Instructions

Arithmetic instructions can be used to perform arithmetic functions on the contents of the registers. Some processors allow a range of arithmetic instructions such as addition, subtraction, multiplication, division and incrementation. Some others only allow addition and subtraction.

Logic Instructions

Logic instructions can be used to perform logic functions on the contents of the registers. Some examples of logic instructions are; and, or, xor and not. These can be useful when masking numbers, for instance converting from ASCII to binary representation of numbers or converting from higher to lower case ASCII.

AND

Only when there is the comparison of two 1s is the answer one.

OR

Only when there are one or more 1s in a comparison is the answer one.

XOR

or EOR (Exclusive OR / eXclusive OR)
Only when there is exactly one 1 in a comparison is the answer one.

NOT

Flip the 1s to 0s and the 0s to 1s. Useful for Two's Complement.

Masking

Example of conversion from ASCII to binary representation of a number: The ASCII representation of the denary number 3 is The binary representation is So to convert from ASCII to binary we need to mask out the first four bits of the binary representation and maintain the last four bits. There are several ways to do this.

AND solution

Note that we have set the last four bits to 1, try converting another ASCII number and see if this mask works for all of them?

XOR solution

Note that we only set the two bits different between the ASCII and binary to 1.  Try this mask for other ASCII numbers


Rules of Thumb
AND, if you want to keep a part of a number, AND 1 with it.  If you want to blank out part of a number, AND 0 with it.
OR, if you want to keep a part of a number, OR 0 with it.  If you want to set part of a number, OR 1 with it.
XOR, if you want to keep a part of a number, XOR 0 with it.  If you change a one to a zero XOR a 1 with it.

Dealing with don't care

The exam may ask you questions where you have to build a mask for a particular number, checking for ones and zeros as well as ignoring contents of certain cells. Below is a quick crib table (X = don't care about the input)

AND

If you place any other input into the equation other than the desired input the result will come out incorrect. You can now compare this with the number 010 and if equal then you know the correct input was received.

OR

If you place any other input into the equation other than the desired input the result will come out incorrect. You can now compare this with the number 010 and if equal then you know the correct input was received.

Example in assembly

You are allowed to input the following number only 0X1, write some assembly language to check that this works correctly.

AND 1 0 1
CMP 0 0 1
BEQ label

Try writing the OR version of the above code.

Shift Operations

If you look at the binary representations of the following numbers you will notice something peculiar:

0001 = 1
0010 = 2
0100 = 4
1000 = 8

Each time we shift the number one space to the left, the value of the number doubles. This doesn't only work for one bit, take a look at this more complicated example.

0001 0101 = 21
0010 1010 = 42

Again, one shift to the left and the number has doubled. On the other hand, one shift to the right halves the value.

Computers are notoriously bad at doing multiplication and division, it takes lots of CPU time and can really slow your code down. To try and get past this problem computers can shift the values in registers and as long as multiplication or division is by powers of 2, then the CPU time is reduced as the action takes only one line of Machine Code. There are three main types of shifts that processors can perform:

Logical Shift

Shifting either left or right, you add a 0 on the empty end.

Arithmetic Shift

You maintain the sign bit of the number being shifted. Generally only shifts right

File:Rotate right arithmetically.svg

Please note the Logical shift example is also an example of an arithmetic shift as the sign remains the same

Circular Shift

The bit that is pushed off one end appears on the other

Test and Branch Instructions

Test and branch instructions are used to test whether a given condition is true or not and then branch to a given instruction depending on the outcome of the test. This makes conditional statements and interation possible.

Computer Instructions

Computers understand instructions in things called words. In a computing context a word is the number of bits a computer can execute at one time. You will get processors that can understand different word sizes, for example the processor on the Sony Playstation had a 32 bit word size. Sony decided to make the Playstation 2 better than the original and the word size of the Playstation 2 was 128 bits. Generally larger word sizes mean faster and more complex CPUs.

The word that a computer can understand is made up of two parts. The first is the type of instruction, or the opcode, the second part contains the variable(s) on which the instruction will execute, or the operand. The operand is sometimes called the address and the following section will explain how a computer can use the operand in different ways.

0 address instruction

This type of instruction takes no parameters and involves Assembly code that doesn't need variables. For example:

  • CLC - clear the carry flag
  • EXIT - exit a subroutine
  • INC - increment the accumulator by 1

1 address instruction

This type of instruction is very useful when you are dealing with only one general purpose register (the accumulator) and takes only one operand. For example

  • LDA #34 - load the accumulator with the denary value of 34
  • ADD 234 - add the value stored at memory location 234 to the accumulator

2 address instruction

This type of instruction can accept two operands and the complexity of operations increases. For example ADD R1, R2 - add R1 to R2 and store the result back into R1

Addressing Formats

There are different methods that a processor can use to calculate the memory address of the instruction being processed or the data being operated on. These are referred to as addressing modes.

Immediate Addressing

This is the addressing mode you have been used to using so far, where the data being operated on is given in the instruction.

Like this: LDA #35 ;Load the number 35 immediately into the accumulator.

Direct Addressing

In direct addressing the location of the data will be given in the instruction.

Like this: LDA 35 ;Load the contents of location 35 in to the accumulator.

Indirect Addressing

This is similar to direct address, although instead of the instruction giving the address of the data it gives an address where the address to the data is held. For example. If memory location A0 contained “F1” and memory location F1 contained “42” then to load 42 in to the accumulator the instruction would be:


LDA (&A0) ;Loads the contents of address given at &A0 in to acc

Relative Addressing

This type of addressing gives a memory location in terms of the current location in memory.

For example: JMP +10 ;branch to the instruction held 10 bytes on.


If this instruction was held at location 1 then it would jump to location 11.

Base Register Addressing

This type of addressing combines the specified with the address held in another location.


LDA &12,B ;loads acc with contents of the address formed by adding the contents of B with the hex address 12.


In this example the address &12 would be added to the address held in B to find the address of the data to be loaded in to the accumulator.

Indexed Addressing

This form of addressing is similar to base register addressing, except that the base addresses are held in an index register. If using this addressing format then the address of an operand can be changed by changing the contents of the index register.

LDA TABLE,X ;Load in to the ACC the contents of TABLE + x

A story to help you tell the difference

There was once a gangster called the Accumulator, pretty cool name huh? He had a lot of 'business' that he was involved in and had to be paid accordingly. He liked to be paid in several different ways. These were immediately, directly, indirectly, indexed and relative.

When he was paid immediately his goon would give him the money there and then, he got it without having to go find it or solve any clues, he got it immediately.

"Boss here's the £5" =
"LDA #5"

When he was paid directly he had to do a little bit of work, all across town he had lots of Post boxes that his clients would drop off payments in. He would be given the name of a particular post box and know that if he went there he would find the cash he wanted. He was directed to the cash.

"Boss the money is in the postbox at address 1023".
= "LDA 1023"

You must understand that the Accumulator had other business friends who were up to some dodgy business and preferred to remain as hidden as posible in their business dealings to keep the cops off their tracks. To do this they used a clever system of putting the money in a post box but instead of directly giving the Accumulator the address they instead gave the Accumulator the address of a postbox that contained the address of the real postbox. They gave him the address indirectly. Sounds a little confusing? Don't worry, hopefully this short transcript will sort things out

"Boss the address of where the money is, is in the postbox at 304"
The Accumulator opens the postbox at 304 and finds a note saying go to 706
When he gets to 706 he finds the money he was looking for
= "LDA (304)"

Business for a gangster is not always straight forward and occasionally they have to solve a clue or two to get their money, a bit like in the movies. In the case of an Indexed payment, Accumulator is given a clue to solve, he knows the base address and someone provides a value that must be added to the base value. He adds these two together and bingo he finds the address at which the money he is owed is stored.

"Boss the base address you need is 7987"
"Boss our sources say that the house your money is stored at is 5 houses up from the base address"
the Accumulator looks in 7987+5 (7992) and finds the cash he is looking for
= LDA TABLE,X

Assembly Code

Computers can understand only 1s and 0s. To get computers to understand what we want them to do we must get our ideas into these 1s and 0s. You can use High level languages or the low level language of Assembly. In Assembly code every line of code will generally transfer into one line of machine code. Assembly is used in industry to program low level routines and functions and the code produced is usually simple but long.

Instruction sets

An instruction set is the range of different instructions that a CPU can understand. There are two schools of thought, the RISC and the CISC. The RISC - reduced instruction set computer has a small number of different instructions it can perform but it generally does them very fast and efficiently. CISC - complex instruction set computer has a large number of different instructions it can perform but often not as fast as executing them as an equivalent RISC.

For the exam you need to know some basic Assembly instructions that a CPU can understand. We will now look at a range of instructions and then some examples of their use.

Basic instructions

ADD #34
add a number to the accumulator and store the value in the accumulator
SUB #34
take a number from the accumulator and store the value back in the accumulator
DEC
take one from the accumulator
INC
add one to the accumulator
LDA 34
load the accumulator with the value contained in memory location 34
STO 34
store the accumulator value into the memory location 34
CMP &34
compare the accumulator against the hexadecimal value of 34 and store the details in the status register
BNE label1
if the comparison was not equal then jump to label label1
BEQ label1
if the accumulator matched the value being compared the jump to label label1
BGT label1
if the accumulator is greater than the value compared jump to label label1
BLT label1
if the accumulator was less than the value compared jump to label label1
JMP label1
jump directly to label label1, similar to the goto function in some high level languages
AND 01001001
'AND' the accumulator with the value 01001001 storing the result in the accumulator
OR 01001001
'OR' the accumulator with the value 01001001 storing the result in the accumulator
XOR 01001001
'XOR' the accumulator with the value 01001001 storing the result in the accumulator
NOT 
not the accumulator storing the result back in the accumulator
MOV R1, R2
Move the contents of register R1 into register R2

add shift instructions here

Labels

You may have noticed that several of the commands above call for the program to 'jump' to a label called label1. This performs the same function as the 'goto' statement in languages like C. Although the goto statement is frowned on in high level languages, it is essential in Assembly to execute loops and conditional statements. labels will appear like this in code:

LDA #40
label1:
INC
CMP #46
BLT label1
STO 1024

this piece of code loads the accumulator with the value 40. The accumulator is then increased by one and tested against the number 46. If the accumulator is less than 46 then you jump to the label1 to keep incrementing the accumulator. What value will be stored in memory location 1024?

Examples

In the examinations you will be often asked to take a piece of pseudo or real code and convert it into assembly. To make sure the examiner knows what you are doing always write comments with your code. Below are some examples of pseudo code along side their assembly equivalents

x = x + 1
LDA x
INC
STO x
while (x >= 6)
x = x + 1
y = y + 4
end while
while:
LDA x
CMP #6
BLT end
INC
STO x
LDA y
ADD #4
STO y
end:

Quick Check Questions

Provide assembly code that will complete the following tasks:

Q0

y = x + y

Q1

working out the negative two's complement of a given binary number x and storing it back in x

Q2

changing a ASCII lower case letter to its binary equivalent

Q3

do x= x-1
z++
while (z != 10)

Programming Concepts

High Level Languages

High-level languages are usually problem-oriented. This means that most (but not all) high-level languages are written to solve problems in specific areas. As a result there are lots of different high-level languages available to the programmer - some sources on the Internet list over 2,000 of them. This can make the process of selecting the most suitable language a daunting task.

There are several things which a programmer can use to select a suitable language. These include:

  • Looking at the facilities offered by the language and comparing them to the problem
  • How well the programme needs to interact with other existing programmes
  • The suitability of the input or output to match the user's needs
  • How experienced the programmer is with a particular language
  • The cost of the necessary compiler/interpreter
  • How long it will take to learn a new language if necessary

No programmer can have a good knowledge of all the current computer languages currently on the market. Existing languages are always being upgraded and added to and new ones are being developed to cope with new situations.

High level languages can be classified by the way in which they are organised. This method of organisation is beter known as a paradigm of which there are a recognised number.

Imperative / Procedural Programming Languages

An imperative is a command that must be obeyed and that is exactly how an imperative language works. Such a language consists of a long list of instructions that the computer will carry out. It will always carry out exactly the same process as long as exactly the same variables are inputted. The variables allow the user to exercise control over the programme but it will still be executed in a similar way.

Some examples of imperative languages include:

  • Fortran - designed to help with mathematical and scientific products.
  • COBOL (Common Business Oriented Language) - developed specifically to handle files of data and is supported by powerful search and report creation routines.
  • BASIC (Beginner's All-Purpose Symbolic Instruction Code) - originally created to allow students to create simple computer program. In recent years, Microsoft has derived Visual Basic from the original language and has taken it towards being object-oriented.
  • Java - In recent years this language has become associated with the Internet and creating online applications but was originally used to programme the chips in mobile telephones and pagers. This language allows a developer to create standalone program called 'applets' which will run without the use of an interpreter.

Logic and Declarative Languages

A declaration is where a statement is made. In the context of programming languages, with a declarative you give facts and rules to the computer which can then be queried to give data back.

Object-Oriented Programming

Object-Orientated programs consist of a number of interacting objects. The objects each have properties and behaviours, much like physical objects. This similarity to the physical world is often used when modelling an existing system, or theorizing about the action of the program. The objects are similar to procedural programmes in that they have variables, methods and functions.

A key difference between an object and a section of linear code is that the variables, methods and functions may have restrictions placed on their use. By not allowing direct access to the state but instead carrying out any changes itself the object can ensure the consistency of its own state. This property is called Object Encapsulation, it is one of the primary reasons that object orientated programming is better suited to complex problems than linear code. In linear code it is common to store the state of the system in a series of global variables, accessible by any part of the program. Object encapsulation allows each object to be reasoned about without having to consider the problems of possible side-effects from code in another object.

Objects have two parts, the state of the object and the behaviours. The state of the object is stored in a number of variables while the behaviour is defined within the methods and functions. An object is defined by a ‘class’. The ‘class’ is a definition of the variables needed and the code for the methods. When an object orientated program is running only a single copy of the class is required in memory, but multiple sets of state may be created. These sets of state are referred to as objects as the compiler, interpreter or runtime environment hides the sharing of class information.

When an object orientated program starts there are no objects, so how are objects created? The program loader is given an initial class to load into memory and an initial method to then start processing. This first method is then responsible for creating further objects, which may create more objects still.

Object orientated programmes also lend themselves to having one or more concurrent flows of processing within the collection of objects.

Instantiation, classes, inheritance, multiple inheritance, polymorphism.

Object-Oriented programming takes the idea of physical real life objects such as "chairs" and "people" and uses this concept within a programming language. It sets the basic foundation as the "Object" which can be assigned variables (e.g. a name, a persons age) and methods (e.g. a method to call to return the name stored within the object). These objects are then used together to build up a program.

Declarative Programming

In contrast to functional and object oriented languages a declarative language such as prolog contains assertions about the problem domain, often in the form of tuples. The language runtime is most often interactive and allows queries to be entered. The language then uses the declarations to deduce the answer.

Data Structures

Data Structures relates to Data Algorithms and Data Restructring for defining good data base management systems.

Algorithms

Algorithm is the step wise representation without any application of any particular logic .eg in the programme to add 3 numbers step1-start step2-take numbers m1 ,m2 ,m3,temp. step3-take m1=1,m2=2,m3=3. step4- add the three numbers. step5-temp=m1+m2+m3(value of addition goes to temp) step6-print temp. step7-stop

Operating Systems

Operating System Classification

There are several types of operating systems.

Batch

In a batch operating system, instructions are given to the computer in Job control language and the task is carried out without any further user interaction.

The job control language tells the computer:

  • The priority of the job,
  • What to do on an error,
  • The filenames of data files to be used,
  • The owner of the job,
  • The processor time to allocate to the job, and
  • The maximum number of lines that can be printed out by the job.

Interactive

In an interactive operating system, the user interacts directly with the operating system to supply commands and data as the application program executes and the user receives the results of processing immediately, The user is in direct two way communication with the computer.

Real time

A real time operating system will give guaranteed feedback within a predefined set period of time, therefore taking away the unpredictability of the operation being carried out. This allows for the system to be mathematically modelled to allow the time needed for operations to be carried out to be determined, even under the predicted maximum stress levels. It allows deadlines to be set on operations being carried so as to provide a "best of" result within the time period able to be given for an operation.

Example: If a real time operating system was used to control a planes rudders (via a RT application) it would need to set deadlines on the calculations used to calculate rudder movements. Without these deadlines a calculations results may be returned to late and cause to plane to crash.

One very important factor to remember about real time operating systems and applications is that "the right answer late is wrong". After all what is the point in having the correct answer to a planes rudder calculation if it comes too late and the plane has already crashed because the rudder angle was not changed earlier.

Multi-programming system

Multi programming is the apparent simultaneous execution of two or more programs. In a desktop computer, for example, several programs all seem to be running at the same time. What is really happening is that the processor is switching between each program, giving each one a small slice of processor time. This happens fast enough to create the illusion of several programs running at once.

Multi-user system

A multi user operating system allows two or more users to communicate with the computer at the same time. Each user has a terminal with a display unit and an input device, like a keyboard, which is connected to the computer system. The processor switches between each user's programs very quickly, and each user is unaware of anybody else using the computer from another terminal.


Command Line Interface

File:Bash screenshot.png
Screenshot of a sample 'Bash' command line session, taken on Gentoo Linux.

A command line interface or CLI is a tool for interacting with computers, often using a text terminal. Commands are entered as lines of text (that is, sequences of typed characters) from a keyboard, and output is also received as text. CLIs originated when teletype machines were connected to computers in the 1950s. In terms of immediate interaction and feedback, they represented an advance over the use of punch cards.

File:B plus.svg Can be quicker to perform tasks if you know the instructions to write
File:B plus.svg Is light on computer resources in comparison to a GUI
File:B minus.svg Not intuitive, can be hard for beginner users to get to grips with
File:B minus.svg May take more time to perform complex tasks that could be executed with a few clicks in a GUI

Graphical user interface

A graphical user interface (GUI) allows the user to interact with their operating systems via the use of windows, menus and a pointer. A typical GUI allows the user to click icons on screen and follow through hierarchical structures rather than having to type command lines.

File:B plus.svg Can be quicker to perform complex tasks if you don't know the syntax
File:B plus.svg Intuitive, easy for a beginner to get to grips wit
File:B minus.svg Requires a lot of processing power to display the GUI, leaving less for the tasks at hand
File:B minus.svg Some tasks may be quicker to perform on a CLI
File:Kde35.png
An example of KDE, one of the X Window System's many graphical user interfaces available for Unix-like systems

Advanced Systems Development

The Practical Project

This module requires students to analyse a real current system and develop a new one. There are several stages in this coursework:

•Analysis •Design •Implementation •Testing •Documentation •Evaluation

Please note that these categories may bear different names. For example, 'Implementation' maybe known as 'Programming'. In 2009, this coursework is worth 60% of the A2-Level, and overall, 30%.

Chapter Answers

Data Representation in Computers

Hexadecimal

Help is available here

  1. Convert the following bases to their equivalent hexadecimal values
    1. 816
    2. A16
    3. 1016
    4. 116
    5. 516
    6. F16
    7. AB16
    8. AF0BE16
  2. Convert the following hexadecimal values to the given base
    1. 1410
  3. 42617416
  4. Hexadecimal numbers are easier for humans to read, understand and remember.

Negative Binary Numbers

Help is available here

  1. What are the denary values of the following twos complement numbers?
    1. 27
    2. − 1
    3. 125
    4. − 103
    5. − 72
  2. Convert the following numbers into negative numbers written in binary
  3. Convert the following hexadecimal values to the given base
    1. − 3
    2. − 12
  4. Find the answers to the following sums in binary, show your working - not yet finished beyond here (YR 12 please complete!!)
    1. 0110 1100 - 0000 0111 = 01100101
    2. 0001 1111 - 0001 0011
    3. 0111 0111 - 0101 1011
    4. 23 (hex) - 1F (hex)
    5. 0001 0010 - 1111 1101

Binary Fractions

Help is available here

  1. What are the values of the following numbers where there are 4 numbers before the decimal point?
    1. 0011.1000
    2. 0101.0111
    3. 0110.1100
    4. EF
    5. 1001.0011
    6. 1100.1101 (note: this number is a two's complement number)
  2. Using 1 byte for each number, with a fixed unsigned decimal point between bits 4 and 5, convert the following denary/decimal numbers into binary or get as close as you can
    1. 0001.1000
    2. 1000.1100
    3. 1001.0011
    4. 0000.1001
    5. 1101.1001 (as close as you can get)
  3. What are the values of the following 16 bit floating point numbers, where the exponent is 6 bits
    1. 0111 0100 1100 1110
    2. 0110 0000 0011 1010
    3. 1011 1100 0100 0001
    4. 1110 0000 0011 1101
  4. Normalise the following 16 bit floating point numbers, where the exponent is 6 bits
    1. 0011 0000 0000 0001
    2. 0001 1100 0000 1110
    3. 1101 0110 0100 0010
    4. 1111 0111 1111 1001
Personal tools
MediaWiki Appliance - Powered by TurnKey Linux