Binary Subtraction using Logic Gates

Posted on February 10, 2021 by Administrator Posted in A Level Concepts, Computer Hardware, Computer Science, Computing Concepts, Physical Computing

In our previous blog post “from transistors to processors” we found out that the CPU consists of logic gates, which are made using transistors.

In this blog post we are looking at how these logic gates can be combined to create an integrated circuit used by the ALU (Arithmetic and Logic Unit of the CPU) to perform a binary subtraction of two 8-bits binary numbers.

Half-Subtractor Circuit

A half-subtractor circuit is used to perform a binary subtraction of two bits of data. It is based on the following Truth Table.

A half-subtractor circuit consists of three logic gates as follows:

Full-Subtractor Circuit

A full-subtractor circuit is used to perform a binary subtraction using three bits of data and is based on the following Truth Table:

A full-subtractor circuit consists of two half-subtractor circuits and an OR gate connected as follows:

Full Binary Subtraction

By connecting one half-subtractor circuit with seven full-subtractor circuits we can create a circuit to implement a full binary subtraction of two 8-bits binary numbers:

Alternative Approach

An alternative approach is to design a circuit that can be used to complete both full binary additions and full binary subtractions of two 8-bit inputs.

This can be achieved using 8 full-adder circuits and 8 XOR gates connected as follows: On this “2-in-1 circuit” the Mode input is used to decide if an addition (Mode=0) or a subtraction (Mode=1) is performed.

Tagged with: logic gates

8-bit ALU using Logic Gates

Posted on February 9, 2021 by Administrator Posted in A Level Concepts, Computer Hardware, Computer Science, Computing Concepts, Physical Computing

In this post we will create an Arithmetic & Logic Unit (ALU) using logic gates. The ALU is one of the main component of the CPU. It is used in the Execution stage of the FDE cycle to perform all the logical (e.g. AND, OR, NOT) operations and all the arithmetic calculations (e.g. ADD, SUB instructions).

Our ALU will perform 4 different operations: three logical operations (NOT, OR and AND) and one arithmetical operation (ADD: +). Here is the instruction table for our ALU:

The ALU will have a built-in 2-to-4 binary decoder that can decode 2-bit instructions represented by inputs F₀F₁.

The Logic unit of our ALU will apply a NOT mask to input A or an OR and an AND masks to inputs A and B.

The Arithmetic unit will use a full adder to perform an addition of A and B (including carried values) and output the binary sum and the carry out value.

1-bit Arithmetic & Logic Unit

Here is the logic gates diagram for out 1-bit ALU:

8-bit Arithmetic & Logic Unit

Let’s represent our 1-bit ALU with the following diagram:

By connecting eight 1-bit ALUs together, we obtain an 8-bit ALU:

8-bit Arithmetic & Logic Unit

Note that a single decoder can be used to control all the 1-bit ALUs. There is no need to replicate this decoder eight times.

The last carried value can be used to detect overflows when performing a binary addition on the two Bytes of data A and B.

Tagged with: CPU, logic gates

Binary Shifters using Logic Gates

Posted on February 9, 2021 by Administrator Posted in A Level Concepts, Computer Hardware, Computer Science, Computing Concepts, Physical Computing

A binary shift is a binary operation that consists of shifting all the digit of a binary number either to the left or to the right by a fixed amount. Binary shifts can be used to multiply a number by a power of 2 (left shift) or to divide a number by a power of 2 (right shift).

Binary Left Shift

A binary left shift is used to multiply a binary number by two. It consists of shifting all the binary digits to the left by 1 digit and adding an extra digit at the end with a value of 0.

Binary Right Shift

A binary right shift is used to divide a binary number by two. It consists of shifting all the binary digits to the right by 1 digit and adding an extra digit at the beginning (to the left) with a value of 0.

8-bit Binary Shifters

A binary shifter is a logic gates circuit that takes a takes a binary input (A) and performs either a left shift or a right shift and outputs the result (S). On the diagram below, input D is used to decide whether a left shift (D=0) or a right shift (D=1) is applied.

Tagged with: logic gates

Binary Comparators using Logic Gates

Posted on February 8, 2021 by Administrator Posted in A Level Concepts, Computer Hardware, Computer Science, Computing Concepts, Physical Computing

