Computer Organisation

Computer Architecture

2.1.1 Outline the architecture of the central processing unit (CPU) and the functions of the arithmetic logic unit (ALU) and the control unit (CU) and the registers within the CPU.

A major defining point in the history of computing was the realisation in 1944–1945 that data and instructions to manipulate data were logically the same and could be stored in the same place. The computer design built upon this principle, which became known as the von Neumann Architecture, is still the basis for computer today. Although the name honours John von Neumann, a brilliant mathematician who worked on the construction of the atomic bomb, the idea probably originated with J. Presper Echkert and John Mauchly, two other early pioneers who worked on the ENIAC at the Moore School at the University of Pennsylvania during the same time period.

von Neumann Architecture

Another major characteristic of the von Neumann architecture is that the units that process information are separate from the units that store information. This characteristic leads to the following components of the von Neumann architecture.

• The memory unit that holds both data and instructions.
• The arithmetic/logic gate unit that is capable of performing arithmetic and logic operations on data.
• The input unit that moves data from the outside world into the computer.
• The output unit that moves results from inside the computer to the outside world.
• The control unit that acts as the stage unit to ensure that all the other components act in concert.

Memory

Memory is a collection of cells, each with a unique physical address. We use the generic word cell here rather than byte, because the number of bits in each addressable location, called the memory's addressability, varies from one machine to another. Today, most computers are byte addressable.

To fully illustrate the concept of memory, take a computer with 4GB of RAM as an example. The memory consists of 4 × 2³⁰ bytes, which means each byte of the computer is uniquely addressable, and the addressability of the machine is 8 bits. The cells in memory are numbered consecutively beginning with 0. For example, if the addressability is 8, and there are 256 cells of memory, the cells would be addressed as follows:

Address	Contents
00000000	11100011
00000001	01010101
$\vdots$	$\vdots$
11111100	00000000
11111101	11111111
11111110	10101010
11111111	00110011

What are the contents of address 11111110? The bit pattern stored at that location is 10101010. However, what the contents actually represents, be it instructions, value, sign, etc. will be discussed later. What is important, however, is to understand that the bit pattern is information and can be interpreted.

When referring to the bits in a byte or word, the bits are numbered from right to left beginning with zero. The bits in address 1111110 are numbered as follows:

Bit Position	7	6	5	4	3	2	1	0
Contents	1	0	1	0	1	0	1	0

Arithmetic/Logic Unit

The Arithmetic/Logic Unit (ALU) is capable of performing basic arithmetic operations such as adding, subtracting, multiplying, and dividing two numbers. This unit is also capable of performing logical operations such as AND, OR, and NOT. The ALU operates on words, a natural unit of data associated with a particular computer design. Historically, the word length of a computer has been the number of bits processed at once by the ALU. However, the current Intel line of processors has blurred this definition by defining the word length to be 16 bits. The processor can work on words (of 16 bits), double words (32 bits), and quadwords (64 bits). In the rest of this wiki, when referring to word, it will be of the historical nature aforementioned.

Most modern ALUs have a small number of special storage units called Registers. These registers contain one word and are used to store information that is needed again immediately. For example, in the calculation of 1 × (2 + 3). 2 is first added to 3 and the result is multiplied by 1. Rather than storing the result of adding 2 and 3 in memory and then retrieving it to multiply it by 1, the result is left in a register and the contents of the register is multiplied by 1. Access to registers is much faster than access to memory locations.

Input/Output Units

All of the computing power in the world would not be useful if one could not input values into the calculations from the outside or report to the outside the results of said calculations. Input and output units are the channels through which the computer communicates with the outside world.

An Input Unit is a device through which data and programs from the outside world are entered into the computer. The first input units interpreted holes punched on paper tape or cards. Modern-day input devices, however, include, but are not limited to; keyboards, mice, cameras (also known as, simply, webcams), and scanning devices.

An Output Unit is a device through which results stored in the computer memory are made available to the outside world. Examples include printers and screen monitors.

Control Unit

The Control Unit is the organising force in the computer, for it is in charge of the Fetch-Execute Cycle. There are two special registers in the control unit. The Instruction Register (IR) contains the instruction that is being executed, and the Program Counter (PC) contains the address of the next instruction to be executed. Because the ALU and the control unit work so closely together they are often thought of as one unit called the Central Processing Unit (CPU).

