数理解析研究所講究録 1420 巻 2005 年 193-205

193

FAST PARALLEL DECODING ON SYSTOLIC ARRAY ARCHITECTURE
FOR CODES ON A CLASS OF ALGEBRAIC CURVES
松井

阪田

一

栗原

省二郎

SHOJIRO SAKATA

HAJIME MATSUI

正純

MASAZUMI KURIHARA

ABSTRACT. We construct a two-dimensional systolic array implementing the Berlekamp-MasseySakata algorithm to provide error-locator polynomials for codes on selected algebraic curves.
This array is constructed by introducing some new polynomials in order to increase the parallelism of the algorithm. The introduced polynomials are used in the majority logic schemeby Sakata et al. to correct errors uP to the designed minimum distance without affecting its
the systolichigh-speed. The arrangement of the nearest local connection of processing units
array is obtained for the general case. Furtherm ore, shortened systolic arrays that reduce thecircuit scale and have the sam function are constructed with only a slight modification of theconnections and controls; this enables the adjustment of the circuit scale for different types ofsystems.
$\ln$$\mathrm{e}$X. PRELIMINARIES

be the set of non-negative integers. In this paper, we consider a one-point algebraiccurve over a finite field $K:=$ F9. For positive integers andgeometric code on Miura’s
curve is defined by the polynomial equation, asuch that $a<b$ andLet$\mathbb{Z}0$$C_{a}^{b}$$\mathrm{g}\mathrm{c}\mathrm{d}(a, b)=1$

(1)

$b$

$a$

$\mathcal{X}$$C_{a}^{b}$$D(x, y):=y^{a}+ex^{b}+ \sum_{(n_{1},n_{2})\in \mathbb{Z}_{0}^{2},n_{1}a+n_{-}b<ab},\chi_{(n_{1},n_{\sim^{7}})}x^{n_{1}}y^{n_{2}}=0$,$e\neq 0$

over $K$ . It is known [9] that is always absolutely irreducible and has no singular point except
curve although. For simplicity, we consider a non-singular
at a single infinite point
given by
A
is
of
genus
Then,
the
[9].
it is possible to argue singular cases similarly
consists of all the$(0 -1)(\mathrm{b}-1)/2$ ; moreover, the residue class ring.
algebraic functions having no poles except at; we denote the pole order of $F\in$except$nK$
points-rational
of
set
be
a
Let
, the $K$ -linear subspace $L(mF_{\infty}):=\{F\in K[\mathcal{X}]|o(F)$as $o(F)$ . For
athas dimension $m-g+1$ , provided $m>2g$ $-2$ by Riemann-Roch Theorem. In
is defined as $C(m):=$this paper, we assume that $m>2g-2$ for simplicity. Our code$\{(c_{j})\in K^{n}|\sum_{j=1}^{r\iota}c_{j}.F(P_{j})=0$ , $F\in L(mP_{\infty})\}$ .
corresponding
Given a received word $(rj)=(c.j)+(ej)$ , where $ej\neq 0$ only for$I(\mathcal{E}):=\{F\in$ideal, we want to find a Grobner basis of the error-locatorto$=0$ ,. Then, the set of common zeros of all the elements in the Grobnerare obtained by O’Sullivan’s formula in [10].
basis agrees with , and the error values,
In this paper, we do not use any special fonts to represent vectors. For any element
denote the first and second components of vector . Let
and.
$K[X]$ is uniquely expressed as $F(x,y)$. Then, an elementfor, whereby ; furthermore, we define $o(n):=o(z^{n})=n_{1}a+n_{2}b$ for
We denote$o(F)=\max\{o(n)|F_{n}\neq0\}$ if, and we remember thatandis defined on both$\mathcal{X}$$C_{a}^{b}$$P_{\infty}$

$g$

$g$

$=$

$\mathrm{K}[\mathrm{X}]:=\mathrm{K}[\mathrm{X}]y]/(D(x, y))$$P_{\infty}$$P_{\infty}$$\{P_{j}\}_{1\leq j\leq n}$$\leq$$m\in \mathbb{Z}0$$P_{\infty}$$\mathrm{K}[\mathrm{X}]$$m\}\mathrm{U}\{0\}$$\mathrm{C}(m)$$j\in\{\prime j_{1}, \cdots 2 Jt\}$$\mathcal{E}=\{P_{j_{\gamma}}\}_{1\leq\gamma\leq t}$$P_{j_{\gamma}}\in \mathcal{E}\}$$K[\mathcal{X}]|F(P_{j_{\gamma}})$$\{e_{j_{\gamma}}\}_{1\leq\gamma\leq t}$$\mathcal{E}$$n\in \mathbb{Z}_{0}^{2}$$n$$\Phi(A)$$:=\{n\in \mathbb{Z}_{0}^{2}|n_{2}<A\}$$n_{2}$$n_{1}$$= \sum_{n\in\Phi(a)}F_{n}x^{n_{1}}y^{n_{2}}$$\mathrm{c}\mathrm{f}$$A\in \mathbb{Z}0$$n\in \mathbb{Z}_{0}^{2}$$x^{n_{1}}y^{n_{2}}$$z^{n}$$\mathbb{Z}_{0}^{2}$$\mathrm{o}(-)$$K[\mathcal{X}]$.
, we denote $\Phi(A, A’):=\{n\in\Phi(A)|o(n)\leq A’\}$ , where Figure shows an example$F= \sum_{n\in\Phi(a)}F_{n}z^{n}\in K[\mathcal{X}]$

For

$A$

,

$A’\in \mathbb{Z}_{0}$of $\Phi(2a-1, A’)$ for $A’=31$ and $(a, b)$ $=(4, 5)$ . From a given received word (rj), we can calculaterjz (ej), where
for $l\in\Phi(2a-1, m)$ by
the syndrome$\{u_{l}\}$$u_{l}= \sum_{j=1}^{n}$$u_{l}= \sum^{t}\gamma=1ej_{\gamma}z^{l}(P_{j_{\gamma}})$194

with $n\in\Phi(2a-1, m)\backslash \Phi(a, m)$ , we may decideaccording to the definition of $C(m)$ . For
induced by the curve defining
syndromes by the linear dependency among the elements ofwith $o(n)=o(l)$ ,equation (1). More precisely, if $n\in\Phi(2a-1, m)\backslash \Phi(am)\rangle$ andwe see that $n’:=n-(0, a)$ satisfies $n’\in\Phi$ ( $a-$ , $m$ –ab) and $l=(b, 0)+n’$ ; we then have$\{u_{n}\}$$K[\mathcal{X}]$$\mathit{1}\in\Phi(a, m)$$1$$u_{n}+eu_{l}+ \sum_{r\in\Phi(a,ab-1)}\chi_{r}u_{\tau+n’}=0$.

, we havewith$o(n)\neqo(n’)$(non-disjoint union). Furthermore, it should be noted that$:=\{n\in\Phi^{(i)}(a)|o(n)\leq A’\}\dot,$. Similarly, for
if and only if $n\neq n’$ for ,$\Phi^{(0)}(a)=\Phi(a)$and $\Phi^{(0)}(a, A’)=\Phi(a, A’)$ .
. Note that
we have$(a, A’)$ for $A’=31$ and $(a, b)$ $=(4,5)$ .
Figure shows an example of,,
The standard partial order on
is defined as follows: for $n=$$o(l^{(i)})=o(l)$$n\leq n’$ if and only if$l\in\Phi(a,A’)$. Let 7forbeandif there exists such an
for and . Then,is uniquely determined for each and if itexists. Note that $l^{(0)}=l$ from its definition.
by $o(\deg(F))$ $=o(F)$ , and let $s:=\deg(F)$ .
We define degree $\deg(F)\in\mathrm{a})$ of$\Phi(a,s)$$\Phi(a,o(s))$
on,From nowifis abbreviated as. Defining
$dFi$
$dFl$
$:=0$
, and
otherwise, we callat l\in $(a). Let
discrepancy ofbe the set of bivariate polynom ials whose discrepancies are zero at every $l\in\Phi(a, A’)$ ,and let $V(u, -1):=K[X]$ . In order to obtain the Grobner basis [1] of, we compute the setof minimal elements in Vr
in the meaning ofconcerning for a sufficiently large. It is shown that $B=2t+4g-2+a$ is sufficient for correcting errors from the facts
that
if $\sum_{n\in\Phi(a,s)}F_{n}u_{n+l}=0$ for all l\in $(a) with
) $\leq t+2g-$ ([12], proof of
Lemma 2) and that the pole orders of the minimal elements inare less than or equal to$t+2g-1+a$ ([3], proof of Lemma 5). From now on, we set $B:=2t+4g-2+a$ .
If we design a code that can correct up to errors, the minimum distanceof the code
must be greater than or equal to $2t+1$ . It is well-known that the Goppa designed distanceof, which is the lower bound of
and agrees with the Feng-Rao designed distance
if $m\geq 4g-$ , is equal to $m-2g+2$ . Thus, we can set $m=2t+2g-1$ and obtain$V(u, m)$ by using. Therefore, to obtain, $2g-1+a$ syndromes offor$2t+2g-1<o(l)\leq 2t+4g-2+a$ are required. These are called unknown syndromes.

For$0\leq \mathrm{i}\leq a-1$$\Phi^{(\mathrm{z})}(a):=(\mathrm{O}, \mathrm{i})+\Phi(a)=\{(n_{1}, n_{2})\in \mathbb{Z}_{0}^{2}|\mathrm{i}\leq n_{2}\leq \mathrm{i}+a -1\}$$\Phi(2a-1)=\bigcup_{i=0}^{a-1}\Phi^{(i)}(a)$$\Phi^{(\iota)}(a, A’)$$n’\in\Phi^{\langle\iota)}(a)$$n$$\Phi(2a-1, A’)=\bigcup_{i=0}^{a-1}\Phi^{(\mathrm{i}\}}(a, A’)$$\Phi^{(i)}$$\leq$$n_{1}\leq n_{1}’$$l^{(i)}$$(n_{1}, n_{2})$$\mathbb{Z}_{0}^{2}$$l$$n’=(n_{1}’, n_{2}’)\in \mathbb{Z}_{0}^{2}$$(i)\in\Phi^{(\mathrm{i})}(a, A’)$$n_{2}\leq n_{2}’$$l^{(\iota)}$

$i$

$l$

$\dot{q}$$F\in K[\mathcal{X}]$$dFi:= \sum_{n\in\Phi(a,\mathrm{s})}F_{n}u_{n+\mathrm{t}^{(s_{2}})_{-\mathrm{S}}}$$s\leq l^{\langle s_{2})}$$F\in \mathrm{K}[\mathrm{X}]$$\mathrm{f}^{\Gamma}(u, A’)$

