Search

Fire codes are cyclic codes generated by the product of two polynomials: a binomial that characterizes the code’s guaranteed burst-correcting capability and an irreducible polynomial that characterizes the code length. However, the true burst-correcting capability of a Fire code may exceed its guaranteed burst-correcting capability, which can be thought of as the designed burst-correcting capability of the Fire code. The true burst-correcting capability of a Fire code depends on the irreducible polynomial used in code construction. In this paper, the maximum true burst-correcting capabilities of Fire codes are considered. Fire codes are classified based on three parameters: their designed burst-correcting capabilities, the least common multiple of the periods of the binomials, and the irreducible polynomials used in their constructions, and the ratios of the periods of primitive polynomials of the same degrees as the irreducible polynomials to the periods of the irreducible polynomials. It is shown that the maximum true burst-correcting capability of each class, which pertains to an infinite number of codes, can be determined by checking whether or not a finite number of incongruences have a solution. It is also shown that in each class, there is an infinite number of Fire codes, with increasing code lengths, that attain this maximum. The maximum true burst-correcting capabilities of several classes of Fire codes are determined. It is also shown that there are infinite sequences of irreducible polynomials that generate cyclic codes of rates approaching one and with burst-correcting capabilities that exceed any given number. [ABSTRACT FROM AUTHOR]

Frequency hopping sequences (FHSs) are employed to mitigate the interferences caused by the hits of frequencies in frequency hopping spread spectrum systems. In this paper, we present combinatorial constructions for FHS sets, including direct constructions by using cyclotomic classes, recursive constructions based on cyclic difference matrices, merging blocks, and discrete logarithm. By these constructions, a number of series of new FHS sets are then produced. These FHS sets are optimal with respect to the Peng–Fan bounds. [ABSTRACT FROM PUBLISHER]

This paper studies an almost-lossless source-channel coding scheme in which source messages are assigned to different classes and encoded with a channel code that depends on the class index. The code performance is analyzed by means of random-coding error exponents and validated by simulation of a low-complexity implementation using existing source and channel codes. While each class code can be seen as a concatenation of a source code and a channel code, the overall performance improves on that of separate source-channel coding and approaches that of joint source-channel coding when the number of classes increases. [ABSTRACT FROM PUBLISHER]

Bent functions can be classified into regular bent functions, weakly regular but not regular bent functions, and non-weakly regular bent functions. Regular and weakly regular bent functions always appear in pairs, since their duals are also bent functions. In general, this does not apply to non-weakly regular bent functions. However, the first known construction of non-weakly regular bent functions by Çeşmelioğlu et al. yields bent functions for which the dual is also bent. In this paper, the first construction of non-weakly regular bent functions for which the dual is not bent is presented. We call such functions non-dual-bent functions. Until now, only sporadic examples found via computer search were known. We then show that with the direct sum of bent functions and with the construction by Çeşmelioğlu et al., one can obtain infinitely many non-dual-bent functions once one example of a non-dual-bent function is known. [ABSTRACT FROM PUBLISHER]

Some physical effects that limit the reliability and performance of multilevel flash memories induce errors that have low magnitudes and are dominantly asymmetric. This motivated the application of the asymmetric limited magnitude error model in flash memory. In this paper, we present a new construction of quasi-perfect codes for such errors, and we also study the perfect codes with symmetric errors. Moreover, we show some nonexistence results on perfect codes for correcting single error of limited magnitude. [ABSTRACT FROM PUBLISHER]

Frequency-hopping sequences (FHSs) with favorable partial Hamming correlation properties have important applications in many synchronization and multiple-access systems. Strictly optimal FHSs are those FHSs with optimal partial Hamming autocorrelation irrespective of the correlation window length. In this paper, strictly optimal FHSs are investigated from a combinatorial approach. A generic connection between strictly optimal FHSs and disjoint cyclic perfect Mendelsohn difference families is established. By virtue of this connection, new strictly optimal FHSs are generated from some disjoint CPMDFs. These strictly optimal FHSs have new parameters not covered in the literature. [ABSTRACT FROM AUTHOR]

