  This paper considers the problem of compressive sensing over a finite
alphabet, where the finite alphabet may be inherent to the nature of the data
or a result of quantization. There are multiple examples of finite alphabet
based static as well as time-series data with inherent sparse structure; and
quantizing real values is an essential step while handling real data in
practice. We show that there are significant benefits to analyzing the problem
while incorporating its finite alphabet nature, versus ignoring it and
employing a conventional real alphabet based toolbox. Specifically, when the
alphabet is finite, our techniques (a) have a lower sample complexity compared
to real-valued compressive sensing for sparsity levels below a threshold; (b)
facilitate constructive designs of sensing matrices based on coding-theoretic
techniques; (c) enable one to solve the exact $\ell_0$-minimization problem in
polynomial time rather than a approach of convex relaxation followed by
sufficient conditions for when the relaxation matches the original problem; and
finally, (d) allow for smaller amount of data storage (in bits).
