Studied by 0 people
Looks like no one added any tags here yet for you.
What do humans understand?
Numbers and strings (i.e characters)
What are examples of what humans understand?
100 or the matrix
What do machines understand?
Binary numbers
Do machines understand human language?
No. We have to convert human language into binary representation
What is encoding?
To convert information into a different form.
What is a character example of binary encoding?
‘a’ encoded as binary 01100001_2 number
What is the representation for transforming characters to binary?
ASCII representation
What is a number example of binary encoding?
25_10 encoded as 00011001_2 number
What is the representation for transforming numbers to binary?
Base-2 representation
How many digits do base-10 numbers have?
10; 0-9
What does it mean for a number to be base-10?
Each digit is multiplied by a power of 10
What is the formula for getting to base-10?
v is base-10 value, d is decimal digit, and i is digit position, increasing right to left, starting from 0
How do we get 17543_10?
How do we get 173_10?
How do we get 1025_10?
How do we get 2001_10?
Answer
What are base-2 numbers?
Binary numbers
How many digits to base-2 numbers have?
2 binary digits; 0 and 1
What does it mean for a number to be base-2?
Each digit multiplied by power of 2
What is the formula for getting to base-2?
v is base 10 value, b is binary digit, and i is digit position
What is the range of binary numbers?
0 - (2^N-1)
N = Number of bits
How do we get 011111010000_
How do we convert 73_10 to binary?
How do we convert 181_10 to binary?
How do we convert 213_10 to binary?
2000_10
01001001
10110101
11010101
What are some Base-2 Terminology?
LSB, MSB
What is LSB?
Least significant bit
What is MSB?
Most significant bit
What is considered the least significant bit? What is considered the most significant bit?
The LSB is going to be the lowest power of two, and the MSB is the highest power of 2
What is the goal of a Decimal to Binary Algorithm?
We can apply a more algorithmic approach to converting a base-10 decimal number to binary; inverse problem
What is the Decimal to Binary Algorithm?
Where does the Decimal to Binary Algorithm Apply?
To any other number bases
How do we use the Decimal to Binary Algorithm on other number bases?
for base-n, replace divide by 2 with divide by n
Convert 18_10 to binary (base-2)
10010
What are Base-16 numbers also called?
Hexadecimal numbers
How many digits are in hexadecimals?
16 hex digits; 0-9 and A-F
What is a hex digit also called?
Hexit
What is a hexdigit?
A group of 4 binary bits
What is each hexit multiplied by?
A power of 16
WHat is the formula for hexits?
v is base-10 value, d is hexit, and i is digit position (increasing right to left, starting at 0)
0×7d0
Convert 73_10 to Hexadecimal
Convert 01101100_2 to Hexadecimal
Convert 0xA9 to Binary
0111 1101 0000
0049
6C
1010 1001
What is ASCII?
A standard format with 7 bits encoded to 128 characters
How many characters total in ASCII?
2^7'
‘A’ in base_10, base_2, and base_16
‘0’ in base_10, base_2, and base_16
‘\0’ in base_10, base_2, and base_1
65; 1000001; 0×41
48; 0110000; 0×30
0; 0000000; 0×00
What character has a 0 value?
The null terminator
Why is the null terminator value important?
Because it’s the only character with 0 value, it allows us to null terminate strings (recognizes the end of a string)
Convert ‘brent’ to Binary
What is fixed-length encoding?
When all symbols have same number of bits
What is an example of fixed-length encoding?
ASCII; each character always has 7 bits
When is fixed-length encoding used?
When all symbols have equal probability
What is variable-length encoding?
When symbols can use different numbers of bits
What is an example of variable-length encoding?
UNICODE 8 and 16
When is variable-length encoding used?
When some symbols are more likely than others; for example, compression
Variable-length Example
Suppose X and Y are twice as likely as W and Z
Encoding possibility: X and Y are 1 bit, W and Z are 2 bits
X and Y would use less bits, while W and Z require more bits
Main concept is commonly occurring symbols are encoded with few bits; the idea behind compression
How do we determine the number of bits for fixed-length representation?
Number of symbols = to 2^ number of bits
if we had 2 symbols, one bit is needed
If we had 4 symbols, 2 bits are needed
If we have 2^n symbols, then n bits are needed
We take the ceiling of log_2(M) to find number of bits for M symbol==
If we had the digits {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, how many bits are need?
If we had the 84 english characters (A-Z (26), a-z (26), 0-9 (10), punctuation (8), math (9), financial (5)), how many bits are need?
log[10] = 3.22 → 4
log[84] = 1.92 → 2
What is MSB used for? How?
Used to encode the sign. If MSB = 0_2, then it is a positive binary number. If MSB = 1_2, then it is a negative binary number.
What is the range for Signed Magnitude Representation?
-(2^(N-1) - 1) to (2^(N-1) - 1)
N = # of bits
What is the range represented in?
Base-10
If N = 8 bits, what is the minimum base-10 number that can be represented in signed magnitude? What is the maximum base-10 number
-127 - 127
What is -49 in SMR
What is +49 in SMR
What is +86 in SMR
What is -86 in SMR
10110001
00110001
01010110
11010110
Why is Signed Magnitude Good?
Easy to negate and compute the absolute value.
What is one reason why Signed Magnitude is bad?
Adding and subtracting can become complicated because we would need to implement a first hardware circuit to the add, and a second hard ware circuit to subtract.
What is the second reason why Signed Magnitude is bad?
2 different ways to represent 0. If all the bits are 0 and the MSB is 1, then the number is a -0. If the MSB is 0, then it is +0. Being able to represent 0 in 2 different ways is not ideal because it can complicate hardware design
What is signed representation like in practice?
It is not frequently used for integer numbers, but used in floating point numbers.
What is another signed representation?
2’s Complement Representation.
How is the sign encoded in 2’s Complement?
MSB is used, so 1 = negative sign, and 0 = positive sign. Conversion from base-10 to base-2 is slightly different from standard MSB Signed magnitude.
2’s Complement examples
-42
42
What is another process other than the formula to convert base-10 to base-2 in 2’s Complement?
A two step negating a number and algorithmic approach.
Explain the 2’s complement second approach.
Complement every bit (1_2 → 0_2, 0_2 → 1_2)
Add 1_2 using binary math (see supplement reading assignment)
2’s Complement Example
Answer
+86 to 2’s Complement
-86 to 2’s Complement
What is 2’s complement’s range?
(-2^(N-1)) to (2^(N-1) - 1)
If N = 8, what is the range in 2‘s complement?
Answer
What will happen if you apply 2’s complement to a negative number?
You will get a positive number.
Apply 2’s Complement to this negative number.
What is another thing we can do in 2’s complement? Why?
Addition, no subtraction. Because we use the MSB to determine whether the number is negative or not, we could do the number + a negative number to perform subtraction.
What is a good thing about representing integers in 2’s Complement?
There is only one 0, no positive or negative 0.
Prove the claim about the 0 in 2’s complement.
Answer
Signed Magnitude vs 2’s Complement
Sign Extension Example.
We would pad the MSBs with 0s to make 8. We don’t change the value of the number.
What do we do if we wanted sign extension with a negative binary nmber?
We would need to use 2’s complement, signed magnitude does not work.
What is the bad things about 2’s complement?
More complex to negate and compute the absolute value.
What are all the good things about 2’s complement?
2’s complement fixes the issues with signed magnitude. It uses only the add operation, only has one 0, and can use sign extension. Overall, it simplifies hardware design.
Note 
Flashcard (85)