The aim of this work is to study the zero-error capacity of pure-state classical-quantum channels in the setting of list decoding. We provide an achievability bound for list-size two and a converse bound holding for every fixed list size. The two bounds coincide for channels whose pairwise absolute state overlaps form a positive semi-definite matrix. Finally, we discuss a remarkable peculiarity of the classical-quantum case: differently from the fully classical setting, the rate at which the sphere-packing bound diverges might not be achievable by zero-error list codes, even when we take the limit of fixed but arbitrarily large list size.

In this paper, we bound the rate of linear codes in Fnqwith the property that anyk≤qcodewords are all simultaneously distinct in at leastdkcoordinates. For the case of particular interestq=k= 3 we recover, with a simpler proof, state of the art results in the cased3= 1 and new bounds ford3> 1. We finally discuss some related open problems on the list-decoding zero-error capacity of discrete memoryless channels.

This paper presents new upper bounds on the rate of linear k-hash codes in$\mathbb{F}_{q}^{n}, q\geq k$, that is, codes with the property that any$k$distinct codewords are all simultaneously distinct in at least one coordinate.

In this paper, we study upper bounds on the minimum length of frameproof codes introduced by Boneh and Shaw [3] to protect copyrighted materials. A q-ary (k,n)-frameproof code of length t is a t×n matrix having entries in {0,1,…,q−1} and with the property that for any column c and any other k columns, there exists a row where the symbols of the k columns are all different from the corresponding symbol (in the same row) of the column c. In this paper, we show the existence of q-ary (k,n)-frameproof codes of length $t = O\left( {\frac{{{k^2}}}{q}\log n} \right)$ for q ≤ k, using the Lovász Local Lemma, and of length $t = O\left( {\frac{{{k^2}}}{{\log \left( {q/k} \right)}}\log \left( {n/k} \right)} \right)$ for q > k using the expurgation method. Remarkably, for the practical case of q ≤ k our findings give codes whose length almost matches the lower bound $\Omega \left( {\frac{{{k^2}}}{{q\log k\log n}}} \right)$ on the length of any q-ary (k,n)-frameproof code and, more importantly, allow us to derive an algorithm of complexity O(tn2) for the construction of such codes.

In this paper, we study bounds on the minimum length of ( k, n, d)-superimposed codes introduced by Agarwal et al. [1], in the context of Non-Adaptive Group Testing algorithms with runlength constraints. A ( k, n, d)-superimposed code of length t is a t × n binary matrix such that any two 1’s in each column are separated by a run of at least d 0’s, and such that for any column c and any other k−1 columns, there exists a row where c has 1 and all the remaining k−1 columns have 0. Agarwal et al. proved the existence of such codes with t = Θ( dk log( n/k) + k2log( n/k)). Here we investigate more in detail the coefficients in front of these two main terms as well as the role of lower order terms. We show that improvements can be obtained over the construction in [1] by using different constructions and by an appropriate exploitation of the Lovász Local Lemma in this context. Our findings also suggest O( nk) randomized Las Vegas algorithms for the construction of such codes. We also extend our results to Two-Stage Group Testing algorithms with runlength constraints.

We revise the proof of low-rate upper bounds on the reliability function of discrete memoryless channels for ordinary and list-decoding schemes, in particular Berlekamp and Blinovsky’s zero-rate bound, as well as Blahut’s bound for low rates. The available proofs of the zero-rate bound devised by Berlekamp and Blinovsky are somehow complicated in that they contain in one form or another some “non-standard” procedures or computations. Here we follow Blinovsky’s idea of using a Ramsey-theoretic result by Komlós, and we complement it with some missing steps to present a proof which is rigorous and easier to inspect. Furthermore, we show how these techniques can be used to fix an error that invalidated the proof of Blahut’s low-rate bound, which is here presented in an extended form for list decoding and for general channels.

We derive an upper bound on the reliability function of mismatched decoding for zero-rate codes. The bound is based on a result by Komlós that shows the existence of a subcode with certain symmetry properties. The bound is shown to coincide with the expurgated exponent at rate zero for a broad family of channel-decoding metric pairs.

