Week 5 The dual code. Syndrome decoding

Version 2023-11-01. To PDF of this week only Open the whole set of notes in PDF

Synopsis. Every linear code \(C\) has a dual code, \(C^\perp ,\) and check matrices. While a generator matrix \(G\) is used to encode messages into codevectors, a check matrix \(H\) serves to detect errors — and to correct them using syndrome decoding.

Motivation. The inner product of vectors

Let \(C\) be a linear code. Given a received vector \(\ul y,\) how to test whether \(\ul y\in C\)? Storing all codevectors of \(C\) is not an option for codes of large length and dimension, whose use is dictated by modern applications to low-noise channels. Storing just a generator matrix \(G\) of \(C\) is better in terms of storage space, but testing whether \(\ul y\) is in the row space of \(G\) can be computationally demanding.

Some codes, however, are defined by a single checksum — recall the even weight code and the ISBN-10 code. A checksum of a given vector is easy to compute.

Extending the checksum approach, we introduce a check matrix which generates the dual code. It turns out that this construction helps to correct errors as well (not just detect). The first notion we need is:

Definition: inner product

For \(\ul u, \ul v \in \F _q^n,\) the scalar (element of \(\F _q)\) defined as \(\ul u \cdot \ul v =\sum _{i=1}^n u_i v_i \) is called the inner product of the vectors \(\ul u\) and \(\ul v.\)

Example: some inner products in \(\F _2^3\)

For \(111,101\in \F _2^3,\) one has

\[ 111\cdot 111=1^2+1^2+1^2=1, \ 111\cdot 101 = 1\cdot 1 + 1\cdot 0 + 1\cdot 1 = 0, \ 101\cdot 101 = 1^2+0^2+1^2=0. \]

If \(C\subset \F _q^n\) is a set, \(\ul v\in \F _q^n,\) we may write \(\ul v \cdot C\) to denote the set \(\{\ul v \cdot \ul c \mid \ul c\in C\}.\)

Properties of the inner product

(1) Expression as a matrix product: \(\ul u \cdot \ul v = \ul u \,\ul v^T.\)

Explanation: we write elements of \(\F _q^n\) as row vectors. Thus, \(\ul u\) is a row vector \((u_1,\ldots ,u_n),\) and \(\ul v^T\) is the transpose of \(\ul v,\) so a column vector \(\left (\begin {smallmatrix} v_1\\ v_2 \\ \vdots \\ v_n \end {smallmatrix}\right ).\) Multiplying \(\ul u,\) an \(1\times n\) matrix, and \(\ul v^T,\) an \(n\times 1\) matrix, we obtain a \(1\times 1\) matrix, which we identify with a scalar in \(\F _q.\)

(2) Symmetry: \(\ul u\cdot \ul v=\ul v \cdot \ul u.\) (Explanation: this is easily seen from the definition.)

(3) Bilinearity: for a scalar \(\lambda \in \F _q\) we have \((\ul u + \lambda \ul w) \cdot \ul v = \ul u \cdot \ul v + \lambda (\ul w \cdot \ul v)\) and \(\ul u\cdot (\ul v + \lambda w) = \ul u \cdot \ul v + \lambda (\ul u \cdot \ul w).\) (Explanation: from linear algebra, the matrix product in \(\ul u \,\ul v ^T\) is bilinear.)

(4) Non-degeneracy: \(\ul u\cdot \F _q^n=\{0\},\) if and only if \(\ul u=0.\)

Explanation: let \(\ul \epsilon _i=(0,\ldots ,0,1,0,\ldots ,0)\) be the vector with \(i\)th symbol \(1\) and all other symbols \(0.\) Then \(\ul u\cdot \ul \epsilon _i=u_i.\) So if \(\ul u\cdot \F _q^n=\{0\},\) then in particular \(\ul u\cdot \ul \epsilon _i=0\) hence \(u_i=0,\) for all \(i,\) meaning that \(\ul u\) is the zero vector. And if \(\ul u=\ul 0,\) then \(\ul u\cdot \ul c=0\) for all \(\ul c\in \F _q^n.\)

The dual code

Definition: dual code

Given a code \(C \subseteq \F _q^n,\) we define the dual code \(C^\perp \) as

\[ C^\perp = \{\ul v \in \F _q^n \mid \ul v \cdot C = \{0\}\} . \]

We can say that \(C^\perp \) consists of all vectors orthogonal to the code \(C\) (where \(\ul v\) orthogonal to \(C\) means \(\ul v\cdot C=\{0\}).\)

  • Exercise. Using bilinearity of the inner product, show that \(C^\perp \) is a linear code.

Recall that \(\Rep (n,\F _2)=\{00\ldots 0, 11\ldots 1\}\subseteq \F _2^n\) is the binary repetition code of length \(n.\) We now work out the code \(\Rep (n,\F _2)^\perp \) using the definition.

