For a directed graphGwith edge set {1, 2, . . . ,k}, a feasible permutations forGis a permutation π on {1, 2, . . . ,k} such that there exists an injective weight functionp: {1, 2, . . . ,k} → Z+for which the sum of the weights of all incoming edges equals the sum of the weights of all outgoing edges at every vertex ofG, provided that ifp(i1)p(i2)p(ik), then π(it) =tfor everyt∈ {1, . . . ,k}. In this paper, we study the number of feasible permutations (denoted byFq,ℓ) for the De Bruijn graphGq,ℓ−1, whereq> 2 is the size of the alphabet. In the caseq= 4, the corresponding De Bruijn graph is used in DNA data storage. To enumerate these feasible permutations, we establish a connection between feasible permutations and regions in a special hyperplane arrangement, denoted byA. Using Zaslavsky’s formula, we present some numerical results and obtain the exact number ofF3,2andF4,2. Since the formula becomes complicated for larger values ofqand ℓ, we concentrate on the case ℓ = 2 and then by counting the regions in a hyperplane sub-arrangement ofA, we provide a lower bound onFq,2. We compare our bound with the latest lower bound onFq,2and show that our bound is Ω(q3J(q)) while the previous one is Ω(q2J(q)), whereJ(q)= (q2−2q+1)!(q2)!/(q2−q)!.

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 method has been 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 Sn of all permutations on {1, ..., n} with the minimum distance at least d ∈ {1, ..., (n/2)} under the Kendall τ-metric. By presenting an algorithm and two theorems, we improve the known lower and upper bounds for P(n, d). In particular, we show that P(n, d) = 4 for all n ≥ 6 and 3/5 (n/2) < d ≤ 2/3 (n/2). Additionally, we prove that for any prime number n and integer r ≤ n/6, P(n, 3) ≤ (n − 1)! − n − 6r/√n2 − 8rn + 20r2 √(n − 1)!/n(n − r)!. This result greatly improves the upper bound of P(n, 3) for all primes n ≥ 37.

In traffic sign recognition tasks, recognition of road signs by observing synthetic reference images is a human-like ability that can be performed by one-shot learning algorithms. One-shot object recognition is a challenging task for deep neural networks in which a deep model classifies query examples based on support images. It becomes more difficult when there is a domain shift between support and query samples. The generalization of a deep model on an unknown domain with different distributions is another problematic task in on-shot recognition. This work introduces a novel deep network named SeqNet to overcome the aforementioned problems. To the best of our knowledge, this work outperforms all state-of-the-art models in one-shot traffic sign recognition and one-shot logo identification by superior results. Our proposed SeqNet model generalizes to unseen domains without further model fine-tuning on the test data. Also, we show how using transferred knowledge from an irrelevant but large domain could reduce the network parameters that result in model size reduction. By utilizing the power of transferred knowledge from a large deep model the SeqNet becomes smaller and has about 6X fewer parameters than its competitors. The smaller size of the SeqNet architecture enables it to be used in resource-constrained devices in many applications such as smart vehicles. The experimental results depict that our proposed SeqNet performance is ameliorated by large margins, with up to 20% accuracy for one-shot classification and 30% area under the curve (AUC) for image retrieval tasks.

Abstract In this paper, two‐hop parallel N ‐relay networks are considered and the diversity‐multiplexing tradeoff (DMT) is derived over Gamma‐Gamma free‐space optical (FSO) channels with identical average received signal to noise rations in all links. In the derivations, both local and global channel state information (CSI) are investigated. In the local CSI case, the node only knows its incoming link conditions, while in the global CSI case, the nodes are aware of all the CSIs in the network. The listening and transmitting times at the relays as variables in the DMT derivation are further considered which are later used to optimize the performance of the network. It is demonstrated that the optimal DMT is obtained with the static quantize map and forward (SQMF) and dynamic quantize map and forward (DQMF) strategies for different ranges of the multiplexing gain. In addition, the optimal schedule of relays in the DQMF strategy is determined as a function of the local channel conditions in the relays.

