nils-herrmann/clean_scirepeval huggingface dataset:
Asynchronous and noncoherent neighbor discovery for the IoT using sparse-graph codes

In this paper, we design a fast and efficient energy-based and asynchronous neighbor discovery protocol for the Internet of Things (IoT). In our solution, we relax the assumption of frame-level synchronization. We formulate a novel asynchronous group testing scheme and apply it to the neighbor discovery problem. We then show that our proposed scheme is able to detect the set of K active neighbors1 among a network of n nodes with codeword length and decoding complexity of Θ(K log (K) log (n)). Finally, we provide extensive simulation results to verify our theoretical guarantees.
Coded computation for multicore setups

Consider a distributed computing setup consisting of a master node and n worker nodes, each equipped with p cores, and a function f (x) = g(f1(x), f2(x),…, fk(x)), where each fi can be computed independently of the rest. Assuming that the worker computational times have exponential tails, what is the minimum possible time for computing f? Can we use coding theory principles to speed up this distributed computation? In , it is shown that distributed computing of linear functions can be expedited by applying linear erasure codes. However, it is not clear if linear codes can speed up distributed computation of ‘nonlinear’ functions as well. To resolve this problem, we propose the use of sparse linear codes, exploiting the modern multicore processing architecture. We show that 1) our coding solution achieves the order optimal runtime, and 2) it is at least Θ(√log n) times faster than any uncoded schemes where the number of workers is n.
Efficient Algorithms for the Data Exchange Problem

In this paper, we study the data exchange problem, where a set of users is interested in gaining access to a common file, but where each has only partial knowledge about it as side-information. Assuming that the file is broken into packets, the side-information considered is in the form of linear combinations of the file packets. Given that the collective information of all the users is sufficient to allow recovery of the entire file, the goal is for each user to gain access to the file, while minimizing some communication cost. We assume that the users can communicate over a noiseless broadcast channel, and that the communication cost is a sum of each user's cost function over the number of bits it transmits. For instance, the communication cost could simply be the total number of bits that needs to be transmitted. In the most general case studied in this paper, each user can have any arbitrary convex cost function. We provide deterministic, polynomial-time algorithms (in the number of users and packets), which find an optimal communication scheme that minimizes the communication cost. To further lower the complexity, we also propose a simple randomized algorithm inspired by our deterministic algorithm, which is based on a random linear network-coding scheme.
Compression of cDNA and inkjet microarray images

Microarray image technology is a powerful tool for monitoring the expression of thousands of genes simultaneously. Each microarray experiment produces immense amounts of image data, and efficient storage and transmission requires compression that utilizes the microarray image's structure and unique analysis goals. We have developed a progressive compression scheme for microarray images which can be either lossy or lossless. Our scheme has a coded data structure that allows fast decoding and reprocessing of image subsets, and includes summary statistics and image segmentation information. Since visual fidelity is not the end goal for microarray images, we introduce a new measure of distortion for lossy compression: the sensitivity of microarray information extraction to compression loss. We find that a lossy compression ratio of 8:1 for cDNA microarrays minimally affects downstream processing. The average lossless compression ratio is 1.83:1 for cDNA images and 2.43:1 for inkjet images, comparable to state-of-the-art lossless schemas, yet with added flexibility and information.
Distributed video coding in wireless sensor networks

This paper addresses the important aspect of compressing and transmitting video signals generated by wireless broadband networks while heeding the architectural demands imposed by these networks in terms of energy constraints as well as the channel uncertainty related to the wireless communication medium. Driven by the need to develop light, robust, energy-efficient, and low delay video delivery schemes, a distributed video coding based framework dubbed PRISM is introduced. PRISM addresses the wireless video sensor network requirements far more effectively than current state-of-the-art standards like MPEG. This paper focuses on the case of a single video camera and use it as a platform to describe the theoretical principles and practical aspects underlying distributed video coding.
On functional duality in MIMO source and channel coding problems having one-sided collaboration

We address duality in a variety of multiple-input-multiple-output (MIMO) source and channel coding problems of interest under different scenarios of "one-sided" inter-terminal collaboration at either the transmitter or at the receiver, including certain cases of. duality between (i) broadcast channel coding and distributed source coding, and (ii) multi-access channel coding and multiple-descriptions source coding. Our notion of duality in this paper is in a functional sense, where the optimal encoder mapping for a MIMO source coding problem becomes identical to the optimal decoder mapping for the dual MIMO channel coding problem, and vice versa. For ease of illustration we give the formulation only for two-input-two-output systems, which can be easily extended to the MIMO case. We present the precise mathematical conditions under which these encoder-decoder mappings are swappable in the two dual MIMO problems, identifying the key roles played by the source distortion and channel cost measures respectively in the MIMO source and channel coding problems in capturing this duality.
Enhancing analog image transmission systems using digital side information: a new wavelet-based image coding paradigm

