CODEWITHSUNDEEP
algorithmmathcompressionproof
benji_r
benji_r

Reputation: 555

compress 2-bit numbers and save 1 bit use compression scheme

I want to create a compression scheme for 2-bit numbers such that it will reduce the size of any sequence by at least one bit. How can I prove this is not possible?

Upvotes: 0

Views: 1055

Answers (1)

templatetypedef
templatetypedef

Reputation: 373002

There are 4 possible two-bit numbers and 3 possible shorter bit sequences (the empty sequence of bits and the sequences 0 and 1). By the pigeonhole principle, this means that any mapping from two-bit sequences to shorter sequences must have at least two sequences compressed to the same shorter sequence. As a result, when you want to decompress this shorter sequence, you will not be able to do so because you won't know which of the original two-bit sequences it came from.

This can be generalized to show that n-bit sequences cannot be losslessly compressed to bit sequences of length less than n. This earlier answer details why this is.

Hope this helps!

Upvotes: 3

Related Questions