Post by noodlesoup on Jul 24, 2011 21:15:49 GMT
In this thread I will explain:
Counting In Binary
The binary number system only has 2 numbers, like how decimal has 10. In decimal, once you hit one more than the highest number that could be in a digit (10), you reset that digit to 0 and increase the amount of the digit left of it by 1 (e.g. 19 → 20). In binary, it's the same thing, except this all happens once you pass 1 in a digit. Here is a table showing the 1st ten numbers from 0 in decimal and in binary:
How to Read Binary
Bit = Binary Digit
As in decimal, every bit in a binary number is of a higher order of magnitude than the one to its right. Look at the number 357 and you will see that it is (7 x 10^0) + (5 x 10^1) + (3 x 10^2). Everything in binary is the same, except that instead of each number one place to the left having 10 times more magnitude than the one to its right, they have only twice as much. Look at the number 1011 (One-zero-one-one, not one-thousand and eleven), it is really (1 x 2^0) + (1 x 2^1) + (0 x 2^2) + (1 x 2^3), or 13 in base-10(decimal). Therefore, to find the decimal equivalent of a number expressed in binary, multiply the rightmost bit by 2^0, then the next bit to the left by 2^1, then the next bit to the left by 2^2, and so on.
Example:
00110101 =
 1 x 2^0 = 1
 0 x 2^1 = 0
 1 x 2^2 = 4
 0 x 2^3 = 0
 1 x 2^4 = 16
 1 x 2^5 = 32
 0 x 2^6 = 0
+0 x 2^7 = 0 
           53
Converting Decimal to Binary
To convert your basic decimal number into binary, continually divide it by 2 while writing out the remainders, then put all the remainders together. For example:
The number 13 in binary:
13 / 2 = 6 Remainder 1
06 / 2 = 3 Remainder 0
03 / 2 = 1 Remainder 1
01 / 2 = 0 Remainder 1
The remainders (from bottom to top) are 1, 1, 0, and 1. Therefore 1101 is 13 in binary.
Binary Arithmetic
The four arithmetic operations are addition, subtraction, multiplication, and division. They all work in the same way in binary as they do in decimal.
Addition
In 2-number decimal addition, you first added a digit in the one's place with the digit in the one's place right below it to get a sum. If the sum was 10 or over (because decimal is base-10), you carried a 1 to the column of digits directly to the left. In binary the principle is the same, only that to carry a 1, you must have a sum of 2 (because binary is base-2).
Examples:
Carries:  1
Addend:   01
Addend: + 01
Sum:      10
Carries:   1111
Addend:   10100101
Addend: + 10011110
Sum:     101000011
Subtraction
In decimal subtraction, if the digit being subtracted was more than the digit being subtracted from, you borrowed from a positive digit in a higher place-value to add 10 (ten) to your digit being subtracted from. In binary, the principle remains the same, but instead of adding ten, you add 10 (one-zero (two)).
Example:
   1
   1010
 1 0 0 1
-0 1 1 0
 0 0 1 1 = 11(binary) = 3(decimal)
Multiplication
There is one difference to binary multiplication and decimal multiplication, and that is since binary only has 1's and 0's, we can multiply a multiple-digit number by each digit of another multiple-digit number with ease.
Example:
Factors:             1011
                    x1101
Partial Products:    1101
                    11010
                        0
                 +1101000
Final Product:   10001111
Notice that an increasing amount of 0's are still added to the front of each partial product, as in decimal multiplication.
Division
When you go from decimal division to binary division, things are still pretty much the same. The hardest part is guessing how many times the divisor goes into the dividend, which is really just comparing one's from the left.
Example:
    1110.1 
10)111010 ←Place-holding zero
  -10↓││
    11││
   -10↓│
     10│
    -10↓
      010
     -10
       0
