This paper introduces a random multiple access method for satellite communications, named Network Coding-based Slotted Aloha (NCSA). The goal is to improve diversity of data bursts on a slotted-ALOHA-like channel thanks to error correcting codes and Physical-layer Network Coding (PNC). This scheme can be considered as a generalization of the Contention Resolution Diversity Slotted Aloha (CRDSA) where the different replicas of this system are replaced by the different parts of a single word of an error correcting code. The performance of this scheme is first studied through a density evolution approach. Then, simulations confirm the CRDSA results by showing that, for a time frame of @math slots, the achievable total throughput is greater than @math , where @math is the maximal throughput achieved by a centralized scheme. This paper is a first analysis of the proposed scheme which open several perspectives. The most promising approach is to integrate collided bursts into the decoding process in order to improve the obtained performance.
We have modeled the decoding process by using density evolution methods, classically applied in the context of LDPC decoding @cite_7 . Indeed, the data recovery process can be considered as a message-passing algorithm where some messages are exchanged between the user nodes and the slot nodes. The theoretical results are validated by simulations. We show (under our hypothesis) that this system can reach a throughput greater than @math .
@cite_7
2131280424 2140253920 2139919528 2949560198
We propose Low Density Parity Check (LDPC) code designs for the half-duplex relay channel. Our designs are based on the information theoretic random coding scheme for decode-and-forward relaying. The source transmission is decoded with the help of side information in the form of additional parity bits from the relay. We derive the exact relationships that the component LDPC code profiles in the relay coding scheme must satisfy. These relationships act as constraints for the density evolution algorithm which is used to search for good relay code profiles. To speed up optimization, we outline a Gaussian approximation of density evolution for the relay channel. The asymptotic noise thresholds of the discovered relay code profiles are a fraction of a decibel away from the achievable lower bound for decode-and-forward relaying. With random component LDPC codes, the overall relay coding scheme performs within 1.2 dB of the theoretical limit. Departing from traditional communication theory where decoding algorithms are assumed to perform without error, a system where noise perturbs both computational devices and communication channels is considered here. This paper studies limits in processing noisy signals with noisy circuits by investigating the effect of noise on standard iterative decoders for low-density parity-check (LDPC) codes. Concentration of decoding performance around its average is shown to hold when noise is introduced into message-passing and local computation. Density evolution equations for simple faulty iterative decoders are derived. In one model, computing nonlinear estimation thresholds shows that performance degrades smoothly as decoder noise increases, but arbitrarily small probability of error is not achievable. Probability of error may be driven to zero in another system model; the decoding threshold again decreases smoothly with decoder noise. As an application of the methods developed, an achievability result for reliable memory systems constructed from unreliable components is provided. Experimental results show that certain message passing algorithms, namely, survey propagation, are very effective in finding satisfying assignments in random satisfiable 3CNF formulas. In this paper we make a modest step towards providing rigorous analysis that proves the effectiveness of message passing algorithms for random 3SAT. We analyze the performance of Warning Propagation, a popular message passing algorithm that is simpler than survey propagation. We show that for 3CNF formulas generated under the planted assignment distribution, running warning propagation in the standard way works when the clause-to-variable ratio is a sufficiently large constant. We are not aware of previous rigorous analysis of message passing algorithms for satisfiability instances, though such analysis was performed for decoding of Low Density Parity Check (LDPC) Codes. We discuss some of the differences between results for the LDPC setting and our results. We initiate the probabilistic analysis of linear programming (LP) decoding of low-density parity-check (LDPC) codes. Specifically, we show that for a random LDPC code ensemble, the linear programming decoder of Feldman succeeds in correcting a constant fraction of errors with high probability. The fraction of correctable errors guaranteed by our analysis surpasses previous nonasymptotic results for LDPC codes, and in particular, exceeds the best previous finite-length result on LP decoding by a factor greater than ten. This improvement stems in part from our analysis of probabilistic bit-flipping channels, as opposed to adversarial channels. At the core of our analysis is a novel combinatorial characterization of LP decoding success, based on the notion of a flow on the Tanner graph of the code. An interesting by-product of our analysis is to establish the existence of ldquoprobabilistic expansionrdquo in random bipartite graphs, in which one requires only that almost every (as opposed to every) set of a certain size expands, for sets much larger than in the classical worst case setting.