More results...

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

Perseverance’s Parachute Secret Message Encoder

On February 18, 2020, NASA successfully landed its rover “Perseverance” on planet Mars. To slow down its descent the rover deployed a parachute. The whole operation was filmed and relayed on the Internet. You can watch the official NASA video on youtube.

The internet community quickly noticed the unusual red and white pattern on the parachute resembling the pattern of a barcode:

NASA-perseverance-parachuteSource: NASA/JPL-Caltech

In just a few hours, internauts successfully decoded the “secret message” encoded on the parachute. The message read:

“Dare Mighty Things – 34° 11’58” N 118° 10’31 W”

The numbers in this message correspond to the GPS coordinates of the JPL centre (NASA’s Jet Propulsion Laboratory in located in California), whereas “Dare Mighty Things” is the moto used by JPL.

The encoding process is fairly basic:

  • The 3 concentric inner rings of the parachute represent one word per ring.
  • Each character of a given word is represented by a number between 1 and 26 corresponding to its position in the alphabet (A is 1, B is 2, up to Z is 26). These numbers are then converted in binary using 7 bits per character followed by “000” as a delimiter between each character.
  • E.g. The word DARE is encoded in the inner circle. D=4 A=1 R=18 E=5 becomes in binary:
    000-0000100-000-0000001-000-0010010-000-0000101-000
  • The pattern consists of red and white stripes. A white stripe represent a 0, a red stripe a 1. e.g.
  • Character Value 64 32 16 8 4 2 1
    D 4
    0
    0
    0
    0
    1
    0
    0
    A 1
    0
    0
    0
    0
    0
    0
    1
    R 18
    0
    0
    1
    0
    0
    1
    0
    E 5
    0
    0
    0
    0
    1
    0
    1
  • The message is encoded clockwise.
  • A ring consists of 80 stripes (to encode a word of a maximum of 8 characters. All unused stripes appear as a large red block.
  • Using a similar approach, the outer ring of the parachute is used to encore the GPS coordinates in DMS (Degrees, Minutes, Seconds) format. Each coordinate being encoded in binary using 7-bits.

Let’s apply this to decode NASA’s Perseverance Secret Message:

"Dare Mighty Things - 34° 11'58" N 118° 10'31"

“Dare Mighty Things – 34° 11’58” N 118° 10’31 W”

Online Encoder

You can use our online secret message encoder to design your own parachute. To do so you will need to:

  • Choose 3 words of maximum 8 letters each.
  • Identify the GPS coordinates (using the DMS format: Degrees, Minutes, Seconds) of a given location on planet earth. (You can use this website (www.gps-coordinates.net) to retrieve the required coordinates)
  • Input this information below to generate your parachute. You can then print or take a screenshot of your parachute.

Decoding Tasks

We have encoded a few messages using the same approach. Well you be able to decode these messages and identify the exact location using the following parachutes?

Somewhere in France...

Parachute #1: Somewhere in Europe…

Parachute #1: Somewhere in America!

Parachute #2: Somewhere in America…

Somewhere in Asia...

Parachute #3: Somewhere in Asia…

To complete this activity on paper, you can download and print the worksheet (PDF file).

unlock-access

Solution...

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

Mars Perseverance Rover

planet-marsOn February 18, 2020, NASA’s rover called “Perseverance” successfully landed on Mars. The mission of this high-tech 6-wheel rover is to explore the surrounding areas, analyse the Martian soil on different locations, take high definition pictures as well as audio recordings. The ultimate hope for NASA is that this rover may find evidence that there was once a form of life on planet Mars. You can read more about this rover on the official NASA website.

The rover and all its various sensors and electromechanical devices are controlled using a range of preloaded algorithms. New algorithms can also be transmitted to the rover via ultra high frequency (UHF) radio transmission.

mars-perseverance-rover

The NASA is asking you to write a few new algorithms that will be used to explore a new specific zone on planet Mars. You will have to design, implement and test 7 algorithms to compete the different missions set by NASA. You will be able to test your algorithms using our Mars Perseverance Simulator Environment (MPSE).

Mission 1Mission 2Mission 3Mission 4Mission 5Mission 6Mission 7

Mission 1: Delimiting the area

The area, the rover will cover is a square of 400m by 400m situated in the North-West area of the Jezero Crater. Your first mission is to implement an algorithm to direct the rover around the perimeter of this area: The path to follow has been traced in white on the Mars Perseverance Simulator Environment.

mars-path-1

The code used to initialise the rover for this mission has already been completed for you (line 1 to 20) and you will not need to update this code. However, you will need to complete this code from line 22.

Note that the rover can respond to the following instructions:

  • rover.forward(distance)
  • rover.left(angle)
  • rover.right(angle)

For instance, you can try the following code to get you started:

rover.forward(200)
rover.left(45)
rover.forward(100)

Mars Perseverance Simulator Environment (MPSE):

Mission 2: Code Optimisation

The rover being located more than 240 million km away from NASA’s Control Centre (on planet Earth!), the radio transmissions needs to be optimised by reducing the quantity of data that needs to be transmitted to the rover.

NASA would hence like you to review the code you produced to complete mission 1 to see if it would be possible to provide a shorter algorithm (in other words to reduce the number of lines in the code needed to direct the rover around the perimeter).

mars-path-1

To do so you will need to use a for loop which will enable you to reduce the number of repeating instructions in your code.

For instance, you can try the following code to get you started:

for i in range(3):
   rover.forward(200)
   rover.left(120)

You will need to adapt your code from mission to make effective use of a for loop, and hence reduce the amount of data to be transmitted from planet Earth to planet Mars.

Mars Perseverance Simulator Environment (MPSE):

Mission 3: Exploring the whole area

NASA would like to create a detailed surface map of the delimited area. To do so, it needs the rover to circulate through the whole area. The path to follow has been highlighted in white in the simulator environment. Write an algorithm to direct the rover alongside this path. Make sure your code is optimised to limit the amount of data to transfer across to the rover.

mars-path-2

Mars Perseverance Simulator Environment (MPSE):

Mission 4: Alternative Path

NASA would like to investigate an alternative path to cover the whole area. The path to follow has been highlighted in white in the simulator environment. Once again, your mission is to write an algorithm to direct the rover alongside this path. Make sure your code is optimised to limit the amount of data to transfer across to the rover.

mars-path-3

Mars Perseverance Simulator Environment (MPSE):

Mission 5: Finding Craters

While completing the full map of the area, the rover identified three small craters. NASA would like you to write an algorithm to visit these three craters one at a time using the information provided on the highlighted path.

mars-path-4

Mars Perseverance Simulator Environment (MPSE):

Mission 6: Finding Craters near a rift!

NASA would like the rover to explore three additional craters. However these are located next to a rift. NASA would like you to write an algorithm to visit these three craters one at a time. You will have to do so making sure the rover does not fall into the rift!

mars-path-6

Mars Perseverance Simulator Environment (MPSE):

Mission 6: Giant Crater Exploration

Finally, NASA would like to explore one giant crater by taking the rover all around the crater. You will need to write an optimised algorithm to go around the crater using the information provided on the highlighted path.

mars-path-5

Remember: To optimise your algorithm, you should make use of a for loop. e.g.

for i in range(3):
   rover.forward(200)
   rover.left(120)

Mars Perseverance Simulator Environment (MPSE):

unlock-access

Solution...

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

Wanted Poster (CSS Task)

wanted-poster-css-taskFor this challenge we will create a Wanted Poster using a range of HTML and CSS skills.

CSS Selectors & CSS Properties

In order to complete this challenge, you need a good understanding of how CSS selectors work. You can learn about CSS selectors on w3schools.com.

css-syntax

To customise the look & feel of your poster using CSS code, you will use different types of selectors such as:

  • TAG
  • .class
  • #id
  • element child-element
  • element child-element:first-child

In this challenge we will use various CSS properties such as:

  • font-family:
  • font-size:
  • color:
  • font-weight:
  • font-style:
  • text-align:
  • padding:
  • margin:
  • background-image:
  • etc.

You can learn more about all these CSS properties on w3schools.com.

CSS Box Model

To understand how margin, borders and padding works you need to understand the CSS Box Model. Click on this picture to find out more:CSS-Box-Model

HTML & CSS Code

To complete this challenge, you will need to edit the code below by clicking on the top-right button “Edit on Codepen”.

See the Pen
WANTED Poster
by 101 Computing (@101Computing)
on CodePen.

Note that this script will the following three pictures:

Instructions

Wooden TexturePaper TextureMugshotWanted!TypographySepia Filter
Your first task is to apply a wooden texture to the whole page. To do so you will need to:

  1.  Apply a background picture to the BODY of the page. The URL for this picture is: https://www.101computing.net/wp/wp-content/uploads/wood.jpg
  2.  Apply a 20px padding to the whole page.
View Solution / CSS Code
To do so you will need to add the following code to CSS section of the Codepen:

BODY {
   background-image: url('https://www.101computing.net/wp/wp-content/uploads/wood.jpg');
   background-repeat: repeat;
   padding: 20px;
}
To create the poster:

  1.  Use CSS to resize the poster (<div class=”poster”>…</div>) by resizing this container to 488px wide by 640px high.
  2.  Apply the following background image to this container: https://www.101computing.net/wp/wp-content/uploads/parchment.jpg
  3.  Apply a padding of 20px to the poster.
  4.  All the content should be aligned to the centre.
  5.  Using an online CSS shadow generator, add a shadow effect to your poster
View Solution / CSS Code
To do so you will need to add the following code to the CSS section of the Codepen:

.poster {
   width: 480px;
   height: 620px;
   box-sizing: border-box;
   background-image: url('https://www.101computing.net/wp/wp-content/uploads/parchment.jpg');
   background-repeat: no-repeat;
   padding: 20px;
   text-align:center;
   box-shadow: 2px 4px 8px 3px #000000;
}
Then we will customise the mugshot picture of Billy the Kid.

  1.  Resize the picture to: 300px wide by 325px high.
  2.  Add a solid border of 2px and dark brown colour: #291200.
  3.  Add a 10px margin to the picture.
View Solution / CSS Code
To do so you will need to add the following code to the CSS section of the Codepen:

#mugshot {
  width: 300px;
  height: 325px;
  border: 2px solid #291200;
  padding: 10px;
}
Then we will customise the title of the Poster (H1 heading saying “WANTED”).

  1.  The font type should be Ewert (Google font).
  2.  The font colour should be dark brown: #291200.
  3.  The font size should be 44pt.
  4.  This heading should not appear in bold.
  5.  This heading should not have any margins.
