Kurihara MASAZUMI (栗原 正純)

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 1700000, indirect: 510000)
本研究は、今まで本研究代表者が着々と実施してきた1点代数曲線符号の効率的な復号法の研究をさらに発展させ、より広い符号クラスである多点代数曲線符号に対し、高速な復号法を導入することが目的である。本研究の成果として、代数幾何符号を構成するのに使われる代数曲線の中で最も重要なHermite曲線を考え、その上で定義できる2点代数曲線符号について、その高速な復号法を確立した。特に、1点代数曲線符号の復号法の拡張として、2点Hermite曲線符号の訂正半径までの誤り訂正を可能とする多数決論理を組み込んだ高速復号法を与えた。

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (B), Fund Type: -, Overall Grant Amount: - (direct: 12600000, indirect: 2340000)
マルチユーザ情報理論と暗号理論の視点から, ネットワーク符号化におけるロバスト性とセキュア性の両立を意識して, 線形ネットワーク符号の新しい構成法, ネットワーク誤り訂正符号の復号に関する基本概念の確立と, 具体的復号アルゴリズムの提案, および, 計算量の評価を行った。さらに, 多重アクセス・ブロードキャスト・ネットワークに適するセキュリティ・プロトコル, 安全なコンテンツ配信のための電子透かし法等の提案をした。

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 3500000, indirect: -)
The objective of this research is to develop efficient algorithms for decoding not only algebraic geometric (AG) codes but also generalized algebraic geometric (GAG) codes and furthermore aim at systematizing past and new research results of fast decoding methods for those codes so that these decoding methods can be used practically in digital communication systems in the highly information-technological world in near future.
As outcomes of our researches, we have clarified several relations among fast decoding methods of those codes. In particular, we have shown that the parallel Berlekamp-Massey (BM) algorithm and Euclidean algorithm for decoding are identical, and that the multiple-sequence BM algorithm can be replaced by a succession of single-sequence BM algorithm. Furthermore, we have shown that the Welch-Belekamp algorithim can be realized as a vectorial version of BM algorithm. We presented these results in the 2004 International Symposium on Information Theory and Applications (ISITA-2004), in Parma, Italy, October 10-13, 2004, in the IEEE 2005 International Symposium on Information Theory, in Adelaide, Australia, September 4-9, 2005, and in the 2006 International Symposium on Information Theory and Applications (ISITA-2006), in Seoul, Korea, October 29-November 1, 2006, respectively. Related to the research, we published a textbook on Coding Theory entitled Introduction to Error-Correcting Codes which is a Japanese translation of A Course in Error-Correcting Codes by J.Justesen, and T.Hoeholdt published by European Mathematical Society, in 2004, as well as a paper entitled "Systolic array architecture implementing Berlekamp-Massey-Sakata algorithm for decoding codes on a class of algebraic curves" in IEEE Transactions on Information Theory, in 2005. In 2006, we had several tutorial lectures to give a grand survey of past and new results of our researches on fast decoding of AG codes.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 2600000, indirect: -)
The objective of this research is to develop an efficient algorithm for solving the problem of synthesizing linear feedback shift register allowing given pairs of input and output arrays by expanding our research results on fast decoding of algebraic geometric (AG) codes. The problem is an extension of the problem of synthesizing linear feedback shit register capable of generating given output arrays, which is closely related to fast decoding methods of practical algebraic codes such as RS codes, BCH codes and next-generation error-correcting codes, i.e. AG codes. The present problem treats nonhomogeneous Toeplitz and block-Toeplitz equations and their multidimensional extensions, while the former problem treats homogeneous Toeplitz and block-Toeplitz equations and their multidimensional extensions. Our problem is known as Wiener-Hoph equations in the field of linear system theory. As an outcome of our research, we have given an efficient method of solving our problem in case of pairs of one-dimensional input and output arrays, and presented our result in the IEEE 2002 International Symposium on Information Theory, in Lausanne, Switzerland, Jun 30-July 5,2000. Next, we have made clear that our method can be applied to fast factorization of polynomials over rational function field in the second stage of list decoding of polynomials over algebraic function field in the second stage of list decoding of AG codes, and presented these results in the Third Asian-European Workshop on Information Theory, in Awakamogawa, Jun 25-28, 2003, and in the IEEE 2003 International Symposium on Information Theory, in Yokohama, Jun 29-July 4, 2003, respectively. In the beginning of this research we undertook to solve the problem from a standpoint of system theory so that we have succeeded to show that our method can be applied to fast list decoding of RS codes and AG codes, which was one of our aims for more efficient decoding method. Related to the research, we published papers on parallel decoding of AG codes and compound-error-correcting codes in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, J85-A, 4, 460-470, 2002 (in Japanese), and E86-A, 7, 1813-1819, 2003 (in English).

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 3500000, indirect: -)
The theme of this research project is on a study of universal coding of enumerative discrete information structures, such as integers, trees, graphs and Young tableaux that frequently appear in the computer science, as well as finite discrete data representing letters of text, sampled quantized voice data, and data of brightness and chroma in pictures.
We have completed the analysis of coding of binary trees, and extended our method to k-ary trees and vector k-ary trees, the use of which should be powerful for universal coding. Furthermore, we moved a step towards the study of Young tableaux containing the class of trees as a subset of them. We can correspond a binary tree to a 2 x n rectangular Young tableaux. But we cannot correspond k-ary tree and vector k-ary tree to a standard Young tableaux in general. However, we show that by an extended Young tableaux defined by a poset in the integer lattice, it is possible to represent them. These results suggest attractive idea on constructing new code for general trees. Furthermore, we got many aspects on the meaning of Hook formula and the bumping algorithm by generalizing the standard Young tableaux to multi-dimensional tableaux. We presented these results at several international conference(IEEE ISIT 2002,2004,ISITA2004 at Parma, Conferences on General information transfer and combinatorics at Bielefeld university).
As well as the above theoretical study, we researched experimentally the performance of watermark and steganography. In the study of watermark for copyright protection and steganography that is considered as a generalized version of hiding information, we performed experiments with respect to the fundamental efficiencies of watermark on resistance against coalition, and steganography using frequency region by considering the structure of relevant data.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 1900000, indirect: -)
The objective of this research is to develop an efficient algorithm for list decoding of algebraic geometric (AG) codes or codes from algebraic curves. An algebraic list decoding method has been introduced recently by M. Sudan. It consists of two major procedures, where the first is to find an interpolation polynomial having a set of zeros specified by the pair of the received word and the information positions, and the second is to factorize the interpolation polynomial. This Sudan algorithm (Sudan-1) has been improved to another version (Sudan-2) by Guruswami and Sudan, where Sudan-1 can work only for coding rate less than 1/3, but the latter even for larger coding rate. As an outcome of our research, we have given efficient methods of finding the interpolation polynomials for both Sudan-1 and Sudan-2 list decoding algorithms of RS codes, and published a paper (in Japanese) treating these subjects in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol.J83-A, No.11, 2000. Therein, based on the observation that the problem of finding the interpolation polynomial is reduced to finding the Grobner basis of a polynomial ideal having the specified zeros, we have given the efficient interpolation methods by applying the BMS algorithm which we invented before for fast realization of the conventional bounded-distance decoding of AG codes. Furthermore, we have made clear that the BMS algorithm can be adapted naturally to fast Sudan-1 interpolation for AG codes, the result of which we presented in the IEEE 2000 International Symposium on Information Theory, in Sorrento, Italy, June 25-30, 2000. On the other hand, it was difficult to adapt the BMS algorithm to fast Sudan-2 interpolation for AG codes, because this problem, do1 not have such a nice structure as the previous. But, we have given a solution to it by using a different formulation based on the defining arrays of a polynomial ideal. We presented the result in the international ' conference AAECC-14, Melbourne, Australia, November 26-30, 2001, and published in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: Proc. AAECC-14 (Eds. S. Boztas, I.E. Shparlinski), Springer Verlag, 2001.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 1600000, indirect: -)
The theme of this research project is on a study of novel transform of information for the efficient data compression and the secure data transmission.
With respect to the information transform for data compression, we have first provided some interesting properties of the fix-free cock. Next, we need an efficient expression of the ordered tree for the date compression .and storage/ Therefore, we analyzed the performance of coding of ordered trees, and established the optimal codeword length function. Furthermore, we had studied the Bernoulli splitting process with biased probabilities, and gave asymptotically the expected branch number and depth of the trie by using the Mellin transform. Here, we encounter the entropy function in the residue of the related generating function. This phenomenon could be found in a case where the generalized amplitudes and frequencies are in the relation of multinomial coefficients and products of probabilities, respectively, in the generalized harmonic series. Furthermore, we proposed the Catalan code for integers by a combination of the pre-order coding and the enumerative coding of binary trees, and compared the performance of the code with that of Elias omega code.
The transform for secure data transmission is studied from two aspects, that is, from the error-correcting coding and the data security points of views. Specifically, by introducing the theoretical framework of protection of data suffered from the compound errors, that is, the mixture of random errors and burst errors, we gave a new efficient decoding method of iterated codes for the compound error correction.
On the other hand, for the study of data security we concentrated on synthesizing a new method which can protect against the attack of removing the watermarks. Here, we considered the relation to the error control code, and investigated the various kind of attacks. We have realized a method having both of the convenience for the user and of the strength against the collision and repeat attack.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 2000000, indirect: -)
The objective of this research is to extend our previous method for fast decoding of one-point algebraic geometric codes (codes from algebraic curves or surfaces) to a fast GMD (generalized minimum distance) decoding of these codes. For fast GMD decoding of conventional algebraic codes including RS codes, several alternative methods have been given by other researchers. On the other hand, based on the recognition that algebraic geometric codes are a natural extention of conventional algebraic codes from one dimension to n dimension, we published some survey papers in volumes Grobner Bases and Applications and Codes, Curves and Signals as well as in journals Journal of IEICE and Mathematical Science. First, in this broad perspective, we published a paper on another version of fast GMD decoding of one-dimensional algebraic codes in IEICE Transactions. Next, we published a paper on fast erasure-and-error decoding method of one-point algebraic geometric codes jointly with American and Danish researchers in IEEE Transactions on Information Theory, the contents of which should be a core of fast GMD decoding method of these codes based on BMS algorithm. But, there still remains a difficult problem of how we can dispense with many redundant iterations of these erasure-and-error decoding procedures which are required by majority logic in determining the unknown syndrome values necessary for error correction up to the designed distance. To settle this problem, we have proposed a pair of GMD procedures, i.e. erasure-addition and erasure-deletion which can be combined with each other in many alternative ways during a fast GMD decoding process. At present we are trying to construct a kind of heuristic algorithm for fast GMD decoding method. Together with these research works we have published several relevant papers on fast decoding of algebraic geometric codes and its parallel implementation, etc.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 1900000, indirect: -)
Before we gave a fast decoding algorithm for one-point algebraic geometric codes up to the designed distance, which can be implemented in serial form on conventional computers of von Neumann type. Now we have etablished a method for implementing the decoding algorithm in parallel form with a sytolic array architecture for the parallel processing. Parts of our results were presented in several international conferences : (1) Our bsic idea for paralleliztion of the original fast decoding algorithm at the conference IMAX-ACA,Line, Austria, in July, 1996 ; (2) A vector version of the fast algorithm which is the kernel of our parallel decoding method at the conference AAECC-12, Toulouse, France, June, 1997 ; published in Lecture Notes in Computer Science (LNSC), Vol.1255 (Eds.Mora et al.), Springer, 1997 ; (3) A method for efficient scheduling of the whole cells (processors) in implementing our parallel decoding algorithm with a systolic array architecture at the IEEE International Symposium on Information Theory, Ulm, Germany, July, 1997. For the codelength n, our method has time complexity of order O (n), which is better than O (n^2) obtained by [R.Kotter, A fast parallel implementation of a BM algoritm for AG codes, On Algebraic Decoding of AG Godes and Cyclic Codes, Dissertation, Linkoping Univ., (section) 3,1996]. In addition, we have proceeded to investigate several relevant themes such as a soft decision decoding method for correcting both erasures and errors, which can be parallelized (Part is contained in the paper published in LNSC-1255). A fast generalized minimum distance (GMD) decoding method was presented in the Allerton Conference on Communication, Control and Computation, Illinois, USA,September, 1997, and a lecture on the Berlekamp-Massey-Sakata algorithm was given at the special conference BlahutFest just before the Allerton Conference. A tutorial paper on Grobner bases and coding theory is published in Grobner Bases and Applications (Eds.Buchberger et al.), Cambridge Univ.Press, 1998.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research, Category: Grant-in-Aid for General Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 1500000, indirect: -)
We have established a fast decoding algorithm of any one-point algebraic-geometric (AG) code, which is defined on an arbitrary algebraic curve, up to the Feng-Rao designed distance. For the codelength n, our method has computational complexity of order O (n^<7/>) and of order less than O (n^3) to decode a one-point AG code defined on a Hermitian plane curve and on any algebraic curve of higher dimension, respectively, while the fundamental Feng-Rao method has complexity of order O (n^3). In regard to efficiency, out method is the best among all the known decoding methods of any one-point AG code. These results were presented in part at the 1994 IEEE Int. Symp. Inform. Theory, at the 1994 IEEE Int. Worshop Inform. Theory, and at some other conferences. The contents were published partially in Finite Fields and Their Applications, Vol.1,1995, and the main part will appear in the forthcoming Special Issue of IEEE Trans. Inform. Theory. The details of our theory were published in Bullet. Unv.Elect. -Comm., Vol.8,1995. In parallel to the above theoretical work, we made some computer experiment. We implemented a software system (C-program) for our decoding method, and by applying it to two kinds of codes defined on a Hermitian plane curve and on its three-dimensional extension, we investigated the actual efficiency of our method. As a result of simulation on many random error-patterns, it was shown that both the number of arithmetics over the finite field and the actual computing time have a tendency quite similar to the theoretical computational complexity, which gives an additional evidence to our theory and a guideline for practical use in future. Furthermore, it was made sure that our method can decode beyond the designed distance in some cases. On the other hand, we published a paper containing a general review on a broader class of AG codes in Bullet. Jap.Soc.Ind.Appl.Math., Vol.4,1994. In addition, we have proceeded to investigate parallel processor architecture for hardware implementation of our method and fast error-and-erasure decoding as extensions of the present research. Some results of the research were presented at the AAECC-11 Conference and at the 1995 IEEE Int.Symp.Inform.Theory, and in some other conferences.