Assignment #5: Applications: Communication (back to full lecture notes)

In this assignment you will use concepts from linear algebra to solve several problems in the application domain of communication.

  1. Alice wants to send Bob the matrix T below. However, she can only afford to send 30 scalars or fewer. Will she be able to send a message from which Bob can recover all the information in the matrix?

    T :=
     
    0 3 1 -4 -1 -8 0 -6 -2 8 2 16
    1 0 -2 0 -2 -9 -2 0 4 0 4 18
    3 -9 -9 12 -3 -3 -6 18 18 -24 6 6
    -2 -6 2 8 6 34 4 12 -4 -16 -12 -68
    3 -3 -7 4 -5 -19 -6 6 14 -8 10 38
     



    numColumns
    :=
    undefined # replace with a formula in terms of T
    numRows
    :=
    undefined # replace with a formula in terms of T
    basisSize
    :=
    undefined # replace with a formula in terms of T
    numScalarsToSend
    :=
    undefined # replace with a formula that produces an integer
    numScalarsToSend
    30

  2. You know that Alice is using a matrix M R2×2 to send encoded vectors in R2 to Bob. You also know that she will only send vectors from the following set:

    {
     
    3
    0
     
    ,
     
    1
    2
     
    ,
     
    4
    4
     
    ,
     
    0
    1
     
    ,
     
    0
    -2
     
    ,
     
    7
    2
     
    ,
     
    2
    1
     
    ,
     
    1
    -1
     
    ,
     
    -2
    2
     
    }

    You observe two encoded messages as they are being transmitted:

    {
     
    4
    -6
     
    ,
     
    2
    11
     
    }

    Determine which two unencoded vectors Alice sent, and then use them along with the encoded vectors and some matrix operations to provide a definition of the encoding matrix. You should be able to use \augment to accomplish this using a definition that fits on a single line.

    v,w R2, ∀ a,b,c,d R,
    v
    =
    \undefined   and
    w
    =
    \undefined   and
     
    ab
    cd
     
    =
    \undefined

    implies
    # ...
     
    ab
    cd
     
    v
    =
     
    4
    -6
     
      and
     
    ab
    cd
     
    w
    =
     
    2
    11
     


  3. Alice wants to send Bob a vector v R2. She has an unreliable device that can transmit a vector in R2 to Bob, but it always adds the following error to v during transmission (where s is unknown ahead of time, and different each time):

    vv + s
     
    -1
    1
     

    Alice and Bob will agree on some u, M, and M' before parting. When sending a vector with x and y components, Alice will use the device to transmit two vectors: (xu) and (yu). Bob will receive w and w' as defined below, and will decode v by computing M w + M w'. Find u,M, and M' that make it possible to retrieve v, and complete the argument below. Hint: review the propositions available in the verification system that deal with matrices and vectors, as they may allow some algebraic manipulations to be more concise.

    x,y,s,s' R, ∀ u,v,w,w' R2, ∀ M,M' R2×2,
    u
    =
    \undefined   and
    M
    =
    \undefined   and
    M'
    =
    \undefined   and
    w
    =
    x u + s
     
    -1
    1
     
      and
    w'
    =
    y u + s'
     
    -1
    1
     
      and
    v
    =
     
    x
    y
     


    implies
         # ...
         v = M w + M' w'

  4. In many of the communication examples being considered, it is useful to be able to construct a matrix whose corresponding linear transformation has a specific non-trivial image, and a specific non-trivial kernel (i.e., the span of a particular vector or set of vectors). Suppose we know that a vector [x;y] in R2 is a linear combination of two linearly independent vectors:

     
    x
    y
     
    =
    s
     
    a
    c
     
    + r
     
    b
    d
     

    We do not know s and r, but we do know all of the following:

     
    x
    y
     
    ,
     
    a
    c
     
    ,
     
    b
    d
     

    One way to remove the [b;d] term from [x;y] is to first set up a matrix equation and solve for s and r:

     
    ab
    cd
     
     
    s
    r
     
    =
     
    x
    y
     

    However, suppose we instead want to find a linear transformation f such that for any [x;y] as defined above, we have:

    f (
     
    x
    y
     
    )
    =
    s
     
    a
    c
     

    In fact, given the information we have, we can construct exactly such a linear transformation:

    f ( v )
    =
    (
     
    ab
    cd
     
     
    10
    00
     
     
    ab
    cd
     
     -1) ⋅ v

    Complete the argument below showing that this linear transformation indeed has this property.

    a,b,c,d,x,y,s,r R,
    (
     
    a
    c
     
    ) and (
     
    b
    d
     
    ) are linearly independent   and

    s
     
    a
    c
     
    + r
     
    b
    d
     
    =
     
    x
    y
     


    implies
    # ...
    s
     
    a
    c
     
    = (
     
    ab
    cd
     
     
    10
    00
     
     
    ab
    cd
     
    ^(-1)) ⋅
     
    x
    y
     


  5. Let polynomials in F = {f | f(t) = a t2 + b t + c } represent a space of possible radio signals. To send a vector v R3 to Bob, Alice sets her device to generate the signal corresponding to the polynomial in F whose coefficients are represented by v. Bob then has his receiver sample the radio signals in his environment at three time points to retrieve the message.
    1. Suppose Bob samples the signals at t {1,2,3} and obtains the vectors P defined below. What vector in R3 did Alice send? Use techniques you have learned in this course to retrieve the vector.

      P := {
       
      1
      1
       
      ,
       
      2
      -3
       
      ,
       
      3
      -11
       
      }

           # ...
      v := \undefined

    2. Suppose the environment contains noise from other communication devices; the possible signals in this noise are always from the span of the following polynomials:

      g(t)
      =
      2 t - 2
      h(t)
      =
      t2 + 3 t
      Alice and Bob agree that Alice will only try to communicate to Bob one scalar r R at a time. They agree on a vector u ahead of time. Any time Alice wants to send some r R to Bob, she will have her device generate the signal corresponding to the polynomial represented by ru. If the vectors P below represent the samples collected by Bob, what scalar was Alice sending to Bob?

      P := {
       
      1
      3
       
      ,
       
      2
      9
       
      ,
       
      3
      13
       
      }

           # ...
      s := \undefined

    3. Suppose there is no noise in the environment. Alice, Bob, and Carol want to send individual scalars to one another at the same time: all three would be sending a signal simultaneously, and all three would be listening at the same time:
      • Alice's device would generate a signal corresponding to a scalar multiple of f(x) = 2 x + 1;
      • Bob's device would generate a signal corresponding to a scalar multiple of g(x) = -x2 + 1;
      • Carol's device would generate a signal corresponding to a scalar multiple of h(x) = x2 - 3 x.

      Suppose you sample the radio signals at a given moment and obtain the vectors P below. Determine which scalars Alice, Bob, and Carol are each transmitting. Your answer can be in the form of a vector.

      P := {
       
      0
      5
       
      ,
       
      1
      7
       
      ,
       
      2
      7
       
      }

           # ...
      v := \undefined