Consider M-valued (M$\geq$3) classification systems realized by combination of N(N$\geq\lceil\log_{2}$M$\rceil$) binary classifiers. Such a construction method is called an Error Correcting Output Code (ECOC). First, focusing on a Reed-Muller (RM) code, we derive a modified RM (mRM) code to make it suitable for the ECOC. Using the mRM code and the Hadamard matrix, we introduce a simplex code which is one of the powerful equidistant codes. Next, from the viewpoint of system evaluation model, we evaluate the ECOC by using constructive coding described above. We show that they have desirable properties such as Flexible, Elastic, and Effective Elastic as M becomes large, by employing analytical formulas and experiments.

To solve multiple classification problems with $M (\geq$ 3) categories, many studies have been devoted using $N (\geq\ \lceil\log_{2}M\rceil)$ binary $(\{0,1\})$ classifiers, where these systems are known as binary Error-Correcting Output Codes (binary ECOC). As an extended version of the binary ECOC, the ternary $(\{0,\ *,\ 1\})$ ECOC have also been discussed, where ternary classifiers classify data into positive examples when the element is 1, into negative examples when the element is 0, and no classification when the element is $*$. In this paper, we discuss the ternary ECOC system from the view point of the system evaluation model based on rate-distortion function. First, we discuss a table of M code words with length N which is given by a ternary matrix W of M rows and N columns. Next, by leveraging the benchmark data for multiclass document classification which is widely used in Japan, the relationships between the probability of classification error Peand the number of the ternary classifiers N for a given M are experimentally investigated. In addition, by assuming the M-dimensional Normal distribution for a classification data model, the relationship between Peand N for a given M is also examined. Finally, we show by the system evaluation model that the ternary ECOC systems have desirable properties such as “Flexible”, “Elastic”, and “Effective Elastic”, when M becomes large.

We discuss disk allocation methods for Cartesian product files by introducing error correcting codes, and have clarified the performance of the methods by system evaluation models developed by using rate distortion theory. Let us assume qnCartesian product files with n attributes and q actual values in each attribute, and store qnfiles into G(≤ qn) disks. For a partial match access request, we represent new disk allocation methods which able to access the disks in parallel as much as possible, where the partial match access request includes an indefinite case (don't care: “*”) in some attributes and the * requires to access the files with corresponding to the attribute for the all actual attribute values. In this paper, we propose to apply unequal error protection codes to the case where the probabilities of occurrence of the * in the attributes for a partial match access request are not the same. We show the disk allocation methods have desirable properties as n becomes large.

Allocation methods for Cartesian product files on multiple disks using linear error-correcting codes are discussed. In this paper, we propose an allocation method using unequal error protection (UEP) codes. Codewords of an UEP code have some special bits which are protected against a greater number of errors than the other bits. We firstly assume a model that “*”, which means “don't care”, appears with different probability in each attribute of queries. In this case, the average access time can be calculated using the split distance distribution. Finally, we illustrate the average access time of the methods using UEP codes.

A new soft decoding algorithm for linear block codes is proposed. The decoding algorithm works with any algebraic decoder and its performance is strictly the same as that of maximum-likelihood-decoding (MLD). Since our decoding algorithm generates sets of different candidate codewords corresponding to the received sequence, its decoding complexity depends on the received sequence. We compare our decoding algorithm with Chase (1972) algorithm 2 and the Tanaka-Kakigahara (1983) algorithm in which a similar method for generating candidate codewords is used. Computer simulation results indicate, for some signal-to-noise ratios (SNR), that our decoding algorithm requires less average complexity than those of the other two algorithms, but the performance of ours is always superior to those of the other two.>

Considering inductive inference and deductive inference as not individual processes but a serial process of information processing, the serial inference procedure is studied for two purposes: the compression of observed facts and the prediction of new well-formed formulas. A serial inference process scheme that uses the correspondence to source coding and prediction problems is proposed. The optimal inference procedures for the two purposes are shown in the proposed scheme.>

The problem of distortionless encoding when the parameters of the probabilistic model of a source are unknown is considered from a statistical decision theory point of view. A class of predictive and nonpredictive codes is proposed that are optimal within this framework. Specifically, it is shown that the codeword length of the proposed predictive code coincides with that of the proposed nonpredictive code for any source sequence. A bound for the redundancy for universal coding is given in terms of the supremum of the Bayes risk. If this supremum exists, then there exists a minimax code whose mean code length approaches it in the proposed class of codes, and the minimax code is given by the Bayes solution relative to the prior distribution of the source parameters that maximizes the Bayes risk.>

The operating cost of distributed database systems (DDBS) usually depends on the storage costs of file copies, i.e file redundancy, and the communication cost of queries and for updates. A basic model is proposed to clarify the tradeoffs between the file redundancies and the communication cost of queries from the viewpoint of rate-distortion theory and its applications, for the case in which almost all requests are assumed to be queries. The result suggests that the addition of a few file copies is effective for the bus or ring network subsystems and the existence of only one file is essential to the star network subsystem, as the system size becomes large. The model leads to a useful measure for selecting the file-allocation design of a large scale DDBS.>

In information retrieval systems, the consecutive retrieval (CR) property enables the design of the system with a minimal search time and no redundant storage. However, the CR property cannot exist between every arbitrary query set and every record set unless we relax these restrictions. We use the variable-buffer quasi-CR (V-QCR) property scheme which tolerates variable buffer size in the main storage and several secondary storages. In secondary file organization, we propose two subschemes: 1) the relaxed CR (RCR) property subscheme which tolerates the duplication of records and multiple access, and 2) the CR property with dummy records (CR-D property) subscheme which tolerates the dummy records and the variable buffer size. For each proposed subscheme, we evaluate the trade-offs between the system redundancy and the loss of search time by rate-distortion theoretic approach. The result indicates that it is worthwhile to search for algorithms that will generate the secondary storage locations satisfying RCR and CR-D property subschemes, when the system size becomes sufficiently large.

Question-answering systems have been studied from the viewpoint of achieving drastic savings of storage with a small error tolerance. A system is called elastic if a drastic memory saving may be achieved by tolerating a low level of indefiniteness of the answer. A necessary condition for the system to be elastic is that the query sets exhibit diverging redundancy. In the binary-valued retrieval problems discussed by P. Elias and R.A. Flower (1975), a system that admits the set of all binary questions regarding an arbitrary binary data with the highest redundance has been shown to be inelastic. On the other hand, a system that admits the exact match question set regarding an arbitrary binary data with the second highest redundancy is found to be elastic.