Show your work on all problems. Without it, we can't give partial credit.
Problem 1
Consider the simple compression scheme based on run-length
encoding
that we looked at in lecture. Recall that in a 10-bit "chunk" we could
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 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
Brookshear, Chapter One Review Problem 7, parts a and d, pg 71.
Problem 4
Brookshear, Chapter One Review Problem 58, pg 75.
Problem 5
Brookshear, Chapter Two Review Problem 5, pg. 108. Assume the machine
has a subtraction instruction, unlike Brookshear's machine of Appendix C.)
Problem 6
Brookshear, Chapter Two Review Problem 11, pg. 109.