logism代写 CS2630: Computer Organization Homework 4

CS2630: Computer Organization Homework 4 Combinational logic

Instructions: You must submit your files to Assignments > Homework 4 on ICON. Make sure your circuits run successfully, and make sure to test them on multiple inputs.

The files to submit are: • popcount.circ
• graycode.circ
• subtractor.circ

For each circuit file, you are responsible for following this checklist: o thefilenameiscorrect

o inputandoutputportsarenotmodifiedinanyway(otherthanconnectingawire to them, of course)

o you’vetestedyourcircuitasdescribed

Goals for this assignment

• Translate between truth tables, Boolean algebra, and logic circuits
• Use hierarchy to organize digital logic circuits
• Build and test more complex digital components like encoders, circuits using shifters,

  and arithmetic

1. Popcount is a function to count the number of 1’s in the input. Among many other things, popcount can be used to help calculate Hamming Distance, one way to measure the difference between two vectors, a common operation in clustering algorithms. Build 3-input popcount in popcount.circ. Note that there are two outputs. Here are truth tables for o2 (two’s bit of count) and o1 (1’s bit of count) shown as one combined table.

2. As you know, counting up in base two requires changing multiple bits at the same time, particularly when you hit the next power of two. In systems that are sensitive to the timing of these transitions. For example, when counting from 3 to 4, base two goes 011 to 100. If any of those three bits flipped earlier than the others, we would temporarily see numbers other than 3 or 4. It would be preferable to have a counting system where only one bit changes at each increment. This idea is called a gray code.

There are many gray codes, but the most common is traditional one is that the Kth value is K ^ (K>>1), where ^ means XOR.

For example with 4-bit numbers:

Here is an algorithm for converting a gray code to base two from Hank Dietz’s The Aggregate Magic Algorithms.

   int g2b(int gray)
   {

}

gray = gray ^ (gray >> 16); // >> mean shift right logical
gray = gray ^ (gray >> 8);  // ^ means xor
gray = gray ^ (gray >> 4);
gray = gray ^ (gray >> 2);

gray = gray ^ (gray >> 1);
return gray;

You will build a 32-bit gray code to base two converter. Along the way, you will learn how to use subcircuits in Logisim.

a) Put your implementation in graycode.circ. Now, you will build the converter, using as many Shifter components as you need to (under Arithmetic | Shifter and configure its Shift Type to Logical Right). You must use the algorithm shown in the pseudocode above. To get constants in your circuit (you need 16, 8, 4, 2, 1), you can use the Constant component under Wiring. You can configure a Constant’s bitwidth and value.

This diagram shows Logisim’s tooltips for each input/output port of the Shifter component.

b) Using the poke tool, test your graycode circuit on a variety of inputs so that you have evidence the circuit works. You should generate those test cases by running the pseudocode in your favorite programming language with some test inputs.

You are about to modify your working circuit. Therefore, this is a good time to make a backup copy of the graycode.circ file.

Okay, so using something as sophisticated as the variable-shift-amount Shifter in Logisim without knowing how it works feels unsatisfying. Now you will replace the Logical Right Shifters with your own.

c) Click Project > Add circuit and for Circuit Name put “LogicalRightShifter”. You’ll now see that there are two circuits in your file

Add to LogicalRightShifter a 32-bit input labeled “in”, a 5-bit input labeled “amount”, and a 32-bit output labeled “out”.

d) Build the circuit so that out = in >> amount. The shift should be shift right logical. You may use shifters (found in the Arithmetic folder) but only with

a constant for the Distance input. You can find constants under the wiring folder. Here are some examples of Shifters with shift amount constant 1 and 2.

You might use answers in Team: Adders, Shifters Multipliers as inspiration. Note that the splitter is located under wiring. Fan Out means the number of wires to split into and Bit Width In means the number of bits on a wire.

5. e)  Using the poke tool, test your out=in>>amount circuit on various inputs.
6. f)  Now go back to your main circuit.

   Replace all the Shifters with your own LogicalRightShifter. To place a LogicalRightShifter in your main circuit, single-click LogicalRightShifter to highlight it, then bring your mouse over to the editing area. It should look something like this (your editing area will of course have the existing Gray circuitry in it, also).

Figure 1: main circuit is selected; showing Input and BaseTwo ports with a LogicalRightShifter placed in the editing area.

g) Test your graycode circuit again to make sure it still works.

More documentation on subcircuits is available at

http://www.cburch.com/logisim/docs/2.7/en/html/guide/subcirc/index.html

3. Build a 3-bit two’s complement subtractor from only basic logic gates (OR, NOR, AND, NAND, NOT, XOR, XNOR). Your circuit should go in subtractor.circ.

• Your solution must be based on the idea of a 3-bit ripple carry adder.
• To reduce duplication and effort, we suggest you use subcircuits. Build the 3-bit

ripple carry adder out of multiple 1-bit adders. The 1-bit adder should be in a

subcircuit called “adder1bit”.
• Notice that subtractor.circ includes a reference implementation to test yours

against.

General tips

• Orange wires and the Width Mismatch error message indicate that you are connecting two ports with differing bitwidths. Figure out what bitwidth you expect the wire to be and check the configurations of both components. For example, I connected this constant and Shifter and got an error message.

Let’s say I wanted the wire to be a 3-bit wire. The Shifter is already 3 bits, but my constant is just 1 bit. So, I click the constant to configure it and change its Data Bits from to 3.