Grading Key: CS 231, Lab 5 (Spring 2000) ---------------------------------------- 1. Representing text 1. The text reads as "Penguin power!" in ASCII In binary, it is: 0101 0000 0110 0101 0110 1110 0110 0111 0111 0101 0110 1001 0110 1110 0010 0000 0111 0000 0110 1111 0111 0111 0110 0101 0111 0010 0010 0001 2. With the specified parity bits, the binary version is (underlined bits changed): 0101 0000 0110 0101 1110 1110 1110 0111 1111 0101 0110 1001 1110 1110 - - - - 1010 0000 0111 0000 0110 1111 0111 0111 0110 0101 0111 0010 0010 0001 - 3. The message would be mis-interpreted in extended ASCII as "Peīēõiī šower!" [should display correctly on a PC] or "Pe”¨›i” ¶ower!" [should display correctly on a Macintosh] 2. Fonts and texts 1. 2^35th symbols, or roughly 32 billion. Why? Because each of the 35 = 5 * 7 pixels can be either on or off (black or white). This is more than in Unicode (16 bit version) or in any other reasonable alphabetic code by an extreme factor. 2. The break-even point can be computed by comparing the number of bits used for the "graphic" version versus those used for the "font+codes" version. We have: 35 n = 35 * 128 + n * 8 27 n = 35 * 128 n = (35 * 128) / 27 n = 165.9259259259259 In other words, the break-even point is between a length of n=165 and n=166. (almost all points were given if 7 bits was used for ASCII instead of 8 bits as stated in the problem; 7 bit usage yields n = 160). 3. Simple graphics 1. The graphic reads "Percy", written in a 4-by-8 grid font: +--------------------+ |## | |# # # # | |# # # # ### ### # # | |## ### # # # # | |# # # # # | |# ## # ### # | | # | | # | +--------------------+ 4. Color graphics 1. The raw pixel information takes up 30 * 40 * (16 / 8) = 2400 bytes, dividing by 8 for eight bits per byte. 2. Using a 75-color palette, we have: (75 * 16) + (30 * 40 * 7) bits = 9600 bits = 1200 bytes This is a savings of 50% (i.e., 1200 vs 2400 bytes). An alternative representation of the palette would include the indexing values in the table itself; then the calculation looks like this: (75 * (7 + 16)) + (30 * 40 * 7) bits = 10,125 bits = 1266 bytes This is a savings of about 47% (i.e., 1266 vs 2400 bytes). (Either answer counts as correct.) 3. Using an n-bit palette we would have the following equivalence (here the square brackets indicate rounding up to the nearest integer value): 30 * 40 * 16 = (n * 16) + (30 * 40 * [log_2(n)]) 1200 = n + 75 * [log_2(n)] At this point we can resolve the equation by noting that various ranges for the value n correspond to different values for [log_2(n)]. We have: 33 <= n <= 64 [log_2(n)] = 6 65 <= n <= 128 [log_2(n)] = 7 129 <= n <= 256 [log_2(n)] = 8 257 <= n <= 512 [log_2(n)] = 9 513 <= n <= 1024 [log_2(n)] = 10 So for n = 512 and n = 513 we have: 1200 > 512 + 75 * 9 = 1187 1200 < 513 + 75 * 10 = 1263 Thus the equation resolves at n = between 512 and 513 bits. Using the alternative representation including the indices in the palette itself, we would have: 30 * 40 * 16 = (n * (16 + [log_2(n)])) + (30 * 40 * [log_2(n)]) 1200 = n + (n x)/16 + 75x where x = [log_2(n)] Referring to the table above we have for n = 256 and n = 512: 1200 < 256 + (256 * 8)/16 + 75 * 8 = 984 1200 < 512 + (512 * 9)/16 + 75 * 9 = 1475 Thus n is between 256 and 512, so x = [log_2(n)] = 9 and we can solve as follows: 1200 = n + (n * 9)/16 + 75 * 9 = n + n * (9/16) + 675 = n * (1 + (9/16)) + 675 525 = n * (25/16) 525 = n * (25/16) 336 = n 5. Run-length encodings 1. The run-length encoding of 00 00 00 00 00 FF FF 00 A1 A1 A1 A1 00 00 00 00 00 A1 A1 FF FF FF 00 00 is: 5 00 2 FF 1 00 4 A1 5 00 2 A1 3 FF 2 00 2. The expanded version of the run-length encoding: 1 00 1 A1 1 00 1 B2 2 C0 1 FF 1 A1 2 32 is: 00 A1 00 B2 C0 C0 FF A1 32 32 The RLE or compressed version is actually longer than the expanded version (24 nibbles versus 20 nibbles). This is because there were not enough runs in the "expanded" version to take advantage of the repetition counts. 6. Sound sampling 1. 736.83 MBytes. 44,100 samples/second * 16 bits/sample * 1 bytes/8 bits * 2 channels * 60 seconds/minute * 73 minutes = 772,632,000 bytes 772,632,000 bytes / (1024 * 1024 bytes / Mbyte) = 736.83 MBytes. 2. Every second of monophonic sound will take 10,000 bytes. With 1024 bytes, we will be able to record 9.76 seconds, or 0.1628 minutes of sound. 7. Digital representation of omelettes 1. For the asparagus-jack cheese-tomato omellete we have: ASCII method: 24 bits Hex method: 12 bits binary method: 16 bits 2. For the given probability distribution, we have the following expected length of representation for an "average omellete": ASCII method: (10%*0)+(30%*8)+(40%*16)+(10%*24)+(10%*32) = 14.4 bits Hex method: (10%*0)+(30%*4)+(40%* 8)+(10%*12)+(10%*16) = 7.2 bits binary method: (10%*16)+(30%*16)+(40%*16)+(10%*16)+(10%*16) = 16 bits 3. With 5-8 ingredients per omellete, the binary representation would be better, since it gives a fixed 16 bits per omelette, whereas the Hex version would give between 20 and 32 bits per omellete.