We have constructed an e-learning system capable of collecting various contexts. From the demonstration experiment using this, we clarified what behavioral patterns of the learners are signs of stumbling blocks of studying and lowering their interest. In particular, we constructed a learner model by clarifying the characteristic appearance patterns of contexts, such as the order of reading textbooks and error patterns in programming. Based on this model, we realized the system that can feed back the information necessary for teacher guidance of students.

The objective of this study is to develop and deepen large-scale and diverse business data analytical technology (business analytics), propose new analytical models corresponding to various business data.
Specifically, we promoted research on the following individual themes: 1) development of data analytics technology for database information on EC sites, 2) development of analytical technique of marketing information accumulated as text data, 3) development of statistical model for recommendar systems, 4) Theoretical analysis of Web marketing model using information retrieval and recommendation technology, 5) Development of analytical method for high dimensional and sparse large scale data, 6) Development of privacy protection data analysis technology.

Applying classification methods based on the statistical machine learning and convex optimization for big data, we showed that it was possible to obtain efficiently the high precision solutions for wide range of various problems.
Specifically, we proposed algorithms and analysis methods, and showed the effectiveness for the following problems:
(1)privacy preserving distributed calculation problem for the case which some parties have different secret data, (2)latent class model analysis problems of EC site or institutional research, (3)dynamic reconfiguration circuit design problem, (4)document classification problem based on L1 optimization, (5)lossless data compression using CART, (6)fault-diagnosis problem using markov random field, and (7)programming edit history acquisition and visualization problem for many students.

The model of Global Literacy Education includes Communication Management, Learning Strategies, Team Work, Critical Thinking, Synthesis Skills, Analytic Skills, Problem Solving, Project Management and Diversity Management. Global Literacy education is realized in the package of three-staged courses: English Tutorials, Critical Reading and Academic Writing (critical thinking, analytic skills, synthesis skills and problem solving skills), Discussion English Tutorials (communication management, learning strategies and problem solving sills) and Cross-Cultural Distance Learning course (project management skills, problem solving skills. project management skills and diversity management skills). All of these courses are based on Common European Framework of Reference for Languages (CEFR). Course Contents are digitalized and provided with automatic assessment of learning outcomes, along with interactive widgets and learner logs to assist instructors to give personalized feedbacks.

This research project took the next generation style of e-learning on the cloud computing environment as main theme from Japanese financial year (FY) 2011 to 2013. In FY 2011, the project assumed an e-learning style that the learners make use of virtual desktop environment for e-learning. In FY 2012, it assumed an e-learning style that they are under e-learning environment with their digital textbooks. In FY 2013, it constructed a prototype of e-learning supporting system that the various logs of the learners can be preserved and visualized on the cloud computing environment. For the above e-learning styles including the prototype, the project enforced some experiments for their evaluations. Then, some interesting results were obtained and the prototype system's effectiveness was proven to some extent. The part of the obtained results was presented at the related conferences.

For its good error correcting ability, Turbo code and Turbo decoding algorithm, which was proposed in the research area of the error correcting codes, have gotten a lot of attention recently as important technology of 21st century's reliable communication and accumulation technique. It have been known that the iterative decoding algorithms which includes Turbo decoding algorithm can be regarded as applications of Belief Propagation algorithm, which was proposed in the research area of the knowledge information processing as uncertain reasoning algorithm. It can be interpreted that the turbo decoding algorithm calculates the approximation of posterior probability effectively.
It was obtained that the Extended Junction Graph (EJG) and the parallel iterative algorithm for calculating posterior probability, which are results achieved in "The Analysis and Design of the Reliable Iterative Decoding Algorithm based on Uncertain Reasoning" which is supported by Grant-in-Aid for Scientific Research in 2000-2002, can deal with general probabilistic models compared to existing belief propagation algorithm and retain the higher performance even when the graph has loops (almost of the practical codes have loops).
In this research, we have done following,
(1)We applied the EJG and the parallel iterative algorithm to the LDPC codes which have some small loops, we sought further efficiency and analyzed the performance.
(2)We applied the algorithm to the channel models which have feedback channel such as ARQ Scheme and analyzed the performance.
(3)Moreover, we applied the algorithm to the decryption of stream cipher and analyzed the performance.

1. We analyzed and generalized our original reasoning algorithm, which is already proposed, based on both Bayesian Network and Graphical Model. Then, we designed a new algorithm for calculating posterior probability on probability models including classes of efficient codes. We also inspected the algorithm in terms of both theoretical and simulating points and then got good results.
2. Moreover, we inspected both convergence and accuracy of the algorithm in terms of the differential geometry, machine learning and statistics and then we gave theoretical understandings onto it.
3. We defined the generalized posterior probability distribution and made mathematical expression of a problem of the uncertain reasoning given the observed probability distribution. It turned out that the result of our reasoning method has a lot of mathematical meanings that is very important. We improved our algorithm by reducing both the calculation and memory occupation, and by paralyzing its procedures.
4. We applied our algorithm on the Extended Junction Graph, which is also our generalized original graph, then proposed the efficient parallel belief propagation algorithm. As a typical application, we applied our algorithm, which is already mentioned in 2., for decoding on Extended Junction Graph constructed by LDPC codes. We examined its natures in terms of both theoretical and experimental aspects.
5. We used our Extended Junction Graph for both convolution codes and tail biting codes, then we applied our algorithm mentioned in 2. for decoding both codes. We examined its results from the both mathematical and computational points of view.
6. We applied our generalized algorithm for calculating posterior probability, which is already proposed year 2001, to a special model class that has guarantee of convergence. The whole procedure guarantees mathematical meanings as well as both efficient calculation and memory occupation.
7. We developed out results in year 2001 on decoding algorithm, then inspected from point of theoretical and experimental view.

今年度目標とした項目に対し,下記の結果を得た.
1.データマイニングとテキストマイニング
新聞記事などのテキストデータについて,その自動分類法と,特に複合語に着目し分類精度を向上させる方式を提案した。また,大規模データベースにおいて属性値が連続値をとる場合に属性間の相関を考慮した離散化の方法を提案し,いずれも信学会・ソサエティ大会で発表した.定型項目と記述項目が混在するアンケートデータからの相関ルールを抽出する新しい方法を提案した.エントロピーを用いて多値属性値の出現頻度から複雑さを評価し,これを最小支持度の修正に反映する.これはテキスト中の単語の出現頻度に対しても合理的に取り扱うことが出来る方法になっており、実データに適用しその有効性を明らかにした.情報理論とその応用シンポジウムで発表した.
2.符号化技術
ブロックターボ符号におけるインタリーバの有効な設計方法を提案した.置換行列に制約条件を加えることにより,構成されたターボ符号の最小距離を増加させることができる.そのときの条件・置換行列の求め方・要素符号を与えたときの最小距離の導出などを具体的に与え評価した.また,リスト復号法を用いた連接符号の復号アルゴリズムの提案・評価,および周期的畳み込み符号の新しい構成法とその性能の導出を行った.いずれも情報理論とその応用シンポジウムで発表した.

(1) (1)We studied data compression for text in source coding. We theoretically derived difference in code lengths between the codes based on the MDL principle and the Bays codes. Then these results were applied to the model selection problem.
(2)We developed an approximately optimal algorithm which reduces complexity in calculation for the Bays code. We applied this algorithm to benchmark test, files, and so on, which gave good results. As data compression for speech, image, and so on, we also proposed an algorithm which applied the trellis codes to the source coding problem, and performed an evaluation experiment for this algorithm.
(2) (1)In channel coding, we developed an algorithm on decoding beyond the BCH bound for BCH codes, and also an algorithm on soft decision decoding for block codes. From the viewpoint of complexity in calculation, we found a practical decoding method.
(2)For convolutional codes, the relation between the Viterbi decoding method and the syndrome decoding method was elucidated. And these results were applied to the ARQ method. We found a decoding method having excellent performance at low rate.
(3)We performed signature analysis by parallel processing as an application of the error-correcting codes to test methods of LSI.

In these a few years, there are a lot of workstations and termiinals connected into single universal network. These workstations will proceed a lot of variety documents such as very personal information, published data, electric magazine, private mail and so on. Establishing a public common database connected to open network will be important subject to realize a high efficient system shared by mass of customers at reasonable cost. A safe-deposit box is very convenient facility, because many kind of assets and important docments of indivisuals are stored with hight security at reasonable cost. The same function of this system will bave to be exist in future information society in the single universal network system. We have proposed secure document image management system which manages private information at resonable cost with high security.
To realize real secure system in such open facility, there are two main problem. They are leakage and illegal occupation. The leakage means the content of document can be thrown out by somebody who is not the autliorized person. The illegal occupation means an injured function of database management occurred by mass of prescribed message that have been kept and are increasing in the database storage.
To solve above problems, we have studied following items.
1. Concreat system configuration and basic functions
2. Network access protocol in deposit and takeout procedure to keep high security
3. Database management protocol for secure document management
4. Customer identificaion scheme using feature of physical characteristics such as sensed data of fingerprint
5. Secure key sharing schemes using smartcard with no pre-communication
6. Scramble algorithm for document image using Soace Filling Curve
And we have constructed real simulation system using G4 FAX, ISDN network, workstations and smart card system in order to evaluate the protocols of proposed system at the point of security atid efficiency.

本講演では、Cプログラミングを用いて基本的な情報処理の方法やアルゴリズムの組み立て方を学ぶ「情報処理基礎演習」の授業を対象とし、編集履歴可視化システムの具体的な活用事例について報告する。具体的には、荒本らによって開発された編集履歴可視化システムを活用して、学生のプログラム作成時の編集履歴データを取得すると共に、演習授業中に実施する小テストやレポート、及び試験得点といったこれまでの教学データを統合し、教育支援に役立てる試みについて検討する。これにより、プログラミング系科目におけるLearning Analyticsの具体的な方法論や活用し得る分析モデルについて明らかにする。

For maximum likelihood decoding, Shamai and Sason have pointed out that various upper bounds which were known are a special case of the DS2 bound. Then, recently, Hof et al. extended this discussion to generalized decoding (GD), which was introduced by Forney with decision criterion FR. Hof et al. also derived the Sulman-Feder bound for GD (GD-SF) for the binary-input output-symmetric channel under some proper conditions. However, this bound employs one parameter, though Forney's original upper bound has two parameters. In this paper, by choosing a proper function g(y), we derive a new GD-SF using two parameters and clarify this bound is tighter than Hof et al.'s GD-SF.

本研究では，大学教育用の教科書の作成を通して，マルテメディアコンテンツやインタラクティブコンテンツを含む電子教材の開発方針の検討を行う。

