scientific article; zbMATH DE number 1498788

MaRDI QIDQ4500978zbMATH OpenFDO

Authors Irina E. Bocharova, Boris D. Kudryashov

Publication date 3 September 2000

zbMATH Keywords

arithmetic codingcombinatorial source codingcomputational complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Source coding (94A29) Prefix, length-variable, comma-free codes (94A45)

Review text

The computational complexity of available combinatorial and arithmetic coding techniques is polynomial in the length of the coded sequence. A coding procedure is constructed whose efficiency is close to the combinatorial coding efficiency and which has low computational complexity of coding and decoding. It represents a kind of variable-length coding. The redundancy of the new algorithm for the binary sequence of length \(n\) admits an upper bound \(0,0868k\) for \(n\leq 256\). For small \(k\), the average redundancy is as follows: 1) \(r(n,k)\leq 1\) for \(k\leq 17\) and \(n\leq 256\); 2) \(r(n,k)\leq 1\) for \(n\leq 49\) and \(k\leq n\). For the entire collection see [Zbl 0918.00043].

Recommendations

• Fast and efficient coding of information sources
• An effective method for encoding information sources using the fast multiplication algorithm
• Fast coding of low-entropy sources
• scientific article; zbMATH DE number 1285526

Cited in

(3)

• Optimal redundancy in computations from random oracles
• Compressors for combined source and channel coding with applications to the generalized Gaussian family (Corresp.)
• Fast coding of low-entropy sources

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4500978)