The rational covariance extension problem to determine a rational spectral density given a finite number of covariance lags can be seen as a matrix completion problem to construct an infinite-dimensional positive-definite Toeplitz matrix the northwest corner of which is given. The circulant rational covariance extension problem considered in this paper is a modification of this problem to partial stochastic realization of periodic stationary process, which are better represented on the discrete unit circle Z(2N) rather than on the discrete real line Z. The corresponding matrix completion problem then amounts to completing a finite-dimensional Toeplitz matrix that is circulant. Another important motivation for this problem is that it provides a natural approximation, involving only computations based on the fast Fourier transform, for the ordinary rational covariance extension problem, potentially leading to an efficient numerical procedure for the latter. The circulant rational covariance extension problem is an inverse problem with infinitely many solutions in general, each corresponding to a bilateral ARMA representation of the underlying periodic process. In this paper, we present a complete smooth parameterization of all solutions and convex optimization procedures for determining them. A procedure to determine which solution that best matches additional data in the form of logarithmic moments is also presented.