Search

In order to overcome the challenges caused by flash memories and also to protect against errors related to reading information stored in DNA molecules in the shotgun sequencing method, the rank modulation is proposed. In the rank modulation framework, codewords are permutations. In this paper, we study the largest size $P(n, d)$ of permutation codes of length $n$, i.e., subsets of the set $S_n$ of all permutations on $\{1,\ldots, n\}$ with the minimum distance at least $d\in\{1,\ldots ,\binom{n}{2}\}$ under the Kendall $\tau$-metric. By presenting an algorithm and some theorems, we managed to improve the known lower and upper bounds for $P(n,d)$. In particular, we show that $P(n,d)=4$ for all $n\geq 6$ and $\frac{3}{5}\binom{n}{2}< d \leq \frac{2}{3} \binom{n}{2}$. Additionally, we prove that for any prime number $n$ and integer $r\leq \frac{n}{6}$, $ P(n,3)\leq (n-1)!-\dfrac{n-6r}{\sqrt{n^2-8rn+20r^2}}\sqrt{\dfrac{(n-1)!}{n(n-r)!}}. $ This result greatly improves the upper bound of $P(n,3)$ for all primes $n\geq 37$., Comment: 15 pages

Spatially coupled low-density parity-check (SC-LDPC) codes are a class of capacity approaching LDPC codes with low message recovery latency when a sliding window decoding is used. In this paper, we first present a new method for the construction of a class of SC-LDPC codes by the incidence matrices of a given non-negative integer matrix $E$, and then the relationship of 4-cycles between matrix $E$ and the corresponding SC-LDPC code are investigated. Finally, by defining a new class of integer finite sequences, called {\it good sequences}, for the first time, we give an explicit method for the construction of a class of 4-cycle free SC-LDPC codes that can achieve (in most cases) the minimum coupling width.

We first give two methods based on the representation theory of symmetric groups to study the largest size $P(n,d)$ of permutation codes of length $n$ i.e. subsets of the set $S_n$ all permutations on $\{1,\dots,n\}$ with the minimum distance (at least) $d$ under the Kendall $\tau$-metric. The first method is an integer programming problem obtained from the transitive actions of $S_n$. The second method can be applied to refute the existence of perfect codes in $S_n$.\\ Here we reduce the known upper bound $(n-1)!-1$ for $P(n,3)$ to $(n-1)!-\lceil\frac{n}{3}\rceil+2\leq (n-1)!-2$, whenever $n\geq 11$ is any prime number. If $n=6$, $7$, $11$, $13$, $14$, $15$, $17$, the known upper bound for $P(n,3)$ is decreased by $3,3,9,11,1,1,4$, respectively., Comment: arXiv admin note: substantial text overlap with arXiv:2206.10193

In this paper, we propose a novel estimator for pilot-aided orthogonal frequency division multiplexing (OFDM) channels in an additive Gaussian and impulsive perturbation environment. Due to sensor failure which might happen because of man-made noise, a number of measurements in high rate communication systems is often corrupted by impulsive noise. High power impulsive noise is generally an obstacle for OFDM systems as valuable information will be completely lost. To overcome this concern, an objective function based on a penalized atomic norm minimization (PANM) is provided in order to promote the sparsity of time dispersive channels and impulsive noise. The corresponding dual problem of the PANM is then converted to tractable semidefinite programming. It has shown that one can simultaneously estimate the time dispersive channels in a continuous dictionary and the location of impulsive noise using the dual problem. Several numerical experiments are carried out to evaluate the performance of the proposed estimator.

In this paper, we address the problem of recovering point sources from two dimensional low-pass measurements, which is known as super-resolution problem. This is the fundamental concern of many applications such as electronic imaging, optics, microscopy, and line spectral estimation. We assume that the point sources are located in the square $[0,1]^2$ with unknown locations and complex amplitudes. The only available information is low-pass Fourier measurements band-limited to integer square $[-f_c,f_c]^2$. The signal is estimated by minimizing Total Variation $(\mathrm{TV})$ norm, which leads to a convex optimization problem. It is shown that if the sources are separated by at least $1.68/f_c$, there exist a dual certificate that is sufficient for exact recovery.

