Recent advances in DNA sequencing technology have caused an exponential growth of publicly available genomic sequence data. A particularly voluminous, frequently used static data set are whole genome alignments. The first lossless compression algorithm for such data sets based on well-established statistical evolutionary models and prediction techniques from lossless binary image compression is introduced. The compression rate is improved by a factor of 1.6 compared to the currently used Lempel-Ziv (LZ) compression.

Information theory--a field at the intersection of applied mathematics and electrical engineering--was primarily developed for the purpose of addressing problems arising in data storage and data transmission over (noisy) communication media. Consequently, information theory provides the formal basis for much of today’s storage and communication infrastructure.

Rapid development of DNA sequencing technologies exponentially increases the amount of publicly available genomic data. Whole genome multiple sequence alignments represent a particularly voluminous, frequently downloaded static dataset. In this work we propose an asymmetric source coding scheme for such alignments using evolutionary prediction in combination with lossless black and white image compression. Compared to the Lempel-Ziv algorithm used so far the compression rates are almost halved.

BACKGROUND: Comparative genomics aims to detect signals of evolutionary conservation as an indicator of functional constraint. Surprisingly, results of the ENCODE project revealed that about half of the experimentally verified functional elements found in non-coding DNA were classified as unconstrained by computational predictions. Following this observation, it has been hypothesized that this may be partly explained by biased estimates on neutral evolutionary rates used by existing sequence conservation metrics. All methods we are aware of rely on a comparison with the neutral rate and conservation is estimated by measuring the deviation of a particular genomic region from this rate. Consequently, it is a reasonable assumption that inaccurate neutral rate estimates may lead to biased conservation and constraint estimates. RESULTS: We propose a conservation signal that is produced by local Maximum Likelihood estimation of evolutionary parameters using an optimized sliding window and present a Kullback-Leibler projection that allows multiple different estimated parameters to be transformed into a conservation measure. This conservation measure does not rely on assumptions about neutral evolutionary substitution rates and little a priori assumptions on the properties of the conserved regions are imposed. We show the accuracy of our approach (KuLCons) on synthetic data and compare it to the scores generated by state-of-the-art methods (phastCons, GERP, SCONE) in an ENCODE region. We find that KuLCons is most often in agreement with the conservation/constraint signatures detected by GERP and SCONE while qualitatively very different patterns from phastCons are observed. Opposed to standard methods KuLCons can be extended to more complex evolutionary models, e.g. taking insertion and deletion events into account and corresponding results show that scores obtained under this model can diverge significantly from scores using the simpler model. CONCLUSION: Our results suggest that discriminating among the different degrees of conservation is possible without making assumptions about neutral rates. We find, however, that it cannot be expected to discover considerably different constraint regions than GERP and SCONE. Consequently, we conclude that the reported discrepancies between experimentally verified functional and computationally identified constraint elements are likely not to be explained by biased neutral rate estimates.

The aim of genetic mapping is to locate the loci responsible for specific traits such as complex diseases. These traits are normally caused by mutations at multiple loci of unknown locations and interactions. In this work, we model the biological system that relates DNA polymorphisms with complex traits as a linear mixing process. Given this model, we propose a new fine-scale genetic mapping method based on independent component analysis. The proposed method outputs both independent associated groups of SNPs in addition to specific associated SNPs with the phenotype. It is applied to a clinical data set for the Schizophrenia disease with 368 individuals and 42 SNPs. It is also applied to a simulation study to investigate in more depth its performance. The obtained results demonstrate the novel characteristics of the proposed method compared to other genetic mapping methods. Finally, we study the robustness of the proposed method with missing genotype values and limited sample sizes.