$I(\mathcal{E})$$(\mathrm{u}, B)$$\deg(\cdot\rangle$$\leq$$B\in \mathbb{Z}0$$t$$F\in I(\mathcal{E})$$1$$0\{\mathrm{n}$$I(\mathcal{E})$$d_{\min}$$t$$d_{\mathrm{G}}$$d_{\min}$$\mathrm{C}(m)$$d_{\mathrm{F}\mathrm{R}}$$2$$\{u_{l}\}_{l\in\Phi(a,m)}$

2. BMS ALGORITHM$I(\mathcal{E})$$\backslash \gamma \mathrm{I}\mathrm{A}\mathrm{K}\mathrm{A}\mathrm{M}\mathrm{I}\mathrm{Y}\mathrm{A}-\mathrm{M}\mathrm{I}\mathrm{U}\mathrm{R}\mathrm{A}$$\{\iota’\iota\}_{l\in\Phi(a)}$FOR CODES ON$C_{a}^{b}$

Curves

Before stating-Sakata (BMS) algorithm, we introduce certain important
quantities such as for $0\leq \mathrm{i}\leq a-1$ to the updating of BMS algorithm and the constructionof systolic array in this paper. By the assumption, we have an integer
suchthat $0<b^{-1}\leq a$ 1,. For $0\leq N\leq B$ , we define a unique integer in$\{0, 1, \cdots, a-1\}$ by, which depends on not only but also $N$ ; however,$N$ is not clearly
indicated. If there exists
with $N=o(l^{(i)})$ , then(mod ). Note thatsince
, and that, if
exists, thenalso exists
and we have
since
by
.
$\mathrm{B}\mathrm{e}\mathrm{r}\mathrm{l}\mathrm{e}\mathrm{k}\mathrm{a}\mathrm{m}\mathrm{p}-\mathrm{M}\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{e}\mathrm{y}$$\overline{l}$$b^{-1}$$\mathrm{g}\mathrm{c}\mathrm{d}(a, b)=1$$bb^{-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d} a)$-$\overline{l}$$\overline{\iota}\equiv b^{-1}N-\mathrm{i}(\mathrm{m}\mathrm{o}\mathrm{d} a)$$\mathrm{i}$$\mathit{1}^{(i)}=(l_{1}^{(i)}, l_{2}^{(i)})\in\Phi^{(i)}(a, B)$$\overline{\iota}=l_{2}^{(i)}-\mathrm{a}$$l_{2}^{(i)}\equiv b^{-1}N$$l^{(i)}=l^{(\overline{\iota})}$$a$$l_{2}^{(i)}=l_{2}^{(\overline{l})}$$\overline{\overline{\iota}}=i$$0\leq l_{2}^{(i)}-\overline{\iota}=\mathrm{i}\leq a-1$$l^{(i)}$$l^{(\overline{\mathrm{z}})}$

1S5
Next, we explain the quantities

and,are initialized as 0,. At the first stage of BMS algorithm, $N$ , , andfor
be $N=o(l)=o(l^{(i)})$ if such andand -1, , respectively. Let $l\in\Phi(a, B)$ and. Jn $N$ -updating of BMS algorithm,
forexist. Then, we define
as follows:andare updated toand$s_{\Lambda^{\Gamma}}^{(i)}=$$s_{N}^{(i)}$$0\leq \mathrm{i}\leq a-1$$($$\mathrm{i})$$d_{N}^{(i)}:=d(F_{N}^{(i)})_{l}$$s_{N+1}^{(i)}$$c_{N}^{(\overline{\mathrm{z}})}$$s_{N+1}^{(i)}$$c_{N+1}^{(\overline{\iota})}$iforotherwise,$d_{N}^{(i)}=0$$:=\{$$l^{(i)}-c_{N}^{(\overline{\iota})}$iforotherwise.
$d_{N}^{(i)}=0$$c_{N}^{(\overline{l})}$(3)$c_{N+1}^{(\overline{\iota})}$$:=\{$$l^{(i)}-s_{\mathrm{A}^{\gamma}}^{(i)}$$l^{(i)}$exists, then$s_{N}^{(\mathrm{a})}\geq l^{(i)}-c_{N}^{\acute{(}\overline{\iota})}$$l$$F_{N}^{(\mathrm{i})}\in K[\mathcal{X}]$$s_{N}^{(i)}$

(2)

If

$(0, \mathrm{i})$$\mathrm{c}_{N}^{(\dot{\iota})}$$l^{(\mathrm{i})}\in\Phi^{(i)}(a, B)$$l^{(i)}$$s_{N}^{(\mathrm{i})}$$c_{N}^{(\mathrm{i})}=(c_{N_{1}^{\prec}}^{(i)},’ \mathrm{i})\in\Phi(a)\cup\{(-1, \mathrm{i})\}$$(s_{N,1}^{(i)}, \mathrm{i})\in\Phi(0\downarrow)$is equivalent to

we define the preserved condition (P) of(P)$s_{N}^{(i)}$,$s_{N}^{(i)}\geq l^{(i)}-c_{N}^{(\overline{\iota})}$,$s_{N,1}^{(\iota)}\geq l_{1}^{(i)}-c_{N1}^{(\overline{\iota})}$and$\Leftrightarrow d_{N}^{(\mathrm{i})}=0$$s_{N}^{(i)}\geq l^{(i)}-c_{N}^{(\overline{\iota})}$or$c_{N}^{(\overline{\iota})}$since$\mathrm{i}=l_{2}^{(i)}-\overline{\iota}$. For simplicity,

as follows:$s_{N}^{(i)}\geq l^{(i\rangle}-c_{N}^{(\overline{\iota})}$

.

.
and
Then the above condition “otherwise” indicates that
In $[7][8]$ , the BMS algorithm starts from $(0, \mathrm{O})\in\Phi(a, B))$ and is performed along with eachas ordering. For later use, we describe here theelement of $\Phi(a, B)$ in the total orderalgorithm performed not along with the pole order in the pole order sequence $(\Phi(a, B))$ but
along with $0\leq N\leq B$ including gap-numbers.
$d_{N}^{(\mathrm{z})}\neq 0$$s_{N_{\backslash }1}^{(i)}<l_{1}^{(\mathrm{i})}-c_{N,1}^{(\overline{\iota})}$$o(\cdot)$$\mathit{0}$BMS Algorithm:
for l $\in\Phi(2a-1_{\dot{J}}m)$ .
Input:
for all $0\leq \mathrm{i}\leq a-1$ .
andOutput:In each step, the indicated procedures are carried out for all $0\leq \mathrm{i}\leq a-1$ .
, $G_{N}^{(i)}:=0$ .
,Step 0: (initializing) $N:=0$ ,,exists andStep 1: (computing discrepancy) If$\{u_{l}\}$$F_{m+1}^{(i)}$$G_{m+1}^{(i)}$$s_{N}^{(\iota)}:=(0, \mathrm{i})c_{N}^{(\mathrm{a})}:=(-1, \mathrm{i})$.
otherwise,
Step 2: ( $N$ -updating)$F_{N}^{(i)}:=y^{\mathrm{i}}$$l^{(\mathrm{z})}$$s_{N}^{(i)}\leq l^{(i)}$$c_{N+1}^{(\overline{\iota})}$as described above,$d_{N}^{(i)}:= \sum(j\rangle F_{N,n}^{(i)}u_{n+l^{(r)}}(i)\backslash n\in\Phi(a_{7}s_{\mathrm{J}})\backslash ’-\mathrm{S}_{\mathrm{A}},\cdot$$d_{N}^{(\iota)}:=0$(4)$s_{N+1}^{(i)}$and$F_{\Lambda^{\gamma}+1}^{(i)}:=z^{s_{N+1}^{(\mathrm{i})}-s_{N}^{(\mathrm{i})}}F_{N}^{(i)}-d_{N}^{(\iota)}z^{s_{N+1}^{(\mathrm{i})}-l^{\{j)}+\mathrm{c}_{N}^{(_{1)}^{-}}}G_{N}^{(\overline{\iota})}$$G_{N}^{(\overline{x})}$(5)$G_{N+1}^{(\overline{\iota})}:=\{$$(d_{N}^{(i)})^{-1}F_{N}^{(\iota)}$,

if (P),
otherwise.

Step 3: If $N<m$ , change $N$ to $N+1$ and go to Step 1; otherwise, stop algorithm.

$\square$.
does not exist, we define
In (4), if
along with pole orders for the
performediswhich
The present form of the BM algorithm,
reduced version of Sakata ’thecurves, by Kamiya-Miura [2] issyndromes from codes on
algorithm [11]. As previously stated, the unknown syndromes must be determined to perform
Step 1-2 for $m$ $<N\leq B$ ; the BMS algorithm including the determination of unknown syndromesis described in a later section. From now on, $N$ is called a processor number, which corresponds
systolic array described later in section 4. The
to processor’s number in theis a system of minimal polynomials
following theorem confirms that
$F_{N+1}^{(i)}.=z^{s_{J\backslash ^{7}+1}^{(i)}-s_{N}^{(i)}}F_{\Lambda^{\gamma}}^{(i)}$$l^{(i)}$$\mathrm{S}$$\mathrm{s}$$C_{a}^{b}$$\mathrm{t}\mathrm{w}\mathrm{o}- \mathrm{d}\mathrm{i}_{1}\mathrm{n}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}1$$\{F_{N}^{(i)}\}_{0\leq \mathrm{z}\leq a-1}$

19G

Theorem 1. We have $F_{N}^{(i)}\in V(u,$N–1),$\deg(F_{N}^{(i)})$$=s_{N}^{(i)}$, and$F^{(i)}N,s_{\Lambda}^{(\mathrm{z})},=1j$moreover,trun $\{\zeta_{N,1}^{(i)}|F\in V(u, N-1)$ , $\deg(F)=(\zeta_{N,1}^{(i)},$ $\mathrm{i})\}=s_{N,1}^{(i)}$ ,

(6)
(7)

$s_{N,1}^{(0)}\geq s_{N,1}^{(1)}\geq\cdots\geq s_{N,1}^{(a-1)}$.

$\square$is alsoThe proof of Theorem 1 is referred to [2] [11] or Appendix , in which
proved for all $N$ , .
associate $F(z)$ with a reciprocal
For later use, we describe a variant of the above algorithm.
$s=\deg(F)$$\overline{F}(Z):=\sum_{n\in\Phi(a,s)}F_{n}Z^{o(s)-o(n\}}$. Note that the degree, whereunivariate polynomial. For example, $Z^{2}+1$
of $F$ must be presented together with to reconstruct $F(z)$ fromcorresponds to $1+x$ if $(a, b)=(2,3)$ and $s=(1,0)$ , and also corresponds to $x+x^{2}$ if $s=(2,0)$ .
Setting$s_{N,1}^{\langle i)}=c_{N,1}^{(i)}+1$$\mathrm{A}$$\mathrm{i}$$\mathrm{W}\mathrm{e}$$\overline{F}(Z)$$\overline{F}$and$\overline{F}_{N}^{(\iota)}(Z):=\overline{F_{N}^{(i)}}(Z)$$\overline{G}_{\mathit{1}\backslash }^{(\overline{\iota})},(Z):=Z^{N-M}\overline{G_{N}^{(\overline{\iota})}}(Z)$,occurs, or $M:=0$
where $M$ is the processor number at which the updating; note thatifholds. Thus, we obtain the univariate version of,, and replacing (4) (5) to the followings:
the BMS algorithm by initializing$G_{N}^{(\overline{\iota})}:=(d_{\mathit{1}1P}^{(J))})^{-1}\overline{F}_{\mathrm{A}4}^{(j)}$$\overline{G}_{N}^{(\overline{\mathrm{z}})}=Z^{N-J\mathit{4}}(d_{M}^{(j)})^{-1}\overline{F}_{fiI}^{(j)}$$G_{N}^{(\overline{x})}=0$$\overline{F}_{0}^{(\mathrm{i})}.--1$$\overline{G}_{0}^{(i)}.--0$(8)$\overline{F}_{N+1}^{(i)}.--\overline{F}_{N}^{(i)}-d_{N}^{(i)}\overline{G}_{N}^{(\overline{l})}$(9)$\overline{G}_{N+1}^{(\overline{\iota})}:=\{$,

if (P),
otherwise.

$Z\overline{G}_{N}^{(\overline{l})}$$Z(d_{N}^{(\mathrm{i})})^{-1}\overline{F}_{N}^{(i)}$This form in which the algorithm updates the reciprocal univariate polynomials corresponds
to Kotter’s algorithm [3]. Furthermore, we apply this mechanism for calculating “candidate
value” of the unknown syndromes in later section.

3. DETERMINATION OF UNKNOWN SYN DROMES
The syndromes obtained with a received word areapply for $n\in\Phi(2a - 1, m)$ , andtherefore, the $N$ -updating for $N>m$ needs the determination of unknown syndrome at Step
1 in the above algorithm to continue the loop until . Through the restriction of curves andreduction of computation, an effective parallel algorithm can be constructed.
From now on, we impose the following restriction of algebraic curves.
$\{u_{n}\}$$B$

Assumption. In the defining equation) $=0$ , $D(z).–y^{a}-ex^{b}- \sum_{n\in\Phi(a,ab-1)}\chi_{n}z^{n}$ of
the curve
let $m_{D}:= \max$ { $o(n)|n\in\Phi(a$ , ab 1),}, Then we only adopt the curve$m_{D}\leqb$$e=1$
satisfying
andin the defining equation. This brings about the defining equation$\mathrm{D}\{\mathrm{z}$$\mathcal{X}_{7}$-$\chi_{n}\neq 0$$D(z)$ $=y^{a}-x^{b}- \sum_{n\in\Phi(1,b)}\chi_{n}z^{n}$ .

For example, the condition is satisfied for the elliptic curves having a defining equation of theform $y^{2}+a_{2}y=a_{5}x^{3}+a_{1}x+a_{0}$ since $(a, b)=(2, 3)$ in this case. The Hermitian curves areanother example. Let be the power of a prime number, then a Hermitian curve is defined by
the equation $y^{r}+y=x^{r+1}$ over; this curve has $r^{3}+1K$-rational points including asingle infinite point, which attain the Hasse-Weil bound.
This restriction leads to a useful property of linear dependency among
and consequently
the syndromes. As previously stated, if $n\in\#(2\mathrm{a}-1, B)\backslash \Phi(a, B)$ andwith$o(n)=o(l)$ , then $n’:=n-(0, a)$ satisfies $n’\in\Phi$ ( $a-1$ , B–ab) and $l=(b, 0)+n’$ . By theabove assumption, we have $u_{n}= \sum_{r\in\Phi(1,b)}\chi_{r}u_{r+n’}+u_{l}$ , where the sum is computed at Step 0$r$$K=\mathrm{F}_{r^{2}}$$q+1+2\mathrm{g}\mathrm{y}/\mathrm{q}$$\{z^{n}\}$$\{u_{n}\}$$\mathit{1}\in\Phi(a, B)$

197(initializing) without the unknown syndromes in the algorithm since $r+7?’\in\Phi(a_{\backslash }m)$ . Therefore,
can be represented as $u_{n}=\wp_{n}+u_{l}$ . where
for all $n\in\#(2\mathrm{a}-1, B)$ ,$u_{n}$$\wp_{n}:=\{$

If
syndro1ne as$l^{(i)}\in\Phi^{(\mathrm{i})}$$(a. B)$if $n=l\in\Phi(20-1, B)\cap\Phi(a_{\dot{J}}B)$ .
otherwise.

$\sum_{r\in\Phi(1b)}.\chi_{r}u_{r+n’}\mathrm{t}1$with$o(l^{(\mathrm{i})})=N$

exists and$s_{N}^{(i)}\leq l^{(i)}.$,$b_{N}^{(i)}:= \sum F_{\Lambda^{7},n}^{(i\rangle}\tau\iota_{n+l\langle \mathrm{z})}n\in\Phi(a,s_{\mathrm{A}^{r}}^{(\mathrm{i})})-s_{N}^{(\mathrm{i}\rangle}+\wp_{l^{\{\mathrm{i})}}$.

of unknown
we define candidate
is not an unknown
that$b_{N}^{(i)}$$[perp]\backslash ^{+}\mathrm{o}\mathrm{t}\mathrm{e}$$u_{n+l^{(\mathrm{i})}-s_{N}^{(\mathrm{i})}}$,$n\neq s_{\Lambda}^{\langle i)}$.
syndrome since $o(n+l^{(i)}-s_{\Lambda^{r}}^{(i)})\leq N-1$ . After is determined, it follows that
It is worth to notice that, in [12][13], the candidate of unknown syndrome was defined by ormttxng, which. In the following majority logic scheme, which aaggrreeeess withfrom[3], ourthatof
Kottertowhichissimilarmodification,andis quoted from [12][13] with this
into equivalence classes according not todefinition makes it possible to classify the set
relation. Our technique is, underequalityeasier
but
to
the
[13]
the linear dependency as in [12].
to realize
the restriction of curves, the combination of this modification and further
on systolic array.
parallel computation of$b_{f\backslash }^{(i)},=d_{\mathrm{A}^{r}}^{(i)}-u_{l}$$u_{l}$$(\langle\rangle)$$d_{\Lambda}^{(\iota)},-u_{l^{(\mathrm{z})}}$$b_{N}^{(\mathrm{i})}$$\wp_{l^{(\mathrm{i})}}$$\{b_{\Lambda}^{(i)},\}$$-(\mathrm{i})1_{\mathrm{A}}^{r},$$\overline{\mathrm{f}\mathrm{t}^{7}}_{J\backslash }(\overline{\iota},)$$b_{N}^{(i)}$. and letexists andfor which: Let be the set of
For each . define therelation.
equality—
thebydividingclasses
equivalenceofbe the set
Then,there is a unique.
as
number of votes$(\phi)$$s_{N}^{(i)}\leq l^{(i)}$$l^{(i)}$$b_{\mathrm{A}^{\mathrm{r}}}^{(\mathrm{a})}$$\equiv$$\{B_{\gamma}\}_{\}B_{\gamma}=\{b_{N}^{(i\rangle}\}_{\mathrm{z}\epsilon}\tau_{\tau}$$\gamma$$h_{\gamma}$$h_{\gamma}:= \sum_{i\in I_{\gamma}}\max\{0\backslash$$l_{1}^{\{i)}-\mathrm{c}_{N,1}^{(\overline{\iota})}-s_{N,1}^{(i)}\}$

hold.
and
.
largest number of votes . and for. and thus, ourfor the largest number of votes
It is shown in [13] thatfrom [13] also gives the correct unkno wn syndrome. To im plement (0)variant of candidate
is adapted as follows:
andon systolic array, the definition of$u_{l}=-b_{N}^{(\iota)}$$\mathrm{i}\in I_{\delta}$$h_{\delta}$$d_{\mathrm{A}^{\dagger}}^{(x)}=0$$h_{\delta}$$h_{\delta}> \sum_{\gamma\neq\delta}h_{\gamma}$$b_{\Lambda^{\tau}}^{(i)}$$\dagger \mathrm{t}_{\mathrm{A}^{\gamma}}^{(i)}\vee(z)$$1_{I4^{\tau}}^{\sim(i)}(\approx)$(10)$1_{N}’’(-( \mathrm{i})z):=\sum_{n\in\Phi^{(\tau)}(a.B)}1_{\backslash \eta+s_{\Lambda}^{(\mathrm{t})}-n}^{(i)}r_{J},,z^{\eta+s_{\mathrm{A}’}^{\langle l)}-n}$(11)$l^{\prime(i)}N,\eta+s_{f\iota^{v}}^{(?)}.-n$,$\mathrm{f}\mathrm{t}_{\mathrm{A}’}^{(\overline{\mathrm{z}})}\vee(z):=\sum_{n’\in\Phi^{(\mathrm{j})}(a,B)}\mathrm{f}\mathrm{f}^{\prime(_{\overline{l}})}z^{\eta+s_{\lambda \mathit{4}}^{\langle g)}-n’}N.\eta+s_{\lambda L}^{(j)}-n’$$F_{\mathrm{A}^{7}.r}^{(i\rangle}\wp_{r+n-s_{\mathrm{A}}^{(j\}}}.\cdot$$F_{f4r}^{(i)},.u_{r+n-6_{\lambda j}}(.2)+$$.=$$\sum_{r\in\Phi(as_{\mathrm{A}^{!}}^{(\iota)})}$$\sum_{r\in\Phi\langle a,s_{\mathrm{A}}^{(\mathrm{i})})}$$\circ(r+n-s_{f_{\dot{\mathrm{V}}}}^{(\iota)})>\max\{m,N-1\}$$o(r+n-s_{\backslash }^{(\iota_{7})}) \leq\max\{m.N-1\}$(12)$\sum_{r\in\Phi(a,s_{M}^{(j)})}$$\sum_{r\in\Phi(a.s_{M}^{(j)})}$$o(r+n’-s_{M}^{\langle j)})> \max\{m,N-1\}$$o(r+n’-s_{M}^{(\prime)}) \leq\max\{m.N-1\}$

wherefor all $n\in\Phi(2a-1, B)$ .
is a fixed element in $(2a--l) satisfying. Then we defineand$\eta\geq n$$\eta$$\deg(1_{N}^{r})(i):=\eta+s_{\mathrm{A}’}^{(i)}$(13)$G_{N.r}^{(\overline{\iota})}\wp_{r+n’-s_{\mathrm{A}\mathit{4}}^{(j))}}$$G_{N,r}^{\langle\overline{\mathrm{z}})}u_{r+n’-s_{\mathrm{A}f}^{(J)}}+$$l\mathrm{b}^{(\overline{\mathrm{c}})}/\vee l\mathrm{v}^{\tau},\eta+s_{M}^{(J\rangle}-n’:=$$\mathrm{Y}1^{\mathrm{v}}\prime \mathrm{e}$regard as$\deg(1\mathrm{t}_{N}^{(\overline{l})}7):=\eta+s_{\Lambda T}^{(j)}$$\overline{1^{r}}_{N}(Z)(i):=\sum_{(n\in\Phi^{(\mathrm{i})}a,B)}V^{(i)}Z^{o(n)}N,\eta+s_{N}^{(\mathrm{s})}-n$,.
$\overline{b\mathrm{f}^{\gamma}}_{N}(Z)(\overline{\iota}):=\sum_{n’\in\Phi^{(j)}\langle a,B)}1V^{\langle\acute{\mathrm{z}})}Z^{o(n’)+N-\mathrm{A}l}N.\eta+s_{M}^{(J)}-n’$with $o(n)=N>m$ , i.e.. the coefficient ofNote that, in (11), the coefficient of$Z^{o(n)}=Z^{N}$ , equals the candidateof unknown syndrome. Then we obtain the following
theorem$z^{\eta+s_{\mathrm{A}\}}^{\langle \mathrm{i})}-n}$$b_{N}^{(i)}$I S8Theorem 2. if N $\leq m$ , then we have
(14)$\overline{V}_{N+1}^{(i)}=\overline{1^{r_{N}^{(i)}}}-d_{N}^{(i)}\overline{W}_{N}^{(\mathrm{z})}$,if (P),$Z(d_{N}^{(i)})^{-1}\overline{1_{N}^{r}\prime}(i)$(15)$\overline{\mathrm{I}f^{\Gamma^{(\overline{\iota})}}}_{N+1}=\{$

otherwise.

$Z\overline{\mathrm{I}l_{N}^{(\overline{\mathrm{z}})}/’}$

If $N>m$ , then we have
(16)$\overline{V}_{N+1}^{(i)}=\overline{1^{\Gamma_{N}^{(i)}}}+u_{l}Z^{N}\overline{F}_{N}^{(i)}-d_{N}^{(\mathrm{z})}(\overline{\mathrm{P}\mathrm{f}^{r_{N}^{(\overline{l})}}}+ulZ^{N}\overline{G}_{N}^{(\overline{\iota})})\backslash$(17)$\overline{\mathrm{T}\hslash_{N+1}^{(l)}/^{\gamma}}=\{$

if (P),$Z(d_{N}^{(i)})^{-1}(\overline{1_{\Lambda}^{(i)}/^{r}},+u_{l}Z^{N}\overline{F}_{N}^{(i)})$otherwise.

$Z(\overline{\mathrm{f}\Psi}_{N}^{(l)}+u_{l}Z^{N}\overline{G}_{N}^{(\overline{\mathrm{z}})})$We postpone the proof of Theorem 2 until Appendix B.
Thus, we obtain the following version of BMS algorithm including the determination of unknown syndromes, employing the majority logic scheme [12][13], where the candidates of unintroduced above.
andknown syndromes are computed parallelly by polynomials
Form):
Parallel Version of BMS Algorithm (Complete
Input:
for l $\in\Phi(2a$ –1, m).
Output:andfor all $0\leq i\leq a-1$ .
In each step, the indicated procedures are carried out for all $0<\mathrm{i}\leq a-1$ .
,
,
,
,
,
Step 0: (initializing) $N:=0$ ,$\overline{\mathrm{f}L^{r_{N}^{(i)}}}$$\overline{\mathrm{T}_{N}^{r}\prime}(i)$$\{u_{l}\}$$F_{B+1}^{(i)}$$G_{B+1}^{(i)}$$s_{N}^{(i)}$and$\overline{\mathrm{T}^{r}}_{N}(i)$$c_{N}^{(i)}$$\overline{F}_{N}^{(\mathrm{i})}:=1$$\overline{G}_{N}^{\langle i)}:=0$$\overline{\mathrm{I}\prime V}_{N}^{(\overline{l)}}:=0$$:= \sum_{n\in\Phi^{\langle i}1(a,m)}u_{n}Z^{o(n)}+\sum_{n\in\Phi^{(i)}}(a,B),m<\circ(n)\wp_{n}Z^{o(n)}$as above.

Step 1: (determining unknown syndrome, checking discrepancy) While $0\leq N\leq m$ ,if
, $d_{N}^{(i)}:=0$ otherwise. While $N>m$ , (0) is carried out,
exists and$d_{N}^{(i)}:=$$l^{(i)}$$\overline{\mathrm{I}_{N,N}^{(i)}/^{r}}$and$s_{N}^{(i)}\leq l^{(i\}}$if$d_{N}^{(i)}:=\overline{1_{N,N}^{\gamma}\tau}(i)+u_{l}$Step 2: ( $N$ updating$l^{(i)}$$s_{N+1}^{(\mathrm{z})}$,exists and$c_{N+1}^{(\mathrm{i})}$,$s_{N}^{(i)}\leq l^{(i)}$$\overline{F}_{N+1}^{(i)}$,$\overline{G}_{N+1}^{(i_{\grave{J}}}$;$d_{N}^{(i)}:=0$

are the samotherwise.
$\mathrm{e}$as above. While $0\leq N\leq m$ ,are updated byandare updated by (14) and (15). While $m<N$ ,and(16) and (17).
Step 3: If $N<B$ , change $N$ to $N+1$ and go to Step 1; otherwise, stop algorithm.
$\overline{1_{N}^{r},}(i)$$\overline{1^{\tau}}_{N}(i)$$\overline{\mathrm{T}4^{\gamma^{(i)}}}_{N}$$\overline{\mathrm{f}\prime \mathrm{f}^{\Gamma(i)}}_{N}$$\square$

4. SYSTOLIC ARRAY FOR PARALLEL BMS ALGORITHM
In this section, we describe two-dimensional systolic array for the algorithm. The twodimensional systolic array is constructed by the following rules.
(i): it is organized by connected processors $\mathrm{P}_{N}(0\leq N\leq B)$ in a series(ii): eachcontains cells(ii): allhave input and output term inais(iv):
is connected to(v):
is connected to, where is uniquely defined by
It should be noted that, whichis equivalent to$N$implies that agrees with
%1. The cellatcalculates the right-hand sides of the
updating formulas, and transmits the resulting values,
tothrough theconnection (iv), and,,tothrough the connection (v). All calculationsof the values and the coefficients of the polynomials in the cells are synchronized at each cloc$\{\mathrm{C}_{\Lambda^{l}}^{(i)}\}_{0\leq i<a}$$a$$\mathrm{P}_{N}$$\{\mathrm{C}_{N}^{(i)}\}$$\mathrm{C}_{N}^{(\mathrm{i})}$$\mathrm{C}_{N+1}^{(i)}$$\mathrm{C}_{N}^{(i)}$$\mathrm{C}_{N+1}^{(i^{*})}$$i^{*}$$\mathrm{i}^{*}\equiv b^{-1}+\mathrm{i}(\mathrm{m}\mathrm{o}\mathrm{d} a)$$\overline{l}\equiv b^{-1}(N+1)-\mathrm{i}^{*}(\mathrm{m}\mathrm{o}\mathrm{d} a)$$\mathrm{i}^{*}\equiv b^{-1}+\mathrm{i}(\mathrm{m}\mathrm{o}\mathrm{d} a)$$-\acute{\mathfrak{g}}^{*}$$\mathrm{C}_{N}^{(i)}$$\overline{l}$$s_{N+1}^{(i)}$$c_{N+1}^{(\overline{l})}$$\overline{G}_{N+1}^{(\overline{x})}$$\overline{W}_{N+1}^{(\overline{l})}$$\mathrm{C}_{N+1}^{(i^{*})}$$\overline{F}_{N+1}^{(i)},1^{\overline{r}_{N+1}^{(i)}}$$\mathrm{C}_{N+1}^{(i)}$199
signal, and in the next section, we show the scheduling, that is, the calculations that are doneat each clock signal.
It is strongly desirable that the connection between cells satisfies local condition in thesense that only the adjoining cells are connected; this is precisely defined as follows. Let$\{(j, N)\}_{0\leq j<a,0\leq N\leq B}$ be a set of lattice points.
For each.1 $N$ , the lattice points $(0, N)$ , $(1, N)$ ,, although
in one processor, $(a-1, N)$ are regarded as the positions of cells
situated at lattice points
andis not generally situated at $(j, N)$ . Two cells incell$|j-j^{+}|\leq
1$. The systolic array is said to$(j,N)$ and $(j^{+}, N+1)$ are said to be in neighborhood ifsatisfy local condition if all the pairs of cells connected by rules (iv) and (v) are in neighborhood.
curves with
We first argue on the arrangement of cells for the decoding of codes on
,
(mod
Let
).
,
with
(mod ); we then solve the general case including
then we define$\{\mathrm{C}_{N}^{(i)}\}_{0\leq \mathrm{i}<a}$$a$$\ldots$$\mathrm{C}_{N}^{(j)}$$\mathrm{p}_{N}$$\mathrm{P}_{N+1}$$\mathrm{p}_{N}$$C_{a}^{b}$$b\equiv 1$

$a$

$a$

(18)

$b$

$b\not\equiv 1$$a- \frac{j-N}{2}$$j+N$ is even,$\frac{j+N+1}{2}$$j+N$ is odd,$a$$b\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d} a)$$\phi_{N}(j):\equiv\{$(19)$\frac{j+N}{2}$$j+N$ is even,$a- \frac{j-N+1}{2}$$j+N$ is odd,$\psi_{N}(j)\underline{\cdot=}\{$

where$\mathrm{m}\mathrm{o}\mathrm{d} a$are chosen in the range $0\leq\phi_{N}(j)$ , $\psi_{N}(j)\leq a-1$ by
holds. Then $\psi_{N}(j)\equiv N-djN(j)$ (mod ) is easily checked. If $\phi_{N}(j’ )=i$ , then$:\equiv \mathrm{i}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{c}\mathrm{a}\mathrm{t}\mathrm{e}\mathrm{s}$that$\psi_{N}(j)$$\phi_{N}(j)\dot,$$\psi_{N}(j)=\overline{\iota}$$a$(mod ).
(mod ) bysince
at position $(j, N)1$ we see that connection (iv) implies that
Situating the cellisnd connection (v) implIiIeess tthhif,is connected to. It can then be shown that the local condition is
ifconnected tosatisfied. More precisely, the following relations hold:$\overline{l}\equiv N-\mathrm{i}$$b\equiv 1$

$a$

$a$

$\mathrm{C}_{N}^{(\phi_{N}(j))}$$\mathrm{C}_{N}^{(\phi_{N}(j))}$$\phi_{N}(j)$$\mathrm{C}_{N+1}^{(\phi_{N+1}(\mathrm{i}’))}$, $j+N$ is odd$\phi_{N-1}(a-1)$$\dot{J}=a-1$$\phi_{N-1}(j+1)$$j\neq a-1$ , $j+N$ is odd$\phi_{N}(j)=\{$$j\neq 0$$\phi_{N-1}(j-1)$$j=a-1$ , $j+N$ is even$j\neq a-1$ , $j+N$ is even$\psi_{N-1}(a-1)$$\psi_{N-1}(j+1)$$\psi_{N}(j)=\{$

is even, $j+N$ is even,$j=0_{\dot{l}}N$$\phi_{N-1}(0)$(21)$\mathrm{a}\mathrm{a}\mathrm{t}\mathrm{C}_{N}^{(\phi_{N}(j))}$$\mathrm{a}\mathrm{a}$$\psi_{N}(j)=\psi N+1(J^{\tilde{\prime}\prime})$$\mathrm{C}_{N+1}^{(\phi N+1(j’))}$(20)$=\phi_{N+1}(j’)\backslash$$\psi_{N-1}(0)$$J$$\psi_{N-1}(j-1)$$=0$$j\neq 0$, $N$ is odd, $j+N$ is odd.

Thus, we can design tl arrangement of cells to satisfy the local condition in the special case, we t\^aand(mod ). In the general case, instead of$\mathrm{u}\mathrm{e}$$b\equiv 1$$\phi_{N}(j)$

$a$

(22)

$\phi_{N}(j;b):\equiv b^{-1}\phi_{N}(j)$,$\psi_{N}(j)$$\psi_{N}(’/-, b):\equiv b^{-1}\psi_{N}(\dot{J})$$\mathrm{e}$.

. Moreover, we claim that
holds since, then. By connecting the cells as described aboveand(20) and (21) are still valid for, the arrangement of cells for the local
andin place of
andwithcondition is obtained.
have notable properties. They have a period of $2a:\phi N+2a(j;b)=$(jib) andand $\psi_{N+2a}(j;b)=\psi_{N}(j;b)$ . Furthermore, they have a kind of symmetry with respect.
and $\psi_{N+a}(j\}.b)=\psi_{N}(j^{\star};b)$ with;to in the sense thatIf$\phi_{N}(j;b)=\mathrm{i}$$\overline{\iota}\equiv b^{-1}N-\mathrm{i}(\mathrm{m}\mathrm{o}\mathrm{d} a)$$\psi_{N}(j;b)=\overline{l}$$\phi_{N}(j;b)$$\phi_{N}(j;b)$$\phi_{N}$$\psi_{N}(j;b)$$\phi_{N}(j’ )$$\psi_{N}(j;b)$$\psi_{N}(j)$$\psi_{N}(j;b)$$\phi_{N}(j;b)$$j$$\phi_{N+a}(j$$b\rangle$$=\phi N(j^{\star};b)$’$j$$+_{f^{\star}}^{\rho}\cdot=a-1$

200
Table Values of$\emptyset\wedge^{1}$$(j,b)$ and$\psi_{N}(j,b)$with$b\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d} 4)$

Figure. Systolic array for codes on$C_{4^{\prime 1}}$curvescan interchange
These properties are utilized in [5] to reduce the scale of thle systolic array.
$\phi_{N}(j;b)$ and $\psi_{N}(jjb)$ in order that the resulting systolic array still satisfies the local condition.
(mod4). An example of theTable lists the values of $\phi N(j;b)$ and $\psi_{N}(j:b)$ with, whichis $y^{4}+y=x^{11}$ overbound(mod ) that attains the Hasse-Weilcurve with
$K$
the
cell
curves having many -rational points. In Figure. we show
is in Miura’s list [9] ofarrangement and their connection in the systolic array constructed as above according to theand $\psi_{N}(j:11)$ in Table, where the solid and double lines express the connection
valuesrespectively.
according to $\phi_{N}(j:11)$ andhave applied the arrangement of cells on the three-dimensional systolic array described in[14] to our two-dimensional systolic array, as in [7] [8], and extended it to the general case for .
$\mathrm{W}" \mathrm{e}$$b$$b\equiv 3$$\equiv 3$$C_{/}^{b}a$$\mathrm{F}_{2^{10}}$$a$$C_{a}^{b}$$\phi_{\Lambda’}(j\backslash \cdot 11)$$\psi_{N}(j;11)_{i}$$\backslash 1’’ \mathrm{e}$$b$5. SCHEDULINGIn this section, we describe the scheduling of data in the algorithm on the systolic array. As
a result, the circuit scale of the systolic array in this section will be reduced to almost half thewerescale with the same running time as in [5]. Although, in $[7][8]$ , gap-numbers
excluded from the processor numbers, we now include them in thle processor nunlbers $0\leq N\leq B$
in order to regularize the arrangement of cells.
) are the values(resp.
andand
We define that, for $0\leq N\leq B$ .
$\mathbb{Z}_{0}\backslash o(\Phi(a))$$g$$f_{N+1.h}^{(i\}}$in $K$ received by cell,that, for $N=0$ ,$f_{0,h}^{(i)}$,$\mathrm{C}_{\mathrm{A}+1}^{(i)}$$v_{0,h}^{(\mathrm{i})}$

.

from
. and

(resp.

$\mathrm{C}_{N}^{(i)}$$g_{0,h}^{(i)}$Next, we define the coefficients$w_{0}^{(i}$$\mathrm{C}_{\mathrm{A}^{r}+1}^{(\mathrm{i}^{*})}$

from), are the values in, )$\mathrm{C}_{\mathrm{A}}^{(\iota)}$

$K$

$h$
)

$\overline{l^{7}}_{J\backslash h}(\dot{\mathrm{z}}.)$.

$w_{\Gamma\iota^{r}+1h}^{(i)}$$g_{N+1,h}^{(\tau)}$$v_{N+1,h}^{(\iota)}$$\overline{\mathrm{f}1^{r}}_{N,h\}(\overline{\iota})\overline{F}_{\Lambda^{r},h}^{\{i)}.$,andat clock$h\in \mathbb{Z}_{0}$inputted to cell$\overline{G}_{\Lambda^{7}.h}^{\{\overline{\iota})}$in$\overline{\mathrm{f}^{\gamma}}_{\Lambda’}(i)$.

.

$\backslash 1^{\prime^{7}}\mathrm{e}$at clock$\mathrm{C}_{0}^{(i)}$$\overline{\ddagger 1_{\Lambda}^{\langle_{\overline{l}})}\vee},$also define,$\overline{F}_{\Lambda}^{(i)}$$h\in \mathbb{Z}_{0}$

. and

.

$\overline{G}_{\Lambda^{\mathrm{r}}}^{(\overline{\iota})}\backslash$respectively, by(23)$\overline{\mathrm{I}^{r_{N}^{(i)}}}=\sum_{h=N}^{B}\overline{1^{r}}_{\Lambda^{\gamma},h}Z^{h}(i)$,,$\overline{F}_{N}^{(i)}=\sum_{h=0}^{o(s_{\wedge}^{(\tau\rangle})}\overline{F}^{(i)}Z^{h}.\overline{G}_{\Gamma 4^{*}}^{(\overline{\mathrm{z}})}\Lambda’,h’=\sum_{fh=N-fl}^{r}\overline{G}_{N.h}^{(\overline{\iota})}Z^{h}o\{s_{\acute{\Lambda}f}^{(}))+_{\mathit{1}}\backslash -\Lambda I$$\overline{fi_{N}^{\langle\overline{\iota})}\prime}=\mathrm{I}^{\overline{7\mathrm{f}^{r}}_{\Lambda^{r},h}Z^{h}}’,(\overline{\iota})$.

), has been omitted since it is not necessary
Note that the coefficient offor $h<N$ ill
in the algorithm : then, it follows fromthat the lowest degree of,
equals $N$ . Then, we give the scheduling for the computation of the coefficientsin, andas follows:$-\langle i$$Z^{h}$$\mathrm{t}_{\mathrm{A}}^{f}$$Z^{h}$$\overline{1\mathrm{t}_{N}^{(\overline{\iota})}\vee}=Z^{N-\lambda \mathit{4}}(d_{M}^{(j)(j)})^{-1}\overline{1^{\mathrm{v}}}_{\lambda \mathrm{f}}$$-(i)|_{N,h}’$$\overline{\mathrm{i}4^{\gamma(\overline{x})}}_{N}$$\overline{\mathrm{f}\mathrm{t}_{N,h)}^{(\overline{\tau})}\prime\vee\vee}\overline{F}_{N,h}^{(\mathrm{i})}$(24)$\overline{G}_{N,h}^{(\overline{\iota})}$$\overline{\mathrm{T}^{\gamma}}_{N,h}=v_{N,N+h7}^{(i)}(i)\overline{\mathrm{f}L^{7}}_{\Lambda^{r},h}(\overline{\iota})=w_{N,N+h}^{(\overline{\mathrm{z}})}$.

