Question: Alternative for removed poly_to_generator_matrix

[vprusso]

Reading the most up-to-date docs, I see that the changelog includes that poly_to_generator_matrix is no longer supported.

While the other elements in the changelog had some points about what to update in lieu of the change, this series of changes did not appear to have any such alternatives. Is there another way to achieve the same functionality with the up-to-date galois package that can be recommended?

Thank you again!

[mhostetter]

Ah, sorry for the breaking change for you.

My intent was for that functionality poly_to_generator_matrix() to be handled in the _CyclicCode class. And then you could make the code code = CyclicCode(n, k, d, poly) and access the generator matrix using code.G. However, I see that _CyclicCode is still private (hence the underscore).

The function you want to use still exists, it's just removed from the API. You can access it with galois._codes._cyclic._poly_to_generator_matrix(). I realize that's not pretty, but it is available. The code is here

galois/src/galois/_codes/_cyclic.py

Lines 193 to 222 in 25baec4

	def _poly_to_generator_matrix(n: int, generator_poly: Poly, systematic: bool) -> FieldArray:
	"""
	Converts the generator polynomial g(x) into the generator matrix G over GF(q).
	"""
	GF = generator_poly.field
	k = n - generator_poly.degree
	if systematic:
	# This is a more efficient Gaussian elimination of the generator matrix G that is produced
	# in non-systematic form
	I = GF.Identity(k)
	P = GF.Zeros((k, n - k))
	if n - k > 0:
	# Skip this section is n = k, which is the identity code (contains no parity)
	P[0, :] = generator_poly.coeffs[0:-1] / generator_poly.coeffs[-1]
	for i in range(1, k):
	P[i, 0] = 0
	P[i, 1:] = P[i - 1, 0:-1]
	if P[i - 1, -1] > 0:
	P[i, :] -= P[i - 1, -1] * P[0, :]
	G = np.hstack((I, P))
	else:
	# Assign the generator polynomial coefficients with highest degree starting along
	# the diagonals
	G = GF.Zeros((k, n))
	for i in range(k):
	G[i, i : i + generator_poly.degree + 1] = generator_poly.coeffs
	return G

in case you need to reference the inputs/outputs.

[vprusso]

Ah, gotcha--that's very helpful!

Now, if I may, I have a super trivial question about generating the parity check and generator matrices.

For example, I want to generate these for the Hamming [7,4] code. I presume I would do something like the following:

from galois._codes._cyclic import _poly_to_parity_check_matrix, _poly_to_generator_matrix

g = galois.primitive_poly(2, 3)
G = galois._codes._cyclic._poly_to_generator_matrix(7, g, systematic=False)
H = galois._codes._cyclic._poly_to_parity_check_matrix(7, g, systematic=False)
print(H)
>>> [[1 1 0 1 0 0 0]
>>>  [0 1 1 0 1 0 0]
>>>  [0 0 1 1 0 1 0]
>>>  [0 0 0 1 1 0 1]]

It seems odd to me that H is a 4 x 7 matrix (my naive impression from referring to this Wikipedia page would have me think that it should be a 3 x 7 matrix):

I'm not an expert in Galois fields or coding theory, so I'm likely asking something quite trivial and am outside of my element. Any input you could provide on the above in terms of being able to generate any matrices G and H for a general Hamming code would be much appreciated!

*(as an aside question, I take it the column order does not matter, right?)

Thank you again for the help, @mhostetter

[mhostetter]

Ah. So for _poly_to_parity_check_matrix(), you need to provide the parity-check polynomial as an input. For _poly_to_generator_matrix(), you need to provide the generator polynomial. (I realize now that the docstring here is wrong.)

The generator and parity-check polynomial are related like this $h(x) = (x^n - 1) / g(x)$. The _CyclicCode class instantiation does this.

galois/src/galois/_codes/_cyclic.py

Lines 24 to 53 in 25baec4

	def __init__(
	self,
	n: int,
	k: int,
	d: int,
	generator_poly: Poly,
	roots: FieldArray,
	systematic: bool,
	):
	verify_isinstance(n, int)
	verify_isinstance(k, int)
	verify_isinstance(d, int)
	verify_isinstance(generator_poly, Poly)
	verify_isinstance(roots, FieldArray)
	verify_isinstance(systematic, bool)
	self._generator_poly = generator_poly
	self._roots = roots
	# Calculate the parity-check polynomial h(x) = (x^n - 1) / g(x)
	f = Poly.Degrees([n, 0], [1, -1], field=generator_poly.field)
	parity_check_poly, remainder_poly = divmod(f, generator_poly)
	assert remainder_poly == 0
	self._parity_check_poly = parity_check_poly
	G = _poly_to_generator_matrix(n, generator_poly, systematic)
	H = _poly_to_parity_check_matrix(n, parity_check_poly, False)
	super().__init__(n, k, d, G, H, systematic)

Yes, the order of the columns in G and rows in H can be arbitrarily swapped.

[vprusso]

Thank you for the response, and I apologize for taking so long to respond.

Great, so extracting the relevant bits of code from the _CyclicCode class in the following way:

import galois
from galois import Poly
from galois._codes._cyclic import _poly_to_parity_check_matrix, _poly_to_generator_matrix


n, k, d = 7, 4, 3
generator_poly = galois.primitive_poly(2, d)

f = Poly.Degrees([n, 0], [1, -1], field=generator_poly.field)
parity_check_poly, remainder_poly = divmod(f, generator_poly)

G = _poly_to_generator_matrix(n, generator_poly, systematic=True)
H = _poly_to_parity_check_matrix(n, parity_check_poly, systematic=True)

yields a matrix H that looks like:

[[1 0 0 1 1 1 0]
 [0 1 0 0 1 1 1]
 [0 0 1 1 1 0 1]]

which appears to (modulo the column order) be equal to the "H" matrix for the (n=7,k=4,d=3) parity check matrix from the Wikipedia link

Taking this one step further to the Hamming [8,4] parity check matrix, running the above code with the altered values of

n, k, d = 8, 4, 3

yield this matrix

[[1 0 0 0 1 1 1 0]
 [0 1 0 0 0 1 1 1]
 [0 0 1 0 1 1 0 1]
 [0 0 0 1 1 0 0 0]]

which it seems is equivalent (up to row and column operations) to the matrix here in the section describing the Hamming [8,4] matrix given as

Probably all trivial questions, but the fact that the matrices are equivalent (modulo row and column operations) is expected and okay presumably, right?

My apologies if these are all super trivial. You can feel free to close this issue out as I think you answered my original question. Thank you again for all the help!

[mhostetter]

Probably all trivial questions, but the fact that the matrices are equivalent (modulo row and column operations) is expected and okay presumably, right?

I believe so, but I haven't implemented Hamming codes before.