The Experts below are selected from a list of 324 Experts worldwide ranked by ideXlab platform
Oscar C. Au - One of the best experts on this subject based on the ideXlab platform.
-
Exact Symbol Error Rate for Variable Length Codes Over Binary Symmetric Channel
2007 IEEE International Conference on Acoustics Speech and Signal Processing - ICASSP '07, 2007Co-Authors: Jiantao Zhou, Zhiqin Liang, Oscar C. AuAbstract:In this paper, we analyze the error recovery performance of variable length codes (VLCs) transmitted over Binary Symmetric Channel (BSC). Simple expressions for the exact mean symbol error rate (MSER) and the exact variance of symbol error rate (VSER) for any crossover probability pe are presented. We also prove that the mean error propagation length (MEPE) derived for single bit inversion error case is a scaled value of MSER when pe tends to zero. Comparisons with simulations demonstrate the accuracy of the MSER and VSER expressions.
-
ICASSP (3) - Exact Symbol Error Rate for Variable Length Codes Over Binary Symmetric Channel
2007 IEEE International Conference on Acoustics Speech and Signal Processing - ICASSP '07, 2007Co-Authors: Jiantao Zhou, Zhiqin Liang, Oscar C. AuAbstract:In this paper, we analyze the error recovery performance of variable length codes (VLCs) transmitted over Binary Symmetric Channel (BSC). Simple expressions for the exact mean symbol error rate (MSER) and the exact variance of symbol error rate (VSER) for any crossover probability pe are presented. We also prove that the mean error propagation length (MEPE) derived for single bit inversion error case is a scaled value of MSER when pe tends to zero. Comparisons with simulations demonstrate the accuracy of the MSER and VSER expressions.
Wojciech Szpankowski - One of the best experts on this subject based on the ideXlab platform.
-
capacity of a structural Binary Symmetric Channel
International Symposium on Information Theory, 2013Co-Authors: Lan V Truong, Wojciech SzpankowskiAbstract:Information theory traditionally deals with the problem of transmitting sequences over a communication Channel and finding the maximum number of messages that a transmitter can send so that the receiver recovers these messages with arbitrarily small probability of error. However, databases of various sorts have come into existence in recent years that require the transmission of new sources of data (e.g., graphs and sets) over communication Channels. Here, we investigate a communication model transmitting Erdos-Renyi (unlabeled) graphs to a destination over a Binary Symmetric Channel (BSC). We find the capacity of such a Channel - called the Structural Binary Symmetric Channel (SBSC) - to be C = 1 - h(e) where h(e) is the Binary entropy of the error bit rate e.
-
ISIT - Capacity of a Structural Binary Symmetric Channel
2013 IEEE International Symposium on Information Theory, 2013Co-Authors: Lan V Truong, Wojciech SzpankowskiAbstract:Information theory traditionally deals with the problem of transmitting sequences over a communication Channel and finding the maximum number of messages that a transmitter can send so that the receiver recovers these messages with arbitrarily small probability of error. However, databases of various sorts have come into existence in recent years that require the transmission of new sources of data (e.g., graphs and sets) over communication Channels. Here, we investigate a communication model transmitting Erdos-Renyi (unlabeled) graphs to a destination over a Binary Symmetric Channel (BSC). We find the capacity of such a Channel - called the Structural Binary Symmetric Channel (SBSC) - to be C = 1 - h(e) where h(e) is the Binary entropy of the error bit rate e.
Kasra Alishahi - One of the best experts on this subject based on the ideXlab platform.
-
capacity achieving linear codes with random Binary sparse generating matrices over the Binary Symmetric Channel
International Symposium on Information Theory, 2012Co-Authors: Makhdoumi A Kakhaki, Karkeh H Abadi, Pedram Pad, Hamid Saeedi, Farokh Marvasti, Kasra AlishahiAbstract:In this paper, we prove the existence of capacity achieving linear codes with random Binary sparse generating matrices over the Binary Symmetric Channel (BSC). The results on the existence of capacity achieving linear codes in the literature are limited to the random Binary codes with equal probability generating matrix elements and sparse parity-check matrices. Moreover, the codes with sparse generating matrices reported in the literature are not proved to be capacity achieving for Channels other than Binary Erasure Channel. As opposed to the existing results in the literature, which are based on optimal maximum a posteriori decoders, the proposed approach is based on a different decoder and consequently is suboptimal. We also demonstrate an interesting trade-off between the sparsity of the generating matrix and the error exponent (a constant which determines how exponentially fast the probability of error decays as block length tends to infinity). Based on our results, we also propose a Channel coding rate achievable by linear codes at a given block length and error probability. Moreover, we prove the existence of capacity achieving linear codes with a given (arbitrarily low) density of ones on rows of the generating matrix. In addition to proving the existence of capacity achieving sparse codes, an important conclusion of our paper is to prove that any arbitrarily selected sequence of sparse generating matrices is capacity achieving with high probability.
-
ISIT - Capacity achieving linear codes with random Binary sparse generating matrices over the Binary Symmetric Channel
2012 IEEE International Symposium on Information Theory Proceedings, 2012Co-Authors: A. Makhdoumi Kakhaki, Pedram Pad, Hamid Saeedi, Farokh Marvasti, H. Karkeh Abadi, Kasra AlishahiAbstract:In this paper, we prove the existence of capacity achieving linear codes with random Binary sparse generating matrices over the Binary Symmetric Channel (BSC). The results on the existence of capacity achieving linear codes in the literature are limited to the random Binary codes with equal probability generating matrix elements and sparse parity-check matrices. Moreover, the codes with sparse generating matrices reported in the literature are not proved to be capacity achieving for Channels other than Binary Erasure Channel. As opposed to the existing results in the literature, which are based on optimal maximum a posteriori decoders, the proposed approach is based on a different decoder and consequently is suboptimal. We also demonstrate an interesting trade-off between the sparsity of the generating matrix and the error exponent (a constant which determines how exponentially fast the probability of error decays as block length tends to infinity). Based on our results, we also propose a Channel coding rate achievable by linear codes at a given block length and error probability. Moreover, we prove the existence of capacity achieving linear codes with a given (arbitrarily low) density of ones on rows of the generating matrix. In addition to proving the existence of capacity achieving sparse codes, an important conclusion of our paper is to prove that any arbitrarily selected sequence of sparse generating matrices is capacity achieving with high probability.
Bane Vasic - One of the best experts on this subject based on the ideXlab platform.
-
finite alphabet iterative decoders part i decoding beyond belief propagation on the Binary Symmetric Channel
IEEE Transactions on Communications, 2013Co-Authors: Shiva Planjery, David Declercq, Ludovic Danjean, Bane VasicAbstract:We introduce a new paradigm for finite precision iterative decoding on low-density parity-check codes over the Binary Symmetric Channel. The messages take values from a finite alphabet, and unlike traditional quantized decoders which are quantized versions of the belief propagation (BP) decoder, the proposed finite alphabet iterative decoders (FAIDs) do not propagate quantized probabilities or log-likelihoods and the variable node update functions do not mimic the BP decoder. Rather, the update functions are maps designed using the knowledge of potentially harmful subgraphs that could be present in a given code, thereby rendering these decoders capable of outperforming the BP in the error floor region. On certain column-weight-three codes of practical interest, we show that there exist {FAIDs that surpass the floating-point BP decoder in the error floor region while requiring only three bits of precision for the representation of the messages}. Hence, FAIDs are able to achieve a superior performance at much lower complexity. We also provide a methodology for the selection of FAIDs that is not code-specific, but gives a set of candidate FAIDs containing potentially good decoders in the error floor region for any column-weight-three code. We validate the code generality of our methodology by providing particularly good three-bit precision FAIDs for a variety of codes with different rates and lengths.
-
Finite Alphabet Iterative Decoders—Part I: Decoding Beyond Belief Propagation on the Binary Symmetric Channel
IEEE Transactions on Communications, 2013Co-Authors: Shiva Planjery, David Declercq, Ludovic Danjean, Bane VasicAbstract:We introduce a new paradigm for finite precision iterative decoding on low-density parity-check codes over the Binary Symmetric Channel. The messages take values from a finite alphabet, and unlike traditional quantized decoders which are quantized versions of the belief propagation (BP) decoder, the proposed finite alphabet iterative decoders (FAIDs) do not propagate quantized probabilities or log-likelihoods and the variable node update functions do not mimic the BP decoder. Rather, the update functions are maps designed using the knowledge of potentially harmful subgraphs that could be present in a given code, thereby rendering these decoders capable of outperforming the BP in the error floor region. On certain column-weight-three codes of practical interest, we show that there exist {FAIDs that surpass the floating-point BP decoder in the error floor region while requiring only three bits of precision for the representation of the messages}. Hence, FAIDs are able to achieve a superior performance at much lower complexity. We also provide a methodology for the selection of FAIDs that is not code-specific, but gives a set of candidate FAIDs containing potentially good decoders in the error floor region for any column-weight-three code. We validate the code generality of our methodology by providing particularly good three-bit precision FAIDs for a variety of codes with different rates and lengths.
-
Finite alphabet iterative decoders approaching maximum likelihood performance on the Binary Symmetric Channel
2012Co-Authors: David Declercq, Bane Vasic, Shiva PlanjeryAbstract:We introduce a generic approach for improving the guaranteed error correction capability of regular low-density parity check codes. The method relies on operating (in serial or in parallel) a set of finite alphabet iterative decoders. The message passing update rules are judiciously chosen to ensure that decoders have different dynamics on a specific finite-length code. The idea is that for the Binary Symmetric Channel, if some error pattern cannot be corrected by one particular decoder, there exists in the set of decoders, another decoder which can correct this pattern. We show how to select a plurality of message update rules so that the set of decoders can collectively correct error patterns on the dominant trapping sets. We also show that a set of decoders with dynamic re-initializations can approach the performance of maximum likelihood decoding for finite-length regular column-weight three codes.
-
ITA - Finite alphabet iterative decoders approaching maximum likelihood performance on the Binary Symmetric Channel
2012 Information Theory and Applications Workshop, 2012Co-Authors: David Declercq, Bane Vasic, Shiva PlanjeryAbstract:We introduce a generic approach for improving the guaranteed error correction capability of regular low-density parity check codes. The method relies on operating (in serial or in parallel) a set of finite alphabet iterative decoders. The message passing update rules are judiciously chosen to ensure that decoders have different dynamics on a specific finite-length code. The idea is that for the Binary Symmetric Channel, if some error pattern cannot be corrected by one particular decoder, there exists in the set of decoders, another decoder which can correct this pattern. We show how to select a plurality of message update rules so that the set of decoders can collectively correct error patterns on the dominant trapping sets. We also show that a set of decoders with dynamic re-initializations can approach the performance of maximum likelihood decoding for finite-length regular column-weight three codes.
-
multilevel decoders surpassing belief propagation on the Binary Symmetric Channel
arXiv: Information Theory, 2010Co-Authors: Shiva Planjery, Shashi Kiran Chilappagari, David Declercq, Bane VasicAbstract:In this paper, we propose a new class of quantized message-passing decoders for LDPC codes over the BSC. The messages take values (or levels) from a finite set. The update rules do not mimic belief propagation but instead are derived using the knowledge of trapping sets. We show that the update rules can be derived to correct certain error patterns that are uncorrectable by algorithms such as BP and min-sum. In some cases even with a small message set, these decoders can guarantee correction of a higher number of errors than BP and min-sum. We provide particularly good 3-bit decoders for 3-left-regular LDPC codes. They significantly outperform the BP and min-sum decoders, but more importantly, they achieve this at only a fraction of the complexity of the BP and min-sum decoders.
Victoria Kostina - One of the best experts on this subject based on the ideXlab platform.
-
ISIT - Real-time Binary Posterior Matching
2019 IEEE International Symposium on Information Theory (ISIT), 2019Co-Authors: Anusha Lalitha, Anatoly Khina, Tara Javidi, Victoria KostinaAbstract:We consider the problem of communications over the Binary Symmetric Channel with feedback, where the information sequence is made available in a causal, possibly random, fashion. We develop a real-time variant of the renowned Horstein scheme and provide analytical guarantees for its error-probability exponential decay rate. We further use the scheme to stabilize an unstable control plant over a Binary Symmetric Channel and compare the analytical guarantees with its empirical performance as well as with those of anytime-reliable codes.
