Search

In 2016, Karney proposed an exact sampling algorithm for the standard normal distribution. In this paper, we study the computational complexity of this algorithm under the random deviate model. Specifically, Karney's algorithm requires the access to an infinite sequence of independently and uniformly random deviates over the range (0,1). We give an estimate of the expected number of uniform deviates used by this algorithm until outputting a sample value, and present an improved algorithm with lower uniform deviate consumption. The experimental results also shows that our improved algorithm has better performance than Karney's algorithm.

In this paper, we propose a systematic low density generator matrix (LDGM) code ensemble, which is defined by the Bernoulli process. We prove that, under maximum likelihood (ML) decoding, the proposed ensemble can achieve the capacity of binary-input output symmetric (BIOS) memoryless channels in terms of bit error rate (BER). The proof technique reveals a new mechanism, different from lowering down frame error rate (FER), that the BER can be lowered down by assigning light codeword vectors to light information vectors. The finite length performance is analyzed by deriving an upper bound and a lower bound, both of which are shown to be tight in the high signal-to-noise ratio (SNR) region. To improve the waterfall performance, we construct the systematic convolutional LDGM (SC-LDGM) codes by a random splitting process. The SC-LDGM codes are easily configurable in the sense that any rational code rate can be realized without complex optimization. As a universal construction, the main advantage of the SC-LDGM codes is their near-capacity performance in the waterfall region and predictable performance in the error-floor region that can be lowered down to any target as required by increasing the density of the uncoupled LDGM codes. Numerical results are also provided to verify our analysis., Comment: submitted to IEEE Transactions on Information Theory

We present in this paper a special class of unit memory convolutional codes (UMCCs), called semi-random UMCCs (SRUMCCs), where the information block is first encoded by a short block code and then transmitted in a block Markov (random) superposition manner. We propose a successive cancellation list decoding algorithm, by which a list of candidate codewords are generated serially until one passes an empirical divergence test instead of the conventional cyclic redundancy check (CRC). The threshold for testing the correctness of candidate codewords can be learned off-line based on the statistical behavior of the introduced empirical divergence function (EDF). The performance-complexity tradeoff and the performance-delay tradeoff can be achieved by adjusting the statistical threshold and the decoding window size. To analyze the performance, a closed-form upper bound and a simulated lower bound are derived. Simulation results verify our analysis and show that: 1) The proposed list decoding algorithm with empirical divergence test outperforms the sequential decoding in high signal-to-noise ratio (SNR) region; 2) Taking the tail-biting convolutional codes (TBCC) as the basic codes, the proposed list decoding of SRUMCCs have comparable performance with the polar codes under the constraint of equivalent decoding delay., Comment: Submitted to IEEE Transactions on Information Theory. arXiv admin note: substantial text overlap with arXiv:1902.09808

This paper is concerned with block Markov superposition transmission (BMST) of tail-biting convolutional code (TBCC). We propose a new decoding algorithm for BMST-TBCC, which integrates a serial list Viterbi algorithm (SLVA) with a soft check instead of conventional cyclic redundancy check (CRC). The basic idea is that, compared with an erroneous candidate codeword, the correct candidate codeword for the first sub-frame has less influence on the output of Viterbi algorithm for the second sub-frame. The threshold is then determined by statistical learning based on the introduced empirical divergence function. The numerical results illustrate that, under the constraint of equivalent decoding delay, the BMST-TBCC has comparable performance with the polar codes. As a result, BMST-TBCCs may find applications in the scenarios of the streaming ultra-reliable and low latency communication (URLLC) data services., Comment: 5 pages, 6 figures, submitted to ISIT2019