Twofold universal prediction schemes for achieving the finite-statepredictability of a noisy individual binary sequence

The problem of predicting the next outcome of an individual binary sequence corrupted by noise using finite memory, is considered. The conditional finite-state (FS) predictability of an infinite individual sequence given its noisy version is defined as the minimum fraction of errors that can be made by any FS predictor fed by the noisy version. It is proved that the conditional FS predictability can be attained almost surely by universal sequential prediction schemes in the case where the noisy version is the output of a binary-symmetric channel (BSC) whose input is the clean individual sequence. In particular, universal predictors of the original noise-free setting, which operate on the noisy sequence, have this property. Moreover, these universal predictors do not depend on the crossover probability characterizing the BSC. It is seen that the noisy setting gives rise to additional criteria by which the performance of prediction schemes can be assessed. Finally, a closer look is taken at the conditional FS predictability, and this quantity is proposed as an additional measure of the complexity of a sequence, perhaps finer and more informative than the predictive complexity of the noise-free setting     

A universal prediction lemma and applications to universal datacompression and prediction

A universal prediction lemma is derived for the class of prediction algorithms that only make inferences about the conditional distribution of an unknown random process based on what has been observed in the training data. The lemma is then used to derive lower bounds on the efficiency of a number of universal prediction and data compression algorithms. These bounds are nonasymptotic in the sense that they express the effect of limited training data on the efficiency of universal prediction and universal data compression     

Universal linear prediction by model order weighting

A common problem that arises in adaptive filtering, autoregressive modeling, or linear prediction is the selection of an appropriate order for the underlying linear parametric model. We address this problem for linear prediction, but instead of fixing a specific model order, we develop a sequential prediction algorithm whose sequentially accumulated average squared prediction error for any bounded individual sequence is as good as the performance attainable by the best sequential linear predictor of order less than some M. This predictor is found by transforming linear prediction into a problem analogous to the sequential probability assignment problem from universal coding theory. The resulting universal predictor uses essentially a performance-weighted average of all predictors for model orders less than M. Efficient lattice filters are used to generate the predictions of all the models recursively, resulting in a complexity of the universal algorithm that is no larger than that of the largest model order. Examples of prediction performance are provided for autoregressive and speech data as well as an example of adaptive data equalization     

Universal prediction of individual sequences

The problem of predicting the next outcome of an individual binary sequence using finite memory is considered. The finite-state predictability of an infinite sequence is defined as the minimum fraction of prediction errors that can be made by any finite-state (FS) predictor. It is proven that this FS predictability can be achieved by universal sequential prediction schemes. An efficient prediction procedure based on the incremental parsing procedure of the Lempel-Ziv data compression algorithm is shown to achieve asymptotically the FS predictability. Some relations between compressibility and predictability are discussed, and the predictability is proposed as an additional measure of the complexity of a sequence     

Finite-memory universal prediction of individual sequences

The problem of predicting the next outcome of an individual binary sequence under the constraint that the universal predictor has a finite memory, is explored. In this analysis, the finite-memory universal predictors are either deterministic or random time-invariant finite-state (FS) machines with K states (K-state machines). The paper provides bounds on the asymptotic achievable regret of these constrained universal predictors as a function of K, the number of their states, for long enough sequences. The specific results are as follows. When the universal predictors are deterministic machines, the comparison class consists of constant predictors, and prediction is with respect to the 0-1 loss function (Hamming distance), we get tight bounds indicating that the optimal asymptotic regret is 1/(2K). In that case of K-state deterministic universal predictors, the constant predictors comparison class, but prediction is with respect to the self-information (code length) and the square-error loss functions, we show an upper bound on the regret (coding redundancy) of O(K/sup -2/3/) and a lower bound of /spl Theta/(K/sup -4/5/). For these loss functions, if the predictor is allowed to be a random K-state machine, i.e., a machine with random state transitions, we get a lower bound of /spl Theta/(1/K) on the regret, with a matching upper bound of O(1/K) for the square-error loss, and an upper bound of O(logK/K) Throughout the paper for the self-information loss. In addition, we provide results for all these loss functions in the case where the comparison class consists of all predictors that are order-L Markov machines.     

Impossibility Results for Universal Composability in?Public-Key Models and with Fixed Inputs

