  We consider the problem of carrier frequency offset (CFO) estimation for a
two-way relaying system based on the amplify-and-forward (AF) protocol. Our
contributions are in designing an optimal preamble, and the corresponding
estimator, to closely achieve the minimum Cramer-Rao bound (CRB) for the CFO.
This optimality is asserted with respect to the novel class of preambles,
referred to as the block-rotated preambles (BRPs). This class includes the
periodic preamble that is used widely in practice, yet it provides an
additional degree of design freedom via a block rotation angle. We first
identify the catastrophic scenario of an arbitrarily large CRB when a
conventional periodic preamble is used. We next resolve this problem by using a
BRP with a non-zero block rotation angle. This angle creates, in effect, an
artificial frequency offset that separates the desired relayed signal from the
self-interference that is introduced in the AF protocol. With appropriate
optimization, the CRB incurs only marginal loss from one-way relaying under
practical channel conditions. To facilitate implementation, a specific
low-complexity class of estimators is examined, and conditions for the
estimators to achieve the optimized CRB is established. Numerical results are
given which corroborate with theoretical findings.