We address digital transmission for enhancing, in a backward compatible way, the quality of analog image transmission systems. We propose a practical algorithm that treats the problem as one of wavelet image compression with side information (available in the form of a noisy analog version of the image) present at the decoder. We propose a rate allocation technique to efficiently allocate the rate among the wavelet coefficients of the image. In typical instances of the problem, we get gain up to 2.5 dB over conventional methods that ignore the side information. Surprisingly, this is typically achieved by modifying a very small fraction of the wavelet coefficients (typically around 10-20%) of the conventional source coder. Extensions of our proposed image transmission framework to that of video transmission finds application in the upgrade of current analog television broadcast systems to digital TV.
On multivariate estimation by thresholding

Despite their simplicity, scalar threshold operators effectively remove additive white Gaussian noise from wavelet detail coefficients of many practical signals. This paper explores the use of multivariate estimators that are almost as simple as scalar threshold operators. Sendur and Selesnick (2002) have recently shown the effectiveness of joint threshold estimation of parent and child wavelet coefficients. This paper discusses analogous results in two situations. With a frame representation, a simple joint threshold estimator is derived and it is shown that its generalization is equivalent to a type of l/sub 1/-regularized denoising. Then, for the case where multiple independent noisy observations are available, the counter-intuitive results by Chang, Yu, and Vetterli (2000) on combining averaging and thresholding are explained as a fortuitous consequence of randomization.
The MDS Queue: Analysing the Latency Performance of Erasure Codes

In order to scale economically, data centers are increasingly evolving their data storage methods from simple data replication to more powerful erasure codes, which provide the same level of reliability as replication, but at a significantly lower storage cost. In particular, it is well known that maximum-distance-separable (MDS) codes, such as Reed–Solomon codes, can achieve a target reliability with the maximum storage efficiency. While the use of codes for providing improved reliability in archival storage systems, where data is less frequently accessed (or so-called “cold data”), is well understood, the role of codes in storing more frequently accessed and active “hot data”, where latency is the key metric, is less clear. In this paper, we study data storage systems based on MDS codes through the lens of queueing theory, and term the queueing system arising under codes as an “MDS queue.” We provide lower and upper bounds on the average job latency for both centralized and decentralized versions of MDS queues. We also provide extensive simulations to corroborate our analysis as well as obtain additional insights.
Asymptotic Interference Alignment for Optimal Repair of MDS Codes in Distributed Storage

The high repair bandwidth cost of (<i>n</i>,<i>k</i>) maximum distance separable (MDS) erasure codes has motivated a new class of codes that can reduce repair bandwidth over that of conventional MDS codes. In this paper, we address (<i>n</i>,<i>k</i>,<i>d</i>) exact repair MDS codes, which allow for any single failed node to be repaired exactly with access to any arbitrary set of <i>d</i> survivor nodes. We show the existence of exact repair MDS codes that achieve minimum repair bandwidth (matching the cut-set lower bound) for arbitrary admissible (<i>n</i>,<i>k</i>,<i>d</i>), i.e., <i>k</i> ≤ <i>d</i> ≤ <i>n</i>-1. Moreover, we extend our results to show the optimality of our codes for multiple-node failure scenarios in which an arbitrary set of <i>r</i> ≤ <i>n</i>-<i>k</i> failed nodes needs to repaired. Our approach is based on asymptotic interference alignment proposed by Cadambe and Jafar. As a byproduct, we also characterize the capacity of a class of multisource nonmulticast networks.
Video multicast over lossy channels based on distributed source coding

We present an algorithm for robust scalable video multicast based on distributed source coding techniques. Unlike prediction based coders, like MPEG, the proposed framework directly addresses the problem of drift due to packet losses. Building on the recently proposed PRISM video coding framework (R. Puri and K. Ramehandran, 2002), we show that substantial gains are possible for video multicast over lossy channels as compared to standard codecs, without a dramatic increase in encoder complexity as the number of streams increases.
Codes can reduce queueing delay in data centers

In this paper, we quantify how much codes can reduce the data retrieval latency in storage systems. By combining a simple linear code with a novel request scheduling algorithm, which we call Blocking-one Scheduling (BoS), we show analytically that it is possible to use codes to reduce data retrieval delay by up to 17% over currently popular replication-based strategies. Although in this work we focus on a simplified setting where the storage system stores a single content, the methodology developed can be applied to more general settings with multiple contents. The results also offer insightful guidance to the design of storage systems in data centers and content distribution networks.
A sparse-graph-coded filter bank approach to minimum-rate spectrum-blind sampling

