Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Hoffman coding in 8bit sequence

  1. Jan 22, 2012 #1
    A data file contains a sequence of 8-bit characters such that all 256 characters are about as common: the maximum character frequency is less than twice the minimum character frequency. Prove that Huffman coding in this case is not more efficient than using an ordinary 8-bit fixed-length code.

    Any help please?
  2. jcsd
  3. Jan 22, 2012 #2


    User Avatar
    Homework Helper

    This isn't very clear: characters are "about as common" with "maximum frequency less than double minimum frequency". This could mean all but two characters have equal likelyhood with probability of 1/256, one of the two characters probability could be (4/3 x 1/256) = 4/768 the other characters probability (2/3 x 1/256) = 2/768. Here it's pretty clear that hoffman coding would result in expansion of data since 254/256 of the time, you don't have hoffman compressable data. On the other extreme, 128 of the characters could be about twice as likely as the remaining 128 characters, but this doesn't match the description "about as common". Still, what would the hoffman coding be for this case?
    Last edited: Jan 22, 2012
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook