Information Theory (cs.IT)

Abstract: This paper deals with Niho functions which are one of the most important classes of functions thanks to their close connections with a wide variety of objects from mathematics, such as spreads and oval polynomials or from applied areas, such as symmetric cryptography, coding theory and sequences. In this paper, we investigate specifically the $c$-differential uniformity of the power function $F(x)=x^{s(2^m-1)+1}$ over the finite field $\mathbb{F}_{2^n}$, where $n=2m$, $m$ is odd and $s=(2^k+1)^{-1}$ is the multiplicative inverse of $2^k+1$ modulo $2^m+1$, and show that the $c$-differential uniformity of $F(x)$ is $2^{\gcd(k,m)}+1$ by carrying out some subtle manipulation of certain equations over $\mathbb{F}_{2^n}$. Notably, $F(x)$ has a very low $c$-differential uniformity equals $3$ when $k$ and $m$ are coprime.

Abstract: Intelligent reflecting surfaces (IRSs) have emerged as a promising technology to improve the efficiency of wireless communication systems. However, passive IRSs suffer from the ``multiplicative fading" effect, because the transmit signal will go through two fading hops. With the ability to amplify and reflect signals, active IRSs offer a potential way to tackle this issue, where the amplification energy only experiences the second hop. However, the fundamental limit and system design for active IRSs have not been fully understood, especially for multiple-input multiple-output (MIMO) systems. In this work, we consider the analysis and design for the large-scale active IRS-aided MIMO system assuming only statistical channel state information (CSI) at the transmitter and the IRS. The evaluation of the fundamental limit, i.e., ergodic rate, turns out to be a very difficult problem. To this end, we leverage random matrix theory (RMT) to derive the deterministic approximation (DA) for the ergodic rate, and then design an algorithm to jointly optimize the transmit covariance matrix at the transmitter and the reflection matrix at the active IRS. Numerical results demonstrate the accuracy of the derived DA and the effectiveness of the proposed optimization algorithm. The results in this work reveal interesting physical insights with respect to the advantage of active IRSs over their passive counterparts.

Abstract: Variant belief-propagation (BP) algorithms are applied to low-density parity-check (LDPC) codes, and a near Shannon limit error-rate performance is obtained. However, the decoders presented in previous literature suffer from a large resource consumption due to the accumulative calculations for each extrinsic message updating. In this paper, check belief is introduced as the probability that the corresponding parity check is satisfied. A check belief propagation (CBP) algorithm is proposed, which can force all the check nodes to contribute their check beliefs to others in a sequential order. The check nodes will enlarge the check beliefs of all the check nodes iteratively. This can result in positive check beliefs for all the check nodes, which indicates that all the parity checks are successfully satisfied. Different from previous BP algorithms, the check beliefs are propagated with no accumulative calculations at an acceptable speed, with low complexity and without performance loss. The simulation results and analyses show that the CBP algorithm provides a similar prominent error-rate performance as the previous BP algorithms, but consumes a lot fewer resources than them. It earns a big benefit in terms of complexity.

Abstract: J. Y. Hyun, et al. (Des. Codes Cryptogr., vol. 88, pp. 2475-2492, 2020) constructed some optimal and minimal binary linear codes generated by one or two order ideals in hierarchical posets of two levels. At the end of their paper, they left an open problem: it also should be interesting to investigate the cases of more than two orders in hierarchical posets with two levels or many levels. In this paper, we use the geometric method to determine the minimality of linear codes generated by any orders in hierarchical posets with two levels. We generalize their cases of one or two orders to any orders and determine the minimality of the linear codes completely.

Abstract: Partial spread is important in finite geometry and can be used to construct linear codes. From the results in (Designs, Codes and Cryptography 90:1-15, 2022) by Xia Li, Qin Yue and Deng Tang, we know that if the number of the elements in a partial spread is ``big enough", then the corresponding linear code is minimal. They used the sufficient condition in (IEEE Trans. Inf. Theory 44(5): 2010-2017, 1998) to prove the minimality of such linear codes. In this paper, we use the geometric approach to study the minimality of linear codes constructed from partial spreads in all cases.

Abstract: In a typical formulation of the private information retrieval (PIR) problem, a single user wishes to retrieve one out of $ K$ datasets from $N$ servers without revealing the demanded message index to any server. This paper formulates an extended model of PIR, referred to as multi-message private computation (MM-PC), where instead of retrieving a single message, the user wishes to retrieve $P>1$ linear combinations of datasets while preserving the privacy of the demand information. The MM-PC problem is a generalization of the private computation (PC) problem (where the user requests one linear combination of the datasets), and the multi-message private information retrieval (MM-PIR) problem (where the user requests $P>1$ datasets). A direct achievable scheme, referred to as baseline scheme, repeats the optimal PC scheme by Sun and Jafar $P$ times, or treats each possible demanded linear combination as an independent dataset and then uses the near optimal MM-PIR scheme by Banawan and Ulukus. However, a direct combination of the PC and the MM-PIR schemes does not result in an achievable scheme. Our main contribution to this new problem is to propose an achievable MM-PC scheme by smartly leveraging the above two schemes with some additional highly non-trivial steps.

