Show your work on all problems. Without it, we can't give partial credit.
Problem 1
Consider the following simple compression scheme based on run-length
encoding. The scheme encodes a file in a sequence of 10-bit "chunks".
In a 10-bit "chunk" we can
represent some single bit repeated up to 255 times by writing
a leading 0, followed by the bit to repeat, followed by an 8-bit binary number
representing the number of repetitions (a run-length encoding).
Alternatively, we could in this
10-bit "chunk" represent a 9-bit sequence by writing a leading 1, followed
by the 9 bits of the sequence. In this scheme, for more than 9 repetitions of
a bit, it makes sense (because it makes the encoded file smaller)
to use the run-length encoding.
Consider compressing with this scheme a simple bit sequence consisting of n repetitions of the bit 0 followed by 90 bits of 0's and 1's that have no repetitions longer than 8. What does the value of n have to be to get a compressed representation that is 80% the length of the original sequence?
Problem 2
Brookshear, Chapter One Review Problem 60, pg. 75.
Problem 3
As we discussed in lecture, in some situations it is sufficient to
detect errors in data, and in others we need to be able to
correct errors. Give one example of a situation where error
detection is enough, and one example where error correction is necessary.
Justify your answers.
Problem 4
Suppose we want to store a 64-bit piece of data, and we want to use the
parity method to detect errors in the data. One way to do it is to add
a single parity bit that holds the parity of the entire 64-bit value. Another
way to do it is to divide the 64-bit data into two 32-bit halves, and then
to add two parity bits, one for each half. Using two parity bits has the
disadvantage that it makes the file slightly bigger (66 vs. 65 bits). Can
you think of an advantage that the two-parity-bits method might have over
the one-parity-bit method?