MARIE 程序代写 汇编语言 Boolean Algebra and Logisim Task

1 Boolean Algebra and Logisim Task

The following truth table describes a Boolean function with four input values X1, X2, X3, X4 and two output values Z1, 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 function as Boolean algebra terms. 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 your particular truth table (e.g., explain for one particular row how you come up with the Boolean terms for that row, and then explain how you combine all rows). This explanation should be no more than a few sentences.

Notation: use the following symbols and notation for writing Boolean algebra expres- sions. Variables are upper-case (e.g., X1, Z2). Boolean AND is written without a symbol, e.g. X1X2. Boolean OR is written with the + symbol, e.g. X1+X2. Negation is written using an overline, e.g. X1. Important: when writing terms like NOT X1 AND NOT X2, there must be a clear gap in the overlines, e.g. X1 X2.

2

1.2 Step 2: Logical circuit in Logisim (10 points)

Model the resulting Boolean terms from Step 1 in a single Logisim circuit, using only the basic gates AND, OR, NOT. You can use gates with more than two inputs.

Briefly explain your construction (as for Step 1, a short explanation is enough). Test your circuit using values from the truth table and document the tests.

1.3 Step 3: Optimized circuit (10 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 func- tion using Karnaugh maps.

You will need to create two Karnaugh maps, one for each output. Your documentation must show (a) the maps, (b) the groups found in the maps, and (c) 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 your tests.

2 Development of a Database for Unit Prerequisites in MARIE

In this task you will develop a MARIE program that implements a database with infor- mation about unit prerequisites. We will break it down into small steps for you.

Most of the tasks require you to write code and test cases. On Moodle, you will find a template for the code. It contains some subroutines that you should use, as well as a number of predefined test cases. Your submission must be based on this template, i.e., you must add implementations of your own subroutines into this template. The code must contain comments, and you submit the .mas file together with the rest of your 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 for the entire programming part of this assignment.

Code similarity: We use tools to check for collaboration and copying between students. If you copy your code from other students, or you let them copy your code, you will receive 0 marks for the entire assignment.

3

2.1 Strings

This section doesn’t contain any tasks for you yet, it only introduces a concept you need for the rest of the assignment.

A string is a sequence of characters. It’s the basic data structure for storing text in a computer. There are several di↵erent ways of representing a string in memory – e.g. you need to decide which character set to use (Unicode or ASCII), 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 block of memory, with each address con- taining one character.
• The characters are encoded using the ASCII encoding.
• The end of the string is marked by the value 0.

  As an example, this is how the string FIT1047 would be represented in memory (written as hexadecimal numbers):

  046 049 054 031 030 034 037 000
  

  Note that for a string with n characters, we need n + 1 words of memory in order to store the additional 0 that marks the end of the string.

  In MARIE assembly, we can use the HEX or DEC keywords to initialise the MARIE memory with a fixed string:

FIT1047,

HEX 046
HEX 049
HEX 054
HEX 031
HEX 030
HEX 034
HEX 037
HEX 000

After assembling this code, you can verify that the string has been loaded into the MARIE memory.

The assignment template contains two subroutines. The PrintString subroutine out- puts a string one character at a time using the Output instruction. The InputString subroutine reads a string one character at a time using the Input instruction.

Tip: you can switch the type of input in the MARIE simulator. For the actual string, use the unicode input method so you can enter real characters. For the final 0, switch to the decimal input method.

4

2.2 Your name as a MARIE string (4 points)

This is the first task you need to submit.

Similar to the FIT1047 example above, encode your name using ASCII characters. You should encode at least 10 characters – if your name is longer, you can shorten it if you want, if it’s shorter, you need to add some characters (such as !?! or …, or invent a middle name).

In the assignment template, you will find a label Name, which is initialised to the value HEX 0. You need change this part of the code so that after assembling, the MARIE memory contains the string with your name starting at label Name.

2.3 Trimming a string (14 points)

This is your second task.

Trimming a string means to remove any space characters from the beginning and the end of the string. For example, given the string FIT 1047 as input, trimming it would result in the string FIT 1047. The symbolises a space character (its ASCII value is decimal 32). Trimming is often used to clean up user input.

You have to implement a subroutine TrimString that trims a string. Its argument, which is passed in the label TrimStringAddr, is the address in memory where the string starts. When the subroutine finishes, the string at that address must not contain any leading or trailing space.

We will trim the string in two phases.

Phase 1 (5 points) The first phase removes any trailing space (i.e., spaces at the end of the string). Your code should follow these steps to achieve the result:

1. Iterate through the string, one character at a time, until you reach the end of the string (the 0 character). This is similar to how the PrintString subroutine works, just without actually printing the characters.
2. In step 1, you found the address of the final 0 in the string. Now iterate backwards, and replace any space character (decimal 32) with a 0, until you reach a character that is not a space character, or the beginning of the string.

The second phase removes leading space characters. There are two approaches, an easy one and a more complicated one. You can choose to implement the easy approach for 2 points, or the complex one for 5 points.

5

Easy phase 2 (2 points) This approach modifies the start address of the string, up- dating it to the first non-space character.

1. Iterate through the string, one character at a time, until you reach a character that is not the space character (decimal 32).
2. Update the start address of the string (at label TrimStringAddr) to the address you found in step 1 (the address of the first non-space character).

Complicated phase 2 (5 points, alternative to easy phase 2) The easy approach above has a disadvantage in some programs, because you have to make sure that you don’t use the old string address any more. The following steps will modify the original string and remove leading spaces (without changing its start address).

1. Keep track of two addresses, the current read address CurRead and the current write address CurWrite. Both are initialised with the start address of the string.
2. Iterate through the string by incrementing CurRead until you find the first non- space character.
3. Iterate through the remaining string, reading the character from CurRead and storing it at CurWrite at each step. CurWrite is now incremented together with CurRead in each step.

There’s a short animation on Moodle to help you understand this algorithm.

Test cases (4 points) You need to implement this subroutine in the assignment tem- plate file. The template already contains one test case. Add the following additional test cases, and briefly document them in your submission PDF:

1. Trimming a string that does not contain any space characters
2. Trimming a string that does not contain any leading or trailing space characters, but does contain at least one space character
3. Trimming a string with at least two leading space characters
4. Trimming a string with at least two trailing space characters

6

2.4 String comparison (15 points)

Now we are going to implement a string comparison subroutine. We will use lexicographic ordering, i.e., the ordering you would use e.g. when sorting names alphabetically.

The subroutine takes two (addresses of) strings as arguments and returns -1 if the first string is lexicographically smaller than the second, 0 if they are equal, and 1 if the first string is lexicographically greater than the second string. For example, ABCD is smaller than BCDEF (because the first character is smaller), ABC is smaller than ABCDE (because it is a proper prefix), and BCDF is greater than BCDE (because the first character that is di↵erent, the F, is greater).

The subroutine will communicate the result back to the caller (the code that called JnS) in the address with the label CmpStringResult, i.e., after returning from the subroutine, CmpStringResult will be equal to -1 if the first string is smaller, 0 if the strings are equal, and 1 if the first string is greater.

Subroutine (10 points) In order to achieve this, your code needs to loop through both strings simultaneously, one character at a time:

1. If the current character in the first string is 0 (i.e., the end of the string), check if the character in the second string is also 0. If it is, set CmpStringResult to 0 (“equal”) and return, otherwise set it to -1 (“less”) and return.
2. If the current character in the first string is not 0:
   1. a)  Check if the current character in the second string is 0. If it is, then the first

      string is larger, so set CmpStringResult to 1 and return.

   2. b)  If the current character in the second string is not 0, you now have to compare the two characters. If they are equal, move to the next character in both strings and go back step 1 in order to compare the next characters.
   3. c)  If they are not equal, set CmpStringResult according to the ordering of the characters (i.e., if the character in the first string is less than the character in the second string, set it to -1, otherwise to 1).

