--------------------------------------------------------------------
Ram Zamir <zamir@eng.tau.ac.il>

 Nested Codes for Information Embedding, Distributed Compression and
 Interference Cancellation:
--------------------------------------------------------------------

 Exploiting the correlation between signals in a communication system
is often a key for increasing its performance.  Common examples are motion
compensation in video compression (spatial/temporal correlation), and
echo or crosstalk cancellation in duplex or multiline transmission.
Here, the correlated signals (previous frames in video
compression, echo in duplex transmission) are available at both the
encoder and the decoder ends of the system.  In some
applications, however, the correlated signal is available only at one
end of the communication link.  This makes exploiting signal correlation
a non trivial task.  An interesting and current example for this
situation is "digital water-marking" or information-embedding,
used mostly for copyright protection of digital audio and video
in a public data network.  Suppose, say, we want to "hide" digital
information (a "water-mark") in a digital sound track, such that
on one hand it would not significantly distort the audio signal,
yet on the other hand it would be hard to maliciously alter it
without making a noticeable change in the audio signal.
An important feature of a water-mark code is that it should be
possible to read it without having access to the original (un-marked)
signal.  Now, if the correlated signal (the original sound track)
was available to the decoder, then the information-embedding process
was very simple:  superposition by the encoder and subtraction
by the decoder.  However, the lack of it at the decoder side
means that the encoder needs to be "smart enough" to allow
"blind detection" by the decoder.

 Somewhat surprisingly, partial knowledge of correlated signals, as
in the example above, is a good model for different important
setups in data communication.  All these setups belong to a class
known as "side information problems" in information theory.  For
example, the same model fits also the problem of interference (or
crosstalk) cancellation in multi-user down-link transmission
(known also as the "vector broadcast channel").  Reversing this model,
we get a source coding problem of compression with side-information
at the decoder.  This is, for example, the case of video compression
when the encoder, say, due to complexity constraints, cannot
perform motion compensation and must encode each frame independently.
The decoder thus must be "smart enough" to exploit the
spatial correlation from previous frames, given these independent
encodings.

 The main theoretical tool for solving side-information problems is
the "random binning scheme".  NESTED LINEAR/LATTICE CODES provide
a practical implementation for this scheme.  In a nested code, the
"bins" take the form of "relative cosets".  This structure allows
to apply encoding and decoding techniques from the rich areas of
algebraic codes and lattices, hence they are very appealing
for practical applications.  Recent work we have done in Tel Aviv
University shows that indeed there exist efficient schemes for
coding and decoding with side-information based on nested codes.
In an on going research, we are working to modify these schemes for
some of the specific applications discussed above.

----------------------------------------------------------------------