EE/Ma 127c Error-Correcting Codesdraft of May 16, 2001R. J. McEliece162 MooreHomework Assignment 4—Due (in class) 9am May 18 , 2001Reading:Handout “The Serial Concatenation of Interleaved Codes ..., ” Secs. I, IIB, and V.Problems to Hand In:Problem 1. In class on Friday May 11, I discussed the iterative decoding of “serial”’turbo codes, with a structure like the one shown in Figure 14b of the handout “The SerialConcatenation of Interleaved Codes.” I emphasized that the componet “APP” decoder forthe outer code (the block labelled “MAP outer code” in Figure 14b) must be capable ofproducing APP’s for the encoded bits as well as the information bits. I also gave as oneexample the “Repeat-Accumulate’ code, in which the outer code is a simple “repeat eachbit q times” device.(a) Describe an efficient APP decoding rule for the information and encoded bits for aq-fold repetition code.(b) Next consider the (6, 2) code obtained by repeating each of the two information bitsthree times: in other words, the codeword associated with the information word (u1,u2)is(u1,u1,u1,u2,u2,u2). Suppose the a priori log-likelihoods for the information bits (u1,u2)areLLR(i)1=0.1, LLR(i)2= −0.1,and the log-likelihoods observed from the channel of the 6 coded bits areLLR(o)1=0.2, LLR(o)2=0.1, LLR(o)3=0.0,LLR(o)4=0.0, LLR(o)5= −0.1, LLR(o)6= −0.2.Compute the APP’s (In log-likelihood form) for the two information bits and the six codebits.Problem 2. In class Monday, May 14, I discussed a “linear congruential” method ofgenerating random permutations of length n = p − 1, where p is an odd prime, i.e., thoseof the formπ(i)=bai(modp),for i =1, 2,...,n. I stated that experiments with p = 1103 indicated that the choice b =1and a = 127 was better than e.g. a = 3, 5, 7. Ling Li has suggested that this may be dueto correlations between π(i) and π(i + 1).Test this suggestion by making a scatter plot of π(i) vs. π(i + 1) for p = 1103 anda =3, 5, 7, 9, and 127, and comment. What about π(i) vs. π(i + 2), etc. ?Problem 3. In class on Wednesday, May 16 I briefly discussed the problem of countingthe number of distinct RA codes with parameters q and k, where q is the repetition number1and k is the number of information bits. Taking into account the freedom of choosing theinterleaver, how many distinct (q, k) RA codes are there? [Hint: the answer is not
View Full Document
Unlocking...