We consider the problem of estimating a discrete signal $X^n =
(X_1, \ldots, X_n)$ based on its noise-corrupted observation
signal $Z^n = (Z_1, \ldots, Z_n)$. The noise-free, noisy, and
reconstruction signals are all assumed to have components taking
values in the same finite $M$-ary alphabet $\{0, \ldots, M-1 \}$.
For concreteness we focus on the additive noise channel $Z_i =
X_i + N_i$, where addition is modulo-$M$, and $\{N_i\}$ is the
noise process. The cumulative loss is measured by a given loss
function. The distribution of the noise is assumed known, and may
have memory restricted only to stationarity and a mild mixing
condition. We develop a sequence of denoisers (indexed by the
block length $n$) which we show to be asymptotically universal in
both a semi-stochastic setting (where the noiseless signal is an
individual sequence) and in a fully stochastic setting (where the
noiseless signal is emitted from a stationary source). It is
detailed how the problem formulation, denoising schemes, and
performance guarantees carry over to non-additive channels,
as well as to higher-dimensional data
arrays. The proposed schemes are shown to be computationally
implementable. We also discuss a variation on these schemes that
is likely to do well on data of moderate size. We conclude with
a report of experimental results for the binary burst noise
channel, where the noise is a finite-state hidden Markov process
(FS-HMP), and a finite-state hidden Markov random field (FS-HMRF),
in the respective cases of one- and two-dimensional data. These
support the theoretical predictions and show that, in practice,
there is much to be gained by taking the channel memory into
account.