14 Hamming over non binary fields

Question 1

u is projectively equivalent
to v, written u ∼ v,

Answer 1

Let u, v ∈ F_q ^r \ {0}.

if there exists λ ∈ Fq \ {0} such that u = λv.
Note that this is an equivalence relation.

We call the set of projective equivalence classes the projective
space of F_q ^n, denoted P(F_q ^r)

( has dimension n − 1 and its elements are called points)

Question 2

Example. Z₅²
has the following projective equivalence
classes:

Answer 2

[01] = {01, 02, 03, 04} ,
[10] = {10, 20, 30, 40} ,
[11] = {11, 22, 33, 44} ,
[12] = {12, 24, 31, 43} ,
[13] = {13, 21, 34, 42} ,
[14] = {14, 23, 32, 41} .
In general there are q − 1 elements in each class, so there are [(q^r ) −1]/[q−1]
projective equivalence classes.

Question 3

definition 14.3

H is PCM is a q-ary Hamming code,
denoted Ham(Fʳ_q).

Answer 3

Let H be a r × {qʳ -1}/{r −1} matrix (over F_q) each of whose columns belongs to a different class in P(Fʳ__q ).

then it is the PCM a q-ary hamming code Ham(Fʳ_q).

Question 4

GIVE PCM FOR
Ham(F₅²).

Answer 4

r=2 q=5

PCM is 2 x (5^2-1)/(4) = 2 x 6 matrix
could choose
H=[
0 1 1 1 1 1
1 0 1 2 3 4]
or
H’=
0 3 4 1 2 3
2 0 4 2 1 2

In H we chose from each class the unique vector whose first non-zero digit is 1;
and then ordered the vectors lexicographically.

Question 5

Ham(Fʳ_q).

thm for 14.5 min distance for hamming code

Answer 5

Theorem 14.5.
Ham(Fʳ_q). has minimum distance 3 and is perfect.

proof: exercise
(min distance 3: PCM , BPB satisfied)

Question 6

**
What coset leaders does a non binary haming code have?**

Syndrome decoding of hamming codes over non binary fields

Answer 6

Again we know that coset leaders are vectors of weight ≤ 1:
COSET LEADERS 0 vector & vectors ae_i

where a ∈ F_q \ {0} and 1 ≤ i ≤ n.

Question 7

background coset leaders hamming codes

Answer 7

For Hamming codes, the codewords are constructed in such a way that the weight of each codeword is equal to the Hamming distance between the codeword and the all-zero vector. The minimum distance of the Hamming code is 3, meaning that the smallest Hamming distance between any two distinct codewords is 3.

Therefore, to maintain the minimum distance of 3, coset leaders of Hamming codes must be vectors with a weight of 1 or 2.

Question 8

**
What syndromes does a non binary haming code have?**

Answer 8

Syndromes: S(0) = 0
S(aeᵢ) = aeᵢ H^T
=acᵢ

Question 9

Syndrome decoding scheme
non binary hamming code

Answer 9

SCHEME:
(i) receive y; compute S(y);

(ii) If S(y) = 0 then x = y;

(iii) any other S(y) ∈ F^r _q must lie in one of the classes of P(F^r_q),

so S(y) = acᵢ = S(aeᵢ) for some a ∈ Fq \ {0} and i ∈ {1, . . . , n}.

Decode by subtracting a from digit i:
y → x = y − aeᵢ

Question 10

Example:
Syndrome decoding scheme
Recall that F_4 = {0, 1, a, b} where a + b = ab = 1, a^2 = b and b^2 = a.

Give PCM for a hamming code
P(F^2 _4)

Answer 10

H=
0 1 1 1 1
1 0 1 a b

n= (4^2-1)/3 = 5
r=2
k=3
so it is a [5,3,3] code over F_4

Question 11

Example:
Syndrome decoding scheme
Suppose we receive y = bab10

Recall that F_4 = {0, 1, a, b} where a + b = ab = 1, a^2 = b and b^2 = a.
for a hamming code
P(F^2 _4)

PCM H=
0 1 1 1 1
1 0 1 a b

Answer 11

S(y) = (b, a, b, 1, 0)H^T
= (a + b + 1 + 0, b + b + a)
= (1 + 1, a) = (0, a) = a(0, 1) = ac_1 = S(ae_1)
so

y → x = y − ae_i
= (b − a, a, b, 1, 0) = 1ab10

which is the correct encoding