CSE5313 Coding and information theory for data science (Lecture 6)

Recap

Vector spaces and subspaces over finite fields

$\mathbb{F}^n$ is a vector space over $\mathbb{F}$.

With point-wise vector addition and scalar multiplication.

Let $V$ be a subspace of $\mathbb{F}^n$.

$V$ is a subgroup of $\mathbb{F}^n$ under vector addition $(\mathbb{F}^n,+)$.

• Apply the theorem: If $H$ is finite, non-empty, and closed under the operation of $G$, then $H$ is a subgroup of $G$.

Is every subgroup of $\mathbb{F}^n$ a subspace?

Cosets in this definition are called Affine subspaces.

New content

Linear codes

A linear code $\mathcal{C}$ is a subspace of $\mathbb{F}^n$ over $\mathbb{F}$.

• The dimension of $\mathcal{C}$ is denoted by $k$.
• The minimum Hamming distance of $\mathcal{C}$ is denoted by $d$.
• Notation $\mathcal{C}= [n,k,d]_{\mathbb{F}}$.

Two equivalent ways to constructing a linear code:

• A generator matrix $G\in \mathbb{F}^{k\times n}$ with $k$ rows and $n$ columns.

  $$\mathcal{C}=\{xG:x\in \mathbb{F}^k\}$$
  • The left image of $G$ is $\mathcal{C}$.
  • The rows of $G$ are a basis for $\mathcal{C}$.

• A parity check matrix $H\in \mathbb{F}^{(n-k)\times n}$ with $(n-k)$ rows and $n$ columns.

  $$\mathcal{C}=\{c\in \mathbb{F}^n:Hc^\top=0\}$$
  • The right kernel of $H$ is $\mathcal{C}$.
  • Multiplying $c^\top$ by $H$ “checks” if $c\in \mathcal{C}$.

Encoding of linear codes

Reminder:

• Encoding is the process of mapping a message $u\in \mathbb{F}^k$ to a codeword $c\in \mathcal{C}\subseteq \mathbb{F}^n$.

$E: \mathbb{F}^k\to \mathcal{C}$ is a linear map.

Let $\mathcal{C}= [n,k,d]_{\mathbb{F}}$ be a linear code with generator matrix $G\in \mathbb{F}^{k\times n}$.

• Encoding is given by $E(x)=xG$.
• It is injective (1-1). Suppose otherwise, then there exists $x_1,x_2\in \mathbb{F}^k$ such that $x_1G=x_2G$. Then $x_1G-x_2G=0\implies (x_1-x_2)G=0\implies x_1-x_2=0\implies x_1=x_2$. Therefore, $E$ is injective.

So linear codes implies linear encoding: $E(x)+E(y)=E(x+y)$.

Systematic codes

Fact: Every $G\in \mathbb{F}^{k\times n}$ can be brought to the form $G_{sys}=(I|A)$ by

• Row operations.
• Permutation of columns.

Fact $\{xG|x\in \mathbb{F}^k\}$ and $\{xG_{sys}|x\in \mathbb{F}^k\}$ are equivalent.

• Same length $n$.
• Same dimension $k$.
• Same minimum Hamming distance $d$.

Encoding a systematic code:

• The input is a part of the output.
• Efficient encoding
• Immediate decoding (if no errors).

Codes, cosets, encoding, decoding

Linear code $[n,k,d]_{\mathbb{F}}$ is a $k$ dimensional subspace of $\mathbb{F}^n$.

Size of the code is $|\mathbb{F}|^k$.

Encoding: $x\to xG$.

Decoding: $(y+e)\to x$, $y=xG$.

Use syndrome to identify which coset $\mathcal{C}_i$ that the noisy-code to $\mathcal{C}_i+e$ belongs to.

Syndrome decoding

• Heavily depends onn the linear structure of the code.

Linear code $\mathcal{C}= [n,k,d]_{\mathbb{F}}$ is a $k$-dimensional subspace of $(\mathbb{F}^n,+)$.

Shift of Linear code $[n,k,d]_{\mathbb{F}}$ is a $k$-dimensional affine subspace of $\mathbb{F}^n$.

All cosets of the same size

If $w_H(e)\leq \lfloor \frac{d-1}{2}\rfloor$, then it is possible to extract $y$ from $y+e$.

by syndrome decoding, we can do better than exhaustive search.

Idea:

Let $y+e$ belogns to the coset $\mathcal{C}+e$.

Moreover,$y_1+e$ and $y_2+e$ are in the same coset.

Standard Array

Let $\mathcal{C}= [n,k,d]_{\mathbb{F}}$ and denote $|F|=q$.

• Then $|\mathcal{C}|=q^k$.
• The number of cosets is $q^{n-k}$.

Then we arrange all $q^n$ elements of $\mathbb{F}^n$ into a $q^{n-k}\times q^k$ array.

• So that every row is a coset (including $\mathcal{C}$ itself)
• Lightest word in each cosets on the leftmost column

Any two elements in a row are of the form $y_1'=y_1+e$ and $y_2'=y_2+e$ for some $e\in \mathbb{F}^n$.

Same syndrome if $H(y_1'+e)^\top=H(y_2'+e)^\top$.

Entries in different rows have different syndrome.

Choose the lightest word in each coset on the leftmost column.

Time complexity: $O(n(n-k))$. Space complexity: $n|F|^n$ space.

Compare with exhaustive search: Time: $O(|F|^n)$.

Syndrome decoding - Intuition

Given $y'$, we identify the set $\mathcal{C} + e$ to which $y'$ belongs by computing the syndrome.

• We identify $e$ as the coset leader (leftmost entry) of the row $\mathcal{C} + e$.
• We output the codeword in $\mathcal{C}$ which is closest ($c'$) by subtracting $e$ from $y'$.

Syndrome decoding - Formal

Given $y'\in \mathbb{F}^n$, we identify the set $\mathcal{C}+e$ to which $y'$ belongs by computing the syndrome.

We identify $e$ as the coset leader (leftmost entry) of the row $\mathcal{C}+e$.

We output the codeword in $\mathcal{C}$ which is closest (example $c_3$) by subtracting $e$ from $y'$.