In a variety of applications, there is a need to authenticate content that has experienced legitimate editing in addition to potential tampering attacks. We develop one formulation of this problem based on a strict notion of security, and characterize and interpret the associated information-theoretic performance limits. The results can be viewed as a natural generalization of classical approaches to traditional authentication. Additional insights into the structure of such systems and their behavior are obtained by further specializing the results to Bernoulli and Gaussian cases. The associated systems are shown to be substantially better in terms of performance and/or security than commonly advocated approaches based on data hiding and digital watermarking. Finally, the formulation is extended to obtain efficient layered authentication system constructions.

Aspects of the duality between the information-embedding problem and the Wyner-Ziv (1976) problem of source coding with side information at the decoder are developed and used to establish a spectrum new results on these and related problems, with implications for a number of important applications. The single-letter characterization of the information-embedding problem is developed and related to the corresponding characterization of the Wyner-Ziv problem, both of which correspond to optimization of a common mutual information difference. Dual variables and dual Markov conditions are identified, along with the dual role of noise and distortion in the two problems. For a Gaussian context with quadratic distortion metric, a geometric interpretation of the duality is developed. From such insights, we develop a capacity-achieving information-embedding system based on nested lattices. We show the resulting encoder-decoder has precisely the same decoder-encoder structure as the corresponding Wyner-Ziv system based on nested lattices that achieves the rate-distortion limit. For a binary context with Hamming distortion metric, the information-embedding capacity is developed, along with its relationship to the corresponding Wyner-Ziv rate-distortion function. In turn, an information-embedding system for this case based on nested linear codes is constructed having an encoder-decoder that is identical to the decoder-encoder structure for the corresponding system that achieves the Wyner-Ziv rate-distortion limit. Finally, based on these results, a simple layered joint source-channel coding system is developed with a perfectly symmetric encoder-decoder structure. Its application and performance is discussed in a broadcast setting in which there is a need to control the fidelity experienced by different receivers. Among other results, we show that such systems and their multilayer extensions retain attractive optimality properties in the Gaussian-quadratic case, but not in the binary-Hamming case.

The conventional list Viterbi algorithm (LVA) produces a list of the L best output sequences over a certain block length in decoding a terminated convolutional code. We show in this paper that the LVA with a sufficiently long list is an optimum maximum-likelihood decoder for the concatenated pair of a convolutional code and a cyclic redundancy check (CRC) block code with error detection. The CRC is used to select the output. New LVAs for continuous transmission are proposed and evaluated, where no termination bits are required for the convolutional code for every CRC block. We also present optimum and suboptimum LVAs for tailbiting convolutional codes. Convolutional codes with Viterbi decoding were proposed for so-called hybrid in band on channel (hybrid IBOC) systems for digital audio broadcasting compatible with the frequency modulation band. For high-quality audio signals, it is beneficial to use error concealment/error mitigation techniques to avoid the worst type of channel errors. This requires a reliable error flag mechanism (error detection feature) in the channel decoder. A CRC on a block of audio information bits provides this mechanism. We demonstrate how the LVA can significantly reduce the flag rate compared to the regular Viterbi algorithm (VA) for the same transmission parameters. At the expense of complexity, a receiver optional LVA can reduce the flag rate by more than an order of magnitude. The difference in audio quality is dramatic. The LVA is backward compatible with a VA.

We consider the problem of embedding one signal (e.g., a digital watermark), within another "host" signal to form a third, "composite" signal. The embedding is designed to achieve efficient tradeoffs among the three conflicting goals of maximizing the information-embedding rate, minimizing the distortion between the host signal and composite signal, and maximizing the robustness of the embedding. We introduce new classes of embedding methods, termed quantization index modulation (QIM) and distortion-compensated QIM (DC-QIM), and develop convenient realizations in the form of what we refer to as dither modulation. Using deterministic models to evaluate digital watermarking methods, we show that QIM is "provably good" against arbitrary bounded and fully informed attacks, which arise in several copyright applications, and in particular it achieves provably better rate distortion-robustness tradeoffs than currently popular spread-spectrum and low-bit(s) modulation methods. Furthermore, we show that for some important classes of probabilistic models, DC-QIM is optimal (capacity-achieving) and regular QIM is near-optimal. These include both additive white Gaussian noise (AWGN) channels, which may be good models for hybrid transmission applications such as digital audio broadcasting, and mean-square-error-constrained attack channels that model private-key watermarking applications.

