Content deleted Content added
m →Example |
→Decoder: add explanations and a large example. |
||
Line 72:
p_x(1110)= 1,\;
p_x(1111)= 0\,.</math>As a result, C(1 1010 010101) = 1101 1110 0001 0010 holds.
=== Decoder ===
As was already mentioned, Lagrange interpolation can be used to efficiently retrieve the message from a codeword. However, a decoder needs to work even if the codeword has been corrupted in a few positions, that is, when the received word is different from any codeword. In this case, a local decoding procedure can help.
=== Decoder ===
{{Expand section|date=August 2018}}
As was already mentioned, Lagrange interpolation can be used to efficiently retrieve the message from a codeword. However, a decoder needs to work even if the codeword has been corrupted in a few positions, that is, when the received word is different from any codeword. In this case, a local decoding procedure can help.
The algorithm from Reed is based on the following property:
you start from the code word, that is a sequence of evaluation points from an unknown polynomial <math display="inline"> p_x </math> of <math display="inline"> {\mathbb F}_2[X_1,X_2,...,X_m] </math> of degree at most <math display="inline"> r </math> that you want to find. The sequence may contains any number of errors up to <math display="inline"> 2^{m-r-1}-1 </math> included.
If you consider a monomial <math display="inline"> \mu </math> of the highest degree <math display="inline"> d </math> in <math display="inline"> p_x </math> and sum all the evaluation points of the polynomial where all variables in <math display="inline"> \mu </math> have the values 0 or 1, and all the other variables have value 0, you get the value of the coefficient (0 or 1) of <math display="inline"> \mu </math> in <math display="inline"> p_x </math> (There are <math display="inline"> 2^d </math> such points). This is due to the fact that all lower monomial divisors of <math display="inline"> \mu </math> appears an even number of time in the sum, and only <math display="inline"> \mu </math> appears once.
To take into account the possibility of errors, you can also remark that you can fix the value of other variables to any value. So instead of doing the sum only once for other variables not in <math display="inline"> \mu </math> with 0 value, you do it <math display="inline"> 2^{m-d} </math> times for each fixed valuations of the other variables. If there is no error, all those sums should be equals to the value of the coefficient searched.
The algorithm consists here to take the majority of the answers as the value searched. If the minority is larger than the maximum number of errors possible, the decoding step fails knowing there are too much errors in the input code.
Once a coefficient is computed, if it's 1, update the code to remove the monomial <math display="inline"> \mu </math> from the input code and continue to next monomial, in reverse order of their degree.
==== Example ====
Let's consider the previous example and start from the code. With <math display="inline"> r=2, m=4 </math> we can fix at most 1 error in the code.
Consider the input code as 1101 1110 0001 0110 (this is the previous code with one error).
We know the degree of the polynomial <math display="inline"> p_x </math> is at most <math display="inline"> r=2 </math>, we start by searching for monomial of degree 2.
* <math display="inline"> \mu=X_3X_4 </math>
** we start by looking for evaluation points with <math display="inline"> X_1=0, X_2=0, X_3\in\{0,1\}, X_4\in\{0,1\}</math>. In the code this is: <u>1101</u> 1110 0001 0110. The first sum is 1 (odd number of 1).
** we look for evaluation points with <math display="inline"> X_1=0, X_2=1, X_3\in\{0,1\}, X_4\in\{0,1\}</math>. In the code this is: 1101 <u>1110 </u>0001 0110. The second sum is 1.
** we look for evaluation points with <math display="inline"> X_1=1, X_2=0, X_3\in\{0,1\}, X_4\in\{0,1\}</math>. In the code this is: 1101 1110 <u>0001</u> 0110. The third sum is 1.
** we look for evaluation points with <math display="inline"> X_1=1, X_2=1, X_3\in\{0,1\}, X_4\in\{0,1\}</math>. In the code this is: 1101 1110 0001 <u>0110</u>. The third sum is 0 (even number of 1).
The four sums don't agree (so we know there is an error), but the minority report is not larger than the maximum number of error allowed (1), so we take the majority and the coefficient of <math display="inline"> \mu </math> is 1.
We remove <math display="inline"> \mu </math> from the code before continue :
code : 1101 1110 0001 0110, valuation of <math display="inline"> \mu </math> is 0001000100010001, the new code is 1100 1111 0000 0111
* <math display="inline"> \mu=X_2X_4 </math>
** <u>11</u>00 <u>11</u>11 0000 0111. Sum is 0
** 11<u>00</u> 11<u>11</u> 0000 0111. Sum is 0
** 1100 1111 <u>00</u>00 <u>01</u>11. Sum is 1
** 1100 1111 00<u>00</u> 01<u>11</u>. Sum is 0
One error detected, coefficient is 0, no change to current code.
* <math display="inline"> \mu=X_1X_4 </math>
** <u>11</u>00 1111 <u>00</u>00 0111. Sum is 0
** 11<u>00</u> 1111 00<u>00</u> 0111. Sum is 0
** 1100 <u>11</u>11 0000 <u>01</u>11. Sum is 1
** 1100 11<u>11</u> 0000 01<u>11</u>. Sum is 0
One error detected, coefficient is 0, no change to current code.
* <math display="inline"> \mu=X_2X_3 </math>
** <u>1</u>1<u>0</u>0 <u>1</u>1<u>1</u>1 0000 0111. Sum is 1
** <u>1</u>0<u>0</u> 1<u>1</u>1<u>1</u> 0000 0111. Sum is 1
** 1100 1111 <u>0</u>0<u>0</u>0 <u>0</u>1<u>1</u>1. Sum is 1
** 1100 1111 0<u>0</u>0<u>0</u> 0<u>1</u>1<u>1</u>. Sum is 0
One error detected, coefficient is 1, valuation of <math display="inline"> \mu </math> is 0000 0011 0000 0011, current code is now 1100 1100 0000 0100.
* <math display="inline"> \mu=X_1X_3 </math>
** <u>1</u>1<u>0</u>0 1100 <u>0</u>0<u>0</u>0 0100. Sum is 1
** 1<u>1</u>0<u>0</u> 1100 0<u>0</u>0<u>0</u> 0100. Sum is 1
** 1100 <u>1</u>1<u>0</u>0 0000 <u>0</u>1<u>0</u>0. Sum is 1
** 1100 1<u>1</u>0<u>0</u> 0000 0<u>1</u>0<u>0</u>. Sum is 0
One error detected, coefficient is 1, valuation of <math display="inline"> \mu </math> is 0000 0000 0011 0011, current code is now 1100 1100 0011 0111.
* <math display="inline"> \mu=X_1X_2</math>
** <u>1</u>100 <u>1</u>100 <u>0</u>011 <u>0</u>111. Sum is 0
** 1<u>1</u>00 1<u>1</u>00 0<u>0</u>11 0<u>1</u>11. Sum is 1
** 11<u>0</u>0 11<u>0</u>0 00<u>1</u>1 01<u>1</u>1. Sum is 0
** 110<u>0</u> 110<u>0</u> 001<u>1</u> 011<u>1</u>. Sum is 0
One error detected, coefficient is 0, no change to current code.
We know now all coefficient of degree 2 for the polynomial, we can start mononials of degree 1. Notice that for each next degree, there are twice as much sums, and each sums is half smaller.
* <math display="inline"> \mu=X_4 </math>
** <u>11</u>00 1100 0011 0111. Sum is 0
** 11<u>00</u> 1100 0011 0111. Sum is 0
** 1100 <u>11</u>00 0011 0111. Sum is 0
** 1100 11<u>00</u> 0011 0111. Sum is 0
** 1100 1100 <u>00</u>11 0111. Sum is 0
** 1100 1100 00<u>11</u> 0111. Sum is 0
** 1100 1100 0011 <u>01</u>11. Sum is 0
** 1100 1100 0011 01<u>11</u>. Sum is 1
One error detected, coefficient is 0, no change to current code.
* <math display="inline"> \mu=X_3 </math>
** <u>1</u>1<u>0</u>0 1100 0011 0111. Sum is 1
** 1<u>1</u>0<u>0</u> 1100 0011 0111. Sum is 1
** 1100 <u>1</u>1<u>0</u>0 0011 0111. Sum is 1
** 1100 1<u>1</u>0<u>0</u> 0011 0111. Sum is 1
** 1100 1100 <u>0</u>0<u>1</u>1 0111. Sum is 1
** 1100 1100 0<u>0</u>1<u>1</u> 0111. Sum is 1
** 1100 1100 0011 <u>0</u>1<u>1</u>1. Sum is 1
** 1100 1100 0011 0<u>1</u>1<u>1</u>. Sum is 0
One error detected, coefficient is 1, valuation of <math display="inline"> \mu </math> is 0011 0011 0011 0011, current code is now 1111 1111 0000 0100.
Then we'll find 0 for <math display="inline"> \mu=X_2 </math>, 1 for <math display="inline"> \mu=X_1 </math> and the current code become 1111 1111 1111 1011.
For the degree 0, we have 16 sums of only 1 bit. The minority is still of size 1, and we found <math display="inline"> p_x=1+X_1+X_3+X_1X3+X_2X_3+X_3X_4</math> and the corresponding initial word 1 1010 010101
=== Generalization to larger alphabets via low-degree polynomials ===
| |||