Communication - Chapter 5

Question 1

How to computer A(n,d)=M

Answer 1

1. A(n,d)≤M: show every (n,d)-code has size ≤M

2. A(n,d)≥M: there exists an (n,d)-code of size M

Question 2

How to view {0,1}ⁿ as a vector space

Answer 2

vector space of dimension n over the binary field 𝔽₂ denoted 𝔽₂ⁿ. Where addition of any two vectors is pointwise modulo 2.

Question 3

Addition of binary strings.

Answer 3

Pointwise modulo 2. 
i.e., 0+0 = 0
1 + 1 = 0
1 + 0 = 1
0 + 1 = 0
NO CARRYING

Question 4

sum code informal

Answer 4

just add x to each element of C via vector addition

Question 5

How to use proposition 5.5 to show A(n,d)≤m.

An optimal (n,d)-code contains the zero vector.

Answer 5

1. For a contradiction suppose there exists an optimal (n,d)-code of size |C|≥m
2. By proposition 5.5 we may assume 00…0ϵC
3. since an (n,d)-code we have minimum hamming distance d. Use this to construct the remaining codewords.
4. If any of these codewords have hamming distance

Question 6

Can you use punctured codes to show A(n,2)=2ⁿ⁻¹

Answer 6

yes

Question 7

If a(x,y) denoted the number of positions where x and y are both 1 then how can we use weights to calculate hamming distance?

Answer 7

dₕ(x,y) = w(x) + w(y) - 2a(x,y)

Question 8

punctured code informal

Answer 8

a punctured code is made from truncating the last ℓ bits from each codeword

Question 9

parity check informal

Answer 9

the parity check code is the code where each codeword has a 0 added to the end if the weight of the codeword is even and a one added if the weight of the codeword is odd.

Question 10

parity check add a 0 if…

Answer 10

w(c) is even

Question 11

parity check add a 1 if…

Answer 11

w(c) is odd

Question 12

condition for A(n,d)=A(n+1,d+1)

Answer 12

d must be odd

Question 13

How to use punctured codes to show A(n,2)≤2ⁿ⁻ˡ

Answer 13

1. let C be an arbitrary (n,d)-code consider c*(l)
2. As dₕ(C)≥d => dₕ(C(l))≥d-l and |C|=|C(l)|
3. Note C*(l) has length n-l so it contains at most 2ⁿ⁻ˡ codewords.
4. Thus |C|=|C*(l)|≤2ⁿ⁻ˡ

Question 14

If d is odd…

Answer 14

A(n,d)=A(n+1,d+1)

Question 15

Let C be an optimal (n,d)-code then

Answer 15

|C|=A(n,d)

Question 16

Plotkins and sphere packing bound give an…

Answer 16

Upper Bound on A(n,d)

i.e. A(n,d)≤(expression)

Question 17

Sphere covering bound gives an

Answer 17

Lower Bound on A(n,d)

i.e. A(n,d)≥(expression)

Question 18

Method to show A(n,d) is less than or equal to 2 to the power of something

Answer 18

Use punctured codes

Question 19

n choose 0

Answer 19

1

Question 20

n choose 1

Answer 20

n

Question 21

extra condition for plotkins bound

Answer 21

2d>n

Question 22

A(n,d)≤A(n+1,d+1)

Answer 22

Use parity check code (increase length)

Question 23

A(n,d)≥A(n+1,d+1)

Answer 23

Use punctured code (decrease the length).

Question 24

When showing A(n,d) ≥

Answer 24

construct an (n,d)-code of size A(n,d)

Question 25

2A(n-1,d)≥

Answer 25

2A(n-1,d)≥A(n,d)