This paper investigates the performance of frames for the linear, redundant encoding of vectors when consecutive frame coefficients are lost due to the occurrence of random burst errors. We assume that the distribution of bursts is invariant under cyclic shifts and that the burst-length statistics are known. In analogy with rate-distortion theory, we wish to find frames of a given size, which minimize the mean-square reconstruction error for the encoding of vectors in a complex finite-dimensional Hilbert space. We obtain an upper bound for the mean-square reconstruction error for a given Parseval frame and in the case of cyclic Parseval frames, we find a family of frames which minimizes this upper bound. Under certain conditions, these minimizers are identical to complex Bose–Chaudhuri–Hocquenghem codes discussed in the literature. The accuracy of our upper bounds for the mean-square error is substantiated by complementary lower bounds. All estimates are based on convexity arguments and a discrete rearrangement inequality.