By definition, \(\Rep (n,\F _2)^\perp = \{\ul v\in \F _2^n \mid \ul v \cdot 00\ldots 0=0, \ \ul v\cdot 11\ldots 1=0\}.\) The first condition, \(\ul v\cdot \ul 0=0\) is vacuous (holds for all vectors \(\ul v\in \F _2^n).\) The second condition, \(\ul v\cdot 11\ldots 1,\) means \(v_1+v_2+\ldots +v_n=0\) in \(\F _2,\) i.e., \(\ul v\in E_n,\) the binary even weight code of length \(n.\) Thus:

Example: the dual code of the binary repetition code

\(\Rep (n,\F _2)^\perp = E_n.\)

Check matrices

Definition: check matrix

A check matrix for a linear code \(C\) means a generator matrix for \(C^\perp .\)

One sometimes says parity check matrix (the term arose from applications of binary codes).

Theorem 5.1: properties of the dual code and a check matrix

If \(C\subseteq \F _q^n\) is a linear code of dimension \(k,\) then:

  • i. \(\dim C^\perp =n-k;\)

  • ii. \(C=\{\ul v\in \F _q^n: \ul v H^T=\ul 0\}\) for any check matrix \(H\) of \(C.\)

  • Proof. We recall the Rank-Nullity Theorem from Linear Algebra: if \(M\) is a matrix with \(n\) columns, then

    \[ \mathrm {rank}(M)+\dim \mathrm {Nullspace}(M)=n, \]

    where \(\mathrm {rank}(M)\) is the dimension of the span of the rows of \(M,\) and \(\mathrm {Nullspace}(M)\) can be written as \(\{\ul v\in \F _q^n: M\ul v^T=\overline 0\}.\)

    i. Consider the matrix \(\begin {bmatrix}C\end {bmatrix}\) made up of all codevectors of \(C\) used as rows. The \(\mathrm {Nullspace}(\begin {bmatrix}C\end {bmatrix})\) is the set \(\{\ul v: \begin {bmatrix}C\end {bmatrix}\ul v^T=\overline 0\}.\) Note that the column vector \(\begin {bmatrix}C\end {bmatrix}\ul v^T\) is \(\begin {bmatrix} \ul c_1 \ul v^T \\ \ul c_2 \ul v^T \\ \vdots \end {bmatrix} = \begin {bmatrix} \ul c_1 \cdot \ul v \\ \ul c_2 \cdot \ul v\\ \vdots \end {bmatrix},\) which is zero if and only if the inner product \(\ul c \cdot \ul v\) is \(0\) for all rows \(\ul c\) of \(\begin {bmatrix} C \end {bmatrix},\) i.e., for all codevectors \(\ul c\) of \(C.\) By definition of the dual code, this happens exactly when \(\ul v\in C^\perp ,\) so \(\mathrm {Nullspace}(\begin {bmatrix}C\end {bmatrix}) = C^\perp .\) By rank-nullity, \(\dim C^\perp = n - \mathrm {rank}(\begin {bmatrix}C\end {bmatrix}).\) Since the rows of \(\begin {bmatrix}C\end {bmatrix}\) span \(C,\) one has \(\mathrm {rank}(\begin {bmatrix}C\end {bmatrix})=\dim C=k\) and so \(\dim C^\perp = n - k.\)

    ii. By definition \(H\) generates the code \(C^\perp ;\) so by i., \(H\) has \(n-k\) rows, \(H=\begin {bmatrix} \ul r_1 \\ \vdots \\ \ul r_{n-k} \end {bmatrix}.\) Thus, \(\mathrm {rank}(H)=\dim C^\perp =n-k,\) and so by rank-nullity, \(\dim \mathrm {Nullspace}(H)=n-(n-k)=k.\) Note that \(C\subseteq \mathrm {Nullspace}(H):\) indeed, if \(\ul c\in C,\) then \(\ul r_i \ul c^T = \ul r_i \cdot \ul c = 0\) for all \(i\) because \(\ul r_i\in C^\perp ,\) which means that \(H\ul c^T=\overline 0.\) Since \(\dim C = \dim \mathrm {Nullspace}(H),\) it follows that \(C=\mathrm {Nullspace}(H),\) which is \(\{\ul v: H\ul v^T=\overline 0\}.\)

    The law \((AB)^T=B^TA^T\) for the product of matrices implies that \((\ul vH^T)^T=H\ul v^T,\) and so \(H\ul v^T\) is zero iff \(\ul vH^T\) is. Thus, \(C=\{\ul v\in \F _q^n: \ul v H^T=\ul 0\}\) as claimed. □

The syndrome of a vector

Definition: syndrome

Let \(H\) be a check matrix for a linear code \(C\subseteq \F _q^n.\) Let \(\ul y\in \F _q^n.\) The vector

\[ S(\ul y)=\ul y H^T \]

is called the syndrome of \(\ul y.\) The linear map \(S\colon \F _q^n \to \F _q^{n-k}\) is the syndrome map.

Proposition 5.2: syndromes of vectors in the same coset

