Universal decoding for finite-state channels

Universal decoding procedures for finite-state channels are discussed. Although the channel statistics are not known, universal decoding can achieve an error probability with an error exponent that, for large enough block length (or constraint length in case of convolutional codes), is equal to the random-coding error exponent associated with the optimal maximum-likelihood decoding procedure for the given channel. The same approach is applied to sequential decoding, yielding a universal sequential decoding procedure with a cutoff rate and an error exponent that are equal to those achieved by the classical sequential decoding procedure.     

Syndrome-source-coding and its universal generalization

A method of using error-correcting codes to obtain data compression, called syndrome-source-coding, is described in which the source sequence is treated as an error pattern whose syndrome forms the compressed data. It is shown that syndrome-source-coding can achieve arbitrarily small distortion with the number of compressed digits per source digit arbitrarily close to the entropy of a binary memoryless source. A "universal" generalization of syndrome-source-coding is formulated which provides robustly effective distortionless coding of source ensembles. Two examples are given comparing the performance of noiseless universal syndrome-source-coding to 1) run-length coding and 2) Lynch-Davisson-Schalkwijk-Cover universal coding for an ensemble of binary memoryless sources.     

Universal portfolios with side information

We present a sequential investment algorithm, the μ-weighted universal portfolio with side information, which achieves, to first order in the exponent, the same wealth as the best side-information dependent investment strategy (the best state-constant rebalanced portfolio) determined in hindsight from observed market and side-information outcomes. This is an individual sequence result which shows the difference between the exponential growth wealth of the best state-constant rebalanced portfolio and the universal portfolio with side information is uniformly less than (d/(2n))log (n+1)+(k/n)log 2 for every stock market and side-information sequence and for all time n. Here d=k(m-1) is the number of degrees of freedom in the state-constant rebalanced portfolio with k states of side information and m stocks. The proof of this result establishes a close connection between universal investment and universal data compression     

A Universal VLSI Architecture for Reed–Solomon Error-and-Erasure Decoders

This paper presents a universal architecture for Reed-Solomon (RS) error-and-erasure decoder. In comparison with other reconfigurable RS decoders, our universal approach based on Montgomery multiplication algorithm can support not only arbitrary block length but various finite-field degree within different irreducible polynomials. Moreover, the decoder design also features the constant multipliers in the universal syndrome calculator and Chien search block, as well as an on-the-fly inversion table for calculating error or errata values. After implemented with 0.18-mum 1P6M technology, the proposed universal RS decoder correcting up to 16 errors can be measured to reach a maximum 1.28 Gb/s data rate at 160 MHz. The total gates count is around 46.4 K with 1.21 mm² silicon area, and the average core power consumption is 68.1 mW.     

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     

Design method of symmetric vector quantiser

A new design algorithm is presented for a symmetric universal vector quantiser based on the successive partitioning of normalised signal space. The universal vector quantiser of video signals is also shown as an example.     

A parallel systems approach to universal receivers

The problem of communication over a channel with unknown characteristics is addressed. The true channel is from a known set of channels, but the transmitter and receiver do not know which of these channels is actually in effect. The goal of a universal receiver is to provide nearly optimal demodulation regardless of the channel that is actually in effect. A parallel receiver implementation is proposed for a universal scheme to cope with such uncertainty. The parallel system consists of a finite number of receivers with the property that, for each channel in the set, the performance of at least one of the receivers will be within a specified performance range. Data verification is accomplished by an appropriate coding system. Sufficient conditions for the existence of such a universal receiver for a prescribed set of channels are established, procedures are outlined for the receiver design, and an example is given to illustrate the applicability of the theory. For M-ary signaling it is shown that, from an information-theoretic viewpoint, the data verification can be achieved at no extra cost by use of the intrinsic side information that is provided by an appropriate coding scheme that also provides error correction     

A sequential algorithm for the universal coding of finite memorysources

The estimation and universal compression of discrete sources are considered, and a sequential algorithm for the universal coding of finite memory sources, attaining asymptotically minimum redundancy, is presented. The algorithm performs an online estimation of the source states and uses an arithmetic code     

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.     

Surrogate-channel design of universal LDPC codes

A universal code is a code that may be used across a number of different channel types or conditions with little degradation relative to a good single-channel code. The explicit design of universal codes, which simultaneously seeks to solve a multitude of optimization problems, is a daunting task. This letter shows that a single channel may be used as a surrogate for an entire set of channels to produce good universal LDPC codes. This result suggests that sometimes a channel for which LDPC code design is simple may be used as a surrogate for a channel for which LDPC code design is complex. We explore here the universality of LDPC codes over the BEC, AWGN, and flat Rayleigh fading channels in terms of decoding threshold performance. Using excess mutual information as a performance metric, we present design results which support the contention that an LDPC code designed for a single channel can be universally good across the three channels.     

The Universal LZ77 Compression Algorithm Is Essentially Optimal for Individual Finite-Length $N$-Blocks

Consider the case where consecutive blocks of N letters of a semi-infinite individual sequence X over a finite alphabet are being compressed into binary sequences by some one-to-one mapping. No a priori information about X is available at the encoder, which must therefore adopt a universal data-compression algorithm. It is known that there exist a number of asymptotically optimal universal data compression algorithms (e.g., the Lempel-Ziv (LZ) algorithm, context tree algorithm and an adaptive Hufmann algorithm) such that when successively applied to N-blocks then, the best error-free compression for the particular individual sequence X is achieved as N tends to infinity. The best possible compression that may be achieved by any universal data compression algorithm for finite N-blocks is discussed. Essential optimality for the compression of finite-length sequences is defined. It is shown that the LZ77 universal compression of N-blocks is essentially optimal for finite N-blocks. Previously, it has been demonstrated that a universal context tree compression of N blocks is essentially optimal as well.     

Efficient universal noiseless source codes

Although the existence of universal noiseless variable-rate codes for the class of discrete stationary ergodic sources has previously been established, very few practical universal encoding methods are available. Efficient implementable universal source coding techniques are discussed in this paper. Results are presented on source codes for which a small value of the maximum redundancy is achieved with a relatively short block length. A constructive proof of the existence of universal noiseless codes for discrete stationary sources is first presented. The proof is shown to provide a method for obtaining efficient universal noiseless variable-rate codes for various classes of sources. For memoryless sources, upper and lower bounds are obtained for the minimax redundancy as a function of the block length of the code. Several techniques for constructing universal noiseless source codes for memoryless sources are presented and their redundancies are compared with the bounds. Consideration is given to possible applications to data compression for certain nonstationary sources.     

Jurgen Habermas “What is universal pragmatics?”

One of the most difficult tasks for any professional communicator is identifying and negotiating the political shoals in an organization. In his essay “What is universal pragmatics?” Habermas (1979) describes a broad, universal concept of pragmatics (the study of language use in a specific situation), one that is useful for analyzing how power affects organizational communication. By exploiting the sociological aspect of Habermas' universal pragmatics, communicators can use his theory to understand how power affects communication in the workplace. I briefly describe Habermas' theory, modify his theory to relate more specifically to communication in an organization, and provide a brief example illustrating the theory's usefulness     

Universal prediction

This paper consists of an overview on universal prediction from an information-theoretic perspective. Special attention is given to the notion of probability assignment under the self-information loss function, which is directly related to the theory of universal data compression. Both the probabilistic setting and the deterministic setting of the universal prediction problem are described with emphasis on the analogy and the differences between results in the two settings     

变长标识统一接入在一体化网络中的研究和实现

首先描述了一体化网络对变长标识接入的需求,在对一体化网络的体系结构以及映射机制进行深入研究的基础上,设计了变长接入标识在一体化网络中的统一接入映射方案,分析了在此方案中32位标识接入到一体化网络时的处理流程,并对其主要功能进行了结构分析与模块设计;最后按照设计方案进行了该方案主体功能的仿真和测试,测试结果和预期分析处理结果一致。     

Universal noiseless coding

Universal coding is any asymptotically optimum method of block-to-block memoryless source coding for sources with unknown parameters. This paper considers noiseless coding for such sources, primarily in terms of variable-length coding, with performance measured as a function of the coding redundancy relative to the per-letter conditional source entropy given the unknown parameter. It is found that universal (i.e., zero redundancy) coding in a weighted sense is possible if and only if the per-letter average mutual information between the parameter space and the message space is zero. Universal coding is possible in a maximin sense if and only if the channel capacity between the two spaces is zero. Universal coding is possible in a minimax sense if and only if a probability mass function exists, independent of the unknown parameter, for which the relative entropy of the known conditional-probability mass-function is zero. Several examples are given to illustrate the ideas. Particular attention is given to sources that are stationary and ergodic for any fixed parameter although the whole ensemble is not. For such sources, weighted universal codes always exist if the alphabet is finite, or more generally if the entropy is finite. Minimax universal codes result if an additional entropy stability constraint is applied. A discussion of fixed-rate universal coding is also given briefly with performance measured by a probability of error.     

On the universality of the LZ-based decoding algorithm

A universal decoder for a family of channels is a decoder that can be designed without prior knowledge of the particular channel in the family over which transmission takes place, and it yet attains the same random-coding error exponent as the optimal decoder tuned to the channel in use. We study Ziv's (1985) decoding algorithm, which is based on Lempel-Ziv (1978) incremental string parsing, and demonstrate that while it was originally proposed as a universal decoder for the family of finite-state channels with deterministic (but unknown) transitions, it is in fact universal for the broader class of all finite-state channels. We also demonstrate that the generalized likelihood decoder may not be universal even for finite families for which a universal decoder always exists     

A new asymptotically optimal code for the positive integers

A new universal binary code for the positive integers is proposed as a modified version of M. Wang's (see ibid., vol.34, p.324-6, Mar. 1988) flag encoding scheme. The codeword length of the new scheme is shorter than Wang's, on an average, for large initial segments of the positive integers. The performance of the new scheme is also compared with that of other universal schemes. Furthermore, it is shown that an asymptotically optimal code can be achieved by modifying the new flag scheme such that the flag length varies dynamically     

A High-Speed Hardware Architecture for Universal Message Authentication Code

We present an architecture level optimization technique called divide-and-concatenate based on two observations: 1) the area of an array multiplier and its associated data path decreases quadratically and their delay decreases linearly as their operand size is reduced and 2) in universal hash functions and their associated message authentication codes, two one-way hash functions are equivalent if they have the same collision probability property. In the proposed approach, we divide a$2w$-bit data path (with collision probability$2^-2w$) into two$w$-bit data paths (each with collision probability$2^-w$) and concatenate their results to construct an equivalent$2w$-bit data path (with a collision probability$2^-2w$). We applied this technique on NH universal hash, a universal hash function that uses multiplications and additions. We implemented the straightforward 32-bit pipelined NH universal hash data path and the divide-and-concatenate architecture that uses four equivalent 8-bit divide-and-concatenate NH universal hash data paths on a Xilinx Virtex II XC2VP7-7 field programmable gate array (FPGA) device. This divide-and-concatenate architecture yielded a 94% increase in throughput with only 40% hardware overhead. Finally, the implementation of universal message authentication code (UMAC) with collision probability$2^-32$using the divide-and-concatenate NH hash as a building block yielded a throughput of 79.2 Gb/s with only 3840 Virtex II XC2VP7-7 FPGA slices.