DOC PREVIEW
CALTECH EE 127 - Homework Assignment 2

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

CALTECH EE 127 - Homework Assignment 2

Download Homework Assignment 2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Homework Assignment 2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Homework Assignment 2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?