Above is a simplified view of the flow of information through the parts of a von Neumann machine. The parts are connected to one another by a collection of wires called a bus, through which data travels in the computer. Each bus carries three kinds of information; address, data, and control. An address is used to select the memory location or device to which data will go, or from which it will be taken. Data then flows over the bus between CPU, memory, and I/O Devices. The control information is used to manage the flow of addresses and data. For example, a control signal will typically be used to determine the direction in which the data is flowing either to or from the CPU. The Bus Width is the number of bits that it can transfer simultaneously. The wider the bus, the more address or data bits it can move at once.

2.1.3 Explain the use of cache memory.

Because memory accesses are very time consuming relative to the speed of the processor, many architectures provide Cache Memory. Cache memory is a small amount of fast-access memory into which copies of frequently used data are stored. Before a main memory access is made, the CPU checks whether the data is stored in the cache memory. Pipelining is another technique used to speed up the Fetch-Execute Cycle. This technique splits an instruction into smaller steps that can be overlapped.

In a personal computer, the component in a von Neumann machine reside physically a printed circuit board called the Motherboard. The motherboard also has connections for attaching other devices to the bus, such as a mouse, a keyboard, or additional storage devices.

So what does it mean to say that a machine is an n-bit processor? The variable n usually refers to the number of bits in the CPU general registers: Two n-bit numbers can be added with a single instruction. It also can refer to the width of the bus, which is the size of the addressable memory—but not always. In addition, n can refer to the width of the data bus—but not always.

The Fetch-Execute Cycle

2.1.4 Explain the machine instruction cycle.

Before looking at how a computer does what it does, let us look at what it can do. The definition of a computer outlines its capabilities; a computer is an electronic device that can store, retrieve, and process data. Therefore, all of the instructions that we give to the computer relate to storing, retrieving, and processing data.

The underlying principle of the von Neumann machine is that data and instructions are stored in memory and treated alike. This means that instructions and data are both addressable. Instructions are stored in contiguous memory locations; data to be manipulated are stored together in a different part of memory. To start the Fetch-Execute Cycle, first of all the data is loaded to the main memory by the operating system, the address of the first instruction is placed onto the program counter.

The process cycle includes four steps:

1. Fetch the next instruction,
2. Decode the instruction
3. Get data if needed,
4. Execute the instruction.
5. Store result of execution and check for next instruction.

Fetch the Next Instruction

The PC increments one by one to point to the next instruction to be executed, so the control unit goes to the address in the memory address register which holds the address of the next instruction specified in the PC, takes it to the main memory through the address bus and returns it to the memory buffer register via the data bus. The MBR is a two way register that temporarily holds data fetched from the Memory(cache or RAM), makes a copy of the contents, and places the copy in the IR. At this point the IR contains the instruction to be executed. Before going to the next step in the cycle, the PC must be updated to hold the address of the next instruction to be executed when the current instruction has been completed. There after the instruction register is responsible for the instruction to be solved by the CU. the CU checks on the status of the instruction and then allows execution. Because the instructions are stored contiguously in memory, adding the number of bytes in the current instruction to the PC should put the address of the next instruction into the PC. Thus the control unit increments the PC. It is possible that the PC may be changed later by the instruction being executed.

In the case of an instruction that must get additional data from memory, the ALU sends an address to the memory bus, and the memory responds by returning the value at that location. In some computers, data retrieved from memory may immediately participate in an arithmetic or logical operation. Other computers simply save the data returned by the memory into a register for processing by a subsequent instruction. At the end of execution, any result from the instruction may be saved either in registers or in memory.

Decode the Instruction

To execute the instruction in the instruction register, the control unit has to determine what instruction it is. It might be an instruction to access data from an input device, to send data to an output device, or to perform some operation on a data value. At this phase, the instruction is decoded into control signals. That is, the logic of the circuitry in the CPU determines which operation is to be executed. This step shows why a computer can execute only instructions that are expressed in its own machine language. The instructions themselves are literally built into the circuit.

Get Data If Needed

The instruction to be executed may potentially require additional memory accesses to complete its task. For example, if the instruction says to add the contents of a memory location to a register, the control unit must get the contents of the memory location.

Execute the Instruction

Once an instruction has been decoded and any operands (data) fetched, the control unit is ready to execute the instruction. Execution involves sending signals to the arithmetic/logic unit to carry out the processing. In the case of adding a number to a register, the operand is sent to the ALU and added to the contents of the register.

When the execution is complete, the cycle begins again. If the last instruction was to add a value to the contents of a register, the next instruction probably says to store the results into a place in memory. However, the next instruction might be a control instruction—that is, an instruction that asks a question about the result of the last instruction and perhaps changes the contents of the program counter.

