Search

This paper considers a real-time status update system in which an energy harvesting (EH)-powered transmitter node observes some physical process, and sends its sensed measurements in the form of status updates to a destination node. The status update and harvested energy packets are assumed to arrive at the transmitter according to independent Poisson processes, and the service time of each status update is assumed to be exponentially distributed. We quantify the freshness of status updates when they reach the destination using the concept of Age of Information (AoI). Unlike most of the existing analyses of AoI focusing on the evaluation of its average value when the transmitter is not subject to energy constraints, our analysis is focused on understanding the distributional properties of AoI through the characterization of its moment generating function (MGF). In particular, we use the stochastic hybrid systems (SHS) framework to derive closed-form expressions of the MGF of AoI under several queueing disciplines at the transmitter, including non-preemptive and preemptive in service/waiting strategies. Using these MGF results, we further obtain closed-form expressions for the first and second moments of AoI in each queueing discipline. We demonstrate the generality of this analysis by recovering several existing results for the corresponding system with no energy constraints as special cases of the new results. Our numerical results verify the analytical findings, and demonstrate the necessity of incorporating the higher moments of AoI in the implementation/optimization of real-time status update systems rather than just relying on its average value. [ABSTRACT FROM AUTHOR]

Linear codes generated by component functions of perfect nonlinear (PN for short) and almost perfect nonlinear (APN for short) functions and the first-order Reed-Muller codes have been an object of intensive study in coding theory. The objective of this paper is to investigate some binary shortened codes of two families of linear codes from APN functions and some $p$ -ary shortened codes associated with PN functions. The weight distributions of these shortened codes and the parameters of their duals are determined. The parameters of these binary codes and $p$ -ary codes are flexible. Many of the codes presented in this paper are optimal or almost optimal. The results of this paper show that the shortening technique is very promising for constructing good codes. [ABSTRACT FROM AUTHOR]

Non-overlapping codes are a set of codewords in $\bigcup _{n \ge 2} \mathbb {Z}_{q}^{n}$ , where $\mathbb {Z}_{q} = \{0,1, {\dots },q-1\}$ , such that the prefix of each codeword is not a suffix of any codeword in the set, including itself; and for variable-length codes, a codeword does not contain any other codeword as a subword. In this paper, we investigate a generic method to generalize binary codes to $q$ -ary ones for $q > 2$ , and analyze this generalization on the two constructions given by Levenshtein (also by Gilbert; Chee, Kiah, Purkayastha, and Wang) and Bilotta, respectively. The generalization on the former construction gives large non-expandable fixed-length non-overlapping codes whose size can be explicitly determined; the generalization on the latter construction is the first attempt to generate $q$ -ary variable-length non-overlapping codes. More importantly, this generic method allows us to utilize the generating function approach to analyze the cardinality of the underlying $q$ -ary non-overlapping codes. The generating function approach not only enables us to derive new results, e.g., recurrence relations on their cardinalities, new combinatorial interpretations for the constructions, and the superior limit of their cardinalities for some special cases, but also greatly simplifies the arguments for these results. Furthermore, we give an exact formula for the number of fixed-length words that do not contain the codewords in a variable-length non-overlapping code as subwords. This thereby solves an open problem by Bilotta and induces a recursive upper bound on the maximum size of variable-length non-overlapping codes. [ABSTRACT FROM AUTHOR]

We consider the problem of lossless compression of individual sequences using finite-state (FS) machines, from the perspective of the best achievable empirical cumulant generating function (CGF) of the code length, i.e., the normalized logarithm of the empirical average of the exponentiated code length. Since the probabilistic CGF is minimized in terms of the Rényi entropy of the source, one of the motivations of this paper is to derive an individual-sequence analogue of the Rényi entropy, in the same way that the FS compressibility is the individual-sequence counterpart of the Shannon entropy. We consider the CGF of the code-length both from the perspective of fixed-to-variable length coding and the perspective of variable-to-variable (V-V) length coding, where the latter turns out to yield a better result, that coincides with the FS compressibility. We also extend our results to compression with side information, available at both the encoder and decoder. In this case, the V-V version no longer coincides with the FS compressibility, but results in a different complexity measure. [ABSTRACT FROM AUTHOR]

