Information Theory
See recent articles
- [1] arXiv:2407.11265 [pdf, html, other]
-
Title: Mix-and-Conquer: Beamforming Design with Interconnected RIS for Multi-User NetworksComments: This paper has been accepted at the IEEE International Conference on Communications (ICC) 2024Subjects: Information Theory (cs.IT); Signal Processing (eess.SP)
We propose a new reconfigurable intelligent surface (RIS) structure, referred to as interconnected RIS (I-RIS), which allows the RIS elements to be interconnected and share the incident signals using simple binary radio frequency (RF) switches and mix them into the reflecting signals. This structure enables multi-user scaling and requires fewer elements (i.e., a compact structure) compared to standard RIS (S-RIS), which assumes no interconnection between the elements. The I-RIS compact design makes it practical for deployment on space-limited nodes, e.g., unmanned aerial vehicles (UAVs). Hence, in this work, we propose a beamforming design based on I-RIS in a multi-user network, where we use binary RF switches as RIS elements. We show that our switch-based I-RIS offers a higher gain compared to an S-RIS using phase shifters. Finally, we introduce two optimization methods, sigmoid filled function (SFF) and semi-definite binary optimization (SBO), to optimize the RIS elements and evaluate their performance in terms of sum-rate and complexity.
- [2] arXiv:2407.11554 [pdf, html, other]
-
Title: Optimal Constant-Weight and Mixed-Weight Conflict-Avoiding CodesComments: 32 pagesSubjects: Information Theory (cs.IT); Combinatorics (math.CO)
A conflict-avoiding code (CAC) is a deterministic transmission scheme for asynchronous multiple access without feedback. When the number of simultaneously active users is less than or equal to $w$, a CAC of length $L$ with weight $w$ can provide a hard guarantee that each active user has at least one successful transmission within every consecutive $L$ slots. In this paper, we generalize some previously known constructions of constant-weight CACs, and then derive several classes of optimal CACs by the help of Kneser's Theorem and some techniques in Additive Combinatorics. Another spotlight of this paper is to relax the identical-weight constraint in prior studies to study mixed-weight CACs for the first time, for the purpose of increasing the throughput and reducing the access delay of some potential users with higher priority. As applications of those obtained optimal CACs, we derive some classes of optimal mixed-weight CACs.
- [3] arXiv:2407.11604 [pdf, other]
-
Title: Building Resilience in Wireless Communication Systems With a Secret-Key BudgetComments: 13 pages, 11 figuresSubjects: Information Theory (cs.IT); Signal Processing (eess.SP)
Resilience and power consumption are two important performance metrics for many modern communication systems, and it is therefore important to define, analyze, and optimize them. In this work, we consider a wireless communication system with secret-key generation, in which the secret-key bits are added to and used from a pool of available key bits. We propose novel physical layer resilience metrics for the survivability of such systems. In addition, we propose multiple power allocation schemes and analyze their trade-off between resilience and power consumption. In particular, we investigate and compare constant power allocation, an adaptive analytical algorithm, and a reinforcement learning-based solution. It is shown how the transmit power can be minimized such that a specified resilience is guaranteed. These results can be used directly by designers of such systems to optimize the system parameters for the desired performance in terms of reliability, security, and resilience.
- [4] arXiv:2407.11651 [pdf, html, other]
-
Title: Fluid Antenna Grouping Index Modulation Design for MIMO SystemsComments: A longer and more detailed version will be submitted to an IEEE journalSubjects: Information Theory (cs.IT); Signal Processing (eess.SP)
Index modulation (IM) significantly enhances the spectral efficiency of fluid antennas (FAs) enabled multiple-input multiple-output (MIMO) systems, which is named FA-IM. However, due to the dense distribution of ports on fluid antennas, the wireless channel exhibits a high spatial correlation, resulting in severe performance degradation in the existing FA-IM scheme. This paper proposes a novel fluid antenna grouping index modulation (FA-GIM) scheme to mitigate the spatial correlation of the FA-IM channel, further enhancing system performance. Based on the spatial correlation model of two-dimensional (2D) fluid antenna surfaces, this paper specifically adopts a block grouping method where adjacent ports are allocated to the same group. The numerical results demonstrate that the proposed scheme exhibits superior bit error rate (BER) performance compared to the state-of-the-art scheme, enhancing the robustness of FA-assisted MIMO systems.
- [5] arXiv:2407.11807 [pdf, html, other]
-
Title: Scalable and Reliable Over-the-Air Federated Edge LearningSubjects: Information Theory (cs.IT); Distributed, Parallel, and Cluster Computing (cs.DC); Machine Learning (cs.LG)
Federated edge learning (FEEL) has emerged as a core paradigm for large-scale optimization. However, FEEL still suffers from a communication bottleneck due to the transmission of high-dimensional model updates from the clients to the federator. Over-the-air computation (AirComp) leverages the additive property of multiple-access channels by aggregating the clients' updates over the channel to save communication resources. While analog uncoded transmission can benefit from the increased signal-to-noise ratio (SNR) due to the simultaneous transmission of many clients, potential errors may severely harm the learning process for small SNRs. To alleviate this problem, channel coding approaches were recently proposed for AirComp in FEEL. However, their error-correction capability degrades with an increasing number of clients. We propose a digital lattice-based code construction with constant error-correction capabilities in the number of clients, and compare to nested-lattice codes, well-known for their optimal rate and power efficiency in the point-to-point AWGN channel.
- [6] arXiv:2407.11810 [pdf, html, other]
-
Title: About the generalized Hamming weights of matrix-product codesSubjects: Information Theory (cs.IT)
We derive a general lower bound for the generalized Hamming weights of nested matrix-product codes, with a particular emphasis on the cases with two and three constituent codes. We also provide an upper bound which is reminiscent of the bounds used for the minimum distance of matrix-product codes. When the constituent codes are two Reed-Solomon codes, we obtain an explicit formula for the generalized Hamming weights of the resulting matrix-product code. We also deal with the non-nested case for the case of two constituent codes.
- [7] arXiv:2407.11896 [pdf, html, other]
-
Title: Trajectory and Power Optimization for Multi-UAV Enabled Emergency Wireless Communications NetworksComments: 6 pages, 3 figuresJournal-ref: 2019 IEEE International Conference on Communications Workshops (ICC Workshops)Subjects: Information Theory (cs.IT); Signal Processing (eess.SP)
Recently, unmanned aerial vehicle (UAV) has attracted much attention due to its flexible deployment and controllable mobility. As the general communication network cannot meet the emergency requirements, in this paper we study the multi-UAV enabled wireless emergency communication system. Our goal is to maximize the capacity with jointly optimizing trajectory and allocating power. To tackle this non-convex optimization problem, we first decompose it into two sub-problems to optimize the trajectory and power allocation, respectively. Then, we propose the successive convex approximation technique and the block coordinate update algorithm to solve the two subproblems. The approximate optimal solution can be obtained after continuous iterations. Simulation results show that the capacity can be greatly increased using our proposed joint trajectory optimization and power allocation.
New submissions for Wednesday, 17 July 2024 (showing 7 of 7 entries )
- [8] arXiv:2407.11079 (cross-list from eess.SP) [pdf, html, other]
-
Title: One-Bit MIMO Detection: From Global Maximum-Likelihood Detector to Amplitude Retrieval ApproachSubjects: Signal Processing (eess.SP); Information Theory (cs.IT)
As communication systems advance towards the future 6G era, the incorporation of large-scale antenna arrays in base stations (BSs) presents challenges such as increased hardware costs and energy consumption. To address these issues, the use of one-bit analog-to-digital converters (ADCs)/digital-to-analog converters (DACs) has gained significant attentions. This paper focuses on one-bit multiple-input multiple-output (MIMO) detection in an uplink multiuser transmission scenario where the BS employs one-bit ADCs. One-bit quantization retains only the sign information and loses the amplitude information, which poses a unique challenge in the corresponding detection problem. The maximum-likelihood (ML) formulation of one-bit MIMO detection has a challenging likelihood function that hinders the application of many high-performance detectors developed for classic MIMO detection (under high-resolution ADCs). While many approximate methods for the ML detection problem have been studied, it lacks an efficient global algorithm. This paper fills this gap by proposing an efficient branch-and-bound algorithm, which is guaranteed to find the global solution of the one-bit ML MIMO detection problem. Additionally, a new amplitude retrieval (AR) detection approach is developed, incorporating explicit amplitude variables into the problem formulation. The AR approach yields simpler objective functions that enable the development of efficient algorithms offering both global and approximate solutions. The paper also contributes to the computational complexity analysis of both ML and AR detection problems. Extensive simulations are conducted to demonstrate the effectiveness and efficiency of the proposed formulations and algorithms.
- [9] arXiv:2407.11118 (cross-list from quant-ph) [pdf, html, other]
-
Title: Tight lower bound on the error exponent of classical-quantum channelsComments: 14 pages, no figures. This work extends arXiv:2207.08899 to the case of general CQ channelsSubjects: Quantum Physics (quant-ph); Information Theory (cs.IT)
A fundamental quantity of interest in Shannon theory, classical or quantum, is the error exponent of a given channel $W$ and rate $R$: the constant $E(W,R)$ which governs the exponential decay of decoding error when using ever larger optimal codes of fixed rate $R$ to communicate over ever more (memoryless) instances of a given channel $W$. Nearly matching lower and upper bounds are well-known for classical channels. Here I show a lower bound on the error exponent of communication over arbitrary classical-quantum (CQ) channels which matches Dalai's sphere-packing upper bound [IEEE TIT 59, 8027 (2013)] for rates above a critical value, exactly analogous to the case of classical channels.
Unlike the classical case, however, the argument does not proceed via a refined analysis of a suitable decoder, but instead by leveraging a bound by Hayashi on the error exponent of the cryptographic task of privacy amplification [CMP 333, 335 (2015)]. This bound is then related to the coding problem via tight entropic uncertainty relations and Gallager's method of constructing capacity-achieving parity-check codes for arbitrary channels. Along the way, I find a lower bound on the error exponent of the task of compression of classical information relative to quantum side information that matches the sphere-packing upper bound of Cheng et al. [IEEE TIT 67, 902 (2021)]. In turn, the polynomial prefactors to the sphere-packing bound found by Cheng et al. may be translated to the privacy amplification problem, sharpening a recent result by Li, Yao, and Hayashi [IEEE TIT 69, 1680 (2023)], at least for linear randomness extractors. - [10] arXiv:2407.11123 (cross-list from quant-ph) [pdf, html, other]
-
Title: Time-symmetric correlations for open quantum systemsComments: 17 pages, 5 figures. Comments welcome!Subjects: Quantum Physics (quant-ph); Information Theory (cs.IT); General Relativity and Quantum Cosmology (gr-qc); High Energy Physics - Theory (hep-th)
Two-time expectation values of sequential measurements of dichotomic observables are known to be time symmetric for closed quantum systems. Namely, if a system evolves unitarily between sequential measurements of dichotomic observables $\mathscr{O}_{A}$ followed by $\mathscr{O}_{B}$, then it necessarily follows that $\langle\mathscr{O}_{A}\,,\mathscr{O}_{B}\rangle=\langle\mathscr{O}_{B}\,,\mathscr{O}_{A}\rangle$, where $\langle\mathscr{O}_{A}\,,\mathscr{O}_{B}\rangle$ is the two-time expectation value corresponding to the product of the measurement outcomes of $\mathscr{O}_{A}$ followed by $\mathscr{O}_{B}$, and $\langle\mathscr{O}_{B}\,,\mathscr{O}_{A}\rangle$ is the two-time expectation value associated with the time reversal of the unitary dynamics, where a measurement of $\mathscr{O}_{B}$ precedes a measurement of $\mathscr{O}_{A}$. In this work, we show that a quantum Bayes' rule implies a time symmetry for two-time expectation values associated with open quantum systems, which evolve according to a general quantum channel between measurements. Such results are in contrast with the view that processes associated with open quantum systems -- which may lose information to their environment -- are not reversible in any operational sense. We give an example of such time-symmetric correlations for the amplitude-damping channel, and we propose an experimental protocol for the potential verification of the theoretical predictions associated with our results.
- [11] arXiv:2407.11762 (cross-list from cs.LG) [pdf, other]
-
Title: Self-Duplicating Random Walks for Resilient Decentralized Learning on GraphsSubjects: Machine Learning (cs.LG); Distributed, Parallel, and Cluster Computing (cs.DC); Information Theory (cs.IT); Applications (stat.AP)
Consider the setting of multiple random walks (RWs) on a graph executing a certain computational task. For instance, in decentralized learning via RWs, a model is updated at each iteration based on the local data of the visited node and then passed to a randomly chosen neighbor. RWs can fail due to node or link failures. The goal is to maintain a desired number of RWs to ensure failure resilience. Achieving this is challenging due to the lack of a central entity to track which RWs have failed to replace them with new ones by forking (duplicating) surviving ones. Without duplications, the number of RWs will eventually go to zero, causing a catastrophic failure of the system. We propose a decentralized algorithm called DECAFORK that can maintain the number of RWs in the graph around a desired value even in the presence of arbitrary RW failures. Nodes continuously estimate the number of surviving RWs by estimating their return time distribution and fork the RWs when failures are likely to happen. We present extensive numerical simulations that show the performance of DECAFORK regarding fast detection and reaction to failures. We further present theoretical guarantees on the performance of this algorithm.
- [12] arXiv:2407.11931 (cross-list from math.CO) [pdf, html, other]
-
Title: Shift-invariant functions and almost liftingsComments: 15 pagesSubjects: Combinatorics (math.CO); Cryptography and Security (cs.CR); Information Theory (cs.IT)
We investigate shift-invariant vectorial Boolean functions on $n$~bits that are lifted from Boolean functions on $k$~bits, for $k\leq n$. We consider vectorial functions that are not necessarily permutations, but are, in some sense, almost bijective. In this context, we define an almost lifting as a Boolean function for which there is an upper bound on the number of collisions of its lifted functions that does not depend on $n$. We show that if a Boolean function with diameter $k$ is an almost lifting, then the maximum number of collisions of its lifted functions is $2^{k-1}$ for any $n$. Moreover, we search for functions in the class of almost liftings that have good cryptographic properties and for which the non-bijectivity does not cause major security weaknesses. These functions generalize the well-known map $\chi$ used in the Keccak hash function.
- [13] arXiv:2407.11932 (cross-list from math.ST) [pdf, html, other]
-
Title: Impossibility of latent inner product recovery via rate distortionSubjects: Statistics Theory (math.ST); Information Theory (cs.IT); Social and Information Networks (cs.SI); Machine Learning (stat.ML)
In this largely expository note, we present an impossibility result for inner product recovery in a random geometric graph or latent space model using the rate-distortion theory. More precisely, suppose that we observe a graph $A$ on $n$ vertices with average edge density $p$ generated from Gaussian or spherical latent locations $z_1, \dots, z_n \in \mathbb{R}^d$ associated with the $n$ vertices. It is of interest to estimate the inner products $\langle z_i, z_j \rangle$ which represent the geometry of the latent points. We prove that it is impossible to recover the inner products if $d \gtrsim n h(p)$ where $h(p)$ is the binary entropy function. This matches the condition required for positive results on inner product recovery in the literature. The proof follows the well-established rate-distortion theory with the main technical ingredient being a lower bound on the rate-distortion function of the Wishart distribution which is interesting in its own right.
Cross submissions for Wednesday, 17 July 2024 (showing 6 of 6 entries )
- [14] arXiv:2312.13415 (replaced) [pdf, html, other]
-
Title: Higher-Order Staircase CodesComments: Submitted to IEEE Transactions on Information TheorySubjects: Information Theory (cs.IT)
We generalize staircase codes and tiled diagonal zipper codes, preserving their key properties while allowing each coded symbol to be protected by arbitrarily many component codewords rather than only two. This generalization which we term "higher-order staircase codes" arises from the marriage of two distinct combinatorial objects: difference triangle sets and finite-geometric nets, which have typically been applied separately to code design. We demonstrate one possible realization of these codes, obtaining powerful, high-rate, low-error-floor, and low-complexity coding schemes based on simple iterative syndrome-domain decoding of coupled Hamming component codes. We anticipate that the proposed codes could improve performance--complexity--latency tradeoffs in high-throughput communications applications, most notably fiber-optic, in which classical staircase codes and zipper codes have been applied. We consider the construction of difference triangle sets having minimum scope and sum-of-lengths, which lead to memory-optimal realizations of higher-order staircase codes. These results also enable memory reductions for early families of convolutional codes constructed from difference triangle sets.
- [15] arXiv:2401.11383 (replaced) [pdf, html, other]
-
Title: Entropic Conditional Central Limit Theorem and Hadamard CompressionComments: 40 pagesSubjects: Probability (math.PR); Information Theory (cs.IT)
We make use of an entropic property to establish a convergence theorem (Main Theorem), which reveals that the conditional entropy measures the asymptotic Gaussianity. As an application, we establish the {\it entropic conditional central limit theorem} (CCLT), which is stronger than the classical CCLT. As another application, we show that continuous input under iterated Hadamard transform, almost every distribution of the output conditional on the values of the previous signals will tend to Gaussian, and the conditional distribution is in fact insensitive to the condition. The results enable us to make a theoretic study concerning Hadamard compression, which provides a solid theoretical analysis supporting the simulation results in previous literature. We show also that the conditional Fisher information can be used to measure the asymptotic Gaussianity.