Hardware has changed dramatically in the last half-century, yet the von Neumann model remains the basis of most computers today. As Alan Perlis, a well-known computer scientist once said;

Sometimes I think the only universal in the computing field is the Fetch-Execute Cycle.

—Alan Perlis, 1981.

RAM and ROM

2.1.2 Describe primary memory.

RAM stands for Random-Access Memory. RAM is memory in which each cell (usually a byte) can be directly accessed. Inherent in the idea of being able to access each location is the ability to change the contents of each location. That is, storing something else into that place can change the bit pattern in each cell.

In addition to RAM, most computers contain a second kind of memory called ROM. ROM stands for Read-Only Memory. The contents in locations in ROM cannot be changed. Their contents are permanent and cannot be altered by a second operation. Placing the bit pattern in ROM is called burning. The bit pattern is burnt either at the time the ROM is manufactured or at the time the computer parts are assembled.

RAM and ROM are differentiated by a very basic property; RAM is volatile, and ROM is not. This means that RAM does not retain its bit configuration when the power is turned off, but ROM does. Because ROM is stable and cannot be changed, it is used to store the instructions that the computer needs to start itself. Frequently used software is also stored in ROM so that the system does not have to read the software each time the machine is turned on. Main memory usually contains some ROM along with the general-purpose RAM.

Secondary Storage Devices

2.1.5 Identify the need for persistent storage.

An input device is the means by which data and programs are entered into the computer and stored into memory. An output device is the means by which results are sent back to the user. Because most of main memory is volatile and limited, it is essential that there be other types of storage devices where programs and data can be stored when they are no longer being processed or when the machine is not turned on. These other types of storage devices (other than that of main memory) are called secondary or auxiliary storage devices. Because data must be read from them and written to them, each storage device is also an input and an output device.

Examples of secondary storage devices include;

• Magnetic Tape,
• Magnetic Disks,
• CDs and DVDs,
• Flash Drives,
• External Hardrives

Operating systems and application systems

2.1.6 Describe the main functions of an operating system.

2.1.7 Outline the use of a range of application software.

As early as the end of the first generation of software development, there was a split between those programmers who wrote tools to help other programmers and those who used to solve problems. Modern software can be divided into two categories, system software and application software, reflecting this separation of goals. Application Software is written to address specific needs — to solve problems in the real world. Word processing programs, games, inventory control systems, automobile diagnostic programs, and missile guidance programs are all application software.

System Software manages a computer system at a more fundamental level. It provides the tools and an environment in which application software can be created and run. System software often interacts directly with the hardware and provides more functionality than the hardware does itself.

The Operating System of a computer is the core of its system software. An operating system manages computer resources, such as memory, and input/output devices, and provides an interface through which a human can interact with the computer. Other system software supports specific application goals, such as a library or graphics software that renders images on a display. The operating system allows an application program to interact with these other system resources.

The above diagram illustrates how an operating system interacts with many aspects of a computer system. The operating system manages hardware resources. It allows application software to access system resources, either directly or through other system software. It provides a direct user interface to the computer system.

Memory, Process, and CPU Management

Recall that executing a program resides in main memory and its instructions are processed one after another in the fetch-decode-execute cycle. Multiprogramming is the technique of keeping multiple programs in main memory at the same time; these programs compete for access to the CPU so that they can do their work. All modern operating system employ multiprogramming to one degree or another. An operating system must therefore perform memory management to keep track of which programs are in memory and where in memory they reside.

Another key operating system concept is the idea of a process, which can be defined as a program in execution. A program is a static set of instructions. A process is a dynamic entity that represents the program while it is being executed. Through multiprogramming, a computer system might have many active processes at once. The operating system must manage these processes carefully. At any point in time a specific instruction may be the next to be executed. Intermediate values have been calculated. A process might be interrupted during its execution, so the operating system performs process management to carefully track the progress of a process and all of its intermediate states.

Related to the ideas of memory management and process management is the need for CPU scheduling, which determines which process in memory is executed by the CPU at any given point.

One must remember, however, that the OS itself is just a program that must be executed. Operating system processes must be managed and maintained in the main memory along with other system software and application programs. The OS executes on the same CPU as other programs, and it must take its turn among them.

