Logic Gates - Truth Tables

The term 'Boolean' derives from the surname of the 19th century mathematician, George Boole. His shorthand notation for logic was based on theories set forth by Aristotle and others.

In short, a boolean variable can hold one of two values, true or false. Often, these variables are recast to 1 and 0 in computers.

We can see how these boolean values are represented in a simple circuit in the following diagram,

When the circuit is completed, we get the boolean value of 1, when it is not complete, we get a value of 0.

The OR Function

The OR function has two inputs, X & Y. The output for each combination of inputs is shown in the truth table below.

X	Y	Q
0	0	0
0	1	1
1	0	1
1	1	1

The OR function returns a 1 if either or both of the inputs are 1.

The Boolean equation for this circuit describes the output Q in terms of the inputs, X and Y. We use the addition sign to indicate OR.

X + Y = Q

The AND Function

The AND function takes two inputs and produces an output based on those values.

The truth table is as follows.

X	Y	Q
0	0	0
0	1	0
1	0	0
1	1	1

The Boolean equation for this circuit describes the output Q in terms of the inputs, X and Y. We use the full stop to indicate AND.

X.Y = Q

The NOT Function

The NOT function takes a single input. The output is always the inverse of the input.

Y	Q
0	1
1	0

We draw a bar over any variable that is passed through a NOT gate.

X = Q

Other Functions

The three functions that you have seen so far are the fundamental functions. By combining the circuits that represent these functions, we can create some ones which are also useful to us.

Three other functions that you will meet are,

• Exclusive Or (XOR)
• NAND
• NOR
• XOR

X	Y	Q
0	0	0
0	1	1
1	0	1
1	1	0

The XOR function takes two inputs and returns true if either (but not both) are set to 1. The boolean equation for this is,

A.B + A.B = Q

NAND

The NAND function is a combination of the AND & NOT functions. It's truth table is as follows,

X	Y	Q
0	0	1
0	1	1
1	0	1
1	1	0

Since NAND means NOT AND, we only get an output of false if both inputs are true. The boolean expression for this function is,

A.B = Q

NOR

The NOR function is a combination of the OR & NOT functions. It's truth table is as follows,

X	Y	Q
0	0	1
0	1	0
1	0	0
1	1	0

Since NOR means NOT OR, we only get an output of false if both inputs are false. The boolean expression for this function is,

A + B = Q

Logic Gates - Diagrams

Symbols

The following tables show the symbols that you should use in your circuit diagrams. Although the symbols are new to you, you will quickly spot the easy ways to remember which one is which.

We can construct circuits from boolean expressions or derive boolean expressions from our circuit diagrams. The following circuit diagram represents the boolean expression Q = A.B + C.D.

The labels E & F can be used as an intermediate stage to writing an expression for the circuit solely in terms of its inputs.

For example,

• E = A.B
• F = C.D
• Q = E + F
• Q = A.B + C.D

Example

Consider the following circuit diagram.

We can write out a truth table for this diagram to show its logic operates.

A	B	C	D	Q
0	0	0	1	0
0	1	1	1	1
1	0	1	1	1
1	1	1	0	0

Column C is A + B (A OR B), Column D is A.B (A NAND B) and Q is C.D (C AND D).

Looking carefully at the truth table, we can see that this circuit performs the same logic as the XOR gate.

Chapter 7_1 Logic Gates.pptx

Boolean Algebra

Look back through the last two pages. At every turn, we have been writing out expressions using boolean variables and the two symbols that express And & OR.

A few additional pieces of information will allow us to manipulate boolean expressions algebraically.

De Morgan's Laws

You can look for a fuller explanation on T'Internet in your own time but, in their simplest form, these laws are,

Look at the laws carefully. In each equation, the sign is changed from AND to OR or from OR to AND. The individual terms have a bar over them to indicate NOT. The whole of the expression has a bar over it. The following three steps describe this process succinctly,

1. NOT the sign
2. NOT the individual terms
3. NOT the lot

The implication for us is that, by substituting these values in boolean expressions, we can convert expressions to forms that require only the use of NOT & OR (NOR) functions or just NOT & AND (NAND) functions.

It is possible to make any logic circuit using only NOR or only NAND gates. Try it out for yourself. You should be able to create a circuit that results in the same output as any of the other logic gates - try it out for yourself. The advantage of this comes in manufacturing where costs can be kept down when only one type of gate is used.

