bitflipDecode -- an experimental implementation of a message passing decoder

Synopsis

Usage:

bitflipDecoder(H,v,maxI)
Inputs:
- H, a matrix,
- v, a vector,
- maxI, an integer,
Outputs:
- a list,

Description

Attempts to decode the vector v relative to the parity check matrix H using a message passing decoding algorithm. The matrix H and the vector v must have entries in GF(2). Returns the empty list if maxI is exceeded.

At each iteration, this function flips all the bits of v that fail the maximum number of parity check equations from H. This is experimental because it has not been fully tested. The output is only guaranteed to be a codeword of the code defined by H.

i1 : R=GF(2);

i2 : H := matrix(R, {{1,1,0,0,0,0,0},{0,1,1,0,0,0,0},{0,1,1,1,1,0,0},{0,0,0,1,1,0,0},{0,0,0,0,1,1,0},{0,0,0,0,1,0,1}});

             6      7
o2 : Matrix R  <-- R

i3 : v := vector transpose matrix(R, {{1,0,0,1,0,1,1}});

      7
o3 : R

i4 : bitflipDecode(H,v,100)

o4 = {0, 0, 0, 1, 1, 1, 1}

o4 : List

Ways to use bitflipDecode :

bitflipDecode(Matrix,Vector,ZZ)

For the programmer

The object bitflipDecode is a method function.