For fixed integers$n$and$b\geq k$, let$A(b,k,n)$the largest size of a subset of$\{1,2,\ldots,b\}^{n}$such that, for any$k$distinct elements in the set, there is a coordinate where they all differ. Bounding$A(b,k,n)$is a problem of relevant interest in information theory and computer science, relating to the zero-error capacity with list decoding and to the study of$(b, k)$-hash families of functions. It is known that, for fixed$b$and$k$,$A(b,k,n)$grows exponentially in$n$. In this paper, we determine new exponential upper bounds for different values of$b$and$k$. A first bound on$A(b,k,n)$for general$b$and$k$was derived by Fredman and Komlós in the ’80s and improved for certain$b\neq k$by Körner and Marton and by Arikan. Only very recently better bounds were derived for general$b$and$k$by Guruswami and Riazanov, while stronger results for small values of$b=k$were obtained by Arikan, by Dalai, Guruswami and Radhakrishnan, and by Costa and Dalai. In this paper, we strengthen the bounds for some specific values of$b$and$k$. Our contribution is a new computational method for obtaining upper bounds on the values of a quadratic form defined over discrete probability distributions in arbitrary dimensions, which emerged as a central ingredient in recent works. The proposed method reduces an infinite-dimensional problem to a finite one, which we manage to further simplify by means of a series of optimality conditions.

We derive an upper bound on the reliability function of mismatched decoding for zero-rate codes. The bound is based on a result by Komlós that shows the existence of a subcode with certain symmetry properties. The bound is shown to coincide with the expurgated exponent at rate zero for a broad family of channel and decoding metric pairs. A full version of this paper is accessible at: https://arxiv.org/pdf/2101.10238.pdf

For fixed integers$b\geq k$, the problem of perfect$(b,\ k)$-hashing asks for the asymptotic growth of largest subsets of$\{1, 2, \ldots, b\}^{n}$such that for any$k$distinct elements in the set, there is a coordinate where they all differ. An important asymptotic upper bound for general, was derived by Fredman and Komlós in the ‘80s and improved for certain by Körner and Marton and by Arikan. Only very recently better bounds were derived for the general case by Guruswami and Riazanov, while stronger results for small values of were obtained by Arikan, by Dalai, Guruswami and Radhakrishnan and by Costa and Dalai. In this paper, we both show how some of the latter results extend to and further strengthen the bounds for some specific small values of and. The method we use, which depends on the reduction of an optimization problem to a finite number of cases, shows that further results might be obtained by refined arguments at the expense of higher complexity.

We present a revised proof of Berlekamp's zero-rate upper bound on the reliability function of discrete memoryless channels, in its extended form for list-decoding as first proved by Blinovsky. The available proofs are somehow uneasy in that they contain in one form or another some cumbersome "nonstandard" procedures or computations. Here we start from Blinovsky's ideas and complement them with some missing steps to present a proof which is entirely in the realm of standard information theoretic tools even for general list size.

Signal processing applications dealing with secure transmission are enjoying increasing attention lately. This paper provides some theoretical insights as well as a practical solution for transmitting a hash of an image to a central server to be compared with a reference image. The proposed solution employs a rigid image registration technique viewed in a distributed source coding perspective. In essence, it embodies a phase encoding framework to let the decoder estimate the transformation parameters using a very modest amount of information about the original image. The problem is first cast in an ideal setting and then it is solved in a realistic scenario, giving more prominence to low computational complexity in both the transmitter and receiver, minimal hash size, and hash security. Satisfactory experimental results are reported on a standard images set.

We prove a new upper bound on the size of codes C ⊆ {1, 2, 3, 4}nwith the property that every four distinct codewords in C have a coordinate where they all differ. Specifically, we provide a self-contained proof that such codes have size at most 26n/19+o(n), that is, rate bounded asymptotically by 6/19 ≤ 0.3158 (measured in bits). This improves the previous best upper bound of 0.3512 due to (Arikan 1994), which in turn improved the 0.375 bound that followed from general bounds for perfect hashing due to (Fredman and Komlós, 1984) and (Körner and Marton, 1988). Finally, using a combination of our approach with a simple idea which exploits powerful bounds on the minimum distance of codes in the Hamming space, we further improve the upper bound to 0.31477.