$\overline{F}_{N,h}^{(i\}}=f_{l\backslash ^{r},2N+h}^{(i)}$.

$\overline{G}_{N,h}^{(\overline{\iota})}=g_{N.2N+h}^{(\overline{x})}$.

These imply that, for example,
is obtained at clock $N+h$ in. The validity of thisscheduling follows from the recurrence formulas (25)-(30) given below and the range of for
.
,
. and
given later.
Thus, the updating formulas (8), (9), (14), (15), (16), an
are changed to the following(25), (26), (27), (28), (29) and (30), respectively.
$\overline{V}_{N,h}^{(i)}$$\mathrm{C}_{N}^{(i)}$$h$$v_{N,h}^{(i)}$$w_{N,h}^{(\overline{l})}$$f_{N.h}^{(\mathrm{i})}$$g_{\Lambda^{\mathrm{Y}}.h}^{(\overline{\iota})}$$\mathrm{n}\mathrm{d}(17)$201
Parallel Version of BMS Algorithm (Scheduling) :for f $\in\Phi(20-1,$m).
Input:.
for allandOutput:out for all $0<\mathrm{i}\leq a-1$ .
arecarriedprocedures
indicated
the
step,
each
Jn
.
.
Step 0: (initializing) $N:=0$ ,$\{u_{l}\}$$0\leq \mathrm{i}\leq a-1$