Binary comparators are logic gates circuit used to compare two binary inputs. There are two types of binary comparators:

Equality Comparators are used to check if the two binary inputs (A and B) are equal or not.
Magnitude Comparators are used to fully compare two binary inputs A and B and produce three possible outpus if A>B, A==B or A

On this post we will focus on Magnitude Operators. You can use this link to find out more about Equality Comparators.

1-bit Magnitude Comparator

A 1-bit magnitude operator compare two 1-bit inputs A and B and is based on the following Truth Table:

And here is the logic gates diagram for this circuit:

1-bit Magnitude Comparator Logic Gates Diagram

You can test this circuit by clicking on the picture below:

4-bit Magnitude Comparator

We can now combine several of the above diagrams to create a 4-bit magnitude comparator as follows:

8-bit Magnitude Comparator

We can then combine two 4-bit magnitude comparators to create an 8-bit magnitude comparator. The first 4-bit-comparator will compare the 4 most significant digits whereas the second will focus on the 4 least significant digits.

Tagged with: logic gates

Binary Decoders using Logic Gates

Posted on February 5, 2021 by Administrator Posted in A Level Concepts, Computer Hardware, Computer Science, Computing Concepts, Physical Computing

A decoder is a logic circuit that converts a coded input to a “decoded” output by converting the input into a different format. Binary decoders can be used to:

Convert BCD/binary value into “denary format”, “octal format” or “hexadecimal format”,
Decoding the opcode of an instruction (Decode stage of the FDE Cycle).

One of the key characteristics of a decoder is the number of inputs and the outputs of its logic circuit. Generally the input code has fewer bits than output code. In this blog post we will investigate the most commonly used binary decoders: 2-to-4 decoder, 3-to-8 decoder and 4-to-16 decoder.

2-to-4 Binary Decoder

A 2-to-4 binary decoder has 2 inputs and 4 outputs. It can be used to convert any 2-bit binary number (0 to 3) into “denary” using the following truth table:

2-to-4 Binary Decoder Logic Gates Diagram

3-to-8 Binary Decoder

A 3-to-8 binary decoder has 3 inputs and 8 outputs. Its logic gate diagram is very similar to the 2-to-4 logic gates diagram, combining a few extra NOT and AND gates to generate the 8 required outputs. It can be used to convert any 3-bit binary number (0 to 7) into “octal” using the following truth table:

Logic Gates Diagram:

3-to-8 Binary Decoder Logic Gates Diagram

4-to-16 Binary Decoder

A 4-to-16 binary decoder has 4 inputs and 8 outputs. It can easily be created by combining two 3-to-8 decoders together and can be used to convert any 4-bit binary number (0 to 15) into “hexadecimal” using the following truth table.

Instruction Decoder

Note that a 4-to-16 Decoder can be used as an instruction decoder to decode 4-bits opcodes from a recently fetched instruction. Each output pin corresponding on one of the low level instruction (e.g. in LMC: LDA, STA, ADD, SUB, BRP, BRZ, BRA, HLT etc…). This is how the decode stage of the FDE cycle is implemented using logic gates!

Whereas binary decoders are used to implement the Decode stage of the FDE cyle, the Fetch stage is implemented using Multiplexers.

Tagged with: logic gates

Equality Comparators using Logic Gates

Posted on February 5, 2021 by Administrator Posted in A Level Concepts, Computer Hardware, Computer Science, Computing Concepts, Physical Computing

An equality comparator is a hardware electronic circuit made from logic gates that takes two binary numbers as input determines whether these are equal or not. Equality comparators and magnitude comparators (used to determine whether a binary input is larger, lower or equal to another binary input) are used in central processing units (CPUs) and microcontrollers.

XNOR Logic Gate

An XNOR logic gate can be used to compare two 1-bit inputs and as it outputs 1 if both inputs are the same, and 0 if they are different:

Truth Table of an XNOR logic gate

4-bit Equality Comparator

Two binary inputs are equal if all their bits are equal. We can therefore design a multi-bit equality comparator by combining several XNOR gates together to compare each bit of both inputs.

For instance, here is the logic gate diagram of a 4-bit equality comparator:

4-bit Digital Equality Comparator Logic Gates Diagram

Logic Gates Studio

You can recreate this circuit online using the our logic gates circuit simulator.

4-bit Digital Equality Comparator Circuit

Logic.ly

You can recreate this circuit online using the logic.ly circuit simulator.

4-bit Digital Equality Comparator Circuit using logic.ly

Tagged with: logic gates

Square Root Estimation Algorithms

Posted on February 4, 2021 by Administrator Posted in Computer Science, Python - Intermediate, Python Challenges, Solved Challenges

Calculating the square value of a number is a very straightforward
process which consists of multiplying this number by itself. For instance:

15² = 15 x 15 = 225

The reverse operation which consists of calculating the square root of a number is not so easy without using the square root function of a calculator. In this blog post we will investigate how to accurately calculate the square root of a number using Python and we will then implement and compare two methods that were used a few centuries ago to estimate the square root value of any given number:

The Babylonian Method,
The Bakhshali Method.

Exponentiation

High level programming languages such as Python have an arithmetic operator to raise a number to the power of an exponent.

In pseudocode the exponentiation operator is the ^ operator.
For instance: 3² appears as 3^2 when using pseudocode.

In Python, the exponentiation operator is **. e.g.:

# 5 to the power of 2 is 25
square = 5 ** 2
# 5 to the power of 3 is 125
cube = 5 ** 3

Square Root = To the power of half

We can easily calculate the square root of a number in a computer program using the exponentiation operator knowing that:

√x = x^½ = x^0.5

So in Python:

# Square root of 25 is...
sqrt = 25 ** 0.5

The Babylonian method

Procedures for calculating/estimating square roots have been known since at least the period of ancient Babylon in the 17th century BCE. Heron’s method (aka Babylonian method) from first century Egypt was the first ascertainable algorithm for computing square root.

This approach is based on estimating the limit of the following convergent sequence:

To implement the Babylonian method of estimating a square root we will use the following algorithm:

Python Code

Use the above flowchart to complete the code below:

The Bakhshali method

This method for finding an approximation to a square root was described in an ancient Indian mathematical manuscript called the Bakhshali manuscript. It uses a similare approach the Babylonian method using a different convergent series as described below:

Your task is to adapt your Python script to implement the Bakhshali method and compare how both series perform to estimate a square root value using a fixed number of iterations.

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area

Multimedia Library (OOP Concepts)

Posted on January 28, 2021 by Administrator Posted in Computer Science, Computing Concepts, OOP Concepts, Python - Advanced, Python Challenges

In this blog post, we will write a computer program to create and maintain a multimedia library of books, CDs and DVDs. The aim of this programming task is to demonstrate some key Object-Oriented Programming concepts such as:

Creating Classes and Objects,
Using Derived Classes (implementing Inheritance),
Using an Abstract class,
Implementing over-riding Polymorphism,
Implementing over-loading Polymorphism.

Class Diagram

This project will be based on the following class diagram:

The Library class will be used to maintain a list of items (Books, DVDs, CDs). It will have a range of methods to:

Add a new item to the list of items,
Remove an item from the list of items,
View the full list of items,
Reset/Empty the list of items,
Find out the number if items in the library.
Find out if the library is empty.

Abstract Class

The Item class is an abstract class: It will not be used to instantiate objects directly from this class. Instead, objects will be instantiated from the three derived classes Book, CD and DVD.

Inheritance

This class diagram clearly shows the inheritance relationship between the Item class and the Book, CD and DVD classes:

The Item class is the parent class (also called master class or super class)
The Book class, CD class and DVD class are the derived classes (also called sub classes or child classes).

When a class such as the Book class inherit from a parent class (Item class), it inherits all the properties and methods from the parent class. Hence a book will inherit the title and the description properties as well as the viewDescription() method from the Item class.

Additional properties and methods can be added to a derived class. For instance the Book class as its own specific properties: author and isbn.

Over-Riding Polymorphism

The viewDescritpion() method is an example of over-riding polymorphism: It has been defined in the parent Item class as an abstract method. It is then implemented differently in the derived classes Book, CD and DVD. You can check the Python code in the trinket below to see the three different implementations of the viewDescription() method in the Book, CD and DVD classes.