Discrete polymatroids are the multi-set analogue of matroids. In this paper, we explore the connections among linear network coding, linear index coding, and representable discrete polymatroids. We consider the vector linear solutions of networks over a field \mathbb Fq , with possibly different message and edge vector dimensions, which are referred to as linear fractional solutions. It is well known that a scalar linear solution over \mathbb Fq exists for a network if and only if the network is matroidal with respect to a matroid representable over \mathbb Fq . We define a discrete polymatroidal network and show that a linear fractional solution over a field \mathbb Fq exists for a network if and only if the network is discrete polymatroidal with respect to a discrete polymatroid representable over \mathbb Fq . An algorithm to construct the networks starting from certain class of discrete polymatroids is provided. Every representation over \mathbb Fq for the discrete polymatroid, results in a linear fractional solution over \mathbb Fq for the constructed network. Next, we consider the index coding problem, which involves a sender, which generates a set of messages X=\x1,x2,\dotso xk\ , and a set of receivers \mathcal R , which demand messages. A receiver R \in \mathcal R is specified by the tuple $(x,H)$ , where x \in X$ is the message demanded by R$ and is the side information possessed by $R$ . We first show that a linear solution to an index coding problem exists if and only if there exists a representable discrete polymatroid, satisfying certain conditions, which are determined by the index coding problem considered. Rouayheb et al. showed that the problem of finding a multi-linear representation for a matroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that matroid. The multi-linear representation of a matroid can be viewed as a special case of representation of an appropriate discrete polymatroid. We generalize the result of Rouayheb et al., by showing that the problem of finding a representation for a discrete polymatroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that discrete polymatroid. [ABSTRACT FROM PUBLISHER]

This paper studies multiuser random coding techniques for channel coding with a given (possibly suboptimal) decoding rule. For the mismatched discrete memoryless multiple-access channel, an error exponent is obtained that is tight with respect to the ensemble average, and positive within the interior of Lapidoth’s achievable rate region. This exponent proves the ensemble tightness of the exponent of Liu and Hughes in the case of maximum-likelihood decoding. An equivalent dual form of Lapidoth’s achievable rate region is given, and the latter is shown to immediately extend to channels with infinite and continuous alphabets. In the setting of single-user mismatched decoding, similar analysis techniques are applied to a refined version of superposition coding, which is shown to achieve rates at least as high as standard superposition coding for any set of random-coding parameters. [ABSTRACT FROM PUBLISHER]

The focus of this paper is on the public communication required for generating a maximal-rate secret key (SK) within the multiterminal source model of Csiszár and Narayan. Building on the prior work of Tyagi for the two-terminal scenario, we derive a lower bound on the communication complexity, R \text {SK} , defined to be the minimum rate of public communication needed to generate a maximal-rate SK. It is well known that the minimum rate of communication for omniscience, denoted by R \text {CO} , is an upper bound on R \text {SK} . For the class of pairwise independent network (PIN) models defined on uniform hypergraphs, we show that a certain Type \mathcal S condition, which is verifiable in polynomial time, guarantees that our lower bound on R \text {SK} meets the R \text {CO} upper bound. Thus, the PIN models satisfying our condition are R \text {SK} -maximal, indicating that the upper bound R \text {SK} \le R \text {CO} holds with equality. This allows us to explicitly evaluate R \text {SK} for such PIN models. We also give several examples of PIN models that satisfy our Type \mathcal S condition. Finally, we prove that for an arbitrary multiterminal source model, a stricter version of our Type \mathcal S condition implies that communication from all terminals (omnivocality) is needed for establishing an SK of maximum rate. For three-terminal source models, the converse is also true: omnivocality is needed for generating a maximal-rate SK only if the strict Type \mathcal S condition is satisfied. However, for the source models with four or more terminals, counterexamples exist showing that the converse does not hold in general. [ABSTRACT FROM PUBLISHER]

In this paper, we develop efficient decoders for non-binary low-density parity-check codes using the alternating direction method of multipliers (ADMM). We apply ADMM to two decoding problems. The first problem is linear programming (LP) decoding. In order to develop an efficient algorithm, we focus on non-binary codes in fields of characteristic two. This allows us to transform each constraint in \mathbb F2^{m} to a set of constraints in \mathbb F2 that has a factor graph representation. Applying ADMM to the LP decoding problem results in two types of non-trivial sub-routines. The first type requires us to solve an unconstrained quadratic program. We solve this problem efficiently by leveraging new results obtained from studying the above factor graphs. The second type requires Euclidean projections onto polytopes that are studied in the literature. Such projections can be solved efficiently using off-the-shelf techniques, which scale linearly in the dimension of the vector to project. ADMM LP decoding scales linearly with block length, linearly with check degree, and quadratically with field size. The second problem we consider is a penalized LP decoding problem. This problem is obtained by incorporating a penalty term into the LP decoding objective. The purpose of the penalty term is to make non-integer solutions (pseudocodewords) more expensive and hence to improve decoding performance. The ADMM algorithm for the penalized LP problem requires Euclidean projection onto a polytope formed by embedding the constraints specified by the non-binary single parity-check code, which can be solved by applying the ADMM technique to the resulting quadratic program. Empirically, this decoder achieves a much reduced error rate than LP decoding at low signal-to-noise ratios. [ABSTRACT FROM AUTHOR]

Frequency hopping sequences (FHSs) with favorable partial Hamming correlation properties have important applications in many synchronization and multiple-access systems. In this paper, we investigate constructions of FHSs and FHS sets with optimal partial Hamming correlation. We first establish a correspondence between FHS sets with optimal partial Hamming correlation and multiple partition-type balanced nested cyclic difference packings with a special property. By virtue of this correspondence, some FHSs and FHS sets with optimal partial Hamming correlation are constructed from various combinatorial structures, such as cyclic difference packings and cyclic relative difference families. As a consequence, our constructions yield new FHSs and FHS sets with optimal partial Hamming correlation. [ABSTRACT FROM AUTHOR]

A key aspect of many resource allocation problems is the need for the resource controller to compute a function, such as the $\max $ or \mathop {\mathrm {arg\,max\kern 0pt}} , of the competing users’ metrics. Information must be exchanged between the competing users and the resource controller in order for this function to be computed. In many practical resource controllers, the competing users’ metrics are communicated to the resource controller, which then computes the desired extremization function. However, in this paper, it is shown that information rate savings can be obtained by recognizing that the controller only needs to determine the result of this extremization function. If the extremization function is to be computed losslessly, the rate savings are shown in most cases to be at most 2 b independent of the number of competing users. Motivated by the small savings in the lossless case, simple achievable schemes for both the lossy and interactive variants of this problem are considered. It is shown that both of these approaches have the potential to realize large rate savings, especially in the case where the number of competing users is large. For the lossy variant, it is shown that the proposed simple achievable schemes are in fact close to the fundamental limit given by the rate distortion function. [ABSTRACT FROM AUTHOR]

This paper investigates the linear network coding problem for erasure broadcast channel with user feedback. An innovative linear network code is shown to be uniformly optimal for the system. In general, determining the existence of innovative packets is proved to be NP-complete. When the finite field size is larger than the number of users, innovative packets always exist and the problem of finding an innovative encoding vector with smallest Hamming weight is considered. The corresponding decision problem is shown to be NP-complete. Optimal and approximate network coding algorithms for maximizing the sparsity of encoding vectors are designed. [ABSTRACT FROM AUTHOR]

In this paper, we discover that univariate form of a Niho bent function is a sum of functions having the form of a Leander–Kholosha bent function taken with particular coefficients from \mathbb F2^{n}^{*} for every term. We know that the Niho bent functions are related to o-polynomials. The power terms in the univariate Niho bent function can be derived by working, in a first step, on each monomial of the corresponding o-polynomial separately, and in a second step, adding them to obtain the global expression. This allows, knowing the monomials in an o-polynomial, to obtain the power terms of the polynomial representing corresponding bent function. However, the coefficients are not calculated explicitly. The explicit form is given for the bent functions obtained from quadratic and cubic o-polynomials. We also calculate the algebraic degree of any bent function in the Leander–Kholosha class. [ABSTRACT FROM AUTHOR]

Constacyclic codes which generalize the classical cyclic codes have played important roles in recent constructions of many new quantum maximum distance separable (MDS) codes. However, the mathematical mechanism may not have been fully understood. In this paper, we use pseudo-cyclic codes, which is a further generalization of constacyclic codes, to construct the quantum MDS codes. We can not only provide a unified explanation of many previous constructions, but also produce some new quantum MDS codes. [ABSTRACT FROM AUTHOR]

The relevance in a sampling theory of U -invariant subspaces of a Hilbert space \mathcal {H} , where U denotes a unitary operator on \mathcal H , is nowadays a recognized fact. Indeed, shift-invariant subspaces of L^2(\mathbb R) become a particular example; periodic extensions of finite signals also provide a remarkable example. As a consequence, the availability of an abstract $U$ -sampling theory becomes a useful tool to handle these problems. In this paper, we derive a sampling theory for finite dimensional multiple generated $U$ -invariant subspaces of a Hilbert space \mathcal {H} . As the involved samples are identified as frame coefficients in a suitable euclidean space, the relevant mathematical technique is that of the finite frame theory. Since finite frames are nothing but spanning sets of vectors, the used technique naturally meets matrix analysis. [ABSTRACT FROM AUTHOR]

Several convex formulation methods have been proposed previously for statistical estimation with structured sparsity as the prior. These methods often require a carefully tuned regularization parameter, often a cumbersome or heuristic exercise. Furthermore, the estimate that these methods produce might not belong to the desired sparsity model, albeit accurately approximating the true parameter. Therefore, greedy-type algorithms could often be more desirable in estimating structured-sparse parameters. So far, these greedy methods have mostly focused on linear statistical models. In this paper, we study the projected gradient descent with a non-convex structured-sparse parameter model as the constraint set. Should the cost function have a stable model-restricted Hessian, the algorithm produces an approximation for the desired minimizer. As an example, we elaborate on application of the main results to estimation in generalized linear models. [ABSTRACT FROM AUTHOR]

