nils-herrmann/clean_scirepeval huggingface dataset:
Arithmetic coding based continuous error detection for efficient ARQ-based image transmission

Block cyclic redundancy check (CRC) codes are typically used to perform error detection in automatic repeat request (ARQ) protocols for data communications. Though efficient, CRCs can detect errors only after an entire block of data has been received and processed. In this work, we introduce a new "continuous" error detection scheme using arithmetic coding that provides a novel tradeoff between the amount of added redundancy and the amount of time needed to detect an error once it occurs. This method of error detection is achieved through the use of an arithmetic codec, and has the attractive feature that it can be combined physically with arithmetic source coding, which is widely used in state-of-the-art image coders. We analytically optimize the tradeoff between added redundancy and error-detection time, achieving significant gains in bit rate throughput over conventional ARQ schemes for binary symmetric channel models for all probabilities of error.
An investigation of wavelet-based image coding using an entropy-constrained quantization framework

Wavelet image decompositions generate a tree-structured set of coefficients, providing an hierarchical data-structure for representing images. A new class of previously proposed image compression algorithms has focused on new ways for exploiting dependencies between this hierarchy of wavelet coefficients using "zero-tree" data structures. This paper presents a new framework for understanding the efficiency of one specific algorithm in this class we introduced previously and dubbed the space-frequency quantization (SFQ)-based coder. It describes, at a higher level, how the SFQ-based image coder of our earlier work can be construed as a simplified attempt to design a global entropy-constrained vector quantizer (ECVQ) with two noteworthy features: (i) it uses an image-sized codebook dimension (departing from conventional small-dimensional codebooks that are applied to small image blocks); and (ii) it uses an on-line image-adaptive application of constrained ECVQ (which typically uses off-line training data in its codebook design phase). The principal insight offered by the new framework is that improved performance is achieved by more accurately characterizing the joint probabilities of arbitrary sets of wavelet coefficients. We also present an empirical statistical study of the distribution of the wavelet coefficients of high-frequency bands, which are responsible for most of the performance gain of the new class of algorithms. This study verifies that the improved performance achieved by the new class of algorithms like the SFQ-based coder can be attributed to its being designed around one conveniently structured and efficient collection of such sets, namely, the zero-tree data structure. The results of this study further inspire the design of alternative, novel data structures based on nonlinear morphological operators.
Exploring connections between Sparse Fourier Transform computation and decoding of product codes

We show that the recently proposed Fast Fourier Aliasing-based Sparse Transform (FFAST) algorithm for computing the Discrete Fourier Transform (DFT)  of signals with a sparse DFT is equivalent to iterative hard decision decoding of product codes. This connection is used to derive the thresholds for sparse recovery based on a recent analysis by Justensen [2] for computing thresholds for product codes. We first extend Justesen's analysis to d-dimensional product codes and compute thresholds for the FFAST algorithm based on this. Additionally, this connection also allows us to analyze the performance of the FFAST algorithm under a burst sparsity model in addition to the uniformly random sparsity model which was assumed in prior work .
Colored Gaussian Source–Channel Broadcast for Heterogeneous (Analog/Digital) Receivers

The problem of transmitting a Gaussian source with memory to a digital and a linear-analog receiver, over an arbitrarily colored, nondegraded Gaussian broadcast channel is studied. The main result of this work is a complete characterization of the set of achievable distortion pairs at the two receivers given a power constraint at the transmitter. Further, a constructive hybrid uncoded-coded scheme consisting of the cascade of source coding with side information and channel coding with side information systems is shown to achieve the entire power-mean squared error (MSE) distortion region associated with the problem. An interesting operating point in this region is one where the digital receiver obtains the classical point-to-point optimal quality and the analog receiver attains the best possible simultaneously achievable distortion. This problem is motivated by the practical application of the seamless ldquoin-bandrdquo digital upgrade of legacy analog transmission systems.
One extra bit of download ensures perfectly private information retrieval

Private information retrieval (PIR) systems allow a user to retrieve a record from a public database without revealing to the server which record is being retrieved. The literature on PIR considers only replication-based systems, wherein each storage node stores a copy of the entire data. However, systems based on erasure codes are gaining increasing popularity due to a variety of reasons. This paper initiates an investigation into PIR in erasure-coded systems by establishing its capacity and designing explicit codes and algorithms. The notion of privacy considered here is information-theoretic, and the metric optimized is the amount of data downloaded by the user during PIR. In this paper, we present four main results. First, we design an explicit erasure code and PIR algorithm that requires only one extra bit of download to provide perfect privacy. In contrast, all existing PIR algorithms require a download of at least twice the size of the requisite data. Second, we derive lower bounds proving the necessity of downloading at least one additional bit. This establishes the precise capacity of PIR with respect to the metric of download. These results are also applicable to PIR in replication-based systems, which are a special case of erasure codes. Our third contribution is a negative result showing that capacity-achieving codes necessitate super-linear storage overheads. This motivates the fourth contribution of this paper: an erasure code and PIR algorithm that requires a linear storage overhead, provides high reliability to the data, and is a small factor away from the capacity.
Learning mixtures of sparse linear regressions using sparse graph codes

