Message from afar

Sending messages across deep space is slow, so compression algorithms are used to minimise the number of bits required to transmit. One commonly used form of compression is known as Huffman encoding where provided the sender and receiver share a common lookup reference, messages can be exchanged using fewer bits than would be required for the full byte equivalent.

For your trip, personal messages between crew and their friends and family back home are sent over a compression system that has a reduced character set. Rather than allowing every upper and lower case of the latin alphabet, or for extended/non-latin characters, there are only 40 characters used. These 40 characters are converted to binary data according to the following table…

A 0010
E 0000
T 0001
I 0011
N 0100
O 0101
S 0110
H 0111
R 10000
D 10001
L 10010
U 10011
C 10100
M 10101
F 10110
B 10111
F 1100000
Y 1100001
W 1100010
G 1100011
P 1100100
B 1100101
V 1100110
K 1100111
Q 1101000
J 1101001
X 1101010
Z 1101011
0 1110000
1 1110001
2 1110010
3 1110011
4 1110100
5 1110101
6 1110110
7 1110111
8 1111000
9 1111001
_ 1111010
. 1111011
' 1111100
* 1111111

An example

Consider the following hexadecimal that represents a binary message c6ab1f512c3fff.

This hexadecimal represents the following binary data: 11000110101010110001111101010001001011000011111111111111.

Read left to right through the bit stream. Since the lookup table requires a minimum of 4 bits, you can start with considering 4 bits and then extend it if you need more values to determine the decoded character.

In this case, the first four bits, 1100 are ambigous. There are 8 characters that could match, all of which use 7 bits in the lookup table, so examine the 7 bits which are 1100011 and note this decodes to the letter G.

Move on to the next four bits, 0101. This converts immediately to the letter O.

Continuing to move through the bit stream, will decode the message as follows:

1100011       => G
0101          => O
0101          => O
10001         => D
1111010       => _
10001         => D
0010          => A
1100001       => Y
1111111111111 => *

The * is a special character that represents end of message, and can be ignored from the final decoded value.

Therefore, the final decoded message was GOOD_DAY.

Your input data

Your input data contains the hexadecimal representation of a message you have received. Decode it using the lookup table above to find the answer.