New lower and upper bounds on the reliability function of typewriter channels are given. Our lower bounds improve upon the (multiletter) expurgated bound of Gallager, furnishing a new and simple counterexample to a conjecture made in 1967 by Shannon, Gallager and Berlekamp on its tightness. The only other known counter example is due to Katsman, Tsfasman and Vladut who used algebraic-geometric codes on a q-ary symmetric channels, q ≥ 49. Here we prove, by introducing dependence between codewords of a random ensemble, that the conjecture is false even for a typewriter channel with q = 4 inputs. In the process, we also demonstrate that Lovász's proof of the capacity of the pentagon was implicitly contained (but unnoticed!) in the works of Jelinek and Gallager on the expurgated bound done at least ten years before Lovász. In the opposite direction, new upper bounds on the reliability function are derived for channels with an odd number of inputs by using an adaptation of Delsarte's linear programming bound. First, we derive a bound based on the minimum distance, which combines Lovász's construction for bounding the graph capacity with the McEliece-Rodemich-Rumsey-Welch construction for bounding the minimum distance of codes in the Hamming space. Then, for the particular case of cross-over probability 1/2, we derive an improved bound by also using the method of Kalai and Linial to study the spectrum distribution of codes.

We prove a new, improved upper bound on the size of codes C ⊆{1, 2, 3, 4}nwith the property that every four distinct codewords in C have a coordinate where they all differ. Specifically, we show that such a code has size at most 26n/19 +o(n), or equivalently has rate bounded by 6/19 ≤ 0.3158 (measured in bits). This improves the previous best upper bound of 0.3512 due to (Arikan 1994), which in turn improved the 0.375 bound that followed from general bounds for perfect hashing due to (Fredman and Komlos, 1984) and (Korner and Marton, 1988). The context for this problem is two-fold: zero-error list decoding capacity, where such codes give a way to communicate with no error on the “4/3 channel” when list-of-3 decoding is employed, and perfect hashing, where such codes give a perfect hash family of size n mapping C to {1, 2, 3, 4}.

The sphere packing bound, in the form given by Shannon, Gallager, and Berlekamp, was recently extended to classical-quantum channels, and it was shown that this creates a natural setting for combining probabilistic approaches with some combinatorial ones such as the Lovász theta function. In this paper, we extend the study to the case of constant-composition codes. We first extend the sphere packing bound for classical-quantum channels to this case, and we then show that the obtained result is related to a variation of the Lovász theta function studied by Marton. We then propose a further extension to the case of varying channels and codewords with a constant conditional composition given a particular sequence. This extension is finally applied to auxiliary channels to deduce a bound, which is useful in the low rate region and which can be interpreted as an extension of the Elias bound.

The capacity of a graph is defined as the rate of exponential growth of independent sets in the strong powers of the graph. In the strong power an edge connects two sequences if at each position their letters are equal or adjacent. We consider a variation of the problem where edges in the power graphs are removed between sequences which differ in more than a fraction δ of coordinates. The proposed generalization can be interpreted as the problem of determining the highest rate of zero undetected-error communication over a link with adversarial noise, where only a fraction δ of symbols can be perturbed and only some substitutions are allowed. We derive lower bounds on achievable rates by combining graph homomorphisms with a graph-theoretic generalization of the Gilbert-Varshamov bound. We then give an upper bound, based on Delsarte's linear programming approach, which combines Lovász' theta function with the construction used by McEliece et al. for bounding the minimum distance of codes in Hamming spaces.

We give new bounds on the reliability function of a typewriter channel with 5 inputs and crossover probability 1/2. The lower bound is more of theoretical than practical importance; it improves very marginally the expurgated bound, providing a counterexample to a conjecture on its tightness by Shannon, Gallager and Berlekamp which does not need the construction of algebraic-geometric codes previously used by Katsman, Tsfasman and Vlăduţ. The upper bound is derived by using an adaptation of the linear programming bound and it is essentially useful as a low-rate anchor for the straight line bound.

We present nonasymptotic achievability and converse bounds on the maximum coding rate (for a fixed average error probability and a fixed average blocklength) of variable-length full-feedback (VLF) and variable-length stop-feedback (VLSF) codes operating over a binary erasure channel (BEC). For the VLF setup, the achievability bound relies on a scheme that maps each message onto a variable-length Huffman codeword and then repeats each bit of the codeword until it is received correctly. The converse bound is inspired by the meta-converse framework by Polyanskiy, Poor, and Verdú (2010) and relies on binary sequential hypothesis testing. For the case of zero error probability, our achievability and converse bounds match. For the VLSF case, we provide achievability bounds that exploit the following feature of BEC: the decoder can assess the correctness of its estimate by verifying whether the chosen codeword is the only one that is compatible with the erasure pattern. One of these bounds is obtained by analyzing the performance of a variable-length extension of random linear fountain codes. The gap between the VLSF achievability and the VLF converse bound, when number of messages is small, is significant: 23% for 8 messages on a BEC with erasure probability 0.5. The absence of a tight VLSF converse bound does not allow us to assess whether this gap is fundamental.

