The nearest lattice point problem in$\mathbb {R}^{n}$is formulated in a distributed network with$n$nodes. The objective is to minimize the probability that an incorrect lattice point is found, subject to a constraint on inter-node communication. Algorithms with a single as well as an unbounded number of rounds of communication are considered for the case$n=2$. For the algorithm with a single round, expressions are derived for the error probability as a function of the total number of communicated bits. We observe that the error exponent depends on the lattice structure and that zero error requires an infinite number of communicated bits. In contrast, with an infinite number of allowed communication rounds, the nearest lattice point can be determined without error with a finite average number of communicated bits and a finite average number of rounds of communication. In two dimensions, the hexagonal lattice, which is most efficient for communication and compression, is found to be the most expensive in terms of communication cost.

We consider the problem of communicating over a relay-assisted multiple-input multiple-output (MIMO) channel with additive noise, in which physically separated relays forward quantized information to a central decoder where the transmitted message is to be decoded. We assume that channel state information is available in the transmitter and show that the design of a rational-forcing precoder - a precoder which is matched to the quantizers used in the relays - is beneficial for reducing the symbol error probability. It turns out that for such rational-forcing precoder based systems, there is natural tradeoff between the peak to average power ratio in the transmitter and the rate of communication between the relays and the central decoder. The precoder design problem is formulated mathematically, and several algorithms are developed for realizing this tradeoff. Optimality of the decoder communication rate is shown based on a result in distributed function computation. Numerical and simulation results show that a useful tradeoff can be obtained between the excess decoder communication rate and the peak-average power ratio in the transmitter.

We present a communication-efficient distributed protocol for computing the Babai point, an approximate nearest point for a random vector${\mathbf{X}}\in \mathbb {R}^{n}$in a given lattice. We show that the protocol is optimal in the sense that it minimizes the sum rate when the components of$\boldsymbol {X}$are mutually independent. We then investigate the error probability, i.e. the probability that the Babai point does not coincide with the nearest lattice point, motivated by the fact that for some cases, a distributed algorithm for finding the Babai point is sufficient for finding the nearest lattice point itself. Two different probability models for$\boldsymbol {X}$are considered—uniform and Gaussian. For the uniform model, in dimensions two and three, the error probability is seen to grow with the packing density, and we demonstrate that the densest lattice in dimension two presents the worst error probability. For higher dimensions, we develop probabilistic concentration bounds as well as bounds based on geometric arguments for the error probability. The probabilistic bounds lead to the conclusion that for lattices which generate suitably thin coverings of$\mathbb {R}^{n}$(which includes lattices that meet Rogers’ bound on the covering radius), the error probability goes to unity as$n$grows. Probabilistic and geometric bounds are also used to estimate the error probability under the uniform model for various lattices including the$A_{n}$family and the Leech lattice,$\Lambda _{24}$. On the other hand, for the Gaussian model, the error probability goes to zero as the lattice dimension tends to infinity, provided the noise variance is sufficiently small.

We construct and analyze the communication cost of protocols (interactive and one-way) for classifying X = (X1,X2, ..., Xn) ∈ [0,1)n⊂ℝn, in a network with n ≥ 2 nodes, with Xiknown only at node i. The classifier takes the form Σi=1nhiXi≥ a, with weights hi∈ {-1,+1}. The interactive protocol (a zero-error protocol) exchanges a variable number of messages depending on the input X and its sum rate is directly proportional to its mean stopping time. An exact analysis, as well as an approximation of the mean stopping time is presented and shows that it depends on γ = α + (1/2 - β), where α = a/n and β = m/n, with m being the number of positive weights. In particular, the mean stopping time grows logarithmically in n when γ = 0, and is bounded in n otherwise. Comparisons show that the sum rate of the interactive protocol is smaller than that of the one-way protocol when the error probability for the one-way protocol is small, with the reverse being true when the error probability is large. Comparisons of the interactive protocol with lower bounds on the sum rate show the correct scaling behavior when γ = 0.

Lattice codes of low rank are considered for an additive Gaussian noise channel with erasures. The objective is to minimize the error probability with no erasures subject to rate and power constraints while ensuring that the error probability under an allowable erasure pattern is bounded from above. Allowable erasure patterns considered here are those of fixed cardinality. Bounds on performance are derived, and several constructions are investigated for lattices in dimension four. It is shown that the problem can be viewed as a simultaneous ellipsoid packing problem, a generalization of the well known sphere packing problem.

We consider the closest lattice point problem in a distributed network setting and study the communication cost and the error probability for computing an approximate nearest lattice point, using the nearest-plane algorithm, due to Babai. Two distinct communication models, centralized and interactive, are considered. The importance of proper basis selection is addressed. Assuming a reduced basis for a two-dimensional lattice, we determine the approximation error of the nearest plane algorithm. The communication cost for determining the Babai point, or equivalently, for constructing the rectangular nearest-plane partition, is calculated in the interactive setting. For the centralized model, an algorithm is presented for reducing the communication cost of the nearest plane algorithm in an arbitrary number of dimensions.

We consider the problem of distributed computation of the nearest lattice point for a two-dimensional lattice. An interactive model of communication is considered. We address the problem of reconfiguring a specific rectangular partition, a nearest plane, or Babai, partition, into the Voronoi partition. Expressions are derived for the error probability as a function of the total number of communicated bits. With an infinite number of allowed communication rounds, the average cost of achieving zero error probability is shown to be finite. For the interactive model, with a single round of communication, expressions are obtained for the error probability as a function of the bits exchanged. We observe that the error exponent depends on the lattice.