$G_{B-\vdash 1}^{(i)}$$F_{B+1}^{(i)}$$s_{\mathrm{A}’}^{(\iota)}.=(0, \mathrm{i})$$(0\leq h\leq B)$$f_{N,0}^{(i\overline{)}}:=1_{\dot{l}}g_{N,0}^{(i)}.=0$$c_{N}^{(i)}.=(-1, \mathrm{i})$.

$w_{N,h}^{(i)}:=0$:0$v_{\Lambda h}^{(i)},$,$\cdot=\{$$h\not\in o(\Phi^{(i)}(a, B\rangle)$.

and $0\leq h\leq m$ .
$h\in o(\Phi^{(i)}(a, B))$ and $m<h\leq B$ .
$h\in o(\Phi^{\langle i)}(a, B))$$u_{n^{(\tau)}}$$\wp_{n^{(_{1})}}$

for $o(n^{(x)})=o(n)$)
with $h=o(n^{(i)})\dot,$ and we have un{i)
is in
where
with $n\in\Phi(a, B)$ .
Step 1: (determining the unknown syndrome, checking discrepancy) While $0\leq N\leq m$ ,is carried; $d_{N}^{(i)}:=0$ otherwise. While $N>m$ ,if 7(i) exists andexists andif
and is obtained. Then,out for$\Phi^{(i)}(a.

$n^{(i)}$B)$$b_{\mathrm{A}}^{(i)},=v_{N,2N}^{(i)}$$:=0\mathrm{o}\mathrm{t}$$(\langle\rangle)$$l^{(i)}$$d_{N}^{(i)}:=v_{N,2N}^{(i)}+u_{l}$$u\iota$$s_{\mathrm{A}^{7}}^{\langle i)}\leq l^{(x)}j$

