Nothing Special   »   [go: up one dir, main page]

Wyner et al., 1998 - Google Patents

On the role of pattern matching in information theory

Wyner et al., 1998

View PDF
Document ID
9867463427124102099
Author
Wyner A
Ziv J
Wyner A
Publication year
Publication venue
IEEE Transactions on information Theory

External Links

Snippet

In this paper, the role of pattern matching in information theory is motivated and discussed. We describe the relationship between a pattern's recurrence time and its probability under the data-generating stochastic source. We show how this relationship has led to great …
Continue reading at citeseerx.ist.psu.edu (PDF) (other versions)

Classifications

    • H—ELECTRICITY
    • H03—BASIC ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1105—Decoding
    • H—ELECTRICITY
    • H03—BASIC ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same information or similar information or a subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
    • H03M7/42—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code using table look-up for the coding or decoding process, e.g. using read-only memory
    • H—ELECTRICITY
    • H03—BASIC ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same information or similar information or a subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
    • H03M7/4006—Conversion to or from arithmetic code
    • H—ELECTRICITY
    • H03—BASIC ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same information or similar information or a subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/3082—Vector coding
    • H—ELECTRICITY
    • H03—BASIC ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same information or similar information or a subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method
    • H03M7/3088—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method employing the use of a dictionary, e.g. LZ78
    • H—ELECTRICITY
    • H03—BASIC ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/13—Linear codes
    • H—ELECTRICITY
    • H03—BASIC ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
    • H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
    • H03M13/3905—Maximum a posteriori probability [MAP] decoding and approximations thereof based on trellis or lattice decoding, e.g. forward-backward algorithm, log-MAP decoding, max-log-MAP decoding; MAP decoding also to be found in H04L1/0055
    • H—ELECTRICITY
    • H03—BASIC ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same information or similar information or a subset of information is represented by a different sequence or number of digits
    • H03M7/14—Conversion to or from non-weighted codes

Similar Documents

Publication Publication Date Title
Wyner et al. On the role of pattern matching in information theory
Yang et al. On the performance of data compression algorithms based upon string matching
Yang et al. Fixed-slope universal lossy data compression
Luczak et al. A suboptimal lossy data compression based on approximate pattern matching
Szpankowski Asymptotic average redundancy of Huffman (and other) block codes
Yang et al. Simple universal lossy data compression schemes derived from the Lempel-Ziv algorithm
Matsushima et al. A class of distortionless codes designed by Bayes decision theory
Sow et al. Complexity distortion theory
Gray et al. Nonblock source coding with a fidelity criterion
Lapidoth et al. The compound channel capacity of a class of finite-state channels
Linder et al. Causal coding of stationary sources and individual sequences with high resolution
Zamir et al. Natural type selection in adaptive lossy compression
Wyner The redundancy and distribution of the phrase lengths of the fixed-database Lempel-Ziv algorithm
Koga et al. Asymptotic properties on codeword lengths of an optimal FV code for general sources
Savari Redundancy of the Lempel-Ziv string matching code
Elshafiy et al. On-the-fly stochastic codebook re-generation for sources with memory
Yang et al. On the redundancy of the fixed-database Lempel-Ziv algorithm for/spl phi/-mixing sources
UCHIDA et al. The optimal overflow and underflow probabilities of variable-length coding for the general source
Shields Performance of LZ algorithms on individual sequences
Yang et al. The redundancy of source coding with a fidelity criterion. II. Coding at a fixed rate level with unknown statistics
Kieffer Finite-state adaptive block to variable-length noiseless coding of a nonstationary information source
Hwang et al. Genetic entropy-constrained vector quantizer design algorithm
Böcherer et al. Fixed-to-variable length resolution coding for target distributions
Rissanen et al. Coding and compression: A happy union of theory and practice
Shamir Sequential universal lossless techniques for compression of patterns and their description length