Abstract: Motivated by applications to noncoherent network coding, we study subspace codes defined by sets of linear cellular automata (CA). As a first remark, we show that a family of linear CA where the local rules have the same diameter -- and thus the associated polynomials have the same degree -- induces a Grassmannian code. Then, we prove that the minimum distance of such a code is determined by the maximum degree occurring among the pairwise greatest common divisors (GCD) of the polynomials in the family. Finally, we consider the setting where all such polynomials have the same GCD, and determine the cardinality of the corresponding Grassmannian code. As a particular case, we show that if all polynomials in the family are pairwise coprime, the resulting Grassmannian code has the highest minimum distance possible.

Abstract: We introduce and characterize a natural generalization of the Two-Wave with Diffuse Power (TWDP) fading model, by allowing that the incident waves arrive in different clusters. The newly proposed model, referred to as the Multi-cluster Two-Wave (MTW) fading model, generalizes both the TWDP and the kappa-mu models under a common umbrella. The special case on which the model parameters reach extreme values is also analyzed, aimed to model harsh fading conditions reported in experimental measurements obtained in enclosed environments. The chief probability functions of both the MTW and the MTW Extreme fading models are obtained, including the probability density function, the cumulative distribution function and the generalized moment-generating function. A number of applications for these models are exemplified, including outage probability in interference-limited scenarios, energy detection, and composite fading modeling.

Abstract: Due to their weak algebraic structure, low rank parity check (LRPC) codes have been employed in several post-quantum cryptographic schemes. In this paper we propose new improved decoding algorithms for (n, k) LRPC codes of dual rank weight d. The proposed algorithms can efficiently decode LRPC codes with the parameters satisfying n - k = rd - c, where r is the dimension of the error support and c <= d - 2. They outperform the original decoding algorithm of LRPC codes when d > 2 and allow for decoding LRPC codes with a higher code rate and smaller values m.

Abstract: In this paper, we consider the robust beamforming design in a reconfigurable intelligent surface (RIS)-aided cell-free (CF) system considering the channel state information (CSI) uncertainties of both the direct channels and cascaded channels at the transmitter with capacity-limited backhaul. We jointly optimize the precoding at the access points (APs) and the phase shifts at multiple RISs to maximize the worst-case sum rate of the CF system subject to the constraints of maximum transmit power of APs, unit-modulus phase shifts, limited backhaul capacity, and bounded CSI errors. By applying a series of transformations, the non-smoothness and semi-infinite constraints are tackled in a low-complexity manner that facilitates the design of an alternating optimization (AO)-based iterative algorithm. The proposed algorithm divides the considered problem into two subproblems. For the RIS phase shifts optimization subproblem, we exploit the penalty convex-concave procedure (P-CCP) to obtain a stationary solution and achieve effective initialization. For precoding optimization subproblem, successive convex approximation (SCA) is adopted with a convergence guarantee to a Karush-Kuhn-Tucker (KKT) solution. Numerical results demonstrate the effectiveness of the proposed robust beamforming design, which achieves superior performance with low complexity. Moreover, the importance of RIS phase shift optimization for robustness and the advantages of distributed RISs in the CF system are further highlighted.

Abstract: We provide a mathematical framework to analyze the limits of Hybrid Automatic Repeat reQuest (HARQ) and derive analytical expressions for the most powerful test for estimating the decodability under maximum-likelihood decoding and $t$-error decoding. Furthermore, we numerically approximate the most powerful test for sum-product decoding. We compare the performance of previously studied HARQ prediction schemes and show that none of the state-of-the-art HARQ prediction is most powerful to estimate the decodability of a partially received signal vector under maximum-likelihood decoding and sum-product decoding. Furthermore, we demonstrate that decoding in general is suboptimal for predicting the decodability.

Abstract: In this paper, we investigate the near-field modelling and analyze the beam focusing pattern for modular extremely large-scale array (XL-array) communications. As modular XL-array is physically and electrically large in general, the accurate characterization of amplitude and phase variations across its array elements requires the non-uniform spherical wave (NUSW) model, which, however, is difficult for performance analysis and optimization. To address this issue, we first present two ways to simplify the NUSW model by exploiting the unique regular structure of modular XL-array, termed sub-array based uniform spherical wave (USW) models with different or common angles, respectively. Based on the developed models, the near-field beam focusing patterns of XL-array communications are derived. It is revealed that compared to the existing collocated XL-array with the same number of array elements, modular XL-array can significantly enhance the spatial resolution, but at the cost of generating undesired grating lobes. Fortunately, different from the conventional far-field uniform plane wave (UPW) model, the near-field USW model for modular XL-array exhibits a higher grating lobe suppression capability, thanks to the non-linear phase variations across the array elements. Finally, simulation results are provided to verify the near-field beam focusing pattern and grating lobe characteristics of modular XL-array.

