Recall that the triangle inequality for the Hamming distance says that d(a, b) + d(b, c)...

 

Transcribed Image Text:

Recall that the triangle inequality for the Hamming distance says that d(a, b) + d(b, c) ≤ d(a, c). Here a, b and c are q-ary words of length n. We will say that b lies between a and c if equality holds in the above formula, i.e., d(a, b) + d(b, c) = d(a, c). The purpose of the next four exercises is to discover and prove a formula for the number of words that lie between a and c. (3) How many words lie between a and a? (4) Assume q = 2 and n = 3. How many words lie (i) between (0,0,0) and (1, 1, 1)? (ii) between (0,0,0) and (1,1,0)? (iii) between (0, 0, 0) and (1,0,0)? (5) Suppose q = 2, a and c are binary words of length n and d(a, c) = d. Based on your answers in Problems 3 and 4, guess a formula for the number of binary words of length n lying between a and c. Prove this formula. (6) We now allow q to be arbitrary and ask the same question as in Problem 5. Given q-ary words a and b of length n and at Hamming distance d, how many q-ary words of length n lie between a and c? Prove your answer. (7) How many binary words of length 6 are at Hamming distance (a) at Hamming distance 6 from (1,0, 1, 0, 1, 0)? (b) at Hamming distance 5 from (1, 0, 1, 0, 1, 0)? Recall that the triangle inequality for the Hamming distance says that d(a, b) + d(b, c) ≤ d(a, c). Here a, b and c are q-ary words of length n. We will say that b lies between a and c if equality holds in the above formula, i.e., d(a, b) + d(b, c) = d(a, c). The purpose of the next four exercises is to discover and prove a formula for the number of words that lie between a and c. (3) How many words lie between a and a? (4) Assume q = 2 and n = 3. How many words lie (i) between (0,0,0) and (1, 1, 1)? (ii) between (0,0,0) and (1,1,0)? (iii) between (0, 0, 0) and (1,0,0)? (5) Suppose q = 2, a and c are binary words of length n and d(a, c) = d. Based on your answers in Problems 3 and 4, guess a formula for the number of binary words of length n lying between a and c. Prove this formula. (6) We now allow q to be arbitrary and ask the same question as in Problem 5. Given q-ary words a and b of length n and at Hamming distance d, how many q-ary words of length n lie between a and c? Prove your answer. (7) How many binary words of length 6 are at Hamming distance (a) at Hamming distance 6 from (1,0, 1, 0, 1, 0)? (b) at Hamming distance 5 from (1, 0, 1, 0, 1, 0)?

Answer rating: 100% (QA)

Solution S No words lie 22 n 3 110 010 from dca a 0 000 000 1190 0... View the full answer