共找到 20 条结果
Graph burning is a discrete-time process on graphs where vertices are sequentially activated and burning vertices cause their neighbours to burn over time. In this work, we focus on a dynamic setting in which the graph grows over time, and at each step we burn vertices in the growing grid $G_n = [-f(n),f(n)]^2$. We investigate the set of achievable burning densities for functions of the form $f(n)=\lceil cn^α\rceil$, where $α\ge 1$ and $c>0$. We show that for $α=1$, the set of achievable densities is $[1/(2c^2),1]$, for $1<α<3/2$, every density in $[0,1]$ is achievable, and for $α=3/2$, the set of achievable densities is $[0,(1+\sqrt{6}c)^{-2}]$.
Guessing random additive noise decoding (GRAND) has received widespread attention recently, and among its variants, ordered reliability bits GRAND (ORBGRAND) is particularly attractive due to its efficient utilization of soft information and its amenability to hardware implementation. It has been recently shown that ORBGRAND is almost capacity-achieving in additive white Gaussian noise channels under antipodal input. In this work, we first extend the analysis of ORBGRAND achievable rate to memoryless binary-input bit channels with general output conditional probability distributions. The analytical result also sheds insight into understanding the gap between the ORBGRAND achievable rate and the channel mutual information. As an application of the analysis, we study the ORBGRAND achievable rate of bit-interleaved coded modulation (BICM). Numerical results indicate that for BICM, the gap between the ORBGRAND achievable rate and the channel mutual information is typically small, and hence suggest the feasibility of ORBGRAND for channels with high-order coded modulation schemes.
This paper studies achievable rates of nanopore-based DNA storage when nanopore signals are decoded using a tractable channel model that does not rely on a basecalling algorithm. Specifically, the noisy nanopore channel (NNC) with the Scrappie pore model generates average output levels via i.i.d. geometric sample duplications corrupted by i.i.d. Gaussian noise (NNC-Scrappie). Simplified message passing algorithms are derived for efficient soft decoding of nanopore signals using NNC-Scrappie. Previously, evaluation of this channel model was limited by the lack of DNA storage datasets with nanopore signals included. This is solved by deriving an achievable rate based on the dynamic time-warping (DTW) algorithm that can be applied to genomic sequencing datasets subject to constraints that make the resulting rate applicable to DNA storage. Using a publicly-available dataset from Oxford Nanopore Technologies (ONT), it is demonstrated that coding over multiple DNA strands of $100$ bases in length and decoding with the NNC-Scrappie decoder can achieve rates of at least $0.64-1.18$ bits per base, depending on the channel quality of the nanopore that is chosen in the sequencing device per c
Examples of achievable Cantorvals are constructed with reversed Kakeya conditions only on a set of asymptotic density zero which answers in positive the Problem 5.2 from Marchwicki and Miska (2021). Additionally, the Lebesgue measure of the boundaries of these Cantorvals is found to be zero which does not answer the still open problem of existence of achievable Cantorvals with boundaries of positive measure.
The generalized linear system (GLS) has been widely used in wireless communications to evaluate the effect of nonlinear preprocessing on receiver performance. Generalized approximation message passing (AMP) is a state-of-the-art algorithm for the signal recovery of GLS, but it was limited to measurement matrices with independent and identically distributed (IID) elements. To relax this restriction, generalized orthogonal/vector AMP (GOAMP/GVAMP) for unitarily-invariant measurement matrices was established, which has been proven to be replica Bayes optimal in uncoded GLS. However, the information-theoretic limit of GOAMP/GVAMP is still an open challenge for arbitrary input distributions due to its complex state evolution (SE). To address this issue, in this paper, we provide the achievable rate analysis of GOAMP/GVAMP in GLS, establishing its information-theoretic limit (i.e., maximum achievable rate). Specifically, we transform the fully-unfolded state evolution (SE) of GOAMP/GVAMP into an equivalent single-input single-output variational SE (VSE). Using the VSE and the mutual information and minimum mean-square error (I-MMSE) lemma, the achievable rate of GOAMP/GVAMP is derived. M
For the two-user multiple-input multiple-output (MIMO) broadcast channel with delayed channel state information at the transmitter (CSIT) and arbitrary antenna configurations, all the degrees-of-freedom (DoF) regions are obtained. However, for the three-user MIMO broadcast channel with delayed CSIT and arbitrary antenna configurations, the DoF region of order-2 messages is still unclear and only a partial achievable DoF region of order-1 messages is obtained, where the order-2 messages and order-1 messages are desired by two receivers and one receiver, respectively. In this paper, for the three-user MIMO broadcast channel with delayed CSIT and arbitrary antenna configurations, we first design transmission schemes for order-2 messages and order-1 messages. Next, we propose to analyze the achievable DoF region of transmission scheme by transformation approach. In particular, we transform the decoding condition of transmission scheme w.r.t. phase duration into the achievable DoF region w.r.t. achievable DoF, through achievable DoF tuple expression connecting phase duration and achievable DoF. As a result, the DoF region of order-2 messages is characterized and an achievable DoF region
The K-user flat fading MIMO interference channel with J instantaneous relays (KICJR) is considered. In the KICJR, the effective channel between sources and destinations including the relays has certain structure and is non-generic. For non-generic channels, the achievable degrees of freedom (DoF) is still unknown. Lee and Wang showed that by using the aligned interference neutralization scheme 3/2 degrees of freedom is achievable in a 2IC1R system, which is 50% more than the 2-user interference channel. But the DoF performance and achievable schemes for other KICJR networks are not investigated in literature. In this paper we devise an achievable scheme called restricted interference alignment for instantaneous-relay aided interference channels. Also, to find insights to the maximum achievable degrees of freedom we develop linear beamforming based on the mean square error (MSE) minimization as an achievable scheme. Furthermore, we present upper-bounds on the maximum achievable degrees of freedom by investigating the properness of the interference alignment equation system. The numerical results show that the DoF performance of the proposed restricted interference alignment scheme a
This paper considers the achievable rates and decoding complexity of low-density parity-check (LDPC) codes over statistically independent parallel channels. The paper starts with the derivation of bounds on the conditional entropy of the transmitted codeword given the received sequence at the output of the parallel channels; the component channels are considered to be memoryless, binary-input, and output-symmetric (MBIOS). These results serve for the derivation of an upper bound on the achievable rates of ensembles of LDPC codes under optimal maximum-likelihood (ML) decoding when their transmission takes place over parallel MBIOS channels. The paper relies on the latter bound for obtaining upper bounds on the achievable rates of ensembles of randomly and intentionally punctured LDPC codes over MBIOS channels. The paper also provides a lower bound on the decoding complexity (per iteration) of ensembles of LDPC codes under message-passing iterative decoding over parallel MBIOS channels; the bound is given in terms of the gap between the rate of these codes for which reliable communication is achievable and the channel capacity. The paper presents a diagram which shows interconnection
What sets A \subset Z^n can be written in the form (K-K) \cap Z^n, where K is a compact subset of R^n such that K+Z^n=R^n? Such sets A are called achievable, and it is known that if A is achievable, then < A >=Z^n. This condition completely characterizes achievable sets for n=1, but not much is known for n \ge 2. We attempt to characterize achievable sets further by showing that with any finite, symmetric set A \subset Z^n containing zero, we may associate a graph G(A). Then if A is achievable, we show the set associated to some connected component of G(A) is achievable. In two dimensions, we can strengthen this theorem further. Further generalizations and open questions are discussed. Throughout, the language and formalism of algebraic topology are useful.
In this paper, we study the achievable rate region of Gaussian multiuser channels with the messages transmitted being from finite input alphabets and the outputs being {\em quantized at the receiver}. In particular, we focus on the achievable rate region of $i)$ Gaussian broadcast channel (GBC) and $ii)$ Gaussian multiple access channel (GMAC). First, we study the achievable rate region of two-user GBC when the messages to be transmitted to both the users take values from finite signal sets and the received signal is quantized at both the users. We refer to this channel as {\em quantized broadcast channel (QBC)}. We observe that the capacity region defined for a GBC does not carry over as such to QBC. We show that the optimal decoding scheme for GBC (i.e., high SNR user doing successive decoding and low SNR user decoding its message alone) is not optimal for QBC. We then propose an achievable rate region for QBC based on two different schemes. We present achievable rate region results for the case of uniform quantization at the receivers. Next, we investigate the achievable rate region of two-user GMAC with finite input alphabet and quantized receiver output. We refer to this chann
This paper investigates the achievable sum rate of multiple-input multiple-output (MIMO) wireless systems employing linear minimum mean-squared error (MMSE) receivers. We present a new analytic framework which unveils an interesting connection between the achievable sum rate with MMSE receivers and the ergodic mutual information achieved with optimal receivers. This simple but powerful result enables the vast prior literature on ergodic MIMO mutual information to be directly applied to the analysis of MMSE receivers. The framework is particularized to various Rayleigh and Rician channel scenarios to yield new exact closed-form expressions for the achievable sum rate, as well as simplified expressions in the asymptotic regimes of high and low signal to noise ratios. These expressions lead to the discovery of key insights into the performance of MIMO MMSE receivers under practical channel conditions.
We present an achievable rate region for the general three user discrete memoryless broadcast channel, based on nested coset codes. We characterize 3-to-1 discrete broadcast channels, a class of broadcast channels for which the best known coding technique\footnote{We henceforth refer to this as Marton's coding for three user discrete broadcast channel.}, which is obtained by a natural generalization of that proposed by Marton for the general two user discrete broadcast channel, is strictly sub-optimal. In particular, we identify a novel 3-to-1 discrete broadcast channel for which Marton's coding is \textit{analytically} proved to be strictly suboptimal. We present achievable rate regions for the general 3-to-1 discrete broadcast channels, based on nested coset codes, that strictly enlarge Marton's rate region for the aforementioned channel. We generalize this to present achievable rate region for the general three user discrete broadcast channel. Combining together Marton's coding and that proposed herein, we propose the best known coding technique, for a general three user discrete broadcast channel.
We consider the problem of communication over a three user discrete memoryless interference channel ($3-$IC). The current known coding techniques for communicating over an arbitrary $3-$IC are based on message splitting, superposition coding and binning using independent and identically distributed (iid) random codebooks. In this work, we propose a new ensemble of codes - partitioned coset codes (PCC) - that possess an appropriate mix of empirical and algebraic closure properties. We develop coding techniques that exploit algebraic closure property of PCC to enable efficient communication over $3-$IC. We analyze the performance of the proposed coding technique to derive an achievable rate region for the general discrete $3-$IC. Additive and non-additive examples are identified for which the derived achievable rate region is the capacity, and moreover, strictly larger than current known largest achievable rate regions based on iid random codebooks.
The problem of reliable communication over the multiple-access channel (MAC) with states is investigated. We propose a new coding scheme for this problem which uses quasi-group codes (QGC). We derive a new computable single-letter characterization of the achievable rate region. As an example, we investigate the problem of doubly-dirty MAC with modulo-$4$ addition. It is shown that the sum-rate $R_1+R_2=1$ bits per channel use is achievable using the new scheme. Whereas, the natural extension of the Gel'fand-Pinsker scheme, sum-rates greater than $0.32$ are not achievable.
An achievable rate region for the Gaussian interference channel is derived using Sato's modified frequency division multiplexing idea and a special case of Han and Kobayashi's rate region (denoted by $\Gmat^\prime$). We show that the new inner bound includes $\Gmat^\prime$, Sason's rate region $\Dmat$, as well as the achievable region via TDM/FDM, as its subsets. The advantage of this improved inner bound over $\Gmat^\prime$ arises due to its inherent ability to utilize the whole transmit power range on the real line without violating the power constraint. We also provide analysis to examine the conditions for the new achievable region to strictly extend $\Gmat^\prime$.
In this work, we consider a discrete-time stationary Rayleigh flat-fading channel with unknown channel state information at transmitter and receiver. The law of the channel is presumed to be known to the receiver. In addition, we assume the power spectral density (PSD) of the fading process to be compactly supported. For i.i.d. zero-mean proper Gaussian input distributions, we investigate the achievable rate. One of the main contributions is the derivation of two new upper bounds on the achievable rate with zero-mean proper Gaussian input symbols. The first one holds only for the special case of a rectangular PSD and depends on the SNR and the spread of the PSD. Together with a lower bound on the achievable rate, which is achievable with i.i.d. zero-mean proper Gaussian input symbols, we have found a set of bounds which is tight in the sense that their difference is bounded. Furthermore, we show that the high SNR slope is characterized by a pre-log of 1-2f_d, where f_d is the normalized maximum Doppler frequency. This pre-log is equal to the high SNR pre-log of the peak power constrained capacity. Furthermore, we derive an alternative upper bound on the achievable rate with i.i.d.
In this paper we look at the topological type of algebraic sum of achievement sets. We show that there is a Cantorval such that the algebraic sum of its $k$ copies is still a Cantorval for any $k \in \mathbb{N}$. We also prove that for any $m,p \in (\mathbb{N}\setminus \{1\}) \cup \{\infty\}$, $p \geq m$, the algebraic sum of $k$ copies of a Cantor set can transit from a Cantor set to a Cantorval for $k=m$ and then to an interval for $k=p$. These two main results are based on a new characterization of sequences whose achievement sets are Cantorvals. We also define a new family of achievable Cantorvals which are not generated by multigeometric series. In the final section we discuss various decompositions of sequences related to the topological typology of achievement sets.
We study the mismatched successive refinement problem where one uses Gaussian codebooks to compress an arbitrary memoryless source with successive minimum Euclidean distance encoding under the quadratic distortion measure. Specifically, we derive achievable refined asymptotics under both the joint excess-distortion probability (JEP) and the separate excess-distortion probabilities (SEP) criteria. For both second-order and moderate deviations asymptotics, we consider two types of codebooks: the spherical codebook where each codeword is drawn independently and uniformly from the surface of a sphere and the i.i.d. Gaussian codebook where each component of each codeword is drawn independently from a Gaussian distribution. We establish the achievable second-order rate-region under JEP and we show that under SEP any memoryless source satisfying mild moment conditions is strongly successively refinable. When specialized to a Gaussian memoryless source (GMS), our results provide an alternative achievability proof with specific code design. We show that under JEP and SEP, the same moderate deviations constant is achievable. For large deviations asymptotics, we only consider the i.i.d. Gauss
We prove that the ensemble the nested coset codes built on finite fields achieves the capacity of arbitrary discrete memoryless point-to-point channels. Exploiting it's algebraic structure, we develop a coding technique for communication over general discrete multiple access channel with channel state information distributed at the transmitters. We build an algebraic coding framework for this problem using the ensemble of Abelian group codes and thereby derive a new achievable rate region. We identify non-additive and non-symmteric examples for which the proposed achievable rate region is strictly larger than the one achievable using random unstructured codes.
In a premier paper on the information-theoretic analysis of a two-user cognitive interference channel(CIC), Devroye et al. presented an achievable rate region for the two-user discrete memoryless CIC. The coding scheme proposed by Devroye et al. is correct but unfortunately some rate-terms in the derived achievable rate region are incorrect (in fact incomplete) because of occurring some mistakes in decoding and analysis of error probability. We correct and complete the wrong rate-terms and thereby show that the corrected achievable rate region includes the rate region presented in.