Skip to main content
MathOverflow

Return to Question

added 97 characters in body
Source Link
itsabijection
itsabijection
  • 1
  • 1

A parity check matrix for a binary linear code is a matrix $H$ (with linearly independent rows) such that the (right) kernel of $H$ is the codespace. Clearly we can replace any row $r_i$ by $r_i + \sum_{j \in J} r_j$ if $i \not \in J$ to produce a matrix with the same kernel. It is a natural question to ask if there is some matrix $H'$ with the same kernel as $H$ such that all rows of $H'$ have weight at most $k$, where the weight of a row is just the number of nonzero entries in the row. Is there a way to produce such an $H'$ (or even to tell if one exists) without checking all matrices with the same nullspace?

Follow up: is there a way to solve the same problem given a parity check matrix over $GF(4)$?

A parity check matrix for a binary linear code is a matrix $H$ (with linearly independent rows) such that the (right) kernel of $H$ is the codespace. Clearly we can replace any row $r_i$ by $r_i + \sum_{j \in J} r_j$ if $i \not \in J$ to produce a matrix with the same kernel. It is a natural question to ask if there is some matrix $H'$ with the same kernel as $H$ such that all rows of $H'$ have weight at most $k$, where the weight of a row is just the number of nonzero entries in the row. Is there a way to produce such an $H'$ (or even to tell if one exists) without checking all matrices with the same nullspace?

A parity check matrix for a binary linear code is a matrix $H$ (with linearly independent rows) such that the (right) kernel of $H$ is the codespace. Clearly we can replace any row $r_i$ by $r_i + \sum_{j \in J} r_j$ if $i \not \in J$ to produce a matrix with the same kernel. It is a natural question to ask if there is some matrix $H'$ with the same kernel as $H$ such that all rows of $H'$ have weight at most $k$, where the weight of a row is just the number of nonzero entries in the row. Is there a way to produce such an $H'$ (or even to tell if one exists) without checking all matrices with the same nullspace?

Follow up: is there a way to solve the same problem given a parity check matrix over $GF(4)$?

edited title
Link
itsabijection
itsabijection
  • 1
  • 1

Given a binary parity check matrix, find a parity check matrix for the same code such that no row has weight greatgreater than $k$

Source Link
itsabijection
itsabijection
  • 1
  • 1

Given a binary parity check matrix, find a parity check matrix for the same code such that no row has weight great than $k$

A parity check matrix for a binary linear code is a matrix $H$ (with linearly independent rows) such that the (right) kernel of $H$ is the codespace. Clearly we can replace any row $r_i$ by $r_i + \sum_{j \in J} r_j$ if $i \not \in J$ to produce a matrix with the same kernel. It is a natural question to ask if there is some matrix $H'$ with the same kernel as $H$ such that all rows of $H'$ have weight at most $k$, where the weight of a row is just the number of nonzero entries in the row. Is there a way to produce such an $H'$ (or even to tell if one exists) without checking all matrices with the same nullspace?