Definitions

Question 1

Alphabet

Answer 1

An alphabet is a set F such that |F| > 1

Question 2

Symbol

Answer 2

A symbol is an element of the alphabet

Question 3

Information

Answer 3

Information is a (long) sequence of symbols

Question 4

Binary alphabet

Answer 4

F = F_2 = {0, 1}

Question 5

Binary symmetric channel

Answer 5

The binary symmetric channel denoted BSC(p) is the following: Input Probability Output 0 1-p 0 0 p 1 1 1-p 1 1 p 0 The probability of a bit error is p

Question 6

Word of length n

Answer 6

A word of length n in the alphabet F is an element of F^n = { v = (v1,…,vn) : v1,…,vn ∈ F}

Question 7

Hamming Distance

Answer 7

The hamming distance d(x,y) is the number of positions where x differs from y

Question 8

d(x,y)

Answer 8

d(x,y) = | {i ∈ (1,…,n) : xi != yi} |

Question 9

Code of length n

Answer 9

A code of length n in the alphabet F is a non empty subset of F^n. C ⊆ F^n, C != ø

Question 10

Codeword

Answer 10

A codeword is an element of a given code

Question 11

Detected error

Answer 11

If y ∈ F^n but not C then a detected error has occurred

Question 12

Undetected error

Answer 12

If y ∈ F^n and C then an undetected error has occurred

Question 13

Decoder

Answer 13

A decoder is a function DECODER: F^n —> C such that ∀y ∈ F^n DECODE(y) is a nearest neighbour of y in C

Question 14

Nearest neighbour

Answer 14

A nearest neighbour of a word y in the code C is a codeword v ∈ C such that d(y,v) = min{d(y,z) : z ∈ C}

Question 15

Decoded correctly

Answer 15

If c is transmitted and y is the received word such that y != c but DECODE(y) = c we say that the received word was decided correctly

Question 16

Let C ⊆ F^n be a code, what is n

Answer 16

n is the length of the code

Question 17

Let C ⊆ F^n be a code, what is M

Answer 17

M = |C|, the number of codewords

Question 18

Let C ⊆ F^n be a code, what is k

Answer 18

k = log_q(M) is the information dimension of C, q = |F|

Question 19

Let C ⊆ F^n be a code, what is d

Answer 19

d = d(C) = min{d(v,w) | v != w, v, w ∈ C} the minimum distance of C defined is M ≥ 2

Question 20

Let C ⊆ F^n be a code, what is R

Answer 20

R = k/n, the rate of code

Question 21

Let C ⊆ F^n be a code, what is 𝛿

Answer 21

𝛿 = d/n, relative distance

Question 22

Trivial Code

Answer 22

Let F be an alphabet, n ∈ N. The trivial code of length n in the alphabet F is C=F^n

Question 23

Repetition Code of length n

Answer 23

The repetition code of length n in the alphabet F is the code Rep(n,F) = {aa…a n times| a ∈ F^n}

Question 24

Hamming Sphere

Answer 24

if y ∈ F^n and 0 ≤ r ≤ n the set S_r(y) = {v ∈ F^n: d(v, y) ≤ r} is known as the hamming sphere with centre y and radius r

Question 25

Perfect Code

Answer 25

A code C ⊆ F^n is perfect if C attains the hamming bound. |C| = q^n/(SUM_0^n (nCi)(q-1)^i), where t= [(d-1)/2], d=d(C)

Question 26

Maximum Distance Seperable Code

Answer 26

A MDS code is a code with k = n-d+1

Question 27

Linear Code

Answer 27

A linear code is a subspace of the vector space F_q^n

Question 28

Weight

Answer 28

The weight of a vector w(v) for v ∈ F_q^n is the number of non zero symbols in the vector v.

Question 29

Zero Sum Code

Answer 29

The zero sum code in F_q^n is C = {v ∈ F_q^n : v1 + … + vn = 0 in F_q}

Question 30

Generator Matrix of a linear code

Answer 30

The generator matrix of linear code C ⊆ F_q^n is a matrix G = (r1…rk) (column vector) where {r1, … , rk} is a basis of C as a vector space

Question 31

Encode

Answer 31

The map F_q^n —> C is encode, mapping u —> uG

Question 32

Generator Matrix in standard form

Answer 32

A generator matrix is in standard form if it’s k leftmost columns form an identity matrix G = [I_k | A] where A is a k x (n-k) matrix

Question 33

Coset

Answer 33

Let C ⊆ F_q^n linear, y belongs to F_q^n, the set y+C = {y + c | c ∈ C} is the coset of y

Question 34

Coset leader

Answer 34

A coset leader of a coset y + C is a vector of minimum weight in y + C

Question 35

Weight Enumerator

Answer 35

Let be a linear code of length n. The weight enumerator W_C = A0x^n + … + Any^n, where Ai = #{c ∈ C: w(c) = i}

Question 36

Dual Code

Answer 36

If C ⊆ F_q^n is a code, C perp = {v ∈ F_q^n | v•C = {0}} is the dual code

Question 37

Check Matrix

Answer 37

A check matrix for a linear code C is a generator matrix for C perp

Question 38

Ham(r,q)

Answer 38

A hamming Ham(r,q) - code is a F_q linear code whose check matrix consists of representative vectors from all lines in F_q

Question 39

Algebra A

Answer 39

An algebra A over F_q is a ring A which is a vector space over F_q such that: ∀λ ∈ F_q, ∀a,b ∈ A, λ(ab) = (λa)b = a(λb)

Question 40

Ideal

Answer 40

An ideal of an algebra R is a subspace I ⊆ R such that RI ⊆ I

Question 41

Syndrome of the vector y

Answer 41

Let H be a check matrix for C. The map S: F_qⁿ –> F_q^n-k. S(y) = yH^T is th syndrome map and yH^T is the syndrome of the vector y

Question 42

Generator Polynomial

Answer 42

We say that g(x) ∈ F_q[x] is a generator polynomial of a cyclic code C if g(x) is monic and C = {all multiples of g(x) of degree < n}

Question 43

Generator polynomial of C ={0}

Answer 43

xⁿ-1

Question 44

Check polynomial

Answer 44

A check polynomial of a cyclic code C is h(x) such that g(x)h(x) = xⁿ - 1