  We consider the problem of private information retrieval (PIR) over a
distributed storage system. The storage system consists of $N$ non-colluding
databases, each storing a coded version of $M$ messages. In the PIR problem,
the user wishes to retrieve one of the available messages without revealing the
message identity to any individual database. We derive the
information-theoretic capacity of this problem, which is defined as the maximum
number of bits of the desired message that can be privately retrieved per one
bit of downloaded information. We show that the PIR capacity in this case is
$C=\left(1+\frac{K}{N}+\frac{K^2}{N^2}+\cdots+\frac{K^{M-1}}{N^{M-1}}\right)^{-1}=(1+R_c+R_c^2+\cdots+R_c^{M-1})^{-1}=\frac{1-R_c}{1-R_c^M}$,
where $R_c$ is the rate of the $(N,K)$ code used. The capacity is a function of
the code rate and the number of messages only regardless of the explicit
structure of the storage code. The result implies a fundamental tradeoff
between the optimal retrieval cost and the storage cost. The result generalizes
the achievability and converse results for the classical PIR with replicating
databases to the case of coded databases.
