In class, we saw a compression algorithm called WindowEncode that was used to en
ID: 3841710 • Letter: I
Question
In class, we saw a compression algorithm called WindowEncode that was used to encode fixed density binary strings of length n with k ones. The algorithm below, BlockEncode, is a similar algorithm for compressing fixed density binary strings of length n with k ones. We will assume for simplicity that n/k is a power of two, so that n/k is an integer, and log(n/k) is also an integer. Block Encode (bitstring s of length n with k ones) Break s into k blocks each of size n/k. For each block B in s, For each one in B, Write a 1 Write the position of the one within B. Write a 0. How would s = 001000000000000010010000 be encoded by BlockEncode? On an input s of length n with k ones, what is the maximum number of bits in the output of BlockEncode(s), in terms of n and k? Justify why this is the maximum. Suppose we know that the string t = 101111010100000 is the output of BlockEncode(s), where s is a binary string of length n = 24 with density k = 3. Find an input string s so that Block Encode(s) = t. Is this the only possible s?Explanation / Answer
Solution:
String s = 001000000000000010010000 encoded by Block Encode.
= 101000100010110
Thus the encoded string is 101000100010110
(b) On an input s of length n with k ones, what is the maximum number of bits in the output of BlockEncode(s), in terms of n and k? Justify why this is the maximum.
Solution:
= klog(n/k)+2^k
Thus the maximum number of output is klog (n/k)+2^k
(c) Suppose we know that the string t 101111010100000 is the output of BlockEncode(s), where s is a binary string of length n 24 with density k 3. Find an input string s so that Block Encode(s) t. Is this the only possible s?
Solution:
Consider string t = 101111010100000.
s is binary string length of n = 24
density k =3
Input string for the 101111010100000 is 000101001000000000000000.
Thus the input string s for the BlockEncode is 000101001000000000000000
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.