A-level Computing/AQA/Print version/Unit 2

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/AQA

Authors

• (AQA) Peter EJ Kemp (editor) - London
• (CIE) Peter Astbury - Alexandria, Egypt

Contributors and proof readers

• Students from Christ the King Sixth Form College
• Students from Loxford School
• Students from Wreake Valley Academy
• Peter L Higginson - Reading

Thanks for helping out!

Book Overview

This is a book about A-Level Computer Science. It aims to fit with the AQA GCE A-Level Computer Science 2015 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 Computer Science students have.

A-level

Paper 1 Index

• 1. Fundamentals of programming
• 2. Fundamentals of data structures
• 3. Fundamentals of algorithms
• 4. Theory of computation
• 13. Systematic approach to problem solving
• Skeleton program | A-level | AS-level

Paper 2 Index

• 5. Fundamentals of data representation
• 6. Fundamentals of computer systems
• 7. Fundamentals of computer organisation and architecture
• 8. External hardware devices
• 9. Consequences of uses of computing
• 10. Fundamentals of communication and networking
• 11. Fundamentals of databases
• 12. Fundamentals of functional programming (A-level only)

Non-exam assessment

• 14. The computing practical project (A-level only)

Programming

Accepted languages

• Java
• Pascal
• Python
• VB
• C#

A-Level Projects can be written in any language.

Old Specification (up to 2017)

AS modules

• COMP1 - Problem Solving, Programming, Data Representation and Practical Exercise
• COMP2 - Computer Components, The Stored Program Concept and the Internet

A2 modules

• COMP3 - Problem Solving, Programming, Operating Systems, Databases and Networking
• COMP4 - The Computing Project

How to read the book

You will meet several coloured boxes, here are their meanings:

Specification link What the specification says you must learn for each chapter

Examples Example questions and how to solve them

Questions Questions to test yourself, click below Answer: to check if you were right

Extension Topics that aren't examined but you might be interested in

There will be a lot of concepts that you need to be familiar with, definitions are highlighted like so:

Word - meaning

Unit 2 - Summary

This exam is worth 40% of your AS grade (20% of A2). It is examined in June.

Definitions

Unit 2 definition list

Past Papers

http://www.aqa.org.uk/subjects/ict-and-computer-science/a-level/computing-2510/past-papers-and-mark-schemes

Fundamentals of Computer Systems

From the Specification : Hardware and Software Understand the relationship between hardware and software and be able to define both.

From the Specification : Classification of Software Be aware of how software is classified. Be able to explain what is meant by system software and application software. Understand the need for and attributes of different types of software

From the Specification : System Software Understand the need for, and functions of, system software: Operating system software Utility programs Library programs Translator software (compiler, assembler, interpreter)

From the Specification : Application Software Describe the different types of application software and the criteria for selecting appropriate software for particular purposes. General purpose application software. Special purpose application software. Bespoke application software

From the Specification : Generations of Programming Language Describe machine-code language and assembly language. Awareness of the development of programming languages and the limitations of both machine-code and assembly-language programming First generation - Machine code Second generation - Assembly language Third generation - Imperative high level language Explain the term imperative high level language and its relationship to first and second generation languages Fourth generation - Declarative language Explain the term declarative programming language and where and why declarative languages are used

From the Specification : Types of Program Translator Define each type of language translator and describe situations where each would be appropriate. Assembler Compiler Interpreter

Hardware and software

Hardware - Physical components that make up a computer system

Software - Computer programs and related data that provide the instructions for telling computer hardware what to do and how to do it

Hardware and Software have a symbiotic relationship, this means that without software hardware is very limited; and without hardware, software wouldn't be able to run at all. They need each other to fulfill their potential.

Standard hardware components	The relationship between Hardware and Software
Hardware of a modern personal computer, can you name all the components?	A layer structure showing the relationship between various layers of software and hardware

Exercise: Hardware and Software Define Hardware: Answer: Physical components that make up a computer system. Define Software: Answer: Computer programs and related data that provide the instructions for telling computer hardware what to do and how to do it. Give names to all the numbered hardware components above: Answer: Monitor Motherboard CPU RAM Expansion cards / graphics card / sound card / network card Power supply Optical disc drive Hard disk drive Keyboard Mouse Give 2 examples of software: Answer: Word Processor Operating System Game Spreadsheet Virus Scanner etc NOTE: If you mentioned a brand name such as Windows TM, you get no marks, the exam wants software types meaning you should have written Operating System. After all, for the previous question, you probably didn't answer Nvidia GTX 970 SSC ACX 2.0.

Classification of Software

You have probably used a lot of software over the years, here we are going to study the different classifications (types) of software that are out there.

• Software can perform many different tasks
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 

The two main classifications of software that all programs fit under are:

• System software
• Application software

Without software, most hardware would sit there doing nothing or perform specific tasks. To make most hardware run we need to use software, and your task here is to select the correct type of software for each job.

System software

System software - software designed to operate the computer hardware and to provide a platform for running application software

An example of a modern GUI as used in Ubuntu

Modern computers are complex machines involving many different parts. To keep it running well you will need system software. System software will handle the smooth running of all the components of the computer. It will also provide the general functionality for other programs to use. These include programs that may be tools to speed up the computer, tools to develop new software and programs to keep you safe from attacks. There are several different types of system software that we will look at in more detail very shortly:

• Operating Systems are a collection of programs that make the computer hardware conveniently available to the user and also hide the complexities of the computer's operation. The Operating System (such as Windows 7, Apples iOS or Linux) interprets commands issued by application software (e.g. word processor and spreadsheets). The Operating System is also an interface between the application software and computer. Without the operating system, the application programs would be unable to communicate with the computer.

• Utility programs are small, powerful programs with a limited capability, they are usually operated by the user (or) operator to maintain a smooth running of the computer system. Various examples include file management, diagnosing problems and finding out information about the computer etc. Notable examples of utility programs include copy, paste, delete, file searching, disk defragmenter, disk cleanup. However, there are also other types that can be separately installable from the Operating System.

• Library programs are a compiled collection of subroutines (e.g. libraries make many functions and procedures available when you write a program)

• Translator software (Assembler, Compiler, Interpreter)

1. Assembler translates assembly language programs into machine code (A binary code that a machine can understand).
2. Compiler translates high level language code into object code (which is the machine language of the target machine).
3. Interpreter analyses and executes a high-level language program a line at a time. Execution will be slower than for the equivalent compiled code as the source code is analyzed line by line.

Application software

Application software - software designed to help the user to perform specific tasks

GIMP is an example of photo editing general purpose application software

Application software is designed for people like me and you to perform tasks that we consider useful. This might be the ability of a scientist to work out statistical information using a set of results, or someone who wants to play the latest computer game. There are several categories of Application software that we'll look into shortly:

• General purpose application software.
• Special purpose application software.
• Bespoke application software

Example: Software categories Place the following software into its correct category: Computer Game - This is built for a human user, therefore it is application software Virus Scanner - This is built to make the computer run better, therefore it is system software

Exercise: Software categories What are the two main categories of software? Answer: System Software Application software Why is software important for computer systems? Answer: Without software the tasks that hardware can perform is often fixed and limited For each of the two main classifications of software give three sub categories: Answer: System software Operating system software Utility programs Library programs Translator software (Compiler, assembler, interpreter) Application software General purpose application software. Special purpose application software. Bespoke application software Place each of these software products into its correct category (application or system): Word processor Operating system Defragmenter GPS mapping software Music encoding library Answer: Word processor (Application) Operating system (System) Defragmenter (System) GPS mapping software (Application) Music encoding library (System) Fill in the missing software categories: Answer:

System software

We should know by now that system software is software that helps a computer to run. We will now look at the different types of system software out there and why each is needed:

Operating system software

An operating system (OS) is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system. Without an operating system, a user cannot run an application program on their computer (unless the application program is self booting).

Xfce Graphical User Interface to a Linux operating system

Time-sharing operating systems schedule tasks for efficient use of the system and may also include accounting for cost allocation of processor time, mass storage, printing, and other resources.

For hardware functions such as input/output and main memory management, the operating system acts as a middleman between application programs and the computer hardware, although the application code is usually executed directly by the hardware it will frequently call the OS or be interrupted by it. Operating systems can be found on almost any device that contains a computer, from mobile phones and video game consoles to supercomputers and web servers.

Examples of popular modern operating systems include Android, iOS, Linux, Mac OS X and Microsoft Windows, but don't use these names in the exam!

Extension: Open vs Closed Source operating systems You might hear the words Open Source when you read about operating systems. Linux is the most well known Open Source OS and Windows is the most well known Closed Source OS. So what does this mean? Open Source programs are programs where you can see the code (the source), you can edit it, copy it and use as you wish within the confines of an open source license. You can even sell it, but the person would be welcome to acquire the code for free if they wanted. As a result of this Linux is not developed by one person or one company but uses code developed by thousands of people, working for different organisations all over the world. And as a result there are many different versions (known as distributions) of Linux out there including Ubuntu, Slackware and Fedora. Android is built using Linux code. Closed Source software doesn't allow people to look at the code or adapt it. Companies normally sell closed source products and you'll have to pay for a copy of Windows. Currently about 83% of desktops run the Windows OS.

Utility programs

Utility software is a type of system software which has a very specific task to perform related to the working of the computer, for example anti virus software, disk defragment etc.

Utility software should not be confused with application software, which allows users to do things like creating text documents, playing games, listening to music or surfing the web. Rather than providing these kinds of user-oriented or output-oriented functionality, utility software usually focuses on how the computer infrastructure (including the computer hardware, operating system, application software and data storage) operates. Due to this focus, utilities are often rather technical and targeted at people with an advanced level of computer knowledge.

KDE System Guard monitoring the CPU usage, processes and memory usage

Examples of utility software include:

• Virus scanner - to protect your system from trojans and viruses
• Disk defragmenter - to speed up your hard disk
• System monitor - to look at your current system resources
• File managers - to add, delete, rename and move files and folders

Library programs

Library programs are collections of compiled routines which are shared by multiple programs, such as the printing function.

Illustration of an application which uses libvorbisfile to play an Ogg Vorbis media file

Library programs contain code and data that provide services to other programs such as interface (look and feel), printing, network code and even the graphic engines of computer games. If you have ever wondered why all Microsoft Office programs have the same look and feel, that is because they are using the same graphical user interface libraries. For computer games a developer might not have the time and budget to write a new graphics engine so they often buy graphical libraries to speed up development, this will allow them to quickly develop a good looking game that runs on the desired hardware. For example Battlefield 3 and Need for Speed both use the same Frostbite engine.

The history of game engine development

Most programming languages have a standard set of libraries that can be used, offering code to handle input/output, graphics and specialist maths functions. You can also create your own custom libraries and when you start to write lots of programs with similar functionality you'll find them very useful. Below is an example of how you might import libraries into VB.NET:

'imports the libraries allowing a program to send emails
Imports System.Net.Mail

'imports the libraries allowing a program to draw in 2D
Imports System.Drawing.Drawing2D

Translator software

The final type of system software that you need to know is translator software. This is software that allows new programs to be written and run on computers, by converting source code into machine code. There are three types that we'll cover in a lot more detail shortly

• Assembler - converts assembly code into machine code
• Interpreter - converts 3rd generation languages such as javascript into machine code one line at a time
• Compiler - converts 3rd generation languages such as C++ into machine code all at once

Exercise: System software Give the 4 system software types Answer: Operating system Utility programs Library programs Translator software Explain two functions of an operating system: Answer: Memory management Provides interface between applications and hardware Printing Processor time allocation Give a benefit of using library programs: Answer: You can use code made by other people without having to write it yourself You can use the same code again and again without having to re-write it Give two examples of utility programs: Answer: Virus scanner Disk defragmenter File manager What is system software for? Answer: System software performs tasks to analyse and help with the smooth running of a computer system What is utility software for? Answer: Utility software is a kind of system software designed to help analyze, configure, optimize and maintain the computer What is the purpose of translator software, give two examples Answer: to convert program source code into machine code that can be executed on the processor Assembler Compiler Interpreter

General purpose application software

General purpose application software is a kind of application that can be used for a variety of tasks. It is not limited to one particular function. They provide a large number of features for its users. For example, a word processor could be classed as general purpose software as it would allow a user to write a novel, create a restaurant menu or even make a poster.

Impress presentation software in LibreOffice 5.2

Examples of General purpose application software include: Word processors, Spreadsheet and Presentation software. Whatever you do, do not use brand names!

Special purpose application software

Special purpose application software is a type of software created to execute one specific task. For example, a camera application on your phone will only allow you to take and share pictures. Another example would be a chess game, it would only allow you to play chess.

Chromium web browser

Other examples of special purpose application software are web browsers, calculators, media players, calendar programs etc. Again, make sure that you don't use brand names!

Bespoke application software

Bespoke application software is tailor made for a specific user and purpose. For example a factory may require software to run a robot to make cars, however, it is the only factory making that car in the world, so the software required would have to be specially built for the task.

Other examples might include software for the military, missile/UAV operations, software for hospitals and medical equipment, software being written inside banks and other financial institutions.

There are several things to consider before purchasing bespoke software, on the plus side:

Software is built for and will meet your precise needs

However, you must also consider

Software will be expensive as you have to cover all of the production costs

It may take some time to develop the software, when special purpose software could be brought straight away

The software is more likely to be buggy as it probably won't have thousands of clients using and testing it

