15
SECTION 2.4. WHY COMPRESSION?
• Over error-prone links with non-negligible bit error rates, compressing messages be-
fore they are channel-coded using error-correcting codes can help improve through-
put because all the redundancy in the message can be designed in to improve error
resilience, after removing any other redundancies in the original message. It is better
to design in redundancy with the explicit goal of correcting bit errors, rather than
rely on whatever sub-optimal redundancies happen to exist in the original message.
Compression is traditionally thought of as
an end-to-end function, applied as part of the
application-layer protocol. For instance, one might use lossless compression between a
web server and browser to reduce the number of bits sent when transferring a collection of
web pages. As another example, one might use a compressed image format such as JPEG
to transmit images, or a format like MPEG to transmit video. However, one may also ap-
ply compression at the link layer to reduce the number of transmitted bits and eliminate
redundant bits (before possibly applying an error-correcting code over the link). When
applied at the link layer, compression only makes sense if the data is inherently compress-
ible, which means it cannot already be compressed and must have enough redundancy to
extract compression gains.
The next chapter describes two compr
ession (source coding) schemes: Huffman Codes
and Lempel-Ziv-Welch (LZW) compression.
⌅ Acknowledgments
Thanks to Yury Polyanskiy for several useful comments and suggestions.
⌅ Exercises
1. Several people at a party are trying to guess a 3-bit binary number. Alice is told that
the number is odd; Bob is told that it is not a multiple of 3 (i.e., not 0, 3, or 6); Charlie
is told that the number contains exactly two 1’s; and Deb is given all three of these
clues. How much information (in bits) did each player get about the number?
2. After careful data collection, Alyssa P
. Hacker observes that the probability of
“HIGH” or “LOW” traffic on Storrow Drive is given by the following table:
HIGH traffic
level LOW traffic level
If the Red Sox are playing
If the Red
Sox are not playing
P (HIGH traffic) = 0.999 P (LOW traffic) = 0.001
P (HIGH traffic)
= 0.25 P (LOW traffic) = 0.75
(a) If it is known that the
Red Sox are playing, then how much information in bits
is conveyed by the statement that the traffic level is LOW. Give your answer as
a mathematical expression.
(b) Suppose it is known that the
Red Sox are not playing. What is the entropy
of the corresponding probability distribution of traffic? Give your answer as a
mathematical expression.
3. X is an unknown 4-bit binary
number picked uniformly at random from the set of
all possible 4-bit numbers. You are given another 4-bit binary number, Y , and told
剩余341页未读，继续阅读
绝不原创的飞龙
- 粉丝: 3w+
- 资源: 1088
我的内容管理
展开
最新资源
- 计算机人脸表情动画技术发展综述
- 关系数据库的关键字搜索技术综述：模型、架构与未来趋势
- 迭代自适应逆滤波在语音情感识别中的应用
- 概念知识树在旅游领域智能分析中的应用
- 构建is-a层次与OWL本体集成：理论与算法
- 基于语义元的相似度计算方法研究：改进与有效性验证
- 网格梯度多密度聚类算法：去噪与高效聚类
- 网格服务工作流动态调度算法PGSWA研究
- 突发事件连锁反应网络模型与应急预警分析
- BA网络上的病毒营销与网站推广仿真研究
- 离散HSMM故障预测模型：有效提升系统状态预测
- 煤矿安全评价：信息融合与可拓理论的应用
- 多维度Petri网工作流模型MD_WFN：统一建模与应用研究
- 面向过程追踪的知识安全描述方法
- 基于收益的软件过程资源调度优化策略
- 多核环境下基于数据流Java的Web服务器优化实现提升性能
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
