02 Linear Code

$$ \newcommand{aster}{*} \newcommand{exist}{\exists} \newcommand{B}{\mathbb B} \newcommand{C}{\mathbb C} \newcommand{I}{\mathbb I} \newcommand{N}{\mathbb N} \newcommand{Q}{\mathbb Q} \newcommand{R}{\mathbb R} \newcommand{Z}{\mathbb Z} \newcommand{eR}{\overline {\mathbb R}} \newcommand{cD}{ {\mathbb D}} \newcommand{dD}{ {\part \mathbb D}} \newcommand{dH}{ {\part \mathbb H}} \newcommand{eC}{\overline {\mathbb C}} \newcommand{A}{\mathcal A} \newcommand{D}{\mathcal D} \newcommand{E}{\mathcal E} \newcommand{F}{\mathcal F} \newcommand{G}{\mathcal G} \newcommand{H}{\mathcal H} \newcommand{J}{\mathcal J} \newcommand{L}{\mathcal L} \newcommand{U}{\mathcal U} \newcommand{M}{\mathcal M} \newcommand{O}{\mathcal O} \newcommand{P}{\mathcal P} \newcommand{S}{\mathcal S} \newcommand{T}{\mathcal T} \newcommand{V}{\mathcal V} \newcommand{W}{\mathcal W} \newcommand{X}{\mathcal X} \newcommand{Y}{\mathcal Y} \newcommand{bE}{\symbf E} \newcommand{bF}{\symbf F} \newcommand{bD}{\symbf D} \newcommand{bI}{\symbf I} \newcommand{bX}{\symbf X} \newcommand{bY}{\symbf Y} \newcommand{nz}{\mathcal Z} \newcommand{bT}{\mathbb T} \newcommand{bB}{\mathbb B} \newcommand{bS}{\mathbb S} \newcommand{bA}{\mathbb A} \newcommand{bL}{\mathbb L} \newcommand{bP}{\symbf P} \newcommand{bM}{\symbf M} \newcommand{bH}{\mathbb H} \newcommand{dd}{\mathrm d} \newcommand{Mu}{\mathup M} \newcommand{Tau}{\mathup T} \newcommand{ae}{\operatorname{a.e.}} \newcommand{aut}{\operatorname{aut}} \newcommand{adj}{\operatorname{adj}} \newcommand{char}{\operatorname{char}} \newcommand{cov}{\operatorname{Cov}} \newcommand{cl}{\operatorname{cl}} \newcommand{cont}{\operatorname{cont}} \newcommand{e}{\mathbb E} \newcommand{pp}{\operatorname{primitive}} \newcommand{dist}{\operatorname{dist}} \newcommand{diam}{\operatorname{diam}} \newcommand{fp}{\operatorname{Fp}} \newcommand{from}{\leftarrow} \newcommand{Gal}{\operatorname{Gal}} \newcommand{GCD}{\operatorname{GCD}} \newcommand{LCM}{\operatorname{LCM}} \newcommand{fg}{\mathrm{fg}} \newcommand{gf}{\mathrm{gf}} \newcommand{im}{\operatorname{Im}} \newcommand{image}{\operatorname{image}} \newcommand{inj}{\hookrightarrow} \newcommand{irr}{\operatorname{irr}} \newcommand{lcm}{\operatorname{lcm}} \newcommand{ltrieq}{\mathrel{\unlhd}} \newcommand{ltri}{\mathrel{\lhd}} \newcommand{loc}{ {\operatorname{loc}}} \newcommand{null}{\operatorname{null}} \newcommand{part}{\partial} \newcommand{pf}{\operatorname{Pf}} \newcommand{pv}{\operatorname{Pv}} \newcommand{rank}{\operatorname{rank}} \newcommand{range}{\operatorname{range}} \newcommand{re}{\operatorname{Re}} \newcommand{span}{\operatorname{span}} \newcommand{su}{\operatorname{supp}} \newcommand{sgn}{\operatorname{sgn}} \newcommand{syn}{\operatorname{syn}} \newcommand{var}{\operatorname{Var}} \newcommand{res}{\operatorname{Res}} \newcommand{data}{\operatorname{data}} \newcommand{erfc}{\operatorname{erfc}} \newcommand{erfcx}{\operatorname{erfcx}} \newcommand{tr}{\operatorname{tr}} \newcommand{col}{\operatorname{Col}} \newcommand{row}{\operatorname{Row}} \newcommand{sol}{\operatorname{Sol}} \newcommand{lub}{\operatorname{lub}} \newcommand{glb}{\operatorname{glb}} \newcommand{ltrieq}{\mathrel{\unlhd}} \newcommand{ltri}{\mathrel{\lhd}} \newcommand{lr}{\leftrightarrow} \newcommand{phat}{^\widehat{\,\,\,}} \newcommand{what}{\widehat} \newcommand{wbar}{\overline} \newcommand{wtilde}{\widetilde} \newcommand{iid}{\operatorname{i.i.d.}} \newcommand{Exp}{\operatorname{Exp}} \newcommand{abs}[1]{\left| {#1}\right|} \newcommand{d}[2]{D_{\text{KL}}\left (#1\middle\| #2\right)} \newcommand{n}[1]{\|#1\|} \newcommand{norm}[1]{\left\|{#1}\right\|} \newcommand{pd}[2]{\left \langle {#1},{#2} \right \rangle} \newcommand{argmax}[1]{\underset{#1}{\operatorname{argmax}}} \newcommand{argmin}[1]{\underset{#1}{\operatorname{argmin}}} \newcommand{p}[1]{\left({#1}\right)} \newcommand{c}[1]{\left \{ {#1}\right\}} \newcommand{s}[1]{\left [{#1}\right]} \newcommand{a}[1]{\left \langle{#1}\right\rangle} \newcommand{cc}[2]{\left(\begin{array}{c} #1 \\ #2 \end{array}\right)} \newcommand{f}{\mathfrak F} \newcommand{fi}{\mathfrak F^{-1}} \newcommand{Fi}{\mathcal F^{-1}} \newcommand{l}{\mathfrak L} \newcommand{li}{\mathfrak L^{-1}} \newcommand{Li}{\mathcal L^{-1}} \newcommand{const}{\text{const.}} $$

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:

  1. Precompute a table pairing syndromes with coset leaders.
    • Note that some syndromes may not have a unique coset leader.
  2. For each received $y \in \bF^n$, compute the syndrome $s = \syn(y)$.
  3. Suppose $e \in \bF^n$ is the coset leader, return ${\hat x} =y - e$.