Proportional Fair (PF) scheduling algorithms are the de facto standard in cellular networks. They exploit the users' channel state diversity (induced by fast-fading) and are optimal for stationary channel state distributions and an infinite time-horizon. However, mobile users experience a nonstationary channel, due to slow-fading (on the order of seconds), and are associated with base stations for short periods. Hence, we develop the Predictive Finite-horizon PF Scheduling ((PF)2S) Framework that exploits mobility. We present extensive channel measurement results from a 3G network and characterize mobility-induced channel state trends. We show that a user's channel state is highly reproducible and leverage that to develop a data rate prediction mechanism. We then present a few channel allocation estimation algorithms that exploit the prediction mechanism. Our trace-based simulations consider instances of the (PF)2S Framework composed of combinations of prediction and channel allocation estimation algorithms. They indicate that the framework can increase the throughput by 15%-55% compared to traditional PF schedulers, while improving fairness.

A new class of exact-repair regenerating codes is constructed by stitching together shorter erasure correction codes, where the stitching pattern can be viewed as block designs. The proposed codes have the help-by-transfer property where the helper nodes simply transfer part of the stored data directly, without performing any computation. This embedded error correction structure makes the decoding process straightforward, and in some cases the complexity is very low. We show that this construction is able to achieve performance better than space-sharing between the minimum storage regenerating codes and the minimum repair-bandwidth regenerating codes, and it is the first class of codes to achieve this performance. In fact, it is shown that the proposed construction can achieve a nontrivial point on the optimal functional-repair tradeoff, and it is asymptotically optimal at high rate, i.e., it asymptotically approaches the minimum storage and the minimum repair-bandwidth simultaneously.

We consider the probability of data loss, or equivalently, the reliability function for an erasure coded distributed data storage system under worst case conditions. Data loss in an erasure coded system depends on probability distributions for the disk repair duration and the disk failure duration. In previous works, the data loss probability of such systems has been studied under the assumption of exponentially distributed disk failure and disk repair durations, using well-known analytic methods from the theory of Markov processes. These methods lead to an estimate of the integral of the reliability function. Here, we address the problem of directly calculating the data loss probability for general repair and failure duration distributions. A closed limiting form is developed for the probability of data loss, and it is shown that the probability of the event that a repair duration exceeds a failure duration is sufficient for characterizing the data loss probability. For the case of constant repair duration, we develop an expression for the conditional data loss probability given the number of failures experienced by a each node in a given time window. We do so by developing a geometric approach that relies on the computation of volumes of a family of polytopes that are related to the code. An exact calculation is provided, and an upper bound on the data loss probability is obtained by posing the problem as a set avoidance problem. Theoretical calculations are compared with simulation results.

The reliability of erasure-coded distributed storage systems, as measured by the mean time to data loss (MTTDL), depends on the repair bandwidth of the code. Repair-efficient codes provide reliability values several orders of magnitude better than conventional erasure codes. Current state of the art codes fix the number of helper nodes (nodes participating in repair) a priori. In practice, however, it is desirable to allow the number of helper nodes to be adaptively determined by the network traffic conditions. In this work, we propose an opportunistic repair framework to address this issue. It is shown that there exists a threshold on the storage overhead, below which such an opportunistic approach does not lose any efficiency from the optimal storage-repair-bandwidth tradeoff; i.e. it is possible to construct a code simultaneously optimal for different numbers of helper nodes. We further examine the benefits of such opportunistic codes, and derive the MTTDL improvement for two repair models: one with limited total repair bandwidth and the other with limited individual-node repair bandwidth. In both settings, we show orders of magnitude improvement in MTTDL. Finally, the proposed framework is examined in a network setting where a significant improvement in MTTDL is observed.

Proportional Fair (PF) scheduling algorithms are the de-facto standard in cellular networks. They exploit the users' channel state diversity (induced by fast-fading), and are optimal for stationary channel state distributions and an infinite time-horizon. However, mobile users experience a non-stationary channel, due to slow-fading (on the order of seconds), and are associated with basestations for short periods. Hence, we develop the Predictive Finite-horizon PF Scheduling ((PF)2S) Framework that exploits mobility. We present extensive channel measurement results from a 3G network and characterize mobility-induced channel state trends. We show that a user's channel state is highly reproducible and leverage that to develop a data rate prediction mechanism. We then present a few channel allocation estimation algorithms that rely on the prediction mechanism. Our trace-based simulations consider instances of the PF2S Framework composed of combinations of prediction and channel allocation estimation algorithms. They indicate that the framework can increase the throughput by 15%–55% compared to traditional PF schedulers, while improving fairness.

Bounds are developed on the probability that the Cartesian product of a given number of finite random sets does not intersect (avoids) a given fixed set. These bounds are then used to estimate the probability of data loss in a distributed storage system that uses erasure codes to protect against data loss when disks fail. These are the first bounds on the probability of data loss that we are aware of. We compare our upper bound on the probability of data loss to approximations that are used in the literature, and show that our bounds are tighter and the gap is significant in some cases. Our bounds also suggest that in some cases, a more efficient (higher rate) code will suffice to meet a data loss probability target than that predicted by approximations widely used in the industry.

We consider the probability of data loss in an erasure coded distributed storage system. Data loss in an erasure coded system depends on the repair duration and the failure probability of individual disks. This dependence on the repair duration complicates the data loss probability analysis. In previous work, the data loss probability of such systems has been studied under the assumption of exponentially distributed disk life and disk repair durations, using well-known analytic methods from the theory of Markov processes. Here, we assume that the repair duration is a constant and derive an upper bound on the probability of data loss by calculating the volumes of specific polytopes that are determined by the code. Closed form bounds are exhibited for some example codes.

The demand for cloud storage is exploding as an ever increasing number of enterprises and consumers are storing and processing their data in the cloud. Hence, distributed object storage solutions (e.g., QFS, Swift, HDFS) are becoming very critical components of any cloud infrastructure. These systems are able to offer good reliability by distributing redundant information across a large number of commodity servers, making it possible to achieve 10 nines and beyond with relative ease. One drawback of these systems is that they are usually designed for deployment within a single data center, where node-to-node latencies are small. Geo-replication (i.e., distributing redundant information across data centers) for most open-source storage systems is, to the best of our knowledge, accomplished by asynchronously mirroring a given deployment. Given that geo-replication is critical for ensuring very high degrees of reliability (e.g., for achieving 16 nines), in this work we evaluate how these storage systems perform when they are directly deployed in a WAN setting. To this end, three popular distributed object stores, namely Quantcast-QFS, Swift and Tahoe-LAFS, are considered and tested in a three-wide data center environment and our findings are reported.

A new class of exact-repair regenerating codes is constructed by combining two layers of erasure correction codes together with combinatorial block designs. The proposed codes have the “uncoded repair” property where the nodes participating in the repair simply transfer part of the stored data directly, without performing any computation. The layered error correction structure results in a low-complexity decoding process. An analysis of our coding scheme is presented. This construction is able to achieve better performance than timesharing between the minimum storage regenerating codes and the minimum repair-bandwidth regenerating codes.

We address the problem of constructing explicit mappings from a k-dimensional continuous alphabet source to an n-dimensional Gaussian channel. The source is assumed to be uniformly distributed on the unit cube [0, 1)k. The scheme considered is based on a family of piecewise linear mappings and its performance is shown to be related to specific projected lattices of Zn. We study sufficient conditions for the mean squared error of such mappings to scale optimally with the signal-to-noise ratio of the channel and present an explicit construction for the case k = n-1. However, in some other cases our scheme requires the source to be uniformly distributed over a fundamental region of a specific lattice, that may be not congruent to [0, 1)k. A dissection technique is presented in order to overcome the source support mismatch and the MSE degradation of such a transformation is analyzed. An example construction of a 2 : n expansion mapping using the dissection technique is presented and is shown to exhibit optimal scaling of the MSE with the channel SNR.

A new class of spherical codes is constructed by selecting a finite subset of flat tori from a foliation of the unit sphere S2L-1⊂ R2Land designing a structured codebook on each torus layer. The resulting spherical code can be the image of a lattice restricted to a specific box in RLin each layer. Group structure and homogeneity, useful for efficient storage and decoding, are inherited from the underlying lattice codebook. A systematic method for constructing such codes are presented as well some examples of constructions. Upper and lower bounds on the performance, the asymptotic packing density and a method for decoding are derived.

Virtualized cloud-based services can take advantage of statistical multiplexing across applications to yield significant cost savings. However, achieving similar savings with real-time services can be a challenge. In this paper, we seek to lower a provider's costs for real-time IPTV services through a virtualized IPTV architecture and through intelligent time-shifting of selected services. Using Live TV and Video-on-Demand (VoD) as examples, we show that we can take advantage of the different deadlines associated with each service to effectively multiplex these services. We provide a generalized framework for computing the amount of resources needed to support multiple services, without missing the deadline for any service. We construct the problem as an optimization formulation that uses a generic cost function. We consider multiple forms for the cost function (e.g., maximum, convex and concave functions) reflecting the cost of providing the service. The solution to this formulation gives the number of servers needed at different time instants to support these services. We implement a simple mechanism for time-shifting scheduled jobs in a simulator and study the reduction in server load using real traces from an operational IPTV network. Our results show that we are able to reduce the load by ~24%(compared to a possible ~31.3% as predicted by the optimization framework).

We propose a system that makes opportunistic use of mobile computing devices and ad hoc networking to provide a transient storage service to clients in a localized geographical region. The main challenge is to offset the potential data loss caused by node mobility with internode communication. We first argue on the basis of simulation and theory that such a service is feasible, given a sufficiently high density of mobile devices. A distributed communication and storage protocol is then presented for situations where all mobile devices are within communication range of each other, and it is shown through testbed experiments and simulation that the protocol operates correctly and makes efficient use of storage space and communication bandwidth, while maximizing the longevity of stored data.

Camera calibration is essential for many computer vision and image processing applications. However, this calibration process can be rather time consuming and may require a significant amount of human intervention. Calibration models traditionally employ a calibration grid whose four corner points must be marked by hand on a per-frame basis. The objective of this work is to develop a technique for processing these frames rapidly, with as little human intervention as possible. We propose an algorithm to extract the boundaries of the calibration grid automatically, based on a spectral analysis of HD (high-definition) video frames. The accuracy of the intrinsic parameters estimated using our automatic method is evaluated through comparison with those obtained using a method that requires hand labeling of the corner points.

We investigate how consumers view content using Video on Demand (VoD) in the context of an IP-based video distribution environment. Users today can use interactive stream control functions such as skip, replay, fast-forward, pause, and rewind to control their viewing. The use of these functions can place additional demands on the distribution infrastructure (servers, network, and set top boxes) and can be challenging to manage with a large subscriber base. A model of user interaction provides insight into the impact of stream control on server and bandwidth requirements, client responsiveness, etc.

A previously designed architecture that endows a wavelength division multiplexed (WDM) optical network with network management capabilities is studied from an information theoretic perspective. The central component of this system is a degraded Σ-interference channel, which combines a multiple access channel and two degraded broadcast channels. Inner and outer bounds for the capacity region are derived for a general discrete memoryless model and a Gaussian model and are shown to provide a complete solution for the symmetric problem. Comparisons are drawn between the coding technique suggested by our information theoretic analysis and the coding method used in a working implementation.

We investigate the user viewing activity for broadcast TV, pre-recorded content using Digital Video Recording (DVR) and video on demand (VoD) in an IP-based content distribution environment. Advanced stream control functions (play, pause, skip, rewind, etc.) provide users with a high level of interactivity, but place demands on the distribution infrastructure (servers, network, home-network) that can be difficult to manage at large scale. To support system design as well as network capacity planning, it is necessary to have a good model of user interaction. Using traces from a well-provisioned operational environment with a large user population, we first characterize interactivity for broadcast TV, DVR and VoD. We then develop parametric models of individual users stream control operations for VoD. Our analysis shows that interactive behavior is adequately characterized by two semi-Markov models, one for weekdays and another for weekends. We propose a parametric model for the underlying sojourn time distributions and show that it results in a superior fit compared to well known distributions (generalized Pareto and Weibull). In order to validate that our models faithfully capture user behavior, we compare the workload that a VoD server experiences in response to actual traces and synthetic data generated from our proposed models.

A cylinder anchored at two distinct points of the lattice Znis called a strut if its interior does not contain a lattice point. We address the problem of constructing struts of maximal radius in Zn. Our main result is a general construction technique, which we call the lifting construction, which produces a sequence of struts that are optimal in the limit. We also tighten a previous result of ours - an achievable lower bound on the volume of a strut. The problem is motivated by a nonlinear analog communication problem. We demonstrate, through simulation, improvements in performance that are obtained using our construction.

In optically routed networks, information for verifying network configuration is not readily available in electronic form. To address this problem, a low-cost all-digital system was developed in [1], [2] for overlaying a low-rate management data channel on a high-rate payload data channel. In this work, we analyze the performance of this novel multi-user communication system under chip-level asynchronism, extending a previous analysis under chip-level synchronism. Two decoding strategies are investigated: a zero-forcing and a minimum mean-squared error detector. Fundamental tradeoffs among several system parameters are identified.

Recently, an all-digital overlay system has been developed in for providing useful management functionalities in optically routed networks. The main feature of the system is to overlay a low-rate stream of management data on a high-rate payload data channel so that the low-rate stream can be recovered by low-cost decoders located at various points within the network. The two key components of the overlay architecture are (i) a constant weight code used for multiplexing payload data streams, and (ii) a CDMA-based protocol used for managing interference among auxiliary data streams. In this work, we provide a general analysis under chip-asynchronous conditions, thereby extending a previous study under chip-synchronous conditions. Our analysis reveals that the bit error rate of the management data channel is limited by the presence of the payload interference. We show that significant performance improvements can be achieved by exploiting the covariance structure of the payload interference and investigate several low-complexity linear detection strategies. Analytical and numerical performance results are provided, and fundamental tradeoffs among several system parameters are identified.

A new class of spherical codes is constructed by selecting a finite subset of flat tori that foliate the unit sphere S2L-1sub R2Land constructing a structured codebook on each torus in the finite subset. The codebook on each torus is the image of a lattice restricted to a specific hyperbox in RL. Group structure and homogeneity, useful for efficient decoding, are inherited from the underlying lattice codebook. Upper and lower bounds on performance are derived and a systematic search algorithm is presented for constructing optimal codebooks. The torus layer spherical codes presented here exhibit good performance when compared to the well known apple-peeling, wrapped and laminated codes.

We present a novel technique for encoding and decoding constant weight binary vectors that uses a geometric interpretation of the codebook. Our technique is based on embedding the codebook in a Euclidean space of dimension equal to the weight of the code. The encoder and decoder mappings are then interpreted as a bijection between a certain hyper-rectangle and a polytope in this Euclidean space. An inductive dissection algorithm is developed for constructing such a bijection. We prove that the algorithm is correct and then analyze its complexity. The complexity depends on the weight of the vector, rather than on the block length as in other algorithms. This approach is advantageous when the weight is smaller than the square root of the block length.

Media companies (and other organizations with large amounts of digital content) require prompt broadcast of extremely large files from a single source to a collection of geographically dispersed destinations. Due to the high cost of terrestrial networks of sufficient bandwidth, satellite networks are commonly used for such transfers. However, current satellite transfers rely on expensive error correction via forward error correction and whole-file retransmission. This paper presents a new, hybrid solution combining the advantages of satellite and terrestrial networks to provide cost-effective reliable file transfer. Specifically, we propose a new peer-to-peer scheme exploiting fast terrestrial networks and multiple receivers to recover from high loss rates (5% or more) in near real-time (latency < 400ms). This solution is efficient, robust under variable packet loss and connectivity, user tunable, scales well, and doubles bandwidth compared to existing approaches. The system has been validated via extensive simulations using a terrestrial network based on the AT&T common backbone core network

This paper analyzes mathematically the effect of quantizer threshold imperfection commonly encountered in the circuit implementation of analog-to-digital (A/D) converters such as pulse code modulation (PCM) and sigma-delta (SigmaDelta) modulation. SigmaDelta modulation, which is based on coarse quantization of oversampled (redundant) samples of a signal, enjoys a type of self-correction property for quantizer threshold errors (bias) that is not shared by PCM. Although "classical" SigmaDelta modulation is inferior to PCM in the rate-distortion sense, this robustness feature is believed to be one of the reasons why SigmaDelta modulation is preferred over PCM in A/D converters with imperfect quantizers. Motivated by these facts, other encoders are constructed in this paper that use redundancy to obtain a similar self-correction property, but that achieve higher order accuracy relative to bit rate compared to classical SigmaDelta. More precisely, two different types of encoders are introduced that exhibit exponential accuracy in the bit rate (in contrast to the polynomial-type accuracy of classical SigmaDelta) while possessing the self-correction property

We consider the problem of predicting packet loss visibility in MPEG-2 video. We use two modeling approaches: CART and GLM. The former classifies each packet loss as visible or not; the latter predicts the probability that a packet loss is visible. For each modeling approach, we develop three methods, which differ in the amount of information available to them. A reduced reference method has access to limited information based on the video at the encoder's side and has access to the video at the decoder's side. A no-reference pixel-based method has access to the video at the decoder's side but lacks access to information at the encoder's side. A no-reference bitstream-based method does not have access to the decoded video either; it has access only to the compressed video bitstream, potentially affected by packet losses. We design our models using the results of a subjective test based on 1080 packet losses in 72 minutes of video.

We present a novel technique for encoding and decoding constant weight binary codes that uses a geometric interpretation of the codebook. Our technique is based on embedding the codebook in a Euclidean space of dimension equal to the weight of the code. The encoder and decoder mappings are then interpreted as a bijection between a certain hyper-rectangle and a polytope in this Euclidean space. An inductive dissection algorithm is developed for constructing such a bijection. We prove that the algorithm is correct and analyze its complexity. The complexity of the proposed algorithm depends on the weight of the code, rather than on the block length as in previous algorithms. This approach is advantageous when the weight is smaller than the square root of the block length.

Existing solutions for optically routed networks (ORNs) lack certain key management functions available to electronically routed networks. In particular, ORNs have extremely limited capabilities to trace the path of an optical signal through the network. In this paper, we present a method for embedding path identification and other management information into the transport stream in such a way that the management information can be read by a low-bandwidth, low-cost receiver, without having to terminate or decode the full-rate payload stream. We outline a method for embedding such management information, using a digital coding process at the transmitter, and two distinct digital decoding processes for receiving the management and payload data streams, respectively. Feasibility of the method is demonstrated by computing the bit-error performance of example codes under realistic operating conditions, including multiple management streams in multiwavelength systems.

The ability of a human to visually detect whether a packet has been lost during the transport of compressed video depends heavily on the location of the packet loss and the content of the video. In this paper, we explore when humans can visually detect the error caused by individual packet losses. Using the results of a subjective test based on 1080 packet losses in 72 minutes of video, we design a classifier that uses objective factors extracted from the video to predict the visibility of each error. Our classifier achieves over 93% accuracy.

We formulate 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 describe 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 show 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 is provided for this case.

We consider monitoring the quality of compressed video transmitted over a packet network from the perspective of a network service provider. Our focus is on no-reference methods, which do not access the original signal, and on evaluating the impact of packet losses on quality. We present three methods to estimate mean squared error (MSE) due to packet losses directly from the video bitstream. NoParse uses only network-level measurements (like packet loss rate), QuickParse extracts the spatio-temporal extent of the impact of the loss, and FullParse extracts sequence-specific information including spatio-temporal activity and the effects of error propagation. Our simulation results with MPEG-2 video subjected to transport packet losses illustrate the performance possible using the three methods.

We consider monitoring the quality of compressed video transmitted over a packet network from the perspective of a network service provider. We estimate the mean-squared error (MSE) caused by packet loss, by examining only the received video bitstream. We merge the best aspects of two of our previously reported methods, with the goal of creating a low-complexity quality monitor that will be able to process many streams simultaneously in the network.

We consider monitoring the quality of compressed video transmitted over a packet network from the perspective of a network service provider. We estimate the mean-squared error (MSE) caused by packet loss by examining only the received video bitstream. We describe our fullparse method, which extracts sequence-specific information including spatio-temporal activity and the effects of error propagation. We show that fullparse performs well with manageable complexity.

We consider two codes based on dynamical systems, for transmitting information from a continuous alphabet, discrete-time source over a Gaussian channel. The first code, a homogeneous spherical code, is generated by the linear dynamical system s/spl dot/=As, with A a square skew-symmetric matrix. The second code is generated by the shift map s/sub n/=b/sub n/s/sub n-1/(mod 1). The performance of each of these codes is determined by the geometry of its locus or signal set, specifically, its arc length and minimum distance, suitably defined. We show that the performance analyses for these systems are closely related, and derive exact expressions and bounds for relevant geometric parameters. We also observe that the lattice /spl Zopf//sup N/ underlies both modulation systems and we develop a fast decoding algorithm that relies on this observation. Analytic results show that for fixed bandwidth expansion, good scaling behavior of the mean squared error is obtained relative to the channel signal-to-noise ratio (SNR). Particularly interesting is the resulting observation that sampled, exponentially chirped modulation codes are good bandwidth expansion codes.

Good codes for transmitting a continuous-alphabet source over an AWGN channel can be constructed using simple dynamical systems. The trajectories of the dynamical systems that we consider are curves in /spl Ropf//sup N/, and we use these curves as signal sets for a modulation system. In this paper we consider the problem of choosing the parameters of the dynamical system such that the length of its trajectory is maximized subject to a constraint on the minimum distance between its "folds". We provide some general results on the construction of such curves and show how to select the parameters optimally in the case N=6. This is done by reducing the problem to one of choosing a vector (1, a, b) in /spl Zopf//sup 3/ for which a high packing density is obtained for the lattice /spl Lambda//sub p/ obtained by projecting /spl Zopf//sup 3/ into the plane orthogonal to (1, a, b). Two approaches are used to prove the central result of the paper.

We consider the design of asymmetric multiple description lattice quantizers that cover the entire spectrum of the distortion profile, ranging from symmetric or balanced to successively refinable. We present a solution to a labeling problem, which is an important part of the construction, along with a general design procedure. The high-rate asymptotic performance of the quantizer is also studied. We evaluate the rate-distortion performance of the quantizer and compare it to known information-theoretic bounds. The high-rate asymptotic analysis is compared to the performance of the quantizer.

