"""Classical error-correcting codes
Copyright 2023 The qLDPC Authors and Infleqtion Inc.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
"""
from __future__ import annotations
import itertools
from collections.abc import Sequence
import galois
import networkx as nx
import numpy as np
import numpy.typing as npt
from qldpc.abstract import DEFAULT_FIELD_ORDER
from .common import ClassicalCode
[docs]
class RepetitionCode(ClassicalCode):
"""Classical repetition code."""
def __init__(self, bits: int, field: int | None = None) -> None:
self._field = galois.GF(field or DEFAULT_FIELD_ORDER)
self._matrix = self.field.Zeros((bits - 1, bits))
for row in range(bits - 1):
self._matrix[row, row] = 1
self._matrix[row, row + 1] = -self.field(1)
[docs]
class RingCode(ClassicalCode):
"""Classical ring code: repetition code with periodic boundary conditions."""
def __init__(self, bits: int, field: int | None = None) -> None:
self._field = galois.GF(field or DEFAULT_FIELD_ORDER)
self._matrix = self.field.Zeros((bits, bits))
for row in range(bits):
self._matrix[row, row] = 1
self._matrix[row, (row + 1) % bits] = -self.field(1)
[docs]
class HammingCode(ClassicalCode):
"""Classical Hamming code."""
def __init__(self, rank: int, field: int | None = None) -> None:
"""Construct a Hamming code of a given rank."""
self._exact_distance = 3
self._field = galois.GF(field or DEFAULT_FIELD_ORDER)
if self.field.order == 2:
# parity check matrix: columns = all nonzero bitstrings
bitstrings = list(itertools.product([0, 1], repeat=rank))
self._matrix = self.field(bitstrings[1:]).T
else:
# More generally, columns = [maximal set of linearly independent strings], so collect
# together all strings whose first nonzero element is a 1.
strings = [
(0,) * top_row + (1,) + rest
for top_row in range(rank - 1, -1, -1)
for rest in itertools.product(range(self.field.order), repeat=rank - top_row - 1)
]
self._matrix = self.field(strings).T
[docs]
class ReedSolomonCode(ClassicalCode):
"""Classical Reed-Solomon code.
Source: https://galois.readthedocs.io/en/v0.3.8/api/galois.ReedSolomon/
References:
- https://errorcorrectionzoo.org/c/reed_solomon
- https://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes6.pdf
"""
def __init__(self, bits: int, dimension: int) -> None:
ClassicalCode.__init__(self, galois.ReedSolomon(bits, dimension).H)
[docs]
class BCHCode(ClassicalCode):
"""Classical binary BCH code.
Source: https://galois.readthedocs.io/en/v0.3.8/api/galois.BCH/
References:
- https://errorcorrectionzoo.org/c/bch
- https://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes6.pdf
"""
def __init__(self, bits: int, dimension: int) -> None:
if "0" in format(bits, "b"):
raise ValueError("BCH codes only defined for 2^m - 1 bits with integer m.")
ClassicalCode.__init__(self, galois.BCH(bits, dimension).H)
[docs]
class ReedMullerCode(ClassicalCode):
"""Classical Reed-Muller code.
References:
- https://errorcorrectionzoo.org/c/reed_muller
- https://feog.github.io/10-coding.pdf
"""
def __init__(self, order: int, size: int, field: int | None = None) -> None:
self._assert_valid_params(order, size)
self._exact_distance = 2 ** (size - order)
self._order = order
self._size = size
generator = ReedMullerCode.get_generator(order, size)
self._matrix = ClassicalCode(generator, field).generator
self._field = galois.GF(field or DEFAULT_FIELD_ORDER)
[docs]
@classmethod
def get_generator(cls, order: int, size: int) -> npt.NDArray[np.int_]:
"""Get the generator matrix for the specified Reed-Muller code."""
cls._assert_valid_params(order, size)
if order == 0:
return np.ones(2**size, dtype=int)
if order == size:
return np.identity(2**size, dtype=int)
mat_a = cls.get_generator(order, size - 1)
mat_b = cls.get_generator(order - 1, size - 1)
mat_z = np.zeros_like(mat_b)
return np.block([[mat_a, mat_a], [mat_z, mat_b]]).astype(int)
@classmethod
def _assert_valid_params(self, order: int, size: int) -> None:
if not (size >= 0 and 0 <= order <= size):
raise ValueError(
"Reed-Muller code R(r,m) must have m >= 0 and 0 <= r <= m\n"
+ f"Provided: (r,m) = ({order},{size})"
)
[docs]
class TannerCode(ClassicalCode):
"""Classical Tanner code, as described in DOI:10.1109/TIT.1981.1056404.
A Tanner code T(G,C) is constructed from:
[1] A bipartite "half-regular" graph G. That is, a graph...
... with two sets of nodes, V and W.
... in which all nodes in V have degree n.
[2] A classical code C on n bits.
For convenience, we make G directed, with edges directed from V to W. The node sets V and W can
then be identified, respectively, by the sources and sinks of G.
The Tanner code T(G,C) is defined on |W| bits. A |W|-bit string x is a code word of T(G,C) iff,
for every node v in V, the bits of x incident to v are a code word of C.
This construction requires an ordering the edges E(v) adjacent to each vertex v. This class
sorts E(v) by the value of the "sort" attribute attached to each edge. If there is no "sort"
attribute, its value is treated as corresponding neighbor of v.
Tanner codes can similarly be defined on regular (undirected) graphs G' = (V',E') by placing
checks on V' and bits on E'.
Notes:
- If the subcode C has m checks, its parity matrix has shape (m,n).
- The code T(G,C) has |W| bits and |V|m checks.
"""
subgraph: nx.DiGraph
subcode: ClassicalCode
def __init__(self, subgraph: nx.Graph, subcode: ClassicalCode) -> None:
"""Construct a classical Tanner code."""
if not isinstance(subgraph, nx.DiGraph):
subgraph = TannerCode.as_directed_subgraph(subgraph)
self.subgraph = subgraph
self.subcode = subcode
sources = [node for node in subgraph if subgraph.in_degree(node) == 0]
sinks = [node for node in subgraph if subgraph.out_degree(node) == 0]
sink_indices = {sink: idx for idx, sink in enumerate(sorted(sinks))}
num_bits = len(sinks)
num_checks = len(sources) * subcode.num_checks
matrix = np.zeros((num_checks, num_bits), dtype=int)
for idx, source in enumerate(sorted(sources)):
checks = range(subcode.num_checks * idx, subcode.num_checks * (idx + 1))
bits = [sink_indices[sink] for sink in self._get_sorted_neighbors(source)]
matrix[np.ix_(checks, bits)] = subcode.matrix
ClassicalCode.__init__(self, matrix, subcode.field.order)
def _get_sorted_neighbors(self, node: object) -> Sequence[object]:
"""Sorted neighbors of the given node."""
return sorted(
self.subgraph.neighbors(node),
key=lambda neighbor: self.subgraph[node][neighbor].get("sort", neighbor),
)
[docs]
@classmethod
def as_directed_subgraph(self, subgraph: nx.Graph) -> nx.DiGraph:
"""Convert an undirected graph for a Tanner code into a directed graph for the same code."""
directed_subgraph = nx.DiGraph()
for node_a, node_b, edge_data in subgraph.edges(data=True):
edge = frozenset([node_a, node_b])
directed_subgraph.add_edge(node_a, edge)
directed_subgraph.add_edge(node_b, edge)
if (sort_data := edge_data.pop("sort", None)) is not None:
directed_subgraph[node_a][edge]["sort"] = sort_data[node_a]
directed_subgraph[node_b][edge]["sort"] = sort_data[node_b]
return directed_subgraph