In this paper, we develop an iterative multiuser joint decoding of code-division multiple-access (CDMA) signals based on a distributed optimization algorithm. For the joint decoding problem, decoding algorithm based on the turbo principle is widely used. The algorithm consists of soft-input soft-output (SISO) channel decoder and SISO multiuser detector and it can be derived as an application of the sum-product algorithm. On the other hand, in the research area of error correcting codes, the decoding algorithm based on convex optimization has been attracting a great deal of attention. Decoding algorithm based on linear programming (LP) has decoding error rate which is comparable with sum-product algorithm with stronger theoretical guarantees. We formulate the joint decoding problem of CDMA signals as an convex optimization problem and we present a relax form of the problem. Moreover, we propose a distributed algorithm which efficiently solves the relaxed optimization problem. The proposed algorithm is based on alternating direction method of multipliers (ADMM).We also see the performance of the proposed decoder through numerical simulations.

It is well known that the random forests proposed by L. Breiman in 2001 achieve the high accuracy for classification problems and regression problems. This method generates many regression trees by using CART for the regression problem. In this manuscript, we proopse the lossless image data compression based on regression trees.Then we treat previously compressed pixels as explaining variables, and treat the next pixel to compress as the objective variable. First, the image data to compress is "learned" by CART or random forests, and the output regression trees are coded. Next, each pixel data is predicted by using these regression trees, and each difference between the prediction value and the actual pixel value is compressed. Finally, we show that the proposed method can reduce compression ratio in comparison with PNG format.

A new method of constructing optimum linear constant weight codes based on various generalization of (u, u+v) construction. We have presented a new method of constructing superimposed code C^<(h_1,h_2…,h_1)>_<(s_1,s_2,…,s_1)> and presented a large class of optimum linear constant weight codes. We present large classes of optimum linear constant weight codes for k=2 and k=3 for n≦128. We also present optimum linear constant weight codes that meet BV bound given k=2, 3, 4,5 and 6, for n≦128. The author would like to present the following conjecture: ・C^(h1)_(s1) given in this paper yields the optimum linear constant weight code at the code-length n=3h_1, number of information symbols k=2 and minimum distance d=2h_1 for any h_1. ・C^<(h1)>_<(s1)> yields the optimum linear constant weight code at n=7h_1, k=3 and d=4h_1 for any h_1. ・Code C^<(h1,h2…,h1)>_<(s1,s2,…,s1)> yields optimum linear constant weight code of length n=2^k-2, number of information symbols k and minimum distance d=2^<k-1>

A new method of constructing optimum linear constant weight codes based on various generalization of (u, u+v) construction. We have presented a new method of constructing superimposed code C^<(h_1,h_2…,h_1)>_<(s_1,s_2,…,s_1)> and presented a large class of optimum linear constant weight codes. We present large classes of optimum linear constant weight codes for k=2 and k=3 for n≦128. We also present optimum linear constant weight codes that meet BV bound given k=2, 3, 4,5 and 6, for n≦128. The author would like to present the following conjecture: ・C^(h1)_(s1) given in this paper yields the optimum linear constant weight code at the code-length n=3h_1, number of information symbols k=2 and minimum distance d=2h_1 for any h_1. ・C^<(h1)>_<(s1)> yields the optimum linear constant weight code at n=7h_1, k=3 and d=4h_1 for any h_1. ・Code C^<(h1,h2…,h1)>_<(s1,s2,…,s1)> yields optimum linear constant weight code of length n=2^k-2, number of information symbols k and minimum distance d=2^<k-1>

本稿では情報数理教育を対象として，インタラクティブなコンテンツに対する電子教材の試作を検討する．具体的にはRSA暗号に対するインタラクティブな教育コンテンツを作成し，評価を行う．このとき，マルチプラットフォーム化を念頭におき，コンテンツはHTML,CSS,JavaScriptのみを使用して構築する．数式の表示はMathJaxにより行う．さらにPhoneGapを用いてマルチプラットフォームに対応可能なアプリ化を検討する．

本研究では、大学教育用の教科書としての電子書籍の試作を行い、電子書籍内のマルチメディアコンテンツが内容理解に与える影響の評価を行なう。具体的には、教科書の内容を補助するような動画や音声を配した電子書籍を試作し、ユーザアンケートによって教育効果を評価する。

In this paper, we study a privacy preserving linear regression analysis. We propose a new protocol of distributed calculation method that calculates a least squares estimator, in case that two parties have different types of explanatory variables. We show security of privacy in the proposed protocol. Because the protocol have iterative calculation, we evaluate the number of iterations with numerical experiments. Finally, we show an extended protocol that is a distributed calculation method for κ parties.

Extended cosine measure has been proposed as one of the method of metric learning which learns metric matrix expressing the characteristics of training data. However, this method introduces a unique metric matrix and estimate it by learning of all training data. Therefore, there is a room to improve this method because document data has normally different statistical characteristics in each category. In this study, we propose the way of learning metric matrices for each category. To show the effectiveness of our proposed method, simulation experiment is conducted.

B. M. Kurkoski et al. have proposed a quantizer design method based on the maximization of the mutual information.Furthermore, an application method for the decoding of LDPC codes has been proposed.This method has the constraints of binary-input discrete memoryless channels, and it is difficult to apply for general channels directly.In this study, we focus on MIMO communication systems and consider a quantizer design method based on the mutual information criteria.Then we propose a design method maximizing the mutual information by the conjugate gradient method.

サイバー大学IT総合学部の専門必修科目「コンピュータ入門」の学生アンケートを分析した.ここで,アンケートは選択型の質問と記述型の質問が混在している.授業モデルを提案し,PLSIモデルを用いて文書のクラスタリング・分類,および重要文抽出・特徴語抽出を行い,授業改善に結びつくヒントを得た.

本稿では,フルオンデマンド形式の情報系科目で実施された学生アンケートの分析結果について報告する.対象とするのはすべての授業がインターネット上で実施され通学を必要としない4年制大学におけるコンピュータ関連の科目である.従来の通学制とは異なる新しい授業形態であることから,効果的な授業のあり方や授業改善についても新しい取り組みが必要になると考えられる.そこで本研究では,通学制の大学において同内容の授業で実施された学生アンケートとの比較分析により,フルオンデマンド授業の特性について検討を行う.

カテゴリが既知の学習データを用いて,新規データのカテゴリを推定する自動分類問題は,サポートベクターマシンなど数多く研究が行われている.本研究では,カテゴリ中に発生するデータがマルコフモデルに従って発生すると仮定したときに,学習データを用いて分類誤り確率を推定する手法を提案する.

Experiments usually aim to study how changes in various factors affect the response variable of interest. Since the model used most often at present in experimental design is expressed through the effect of each factor, it is easy to understand how each factor affects the response variable. However, since the model contains redundant parameters, a considerable amount of time is often necessary to implement the procedure for estimating the effects. On the other hand, it has recently been shown that the model in experimental design can also be expressed in terms of an orthonormal system. In this case, the model contains no redundant parameters. Moreover, the theorem with respect to the sum of squares for the 2-factor interaction, needed in the analysis of variance (ANOVA) has been obtained. However, 3-factor interaction is often to be considered in real cases, but the theorem with respect to the sum of squares for the 3-factor interaction has not been obtained up to now. In this paper, we present the theorem with respect to the sum of squares for the 3-factor interaction in a model based on an orthonormal system. Furthermore, we can also obtain the theorem for interactions with 4 or more factors by the similar proof. Hence, in any real case, we can execute ANOVA in the model based on an orthonormal system.

In this paper, we present the theorem of the relation between the Fourier coefficients and the 3-factor interaction effects. From this theorem, the 3-factor interaction effects can be easily obtained from the Fourier coefficients. Therefore, it is possible to implement the estimation procedures easily as well as to understand how any interaction affects the response variable in the model based on an orthonormal system.

The text classification problem has been investigated by various techniques, such as a vector space model, a support vector machine, and so on. On the other hand, the Context-Tree Weighting (CTW) algorithm has been proposed as an outstanding data compression. Furthermore, experimental results have been reported using the CTW algorithm for the text classification. In this paper, we assume that each document with same category arises from one stochastic model for the text classification using the CTW algorithm. Then we propose an analysis method to obtain the classification error probability for the document with the finite length.

Allocation methods for Cartesian product files on multiple disks by using linear error-correcting codes were proposed. In this paper, we propose an allocation method using unequal error protection(UEP) codes. Code-words of an UEP code have some special bits which are protected against a greater number of errors than other bits. We firstly assume a model that "*", which means "don't care". appear with different probability in each attribute of queries. In this case, the average response time can be calculated by using the split distance distribution. Then, we calculate the average response time of the allocation method using UEP codes, and we show the effectiveness of this method from numerical examples.

Probabilisitc inference problem on the graphical model is very important since it is arising in many applications which include theory of error-correcting codes, image processing, speech recognition, and so on. Recently, linear programming based decoding algorithm for the error-correcting code has been receiving a lot of attention. Viewing the decoding problem as an example of the probabilistic inference problem on the graphical model, the factor graph corresponds to the problem has some specific structure. The functions in the factor graph can be classified into two classes, indicator functions and non-indicator functions. For the graph corresponds to the decoding problem, each non-indicator function is connected to only one variable node. On the other hand, the factor graph corresponds to the general probabilistic inference problems possibly have non-indicator functions which is connected to more than one variable nodes. The aim of this study is to develop the linear programming based inference algorithm for general inference problems.

Encoding complexities of LDPC codes and Generalized LDPC (GLDPC) codes, which are constructed by combining the ordinarily LDPC codes and linear block codes, are proportional to the square of the code length when using their generator matrices. J. Lu et.al. have proposed a linear time encodable method called "labe-and-decide algorithm" which decomposes Tanner graphs of arbitrary class of randomly constructed LDPC codes into a hierarchical structure to calculate parity bits from information bits. In this study, we propose an efficient encoding method for arbitrary class of randomly constructed GLDPC codes. It applies Dulmage-Mendelsohn decomposition for both the parity-check matrix and base code of GLDPC codes and cancalculate the parity bits by using pseudo inverse matrix of the component codes of GLDPC codes. We show the effectiveness of the proposed encoding algorithm by deriving the maximum number of encoding operation.

Though the iterative threshold of Bit-flipping (BF) decoding is less than that of belief-propagation (BP) decoding, BF decoding algorithm is an effective method compared with the BP decoding algorithm in term of the decoding complexity. It is verified that the BF decoding shows an error floor when the channel error probability is small. To overcome this problem, S.K. Planjery, et. al. have proposed three bits BF decoding algorithm whose messages are combined with an ordinarily binary message and two bits message which represents a reliability of a codeword bit. Although the decoding performance of three bits BF decoding on an error floor region is greater than that of the BF decoding, its decoding rule is so complicated that it can be applied to for only the regular LDPC codes with variable node degree 3. In this paper, we propose a new three bit BF decoding algorithm applicable for the irregular LDPC codes. We also show by simulation results that the performance of the proposed new three bits BF decoding algorithm rule is better than that of the ordinarily three bits BF decoding algorithm. We also analytically derive the performance of both three bits BF decoding algorithms and compared them to show the effectiveness of our algorithm by the density evolution.

Experiments usually aim to study how changes in various factors affect the response variable of interest. Since the response model used most often at present in experimental design is expressed through the effect of each factor, it is straightforward to ascertain how each factor affects the response variable. However, since the response model contains redundant parameters, we must calculate the degrees of freedom defined by the number of independent parameters in the analysis of variance. In this paper, we show that through a description of experimental design based on an orthonormal system, the response model can be expressed using only independent parameters. Hence, we do not have to calculate the degrees of freedom defined by the number of independent parameters.

