This paper considers the performance of long Reed-Muller (RM) codes transmitted over binary memoryless symmetric (BMS) channels under bitwise maximum-a-posteriori decoding. Its main result is that the family of binary RM codes achieves capacity on any BMS channel with respect to bit-error rate. This resolves a long-standing open problem that connects information theory and error-correcting codes. In contrast with the earlier result for the binary erasure channel, the new proof does not rely on hypercontractivity. Instead, it combines a nesting property of RM codes with new information inequalities relating the generalized extrinsic information transfer function and the extrinsic minimum mean-squared error.
相關內容
Let $W$ be a binary-input memoryless symmetric (BMS) channel with Shannon capacity $I(W)$ and fix any $\alpha > 0$. We construct, for any sufficiently small $\delta > 0$, binary linear codes of block length $O(1/\delta^{2+\alpha})$ and rate $I(W)-\delta$ that enable reliable communication on $W$ with quasi-linear time encoding and decoding. Shannon's noisy coding theorem established the \emph{existence} of such codes (without efficient constructions or decoding) with block length $O(1/\delta^2)$. This quadratic dependence on the gap $\delta$ to capacity is known to be best possible. Our result thus yields a constructive version of Shannon's theorem with near-optimal convergence to capacity as a function of the block length. This resolves a central theoretical challenge associated with the attainment of Shannon capacity. Previously such a result was only known for the erasure channel. Our codes are a variant of Ar{\i}kan's polar codes based on multiple carefully constructed local kernels, one for each intermediate channel that arises in the decoding. A crucial ingredient in the analysis is a strong converse of the noisy coding theorem when communicating using random linear codes on arbitrary BMS channels. Our converse theorem shows extreme unpredictability of even a single message bit for random coding at rates slightly above capacity.
We investigate the problem of message transmission over time-varying single-user multiple-input multiple-output (MIMO) Rayleigh fading channels with average power constraint and with complete channel state information available at the receiver side (CSIR). To describe the channel variations over the time, we consider a first-order Gauss-Markov model. We completely solve the problem by giving a single-letter characterization of the channel capacity in closed form and by providing a rigorous proof of it.
We propose a new family of spatially coupled product codes, called sub-block rearranged staircase (SR-staircase) codes. Each SR-staircase code block is constructed by encoding rearranged preceding code blocks, where the rearrangement involves sub-blocks decomposition and transposition. The major advantage of the proposed construction over the conventional staircase construction is that it enables to employ stronger algebraic component codes to achieve better waterfall and error floor performance with lower miscorrection probability under low-complexity iterative bounded distance decoding (iBDD) while having the same code rate and similar blocklength as the conventional staircase codes. We characterize the decoding threshold of the proposed codes under iBDD by using density evolution and also derive the conditions under which they achieve a better decoding threshold than that of the conventional staircase codes. Further, we investigate the error floor performance by analyzing the contributing error patterns and their multiplicities. Both theoretical and simulation results show that SR-staircase codes outperform the conventional staircase codes in terms of waterfall and error floor while the performance can be further improved by using a large coupling width.
A novel recursive list decoding (RLD) algorithm of Reed-Muller (RM) codes based on successive permutations (SP) of the codeword is presented. An SP scheme that performs maximum likelihood decoding on a subset of the symmetry group of RM codes is first proposed to carefully select a good codeword permutation on the fly. Then, the proposed SP technique is applied to an improved RLD algorithm that initializes different decoding paths with random codeword permutations, which are sampled from the full symmetry group of RM codes. Finally, an efficient latency reduction scheme is introduced that virtually preserves the error-correction performance of the proposed decoder. Simulation results demonstrate that for the RM code of size $256$ with $163$ information bits, the proposed decoder reduces $39\%$ of the computational complexity, $36\%$ of the decoding latency, and $74\%$ of the memory requirement of the state-of-the-art RLD algorithm with list size $64$ that also uses the permutations from the full symmetry group of RM codes, while only incurring an error-correction performance degradation of $0.1$ dB at the target frame error rate of $10^{-3}$.
In this article, we present a new construction of evaluation codes in the Hamming metric, which we call twisted Reed-Solomon codes. Whereas Reed-Solomon (RS) codes are MDS codes, this need not be the case for twisted RS codes. Nonetheless, we show that our construction yields several families of MDS codes. Further, for a large subclass of (MDS) twisted RS codes, we show that the new codes are not generalized RS codes. To achieve this, we use properties of Schur squares of codes as well as an explicit description of the dual of a large subclass of our codes. We conclude the paper with a description of a decoder, that performs very well in practice as shown by extensive simulation results.
In this paper, we investigate the secure rate-splitting for the two-user multiple-input multiple-output (MIMO) broadcast channel with imperfect channel state information at the transmitter (CSIT) and a multiple-antenna jammer, where each receiver has equal number of antennas and the jammer has perfect channel state information (CSI). Specifically, we design the secure rate-splitting multiple-access in this scenario, where the security of splitted private and common messages is ensured by precoder design with joint nulling and aligning the leakage information, regarding to different antenna configurations. As a result, we show that the sum-secure degrees-of-freedom (SDoF) achieved by secure rate-splitting outperforms that by conventional zero-forcing. Therefore, we validate the superiority of rate-splitting for the secure purpose in the two-user MIMO broadcast channel with imperfect CSIT and a jammer.
We consider a parallel server system with so-called cancel-on-completion redundancy. There are $n$ servers and multiple job classes $j$. An arriving class $j$ job consists of $d_j$ components, placed on a randomly selected subset of servers; the job service is complete as soon as $k_j$ components out of $d_j$ (with $k_j \le d_j$) complete their service, at which point the unfinished service of all remaining $d_j-k_j$ components is canceled. The system is in general non-work-conserving, in the sense that the average amount of new workload added to the system by an arriving class $j$ job is not defined a priori -- it depends on the system state at the time of arrival. This poses the main challenge for the system analysis. For the system with a fixed number of servers $n$ our main results include: the stability properties; the property that the stationary distributions of the relative server workloads remain tight, uniformly in the system load. We also consider the mean-field asymptotic regime when $n\to\infty$ while each job class arrival rate per server remains constant. The main question we address here is: under which conditions the steady-state asymptotic independence (SSAI) of server workloads holds, and in particular when the SSAI for the full range of loads (SSAI-FRL) holds. (Informally, SSAI-FRL means that SSAI holds for any system load less than $1$.) We obtain sufficient conditions for SSAI and SSAI-FRL. In particular, we prove that SSAI-FRL holds in the important special case when job components of each class $j$ are i.i.d. with an increasing-hazard-rate distribution.
We outline a geometrical correspondence between capacity and effective free energy minima of discrete memoryless channels. This correspondence informs the behavior of a timescale that is important in effective statistical physics.
To improve the search efficiency for Neural Architecture Search (NAS), One-shot NAS proposes to train a single super-net to approximate the performance of proposal architectures during search via weight-sharing. While this greatly reduces the computation cost, due to approximation error, the performance prediction by a single super-net is less accurate than training each proposal architecture from scratch, leading to search inefficiency. In this work, we propose few-shot NAS that explores the choice of using multiple super-nets: each super-net is pre-trained to be in charge of a sub-region of the search space. This reduces the prediction error of each super-net. Moreover, training these super-nets can be done jointly via sequential fine-tuning. A natural choice of sub-region is to follow the splitting of search space in NAS. We empirically evaluate our approach on three different tasks in NAS-Bench-201. Extensive results have demonstrated that few-shot NAS, using only 5 super-nets, significantly improves performance of many search methods with slight increase of search time. The architectures found by DARTs and ENAS with few-shot models achieved 88.53% and 86.50% test accuracy on CIFAR-10 in NAS-Bench-201, significantly outperformed their one-shot counterparts (with 54.30% and 54.30% test accuracy). Moreover, on AUTOGAN and DARTS, few-shot NAS also outperforms previously state-of-the-art models.
In this paper we study the convergence of generative adversarial networks (GANs) from the perspective of the informativeness of the gradient of the optimal discriminative function. We show that GANs without restriction on the discriminative function space commonly suffer from the problem that the gradient produced by the discriminator is uninformative to guide the generator. By contrast, Wasserstein GAN (WGAN), where the discriminative function is restricted to $1$-Lipschitz, does not suffer from such a gradient uninformativeness problem. We further show in the paper that the model with a compact dual form of Wasserstein distance, where the Lipschitz condition is relaxed, also suffers from this issue. This implies the importance of Lipschitz condition and motivates us to study the general formulation of GANs with Lipschitz constraint, which leads to a new family of GANs that we call Lipschitz GANs (LGANs). We show that LGANs guarantee the existence and uniqueness of the optimal discriminative function as well as the existence of a unique Nash equilibrium. We prove that LGANs are generally capable of eliminating the gradient uninformativeness problem. According to our empirical analysis, LGANs are more stable and generate consistently higher quality samples compared with WGAN.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191