itc Lecture3

download itc Lecture3

of 19

Transcript of itc Lecture3

  • 8/6/2019 itc Lecture3

    1/19

    1

    Lecture 3

    Introduction to Vector Space Theory

    Matrices

  • 8/6/2019 itc Lecture3

    2/19

    2

    Block codes: basic definitions An alphabet is a discrete (usually finite) set of

    symbols.example: B = { 0; 1} is the binary alphabet

    Definition: A block code of blocklength n over an

    alphabet X is a nonempty set of n-tuples ofsymbols from X.

    The n-tuples of the code are called codewords.

    Codewords are vectors whose components aresymbols in X.

  • 8/6/2019 itc Lecture3

    3/19

    3

    Block codes: basic definitions Codewords of length n are typically generated

    by encoding messages of k information bitsusing an invertible encoding function.

    Number of codewords is M = 2k , Rate R = k/n

    The rate is a dimensionless fraction; the fractionof transmitted symbols that carry information.

    A code with blocklength n and rate k/n is calledan (n; k) code

  • 8/6/2019 itc Lecture3

    4/19

    4

    Linear Block Codes

    matrixGeneratorG

    (vector)wordmessagem

    (vector)wordcode

    ,

    =

    c

    where

    Gmc

  • 8/6/2019 itc Lecture3

    5/19

    5

    Vector Space-Introduction

    Ann-dimensional vector has a form

    x = (x1, x2, x3, , xn ). The setRn ofn-dimensional vectors is a vector

    space.

    Any set Vis called a vector space if it containsobjects that behave like vectors:

    ie, they add & multiply by scalars according to

    certain rules. In particular, they must beclosedunder vector addition and scalar multiplication.

    Butaddition &scalar multiplication need not be

    defined conventionally!

  • 8/6/2019 itc Lecture3

    6/19

    6

    Contd

    Let V denote the vector space.The addition on Vis vector addition.The scalar multiplicationcombines a scalar from a Field F and a vectorfrom V. Hence V is defined over a field F.

    V must form a commutative group under addition For any element a in F and any element v in V,a.V is an element in V.

    Distributive law- a.(u+v)=a.u+a.v Associative law- (a.b).v=a.(b.v)

  • 8/6/2019 itc Lecture3

    7/19

    7

    Contd.

    Important vector spaces:

    R, R2, R3,Rn with usual + andscalar multn. Mmn; the set of allm xn matrices

    Pn; all polynomials of degree n Consider a vector space over binary fieldF2.Consider the sequence u=u0un-1 where the

    ui sare from {0,1}.We can construct such 2n

    n-tuples over F2.Let Vn denote this set. Vn is aVector space over F2

  • 8/6/2019 itc Lecture3

    8/19

    8

    Subspaces

    A set Wof vectors isasubspace of vectorspace Vif and only ifW is a subset ofV andW is itself a vector space under the same

    addition and scalar multiplication.

    For any two vectors u,v W, (u+v) W.

    For any element a in F and any u in W, a.umust be in W.

  • 8/6/2019 itc Lecture3

    9/19

    9

    Contd

    To test ifWis a Subspace

    We should, but need not, check all the propertiesof a vector space in W: most hold because Ws

    vectors are also in the bigger vector space V.

    But wemust check closure in W: linear

    combinations of vectors in Wmust also lie in W.

    This means thezero &additive inverses mustbe in Wtoo.

  • 8/6/2019 itc Lecture3

    10/19

    10

    Examples

    Let u1,.,uk be a set of k vectors in V over

    a field F. The set of all linear combinationsof u1,.,uk forms a subspace of V.

    The set of polys of degree 2 or less is a

    subspace of the set of polynomials of degree3 or less.

    Theset of integers isnot a subspace ofR,because the set of scalars includes fractions,eg 1/2.

  • 8/6/2019 itc Lecture3

    11/19

    11

    Spanning Sets &Linear Independence

    A set S = {u1,u2,.......,un} of vectors is said tospan avector space Vifevery vector in Vcan beexpressed as a linear combination of the vectors inS.

    Ex:(x, y, z ) = x i + yj + z k, so every vector inR

    3

    isa linear combination of i, j & k.

    If any vector in a set can be expressed as a

    linear combination of the others, we call theset linearly dependent. If not, the set is linearlyindependent.

  • 8/6/2019 itc Lecture3

    12/19

    12

    Basis set

    A set of linearly independent vectors is a

    basis for a Vector space V if each vector inV

    can be expressed in one and only one way as alinear combination of the set.

    In any Vector space or subspace there exists atleast one set B of linearly independent vectorswhich span the space.

    The no. of vectors in the Basis of a Vectorspace is the dimensionof the Vector space.

    One example of a basis are the vectors

    (1,0,,0), (0,1,,0),, (0,0, , 1).

  • 8/6/2019 itc Lecture3

    13/19

    13

    Orthogonality

    Let u= and

    v=

    be two n-tuples in Vn. We define the inner product(dot product) as

    u.v= where the multiplication and addition are

    carried out in mod-2.. The inner product is a scalar. If u.v=0, then u and v

    are said to be orthogonal to each other

    The inner product has the following properties

    (1) u.v=v.u

    (2) u.(v+w)=u.v+u.W

    (3)(au).v=a(u.v)

    .

    ),.....,( 110 nuuu

    ),....,( 110 nvvv

    0 0 1 1 1 1........ n nu v u v u v + + +

  • 8/6/2019 itc Lecture3

    14/19

    14

    MatricesA k x n matrix over F2 is a rectangular array with

    k rows and n columns.

    00 01 02 0, 1

    10 11 12 1, 1

    1,0 1,1 1,2 1, 1

    .....

    .....

    . . . . .

    . . . . .

    .....

    n

    n

    k k k k n

    g g g gg g g g

    G

    g g g g

    =

    where each ijg 0 0i k and j n with

    is an element from the binary field F2.

  • 8/6/2019 itc Lecture3

    15/19

    15

    G is also represented by its k rows

    as0 0 1, ,..... kg g g

    0

    1

    1

    .

    .

    k

    g

    g

    G

    g

    =

    Each row of G is an n-tuple and each column is a k-tuple over F2.

  • 8/6/2019 itc Lecture3

    16/19

    16

    If k (with ) rows of G are linearlyindependent, then the 2k linear combinationsof of these rows form a k dimensionalsubspace of the vector spaceVn of all the n-

    tuples over F2. This subspace is called therow space of G

    Elementary row operations will not changethe row space of G

    k n

  • 8/6/2019 itc Lecture3

    17/19

    17

    Let S be the row space of a k x n matrix G overF2whose rows are linearly independent. Let Sd be

    the null space ofS. Then the dimension ofSd is

    n-k. Consider (n-k) linearly independentvectorsin Sd. These vectors span Sd. We can form an

    (n-k) x n matrix H as00 01 02 0, 10

    10 11 12 1, 11

    1,0 1,1 1,2 1, 11

    .....

    .....

    . . . . ..

    . . . . ..

    .....

    n

    n

    n k n k n k n k nn k

    h h h hh

    h h h hh

    H

    h h h hg

    = =

    The row space of H is Sd

  • 8/6/2019 itc Lecture3

    18/19

    18

    Since each row gi is a vector in S and each

    row hj of H is a vector in Sd, the innerproduct of gi and hj must be zero. As therow space S of G is the null space of the

    row space Sd of H, S is called the null space

    or dual spaceof H.

  • 8/6/2019 itc Lecture3

    19/19

    19

    Theorem

    For any k x n matrix G over F2, with k linearly

    independent rows, there exists an (n-k) x nmatrix over the same field with (n-k) linearlyindependent rows such that for any row gi in

    G and any hj in H, gi.hj = 0. The row space ofG is the null space of H and vice versa.