Merhav Neri
The Viterbi Faculty of Electrical and Computer Engineering, Technion-Israel Institute of Technology, Technion City, Haifa 3200003, Israel.
Entropy (Basel). 2023 Aug 11;25(8):1199. doi: 10.3390/e25081199.
We propose a universal ensemble for the random selection of rate-distortion codes which is asymptotically optimal in a sample-wise sense. According to this ensemble, each reproduction vector, x^, is selected independently at random under the probability distribution that is proportional to 2-LZ(x^), where LZ(x^) is the code length of x^ pertaining to the 1978 version of the Lempel-Ziv (LZ) algorithm. We show that, with high probability, the resulting codebook gives rise to an asymptotically optimal variable-rate lossy compression scheme under an arbitrary distortion measure, in the sense that a matching converse theorem also holds. According to the converse theorem, even if the decoder knew the -th order type of source vector in advance ( being a large but fixed positive integer), the performance of the above-mentioned code could not have been improved essentially for the vast majority of codewords pertaining to source vectors in the same type. Finally, we present a discussion of our results, which includes among other things, a clear indication that our coding scheme outperforms the one that selects the reproduction vector with the shortest LZ code length among all vectors that are within the allowed distortion from the source vector.
我们提出了一种用于随机选择率失真码的通用集合，它在样本意义上是渐近最优的。根据这个集合，每个再现向量(\hat{x})在与(2^{-LZ(\hat{x})})成比例的概率分布下独立随机选择，其中(LZ(\hat{x}))是与1978年版本的莱普尔 - 齐夫（LZ）算法相关的(\hat{x})的码长。我们证明，以高概率，所得码本在任意失真度量下产生一种渐近最优的变率有损压缩方案，即匹配的逆定理也成立。根据逆定理，即使解码器提前知道源向量的第(n)阶类型（(n)是一个大但固定的正整数），对于绝大多数与同一类型源向量相关的码字，上述码的性能也无法从本质上得到改善。最后，我们对我们的结果进行了讨论，其中包括明确指出我们的编码方案优于在与源向量的允许失真范围内的所有向量中选择具有最短LZ码长的再现向量的方案。
