On the Structure of Optimal Real-Time Encoders and Decoders in Noisy Communication

The output of a discrete-time Markov source must be encoded into a sequence of discrete variables. The encoded sequence is transmitted through a noisy channel to a receiver that must attempt to reproduce reliably the source sequence. Encoding and decoding must be done in real-time and the distortion measure does not tolerate delays. The structure of real-time encoding and decoding strategies that jointly minimize an average distortion measure over a finite horizon is determined. The results are extended to the real-time broadcast problem and a real-time variation of the Wyner-Ziv problem     

On finite-state vector quantization for noisy channels

Finite-state vector quantization (FSVQ) over a noisy channel is studied. A major drawback of a finite-state decoder is its inability to track the encoder in the presence of channel noise. In order to overcome this problem, we propose a nontracking decoder which directly estimates the code vectors used by a finite-state encoder. The design of channel-matched finite-state vector quantizers for noisy channels, using an iterative scheme resembling the generalized Lloyd algorithm, is also investigated. Simulation results based on encoding a Gauss-Markov source over a memoryless Gaussian channel show that the proposed decoder exhibits graceful degradation of performance with increasing channel noise, as compared with a finite-state decoder. Also, the channel-matched finite-state vector quantizers are shown to outperform channel-optimized vector quantizers having the same vector dimension and rate. However, the nontracking decoder used in the channel-matched finite-state quantizer has a higher computational complexity, compared with a channel-optimized vector-quantizer decoder. Thus, if they are allowed to have the same overall complexity (encoding and decoding), the channel-optimized vector quantizer can use a longer encoding delay and achieve similar or better performance. Finally, an example of using the channel-matched finite-state quantizer as a backward-adaptive quantizer for nonstationary signals is also presented.     

Joint source and noisy channel trellis encoding (Corresp.)

In a trellis encoding communication system the decoder is a time-invariant nonlinear filter with finite memory (sliding-block code), and the encoder is a trellis search algorithm matched to the decoder. A coding theorem is established for a trellis encoding of a stationary and ergodic source over a discrete memoryless noisy channel which shows that such communication systems can perform arbitrarily close to the source distortion-rate function evaluated at the channel capacity.     

Efficient source decoding over memoryless noisy channels using higher order Markov models

Exploiting the residual redundancy in a source coder output stream during the decoding process has been proven to be a bandwidth-efficient way to combat noisy channel degradations. This redundancy can be employed to either assist the channel decoder for improved performance or design better source decoders. In this work, a family of solutions for the asymptotically optimum minimum mean-squared error (MMSE) reconstruction of a source over memoryless noisy channels is presented when the redundancy in the source encoder output stream is exploited in the form of a /spl gamma/-order Markov model (/spl gamma//spl ges/1) and a delay of /spl delta/,/spl delta/>0, is allowed in the decoding process. It is demonstrated that the proposed solutions provide a wealth of tradeoffs between computational complexity and the memory requirements. A simplified MMSE decoder which is optimized to minimize the computational complexity is also presented. Considering the same problem setup, several other maximum a posteriori probability (MAP) symbol and sequence decoders are presented as well. Numerical results are presented which demonstrate the efficiency of the proposed algorithms.     

A note on feedback communication with noisy side information at the receiver (Corresp.)

A feedback communication system which has noisy side information at the receiver is considered. The estimation scheme is a simple extension of the conventional one without side information. The resulting mean-squared error is compared with the rate-distortion bound obtained recently by Wyner and Ziv.     

DPCM picture transmission over noisy channels with the aid of aMarkov model

The problem of DPCM picture transmission over noisy channels is considered. It is well known that DPCM systems are very sensitive to channel errors. The goal in this work is to build robustness against channel errors. Three methods are proposed in this paper and are obtained by modeling the encoded signal as a Markov sequence. First, an optimum method for decoding correlated sequences is derived, and it is shown to require Viterbi decoding. Then, a modified MAP method (MMAP) for Markov sequences is described. A maximal signal-to-noise (MSNR) receiver for DPCM systems is also developed that minimizes the distortion power due to channel errors. The appropriate cost matrix for this receiver is computed. These methods are applied to DPCM picture transmission over noisy channels and are compared with a another method. The SNR graphs, as well as subjective examination of the received pictures, demonstrate that the proposed procedures are quite effective and superior to that method. Among the proposed methods, the MSNR receiver was found to be more effective than the others for a given order of the Markov model. It is observed that the proposed methods are most beneficial for low detail pictures.     

Alphabet-constrained data compression

The optimal data compression problem is posed in terms of an alphabet constraint rather than an entropy constraint. Solving the optimal alphabet-constrained data compression problem yields explicit source encoder/decoder designs, which is in sharp contrast to other approaches. The alphabet-constrained approach is shown to have the additional advantages that (1) classical waveform encoding schemes, such as pulse code modulation (PCM), differential pulse code modulation (DPCM), and delta modulation (DM), as well as rate distortion theory motivated tree/trellis coders fit within this theory; (2) the concept of preposterior analysis in data compression is introduced, yielding a rich. new class of coders: and (3) it provides a conceptual framework for the design of joint source/channel coders for noisy channel applications. Examples are presented of single-path differential encoding, delayed (or tree) encoding, preposterior analysis, and source coding over noisy channels.     

Optimum linear coding in continuous-time communication systems with noisy side information at the decoder (Corresp.)

The problem of optimal coding in a communication system with a noiseless feedback link and with noisy side information at the decoder is treated. The message is taken as a Gaussian random variable and both the main and the side channels are assumed to be continuous white-Gaussian. A linear encoding-decoding scheme is developed which attains the well-known performance bounds for the special cases of i) noiseless side information and ii) no side information.     