Recently, with increasing electric documents, effective knowledge acquisition become important issue method. Document classification is one of the techniques. In this paper, we use Probabilistic Latent Semantic Indexing (PLSI) as document classification technique. The characteristics of PLSI is dealtwith handle multi-category and lead solution with using EM algorithm. We propose a method that can classify a small amount of training data using the EM algorithm. We apply this method into WEB page and show its effectiveness.

In this paper, we develop a linear-programming (LP) decoding for the multiple-access channel with binary linear codes. For the single-user channel, LP decoding has been attracting much attention in recent years as a good approximation to the maximum likelihood decoding. We demonstrate that how the maximum likelihood decoding problem for the multiple-access channel with binary linear codes can be formulated as a linear programming problem. It is not straightforward because the objective function of the problem is a non-linear function of the codeword symbols in general. We introduce the auxiliary variables such that the objective function is a linear function of those variables. Then the ML decoding problem reduces to the LP problem however, it is too complex for practical implementation. As the case for the single-user channel, we formulate the relaxed LP problem. Just as in the case of the single-user channel, the proposed decoder has the desirable property called ML certificate property, that is, if the decoder outputs integer solution, it is guaranteed to be the ML codeword. The computational complexity of the proposed algorithm is the exponential order of the number of users, however, we can reduce the computational complexity of the algorithm for the gaussian multiple-access channel. Furthermore, we compare the performance of the proposed decoder with the decoder based on the sum-product algorithm.

Problems associated with document classification, an important application of text mining of text data, are focused on in this paper. There have been many models and algorithms proposed for text classification; one of these is a technique using a vector space model. In these methods, a digital document is represented as a point in the vector space which is constructed by morphological analysis and counting the frequency of each word in the document. In the vector space model, the documents can be classified using the distance measure between documents. However, there are specific characteristics in the vector space model for document classification. Firstly, it is not easy to automatically remove unnecessary words completely. The existence of unnecessary words is one of the characteristics of the text mining problems. Secondly, the dimensions of the word vector space are usually huge in comparison to the number of words appearing in a document. Although the frequencies of words appearing in a document could be small in many cases, many kinds of such words with small frequency can usually be used to classify the documents. In this paper, we evaluate the performance of document classification in the case where unnecessary words are included in the word set. Moreover, the performance of the distance measure between documents in a large dimensional word vector space is analyzed. From the asymptotic results about the distance measure, we can provide an explanation of the fact given in many experiments that classification using the empirical distance between documents calculated via the cosine measure is not particularly bad. It is also suggested that the KL-divergence is not useful for text mining problems.

F.P.Preparata et al. have proposed a fault diagnosis model to find all fault nodes in the multiprocessor system by using outcomes which each of nodes tests some other nodes. In this paper, for probabilistic diagnosis models, we show an efficient diagnosis algorithm to obtain a posteriori probability that each of nodes is faulty given the syndrome. Furthermore, we propose a method to analyze the diagnostic error probability of this algorithm.

In digital signal processing, the sampling theorem states that any real valued function ƒ can be reconstructed from a sequence of values of ƒ that are discretely sampled with a frequency at least twice as high as the maximum frequency of the spectrum of ƒ. This theorem can also be applied to functions over finite domain. Then, the range of frequencies of ƒ can be expressed in more detail by using a bounded set instead of the maximum frequency. A function whose range of frequencies is confined to a bounded set is referred to as bandlimited function. And a sampling theorem for bandlimited functions over Boolean domain has been obtained. Here, it is important to obtain a sampling theorem for bandlimited functions not only over Boolean domain (GF(q)ⁿ domain) but also over GF(q)ⁿ domain, where q is a prime power and GF(q) is Galois field of order q. For example, in experimental designs, although the model can be expressed as a linear combination of the Fourier basis functions and the levels of each factor can be represented by GF(q)ⁿ, the number of levels often take a value greater than two. However, the sampling theorem for bandlimited functions over GF(q)ⁿ domain has not been obtained. On the other hand, the sampling points are closely related to the codewords of a linear code. However, the relation between the parity check matrix of a linear code and any distinct error vectors has not been obtained, although it is necessary for understanding the meaning of the sampling theorem for bandlimited functions. In this paper, we generalize the sampling theorem for bandlimited functions over Boolean domain to a sampling theorem for bandlimited functions over GF(q)ⁿ domain. We also present a theorem for the relation between the parity check matrix of a linear code and any distinct error vectors. Lastly, we clarify the relation between the sampling theorem for functions over GF(q)ⁿ domain and linear codes.

A new method of constructing efficient codes on the basis of (u,u+v)construction is presented. We present a large class of optimum linear codes for small number of information symbols. Namely we present (3(2^m-1),m+1,3・2^m-2) code, (3(2^m-1)+1,m+1,3・2^m-1) code and (3(2^m-1)+2,m+1,3・2^m) code respectively. We show that these codes meet the bound of linear codes (m≦6) due to Brouwer and Verhoeff. It is strongly conjectured that, for m>6, our codes meet the bound for any code-length. We then present the (n,2,d) codes that meet the bound of any linear code of length n≦125. It is strongly conjectured that the proposed (n,2,d) codes meet the bound of optimum linear code of any code length. We also present the (n,3,d) code that meet the bound of any linear code of length n except n=8+7μ for n≦60. It is strongly conjectured that our (n,3,d) code meet the bound for any code length except m=8+7μ(μ=1,2,…). Finally we present several optimum linear codes for the number of information symbols k=4,5,6 and 7.

A lower bound on a probability of a burst erasure correction capability of regular low-density parity-check (LDPC) code ensemble under the belief-propagation decoding is investigated. This bound is based on the second moment method which expresses the upper bound on the minimum span for stopping sets of the regular LDPC code ensemble.

The combination of the low-density parity-check (LDPC) codes and the iterative decoding algorithm has high performance. It has been shown that Generalized LDPC (GLDPC) codes, which are constructed by conbining the ordinarily LDPC codes and linear block codes, are asymptotically good codes and achieve channel capacity almost nearly. Unfortunately encoding complexity of these codes is proportional to the square of the code length. In this paper, we propose a linear time encodable GLDPC codes by applying systemtic structure for its subcodes, and the stair-like structure of the extended Irregular Repeat Accumulate (eIRA) codes for its base code. We show by some numerical example that the number of encoding operations for the proposed GLDPC codes is less than those of the conventional ones. We also show by simulation results that the decoding performances of the proposed GLDPC codes are almost the same as those for the ordinarily codes.

The performance of a combination of the irregular low-density parity-check (LDPC) codes and the belief-propagation (BP) decoding algorithm strongly depends on a structure of their parity-check matrixes, and some of the codes exhibit bad performance. In this paper, we propose methods for constructing structured irregular LDPC codes which effectively facilitate for the BP decoding algorithm. We also develop methods for effective updating rules according to the bit node positions for the Shuffled BP decoding algorithm. We also show by simulation results that the decoding performances of the proposed irregular LDPC codes are better than those of the conventional ones.

We develope two methodology of constructing irregular low-density parity-check (LDPC) code for correcting a burst erasure. With high probability, the performance degradation is caused by producing small size of stopping sets of many degree two variable nodes. In this paper we present effective variable node reordering method to increase minimum span of stopping sets (MSSS) by using the special structure of degree two variable nodes of extended irregular repeat accumulate (eIRA) codes. The proposed two codes have also efficient encodable property since they are the class of eIRA codes. Furthermore we present construction method of irregular LR-LDPC which are known to have large MSSS. From the experimental results, we show that MSSS of the proposed codes are larger than the conventional ones.

In this paper, we propose a effective grouping method for the Group Shuffled BP decoding algorithm using the irregular LDPC codes according to the structure of a Tanner graph and the degree distribution of the codes which can accelerate the convergence speed and in result reduce the decoding delay. We show simulation results which indicate that the decoding performance of the proposed grouping method is better than those of the conventional grouping method.

The combination of the low-density parity-check (LDPC) code and the belif-propagation (BP) decoding algorithm exhibits a good decoding performance. Now error correction via LDPC code is applied for high speed wireless channel, wired channel and magnetic recording systems. To evaluate the correcting capability for burst erasure, analysis for the LDPC code ensemble has been employed. First, this analytical method evaluates the minimum span of the stopping set, and then, calculate the critical minimum span rate which expresses the rate of the correctable burst erasure for the code length. In this paper, we formulate more accurate critical minimum span rate by using minimum stopping set for the standard Tanner graph ensemble. We then apply it to evaluate the critical minimum span rate for the LR Tanner graph ensemble, which is a combined graph ensemble with a good correcting capability for burst erasure.

In this paper, we study interleaved codes with plural LDPC codes. Interleaved codes are one of efficient error correcting schemes for burst errors. Interleaver is utilized for utilized to disperse burst error. In contrast, interleaver is utilized for good estimation of the channel states for joint estimation-decoding in this study. We evaluate error correcting performance of the interleaved codes by computer simulation. Furthermore, we propose a simple analysis method for this interleaved codes based on density evolution method considered to the states of channels.

In this paper, a new pre-trained detection scheme for near-duplicated images is proposed. By using the assumption that the difference vectors between the original image and its near-duplicated image form altered or non-altered spaces independent of the original images. With pre-trained results, we regard features with large values in the difference vectors as the affected features by alteration. To avoid mis-detection, the proposed method codenses similar features together. The proposed method is valid for the original images without pre-training. We show by simulation results that the precision of the proposed method is larger than that of the conventional ones.

In this paper, a weak universal joint source-channel coding is considered. Weak universal means that a source probabilistic structure and a channel probabilistic structure are parametric and the set of parameter and its prior probability are known, but the parameter is unknown. Then we show a condition for the class of sources and channels that the error probability averaged by prior probability converges to 0.

Multiuser detection algorithms based on the belief propagation algorithm is presented. Previously, multiuser detection algorithm based on the belief propagation algorithm was proposed however, the algorithm is the approximation of the belief propagation due to the computational complexity. In this paper, belief propagation algorithm can be applied to the multiuser detection problems in the same way of the definition by converting the factor graph structure. The proposed algorithm is optimum when the factor graph, which form is determined by signature sequences, has no cycles.

Outliers are often included in statistical data. The statistics analysis result is influenced from outliers. Therefore, there are many researches for handling of outliers. Box modeled outliers using mixture distribution. There are many researches that aim parameter estimation or outlier detection about this model. In this paper, we treat prediction problem about this model. First, we present an optimal prediction method with reference to the Bayes criterion in this model. The computational complexity of this method grows exponentially. Next, we propose an approximation algorithm reducing the computational complexity using EM algorithm, and evaluate this algorithm through some simulations.