Sampling of bandlimited signals whose frequency support is unknown is called spectrum-blind sampling. It has attracted considerable attention due to its potential for sampling much lower than the Nyquist rate. The minimum rate for spectrum-blind sampling has been established as twice the measure of the frequency support. We study this sampling problem and propose a novel sampling framework by leveraging tools from modern coding theory. Our approach is based on subsampling the outputs of a carefully designed sparse-graph-codedfilter bank. The key idea is to exploit, rather than avoid, the aliasing artifacts induced by subsampling, which introduces linear mixing of spectral components in the form of parity constraints for sparse-graph codes. Under the proposed sampling scheme, signal reconstruction becomes equivalent to the peeling decoding of sparse-graph codes in erasure channels. As a result, we can simultaneously approach the minimum sampling rate, while also having a computational cost that is linear in the number of samples. We support our theoretical findings through numerical experiments.
OFDMA Downlink Resource Allocation for Ergodic Capacity Maximization with Imperfect Channel Knowledge

In this paper, we derive an optimal resource allocation algorithm for ergodic weighted-sum capacity maximization in OFDMA systems assuming the availability of only partial (imperfect) CSI. Using a dual optimization framework, we show that the optimal power allocation is multi-level waterfilling based on the conditional expected value of the channel-to-noise ratio, and the optimal user is selected based on the maximum weighted conditional expected capacity penalized by the required power. The algorithm is shown to have O(MK) complexity for an OFDMA system with K used subcarriers and M active users, and achieves relative duality gaps of less than 10-5 (99.99999% optimal).
Minimum entropy segmentation applied to multi-spectral chromosome images

In the early 1990s, the state-of-the-art in commercial chromosome image acquisition was grayscale. Automated chromosome classification was based on the grayscale image and boundary information obtained during segmentation. Multi-spectral image acquisition was developed in 1990 and commercialized in the mid-1990s. One acquisition method, multiplex fluorescence in-situ hybridization (M-FISH), uses five color dyes. We propose a segmentation algorithm for M-FISH images that minimizes the entropy of classified pixels within possible chromosomes. This method is shown to correctly decompose even difficult clusters of touching and overlapping chromosomes. Finally, an example image is given to illustrate the algorithm.
Design of sparse filters for channel shortening

Channel shortening filters have been used in acoustics to reduce reverberation, in error control decoding to reduce complexity, and in communication systems to reduce inter-symbol interference. The cascade of a channel and a channel shortening filter would produce an overall impulse response that has more of the energy in the channel impulse response compacted into fewer adjacent samples. Once designed, channel shortening filters operate on a per-sample basis. In this paper, we evaluate sparse FIR filters, which use more design complexity and less per-sample processing complexity, for channel shortening. Our contributions include (1) proposing a new sparse FIR filter design method for channel shortening, and (2) evaluating design tradeoffs in energy compaction vs. implementation complexity for sparse and non-sparse FIR filters. Our simulation results for ADSL channels show that sparse designs could achieve the same energy compaction with half as many coefficients than non-sparse FIR filters for low filter orders.
Linear color-separable human visual system models for vector error diffusion halftoning

Image halftoning converts a high-resolution image to a low-resolution image, e.g., a 24-bit color image to a three-bit color image, for printing and display. Vector error diffusion captures correlation among color planes by using an error filter with matrix-valued coefficients. In optimizing vector error filters, Damera-Venkata and Evans (see  vol.10, p.1552-65, Oct. 2001) transform the error image into an opponent color space where Euclidean distance has perceptual meaning. This letter evaluates color spaces for vector error filter optimization. In order of increasing quality, the color spaces are YIQ, YUV, opponent (by Poirson and Wandell, 1993), and linearized CIELab (by Flohr, Kolpatzik, Balasubramanian, Carrara, Bouman, and Allebach, 1993).
SPCp1-06: Codebook Design for Noncoherent MIMO Communications Via Reflection Matrices

This paper studies the codebook design problem for noncoherent multiple input multiple output (MIMO) communications. Each codeword in the codebook is considered to be a point in a Grassmann manifold. In this paper, the codebook design is formulated as an inverse eigenvalue problem. A new algorithm using reflection matrices is proposed to obtain the optimal codebook for noncoherent block fading channels where the channel state information (CSI) is unknown at both the receiver and transmitter. The key contribution of this paper is that our algorithm is able to construct an optimal codebook via a sequence of reflection matrices.
Real-time sonar beamforming on workstations using process networks and POSIX threads

We present a scalable framework for real-time data-intensive systems on commodity multiprocessor workstations. The framework is an extension of the process network model, which captures parallelism, guarantees determinate execution, and executes to bounded memory. We implement the framework using lightweight POSIX threads and prototype a 4-GFLOP sonar beamformer on a 12-processor 336-MHz Sun Enterprise server. The beamformer scales nearly linearly from 1 to 12 processors.
Optimal Downlink OFDMA Resource Allocation with Linear Complexity to Maximize Ergodic Rates