In this paper, we consider the mixture of sparse linear regressions model. Let β<sup>(1)</sup>,…, β<sup>(L)</sup> ∊ C<sup>n</sup> be L unknown sparse parameter vectors with a total of K non-zero coefficients. Noisy linear measurements are obtained in the form y<inf>i</inf> = x<inf>i</inf><sup>H</sup>β<sup>(ℓi)</sup> + w<inf>i</inf>, each of which is generated randomly from one of the sparse vectors with the label ℓ<inf>i</inf> unknown. The goal is to estimate the parameter vectors efficiently with low sample and computational costs. This problem presents significant challenges as one needs to simultaneously solve the demixing problem of recovering the labels ℓ<inf>1</inf> as well as the estimation problem of recovering the sparse vectors β <sup>(ℓ)</sup>. Our solution to the problem leverages the connection between modern coding theory and statistical inference. We introduce a new algorithm, Mixed-Coloring, which samples the mixture strategically using query vectors x<inf>i</inf> constructed based on ideas from sparse graph codes. Our novel code design allows for both efficient demixing and parameter estimation. The algorithm achieves the order-optimal sample and time complexities of Θ (K) in the noiseless setting, and near-optimal Θ (K polylog(n)) complexities in the noisy setting. In one of our experiments, to recover a mixture of two regressions with dimension n = 500 and sparsity K = 50, our algorithm is more than 300 times faster than EM algorithm, with about 1/3 of its sample cost.
On low-complexity video encoding through feedback

We consider the design of a low-complexity video encoder in a scenario where an unconstrained receiver can help the encoder reduce complexity by exploiting feedback. To aid us in making design choices, we propose a simple model for video data that captures key properties of the temporal correlation between video frames and the predictability of motion vectors. Our analysis identifies the strengths and weaknesses of previous approaches and motivates a hybrid approach in which the decoder sends motion information to reduce motion estimation workload, the encoder uses incremental distributed source coding on the blocks with poor motion estimates, and the decoder performs decoder motion search and requests additional bits when necessary. Under the model, our analysis shows that such a hybrid scheme outperforms prior approaches. Experimental results of comparable implementations indicate that the hybrid scheme, while not fully implemented, is very promising in practice.
Capacity issues in digital image watermarking

We study certain aspects of the problem of watermarking images, not for the classical example of ownership identification, but instead for embedding a unique identifier that can act as a "serial number" for the image in which it is embedded. In this context, two fundamental questions are: (a) what is the maximum number of different watermarks that can be distinguished reliably? and (b) what are good design techniques for watermarking methods to approximate that maximum? Under the assumption that attacks can be modeled as additive noise, we provide answers to both questions. To answer (a), we first show how the process of inserting a watermark is analogous to that of storing bits in certain devices, and then we compute the storage capacity of these devices. To answer (b), we present a specific design of a modulator to store information in those devices. Numerical simulations reveal that although strongly suboptimal in the number of bits they can effectively store in an image, simple and very low complexity modulator designs are able to pack enough bits in an image to be useful in practice.
Interference alignment as a tool in network coding as applied to distributed storage

In this paper, we outline an approach to the task of designing network codes in a non-multicast setting. Our approach makes use of the concept of interference alignment. As an example, we consider the distributed storage problem where the data is stored across the network in n nodes and where a data collector can recover the data by connecting to any k of the n nodes and where furthermore, upon failure of a node, a new node can replicate the data stored in the failed node while minimizing the repair bandwidth.
Complexity-outsourced low-latency video encoding through feedback under a sum-rate constraint

In live video communication, the quality of the video that is encoded on a mobile device is more often than not constrained by the available computational resources. We address this problem by allowing the encoder to “outsource” the encoding complexity to the decoder through the use of feedback, under a sum-rate constraint comprising the weighted sum of the forward and feedback rates. Analysis of such a complexity-outsourced framework using an analytically tractable video model reveals that the feedback rate should be optimally adapted to the video motion characteristics. Application of our framework to real-world video sequences reveals the efficacy of our proposed architecture, with experimental results validating that substantial gains in PSNR are achievable over state-of-the-art fast-search algorithms at a comparable level of complexity. These gains are significant even for mobile live video communication applications over the Internet.
PRISM: a "reversed" multimedia coding paradigm

