PUZZLE #2657: LDPC Decoding (diff 2)

ldpc learn difficulty: 2/7 compute author: system unsolved audits passed

A 10-block LDPC-coded message (10,5) sparse code. 20 bits flipped by noise. Use iterative bit-flipping on the Tanner graph to recover the data.

DATA

Encoded	`0100000101011111110000011110001010000011001000100010110111110101001110000101011001111011011111010000`
H	`[1, 1, 0, 1, 0, 1, 0, 0, 0, 0], [0, 1, 1, 0, 1, 0, 1, 0, 0, 0], [0, 0, 1, 1, 0, 1, 0, 1, 0, 0], [0, 0, 0, 0, 1, 0, 1, 1, 1, 0], [1, 0, 0, 0, 0, 0, 0, 1, 0, 1]`
N Variable	`10`
N Check	`5`
Data Bits	`5`
N Blocks	`10`
Adj List	`[0, 4], [0, 1], [1, 2], [0, 2], [1, 3], [0, 2], [1, 3], [2, 3, 4], [3], [4]`
Check Adj	`[0, 1, 3, 5], [1, 2, 4, 6], [2, 3, 5, 7], [4, 6, 7, 8], [0, 7, 9]`
Errors	`20`
Hint	`Run bit-flipping: initialize with noisy codeword. For each check node, compute if its parity equation is satisfied. For each variable node, count connected check nodes that are violated. Flip any variable bit where > half its checks are violated. Repeat until all checks pass or 50 iterationsFirst 5 bits of each block are the data bits.`
Answer Format	`lowercase letters, no spaces or punctuation`

{
  "type": "ldpc",
  "encoded": "0100000101011111110000011110001010000011001000100010110111110101001110000101011001111011011111010000",
  "H": [
    [
      1,
      1,
      0,
      1,
      0,
      1,
      0,
      0,
      0,
      0
    ],
    [
      0,
      1,
      1,
      0,
      1,
      0,
      1,
      0,
      0,
      0
    ],
    [
      0,
      0,
      1,
      1,
      0,
      1,
      0,
      1,
      0,
      0
    ],
    [
      0,
      0,
      0,
      0,
      1,
      0,
      1,
      1,
      1,
      0
    ],
    [
      1,
      0,
      0,
      0,
      0,
      0,
      0,
      1,
      0,
      1
    ]
  ],
  "n_variable": 10,
  "n_check": 5,
  "data_bits": 5,
  "n_blocks": 10,
  "adj_list": [
    [
      0,
      4
    ],
    [
      0,
      1
    ],
    [
      1,
      2
    ],
    [
      0,
      2
    ],
    [
      1,
      3
    ],
    [
      0,
      2
    ],
    [
      1,
      3
    ],
    [
      2,
      3,
      4
    ],
    [
      3
    ],
    [
      4
    ]
  ],
  "check_adj": [
    [
      0,
      1,
      3,
      5
    ],
    [
      1,
      2,
      4,
      6
    ],
    [
      2,
      3,
      5,
      7
    ],
    [
      4,
      6,
      7,
      8
    ],
    [
      0,
      7,
      9
    ]
  ],
  "errors": 20,
  "hint": "Run bit-flipping: initialize with noisy codeword. For each check node, compute if its parity equation is satisfied. For each variable node, count connected check nodes that are violated. Flip any variable bit where > half its checks are violated. Repeat until all checks pass or 50 iterationsFirst 5 bits of each block are the data bits.",
  "answer_format": "lowercase letters, no spaces or punctuation"
}

author's note: Audited: ldpc diff 2