galois.BCH.decode

galois.BCH.decode(codeword: ArrayLike, erasures: NDArray | None = None, output: 'message' | 'codeword' = 'message', errors: False = False) → FieldArray

galois.BCH.decode(codeword: ArrayLike, erasures: NDArray | None = None, output: 'message' | 'codeword' = 'message', errors: True = True) → tuple[FieldArray, int | ndarray]

Decodes the codeword \(\mathbf{c}\) into the message \(\mathbf{m}\).

Parameters:¶

codeword: ArrayLike¶

The codeword as either a \(n\)-length vector or \((N, n)\) matrix, where \(N\) is the number of codewords.

Shortened codes

For the shortened \([n-s,\ k-s,\ d]\) code, pass \(n-s\) codeword symbols into decode() to return the \(k-s\) message symbols.

erasures: NDArray | None = None¶

Optionally specify the erasure locations as a boolean array with shape equal to the codeword, where True indicates an erasure at that location. The default is None, which indicates no erasures.

output: 'message' | 'codeword' = 'message'¶

Specify whether to return the error-corrected message or entire codeword. The default is "message".

errors: False = False¶

errors: True = True

Optionally specify whether to return the number of corrected errors. The default is False. If erasures are provided, the number of corrected errors does not include the number of erasures corrected, only the number of unknown symbol errors corrected.

Returns:¶

If output="message", the error-corrected message as either a \(k\)-length vector or \((N, k)\) matrix. If output="codeword", the error-corrected codeword as either a \(n\)-length vector or \((N, n)\) matrix.
If errors=True, returns the number of corrected symbol errors as either a scalar or \(N\)-length array. Valid number of corrections are in \([0, t]\). If a codeword has too many errors and cannot be corrected, -1 will be returned.

Notes¶

The message vector \(\mathbf{m}\) is a member of \(\mathrm{GF}(q)^k\). The corresponding message polynomial \(m(x)\) is a degree-\(k\) polynomial over \(\mathrm{GF}(q)\).

\[\mathbf{m} = [m_{k-1},\ \dots,\ m_1,\ m_0] \in \mathrm{GF}(q)^k\]

\[m(x) = m_{k-1} x^{k-1} + \dots + m_1 x + m_0 \in \mathrm{GF}(q)[x]\]

The codeword vector \(\mathbf{c}\) is a member of \(\mathrm{GF}(q)^n\). The corresponding codeword polynomial \(c(x)\) is a degree-\(n\) polynomial over \(\mathrm{GF}(q)\). Each codeword polynomial \(c(x)\) is divisible by the generator polynomial \(g(x)\).

\[\mathbf{c} = [c_{n-1},\ \dots,\ c_1,\ c_0] \in \mathrm{GF}(q)^n\]

\[c(x) = c_{n-1} x^{n-1} + \dots + c_1 x + c_0 \in \mathrm{GF}(q)[x]\]

In decoding, the syndrome vector \(\mathbf{s}\) is computed by evaluating the received codeword \(\mathbf{r}\) in the extension field \(\mathrm{GF}(q^m)\) at the roots \(\alpha^c, \dots, \alpha^{c+d-2}\) of the generator polynomial \(g(x)\). The equivalent polynomial operation computes the remainder of \(r(x)\) by \(g(x)\) in the extension field \(\mathrm{GF}(q^m)\).

\[\mathbf{s} = [r(\alpha^c),\ \dots,\ r(\alpha^{c+d-2})] \in \mathrm{GF}(q^m)^{d-1}\]

\[s(x) = r(x)\ \textrm{mod}\ g(x) \in \mathrm{GF}(q^m)[x]\]

A syndrome of zeros indicates the received codeword is a valid codeword and there are no errors. If the syndrome is non-zero, the decoder will find an error-locator polynomial \(\sigma(x)\) and the corresponding error locations and values.

Note

The \([n, k, d]_q\) code has \(d_{min} \ge d\) minimum distance. It can detect up to \(d_{min}-1\) errors.

Examples¶

Vector Vector (shortened) Matrix Matrix (shortened) Matrix (erasures)

Encode a single message using the \(\textrm{BCH}(15, 7)\) code.

In [1]: bch = galois.BCH(15, 7)

In [2]: GF = bch.field

In [3]: m = GF.Random(bch.k); m
Out[3]: GF([0, 0, 1, 0, 1, 1, 0], order=2)

In [4]: c = bch.encode(m); c
Out[4]: GF([0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1], order=2)

Corrupt \(t\) symbols of the codeword.

In [5]: bch.t
Out[5]: 2

In [6]: c[0:bch.t] ^= 1; c
Out[6]: GF([1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1], order=2)

Decode the codeword and recover the message.

In [7]: d = bch.decode(c); d
Out[7]: GF([0, 0, 1, 0, 1, 1, 0], order=2)

In [8]: assert np.array_equal(d, m)

Decode the codeword, outputting the number of corrected errors, and recover the message.

In [9]: d, e = bch.decode(c, errors=True); d, e
Out[9]: (GF([0, 0, 1, 0, 1, 1, 0], order=2), 2)

In [10]: assert np.array_equal(d, m)

Encode a single message using the shortened \(\textrm{BCH}(12, 4)\) code.

In [11]: bch = galois.BCH(15, 7)

In [12]: GF = bch.field

In [13]: m = GF.Random(bch.k - 3); m
Out[13]: GF([1, 1, 0, 0], order=2)

In [14]: c = bch.encode(m); c
Out[14]: GF([1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1], order=2)

Corrupt \(t\) symbols of the codeword.

In [15]: bch.t
Out[15]: 2

In [16]: c[0:bch.t] ^= 1; c
Out[16]: GF([0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1], order=2)

Decode the codeword and recover the message.

In [17]: d = bch.decode(c); d
Out[17]: GF([1, 1, 0, 0], order=2)

In [18]: assert np.array_equal(d, m)

Decode the codeword, outputting the number of corrected errors, and recover the message.

In [19]: d, e = bch.decode(c, errors=True); d, e
Out[19]: (GF([1, 1, 0, 0], order=2), 2)

In [20]: assert np.array_equal(d, m)

Encode a matrix of three messages using the \(\textrm{BCH}(15, 7)\) code.

In [21]: bch = galois.BCH(15, 7)

In [22]: GF = bch.field

In [23]: m = GF.Random((3, bch.k)); m
Out[23]: 
GF([[1, 0, 0, 1, 1, 0, 1],
    [0, 0, 1, 0, 0, 1, 1],
    [0, 1, 1, 0, 1, 1, 1]], order=2)

In [24]: c = bch.encode(m); c
Out[24]: 
GF([[1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0],
    [0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0]], order=2)

Corrupt the codeword. Add zero errors to the first codeword, one to the second, and two to the third.

In [25]: c[1,0:1] ^= 1

In [26]: c[2,0:2] ^= 1

In [27]: c
Out[27]: 
GF([[1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0],
    [1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0],
    [1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0]], order=2)

Decode the codeword and recover the message.

In [28]: d = bch.decode(c); d
Out[28]: 
GF([[1, 0, 0, 1, 1, 0, 1],
    [0, 0, 1, 0, 0, 1, 1],
    [0, 1, 1, 0, 1, 1, 1]], order=2)

In [29]: assert np.array_equal(d, m)

Decode the codeword, outputting the number of corrected errors, and recover the message.

In [30]: d, e = bch.decode(c, errors=True); d, e
Out[30]: 
(GF([[1, 0, 0, 1, 1, 0, 1],
     [0, 0, 1, 0, 0, 1, 1],
     [0, 1, 1, 0, 1, 1, 1]], order=2),
 array([0, 1, 2]))

In [31]: assert np.array_equal(d, m)

Encode a matrix of three messages using the shortened \(\textrm{BCH}(12, 4)\) code.

In [32]: bch = galois.BCH(15, 7)

In [33]: GF = bch.field

In [34]: m = GF.Random((3, bch.k - 3)); m
Out[34]: 
GF([[1, 1, 0, 1],
    [0, 0, 0, 1],
    [0, 1, 1, 0]], order=2)

In [35]: c = bch.encode(m); c
Out[35]: 
GF([[1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0],
    [0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
    [0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1]], order=2)

Corrupt the codeword. Add zero errors to the first codeword, one to the second, and two to the third.

In [36]: c[1,0:1] ^= 1

In [37]: c[2,0:2] ^= 1

In [38]: c
Out[38]: 
GF([[1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0],
    [1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
    [1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1]], order=2)

Decode the codeword and recover the message.

In [39]: d = bch.decode(c); d
Out[39]: 
GF([[1, 1, 0, 1],
    [0, 0, 0, 1],
    [0, 1, 1, 0]], order=2)

In [40]: assert np.array_equal(d, m)

Decode the codeword, outputting the number of corrected errors, and recover the message.

In [41]: d, e = bch.decode(c, errors=True); d, e
Out[41]: 
(GF([[1, 1, 0, 1],
     [0, 0, 0, 1],
     [0, 1, 1, 0]], order=2),
 array([0, 1, 2]))

In [42]: assert np.array_equal(d, m)

Encode a matrix of three messages using the \(\textrm{BCH}(15, 7)\) code.

In [43]: bch = galois.BCH(15, 7)

In [44]: GF = bch.field

In [45]: m = GF.Random((3, bch.k)); m
Out[45]: 
GF([[0, 0, 1, 0, 0, 1, 1],
    [0, 0, 1, 0, 0, 0, 1],
    [0, 1, 1, 0, 0, 1, 1]], order=2)

In [46]: c = bch.encode(m); c
Out[46]: 
GF([[0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1],
    [0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0]], order=2)

Corrupt the codeword. Add one error to the first codeword, two to the second, and \(d - 1\) to the third.

In [47]: erasures = np.zeros(c.shape, dtype=bool)

In [48]: erasures[0,0:1] = True

In [49]: erasures[1,0:2] = True

In [50]: erasures[2,0:bch.d - 1] = True

In [51]: c[erasures] += GF.Random(np.sum(erasures), low=1)

In [52]: c
Out[52]: 
GF([[1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0],
    [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1],
    [1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0]], order=2)

Decode the codeword using known error locations (erasures) and recover the message.

In [53]: d = bch.decode(c, erasures=erasures); d
Out[53]: 
GF([[0, 0, 1, 0, 0, 1, 1],
    [0, 0, 1, 0, 0, 0, 1],
    [0, 1, 1, 0, 0, 1, 1]], order=2)

In [54]: assert np.array_equal(d, m)

Decode the codeword, outputting the number of corrected errors, and recover the message. Notice that zero unknown errors were corrected, since all errors were provided as erasures.

In [55]: d, e = bch.decode(c, erasures=erasures, errors=True); d, e
Out[55]: 
(GF([[0, 0, 1, 0, 0, 1, 1],
     [0, 0, 1, 0, 0, 0, 1],
     [0, 1, 1, 0, 0, 1, 1]], order=2),
 array([0, 0, 0]))

In [56]: assert np.array_equal(d, m)