FIT1047 Tutorial 4 & 5 – Sample Solution
Topics • Memory addressing
• Programming MARIE assembly code
• Boolean Algebra, Digital Circuit logic, K-Map & Assignment 1 Discussion Instructions
The tasks are supposed to be done in groups of two or three students. You will need the MARIE simulator for this assignment.
Task 1: Conditionals
A conditional statement allows the flow of a program to depend on data. In a high- level programming language, this is typically achieved using if-then-else statements such as the following (this is Python syntax):
if X == Y: X=X+Y
else: Y=Y+x
Implement this piece of code using MARIE assembly. Make use of labels!
Task 2: Subroutines
An important concept in programming is that of a procedure, function, or subrou- tine, a piece of code that has a fixed purpose and that needs to be executed over and over again.
As a simple example, you saw last week that MARIE doesn’t have an instruction for multiplication. Now imagine a large program: you will probably need the multiplication routine in hundreds of different places!
Of course, you could just copy and paste the piece of code into the place where you need it. Discuss why that’s a bad idea!
• Copying and pasting the code increases the number of lines of code (the complexity of the code), making it harder to write the code in the first place and reducing the readability of the code.
• As a consequence of increased code complexity, if we make a mistake we have to fix it in hundreds of different places. This is error-prone and means that the program will likely contain more bugs. Similarly, if requirements change, there is no single piece of code that needs to be changed. Subroutines therefore also improve the maintainability of the code.
1
Most ISA (Instruction Set Architectures) have some level of support for writing subrou- tines. In MARIE, there’s the JnS X instruction (“jump and store”): It stores the value of the PC at memory address X and then jumps to address X+1. The value stored at X is called the return address, i.e., the address where execution should continue once the subroutine has finished its job.
To return from a subroutine, the last instruction in the subroutine should be a jump back to the return address. This can be achieved using the JumpI X instruction: it jumps to the address stored at address X (compare that to Jump X which jumps to the address X).
1. Explain how you can use JnS X and JumpI X to implement subroutines. In par- ticular, think about why JnS stores the value of the PC, not PC+1.
JnS X can be used to jump to the subroutine while saving the PC at address X. JumpI X can be used to return from the subroutine.
JnS X saves the PC not PC+1 because the program counter (PC) holds the address of the next instruction to be executed in the program. This will be the instruction to be executed after returning from the subroutine.
2. Implement a simple subroutine that computes 2 × X, i.e., it takes the value in a memory location X, doubles it, and returns to where the original program left off.
See sample MARIE assembly code subroutine double.mas.
3. Take the multiplication code from last week and convert it into a subroutine. See sample MARIE assembly code subroutine mult.mas.
4. Write the following code segment in MARIE assembly language: (Optional)
Label
Instruction
Operand
Begin,
Load
var_X
Subt
Ten
skipcond
000
Jump
Done
Load
var_X
Add
One
Store
var_X
Jump
Begin
Done,
Halt
var_X
Dec
1
One,
Dec
1
Ten,
Dec
10
X=1
while X < 10 do
X=X+1 endwhile
Solution:
2
Task 3: Boolean Algebra 3.a List the truth table for F .
X
Y
Z
F(X,Y,Z)
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 0 1 1 1 1 1 0
3.b Draw the logic diagram using the original Boolean expression.
3.c Simplify the expression using a Karnaugh map.
Section a is Z, section b is XY and section c is XY . Thus,F(X,Y,Z)=Z+XY +XY
3.d List the truth table for your answer in part 3.c. Solution: Same as 2.a
3.e Draw the logic diagram for the simplified expression in part 3.c.
Digital Logic
Task-4: Exercise 1: Learn to reduce Sum of Products (SOP) using Karnaugh Map. Reduction rules for SOP using K-map
SOLUTION:
SOLUTION: Sum of Products:
To obtain the standard Sum-of-Products expression. Working from the Truth Table, for each row with a true output (i.e., containing 1) list the state of the input variables as a product term (i.e., an AND expression). The AND expressions from each selected row can then be OR’ed together, yielding the Sum of Products form:
Now we will write down the marked groups and find the reduced expression. Quad pair= W’Y’ 1st pair = XYZ 2nd pair = X’YZ’
Now the results of the reduced final expression is:-
F = W’Y’ + XYZ + X’YZ’
This is the required answer.
Task-4: Exercise 2
Learn to reduce Product of Sum (POS) using Karnaugh Map.
SOLUTION: Product of Sums: Working from the truth table, for each row with a zero output, list the state of the input variables as a product term and complement this sum of products to get product of sums:
Now we will write down the marked groups and find the reduced expression. Quad pair= WY’ 1st pair = X’YZ 2nd Pair = XYZ’
Now the results of the reduced final expression is:-
F’ = WY’ + X’YZ + XYZ’
� ��������������������������� F= WY’ + X’YZ + XYZ’
�������� ������� ������� F=(WY’)� X’YZ��XYZ’�
F = (W’+Y) (X+Y’+Z’) (X’+Y’+Z)
This is the required answer.
Task-4: Exercise 3
Given the following truth table:
A
B
C
Output (F)
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
1
1
1
1
0
a) Write a Boolean expression in the Sum-of-Products standard format that represents the logic function performed by this circuit.
SOLUTION: Sum of Products:
Take the truth table to obtain the standard Sum-of-Products expression. Working from the Truth Table, for each row with a true output (i.e., containing 1) list the state of the input variables as a product term (i.e., an AND expression). The AND expressions from each selected row can then be OR’ed together, yielding the Sum of Products form:
𝑇𝑇h𝑖𝑖𝑖𝑖 𝑖𝑖𝑖𝑖 𝑡𝑡h𝑒𝑒 𝑟𝑟𝑒𝑒𝑟𝑟𝑟𝑟𝑖𝑖𝑟𝑟𝑒𝑒𝑟𝑟 (𝑆𝑆𝑆𝑆𝑆𝑆) 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑒𝑒𝑏𝑏𝑏𝑏 𝑒𝑒𝑟𝑟𝑟𝑟𝑏𝑏𝑡𝑡𝑖𝑖𝑏𝑏𝑏𝑏 = 𝐹𝐹(𝐴𝐴, 𝐵𝐵, 𝐶𝐶) = 𝐴𝐴̅𝐵𝐵�𝐶𝐶 + 𝐴𝐴𝐵𝐵�𝐶𝐶̅ + 𝐴𝐴𝐵𝐵𝐶𝐶̅
b) From the truth table: convert the logic function into the Product-of-Sums standard format.
SOLUTION: Product of Sums:
Working from the truth table, for each row with a zero output, list the state of the input variables as a product term and complement this sum of products to get product of sums: 𝐹𝐹� = 𝐴𝐴̅𝐵𝐵�𝐶𝐶̅ + 𝐴𝐴̅𝐵𝐵𝐶𝐶̅ + 𝐴𝐴̅𝐵𝐵𝐶𝐶 + 𝐴𝐴𝐵𝐵�𝐶𝐶 + 𝐴𝐴𝐵𝐵𝐶𝐶
�������������������������������������������� 𝐹𝐹 = 𝐴𝐴 ̅ 𝐵𝐵� 𝐶𝐶 ̅ + 𝐴𝐴 ̅ 𝐵𝐵 𝐶𝐶 ̅ + 𝐴𝐴 ̅ 𝐵𝐵 𝐶𝐶 + 𝐴𝐴 𝐵𝐵� 𝐶𝐶 + 𝐴𝐴 𝐵𝐵 𝐶𝐶
������ ������ ������ ������
̅�̅ ̅ ̅ ̅ � ������ 𝐹𝐹 = 𝐴𝐴𝐵𝐵𝐶𝐶 ∙ 𝐴𝐴𝐵𝐵𝐶𝐶 ∙ 𝐴𝐴𝐵𝐵𝐶𝐶 ∙ 𝐴𝐴𝐵𝐵𝐶𝐶 ∙ 𝐴𝐴𝐵𝐵𝐶𝐶
𝑇𝑇h𝑖𝑖𝑖𝑖 𝑖𝑖𝑖𝑖 𝑡𝑡h𝑒𝑒 𝑟𝑟𝑒𝑒𝑟𝑟𝑟𝑟𝑖𝑖𝑟𝑟𝑒𝑒𝑟𝑟 (𝑆𝑆𝑆𝑆𝑆𝑆)𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑒𝑒𝑏𝑏𝑏𝑏 𝑒𝑒𝑟𝑟𝑟𝑟𝑏𝑏𝑡𝑡𝑖𝑖𝑏𝑏𝑏𝑏 = 𝐹𝐹(𝐴𝐴, 𝐵𝐵, 𝐶𝐶)
= ( 𝐴𝐴 + 𝐵𝐵 + 𝐶𝐶 ) ∙ ( 𝐴𝐴 + 𝐵𝐵� + 𝐶𝐶 ) ∙ ( 𝐴𝐴 + 𝐵𝐵� + 𝐶𝐶 ̅ ) ∙ ( 𝐴𝐴 ̅ + 𝐵𝐵 + 𝐶𝐶 ̅ ) ∙ ( 𝐴𝐴 ̅ + 𝐵𝐵� + 𝐶𝐶 ̅ )