Effective October 1, 2012, QUALCOMM Incorporated completed a corporate reorganization in which the assets of certain of its businesses and groups, as well as the stock of certain of its direct and indirect subsidiaries, were contributed to Qualcomm Technologies, Inc. (QTI), a wholly-owned subsidiary of QUALCOMM Incorporated. Learn more about these changes

You are here

Raptor Codes Technical Overview

The world’s most advanced forward error correction (FEC) code for data networks, Raptor codes provide protection against packet loss by sending additional repair data used to reconstruct “erased” or “lost” data. Erasure codes provide data recovery by transforming a message into a longer message, allowing the original message to be recovered from a subset of the expanded message. RaptorQ™ recovers missing data packets with only minimal amounts of additional repair data and without requiring retransmission from the sendera efficiently and effectively providing reliability in data networks.

Raptor codes are fountain codes, built on LT codes

Luby Transform (LT) codes were the first class of efficient practical fountain codes, and were invented in 1998 by Michael Luby. A fountain code can generate a potentially unlimited amount of encoded data from the source data, where the source data can be efficiently and completely recovered from reception of any combination of encoded data essentially equal in size to the source data. Raptor codes build-on LT codes. They were invented by Amin Shokrollahi in 2001. For detailed technical information about the origin of Raptor Codes, please refer to Raptor Codes - IEEE Transactions On Information Theory.

How the Raptor fountain code algorithm works

Though advanced at the time, LT codes did not have linear decoding properties. The amount of time needed to decode was more than linear than the size of the data being decoded. The new concept with Raptor codes is to employ pre-coding to ease the recovery process (and speed up decoding). A light-weight pre-coding on the source symbols produces a small fraction of redundant symbols, which added to the source symbols, become the intermediate symbols. These have the desirable property of being recoverable once most of them are known, using the relationship built by the pre-coding. The intermediate symbols then become the input of the LT code. With this technique Raptor encoding and decoding take linear time, meaning the encoding and decoding speed is consistently linearly proportional to the size of the data being decoded across all source block sizes.

Raptor FEC characteristics:

  • Generate a potentially limitless amount of encoded data from any original set of source data
  • Support extremes of low or high loss as needed
  • Recover source data from an amount of received encoded data only slightly larger than the size of the source data, regardless of which specific encoded data has been received
  • Exceptionally fast encoding and decoding algorithms
  • Highly CPU-efficient solution with very low overhead

Raptor codes are the FEC of choice for standards

Raptor 10, known as “Raptor” in RFC 5053, has been included in many standards supported by the IETF, 3GPP and DVB. [RaptorQ], the latest and best performing Raptor FEC, is IETF RFC 6330. RaptorQ codes will continue to be adopted into a number of standards.
A recent monograph describing the theory behind Raptor Codes, and in particular the design rationale behind the Raptor 10 and RaptorQ codes is provided in Raptor Codes - Foundations and Trends in Communications and Information Theory, co-authored by Mike Luby and Amin Shokrollahi.

Raptor codes do not require a backchannel – allow great network efficiency

An application not using a Raptor forward error correction code typically has to employ protocols that use a lot of feedback and retransmission protocols to enable reliable file delivery or high quality media streaming. These protocols add overheads, require two-way data communication, and can be un-scalable. Using a Raptor code, an application can send and receive encoded data, and the fountain properties of the solution obviate, or greatly reduce the usage of feedback and retransmission protocols. This allows simpler, more scalable, and more efficient solutions.

Application Layer FEC provides flexibility in implementation

Raptor technology can be employed at the application or transport layer to provide reliability to data communications. Easily integrated into any application, Raptor FEC optimally protects streaming media or data distribution applications from the effects of packet loss, regardless of the source of the packet loss. Raptor technology is platform, source and content agnostic.

Guaranteed reliable delivery in end-to-end communications over any data network

Whether enhancing the quality of streaming content or accelerating the delivery of data, Raptor FEC provides complete flexibility in balancing and optimizing a specific application’s requirements for bandwidth utilization, latency, and degree of packet-loss protection. And because the algorithms employed by Raptor codes can be implemented as software on relatively low-power platforms, Raptor FEC enables a variety of new applications and services, including mobile platforms. For more information on how Raptor codes can be applied to streaming and content delivery solutions please visit our Resources page.