During the last years, the amount of genetic data available has increased rapidly which creates the demand for advanced techniques for their interpretation. In the following, we present an approach of applying communication theory for biological sequence analysis. We use an analogy to frame synchronization to gain more insights into transcription, the step of copying a gene into messenger RNA (mRNA). In continuous and packet data transmission, successful decoding of a transmitted data stream at the receiver side strongly depends on the choice of the sync word that indicates the beginning of the message and thus needs to be detected reliably. Analogously, biological sync words indicate the beginning of a gene, i.e. they mark the sequence in the DNA that needs to be copied during transcription. These biological sync words are the -35 promoter region and the -10 promoter region named after their approximate position before the gene. In digital data transmission, the sync word is selected from all possible patterns based on its autocorrelation behavior. Therefore, we use an adapted autocorrelation function to investigate the synchronization properties of the promoter regions revealing that the -35 region is an outstanding synchronization pattern. In contrast to that, the -10 region, though more important for transcription initiation, showed to have worse properties. However, when including sequence constraints imposed through the region's importance for transcription, the -10 region showed to be among the best possible sequences, too. These facts imply that during evolution promoter sequences evolved in a way to optimize their synchronization properties.

We consider the problem of estimating the parameters of a convolutional encoder from noisy data observations, i.e. when encoded bits are received with errors. Reverse engineering of a channel encoder has applications in cryptanalysis when attacking communication systems and also in DNA sequence analysis, when looking for possible error correcting codes in genomes. We present a new iterative, probabilistic algorithm based on the Expectation Maximization (EM) algorithm. We use the concept of log-likelihood ratio (LLR) algebra which will greatly simplify the derivation and interpretation of our final algorithm. We show results indicating the necessary data length and allowed channel error rate for reliable estimation.

For iterative detection/decoding (turbo) schemes, we modify sequential decoding, which contrary to a posteriori probability (APP) Bahl-Cocke-Jelinek-Raviv (BCJR) decoding, enjoys a complexity almost independent of the number of states. This novel list-sequential (LISS) decoder avoids most of the drawbacks of the classical sequential decoders, such as variable workload and erased frames when working within a turbo scheme. It uses a metric containing a priori and channel values, a metric length bias term for speeding up the tree search, a soft extension of paths without increasing the stack size, and soft weighting to obtain a soft output. We present several turbo applications using the LISS including equalization, single-antenna interference cancellation, multiuser and multiple-input multiple-output detection. It is shown that the LISS achieves the optimal (genie) or APP performance at a bit-error rate after the outer decoder of less than 10-4, but it also works with channels which have a high number of taps, constellation points, antennas, and states where the APP (BCJR) algorithm becomes infeasible

We introduce an extension of the relay channel that we call two-way relay channel. The two-way relay channel consists of two users which want to communicate to each other with the help of one relay. We consider the time-division two-way relay channel without power control, where the broadcast channels are orthogonalized in time and where the two users and the relay use the same transmission power. We describe a joint network-channel coding method for this channel model, where channel codes are used at both users and a network code is used at the relay. The channel code of one user and the network code form a distributed turbo code which we call turbo network code and which can be iteratively decoded at the other user. Moreover, we conjecture closed expressions for lower bounds for the channel capacities of the time-division relay and two-way relay channel without power control and deliver simulation results of the proposed turbo network code.

Interference cancellation is an important issue since the coverage and capacity in the uplink are mainly interference limited. The interference from the own cell can be mitigated by multiuser detection. However, there does not exist a powerful interference cancellation technique for the interference from neighboring cells, the intercell interference. This work proposes a technique for combating the intercell interference. Since base-stations in wireless systems are connected through a backbone network, we propose the exchange of information through the network between the base-stations, in order to help each other in the detection of the signals. We present several strategies how this could be performed. Especially, we propose an iterative way for reducing the intercell interference: The Turbo Base-Station Cooperation. Simulation results show remarkable gains, especially in the presence of a strong interferer.

Finding the causal genetic regions underlying complex traits is one of the main aims in human genetics. In the context of complex diseases, which are believed to be controlled by multiple contributing loci of largely unknown effect and position, it is especially important to develop general yet sensitive methods for gene mapping. We discuss the use of Shannon's information theory for population-based gene mapping of discrete and quantitative traits and for marker clustering. Various measures of mutual information were employed in order to develop a comprehensive framework for gene mapping analyses. An algorithm aimed at finding so-called relevance chains of causal markers is proposed. Moreover, entropy measures are used in conjunction with multidimensional scaling to visualize clusters of genetic markers. The relevance chain algorithm successfully detected the two causal regions in a simulated scenario. The approach has also been applied to a published clinical study on autoimmune (Graves') disease. Results were consistent with those of standard statistical methods, but identified an additional locus of interest in the promotor region of the associated gene CTLA4. The developed software is freely available at http://www.Int.ei.tum.de/download/InfoGeneMap/.