In this paper, different strategies for the calculation of the Harte's Harmonic Change Detection Function (HCDF) are discussed. HCDFs can be used for detecting chord boundaries for Automatic Chord Estimation (ACE) tasks, where the chord transitions are identified as peaks in the HCDF. We show that different audio features and different novelty metric have significant impact on the overall accuracy results of a chord segmentation algorithm. Furthermore, we show that certain combination of audio features and novelty measures provide a significant improvement with respect to the current chord segmentation algorithms.

This paper presents an extension of the Elias bound on the minimum distance of codes for discrete alphabets with general, possibly infinite valued, distances. The bound is obtained by combining a previous extension of the Elias bound, introduced by Blahut, with an extension of a bound previously introduced by the author which builds upon ideas of Gallager, Lovász, and Marton. The result can in fact be interpreted as a unification of the Elias bound and of Lovász's bound on graph (or zero-error) capacity, both being recovered as particular cases of the one presented here. Previous extensions of the Elias bound by Berlekamp, Blahut, and Piret are shown to be included as particular cases of our bound. Applications to the reliability function are then discussed.

In this paper, we propose an upper bound on the minimum Bhattacharyya distance of codes for channels with a zero-error capacity. The bound is obtained by combining an extension of the Elias bound introduced by Blahut, with an extension of a bound previously introduced by the author, which builds upon ideas of Gallager, Lovász and Marton.

The sphere packing bound, in the form given by Shannon, Gallager and Berlekamp, was recently extended to classical-quantum channels, and it was shown that this creates a natural setting for combining probabilistic approaches with some combinatorial ones such as the Lovász theta function. In this paper, we extend the study to the case of constant composition codes. We first extend the sphere packing bound for classical-quantum channels to this case, and we then show that the obtained result is related to a variation of the Lovász theta function studied by Marton. We then propose a further extension to the case of varying channels and codewords with a constant conditional composition given a particular sequence. This extension is then applied to auxiliary channels to deduce a bound which can be interpreted as an extension of the Elias bound.

Lovász's bound to the capacity of a graph and the the sphere-packing bound to the probability of error in channel coding are given a unified presentation as information radii of the Csiszár type using the Rényi divergence in the classical-quantum setting. This brings together two results in coding theory that are usually considered as being of a very different nature, one being a “combinatorial” result and the other being “probabilistic”. In the context of quantum information theory, this difference disappears.

We propose a novel approach for bounding the probability of error of discrete memoryless channels with a zero-error capacity based on a combination of Lovász' and Gallager's ideas. The obtained bounds are expressed in terms of a function v(ρ), introduced here, that varies from the cut-off rate of the channel to the Lovázs theta function as ρ varies from 1 to ∞ and which is intimately related to Gallager's expurgated coefficient. The obtained bound to the reliability function, though loose in its present form, is finite for all rates larger than the Lovász theta function.

In this paper, lower bounds on error probability in coding for discrete classical and classical-quantum channels are studied. The contribution of the paper goes in two main directions: 1) extending classical bounds of Shannon to classical-quantum channels, and 2) proposing a new framework for lower bounding the probability of error of channels with a zero-error capacity in the low rate region. The relation between these two problems is revealed by showing that Lovász' bound on zero-error capacity emerges as a natural consequence of the sphere packing bound once we move to the more general context of classical-quantum channels. A variation of Lovász' bound is then derived to lower bound the probability of error in the low rate region by means of auxiliary channels. As a result of this study, connections between the Lovász theta function, the expurgated bound of Gallager, the cutoff rate of a classical channel, and the sphere packing bound for classical-quantum channels are established.

Video streaming with Peer-to-Peer (P2P) architectures and Scalable Video Coding (SVC) appears to be an interesting solution for an efficient streaming in the heterogeneous scenario of Internet applications. A key issue in such approach is the optimization of the bandwidth capacity of the P2P system. In this paper we propose an innovative approach for the network overlay optimization based on Integer Linear Programming. The proposed approach is particularly suitable in case of push-based solutions for video streaming using SVC with prioritized content. The simulation results show the flexibility of the proposed model when used to generate an overlay following different constraints and operational requirements. The usability and the computational complexity of the proposed method is also analyzed when the overlay includes an high number of peers.

