Back in 1967 the Croat linguist Ž. Muljačić had used a fuzzy generalization of the Hamming distance between binary strings to classify Romance languages. In 1956 Cl. Shannon had introduced the notion of codeword distinguishability in zero-error information theory. Distance and distinguishability are subtly different notions, even if, with distances as those usually met in coding theory (ruling out zero-error information theory, which is definitely non-metric), the need for string distinguishabilities evaporates, since the distinguishability turns out to be an obvious and trivial function of the distance. Fuzzy Hamming distinguishabilities derived from Muljačić distances, instead, are quite relevant and must be considered explicitly. They are very easy to compute, however, and we show how they could be applied in coding theory to channels with erasures and blurs. Fuzzy Hamming distinguishabilities appear to be quite a promising tool to extend Muljačić approach from linguistic classification to linguistic evolution.

Back in 1967 the linguist Ž. Muljačić used an additive distance between ill-defined linguistic features which is a forerunner of the fuzzy Hamming distance between strings of truth values in standard fuzzy logic. Here we show that if the logical frame is changed one obtains additive distances which are either sorely inadequate, as in the Łukasiewicz or probabilistic case, or coincide with the distance originally envisaged by Muljačić, as happens with a whole class of T-norms (abstract logical conjunctions) which includes the nilpotent minimum. All this strengthens the role of Muljačić distances in linguistic clustering and of Muljačić distinguishabilities (a notion subtly different from distances, but quite inalienable) in linguistic evolution. As a preliminary example we re-take and re-examine Muljačić original data.

We put forward an ample framework for coding based on upper probabilities, or more generally on normalized monotone set-measures, and model accordingly noisy transmission channels and decoding errors. Two inverse problems are considered. In the first case, a decoder is given and one looks for chann els of a specified family over which that decoder would work properly. In the second and more ambitious case, it is codes which are given, and one looks for channels over which those codes would ensure the required error correction capabilities. Upper probabilities allow for a solution of the two inverse problems in the case of usual codes based on checking Hamming distances between codewords: one can equivalently check suitable upper probabilities of the decoding errors. This soon extends to “odd” codeword distances for DNA strings as used in DNA word design, where instead, as we prove, not even the first unassuming inverse problem admits of a solution if one insists on channel models based on “usual” probabilities.

Spearman distance is a permutation distance which might be used for codes in permutations beside Kendall distance. However, Spearman distance gives rise to a geometry of strings, which is rather unruly from the point of view of error correction and error detection. Special care has to be taken to discriminate between the two notions of codeword distance and codeword distinguishability. This stresses the importance of rejuvenating the latter notion, extending it from Shannon's zero-error information theory to the more general setting of metric string distances.

We re-take the possibilistic (as opposed to probabilistic) approach to information coding put forward in 1,2. To enhance the possibilistic approach also outside the realm of "subjective" uncertainties, in this paper we adopt an "objective" interpretation of possibilistic source coding based on utility functions and an "objective" interpretation of possibilistic channel coding based on distortion measures and similarity indices. We stress the relationship between possibilistic coding as based on distortions between sequences and algebraic coding as based on minimum distances between codewords. We compute the operational (coding-theoretic) entropy for a new class of possibilistic sources.

We re-take the possibilistic model for information sources recently put forward by the first author, as opposed to the standard probabilistic models of information theory. Based on an interpretation of possibilistic source coding inspired by utility functions, we define a notion of possibilistic entropy for a suitable class of interactive possibilistic sources, and compare it with the possibilistic entropy of stationary non-interactive sources. Both entropies have a coding-theoretic nature, being obtained as limit values for the rates of optimal compression codes. We list properties of the two entropies, which might support their use as measures of "possibilistic ignorance".

In [2] a theory of incomplete interval probabilities has been put forward, which is meant to give a common framework to both interval probabilities and open-frame bodies of evidence, as obtained by application of the non-normalized Dempster rule. Below, as a continuation of [2], we compare two possible ways of "conditioning" based on a special case of the rule, i.e. open-frame Dempster conditioning.

We study the composition of messages in an encoding tree for a Tunstall code, and, more generally, in a tree whose skewness is bounded. For such trees a sort of "law of large numbers" holds true; actually, we provide a direct and converse coding theorem for variable-length to block length source codes, when a vanishing error probability is allowed.

