1. Boolean Algebra and Logisim Task (50 Marks)
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 000010 000110 001001 001111 010010 010111 011000 011111 100001 100111 101010 101101 110011 110101 111010 111101
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 Boolean Algebra Expressions (10 points)
Write the Boolean functions as Boolean algebra terms, using either the Product of Sums (POS) or Sum of Products (SOP) method. Notice that the truth table consists of four inputs and two outputs. Hence you must have two separate Boolean functions representing two outputs to the same input set.
Briefly explain the steps you followed to formulate the two Boolean functions from the given truth table. Please use standard notation for writing Boolean algebra expressions. Boolean “AND” is written without a symbol, e.g. X1X2. Boolean OR is written with the ‘+’ symbol, e.g. “X1 + X2”. Boolean negation is
written using an over-line, e.g. 𝑋1 . When writing terms like “NOT X1 AND NOT X2”, there must be a clear gap in the over-lines, e.g. 𝑋1 𝑋2 . Hint: Note that 𝑋1 𝑋2 𝑋3 𝑋4 is not equal to “ 𝑋1. 𝑋2. 𝑋3.𝑋4”.
1.2 Logical circuit in Logisim (20 points)
Model the resulting Boolean terms from section 1.1 in a single logic circuit in Logisim, using only the basic gates AND, OR, NOT. You can use logic gates with more than two inputs. The logic circuit should show all the four inputs, and both the outputs Z1 & Z2 with appropriate labels. The two outputs should not be split up into two different Logisim circuits.
● Briefly explain your construction (same as for section 1.1, a short explanation is enough).
● Test your circuit using input values from the truth table and document at least three test cases
(you may take “Print Screen” of your Logisim logic circuit showing appropriate inputs and corresponding outputs).
1.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 section 1.1.
1. Subtask-1: Optimize the function using Karnaugh map to its minimal form.
2. Subtask-2: Optimize the function using Boolean identities and verify its minimal form with that
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) reduced Boolean functions derived from K-Maps.
d) The two Boolean identities reduction for Z1 & Z2 with steps.
e) A comparison of the two methods (K-Map & Boolean Identities methods) showing 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 at least three test cases (you may take “Print Screen” of your Logisim logic circuit showing appropriate inputs and corresponding outputs).
Note: You can use Product-of-Sum or Sum-of-Product to optimise in subtask-2.
2. MARIE Task (50 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 your code with sample inputs and write the analysis of the outcome explaining the expected outcome. Your MARIE program must contain brief comments explaining the purpose of your subroutines and main programs (to be written in the .mas file). You must submit your code as .mas files together with the rest of your assignment.
The description of your experiences while testing your code with test inputs and the subsequent analysis needs to be submitted as part of the main PDF file you submit for this assignment. In some cases wherever it is appropriate, you may add test data to your program to prepare test cases. These test cases, which are mostly appropriate for programs processing numeric data, should be working without requiring much input from the user, i.e. a self-contained MARIE assembly program.
The following section introduces some concepts that you need for the rest of the assignment.
Name as Strings
A string is a sequence of characters. It is 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. For this assignment, we will use the following string representation:
● A string is represented in a contiguous memory location, with each address containing a
single character.
● The characters are encoded using the ASCII encoding. End of a string is marked by the ASCII
character comma ‘,’.
● 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 dot ‘.’.
Representation of Strings in Memory using ASCII code
An illustrated example below showing 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 + 2 words of memory in order to store all the characters belonging to a first name, a last name, the additional ‘,’ and ‘.’.
Strings in MARIE
In MARIE assembly language programming, we can make use of the ADR command, the HEX
keyword and a label “myName” to put a string into memory location:
myNameAdd, ADR myName
myName, HEX 04A //J HEX 06F //o HEX 068 //h HEX 06E //n HEX 02C //, HEX 04E //N HEX 06F //o HEX 061 //a HEX 068 //h HEX 02E //.
After assembling the above MARIE code, we will find that the variable (or label) myNameAdd contains the address of the string i.e. the address of the first character ‘J’ of the string “John Noah”. An example below shows how to access the first character of the above string and display:
start, LoadI myNameAdd Output
……… Halt
2.1 Write a MARIE Program to Store Multiple User Entered Names in Consecutive Memory Rows and Print Them at the End of Data Entry. (20 marks)
Prepare a MARIE program to enter full names using Unicode / ASCII characters. Limit each part of a name (First Name or Last Name) to at most 5 characters – if a name is longer, you can shorten it (limit the maximum number of characters per full name to 12). After assembling and running your MARIE program, it should prompt for entering names using a keyboard. For the MARIE simulator, Unicode input from the keyboard can only be entered character by character. Your program should store the names in MARIE memory and print them at the end.
(i). Subroutine subInputNames: The first part of your program should focus on getting the full names as input from the keyboard and storing them in a particular location in MARIE memory. For this task, prepare a MARIE subroutine called subInputNames. Your subroutine should input (Unicode /ASCII) ‘,’ terminated First name and (Unicode /ASCII) ‘.’ terminated Last name as described in the previous section. The names have to
be stored starting from the memory address 300H. A single name (First Name and Last Name) is to be stored in one row of MARIE memory. After entering a full name, a Unicode/ASCII ‘.’ will be stored to mark the end of the name in the memory, and the program should proceed to take the next name, which is to be stored at memory location
310H. This location is one row (16 words) ahead from the memory location of the
previous name entry. You can use memory locations 320H, 330H, … to store more names respectively. After entering a full name, a ‘$’ from input will terminate the entire name entry process and will return control to the calling program. You have to store the ‘$’ in the memory to mark the end of the name database. Your program must be capable of accepting names one after the other, until a user enters a ‘$’ to stop taking inputs. You can verify the correct working of your program by viewing the memory content starting from
#300H.
(ii). Subroutine subPrintString: In the second part of your program, prepare a MARIE subroutine called subPrintString that can print all the full names stored. This subPrintString subroutine should access all the full names in the memory (that are entered and saved by the subInputNames earlier) and printout using the “Output” instruction.
Start by using a label “PrintNameAdd” 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 ‘,’, then increment the address by one, and keep doing that until the character loaded from the address is a ‘,’ (which signals the end of the first name). Then, instead of printing (or output) the ASCII “,” character, 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 ‘.’ (which signals the end of the Last Name). Then, when you load the ASCII ‘.’ which marks the “end of a name”, instead of printing (or output) the ASCII “.” character, print an ASCII “New Line” character. Then your program should proceed to print the next name. If the loaded character is ‘$’, the subroutine needs to stop printing and gives control to the main program. While testing your code and writing the test cases for this task, you have to use at least three names (your First Name and Last Name, your friend’s name and your tutor’s name). Please note that these names should not be hard coded and assigned labels to identify each of these three names.
To receive full marks, your code needs to be in the form of a main program and use of subroutine that can be called using the JnS instruction. Save your code as “2_1_Enter_and_PrintingNames.mas”.
2.2 A MARIE Subroutine to Change Cases of Characters of User Entered Names (Upper to Lower or Lower to Upper Cases) and Print (15 marks)
Write a subroutine to change cases of all the characters of a user entered name string: Upper to Lower case or Lower to Upper case. Name the subroutine as subChangeCase. This subroutine modifies all the characters of a string in memory (from lower to upper or upper to lower cases). The program should then print the original and the modified string. Submit your MARIE code and documentation of test cases converting at least three names. To receive full marks, the main program from section 2.1 must be extended to print the original name string and the modified changed-case name string by calling the respective subroutines. Name your MARIE code file as “2_2_ChangeCase.mas”.
Hint: you can easily identify the uppercase or lowercase ASCII value ranges through the ASCII table and notice the numeric difference between the uppercase and lowercase characters.
2.3 A MARIE Subroutine to Substitute Characters of User Entered Names and Print (15 marks)
In this section, we are going to implement substitution of characters of a user-entered name. It replaces each character in a string by a different character of the alphabet defined by a simple shift. A shift of 3 positions, shown in the table below.
abcdefghijklmnopqrstuvwxyz defghijklmnopqrstuvwxyzabc
Please note the use of lower case alphabets only, and we will substitute only “alphabets”.
To substitute, the corresponding letter in the bottom row replaces each letter in the top row. You will implement mapping in MARIE by a lookup table, storing the result of substitution for each letter. The lookup table below maps a shift of three (3) positions.
mySubstKey1Addr,ADR mySubstKey1
mySubstKey1,
HEX 064 / a -> d HEX 065 / b -> e HEX 066 / c -> f HEX 067 / d -> g HEX 068 / e -> h HEX 069 / f -> i HEX 06A / g -> j HEX 06B / h -> k HEX 06C / i -> l HEX 06D / j -> m HEX 06E / k -> n HEX 06F / l -> o HEX 070 / m -> p HEX 071 / n -> q HEX 072 / o -> r HEX 073 / p -> s HEX 074 / q -> t HEX 075 / r -> u HEX 076 / s -> v HEX 077 / t -> w HEX 078 / u -> x HEX 079 / v -> y HEX 07A / w -> z HEX 061 / x -> a HEX 062 / y -> b HEX 063 / z -> c
A subroutine to perform substitution on a string
In this task, you will implement a MARIE subroutine called subSubstitution that can perform substitution on a string. You need to display the string before and after the substitution process. You can assume that the string only contains lower case characters. For each letter in the string, you will need to load the correct value for its substitution from the table “mySubstKey1”, and then store that value in memory.
Think about how to get “a value” from a table. e.g., assume that the original letter is ‘k’, which is the 11th letter in the alphabet. Therefore, we need to load the 11th entry in the table – in other words, the entry at address mySubstKey1Addr + 10 (which is HEX 06E or DEC 110, or the letter ‘n’).
The letter ‘k’ has an ASCII value of HEX 06B (DEC 107). So, how do we determine to add ‘10’ to the address “mySubstKey1Addr”? We simply subtract the ASCII value for the letter ‘a’, which is HEX 061 (DEC 97). So, in decimal notation, “117 – 97 = 10” or in HEX notation, “HEX 06B – HEX 061 = HEX A.” The following illustrated example explains the substitution process further. Here, the first name is “patrick”, and the last name is “lee.” And, it will be stored in the memory as shown below.
070 061 074 072 069 063 06B 020 06C 065 065 02E patrick lee.
During the substitution process, the following transformation (in the memory) will occur.
patricklee sdwulfnohh
Moreover, the new substituted string will be stored in the memory as shown below.
073 064 077 075 06C 066 06E 020 06F 068 068 02E sdwulfn ohh.
Please note that, during the substitution process, ASCII value for “SPACE” and ‘.’ remains unchanged. 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.