FIT1047 S1 2019 Assignment 1
Submission guidelines
This is an individual assignment, group work is not permitted.
We use tools to check for plagiarism and collusion. 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.
Individualized exercises: Some exercises require you to pick one of several options based on your student ID.
Late submission:
• By submitting a special consideration form, available from http://www.monash.
edu.au/exams/special-consideration.html
• 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: See instructions for Task 2 for details.
Marks: This assignment will be marked out of 100 points. It is worth 22.5% 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, and pasting from websites or textbooks. This includes both the student who copies, and the student who lets them copy!
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.
1
1 Boolean Algebra and Logisim Task
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
0
1
0
0
1
1
1
0
1
1
1
0
1
1
0
0
1
0
1
1
0
1
0
1
0
1
1
0
0
1
1
Table 1: Truth table for Z1 and Z2
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 Step 1: Boolean Algebra Expressions (10 points)
Write the Boolean equation for your truth table in products of sums form. First, think about how to deal with the two outputs. Then, describe each single row in terms of Boolean algebra. Finally, combine the terms for single rows into larger terms. Briefly explain these steps for the truth table given.
1.2 Step 2: Logical circuit in Logisim (10 points)
Model the resulting Boolean terms from Step 1 in a single Logisim circuit, using the basic gates AND, OR, NOT. You can use gates with more than two inputs.
1.3
• •
Explain what you did for each step.
Test your circuit using values from the truth table and document the tests.
Step 3: Optimized circuit (15 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, optimize the function using Karnaugh maps.
You will need to create two Karnaugh maps, one for each output. Your documentation should show the maps as well as the groups found in the maps and how they relate to terms in the optimized Boolean function.
Then use Logisim to create a minimal circuit. Don’t use any other gates other than AND, OR, and NOT. Test your optimized circuit using values from the truth table.
Page 2
2 Statistics of a sorted data set in MARIE
This task will require you computing the median of a set of sorted numbers. We will break it down into small steps for you. Most of the tasks require you to write code and test cases. 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.
Important: In-class interviews – You will be required to demonstrate your code to your tutor after the submission deadline. Failure to demonstrate will lead to zero marks being awarded to the entire programming part of this assignment.
2.1 Inputting a list of numbers (15 marks)
The first step is to input a set of numbers (number-by-number, using the Input instruction). You can assume that this will be a set of positive integers and that the last number given will be a zero. This means you can keep reading numbers until you receive a zero.
Setup code in MARIE which reads a set of positive integers and stores these as an array (contiguous block of memory). Do not include the 0 in the array; as you accept numbers you should keep track of the size and store this in a variable once all the reading is complete. Print the size of the array using the Output instruction to help you test that your program is correct.
2.2 List input subroutine (5 marks)
Extend your list input so that it can be used as a subroutine.
2.3 Checking the order (15 marks)
This part will require you to determining whether the given array is in order. Once you have an array of positive numbers, step through this array and store 1 in a variable inOrder where it is in ascending order or 0 otherwise. You should implement this as a subroutine which can be triggered once all the array values have been entered. You may like to display this variable for testing purposes.
2.4 Division by 2 (10 marks)
Prepare a MARIE subroutine DIV which computes the quotient and remainder for dividing a number by 2.
This can be done by the method of successive subtraction. The strategy is as follows:
1. accept a numerator N and divisor D 2. set quotient Q to zero
3. while N ≥ D…
increase Q by one
reduce N by D
4. N now holds the remainder and Q holds the quotient
2.5 Finding the Median (10 marks)
Once you know that the set of numbers are in order, find the middle value in the array to use as the median. Your DIV subroutine should help here. If there are two middle values (e.g. there are an even number of items) you should use the left of these as the median.
Page 3
2.6 Complete Program (10 marks)
As a final step, combine all the previous subroutines into a program that does the following:
• Let a user input a list of numbers using the subroutine from 2.2
• Check whether or not that list is in order using your subroutine from 2.3
• Find the median of this list of numbers using your subroutine from 2.5 (note this will also involve using your division by two subroutine from 2.4)
• Output whether the list is in order (as a 0 or 1) and then the median if there is one
Files to be submitted:
One folder named ”YourLastName FirstName StudentID” containing the following files:
1. Report for the written tasks (YourFullName YourStudentID.PDF). 2. Two Logisim files, one for task 1.2 and one for 1.3 call them as
• LogicalCircuit.circ and
• OptimizedCircuit.circrespectively.
3. Six MARIE files for task 2, name them as
• 2.1 InputtingList
• 2.2 InputtingListSubroutine
• 2.3 CheckingOrder
• 2.4 DivisionBy2
• 2.5 FindingMedian and
• 2.6 CompleteProgram respectively and submit all as .mas files.
Zip the folder under the same name and submit it to Moodle.
Page 4