Block Codes¶

Codewords¶

A $q$-ary block code, denoted $\mathcal{C}$, consists of a set of $M$ vectors, referred to as codewords.

Each codeword is of fixed length $n$ and is represented as:

where $m$ is the index of the codeword ($1 \leq m \leq M$), and each component $c_{mi}$ (for $1 \leq i \leq n$) is a symbol from an alphabet of size $q$.

The code can be mathematically expressed as:

where $\mathcal{X}$ is the alphabet with $|\mathcal{X}| = q$, and $\mathcal{X}^n$ denotes the set of all possible sequences of length $n$ over $\mathcal{X}$.

Alphabet and Symbols¶

The alphabet $\mathcal{X}$ comprises $q$ distinct symbols, such as $\{0, 1\}$ for a binary code ($q = 2$) or $\{0, 1, 2, 3\}$ for a quaternary code ($q = 4$).

Each component of a codeword, $c_{mi} \in \mathcal{X}$, determines the code’s structure and its applicability in various systems.

Binary Codes¶

When $q = 2$, the alphabet is binary, consisting of symbols $\{0, 1\}$, and the code is termed a binary code.

In this case, each codeword is a vector of $n$ bits:

For example, a binary codeword of length $n = 4$ might be $\vec{c}_1 = (1, 0, 1, 1)$.

Relation Between $q$-ary and Binary Representation¶

If the alphabet size is a power of 2, i.e., $q = 2^b$ for some positive integer $b$, each $q$-ary symbol can be represented as a $b$-bit binary sequence.

For instance, if $q = 4 = 2^2$, the alphabet $\{0, 1, 2, 3\}$ can be mapped as:

This mapping enables efficient encoding of $q$-ary symbols into binary form for storage or transmission.

Transformation of Nonbinary Codes to Binary Codes¶

A nonbinary code with block length $K$ consists of codewords with $K$ $q$-ary symbols.

Such a code can be transformed into a binary code of length $n = bK$ by representing each $q$-ary symbol (where $q = 2^b$) as its $b$-bit binary equivalent.

For example, consider a quaternary code ($q = 4$) with block length $K = 2$ and a codeword $\vec{c}_1 = (2, 3)$.

Using the mapping above, $2 \to 10$ and $3 \to 11$, the codeword is transformed into a binary sequence of length $n = bK = 2 \times 2 = 4$:

Formally, a nonbinary code $\mathcal{C} \subseteq \mathcal{X}^K$ (with $|\mathcal{X}| = q$) is converted to a binary code $\mathcal{C}' \subseteq \{0, 1\}^{bK}$, where each symbol in $\mathcal{X}$ is expanded into $b$ bits.

Example of a $q$-ary Block Code¶

A $q$-ary block code $\mathcal{C}$ is defined with:

• Alphabet: $q = 3$, $\mathcal{X} = \{0, 1, 2\}$ (ternary).

• Block length: $K = 2$.

• Number of codewords: $M = 9$.

The code consists of all possible sequences of length $K = 2$:

Each codeword $\vec{c}_m = (c_{m1}, c_{m2})$, with $c_{mi} \in \{0, 1, 2\}$, satisfies $\mathcal{C} \subseteq \mathcal{X}^K$, where $|\mathcal{X}|^K = 3^2 = 9$.

This code has no error-correcting capability (minimum Hamming distance 1), but it exemplifies a $q$-ary block code structure.

Conversion to Binary Block Code¶

To convert $\mathcal{C}$ to a binary block code $\mathcal{C}'$, each ternary symbol is mapped to a 2-bit sequence ($b = \lceil \log_2 3 \rceil = 2$):

Each codeword of length $K = 2$ becomes a binary codeword of length:

Transforming the codewords:

• $(0,0) \to (00, 00) \to (0,0,0,0)$,

• $(0,1) \to (00, 01) \to (0,0,0,1)$,

• $(0,2) \to (00, 10) \to (0,0,1,0)$,

• $(1,0) \to (01, 00) \to (0,1,0,0)$,

• $(1,1) \to (01, 01) \to (0,1,0,1)$,

