The purpose of this assignment is for you to understand the datapath and the state machine of the LC-3 processor (as presented in the Patt textbook, and Lecture and Lab). You will implement components on the LC-3 datapath and complete the microcode for multiple LC-3 machine instructions. Note: The LC-3 implementation in this assignment is simplified, and does not include all the features or components of the full LC-3 from the Patt textbook or Lecture or Lab.Please read this entire document before starting. It includes many details of the assignment, as well as tips, tricks, and references that will help you. • You will complete the microcode for many of the LC-3 machine code instructions as well as a couple of new instructions. You will enter the control signals into the microcode.xlsx spreadsheet we have provided. Instructions on how to test your microcode can be found here. IMPORTANT NOTE: While working on the assignment, be sure to review ‘Section 4.5: Tips, Tricks, and Recommendations’, ‘Section 9: Appendix: Datapath Control Signals’,‘Section 9.1: Mux Values’ for info on selector bits for different muxes, ‘Section 9.2: LC3 Reference’.1.3 Criteria Your grade on this assignment has two parts: the submission (microcode.xlsx), and a demo (demonstration of your solution and knowledge to a TA). • The submission is worth a total of 50% of your homework grade. As with prior assignments, the autograder will give you an approximation of your final grade on this portion of the assignment. • You will also demonstrate your solution, and understanding of the concepts, to one of your TAs for 50% of your homework grade. The demos will happen after the assignment is due, and we will announce details closer to that time. You are responsible for signing up for and then attending a demo slot at that time. Logistics and details of demos will be posted on Canvas before they are held.Welcome to Homework 4! In this homework, you’ll develop familiarity with the functionality of the microcontroller and components on the LC-3 Datapath that we’ve covered in class. Please read through the entire document before starting and acquaint yourself with the rules and submission policies stated in the syllabus. Often times things are elaborated on below where they are introduced, so reading the entire document can give you a better grasp on things. Start early and if you get stuck, there’s always the Ed Discussion page or come visit us in office hours.2.1 The LC-3’s Microcontroller The LC-3 datapath we’ve discussed in class contains a lot of pieces very similar to circuits we’ve seen or even made before (e.g. an ALU, a register file with 8 edge-triggered general purpose registers, a RAM unit, etc.). One piece we’ve mostly referred to as a “black-box” in the past is the microcontroller. It’s responsible for controlling the entire datapath, and getting it to properly execute the instructions that we give it. That’s a big task! So how does the microcontroller actually work? The microcontroller uses the idea of states to keep track of which datapath components to use and when. In lecture, we introduced the notion of macro-states and micro4 states. A micro-state is an individual state of the finite state machine that specifies control signals that should be asserted in a single clock cycle. The micro-states are components of a slightly larger sequence of states known as macro-states. FETCH is a macro-state, and each of the EXECUTE stages of LC-3 instructions is also a macro-state. Each of the macro-states will require between 1-5 micro-states to complete, depending on the complexity of the instruction. The microcontroller, shown above, is a finite state machine. It has 59 possible states (holy dancing crab!), and because it is implemented in the “binary reduced” style, it needs 6 bits to store all its possible states. It also has 49 output bits of output flags, including 10 which are used to determine the next state and 39 which extend throughout the datapath to control other pieces of the LC-3.That would be a lot of very complex hardware—if it were built entirely with combinational logic. It turns out there is an easier way. We can actually use a ROM(Read-only Memory) in order to specify the behavior of each distinct state in the state machine.2.2 The ROM ROM stands for Read-only Memory and as its name suggests it is a piece of memory that can only be read. Each memory address will hold an entry that represents a micro-state. This entry holds two crucial pieces of information: 1) what signals to assert on the datapath for a specific micro-state and 2) what the next state should be. With the ROM, we can hardcore this information into a binary string. We can now read from the ROM with the appropriate memory address to obtain the binary string for a specific micro-state. What does a ROM entry look like? We encourage you to go ahead and open up microcode.xlsx, on the microcode sheet, to follow along.A ROM entry is basically a long binary string. The last few bits of it cover the transition to the next state (these are essentially the address of the binary string for the next state in the ROM)—you don’t need to worry about this at all during this homework, so we’ve covered it in dark grey on the right. Do NOT modify the NEXT bits, or stuff will break. Each of the other bits corresponds to a signal asserted onto the datapath during that clock cycle. For this homework, we only require that you implement 19 of the signals asserted onto the datapath (notice that 3 of these are 2-bit signals).In this homework, you’ll actually write the “microcode” which allows the microcontroller to function. We’ve simplified and removed a number of micro-states which aren’t directly a part of the LC-3’s main instructions. There are only 36 micro-states in this homework. We’ve also given you the microcode for DECODE, BR, JSR, JSRR, and HALT (Do not change these!). Your task is to fill in the rest and finish the LC-3 microcode!2.3 Files Provided • LC3.sim – a large CircuitSim file containing the LC-3 AND a “Manual LC-3” which does not need to be modified in any way but is simply present as a tool for you while writing microcode. Once again, you do not need to modify any subcircuits in this file. • microcode.xlsx – an Excel document in which you will write your microcode. Do not touch cells that have been blacked out and do not edit the output sheet directly. • tests/ – a subdirectory which contains a number of test cases you can use to verify the functionality of your microcode. • hw4-tester.jar – a local tester you can use to verify your microcode. This tester is also available on Gradescope (where it will be a part of your grade). • LC-3InstructionsDetail.pdf – a PDF with descriptions and pseudocode for each instruction.2.4 Tasks You Must Complete 1. Complete the microcode in microcode.xlsx, in the microcode sheet. 3 Using the CircuitSim File The LC-3 datapath you will be working with for this homework, as contained in the LC3.sim file, is a complete but simpler version of the LC-3 datapth you might encounter in your textbook’s appendix C.Here are some notable differences between the two: • The instruction set used by the LC-3 in Homework 4 does not have a TRAP instruction. • In the regular LC-3, halting is handled by a trap. In Homework 4, this opcode (1111) is taken up by a single “HALT” instruction that just loops infinitely. The LC-3 in Homework 4 does not have circuitry for handling interrupts/traps/exceptions/etc. • The state machine used by the LC-3 in Homework 4 numbers its states differently from those in the book, and the microcontroller signals are a little different. The LC-3 in Homework 4 assumes that memory reads/writes take a single clock cycle like in CircuitSim, while in practice they take much longer.• The LC-3 in Homework 4 does not include I/O. You can ignore the components not present in the LC3.sim file as they appear in the textbook. We have provided you with this built LC-3 datapath for your own understanding and manual testing, but you do not need to modify anything in this file.4 Writing the Microcode 4.1 General Instructions • Use Microsoft Excel! Do not use Numbers or anything else, it will not work. Remember, you have an account for most Microsoft products via your Georgia Tech login.• In microcode.xlsx Excel document, microcode sheet, there exist a number of macro-states. Among them are FETCH and the execute stages for most instructions supported by the LC-3 (we’ve removed several macro-states related to trap and interrupt handling). For each macro-state, we’ve provided space for the micro-states which will make up that macro-state, and for each micro-state, we’ve handled all of the logic related to transitioning to the next micro-state. • You should complete all the remaining macro-states by filling in their micro-states. – If you notice that the output column to the right of the blacked-out columns (column AH) is showing artifacts like #NAME?, ensure that you have the most up-to-date version of Excel. As a last resort, try opening the Excel spreadsheet in your Georgia Tech Office 365 Online Excel workspace. Sign in to Office 365 with Georgia Tech credentials, select ‘Excel’, and then choose ‘Upload and open’ to edit the excel sheet online.4.2 Filling Out The Microcode Spreadsheet The microcontroller is the “brain” of the LC-3 and it performs operations by manipulating the control signals within the datapath. The microcode.xlsx spreadsheet is an abstraction of what the microcontroller does in each micro-state. In the microcode.xlsx spreadsheet, the rows correspond to micro-states and the columns correspond to control signals on the LC-3 datapath. What you need to do is fill in the spreadsheet based on the control signals that are set for each micro-state. You should check out the Appendix and subcircuits in LC3.sim for specifications on each control signal. For example, for the micro-state BR1, the control signals involved are: • LD.PC • PCMUX = 01 • ADDR2MUX = 10 Please read ‘Section 4.5: Tips, Tricks, and Recommendations’, before beginning to fill out the microcode. 7 4.3 LDSKIP Your fellow TAs are trying to create a few new LC-3 instructions! We’re calling the first one – LDSKIP – Load and Skip. This instruction should add the value of the PC to a 9-bit offset. Then, it should use the calculated address to load from memory into the PC. Next, the program should increment the PC. • PC
The purpose of this assignment is to practice the low-level concepts we have learned, from sequential logic to state machines in CircuitSim. Part 1 focuses on implementing sequential logic circuits like RS latches, Gated-D latches, D-Flip Flops which you will use to build a register from the ground up and eventually build a simple memory circuit as well. Part 2 focuses on using a state machine diagram and scenario to build and simplify KMaps and then build a Binary Reduced State Machine in CircuitSim. Finally, in Part 3, you will use your understanding of CircuitSim and these various circuitry concepts to build some of the key components of the Datapath.1. To understand how a register circuit works 2. To learn how to make a state machine 3. To understand K-maps and simplification 4. To see how state machines can integrate with computer processing 1.2 Task There are three parts to this assignment. 1. First, you will build sequential logic components in CircuitSim from the ground up. 2. Second, you will complete a K-Map to simplify your binary reduced state machine circuit, and implement the simplified circuit. 3. Third, you will implement parts of the datapath we have provided for you. Before you start the assignment, be sure to read the rest of the PDF for more detailed instructions and hints.1.3 Criteria You must utilize the provided CS 2110 version of CircuitSim, which is available via the JAR on Canvas. Utilizing other versions of CircuitSim is strictly prohibited and may result in damaged or corrupted files. You will submit four files to Gradescope: • latches.sim • kmap.xlsx • fsm.sim • datapath.simYour grade is based on: 1) the correct outputs from your circuits; and 2) not using any banned components. For part 2 (binary reduced state machine), you will lose points if your circuit does not correspond to your K-Map or if your circuit is not minimal. The grade you see on Gradescope may not be the final grade you receive, as we may run additional tests on your submission.You may submit your code to Gradescope as many times as you like until the deadline. We will grade your last active submission. We have also provided a local checker that you can test your code with. Please submit your code to Gradescope at least once prior to the deadline, to ensure you are not encountering any issues submitting at the last minute.Part 1: For this part, you will be building your own register and simple memory from the ground up. • Implement your circuits in the “latches.sim” file Part 2: Given the a state diagram, you will be minimizing the logic by using K-Maps. • Fill out the K-Maps located in the spreadsheet named “kmap.xlsx” • The binary reduced circuit will be implemented in the “Binary Reduced SM” subcircuit of the “fsm.sim” file Part 3: Finish connecting the datapath we have partially provided you • Connect the datapath.• The datapath will be implemented in the “Datapath” subcircuit of the “datapath.sim” file Do not change/delete any of the input/output pins. (Though you may change the actual value of the input pins) There is more to the assignment in the next pages.2.1 Part 1 For this part of the assignment you will build your own register and simple memory from the ground up. All work for this section needs to be done in the latches.sim file. 2.1.1 RS Latch You will start by building a RS latch using NAND gates, as described in your textbook. The RS Latch is the basic circuit for sequential logic. It stores one bit of information, and it has 3 important states: 1. R=1 S=1 : This is called the Quiescent State. In this state the latch is storing a value, and nothing is trying to change that value. 2. R=1 S=0 : By changing momentarily from the Quiescent State to this state, the value of the latch is changed so that it now stores a 1. 3. R=0 S=1 : By changing momentarily from the Quiescent State to this state, the value of the latch is changed so that it now stores a 0. Once you set the bit you wish to store, change back to the quiescent state to keep that value stored. Notice that the circuit has two output pins; one is the bit the latch is currently storing, and the other is the opposite of that bit. Note: In order for the RS Latch to work properly, you must not set both R and S to 0 at the same time. • Build your circuit in the “RS Latch” subcircuit in the “latches.sim” file.2.1.2 Gated D Latch Using your RS latch subcircuit, implement a Gated D Latch as described in the textbook. The Gated D Latch is made up of an RS Latch as well as two additional gates that serve as a control. With that addition not only can we control what value is stored by the latch, but also when that value will be saved.The value of the output can only be changed when Write Enable is set to 1. Notice that the Gated D Latch subcircuit only has one output pin, so you should disregard the inverse output of your RS Latch. • Implement this circuit in the “Gated D Latch” subcircuit in the “latches.sim” file. • You should use your previous RS latch subcircuit.2.1.3 D Flip-Flop Using the Gated D Latch circuit you built, create a D flip-flop. A leader-follower D flip-flop is composed of two Gated D latches back to back, and it implements edge triggered logic. Your D flip-flop output should be able to change on the rising edge, which means that the state of the D Flip-Flop should only be able to change at the exact instant the clock goes from 0 to 1. • Implement this circuit in the “D Flip-Flop” subcircuit in the “latches.sim” file. • You should use your previous Gated D latch subcircuit. 2.1.4 Register Using the D Flip-Flop you just created, build a 4-bit Register. Your register should also use edge-triggered logic. The value of the register should change on the rising edge. 7 • This circuit will be implemented in the “Register” subcircuit in the “latches.sim” file. • You should use your previous D flip-flop subcircuit.2.1.5 Memory Using the Gated D Latches you just created, build a 4×1 memory where your memory has 4 addresses/rows which store 1-bit of data each. Your memory should use level-triggered logic. Take a look at the following (blackbox) memory visual….In the provided circuit you have the following components • ‘Address Selector’ or (‘Selector’ in circuit) – a 2-bit input and determines which row of memory we select. – When ‘Address Selector’ is 00, we select the top most row. – When ‘Address Selector’ is 01, we select the second row. – When ‘Address Selector’ is 10, we select the third row. – When ‘Address Selector’ is 11, we select the fourth row. • ‘Enable’ – decides whether you want to write into memory or not. NOTE:• You can write/save into a particular row if the ‘enable’ is ON and that row is selected by the ‘Address Selector’. • Each row can contain 1-bit data. • The ‘Address Selector’ also determines which row’s output is displayed.2.2 Part 2 2.2.1 Scenario Meet Pablo, your soon to be favorite canine companion. With a fur coat softer than snow and a tail that can’t stop wagging, he’s a dog that can cheer you up at any time. Whether he’s playing fetch or barking away at a squirrel, Pablo is proof that life is better with a furry friend by your side. A quick observation of Pablo reveals that he primarily exists in four possible states: a Sleep state, an Eat state, a Play state, and a Walk state! At each of these states, he can be seen exhibiting some combination of two behaviors: tail wagging and barking – this is the state’s output.Pablo begins in the Sleep state. After getting enough rest, he can choose to proceed to the Eat state if he’s hungry, or the Play state. From the Play state, Pablo can either stay at the Play state or, if he’s had his fill of playing, can continue to the Eat state. After eating, he can go for a walk or cycle back to the Play state. Following his time in the Walk state, Pablo will be too tired for any more activity and unconditionally return to the Sleep state.2.2.2 Binary Reduced State Machine Diagram The state machine transition diagram below lays out this scenario in full:2.2.3 Quick review of Binary Reduced State Machines! Each state corresponds with a binary number in a binary reduced state machine. The binary number represents the state number as a decimal translation. What does this mean? In a binary reduced state machine, we convert the binary number into a decimal number to find the state number. So 00 = state 0 and 11 = state 3. Each state contains a transition to the next state based on an input M. M represents M=1, while M’ represents M=0. A transition on M means you move from a specified state to the state the transition points to when the M input is set to 1. The outputs are dependent on the current state. • State 00 refers to the Sleep State • State 01 refers to the Eat State • State 10 refers to the Play State • State 11 refers to the Walk State2.2.4 KMAPS • First, produce the K-maps for the state transition diagram above on the provided spreadsheet named kmap.xlsx. Use the K-maps to produce the reduced Boolean expressions for the state machine. The inputs for each K-map are: – S0 = Current state least significant bit – S1 = Current state most significant bit – M = Input bit The outputs to make K-maps for are: – N0 = Next State least significant bit – N1 = Next State most significant bit – T = Tail Wagging – B = BarkingPlease Note: This State Machine is a Moore State Machine, meaning that the output values are determined solely by the current state (you should not use the N1 and N0 outputs or the M input for determining the values for Tail Wagging (T), Barking (B)).– You will fill out one K-map per output and one per next state bit for a total of 4 K-maps (T, B, N0, N1). The respective K-maps are located in the kmap.xlsx file. – Your K-map must give the best solution of groupings possible to receive full credit. This means you must select the optimal values for any don’t cares (if applicable) in your K-maps to do this. – It may be helpful to check with others on Ed Discussion to see if your circuit is optimal. In order to do this without giving away your answer you may share the number of AND and OR gates used. The final total number is enough. Try not to give away how many gates you used for each step, as it could give away how your K-maps are done.– IMPORTANT: The K-maps will be autograded. Because of this, there are a set of restrictions to how you must fill your K-maps to ensure you get full credit: ∗ When you fill the row and column headers for your K-maps, you may only use the following variable names: S0, S1, and M. To negate a variable, you must use an apostrophe. Two adjacent variables with nothing in between are interpreted as an AND. Example label: S0’M∗ When writing the Boolean expressions resulted from your K-map groupings, you must use the same rules as the previous bullet point, but also use ”+” for OR (no spaces). Example grouping: For the Boolean expression (NOT S0) OR (S1 AND M), write S0’+S1M ∗ When filling in the cells of your K-map table, you must use 0, 1, and X.2.2.5 Binary Reduced Dog • Implement this circuit in the “Binary Reduced SM” subcircuit of the provided fsm.sim file. You will lose points if your circuit does not correspond to your K-map or if your circuit is not minimal. You should use only the minimal components possible to implement the state machine. • HINT: We recommend you make a truth table for the state machine to help organize the logic, and then transfer your answers to the K-maps. We’ve provided truthtable.xlsx to help with this. Note: You are not required to complete truthtable.xlsx or submit it anywhere; it is only provided for convenience when making your K-maps.2.3 Part 3 For this part of the assignment you will be completing parts of a processor datapath. A datapath is essentially a collection of components that can perform operations. By turning on and off certain inputs of the datapath, your datapath (upon completion) will be able to process instructions. You can use the provided microcontroller that uses the datapath to handle the instructions (apart from changing the clock).Please Note: Much of the terminology in this section of the PDF has been heavily simplified to provide a basic overview that will allow you to create the datapath without an intricate understanding of computer processing.2.3.1 What is an instruction? Above is an example of an instruction. • The arrow points to the “Opcode” (operation code). This defines what the operation is. For this datapath, we have simplified the Opcode to the left most bit (bit 7) for a possibility 2 operations. These operations will be either an AND or ADD operation. An AND operation will occur when the Opcode is a 0. An ADD operation will occur when the Opcode is a 1.• The rest of the bits represent the “Operand”, which represents the parameters of our instruction. This has also been simplified to a single value represented by 7 bits (bits 0-6). This will be the value that will be ADDed or ANDed with the value currently in the Datapath (This will be held in the general purpose register, but more on this later). The value can be determined simply by reading the 6 bits as an unsigned binary number.• With this information, we can now decipher the above example. The 1 for the Opcode (the leftmost bit) tells us that this is an ADD instruction. Reading the Operand (bits 0-6) as an unsigned binary number tells us the value is 19. Therefore, putting the two together completes our instruction as ADD 19. When executing this instruction, it will take the value of 19 and adds it to our current value.2.3.2 Components of the Datapath • The register labeled ‘PC’ is a simplified version of a “Program Counter”. The Program Counter stores a value (referred to as the “address”) corresponding to the next instruction. For this datapath, the PC register will store a possible 4 addresses represented in two digit binary: 00, 01, 10, 11. Furthermore, these values correspond to the 4 possible instructions in the INPUTS & OUTPUTS section: 00 to INSTR0, 01 to INSTR1, 10 to INSTR2, 11 to INSTR3. Therefore, say the value of the PC is 10 in binary, then the current instruction being processed by the datapath would be INSTR1, since INSTR1 corresponds to the address 01, and the PC holds the address of the next instruction. Note: When no instructions are being processed by the datapath (before beginning any clock cycles) the value of the PC will be 00. This should makes sense because the next instruction to be processed would be instruction INSTR0. • The register labeled ‘IR’ refers to the “Instruction Register”. This register will store the value of the current instruction that we are executing. So when the INSTR1 instruction is being processed, the IR will display the value of that whole instruction. Because we are considering the whole instruction, the IR should not differentiate between the Opcode or Operand, rather it should treat the bits as one 8-bit value.• The register labeled ‘REG’ is our general-purpose register. This register will hold the result of the operations we run. This register will allow you to observe whether your instructions are being processed by the datapath as intended. Remember that instructions will be applied to the value currently in the register. This means that if the current value in REG is a 5, and our next instruction is ADD 10, then REG should display a value of 15 when the instruction is finished executing.• The component labeled ALU is similar to the one you implemented in HW02. This will handle the actual calculation of the instruction. The input “ALUK” (short for ALU Control) will determine which calculation will occur. As stated before, when the Opcode of an instruction is a 0, the operation should be an AND operation. If the Opcode is 1, the operation should be an ADD operation. Remember that instructions will be applied to the value currently in REG. This should help in deciding which inputs should be sent into the ALU when operations should occur. • The section labeled as Microcontroller is what actually will be controlling this datapath. The display on the datapath circuit may seem complex, but it is quite simply a Finite State Machine (You implemented a binary-encoded state machine for part 2). We have added more to the Microcontroller component to allow students to manually test their datapath. Upon completion, the Microcontroller will have the datapath cycle through different states, turning inputs on and off, allowing instructions to be interpreted and executed autonomously (apart from controlling the clock). Please Note: Values displayed on registers are in hex not binary.2.3.3 What do I need to do? The datapath provided is not complete. Your job is to determine how to connect the datapath so that instructions can be properly processed. This will include setting up the datapath to be able to “Fetch”, “Decode”, and “Execute” instructions, as well as setting up the control signals (the outputs of the microcontroller) to align with each step.Fetch In order to actually execute an instruction, we must first “Fetch” the instruction and store it in our IR. To be able to fetch an instruction, our datapath must be able to do the following: 1. When LD.IR = 1 on a rising clock edge, use the value in the PC to load the correct instruction to the IR. For example, if PC = 01, we should load inst1 into the IR. This is the actual “fetching” of the instruction.2. When PCINC = 1 on a rising clock edge, we should increment the value of the PC. This is so that we can get the next instruction the next time we fetch (instead of the same one over and over again). Quick hints to Fetch: • A tunnel labeled PC is currently attached to a MUX with tunnels to our four instructions. What value should we assign to this tunnel to retrieve the correct instruction? (No, it’s not a trick question.) • What component can you use to increment the value of a number? Hint: incrementing is just addition. Decode Once we have “Fetched” our instruction and stored it in our IR, we must “Decode” our instruction. This essentially means to determine what the instruction will be doing, so we may prepare our datapath accordingly.To do this we must: 1. Take the value in the IR, and set the values of the Opcode and Operand accordingly. 2. That is all! No control signals need to be set as decode simply sets up the Datapath for the following states. Quick hints to Decode: • Which bits of the instruction tells us the operation occurring? This is the opcode. • Which bits of the instruction tells us what is the value being used in the operation? This is the operand. Execute Once we have “Decoded” our instruction, we need to actually “Execute” this instruction for anything to actually happen. In this simplified datapath, this will mean either executing an AND operation or ADD operation and appropriately update the value of “REG”. For this to work: 1. Send the inputs of the operation to the ALU, remember that operations will be applied to the value currently in the REG. 2. Connect ALUK to the appropriate location. Remember that ALUK stands for “ALU control” and is used to determine the operation performed by the ALU. Remember, when the Opcode is a 0, the instruction should perform an AND operation. When the Opcode is a 1, the instruction should perform an ADD operation. 3. When LD.REG = 1 on a rising clock edge, we should set REG to be equal to the resulting value from the ALU.Quick hints to Execute: • What values will be used as the inputs of our operation? • What component of our datapath can perform these operations? • What can we use to determine the operation being performed? 14 2.3.4 How do we actually execute an instruction?NOTE: You should only use the state machine for your datapath once you have a completed datapath to test. When you believe you have set up Fetch, Decode, and Execute properly. We can now test our datapath by actually executing some instructions. 1. Set up some instructions. Change the values of the instructions, so that you can see how the datapath processes them. Remember how instructions are set up. Keep in mind: It is probably a good idea to decide what values should be displayed throughout the processing, so you can verify your datapath is working correctly. 2. You can test your inputs by seting the CONTROL MODE input to 0. This will make the datapath rely on the provided state machine circuit which will set the control signals for you. You can then click the clock and the state machine will process your instructions. 3. You can use “Manual” inputs to control your datapath. To enter manual mode, set the CONTROL MODE input to 1. The datapath will now rely on inputs (control signals) you select to control instruction processing. You can now manually Fetch, Decode, and Execute (in this order) to process the instruction: (a) Fetch: On a rising clock edge, set LD.IR = 1 and PCINC = 1. Remember, setting LD.IR = 1 should load one of the four instructions into the IR depending on the current PC value. Setting PCINC = 1 should increment the value of the PC. (b) Decode: Nothing needs to be done here. Again, this step is here to set up the actions of the future states. (c) Execute: On a rising clock edge, set LD.REG = 1, and if an ADD operation should occur, set ALUK = 1. Remember, this should insert the result of the ALU operation into REG. 4. If Fetch, Decode, and Execute are working properly (and your state machine if you are using one), you should be able to see the appropriate values across the registers and outputs.2.4 Moving and Reorienting Components Please make sure to follow the text that says to not delete anything that’s already provided, change the general orientation of components, and change the general direction of components. Doing any of the above would result in the provided “Microcontroller (One Hot)”, “Microcontroller” subcircuit (that are already built) to be connected improperly and cause short circuits. Make sure to not change the orientation or layout of the input or output pins. Basically, please don’t mess with the provided circuits (i.e. “Microcontroller (One Hot)”, “Microcontroller”, “ALU”) or you might get errors.3 Testing To test your circuits locally, navigate to the directory with the files for this homework and run the tester JAR file with java -jar hw03-tester.jar Note 1: The local autograder does not check kmap.xlsx. It checks all of the other files. In order to ensure that your answers in kmap.xlsx are correct, please submit on Gradescope. Note 2: There are some errors that may inexplicably occur in the process of running the local autograder (e.g., Error creating subcircuit for circuit ‘…’). If any of these errors prevent the tests from running, try running the autograder again until the tests run. 4 Deliverables Submit the following files to the “Homework 3: State Machines” assignment on Gradescope: • latches.sim • fsm.sim • kmap.xlsx • datapath.sim Note: The autograder may not reflect your final grade on the assignment. We reserve the right to run additional tests during grading.5 Rules and Regulations 1. Please read the assignment in its entirety before asking questions. 2. Please start assignments early, and ask for help early. Do not email us the night the assignment is due with questions. 3. If you find any problems with the assignment, please report them to the TA team. Announcements will be posted if the assignment changes. 4. You are responsible for turning in assignments on time. This includes allowing for unforeseen circumstances. If you have an emergency please reach out to your instructor and the head TAs IN ADVANCE of the due date with documentation (i.e. note from the dean, doctor’s note, etc). 5. You are responsible for ensuring that what you turned in is what you meant to turn in. No excuses if you submit the wrong files, what you turn in is what we grade. In addition, your assignment must be turned in via Gradescope. Email submissions will not be accepted. 6. See the syllabus for information regarding late submissions; any penalties associated with unexcused late submissions are non-negotiable. 7. We reserve the right to add more test cases to the auto grader. Full credit is awarded for wholly correct implementations.
You have learned about digital logic, including transistors, gates, and combinational logic. Gates (AND, OR, etc.) can be built using transistors, and combinational logic circuits (decoder, multiplexers, ALUs etc.) can be built using gates. Note how the concepts build up from transistors to gates to combinational logic. We have provided you with a tool called CircuitSim that allows you to simulate building circuits, without actually using physical hardware. The purpose of this assignment is for you to become proficient building gates and combinational logic circuits.You will complete four CircuitSim files, and build an ALU (arithmetic logic unit) from the ground up. Please read this entire document for detailed instructions, including which digital logic components you are allowed to use or prohibited from using for each part of the assignment. This document also contains tutorials on using CircuitSim. The steps to complete this assignment are: 1. Create the standard logic gates (NAND, NOR, NOT, AND, OR) 2. Apply DeMorgan’s Law to convert a provided circuit to one without any OR Gates 3. Create an 8-input multiplexer and an 8-output decoder 4. Use multiplexers to create a circuit that evaluates the sign of a number 5. Create a 1-bit full adder 6. Create an 8-bit full adder using the 1-bit full adder 7. Use your 8-bit full adder and other components to construct an 8-bit ALU1.3 Criteria You must use the provided CS 2110 version of CircuitSim, which is available via the JAR on Canvas. Other versions of CircuitSim are incompatible with our autograders. You will submit four CircuitSim files that you produce to Gradescope: gates.sim, demorgan.sim, plexers.sim, and alu.sim. Your circuits must work properly and produce the desired results in order to receive credit. For the ALU portion, partial credit is awarded for each operation that works properly. Be sure to avoid using components that are disallowed for each phase of this assignment.2 Optional Tutorial Note: This tutorial is optional and to help you get acquainted with CircuitSim before you start this homework. If you’re comfortable with this software, feel free to skip ahead. CircuitSim is an interactive circuit simulation package. We will be using this program for the next couple of homework assignments. This is a tutorial to help you get acquainted with the software. CircuitSim is a powerful simulation tool designed for educational use. This gives it the advantage of being a little more forgiving than some of the more commercial simulators. However, it still requires some time and effort to be able to use the program efficiently. With this in mind, we present you with the following assignment: 2.1 Part 1 — Read Resources Read through the following resources • CircuitSim Wires Documentation https://ra4king.github.io/CircuitSim/docs/wires/ • Tutorial 1: My First Circuit https://ra4king.github.io/CircuitSim/tutorial/tut-1-beginner 2.2 Part 2 — Complete Tutorial 2 Complete Tutorial 2 https://ra4king.github.io/CircuitSim/tutorial/tut-2-xor Instead of saving your file as xor.sim, save your file as part1.sim. As well, make sure you label your two inputs a and b, and your output as c, as well as rename your subcircuit to xor.2.3 Part 3 — Complete Tutorial 3 Complete Tutorial 3 https://ra4king.github.io/CircuitSim/tutorial/tut-3-tunnels-splitters Name the subcircuit umbrella, the input in, and the output out. Save your file as part2.sim.3.1 1-Bit Logic Gates Allowed Components: Wiring Tab and Circuits Tab All of the circuits in this file are in the gates.sim file. For this part of the assignment, you will create a transistor-level implementation of the NOT, NAND, NOR, AND, and OR logic gates.For this section you are only allowed to use components listed in the Wiring section and circuits you have already implemented. For example, once you implement the NOT gate you are free to use that subcircuit in implementing other logic gates. Implementing the gates in the order listed below will be easiest. As a brief summary of the behavior of each logic gate: NOT (Input: IN – Output: OUT) A NOT A 0 1 1 0 NAND (Inputs: A, B – Output: OUT) A B A NAND B 0 0 1 0 1 1 1 0 1 1 1 0 NOR (Inputs: A, B – Output: OUT) A B A NOR B 0 0 1 0 1 0 1 0 0 1 1 0 AND (Inputs: A, B – Output: OUT) A B A AND B 0 0 0 0 1 0 1 0 0 1 1 1 OR (Inputs: A, B – Output: OUT) A B A OR B 0 0 0 0 1 1 1 0 1 1 1 1 All of the logic gates must be within their named sub-circuits.3.2 DeMorgan’s Law Allowed Components: Wiring Tab, NOT Gate, 9 OR Gates, and 1 NAND Gate The circuits in this file are in the demorgan.sim file. De Morgan’s laws help relate conjunctions (AND) and disjunctions (OR) of propositions with negation. In this file, you will be creating a circuit that is an alternative to the circuit that is provided in the Provided subcircuit (first tab). Your work will be done in the Student subcircuit (second tab).3.2.1 Provided Nothing needs to be done in this subcircuit! You may find it helpful to test some inputs and build a truth table. 3.2.2 Student This circuit needs to be directly equivalent to the circuit provided in the Provided subcircuit, meaning the same inputs should lead to the same outputs. Here’s the catch: you must to rebuild this circuit with exactly 9 OR gates, 1 NAND gate, and no other gates! You may use NOT gates / bubbles on the inputs of gates freely.3.3 Plexers All of the circuits in this file are in the plexers.sim file. 3.3.1 Decoder Allowed Components: Wiring Tab, Circuits Tab, and Gates Tab The decoder you will be creating has a single 3-bit selection input (SEL), and eight 1-bit outputs (labeled A, B, C, …, H). The decoder uses the SEL input to raise a specific output line, as seen below. For example: SEL = 000 ==> A = 1, BCDEFGH = 0 SEL = 001 ==> B = 1, ACDEFGH = 0 SEL = 010 ==> C = 1, ABDEFGH = 0 SEL = 011 ==> D = 1, ABCEFGH = 0 SEL = 100 ==> E = 1, ABCDFGH = 0 SEL = 101 ==> F = 1, ABCDEGH = 0 SEL = 110 ==> G = 1, ABCDEFH = 0 SEL = 111 ==> H = 1, ABCDEFG = 0 3.3.2 Multiplexer Allowed Components: Wiring Tab, Circuits Tab, and Gates Tab The multiplexer you will be creating has 8 1-bit inputs (labeled appropriately as A, B, C, …, H), a single 3-bit selection input (SEL), and one 1-bit output (OUT). The multiplexer uses the SEL input to choose a specific input line for forwarding to the output. For example: SEL = 000 ==> OUT = A SEL = 001 ==> OUT = B 7 SEL = 010 ==> OUT = C SEL = 011 ==> OUT = D SEL = 100 ==> OUT = E SEL = 101 ==> OUT = F SEL = 110 ==> OUT = G SEL = 111 ==> OUT = H3.3.3 Sign Evaluation Allowed Components: Wiring Tab, Circuits Tab, Gates Tab, and Plexer Tab In this step, you will construct a circuit that takes an 8-bit two’s complement input and evaluates whether the input is negative, zero, or positive. Based on this, this circuit will output a 3-bit bit-vector called NZP where the most significant bit is 1 iff the input is negative, the middle bit is 1 iff the input is zero, and the least significant bit is 1 iff the input is positive. Only 1 bit of the output should be set at any given time. Zero is not considered a positive number.For example: INPUT = 10111000 ==> NZP = 100 INPUT = 00000000 ==> NZP = 010 INPUT = 00000100 ==> NZP = 001 Note that you may use the plexer tab for this circuit. Hint: Recall that in two’s complement, the most significant bit can be used to determine the sign of a number!3.4 Adders & ALUs All of the circuits in this file are in the alu.sim file. 3.4.1 1-Bit Adder Allowed Components: Wiring Tab, Circuits Tab, and Gates Tab The full adder has three 1-bit inputs (A, B, and CIN), and two 1-bit outputs (SUM and COUT). The full adder adds A + B + CIN and places the sum in SUM and the carry-out in COUT. For example: A = 0, B = 1, CIN = 0 ==> SUM = 1, COUT = 0 A = 1, B = 0, CIN = 1 ==> SUM = 0, COUT = 1 A = 1, B = 1, CIN = 1 ==> SUM = 1, COUT = 1 Hint: Making a truth table of the inputs will help you.3.4.2 8-Bit Adder Allowed Components: Wiring Tab, Circuits Tab, and Gates Tab For this part of the assignment, you will daisy-chain 8 of your 1-bit full adders together in order to make an 8-bit full adder. This circuit should have two 8-bit inputs (A and B) for the numbers you’re adding, and one 1-bit input for CIN. The reason for the CIN has to do with using the adder for purposes other than adding the two inputs. There should be one 8-bit output for SUM and one 1-bit output for COUT.3.4.3 Basic 8-Bit ALU Allowed Components: Wiring Tab, Circuits Tab, Gates Tab, and Plexer Tab You will first create a simple 8-bit ALU, using the 8-bit full adder you created previously. For this ALU, we will be using a multiplexer. This ALU has two 8-bit inputs for A and B and one 2-bit input for OP, the op-code for the operation in the list below. It has one 8-bit output named OUT. The following 4 operations will be selected from: 00. Addition [A + B] 01. AND [A & B] 10. NOT [NOT A] 11. Pass [PASS A]The Pass operation simply refers to outputting the value of A unchanged. Notice that NOT and Pass only operate on the A input. They should NOT rely on B being a particular value. The provided autograder will check the op-codes according to the order listed above (Addition (00), AND (01), etc.) and thus it is important that the operations are in this exact order.3.4.4 Intermediate 8-Bit ALU Allowed Components: Wiring Tab, Circuits Tab, Gates Tab, and Plexer Tab You will next create a different 8-bit ALU, with identical structure as the previous, but more complex operations as outlined below. Make sure to match the OP 00. isPalindrome [A == reverse(A)] 01. isDivisibleBy32 [A % 32 == 0] 10. inBetween[8, 64) [A is in the range of [8, 64)] 11. maximum(-15 * A, B) [max(-15 * A, B)]For circuits isPalindrome, isDivisibleBy32, and inBetween[8, 64) operations, return 00000001 if the condition is true, and 00000000 otherwise. The autograder will check the op-codes according to the order listed above and thus it is important that the operations are in this exact order. 10 3.5 Running the Autograder To run the autograder locally, type the following command into your terminal while in the Homework 2 directory: java -jar hw02-tester.jar Make sure all the tests have been passed. Keep in mind that even if you get full credit from the autograder, we reserve the right to test for more cases.4 Disclaimers The following are trivial things that may lead to errors on the autograder, even though your circuit is technically correct. 1. Renaming or removing input pins may cause issues with the autograder because it’s looking for input pins with a specific label. 2. You must use constant pins when necessary. Using any input pins for a scenario where a fixed constant value is required will lead to the autograder setting the input pin to 0 and thus cause issues for scenarios where it needed to be a constant 1. Never add/remove input or output pins. All necessary input and output pins have been provided for you.5 Deliverables Please upload the following files onto the assignment on Gradescope: 1. gates.sim NOT, NAND, NOR, AND, OR 2. demorgan.sim Provided, Student 3. plexers.sim Decoder, MUX, Sign Evaluation 4. alu.sim 1-Bit Adder, 8-Bit Adder, Basic ALU, Intermediate ALU 6 Sub-Circuit TutorialAs you build circuits that are more and more sophisticated, you will want to build smaller circuits that you can use multiple times within larger circuits. Sub-circuits behave like classes in Object-Oriented languages. Any changes made in the design of a sub-circuit are automatically reflected wherever it is used. The direction of the IO pins in the sub-circuit correspond to their locations on the representation of the sub-circuit.To create a sub-circuit: 1. Go to the “Circuits” menu and choose “New circuit” 11 2. Name your circuit by right-clicking on the “New circuit” item and selecting “Rename” To use a sub-circuit: 1. Click the “Circuits” tab next to the “Misc” tab 2. Select the circuit you wish to use and place it in your design7 Rules and Regulations 1. Please read the assignment in its entirety before asking questions. 2. Please start assignments early, and ask for help early. Do not email us the night the assignment is due with questions. 3. If you find any problems with the assignment, please report them to the TA team. Announcements will be posted if the assignment changes. 4. You are responsible for turning in assignments on time. This includes allowing for unforeseen circumstances. If you have an emergency please reach out to your instructor and the head TAs IN ADVANCE of the due date with documentation (i.e. note from the dean, doctor’s note, etc). 5. You are responsible for ensuring that what you turned in is what you meant to turn in. No excuses if you submit the wrong files, what you turn in is what we grade. In addition, your assignment must be turned in via Gradescope. Email submissions will not be accepted. 6. See the syllabus for information regarding late submissions; any penalties associated with unexcused late submissions are non-negotiable. 7.1 Academic Misconduct Academic misconduct is taken very seriously in this class. Quizzes, timed labs and the final examination are individual work. Homework assignments will be examined using cheat detection programs to find evidence of unauthorized collaboration. You are expressly forbidden to supply a copy of your homework to another student. If you supply a copy of your homework to another student and they are charged with copying, you will also be charged. This includes storing your code on any platform which would allow other parties to it (public repositories, pastebin, etc). If you would like to use version control, use a private repository on github.gatech.edu Homework collaboration is limited to high-level collaboration. Each individual programming assignment should be coded by you. You may work with others, but each student should be turning in their own version of the assignment.High-level collaboration means that you may discuss design points and concepts relevant to the homework with your peers, share algorithms and pseudo-code, as well as help each other debug code. What you shouldn’t be doing, however, is pair programming where you collaborate with each other on a single instance of the code, or providing other students any part of your code.
The goal of this assignment is for you to understand bitwise operators, and how to use them to manipulate data (including integers and ASCII codes for characters) programmatically. For this assignment you will be programming in Java, because you should already be familiar with it. The concepts of bitwise operations that you apply here will be used throughout the remainder of this course, including in machine language, assembly language, and C programs.You will complete the Java methods in the provided files: BitVector.java, Bases.java, and Operations.java. The comments in the provided code files describe what each method should accomplish. The restrictions on which operators you are allowed to use may change between files and sometimes within methods of the same file, so it is in your best interest to read each comment carefully. Before you start this assignment, please read the rest of this document for more detailed instructions and hints. 1.3 Criteria Your coding grade is based on: 1) the correct output from your methods; 2) not using any banned operators; and 3) not hardcoding a literal result from a method, or any other such workaround. The grade you see on Gradescope is the grade you receive, unless we find that you’ve hardcoded return values.You may submit your code to Gradescope as many times as you like until the deadline. We will only grade your last submission. We have also provided a local autograder that you can test your code with. Submit to Gradescope early and often, to help ensure that you do not encounter issues submitting at the last minute.1. Make sure all 4 files are in the same folder: (a) BitVector.java (b) Bases.java (c) Operations.java (d) hw1checker.jar Note: An Examples.java file is also included which shows and explains examples of two methods similar to those used in your assignment. This is just provided for reference, so there are no tasks to be completed within it.2. Complete all of the methods in the three java files, in the order that they appear above. Run the autograder and verifier (instructions below) frequently to avoid errors and to ensure that you are only using the allowed operations. If you get stuck, a helpful file to check out is Examples.java. It has detailed explanations for how to complete similar methods. 2 3 How to run the auto-grader & verifier 1. Make sure that the hw1checker.jar file is in the same folder as your BitVector.java, Bases.java, and Operations.java files. 2. Navigate to this folder in your command line. 3. Run the desired command (see below).3.1 Commands 1. Test all methods and verify that no banned operations are being used (checks all 3 files): java -jar hw1checker.jar Note: Your grade will be dependent on the output of the above command, as it will both test the output of your methods, and verify that you are not using banned operations. If you get stuck though, you can use some of the below commands to help you debug. On Windows and Mac, you can also double click the hw1checker.jar in your file explorer to test and verify all 3 files. The results will be placed in a new file called gradeLog.txt. Any errors with compilation, infinite loops, or other runtime errors will be placed in a new file called errorLog.txt.2. Test & verify all methods in a single file. Useful for when you just want to look at one file at a time. For example, using Bases.java: java -jar hw1checker.jar -g Bases.java 3. Test all methods in a single file without running verifier. This means that this will only run the unit tests, and will not check for the use of banned operations. Useful for when you just want to try and get something that works. For example, using Bases.java: java -jar hw1checker.jar -t Bases.java 4. Verify all methods in a single file without running tests. For example, using Bases.java: java -jar hw1checker.jar -v Bases.java5. Any combination of files can also be graded, tested, or verified at the same time. For example grading, Bases.java and Operations.java simultaneously: java -jar hw1checker.jar -g Bases.java Operations.java 3.2 Note for M1 Mac Users When running the autograder, you may see some UnsatisfiedLinkErrors above the autograder output with the message starting “cannot open shared object file”. Ignore them, they will not affect your score.4 Rubric The grade the autograder gives you should be the same as the grade you get (unless you intentionally hardcode just the solutions or try to hack the autograder). 3 5 Deliverables 1. Please upload the following 3 files to the “Homework 1: Bases and Bitwise Operations” assignment on Gradescope: (a) BitVector.java (b) Bases.java (c) Operations.java6 Hints 6.1 Printing numbers in different bases Remember that all numbers are stored in your computer as binary. When you perform operations such as System.out.println(), the computer does the translation into another base for you. All you need to do is tell the computer how you are representing your numbers, and how to interpret them. For example, you can specify 16 in decimal, octal, or hexadecimal like so: System.out.println(16); // decimal (base 10), the default System.out.println(020); // octal (base 8), precede the number with a zero System.out.println(0x10); // hexadecimal (base 16), precede the number with a “0x” (zero x) You can also tell Java to print out your number in different bases using a method called printf. printf is the GRANDFATHER of all printing functions! When we get to C programming, you will be using it a lot. It is useful if you would like to write your own tester as well. printf takes a variable number of arguments, the first of which is a format string. After the format string come the parameters. The formatting for the numbers is controlled by the format string. 6.1.1 Example System.out.printf(“In decimal: %d”, 16); System.out.printf(“In octal: %o”, 16); System.out.printf(“In hexadecimal: %x”, 16); The %d, %o, or %x get replaced by the parameter passed in. printf does not support printing the number out in binary. For more information about printf read http://en.wikipedia.org/wiki/Printf. 6.2 Multiplication and division You may find that there are times in which you need to use division or multiplication, but are not allowed to. Recall from lecture that you can use bitshifting to multiply or divide by powers of 2; this concept isn’t found in the book, but is in the lecture slides.7 Rules and Regulations 7.1 General Rules 1. You should write your code with useful comments that explain any algorithms you use (i.e., do not write a comment for every statement.) While comments are not graded, writing comments will make your code easier to understand, both by yourself and by any TAs that you visit during office hours. 2. Although you may ask TAs for clarification, you are ultimately responsible for what you submit. This means that (in the case of demos) you should come prepared to explain to the TA how any piece of code you submitted works. 3. Please read the assignment in its entirety before asking questions. 4. Please start assignments early, and ask for help early. Do not email us the night the assignment is due with questions.5. If you find any problems with the assignment it would be greatly appreciated if you reported them to the authors (which can be found at the top of the assignment). Announcements will be posted if the assignment changes.7.2 Submission Conventions 1. All files you submit for assignments in this course should have your name at the top of the file as a comment for any source code file, and somewhere in the file, near the top, for other files unless otherwise noted. 2. Submit all three files that you edited to Gradescope. 3. Do not submit compiled files, that is .class files for Java code and .o files for C code. Only submit the files we ask for in the assignment.4. Do not submit links to files. The autograder does not understand it, and we will not manually grade assignments submitted this way as it is easy to change the files after the submission period ends.7.3 Submission Guidelines 1. You are responsible for turning in assignments on time. This includes allowing for unforeseen circumstances. If you have an emergency let us know IN ADVANCE of the due time supplying documentation (i.e. note from the dean, doctor’s note, etc). Extensions will only be granted to those who contact us in advance of the deadline and no extensions will be made after the due date.2. You are also responsible for ensuring that what you turned in is what you meant to turn in. After submitting you should be sure to download your submission into a brand new folder and test if it works. No excuses if you submit the wrong files, what you turn in is what we grade. In addition, your assignment must be turned in via Gradescope. Under no circumstances whatsoever we will accept any email submission of an assignment. Note: if you were granted an extension you will still turn in the assignment over Gradescope.3. Make sure to start working on your assignments early, and keep track of all due dates. See the syllabus for information regarding late submissions; any penalties associated with unexcused late submissions are non-negotiable.7.4 Syllabus Excerpt on Academic Misconduct Academic misconduct is taken very seriously in this class. Quizzes, timed labs and the final examination are individual work. Homework assignments are collaborative at a high level – but you must turn in your own original work. In addition, many homework assignments will be evaluated via demo or code review. During this evaluation, you will be expected to be able to explain every aspect of your submission. Homework assignments will also be examined using electronic computer programs to find evidence of unauthorized collabortion. What is unauthorized collaboration? Each individual programming assignment should be coded by you. You may work with others, but each student should be turning in their own version of the assignment. Submissions that are essentially identical will receive a zero and will be sent to the Dean of Students’ Office of Academic Integrity. Submissions that are copies that have been superficially modified to conceal that they are copies are also considered unauthorized collaboration. You are expressly forbidden to supply a copy of your homework to another student via electronic means. This includes simply e-mailing it to them so they can look at it. If you supply an electronic copy of your homework to another student and they are charged with copying, you will also be charged. This includes storing your code on any site which would allow other parties to obtain your code such as but not limited to public repositories (Github), pastebin, etc. If you would like to use version control, use a private repository on github.gatech.edu. 7.5 Is collaboration allowed? Collaboration is allowed on a high level, meaning that you may discuss design points and concepts relevant to the homework with your peers, share algorithms and pseudo-code, as well as help each other debug code. What you shouldn’t be doing, however, is pair programming where you collaborate with each other on a single instance of the code. Furthermore, sending an electronic copy of your homework to another student for them to look at and figure out what is wrong with their code is not an acceptable way to help them, because it is frequently the case that the recipient will simply modify the code and submit it as their own. Figure 1: Collaboration rules, explained colorfully
HW Q1: (Spong, Problem 2-15) If the coordinate frame A is obtained from the coordinate frame B by a rotation of π/2 about the x-axis followed by a rotation of π/2 about the fixed y-axis, find the rotation matrix R representing the composite transformation. Sketch the initial and final frames. 1 Figure 1: HW Q2: (Spong, Problem 2-37) Consider the diagram in Figure 1. A robot is set up 1 meter from a table. The table top is 1 meter high and 1 meter square. A frame o1 x1, y1, z1 is fixed to the edge of the table as shown. A cube measuring 20 cm on a side is placed on top of the table and at the center of the table with frame o2 x2, y2, z2 established at the center of the cube as shown. A camera is situated directly above the center of the block 2m above the table top with frame o3 x3, y3, z3 attached as shown. Find the homogeneous transformations relating each of these frames to the base frame o0 x0, y0, z0. Find the homogeneous transformation relating the frame o2 x2, y2, z2 to the camera frame o3 x3, y3, z3. 2 Figure 2: HW Q3: For each of the three degree of freedom manipulators shown in Figure 2, find the forward kinematics map. Assume that the link lengths are given to you in as l1, l2, l3, etc. Specifically, in (i), l1 is the vertical height of the first joint and l2 is the length of the arm segment after θ1,2. In (ii) and (iii), l1 is the vertical height of the first joint, l2 is the length of the arm segment after θ1,2 and before θ3, and l3 is the length of the arm after θ3. In (iv), the first two link lengths are as defined above. The last link length is determined by the translational joint, θ3, which determines the additional amount by which the hand extends beyond the l2 part of the arm. HW Q4: Let J (θ) : R n →R 6 be the Jacobian of a manipulator. Show that the manipulability measure µ = √ det(JJT ) is given by the product of the singular values J(θ); that is, µ = 6 ∏ i=1 σi(θ). Thus, µ3(θ) is zero if and only if the Jacobian is singular. 3 HW Q5: A point in a manipulator’s workspace is said to be isotropic if the condition number (the ratio of the largest to smallest singular values) of the Jacobian is 1. (a) Calculate conditions under which a two-link planar manipulator has isotropic points and sketch their location in the plane. (b) Discuss why isotropic points are useful for tasks which involve applying forces against the environment. (a) (b) Figure 3: Illustration of Q1. (a) is before moving the arm. (b) is after moving the arm to the configuration calculated in your function. PA Q1: Implement the function in Q1.m. This function will use the built-in inverse kinematics function in the RTB to calculate a joint configuration that corresponds to a desired end effector position (just position, not orientation). The function will take as input a robot (encoded as a SerialLink class) and a desired position (encoded as a 3×1 vector). It will calculate a target joint configuration that will cause the end of the robot arm to reach a point at the center of the sphere (see Figure 3). This function should work for arbitrary desired positions. Note that in order to use the inverse kinematics functions in the toolbox, you need to apply the appropriate mask vector. 4 PA Q2: Achieve the same result as in PA Q1, but this time using Jacobian pseudoinverse or Jaboian transpose iterations. The exact solution found by your function will probably be different from what you found in PA Q1. However, the end effector should reach the same position. PA Q3: In Q2, you used Jacobian pseudoinverse or transpose iterations to solve for the IK. However, notice that you function returns only a single vector of joint angles corresponding to a final configuration. In this question, I want you to use Jacobian Pseudoinverse control to find a trajectory that moves the end effector to the goal position in precisely a straight line and with a specific velocity. The input to the function is a 3 × 1 goal position, a parameter epsilon that specifies the maximum allowed distance of the manipulator from the goal position at termination, and a parameter velocity that specifies exactly how far the end effector should move on each time step. The output of this function should be an n × 9 trajectory that moves the end effector exactly velocity distance per row of the matrix. (a) Figure 4: Tracing out a circle in the workspace PA Q4: Using the result of Q3, write a function that finds a trajectory (i.e. an n × 9 matrix of joint angles) that moves the end effector in a circle as specified in the hw1.m code (Figure 4) at constant velocity. Each row of the 5 output trajectory matrix should cause the end effector to move its position by exactly the velocity specified. (a) (b) Figure 5: Joint configurations found by my code before (a) and after (b) running the code in Q3. (a) PA Q5: Now, imagine that there is a two-fingered hand on the end of the arm. Use Jacobian pseudoinverse control to move the arm/hand so that the two fingers capture the sphere by moving each finger to one side of the sphere as shown in hw1.m. There are now TWO objectives in this problem (to move each finger to the desired spot), not just one. I want you to solve this problem by formulating a new Jacobian matrix that reflects the twopart objective. Notice that the configuration of the arm and two fingers is now encoded as an 11-dof (degree of freedom) configuration rather than a 9-dof configuration. The first seven joints are the arm joints. The next two joints are for finger f1. The final two joints are for finger f2.
PA Q1: In this question, I have created a convolutional neural network that can be trained to classify MNIST digits. However, my current code runs rather slowly. Please change two lines in the definition of ”layers” in Q1.m to speed up learning. When you’re done, it should get to near 99% accuracy the the end of the second epoch. It might help to have a look at the Matlab docs on MNIST classification at https://www.mathworks.com/help/nnet/ examples/create-simple-deep-learning-network-for-classification. html. PA Q2: In this question, you must modify the network you designed in Q1.m to handle English letter classification instead of digit classification. There are 26 letters in the English alphabet. The letters have exactly the same image size as do the MNIST digits: 28×28 grayscale. Your answer to 1 this question should be a ”Layers” structure analogous to what I provided in Q1.m. PA Q3: In this question, we will speed up learning for letter classification by finetuning a network that was pretrained on the MNIST digit classification task. In pretraining/finetuning, we train a network on one task (in this case, the MNIST digit classification) and then copy most of the learned weights to a new network that is used to solve a new task (in this case, letter classification). Your answer to this question should actually *do* MNIST classification using your code from Q1 and then copy the appropriate weights to a new network. For more information on how to do this with Matlab, see the documentation at: https://www.mathworks.com/help/nnet/ examples/transfer-learning-using-alexnet.html.
PA Q1: In this question, you must use RANSAC to localize a sphere given point cloud data. The point cloud contains a ball that is only partially visible to the sensor. The position of the center of the ball is unknown. The radius is unknown, but between 5cm (0.05m) and 11cm (0.11m). Write a function in Q1.m that calculates these two quantities. You can test your code using the cropped point cloud (see commented hw3.m). But, you should submit code that works on the entire point cloud without cropping. Important: please do NOT use the built-in Matlab function for sphere fitting. However, you MAY use the built-in function for computing surface normals, pcnormals. Hint: one way to generate sphere hypotheses is as follows: 1. sample a point from the cloud; 2. sample a radius of the candidate sphere between 5 and 11cm; 3. project a vector from the sampled point in the direction of the associated surface normal for a distance equal to the sampled radius. This point would be at the center of the candidate sphere. PA Q2: Same as Q1 except for a cylinder. This question is harder because you need to calculate the center, the orientation, and the radius (between 2 0.05m and 0.1m). The orientation should be returned in the form of a unit vector pointing along the axis of the cylinder (either direction is fine). You only need to solve this problem for the segmented cloud, as implemented in the code. Hint: one way to generate cylinder hypotheses is as follows: 1. Sample a radius for the candidate cylinder between 5 and 10 cm. 2. Sample two points from the cloud 3. Set the cylinder axis direction equal to the direction of the cross product between the surface normals associated with the two sampled points. 4. Pick one of the sampled points from the cloud and use it to estimate a candidate center, just as you did in Q1. 5. Project the points in the cloud onto the plane orthogonal to the axis you just calculated. You can do this projection by multiplying the points in the cloud by this matrix: I − aˆaˆ T , where ˆa is equal to the axis of the cylinder. Also project the candidate center into this plane in the same way. 6. Evaluate number of inliers in the plane for a circle with the given projected center and the sampled radius. 3
PA Q1: In this question, you must implement a finite horizon discrete time LQR for the damped mass system described in class and illustrated in the course slides. The time horizon, T, and the A and B matrices that encode the system dynamics are already encoded in hw3.m and you don’t need to change them. Also, the QT, Q, and R cost matrices as well as the initial state, x0, are already encoded in hw3.m. What you need to do is to implement two functions: FH DT Riccati and getControl as described in Q1.m. FH DT Riccati should do the Riccati equation recursion. It should return a cell array, P seq , where each cell is a 4 × 4 P matrix and the cell index is the same as the time index ( P seq{i} denotes the 4 × 4 P matrix at time i). getControl should calculate the control action when the system is in state x at time i. 1 PA Q2: Exactly the same as Q1 except that you should now implement a receeding horizon controller. Whereas in Q1 you were to find the optimal control for a fixed time horizon T, now you must execute a receeding horizon controller where you calculate a control action at each time step by optimizing over the next T time steps. PA Q3: In this question, we are going to use the LQR framework in a new way. As we have studied it so far, LQR can generate large control inputs that can change quickly. For example, the control output calculated in Q1 and Q2 is very large on the first few time steps. It is sometimes desirable to find a trajectory that minimizes the change in control input rather than the magnitude of the control input itself. It turns out that we can use LQR to calculate these sorts of control policies as well. Suppose that we want to minimize a cost function of the form: J(X, U) = x T TQT xT + T X−1 t=1 x T t Qxt + u T t Rut + ∆u T t Rˆ∆ut , where the last term in the summation imposes a cost on change in control input. We can achieve this behavior by defining a new system:xt+1 ut+1 ! =A B 0 I ! xt ut ! +B I ! ∆ut with cost function J(X, U) = xT uT !T QT 0 0 0 ! xT uT ! + T X−1 t=1 xt ut !T Q 0 0 R ! xt ut ! + ∆u T t Rˆ∆ut . You should ask yourself the following questions: what is the new state vector representation? What are the new “A” and “B” matrices? Use this new representation to calculate the optimal trajectory in this scenario. You need to create three functions in Q3.m: FH DT Riccati, getControl, and getSyntheticDynamics. However, FH DT Riccati and getControl should be exactly the same functions as you created in Q1.m. The only new function is getSyntheticDynamics. This takes the underlying 2 parameters of the system as input and produces as output the new modified parameters. PA Q4: This question is completely written – no programming required! The standard LQR formulation finds an optimal solution to the linear system, xt+1 = Axt + But , with a quadratic cost function, J(u1:T −1) = x T TQfx T + T X−1 t=1 x T t Qxt + u T t Rut . But sometimes we want to find an optimal solution to this problem (same cost function): xt+1 = Axt + But + c, where c is an additional constant term that makes the system dynamics affine instead of linear. It turns out that we can solve the affine version of the LQR problem by defining the following matrices: A¯ =A c − BR−1 r 0 1 ! , B¯ =B 0 ! , Q¯ f =Qf qf q T f η ! , Q¯ =Q q q T η ! , where η is an arbitrary constant, and vectors: x¯t =xt 1 ! , u¯t = ut + R −1 r. 1) Substitute the matrices above into A¯x¯t + B¯u¯t in order to show that this parameterization solves the affine problem. 2) Substitute into: x¯ T TQ¯ fx¯ T + T X−1 t=1 x¯ T t Q¯x¯t + ¯u T t Ru¯t to find the cost function that is optimized for. 3 3) Give an example of an affine system that could be controlled using this method. 4) If we redefine A¯ as: A¯ =A c 0 1 ! , then how should we redefine ¯ut so that the system dynamics are still xt+1 = Axt + But + c? What is the effect of this reparameterization on the cost function? 4
PA Q1: Write a function that draws n random samples in the unit (three dimensional) cube and returns the n × n all-pairs distance matrix between pairs of samples. Note that this distance matrix should be symmetric and the diagonal should be zero. PA Q2: The distance matrix calculated in Q1 can be viewed as a fully connected weighted graph. For a given radius and given number of samples, prune edges with weights greater than radius and randomly subsample vertices down to the specified number. Return the corresponding adjacency matrix. PA Q3: For a given radius and number of samples, calculate whether the r-disk graph on the unit cube *should* be connected or not according to Theorem 7 of the Karaman and Frazolli paper. Compare this result with the actual connectivity statistics you got in Q2. How are they the same or different? Why do you think that is? PA Q4: Write a function that calculates the sPRM graph for a given set of samples and a given radius. You should prune any input samples that are in collision and output the remaining samples as samplesFree. You should output the weighted adjacency matrix for the sPRM graph. Note that we’ve 2 given you two functions to help with collision checking: robotCollision and checkEdge. PA Q5: Write a function that implements RRT to find a path from qStart to qGoal. Return qMilestones, an m×4 matrix of vertices (i.e. points) along the path. 3
Project 8 (C++) : K-Curvature edge detector as taught in lecture and in lecture notes. A very easy project. You will be given four data files: dataA, dataB, dataC, and dataD, run your program four times for each data Include in your hard copy: – cover page – source code – outFile1, outFile2, outFile3 for dataA – outFile1, outFile2, outFile3 for dataB – outFile1, outFile2, outFile3 for dataC – outFile1, outFile2, outFile3 for dataD ******************************** Language: C++ Project points: 10 pts Due Date: Soft copy (*.zip) and hard copies (*.pdf): 10 on time: 5/11/2021 Tuesday before midnight -1 for 1 day late: 5/12/2021 Wednesday before midnight -2 for 2 days late: 5/13/2021 Thursday before midnight -10/10: 5/13/2021 Thursday after midnight – 5/10: does not pass compilation 0/10: program produces no output 0/10: did not submit hard copy. *** Follow “Project Submission Requirement” to submit your project. ************************************* I. Inputs: There are two inputs. a) inFile (argv[1]) : A text file contains a list of boundary points of an object in an image. The format of the input is as follows: #rows #cols minVal maxVal // image header label // the label of the object r1 c1 r2 c2 r3 c3 : b) K (from console): ask the user for K to be used in the K-curvature computation. ************************************* II. Outputs: There are three output files. a) outFile1 (argv[2]): The result of the K-curvature of the object boundary points. The format of this output file is as follows: #rows #cols minVal maxVal // image header label // the label of the object. #pts // the number of boundary points r1 c1 1 // not a corner r2 c2 9 // a corner (use 9 for corner indicator for the K-curvature) r3 c3 1 // not a corner : : b) outFile2 (argv[3]): Pretty print (displaying)of the result of the K-curvature corner detection, as in an image, where corner points are printed as 8 and non-corner points are printed as 1. c) outFile3 (argv[4]): for all debugging output ******************************* III. Data structure: ******************************* – An image class friend of kCurvature class – numRows (int) – numCols (int) – minVal (int) – maxVal (int) – imgAry (int**) // a 2D array for display, initially set to 0 methods: – constructor(…) – plotPt2Img (…) // put each point (x, y)’s corner value (1 or 9) at ImgAry(x, y) – reformatPrettyPrint (…) // reuse code from your previous project – A boundaryPt class friend of kCurvature class – (int) x – (int) y – (double) curvature – (int) localMax – (int) corner // 1 means it is not a corner or 9 means it is a corner – A kCurvature class – (int) K // Ask the user from console – (int) numPts // # of boundary pts – Q (int) // an index of the array, initially set to 0 – P (int) // an index of the array, initially set to K – R (int) // an index of the array, initially set to 2*K – (boundaryPt *) PtAry // an 1D array of boundaryPt class size is numPts, // need to dynamically allocate. // use mod function to compute the curvature for the beginning of // the K points without extending the tail of the array, methods: – constructors (…) – initialization (…) // See algorithm below – cornerDetection (…) // See algorithm below – (int) countPts (…) // reads and returns the count of the boundary points in the input file. – storePt (x, y, index) // the x, y to PtAry[index] – computeCurvature (Q,P,R) // taught in class – computeLocalMaxima (PtAry) // P(i) is a local maxima if in its 1 X 5 neighborhood if the curvature // of p(i) is >= the curvatures of // its linear neighbors: p(i-2), p(i-1), p(i+1), p(i+2) // returns 1 if yes, returns 0 if not. – (int) markCorner (PtAry) // go thru the entire PtAry, i = 0 to numPts -1 // set PtAry[i]-> corner to 9 if a) PtAry [i] is a local maxima && b) in its 1X5 neighborhood, only PtAry [i-1] or PtAry [i+1] can be a local maxima // otherwise, set PtAry[i]-> corner to 1 – printBoundary(outFile1) // output only (x, y, corner) of the entire PtAry to outFile1 in format given in the above. – display(…) // plot PtAry to imgAry – printPtAry(outFile3) // For debugging, print the content of the entire PtAry to outFile3******************************* IV. main () ******************************* // Algorithm may contain bugs, debugging is yours and report bugs to Dr. Phillips. Step 0: inFile, outFile1, outFile2, outFile3 open input files numRows, numCols, minVal, maxVal get from inFile label get from inFile K ask the user from console imgAry dynamically allow Step 1: initialization (inFile) printPtAry (outFile3) Step 2: cornerDetection (…) printPtAry(outFile3) Step 3: computeLocalMaxima (PtAry) for all point in PtAry[index], index from 0 to numPts-1 Step 4: markCorner (PtAry) Step 5: printBoundary(outFile1) Step 6: plotPt2Img() // put each point (x, y)’s corner value (1 or 9) at Img(x, y) Step 7: reformatPrettyPrint (imgAry, outFile2) // output imgAry to outFile2 Step 8: close all files ******************************* V. initialization (inFile) ******************************* // Algorithm may contain bugs, debugging is yours and report bugs to Dr. Phillips. Step 1: numPts countPts (inFile) Step 2: close inFile inFile open the input file the second time. Step 3: index 0 Step 4: (x, y) read from inFile Step 5: storePt (x, y, index) // store x, y to PtAry[index] Step 6 : index ++; Step 7 : Repeat step 4 – step 6 until inFile is empty ******************************* VI. cornerDetection (…) ******************************* // Algorithm may contain bugs, debugging is yours and report bugs to Dr. Phillips. Step 0: Q 0 P K R 2* K Step 1: index P Step 2: curvature computeCurvature (Q, P, R) Step 3: PtAry[index]->curvature curvature Step 4: outFile3 print Q, P, R, index, x, y, curvature of PtAry[index] // for debugging to see the curvature. Step 5: Increment Q, P, R by 1 // each need to mod with numPts Step 6: repeat step 2 to step until P == K-1
Project 6 (C++): Thinning is the 2nd methods to obtain the skeletons of objects in a given binary image. The thinning of an object is like peeling off one layer of object from 4 sides (north, south, west, and east) in iterations, until the object becomes a skeleton. Implement the thinning algorithm given in the lecture notes. *** This is an easy project, for your own good, do the project on your own! What you need to do: 1) You will have two (2) date files: image1 and image2 to test your program. 2) Run your program two times using each of test data 3) Include in your hard copies: – Project cover page – Project source code – reformatPrettyPrint outFile1 for image1 – reformatPrettyPrint outFile2 for image1 – reformatPrettyPrint outFile1 for image2 – reformatPrettyPrint outFile2 for image2 ******************************** Language: C++ Project points: 10pts Due Date: Soft copy (*.zip) and hard copies (*.pdf): 10/10 on time: 4/9/2021 Friday before midnight. +1 early submission: 4/5/2021 Monday before midnight. -1 for 1 day late: 4/10/2021 Saturday before midnight. -2 for 2 days late: 4/11/2021 Sunday before midnight. -10/10: after 4/11/2021 Sunday after midnight. -5/10: does not pass compilation 0/10: program produces no output 0/10: did not submit hard copy. *** Follow “Project Submission Requirement” to submit your project. ************************************* I. Input: inFile (argv [1]): a binary image ************************************* II. Outputs: There are two outfiles: a) outFile1 (argv [2]):to store the final thinning result with the image header. b) outFile2 (argv [3]): – reformatPrettyPrint input image with proper caption. – reformatPrettyPrint after completing each cycle (after thinning all sides) with proper caption, i.e., (“result of thinning : cycle – 1”) (“result of thinning : cycle – 2” ) ******************************* III. Data structure: ******************************* – A Thinning class – (int) numRows – (int) numCols – (int) minVal – (int) maxVal – (int) changeflag – (int) cycleCount – (int **) aryOne // a 2D array, need to dynamically allocate at run time of size numRows + 2 by numCols + 2. – (int **) aryTwo // the same as firstAry – methods: – constructor(…) // need to dynamically allocate aryOne and aryTwo // assign values to numRows,…, etc. – zeroFrame (Ary)// framing the extra 2 rows and extra 2 columns with zeros. – loadImage (inFile, aryOne) // Read from the input file onto inside frame of firstAry – copyArys () // always copy from aryTwo to aryOne*** The following four thinning operations are given in the lecture notes; check aryOne and write the result to aryTwo; make sure only operate on pixels inside the frame of arrays – NorthThinning (aryOne, aryTwo) // See the lecture note; – SouthThinning (aryOne, aryTwo) // – WestThinning (aryOne, aryTwo) // : – EastThinning (aryOne, aryTwo) // : – reformatPrettyPrint (aryTwo, file) // reuse code from your previous project ******************************* III. main (…) ******************************* step 0: inFile open input file from argv[1] numRows, numCols, minVal, maxVal read from inFile outFile1 open from argv [2] outFile2 open from argv [3] outFile1 write numRows, numCols, minVal, maxVal dynamically allocate firstAry of size numRows + 2 by numCols + 2. dynamically allocate secondAry of size numRows + 2 by numCols + 2. step 1: zeroFrame(firstAry) zeroFrame(secondAry)step 2: loadImage (inFile, firstAry) step 3: cycleCount 0 step 4: reformatPrettyPrint (firstAry, outFile2) // This print is before thinning step 5: changeFlag 0 step 6: NorthThinning (firstAry, secondAry) copyArys (…) step 7: SouthThinning (firstAry, secondAry) copyArys(…) step 8: WestThinning (firstAry, secondAry) copyArys(…) step 9: EastThinning (firstAry, secondAry) copyArys(…) step 10: cycleCount ++ Step 11: reformatPrettyPrint (firstAry, outFile2) Step 12: repeat step 5 to step 11 while changeFlag > 0 step 13: outFile1 output inside frame of firstAry from [1][1] *without* extra rows and cols step 14: close all files
Project 5 (in Java): Given a binary image, the task is to produce a loss-less compression of the input image via the skeleton of 8-connectness distance transform. (Read all the lecture notes on this topic posted in Google classroom.)Summary of what your program will do: 1) Allocate two 2D arrays with extra 2 rows and extra 2 cols. One for input, called ZeroFramedAry, and one for skeleton, skeletonAry; zero frame both arrays; load input into inside of the frame of ZeroFramedAry. 2) Performs the 1st-pass of the 8-connectness distance transform for all pixels inside the frame of ZeroFramedAry. 3) reformatPrettyPrint of the result of the Pass-1 to outFile1 with proper captions. 4) Performs the 2nd-pass of the 8-connectness distance transform on the result of 1st pass (inside of the frame) 5) reformatPrettyPrint of the result of the Pass-2 to outFile1 with proper captions. 6) Performs local maxima operation on the result of 2nd-pass. 7) reformatPrettyPrint the local maxima to outFile1 with proper captions. 8a) write the header to skeleton file 8b) Produce skeleton (compressed file): for each skeleton (i, j) > 0 (i.e., local maxima), write a triplet i j skeleton (i,j) to *skeleton* file, one triplet per text-line // skeleton file is the compressed (skeleton) file. 9) The name of the compressed file is to be created during the run time of your program, using the original file name with an extension “_skeleton.” For example, if the name of the input file is “image1”, then the name of the compressed file should be “image1_skeleton”. 10) close the compressed file (image1_skeleton) // To make sure your program works correctly; you are going to do a de-compression on the compressed file as follows. 11) re-open the compressed file (image1_skeleton). 12) re-set ZeroFramedAry to zero 13) Load triplets from compressed file to ZeroFramedAry, i.e., for each triplet (i, j, dist), ZeroFramedAry(i, j) dist 14) Perform 1st-pass expansion on the ZeroFramedAry // algorithm given below 15) reformatPrettyPrint of the result of 1st-pass expansion to outFile2 with captions. 16) Perform 2nd pass expansion on the result of 1st expansion // algorithm given below 17) reformatPrettyPrint of the result of 2nd-pass expansion to outFile2 with caption. // If your program work correctly, the result of 2nd-pass expansion should be // identical to the result of the 2nd pass of distance transform. 18) Produce decompressed file: a) Write the original image header to the decompressed file b) Threshold ZeroFramedAry with threshold value == 1 begins at (1,1) and ends at (?,?) i.e., if ZeroFramedAry (i, j) >= 1 output 1 and a blank space to de-compressed file. else output 0 and a blank space to de-compressed file.19) The name of the decompressed file is to be created during the run time of your program, using the name of the input file with an extension “_decompressed.” For example, if the name of the input file is “image1”, then the name of the compressed file should be “image1_decompressed”. (This can be done simply using string concatenation.) 20) Closed the de-compressed file. // after this step your directory should have these three files: image1, image1_skeleton, and image1_decompressed. 21) If your program works correctly, image1_decompressed should be identical to image1. 22) run your program twice: with image1 and image2 Include in your hard copies: – cover page – source code – Run on image1 – Print the input file – Print outFile1 – Print outFile2 – Print skeleton file – Print decompressed file – Run on image2 – Print the input file – Print outFile1 – Print outFile2 – Print skeleton file – Print decompressed file************************************** Language: Java ************************************** Points: 12 pts Due Date: Soft copy (*.zip) and hard copies (*.pdf): 12/12 on time: 3/30/2021 Tuesday before midnight +1 early submission: 3/27/2021 Saturday before midnight -1 for 1 day late: 3/31/2021 Wednesday Thursday before midnight -2 for 2 days late: 4/1/2021 Thursday before midnight -12/12 : after 4/1/2021 Thursday after midnight -6/12: does not pass compilation 0/12: program produces no output 0/12: did not submit hard copy. *** Follow “Project Submission Requirement” to submit your project. ************************************** I. Input (args[0]): a binary image ************************************** II. Outputs: – OutFile1 (args[1]): for – reformatPrettyPrint of t the results of 1st pass 8-connectness distance transform – reformatPrettyPrint of the results of 2nd pass 8-connectness distance transform – reformatPrettyPrint of the local maxima skeleton – OutFile2 (args[2]): for – reformatPrettyPrint of the results of 1st pass expansion – reformatPrettyPrint of the results of 2nd pass expansion – skeleton file (generated at run-time) for store the compressed file using the following format: Example: 20 20 0 7 // the header of the distance transform image. 4 7 2 // the skeleton pixel at (4, 7) with distance of 2 6 7 3 // the skeleton pixel at (6, 7) with distance of 3 : : – DeCompressed file (generated at run-time), an image file where the first text-line is the image header, follows by rows and cols of pixel values. ******************************* III. Data structure: ******************************* – An ImageProcessing class – numRows (int) – numCols (int) – minVal (int) – maxVal (int) – newMinVal (int) – newMinVal (int) – zeroFramedAry (int **) a 2D array, need to dynamically allocate of size numRows + 2 by numCols + 2. – skeletonAry (int **) a 2D array, need to dynamically allocate of size numRows + 2 by numCols + 2. – methods: – setZero (Ary) // set 2D Ary to zero. You should know how to do this. – loadImage (…) // Read from the given File onto inside frame of zeroFramedAry // You should know how to do this. – Compute8Distance (…) // See algorithm below – fistPass8Distance (Ary) // algorithm is given in lecture notes – secondPass_8Distance (zeroFramedAry) // algorithm is given in lecture notes // Note** In second pass, you need // to keep track the newMinVal and newMaxVal // You should know how to do this – isLocalMaxima (zeroFramedAry, i, j) // algorithm is given in lecture notes – computeLocalMaxima (zeroFramedAry, skeletonAry) // algorithm is given in lecture notes – extractLocalMaxima(…) // for each skeletonAry[i,j] > 0 write the triplet to // skeletonFile. For easy programming, i and j do not need to // subtract by 1 when output the triplets to skeletonFile. – skeletonExtraction (…) // See algorithm below – skeletonExpansion(…) // See algorithm below – firstPassExpension (…)// algorithm is given in lecture note. – secondPassExpension (…)// algorithm is given in lecture note. – ary2File(…) // do a threshold on zeroFramedAry // with the threshold value at 1, begins at (1,1) // and ends at (?,?) i.e., if zeroFramedAry (i, j) >= 1 output 1 and a blank space to decompressed file. else output 0 and a blank space to decompressed file. – reformatPrettyPrint (…) // reuse codes from your previous project. ******************************* III. main (…) ******************************* step 0: inFile open input file numRows, numCols, minVal, maxVal read from inFile dynamically allocate zeroFramedAry with extra 2 rows and 2 cols dynamically allocate skeletonAry with extra 2 rows and 2 cols open outFile_1, outFile_2 Step 1: skeletonFileName args[0] + “_skeleton.txt” Step 2: skeletonFile open ( skeletonFileName ) Step 3: decompressedFileName args[0] + “_decompressed.txt” Step 4: decompressFile open (decompressedFileName) step 5: setZero (zeroFramedAry) setZero (skeletonAry) Step 6: loadImage (inFile, zeroFramedAry) // begins at zeroFramedAry (1,1) Step 7: compute8Distance (zeroFramedAry, outFile1) // Perform distance transform Step 8: skeletonExtraction (zeroFramedAry, skeletonAry, skeletonFile, outFile1) // perform lossless compression Step 9: skeletonExpansion (zeroFramedAry, skeletonFile, outFile2) // perform decompression step 10: Output numRows, numCols, newMinVal, newMaxVal to decompressFile Step 11: ary2File (zeroFramedAry, decompressFile) Step 12: close all files ******************************* IV. Compute8Distance (zeroFramedAry, outFile1) ******************************* step 1: fistPass_8Distance (zeroFramedAry) / step 2: reformatPrettyPrint (zeroFramedAry, outFile1) // with proper caption i.e., 1st pass distance transform step 3: secondPass8Distance (zeroFramedAry) // begins at zeroFramedAry(?,?) Step 4: reformatPrettyPrint (zeroFramedAry, outFile1) // with proper caption i.e., 2nd pass distance transform ******************************* V. skeletonExtraction (zeroFramedAry, skeletonAry, skeletonFile, outFile1) ******************************* step 1: computeLocalMaxima (zeroFramedAry, skeletonAry) Step 2: reformatPrettyPrint (skeletonAry, outFile1) // with proper caption i.e., Local maxima step 3: extractLocalMaxima (skeletonAry, skeletonFile) Step 4: close skeletonFile******************************* VI. skeletonExpansion (zeroFramedAry, skeletonFile, outFile2) ******************************* Step 1: re-open skeletonFile Step 2: setZero (zeroFramedAry) step 3: load (skeletonFile, zeroFramedAry) step 4: firstPassExpension (zeroFramedAry) step 5: reformatPrettyPrint (zeroFramedAry, outFile2) // with proper caption i.e., 1st pass Expansion step 6: secondPassExpension (zeroFramedAry) // begins at ZeroFramedAry(?,?) // During the 2nd pass, you need to track the newMinVal and newMaxVal Step 7: reformatPrettyPrint (zeroFramedAry, outFile2) // with proper caption i.e., 2nd pass Expansion
Project 4 (C++): You are to implement both 4-connected and 8-connected component algorithms in this project. Your program let the user to choose which algorithm (4-CC or 8-CC) to run the program from console. Both algorithms consist of the following stages except which neighbors are to be checked: ******************************** Language: C++ Project points:12 pts Due Date: Soft copy (*.zip) and hard copies (*.pdf): 3/21/2021 Sunday before midnight +1 early submission: 3/18/2021 Thursday before midnight -1 for 1 day late: 3/22/2021 Monday before midnight -2 for 2 days late: 3/23/2021 Tuesday before midnight -12/12 : after 3/23/2021 Tuesday after midnight -6/12: does not pass compilation 0/12: program produces no output 0/12: did not submit hard copy. *** Follow “Project Submission Requirement” to submit your project. *** Run your program twice; first using 8 and then using 4. Your hard copies include: -Cover page – source code – RFprettyPrintFile for 8-connectness – labelFile for 8-connectness – propertyFile for 8-connectness – RFprettyPrintFile for 4-connectness – labelFile for 4-connectness – propertyFile for 4-connectness ************************************* I. Inputs: There are two inputs a) inFile (argv[1]): A binary image. b) connectness (argv[2]) ************************************* II. Outputs: There are 3 output files. a) RFprettyPrintFile (argv[3]): (include in your hard copy) for the followings: ** a proper caption means the caption should say what the printing is. – reformatPrettyPrint of the result of the Pass-1 with proper captions – print newLabel and the EQAry after Pass-1, with proper captions – reformatPrettyPrint of the result of the Pass-2 with proper captions – print newLabel and the EQAry after Pass-2, with proper captions – Print the EQAry after manage the EQAry, with proper caption – reformatPrettyPrint of the result of the Pass-3 with proper captions – reformatPrettyPrint of the result bounding boxes drawing. b) labelFile (argv[4]): ** (include in your hard copy) to store the result of Pass-3 — the labelled image file with image header, numRows numCols newMin NewMax. ** This file will be used in future processing. c) propertyFile (argv[5]): ** (include in your hard copy) to store the connected component properties. The format is to be as below: – 1st text-line, the header of the input image, – 2nd text-line is the total number of connected components. – from 3rd text, use four text-lines per each connected component: – label – number of pixels – upperLftR upperLftC //the r c coordinated of the upper left corner – lowerRgtR lowerRgtC //the r c coordinated of lower right corner For an example: 45 40 0 9 // image header 9 // there are a total of 9 CCs in the image 1 // CC label 1 187 // 187 pixels in CC label 1 4 9 // upper left corner of the bounding box at row 4 column 9 35 39 // lower right corner of the bounding box at row 35 column 39 : : ** This file will be used in future processing. ******************************* III. Data structure: ******************************* A CClabel class – (int) numRows – (int) numCols – (int) minVal – (int) maxVal – (int) newMin – (int) newMax – (int) newLabel // initialize to 0 – (int) trueNumCC // the true number of connected components in the image // It will be determined in manageEQAry method. – (int **) zeroFramedAry // a 2D array, need to dynamically allocate //at run time of size numRows + 2 by numCols + 2. – NonZeroNeighborAry [5] // 5 is the max number of neighbors you have to check. // For easy programming, you may consider using this 1-D array // to store pixel (i, j)’s non-zero neighbors during pass 1 and pass2. – (int *) EQAry // an 1-D array, of size (numRows * numCols) / 4 // dynamically allocate at run time // and initialize to its index, i.e., EQAry[i] = i. – Property (1D struct or class) – (int) label // The component label – (int) numPixels // total number of pixels in the cc. – (int) minR – (int) minC – (int) maxR – (int) maxC // In the Cartesian coordinate system, any rectangular box can be //represented by two points: upper-left corner and the lower-right //corner of the box. Here, the two points:(minR minC) and(maxR maxC) represents the smallest rectangular box that the cc can fit inside the box. – (*Property) CCproperty // A struct 1D array for storing all components’ properties. // The size of array is the actual number of cc after manageEQAry– Methods: – constructor(…) // need to dynamically allocate all arrays, and assign values to numRows,, etc. – zero2D (…) // ** Initialized a 2-D array to zero. You must implement this method, don’t count on Java. – minus1D (…) // ** Initialized a 1-D array to -1. – loadImage (…) // read from input file and write to zeroFramedAry begin at(1,1) – imgReformat (zeroFramedAry, RFprettyPrintFile) // Print zeroFramedAry to RFprettyPrintFile // as in your previous project. – connect8Pass1 (…) // On your own, as taught in class and algorithm is in lecture note – connect8Pass2 (…) // On your own, as taught in class and algorithm is in lecture note – connect4Pass1 (…) // On your own, as taught in class and in lecture note – connect4Pass2 (…) // On your own, as taught in class and in lecture note – connectPass3 (…) // There is no differences between 4-connectness and // 8-connectness. On your own, as taught in class and in lecture note – drawBoxes (…) // Draw the bounding boxes on all connected components // in zeroFramedAry. See algorithm below – updateEQ (…) // Update EQAry for all non-zero neighbors to minLabel, it will be easier to use //NonZeroNeighborAry to store all non-zero neighbors. – (int) manageEQAry (…) // on your own // The algorithm was taught and given in class and in lecture note // The method returns the true number of CCs in // the labelled image. – printCCproperty (…) // print the component properties to propertyFile // using the format given in the above. // you should know how to do this. – printEQAry (…) // Print EQAry with index up to newLabel, not beyond. On your own – printImg (…) // Output image header and zeroFramedAry (inside of framing) to labelFile // on your own. ******************************* IV. main(…) ******************************* step 0: inFile open the input file (argv[1]) RFprettyPrintFile, labelFile, propertyFile open from args[] numRows, numCols, minVal, maxVal read from inFile dynamically allocate zeroFramedAry. Connectness from argv[2] newLabel 0 step 1: zero2D (zeroFramedAry) step 2: loadImage (inFile, zeroFramedAry) step 3: if connectness == 4 connect4Pass1 (… ) imgReformat (zeroFramedAry, RFprettyPrintFile) printEQAry (newLabel, RFprettyPrintFile) // print the EQAry up to newLable with proper caption Connect4Pass2 (…) imgReformat (zeroFramedAry, RFprettyPrintFile) printEQAry (newLabel, RFprettyPrintFile) // print the EQAry up to newLabel with proper caption step 4: if connectness == 8 connect8Pass1 (… ) imgReformat (zeroFramedAry, RFprettyPrintFile) printEQAry (newLabel, RFprettyPrintFile) // print the EQAry up to newLabel with proper caption Connect8Pass2 (…) imgReformat (zeroFramedAry, RFprettyPrintFile) printEQAry (newLabel, RFprettyPrintFile) // print the EQAry up to newLable with proper caption step 5: trueNumCC manageEQAry (EQAry, newLabel) printEQAry (newLabel, RFprettyPrintFile) // print the EQAry up to newLabel with proper caption step 6: connectPass3 (…) step 7: imgReformat (zeroFramedAry, RFprettyPrintFile) step 8: printEQAry (newLabel, RFprettyPrintFile) // print the EQAry up to newLabel with proper caption step 9: output numRows, numCols, newMin, newMax to labelFile step 10: printImg (labelFile) // Output the result of pass3 from zeroFramedAry to //labelFile, begins at zeroFramedAry[1, 1] and ending at ?? step 12: printCCproperty (propertyFile) // print cc properties to propertyFile step 13: drawBoxes (zeroFramedAry, CCproperty) step 14: imgReformat (zeroFramedAry, RFprettyPrintFile) step 15: print trueNumCC to RFprettyPrintFile with proper caption step 16: close all files ******************************* VI. drawBoxes (zeroFramedAry, CCproperty) ******************************* step 1: index 1 step 2: minRow CCproperty[index]’s minR // need to add 1 minCol CCproperty[index]’s minC // need to add 1 maxRow CCproperty[index]’s maxR // need to add 1 maxCol CCproperty[index]’s maxC // need to add 1 label CCproperty[index]’s label step 3: Assign all pixels on minRow from minCol to maxCol label Assign all pixels on maxRow from minCol to maxCol label Assign all pixels on minCol from minRow to maxRow label Assign all pixels on maxCol from minRow to maxRow label step 4: index++ step 5: repeat step 2 to step 4 while index is within the number of cc.
Project 2 (in C++): You are to implement the three image enhancement methods taught in class: (1) 3X3 averaging, (2) 3×3 median filter,(3)5×5 corner preserving filter. ************************************** Add the following into your #include: #include using namespace std; *************************************** Hard copy includes: – Cover page – Source code – rfImg file – AvgOutImg file – AvgThrImg file – AvgPrettyPrint file – MedianOutImg file – MedianThrImg file – MedianPrettyPrint file – CPOutImg file – CPThrImg file – CPrettyPrint file ** You must use a fix font — “courier new”, and choose a font size so that When printing an image file, it will fit in one page. ************************************** Language: (C++) ************************************** Project points: 10 pts Due Date: Soft copy (*.zip) and hard copies (*.pdf): -0 2/21/2021 Sunday before midnight -1 for 1 day late: 2/22/2021 Monday before midnight -2 for 2 days late: 2/22/2021 Tuesday before midnight -10/10: 2/22/2021 Tuesday after midnight *** Name your soft copy and hard copy files using the naming convention as given in the project submission requirement discussed in a lecture and is posted in Google Classroom. *** All on-line submission MUST include Soft copy (*.zip) and hard copy (*.pdf) in the same email attachments with correct email subject as stated in the email requirement; otherwise, your submission will be rejected. ******************************* I. Input files: a) inFile (argv[1]): A txt file representing a grey-scale image with image header. b) threshold value (argv[2]) // USE 30 ******************************* II. Output files: 1) rfImg (argv[3]): the input image after reformatting. 2) AvgOutImg(argv[4]): The image of the result of 3×3 average filter, after reformatting. 3) AvgThrImg(argv[5]): The threshold result of 3×3 average filter, after reformatting. 4) AvgPrettyPrint(argv[6]): The pretty print of the threshold result of average filter. 5) MedianOutImg(argv[7]): The image of the result of 3×3 median filter, after reformatting. 6) MedianThrImg(argv[8]): The threshold result of 3×3 median filter, after reformatting. 7) MedianPrettyPrint(argv[9]): The pretty print of the threshold result of median filter. 8) CPOutImg(argv[10]): The image of the result of 5×5 corner preserve filter, after reformatting. 9) CPThrImg(args[11]): The threshold result of 5×5 corner preserve filter, after reformatting. 10) CPPrettyPrint(args[12]): The pretty print of the threshold result of corner preserve filter. ******************************* III. Data structure: ******************************* – imageProcessing class – (int) numRows – (int) numCols – (int) minVal – (int) maxVal – (int) newMin – (int) newMax – (int) thrVal // from argv[2] – (int) neighborAry [9] // You may consider using this // 1-D array to hold the 3×3 neighbors of a pixel // during the computation of average and median operations. – (int) CPmasks[8][5][5] // This 3D array is used in the corner //preserving averaging. These 8 masks of 5×5 are designed to //compute the averages of the 8 groups in a pixel’s 5×5 //neighborhood without having to indexing the coordinates of 9 //pixels in each of the 8 groups. The 8 masks are posted in Google //classroom. // The detail of the usage of these masks is given in the lecture. – (int) neighbor5x5[5][5] // for store the 5×5 neighbors of a pixel. – (int **) mirror3by3Ary // a 2D array, dynamically allocate //at run time of size numRows + 2 by numCols + 2. // This array is for loading the input image into // the inside the frame of the array and to be use by // 3×3 averaging (mean filter) and median filter. – (int **) mirror5by5Ary // a 2D array, dynamically allocate //at run time of size numRows + 4 by numCols + 4. // This array is for loading the input image into // the inside the frame of the array and to be use by // 5×5 corner preserve averaging. – (int **) avgAry // a 2D array, dynamically allocate at run time // of size numRows + 2 by numCols + 2 for storing // the result of the 3×3 averaging – (int **)medianAry // a 2D array, dynamically allocate at run time // of size numRows + 2 by numCols + 2 for storing // the result of the 3×3 median filter. – (int **) CPAry // a 2D array, dynamically allocate at run time // of size numRows + 4 by numCols + 4 for storing // the result of the 5×5 corner preserving averaging methods: – threshold (…)// see algorithm below. – imgReformat (…) // see algorithm below. – loadCPmasks (…) // Either hard coded or read from files – loadneighbors (…) // load the 5×5 neighbors of a pixel. – loadImage (…)// On your own!! // read from input file and load the image onto mirror3by3Ary and // mirror5by5Ary. – mirrorFraming (Ary, frameSize) // On your own!! See lecture note. // The method should be able handle 3×3 mirrorframe and 5×5 // mirrorframe. For 3×3, frame size is 1, for 5×5, frame size // is 2. – ComputeAvg (…) // see algorithm below. // Scans thru all pixels inside the frame of the mirror3by3Ary, // apply avg3x3 on each pixel, then, outputs the result to avgAry; // it also keeps track of newMin and newMax during the process. – computeMedian(…) // see algorithm below. // Scans thru all pixels inside the frame of the mirror3by3Ary, // apply median3x3 on each pixel, then, outputs the result to // medianAry; it also keeps track of newMin and newMax during the // process. – computeCPfilter (…) // see algorithm below. // Scans thru all pixels inside the frame of the mirror5by5Ary, // applying the corner preserving algorithm, then, outputs the // result to CPAry; it also keeps track of newMin and newMax // during the process. – sort (neighborAry) // Used by median filter method. You may use any //sorting algorithm. On your own!! – (int) avg3x3 (i, j) // On your own!! See lecture note. // computes and returns the average of the pixel (i, j)’s 3×3 // neighborhood. – (int) median3x3 (i, j) //On your own!! See lecture note. // computes and returns the median value of the pixel (i, j)’s 3×3 // neighborhood. – (int) CP5x5 (i, j) //On your own!! See lecture note. // The method loads the 5×5 neighbors of mirror5by5Ary[i, j] onto // CPneighbor5x5 array, then apply convolution using CPmasks to //get the averages; then computes the differences between //mirror5by5Ary[i, j] and each of the 8 averages, then returns the //average of a group having the minimum differences. -(int) convolution (…) // On your own!! See lecture note. // Compute the convolution using a given 5×5 mask // onto the loaded Pneighbor5x5 and returns the result. – AryToFile (ary, outFile, frameSize) // on your own! // It prints the image header: numRows numCols newMin newMax //to outFile, then, prints the ary without the frames. – prettyPrint (inAry, outFile) // print without the frames. // if inAry [i][j] > 0 outFile inAry [i][j] follows by one blank space else outFile “.” follows by one blank space ******************************* IV. main(…) ******************************* step 0: open inFile and open all outfiles thrVal get from argv[2] step 1: numRows, numCols, minVal, maxVal read from inFile newMin minVal newMax maxVal step 2: loadImage (inFile) step 3: mirrorFraming (mirror3by3Ary,1) imgReformat (mirror3by3Ary, rfImg) step 4: ComputeAvg(…) imgReformat (avgAry, AvgOutImg, 1) threshold (avgAry, thrAry, 1) AryToFile (thrAry, AvgThrImg, 1) prettyPrint (thrAry, AvgPrettyPrint, 1) step 5: computeMedian (…) imgReformat (medianAry, MedianOutImg, 1) threshold (medianAry, thrAry, 1) AryToFile (thrAry, MedianThrImg, 1) prettyPrint (thrAry, MedianPrettyPrint, 1) Step 6: mirrorFraming (mirror5by5Ary, 2) Step 7: computeCPfilter (…) imgReformat (CPAry, CPOutImg, 2) threshold (CPAry, thrAry, 2) AryToFile (thrAry, CPThrImg, 2) prettyPrint (thrAry, CPPrettyPrint, 2) step 8: close all files ************************************** V. computeAvg (…) ************************************** // process the entire ary, keep track of newMin and newMax step 0: newMin 9999; newMax 0 step 1: r 1 step 2: c 1 step 3: avgAry [r,c] avg3x3 (r, c) step 4: if newMin > avgAry [r,c] newMin avgAry [r,c] if newMax < avgAry [r,c] newMax avgAry [r,j] step 5: c++ step 6: repeat step 3 to step 5 while c < numCols+1 step 7: r++ step 8: repeat step 2 to step 7 while r < numRows+1 ************************************** VI. computeMedian (…) ************************************** // process the entire ary, keep track of newMin and newMax step 0: newMin 9999; newMax 0 step 1: r 1 step 2: c 1 step 3: medianAry [r,c] median3x3 (r, c) step 4: if newMin > medianAry [r,c] newMin medianAry [r,c] if newMax < medianAry [r,c] newMax medianAry [r,j] step 5: c++ step 6: repeat step 3 to step 5 while c < numCols+1 step 7: r++ step 8: repeat step 2 to step 7 while r < numRows+1 ************************************** VI. computeCPfilter (…) ************************************** // process the entire ary, keep track of newMin and newMax step 0: newMin 9999; newMax 0 step 1: r 2 step 2: c 2 step 3: CPAry [r,c] CP5x5 (r, c) step 4: if newMin > CPAry [r,c] newMin CPAry [r,c] if newMax < CPAry [r,c] newMax CPAry [r,j] step 5: c++ step 6: repeat step 3 to step 5 while c < numCols+2 step 7: r++ step 8: repeat step 2 to step 7 while r < numRows+2 ******************************* VII. imgReformat (inAry, OutImg, frameSize) ******************************* Step 1: OutImg output numRows, numCols, newMin, newMax Step 2: str to_string(newMax) // a method in C++ string class Width length of str Step 3: r frameSize Step 4: c frameSize Step 5: OutImg inAry[r][c] Step 6: str to_string (inAry[r][c]) WW length of str Step 7: OutImg one blank space WW ++ Step 8: repeat step 7 while WW < Width Step 9: c++ Step 10: repeat Step 5 to Step 9 while c < (numCols + frameSize) Step 11: r++ Step 12: repeat Step 4 to Step 10 while c < (numCols + frameSize) ******************************* VII. threshold (ary1, ary2, frameSize) ******************************* step 0: newMin 0 newMax 1 step 1: r frameSize step 2: c frameSize step 3: if ary1[r][c] >= thrVal ary2[r][c] 1 else ary2[r][c] 0 step 4: c++ step 5: repeat step 3 to step 4 while c < (numCols + frameSize) step 6: r++ step 7: repeat step 2 to step 6 while r < (numRows + frameSize)
you are to perform the following tasks: 1. Compute histogram of the input image and display the histogram in two formats, see the output description below. 2. Perform binary threshold operation on the input image with a given threshold value via argv[]. 3. Output the result of the threshold in two formats, see the output description below. ************************************** Language: C++ ************************************** Project points: 10 pts Due Date: Soft copy (*.zip) and hard copies (*.pdf): -0 2/14/2021 Sunday before midnight -1 for 1 day late: 2/15/2021 Monday before midnight -2 for 2 days late: 2/16/2021 Tuesday before midnight -10/10: 2/16/2021 Tuesday after midnight *** Name your soft copy and hard copy files using the naming convention as given in the project submission requirement discussed in a lecture and is posted in Google Classroom. *** All on-line submission MUST include Soft copy (*.zip) and hard copy (*.pdf) in the same email attachments with correct email subject as stated in the email requirement; otherwise, your submission will be rejected. 1. Run your program on data1 with threshold 5 2. Run your program on data2 with threshold 38. 3. Include in your hard copy *.pdf file as follows: – Cover page. – source code. – Output outFile1 for data 1. – Output outFile2 for data 1. – Output outFile3 for data 1. – Output outFile4 for data 1. – Output outFile1 for data 2. – Output outFile2 for data 2. – Output outFile3 for data 2. – Output outFile4 for data 2. ********************************************** I. Input: There are two inputs to the program. ********************************************** a) inFile1 (argv[1]): a txt file representing a grey-scale image, where the first text line (4 integers) is the “header” of the input image then follows by rows and cols of integers. For example, 4 6 1 12 // image has 4 rows,6 cols, min is 1, max is 12 2 3 4 11 2 9 5 6 11 2 10 7 1 1 12 1 9 9 4 5 6 9 9 9 b) a threshold value (argv[2]) ******************************************* II. Outputs: There are four output files. ******************************************* a) OutFile1 (use argv[3]): For the output of histogram in the following format (to be used in the future project): The first text-line is the image header, follows by a list of pairs where i = 0 to max and j is the hist(i) For example: 4 6 1 12 0 0 1 3 2 3 3 1 4 2 5 2 6 2 7 1 8 0 9 6 10 1 11 2 12 1 b) OutFile2 (use argv[4]): Display the histogram (for visual) as follows: first text line is the image header then follows by a list of : greyScale (numpixels): number of +’s for example, the output of the histogram of the above image would be: Use the maximum of 70 +’s for all counts greater than 70. Use small font size so that 70 +’s can be printed on one text line. 4 6 1 12 0 (0): 1 (3):+++ 2 (3):+++ 3 (1):+ 4 (2):++ 5 (2):++ 6 (2):++ 7 (1):+ 8 (0): 9 (6):++++++ 10 (1):+ 11 (2):++ 12 (1):+ c) outFile3 (use argv[5]): The result of the threshold of the input image. (To be used for future processing.) Note: The output binary image also needs to have the image header. For example, given the above image and 6 as the threshold value then the binary image would be: 4 6 0 1 // notice the min and max values have changed 0 and 1. 0 0 0 1 0 1 0 1 1 0 1 1 0 0 1 0 1 1 0 0 1 1 1 1 d) outFile4 (use argv[6]): (For nice visual purposes). For example, given the above threshold image, the pretty print replace 0 with a period.4 6 0 1 . . . 1 . 1 . 1 1 . 1 1 . . 1 . 1 1 . . 1 1 1 1 ******************************* III. Data structure: ******************************* – image class – numRows (int) – numCols (int) – minVal (int) – maxVal (int) – histAry(int*) //a 1D integer array, size of maxVal + 1 // need to be dynamically allocated at run time – thresholdValue (int) // via argv[2] Methods: – computeHist(…) // The algorithm is given in the lecture note – printHist (…)// on your own; see the above example – dispHist (…)// on your own; see the above example – threshold(…) // The algorithm is given below ******************************* IV. main (…) ******************************* step 0: inFile open input file use argv[1] open all 4 outFiles via argv[3], argv[4], argv[5], argv[6] step 1: numRows, numCols, minVal, maxVal read from inFile step 2: histAry dynamically allocate and initialize to 0 step 3: ComputeHist (…) step 4: printHist(outFile1) Step 5: dispHist (outFile2) step 6: close inFile reopen inFile Step 7: thrVal get from argv[2] outFile3 “The threshold value uses is ” thrVal outFile4 “The threshold value uses is ” thrVal Step 8: threshold (inFile, outFile3, outFile4, thrVal) step 9: close all files ************************************************* V. threshold (inFile, outFile3, outFile4, thrVal) ************************************************* Step 0: minVal 0 maxVal 1Step 1: outFile3, outFile4 output numRows, numCols, minVal and maxVal Step 2: pixelVal read from inFile one integer at a time Step 3: if pixelVal >= thrVal outFile3
A) You will be given four (4) image files: Img1, Img2, Img3, and Img4; and you will be given two (2) structuring elements: Elem1 and Elem2. – Test1: to verify the correctness of your program, you will run your program using Img1 with Elem1. – Test2: to verify the correctness of your program, you will run your program using Img2 with Elem2. B) You are to design two (2) structuring elements: Elem3 and Elem4 for Img3 and Img4. To design Elem3, make observation to see what are objects in Img3. The goal is to extract object(s) from Img3. To design Elem4, make observation to see what are objects in Img4. The goal is to extract object(s) from Img4. – Test3: to verify the correctness of your design, you will run your program using Img3 with Elem3. – Test4: to verify the correctness of your design, you will run your program using Img4 with Elem4. Your hard copies include: – cover sheet – program source code – print all output files for test1 – print all output files for test2 – print all output files for test3 – print all output files for test4 ******************************** Language: Java Project points: 10 pts Due Date: Soft copy (*.zip) and hard copies (*.pdf): -0 2/28/2021 Sunday before midnight -1 for 1 day late: 3/1/2021 Monday before midnight -2 for 2 days late: 3/2/2021 Tuesday before midnight -10/10: 3/2/2021 Tuesday after midnight -5/10: does not pass compilation 0/10: program produces no output 0/10: did not submit hard copy. *** Follow “Project Submission Requirement” to submit your project. ******************************* I. Inputs: There are two input files. ******************************* a) InFile1 (args[0]): a txt file representing a binary image with header. b) InFile2 (args[1]): a txt file representing a binary image of a structuring element with header and the origin of the structuring element. The format of the structuring element is as follows: 1st text line is the header; the 2nd text line is the position (w.r.t. index) of the origin of the structuring element then follows by the rows and column of the structuring element. For example: 5 5 0 1 // 5 rows, 5 columns, min is 0, max is 1: 2-D structuring element 2 2 // origin is at row index 2 and column index 2. 0 0 1 0 0 0 0 1 0 0 1 1 1 1 1 0 0 1 0 0 0 0 1 0 0 ** Note: when a structure element contains zeros, only those 1’s to be used in the matching in the erosion! Another example: 3 3 1 1 // 3 rows, 3 columns, min is 1, max is 1: 2-D structuring element 1 1 // origin is at row index 1 and column index 1. 1 1 1 1 1 1 1 1 1 Another example: 1 5 1 1 // 1 rows, 5 columns, min is 1, max is 1: 1-D structuring element 0 2 // origin is at row index 0 and column index 2. 1 1 1 1 1 ******************************* II. Outputs: (All of the following output files need to be included in your hard copies!) – dilateOutFile (args[2]): the result of dilation image with header, without framed boarders. – erodeOutFile (args[3]): the result of erosion image with header, the same dimension as imgFile – closingOutFile (args[4]): the result of closing image with header, the same dimension as imgFile – openingOutFile (args[5]): the result of opening image with header, the same dimension as imgFile – prettyPrintFile (args[6]): pretty print which are stated in the algorithm steps *** Note: When you run your program, please name your output files as given in the above. *** NO HARD coded file names in the program, -2 points if you hard code file name in this project!!! ******************************* III. Data structure: ******************************* – numImgRows (int) – numImgCols (int) – imgMin (int) – imgMax (int) – numStructRows (int) – numStructCols (int) – structMin (int) – structMax (int) – rowOrigin (int) – colOrigin (int) – rowFrameSize (int) // set to numStructRows / 2 – colFrameSize (int) // set to numStructCols / 2 – extraRows (int) // set to rowFrameSize * 2 – extraCols (int) // set to colFrameSize * 2 – zeroFramedAry (int **) // a 2D array of size (numImgRows + extraRows) by (numImgCols + extraCols) // for the input image, needs to dynamically allocate at run time. – morphAry (int **) // Same size as zeroFramedAry. – tempAry (int **) // Same size as zeroFramedAry. // tempAry is to be used as the intermediate result in opening and closing operations. – structAry (int **) //a 2D array of size numStructRows by numStructCols, // needs to dynamically allocate at run time.Methods: – loadImg (imgFile, zeroFramedAry) // On your own! // load imgFile to zeroFramedAry, begins at (rowOrigin, colOrigin) and ends at ?? – loadstruct (structFile, structAry) // On your own! // load structFile to structAry. – zero2DAry (…) // set a given 2D array to zero. – ComputeDilation (…) // process every pixel of the entire ary // see algorithm below. – ComputeErosion (…)// process every pixel of the entire ary // see algorithm below. – ComputeOpening (…)// see algorithm below. – ComputeClosing (…)// see algorithm below. – dilation (i, j, inAry, outAry) // Perform dilation on pixel (i, j) with structAry. // On your own! – erosion (i, j, inAry, outAry) // Perform erosion on pixel (i, j) with structAry. // On your own! – AryToFile (Ary, outFile) // output the img header (from input image header) //then output the rows and cols of Ary to outFile *excluding* the framed borders of Ary. – prettyPrint (Ary, outFile) // Remark: use “Courier new” font and small font size to fit in the page. // if Ary [i, j] == 0 output “. ” // a period follows by a blank // else output Ary [i, j] follows by a blank ******************************* IV. Main(…) ******************************* step 0: imgFile, structFile, dilateOutFile, erodeOutFile, openingOutFile, closingOutFile, prettyPrintFile open step 1: numImgRows, numImgCols, imgMin, imgMax read from imgFile numStructRows, numStructCols, structMin, structMax read from structFile rowOrigin, colOrigin read from strucFile step 2: zeroFramedAry, structAry, morphAry, tempAry dynamically allocate // see description in the above step 3: zero2DAry(zeroFramedAry, numImgRows, numImgCols) // see description in the above step 4: loadImg (imgFile, zeroFramedAry) // see description in the above prettyPrint (zeroFramedAry, prettyPrintFile) // write a meaningful caption before prettyPrint step 5: zero2DAry(structAry, numStructRows, numStructCols) loadstruct (structFile, structAry) // see description in the above prettyPrint (structAry, prettyPrintFile) // see description in the above step 6: zero2DAry(morphAry, numImgRows, numImgCols) ComputeDilation (zeroFramedAry, morphAry) // see algorithm below AryToFile (morphAry, dilateOutFile) // see description in the above prettyPrint (morphAry, prettyPrintFile) // write a meaningful caption before prettyPrint step 7: zero2DAry(morphAry, numImgRows, numImgCols) ComputeErosion (zeroFramedAry, morphAry) // see algorithm below AryToFile (morphAry, erodeOutFile) prettyPrint (morphAry, prettyPrintFile) // write a meaningful caption before prettyPrint step 8: zero2DAry(morphAry, numImgRows, numImgCols) ComputeOpening (zeroFramedAry, morphAry, tempAry) // see algorithm below AryToFile (morphAry, openingOutFile) prettyPrint (morphAry, prettyPrintFile) // write a meaningful caption before prettyPrint step 9: zero2DAry(morphAry, numImgRows, numImgCols) ComputeClosing (zeroFramedAry, morphAry, tempAry) // see algorithm below AryToFile (morphAry, closingOutFile) prettyPrint (morphAry, prettyPrintFile) // write a meaningful caption before prettyPrint step 10: close all files ******************************* V. ComputeDilation (inAry, outAry) ******************************* // process dilation on each pixel in the entire zeroFramedAry step 1: i rowFrameSize step 2: j colFrameSize step 3: if inAry [i,j] > 0 dilation (i, j, inAry, outAry) step 4: j++ step 5: repeat step 3 to step 4 while j < (numImgCols + colFrameSize) step 6: i++ step 7: repeat step 2 to step 6 while i < (numImgRows + rowFrameSize) ******************************* VI. ComputeErosion (inAry, outAry) ******************************* // process dilation on each pixel in the entire zeroFramedAry step 1: i rowFrameSize step 2: j colFrameSize step 3: if inAry[i,j] > 0 erosion (i, j, inAry, outAry) step 4: j++ step 5: repeat step 3 to step 4 while j < (numImgCols + colFrameSize) step 6: i++ step 7: repeat step 2 to step 6 while i < (numImgRows + rowFrameSize) ******************************* V. ComputeClosing (zeroFramedAry, morphAry, tempAry) ******************************* step 1: ComputeDilation (zeroFramedAry, tempAry) step 2: ComputeErosion (tempAry, morphAry) ******************************* V. ComputeOpening (zeroFramedAry, morphAry, tempAry) ******************************* step 1: Compute Erosion (zeroFramedAry, tempAry) step 2: ComputeDilation (tempAry, morphAry)
Year 2 Integrated Business Functions (2025 Spring Term) Module 6: Financing for Growth Assignment 1 (Individual) This is an INDIVIDUAL assignment. This assignment is marked out of 100. It is worth 20 marks of the total course scores (i.e., 600 marks). INSTRUCTIONS: Please read the instructions carefully before attempting the Assignment. 1. Submission Due Date ● 28 February 2025 (Friday) before 5:00 pm. Please submit your final answers by uploading them on OLE (electronic submission). ● No extension of the submission due date will be allowed. 2. Assignment Submission As a mechanism to maintain academic integrity, you are required to submit soft copies of your assignments, as explained below: • You should upload a soft copy of the assignment to the OLE of the course by 5 pm on the submission due date. Files uploaded to the OLE should be prepared in Microsoft Word. Please refer to the Quick Start Guide for the submission of assignments to Turnitin. During submission, you will also need to declare whether and how you have used generative AI when completing the assignments. • You do not have to submit a hard copy of your assignments. If circumstances arise making it necessary to adjust the arrangement, further announcement will be made as soon as possible. • 10% of the marks awarded to the assignment will be deducted for each calendar day it is overdue until the soft copy ofthe assignment is submitted. 3. ANSWER ALL THE QUESTIONS 4. Plagiarism All assignments will undergo plagiarism check. Plagiarism involves copying from another source without acknowledgement. You should make sure all sources you used in the assignment are properly referenced, you also need to acknowledge on the OLE the ways you use Generative AI in the process of undertaking your assignments. Even there is proper referencing, you should not make excessive use of the words composed by others. Penalty will be applied if plagiarism is confirmed. Sources of information and references must be stated in the format of APA Style. (7th edition) created by the American Psychological Association. Training on the format of stating source of information (reference) will be given to you prior to the submission due date. You must follow strictly the format as stated below. No marks will be given for the part(s) that is/are copied from the works of others without stating the source of reference. You should follow the guideline, “Academic writing: Acknowledging your sources” on the OLE to avoid plagiarism. Question 1 (30 marks) (a) Describe the main components of personal financial statements which include the personal balance sheet and cash flow statement. Illustrate the main purposes of these personal financial statements in the context of personal financial planning. (6 marks) (b) Follow the template and examples provided in Unit 1, Part 2 - "Money Management Skill" of the custom textbook, construct the personal balance sheet and monthly cash flow statement for Mr. Lee utilizing the information recorded as of March 31, 2025: (12 marks) Monthly take-home salary in March 2025 = $60,000 Assume the average salary tax rate for Mr. Lee is 12% Cash on hand $3,000 $100,000 deposit in bank saving account, with annual interest rate of 1.8% Self-occupancy property with market value of HK$5 million and outstanding mortgage of HK$3 million Monthly mortgage payment $18,000 Management fee of property $1000 Mobile phone bill $200 Electricity and water bills $2000 A year 2022 BMW car with original purchase price of $300,000. The current market is depreciated by 20%. The automobile loan for this car is $160,000 Car-park monthly rent $3,000 Monthly auto-loan payment $5,000 Unpaid rates & government rent for property $2,500 Bank credit cards outstanding balance $50,000 Whole-Life Insurance monthly payment $3,000 Food and beverage $8,000 Buy new clothing $3,000 Jewelry purchased in Jan 2025 worth $50,000 Rolex Watch purchased in 2024 worth $60,000 Public transportation $500 Entertainment $2,500 Medical expense $1,000 Other expenses $2000 Balance of pension fund = HK$250,000 All the surplus is used for saving in this month (c) According to the formulae provided by P.47 of the custom textbook, calculate the following financial ratios for Mr. Lee and provide some analysis. Debt Ratio Current Ratio Liquidity Ratio Debt-Payment Ratio (include mortgage) Debt-Payment Ratio (exclude mortgage) Saving Ratio (12 marks) Question 2 (30 marks) (a) Visit the website of the Hong Kong Association of Banks (HKAB) to determine the HIBOR rates for 1 month and 12 months as of 8 January 2025. Please round the figures to one decimal place (i.e., A.B%) and use these numbers for the calculations in Questions 2(b) through 2(d). (2 marks) (b) Susanna has taken out a personal loan of $300,000 from a bank. The interest rate is calculated as the 1-month HIBOR rate from 8 January 2025 plus 3%. The loan is to be repaid with monthly payments over three years, with the payments scheduled for the end of each month. Calculate the monthly payment amount for this loan. (6 marks) (c) ABC Company has issued a 20-year bond with a coupon rate equal to the 12-month HIBOR (as of 8 January 2025) plus 1.2%. This bond has a face value of $1,000 and pays interest semiannually. If the yield to maturity (YTM) ofthis bond is 5%, what is its current price of the bond in dollars? (6 marks) (d) With respect to the 20-year bond issued by ABC Company referenced in Question 2(c), is it being sold at a premium or a discount? What can you deduce about the relationship between the coupon rate and the yield to maturity (YTM) for bonds sold at a premium? Explain why some bonds are sold above their par value at a premium, while others are sold below it at a discount. (8 marks) (e) If you are the CFO of a company and responsible to issue a bond, how would you determine the suitable coupon rate for the bonds? Please also explain the difference between the coupon rate and the required return on a bond. (8 marks) Question 3 (40 marks) (a) Determine the amount of Tencent's (700.HK) dividend payment for the year 2023 by checking AAStocks or the announcement from HKEXnews released on 20 March 2024. (5 marks) (b) Based on the dividend payment from Tencent in 2023 mentioned in Question 3(a), if you intend to invest in Tencent in 2024 with an expected return rate of 4% and anticipate a steady annual dividend growth of 3%, determine the current stock price by applying the dividend growth model formula. (5 marks) (c) Another company has recently issued a dividend that is $0.1 higher than Tencent's dividend payment mentioned in Question 3(a). This company plans to achieve a rapid dividend growth rate of 10% over the next three years, after which the growth rate will stabilize at a steady 5%. Given a required rate of return of 8%, determine the current share price using the dividend non-constant growth model. (10 marks) (d) Some companies listed on the HKEx do not pay dividends. What factors might lead a company to decide not to pay dividends? Why are some investors still willing to purchase shares of companies that do not offer dividends? (10 marks) (e) Is it possible for a company distribute dividends even if it reports a negative net income for the year? What reasons might the company's directors have for choosing to pay dividends despite this negative net income? (10 marks)
Java Lab7 Fall 2022 In this lab, you will practice with methods. 1. Create a project named Lab7 with a class named Lab7Main. Copy the file "paPop.csv" from Canvas into your main project directory. This file is a comma-separated value (CSV) file that contains information about the population density of Pennsylvania over a range of years. The format is , one set per line, where year is an integer and density is a double.2. Create a class named YearPop that contains two fields: int year and double pop. It should have an overloaded constructor that sets the member data, and it should have getters for the data (but not setters). 3. Lab7Main should have this member data: - a File object named myfile, set to null; - a Scanner object named fileScanner, set to null - an ArrayList named data to hold the file data, set to null Create these methods in Lab7Main (Note: except for main(), these are *not* static methods. Use regular methods.): - boolean openFile(filename) that takes a String parameter called filename and new's up myfile using filename. Then, in a try-catch block, as we've done in other code, new up fileScanner with myfile. If that fails, display an error message and return false (instead of calling exit( ) like we did before), otherwise return true. - YearPop makeData(line) that takes one String parameter named line in the CSV format above, splits it, creates a new YearPop object with that data in it, and returns that object. - void createList( ) should new up data; use a loop to read lines from the data file, one at a time; call makeData on each line; then place the returned YearPop object into the data ArrayList. - double findYear(year) should look for year in the ArrayList data; if it finds it, return the population density; if not, return -1.0 (an error code). - main( ): new-up a Scanner object for reading from the keyboard; new-up a Lab7Main object called lab and call openFile( ) to open the data file; call createList( ) to read the data; prompt the user for a year; use findYear( ) to get the population density and display it like this: Year: 1908 Population density: 165.073 then ask the user if they want to look up another (use Y or N) – loop until the user enters N. 4. This has nothing to do with the rest of the lab; it's just recursion practice. Write a static recursive method with this signature: public static int computeFibonacci(int first, int second, int n) that computes the n'th entry of the Fibonacci sequence, which is (normally) 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … This is generated by starting with two integers (normally 0 and 1), adding them together to get the next value (1), adding those next two to get the next value (2), and so on. So if the program calls computeFibonacci(0,1,7) it should return 13 (counting from 0, of course), and you should display: Fibonacci #7 = 13 The call could set first and second to anything, but always call it with 0 and 1 to keep things simple; try it out with different values of n. The stopping condition is: when the parameter n is 0, just return first, but for some larger value of n, compute the n-1'th Fibonacci number by recursion. Note: this is a pretty common problem, so you *could* find the solution on the web, but don't – try to code this to get some practice with recursion. You might want to print the values of the parameters for debugging purposes. Deliverable: Add your name and Andrew id to the comment at the top of the LabMain.java file. Upload the file to Canvas (no need to upload YearPop.java).