We propose an image retrieval method that extracts features using probability and Euler vectors of wavelet coefficient's bit-plane. Each bit-plane is associated with probabilities represents the frequency of "1" occurrence, and bit-plane of wavelet coefficients can be extracted from JPEG2000 coded images. On the other hand, Euler vectors generated from a bit-plane, it has a great affinity for JPEG2000. In this paper, we propose the image retrieval method using bit-planes and the Euler vector of JPEG2000 coded texture image. We show by simulation result with using Vis Tex data set that retrieval precision of the proposed method is better than that of the conventional one.

We propose an image retrieval method that extracts features using probability and Euler vectors of wavelet coefficient's bit-plane. Each bit-plane is associated with probabilities represents the frequency of "1" occurrence, and bit-plane of wavelet coefficients can be extracted from JPEG2000 coded images. On the other hand, Euler vectors generated from a bit-plane, it has a great affinity for JPEG2000. In this paper, we propose the image retrieval method using bit-planes and the Euler vector of JPEG2000 coded texture image. We show by simulation result with using Vis Tex data set that retrieval precision of the proposed method is better than that of the conventional one.

This paper generalizes parallel error correcting codes proposed by Ahlswede et al. over a new type of multiple access channel called parallel error channel. The generalized parallel error correcting codes can handle with more errors compared with the original ones. We show construction methods of independent and non-independent parallel error correcting codes and decoding methods. We derive some bounds about the size of respective parallel error correcting codes. The obtained results imply a single parallel error correcting code can be constructed by two or more kinds of error correcting codes with distinct error correcting capabilities.

In the previous result, we generalized the achievability of variable-length coding from two viewpoints. One is the definition of an overflow probability, and the other is the definition of an achievability. We defined the overflow probability as the probability of codeword length, not per symbol, is larger than η_n and we introduce the ε-achievability of variable-length codes that implies an existence of a code for the source under the condition that the overflow probability is smaller than or equal to ε. Then, we showed the condition of ε-achievability for some restricted sources given ε. In this paper, at first we define the ε-achievability for the parametric compound source. Then we show the sufficient condition for the ε-achievability.

By combining statistical analyses and information retrieval techniques, an efficient way for knowledge discovery from questionnaires is discussed. Since usual questionnaires include questions answered by a fixed format and those by a free format, it is important to introduce the methods by both data mining and text mining. The answers by the fixed format are called "items", and those by the free format, simply "texts". In this paper, using an algorithm for processing answers with both the items and the texts and that for extracting important sentences from texts combined with statistical techniques, a method for analyzing the questionnaires is established. The method is applied to a case of improvements for the quality of education by which the student questionnaire is executed to a class, and we obtain useful knowledge which leads to faculty development.

We have developed a public key certificate validation system considering the restrictions peculiar to the mobile environment, such as processing the speed and memory capacity of a cellular-phone terminal, and the network transmission speed. In this paper we derive a theoretical formula showing the performance of a validity check of the public key certificate of the conventional system and of the proposed system, and compare and examine a theoretical value in a mobile environment. Moreover, we evaluate the actual measurement that uses the server and cellular-phone terminal that we developed. We show that our proposed system based on the certificate validation server (CVS) system is better than the conventional system from the viewpoint of processing speed and transmission speed. (c) 2007 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.

Digital fingerprinting, a copyright protection technique for digital contents, is considered. Digital fingerprinting should deter collusion attacks, where several fingerprinted copies of the same content are mixed to disturb their fingerprints. In this paper, we consider the averaging attack, which has effect for multimedia fingerprinting. We propose new collusion-secure fingerprinting codes based on finite geometries (FGs) which increase the rate of conventional collusion-secure codes, while they guarantee to identify the same number of colluders. Due to the new FG-based fingerprinting codes, the system can deal with a larger number of users to distribute a digital content.

By combining statistical analyses and information retrieval techniques, an efficient way for knowledge discovery from questionnaires is discussed. Since usual questionnaires include questions answered by a fixed format and those by a free format, it is important to introduce the methods by both data mining and text mining. The answers by the fixed format are called "items", and those by the free format, simply "texts". In this paper, using an algorithm for processing answers with both the items and the texts and that for extracting important sentences from texts combined with statistical techniques, a method for analyzing the questionnaires is established. The method is applied to a case of improvements for the quality of education by which the student questionnaire is executed to a class, and we obtain useful knowledge which leads to faculty development.

In the present paper, we consider the automatic text categorization as a series of information processing and propose a new classification technique called the Frequency Ratio Accumulation Method (FRAM). This is a simple technique that calculates the sum of ratios of word frequency in each category. However, in FRAM, feature terms can be used without limit. Therefore, we propose the use of the character N-gram and the word N-gram as feature terms using the above-described property of FRAM. Next, we evaluate the proposed technique through a number of experiments. In these experiments, we classify newspaper articles from Japanese CD-Mainichi 2002 and English Reuters-21578 using the Naive Bayes method (baseline method) and the proposed method. As a result, we show that the classification accuracy of the proposed method is far better than that of the baseline method. Specifically, the classification accuracy of the proposed method is 87.3% for Japanese CD-Mainichi 2002 and 86.1% for English Reuters-21578. Thus, the proposed method has very high performance. Although the proposed method is a simple technique, it provides a new perspective and has a high potential and is language-independent Thus, the proposed method can be expected to be developed further in the future.

By combining statistical analyses and information retrieval techniques, an efficient way for knowledge discovery from questionnaires is discussed. Since usual questionnaires include questions answered by a fixed format and those by a free format, it is important to introduce the methods by both data mining and text mining. The answers by the fixed format are called "items", and those by the free format, simply "texts". In this paper, using an algorithm for processing answers with both the items and the texts and that for extracting important sentences from texts combined with statistical techniques, a method for analyzing the questionnaires is established. The method is applied to a case of improvements for the quality of education by which the student questionnaire is executed to a class, and we obtain useful knowledge which leads to faculty development.

Recently, a word-valued source has been proposed as a new class of information source models. A word-valued source is regarded as a source with a probability distribution over a word set. Although a word-valued source is a nonstationary source in general, it has been proved that an entropy rate of the source exists and the Asymptotic Equipartition Property (AEP) holds when the word set of the source is prefix-free. However, when the word set is not prefix-free (non-prefix-free), only an upper bound on the entropy density rate for an i.i.d. word-valued source has been derived so far. In this paper, we newly derive a lower bound on the entropy density rate for an i.i.d. word-valued source with a finite non-prefix-free word set. Then some numerical examples are given in order to investigate the behavior of the bounds.

We consider the reliability-based heuristic search methods for maximum likelihood decoding, which generate test error patterns (or, equivalently, candidate codewords) according to their heuristic values. Some studies have proposed methods for reducing the space complexity of these algorithms, which is crucially large for long block codes at medium to low signal to noise ratios of the channel. In this paper, we propose a new method for reducing the time complexity of generating candidate codewords by storing some already generated candidate codewords. Simulation results show that the increase of memory size is small.

We study a modification method for constructing low-density parity-check (LDPC) codes for solid burst erasures. Our proposed modification method is based on a column permutation technique for a parity-check matrix of the original LDPC codes. It can change the burst erasure correction capabilities without degradation in the performance over random erasure channels. We show by simulation results that the performance of codes permuted by our method are better than that of the original codes, especially with two or more solid burst erasures.

We propose a new fixed-rate error correction system with a feedback channel. In our system, the receiver transmits a list of positions of unreliable information bits based on the log a-posteriori probability ratios by outputs of a soft-output decoder to the transmitter. This method is just like that of the reliability-based hybrid ARQ scheme. To dynamically select an appropriate interleaving function with feedback information is a key feature of our system. By computer simulations, we show that the performance of a system with a feedback channel is improved by dynamically selecting an appropriate interleaving function.

Orthogonal Arrays (OAs) have been playing important roles in the field of experimental design. It has been known that OAs are closely related to error-correcting codes. Therefore, many OAs can be constructed from error-correcting codes. But these OAs are suitable for only cases that equal interaction effects can be assumed, for example, all two-factor interaction effects. Since these cases are rare in experimental design, we cannot say that OAs from error-correcting codes are practical. In this paper. we define OAs with unequal strength. In terms of our terminology. OAs from error-correcting codes are OAs with equal strength. We show that OAs with unequal strength are closer to practical OAs than OAs with equal strength. And we clarify the relation between OAs with unequal strength and unequal error-correcting codes. Finally, we propose some construction methods of OAs with unequal strength from unequal error-correcting codes.

We propose transformation of a parity-check matrix of any low-density parity-check code. A code with transformed parity-check matrix is an equivalent of a code with the original parity-check matrix. For the binary erasure channel, performance of a message-passing algorithm with a transformed parity-check matrix is better than that with the original matrix.

Tail biting trellis codes and block concatenated codes are discussed from random coding arguments. An error exponent and decoding complexity for tail biting random trellis codes are shown. We then propose a block concatenated code constructed by a tail biting trellis inner code and derive an error exponent and decoding complexity for the proposed code. The results obtained by the proposed code show that we can attain a larger error exponent at all rates except for low rates with the same decoding complexity compared with the original concatenated code. © 2006 Taylor &amp
Francis Group, LLC.

Orthogonal Arrays (OAs) have been playing important roles in the field of experimental design. It is well known that OAs are closely related to error-correcting codes, and many good OAs are constructed from error-correcting codes. And factorial effects that can be estimated with OAs corresponding to error-correcting codes are clarified. On the other hand, in our past researches, we focused on the relation between OAs and unequal error protection codes (UEP codes). OAs corresponding to UEP codes are called OAs with unequal strength (UOAs), where OAs corresponding to error-correcting codes are called OAs with equal strength. We showed that UOAs are more practical than OAs with equal strength, and proposed some construction methods of UOAs from UEP codes. But, in the researches, we only showed some examples of factorial effects that can be estimated with UOAs, so we had never clarified these factorial effects as well as OAs with equal strength. In this paper, we clarify factorial effects that can be estimated with UOAs.

Reliability Based Hybrid ARQ (RB-HARQ) is an ARQ scheme using the modified feedback. In the RB-HARQ, the receiver returns both NAK signal and unreliable bit indices if the received sequence is not acknowledged. Since the unreliable bit index is determined by the bitwise posterior probability, better approximation of that probability is crucial. Assuming the systematic codes, the proposed RB-HARQ scheme has two features for this approximation: (1) The sender retransmits newly encoded parity bits corresponding to the unreliable information bits; (2) The retransmitted parity bits as well as the initial received sequence are put all together to perform the message passing decoding.

Tail biting trellis codes and block concatenated codes are discussed from random coding arguments. An error exponent and decoding complexity for tail biting random trellis codes are shown. We then propose a block concatenated code constructed by a tail biting trellis inner code and derive an error exponent and decoding complexity for the proposed code. The results obtained by the proposed code show that we can attain a larger error exponent at all rates except for low rates with the same decoding complexity compared with the original concatenated code. © 2006 Taylor &amp
Francis Group, LLC.

This paper generalizes parallel error correcting codes proposed by Alshwede et al. over a type of multiple access channels called a parallel channel. The generalized parallel error correcting codes can handle with more errors compared with the original ones. We show construction methods of independent and non-independent parallel error correcting code and decoding methods. We derive some bounds about the size of respective parallel error correcting code.