The following sections (Single Contiguous Memory Management, Partition Memory Management, Paged Memory Management) are for interest purposes only. The Computer Science Guide clearly notes under 2.1.6 that "technical details are not needed. For example, memory management should be described but how this is handled in a multitasking environment is not expected." Therefore, these sections serve the purpose of illustrating memory management techniques and can be summarised rather than utilised in an exam.

Single Contiguous Memory Management

Has only the operating system and one other program in memory at one time. This is the most basic type of memory management.

Partition Memory Management

The memory is broken up into different parts. Has the operating system and any number of programs running at the same time through these different partitions. The partitions have a base and a bound register.

Base register

• A register that holds the beginning address of the current partition (the one that is running)

Bounds register

• A register that holds the length of the current partition

Partition selection First fit

• Allocate program to the first partition big enough to hold it

Best fit

• Allocated program to the smallest partition big enough to hold it

Worst fit

• Allocate program to the largest partition big enough to hold it

Paged Memory Management

A technique in which processes are divided into fixed-size pages and stored in memory frames when loaded.

Frame

• A fixed-size portion of main memory that holds a process page

Page

• A fixed-size portion of a process that is stored into a memory frame

Binary, decimal and hexadecimal representation of data

What is binary ?

The term binary refers to any encoding in which there are two possible values. In computer science they refer to the electronic values 0 and 1 (see figure below). Booleans values are binary. In computers we use binary instead of the decimal system as they offer a much simpler and efficient way to perform calculations through electronics than they would with a decimal system. This can be explored in the following sections regarding binary gates.

Image: 150 pixels

Interpretation of voltages to binary by the computer. Given that we are in a system where the max voltage is 5 Volts, then input current in an electrical wire is interpreted as a logical 0 by a transistor if the voltage is between 0 volts and 0.8 volts. On the other hand if the voltage is between 2 volts and 5 volts then the transistor interprets the input signal as a logical 1 (right diagram). It is important to note that there is a non-usable area of voltage that does not correspond to either a logical 0 or 1. This non-usable area is particularly useful since voltage always slightly fluctuates, having this grey zone allows us to better identify electrical signals (0 and 1) from each other. Similar voltage conversions from volts to binary digits also exist for output signals from transistors.¹

The base of a number system specifies the number of digits used in the system. The digits always begin with 0 and continue through one less than the base. For example, there are 2 digits in base 2: 0 and 1. There are 8 digits in base 8: 0 through to 7. There are 10 digits in base 10: 0 through 9. The base also determines what the positions of digits mean. When one adds 1 to the last digit in the number system, one has to carry the digit position to the left.

Positional notation

Numbers are written using positional notation. The rightmost digit represents its value multiplied by the base of the zeroth power. The digit to the left of that one represents its value multiplied by the base to the first power. The next digit represents its value multiplied by the base to the second power. The next digit represents its value multiplied by the base to the third power, and so on. One is usually familiar with positional notation even if they are not aware. One is instinctively inclined to utilise this method to calculate the number of ones in 943:

	$9$	$\times$	$10^{2}$	$=$	$9$	$\times$	$100$	$=$	$900$
$+$	$4$	$\times$	$10^{1}$	$=$	$4$	$\times$	$10$	$=$	$40$
$+$	$3$	$\times$	$10^{0}$	$=$	$3$	$\times$	$1$	$=$	$3$
									$943$

A more formal way of defining positional notation is to say that the value is represented as a polynomial in the base of a number system. But what is a polynomial? A polynomial is a sum of two or more algebraic terms, each of which consists of a constant multiplied by one or more variables raised to a non-negative integral power. When defining positional notation, the variable is the base of the number system. Thus 943 is represented as a polynomial as follows, with $x$ acting as the base:

$9\times x^{2}+4\times x^{1}+3\times x^{0}$

To express this idea formally, a number in the base-$R$ number system has $n$ digits, it is represented as follows, where $d_{i}$ represents the digit in the $i$th position in the number:

$d_{n}\times R^{n-1}+d_{n-1}\times R^{n-2}+\ldots +d_{2}\times R+d_{1}$

Look complicated? Take a concrete example of 63578 in the base 10. Here $n$ is 5 (the number has exactly 5 digits), and $R$ is 10 (the base). The formula states that the fifth digit (the last digit on the left) is multiplied by the base to the fourth power; the fourth digit is multiplied by the base to the third power, and so on:

$6\times 10^{4}+3\times 10^{3}+5\times 10^{2}+7\times 10^{1}+8$

