Video compression is achieved by exploiting spatial and temporal correlations in the frame sequence. A frame is typically predicted by the encoder from previously coded information (such as blocks and/or frames), and the residual between the frame and its prediction is entropy coded. As the quality of the prediction has a major impact on compression performance, searching for the best predictor imposes a heavy computational burden on the encoder. As a result, complexity is out of balance with an encoder that is significantly more complex than the decoder. A new way of performing video coding has been introduced in the last decade. This new paradigm, called distributed video coding (DVC), shifts the complexity from the encoder to the decoder. This shift is realized by making the decoder responsible for generating the prediction signal, hereby relieving the encoder from this complex task. However, while the encoder could select the best predictor based on a comparison with the original to be coded, the decoder cannot perform this comparison as it only has previously decoded information at its disposal. This makes that the task of the decoder to find good predictions is more challenging. Due to this complexity shift, DVC facilitates a different range of applications featuring cheap, small and/or power-friendly encoding devices. Some example applications include wireless sensor networks, wireless video surveillance, and video conferencing using mobile devices (Pereira et al., 2008). Despite current research in DVC, compression performance is still low compared to conventional solutions such as H.264/AVC. Therefore, in this chapter, we will focus on one of the challenges in DVC with a strong impact on compression performance, namely: estimating the correlation noise.