The reliability-based heuristic search methods for maximum likelihood decoding (MLD) generate test error patterns (or, equivalently, candidate codewords) according to their heuristic values. Test error patterns are stored in lists and its space complexity is crucially large for MLD of long block codes. Based on the decoding algorithms both of Battail and Fang and of its generalized version suggested by Valembois and Fossorier, we propose a new method for reducing the space complexity of the heuristic search methods for MLD including the well-known decoding algorithm of Han et al. If the heuristic function satisfies a certain condition, the proposed method guarantees to reduce the space complexity of both the Battail-Fang and Han et al. decoding algorithms. Simulation results show the high efficiency of the proposed method.

Orthogonal arrays have been used in the field of experimental design. Hedayat and Sloane showed the relation between orthogonal arrays and error-correcting codes[1]. And they proposed some construction methods of both linear and nonlinear orthogonal arrays from error-correcting codes. On the other hand, the paper[5] defined unequal orthogonal arrays as new class. It showed that unequal orthogonal arrays are more applicable to experimental design. Furthermore, it showed the relation between unequal orthogonal arrays and unequal error-correcting codes[3], and proposed the construction method of unequal orthogonal arrays from unequal error-correcting codes. But orthogonal arrays from this construction method are all linear. In this paper, we clarify the relation between nonlinear unequal orthogonal arrays and codes. And we propose one of construction methods of nonlinear unequal orthogonal arrays from error-correcting codes.

The best-known algorithm for the decoding of low-density parity-check (LDPC) codes is the sum-product algorithm (SPA). The SPA is a message-passing algorithm on a graphical model called a factor graph (FG). The performance of the SPA depends on a structure of loops in a FG. Pearl showed that loops in a graphical model could be erased by the clustering method. This method clusters plural nodes into a single node. In this paper, we show several examples about a decoding on a FG to which the clustering method is applied. And we propose an efficient decoding algorithm for it. © 2005 IEEE.

The problem of universal codes with side information is investigated from Bayes criterion. We propose side information context tree models which are an extension of context tree models to sources with side information. Assuming a special class of the prior distributions for side information context tree models, we propose an efficient algorithm of Bayes code for the models. The asymptotic code length of the Bayes codes with side information is also investigated.

Universities are expected to keep faculty developments. By using knowledge acquisition methods such as the statistical techniques or the information retrieval methods, we propose the efficient methods for analyzing the students answers for questionnaires. First, a model, which shows the relationships between a students characteristic and the degree of satisfaction or their score, is proposed. Next, a set of questionnaires is analyzed using the statistical technique or the information retrieval method, and finally the class model is verified.

The best-known algorithm for the decoding of low-density parity-check (LDPC) codes is the sum-product algorithm (SPA). The SPA is a message-passing algorithm on a graphical model called a factor graph (FG). The performance of the SPA depends on a structure of loops in a FG. Pearl showed that loops in a graphical model could be erased by the clustering method. This method clusters plural nodes into a single node. In this paper, we show several examples about a decoding on a FG to which the clustering method is applied. And we propose an efficient decoding algorithm for it. © 2005 IEEE.

The problem of universal codes with side information is investigated from Bayes criterion. We propose side information context tree models which are an extension of context tree models to sources with side information. Assuming a special class of the prior distributions for side information context tree models, we propose an efficient algorithm of Bayes code for the models. The asymptotic code length of the Bayes codes with side information is also investigated.

Reliability-based maximum likelihood decoding (MLD) algorithms of linear block codes have been widely studied. These algorithms efficiently search the most likely codeword using the generator matrix whose most reliable and linearly independent k (dimension of the code) columns form the identity matrix. In this paper, conditions for omitting unnecessary metrics computation of candidate codewords are derived in reliability-based MLD algorithms. The proposed conditions utilize an order relation of binary vectors. A simple method for testing if the proposed conditions are satisfied is devised. The method for testing proposed conditions requires no real number operations and, consequently, the MLD algorithm employing this method reduces the number of real number operations, compared to known reliability-based MLD algorithms.

Reliability-based maximum likelihood decoding (MLD) algorithms of linear block codes have been widely studied. These algorithms efficiently search the most likely codeword using the generator matrix whose most reliable and linearly independent k (dimension of the code) columns form the identity matrix. In this paper, conditions for omitting unnecessary metrics computation of candidate codewords are derived in reliability-based MLD algorithms. The proposed conditions utilize an order relation of binary vectors. A simple method for testing if the proposed conditions are satisfied is devised. The method for testing proposed conditions requires no real number operations and, consequently, the MLD algorithm employing this method reduces the number of real number operations, compared to known reliability-based MLD algorithms.

In this paper we treat universal source coding when the parameters of the probabilistic model of source are known. Bayes code is one of the wellknowm universal codes. Bayes code has Bayes optimality in point of minimization of redundancy. Recently, many researches of Bayes code for nohstationary sources are done. Researches for sources with piecewise constant parameters are one of them. Each sections are visible to stationary sources. But these sources have abruptly changing parameters. And they are treated as nonstationary sources. But the Asymptotic character of mean redundancy for this source is not known. In this paper, we evaluate asymptotic mean redundancy of this source with the conditions of change number is not kown. And we show that Bayes code has universality with some condtions.

A key distribution scheme is a method to distribute off-line initial private pieces of information among a set of users, such that each group of a given size can compute a common key for secure conference. In this paper, we consider a ramp model for key distribution scheme. In the ramp model, the required resources can be reduced at the cost of a secerity degradation which depends on the size of users. We define a ramp model for key distribution scheme, show lower bounds on the size of the piece of a user's information and design a ramp model for key distribution scheme.

In this paper, we investigate the channel capacity in the case that we do not know the probabilistic model of the channel. First we show the channel capcity in the universal case. To show our main theorem we introduce the decoding scheme that minimizes the probability of error with respect to Bayes criteria.

Several reliability based code search algorithms for maximum likelihood decoding have been proposed. These algorithms search the most. likely codeword, using the most reliable information set. where the leftmost k (the dimension of code) columns of generator matrix are the most reliable and linearly independent. Especially, D. Gazelle and J. Snyders have proposed an efficient decoding algorithm and this algorithm requires small number of candidate codewords to find out the most likely codeword. In this paper, we propose new efficient methods for both generating candidate codewords and computing metrics of candidate codewords to obtain the most likely codeword at the decoder. The candidate codewords constructed by the proposed method are identical those in the decoding algorithm of Gazelle et al. Consequently, the proposed decoding algorithm reduces the time complexity in total; compared to the decoding algorithm of Gazelle et al. without the degradation in error performance.

Nishiara and Morita defined an i.i.d. word-valued source which is defined as a pair of an i.i.d. source with a countable alphabet and a function which transforms each symbol into a word over finite alphabet. They showed the asymptotic equipartition property (AEP) of the i.i.d. word-valued source and discussed the relation with source coding algorithm based on a string parsing approach. However, their model is restricted in the i.i.d. case and any universal code for a class of word-valued sources isn't discussed. In this paper, we generalize the i.i.d. word-valued source to the ergodic word-valued source which is defined by an ergodic source with a countable alphabet and a function from each symbol to a word. We show existence of entropy rate of the ergodic word-valued source and its formula. Moreover, we show the recurrence time theorem for the ergodic word-valued source with a finite alphabet. This result clarifies that Ziv-Lempel code (ZL77 code) is universal for the ergodic word-valued source.

Conventionally, decision tree generation algorithm has been used when performing prediction using the decision tree model. It can be considered that these are the model selection algorithm in the basis to which data was given. And, It predicts using the model chosen by the basis to which data was given. Therefore, it was very difficult to perform theoretical evaluation to the rate of a prediction error. In this work, we shows the prediction algorithm which makes the rate of an average prediction error the minimum. First, we re-formulize a decision tree model as a parametric stochastic model. The optimal prediction algorithm based on Bayes decision theory is shown using the model. Furthermore, the algorithm which calculates a prediction distribution efficiently by restraining a model class is described.

Recently, the compression algorithms based on the grammar have been proposed. These algorithms first generate the grammar and then apply the arithmetic code. H.Nakamura et al. proposed an algorithm which registeres the most frequent digram as a rule. While, M.Kanda et al. have proposed an algorithm which makes the grammar the optimum by calculating the ideal code length of the arithmetic code. In this paper, we propose a new algorithm that we generates the grammar for the most frequent N-gram as well as the most frequent digram.

The Ziv-Lempel(LZ)codes which are typical universal codes have been proposed modifing algorithms from not only theoretical but practical use. Recently, a word-valued source has been by proposed as a new class of source models, and its entropy rate is analyzed. The LZ78 codes for the word-valued source can be applied with two kinds of methods (i) inclemental parsing for each word (ii) inclemental parsing for each symbol. The performance compression of the LZ78 codes between these two kinds of methods is an interesting theme. In this paper, we show that the upper bound of average redundancy achieves O(1/log n) and consider about validity of LZ78 codes.

Ziv-Lempel (ZL) codes and Bayes codes are typical universal codes. An improved algorithm of the ZL code is widely used in compression software. On the other hand, practical use of Bayes codes is difficult due to the large amount of computation needed. However, a realizable algorithm in terms of computation effort has been constructed for the FSMX model group [9]. In this paper, an information source generating a sequence by word units is assumed as a model that can represent the probabilistic structure of actual data such as text data. The asymptotic compression performance of both codes is analyzed and evaluated for the information source class (information source for the block unit) with a constant (fixed) word length. As a result, it is found that Bayes code cannot directly be universal as a coding algorithm for symbol units. On the other hand, the ZL78 code can be directly universal. Also, a configuration method for the Bayes coding method is given for an information source with a block unit. (C) 2002 Wiley Periodicals, Inc.

In this paper, we consider the Bayesian approach for representation of a set of documents. In the field of representation of a set of documents, many previous models, such as the latent semantic analysis (LSA), the probabilistic latent semantic analysis (PLSA), the Semantic Aggregate Model (SAM), the Bayesian Latent Semantic Analysis (BLSA), and so on, were proposed. In this paper, we formulate the Bayes optimal solutions for estimation of parameters and selection of the dimension of the hidden latent class in these models and analyze it's asymptotic properties.

Based on techniques in information retrieval, we discuss methods for knowledge acquisition from documents composed of both fixed and free for-mats. The documents with the fixed format imply items such as those of selecting one from sentences, words, symbols, or numbers. While the documents with the free format are the usual texts. In this paper, starting with an item-document matrix and a term-document matrix used for the representation of a document set, we propose a new method for knowledge acquisition taking simultaneously into account of both fixed and free formats. A method based on the Probabilistic Latent Semantic Indexing (PLSI) model is used for clustering a set of documents. The proposed method is applied to a document set given by questionnaires of students which is taken for the purpose of faculty development. We show the effectiveness of the proposed method compared to the conventional method.

