This paper studies the state estimation problem for a stochastic discrete-time system over a lossy channel where the packet loss is modeled as an independent and identically distributed binary process. To counter the effect of random packet loss, we propose a linear coding method to preprocess the measured output, and prove that the coded output is information preserving when packet loss is void and is information enhancing when packet loss is present. An optimal state estimator under the minimum mean square error (MMSE) criterion is derived for the coded output when subject to packet loss. The maximum packet loss rate for ensuring a stable estimator is then derived and shown to be very close to a well-known lower bound. Also considered is a compressed linear coding method where the measured output is first compressed onto a lower dimensional space before encoding, and it is shown that the similar packet rate condition for stability holds. Crown Copyright (C) 2014 Published by Elsevier Ltd. All rights reserved.