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$.