Coded transmission over channels introducing intersymbol interference in presence of a co-channel interferer and additive white Gaussian noise poses a problem for single antenna receivers. In this context we present a bidirectional list-sequential (LISS) interference canceller which performs joint detection of the desired user and the interferer. The tree-based LISS algorithm is derived from a decoding technique for convolutional codes with high memory, namely sequential decoding, and adapted to the soft-in/soft-out detection problem. Due to bidirectional tree-searching with two independent LISS algorithms, the proposed detector allows parallel processing with a controllable complexity even for high memory channels.

We investigate the effect of channel coding on throughput and energy consumption in uncoordinated distributed (and) wireless networks, e.g. sensor networks. Although the redundancy associated with channel coding causes additional interference in this type of networks, we show that coding can decrease the frame error rate and increase the throughput. Furthermore, we introduce a new measure, which we call the energy based system efficiency. It relates the average throughput to the required transmission energy and allows prediction of the performance of certain coding schemes.

Identifying the causal genetic markers responsible for complex diseases is a main aim in human genetics. In the context of complex diseases, which are believed to have multiple causal loci of largely unknown effect and position, there is a need to develop advanced methods for gene mapping. In this work, we propose a novel algorithm based on independent component analysis for gene mapping. To apply the algorithm, we model the intra-cellular interactions as a mixing process of multiple sources. Results prove the superiority of the proposed algorithm over conventional statistical based methods, and demonstrate yet another successful application of a well known signal processing technique to an important problem in the field of human genetics.

The increase in the availability of genetic data in the last years is prompting the efforts to use tools from communications engineering for the understanding of genetic information. Processes in molecular biology can be modeled through the use of these tools. A communication theory based model for the process of translation in gene expression is proposed. The model is based on the assumption that the ribosome decodes the mRNA sequences using the 3' end of the 16SrRNA molecule as a one dimensional codebook. The biological consistency of the model is proven in the detection of the Shine-Dalgarno signal and the initiation codon for translation initiation. Furthermore, implications on the role of the 16SrRNA 3' end in the complete process of prokaryotic translation are presented and discussed. Interestingly, the obtained results lay out the possibility of an interaction of this part of the ribosome in the process of translation termination. Finally, results obtained via the proposed model are compared with published experimental results for different mutations of the rRNA molecule. Total agreement between both sets of results proves the validity of the proposed model. By means of simulated mutations in the last 13 bases of the 16SrRNA, a global analysis of this part of the ribosome in the process of translation is established. This work illustrates the relevance of communication theory based models for genetic regulatory systems.

Possibilities of using mutual information for classification and content recognition are exploited. Two different mutual information based distance measures are proposed, one for classification and one for content recognition. The measure proposed for classification is shown to be a metric. The influence of compression based estimation methods on the proposed measures is investigated. Several examples of successful applications in the field of genetics are presented.

In this paper, the distribution of mutual information between two discrete random variables is approximated by means of a second-order Taylor series expansion. Approximative expressions for the distribution of mutual information (MI) between independent random variables, conditional MI between conditionally independent variables, and MI between (weakly) dependent random variables are derived. These distributions are functions of the available sample size and the number of realisations of the random variables only; knowledge of the variables' PMF is not required. The results are verified numerically for various cases. Exemplary application ideas in statistics and communications engineering are proposed.

This paper presents the usability of context tree weighting method (CTW) for applications involving content recognition. The CTW method is a statistics-based universal date compression algorithm that is capable of achieving superior performance compared to Lempel-Ziv based algorithms. The concept of context tree freezing after the reference sequence is encoded to avoid learning the memory structure of the appended test sequence is used to modify CTW for content recognition purposes.

We study a list-sequential (LISS) multiuser detector for coded applications in a turbo scheme. Optimal with respect to the bit error rate within that iterative scheme would be an APP detector that calculates the a posteriori probabilities. Unfortunately, this detector suffers from a prohibitively high computational complexity for a large number of users. Therefore, we apply a sequential algorithm operating on a tree that approximates the a posteriori probabilities with reduced complexity. The tradeoff between performance and computational burden can be controlled by the size of the available memory.

