11 syndrome decoding Flashcards
“syndrome decoding”
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
def 11.1 Let H be a PCM for a [n, k]-code C over F_q ^n
The syndrome map of C is
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
cosets of C are in 1-1 correspondence with syndromes
lemma 11.2
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). □
cosets ?
= qⁿ/qᵏ= q ⁿ⁻ᵏ
= # vectors in F_q ⁿ⁻ᵏ
as cosets and syndromes are in bijection
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
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.
THM 11.4
DETERMINE THE MIN DISTANCE d(C) from the PCM H
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.
special cases of PCM and d(C):
has no 0 columns
no two columns are a multple of each other
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.
E.g 11.5 what is the d(C) for binary code generated by..
G=
[1011]
[0101 ]
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
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]
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
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)?
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.
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
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
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₁₁¹⁰
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
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₁₁¹⁰
y = 2610197034 has A = 0 and B ̸= 0 (check
it!), so seek retransmission in this case.
PARTIAL DECODING SCHEME SUMMARY
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.
