IMPORTANT: This message is going to be really damn long. To ensure that you received the whole thing, scroll to the end and make sure that you can read the line: "If you can read this, you got the whole message." Tim Kerby wrote: > What is the difference between 2s complement, logical complement and > complement (NOT) and any others? Tim: Let's do the easy one first. LOGICAL COMPLEMENT: ------------------- Glossary note: In this message, "==" should be read as "is equal to", and "!=" should be read as "is not equal to". Ok... Logical expressions ("p == q", "1 == 0", "x > 3", etc.) are either TRUE or FALSE. The logical complement (NOT) of an expression simply inverts its true/false state. For example: "1 == 0" is FALSE. "NOT (1 == 0)" is TRUE. Often, logical expressions of the form "x != 0" are expressed in a shorthand form: They're simply written "x"; the "!= 0" is implied. For example: "123" is TRUE. "NOT (123)" is FALSE. "0" is FALSE. "NOT (0)" is TRUE. If x != 0, "x" is TRUE and NOT (x) is FALSE. Ok... Now the harder ones: One's Complement" and Two's Complement. Before you can understand much about this, you need to have some idea of how things work inside the PIC, so we'll digress a bit into the realm of microprocessor ALU design. BUILDING AN ADDER: ------------------ Let's say that you're designing a microprocessor. Your employer, like most VLSI semiconductor vendors, values efficient design over all else... All of your circuitry must be built with the fewest possible number of logic gates. You're assigned the task of designing the ALU (Arithmetic Logic Unit) and today you're designing the portion of the circuit that adds two binary numbers together. For simplicity, let's say that each input is only one bit wide, and that you want only a single-bit output (we'll evolve it to a full 8-bit adder with carry-in and carry-out shortly). You have a whole handful of logic gates (we'll cheat a bit and say that you have AND, XOR, OR, and NOT gates, even though XOR and OR can be built from AND and NOT)... How do you build this single-bit adder with the smallest number of parts? The first thing to do is draw the Truth Tables for the gates you have. Here's the one for NOT: A | NOT (A) ___|________ 0 | 1 1 | 0 What this truth table says is that if you input a "0" to a NOT gate, it outputs a "1", and if you input a "1", it outputs a "0". The truth table for AND gates is similarly constructed, but the "AND" function takes TWO inputs (which we'll call "A' and "B"), so there are four possible input combinations rather than two: A | B | A AND B ___|___|_________ 0 | 0 | 0 0 | 1 | 0 1 | 0 | 0 1 | 1 | 1 The AND function works the way you'd expect it to: If A and B are BOTH true (1), the result is also true; otherwise, the result is false (0). The OR and XOR gates each take two inputs, as well: A | B | A OR B A | B | A XOR B ___|___|________ ___|___|_________ 0 | 0 | 0 0 | 0 | 0 0 | 1 | 1 0 | 1 | 1 1 | 0 | 1 1 | 0 | 1 1 | 1 | 1 1 | 1 | 0 "OR" is pretty straightforward: If either A or B (or both) is true, the output is true. "XOR" ("exclusive-OR") is only slightly more complicated: If A or B (but not both) is true, the output is true. Where were we? Oh, yeah... We were building a single-bit, no-carry adder. Ok. Draw the truth table for the "add two single-bit numbers A and B and output a single-bit result" operation: A | B | A + B ___|___|_______ 0 | 0 | 0 0 | 1 | 1 1 | 0 | 1 1 | 1 | 0 Check it out... THIS truth table looks just like the "XOR" truth table. To perform this simple addition, therefore, you just need one XOR gate; your two single-bit inputs go in, and the result comes out. We'll write this as: Sum = A XOR B. Now, look at the addition table again. The first three results seem ok, but everyone knows that 1 + 1 does NOT equal 0; it equals 2. "2" is represented in binary by "10", a two-digit number. Just as in decimal addition when we're asked to add 5 + 5, we need to output "0" and "carry the one". Since we were specifically told to build an adder with just a single-bit result, we can be forgiven for only outputting the rightmost bit, but in the real world, we're going to need some way of carrying a "1" bit out of our sum whenever the result is too large to fit in 1 bit. So... Draw another, expanded, truth table, showing both the single-bit result and the carry out of the sum: A | B | A + B | Cout ___|___|_______|_____ 0 | 0 | 0 | 0 0 | 1 | 1 | 0 1 | 0 | 1 | 0 1 | 1 | 0 | 1 At this point, if you've been paying attention, you should immediately notice that the "Cout" column looks exactly like the "AND" truth table above. Go back and check it... See? 0, 0, 0, 1. What does this mean? It's simple: To add two one-bit numbers and get a single-bit result and a carry, you need to feed your two inputs into an XOR gate to get the sum, and simultaneously feed the two inputs into an AND gate to get the carry-out: Sum = A XOR B. Cout = A AND B. If we examine our output now that we've added the Carry-Out, we se that it's correct: 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0, carry the 1. This is all well and good for a single-bit adder, but we usually deal with numbers that are 8 bits wide. Can we just string eight of these two-gate adders together and have each one operate on one pair of bits? Well, yes, but we need to do something with that carry-out bit. Specifically, we need to add each one-bit-adder stage's carry-out bit to the next stage's output. While we're at it, we'll want to add a carry-IN bit to the first stage, to make it easy for the guy who's eventually going to buy our microprocessor to perform additions on numbers that are larger than 8 bits. Of course, carrying a "1" into our addition will change our result, and the state of our carry-out bit will now be dependent not only on the A and B inputs, but also on the carry-in bit, which was similarly dependent on the PREVIOUS stage's inputs and carry-in bit, which was dependent on the stage before IT, which was... It's all starting to get complicated now, so let's break the problem into two smaller pieces: 1) Properly handling the sum of A, B, and the carry-in bit, and 2) Properly setting the carry-out bit. Let's do the carry-in ("Cin") first. Think about what we're trying to do: We're going to add A and B together, then add the result to Cin. As we discovered earlier, addition (if you ignore the carry-out, which we're doing for now) is equivalent to XOR: A + B = A XOR B. It doesn't take much of a stretch to see that A + B + Cin, therefore, equals (A XOR B) XOR Cin. We can test this with yet another truth table; this one has eight combinations of three inputs (Cin, A, and B), and shows the results of three oerations on those inputs: Cin | A | B | A XOR B | (A XOR B) XOR Cin | A + B + Cin ____|___|___|_________|___________________|____________ 0 | 0 | 0 | 0 | 0 | 0 0 | 0 | 1 | 1 | 1 | 1 0 | 1 | 0 | 1 | 1 | 1 0 | 1 | 1 | 0 | 0 | 0 1 | 0 | 0 | 0 | 1 | 1 1 | 0 | 1 | 1 | 0 | 0 1 | 1 | 0 | 1 | 0 | 0 1 | 1 | 1 | 0 | 1 | 1 Yep... Acording to the truth table, "(A XOR B) XOR Cin" produces exactly the same results as "A + B + Cin". Cool. Now we deal with the carry-out. This is going to take a little more thought. Remember that, back in simpler times when we were just adding A and B without a carry-in, the carry-out was just equal to A AND B. Let's start by assuming that our final carry-out bit will be equal to that simple carry-out, then figure out what circumstances can change it. Ok... Truth-table time again. In this case, we're going to draw a table that tells us whether we need to change the "simple carry-out" (A AND B) to get our final carry-out. This truth table shows two inputs ("A + B" and "Cin") and one output (whether or not to change the simple carry-out bit): A + B | Cin | Change? ______|_____|________ 0 | 0 | No 0 | 1 | No 1 | 0 | No 1 | 1 | Yes You might want to take some time working out simple examples to verify that the above truth-table is actually correct. If you replace the "No" and "Yes" entries with "0" and "1", this table looks just like the "AND" truth-table, so we can start to express our carry-out logic as: Step #1: Calculate a simple carry-out by ANDing the two inputs. Step #2: AND A + B with the carry-in. If the result is 1, invert the simple carry-out bit; otherwise, leave it unchanged. Hang on... We're almost done; all we need to do now is figure out how to express Step #2 in terms of logic gates. If you go way back and look at the "XOR" truth table, you'll see that it seems to do just what we want: If input A is 1, the output is the inverse of input B; if input A is 0, the output is equal to B. If we make the XOR gate's "A" input equal to "(A + B) AND Cin" (which we know is equal to "(A XOR B) AND Cin"), and we make the XOR gate's "B" input equal to the simple carry-out ("A AND B"), we can put this all together and get: Carry-out ("Cout") = [(A XOR B) AND Cin] XOR [A AND B]. So... The total description of our "single-bit adder with carry-in and carry-out" circuit is: Inputs: A, B, Cin. Outputs: Sum = (A XOR B) XOR Cin. Cout = [(A XOR B) AND Cin] XOR [A AND B]. The "A XOR B" term that appears in both equations is just a single XOR gate whose output is split, so this circuit requires only two AND gates and three XOR gates. You can cascade as many of these 5-gate single-bit adder stages as you want; building a complete 8-bit adder requires only 40 gates (or 41 if you want to provide an "overflow" flag). Whew. SO WHAT THE HELL DOES THIS HAVE TO DO WITH 1'S- AND 2'S COMPLEMENT? ------------------------------------------------------------------- Glad you asked. I'll answer this in the next message, since I'm running out of room in this one. -Andy If you can read this, you got the whole message. === Andrew Warren - fastfwd@ix.netcom.com === === Fast Forward Engineering - Vista, California === === === === Did the information in this post help you? Consider === === contributing to the PICLIST Fund. Details are at: === === http://www.geocities.com/SiliconValley/2499/fund.html ===