ldpccatalog

Documentation

Overview

Package ldpccatalog carries the precomputed pivot transcripts of every message parity-check code the decoder can select.

Building a decoder parity-check matrix is a Gallager construction followed by a systematic reduction. The construction is cheap and the reduction is not, yet the reduction discovers only one number per parity row: the column that row pivots at. Everything after it - the rank, the dependent rows, the column arrangement and both kinds of column swap - is a deterministic function of that sequence. So the sequence is precomputed here and the reduction is deleted from the decode path rather than made faster.

The catalog covers the complete legal key space rather than a reachable subset. A capacity is always a multiple of the row weight and never exceeds MaxCapacity, which bounds the space at a size worth storing outright; total coverage then discharges the completeness question by construction instead of by an enumeration that would have to be re-proved whenever a symbol shape changes.

Complete coverage costs roughly 13 MB per generator, so an ordinary build sweeps it on first use rather than embedding it into every dependant. A build tagged jabcode_ldpc_catalog_blob embeds the checked-in artifacts instead and spends the size to skip that sweep; the two carry the same bytes.

Index

• Constants
• func Blob(g Generator) []byte
• func Combined() []byte
• func Generate(g Generator) ([]byte, int, error)
• func Pivots(g Generator, wc, wr, capacity int) ([]uint16, bool)
• func Slot(wc, wr, capacity int) (int, bool)
• func SlotCount() int
• func StoredRows(wc, wr, capacity int) int
• func Wellformed(g Generator) bool
• type Generator
  • func GeneratorOf(variant wire.Variant) Generator
  • func (g Generator) Variant() wire.Variant

Constants

const (
	// MinColWeight and MaxRowWeight bound the ECC parameters a symbol may name.
	MinColWeight = 3
	MinRowWeight = 4
	MaxRowWeight = 11

	// MaxCapacity is the longest sub-block a correction may hold. It matches
	// MAX_SUB in the device shaders, which
	// detect.TestGPULDPCMatrixConstantsMatchShader holds together.
	MaxCapacity = 2816
)

The bounds of a selectable message code. A parity-check matrix outside them is refused before it reaches the catalog, so a missing slot is a defect and never an ordinary outcome.

const (
	PivotNone = 0xFFF
	SweepNone = 0xFFFF
)

PivotNone marks a dependent parity row inside a transcript. It is stored in the same twelve bits as a real pivot column, which reach 4095 while the largest column a legal capacity can name is MaxCapacity-1.

SweepNone is how ecc.PivotSweep spells the same thing. The two differ because the sweep is not bounded by the catalog's twelve-bit field, and Pivots translates between them rather than narrowing the sweep's sentinel.

Functions

func Blob

func Blob(g Generator) []byte

Blob is one generator's catalog as the device receives it: a little-endian u32 stream of the header, the directory and the packed record area. Returns nil when the build does not compile that generator's wire family.

func Combined

func Combined() []byte

Combined is every compiled catalog behind one prefix, as the device receives it: magic, format, then one base word per generator giving the word offset of that generator's catalog, or zero where the build does not carry it.

One buffer rather than one per generator is what lets the device select a generator by indexing rather than by binding a second resource, and it is what lets the whole catalog ride a single device allocation.

func Generate

func Generate(g Generator) ([]byte, int, error)

Generate computes one generator's catalog from scratch, producing exactly the bytes the checked-in artifact holds, and reports how many pivots it stored.

It is what an ordinary build runs on first use and what the generator command writes, so the two forms share one implementation instead of two that can drift. Keys are independent, so the sweeps run across the machine while the packing stays in slot order. It is minutes of elimination, which is the whole cost of keeping the artifact out of a dependant's binary.

func Pivots

func Pivots(g Generator, wc, wr, capacity int) ([]uint16, bool)

Pivots reconstructs one code's full pivot sequence, leading block included, in the form ecc.PivotSweep would have returned. It is the host mirror of what the device reconstruction does, and exists so the catalog can be checked against the builder it replaces.

func Slot

func Slot(wc, wr, capacity int) (int, bool)

Slot numbers a key within one generator's directory. Keys are dense by construction - every multiple of wr up to MaxCapacity is legal for every admissible column weight - so the directory is a perfect hash with no probing, no collision handling and no stored key to compare against.

The device computes the same number from the payload shape it already holds, which is why the arithmetic is kept trivial.

func SlotCount

func SlotCount() int

SlotCount is the size of one generator's directory.

func StoredRows

func StoredRows(wc, wr, capacity int) int

StoredRows is how many pivots a key contributes to the record area. The leading Gallager block is omitted because ecc.LeadingPivot already gives it.

func Wellformed

func Wellformed(g Generator) bool

Wellformed reports whether a catalog is present and its header describes the directory and record area this build expects. It is what a consumer checks before uploading, so a catalog regenerated under a changed format is caught at the boundary rather than as a wrong parity matrix.

Types

type Generator

type Generator uint8

Generator names the pseudo-random column permutation a wire variant builds its Gallager copies with. The two families need separate catalogs because a permutation change moves every pivot.

const (
	// GeneratorISO is the ISO/IEC 23634 permutation.
	GeneratorISO Generator = 0
	// GeneratorLCG is the C-family 64-bit permutation.
	GeneratorLCG Generator = 1
)

func GeneratorOf

func GeneratorOf(variant wire.Variant) Generator

GeneratorOf reports which catalog a wire variant reads.

func (Generator) Variant

func (g Generator) Variant() wire.Variant

Variant returns a wire variant that builds its codes with g, for a consumer that has a generator and needs to call the matrix builder.