More results...

Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors
post
page
Python IDE Dashboard

Average night’s sleep survey

sleep-surveyFor her PSHE homework on the importance of sleep, Clarisse has decided to collect data from pupils of different year groups from her school. She will do so using a short survey.

The aim of the survey will be to find out, on average, how many hours of sleep students have per night and to compare these findings with the recommended number of hours for high school students.

According to the National Sleep Foundation, the recommended numbers of hours of sleep per night are as follows:

Age Group Recommended Sleep
School-aged Children 6-13 years 9 to 11 hours
Teenagers 14-17 years 8 to 10 hours
Young Adults 18-25 years 7 to 9 hours

Clarisse’s survey will only have one question: How many hours do you sleep each night?

To help her calculate the resulting average number of hours of sleep per night she would like you to write a Python program based on the following flowchart:
sleep-survey-flowchart
This algorithm is based on:
iteration-label

Algorithm Trace Table

To gain a better understanding of how this algorithm works you will need to complete the following trace table considering the following user inputs:

8 , y , 10 , y , 12 , n

 Line NumbercarryOntotalHoursnumberOfStudentscarryOn ==”y”hoursaverageOUTPUT
1“y”
20
30
4True
58
68
71
88
98
10“y”
4True
510
618

Python Code

Use the above flowchart to complete the Python code for this program:

Extension Task

Write a new program to make suitable recommendations to school children on whether or not they are spending enough time sleeping per night. Your program should:

  • Ask for the name and the age of the end-user,
  • Ask for the number of hours they spend sleeping each night (on average),
  • Compare this number of hours with the recommended hours for their age category,
  • Display an approriate message to say whether:
    • They are not spending enough time sleeping per night,
    • They are spending the recommended amount of time sleeping per night,
    • They are spending more than the recommended amount of time sleeping per night!

Your algorithm will be based on:
selection-label

As a reminder, the recommended numbers of hours of sleep per night are as follows:

Age Group Recommended Sleep
School-aged Children 6-13 years 9 to 11 hours
Teenagers 14-17 years 8 to 10 hours
Young Adults 18-25 years 7 to 9 hours

Testing

Create a test plan to test your program. Make sure to include valid, boundary, invalid and erroneous test data in your test plan: (click on the … to add your own data)

Test # Input Values: Type of test Expected Output Actual Output
#1 Age: 12
Number of Hours: 10
Valid Test You are spending the recommended amount of time sleeping per night.
#2 Age:
Number of Hours:
Valid Test
#3 Age:
Number of Hours:
Invalid Test
#4 Age:
Number of Hours:
Invalid Test
#5 Age:
Number of Hours:
Boundary Test
#6 Age:
Number of Hours:
Boundary Test
#7 Age:
Number of Hours:
Erroneous Test
#8 Age:
Number of Hours:
Erroneous Test

Tagged with: , ,

Reverse Polish Notation Parser

Reverse Polish notation (RPN), also known as Polish postfix notation or simply postfix notation, is a mathematical notation in which operators follow their operands. This notation is an alternative notation to the standard infix notation in which operators are located between their operands or to the prefix Polish notation (PN), in which operators precede their operands.

Note that the description “Polish” refers to the nationality of logician Jan Łukasiewicz, who invented Polish notation in 1924

Prefix Notation
(a.k.a. Polish Notation)
Infix Notation Postfix Notation
(a.k.a. Reverse Polish Notation)
+ 2 5 2 + 5 2 5 +

Binary Expression Trees

The Polish Notations (prefix or postfix) are used by programming language interpreters where Boolean and arithmetic expressions are parsed into abstract syntax trees. You can find out more about the use of binary trees to store Boolean and arithmetic expressions and about the pre-order, in-order and post-order depth-first traversals of a binary tree.

The use of binary expression trees can be used to facilitate the conversion of an expression from a more intuitive infix notation to either a prefix (RPN) notation or postfix (PN) notation.

The Shunting-Yard Algorithm

Edsger W. Dijkstra invented the shunting-yard algorithm to convert infix expressions to postfix expressions (RPN). The name comes from the fact that the algorithm’s operation resembles that of a railroad shunting yard.

