DOC PREVIEW
CALTECH EE 127 - Error-Correcting Codes

This preview shows page 1 out of 4 pages.

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

Unformatted text preview:

EE/Ma 127b Error-Correcting CodesMarch 26, 2007R. J. McEliece162 MooreDetails of Viterbi Decoder ProjectDue date: Week of April 23, 2007You (and/or your team; maximum of three students per team) are expected to producea computer program to implement the Viterbi decoding algorithm for the Voyager code,i.e., the (2, 1, 6, 10) binary convolutional code with generator matrix(G1(D), G2(D)) = (1 + D2+ D3+ D5+ D6, 1 + D + D2+ D3+ D6).• The Deliverable, Part 1. I want you to run simulations with your Viterbi decoder topro duce graphs showing the (approximate) relationship between Eb/N0and the decodedbit error probability for the given convolutional code, for Eb/N0ranging from 1 dB to 6dB,in increments of 0.5 dB. Graph 1 will show the results for “hard decision” decoding andGraph 2 will show the results for “soft decision” deco ding. For comparison, also plot theuncoded bit error probability, given by the formulaPuncoded= Q(p2Eb/N0),whereQ(x) =1√2πZ1xe−t2/2dt.• The Deliverable, Part II. This part is to entertain the Professor. Provided you turnin an answer, it will not affect your grade. Select a random 4-digit seed equal to the lastfour digits of the SSN of the oldest member of your team. Using this seed, decode 100000bits with a noise variance of exactyσ = ln 2,with both hard and soft decision decoding. Report the number of bit errors made by yourdecoder.• Important Fact: For a binary code of rate R on the AWGN channel, the relationshipbetween Eb/N0, the bit signal-to-noise ratio and σ2, the Gaussian noise variance, is givenbyσ2=µ2REbN0∂−1,so for example for a R = 1/2 code like the Voyager code, the relationship is simplyσ2=µEbN0∂−1.Finally remember that Eb/N0is normally quoted in “dBs,” where a dimensionless quantityx equals 10 log10x dB’s. Thus for example, a value of Eb/N0of 3.5 dB for the Voyagercode corresponds to a value of σ2= 0.4467.1Additional details on Viterbi Decoder Project.1. Use the recursionpn+6= pn+1⊕ pnfor n ≥ 0with the initial conditionsp0= 1, p1= p2= p3= p4= p5= 0,to generate the N information bits. Ensure that the generated sequence is 100000100001 . . .and is periodic with period 63.2. Encode the information sequence using the generator polynomials G1(D) and G2(D) givenabove.3. The encoder outputs 0’s and 1’s. However, the input to the AWGN is ±1. Therefore, map0’s to +1’s and 1’s to -1’s.4. To simulate the AWGN with soft decision decoding, add the mean zero, variance σ2normal(Gaussian) random variables generated by the following segment of pseudo-code, to the±10s generated at the previous step. This program outputs two random variables, n1andn2. Use n1(resp. n2) for the encoder output corresponding to the generator polynomialG1(D) (resp. G2(D)). SEED and σ (i.e., Eb/N0) will be specified at the time of testing yourprogram. urand() is a function which generates a random variable uniformly distributedin the interval [0, 1].main(){. . .global iurv;. . .iurv = SEED;. . .. . .}normal(n1, n2, σ) /* See “Donald E.Knuth, The Art of Computer Programming, Vol.2,p.104 ” */{do {x1= urand();x2= urand();2x1= 2x1− 1;x2= 2x2− 1;/* x1and x2are now uniformly distributed in [-1,+1] */s = x21+ x22;} while (s ≥ 1.0)n1= σx1p−2 ln s/s;n2= σx2p−2 ln s/s;}urand(){iurv = (14157iurv + 6925)(mod32768);return iurv/32767;}5. For “hard decision” decoding:(a) Take the sign of the output of the AWGN (Define Sign(0) = +1.)(b) Map +1’s to 0’s and -1’s to 1’s.6. Truncate your survivors to length 32 and output the oldest bit on the survivor with theleast metric (“Best State Decoding”). To decode N bits, generate N + 32 bits in (1).Your program should output the fraction of decode bits in error (Bit Error Rate) in bothcases.The following table lists some typical values.N σ Eb/N0SEED BER (soft) BER (hard)1000 0.8 1.94dB 101 0.010 0.1581000 0.9 0.92dB 111 0.107 0.2257. What to do in case of tied metrics? There are two cases to consider. First, in the “add-compare-select” step the two metrics could be equal. In this case you can safely selecteither choice; it won’t affect the decoder performance. Second, in choosing the survivorwith the best metric, if there are two or more best states, take the majority vote of theoldest bits on the winning states. If this is still tied, choose arbitrarily.8. Notes on simulation accuracy. As Eb/N0increases, you will find that decoder bit errorsbecome quite rare. I suggest, but do not insist on, the following approach. At a givenvalue of Eb/N0, run your decoder until you have seen at least K errors. If this required Ndeco ded bits, your estimate of the bit error probability is K/N. The larger K, is the more3accurate your plot will be, but K will be limited by you decoder’s speed. For example,with Eb/N0= 4.0dB, and sft decision decoding, the BER is arond 10−5, which means youwill need to decode around 10000K bits before K bit errors have


View Full Document

CALTECH EE 127 - Error-Correcting Codes

Download Error-Correcting Codes
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 Error-Correcting Codes 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 Error-Correcting Codes 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?