1
$\begingroup$

In my study of BCH codes I've come across the following equation (the "key equation"):

$$ \Omega(x) \equiv \Lambda(x)S(x) \mod x^{n-k} \tag{1} $$

Where the two terms on the right are defined by:

$$ \Lambda(x) = \prod_{k=1}^{\nu}(1-X_k x) \\ S(x) = \sum_{j=0}^{n-k-1} \left( x^j \sum_{k=1}^{\nu} Y_k X_k^{c+j} \right) $$

(And $2\nu<n-k$.) In most of the papers I've read, it is stated with no explanation that $\Omega(x)$ is therefore equal to:

$$ \Omega(x) = \sum_{i=1}^{\nu}\left( X_i^c Y_i \prod_{\substack{k=1 \\ k\ne i}}^{\nu}(1-X_k x)\right) \tag{2} $$

(Or vice-versa, $(2)$ is treated as the definition, and it is then stated that $(1)$ must be true.) The $X_k$, and $Y_k$, and $x$ are members of a finite field, if it makes a difference.

My question is how can we show this to be true?

So far my best try has been to try factoring the product out of the summation on the left, and changing the order of the summations on the right:

$$ \begin{align} \sum_{i=1}^{\nu}\left( X_i^c Y_i \prod_{\substack{k=1 \\ k\ne i}}^{\nu}(1-X_k x)\right) &\equiv \left[\prod_{k=1}^{\nu}(1-X_k x)\right]\left[ \sum_{j=0}^{n-k-1} \left( x^j \sum_{k=1}^{\nu} Y_k X_k^{c+j} \right)\right] \\ \left[\prod_{k=1}^{\nu}(1-X_k x)\right]\left[\sum_{k=1}^{\nu} \frac{Y_k X_k^c}{1-X_k x} \right] &\equiv \left[\prod_{k=1}^{\nu}(1-X_k x)\right]\left[ \sum_{k=1}^{\nu} Y_k X_k^c\left(\sum_{j=0}^{n-k-1} (X_k x)^j \right)\right] \end{align} $$

(Remember this is taken $\text{mod}~x^{n-k}$.)

This looks promising, since the series expansion of $(1-x)^{-1}$ is $\sum_{i=0}^\infty x^i$. Intuitively I feel like I should be able to replace $(1-X_k x)^{-1}$ with an infinite sum, then somehow truncate that sum due to the $\text{mod}~x^{n-k}$. I'm stuck on three points:

  1. Can I justify introducing a division? I know it has to cancel with one of the product terms, but it makes me uneasy. If I use the series expansion I get an infinite number of terms in the polynomial, how can this be equal to the original expression which clearly has a finite degree?
  2. The sum is getting "mixed" with the product in a polynomial multiplication, so the terms in this sum are going to get spread out over different powers of $x$; how can I know where to truncate the series?
  3. Usually if I truncate a series expansion, I get an approximation to the original function. Why doesn't it introduce error in this case?
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.