Go implementation of various fountain codes. Luby Transform, Online codes, Raptor code.

Includes many tests, libraries, and utilities.

The abstraction level is "low" -- that is, the code currently supports very low-level encoder/decoder level functionality, without any packetizing, etc. that a full system would include on top of this layer.



    Package fountain includes implementations of several fountain codes.

    Fountain codes have the property that a very large (more or less unlimited) number of code blocks can be generated from a fixed number of source blocks. The original message can be recovered from any subset of sufficient size of these code blocks, so even if some code blocks are lost, the message can still be reconstructed once a sufficient number have been received. So in a transmission system, the receiver need not notify the transmitter about every code block, it only need notify the transmitter when the source message has been fully reconstructed.

    The overall approach used by this package is that there are various codec implementations which follow the same overall algorithm -- splitting a source message into source blocks, manipulating those source blocks to produce a set of precode blocks, then for each code block to be produced, picking constituent precode blocks to use to create the code block, and then using an LT (Luby Transform) process to produce the code blocks.



    This section is empty.


    This section is empty.


    func NewMersenneTwister

    func NewMersenneTwister(seed int64) rand.Source

      NewMersenneTwister creates a new MT19937 PRNG with the given seed. The seed is converted to a 32-bit seed by XORing the high and low halves.

      func NewMersenneTwister64

      func NewMersenneTwister64(seed int64) rand.Source

        NewMersenneTwister64 creates a new 64-bit version of the MT19937 PRNG.


        type Codec

        type Codec interface {
        	// SourceBlocks returns the number of source blocks to be used in the
        	// codec. Note that this may not be the same number as the number of intermediate
        	// code blocks. It is the minimum number of encoded blocks necessary to
        	// reconstruct the original message.
        	SourceBlocks() int
        	// GenerateIntermediateBlocks prepares a set of precode blocks given the input
        	// message. The precode blocks may just be identically the blocks in the
        	// original message, or it may be a transformation on those source blocks
        	// derived from a codec-specific relationship.
        	// For example, in Online codes, this consists of adding auxiliary blocks.
        	// In a Raptor code, the entire set of source blocks is transformed into a
        	// different set of precode blocks.
        	GenerateIntermediateBlocks(message []byte, numBlocks int) []block
        	// PickIndices asks the codec to select the (non-strict subset of the) precode
        	// blocks to be used in the LT composition of a particular code block. These
        	// blocks will then be XORed to produce the code block.
        	PickIndices(codeBlockIndex int64) []int
        	// NewDecoder creates a decoder suitable for use with blocks encoded using this
        	// codec for a known message size (in bytes). The decoder will be initialized
        	// and ready to receive incoming blocks for decoding.
        	NewDecoder(messageLength int) Decoder

          Codec is an interface for fountain codes which follow the general scheme of preparing intermediate encoding representations based on the input message and picking LT composition indices given an integer code block number.

          func NewBinaryCodec

          func NewBinaryCodec(numSourceBlocks int) Codec

            NewBinaryCodec returns a codec implementing the binary fountain code, where source blocks composing each LT block are chosen randomly and independently.

            func NewLubyCodec

            func NewLubyCodec(sourceBlocks int, random *rand.Rand, degreeCDF []float64) Codec

              NewLubyCodec creates a new Codec using the provided number of source blocks, PRNG, and degree distribution function. The intermediate blocks will be a roughly-equal-sized partition of the source message padded so that all blocks have equal size. The indices will be picked using the provided PRNG seeded with the BlockCode ID of the LTBlock to be created, according to the degree CDF provided.

              func NewOnlineCodec

              func NewOnlineCodec(sourceBlocks int, epsilon float64, quality int, seed int64) Codec

                NewOnlineCodec creates a new encoder for an Online code. epsilon is the suboptimality parameter. ("Efficiency" or "e") A message of N blocks can be decoded with high probability from (1+3*epsilon)*numSourceBlocks received blocks. quality is the decoder quality factor ("q"). This parameter influences the failure rate of the decoder. Given (1+3*epsilon)*N blocks, the algorithm will fail with probability (epsilon/2)^(quality+1) seed is the random seed used to pick auxiliary encoding blocks.

                func NewRU10Codec

                func NewRU10Codec(numSourceSymbols int, symbolAlignmentSize int) Codec

                  NewRU10Codec creates an unsystematic raptor-like fountain codec which uses an intermediate block generation algorithm similar to the Raptor R10 codec.

                  func NewRaptorCodec

                  func NewRaptorCodec(sourceBlocks int, alignmentSize int) Codec

                    NewRaptorCodec creates a new R10 raptor codec using the provided number of source blocks and alignment size.

                    type Decoder

                    type Decoder interface {
                    	// AddBlocks adds a set of encoded blocks to the decoder. Returns true if the
                    	// message can be fully decoded. False if there is insufficient information.
                    	AddBlocks(blocks []LTBlock) bool
                    	// Decode extracts the decoded message from the decoder. If the decoder does
                    	// not have sufficient information to produce an output, returns a nil slice.
                    	Decode() []byte

                      Decoder is an interface allowing decoding of fountain-code-encoded messages as the blocks are received.

                      type LTBlock

                      type LTBlock struct {
                      	// BlockCode is the ID used to construct the encoded block.
                      	// The way in which the ID is mapped to the choice of blocks will vary by
                      	// codec.
                      	BlockCode int64
                      	// Data is the contents of the encoded block.
                      	Data []byte

                        LTBlock is an encoded block structure representing a block created using the LT transform.

                        func EncodeLTBlocks

                        func EncodeLTBlocks(message []byte, encodedBlockIDs []int64, c Codec) []LTBlock

                          EncodeLTBlocks encodes a sequence of LT-encoded code blocks from the given message and the block IDs. Suitable for use with any fountain.Codec. Note: This method is destructive to the message array.

                          type MersenneTwister

                          type MersenneTwister struct {
                          	// contains filtered or unexported fields

                            MersenneTwister is an implementation of the MT19937 PRNG of Matsumoto and Nishimura. Following Uses the 32-bit version of the algorithm. Satisfies math/rand.Source

                            func (*MersenneTwister) Int63

                            func (t *MersenneTwister) Int63() int64

                              Int63 produces a new int64 value between 0 and 2^63-1 by combining the bits of two Uint32 values.

                              func (*MersenneTwister) Seed

                              func (t *MersenneTwister) Seed(seed int64)

                              func (*MersenneTwister) Uint32

                              func (t *MersenneTwister) Uint32() uint32

                              type MersenneTwister64

                              type MersenneTwister64 struct {
                              	// contains filtered or unexported fields

                                MersenneTwister64 is a 64-bit MT19937 PRNG after Nishimura. See Satisfies math/rand.Source

                                func (*MersenneTwister64) Int63

                                func (t *MersenneTwister64) Int63() int64

                                  Int63 returns the next value from the PRNG. This value is the low 63 bits of the Uint64 value.

                                  func (*MersenneTwister64) Seed

                                  func (t *MersenneTwister64) Seed(seed int64)

                                    Seed initializes the state of the PRNG with the given seed value.

                                    func (*MersenneTwister64) SeedSlice

                                    func (t *MersenneTwister64) SeedSlice(seed []uint64)

                                      SeedSlice allows the twister to be initialized with a slice of seed values.

                                      func (*MersenneTwister64) Uint64

                                      func (t *MersenneTwister64) Uint64() uint64

                                        Uint64 returns the next pseudo-random value from the twister.