The research of Gupta and Kumar (March 2000) gave a proportional relationship of the network capacity. We propose a simple approach to deriving the multihop radio network capacity in this paper. This approach is not only able to give the proportional relationship, but it also presents an explicit formulation of the network capacity as well. The formulation is applicable to both the trend prediction of large network and capacity estimation of a small network. This result is valuable for both the theoretical research and for practical performance estimation of multihop radio network. In addition, the methodology can easily be extended to more complex cases, as illustrated by our three-dimensional study. We also implement an ideal network model to verify the capacity derivation, and theoretically prove that the formula is consistent with the previous research works. From the derivation of the formula, most of the important parameters that affect the capacity are discussed and possible approaches to capacity improvement are proposed.

We consider coded 8-PSK transmissions over intersymbol interference channels with a long impulse response and employ a receiver performing iterative equalization and decoding. This paper also uses the techniques from sequential decoding adapted to the equalization task in a turbo scheme. This list-sequential (LISS) equalizer operates on a tree and approximates the a posteriori probabilities with reduced complexity.

Methods used in information theory can be used in genomic analysis to provide a more meaningful insight into the genetic process. Using an information transfer model between certain polymorphisms in the human genome (SNP) and certain diseases (e.g. Alzheimer), Shannon's mutual information can identify the relevant SNP. Several compression algorithms approximating the entropy of DNA sequences are used to distinguish between introns and exons. Certain distance measures derived from DNA sequences allow classification leading to evolutionary trees. They can also be used for content recognition.

A very flexible transmission system for multimedia over mobile Internet is proposed. For a mobile Internet scenario, a combination of a lossy packet data network and a mobile network is assumed. Conventional solutions are based on a separation of both networks. The new system is able to manage both packet losses and bit errors in a single decoding step without any transcoding. Furthermore, the system can be adapted easily to the current channel states of both networks in a very flexible way with a minimum of signalization overhead. In a simulation example, the performance of the new system is shown for short block-length speech transmission using recursive systematic convolutional codes, and for large block-length data transmission using a parallel concatenated convolutional code.

We investigate bit-interleaved coded modulation with iterative decoding (BICM-ID) for bandwidth efficient transmission, where the bit error rate is reduced through iterations between a multilevel demapper and a simple channel decoder. In order to achieve a significant turbo-gain, the assignment strategy of the binary indices to signal points is crucial. We address the problem of finding the most suitable index assignments to arbitrary, high order signal constellations. A new method based on the binary switching algorithm is proposed that finds optimized mappings outperforming previously known ones.

We investigate an iterative receiver with a linear detector for complex symbols to suppress the co-antenna interference introduced by a multiple input multiple output (MIMO) channel. For generalized MIMO systems, i.e., systems that transmit complex conjugate repetitions as well as the pure data, we show that the standard linear detector has to be replaced by a widely linear (WL) detector. The WL detector consists of four real filters represented by two complex filters for the data symbols and their complex conjugates, respectively. The generalized MIMO transmitter structure allows for a description of the detector that is applicable to many different MIMO systems. Furthermore, we demonstrate that even for systems without complex conjugate repetitions, WL filtering is beneficial in iterative detection.

For iterative detection in systems employing multiple antennas with an outer code we need a MIMO detector delivering a-posteriori capabilities (APP) about the code bits. Full-APP detection would lead to prohibitive complexity; therefore we extend for high-level signals the concept of the sphere decoder using an approach from sequential decoding instead of geometrical considerations. We show how a priori information can be incorporated into the metric, which is then optimized by systematic tree search. Furthermore, we show how the reliability of the resulting L-values can be improved by augmenting the complete search tree. Simulation results show an improved performance over the list sphere decoder.

The turbo principle (iterative decoding between component decoders) is a general scheme, which we apply to joint source-channel decoding. As a realistic example (e.g., speech parameter coding), we discuss joint source-channel decoding for auto-correlated continuous-amplitude source samples. At the transmitter, the source samples are quantized and their indexes are appropriately mapped onto bitvectors. Afterwards, the bits are interleaved and channel-encoded; an AWGN channel is assumed for transmission. The auto-correlations of the source samples act as implicit outer channel codes that are serially concatenated with the inner explicit channel code. Thus, by applying the turbo principle, we can perform iterative decoding at the receiver. As an example, we show that, with a proper bit mapping for a 5-bit quantizer, iterative source-channel decoding saves up to 2 dB in channel SNR or 8 dB in source SNR for an auto-correlated Gaussian source.

