FAST PARALLEL DECODING ON SYSTOLIC ARRAY ARCHITECTURE FOR CODES ON A CLASS OF ALGEBRAIC CURVES (Algebraic Aspects of Coding Theory and Cryptography)
Hajime Matsui, Shojiro Sakata, Masazumi Kurihara · Kyoto University Research Information Repository (Kyoto University) · 2005
We construct a two-dimensional systolic array implementing the Berlekamp-Massey- Sakata 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 par- allelism of the algorithm.The introduced polynomials are used in the majority logic scheme by Sakata et al. to correct errors uP to the designed minimum distance without affecting its high-speed.The arrangement of the nearest local connection of processing units $\ln$ the systolic array is obtained for the general case.Furtherm ore, shortened systolic arrays that reduce the circuit scale and have the sam $\mathrm{e}$ function are constructed with only a slight modification of the connections and controls; this enables the adjustment of the circuit scale for different types of systems.X. PRELIMINARIES Let $\mathbb{Z}0$ be the set of non-negative integers.In this paper, we consider a one-point algebraic-that$\mathcal{X}$ is always absolutely irreducible and has no singular point except at a single infinite point $P_{\infty}$ .For simplicity, we consider a non-singular $C_{a}^{b}$ curve although it is possible to argue singular cases similarly [9].Then, the genus $g$ of A is given by $g$ $=$ $(0 -1)(\mathrm{b}-1)/2$ ; moreover, the residue class ring $\mathrm{K}[\mathrm{X}]:=\mathrm{K}[\mathrm{X}]y]/(D(x, y))$ consists of all the algebraic functions having no poles except at $P_{\infty}$ .Let $\{P_{j}\}_{1\leq j\leq n}$ be a set of $nK$-rational points except $P_{\infty}$ ; we denote the pole order of $F\in$has dimension $m-g+1$ , provided $m>2g$ $-2$ by Riemann-Roch Theorem.In this paper, we assume that $m>2g-2$ for simplicity.Our code $\mathrm{C}(m)$ is defined as $C(m):=$ $\{(c_{j})\in K^{n}|\sum_{j=1}^{r\iota}c_{j}.F(P_{j})=0$ , $F\in L(mP_{\infty})\}$ .Given a received word $(rj)=(c.j)+(ej)$, where $ej eq 0$ only for $j\in\{\prime j_{1}, \cdots 2 Jt\}$ corresponding to $\mathcal{E}=\{P_{j_{\gamma}}\}_{1\leq\gamma\leq t}$ , we want to find a Grobner basis of the error-locator ideal $I(\mathcal{E}Then, the set of common zeros of all the elements in the Grobner basis agrees with $\mathcal{E}$ , and the error values $\{e_{j_{\gamma}}\}_{1\leq\gamma\leq t}$ are obtained by O'Sullivan's formula in [10].In this paper, we do not use any special fonts to represent vectors.For any element $n\in \mathbb{Z}_{0}^{2}$ , $n_{1}$ and $n_{2}$ denote the first and second components of vector $n$ .Let $\Phi(A)$ $:=\{n\in \mathbb{Z}_{0}^{2}|n_{2}