Help on understanding 136 Variable Length Code Unpack
Back to General discussions forum
Could any one help me understand the logic of the example in problem #136, Variable Length Code Unpack?
I've already completed the previous problem, #135, which is a counterpart to this one. Here's my understanding of both:
#135, encoding
- # 135, variable length code, is about encoding a regular string, by mapping
each character to a binary value, as per the encoding table given in the
problem statement.
- The given encoding table is 28 different possibilities
- After mapping each letter to binary, group all of the mappings into octets. (groups of 8)
- Convert the octet from binary to hexadecimal
#136, decoding
- # 136, variable length code unpack, is for decoding a message, by mapping a 5-bit encoding to a letter.
- Use the same table from the previous problem to decrypt the message.
However, the input is a base-32 number. How are we're supposed to map a character, which could be one of 32 values, to a table offering 28?
And how does this compressed sequence: 0SA14NH2CG2K8GH1GOD604, evaluate to the
5-bit sequence from the example?
I can see 5-bit result of that operation:
00000 11100 01010 00001 00100 10111 10001 00010 01100 10000 00010 10100 01000 10000 10001 00001 10000 11000 01101 00110 00000 00100,
is the same as the raw (ungrouped) output from the previous problem:
0000011 10001 01000 001001 00101 11 10001 000100 11 001000 0000101 01000 10001 0000100 01000 011 000011 000011 01001 10000 0000100.
You just have to remove the spaces. But I'm not sure what to do with this information.
Anyway, could anyone give me a pointer or two?
Thanks.
Hi! Thanks for your message!
>is the same as the raw (ungrouped) output from the previous problem:
Yes it is the same bit string. Of course without spaces as bit strings could not have spaces - just zeroes and ones.
>But I'm not sure what to do with this information.
We need to convert the proposed input to bit string (as you have already done) - convert letters
to 5-bit chunks and then glue them together.
Now we need to split this bit string into variable length codes using the same code-table as for encoding. At first this may look strange since the codes are of variable length, but as none of them has the starting bits which could be misunderstood as some other code, there is only one way to decode.
For example, let us try with the line you have shown above:
00000111000101000001001001011110001...
It starts with five zeroes. There is no code in the table consisting of only less than 5 zeroes.
Moreover there are only two codes which have 5 zeroes followed by one. So it is obviously 0000011.
Let us write down this w and proceed:
.......1000101000001001001011110001...
The next code starts with 1 and there are only few of them. You can easily find out that
only one (10001) is suitable again... Let us write down the letter o and remove these
bits:
............01000001001001011110001...
And so on, and so on.