Search

This paper describes new, simple, recursive methods of construction for orientable sequences, i.e. periodic binary sequences in which any $n$ -tuple occurs at most once in a period in either direction. As has been previously described, such sequences have potential applications in automatic position-location systems, where the sequence is encoded onto a surface and a reader needs only examine $n$ consecutive encoded bits to determine its location and orientation on the surface. The only previously described method of construction (due to Dai et al.) is somewhat complex, whereas the new techniques are simple to both describe and implement. The methods of construction cover both the standard ‘infinite periodic’ case, and also the aperiodic, finite sequence, case. Both the new methods build on the Lempel homomorphism, first introduced as a means of recursively generating de Bruijn sequences. [ABSTRACT FROM AUTHOR]

In this paper, we present two new families of APN functions. The first family is in bivariate form $\big (x^{3}+xy^{2}+ y^{3}+xy, x^{5}+x^{4}y+y^{5}+xy+x^{2}y^{2} \big)\,\,\vphantom {_{\int _{\int }}}$ over ${\mathbb F}_{2^{m}}^{2}$. It is obtained by adding certain terms of the form $\sum _{i}(a_{i}x^{2^{i}}y^{2^{i}},b_{i}x^{2^{i}}y^{2^{i}})$ to a family of APN functions recently proposed by Gölo&gcaron;lu. The $\vphantom {_{\int _{\int }}}$ second family has the form $L(z)^{2^{m}+1}+vz^{2^{m}+1}$ over ${\mathbb F}_{{2^{3m}}}$ , which generalizes a family of APN functions by Bracken et al. from 2011. By calculating the $\Gamma $ -rank of the constructed APN functions over ${\mathbb F}_{2^{8}}$ and ${\mathbb F}_{2^{9}}$ , we demonstrate that the two families are CCZ-inequivalent to all known families. In addition, the two new families cover two known sporadic APN instances over ${\mathbb F}_{2^{8}}$ and ${\mathbb F}_{2^{9}}$ , which were found by Edel and Pott in 2009 and by Beierle and Leander in 2021, respectively. [ABSTRACT FROM AUTHOR]

In a recent work, Beierle, Brinkmann and Leander presented a recursive tree search for finding APN permutations with linear self-equivalences in small dimensions. In this paper, we describe how this search can be adapted to find many new instances of quadratic APN functions. In particular, we found 12,921 new quadratic APN functions in dimension eight, 35 new quadratic APN functions in dimension nine and five new quadratic APN functions in dimension ten up to CCZ-equivalence. Remarkably, two of the 35 new APN functions in dimension nine are APN permutations. Among the 8-bit APN functions, there are three extended Walsh spectra that do not correspond to any of the previously-known quadratic 8-bit APN functions and, surprisingly, there exist at least four CCZ-inequivalent 8-bit APN functions with linearity 27, i.e., the highest possible non-trivial linearity for quadratic functions in dimension eight. [ABSTRACT FROM AUTHOR]

We formulate and study the problem of ON-OFF privacy. ON-OFF privacy algorithms enable a user to continuously switch his privacy between ON and OFF. An obvious example is the incognito mode in internet browsers. But beyond internet browsing, ON-OFF privacy can be a desired feature in most online applications. The challenge is that the statistical correlation over time of a user’s online behavior can lead to leakage of information. We consider the setting in which a user is interested in retrieving the latest message generated by one of $N$ sources. The user’s privacy status can change between ON and OFF over time. When privacy is ON the user wants to hide his request. Moreover, since the user’s requests depend on personal attributes such as age, gender, and political views, they are typically correlated over time. As a consequence, the user cannot simply ignore privacy when privacy is OFF. We model the correlation between user’s requests by an $N$ state Markov chain. The goal is to design query schemes with optimal download rate, that preserve privacy in an ON-OFF privacy setting. In this paper, we present inner and outer bounds on the achievable download rate for $N$ sources. We also devise an efficient algorithm to construct an ON-OFF privacy scheme achieving the inner bound and prove its optimality in the case $N=2$ sources. For $N > 2$ , finding tighter outer bounds and efficient constructions of ON-OFF privacy schemes that would achieve them remains an open question. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the additivity phenomenon in the quantum dynamic capacity region of a quantum channel for trading the resources of classical communication, quantum communication, and entanglement. Understanding such an additivity property is important if we want to optimally use a quantum channel for general communication purposes. However, in a lot of cases, the channel one will be using only has an additive single or double resource capacity region, and it is largely unknown if this could lead to a strictly superadditive double or triple resource capacity region, respectively. For example, if a channel has additive classical and quantum capacities, can the classical-quantum capacity region be strictly superadditive? In this paper, we answer such questions affirmatively. We give proof-of-principle requirements for these channels to exist. In most cases, we can provide an explicit construction of these quantum channels. The existence of these superadditive phenomena is surprising in contrast to the result that the additivity of both classical-entanglement and classical-quantum capacity regions imply the additivity of the triple resource capacity region for a given channel. [ABSTRACT FROM AUTHOR]

