Laboratory Assignment 1 (part 1 , part 2 and part 3) Solution

Problem 1: Context of the Course
(a) Using Internet and/or library resources, describe and explain in your own words and sketches the signal processing involved in radar technology and the signal processing hardware used to implement it.
(b) In lecture, we discussed FPGA’s vs. ASIC’s as two hardware platforms to implement signal processing techniques in practice. Using the Internet resources and/or the library, list at least 4 advantages each technology has when compared to the other one.
Problem 2: Error Control Codes
As covered in class, large distances between codewords are important for code error-correcting ability.
(a) Show that for any binary linear block code, dmin = min wt(c), searching over all non-zero codewords.
(b) Does this result extend to non-binary linear codes? Answer and fully justify your answer.
(c) State and prove the Hamming bound on dmin for binary codes. Use it to show that a (24, 12, 9) binary code does not exist.
(d) Explain why an (n,k,dmin) binary code can ALWAYS correct up to (dmin -1) erasures.
(e) For the (6,3, 3) binary code discussed in class, list all its codewords and verify that its dmin = 3 with and without using the result from part (a).
(f) How many codeword pairs are at a distance dmin for this code? Finally, sketch so called code spectrum of this code.
Problem 3: Implementing Decoding Algorithms
(a) Using Matlab, implement an encoder for the (6,3,3) code from class and a function for binary erasure channel that takes as an input a binary 0/1 vector and probability of erasure value. The output of the function is the binary vector corrupted with i.i.d. erasures represented by 1/2 values, which occurred with the given probability.
(b) Using Matlab, implement the exhaustive decoding algorithm from class for the (6,3,3) code on the erasure channel. (Hint: You can use proper distance function to “vectorize” your algorithm for speed.)
(c) Implement an erasure decoding algorithm for this (6,3,3) code using Gaussian elimination to solve 5v vv- 101000n out the erasure.
(d) Test performance of these algorithms using your encoder and erasure channel scripts from (a).
(e) Complexity consideration: What would the complexity of these decoders is your code is a (10000,
5000) code? Estimate how many seconds/days it would it take to decode erasures in such a
codeword on a regular computer. (Use approximations as necessary.)



Laboratory Assignment 1 (part 1 and part 2)


Problem 1: Context of the Course
(a) Using Internet and/or library resources, describe and explain in your own words and sketches the signal processing involved in radar technology and the signal processing hardware used to implement it.
(b) In lecture, we discussed FPGA’s vs. ASIC’s as two hardware platforms to implement signal processing techniques in practice. Using the Internet resources and/or the library, list at least 4 advantages each technology has when compared to the other one.
Problem 2: Error Control Codes
As covered in class, large distances between codewords are important for code error-correcting ability.
(a) Show that for any binary linear block code, dmin = min wt(c), searching over all non-zero codewords.
(b) Does this result extend to non-binary linear codes? Answer and fully justify your answer.
(c) State and prove the Hamming bound on dmin for binary codes. Use it to show that a (24, 12, 9) binary code does not exist.
(d) Explain why an (n,k,dmin) binary code can ALWAYS correct up to (dmin -1) erasures.
Alternatively, show that this code can ALWAYS correct (dmin -1)/2 binary errors in a codeword.
(e) For the (6,3, 3) binary code discussed in class, list all its codewords and verify that its dmin = 3 with and without using the result from part (a).
(f) How many codeword pairs are at a distance dmin for this code? Finally, sketch so called code spectrum of this code.
(g) Redo parts (f) and (e) for the Hamming (8,4,4) code introduced in class.
(h) Show that dmin ? n-k+1 for every (n,k,,dmin) systematic binary linear block code.
EXTRA CREDIT:
Is the inequality in part (h) true for all non-systematic binary linear codes – i.e., codes for which the codewords do not contain the message bits. If not, give a counter-example, if yes, fully justify your answer.
Problem 3: Implementing Decoding Algorithms
(a) Using Matlab, implement an encoder for the (6,3,3) code from class and a function for binary erasure channel that takes as an input a binary 0/1 vector and probability of erasure value. The output of the function is the binary vector corrupted with i.i.d. erasures represented by 1/2 values, which occurred with the given probability.
(b) Using Matlab, implement the exhaustive decoding algorithm from class for the (6,3,3) code on the erasure channel. (Hint: You can use proper distance function to “vectorize” your algorithm for speed.) If more than one codeword is the best match to the received data vector with erasures, the decoder outputs a list of all such codewords,
(c) Implement an erasure decoding algorithm for this (6,3,3) code using Gaussian elimination to solve out the erasure. (Hint: Modify the (n-k) =(6-3)=3 parity check equations to start.)
(d) Test performance of these algorithms using your encoder and erasure channel scripts from (a).
(e) Complexity consideration: What would the complexity of these decoders is your code is a (10000,
5000) code? Estimate how many seconds/days it would it take to decode erasures in such a codeword on a regular computer. (Use approximations as necessary.)
(f) Construct parity check matrices for the above (6,3,3) binary code and for the Hamming (8,4,4) code discussed in class.
(g) Use (f) to determine the general format of the parity check matrix H for any systematic binary linear code with generator matrix G=(I | P).
Problem 4: Convolutional Codes
(a) Draw the finite state machine representation and one full stage of the trellis diagram for the rate ½ convolutional code used in the 2G, 3G and 4G cellphones.
(b) Sketch one stage of the trellis diagram for the (6,3,3) binary linear block code from class.