We present an analog rotating ring decoder for decoding an LDPC convolutional code. The decoder architecture uses a window of soft received L-values, K time units in the past and K time units in the future, to decode a given bit. The window of 2K+1 time units is arranged in a ring structure, and decoding proceeds in a continuous fashion by rotating around the ring. Simulation results indicate performance almost identical to that achieved with digital decoding.

The transmission of multimedia data over best-effort packet networks has motivated a strong research effort in the area of multiple description coding. While most contributions concentrate on the design of encoders for the erasure channel, this paper considers the transmission of multiple descriptions over a typical wireless link. Assuming that channel state information is available and that the reliability of each transmitted bit is known to the receiver, we present a soft-in/soft-out decoder for a new class of block codes derived from multiple description scalar quantization. The idea of cross decoding multiple descriptions using soft information, can be successfully extended to the concatenation of multiple description codes and convolutional codes. For this case, the application of the turbo principle yields an iterative decoding scheme, which makes use of the correlation between descriptions in a very effective way.

We focus on a trellis-based decoding technique for variable length codes (VLCs) which does not require any additional side information besides the number of bits in the coded sequence. A bit-level soft-in/soft-out decoder based on this trellis is used as an outer component decoder in an iterative decoding scheme for a serially concatenated source/channel coding system. In contrast to previous approaches using this kind of trellis we do not consider the received sequence as a concatenation of variable length codewords, but as one long code word of a (weak) binary channel code which can be soft-in/soft-out decoded. By evaluating the distance properties of selected variable length codes we show that some codes are more suitable for trellis-based decoding than others. Finally we present simulation results which show the performance of the iterative decoding approach.

We consider FEC coded transmit diversity with space-time block codes. We show that all space-time block codes are equivalent in terms of SNR per bit and give a new view on space-time block codes as a transformation of the fading MIMO channel towards a Gaussian SISO channel. Using a simple equivalent channel model we provide analytical results on the BER of uncoded and FEC coded transmit diversity. Finally, we roughly discuss using multiple antennas for transmit diversity or beamforming.

The performance of high-rate tail-biting convolutional codes serially concatenated with generalized partial response channels is studied. The effect of precoders on the overall performance is investigated. Extrinsic information transfer charts are used to guide the selection of appropriate tail-biting codes and precoders. Simulation results for a magnetic recording system modeled as a serial concatenation of tail-biting codes with a generalized partial response channel are presented. In particular, rate-8/9 and -16/17 short- and long-block-length tail-biting codes are studied. In the former case, hard-decision decoded interleaved Reed-Solomon (RS) codes are used as the outer-most code, whereas in the latter case the sector-size tail-biting codes replace the RS codes traditionally used in storage systems. The results indicate that high-rate tail-biting codes deliver significant performance gains when used in conjunction with a rate-1 precoder and iterative detection/decoding. The results also show that long tail-biting codes can outperform hard-decision decoding of RS codes by 2 dB at a sector error rate of approx. 10/sup -4/.

We present two new decoding algorithms that estimate the output (path in the trellis) of a Markov source observed through a discrete memoryless channel with special application to convolutional codes. In a change of paradigm, these decoders do not exclusively aim at a low average error probability, but rather try to maximize the contiguously correct decoded subpath (where a subpath begins with the first symbol) - a concept termed far end error decoding. In addition to path estimation, these decoders provide a reliability about each subpath and, thus, enable us to localize the first decoding error without spending additional redundancy. This approach is motivated by the fact that in many applications it is much more important to deliver only error free data to the source decoder rather than to achieve a low error probability. The significant performance gain possible with this new approach is demonstrated for the example of SPIHT coded images.

The turbo principle has been widely applied to various detection/decoding problems in recent years. Here we show how the general idea can be extended to a communication scheme where a variable length code is used for data compression followed by a channel code to protect the data against channel errors. Iterations are performed between the channel decoder and the decoder for the variable length source code. Since the exchange of extrinsic information is essential for the performance of turbo decoding schemes we describe how EXIT-charts can be applied to predict the performance of the iterative source-channel decoding approach.