Over-Loading Polymorphism

We did not implement over-loading polymorphism in this example as it is not directly supported in Python. Over-loading polymorphism is used when the same method is implemented several times within a class, each time accepting a different set of parameters (either a different number of parameters, or using parameters of different data types).

For instance, we could implement over-loading polymorphism to the addItem() method of the Library class as follows:

def addItem(self, item): #the item parameter is an object (e.g. Book, CD or DVD)#
   self.items.append(item)

def addItem(self, title, description, author, isbn):
   book = Book(title, desription, author, isbn)
   self.items.append(book)

def addItem(self, title, description, artist, genre, numberOfTracks):
   cd = CD(title, desription, artist, genre, numberOfTracks)
   self.items.append(cd)

def addItem(self, title, description, director, certificate):
   dvd = DVD(title, desription, director, certificate)
   self.items.append(dvd)

You can read this article to find out how to implement overloading polymorphism in Python using the multipledispatch library.

Python Code

Here is the Python code for our multimedia library project:

Tagged with: OOP

MP3 Playlist Class

Posted on January 27, 2021 by Administrator Posted in Computer Science, OOP Concepts, Python - Intermediate, Python Challenges

The aim of this challenge is to implement a Class in Python to maintain an MP3 Playlist. This class could be used when developing the software for a music App on a smartphone or an mp3 player.

This MP3 playlist will be stored as a queue of MP3 tracks. When new tracks are being added to the playlist, they are enqueued at the end of the playlist. The key features that we will implement within this class are the ability to:

Here is the class diagram for this project:

Python Code

We have started the code used to load a mp3 playlist from a text file.
Your task is to complete this code to implement all the methods mentioned above.

Solution (Step by step)

load() & save()enqueue()remove()getNumberOfTracks()getTotalDuration()shuffle()reset()isEmpty()

The load() and save() methods are used to load a playlist from a CSV file and save it on the CSV file. The save method() will overwrite the playlist if it already exists or create a new file if the file does not exists.

Here is the code to add to the Playlist class:

def load(self):
    self.tracks = []
    print("Loading tracks from CSV file.")
    file = open(self.filename,"r")
    for line in file:
      fields = line.split(";")
      track = Track(fields[0],fields[1],int(fields[2]))
      self.tracks.append(track)    
    file.close()
    
def save(self):
    print("Saving your playlist...")
    file = open(self.filename,"w")
    for track in self.tracks:
      file.write(track.title + ";" + track.artist + ";" + str(track.duration)+ ";")
    file.close()
    print("Playlist saved!")

In the main program we can test our load() and save() methods using the following code:

from playlist import Track, Playlist

myPlaylist = Playlist("Pop Music","pop_music.csv")
myPlaylist.load()
myPlaylist.view()

#Add or remove tracks or shuffle the playlist... using the enqueue(), remove() and shuffle() methods.

myPlaylist.save()

The enqueue() method from the Playlist class is used to append a track at the end of the tracks list:

def enqueue(self, track):
    self.tracks.append(track)

You can test this code as follows:

from playlist import Track, Playlist

myPlaylist = Playlist("Pop Music","pop_music.csv")
myPlaylist.load()

newTrack = Track("Wonderwall","Oasis",245)
myPlaylist.enqueue(newTrack)
myPlaylist.view()

myPlaylist.save()

The remove() method from the Playlist class is used to remove a track from the track list:

def removeTrack(self, track):
    self.tracks.remove(track)

You can test this code as follows:

from playlist import Track, Playlist

myPlaylist = Playlist("Pop Music","pop_music.csv")
myPlaylist.load()

myPlaylist.view()
myPlaylist.removeTrack(myPlaylist.tracks[2]) #This will remove the third track from the playlist!
myPlaylist.view()

This method will return the length of the tracks list.

def getNumberOfTracks(self):
    return len(self.tracks)

To test this method:

from playlist import Track, Playlist

myPlaylist = Playlist("Pop Music","pop_music.csv")
myPlaylist.load()

numberOfTracks = myPlaylist.getNumberOfTracks()
print("This playlist has " + str(numberOfTracks) + " tracks!")

