User:Saul/cs and math

Bases

Binary

Unsigned

Unsigned binary can represent numbers from 0 to 2^bits - 1, eg. 4 bits of unsigned binary can represent numbers from 0 to 15.
In unsigned binary all numbers are positive.
Here is a few conversions from decimal to binary:

Binary : Decimal
000 : 0
001 : 1
010 : 2
011 : 3
100 : 4
101 : 5
110 : 6
111 : 7

One's Compliment

One's compliment was an old way of specifying signed binary.

The way of specifying a number as negative in binary was to set the most significant bit (The left most bit) to a 1.
0XXX would be a positive number and 1XXX would be a negative number.

In one's compliment negative numbers are represented by setting the most significant bit (The left most bit) and flipping all the other individual bits to the opposite.
For example to get -2 in binary:

010 (+2 in decimal)
-> 110 (Set the most significant bit to 1)
-> 101 (flip all other bits, -2 in decimal)

Here is a few conversions from decimal to binary (one's compliment):

Binary : Decimal
1000 : -7
1001 : -6
1010 : -5
1011 : -4
1100 : -3
1101 : -2
1110 : -1
1111 : -0
0000 : +0
0001 : +1
0010 : +2
0011 : +3
0100 : +4
0101 : +5
0110 : +6
0111 : +7

The issue with one's compliment is that there are two zeros - 000 = +0, 111 = -0 and adding one's compliment numbers together does not always correctly sum, for example:

5    + -3  = 0 (Decimal)
0101 + 1100 = 10001 = 0001 (drop the left most bit as it is out out of the 4-bit scope)

Two's Compliment

Two's compliment can represent numbers from -2^{bits - 1} to 2^{bits - 1} - 1, eg. two's compliment in 4 bits can represent numbers from -8 to 7
Two's compliment is a solution to the problems that one's compliment has.
To turn a binary number to its negative, start by doing the same thing as one's compliment, then just add 1 to the result for example:

0101 (unsigned binary : 5 in decimal)
1010 (one's compliment)
1011 (two's compliment : -5 in decimal)

To turn a binary number from its negative to its positive just do the same process!

Examples

Here is a few conversions from decimal to binary (two's compliment):

1000 : -8
1001 : -7
1010 : -6
1011 : -5
1100 : -4
1101 : -3
1110 : -2
1111 : -1
0000 : +0
0001 : +1
0010 : +2
0011 : +3
0100 : +4
0101 : +5
0110 : +6
0111 : +7

Other Notes

Two's compliment is like the standard way of looking at binary but the most significant bit now represents the negative version of itself as this table shows:

-8	4	2	1	Calculation	Result (Decimal)
1	0	0	0	1x-8 + 0x4 + 0x2 + 0x1	-8
1	0	0	1	1x-8 + 0x4 + 0x2 + 1x1	-7
1	0	1	0	1x-8 + 0x4 + 1x2 + 0x1	-6
1	0	1	1	1x-8 + 0x4 + 1x2 + 1x1	-5
1	1	0	0	1x-8 + 1x4 + 0x2 + 0x1	-4
1	1	0	1	1x-8 + 1x4 + 0x2 + 1x1	-3
1	1	1	0	1x-8 + 1x4 + 1x2 + 0x1	-2
1	1	1	1	1x-8 + 1x4 + 1x2 + 1x1	-1
0	0	0	0	0x-8 + 0x4 + 0x2 + 0x1	0
0	0	0	1	0x-8 + 0x4 + 0x2 + 1x1	1
0	0	1	0	0x-8 + 0x4 + 1x2 + 0x1	2
0	0	1	1	0x-8 + 0x4 + 1x2 + 1x1	3
0	1	0	0	0x-8 + 1x4 + 0x2 + 0x1	4
0	1	0	1	0x-8 + 1x4 + 0x2 + 1x1	5
0	1	1	0	0x-8 + 1x4 + 1x2 + 0x1	6
0	1	1	1	0x-8 + 1x4 + 1x2 + 1x1	7

Addition

Unsigned

To add binary numbers together you add the digits together from the right to the left and if you add two 1's together the result is 0 with a carry.

Example

Add 11010010₂ (210₁₀) and 01100111₂ (103₁₀).

1   11
 11010010
+01100111
---------
100111001

Note: This overflows the 8bit context!
11010010₂ (210₁₀) + 01100111₂ (103₁₀) = 100111001₂ (313₁₀)

Signed

Adding signed binary is the same as unsigned but the overflow must be removed!

Example

Add 11010010₂ (-46₁₀) and 01100111₂ (103₁₀).

(Using the unsigned working for this number)
11010010₂ + 01100111₂ = 100111001₂

Remove the overflow from the 8 bit scope in the result:
11010010₂ (-46₁₀) + 01100111₂ (103₁₀) = 00111001₂ (57₁₀)

Subtraction

To subtract a binary number from another convert the second number to the two's compliment and add them together as usual.

Example

Subtract 0010₂ (2₁₀) from 0101₂ (5₁₀).

0101 - 0010
-> 0101 + (-0010)

Find the two's compliment of 0010:

0010
-> 1101 (Flip bits)
-> 1110 (add 1)

0010 two's compliment is 1110.
Substitute two's compliment to as the negative second number:

-> 0101 + 1110

Add them together:

1
 0101
+1110
-----
10011

Remove the bits that exceed the scope (4bit scope in this case).

10011
-> 0011 (removed overflow)

Therefore 0101₂ (5₁₀) - 0010₂ (2₁₀) = 0011₂ (3₁₀)

Full Working

0101 - 0010
-> 0101 + (-0010)

Convert (-0010) to two's compliment:
-> 1101 (Flip bits)
-> 1110 (add 1)

-> 0101 + (-0010)
-> 0101 + 1110 = 10011
-> 0011

Octal

Octal is base 8 and is easy to convert from/to binary due to its special property, that which is having 2 as one of its roots, eg. 2³ = 8
Octal digits never exceed 7, 8 is represented by 10.

Binary to Octal

Number to convert:

01010101000111

Since octal is 2³ we can separate the binary digits in sets of threes from the right to the left.

01 010 101 000 111

Since the first set of numbers has only 2 numbers in it we add leading zeros as necessary.

001 010 101 000 111

Convert these sets of threes into Decimal or Octal (Same thing since a single octal (8) digit does not exceed decimal (10)):

1 2 5 0 7

Concatenate the results together and you have your Octal representation:

12507

Hexadecimal

Hexadecimal is base and is favoured in computing due to it being a larger base than Octal or Decimal and it has the property of having 2 as one of its roots, eg. 2⁴ = 16
Hexadecimal digits represent the decimal numbers from 0-15 where digits above 9 are represented by letters.
Here is few conversions from Hexadecimal to Decimal:

Hexadecimal : Decimal
0 : 0
1 : 1
2 : 2
3 : 3
4 : 4
5 : 5
6 : 6
7 : 7
8 : 8
9 : 9
A : 10
B : 11
C : 12
D : 13
E : 14
F : 15

Binary to Hexadecimal

Number to convert:

01110101000111

Since hexadecimal is 2⁴ we can separate the binary digits in sets of fours from the right to the left.

01 1101 0100 0111

Add leading zeros if necessary:

0001 1101 0100 0111

Convert the groups into decimal (from binary):

1 13 4 7

Convert the sections into hexadeimal (from decimal):

1 D 4 7

Concatenate the results together and you have your Hexadecimal representation:

1D47

Other Bases

Convert to Decimal

To convert a number of a different base to decimal sum the total of each digit times the base to the power of its position (starting at 0).
Pseudo code representation:

d = digit;
b = base;
p = position;

sum = 0;
for every digit in number
	sum  += d*b^p;

Example

Convert 60125206₇ to decimal:

Number: 60125206
Base: 7

Multiply each number by the base to the power of position (starting at 0):

6x7^7 + 0x7^6 + 1x7^5 + 2x7^4 + 5x7^3 + 2x7^2 + 0x7^1 + 6x7^0

Calculate:

6x823543 + 0x117649‬ + 1x16807‬ + 2x2401 + 5x343 + 2x49 + 6x1
4941258  + 0        + 16807   + 4802   + 1715  + 98   + 6

4964686‬

Therefore 60125206₇ is 4964686₁₀

Convert from Decimal

To convert a number from decimal you have to recursively divide it by the base and set the remainder as the digit.
Pseudo code representation:

n = number;
b = base;
i = current iteration;
d = digit string;

d = "";
i = n;

do
	d.append(i % b);
	i = floor(i / b);
while floor(i / b) > 0

d.reverse();

Example

Convert 283109₁₀ to base 17.

Number: 283109
Base: 10

Recursively divide by base and take the remainder like so:

283109 / 17 = 16653	r 8
 16653 / 17 =   979	r A (10)
   979 / 17 =    57	r A (10)
    57 / 17 =     3	r 6
     3 / 17 =     0	r 3

Read the remainders from bottom to top:

36AA8

Therefore 283109₁₀ is 36AA8₁₇

Boolean Algebra

Boolean algebra is usually used in circuit design and programming.

Table

Programming, Engineering and Mathematics often use different symbols to represent Boolean expressions as this table shows:

English	Programming	Engineering	Mathematics
AND	&&	•	∧
NAND
OR			+	∨
XOR (Exclusive Or)		⊕
NOR (Neither Or)
XNOR (Equivalence)	==
NOT	!	—	¬
TRUE	true	1
FALSE	false	0

Precedence

The order in which Boolean algebra are completed are: Brackets -> NOT -> AND -> OR

Laws

Here is a list of 15 laws when working with Boolean algebra equations: (Note the Engineering notation is used except in the case of NOT where programming notation is used due to HTML entity limitations)

1.  !(A + B) = !A • !B
2.  !(A • B) = !A + !B
3. A + A = A
4. A + 0 = A
5. A + 1 = 1
6. A + !A = 1
7. A + A • B = A
8. A • A = A
9. A • 0 = 0
10. A • 1 = A
11. A • !A = 0
12. A + !A • B = A + B
13. A • (B + C) = (A • B) + (A • C)
14. A + (B • C) = (A + B) • (A + C)
15. A = A

Converting Operators

Sometimes it can be useful to convert one operator to another because most chips have multiple gates of the same type on them, so if operators were the same type they could use the same chip rather than have a different one.

OR to AND

Using rule #1:
A + B = !(!A • !B)

AND to OR

Using rule #2:
A • B = !(!A + !B)

XOR

A ⊕ B

to AND and OR

A ⊕ B = (A + B) • !(A • B)

to AND only

A ⊕ B = !(!A • !B) • !(A • B)

NAND

NAND is one of the more useful gates because all other gates can be simulated by it.

Converting to NAND

NOT

A NAND A

AND

(A NAND B) NAND (A NAND B)

OR

(A NAND A) NAND (B NAND B)

Simplification

Like algebra Boolean algebra equations can sometimes be simplified - this is useful because if you can simplify a circuit you can save gates and therefore save chips.

Example

Simplify this:
!X • !Y • !Z + !X • !Y • Z + !X • Y • !Z

The trick here is to find two sets (interconnected AND statements) that have a single difference.
In this example the first and second sets only difference is Z which if we look at rule #6 - Z + !Z = 1
Therefore we can simplify it to this:
!X • !Y + !X • Y • !Z

Now it may look difficult to simplify this further as there is multiple differences between these groups, however we can add one of the groups on from the original set like so:
!X • !Y + !X • Y • !Z + !X • !Y • !Z

Now we see this can be simplified again:
!X • !Y + !X • !Z

Optional - Less Operators

The equation optionally can have further operators removed by factorization:
!X • (!Y + !Z)
Which we can then change the second two NOT statements into one using rule #2:
!X • !(Y • Z)
And again using rule #1:
!(X + (Y • Z))

Karnaugh Maps

An easy way to simplify Boolean algebra is to use Karnaugh maps.

Rules

Here are the grouping rules for Karnaugh maps.

1. No zeros allowed.
2. No diagonals.
3. Only power of 2 number of cells in each group.
4. Groups should be as large as possible.
5. Every one must be in at least one group.
6. Overlapping allowed.
7. Wrap around allowed.
8. Fewest number of groups possible.

Example

Consider the previous example, simplify this:
!X • !Y • !Z + !X • !Y • Z + !X • Y • !Z
First we would count the unique values: X, Y and Z.
Then we would need to make a table from these as evenly as possible, however when writing the values out they must only change one value at each change in row or column in a way that wraps:

X • Y / Z	Z	!Z
X • Y
X • !Y
!X • !Y
!X • Y

Then we go through each section in the equation (sections separated by '+' (OR)) and fill in the table with a '1' using the coordinates of the section:
!X • !Y • !Z + !X • !Y • Z + !X • Y • !Z

X • Y / Z	Z	!Z
X • Y
X • !Y
!X • !Y		1
!X • Y

!X • !Y • !Z + !X • !Y • Z + !X • Y • !Z

X • Y / Z	Z	!Z
X • Y
X • !Y
!X • !Y	1	1
!X • Y

!X • !Y • !Z + !X • !Y • Z + !X • Y • !Z

X • Y / Z	Z	!Z
X • Y
X • !Y
!X • !Y	1	1
!X • Y		1

Fill the rest with '0's:

X • Y / Z	Z	!Z
X • Y	0	0
X • !Y	0	0
!X • !Y	1	1
!X • Y	0	1

Then we need to group them according to the grouping rules:
!X • !Y + !X • !Z

Complex Numbers

Complex numbers are a complex (consisting of different and connected parts) of real numbers and imaginary numbers.

Matrices

Matrices are a way of representing complex numbers, usually consisting of a multi-dimensional array of numbers.
Below is an example of the matrix 'A' which is a 3x3 matrix consisting of the numbers a-i.

Matrix A

a	b	c
d	e	f
g	h	i

Addition and Subtraction

To add or subtract two matrices you must first ensure they are both the same size.
For example to calculate the following matrices: A_NxM + B_QxR you must ensure that N == Q and M == R.

Matrix A

a	b	c
d	e	f
g	h	i

+

Matrix B

j	k	l
m	n	o
p	q	r

=

Matrix A+B

a+j	b+k	c+l
d+m	e+n	f+o
g+p	h+q	i+r

Matrix A

a	b	c
d	e	f
g	h	i

-

Matrix B

j	k	l
m	n	o
p	q	r

=

Matrix A-B

a-j	b-k	c-l
d-m	e-n	f-o
g-p	h-q	i-r

Example

Matrix A

1	0	5
1	3	7
5	9	2

+

Matrix B

5	5	5
1	8	1
9	1	7

=

Matrix A+B

6	5	10
2	11	8
14	10	9

Matrix A

1	-2	3
3	-2	1
-7	5	-6

-

Matrix B

7	5	6
-3	-9	-7
0	0	9

=

Matrix A-B

-6	-7	-3
6	7	8
-7	5	-15

Multiplication

Matrices can by multiplied scaly quantities or other matrices. Matrices multiplication is not communal - A_{N x M} x B_{Q x R} != B_{Q x R} x A_{N x M}

Scalar

Multiplying a matrix by a scalar value multiplies all values within the matrix by that value.

Z x

Matrix A

a	b	c
d	e	f
g	h	i

=

Z x Matrix A

Za	Zb	Zc
Zd	Ze	Zf
Zg	Zh	Zi

Example

4 x

Matrix A

1	4	8
2	5	0
9	-5	3

=

4 x Matrix A

4	16	32
8	20	0
36	-20	12

Other Matrices

Multiplying a matrix by another matrix requires you to multiply each value in the row of the first matrix by the corresponding value in the second value's column and sum the total and put it in the position of that row and column, rinse and repeat for the other rows of the first matrix and the columns of the second.

To multiply two matrices together the rows in the first one must be the same amount of the columns in the second matrix.
A_{N x M} x B_{Q x R} can only be done if M and Q are equal.
B_{Q x R} x A_{N x M} can only be done if R and N are equal.

The size of the resulting matrix will have the amount of rows the first matrix has and the columns of the second.
A_{N x M} x B_{Q x R} = C_{N x R}
B_{Q x R} x A_{N x M} = C_{Q x M}.

Matrix A

a	b	c
d	e	f
g	h	i

x

Matrix B

j	k	l
m	n	o
p	q	r

=

Matrix AB

aj + bm + cp	ak + bn + cq	al + bo + cr
dj + em + fp	dk + en + fq	dl + eo + fr
gj + hm + ip	gk + hn + iq	gl + ho + ir

Example

Matrix A

1	7
4	0
-5	3

x

Matrix B

7	-3	5	6
-1	6	1	6

=

Matrix AB

1x7 + 7x-1	1x-3 + 7x6	1x5 + 7x1	1x6 + 7x6
4x7 + 0x-1	4x-3 + 0x6	4x5 + 0x1	4x6 + 0x6
-5x7 + 3x-1	-5x-3 + 3x6	-5x5 + 3x1	-5x6 + 3x6

=

Matrix AB

0	39	12	48
28	-12	20	24
-38	33	-22	-30

Identity

Identity matrix in complex numbers is the similar to '1' in real numbers.
For example in real numbers: Y x 1 = Y
In matrices: A_{n x n} x I_{n x n} = A_{n x n} - where I_{n x n} is an identity matrix.
Identity matrices are communal - A_{n x n} x I_{n x n} = I_{n x n} x A_{n x n}

Examples

I_1x1

1

I_2x2

1	0
0	1

I_3x3

1	0	0
0	1	0
0	0	1

And so on.

Inverse

An inverse matrix is a matrix to the power of -1, the same way that the inverse of a scalar number is 1 divided by it - which is same as multiplying by that number to the power of -1, for example: (1/6 = 6^-1)
So to switch a matrix to the other side of an equation multiply the other side by the inverse and the first side will cancel, for example:
Ax = y
(Where A is a matrix)
A^-1Ax = yA^-1 x = yA^-1

Finding the Inverse

The formulae for finding the inverse of a 2x2 matrix is:

Matrix A^-1

a	b
c	d

= (1 / (ad - bc)) *

Matrix A_s

d	-c
-b	a

Checking

To check if a matrix is an inverse multiply it by the normal matrix and the result should be Identity matrix.
For example: A*A^-1=I

Matrix A^-1

4	7
2	6

X

Matrix A^-1

0.6	-0.7
-0.2	0.4

=

Identity Matrix

1	0
0	1

Further Explanation

The inverse of a 2x2 matrix can be found via:
A^-1 = (1 / Det(A)) * A_S
(Where A is a 2x2 matrix and Det(A) is the Determinant of A and A_S is the swapped matrix)

Determinant

The determinant can be calculated by multiplying the top right element by the bottom left subtracted from the product of the top left and bottom right elements.
If the determinant is 0 then the matrix has no inverse.
For example:

Matrix A

a	b
c	d

Det(A) = (a * d) - (b * c)

A_s

This matrix is A but with the corners swapped with each other, and the top-right and top-left ones as the negative value.
For example:

Matrix A

a	b
c	d

Matrix A_s

d	-c
-b	a

Singular

A singular matrix is a matrix that has no inverse, the same way in scalar numbers 0 has no inverse as you cannot divide by 0.
If the determinant of a matrix is 0 then that matrix has no inverse.

Transformations

A matrix can be transformed in many ways, most useful to alter a shape that is defined by a set of points.
A point defined as a coordinate can be defined as a matrix:

(x, y) =

x

y

Once you have your point as a matrix it can be multiplied by another to perform certain transformations on it.

Rotation

A object can be rotated by multiplying the points (matrices) that form that object by another matrix.
The points will be rotated around the origin as its pivot point.
The matrix you need to multiply by is:

cos(A)	-sin(A)
sin(A)	cos(A)

Where A is the angle to rotate by.

Example

To rotate a point (x,y) by 36 degrees:

cos(36)	-sin(36)
sin(36)	cos(36)

=

0.81	-0.59
0.59	0.81

0.81	-0.59
0.59	0.81

x

y

=

0.81x + -0.59y

0.59x + 0.81y