Recently, several VLSI implementations of analog decoders have been reported for rate 1/2 tailbiting convolutional codes. The main advantages of analog decoders are much higher decoding speed, smaller chip size and lower power consumption when compared to an equivalent digital decoder. Since many high speed applications require code rates well above 1/2 we focus on high rate tailbiting convolutional codes. For digital decoder implementations it has been shown by C. Weiss and J. Berkmann (see Proc. 3rd ITG Conf. Source and Channel Coding, Munich, Germany, p.199-207, Jan. 2000) that it is advantageous to use the trellis of the dual code which is less complex for high rate codes. The novel analog decoder design proposed in this paper can be seen as a direct analog implementation of the algorithm described by Weiss and Berkman.

For coded data transmission over channels introducing inter-symbol interference, one approach for joint equalization and decoding in the receiver is turbo equalization. We rederive existing linear equalization algorithms applicable to turbo equalization for 2/sup m/-ary signal alphabets and compare their computational complexity. Moreover by evaluating the algorithm performance properly, we select for each iteration the most suitable of the two algorithms with lowest computational complexity and achieve at low bit error rates a performance close to that of optimal approaches for equalization, ie, maximum a-posteriori probability symbol detection.

In this paper we describe a trellis representation of variable length coded data which is capable of being used for bit-level or symbol-level maximum a posteriori (MAP) decoding of variable length codes (VLC). A bit-level soft-input/soft-output module is derived and is applied in an iterative decoding structure consisting of an outer variable length code and an inner convolutional code. Due to their inherent redundancy reversible variable length codes (RVLC) yield good results with this system. We present simulation results in terms of symbol error rate performance when the data is transmitted over a fully interleaved Rayleigh fading channel using BPSK modulation. As measure for the symbol error rate the Levenshtein distance is used which regards the self-synchronizing properties of variable length codes better than a simple symbol-by-symbol comparison.

A variable channel coding scheme for adaptive multi rate (AMR) speech transmission over mobile radio channels is proposed. Although it was developed for the GSM (Global System for Mobile Communications), the basic concept of variable channel coding can be adopted to other digital radio systems. The new AMR concept allows almost wire-line speech quality even for poor channel conditions by dynamically splitting the gross bit rate between source (speech) and channel coding according to the channel quality. In this study we show some new aspects relating to AMR and show the advantage of recursive systematic convolutional (RSC) codes for mobile speech transmission. With some modification they improve not only the bit error rate but also the frame erasure rate. It is derived that RSC codes can be decoded with a "standard" non-systematic Viterbi decoder and a simple transformation. A new powerful approach is employed for the detection of the currently used mode (in-band signaled information) where the mode bits are integrated in a long block and codes gain with their length.

Multimedia transmission has to handle a variety of compressed and uncompressed source signals such as data, text, image, audio, and video. On wireless channels the error rates are high and joint source/channel coding and decoding methods are advantageous. Also, the system architecture has to adapt to the bad channel conditions. Several examples of a joint design are given. We especially advocate the use of rate-compatible punctured systematic recursive convolutional (RCPRSC) codes which are show to lead to a straightforward and versatile unequal error protection (UEP) design. In addition, the high-end receiver could use soft outputs and source-controlled channel decoding for even better performance.

An overview of the many practical applications of channel coding theory in the past 50 years is presented. The following application areas are included: deep space communication, satellite communication, data transmission, data storage, mobile communication, file transfer, and digital audio/video transmission. Examples, both historical and current, are given that typify the different approaches used in each application area. Although no attempt is made to be comprehensive in the coverage, the examples chosen clearly illustrate the richness, variety, and importance of error-control coding methods in modern digital applications.

