Documentation ¶
Overview ¶
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.
Index ¶
- func NewMersenneTwister(seed int64) rand.Source
- func NewMersenneTwister64(seed int64) rand.Source
- type Codec
- func NewBinaryCodec(numSourceBlocks int) Codec
- func NewLubyCodec(sourceBlocks int, random *rand.Rand, degreeCDF []float64) Codec
- func NewOnlineCodec(sourceBlocks int, epsilon float64, quality int, seed int64) Codec
- func NewRU10Codec(numSourceSymbols int, symbolAlignmentSize int) Codec
- func NewRaptorCodec(sourceBlocks int, alignmentSize int) Codec
- type Decoder
- type LTBlock
- type MersenneTwister
- type MersenneTwister64
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func NewMersenneTwister ¶
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 ¶
NewMersenneTwister64 creates a new 64-bit version of the MT19937 PRNG.
Types ¶
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 ¶
NewBinaryCodec returns a codec implementing the binary fountain code, where source blocks composing each LT block are chosen randomly and independently.
func NewLubyCodec ¶
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 ¶
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 ¶
NewRU10Codec creates an unsystematic raptor-like fountain codec which uses an intermediate block generation algorithm similar to the Raptor R10 codec.
func NewRaptorCodec ¶
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 ¶
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 http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf 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 http://dl.acm.org/citation.cfm?id=369540&dl=ACM&coll=DL&CFID=261426526&CFTOKEN=25107569 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.