没有合适的资源?快使用搜索试试~ 我知道了~
首页Raptor的理论、设计和实现
资源详情
资源推荐
Foundations and Trends
R
in
Communications and Information Theory
Vol. 6, Nos. 3–4 (2009) 213–322
c
2011 A. Shokrollahi and M. Luby
DOI: 10.1561/0100000060
Raptor Codes
By Amin Shokrollahi and Michael Luby
Contents
1 Introduction 215
1.1 Data Transmission 216
1.2 The Transmission Control Protocol 217
1.3 The User Datagram Protocol 218
1.4 Point-to-point Transmission 219
1.5 Point-to-multipoint Transmission 219
1.6 Multipoint-to-point Transmission 220
1.7 Multipoint-to-multipoint Transmission 221
1.8 Fountain Code Overview 222
1.9 Fountain Code Construction Outline 224
1.10 The Random Binary Fountain 226
2 Foundations 229
2.1 LT Codes 229
2.2 Raptor Codes 238
2.3 Systematic Version 242
2.4 Inactivation Decoding 247
3 Standardized Raptor Codes 256
3.1 Standardization 256
3.2 The R10 Code (Raptor 10) 258
3.3 The RQ code 271
A Rank of Random Matrices 304
B Failure Probability of R10 and RQ 307
B.1 Methodology 307
B.2 The Failure Probability of R10 311
B.3 The Failure Probability of RQ 314
Acknowledgments 319
References 321
Foundations and Trends
R
in
Communications and Information Theory
Vol. 6, Nos. 3–4 (2009) 213–322
c
2011 A. Shokrollahi and M. Luby
DOI: 10.1561/0100000060
Raptor Codes
Amin Shokrollahi
1
and Michael Luby
2
1
EPFL, Station 14, Lausanne 1015, Switzerland, amin.shokrollahi@epfl.ch
2
Qualcomm, Inc., 3195 Kifer Road, Santa Clara, CA 95051, USA,
luby@qualcomm.com
Abstract
This monograph describes the theory behind Raptor codes, and eluci-
dates elements of the processes behind the design of two of the most
prominent members of this class of codes: R10 and RaptorQ (RQ). R10
has already been adopted by a number of standards’ bodies, and RQ
is in the process of entering various standards at the time of writing of
this monograph.
The monograph starts with the description of some of the
transmission problems, which inspired the invention of Fountain codes.
Thereafter, Luby transform codes (LT codes) and Raptor codes are
introduced and insights are provided into their design. These codes are
currently the most efficient realizations of Fountain codes. Different
algorithms are introduced for encoding and decoding various versions
of these codes, including their systematic versions. Moreover, a hybrid
decoding algorithm called “inactivation decoding” is introduced, which
is an integral part of all modern implementations of Raptor codes.
The R10 and RQ codes have been continued and will continue to
be adopted into a number of standards and thus there are publicly
available specifications that describe exactly how to implement these
codes. However, the standards’ specifications provide no insight into
the rationale for the design choices made. One of the primary purposes
of this document is to provide this design rationale.
We provide results of extensive simulations of R10 and RQ codes
to show the behavior of these codes in many different scenarios.
1
Introduction
In theory, there is no difference between theory and
practice, but in practice there is.
1
This monograph describes the theory, design, and practical realiza-
tion of Raptor codes. Section 2 describes conceptual design and analysis
tools that provide provably good Raptor code designs. Section 3
describes more detailed design and heuristic analysis tools that
provide constructions of practical Raptor codes. Based on their excel-
lent recovery properties and computational complexity, these practical
constructions have been standardized, implemented, and deployed.
In general and as seems to be universally typical, the performance
of the practical constructions far exceed what can be rigorously proven.
Although the theoretical tools and designs provide the big ideas and
insights, it is the more detailed and precise heuristic tools and meth-
ods that have been developed and honed over the years to become
precision instruments that were used to craft the design details of the
1
Written on the interior glass wall of the EPFL cafeteria in the Computer Science Build-
ing BC, just near Place Alan Turing. Wikipedia attributed to Johannes L. A. van de
Snepscheut and also to Yogi Berra.
215
剩余111页未读,继续阅读
熊比尔
- 粉丝: 0
- 资源: 4
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功