Laboratory Assignment 1 (part 1, part 2 and part 3)

Problem 1: Context of the Course
(a) Using Internet and/or library resources, describe and explain in your own words and sketches the signal processing involved in radar technology and the signal processing hardware used to implement it.
(b) In lecture, we discussed FPGA’s vs. ASIC’s as two hardware platforms to implement signal processing techniques in practice. Using the Internet resources and/or the library, list at least 4 advantages each technology has when compared to the other one.
(c) Explain in your own words why FPGA signal processing hardware cannot be used in space missions
(e.g. Earth orbiting satellites, moon or Mars missions, etc.). Cite online references as necessary.
Problem 2: Error Control Codes
As covered in class, large distances between codewords are important for code error-correcting ability.
(a) Show that for any binary linear block code, dmin = min wt(c), searching over all non-zero codewords.
(b) Does this result extend to non-binary linear codes? Answer and fully justify your answer.
(c) State and prove the Hamming bound on dmin for binary codes. Use it to show that a (24, 12, 9) binary code does not exist.
(d) Explain why an (n,k,dmin) binary code can ALWAYS correct up to (dmin -1) erasures.
Alternatively, show that this code can ALWAYS correct (dmin -1)/2 binary errors in a codeword.
(e) For the (6,3, 3) binary code discussed in class, list all its codewords and verify that its dmin = 3 with and without using the result from part (a).
(f) How many codeword pairs are at a distance dmin for this code? Finally, sketch so called code spectrum of this code.
(g) Redo parts (f) and (e) for the Hamming (8,4,4) code introduced in class.
(h) Show that dmin ? n-k+1 for every (n,k,,dmin) systematic binary linear block code.
EXTRA CREDIT:
Is the inequality in part (h) true for all non-systematic binary linear codes – i.e., codes for which the codewords do not contain the message bits. If not, give a counter-example, if yes, fully justify your answer.
Problem 3: Implementing Decoding Algorithms
(a) Using Matlab, implement an encoder for the (6,3,3) code from class and a function for binary erasure channel that takes as an input a binary 0/1 vector and probability of erasure value. The output of the function is the binary vector corrupted with i.i.d. erasures represented by 1/2 values, which occurred with the given probability.
(b) Using Matlab, implement the exhaustive decoding algorithm from class for the (6,3,3) code on the erasure channel. (Hint: You can use proper distance function to “vectorize” your algorithm for speed.) If more than one codeword is the best match to the received data vector with erasures, the decoder outputs a list of all such codewords,
(c) Implement an erasure decoding algorithm for this (6,3,3) code using Gaussian elimination to solve out the erasure. (Hint: Modify the (n-k) =(6-3)=3 parity check equations to start.)
(d) Test performance of these algorithms using your encoder and erasure channel scripts from (a).
(e) Complexity consideration: What would the complexity of these decoders is your code is a (10000,
5000) code? Estimate how many seconds/days it would it take to decode erasures in such a codeword on a regular computer. (Use approximations as necessary.)
(f) Construct parity check matrices for the above (6,3,3) binary code and for the Hamming (8,4,4) code.
(g) Use (f) to determine the general format of the parity check matrix H for any systematic binary linear
code with generator matrix G=(I | P).
(h) In Matlab, implement the syndrome decoder for the (6,3,3) code linear block code from class. Then simulate its bit error rate performance using binary symmetric channel errors with probability of channel error being 0.2, 0.15, 0.1, 0.05 and 0.01 respectively.
Problem 4: Convolutional Codes and Codes with Trellis Structure
(a) Draw the finite state machine representation and one full stage of the trellis diagram for the rate ½ convolutional code used in the 2G, 3G and 4G cellphones.
(b) Sketch the trellis diagram for the (6,3,3) binary linear block code from class.
(c) Sketch one full stage of the trellis diagram for an intersymbol echo interference channel
described by equation ** yn = xn + 2xn-1 + xn-2 **where channel inputs take value -1 or +1.
(d) Consider a (5,3) ternary linear block code over alphabet {-1,0,+1} and modulo 3 addition
described by c = (m1, m2, m3, p1=m1+m2+m3, p2=m1-m2+m3).
Sketch the trellis diagram for this code that has at most 3 states at each trellis stage.
In addition, determine its dmin and write down its generator and parity check matrices G and H.
(e) Explain why convolutional codes are called “convolutional” and write down the input/output
convolution equations for the code from parts (a) and (c) and appropriate impulse responses.
Problem 5: Check out the FPGA based signal processing board from the Trottier Bldg.
technicians, connect it to a lab PC and redo the initial TA demo shown in the lab session.