herwise.

Step 2: ( -updating)$\mathrm{T}\mathrm{V}$(25)$t\mathrm{s}_{\mathrm{A}^{\mathrm{T}}+1}^{(i)}.,$$c_{\mathrm{A}^{\dagger}+1}^{(i)}$are the same as in (2).

$f_{f\backslash ^{\tau}+1,h+2}^{(i)}:=f_{N.h}^{(i)}-d_{N}^{(\mathrm{i})}g_{\mathrm{A}’.l\iota}^{(\overline{\mathrm{t}})}$.
if (P).
otherwise:$(\overline{\mathrm{r}})$(26)$g_{\Lambda^{\mathrm{v}}+1.h+3}^{(\overline{\iota}\rangle}$$g_{N,h}$$.=\{$$(d_{N}^{(i)})^{-1}f_{\mathrm{A}h}^{(i)}.$

,

while

$+u_{n}$$s_{\Lambda}^{(\iota)},\leq l^{(i)}$$d_{N}^{(i)}:=v_{h_{\backslash }^{\tau}2N}^{(i)}$$d_{N}^{(\mathrm{z})}$$=\mathrm{p}\mathrm{n}\{1$$0\leq N\leq m\backslash$

(27)

.

$q_{\lambda_{\wedge^{\tau}+1.h+1}}^{(i)}:=v_{\mathrm{A}^{r}.h}^{(\iota)}-d_{N}^{(i)}w_{\mathrm{A}h}^{(\overline{\tau})}"$

if (2).
otherwise :$\langle\overline{\mathrm{z}})$(28)$?\mathit{1})_{\wedge’+1,h+2}(\overline{\iota})$$w_{N,h}$$.=\{$$(d_{N}^{(i)})^{-1}v_{N.h}^{(\mathrm{i})}$while $m<N$ .

.

(29)

$v_{N+1,h+1}^{(i)}:=v_{\mathrm{A}h}^{(i)},.+u/f_{Nh}^{(i)}-d_{N}^{(i)}(w_{\mathit{1}\mathrm{V}h}^{(\overline{\iota})}+u_{l}g_{N_{\backslash }h}^{(\overline{\mathrm{z}})})’$

if$(u_{N.h}^{(\overline{\iota})})+u_{l}g_{\mathit{1}\backslash h}^{(\overline{\iota})},.)$(30)$(\mathrm{P})_{\backslash }$$w_{\Lambda^{r}+1.h+2}^{(\overline{\iota})}:=\{$

otherwise.

$(d_{t\mathrm{v}^{7}}^{(i)})^{-1}(v_{N,h}^{(i)}+u_{f}f_{N.h}^{\{i)})$

Step 3: If $N<B$ , change $N$ to $N+1$ and go to Step 1: otherwise, stop algorithm.
,
In view of the left-hand side of (25)-(30), we see that the number of registers formust be set to one, two, two, and three, respectively. In order to completeiinnand$\square$$v_{N.h}^{(i)}$$f_{N,h}^{(i)}\dot{J}$$g_{N,h}^{(i)}$$\mathrm{C}_{N}^{(i)}$the construction of the array, the range ofThis is given from (23) as follows:

$h$

for

$v_{N,h}^{(i)}$

for

.

(31)

$2N\leq h\leq N+B$

(32)

$2N\leq h\leq 2N+o(s_{f\backslash }^{(i)},)$$w_{N,h}^{(\overline{l})}$$v_{\mathrm{A}^{\tau},h}^{(i)}$for$2N+N-M\leq h\leq 2N+N-\Lambda l$(33)$w_{N,h}^{(_{\iota}\rangle}\eta\dot,$.

$f_{N,h}^{(i)}$

and

, and

$w_{N,h}^{(\overline{l})}$$f_{N.h}^{(i)}$$g_{N.h}^{(\overline{l})}$must be indicated.

.

.

$+o(s_{l\backslash \mathrm{f}}^{(J)})$for$g_{\Lambda h}^{(\overline{l})}"$.

The validity of the scheduling follows from the observation that the values in the. which are obtained at clockandare obtained at clock except forside of$\mathrm{r}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}arrow \mathrm{h}\mathrm{a}\mathrm{n}\mathrm{d}$$(2\acute{0})-(30)$$h$$d_{f4}^{(i)}.$

$ul$

202
while the values in the left-hand side are obtained at clock $>h$ . Thus, the systolic
array consisting of $B+1$ processors has been constructed.
$2N\leq h$ ,APPENDIX A. Proof OF THEOREM 1
Theorem 1 is proved by the following three lemmas.

Lemma 1. Suppose that $G(z)\in V(u, M-1)$ , $G_{t}=1$ , $dG_{k}\neq 0$ , and $t\leq k$ with $t=\deg(G)$ ,$k\in\Phi^{(t_{2})}(a, B)$ , and $o(k)=M$ .
and $F_{s}=1$ with
Moreover, suppose that$s_{1}\geqk_{1}-t_{1}+1$.
and$s=\deg(F)$ . Then, it holds that at least one condition of$F(z)\in \mathrm{V}(\mathrm{u}, M)$$s_{2}\neq h_{2}^{\wedge}-t_{2}$Proof of Lemma 1. “SVe suppose that

and$F\in V$ ($u\dot,$$s_{1}\leq k_{1}-t_{1}$$\square$and $s_{2}=k_{2}-t_{2}$ . Since $G\in V(u, M-1)$

I ), we have
$f$

-I
-I

( ,I

$G_{n}u_{n+l-t}=u_{f}$for$l\in\Phi^{(t_{2})}$$F_{r}u_{r+l-s}=u_{l}$for$l\in\Phi^{(s_{2})}$ $(a, \mathbb{J}f)$

$a$

$f$

1), $t\leq l$ ,-$n\in\Phi(a,t)\backslash \{t\}$,$s\leq l$.

$r\in\Phi(a,s)\backslash \{s\}$Since $n_{2}+k_{2}-t_{2}\leq a-1+s2$ and $n+h.-t$ $\geq n+s\geq s$ for $n\in\Phi(a,t)$ , we have $n+k-t\in\Phi^{(s_{2})}(a, M)$
and $\leq n+k’$. $-t$ for $n\in\Phi(a, t))$ and moreover,$s$-$\sum_{n\in\Phi(a,t)\backslash \{t\}}G_{n}u_{n+k-t}=\sum_{n\in\Phi(a,t)\backslash \{t\}}G_{n}\{\sum_{\tau\in\Phi(a,s)\backslash \{s\}}F_{r}u_{r+\langle n+k-t)-s}\}$$\sum$$=$$n\in\Phi(a,t)\backslash \{t\}$$r\in\Phi(a,s)\backslash \{s\}$$=-$$G_{n}u_{n+(r+k-s)-t}$$\sum$$F_{r}$$F_{r}u_{r+k-s}$$\sum$,$r\in\Phi(a,s)\backslash \{s\}$where the last equality follows from $r+k-s\in\Phi^{(t)}\underline’(a, M-1)$ and $t\leq r+k.-s$ forsince $r_{2}+k_{2}-s_{2}\leq a-1+t_{2}$ and $r+k-s\geq r+t\geq t$ for r\in $(a, ), and the last sum agrees( A ). This contradicts $dG_{k}\neq 0$ . $[]$
withsince $s\underline{9}\leq k_{2}=s_{2}+t_{2}\leq s_{2}+a-1$ and$r\in\Phi(a, s)\backslash \{s\}$