Some Other Rules To Bear In Mind

Commutative Laws

A + B = B + A

A.B = B.A

Associative Laws

A + (B + C) = (A + B) + C

A.(B.C) = (A.B).C

Distributive Laws

A.(B + C) = (A.B) + (A.C)

A + (B.C) = (A + B).(A + C)|

Tautology Laws

A.A = A

A + A = A

A + A = 1

A.A = 0

Double Complement Law

A = A

Absorption Laws

A + (A.B) = A

A.(A + B) = A

Common Sense Laws

If you can't see why, draw a simple circuit with a power supply and lamp - you'll see.

0.A = 0

1 + A = 1

1.A = A

0 + A = A

0 = 1

1 = 0

Example

boolean algebra and reduction.ppt

Chapter 7_1 De Morgans Laws.pptx

Section 71 Revision Cards Textbook Definitions.ppt

Computer Architecture

Three-Box Model

The three-box model is the simplest way to represent the internal components of a computer system.

Processor

The main job of the processor is to execute programs and supervise and control the functioning of the other components.

Main Memory

Main memory is the location where instructions and data are stored. Memory is principally made up of RAM chips but may include one or more ROM chips.

Random Access Memory

Random access memory is readable and writable. RAM is volatile, its contents are wiped every time that the computer is switched off.

Read-Only Memory

ROM chips provide fast-access to non-volatile information. It tends to be used to store the instructions required to load the computer system.

Buses

A bus is a set of parallel wires that connect components of the computer system together. The bus that connects the boxes in the above diagram is known as the System or External Bus. In reality, this tends to be divided into three buses which carry different types of information.

Data Bus

A bi-directional bus transporting data between components, typically consisting of 32 parallel wires.

Address Bus

A uni-directional bus, typically consisting of 32 wires, used to address memory and IO locations.

Control Bus

A bi-directional bus, typically consisting of 8 wires. It is used to transport control signals between the components.

Typical control lines include,

• Memory Write - causes data on the data bus to be written into the addressed location.
• Memory Read - causes data from the addressed location to be placed on the data bus.
• I/O Write - causes data on the data bus to be output to the addressed I/O port.
• I/O Read - causes data from the addressed I/O port to be placed on the data bus.
• Transfer ACK - indicates that data have been accepted from or placed on the data bus.
• Bus Request - indicates that component needs to gain control of bus.
• Bus Grant - indicates that a requesting component has been granted control of the system bus
• Interrupt request - indicates that an interrupt is pending.
• Interrupt ACK - acknowledges that the pending interrupt has been recognised.
• Clock - used to synchronise operations.
• Reset - initialises all components.

Expanding The Three-Box Model

In examinations, you may be presented with an expanded version of the above diagram. You are likely to have to identify some of the components.

You may see something like this,



Suppose that you are presented with the following diagram and asked to match up the names of components to the numbers on the diagram. The names of the components that you need to match are, processor, ROM, RAM, address bus, data bus and clock.



Clock: The role of the clock is to send timing signals. It is connected directly to the processor and not along any of the three buses. Item number 1 is the only box not connected to a bus and must therefore be the clock.

Processor: The processor is connected directly to the clock and must therefore be box number 2.

Address Bus: Wire number 6 must be the address bus. The processor is the only component that can place addresses on the bus.

Data Bus: Wire number 5 must therefore be the data bus.

ROM Common sense tells us that, since ROM is read-only, it must be the box that does not accept data from the data bus - box 3.

RAM Similarly, RAM must be the box that has a bi-directional connection to the data bus.




Bus Direction.pptx

Von Neumann Machines - questions.pptx

Von Neumann Machines.pptx

Chapter 7 2 Computer Architecture Part 1.pptx

Section 7 2 Revision Cards Textbook Definitions.ppt

Structure of the Processor

Components Of The Processor

ALSO SEE PREZI BELOW

A processor contains the following components,

• Control Unit - fetches, decodes, executes instructions.
• Arithmetic & Logic Unit - performs arithmetic and logical operations on data.
• Registers - fast, on-chip memory inside the CPU, dedicated or general purpose.
• Internal Clock - derived directly or indirectly from the system clock
• Internal Buses - to connect the components
• Logic Gates - to control the flow of information

What Is A Register?

Registers are storage locations within the circuitry of the CPU. They are very fast on-chip memory storing binary values using 32 or 64 bits. Information is held there while it is being interpreted or manipulated. Registers are dedicated or general purpose.

