Fountain codes
Fountain codes
复制标题
DOI：
10.1049/ip-com:20050237
复制
发表时间：
2005-12-01
期刊：
影响因子：
--
通讯作者：
MacKay, DJC
中科院分区：
文献类型：
--
作者：
MacKay, DJC
喷泉码是一种破纪录的稀疏图码，适用于有擦除的信道，如互联网，文件以多个小数据包传输，每个数据包要么被无错误地接收，要么没有被接收。标准的文件传输协议只是将文件分割成K个数据包大小的片段，然后重复传输每个数据包，直到成功接收。发送器需要一个反向信道来找出哪些数据包需要重传。相比之下，喷泉码使数据包成为整个文件的随机函数。发送器在接收器处喷射分组，而不知道接收到哪些分组。一旦接收器已经接收到任何N个分组，其中N仅略大于原始文件大小K，则可以恢复整个文件。本文综述了随机线性喷泉码、LT码和Raptor码。最好的喷泉码的计算成本非常小，与文件大小呈线性关系。
Fountain codes are record-breaking sparse-graph codes for channels with erasures, such as the internet, where files are transmitted in multiple small packets, each of which is either received without error or not received. Standard file transfer protocols simply chop a file up into K packet-sized pieces, then repeatedly transmit each packet until it is successfully received. A back channel is required for the transmitter to find out which packets need retransmitting. In contrast, fountain codes make packets that are random functions of the whole file. The transmitter sprays packets at the receiver without any knowledge of which packets are received. Once the receiver has received any N packets, where N is just slightly greater than the original file size K, the whole file can be recovered. In the paper random linear fountain codes, LT codes, and raptor codes are reviewed. The computational costs of the best fountain codes are astonishingly small, scaling linearly with the file size.