$s$

$k$

$u_{k}$

Lemma 2. We have$s_{N,1}^{(i)}=c_{N,1}^{(i)}+1$$\in\Phi^{(s_{2})}$

$a\}$

$I$

.

$\square$

Proof of Lemma 2. We prove it by induction. The case of $N=0$ follows from the initializing.

, then also
for aallll 2, we prove $s_{N+1,1}^{(i)}=c_{N+1,1}^{(i)}+1$ . If there is no
Assuming. It follows from the assumption ofno , and therefore, we may assume that there is. Thus. we may assume thatthe induction that
if and onty if, then it,, andwithout loss of generality. If$l^{(i)}$$s_{N,1}^{(\mathrm{z})}=c_{N,1}^{(i)}+1$$l^{(i)}=l^{(\overline{\iota}\rangle}$$l^{(\overline{\iota})}$$s_{N,1}^{(i)}\geq l_{1}^{(i)}-c_{N.1}^{(\overline{\iota})}$$s_{N.1}^{(i)}<l_{1}^{(\mathrm{z})}-c_{N,1}^{\langle\overline{\iota})}$$d_{N}^{(i)}\neq 0$$s_{N,1}^{(\overline{\iota})}<l_{1}^{(\overline{\iota})}-c_{N,1}^{(i)}$contradicts Lemma 1 sinceThus, we obtain$s_{N,1}^{(\overline{\iota})}\geq l_{1}^{(\overline{\iota})}-\mathrm{c}_{N,1}^{(\mathrm{i})}$$d_{N}^{(\overline{\mathrm{z}})}\neq 0$$F_{N}^{(i)}\in \mathrm{V}(\mathrm{u}, N-1)$

and,$F_{N}^{(\overline{\mathrm{z}})}\in \mathrm{V}(\mathrm{u}, N)$$s_{N+1,1}^{(i)}-c_{\Lambda+1,1}^{(i)},=s_{N,1}^{(\overline{\iota})}-c_{N,1}^{(\overline{l})}$