The majority of works in distributed storage networks assume a simple network model with a collection of identical storage nodes with the same communication cost between the nodes. In this paper, we consider a realistic multi-rack distributed data storage network and present a code design framework for this model. Considering the cheaper data transmission within the racks, our code construction method is able to locally repair the nodes failure within the same rack by using only the survived nodes in the same rack. However, in the case of severe failure patterns when the information content of the survived nodes is not sufficient to repair the failures, other racks will participate in the repair process. By employing the criteria of our multi-rack storage code, we establish a linear programming bound on the size of the code in order to maximize the code rate. [ABSTRACT FROM AUTHOR]

Transmissions across asynchronous communication channels are subject to delay injection attacks, which can cause an arbitrary number of skews. That is, such attacks can cause an arbitrary number of transmitted signals to arrive after the first signal of the next transmission has arrived. The (common) assumption that despite the delays, all signals from the $i$ th transmission arrive at the decoder before any signal from the (i+2){\text{nd}} transmission arrives is called a no switch assumption. This paper presents a self-synchronizing, zero-latency, zero-error coding scheme that requires no acknowledge and can decode transmissions distorted by an arbitrary number of skews that obey this no switch assumption. The rate associated with the coding scheme provides a lower bound of 0.6942 for the (zero-error) capacity of such a channel. It is further shown that zero-error channel capacity of the channel is upper bounded by 0.7248. Finally, this paper presents bounds on the (zero-error) capacity of a channel for which the number of transmissions that can mix with one another is large. [ABSTRACT FROM AUTHOR]

The $q^{t} \times (q+1)t$ ordered orthogonal arrays (OOAs) of strength $t$ over the alphabet $ \mathbb {F}_{q}$ were constructed using linear feedback shift register sequences (LFSRs) defined by primitive polynomials in $ \mathbb {F}_{q}[x]$. In this paper, we extend this result to all polynomials in $\mathbb {F}_{q}[x]$ which satisfy some fairly simple restrictions, i.e., the restrictions that are automatically satisfied by primitive polynomials. While these restrictions sometimes reduce the number of columns produced from $(q+1)t$ to a smaller multiple of $t$ , in many cases, we still obtain the maximum number of columns in the constructed OOA when using non-primitive polynomials. For $2 \le q \le 9$ and small $t$ , we generate OOAs in this manner for all permissible polynomials of degree $t$ in $ \mathbb {F}_{q}[x]$ and compare the results to the ones produced in , , and showing how close the arrays are to being “full” orthogonal arrays. Unusually for the finite fields, our arrays based on the non-primitive irreducible and even reducible polynomials are closer to the orthogonal arrays than those built from the primitive polynomials. [ABSTRACT FROM AUTHOR]