Universal composability and concurrent general composition consider a setting where secure protocols are run concurrently with each other and with arbitrary other possibly insecure protocols. Protocols that meet the definition of universal composability are guaranteed to remain secure even when run in this strongly adversarial setting. In the case of an honest majority, or where there is a trusted setup phase of some kind (like a common reference string or the key-registration public-key infrastructure of Barak et al.?in FOCS 2004), it has been shown that any functionality can be securely computed in a universally composable way. On the negative side, it has also been shown that in the plain model where there is no trusted setup at all, there are large classes of functionalities which cannot be securely computed in a universally composable way without an honest majority. In this paper, we extend these impossibility results for universal composability. We study a number of public-key models and show for which models the impossibility results of universal composability hold and for which they do not. We also consider a setting where the inputs to the protocols running in the network are fixed before any execution begins. The majority of our results are negative and we show that the known impossibility results for universal composability in the case of no honest majority extend to many other settings.     

Current-mode OTA-C realisation of arbitrary filter characteristics

Two universal current-mode integrator-based OTA-C filter structures are presented. General explicit design formulas are derived. The filter architectures proposed are constructed using a canonical FLF configuration with an input distribution or output summation network. They are comprehensive in function. By setting any particular input distributing or output summing weights (transconductances), we can realise arbitrary approximation characteristics. It is also straightforward to obtain universal filter architectures and the corresponding design formulae of any particular order. The universal second and third order filters and design formulas are discussed in detail     

Universal Delay-Limited Simulation

Universal, delay-limited simulation of an unknown information source of a certain parametric family (e.g., the family of memoryless sources or Markov sources of a given order), given a training sequence from that source and a stream of independent and uniformly distributed bits, is considered. The goal of universal simulation is that the probability law of the generated sequence be identical to that of the training sequence, with minimum mutual information between the random processes generating both sequences. In the delay-limited setting, the simulation algorithm generates a random sequence sequentially, by delivering one symbol for each training symbol that is made available after a given initial delay, whereas the random bits are assumed to be available on demand. In this paper, the optimal universal delay-limited simulation scheme is characterized for broad parametric families, and the mutual information achieved by the proposed scheme is analyzed. The results are extended to a setting of variable delay.      

市场机制下电信普遍服务政策探讨

在行业垄断时期，许多国家通常都采用交叉补贴的方式解决普遍服务问题。但这种原来奏效的方式已很难适应目前开放竞争的电信市场。目前，各国普遍采用三大政策来解决普遍服务问题，即设置条件、普遍服务基金和隐性补助。但是，为了更灵活更有效地推进普遍服务义务的实施，人们已经开始探讨和应用另外一种、即“可交易的普遍服务”政策，利用市场化的方式和手段来解决这一问题。     

n阶传输函数的CC实现

本文提出了两个基于积分器的通用CC网络结构。该结构是在典型FLF结构的基础上增加输入分布和输出求和CC网络生成的。适当设置输入分布和输出求和CC网络元件参数,能实现任意高阶传输函数。文中给出了系统的设计公式。     

Toward optimality in scalable predictive coding

A method is proposed for efficient scalability in predictive coding, which overcomes known fundamental shortcomings of the prediction loop at enhancement layers. The compression efficiency of an enhancement-layer is substantially improved by casting the design of its prediction module within an estimation-theoretic framework, and thereby exploiting all information available at that layer for the prediction of the signal, and encoding of the prediction error. While the most immediately important application is in video compression, the method is derived in a general setting and is applicable to any scalable predictive coder. Thus, the estimation-theoretic approach is first developed for basic DPCM compression and demonstrates the power of the technique in a simple setting that only involves straightforward prediction, scalar quantization, and entropy coding. Results for the scalable compression of first-order Gauss-Markov and Laplace-Markov signals illustrate the performance. A specific estimation algorithm is then developed for standard scalable DCT-based video coding. Simulation results show consistent and substantial performance gains due to optimal estimation at the enhancement-layers.     

On the role of pattern matching in information theory

In this paper, the role of pattern matching in information theory is motivated and discussed. We describe the relationship between a pattern's recurrence time and its probability under the data-generating stochastic source. We show how this relationship has led to great advances in universal data compression. We then describe nonasymptotic uniform bounds on the performance of data-compression algorithms in cases where the size of the training data that is available to the encoder is not large enough so as to yield the asymptotic compression: the Shannon entropy. We then discuss applications of pattern matching and universal compression to universal prediction, classification, and entropy estimation     

Optimum built-in barrier height utilizing an extended concept of impedance matching