General Purpose Registers

Can be used by programmers to store data temporarily. Some computers may have up to 16 general purpose registers (R1...R16). Processor designers have assigned no specific role to these registers.

Stack Pointer (SP)

Points to a stack data structure holding return addresses, procedure or function parameters and local variables. Used when a procedure or function is called. Also used when an interrupt is serviced. (Interrupt = a signal from a source (hardware or software) requesting the attention of the processor)

Program Counter (PC)

Holds the address in main memory of the next instruction to be executed.

AKA Sequence Control Register (SCR) or Sequence Register.

Status Register (SR)

Contains bits that are set and cleared based on the results of an instruction. Allows the CPU to store information such as the occurrence of an overflow. This information can be used to decide whether or not to branch out of a given sequence of instructions.

The Accumulator

Holds the result of the current set of calculations. The instruction ADD #25 means add the value 25 to the contents of the accumulator and store the result in the accumulator.

Current Instruction Register (CIR)

Stores operator and operand for the current instruction.

Eg LDA 1000 (Load location 1000 into Accumulator)

LDA operator what you do
1000 operand what you do it to

Memory Address Register (MAR)

Holds the address of the memory location from or to which data is to be read or written. This could be the address of an instruction to be fetched or the address of data to be used in the instruction. When fetching instructions, copies the contents of the Program Counter.

Memory Buffer Register (MBR)

AKA Memory Data Register (MDR) Temporarily stores data read from or written to memory. CPU and Memory operate at different speeds (hence buffer)

Eg LDA 1000 placed here en route to the CIR for decoding.

Operand (1000) placed in MAR. Contents of 1000 copied to the MBR.

System Clock

Every computer has a system clock. The clock is a quartz controlled oscillator supplying timing signals at a fixed rate. Other timing signals are derived from this. These signals are used to regulate the execution of instructions and to synchronise the operation of the computer components.

Clock Speed

Processors are designed to execute instructions at a particular frequency. Expressed in Megahertz or Gigahertz. Some instructions require more ticks of the clock than others.

Word Length

The word is the smallest chunk of memory that a program can refer to independently. The length of the word limits the complexity of the instruction set and the efficiency of mathematical operations.

Bus Width

This term refers to the number of parallel wires allocated to a bus. The number of wires determines how large a word can be transferred over the bus. Each wire can transfer a binary digit. Word size increases with bus width.

Factors Affecting Performance

The performance of a computer system can be measured by running standard programs on the processor and assessing the number of machine operations completed for each unit of time.

Measured in GOPS - Giga-Ops Per Second (or MOPS)

Moore's Law

Gordon E Moore - Engineer and co-founder of Intel. In 1965, for a special issue of the journal Electronics, Moore was asked to predict developments over the next decade. In reviewing past increases in the number of transistors per silicon chip, Moore formulated what became known as Moore's law: The number of transistors per silicon chip doubles each year.

Increase Clock Speed

The more transistors packed into the same space, the more heat generated by their operation. Quantum physics suggests theoretical limits on transistor size. Similarly, the higher the frequency of clock ticks, the more heat generated. Both factors place limits on clock speed.

Multicore Processors

Processors are arranged into several cores. Each core runs at a lower frequency. Multiple tasks are run at the same time on different cores or tasks are split across several cores. Multicore processors are particularly suited to multimedia work.

Increase Word Length

Typical processor word lengths are 32bit and 64bit. General purpose registers usually have a similar word length. The bigger the word length, the bigger the operands and the results. When an operand is larger than the word length, it must be split into multiple instructions, requiring more clock ticks. Word length also limits the number of storage locations that can be addressed in main memory. For this reason, there is a limit on how much memory can be addressed in a computer system with a 32bit word size.

Increase Bus Width

The system bus between the processor and main memory accounts for the worst time penalty in processing. The wider the bus, the larger the word that can be transferred along it. Where an address or instruction is wider than the bus, multiple clock ticks are required for processing.

Machine Code Operations

Machine Code

We already know that the language of the digital computer is binary. The patterns of 1's and 0's represent both the data we want to work with and the instructions we want the computer to carry out.

A machine operation is usually expressed in two parts. 32 bits are typically used to express the entire instruction which is divided into,

Operation Code + Operand

The operation code represents a specific machine operation (eg add, load, store). The operand is an item of data or an address of an item of data.