An involution is a permutation, such that its inverse is itself (i.e., cycle length ≤ 2). Due to this property, involutions have been used in many applications, including cryptography and coding theory. In this paper, we provide a systematic study of involutions that are defined over a finite field of characteristic 2. We characterize the involution property of several classes of polynomials and propose several constructions. Furthermore, we study the number of fixed points of involutions, which is a pertinent question related to permutations with short cycle. In this paper, we mostly have used combinatorial techniques. [ABSTRACT FROM AUTHOR]

Switch codes, first proposed by Wang et al., are codes that are designed to increase the parallelism of data writing and reading processes in network switches. A network switch is required to write $n$ incoming packets and read $k$ outgoing packets while using $m$ memory banks, each able to write and read one packet per time unit. Each set of $n$ packets written to the switch simultaneously is called a generation. The objective is to store the packets in the banks such that every request of $k$ packets, which can belong to previous generations, can be handled by reading at most one packet from every bank. In this paper, we study a new type of switch codes that can simultaneously deliver large packet request and good coding rate. These attractive features are achieved by relaxing the request model to a natural sub-class we call consecutive requests. For this new request model, we define a new type of codes called consecutive switch codes. These codes are studied in both the computational and combinatorial models, corresponding to whether the data can be encoded or not. For binary codes, we also study an intermediate model in which a coded packet is formed by the XOR operations of at most two input packets. We present several code constructions and prove the optimality of one family of these codes by providing the corresponding lower bound. Finally, we introduce a construction of conventional switch codes, which improves upon the best known results for the case $n=k$ . [ABSTRACT FROM AUTHOR]

Network switches and routers scale in rate by distributing the packet read/write operations across multiple memory banks. Rate scaling is achieved so long as sufficiently many packets can be written and read in parallel. However, due to the non-determinism of the read process, parallel pending read requests may contend on memory banks, and thus significantly lower the switching rate. In this paper, we provide a constructive study of codes that guarantee fully parallel data reconstruction without contention. We call these codes “switch codes,” and construct three optimal switch-code families with different parameters. All the constructions use only simple XOR-based encoding and decoding operations, an important advantage when operated in ultra-high speeds. Switch codes achieve their good performance by spanning simultaneous disjoint local-decoding sets for all their information symbols. Switch codes may be regarded as an extreme version of the previously studied batch codes, where the switch version requires parallel reconstruction of all the information symbols. [ABSTRACT FROM PUBLISHER]

The large majority of commercially available multiple-input multiple-output (MIMO) radio channel measurement devices (sounders) is based on time-division multiplexed switching (TDMS) of a single transmit/receive radio frequency chain into the elements of a transmit/receive antenna array. While being cost-effective, such a solution can cause significant measurement errors due to phase noise and frequency offset in the local oscillators. In this paper, we systematically analyze the resulting errors and show that, in practice, overestimation of channel capacity by several hundred percent can occur. Overestimation is caused by phase noise (and to a lesser extent by frequency offset), leading to an increase of the MIMO channel rank. Our analysis furthermore reveals that the impact of phase errors is, in general, most pronounced if the physical channel has low rank (typical for line-of-sight or poor scattering scenarios). The extreme case of a rank-1 physical channel is analyzed in detail. The capacity bounds derived in this paper show excellent agreement with measurement results. In light of the findings of this paper, the results obtained through MIMO channel measurement campaigns using TDMS-based channel sounders should be interpreted with great care. [ABSTRACT FROM AUTHOR]

This paper considers the problem of communication over a discrete memoryless channel (DMC) or an additive white Gaussian noise (AWGN) channel subject to the constraint that the probability that an adversary who observes the channel outputs can detect the communication is low. In particular, the relative entropy between the output distributions when a codeword is transmitted and when no input is provided to the channel must be sufficiently small. For a DMC whose output distribution induced by the “off” input symbol is not a mixture of the output distributions induced by other input symbols, it is shown that the maximum amount of information that can be transmitted under this criterion scales like the square root of the blocklength. The same is true for the AWGN channel. Exact expressions for the scaling constant are also derived. [ABSTRACT FROM AUTHOR]

