The algorithm below BlockEncode is an algorithm for compress

The algorithm below, BlockEncode, is an 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.

a) How would s = 001000000000000010010000 be encoded by BlockEncode?

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.

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 BlockEncode(s)=t. Is this the only possible s?

Solution

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