Multiple description source coding

In many applications, such as real-time image and video, we need to be able to handle packet losses without re-transmitting the lost packets. To do this we need to build in redundancy within the transmission schemes for robustness to such losses. A multiple description source coder (MDC) generates a set of binary streams or descriptions of a source sequence, each with its own rate constraint. The transmission medium may deliver some or all of the descriptions to the decoder. The design objective is to minimize the distortion if all the descriptions are received, subject to the constraint that a minimum fidelity is guaranteed if only some of the descriptions are delivered. An important application of such a coding scheme is source transmission through networks which do not support a priority structure, the best example being the Internet. On such networks, there is no special class of packets for which strong quality of service (QoS) guarantees are made. Another transmission scheme which is important in practice is successively refinable coders where packets are delivered with a strict priority structure.

Most of the work has centered around the successively refinable and balanced cases, which are in a sense two extreme cases of the distortion profile. We proposed a technique that bridges the two schemes, in the sense that it allows for an arbitrary distortion profile. By making the descriptions have different distortions, one can show that the quantizer behavior can range from balanced (where each description is equally important) to a strict hierarchy (where the loss of some descriptions could make the decoding impossible). The design is proposed for a lattice vector quantizer, but the general principle of asymmetric multiple description coding can be extended to a host of other quantizers. This could include trellis coded quantizers, unstructured vector quantizers etc. This could potentially allow us to incorporate channel (or network route) reliability information into the transmission.

We also explored several basic questions about the existence of lattices with desired properties for the multiple description lattice quantizer. The high rate asymptotic analysis reveals the trade-offs in the quantizer design. It also shows that the exponential decay rates of the distortion with the source transmission rates match those predicted by rate-distortion theory, showing that this design is asymptotically efficient. This source coding design is suitable for situations where there is heterogeneous loss probabilities in the network.

We have also made contributions to the fundamental limits of multiple description coded systems by proving the performance limits for Gaussian stationary and ergodic sources with quadratic distortion measure. We give a single letter characterization for the two-description coding for stationary and ergodic sources with quadratic distortion measures. This formalizes the requirements of transform-based multiple-description source codes.

In an abstract framework, we can think of the video as a sequence of correlated random variables which we are trying to describe efficiently. In (Witsenhausen and Wyner, 1980; Puri and Ramchandran, 2003) an alternate approach was taken by considering the video coding problem as a source coding problem with side-information. In this setting, after encoding and transmitting the “previous frame, the “current frame develops an encoder which does not explicitly depend on the knowledge of the previous frame. The basic idea of this scheme arises from encoding schemes and decoding described in (Slepian and Wolf, 1974; Wyner and Ziv 1976). Since the encoder does not explicitly use the side-information (previous frame) it can be designed such that the computational complexity is shifted from the encoder to the decoder. Such an architecture is attractive for applications where the encoder needs to be simple but the decoder can be more complex. However, even with this idea the robustness to route failures which is inherent to MD coding is not captured.

Motivated by this, we formulated a multi-terminal source coding problem, where we are required to construct a multiple-description code for a source sequence when side information about dependent random processes is available at the decoder only, or at both the decoder and the encoder. We described an achievable rate-distortion region for these problems in two cases: where there is common side-information at the decoders and when they are different. In the quadratic Gaussian case, and when there is common side information among the decoders, we showed that the rate region when both the encoder and decoder have access to the side information coincides with that of decoder–only side information. This is analogous to the single-description (Wyner-Ziv) case, and an explicit characterization of the rate-distortion region was provided for this case.

We have started an investigation into how to allocate resources in a network with competing multiple-description flows. This could have applications to real-time delivery of multimedia applications over a shared best-effort network. We have posed this question in terms of a network utility maximization framework and developed decentralized resource allocation algorithms. We utilized the flexibility of the constructions to develop these decentralized algorithms for path diversity. With competing flows, one would expect that the induced uncertainty would cause the overall network utility to be maximized by a conservative strategy by each flow. One surprising finding from this was that if all flows used opportunistic strategies that aggressively utilize resources, these outperform conservative schemes even under competition.