Sequence MAP decoding of trellis codes for Gaussian and Rayleighchannels

This paper considers the use of sequence maximum a posteriori (MAP) decoding of trellis codes. A MAP receiver can exploit any “residual redundancy” that may exist in the channel encoded signal in the form of memory and/or a nonuniform distribution, thereby providing enhanced performance over very noisy channels, relative to maximum likelihood (ML) decoding. The paper begins with a first-order two-state Markov model for the channel encoder input. A variety of different systems with different source parameters, different modulation schemes, and different encoder complexities are simulated. Sequence MAP decoding is shown to substantially improve performance under very noisy channel conditions for systems with low-to-moderate redundancy, with relative gain increasing as the rate increases. As a result, coding schemes with multidimensional constellations are shown to have higher MAP gains than comparable schemes with two-dimensional (2-D) constellations. The second part of the paper considers trellis encoding of the code-excited linear predictive (CELP) speech coder's line spectral parameters (LSPs) with four-dimensional (4-D) QPSK modulation. Two source LSP models are used. One assumes only intraframe correlation of LSPs while the second one models both intraframe and interframe correlation. MAP decoding gains (over ML decoding) as much as 4 dB are achieved. Also, a comparison between the conventionally designed codes and an I-Q QPSK scheme shows that the I-Q scheme achieves better performance even though the first (sampler) LSP model is used     

Precoding and Decoding Paradigms for Distributed Vector Data Compression

In this paper, we consider the problem of lossy coding of correlated vector sources with uncoded side information available at the decoder. In particular, we consider lossy coding of vector source xisinR^N which is correlated with vector source yisinR^N, known at the decoder. We propose two compression schemes, namely, distributed adaptive compression (DAC) and distributed universal compression (DUC) schemes. The DAC algorithm is inspired by the optimal solution for Gaussian sources and requires computation of the conditional Karhunen-Loegraveve transform (CKLT) of the data at the encoder. The DUC algorithm, however, does not require knowledge of the CKLT at the encoder. The DUC algorithms are based on the approximation of the correlation model between the sources y and x through a linear model y=Hx+n in which H is a matrix and n is a random vector and independent of x. This model can be viewed as a fictitious communication channel with input x and output y. Utilizing channel equalization at the receiver, we convert the original vector source coding problem into a set of manageable scalar source coding problems. Furthermore, inspired by bit loading strategies employed in wireless communication systems, we propose for both compression schemes a rate allocation policy which minimizes the decoding error rate under a total rate constraint. Equalization and bit loading are paired with a quantization scheme for each vector source entry (a slightly simplified version of the so called DISCUS scheme). The merits of our work are as follows: 1) it provides a simple, yet optimized, implementation of Wyner-Ziv quantizers for correlated vector sources, by using the insight gained in the design of communication systems; 2) it provides encoding schemes that, with or without the knowledge of the correlation model at the encoder, enjoy distributed compression gains     

