In compressed sensing, the search for the unique sparsest solution to an under-determined system of linear equations is the main challenge. The sensing matrix contains all coefficients of this linear system. Besides the common approach of random sensing matrices, deterministic constructions gain more and more interest. Among them, matrices with columns being circular shifts of other columns are particularly interesting because their structure allows to reduce the complexity in several reconstruction algorithms by applying the fast Fourier transform. For example, such matrices can be built from cyclic codes.

In this thesis, the construction of such matrices based on cyclic codes should be investigated and the resulting matrices should be compared to a circulant construction by DeVore. Because of the advantage in reconstruction, several recovery algorithms should be reviewed and their performance should be investigated. Additionally, the noise resilience of the discussed sensing matrices is also subject of examinations.