Midterm 1 Flashcards
What are the main components of a computer?
Memory: Main memory or RAM (volatile), secondary memory (non-volatile- examples are like flash memory and discs), cache memory (also volatile)
Processor (CPU): Arithmetic/logic circuits, timing/control circuits, registers, and cache memory
Input: keyboard, mouse, touchpad, cameras
Output units: printers, speakers
How do the different components of the computer communicate with one other.
Each component of a computer (memory, processor, input, and output) are connected through an interconnected network. A component that is missing could be internet connection if a computer wanted to access data from the internet
What is the smallest unit of memory?
A bit (or a binary digit)
A bit may be either a ________ or a _________
0, 1
What are the hardware devices that can store a bit called?
Also called bits
When you are writing a bit, you are overwriting it. Explain what this means.
When you overwrite a bit, it means the original bit that you have written, isn’t going to be there anymore. Meaning if you wrote a 1 before, and you write a 0 now, the new value of the bit is 0 and the 1 disappears.
True or False: The main memory of a computer system is where data information is kept.
True
Data can be many different types. Provide some examples:
Audio, visual, integer, character, float, etc.
Before you run a program (any program) where is it?
It will be located on the hard drive or disc
In order for any instruction of a program to execute, where does the instruction have to be? Where does the data for that instruction have to be?
In order for any instruction of a program to execute, the instruction as well as the data for that instruction should be in the computer’s memory.
Main memory is also referred to as what?
Random Access Memory or RAM
What happens when you shut down a machine? Explains what happens with the memory.
When you shut down a machine, due to memory technology, contents in the main memory disappear. We require power for certain machines, so not having the appropriate technology or power for your machine could result in the contents of the main memory disappearing
True or False: Processor gets information from input and output devices
True
To prevent overwriting and to retain the old bit, what must we do?
We must store the bit string as a new variable
What is an ordered sequence of 1 or more bits called?
A bit string
True or False: “10” and “01” are different bits strings.
True. It does NOT matter if the bit strings comprise of the same bits, the order matters. If they are in a different order, they are different bit strings
How do we store EVERYTHING as a bit string?
By encoding everything as a bit string. Encoding mean converting the meaning/value to a bit string that can be used to represent it
If given the bit string “01” and if you are asked what it represents, (not the value of a bit string) what should your answer be?
No idea. It is impossible to tell as it could have various meanings. More context must be provided
True or False: Memory is organize into a sequence or an array of words.
True
In the prior generation of hardware, a word was a string of 32 bits. How many bits is a word in this generation?
64 bits. However, there is no universal agreement on the definition or size of a word. Unless and otherwise stated, we will assume it is 64 bits.
A byte is ALWAYS defined as what?
A string of 8 bits. A byte is ALWAYS a string of 8 bits. This definition is universal
In this generation, a word would be how many bytes?
A word would be 8 bytes in this generation.
For unsigned binary numbers, how do we find the largest number that can be encoded for n number bits?
2^n-1
What is the smallest number that could be encoded for a bit string?
0
What is the range of values which can be encoded by B2U number of n bits?
0 through 2^n-1
True or False: The range is dependent on n number of bits. Larger n, bigger range.
True
How do we encode values using B2U?
You start by using the rightmost digit and you multiply that with 2*0. Your leftmost digit should be multiplied by 2^n-1.
Example: The bit string “11001” denotes the value of 25. How?
1 *2^0 + 0 *2^1 + 0 *2^2 + 1 *2^3 + 1 *2^4 = 1+0+0+8+16= 25
What is the encoding scheme for negative numbers called and how does it work?
Binary to sign and magnitude (B2S). A first bit of 0 is used to denote for a non-negative number and 1 for negative number so “0101” denotes +5 and “1101” denotes -5.
True or False: B2S is extremely efficient in machines.
False. B2S is intuitive and does NOT work well in machines, and nobody uses it for signed numbers.
Using B2U, compute the arithmetic operation of adding the following two 4 bit numbers “0101” and “0110”
Carry: 0 1000
1st Number: 0101
2nd Number: 0110
Sum: 1011
What is the lsbs?
Least significant bits; the rightmost pair of bits
What is overflow?
Overflow means that the sum generated by the addition hardware is NOT ACCURATE because there are not enough bits to store the accurate/correct result.
Show an example of overflow using B2U and explain the issue:
Carry: 1 1100
1st number: 0110
2nd number: 1010
Sum: 0000
Here, the sum is 0 when in reality it should be 16 as the 1st bit string adds up to 6 and the 2nd bit string adds up to 10. However, there is overflow which resulted in the incorrect sum. This is due to the fact that the largest value encoded in a bit string comprised of 4 bits is 15. The result of 16 is too big.
Why can we just not add another bit to counter overflow? Meaning, if the processor is adding two 4 bit numbers, and the there is overflow (the anticipated result doesn’t fit in 4 bits) why don’t we just add an extra bit to store the result? In other words, why don’t we store it as a 5 bit result?
This is not effective as this makes the hardware way more complicated and the performance will not be any better than if you were to store it as a 4 (or however many) bit result. This is exactly why no manufacturer builds a computer that uses an extra bit to store the proper result when there is overflow.
True or False: Because adding an extra bit to store a result when there is overflow is inefficient, CPUs generally use the same number of bits to store results that are used for operands. CPUs generally only work on operands of certain number of bits (8, 16, 32, and 64 bit operands/results are what all general-purpose CPUs have today)
True
All CPUs store the carry from the addition of the msbs somewhere, so that overflow can be detected. Processors store this last carry in a 2 1 bit flag. What is this called and what is its abbreviation?
This called the carry flag, and its abbreviation is C.
For an unsigned arithmetic operation, what does it mean when C is 1?
This means that the result derived from the last arithmetic operation is incorrect
For an unsigned arithmetic operation, what does it mean if C is 0?
The result of the last arithmetic operation is correct.
What is the msbs?
Most significant bits; this is the leftmost bit in a bit string
For the 2’s complement, what are our 3 priorities?
- Want to have roughly equal number of positive and negative number (suppose we have 3 bits, meaning total of 8 different bit strings, ideally we would like to have 4 positive and 4 negative numbers)
- We want to have as many numbers as possible (that is, every encoding should encode a unique value- we do not want 2 encodings of the same value)
- Want to have an easy comparison for equality of numbers, and easy determination of sign of number
The 2’s complement encoding scheme can be denotes as:
B2T
With the encoding scheme B2T, there is a 2-step algorithm (thus why it is called 2’s complement). that is often used to negate values (or to get the negative value that corresponds to some positive value). What are the two steps to the algorithm?
1) Invert all the bits (change 1’s to 0’s and 0’s to 1’s)
2) Add 1 to the result of step 1
Using B2T, negate the bit string “0101”:
1) Invert: 1010
2) Add 1: 1011
“0101” is a value of 5. “1011” is -5 in B2T
The 1’s complement encoding scheme can be denoted as”
B2O
True or False: The 2’s complement was developed based on 1’s complement, which is a simpler scheme for negation of integer numbers, but does not work nearly as well.
True
If we have a non-negative integer in B2U, let’s say 011, how we can we negate it using 1’s complement?
Use one’s complement. You simply just invert (or complement) all of the bit. So we would get “100”.
The 1’s complement encoding scheme looks simpler but it does not work well for arithmetic operations. Why is this the case?
Because we cannot use the same hardware in the ALU (arithmetic logic unit) to do signed and unsigned operations. We would need one adder for unsigned values, and a different adder for signed values. This makes the hardware more complex and expensive.
For a 1’s complement addition, if we look at lots of examples, we will see that the result will be incorrect if both operands are negative. How do we mitigate this?
Use a carry of 1 for the 1st pair of bits when both operands are negative (have an msbs of 1)
How can we get the hardware to use a carry of 1 to add the 1st two bits when both operands are negative?
We can use the an AND gate for the two msbs in the operands and use the output of that gate as the first carry. This method also works if both operands are positive
With B2O encoding, if one operand is positive and one is negative using the AND gate can be challenging (0 AND 1 is 0) so the first carry could be 0. Sometimes you will get the correct result and sometimes you will not, as it will not always work for operands of different signs. How would yo come up with a solution?
You can add back the last carry
Ex: Carry: 0 0000
1st Number: 1100 (-3) 2nd Number: 0010 (2) Sum: 1110 (-1)
Ex 2: Carry: 1 1000
1st Number: 1100 (-3)
2nd Number: 0100 (4)
Sum: 0000 (0)
What do you notice?
The second example yields and incorrect result. In the first example, we used a carry of 0 and that was correct, in the second example (1 and 0 is 0) the result is incorrect. So, if the result is correct with a 1st carry of 0, then LAST carry will also be 0, BUT if the result is incorrect with first carry of 0, then LAST carry is 1
When adding two number with different signs in B2O getting the correct results depends on what?
Choosing the right carry for the first pair of bits (but making the right choice of the bit to use for the first carry requires more complicated hardware)
True or False: When adding numbers with different signs in B2O with a 1st carry of 0, then the LAST carry will ALSO be 0
True
True or False: When adding two numbers with different signs in B2O, if the result is incorrect with a 1st carry of 0, then the LAST carry will be 1
True
How do we fix getting an incorrect result with B2O?
Add the last carry back to the result and then the result will always be correct as long as there is no overflow
How do we fix getting an incorrect result with B2O?
Add the last carry back to the result and then the result will always be correct as long as there is no overflow
What is the disadvantage of adding numbers with different signs in B2O?
The disadvantage is that it requires a SECOND addition operation (when you add back the last carry). This means addition takes twice as long and addition is A VERY COMMON OPERATION in programs
How can the addition unit in the processor determine if the two numbers added have different signs (one has sign bit of 0, and the other has sign bit of 1) ?
By using the XOR gate. The adder can input the 2 msbs to an exclusive-or (XOR) gate. XOR outputs a 1 if and any if exactly 1 of the two input bits is 1.
How does the XOR gate determine if a second addition needs to be done?
If the XOR gate output is 1, a second addition will be done using the last carry from the first addition as the first carry for the second addition. If the output of the XOR gate is 0, only one addition will be done, as we described before.
True or False: When adding two negative numbers in B2O, using a carry of 1 for the first pair of bits always works.
True
True or False: When adding two non-negative numbers in B2O, using a carry of 0 for the first pair of bits always works also (it’s just line B2U addition)
True
True or False: When adding two numbers with different signs (XOR gate outputs 1), use a 1st carry of 0, but then add the last carry back the the result (do a second addition to obtain the final correct result).
True
What method of encoding is universally used in hardware that is built today?
2’s complement.
Why are B2S and 1’s complement not used in modern hardware?
It makes the hardware more complicated; different hardware needed for signed and unsigned arithmetic, and for B2O addition takes twice as long
With 2’s complement, the same hardware can be used for unsigned and signed arithmetic for ALL operations, with only a very small wrinkle. Explain this wrinkle.
The wrinkle is that overflow must be detected differently. If the carry is 1, that implies that the result is incorrect but the result could be correct and still have a last carry of 1. There could also be a last carry of 0, but the result could be incorrect.
In B2T and signed operations how do we detect overflow?
We need to compare the second to last carry and the carry from msbs. If the two carries are same, there is NO overflow and if the two carries are different, there is overflow
All CPUs today have a second flag in addition to the carry flag which is used to detect overflow for signed operations. What is this flag called and what is its abbreviation?
It is the overflow flag and is abbreviated as O
How do you determine the bit value of the overflow flag?
We use an XOR gate. The XOR gate outputs a 1 of the two bits are different. It will output a 0 if both the last carry and second to last carry are 0 or 1.
True or False: The O flag will be 0 if there is no overflow and the will be 1 is there is overflow.
True
What are the advantages of 2’s complement?
- Arithmetic is easy and uniform for positive and negative nos.
- Going from 3-bit to 4-bit is easy: just extend the sign bit; works for any number of bits
What is the range of values for B2T numbers for n bits?
-2^n-1 to 2^n-1 -1
For a 4 bit B2T number, what would the range of values be?
-8 to 7 (because -2^4-1 to 2^4-1 - 1)
For a 4 bit B2T number, what would the range of values be?
-8 to 7 (because -2^4-1 to 2^4-1 - 1)
True or False: We use the carry flag (C) only for unsigned operations.
True. Today all CPUs have a second flag in addition to C flag. For B2O and B2T we use the overflow flag because in signed operations we need to distinguish overflow properly.
True or False: Because 2’s (B2T) works for both signed and unsigned arithmetic, we can do subtraction by adding the negative of the number being subtracted.
True. If you need to do a-b, just do a+ (-b). We invert the bits of the second operand (input each one into a NOT gate) and change the carry used for the first pair of bits from 0 to 1 (this is equivalent to adding 1 to the complemented second operand rather than using 0 for the first pair as you would for B2U or B2T).
Carry: 1 1001
1st Number: 0100 (4)
2nd Number: 1100 (-3 in B2O)
Sum: 0001
Is the result correct?
Yes it is. The last two carries are same so the overflow flag is 0. If the two bits are different, the CPU would store a 1 in the overflow flag
Carry: 1 1001
1st Number: 0100 (4)
2nd Number: 1100 (-3 in B2O)
Sum: 0001
Is the result correct?
Yes it is. The last two carries are same so the overflow flag is 0. If the two bits are different, the CPU would store a 1 in the overflow flag
How is overflow detected with subtraction?
Overflow can be detected with using the last and second to last carry, but because subtraction is a signed operation, overflow is detected with an XOR gate. If the last two carries are same, there is NO overflow and the O flag will be 0. If the last two carries are different, the O flag will be 1 and result is incorrect
Floating point numbers are a powerful representation used to represent a wide range of values. What is the way to show the floating point numbers in IEEE 754 (single point precision)?
-1 bit for the sign of the number (0 if positive and negative if 1)
- 8 bits to represent a signed exponent to a base of 2
- 23 significant bits in the form 1.XX…X
- Remember there is an implied 1 before the binary point
- This works because the use of the exponent covers a wide range of values with the number of significant bits being the same at different values
What is the most common way/standard of encoding floating point numbers?
Using the standard IEEE 754. IEEE 754 is used for flavors on Intel based PC, Macs, and most Unix and Linux platforms.
True or False: In the IEEE 754 standard the first bit (msb) encodes the sign of the number and it is 0 for non-negative and 1 for negative.
True.
In the IEEE 754, the next 8 bits encode the exponent, but the exponent is encoded with a bias (a number added to the true exponent); to get the true exponent you must subtract the bias. What is the bias?
For single point precision, it is 127
For a 32 bit IEEE 754-encoded number, the format is:
X YYYYYYYY ZZZZZZZZZ…
(1-bit sign) (8-bit biased exponent) (23-bit mantissa)
The standard form of the encoded number is:
(-1)^x * 1.ZZZZZZZZZZZ * 2^exp
REMEMEMBER: exp in the formula above is **the true exponent, NOT the biased exponent (which is the exponent represented as part of the 32 bit encoding). Also, the 1 before the decimal isn’t apart of encoding; it is implied.
True or False: If the exponent is negative, float point numbers can be used to represent which are less than 1. If the exponent is negative and very small, positive numbers can be represented which are extremely small that is much less than 1, extremely close 0 (or negative numbers much greater than -1 and close to 0).
True
For IEEE 754 single precision, what is the biased exponent range?
0-255
For IEEE 754 single precision is, what is the true exponent range?
-126 to 127
What are the values of exponents from -126 to 127 called in IEEE 754?
Normalized numbers
What the range of true exponents, we can encode floating point numbers in the range:
+/- 1.0 * 2^-126 to +/- 1.0 * 2^127
If the encoded exponent is 0 (all 8 bits of the exponent are 0’s), what is this called?
Demoralized number (this can be used to represent 0, and the values with absolute value much less than 1, that is, values extremely close to 0)
If a number has a biased exponent of 255 what does this mean?
All 8 exponent bits are 1 are used to encode +/- infinity, and errors
If we compare the range of floats using IEEE 754 single precision to 32 bit signed integers, we can see floats have a much, much larger range:
Floats: +/- 1.0 * 2^-126 to +/- 1.0 * 2^127
Signed ints (B2T) -2^31 to 2^31 - 1
For non-negative floats, we can represent:
-0
- From values which are extremely small, but close to 0, to values which are extremely large, much larger than the larger integer which can be represented, even with a 64 bit
If we want perfect precision, but much more limited range, we need:
Integer types
Some encoded floats represent real number values precisely, but only if the number can be written in the form:
(+/-) x/y where y is an integer of the form 2^n, for integer n less than or equal to 0. Fractional values such as (1/5) cannot be stored precisely in binary; they can only be approximated.
The most significant bit (msb) in an ASCII character iencoding is always 0. What is the implication of this?
This means that the msb can be used to detect errors in the transmission of character data, for example, across a network connection.
ASCII uses only 7 bits (remember that the msb is always 0), and this means it can encode a very limited number of characters. What can we do to encode for a larger character set?
Use more bits and use the UTF-8 encoding method
True or False: Each character is encoded by one to four 8 bits bytes
True
True or False: In UTF-8 although the encoding of any particular character always uses the same number of bytes, encoding TWO different characters may use a different number of bytes.
True
True or False: ASCII and UTF-8 are equivalent for one-byte encoded UTF-8 characters
True
Since 2009, UTF-8 has been the dominant character encoding scheme for the World Wide Web
True
What is the error detection method for ASCII?
Parity. We use 8 bits instead of 7 (the value of 8th bit being chosen to get even number of 1’s)
What does VPB stand for?
Vertical parity bit
What does HPB stand for?
Horizontal parity bit
For columns, what does it mean if the VPB is 1?
It means the number of 1’s in the column is odd
For columns, what does it mean if the VPB is 0?
It means the number of 1’s is even for the column
For rows, what does it mean if the HPB is 1?
It means the number of 1’s is odd for the row
What does it mean if the HPB is 0?
It means number of 1’s is even in the row
Everything in the computer is stored as bit strings. So how do you know what value is encoded?
You must know which value is stored WHERE in memory and WHAT the encoding scheme is to store the value, in order to be able to interpret the data.
If you don’t know the encoding scheme, it would just be a bunch of bit strings, and you can’t tell if something is a photo, emoji, video
Memory is organized as an ___________ of bytes; each byte in the memory array has an ____________, and this index of the memory byte is called an _________. System addresses always start with index _______.
Array, index, address, 0
True or False: Memory consists of a huge number of bytes, and each byte in memory has a unique address. If the memory has for example 10 bytes, their addresses will be 0,1,2…9 and will be represented as a bit string.
True. EVERYTHING in the computer is represented as a bit string
True or False: Numbers (integers and single-precision floats) are usually stored in 4 bytes, though the word size in a 64-bit machine 8 bytes.
True
True or False: In a typical machine today, the address is represented as a 64-bit string (16 hexadecimal) and the word size is 8 bytes. In prior generation of computer systems, addresses were 32 bits (8 hexadecimal) and word size was 4 bytes.
True
