We study a variant of the classical circuit-lower-bound problems: proving lower bounds for sampling distributions given random bits. We prove a lower bound of 1-1/n^{\Omega(1)} on the statistical distance between (i) the output distribution of any small constant-depth (a.k.a.~\mathrm{AC}^0) circuit f : \{0,1\}^{\mathrm{poly}(n)} \to \{0,1\}^n, and (ii) the uniform distribution over any code \mathcal{C} \subseteq \{0,1\}^n that is ``good'', i.e.~has relative distance and rate both \Omega(1). This seems to be the first lower bound of this kind.

We give two simple applications of this result: (1) any data structure for storing codewords of a good code \mathcal{C} \subseteq \{0,1\}^n requires redundancy \Omega(\log n), if each bit of the codeword can be retrieved by a small \mathrm{AC}^0 circuit; (2) for some choice of the underlying combinatorial designs, the output distribution of Nisan's pseudorandom generator against \mathrm{AC}^0 circuits of depth d cannot be sampled by small \mathrm{AC}^0 circuits of depth less than d.