1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Limit of compression (source coding theorem)

  1. Apr 4, 2009 #1

    gop

    User Avatar

    Hi

    The source coding theorem says that one needs at least N*H bits to encode a message of length N and entropy H. This supposedly is the theoretical limit of data compression.

    But is it? Or does it only apply to situations where only the frequency (probability) of a given symbol is known?

    For example, If I know that the symbol x is always followed by the symbol y (or that this happens with a very high probability) couldn't I use this to construct a compression algorithm that needs fewer bits than N*H?

    thx
     
  2. jcsd
  3. Apr 4, 2009 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    If x is (almost) always followed by y, then that lowers the entropy. It's already taken into account.
     
  4. Apr 4, 2009 #3

    gop

    User Avatar

    But if I have something like this

    p(x,y,z)= (1/3,1/3,1/3)

    then I have entropy 1.585. But now I could have p(y|x) = 1/2 or p(y|x) = 1 as long as p(y|z)=1-p(y|x) the overall probability p(x,y,z) stays the same. So I have the same entropy. But in the case of p(y|x)=1 I can only use two symbols say p(xy,z) = (1/2,1/2) which has entropy 1.

    I guess I'm missing something obvious here but...

    thx
     
  5. Apr 4, 2009 #4

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Yes, your formula doesn't apply unless the choices are made independently.
     
  6. Apr 5, 2009 #5

    gop

    User Avatar

    ok I got it if I use conditional probabilities I need to use another model and another way to compute the entropy rate.

    thx
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Limit of compression (source coding theorem)
  1. Limit of this ? (Replies: 11)

  2. Code Cracking (Replies: 5)

  3. Cyclic codes (Replies: 4)

  4. An Unbreakable Code? (Replies: 10)

  5. Theorem for limits? (Replies: 5)

Loading...