In this work, we present PRISM (power-efficient, robust, high-compression, syndrome-based multimedia coding), a video coding paradigm based on the principles of coding with side information (which, unlike the classical Wyner-Ziv coding scenario Wyner, A et al. (1976), is characterized by an ambiguous state of nature characterizing the side-information Ishwar, P et al. (2003)). PRISM's architectural goals are to inherit the low encoding complexity and robustness of motion-JPEG style intra-frame video codecs while approaching the high compression efficiency of full-motion interframe video codecs. The PRISM paradigm roughly swaps the encoder-decoder complexity with respect to conventional video coding architectures through the novel concept of moving the motion compensation task from the encoder to the decoder. These traits make PRISM well-matched to uplink-rich media applications involving wireless video and security cameras, multimedia-equipped phones and PDA's etc.
Clustering source/channel rate allocations for receiver-driven multicast under a limited number of streams

We propose a clustering based algorithm to address the problem of receiver-driven multicast with error control under the constraint of a given limited number of streams, where each stream represents the same audio or video source having the same transmission rate but a different redundancy. Our algorithm formulates a design methodology for this set of packetized streams such that it best covers, in a global expected distortion sense, a collection of possible packet erasure channels with respect to a probability distribution over the collection. The resulting set of streams is suitable for Internet multicast to a collection of receivers with various packet loss characteristics. The algorithm is essentially a K-means algorithm, and in one simulation, reduces the expected distortion by over 4 dB with only 4 streams.
Arithmetic coding-based continuous error detection for efficient ARQ-based image transmission

Block cyclic redundancy check (CRC) codes are typically used to perform error detection in automatic repeat request (ARQ) protocols for data communications. Although efficient, CRCs can detect errors only after an entire block of data has been received and processed. We propose a new "continuous" error detection scheme using arithmetic coding that provides a novel tradeoff between the amount of added redundancy and the amount of time needed to detect an error once it occurs. This method of error detection, first introduced by Bell, Witten, and Cleary (1990), is achieved through the use of an arithmetic codec, and has the attractive feature that it can be combined physically with arithmetic source coding, which is widely used in state of-the-art image coders. We analytically optimize the tradeoff between added redundancy and error-detection time, achieving significant gains in bit rate throughput over conventional ARQ schemes for binary symmetric channel models for all probabilities of error.
Joint source channel matching for a wireless image transmission

Application of joint source-channel matching in heterogeneous multi-media environments will demand general source-channel optimization schemes suitable for a wide variety of source coding standards, channel coders, and variable channel conditions. We develop a general approach for joint source-channel matching based on a parametric distortion model that can be accurately applied to most classes of source and channel coders. Our simulations indicate that it may be possible to obtain nearly all of the benefits of joint source-channel optimization by matching existing source and channel coding standards using the simple and general approach we propose.
Securing Dynamic Distributed Storage Systems Against Eavesdropping and Adversarial Attacks

We address the problem of securing distributed storage systems against eavesdropping and adversarial attacks. An important aspect of these systems is node failures over time, necessitating, thus, a repair mechanism in order to maintain a desired high system reliability. In such dynamic settings, an important security problem is to safeguard the system from an intruder who may come at different time instances during the lifetime of the storage system to observe and possibly alter the data stored on some nodes. In this scenario, we give upper bounds on the maximum amount of information that can be stored safely on the system. For an important operating regime of the distributed storage system, which we call the bandwidth-limited regime, we show that our upper bounds are tight and provide explicit code constructions. Moreover, we provide a way to short list the malicious nodes and expurgate the system.
Image transmission using arithmetic coding based continuous error detection

Block cyclic redundancy check (CRC) codes represent a popular and powerful class of error detection techniques in modern data communication systems. Though efficient, CRCs can detect errors only after an entire block of data has been received and processed. We propose a new "continuous" error detection scheme using arithmetic coding that provides a novel tradeoff between the amount of added redundancy and the amount of time needed to detect an error once it occurs. We demonstrate how the new error detection framework improves the overall performance of transmission systems, and show how sizeable performance gains can be attained. We focus on two popular scenarios: (i) automatic repeat request (ARQ) based transmission; and (ii) forward error correction frameworks based on (serially) concatenated coding systems involving an inner error-correction code and an outer error-detection code.
Efficient file synchronization: A distributed source coding approach