Boolean Logic
Boolean operations deal with 1's and 0's, and they are what you see implemented in logic gates. For these operations you have 2 variables, x and y, which can be true ('1' or 'on') or false ('0' or 'off'). The answer to a Boolean expression is also true or false. In terms of digital electronics, x and y can be seen as inputs, the operation can be seen as the logic gate, and the answer can be seen as the output.
These are some of the Boolean operations:
Negation (NOT)
Negation of xcan be written as NOTx. If x is true, then NOTx is false, and vice-versa.
In electronics, this is represented as a NOT gate. The state of the output is simply "NOT" what the state of the input is.
Conjunction (AND)
Conjunction of x and y can be written as x AND y. x AND y is true if and only if both x and y are true.
In electronics, this is represented as an AND gate. Its output is only on when both one input "AND" the other are on. The and operator also has an exact arithmetic counterpart: multiplication.
Negated/NOT AND (NAND)
Non-conjunction of x and y can be written as x NAND y. x NAND y is true if and only if both x and y are not true.
In electronics, this is represented as a NAND gate. Its output is only not on when both one input "AND" the other are on. A special property of this gate is that any other gate, and therefore any other logical device, can be made from different networks of only NANDs.
Disjunction
Disjunction of x and y can be written as x OR y. x OR y is true when one or (inclusively) the other input is on.
In electronics, this is represented as an OR gate. Its output is only on when one input "OR" (inclusively) the other are on.
Negated/NOT OR (NOR)
Non-disjunction of x and y can be written as x NOR y, and is only true when x or (inclusively) y are not true.
In electronics, this is represented as a NOR gate. Its output is only on when neither one input "NOR" (inclusively) the other are true. This gate shares the same property of the NAND gate, as any other gate can be made from networks of only NORs.
Exclusive OR (XOR)
"Antivalence" (opposite of equivalence) between x and y can be written as x XOR y, and is only true when x or (exclusively) y are true.
In electronics, this is represented by a XOR gate. Its output is only on when one output or (exclusively) the other are true. This gate has the property that if any one of its inputs change, its output will also change.
Negated/NOT XOR (XNOR) (Exclusive NOR)
Equivalence between x and y can be written as x XNOR y, and is only true when x and y are either both true or both false.
In electronics, this is represented by an XNOR gate. Its output is only on when the two inputs are either both on or both off. This gate also shares the XOR property that if any one of its inputs change, its output will change as well.
Implication (IMP)
An implication of y from x can be written as x → y (or you can simply write x Implies y), and is false only when x is true (implying y), but y is false. Note that x → y may not be the same as Cyx.
In electronics, this is represented by an OR gate with one negated input. Its output is only false when the negated input is on while the other input is off.
Arithmetic with Circuits
The four basic arithmetic operations + / - / × / ÷ can be made from the use of logic gates in circuits.
Addition
Addition can be done quite simply with a device called an adder.
Half Adder:
A half adder has 2 inputs: A and B, and is designed to add 2 bits (1's or 0's). The inputs A and B in a half adder can represent any bit, though in about all cases, they represent the least significant bit (the bit whose decimal value is 1 or 0), since a 1 cannot be carried into a half adder from a previous addition calculation. This makes them suitable for being the first, and only the first, adder in a connection of multiple adders to add larger numbers. To read the output, assign S (sum) as the least significant bit, and C (carry out) as the next bit to the left.
Full Adder:
A full adder has 3 inputs: A, B, and Cin (carry in). It also has 2 outputs: S (sum) and Cout (carry out). All 3 inputs are of the same order of magnitude and are added together.
N-Bit Adder
N-Bit adders work using multiple full adders set up in a way such that each adder's Cout connects with the next adder's Cin. This allows N adders to be able to calculate the sums of 2 N-bit numbers. It is okay for the first adder be a half-adder, since there is no carrying from the adder before it (as there is no adder before it).
4-Bit Adder
Subtraction
It is possible to fashion a logic circuit that subtracts numbers using regular subtraction; however, one can be made using adders so that building a new circuit can be avoided. These types of circuits that can be used both as an adder and subtractor are called adder-subtractors. To subtract two binary numbers this way, a different method of subtraction must be used. Let's say we had a - b, where both a and b were in binary. Look at b and invert its digits, then add 1. Add that number to a and you have your answer, which will be in two's complement notation. To find the value of a number in two's complement notation, look at the most significant bit: if it is a 0, the number will be positive and can be read normally, but if it is a 1, the number is negative and to get the absolute value you must invert it and add 1.
Example:
3 - 7
 011 (3)  a=011
