MCD4700 Introduction to computer systems, networks and security - Assignment 1 Boolean Algebra and Logisim Task
MCD4700
Introduction to computer systems, networks and security
Assignment 1
Trimester 2, 2022
Submission guidelines
This is an individual assignment, group work is not permitted
Deadline: 12 August, 2022, 11:55 pm
Submission format: docx for the written tasks, LogiSim circuit files for task 1, MARIE assembly files for task 2. All files must be uploaded electronically via Moodle.
Late submission:
● By submitting a Special Consideration Form or visit this link: https://lms.monashcollege.edu.au/course/view.php?id=1331
● Or, without special consideration, you lose 5% from 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 Y marks, only (Y - Y×n×0.05) will be counted where n is the number of days you submit late.
● Assessment items will not be accepted after more than 14 calendar days unless a Special Consideration application has been approved. This 14-day time frame does not apply to assessments due in Week 12.
In-class interviews: See instructions for Task 2 for 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. If there is any evidence of copying (including from online sources without proper attribution), collaboration, pasting from websites or textbooks, Zero marks may be awarded for the whole assignment, the unit or you may be suspended or excluded from your course. Monash Colleges policies on plagiarism, collusion, and cheating are available here or see this link:
https://www.monashcollege.edu.au/__data/assets/pdf_file/0010/17101/dip-assessment-policy.pdf
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. Boolean Algebra and Logisim Task (40 marks)
| Input | Output |
|
| |||
A | B | C | D | Z1 | Z2 | Z1 terms | Z2 terms |
0 | 0 | 0 | 0 | 1 | 0 | A’B’C’D’ | - |
0 | 0 | 0 | 1 | 1 | 0 | A’B’C’D | - |
0 | 0 | 1 | 0 | 1 | 1 | A’B’CD’ | A’B’CD’ |
0 | 0 | 1 | 1 | 1 | 0 | A’B’CD | - |
0 | 1 | 0 | 0 | 0 | 0 | - | - |
0 | 1 | 0 | 1 | 0 | 0 | - | - |
0 | 1 | 1 | 0 | 1 | 0 | A’BCD’ | - |
0 | 1 | 1 | 1 | 1 | 0 | A’BCD | - |
1 | 0 | 0 | 0 | 0 | 1 | - | AB’C’D’ |
1 | 0 | 0 | 1 | 0 | 1 | - | AB’C’D |
1 | 0 | 1 | 0 | 1 | 1 | AB’CD’ | AB’CD’ |
1 | 0 | 1 | 1 | 1 | 0 | AB’CD | - |
1 | 1 | 0 | 0 | 0 | 1 | - | ABC’D’ |
1 | 1 | 0 | 1 | 0 | 0 | - | - |
1 | 1 | 1 | 0 | 1 | 0 | ABCD’ | - |
1 | 1 | 1 | 1 | 0 | 0 | - | - |
Truth table for Z1 and Z2
Step 1: Boolean Algebra Expressions (10 marks)
Write the Boolean equation for your truth table in sum of products form (your choice). First, think about how to deal with the two outputs. Then, describe each single row in terms of Boolean algebra. Finally, combine the Boolean terms for each row into a larger term. Briefly explain these steps for the truth table given.
Z1= A’B’C’D’+A’B’C’D+ A’B’CD’+ A’B’CD+ A’BCD’+ AB’CD+ AB’CD’+ AB’CD+ ABCD’
Z2= A’B’CD’+ AB’C’D’+ AB’C’D+ AB’CD’+ ABC’D
Step 2: Logical Circuit in Logisim (10 marks)
Model the resulting Boolean terms from Step 1 in a single Logisim circuit, using the basic gates AND, OR, NOT. Use the original Boolean expression for drawing the circuit (do not simplify the expression). You can use logic gates with more than two inputs.
To do this task you have to use a template Logisim file “task_1.2_and_1.3_template” that has been provided with this assignment. Do not forget to rename it and do not change the labels or add any extra label, otherwise 2 marks will be detected.
Step 3: Optimised Circuit (20 marks)
The goal of this task is to find a minimal circuit (using only universal NAND gates). Based on the truth table and Boolean algebra terms from Step 1, optimize the function using Karnaugh maps.
You 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 logic circuit. Don’t use any other gates, other than NAND. Your documentation should also show how the equations have been changed to “NAND only”. Use the template Logisim file “task_1.2_and_1.3_template” that has been provided with this assignment. Do not forget to rename it.
Then use Logisim to create a logic circuit. Don’t use any other gates, other than NAND. Use the template Logisim file “task_1.3_template” that have been provided with this assignment. Do not forget to rename it.
Z1 table
| C’D’ | C’D | CD | CD’ |
A’B’ | 1 | 1 | 1 | 1 |
A’B | 0 | 0 | 1 | 1 |
AB | 0 | 0 | 0 | 1 |
AB’ | 0 | 0 | 1 | 1 |
Z2 table
| C’D’ | C’D | CD | CD’ |
A’B’ | 0 | 0 | 0 | 1 |
A’B | 0 | 0 | 0 | 0 |
AB | 1 | 0 |
| 0 |
AB’ | 1 | 1 | 0 | 1 |
Z1 = A’B’+A’C+B’C+CD’
Z1=(A’B’+A’C+B’C+CD’)’
Z1=(A’B’. A’C. B’C. CD’)’
Z2=AC’D’+AB’C’+B’CD
Z2= (AC’D’+AB’C’+B’CD)’
Z2= (AC’D’. AB’C’.B’CD)’
2. MARIE (60 marks)
In this task you will develop a MARIE application that performs some manipulation of characters, strings and numbers. We will break it down into small steps for you. Most of the tasks require you to write code, test cases and some small analysis. The code must contain proper comments and well indented. You 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.
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.
Background - Lists of data
In computer programming, quite often we have to deal with lists of numbers (or other types of data). There are different approaches to store lists in computer memory. The approach we will study here works like this: All data in the list is stored sequentially in memory, i.e. the list will occupy a contiguous block of memory. Other than list data, we also need to keep a record of list size. It will be useful whenever we have to process all the items in a list.
In a MARIE program, a list of four numbers can be defined as below. Note how we have to store size in a separate variable.
ListAddr, ADR List
Size, Dec 4
List, Dec 2
Dec -4
Dec -1
Dec 7
Note that ADR is used to load the address of a label into another label. For example, assuming label List ends up in memory at address 2A. Now if we want to use indirect addressing instructions (e.g. LoadI), we need to get the address of List (i.e., 2A). The ADR keyword will be helpful here. So, the line ListAddr, ADR List will result in the value 2A being placed at the label ListAddr. So now we can use an instruction like LoadI ListAddr in order to indirectly load from the list. Try this out in the simulator to get an idea how it works.
2.1. Reading in a List of Integers (10 marks)
Prepare a MARIE program which first reads in a positive integer, Size (representing the number of items which will be received), and then reads in a group of integers one item at a time until there are Size of them and stores these into memory sequentially, starting from an address which is referenced by ListAddr (add described in the background section).
Document at least two test cases using screenshots of what Size and the list values are in the memory and in the output area (the first value is the size and the reset is the list). The document should be written into the report, such as the screenshot in Figure 1.
Figure 1: Reading in a List of Integers
2.2. ListInput and ListOutput Subroutines (10 marks)
Convert the above program into a subroutine called ListInput. When the main program runs, it should call the subroutine to get size and list numbers as input from the user and then reads in a group of integers one item at a time until there are Size of them and stores these into memory sequentially. Implement another subroutine called ListOutput which will display all the values after saving them into the memory (use output).
Note: Should read the list from the memory and display it.
Document at least two test cases using screenshots of what Size and the list values are (the first value is the size and the reset is the list) into the memory and in the output area. The document should be written into the report, such as the screenshot in Figure 2.
Figure 2: ListInput and ListOutput Subroutines
2.3. Finding the Minimum, Maximum and Range (15 marks)
a. Prepare a MARIE subroutine FindMinMax which takes the size and address of a list (ListAddr), and iterates over the list items to find the minimum and maximum value. As a hint, you may assume the first item in the list is the maximum (and minimum) and then update the maximum (or minimum) if you find any later elements exceed it (or smaller). A pseudo code of this method is given below
let min = first_item, max = first_item, count = size while (count > 0){ item = get_next_item_from_list if (item > max) max = item
if (item < min) min = item
count = count - 1
}
In the main program, call the FindMinMax subroutine and output the minimum and maximum values obtained respectively. For this task, hard code the list and the size of the list, the size should be any number greater than 3.
b. Prepare a MARIE subroutine FindRange takes the maximum and minimum of the list of items (as determined by your code in part a) and computes the difference
between them (maximum - minimum) and outputs them (minimum, maximum and range respectively). This is called
range in statistics.
A pseudo code of this method is given below
range = max - min
Document at least two test cases using screenshots of what minimum and maximum values (display minimum, maximum and range respectively). The document should be written into the report, such as the screenshot in Figure 3.
Figure 3: Finding the Minimum, Maximum and Range
2.4. Finding the Even and Odd (15 marks)
Prepare a MARIE subroutine called EvenOdd which takes a value from the user and check if it is odd or even. If the value is odd display the value and zero else display the value and one.
Write a main program where the user will be repeatedly asked to enter (input) value, store the number in a variable, then find and display (output) the number and zero (if it is odd) or one (if it is even). The program will only stop when a zero is entered.
Hint: this task can be solved either
• Using divide by 2, division operation can be achieved by repeated subtraction, this program needs N (the numerator) and D (the denominator, in this task D=2) (N= N - 2) operations until we get N smaller than 2.
1. Set R =0, Q = 0
2. Is N < 2,
3. Jump to Line 5
4. N = N - 2, Q = Q + 1, R = N
5. Jump to Line 2
6. Return
• Or, start with a variable as 1 and switch it numerator (N) times (0 to 1 and 1 to 0). If the variable gets the original value (which is 0) back, then N is even, else N is odd.
1. isOdd = 0
2. Is N = 0,
3. Jump to Line 5
4. N = N - 1, isOdd = opposite isOdd (flip isOdd)
5. Jump to Line 2
6. Return
Figure 4: Finding the Even and Odd
Code Documentation and Development (5 marks)
All the variables/labels should have a meaningful naming convention. The code should include proper comments.
Code Readability (5 marks)
Before you submit, be sure your code is well organised and very easy to follow included code indentation, effective use of whitespace etc.
Files to be submitted:
One folder named “YourFirstNameLastNameStudentID” containing the following files:
1. Report for the written tasks (One Word file called YourFirstNameLastName StudentID.doc / docx). The report should include your Full name, your student ID, your class number and your tutor’s name.
2. Two Logisim files, one for task 1.2 and one for 1.3, name them LogicalCircuit.circ and OptimizedCircuit.circ respectively.
3. MARIE files for tasks 2.1 to 2.4 name them as below:
● 2.1_ReadinginaListofIntegers.mas
● 2.2_ListInputandListOutputSubroutines.mas
● 2.3_AB_FindingtheMinimumMaximumRange.mas
● 2.4_ FindingtheEvenandOdd.mas
Zip the folder under the same name and submit it to moodle. You need to make sure there are no spaces in any of the filenames.
NOTE! Your submitted files must be correctly identified (as described above). Any submission that does not comply will receive an automatic 10 marks penalty (applied after marking).