High & Low-Level Languages

C# is a high-level compiled language. We write our programs using statements which are easily understandable to us. When we compile our source code into object code (the machine code instructions that the computer can understand), the statements we wrote in C# are converted into the binary patterns that represent these instructions translated into machine code. Each high-level statement may require many machine code operations.

Assembly language is a low-level language. Instead of writing out binary patterns, the programmer uses mnemonics - a word like LOAD is used in place of the binary pattern that represents this machine operation. Assembly programs are turned into executable machine code using an assembler. Unlike with the high-level compiled language, each statement in assembly language has a single equivalent in machine code.

Assembly Language Instructions

The term Instruction Set is used to refer to the list of binary patterns that represent the machine operations of a specific processor. Low-level languages are platform-specific. Each processor has its own set of instructions and requires a different assembler to turn the programs into machine code. You should also appreciate that low-level programming requires a level of detail and a regard for the architecture of the specific machine that is being programmed that makes it more time-consuming to write than a high-language program. It is used where specific machine registers need to be accessed, where programs need to address specific memory locations, occupy as little space in memory as possible or execute very quickly.

At this stage, you do not need to be able to write programs in Assembly. You do need to appreciate its uses and limitations as well as recognise roughly what the program may look like.

Remember that the operand part of the machine code instruction could refer to data, an address in memory and may include a reference to a general-purpose machine register. The following examples show this,

LOAD #5 - Load the value 5 into the accumulator
STORE 27 - Store a copy of the accumulator in memory location 27
ADD R1, #46 - Add the value 46 to the contents of machine register R1

The meaning of the operand is determined by what is called the addressing mode. The hash symbol in operands tends to mean that the number which follows is a value and not the address of a location in main memory.

Addressing Modes

Immediate Addressing

The operand contains the value that is being operated on,

LOAD #11101011B - Load the binary value 11101011 into the accumulator
LOAD #&84 - Load the hex value 84 into the accumulator

Direct Addressing

The operand contains an address of a location in memory which contains the value to be operated upon,

LOAD 35 - Load the contents of memory location 35 into the accumulator.

Indirect Addressing

The operand contains an address of a location in memory. This location contains the address of the location in memory where the value is stored,

LOAD (1000) - load the contents of the memory location whose address is stored in location 1000.

Indexed Addressing

Indexed addressing is used in machines containing an index register. With this mode of addressing, values in the operand are incremented by the value stored in the index register,

LOAD X, #50 - load into the accumulator the contents of the location in memory which is formed by adding 50 to the contents of register X

Base Register Addressing

Similar to indexed addressing except that a base address is stored in a register. The address field contains an offset which is added to the base address to form the address to be used in the operation.

LOAD 35, B - load the contents of the address formed by adding 35 to the base address stored in register B.

Relative Addressing

Used to branch to an address relative to the instruction held in the Program Counter.

JMP +100 - branch to the instruction 100 bytes on.

The advantage of using Base Register and Relative addressing modes is that programs can become relocatable in memory.

The Fetch-Execute Cycle

Stored program computers are designed to fetch, decode and execute instructions in a continuous cycle. This is known as the fetch-execute cycle.

Fetch

1.The Program Counter (PC) contains the address of the next instruction to be fetched
2.The address contained in the PC is copied to the Memory Address Register (MAR).
3.The instruction is copied from the memory location contained in the MAR and placed in the Memory Buffer Register (MBR).
4.The entire instruction is copied from the MBR and placed in the Current Instruction Register (CIR)
5.The PC is incremented so that it points to the next instruction to be fetched

Execute

1.The address part of the instruction is placed in the MAR
2.The instruction is decoded and executed
3.The processor checks for interrupts (signals from devices or other sources seeking the attention of the processor) and either branches to the relevant interrupt service routine or starts the cycle again.

Demonstration

The following presentation shows the way that registers are used during the fetch-execute cycle. Save the file to your computer before loading it up. Advance the slideshow by clicking the mouse. There is a lot of information on the screen and you will get the best out of this demonstration by taking your time and making sure that you can clearly see what has happened before moving on.

fedemo.ppt by C Traynier

Example Animations:

Fetch-execute cycle
Execute Cycle
Sample Program

Other files:

Fetch Execute Cycle.ppt
Stored program concept + CPU.pptx
Fetch Execute - Animated in Powerpoint.ppt
COMP2 Fetch Execute.pdf