You need to implement the subroutine in the assignment template file.

Test cases (5 points) The template already contains one test case, using your name as both arguments, for which your subroutine should return that the two strings are equal. Add the following additional test cases and document them in your PDF submission:

1. A test case where the two strings are empty

7

2. A test case where the first string is shorter and a prefix of the second string (i.e., it’s shorter, but all characters are the same as in the second string; e.g. “abcde” is a prefix of “abcdefgh”)
3. A test case where the second string is shorter and a prefix of the first string
4. A test case where the first two characters of the strings are the same, but the first string is lexicographically smaller than the second
5. A test case where the first two characters of the strings are the same, but the first string is lexicographically larger than the second

2.5 Database lookup

We will now explain the database format. This is just an explanation, the first task you need to implement is in Sect. 2.5.2. Let’s assume we have the following information about unit prerequisites:

• for FIT2093, the prerequisites are FIT1045 and FIT1047

• for FIT2100, the prerequisite is FIT1047
We now have to store this information in our MARIE memory in a way that lets us

query it. For this task, we will use the following encoding into MARIE.

2.5.1 Representing the data in MARIE

For each unit, we store a string that lists the prerequisites. In this case, since our database has two entries (for FIT2093 and FIT2100), we store two strings:

FIT2093, DEC 70 / F DEC73 /I DEC84 /T DEC49 /1 DEC48 /0 DEC52 /4 DEC55 /7 DEC44 /,