A likelihood encoder is studied in the context of lossy source compression. The analysis of the likelihood encoder is based on the soft-covering lemma. It is demonstrated that the use of a likelihood encoder together with the soft-covering lemma yields simple achievability proofs for classical source coding problems. The cases of the point-to-point rate-distortion function, the rate-distortion function with side information at the decoder (i.e., the Wyner–Ziv problem), and the multi-terminal source coding inner bound (i.e., the Berger–Tung problem) are examined in this paper. Furthermore, a non-asymptotic analysis is used for the point-to-point case to examine the upper bound on the excess distortion provided by this method. The likelihood encoder is also related to a recent alternative technique using the properties of random binning. [ABSTRACT FROM AUTHOR]

This paper builds on the variant of the function field sieve (FFS) algorithm for the medium prime case introduced by Joux and Lercier in 2006. We make several contributions. The first contribution uses a divisibility and smoothness technique and goes on to develop a sieving method based on the technique. This leads to significant practical efficiency improvements in the descent phase and also provides improvement to Joux’s pinpointing technique. The second contribution is a detailed analysis of the degree of freedom and the use of a walk technique in the descent phase of the algorithm. Such analysis shows that it is possible to compute discrete logarithms over certain fields, which are excluded by the earlier analyses performed by Joux and Lercier (2006) and Joux (2013). In concrete terms, we present computations of discrete logs for fields with 16 and 19-bit prime characteristic. We also provide concrete analysis of the effectiveness of the FFS algorithm for certain fields of characteristic ranging from 16 to 32-bit primes. The final contribution is to perform a complete asymptotic analysis of the FFS algorithm for fields \mathbb FQ with p=LQ(1/3,c) . This closes gaps and corrects errors in the analysis earlier performed by Joux–Lercier and Joux and also provides new insights into the asymptotic behavior of the algorithm. [ABSTRACT FROM AUTHOR]

This paper shows that the capacity region of the continuous-time Poisson broadcast channel is achieved via superposition coding for most channel parameter values. Interestingly, the channel in some subset of these parameter values does not belong to any of the existing classes of broadcast channels for which superposition coding is optimal (e.g., degraded, less noisy, and more capable). In particular, we introduce the notion of effectively less noisy broadcast channel and show that it implies less noisy but is not in general implied by more capable. For the rest of the channel parameter values, we show that there is a gap between Marton’s inner bound and the UV outer bound. [ABSTRACT FROM AUTHOR]

Motivated by the rank modulation scheme, a recent study by Sala and Dolecek explored the idea of constraint codes for permutations. The constraint studied by them is inherited by the inter-cell interference phenomenon in flash memories, where high-level cells can inadvertently increase the level of low-level cells. A permutation \sigma \in Sn satisfies the single-neighbor $k$ -constraint if \sigma (i+1)-\sigma (i)\leq k$ for all 1\leq i\leq n-1$ . In this paper, this model is extended into two constraints. A permutation k$ -constraint if for all 2 \leq i \leq n-1$ , \sigma (i)-\sigma (i-1)\leq k$ or \sigma (i \,\, + \,\, 1)-\sigma (i)\leq k$ , and it satisfies the asymmetric two-neighbor k$ -constraint if for all 2 \leq i \leq n-1$ , and the capacity of the second constraint is 1 regardless for any positive $k$ . We also extend our results and study the capacity of these two constraints combined with error-correcting codes in the Kendall $\tau $ -metric. [ABSTRACT FROM AUTHOR]

Subspace codes have received an increasing interest recently due to their application in error correction for random network coding. In particular, cyclic subspace codes are possible candidates for large codes with efficient encoding and decoding algorithms. In this paper, we consider such cyclic codes and provide constructions of optimal codes for which their codewords do not have full orbits. We further introduce a new way to represent subspace codes by a class of polynomials called subspace polynomials. We present some constructions of such codes, which are cyclic and analyze their parameters. [ABSTRACT FROM AUTHOR]

Burst errors are a type of distortion in many data communications and data storage channels. In this paper, we consider the list decodability of codes for single burst error case and phased-burst error case independently. Firstly, we analyze the list decodability of random codes, and we show that the burst list decoding radius and the rate of random codes achieve the Singleton bound and the Gilbert-Varshamov bound for single case and phased case, respectively. Second, we illustrate that cyclic codes and algebraic geometry codes are good burst list-decodable codes for single case and phased case, respectively. [ABSTRACT FROM AUTHOR]