It follows from Lemma 2 that$\max^{t}\leq\{s_{N}^{(i)}$,$d_{N}^{(\overline{\iota})}=0$,$s_{N,1}^{(\overline{\mathrm{z}})}\leq l_{1}^{(i)}-s_{N,1}^{(i)}$, and$\overline{l}=l_{2}^{(i)}-\mathrm{i}$.

$l^{(i)}-c_{\Lambda^{\gamma}}^{(\overline{\iota})} \}=(\max\{s_{N,1}^{(i)}$.

$\square$,$l_{1}^{(i)}-s_{N,1}^{(\overline{\iota})}+1\}$,$\mathrm{i}$).

Lemma 3. Let $F(z)\in \mathrm{V}(\mathrm{u}, N-1)$ ,with $s=\deg(F)$ for $l\in\Phi^{(s_{2})}(a, B)$ , and let $G(z)\in$, $t\leq k$ with $t=\deg(G)$ for. Moreover, suppose that $G\neq 0$ , $dG_{k}=1$ ,$t_{2}=l_{2}-s_{2}$ . Then,$=o(k.)<N=o(l)$ and$s$$k\in\Phi^{(t_{2}\rangle}(a, B)$$\mathrm{t}’\vee(u, M-1)$$l\mathit{1},F$$\leq l$$k_{2}$-$H(z)$ $:=z^{r-s}F-dF_{l}z^{\gamma-l+k-t}G\in V(u, N)$

and $\deg(H)$ $=r$ , where $r:=s$ if $dFi=0$ , and $r:= \max\{s, l-k+t\}=\leq(\max\{s_{1}, l_{1}-k_{1}+t_{1}\}, s_{2})$otherwise.

$\square$203
Proof of Lemma 3. Since$o(z^{r-s}F)-o(z^{r-l+k-t}G)=r_{1}a+s_{2}b-(r_{1}-l_{1}+\mathrm{h})\mathrm{a}-t_{2}b$(34)$=o(l)-o(k)>0$ ,we obtain $\deg(H)$ $=r$ . Next, since $F\in 1^{\Gamma}(u, N-1)$ and0$F_{n}u_{n+p-s}=\{$$\sum$$G\in \mathrm{V}(\mathrm{u}, M-1)$$p\in\Phi^{(s_{2})}(a, N-1)$, we have, $s\leq p$$p=l$ ,

$dF_{l}$$n\in\Phi(a,s)$$G_{n}u_{n+p-t}=\{$$\sum$

01$p\in\Phi^{(t_{2})}(a, M-1)$, $t\leq p$$p=k$ .

$n\in\Phi(a,t)$$1h^{t}\mathrm{e}$may assume$dF_{l}\neq 0$. If$p\in\Phi^{(s)}\underline’(a, N-1)$

and $r\leq p$ then we have $p-l+k$.

$\in\Phi^{(t\underline{)}}$)) $(a, \mathbb{J}I -1)$

and $t\leq p-l+k$ , and moreover,$\sum_{n\in\Phi(ar)},H_{n}u_{n+\mathrm{p}-r}=\sum_{n\in\Phi(a,s)}F_{n}u_{n+(\tau-6)+p-7}-dF_{l}\sum_{n\in\Phi(at)},G_{n}u_{n+(r-l+k-t)+p-r}$$= \sum_{r\iota\in\Phi(as)},F_{n}u_{n+p-\mathrm{s}}-dF_{l}\sum_{n\in\Phi(a,t)}G_{n}u_{n+(p-l+k)-t}$

0

$=\{$

$dF_{f}-dF_{l}\cdot$

Proof of Theorem 1, If
Thus $d_{N+1}^{(i)}=0$ and$d_{N}^{(i)}\neq 0$,$c_{N}^{(\overline{\mathrm{z}})}=k^{(j)}-s_{fl\mathrm{f}}^{(J)}$$1=0$$G_{N}^{\{\overline{\iota})}=0_{\backslash }$$\deg(F_{N_{\mathrm{T}}^{1}1}^{(i)})=s_{\Lambda+1}^{(i)}$number most recently satisfying

we haveand$p\in\Phi^{(_{\mathrm{S}9})}.(a, N-1)_{\}r\leq p$$\square$$p=l$ .

then$s_{N+\mathit{1}.1}^{(i)}:=l_{1}^{(i)}+1$

hold. Supposing that

$G_{N}^{(\overline{\iota})}:=(d_{M}^{(j)})^{-1}F_{flP}^{(j)}$$G_{N}^{(\overline{\iota})}\neq 0$

and$F_{I\mathrm{v}^{7}+1}^{(i)}$, let$\Lambda f$, $o(k^{(j)})=M$ , and.

be the processor$\overline{l}=k_{2}^{(j)}-j$, then. Thus we can prove the theorem except for (6) and (7) by using. The minimality (6) is proved by induction. (6)Lemma 3 since, we prove it for
at $N:=0$ holds trivially. Supposing that the equality is true for, thenorin (6). If
be the minimum ofLet, we havehold. Ifand, thusas in the proof of Lemma 2. Assuming, and moreover,$l^{(i)}-k^{(j)}+s_{I1I}^{(j)}.=l^{(i)}-c_{N}^{(\overline{\iota})}$$s_{N+1.1}^{(i)},,\cdot$$s_{N,1}^{(i)}$$\zeta_{N,1}^{(i)}$$s_{N,1}^{(i)}=\sigma_{N1,)}^{(i)},$$s_{N}^{(i)}\leq l^{\{\mathrm{z})}-c_{N}^{(\overline{x})}.$$d_{\mathit{1}\backslash }^{(i)},=0$$\leq$$\sigma_{N,\rfloor}^{(\mathrm{i})}$$d_{N}^{(i)}\neq 0$$\sigma_{N+1,1}^{\langle i)}=s_{N+1,1}^{(i)}$$\sigma_{N+1,1}^{(i)}\leq s_{N+1,1}^{(i)}=s_{N.1}^{i}(i)$$s_{N}^{(i)}.>l^{(i)}-\mathrm{c}_{N}^{(\overline{\mathrm{z}})}$$d_{N}^{(\overline{\iota})}\neq 0$$\sigma_{N+1,1}^{(i)}\leq s_{N+1,1}^{(\iota)}=l_{1}^{(x)}-s_{N,1}^{(\overline{\iota})}.+1.$, Lemma 1 is again applied for. Then this leads contradiction and prove$F_{N}^{(\overline{\iota})}\in V(u, N-1)$$\sigma_{N+1,1}^{(i)}\leq l_{1}^{(\mathrm{i})}-s_{N,1}^{(\overline{0})}$$\deg(F)=(\sigma_{N+1,1}^{(i)}, \mathrm{i})$, $F\in V(u, N)$ with$\sigma_{\Lambda^{t}+1,1}^{(i)}=s_{\Lambda^{\Gamma}+1,1}^{(i)}$. Lastly for theis still in $V(u, N-1)$ andwith $0\leq \mathrm{i}<j\leq a-1$ ,$\deg(y^{j-i}F_{N}^{(i)})=$
which contradicts the minimality ofandandWe have proved Kamiya-Miura’s version with no use of figures shaped bycasealong with the line of the proof in [4] of Berlekamp-Massey algorithm for one-dimensional
more analogously than the original one

proof of (7), supposing$s_{N,1}^{(i)}<s_{N,1}^{(j)}$$y^{\mathrm{J}}-iF_{N}^{(i)}$$\square$$s_{7,\mathrm{z}\mathrm{V},1}^{(j)},\cdot$$(s_{N,1}^{(i)},j)$$s_{N}^{(i)}$$c_{N}^{(l)}$204
APPENDIX B. PROOF OF$\mathrm{T}\mathrm{H}\mathrm{E}\mathrm{O}\mathrm{R}\mathrm{E}.\backslash 4$$2$, we change (11) and (12) by setting
andBefore proving Theorem 2 for the present$\pi:=r+n-s_{N}^{(i)}$ and, respectively, as follows:$\overline{\dagger \mathrm{i}^{7}}_{\mathrm{A}^{\nu}}(\overline{\iota})$$-\mathrm{I}_{\mathrm{A}^{r}}’’(i\rangle$$\pi:=r+n’-s_{\mathrm{A}\mathrm{f}}^{\langle j\}}.$(35)$\overline{1/\cdot}(\Lambda^{\mathrm{r}}Z)(i):=\sum_{n\in\Phi^{(i)}(aB)}\{_{o(\pi)\leq\max\{m\mathrm{A}^{\acute{r}}-1\}}\pi\in\Phi^{(\Pi}2^{-1)}N\sum_{(.an)}F^{(i)}\pi-n+s_{\Lambda^{r}}^{(i)},N.\pi-n+s_{\Lambda}^{(i)}u_{\pi}+\sum_{o(\pi)>\max\{m,\Lambda-1\}}F^{(i)},\wp_{\pi}m\in\Phi^{\{n_{2}-i)}\langle a.n)\}Z^{o(n)}$

.

(36)

$\{_{o(\pi)\leq\max\{m.N-1\}}\pi\in\Phi^{(n_{2}-)}’(a,n’).\pi\in\Phi^{(,\prime}’ 2^{-J)}’\iota\sum_{)}G^{(_{\overline{l}})}u_{\pi}+\sum_{(a.n)}\mathrm{A}.\pi-n^{l}+s_{\Lambda d}^{(y)}G^{(\overline{l})}\wp_{\pi}N\pi-n^{J}+s_{\Lambda 4}^{\langle j\}}o(\pi)>\max\{m,\mathit{1}4^{r}-1\}\}Z^{o(n’\rangle+N-\Lambda J}$$\overline{\mathrm{T}t.}N(Z)(\overline{\iota}):=\mathrm{I}n’\in\Phi a,B)$

Note th at, if
and $n:=n’+l^{(i)}-k^{(j)}\in\Phi^{(i)}$ $(a. B)$ with $o(l^{\langle i)})=N$ and $o(k^{(g)})=\mathrm{A}I$
equalsin (36), the coefficient of$c_{N.1}^{(\overline{\mathrm{z}})}\neq-1$$Z^{o(n’)+\mathrm{A}’-\Lambda I}=Z^{o(n)}$

(37)

.

$G^{(\overline{I})}.u_{\pi}+N\pi-n+\iota\{\mathrm{i}\}_{-c_{\Lambda}^{\langle^{-})}}$$\sum_{\pi\in\Phi^{(n_{2^{-\mathrm{a})}}}(a,n)}$$o( \pi)>\max\{m,N-1\}$$o( \pi)\leq\max\{m,N-1\}$

since$c_{N}^{(\overline{\iota})}=k^{(j)}-s_{\lambda I}^{(j)}$$\pi\in\Phi^{(n_{2}-i)}(a.n)$$G^{\langle\iota)}\wp_{\pi}N,\pi-n+l^{\{\mathrm{e})}-c_{f\mathrm{v}^{\mathrm{r}}}^{(^{-}\rangle}$$\sum_{\pi\in\Phi^{(n_{2^{-j)}}}\{a.n)}$, $n_{2}’-j=n_{2}-l_{2}^{(i)}+k_{2}^{\langle j)}-j=n_{2}-\mathrm{i}$ . andforwith $o(\pi)>o(n’)$ .

