FIT1047 – Introduction to Computer Systems, Networks and Security
Assignment-1 Semester 2, 2019
Submission guidelines
This is an individual assignment, group work is not permitted.
Deadline: Assignment 1 due by week-7, Friday 4:00 PM.
Submission format: PDF for the written tasks, LogiSim circuit files for task 1, MARIE assembly files for task 2. All files must be uploaded electronically via Moodle. More details at the end of the assignment specifications.
Individualised exercises: Some exercises require you to pick one of several options based on your student ID.
Late submission:
• By submitting a Special Consideration Form with supporting documentation.
• Or, without special consideration, you lose 5% of your mark per day that you submit late
(including weekends). Submissions will not be accepted more than 5 days late.
This means that if you got x marks, only 0.95n × x will be counted where n is the number of days you submit late.
In-class interviews: You will be required to demonstrate your code to your tutor after the submission deadline. Failure to attend & demonstrate will lead to zero marks being awarded to the entire Marie programming part of this assignment. See instructions for Task 2 for more details.
Marks: This assignment will be marked out of 100 points, and count for 20% of your total unit marks.
Plagiarism: It is an academic requirement that the work you submit be original. Zero marks will be awarded for the whole assignment if there is any evidence of copying (including from online sources without proper attribution), collaboration, pasting from websites or textbooks. Further Note: When you are asked to use internet resources to answer a question, this does not mean copy-pasting text from websites. Write answers in your own words such that your understanding of the answer is evident. Acknowledge any sources by citing them. Your work will be submitted and compared with previous students works and also on the internet for plagiarism using Turnitin software. So please make sure the submission is your work.
1. Boolean Algebra and Logisim Task
The following truth table describes a Boolean function with four input values X1, X2, X3, X4
and two output values Z1, Z2.
X1
X2
X3
X4
Z1
Z2
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
1
1
0
1
1
0
1
1
1
0
0
1
1
0
1
0
0
1
0
1
0
1
0
1
1
1
1
0
1
1
1
0
The main result of this task will be a logical circuit correctly implementing this Boolean function in the Logisim simulator. Each step as defined in the following sub-tasks needs to be documented and explained.
1.1 Task 1: Boolean Algebra Expressions (5 points)
Write the Boolean function as Boolean algebra terms, using, either Product of Sum (POS) or Sum of Product (SOP) method. First, think about how to deal with the two outputs. Then, describe each single row in terms of Boolean algebra. e.g. combine the inputs (A, B, C, & D) to form a POS or SOP terms for each row. Finally, combine the terms for single rows into larger terms. As, Z1 and Z2 are two separate outputs, you need to deal with them separately.
Briefly explain these steps for your particular truth table (e.g., explain for one particular row how you come up with the Boolean terms for that row, and then explain how you combine all rows). This explanation should be no more than a few sentences.
Notation: use the following symbols and notation for writing Boolean algebra expressions. Variables are upper-case (e.g., A, B, C, D, X1, Z2). Boolean AND is written without a symbol, e.g. X1X2. Boolean OR is written with the + symbol, e.g. X1+X2. Negation is written
using an overline, e.g. 𝑋𝑋1 . Important: when writing terms like NOT X1 AND NOT X2, there must be a clear gap in the overlines, e.g. 𝑋𝑋1 𝑋𝑋2
1.2 Task 2: Logical circuit in Logisim (10 points)
Model the resulting Boolean terms from Step 1 in a single Logisim circuit, using only the basic gates AND, OR, NOT. You can use gates with more than two inputs. The single logic circuit should show all the four inputs, and both the outputs Z1 & Z2. The outputs should not be split up into two circuits.
1
1.3
• •
Briefly explain your construction (as for Step 1, a short explanation is enough). Test you circuit using values from the truth table and document the tests.
Task 3: Optimized circuit (20 points)
The goal of this task is to find a minimal circuit using only AND, OR, and NOT gates. Based on the truth table and Boolean algebra terms from Step 1.
1. Subtask-1: Optimize the function using Karnaugh maps to its minimal form
2. Subtask-2: Optimize the function using Boolean identities and verify its minimal form
from the subtask-1
You will need to create two Karnaugh maps and work on two separate Boolean Identities reduction forms, one for each output Z1 & Z2. Your documentation must show
a) the K-Maps.
b) the groups found in the K-Maps
c) The two Boolean identities reduction for Z1 & Z2 with steps.
d) And compare and contrast the two methods (K-Map & Boolean Identities methods)
show how they relate to terms in the optimized Boolean function.
Then use Logisim to create a minimal circuit, using only AND, OR, and NOT gates. Test your optimized circuit using values from the truth table and document your tests.
Note you can use Product-of-Sum or Sum-of-Product to optimise in subtask-2
2. MARIE (65 Marks)
In this task you will develop a MARIE application that performs some manipulation of strings. We will break it down into small steps for you.
Most of the tasks require you to write the code, test cases and some small analysis. The code must contain comments, and you must submit it as .mas files together with the rest of your assignment. The test cases should also be working, self-contained MARIE assembly files (without requiring much input from the user). The analysis needs to be submitted as part of the main PDF file you submit for this assignment. After the submission of your assignment, you will be required to give an interview to your tutor, the tutor may ask questions relating your programming concepts, logic and proof that its your work and not someone else’s work. The Interview is Mandatory and if you miss the interview you will be marked “zero”. The interview is done during the tutorials following the submission. Details will be discussed by the tutor in respective tutorials.
Name as Strings
This section introduces the concepts you need for the rest of the assignment. A string is a sequence of characters. It’s the basic data structure for storing text in a computer. There are several different ways of representing a string in memory and how to deal with strings of arbitrary length.
2
For this assignment, we will use the following string representation:
● A string is represented in a contiguous memory location, with each address containing one character.
● The characters are encoded using the ASCII encoding.
● End of a string is marked by the ASCII character ‘0’.
● A name will be composed of two strings, namely, First Name and Last Name.
● End of a name will be marked by another ASCII character ‘0’.
As an example, this is how, a name “John Noah” would be represented in memory (written as hexadecimal numbers):
Note that for a string with n characters, we need n + 3 words of memory in order to store all the characters belonging to a name and the additional ‘0’s that marks the end of each of the two strings, i.e. First Name and Last name, and end of the name.
In MARIE assembly language programming, we can make use of the ADR command, the HEX keyword and a label “myName” to put this string into memory:
myNameAdd, ADR myName myName, HEX 04A //J HEX 06F //o HEX 068 //h HEX 06E //n HEX 030 //0
HEX 04E //N HEX 06F //o HEX 061 //a HEX 068 //h HEX 030 //0 HEX 030 //0
2.1 Your name as a MARIE string (5 Marks)
Prepare a MARIE program to encode your full name using Unicode / ASCII characters. You should encode at most 5 characters for each part of your name (First Name or Last Name)– if your name is longer, you can shorten it, if it is less than 5 characters, then you can add dots ‘.’ You need to submit a MARIE file that contains code, using HEX like above, so that after assembling, your name is stored in MARIE memory.
04A
06F
068
06E
030
04E
06F
061
068
030
030
J
o
h
n
0
N
o
a
h
0
0
3
2.2 A subroutine for printing names (10 Marks)
Prepare a MARIE subroutine called printStringName that can print any name containing two ASCII ‘0’ terminated strings (using the “Output” instruction).
Start by using a label “PrintName” that holds the start address of a name string (like, myNameAdd in the example above). The code should then load a character from that address, output it if it is not ‘0’, then increment the address by one, and keep doing that until the character loaded from the address is a ‘0’ (which signals the end of the string). Then, print an ASCII “Space” character, and proceed to print the second part of the name string, i.e. Last Name until the character loaded from the address is a ‘0’ (which signals the end of the string). Then, when you load the second ASCII ‘0’ which marks the “end of a name”, print an ASCII “New Line” character and proceed to print the next name. For this task, you may use two or three names (your First Name and Last Name, your teacher’s name, your tutor’s name etc. minimum two names) to print, each name hard coded and assigned a label to identify.
To receive full marks, your code needs to be in the form of a subroutine that can be called using the JnS instruction. You need to write a MARIE main program to call this subroutine.
2.3 A subroutine to swap names (10 marks)
In section 2.2, assuming you have been using a few names (having two parts, First and Last names) and having them hard-coded in memory locations, such as myName1Add, myName2Add, myName3Add, etc. You can continue working on your MARIE program done in 2.2 to write another MARIE subroutine called subSwapNames to swap names between two memory locations, e.g. Name1 at memory location myName1Add and Name2 at memory location myName2Add.
Assume, before the swap, memory contents beginning at Memory Location: #myName1Add 04A 06F 068 06E 030 04E 06F 061 068 030 030 And, at Memory Location:
#myName2Add 04B 06D 069 07E 030 05E 07F 021 098 030 030
After the swap, memory contents beginning at Memory Location: #myName1Add04B 06D 069 07E 030 05E 07F 021 098 030 030 And at Memory Location:
#myName2Add04A 06F 068 06E 030 04E 06F 061 068 030 030
To receive full marks, your code needs to be in the form of a subroutine that can be called using the JnS instruction. You need to write a MARIE main program to call this subroutine.
2.4 A subroutine for entering names from keyboard (10 marks)
In this task, we will focus on getting our names as input from keyboard, and storing them in a particular location in MARIE memory. For this task, prepare a MARIE subroutine called
4
subInputNames to input names from keyboard, when you input Unicode /ASCII ‘0’ terminated strings, two of them, consecutively, to be treated as First and Last names. The names are to be stored beginning at memory address 500H one name (First Name and Last Name) in one row of MARIE memory. At the end of the “Last Name” entry, a second Unicode/ASCII ‘0’ will be stored to mark the end of the current name in the memory, and proceed to input the second name, which is to be stored at memory location 510H. This location is one row (16 words) forward from the memory location of the last name entry. After the last name entry, a ‘$’ from input will terminate the entire name entry process, and control will return to the calling program. You can verify the correct working of your program by viewing the memory content starting from #500H.
To receive full marks, your code needs to be in the form of a subroutine that can be called using the JnS instruction. You need to write a MARIE main program to call this subroutine.
2.5. Printing Names that are entered from Keyboard (10 marks)
Prepare a MARIE subroutine called printMultipleNames which uses the code from parts 2.2 and 2.4 to output some names that are entered from keyboard.
To receive full marks, your code needs to be in the form of a subroutine that can be called using the JnS instruction. You need to write a MARIE main program to call this subroutine.
3.1 A Simple Calculator in MARIE (20 marks)
In this task you will develop a MARIE program that implements four basic functions of a calculator – addition, subtraction, multiplication and division.
The program should be performing the user selected tasks (one of the mentioned mathematical operations) after the user enters one of the selection inputs, ‘a’, ‘s’, ‘m’ or ‘d’. Here, input ‘‘a’ selects addition process, ‘s’ selects subtraction process, ‘m’ selects multiplication process and ‘d’ selects division process. User enters ‘q’ to quit the program.
You are required to write subroutines to perform these tasks (addition, subtraction, multiplication and division) and write a main program to process user selection inputs and call the appropriate subroutine thereof. The codes must contain comments, as a paragraph before any block of code i.e. subroutine or as inline comments wherever appropriate. You should submit the “*.mas” files together with the rest of your assignment.
Files to be submitted:
One zipped folder named “YourFirstName_LastName_StudentID” containing the following files and zipped/compressed (YourFirstName_LastName_StudentID.zip):
1. Report for the written tasks (One PDF file called YourFirstName_LastName_ StudentID.pdf). The report should include your Full name, your student ID, your class number and your tutor’s name. Also include the original truth table in the pdf.
2. The pdf report should show the workings for the following:
5
a. Subtask-1: Optimize the function using Karnaugh maps to its minimal form b. Subtask-2: Optimize the function using Boolean identities and verify its
minimal form from the subtask-1.
3. You will need to include two Karnaugh maps worked on two separate Boolean
Identities reduction forms, one for each output Z1 & Z2. Your documentation must show
a. the maps.
b. the groups found in the maps
c. The Boolean identities reduction steps
d. and how they relate to terms in the optimized Boolean function.
4. Two Logisim files, one for task 1.2 and one for 1.3, name them LogicalCircuit.circ and OptimizedCircuit.circ respectively.
5. Suggested MARIE file names are given below:
● 2_1_Name.mas
● 2_2_PrintName.mas
● 2_3_SwapName.mas
● 2_4_InputName.mas
● 2_5_PrintingNamesFromKeyboard.mas ● 3_1_SimpleCalculator.mas
Zip the folder with this name (YourFirstName_LastName_StudentID.zip) and submit it to Moodle. You need to make sure there are no spaces in any of the filenames.
6