A low-complexity method of linearly combining an analog frequency-modulation (FM) signal with a low-level multitone signal for simultaneous broadcasting of digital data and analog FM is proposed and evaluated. The analog FM signal can be recovered with a standard FM receiver. The digital multitone signal is added symmetrically at the band edges of the 200-kHz FM signal in contiguous bands with variable width. To maximize the data rate, the digital bandwidth is maximized subject to a maximum allowed distortion of the demodulated analog FM signal. The impact of the analog FM signal on, digital reception is cancelled by means of transmitter precanceling techniques. Conditions for precanceling techniques for multipath channels are formulated. The main advantage of the contiguous band insertion method is that the rate of the control channel is considerably lower compared to previously proposed methods of carrier insertion without significant reduction in data rate. We present a number of numerical results for acoustical signals.

Hybrid in-band on-channel (IBOC) broadcasting systems for digital audio radio have the capability of simultaneously transmitting analog FM and digital audio of CD-like quality. Due to fading and interference in the already-crowded FM band, the signal design for the hybrid IBOC system is very challenging. It has been proposed to use a method of double sideband transmission where the digital information is transmitted by means of orthogonal frequency-division multiplexing (OFDM) on both sides of the analog host FM and where the digital information can be recovered when one sideband is partially or even totally lost. This leads to an interesting channel coding problem, where we search for optimal pairs of high-rate codes that form good combined low-rate codes, which are better than classic code combining techniques. Furthermore, we also search for rate-compatible punctured convolutional codes which can be used for two-level unequal error protection (UEP) of digital audio. Since some of the tones in the multitone modem (OFDM) are more exposed to interference than others, optimal assignments of convolutional code bits to tones depending on their spectral position are also found. A large number of new codes with memory 6 and 8 are presented both for equal error protection and UEP.

A variety of emerging applications require the design of systems for embedding one signal within another signal. We describe a new class of embedding methods called quantization index modulation (QIM) and develop a realization termed coded dither modulation in which the embedded information modulates the dither signal of a dithered quantizer. We also develop a framework in which one can analyze the performance trade-offs among robustness, distortion, and embedding rate, and we show that QIM systems have considerable performance advantages over previously proposed spread-spectrum and low-bit modulation systems.

Simultaneous broadcasting of digital data and existing analog FM is investigated. A suboptimum method of linearly combining the analog FM signal with a low level multitone signal is proposed and evaluated. The analog FM signal is to be recovered with a standard FM receiver. The digital multitone signal is added symmetrically at the band edges of the 200 kHz FM signal in contiguous bands with variable width. To maximize the data rate, the digital bandwidth is maximized subject to a maximum allowed distortion of the analog FM signal. The impact of the analog FM signal on digital reception is cancelled by means of transmitter precancelling techniques. Conditions for precancelling techniques for multipath channels are formulated. The main advantage of the contiguous band insertion (CBI) method is that the rate of the control channel is considerably lower compared to previous near optimum methods of carrier insertion without significant reduction in data rate. We present a number of numerical results for acoustical signals.

A variety of related applications have emerged that require the design of systems for embedding one signal within another signal. We propose a new class of embedding methods called quantization index modulation (QIM) and develop an example of such a method called dither modulation in which the embedded information modulates the dither signal of a dithered quantizer. We also develop a framework within which one can analyze performance trade-offs among robustness, distortion, and embedding rate, and we show that QIM systems have considerable performance advantages over previously proposed spread-spectrum and low-bit modulation systems.

The properties of chaotic dynamical systems make them useful for channel coding in a variety of practical communication applications. To illustrate this, a novel analog code based on tent map dynamics and having a fast decoding algorithm is developed for use on unknown, multiple, and time-varying signal-to-noise ratio (SNR) channels. This code is shown to be an attractive alternative to both digital codes and linear modulation in such scenarios. Several properties and interpretations of the codes are developed, along with some methods for their optimization.