• $(1,2) \to (01, 10) \to (0,1,1,0)$,

• $(2,0) \to (10, 00) \to (1,0,0,0)$,

• $(2,1) \to (10, 01) \to (1,0,0,1)$,

• $(2,2) \to (10, 10) \to (1,0,1,0)$.

The binary code is:

Parameters of $\mathcal{C}'$¶

• Alphabet: $q' = 2$, $\mathcal{X}' = \{0, 1\}$.

• Block length: $n = 4$.

• Number of codewords: $M = 9$.

The code $\mathcal{C}' \subseteq \{0, 1\}^4$, with $|\{0, 1\}^4| = 2^4 = 16$, preserves the size $M = 9$ and has a minimum Hamming distance of 1, consistent with the original code.

Review of Hamming Distance¶

The Hamming distance is a metric to measure the difference between two codewords of equal length.

It quantifies the number of positions at which their corresponding symbols differ, assessing a code’s error-detecting and error-correcting capabilities.

Definition¶

For two codewords $\vec{c}_1 = (c_{11}, c_{12}, \ldots, c_{1n})$ and $\vec{c}_2 = (c_{21}, c_{22}, \ldots, c_{2n})$ of length $n$ over an alphabet $\mathcal{X}$, the Hamming distance, denoted $d_H(\vec{c}_1, \vec{c}_2)$, is defined as:

where:

Thus, $d_H(\vec{c}_1, \vec{c}_2)$ counts the number of indices $i$ (for $1 \leq i \leq n$) where $c_{1i} \neq c_{2i}$.

Example¶

Consider a ternary ($q = 3$) block code with codewords of length $n = 3$ over $\mathcal{X} = \{0, 1, 2\}$.

Let two codewords be:

Compute the Hamming distance:

• Position 1: $c_{11} = 0$, $c_{21} = 0$, so $\delta(0, 0) = 0$.

• Position 2: $c_{12} = 1$, $c_{22} = 2$, so $\delta(1, 2) = 1$.

• Position 3: $c_{13} = 2$, $c_{23} = 1$, so $\delta(2, 1) = 1$.

Thus:

The Hamming distance between $\vec{c}_1$ and $\vec{c}_2$ is 2, indicating they differ in two positions.

Note that the Hamming distance of 2 refers to the distance between two specific codewords, $\vec{c}_1 = (0, 1, 2)$ and $\vec{c}_2 = (0, 2, 1)$, which differ in two positions.

This does not imply that 2 is the minimum distance of the code, as other pairs in the (unspecified) code could have smaller distances.

Application in Error Detection and Correction¶

The minimum Hamming distance of a code, $\min_{\vec{c}_i \neq \vec{c}_j} d_H(\vec{c}_i, \vec{c}_j)$, determines its error-correcting capability.

A code can detect up to $d-1$ errors and correct up to $\lfloor (d-1)/2 \rfloor$ errors, where $d$ is the minimum distance.

$(n, k)$ Code¶

In a binary block code of length $n$, there are $2^n$ possible codewords, representing all possible combinations of $n$ bits over the alphabet $\{0, 1\}$.

From this set, $M = 2^k$ codewords, where $k < n$, are selected to form an $(n, k)$ code.

Each codeword uniquely corresponds to a $k$-bit information block, with the $n - k$ redundant bits enabling error detection or correction.

This encoding process, often implemented via a generator matrix or systematic encoding, defines the code’s structure.

The code rate, given by:

quantifies the fraction of information bits per codeword, reflecting the trade-off between data efficiency and error-correcting capability.

For a general $q$-ary code over an alphabet of $q$ symbols, there are $q^n$ possible codewords.

Selecting $M = q^k$ codewords, where $k < n$, allows the encoding of $k$-symbol information blocks, with each symbol carrying $\log_2 q$ bits of information.

This generalizes the binary case ($q = 2$), offering increased flexibility in code design for diverse applications, such as high-density data transmission or robust error correction in nonbinary channels.

The code rate remains $R_c = \frac{k}{n}$, and the choice of $q$ influences the code’s error-correcting power, often measured by the minimum Hamming distance.