In this paper, the Sphere-Packing-Bound of Fano, Shannon, Gallager and Berlekamp is extended to general classical-quantum channels. The obtained upper bound for the reliability function, for the case of pure-state channels, coincides at high rates with a lower bound derived by Burnashev and Holevo [1]. Thus, for pure state channels, the reliability function at high rates is now exactly determined. For the general case, the obtained upper bound expression at high rates was conjectured to represent also a lower bound to the reliability function, but a complete proof has not been obtained yet.

Let C(d) be the capacity of the binary deletion channel with deletion probability d. It was proved by Drinea and Mitzenmacher that, for all d, C(d)/(1 - d) ≥ 0.1185. Fertonani and Duman recently showed that lim supd→1C(d)/(1-d) ≤ 0.49. In this paper, it is proved that limd→1C(d)/(1 - d) exists and is equal to infdC(d)/(1-d). This result suggests the conjecture that the curve C(d) my be convex in the interval d ∈ [0, 1]. Furthermore, using currently known bounds for C(d), it leads to the upper bound limd→1C(d)/(1 - d) ≤ 0.4143.

In this paper, we propose a revisitation of the topic of unique decodability and of some fundamental theorems of lossless coding. It is widely believed that, for any discrete sourceX, every ldquouniquely decodablerdquo block code satisfiesE[l(X1,X2,...,Xn)]gesH(X1,X2,...,Xn) whereX1,X2,...,Xnare the firstnsymbols of the source,E[l(X1,X2,...,Xn)] is the expected length of the code for those symbols, andH(X1,X2,...,Xn) is their joint entropy. We show that, for certain sources with memory, the above inequality only holds when a limiting definition of ldquouniquely decodable coderdquo is considered. In particular, the above inequality is usually assumed to hold for any ldquopractical coderdquo due to a debatable application of McMillan's theorem to sources with memory. We thus propose a clarification of the topic, also providing an extended version of McMillan's theorem to be used for Markovian sources.

In this paper we consider the problem of image encoding with side information at the decoder, where the side information is an integer shifted version of the image at the encoder. The encoder is asked to send the shift of its own image with respect to the side information which is only available at the decoder. We propose a solution based on the encoding of the phase sign of the DFT coefficients, taken at exponentially spaced positions. We first introduce the method under ideal hypothesis, i.e. noiseless conditions without border effects, giving a theoretical foundation to the technique. Then, we consider the more realistic case of noisy images with border effects, showing the effectiveness of the proposed method.

The field of distributed video coding (DVC) theory has received a lot of attention in recent years and effective encoding techniques have been proposed. In the present work the framework of pixel domain Wyner-Ziv coding of video frames is considered, following the scheme proposed in A. Aaron et al. (2002). Some key frames are supposed to be available at the decoder while other frames are Wyner-Ziv encoded using turbo codes; at the decoder motion compensated interpolation between the key frames is performed in order to construct the side information for the Wyner-Ziv frame decoding. In this paper an improved model for the correlation noise between the side information frame and the original one is proposed. It is shown that modeling the nonstationary nature of the noise leads to substantial gain in the rate-distortion performance. Furthermore, by considering the memory of the noise, we show that some further gain can be obtained by placing an interleaver before the turbo codec so as to spread the correlation noise all over the frame

In this paper we consider the use of variable length non prefix-free codes for coding constrained sequences of symbols. We suppose to have a Markov source where some state transitions are impossible, i.e. the stochastic matrix associated with the Markov chain has some null entries. We show that classic Kraft inequality is not a necessary condition, in general, for unique decodability under the above hypothesis and we propose a relaxed necessary inequality condition. This allows, in some cases, the use of non prefix-free codes that can give very good performance, both in terms of compression and computational efficiency. Some considerations are made on the relation between the proposed approach and other existing coding paradigms

Efficient geometric algorithms are provided for the linear approximation of digital signals under the uniform norm. Given a set of n points (x/sub i/, y/sub i/), i=1..n, with x/sub i/<x/sub j/ if i

Many second generation image coding techniques have been studied in recent years. Most of these methods consider the l/sub 2/ norm of the error introduced in the coded image, while for the l/sub /spl infin// case only predictive or transform based methods were considered up to now, focusing on near-lossless coding. In this paper we present a first scheme for l/sub /spl infin// norm in the framework of second generation image coding. The image is adaptively segmented into rectangular regions of varying size leading to a binary tree decomposition. The grey levels of the pixels within every leaf are approximated by means of l/sub /spl infin// sub-optimal bilinear surfaces.