Why use the prefix notation or postfix notations?

The main benefit of both the Polish Notation and of the Reverse Polish Notation over the infix notation is that they do not require the use of parentheses as long as each operator has a fixed number of operands.

For instance:

Prefix Notation
(a.k.a. Polish Notation)
Infix Notation Postfix Notation
(a.k.a. Reverse Polish Notation)
x + 3 4 5 (3 + 4) x 5 3 4 + 5 x

As a result, entering an expression using the Polish Notations (PN or RPN) is quicker and would lead to less errors even though it may appear less intuitive to start with than the infix notation.

The reverse Polish scheme was first introduced in 1954 by Arthur Burks, Don Warren, and Jesse Wright and was later on reinvented by Friedrich L. Bauer and Edsger W. Dijkstra in the early 1960s in order to reduce computer memory access by using a stack to evaluate a RPN expression.

Using a Stack to evaluate a RPN expression

The following Python code demonstrated the use of a Stack data structure to evaluate/parse an expression using the Reverse Polish Notation.

You can retrace the steps from this algorithm using the following arithmetic expressions:

Expression #1Expression #2Expression #3Expression #4Expression #5
Operand Stack:

Expression:

Operand 1:
Operand 2:
Operator:
Result:
Operand Stack:

Expression:

Operand 1:
Operand 2:
Operator:
Result:
Operand Stack:

Expression:

Operand 1:
Operand 2:
Operator:
Result:
Operand Stack:

Expression:

Operand 1:
Operand 2:
Operator:
Result:
Operand Stack:

Expression:

Operand 1:
Operand 2:
Operator:
Result:

Truth Table Generator (Using Python)

binary-bannerThe purpose of this blog post is to write a Python script that will interpret a Boolean expression and output its full Truth Table.

Boolean Expressions & Truth Tables

Before attempting this challenge, you should test your understanding of Boolean expressions, logic gates diagrams and truth tables by competing this online quiz:
Online QuizBoolean Expressions, Logic Gates Diagrams and Truth Tables

Python Bitwise Operators

To implement a Python script than can interpret a Boolean expression we will the following bitwise operators:

Bitwise Operator Example Meaning
& a & b Bitwise AND
| a | b Bitwise OR
^ a ^ b Bitwise XOR
~ ~a Bitwise NOT

Note that in Python, the following two bitwise operators can also be used to perform a bitwise left shift or right shift:

Bitwise Operator Example Meaning
<< a << n Bitwise left shift by n places
>> a >> n Bitwise right shift by n places

Python Code (Solution)

Here is the Python code for our Truth Table Generator function truthTable() which takes two parameters:

  • A Boolean expression: e.g. A AND NOT (B OR C)
  • The number of inputs: either 2, 3 or 4: A, B, C and D

Your Task

Write an additional function to perform a bitwise left shift or a bitwise right shift using the bitwise operators << and >>.

Check that performing a left shift by n place(s) is equivalent to multiplying a number by 2n.

For instance 5 << 3 is the same as 5×23 = 40.

Check that performing a right shift by n place(s) is equivalent to dividing a number by 2n (whole division).

For instance 40 >> 3 is the same as 40/23 = 5.

File Size Calculations

binary-dataDigital data consists of binary information and is stored as a collection of 0’s and 1’s. On a computer system, numbers, text, pictures, sound files, video clips and computer programs are all stored using binary code.

Storing text files in binary

Text files are stored using a character set such as ASCII code or UNICODE. The number of bits used to encode one character has an impact on the total number of characters included in the character set.
For instance:

  • ASCII code uses 7 bits per characters and contains 128 codes/characters.
  • Extended ASCII code uses 8 bits per characters and contains 256 codes/characters.
  • UNICODE uses either 2 Bytes (UTF-16) or 4 Bytes (UTF-32) per character and contains either 65,536 or 4,294,967,296 characters, enough to include all the characters and symbols used in every language worldwide.

Based on this information, we can easily work out the formula used to estimate the size of a text file as follows:

Text File Size = number of bits per character x number of characters

Text File Size Estimation

Storing bitmap pictures in binary

A bitmap picture is a 2D grid of pixels of different colours. You can read more about how bitmap pictures are stored in binary on this post.

Two criteria will impact the file size of a bitmap picture:

  • The resolution: The number of pixels it contains which can be defined as: width in pixels x height in pixels. For instance a picture of 640 by 480 pixels would contain 640 x 480 = 307,200 pixels.
  • The colour depth: The number of bits used to encode the colour of one pixel. For instance a 1-bit colour depth means that the graphic can only include 2 colours (e.g. 1 = black, 0 = white), and 8-bit colour depth means that the graphic can include up to 256 colours, and a 3-Byte colour depth (RGB code) would include 16,777,216 colours.

Based on this information, we can easily work out the formula used to estimate the size of a bitmap picture as follows:

Picture File Size = colour depth x width in pixels x height in pixels

Picture File Size Estimation

Note that a bitmap picture would also include a few more Bytes of data to store the Meta Data which contain additional information used by the computer to render the graphic such as the width of the graphic in pixels, its height in pixels and its colour depth. We will however ignore this in our file size estimation as for large graphics this would only make a small difference to the file size estimation.

Storing sound files in binary

An analogue sound wave can be digitalised using a process called sound sampling. You can find out more about sound sampling on this post.

Three criteria will impact the file size of a sound file:

  • The sample rate: The sample rate correspond to the number of samples being recorded per second. For instance a phone call would have a sample rate of 8kHz (8,000 samples per second) whereas an audio CD would record music with a sample rate of 44.1kHZ (44,000 samples per second) resulting in a higher quality sound.
  • The bit depth: The bit depths correspond to the number of bits used to record one sample. For instance retro-arcade games used to use 8-bit music. Old mobile phones used to use 16-bit ringtones. Higher quality sound files may use a 32-bit bit-depth or higher.
  • The duration: The duration of a the sound files in seconds will impact on the number of samples needed to record the sound file and hence it will have an impact on the file size.

Based on this information, we can easily work out the formula used to estimate the size of a sound file as follows:

Sound File Size = sample rate x duration x bit depth

Mono-Sound File Size Estimation

Note that the above formula is used to estimate the file size of a mono sound file. some sound files use multiple channels such as stereo files (2 channels) or Dolby-surround sound files (6 channels). To estimate their file size, you need to multiply the above formula by the number of channels.

Sound File Size = sample rate x duration x bit depth x number of channels

Sound File Size Estimation

Also, similar to picture files, a sound file would also include some meta-data (sample rate, bit depth, number of channels) needed for the computer to interpret the data, however we will once again ignore this data in our file size estimation.

Programming Task

Your task is to write three procedures used to estimate the file size of text files, bitmap pictures and sound files as follows:

  • estimateTextFileSize() will take two parameters, the number of bits per character and the number of characters in the file. It will output the estimated file size using the formula provided earlier in this post.
  • estimatePictureFileSize() will take three parameters, the width and height of the picture in pixels and its colour depth. It will output the estimated file size using the formula provided earlier in this post.
  • estimateSoundFileSize() will take four parameters, the sample rate (in Hz), the bit depth, the duration (in seconds) and the number of channels. It will output the estimated file size using the formula provided earlier in this post.

Note that for all three procedures, the output information should be displayed using the most suitable unit (bits, Bytes, KB, MB or GB)

Python Code

Complete your code below:

Test Plan


All done? It’s now time to test your code to see if it works as expected.

Test # Type of file Input Values Expected Output Actual Output
#1 Text File Number of bits per character: 8 bits (Extended ASCII)
Number of characters: 3,000
File Size: 3KB (or 2.93KB)
#2 Text File Number of bits per character: 16 bits (Unicode UTF-16)
Number of characters: 12,000
File Size: 24KB (or 23.44KB)
#3 Picture File Width: 640 pixels
Height: 480 pixels
Colour depth: 8 bits
File Size: 307.2KB (or 300KB)
#4 Picture File Width: 1920 pixels
Height: 1080 pixels
Colour depth: 24 bits
File Size: 6.22MB (or 5.93MB)
#5 Sound File (Mobile phone ring tone) Sample Rate: 8 KHZ (=8,000 Hz)
Bit Depth: 16-bits per sample
Duration: 30 seconds
Channel: 1 (mono)
File Size: 480KB (or 468.75KB)
#6 Sound File (uncompressed audio CD track) Sample Rate: 44.1 KHZ
Bit Depth: 16-bits per sample
Duration: 210 seconds
Channel: 2 (stereo)
File Size: 37.04MB (or 35.33MB)

