RATE ALLOCATION FOR MARKOV MODEL AIDED CONVOLUTIONAL CODING OF VECTOR QUANTIZED IMAGE DATA by XIAOPING LIN B.Sc. (Electrical Engineering), Zhejiang University, China, 1993 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLffiD SCEENCE in THE FACULTY OF GRADUATE STUDIES DEPARTMENT OF ELECTRICAL ENGINEERING We accept this thesis as conforming to the required standard T H E UNIVERSITY OF BRITISH COLUMBIA Feb 2000 © Xiaoping Lin, 2000 In presenting degree this thesis in at the University of partial fulfilment British Columbia, of the requirements for an advanced I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of department this or thesis by publication of this for scholarly his thesis or her purposes may representatives. for financial gain shall be It is not granted by understood the head that be allowed without of my copying or my written permission. Department of H ttcifCCCx^L The University of British Columbia Vancouver, Canada Date DE-6 (2/88) AfOY+t 12 &Hcj r Co^yfyv^e e V v ^^Cflh. CucVc viee y V n t 3 Abstract This thesis proposes an optimally rate allocated image transmission system that uses Vector Quantization (VQ) for source coding, and a family of variable rate Punctured Convolutional Codes (PCCs) for channel coding. At the receiver, we apply the source aided channel decoding technique known as Markov Model Aided Decoding (MMAD). Our optimality criterion is to maximize the average end-to-end Reconstruction Signal-to-Noise Ratio (RSNR) under the constraints of a fixed information rate (in pixels per second) and a fixed transmission bandwidth. For a given channel SNR, this joint source-channel coder design achieves the optimal rate allocation between the source coding and the channel coding operations. Compared with the conventional rate allocated system (the analogous system that does not use MMAD), the proposed system gives significant performance improvement. This is due to the fact that M M A D increases the strength of the channel codes, thus allowing the system to allocate more rate to the source coder, which results in a higher resolution image. In the course of our study, we first investigate MMAD without explicit channel coding for VQ image transmission over the noisy memoryless channels comprising the Binary Symmetric Channel (BSC) and the Additive White Gaussian Noise (AWGN) channel. In order to evaluate the effects of the order of the Markov model of the data, we consider two types of decoding algorithms. One is based on the Viterbi sequence decoding algorithm, the other is based on the Bahl, Cocke, Jelinek and Raviv (BCJR) decoding algorithm. The former is computationally less complex, and is optimal (in the sense of minimizing the Bit Error Rate (BER)) for decoding with a first order (O(l)) model; while the latter allows an efficient, but slightly sub-optimal, decoding algorithm for decoding with a second order (0(2)) model. We find that most of the M M A D ii coding gain is already achieved by using the 0(1) model, and therefore in the remainder of the study consider it only. We go on to analyze two types of O(l) M M A D with Convolutional Codes (CCs) employed for explicit channel coding. We call the decoders Markov Model Aided Convolutional Decoders (MMACDs), and show via simulation that the performance benefits attained by using the Markov model are similar to the large gains found for M M A D without explicit channel coding. One type of M M A C D is based on the Viterbi algorithm, and applies a trellis merging technique. This decoder has an optimal BER performance, but has the constraint that the length of the source codewords be less than the memory of the CC. The other MMACD is a concatenation of a soft-output channel decoder followed by an M M A D without channel coding. This decoder does not have the constraint on the length of the source codewords, but has less coding gain than the trellis merged decoder. Finally, we investigate the problem of optimal rate allocation between the source coding and the channel coding for VQ/PCC transmission systems that employ M M A D . Our simulation results over the AWGN channel show that the optimal rate allocated system is superior in RSNR performance to the optimally rate allocated system without M M A D . The M M A D coding gain depends on the image, but is typically 2 dB in channel SNR. We find that for the conventional system, the point of optimal rate allocation is fairly independent of the image; while for the M M A D system the allocation depends strongly on the image characteristics. Because of this, the rate allocation calculation is significantly more complicated when using M M A D . The rate allocated systems require an estimate of the channel SNR. Because in practice there will always be some inaccuracy in estimating this, to conclude our study we investigate the sensitivity of the iii rate allocated systems to channel mismatch, and find them to be fairly robust. iv Table of Contents Abstract ii List of Tables vii List of Figures viii Acknowledgments x Chapter 1 Introduction 1 1.1 Motivation and Objectives 1 1.2 Thesis Outline Chapter 2 • 4 Vector Quantization 7 2.1 The LBG Design Algorithm 8 2.2 Index Assignment 12 2.2.1 The Growth Algorithm 13 2.2.2 Natural Binary Codes from the Splitting Algorithm 16 Markov Model Aided Decoding without Explicit Channel Coding 21 M M A D Based on the Viterbi Algorithm 24 3.1.1 Viterbi Based 0(1) MMAD 24 3.1.2 Viterbi Based 0(2) M M A D 27 Chapter 3 3.1 3.2 M M A D Based on MAP Algorithms with SDF 3.2.1 Symbol-by-Symbol MMAD 30 3.2.2 Sequence MMAD Based on the BCJR Algorithm 34 3.3 Iterative S ource Model Recovery Chapter 4 30 38 Markov Model Aided Convolutional Decoding V 41 4.1 4.2 MMACD Based on the Viterbi Algorithm 44 4.1.1 The Viterbi Algorithm for Convolutional Codes 44 4.1.2 Trellis Merging MMACD Based on the Viterbi Algorithm 47 Concatenated MMACD Based on the BCJR Algorithm 52 4.2.1 The BCJR Algorithm for Convolutional Codes 52 4.2.2 A Concatenated MMACD Based on the BCJR Algorithm 56 Chapter 5 Rate Allocated Image Transmission Systems 60 5.1 System Model 60 5.2 Punctured Convolutional Codes (PCCs) 64 5.2.1 PCC Encoding and Decoding 64 5.2.2 Search for Good PCCs 66 5.2.3 M M A D for PCCs 69 5.3 Distortion Calculation for Rate Allocated Systems 71 5.4 Optimal Rate Allocation without MMAD 74 5.5 Optimal Rate Allocation with MMAD 77 5.6 Sensitivity to Channel Mismatch 84 Conclusions and Future Work 87 6.1 Summary 87 6.2 Proposed Future Work 90 Chapter 6 Glossary 91 Bibliography 92 Appendix 96 A. 1 BCJR Based MMACD with Trellis Merging vi 96 List of Tables 5.1 Combination of Rs and Rc 64 5.2 Optimal Rs for non-MMAD systems for the various images 77 5.3 Optimal Rs for MMAD systems for the various images 79 5.4 AR between the two systems for the various images 80 S vii List of Figures 2.1 Diagram of Vector Quantizer 8 2.2 VQ data transmission system 12 2.3 Multilevel structure for index assignment for q=4 VQ 15 2.4 Decision tree for Natural Binary Codes, 3-bit VQ 16 2.5 RSNR performance of the two index assignment schemes 18 2.6 Original 512 by 512 Lena image and VQ reconstructed images 19 2.7 Original 256 by 256 Sena image and VQ reconstructed images 20 3.1 Non-source aided VQ transmission systems (a) BSC (b) AWGN 22 3.2 VQ/MMAD transmission systems (a) BSC (b) AWGN 23 3.3 4 state trellis for 2-bit VQ 26 3.4 Viterbi based MMADs without explicit channel coding 29 3.5 MMAP decoders with SDF without explicit channel coding 33 3.6 0(2) sequence MMAD with HDF and SDF 36 3.7 MMADs at channel SNR=0dB for AWGN, e = 0.0786 for BSC 38 3.8 Iterative Source Model Recovery, 3-bit VQ over AWGN 40 4.1 Rate 1/2, Memory 2 CC 43 4.2 VQ with CC over AWGN 43 4.3 Rate 1/2, memory 2 CC trellis diagram 47 4.4 VQ /MMACD using trellis merging 47 4.5 Regular Trellis and Two-Stage Merged Trellis of memory 2 CC 49 4.6 Viterbi decoding with and without an 8-State Markov Model for 3-bit VQ 50 viii 4.7 Viterbi decoding with or without MMAD for 3-bit VQ over AWGN 51 4.8 Concatenated MMACD 57 4.9 BCJR and Concatenated MMACDs 59 5.1 System model 61 5.2 65 Trellis for R = 2/3 PCC based on (2, 1, 2) code 5.3 BER performance of the various rate PCCs based on (3, 1, 8) code 68 5.4 BER performance of PCC decoding with or without M M A D 69 5.5 BER performance of VQ/PCC family at R=2 with MMAD, 512 Lena 70 5.6 BER performance of PCC with MMAD for different images 71 5.7 Optimal rate allocation for the conventional system without M M A D 76 5.8 Optimal rate allocation for the system with MMAD 78 5.9 Optimally rate allocated systems with and without M M A D 82 5.10 Performance of the two rate allocated systems at channel SNR = 0 dB 83 5.11 Performance of the two rate allocated systems at channel SNR = -2dB 84 5.12 Effect of channel mismatch for the two rate allocated systems 86 ix Acknowledgment I would like to thank my parents, Genguan Lin &Yuping Chen, and my brother, Jinsong, for their eternal love and encouragement. I feel very fortunate to be a graduate student of my supervisor, Dr. Samir Kallel, and am very appreciative of his helpful suggestions and guidance throughout this project. I am deeply indebted to Dr. Robert Link for his inestimable guidance throughout this endeavour and for thoroughly proofreading this thesis report. I am very grateful to the National Sciences and Engineering Research Council of Canada, the British Columbia Advanced systems Institute and Mobile Data Solutions Inc. of Richmond, BC, for their financial aid. Finally I would like to thank all my friends in the communication group. Chapter 1 Introduction 1.1 Motivation and Objectives A conventional end-to-end digital transmission system is composed of a source encoder, a channel encoder, a channel, a channel decoder and a source decoder. Source coding, or source compression, reduces the symbol throughput requirement upon the transmitter by removing the redundancy in the source data. Channel coding, also called error control coding, introduces controlled redundancy into the transmitted information stream to protect it from channel noise. A basic result of Shannon's information theory states that nearly optimal communication of an information source over a noisy channel can be accomplished by separately optimizing the source coding and the channel coding operations [1]. However, this result is true only when there is no constraint on the source code dimension and the channel code block length. Based on this result, a conventional source encoder removes as much redundancy in the source as possible in order to deliver a source encoded bit-stream of statistically independent and equally probable bits. However, the more the source data is compressed, the more vulnerable to the channel noise the coded data will be. Therefore, we need more bits for error protection, but it is expensive to design a good channel code over a very noisy channel in terms of bandwidth, delay and complexity. The Shannon theory does not give an algorithm to design good channel codes with finite block length. On the other hand, in practice, due to the lack of exact information about the source, it is not possible to design a source encoder which can remove all the redundancy some residual redundancy always exists in the source coder output sequence. Shannon mentions that any redundancy in the source will usually help to combat noise if it is utilized at the receiving point [2]. Thus, for a practical system, the source and channel codes should not be treated sepa- 1 Chapter 1 Introduction 2 rately. If one wishes to perform near the Shannon limit with moderate delay or channel coding block lengths, it is necessary to consider the design of the source and the channel codes jointly. It may not actually be necessary to combine the source and channel codes, but simply to jointly design them. The systems in which the source coding and channel coding operations are jointly designed are called Joint Source/Channel Coding (JSCC) systems. It has been shown by investigations [3]-[9] that JSCC systems reduce the distortion as well as complexity and delay. JSCC systems have been divided into three broad classes [5]: joint source/channel coders, where the source and channel coding operations are truly integrated; constrained joint source channel coders, where channel coders use some knowledge of the properties of the output of a traditional source coder to mitigate the effects of the noisy channel; and concatenated source /channel coders, which allocate afixedbit rate between a cascaded source coder and a channel coder. In this thesis, a system combining the latter two schemes is proposed and analyzed. Because entropy encoded data is very sensitive to noise, it has been found that for very noisy channels, that it is better to use fixed length source codes which result in substantial residual redundancy, rather than use variable length codes which effectively remove the redundancy [7]. Markov Model Aided Decoding (MMAD) is a source-aided channel decoding technique whereby the residual redundancy in the source is encapsulated in the form of a Markov Model which provides a priori information about the source to the channel decoder. This thesis provides an extensive investigation into joint source-channel coding design with Vector Quantization (VQ) and Convolutional Codes (CCs), both of which are used widely in wireless image transmission systems. VQ is an efficient compression algorithm for removing Chapter I Introduction 3 redundancy in the data source in order to maximize bandwidth utilization. Though M M A D has been investigated for Differential Pulse Code Modulation (DPCM) transmission over the Binary Symmetric Channel (BSC) and the Additive White Gaussian Noise (AWGN) channels [4][5], an extensive investigation into MMAD for VQ transmission hasriotbeen performed. This thesis contributes to this effort through the following: • Reviewing the VQ design method including the LBG algorithm and two index assignment methods. • Applying M M A D techniques using a first order or a second order model for the VQ transmission systems without explicit channel coding. These are based on the Viterbi and the Bahl, Cocke, Jelinek and Raviv (BCJR) algorithms. We also consider iterative model recovery techniques which allow the receiver to recover the model of the source data from the noise corrupted channel data. • Applying the Viterbi algorithm with the trellis merging technique to develop a trellis merged Markov Model Aided Convolutional Decoder (MMACD) for VQ and CC transmission systems, and proposing an alternate concatenated MMACD based on the BCJR algorithm. Many authors, including the present, find large Markov Model Aided Decoding gains, but this is usually because the large gain is usually in a region where the channel code is not effective. There is no M M A D gain for very high channel Signal-to-Noise Ratio (SNR). How can we evaluate M M A D more fairly? The third generation wireless systems allow multi-rate transmission, making rate-allocated systems possible. We believe that a fair system forjudging the performance improvements attainable by employing M M A D techniques would be a rate allocated Chapter 1 Introduction 4 system. Therefore, in this thesis we propose and analyze an optimally rate allocated image transmission system that uses VQ for source coding, and a family of variable rate Punctured Convolutional Codes (PCCs) for channel coding. We consider the rate allocation problem for both M M A D and conventional channel decoding. The combination of source and channel coding used maximizes the end-to-end Reconstruction Signal-to-Noise-Ratio (RSNR) under the constraints of a fixed channel bandwidth, and afixedinformation transmission rate. More specifically, this thesis contributes through the following: • Finding the best PCCs for our system requirements. • Proposing a rate allocated system with MMAD. Applying model simulation to study the optimal rate allocation for the rate allocated systems with and without MMAD. Comparing the performance of the proposed system with that of the conventional rate allocated system without MMAD. • Examining the channel mismatch effect for the optimal rate allocated systems with or without MMAD. 1.2 Thesis Outline This thesis is composed of the following: Chapter 2 presents the background necessary for a basic understanding of VQ. The LBG algorithm is introduced. We investigate the performance of two index assignment algorithms and choose one for our later investigations. Chapter 1 Introduction 5 Chapter 3 focuses on the basic VQ transmission system over the memoryless channels BSC and AWGN without explicit channel coding. We consider both symbol-by-symbol and sequence decoding algorithms. As well we consider using both first order (0(2)) (0(1)) and second Markov models. The symbol-by-symbol decoding algorithms, as well as the sequence decoding algorithms that use the 0(2) model, require feedback of previous decoding decisions. We consider two types of feedback: feedback of hard decoding decisions, and feedback of a posteriori symbol probabilities. These are called Hard-Decision-Feedback (HDF) and Soft-DecisionFeedback (SDF), respectively. The HDF sequence decoders are based on the Viterbi algorithm, while the SDF sequence decoders are based on the BCJR algorithm. In the last part, an iterative source recovery technique is applied to obtain the source model without a priori source information. In Chapter 4, the investigation is continued to MMACDs for VQ data transmission with CCs. One type of MMACD uses a trellis merging technique, which allows one to efficiently use a Markov model while employing the Viterbi decoding algorithm. Another type of MMACD proposed is a concatenated decoder, which uses the BCJR algorithm in a pure channel decoder, followed by the Viterbi based M M A D for no channel coding. The former is computationally simpler, and is optimal in the sense of minimizing the bit error rate. However, it has a restriction (that the length of the source codewords be less than the channel code memory) that the latter decoder does not have. In Chapter 5, we propose an optimally rate allocated M M A D system for VQ with PCC transmission over the AWGN channel. The model simulation scheme is used to determine the optimal rate allocation between VQ and PCC for the systems with and without M M A D . Their Chapter 1 Introduction 6 optimal rate allocation for the different images is studied. We compare the RSNR performance of the proposed system with that of the conventional rate allocated non-MMAD system. Also, their sensitivity to channel mismatch is examined. In Chapter 6, we make concluding remarks and present suggestions for future work. Chapter 2 Vector Quantization In this thesis, all our image transmission systems are based on Vector Quantization [10][20] as the source coding technique. VQ provides two attractive features: high compression ratio and simple decoder structure; thus, it has aroused wide attention for many years. It has been extensively used for source coders in digital transmission of analog signals. Whether or not the source output values are correlated or uncorrected, for a given rate in bits per pixel (bpp), properly designed vector quantizers will always perform better (less distortion) than scalar quantizers [10]. VQ is like scalar quantization except that all components of Q, successive source samples, are quantized simultaneously. Normally these Q. successive source samples are formed by grouping a block of pixels (quantization block) together in a vector. As such, a vector quantizer is characterized by a Q. -dimensional partition, a Q -dimensional codebook (containing Q -dimensional points, reproduction codewords or codevectors), and an assignment of binary codewords (called indices) to the cells of the partition (equivalently, to the codevectors). For Q -dimensional VQ, image vectors are formed by dividing an image into non-overlapping blocks of Q. pixels. Each input vector is compared with the codevectors of the codebook. The index of the nearest codevector is sent to the decoder. The decoder has a codebook identical to the encoder, and decoding can be implemented by a simple table look-up operation. The pictorial representation of this procedure is shown in Figure 2.1 [10]. There are the two main problems in VQ design. One of the problems is how to generate the reproduction vectors, or the codebook over the source; the other is how to choose the binary 7 Chapter 2 Vector Quantization 8 representation of the reproduction codevectors (or the indices), so that the effect of channel errors is not too degrading on the performance. "J image source #• • • • Block into Vectors reconstructed image VQ Encoder Find closest! rl Codevector codebook index VQ Decoder Table Look-up index codebook Unblock Figure 2.1: Diagram of Vector Quantizer 2.1 The LBG Design Algorithm The popularly known Linde-Buzo-Gray (LBG) algorithm or the generalized Lloyd algorithm (GLA) [14] forms the basis of most vector quantizer designs. There exists various VQ design algorithms, and although each has found its adherents, none convincingly yields significant benefits over the LBG algorithm and its variations in terms of trading off rate and distortion [15]. In this paper we use the LBG algorithm as our VQ codebook design algorithm due to its simplicity and its effectiveness in the compression of various source inputs [10] [16]. Before we talk about the LBG algorithm, let us define some terminologyfirst.The amount of compression will be described by the rate, in bpp. Assume we have a codebook of size M, and the input vector is of dimension Q . Each possible codevector is mapped to an index in order to Chapter 2 Vector Quantization 9 inform the decoder which codevector was selected. The index can be a fixed length (fixed-rate VQ) or a variable length (variable-rate VQ). In our system we only consider fixed rate V Q , because variable-rate V Q , though it has better compression performance, results in data that is more sensitive to the channel noise. Thus, each codevector is represented by an index with q=riog M"| bits. For simplicity, we call this V Q a q-bit VQ. As each codevector represents the 2 reconstruction values for Q, source output samples, the rate for a Q. -dimensional vector quantizer riog M] with a codebook size M would be R = •———• bpp. 2 s Define a £1 -dimensional vector quantizer as a mapping function y=q(x), where x represents a source vector, y represents the corresponding reproduction codevector. Each time it assigns a typical source vector (a block of Q. source symbols) x vector y=q(x), y C = { c , Cp 0 = (y°, y , 1 n ') drawn from a = (x°, x\, ..., x^ ~ ) to a code1 n finite reproduction codebook c _ j } , where Cj is a reproduction codevector. The vector quantizer q is comM pletely described by the codebook C with the quantization regions R = {R , R Q q(x) = Cj, if x e R , Ri= {x: d(x, ci) <d(x, Cj) = 0, 1, t lt R M - l }. M- 1. Normally we mea- sure the distortion between a source vector and the reproduction codevector by the mean squared error. £2-1 d{x,y) = \\x-yf= ^(x'-y') 2 (= 0 this is also called Euclidean distance. (2.1) Chapter 2 Vector Quantization 10 We assume to use the image source data as the training set for the codebook design. Suppose the total number of the source symbols in one image is N . Then, for Q -dimensional VQ, the t total number of source vectors is N = N/Q.. The LBG or GLA algorithm proceeds as follows v [10]: 1: Start with an initial set of reconstruction values or an initial codebook [y,}^°\ y. = (yP, yj, y p ~ ) , i = 0, 1, . . . , M - 1 l and a set of source vector {x„}, n = 0, 1, ..., M - 1 . Set the repeating time variable k=0 and the original average distortion D =0. Select threshold e. (0) 2: Calculate the quantization regions {R./ ^}, i = 0, 1, k R/ >={x :d(x , )<d(x ,y -) V i * ; } i = 0, 1 , . . . , M - 1 k n n y/ M ; 3: Compute the average distortion M - 1 by: (2.2) between the source vectors and the reproduction codevectors. K-l Y d(x -q(x )) J (*)) D = n n n^o _ (2 .3) W_ (k-i) D D 4: If — < e stop; otherwise, continue. D ' '. { 5: k=k+l. Obtain new reconstruction values {y,-}^, i = 0, 1, ...,M- 1 by calculating the average value of the elements of each of the quantization regions R ^ . Go to Step 2. The selection of the initial codebook is very important. Linde, Buzo, and Gray described the splitting algorithm in their original paper [14]. It starts by designing a codebook of size one, or Chapter 2 Vector Quantization ]1 a one level vector quantizer. For the one-level quantizer, the output point of the codebook is the average value of the entire source vectors. From this point, one can obtain the initial codebook for a two-level vector quantizer by including the reproduction codevector of the one-level quantizer and a second codevector, obtained by adding a perturbation vector 8, which can be a fixed or a random vectors. Then the LBG algorithm is applied to get the final reproduction codevectors of the two-level VQ. In the same way, one can obtain the initial codebook of a four level quantizer by splitting the final output points of the two-level quantizer. Then the L B G algorithm is used to get the final codebook for the four-level VQ. In this manner, we keep doubling the number of quantization levels until we reach the desired number of levels [10]. After the final reconstruction values form the final codebook C = {c , c Q {VJ}^, c _,}, p M i = 0, 1, M - 1 are obtained, we can where c; represents one of these reconstruction codevectors. Then these codevectors are represented by q-bit indices, q = [~log M~|, which are the 2 most efficient way to represent source information. Suppose we sent these indices into a noisy channel. Because essential information of source data is extracted and source redundancy is removed by VQ, the vector quantized data are very sensitive to channel noise. Proper assignment of binary indices to VQ codewords can reduce the distortion due to the channel noise without an increase in bit rate or decoding complexity. If the index mapping function is y ( c ) , for 2 quantization levels, there are q! possible ways to map a q code vector Cj onto an index y ( c ( ). Index assignment is an important topic in VQ design. In recent years, some iterative index assignment algorithms like the pseudo-Gray coding [17] and the simulated annealing [18] have been reported. However, these iterative procedures are quite computa- Chapter 2 Vector Quantization 12 tionally intensive. In the next section, we consider two computationally efficient index assignment algorithms: the Growth algorithm [19] and the Natural Binary Codes (NBCs) [18] from the splitting algorithm. The performance of each is compared. 2.2 Index Assignment Consider the design of a Q-dimensional, q-bit VQ with the codebook C = {c , C j , ..., c _ j} , where M = 2 . Let the index set be denoted by / = {0, 1, ..., M - 1} . q 0 M We define a one-to-one index mapping as y: C —> / , which assigns the indices to the codevectors. Suppose C j is represented by the index i = 0, 1, M - 1. The indices of the quantized vectors are transmitted over a noisy memoryless channel. Figure 2.2 shows the VQ transmission system without explicit channel coding. Cj X W VQ w I Index Mapping W J Noisy Channel x = VQ" 1 w Figure 2.2: VQ data transmission system Due to the channel noise, index i may become index j at the VQ decoder, j = 0, 1, ..., M - 1. Let p(j\i), i, j = 0,1,...,M-1, denote the probability that j is received given that i is actually sent over the noisy channel. The overall distortion per source sample of the communication system is as follows: M-1M-1 D(q,j) = ^ J i=0 p{j\i)\p{x)d[x, ]dx j=0 Cj (2.4) R, where d(x,y) is the distortion measure between codevector x and y given by (2.1), and R; is the Chapter 2 Vector Quantization 13 quantization region of the codevector Cj. When the distortion is measured by mean square error (2.1) and the codevectors are the centroid of their respective quantization region, (2.4) can be written as [18]: M-1M-1 M-l D(q,j) = ^ X \p(x)d[x,c ]dx +± X i X PWpUWdlCpCj] (2.5) where the first term is the average quantization distortion per source sample. We use D$(q) to denote it, and call it the source distortion. We also note that the value of the second term will be influenced by the source information, the index assignment and the channel characteristic. This term is denoted by D (y) and is called the channel distortion. Thus we have c D(q,y) = D (q)+D (q,y) s (2.6) c It has been shown that a substantial reduction in channel distortion can be obtained through an appropriate index assignment rather than a random assignment [20]. Recently, H-S Wu and J. Barba developed an efficient index scheme called the Growth Algorithm [19] which is simple computationally and which has excellent performance compared with the average random assignment. In what follows we will present this algorithm and another algorithm called the NBCs from the splitting algorithm. 2.2.1 The Growth Algorithm The Growth index assignment technique [19] was published in 1993. The channel is assumed to be memoryless with bit error probability e. Accordingly, p(i\j) = e (l m -e)^~ , m where m is the Hamming distance of the index i and j . For simplicity, assume that no more than Chapter 2 Vector Quantization 14 one bit is in error for any one received binary index. Let h(i,j) denote the Hamming distance between index i and j . H ^ i j ) represents those indices i and j whose Hamming distance between them is 1; Hi(ij) = { (i,j) I h(i,j)=l }. Thus, the channel error transition probability can be described as 1 - ql P(i\j) = 8 fori = j for(i, j) e H (i, j) x 0 otherwise Thus, the second term in (2.5), the channel distortion, can be rewritten as: M -1 D (q,j)= c ^ I P(<) , = 0 d[ , ] X («'.y') e (2.7) Ci Cj H\(iJ) To reduce the channel distortion, one should try to assign the codevectors with smaller Euclidean distance onto the indices with Hamming distance equal to one. When the indices are represented by q bits, there are 2 indices in total. The Growth algorithm is explained as follows [19]: q This algorithm starts to establish a q+1 multilevel index structure. The structure begins with the top level which contains only one node. Any indices whose Hamming distance is 1 from the index on the top node is allocated on the first level. Any indices whose Hamming distance is 1 from any index on the (m-l) level, except those which have been assigned to 0 ~ (m-2) level, th th is assigned to the m level. There are — th th —— nodes on the m level, where 0 < m < q, th [{q-m)\m\\ there are 2 nodes in the structure in total. Figure 2.3 shows an example of the multilevel structure q for q=4. Any indices which are separated by Hamming distance 1, are connected by a straight line Chapter 2 Vector Quantization 15 directly. The number shown at each node is the index representing the code word at the node. After assigning the indices on the structure nodes, we assign the codevectors from the codebook on the according nodes. To make the D (y) c smaller, two codevectors with small Euclidean distance between them tend to be assigned as neighboring nodes linked by a straight line; and a centroid with large a priori probability tends to be assigned to the high levels so that this centroid has more freedom to be chosen as a neighbor of those codes. Thus, each node is assigned one index code and one codevector. A one-to-one mapping can be established by mapping the index in each node to the codevector in the same position corresponding to the identical multilevel structure created based on the Hamming distance of indices. This algorithm is computationally very simple and it has to consider the Euclidean distance between the codevectors, the probability of the codevectors and the Hamming distance between the indices. Its performance is much better than the average performance attained by random index assignments. It is not the optimal assignment, but it comes close to an optimal assignment [19]. Figure 2.3: Multilevel structure for index assignment for q=4 V Q 16 Chapter 2 Vector Quantization 2.2.2 Natural Binary Codes from the Splitting Algorithm Suppose the splitting algorithm is used to initialize the vector quantization procedure. To design a Q -dimensional vector quantizer, first we compute the average of the entire input as the output codevector of a one-level vector quantizer, say y . We put it on the top node of a tree. After 0 splitting y into yo and y (l+8), we apply the LBG algorithm to get the two codevectors, called 0 y 1 0 0 and y , as the output of the two-level vector quantizer. We put them on the second level of the n tree and label them 0 and 1 respectively. In the same manner, we will get the four output codevectors called y r> y2i> y22> 23> labelled as 00, 01, 10, 11 respectively. As we continue splitting and v 2 building the tree, we are also building binary strings with the desired codevectors having binary codes called Natural Binary Codes (NBCs). Figure 2.4 shows an example of a decision tree for a 8-level VQ with the 3-bit NBC indices. The leaves of the tree are the output codevectors and the label inside each node leaf is the index corresponding to the output codevector. Figure 2.4: Decision tree for Natural Binary Codes, 3-bit V Q We have applied the NBC and the Growth algorithms respectively in the system of Figure 2.2 with the 512 by 512 standard monochrome Lena image. For our simulations, in order to keep the required side information low, we use a low dimension 2 by 2, Q = 4, LBG VQ then forms a Chapter 2 Vector Quantization 17 codebook composed of 16 codevectors. After compressing the image into the indices, we transmit sends these indices over the BSC channel. The VQ decoder decodes these noise affected indices to reconstruct the image according to the codebook. In this paper, we suppose the codebook is known perfectly by the VQ decoder. The performance is measured in terms of the Reconstruction Signal-to-Noise Ratio (RSNR). RSNR = 101og ^ 10 ; (2.8) r, c where x r c is original image source value at the point of row r and column c and x' is the reconstructed value at the same position. The RSNR performance for 4-bit VQ using the Growth algorithm and the NBC is shown in Figure 2.5. It is interesting to find that the NBC performs about 2 dB better than the growth algorithm. We also tried other rate VQs. In most cases the NBCs from the splitting algorithm performs very well. The reason is that the codevectors will be concentrated on a thin ellipsoid in the -dimensional space, and the binary partitions obtained by the splitting algorithm are such that "most" vectors in the same region are closer to one another than to those in other regions; and therefore, to a great extent, binary codewords of small Hamming distance will be assigned to the codevectors of small Euclidean distance [18]. Also due to the NBC algorithm's simplicity, in the latter, we use it as our index assignment algorithm. 18 Chapter 2 Vector Quantization 0.02 0.04 0.06 0.08 Error P r o b a b i l i t y of B S C C h a n n e l 0.1 0.12 Figure 2.5: R S N R performance of different index assignment schemes Figure 2.6 shows the original Lena image and the applied 3-bit, 4-bit, 5-bit V Q reconstructed images without noise influence. Their rates are 8 bpp, 0.75 bpp, 1.00 bpp, 1.25 bpp and 1.50 bpp respectively. Figure 2.7 shows the original 256 by 256 Sena image and 3, 4, 5-bit VQ reconstructed images. Note that fairly high quality is already achieved at the source coding rate of 1.00 bpp. 19 Chapter 2 Vector Quantization Original Image RSNR=25.04dB using 1 .OObpp RSNR=23.13dB using 0.75bpp RSNR=26.80dB using 1.25bpp Figure 2.6: Original 512 by 512 Lena image and VQ reconstructed images Chapter 2 Vector Quantization RSNR=23.40dB using 1 .OObpp 20 RSNR=25.75dB using 1.25bpp Figure 2.7: Original 256 by 256 Sena image and V Q reconstructed images Chapter 3 Markov Model Aided Decoding without Explicit Channel Coding It was shown in Chapter 2 that a good index assignment can reduce the end-to-end distortion. In addition to that, we will exploit another way to protect VQ data against the channel errors without increasing the bit rate. It is known that the residual redundancy in the source encoded data can and should be exploited for channel error protection [21]. Although VQ removes much redundancy, there is still some statistical dependency existing among spatially neighboring VQ encoded symbols, especially when the dimension of the vector quantizer is low. It is known that Markov Model Aided Decoding (MMAD) techniques can make good use of residual redundancy to help error protection [4][5]. In this chapter, we will study M M A D techniques for vector quantized image data transmission without explicit channel codes. Although M M A D techniques as described below can be used in conjunction with any fixed length source code, in this paper we consider only images encoded by a vector quantizer. In M M A D one models the source data set as afinite-stateMarkov sequence, and integrates it into the channel decoding process. Therefore, the MMADs require that the receiver have the model of the source. There are two ways for the receiver to obtain the source model parameters. One method is to measure the model parameters at the transmitter and then sent them as side information. Alternatively, it is possible for the receiver to recover the source model without a priori information, as we will discuss in the latter part of this chapter. Suppose an image is quantized by a VQ with codebook size 2 , and that the corresponding q index is q-bit. These indices are represented by a symbol, s , of a Q-ary alphabet, defined at each r c point (r, c) of the VQ encoded image; where r is the row index and c is the column index, Q = 2 . q 21 Chapter 3 Markov Model Aided Decoding without Explicit Channel Coding 22 Here we will compare the RSNR performance between the M M A D and the non-source aided decoding. We consider the decoding of the sequence of received symbols resulting from the row-byrow transmission over the noisy memoryless channels BSC or AWGN. For the AWGN channel, each bit 0 or 1 is BPSK modulated into ±1 before transmission over the channel. The block diagrams of the conventional systems without source aided decoding are shown in Figure 3.1. • VQ Encoder BSC W w VQ Decoder b» w (a) -—• VQ Encoder •w BPSK ~ " 1 W AWGN fe. BPSK" W 1 VQ Decoder w (b) Figure 3.1: Non-source aided V Q transmission systems (a) B S C (b) A W G N The block diagrams of the system with M M A D are shown in Figure 3.2, in which we assume for now that the knowledge of the source is known perfectly by the receiver. The sequence of q-bit symbols is modeled as a finite order Markov sequence. The RSNR performance between the two systems will be compared. Chapter 3 Markov Model Aided Decoding without Explicit Channel Coding VQ Encoder 1 • BSC • MM AX) 23 • VQ Decoder a priori probabilities (a) VQ Encoder —w BPSK W AWGN MMAD VQ Decoder 1 I a priori probabilities! (b) Figure 3.2: VQ/MMAD transmission systems (a) BSC (b) AWGN In Section 3.1 and 3.2, we will review the MMAD principles which are modified based on the Viterbi algorithm or the BCJR algorithm. Two different types of Markov Model will be considered and compared. One is the first order (0(1)) Markov model, the other is the second order (0(2)) Markov model. In section 3.3, an iterative model recovery technique is applied to allow, the receiver to recover the source model parameters without any a prior information. Here we assume that the VQ used in our simulations is a 4-dimensional LBG VQ with NBCs indices. Chapter 3 Markov Model Aided Decoding without Explicit Channel Coding 24 3.1 MMAD Based on the Viterbi Algorithm The Viterbi algorithm is normally a Maximum Likelihood (ML) sequence decoder [22] (refer to Section 4.1), which selects the sequence s that maximizes XX^^r c\ r c) > where s r c ^r,c\ r,c^ P s is the probability of the receiving symbol s r c given that s r c was transmitted; and depends only on the channel. Note that the Viterbi algorithm is not limited to convolutional codes because one can still form the source symbols into a two dimensional trellis (time forming one dimension, the states forming the other). Here the value of a state is the value of a VQ symbol. We apply the Viterbi decoding algorithm in a block decoding mode where each block is a row of VQ image data. We use the term depth to refer to the decoder memory in a particular direction. M M A D based on the Viterbi algorithm takes advantage of a priori source statistics information in such a manner that MAP sequence coding is achieved (refer to section 4.1). Here two different types of the Markov model (O(l) and 0(2)) are considered and their performance is compared. The necessary modification to the Viterbi algorithm for M M A D is shown in the following. 3.1.1 Viterbi Based O(l) MMAD In O(l) M M A D , one models the VQ source data as a first order Markov model. This model is defined by the a priori probability of a symbol given that the symbol previous in the row is known, for all Q symbols in the code alphabet. It is assumed that the a priori conditional probabilities (Markov model) of the VQ source data are exactly known to the receiver. Since the rows are independent, each may be decoded separately. The horizontal depth of the decoder is the row size, the vertical depth is 0. It is shown that using Viterbi based 0(1) M M A D to decode the Chapter 3 Markov Model Aided Decoding without Explicit Channel Coding 25 received sequence optimally in the sense of minimizing the probability of sequence error, the receiver must choose the sequence s which maximizes [4][5]: U (K,c\^c)P^r,c\^c-0 (3-D P c where P(s \s r c r c _ j) is the priori probability of s r c given that s _ r c x was previous symbol, which depends only on the source and defines the Markov model. The most computationally efficient way to decode this sequence is to form a trellis, by indexing the states with both a state index and a time index, and apply the Viterbi algorithm to decode one row (with fixed row index r) at a time. The example of a 4-state trellis is shown in Figure 3.3. Assume that the number of symbols per row is L, of that there are Q states at each time c, corresponding to the symbols s r c of the Q-array symbol alphabet. There is a branch metric calculated between every pair of states consecutive in time whose value is given by: teS (K,c\s ,c)+teg (Sr,c\Sr,c-0 P (3-2) P r Among the paths terminating on a given state, the one having the largest cumulative metric is stored, resulting in Q paths at any given time. Of these, the path with the largest cumulative metric is the decoder's best estimate of the transmitted sequence of symbols up to the current time. When the channel is the BSC, the channel transition probability is: (K,c\ r, ) = p s c e r f (l-e)*- d (3.3) Chapter 3 Markov Model Aided Decoding without Explicit Channel Coding 26 where e is the channel bit error probability, d is the hamming distance between the transmitted symbol s and the received symbol s . IC rc When the channel is the AWGN, define the channel SNR = E / N , where E is the b 0 b received energy of per bit, N is noise spectral density, then we have: 0 q-l ( r,c\h,c) = X ^ J . c K c ) P S ( 3 i =0 P&, \H,c) e =7 = •e x p { - ( < c ; ^ c ) 2 00 01 10 11 candidate paths Figure 3.3: 4 state trellis for 2-bit VQ 4 ) (3-5) l state index r b e s t p a t h a t time r - • Chapter 3 Markov Model Aided Decoding without Explicit Channel Coding 27 3 . 1 . 2 Viterbi Based 0 ( 2 ) MMAD For optimal decoding when source is modeled as a 0(2) Markov sequence, the decoder must choose the sequence s that maximizes [4]: ll (K,c\^c)P^r,c\Sr,c-l^r-Uc) (3-6) P r where P(s \s _\, s _ r c r c r l c ) is the probability of s c given that s _i was previous in the row and rc rc s .i was previous in the column. These Q second order transition probabilities define the 0(2) 3 r c model at the receiver. Since the rows are no longer independent, they can no longer be decoded separately. In principle, for optimality with respect to the second order Markov model, all the rows must be decoded simultaneously. Here we only consider the case that a decoded row is used to aid the decoding of the subsequent row. This is referred to as vertical depth 1 sheet decoding in reference [4]. The decoding of a row proceeds just the same as the Viterbi 0(1) M M A D decoding, except that the decoder selects the sequence which maximizes: n P < 3 r , c K c ) ^ r , c K c ^ - l , c ) (-) 3 7 c where s _ j r c are the decoded symbols for the previous row and are referred to as the Hard-Deci- sion-Feedback (HDF). The log likelihood function for the branch metric: l 0 g ^ c | ^ c ) + 1 0g^, |^c-l^r-l C ) C (3-8) ) depends on the previously decoded row via the decoded symbols s _ r { c . Obviously, the perfor- Chapter 3 Markov Model Aided Decoding without Explicit Channel Coding 28 mance depends on the correctness of the previously decoded sequence. The RSNR performance of the different decoders for 3-bit VQ transmission over BSC and AWGN is shown in Figure 3.4. We use the 512 by 512 Lena image. Compared with the nonM M A D decoders which are labelled non-source aided, the Viterbi based M M A D decoders which are labelled Viterbi + O(l) MMAD or Viterbi + 0(2) MMAD, give significant improvement for VQ transmission for high channel error rates - about 5dB for the BSC channel, and 6dB for the AWGN channel. The two curves converge when channels become cleaner. The reconstructed Lena images of the non-source aided decoding and the Viterbi O(l) M M A D for 3-bit VQ transmission over the BSC and AWGN channels are shown on in Figure 3.7. These images are obtained using the same channel Bit Error Rate (BER). The BSC channel crossover error probability is 0.0768; while the AWGN channel SNR which results in the same bit error probability or BER of 0.0768 for the system without M M A D is OdB. For the BPSK signal over the A W G N channel, the B E R is calculated by BERBPSK Chapter 3 Markov Model Aided Decoding without Explicit Channel Coding i t 29 I <> - •- . 0 e •+• non source aided Viterbi+0(1) M M A D Viterbi+0(2) M M A D o' ' 0 ' 0.02 ' ' 0.04 0.06 0.08 Bit Error Probability of B S C Channel I ' • 0.1 0.12 (a) 3-bit VQ transmission over the BSC channel, 512 Lena 1 I 1 - o' 1 - —0— non source aided e Viterbi+0(1) M M A D • + • Viterbi+Q(2) M M A D ' 3 - 2 - =^-> 1 ' ' ' ' 0 channel S N R of A W G N (dB) 1 2 3 (b) 3-bit VQ transmission over the AWGN channel, 512 Lena Figure 3.4: Viterbi based M M A D decoders without explicit channel coding For the same MMAD system, we find that VQ using M M A D for the AWGN channel gives higher M M A D gain than for the BSC channel. Because M M A D for the AWGN channel uses the Chapter 3 Markov Model Aided Decoding without Explicit Channel Coding unquantized signal level representing the transmitted bit; this unquantized signal has more channel information than the BSC quantized signal, thus allowing the source statistics to weight the decision more accurately. Because of that, for the AWGN channel, the 0(2) M M A D is a little better than the 0(1) M M A D , but opposite for the BSC channel. This poor performance of the 0(2) M M A D decoder relative to the 0(1) M M A D decoder is due to error propagation from row to row. We find in the next section that this error propagation can be mitigated by using Soft-Decision-Feedback (SDF) information from the previously decoded row. 3.2 MMAD Based on MAP Algorithms with SDF The 0(2) M M A D based on the Viterbi algorithm uses HDF values. Here we use SDF instead of HDF to give the 0(2) MMAD more correct knowledge [23]. The Viterbi based M M A D algorithm is a MAP sequence decoding method which minimizes the probability of the sequence error. However, this algorithm does not minimize the probability of symbol error. We apply two other MAP decoders which minimize the probability of symbol error. One uses a symbol-bysymbol Modified M A P (MMAP) decoding algorithm and the other uses a sequence M A P decoding algorithm known as the BCJR algorithm using the modified, numerically stable vision [8] [24]. These decoders provide the a posterior probability (app) which can be exploited by M M A D decoders as SDF. We will see that M M A D based on the BCJR algorithm with SDF achieves a better performance than the Viterbi based 0(2) MMAD. 3.2.1 Symbol-by-Symbol MMAD The MMAP receiver proposed [4], for data obeying a 0(1) Markov model, is a symbol- 30 Chapter 3 Markov Model Aided Decoding without Explicit Channel Coding 31 by-symbol decoder whose decoding rule is to choose the symbol s which maximizes rc P(K.c\ r.c)P(Sr,c\*r,c-0 ( -9) S where s 3 _ j is the previously decoded symbol in the row. r c Similarly, for data obeying a 0(2) Markov model, the MMAP decoding rule is to select the symbol s which maximizes rc (3.10) P(K,c\Sr,c)P(\,c\Sr,c-l>-S _ ) r where s _ r l c hc is the previously decoded symbol in the column. s _ r c and s _ l r l are the HDF symbols. The performance of a decoder using the decision variables in (3.9) (3.10) will depend on these feedback values. A error in the HDF value might cause further errors for the present decoding. For 3-bit VQ transmission over the BSC channel, from Figure 3.5 (a), we can see that the O(l) MMAP with HDF is not better than the non-source aided decoding; and the performance of 0(2) MMAP with HDF decreases quickly when the channel becomes worse. Consider using n(s _ j ) , n(s _ r c r } ) instead of s _ j , s _ c r c r l c . where iz(s ) is the a r c posteriori probability of s . The a posteriori probabilities of the previously decoded symbols are rc used as Soft-Decision-Feedback for decoding the current symbol. The MMAP decision variables for the O(l) SDF are [23]: s' where s is the symbol state and it _ (s) r c l = P (s ^ _ app r c l = s) is the a posteriori probability that Chapter 3 Markov Model Aided Decoding without Explicit Channel Coding 32 the state at position (r, c-1) is equal to s. The computation of n (s) is given by the normalized r c product: s' The optimal decision rule is to choose the symbol s rc = s that maximizes h (s). rc first symbol, the decoding variable is "k (s) = p(s \s = rc rc rc s)P(s rc Note for the = s). Similarly for MMAP with 0(2) SDF, the decision variables are [23]: s" s' where 7t (^) has the same normalization equation as (3.12). rc The performance of the symbol-by-symbol MMADs with SDF is shown in Figure 3.5. We find that for 3-bit VQ transmission over the BSC channel, the 0(1) MMAP with SDF gives about 3dB improvement over the non-source aided decoder; and the 0(2) MMAP with SDF gives about 3dB gain over the 0(1) MMAP with SDF. Compared with Figure 3.4, the 0(2) MMAP with SDF has a similar M M A D gain as the Viterbi based O(l) MMAD. This is because that the former is a symbol-by-symbol decoder, while the latter is a sequence decoder. We conclude that using SDF or a posteriori symbol probabilities, is far superior than using HDF in terms of performance for the symbol-by-symbol decoding. In the next section, we will find that the same is true for sequence decoding. er 3 Markov Model Aided Decoding without Explicit Channel Coding 0.04 0.06 0.08 Bit Error Probability of B S C C h a n n e l (a) 3-bit VQ transmission over the BSC channel 0 -O—I— Non Source Aided 0(1) M M A P with S D F 0 ( 2 ) M M A P with S D F -1 0 c h a n n e l S N R of A W G N ( d B ) 1 (b) 3-bit VQ transmission over the AWGN channel Figure 3.5: M M A P decoders with S D F without explicit channel coding Chapter 3 Markov Model Aided Decoding without Explicit Channel Coding 34 3.2.2 Sequence MMAD Based on the BCJR Algorithm In this part, we develop a row-by-row M A P decoding method based on the BCJR algorithm [25] with SDF. The BCJR algorithm was derived for decoding discrete time finite state Markov sequence over noisy memoryless channels. As in the case of the Viterbi algorithm, the BCJR algorithm can be used for any linear code by forming a trellis [25]. Unlike the Viterbi algorithm, the BCJR algorithm minimizes the probability of symbol error. The decoder estimates the a posteriori probabilities of the states which we exploit for SDF. Based on the algorithm [25], we develop a row-by-row BCJR decoding method with SDF using the modified numerically stable version [8][24]. Suppose the number of source symbols in a row is x; then the input VQ data sequence for each row to a noisy memory-less channel is denoted by s\= s s ...s ; l 2 x and the received sequence is denoted by sj= s s l s s . Define the x state of the Markov sequence at one time as the value of the corresponding source symbol. Considering one row, the optimal decision rule is to choose the symbol S; = s, that maximizes the a posteriori probability P(s~ s\sj) which is given by a normalized product: (s) n = lK w ' y . (3.14) where a^s) is the joint probability of state at time i, a^s) = P(s,- = s, s\); while p\(.s) is the probability of the received sequence from time i+1 to time i given that the state is s at time i , p,-(5) = P ( 3 ? k - = + 1 *). Chapter 3 Markov Model Aided Decoding without Explicit Channel Coding To calculate a and (3, define a probability function: y^s^s) 35 = P(s~ s;s \s._ = s'), l l 0 < s, s' < Q, Q = 2 , then as shown in [25], a is given by the forward recursion [25] of the q modified numerically stable version [8] [24]: with boundary condition a (s)= y^O, s). Similarly, (3 is determined by the backward recursion: l XP,- i(*')-Y,+ p » + =^ (3.16) IXP«(*')-Y,- i(/>*") + with the boundary condition P (.s)= ^ . Where y depends on the channel transition probability T t n e a P( r, \ r,c)> s c s Priori source transition probabilities of the second order Markov model -l'^r-i.c) an< ^ the posteriori probability of the previously decoded row (SDF) n _ (s): r lc y (s',s) r>c = P(s \s = rc rc s)^P(s = rtC s\s _= rc s\s _ = r lc s")n _ (s") r lc (3.17) s" Figure 3.6 shows that the 0(2) sequence MMAD with SDF based on the BCJR algorithm is better than the 0(2) sequence MMAD with HDF based on the Viterbi algorithm for 3-bit VQ data transmission over the BSC or AWGN channel. Chapter 3 Markov Model Aided Decoding without Explicit Channel Coding 36 (a) 3-bit VQ transmission over the BSC channel (b) 3-bit VQ transmission over the AWGN channel Figure 3.6: 0(2) sequence M M A D with H D F and S D F Figure 3.7 also shows the reconstructed images decoded by the 0(2) M M A D with SDF (BCJR) for the 3-bit VQ 512 by 512 Lena image over an AWGN channel of OdB SNR, which Chapter 3 Markov Model Aided Decoding without Explicit Channel Coding corresponds to the B S C channel of cross-over probability 0.0786. Although the advantage of the 0 ( 2 ) M M A D with S D F ( B C J R ) over the O ( l ) M M A D (Viterbi) is relatively small by image R S N R measure, the image decoded with the 0 ( 2 ) M M A D with S D F ( B C J R ) is visually much better in the high detail regions of the image. Non Source A i d e d RSNR=13.17dB 0 ( 1) M M A D (Viterbi) RSNR=18.24dB 0(2) M M A D with S D F ( B C J R ) RSNR=19.00dB (a) 3-bit V Q over B S C 37 Chapter 3 Markov Model Aided Decoding without Explicit Channel Coding 38 Non Source Aided RSNR=13.19dB 0(1)MMAD (Viterbi) RSNR=19.84dB 0(2) M M A D with SDF (BCJR) RSNR=20.53dB (b) 3-bit VQ over AWGN Figure 3.7: M M A D s at channel SNR=0dB for A W G N , £ = 0.0786 for BSC 3.3 Iterative Source Model Recovery In the above we assumed that the a priori source information is perfectly known by the receiver as the side information. Obviously this will increase the transmission overhead. Also, the Chapter 3 Markov Model Aided Decoding without Explicit Channel Coding transmitter must be modified to measure and encode the source model. If the images are time variant, using a prior knowledge may lead to inaccuracy. We will consider a recently published iterative decoding method to recover the source model form the noise corrupted channel data [26]. The M M A D will first decode the received data without a priori knowledge; it then measures the statistics of the decoded data as the source model for the next decoding iteration. The convergence to the ideal M M A D is achieved after repeating the above steps a few times. We apply this method to the 3-bit VQ data transmission over the AWGN channel with the Viterbi based O(l) MMAD. The curves in Figure 3.8 show that the process converges the remarkably quickly to the result that a receiver which has perfect a priori knowledge of the source model. The source model is recovered well enough at the end of 2nd iteration. Further iterations yield minor or negligible improvement. This means that by using the iterative source model recovery algorithm, we can reconstruct the noisy damaged image without a prior source information. In the iterative M M A D system structure of the conventional transmitter is unchanged; but there is the drawback of a processing time delay at the receiver. In this chapter, we have found substantial performance gains by using the various kinds of MMADs for the VQ data transmission over the memoryless noisy channels. In the next chapter, we will continue to investigate MMADs for systems with channel convolutional codes. Among the various MMADs, we choose the O(l) sequence M M A D for our latter research because the following reasons: The sequence MMADs have superior performance than the symbol-by-symbol decoders. Although the symbol-by-symbol 0(2) with SDF M M A D performs as well as the 0(1) sequence M M A D , the O(l) sequence M M A D is easier to incorporate into the convolutional codes. The performance gain attained by using the 0(2) sequence M M A D instead of the 0(1) 39 Chapter 3 Markov Model Aided Decoding without Explicit Channel Coding sequence M M A D is small. Moreover, the former is significantly more complex than the latter. Figure 3.8: Iterative Source Model Recovery, 3-bit VQ over AWGN Chapter 4 Markov Model Aided Convolutional Decoding In Chapter 3 we found that M M A D without explicit channel coding gives significant coding gain for VQ transmission at high channel error rates, but provides little improvement at low channel error rates. On the other hand, conventional Forward Error Correcting (FEC) codes provide excellent error protection at low error rates, so that the combination of conventional FEC codes with M M A D can give good performance at all channel error rates. In this chapter, we will continue the development by incorporating Convolutional Codes (CCs) for VQ data transmission over the AWGN channel. Convolutional codes are selected as our FEC codes due to their pervasiveness in existing systems. We call source aided channel decoding, which uses the source statistics information in the form of a Markov Model to aid the convolutional channel decoding, Markov Model Aided Convolutional Decoding (MMACD). Convolutional Codes were first introduced by Eli [27] in 1955. He proved that redundancy introduced into a data stream through the use of a linear shift register [22] can give substantial error protection ability. He also showed that the resulting codes were very good even when randomly chosen. This result correlated to Shannon's theory that there exist randomly selected codes that, on average, can provide high levels of error protection ability, given data transmission at a rate less than the channel capacity [28]. Let us start with the standard definition of a convolutional code [22] [29] [30]. A rate kJn convolutional encoder takes k input bits and generates n output bits. The input bit stream is fed into a shift register circuit consisting of a series of memory elements. Normally, an input data stream is fed into a shift register with memory m The total memory is M = X j> m v 41 Chapter 4 Markov Model Aided Convolutional Decoding 42 i = 0, ..., k - 1. The constraint length K of a convolutional code is the maximum number of bits in a single output stream that can be affected by any input bit. The maximal memory m of the convolutional code is the length of the longest input shift register. In practice, the constraint length is usually taken to be the length of the longest input register plus one. K = 1 +m (4.1) A (n, k) convolutional code with memory m is said to be an (n, k, m) CC. The minimum free distance, denoted d is the minimum Hamming distance between all pairs of complete f r e e convolutional code words. The convolution operation can be described by the delay transform, or D-transform, X(D) = U(D)xG(D) (4.2) The transfer-function matrix G(D) is a k x n matrix with polynomial entries for an (n, k, m) CC. U(D) is the D-transform of the input code words. X(D) is the D-transform of the output code words of the convolutional code. For example: JC = (x , x x , Q v 2 ...)<-» X(D) = XQ + x D + x D 2 x 2 + ... m, G(D) elements are the generator polynomials g- •(£)). = ^ m= 8ljD , m where i = 1 , k ; j = 1, 0 n. It is simple to use octal codes to represent gij(D). For example, Figure 4.1 shows an (2, 1, 2) CC with G(D) = (1+D+D , 1+D ). We can represent it by the generator polynomials gj = 7 , g = 2 2 8 4g- 2 43 Chapter 4 Markov Model Aided Convolutional Decoding Figure 4.1: Rate 1/2, memory 2 C C With a CC, the block diagram of the end-to-end system for q-bit VQ transmission over the AWGN channel is shown in Figure 4.2. VQ u r CC • • BPSK AWGN y CC" —• 1 u' • VQ" 1 L Figure 4.2: VQ with C C over A W G N In this chapter, we will develop two different kinds of MMACD techniques. One is based on the Viterbi algorithm; the other is based on the BCJR algorithm. Their performance and computation complexity is compared and analyzed. In our simulations, we use a (3,1,5) convolutional code with the generator polynomials gj = 74 , g = 53 , g = 37 for the 3-bit VQ encoded 8 2 8 3 8 Lena image transmitted over the AWGN channel. As mentioned previously, the source model can be made known to the receiver in several ways. One is by transmitting the model parameters as side information with stronger error protec- Chapter 4 Markov Model Aided Convolutional Decoding 44 tive codes. Another is by estimating the model information by the iterative source model recovering technique used in Section 3.3. In the simulations discussed in the following, we assume that the source information is known perfectly by the receiver. 4.1 MMACD Based on the Viterbi Algorithm 4.1.1 The Viterbi Algorithm for Convolutional Codes In 1976, Viterbi discovered a practical decoding algorithm for convolutional codes [28]. The Viterbi decoding algorithm has been known for at least ten years in various forms in the field of operations research due to its simplicity and low decoding complexity. Consider the decoding problem presented in Figure 4.2. An information VQ sequence u is encoded by a CC and modulated into the sequence x, which is transmitted over an AWGN channel. The Viterbi decoder takes the received sequence y and generates an estimated u'. The decision rule for the conventional Viterbi decoder is to select the sequence u' that maximizes the probability P(y I u). We know that MAP decoder maximizes P(«ly); and M L decoder maximizes P(yl«). If the distribution of the source words u is uniform, then according to Baye's rule, we have: P(u\y) • P(y) = P(y\u) • P(u) (4.3) then the two decoders are identical. In the conventional Viterbi algorithm, the term p(u), the a priori probability of the information sequence, is not known and is assumed the same for every sequence u. Thus the Viterbi decoder is a M L decoder. Suppose that we have an input sequence u composed of L q-bit symbols u , U i , . . . u _i; Lq 0 L 45 Chapter 4 Markov Model Aided Convolutional Decoding is the decoding block length. Then the source bit stream to the encoder is, u = ( u ° , u \ . . . , u o ^ " ) , U L . ! , U L . / , . . . , U . J (q-D) 1 0 where u^ represents the j t h 0 0 bit of the i L t h source symbol. For a rate 1/n code, the encoder output bit sequence x and received bit sequence y w i l l consist of L q n bits: x=(x °( >,x 0 0 0(0) y=(yo where x(W e ±1 is the k the i t n t h 0 0 ^),x ./ q 1 ) ( 0 ) L ,.... X L . ^ " 1 ^ ) 0(n-l) (q-D(O) . — y n >-,yo bit of the channel encoded word which corresponds to the j bit of V Q source input symbol, and y^( ) is the corresponding received bit. Because the A W G N m channel is a memoryless channel, that the noise process affecting a given bit in the received word y is independent of the noise process affecting all of the other received bits. The decision rule is to choose the u with the largest path metric computed by: L-\q-\ p{y\u) = n n i = 0j =0 c - ) 4 4 Then the log likelihood function known as the branch metric is calculated by: n-l \ogP(yJ\uJ) = X l o g P ( y / | * / ) W W (4.5) k=0 For the A W G N channel, we define E as the received energy per channel codeword bit, and the s channel S N R = E / N . We have: s 0 Chapter 4 Markov Model Aided Convolutional Decoding m\ m) = - 1 P{y x 46 . exp - < ' (y (4.6) ) then (4.5) can be expressed as: n- 1 log/>(y/|u/) = £ (y/W-Jcp)) + C (4.7) 2 0 fc = 0 where C is an irrelevant constant value. In the Viterbi algorithm, the code trellis is used for the computation of P(y I u). A trellis diagram shows the encoder states as a function of the time. Each stage in the trellis corresponds an input bit. The state of the encoder is simply the contents of its shift registers. For an encoder with total memory m, the number of states is 2 . For CCs, the initial state is normally chosen to be 0. m After inputting the bit sequence of length L, m 0s are input to cause the last state of the sequence to be 0. The branches of the trellis diagram are labeled with the output bits corresponding to the associated state transitions. Among the paths terminating on a given node, the one which has the largest cumulative metric is stored, where the cumulative branch metric for a path is the sum of the branch metrics along a path. Therefore, at each time there will be 2 survivor paths. After m calculating for all of the stages, we trace back from the last node (zero state) to find the one path with the maximum-likelihood probability called ML path. According to this path, we can get the input bit on every stage. Then we obtain the decoded source symbols u' by combining consecutive q decoded bits into symbols. Figure 4.3 shows the trellis diagram for the rate 1/2 encoder of Figure 4.1. Chapter 4 Markov Model Aided Convolutional Decoding 47 11 M L path Figure 4.3: Rate 1/2, memory 2 C C trellis diagram 4.1.2 Trellis Merging MMACD Based on the Viterbi Algorithm Suppose that we use a q-bit VQ source and its bit stream is encoded with a convolutional encoder, modulated and sent over an AWGN channel. Here we will apply a technique called trellis merging [26] which allows the correlation in the source codeword stream to be utilized when decoding a trellis-based channel code. The system block diagram is shown in Figure 4.4. w VQ u 1 CC BPSK fe. V Figure 4.4: 1 ' AWGN y hi w MMACD u' W VQ" 1 V Q / M M A C D using trellis merging Let the length of the source symbol sequence block be L. Each q-bit source symbol will be encoded into q • n channel bits by a rate 1/n convolutional code with memory m. Each block of n bits corresponding to one source information bit is called a channel codeword. If we block q Chapter 4 Markov Model Aided Convolutional Decoding 48 channel codewords into a single block, the block will correspond to a single source codeword (symbol). The trellis merging algorithm is shown in the following [26]: We model the source by a first order, Q state Markov model, with Q = 2 . The model is q defined by the Q a priori transition probabilities PO^Iw,.;). For a 0(1) Markov sequence, it can be 2 shown that p(u) = n K h - i ) p <-) 4 8 i i = 0, ..., L - 1. Since the channel is memoryless, we have L-1 p(y\u) = n (^h) p <") 4 9 ;=o where y; is the block of q channel codewords which corresponds to the source symbol uj. Therefore, using the source statistics to aid the conventional channel decoding, MMACD selects the estimate u that maximizes: n^N-^l",-,.) (4-10) i This decoding algorithm proceeds in the same manner as the conventional Viterbi algorithm except that it has a modified branch metric: logP(y,. | « ) + logP( «,•!«,•_!) I where (4.1.1) Chapter 4 Markov Model Aided Convolutional Decoding 49 7 = Ok = 0 The first term in (4.11) is the usual term for M L decoding, and depends only upon the channel, while the second term depends on the source statistics. Inclusion of the source term in the branch metric causes the decoding to become MAP sequence decoding. In the trellis diagram, this (blocking q channel codewords into one) corresponds to merging q branches into one which is connected by the two remaining end nodes directly. Then every stage of the new trellis corresponds to an input source symbol rather than an input bit. The decoding proceeds as the conventional Viterbi algorithm except that the trellis length will be reduced by a factor q, but the number of branches is increased by the factor 2 q_1 and the branch metric will be modified. Therefore, the computational complexity of decoding in a merged trellis is in proportional to 2 "Vq. When q is increased from 1 to 2, the computational complexity does q not increase. An example of trellis merging for the CC with memory m=2 and 2-bit VQ is shown in Figure 4.5. Figure 4.5: Regular Trellis and Two-Stage Merged Trellis of memory 2 C C Chapter 4 Markov Model Aided Convolutional Decoding 50 In Figure 4.6 we show the simulation result for transmission of 512 monochrome Lena encoded with a 3-bit VQ and a (3, 1, 5) convolutional code. The result shown in the figure tells us that Viterbi based trellis merging gives significant Markov model coding gain compared with conventional Viterbi decoding for the transmission of VQ image data over a AWGN channel. At the BER of 10 the coding gain due to use of the Markov Model is approximately 1.6dB. Similar to the M M A D without explicit channel coding, M M A D for the convolutional channel codes or M M A C D gives less coding gain for the low error rate channel. Because in a clean channel, the channel term of the branch metric is strong enough to correct almost all channel errors; and the source term has a relatively weak influence on biasing the metric. But for a noisy channel, the source model is more effective at biasing the branch metric. We can see that the two curves will converge when the channel SNR becomes high. The comparison of the reconstructed Lena images at the channel SNR=-6dB and -4dB is shown in Figure 4.7. The improvement obtained by MMACD is about 9.44dB in RSNR when the channel SNR is -6dB. Conventional Viterbi Viterbi Trellis Merged M M A C D -4.5 -4 -3.5 A W G N channel S N R = Es/NO (dB) Figure 4.6: Viterbi decoding with and without an 8-State Markov Model for 3-bit V Q 51 Chapter 4 Markov Model Aided Convolutional Decoding Viterbi only at SNR = -6dB RSNR = 9.2 ldB Viterbi only at SNR = -4dB RSNR = 16.65dB Viterbi MMACD at SNR = -6dB RSNR = 18.65dB Viterbi MMACD at SNR = -4dB RSNR = 22.20dB Figure 4.7: Viterbi decoding with or without M M A D for 3-bit V Q over AWGN Trellis merging is an efficient algorithm to make use of the VQ source information to aid the channel decoding, but it is necessary that the memory m of the convolutional code be greater or equal to the number q of bits per VQ symbol. Chapter 4 Markov Model Aided Convolutional Decoding 52 4.2 Concatenated MMACD Based on the BCJR Algorithm In this section, we will be considering an alternate technique to trellis merging that does not have the restriction q<m. This would be useful for systems in which the source encoder produces long source words or in which a low memory channel code is used. This proposed decoding technique is called the concatenated MMACD. The conventional non-source aided channel decoder based on the BCJR algorithm decodes the received sequence in the first stage, then passes the a posteriori source bit probabilities to a cascaded M M A D without explicit channel coding which decodes the noise effected source bit stream using the Markov model in the second stage. Here we will discuss the BCJR algorithm for convolutional codes first. 4.2.1 The BCJR Algorithm for Convolutional Codes In Chapter 3, we developed the BCJR decoding algorithm with SDF for the system without an explicit channel code. Here we will develop the BCJR [25] decoding algorithm for a convolutional code using the modified numerically stable version [8] [24]. Assume we use a 1/n CC with memory m. The BCJR algorithm considers the source as a discrete-time finite-state Markov process. Suppose the q-bit VQ source is encoded bit-by-bit, and that the data bit stream is u = ); here U j is a bit 0 or 1, x is the decoding block length T = L • q + m and L is the total number of VQ source symbols in one block. Let JC = (x x , ..., x ) be the encoded channel code word sequence, and let y = (yj, y , p 2 T 2 y ) be x the corresponding received sequence of a noisy channel transmission, xj = ( \ ^ ° \ x^ ^,..., x/"" ^), 1 y-j = (yi , y j , (0) (1) yi (n_1) 1 ) . Let S refer to the state of the Markov process. Unlike the BCJR decoding without explicit channel coding, the state here refers to the state of the convolutional Chapter 4 Markov Model Aided Convolutional Decoding 53 code instead of the VQ symbol value, which is the content of the shift registers. For a code with memory m, the total number of the states is 2 . m We also know that the state of a convolutional code normally starts in the initial state SQ = 0, and that the last state is forced to be 5 = 0 by adding a tail sequence of zeros. The objective T of the B C J R convolutional decoding is to examine y and estimate the a posteriori bit probabilities 1. e. P ( « | y ) , 0 < i < i, which can be obtained from the a posteriori probabilities of.the state ( P(Sly), ,<. , p P m W Pis*y) ~P(yj~ = = (4.13) XjO) where X (s) = P(S = s, y ) . P(y) is a constant P(y) = A, (0). Let Sj = (sj , sj ,..., 0 { T T 1 Si(m_1)), so the input bit uj = Sj at time i. Define A, be the set of states S; such that s, = 0 which means that the 0 0 input bit at time i is 0. After getting a posteriori probabilities of the state P(Sly), calculate [25]: X P("i = 0\y)= W W = 5T7m I i X {s) ( 4 - 1 4 ) Then the decoder can decode u, = 0 if P(w = 0|y) > 0.5; otherwise u, = 1. ( Similar to Chapter 3, X is calculated by: X (s) t = a,.(5) • B.(j) (4.15) The calculation of a and [3 uses the same equations as (3.15) and (3.16), except that s or s' is now Chapter 4 Markov Model Aided Convolutional Decoding the state of the convolutional code, 0 < s, s' < 2 m 54 instead of the VQ symbol value. For the BCJR convolutional decoding, the initial boundary conditions for a become a (0) = 1 and 0 a (s * 0) = 0, corresponding to the encoder initial state 0; and the final boundary conditions for Q P are P ( 0 ) = 1 and P ( j * 0) = 0, corresponding to the encoder ending in state 0. t x The transition probability y^s', s) is defined as y^s'/s) = P(s = s, y^s^ i { = s') and is easily shown to be y.(s',5) = Piu^Piy^) (4.16) The first term P(uj) is the a priori probability of the bit u that causes the transition t (s _ i l = s') —> (s = s) which results in the encoder output xj. Now it assumes all input sequences ( equally likely for i<Lq. For i> Lq, the input to the CC is m 0s, so P(Uj) is equal to 1. The second term P(yjlXj) is the probability that code word y; is received given that code word Xj is sent and this depends on the channel. Because the input bit u e 0, 1, then we have: i 1 i TI/ \ . yi Xi 0 / 1 •^ s'^s,i>Lq and input bit u,. For a memoryless A W G N ( 4 - 1 7 ) else where s' A s means that the transition (s-_ j = s') -4 (s- = s) SJ.J r s'^s,i<Lq -•P(y,.|x.) P( \ ) 0 channel: exists, because S; is decided by Chapter 4 Markov Model Aided Convolutional Decoding 55 n-l (4.18) = UP(y\ \x\ ) (yi\ i) P k) X k) • k=0 For the bit transition probability of AWGN channel see (4.6). Using the stable renormalization version, we can see that the complexity of the computation will increase with the state number. Due to the relationship between the previous state, the current state and the current input bit, we can simplify the calculation of a and P in (3.15) and (3.16) by: Xrx«-i(''Cs,fc)) • Y,.(fCs, *) (4.19) aAs) = b s' ^ p..(j) = i (t(s,b))-y (s, + 1 t(s,b)) i+1 XlP^')-Y, i(^ b s' + : (4.20) t(s',b)) t'(s, b) is the function to get the previous state value if we know the current state value s and the current input bit b. t(s', b) is the function to get the current state value given the previous state value and the current input bit b = 0 or 1. There are 2 states in total. Thus, using (4.19) and m (4.20) we can reduce the computation by the factor of 2 m_1 . The BER of this algorithm is shown in Figure 4.9. Compared with Figure 4.6, we see that the BCJR decoding algorithm has the same error protection ability as the Viterbi algorithm. The computation of the algorithm becomes considerable when the constraint length of the convolutional code becomes large. But the advantage of this algorithm is that it can provide the soft Chapter 4 Markov Model Aided Convolutional Decoding 56 output of a posteriori probability (app); we will exploit this character to propose a concatenated MMACD which does not have the restriction q < m in next section. On the other hand, we can apply the trellis merging method of Section 4.1.2 to a softoutput trellis merged (BCJR trellis merged) MMACD. It would be useful for constructing sourceaided turbo decoding systems [31][8], and we used it to check the concatenated MMACD that we will propose. We find that the BCJR trellis merged decoder also has the same BER as the Viterbi trellis merged decoder. The detailed information about the BCJR trellis merged decoding algorithm is shown in the Appendix. 4.2.2 A Concatenated MMACD Based on the BCJR Algorithm It is true that these trellis merging techniques combine the channel transition term and the source statistics term together in the calculation of the branch metric. However, these trellis merged MMACDs have to satisfy the condition that q<m. Can we calculate the channel term first and combine the source term later? Thus, in the case that g > m, we could have an alternative way to take advantage of the Markov model. Consequently we propose a concatenated MMACD which is composed of two decoders. The first decoder is a conventional channel decoder and the second decoder is the Viterbi based M M A D without explicit channel coding. First, the conventional channel decoder decodes the received sequence y, then passes its output into the MMAD which can bias the decision using the source information. The output of the first decoder can be hard output or soft output. Our analysis and simulations showed that the second decoder can not give help if the first decoder gives the hard output decision. Therefore, we would like to use a decoder which can generate soft output Chapter 4 Markov Model Aided Convolutional Decoding 57 information. The B C J R algorithm is optimum in the sense that it estimates the exact value for a soft output {app of source bit) P(ujJ|y), where uj is the j t h bit of the i t h source symbol. Because of this, we would like to use the B C J R decoder as the first decoder in the concatenated M M A C D . The structure of a concatenated M M A C D is in Figure 4.8. y | 1—^ app Soft in / Soft out . P{uj\y) BCJR MMAD 1 u ' J Figure 4.8: Concatenated M M A C D F o r M M A D w i t h o u t e x p l i c i t c h a n n e l c o d i n g , the b r a n c h m e t r i c is c a l c u l a t e d by l o g p ( M - p - ) + logP(M-|w-_ j ) , where Uj is the V Q source symbol, and u is the received symbol. i For q-bit V Q transmission with a convolutional code over the memoryless A W G N channel, the B C J R decoder gives the app of a input bit P(uj\y), j=0, 1 , q - 1 , and y is the received sequence. The M M A D without explicit channel coding in the proposed concatenated MMACD decoder uses the channel transition probabilities for the branch metric. q-\ P(«,.|fi,.) = Y[P(uj\y) 7 = 0 (4.21) Chapter 4 Markov Model Aided Convolutional Decoding 58 which is based on P((M/|U/) = P(M/|y)), and that the q conditional bit probabilities P(M/|W/) are independent. The simulation result shown in Figure 4.9 shows that this decoding gives some improvement over the conventional B C J R or Viterbi decoding, but much less improvement over the trellis merged decoding. To investigate this further, we use the B C J R trellis merged decoder (see the Appendix) without using the source statistics in the y calculation to generate the app of the input symbol P(M,IV) instead of the app of the input bit P(M/|V) ; and we pass this soft output to the MMAD. From the simulation result in Figure 4.9, we find that the performance using the app of the input bit P(w/|y) is different from the one using the app of the input symbol P(«,ly), which means that conditional bit probabilities P(u/|w/) are not quite independent. Also, the B C J R concatenated decoder using the app of symbol cannot outperform the trellis merging MMAD. Although there is no loss of information when we pass the soft output of the convolutional decoder to the M M A D , we do find a performance penalty with respect to the trellis merged decoder. This is because in the trellis merged decoder the source information is used to bias the decision based on the received channel data. In the concatenated decoder, the convolutional decoder increases the reliability of the received channel data. The source information in the second decoding stage cannot bias a decision based on this more reliable information as effectively. The B C J R is not computationally efficient for large memory convolutional codes, also that the computational complexity of the M M A D without explicit channel codes grows exponentially Chapter 4 Markov Model Aided Convolutional Decoding 59 with the number q of bits per VQ symbol. Therefore this decoding method is practical only for short constraint lengths and long VQ symbols. It should only be used when the restriction q < m is not satisfied so that the trellis merging cannot be applied. • -Eb;; '••+-.. ':• • . ^ i'.'.... :::::::::.:...... 10 o I -6 -4 I • •+• '.'.WW B C J R only B C J R app of Bit +MMAD B C J R app of Symbol+MMAD j -5.5 ^ I T—' I | i | - 4 S N R = Es/NO - 3 . 5 (dB) the A- 4W. 5G N channel Figure 4.9: '.':': .'. .':.<> : - r -5 :::::(] i | -3 1 I -2.5 I -2 B C J R and Concatenated M M A C D s From the above discussion, it can be concluded that the Viterbi based trellis merging is the most efficient method with which to take advantage of the Markov source model. In the following, we will use the Viterbi based decoder with trellis merging to construct in the rate allocated systems. Chapter 5 Rate Allocated Image Transmission Systems In this chapter, we will continue by investigating the problem of rate allocation between the source encoder and the channel encoder for VQ image transmission over the AWGN channel, given that the system information rate and channel transmission rate are fixed. Here we will use Punctured Convolutional Codes (PCCs) as the channel codes. We have shown that M M A D convolutional decoders give little improvement at low error rates. Some authors including the present, found that at most times the bit error probability becomes very low when the source and channel rate is optimally allocated [3]. That would indicate that M M A D may be not useful for the rate allocated systems. However, MMAD does extend the SNR rage over which a channel code corrects most of the channel errors; and we will find that this does impact the rate allocation. In this chapter, we will compare the two rate allocated systems: system A is the conventional rate allocated system without MMAD; system B is the proposed rate allocated system with MMAD. We will apply the model simulation scheme to determine the optimal rate allocation for the two systems and examine the difference of the optimal rate allocation between the two systems. Performance comparisons are made in terms of the end-to-end RSNR as a function of channel bit SNR. We conclude the study with comparative analysis of the sensitivity to channel mismatch of the two systems. First, we will discuss the system model and look for good PCCs for our systems. The distortion calculation scheme for determining the optimal rate allocation is discussed as well. 5.1 System Model Figure 5.1 shows the block diagram of the end-to-end communication system. 60 61 Chapter 5 Rate Allocated Image Transmission Systems Source Encoder Channel Encoder a q Modulator Channel Channel Decoder Source Decoder Demodulator P Figure 5.1: System model Let R be the source rate, which means bits per pixel (bpp), for the Q. -dimension fixed s rate VQ - each encoded symbol is composed of Q.R bits. The channel encoder will add the conS trolled redundant bits for these source encoded bits, which will result in £l(R + R ) bpp. Define s c the total rate R = R + R , where R is the channel rate. Then, the channel coding rate r is given s c c c by: R„ ° r (5.1) R„ + R, The channel coded bits (channel symbols) are then modulated into the channel symbols and transmitted over an AWGN channel at a rate of one channel symbol per T second, where T is the channel symbol time. Define the information transmission rate I of the system as the number of the r source symbols (pixels) transmitted per second. Given the channel symbol transmission rate 1/T, we have: 1 r T(R S + R) C (5.2) Chapter 5 Rate Allocated Image Transmission Systems 62 Thus given a fixed source information rate I and a fixed channel symbol transmission rate 1 / T , r the total rate R= R +R is fixed too. In that case the rate allocation problem is reduced to finding s c the best combination of R and R for a given fixed R. s c We suppose a discrete-time, real-valued, stationary source encoded with the VQ source coder and the PCC channel coder. Each possible Q -dimensional source vector y is mapped to a binary code (index) s with fixed length. After the channel coding, the binary code s becomes the channel symbol vector x. These channel symbols are modulated by BPSK and are sent to the AWGN channel. Due to the channel noise, the received channel symbol vector y might not be the same as the transmitted symbol vector x. After passing into the channel decoder, which may correct some of channel errors, one obtains the decoded binary code s' corresponding to the original binary code s. Finally, the noisy reproduction y' is obtained after s' is passed through the source decoder. We calculate the total end-to-end distortion of the system as the squared error between the source vector v and the source reconstructed vector v': d(y, y') = ||y - y'|| . The total distortion 2 is normally composed of the channel errors or distortion and the source quantization errors or distortion. Given a fixed total rate R, if one uses the high R , then there are fewer bits used for R . s c This will occur at the high channel code rate (large r ) at the expense of the high probability of bit c error. In that case, the source coding or quantization distortion is small, but since the channel decoding error probability is relatively high, the end-to-end distortion may also be unacceptably high. On the other hand, if we give more bits for the channel rate R , the low channel coding rate c r occurs at the cost of low source coding resolution. In this case, the channel decoding error probc Chapter 5 Rate Allocated Image Transmission Systems 63 ability is small, but the source coding distortion is relatively high; thus again possibly yielding a large total distortion. Between those two extremes there should exist the optimum combination of the source rate R and the channel rate R which minimizes the distortion. The optimal rate allocation for the s c conventional system depends on the channel SNR = E / N , the source statistics, channel coding s 0 and modulation [3]. Usually, R corresponding to the optimal bit allocation, will increase when s the channel SNR is increased. Because the less noise there is in the channel, the less bits are needed for error protection, and the more bits can be used by the source code. For the various source rates R , the system needs the various rate channel codes r . We s c choose a family of PCCs as the variable rate channel codes that are generated from the same convolutional code. This allows relatively simple implementation of the transmitter and the receiver. For our systems, we use a 4-dimensional VQ, and consider the total rate R = 2bpp over the range of channel SNRs -3dB < E /N <3dB. s We choose these values for the parameters Q because, we will see from the following numerical results, that there is little distortion reduction for R > 2bpp or E Q / N > 3dB. For each R 0 < R < R, there is a corresponding R = s 0 s s c R-R .We s assume all the redundant bits are used for the channel code, and that the codes are equal weight channel codes, which means that there is the same error protection for each bit of the source encoded data. Previous research has found that there is not much difference between using equal weight channel codes and using unequal weight channel codes when the system is optimally rate allocated [3][32]. Chapter 5 Rate Allocated Image Transmission Systems 64 For example, if we use a 3-bit.4-dimensional VQ, the source rate R is 0.75 bpp, and using s (5.1), the channel coding rate required r is 3/8. All the variable rate codes that our systems c require are shown in Table 5.1. In the next section we will discuss PCCs and the way to search for the best PCCs we need. Table 5.1: Combination of R and R s c q-bit V Q R 0.25 1 1.75 1/8 0.50 2 1.50 2/8 0.75 3 1.25 3/8 1.00 4 1.00 4/8 1.25 5 0.75 5/8 1.50 6 0.50 6/8 1.75 7 0.25 7/8 2 8 0 1 R s c r c 5.2 Punctured Convolutional Codes (PCCs) 5.2.1 PCC Encoding and Decoding PCCs [31]-[37] have drawn considerable attention in recent years, because one would like to build a system with more flexible rate channel codes when the channel states or characteristics change very often. PCCs were first introduced by Cain, Clark, and Geist [34]. They used a fixed CC (n, k, m) to generate high-rate PCCs by periodically deleting (puncturing) bits with period p from one or more of the encoder output streams. The resulting high-rate codes are defined by the low-rate code used, called the original code, and by the nx p perforation matrixes which show the pattern (the number and specific positions) of the punctured bits. For example, for the rate 1/2 code (2, 1, 2) in Figure 3.2, the perforation matrix of rate 2/3 punctured code is given by 65 Chapter 5 Rate Allocated Image Transmission Systems where 0 means the corresponding bit symbol will not be transmitted, and 1 means the corresponding bit symbol will be kept to transmit. The trellis of the rate 2/3 punctured code from the 1/2 original code is shown in Figure 5.2, where the symbol x indicates the punctured bit. Every period, with 2 bits input, the fourth coded bit is not transmitted and 3 bits are transmitted instead of 4 bits, so the rate of this PCC is 2/3. The decoding of PCC is similar to the Viterbi decoding algorithm for the original code. The decoding is performed on the trellis of the original low-rate code by inserting a dummy data bit into the position corresponding to the punctured bit symbol. In the decoding process this dummy data bit is discarded by assigning it the same metric value (usually zero) regardless of the code bit symbol, 0 or 1 [33]. state OQ 00 Ox 00 01 10 11 Figure 5.2: Trellis for R = 2/3 PCC based on (2,1, 2) code Chapter 5 Rate Allocated Image Transmission Systems 66 5.2.2 Search for Good PCCs Let the number of ones in the perforation matrix be /. The rate of generated PCC from a 1/ n original code with puncturing period p will be r = y . By changing the value of p or /, varic able-rate codes of all punctured rates of interest are readily obtained from the same low-rate encoder. Unlike the search for the usual convolutional codes, the search for punctured codes is often based on intuition and trial rather than on a strict mathematical construction [36]. We choose the (3, 1, 8) convolutional code as the original code with the generator polynomial g!=557 , 8 g =663 , and g =771 because it has powerful error protection ability. Our research is based on 2 8 3 8 the intuition that "good codes generate good codes". We apply the following process to look for the best variable rate PCC from this 1/3 rate original code: In practice we only consider PCCs at the reasonable allocation 0.75 < R < 2 due to the s corresponding VQs' high source distortion when R is small. For R = 2 or r = 1, all bits are allos s c cated to the source encoder, which means no channel coding. So the variable channel coding rates required for our system are 3/8, 4/8, 5/8, 6/8, and 7/8. To generate a punctured code with rate r = c j/8, 3 < 7 ^ 7 , we choose the perforation matrix period p = j . With j input bits in a period, the encoder should have 8 output bits for the rate j/8 code. Thus in the pattern of the perforation matrix 3 x y, 3 < y' < 7, 8 positions are assigned to 1, and the other positions are assigned to 0. o Consequently there are C , . possible perforation matrixes for the rate j/8 codes, where C is the j X J combination function; in another words, we have C® • possible codes with rate j/8. x 67 Chapter 5 Rate Allocated Image Transmission Systems Then, among these same rate codes, we will select the best code which has the best performance over the AWGN channel. It is known that an upper bound on the bit error probability P of b a PCC with a period p is given by [34] [37]: (5.3) where d free is the free distance of the code and Cj is the total number of bit errors in all the incor- rect paths of Hamming weight i , i > dj- . Pi is the probability that one such incorrect path is ree selected in the Viterbi decoding process. For the AWGN channel and BPSK modulation, (5.4) where r is the channel coding rate, and E / N is the energy per bit-to-noise density ratio, c b 0 Thus, the criterion for searching the best punctured code is to select one with the maximum d free and the minimum Cj. After obtaining all the possible perforation matrixes, we calculate the corresponding d free and Cj of each code. The codes with maximum d free are picked out first, then among these codes, we select one with the minimum Cj as the best code. Of course, we have to check if the resulting code is not catastrophic code which may translate a small number of errors in the received codeword to an unlimited number of data error. In the above way, we obtain the required best variable-rate PCCs, which have the follow- 68 Chapter 5 Rate Allocated Image Transmission Systems ing perforation matrixes: 0 1 1 3/8 PCC: P = 1 1 1 1 1 1 , 4/8 PCC: P = 110 , 5/8 PCC: P 1111 1111 10 = 10 10 0 10 1 0 1 1 1 1 10 0 0 0 0 0 0 0 0 0 6/8 PCC: P = 110 OOOO 7/8 PCC: P = 110 10 1 1 0 1 0 0 0 0 0 1 1 10 0 1 1 0 0 Their B E R performance is shown in Figure 4.3. I. .•tV . i..: ^ —rX . : ). ! \ \ : :;::::::::::;:\::::::::;:::::: •:.:;:::::::::::: ::::::;::::::::: s : \ : s \ : s ,...: ;.\ ; :\:::: \ : \ !..\ i :;::::::\:::;::::::::::1s..::::::::::::::\:::;:::::::::: i.\ .; \ :..> S/S P C C • e • 4/8 P C C • •+ • 5/8 P C C • V - 6/8 P C C ; \.. : .V : \ : \ 7/8 PCC -3 -1 -2 E s / N o of c h a n n e l O Figure 5.3: BER performance of the various rate PCCs based on (3,1,8) code In a practical encoding implementation, the original channel encoder is followed by a puncturing table, which is used to store the perforation matrixes corresponding to the different rates. The output streams of the original coder are punctured according to the puncturing table 69 Chapter 5 Rate Allocated Image Transmission Systems associated with the selected rate. 5.2.3 MMAD for PCCs After obtaining the variable rate codes we need, and their B E R performance, similarly as in Chapter 4 for C C decoding, we apply the M M A D technique to the P C C decoding. In this chapter, we only consider the Viterbi based trellis merging M M A D technique for our rate allocated systems because the memory of our channel codes is greater than the longest source code word length. The B E R performance of the 3/8 P C C decoding with and without M M A D for the 3-bit V Q encoded 512 by 512 Lena image is shown in Figure 5.4. We see that M M A D improves the conventional P C C Viterbi decoding at noisy channel by taking advantage of the source statistics. When the channel S N R becomes high, the performance of two decoders converges. O •0 • 10 3bit V Q + 3/8 P C C 3bit V Q + 3/8 P C C + M M A d o 10 • 10"' 10 -4 -3.5 -3 Es/NO of c h a n n e l Figure 5.4: BER performance of PCC decoding with or without M M A D , 512 Lena For the latter rate allocated systems, we simulate the B E R of the various rate P C C s using Chapter 5 Rate Allocated Image Transmission Systems 70 M M A D with the corresponding source rate VQ for the Lena image. The results for the R=2 family are shown in Figure 5.5. : : : : : 1 : : : : : : : : : : 1 : : : : : :; ; ; ! : ; ; ; [ r-^ : : 1 :::!::: : : : : : : : ! : : : : : : : : : : : - •.«&. i" i l " : : ^ : . : ^ : : : : : t l + s i : : : : < i^. . . . •. ^ . . . ^. .' ^ . . : . . . : : isiri i : : : : : : : rs : :SaU i i i : ..v.... . ..;>..... v • V " " " : . . . . .s - :s.::::;; N ........ ' "V . ...... : : : : \ • N . \ : 3-bit 4-bit • -+• 5 - b i t 6-bit • <• 7 - b i t i VQ+3/8 P C C VQ+4/8 P C C VQ+5/8 P C C VQ+6/8 P C C VQ+7/8 P C C i x ', X; : : " " " s^: : :::x : : ....... N \ \ : : : : : : : :'ha: : : : : : -1 : \ : : : : : : : :: ~\: : : : : : : : v : : : : : ^ \ • \ x \ j -2 E s / N o of c h a n n e l X X . >+ : : : I : : : : : : : : : : : : : : : : r: X N - - . - • VX \ - V :: : ..:x ... . : : : : : X N: : 1 : N N " " \ > ; 4". ::::::::: v : ! r: ^ N v \ ; > Figure 5.5: BER performance of VQ/PCC family at R=2 with M M A D , 512 Lena Because MMAD uses the source statistics to aid the channel decoding, the BER performance of PCC using M M A D should be a function of the source statistics which will be related to the source characteristics and the source encoder. We use a discreet event simulation to obtain the BER of the 3-bit VQ with 3/8 PCC using MMAD for the 512 by 512 Lena image and the 256 by 256 Sena image. In Figure 5.6, as expected, we see that PCC plus M M A D for the Sena image is different from that for the Lena image. 71 Chapter 5 Rate Allocated Image Transmission Systems • "~ci~:::: -€> e M M A D for 512 Lena 3bit V Q M M A D for 256 S e n a 3bit V Q -4.5 Figure 5.6: -4 -3.5 Es/No of channel B E R performance of P C C with M M A D for different images 5.3 Distortion Calculation for Rate Allocated Systems The calculation of the end-to-end distortion is used to determine the optimal rate allocation for rate allocated systems [3][38], which select the rate with the minimum distortion as the optimal rate. For the system in Figure 5.1, we define the total distortion D of the system as t D = E[d(V, V')], where V is the source input vector, and its reproduction V' is the output of t the receiver. When the channel errors are independent of the source, and the source encoder is designed to meet the centroid condition, which means the reproduction codevector corresponding to the binary code s is the centroid of the quantization region R : r\(s) = E[V\ v e R ], the total s s distortion D is the sum of source distortion D and channel distortion D [3][38]; therefore: t s c 72 Chapter 5 Rate Allocated Image Transmission Systems D = D D s + t (5.5) c D = £ [||V-ri(^(y))|| ] D = c £ 4 > 4 (5.6) 2 v s . [ | | T I ( 5 ) - ? - 1 ( 3 ) I I , 2 (5.7) ] where D is the distortion-rate performance of the vector quantizer and is known or precomputed s for the chosen VQ. D is determined by the channel encoder, decoder and source statistics. We c have: c = J^n^Pi^h^-q-Hs^ D (5.8) 2 where P(s) is the source coded data statistics which can be precomputed if the source encoder is fixed. P(s'|s) is called the index crossover probability, which is a function of the channel encoding, modulation, channel decoding and the channel character. When the bit errors of the channel decoder output are independent, the bit error probability P , the index crossover probability is calb culated as P -(l-P ) ClR -n P(s'\s) = n (5.9) s b b where n is the Hamming distance between index s and index s'. In addition to P(s'|s), we need to know the source encoder codebook; using (5.8), D is c easily calculated. Thus, having D and D , the total distortion D is obtained staightforwardly. s c t After calculating all possible D for each possible rate, we choose the R with the minimum D as t the optimal rate which is sent to the transmitter. s t 73 Chapter 5 Rate Allocated Image Transmission Systems We can see that the bit error probability P of the channel coding is an essential term b which may be more complicated for the calculation of the total distortion (5.5)-(5.9) than the other terms. For the system using PCCs, the bit error probability P of the PCC Viterbi decoding is not b related to the source statistics and can be efficiently computed, so this scheme was used to determine the optimal rate allocation for the rate allocated systems using the Viterbi decoding only [3][38]. When considering the system with MMAD, this method can be also used to determine the rate allocation for a M M A D system. However since the decoding decision of PCC with M M A D is influenced by the source statistics and source coders, it is difficult to get the bit error probability P . Because of this, it will be computationally complicated to determine the optimal rate allocab tion for the M M A D system. Because we do not want to worry about the calculation of P and its preciseness, we b choose an alternative scheme, model simulation, to determine the optimal rate allocation for our systems. Our optimality criterion is to maximize the average end-to-end RSNR. At the same channel SNR, we simulate every model in the system and calculate the end-to-end RSNR for each R ; s the rate with the maximum RSNR is selected as the optimal rate. It is true that at the rate with the smallest distortion, the RSNR = 10 • log — will be the largest, where D is the total end-to-end distortion, and a 2 is the image variance. Therefore, the two schemes are actually same for calculating the optimal rate allocation. Compared with the dis- Chapter 5 Rate Allocated Image Transmission Systems 74 tortion calculation, the model simulation scheme can be done off-line, too, with the similar simulation complexity. The result of the model simulation scheme is more straightforward. In the next sections we will use this scheme to determine the optimal rate allocation for non-MMAD and M M A D systems. First we will simulate the non-MMAD system. 5.4 Optimal Rate Allocation without MMAD According to Figure 5.1, we simulate each model in the following way: with all the required PCCs, we combine the VQ source encoder, the PCC channel encoder, the AWGN channel with the corresponding PCC decoder and VQ decoder. Given a certain channel SNR, if one selects R as the VQ source encoding rate, the corresponding PCC channel coding rate should be s r = R /R. At the receiver, the final RSNR is calculated. Then, according to the result of RSNRs, c s we select the R with the largest RSNR and decree it to be the optimal rate for this channel SNR. s This process will be repeated for each R 0.75 < R < 2. Then we repeat the above process for s s other channel SNRs. Then we plot these results on one graph. The result of the optimal rate allocation for the 512 by 512 Lena is shown in Figure 5.7. It is seen from this figure that the improper choice of R can reduce the RSNR by 10-20 dB. As s expected, with the channel SNR increasing, the value of the optimal rate R is increased, too, since s less bits are needed for the channel coding when the channel becomes cleaner. The optimal rate result obtained by the model simulation scheme is the same as that obtained by the distortion calculation in [3]. The solid line with the symbol "+" shows the simulation result of the transmission of the rate R VQ encoded data only over the noiseless channel. We will use it to compare with the pers Chapter 5 Rate Allocated Image Transmission Systems 75 formance of VQ with PCC over the AWGN channel at the different channel SNRs. We see that RSNR increases monotonically as the channel SNR increases. It is a fact that with the certain rate R VQ, when all the channel errors are corrected by the corresponding rate PCC, the final RSNR s value should be equal to the RSNR value corresponding to the same rate R on the solid line. In s these cases, the total distortion is contributed by the source distortion. We choose the rate with the highest RSNR as the optimal rate for the certain channel SNR. The figure shows that the optimal bit rate R is often at the point that the RSNR is approximately s the same as the value on the solid line associated with the same rate R , except in the worst chans nel situation SNR = -3dB. This also means that most of the total distortion at the optimal rate allocation (R , R ) is determined by the source distortion. It is due to the fact that at the optimal rate s c allocation, the channel bit error-probabilities of the PCC decoding are approximately zero, that channel errors are almost all corrected. Refer to the bit error probability or bit error rate (BER) of the PCC decoders based on the Viterbi algorithm in Figure 5.3. Our simulation found the deviation, rj, of the RSNR result to be less than 0.2 dB, by using 10 different seed numbers to retransmit the same image. So to save simulation time, the reported RSNRs for the curves of this chapter are obtained by using only one seed number. 76 Chapter 5 Rate Allocated Image Transmission Systems -*— no noise e _i 0.6 Es/N0 = 0dB i i 0.8 1 Figure 5.7: i I i 1.2 1.4 1.6 Rs(bpp), Iena.img512 i i i_ 1.8 2 2.2 Optimal rate allocation for the conventional system without M M A D Following this, we select other images with different variance, correlation and size, and apply the non-MMAD system to see if the optimal rate allocation is changed with image. From our results in Table 5.2, the optimal rate allocation turns out to be fairly independent of the image. We find that in the few cases, when the optimal allocation differs from our reported image independent allocation, that the price in RSNR is very small (always less than 0.5 dB). The point of optimal rate allocation always is the allocation where most the channel errors are corrected and this does not depend on the image. It is known that the BER performance of the PCC decoding without M M A D does not relate to the source statistics, but to the channel codes' character and channel SNR. Chapter 5 Rate Allocated Image Transmission Systems 77 Table 5.2: Optimal R for non-MMAD systems for the various images s Lena 512 Pepper51 2 Couple 512 Lena 256 Sena 256 Couple 256 -3 0.75 0.75 0.75 0.75 0.75 0.75 -2 0.75 0.75 0.75 0.75 0.75 0.75 -1 1.00 1.00 1.00 1.00 1.00 1.00 0 1.00 1.00 1.00 1.00 1.00 1.00 1 1.25 1.25 1.25 1.25 1.25 1.25 2 1.25 1.25 1.25 1.50 1.25 1.50 3 1.50 1.50 1.50 1.50 1.50 1.50 Es/No (dB) This result is very useful for the design of the rate allocation for the conventional nonM M A D system. The optimal rate allocation non-MMAD system associated with the channel SNR can be calculated off-line only once. If we store the result into a mapping table, the system can use a table look-up to determine the rate. 5.5 Optimal Rate Allocation with MMAD Here we continue to use the model simulation to study the optimal rate allocation for the system with MMAD. The simulation process is the same as the above, except it uses the M M A D PCC decoders instead of PCC conventional decoders. We obtain the optimal rate allocation of the M M A D system with the 512 by 512 Lena image using the curves shown in Figure 5.8. Comparing the optimal rate allocation of the conventional non-MMAD system with that of the M M A D system, there are some similarities and some differences. One similarity is that the optimal rate R is increased as the channel SNR is increased. Similarly, the improper choice of the s Chapter 5 Rate Allocated Image Transmission Systems optimal rate R can reduce the system RSNR by 4-10 dB; this value is less than that of the cons ventional non-MMAD system. It is also true for the M M A D system that at the optimal rate, the total distortion is mostly determined by the source distortion; the B E R of P C C with M M A D is approximately zero. However, an interesting result is found in that the optimal rate allocation for V Q using PCC with M M A D is not always the same as that for V Q using PCC only. For the same channel SNR, the increased channel error protection capability offered by including M M A D results in an optimal rate allocation which gives more rate to the source coding operation. Figure 5.8: Optimal rate allocation for the system with M M A D We continue to investigate the optimal rate allocation of the M M A D system for various 78 Chapter 5 Rate Allocated Image Transmission Systems 79 other images. For the same channel SNR, the optimal rate of the M M A D system is often higher than that of the non-MMAD system. Unlike the conventional system, the optimal rate allocation is not always the same for different images. See Table 5.3. Table 5.3: Optimal R for MMAD systems for the various images s Lena 512 Pepper 512 Couple 512 Lena 256 Sena 256 Couple 256 -3 0.75 1.00 0.75 0.75 1.00 0.75 -2 1.00 1.00 1.00 1.00 1.25 1.25 -1 1.25 1.50 1.00 1.25 1.75 1.25 0 1.50 1.50 1.25 1.75 1.75 1.75 1 1.75 1.75 1.25 1.75 1.75 1.75 2 1.75 1.75 1.75 2.00 2.00 2.00 3 2.00 2.00 1.75 2.00 2.00 2.00 Es/No (dB) To make this result clearer, we define AR as the difference of the optimal rate allocation S between the two systems (5.10) AR = RM-RN S where the R** is the optimal rate allocation R for the system using M M A D , and is the s optimal rate allocation R for the non-MMAD system. From Table 5.4, we see that AR s are not s s always same for the different images, though AR s are almost always greater than zero. S Because the BER of the PCC using MMAD is a function of image statistics and the source VQ encoder and channel character, and that the optimal rate is often occurred at the BER equal to zero, the optimal rate allocation for the system with M M A D will depend on the image variance, Chapter 5 Rate Allocated Image Transmission Systems 80 VQ encoder and the channel SNR. That is why AR s in Table 5.4 is not often the same for the s different images at the same channel SNR. Table 5.4: AR between the two systems for the various images S Es/No (dB) 512 Lena 512 Pepper 512 Couple 256 Lena 256 Sena 256 Couple -3 0.00 0.25 0.00 0.00 0.25 0.00 -2 0.25 0.25 0.25 0.25 0.50 0.50 -1 0.25 0.50 0.00 0.25 0.75 0.75 0 0.50 0.50 0.25 0.75 0.75 0.75 1 0.50 0.50 0.00 0.50 0.50 0.50 2 0.50 0.50 0.50 0.50 0.75 0.50 3 0.50 0.50 0.25 0.50 0.50 0.50 After determining the optimal rate allocation for the VQ with PCC transmission systems, here we propose a rate-allocated MMAD system B, which always uses the optimal rate allocation for the system applying MMAD. System B will be compared with the conventional rate-allocated non-MMAD system A, which always uses the optimal rate allocation for the system without MMAD. We apply the two systems for the following images: 512 by 512 Lena, Peppers, Couple and 256 by 256 Sena. Figure 5.9. shows that when the source and the channel coding are optimally rate allocated, system B often gives a superior performance to the conventional rate allocated system A. The average improvement in RSNR of the rate allocated MMAD system is about 2.4 dB for the 512 Lena image, 2.85 dB for the 512 Peppers image, 4.5 dB for the 512 Couple image, and 4.1 dB for the 256 Sena image. Chapter 5 Rate Allocated Image Transmission Systems 81 This significant improvement is because that for the same channel SNR, system B often selects the larger optimal rate R than that system A, which will make the source distortion s smaller. Even when it chooses the same R , MMAD has stronger error protection ability than the s conventional PCC decoding which will make the channel distortion smaller. 30 ^<>- " ' <y " ' s •— •Oitoputm M -M M AD — e A:B:opm imay lrarteatealo acloactead tednonM AD 1 EsN / o of 0 AWGN chann el (a) 512 by 512 Lena -1 1 EsN / o of 0 AWGN chann el (b) 512 by 512 Peppers Chapter 5 Rate Allocated Image Transmission Systems 82 (d) 256 by 256 Sena Figure 5.9: Optimally rate allocated systems with and without MMAD The reconstructed images are shown in Figures 5.10 and Figure 5.11. They compare the performance of the two systems at the channel SNR OdB for the 512 Lena image and that of the Chapters Rate Allocated Image Transmission Systems 83 channel S N R -2dB for 256 for the Sena image. The original Lena and Sena images are shown in Chapter 2. The difference in the clarity of these images is much more evident on a high-resolution computer monitor than the shown low-resolution printer output. For the Lena image when the channel S N R = OdB, system A chooses the higher optimal rate R = l.Obpp, and system B applies R = 1.50bpp. Their respective R S N R s are 24.96 d B , and s s 27.30 d B . The gain of the optimally rate allocated M M A D system is 2.46 d B . For Sena at channel S N R = -2dB, the gain of the optimally rate allocated M M A D system is 3.34 d B . These results show that the improvement of optimally rate allocated M M A D is very significant. (a) System A , R S N R = 24.96 dB R =1.00bpp s ( b ) S y s t e m B , R S N R = 27.30 d B R =1.50bpp s Figure 5.10: Performance of the two rate allocated systems at channel SNR = 0 dB Chapter 5 Rate Allocated Image Transmission Systems (a) System A, RSNR = 20.93 dB R = 0.75bpp s (b) System B, RSNR = 24.27dB R =1.25bpp s Figure 5.11: Performance of the two rate allocated systems at channel SNR = -2dB 5.6 Sensitivity to Channel Mismatch Because the optimal rate allocation depends on the channel SNR E / N , the performance s 0 of the rate allocated systems will suffer if the channel SNR is estimated in error. Here we will make a channel mismatch sensitivity analysis. Suppose we calculate the optimal allocation when the channel SNR is estimated as, for example, 2 dB, but when we send the data the channel SNR is actually 1.5 dB. How much performance will we lose? Figures 5.12 shows the effect of channel mismatch for the systems A and B. In each of these figures, we show the RSNR versus channel SNR curve for the system designed with perfect knowledge of the channel SNR, as well as three curves, each of which is obtained by using the allocation determined to be the best at a particular SNR, and using this allocation for transmission at any channel SNR. For example, the curve labeled "designed at SNR = 0 dB Rs=1.50 bpp" Chapter 5 Rate Allocated Image Transmission Systems 85 shows the performance attained over the entire range of channel SNRs when we transmit using the allocation which is only optimal at the one channel SNR of 0 dB. The difference between this curve and the ideal design curve at the channel SNR 1 dB (-1 dB) gives the performance loss when the channel SNR has been under-estimated (over-estimated) by 1 dB. For system A a 1 dB mismatch can cause a 1.2 dB loss in RSNR; while for system B a 1 dB mismatch can cause a 2.0 dB loss in RSNR. However, system B still achieves the higher absolute RSNR value than system A in the same case of channel mismatch. The slightly greater noise sensitivity of system B is due to the fact that Markov-model aided decoding requires an estimate of the channel SNR, while non-Markov-model aided decoding does not. The curves designed for a particular channel SNR fall off more rapidly from the ideal result at decreasing channel SNR, indicating that the loss is greater when the channel SNR is over estimated. Therefore, the main conclusion to draw from the noise sensitivity analysis curves is that for both systems, when the channel SNR is imperfectly known, it is better to design the source and channel code for a pessimistic estimate of the channel SNR. er 5 Rate Allocated Image Transmission Systems (a) Non-MMAD rate allocated system A (b) MMAD rate allocated system B Figure 5.12: Effect of channel mismatch for the two rate allocated systems Chapter 6 Conclusions and Future Work 6.1 Summary In this thesis, we have investigated joint source-channel code design for Vector Quantized image transmission systems. We reviewed the LBG algorithm for VQ codebook design, and have considered two methods for assigning binary codewords (indices) to the resulting quantizer output points in the codebook. Of the two index assignment schemes we have found the natural binary code from the splitting algorithm to be the more noise robust, and have used it in the remainder of our study. A noise robust source coder such as the one that we use has substantial residual redundancy in its output stream. In our approach, the channel decoder makes use of this residual redundancy by the technique known as Markov Model Aided Decoding. MMADs can be symbolby-symbol decoders, or can be sequence decoders. As well, they can use a Markov Model of any finite order. In order to choose among the various M M A D options, we first considered M M A D without explicit channelcoding. We found the O(l) sequence decoders to significantly outperform the O(l) symbol-by-symbol decoders. However, the 0 ( 2 ) symbol-by-symbol decoder with Soft Decision Feedback performs almost as well as the 0 ( 2 ) sequence decoder with Soft Decision Feedback. For the symbol-by-symbol decoders with SDF, increasing the order of the Markov model from one to two significantly improves the performance. For the sequence decoders, the performance gain attained by increasing the order of the Markov model from one to two is slight by RSNR measure. Because the 0 ( 1 ) sequence M M A D method is easily incorporated into the convolutional codes, in the ensuing investigation we considered only the O(l) sequence decoders. We went on to consider MMAD with explicit channel coding, taking the channel codes to 87 Chapter 6 Conclusions and Future Work 88 be convolutional codes. To make optimal use of the source statistics in the decoding process the technique called trellis merging was found to be necessary. However, this technique is restricted to the cases in which the source codewords are shorter in length than the memory of the channel code. We proposed a concatenated system in which a pure (non-model aided) channel decoder based on the BCJR algorithm passed the a posteriori source bit probabilities to a cascaded M M A D which sequence decodes the noise corrupted source bit stream using the Markov model (i.e. the second stage consists of an MMAD without channel coding). Even though the passing of soft-information insures that there is no information loss incurred by breaking up the decoding into two stages, we find that the performance of the concatenated decoder is inferior to that of the integrated, merged trellis decoder. This is because in the concatenated system the reliability of the channel information is increased before the source information is applied to bias the decoding decision. In the integrated decoder, the source information biases a decision based on the raw channel data, and provides a more effective bias at this point in the decoding process. We found very large gains - up to 9 dB in RSNR - by using MMAD. However, these large gains are attained in a region of low channel SNR where the channel code is no longer effective. To make a more fair evaluation of M M A D , we considered applying M M A D in a rate allocated system. Given a fixed information transmission rate (in pixels per second), and a fixed transmission channel bandwidth, the total distortion of the image transmission is significantly reduced by optimally allocating the overall coding rate between the source coding and the channel coding operations. Authors, including the present, have found that in an optimally rate allocated system the bit error probability is usually very low. Since the M M A D techniques give little improvement when the error rate is low, this would indicate that M M A D is not useful for rate-allocated systems. However, by comparing with the analogous the conventional rate allocated non-MMAD system, Chapter 6 Conclusions and Future Work we found the interesting result that indeed M M A D can improve a conventional rate-allocated system; and in fact the coding gain is typically around 2 dB in channel SNR. This is because M M A D does increase the SNR range over which the channel code provides a low probability of bit error. This increased strength in the channel code results in a rate allocation that gives more of the overall fixed rate to the source coder, thus resulting in a higher quality image even when the bit error rate is low. Because the optimal rate allocation is always at the point where the channel code is just strong enough to correct almost all the errors, for non-MMAD the optimal rate allocation is almost independent of the image. This means that a system can be simply implemented by employing a table look-up for the rate allocation to use at a particular channel SNR. However, for M M A D the BER depends on the image, and therefore the rate allocation must be determined for each image by an off-line calculation before the image can be formatted for transmission. We did the calculation by employing a discreet event simulation. This calculation could be done more efficiently if one could find an analytic expression for the BER of a Markov-model aided channel code. Our results give strong motivation to solve this open problem. Because the point of optimal rate allocation depends on the channel SNR, inaccurate channel SNR estimation generally decreases the performance of the rate allocated systems whether or not they employ MMAD. Our experiments indicate that M M A D and non-MMAD rate allocated systems have similar sensitivity to channel SNR mismatch, and both are fairly robust. Based on the performance results, one is better off selecting the optimal rate for a pessimistic channel SNR if the value cannot be known precisely. The M M A D applied to the rate allocated systems is the 0(1) sequence M M A D . Because 89 Chapter 6 Conclusions and Future Work the 0(2) sequence M M A D with SDF gives better performance than the 0(1) sequence M M A D , we could also improve the performance of the rate-allocated systems by using the 0(2) sequence M M A D with SDF. However, this would increase the computational complexity significantly because the channel decoder would have to be changed from Viterbi-based to BCJR based. 6.2 Proposed Future Work Suggestions for future study of MMAD for VQ image transmission are as follows: • Find an analytic expression for the BER of MMAD, so the rate allocation can be calculated more efficiently. • Evaluate the MMAD rate-allocated system performance over fading channels. • Consider other VQ techniques, channel codes, and modulation methods. • Study ways to obtain an accurate channel SNR estimate. 90 Glossary app a posteriori probability AWGN Additive White Gaussian Noise BER Bit Error Rate BSC Binary Symmetric Channel CC Convolutional Code bpp bits per pixel GLA Generalized Lloyd Algorithm HDF Hard Dicision Feedback LBG Linde-Buzo-Gray JSCC Joint Souce/Channel Coding MMAD Markov Model Aided Decoding or Markov Model Aided Decoder MMACD Markov Model Aided Convolutional Decoding or Markov Model Aided Convolutional Decoder NBC Natural Binary Code O(l) first order 0(2) second order PCC Punctured Convolutional Code RSNR Reconstruction Signal-to-Noise Ratio SNR Signal-to-Noise Ratio VQ Vector Quantization 91 Bibliography [I] C E . Shannon. "Coding Theorems for a Discrete Source with a Fidelity Criterion.", IRE National Convention Record, Part 4, pp. 142-163, 1959. [2] C.E.Shannon, Collected papers, N . J. A. Sloane and A. Wyner, Eds. New York, IEEE Press, pp. 40, 1993. [3] Andrea J. Goldsmith, Michelle Effros, "Joint Design of Fixed-Rate Source Codes and Multiresolution Channel Codes", IEEE Transaction on Communication, vol. 46, pp. 13011312, Oct. 1998. [4] S. Emami and S. Miller, "DPCM Picture Transmission over Noisy Channels with the Aid of a Markov Models,", IEEE Transaction on Image Processing, vol. 4, no. 11, pp. 1473- 1481, Nov. 1995. [5] [6] Robert Link and Samir Kallel, "Optimal Use of Markov Models for DPCM Picture Transmission over Noisy Channels", submitted to IEEE Transaction on Communication, Feb. 1999. K. Sayhood,' F. Liu and J.D. Gibson, "A Constrained Joint Source/Channel Coder Design", IEEE Journal Selected Areas Communication, vol.12, no. 9, pp. 1584-1592, Dec. 1994. [7] W. Xu, J. Hagenauer, and J. Hollman, "Joint Source-channel Decoding Using the Residual Redundancy in Compressed Image", ICC/SUPERCOMM'96, pp. 142-148, June 1996. [8] Rober. Link, Norman C. Lo and Samir Kallel, "Source-Aided Turbo Decoding of Serially Concatenated Codes", submitted to IEEE Transaction on Communication, May 1999. [9] Retrand Hochwald, "Trade-off Between Source and Channel Coding on a Gaussian Channel", IEEE Transaction on Information. Theory, vol. 44, pp. 3044-3055, Nov. 1998. [10] [II] Khalid Sayhood, "Introduction to Data Compression", Morgan Kaufman Publishers, Inc., 1992. T.M. Cover and J.A. Thomas, "Elements of Information Theory", IEEE Transaction on Information Theory, vol. 29, pp. 820-824, Nov. 1983. 92 93 [12] T. Berger, "Rate Distortion Theory: A Mathematical Basis for Data Compression", Englewood Cliffs, NJ: Prentice Hall, 1971. [13] R.M. Gray, "Entropy and Information Theory", New York: Springer-Verlag, 1990. [14] LINDE Y., BUZO A., and GRAY R.M., "An Algorithm for Vector Quantizer Design", IEEE Transaction on Communication, vol. 28, pp.84-95, Jan. 1980. [15] Robert M . Gray, David L. Neuhoff, "Quantization", IEEE Transaction on Information Theory, vol. 44, no. 6, pp. 2325-2383, Oct. 1998. [16] "Global Convergence and Empirical Consistency of the generalized Lloyd algorithm", IEEE Transaction on Information Theory, vol. 32, pp. 148-155, Mar. 1986. [17] K. Zeger and A. Gersho, "Pseudo-Gray Coding.", IEEE Transaction on Communication, vol. 38, no. 12, pp. 2147-2158, Dec. 1990. [18] Farvardin, N., "A Study of Vector Quantization for Noisy Channels", IEEE Transaction on Information Theory, vol. 36, no. 4, pp. 799-809, 1990. [19] H-S. Wu and J. Barba, "Index Allocation in Vector Quantization for Noisy Channels", Electron Letter, vol. 29, no. 15, pp. 1317-1319, July 1993. [20] J. R. B. De Marca and N. S. Jayant, "An Algorithm for Assigning Binary Indices to The Codevectors of a Multidimensional Quantizer", IEEE International. Communication Conference, Seattle, WA, pp.1128-1132, June 1987. [21] J. Hagenauer, "Source-Controlled Channel Decoding", IEEE Communication, vol. 43, no. 9, pp. 2449-2457, Sept. 1995. [22] Stephen Bryant Wicker, "Convolutional Codes", chapter in the book of Error Control Coding, pp. 268-271. [23] Robert Link and Samir Kallel, "Markov Model Aided Decoding for Image Transmission using Soft-Decision-Feedback", submitted to IEEE Transaction on Communication, Mar. 1999. [24] W.E. Ryan. "A Turbo Code Tutorial", http://telsat.nmsu.edu/~wryan/turbo2c.ps. Transaction on 94 [25] L.R.Bahl, J.Cocke, F.Jelinek, and J. Raviv, "Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate", IEEE Transaction on Information Theory, vol. 20, no. 2, pp. 284-287, Mar. 1974. [26] Samir Kallel, Norman C. Lo, and Robert Link, "Markov Model Aided Channel Decoding", report, Nov. 1998. [27] P.Elia, "Coding for Noisy Channels", IRE Convention Record, Part 4, pp. 37-47, 1995. [28] A.J. Viterbi, "Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm", IEEE Transaction on Information Theory, vol. 13, pp. 260-269, Apr. 1967. [29] G. D. Forney, Jr. "Convolutional Codes: Algebraic structure", IEEE Transaction on Information Theory, vol. 16, no.6, pp. 268-278, Nov. 1970. [30] "The Algebraic Theory of Convolutional Codes", Handbook of Coding Theory, in preparation. [31] Norman C. Lo, "The Application of Source-aided Turbo Decoding to IS-95 CDMA Systems", master thesis, University of British Columbia, Dept. E E . , Apr. 1999. [32] Amin Alavi, "An Adaptive Subband-Based Joint Source-Channel Coder for Image Transmission", master thesis, University of British Columbia, Dept. E.E., June 1999. [33] David Haccoun, Guy Begin, "High-Rate Punctured Convolutional Codes for Viterbi and Sequential Decoding", IEEE Transaction on Communication, vol. 37, no. 11, pp. I l l 3- 1125,. Nov. 1989. [34] J. Bibb Cain and George C. Clark, JR., "Punctured Convolutional Codes of Rate (n-l)/n and Simplified Maximum Likelihood Decoding", IEEE, Transaction on Information Theory, vol. 25, no. 1, pp. 97-100, Jan. 1979. [35] Joachim Hagenauer, "Rate-Compatible Punctured Convolutional Codes and Their Applications", IEEE Transaction on Communication, vol. 36, no. 4, pp. 389-400, April 1988. [36] G. Begin and D. Haccoun, "High Rate Punctured Convolutional Codes: Structure Properties and Construction Techniques", IEEE Transaction on Communication, vol. 37, no. 12, pp. 1381-1200, Dec. 1989. 95 [37] Yutaka Yasuda, Kanshiro Kashiki and Yasuo Hirata, "High Rate Punctured Convolutional Codes for Soft Decision Viterbi Decoding", IEEE Transaction on Communication, vol. 32, no. 3, pp. 315-319, March 1984. [38] Hamid Jafarkhami, Paschalis Ligddas, and Nariman Farvardin, "Adaptive Rate Allocation in a Joint Source/Channel Coding Framework for Wireless Channels", IEEE Transaction on Communication, pp 492-495, 1996. Appendix A.l. BCJR Based Trellis Merging MMACD A s in the Viterbi based M M A C D , trellis merging techniques can be used i n the B C J R algorithm. Let L be the number of V Q source symbols in a block, an input sequence u composed of Lq-bit symbols and a few q-bit zeros u — (wj, ..., u^, ..., u^), x — L + m , where Uj = (uj°, Uj ,..., U ( / ~ ^ ) , composed of q bits represents one symbol instead of one bit, where j V Q source symbol. If we use a qn-bit channel codeword instead of a n-bit channel 1 Q bit in the i t h t h codeword, then the encoded channel codeword sequence w i l l be x = (JC,, xj = (x;°, X; ..., Xj 1 q _ 1 ) x, Uj J represents x ), L x where corresponding to the source symbol u x ^ x ^ ) , . . . ^ ^ " ) ) refers to the n-bit 0 1 1 1 i ; channel codeword corresponding to the source bit ur and xjW e ± 1 . F r o m the trellis diagram, 1 the output o f a branch w i l l be qn bits codeword. S i m i l a r l y , the received qn-bit c o d e w o r d sequence y = (y v ...,y , L y ), y = ( ° , yj ,..., y^" ), yJ = ( y ^ , y^ ),..,, y ^ ) . 1 T { 1 1 y i The equations in Section 4.21 needn't change except that the value of u, is from 0 to 2 instead of 0,1. q The transition probability (4.16) becomes: yi(s', s) = PiuAu^Piy^) where P^JIUJ.J) (A.l) is the a priori probability of the source symbol u, w h i c h cause the transition (s _ j = s') —> (5- = s) w h i c h results i n the encoded qn-bit codeword x ^ and P ( y j l X j ) is the t channel transition probability of the qn-bit channel codeword: 96 97 q-\n-\ (yi\ i) p = x n n p w w K w ) ( -2) a / = Ok = 0 Y,-0, s) = \ 1 (A.3) 1 I 0 else s' — » 5 means that the transition (J,-_ j = s') —> (s; = 5) exists because both encoder inputs u, and Uj.j have to be determined by the states SJ.J, Sj at times i-1 and i. This algorithm requires that q should be less or equal to the memory m of the code, too, because of using the merged trellis. For decoding, define Aj as the set of state Sj corresponding to the current input u, = j , j = 0. J 1 , 2 - l , which means that from Sj = (SJ , q 0 Sj 1 ,..., S i ( n > 1 ) ) , we can see that u ^ " ^ , u ^ s ^ " . 0 1 The decoder to choose Uj=j which maximizes: P("i = J\y) = jTTox X hi*) ( -> A 4 where j = 0, 1 , 2 - l . In practice, we use (4.19) and (4.20) to calculate a and (3 except that b q represents a symbol input, b = 0, 1 , 2 - l instead of a bit input 0 or 1. If q< m, we can see that q (4.18) (4.18) still can reduce the complexity of the computation. Our simulation result shows that the BCJR based trellis merging M M A C D gives essentially the same BER performance as the Viterbi algorithm with the Viterbi based trellis merging MMACD. On the whole, the trellis merging MMACD techniques can give better error protection when the channel SNR is low. Trellis merging reduces the overall length of the trellis by a factor of q, but increases the number of branches by a factor of 2 q_1 . When q is increased 98 from 1 to 2, the computation complexity can be ignored. The BCJR based trellis merging algorithm is more complicated than the Viterbi based trellis merging algorithm. It suggests that one had better use the Viterbi trellis merging algorithm if q<m. However the BCJR based trellis merging is useful for constructing source-aided turbo decoding systems[8] [31] or will be useful to other concatenated source-aided systems in the future. In this paper, we used the BCJR trellis merging without Markov model to generate the a posteriori symbol probabilities in order to compare with the concatenated decoding using the a posteriori bit probabilities.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Rate allocation for Markov model aided convolutional...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Rate allocation for Markov model aided convolutional coding of vector quantized image data Lin, Xiaoping 2000-12-31
pdf
Page Metadata
Item Metadata
Title | Rate allocation for Markov model aided convolutional coding of vector quantized image data |
Creator |
Lin, Xiaoping |
Date | 2000 |
Date Issued | 2009-07-06T22:30:43Z |
Description | This thesis proposes an optimally rate allocated image transmission system that uses Vector Quantization (VQ) for source coding, and a family of variable rate Punctured Convolutional Codes (PCCs) for channel coding. At the receiver, we apply the source aided channel decoding technique known as Markov Model Aided Decoding (MMAD). Our optimality criterion is to maximize the average end-to-end Reconstruction Signal-to-Noise Ratio (RSNR) under the constraints of a fixed information rate (in pixels per second) and a fixed transmission bandwidth. For a given channel SNR, this joint source-channel coder design achieves the optimal rate allocation between the source coding and the channel coding operations. Compared with the conventional rate allocated system (the analogous system that does not use MMAD), the proposed system gives significant performance improvement. This is due to the fact that MMAD increases the strength of the channel codes, thus allowing the system to allocate more rate to the source coder, which results in a higher resolution image. In the course of our study, we first investigate MMAD without explicit channel coding for VQ image transmission over the noisy memoryless channels comprising the Binary Symmetric Channel (BSC) and the Additive White Gaussian Noise (AWGN) channel. In order to evaluate the effects of the order of the Markov model of the data, we consider two types of decoding algorithms. One is based on the Viterbi sequence decoding algorithm, the other is based on the Bahl, Cocke, Jelinek and Raviv (BCJR) decoding algorithm. The former is computationally less complex, and is optimal (in the sense of minimizing the Bit Error Rate (BER)) for decoding with a first order (O(l)) model; while the latter allows an efficient, but slightly sub-optimal, decoding algorithm for decoding with a second order (0(2)) model. We find that most of the MMAD coding gain is already achieved by using the 0(1) model, and therefore in the remainder of the study consider it only. We go on to analyze two types of O(l) MMAD with Convolutional Codes (CCs) employed for explicit channel coding. We call the decoders Markov Model Aided Convolutional Decoders (MMACDs), and show via simulation that the performance benefits attained by using the Markov model are similar to the large gains found for MMAD without explicit channel coding. One type of MMACD is based on the Viterbi algorithm, and applies a trellis merging technique. This decoder has an optimal BER performance, but has the constraint that the length of the source codewords be less than the memory of the CC. The other MMACD is a concatenation of a soft-output channel decoder followed by an MMAD without channel coding. This decoder does not have the constraint on the length of the source codewords, but has less coding gain than the trellis merged decoder. Finally, we investigate the problem of optimal rate allocation between the source coding and the channel coding for VQ/PCC transmission systems that employ MMAD. Our simulation results over the AWGN channel show that the optimal rate allocated system is superior in RSNR performance to the optimally rate allocated system without MMAD. The MMAD coding gain depends on the image, but is typically 2 dB in channel SNR. We find that for the conventional system, the point of optimal rate allocation is fairly independent of the image; while for the MMAD system the allocation depends strongly on the image characteristics. Because of this, the rate allocation calculation is significantly more complicated when using MMAD. The rate allocated systems require an estimate of the channel SNR. Because in practice there will always be some inaccuracy in estimating this, to conclude our study we investigate the sensitivity of the rate allocated systems to channel mismatch, and find them to be fairly robust. |
Extent | 4811446 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Collection |
Retrospective Theses and Dissertations, 1919-2007 |
Series | UBC Retrospective Theses Digitization Project |
Date Available | 2009-07-06 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0065271 |
URI | http://hdl.handle.net/2429/10286 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2000-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- [if-you-see-this-DO-NOT-CLICK]
- ubc_2000-0109.pdf [ 4.59MB ]
- Metadata
- JSON: 1.0065271.json
- JSON-LD: 1.0065271+ld.json
- RDF/XML (Pretty): 1.0065271.xml
- RDF/JSON: 1.0065271+rdf.json
- Turtle: 1.0065271+rdf-turtle.txt
- N-Triples: 1.0065271+rdf-ntriples.txt
- Original Record: 1.0065271 +original-record.json
- Full Text
- 1.0065271.txt
- Citation
- 1.0065271.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
China | 21 | 24 |
United States | 17 | 1 |
Japan | 12 | 0 |
United Kingdom | 2 | 0 |
India | 2 | 0 |
France | 2 | 0 |
Germany | 2 | 1 |
Brazil | 1 | 22 |
Russia | 1 | 0 |
City | Views | Downloads |
---|---|---|
Beijing | 19 | 1 |
Tokyo | 12 | 0 |
Washington | 9 | 0 |
Ashburn | 8 | 0 |
Unknown | 6 | 23 |
London | 2 | 0 |
Shenzhen | 2 | 23 |
Recife | 1 | 0 |
Saint Petersburg | 1 | 0 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065271/manifest