Search

In this paper we provide a method to obtain tight lower bounds on the minimum redundancy achievable by a Huffman code when the probability distribution underlying an alphabet is only partially known. In particular, we address the case where the occurrence probabilities are unknown for some of the symbols in an alphabet. Bounds can be obtained for alphabets of a given size, for alphabets of up to a given size, and for alphabets of arbitrary size. The method operates on a Computer Algebra System, yielding closed-form numbers for all results. Finally, we show the potential of the proposed method to shed some light on the structure of the minimum redundancy achievable by the Huffman code.

A class of two-bit bit flipping algorithms for decoding low-density parity-check codes over the binary symmetric channel was proposed in [1]. Initial results showed that decoders which employ a group of these algorithms operating in parallel can offer low error floor decoding for high-speed applications. As the number of two-bit bit flipping algorithms is large, designing such a decoder is not a trivial task. In this paper, we describe a procedure to select collections of algorithms that work well together. This procedure relies on a recursive process which enumerates error configurations that are uncorrectable by a given algorithm. The error configurations uncorrectable by a given algorithm form its trapping set profile. Based on their trapping set profiles, algorithms are selected so that in parallel, they can correct a fixed number of errors with high probability., Comment: 5 pages, 1 figure, accepted for presentation at the IEEE International Symposium on Information Theory (ISIT) 2012

In this paper, we propose a new class of bit flipping algorithms for low-density parity-check (LDPC) codes over the binary symmetric channel (BSC). Compared to the regular (parallel or serial) bit flipping algorithms, the proposed algorithms employ one additional bit at a variable node to represent its "strength." The introduction of this additional bit increases the guaranteed error correction capability by a factor of at least 2. An additional bit can also be employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis of the proposed algorithms is described. These algorithms outperform the Gallager A/B algorithm and the min-sum algorithm at much lower complexity. Concatenation of two-bit bit flipping algorithms show a potential to approach the performance of belief propagation (BP) decoding in the error floor region, also at lower complexity., Comment: 6 pages. Submitted to IEEE International Symposium on Information Theory 2011

This paper is concerned with the construction of low-density parity-check (LDPC) codes with low error floors. Two main contributions are made. First, a new class of structured LDPC codes is introduced. The parity check matrices of these codes are arrays of permutation matrices which are obtained from Latin squares and form a finite field under some matrix operations. Second, a method to construct LDPC codes with low error floors on the binary symmetric channel (BSC) is presented. Codes are constructed so that their Tanner graphs are free of certain small trapping sets. These trapping sets are selected from the Trapping Set Ontology for the Gallager A/B decoder. They are selected based on their relative harmfulness for a given decoding algorithm. We evaluate the relative harmfulness of different trapping sets for the sum product algorithm (SPA) by using the topological relations among them and by analyzing the decoding failures on one trapping set in the presence or absence of other trapping sets., Comment: This is a 21 page paper. It contains 18 figures and 4 tables. This paper was submitted to IEEE Transactions on Information Theory

In this paper, we give necessary and sufficient conditions for low-density parity-check (LDPC) codes with column-weight three to correct three errors when decoded using hard-decision message-passing decoding. Additionally, we give necessary and sufficient conditions for column-weight-four codes to correct three errors in four iterations of hard-decision message-passing decoding. We then give a construction technique which results in codes satisfying these conditions. We also provide numerical assessment of code performance via simulation results., Comment: 25 pages. 11 Figures. Part of the work was presented at the Information Theory Workshop (ITW), May 5-9 2008, Porto, Portugal. submitted to IEEE Transactions on Information Theory

The relation between the girth and the error correction capability of column-weight-three LDPC codes is investigated. Specifically, it is shown that the Gallager A algorithm can correct $g/2-1$ errors in $g/2$ iterations on a Tanner graph of girth $g \geq 10$., Comment: 7 pages, 7 figures, submitted to IEEE Transactions on Information Theory (July 2008)

The relation between the girth and the guaranteed error correction capability of $\gamma$-left regular LDPC codes when decoded using the bit flipping (serial and parallel) algorithms is investigated. A lower bound on the size of variable node sets which expand by a factor of at least $3 \gamma/4$ is found based on the Moore bound. An upper bound on the guaranteed error correction capability is established by studying the sizes of smallest possible trapping sets. The results are extended to generalized LDPC codes. It is shown that generalized LDPC codes can correct a linear fraction of errors under the parallel bit flipping algorithm when the underlying Tanner graph is a good expander. It is also shown that the bound cannot be improved when $\gamma$ is even by studying a class of trapping sets. A lower bound on the size of variable node sets which have the required expansion is established., Comment: 17 pages. Submitted to IEEE Transactions on Information Theory. Parts of this work have been accepted for presentation at the International Symposium on Information Theory (ISIT'08) and the International Telemetering Conference (ITC'08)

JPEG 2000 Part 2 (Extensions) contains a number of technologies that are of potential interest in remote sensing applications. These include arbitrary wavelet transforms, techniques to limit boundary artifacts in tiles, multiple component transforms, and trellis-coded quantization (TCQ). We are investigating the addition of these features to the low-memory (scan-based) implementation of JPEG 2000 Part 1. A scan-based implementation of TCQ has been realized and tested, with a very small performance loss as compared with the full image (frame-based) version. A proposed amendment to JPEG 2000 Part 2 will effect the syntax changes required to make scan-based TCQ compatible with the standard.