Iterative decoding is applied to code division multiple access (CDMA) systems with two-stage serial concatenated channel coding. For a direct sequence (DS) CDMA system like in the uplink of the standard IS-95(A) using M-ary orthogonal modulation (inner code) and an outer convolutional code with interleaving we give the optimum symbol-by-symbol maximum a posteriori (MAP) decoding rules for the inner block code in a coherent and noncoherent receiver design. Further suggestions for suboptimum MAP decoders with lower complexity are made. The inner decoding rule is extended to use a priori information for the systematic bits, which is delivered from the outer decoding stage. These algorithms are essential for iterative decoding of the system. Simulation results show a decoding gain of about 0.6 dB for a bit error rate (BER) of 10/sup -3/ by replacing the maximum likelihood (ML) decoder for the inner code by a MAP decoder. A total gain of about 1.2 dB is achieved by the use of iterative decoding after only three to five iterations.

Iterative decoding of two-dimensional systematic convolutional codes has been termed "turbo" (de)coding. Using log-likelihood algebra, we show that any decoder can be used which accepts soft inputs-including a priori values-and delivers soft outputs that can be split into three terms: the soft channel and a priori inputs, and the extrinsic value. The extrinsic value is used as an a priori value for the next iteration. Decoding algorithms in the log-likelihood domain are given not only for convolutional codes but also for any linear binary systematic block code. The iteration is controlled by a stop criterion derived from cross entropy, which results in a minimal number of iterations. Optimal and suboptimal decoders with reduced complexity are presented. Simulation results show that very simple component codes are sufficient, block codes are appropriate for high rates and convolutional codes for lower rates less than 2/3. Any combination of block and convolutional component codes is possible. Several interleaving techniques are described. At a bit error rate (BER) of 10/sup -4/ the performance is slightly above or around the bounds given by the cutoff rate for reasonably simple block/convolutional component codes, interleaver sizes less than 1000 and for three to six iterations.

Source and channel coding have been treated separately in most cases. It can be observed that most source coding algorithms for voice, audio and images still have correlation in certain bits. Transmission errors in these bits usually account for the significant errors in the reconstructed source signal. This paper proposes a modification of the Viterbi decoding algorithm (VA) for binary trellises which uses a priori or a posteriori information about the source bit probability for better decoding in addition to soft inputs and channel state information. Analytical upper bounds for the BER of convolutional codes for this modified VA (APRI-VA) are given. The algorithm is combined with the soft output viterbi algorithm (SOVA) and an estimator for the residual correlation of the source bits to achieve source-controlled channel decoding for framed source bits. The description is simplified by an algebra for the log-likelihood ratio L(u)=log(P(u=+1)/P(u=-1)) which allows a clear definition of the "soft" values of source-, channel-, and decoded bits as well as a simplified description of the traceback version of the SOVA. Applications are given for PCM transmission and the full rate GSM speech codec. For an PCM coded oversampled bandlimited Gaussian source transmitted over Gaussian and Rayleigh channels with convolutional codes the decoding errors are reduced by a factor of 4 to 5 when the APRI-SOVA is used instead of the VA. A simple dynamic Markov correlation estimator is used. With these receiver-only modifications the channel SNR in a bad mobile environment can be lowered by 2 to 4 dB resulting in the same voice quality. Further applications are briefly discussed.>

The unequal error protection capabilities of convolutional codes belonging to the family of rate-compatible punctured convolutional codes (RCPC codes) are studied. The performance of these codes is analyzed and simulated for the first fading Rice and Rayleigh channels with differentially coherent four-phase modulation (4-DPSK). To mitigate the effect of fading, interleavers are designed for these unequal error protection codes, with the interleaving performed over one or two blocks of 256 channel bits. These codes are decoded by means of the Viterbi algorithm using both soft symbol decisions and channel state information. For reference, the performance of these codes on a Gaussian channel with coherent binary phase-shift keying (2-CPSK) is presented. A number of examples are provided to show that it is possible to accommodate widely different error protection levels within short information blocks. Unequal error protection codes for a subband speech coder are studied in detail. A detailed study of the effect of the code and channel parameters such as the encoder memory, the code rate, interleaver depth, fading bandwidth, and the contrasting performance of hard and soft decisions on the received symbols is provided.>

By using codes of rate 2/3 followed by 8-PSK modulation, a gain of 3-6 dB is obtained over uncoded 4-PSK, for an ideal coherent transmission on the white Gaussian channel. In the presence of carrier phase offset, it has been shown that trellis-coded 8-PSK systems are more sensitive than uncoded 4-PSK. A more robust performance can be achieved by using rate 2/3 trellis-coded 8-PSK signals and 4-PSK signals in a time-varying manner. Only the mapper from the output of the binary convolutional code to the signal point number to be transmitted has to be periodically time-varying. In its simplest form, trellis-coded 8-PSK and 4-PSK signals alternate in time. An examination has also been made of systems where the mixture of 8-PSK and 4-PSK signals varies, with a short periodic sequence of time-varying mapping rules. The distance spectra and error probability are evaluated with and without phase offset. Simulation results of bit error rate (BER) and performance of the recovery loop (S curve) are presented. It is concluded that systems which are more robust against jitter can be achieved by means of time-varying hybrid trellis-coded 8/4-PSK systems.>

The coder is a dynamic bit allocation sub-band coder of the type first proposed by Ramstad (1982). It is structured in such a way that the relative importance of all bits is established as a byproduct of the dynamic bit allocation. It is shown that there is a difference in error sensitivity of four orders of magnitude between the most and the least important bits of the bit stream on average. A very flexible unequal error protection scheme is used to match the error sensitivity of the sub-band coder bit stream. This is accomplished using the concept of rate compatible punctured convolutional coding. The resulting coder gives robust performance over a simulated noisy channel. Its nominal bit rate is 16 kb/s, with 12 kb/s assigned for speech coding and 4 kb/s assigned for error correction. The entire encoder and decoder have been implemented on a single AT&T DSP-32 digital signal processor.>

The concept of punctured convolutional codes is extended by punctuating a low-rate 1/N code periodically with period P to obtain a family of codes with rate P/(P+l), where l can be varied between 1 and (N-1)P. A rate-compatibility restriction on the puncturing tables ensures that all code bits of high rate codes are used by the lower-rate codes. This allows transmission of incremental redundancy in ARQ/FEC (automatic repeat request/forward error correction) schemes and continuous rate variation to change from low to high error protection within a data frame. Families of RCPC codes with rates between 8/9 and 1/4 are given for memories M from 3 to 6 (8 to 64 trellis states) together with the relevant distance spectra. These codes are almost as good as the best known general convolutional codes of the respective rates. It is shown that the same Viterbi decoder can be used for all RCPC codes of the same M. the application of RCPC codes to hybrid ARQ/FEC schemes is discussed for Gaussian and Rayleigh fading channels using channel-state information to optimise throughput.>

Towards the year 2000, maritime satellite communications using the INMARSAT system will employ a second and third generation of satellites and new ship earth stations (SES). The new SES standards will use very small antennas with gains between 0 and 15 dBi. At the lower end of SES there will be no antenna stabilization. The communication channel for such small stations is described by a model including multipath fading, Doppler shift, and noise. The results of an extensive measurement program were used to determine the parameters of the channel model, which depend on antenna type and elevation angle. Analytical calculations as well as synthetic and stored channel hardware simulations have been used to determine the performance of several modulation schemes. A complete data link using PSK modems with AFC/Costas loop, interleaving, and FEC codecs at 1.2 kbits/s was built up around a hardware maritime channel simulator, to study the performance of data transmission on the small SES maritime channel. Theoretical and measured results are given for interleaved Viterbi decoding with channel state information and Reed-Solomon codes. The measurements show that with interleaved FEC schemes, the requiredE_{b}/N_{o}for a BER 10-5is in the range of 9-15 dB and the effects of multipath fading are almost compensated for.

Fading in mobile satellite communications severely degrades the performance of data transmission. The channel is modeled with nonfrequency selective Rice and Rayleigh fading. Also, stored channel simulation is used for hardware data transmission. FEC coding with Viterbi decoding of convolutional codes, and Berlekamp-Massey decoding of Reed-Solomon codes, are used to compensate for the fading. In addition to interleaving, channel state and erasure information improve the performance of the decoder. The BER after decoding is calculated for specific codes on several channels and for different transmission schemes. Using very simple channel state and erasure information gives 2-7 dB additional coding gain. These gains have been verified by hardware data transmission on synthetic fading channels and stored mobile satellite channels.

The result of a computer search for systematic convolutional codes with rates(N - 1)/NforNfrom 3 to 8 is presented. The codes have rapidly growing column distance, making them attractive for sequential decoding.