An Efficient Universal Coding Algorithm for Noiseless Channel with Symbols of Unequal Cost
スポンサーリンク
概要
- 論文の詳細を見る
This paper describes an efficient and simple coding algorithm of universally optimal codes for stationary (ergodic) sources and noiseless channel with unequal symbol costs. The symbol cost indicates the required time (or space) for the transmission (or storage) of that symbol, and the cost of any code symbol depends only on that symbol. The proposed coding algorithm mainly consists of two parts. The first part is based on the well-known Ziv-Lempel coding algorithm proposed in I978 (sometimes called LZ78), and the second part is based on the Varn coding algorithm. The coding algorithm asymptotically achieves an optimal average cost of codes for stationary sources, and also achieves an optimal cost of codes for stationary ergodic sources with probability one. Furthermore, the computational complexity of the proposed coding algorithm is linear with respect to the length of source sequence and coded sequence.
- 社団法人電子情報通信学会の論文
- 1997-11-25
著者
-
Iwata K
The Authors Are With The Department Of Information Science And Intelligent Systems Faculty Of Engine
-
Morii M
Univ. Tokushima Tokushima‐shi Jpn
-
Uyematsu T
The Dept. Of Communications And Integrated Systems Tokyo Institute Of Technology
-
Uyematsu T
The Author Is With The Department Of Electrical And Electronic Engineering Tokyo Institute Of Techno
-
IWATA Ken-ichi
the Department of Information Science and Intelligent Systems, Faculty of Engineering, The Universit
-
MORII Masakatu
the Department of Information Science and Intelligent Systems, Faculty of Engineering, The Universit
-
UYEMATSU Tomohiko
School of Information Science, Japan Advanced Institute of Science and Technology Ishikawa
関連論文
- The Efficient GMD Decoders for BCH Codes (Special Issue on Multiple-Valued Logic)
- On a Recursive Form of Welch-Berlekamp Algorithm
- Efficient Secret Sharing Schemes Based on Authorized Subsets(Cryptography and Information Security)
- Secret Key Capacity for Ergodic Correlated Sources(Information Theory)
- One-Point Algebraic Geometric Codes from Artin-Schreier Extensions of Hermitian Function Fields (Special Section on Information Theory and Its Applications)
- A Simple Parallel Algorithm for the Ziv-Lempel Encoding
- An Efficient Universal Coding Algorithm for Noiseless Channel with Symbols of Unequal Cost
- Proposal of an Automatic Signature Scheme Using a Compiler (Special Section on Cryptography and Information Security)
- Reliability Functions for Concatenated Codes Employing Modular Codes with Maximum Likelihood Decoding
- Permutation Cipher Scheme Using Polynomials over a Field
- New Weakness in the Key-Scheduling Algorithm of RC4
- Internal-State Reconstruction of a Stream Cipher RC4(Information Security)(Information Theory and Its Applications)
- A Method for Improving Fast Correlation Attack Using Parity Check Equations Modifications (Information Security)