We consider Zador's (1963, 1966, 1982) asymptotic formula for the distortion-rate function for a variable-rate vector quantizer in the high-rate case. This formula involves the differential entropy of the source, the rate of the quantizer in bits per sample, and a coefficient G which depends on the geometry of the quantizer but is independent of the source. We give an explicit formula for G in the case when the quantizing regions form a periodic tiling of n-dimensional space, in terms of the volumes and second moments of the Voronoi cells. As an application we show, extending earlier work of Kashyap and Neuhoff (see ibid, vol.47, p.2538-2383, 2001) that even a variable-rate three-dimensional quantizer based on the "A15" structure is still inferior to a quantizer based on the body-centered cubic lattice. We also determine the smallest covering radius of such a structure.

The objective of multiple description coding (MDC) is to encode a source into multiple bitstreams supporting multiple quality levels of decoding. In this paper, we only consider the two-description case, where the requirement is that a high-quality reconstruction should be decodable from the two bitstreams together, while lower, but still acceptable, quality reconstructions should be decodable from either of the two individual bitstreams. This paper describes techniques for meeting MDC objectives in the framework of standard transform-based image coding through the design of pairwise correlating transforms. The correlation introduced by the transform helps to reduce the distortion when only a single description is received, but it also increases the bit rate beyond that prescribed by the rate-distortion function of the source. We analyze the relation between the redundancy (i.e., the extra bit rate) and the single description distortion using this transform-based framework. We also describe an image coder that incorporates the pairwise transform and show its redundancy-rate-distortion performance for real images.

Sigma-delta modulation, a widely used method of analog-to-digital (A/D) signal conversion, is known to be robust to hardware imperfections, i.e., bit streams generated by slightly imprecise hardware components can be decoded comparably well. We formulate a model for robustness and give a rigorous analysis for single-loop sigma-delta modulation applied to constant signals (DC inputs) for N time cycles, with an arbitrary (small enough) initial condition u/sub o/, and a quantizer that may contain an offset error. The mean-square error (MSE) of any decoding scheme for this quantizer (with u/sub o/ and the offset error known) is bounded below by 1/96N/sup -3/. We also determine the asymptotically best possible MSE as N/spl rarr//spl infin/ for perfect decoding when u/sub o/=0 and u/sub o/= 1/2 . The robustness result is the upper bound that a triangular linear filter decoder (with both u/sub o/ and the offset error unknown) achieves an MSE of 40/3N/sup -3/. These results establish the known result that the O(1/N/sup 3/) decay of the MSE with N is optimal in the single-loop case, under weaker assumptions than previous analyses, and show that a suitable linear decoder is robust against offset error. These results are obtained using methods from number theory and Fourier analysis.

The problem of designing a multiple-description vector quantizer with lattice codebook /spl Lambda/ is considered. A general solution is given to a labeling problem which plays a crucial role in the design of such quantizers. Numerical performance results are obtained for quantizers based on the lattices A/sub 2/ and Z/sup i/, i=1, 2, 4, 8, that make use of this labeling algorithm. The high-rate squared-error distortions for this family of L-dimensional vector quantizers are then analyzed for a memoryless source with probability density function (PDF) p and differential entropy h(p)

We consider the design of asymmetric multiple description lattice quantizers that cover the entire spectrum of the distortion profile, ranging from symmetric or balanced to successively refinable. We present a solution to a labeling problem, which is an important part of the construction, along with a general design procedure. This procedure is illustrated using a ZZ/sup 2/ lattice. We also evaluate its rate-distortion performance and compare it to known information theoretic bounds.

In the presence of bit errors, variable length (VL) codes often suffer from a loss of synchronization, which leads to spans of symbol errors. It is of our interest to investigate whether the redundancy introduced by multiple description (MD) coding is useful for improving performance. We consider a sequence of i.i.d. source symbols of known length, first quantized, then coded using MD VL codes and transmitted over a binary symmetric channel (BSC). We propose a maximum a posteriori probability (MAP) decoder, in which the optimal sequence with the right number of symbols and bits is found using the Viterbi algorithm. We compare the MD VL code performance against a conventional single description (SD) VL entropy code, and against a single description (SD) parity code.

We consider the problem of coding images for transmission over error-prone channels. The impairments we target are transient channel shutdowns, as would occur in a packet network when a packet is lost, or in a wireless system during a deep fade: when data is delivered it is assumed to be error-free, but some of the data may never reach the receiver. The proposed algorithms are based on a combination of multiple description scalar quantizers with techniques successfully applied to the construction of some of the most efficient subband coders. A given image is encoded into multiple independent packets of roughly equal length. When packets are lost, the quality of the approximation computed at the receiver depends only on the number of packets received, but does not depend on exactly which packets are actually received. When compared with previously reported results on the performance of robust image coders based on multiple descriptions, on standard test images, our coders attain similar PSNR values using typically about 50-60% of the bit rate required by these other state-of-the-art coders, while at the same time providing significantly more freedom in the mechanism for allocation of redundancy among descriptions.

In this paper the windowed Fourier encoding-decoding scheme applied to the multiple description compression problem is analyzed. In the general case, four window functions are needed to define the encoder and decoder, although this number can be reduced to three or two by using time-shift or frequency-shift division schemes. The encoding coefficients are next divided into two groups according to the eveness of either the modulation or translation index. The distortion on each channel is analyzed using the Zak transform. For the optimal windows, explicit representation formulas are obtained and nonlocalization results are proved. Asymptotic formulas of the total distortion and transmission rate are established and the redundancy is shown to trade off between these two.

