SCD - Unit 1.4.3


T1 - Logic Gates and Truth Tables

Binary Switches - Can be ON or OFF, combined to create simple circuits called logic gates

Logic Gates: NOT, AND, OR, XOR and are prioritised in this order

NOT - Input 0 has an output of 1, Input 1 has an output of 0, gate is a triangle with a circle on the end

  • In Boolean: Algerbra - P = NOT A , Notation - P = ¬A

AND - If both inputs are 1 then output is 1, else the output is zero, gate is a D 

  • In Boolean: Algerbra - P = A AND B , Notation - P = A ^ B

OR - If either input is a 1, output is 1, else output is zero, gate is an arrow head

  • In Boolean: Algerbra - P = A OR B , Notation - P = A v B

XOR - If either input is a 1 output is 1 except when both 1 then output is zero, else output is zero, gate is OR gate with an extra curve

  • In Boolean: Algerbra - P = A XOR B , Notation - P = A v B
1 of 11

T1 - Creating logic circuits

All logic gates have their own truth table showing the possible inputs and outputs

Multiple logic circuits can be combined to produce an output based on multiple inputs, so with 3 inputs the number of possible inputs is 23

In order to have every single input then count up in binary on the inputs of the truth table

2 of 11

T2 - Simplifying Boolean Expressions

De Morgan's Laws:

  • 1st law - ¬(A v B) = ¬A ^ ¬B  < Notice the sign change
  • 2nd Law - ¬(A ^ B) = ¬A v ¬B

Steps to implement are - Invert the terms, Change the sign, Invert the result

9 Useful Rules: (Remember that an AND gate = multiply and OR gate = add)

  • X ^ 0 = 0
  • X ^ 1 = X
  • X ^ X = X
  • X ^ ¬X = 0
  • X v 0 = X
  • X v 1 = 1
  • X v X = X
  • X v ¬X = 1
  • ¬¬X = X

3 of 11

T2 - Special Rules

Commutative Rule: (Order doesn't matter)

  • X ^ Y = Y ^ X
  • X v Y = Y v X

Associative Rule: (Multiplying or adding any combination of numbers is the same no matter the order)

  • X ^ (Y ^ Z) = (X ^ Y) ^ Z
  • X v (Y v Z) = (X v Y) v Z

Distributive Rule: (Bracket expansion like in maths)

  • X ^ (Y v Z) = (X ^ Y) v (X ^ Z)
  • (X v Y) ^ (W v Z) = (X ^ W) v (X ^ Z) v (Y ^ W) v (Y ^ Z)

Absorption Rule: (If two terms exist in a trio then the pair is always the answer)

  • X v (X ^ Y) = X
  • X ^ (X v Y) = X
4 of 11

T2 - Breaking down Logic Gates

In a circuit diagram each logic gate can be broken down to find the boolean expression that it represents by labeling the output from each gate going left to right

When simplifying boolean expressions the logic gates go in the order:

  • NOT
  • AND
  • OR
  • XOR
5 of 11

T3 - Karnaugh Maps

Karnaugh maps are similar to truth tables and are used to lay out boolean expressions and are often an easier method of simplifying expressions

When drawing a karnaugh map place a 1 in the corresponding box(es) when the output is true/1

Expressions can then be grouped by placing a box around a group of 1's and they can only be in groups of 2x but can wrap around the table when there are more than two variables

When you make a group of 1's you produce an expression which outputs those values when true

It is better to have groups as large as possible as it means that the expression simplifies down a lot more

6 of 11

T3 - Greater than 2 variable karnaugh maps

When using expressions with 3 or more expressions you combine two across the columns, the combination does not matter (so for a 3 varaible map you could have AB on the top and C on the side)

As a result of this you need to increase the number of bits so all the possible combinations are there

For a 3 varaible karnaugh map the terms increase in the order: 00, 01, 11, 10 , this is not numerical order as only 1 bit can be changed at a time

7 of 11

T4 – D-type flip-flops, adders and half-adders

In order to perform and two bit addition you need to use logic gate circuits, there are two specific ones called half adders and full adders

Half Adder- Takes the input of bits A and B and outputs the result S and the carry bit C

  • represents the sum: S = A v B - XOR gate as the addition of two 1's produces a zero
  • represents the carry bit: C = A ^ B
  • If A and B are both equal to 1, S = 0 and C = 1

As a half adder only has two inputs it cannot carry from a previous addition and is only able to handle one-bit numbers

8 of 11

T4 - Full Adders

Full Adder:

  • Combination of two half-adders
  • Has 3 inputs, A, B and the carry bit Cin and two outputs S and Cout
  • Cin is the carry bit from the previous operation

Multiple full adders can be connected to perform multi-bit addition with each adder having two new inputs

If needed the first adder can be made into a half-adder as the least significant bit will never have a carry bit

9 of 11

T4 - Edge-triggered D-type flip-flops

A flip flop is an elemental sequential logic circuit able to store one bit and flip between two states, 0 and 1

  • It has two inputs D and the clock signal
  • It has two outputs and NOT Q

Clock -  Sequential circuit that changes state at regular time intervals and is needed to change the state of flip flop circuits

  • An edge-triggered D-type flip-flop only changes on the rising edge of the clock signal

D-type flip-flops can be used as memory units:

  • Output Q only takes on a new value if value of D has changed at rising edge of clock pulse
  • Next clock pulse 'freezes' or 'stores' the input value D in Q until the next clock pulse
  • What happens inbetween the clock pulses at D does not matter (Q remains the same and will only ever change on a rising clock edge if the value at D has changed)
10 of 11

T4 - Edge-triggered D-type flip-flop uses

D-type flip-flops have many real world uses:

  • Creating registers and counters
  • Intermediate storage during arithmetic operations
  • Static RAM uses D-type flip-flops
    • This is faster and more expensive then regular dynamic (D) RAM which needs periodic refreshing as charge can deplete
    • Typically used for cache memory while DRAM is used for main memory

It can be used for intermediate storage in the FDE cycle as each operation only takes one clock cycle so each clock cycle the value in D is read and and output Q is produced

11 of 11


No comments have yet been made

Similar Computing resources:

See all Computing resources »See all Fundamentals of computer systems resources »