My note when previewing Copying the Textbook of abstract algebra.

Form now on, only the theorems that is new to me are included in my note

Chapter 8: Maximum-Likelihood Decoding

Error-Detecting and Correcting Codes

  • Theorem 8.13

    $d_{min}=2n+1$ means correcting $n$ or fewer errors or detecting $2n$ or fewer errors.

Linear Codes

  • Group Code

    A code that is a subgroup of $\mathbb{Z}_2^n$

  • Lemma 8.17

    $w(\mathbf{x}+\mathbf{y})=d(\mathbf{x},\mathbf{y})$

  • Theorem 8.18

    $d_{min}=\min\{w(\mathbf{x}):\mathbf{x}\ne 0\}$

  • Theorem 8.21

    $H\in\mathbb{M}_{m\times n}(\mathbb{Z}_2)$, then $\mathrm{null}(H)$ is a group code

Parity-Check and Generator Matrices

  • Canonical Parity-Check Matrix

    $H=(A|I_m)$, $A\in\mathbb{M}_{m\times (n-m)}(\mathbb{Z}_2)$

  • Generator Matrix

    $G=(\frac{I_{n-m}}{A})$

  • Theorem 8.25

    1. If $H\in\mathbb{M}_{m\times n}(\mathbb{Z}_2)$ is a canonical parity-check matrix
    2. then Null(H) consists of all $\mathbf{x}\in\mathbb{Z}_2$ whose first $n-m$ bits are arbitrary but whose last $m$ bits are determined by $H\mathbf{x} = 0$.
    3. Each of the last $m$ bits serves as an even parity check bit for some of the first $n-m$ bits.
    4. Hence, $H$ gives rise to an $(n, n - m)$-block code.

  • Theorem 8.26

    1. Suppose that $G$ is an $n \times k$ standard generator matrix.
    2. Then $C = \{\mathbf{y} : G\mathbf{x} = \mathbf{y}\ for\ \mathbf{x} \in \mathbb{Z}_2^k\}$ is an $(n, k)$-block code.
    3. More specifically, $C$ is a group code.

  • Theorem 8.31

    Then the null space of $H$ is a single error-detecting code if and only if no column of $H$ consists entirely of zeros.

  • Theorem 8.34

    Let H be a binary matrix. The null space of $H$ is a single error-correcting code if and only if $H$ does not contain any zero columns and no two columns of $H$ are identical.

Efficient Decoding

  • Syndrome

    $H\mathbf{x}$, where $H$ is an $n\times m$-matrix, and $\mathbf{x}\in\mathbb{Z}_2^k$

  • Proposition 8.36

    $\mathbf{x}=\mathbf{c}+\mathbf{e}$, $\mathbf{x}$ is the code received, $\mathbf{c}$ is the codeword, $\mathbf{e}$ is the transmission error. Then $H\mathbf{x}=H\mathbf{e}$

  • Theorem 8.37

    1. Let $H\in\mathbb{M}_{m\times n}(\mathbb{Z}_2)$ and suppose that the linear code corresponding to $H$ is single error-correcting.
    2. Let $\mathbf{r}$ be a received $n$-tuple that was transmitted with at most one error.
    3. If the syndrome of $\mathbf{r}$ is $0$, then no error has occurred;
    4. Otherwise, if the syndrome of $\mathbf{r}$ is equal to some column of H, say the $i$-th column, then the error has occurred in the $i$-th bit.

  • Coset Decoding

    Coset or standard decoding uses the cosets of $C$ in $\mathbb{Z}_2^n$ to implement maximum-likelihood decoding.

  • Proposition 8.43

    1. Let $C$ be an $(n,k)$-linear code given by the matrix $H$ and suppose that $\mathbf{x}$ and $\mathbf{y}$ are in $\mathbb{Z}_2^n$ .
    2. Then $\mathbf{x}$ and $\mathbf{y}$ are in the same coset of $C$ if and only if $H\mathbf{x} = H\mathbf{y}$.
    3. That is, two n-tuples are in the same coset if and only if their syndromes are the same.