Chapter 1 Coding

Question 1

Block code

Answer 1

code with all codewords fixed length

Question 2

S

Answer 2

S=S_alph e.g.|S|=26 or |S|= 2 if binary S^0 ={0}

Question 3

S^l

Answer 3

S X S X S X…S
Finite sequence of elements, length l

Question 4

Words in/ over S

Answer 4

S* = ∪{l≥0} S’
S^+ = ∪{l>0}S^l
The elements of S
∗
are also called words over (or in) the alphabet
S.

Question 5

S^0

Answer 5

S^0 ={0} The set containing the empty sequence

Question 6

Product defined on S*

Answer 6

◦ : S∗ × S∗ → S∗
(x, y) → x ◦ y = xy
where xy is the concatenation of x and y

Question 7

Block encoding map

Answer 7

for a “source alphabet” T 1-to1 function
f : T → S^n

to ** word** of length n ≥ 1 over code alphabet S
messages to be sent

Question 8

Code C Defn 1.4

Answer 8

Image set C= f(T) corresponding block code

A block (or fixed-length) code
C = {(x1, x2, …, xn),(y1, y2, …, yn), …}
of length n over the alphabet S is a subset of S^n

of M elements

Code C is q-ary
if |S| = q
C⊆S^n

Question 9

Extension f : T∗ → S∗

Answer 9

Extending map to encode each element of T in succession
words length n≥ 1

Question 10

q-ary

Answer 10

|S|=q e.g binary 3-ary
be aware of this every time, especially in fields

Question 11

x∈T^l encoded over S by…

Answer 11

aplying f to each element
f(T^l)⊆ S^{ln}
f(x)_{(i-1)n+j} = f(x_i)_j

(code length n for each “letter” in messageword length l

Question 12

repetition code
q-ary length n

Answer 12

(n,q,n)
q-ary length n

C_{q,n} = {ii…i| i∈ S}

Question 13

is code (2t+1,2,2t+1) perfect?

Answer 13

Binary repetition code
n=2t+1

every string y ∈S²ᵗ⁺¹ either has more 0’s than 1’s y ∈Bₜ(0..0)
or more 1’s than 0s y ∈Bₜ(1,..,1)

Hence S²ᵗ⁺¹ =Bₜ(0,..,0) ⊔Bₜ(1,..,1)
and C₂,₂ₜ₊₁ is perfect