To calculate the total duration of a playlist we need to add the duration of each of its tracks.

def getTotalDuration(self):
    duration = 0
    for track in self.tracks:
      duration += track.duration
    return duration

To test this method:

from playlist import Track, Playlist

myPlaylist = Playlist("Pop Music","pop_music.csv")
myPlaylist.load()

duration = myPlaylist.getTotalDuration()
print("This playlist lasts " + str(duration) + " seconds!")

The shuffle method just needs to shuffle the list of tracks using the shuffle() function from the random library.
We will hence need to import the random library by adding the following line at the top of the playlist.py file:

import random

Then we will add the following method to the Playlist class:

def shuffle(self):
  random.shuffle(self.tracks)

In the main program we can test our shuffle method using the following code:

from playlist import Track, Playlist

myPlaylist = Playlist("Pop Music","pop_music.csv")
myPlaylist.load()

myPlaylist.shuffle()
myPlaylist.view()

To reset a playlist we just need to reset its tracks list to an empty list.

def reset(self):
  self.tracks = []

In the main program we can test our reset method using the following code:

from playlist import Track, Playlist

myPlaylist = Playlist("Pop Music","pop_music.csv")
myPlaylist.load()

myPlaylist.reset()
myPlaylist.view()

To check is a playlist is empty we can check if the length of its tracks list is equal to 0.

def isEmpty(self):
  return len(self.tracks)==0

In the main program we can test our reset method using the following code:

from playlist import Track, Playlist

myPlaylist = Playlist("Pop Music","pop_music.csv")
myPlaylist.load()

if myPlaylist.isEmpty():
   print("Your playlist is empty.")

myPlaylist.reset()

if myPlaylist.isEmpty():
   print("Your playlist is empty.")

myPlaylist.view()

Tagged with: OOP

Shopping Basket Class

Posted on January 26, 2021 by Administrator Posted in Computer Science, OOP Concepts, Python - Intermediate, Python Challenges, Solved Challenges

One of the key features of any e-commerce website is the shopping basket. It is used to let the end-users add products to their basket before proceeding to checkout.

In this Python challenge we will create a Shopping Basket class to implement the different functionalities (behaviours) such as:

To do so we will create the following two classes:

The items property of the Shopping Basket class will be a dictionary of items:quantity pairs. (The items are the keys, for each key, the quantity in the basket is the value)

Python Code

Your task

Add a new “Stock Level” property to the item class.

Update the addItem(), removeItem(), updateItem() and reset() methods of the Shopping Basket class to check the availability of the item in stock before adding/changing the desired quantity, and by updating the Stock Level property of the item class accordingly when items are added/removed from the shopping basket.

Solution...

The solution for this challenge is available to full members!
Find out how to become a member:
➤ Members' Area

Tagged with: OOP

Learning Zone ✕

Theory Concepts

Interactive Quizzes

GCSE Computer Science (UK)

A-Level Computer Science (UK)

Coding Challenges ✕

Python Challenges

HTML / CSS & JavaScript

LMC

SQL

Block Programming

Interactive Coding Puzzles

Online Interactive Tools ✕

Coding Tools

Design Tools

Logic Gates Circuits

Cryptography Corner

Member's Area ✕

Register/Sign Up

Get In Touch

Books Corner

Half-Subtractor Circuit

Full-Subtractor Circuit

Full Binary Subtraction

Alternative Approach

1-bit Arithmetic & Logic Unit

8-bit Arithmetic & Logic Unit

Binary Left Shift

Binary Right Shift

8-bit Binary Shifters

1-bit Magnitude Comparator

4-bit Magnitude Comparator

8-bit Magnitude Comparator

2-to-4 Binary Decoder

3-to-8 Binary Decoder

4-to-16 Binary Decoder

Instruction Decoder

XNOR Logic Gate

4-bit Equality Comparator

Logic Gates Studio

Logic.ly

Exponentiation

Square Root = To the power of half

The Babylonian method

Python Code

The Bakhshali method

Solution...

Class Diagram

Abstract Class

Inheritance

Over-Riding Polymorphism

Over-Loading Polymorphism

Python Code

Python Code

Solution (Step by step)

Python Code

Your task

Solution...

Recent Posts

Our Latest Book