tannerGraph -- outputs the tanner graph associated with the given parity check matrix

Synopsis

Usage:

tannerGraph(H)
Inputs:
- H, a matrix,
Outputs:
- a graph,

Description

Given a linear code $C$ with parity-check matrix H, the function returns the Tanner graph associated to H. This is a bipartite graph with one set of vertices indexed by the rows of H and the other by the columns of H. The vertex corresponding to the $i$-th row is connected to the vertex corresponding to the $j$-th column if and only if the $(i,j)$-th entry of H is nonzero.

i1 : H := matrix(GF(2), {{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
o1 : Matrix (GF 2)  <-- (GF 2)

i2 : tannerGraph(H)

o2 = Graph{c  => {r }            }
            0      0
           c  => {r , r , r }
            1      0   1   2
           c  => {r , r }
            2      1   2
           c  => {r , r }
            3      2   3
           c  => {r , r , r , r }
            4      2   3   4   5
           c  => {r }
            5      4
           c  => {r }
            6      5
           r  => {c , c }
            0      0   1
           r  => {c , c }
            1      1   2
           r  => {c , c , c , c }
            2      1   2   3   4
           r  => {c , c }
            3      3   4
           r  => {c , c }
            4      4   5
           r  => {c , c }
            5      4   6

o2 : Graph

Ways to use tannerGraph :

tannerGraph(Matrix)

For the programmer

The object tannerGraph is a method function.