In the previous calculation, one assumed that the number base is 10. This is a logical assumption because the generic number system is base 10. However, there is no reason why the number 943 could not represent a value in base 13. In order to distinguish between these values, the general notation of $k_{R}$ is utilised in order to represent a number $k$ in base $R$. Therefore, $943_{10}$ is a number found in the base 10 system. In order to turn turn $943_{13}$ into $k_{10}$ one simply uses the previous calculation:

	$9$	$\times$	$13^{2}$	$=$	$9$	$\times$	$169$	$=$	$1521$
$+$	$4$	$\times$	$13^{1}$	$=$	$4$	$\times$	$13$	$=$	$52$
$+$	$3$	$\times$	$13^{0}$	$=$	$3$	$\times$	$1$	$=$	$3$
									$1576_{10}$

Therefore, 943 in base 13 is equal to 1576 in base 10, or $943_{13}=1576_{10}$. One must keep in mind that these two numbers have an equivalent value. That is, both represent the same number of "things." If one bag contains $943_{13}$ beans and a second bag contains $1576_{10}$ beans, then both bags contain the exact same number of beans. The number systems just allow one to represent the value in various ways.

Note that in base 10, the rightmost digit is the "ones" position. In base 13, the rightmost digit is also the "ones" position. In fact, this is true for any base, because anything raised to the power of zero is one.

Why would anyone want to represent values in base 13? It is not done very often, granted, but it is sometimes helpful to understand how it works. For example, a computing technique called hashing takes numbers and scrambles them, and one way to scramble numbers is to interpret them in a different base.

Other bases, such as base 2 (binary), are particularly important in computer processing. It is also helpful to be familiar with number systems that are powers of 2, such as base 8 (octal), and base 16 (hexadecimal).

How is data stored in binary format ?

The following four questions are typically seen in Paper 1 Section A.

How many possible numbers can I store in a byte ?

A bit is the smallest unit of data that a computer can process and store. It can either store a 1 or a 0 and represents on/off, true/false, yes/no.

1 byte is a unit of data that consists of/stores 8 bits. 1 byte represents 2⁸ distinct values.

• The biggest value a 1-byte number can be ( when all 8 bits are set to ) is: 11111111
• That represents: 2⁷+2⁶+2⁵+2⁴+2³+2²+2¹+2⁰ = 255

How many possible numbers can I store in a an n-bit number ?

Since there are n possible bits that each can take two possible values (1 or 0), we can store $2^{n}$ possible numbers in a n-bit number.

In a byte this means we can store 2⁸ = 256 different numbers.

What is the biggest number I can get in a an n-bit number ?

Since there are n possible bits that each can take two possible values (1 or 0), the biggest number that we can get is 2ⁿ -1. Indeed the smallest number that we can get is a 0 hence the -1 in the formula.

In a byte this means the biggest number we can get is 2⁸ -1 = 255, being 11111111, and the smallest number is 0 being 0000000.

How do I convert a base 2 (binary) number into a base 10 (decimal) number ?

To convert a binary number into decimal, we just need to sum all powers of 2 that have a 1 in the binary digit.

For example let's take the binary number 1011. Following the previous rule of positional number we achieve the following table:

	$1$	$\times$	$2^{3}$	$=$	$1$	$\times$	$8$	$=$	$8$
$+$	$0$	$\times$	$2^{2}$	$=$	$0$	$\times$	$4$	$=$	$0$
$+$	$1$	$\times$	$2^{1}$	$=$	$1$	$\times$	$2$	$=$	$2$
$+$	$1$	$\times$	$2^{0}$	$=$	$1$	$\times$	$1$	$=$	$1$
									$11$

Now following the same logic, but just written differently, if we convert the following byte into decimal: 10011100

binary to decimal conversion table

	1	0	0	1	1	1	0	0
=	27	26	25	24	23	22	21	20
=	128	64	32	16	8	4	2	1
=	128			16	8	4

We only add the columns where the binary digit is equal to 1. So 10011100 = 128 + 16 + 8 + 4 = 156

How do I convert a base 10 (decimal) number into a base 2 (binary) number ?

If we want to convert a decimal number to a binary number we will also use our previous conversion table.

For example let's convert decimal number 56:

• First we look at the biggest binary power that can entirely fit in 56. This is 32 = 2⁵. It is not 64 because 56 does not fit entirely into 64.
• Then we take the remainder of 56 - 32 = 24. We check which is the biggest binary power that can entirely fit into 24. This is 16 = 2⁴.
• Then we take the remainder of 24 - 16 = 8. We check which is the biggest binary power that can entirely fit into 24. This is 8 = 2³.
• Finally 8 - 8 = 0 so we have reached the end.

