MCD4700 – Introduction to Computer Systems, Networks and Security
Assignment 1 – Trimester 3, 2020
Submission guidelines
This is an individual assignment, group work is not permitted Deadline: November 30, 2020, 11:55pm
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://forms.apps.monash.edu/frevvo/web/tn/monash.edu/u/614aac3c-8ab8-4309- 9283-375663fa97d8/app/_86jlUBdoEeiMWO8cc5Na1A/form/c87ebd1e-ce2d-4a5f- b00d- 04027382df50?typeId=_uSFSQParEemFyv5Ip1_2Eg&locale=en_US,eng_US,eng,en& embed=true
¡ñ Or, without special consideration, you lose 5 marks 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 Y marks, only Y-n*5 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 College¡¯s 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.
¡ñ Assessments due in Week 12 will not be accepted more than 7 calendar days after the due date.
1. Boolean Algebra and Logisim Task (35 marks)
Input
Output
A
B
C
D
Z1
Z2
0
0
0
0
0
0
0
0
0
1
1
0
0
0
1
0
0
0
0
0
1
1
1
0
0
1
0
0
0
1
0
1
0
1
1
1
0
1
1
0
0
1
0
1
1
1
0
0
1
0
0
0
0
0
1
0
0
1
1
0
1
0
1
0
0
0
1
0
1
1
1
0
1
1
0
0
0
1
1
1
0
1
0
0
1
1
1
0
0
1
1
1
1
1
1
1
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 terms for single rows into larger terms. Briefly explain these steps for the truth table given.
1
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 it). You can use 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 have 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 (15 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. Your documentation should show how the equations have been changed to NAND only.
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 than NAND. Use the template Logisim file ¡°task_1.2_and_1.3_template¡± that have been provided with this assignment. Do not forget to rename it.
2
2. MARIE (65 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 comments, and 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.
Numbers, Characters and Strings Stored in MARIE Memory
This section introduces the concepts you need for the rest of the assignment. We can store numbers (Decimal or Hexadecimal) or characters in predefined memory locations in MARIE using a combination of the following commands: Input, Adr, StoreI & LoadI. The input data (number or character) can either be from a keyboard or from the program itself i.e. hardcoded. In the following example in Figure1, a user has entered the decimal number ¡°2010¡± from the keyboard.
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.
Instruction No.
Code
1
Input
2
storeI myAdd
3
Halt
4
myAdd, HEX 100
5
One, DEC 1
Memory Location (Hex)
Memory Content
0FFH
100H
0014H
101H
102H
Figure 1 (a)
Figure 1 (b)
Figure1: Instructions and Memory locations in MARIE
These numbers that are stored in memory, we can manipulate them using a combination of available MARIE commands (e.g. Load, LoadI, add, subt, store & storeI).
3
Instruction No.
Code
1
LoadI myAdd
2
Add One
2
storeI myAdd
3
Halt
4
myAdd, HEX 100
5
One, DEC 1
Memory Address (Hex)
Memory Content
0FFH
100H
0015H
101H
102H
Figure 2 (a)
Figure 2 (b)
Figure2: Manipulate data stored into the memory
When a program inputs a series of characters (i.e. a string is a sequence of characters) using Unicode input mode, and stores them in the MARIE memory starting from location #0FFH, it may look like the Figure 3 below. Note that all the entered characters (alphabets, numbers and punctuation marks) are represented in ASCII (using Hexadecimal format).
Memory Location (Hex)
Memory Content
0FFH
048H
100H
069H
04AH
06FH
Figure 3
Character
¡®H¡¯
¡®i¡¯
101H
02CH
¡®,¡¯
102H
¡®J¡¯
103H
¡®o¡¯
104H
068H
¡®h¡¯
105H
06EH
¡®n¡¯
106H
02EH
¡®.¡¯
Figure3: Store a list of characters (string) in MARIE
In MARIE, we can create hard-coded strings and access the member characters one by one by making use of the ADR command, the HEX keyword and a label. Here, the label ¡°myAdd¡± refers to the memory location of the label ¡°myName¡±. So, ¡°myAdd=0001¡± referring to the first character ¡®J.¡¯
4
Instr. No.
Memory Location
Label
Code
Memory Contents
1
000
myAdd,
ADR myName
0001
001
myName,
HEX 04A /J
004A
002
HEX 06F /o
006F
003
HEX 068 /h
0068
004
HEX 06E /n
006E
005
HEX 02C /,
002C
006
HEX 04E /N
004E
007
HEX 06F //o
006F
008
HEX 061 //a
0061
009
HEX 068 //h
0068
00A
HEX 02E //.
002E
Figure 4
Figure4: Manipulate data stored into the memory
2.1 Implement a stack in MARIE (30 marks)
In this section, you will implement a stack in MARIE using a block of memory (a block of two
rows i.e. 32 words should be enough).
In a stack, we remove the item the most recently added.
(i) Subroutine to Perform Push Operation
Write a MARIE subroutine called (Push) to perform the ¡°Push¡± operation of your stack implementation. Here, you will enter characters (ASCII/Unicode) from the keyboard and store in the stack. You need to display the characters while accepting them from the keyboard. You will use two variables to store two memory locations (you may use address #200H for this purpose) to be used as the ¡°Top¡± and ¡°Bottom¡± for your stack. These two variables will have the same addresses at the beginning and will change as you enter data. After a few data entries, the beginning address of the stack i.e. ¡°Top¡± will change while the ending address i.e ¡°Bottom¡± will remain the same. Your data entry will terminate when the user enters a dot character ¡®.¡¯. Please remember that you need to store this character (¡®.¡¯) as well, as it will be a delimiter for the string. This will mark the end of a sentence. In addition to that, the user will enter ¡®,¡¯ as a separator between words. So, the input sequence (from the keyboard) for this sentence ¡°This is a test.¡± will be ¡°This,is,a,test.¡±.
A stack is a ¡°cylinder-like¡± holder of data items, where
items are inserted and removed according to the last-in first-out (LIFO) principle. In this stack
implementation, only two operations are possible: push an item into the stack, and pop an item
out of the stack. So, the data elements can be added to and removed from the stack-top only.
5
(ii) Subroutine to Perform Pop Operation
Write another MARIE subroutine called (Pop) to perform the ¡°Pop¡± operation of your stack implementation. Here, you need to read (i.e. retrieve) and display the characters from the stack
following LIFO logic. While retrieving in this fashion, you are basically reversing the string. You may notice that the new reversed sentence display starts with a dot ¡®.¡¯ sign. The following figure (Figure 5) illustrates the process.
Memory Address
1FCH
1FDH 1FEH 1FFH
Stack [Empty]
Memory Address
1FCH 1FDH 1FEH 1FFH
Figure 5: Stack – Illustrated
Stack
1
0
1
0
(iii) Combining them all
<-Stack-Top <-Stack-Bottom
Now, write a MARIE main program to call these two subroutines to create a stack, store a short sentence (e.g. ¡°Hello, how are you?¡± Or ¡°This is a test.¡± ) in the stack and read from the stack. To receive full marks, you need to write:
a. Two subroutines (for Push and Pop operations) and
b. A MARIE main program to call the subroutines to perform ¡°Push and Pop¡± operations
on your stack.
c. Document at least two test cases using screenshots of what the output screen (in
MARIE) looks like after printing a string (one test for your name and your ID and the
other test for anything). The document should be written into the report.
Please note that you need to use the ¡°JnS¡± command to call the subroutines, and need to use the ¡°JumpI¡± command to return to the calling program.
<-Stack-Top
<-Stack-Bottom
6
2.2 A ¡°Decimal to Binary¡± Converter (35 marks)
In this section, you will implement ¡°A Decimal to Binary Converter¡± using Division and Remainder operations. When a user inputs a decimal number, for example ¡°10¡±, your program will use division and remainder operations to convert and display the corresponding Binary number ¡°1010.¡±
You need to write (i) a subroutine to perform division and remainder operations, (ii) a subroutine to perform ¡°Decimal to Binary¡± conversion, (iii) a main program utilising these subroutines creating a ¡°Decimal to Binary Converter.¡± It is worthy to mention that you need to use a stack to save the successive remainders as they are produced by the division process (using Push operation) and later to read from the stack (using Pop operation) and display. This will reverse the order of appearance of remainders, as it is required for the Decimal to Binary conversion process (see Figure 6).
Division By 2
Quotient
Remainder
Position in the Stack
10/2
5
0
<- This item will be stored at the bottom of the stack. It will be retrieved last.
5/2
2
1
2/2
1
0
1/2
0
1
<- This item will be stored at the top of the stack. It will be retrieved first.
Figure 6: Decimal to Binary conversion using division and remainder
(i) Subroutine For Division & Remainder Operations
Division can be achieved by repeated subtraction (numerator - denominator) until we get a quotient smaller than the denominator, while the remainder can be derived from this division process when we get a quotient that is equal to zero. An algorithm for this is given below:
Algorithm for Division & Remainder Operation [N / D) -> Producing Q and R]
Note: this program (or subroutine) needs N (the numerator) and D (the denominator) as inputs, and produces Q (the quotient) and R (the remainder) as outputs.
1. SetR=0,Q=0
2. IsN