Connection Between $(n, k)$ Code and $q$-ary Block Code¶

We can say that the $(n, k)$ code is a specific parameterization of a $q$-ary block code tailored for error control.

Recall the general structure as:

• $q$-ary Block Code: A $q$-ary block code $\mathcal{C}$ consists of $M$ codewords, each a vector of length $n$ (or $K$ in the revised version), with components drawn from an alphabet of $q$ symbols.

  The code is a subset of all possible sequences:

  $$\mathcal{C} \subseteq \mathcal{X}^n, \quad |\mathcal{X}| = q, \quad |\mathcal{C}| = M.$$

  (15)

  The number of codewords $M$ and the block length ($n$ or $K$) are general parameters, and the code may be binary ($q = 2$) or nonbinary ($q > 2$).

• $(n, k)$ Code: The $(n, k)$ code is a specific type of block code where the number of codewords is explicitly defined as $M = q^k$ for a $q$-ary alphabet, and each codeword has length $n$.

  Thus, it is a $q$-ary block code with:

  $$|\mathcal{C}| = q^k, \quad k < n.$$

  (16)

  The parameters $n$ and $k$ define the codeword length and the size of the information block, respectively.

Thus, we can see that the $(n, k)$ code is a $q$-ary block code with a constrained size, where the number of codewords is $M = q^k$.

The $q$-ary block code is a more general concept, allowing any $M \leq q^n$, whereas the $(n, k)$ code fixes $M$ to encode exactly $k$ $q$-ary symbols of information, introducing structure for error control.

Weight (Overview)¶

A key codeword parameter is its weight, defined as the number of nonzero elements it contains, reflecting its density of active symbols.

Each codeword in a code typically has a unique weight, and the collection of all weights forms the weight distribution.

If all $M$ codewords share the same weight, the code is classified as a fixed-weight or constant-weight code.

Linear Block Codes¶

Linear block codes (LBCs), a prominent subset of block codes, have been extensively studied over recent decades due to their advantageous properties.

Their linearity ensures easier implementation and analysis, as operations follow algebraic rules, reducing computational complexity.

LBCs perform comparably to the broader class of block codes, making them practical without significant loss in efficacy.

An LBC $\mathcal{C}$ is a $k$-dimensional subspace within an $n$-dimensional space, termed an $(n, k)$ code.

For binary LBCs, $\mathcal{C}$ contains $2^k$ sequences of length $n$, closed under addition: if $\vec{c}_1, \vec{c}_2 \in \mathcal{C}$, then $\vec{c}_1 + \vec{c}_2 \in \mathcal{C}$.

This closure ensures the all-zero vector $\vec{0}$ is always a codeword, a property stemming from the linear structure.

Review of Arithmetic in $\text{GF}(2)$¶

In coding theory, particularly for binary linear block codes, the underlying algebraic structure is the finite field $\text{GF}(2)$.

Arithmetic operations (addition, subtraction, multiplication, and division, where applicable) are computed with the result taken modulo 2, ensuring that outputs remain in the set $\{0, 1\}$.

The operations in $\text{GF}(2)$ are defined as follows:

• Addition (mod 2):

  $$0 + 0 = 0, \quad 0 + 1 = 1, \quad 1 + 0 = 1, \quad 1 + 1 = 0$$

  (17)

  This is equivalent to the exclusive OR (XOR) operation:

  • $1 + 1 = 0$ because $1 + 1 = 2$, and $2 \mod 2 = 0$.

  • Addition is commutative and associative, and the additive identity is 0.

  • Each element is its own additive inverse: $0 + 0 = 0$, $1 + 1 = 0$.

  • This is often denoted by the symbol $\oplus$ in coding theory.

• Subtraction: Since $\text{GF}(2)$ has characteristic 2, subtraction is identical to addition:

  $$a - b = a + b \pmod{2}$$

  (18)

  For example, $1 - 1 = 1 + 1 = 0$.

