A source coding scheme using sparse graphs: Modern Coding Theory Course Exam 2008

This is the report that submitted towards the final examination evaluation of the doctoral course \textit{Modern Coding theory} by Ruediger Urbanke at EPFL during Spring 2008. The problem studied can be roughly stated as source coding or compression using sparse graphs. We discuss a simple source coding problem and analyze its performance using an analytical tool formulated by \textit{Wormald}, usually employed to describe the expected behaviour of a suitably conditioned stochastic process on graph. A simulation investigation of the chosen scheme is also presented to verify the theoretical analysis.