The general approach in a noisy channel scalar quantizer design is an iterative descent algorithm, which guarantees only a locally optimal solution. While sufficient conditions under which the local optimum becomes a global optimum are known in the noiseless channel case, such sufficient conditions were not derived for the noisy counterpart. Moreover, efficient globally optimal design techniques for general discrete distributions in the noiseless case exist; however, they seem not to extend to the noisy scenario when a fixed index assignment is assumed. Recently, the design of noisy channel scalar quantizer with random index assignment (RIA) was proposed using a locally optimal iterative algorithm. In this paper, we derive sufficient conditions for the uniqueness of a local optimum, which, thus, guarantee the global optimality of the solution. These sufficient conditions are satisfied for a log-concave probability density function which is, additionally, symmetric around its mean. Furthermore, we show that, assuming an RIA, the globally optimal design for general discrete sources can also be carried out efficiently. [ABSTRACT FROM AUTHOR]

Due to recent applications to communications over powerlines, multilevel flash memories, and block ciphers, permutation codes have received a lot of attention from both coding and mathematical communities. One of the benchmarks for good permutation codes is the Gilbert–Varshamov bound. Although there have been several constructions of permutation codes, the Gilbert–Varshamov bound still remains to be the best asymptotical lower bound except for a recent improvement in the case of constant minimum distance. In this paper, we present an algebraic construction of permutation codes from rational function fields, and it turns out that, for a prime number $n$ of a symbol length, this class of permutation codes improves the Gilbert–Varshamov bound by a factor n$ asymptotically for a minimum distance d$ with . Furthermore, for a constant minimum distance $d$ , we improve the Gilbert–Varshamov bound by a factor $n$ as well as the recent one given by Gao et al. by a factor $n/\log n$ asymptotically for all sufficiently large $n$ . [ABSTRACT FROM PUBLISHER]

In 1973, Gallager proved that the random-coding bound is exponentially tight for the random code ensemble at all rates, even below expurgation. This result explained that the random-coding exponent does not achieve the expurgation exponent due to the properties of the random ensemble, irrespective of the utilized bounding technique. It has been conjectured that this same behavior holds true for a random ensemble of linear codes. This conjecture is proved in this paper. In addition, it is shown that this property extends to Poltyrev’s random-coding exponent for a random ensemble of lattices. [ABSTRACT FROM PUBLISHER]

In this paper, a forward decoding procedure is developed for the compress-and-forward (CF) relaying scheme. This procedure uses a layered framework and is based on exploiting a feature of the $N$ -to-1 mapping inherent in the underlying Wyner–Ziv binning. It is shown that exploiting this mapping enables the relaxation of the constraint on the rate of the relay codewords representing the bin indices. For the cooperative multimessage network, the proposed procedure achieves the same rate region as the short-message noisy network coding (SNNC) scheme. However, this procedure is more advantageous for other networks including the two networks presented herein. The first network is a relay chain one with two destinations, whereas the second network is a partially cooperative multimessage one with three destinations. In both networks, side information is available to a subset of the decoding nodes, but not to the rest of the nodes, and in both cases, the network benefits from the relaxation of the rate of the CF bin indices. This relaxation results in rate regions larger than those achieved by the conventional CF and SNNC. [ABSTRACT FROM PUBLISHER]

A q -ary code of length n , size M , and minimum distance d code. An (n,q^{k},n-k+1)_{q} code is called a maximum distance separable (MDS) code. In this paper, some MDS codes over small alphabets are classified. It is shown that every (k+d-1,q^{k},d)_{q} code with k\geq 3 , d \geq 3 , is equivalent to a linear code with the same parameters. This implies that the (6,5^4,3)5 code and the (n,7^{n-2},3)7 MDS codes for n\in \6,7,8\ are unique. The classification of one-error-correcting 8-ary MDS codes is also finished; there are 14, 8, 4, and 4 equivalence classes of (n,8^n-2,3)8 codes for $n=6,7,8$ , and 9, respectively. One of the equivalence classes of perfect (9,8^{7},3)_{8} codes corresponds to the Hamming code and the other three are nonlinear codes for which there exists no previously known construction. [ABSTRACT FROM PUBLISHER]

This paper investigates the capacity region of the three-receiver AWGN broadcast channel where the receivers: 1) have private-message requests and 2) may know some of the messages requested by other receivers as side information. We first classify all 64 possible side information configurations into eight groups, each consisting of eight members. We next construct transmission schemes, and derive new inner and outer bounds for the groups. This establishes the capacity region for 52 out of 64 possible side information configurations. For six groups (i.e., groups 1, 2, 3, 5, 6, and 8 in our terminology), we establish the capacity region for all their members, and show that it tightens both the best-known inner and outer bounds. For group 4, our inner and outer bounds tighten the best-known inner bound and/or outer bound for all the group members. Moreover, our bounds coincide at certain regions, which can be characterized by two thresholds. For group 7, our inner and outer bounds coincide for four members, and thereby establishing the capacity region. For the remaining four members, our bounds tighten both the best-known inner and outer bounds. [ABSTRACT FROM PUBLISHER]