Exercise: Application Software List and describe the three types of application software: Answer: General purpose software - software that can be used for multiple purposes Special purpose software - software built for a specific purpose Bespoke application software - software built for a specific user and purpose Give an example of each: Answer: (Don't let the examiner catch you using product names!) General purpose software - word processor / presentation software / spreadsheet Special purpose software - Web browser / media players / calender programs Bespoke application software - car robot control software / military control software Why might you choose to use general purpose software instead of bespoke software, why might it not be suitable? Answer: general purpose software is: cheaper than bespoke readily available, whilst bespoke may take some time to write able to perform multiple tasks probably less buggy However, it might not perform all the tasks needed by the user

Generations of programming language

There are many types of programming languages out there and you might already have heard of a few of them, for example: C++, VB.NET, Java, Python, Assembly. We will now look at the history of how these languages came about and what they are still useful for. In all cases keep in mind that the only thing a computer will execute is machine code or object code when it has been converted from a language to run on a processor.

Generation	First	Second	Third	Fourth
Code example	10101010011000101 10011010100000010 11111111101000101	LDA 34 ADD #1 STO 34	x = x + 1	body.top { color : red; font-style : italic }
Language	(LOW) Machine Code	(LOW) Assembly Code	(HIGH) Visual Basic, C, python etc.	(HIGH) SQL, CSS, Haskell etc.
Relation to Object Code (generally)	--	one to one	one to many	one to many

First generation

The Colossus Mark 2 was the world's first electronic digital programmable computer. Operators had to write the machine code directly by setting switches.

The first generation program language is pure machine code, that is just ones and zeros, e.g.$0010010010101111101010110$. Programmers have to design their code by hand then transfer it to a computer by using a punch card, punch tape or flicking switches. There is no need to translate the code and it will run straight away. This may sound rather archaic, but there are benefits:

Code can be fast and efficient

Code can make use of specific processor features such as special registers

And of course drawbacks

Code cannot be ported to other systems and has to be rewritten

Code is difficult to edit and update

Second generation programming

Second-generation programming languages are a way of describing Assembly code which you may have already met.

By using codes resembling English, programming becomes much easier. The usage of these mnemonic codes such as LDA for load and STA for store means the code is easier to read and write. To convert an assembly code program into object code to run on a computer requires an Assembler and each line of assembly can be replaced by the equivalent one line of object (machine) code:

Assembly Code		Object Code
LDA A ADD #5 STA A JMP #3	-> Assembler ->	000100110100 001000000101 001100110100 010000000011

Assembly code has similar benefits to writing in machine code, it is a one to one relationship after all. This means that assembly code is often used when writing low level fast code for specific hardware. Until recently machine code was used to program things such as mobile phones, but with the speed and performance of languages such as C being very close to Assembly, and with C's ability to talk to processor registers, Assembly's use is declining.

As you can hopefully see there are benefits to using Second-Generation Languages over First-Generation, plus a few other things that makes Assembly great:

Code can be fast and efficient

Code can make use of specific processor features such as special registers

As it is closer to plain English, it is easier to read and write when compared to machine code

And of course drawbacks

Code cannot be ported to other systems and has to be rewritten

Third generation (High Level Language)

Even though Assembly code is easier to read than machine code, it is still not straight forward to perform loops and conditionals and writing large programs can be a slow process creating a mish-mash of goto statements and jumps. Third-generation programming languages brought many programmer-friendly features to code such as loops, conditionals, classes etc. This means that one line of third generation code can produce many lines of object (machine) code, saving a lot of time when writing programs.

Imperative languages - code is executed line by line, in a programmer defined sequence

Third generation (High Level Languages) codes are imperative. Imperative means that code is executed line by line, in sequence. For example:

dim x as integer
x = 3
dim y as integer
y = 5
x = x + y
console.writeline(x)

Would output: 8

Third generation languages can be platform independent, meaning that code written for one system will work on another. To convert a 3rd generation program into object code requires a Compiler or an Interpreter.

To summarise:

Hardware independence, can be easily ported to other systems and processors

Time saving programmer friendly, one line of 3rd gen is the equivalent of many lines of 1st and 2nd gen

However

Code produced might not make the best use of processor specific features unlike 1st and 2nd gen

Extension: Programming Paradigms There are several types of Third-generation languages that you will cover in more detail at A2. They include: Object Orientated Event driven

Fourth generation

Fourth-generation languages are designed to reduce programming effort and the time it takes to develop software, resulting in a reduction in the cost of software development. They are not always successful in this task, sometimes resulting in inelegant and hard to maintain code. Languages have been designed with a specific purpose in mind and this might include languages to query databases (SQL), languages to make reports (Oracle Reports) and languages to construct user interface (XUL). An example of 4th generation programming type is the declarative language.

--an example of a Structured Query Language (SQL) to select criminal details from a database
SELECT name, height, DoB FROM criminals WHERE numScars = 7;

Declarative languages - describe what computation should be performed and not how to perform it. Not imperative!

An example of a declarative language is CSS which you might learn more about when completing any web design unit

/*code to change the headings on a page to green and the paragraphs to red and italic*/
h1 { color : #00FF00; }
p { color : #FF0000; font-style : italic }

Exercise: Generations of programming language Describe what is meant by an imperative language: Answer: code is executed line by line, in sequence What is the relationship between lines of object code and lines of 2nd generation language code Answer: one line of 2nd generation = one line of object code What is the relationship between lines of object code and lines of 3rd generation language code: Answer: one line of 3rd generation = many lines of object code Give two benefits of using 3rd generation over using assembly. Give one drawback Answer: quicker and easier to write and maintain hardware independent, written once, can be used many times may lack the low level, processor specific functionality, meaning slower code Give the definition of a declarative language Answer: describes what computation should be performed and not how to perform it. Not imperative! For 2nd and 3rd generation languages give the program translator required to convert the language generation to object code: Answer: 2nd (Assembly) requires an assembler 3rd requires an interpreter or a compiler

Fundamental Hardware Elements of Computers

From the specification: Logic Gate: Construct truth tables for the following gates: NOT, AND, OR, XOR, NAND, NOR Be familiar with drawing logic diagrams involving one or more of the above gates. Boolean Algebra: Be familiar with the use of De Morgan’s laws and Boolean identities to manipulate and simplify simple Boolean expressions.

Logic Gates

In 1854 a British mathematician, George Boole, developed Boolean Algebra. Instead of an algebra that uses numbers, boolean algebra uses truth values, true(1) and false(0). By defining sentences using truth values and performing operations on these truth values you can work out the overall conclusion of complex statements. Boolean Algebra has had a massive impact on Computer Science and the language that computers understand is a language of 1s and 0s, boolean.

Examples of Boolean Algebra shown in a truth table

$x$ $y$ $x.y$ $x+y$ 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1

$x$ ${\overline {x}}$ 0 1 1 0

Logic gates are pieces of hardware that perform operations on boolean inputs, allowing us to create complex devices out of abstract boolean algebra. Logic gates are the fundamental building blocks of hardware and processors will be made out of billions of them. A logic gate will typically have one or two inputs, in the examples here defined by A and B, There are six types of gate that you need to know:

• 
  NOT
• 
  AND
• 
  OR
• 
  XOR
• 
  NAND
• 
  NOR

NOT

A NOT gate takes only one input and gives one output

A NOT gate will always give an output opposite to what the input is e.g. 1 (not gate) 0. A NOT gate takes one boolean input and flips it. It is possible to have a double NOT. This will reverse the original NOT. The symbol would have an extra bar over it.

In Boolean Algebra we write a NOT symbol by placing a bar on top of a letter(${\overline {A}}$) or letters (${\overline {C+B}}$).

Examples of a NOT gate at work are as follows: NOT(It is not raining) = It is raining ${\overline {TRUE}}=FALSE$ ${\overline {0}}=1$

To summarise here is a truth table showing the relationship between A and ${\overline {A}}$

A	${\overline {A}}$
0	1
1	0

AND (.)

An AND gate takes two inputs and combines them to form one output

An AND gate will combine the boolean values of two inputs (you can get more than two inputs but we don't need to know about that type of gate here). If and only if both inputs are true will it output true. If any of the inputs are false it will out put false.

In Boolean Algebra we write an AND symbol by placing a bullet point between two (${A}.{B}$) or more (${A}.{B}.C$) values.

Examples of an AND gate at work are as follows: Six is bigger than four AND Cats are bigger than gerbils = TRUE $TRUE.FALSE=FALSE$ $(7<8).(2>1)=TRUE$ $(8>0).{\overline {(20=19)}}=TRUE$

An easy way to remember how an AND gate works is thinking about a circuit to turn a light bulb on. If both switches are on then the bulb will light up, if any switch is off then the bulb won't light.

a circuit diagram equivalent to an AND gate

To summarise here is a truth table showing all the different values for two inputs A and B and the result of ANDing those values together

A	B	A.B
0	0	0
0	1	0
1	0	0
1	1	1

OR (+)

An OR gate takes two inputs and combines them to form one output

An OR gate will combine the boolean values of two inputs. If one or more inputs are true then the output will be true. If both the inputs are false then the output will be false.

In Boolean Algebra we write an OR symbol by placing a plus symbol between two (${A}+{B}$) or more (${A}+{B}+C$) values.

Examples of an OR gate at work are as follows: humans have two legs OR Elephants have 8 legs = TRUE $TRUE+FALSE=TRUE$ $(9>3)+(2>1)=TRUE$ ${\overline {(20=20)}}+(5>6)=FALSE$

An easy way to remember how an OR gate works is thinking about a circuit to turn a light bulb on. If one or more switches are on then the bulb will light up, if both switch are off then the bulb won't light.

a circuit diagram equivalent to an OR gate

To summarise here is a truth table showing all the different values for two inputs A and B and the result of ORing those values together

A	B	A+B
0	0	0
0	1	1
1	0	1
1	1	1

XOR ($\oplus$)

A XOR gate takes two inputs and combines them to form one output

An exclusive- OR, XOR, gate will combine the boolean values of two inputs. If exactly one input is true then the output will be true. If both the inputs are false or both the inputs are true then the output will be false.

In Boolean Algebra we write an XOR symbol by placing a plus symbol surrounded by a circle between two (${A}\oplus {B}$) or more (${A}\oplus {B}\oplus {C}$) values.

Examples of an XOR gate at work are as follows: it is raining XOR it is not raining = TRUE $TRUE\oplus TRUE=FALSE$ $(9<3)\oplus (2<1)=FALSE$ ${\overline {(20=20)}}\oplus (8>2)=TRUE$

To summarise here is a truth table showing all the different values for two inputs A and B and the result of XORing those values together

A	B	$~A\oplus B$
0	0	0
0	1	1
1	0	1
1	1	0

NAND

A NAND gate takes two inputs and combines them to form one output

A NAND gate will combine the boolean values of two inputs, AND them together, and NOT the result. If one or less input is true then the output will be true. If both the inputs are true then the output will be false. To draw a NAND gate you draw an AND gate and add a circle to the front, as you can see above.

In Boolean Algebra we write an NAND symbol by taking an AND equation and NOTing the result (${\overline {{A}.{B}}}$).

Examples of an NAND gate at work are as follows: (A=A) NAND (A<>B) = TRUE ${\overline {TRUE.TRUE}}=FALSE$ ${\overline {(9<3).(2<1)}}=TRUE$ ${\overline {(20>20).(8>2)}}=TRUE$

To summarise here is a truth table showing all the different values for two inputs A and B and the result of NANDing those values together

A	B	$A.B$	${\overline {A.B}}$
0	0	0	1
0	1	0	1
1	0	0	1
1	1	1	0

NOR

A NOR gate takes two inputs and combines them to form one output

A NOR gate will combine the boolean values of two inputs, OR them together, and NOT the result. If no input is true then the output will be true. If either or both inputs are true then the result will be false. To draw a NOR gate you draw an OR gate and add a circle to the front, as you can see above.

In Boolean Algebra we write an NOR symbol by taking an OR equation and NOTing the result (${\overline {{A}+{B}}}$).

Examples of an NOR gate at work are as follows: (A=A) NOR (A<>B) = FALSE ${\overline {FALSE+TRUE}}=FALSE$ ${\overline {(9<3)+(2<1)}}=TRUE$ ${\overline {(20>20)+(8>2)}}=FALSE$

A	B	$A+B$	${\overline {A+B}}$
0	0	0	1
0	1	1	0
1	0	1	0
1	1	1	0

Exercise: Logic Gates Give the symbol and gate diagram for an OR statement Answer: + Give the symbol and gate diagram for an AND statement Answer: . Give the symbol and gate diagram for a XOR statement Answer: $\oplus$ Give answers to the following equations: TRUE AND TRUE Answer: TRUE TRUE + FALSE Answer: TRUE TRUE + TRUE Answer: TRUE TRUE $\oplus$ TRUE Answer: FALSE NOT(TRUE) . TRUE Answer: FALSE ${\overline {\overline {TRUE}}}+FALSE$ Answer: TRUE Draw a NAND gate and truth table Answer: A B $A.B$ ${\overline {A.B}}$ 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 Complete the following table: Name NAND NOR AND NOT OR XOR Gate Symbol Truth Table Answer: Name NAND NOR AND NOT OR XOR Gate Symbol ${\overline {A.B}}$ ${\overline {A+B}}$ $.$ ${\overline {A}}$ $+$ $\oplus$ Truth Table A B $A.B$ ${\overline {A.B}}$ 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 A B $A+B$ ${\overline {A+B}}$ 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 A B A.B 0 0 0 0 1 0 1 0 0 1 1 1 A ${\overline {A}}$ 0 1 1 0 A B A+B 0 0 0 0 1 1 1 0 1 1 1 1 A B $~A\oplus B$ 0 0 0 0 1 1 1 0 1 1 1 0

Boolean gate combinations

Now you have learnt logic gates we will take a look at how they are combined inside hardware. You may well be asked in an exam to draw your own logic gates or to work out what a combination of logic gates will output. In this section we will look at the best way to describe what a set of logic gates is in boolean algebra. Let's take a look at a quick example:

Exercise: Logic gate combination outputs For the following logic gate combinations work out output Q for each: Answer: Answer: Answer: This equation can be simplified to equal $A.B$, as $B.B=B$, we'll find out why this is the case in the simplifying boolean equations section coming up Answer: This equation can be simplified to equal 0 (always false), as ${\overline {A+B}}.A=0$, we'll find out why this is the case in the simplifying boolean equations section coming up Answer:

Building circuits

A common question in the exam is to be given some boolean algebra and be asked to express it as logic gates. Let's take a look at an addition and subtraction example that you should be familiar with:

$9-(7+1)$

First we are going to deal with the inner-most brackets

$(7+1)=8$

Finally we combine this answer with the $9-$

$=9-(8)=1$

It will work exactly in the same way for boolean algebra, but instead of using numbers to store our results, we'll use logic gates:

Example: Building circuits $C.(A+B)$ As with any equation, we are going to deal with the inner-most brackets first$(A+B)$, then combine this answer with the $C.$

Exercise: Building circuits Draw the circuit diagrams for the following. (Remember: do we deal with AND or OR first?): $A.B+C$ Answer: $({\overline {A}}+{\overline {B}}).C$ Answer: ${\overline {(A+B)}}.C$ Answer: $(A.{\overline {B}})\oplus (B.C)$ Answer: ${\overline {(A.B).(C+{\overline {D}})}}$ Answer:

A common question in the exam is to give you a description of a system. You'll then be asked to create a boolean statement from this description, and finally build a logic gate circuit to show this system:

Example: Building circuits Using boolean algebra describe the following scenario: “ A car alarm is set off if a window is broken or if it senses something moving inside car, and the car is not being towed, or the engine is not on. ” Where: A = being towed, B = window broken, C = engine on, D = senses movement Before you rush into answering a question like this, let's try and break it down into its components. The questioner will often be trying to trick you. The two occasions that the alarm will sound are: $B+D$ but there is a caveat, the alarm will sound if either of these are true AND two things are also true, namely the engine is NOT on, and the car is NOT being towed: ${\overline {A}}+{\overline {C}}$ Combining both we get (remember the brackets!): $(B+D).({\overline {A}}+{\overline {C}})$ The next step is to create a diagram out of this:

Exercise: Building circuits A security system allows people of two different clearance levels access to a building. Either they have low privileges and they have a card and they are not carrying a mobile. Alternatively they have a key and are allowed to carry a mobile. The inputs available are: A = carrying a card B = carrying a mobile phone C = carrying a key Write down the boolean equation to express this: Answer: $(A.{\overline {B}})+(C)$ If you wrote: $(A.{\overline {B}})+(C.B)$ You'd be wrong! The reason being the text says: Alternatively they have a key and are allowed to carry a mobile. This doesn't mean $C.B$, it means they can carry a mobile, or they can choose not to: $C.(B+{\overline {B}})$, which simplifies to: $C.(B+{\overline {B}})=C.(1)=C$. Draw the logic gate diagram to solve this: Answer:

Gate conversion

Sometimes it is cheaper to create circuits using only one sort of gate, and you might be asked to do so in the exam. These gates tend to be NAND & NOR gates. "But how can you create complex circuits by using only one type of gate?!" you may well ask. We'll now cover how other gates can be made from NAND & NOR gates:

Step	NOR Gate	Equivalent
Diagram
Description	If you split the same input (A) and feed it into NOR both gate inputs you create a NOT Gate
Truth Table	Because: A A $A+A$ ${\overline {A+A}}$ ${\overline {A}}$ 0 0 0 1 1 1 1 1 0 0

Step	NAND Gate	Equivalent
Diagram
Description	If you split the same input (A) and feed it into both NAND gate inputs you create a NOT Gate
Truth Table	Because: A A $A.A$ ${\overline {A.A}}$ ${\overline {A}}$ 0 0 0 1 1 1 1 1 0 0

Exercise: Gate Conversion Render the following boolean equations using only NAND gates: ${\overline {{\overline {A}}.B}}$ Answer: ${\overline {A}}.{\overline {B}}$ Answer: Now try the similar questions using only NOR gates (you might need De Morgan's Law to help you out here, or use a truth table to simplify things) $A+{\overline {B}}$ Answer: ${\overline {A}}.{\overline {B}}$ Answer: Why might you want to use only one sort of gate to create a circuit? Answer: It might be cheaper to make circuits with only one sort of gate, it might make for simpler circuits

Boolean algebra

We have met gate logic and combinations of gates. Another way of representing gate logic is through boolean algebra, a way of algebraically representing logic gates. You should have already covered the symbols, below is a quick reminder:

Bitwise Operator	NOT(${\overline {A}}$)	AND(.)	OR(+)	XOR($\oplus$)	NAND(${\overline {A.B}}$)	NOR(${\overline {A+B}}$)
Description	invert input	where exactly two 1s	where one or more 1s	where exactly one 1	where less than two 1s	where exactly two 0s

For the exam you might have:

• to convert logic gates into boolean algebra,
• build logic gate combinations from boolean algebra,
• simplify boolean algebra.

Simplifying boolean equations

A common question is to give you a complex boolean equation, which you will then have to work out a simpler exact equivalent. This is useful when you are designing circuits and want to minimise the number of gates you are using or make circuits that only use particular types of gates. To simplify boolean equations you must be familiar with two methods. You can normally use either, but try to master both:

• Truth tables
• Boolean algebra - identities and De Morgans Law

Example: Simplifying boolean equations with Truth Tables Draw the truth table for the following: $(A.B)+A$ We are going to solve this using a truth table and we need to break the problem down into its component parts: As the equation uses A and B list the different values they can take (4 in total) $A$ $B$ 0 0 0 1 1 0 1 1 Next we are going to work out the brackets first: $A.B$ and add this to our truth table $A$ $B$ $A.B$ 0 0 0 0 1 0 1 0 0 1 1 1 Finally we will OR this result ($A.B$) with A to find $(A.B)+A$, the final column of the truth table $A$ $B$ $A.B$ $(A.B)+A$ 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 Now that our truth table is complete, look at the final column, is there a simpler way of writing this? Why aye! The final column is true when, and only when, A is true, it doesn't require B's input at all. So we can simplify to A telling us that: $(A.B)+A=A$

Example: Simplifying boolean equations with Truth Tables Let's look at another example ${\overline {A.{\overline {B}}}}$ We first of all need to break down the equation into its component parts. Starting off with A and B we the work out ${\overline {B}}$, then $A.{\overline {B}}$ and finally ${\overline {A.{\overline {B}}}}$. $A$ $B$ ${\overline {B}}$ $A.{\overline {B}}$ ${\overline {A.{\overline {B}}}}$ 0 0 1 0 1 0 1 0 0 1 1 0 1 1 0 1 1 0 0 1 This can be simplified to ${\overline {A}}+B$ telling us that: ${\overline {A.{\overline {B}}}}={\overline {A}}+B$. How did we jump to this conclusion? Let's take a look at all the places where the result is true: $A$ $B$ ${\overline {A.{\overline {B}}}}$ 0 0 1 0 1 1 1 0 0 1 1 1 We need to get a combination of A, B that gives the result shown above. We can see that whenever A is false (${\overline {A}}$)the answer is true: $A$ $B$ ${\overline {A.{\overline {B}}}}$ 0 0 1 0 1 1 1 0 0 1 1 1 We can also see that whenever the B value is true then the answer is also true: $A$ $B$ ${\overline {A.{\overline {B}}}}$ 0 0 1 0 1 1 1 0 0 1 1 1 So we know that we need to combine ${\overline {A}}$ with $B$ to get an equation solving all cases. If we AND them ${\overline {A}}.B$ this only gives us one of the scenarios, so that's not the answer. If we OR them ${\overline {A}}+B$ then this gives us three answers, matching all the responses above. This is our solution.

Exercise: Simplifying boolean equations with Truth Tables Give a simplified boolean description, ?, for the following truth tables: $A$ $B$ $?$ 0 0 0 0 1 1 1 0 0 1 1 1 Answer: $B$ $A$ $B$ $?$ 0 0 0 0 1 0 1 0 0 1 1 1 Answer: $A.B$ $A$ $B$ $?$ 0 0 1 0 1 1 1 0 1 1 1 1 Answer: $1$ $A$ $B$ $?$ 0 0 1 0 1 0 1 0 1 1 1 1 Answer: $A+{\overline {B}}$ Simplify the following boolean equations using truth tables: $({\overline {A.B}}).A$ Answer: $A$ $B$ ${A.B}$ ${\overline {A.B}}$ ${\overline {A.B}}.A$ 0 0 0 1 0 0 1 0 1 0 1 0 0 1 1 1 1 1 0 0 This can be simplified to: $A.{\overline {B}}$ $({\overline {A.B}})+A$ Answer: $A$ $B$ ${A.B}$ ${\overline {A.B}}$ ${\overline {A.B}}+A$ 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 0 1 The answer in all cases is a plain $1$ $(A.{\overline {B}})+B$ Answer: $A$ $B$ ${\overline {B}}$ $(A.{\overline {B}})$ $(A.{\overline {B}})+B$ 0 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 1 0 0 1 This can be simplified to: ${\overline {{\overline {A}}.{\overline {B}}}}$ OR $A+B$ (because of De Morgan's Laws) ${\overline {B}}+A.B$ Answer: Remember that we deal with the AND before the OR, meaning we can read the equation as: ${\overline {B}}+(A.B)$ $A$ $B$ $(A.B)$ ${\overline {B}}$ ${\overline {B}}+(A.B)$ 0 0 0 1 1 0 1 0 0 0 1 0 0 1 1 1 1 1 0 1 This can be simplified to: $A+{\overline {B}}$ $({\overline {A}}+{\overline {B}}).B$ Answer: $A$ $B$ ${\overline {A}}$ ${\overline {B}}$ $({\overline {A}}+{\overline {B}})$ $({\overline {A}}+{\overline {B}}).B$ 0 0 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 This can be simplified to: ${\overline {A}}.B$

Boolean identities

Sometimes a very complex set of gates can be simplified to save on cost and make faster circuits. A quick way to do that is through boolean identities. Boolean identities are quick rules that allow you to simplify boolean expressions. For all situations described below:

A = It is raining upon the British Museum right now (or any other statement that can be true or false)
B = I have a cold (or any other statement that can be true or false)

Identity	Explanation	Truth Table
$A.A=A$	It is raining AND It is raining is the same as saying It is raining	$A$ $A$ $A.A$ 0 0 0 1 1 1
$A.{\overline {A}}=0$	It is raining AND It isn't raining is impossible at the same time so the statement is always false	$A$ ${\overline {A}}$ $A.{\overline {A}}$ 0 1 0 1 0 0
$1+A=1$	2+2=4 OR It is raining. So it doesn't matter whether it's raining or not as 2+2=4 and it is impossible to make the equation false	1 $A$ $1+A$ 1 0 1 1 1 1
$0+A=A$	1+2=4 OR It is raining. So it doesn't matter about the 1+2=4 statement, the only thing that will make the statement true or not is whether it's raining	$0$ $A$ $0+A$ 0 0 0 0 1 1
$A+A=A$	It is raining OR It is raining is the equivalent of saying It is raining	$A$ $A$ $A+A$ 0 0 0 1 1 1
$A+{\overline {A}}=1$	It is raining OR It isn't raining is always true	$A$ ${\overline {A}}$ $A+{\overline {A}}$ 0 1 1 1 0 1
$0.A=0$	1+2=4 AND It is raining. It is impossible to make 1+2=4 so this equation so this equation is always false	$0$ $A$ $0.A$ 0 0 0 0 1 0
$1.A=A$	2+2=4 AND It is raining. This statement relies totally on whether it is raining or not, so we can ignore the 2+2=4 part	$1$ $A$ $1.A$ 1 0 0 1 1 1
$A+B=B+A$	It is raining OR I have a cold, is the same as saying: I have a cold OR It is raining	$A$ $B$ $A+B$ $B+A$ 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 1
$A.B=B.A$	It is raining AND I have a cold, is the same as saying: I have a cold AND It is raining	$A$ $B$ $A.B$ $B.A$ 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1
$A+(A.B)=A$	It is raining OR (It is raining AND I have a cold). If It is raining then both sides of the equation are true. Or if It is not raining then both sides are false. Therefore everything relies on A and we can replace the whole thing with A. Alternatively we could play with the boolean algebra equation: $A+(A.B)=(1.A)+(A.B)$ Using the identity rule $1.A=A$ $(1.A)+(A.B)=A.(1+B)$ Take out the A, common to both sides of the equation $A.(1+B)=A.1$ Using the identity rule $1+B=1$ $A.1=A$ Using the identity rule $1.A=A$	$A$ $B$ $A.B$ $A+(A.B)$ 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1
$A.(A+B)=A$	It is raining AND (It is raining OR I have a cold). If It is raining then both sides of the equation are true. Or if It is not raining then both sides are false. Therefore everything relies on A and we can replace the whole thing with A. Alternatively we could play with the boolean algebra equation: $A.(A+B)=(0+A).(A+B)$ Using the identity rule $0+A=A$ $(0+A).(A+B)=A+(0.B)$ Take out the A, common to both sides of the equation $A+(0.B)=A+0$ Using the identity rule $0.B=0$ $A+0=A$ Using the identity rule $0+A=A$	$A$ $B$ ${A+B}$ $A.(A+B)$ 0 0 0 0 0 1 1 0 1 0 1 1 1 1 1 1

Examples of manipulating and simplifying simple Boolean expressions.

Example: Simplifying boolean expressions Let's try to simplify the following: $A+B+B$ Using the rule $B+B=B$ $A+B+B=A+B$ Trying a slightly more complicated example: $(A.0)+B$ dealing with the bracket first $(0)+B$ as $0.A=0$ $B$ as $0+B=B$ $(A.0)+B=B$

Exercise: Simplifying boolean expressions $A+0$ Answer: $A$ $A.0$ Answer: $0$ $E+1$ Answer: $1$ $A+A+B+B+C$ Answer: $A+B+C$ $(A.B)+(A.B)$ Answer: $A.B$ $A.A.B.B.C$ Answer: $A.B.C$ $(A+{\overline {A}}).B$ Answer: $(A+{\overline {A}}).B$ applying the identity $A+{\overline {A}}=1$ $(1).B$ applying the identity $1.B=B$ $B$

Sometimes we'll have to use a combination of boolean identities and 'multiplying' out the equations. This isn't always simple, so be prepared to write truth tables to check your answers:

Example: Simplifying boolean expressions $(A.B)+A$ Where can we go from here, let's take a look at some identities $(A.B)+(A.1)$ using the identity A = A.1 $A.(B+1)$ taking the common denominator from both sides $A.1$ as B+1 = 1 $A$ Now for something that requires some 'multiplication' $({\overline {A}}.B)+A$ $({\overline {A}}+A).(B+A)$multiply it out $1.(B+A)$cancel out the left hand side as $({\overline {A}}+A)=1$ $B+A$using the identity $1.Q=Q$

Exercise: Simplifying boolean expressions $(A.{\overline {B}})+B$ Answer: $(A.{\overline {B}})+B$ $(A+B).({\overline {B}}+B)$ multiplying out $(A+B).(1)$ $(A+B)$ $(A+B).{\overline {A}}$ Answer: This takes some 'multiplying' out: $(A+B).{\overline {A}}$ $(A.{\overline {A}})+({\overline {A}}.B)$ $0+({\overline {A}}.B)$ $B.{\overline {A}}$ $B.(A+A.B)$ Answer: This takes some 'multiplying' out: $B.(A+(A.B))$ treat the brackets first and the AND inside the brackets first $(B.A)+(B.A.B)$ multiply it out $(B.A)+(A.B)$ as $B.A.B=A.B$ $A.B$ as $(B.A)=(A.B)$ $(A+B).(A+A)$ Answer: $(A+B).(A+A)$ $(A+B).A$ as $A=A+A$ $(A+B).(A+0)$ as $A=A+0$ $A+(B.0)$ take A out as the common denominator $A$ as $(B.0)=0$ $(A.{\overline {B}})+{\overline {A}}$ Answer: This takes some 'multiplying' out: $(A.{\overline {B}})+{\overline {A}}$ $(A+{\overline {A}}).({\overline {B}}+{\overline {A}})$ $1.({\overline {B}}+{\overline {A}})$ ${\overline {B}}+{\overline {A}}$ $(A.B)+{\overline {A}}$ Answer: This takes some 'multiplying' out: $(A.B)+{\overline {A}}$ $(A+{\overline {A}}).(B+{\overline {A}})$ multiplied out $(1).(B+{\overline {A}})$ as $(A+{\overline {A}})=1$ $B+{\overline {A}}$ as $1.Q=Q$ $(A.{\overline {B}})+(A.B)$ Answer: Take the common factor, $A$ from both sides: $A.({\overline {B}}+B)$ As ${\overline {B}}+B=1$ Then $A.({\overline {B}}+B)=A.1$ As $A.1=A$ Then $(A.{\overline {B}})+(A.B)=A$

De Morgan's Laws

De Morgan's laws are used to simplify Boolean equations so that you can build equations only involving one sort of gate, generally only using NAND or NOR gates. This can lead to cheaper hardware. There are two laws that you need to remember:

${\overline {P.Q}}={\overline {P}}+{\overline {Q}}$		${\overline {P+Q}}={\overline {P}}.{\overline {Q}}$
Rule 1		Rule 2

An easy way to remember De Morgan's Laws is through the rhyme: "break the line, change the sign"!

Let's prove that I'm not lying to you by creating a truth table to prove that: ${\overline {P+Q}}={\overline {P}}.{\overline {Q}}$

Answer:

P	Q	${P}+{Q}$	${\overline {P+Q}}$	${\overline {P}}$	${\overline {Q}}$	${\overline {P}}.{\overline {Q}}$
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

Since the values in the 4th and last columns are the same for all rows (which cover all possible truth value assignments to the variables), we can conclude that the two expressions are logically equivalent.

Now we prove ${\overline {P.Q}}={\overline {P}}+{\overline {Q}}$ by the same method:

Answer:

P	Q	${P}.{Q}$	${\overline {P.Q}}$	${\overline {P}}$	${\overline {Q}}$	${\overline {P}}+{\overline {Q}}$
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

There is a rather nice concrete way of thinking about this, with a gate that's padlocked with two padlocks, padlock 1 and padlock 2.

We'll use $P$ to stand for padlock 1 is open, and $Q$ to stand for padlock 2 is open.

You can go through the gate if padlock 1 is open AND padlock 2 is open ($P.Q$) You can not go through the gate if padlock 1 is locked OR padlock 2 is locked (${\overline {P}}+{\overline {Q}}$)

Since 'You can not go through the gate' is the same as the opposite (negation) of 'You can go through the gate' and, remembering

gate is open = $P.Q$ gate is closed = ${\overline {P}}+{\overline {Q}}$ you should be able to see that NOT{gate is open} = ${\overline {P}}+{\overline {Q}}$ or

${\overline {P.Q}}$ = ${\overline {P}}+{\overline {Q}}$

Example: Simplifying boolean equations using boolean algebra Simplify the following: ${\overline {(A.{\overline {B}})+{\overline {A}}}}$ $A$ $B$ ${\overline {A}}$ ${\overline {B}}$ $A.{\overline {B}}$ $(A.{\overline {B}})+{\overline {A}}$ ${\overline {(A.{\overline {B}})+{\overline {A}}}}$ 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 1 0 0 0 0 1 From looking at the truth table we can see that it equates to $A.B$. But we should also know how to get to this result by using boolean identities. Let's give it a go: Using De Morgans Law: ${\overline {P+Q}}={\overline {P}}.{\overline {Q}}$. Where P = $(A.{\overline {B}})$ and Q = $({\overline {A}})$ Take each side separately and applying De Morgans Law convert the centre gate to an AND: ${\overline {(A.{\overline {B}})+({\overline {A}})}}=({\overline {A.{\overline {B}}}}).({\overline {\overline {A}}})$ Now dealing with the left hand side of our new equation (${\overline {A.{\overline {B}}}}$), apply De Morgans Law again (${\overline {P.Q}}=={\overline {P}}+{\overline {Q}}$) and cancel out the double bars: $({\overline {\overline {{\overline {A}}+{\overline {\overline {B}}}}}}).({A})=({\overline {A}}+{B}).({A})$ Multiply out both sides: $({\overline {A}}.A)+(B.A)$ From the Identity ${\overline {A}}.A=0$ we can replace the left hand side: $0+(B.A)$ From the Identity $0+X=X$ we can ignore the 0 leaving us with: $B.A$ From the Identity $X.Y=Y.X$ we can swap the values around: $A.B$ = the value we calculated by truth table Let's try another

Exercise: Simplifying boolean equations Simplify the following using De Morgan's Laws and boolean identities. Check your answers by making truth tables: ${\overline {A.B}}+A$ Answer: Using Demorgans rule that: ${\overline {A.B}}={\overline {A}}+{\overline {B}}$ Making ${\overline {A.B}}+A={\overline {A}}+{\overline {B}}+A$ Using the boolean identity that ${\overline {A}}+A=1$ Making ${\overline {A}}+{\overline {B}}+A={\overline {B}}+1$ Using the boolean identity that ${\overline {B}}+1=1$ We simplify down to ${\overline {A.B}}+A==1$ ${\overline {(A+{\overline {B}}).{\overline {A}}}}$ Answer: $A$ $B$ ${\overline {A}}$ ${\overline {B}}$ $A+{\overline {B}}$ $(A+{\overline {B}}).{\overline {A}}$ ${\overline {(A+{\overline {B}}).{\overline {A}}}}$ 0 0 1 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 1 1 1 0 0 1 0 1 If you're catching on to this, you'll notice that this is the equivalent of $A+B$. But we better check it with boolean algebra identities and De Morgans Law to confirm we have the correct answer. Using De Morgans Law: ${\overline {P.Q}}={\overline {P}}+{\overline {Q}}$ Take each side separately and applying De Morgans Law convert the centre gate to an AND: ${\overline {(A+{\overline {B}}).({\overline {A}})}}={({\overline {A+{\overline {B}}}})+({\overline {\overline {A}}})}$ Cancel out the double bars: ${({\overline {A+{\overline {B}}}})+({\overline {\overline {A}}})}=({\overline {A+{\overline {B}}}})+({A})$ Now dealing with the left hand side of our new equation, apply De Morgans Law again and cancel out the double bars: $({\overline {\overline {{\overline {A}}.{\overline {\overline {B}}}}}})+({A})=({\overline {A}}.{B})+({A})$ Multiply out both sides: $({\overline {A}}+A).(B+A)$ From the Identity ${\overline {A}}+A=1$ we can replace the left hand side: $1.(B+A)$ From the Identity $1.X=X$ we can ignore the 1 leaving us with: $B+A$ From the Identity $X+Y=Y+X$ we can swap the values around: $A+B$ = the value we calculated by truth table ${\overline {({\overline {A+B}})+B}}$ Answer: $A$ $B$ $A+B$ ${\overline {A+B}}$ $({\overline {A+B}})+B$ ${\overline {({\overline {A+B}})+B}}$ 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 1 1 0 1 0 ${\overline {({\overline {A+B}})+B}}$ If you're catching on to this, you'll notice that this is the equivalent of $A.{\overline {B}}$. But we better check it with boolean algebra identities and De Morgans Law to confirm we have the correct answer. Using De Morgans Law: ${\overline {P.Q}}={\overline {P}}+{\overline {Q}}$ Take each side separately (P=${\overline {A+B}}$ and Q=$B$) and applying De Morgans Law convert the centre gate to an AND: ${\overline {({\overline {A+B}})+B}}=({\overline {\overline {A+B}}}).{\overline {B}}$ Cancel out the double bars:$({\overline {\overline {A+B}}}).{\overline {B}}=(A+B).{\overline {B}}$ Multiply out both sides: $(A.{\overline {B}})+(B.{\overline {B}})$ From the Identity $(B.{\overline {B}})=0$ we can replace the right hand side: $(A.{\overline {B}})+0$ From the Identity $X+0=X$ we can ignore the 0 leaving us with: $A.{\overline {B}}$ = the value we calculated by truth table

Hardware and software

Hardware - Physical components that make up a computer system

Software - Computer programs and related data that provide the instructions for telling computer hardware what to do and how to do it

Hardware and Software have a symbiotic relationship, this means that without software hardware is very limited; and without hardware, software wouldn't be able to run at all. They need each other to fulfill their potential.

Standard hardware components	The relationship between Hardware and Software
Hardware of a modern personal computer, can you name all the components?	A layer structure showing the relationship between various layers of software and hardware

Exercise: Hardware and Software Define Hardware: Answer: Physical components that make up a computer system. Define Software: Answer: Computer programs and related data that provide the instructions for telling computer hardware what to do and how to do it. Give names to all the numbered hardware components above: Answer: Monitor Motherboard CPU RAM Expansion cards / graphics card / sound card / network card Power supply Optical disc drive Hard disk drive Keyboard Mouse Give 2 examples of software: Answer: Word Processor Operating System Game Spreadsheet Virus Scanner etc NOTE: If you mentioned a brand name such as Windows TM, you get no marks, the exam wants software types meaning you should have written Operating System. After all, for the previous question, you probably didn't answer Nvidia GTX 970 SSC ACX 2.0.

Internal and external hardware components of a computer

Modern computing (arguably) started in 1822 when Charles Babbage, a British Mathematician, proposed 'the difference engine'. This was a mechanical machine that could calculate numbers from given inputs. Unfortunately Babbage never got enough funding to realise his plans and there was no Victorian Computing Revolution, however, you can see a completed modern version in the Science Museum in London (along with half of Babbage's brain!).

Since Babbage there have been several different designs of computers, and the one we are going to focus on here is called the 3-Box Model, or Von Neumann machine. In this machine:

• All data and instructions are stored in the Main Memory
• Instructions are sent to the Processor along the System Bus to be executed
• Any input and output (such as printing and entering instruction) is performed by I/O devices with the data travelling from the I/O devices to the Processor and Main Memory by means of the System Bus:

Von Neumann's Architecture

Consider a program stored on a DVD, to get the machine to run it, you will have to input the data from the DVD to the memory using the system bus. Once the program is loaded into memory the instructions it will be sent to the CPU line by line using the system bus and executed there. Any things to be printed or shown on a screen will be sent to the Output box.

We'll now look in more detail at these components:

Processor

Plot of CPU transistor counts against dates of introduction. Note the logarithmic scale; the fitted line corresponds to exponential growth, with transistor count doubling every two years.

The processor (or Central Processor Unit - CPU) is one of the most complex parts of any computer system. The processor executes programs and supervises the operation of the rest of the system. Single chip processors are otherwise known as microprocessors. Gordon E Moore theorized that the number of transistors that could be integrated onto the chip would double every 18–24 months, most modern processors will contain billions of transistors. Multicore microprocessors are now very popular, where the processor will have several cores allowing for multiple programs or threads to be run at once.

Main Memory

Main memory - data store that can be directly addressed by the CPU

Main memory is used to store program instruction and data, using the System Bus to communicate with CPU. Main memory is often created using Random Access Memory (or RAM) or Read Only Memory (ROM). Modern computers will have gigabytes of RAM, meaning that large programs can run and multiple programs can run at once. The more main memory that you have the larger the number of programs you can run at once.

Main memory is often made up of RAM modules, where you can adjust the amount by swapping in higher capacity modules or adding more modules

Main memory consists of data stored in addresses, in general, the more main memory you have the more addresses you'll have and vice versa.

Address	Contents
1024	Cabbage
1025	Celery
1026	Courgette
1027	Carrot
1028	Cucumber
1029	Chard

In the above example if we were to perform the following assembly code instruction:

LDA 1026 ;LOAD memory location 1026

This would return the word: "Courgette"

If we were to perform the following assembly code instruction:

STO "Beetroot", 1025 ;STORE data given into memory location 1025

This would change the value stored in memory location 1025 from "Celery" to "Beetroot"

ROM and RAM

RAM - Random Access Memory can be read from and written to. Data is cleared when the power is off

ROM - Read Only Memory can only be read from, data is maintained when the power is off

The two main types of main memory are ROM and RAM. Whilst RAM might be several gigabytes in size, ROM will often be a few kilobytes. As ROM is read only memory, it tends to store core software instructions such as the code needed to load the Operating System into RAM (known as bootstrapping) or change the bios. RAM is much much larger and stores the code to run the operating system and programs that you run on your computer. When you load a disc into a games console, the code won't do anything until it has loaded from the disc into the system RAM, that's why you see a loading screen.

Exercise: Central Processing Unit Give a definition for main memory: Answer: Main memory is a data store that can be directly addressed by the CPU What is the difference between ROM and RAM? Answer: ROM is Read Only Memory, RAM is random access memory. This means that ROM cannot be written to, it can only be read from. RAM can be both read from and written to. Name the four components of Von Neumann Architecture Answer: Processor Main memory I/O devices System bus

System Bus

A Bus is a connection between different devices. This connection will normally consist of multiple wires along which signals, instructions and data will be carried. In Von Neumann Architecture there is a single bus to manage the connection between the three main components. The System Bus consists of 3 separate buses, each with a specific task that you need to know. This three bus model is an expansion of the Von Neumann architecture showing greater detail.

Address Bus

A single-directional bus that carries address signals from the CPU to Main Memory and I/O devices. This might involve the CPU requesting some data from Main Memory, sending the address of the data to Main Memory, then Main Memory returning the data along the data bus. Let's take a look at some code:

LDA 23

This code is asking to load the data from memory address 23 into the CPU, the address bus does not send addresses to the processor, but only sends them from the processor. To do this the CPU would send 23 along the Address Bus, and the value from memory location 23 would be sent along the Data Bus back to the CPU. The size of the Address Bus can dictate how much Main Memory you can have in your system. For example, if you had an Address Bus of 3 bits, then:

Maximum value   = 111 = 7
Range of values = 
                  000
                  001
                  010
                  011
                  100
                  101
                  110
                  111

This would mean that your Main Memory could only have 8 different addressable blocks

Data bus

A bi-directional bus, typically consisting of 32 wires, used to transport data and instructions between the three components of the three-box model. The larger the Data Bus the more data can be transported at one time. For example if we have an 8 bit Data Bus, the maximum value we could send along the Bus would be:

1111 1111 = 255

The larger the Data Bus the more data we can send at once and the more complex instructions we can use.

Control bus

A bi-directional bus, typically consisting of more than 16 wires, used to transport control signals between the three components of the three-box model. The control bus is used to carry important information such as messages to say when a device has finished a job or when a device has just been plugged in. A simple example would be when you plug in your USB key and after a few moments a screen pops up asking you what you want to do with it. The control bus also contains interrupt signals which allow devices (printers, keyboards, disks, etc.) to signal that they have finished a request. The CPU temporarily suspends its current program, services the device and then resumes the previous program.

Extension: Modern Architecture The information above will serve you well for the exam; however, the way many modern processors work may break the definitions you have just learnt: Since modern CPUs now have internal memory(cache) and I/O devices have the ability to access memory without the need for the CPU(DMA), the address bus has to be bi-directional. However, the model used in the exam treats it as being uni-directional. Some modern systems combine address and data buses since they are used at different parts of the fetch decode execute cycle. What is now called ROM is nowadays just hard to write Flash memory requiring special equipment, voltages or processes. It isn't truly Read Only as you can change it with some difficulty. You may have upgraded the BIOS on your computer for example. Modern chip designs have evolved either towards integrating more logic onto the CPU chip (memory controllers, Ethernet interfaces, serial ports etc.) for embedded applications (driven originally by the design of printers and photocopiers and called SOC - System On a Chip) or towards a single fast bus towards a second chip that has multiple buses for various types of device (see Northbridge for more information).

Exercise: Central Processing Unit Complete the following table: Name Direction Description Address Bus Data Bus Control Bus Answer: Name Direction Description Address Bus uni-directional Carries addresses from the CPU to main memory or other devices Data Bus bi-directional Transports data and instructions Control Bus bi-directional Transports control signals What is the largest number the following width data buses can carry at one time: width 4 wires Answer: $1111=2^{4}-1=15$ width 6 wires Answer: $111111=2^{6}-1=63$ width 10 wires Answer: $1111111111=2^{10}-1=1023$ How many addresses can the following width addresses buses address: width 4 wires Answer: $1111=2^{4}=16$ width 5 wires Answer: $11111=2^{5}=32$ width 8 wires Answer: $11111111=2^{8}=256$ An address bus that can address a maximum of 2GB memory is 31 wires in width. How many wires would it need if it were to address a maximum of 4GB of memory? Answer: 32 as $2^{32}=4294967296$ bytes or 4GB of memory But you don't have to be really good at maths to answer this. 4GB is twice 2GB and we know that 2^x is half the size of 2^x+1.

Peripherals

Input/Output devices are used by the system to get information in and out, as they are not internal but are connected to the CPU, we refer to them as peripherals (your hands are peripheral to your torso). We'll cover the specific ones you need to learn a little later, but for the moment you need to know the fundamental difference:

• Input Devices - used to get information into the system. E.g. Keyboard
• Output Devices - used to send information out of the system. E.g. Visual Display Unit (VDU)

If you look at the Von Neumann Architecture notice that it doesn't mention Keyboard or display, this is a very smart move as you don't want to force every computer to have a keyboard (think about a games console, there is no keyboard on that) or a VDU (some computer such as MP3 players don't have a screen). However, some computer architecture does include specific I/O controllers:

I/O controllers

An I/O controller is an electronic circuit that connects to a system bus and an I/O device; it provides the correct voltages and currents for the system bus and the I/O device. Examples would include:

• keyboard controller, attached to a keyboard
• disk controller for a Hard Disk (Hard Disks are not main memory!)
• video display controller, attaching a video display unit (monitor)

I/O ports

I/O ports is a complementary method of performing input/output between the CPU and peripheral devices in a computer. This allows I/O devices to be connected to the CPU without having to have specialist hardware for each one. Think about the USB port on your computer, you can connect Keyboards, Mice, Game pads, Cameras, Phones, etc. and they all connect using the same port.

Secondary storage

Main memory can be very expensive and you often require storing data that you won't use constantly. Think about a computer game that you haven't played for a couple of months. The last thing you want to do is to store this code in main memory taking up all that precious and expensive space. To get past this issue we use secondary storage. This is normally inexpensive data storage sitting external to the CPU, connected through an I/O controller, that we can use as and when we need. Secondary Storage will store data permanently, without the need for the electricity to remain always on (Think about a USB key, it doesn't need to be plugged in to keep its data). So taking the game example again, we only load the game into main memory (maybe from a DVD or hard disk), as and when we need it. Examples of secondary storage include:

• Hard Disk drive
• USB thumb drives
• CD-ROM / DVD / Blu-ray
• Tape drives

A hard disk drive with protective cover removed.

Exercise: I/O and Peripherals Name 2 input peripherals: Answer: Keyboard Mouse Scanner Camera Microphone Games pad Name 2 output peripherals: Answer: Speakers Printer Visual Display Unit Name two ways to connect peripherals to a CPU: Answer: I/O controller I/O ports Name 2 secondary storage devices: Answer: Hard Disk USB thumb stick CD-ROM / DVD / Blu-Ray Name 2 I/O controllers Answer: Hard Disk controller Keyboard controller Visual Display Unit Controller

Addressable memory

A computer must be able to access main memory for reading and writing, they do this by using addressable memory. Main memory is a little like a set of school lockers, each with a different number. Each locker contains a block of data and if you fill up one locker you can use the next locker to expand into.

Looking at the example above you can see locker '0' contains '8975', whilst lockers 1 to 6 contain the sentence "The Cat sat on the dog!". Locker '7' is empty, locker '8' contains a boolean value and locker '9' contains the number 48. As you can see if we only used one character for the locker number then we could only ever have 10 lockers. If you limit the number of addresses you can use then you limit the amount of memory you can talk to. If you have a small address bus then you won't be able to have much main memory.

The way that data is stored in a computer is very similar:

Stored program concept

stored program concept - a program must be in main memory in order for it to be executed. The instructions are fetched, decoded and executed one at a time

Building on the Von Neumann architecture we get the idea of how the stored program concept works. If you have ever loaded a game on a console you might notice that:

1. you need to insert a disc
2. the disc spins
3. the game says loading
4. the game plays

This is the stored program concept in motion! Let's take apart what is happening:

1. You insert an optical disk (secondary storage) with the code on
2. The code is loaded into main memory
3. The processor fetches, decodes and executes instructions from main memory to play game

Exercise: Characteristics of a processor How many different addresses can a 8 line address bus address? Answer: $2^{8}=256$ How does the address bus affect main memory? Answer: If you have a small address bus then you will be limited in the number of addresses you can talk to and therefore how much main memory you can directly address. How wide would the address bus have to be to talk to 1024 addresses? Answer: 10 lines wide since $2^{10}=1024$ What is wrong with using a 9 bit address bus but having 700 memory locations in main memory? Answer: We can only address $2^{9}=512$ different locations. It wouldn't be able to talk to address locations $513-700$. Define the stored program concept: Answer: A program must be (resident) in main memory in order for it to be executed. The instructions are fetched from main memory, then decoded and executed in the CPU.

Structure and role of the processor

A processor (CPU) has several core components that work together to perform calculations. You need to know each of these and how they interact:

Arithmetic logic unit

A simple example of an arithmetic logic unit (2-bit ALU) that does AND, OR, XOR, and addition

The Arithmetic Logic Unit or the ALU is a digital circuit that performs arithmetic and logical operations. Where arithmetic operations include things such as ADD and SUBTRACT and the logical operations include things such as AND, OR, NOT.

The ALU is a fundamental building block in the central processing unit (CPU) of a computer and without it the computer wouldn't be able to calculate anything! Some examples of assembly code instructions that would use the ALU are as follows (not all processors will have all these instructions):

ADD ;add one number to another number
SUB ;subtract one number to another number
INC ;increment a number by 1
DEC ;decrements a number by 1
MUL ;multiply numbers together
OR  ;boolean algebra function
AND ;boolean algebra function
NOT ;boolean algebra function
XOR ;boolean algebra function
JNZ ;jump to another section of code if a number is not zero (used for loops and ifs)
JZ  ;jump to another section of code if a number is zero (used for loops and ifs)

Control unit

The control unit sits inside the CPU and coordinates the input and output devices of a computer system. It coordinates the fetching of program code from main memory to the CPU and directs the operation of the other processor components by providing timing and control signals.

Clock

Processor clock - A timing device connected to the processor that synchronises when the fetch, decode execute cycle runs

Your computer might contain several clocks that each regulate different things. The clock we are going to look at here will keep the processor in line. It will send the processor a signal at regular times telling it to start the fetch decode execute routine.

Lights flash at frequency f = 0.5 Hz (Hz = hertz), 1.0 Hz and 2.0 Hz, where $x$ Hz means $x$ flashes per second.

Clock speed - The number of cycles that are performed by the CPU per second

Clock speed is measured in Hertz, which means 'per second'. You have probably heard of clock speeds such as 1 MHz, this means 1,000,000 cycles per second and potentially a million calculations. A computer of speed 3.4 GHz means it might be capable of processing 3,400,000,000 instructions per second! However it isn't as simple at that, as some processors can perform more than one calculation on each clock cycle, and processors from different manufacturers and using different architecture are often difficult to compare. (See the Megahertz myth). Also with the increase in multi-core processors such as the PS3 (7 cores) and the Xbox 360 (3 cores) there might be times where the clock might be ticking but there is nothing for the processor to calculate, the processor will then sit idle.

General purpose and dedicated registers

Registers - a small amount of fast storage which is part of the processor

For immediate calculations, using main memory is too slow. Imagine having to send a signal along the address bus and some data along the data bus when all you want to do is store the result of adding two numbers together. The distance between the processor and main memory, even though it might be a few centimetres, is far enough for the signal to take a significant time to get there. To get past this issue there are small amounts of memory stored inside the processor itself, these are called registers. Registers are incredibly fast pieces of memory that are used to store the results of arithmetic and logic calculations.

Different processors will have different sets of registers. A common register is the Accumulator (acc) which is a data register, where the user is able to directly address (talk to) it and use it to store any results they wish. Processors may also have other registers with particular purposes:

• General purpose register - allow users to use them as they wish
• Address registers - used for storing addresses
• Conditional registers - hold truth values for loop and selection

There are also 4 registers in particular that you need to know, we'll meet them in more detail in the next chapter:

• Program Counter (PC) - an incrementing counter that keeps track of the memory address of which instruction is to be executed next.
• Memory Address Register (MAR) - holds the address in memory of the next instruction to be executed
• Memory Buffer Register (MBR) - a two-way register that holds data fetched from memory (and ready for the CPU to process) or data waiting to be stored in memory
• Current Instruction register (CIR) - a temporary holding ground for the instruction that has just been fetched from memory

Exercise: Structure and role of the processor Give a description of the Arithemtic Logic Unit: Answer: The Arithmetic Logic Unit or the ALU is a digital circuit that performs arithmetic and logical operations. What does 3MHz mean: Answer: 3,000,000 clock cycles per second What does a processor clock do: Answer: Synchronises the operation of the processor What are registers: Answer: a small amount of fast storage which is part of the processor Name 3 registers used by the processor and explain what each does: Answer: Program Counter (PC) - an incrementing counter that keeps track of the memory address of which instruction is to be executed next... Memory Address Register (MAR) - holds the address in memory of the next instruction to be executed Memory Buffer Register (MBR) - a two-way register that holds data fetched from memory (and ready for the CPU to process) or data waiting to be stored in memory Current Instruction register (CIR) - a temporary holding ground for the instruction that has just been fetched from memory General purpose registers - Accumulator - Used to store results of calculations

Increasing performance

If we want to increase the performance of our computer, we can try several things

• Increasing the clock speed
• Adjusting word length
• Increasing bus widths

For each different methods we are going to look at these old games consoles to see how performance increase was achieved:

System	Year	Speed	Word size	Notes
NES	1983	1.79 MHz	8 bit
SNES	1990	3.58 MHz	16 bit
Nintendo 64	1996	93.75 MHz	64 bit
GameCube	2001	486 MHz	128 bit	cooling fan introduced

Clock speed

Clock speed - The number of cycles that are performed by the CPU per second

The most obvious way to increase the speed of a computer would be to increase the speed of the computer clock. With a faster clock speed the processor would be forced to perform more instructions per second.

Example: Clock Speed As you can see on the console table above, each successive console showed an increase in clock speed. A clock speed of 800 MHz is twice as fast as a clock speed of 400 MHz, meaning it should be able to calculate twice as many calculations in a given time.

But what is to stop us increasing the clock speed as much as we want? If you study Physics you might already know this, but the problem with increased clock speed is that an increased current will have to flow through the circuits. The more current that flows, the hotter things get. You might notice that a laptop will get hot or even your mobile phone when you are doing something processor intensive like playing a game. The faster the clock speed, the hotter the processor runs. To counter this computer scientists have come up with smarter chip designs and introduced heat sinks, fans, and even liquid cooling into computers. If a processor runs too hot it can burn out!

NES processor	Heat sink	CPU fan	Water cooling
No need for fans or heat sinks	Draws the heat away from the processor, which sits beneath	I love the CPU so much, I'm a real CPU fan	Metal contacts are placed on the cpu drawing heat away, water then passes over these contacts to draw heat away

Word size

Word size - The number of bits of information that a processor can process at one time

Another way to increase the performance of a computer is to increase the word size. This means increasing the number of bits a computer can process at one time. As you can see from our console table, increasing word size was a big part of creating faster consoles, they even named a console the N64 to boast about its word size. With a larger word, computers can handle larger or more precise calculations and do more complicated things. Modern computer mostly have 32 or 64 bit word sizes, with specialist hardware such as games consoles being able to handle up to 128 bit words.

Example: Word Length Compsognathus Imagine that we were only able to use words of length 6 letters or less and we wanted to describe the Compsognathus dinosaur to someone. We might try the following: “ A small living thing, with little claws and tough skin. It lived over ten plus five, times ten, plus seven, times ten, times ten, times ten, times ten, times ten, times ten years ago. ” If we were able to use more letters per word (have a larger word size), then we could achieve more in fewer words. “ A small dinosaur with little claws and tough skin. It lived over one hundred and fifty-seven million years ago. ” However, to understand the longer words you would have to know what dinosaur and million meant, maybe stopping for a brief moment to remember. In computing terminology, you would have to have more complicated hardware and using lots of little words could be faster than processing larger ones.

Bus size

Bus Size - The number of bits of information a bus can carry at one time (the number of wires making up a bus)

Now that we understand what word size is. Imagine that you have a processor able to understand 32 bit words at a single time. This is pretty standard. But what happens if the bus sending the words from memory to the processor was only 8 bits wide? We'd get a bottle neck. It would involve four chunks of data to be sent along the Data Bus before we had a word for the processor to execute. In other words, to increase performance we must also increase the bus size to avoid bottle necks:

Example: Bus Size Imagine our friend can understand words of 28 bit length and we are sending the word: antidisestablishmentarianism to them. If the link between us (the bus), say a chat window on a website, only allowed for 4 letters at a time (the bus width). We'd have to send the following: anti dise stab lish ment aria nism Requiring seven data sends before our friend is ready to process the word we sent them. If we were able to send more letters at once, through a larger bus width, then our friend wouldn't have to wait around to receive all the data.

Exercise: Increasing Processor Performance Name three ways to increase Processor performance: Answer: Increase clock speed Adjust word length Increase bus width What draw back might increasing clock speed bring? Answer: Processor might need extra cooling hardware to stop it over heating What is a benefit of increasing word length? Answer: Computers can perform more complex instructions in one go, dealing with larger numbers and greater number accuracy How might bus width impact on the speed of a computer? Answer: If the bus width is smaller than the word size, then the CPU will have to wait around whilst the bus delivers data and instructions to it.

How does it all fit together?

A very common exam question is to name the components of a computer architecture diagram. Now we have met the processor, buses and various other computer components we can start to answer questions like the following:

Example: Name the component Match the following components to the numbers on the diagram: Processor, Data bus, Control Bus, Main memory, Keyboard, Secondary storage, Address bus, Clock, Monitor, VDU controller, disk controller, keyboard controller Don't worry about the size of this problem, we are going to tackle it bit by bit. the first step is to remember the differences between each of the components: Processor - connected to other devices using buses Data bus - bi-directional connection between devices Main memory - internal to the computer and linked through the buses Keyboard - external to the computer, an input device Secondary storage - external device, an input and output device Address bus - uni-directional connection between devices Clock - regulates the processor Monitor - external output device VDU controller - connects system to external monitor Disk controller - connects system to external secondary storage Keyboard controller - connects system to external keyboard device Control Bus - A bi-directional bus used to control signals between the components Now we have remembered what each device does, can you label them all? Answer: Clock Processor Main memory keyboard controller VDU controller Disk controller Data bus (or Control bus) Control bus (or Data bus) Address bus Keyboard Monitor Secondary storage

Exercise: System Diagrams For the following diagram where applicable add single or multi directional connections between devices and buses Answer:

Machine code

Machine code - simple instructions that are executed directly by the CPU

As we should hopefully already know, computers can only understand binary, 1s and 0s. We are now going to look at the simplest instructions that we can give a computer. This is called machine code.

Machine code allows computers to perform the most basic, but essential tasks. For this section we are going to use the Accumulator (you met this register earlier) to store the intermediate results of all our calculations. Amongst others, the following instructions are important for all processors:

• LDA - Loads the contents of the memory address or integer into the accumulator
• ADD - Adds the contents of the memory address or integer to the accumulator
• STO - Stores the contents of the accumulator into the addressed location

Assembly code is the easy to read interpretation of machine code, there is a one to one matching, one line of assembly equals one line of machine code:

Machine code	Assembly code
000000110101 =	Store 53

Let's take a look at a quick coding example using assembly code.

LDA #23 ;loads the number 23 into the accumulator
ADD #42 ;adds the number 42 to the contents of the accumulator = 65
STO 34  ;save the accumulator result to the memory address 34

The code above is the equivalent of saying x = 23 + 42 in VB.NET.

• the above example is not entirely factually correct as the variable "x" has never been created(defined)in the Assembly code example.

Instruction set

Instruction set - the range of instructions that a CPU can execute

There are many different instructions that we can use in machine code, you have already met three (LDA, ADD, STO), but some processors will be capable of understanding many more. The selection of instructions that a machine can understand is called the instruction set. Below are a list of some other instructions that might be used:

ADD ;add one number to another number
SUB ;subtract one number from another number
INC ;increment a number by 1
DEC ;decrement a number by 1
MUL ;multiply numbers together
OR  ;boolean algebra function
AND ;boolean algebra function
NOT ;boolean algebra function
XOR ;boolean algebra function
JNZ ;jump to another section of code if a number is not zero (used for loops and ifs)
JZ  ;jump to another section of code if a number is zero (used for loops and ifs)
JMP ;jump to another section of code (used for loops and ifs)

Let us look at a more complex example of assembly code instructions:

LDA #12 ;loads the number 12 into the accumulator
MUL #2  ;multiplies the accumulator by 2 = 24
SUB #6  ;take 6 away from the accumulator = 18
JNZ 6   ;if the accumulator <> 0 then goto line 6
SUB #5  ;take 5 away from the accumulator (this line isn't executed!)
STO 34  ;saves the accumulator result (18) to the memory address 34

You'll notice that in general instructions have two main parts:

• opcode - instruction name
• operand - data or address

The breakdown of a machine instruction

Depending on the word size, there will be different numbers of bits available for the opcode and for the operand. There are two different philosophies at play, with some processors choosing to have lots of different instructions and a smaller operand (Intel, AMD) and others choosing to have less instructions and more space for the operand (ARM).

• CISC - Complex Instruction Set Computer - more instructions allowing for complex tasks to be executed, but range and precision of the operand is reduced. Some instruction may be of variable length, for example taking extra words (or bytes) to address full memory addresses, load full data values or just expand the available instructions.
• RISC - Reduced Instruction Set Computer - less instructions allowing for larger and higher precision operands.

Exercise: Instruction sets What is the instruction set: Answer: the range of instructions that a CPU can execute Name and explain the two parts that make up an machine code instruction: Answer: opcode - the command to be executed operand - the data or address being worked upon For a word with 4 bits for an opcode and 6 bits for an operand How many different instructions could I fit into the instruction set? What is the largest number that I could use as data? Answer: Number of instructions: $2^{4}=16$ largest operand: $2^{6}-1=63$ For a 16 bit word with 6 bits for an opcode How many different instructions could I fit into the instruction set? What is the largest number that I could use as data? Answer: Number of instructions: $2^{6}=64$ largest operand: $2^{10}-1=1023$ Why might a manufacturer choose to increase the instruction set size? Answer: so that they can increase the number of discrete instructions that can be executed What might be the problem with increasing the space taken up by the opcode? Answer: less space for the operand, meaning reduced range and precision in data be processed in a single instruction Give two benefits for increasing the word size of a processor? Answer: more space available to increase the instruction set size greater range and precision available in the operand

Addressing modes

You might notice that some instructions use a # and others don't, you might even have an inkling as to what the difference is. Well here is the truth:

        # = number
[no hash] = address

Let's take a look at a quick example:

Assembly code	Main memory start	Main memory end
LOAD #10 ADD #12 STORE 12	Address Contents 10 9 11 2 12 7 13 10 14 12	Address Contents 10 9 11 2 12 22 13 10 14 12
This code loads the number 10 into the accumulator, then adds the number 12, it then stores the result 22 into memory location 12.

Let's take a look at doing this without the hashes:

Assembly code	Main memory start	Main memory end
LOAD 10 ADD 12 STORE 12	Address Contents 10 9 11 2 12 7 13 10 14 12	Address Contents 10 9 11 2 12 16 13 10 14 12
This code loads the value stored in memory location 10 into the accumulator (9), then adds the value stored in memory location 12 (7), it then stores the result into memory location 12 (9 + 7 = 16).

There are many types of addressing modes. But we only need to know 3, they are:

Addressing Mode	Symbol	Example	Description
Memory Location		LOAD 15	15 is treated as an address
Integer	#	LOAD #15	15 is treated as a number
Nothing		HALT	Some instruction don't need operands such as halting a program

Exercise: Assembly code and Addressing modes For the following memory space, what would it look like after executing the assembly code below: Address Contents 10 1 11 4 12 4 13 100 14 5 LOAD 14 ADD #12 STORE 12 Answer: Address Contents 10 1 11 4 12 17 13 100 14 5 For the following memory space, what would it look like after executing the assembly code below: Address Contents 211 6 212 3 213 78 214 21 LOAD #100 STORE 213 LOAD 214 ADD 213 STORE 214 Answer: Address Contents 211 6 212 3 213 100 214 121 For the following memory space, what would it look like after executing the assembly code below: Address Contents 99 6 100 6 101 8 102 9 LOAD 100 ADD 101 DIV #7 STORE 102 Answer: Address Contents 99 6 100 6 101 8 102 2 Write some assembly code to do the following: 34 + 35 and store in memory location 100 Answer: LOAD #34 ADD #35 STORE 100 Write some assembly code to do the following: 4 + (100 / 2) and store in memory location 100 Answer: LOAD #100 DIV #2 ADD #4 STORE 100 List and give examples of three addressing modes: Answer: Memory Locations - LOAD 15 Integers (Whole Numbers) - LOAD #15 Nothing - HALT

Machine code and instruction sets

There is no set binary bit pattern for different opcodes in an instruction set. Different processors will use different patterns, but sometimes it might be the case that you are given certain bit patterns that represent different opcodes. You will then be asked to write machine code instructions using them. Below is an example of bit patterns that might represent certain instructions.

Machine code	Instruction	Addressing mode	Hexadecimal	Example
0000	STORE	Address	0	STO 12
0001	LOAD	Number	1	LDA #12
0010	LOAD	Address	2	LDA 12
0100	ADD	Number	4	ADD #12
1000	ADD	Address	8	ADD 12
1111	HALT	None	F	HALT

Exercise: Machine Code Using the table above provide machine code to do the following: LOAD 12 ADD #6 Answer: 0010 00001100 0100 00000110 Using the table above give the assembly code for the following machine code: 0001 00000111 0100 00001001 0000 00011110 Answer: LOAD #7 ADD #9 STORE 30 Explain what the above code does: Answer: loads the integer 7 into the Accumulator, adds the integer 9 to the Accumulator, stores the result, 16, in memory location 30 Convert the following machine code into hexadecimal: 0001 00111011 0100 00001001 0000 00011110 1111 00000000 Answer: 1 3 B 4 0 9 0 1 E F 0 0 If we were lacking Assembly code, why might we want to convert machine code into Hexadecimal? Answer: It makes it easier for humans to read and understand.

Extension: Little Man Computer If you would like to play around with Assembly language a great place to start is the Little man computer. You can find a Java applet and some examples at the York University website or a javascript version created by Peter Higginson

The Fetch–Execute cycle and the role of registers within it

The Fetch-Decode-Execute cycle of a computer is the process by which a computer:

1. fetches a program instruction from its memory,
2. determines what the instruction wants to do,
3. and carries out those actions.

This cycle is repeated continuously by the central processing unit (CPU), from bootup to when the computer is shut down. In modern computers this means completing the cycle billions of times a second! Without it nothing would be able to be calculated.

Registers/circuits involved

The circuits used in the CPU during the cycle are:

• Program Counter (PC) - an incrementing counter that keeps track of the memory address of which instruction is to be executed next...
• Memory Address Register (MAR) - the address in main memory that is currently being read or written
• Memory Buffer Register (MBR) or Memory Data Register (MDR) - a register that holds data fetched from memory (and ready for the CPU to process) or data waiting to be stored in memory. This register can send or receive data via the Data Bus (2-way register).
• Current Instruction register (CIR) - a temporary holding ground for the instruction that has just been fetched from memory
• Control Unit (CU) - decodes the program instruction in the CIR, selecting machine resources such as a data source register and a particular arithmetic operation, and coordinates activation of those resources
• Arithmetic logic unit (ALU) - performs mathematical and logical operations

Register notation

To describe the cycle we can use register notation. This is a very simple way of noting all the steps involved. In all cases where you see brackets e.g. [PC], this means that the contents of the thing inside the brackets is loaded. In the case of the first line, the contents of the program counter is loaded into the Memory Address Register.

$MAR\gets [PC]$

$MBR\gets [Memory]_{MARaddress};PC\gets [PC]+1$ (Increment the PC for next cycle at the same time)

$CIR\gets [MBR]$

$[CIR]$ decoded then executed

Detailed description of Fetch-Decode-Execute Cycle

To better understand what is going on at each stage we'll now look at a detailed description:

The contents of the Program Counter, the address of the next instruction to be executed, is placed into the Memory Address Register

The address is sent from the MAR along the address bus to the Main Memory. The instruction at that address is found and returned along the data bus to the Memory Buffer Register. At the same time the contents of the Program Counter is increased by 1, to reference the next instruction to be executed.

The MBR loads the Current Instruction Register with the instruction to be executed.

The instruction is decoded and executed using the ALU if necessary.

The Cycle starts again!

Exercise: Fetch Execute Cycle Name 3 registers involved in the Fetch Execute Cycle and describe what each does: Answer: Program Counter (PC) - an incrementing counter that keeps track of the memory address of which instruction is to be executed next... Memory Address Register (MAR) - holds the address in memory of the next instruction to be executed Memory Buffer Register (MBR) - a two-way register that holds data fetched from memory (and ready for the CPU to process) or data waiting to be stored in memory Current Instruction register (CIR) - a temporary holding ground for the instruction that has just been fetched from memory Describe the Fetch Execute Cycle using register notation: Answer: $MAR\gets [PC]$ $MBR\gets [Memory]_{MARaddress};PC\gets [PC]+1$ $CIR\gets [MBR]$ $CIRexecutes$ Complete the following diagrams showing each step of the fetch decode execute cycle: Answer: Answer: Answer: Answer:

Hardware Devices

Input and Output Devices Know the main characteristics, purpose and suitability of contemporary devices (see the Teacher Resource Bank), and understand their principles of operation, including methods of error checking (check digit).

Secondary Storage Devices Explain the need for secondary storage within a computer system, know the main characteristics, purpose and suitability, and understand the principles of operation of contemporary devices (see the Teacher Resource Bank). Compare the capacity and speed of access of various media and make a judgement about their suitability for different applications

Input and output devices

You should already have met the internal components of the computer and the peripherals, that sit outside. We are now going to look at two different categories of peripherals. Those that input data into a computer, and those that output data from the computer.

Computers work along the lines shown above, they receive inputs (instructions etc.), they process the input working out what to do with it, then they output some form of result

How do we tell what is an input and what is an output device? Think about it from the computer's perspective. If a device is putting data into the computer in the form of text, sound, images, button presses etc. then it is an input device, if the device is outputting things from the computer such as sound, movement, printing, images etc., then it is an output device. It really is that easy to tell the difference, but be warned, some devices can be both input and output!

Let's take a look at two examples:

Example: Telling the difference between input and output devices An LG LCD monitor When you are using the monitor it displays things that you are doing, such as moving windows and clicking on website links. At no point do you click on the screen or put anything into the monitor. The only thing it does is output information, therefore it is an output device. Easy! An optical mouse A mouse is used to move a little cursor around the screen, clicking and dragging as you go. if you let go of the mouse, the cursor will stop. The computer is relying on you to move the mouse, the mouse won't move on its own! Therefore it is an input device.

Exercise: Input and output devices Note whether the following devices are input or output devices (or both!) Printer Mouse Keyboard Monitor Web cam Scanner Graphics tablet Joypad/Controller Speakers Answer: Printer - output Mouse - input Keyboard - input Monitor - output Web cam - input Scanner - input Graphics tablet - input or output (if there is a screen on it) Joypad/Conroller - input (output as well if it vibrates!) Speakers - output

Input devices

Pay special attention to devices with an orange background, you need to be able to describe exactly how they work!

Input Device - Devices that send data or instructions into a computer

Mouse

A mouse is a pointing device used on the screen of a computer. Enables the user to execute commands or issue instructions to the computer by controlling a pointer on the screen.

Keyboard

The keyboard is one of the most popular ways of inputting data information and instructions into a computer. The basic mechanical keyboard relies on springed keys being pressed down to complete an electrical circuit. This circuit then transmits a binary signal (commonly using ASCII) to the computer to represent the key pressed.

Stylised cross-section of a Chiclet keyboard (there are other technologies out there used to make keyboards). The bottom right hand button has been pressed, completing the circuit shown in red.

There are many different keyboard layouts, with differences between languages and countries. The most popular layout is the QWERTY keyboard. Other layouts include:

• AZERTY - for countries such as France and Belgium
• QWERTZ - for countries such as Germany and Austria
• Arabic - different values to most keys
• Ukrainian
• Chinese - laid over a QWERTY keyboard

There are variations QWERTY keyboard with the UK and the USA having very slight differences in layout. There also variations in English language keyboards such as the Dvorak layout, which followers claim to be superior to QWERTY.

QWERTY keyboard

Voice recognition

Microphone connected to software that converts human speech into commands or text.

Pros

Natural interface with a computer allowing for new users to execute commands without having to learn complex command set

Cons

Speech recognition might not recognise the difference between similar words i.e. "their" and "they're" or be able to understand regional accents

microphone

Digital camera

1. Light is focused through the lens onto the image sensor at the back of the camera
2. The image sensor is made up of an array of Red, Green and Blue photosensors, called a Bayer filter. Each sensor will only record values for that particular colour.

• 
  This image
• 
  went through this
• 
  like so

And became these:

• 
  Red
• 
  Green
• 
  Blue

3. The different colour arrays are combined to form an image and makes this:

• 
  Combined image
• 
  Applying an algorithm to merge cells
• 
  Notice it is not quite the same as this Original

4. Once the RGB values have been captured, they can then be stored digitally using SD or compact flash cards. Save formats include JPEG or TIFF.

Pros

You can preview images taken without having to get them developed

You can apply filters and images to add special effects

Cons

Some people argue that the quality of photos taken using the traditional film medium is better

Camara2sig

Barcode reader

Used in supermarkets,warehouses,libraries keeping track of produce etc. They allow for quick reading of product details so that prices and information can be retrieved and/or stock levels updated. However the amount of data stored in a barcode is very limited

barcodes are very common

1. A laser is directed towards the barcode, scanning across it and the reflected light is captured by the reader
2. The intensity of light reflected back is read by a sensor in the bar code reader
   • High intensity = white bar
   • Low intensity = black bar
3. The pattern received is translated into a code which gives the identity of the barcode being scanned
4. This code is checked against a product database and the product details displayed

Plessey code is one way to encode barcodes

To make sure that the number you have received is correct barcodes employ check digits. Read on to find out more

Pros

Cheap to produce as all you need to do is print a black and white image

Quick to read, and with multi-direction scanners, can be read from different angles

Cons

Only a limited amount of data can be stored

barcode reader

Optical mark reader

Used in things like multi choice question papers. The student would be given a selection of answers and then mark the ones they thought correct with a pen or pencil. When finished, the forms would be fed into a machine that would look for black marks. The position of these marks correspond to answers and the form could be marked at some speed.They can also be used for student registration

multi choice exam paper ready for OMR

Optical character reader

Used in scanning printed or written text into a digital format. Used by Amazon and Google to scan books.

Sketch of a typical manual book scanner

Magnetic stripe reader

Used to read data from bank cards and access cards. Data is stored in the magnetic, generally black, strip on the back of these cards

An example of the reverse side of a typical credit card.: Green circle #1 labels the Magnetic stripe

Smart card reader

Used in bank cards, often known as part of 'chip and pin'. More secure than Magnetic stripes though more expensive to produce.

RFID reader

Used to read data without physical contact. Examples include the London Oyster Card System. Where the card has a Radio Frequency Identification(RFID) chip.

1. The card is then placed above a reader and the magnetic field produced by the reader creates a current in the card's circuitry (no physical contact is required)

   

2. This current powers a small radio transmitter that transmits a radio wave with the details about the card to the reader

   

3. If the details of the card are legitimate (checked on database) then it lets the person through the gate

   

Pros

Can be read without physical contact (health and safety concerns)

Fast way to pay for things

Cons

Thieves could read your card remotely, stealing your details

Having multiple RFID cards together, means that they can interfere with each other and none of them can be read

A damaged card, revealing the microchip in the lower right corner, and the aerial running around the edge of the card.

Oyster card readers on London Underground ticket barriers at Canary Wharf.

Touch sensitive

More and more devices are relying on touch technologies.

Touch-sensitive screen

1. Each of the four corners of a screen emits a uniform electric field which covers the screen
2. When you place your finger on or near the screen it disrupts this field and draws current
3. Measuring the amount of current pulled from each corner you can triangulate the position of the finger

Pros

Natural, intuitive interface with devices

The ability to remap screen functions to suit the task (for example bringing up a keyboard when necessary

Cons

Cold weather can affect the functioning of touch screens

Won't work through standard gloves, as this stops your fingers conducting electricity

Graphics tablet

Used in the design and architectural industries. This allows for people to draw on the tablet in a natural way (as they would with a pencil and paper) and for their drawing to appear on the computer.

Wacom Pen-tablet

Exercise: Inputs What input device might a multi-choice questionnaire writer use to input completed forms into a computer. Why? Answer: OMR - optical mark recognition software, as it will allow for input of papers with marks on them Describe the functioning of a bar-code reader: Answer: A light or laser is directed towards the barcode, scanning across it and the reflected light is captured by the reader The intensity of light reflected back is read by a sensor in the bar code reader High intensity = white bar Low intensity = black bar The pattern received is translated into a code which gives the identity of the barcode being scanned Describe the functioning of digital camera: Answer: Light is focused through the lens onto the image sensor at the back of the camera The image sensor is made up of an array of Red, Green and Blue photosensors, called a Bayer filter. Each sensor will only record values for that particular colour. The different colour arrays are combined to form an image The image is stored as a TIFF or a JPEG Why might it beneficial for professional photographer to use a digital camera instead of a film camera? Answer: Digital images allow you to edit and manipulate them, adding software filters. Digital cameras allow you to take pictures and preview the results, discarding those that you don't want. Film cameras wouldn't show you the image until you had developed it, and such a process is very expensive Give two benefits of using RFID cards to pay for produce over using hard cash. What is a draw back? Answer: Can be read without physical contact (health and safety concerns) Fast way to pay for things Thieves could read your card remotely, stealing your details, without you even knowing it Give a benefit of having a touch screen phone over a phone with a hardware keyboard. Why might some people prefer a hardware keyboard? Answer: A touch screen phone would allow you to have a keyboard on the screen that could be hidden when not needed. Meaning the screen space can be used for other purposes Some people might prefer the hardware keyboard as they like to feel the response of keys being pressed and improve their typing (advances are being made in haptic technology to bring this to touch screens) Describe the functioning of a touch sensitive screen: Answer: Each of the four corners of a screen emits a uniform electric field which covers the screen When you place your finger on or near the screen it disrupts this field and draws current Measuring the amount of current pulled from each corner you can triangulate the position of the finger

Scanners

Several of the scanners featured here record biological (bio) measurements (metrics) about human beings. Physical data such as finger prints are unique to each person.

Flatbed Scanner

Flat bed scanners are used to convert images and text into a digital format.

The main components of a flatbed scanner

1. Place the object you want to scan on the glass pane, face down
2. the light moves to the start of the document and illuminates a slice
3. The slice is reflected into the CCD (an array of optical sensors) where its image is stored as digital data
4. the light and mirror move down to the next slice and so on
5. once all the slices are completed they are put together into a digital image

Flatbed Scanner

Fingerprint Scanner

A finger print

The ridges and troughs on a person's finger and toes are unique to that person. Using a scanner a finger print pattern can be recorded and compared to others on a database, allowing a computer to match finger prints from crimes to a suspect, or to allow people into restricted areas.

Fingerprint scanner in Tel Aviv

Retina Scanner

The blood vessels in a normal human retina form a unique pattern for each person

Retina scanners are used to record the pattern of blood vessels at the back of someone's eye. As everyone has different pattern of vessels, retina scanners can be used to uniquely identify people.

Iris Scanner

Iris patterns can be different colours and form a unique identifier for each person

By taking a picture of the blood vessels and colouring of someone's eye, we can get a unique pattern that can be used to identify individuals. People might try and circumvent this by using contact lenses

A U.S. Marine Corps Sergeant uses an iris scanner to positively identify a member of the Baghdadi city council prior to a meeting with local tribal leaders, sheiks, community leaders and U.S. service members.

Exercise: Scanners Explain how a flat bed scanner works: Answer: Place the object you want to scan on the glass plane, face down the light moves to the start of the document and illuminates a slice The slice is reflected into the CCD where it's image is stored the light and mirror move down to the next slice and so on once all the slices are completed the image is assembled using them Give two examples of devices that collect biometric data: Answer: Retina scanners Finger print scanners Iris recognition

Check digits

Check Digit - an additional digit added to a data string and depending on that string, used for checking that the string has been sent correctly

With input devices we have a lot of data being sent into the computer, with image capture devices we could be talking about billions of ones and zeroes. How can we make sure that they all get from the input device to the computer safely, without becoming corrupted? There are many error checking methods out there and you will cover some of them in more detail in Unit 1, however, for the moment we will learn a little about check digits:

An example of using check digits (The exam will not expect you to know this technique) is the final digit of a Universal Product Code computed as follows:

1. Add the digits (up to but not including the check digit) in the odd-numbered positions (first, third, fifth, etc.) together and multiply by three.
2. Add the digits (up to but not including the check digit) in the even-numbered positions (second, fourth, sixth, etc.) to the result.
3. Take the remainder of the result divided by 10 (modulo operation) and subtract this from 10 to derive the check digit.

Example: Check Digits For instance, the UPC-A barcode for a box of tissues is "036000241457". The last digit is the check digit "7", and if the other numbers are correct then the check digit calculation must produce 7. Add the odd number digits: 0+6+0+2+1+5 = 14 Multiply the result by 3: 14 * 3 = 42 Add the even number digits: 3+0+0+4+4 = 11 Add the two results together: 42 + 11 = 53 To calculate the check digit, take the remainder of (53 / 10), which is also known as (53 modulo 10), and subtract from 10. Therefore, the check digit value is 7. Correct!

Exercise: Check digits Calculate the check digit for the following food item "01010101010": Answer: Add the odd number digits: $0+0+0+0+0+0=0$ Multiply the result by 3: $0*3=0$ Add the even number digits: $1+1+1+1+1=5$ Add the two results together: $0+5=5$ To calculate the check digit, take the remainder of (5 / 10), which is also known as (5 modulo 10), and subtract from 10 i.e. (10 - 5 modulo 10) = 5. Therefore, the check digit value is 5. If the remainder is 0, subtracting from 10 would give 10. In that case, use 0 as the check digit. Did the following barcode scan correctly: "01234567890 6"? Answer: Add the odd number digits: 0+2+4+6+8+0 = 20 Multiply the result by 3: 20 * 3 = 60 Add the even number digits: 1+3+5+7+9 = 25 Add the two results together: 60 + 25 = 85 To calculate the check digit, take the remainder of (85 / 10), which is also known as (85 modulo 10), and subtract from 10 i.e. (10 - 85 modulo 10) = 5. Therefore, the check digit value is 5. If the remainder is 0, subtracting from 10 would give 10. In that case, use 0 as the check digit. Therefore the check digit given, 6, shows that the code is incorrect. Why do we use check digits? Answer: We use check digits to make sure that data received has been received correctly

Output devices

Pay special attention to devices with an orange background, you need to be able to describe exactly how they work!

Output Devices - Device that a computer sends data or instructions to

Visual display units

Cathode-Ray Tube

A cathode ray tube is a Visual Display Unit. You might know them as the old 'fat' televisions and monitors that have mostly been superseded by LCD screens.

Pros

the image on a CRT can be viewed from a wide range of angles

Cons

Heavy, large and power hungry compared to LCD screens

Cutaway rendering of a color CRT:
1. Three Electron guns (for red, green, and blue phosphor dots)
2. Electron beams
3. Focusing coils
4. Deflection coils
5. Anode connection
6. Mask for separating beams for red, green, and blue part of displayed image
7. Phosphor layer with red, green, and blue zones
8. Close-up of the phosphor-coated inner side of the screen

Flat Screen (LCD)

A 19-inch LG flat-panel LCD monitor.

LCDs are Visual Display Units. Most modern Televisions and Monitors are liquid crystal displays (LCD). An LCD screen is made up by an array of pixels or picture elements, each pixel contains Red Green and Blue and there is a back light that shines through the pixel, creating an image

To change the image displayed on the screen will require different combinations of Red, Green and Blue pixels. To do this the pixels are sandwiched between two polarized grills.

These grills are controlled by an electric current and when current is applied, the grids go perpendicular to each other, blocking out all light from a particular colour.

Applying different current patterns to different pixels means that you can choose whether each pixel displays Red, Green or Blue, thus building an image:

Pros LCD screens have several benefits over traditional CRT screens:

Smaller and lighter than equivalent sized CRT

More energy efficient than CRT

Cons

viewing angles of LCD screens can be smaller than an equivalent CRT. This means the viewers can't see images from the side of the screen

Dead pixels can plague LCD Monitors, where the grills governing the colour of an individual pixel get stuck and fix that pixel to always displaying a certain colour or no colour at all

an example of a dead pixel

Plasma Screen

Plasma screens are Visual Display Units. They are generally more expensive than LCDs and CRTs, and offer similar performance to an LCD. They are power hungry and used mainly for large television sets

Exercise: Visual Display Units Explain how an LCD screen works: Answer: An LCD screen is made up by an array of pixels, each pixel contains Red Green and Blue and there is a back light that shines through the pixel, creating an image. The pixels are sandwiched between two polarized grills. These grills are controlled by an electric current and when current is applied, the grids go perpendicular to each other, blocking out all light from a particular colour. Applying different current patterns to different pixels means that you can choose whether each pixel displays Red, Green or Blue, thus building an image Give two benefits and one drawback of using a LCD screen over a CRT: Answer: Smaller and lighter than equivalent sized CRT More energy efficient than CRT dead pixels can effect the image Name 3 types of Visual display unit: Answer: LCD Plasma CRT

Sound output

Speech output might include speech synthesis, headphones or speakers

A pair of speakers for notebook computers, runs off USB

Electronic paper

Amazon Kindle using an e-paper display

Electronic paper is made up of tiny plastic balls that have different colours on each side (black and white). Applying an electrical current to the 'paper' flips the balls to make the pattern of a picture and an image is displayed. The image stays there until you apply another current. This is used in modern e-book readers such as the Amazon Kindle and in other devices such as phones

If you look closely you can see the 'ball's on the Kindle 3

Appearance of pixels

Pros

Images are easy to read in sunlight, unlike most electronic screens

You only need to use electricity to change the image, not maintain it, meaning batteries last longer than LCD screens. In some cases batteries may last weeks, whilst an LCD equivalent would only last a day or two

Cons

The refresh rate of screens is too slow to show moving images

Ghosting might occur, where the shadow of old images remains on the screen after you have refreshed

An e-ink screen showing the "ghost" of a prior image

Exercise: Electronic paper Give two benefits and one drawback for using electronic paper over an LCD screen: Answer: Images are easy to read in sunlight You only need to use electricity to change the image, not maintain it, meaning batteries last longer than LCD screens The refresh rate of screens is too slow to show moving images

Printers

There are several different types of Printers, the one's you need to know are below

Impact Printer

Impact printers rely on a forcible impact to transfer ink to the media, similar to the action of a typewriter. All but the dot matrix printer rely on the use of formed characters, letterforms that represent each of the characters that the printer was capable of printing. Impact printers varieties include, typewriter-derived printers, teletypewriter-derived printers, daisy wheel printers, dot matrix printers and line printers. Dot matrix printers remain in common use in businesses where multi-part forms are printed, such as car rental services, this allows several sheets of paper to be written to with one strike of the printer head, it also allows for carbon paper to be written to through sealed envelopes:

Dot matrix printers use a print head containing a line of pins. The number of pins can vary from 7 into the dozens. As the print head passes over the paper the pins impact on the ink ribbon forming characters on the paper line by line.

7 pin print head

Pros

Can print multi-part stationary

very cheap to run

Cons

unable to produce high definition images, you are limited to the number of pins available

slow when compared to laser

output from a dot-matrix printer, showing the individual rod strikes on the ribbon to make an image on the paper

Inkjet Printer

Inkjet heads:
Disposable head (left) and
Fixed head (right) with ink cartridge (middle)

Inkjets are examples of non-impact printer. They operate by propelling variably-sized droplets of liquid or molten material (ink) onto almost any sized page. They are the most common type of computer printer used by consumers.

1. The paper is fed into the printer
2. The print head contains one or more cartridges of ink of different colours (some only have black ink)
3. The print head moves from one side to another, each cartridge spraying tiny particles of ink onto the paper to form the correct pattern
4. After one line is finished the paper is fed through a little more, and the next line printed

Output from an inkjet printer showing the individual blobs of ink on the paper

Pros

Inkjet printers are cheaper than lasers

They can produce high quality images for photos etc

Cons

They are slower than lasers

Per page they are relatively expensive

Laser Printer

Lasers are examples of non-impact printers. A laser printer rapidly produces high quality text and graphics. They work in the following way:

1. The drum is given a negative charge
2. This charge is erased in the correct places by the laser to create the image using the photoelectric effect

3. The drum is coated in toner, a negatively charged fine dust, which is repelled by the charge on the drum. Only in the uncharged areas does the toner apply
4. The drum rolls over the paper and transfers the toner onto it(if your printing gets jammed the paper might have this dust on it which comes off on your hands)
5. The paper is then put through heated rollers which melts the toner and seals it to the paper, thus finishing the image.

Pros

Fast

Cheap to Produce large volumes of printing

Cons

Expensive hardware

Hp laserjet 4200

Plotter

Plotters were an alternate printing technology once common in engineering and architectural firms. Pen-based plotters rely on contact with the paper, but not impact, per se, and special purpose pens that are mechanically run over the paper to create text and images. They were particularly adept to printing vector graphics, though they have generally been replaced with wide-format conventional inkjet/laser printers.

1. Paper is placed in the plotter.
2. The plotter arm selects a pen of the correct colour
3. the arm then moves the pen to the area where printing needs to start.
4. the pen is lowered onto the paper and the arm moves it drawing a continuous image.
5. The pen raises and lowers depending on what needs to be drawn, the plotter can also select from a group of colour pens

(some plotters involve keeping the pens stationary and moving the paper instead)

Pros

cheap to run

can produce very precise technical drawings

Cons

there may be issues around the colour pens available, it is hard to combine colours as you would in an inkjet

slow

Plotter at work on a technical drawing

3D Printers

Many 3D printers work by heating up a filament of coloured plastic, fed from a spool. As the plastic cools it builds the model from the base up.

There are also 3D printers which work with resin, powder, or paper. There are medical applications which build prosthetics and even much larger printers which use concrete for building.

Exercise: Printers What printing device is best for printing thousands of leaflets to advertise a shop opening? Why? Answer: Laser printer: it can print incredibly fast it can print in colour toner doesn't run in the rain, meaning the leaflets won't be spoilt during delivery For a seven pin impact printer, what character would the following line codes output: 1,2,3,4,5,6,7 | 1,4 | 1,4 | 2,3 Answer: Describe how a laser printer works: Answer: Electrical charge version of the image is transferred to the drum Paper passes over the drum and the charge is transferred to the paper Toner, a fine dust, is attracted to the charge on the paper, making the image The paper is then put through heated rollers which then melts the toner and seals it to the paper, thus finishing the image. When might you want to use an impact printer over an inkjet printer? Answer: When you are printing multi-part stationary When might you want to use an inkjet printer over an impact printer? Answer: When you want detail and colour

Secondary storage devices

This section will be looking at the various forms of secondary storage devices (media). For each device you should be familiar with the following details:

• Seek time - The average time taken from requesting data to starting to read the requested data
• Capacity - The amount of data it is possible to store on a medium
• Write type - Whether it is read only, write only, or readable and writable
• Cost - How much it costs per megabyte
• Access type - Whether it uses Random Access or Serial Access

sequential access requires all memory locations before the one sought to be read, before reaching it. Random access memory allows you to jump directly to the memory location you are seeking

Pay special attention to devices with an orange background, you need to be able to describe exactly how they work!

Magnetic media

Magnetic media stores data by assigning a magnetic charge to metal. This metal is then processed by a read head, which converts the charges into ones and zeros. Historically, magnetic media has been very popular for storing programs, data, and making backups. It looks set to continue in this role for some time. However, solid state technology is starting to be used more and more, storing programs and data on new devices such as mobile phones and cameras.

Magnetic media
Device	Size
Hard Disk	Up to 8 Terabytes
Magnetic Tape	Up to 2 Terabytes

Hard disk

Video of exposed hard disk drive (HDD)

Hard disks are usually found inside computers to store programs and data. They are increasingly cheap and more and more companies are using them to back things up. Hard disks can vary in physical size with some disks getting as small as your thumb. More closely packed platters, greater density of data on each platter to allow for more tracks and cylinders and the ability to write smaller magnetic spots have all been developments in the design of hard disks to increase their storage capacity. The capacity of a commercial disk is currently up to about 4 terabytes allowing users to read and write to them. They are constructed from several key components:

• Platter - Metallic disks where one or both sides of the platter are magnetised, allowing data to be stored. The platter spins continuously, thousands of times a second, around a spindle while in use. There may be several platters, with data stored across them. The disk is divided into tracks and sectors with data represented by magnetising spots on the disk.
• Head - The head reads magnetic data from the platter. For a drive with several platters there may be two heads per platter allowing data to be read from top and bottom of each
• Actuator Arm - used to move the read heads in and out of the disk so that data can be read and written to particular locations. They allow you to access data in a random fashion, so you don't need to read your way through the entire disk to fetch a particular bit of information, you can jump right there. Seek time is very low.
• Power connector - provides electricity to spin the platters, move the read head and run the electronics
• IDE connector - allows for data transfer from and to the platters
• Jumper block - used to get the disk working in specific ways such as RAID

For the exam you must be able to explain how a hard disk works:

1. The platters spin around the spindle
2. data is requested to be read from a particular area of a platter
3. the actuator arm moves the read head to that track
4. Once the data sector that is required has spun around and under the read head, data is read
5. Read data is sent from the IDE connector to main memory

Description of a hard disk platter

Writing data is very similar:

1. The platters spin around the spindle
2. data is sent to the hard disk using the IDE connector
3. the actuator arm moves the write head to the track that will be written to
4. Once the data sector that is required has spun around and under the write head, data is written to the platter

Pros

Fast seek times

Random access

High capacities possible

Low cost per megabyte

Cons

Very susceptible to damage from physical shocks

Magnetic Tape drive

DDS tape drive. Above, from left right: DDS-4 tape (20 GB), 112m Data8 tape (2.5 GB), QIC DC-6250 tape (250 MB), and a 3.5" floppy disk (1.44 MB)

Increasingly obsolete, the tape has been a medium to deliver software and back up data since the early days of computing. Nowadays they are used mostly for corporate backing up and archiving of data. Tapes are sequential data stores, meaning that if you had information stored at the end of the tape you would have to wind your way through the entirety of the tape before you could read it. There is no random access like with a hard disk! Tapes can be several terabytes in size and reading and writing can be very fast as long as you read or write continuous sections of the tape at once.

Pros

Fast

High capacity

Cheap per megabyte

Cons

Serial read and write capabilities

Optical media

Optical media works by creating a disc with a pitted metallic surface. There are several different types of disk out there ranging from 650 MB to 128 GB, with the pits and lands getting closer together for higher volume disks. The principle behind how each of them works is the same.

pitted surface visible on the surface of a CD. Massively zoomed in!

Optical media
Device	Type	Size	Image
CD-ROM CD-R CD-RW	Read Only Write once then Read only re-Writable	650 - 900 MB
DVD-ROM DVD-R DVD-RW DVD-RAM	Read Only Write once then Read only re-Writable re-Writable	4.7 - 9.4 GB
Blu-ray (BD) disc HD DVD (obsolete)	Re-Writable and Read Only versions available. Uses a blue laser, that is able to recognise smaller pits and lands, which allows for the pits and lands to be more closely packed, and so store more data	25 - 128 GB

CD-ROM

close up of the surface of a CD being read

A CD-ROM is a metal disc embedded into a plastic protective housing. Each disc has to be 'mastered'; this is the process of creating the CD and placing the data on it. CDs are WORM (Write Once, Read Many) media; this refers to the fact that once they have been mastered, there is no way to change the data on them.

Reading from a CD-ROM

1. A single track runs in a spiral pattern from the centre of the disc to the outside, this track is made of pits and lands to represent the ones and zeroes of binary data
2. A low-powered laser is shone on the metallic surface and the reflection is captured in a photodiode sensor, the lands reflect differently to the pits, meaning it can tell the difference between a 1 and a 0
3. The disc spins and the laser follows the track
4. The binary data (the 1s and 0s) are put together and the CD-ROM has been read

Pros

Cheap

Data cannot be written over by the consumer

Cons

Slow seek time

Data degrades with time, discs from 20 years ago might not work!

Can only be written to with a very high powered laser, which is not usually available in home computers

Data cannot be written over

CD-R

The CD-R is made of a reflective metal disk with a layer of (usually green, opaque) dye on top.

Writing to a CD-R

1. A single track runs in a spiral pattern from the centre of the disc to the outside.
2. A high-powered laser is shone onto the CD-R, changing the transparency (permanently) of the dye above. The transparent and opaque parts represent binary 1s and 0s
3. The disc spins and the laser follows the track, putting the binary data onto the CD-R in a spiral track
4. The data has been written

Reading from a CD-R

1. A single track runs in a spiral pattern from the centre of the disc to the outside, this track is made of pits and lands to represent the ones and zeroes of binary data
2. A low-powered laser is shone on the surface and the reflection is captured in a photodiode sensor. The opaque dye will reflect differently to the transparent dye (which would just reflect the metal underneath it), meaning it can tell the difference between a 1 and 0
3. The disc spins and the laser follows the track
4. The binary data (the 1s and 0s) are put together and the CD-R has been read

Pros

Cheap

Can be written to using a conventional home computer

Cons

Slow seek time

Data degrades with time, discs from 20 years ago might not work!

Data cannot be written over

CD-RW

The CD-RW is made of a reflective metal disk with a layer of a special ('phase change') metal on top.

Writing to a CD-RW

1. A single track runs in a spiral pattern from the centre of the disc to the outside.
2. A high-powered laser is shone onto the CD-RW. Depending on whether this is very high powered or heats at a slightly lower temperature, the top layer of metal cools differently. These will result in different amounts of reflectivity, which represent the 1s and 0s.
3. The disc spins and the laser follows the track, putting the binary data onto the CD in a spiral track
4. The data has been written

Reading from a CD-RW

1. A single track runs in a spiral pattern from the centre of the disc to the outside, this track is made of pits and lands to represent the ones and zeroes of binary data
2. A low-powered laser is shone on the surface and the reflection is captured in a photodiode sensor. The different ways the metal has cooled reflect different amounts, meaning it can tell the difference between a 1 and 0
3. The disc spins and the laser follows the track
4. The binary data (the 1s and 0s) are put together and the CD-RW has been read

Pros

Cheap

Can be written to using a conventional home computer

Cons

Slow seek time

Data degrades with time, discs from 20 years ago might not work!

Data can be changed after writing

Not all CD players (mostly older ones) can read CD-RWs, as opposed to CD-ROMs and CD-Rs

Solid-state memory

Solid-state memory
Device	Description
USB flash drive	Up to 256 GB
Memory card	Up to 256 GB

USB (memory stick) Flash Drive

Internals of a typical USB flash drive
1	USB Standard-A plug
2	USB mass storage controller device
3	Test points
4	Flash memory chip
5	Crystal oscillator
6	LED
7	Write-protect switch (Optional)
8	Space for second flash memory chip

USB Flash drives are solid state, that means that there are no moving parts. This is very useful for seek times as we don't have to wait for mechanical movement, meaning seek time is very low and it allows for fast Random Access Memory. Flash drives can be set to read only mode, but they will always allow for reading and writing. The size of flash drives is not as great as a Hard Disk and they are generally much more expensive per megabyte

1. put drive into USB socket
2. USB driver loads, providing the computer with code on how to read and write from the USB
3. The USB is read, giving information on the file and folder structure (File Allocation Table) to the Computer
4. [Reading] The user chooses to open a file, the Computer sends the address wanted to the USB port
5. [Reading] The USB returns the data at the location requested
6. [Writing] The computer sends data to the USB port where it is place into empty space on the drive
7. [Writing] The computer then requests a new version of the file and folder structure

Pros

Very fast seek times

Very portable

Cons

Limited capacity

Expensive per MB when compared to Hard Disks

Memory cards

Work in much the same way as a Flash drive and can often be converted into Flash Drives. They have different connectors and are generally smaller than USB Flash drives allowing for them to be used in cameras, mobile phones and game consoles.

comparison of different memory cards

Exercise: Secondary Storage Choose the correct secondary storage device for each of the following scenarios: A company needs to backup some HD movie files for 4 years. Answer: DVD-ROM Blu-Ray Tape Hard Disk NOTE: not CD-ROM, it is too small and USB might be too expensive an option You need to store files for a school project taking up about 70 MB that you can then transport to and from school Answer: USB Memory Stick(remember not to say USB on it's own!) CD-RW NOTE: nothing that is ROM! Why do some people reckon that Blu-Ray will be the last optical disk format? Answer: As broadband gets faster and people store more and more of their data online, everything will be transmitted over the internet and there will be no need to have large physical storage at home Describe how a Hard Disk writes a file Answer: The platters spin around the spindle data is sent to the hard disk using the IDE connector the actuator arm moves the write head to the track that will be written to Once the data sector that is required has spun around and under the write head, data is written to the platter Describe how a computer reads from a usb Answer: put drive into USB socket USB driver loads, providing the computer with code on how to read and write from the USB The USB is read, giving information on the file and folder structure (File Allocation Table) to the Computer The user chooses to open a file, the Computer sends the address wanted to the USB port The USB returns the data at the location requested What optical disk format would you recommend for the following: Making long term backups of some photos Answer: CD-R DVD-R NOTE: there is no need for RW or RAM here Distributing a software product that includes 20 minutes of HD video footage Answer: DVD-ROM Blu-Ray NOTE: CD-ROM would probably be too small for this Backing up school work at the end of each week to take home Answer: USB Flash Drive DVD-RW / RAM CD-RW NOTE: Rs wouldn't be suitable as you would have to keep throwing them away!

Structure of the Internet

The Internet and its Uses Internet World Wide Web (WWW) and routers. Intranet Understand the structure of the Internet, the role of packet switching Understand the difference between the Internet, the Web and an intranet.

The Internet and its Uses Uniform Resource Locator (URL) Describe the term URL in the context of Internet working. Uniform Resource Identifier (URI) Describe the role of URIs in the context of Internet working. Domain Names and IP Addresses Explain the terms domain name and IP address. Describe how domain names are organised. Know that an IP address is split into a network identifier part and a host identifier part.

The Internet, Intranet and World Wide Web Internet registries and Internet registrars Explain why such services are provided. Internet Service Providers (ISP) Understand the role of an ISP. Domain Name Server (DNS) Understand the purpose of Domain Name Server. The Client–Server Model Be familiar with the client–server model. Common Standard Protocols: TCP/IP - Describe the role of the four layers of the TCP/IP protocol stack, including sockets. FTP - FTP client software and an FTP server to transfer files using anonymous and non-anonymous access. HTTP - Web server to retrieve web pages in text form HTTPS TELNET - Telnet server for remote management of a server POP3, SMTP - E-mail server to read and send e-mail Well-known ports Client ports Understand the role of a web browser in retrieving web pages and web page resources and rendering these accordingly.

The Internet

The Internet - a global system of interconnected computer networks that use the standard Internet Protocol suite (TCP/IP)

The internet impacts heavily upon the way that we live, study and work. But it hasn't always been that way. In the 1960s ARPA, a part of the American Department of Defence, funded several large computing projects. These projects were very expensive and situated in different parts of the USA. It was unreasonable to expect research groups to travel to each of these sites, and it was far too expensive to build more of them, what was needed was a method to link them together so that information could be easily exchanged. ARPANET was created, basing communication on packet switching. This system of communication broke messages into chunks which were then passed to other sites using a network of interlinked computers. Due to the unreliable nature of connections, if any link in the network broke, a packet could be re-routed around the problem to reach its destination. The concept is similar to how drivers can take different routes when they meet a blocked off road.

ARPANET logical map, March 1977

Extension: Cold War Rumours A popular myth is that the internet was started because the American Department of Defense were looking at how they could maintain control of military installations in the event that they were on the receiving end of a Soviet Nuclear strike. This would mean that communications between sites would have to be maintained even if one or more of the sites connecting installations were knocked out. A sound idea, but not the reason for starting ARPANET. The network never carried any classified material and was predominantly used for research purposes, connecting research institutions, including Universities in the UK.

In the 70s ARPA funded other experimental networks and made an effort to unite them. At the same time the limits of the initial network to 63 nodes and 252 hosts were reached and so the TCP/IP protocol was created. This protocol, or set of rules, allowed different networks to talk to each other. This protocol still forms the main link between networks in the internet to this day.

As the internet consists of many different networks interlinking with each other, the internet has no central structure or governing body. This makes it very robust, meaning that if one connection between two hosts is lost, you can probably find another route to send information by. It also poses a threat to some governments, as they struggle to restrict information available to their citizens. Countries such as North Korea and China filter their internet links through a few connections to the outside world, this means the government can control what comes in and out of the country, giving them the ability to filter which websites are available and allow them to switch the internet 'off' at times of crisis, by cutting these connections. This happened during the 2011 Arab Spring, where Tunisia, Egypt and Libya tried to stop their citizens from getting information from the outside world.

Diagram of routing paths through a portion of the Internet, notice the multiple routes you can take to get from one network to another

World Wide Web (WWW)

World Wide Web - a system of interlinked hypertext documents accessed via the Internet

The first thing to notice is that the World Wide Web is not the internet, but a subset of what the internet offers. The internet hosts all forms of data, including games, video, telecommunications etc. while the WWW only transmits hypertext documents. The WWW is accessed through a web browser linking files together using hyperlinks and was invented by a British computer scientist, Sir Tim Berners-Lee in 1989.

Intranet

Intranet - a private network within an organisation which may offer printer sharing, file sharing, communication, private websites etc...which uses internet technologies such as TCP/IP and web browsers using transmition medium such as wired or wireles connection

the relationships between the internet, intranets and the World Wide Web

Routers

Router - a device that interconnects with two or more computer networks, which then interchange packets with each other

To link multiple computers together we need to use devices called routers or switches. These devices co-ordinate sending messages from one system to another, making sure that packets get to their destinations

A typical home or small office router showing the ADSL telephone line and Ethernet network cable connections

Packet switching

Packet switching is the method by which the internet works, it features delivery of packets of data between devices over a shared network. For example the school web server sending you a webpage over the internet or you sending an email to a friend. To get from one device to another the data packets will have to travel through network adapters, switches, routers and other network nodes. The route taken by each packet might vary and at times there might be a lot of data travelling through these nodes meaning packets will be queued. This will result in varying times it takes to send data from one device to another depending on the traffic load in the network.

Different routes taken by three different data packets being sent to the same destination

If you play computer games online you might have heard the term latency (or lag), this is the time taken to send data from one device to another. The higher the latency (time taken to send data), the less responsive your game will be. People with very low latency tend to do better at games as their machines will be more responsive.

Example: The ping command To see the time it takes to send a message using packet switching you can use the ping command to time how long it takes to send data to another device, in this case we have used the command prompt to ping the www.example.com server: # ping -c 5 www.example.com PING www.example.com (192.0.43.10) 56(84) bytes of data. 64 bytes from 43-10.any.icann.org (192.0.43.10): icmp_seq=1 ttl=250 time=80.5 ms 64 bytes from 43-10.any.icann.org (192.0.43.10): icmp_seq=2 ttl=250 time=180.1 ms 64 bytes from 43-10.any.icann.org (192.0.43.10): icmp_seq=3 ttl=250 time=80.3 ms 64 bytes from 43-10.any.icann.org (192.0.43.10): icmp_seq=4 ttl=250 time=80.3 ms 64 bytes from 43-10.any.icann.org (192.0.43.10): icmp_seq=5 ttl=250 time=80.4 ms As you can see the same data is being sent to the same location in all 5 attempts, but the second attempt met traffic on the way and took much longer. However, at 180.1 milliseconds you probably wouldn't notice.

As packet switching doesn't define a set route for data to be sent by, any disruption in the network can be circumnavigated by re-routing:

demonstration of how the internet can re-route message if nodes fail. This makes the internet very robust

Example: The trace command The tracert command is used to map the route from one machine to another on the internet showing all the intermediate nodes, in this case, the message took ten steps to get there. The code above shows a trace from a home network to the www.google.com website. You can see that the 4th hop got lost and the data had to be re-routed. # tracert www.google.com Tracing route to www.l.google.com [209.85.147.99] over a maximum of 30 hops: 1 62 ms 99 ms 99 ms bebox.config [192.168.1.254] 2 53 ms 19 ms 18 ms 87-194-56-8.bethere.co.uk [87.194.56.8] 3 * * 83 ms 10.1.2.177 4 * * * Request timed out. 5 20 ms 17 ms 17 ms 64.233.175.25 6 20 ms 38 ms 19 ms 209.85.253.92 7 26 ms 56 ms 23 ms 66.249.95.173 8 45 ms 24 ms 24 ms 72.14.236.191 9 33 ms 35 ms 35 ms 216.239.46.221 10 27 ms 22 ms 22 ms bru01m01-in-f99.1e100.net [209.85.147.99] Trace complete. If you want to try this at home there are different commands used on different operating systems: Windows - tracert Linux - tracepath or traceroute Mac - traceroute

Packet switching steps

1. Data split into chunks (data packets)
2. Each packet has a from address, to address, and payload (data chunk)
3. If data requires multiple chunks, then the order of each packet is noted
4. Packets sent onto the network, moving from router to router taking different paths (set by the router). Each packet's journey time can, therefore, differ.
5. Once packets arrive, they are re-ordered
6. Message sent from recipient to sender indicating that the message has been received
7. If no confirmation message, sender transmits data again

Exercise: Internet/Intranet/World Wide Web For the following packets (Green, Blue, Red), assuming each step from router to router takes an equal time. What order will the packets arrive at their destination? How do we make sure that the packets are read in the correct order? Answer: Green Red Blue Each packet has a sequence number attached to it so that it can be ordered when it reaches its destination. What happens if a packet gets permanently lost on the way to a host? Answer: The packet will be resent until a confirmation message is returned from the recipient What happens if a router on the network fails? How will the packets get to their destination? Answer: The packets will be re-routed around the failed node

IP addresses

IP Address - numerical label assigned to each device (e.g., computer, printer) participating in a computer network that uses the Internet Protocol

Every device attached to a network has a number assigned to it. This unique number is called the IP Address, and you might be familiar with the format of:

nnn.nnn.nnn.nnn e.g. 192.168.7.1

Currently the most common form of IP Address is IPv4 which uses 32 bits to store an address. This means that there are theoretically $2^{32}=4,294,967,296$ different IP Addresses that can exist. However, due to the allocation of IP ranges to different organisations and tasks, the number is lower.

An IP address (version 4) in both dot-decimal notation and binary code

An IPv4 address is typically shown as split into 4 chunks as shown above. Different ranges of IP addresses are categorised differently, with the first part of the IP specifying who or where the IP address is (the network identifier), and the second part defining which host/machine it is (the host identifier).

$\underbrace {192\cdot 168} _{\text{network}}\cdot \underbrace {12\cdot 162} _{\text{host}}$

Different sets of IP ranges are allocated to particular networks, geographic areas, companies etc. The table below shows several examples of IP ranges and the uses that they have been put to:

IP range	Description	Example
192.168.___.___ 172.16.___.___ - 172.31.___.___ 10.___.___.___	Private networks, e.g. intranets	192.168.1.23
41.___.___.___ 102.___.___.___ 105.___.___.___	AfriNIC allocations for IP addresses in Africa	102.43.1.65
81.___.___.___ 217.___.___.___ 62.___.___.___	European allocations for IP addresses	81.202.17.89
200.___.___.___	Latin America and the Caribbean	200.100.50.25
9.___.___.___	IBM	9.1.2.3
17.___.___.___	Apple	17.19.23.29

As you saw with packet switching, every request that gets sent over the internet is sent with the sender's IP address attached. This is useful for many different reasons. Firstly you can send a confirmation message to the sender to confirm that you received the data. Secondly websites can keep track of where their users come from. Thirdly websites can block requests from certain IP address ranges. For example if you were running a national television service such as the BBC, where your programming was paid for by your fellow countrymen, you wouldn't want people from other countries watching programmes that they hadn't paid for. If you try and access the BBC iPlayer from the USA it will say "Not available in your area". This is because an American's IP would be from a banned IP range. IP banning can also be used by governments to bar their populations from accessing websites on certain IP addresses.

The diagram above shows how two intranets can connect across the internet. If the computer in Intranet A with the IP address 192.168.1.2 wants to send a message to a computer in Intranet B, it will send its message through the Router connected to Intranet A (IP=172.8.18.100). This router will then route the message onto the internet, going from router to router until it reaches the router attached to Intranet B (IP=201.108.0.45). This router will then pass the message on to the correct machine in Intranet B. Notice that because each intranet is connected to the internet through a router, the computers on each intranet will appear as having the IP of their router when connected to the internet. If you share a house and someone commits a crime online, the finger might be pointed at the whole household! Using IP addresses this way was never the intention of the designers of TCP/IP, they would much prefer that each machine had a distinct IP address, however, with the shortage of IP addresses this isn't possible. What is needed is a system that has more addresses available.

Extension: IPv6 As you might have noticed, there is a limit to the number of IPv4 addresses we can have, this limit is well below the current population of the world. If we were in the future to have every inhabitant of the planet connected to the internet, there wouldn't be enough IP Addresses for them to use! This problem is very current and IPv6 is being introduced to try and resolve it. IPv6 uses 128 bits for each address, meaning we have theoretically $2^{128}$ addresses available = $340,282,366,920,938,463,463,374,607,431,768,211,456$ different possible addresses. Decomposition of an IPv6 address from hexadecimal representation to its binary value. The IPv6 address has 128 bits split into: 64 bits for the network the first 16 bits are used for address type 16 bits for sub networks leaving 32 bits for main networks 64 bits for the interface addresses Why would we ever need this many you may ask? With so many addresses this will allow each person to have multiple devices connected to the internet, currently driven by the demand for internet on mobile phones. We are also looking at connecting lots of other devices to the internet that might not currently be connected. For example we could have fridges telling us when we are low on milk, ovens telling us when they need cleaning, bikes telling us when they need a service. The future is coming, watch this IPv6 space!

Exercise: IP Addresses What is an IP address, give an example? Answer: Numerical label assigned to each device (e.g., computer, printer) participating in a computer network that uses the Internet Protocol 192.168.7.1 What is the IP address range for an internal network? Answer: 192.168.___.___ OR 172.16.___.___ - 172.31.___.___ 10.___.___.___ What IP address would an internal network machine appear to have when connecting to the internet? Answer: The address of the router Convert the following IP address into binary: 123.45.67.89 Answer: 01111011.00101101.01000011.01011001 Convert the following IP address into decimal: 01011110.01100010.10011011.00010000 Answer: 94.98.155.16 Why has IPv6 been introduced? Answer: IPv4 only has 32 bits, this means as more and more machines connect to the internet we will eventually run out of IP Addresses. IPv6 allows for more addresses to be used. For the following IP address can be split into two parts, label each: 192.168.23.2 Answer: $\underbrace {192\cdot 168} _{\text{network}}\cdot \underbrace {23\cdot 2} _{\text{host}}$

Domain names

Domain Name - humanly-memorable names for Internet participants such as computers, networks, and services. One domain name can be connected to multiple IP addresses

Trying to remember IP addresses is as difficult as trying to remember people's phone numbers. Not many people do it well and you are far more likely to be using a domain name to access a website. A domain name allows us to link to servers and other computers using easily remembered names. The domain name also tells us a bit about the location we are visiting through the use of top level domain names.

Top level domain	Description
.com	Commercial
.gov	US governmental organisations
.mil	US military
.org	Organisation
.uk	United Kingdom, country specific website
.so	Somalia, country specific website
.xxx	Adult entertainment
.onion	Deep Web Links

Sometimes top level domain names might be joined by second level domains, chained together to tell you more detailed information:

bbc.com - there is a commercial organisation called bbc
bbc.co.uk - there is a United Kingdom commercial organisation called bbc.
tfl.gov.uk - there is a United Kingdom governmental organisation, called TFL.

Second level domain names typically tell you the person/company/organisation that owns the address. Finally you have the host or service name, which is the machine/service you are connecting to. For example:

en.wikipedia.org - an organisation, called Wikipedia, requesting the English language version
www.ibm.com - an commercial organisation, called IBM, connecting to the www (World Wide Web) host/service machine

$\underbrace {windows} _{\text{host}}.\underbrace {microsoft} _{\text{domain name}}.\underbrace {com} _{\text{top level domain}}$

Diagram of how domain names are constructed

In the example above a client sends a request to a Domain Name Server for www.debian.com, but after that domain name lookup is hierarchical:

• a request for .com is first sent to a known root server which provides the address of the name server for .com.
• This is then queried for debian.com giving the address of another name server
• which finally provides the address for www.debian.com.

Results are remembered for a period of time to reduce the work load.

Domain Name System (DNS)

Domain Name System server (DNS server) - translates domain names into IP addresses

If you have a modern mobile phone it is very unlikely that you will type in the number of your friends each time you want to call or text them. You are far more likely to use the address book, typing in their name, then letting the phone find the number. This is exactly the same principle behind the Domain Name System. A DNS server translates domain names meaningful to humans (such as www.google.com) into IP Addresses for the purpose of locating and addressing these devices worldwide.

Domain names are far easier for humans to remember than an IP address. To see a domain name in action you can use the ping command, where pinging google, uses the DNS server to find the IP address you want to send a ping packet to:

# ping www.google.com
Pinging www.l.google.com [209.85.229.99] with 32 bytes of data:

Or on Linux try dig

$ dig www.google.com
-- Snip --
;; ANSWER SECTION:
www.google.com.		246	IN	A	173.194.34.144
www.google.com.		246	IN	A	173.194.34.148
www.google.com.		246	IN	A	173.194.34.145
www.google.com.		246	IN	A	173.194.34.146
www.google.com.		246	IN	A	173.194.34.147

Internet registries and Internet registrars

Internet Registrars - allow organisations and individuals to buy their own domain names

Internet registrars are responsible for allocating internet domains to anyone who wants one. If someone wanted to own their own website with a domain name, they would have to go to an internet registrar in order to buy the website name. These services typically require payment in order to maintain control over the name of the website. If you do not renew your website, then the internet registrars may sell it to other buyers.