Problem Set 3 Harvard Extension School CSCI E-93: Computer Architecture Fall 2024 Due: October 13, 2024 at Midnight ET (Eastern Time) Total of 200 Points Please submit your solution to this problem set using "git" with named branch problem-set-3. 1. (60 Points) VHDL Counter Produce VHDL code for the DE2-115 Development and Education Board using Quartus Prime Lite Edition, Release 20.1.1. Your code will reside in the EP4CE115F29C7N (DE2-115) (identified in Quartus as EP4CE115F29C7) FPGA device. Your VHDL code should implement an 8-bit counter that resets (to value zero) when pushbutton KEY3 (KEY[3]) is pressed and counts up by one each time pushbutton KEY2 (KEY[2]) is pressed. Note that the pushbuttons are active low (i.e., normally high) and are debounced in hardware. The value in the counter should be displayed in the two leftmost seven-segment LEDs (HEX7 (HEX7_D[*]) and HEX6 (HEX6_D[*])) as a hexadecimal number. Note that the LED segments are active low (i.e., the segment is illuminated when the corresponding I/O pin is driven low). As we have seen in class, sometimes the hardware-debounced pushbuttons still exhibit contact bouncing. It is often possible to remove the residual contact bouncing by pushing the pushbutton quite gently. In any case, it is *not* necessary for you add any debouncing in your VHDL code. For the DE2-115, KEY3 is connected to FPGA pin PIN_R24 and KEY2 is connected to FPGA pin PIN_N21. In the Altera DE2-115 User Manual (available from the Terasic web site and with copyright dates 2003-2013), Figure 4-10 identifies the scheme for naming the segments in each display. In the same document, Table 4-4 identifies the pin assignments for the seven-segment LEDs. Please perform your pin assignments using the attribute chip_pin method discussed in the VHDL slides. Please continue to do so for all VHDL code that you write for this class. Your counter should be designed from basic gates -- that is, do not simply use VHDL's ability to add one to an integer as a way to build a counter. For this problem set, start by implementing a full-adder entity. Use the full-adder to implement an 8-bit adder entity. Implement an entity that converts a four-bit vector into a vector for a seven-segment display. Implement an 8-bit register with asynchronous clear capability. For this problem set, use the signal from the count pushbutton (KEY2) as the clock for your register. If your register has an enable input, it can be always enabled. Use instantiations of these entities to build your top-level entity. Remember to set "Reserve all unused pins:" to "As input tri-stated" under Assignments -> Settings... -> Category: Device -> Device and Pin Options... -> Unused Pins every time you create a new project. Also, remember to check all warnings issued by the compiler and also to assign appropriate pins that are used in the project. See Altera Software Installation and Licensing Manual for Windows (http://www.altera.com/literature/manual/quartus_install.pdf) for information on how to install, configure, and use the Altera software. The drivers for connecting the DE2-115 over USB are located in the following directories: Windows: :\altera\\quartus\drivers Linux: /altera /quartus/drivers 2. (25 Points) Katz and Borriello 3.18 (Hazard-Free Design) (5 Points per subpart) Given the following specifications of Boolean functions, implement them as hazard-free circuits: (a) F(A,B,C) = B(~C) + (~A)C (b) F(A,B,C,D) = Sum-of m(0,4,5,6,7,9,11,13,14) (c) F(A,B,C) = (A + B)(~B + C) (d) F(A,B,C,D) = Product-of M(0,1,3,5,7,8,9,13,15) (e) F(A,B,C,D,E) = Sum-of m(0,1,3,4,7,11,12,15,16,17,20,28) 3. (30 Points) Katz and Borriello 5.12 (ALU Design) Implement to the gate level an ALU bit slice with three operation selection inputs, S2, S1, S0, that implements the following eight functions of the two data inputs, A and B (and carry-in Cn): S2 S1 S0 | ALU Operation ---------------------------- 0 0 0 | Fi = 0 0 0 1 | Fi = B minus A 0 1 0 | Fi = A minus B 0 1 1 | Fi = A plus B 1 0 0 | Fi = A XOR B 1 0 1 | Fi = A OR B 1 1 0 | Fi = A AND B 1 1 1 | Fi = 1 Assume a simple ripple-carry scheme between bit slices. 4. (15 Points) Katz and Borriello 7.4 (Counter Design) (5 Points per subpart) Consider the design of a 4-bit Gray-code counter (that is, only one of the state bits changes for each transition) that counts in the following sequence: 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000, and then back to 0000, 0001, 0011, etc. (a) Draw a state diagram and next-state table. (b) Implement the counter using D flip-flops. (c) Do you have to worry about self-starting? Why or why now? 5. (10 Points) Katz and Borriello 7.27 (Word Problem) A Moore machine has one input and one output. The output should be 1 if the total number of 0s received at the input is odd and the total number of 1s received is an even number greater than 0. This machine can be implemented in exactly six states. Draw a complete state diagram. Indicate what each state is meant to represent. 6. (10 Points) Katz and Borriello 8.2 (State Reduction) Given the state diagram in Figure Ex. 8.2, obtain an equivalent reduced- state diagram containing a minimum number of states. You may use row- matching or implication charts. Put your final answer in the form of a state diagram rather than a state table. Make it clear which states have been combined. You should choose a method that will yield some reduction. Please justify your choice of method. 7. (20 Points) Katz and Borriello 8.7 (State Assignment) Given the state diagram in Figure Ex. 8.7, implement a state assignment using the following techniques: (a) Minimum bit-change heuristic (b) State assignment guidelines Show your assignment in a state map. Explain the rationale for your state assignment. 8. (30 Points) Final Program in the C Programming Language Write a program in the C Programming Language to perform the following actions. Write separate procedures or functions for each of these operations: (1) input a string using character input operations, (2) convert a string to a signed integer numeric value in two's-complement representation representing the same value in decimal and checking that all characters in the string are digits with a possible preceding negative-sign (which is the same character as a dash or hyphen) -- this function should indicate if the input string cannot be successfully be represented as a signed integer numeric value, (3) take two signed integer numeric values in two's-complement representation (these are named the multiplicand and the multiplier) and multiply them to produce a signed integer numeric product in two's-complement representation (at your option, the product may be either at the same precision as the multiplicand and the multiplier or may be in twice the precision of the multiplicand and the multiplier) -- it is not necessary to detect overflow, (4) convert a signed integer numeric value in two's-complement representation to a string representing the same value in decimal (note that this value may be negative), and (5) output a string using character output operations. These functions are specified to perform the same way that the functions required for the final project perform. The minimum number you need to be able to read is -32768 and the maximum number you need to be able to read is 32767. You're welcome to accept numbers that span a larger range. The minimum precision for all signed integer numeric values must be able to represent values from -32768 to 32767, inclusively. Note that integer types in C on all modern computers use two's-complement representation; therefore, you are welcome to use "int" as the data type for your numbers. Please do *not* create arrays of bits to represent numeric values. All input characters are encoded using the ASCII character-encoding scheme. None of these functions should use any library methods to perform their computation. That is, do not use built-in calls to perform the string-to-value conversions (or vice versa); this conversion should be written from scratch. You are allowed to use library functions for input/output operations for characters, but not for either strings or for integers (i.e., fputc(c, stream), putc(c, stream), and putchar(c) are allowed for output, but fputs(s, stream), puts(s), printf("%s", s), and printf("%d", i) are *not* allowed; fgetc(stream), getc(stream), and getchar() are allowed for input, but fgets(s, n, stream), gets(s), scanf("%s", s), and scanf("%d", &i) are *not* allowed). Also, do not use the multiply operator to perform multiplication. Your algorithm for multiplication should use an efficient shifting approach. None of your code should use a multiply, divide, remainder, or modulo operator provided by the programming language. A main program should exist to call these functions so that: (1) a prompt is output asking the user to enter a value and that value is input as a string, (2) a second prompt is output asking the user to enter a second value and that value is input as a string, (3) the input strings are converted to integer numeric values and any errors are output to the user if the strings do not contain strictly decimal digits, (4) the two input values are multiplied by each other to produce a product, (5) the product is converted into a string representing that decimal value, (6) the product string is output preceded by an appropriate string describing the output. Your interaction with the main program might look like: This program multiplies two signed integers. Please enter the first number: 3 Please enter the second number: 4 The product of 3 and 4 is 12. This program multiplies two signed integers. Please enter the first number: z That input is not valid, please reenter: -3 Please enter the second number: 22 The product of -3 and 22 is -66. This program multiplies two signed integers. Please enter the first number: Function/procedure/method declarations should be: (1) Input a string using character input operations: char *getString(char *string, int stringSize); /* read one character at a time until reaching a newline. Assemble the * characters into a nul-terminated string. That is, perform an * operation similar to "char *fgets(char *s, int n, FILE *stream)". * sample typed input: "1234\n" or "-77\n" * sample output: "1234" or "-77" * * Parameters: * string pointer to a char array in memory in which the input * characters are returned as a nul-terminated string * stringSize size of the "string" char array in memory * * Return value: * identically the same pointer to the char array in * memory in which the input string is returned that * was passed in as the first parameter */ (2) Determine if a string represents a valid signed integer numeric value: int validateIntegralString(char *string); /* determines if the nul-terminated string pointed to by "string" contains * a valid ASCII signed integer value as defined in Problem Set 3 * * sample input: "1234" * sample output: 1 * * sample input: "-57" * sample output: 1 * * sample input: "1a234" * sample output: 0 * * Parameters: * string pointer to a nul-terminated char array in memory * the characters in which are to be validated as * to whether they represent an ASCII signed integer * value as defined in Problem Set 3 * * Return value: * signed int value which will be 0 (false) if the input * string pointed to by "string" is *not* a valid ASCII * signed integer value and will be 1 (true) if the input * string pointed to by "string" *is* a valid ASCII signed * integer value */ (3) Convert a string to a signed integer numeric value: int stringToInt(char *string); /* perform an operation similar to "long strtol(const char *str, * char **endptr, int base)" * sample input: "1234" * sample output: 1234 * * Parameters: * string pointer to a nul-terminated char array in memory * the ASCII characters of which are to be converted * into a signed int in two's-complement representation * * Return value: * signed int value of the initial characters in the * "string" nul-terminated string */ (4) Multiply two signed integer numeric values: int multiply(int a, int b); /* signed multiplication; don't use the multiplication operator * * Parameters: * a signed int representing the multiplicand * b signed int representing the multiplier * * Return value: * signed int value of the multiplication product */ (5) Convert a signed integer numeric value in two's-complement representation to a string representing the same value in decimal: char *intToString(int value, char *string, int stringSize); /* perform an operation similar to "int sprintf(char *s, const char *format, * ...)" with a format string of "%d" * sample input: 1234 * sample output: ['1,'2','3','4','\n'] * * Parameters: * value signed int value to be converted into an ASCII * string * string pointer to a char array in memory in which ASCII * characters representing the "value" are returned as * a nul-terminated string * stringSize size of the "string" char array in memory * * Return value: * identically the same pointer to the char array in * memory in which the ASCII string is returned that * was passed in as the first parameter */ (6) Output a string using character output operations: void putString(char *string); /* output a string to stdout. Perform an operation similar to * "int fputs(const char *s, FILE *stream)" * should call "int fputc(int c, FILE *stream)" to perform the output * * Parameters: * string pointer to a nul-terminated char array in memory * the characters of which are to be output * * Return value: * none */ Last revised 21-Oct-24