1
$\begingroup$

Let F be a deterministic compression function that takes fixed length 128 bit inputs and outputs 8 bits. Each input to the function has 128 bits of entropy, does that mean that the output byte has 128 bits of entropy ?

$\endgroup$
  • $\begingroup$ No, it's not possible to have 128 bits of entropy in 8 bits of data. 01011001 and 01011001 are identical, regardless of how random the data was before fed into your compression function. $\endgroup$ – MechMK1 Mar 26 at 13:39
  • $\begingroup$ How does the original entropy "disappear" when the 128 bits are distilled down to eight, can you formalize that into an answer ? $\endgroup$ – William Hird Mar 26 at 13:51
  • 1
    $\begingroup$ No, because poncho's answer already covers that pretty well. The idea is that X bits can never have more entropy than X bits. $\endgroup$ – MechMK1 Mar 26 at 14:00
  • 3
    $\begingroup$ Entropy is not something that "appears" or "disappears". Entropy is a property of a probability distribution. Which is also why the statement "Each input to the function has 128 bits of entropy" is nonsensical. An individual value has no entropy. The distribution it is drawn from does. $\endgroup$ – Maeher Mar 26 at 14:01
  • $\begingroup$ OK, thank you. Information Theory 101 :-) $\endgroup$ – William Hird Mar 26 at 14:03
4
$\begingroup$

Of course not; 8 bits have a maximum of 8 bits of entropy. There does not exist a probability distribution over the 256 possible values of those 8 bits that gives an entropy value of more than 8.

What this means is that your function can have more entropy on the input than the output. This is not uncommon, and typically happens if you have a function with fewer possible outputs than inputs (the only exception is if the probability distribution that the input occurs has some inputs with zero probability).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.