defs 1-3

Question 1

alphabet
symbols
information

Answer 1

Fix a set F and call it the alphabet.
Elements of F are called symbols.
By information, we mean a stream (a sequence) of symbols.

Question 2

transmit information

Answer 2

It means that symbols are sent by one party (the sender) and are received by another
party (receiver). The symbols are transmitted via some medium, which we will in general
refer to as the channel

Question 3

binary alphabet, bit

Answer 3

The binary alphabet is the set {0, 1}. A bit is the

same as binary symbol, an element of the binary alphabet.

Question 4

binary symmetric channel with bit error rate

Answer 4

denoted BSC (p)
A channel which transmits binary symbols according to the following rule:
A bit (0 or 1), transmitted via the channel, arrives unchanged with probability 1 − p, and gets flipped with probability p

Question 5

Hamming distance

Answer 5

A word of length n in the alphabet F is an
element of F^n = {v_ = (v1, v2, . . . , vn) | vi ∈ F, 1 ≤ i ≤ n}.

The Hamming distance between two words x, y ∈ F
n is the number of positions where the symbol in x differs from the symbol in y:

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

Question 6

Code

Answer 6

A code of length n in the alphabet F is a non-empty
subset of F^n

C ⊆ F^n, C =! ∅

Question 7

Codeword

Answer 7

A codeword is an element of the code

Question 8

detected error

undetected error

Answer 8

let c_ be a codeword transmitted, y_ be the word received, c_ ∈C , y_∈F^n

If y_∈! C a detected error occurred

If y_∈ C but y_ =!c_ an undetected error occurred

Question 9

Decoder

Answer 9

A decoder is a function Decode: F^n -> C such that for all y_∈F^n, DECODE(y_) is a nearest neighbour of y_ in C

Question 10

Nearest neighbour

Answer 10

A nearest neighbour of a word y_ in C is a codeword v_∈C such that:
d(y_,v_) = min{d(y_,z_): z_∈C}

Question 11

Decoded correctly

Answer 11

DECODE(y_) = c_

the symbol errors corrected by decoder

Question 12

Parameters of a code:
• n
• M
• k
• d(C)
• R
• δ(delta)

Answer 12

Let C ⊆ F^n be a code. Then:
• n is the length of the code;

• M denotes the number of codewords, i.e., M = #C;

• k = log_q M is the information dimension of C
(warning: k may not be an integer, although we will see that k is an integer for all useful types of codes);

• d(C) = min{d(v, w) : v, w ∈ C, v 6= w} is the minimum distance of C. It is defined if #C ≥ 2;
• R = k/n is the rate of C;
• δ = d/n is the relative distance of C.

We say that C is an (n, M, d)q-code or an [n, k, d]q-code

Question 13

Trivial code

Answer 13

Let C = F^n (every word is a codeword).
Then d(C) = 1. Indeed, d(C) is always positive, because it is measured between pairs of distinct codewords; and there are codewords at distance 1 in the trivial code, for
example aaa . . . a and baa . . . a where a 6= b ∈ F.
This code C is called the trivial code of length n in the alphabet F. 

It is an [n, n, 1]q-code. It detects 0 errors and corrects 0 errors

Question 14

Repetition code

Answer 14

The repetition code of length n in the alphabet F,
Rep(n, F) = {aa . . . a | a ∈ F} ⊂ F^n
has q codewords of length n. Each codeword is made up of one symbol repeated n times. The number of codewords is M = q.

This is an [n, 1, n]q-code

Question 15

Trivial bound

Answer 15

If an [n,k,d]_q exists then k≤n and d≤n

Question 16

Hamming bound

Answer 16

If (n, M, d)_q codes exist, then:

M≤ q^n
____
SUM(^t_i=o) (nCi)(q-1)^i

where t=[(d-1)/2]

Question 17

Hamming sphere

Answer 17

if y_∈F^n and 0≤ r ≤n
the set S_r(y_) ={ v_∈ F^n: d(v_,y_)=r}
is the Hamming sphere with centre y_ and radius r

Question 18

perfect code

Answer 18

A code which attains the Hamming bound is called a perfect code

Question 19

singleton bound

Answer 19

If [n, k, d]q codes exist, k ≤ n − d + 1

Question 20

maximum distance separable code, MDS code

Answer 20

A code which attains the Singleton bound is called a maximum distance separable (MDS) code.