Now we mark the powers of two that we used for our calculus as a binary 1 and the other powers as 0. We get 00111000

decimal to binary conversion table

	27	26	25	24	23	22	21	20
=	128	64	32	16	8	4	2	1
=	0	0	1	1	1	0	0	0

How are floats represented in binary ?

Section to go more in-depth on the content.

Floats are typically represented in 4 bytes. Out of these 32 bits: 1 bit is used for the sign of the number, 8 bits are used for the exponent and 23 bits are used for the floating point of the number. It is a way of storing numbers in scientific notation.

It is interesting to note that if we want to represent negative and positive numbers (whole numbers or decimal) we need to use one bit for storing the sign. If we only store positive numbers we don't need to keep that sign bit.

Exercises - Binary representation of numbers

1. What is the decimal representation of 1001 ?

2³ + 2⁰ = 8 + 1 = 9

2. What is the decimal representation of 01000101 ?

2⁶ + 2²+ 2⁰ = 64 + 4 + 1 = 69

3. What is the binary representation of 42 ?

42 - 32 = 10 with 32 = 2⁴

10 - 8 = 2 with 8 = 2³

2 - 2 = 0 with 2 = 2¹

Hence the binary representation: 00011010

4. What is the binary representation of 129 ?

129 - 128 = 1 with 128 = 2⁷

1 - 1 = 0 with 1 = 2⁰Hence the binary representation: 01000001

5. How many different integers can I represent in 2 bytes ?

2 bytes are 16 bits (2 x 8bits), hence 2¹⁶ = 65536 different numbers can be represented in 2 bytes

6. What is the biggest number I can represent in 2 bytes ?

2 bytes are 16 bits (2 x 8bits), hence 2¹⁶ -1 = 65535 is the biggest number that can be represented in 2 bytes.

It is also helpful to be familiar with number systems that are powers of 2, such as base 8 (octal), and base 16 (hexadecimal). Recall that base 10 has ten digits (0−9), base 2 has two digits (0−1), and base 8 has eight digits (0−7). Therefore, the number 943 could not represent a value in any base less than 10, because the digit 9 does not exist in those bases. It is, however, a valid number in base 10 or any base higher than that. Likewise, the number 2074 is a valid number in base 8 or higher, but it simply does not exist (because it uses the digit 7) in any base lower than that.

What are the digits in bases higher than 10? One needs to assign symbols to represent the digits that correspond to the decimal values 10 and beyond. In bases higher than 10, one generally looks towards letters as digits. The letter A, consequently, will represent the number 10, B to represent 11, C to represent 12, and so forth. All digits are written in the following conversion table.

What is Hexadecimal ?

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

Hexadecimal is a numbering system that uses 16 possible digits. Its primary attraction is its ability to represent very high numbers with fewer digits that in binary or in the decimal system.

How do I convert a decimal number to a hexadecimal number ?

The method is following:

• Apply a floor division to the decimal number by 16. Write down the remainder.
• Continue applying floor division by 16 to the previous result of the floor division until you reach 0. Keep writing down the remainders.
• Convert the remainders, from last one to first one, to hexadecimal.
• You have your hexadecimal number !

For example if we want to convert the decimal number 2545 to hexadecimal:

• We apply floor division: 2545 // 16 = 159, The remainder of that division is 2545 % 16 = 1
• We apply floor division to our previous result: 159 // 16 = 9, The remainder of that division is 159 % 16 = 15
• We apply floor division to our previous result: 9 // 16 = 0, The remainder of that division is 9 % 16 = 9.
• We reached 0 so we stop dividing.
• We convert our remainders: 9 → 9, 15 → F, 1 → 1
• So our hexadecimal number is: 9F1

How do I convert a hexadecimal number to a decimal number ?

This conversion is a bit simpler as we can use the positional notation to convert our number. Indeed we just need to multiply each hexadecimal digit by its corresponding power of 16.

For example if we want to convert the hexadecimal number ABC to decimal we can do the following:

	$A$	$\times$	$16^{2}$	$=$	$10$	$\times$	$256$	$=$	$2560$
$+$	$B$	$\times$	$16^{1}$	$=$	$11$	$\times$	$16$	$=$	$176$
$+$	$C$	$\times$	$16^{0}$	$=$	$12$	$\times$	$1$	$=$	12
									$2748$

How do I convert a binary number to a hexadecimal number ?

