Information Theory (cs.IT)

Abstract: Various precoders have been recently studied by the wireless community to combat the channel fading effects. Two prominent precoders are implemented with the discrete Fourier transform (DFT) and Walsh-Hadamard transform (WHT). The WHT precoder is implemented with less complexity since it does not need complex multiplications. Also, spreading can be applied sparsely to decrease the transceiver complexity, leading to sparse DFT (SDFT) and sparse Walsh-Hadamard (SWH). Another relevant topic is the design of iterative receivers that deal with inter-symbol-interference (ISI). In particular, many detectors based on expectation propagation (EP) have been proposed recently for channels with high levels of ISI. An alternative is the maximum a-posterior (MAP) detector, although it leads to unfeasible high complexity in many cases. In this paper, we provide a relatively low-complexity \textcolor{black}{computation} of the MAP detector for the SWH. We also propose two \textcolor{black}{feasible methods} based on the Log-MAP and Max-Log-MAP. Additionally, the DFT, SDFT and SWH precoders are compared using an EP-based receiver with one-tap FD equalization. Lastly, SWH-Max-Log-MAP is compared to the (S)DFT with EP-based receiver in terms of performance and complexity. The results show that the proposed SWH-Max-Log-MAP has a better performance and complexity trade-off for QPSK and 16-QAM under highly selective channels, but has unfeasible complexity for higher QAM orders.

Abstract: Orthogonal time sequency multiplexing (OTSM) has been recently proposed as a single-carrier (SC) waveform offering similar bit error rate (BER) to multi-carrier orthogonal time frequency space (OTFS) modulation in doubly-spread channels under high mobilities; however, with much lower complexity making OTSM a promising candidate for low-power millimeter-wave (mmWave) vehicular communications in 6G wireless networks. In this paper, the performance of OTSM-based homodyne transceiver is explored under hardware impairments (HIs) including in-phase and quadrature imbalance (IQI), direct current offset (DCO), phase noise, power amplifier non-linearity, carrier frequency offset, and synchronization timing offset. First, the discrete-time baseband signal model is obtained in vector form under the mentioned HIs. Then, the system input-output relations are derived in time, delay-time, and delay-sequency (DS) domains in which the parameters of HIs are incorporated. Analytical studies demonstrate that noise stays white Gaussian and effective channel matrix is sparse in the DS domain under HIs. Also, DCO appears as a DC signal at receiver interfering with only the zero sequency over all delay taps in the DS domain; however, IQI redounds to self-conjugated fully-overlapping sequency interference. Simulation results reveal the fact that with no HI compensation (HIC), not only OTSM outperforms plain SC waveform but it performs close to uncompensated OTFS system; however, HIC is essentially needed for OTSM systems operating in mmWave and beyond frequency bands.

Abstract: This paper investigates double RIS-assisted MIMO communication systems over Rician fading channels with finite scatterers, spatial correlation, and the existence of a double-scattering link between the transceiver. First, the statistical information is driven in closed form for the aggregated channels, unveiling various influences of the system and environment on the average channel power gains. Next, we study two active and passive beamforming designs corresponding to two objectives. The first problem maximizes channel capacity by jointly optimizing the active precoding and combining matrices at the transceivers and passive beamforming at the double RISs subject to the transmitting power constraint. In order to tackle the inherently non-convex issue, we propose an efficient alternating optimization algorithm (AO) based on the alternating direction method of multipliers (ADMM). The second problem enhances communication reliability by jointly training the encoder and decoder at the transceivers and the phase shifters at the RISs. Each neural network representing a system entity in an end-to-end learning framework is proposed to minimize the symbol error rate of the detected symbols by controlling the transceiver and the RISs phase shifts. Numerical results verify our analysis and demonstrate the superior improvements of phase shift designs to boost system performance.

Abstract: In this paper, we present a non-coherent energy detection scheme for spatial modulation (SM) systems. In particular, the use of SM is motivated by its low-complexity implementation in comparison to multiple-input multiple-output (MIMO) systems, achieved through the activation of a single antenna during transmission. Moreover, energy detection-based communications restrict the channel state information to the magnitude of the fading gains. This consideration makes the design applicable for low-cost low-powered devices since phase estimation and its associated circuitry are avoided. We derive an energy detection metric for a multi-antenna receiver based on the maximum-likelihood (ML) criterion. By considering a biased pulse amplitude modulation, we develop an analytical framework for the SM symbol error rate at high signal-to-noise ratios. Numerical results show that the diversity order is proportional to half the number of receive antennas; this result stems from having partial receiver channel knowledge. In addition, we compare the performance of the proposed scheme with that of the coherent ML receiver and show that the SM energy detector outperforms its coherent counterpart in certain scenarios, particularly when utilizing non-negative constellations. Ultimately, we implement an SM testbed using software-defined radio devices and provide experimental error rate measurements that validate our theoretical contribution.

Abstract: It was shown by Boukerrou et al.~\cite{Bouk} [IACR Trans. Symmetric Cryptol. 1 2020, 331--362] that the $F$-boomerang uniformity (which is the same as the second-order zero differential uniformity in even characteristic) of perfect nonlinear functions is~$0$ on $\F_{p^n}$ ($p$ prime) and the one of almost perfect nonlinear functions on $\F_{2^n}$ is~$0$. It is natural to inquire what happens with APN or other low differential uniform functions in even and odd characteristics. Here, we explicitly determine the second-order zero differential spectra of several maps with low differential uniformity. In particular, we compute the second-order zero differential spectra for some almost perfect nonlinear (APN) functions, pushing further the study started in Boukerrou et al.~\cite{Bouk} and continued in Li et al. \cite{LYT} [Cryptogr. Commun. 14.3 (2022), 653--662], and it turns out that our considered functions also have low second-order zero differential uniformity.

Abstract: In this paper, we introduce a variation of the group testing problem capturing the idea that a positive test requires a combination of multiple ``types'' of item. Specifically, we assume that there are multiple disjoint \emph{semi-defective sets}, and a test is positive if and only if it contains at least one item from each of these sets. The goal is to reliably identify all of the semi-defective sets using as few tests as possible, and we refer to this problem as \textit{Concomitant Group Testing} (ConcGT). We derive a variety of algorithms for this task, focusing primarily on the case that there are two semi-defective sets. Our algorithms are distinguished by (i) whether they are deterministic (zero-error) or randomized (small-error), and (ii) whether they are non-adaptive, fully adaptive, or have limited adaptivity (e.g., 2 or 3 stages). Both our deterministic adaptive algorithm and our randomized algorithms (non-adaptive or limited adaptivity) are order-optimal in broad scaling regimes of interest, and improve significantly over baseline results that are based on solving a more general problem as an intermediate step (e.g., hypergraph learning).

Abstract: It is disproved the Tokareva's conjecture that any balanced boolean function of appropriate degree is a derivative of some bent function. This result is based on new upper bounds for the numbers of bent and plateaued functions.

Abstract: The problem of transmitting a parameter value over an additive white Gaussian noise (AWGN) channel is considered, where, in addition to the transmitter and the receiver, there is a helper that observes the noise non-causally and provides a description of limited rate $R_\mathrm{h}$ to the transmitter and/or the receiver. We derive upper and lower bounds on the optimal achievable $\alpha$-th moment of the estimation error and show that they coincide for small values of $\alpha$ and for low SNR values. The upper bound relies on a recently proposed channel-coding scheme that effectively conveys $R_\mathrm{h}$ bits essentially error-free and the rest of the rate - over the same AWGN channel without help, with the error-free bits allocated to the most significant bits of the quantized parameter. We then concentrate on the setting with a total transmit energy constraint, for which we derive achievability results for both channel coding and parameter modulation for several scenarios: when the helper assists only the transmitter or only the receiver and knows the noise, and when the helper assists the transmitter and/or the receiver and knows both the noise and the message. In particular, for the message-informed helper that assists both the receiver and the transmitter, it is shown that the error probability in the channel-coding task decays doubly exponentially. Finally, we translate these results to those for continuous-time power-limited AWGN channels with unconstrained bandwidth. As a byproduct, we show that the capacity with a message-informed helper that is available only at the transmitter can exceed the capacity of the same scenario when the helper knows only the noise but not the message.