In this paper, an empirical characteristic function (ECF) based estimator of the line-of-sight (LOS) power for the near user in an uplink non-orthogonal multiple access (NOMA) system with unknown impulsive noise is proposed. The channels between the users and the base station (BS) are assumed to have Rician fading. The performance of the proposed estimator is analytically evaluated, which demonstrates the asymptotic unbiasedness and consistency of the estimator. Furthermore, the approximate expression derived for the variance is confirmed through computer simulations. Numerical results show that the proposed estimator outperforms the previous estimator for the LOS power in the mixture of Gaussian and alpha-stable noise.

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 O(log n) and O(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.

Dirty paper coding (DPC) is a non‐linear transmit scheme in presence of known interference, which is capacity achieving. Unfortunately, the implementation complexity of DPC is usually prohibitive. A sub‐optimal yet practical method to implement DPC in inter‐symbol interference channels is Tomlinson–Harashima precoding (THP). However, THP is not applicable to the constant‐envelope phase shift keying (PSK) modulation. In this study, a modified Tomlinson–Harashima precoder is proposed to implement DPC for PSK modulation. The technique involves design of decision region at the receiver side and an algorithm to select the phase of transmitted symbol optimally at the transmitter side accordingly. Various patterns, namely, striped, checked, hexagonal, and radial are proposed and examined. Simulation results show that by using the proposed equaliser, the error floor is eliminated and significantly smaller bit‐error rate is achieved. Numerical and simulation results show that the striped pattern outperforms other decision region designs. Moreover, its implementation and computational complexities is almost the same as the Tomlinson–Harashima precoder.

The diversity-multiplexing trade-off (DMT) of half-duplex single-relay networks is computed analytically, where all the channels in the networks are assumed to be quasi-static flat-fading channels with independent Rayleigh distributions. We have computed DMT of dynamic quantize-map-and-forward (DQMF) strategy analytically, which has the optimal DMT for half-duplex single-relay networks with local channel state information. As a result, the optimal listening time of the relay in the DQMF strategy as a function of the source-relay channel realization can also be determined using our solution.

Computing optimal half-duplex schedules in Gaussian relay networks is a challenging problem due to the lack of an exact capacity characterization and the large number of transmit-receive configurations that must be considered. We approach the problem using a constant-gap capacity approximation based on the cut-set bound with independent encoding at the nodes. We formulate an optimization problem to obtain the cut-set optimal half-duplex schedule and find that it is hard to solve in general. This is because it 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 this problem. In certain classes of network topologies, our approach yields polynomial time algorithms for finding half-duplex schedules that achieve capacity within a constant gap. 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.

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 a 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 the polynomial time. We propose a 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.

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, predefined 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 paper, 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.

Computing the cut-set bound in half-duplex (HD) relay networks is a challenging optimization problem that involves an exponential number of variables and constraints (exponential in the number of nodes in the network). We present a general technique for efficiently computing the HD schedule that maximizes the cut-set bound (with i.i.d. input distribution) in layered Gaussian relay networks. We use simulations to show running time improvements over alternative methods and compare the performance of various HD scheduling approaches in different SNR regimes.

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-signal-to-noise-ratio 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.

A new communication scheme for Gaussian diamond relay networks based on superposition coding and partial decoding at the relays is presented. A first level codebook is constructed with symbols chosen from a binary alphabet while a second level codebook is composed of codewords chosen with Gaussian symbols. The relays partially decode the message to identify when to amplify the incoming signals. The new communication scheme is a generalization of decode-and-forward, amplify-and-forward, and bursty-amplify-and-forward. The achievable rates are studied in the asymptotic low SNR regime. It is shown that the new scheme outperforms all previously known schemes for some channels and parameter ranges.

Very often, constrained coding schemes impose nonlinear constraints on arrays and therefore it is usually nontrivial to determine how many arrays satisfy the given constraints. In this paper we show that there are non-trivial constrained coding scenarios where the number of constrained arrays can be estimated to a surprisingly high accuracy with the help of the sum-product algorithm, despite the fact that the underlying factor graphs have many short cycles, and we investigate the reasons why this is the case. These findings open up interesting possibilities for determining the number of constrained arrays also for scenarios where other counting and bounding techniques are not readily available.

When data traffic in a wireless network is bursty, small amounts of data sporadically become available for transmission, and the energy cost associated with synchronizing the network nodes prior to each communication block is not negligible. Therefore, designing energy-efficient communication schemes for such asynchronous scenarios is of particular importance. In this paper, we show that, for symmetric diamond networks, by performing the tasks of synchronization and communication separately, it is possible to achieve the minimum energy-per-bit to within a factor that ranges from 2 in the synchronous case to 1 in the highly asynchronous regime.

Let ${\mathcal{A}}_n$ be the set of all $n \times n$ binary matrices in which the number of $1$'s in each row and column is at most $n/2$. We show that $|{\mathcal{A}}_n| = 2^{n^2 - \rho n + \delta \sqrt{n}} \cdot n^{O(1)}$, for a constant $\rho \approx 1.42515$, and $\delta = \delta(n) \approx 1.46016$ for even $n$ and $0$ otherwise.

Consider the set Anof all n×n binary matrices in which the number of 1's in each row and column is at most n/2. We show that the redundancy, n2- log2|An|, of this set equals ρn + o(n), for a constant ρ ≈ 1.42515.

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.

We consider the deterministic construction of a measurement matrix and a recovery method for signals that are block sparse. A signal that has dimension N = nd, which consists of n blocks of size d, is called (s, d)-block sparse if only s blocks out of n are nonzero. We construct an explicit linear mapping Phi that maps the (s, d) -block sparse signal to a measurement vector of dimension M, where s - dd/d+1) - o(1). We show that if the (s,d)- block sparse signal is chosen uniformly at random then the signal can almost surely be reconstructed from the measurement vector in O(N3) computations.