-111 (-7) b=111 → Invert all bits and add 1 → 001
 011
+001 ← Add modified b to a
 100  ←see that most significant bit is 1 and realize answer is negative. Invert number (turns to 011) and add 1 (turns to 100).
-100, or -4, will be your answer.
Also, here is a table comparing numbers in two's complement to regular binary numbers to decimal:
To modify adders to output numbers in this notation, you must attach an XOR gate to one input of each adder then make a wire that inputs into each XOR gate and the Cin of the adder. To use, the negative term must be inputted into the XOR gates and positive number must be inputted directly into the adders. The circuit should look like this:
The Control input controls whether the circuit will add or subtract. When it is off, the circuit works exactly like an adder, but when it is on, it inverts all B inputs and adds 1 via the Cin input.
Multiplication
Multiplication in circuits can be easily done in a way that mirrors long multiplication. Using n - 1 adders, you can multiply 2 n-bit numbers. Let's take a look at what a binary multiplier does:
Example:
    1111 (15)
   ×1001 (9)
   01001 ⇦ 01001* 1001 × the rightmost bit of 1111
  +1001│ ⇦ 1001 (shifted 1 bit left (10010)) 1001 × 2nd bit from the right in 1111
  01101│ ⇦ 01101* adding the 2 products (0100 + 1001)
 +1001││ ⇦ 1001 (shifted 2 bits left (100100)) 1001 × 3rd bit from the right in 1111
 01111││ ⇦ 01111* is calculated by adding 0110 + 1001