Abstract: We consider the multi-access coded caching problem, which contains a central server with $N$ files, $K$ caches with $M$ units of memory each and $K$ users where each one is connected to $L (\geq 1)$ consecutive caches, with a cyclic wrap-around. Caches are populated with content related to the files and each user then requests a file that has to be served via a broadcast message from the central server with the help of the caches. We aim to design placement and delivery policies for this setup that minimize the central servers' transmission rate while satisfying an additional linear sub-packetization constraint. We propose policies that satisfy this constraint and derive upper bounds on the achieved server transmission rate, which upon comparison with the literature establish the improvement provided by our results. To derive our results, we map the multi-access coded caching problem to variants of the well-known index coding problem. In this process, we also derive new bounds on the optimal transmission size for a `structured' index coding problem, which might be of independent interest.

Abstract: In space-air-ground integrated networks (SAGIN), terminals face interference from various sources such as satellites and terrestrial transmitters. However, managing interference with traditional interference management schemes (IM) is challenging since different terminals have different channel state information (CSI). This paper introduces a UAV carrying an active RIS (UAV-RIS) to assist in the interference elimination process. Furthermore, a UAV-RIS-aided IM scheme is proposed, which takes into account the multiple types of CSIs present in SAGIN. In this scheme, the satellite, terrestrial transmitters, and UAV-RIS collaborate to design precoding matrices based on the specific type of CSI of each node. Additionally, the DoF gain obtained by the proposed IM scheme is thoroughly discussed for SAGIN configurations with different numbers of users and transceiver antennas. Simulation results demonstrate that the proposed IM scheme outperforms existing IM schemes without UAV-RIS for the same type of CSI. The results also showcase the capacity improvement of the network when the proposed IM scheme is adopted under different types of CSI.

Abstract: We consider a standard two-source model for uniform common randomness (UCR) generation, in which Alice and Bob observe independent and identically distributed (i.i.d.) samples of a correlated finite source and where Alice is allowed to send information to Bob over an arbitrary single-user channel. We study the \(\boldsymbol{\epsilon}\)-UCR capacity for the proposed model, defined as the maximum common randomness rate one can achieve such that the probability that Alice and Bob do not agree on a common uniform or nearly uniform random variable does not exceed \(\boldsymbol{\epsilon}.\) We establish a lower and an upper bound on the \(\boldsymbol{\epsilon}\)-UCR capacity using the bounds on the \(\boldsymbol{\epsilon}\)-transmission capacity proved by Verd\'u and Han for arbitrary point-to-point channels.

Abstract: A code of length $n$ is said to be (combinatorially) $(\rho,L)$-list decodable if the Hamming ball of radius $\rho n$ around any vector in the ambient space does not contain more than $L$ codewords. We study a recently introduced class of higher order MDS codes, which are closely related (via duality) to codes that achieve a generalized Singleton bound for list decodability. For some $\ell\geq 1$, higher order MDS codes of length $n$, dimension $k$, and order $\ell$ are denoted as $(n,k)$-MDS($\ell$) codes. We present a number of results on the structure of these codes, identifying the `extend-ability' of their parameters in various scenarios. Specifically, for some parameter regimes, we identify conditions under which $(n_1,k_1)$-MDS($\ell_1$) codes can be obtained from $(n_2,k_2)$-MDS($\ell_2$) codes, via various techniques. We believe that these results will aid in efficient constructions of higher order MDS codes. We also obtain a new field size upper bound for the existence of such codes, which arguably improves over the best known existing bound, in some parameter regimes.

Abstract: We consider a special case of $X$-secure $T$-private information retrieval (XSTPIR), where the security requirement is \emph{asymmetric} due to possible missing communication links between the $N$ databases considered in the system. We define the problem with a communication matrix that indicates all possible communications among the databases, and propose a database grouping mechanism that collects subsets of databases in an optimal manner, followed by a group-based PIR scheme to perform asymmetric XSTPIR with the goal of maximizing the communication rate (minimizing the download cost). We provide an upper bound on the general achievable rate of asymmetric XSTPIR, and show that the proposed scheme achieves this upper bound in some cases. The proposed approach outperforms classical XSTPIR under certain conditions, and the results of this work show that unlike in the symmetric case, some databases with certain properties can be dropped to achieve higher rates, concluding that more databases is not always better.