• Multiplication (mod 2):

  $$0 \cdot 0 = 0, \quad 0 \cdot 1 = 0, \quad 1 \cdot 0 = 0, \quad 1 \cdot 1 = 1$$

  (19)

  This is equivalent to the logical AND operation.

  • The multiplicative identity is 1.

  • Division is only defined for non-zero elements (i.e., 1), and $1 \div 1 = 1$.

• Modulo 2: Taking an integer modulo 2 maps it to $\{0, 1\}$:

  $$k \mod 2 = \begin{cases} 0 & \text{if } k \text{ is even}, \\ 1 & \text{if } k \text{ is odd}. \end{cases}$$

  (20)

  For example, in vector operations, all components are 0 or 1, and sums like $1 + 1 + 1 = 3 \mod 2 = 1$ arise.

Generator Matrix for LBC¶

In an LBC, the mapping from $M = 2^k$ information sequences of length $k$ to $2^k$ codewords of length $n$ is represented by a $k \times n$ generator matrix $\mathbf{G}$, where:

Here, $\vec{u}_m$ is a $k$-bit information sequence, and $\vec{c}_m$ is its corresponding codeword.

The matrix $\mathbf{G}$ encapsulates the linear transformation, enabling systematic encoding by defining how information bits generate codewords, streamlining both design and hardware realization.

The rows of $\mathbf{G}$, denoted $\vec{g}_i$ for $1 \leq i \leq k$, are codewords corresponding to the $k$ standard basis vectors of the information space (e.g., $(1,0,\ldots,0)$, etc.), structured as:

Thus, a codeword is:

where summation occurs in the Galois Field $\mathrm{GF}(2)$ (modulo-2 arithmetic), ensuring binary operations.

The code $\mathcal{C}$ is the row space of $\mathbf{G}$, encompassing all linear combinations of its rows.

Two LBCs, $\mathcal{C}_1$ and $\mathcal{C}_2$, are equivalent if their generator matrices share the same row space, possibly after column permutation, indicating that code properties depend on the subspace, not the specific matrix representation.

Parity Check Bits¶

When the generator matrix $\mathbf{G}$ of a linear block code is structured as Proakis (2007, Eq. (7.2-4)):

where $\mathbf{I}_k$ is a $k \times k$ identity matrix and $\mathbf{P}$ is a $k \times (n - k)$ matrix, the code is classified as systematic.

In systematic codes, the first $k$ components of a codeword directly correspond to the information sequence, explicitly retaining the original data.

The subsequent $n - k$ components, termed parity check bits, are generated from the information bits using $\mathbf{P}$ and provide redundancy to mitigate transmission errors.

It is noteworthy that any linear block code can be converted into an equivalent systematic form, as represented by the above equation, through elementary row operations (such as row swapping or addition) and column permutations, preserving the code’s essential characteristics while achieving this structured format.

Example¶

To demonstrate the conversion of a linear block code into an equivalent systematic form, consider a $(4, 2)$ binary linear block code (codeword length $n = 4$, information bits $k = 2$) with the generator matrix:

This matrix is not in systematic form, as it lacks the structure $\mathbf{G} = [\mathbf{I}_k | \mathbf{P}]$, where $\mathbf{I}_k$ is the $2 \times 2$ identity matrix.

Perform Elementary Row Operations

The objective is to transform the first $k = 2$ columns into the identity matrix $\mathbf{I}_2 = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$.

The first column of $\mathbf{G}_1$ is already $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$.

To achieve $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$ in the second column, we need a 0 in position (1, 2) (currently 1) and a 1 in position (2, 2) (already 1).

Perform the row operation: $\text{Row 1} \gets \text{Row 1} + \text{Row 2}$ (in $\text{GF}(2)$, addition is XOR):

The resulting matrix is:

The first two columns now form $\mathbf{I}_2$, so the matrix is in systematic form:

Note that no column permutations were required here, as the first two columns were transformed into $\mathbf{I}_2$ using row operations.

Preservation of Code Characteristics

The matrix $\mathbf{G}_2$ generates codewords equivalent to those of $\mathbf{G}_1$. For an information sequence $\vec{u} = [u_1, u_2]$, the codeword using $\mathbf{G}_2$ is:

The original matrix $\mathbf{G}_1$ produces:

The codewords span the same code (up to permutation), preserving the error-correcting properties, such as the minimum distance.

This example shows how a single row operation transforms $\mathbf{G}_1$ into the systematic $\mathbf{G}_2$, maintaining the code’s essential characteristics.

Dual Code and Parity Check Matrix¶

An orthogonal complement of code $\mathcal{C}$ consists of all $n$-dimensional binary vectors orthogonal to every codeword in $\mathcal{C}$.

Since $\mathcal{C}$ constitutes a $k$-dimensional subspace within the $n$-dimensional binary vector space, its orthogonal complement forms an $(n - k)$-dimensional subspace.

This subspace defines an $(n, n - k)$ code, denoted $\mathcal{C}^\perp$, referred to as the dual code of $\mathcal{C}$.

The generator matrix of $\mathcal{C}^\perp$, an $(n - k) \times n$ matrix, has rows orthogonal to those of $\mathbf{G}$, the generator matrix of $\mathcal{C}$.

This matrix, known as the parity check matrix of $\mathcal{C}$ and denoted $\mathbf{H}$, satisfies the condition that for every codeword $\vec{c} \in \mathcal{C}$:

This orthogonality property enables $\mathbf{H}$ to serve as a mechanism for verifying membership in $\mathcal{C}$, leveraging the algebraic structure of linear codes for error detection.

Parity Check Matrix Properties¶

A binary $n$-dimensional vector $\vec{c}$ satisfies $\vec{c} \, \mathbf{H}^{\sf T} = \vec{0}$ if and only if it resides in the orthogonal complement of the row space of $\mathbf{H}$, which corresponds exactly to $\mathcal{C}$.

Thus, this equation establishes a necessary and sufficient condition for $\vec{c} \in \{0, 1\}^n$ to be a codeword, rendering $\mathbf{H}$ an effective tool for codeword identification.

Given that the rows of $\mathbf{G}$ are codewords, it follows that:

For systematic codes where $\mathbf{G} = [\mathbf{I}_k | \mathbf{P}]$, the parity check matrix is expressed as Proakis (2007, Eq. (7.2-7)):

In the binary field (GF(2)), where modulo-2 arithmetic applies, $-\mathbf{P}^{\sf T} = \mathbf{P}^{\sf T}$, simplifying $\mathbf{H}$ to $[ \mathbf{P}^{\sf T} | \mathbf{I}_{n-k} ]$.

This configuration ensures that the product $\mathbf{G} \mathbf{H}^{\sf T} = \vec{0}$ holds, as the interaction between $\mathbf{P}$ and $\mathbf{P}^{\sf T}$ aligns with the identity matrices to satisfy the orthogonality condition.

Example¶

We illustrate the concepts of the dual code and parity check matrix, consider a $(4, 2)$ linear block code $\mathcal{C}$ over $\text{GF}(2)$, with codeword length $n = 4$ and information bits $k = 2$.

The dual code $\mathcal{C}^\perp$ is a $(4, n - k) = (4, 2)$ code.

Define the Code $\mathcal{C}$

Let the generator matrix of $\mathcal{C}$ be:

This is in systematic form, $\mathbf{G} = [\mathbf{I}_2 | \mathbf{P}]$, where:

The codewords are generated as $\vec{c} = \vec{u} \mathbf{G}$ for $\vec{u} = [u_1, u_2]$. Computing all codewords:

• $\vec{u} = [0, 0]$: $\vec{c} = [0, 0, 0, 0]$

• $\vec{u} = [1, 0]$: $\vec{c} = [1, 0, 1, 0]$

• $\vec{u} = [0, 1]$: $\vec{c} = [0, 1, 1, 1]$

• $\vec{u} = [1, 1]$: $\vec{c} = [1, 0, 1, 0] + [0, 1, 1, 1] = [1, 1, 0, 1]$

Thus:

This is a 2-dimensional subspace of $\mathbb{F}_2^4$.

Find the Dual Code $\mathcal{C}^\perp$