To easily convert a binary number to a hexadecimal number you just need to split your binary number in groups of 4 bits. If the length of your binary number is not an exact multiplication of 4, just add 0s to the left side of your binary number until you reach a multiple of 4.

Then convert your groups of 4 bits to their corresponding hexadecimal characters and you will have your hexadecimal number !

For example if we want to convert the binary number: 1011111011

• Our number has 10 bits so we add two 0s to the left side: 001011111011
• We divide our number in groups of 4 bits: 0010 1111 1011
• We convert the binary number to hexadecimal numbers: 0010 → 2, 1111 → F, 1011 → B
• Our hexadecimal number is 2FB

What is Octal ?

Not needed for the exams

Octal is a numbering system in base 8, meaning only digits from 0 to 7 exist in this notation.

For example, one can calculate the decimal equivalent of 754 in octal (base 8) − simply put, finding $754_{8}=k_{10}$. As before, it is the case of expanding the number in its polynomial form and adding up the numbers:

	$7$	$\times$	$8^{2}$	$=$	$7$	$\times$	$64$	$=$	$448$
$+$	$5$	$\times$	$8^{1}$	$=$	$5$	$\times$	$8$	$=$	$40$
$+$	$4$	$\times$	$8^{0}$	$=$	$4$	$\times$	$1$	$=$	$4$
									$492$

Simple logic gates

Use BOOLR to practice using logic gates.

2.1.11 Define the Boolean operators; AND, OR, NOT, NAND, NOR, and XOR.

2.1.12 Construct truth tables using the above operators.

The gates in a computer are sometimes referred to as logic gates because they each perform just one logical function. That is, each gate accepts one or more input values and produces a single output value. Because one is dealing with binary information, each input and output is either 0, corresponding a low-voltage signal, or 1, corresponding to a high-voltage signal. The type of gate and the input values determine the output value.

Gate Definitions

NOT Gate

Boolean Expression	Logic Diagram Symbol	Truth Table
X = A'	AX	A X 0 1 1 0

A NOT gate accepts one input value and produces one output value. The table to the right illustrates a NOT gate in three ways; as a Boolean expression, as its logical diagram symbol, and using a truth table. In each representation, the variable A represents the input signal, which is either 0 or 1. The variable X represents the output signal, whose value (0 or 1) is determined by the value of A.

By definition, if the input value for a NOT gate is 0, the output is 1; if the input value is 1, the output is 0. A NOT gate is sometimes referred to as an inverter because it inverts the input value.

In Boolean expressions, the NOT operation is represented by the ' mark after the value begin negated. Sometimes this operation is shown as a horizontal bar over the value begin negated. In the Boolean expression in the table, X is assigned to the value determined by applying a NOT operation to input value A. In such an assignment statement, the variable on the left of the equal sign takes on the value of the expression on the right-hand side.

The logical diagram symbol for a NOT gate is a triangle with a small circle (called an inversion bubble) on the end. The input and output are shown as lines flowing into and out of the gate. Sometimes these lines are labeled, though not always.

The truth table shows all possible input values for a NOT gate as well as the corresponding output values. Because there is only one input signal to a NOT gate, and that signal can only be 0 or 1, there are only two possibilities for the column labelled A in the truth table. The column labelled X shows the output of the gate, which is the inverse of the input. Note that of the three representations, only the truth table actually defines the behaviour of the gate for all situations.

These three notations are just different ways of representing the same thing, for example, the result of the Boolean expression 0' is always 1, and the result of the Boolean expression 1' is always 0. This behaviour is consistent with the values shown in the truth table.

AND Gate

Boolean Expression	Logic Diagram Symbol	Truth Table
X = A • B	A X B	A B X 0 0 0 0 1 0 1 0 0 1 1 1

Unlike the NOT gate, which accepts one input signal, an AND gate accepts two input signals. The values of both input signals determine what the output signal will be. If the two input values for an AND gate are both 1, the output is 1; otherwise, the output is 0.

The AND operation in Boolean algebra is expressed using a single dot (•) or, in some cases, an asterisk (*). Often the operator itself is assumed, for example A•B is often written as AB.

Because there are two inputs and two possible values for each input, four possible combinations of 1 and 0 can be provided as input to an AND gate. Therefore, four situations can occur when the AND operator is used in a Boolean expression.

Likewise, the truth table showing the behaviour of the AND gate has four rows, showing all four possible input combinations.

OR Gate