A locally recoverable code (LRC code) is a code over a finite alphabet, such that every symbol in the encoding is a function of a small number of other symbols that form a recovering set. In this paper, we derive new finite-length and asymptotic bounds on the parameters of LRC codes. For LRC codes with a single recovering set for every coordinate, we derive an asymptotic Gilbert–Varshamov type bound for LRC codes and find the maximum attainable relative distance of asymptotically good LRC codes. Similar results are established for LRC codes with two disjoint recovering sets for every coordinate. For the case of multiple recovering sets (the availability problem), we derive a lower bound on the parameters using expander graph arguments. Finally, we also derive finite-length upper bounds on the rate and the distance of LRC codes with multiple recovering sets. [ABSTRACT FROM AUTHOR]

Hilberg’s conjecture about natural language states that the mutual information between two adjacent long blocks of text grows like a power of the block length. The exponent in this statement can be upper bounded using the pointwise mutual information estimate computed for a carefully chosen code. The bound is the better, the lower the compression rate is, but there is a requirement that the code be universal. So as to improve a received upper bound for Hilberg’s exponent, in this paper, we introduce two novel universal codes, called the plain switch distribution and the preadapted switch distribution. Generally speaking, switch distributions are certain mixtures of adaptive Markov chains of varying orders with some additional communication to avoid the so-called catch-up phenomenon. The advantage of these distributions is that they both achieve a low compression rate and are guaranteed to be universal. Using the switch distributions, we obtain that a sample of a text in English is non-Markovian with Hilberg’s exponent being ≤0.83, which improves over the previous bound ≤0.94 obtained using the Lempel–Ziv code. [ABSTRACT FROM PUBLISHER]

This paper studies variable-length (VL) source coding of general sources with side-information. Novel one-shot coding bounds for Slepian–Wolf (SW) coding, which give nonasymptotic tradeoff between the error probability and the codeword length of VL-SW coding, are established. One-shot results are applied to asymptotic analysis, and a general formula for the optimal coding rate achievable by weakly lossless VL-SW coding (i.e., VL-SW coding with vanishing error probability) is derived. Our general formula reveals how the encoder side-information and/or VL coding improve the optimal coding rate in the general setting. In addition, it is shown that if the encoder side-information is useless in weakly lossless VL coding then it is also useless even in the case where the error probability may be positive asymptotically. [ABSTRACT FROM AUTHOR]

This paper considers the Gaussian half-duplex relay channel (G-HD-RC): a channel model where a source transmits a message to a destination with the help of a relay that cannot transmit and receive at the same time. It is shown that the cut-set upper bound on the capacity can be achieved to within a constant gap, regardless of the actual value of the channel parameters, by either partial-decode-and-forward or compress-and-forward. The performance of these coding strategies is evaluated with both random and deterministic switch at the relay. Numerical evaluations show that the actual gap is less than what analytically obtained, and that random switch achieves higher rates than deterministic switch. As a result of this analysis, the generalized degrees-of-freedom of the G-HD-RC is exactly characterized for this channel. In order to get insights into practical schemes for the G-HD-RC that are less complex than partial-decode-and-forward or compress-and-forward, the exact capacity of the linear deterministic approximation (LDA) of the G-HD-RC at high signal-to-noise-ratio is determined. It is shown that random switch and correlated nonuniform inputs bits are optimal for the LDA. It is then demonstrated that deterministic switch is to within one bit from the capacity. This latter scheme is translated into a coding strategy for the original G-HD-RC and its optimality to within a constant gap is proved. The gap attained by this scheme is larger than that of partial-decode-and-forward, thereby pointing to an interesting practical tradeoff between gap to capacity and complexity. [ABSTRACT FROM AUTHOR]

Rare events can potentially occur in many applications. When manifested as opportunities to be exploited, risks to be ameliorated, or certain features to be extracted, such events become of paramount significance. Due to their sporadic nature, the information-bearing signals associated with rare events often lie in a large set of irrelevant signals and are not easily accessible. This paper provides a statistical framework for detecting such events so that an optimal balance between detection reliability and agility, as two opposing performance measures, is established. The core component of this framework is a sampling procedure that adaptively and quickly focuses the information-gathering resources on the segments of the dataset that bear the information pertinent to the rare events. Particular focus is placed on Gaussian signals with the aim of detecting signals with rare mean and variance values. [ABSTRACT FROM AUTHOR]

