Timeline for Given a binary parity check matrix, find a parity check matrix for the same code such that no row has weight greater than $k$
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 19, 2022 at 21:00 | comment | added | unknown | @RobPratt I'm interested to see how integer linear programming can be applied here. I think the problem can re-stated as finding linear combinations of the rows of $H$ with the least maximum weight...you'd have to add that the rows are independent which will complicate things...I can ask a post a separate question is this is different from OP's | |
| Jul 19, 2022 at 18:49 | comment | added | Kevin | @itsabijection Yes, I deleted my comment after realizing it's not obvious how that helps you. Perhaps the hardness proof for finding a min weight codeword can be adapted to your situation. | |
| Jul 19, 2022 at 17:54 | comment | added | RobPratt | Sounds like a job for integer linear programming. Do you have example data? | |
| Jul 19, 2022 at 17:40 | comment | added | itsabijection | Thank you for your comment @Kevin. To see if I understand - if we could solve my problem then we would know if there at at least $r$ (number of rows of $H$ independent vectors in the dual codespace of weight at most $k$. To find the minimum weight codeword we could try all $k$ from $0$ to the number of columns of $H$. If we ever get a YES answer (that $H'$ exists) then we would know the minimum distance of the dual code is at most $k$. However, if we get a NO answer, doesn't this just say that there are at most $r - 1$ codewords of weight $k$? Does this let us find the minimum weight codeword? | |
| Jul 19, 2022 at 16:20 | history | edited | itsabijection | CC BY-SA 4.0 |
added 97 characters in body
|
| Jul 19, 2022 at 16:19 | history | edited | itsabijection | CC BY-SA 4.0 |
edited title
|
| S Jul 19, 2022 at 16:18 | review | First questions | |||
| Jul 19, 2022 at 17:49 | |||||
| S Jul 19, 2022 at 16:18 | history | asked | itsabijection | CC BY-SA 4.0 |