+1001↓↓↓ ⇦ 1001 (shifted 3 bits left (1001000)) 1001 × 4th bit from the right in 1111
10000111 (135)
The 3 sets of colored numbers represent the 3 sets of numbers that would go into the 3 4-bit adders in a 4-bit multiplier.
*This rightmost bit is automatically sent as the next bit in the answer output and disregarded in adding operations. This is done because it can no longer be changed (it will only be added to 0's). A 0 (bold) is added before the number in order to make it a 4-bit number again.
So how would the schematics of a 4-bit binary multiplier look like?:
All inputs beginning with 'A' or 'B' represent a specific value of a bit of A or B. A4/B4 would be the most significant bit, and A1/B1 would be the least significant. The AND gates are labelled to show which inputs they are receiving. In the full adders, labels with lower numbers represent less significant bits. Also, inputs labelled '(0) False' are to always remain 0/off/false.
Division
[Unfinished]
- Counting in binary
- How to read binary
- How to convert decimal into binary
- How to perform binary arithmetic operations
- Simple Boolean operations (AND, OR, XOR...) (Logic gates)
- Logic gate symbols
- Arithmetic with circuits
Counting In Binary
The binary number system only has 2 numbers, like how decimal has 10. In decimal, once you hit one more than the highest number that could be in a digit (10), you reset that digit to 0 and increase the amount of the digit left of it by 1 (e.g. 19 → 20). In binary, it's the same thing, except this all happens once you pass 1 in a digit. Here is a table showing the 1st ten numbers from 0 in decimal and in binary:
Decimal | Binary |
0 | 0 |
1 | 1 |
2 | 10 |
3 | 11 |
4 | 100 |
5 | 101 |
6 | 110 |
7 | 111 |
8 | 1000 |
9 | 1001 |
How to Read Binary
Bit = Binary Digit
As in decimal, every bit in a binary number is of a higher order of magnitude than the one to its right. Look at the number 357 and you will see that it is (7 x 10^0) + (5 x 10^1) + (3 x 10^2). Everything in binary is the same, except that instead of each number one place to the left having 10 times more magnitude than the one to its right, they have only twice as much. Look at the number 1011 (One-zero-one-one, not one-thousand and eleven), it is really (1 x 2^0) + (1 x 2^1) + (0 x 2^2) + (1 x 2^3), or 13 in base-10(decimal). Therefore, to find the decimal equivalent of a number expressed in binary, multiply the rightmost bit by 2^0, then the next bit to the left by 2^1, then the next bit to the left by 2^2, and so on.
Example:
00110101 =
 1 x 2^0 = 1
 0 x 2^1 = 0
 1 x 2^2 = 4
 0 x 2^3 = 0
 1 x 2^4 = 16
 1 x 2^5 = 32
 0 x 2^6 = 0
+0 x 2^7 = 0 
           53
Converting Decimal to Binary
To convert your basic decimal number into binary, continually divide it by 2 while writing out the remainders, then put all the remainders together. For example:
The number 13 in binary:
13 / 2 = 6 Remainder 1
06 / 2 = 3 Remainder 0
03 / 2 = 1 Remainder 1
01 / 2 = 0 Remainder 1
The remainders (from bottom to top) are 1, 1, 0, and 1. Therefore 1101 is 13 in binary.
Binary Arithmetic
The four arithmetic operations are addition, subtraction, multiplication, and division. They all work in the same way in binary as they do in decimal.
Addition
In 2-number decimal addition, you first added a digit in the one's place with the digit in the one's place right below it to get a sum. If the sum was 10 or over (because decimal is base-10), you carried a 1 to the column of digits directly to the left. In binary the principle is the same, only that to carry a 1, you must have a sum of 2 (because binary is base-2).
Examples:
Carries:  1
Addend:   01
Addend: + 01
Sum:      10
Carries:   1111
Addend:   10100101
Addend: + 10011110
Sum:     101000011
Subtraction
In decimal subtraction, if the digit being subtracted was more than the digit being subtracted from, you borrowed from a positive digit in a higher place-value to add 10 (ten) to your digit being subtracted from. In binary, the principle remains the same, but instead of adding ten, you add 10 (one-zero (two)).
Example:
   1
   
 
-0 1 1 0
 0 0 1 1 = 11(binary) = 3(decimal)
Multiplication
There is one difference to binary multiplication and decimal multiplication, and that is since binary only has 1's and 0's, we can multiply a multiple-digit number by each digit of another multiple-digit number with ease.
Example:
Factors:             1011
                    x1101
Partial Products:    1101
                    11010
                        0
                 +1101000
Final Product:   10001111
Notice that an increasing amount of 0's are still added to the front of each partial product, as in decimal multiplication.
Division
When you go from decimal division to binary division, things are still pretty much the same. The hardest part is guessing how many times the divisor goes into the dividend, which is really just comparing one's from the left.
Example:
    1110.1 
10)111010 ←Place-holding zero
  -10↓││
    11││
   -10↓│
     10│
    -10↓
      010
     -10
       0
