ldpc.mod2

Assorted functions to work with binary vectors and matrices

ldpc.mod2.inverse(matrix)

Computes the left inverse of a full-rank matrix.

Notes

The `left inverse’ is computed when the number of rows in the matrix exceeds the matrix rank. The left inverse is defined as follows:

Inverse(M.T@M)@M.T

We can make a further simplification by noting that the row echelon form matrix with full column rank has the form:

row_echelon_form=P@M=vstack[I,A]

In this case the left inverse simplifies to:

Inverse(M^T@P^T@P@M)@M^T@P^T@P=M^T@P^T@P=row_echelon_form.T@P

Parameters: matrix (numpy.ndarray) – The binary matrix to be inverted in numpy.ndarray format. This matrix must either be square full-rank or rectangular with full-column rank.
Returns: The inverted binary matrix
Return type: numpy.ndarray

Examples

>>> # full-rank square matrix
>>> mat=np.array([[1,1,0],[0,1,0],[0,0,1]])
>>> i_mat=inverse(mat)
>>> print(i_mat@mat%2)
[[1 0 0]
 [0 1 0]
 [0 0 1]]

>>> # full-column rank matrix
>>> mat=np.array([[1,1,0],[0,1,0],[0,0,1],[0,1,1]])
>>> i_mat=inverse(mat)
>>> print(i_mat@mat%2)
[[1 0 0]
 [0 1 0]
 [0 0 1]]

ldpc.mod2.mod10_to_mod2(dec, length=0)

Converts a decimal number to a binary number, with optional padding to produce a binary vector of a given length.

Parameters

dec (int) – Decimal number (base 10).
length (int, optional) – The length of the binary string. If the specified `length’ is greater than the bit-length of the binary number the output is left-padded with zeros. The default `length’ is set to zero.

Returns

A binary integer list encoding the binary represenation of the inputted decimal number

Return type

list

Examples

>>> mod10_to_mod2(2,length=5)
[0, 0, 0, 1, 0]

ldpc.mod2.mod2_to_mod10(binary_arr)

Converts binary number represented as a list to a decimal number.

Parameters: binary_arr (list) – A binary number represented as the entries of a list
Returns: The decimal representation of the inputted binary array
Return type: int

Examples

>>> mod2_to_mod10([0,0,0,1,0])
2

ldpc.mod2.nullspace(matrix)

Computes the nullspace of the matrix M. Also sometimes referred to as the kernel.

All vectors x in the nullspace of M satisfy the following condition:
Mx=0

orall x in nullspace(M)

Why does this work?

The transformation matrix, P, transforms the matrix M into row echelon form, ReM:
P@M=ReM=[A,0]^T,
where the width of A is equal to the rank. This means the bottom n-k rows of P must produce a zero vector when applied to M. For a more formal definition see the Rank-Nullity theorem.

matrix: numpy.ndarray
A binary matrix in numpy.ndarray format

numpy.ndarray
A binary matrix where each row is a nullspace vector of the inputted binary matrix
>>> H=np.array([[0, 0, 0, 1, 1, 1, 1],[0, 1, 1, 0, 0, 1, 1],[1, 0, 1, 0, 1, 0, 1]])
>>> print(nullspace(H))
[[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]]

ldpc.mod2.rank(matrix)

Returns the rank of a binary matrix

Parameters: matrix (numpy.ndarray) – A binary matrix in numpy.ndarray format
Returns: The rank of the matrix
Return type: int

Examples

>>> H=np.array([[1,0,0],[0,1,0],[0,0,1]])
>>> print(rank(H))
3

>>> H=np.array([[1,1,0],[0,1,1],[1,0,1]])
>>> print(rank(H))
2

ldpc.mod2.reduced_row_echelon(matrix)

Converts matrix to reduced row echelon form such that the output has the form rre=[I,A]

Parameters

matrix (numpy.ndarray) – A binary matrix in numpy.ndarray format

Returns

reduced_row_echelon_from (numpy.ndarray) – The reduced row echelon form of the inputted matrix in the form rre=[I,A]
matrix_rank (int) – The binary rank of the matrix
transform_matrix_rows (numpy.ndarray) – The transformation matrix for row permutations
transform_matrix_cols (numpy.ndarray) – The transformation matrix for the columns

Examples

>>> H=np.array([[0, 0, 0, 1, 1, 1, 1],[0, 1, 1, 0, 0, 1, 1],[1, 0, 1, 0, 1, 0, 1]])
>>> rre=reduced_row_echelon(H)[0]
>>> print(rre)
[[1 0 0 1 1 0 1]
 [0 1 0 1 0 1 1]
 [0 0 1 0 1 1 1]]

ldpc.mod2.row_basis(matrix)

Outputs a basis for the rows of the matrix.

Parameters: matrix (numpy.ndarray) – The input matrix
Returns: A numpy.ndarray matrix where each row is a basis element.
Return type: numpy.ndarray

Examples

>>> H=np.array([[1,1,0],[0,1,1],[1,0,1]])
>>> rb=row_basis(H)
>>> print(rb)
[[1 1 0]
 [0 1 1]]

ldpc.mod2.row_echelon(matrix, full=False)

Converts a binary matrix to row echelon form via Gaussian Elimination

Parameters

matrix (numpy.ndarry or scipy.sparse) – A binary matrix in either numpy.ndarray format or scipy.sparse
full (bool, optional) – If set to `True’, Gaussian elimination is only performed on the rows below the pivot. If set to `False’ Gaussian eliminatin is performed on rows above and below the pivot.

Returns

row_ech_form (numpy.ndarray) – The row echelon form of input matrix
rank (int) – The rank of the matrix
transform_matrix (numpy.ndarray) – The transformation matrix such that (transform_matrix@matrix)=row_ech_form
pivot_cols (list) – List of the indices of pivot num_cols found during Gaussian elimination

Examples

>>> H=np.array([[1, 1, 1],[1, 1, 1],[0, 1, 0]])
>>> re_matrix=row_echelon(H)[0]
>>> print(re_matrix)
[[1 1 1]
 [0 1 0]
 [0 0 0]]

>>> re_matrix=row_echelon(H,full=True)[0]
>>> print(re_matrix)
[[1 0 1]
 [0 1 0]
 [0 0 0]]

ldpc.mod2.row_span(matrix)

Outputs the span of the row space of the matrix i.e. all linear combinations of the rows

Parameters: matrix (numpy.ndarray) – The input matrix
Returns: A numpy.ndarray matrix with rows reperesenting all linear combinations of the rows of the inputted matrix.
Return type: numpy.ndarray

Examples

>>> H=np.array([[1,1,0],[0,1,1],[1,0,1]])
>>> print(row_span(H))
[[0 0 0]
 [0 1 1]
 [1 0 1]
 [1 1 0]]