Über die Implementierung redundanzfreier Codes zur Datenverschlüsselung. (German) Zbl 0608.94010

The implementation of redundancy-free (noiseless) encodings is studied for both independent and Markovian sources. The existence of fast encodings for such sources is considered. In particular, necessary and sufficient conditions are given for the complexity of encoding the length n output of a finite Markov source to be \(O(n^{3/2})\), with probability arbitrarily close to one, rather than the worst case of \(O(n^ 2)\).
Reviewer: I.F.Blake


94A45 Prefix, length-variable, comma-free codes
94A29 Source coding
Full Text: DOI EuDML


[1] 1. R. ASH, Information Theory, John Wiley und Sons, New York, 1965. Zbl0141.34904 MR229475 · Zbl 0141.34904
[2] 2. K. L. CHUNG, Markov Chains with Stationary Transition Probabilities, Springer-Verlag, Berlin, 1967. Zbl0146.38401 MR217872 · Zbl 0146.38401
[3] 3. F. C. FRICK und W. H. SUMBY, Control Tower Language, J. Acoust. Soc. Amer., Bd. 24, 1952, S. 595-596.
[4] 4. F. JELINEK, Probabilistic Information Theory, McGraw-Hill Book Co., New York, 1968. Zbl0174.50702 · Zbl 0174.50702
[5] 5. F. JELINEK und K. S. SCHNEIDER, Variable-Length Encoding of Fixed-Rate Markov Sources for Fixed-Rate Channels, I.E.E.E. Trans. Information Theory, Bd. IT-20, 1974, S. 750-755. Zbl0301.94022 MR459925 · Zbl 0301.94022 · doi:10.1109/TIT.1974.1055302
[6] 6. H. JÜRGENSEN und M. KUNZE, Charakterisierung redundanzfreier Codes zur Datenverschlüsselung, R.A.I.R.O., Informatique Théorique. Zbl0573.94003 · Zbl 0573.94003
[7] 7. T. C. PASCO, Source Coding Algorithms for Fast Data Compression, PhD Thesis, Stanford University, CA, 1976.
[8] 8. F. RUBIN, Cryptographic Aspects of Data Compression Codes, Cryptologia, Bd. 3, 1979, S. 202-205. Zbl0416.94014 · Zbl 0416.94014 · doi:10.1080/0161-117991854061
[9] 9. F. RUBIN, Arithmetic Stream Coding Using Fixed Precision Registers, I.E.E.E. Trans. Information Theory, Bd. IT-25, 1979, S. 672-675. Zbl0422.94029 MR551265 · Zbl 0422.94029 · doi:10.1109/TIT.1979.1056107
[10] Zusatz während der Korrektur : Das Dekodierungsproblem wurde von uns mittlerweile in der Arbeit < Complexity of Redundance-Free Codes >, Report 142, Dep. Comp. Sci., Univ. Western Ont., 1985, gelöst.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.