In the framework of prediction of individual sequences, sequential prediction methods are to be constructed that perform nearly as well as the best expert from a given class. We consider prediction strategies that compete with the class of switching strategies that can segment a given sequence into several blocks, and follow the advice of a different “base” expert in each block. As usual, the performance of the algorithm is measured by the regret defined as the excess loss relative to the best switching strategy selected in hindsight for the particular sequence to be predicted. In this paper, we construct prediction strategies of low computational cost for the case where the set of base experts is large. In particular, we provide a method that can transform any prediction algorithm \cal A that is designed for the base class into a tracking algorithm. The resulting tracking algorithm can take advantage of the prediction performance and potential computational efficiency of \cal A in the sense that it can be implemented with time and space complexity only O(n^\gamma \ln n) times larger than that of \cal A, where n is the time horizon and \gamma \geq 0 is a parameter of the algorithm. With \cal A properly chosen, our algorithm achieves a regret bound of optimal order for \gamma > 0, and only O(\ln n) times larger than the optimal order for \gamma =0 for all typical regret bound types we examined. For example, for predicting binary sequences with switching parameters under the logarithmic loss, our method achieves the optimal O(\ln n) regret rate with time complexity O(n^1+\gamma \ln n) for any \gamma \in (0,1). [ABSTRACT FROM PUBLISHER]

Cross-bifix-free sets are sets of words such that no prefix of any word is a suffix of any other word. In this paper, we introduce a general constructive method for the sets of cross-bifix-free binary words of fixed length. It enables us to determine a cross-bifix-free words subset which has the property to be non-expandable. [ABSTRACT FROM PUBLISHER]

This paper investigates the following general problem relating to ordered random processes: given n independent but not necessarily identical random processes, how frequently, on average, does any given process become one of the pth (p=1,2,\ldots, n-1) largest processes? This is a fundamental problem arising in the design and analysis of contemporary multidimensional wireless communication systems (e.g., multiantenna, multiuser) employing opportunistic selection. We formulate this problem as one involving the level crossing rate (LCR) of a carefully defined ordered random process across the zero threshold, which we solve by developing a new mathematical framework based on the theory of permanents. For the case where the processes correspond to time-varying Rayleigh fading channels, we present exact closed-form formulas for the LCR, simplified tight upper bounds, as well as asymptotic results for n and p approaching infinity but with fixed ratio. These results reveal interesting fundamental limits for the LCR, and are shown to given meaningful insight even for small values of n and p. We further use our mathematical framework to characterize the required per-branch and overall switching rate of a generalized selection combining diversity receiver, allowing for different average powers for each branch. With the aid of majorization theory, we demonstrate that the overall switching rate is maximized when the power delay profile is uniform. [ABSTRACT FROM PUBLISHER]

The problem of finding the rate-distortion function of an arbitrarily varying source (AVS) composed of a finite number of memoryless subsources is revisited. Berger's 1971 paper “The Source Coding Game” solves this problem when the adversary is allowed only strictly causal access to the subsource realizations. The case when the adversary has access to the subsource realizations non-causally is considered. This new rate-distortion function is determined to be the maximum of the rate-distortion function over a set of independent and identically distributed (IID) random variables that can be simulated by the adversary. The results are extended to allow for partial or noisy observations of subsource realizations. The model is further explored by attempting to find the rate-distortion function when the ‘adversary’ is actually helpful. Finally, a bound is developed on the uniform continuity of the IID rate-distortion function for finite-alphabet sources. The bound is used to give a sufficient number of distributions that need to be sampled to compute the rate-distortion function of an AVS to within a desired accuracy. The bound is also used to give a rate of convergence for the estimate of the rate-distortion function for an unknown IID source. [ABSTRACT FROM AUTHOR]