EE/Ma 127c Error-Correcting Codesdraft of April 16, 2001R. J. McEliece162 MooreHomework Assignment 2—Final VersionDue (in class) 9am April 20, 2001Reading: Handout “The Forward-Backward Algorithm”Handout “The optimal decoding of linear codes for mimimizing symbol error rate.”“The Generalized Distributive Law,” (Esp. Page 326, column 2 – p. 327, col.1)Problems to Hand In:Problem 1. Consider the following weighted trellis, like the one I belabored in class onApril 11.AB1242284281212421124(a) Compute the αi’s and βi’s.(b) Find the value of the flow from A to B through each edge and vertex.(c) Use the ”log” forward-backward algorithm using the approximation log(x + y) ≈max(log x, log y ), to compute the same flows as in part (a).Problem 2. In class on April 13, I showed thatlog(x + y) = max(log x, log y)+f(∆),where f(∆) = log(1 + e−∆), and ∆ = |log x −log y|. A two-bit approximation to f(∆) isof the formf(∆) ≈y1if 0 ≤ ∆ < ∆1y2if ∆1≤ ∆ < ∆2y3if ∆2≤ ∆ < ∆3y4if ∆3≤ ∆.(Thus the approximation is characterized by the seven numbers ∆1, ∆2, ∆3, and y1,y2,y3,y4.)Find the “best” such approximation that you can. [You can define the goodness of theapproximation in any way that seems reasonable to you. For example, you might want tominimize the maximum discrepancy between the true value of F (∆) and its approxima-tion.)1Problem 3. In class on April 16, I discussed the notion of a commutative semiring, andgave these five examples.K “(+, 0)” “(·, 1)” short name[0, ∞)(+, 0) (·, 1) sum-product (SP)(0, ∞] (min, ∞)(·, 1) min-product (mP)[0, ∞) (max, 0) (·, 1) max-product (MP)(−∞, +∞] (min, ∞)(+, 0) min-sum (mS)[−∞, ∞) (max, −∞)(+, 0) max-sum (MS)(a) Verify the distributive law, i.e.,(a · b)+(a · c)=a · (b + c),for each of these 5 semirings.(b) As I mentioned is class, the four semirings mP, MP, mS, and MS are all isomorphic toeach other. For example, MP becomes mS under the mapping x →−log x. Now completethe following isomorphism matrix:mP MP mS MSmP ∗MP ∗−log xmS ∗MS
View Full Document