Boolean Logic
Boolean operations deal with 1's and 0's, and they are what you see implemented in logic gates. For these operations you have 2 variables, x and y, which can be true ('1' or 'on') or false ('0' or 'off'). The answer to a Boolean expression is also true or false. In terms of digital electronics, x and y can be seen as inputs, the operation can be seen as the logic gate, and the answer can be seen as the output.
These are some of the Boolean operations:
- Negation (NOT)
- Conjunction (AND)
- Negated AND (NAND)
- Disjunction (OR)
- Negated OR (NOR)
- Exclusive OR (XOR)
- Negated XOR (XNOR)
- Implication (IMP)
Negation (NOT)
Negation of xcan be written as NOTx. If x is true, then NOTx is false, and vice-versa.
In electronics, this is represented as a NOT gate. The state of the output is simply "NOT" what the state of the input is.
Input | Output |
x | NOTx |
0 | 1 |
1 | 0 |
Conjunction (AND)
Conjunction of x and y can be written as x AND y. x AND y is true if and only if both x and y are true.
In electronics, this is represented as an AND gate. Its output is only on when both one input "AND" the other are on. The and operator also has an exact arithmetic counterpart: multiplication.
[cs=2]Input | Output | |
x | y | x AND y |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Negated/NOT AND (NAND)
Non-conjunction of x and y can be written as x NAND y. x NAND y is true if and only if both x and y are not true.
In electronics, this is represented as a NAND gate. Its output is only not on when both one input "AND" the other are on. A special property of this gate is that any other gate, and therefore any other logical device, can be made from different networks of only NANDs.
[cs=2]Input | Output | |
x | y | x NAND y |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Disjunction
Disjunction of x and y can be written as x OR y. x OR y is true when one or (inclusively) the other input is on.
In electronics, this is represented as an OR gate. Its output is only on when one input "OR" (inclusively) the other are on.
[cs=2]Input | Output | |
x | y | x OR y |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
Negated/NOT OR (NOR)
Non-disjunction of x and y can be written as x NOR y, and is only true when x or (inclusively) y are not true.
In electronics, this is represented as a NOR gate. Its output is only on when neither one input "NOR" (inclusively) the other are true. This gate shares the same property of the NAND gate, as any other gate can be made from networks of only NORs.
[cs=2]Input | Output | |
x | y | x NOR y |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 0 |
Exclusive OR (XOR)
"Antivalence" (opposite of equivalence) between x and y can be written as x XOR y, and is only true when x or (exclusively) y are true.
In electronics, this is represented by a XOR gate. Its output is only on when one output or (exclusively) the other are true. This gate has the property that if any one of its inputs change, its output will also change.
[cs=2]Input | Output | |
x | y | x XOR y |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Negated/NOT XOR (XNOR) (Exclusive NOR)
Equivalence between x and y can be written as x XNOR y, and is only true when x and y are either both true or both false.
In electronics, this is represented by an XNOR gate. Its output is only on when the two inputs are either both on or both off. This gate also shares the XOR property that if any one of its inputs change, its output will change as well.
[cs=2]Input | Output | |
x | y | x XNOR y |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Implication (IMP)
An implication of y from x can be written as x → y (or you can simply write x Implies y), and is false only when x is true (implying y), but y is false. Note that x → y may not be the same as Cyx.
In electronics, this is represented by an OR gate with one negated input. Its output is only false when the negated input is on while the other input is off.
[cs=2]Input | Output | |
x | y | x → y |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
Logic Gate Symbols
Arithmetic with Circuits
The four basic arithmetic operations + / - / × / ÷ can be made from the use of logic gates in circuits.
Addition
Addition can be done quite simply with a device called an adder.
Half Adder:
A half adder has 2 inputs: A and B, and is designed to add 2 bits (1's or 0's). The inputs A and B in a half adder can represent any bit, though in about all cases, they represent the least significant bit (the bit whose decimal value is 1 or 0), since a 1 cannot be carried into a half adder from a previous addition calculation. This makes them suitable for being the first, and only the first, adder in a connection of multiple adders to add larger numbers. To read the output, assign S (sum) as the least significant bit, and C (carry out) as the next bit to the left.
Full Adder:
A full adder has 3 inputs: A, B, and Cin (carry in). It also has 2 outputs: S (sum) and Cout (carry out). All 3 inputs are of the same order of magnitude and are added together.
A | B | Cin | Cout | S | Reason |
0 | 0 | 0 | 0 | 0 | (0 + 0 + 0 = 00) |
1 | 0 | 0 | 0 | 1 | (1 + 0 + 0 = 01) |
0 | 1 | 0 | 0 | 1 | (0 + 1 + 0 = 01) |
0 | 0 | 1 | 0 | 1 | (0 + 0 + 1 = 01) |
1 | 1 | 0 | 1 | 0 | (1 + 1 + 0 = 10) |
1 | 0 | 1 | 1 | 0 | (1 + 0 + 1 = 10) |
0 | 1 | 1 | 1 | 0 | (0 + 1 + 1 = 10) |
1 | 1 | 1 | 1 | 1 | (1 + 1 + 1 = 11) |
N-Bit Adder
N-Bit adders work using multiple full adders set up in a way such that each adder's Cout connects with the next adder's Cin. This allows N adders to be able to calculate the sums of 2 N-bit numbers. It is okay for the first adder be a half-adder, since there is no carrying from the adder before it (as there is no adder before it).
4-Bit Adder
Subtraction
It is possible to fashion a logic circuit that subtracts numbers using regular subtraction; however, one can be made using adders so that building a new circuit can be avoided. These types of circuits that can be used both as an adder and subtractor are called adder-subtractors. To subtract two binary numbers this way, a different method of subtraction must be used. Let's say we had a - b, where both a and b were in binary. Look at b and invert its digits, then add 1. Add that number to a and you have your answer, which will be in two's complement notation. To find the value of a number in two's complement notation, look at the most significant bit: if it is a 0, the number will be positive and can be read normally, but if it is a 1, the number is negative and to get the absolute value you must invert it and add 1.
Example:
3 - 7
 011 (3)  a=011
