My project revolves around the constructions and performance of binary codes from bipartite graphs.
I am working with Alexander Barg.

The purpose of this project is to construct and establish performance of several specific examples of
expander codes. First, constructions of expander codes will need to be studied and implemented. Secondly,
the error probability of several codes from the family described needs to be simulated and compared
with another popular code family, the so-called low-density parity-check codes decoded by a message-passing
iterative algorithm, for which the error probability of decoding  is known and appears in the literature.

• "A recursive approach to low complexity codes," R.Tanner,  IEEE Transactions on Information Theory, Volume: 27 Issue: 5,

Sep 1981
• "Expander codes," M. Sipser, D.A. Spielman,   IEEE Transactions on Information Theory, Volume: 42 Issue: 6 , Nov. 1996

 See also the earlier conference proceedings: "Expander codes," M. Sipser, D.A. Spielman, Proceedings of the 35th Annual
 Symposium on the Foundations of Computer Science (FOCS 94), Nov. 1994
• "On expander codes," G. Zemor, IEEE Transactions on Information Theory , Volume: 47 Issue: 2 , Feb 2001
• "Error exponents of expander codes," A. Barg,  G. Zemor, IEEE Transactions on Information Theory , Volume: 48 Issue: 6 ,

 June 2002
• A series of papers by Piotr Indyk and Venkatesan Guruswami:"Linear time encodable and list decodable codes," Proceedings

of the 35th Symposium on Theory of Computing, 2003; "Near-optimal Linear-Time Codes for Unique Decoding and New
List-Decodable Codes Over Smaller Alphabets,"  Proceedings of the 34th Symposium on Theory of Computing, 2002;
"Expander-based Constructions of Efficiently Decodable Codes," Proceedings of the 42nd Symposium on Foundations
of Computer Science, 2001.

• Gallager's original monograph, "Low Density Parity Check Codes," M.I.T. Press, 1963, can be downloaded [here].
• "Good error-correcting codes based on very sparse matrices," MacKay, D.J.C.; IEEE Transactions on Information Theory,

Volume: 45 Issue: 2 , March 1999 .
• Currently the best practical results: "On the design of low-density parity-check codes within 0.0045 dB of the

Shannon limit," Sae-Young Chung; G.D. Forney,., Jr.; T.J. Richardson,  R. Urbanke, IEEE Communications Letters,
Volume: 5 Issue: 2 , Feb 2001
• "Efficient encoding of low-density parity-check codes," T.J. Richardson, R. Urbanke, IEEE Transactoins on Information Theory,

Volume: 47 Issue: 2 , Feb 2001
"Design of capacity-approaching irregular low-density parity-check codes," T.J. Richardson,  M.A Shokrollahi, R. Urbanke,
IEEE Transactions on Information Theory, Volume: 47 Issue: 2 , Feb 2001
• "The capacity of low-density parity-check codes under message-passing decoding,"  T.J. Richardson, R. Urbanke, IEEE

Transactions on Information Theory, Volume: 47 Issue: 2 , Feb 2001
• "Improved low-density parity-check codes using irregular graphs," M.G. Luby, M. Mitzenmacher, M.A Shokrollahi,

D.A. Spielman, IEEE Transactions on Information Theory, Volume: 47 Issue: 2 , Feb 2001
• Original turbo coding paper: "Near Shannon limit error-correcting coding and decoding: Turbo-codes," C. Berrou,

A. Glavieux,  P. Thitimajshima,  IEEE International Conference on Communications (ICC 93), Volume: 2 , 23-26 May 1993
• "Turbo decoding as an instance of Pearl's “belief propagation” algorithm," R.J. McEliece, MacKay, D.J.C.; Jung-Fu Cheng,

IEEE Journal on Selected Areas in Communications, Volume: 16 Issue: 2 , Feb. 1998


---

Code I have written:

• quaternion.cpp -- a file containing methods allowing computations with quaternions
• mtwo.cpp -- a file containing methods allowing computations with PSL2(q)
• graph_holder.cpp -- a file containing methods for storage and decoding algorithms for random bipartite graphs
• partitioned_graph.cpp -- a file containing methods for storage and decoding algorithms for random partitioned bipartite graphs.
• decomposition.cpp -- a file for dealing with decompositions of prime numbers into sums of four squares
• edge_graph.cpp -- a file for creating vertex-edge graphs.
• auxi.cpp -- a file containing some auxiliary functions for decoding an encoding
• alpha_exp.cpp -- a file containing some decode for operations in finite fields
• bch.cpp -- a file containing some algorithms for exhaustive search decoding of some BCH codes
• hamm.cpp -- a file containing some algorithms for exhaustive search decoding of Hamming codes
• rm15.cpp, rm36.cpp , rm.cpp -- files containing some algorithms for decoding of some Reed-Muller codes
• dcd.cpp -- some auxiliary decoding functions
• factor.cpp -- some algorithms for factoring
• bch3121synd.txt, bch3126synd.txt, rm36.txt, trn_mtr.txt -- syndrome tables necessary for some of the above codes to work