We consider the problem of designing a lattice-based multiple description vector quantizer for a two-channel diversity system. The design of such a quantizer can be reduced to the problem of assigning pair labels to points of a vector quantizer codebook. A general labeling procedure based on the structure of the lattice is presented, along with detailed results for the hexagonal lattice: algorithms, asymptotic performance, and numerical simulations. Asymptotically, when compared with the lattice Z, the resulting quantizer achieves the standard second-moment gain of the hexagonal lattice for the central distortion, and, surprisingly, achieves the two-dimensional sphere gain for the side distortion.

A balanced twin-description interframe video coder is designed and performance results are presented for video transmission aver packet networks with packet losses. The coder is based on a predictive multiple description quantizer structure called mutually-refining DPCM (MR-DPCM). The novel feature of this predictive quantizer is that the decoder and encoder filter states trade in either of the two single-channel modes as well as in the two-channel mode. The performance and indeed the suitability of the multiple description approach for a network with packet lasses depends an the packetization method. Two packetization methods are considered-a "correct" one and a low latency but "incorrect" one. Performance results are presented for synthetic sources as well as for a video sequence under a variety of conditions.

We consider the problem of image coding for communication systems that use diversity to overcome channel impairments. We focus on the special case in which there are two channels of equal capacity between a transmitter and a receiver. Our designs are based on a combination of techniques successfully applied to the construction of some of the most efficient wavelet based image coding algorithms, with multiple description scalar quantizers (MDSQs). For a given image, we produce two bitstreams, to be transmitted over each channel. Should one of the channels fail, each individual description guarantees a minimum image quality specified by the user. However, if both descriptions arrive at destination, they are combined to produce a higher quality image than that achievable based on individual descriptions. We formulate a discrete optimization problem, whose solution gives parameters of the proposed encoder yielding optimal performance in an operational sense. Simulation results are presented.

A high-rate analysis of multiple description quantizers is presented for rth-power distortions and general source densities. Both, fixed-length and variable-length encoding of the quantizer indices are considered. Optimal companding functions are shown to be the same as for single-channel quantizers. As compared to the bound of Ozarow (1980), a gap of 8.69 dB and 3.07 dB exists between the entropy-constrained and level-constrained cases, respectively, for a memoryless Gaussian source and r=2.

The objective of multiple description coding (MDC) is to encode a source into two (or more) bitstreams supporting two quality levels of decoding. A high-quality reconstruction should be decodable from the two bitstreams together, while lower, but still acceptable, quality reconstructions should be decodable from either of the two individual bitstreams. This paper describes techniques for meeting MDC objectives in the framework of standard transform-based image coding through the design of pairwise transforms.

The multiple description transform coder is introduced for sources with memory and an asymptotic analysis is presented for the squared error distortion. For stationary Gaussian sources, the optimal transform and the optimal bit allocation for the multiple description coder are identical to those for the single description coder.

Fractal coding and classi#ed transform coding exhibit strong structural similarity, but they use di#erenttypes of redundancy in image data: piecewise self-similarity in one case and local correlation in the other. Comparing performance of the two techniques leads to a quantitative, compression-oriented de#nition of piecewise self-similarity. The amount of piecewise self-similarity is evaluated for sample images. For a moderate number of domain blocks, classi#ed transform coding consistently outperforms fractal coding, and the images are not found to be piecewise self-similar. As the number of domain blocks increases, the performance gap becomes negligible. 1. INTRODUCTION Fractal coding #1# is a recent approach to image compression. Its basic premise is that images exhibit a type of redundancy called piecewise self-similarity. In a piecewise self-similar image, a blockofwaveform data can be related to another one so that the two resemble each other. Compression is achieved if one of th...

We consider the problem of reducing the peak distortion of transform/wavelet compression schemes. A new coding scheme called transient DPCM (T-DPCM) is developed. It is shown that T-DPCM has the same asymptotic (in rate) mean squared-error (MSE) performance as the transform or wavelet compression system it is derived from (for an appropriate model). Further, it is shown that T-DPCM has significantly smaller peak distortion than the corresponding transform/wavelet coder. Results are provided for synthetic source models and for the image 'Lena'.

A part of a fractal code is an assignment of a domain block to every range block. The assignment is used to construct the dependence graph of a fractal code. The vertices of the graph represent the range blocks. Two vertices z and y are connected by a directed edge from y to x if the range block y is overlapped, fully or partially, by the domain block assigned to the range block x. An algorithm to analyze the structure of the dependence graph is presented. The exposed structure of the graph can be used for three different purposes. The first one is convergence analysis: the affine transformations linking domain and range blocks can be classified into those that affect convergence and those that do not. The second one is decoding time reduction: certain range blocks can be reconstructed in a non-iterative way. The third one is improving upon collage coding: the affine transformations for some range blocks can be optimized based on the domain blocks extracted from the reconstructed rather than the original image.

Speech quality in packetized speech systems can degrade substantially when packets are lost. We consider the problem of DPCM system design for packetized speech systems. The problem is formulated as a multiple description problem and the problem of optimal selection of the encoder and decoder filters is addressed. We show that significant improvements in performance are obtained as compared to an earlier system proposed by Jayant and Christensen (1981). Further, we show that for a first-order Gauss-Markov source significant performance improvements can be obtained by using a second-order predictor instead of a first-order predictor.>

We show the multiple description scalar quantizer (MDSQ), when used over a slow fading Rayleigh channel, results in a smaller interleaving delay than traditional channel code-based approaches and substantially outperforms a system using a maximum ratio combiner. We consider a continuous alphabet source without memory over a slow Rayleigh fading channel. Specifically, it is initially assumed that the Rayleigh parameter remains constant over a specific time interval and the demodulator has available perfect estimates of the Rayleigh parameter. An analysis of the problem is presented and theoretical justification is provided for using the MDSQ. For a Gaussian source without memory, performance comparisons are presented against a traditional maximum ratio combiner (MRC)-based system as well as against channel code-based systems. It is shown that the performance of the MDSQ-based system dominates the MRC-based system at all channel signal-to-noise ratios and is superior to channel code-based systems when the interleaving delay is constrained. Simulation results for a mobile radio channel model at 15 m.p.h. indicate a reduction in the interleaving delay by at least a factor of three.

