MerLean-example

8 Def 5: LDPC Code

Definition 59 Row Weight
#

For a linear map \(f : (\operatorname {Fin} n \to \mathbb {F}_2) \to _{\mathbb {F}_2} (\operatorname {Fin} m \to \mathbb {F}_2)\) and an index \(i : \operatorname {Fin} m\), the row weight of row \(i\) of the matrix representation of \(f\) is defined as

\[ \operatorname {rowWeight}(f, i) := \operatorname {hammingWeight}\! \left(\lambda \, j : \operatorname {Fin} n,\ f(\operatorname {Pi.single}\ j\ 1)\ i\right), \]

i.e., the number of column indices \(j\) such that the \((i,j)\)-entry of the matrix is nonzero.

Definition 60 Column Weight
#

For a linear map \(f : (\operatorname {Fin} n \to \mathbb {F}_2) \to _{\mathbb {F}_2} (\operatorname {Fin} m \to \mathbb {F}_2)\) and an index \(j : \operatorname {Fin} n\), the column weight of column \(j\) of the matrix representation of \(f\) is defined as

\[ \operatorname {colWeight}(f, j) := \operatorname {hammingWeight}\! \left(f(\operatorname {Pi.single}\ j\ 1)\right), \]

i.e., the number of row indices \(i\) such that the \((i,j)\)-entry of the matrix is nonzero.

Definition 61 Bounded Weight
#

A linear map \(f : (\operatorname {Fin} n \to \mathbb {F}_2) \to _{\mathbb {F}_2} (\operatorname {Fin} m \to \mathbb {F}_2)\) is said to have bounded weight \(w\) (for some \(w \in \mathbb {N}\)) if every row and every column of its matrix representation has Hamming weight at most \(w\):

\[ \operatorname {HasBoundedWeight}(f, w) \; :=\; \left(\forall \, i : \operatorname {Fin} m,\ \operatorname {rowWeight}(f, i) \leq w\right) \; \land \; \left(\forall \, j : \operatorname {Fin} n,\ \operatorname {colWeight}(f, j) \leq w\right). \]
Definition 62 LDPC Code Family
#

A family of CSS codes indexed by a type \(\iota \), say \(\{ C_\alpha \} _{\alpha \in \iota }\) where each \(C_\alpha \) is a CSS code with parameters \((n(\alpha ),\, r_X(\alpha ),\, r_Z(\alpha ))\), is called low-density parity-check (LDPC) if there exists a uniform bound \(w \in \mathbb {N}\) such that for every \(\alpha \in \iota \), both the parity-check matrix \(H_X\) and the transposed parity-check matrix \(H_Z^T\) (as stored in the CSS code structure) have bounded weight \(w\):

\[ \operatorname {IsLDPC}(\{ C_\alpha \} ) \; :=\; \exists \, w \in \mathbb {N},\ \forall \, \alpha \in \iota ,\ \operatorname {HasBoundedWeight}((C_\alpha ).H_X,\, w) \; \land \; \operatorname {HasBoundedWeight}((C_\alpha ).H_Z^T,\, w). \]

Note: Since the CSS code structure stores \(H_Z^T\) rather than \(H_Z\) directly, and since the weight bound \(w\) applies symmetrically to both rows and columns, the condition \(\operatorname {HasBoundedWeight}(H_Z^T, w)\) is equivalent to requiring that \(H_Z\) itself has all row weights and column weights bounded by \(w\).