Let \(S\) be a syndrome map for a linear code \(C\subseteq \F _q^n.\) If \(\ul v,\ul y\in \F _q^n,\)

  • • \(S(\ul v)=S(\ul y)\) \(\iff \) \(\ul v,\ul y\) are in the same coset of \(C;\)

  • • \(S(\ul v)=\ul 0\) \(\iff \) \(\ul v\in C.\)

  • Proof. \(\ul yH^T=\ul vH^T\) \(\iff \) \((\ul y - \ul v)H^T=\ul 0\) \(\iff \) \(\ul y-\ul v\in C.\) By definition of cosets, this means that \(\ul v\) is in the coset of \(\ul y.\) In particular, \(S(\ul v)=\ul 0\) means \(\ul v\in \ul 0+C=C.\) □

The use of syndromes in error detection and correction

If \(S(\ul y)\ne 0,\) \(\ul y\) is not a codevector, so the syndrome map detects errors in a received vector.

To correct errors, we need to construct a decoder for the linear code \(C.\) If we know a check matrix \(H\) for \(C,\) we can improve the standard array decoder for \(C.\) We will write the same decoder differently; it will require much less memory but more calculations.

Algorithm 5.3: the syndrome decoder

Preparation. Construct a table of syndromes, with \(q^{n-k}\) rows, of the form

.
Coset leader \(\ul a_i\) \(S(\ul a_i)\)

Start with the top row: the codeword \(\ul 0\) and its syndrome \(S(\ul 0)=\ul 0.\)

At each step, choose a vector \(\ul a_i\in \F _q^n\) of smallest weight such that \(S(\ul a_i)\) does not appear in the table; then \(\ul a_i\) is a coset leader of a new coset.

Decoding.

  • • Receive a vector \(\ul y\in \F _q^n.\)

  • • Calculate \(S(\ul y)=\ul y H^T.\)

  • • In the table, find \(\ul a_i\) with \(S(\ul a_i)=S(\ul y).\) Then \(\ul a_i\) is the coset leader of \(\ul y+C.\)

  • • Return \(\Decode (\ul y)=\ul y-\ul a_i.\)

Remark. The syndrome decoder is based on a choice of one coset leader in every coset. This is the same as for the standard array decoder.

In fact, if the same coset leaders are chosen in both decoders, both decoders with yield the same function \(\Decode \colon \F _q^n \to C.\) They differ only in the way this function is computed.

The number of arithmetic operations required to calculate the syndrome \(S(\ul y)=\ul y H^T\) can be of order \(n^2,\) whereas the standard array decoder requires \(\sim n\) operations to look up a vector. On the other hand, the amount of memory required by the syndrome decoder is proportional to \(q^{n-k}\) which is better than \(q^n\) for the standard array. The advantage is especially significant for codes with high code rate \(\dfrac kn.\)

Nevertheless, for codes which have more algebraic structure (than just linear codes), decoding algorithms exist which require even less storage, but the computation complexity is higher compared to syndrome decoding. Some examples will appear from the next chapter onwards.

Example: example of syndrome decoding

Let \(C\) be the binary linear code with check matrix \(H=\left [\begin {array}{cc|cccc} 0&0&1&0&0&0\\ 1&0& 0&1&0&0 \\ 1&1&0&0&1&0\\ 0&1&0&0&0&1 \end {array}\right ].\)

  • (a) Construct the table of syndromes for \(C\) using the matrix \(H.\)

  • (b) Using the table of syndromes, decode the received vector \(\ul y=111111.\)

Solution.

(a) When calculating syndromes, it is useful to observe that the syndrome of a vector \(0\ldots 010\ldots 0\) (with \(1\) in position \(i\) and \(0\)s elsewhere) is equal to the \(i\)th column of \(H,\) transposed.

The syndrome map is linear, so the syndrome of a sum of two vectors is the sum of their syndromes, etc.

For example, \(S(011000) = 0011+1000=1011\) (the sum of the second and the third columns of \(H,\) transposed).

.
vector syndrome leader?
\(000000\) \(0000\) yes
\(000001\) \(0001\) yes
\(000010\) \(0010\) yes
\(000100\) \(0100\) yes
\(001000\) \(1000\) yes
\(010000\) \(0011\) yes
\(100000\) \(0110\) yes

All vectors of weight \(1\) have different syndromes, so they all are coset leaders. We need more coset leaders, hence we start looking at vectors of weight \(2,\) then weight \(3:\)

.
\(000011\) \(0011\) no, syndrome already in the table
\(000101\) \(0101\) yes
\(001001\) \(1001\) yes
\(001010\) \(1010\) yes
\(001100\) \(1100\) yes
\(010100\) \(0111\) yes
\(011000\) \(1011\) yes
\(101000\) \(1110\) yes
\(001101\) \(1101\) yes
\(011100\) \(1111\) yes

When we try a vector, say of weight \(2,\) and find that is syndrome is already in the table, we ignore that vector and try another one.

We found \(16=2^{6-2}\) coset leaders so we stop.

(b) \(S(111111)=1010\) which is the syndrome of the coset leader \(001010\) in the table. Therefore, \(\Decode (111111)=111111-001010=110101.\)