Note that this test plan gives you two possible outputs for each test depending on whether your calculations are based on 1KB = 1,000 Bytes or 1KB=1,024 Bytes. Both approaches are acceptable.

Extension Task 1: Animated Gif File

Animated Gif files consists of a collection of bitmap pictures that are displayed one at a time over a few seconds. Most animated gif files loop back to the first picture (frame) after reaching the last frame. The frame rate of a gif file defines the number of frames per second.

We can calculate the size of an animated gif files as follows:

Animated Gif File Size = width x height x colour depth x frame rate x duration

Animated Gif File Size Estimation

Your task is to create an extra function called estimateAnimatedGifFileSize() that will take five parameters, the width and height of the pictures in pixels, their colour depth, the frame rate in fps (frame per seconds) and the duration of the animation in seconds. It will output the estimated file size using the above formula.

You can then test your subroutine using the following input data:

Test # Type of file Input Values Expected Output Actual Output
#1 Animated Gif File Width: 150 pixels
Height: 150 pixels
Colour depth: 4 bits
Frame Rate: 4 fps
Duration: 6 seconds.
File Size: 270KB (or 263.67KB)

Extension Task 2: Movie Files

Movie files are similar to animated gif. A movie clip also consists of a collection of still pictures displayed with a high frame rate e.g. 24 fps (frames per seconds). Movie clips also include a soundtrack that also need to be included in the estimation of the overall file size of a movie clip.

You can then test your subroutine using the following input data:

Test # Type of file Input Values Expected Output Actual Output
#1 Uncompressed Movie File Width: 1920 pixels
Height: 1080 pixels
Colour depth: 24 bits
Frame Rate: 24 fps
Duration: 1 hour 15 minutes

Soundtrack:
Sample Rate: 48 KHZ
Bit Depth: 16-bits per sample
Duration: 1 hour 15 minutes.
Channel: 6 (Dolby-Surround)

File Size: 672GB (or 640GB) File Size: 6.22MB (or 5.93MB)

Compression Algorithms

Note that these calculations are based on estimating file size of uncompressed files. Compression algorithms are often applied to picture files, sound files and movie files to reduce their overall file size.

For instance .png or .jpg picture files, .mp3 sound files or .mp4 movie files are all compressed files so their file size would be smaller than the file size given by the above calculations.

Tagged with:

Binary Subtraction using Logic Gates

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.
half-subtractor-truth-table

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

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:
full-subtractor-truth-table

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

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:
8-bit-subtractor-block-diagram

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.
8-bit-subtractor-block-diagram-using-full-adders

Tagged with:

8-bit ALU using Logic Gates

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:
ALU-Instruction-Table

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

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:
1-bit-ALU

8-bit Arithmetic & Logic Unit

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

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

8-bit Arithmetic & Logic Unit

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: ,

Binary Shifters using Logic Gates

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-left-shift

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.
binary-right-shift

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.binary-shift-logic-gates-diagram

Tagged with:

Binary Comparators using Logic Gates

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:
1-bit-magnitude-comparator-truth-table
And here is the logic gates diagram for this circuit:

1-bit Magnitude Comparator Logic Gates Diagram

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:
4-bit-magnitude-comparator-logic-gates-diagram

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:

Binary Decoders using Logic Gates

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-truth-table

2-to-4 Binary Decoder Logic Gates Diagram

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:
3-to-8-binary-decoder-truth-table
Logic Gates Diagram:

3-to-8 Binary Decoder 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.
4-to-16-binary-decoder-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!
instruction-decoder
Whereas binary decoders are used to implement the Decode stage of the FDE cyle, the Fetch stage is implemented using Multiplexers.

Tagged with:

Equality Comparators using Logic Gates

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

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

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

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

4-bit Digital Equality Comparator Circuit using logic.ly

Tagged with: