Error-correcting output coding (ECOC) is a method for constructing a multi-valued classifier using a combination of given binary classifiers. ECOC can estimate the correct category by other binary classifiers even if the output of some binary classifiers is incorrect based on the framework of the coding theory. The code word table representing the combination of these binary classifiers is important in ECOC. ECOC is known to perform well experimentally on real data. However, the complexity of the classification problem makes it difficult to analyze the classification performance in detail. For this reason, theoretical analysis of ECOC has not been conducted. In this study, if a binary classifier outputs the estimated posterior probability with errors, then this binary classifier is said to be noisy. In contrast, if a binary classifier outputs the true posterior probability, then this binary classifier is said to be noiseless. For a theoretical analysis of ECOC, we discuss the optimality for the code word table with noiseless binary classifiers and the error rate for one with noisy binary classifiers. This evaluation result shows that the Hamming distance of the code word table is an important indicator.

与えられた二値判分類器を組み合わせて用いる多値分類器の構成法の1つに，符号理論の枠組みを導入した誤り訂正符号に基づく多値分類法（Error-Correcting Output Coding：ECOC法）がある．この手法が実データに対して良い性能を示すことは実験的に知られているが，ECOC法に対する分類精度について，理論的な最適性については明らかになっていない．そこで本研究では最大事後確率分類を可能とする二値分類器を仮定した場合，ECOC法が最適な多値分類法になる十分条件を示す．この結果，同様の仮定のもとでn-vs-allおよびExhaustive符号が最適な多値分類法になることが示せる．これは種々のECOC法に対する最適性の議論の方向性の1つを示唆している．

The development in information technology has resulted in more diverse data characteristics and a larger data scale. Therefore, pattern recognition techniques have received significant interest in various fields. In this study, we focus on a pattern recognition technique based on distance metric learning, which is known as the learning method in metric matrix under an arbitrary constraint from the training data. This method can acquire the distance structure, which takes account of the statistical characteristics of the training data. Most distance metric learning methods estimate the metric matrix from pairs of training data. One of the problem of the distance metric learning is that the computational complexity for prediction (i. e. distance calculation) is relatively high especially when the dimension of input data becomes large. To calculate the distance effectively, we propose the way to derive low rank metric matrix with nuclear norm regularization. When solving the optimization problem, we use the alternating direction method of multiplier and proximal gradient. To verify the effectiveness of our proposed method from the viewpoint of classification accuracy and rank reduction, simulation experiments using benchmark data sets are conducted.

In this manuscript, we investigate a collaborative filtering method to characterize consumption behavior of customers and services with various attributes for marketing. We assume that each customer and service have the invisible attribute which is called latent class. Assuming a combination of attribute values of a customer and service is classified to a latent class, furthermore, we propose a new Bayesian statistical model that consumption behavior is probabilistically arise based on a latent class combination of a customer, service and attribute values. Then, we show the method to estimate parameters of a statistical model based on the variational Bayes method and the mean field approximation. Consequently, we show the effectiveness of the proposed model and the estimation method by simulation.

Construction methods for multi-valued classification (multi-class) systems using binary classifiers are discussed and evaluated by a trade-off model for system evaluation based on rate-distortion theory. Suppose the multi-class systems consisted of M(≥3) categories and N(≥M-1) binary classifiers, then they can be represented by a matrix W, where the matrix W is given by a table of M code words with length N, called a code word table. For a document classification task, the relationship between the probability of classification error Pe and the number of binary classifiers N for given M is investigated, and we show that our constructed systems satisfy desirable properties such as “Flexible”, and “Elastic”. In particular, modified Reed Muller codes perform well: they are shown to be “Effective elastic”. As a second application we consider a hand-written character recognition task, and we show that the desirable properties are also satisfied.

In this manuscript, we investigate a collaborative filtering method to characterize consumption behavior (or evaluation) of customers (or users) and services (or items) for marketing. Assuming that each customer and service have the invisible attribute, which is called latent class, we propose a new Bayesian statistical model that consumption behavior is probabilistically arise based on a latent class combination of a customer and service. Then, we show the method to estimate parameters of a statistical model based on the variational Bayes method and the mean field approximation. Consequently, we show the effectiveness of the proposed model and the estimation method by simulation and analyzing actual data.

The flipped classroom approach has recently begun to attract attention. In a flipped classroom, the conventional oles of classroom and homework are reversed: students study on their own using digital teaching materials or e-learning prior to class and then apply their learning in classroom activities. The authors have developed a method for improving the effectiveness of the classroom component: the students in a class are grouped on the basis of the time they spent studying (as recorded in their self-study logs) and their degree of understanding (as revealed by a self-study achievement test), and a different learning model is used for each group to improve their degree of understanding. Although they were unable to find a meaningful statistical difference in the test scores obtained in an experiment using one class of 34 students, there was a notable difference in the way questions were answered. The results of a free-description questionnaire indicate that the group learning encourages active learning.

電子教材を使って学習者がどこまで進んだか、問題を解くためにどのページを何秒見たかなどの詳細な閲覧ログの取得から、学習状況を分析し、学習指導の支援、教材の改善などを可能にした閲覧履歴可視化システムと、初学者向けのプログラミング言語の演習をブラウザベースで提供し、学習者のプログラミング状況（どんなエラーを出しているのか、エラーに対してどんな修正を行ったのか。エラーが無くなるまでどのような経緯でコーディングを行ったのかなど）の詳細な編集ログの取得から、学習状況を可視化し、学習指導の支援を可能にした編集履歴可視化システムの開発事例を報告する。

The distance metric learning is the method to learn the distance metric from training data considering its statistical characteristics under the arbitrary constraints. To obtain the desirable distance metric, the optimization problem is solved. Most of the distance metric learning methods aim to gain the global optimal metric matrix. However there is a possibility that the global metric matrix cannot express the statistical characteristics of each category in detail. In addition, if the dimension of input data increase, the computational cost of calculating distance between data increases either. To avoid this problem, we adopt the way to use the l(1) regularization to gain sparse metric matrix. By combining those, we focus on the way to deriving the plural metric matrices with a sparse structure in this study. To verify the effective ness of our proposed method, we conduct simulation experiments by using UCI machine learning repository.

The Bayes coding algorithm for the tree model class is an effective method calculating the prediction probability of appearing symbol at the next time point from the past data under the Bayes criterion. The Bayes optimal prediction is given by the mixture of all models in a given model class, and the Bayes coding algorithm gives an efficient way to calculate a coding probability. This algorithm is applicable to a general prediction problem with Time-series data. Although the Bayes coding algorithm assumes a class of Markov sources, other model classes can be useful for a real prediction problem in practice. For example, the data at the next time point may not always depend on the strict sequence of the past data. It can be possible to construct an efficient Bayes prediction algorithm for a model class on which the probability of the next symbol is conditioned by the cumulative number in a past data sequence. However, there is usually no way to previously know which model class is the best for the observed data sequence. This paper considers the method to mix the prediction probabilities given by the mixtures on different model subclass. If each calculation of the mixtures on subclasses is efficient, the proposed method is also sufficiently efficient. Based on the asymptotic analysis, we evaluate the prediction performance of the proposed method.

The electronic commerce site (EC site) has become an important marketing channel where consumers can purchase many kinds of products
their access logs, including purchase records and browsing histories, are saved in the EC sites' databases. These log data can be utilized for the purpose of web marketing. The customers who purchase many product items are good customers, whereas the other customers, who do not purchase many items, must not be good customers even if they browse many items. If the attributes of good customers and those of other customers are clarified, such information is valuable as input for making a new marketing strategy. Regarding the product items, the characteristics of good items that are bought by many users are valuable information. It is necessary to construct a method to efficiently analyze such characteristics. This paper proposes a new latent class model to analyze both purchasing and browsing histories to make latent item and user clusters. By applying the proposal, an example of data analysis on an EC site is demonstrated. Through the clusters obtained by the proposed latent class model and the classification rule by the decision tree model, new findings are extracted from the data of purchasing and browsing histories.

データの統計的特徴を考慮した距離構造を学習する方法論としてメトリックラーニングが知られており，そのための様々な手法が提案されている．メトリックラーニングはマハラノビス距離におけるマハラノビス行列（以下，計量行列）を学習するための手法であるが，パラメータ数が入力データの次元数の2乗に比例することが知られている．加えて，学習に要するデータの数も同様に増加してしまうため，高次元データを用いた場合には非常に多くのデータを用意する必要がある．本研究では，計量行列のパラメータ数を減少させるための方法としてl₁正則化に基づくアプローチを採用し，ADMM (Alternating Direction Method of Multiplier) を用いた最適な計量行列の導出方法を示す．提案手法を高次元，スパースなデータセット，ならびに低次元，密なデータセットそれぞれについて適用し，その有効性について示す．

Flipped classrooms have recently begun to attract attention. In a flipped classroom, the roles of a classroom and homework are reversed. Specifically, the students study on their own by using digital teaching materials or e-learning prior to a school hours and apply their learning mainly in the classroom discussions. In this paper, we propose a method for an effective flipped classroom based on the log information of the self-study. Specifically, when students study by e-learning at home, we collect learning logs. We classify students into groups on the basis of their study time and degree of understanding by analyzing the learning logs. We can improve the degree of understanding of the students by conducting a discussion and/or giving a presentation to each group in the classroom.

In this paper, we focus on pattern recognition based on the vector space model. As one of the methods, distance metric learning is known for the learning metric matrix under the arbitrary constraint. Generally, it uses iterative optimization procedure in order to gain suitable distance structure by considering the statistical characteristics of training data. Most of the distance metric learning methods estimate suitable metric matrix from all pairs of training data. However, the computational cost is considerable if the number of training data increases in this setting. To avoid this problem, we propose the way of learning distance metric by using the each category centroid. To verify the effectiveness of proposed method, we conduct the simulation experiment by using benchmark data.

本稿ではプライバシー保護を目的とした回帰分析について扱う．これは複数のユーザがそれぞれ異なるデータを保持したもとで，それぞれの保持するデータを互いに公開，共有することなく，協力して全てのデータを用いた場合と同等の回帰分析を行うというものである．本稿ではまず，ユーザが2人の場合を想定し，2者が異なる属性に関するデータを保持しているもとで最小二乗推定量を分散計算する場合を考える．そのもとで，新たな分散計算プロトコルを提案し，プライバシーについてプロトコルの安全性を評価する．また，提案するプロトコルは繰り返し計算を行うため，数値実験によりプロトコルの繰り返し数についての評価を行う．さらに，収束回数を削減する修正プロトコルを提案し，多者間での分散計算への拡張も行う．

Hassoune and O'Connor proposed a dynamically reconfigurable dynamic logic circuit (DRDLC) that generates Boolean functions by using double-gate (DG) carbon nanotube (CNT) FETs, which have an ambipolar property. O'Connor et al. proposed a DRDLC that generates 14 Boolean functions asing two Boolean inputs with seven transistors. Furthermore, DRDLCs that generates all 16 Boolean functions have been proposed. In this paper, we focus on the design of a dynamic logic circuit with n Boolean inputs. First, we show a DRDLC that generates the monomial Boolean functions. Next, we propose a DRDLC that generates the whole set of Boolean functions consisting oft terms or less. Finally, we report the number of Boolean functions generated by the proposed DRDLC.

This letter describes a design methodology for an arithmetic logic unit (ALU) incorporating reconfigurability based on double-gate carbon nanotube field-effect transistors (DG-CNTFETs). The design of a DG-CNTFET with an ambipolar-property-based reconfigurable static logic circuit is simple and straightforward using an ambipolar binary decision diagram (Am-BDD), which represents the cornerstone for the automatic pass transistor logic (PTL) synthesis flows of ambipolar devices. In this work, an ALU with 16 functions is synthesized by the design methodology of a DG-CNTFET-based reconfigurable static logic circuit. Furthermore, it is shown that the proposed ALU is much more flexible and practical than a conventional DG-CNTFET-based reconfigurable ALU.

In this paper circuit design of reconfigurable dynamic logic based on double gate CNTFETs focusing on number of states of back gate voltages has been newly described. 16 function 9-10T DRDLC for two Boolean inputs with two states (+V, -V) of back gate voltages has been newly proposed. Using this 9-10T DRDLC the conventional 7T DRDLC with three states (+V, 0, -V) of back bate voltages is successfully derived. Furthermore, using four states (+2V, +V, 0, -V) of back gate voltages 6T DRDLC can be realized. These DRDLC with small number of DG-CNTFETs is promising candidates for realizing future high performance reconfigurable LSI. © 2013 Junki Kato et al.

Circuit design of 2-input reconfigurable dynamic logic based on double gate MOSFETs with the whole set of 16 functions has been newly described. 16 function 12T DRDLC with two states (+V, 0) of control gate voltages and 14T DRDLC with two states (0, -V) of control gate voltages have been newly proposed. From these two states control gate case, 12T DRDLC with three states (+V, 0, -V) of control gate voltages is successfully derived. Newly proposed DG-MOSFET with two states (+V, 0), (0, -V) cases can be successfully realized using presently available OR type, AND type IDG-MOSFET, respectively. Newly proposed circuit design, especially for 16 functions 12T DRDLC with two states (+V, 0) case is the promising candidates for realizing future reconfigurable LSIs. © 2013 Junki Kato et al.

This paper proposes a new latent class model to represent user segments in a marketing model of electric commerce sites. The aspect model proposed by T. Hofmann is well known and is also called the probabilistic latent semantic indexing (PLSI) model. Although the aspect model is one of effective models for information retrieval, it is difficult to interpret the meaning of the probability of latent class in terms of marketing models. It is desirable that the probability of latent class means the size of customer segment for the purpose of marketing research. Through this formulation, the simulation analysis to dissect the several situations become possible by using the estimated model. The impact of the strategy that we contact to the specific customer segment and make effort to increase the number of customers belonging to this segment can be predicted by using the model demonstrating the size of customer segment. This paper proposes a new model whose probability parameter of latent variable means the rate of users with the same preference in market. By applying the proposed model to the data of an internet portal site for job hunting, the effectiveness of our proposal is verified.

In this paper, we focus on pattern recognition based on the vector space model with the high dimensional and sparse data. One of the pattern recognition methods is metric learning which learns a metric matrix by using the iterative optimization procedure. However most of the metric learning methods tend to cause overfitting and increasing computational time for high dimensional and sparse settings. To avoid these problems, we propose the method of l(1) regularized metric learning by using the algorithm of alternating direction method of multiplier (ADMM) in the supervised setting. The effectiveness of our proposed method is clarified by classification experiments by using the Japanese newspaper article and UCI machine learning repository. And we show proposed method is the special case of the statistical sparse covariance selection.

F. P. Preparata et al. proposed a fault diagnosis model (PMC model) to find all fault units in the multicomputer system by using outcomes that each unit tests some other units. T. Kohda proposed a highly structured(HS) system and the syndrome analysis method(SAM) to diagnose from local testing results. In this paper, we introduce the maximum a posteriori probability algorithm(MAPDA) for the HS system in the probabilistic fault model. Analyzing the MAPDA, we show that the SAM is closer to the MAPDA as the fault probability becomes smaller. Finally, we show the robustness of the SAM in the HS system.

I. O'Connor et al. have proposed a dynamically reconfigurable dynamic logic circuit (DRDLC) to generate some logic functions by using the double-gate (DG) carbon nanotube (CNT) FETs which have the ambipolar property [1]. This DRDLC consists of seven transistors to generate 14 logic functions which do not include the XOR and XNOR functions. On the other hand, K. Jabeur eta!, have proposed a DRDLC to generate the whole set of 16 logic functions including XOR and XNOR by adding 4 or 8 transistors to O'Connor's circuit [5]. In this letter, we propose a DRDLC, which consists of only seven transistors, to generate the whole set of 16 logic functions by using DG-CNTFETs. Finally, we show that the number of transistors can be reduced compared to the conventional DRDLC to generate 16 logic functions.

This letter describes the design methodology for reduced reconfigurable logic circuits based on double gate carbon nanotube field effect transistors (DG-CNTFETs) with ambipolar propoerty. Ambipolar Binary Decision Diagram (Am-BDD) which represents the cornerstone for automatic pass transistor logic (PTL) synthesis flows of ambipolar devices was utilized to build DG-CNTFET based n-input reconfigurable cells in the conventional approach. The proposed method can reduce the number of ambipolar devices for 2-inputs reconfigurable cells, incorporating the simple Boolean algebra in the Am-BDD compared with the conventional approach. As a result, the static 2-inputs reconfigurable circuit with 16 logic functions can be synthesized by using 8 DG-CNTFETs although the previous design method needed 12 DG-CNTFETs for the same purpose. Copyright © 2013 The Institute of Electronics, Information and Communication Engineers.

本発表では，大学における情報数理科目を対象とした，インタラクティブな電子教材の開発の検討を行う．この教材は主に学生の自習に用いることを前提としたインタラクティブなものとする．また，タブレット端末やスマートフォン端末などでのマルチプラットフォームへの対応や，複雑な数式も表示可能であること，できるだけ一般的な環境での開発を念頭に置いてHTML5+JavaScriptを用いることを前提とする．実際に教材を試作して大学の授業において使用し，問題点の検討や教材の効果の評価を行う．これらの検討結果は大学に限らず，より一般的なインタラクティブ教材を制作する際の有益な示唆を与えると考えられる．

In this paper, we propose the method for embedding the latch and the flip flop (FF) circuit to the universal logic circuit of Double Gate Carbon NanoTube Field Effect Transistor (DG-CNTFET) proposed in the previous work. Previously, 2-inputs universal logic circuit by 8 DG-CNTFET was proposed. If the embedding of flip flop to them is possible, the reconfigurable circuit which includes a state such as flip flop can be realized. The result of our research shows that SR-latch and D-latch with 3-inputs/state can be embedded within 2-inputs universal logic circuit. Thus it is shown that a D-FF can be embedded to two 2-inputs universal logic circuit. © 2013 IEEE.

We propose new algorithms for fault diagnosis problem based on the dual decomposition method and the augmented Lagrangian method. Our algorithms are convergent and those outputs are same as that of Linear Programming (LP) based fault diagnosis algorithm. The proposed algorithms have smaller computational complexity than ordinary LP solver. Experimental results show the practical potentials of the proposed algorithms.

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

In this paper, a new attack model in which the number of colluders are distributed according to a certain probability distribution is introduced. Two classes of collusion attacks which include well-known collusion attacks in the context of multimedia fingerprinting are provided. For these two attack classes, achievable rates for the unknown size of the actual colluders are derived. Based on the derived achievable rates, achieve rates for some particular attacks are investigated. For the AND attack, the bound derived in this paper coincides with the previous known bound, although the attack model in this paper does not assume that the decoder knows the actual number of colluders. Moreover, for the averaging attack, it is clarified that derived achievable rate is larger than previously known bound with random linear codes. © 2011 IEEE.

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

An iterative decoding algorithm of rate-compatible punctured low-density parity-check (RCP-LDPC) codes of high coding rates is developed. This algorithm performs a predetermined recovering process of punctured bits sums at the beginning of each iteration of the standard belief-propagation (BP) decoding algorithm. By propagating messages of two punctured bits sum, this algorithm can recover much more punctured bits than the standard BP decoding algorithm. It is shown that the proposed algorithm is applicable for RCP-LDPC codes of higher coding rates with little increase of decoding complexity. © 2010 IEEE.

Two decoding procedures combined with a belief-propagation (BP) decoding algorithm for low-density parity-check codes over the binary erasure channel are presented. These algorithms continue a decoding procedure after the BP decoding algorithm terminates. We derive a condition that our decoding algorithms can correct an erased bit which is uncorrectable by the BP decoding algorithm. We show by simulation results that the performance of our decoding algorithms is enhanced compared with that of the BP decoding algorithm with little increase of the decoding complexity.

In this paper. we analyze the robustness for low-density parity-check (LDPC) codes over the Gilbert-Elliott (GE) channel. For this purpose we propose a density evolution method for the case where LDPC decoder uses the mismatched parameters for the GE channel. Using this method, we derive the region of tuples of true parameters and mismatched decoding parameters for the GE channel. where the decoding error probability approaches asymptotically to zero.

We propose a maximum likelihood decoding scheme with decoder's partial cooperation, in which only unidirectional information passing is possible, for correlated parallel channels. We derive a bound on the probability of decoding error for the proposed scheme with a coset code ensemble by using randomized technique. From the property of the derived error exponent, we show a condition that the scheme achieves the capacity region. We compare the proposed scheme with other possible scheme with decoder's unidirectional cooperation.

In this paper, we investigate the design of low-density parity-check (LDPC) codes for the Gilbert-Elliott (GE) channel. Recently, Eckford et al. proposed a design method of irregular LDPC codes using approximate density-evolution (DE) for Markov channels [7]. In the design method proposed by Eckford et al., the probability density function (PDF) of the messages from variable nodes to check nodes is approximated by the Gaussian distribution. In this paper, we first show the method to obtain the accurate PDF of the messages from variable nodes to check nodes by utilizing two DE steps for the Gaussian distribution. We call this method the iterative density approximation (IDA). Using this method, we can design the good LDPC codes. Next, we propose an efficient design method of irregular LDPC codes by using Beta approximation to the PDF of the channel state probability for the GE channel. Consequently, we show that the complexity to calculate PDFs of the channel messages is considerably reduced though the rates of LDPC codes obtained by using the proposed approximation are almost the same as that of the IDA method.

In 1996 Rosenthal and York proposed (time-invariant) BCH convolutional codes [4] in which the parity check matrix of a BCH code is used in the construction of the convolutional code. The lower bound on the minimum free distance of a BCH convolutional code is guaranteed by the BCH limit. In this paper we propose a periodically time-variant convolutional code that can be constructed not only using the BCH parity check matrix but using the check matrix of any binary linear block code and show that the lower bound on the minimum free distance is guaranteed by the minimum free distance of the binary linear block code. In addition, taking 12 binary linear block codes as examples, we perform comparisons of the proposed codes with BCH convolutional codes using three evaluation criteria (minimum free distance, number of delay elements, coding rate) and show that there exist proposed codes that are superior to existing ones. (C) 2007 Wiley Periodicals, Inc. Electron Comin Jpn Pt 3, 90(9):31-40,2007; Published online in Wiley InterScience (www.interscience. wiley.com).

マトリックスクラスタリングとは与えられた疎行列に対し，指定された面積以上で，指定された密度（部分行列における1の要素の比率）以上の密な部分行列を抽出することと定義される．この手法はCRM向けのデータマイニング手法として提案されたものであり，より関連の深い商品と顧客をクラスタリングすることを可能としている．本稿ではアプリオリアルゴリズムを拡張し，ある特定の条件を満たす部分行列全てを抽出するマトリックスクラスタリングアルゴリズムを提案する．これにより，顧客の購買情報をきめ細かく分析することが可能となる．

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.

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.

Y.S. Han et al. have proposed an efficient maximum likelihood decoding (MLD) algorithm using A* algorithm which is the graph search method. In this paper, we propose a new MLD algorithm for linear block codes. The MLD algorithm proposed in this paper improves that given by Han et al. utilizing codewords of dual codes. This scheme reduces the number of generated codewords in the MLD algorithm. We show that the complexity of the proposed decoding algorithm is reduced compared to that given by Hall et al. without increasing the probability of decoding error.

For the two-dimensional BCH code, several decoding methods exceeding the BCH bound and correcting the errors that cannot be corrected by the conventional Limited distance decoding method have been proposed. This article proposes an algorithm that allows reduction of the computational volume in a decoding method exceeding the BCH bound by solving the equation for unknown variables beforehand and limiting the range of the error location. Further, this decoding method exceeding the BCH bound is applied to soft-decision decoding methods that use limited-distance decoding multiple times, and especially to Chase decoding, the decoding of Tanaka et al., and that of Kaneko et al. It is shown that the amount of computation and the decoding error rate are improved. (C) 1999 Scripta Technica.

2元(n,k,d)BCH符号に対し誤り訂正能力tを超えるt+v個の誤りが生じたとき, この誤りを訂正する復号法が提案されている. 本論文では硬判定受信系列にテスト誤り系列を加えたものに, このt+v重誤り訂正を複数回用いる軟判定復号法について述べる. そのときテスト誤り系列に2元(N,K)線形符号(n≧N)の符号語を用いることにより, 効率よく符号語を探索する手法を提案する. その結果, 提案復号法はその特別な場合としてChase復号法のアルゴリズム2を含み, Chaseアルゴリズム2の復号誤り確率を劣化させることなくその最大計算量を1/(_2N-K)に低減することができることを示す. 更に, この復号法を最ゆう復号法へ拡張し, その有効性も示す.