this is a very common question but I think I’m posting it in a different way.

Suppose that we have 256 different possible messages with uniform distribution to be represented in a binary code. Then it would be necessary at least 8 bits in each word to represent all the 256 = 28 possibilities. Nevertheless, some of those words may be compressed in fewer than 8 bits. For example, 00000000 may be compressed in log(8) + O(1) bits, and as O(1) becomes assintotically irrelevant, occurrences of 00000000 can be assintotically represented in nearly log(8)=3bits. This in obvious contradiction with the minimum of 8 bits required for this codification and, in fact, violates the prefix-code requirement, as this 3 bits compressed word is a prefix for other words in the codification.

My question is how we can bring together both notions of entropy and complexity in dealing with the above situation, as they seem contradictory.