We develop a reference setting for uncertainty representation, i.e. incomplete interval probabilities, which we think may be useful not only at the formal but also at the conceptual level. The universe we choose to work on is a finite set, which is thought of as open (incomplete, not fully observable); a pre-assumption we make is acceptance of Dempster rule without the normalization coefficient as an adequate tool for pooling opinions. We make use of three comparatively old ingredients: interval probabilities, open-frame bodies of evidence and Rényi's incomplete probabilities. As for open-frame bodies of evidence, we introduce a formal novelty, seemingly of little or no consequence, which instead leads us quite naturally to the unifying approach of incomplete interval probabilities. We tackle the problem of forcing incomplete states of knowledge into completeness, as required at the operational stage of decision making.

We give a convenient criterion which shows that "most" bodies of evidence are not representable through simple interval probabilities, i.e. interval probabilities defined through singleton constraints. Actually, the two theories are largely non-overlapping.

In the first part of this paper, we tackle the case where a variable length-to-block Tunstall code is used to encode the wrong source (miscoding). It turns out that, exactly as happens in the case with Huffman coding, the asymptotic excess rate is given by the informational divergence between the probability distribution ruling the source and the probability distribution for which the Tunstall code had been devised. We also prove asymptotic equality between the individual rate of a codeword and the corresponding self-information. This allows us to bound the maximal and the minimal length in a Tunstall tree. In the second part of the paper we study the case where the probability distribution of the source changes in time. If this happens, it is necessary to frequently update the current code, to ensure that the optimality conditions concerning its rate are met. This coding procedure is known as adaptive coding. We propose some schemes for adaptive Tunstall coding, based on the structure of the coding tree, on the "ordering property", analogous to Gallager's (1978) sibling property of the Huffman code, and on the "Tunstall regions", analogous to the attraction regions due to Longo and Galasso (1982).

Simmons' lower bound on impersonation P/sub 1/>or=2/sup -I(M;E)/ where M and E denote the message and the encoding rule, respectively, is strengthened by maximizing over the source statistics and by allowing dependence between the message and the encoding rule. The authors show that a refinement of their argument, which removes the assumption of independence between E and the source state S, leads to an even stronger bound.>

Unlike recent works by Blom and Dunham on simple substitution ciphers, papers, we do not consider equivocations (conditional entropies given the cryptogram) but rather the probability that the enemy makes an error when he tries to decipher the cryptogram or to identify the key by means of optimal identification procedures. This approach is suggested by the usual approach to coding problems taken in Shannon theory, where one evaluates error probabilities with respect to optimal encoding-decoding procedures. The main results are asymptotic; the same relevant parameters are obtained as in Blom or Dunham.

A new approach to the classical fixed-length noiseless source coding problem is proposed for the case of finite ergodic Markov sources. This approach is based on simple counting arguments. The central notion of "Markov type" (a set containing all the source sequences having the same transition counts from letter to letter) is introduced and the cardinality of such a set is evaluated via graph theoretical tools. The error exponent is shown to be a weighted average of informational divergences, and the universal character of the result is stressed. As a corollary, the classical source coding theorem (determining the achievable rates) is rederived.

Universally attainable error exponents for broadcast channels with degraded message sets are obtained using a technique which generalizes that introduced by Csiszár, Körner, and Martron for the ordinary channel. Lower and upper bounds to the error probabilities over a single broadcast channel are also given.

A combinatorial approach is proposed for proving the classical source coding theorems for a finite memoryless stationary source (giving achievable rates and the error probability exponent). This approach provides a sound heuristic justification for the widespread appearence of entropy and divergence (Kullback's discrimination) in source coding. The results are based on the notion of composition class -- a set made up of all the distinct source sequences of a given length which are permutations of one another. The asymptotic growth rate of any composition class is precisely an entropy. For a finite memoryless constant source all members of a composition class have equal probability; the probability of any given class therefore is equal to the number of sequences in the class times the probability of an individual sequence in the class. The number of different composition classes is algebraic in block length, whereas the probability of a composition class is exponential, and the probability exponent is a divergence. Thus if a codeword is assigned to all sequences whose composition classes have rate less than some rateR, the probability of error is asymptotically the probability of the must probable composition class of rate greater thanR. This is expressed in terms of a divergence. No use is made either of the law of large numbers or of Chebyshev's inequality.

A source coding problem is considered which generalizes source coding with side information [1], [2]. Three correlated information sourcesX,YandZ, are block-encoded:Yis to be reconstructed by two different decoders, one having access to the encoded version ofXand the other having access to the encoded version ofZ. The region of achievable rates is determined, assuming that thc sources are discrete, memoryless, and stationary. The resuit is generalized to an arbitrary finite number of decoders.