  We introduce the new concept of computation coding. Similar to how
rate-distortion theory is concerned with the lossy compression of data,
computation coding deals with the lossy computation of functions.
  Particularizing to linear functions, we present an algorithm to reduce the
computational cost of multiplying an arbitrary given matrix with an unknown
column vector. The algorithm decomposes the given matrix into the product of
codebook wiring matrices whose entries are either zero or signed integer powers
of two.
  For a typical implementation of deep neural networks, the proposed algorithm
reduces the number of required addition units several times. To achieve the
accuracy of 16-bit signed integer arithmetic for 4k-vectors, no multipliers and
only 1.5 adders per matrix entry are needed.