Sum-product algorithm, a well-known decoding algorithm of LDPC codes, is based on APP decoding to decode each received symbol. We usually assume that the parameters of channels are known, since a likelihood of channel noise is needed. When we consider applying it to practical channels, it is rarely that the parameters of channels are known. In this paper we propose a decoding algorithm combined with estimating unknown parameters of channels and we show that the bit error probability is as close as that of a decoding algorithm in which the parameters are known.

One of the most prominent blind channel equalizer is Godard algorithm, which many researchers have been devoted to recently. Since the Godard algorithm has local minima, which leads to inferior equalization performance, recently, K. Dogancay and R. A. Kennedy have reformulated the Godard algorithm so that equalizer parameters converge globally and we can perform more robust way of equalization. In this paper, the equalization algorithm, which the equalization parameter is proved to control bias of estimator under the certain noise model, is proposed. Furthermore, an efficient adaptive implementation of the algorithm is proposed.

We consider the kind of distributed cooperative systems defined as follows. First, a number of agents make observations of an information of correlative states. Second, the agent receives the partial information from other agent and sends the part of observed information to other agent. Finally, the agent utilizes observed information to the full for group decision. In this paper, we apply a multi-terminal systems to a distributed cooperative system and formulate a distributed cooperative problem based on Bayes decision theory. In tha case that loss function is the logarithmic loss function, we shall derive the Bayes rule that minimizes Bayes risk, and show that Bayes risk of the Bayes rule is represented as two types of the mutual information.

Statistical model selection is one of the most important problems in statistics, and many works have left essential results. The conventional information criteria for model selection, such as the Akaike information criterion (AIC), the Bayesian information criterion (BIC), and minimum description length (MDL) were derived from different viewpoints. Many other model selection criteria have also been reported from various viewpoints. On the other hand, if we specify the model class and assume prior probabilities, then we can acquire Bayes optimal model selection for a finite number of samples based on Bayes decision theory. Furthermore, we can assume the various loss function adapting the purpose of model selection for practical cases. In this paper, we analyze the asymptotic properties of stasistical model selection based on Bayes decision theory. At first, we formulate Bayes optimal solution based on Bayes decision theory. In this formulation, we introduce the general loss function for practical problems. Moreover, we analyze the upper limits of the error rate of the model selection.

In this paper, the generalized proof are shown for the coding theorem of [1]. Consequently, the further discussion is obtained.

We analyse the extended stochastic complexity (ESC) which has been proposed by K. Yamanishi. The ESC can be applied to learning algorithms for on-line prediction and batch-learning settings. Yamanishi derived the upper bound of ESC satisfying uniformly for all data sequences and that of the asymptotic expectation of ESC. However, Yamanishi concentrates mainly on the worst case performance and the lower bound has not been derived. In this paper, we show some interesting properties of ESC which are similar to Bayesian statistics: the Bayes rule and the asymptotic normality. We then derive the asymptotic formula of ESC in the meaning of almost sure and mean convergence within an error of o(1) using these properties.

In document retrieval system by keywords, an inverted file is often used. We propose a new method for compressing and decoding it. In the proposed method, it is compressed and decoded at two stages, and syndromes are used in compression. We represent an inverted file by a simple mathematical model and evaluate the system by two quantities. One is size of secondary memory where an inverted file and a decode tree are stored. Another is time complexity for decoding it. The VG bound is used to derive the two quantities. The numerical calculation shows trade-off relation between the two quantities. The time complexity decreases strikingly compared with increase in memory which shows the usefulness of the proposed method.

Posterior distributions conditioned by a data sequence converge to normal distributions under proper assumptions. This characteristic is called the asymptotic normality. In many previout works, convergence in probability or almost sure convergence, etc. have been considered. In this paper, we derive the asymptotic normality which holds uniformly for data sequences, without assuming the true distribution. On the other hand, the SC, an extension of the MDL criterion, is defined as a code length of the Bayes code, or the maximum likelihood code. The asymptotic formula of the SC was discussed in the meaning of uniform convergence. This is essential in a notion of the universal modeling. We show the asymptotic normality in the meaning of uniform convergence and derive the asymptotic formula of the SC which holds uniformly for data sequences directly from the uniform asymptotic normality.

The statistical model selection problems are discussed, and the criterion based on the Bayes decision theory for the detection of the true model is derived. We propose a new Bayesian model selection scheme, which can detect the change points of the parameter of the information source and also estimate each unknown parameter. In this paper, we formulate the Bayes optimal solution of the change detection problem, and analyze its property of the consistency. (C) 1999 Elsevier Science B.V. All rights reserved.

There are two main learning paradigms in machine learning.One is leaning from examples and the other is learning from queries. It is necessary in learning from queries to use good query strategy because the probability that the true hypothesis is learned depends on it. However, from the computational learning theory it is important to judge whether it can learn or cannot, and it cannot be decided which query strategy is good. In this paper, we formulate learning from queries by the decision theory and propose a method of evaluating query strategy, where under the conditon that one of learning criteria (success principle, efficiency principle) is restricted, the other is minimized. Furthermore, we p ropose a new lower bound required for the branch-and-bound algorithm which gets efficiently the optimal query strategy. This paper is an effective study from the viewpoint of guaranteeing that the computational work for an oracle is made the smallest in learning.

LZ78 code is one of the most effective universal code which leads to many improved coding methods. However, even if we want to decode only the partial sequence then we must decode all of the sequence from the initial. In order to partially decode, the improved method is needed. For the LZ77 code, K.Iwata et al. proposed the improved partially decodable code. In this paper, we propose the new partially decodable code based on LZ78 code.

Y.Steinberg and M.Gutman proposed the lossy compression algorithm based on the string matching algorithm used in LZ77 code. Furthermore, Obata et.al proposed an improved algorithm which is efficient for finite i.i.d. sequence. This algorithm is a method which generates a new codeword nearby selected sequences. But this algorithm is not effective for the sources with finite memory. Then, we propose an efficient algorithm for Markov Source and show the characteristics of the algorithm from the simulation experiments.

This paper presents a new architecture for multiple-input signature analyzers. The proposed signature analyzer with Hδ inputs is designed by parallelizing a GLFSR(δ, m), where δ is the number of input signals and m is the number of stages in the feedback shift register. The GLFSR, developed by Pradhan and Gupta, is a general framework for representing LFSR-based signature analyzers. The parallelization technique described in this paper can be applied to any kind of GLFSR signature analyzer, e. g., SISRs, MISRs, multiple MISRs and MLFSRs. It is shown that a proposed signature analyzer with Hδ inputs requires less complex hardware than either single GLFSR(Hδ, m)s or a parallel construction of the H original GLFSR(δ, m)s. It is also shown that the proposed signature analyzer, while requiring simpler hardware, has comparable aliasing probability with analyzers using conventional GLFSRs for some CUT error models of the same test response length and test time. The proposed technique would be practical for testing CUTs with a large number of output sequences, since the test circuit occupies a smaller area on the LSI chip than the conventional multiple-input signature analyzers of comparable aliasing probability.

In this paper, prediction using side information is studied. This problem has been investigated as predictive inference in the field of Bayesian theory and as on-line learning in the field of learning theory. The prediction problem under consideration is to predict-log p(y mid x)using given side information x.It is regarded as universal coding given side information. The Bayes risk of the Bayes predictive inference and the maxmini risk correspond to the mutual information of a certain multi-terminal channel and its capacity, respectively. In a certain prediction model, I.e., a multi-terminal channel, the Bayes optimum prediction is derived. Moreover, the asymptotic forms of Bayes risk and maximin risk are shown. This maximin risk is regarded as a difficulty measure of predictive inference and learning.

In this paper, we shall discuss on the statistical model selection problems. The purpose of AIC is different from those of BIC and MDL, and AIC has not consistency although BIC and MDL have. Here a question arises. Does AIC have not consistency for the purpose? On the other hand, if we specify the model class, then we can formulate the Bayes optimal model selection for finite samples based on Bayes decision theory. In this paper, we show that model selection based on Bayes decision theory has consistency independent of whether the purpose is prediction of future observation or detection of a true model.

Concatenated codes have many remarkable properties from both the theoretical and practical viewpoints. The minimum distance of a concatenated code is at least the product of the minimum distances of an outer code and an inner code. In this paper, we shall examine some cases that the minimum distance of concatenated codes is beyond the lower bound and get the tighter bound or the true minimum distance of concatenated codes by using the complete weight enumerator of the outer code and the Hamming weight enumerator of the inner code. Furthermore we propose a new decoding method based on Reddy-Robinson algorithm by using the decoding method beyond the BCH bound.

In trellis coding for data compression, it is difficult to search all codes, and a code is selected by the local search method. In the meantime, the property of the optimal code is shown in Rate-Distortion Theory. In this paper, we propose an algorithm which selects a good code by using the property to avoid selecting a local optimal code as much as possible. To evaluate the algorithm using the property, first we investigate the property of the optimal code for small constraint length by the simulation. Next we compare the result by the algorithm using the property for that by the algorithm not using the property by the simulation.

In this paper, we analyze the asymptotic properties of the stasistical model selection based on Bayes decision theory. At first, we shall formulate the change detection problem based on Bayes decision theory. In this formulation, we introduce the general loss function for the practical problems. Moreover, we analyze the upper bound of the error rate of the model selection.

In the PAC learning model and the U-learning model, the learning algorithm runs independent of the prior distribution. On the other hand, the Bayes algorithm works utilized the prior distribution, and it is Bayes optimal. Haussler have analyzed the sample complexity on the Bayes algorithm. But the algorithm usually requires a large amount of the time complexity. In this paper, we discuss on the complexity of the Bayes algorithm focusing on not only the sample complexity but also the time complexity. In this new learning model, the complexity depends on both the concept class and the family of priors. On the basis of both complexities, we propose a new concept called Bayesian learnability. Moreover we show the learnability of typical concept classes, and the properties of the Bayesian learnability.

A new soft-decision maximum-likelihood decoding algorithm is proposed, which generates a set of candidate codewords using hard-decision bounded-distance decoding. BS improving the generating method of input vectors for the bounded-distance decoding due to Kaneko et al., decoding time complexity is reduced without degradation of performance, The space complexity is dependent on the hounded-distance decoding.

The Bayes code is the Bayes optimal solution based on Bayes decision theory. This is the method which uses mixture of all models in model class for coding function. B.S.Clarke and A.R.Barron analyzed asymptotic mean codelength of the Bayes code and showed that Jaffreys' prior is the asymptotically least favorable under entropy risk for i.i.d sources. This paper consists of two parts. At first, we show the asymptotic codelengths of the Bayes codes for individual sequences for the parametric model class. The main condition required here for the parameter space is that the posterior probability of parameter has asymptotic normality. Generally speaking, the asymptotic notmality of posterior distribution distribution holds for other than i.i.d. sources. Secondly, we shall prove that Clarke and Barron's asymptotics of the Bayes code is satisfied for more general model classes than i.i.d. sources. The main conditions required here is the Central Limit Theorem for the maximum likelihood estimates. Since the target of source coding is not usually i.i.d. source, the extension is this paper is effective.

