1. Not finding help here? Sign up for a free 30min 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!

Explain hamming distance satisfies the triangle inequity

  1. Nov 6, 2013 #1
    Hamming distance satisfies the triangle inequity that is for all x, y, u in c such that d(x,y) <= d(x,u) + d(u,y) where c is a code. Also when does the equality hold?

    My approach is
    Turning x to u by changing at most d(x,u) letters and turning u to y by changing at most d(u,y) letters. So turning x to t will change no more than d(x,u) + d(u,y) letters.


    By looking at the following example, x = 001111, y = 111111, z = 011111. The equality holds when changing x to y, z is just a intermediate step, the equality holds.

    Does this make sense?

    If not, how should I approach this?
     
    Last edited: Nov 6, 2013
  2. jcsd
  3. Nov 7, 2013 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You have the right idea, but you might state it more precisely. If we define ##x_n##, ##y_n##, and ##u_n## to be the ##n##'th letter of ##x##, ##y##, and ##u##, respectively, and ##N## is the code length, then we have
    $$d(x,y) = \sum_{n=1}^{N} |x_n - y_n|$$
    and similarly for ##d(y,u)## and ##d(x,u)##. Proving the triangle inequality is therefore equivalent to proving that
    $$\sum_{n=1}^{N} |x_n -y_n| \leq \sum_{n=1}^{N} |x_n - u_n| + \sum_{n=1}^{N} |u_n - y_n|$$
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Explain hamming distance satisfies the triangle inequity
  1. Triangle inequality (Replies: 2)

  2. Triangle Inequality (Replies: 2)

Loading...