A Generalization of the Blahut–Arimoto Algorithm to Finite-State Channels

The classical Blahut-Arimoto algorithm (BAA) is a well-known algorithm that optimizes a discrete memoryless source (DMS) at the input of a discrete memoryless channel (DMC) in order to maximize the mutual information between channel input and output. This paper considers the problem of optimizing finite-state machine sources (FSMSs) at the input of finite-state machine channels (FSMCs) in order to maximize the mutual information rate between channel input and output. Our main result is an algorithm that efficiently solves this problem numerically; thus, we call the proposed procedure the generalized BAA. It includes as special cases not only the classical BAA but also an algorithm that solves the problem of finding the capacity-achieving input distribution for finite-state channels with no noise. While we present theorems that characterize the local behavior of the generalized BAA, there are still open questions concerning its global behavior; these open questions are addressed by some conjectures at the end of the paper. Apart from these algorithmic issues, our results lead to insights regarding the local conditions that the information-rate-maximizing FSMSs fulfill; these observations naturally generalize the well-known Kuhn-Tucker conditions that are fulfilled by capacity-achieving DMSs at the input of DMCs.     

On the Static Resolution of Digitally Corrected Analog-to-Digital and Digital-to-Analog Converters With Low-Precision Components

This semi-tutorial paper considers the effect of component mismatch on the static accuracy of analog-to-digital converters (ADCs) and digital-to-analog converters (DACs) with digital correction. First, it is noted that the effective static resolution of flash ADCs is not much reduced by component mismatch: with proper digital correction, the loss due to mismatch is only about 1.3 bit, virtually independently of the mismatch level unless the mismatch is very small. Second, it is noted that current steering DACs may actually benefit from component mismatch. Moreover, with proper digital correction, current steering DACs can achieve an effective static resolution of m bits with as few as m+2 near-unit low-precision current sources     

A practical reliability metric for block codes used on binary-inputchannels

A reliability metric (RM) for a block code is defined to be a function that operates on both the decoder input (a block of channel output) and the decoder output (the codeword estimate) and produces a real number as a measure of the reliability of the decoder decision. The best RM has the disadvantage of depending on the codeword probabilities. Thus, the ideal RM is defined as the value that would be computed for equally likely codewords. The implementation of the ideal RM is too costly for most applications. The author proposes an easily implemented RM for binary-input memoryless channels (for state-observable channels with a freely evolving state such as some fading channels) when the codewords consist of n 2^m-ary symbols, each of which is transmitted serially by m uses of the channel. Simulation results for some BCH codes and some Reed-Solomon codes used in a simple ARQ system show that the proposed RM performs nearly as well as the ideal RM and much better than a previously proposed practical RM     

Probability propagation and decoding in analog VLSI

The sum-product algorithm (belief/probability propagation) can be naturally mapped into analog transistor circuits. These circuits enable the construction of analog-VLSI decoders for turbo codes, low-density parity-check codes, and similar codes     

Cascode Configurations for Switched Current Copiers

Various cascode circuits are investigated with regard to their suitability for switched current copier applications. A generalized circuit representation for cascodes is introduced and different cascode circuits are compared with respect to their small-signal parameters as well as their associated dynamic output ranges. A method called reference voltage and current tracking for dynamic output range improvement is proposed. An improved regulated cascode circuit with extended dynamic output range using reference current tracking and level shifting technique is presented. The dynamic output ranges of cascode circuits used in switched current copiers are discussed in detail and the corresponding saturation operating areas are compared. The results are applied to typical switched-current circuits and the use of cascodes in switched-current applications with cascaded current copier cells is investigated.     

Signal sets matched to groups

Recently, linear codes over Z_M (the ring of integers mod M) have been presented that are matched to M -ary phase modulation. The general problem of matching signal sets to generalized linear algebraic codes is addressed based on these codes. A definition is given for the notion of matching. It is shown that any signal set in N-dimensional Euclidean space that is matched to an abstract group is essentially what D. Slepian (1968) called a group code for the Gaussian channel. If the group is commutative, this further implies that any such signal set is equivalent to coded phase modulation with linear codes over Z_M. Some further results on such signal sets are presented, and the signal sets matched to noncommutative groups and the linear codes over such groups are discussed     

Molecular variant of factor VII

1. The inhibitory effects of T-2 toxin and trichodermin on poly(U)-directed polyphenylalanine synthesis were studied by using cell-free systems from reticulocytes. Conditions for amino acid incorporation were carefully chosen in an attempt to ensure that the large majority of poly(U) chains bound only one ribosome engaged in protein synthesis and that all such ribosomes carried nascent polyphenylalanine chains containing approximately the same number of residues. 2. Cell-free systems were allowd to synthesize polyphenylalanine, and T-2 toxin and trichodermin were added to the incorporation mixtures at various times. Irrespective of the time of addition, trichodermin (50 mug/ml) inhibited polyphenylalanine synthesis by approx. 70%. In contrast, although T-2 toxin (40 mug/ml), when added at early incubation times, could inhibit polyphenylalanine synthesis with a maximum of 50%, the drug had no effect on the system when added after a critical time-period. 3. It is concluded that although both T-2 toxin and trichodermin can inhibit peptide-bond formation on ribosomes at the level of the peptidyl transferase catalytic centre the presence, on ribosomes, of nascent polyphenylalanine chains above a certain critical chain length excludes T-2 toxin from functional interaction with its receptor site.     

Factor graphs and the sum-product algorithm

Algorithms that must deal with complicated global functions of many variables often exploit the manner in which the given functions factor as a product of “local” functions, each of which depends on a subset of the variables. Such a factorization can be visualized with a bipartite graph that we call a factor graph, In this tutorial paper, we present a generic message-passing algorithm, the sum-product algorithm, that operates in a factor graph. Following a single, simple computational rule, the sum-product algorithm computes-either exactly or approximately-various marginal functions derived from the global function. A wide variety of algorithms developed in artificial intelligence, signal processing, and digital communications can be derived as specific instances of the sum-product algorithm, including the forward/backward algorithm, the Viterbi algorithm, the iterative “turbo” decoding algorithm, Pearl's (1988) belief propagation algorithm for Bayesian networks, the Kalman filter, and certain fast Fourier transform (FFT) algorithms     

The Factor Graph Approach to Model-Based Signal Processing

The message-passing approach to model-based signal processing is developed with a focus on Gaussian message passing in linear state-space models, which includes recursive least squares, linear minimum-mean-squared-error estimation, and Kalman filtering algorithms. Tabulated message computation rules for the building blocks of linear models allow us to compose a variety of such algorithms without additional derivations or computations. Beyond the Gaussian case, it is emphasized that the message-passing approach encourages us to mix and match different algorithmic techniques, which is exemplified by two different approaches - steepest descent and expectation maximization - to message passing through a multiplier node.