diff options
author | lshprung <lshprung@yahoo.com> | 2020-10-16 10:28:33 -0700 |
---|---|---|
committer | lshprung <lshprung@yahoo.com> | 2020-10-16 10:28:33 -0700 |
commit | a7e6070ffab93d3fc80345604464f28d9ebbf724 (patch) | |
tree | 61ee0354cac1ec12ae858eee56348ee556583e7c | |
parent | 15e38ea0c10e039aa1c6cf4a20fa15116393faf1 (diff) |
Post-class 10/16
-rw-r--r-- | 10.md | 4 | ||||
-rw-r--r-- | 11.1.png | bin | 0 -> 17108 bytes | |||
-rw-r--r-- | 11.2.png | bin | 0 -> 12498 bytes | |||
-rw-r--r-- | 11.3.png | bin | 0 -> 37674 bytes | |||
-rw-r--r-- | 11.4.png | bin | 0 -> 7976 bytes | |||
-rw-r--r-- | 11.md | 145 |
6 files changed, 149 insertions, 0 deletions
@@ -181,3 +181,7 @@ - We are learning things in the context of underlying circuit implementations - We have learned how to build an adder, not a subtractor - When you need to show subtraction, you \*must\* negate and add + +--- + +[Overflow, Comparison, ALU ->](11.md) diff --git a/11.1.png b/11.1.png Binary files differnew file mode 100644 index 0000000..06e8298 --- /dev/null +++ b/11.1.png diff --git a/11.2.png b/11.2.png Binary files differnew file mode 100644 index 0000000..7cf0884 --- /dev/null +++ b/11.2.png diff --git a/11.3.png b/11.3.png Binary files differnew file mode 100644 index 0000000..2e9921b --- /dev/null +++ b/11.3.png diff --git a/11.4.png b/11.4.png Binary files differnew file mode 100644 index 0000000..5c63f28 --- /dev/null +++ b/11.4.png @@ -0,0 +1,145 @@ +[\<- Signed numbers and subtraction](10.md) + +# Overflow, Comparison, ALU + +## Overflow + +- Remember, signed numbers, and hardware computation units, have a fixed number of bits +- What happens if the result of the addition/subtraction needs more than the available bits? +- Need to detect this condition. What happens next depends on the "system" in which the circuit is implemented + +### Determining Overflow + +- Adding two numbers with the same "sign" should not yield a result with the opposite sign + +![diagram](11.1.png) + +### HW detection of overflow + +- As humans, we can look at the sum of two numbers and see whether there's overflow +- A HW circuit, like a 4-bit adder, needs a way to "flag" whether the result is valid + - The carry-in to the sign bit position (C3) should match the carry-out (C4) +- Overflow = C3 ^ C4 (for a 4-bit adder) + - C7 ^ C8 for an 8-bit adder + - Remember: `^` is XOR +- Note: adding a negative and positive number can never overflow + +### 8-bit signed addition example + +- Computation of 0xDA + 0xAB + - Two negative 8-bit numbers + +![diagram](11.2.png) + +- No overflow: C7 == C8 + - Even though C3 != C4 +- It's the sign bit that we care about! + +--- + +## Comparison + +### Comparators + +- Often it's usefule to detect comparisons + - `==`, `>`, `<`, `!=`, `>=`, `<=` + - "Answer" is true/false, yes/no, 1/0 +- XOR gates provide an easy means to determine if two bits are equal (`==`) + - Apply to each bit position and OR the results + - A 1 means the bits don't match => inequality +- For unsigned `>` or `<`, start at the MSB (most significatn bit) and find the first mismatch + - Really only practical for small # of bits + +### Signed Comparison + +- Subtract the numbers (A-B) and check the result + - Three mutually exclusive possibilities + - A-B > 0 => A>B + - A-B = 0 => A=B + - A-B < 0 => A<B +- We already have a sign bit for the result + - Can be used to determine A-B<0, but doesn't differentiate the other two possibilities + - Need to add a zero-detect + +--- + +## Interpreting overflow when doing comparison + +- Since we don't need the actual result of the subtraction, we can use overflow + - It doesn't matter that the computed result is wrong +- Negative overflow + - Adding two negatives, sign bit of result is 0 + - Should be 1, can be interpreted as a negative +- Positive overflow + - Adding two positives, sign bit of result is 1 + - Should be 0, can be interpreted as positive + +--- + +## ALU concept and example + +### Arithmetic Logic Unit (ALU) + +- Abstraction layered on top of an adder + - Used for any number of operations that generate a result based on two inputs +- Operands (A and B) and a "command" + - We've already seen this for subtraction +- Output is either a computation ro a comparison result + - For comparison type command, output is 1 for true, 0 for false (it's a yes/no question) + +### Example ALU + +- Limit ourselves to add, subtract, and comparison +- An example 2-bit command (F1, F0) + - 00 means add + - 01 means subtract + - 11 means "set on less than" + - i.e. "true or false: A is less than B" +- Not that we're not using the encoding 10 just yet + - You'll be filling this in as a homework problem + +### Example ALU block diagram + +- F1, F0 decoded to generate controls + +![diagram](11.3.png) + +--- + +## Comparison logic + +- Assumes that the decode of F1 and F0 will cause Subtract to be asserted +- Define a signal called LT (for Less Than) to tell us "yes, A is less than B" +- Using Sum and OVF, when whould LT be true? How do we know A-B<0? + +|S3 OVF|LT| +|------|--| +|00 |0 | +|01 |1 | +|10 |1 | +|11 |0 | + +- For this first example, where the only comparison is "less than": + - The "Subtract" signal is just F0 + - The "Comparison Type" input isn't needed + - The "True/False" output is just LT +- Adding another comparison command would require use of the "Comparison Type" signal to select what value to put on the "True/False" output + +--- + +## Result Selection + +### Selecting final result + +- If command is specifying add or subtract, result should be output of adder +- If command is specifying a comparison, result should be either 0001 (true) or 0000 (false) + - Bits 3,2,1 are 000 in either case, bit 0 is output of comparison logic +- How to choose between these results? + - What circuit do we use for a choice? + +### Result selection circuit + +- RT = Result Type +- T/F = True/False + +![diagram](11.4.png) |