DEC 32 / DEC70 /F DEC73 /I DEC84 /T DEC49 /1 DEC48 /0 DEC52 /4

8

DEC53 /5 DEC 0

FIT2100, DEC 70 / F DEC73 /I DEC84 /T DEC49 /1 DEC48 /0 DEC52 /4 DEC55 /7

DEC 0

Now that we have the actual data in memory, what is missing is an index, i.e., a way of finding the right information when the user queries the database. The index is repre- sented as a “list” of strings and addresses:

IdxAddr, ADR Idx Idx, DEC70/F DEC73 /I DEC84 /T DEC50 /2 DEC48 /0 DEC57 /9 DEC51 /3

DEC 0
ADR FIT2093 DEC70 /F DEC73 /I DEC84 /T DEC50 /2 DEC49 /1 DEC48 /0 DEC48 /0 DEC 0
ADR FIT2100 DEC 0

/ End of the index

The index starts at address Idx, with the string FIT2093 (including final 0), followed by the address where the prerequisites for FIT2093 are stored (ADR FIT2093). Then we have the next index entry, which is the string FIT2100 followed by the address where the data for FIT2100 is stored. Finally, the end of the index is marked by a 0.

The assignment template contains a database with a few extra entries.

9

2.5.2 Finding an entry (12 points)

You will now write a subroutine FindEntry that finds an entry in the index and outputs the corresponding data. The argument to the subroutine is the address of the string to look up, passed using the label FindEntryString.

Subroutine (10 points) The subroutine should work as follows:

1. Introduce a label CurrentEntry, and load the address of the first index entry into

   CurrentEntry.

2. If the current entry contains an empty string (i.e., there is a 0 stored at that entry, as for the End of index marker above), your subroutine should output ”not found” and then return.
3. Otherwise, compare the string in the current entry to the query string using the CmpString subroutine.
   1. a)  If the strings are equal, load the address of the data (which is stored at the address after the index string), output the data using the PrintString subroutine and return.
   2. b)  If they are not equal, skip to the next index entry by searching for the 0 that marks the end of the current string and skip the next address (which contains the address of the prerequisites), and continue with step 2.

Test cases (2 points) You need to add your search subroutine into the assignment template. Your search subroutine must use your comparison subroutine from 2.4. The template already contains one test case. You need to add two more test cases as follows:

1. A test case that finds the first entry in the database 2. A test case that finds the last entry in the database

2.5.3 Cleaning up user input (15 points)

The code above now works if the user enters the unit code exactly as it is stored in the database. We want to make the system more flexible by automatically stripping white space, converting the user’s input into upper case, and adding the letters FIT if necessary. E.g., if the user enters “ Fit2100” or “2100” they should still get the correct answer.

10

Subroutine (12 points) Write a subroutine CleanInput that takes the address of a string as input using label CleanInputString and modifies the string in three steps:

1. Trim white space using the subroutine developed earlier. (1 point)
2. Convert all characters into upper case (and leave other characters such as numbers unchanged). (5 points)
3. If the string starts with a number, your subroutine will add the characters “FIT” to the beginning of the string. (6 points)

Hint: to convert an ASCII character from lower case to upper case, you just have to subtract a fixed number from the integer that encodes the ASCII character. For example, “A” has ASCII code 65, and “a” has code 97, so subtracting 32 from a lower case character converts it into upper case.

Test cases (3 points) You need to add your flexible input subroutine into the assign- ment template. The template already contains one test case. You need to add three more test cases as follows:

1. A test case that does not require any changes (i.e., all characters are already upper case)
2. A test case that contains some lower case and some upper case characters
3. A test case that starts with a number (i.e., your subroutine should add the “FIT”)

2.5.4 Putting everything together

The template contains a section (commented out, at the very start) that calls all your subroutines in the right order to implement a simple application. When you run that code, it will

1. Ask the user to input a unit they want to look up
2. Clean up the user input
3. Look up the prerequisites in the database and print them if found 4. Go back to step 1

11