-111 (-7) b=111 → Invert all bits and add 1 → 001
 011
+001 ← Add modified b to a
 100  ←see that most significant bit is 1 and realize answer is negative. Invert number (turns to 011) and add 1 (turns to 100).
-100, or -4, will be your answer.
Also, here is a table comparing numbers in two's complement to regular binary numbers to decimal:
Decimal | Binary | 2's Comp. Notation |
32 | 100000 | 00100000 |
31 | 11111 | 00011111 |
2 | 10 | 00000010 |
1 | 1 | 00000001 |
0 | 0 | 00000000 |
-1 | -1 | 11111111 |
-2 | -10 | 11111110 |
-32 | -100000 | 11100000 |
To modify adders to output numbers in this notation, you must attach an XOR gate to one input of each adder then make a wire that inputs into each XOR gate and the Cin of the adder. To use, the negative term must be inputted into the XOR gates and positive number must be inputted directly into the adders. The circuit should look like this:
4-bit Adder-Subtractor
The Control input controls whether the circuit will add or subtract. When it is off, the circuit works exactly like an adder, but when it is on, it inverts all B inputs and adds 1 via the Cin input.
Multiplication
Multiplication in circuits can be easily done in a way that mirrors long multiplication. Using n - 1 adders, you can multiply 2 n-bit numbers. Let's take a look at what a binary multiplier does:
Example:
    1111 (15)
   ×1001 (9)
   01001 ⇦ 01001* 1001 × the rightmost bit of 1111
  +1001│ ⇦ 1001 (shifted 1 bit left (10010)) 1001 × 2nd bit from the right in 1111
  01101│ ⇦ 01101* adding the 2 products (0100 + 1001)
 +1001││ ⇦ 1001 (shifted 2 bits left (100100)) 1001 × 3rd bit from the right in 1111
 01111││ ⇦ 01111* is calculated by adding 0110 + 1001
+1001↓↓↓ ⇦ 1001 (shifted 3 bits left (1001000)) 1001 × 4th bit from the right in 1111
10000111 (135)
The 3 sets of colored numbers represent the 3 sets of numbers that would go into the 3 4-bit adders in a 4-bit multiplier.
*This rightmost bit is automatically sent as the next bit in the answer output and disregarded in adding operations. This is done because it can no longer be changed (it will only be added to 0's). A 0 (bold) is added before the number in order to make it a 4-bit number again.
So how would the schematics of a 4-bit binary multiplier look like?:
All inputs beginning with 'A' or 'B' represent a specific value of a bit of A or B. A4/B4 would be the most significant bit, and A1/B1 would be the least significant. The AND gates are labelled to show which inputs they are receiving. In the full adders, labels with lower numbers represent less significant bits. Also, inputs labelled '(0) False' are to always remain 0/off/false.
Division
[Unfinished]