Homework 15 Updated Homework 15 is due on Friday December 29 at 23 59 Please submit your Homework on BlackBoard as a pdf file and follow the complete submission guidelines Homework Please ask all questions about this assignment during the office hours or post them on Campuswire LC 3 datapath and control word codes In this homework you must implement control signals for an LC 3 processor For problems 1 4 you should consider only the abbreviated list given in Section 4 1 1 p 133 of the notes The full set in Appendix C of Patt and Patel includes several aspects of LC 3 functionality that we do not discuss in our class For examples of mapping RTL to these control signals see Sections 4 1 2 and 4 1 3 1 Control signals for STI instruction Write the full set of Patel s FSM diagram to identify each state for example the first fetch state is 18 and the decode state is 32 control signals necessary to implement an STI instruction from fetch through execution Use the state numbers in datapath Patt and Make sure the datapath control signals are in the same order as the table shown below or you will lose points note please determine the number of columns needed based on the instruction not based on the figure below 2 Control signals for BR instruction Write the full set of numbers to identify the states datapath control signals necessary to implement the execution not fetch nor decode of a BR instruction Again use the state Make sure the datapath control signals are in the same order as the table shown below or you will lose points 3 Sequencing bits for STI and BR instructions For each of the FSM states in problems 1 and 2 complete processing of an STI instruction and execution of a BR instruction write the sequencing control bits J COND and IRD using the simplified version of the and Patel micro sequencer described in Appendix C 4 circuit as shown below Patt Make sure the sequencing control bits are in the same order as the table shown below or you will lose points 4 Pair codes A friend of yours is quite excited about having developed a new class of codes pair codes Pair codes are a generalization of the 2 out of 5 representation discussed in Notes Set 4 2 Lumetta s notes In a pair code each code word has exactly two 1 bits However one can define a pair code on any number of bits N For example if N 100 one has 100 bits in the code words and exactly two 1 bits Your friend points out that as N grows the fraction of valid code words drops dramatically For N 100 for example there are only 4950 valid code words 100 times 99 divided by 2 but there are 2 patterns Your friend argues that error correction capabilities for pair codes must be quite powerful since the codes are so sparse 100 bit 1 2 3 What is the Hamming distance of the pair code with 6 bit code words Use an example to prove that your answer is correct What is the Hamming distance of the pair code on 100 bit code words Explain how you can again prove that your answer is correct please avoid writing 100 bit numbers How many bits can be corrected using a pair code with N bit code words Notes Set 4 2 Lumetta s notes provided details on 7 bit Hamming codes Consider the use of Hamming codes on more bits 1 2 3 If a Hamming code is used with 10 bits how many of the bits are parity check bits If a Hamming code is used with 100 bits how many of the bits are parity check bits Why does it make little sense to use a Hamming code with 128 bits Explain your answer A communication system uses a SEC DED Single Error Correction Double Error Detection code to protect transmissions The code is based on a 7 bit Hamming code extended with an odd parity bit the most significant bit x8 Using the notation from the notes each received word consists of the parity bit followed by the 7 bit Hamming code word x7x6x5x4x3x2x1 For each of the following received words extract the 4 bit data word when possible or mention that the received word had uncorrectable errors Hint Remember that this code is able to correct single errors If you detect an error and can flip 1 bit to get to a valid codeword then you have found and fixed the error If you can t get to a valid codeword with 1 bit flip then the received word is uncorrectable because there may be more than one way to flip two bits to get to valid codewords 5 Hamming codes 6 SEC DED 1 2 3 4 5 00101101 10011110 10101001 10010001 00111001