OFDMA resource allocation assigns subcarriers and power, and possibly data rates, to each user. Previous research efforts to optimize OFDMA resource allocation with respect to communication performance have focused on formulations considering only instantaneous per-symbol rate maximization, and on solutions using suboptimal heuristic algorithms. This paper intends to fill gaps in the literature through two key contributions. First, we formulate continuous and discrete ergodic weighted sum rate maximization in OFDMA assuming the availability of perfect channel state information (CSI). Our formulations exploit time, frequency, and multi-user diversity, while enforcing various notions of fairness through weighting factors for each user. Second, we derive algorithms based on a dual optimization framework that solve the OFDMA ergodic rate maximization problem with O(MK) complexity per OFDMA symbol for M users and K subcarriers, while achieving data rates shown to be at least 99.9999% of the optimal rate in simulations based on realistic parameters. Hence, this paper attempts to demonstrate that OFDMA resource allocation problems are not computationally prohibitive to solve optimally, even when considering ergodic rates.
Low complexity subband analysis using quadrature mirror filters

In this article, a novel method of performing subband analysis of digital signals is proposed. Conventional subband decomposition algorithms typically use a binary tree filterbank structure comprised of halfband filters. Due to design limitations of finite length filters, conventional decomposition algorithms typically suffer from interference due to aliasing. While longer halfband filters may reduce aliasing, such filters also increase latency and implementation complexity. Our proposed algorithm uses a novel structure of quadrature mirror filters to ensure aliasing is present outside of the spectral region of interest. Simulation results indicate that, compared to conventional algorithms, the proposed algorithm 1) reduces interference from aliasing by over 30dB, 2) reduces signal processing latency, and 3) reduces implementation complexity.
Evaluating MMX technology using DSP and multimedia applications

Many current general purpose processors are using extensions to the instruction set architecture to enhance the performance of digital signal processing (DSP) and multimedia applications. In this paper, we evaluate the X86 architecture's multimedia extension (MMX) instruction set on a set of benchmarks. Our benchmark suite includes kernels (filtering, fast Fourier transforms, and vector arithmetic) and applications (JPEG compression, Doppler radar processing, imaging, and G.722 speech encoding). Each benchmark has at least one non-MMX version in C and an MMX version that makes calls to an MMX assembly library. The versions differ in the implementation of filtering, vector arithmetic, and other relevant kernels. The observed speed up for the MMX versions of the suite ranges from less than 1.0 to 6.1. In addition to quantifying the speedup, we perform detailed instruction level profiling using Intel's VTune profiling tool. Using VTune, we profile static and dynamic instructions, microarchitecture operations, and data references to isolate the specific reasons for speedup or lack thereof. This analysis allows one to understand which aspects of native signal processing instruction sets are most useful, the current limitations, and how they can be utilized most efficiently.
Optimum channel shortening for discrete multitone transceivers

We propose an optimum channel shortening method for discrete multitone (DMT) transceivers. The proposed method shortens a given channel to a desired length while maximizing the number of bits transmitted on a DMT symbol. The key to the optimum solution is the definition of the SNR in a subchannel using the equivalent signal, noise, and ISI paths in the system. Our simulation results show that the proposed method outperforms the best existing method with a 18% increase in the bit rate. We show that the maximum shortening SNR method is a special case of the proposed method and both methods are nearly equivalent when the input energy distribution is constant over all subchannels.
VLIW DSP vs. superscalar implementation of a baseline 11.263 video encoder

A Very Long Instruction Word (VLIW) processor and a superscalar processor can execute multiple instructions simultaneously. A VLIW processor depends on the compiler and programmer to find the parallelism in the instructions, whereas a superscaler processor determines the parallelism at runtime.  The superscalar speedup from one-way to four-way issue is 2.88:1, and from four-way to 256-way issue is 2.43:1. To reduce the execution time on the C6700, we write assembly routines for sum-of-absolute-difference, interpolation, and reconstruction, and place frequently used code and data into on-chip memory. We use TI's discrete cosine transform assembly routines. The hand optimized VLIW DSP implementation is 61/spl times/ faster than the C version compiled with level two optimization. Most of the improvement was due to the efficient placement of data and programs in memory. The hand optimized VLIW implementation is 14% faster than a 256-way superscalar implementation without hand optimizations.
Design tradeoffs in joint powerline and wireless transmission for smart grid communications

Providing reliable smart grid communication from customers to the local utility faces significant challenges due to noise, interference, frequency selectivity, path loss and fading. For transmission over narrowband powerline channels (3-500 kHz) and unlicensed wireless channels (902-928 MHz), this paper reviews previous approaches for (a) channel modeling and estimation and (b) noise/interference modeling and mitigation. Based on these approaches, the paper reviews methods for joint transmission over the powerline and wireless channels to improve reliability further. The key contribution of this paper is to explore design tradeoffs in communication performance vs. implementation complexity for joint transmission.