Recently, the high-speed data transmission techniques that have been developed for communication systems have in turn necessitated the implementation of high-speed error correction circuits. Parallel processing has been found to be an effective method of speeding up operations, since the maximum achievable clock frequency is generally bounded by the physical constraints of the circuit. This paper presents a parallel encoder and decoder architecture which can be applied to both binary and nonbinary cyclic codes. The architecture allows H symbols to be processed in parallel, where H is an arbitrary integer, although its hardware complexity is not proportional to the number of parallel symbols H. As an example, we investigate hardware complexity for a Reed-Solomon code and a binary BCH code. It is shown that both the hardware complexity and the delay for a parallel circuit is much less than that with the parallel operation of H conventional circuits. Although the only problem with this parallel architecture is that the encoder's critical path length increases with H, the proposed architecture is more efficient than a setup using H conventional circuits for high data rate applications. It is also suggested that a parallel Reed-Solomon encoder and decoder, which can keep up with optical transmission rates, i.e., several giga bits/sec, could be implemented on one LSI chip using current CMOS technology.

Recently, Bayes Coding is one of the most active subject in the research of universal coding. Bayes Coding is constructed based on statistic decision theory, and it determines the coding probability in the point of minimization of mean redundancy. Though, in the Bayes Coding algorithm for FSMX sources, the coding probability is calculated using a context tree it needs enormous memories. In this paper, first we show the lower bound of mean code length in limited memories. Secondly, we propose Bayes Coding algorithm under limited memories, and investigate its performance.

Ziv-Lempel algorithm and Bayes algorithm are wellknowm as universal code. In recent years it is obvious that Ziv-Lempel algorithm supposes the probability distribution of information source implicitly. The relation between ZL code and Bayes code has been discussed from some three points of view[2]. From previous reseaches it is known that Bayes code surpasses ZL code concerning compresion rate. On the other hand ZL code surpasses Bayes code concerning complexity. So in this paper, from the three points of view, we consider the relation between ZL code and Bayes code by introducing the experimental algorithm.

The minimum description length (MDL) principle which was proposed by J.Rissanen has been studied not only in the universal source coding but in the areas on data analysis, learning theory and the statistical model selection. The MDL is the method to minimize the total description length of the data and that of a probabilistic model, and is closely related to Bayesian statistics. This is because the MDL assumes implicitly the prior distribution. On the other hand, the Bayes coding is the method which uses mixture of all models in model class for coding function. The Bayes code is obtained by the Bayes optimal solution for the code length. Therefore, if we can assume the same prior distribution in both coding, it is clear that the Bayes code is superior to the code based on MDL principle. In this paper, we shall analysis the difference the codelengths between the MDL and the Bayes codes and show that the Bayes code is superior to the code based on the MDL principle.

Several kinds of LFSR-based signature analyzers have been proposed for LSI built-in self test. MLFSR, which has been proposed for multiple output CUT by Pradhan et al., has the possibility to achieve the better aliasing probability than other schemes such as the multiple MISR scheme with comparable hardware complexity. The only problem with this scheme is that the hardware complexity becomes larger than propotionally as δ increases, where δ is the number of parallel signals inputted into MLFSR, and so MLFSR is not adequate for testing CUTs with large number of output signals. In this report, we propose a parallel architecture for signature circuits applicable to such CUTs. This architecture allows Hδ bits to be processed in parallel, where H can be chosen as an arbitrary integer. It is shown that the complexity for the parallel circuit, with Hδ input, signals is much smaller than that for a parallel opereation of H converntional circuits with δinput signals.

This paper proposes a new formulation which minimizes the differential entropy for an optimal control problem. The conventional criterion of the optimal regulator control is a standard quadratic cost function E[M{x(t)}(2) + N{u(t)}(2)], where x(t) is a state variable, u(t) is an input value, and M and N are positive weights. However, increasing the number of the variables of the system it is complex to find the solution of the optimal regulator control. Therefore, the simplicity of the solution is required. In contrast to the optimal regulator control, we propose the minimum entropy control which minimizes a differential entropy of the weighted sum of x(t) and u(t). This solution is derived on the assumptions that the linear control and x(t)u(t) less than or equal to 0 are satisfied. As the result, the formula of the minimum entropy control is very simple and clear. This result will be useful for the further work with multi variables of simple control formulation.

In this paper, a parallel encoder and decoder architecture for cyclic codes is presented. This architecture can decrease encoding and decoding time 1/H(H > 1) compared to conventional codec, where H is the number of symbols processed in parallel. As an example, we investigate hardware complexity for a (255,251) Reed-Solomon code over GF(2^8). It is shown that hardware complexity for a set of parallel encoder and decoder is much smaller than that for a parallel operation of H conventional sets.

In this paper, we present the results of analyses on superimposed codes constructed based on a probabilistic manner. The superimposed-codes have a feature which is superior to the conventional one not only in the code rates but also in the decoding complexity. The results of analyses show that the codes with larger rates by a factor of approximately 3 compared with the conventional one, exist under the same value of the probability of decoding error and the same level of the decoding complexity. Finally the table of the efficient codes parameter is given.

In this paper, we propose a new algorithm in the field of markov decision processes with unknown transition probabilities. The decision algorithms are evaluated by only a criterion of convergence or rewards in previous researches. The proposed algorithm is considered from both criteria. The effectiveness of our algorithm against previous algorithm is shown by some simulations.

The most useful method to get some randomness in computational simulation is to use psuedo-random numbers. This paper gives a new approach, using Bayes Coding Algorithm. The proposed method tests some traditional tests at once. This paper comes from the Information Theory, likes a test using Lemple-Ziv algorithm. But, we test not only redundancy. Our test, using Bayes Coding Algorithm, can also analize the probability of each sequence.

Among the universal coding problems, Bayes Coding is one of the most active subject in the research field of recent data compaction. The Bayes Coding Algorithms for FSMX sources proposed in the recent researches use a fixed-depth context tree. In this paper, we study the compression ratio of the newly proposed algorithm which uses a variable-depth context tree, and investigate the difference of redundancy caused by prior probability distribution of prameters.

The optimal universal code for FSMX sources with respect to Bayes redundancy criterion is deduced under the condition that the model, the probabilistic parameters and the initial state are unknown. The efficient algorithm of the optimal code is also proposed by using a context tree. Although the context tree weighting(CTW) algorithm needs the context in the initial situation and can not treat the infinite depth context tree, this algorithm is free from these problems. The algorithm is not only Bayes optimal for FSMX sources but also asymptotically optimal for a stationary ergodic sources. Moreover the algorithm is regarded as a generalization of the Ziv-Lempel algorithm.

Allocation methods for Cartesian product files on multiple disks by using linear error-correcting codes are proposed.This allocation methods can be apply to queries in which the characteristic of each attribute is not even.The structure of Reed- Solomon codes over GF(p^m),which give the strictly optimal allocation when all possible partial match queries are equiprobable,and the mapping by the basis for GF(p^m)over the subfields is used.As a result,a file is constructed by records which has the attributes in which the domain is partitioned by different number.The properties of this method are described.

This paper discusses an inductive learning method in probabilistic model which is applied to diagnostic system.In this system empirical knowledge is learned from given data as the probability distribution of the failures,and tests are selected according to this knowledge.We use presumption tree to represent the probability distribution,and adopt the MDL principle to select a presumption tree as themost approximate one.But,since the probability distribution becomes complicated,complexity of model selection increases exponentially with number of attributes So it requires an effcient search technique. In this paper,we propose a new effcient algorithm to search the optimal presumption tree which minimize it′s description length.An d we show that our algorithm gives a supplement of the weakness of the conventional algorithm.

The technique which derives a general rule to explain the given examples called an inductive learning.In this paper,we discuss on the decision tree as a method for the expressing the knowledge obtained by learning though there are various forms such as the formal.language,the predicate logical expression,and PROLOGprogram. The ID3 is proposed by J.R.Quinlan as a method for constructing the decision t e.However the correlation of two or more attributes can not take into account.because only one attribute paid attention in each step of the generation process of the tree.As a result,it is not guaranteed that the average number of questions using the generated rule is minimized.We propose a new algorithm which enables to consider the relationship between two or more attributes in each step of the generation process of the tree.And it is shown a more efficient decision tree can be constructed.

The problem of learning a concept from examples in the model introduced by Valiant is discussed.According to the traditional ways of thinking,it is assumed that the learnability is independent of theoccurence probability qf instance.By utilizing this probability,we propose the metric as a new measure to determine the complexity,of hypothesis space.The metric measures the hardness of discrimination between hypotheses. Furthermore,we obtain the average metric dependent on prior information.This metric is the measure of complexity for hypothesis space in the average.Similarly in the worst case,we obtain the minimum metric. We make clear the relationship between these measures and the Vapnik-Chervonenkis(VC)dimension.Finally,we show the upper bound on sample complexity utilizing the metric.This results can be applied in the discussion on the learnability of the class with an infinite VC dimension.

A decoding algorithm which executes maximum likelihood decoding(MLD)by using bounded distance decoding is known as a soft- decision decoding.However a problem is to reduce complexity of bounded distance decoding to execute MLD.On the other hand,GMD decoding is well known as an apfioximate of MLD.Recently GMD decoding in which an algebraic decoding is executed only once has been developed.In this paper we propose efficient MLD algorithm by using GMD decoding for several times.We also show that complexity for calculating syrifirome can be reduced when we use algebraic decoding several times required for soft-decision decoding. Moreover we provide an efficient algorithm to generate the sequences to be decoded to a maximum likelihood Cpdeword more efficiently.We show that the decoding complexity can be considerably reduced in the computer simulations.

In the research area on knowledge information processing, knowledge acquisition from experts becomes an important problem to construct efficient expert systems.On the other hand,the method for learning rules from examples is also important.Using rules given from a finite set examples,we should represent uncertain knowledge with range of certain factors.If we can combine knowledge given from experts with knowledge given from examples,we can establish more reliable knowledge.In this paper,we propose a new method that update the knowledge based on experts by using examples,provided that additional examples have noises in the observation.

A fundamental and total model for deductive and inductive inference is proposed from the view points of decision theory and information theory.Deductive and inductive inference are regarded as the decision problems in the proposed fundamental model.The inference problems of induction and deduction are represented by the decision functions and the loss functions.The optimal procedures of the inference problems are given by decision theory. The average risks of the optimal procedures are evaluated by using information theory.

On ARQ schemes,using VA(Viterbi algorithm)and cumlating the rejected sequences to make use to the powerful decision for the next repeated,it is one of approaches that eliminating only the non-reliable segments from maximum likelihood path over the trellis block,chosing by the likelihood ratio testing at the each two pathes unmerged.Then,the decoder selects the only rebable segments form each blocks repeat requested.On these cases,the procedure of VA with some earsure option is not the single stage testing like Yamamoto￡1!′s scheme,but the sequntal tesing problem s.In this paper,we disccus the sequential testing,espacially using VA with repeat request the rejected sequences cumulating. ￡1!H.Yamamoto and K.Itoh,″ Vitebi decoding algorithm for convol utional codes with repeat request″ IEEE Trans.Inf.Theory,vol.IT-26 ,pp540-547(Sep.1980).

