Background
Simplex codes are a family of binary linear codes that are duals of Hamming codes. For a given integer $m$, the binary simplex code has parameters $[2^m−1,m,2^{m−1}]$. These codes are notable for their large minimum distance and large autormorphism groups that are useful for compiling logic in quantum stabiliser codes.
Reference
See the Error Correction Zoo for a descripton of the Simplex Code Family.
🔢 Example for $m = 3$
For $m = 3$, the binary simplex code has parameters $[7, 3, 4]$, and its generator matrix $H_{\text{simplex}}$ is:
$$
H_{\text{simplex}} = \begin{bmatrix}
1 & 1 & 1 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 1 & 1 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 1 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 1 \\
\end{bmatrix}
$$
This matrix generates the simplex code, which is the dual of the $[7, 4, 3]$ Hamming code.
The corresponding parity-check matrix $H_{\text{hamming}}$ of the $[7, 4, 3]$ Hamming code is:
$$
H_{\text{hamming}} = \begin{bmatrix}
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 \\
\end{bmatrix}
$$
This matrix satisfies the condition $H_{\text{hamming}} \cdot H_{\text{simplex}}^T = 0$, confirming that the simplex code is indeed the dual of the Hamming code.
🔢 Example for $m = 4$
For $m = 4$, the binary simplex code has parameters $[15, 4, 8]$, and its generator matrix $H_{\text{simplex}}$ is:
$$
H_{\text{simplex}} = \begin{bmatrix}
0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
\end{bmatrix}
$$
This matrix generates the simplex code, which is the dual of the $[15, 11, 3]$ Hamming code.
The corresponding parity-check matrix $H_{\text{hamming}}$ of the $[15, 11, 3]$ Hamming code is:
$$
H_{\text{hamming}} = \begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
\end{bmatrix}
$$
This matrix satisfies the condition $H_{\text{hamming}} \cdot H_{\text{simplex}}^T = 0$, confirming that the simplex code is indeed the dual of the Hamming code.
Pseudocode for Generating the Binary Simplex Code
Input:
m: Integer representing the dimension of the simplex code
Output:
H: Parity check matrix of the binary simplex code
Procedure:
1. Obtain the parity-check matrix H of the Hamming code of length $2^m - 1$ using `ldpc.codes.hamming_code(m)` function.
2. Compute the kernel (null space) of H over GF(2) using `ldpc.mod2.kernel(H)`. This yields the parity check matrix H_simplex of the simplex code.
3. Return H_simplex.
Python Function Template
import numpy as np
from ldpc.codes import hamming_code
from ldpc.mod2 import kernel
import scipy.sparse
def simplex_code(m: int) -> scipy.sparse.csr_matrix:
"""
Generate the generator matrix of a binary simplex code.
Parameters:
m (int): Dimension of the simplex code.
Returns:
H_simplex (np.ndarray): Generator matrix of shape (m, 2^m - 1).
"""
# Implement function here
return H_simplexUnitary Hack Instructions
- Location: Place the implementation in the src_python/ldpc/codes directory.
- Testing: Add corresponding tests in the python_test directory to validate the correctness of the generator matrix for various values of m.
