Ottawa–Carleton
Discrete Mathematics Group

28 November 2008, 11.30am
FTX 137, U. Ottawa

The set of solutions of a linear homogenous congruence system over Z_g forms a lattice. Therefore, finding a solution for this system is equivalent to finding the corresponding lattice point. Min-sum algorithm is a well known iterative decoding algorithm for decoding binary codes. It works on the Tanner graph of a code, a bipartite graph based on the dual (parity checks) of the code. Min-sum algorithm is generalized to decode group codes and lattices. So to solve such system, we define a Tanner graph for the system and work along the nodes and the edges of this bipartite graph. We explain the detail of this algorithm and comments on further research.