We discuss the method for representing uncertain knowledge information and also on a reasoning system that guarantees a given reliability based on information theory and probability theory. In this paper, we propose a new reasoning system which consists of inductive and deductive inferences, by using a knowledge representation method with a range of certainty factors. In inductive inference, a new atom is computed from the observed data or facts, together with the upperbound and lowerbound between which its probability must fall. Also in deductive inference, which includes negation, conjunction, disjunction, chain and modus ponens, a new atom is deduced with a range of certainty factors computed from the results of inductive inference. Properties and behaviors of the system are clarified. It can be concluded that the new reasoning system is effective of conventional expert systems.

The Plotkin′s construction methods,or ds are known to be an effective for obtaining efficient codes by using previously known codes.The present authors have proposed the new codes C constructed on the basis of the Plotkin′s construction and their decoding algorithm. In this paper,we discuss on exponential error bounds for the codes C from the random coding arguments.We show that the codes C are superior compared to the conventional single stage codes from the view-point of error exponents for rates below capacity. Throughout this paper,channels are assumed to be the binary input additive white Gaussian noise channels with the signal to noise ratio p.

In practical applications of coding theory,e.g.,Signature analysis,ARQ system,etc.,analyses on the probability of undetected error for binary linear block codes plays an improtant part.It has been known that the probability of undetected error for the binary linear block codes having a symmetric weight distribution converges exponentially to zero with code length n.In this paper, we discuss about iterated codes having a symmetric weight distribution used as error detecting codes.It is shown that the probability of undetected error for the iterated codes also converges exponentially to zero with code length n,and the complexity of the operation to detecte an error for the iterated codes is simpler than that for the ordinary codes.

The ARQ is an error control scheme such that,if the receiver decides that the received information is not reliable,he can request the same information repeated.Some kinds of ARQ schemes do not disacard non-reliable informaion,but cumulating it to make use of powerful decision if the next received sequence should be decoded or not.This idea can be considered as a sequential decision with the cumulating rejected information.The well-Known Wald′s sequntial ratio test,which can make most powerful decision if sample size is variable,have the same principle like these kinds of ARQ.In this paper,we try to evaluate the ARQ cumulating rejected information with the random coding argument like Forney￡7 !′s as possible.So we study the error exponent of decoding the 2nd inform under the condision of the 1st inform is rejected.

Autoassociative recall is the first model that was realized as an associative recall in neural networks.Although the capability has been studied,it is not enough to analize the dynamics in the recall process of the reasonable patterns.In this paper we discuss the behavior of the wight matrix in Autoassociative Recall,and suggest some pro cedures to avoid the situation caused by the weight matrix that makes the recall impossi ble.

Information networks can be represented by graphs in which the set of vertices corresponds to the nodes in the networks and that of the edges corresponds to the links.Based on such a model,the efficient construction of information networks,for which the transmisson delay is short and the realiability is high,has been studied from graph theorical approach.This problem is to construct a network with high realiability(node connectivity k)and quasiminimal maximum transmission delay(diameter),when the number of nodes(vertices n)and that of the neighboring nodes(degrees k) are given.Original studies have been devoted to obtain high realiability sacrificing the long delay.In this paper,we propose a new method for constructing of information networks for which the delay is shorter in a limitation and show the effectiveness of the proposed method.

Shapiro′s model inference system can infer the only model which can represent with first order language given in advance.But at the view point of concept learning,it is not natural situation to set the model which includes theoretical terms.It seems that creating or discovering theoretical terms is the essential probrem in machine learning,but it′s very hard.Although some methods of cr eating theoretical terms are proposed,they have no guarantee to identify a concept in the limit.In this paper,we extend the Shapiro′s system and show that it is possible to identify a concep t in the limit at the system which creates theoretical terms.

　今年度目標とした各項目に対し、下記の結果を得た。１．データマイニング　遺伝的アルゴリズムとk-means法を用いたクラスタリング技法、属性間の関連を考慮した帰納推論について、それぞれ新しいアルゴリズムの提案と性能の評価を行った。いずれも日本経営工学会春季・秋季発表大会で報告した。また、大規模データベースにおける多値属性を考慮した相関ルール抽出法について検討し、従来２値の場合しか処理できなかったものを拡張した。結果は人工知能学会で発表した。２．分散直積ファイルのディスク配置問題　符号理論を応用した効率のよい配置法について検討した。Reed-Solomon符号を用いるとエラスティック（ファイルの数が大きくなる程、わずかな平均アクセス時間の増大を許容すれば大きくディスクの数を減らすことが可能）であることを示した。国際会議で報告した。３．情報検索システム　情報検索システムへの符号化技術の応用としては進展がなかった。近接分野の取り組みとして、これに近い視点からテキストマイニングについて取り上げた。新聞記事を対象にクラスラリングを効率よく行う方法、日本語のキーワード検索において効率よく合成語を見つけ出す方法について検討している。４．その他　符号理論のプロパーなテーマを取り上げた。Ａ＊アルゴリズムを用いて計算量を押えながら最ゆう復号を実行する方法、ＢＣＨたたみこみ符号の新しい構成法を提案し、電子情報通信学会に報告した。前者は論文にまとめ信学会に投稿した。

　本研究は符号化技術について（1）データ圧縮を行う情報源符号化（2）誤り訂正を行う通信路符号化について基礎的な考察と同時に情報システムの応用を図ったものである。（1）情報源符号化　（a）基礎的考察……マルコフ情報源に対し誤り伝播をおさえることができる符号化と、部分的に復号可能なZL符号の拡張について考察した　（b）応用……統計的モデル推定問題はユニバーサル情報源符号化の情報源モデルの推定と同じように考えることができる。ここでは、パラメータが一時間と共に変わるようなモデルが入力されたときのパラメータ変化量を推定する方法と、ベイズ符号の近似アルゴリズムを用いて木構造のモデル族の予測方法について考察した。（２）通信路符号化　（a）基礎的考察……2元BCH符号についてわずかな計算量の増大でBCH限界を越える復号法を示し、これを用いて近似最尤復号への適用を図った。また、たたみ込み符号を用いたARQ方式についてリスト復号を行うことにより従来の復号誤り確率，を低減する方法について考察した。　（b）情報検索における転置ファイルの圧縮について2段階符号化を行うことにより復号・検索が容易になる方法を示し評価した。また並列化したBCH符号化によりLSIの組込みテスト回路の性能を向上させる方式を示した。

本研究は符号化技術について符号理論、情報理論から考察しその応用を図ったものである。対象とする符号化技術は大別にデータ圧縮を行う情報源符号化と誤り訂正を行う通信路符号化である。　通信路符号化については通信符号の真の距離が増加する場合の条件とその復号法を与えている。また、ＢＣＨ符号の最小距離を越える復号法を示し軟判出復号法への応用を図っている。不均一誤り訂正符号についても軟判定復号法を示し誤り確立の低減する方法を明らかにしている。　情報源符号化についてはTunstall符号やＦＧ符号の改良を行い圧縮効率をなるだけ低下させないで途中からの復号を可能とする方法、歪を許した圧縮のアルゴリズムを明らかにし実データに応用したときの評価を行っている。また情報源符号化の応用として、木構造をもつデデuの学習アルゴリズムに用い計算量低減を図っている。研究成果の発表1997年５月"On the minimum distance of binary concalenaled codes" IFICE Trons. E80-A, May 1997. pp.922-923.“An improvement of soft-decision maximum likelihood decoding algorizhm using hand-decision bounded distance decoding,”IEEE Trons. IT-43, July 1997. PP. 1314-1319“Berlekamp-Massey アルゴリズムを用いたＢＣＨ限界を越える復号法の計算量について”、信号論、J80-A、pp. 1554-1558, 1997, 9.1997年11月“On the minimum distance of concatenated cosse and decoding method up to the true minimum distance”, IEICE, Tromo. E80-A, pp. 2111-2116 Nov. 1997.

　本研究は符号化に関する基礎的・応用的研究に関するものである。基礎的研究としては、最尤復号あるいは近似的最尤復号を実行するアルゴリズムの提案とその評価に関するものがある。最尤復号は復号誤り確率を最小にするが計算量は大きい。これを近似的に実行すると、どの程度の符号誤り確率の変化になるかを評価している。また、連接符号の最小距離の下界を改良する符号化の条件とその復号法を明らかにした。GMD復号法と拡張した方法により、実際の最小距離によりきまる誤り訂正可能個数までの訂正ができることを示した。この他、符号化を用いた判定帰還方式について棄却した受信条列を有効に利用し信頼度を向上させる方式 およびViterbi復号法を用いたたたみ込み符号の固定遅延復号について提案・評価結果を明らかにした。いずれも誤り指数を導出し、同時にシュミレーションによりその動作の確認を行った。　応用的研究としては、高速化を目的とした巡回符号の符号器・復号器の並列化方式の提案とその解析を行った。この構成法を用いてFTCにおけるLSIのビルトインテストに応用する場合を考察し、回路規模を小さくできることを明らかにした。　この他、情報源符号化において受信系例の途中から復号する方式、歪のある情報圧縮における代表元を記憶するリスト作成のアルゴリズムを改良する方式などを提案し、それぞれの性格を評価した。情報源符号化のアルゴリズムと性質を利用した知識情報処理における帰納推論への応用を図った。知識表現として決定木を用いるとき、マルコフモデルを推定しモデル選択を行う問題に応用し有効性を確認した。

本研究は情報理論・符号理論に共通の符号化技術に関するもので基礎的研究と応用的研究に分けられる。前者は誤り訂正で実行する新しいアルゴリズムの提案とその評価に関するものであり，後者は主として誤り検出符号のフォールトトレラントシステムの応用である。（1）基礎的研究 誤り訂正を実行する符号アルゴリズムを扱っている。まず，バースト誤りが生起するとき，線形巡回符号の性質を用いて受信系列をずらしたものと重量することにより，誤りを打ち消し合い比較的簡単なアルゴリズムで強力な能力を引き出せることを示した。また，最小距離が偶数の連接符号において，内部符号の復号結果を利用することにより従来検出に止まっていた符号法を改良できることを示した。さらに，線形ブロック符号において，最尤復号をトレリス構造を用いて効率良く実行できることを示した。この他，情報源符号化についても考察している。Ziv-Lempel符号の符号化アルゴリズムを逆にたどることにより，実行しているパラメータ推定の方法を解明した。また，歪のあるデータ圧縮に歪のないデータ圧縮のアルゴリズムを適用して，従来よりさらに圧縮率を上げることが可能であることを示した。（2）応用的研究 LSIなどのBuilt In Self Testでは回路に組み込まれたテスト回路により誤りを検出する。このとき，シグネチャとよぶデータ圧縮技術が用いられる。並列化可能な誤り検出符号の符号器構成を与えることによりテストが高速化できることを示した。また，符号化技術の知識情報処理への応用として，不確実な知識に新しい観測データを加え高信頼化を図るのに有効な判定・評価方法や，パターン認識などに用いられる事後確率の計算法を効率良く実行できる方法を示した。