In this paper, we extend two earlier works further in two directions and compute the weight distribution of these cyclic codes under more relaxed conditions. It is interesting to note that many cyclic codes in the family are optimal and have only a few non-zero weights. Besides using similar ideas, we carry out some subtle manipulation of certain exponential sums. [ABSTRACT FROM AUTHOR]

Quadratic residue codes are a well-known class of codes. In this paper, we consider the constructions of self-dual codes by higher power residues, especially fourth power residues. New infinite families of self-dual codes over GF(2), GF(3), GF(4), GF(8), and GF(9) are introduced. Some of them have better minimum weight than previously known codes. We also give general results related to the automorphism group of some of these codes. [ABSTRACT FROM PUBLISHER]

Since discovery of Goppa geometric codes, people have been asking the question: are there different constructions of block codes from algebraic curves that give the same parameters as Goppa geometric codes. Despite of great effort by researchers, no such constructions have been found so far. Although in literature, there are many constructions of block code from algebraic curves, most of them are quite different from the one by Goppa in nature and thus they have different parameters. Some of these constructions have the same parameters as Goppa geometric codes, however it was proved that these are essentially the same codes defined by Goppa. In this paper, we solve this question for the case where the characteristic of the ground field is 2, namely, we present a different construction of block codes from algebraic curves that give the same parameters as Goppa geometric codes for the characteristic 2 case. [ABSTRACT FROM PUBLISHER]

An m -ary block code, m=2,3,4,\ldots , of length n \!\in \! \mathbfI\!\mathbfI\mskip -7mu\mathbfN is called balanced if, and only if, every codeword is balanced; that is, the real sum of the codeword components, or weight, is equal to \left \lfloor (m-1)n/2 \right \rfloor . This paper presents efficient encoding schemes to m -ary balanced codes with parallel (hence, fast) decoding. In fact, the decoding time complexity is O(1) digit operations. These schemes are a generalization to the m -ary alphabet of Knuth’s complementation method with parallel decoding. Let indicate the number of m -ary words of length n and weight . For any m \!\in \! {\mathbf{I}}\!{\mathbf{I}}\mskip -7mu{\mathbf{N}} , m\geq 2 , a simple implementation of the method is given which uses r \!\in \! \mathbfI\!\mathbfI\mskip -7mu\mathbfN check digits to balance k\leq \\binomr \left \lfloor (m-1)r/2 \right \rfloor \vphantom {RRm-\{m\bmod {2}+[(m-1)k]\bmod 2\}\}/(m-1) information digits with an encoding time complexity of O(mk\log mk) digit operations. A refined implementation of the parallel decoding method is also given with r check digits and k\leq (m^{r}-1)/(m-1) information digits, where the encoding time complexity is O(k\sqrt {\log _{m}k})$ . Thus, the proposed codes are less redundant than the $m$ -ary balanced codes with parallel decoding found in the literature and yet maintain the same complexity. [ABSTRACT FROM AUTHOR]

In this paper, the difference between the redundancy of the optimal asymmetric/symmetric fix-free code, and that of the optimal prefix-free code is considered as the penalty of benefiting from the desired properties of fix-free codes. This penalty is studied from different perspectives. In particular, it is shown that the average penalty of asymmetric fix-free codes is less than 0.21 bit per symbol. Moreover, it is proved that when the source alphabet size is sufficiently large, for almost all sources, the penalty is less than or equal to 0.182 bit per symbol. Regarding symmetric fix-free codes, it is shown that the average penalty tends to infinity as the source alphabet size increases. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of increasing the robustness to bit errors for two description scalar quantizers. Our approach is to start with an m -diagonal index assignment and further apply a permutation to the indexes of each description to increase the minimum Hamming distance d_{\rm min} of the set of valid index pairs. In particular, we show how to construct linear permutation pairs achieving d_{\rm min}\geq 3$ , and establish a lower bound in terms of the description rate $R$ , for the highest value of $m$ for which such permutations exist. [ABSTRACT FROM AUTHOR]