Boolean Expression	Logic Diagram Symbol	Truth Table
X = A + B	A X B	A B X 0 0 0 0 1 1 1 0 1 1 1 1

Like the AND gate, there are two inputs to an OR gate. If the two input values are both 0, the output value is 0; otherwise, the input is 1.

The Boolean algebra OR operation is expressed using a plus sign (+). The OR gate has two inputs, each of which can be one of two values, so as with an AND gate there are four input combinations and therefore four rows in the truth table.

XOR Gate

Boolean Expression	Logic Diagram Symbol	Truth Table
X = A ⊕ B	A X B	A B X 0 0 0 0 1 1 1 0 1 1 1 0

The XOR, or exclusive OR, gate is illustrated to the right. An XOR gate produces 0 if its two inputs are the same, and 1 otherwise. Note the difference between the XOR gate and the OR gate; they differ only in one input situation. When both input signals are 1, the OR gate produces a 1 and the XOR produces a 0.

Sometimes the regular OR gate is referred to as the inclusive OR, because it produces a 1 if either or both of its inputs is a 1. The XOR produces a 1 only if its inputs are mixed, one 1 and one 0. Think of XOR gates as saying, "When I say or, I mean one or the other, no both."

The Boolean algebra symbol ⊕ is sometimes used to express the XOR operation. However, the XOR operation can also be expressed using the other operators; we leave that as an exercise.

Note that the logic diagram symbol for the XOR gate is just like the symbol for an OR gate except that it has an extra curved line connecting its input signals.

NAND and NOR Gates

NAND Gate
Boolean Expression	Logic Diagram Symbol	Truth Table
X = (A • B)'	A X B	A B X 0 0 1 0 1 1 1 0 1 1 1 0
NOR Gate
Boolean Expression	Logic Diagram Symbol	Truth Table
X = (A + B)' X = A - B	A X B	A B X 0 0 1 0 1 0 1 0 0 1 1 0

The NAND and the NOR gate accept two input values. The NAND and NOR gates are essentially the opposite of the AND and OR gates, respectively. That is, the output of a NAND gate is the same as if one took the output of an AND gate and put it through an inverter (a NOT gate).

There are typically no specific symbols used to express the NAND and NOR gates operations in Boolean algebra. Instead, one should rely on their definitions to express the concepts. That is, the Boolean algebra expression for NAND is the negation of the AND operation. Likewise, the Boolean algebra expression for NOR is the negation of an OR operation.

The logic diagram symbols for the NAND and NOR are the same as those for the AND and OR except that the NAND and NOR symbols have the inversion bubble (to indicate the negation). Compare the output columns for the truth tables for the AND and NAND. They are the opposite, row by row. The same is true for OR and NOR gates.

Review of Gate Processing

Six specific types of gates have been observed. It may seem to be a difficult task to keep them straight and remember how they all work. Well, that probably depends on how one thinks about it. One should not be encouraged to try and memorise truth tables. The processing of these gates can be described briefly in general terms. If one thinks of them that way, one can produce the appropriate truth table any time needed.

Some of these descriptions are in terms of what input values cause the gate to produce as 1 as a n output; in any other case, it produces a 0:

• A NOT gate inverts its single input value,
• An AND gate produces 1 if both input values are 1,
• An OR gate produces 1 if one or the other or both input values are 1,
• An XOR gate produces 1 if one or the other (but not both) input values are 1,
• A NAND gate produces the opposite results of an AND gate, and
• A NOR gate produces the opposite results of an OR gate.

Constructing Gates

2.1.13 Construct a logic diagram using AND, OR, NOT, NAND, NOR, and XOR.

Combinational Circuits

A combinational circuit consists of logic gates whose outputs are determined at any time from the present combination of inputs irrespective of previous inputs.It consists of input variables, logic gates and output variables. The logic gate accept signals from inputs and generate signals at the outputs.Some of the examples of combinational circuits are binary adder, decimal adder,decoder,multiplexer,half adder, half subtractor etc.

Half adder

A half-adder circuit diagram

A logic circuit for the addition of two one-bit numbers is called a half adder. There must be two bits output: the sum of the addition (either a 1 or 0) and whether or not you carry a bit. The carry comes from the addition of 1 + 1, which equals 10 (binary 2). The addition process is reproduced in this truth table.

A	B	Sum	Carry
0	1	1	0
1	0	1	0
1	1	0	1

Multiplexers

BOOLEAN EXPRESSION:
D0 = X’Y’  ,  D1 = X’Y
D2 = XY’  ,  D3 = XY