11 syndrome decoding Flashcards

1
Q

“syndrome decoding”

A

very likely to occur in exam

PCM makes decoding more efficient:
recieve vector y in F_q^n

compute coset it lies in by computing its syndrome
S(y)=z in F_q ⁿ⁻ᵏ

Find coset leader decode x=y-e

Note that we no longer need most of the standard array; just the coset leaders and their syndromes: a syndrome look-up table

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

def 11.1 Let H be a PCM for a [n, k]-code C over F_q ^n

The syndrome map of C is

A

H be a PCM for a [n, k]-code C over F_q ^n

The syndrome map of C is
S : F_q ⁿ → F_q ⁿ⁻ᵏ
S(y) = y Hᵀ

S(y) is the syndrome vector of y. This is a surjective linear map
C=ker S

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

cosets of C are in 1-1 correspondence with syndromes
lemma 11.2

A

Vectors u, v ∈ F_q ⁿ
are in the same coset of C iff
S(u) = S(v).

Proof: Indeed u and v are in the same coset iff u − v ∈ C iff
S(u − v) = 0 iff S(u) = S(v). □

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

cosets ?

A

= qⁿ/qᵏ= q ⁿ⁻ᵏ

= # vectors in F_q ⁿ⁻ᵏ
as cosets and syndromes are in bijection

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

example 11.3
Binary code gen by G=
[1 0 1 1]
[0 1 0 1 ]
gives PCM H
coset leaders
syndromes
decode y=1010

A

H=
1 0 1 0
1 1 0 1
The coset leaders for C are 0000, 1000, 0100, 0010, and the
syndromes: S(0000) = 00
S(1000)=11
S(0100) =01
S(0010) =10

y = 1010 then
yHT=01
so y is in the coset 0100 +
C. Thus we decode as x=y− 0100 = 1110.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

THM 11.4
DETERMINE THE MIN DISTANCE d(C) from the PCM H

A

Let C be a [n,k]-code over F_q with PCM H. Then

d(C) = d iff every set of d − 1 columns of H is linearly
independent, but there exists some set of d columns which is linearly dependent.

proof: consider columns of H . If x in X has weight w then H has a set of w columns linearly dependent. xH^t=0 and for these non zero coordinates we use the sum of these x rows of H^T IE COLS of H=0
ie the columns of H are linearly dependent.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

special cases of PCM and d(C):
has no 0 columns
no two columns are a multple of each other

A

d(C) ≥ 2 iff no set of 1 columns is LD ⇐⇒ H has no zero
columns.

d(C) ≥ 3 iff no set of 2 columns is LD ⇐⇒ no two columns of H are a multiple of each other columns.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

E.g 11.5 what is the d(C) for binary code generated by..
G=
[1011]
[0101 ]

A

Work out H first then look at cols
H=
[1010
1101]
no o cols d(C)
one col is a multiple of another
d(C)>=2

in G there is a row of weight 2 d(C)>=2
d(C)=2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is d(C) for the binary code generated by
G=
[10110
01101] PCM
H=
[1 1 1 0 0
1 0 0 1 0
0 1 0 0 1]

A

columns of H:
no 0 col
no repeated col d(C)>=3
G rows weight 3.

c_1+c_3+c_4=0 so d(C)<= 3 (since 10110 in C)

d(C)=3

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

11.6. Example. Consider linear code C over Z11 with PCM
H =

1 1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 X

where X = 10 (Roman numeral).

what is d(C)?

A

This C has length 10 (number of columns of H), redundancy 2 (number of rows), so dimension 8.

No two columns are a multiple of each other, so d(C) ≥ 3. We have c1 − 2c2 + c3 = 0 so

1910000000 ∈ C, so d(C) ≤ 3. Hence d(C) = 3 — it is a single
error correcting code.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

11.6. Example. Consider linear code C over Z11 with PCM
H =

1 1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 X

where X = 10 (Roman numeral).

COSET LEADERS? How would we decode

A

Since d(C) = 3 every vector of weight ≤ 1 is a coset leader of C
(by our earlier result). There are 100 weight 1 vectors in Z₁₁¹⁰
namely all non-zero multiples de_i of all e_i (standard ordered basis elements).

S(de_i)= (d,d_i)

receive y in Z₁₁¹⁰
compute S(y)=(a,b) in Z₁₁²

if (a,b)=(0,0) then y in C decode x=y

if a,b both non zero assume single error
x=y-ae_i

if only one of a,b is non zero y is not in a coset led by a
weight 1 or 0 vector. Therefore at least 2 errors have occured.Request retransmission

partial scheme as some weight 2 coset leaders but we didnt use standard array

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

11.6. Example. Consider linear code C over Z11 with PCM
H =

1 1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 X

where X = 10 (Roman numeral).

decode y = 1025234260 ∈ Z₁₁¹⁰

A

S(y)=(3,10)
in {0,..10}

so assume error is A = 3 in digit
i = A^−1B = 3−1 × 10 = 4 × 10 = 7. Thus subtract 3 from y_7:
x = 1025231260

check in C: xH^T=0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

11.6. Example. Consider linear code C over Z11 with PCM
H =

1 1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 X

where X = 10 (Roman numeral).

decode y = 2610197034 ∈ Z₁₁¹⁰

A

y = 2610197034 has A = 0 and B ̸= 0 (check
it!), so seek retransmission in this case.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

PARTIAL DECODING SCHEME SUMMARY

A

This partial decoding generalises to d = 2t + 1.
All vectors of weight ≤ t are coset leaders: list their syndromes. If
we receive y with S(y) in the list decode it; else seek
retransmission.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly