共找到 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
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 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
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.
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.
Achievable and converse bounds for general channels and mismatched decoding are derived. The direct (achievable) bound is derived using random coding and the analysis is tight up to factor 2. The converse is given in term of the achievable bound and the factor between them is given. This gives performance of the best rate-R code with possible mismatched decoding metric over a general channel, up to the factor that is identified. In the matched case we show that the converse equals the minimax meta-converse of Polyanskiy et al.
In this paper, transmission over time-selective, flat fading relay channels is studied. It is assumed that channel fading coefficients are not known a priori. Transmission takes place in two phases: network training phase and data transmission phase. In the training phase, pilot symbols are sent and the receivers employ single-pilot MMSE estimation or noncausal Wiener filter to learn the channel. Amplify-and-Forward (AF) and Decode-and-Forward (DF) techniques are considered in the data transmission phase and achievable rate expressions are obtained. The training period, and data and training power allocations are jointly optimized by using the achievable rate expressions. Numerical results are obtained considering Gauss-Markov and lowpass fading models. Achievable rates are computed and energy-per-bit requirements are investigated. The optimal power distributions among pilot and data symbols are provided.
Analyzing the achievable rate of molecular communication via diffusion (MCvD) inherits intricacies due to its nature: MCvD channel has memory, and the heavy tail of the signal causes inter symbol interference (ISI). Therefore, using Shannon's channel capacity formulation for memoryless channel is not appropriate for the MCvD channel. Instead, a more general achievable rate formulation and system model must be considered to make this analysis accurately. In this letter, we propose an effective ISI-aware MCvD modeling technique in 3-D medium and properly analyze the achievable rate.
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.
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$.
Schein and Gallager introduced the Gaussian parallel relay channel in 2000. They proposed the Amplify-and-Forward (AF) and the Decode-and-Forward (DF) strategies for this channel. For a long time, the best known achievable rate for this channel was based on the AF and DF with time sharing (AF-DF). Recently, a Rematch-and-Forward (RF) scheme for the scenario in which different amounts of bandwidth can be assigned to the first and second hops were proposed. In this paper, we propose a \emph{Combined Amplify-and-Decode Forward (CADF)} scheme for the Gaussian parallel relay channel. We prove that the CADF scheme always gives a better achievable rate compared to the RF scheme, when there is a bandwidth mismatch between the first hop and the second hop. Furthermore, for the equal bandwidth case (Schein's setup), we show that the time sharing between the CADF and the DF schemes (CADF-DF) leads to a better achievable rate compared to the time sharing between the RF and the DF schemes (RF-DF) as well as the AF-DF.
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.
暂无摘要（点击查看原文获取完整内容）