EE/Ma 127b Error-Correcting CodesApril 11, 2007R. J. McEliece162 MooreHomework Assignment 2 (Incomplete)Due (in class) 9am April 13, 2007Reading: Lecture 0, Lecture 1, Lecture 2, Lecture 3Problems to Hand In:Problem 1. Find the free distance, the Hilbert Series, and the dimensions δLof thedegree L polynomial subcodes for the following convolutional codes.(a) G =°1 + w + w21 + w3¢,(b) G =µ1 + w w 11 + w2+ w31 + w + w2+ w30∂.Problem 2. Consider a discrete memoryless channel with input alphabet {0, 1}, andoutput alphabet {A, B, C, D} with transition probability matrixP =µA B C D0 p q r s1 s r q p∂.where p + q + r + s = 1. Thus Pr{Y = B|X = 0} = p(B|0) = q, for example.If y = (y1, . . . , yn) is the channel output, the likelihood of an input x = (x1, . . . , xn) isp(y|x) =nYi=1p(yi|xi).Now consider the following “metric matrix”:M =µA B C D0 0 1 2 41 4 2 1 0∂.Find values of p, q, r, and s so thatargmaxx∈Sp(y|x) = argminx∈SnXi=1M(xi, yi).for any set S of binary vectors and any fixed y.Problem 3. Find the flow from A to B in the trellis below, using each of the semirings“Sum-Product,” ”Min-Product,” ”Max-Pro duct,” ”Min-Product,” ’Min-Sum,” and ”Max-Sum.”Some Important SemiringsK “(+, 0)” “(·, 1)” short name4. [0, 1) (+, 0) (·, 1) sum-product5. (0, 1] (min, 1) (·, 1) min-product6. [0, 1) (max, 0) (·, 1) max-product7. (−1, 1] (min, 1) (+, 0) min-sum8. [−1, 1) (max, −1) (+, 0)
View Full Document
Unlocking...