Proof of Theorem 2. The coefficient of$z^{\pi-7?+s_{\mathrm{A}+3}^{(i)}}$in$F_{\Lambda+1}^{(i)},(z)$$F^{(i)}N,\pi-n+s_{\Lambda}^{\langle\}}?.-d_{\Lambda^{\gamma}}^{\{i)}G_{\wedge\pi-n+\ell^{\{i)}-c_{\iota^{l}}^{\mathfrak{l}^{-)}}}^{(\acute{\iota})}$which is regarded ascontribution of$G^{(\overline{\iota})}\mathrm{A}^{r}.\pi-n+l^{(i)}-c_{\mathrm{A}}^{\mathfrak{l}^{-)}}:=0$

if$F^{(i)}$$N,\pi-n+s_{\mathrm{A}^{7}}^{(_{1})}$$F^{(i)}$(z)$N,\pi-n+s_{N}$$l^{\{i)}$equals.

does not exist. Substituting this into (35) for$\overline{1’}_{N+1}(?)$, theequals$\pi\in\Phi^{(n)}(a,n)\mathrm{I}F^{(i)}u_{\pi}+N,r_{\downarrow}-n+s_{N}^{(\mathrm{i})}\sum_{\pi\in\Phi^{(n_{2}-i\}}(a,n)}F_{\wedge^{r},\pi-n+s_{\mathrm{A}}^{\{,)}}^{(i)},\wp_{\pi}$.

$o( \pi)>\max\{m,N\}$$o( \pi)\leq\max\{m,N\}$

If $N\leq m$ , that is, rnax{m.\acute $N$ } $=m$ , then this agrees with the coefficient ofinat (35).
If $N>m$ . that is. $\max\{m_{\dot{r}}N\}=$ A and $\max\{m, N-1\}=\mathrm{N}-1$ , then this agrees with$Z^{o(n)}$$\overline{\mathrm{t}^{r}}_{\Lambda}(i,)$$\sum_{\pi\in\Phi^{\{\mathfrak{n}_{2}-i)}(a,n)}F^{(i)},u_{\pi}+\sum_{(a,n)}\mathrm{A},\pi-n+s_{N}^{(\tau)}F^{(i)}\wp_{\pi}+u_{l}F^{(i)}\mathrm{A}^{\gamma}’,\pi-n+s_{\backslash ^{\mathrm{r}}}^{\{r)}\mathrm{A}" l^{(n_{2}-\mathrm{i})}-n+s_{\backslash }^{(.)}\pi\in\Phi^{(n_{2}-\mathrm{z})}‘$$o(\pi)\leq N-1$$o(\pi)>N-1$

where the last term is regarded as zero if there is no

Since $o(l^{(n_{2}-\iota)}-n+s_{N}^{(i)})=N+o(s_{N}^{(i)})-o(n)$ ,$ulZ^{N}\overline{F}_{N}^{(i\rangle}$. Similarly. the contribution ofwith $o(l^{(n_{2}-i)})=N$ .
is the coefficient ofin$l^{(n_{2}-r)}\in\Phi^{(n_{2}-i)}(o_{\dot{J}}n)$$u_{l}F^{(i)}N,l^{(n_{2}-\tau)}-n+s_{\mathrm{A}}^{(j)}$$Z^{o(n)}$equals$G^{(\overline{\iota})}$$N,\pi-n+l^{(\mathrm{i})}-c_{f_{\vee}}^{(\overline{r})}$$\pi\in\Phi^{()}(a,n)\mathrm{I}G^{(\overline{\mathrm{z}})}u_{\pi}+N,\pi-n+l^{(i\}}-\mathrm{c}_{j\backslash ’}^{(^{-})}\pi\in\Phi^{(\Pi}(a.n)\sum_{2^{-\mathrm{i})}}G^{(\overline{x})}\wp_{\pi}N,\pi-n+l^{(,)}-c_{N}^{\langle_{1}^{-}\}}$$o( \pi)\leq\max\{m,N\}$.

$o( \pi)>\max\{m.N\}$

.

.

205
If $N\leq m$ . then this agrees with the coefficient ofthen this agrees with$Z^{o(n)}$in$\overline{\dagger f’}\mathrm{A}(\overline{x},)$at (36), as noted there. If $N>m$ .

$\pi-n+_{J}l^{\langle_{?})}-c_{\backslash \prime}^{(^{-})}+\wp_{\pi}u\ell G^{(\overline{\mathrm{z}}\acute{)}},\mathrm{g}I\backslash l(n_{2^{-i)}}-n+l\langle \mathrm{i})_{-c_{N}^{\mathrm{t}^{-})}}$”$\sum_{\pi\in\Phi^{(\mathrm{n}_{2}-i)}(a,n)}G^{(\overline{\iota})},)N\pi-n+l^{(7}-\mathrm{c}_{f\backslash }^{(^{-)}}1\cdot u_{\pi}+\sum_{(\pi\in\Phi^{(n_{2^{-?)}}}a,n)}G^{(\overline{\iota})}\mathrm{A}$$o(\pi\}>N-1$$o(\pi)\leq N-1$

Since

.

$o(l^{(n_{2}-\mathrm{i})}-n+l^{(i\}}-c_{\mathrm{A}^{\tau}}^{\langle\overline{\iota})})=N+o(s_{J\iota f}^{(j)})-o(n)+N-\Lambda \mathit{1}\backslash u\iota G_{\wedge l^{(n_{2}-\tau)}-n+/(\tau)}^{(\overline{\iota})},,-c_{\mathrm{A}}^{\{\overline{\tau}\}}$

coefficient ofsimilar manner$Z^{o(n)}$in$u_{l}Z^{N}\overline{\mathrm{I}\pi_{N}^{(\overline{\mathrm{z}})}\vee}$is the: thus (14) and (16) are proved. (15) and (17) are verified in a$\square$

REFERENCES[1] D Cox, J Little and D. C’Shea, Ideals, varieties and algorithms,[2] N Kamiya, S Miura, “On a recursive decoding algorithm for codes defined on algebraic curves with at mostone higher order cusp,” (Japanese) Trans IEICE, J76-A. no. 3. pp.480 492\rangle 1993’.
[3] R Kotter, ttA fast parallel implementation of a Berlekamp-Massey algorith rn for algebraic-geometric codes
IEEE Trans Inf Theory, voI.44-4, PP.1353-1368, 1998
[4] JL Massey “Shift-register synthesis and BCH decoding,” IEEE Trans Inf Theory, vol.IT-15, pp 122-127.
1969.
Matsui, “A method to reduce the circuit scale of systolic array for BMS algorithm,’- (Japanese) Proc. The
26ih Symposium on Information Theory and Its Applications, pp 457-460, Dec 17, 2003.
[6] H Matsui S. Sakata, S. Mita “Determination of unknown syndromes in parallel decoding of codes from
A. no 4.
algebraic curves with systolic array,” (Japanese) Trans. IEICE,[7] H. Matsui, N. Matsunagi, S. Mita. “Construction of decoder for codes on algebraic curves and its performance
estimation,” Proc, International Symposium on Information Theory and Its Applications, pp411 414. Xi an
China Oct 9. 2002
[8] H Matsui, S Mita “Parallel decoding of codes on a class of algebraic curves using two-dimensional systolic
array.” (Japanese) Trans IEICE, J86-A. no 9. pp
IEICE, J76-A, no 11.
[9] S Miura, “Algebraic geometric codes on certain plane curves,” (Japanese)
1735-1745,
1992
PI)[10] MEO’Sullivan. “On Koetter’s algorithm and the com putation of error values,” Designs, Codes and CryPtography. vo1.31, PP. 169-188, 2004[11] S Sakata, “Finding a minimal set of linear recurring relations capable of gen erating a given finite two.
Journal of Syrnbolic Cornputation, No , pp 321-337, Nov 1988
dimensional
vector version of the BMS algorithm for implementing fast erasure-and-error decoding of[12] S. Sakata,
Proc AAECC-12, Lecture Notes m Computer Science, vol 1993, pp 291-310. Springer
codes.”
one-point AG$\mathrm{U}\mathrm{T}.\backslash 4$$\mathrm{S}\mathrm{p}\mathrm{r}1\mathrm{n}\mathrm{g}\mathrm{e}\mathrm{r}-1^{r}\mathrm{e}\mathrm{r}1\mathrm{a}\mathrm{g}_{\backslash }1992$$[\acute{\mathrm{i}\mathrm{J}}]\mathrm{H}$$\mathrm{J}8\acute{\mathrm{i}\}}$$\mathrm{p}\mathrm{p}.460-470_{\backslash }2002$$94_{\overline{\mathrm{D}}}-956,2003$$Trar\iota s$$\dot{\mathrm{i}1}$$\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{a}-\backslash \cdot.\cdot$$‘(\mathrm{A}$

Verlag, 1997[13] S. Sakata, H Elbrond Jensen, and T. Hoholdt, “Generalized Berlekamp-Massey decoding of algebraic geometric code uP to half the Feng-Rao bound,” IEEE Trans. Inf. Theory, vo1.41, No.6, Part I. PP 1762-1768.
Nov 1995
and[14] S Sakata and hl Kurihara, “A systolic array architecture for fast decoding of one-point AG codes
1719,
vol
Science,
Computerin
AAECC-13,
Notes
Lectureit,”
Procscheduling of parallel processing on
pp.302-313 Springer Verlag, 1999

(Hajime MATSUI)
Toyota Technological Institute)
豊田工業大学電子情報系 (Electronics andHisakata,
Tenpakn-ku, Nagoya 468-8511, Japan)
468-8511 名古屋市天白区久方 2-12-1 (2-12-1.ac.jp-mail address: hmat
松井.-.

$\mathrm{I}\mathrm{n}\mathrm{f}\dot{\mathrm{o}}\mathrm{r}\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{S}\mathrm{c}\mathrm{i}\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{c}_{\backslash }$$\mathrm{s}\mathrm{u}\mathrm{i}\Phi \mathrm{t}\mathrm{o}\mathrm{y}\mathrm{o}\mathrm{t}\mathrm{a}-\mathrm{t}\mathrm{i}$$\mathrm{e}$(Shojiro SAKATA), 栗原 正純 (Masazumi KURIHARA). The
電気通信大学情報通信工学科 (Department of 1nformation and Communication-Communications)
University of
182-8585 東京都調布市調布 丘 1-5-1 (1-5-1 Chofugaoka. Chofu-shi. Tokyo 182-8585, Japan)
阪田省二郎$\mathrm{E}_{\mathrm{I}1}\mathrm{g}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{n}\mathrm{g}_{;}$$\mathrm{E}\mathrm{l}\mathrm{e}\{j\mathrm{t}\mathrm{r}\mathrm{o}$$F$