Abstract: With the increase in the number of antennas at base stations (BSs), centralized multi-antenna architectures have encountered scalability problems from excessive interconnection bandwidth to the central processing unit (CPU), as well as increased processing complexity. Thus, research efforts have been directed towards finding decentralized receiver architectures where a part of the processing is performed at the antenna end (or close to it). A recent paper put forth an information-lossless trade-off between level of decentralization (inputs to CPU) and decentralized processing complexity (multiplications per antenna). This trade-off was obtained by studying a newly defined matrix decomposition--the WAX decomposition--which is directly related to the information-lossless processing that should to be applied in a general framework to exploit the trade-off. {The general framework consists of three stages: a set of decentralized filters, a linear combining module, and a processing matrix applied at the CPU; these three stages are linear transformations which can be identified with the three constituent matrices of the WAX decomposition. The previous work was unable to provide explicit constructions for linear combining modules which are valid for WAX decomposition, while it remarked the importance of these modules being sparse with 1s and 0s so they could be efficiently implemented using hardware accelerators.} In this work we present a number of constructions, as well as possible variations of them, for effectively defining linear combining modules which can be used in the WAX decomposition. Furthermore, we show how these structures facilitate decentralized calculation of the WAX decomposition for applying information-lossless processing in architectures with an arbitrary level of decentralization.

Abstract: A coded distributed computing (CDC) system aims to reduce the communication load in the MapReduce framework. Such a system has $K$ nodes, $N$ input files, and $Q$ Reduce functions. Each input file is mapped by $r$ nodes and each Reduce function is computed by $s$ nodes. The objective is to achieve the maximum multicast gain. There are known CDC schemes that achieve optimal communication load. In some prominent known schemes, however, $N$ and $Q$ grow too fast in terms of $K$, greatly reducing their gains in practical scenarios. To mitigate the situation, some asymptotically optimal cascaded CDC schemes with $r=s$ have been proposed by using symmetric designs. In this paper, we put forward new asymptotically optimal cascaded CDC schemes with $r=s$ by using $1$-designs. Compared with earlier schemes from symmetric designs, ours have much smaller computation loads while keeping the other relevant parameters the same. We also obtain new asymptotically optimal cascaded CDC schemes with more flexible parameters compared with previously best-performing schemes.

Abstract: Overlapped arithmetic codes, featured by overlapped intervals, are a variant of arithmetic codes that can be used to implement Slepian-Wolf coding. To analyze overlapped arithmetic codes, we have proposed two theoretical tools: Coset Cardinality Spectrum (CCS) and Hamming Distance Spectrum (HDS). The former describes how source space is partitioned into cosets (equally or unequally), and the latter describes how codewords are structured within each coset (densely or sparsely). However, until now, these two tools are almost parallel to each other, and it seems that there is no intersection between them. The main contribution of this paper is bridging HDS with CCS through a rigorous mathematical proof. Specifically, HDS can be quickly and accurately calculated with CCS in some cases. All theoretical analyses are perfectly verified by simulation results.

Abstract: Quantifying the performance bound of an integrated localization and communication (ILAC) system and the trade-off between communication and localization performance is critical. In this letter, we consider an ILAC system that can perform communication and localization via time-domain or frequency-domain resource allocation. We develop an analytical framework to derive the closed-form expression of the capacity loss versus localization Cramer-Rao lower bound (CRB) loss via time-domain and frequency-domain resource allocation. Simulation results validate the analytical model and demonstrate that frequency-domain resource allocation is preferable in scenarios with a smaller number of antennas at the next generation nodeB (gNB) and a larger distance between user equipment (UE) and gNB, while time-domain resource allocation is preferable in scenarios with a larger number of antennas and smaller distance between UE and the gNB.

Abstract: We introduce a formal framework to study the multiple unicast problem for a coded network in which the network code is linear over a finite field and fixed. We show that the problem corresponds to an interference alignment problem over a finite field. In this context, we establish an outer bound for the achievable rate region and provide examples of networks where the bound is sharp. We finally give evidence of the crucial role played by the field characteristic in the problem.