E2 205 Sample Midterm Exam

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Transcript
  MIDTERMEXAM E2 205Oct 8, 2015PVK ã  90-min exam, 13 questions, maximum score = 46 points, answer all questions ã  closed-book exam (no books, no class notes, no handwritten notes, no calculators) ã  Please make clear your reasoning and show clearly, all your working! ã  Please identify the question you are answering using a large numeral and make sure that the numeral is not hiddenunder the staple! ã  Good luck!1. The pair,  G  =   Z  24 , +  is a group under  +  where  +  denotes additional modulo 4. Show that the set  H   =  { ( a , b ) | a , b ∈{ 0 , 2 }} , is a subgroup of   G . Identify clearly, all the cosets of   H   in  G .3 points2. Given that  x ,  y ∈ F n 2 , and satisfy d   H  (  x ,  y ) =  6 , what is the size of  |  B   x , 3 ) ∩  B (  y , 3 )  | ?Explain your reasoning. 3 points3. Add a fourth binary column to the binary (i.e., entries lie in  F 2 ) matrix  A  =  1 1 00 1 11 0 0  , so that in the resulting  ( 3 × 4 )  binary matrix  B , any 3 columns of   B  are linearly independent over  F 2 . 2 points4. How many distinct 3-dimensional subspaces (with F 2  as the field of scalars) are contained in the 6 dimensional vectorspace  F 62  ? Show all your working and explain your reasoning.4 points5. Is it possible to construct a very long binary block code having the following parameters:Rate  R  : =  log 2 ( | C  | ) n =  0 . 15 δ   : =  d  min n =  0 . 8?Explain your reasoning. 2 points  6. Given a block code C   of length  n  and size | C  |  =  M  , prove that there exists some  n -tuple  x ∈ F n 2  such that |  B (  x , e ) ∩ C   | ≥  M  |  B ( 0 , e ) | 2 n  , for any integer  e , 1 ≤ e ≤ ( n − 1 ) . Here as in class,  B (  x , e ) =  {  z ∈ F n 2  | d   H  (  z ,  x ) ≤ e } . Make clear your reasoning.4 points7. The standard array table of a linear block code  C   is given in Fig. 1. We use  c , e ,  y  to denote the codeword, error andreceived vectors over a BSC so that  y  =  c + e  .   000000 100110 010011 001111 110101 101001 011100 111010 (000) T  000001 100111 010010 001110 110100 101000 011101 111011 (001) T  000010 100100 010001 001101 110111 101011 011110 111000 (010) T  000100 100010 010111 001011 110001 101101 011000 111110 (100)  T  001000 101110 011011 000111 111101 100001 010100 110010 (111)  T  010000 110110 000011 011111 100101 111001 001100 101010 (011)  T  100000 000110 110011 101111 010101 001001 111100 011010 (110)  T  000101 100011 010110 001010 110000 101100 011001 111111 (101)  T  CodewordsElements of a coset Coset leader Syndrome Figure 1: Standard array.(a) Determine the probability that the codeword is correctly decoded under ML decoding, if the channel is a BSChaving crossover probability  ε  . Show all your working and explain briefly, your reasoning. 2 points(b) Assume that the first 3 code symbols represent the message symbols. Is it then true that the first and secondmessage bits are equally likely to be decoded incorrectly ? Explain. 3 points8. Consider the linear, binary, block code C   possessing generator matrix G  =  1 1 0 1 0 00 1 1 1 0 00 0 0 1 1 1  . (a) Write down the parameters  [ n  , k   , d   min ]  of the dual code C  ⊥ . 2 points(b) Identify a suitable generator matrix  G  and a suitable parity-check matrix  H   for the dual code C  ⊥ . Show all yourworking. 4 points  9. Let C   be an  [ n , k  , d  ]  linear code having  ( k  × n )  generator matrix  G . What is the smallest value of   l  such that any  ( k  × l ) sub-matrix of   G  must have rank   k   ? Explain fully. 4 points10. Write down an expression for the syndrome  s  of an  [ n , k  , d  min ]  binary, linear code  C   in terms of its generator and/orparity check matrices denoted by  G ,  H   respectively. You may assume that transmission is over a BSC and that thereceived vector is  y . What is the size of the set of all possible syndromes obtained in this fashion upon repeatedtransmission over the BSC ? Explain your reasoning. 3 points11. Consider the ring  R  of power series given by R  =  F 2 [[  x ]] =   ∞ ∑ i = 0 a i  x i | a i  ∈ F 2  . Which elements of   R  have inverses ? Give as complete an answer as you can. Explain your reasoning.4 points12. The outputs  ( v ( 1 ) t   , v ( 2 ) t   )  of a rate  12  convolutional encoder with single input and two outputs are mapped by a modulatorto real values according to (  x ( 1 ) t   ,  x ( 2 ) t   ) = (( − 1 ) v ( 1 ) t  ,  ( − 1 ) v ( 2 ) t  ) . After transmission over an additive white Gaussian noise channel, the channel output is given by (  y ( 1 ) t   ,  y ( 2 ) t   ) = (  x ( 1 ) t   ,  x ( 2 ) t   ) + ( n ( 1 ) t   , n ( 2 ) t   ) where the random variables  n (  j ) t   ,  j  = 1 , 2 are Gaussian with zero mean and unit variance. If the pair of received symbolsfollowing the  t  th transmission are given by  ( − 2 , + 3 ) , identify the branch metrics for all eight branches of the trellis,corresponding to time  t   using the trellis section for time  t   shown in Fig. 2. Show all your working. 00 10 01 11 00 10 01 11 Figure 2: Trellis section.4 points13. In a certain convolutional encoder there is a single input stream { u t  } ∞ t  = 0  and three output streams { v (  j ) t   } ∞ t  = 0 ,  j  =  1 , 2 , 3given (for  t   ≥ 0) by: v ( 1 ) t   =  u t   + u t  − 1  + u t  − 3 , v ( 2 ) t   =  u t   + u t  − 2  + u t  − 4 , v ( 3 ) t   =  u t  − 1  + u t  − 2  + u t  − 3 . Write down the polynomial generator matrix  G (  D )  for the code.2 points
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x