fountain

package module
v0.0.0-...-4928733 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Aug 20, 2016 License: Apache-2.0 Imports: 3 Imported by: 3

README

gofountain

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.

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

Constants

This section is empty.

Variables

This section is empty.

Functions

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.

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

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 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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL