Zero-error single-channel source coding has been studied extensively over the past decades. Its natural multi-channel generalization is however not well investigated. While the special case with multiple symmetric-alphabet channels was studied a decade ago, codes in such setting have no advantage over single-channel codes in data compression, making them worthless in most applications. With essentially no development since the last decade, in this paper, we break the stalemate by showing that it is possible to beat single-channel source codes in terms of compression assuming asymmetric-alphabet channels. We present the multi-channel analog of several classical results in single-channel source coding, such as that a multi-channel Huffman code is an optimal tree-decodable code. We also show some evidences that finding an efficient construction of multi-channel Huffman codes may be hard. Nevertheless, we propose a suboptimal code construction whose redundancy is guaranteed to be no larger than that of an optimal single-channel source code.


翻译:在过去几十年中,对零危险单一通道源编码进行了广泛研究,但其自然多通道一般化却没有得到很好地调查。虽然十年前曾对多个对称阿尔法特信道的特例进行了研究,但这种设置的编码在数据压缩方面没有比单一通道编码的优势,使这些编码在大多数应用中毫无价值。由于自过去十年以来基本上没有发展,本文件通过表明有可能在不对称的通道内压缩时,在单一通道源编码中击败单一通道源编码,从而打破了僵局。我们在单通道源编码中展示了多个经典结果的多通道模拟,例如多通道Huffman编码是一种最佳的树代号。我们还表明,找到高效地构建多通道Huffman编码可能很困难。然而,我们提议了一种次优化的编码结构,其冗余保证不会大于最佳的单一通道源编码。

0
下载
关闭预览

相关内容

iOS 8 提供的应用间和应用跟系统的功能交互特性。
  • Today (iOS and OS X): widgets for the Today view of Notification Center
  • Share (iOS and OS X): post content to web services or share content with others
  • Actions (iOS and OS X): app extensions to view or manipulate inside another app
  • Photo Editing (iOS): edit a photo or video in Apple's Photos app with extensions from a third-party apps
  • Finder Sync (OS X): remote file storage in the Finder with support for Finder content annotation
  • Storage Provider (iOS): an interface between files inside an app and other apps on a user's device
  • Custom Keyboard (iOS): system-wide alternative keyboards

Source: iOS 8 Extensions: Apple’s Plan for a Powerful App Ecosystem
【图与几何深度学习】Graph and geometric deep learning,49页ppt
专知会员服务
44+阅读 · 2020年10月31日
【DeepMind】强化学习教程,83页ppt
专知会员服务
152+阅读 · 2020年8月7日
【IJCAJ 2020】多通道神经网络 Multi-Channel Graph Neural Networks
专知会员服务
25+阅读 · 2020年7月19日
商业数据分析,39页ppt
专知会员服务
159+阅读 · 2020年6月2日
专知会员服务
60+阅读 · 2020年3月19日
最新!Yann Lecun 纽约大学Spring2020深度学习课程,附PPT下载
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【音乐】Attention
英语演讲视频每日一推
3+阅读 · 2017年8月22日
Arxiv
0+阅读 · 2021年6月29日
VIP会员
相关VIP内容
【图与几何深度学习】Graph and geometric deep learning,49页ppt
专知会员服务
44+阅读 · 2020年10月31日
【DeepMind】强化学习教程,83页ppt
专知会员服务
152+阅读 · 2020年8月7日
【IJCAJ 2020】多通道神经网络 Multi-Channel Graph Neural Networks
专知会员服务
25+阅读 · 2020年7月19日
商业数据分析,39页ppt
专知会员服务
159+阅读 · 2020年6月2日
专知会员服务
60+阅读 · 2020年3月19日
最新!Yann Lecun 纽约大学Spring2020深度学习课程,附PPT下载
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
相关资讯
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【音乐】Attention
英语演讲视频每日一推
3+阅读 · 2017年8月22日
Top
微信扫码咨询专知VIP会员