Syndrome ($s=H{y}^T$)

The syndrome of a received word $y$ with respect to a parity-check matrix $H$ is $s=H{y}^T$. It vanishes exactly when $y$ is a codeword and otherwise identifies the coset containing the error pattern.

For a linear code with parity-check matrix $H$, write the received word as $y=c+e$, where $c$ is a codeword and $e$ an error pattern. Its syndrome depends only on the error because $H{c}^T=0$. A syndrome decoder chooses a representative error $\hat{e}$ with that syndrome and returns $y-\hat{e}$. Choosing a minimum-Hamming weight representative gives minimum-distance decoding; within the guaranteed correction radius it recovers the unique transmitted codeword. Several representatives may tie outside that radius.

For a rank-$(N-k)$ parity-check matrix of a linear code $C$, two words have equal syndromes exactly when their difference lies in $C$. Thus attainable syndromes label cosets bijectively. For a received word $c+e$, its syndrome is that of the error $e$, so minimum-weight representatives provide minimum-distance decoding.

// Target: algebra.bigb

A coset leader is a minimum-Hamming-weight word in a coset of a linear code. It represents a most economical error pattern with the associated syndrome. Several leaders can tie; they need not be unique outside the code's guaranteed correction radius.