View Solution / CSS Code
To do so you will need to add the following code to the CSS section of the Codepen:

h1 {
  font-family: ewert;
  color: #291200; 
  font-size: 44pt;
  font-weight: normal;
  margin: 0px;
}
To complete your poster change the typography of the different headings, subheadings of the poster.

  1.  You should use a combination of the following two google fonts:
    • Ewert
    • Ultra
  2.  All the text should appear in dark brown: #291200.
  3.  All the text should fit on the poster. To do so you will need to update margins and font sizes.
  4.  Different font sizes and weights should be used to make key information standout nicely.
  5.  The description: “Armed and very dangerous” should appear in italic.
  6.  The reward price should have a double underline!
 The final touch to complete this poster is to apply a sepia filter to the mugshot picture.

View Solution / CSS Code
To do so you will need to add the following code to the CSS section of the Codepen:

#mugshot {
   filter: sepia(60%);
}

Final Poster Preview

This is what your poster should look like at the end of this task:
wanted-poster-css

unlock-access

Solution...

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

Binary Search Tree Implementation

binary-search-tree-python-implementationBinary Search Trees are an effective solution to store data in a computer program and perform a binary search.

The benefits of using a BST (Binary Search Tree) data structure is that data can be added to the tree as it is received and the BST structure will store it effectively so that:

  • A sorted list of the data can be generated using an in-order traversal of the tree.
  • A binary search can be easily implemented making this data structure very effective to access/search through. A binary search has an O(log(n)) notation for time complexity.
  • Data/Nodes can easily be added or removed from the tree without having to rearrange the whole data structure

Binary-Search-Tree
The characteristics of a Binary Search Tree are as follows:

  1. Being a type of tree data structure, it consists of nodes and branches with a parent/child relationship between nodes,
  2. Each node can have a maximum of two children node: The left child and the right child,
  3. The left subtree of a node contains only nodes with values lesser than the node’s value.
  4. The right subtree of a node contains only nodes with values greater than the node’s value.

When a new node is added to the tree, if added in a way that do not conflict with the 4 characteristics listed above.

Capital Cities BSTRandom Numbers BST
binary-search-tree-capital-cities
Can you add the following cities to this Binary Search Tree:

  • Cape Town
  • Seoul
  • How would you then remove New-York from this BST tree?

    binary-search-tree-random-numbers
    Can you add the following numbers to this Binary Search Tree:

  • 62
  • 59
  • 23
  • How would you then remove number 28 from this BST tree?

    Depth-first Traversal Of Binary Search Tree

    The three depth-first traversal methods to read through all the nodes of a BST are:

    1. Pre-order Traversal
    2. In-order Traversal
    3. Post-order Traversal

    The in-order traversal is frequently used as it retrieves the nodes in order: alphabetical order or numerical order depending on the data types of the nodes’ values. This remains the case even if the nodes were added to the tree in a completely different order.

    You can read more and practise your understanding of the different breadth-first and depth-first traversals of tree on this blog post as well as investigate their algorithms (in pseudocode).

    Python Implementation

    Different approaches can be used to implement a Binary Search Tree in Pythons. It can be achieved by combining different data structures (e.g. hash tables and lists). However in this blog post we will implement our BST data structure using Object Oriented concepts (OOP Programming).

    First we will create a Node class to store the following 3 values:

    • The value of the node,
    • A pointer to the left node,
    • A pointer to the right node.

    Here is the Python code for the Node class:

    class Node:
      def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    We will then create a Tree class.
    The main property of our Tree class will be its root Node. We will then implement a range of methods as follows:

    • insert() – Insert a new value/node in the correct position within the BST,
    • delete() – Find a node based on its value and remove it from the tree,
    • find() – Perform a Binary Search on the tree to find a specific Node based on its value,
    • preorder_traversal() – Perform and output the result of a pre-order traversal of the tree,
    • inorder_traversal() – Perform and output the result of an in-order traversal of the tree,
    • postorder_traversal() – Perform and output the result of a post-order traversal of the tree,
    • draw() – Perform and output the result of a post-order traversal of the tree.

    You can investigate the Python code used to implement all of the above 7 methods in the trinket below.

    Python Code

    Use the following Python code to build your own BST, adding one value at a time. You will be able to visualise your tree on screen and view the outputs of the three depth-first traversal methods:

    Python Challenge

    Add two methods to the Tree class as follows:

  • saveToFile() – Save the whole content of the binary tree in a text file. You will have to investigate the best format to do so. For instance you could save the BST data structure as a JSON file or an XML file.
  • loadFromFile() – Load the whole content of the binary tree from a text file (using the JSON or XML formats).
  • Tagged with:

    Lossless Compression: Huffman Coding Algorithm

    The Huffman Coding algorithm is used to implement lossless compression. For the purpose of this blog post, we will investigate how this algorithm can be implemented to encode/compress textual information.

    The principle of this algorithm is to replace each character (symbols) of a piece of text with a unique binary code. However the codes generated may have different lengths. In order to optimise the compression process, the idea behind the Huffman Coding approach is to associate shorter codes to the most frequently used symbols and longer codes to the less frequently used symbols.

    So let’s consider the following message which consists of 20 characters:
    huffman-coding-message

    Note that the Huffman coding algorithm is normally used to compress larger amount of data and would not really be used to compress such a small message!

    Step 1: Frequency Analysis

    The first step of the Huffman Coding algorithm is to complete a frequency analysis of this message by:

    • Identifying all the symbols used in the message,
    • Identifying their weights (or frequencies) by counting their occurrences (the number of times they appear) within the message,
    • Sorting this list of symbols in ascending order of their weights.

    huffman-coding-frequency-analysis

    Step 2: Organising Symbols as a Binary Tree

    To do so each symbol becomes a node storing the symbol itself and its weight.
    Then the tree is constructed through the following iterative process:
    huffman-coding-tree

    Step 3: Generating the Huffman Codes

    Using the above tree, we can now identify the Huffman code for each symbol (leaves of the tree. This is done by highlighting the path from the Root node of the tree to the required leave/symbol. The labels of each branch are concatenated to form the Huffman code for the symbol.
    huffman-coding-path

    As you can see, most frequent symbols are closer to the root node of the tree, resulting in shorter Huffman codes.

    The resulting Huffman Codes for our message are:
    huffman-coding-codes

    Encoding the message

    We can now encode the message by replacing each symbol with its matching Huffman code.
    huffman-coding-encoded-message-codes

    Encoded/compressed message:

    010100111101000011111011010111100001101111010000111100101000110

    Python Implementation

    Here is a Python implementation of the Huffman Coding algorithm:

    Python Task

    To complete the above code, we need an extra method to our HuffmanEncoder class called decode().

    This method should take two parameters:

    • An encoded message (Binary string)
    • the Huffman codes used to encode the message (Using a python dictionary)

    Using the above information, the decode() method would then decode the message one character at a time.

    unlock-access

    Solution...

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

    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: