We will use the Welch-Berlekamp algorithm to decode GRS codes. Remember that this algorithm solves a linear system to determine polynomials \(E(x), Q(x)\) such that \(y_i E(\alpha_i)=Q(\alpha_i)\) for each \(1\leq i \leq n\text{,}\) then checks if the polynomial \(P(x)=Q(x)/E(x)\) is close enough to the received message \(\by\text{.}\)
Let’s practice using the algorithm for GRS decoding. For the following problem, we will work with the \([8,4,5]_{13}\) GRS code over \(\F_{13}\) with code locators \(\balpha=(1,4,3,12,9,10,5,8)\) and column multipliers \(\bv=(12,11,2,1,2,11,11,2)\text{.}\) This code has canonical parity check matrix given by
Suppose the vector \(\by=(0,0,0,0,0,0,3,5) \) is received. Step through the Berlekamp-Welch algorithm to find an error vector \(\be\) and decoded codeword \(\bc\text{.}\) You should be able to determine these answers without doing any work at this point in the semester - use this example to solidify your understanding of the process.