Schottky-barrier height optimization for high-frequency usage is analytically discussed with an extended concept of impedance matching. The optimum value of 0.3 eV is almost a universal constant under various operating conditions, and agrees well with the previous prediction obtained by large signal simulation and InxGa1-xAs experiments.     

15/30 Mbit/s Universal Digital TV Codec Using a Median Adaptive Predictive Coding Method

This paper describes a 15/30 Mbit/s TV codec with a new approach to high-efficiency coding for TV signals, i.e., median adaptive prediction. The 15/30 Mbit/s codec, commonly applicable to NTSC, PAL, and SECAM (525/60 and 625/50) systems, uses adaptive prediction incorporating a motion-compensated interframe, an interfield, and an intrafield predictor. Its performance for digital transmission is presented. This universal codec is designed, based on CCIR recommendations concerning digital TV coding parameters for studios (Rec. 601) and general principles on long-distance digital TV transmission (Rec. 604). A field trial of 15 Mbit/s digital TV transmission using this codec between earth stations with a 30 m diameter antenna and a 5 m diameter antenna is reported.     

Universal discrete denoising: known channel

A discrete denoising algorithm estimates the input sequence to a discrete memoryless channel (DMC) based on the observation of the entire output sequence. For the case in which the DMC is known and the quality of the reconstruction is evaluated with a given single-letter fidelity criterion, we propose a discrete denoising algorithm that does not assume knowledge of statistical properties of the input sequence. Yet, the algorithm is universal in the sense of asymptotically performing as well as the optimum denoiser that knows the input sequence distribution, which is only assumed to be stationary. Moreover, the algorithm is universal also in a semi-stochastic setting, in which the input is an individual sequence, and the randomness is due solely to the channel noise. The proposed denoising algorithm is practical, requiring a linear number of register-level operations and sublinear working storage size relative to the input data length.     

Simple Indoor Path Loss Prediction Algorithm and Validation in Living Lab Setting

A simple heuristic algorithm has been developed for an accurate prediction of indoor wireless coverage, aiming to improve existing models upon multiple aspects. Extensive measurements on several floors in four buildings are used as validation cases and show an excellent agreement with the predictions. As the prediction is based on the free-space loss model for every environment, it is generally applicable, while other propagation models are often too dependent on the environment upon which it is based. The applicability of the algorithm to a wireless testbed network in a living lab setting with WLAN 802.11b/g nodes is investigated by a site survey. The results can be extremely useful for the rollout of indoor wireless networks.     

Modelling attenuation by rain in tropical regions

The data in the CCIR data banks were employed for a statistical study of the relative performance of several rain attenuation prediction procedures in temperate and tropical regions. The results show that the models worked well, in general, when used for prediction at latitudes more than 30° from the equator, but, in the equatorial region, significant prediction errors were observed for all the models. Three sources of error were discovered. The most important is the use of too few rain climate zones to span the wide range of rain conditions present in the equatorial region. The second is an inadequate procedure for taking the naturally occurring vertical variations of specific attenuation into account. Finally, for the CCIR attenuation prediction model, the use of a universal shape for the cumulative distribution of path attenuation must be called into question.     

General Composition and Universal Composability in Secure Multiparty Computation

Concurrent general composition relates to a setting where a secure protocol is run in a network concurrently with other, arbitrary protocols. Clearly, security in such a setting is what is desired, or even needed, in modern computer networks where many different protocols are executed concurrently. Canetti (FOCS 2001) introduced the notion of universal composability and showed that security under this definition is sufficient for achieving concurrent general composition. However, it is not known whether or not the opposite direction also holds. Our main result is a proof that security under concurrent general composition, when interpreted in the natural way under the simulation paradigm, is equivalent to a variant of universal composability, where the only difference relates to the order of quantifiers in the definition. (In newer versions of universal composability, these variants are equivalent.) An important corollary of this theorem is that existing impossibility results for universal composability (for all its variants) are inherent for definitions that imply security under concurrent general composition, as formulated here. In particular, there are large classes of two-party functionalities for which it is impossible to obtain protocols (in the plain model) that remain secure under concurrent general composition. We stress that the impossibility results obtained are not “black-box,” and apply even to non-black-box simulation. Our main result also demonstrates that the definition of universal composability is somewhat “minimal” in that the composition guarantee provided by universal composability implies the definition itself. This indicates that the security definition of universal composability is not overly restrictive. An extended abstract of this work appeared in the 44th FOCS, 2003. Yehuda Lindell: Most of this work was carried out while the author was at the IBM T.J. Watson Research Center.