CODEWITHSUNDEEP
algorithmencodingcharacter-encodingcompression
Jason
Jason

Reputation: 25

Finding uniquely decodable codes

Which of the following codes are uniquely decodable?

code 1 code 2 code 3 code 4 A 0 0 1 1 B 100 1 01 01 C 10 00 001 001 D 11 11 0001 000

For those that are uniquely decodeable, give the encoding of 1000000000000

/*********************************/

So I have found that code 3 and 4 are prefix free and instantaneously decodable. It's easy to give the encoding with code 4 as ADDDD, but I'm lost how I would do it for the third one since it doesn't seem to be able to match up to the string at all. Am I wrong somehow that code 3 is uniquely decodable?

Upvotes: 0

Views: 533

Answers (1)

Mark Adler
Mark Adler

Reputation: 112284

Code 3 is uniquely decodable, but it is not complete. Therefore you can come up with sequences of bits that are not decodable with Code 3. E.g. 0000. In fact, you could make the code complete by adding the code 0000 for, say, E.

Code 4 on the other hand is complete, and so any sequence of bits can be decoded. (Though the sequence might end in the middle of a code.)

Upvotes: 2

Related Questions