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

Random Library Challenges

Posted on January 25, 2021 by Administrator Posted in Computer Science, Python - Intermediate, Python Challenges, Solved Challenges

In this blog post we will experiment using some of the key functions from the random library. Many Python games will involve some degree of “randomness” for the game to be more realistic and unpredictable. Flipping a coin, throwing a dice, shuffling a deck of cards, spawning a sprite at a random location, generating a random password are all actions that can be implemented in Python fairly easily using the random library.

So let’s first investigate the most useful functions from this library to find out how to:

Generate a random number/integer,
Generate a random letter from the alphabet,
Select a random value from a list,
Identify a random index/location from a list,
Shuffle the values from a list.

We will then apply these techniques to solve a set of mini challenges to generate the following random values:

Using the random libraryPython IDEPython Challenges

Generating a random integer:

To generate a random number between two values (e.g. between 1 and 10), you will need to use the random.randint() function:

import random
number = random.randint(1,10)
print(number)

Generating a random letter from the alphabet: (Using the ASCII code)

To generate a random letter from the alphabet we can use the ASCII code where the ASCII code for letter “A” is 65 and the ASCII code for letter “Z” is 90. To do so we will generate a random number between 65 and 90 to then retrieve the matching ASCCI character using the chr() function.

import random
ascii = random.randint(65,90)
letter = chr(ascii)
print(letter)

Generating a random letter from the alphabet: (Using the random.choice() function)

An alternative approach used to generate a random letter from the alphabet is to randomly select a character from a string using the random.choice() function.

import random
letter = random.choice("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
print(letter)

Selecting a random value from a list: (using a random index)

We can randomly select a value from a list by first generating a random number between 0 and the length of the list -1. We can then use this rnadomlygenerated index to access the value from the list at the given position/index.

import random
weekdays = ["Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"]
index = random.randint(0,len(weekdays)-1)
day = weekdays[index]
print(day)

Selecting a random value from a list: (using the random.choice() function)

The random.choice() function can also be used to randomly pick a value from a list

import random
weekdays = ["Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"]
day = random.choice(weekdays)
print(day)

Shuffling list:

The random.shuffle() function is used to shuffle all the values from a list.

import random
weekdays = ["Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"]
random.shuffle(weekdays)
print(weekdays)

Adapt the code provided to complete the following challenges:

Challenge #1: Generating a random IP address:

random-ip-address
An IP address consists of 4 numbers between 0 and 255 separated by a dot. Your task is to write a Python script that generates and outputs a valid random IP address.

Challenge #2: Flipping a coin:

random-head-or-tails
Your task is to write a Python script that randomly outputs “Heads” or “Tails”.

Challenge #3: Throwing a dice:

random-throw-dice
Your task is to write a Python script to throw a dice by randomly generating a value between 1 and 6.

Challenge #4: Generating a random phone number:

random-phone-number
Your task is to write a Python script to generates a random phone number consisting of 11 digits.

Challenge #5: Generating a random postcode:

random-postcode
Your task is to write a Python script to generates a random UK postcode in the format: LetterLetterNumber_NumberLetterLetter.

Challenge #6: Generating a random date:

random-date
Your task is to write a Python script to generates a random date in the format: DD/MM/YYYY.

Challenge #7: Generating a randomly pick a playing card:

random-playing-card
Your task is to write a Python script to randomly pick and output a card from a deck of 52 playing cards. The program should output the suit and value of the card (e.g. 7 of hearts, Queen of clubs, etc…).

Challenge #8: Generating a random password:

random-password
Your task is to write a Python script to randomly generate a strong password mixing lowercase, uppercase, numbers and punctuation signs in any order.
You can check this post for some extra help on this challenge.

Challenge #9: Generating 6 random lottery numbers:

random-lottery-numbers
Your task is to write a Python script to randomly generates and outputs 6 unique random numbers between 1 and 50.
You can check this post for some extra help on this challenge.

Solution...

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

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

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...

Generating a random integer:

Generating a random letter from the alphabet: (Using the ASCII code)

Generating a random letter from the alphabet: (Using the random.choice() function)

Selecting a random value from a list: (using a random index)

Selecting a random value from a list: (using the random.choice() function)

Shuffling list:

Challenge #1: Generating a random IP address:

Challenge #2: Flipping a coin:

Challenge #3: Throwing a dice:

Challenge #4: Generating a random phone number:

Challenge #5: Generating a random postcode:

Challenge #6: Generating a random date:

Challenge #7: Generating a randomly pick a playing card:

Challenge #8: Generating a random password:

Challenge #9: Generating 6 random lottery numbers:

Solution...

Recent Posts

Our Latest Book