### 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 =

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

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.

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:

Sum: 10

Carries: 1111

Addend: 10100101

Addend:

Sum: 101000011

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

~~10~~10

~~1~~ 0 0 1

0 0 1 1 = 11(binary) = 3(decimal)

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

Partial Products: 1101

1101

0

Final Product: 10001111

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:

10)111010 ←Place-holding zero

11││

10│

010

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,

These are some of the Boolean operations:

Negation of

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 of

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.

Non-conjunction of

In electronics, this is represented as a NAND gate. Its output is only

Disjunction of

In electronics, this is represented as an OR gate. Its output is only on when one input "OR" (inclusively) the other are on.

Non-disjunction of

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.

"Antivalence" (opposite of equivalence) between

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.

Equivalence between

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.

An implication of

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 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 C

N-Bit adders work using multiple full adders set up in a way such that each adder's C

4-Bit Adder

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

Example:

3 - 7

011 (3) a=011

011

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 C

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 C

Multiplication in circuits can be easily done in a way that mirrors long multiplication. Using

Example:

1111 (15)

01101│ ⇦ 01101* adding the 2 products (0100 + 1001)

01111││ ⇦ 01111* is calculated by adding 0110 + 1001

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.

[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 =

**B**inary Dig**it**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

1101

**0**0

__+1101__**000**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

*x*can be written as NOT*x*. If*x*is true, then NOT*x*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 C*yx*.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 C

_{in}(carry in). It also has 2 outputs: S (sum) and C_{out}(carry out). All 3 inputs are of the same order of magnitude and are added together.A | B | C_{in} | C_{out} | 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 AdderN-Bit adders work using multiple full adders set up in a way such that each adder's C

_{out}connects with the next adder's C_{in}. 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 → 001011

__+001__← Add modified b to a100 ←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 C

_{in}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 C

_{in}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)__0__1001 ⇦ 01001* 1001 × the rightmost bit of 111*1*__+1001__│ ⇦ 1001 (shifted 1 bit left (10010)) 1001 × 2^{nd}bit from the right in 11*1*101101│ ⇦ 01101* adding the 2 products (0100 + 1001)

__+1001__││ ⇦ 1001 (shifted 2 bits left (100100)) 1001 × 3^{rd}bit from the right in 1*1*1101111││ ⇦ 01111* is calculated by adding 0110 + 1001

__+1001__↓↓↓ ⇦ 1001 (shifted 3 bits left (1001000)) 1001 × 4^{th}bit from the right in*1*11110000111 (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]