Hadamard-based soft decoding for vector quantization over noisychannels

We present an estimator-based, or soft, vector quantizer decoder for communication over a noisy channel. The decoder is optimal according to the mean-square error criterion, and Hadamard-based in the sense that a Hadamard transform representation of the vector quantizer is utilized in the implementation of the decoder. An efficient algorithm for optimal decoding is derived. We furthermore investigate suboptimal versions of the decoder, providing good performance at lower complexity. The issue of joint encoder-decoder design is considered both for optimal and suboptimal decoding. Results regarding the channel distortion and the structure of a channel robust code are also provided. Through numerical simulations, soft decoding is demonstrated to outperform hard decoding in several aspects     

Bit-estimate based decoding for vector quantization over noisychannels with intersymbol interference

We introduce new techniques for quantization over noisy channels with intersymbol interference. We focus on the decoding problem, and present a decoder structure that allows the decoding to be based on soft minimum mean square-error estimates of the transmitted bits. The new bit-estimate based decoder provides a structured lower-complexity approximation of optimal decoding for general codebooks, and for so-called linear mapping codebooks, it is shown that its implementation becomes particularly simple. We investigate decoding based on optimal bit-estimates, and on suboptimal estimates of lower computational complexity. We also consider encoder optimization and combined source-channel code design. Numerical simulations demonstrate that bit-estimate based decoding is able to outperform a two-stage decision-based approach implemented using Viterbi sequence detection plus table look-up source decoding. The simulations also show that decoding based on suboptimal bit-estimates performs well, at a considerably lowered complexity     

On feedback and the classical capacity of a noisy quantum channel

In Shannon information theory, the capacity of a memoryless communication channel cannot be increased by the use of feedback from receiver to sender. In this correspondence, the use of classical feedback is shown to provide no increase in the unassisted classical capacity of a memoryless quantum channel when feedback is used across nonentangled input states, or when the channel is an entanglement-breaking channel. This gives a generalization of the Shannon theory for certain classes of feedback protocols when transmitting through noisy quantum communication channels.     

Linear Precoders for Bit-Interleaved Coded Modulation on AWGN Channels: Analysis and Design Criteria

This paper investigates linear precoding for bit-interleaved coded modulation (BICM) on additive white Gaussian noise (AWGN) channels. Concatenating a linear precoder as an inner encoder with an outer (convolutional) encoder produces a powerful code with a limited decoding complexity. Linear precoders are examined and optimized for two scenarios: using (i) a noniterative decoding strategy and (ii) an iterative decoding strategy under a perfect feedback assumption. The precoder design is based on an information-theoretical approach, on the one hand, and a pair-wise error probability (PEP) analysis, on the other hand. Both approaches render convenient precoder design rules. For a binary phase-shift keying (BPSK) signal set, the optimal precoders that result from these rules are also derived. Numerical results confirm the analytical findings and simulations illustrate the effectiveness of the approach.     

Adaptive communication receivers