We consider load balancing problem in a cache network consisting of storage-enabled servers forming a distributed content delivery scenario. Previously proposed load balancing solutions cannot perfectly balance out requests among servers, which is a critical issue in practical networks. Therefore, in this paper, we investigate a coded cache content placement where coded chunks of original files are stored in servers based on the files popularity distribution. In our scheme, upon each request arrival at the delivery phase, by dispatching enough coded chunks to the request origin from the nearest servers, the requested file can be decoded. Here, we show that if $n$ requests arrive randomly at $n$ servers, the proposed scheme results in the maximum load of $O(1)$ in the network. This result is shown to be valid under various assumptions for the underlying network topology. Our results should be compared to the maximum load of two baseline schemes, namely, nearest replica and power of two choices strategies, which are $\Theta(\log n)$ and $\Theta(\log \log n)$, respectively. This finding shows that using coding, results in a considerable load balancing performance improvement, without compromising communications cost performance. This is confirmed by performing extensive simulation results, in non-asymptotic regimes as well., Comment: The paper is 12 pages and contains 8 figures

In this paper, we consider compressive sensing (CS)-based recovery of delays and Doppler frequencies of targets in high resolution radars. We propose a novel sub-Nyquist sampling method in the Fourier domain based on difference sets (DS), called DS-sampling, to create dictionaries with highly incoherent atoms. The coherence of the dictionary reaches the Welch minimum bound if the DS-sampling is employed. This property let us to implement sub-Nyquist high resolution radars with minimum number of samples. We also develop a low complexity recovery method, based on structured CS and propose a new waveform, called difference set--frequency coded modulated (DS-FCM) waveform, to boost the recovery performance of the sub-Nyquist radar in noisy environments. The proposed method solves some of the common problems in many CS-based radars and overcome disadvantages of the conventional Nyquist processing, i.e. matched filtering in high resolution radar systems. The proposed method allows us to design sub-Nyquist radars, which require less than 2% of Nyquist samples and recover targets without resolution degradation in comparison to the conventional Nyquist processing., Comment: There is no clear definition for the proposed modified DF. - There are some problems with the DS-FCM waveform, like PAPR issues which should be discussed. - The performance of recovery algorithms in noisy setting needs a mathematical proof

Computing the cut-set bound in half-duplex relay networks is a challenging optimization problem, since it requires finding the cut-set optimal half-duplex schedule. This subproblem in general involves an exponential number of variables, since the number of ways to assign each node to either transmitter or receiver mode is exponential in the number of nodes. We present a general technique that takes advantage of specific structures in the topology of a given network and allows us to reduce the complexity of computing the half-duplex schedule that maximizes the cut-set bound (with i.i.d. input distribution). In certain classes of network topologies, our approach yields polynomial time algorithms. We use simulations to show running time improvements over alternative methods and compare the performance of various half-duplex scheduling approaches in different SNR regimes., Comment: Submitted to IEEE Transactions on Information Theory. Part of this work will be presented at ISIT 2013

When data traffic in a wireless network is bursty, small amounts of data sporadically become available for transmission, at times that are unknown at the receivers, and an extra amount of energy must be spent at the transmitters to overcome this lack of synchronization between the network nodes. In practice, pre-defined header sequences are used with the purpose of synchronizing the different network nodes. However, in networks where relays must be used for communication, the overhead required for synchronizing the entire network may be very significant. In this work, we study the fundamental limits of energy-efficient communication in an asynchronous diamond network with two relays. We formalize the notion of relay synchronization by saying that a relay is synchronized if the conditional entropy of the arrival time of the source message given the received signals at the relay is small. We show that the minimum energy-per-bit for bursty traffic in diamond networks is achieved with a coding scheme where each relay is either synchronized or not used at all. A consequence of this result is the derivation of a lower bound to the minimum energy-per-bit for bursty communication in diamond networks. This bound allows us to show that schemes that perform the tasks of synchronization and communication separately (i.e., with synchronization signals preceding the communication block) can achieve the minimum energy-per-bit to within a constant fraction that ranges from 2 in the synchronous case to 1 in the highly asynchronous regime., Comment: Several proofs were updated

A new communication scheme for Gaussian parallel relay networks based on superposition coding and partial decoding at the relays is presented. Some specific examples are proposed in which two codebook layers are superimposed. The first level codebook is constructed with symbols from a binary or ternary alphabet while the second level codebook is composed of codewords chosen with Gaussian symbols. The new communication scheme is a generalization of decode-and-forward, amplify-and-forward, and bursty-amplify-and-forward. The asymptotic low SNR regime is studied using achievable rates and minimum energy-per-bit as performance metrics. It is shown that the new scheme outperforms all previously known schemes for some channels and parameter ranges., Comment: Submitted to IEEE Transactions on Information Theory

The capacity or approximations to capacity of various single-source single-destination relay network models has been characterized in terms of the cut-set upper bound. In principle, a direct computation of this bound requires evaluating the cut capacity over exponentially many cuts. We show that the minimum cut capacity of a relay network under some special assumptions can be cast as a minimization of a submodular function, and as a result, can be computed efficiently. We use this result to show that the capacity, or an approximation to the capacity within a constant gap for the Gaussian, wireless erasure, and Avestimehr-Diggavi-Tse deterministic relay network models can be computed in polynomial time. We present some empirical results showing that computing constant-gap approximations to the capacity of Gaussian relay networks with around 300 nodes can be done in order of minutes. For Gaussian networks, cut-set capacities are also functions of the powers assigned to the nodes. We consider a family of power optimization problems and show that they can be solved in polynomial time. In particular, we show that the minimization of the sum of powers assigned to the nodes subject to a minimum rate constraint (measured in terms of cut-set bounds) can be computed in polynomial time. We propose an heuristic algorithm to solve this problem and measure its performance through simulations on random Gaussian networks. We observe that in the optimal allocations most of the power is assigned to a small subset of relays, which suggests that network simplification may be possible without excessive performance degradation., Comment: Submitted to IEEE Transactions on Information Theory

Let A be an M by N matrix (M < N) which is an instance of a real random Gaussian ensemble. In compressed sensing we are interested in finding the sparsest solution to the system of equations A x = y for a given y. In general, whenever the sparsity of x is smaller than half the dimension of y then with overwhelming probability over A the sparsest solution is unique and can be found by an exhaustive search over x with an exponential time complexity for any y. The recent work of Cand\'es, Donoho, and Tao shows that minimization of the L_1 norm of x subject to A x = y results in the sparsest solution provided the sparsity of x, say K, is smaller than a certain threshold for a given number of measurements. Specifically, if the dimension of y approaches the dimension of x, the sparsity of x should be K < 0.239 N. Here, we consider the case where x is d-block sparse, i.e., x consists of n = N / d blocks where each block is either a zero vector or a nonzero vector. Instead of L_1-norm relaxation, we consider the following relaxation min x \| X_1 \|_2 + \| X_2 \|_2 + ... + \| X_n \|_2, subject to A x = y where X_i = (x_{(i-1)d+1}, x_{(i-1)d+2}, ..., x_{i d}) for i = 1,2, ..., N. Our main result is that as n -> \infty, the minimization finds the sparsest solution to Ax = y, with overwhelming probability in A, for any x whose block sparsity is k/n < 1/2 - O(\epsilon), provided M/N > 1 - 1/d, and d = \Omega(\log(1/\epsilon)/\epsilon). The relaxation can be solved in polynomial time using semi-definite programming.