Documentation
¶
Overview ¶
Package fec provides the error-detection and error-correction primitives used inside a burst.
The design principle here is that three different failure modes need three different defences, and conflating them is how acoustic links end up "mostly working":
- CRC detects. It is cheap, it is exact, and it never guesses.
- Reed-Solomon corrects. It fixes the random bit errors that noise produces.
- Interleaving spreads. It converts the burst errors that reverb, dropouts and a passing hand produce into random-looking errors that Reed-Solomon can actually correct.
None of them replaces ARQ, which handles the losses that no inner code survives.
Index ¶
- Constants
- Variables
- func CRC32(data []byte) uint32
- func CRC32Update(sum uint32, data []byte) uint32
- func VerifyCRC32(data []byte, want uint32) error
- type BlockCodec
- type Codec
- type ConvInterleaver
- type Identity
- type Interleaver
- func (i *Interleaver) BlockLen() int
- func (i *Interleaver) Deinterleave(src []byte) ([]byte, error)
- func (i *Interleaver) DeinterleaveFloats(src []float64) ([]float64, error)
- func (i *Interleaver) Depth() int
- func (i *Interleaver) Interleave(src []byte) ([]byte, error)
- func (i *Interleaver) Spread() int
- type ReedSolomon
- func (r *ReedSolomon) CodewordLen() int
- func (r *ReedSolomon) DataLen() int
- func (r *ReedSolomon) Decode(dst, src []byte) (int, error)
- func (r *ReedSolomon) DecodeSoft(dst, src []byte, confidence []float64, threshold float64) (int, error)
- func (r *ReedSolomon) Encode(dst, src []byte) ([]byte, error)
- func (r *ReedSolomon) EncodedLen(n int) int
- func (r *ReedSolomon) MaxCorrectable() int
- func (r *ReedSolomon) MaxErasures() int
- func (r *ReedSolomon) Name() string
- type SoftCodec
Constants ¶
const ( // ReedSolomonName is the codec name used in profiles and capability // exchange. It stays stable across parameter choices, so a peer can // advertise the code without also having to agree on its rate before it can // be named. ReedSolomonName = "rs" // RSShardSize is the GF(2^8) codeword limit: a codeword is a polynomial over // GF(2^8) and cannot have more than 255 coefficients. RSShardSize = 255 // RSDefaultData and RSDefaultParity are the parameters ByName resolves "rs" // to when no explicit size is given. They are a rate-1/2 code, matching the // shipped link's default: the simulator shows rate 1/2 is the knee for the // robust profile, and the two must agree or a probe estimate and a transfer // would tell different stories about the same room. RSDefaultData = 64 RSDefaultParity = 64 )
Variables ¶
var ( // ErrCRCMismatch means the frame was received but is not intact. ErrCRCMismatch = errors.New("fec: CRC mismatch") // ErrEmpty means a frame carried no data at all. ErrEmpty = errors.New("fec: empty input") // ErrUncorrectable means the code found more errors than it can fix. The // caller must discard the block, never use it partially. ErrUncorrectable = errors.New("fec: uncorrectable") // ErrNotImplemented marks a declared-but-unwritten codec. ErrNotImplemented = errors.New("fec: not implemented") // ErrBlockSize means the input length is not a whole number of code blocks. ErrBlockSize = errors.New("fec: input is not a whole number of blocks") // ErrBadParams means a codec was constructed with sizes it cannot support. ErrBadParams = errors.New("fec: invalid codec parameters") // ErrBufferTooSmall means the caller's destination cannot hold the result. ErrBufferTooSmall = errors.New("fec: destination buffer too small") // ErrConfidence means a soft decoder was given a confidence count that does // not match the number of coded bytes. ErrConfidence = errors.New("fec: confidence length does not match input") )
Functions ¶
func CRC32Update ¶
CRC32Update extends a running CRC-32C with more data.
func VerifyCRC32 ¶
VerifyCRC32 reports whether data matches want, distinguishing the three outcomes that callers actually care about: valid, corrupt, and no data at all.
Types ¶
type BlockCodec ¶
type BlockCodec interface {
Codec
// DataLen is the number of data bytes in one codeword.
DataLen() int
// CodewordLen is the number of bytes one codeword occupies on the wire.
CodewordLen() int
}
BlockCodec is a Codec with a fixed block geometry: dataLen bytes in, dataLen+parity out per codeword. A block interleaver needs this to line its rows up with codewords, so that a burst of lost bytes becomes one lost symbol per codeword rather than a whole codeword's worth in one place.
type Codec ¶
type Codec interface {
// Name identifies the codec in profiles, logs and peer capability exchange.
Name() string
// EncodedLen returns the encoded length for an input of n bytes.
EncodedLen(n int) int
// Encode writes the systematic encoding of src into dst, which must be at
// least EncodedLen(len(src)) bytes, and returns the used prefix.
Encode(dst, src []byte) ([]byte, error)
// Decode writes the corrected copy of src into dst, which must be at least
// len(src). It returns the number of corrected symbols, or ErrUncorrectable
// if the block cannot be repaired.
Decode(dst, src []byte) (corrected int, err error)
// MaxCorrectable is the number of symbol errors the code can repair per
// block. Zero means detection only.
MaxCorrectable() int
}
Codec is a systematic block code applied to a burst's payload. "Systematic" is a requirement, not an implementation detail: the recovered data must appear in the output in the same order it went in, so that a burst that decodes with zero corrections is byte-identical to what the sender framed. That property is what lets the MAC layer's CRC and the transfer layer's digest agree about what was actually sent.
type ConvInterleaver ¶
type ConvInterleaver struct {
// contains filtered or unexported fields
}
ConvInterleaver is a convolutional (Ramsey type III) interleaver. It achieves the same burst-spreading as the block interleaver with half the latency and half the memory, which matters when the link is turning around every few hundred milliseconds. It is declared here because the block interleaver's latency may prove to be the wrong trade once real turnaround times are measured, and because the interface should not have to change when that decision is made.
func NewConvInterleaver ¶
func NewConvInterleaver(depth, width int) *ConvInterleaver
NewConvInterleaver returns a convolutional interleaver with the given depth and symbol width.
func (*ConvInterleaver) Deinterleave ¶
func (c *ConvInterleaver) Deinterleave(_ []byte) ([]byte, error)
Deinterleave is not yet implemented; see the type comment.
func (*ConvInterleaver) Depth ¶
func (c *ConvInterleaver) Depth() int
Depth returns the interleaving depth.
func (*ConvInterleaver) Interleave ¶
func (c *ConvInterleaver) Interleave(_ []byte) ([]byte, error)
Interleave is not yet implemented; see the type comment.
type Identity ¶
type Identity struct{}
Identity is the rate-1 codec: it adds no redundancy and corrects nothing. It is the correct default for v0 and it is not a placeholder. ARQ is the primary reliability mechanism, and a link with ARQ and no inner FEC is fully lossless; it is merely less efficient under noise. Starting with Identity keeps the first working version honest about where its reliability actually comes from.
func (Identity) EncodedLen ¶
func (Identity) MaxCorrectable ¶
type Interleaver ¶
type Interleaver struct {
// contains filtered or unexported fields
}
Interleaver is a block interleaver over a matrix of rows x cols bytes. Semantics: the sender writes codewords as rows and transmits columns; the receiver fills columns and reads rows. A burst error in transmission therefore lands as one byte per row on the receiving side.
func NewInterleaver ¶
func NewInterleaver(rows, cols int) *Interleaver
NewInterleaver returns an interleaver with the given dimensions. rows is the interleaving depth - how many consecutive codewords get mixed together - and cols is the codeword length.
func (*Interleaver) BlockLen ¶
func (i *Interleaver) BlockLen() int
BlockLen returns the number of bytes the interleaver consumes and produces per operation.
func (*Interleaver) Deinterleave ¶
func (i *Interleaver) Deinterleave(src []byte) ([]byte, error)
Deinterleave reverses Interleave. It is its own inverse in structure but not in indexing, hence a separate method rather than a clever reuse.
func (*Interleaver) DeinterleaveFloats ¶
func (i *Interleaver) DeinterleaveFloats(src []float64) ([]float64, error)
DeinterleaveFloats applies the same permutation as Deinterleave to a parallel slice. It exists for soft decoding: the per-symbol confidence travels beside the coded bytes, and if it is not permuted with them it points at the wrong symbols after deinterleaving, which is worse than having no confidence at all.
func (*Interleaver) Depth ¶
func (i *Interleaver) Depth() int
Depth returns the interleaving depth in codewords.
func (*Interleaver) Interleave ¶
func (i *Interleaver) Interleave(src []byte) ([]byte, error)
Interleave returns a new buffer with src permuted for transmission. src must be exactly BlockLen bytes.
func (*Interleaver) Spread ¶
func (i *Interleaver) Spread() int
Spread is the number of consecutive on-air symbols that a single lost codeword symbol becomes after deinterleaving. It is the number that matters when sizing FEC against a measured dropout length.
type ReedSolomon ¶
type ReedSolomon struct {
// contains filtered or unexported fields
}
ReedSolomon is a systematic, shortened Reed-Solomon code over GF(2^8).
Input is split into blocks of data bytes; the final block is zero-padded, and each block becomes one codeword of data+parity bytes. The codeword is laid out low-degree-first, exactly as gf.go's polynomials are stored, which puts the parity bytes before the data on the wire. Nothing outside this package may assume the on-air order: the inspector sees parity-then-data, and that is documented rather than hidden so that a test that round-trips through the real encoder is the only kind that proves anything.
func NewReedSolomon ¶
func NewReedSolomon(dataBytes, parityBytes int) (*ReedSolomon, error)
NewReedSolomon constructs a codec whose codewords are dataBytes+parityBytes long. Both must be positive, and the codeword must not exceed RSShardSize.
func (*ReedSolomon) CodewordLen ¶
func (r *ReedSolomon) CodewordLen() int
CodewordLen is the number of bytes one codeword occupies on the wire.
func (*ReedSolomon) DataLen ¶
func (r *ReedSolomon) DataLen() int
DataLen is the number of data bytes in one codeword.
func (*ReedSolomon) Decode ¶
func (r *ReedSolomon) Decode(dst, src []byte) (int, error)
Decode implements Codec, correcting unknown errors only.
func (*ReedSolomon) DecodeSoft ¶
func (r *ReedSolomon) DecodeSoft(dst, src []byte, confidence []float64, threshold float64) (int, error)
DecodeSoft corrects src using a per-byte confidence, where lower means less trustworthy. Bytes whose confidence falls below threshold become erasures, up to the code's erasure capacity per codeword; if more than that many are below threshold, the least confident are erased and the rest are left as ordinary errors for Berlekamp-Massey to find.
func (*ReedSolomon) Encode ¶
func (r *ReedSolomon) Encode(dst, src []byte) ([]byte, error)
Encode implements Codec.
func (*ReedSolomon) EncodedLen ¶
func (r *ReedSolomon) EncodedLen(n int) int
EncodedLen implements Codec. It rounds up to whole codewords, because a block that does not fill a codeword still costs a whole one.
func (*ReedSolomon) MaxCorrectable ¶
func (r *ReedSolomon) MaxCorrectable() int
MaxCorrectable implements Codec: half the parity, as Reed-Solomon always is.
func (*ReedSolomon) MaxErasures ¶
func (r *ReedSolomon) MaxErasures() int
MaxErasures is how many known-erased symbols a codeword can recover. It is the full parity count rather than half of it, and that factor of two is the entire reason the soft path exists.
type SoftCodec ¶
type SoftCodec interface {
Codec
DecodeSoft(dst, src []byte, confidence []float64, threshold float64) (int, error)
// MaxErasures is how many known-erased symbols can be recovered per block.
MaxErasures() int
}
SoftCodec is a Codec that can use per-symbol reliability. DecodeSoft is the erasure-aware entry point: confidence[i] describes src[i], lower meaning less trustworthy, and symbols below threshold are treated as known erasures. It is a separate interface rather than a method on Codec because a codec that does not implement it is still perfectly usable through Decode, and a caller should never be forced to invent a confidence it does not have.
Source Files