110-1 Foundations of Computer Science, 4th Edition

--- title: 110-1 Foundations of Computer Science, 4th Edition --- # Chapter 1 # What is the main difference between Turing model and von Neumann model? * Universal Turing Machine * Stores only data in the memory. * The von Neumann Model * Stores both data and program in the memory. # What are the main functions of memory, ALU, control unit, and I/O subsystem? * Memory * Storage area for programs and data during processing. * Arithmetic logic unit (ALU) * Calculation of arithmetic and logical operations. * Control unit: * Manipulates the operations of the memory, ALU and I/O subsystems. * Input: * Accepts the data and the program from outside of the computer. * Output: * Sends the results of processing to outside world. # Distinguish between computer program and computer algorithm. * Program * Store in memory with data. * A sequence of instructions specifying what to do to the data. * Algorithm * Compilation of instructions for accomplishing a task. * Step-by-step solution. # Distinguish between machine language and computer languages. * Machine language * Instructions using binary patterns. * Tedious for long program. * Computer language * Using symbols to represent binary patterns. * Limited number of symbols and words. # Chapter 2 # Give a short definition of number system. A number system (or numeral system) is a system that uses distinct symbols to represent a number. # How to determine the radix of a number system? Radix is the base (or b), which is equal to the total number of the symbols in the set S. # Explain why conversion among binary, octal and hexadecimal systems is simple. * For four bits in the binary system are represented as one digit in the hexadecimal system. * For three bits in the binary system are represented as one digit in the octal system. # Distinguish between positional and non-positional number system. * In a positional number system, the position a symbol occupies in the number determines the value it represents. Each position has a place value associated with it. * A nonpositional number system uses a limited number of symbols in which each symbol has a value. However, the position a symbol occupies in the number normally bears no relation to its value—the value of each symbol is fixed. # Chapter 3 # What is overflow in unsigned representation? When will it occur? * The range of integers able to be represented is limited. For an n-bit system, the range is 0 to 2^𝑛−1^. * Considering a 4-bit binary system * The maximum value: 2^4^−1=15 * What if we want to store 20 in such system? * Change 20 to binary value: (10100)~2~ * The last 4 bits are stored to memory * The result is (0100)~2~= (4)~10~ * This is what we call overflow # Store 51 and -37 in 8-bit unsigned, sign-and-magnitude, and two’s complement representations. * Store 51 and -37 in an 8-bit memory location using unsigned representation 無號數. * 1. Change 51 to binary value: (11 0011)~2~ 2. Add two 0s to the left: (0011 0011)~2~ 3. Store the binary value to memory * 1. Change -37 to binary value: (10 0101)~2~ 2. Add two 0s to the left: (0010 0101)~2~ 3. Store the binary value to memory * Store 51 and -37 in an 8-bit memory location using sign-and-magnitude representation 符號大小值法. * 1. Change 51 to 7-bit binary 1. Change 51 to binary value: (11 0011)~2~ 2. Add one 0 to the left:(011 0011)~2~ 2. Set the leftmost bit to 0: (0011 0011)~2~ * 1. Change -37 to 7-bit binary 1. Change -37 to binary value: (10 0101)~2~ 2. Add one 0 to the left:(010 0101)~2~ 2. Set the leftmost bit to 1: (1010 0101)~2~ * Store 51 and -37 in an 8-bit memory location using two’s complement representation 2's補數表示法. * 1. Change 51 to 8-bit binary 1. Change 51 to binary value: (11 0011)~2~ 2. Add two 0s to the left: (0011 0011)~2~ 2. Get the binary value of 51: (0011 0011)~2~ 3. Apply two’s complement: (1100 1101)~2~ * 1. Change -37 to 8-bit ：inary 1. Change -37 to binary value: (10 0101)~2~ 2. Add two 0s to the left: (0010 0101)~2~ 2. Get the binary value of -37: (0010 0101)~2~ 3. Apply two’s complement: (1101 1011)~2~ # Retrieve 10001110 in unsigned, sign-and-magnitude, and two’s complement representations * Retrieve the bit string 1000 1110 stored in memory as an unsigned integer. 1. Remove the redundant 0s and get: (1000 1110)~2~ 2. Transfer the binary value to integer value:1×2^7^+1×2^3^+1×2^2^+1×2^1^=142 3. Output the integer value 142. * Retrieve the integer that is stored as 1000 1110 in sign-and-magnitude representation. 1. Take the first bit: 1 as negative value 2. Change the (000 1110)~2~ to decimal value: 1×2^3^+1×2^2^+1×2^1^=14 3. Add the sign and output the result -14 * Retrieve an integer in two’s complement for 1000 1110. 1. Take the first bit: 1 as negative value 2. Apply two’s complement: 000 1110 → 111 0010 3. Change (111 0010)~2~ to decimal value: 1×2^6^+1×2^5^+1×2^4^+1×2^1^=114 4. Add the sign and output the result -114 # Give the steps to store a number in IEEE standard floating-point format. Also give the steps to retrieve a number stored in IEEE standard floating-point format. * Store numbers in IEEE standard floating-point format 浮點數表示方法： Show the Excess_127 (single precision單精度 32bits: S1+E8+M23) representation of the decimal number 5.75 1. Store the sign (S正負位元) The sign is positive, so S = 0. 2. hange the number to binary Decimal to binary transformation: 5.75 = (101.11)~2~ 3. Normalize (101.11)~2~=(1.0111)~2~×2^2^ 4. Find the values of exponent (E/C特性質) and mantissa (M正規畫後之尾數) E = 2 + 127(超2^8-1^=128碼) = 129 = (1000 0001)~2~, M = 0111. We need to add 19 zeros at the right of M to make it 23 bits. >> 正規化後尾數範圍：$(0.1)$~n進制~ $\le M<1$ 5. Concatenate S, E and M 0100000010111000000000000000000 >> 倍精度64bits之E為11bits以Excess-1023碼表示，另外M有52個bits (S1+E11+M52) * Retrieve numbers stored in IEEE Standard floating-point format The bit pattern (11001010000000000111000100001111)~2~ is stored in Excess_127 format. Show the value in decimal. 1. Find the value of sign (S), exponent (E), and mantissa (M) The first bit represents S, the next eight bits, E and the remaining 23 bits, M 2. If S = 0 set the sign to positive, otherwise negative The sign is negative 3. Find the shifter E - 127 The shifter is E − 127 = 148 − 127 = 21 4. Denormalize mantissa Denormalizationgets (1.00000000111000100001111)~2~×2^(23-2=21)^ 5. Change the denormalizednumber to binary to find the absolute value The binary value is (1000000001110001000011.11)~2~ The absolute value is 2,104,387.75 6. Add the sign The number is −2,104,387.75 # What are the three steps of storing audio information? Briefly explain each step. * Sampling * Select only a finite number of points on the analog signal, measure their values, and record them. * Quantization * a process that rounds the value of a sample to the closest integer value. # Given an audio with 40000 samples per second and 16 bits per sample. Show the bit rate of such audio Bit depth × Sampling rate = how precisely the samples were encoded × the number of audio samples recorded per unit of time = 16 × 40000 # Distinguish between raster graphics and vector graphics. * Raster graphics has two disadvantages * The file size is big * Rescaling is troublesome (ragged when enlarged) * Vector graphics * Does not store the bit patterns for each pixel * An image is decomposed into a combination of geometrical shapes such as lines, squares, or circles * Each shape defined by a mathematical formula # Chapter 4 # Show how to set, unset, flip the first and the last bits of binary pattern (1110 0111)~2~ using pattern level operation * Complementing (NOT) * Complement the whole pattern (one’s complement) * | INPUT | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | OUTPUT | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | * Unsetting specific bits (AND) * Use mask as the second input with some zeros which is to unset the corresponding bits in the first input * | INPUT | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | MASK | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | | OUTPUT | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | * Flipping specific bits (XOR) * Use mask as the second input with some ones which is to flip the corresponding bits in the first input * | INPUT | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | MASK | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | | OUTPUT | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | * Setting specific bits (OR) * Use mask as the second input with some ones which is to set the corresponding bits in the first input * | INPUT | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | | ------ | ---------------------------- | --- | --- | --- | --- |:--- | --- | ---------------------------- | | MASK | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | | OUTPUT | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | # ADD - Shift Operation - 1. Logical shift operations * Use a logical left shift operation on the bit pattern 1001 1000. * The leftmost bit is lost and a 0 is inserted as the rightmost bit * | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | Original | | -------- | -------- | --- | --- | --- | --- | --- | --- | -------- | | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | After Shift | * Use a circular left shift operation on the bit pattern 1001 1000. * The leftmost bit is circulated and becomes the rightmost bit. * | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | Original | | -------- | -------- | --- | --- | --- | --- | --- | --- | -------- | | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | After Shift | # ADD - Shift Operation - 2. Arithmetic shift operation * Use an arithmetic right shift operation on the bit pattern 1001 1001. * The pattern is an integer in two’s complement format * The leftmost bit is retained and also copied to its right neighbor bit. * | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | Original | | -------- | -------- | --- | --- | --- | --- | --- | --- | -------- | | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | After Shift | * The original number was −103 and the new number is −52, which is the result of dividing −103 by 2 truncated to the smaller integer. * Use an arithmetic left shift operation on the bit pattern 1101 1001. The pattern is an integer in two’s complement format. * The leftmost bit is lost and a 0 is inserted as the rightmost bit. * | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | Original | | -------- | -------- | --- | --- | --- | --- | --- | --- | -------- | | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | After Shift | * The original number was −39 and the new number is −78. The original number is multiplied by two. The operation is valid because no underflow occurred. * Use an arithmetic left shift operation on the bit pattern 0111 1111. The pattern is an integer in two’s complement format. * The leftmost bit is lost and a 0 is inserted as the rightmost bit. * | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | Original | | -------- | -------- | --- | --- | --- | --- | --- | --- | -------- | | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | After Shift | * The original number was 127 and the new number is −2. Here the result is not valid because an overflow has occurred. The expected answer 127 ×2 = 254 cannot be represented by an 8-bit pattern(-128~+127). # ADD - Arithmetic Operations on Integer * Two integers A = (0001 0001)~2~ and B = (0001 0110)~2~ are stored in two’s complement format. Show how B is added to A. * The operation is adding. A is added to B and the result is stored in R. (+17) + (+22) = (+39). * | | | | 1 | | | | | | Carry | | --- | --- | --- | --- | --- | --- | --- | -------- | -------- | -------- | | | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | A | | + | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | B | | | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | R | * Two integers A = (0001 1000)~2~and B = (1110 1111)~2~are stored in two’s complement format. Show how B is added to A. * The operation is adding. A is added to B and the result is stored in R. (+24) + (-17) = (+7). * | 1 | 1 | 1 | 1 | 1 | | | | | Carry | | --- | --- | --- | --- | --- | --- | --- | -------- | -------- | -------- | | | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | A | | + | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | B | | | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | R | * Two integers A = (0001 1000)~2~ and B = (1110 1111)~2~ are stored in two’s complement format. Show how B is subtracted from A. * The operation is subtracting. A is added to ($\overline B$+1) and the result is stored in R. (+24) -(-17) = (+41). * $\overline B$=(0001 0000)~2~, and $\overline B$+1=(0001 0001)~2~ * | | | | 1 | | | | | | Carry | | --- | --- | --- | --- | --- | --- | --- | -------- | -------- | -------- | | | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | A | | + | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | ($\overline B$+1) | | | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | R | * Two integers A = (1101 1101)~2~ and B = (0001 0100)~2~ are stored in two’s complement format. Show how B is subtracted from A. * The operation is subtracting. A is added to ($\overline B$+1) and the result is stored in R. (-35) -(-+20) = (-55). * $\overline B$=(1110 1011)~2~, and $\overline B$+1=(1110 1100)~2~ * | 1 | 1 | 1 | 1 | 1 | 1 | | | | Carry | | --- | --- | --- | --- | --- | --- | --- | -------- | -------- | -------- | | | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | A | | + | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | ($\overline B$+1) | | | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | R | * Two integers A = (0111 1111)~2~ and B = (0000 0011)~2~ are stored in two’s complement format. Show how B is added to A. * The operation is adding. A is added to B and the result is stored in R. * | | 1 | 1 | 1 | 1 | 1 | 1 | 1 | | Carry | | --- | --- | --- | --- | --- | --- | --- | -------- | -------- | -------- | | | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | A | | + | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | B | | | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | R | * We expect the result to be 127 + 3 = 130, but the answer is −126. The error is due to overflow, because the expected answer (+130) is not in the range −128 to +127 * Two integers A=(0001 0001)~2~ and B=(1001 0110)~2~ are stored in sign-and-magnitude format. Show how B is added to A. * Addition: the sign of B is not changed. * 𝑆 = 𝐴~𝑠~ ++∨++ 𝐵~𝑠~ = 0 ++∨++ 1 = 1, 𝑅~𝑀~ = 𝐴~𝑀~+($\overline B$~𝑀~+1) * | | | No overflow | | | | | | | | | Carry | | --- | --- | --- | --- | --- | --- | --- | --- | --- | -------- | -------- | -------- | | A~s~ | 0 | | | 0 | 0 | 1 | 0 | 0 | 0 | 1 | A~M~ | | B~s~ | 1 | | + | 1 | 1 | 0 | 1 | 0 | 1 | 0 | ($\overline B$~𝑀~+1) | | | | | | 1 | 1 | 1 | 1 | 0 | 1 | 1 | R~M~ | | R~s~ | 1 | | | 0 | 0 | 0 | 0 | 1 | 0 | 1 | R~M~ = ($\overline R_M$ + 1) | * Since there is no overflow, we need to take the two’s complement of 𝑅~𝑀~. The sign of 𝑅 is the sign of 𝐵. * (+17) + ( −22) = (−5). * Two integers A=(1101 0001)~2~ and B=(1001 0110)~2~ are stored in sign-and-magnitude format. Show how B is subtracted from A. * Subtraction: B~𝑠~ = $\overline B$~s~ * 𝑆 = 𝐴~𝑠~ ++∨++ B~𝑠~ = 0 ++∨++ 1 = 1, 𝑅~M~ = 𝐴~𝑀~ + ($\overline B$~𝑀~ + 1) * | | | Overflow $\rightarrow$ | 1 | | | | | | | | Carry | | --- | --- | --- | --- | --- | --- | --- | --- | --- | -------- | -------- | -------- | | A~s~ | 1 | | | 1 | 0 | 1 | 0 | 0 | 0 | 1 | A~M~ | | B~s~ | 1 | | + | 1 | 1 | 0 | 1 | 0 | 1 | 0 | ($\overline B$~𝑀~+1) | | R~s~ | 1 | | | 0 | 1 | 1 | 1 | 0 | 1 | 1 | R~M~ | * Since there is an overflow, the value of 𝑅~𝑀~ is final. The sign of R is the sign of 𝐴. * (−81) − (−22) = (−59) # ADD - Arithmetic Operations on Reals * Show how the computer finds the result of (+5.75) + (+161.875) = (+167.625). * Change +5.75 and +161.875 to Excess_127 format * 5.75 * 5.75 = 5 + 0.75 = (101)~2~ + (0.11)~2~= (101.11)~2~ * (101.11)~2~ = (1.0111)~2~ × 2^2^ * S = 0, E = 2 + 127 = 129 = (10000001)~2~ * M = (01110 00000 00000 00000 000)~2~ * 161.875 * 161.875 = 161 + 0.875 = (10100001)~2~ + (0.111)~2~ = (10100001.111)~2~ * (10100001.111)~2~ = (1.0100001111) ×2^7^ * S = 0, E = 7 + 127 = 134 = (10000110)~2~ * M = (01000 01111 00000 00000 000)~2~ * | | S | E | M | | -------- | -------- | --- | -------- | | A | 0 | 1000 0001 | 01110 00000 00000 00000 000 | | B | 0 | 1000 0110 | 01000 01111 00000 00000 000 | * De-normalize the numbers by adding the hidden 1s to the mantissa and incrementing the exponent * | | S | E | Denormalized M | | -------- | -------- | --- | -------- | | A | 0 | 1000 0010 | 10111 00000 00000 00000 0000 | | B | 0 | 1000 0111 | 10100 00111 10000 00000 0000 | * Alignment the exponent by incrementing the lower exponent and rightshift the corresponding mantissa * | | S | E | Denormalized M | | -------- | -------- | --- | -------- | | A | 0 | 1000 0111 | 00000 10111 00000 00000 0000 | | B | 0 | 1000 0111 | 10100 00111 10000 00000 0000 | * Do sign-and-magnitude addition, treating the sign and the mantissa of each number as one integer stored in sign-and-magnitude representation * | | S | E | Denormalized M | | -------- | -------- | --- | -------- | | A | 0 | 1000 0111 | 00000 10111 00000 00000 0000 | | B | 0 | 1000 0111 | 10100 00111 10000 00000 0000 | | R | 0 | 1000 0111 | 10100 11110 10000 00000 0000 | * No overflow in the mantissa, so we normal * | | S | E | Denormalized M | | -------- | -------- | --- | -------- | | R | 0 | 1000 0110 | 01001 11101 00000 00000 0000 | * The mantissa is only 23 bits, no rounding is needed. E = (10000110)~2~ = 134 M = 0100111101. In other words, the result is (1.0100111101)~2~×2^134-127^ = (10100111.101)~2~ = 167.625 * Show how the computer finds the result of (+5.75) + (−7.0234375) = − 1.2734375. * Change +5.75 and −7.0234375 to Excess_127 format * | | S | E | M | | -------- | -------- | --- | -------- | | A | 0 | 1000 0001 | 01110 00000 00000 00000 000 | | B | 1 | 1000 0001 | 11000 00110 00000 00000 000 | * De-normalize the numbers by adding the hidden 1s to the mantissa and incrementing the exponen * | | S | E | Denormalized M | | -------- | -------- | --- | -------- | | A | 0 | 1000 0010 | 10111 00000 00000 00000 000 | | B | 1 | 1000 0010 | 11100 00011 00000 00000 000 | * Do sign-and-magnitude addition, treating the sign and the mantissa of each number as one integer stored in sign-and-magnitude representation * | | S | E | Denormalized M | | -------- | -------- | --- | -------- | | A | 0 | 1000 0010 | 10111 00000 00000 00000 000 | | B | 1 | 1000 0010 | 11100 00011 00000 00000 000 | | **B** | 1 | 1000 0010 | 00011 11101 00000 00000 000 | | R | 1 | 1000 0010 | 11010 11101 00000 00000 000 | | **R** | 1 | 1000 0010 | 00101 00011 00000 00000 000 | * Normalize: decrement the exponent three times and shift the de-normalized mantissa to the left three position * | | S | E | Denormalized M | | -------- | -------- | --- | -------- | | R | 1 |0111 1111 | 01000 11000 00000 00000 00000 | * Round the mantissa to 23 bits * | | S | E | Denormalized M | | -------- | -------- | --- | -------- | | R | 1 |0111 1111 | 01000 11000 00000 00000 000 | * The result is R = − 2^127-127^×(1.0100011)~2~ = − 1.2734375, as expected. ## ADD - There are two ways to perform table-to-expression transformation. What are the two methods? Use them to transform the table to expressions without simplification.[一字不錯考題] | A | B | C | F | | -------- | -------- | -------- | -------- | | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 1 | | 0 | 1 | 0 | 1 | | 0 | 1 | 1 | 0 | | 1 | 0 | 0 | 1 | | 1 | 0 | 1 | 0 | | 1 | 1 | 0 | 0 | | 1 | 1 | 1 | 1 | 1. Sum of Products: AND 1. Consists of up to 2^n^ minterms, each of which is a product (ANDing) of all variables. 2. Each minterm corresponds to a row. If the value of a variable is 0, the complement of the variable appears in the term. 3. The procedure is 1. Find the minterms for each row for which the function has a value of 1. 2. Use the sum (ORing) of the terms in 1. 4. eight minterms: 1. | A | B | C | F | Minterm | | --- | --- | --- | --- | --- | | 0 | 0 | 0 | 0 | m~0~=$\overline{ABC}$ | | 0 | 0 | 1 | 1 | m~1~=$\overline{AB}C$ | | 0 | 1 | 0 | 1 | m~2~=$\overline{A}B\overline{C}$ | | 0 | 1 | 1 | 0 | m~3~=$\overline{A}BC$ | | 1 | 0 | 0 | 1 | m~4~=$A\overline{BC}$ | | 1 | 0 | 1 | 0 | m~5~=$A\overline{B}C$ | | 1 | 1 | 0 | 0 | m~6~=$AB\overline{C}$ | | 1 | 1 | 1 | 1 | m~7~=$ABC$ | 2. Sum the minterms with value 1 F = m~1~ + m~2~ + m~4~ + m~7~ = $\overline{AB}C$ + $\overline{A}B\overline{C}$ + $A\overline{BC}$ + $ABC$ 2. Product of Sum: OR 1. Consists of up to 2^n^ maxterms, each of which is a sum (ORing) of all variables 2. The procedure is 1. Find the mintermsfor each row for which the function has a 0 value. 2. Find the complement of the sum of the terms in 1. 3. Use De Morgan’s rules to change mintermsto maxterms. 3. eight minterms 1. | A | B | C | F | Maxterm | | --- | --- | --- | --- | --- | | 0 | 0 | 0 | 0 | M~0~=$A+B+C$ | | 0 | 0 | 1 | 1 | M~1~=$A+B+\overline{C}$ | | 0 | 1 | 0 | 1 | M~2~=$A+\overline{B}+C$ | | 0 | 1 | 1 | 0 | M~3~=$A+\overline{B}+\overline{C}$ | | 1 | 0 | 0 | 1 | M~4~=$\overline{A}+B+C$ | | 1 | 0 | 1 | 0 | M~5~=$\overline{A}+B+\overline{C}$ | | 1 | 1 | 0 | 0 | M~6~=$\overline{A}+\overline{B}+C$ | | 1 | 1 | 1 | 1 | M~7~=$\overline{A}+\overline{B}+\overline{C}$ | 2. Find the complement of the sum of minterms with value 0 F = M~0~ . M~3~ . M~5~ . M~6~ 3. Use De Morgan’s rules to change the minterms to maxterms F = $ABC$ . $A\overline{BC}$ . $\overline{A}B\overline{C}$ . $\overline{AB}C$ * Function simplification: Karnaughmap Method * Only suitable for less than or equal to 4 variables * Complicated when we have 5 or more variable > [Sum Of Product (SOP) & Product Of Sum (POS)](https://www.electricaltechnology.org/2018/05/sum-of-product-sop-product-of-sum-pos.html)[color=blue] ## [Boolean Algebra and Logic Gates](https://examsdaily.in/wp-content/uploads/2018/08/lgba.png) (Textbook p.564(584)) # Chapter 5 ## Briefly explain how CPU gets memory access through cache. 1. The CPU checks the cache. 2. If the word is found, CPU accesses it immediately; otherwise, CPU copies a block of memory starting with the desired word, and replaces the previous contents in cache. 3. The CPU access the cache and copies the word. > [Wikipedia - CPU Cache](https://zh.wikipedia.org/wiki/CPU%E7%BC%93%E5%AD%98)[color=blue] 1. 當CPU發出memory存取請求時，會先查看cache內是否有請求資料。 2. 如果存在（命中），則不經存取memory直接返回該資料； 3. 如果不存在（失效），則要先把memory中的相應資料載入cache，再將其返回CPU。 ## Distinguish among CD-ROM, CD-R, and CD-RW on the aspects of creation. | Creation | CD-ROM | CD-R | CD-RW | | ----------- | ------ | ---- | ----- | | Master Disk and Mold | o | x | x | | Reflective Layer | o | gold | alloy | | Lands or Pit | A very thin layer of aluminum provides the reflective surface. A protective layer of lacquer is applied and a label is added | X | High-power lasers to create pit | ## A computer has 16 gigabytes main memory and 8-byte word. How many bit does the computer need to address all the memory location? How many connections are needed for data bus? How many connections are needed for address bus? 1. 16GB = 2^4^ * 2^30^ Bytes = 2^3^ * 2^4^ * 2^30^ bits = 2^37^bits 2. 8-byte = 2^3^ * 2^3^ bits = 64 connections 3. 8-byte = 2^3^; Ans: 3 connections ## Distinguish between isolated I/O and memory-mapped I/O 1. Isolated I/O 1. Instructions to read / write memory and I/O devices are different. 用來讀 / 寫記憶體的指令完全不同於用來讀 / 寫輸入 / 輸出設備的指令 4. Each I/O device has its own address which is able to overlap with memory addresses without any ambiguity. 每一個輸入 / 輸出設備有自己的位址，輸入 / 輸出位址可以與記憶體的位址重疊而不會模稜兩可，因為指令本身就不同。 4. Memory-mapped I/O 1. Treat each register in the I/O controller as a word in memory. CPU 將輸入 / 輸出控制器中的每一個暫存器視為記憶體的字組。 6. The same instructions for memory and I/O devices. 所有記憶體指令可以被輸入 / 輸出設備使用 8. Result in a small number of instructions. 優點是指令數量較少 10. But part of memory address space is allocated to registers in I/O controllers. 缺點是記憶體的部份位址空間被配置給輸入 / 輸出控制器中的暫存器 > [Subsystem Interconnection](https://sls.weco.net/node/22752)[color=blue] ## Show one advantage and disadvantage of interrupt-driven I/O over programmed I/O. * Saving CPU time 降低CPU閒置時間 * Data loss might happen 可能造成資料遺失 ## Explain why DMA is efficient to transfer data. It does not need to wait for device to prepare data. 當DMA控制器執行資料傳送時，CPU可以自由地完成其他工作。 ## Give the full names of CISC and RISC, and compare them. 1. Complex Instruction Set Computer * A computer that defines an extensive set of instructions, even those that are used less frequently. 3. Reduced Instruction Set Computer * A computer that uses only frequently used instructions. ## Give the requirements of true parallel processing. * Parallel processing requires multiple processors and all the processor works simultaneously in the system. From: [Parallel Processing](https://binaryterms.com/parallel-processing-in-operating-system.html) P.S. Several tasks can be performed simultaneously. Applications of parallel processing: •Scientific computation •Large matrices multiplication •Computational fluid dynamics # Chapter6 ## Compare multiprocessor system with distributed system in the following aspects: CPU clock rate, memory, operating system, and communication. | Aspects | Multiprocessor Systems | Distributed Systems | | ---------------- | ---------------------- | ----------------------- | | CPU clock rate | same | different | | Memory | same | different | | Operating System | same | different | | Communication | through shared memory | through message passing | | Aspects | Multiprocessor Systems | Distributed Systems | | ---------------- | ---------------------- | ----------------------- | | CPU clock rate, memory, operating system | 共享相同 | 各自不同 | | Communication | 分享記憶體 | 訊息傳遞 | ## Compare partitioning, paging and segmentation. | partitioning | paging | segmentation | | -------- | --- | -------- | | | internal fragmentation | external fragmentation | | 大小不一定相同 | 大小一致 | 大小不一 | ## Briefly describe virtual memory and show the applicable memory management technique * Make process of which size is larger than physical memory executable. 允許當程式大小＞實體記憶體大小，而程式仍能執行。 (A form of memory organization that allows swapping of programs between memory and magnetic storage to give the impression of a larger main memory than really exists.) * Demand paging and demand segmentation. * For example, a memory size of 10 MB can execute 10 programs, each of size 3 MB, for a total of 30 MB. * At any moment, 10 MB of the 10 programs are in memory and 20 MB are on disk. There is therefore an actual memory size of 10 MB, but a virtual memory size of 30 MB. ## Distinguish program, job, and process. | Program | Job | Process | | -------- | -------- | -------- | | Non-active set of instructions stored in disk | A program become a job from the moment it is selected for execution until it has finished running | A program in execution or a job in memory | ## What are the five states of a process? Briefly describe them. 1. New 開始初始化一個行程 2. Running 指令正在執行 3. Waiting 等待某一特定事件的發生 4. Ready 該行程正等待指定一個處理器 5. Terminate 該行程完成執行 ![](https://i.imgur.com/gC22U0H.png) ## Describe the events of state transition in the lifecycle of processes. 1. New: the process has been loaded into memory by the job scheduler 2. Ready: the process is ready to be executed by CPU 3. Running: the process is executing by CPU 4. Waiting: the process waits for the completion of some event 5. Terminate: the process ends and leaves from the memory ## ADD - CPU Scheduling Algorithms not textbook p. 3-44 Five criteria of scheduling •CPU utilization:Process execution time / Total time •Throughput:The number of process completed in unit time •Waiting time:Sum of the waiting time for process in the ready queue for execution •Turnaround time:Process finished time –process entered system time •Response time:Command responded time –command entered time # Chapter 7 ## A network is a combination of hardware and software. What are their main tasks? * The hardware consists of the physical equipment that carries signals from one point in the network to another. * The software consists of instructions that make the services we expect from a network possible. ## What is protocol layering? What are the main advantages of protocol layering? 1. Protocol Layering * The idea of using a set of protocols to create a hierarchy of rules for handling a difficult task. 2. Advantages * Separate the services from the implementation * Simplify the system ## Give the five layers in TCP/IP protocol suite. 1. Physical Layer (實體層) 2. Host-to-network (or data link, 資料連結層) 3. Internet (network, 網路層) 4. Transport(傳輸層) 5. Application(應用層) ## Give the four addresses used in the TCP/IP protocol suite. * No physical layer addresses * The unit of data exchange at physical layer is a bit 1. Host-to-network (or data link, 資料連結層)-MAC(Media Access Control Address, 媒體存取控制位址) addresses, 2. Internet (network, 網路層)-IP address (IP位址) 3. Transport(傳輸層)- port numbers(埠號) 4. Application(應用層)-name ## What are the two application layer paradigms? 1. Client-server paradigm(主從式派點) 2. Peer-to-peer paradigm(對等式派點) ## Give two advantages for peer-to-peer application layer paradigm. 1. Easily scalable 2. Cost-effective in eliminating the need for expensive server ## Give two reasons about the popularity and growth of the Web (WWW). * Distributed(分散) * Each web server can add a new web page without overloading a few servers. * Linked(鏈結) * Linking allows one web page to refer to another web page stored in another server. ## What is web client? Give its name and components. 1. Name: Browser （瀏覽器） * A variety of vendors offer commercial browsers that interpret and display a web page, and all of them use nearly the same architecture. 2. Components: * controller(控制器) * client protocols(客端協定) * interpreters(直譯器) ## Give the five components in the FTP application. * The client has three components: * user interface * client control process * the client data transfer process * The server has two components: * the server control process * the server data transfer process ## What is the main problem in TELNET? What is the solution of such problem? * Problem: * We cannot have a specific client/server program for a set of common scenarios. * Solution: * remote login(遠端登錄) application ## How can SSH provide a secure network? * Connecting SSH client and SSH server ## What is the main purpose of having the domain name system (DNS)? Help other application program. ## Use csie.fju.edu.tw to explain the three parts of a name in the name space. 1. edu: The first part can define the nature of the organization 2. fju: The second part can define the name of the organization 3. csie: The third part can define the departments in the organization 4. tw: Country domain ## What is the main task of transport-layer protocol? What kind of communication do the transport layer services use? What is used to achieve such kind of communication? 1. The transport-layer protocol is responsible for delivery of the message to the appropriate process. * Provide process-to-process communication. 2. The network layer. 3. The network layer is responsible for communication at the computer level, but it can deliver the message only to the destination computer. ## Briefly describe the user datagram protocol and transmission control protocol. 1. User Datagram Protocol (UDP,用戶資料元協定) * Connectionless(無連接), unreliable transport protocol * Simple protocol using a minimum of overhead * E.g., send simple message without concern of reliability * UDP packets are known as user datagrams * 8 bytes header * Less than 65535 bytes since each packet is stored in IP datagram with the total length of 65535 byte 2. Transmission Control Protocol (TCP,傳輸控制協定) * Connection-oriented (連接導向式), reliable protocol * Explicitly defines connection establishment, data transfer, and connection teardown phases to provide connection-oriented services * There is a connection (relationship) between all packets (segments) belonging to the same message (from application layer) * TCP groups a number of bytes together into a packet called a segment * Each segment has a header for control purposes. * Segments are encapsulated into IP datagram and transmitted. * Use sequence number to define the order of segments * Related to the number of bytes in each segment * For a 6000 bytes message, the first segment has sequence number 0, the second one has sequence number 2000, and the third one has sequence number 400 ## UDP is connectionless, unreliable transport protocol, whereas TCP is connection-oriented, reliable protocol. Explain the meaning of connectionless, connection-oriented, unreliable, and reliable. * connectionless * The network layer treats each packet independently (like the way the post office does with the letters). * In other words, there is no relationship between packets belonging to the same transport-layer payload. * connection-oriented * There is a connection (relationship) between all packets (segments) belonging to the same message (coming from the application layer). * unreliable * The packets can be corrupted, lost, duplicated. * In other words, the network layer provides a best-effort delivery, but there is no guarantee that a packet will reach the destination as we expect. * reliable * Some measures speak directly to a system’s reliability, most notably, mean time between failures. ## What are the three main services provided by network layer? Provide service to transport layer 1. Packetizing(封包封裝) 2. Packet delivery(封包遞送) 3. Routing(路由) ## Please briefly describe the function of routing protocol. Help the routers coordinate their knowledge about the neighborhood and to come up with consistent tables to be used when a packet arrives. ## What are the common notations of IPv4 and IPv6 addresses? * IPv4: Three common notations * binary * dotted-decimal * hexa-decimal * IPv6: * binary (computer) * colon-hexadecimal(human) ## What are the level hierarchy in each of the IPv4 and IPv6? * IPv4 * prefix(前綴) defines the network * suffix (後綴) defines the nodes * length depends on the site (organization) * IPv6 * site (organization) * subnetwork * connection to the host ## What kind of communication do the data-link layer services use? Node-to-node. ## Which layers in TCP/IP protocol suite are node-to-node communication? Physical Layer. ## Please list the two ways of transmission, and the four conversions in physical layer. * Transmission Media: Two categories 1. Guided (有界) media 2. Unguided (無界) media * Physical Layer: * Digital Transmission(數位傳輸) 1. Digital-to-digital conversion(數位數位轉換) 2. Analog-to-digital conversion(類比數位轉換) * Analog Transmission(類比傳輸) 1. Digital-to-analog conversion (數位類比轉換) 2. Analog-to-analog conversion(類比類比轉換) ## Give the two categories of transmission media 1. Guided (有界) media 2. Unguided (無界) media ###### tags: `計算機概論`

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.