[go: up one dir, main page]

Kieffer et al., 2002 - Google Patents

Structured grammar-based codes for universal lossless data compression

Kieffer et al., 2002

View PDF
Document ID
11608198448336731253
Author
Kieffer J
Yang E
Publication year
Publication venue
Communications in Information and Systems

External Links

Snippet

A grammar-based code losslessly compresses each finite-alphabet data string x by compressing a context-free grammar Gx which represents x in the sense that the language of Gx is {x}. In an earlier paper, we showed that if the grammar Gx is a type of grammar …
Continue reading at plouffe.fr (PDF) (other versions)

Classifications

    • 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/4031—Fixed length to variable length coding
    • H03M7/4037—Prefix 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/3082—Vector coding
    • 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/27—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 using interleaving techniques
    • H03M13/2742—Irregular interleaver wherein the permutation pattern is not obtained by a computation rule, e.g. interleaver based on random generators
    • H03M13/2746—S-random interleaver

Similar Documents

Publication Publication Date Title
Savari Redundancy of the Lempel-Ziv incremental parsing rule
Yang et al. Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform. i. without context models
EP1147612B1 (en) Code book construction for variable to variable length entropy encoding
JP4786796B2 (en) Entropy code mode switching for frequency domain audio coding
Manzini An analysis of the Burrows—Wheeler transform
Weinberger et al. A sequential algorithm for the universal coding of finite memory sources
Kieffer et al. Universal lossless compression via multilevel pattern matching
Gray et al. Vector quantizers and predictive quantizers for Gauss-Markov sources
Orlitsky et al. Speaking of infinity [iid strings]
EP1142129A1 (en) Variable to variable length entropy encoding
US20030210164A1 (en) Method of generating Huffman code length information
Yang et al. Universal lossless data compression with side information by using a conditional MPM grammar transform
Kieffer et al. Structured grammar-based codes for universal lossless data compression
Pic et al. Mq-coder inspired arithmetic coder for synthetic dna data storage
US6456209B1 (en) Method and apparatus for deriving a plurally parsable data compression dictionary
Seroussi On universal types
Yang et al. Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform. 2. With context models
Goyal et al. On optimal permutation codes
Shields Performance of LZ algorithms on individual sequences
Savari Redundancy of the Lempel-Ziv string matching code
US7193542B2 (en) Digital data compression robust relative to transmission noise
Yang et al. On the redundancy of the fixed-database Lempel-Ziv algorithm for/spl phi/-mixing sources
Kieffer et al. Survey of grammar-based data structure compression
US7081839B2 (en) Method and apparatus for compressing an input string to provide an equivalent decompressed output string
Yamamoto et al. A Universal Data Compression Scheme based on the AIVF Coding Techniques