Berlekamp–Massey algorithm: Difference between revisions

Revision as of 20:29, 12 September 2016

Revision as of 20:31, 12 September 2016

Line 139:

==The algorithm for the binary field==

The following is the Berlekamp–Massey algorithm specialized for the typical binary [[finite field]] F₂ (also written GF(2)). The field elements are '0' and '1'. The field operations '+' and '−' are identical and are equivalent to the 'exclusive or' operation, XOR. The multiplication operator '*' becomes the logical AND operation. The division operator reduces to the identity operation (i.e., field division is only defined for dividing by 1, and x/1 = x).

#Let <math>s_0, s_1, s_2 \cdots s_{n-1}</math> be the [[bit]]s of the stream.