In this paper, we design a new iterative low-complexity algorithm for computing the Walsh–Hadamard transform (WHT) of an N dimensional signal with a K -sparse WHT. We suppose that N is a power of two and K=O(N^\alpha) , scales sublinearly in N for some and a computational complexity O(K\log _{2}(K) \log _{2}({N}/{K})) . Moreover, the algorithm succeeds with a high probability approaching 1 for large dimension N . Our approach is mainly based on the subsampling (aliasing) property of the WHT, where by a carefully designed subsampling of the time-domain signal, a suitable aliasing pattern is induced in the transform domain. We treat the resulting aliasing patterns as parity-check constraints and represent them by a bipartite graph. We analyze the properties of the resulting bipartite graphs and borrow ideas from codes defined over sparse bipartite graphs to formulate the recovery of the nonzero spectral values as a peeling decoding algorithm for a specific sparse-graph code transmitted over a binary erasure channel. This enables us to use tools from coding theory (belief-propagation analysis) to characterize the asymptotic performance of our algorithm in the very sparse ( \alpha \in (0, 1/3] ) and the less sparse ( \alpha \in (1/3, 1) ) regime. Comprehensive simulation results are provided to assess the empirical performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper considers relay assisted transmission for multiuser networks when the relay has no access to the codebooks used by the transmitters. The relay is called oblivious for this reason. Of particular interest is the generalized compress-and-forward (GCF) strategy, where the destinations jointly decode the compression indices and the transmitted messages, and their optimality in this setting. The relay-to-destination links are assumed to be out-of-band with finite capacity. Two models are investigated: 1) the multiple access relay channel (MARC) and 2) the interference relay channel (IFRC). For the MARC with an oblivious relay, a new outerbound is derived and it is shown to be tight by means of achievability of the capacity region using GCF scheme. For the IFRC with an oblivious relay, a new strong interference condition is established, under which the capacity region is found by deriving a new outerbound and showing that it is achievable using GCF scheme. The result is further extended to establish the capacity region of M-user MARC with an oblivious relay, and multicast networks containing $M$ sources and $K$ destinations with an oblivious relay. [ABSTRACT FROM PUBLISHER]

In this paper, we study the probability of successful deception of an uncompressed biometric authentication system with side information at the adversary. It represents the scenario where the adversary may have correlated side information, e.g., a partial finger print or a DNA sequence of a relative of the legitimate user. We find the optimal exponent of the deception probability by proving both the achievability and the converse. Our proofs are based on a connection between the problem of deception with side information and the rate distortion problem with side information at both the encoder and the decoder. [ABSTRACT FROM PUBLISHER]

The problem of detecting a single anomalous process among a finite number $M$ of processes is considered. At each time, a subset of the processes can be observed, and the observations from each chosen process follow two different distributions, depending on whether the process is normal or abnormal. The objective is a sequential search strategy that minimizes the expected detection time subject to an error probability constraint. This problem can be considered as a special case of active hypothesis testing first considered by Chernoff where a randomized strategy, referred to as the Chernoff test, was proposed and shown to be asymptotically (as the error probability approaches zero) optimal. For the special case considered in this paper, we show that a simple deterministic test achieves asymptotic optimality and offers better performance in the finite regime. We further extend the problem to the case where multiple anomalous processes are present. In particular, we examine the case where only an upper bound on the number of anomalous processes is known. [ABSTRACT FROM PUBLISHER]

The study of Armstrong codes is motivated by the problem of understanding complexities of dependences in relational database systems, where attributes have bounded domains. A $(q,k,n)$ -Armstrong code is a $q$ -ary code of length $n$ with minimum Hamming distance $n-k+1$ , and for any set of $k-1$ coordinates, there exist two codewords that agree exactly there. Let $f(q,k)$ be the maximum $n$ for which such a code exists. In this paper, $f(q,3)=3q-1$ is determined for all $q\geq 5$ with three possible exceptions. This disproves a conjecture of Sali. Furthermore, we introduce generalized Armstrong codes for branching, or $(s,t)$ -dependences, construct several classes of optimal Armstrong codes, and establish lower bounds for the maximum length $n$ in this more general setting. [ABSTRACT FROM AUTHOR]

This paper studies sequential methods for recovery of sparse signals in high dimensions. When compared with fixed sample size procedures, in the sparse setting, sequential methods can result in a large reduction in the number of samples needed for reliable signal support recovery. Starting with a lower bound, we show any coordinate-wise sequential sampling procedure fails in the high dimensional limit provided the average number of measurements per dimension is less then \log (s)/D(P0||P1) , where s is the level of sparsity and D(P_{0}||P_{1}) is the Kullback–Leibler divergence between the underlying distributions. A series of sequential probability ratio tests, which require complete knowledge of the underlying distributions is shown to achieve this bound. Motivated by real-world experiments and recent work in adaptive sensing, we introduce a simple procedure termed sequential thresholding, which can be implemented when the underlying testing problem satisfies a monotone likelihood ratio assumption. Sequential thresholding guarantees exact support recovery provided the average number of measurements per dimension grows faster than \log (s)/D(P0||P1) , achieving the lower bound. For comparison, we show any nonsequential procedure fails provided the number of measurements grows at a rate less than \log (n)/D(P_{1}||P_{0})$ , where $n$ is the total dimension of the problem. [ABSTRACT FROM AUTHOR]