The problem of reconstructing a source sequence with the presence of decoder side-information that is mis-synchronized to the source due to deletions is studied in a distributed source coding framework. Motivated by practical applications, the deletion process is assumed to be bursty and is modeled by a Markov chain. The minimum rate needed to reconstruct the source sequence with high probability is characterized in terms of an information theoretic expression, which is interpreted as the amount of information of the deleted content and the locations of deletions, subtracting “nature's secret”, that is, the uncertainty of the locations given the source and side-information. For small bursty deletion probability, the asymptotic expansion of the minimum rate is computed.
Distributed source coding: symmetric rates and applications to sensor networks

We address the problem of distributed source coding using a practical and constructive approach, referred to as distributed source coding using syndromes (DISCUS), with applications to sensor networks. We propose low complexity encoding and decoding methods based on linear codes, to achieve all points in the achievable rate region of the Slepian-Wolf (1973) problem. The extension of these concepts to the construction of Euclidean-space codes is also studied and analyzed for the case of trellis and lattice codes. The performance of these symmetric methods for encoding with a fidelity criterion is shown to be the same as that of asymmetric encoding. Simulations are presented to corroborate these results.
On enhancing MPEG video broadcast over wireless networks with an auxiliary broadcast channel

We study the problem of enhancing a baseline standards-compliant video-over-wireless broadcast system through the use of an auxiliary wireless broadcast channel. Our proposed solution is based on the information-theoretic concept of broadcast source coding which subsumes the concept of source coding with side-information. We integrate into this framework an analytically tractable mechanism for dynamically incorporating channel loss. Empirical validation of our proposed algorithm on a typical 3G wireless network broadcast channel simulator reveals its superior performance over pure FEC-based solutions by an average of 2-4 dB in PSNR.
Coding for sensor networks using untuned radios

The drive toward the implementation and massive deployment of wireless sensor networks calls for ultra-low-cost and low-power nodes. While the digital subsystems of the nodes are still riding Moore's Law, there is no such trend regarding the performance of analog components. This work presents a fully integrated architecture of both digital and analog components (including local oscillator) that offers significant reduction in cost, size and power consumption of the overall node. While such a radical architecture cannot offer the reliable tuning of standard designs, it is shown that by using randomized signal processing techniques, a dense network of such nodes can achieve throughput linear in the number of channels available for communication. Moreover, the ratio of the achievable throughput of the untuned network to the throughput of a tuned network with perfect coordination is shown to be close to 1/e.
Towards a theory for video coding using distributed compression principles

This paper presents an information-theoretic study of video codecs that are based on the principle of source coding with side information at the decoder. In contrast to the classical Wyner-Ziv side-information source coding problem (1976), in this work we address the situation where the source and side-information are connected through a state of nature that is unknown to both the encoder and the decoder. We dub this framework as source encoding with side-information under ambiguous state of nature (SEASON). Our objective is to compare the achievable rate-distortion (R/D) performance of conventional video codecs designed under the motion-compensated predictive coding (MCPC) framework and video codecs designed under the SEASON framework. Our analysis shows that under appropriate motion models and for Gaussian displaced frame difference (DFD) statistics, the R/D performance of a classical MCPC-based video codec is matched by that of our proposed SEASON-based video codec, with the hitter being characterized by the novel concept of moving the motion compensation task from the encoder to the decoder.
A simple algorithm for removing blocking artifacts in block-transform coded images

Despite their widespread popularity, the Joint Photographers Expert Group (JPEG) and Motion Pictures Expert Group (MPEG) compression standards can lead to noticeable "blocking" artifacts-artificial rectangular discontinuities in the decoded image. Powerful postprocessing algorithms have been developed to remove blocking artifacts without destroying key image information. However, all but the simplest algorithms can be too complex for real-time applications such as video and still image decoding. We introduce a fast, easy-to-implement algorithm that removes blockiness by performing a simple nonlinear smoothing of pixels. This approach significantly improves visual quality and achieves subjective and objective (PSNR) gains that are competitive with the best deblocking algorithms reported in the literature at much reduced computational complexity.
A Survey on Network Codes for Distributed Storage

Distributed storage systems often introduce redundancy to increase reliability. When coding is used, the repair problem arises: if a node storing encoded information fails, in order to maintain the same level of reliability we need to create encoded information at a new node. This amounts to a partial recovery of the code, whereas conventional erasure coding focuses on the complete recovery of the information from a subset of encoded packets. The consideration of the repair network traffic gives rise to new design challenges. Recently, network coding techniques have been instrumental in addressing these challenges, establishing that maintenance bandwidth can be reduced by orders of magnitude compared to standard erasure codes. This paper provides an overview of the research results on this topic.