Note that all arithmetic is mod 2.

The dual code $\mathcal{C}^\perp$ consists of all $\vec{x} = [x_1, x_2, x_3, x_4] \in \mathbb{F}_2^4$ such that $\vec{x} \cdot \vec{c} = 0$ for all $\vec{c} \in \mathcal{C}$.

Since $\mathcal{C}$ is spanned by the rows of $\mathbf{G}$, $\vec{x}$ must be orthogonal to:

• Row 1: $[1, 0, 1, 0]$, so $x_1 + x_3 = 0 \implies x_1 = x_3$

• Row 2: $[0, 1, 1, 1]$, so $x_2 + x_3 + x_4 = 0 \implies x_2 = x_3 + x_4$

Let $x_3 = a$, $x_4 = b$. Then $x_1 = a$, $x_2 = a + b$, so $\vec{x} = [a, a + b, a, b]$.

The codewords are:

• $a = 0, b = 0$: $\vec{x} = [0, 0, 0, 0]$

• $a = 1, b = 0$: $\vec{x} = [1, 1, 1, 0]$

• $a = 0, b = 1$: $\vec{x} = [0, 1, 0, 1]$

• $a = 1, b = 1$: $\vec{x} = [1, 0, 1, 1]$

Thus:

This is a $(4, 2)$ code, with dimension $n - k = 2$.

Construct the Parity Check Matrix $\mathbf{H}$

The parity check matrix $\mathbf{H}$ of $\mathcal{C}$ is the generator matrix of $\mathcal{C}^\perp$, an $(n - k) \times n = 2 \times 4$ matrix. For a systematic $\mathbf{G}$, we have:

Thus:

The rows $[1, 1, 1, 0]$ and $[0, 1, 0, 1]$ are in $\mathcal{C}^\perp$.

Verify Orthogonality

For every $\vec{c} \in \mathcal{C}$, we must have $\vec{c} \, \mathbf{H}^{\sf T} = \vec{0}$, where:

Verify for each codeword:

• $\vec{c} = [0, 0, 0, 0]$: $[0, 0, 0, 0] \mathbf{H}^{\sf T} = [0, 0]$

• $\vec{c} = [1, 0, 1, 0]$: $[1, 0, 1, 0] \mathbf{H}^{\sf T} = [1 + 1, 0] = [0, 0]$

• $\vec{c} = [0, 1, 1, 1]$: $[0, 1, 1, 1] \mathbf{H}^{\sf T} = [1 + 1, 1 + 1] = [0, 0]$

• $\vec{c} = [1, 1, 0, 1]$: $[1, 1, 0, 1] \mathbf{H}^{\sf T} = [1 + 1, 1 + 1] = [0, 0]$

All satisfy $\vec{c} \, \mathbf{H}^{\sf T} = \vec{0}$.

Error Detection

The matrix $\mathbf{H}$ enables error detection. For a received vector $\vec{r}$, the syndrome is $\vec{s} = \vec{r} \mathbf{H}^{\sf T}$. If $\vec{s} = \vec{0}$, then $\vec{r} \in \mathcal{C}$. For example, test $\vec{r} = [1, 0, 0, 0]$:

This indicates $\vec{r} \notin \mathcal{C}$, detecting an error.

This example demonstrates that $\mathbf{H}$ is the parity check matrix of $\mathcal{C}$, generates $\mathcal{C}^\perp$, and supports error detection, as described.

EXAMPLE: (7, 4) Linear Block Code¶

Consider a (7, 4) linear block code with the generator matrix:

This structure, featuring a 4×4 identity matrix $\mathbf{I}_4$ followed by a 4×3 matrix $\mathbf{P}$, identifies it as a systematic code, where the first four bits of each codeword mirror the information sequence.

The corresponding parity check matrix is:

For an information sequence $\vec{u} = (u_1, u_2, u_3, u_4)$, the codeword $\vec{c} = (c_1, c_2, \ldots, c_7)$ is computed as:

Here, the first four components copy the input, while the last three (parity bits) are linear combinations over GF(2), enhancing error detection capability.