Starting from:
$30
COMP273- Assignment 2 Solved
Hand in your solutions using mycourses, following the instructions at the end of this assignment, on page 3. Before starting create a folder on your computer system and call it answer-folder. For Questions 1 and 2, use the provided templates, .circ and asm (text) files as a starting point. You must be sure that the solution you provide for Q1 runs in logismevolution. As well, you must make sure that the solutions you provide for Q2 and Q3 run in MARS. For Q1 we also ask that you explain your circuit design in words, in a separate electronic file. For Q2 and Q3 your explanations should be in the form of comments in your .asm files. Late policy: 10% off per day late, for up to 2 days. If submitted 48 hrs or more after the deadline, your assignment will not be accepted and will be scored 0!.
1 An 8-bit Shift Register (30 marks)
Design an 8-bit shift register with output bits A7A6A5A4A3A2A1A0. Each bit Ai is represented by the Q output of a rising edge triggered D Flip-flop, which is available in logisimevolution. The circuit has a clock and it also has the following two selector inputs: S0,S1. The roles of the selector inputs are described in the table below. The timing is such that a hold, shift right, shift left or circular shift right, is controlled by the clock input.
S1
S0
Function
0
0
No shift - hold
0
1
Shift right
1
0
Shift left
1
1
Circular shift right
The bit that is shifted out, i.e., when you do a shift right or a shift left, should be stored in an additional output called Bout. Correspondingly, an input bit, called Bin should be brought in to the space created by the open position, when you carry out a shift operation. A template file has been provided for you called shift.circ, which you can start with and then modify. Explain your design in words in a separate text file, which you will also upload, and then submit the circuit (shift.circ) implementation in logisim-evolution. Note that the TA’s will download and test your circuit design.
2 String Capitalization (30 marks)
You are to write a MIPS program that takes as input a string of text and then does the following.
• Prints the input string
• Capitalizes and prints the capitalized string.
You can assume that the string input is comprised of words consisting of keyboard alphabetic characters, with each word separated by a single “space” character, and with each word beginning with an alphabetical character. The program should be able to handle strings up to 127 characters in length. No characters other than lowercase letters should be modified. In other words, the input string may have some of its letters already capitalized. Use properties of the ASCII code, and in particular the manner in which characters are represented, to solve this problem!
As a working example, given the input string "this is A StrinG", the printed capitalized output should be "THIS IS A STRING". A template file capitalize.asm has been provided for you. In this file, you will note that there is an input string that is hard-coded and there is place for an output string. The TA’s might change the contents of the input string while testing your code. You should use the space allocated for the output string to write in the content of your capitalized output. Then, it should be a simple matter to print it.
3 Quadratic Congruence (40 marks)
One of the problems in the set of NP-Complete problems is that of quadratic congruences: given positive integers a, b and c, does there exist an integer x ≤ c such that x2 ≡ a mod b? For small values of a, b, and c, we can decide by brute force if the congruence can be solved. Write a program in assembly to get values for a, b and c from the user and then outputs each value of x, for which congruence holds, or reports back that there is no solution. You can use a single main program for this question; i.e., you do not have to use subroutines. However, if you use subroutines make sure that they are commented and your code is well structured. Note that you can use the rem pseudo-instruction to get the modulus of two numbers. Please name your solution file quad.asm.
An example of four test cases is given below. We will test your program with these and some other (different) test cases. Note, you can print your solutions for x in any way you like - the table below just shows the full solution set for certain choices of a,b,c.
a
b
c
Solution (x)
4
7
5
Yes (2,5)
1
5
6
Yes (1,4,6)
3
10
4
No solution
5
12
7
No solution
1 An 8-bit Shift Register (30 marks)
Design an 8-bit shift register with output bits A7A6A5A4A3A2A1A0. Each bit Ai is represented by the Q output of a rising edge triggered D Flip-flop, which is available in logisimevolution. The circuit has a clock and it also has the following two selector inputs: S0,S1. The roles of the selector inputs are described in the table below. The timing is such that a hold, shift right, shift left or circular shift right, is controlled by the clock input.
S1
S0
Function
0
0
No shift - hold
0
1
Shift right
1
0
Shift left
1
1
Circular shift right
The bit that is shifted out, i.e., when you do a shift right or a shift left, should be stored in an additional output called Bout. Correspondingly, an input bit, called Bin should be brought in to the space created by the open position, when you carry out a shift operation. A template file has been provided for you called shift.circ, which you can start with and then modify. Explain your design in words in a separate text file, which you will also upload, and then submit the circuit (shift.circ) implementation in logisim-evolution. Note that the TA’s will download and test your circuit design.
2 String Capitalization (30 marks)
You are to write a MIPS program that takes as input a string of text and then does the following.
• Prints the input string
• Capitalizes and prints the capitalized string.
You can assume that the string input is comprised of words consisting of keyboard alphabetic characters, with each word separated by a single “space” character, and with each word beginning with an alphabetical character. The program should be able to handle strings up to 127 characters in length. No characters other than lowercase letters should be modified. In other words, the input string may have some of its letters already capitalized. Use properties of the ASCII code, and in particular the manner in which characters are represented, to solve this problem!
As a working example, given the input string "this is A StrinG", the printed capitalized output should be "THIS IS A STRING". A template file capitalize.asm has been provided for you. In this file, you will note that there is an input string that is hard-coded and there is place for an output string. The TA’s might change the contents of the input string while testing your code. You should use the space allocated for the output string to write in the content of your capitalized output. Then, it should be a simple matter to print it.
3 Quadratic Congruence (40 marks)
One of the problems in the set of NP-Complete problems is that of quadratic congruences: given positive integers a, b and c, does there exist an integer x ≤ c such that x2 ≡ a mod b? For small values of a, b, and c, we can decide by brute force if the congruence can be solved. Write a program in assembly to get values for a, b and c from the user and then outputs each value of x, for which congruence holds, or reports back that there is no solution. You can use a single main program for this question; i.e., you do not have to use subroutines. However, if you use subroutines make sure that they are commented and your code is well structured. Note that you can use the rem pseudo-instruction to get the modulus of two numbers. Please name your solution file quad.asm.
An example of four test cases is given below. We will test your program with these and some other (different) test cases. Note, you can print your solutions for x in any way you like - the table below just shows the full solution set for certain choices of a,b,c.
a
b
c
Solution (x)
4
7
5
Yes (2,5)
1
5
6
Yes (1,4,6)
3
10
4
No solution
5
12
7
No solution
1 file (2.2KB)