Offset codebook or ${\mathsf {OCB}}$ mode is a popular block cipher mode of operation for authenticated encryption. The latest version of this cipher, called ${\mathsf {OCB3}}$ , is one of the finalists in CAESAR. In this paper, we explore the scope of random read access and out-of-sequence decryption in ${\mathsf {OCB}}$. We observe that the current versions of ${\mathsf {OCB}}$ are inefficient in this respect owing to the ineptness of the underlying mask generating function (MGF). We propose new candidates for MGF based on ${\mathsf {AES}}$ round function, which are efficient in direct computation and provide comparable performance in the usual setting. Our schemes are not the obvious choices for MGF in conventional sense as they do not have optimal almost XOR universal (AXU) bound. In existing ${\mathsf {OCB}}$ designs, the MGFs are required to have $ 2^{-n} $ , i.e. optimal, AXU bound in order to upper bound the distinguishing advantage to $ O(\sigma ^{2}/2^{n}) $ , where $ n $ is the block size of the underlying block cipher and $ \sigma $ is the total number of blocks among all queries. We find this specific requirement too restrictive. We abstract the ${\mathsf {OCB}}$ design, termed as ${\mathsf {GOCB}}$ , to look into the universal notion required from the underlying MGF. We propose a relaxed notion of AXU, called locally imperfect XOR universal (LIXU) hash, which can be of independent interest. Using LIXU as the underlying MGF, we recover reasonable security bounds for our schemes. [ABSTRACT FROM AUTHOR]

Point processes are often described with functionals, such as the probability generating functional, the Laplace functional, and the factorial cumulant generating functional. These are used to facilitate modelling of different processes and to determine important statistics via functional differentiation. In information theory, generating functions have also been defined for probability densities to determine information quantities such as the Shannon information and Kullback-Leibler divergence, though as yet there are no such analogues for point processes. The purpose of this article is to exploit the advantages of both types of generating function to facilitate the derivation of information statistics for point processes. In particular, a generating functional for point processes is introduced for determining statistics related to entropy and relative entropy based on Golomb’s information function and Moyal’s probability generating functional. It is shown that the information generating functional permits the derivation of a suite of statistics, including localised Shannon entropy and Kullback-Leibler divergence calculations. [ABSTRACT FROM AUTHOR]

We study the cross-join pairs in the cycles of linear feedback shift registers whose characteristic polynomials are of the form $l(x) = p_{1}(x)p_{2}(x)\cdots p_{k}(x)$ , where $p_{i}(x), 1\leq i\leq k$ are primitive polynomials of coprime degrees. Firstly, we use Coppersmith et al.’s generating function theory to derive the lower and upper bounds for the number of cross-join pairs. Then we design an algorithm to generate these cross-join pairs. The algorithm requires a preparatory phase which costs $O(2^{n'})$ time where $n'$ is the largest degree of $p_{i}(x), 1\leq i\leq k$ , and after that it costs only $O(n^{3})$ time to generate one cross-join pair where $n$ is the degree of $l(x)$. We also consider a special class of cross-join pairs, for which the preparatory phase costs only $O(2^{n''})$ time where $n''$ is the second-largest degree of $p_{i}(x), 1\leq i\leq k$. The number of these special cross-join pairs is about $\frac {1}{12}2^{2n-n'}$. We present some experimental results, which validate our analysis and demonstrate the efficiencies of the algorithms. These cross-join pairs can be used in the cross-joining method to construct de Bruijn sequences. [ABSTRACT FROM AUTHOR]

We derive tight and computable bounds on the bias of statistical estimators, or more generally of quantities of interest, when evaluated on a baseline model $P$ rather than on the typically unknown true model $Q$. Our proposed method combines the scalable information inequality derived by P. Dupuis, K.Chowdhary, the authors and their collaborators together with classical concentration inequalities (such as Bennett’s and Hoeffding-Azuma inequalities). Our bounds are expressed in terms of the Kullback-Leibler divergence $R(Q\|P)$ of model $Q$ with respect to $P$ and the moment generating function for the statistical estimator under $P$. Furthermore, concentration inequalities, i.e. bounds on moment generating functions, provide tight and computationally inexpensive model bias bounds for quantities of interest. Finally, they allow us to derive rigorous confidence bands for statistical estimators that account for model bias and are valid for an arbitrary amount of data. [ABSTRACT FROM AUTHOR]