Search

The fundamental task of group testing is to recover a small distinguished subset of items from a large population while efficiently reducing the total number of tests (measurements). The key contribution of this paper is in adopting a new information-theoretic perspective on group testing problems. We formulate the group testing problem as a channel coding/decoding problem and derive a single-letter characterization for the total number of tests used to identify the defective set. Although the focus of this paper is primarily on group testing, our main result is generally applicable to other compressive sensing models. [ABSTRACT FROM AUTHOR]

After a general description of the Burrows–Wheeler transform and a brief survey of recent work on processing its output, the paper examines the coding of the zero-runs from the MTF recoding stage, an aspect with little prior treatment. It is concluded that the original scheme proposed by Wheeler is extremely efficient and unlikely to be much improved. The paper then proposes some new interpretations and uses of the Burrows–Wheeler transform, with new insights and approaches to lossless compression, perhaps including techniques from error correction. [Copyright &y& Elsevier]

Slepian and Wolf considered a coding system (called SW system) for coding the multiterminal (information) source. This paper extends the SW system and defines anew a system (called SWL system) where encoders are mutually links. The problem of determining the optimal error exponent in the admissible rate region has not been answered completely for the SW system. It is shown in this paper that this problem can completely be solved for the SWL system. It is shown also that the optimal exponent can be achieved by the universal code. It is shown further that even if the encoders are linked, the admissible rate region is not enlarged and the reliability of the information transmission is not improved when the transmission rate is outside the admissible rate region. It is interesting to note that those results correspond in a sense to those for the channel with feedback. [ABSTRACT FROM AUTHOR]

One way to find near-matches in large datasets is to use hash functions. In recent years locality-sensitive hash functions for various metrics have been given; for the Hamming metric projecting onto k bits is simple hash function that performs well. In this paper, we investigate alternatives to projection. For various parameters hash functions given by complete decoding algorithms for error-correcting codes work better, and asymptotically random codes perform better than projection. [ABSTRACT FROM AUTHOR]

Tardos has proposed a randomized fingerprinting code that is provably secure against collusion attacks. We revisit his scheme and show that it has significantly better performance than suggested in the original paper. First, we introduce variables in place of Tardos' hard-coded constants and we allow for an independent choice of the desired false positive (FP) and false negative (FN) error rates. Following through Tardos' proofs with these modifications, we show that the code length can be reduced by more than a factor of two in typical content distribution applications where high FN rates can be tolerated. Second, we study the statistical properties of the code. Under some reasonable assumptions, the accusation sums can be regarded as Gaussian-distributed stochastic variables. In this approximation, the desired error rates are achieved by a code length twice shorter than in the first approach. Overall, typical FP and FN error rates may be achieved with a code length approximately five times shorter than in the original construction. [ABSTRACT FROM AUTHOR]

There is a large literature devoted to the problem of finding an optimal (mm-cost) prefix-free code with an unequal letter-cost encoding alphabet of size. While there is no known polynomial time algorithm for solving it optimally, there are many good heuristics that all provide additive errors to optimal. The additive error in these algorithms usually depends linearly upon the largest encoding letter size. This paper was motivated by the problem of finding optimal codes when the encoding alphabet is infinite. Because the largest letter cost is infinite, the previous analyses could give infinite error bounds. We provide a new algorithm that works with infinite encoding alphabets. When restricted to the finite alphabet case, our algorithm often provides better error bounds than the best previous ones known. [ABSTRACT FROM AUTHOR]

In this paper, we study the performance of different graph-based error-correcting codes over Gilbert-Elliott (GE) channels. We propose a hybrid coding scheme in which each code bit is checked by both a parity-check code and a Hamming code. A hybrid code can be represented by a code-to-code graph, which can be used to optimize the code. Asymptotic minimum distance properties of the hybrid code are derived, and it is shown that the expected minimum distance of the hybrid code increases linearly with respect to the code length. Simulation results show that for a typical GE channel, hybrid codes can outperform regular low-density parity-check codes by more than an order of magnitude, in terms of bit-error rate. [ABSTRACT FROM AUTHOR]

Bose and Al-Bassam designed quasi-systematic single asymmetric error-correcting codes that are able to encode k information bits in a Systematic way, but cannot encode all k information words. However, "Consgtruction 1" of their paper does not provide an efficient way for computing the number of codewords. In this Correspondence, we derive a recursive relation based on generating functions in order to compute the maximum number of codewords in such codes. This recursion allows us to determine those numbers for large code lengths which may not be feasible otherwise. [ABSTRACT FROM AUTHOR]