Linear Code #
Suppose $\bF$ is a finite field. Then $\bF^n$ is a vector space over $\bF$.
Linear code #
A linear code $L$ is a linear subspace of $\bF^n$.
The class of all linear codes in $\bF^n _ q$ of dimension $k$ and minimum distance $d$ is denoted as $[n, k, d] _ q$.
In coding theory, we use the convention where codewords correspond to row vectors $u \in \bF^{1 \times k}$.
- $r = n - k$ is called the redundancy of the linear code.
- Any matrix $G \in \bF^{k \times n}$ whose row space $\row(G) = \col(G^T) = \span\p{G _ {i, \cdot}} _ {i = 1}^k = L$, is called a generator matrix of linear code $L$.
- Any matrix $H \in \bF^{(n - k) \times n}$ whose null space $\null(H) = \c{x \in \bF^{n}: Hx = 0} = L$, is called a parity check matrix of linear code $L$.
Permutation equivalence #
Suppose $\sigma \in S _ n$ is a permutation on $\c{1, \ldots, n}$.
- For $c = (c _ 1, \ldots, c _ n) \in \bF^n$, define $\sigma(c) := (c _ {\sigma(1)}, \ldots, c _ {\sigma(n)})$.
- Define $P _ {\sigma} \in \c{0, 1}^{n \times n}$ as $(P _ \sigma) _ {ij} = 1(i = \sigma(j))$.
- It is called the column permutation matrix.
- It permutes columns by $\sigma$ when acting on the right. Since $$ (AP _ {\sigma}) _ {ik} = A _ {ij} (P _ {\sigma}) _ {jk} = A _ {ij} 1(j = \sigma(k)) = A _ {i, \sigma(k)} $$
- It is straight forward to give the inverse matrix of $P _ {\sigma}$, since $$ (P _ {\sigma^{-1}}) _ {ij} = 1(i = \sigma^{-1}(j)) = 1(j = \sigma(i)) = (P _ \sigma)^{-1} = P _ {\sigma}^T $$
- $\det P _ \sigma = \operatorname{sgn}(\sigma)$, which is a basic fact from linear algebra.
- Block code $C \subseteq \bF^n$ and $\sigma[C]$ are called permutation-equivalent.
- It is an equivalence relationship on block codes on $\bF^n$.
Standard form of the generating matrix #
Given a generating matrix $G \in \bF^{k \times n}$ of linear code $L$.
- First reduce $G$ into RREF by row operations, represented by left application of $E \in \bF^{k \times k}$.
- Next, permute all leading columns to the left by apply $P _ {\sigma}$ to the right.
$$ G' = EGP _ \sigma =\left[\begin{array}{ccccccc} 1 & 0 & \ldots & 0 & b _ {1, m+1} & \ldots & b _ {1 n} \\ 0 & 1 & \ldots & 0 & b _ {2, m+1} & \ldots & b _ {2 n} \\ & \vdots & & \vdots & & \vdots & \\ 0 & 0 & \ldots & 1 & b _ {m, m+1} & \ldots & b _ {m n} \end{array}\right] = [I _ k | A] $$
where $I _ k \in \bF^{k \times k}, A \in \bF^{k \times (n - k)}$. $G'$ is a generating matrix of permuted linear code $L' = \sigma[L]$.
The generating matrix $G'$ is said of the standard form.
Similarly, we can transform any parity check matrix $H$ into $EHP _ {\sigma} = H' = [B| I _ {n - k}]$, which is the standard form of a parity check matrix.
Compute $H$ from $G$ #
Given generating matrix $G \in \bF^{k \times n}$, first transform it into the standard form.
- Reduce $G$ into RREF by left application of $E$.
- Permute columns of $G$ into $[I _ k | A]$ with right application of $P _ {\sigma}$.
That is $G' = EGP _ {\sigma} = [I _ k | A]$. Now define $H' = [-A^T | I _ {n - k}]$.
- Clearly $H'$ has full rank, and $H' (G')^T = \O$.
- Observe that $$ H'(G')^T = H'(EGP _ {\sigma})^T = H'P _ {\sigma^{-1}} G^T E^T = \O \implies H' P _ {\sigma^{-1}}G^T = \O $$
- Now define $H = H'P _ {\sigma^{-1}}$.
$H$ is the desired parity check matrix.
Compute $G$ from $H$ #
Given parity check matrix $H \in \bF^{(n - k) \times n}$, first transform it into the standard form.
- Reduce $H$ into RREF by left application of $E$.
- Permute columns of $H$ into $[B|I _ {n -k}]$ with right application of $P _ {\sigma}$.
That is $H' = EHP _ {\sigma} = [B|I _ {n - k}]$. Now define $G' := [I _ k | -B^T]$.
- Clearly $G'$ has full rank, and $H' (G')^T = \O$.
- Observe that $$ H'(G')^T = EHP _ {\sigma}(G')^T = E H (G'P _ {\sigma^{-1}})^T = \O \implies H(G' P _ {\sigma^{-1}})^T = \O $$
- Now define $G = G'P _ {\sigma^{-1}}$.
$G$ is the desired generating matrix.
Dual code #
Given linear code $L \subseteq \bF^n$, with a generating matrix $G$ and parity check matrix $H$.
There exists a unique linear code $L^\perp \subseteq \bF^n$ with generating matrix $H$ and parity check matrix $G$.
$L^\perp$ is called the dual code of $L$.
- Since $GH^T = \O _ {k \times(n - k)}$, we have $HG^T = \O _ {(n - k) \times k}$.
- $\dim L + \dim L^\perp = n$.
Minimum weight and distance of linear codes #
Suppose $L \subseteq \bF^n$ is a linear code with generator matrix $G \in \bF^{k \times n}$ and parity check matrix $H \in \bF^{(n - k) \times n}$.
We have $d(L) = w(L)$ (minimum distance = minimum weight). $$ d(L) = \min _ {x, y \in L} d(x, y) = \min _ {x, y \in L} d(0, y - x) = \min _ {z \in L} w(z) = w(L) $$ $w(L)$ is directly encoded in $H$. Note that $w(L) = i$ if and only if:
- Any $i - 1$ columns in $H$ are linearly independent.
- Otherwise there would be a codeword of weight less than $w(L)$.
- There exists $i$ columns in $H$ that are linearly dependent.
Syndrome and cosets #
Given linear code $L \subseteq \bF^n$ with parity check matrix $H$.
Suppose $w \in \bF^k$ is encoded into $x \in \bF^n$. And the received word is $y \in \bF^n$.
Suppose $y = x + e$ where $e \in \bF^n$ is the error. The syndrome of $y$ is defined as $$ \syn(y):= H y^T = H(x + e)^T = H e^T $$
- $\syn: \bF^n \to \bF^{n - k}$ is a linear map by definition.
- $\syn$ is surjective, since $H$ has full rank.
- $\null(\syn) = L$, since $H$ is the parity check matrix of $L$.
- $\syn(y) = \syn(x + e) = \syn(e)$.
There is a one-to-one correspondence between cosets in $\bF^n / L$ and syndromes in $\bF^{n - k}$.
- By fundamental theorem of linear maps, $\bF^{n - k} \simeq \bF^n / L$.
Syndrome decoding #
Syndrome decoding is an efficient way to implement minimum distance decoding of linear codes.
Consider $[n, k]$-linear code $L \subseteq \bF^n$.
- Define the weight of coset $w(x + L)$ as the minimum weight of all vectors in $x + L$.
- $v \in x + L$ is called the leader of coset $x + L$ if $w(v) = w(x + L)$.
- A coset of weight at most $P _ r(L)$ has a unique coset leader.
- Suppose $v$ is a coset leader of $x + L$ where $w(x + L) \le P _ r(L)$.
- Then for all $u \in x + L$, $d(u, v) \ge d(L)$.
- Therefore $d(u, 0) = w(u) \ge {d(L) - w(v)} > w(v)$.
Syndrome decoding is the following implementation of minimum distance decoding:
- Precompute a table pairing syndromes with coset leaders.
- Note that some syndromes may not have a unique coset leader.
- For each received $y \in \bF^n$, compute the syndrome $s = \syn(y)$.
- Suppose $e \in \bF^n$ is the coset leader, return ${\hat x} =y - e$.