DNA microarrays comprising tens of thousands of probe spots are currently being employed to test multitude of targets in a single experiment. Typically, each microarray spot contains a large number of copies of a single probe designed to capture a single target, and hence collects only a single data point. This is a wasteful use of the sensing resources in comparative DNA microarray experiments, where a test sample is measured relative to a reference sample. Since only a small fraction of the total number of genes represented by the two samples is differentially expressed, a vast number of probe spots will not provide any useful information. To this end we consider an alternative design, the so-called compressed microarrays, wherein each spot is a composite of several different probes and the total number of spots is potentially much smaller than the number of targets being tested. Fewer spots directly translates to significantly lower costs due to cheaper array manufacturing, simpler image acquisition and processing, and smaller amount of genomic material needed for experiments. To recover signals from compressed microarray measurements, we leverage ideas from compressive sampling. Moreover, we propose an algorithm which has far less computational complexity than the widely-used linear-programming-based methods, and can also recover signals with less sparsity.

The multivariate interpolation decoding (MID) algorithm for certain Reed-Solomon codes was recently introduced by Parvaresh and Vardy. The MID algorithm attempts to list-decode up to ntauMID= n (1 -RM(M+1)/) errors, in a Reed-Solomon code of length n and rate R, using (M+1)-variate polynomial interpolation. This improves on the Guruswami-Sudan decoding radius of tauGS= 1 - radicR by a large margin, especially for high-rate codes. The problem is that successful decoding is not guaranteed: there are certain patterns of less than ntauMIDerrors which the MID algorithm fails to decode. Nevertheless, simulations show that the actual performance of the MID decoder is very close to what one would expect if all patterns of up to ntauMIDerrors were corrected. On the other hand, analysis of the failure probability for the MID algorithm is extremely difficult, and there were no analytic results so far to confirm this empirically observed behavior. In this work, we provide such analytic results: we present a detailed analysis of the probability of failure in the MID algorithm for the special case where M = 2 and the interpolation multiplicity is m = 1. In this case, the MID algorithm attempts to correct up to ntau2,1errors, where tau2,1= 1 -3radic6R2. We consider the situation where symbol values received from the channel at the erroneous positions are distributed uniformly at random (a version of the q-ary symmetric channel). We show that, with high probability, the performance of the MID algorithm is very close to the optimum in this case. Specifically, we prove that if the fraction of positions in error is at most tau2,1-O(R5/3), then the probability of failure in the MID algorithm is at most n-Omega(n). Thus the probability of failure is, indeed, negligible for large n in this case

We introduce a new family of error-correcting codes that have a polynomial-time encoder and a polynomial-time list-decoder, correcting a fraction of adversarial errors up to /spl tau//sub M/ = 1 - /sup M+1//spl radic/(M/sup M/R/sup M/) where R is the rate of the code and M /spl ges/ 1 is an arbitrary integer parameter. This makes it possible to decode beyond the Guruswami-Sudan radius of 1 /spl radic/R for all rates less than 1/16. Stated another way, for any /spl epsiv/ > 0, we can list-decode in polynomial time a fraction of errors up to 1 - /spl epsiv/ with a code of length n and rate /spl Omega/(/spl epsiv//log(1//spl epsiv/)), defined over an alphabet of size n/sup M/ = n/sup O(log(1//spl epsiv/))/. Notably, this error-correction is achieved in the worst-case against adversarial errors: a probabilistic model for the error distribution is neither needed nor assumed. The best results so far for polynomial-time list-decoding of adversarial errors required a rate of O(/spl epsiv//sup 2/) to achieve the correction radius of 1 - /spl epsiv/. Our codes and list-decoders are based on two key ideas. The first is the transition from bivariate polynomial interpolation, pioneered by Sudan and Guruswami-Sudan [1999], to multivariate interpolation decoding. The second idea is to part ways with Reed-Solomon codes, for which numerous prior attempts at breaking the O(/spl epsiv//sup 2/) rate barrier in the worst-case were unsuccessful. Rather than devising a better list-decoder for Reed-Solomon codes, we devise better codes. Standard Reed-Solomon encoders view a message as a polynomial f(X) over a field F/sub q/, and produce the corresponding codeword by evaluating f(X) at n distinct elements of F/sub q/. Herein, given f(X), we first compute one or more related polynomials g/sub 1/(X), g/sub 2/(X), ..., g/sub M-1/(X) and produce the corresponding codeword by evaluating all these polynomials. Correlation between f(X) and g/sub i/(X), carefully designed into our encoder, then provides the additional information we need to recover the encoded message from the output of the multivariate interpolation process.

The main computational steps in algebraic soft-decoding and/or Sudan-type list-decoding of Reed-Solomon codes are interpolation and factorization. The interpolation consists of computing a bivariate polynomial Q(X,Y) that passes through a prescribed set of points with prescribed multiplicities. Using the iterative algorithm of Koetter (1996), this computation can be accomplished in time O(N2), where N is the number of linear equations satisfied by the coefficients of Q(X,Y). Here, we recast the iterative interpolation procedure of (R. Koetter, 1996) as a computation of the product of a certain chain of polynomial matrices. We then derive a dynamic-programming algorithm which optimizes the multiplication order in computing this matrix chain. The resulting optimization reduces the number of finite-field operations required to compute Q(X,Y) by a factor of about two