This paper describes the results of an investigation of some communication receivers whose response to an input signal changes in a manner determined by the input signal. The problem considered is the design of a communication receiver to receive a message which is coded intoMfixed unknown signal waveforms and transmitted through a noisy channel. An optimal (minimum probability of error at each time interval) receiver is derived which has an exponentially growing structure. It requires(M - 1)M^{n-1}subsystems to receive thenth message symbol. The derivation suggests forms of adaptive receivers which need a more practical amount of equipment to implement, which we call the gremlin and the decision-directed adaptive receiver. The gremlin receiver is a taught-learning machine since, after it makes a decision, a gremlin tells it what the correct decision was. The decision-directed receiver is a self-taught learning machine, using its own output instead of a gremlin's. It is shown that the gremlin receiver converges to a matched filter for the unknown signal and that, in any practical case, the decision-directed receiver performs almost as well. Finally, some results of an experimental simulation of the decision-directed receiver are presented. A plot of the relative frequency of error vs. time is given for a number of different signal-to-noise ratio's (SNR's).     

Gaussian degraded relay channel with lossy state reconstruction

We consider a state reconstruction problem where the additive state process to a Gaussian degraded relay channel (GRC) is to be reconstructed at the receiver subject to some distortion/fidelity constraints. The state process we consider is Gaussian, independent and identically distributed (i.i.d.) and known a priori at the encoder as well as the relay. The receiver has to perform a lossy estimation of the state process, to within some prescribed distortion tolerance under a squared error distortion criterion. The setting also involves communicating messages across to the receiver, in addition to the estimation. Naturally, there is a tension between communication rate and state reconstruction fidelity. We are interested in the optimal trade-off between the distortion incurred at the receiver versus the rate at which messages can be communicated. We provide a complete characterization of the optimal rate versus distortion performance. The main contribution of the paper is a characterization of the fundamental limits of achievable rate versus distortion pairs in the Gaussian degraded relay model under consideration.     

水下光通信防恶性码卷积码设计

为了防止在水下光通信系统中激光器发送长"0"或长"1"信号序列,避免通信系统发生无穷多个比特错误,采用一种新的卷积码编码方案,进行了编码设计和Viterbi译码理论分析与误比特性能仿真验证,用VHDL语言实现了编码器现场可编程门阵列设计,得到了编码系统与未编码系统的误比特率和达到同样误码性能所需的信噪比。结果表明,这种编码能够降低水下无线光通信系统的误比特率,提高通信的可靠性,降低系统对信噪比的需求。     

通信系统中卷积码编解码器的VHDL实现

卷积码作为通信系统中重要的编码方式,以其良好的编码性能,合理的译码方法,被广泛应用。在阐述卷积码编解码器基本工作原理的基础上,给出了（3,1,2）卷积编码器和（2,1,1）卷积解码器的VHDL设计,在QuartusII环境下进行了波形仿真,并下载到EPF10K10LC84-3上进行了验证,其结果表明了该编解码器的正确性和合理性。     

Coding for noisy channels with input-dependent insertions

Tree encoding and sequential decoding are considered for noisy channels that respond a random number of times to each input. Such channels appear in mathematical models of certain speech recognition systems. The decoding error probability and the channel capacity are bounded by extension of the methods of Jelinek and Zigangirov to noisy multilevel channels with input-dependent insertions. Certain analytical difficulties peculiar to the channels in question are indicated.     

Confidential communication scheme based on uncertainty of underwater noisy channels

Aiming at the influence of the uncertainty of underwater noise on information transmission and the security problem of the communication over noisy channels,a confidential communication scheme based on the uncertainty of underwater noisy channels was proposed.The proposed scheme was composed of an interactive key extraction protocol based on Godel’s code and a privacy amplification protocol based on r-circulant Toeplitz matrix.During the process of key extraction,the key sequence comparing number was reduced through the Godel’s code.When calculating the key length after privacy amplification,the uncertainty of underwater noise was considered to make the proposed scheme more practical.Experimental results show that under the condition of satisfying protocol security,it takes 11.99 s to transmit 119 940 bit string where the lower bound of the generated secret key length is 117 331 bit after privacy amplification and the upper bound of the adversary’s information about the secret key is 2 609 bit.Moreover,the proposed scheme (nt+s)×(nt+s)-order r-circulant Toeplitz matrix decreases(nt+s)-1 bit memory space compared to the traditional Toeplitz matrix with the same order.