A fractal encoder processes the original source vector by selecting a contractive map whose unique fixed point (attractor) approximates the original. A description of the map is transmitted to the decoder. The decoder iterates the map to recover the attractor. The task of picking the map is called the inverse problem. The predominantly used, suboptimum, technique to solve the inverse problem is collage coding. In collage coding, only the first decoding iteration is optimized. We propose two new suboptimum algorithms for the inverse problem. In our approach, the encoder imitates the iterative operation of the decoder. At each step, however, a new map is used so as to keep the sequence of approximations close to the original. If the sequence converges, then the limit is an attractor, and it is a good candidate for the reconstructed vector. The description of the map corresponding to the attractor is sent to the decoder.>

The problem of entropy-constrained multiple-description scalar quantizer design is posed as an optimization problem, necessary conditions for optimality are derived, and an iterative design algorithm is presented. Performance results are presented for a Gaussian source, along with comparisons to the multiple-description rate distortion bound and a reference system.>

Fractal image compression using self-affine transformations has recently drawn considerable attention. Although some elements of the technique have a well-established foundation, many issues remain unclear. We consider the attractors that are obtained by varying the parameters of the contractive transformation. We show that the parameters can be divided into two groups and that if the parameters in the first group are fixed, the set of attractors obtained by varying the parameters in the second group is a vector space. Based on this observation, an improvement to the collage coding technique for encoding data is obtained. We then present a coder, referred to as the classified transform coder, which is structurally limited in the same way as the fractal coder. However, in the classified transform coder, the design of the pool of subspaces is directly addressed. Finally, some performance results are presented for the classified transform coder.© (1993) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

The design of scalar quantizers for communication systems that use diversity to overcome channel impairments is considered. The design problem is posed as an optimization problem and necessary conditions for optimality are derived. A design algorithm, a generalization of S.P. Lloyd's (1962) algorithm for quantizer design, is developed. Unlike a single channel scalar quantizer, the performance of a multiple description scalar quantizer is dependent on the index assignment. The problem of index assignment is addressed. Good index assignments, performance results, and sample quantizer designs are presented for a memoryless Gaussian source. Comparisons are made with rate distortion bounds for the multiple description problem.>

The problem of designing block source codes and modulation signal sets that are both energy and bandwidth constrained is considered. For the class of linear estimator-based decoders, necessary conditions for optimality for the encoder, decoder and modulation signal set are derived. An algorithm that iteratively solves these necessary conditions to converge to a locally optimum solution has been developed. By studying the performance of the previous class of digital communication systems in the limit of infinite encoding rates, it is demonstrated that the MSE of a bandwidth and energy constrained digital system is bounded from below by that of a block pulse amplitude modulation system. This bound is readily computable in terms of the eigenvalues of the source and channel covariance matrices. The results indicate that for a correlated source, a sufficiently noisy channel and specific source block sizes and bandwidths, the digital system performance coincides with the optimum performance theoretically attainable. Further, significant performance improvements over the standard VQ-based system are demonstrated when the channel is noisy.>

The performance and complexity of channel-optimized vector quantizers are studied for the Gauss-Markov source. Observations on the geometric structure of these quantizers are made, which have an important implication on the encoding complexity. For the squared-error distortion measure, it is shown that an operation equivalent to a Euclidean distance measurement with respect to an appropriately defined set of points (used to identify the encoding regions) can be used to perform the encoding. This implies that the encoding complexity is proportional to the number of encoding regions. It is then demonstrated that for very noisy channels and a heavily correlated source, when the codebook size is large, the number of encoding regions is considerably smaller than the codebook size-implying a reduction in encoding complexity.>

A method is presented for the joint source-channel coding optimization of a scheme based on the two-dimensional block cosine transform when the output of the encoder is to be transmitted via a memoryless binary symmetric channel. The authors' approach involves an iterative algorithm for the design of the quantizers (in the presence of channel errors) used for encoding the transform coefficients. This algorithm produces a set of locally optimum (in the mean-squared error sense) quantizers and the corresponding binary codeword assignment for the assumed transform coefficient statistics. To determine the optimum bit assignment among the transform coefficients, the authors have used an algorithm based on the steepest descent method, which, under certain convexity conditions on the performance of the channel-optimized quantizers, yields the optimal bit allocation. Simulation results for the performance of this locally optimum system over noisy channels have been obtained, and appropriate comparisons with a reference system designed for no channel errors have been made. It is shown that substantial performance improvements can be obtained by using this scheme. Furthermore, theoretically predicted results and rate distortion-theoretic bounds for an assumed two-dimensional image model are provided.>

We present an analysis of the zero-memory quantization of memoryless sources when the quantizer output is to be encoded and transmitted across a noisy channel. Necessary conditions for the joint optimization of the quantizer and the encoder/decoder pair are presented, and an iterative algorithm for obtaining a locally optimum system is developed. The performance of this locally optimal system, obtained for the class of generalized Gaussian distributions and the binary symmetric channel, is compared against the optimum performance theoretically attainable (using rate-distortion theoretic arguments), as well as against the performance of Lloyd-Max quantizers encoded using the natural binary code and the folded binary code. It is shown that this optimal design could result in substantial performance improvements. The performance improvements are more noticeable at high bit rates and for broad-tailed densities.