Snake-in-the-box code is a Gray code, which is capable of detecting a single error. Gray codes are important in the context of the rank modulation scheme, which was suggested recently for representing information in flash memories. For a Gray code in this scheme, the codewords are permutations, two consecutive codewords are obtained using the push-to-the-top operation, and distance measure is defined on permutations. In this paper, the Kendall’s \(\tau \) -metric is used as the distance measure. We present a general method for constructing such Gray codes. We apply the method recursively to obtain a snake of length \(M_{2n+1}=((2n+1)(2n)-1)M_{2n-1}\) for permutations of \(S_{2n+1}\) , from a snake of length \(M_{2n-1}\) for permutations of \(S_{2n-1}\) . Thus, we have \(\lim \limits _{n\to \infty }{M_{2n+1}}/{S_{2n+1}}\approx 0.4338\) , improving on the previous known ratio of \(\lim \limits _{n\to \infty }{1}/\sqrt {{({\pi n})}}\) . Using the general method, we also present a direct construction. This direct construction is based on necklaces and it might yield snakes of length \({(2n+1)!}/{2} -2n\,+\,1\) for permutations of \(S_{2n+1}\) . The direct construction was applied successfully for \(S_{7}\) and \(S_{9}\) , and hence \(\lim \limits _{n\to \infty } {M_{2n+1}}/{S_{2n+1}}\approx 0.4743\) . [ABSTRACT FROM PUBLISHER]

Write-once memory (WOM) is a storage medium with memory elements, called cells, which can take on \(q\) levels. Each cell is initially in level 0 and can only increase its level. A \(t\) -write WOM code is a coding scheme, which allows one to store \(t\) messages to the WOM such that on consecutive writes every cell’s level does not decrease. The sum-rate of the WOM code, which is the ratio between the total amount of information written in the \(t\) writes and number of memory cells, is bounded by \(\log (t+1)\) . Our main contribution in this paper is a construction of binary three-write WOM codes with sum-rate approaching 1.885 for sufficiently large number of cells, whereas the upper bound is 2. This improves upon a recent construction of sum-rate 1.809. A key ingredient in our construction is a recent capacity achieving construction of two-write WOM codes, which uses the so-called Wozencraft ensemble of linear codes. In our construction, we encode information in the first and second write in a way that leaves a large number (roughly half) of the cells nonprogrammed. This allows us to use the above two-write construction in order to invoke a third write to the memory. We also give specific constructions of nonbinary two-write WOM codes and multiple writes, which give better sum-rate than the currently best known ones. In the construction of these codes, we build upon previous nonbinary constructions and show how tools such symbols relabeling can help in achieving high sum-rates. [ABSTRACT FROM PUBLISHER]

The problem of simultaneously generating a secret key (SK) and private key (PK) pair among three terminals via public discussion is investigated. In this problem, each terminal observes a component of correlated sources. All three terminals are required to generate the common SK to be concealed from an eavesdropper that has access to the public discussion, while two designated terminals are required to generate an extra PK to be concealed from both the eavesdropper and the remaining terminal. An outer bound on the SK-PK capacity region was established by Ye and Narayan, and was shown to be achievable for a special case. In this paper, the SK-PK capacity region is established in general by developing schemes to achieve the outer bound for the remaining two cases. The main technique lies in the novel design of a random binning-joint decoding scheme that achieves the existing outer bound. [ABSTRACT FROM AUTHOR]

Multimedia fingerprinting is an effective technique to trace the sources of pirate copies of copyrighted multimedia contents. Separable codes were introduced to detect colluders taking part in the averaging attack, which is the most feasible approach to perform a collusion attack. In this paper, we provide some improved bounds for the size of separable codes. Using a combinatorial technique named grouping coordinates, we have greatly reduced the upper bound. On the other hand, we also provide some lower bounds for the size of separable codes by both probabilistic and deterministic construction methods. In particular, \( \overline {2}\) -separable codes with asymptotically optimal rate are obtained by the deletion method. [ABSTRACT FROM AUTHOR]

In this paper, we study the capacity/entropy region of finite, directed, acyclic, multiple-sources, and multiple-sinks network by means of group theory and entropy vectors coming from groups. There is a one-to-one correspondence between the entropy vector of a collection of \(n\) random variables and a certain group-characterizable vector obtained from a finite group and \(n\) of its subgroups. We are looking at nilpotent group characterizable entropy vectors and show that they are all also abelian group characterizable, and hence they satisfy the Ingleton inequality. It is known that not all entropic vectors can be obtained from abelian groups, so our result implies that to get more exotic entropic vectors, one has to go at least to soluble groups or larger nilpotency classes. The result also implies that Ingleton inequality is satisfied by nilpotent groups of bounded class, depending on the order of the group. [ABSTRACT FROM AUTHOR]