Decoding methods: Difference between revisions

Revision as of 07:34, 16 October 2019

Revision as of 07:46, 16 October 2019

Line 132:

For '''Binary''' codes, if both <math>k</math> and <math>n-k</math> are not too big, and assuming the code generating matrix is in standard form, syndrome decoding can be computed using 2 precomputed lookup tables and 2 XORs only. <ref>[[Jack Keil Wolf ]] (2008) ''An Introduction to Error Correcting Codes'', Course: Communication Systems III, [[UCSD]], http://circuit.ucsd.edu/~yhk/ece154c-spr17/pdfs/ErrorCorrectionI.pdf</ref>

Let <math>z</math> be the received (possibly erroneous)noisy code-word, i.e. <math>z=x\oplus e</math>. Using the encoding lookup table of size <math>2^k</math>, the code-word <math>z'</math> corresponding to the first <math>k</math> bits of <math>z</math> is found.

The syndrome is then computed as the last <math>n-k</math> bits of <math>s=z\oplus z'</math> (the first <math>k</math> bits of the XOR are zero [since the generating matrix is in standard form] and discarded). Using the syndrome, the error <math>e</math> is computed using the syndrome lookup table of size <math>2^{n-k}</math>, and the decoding is then computed via <math>x = z \oplus e</math> (for the encoded code-word, or the first <math>k</math> bits of <math>x</math> for the original word).

The number of entries in the two lookup tables is <math>2^k+2^{n-k}</math>, which is significantly smaller than <math>2^n</math> required for [[standard array|standard array decoding]] that requires only <math>1</math> lookup. Additionally, the precomputed encoding lookup table can be used for the encoding, and is thus often useful to have.