Coding

?
  • Created by: Danielle
  • Created on: 22-10-15 22:00
Define (Hamming) distance
The number of places in which the codewords u and v differ.
1 of 72
Define (Hamming) weight
The number of non-zero symbols in a codeword u.
2 of 72
Define distance of a codeword
It is the smallest distance between any two distinct codewords in C.
3 of 72
State the three subspace axioms
1. The subset U of V is non-empty. 2. For all u, v in U, u+v is in U. 3. For all u in U and a in F, a*u is in U.
4 of 72
Define linear independence
X is linearly independent if the only solution to a_1x_1+...+a_nx_n=0 is a_1=...+a_n=0.
5 of 72
What is the redundancy of the [n,k,d]-linear code?
n-k
6 of 72
How many errors can C detect?
C can detect up to s errors if d(C)≥s+1
7 of 72
How many errors can C correct?
C can correct up to t errors if d(C)≥2t+1
8 of 72
Define a generator matrix for C
A generator matrix for C is a matrix whose rows form a basis for C.
9 of 72
When is C a linear code?
C is a subspace of V(n,q) then C is a linear code.
10 of 72
In a linear code [n,k,d], what are n, k and d?
n is the length of the codeword, k is the dimension and d is the distance of C.
11 of 72
When are u and v said to be orthogonal?
When the dot product of u and v is 0, i.e. u.v=0
12 of 72
What is the orthogonal subspace of U?
U^(upside down T) is the set {v in V(n,F) | v.u=0 for all u in U}, it is the set of vectors orthogonal to every vector in U.
13 of 72
Define the dual code of C
It is the orthogonal subspace C^(upside down T), when C is a linear code.
14 of 72
How do we encode a message using generator matrices?
We encode a message x by multiply on the right by G, i.e. xG.
15 of 72
How many vectors are in a subspace of dimension k?
There are q^k vectors.
16 of 72
How many vectors in the vector space V(n,q)?
There are q^n vectors.
17 of 72
Define a field
A field is a set F obeying + and x operations
18 of 72
What is the first field operation?
F is closed under + and x: For all a,b in F, a+b is in F and axb is in F.
19 of 72
What is the second field operation?
+ and x are commutative: For all a,b in F, a+b=b+a and axb=bxa.
20 of 72
What is the third field operation?
+ and x are associative: For all a,b,c in F, (a+b)+c=a+(b+c) and (axb)xc=ax(bxc).
21 of 72
What is the fourth field operation?
Distributivity: For all a,b,c in F, a+(bxc)=(axb)+(axc).
22 of 72
What is the fifth field operation?
There is an element 0 in F, with a+0=a for all a in F.
23 of 72
What is the sixth field operation?
There is an element 1 in F, with ax1=1 for all a in F.
24 of 72
What is the seventh field operation?
For every a in F, there is a b in F with a+b=0. An additive inverse.
25 of 72
What is the eighth field operation?
For every a in F except 0, there is a b in F with axb=1. A multiplicative inverse.
26 of 72
If the generator matrix for a linear [n,k,d] code C is G = [I_k | A] in standard form, what is the parity check matrix for C?
H=[-A^T | I_(n-k)]
27 of 72
Define a coset of U
Let U be the subspace of V and suppose v is in V. It is the set {v+u | u is in U} and is denoted by v+U
28 of 72
If C is an r-dimension subspace of V(n,q), how many vectors does the coset of C have?
It has exactly q^r vectors.
29 of 72
If C is an r-dimension subspace of V(n,q), how many cosets are there?
There are q^(n-r) cosets altogether.
30 of 72
What is a standard coding array?
It is an organised way of displaying the cosets of C.
31 of 72
How do you construct a standard coding array?
1. List all codewords, begin with 0. 2. List codeword of minimum weight not listed. 3. Add this to the ones above. 4. Repeat until every codeword is listed.
32 of 72
In a standard coding array, what is the closest codeword to w and how do you obtain it?
It is the codeword at the top of the column containing w, it is obtained by subtracting the coset leader to w.
33 of 72
Define the syndrome of u.
It is the vector uH^T, where H^T is the transpose of the parity check matrix.
34 of 72
What are the steps for syndrome decoding?
1. Receive u. 2. Compute the syndrome uH^T and find the coset leader v with the same syndrome. 3. Decode to u-v.
35 of 72
For an (n,M,d)-code, what are n, M and d?
n is the length of the code, M is the number of codewords in the code and d is the distance.
36 of 72
What is the sphere of radius r and centre w?
It is the set {u in the set of words of length n over the alphabet | d(w,u)≤r}. Denoted S(w,r)
37 of 72
What is the binomial coefficient?
(n m)=n!/(m!(n-m)!)
38 of 72
What is the Hamming or sphere-packing bound?
Suppose C is an (n,M,2t+1)-code over an alphabet of size q, then M{(n 0)+(n 1)(q-1)+...+(n t)(q-1)^t}≤q^n.
39 of 72
What is the Hamming bound, continued?
It is the upper bound M, obtained from earring the Hamming bound, for the number of codewords in a code with a given length n and ODD distance 2t+1.
40 of 72
What is the Singleton bound for any [n,k,d]-code?
For any [n,k,d]-code, d-1≤n-k.
41 of 72
When is an (n,M,2t+1)-code perfect?
When it achieves the Hamming bound, so if M{(n 0)+(n 1)(q-1)+...+(n t)(q-1)^t}=q^n.
42 of 72
Define a binary Hamming code
It is a code whose parity check matrix H, is a matrix whose columns are all non-zero vectors from V(r,2). Where r is a positive integer and the code is denoted Ham(r,2).
43 of 72
Is Ham(r,2) a linear code? Is it perfect?
Yes, it is a [(2^r)-1,(2^r)-r-1,3]-linear code. Yes, it is perfect.
44 of 72
What is the dimension of Ham(r,2)?
Dim(Ham(r,2))=n-r
45 of 72
Define equivalent
If u and v are non-zero vectors, they are equivalent if there a in F, a≠0, with u=av.
46 of 72
How is Ham(r,q) constructed?
By building the parity-check matrix, we pick 1 vector from each equivalence class and make these columns.
47 of 72
What type of code is Ham(r,q)
It is a (((q^r)-1)/(q-1), (((q^r)-1)/(q-1)-r, 3) code.
48 of 72
Define a Hadanard code.
It is the dual code of a binary hamming code.
49 of 72
What is the first commutative ring with identity axiom?
R is closed under + and x.
50 of 72
What is the second commutative ring with identity axiom?
+ and x are commutative
51 of 72
What is the third commutative ring with identity axiom?
+ and x are associative
52 of 72
What is the fourth commutative ring with identity axiom?
+ has an identity element 0.
53 of 72
What is the fifth commutative ring with identity axiom?
x has an identity element 1.
54 of 72
What is the sixth commutative ring with identity axiom?
For every a in R, there is an element -a in R with a+(-a)=0
55 of 72
What is the seventh commutative ring with identity axiom?
x distributes over +
56 of 72
Define an ideal
An ideal is a set I⊆R such that: 1. For every a,b in I, a+b is in I. 2. For every a in I and r in R, ar is in I. 3. I is non-empty.
57 of 72
When does an ideal equal a ring, i.e. I=R?
If and only if 1 is in the ideal, I.
58 of 72
Define deg(g) if g is in F[X], a polynomial with coefficients from F
deg(g) is the largest exponent of X with a non-zero coefficient in g.
59 of 72
Define polynomial division
If p, q are in F[X], q≠0, there are m,r in F[X] such that deg(r)
60 of 72
Define $a$
$a$ is the set {ab | b is in R}.
61 of 72
When is an ideal I⊆R a principal?
If I= for some a in I.
62 of 72
In F[X], what are all ideals?
All ideals are principal.
63 of 72
Define a coset for an ideal
It is the set of the form a+I={a+b | b is in I}. If I is clear we write [a] for a+I.
64 of 72
Define R(p,n)
R(p,n)=GF(p)[X]/$X^n -1$. It is the polynomials in GF(p)[X] with degree less than n, addition and multiplication mod X^n -1.
65 of 72
Define a cyclic code
A code C ⊆V(p,n) is cyclic if: 1. C is linear. 2. If (a_1,...,a_n) is in C, then (a_n, a_1,...,a_n-1) is in C, where (a_1,...,a_n) is a single codeword.
66 of 72
If (a_1,a_2,...,a_n) is a codeword, what is the corresponding polynomial?
The corresponding polynomial is a_1+a_2x+a_3x^2+...+a_nx^n-1.
67 of 72
Define the generator polynomial for C
If C is a cyclic code, so I(C) is an ideal, the generator polynomial for C is the monic polynomial of least degree in I(C).
68 of 72
Define the parity check polynomial
If C is a cyclic code and g(X) is its generator polynomial, the g(X) divides X^n -1. Then h(X) is the parity check polynomial such that gh=X^n -1.
69 of 72
How do you encode a message word via polynomial?
If C is a cyclic code in R(p,n) and g(X) its generator polynomial of degree k. Take a message word and make it a polynomial w(X). Encode as w(X)g(X).
70 of 72
Define the syndrome polynomial
S(X)=w(X) mod g(X). It is the remainder when dividing w(X) by g(X).
71 of 72
How do you decode the polynomial code w(X)?
1. Find syndrome S(X) by dividing W(X) by g(X). 2. Multiply S(X) by X and add the values of X to get g(X). 3. Repeat until S_a(X)=1 (mod g(X)), where a is the number of times you do XS(X). 4. Find e(X)=X^(n-a). 5. Decode to C(X)=w(X)-e(X).
72 of 72

Other cards in this set

Card 2

Front

Define (Hamming) weight

Back

The number of non-zero symbols in a codeword u.

Card 3

Front

Define distance of a codeword

Back

Preview of the front of card 3

Card 4

Front

State the three subspace axioms

Back

Preview of the front of card 4

Card 5

Front

Define linear independence

Back

Preview of the front of card 5
View more cards

Comments

No comments have yet been made

Similar Mathematics resources:

Proofs
See all Mathematics resources »See all MATH324 resources »