A N ADAPTIVE SUBBAND-BASED JOINT CODER FOR IMAGE SOURCE-CHANNEL TRANSMISSION By Amin Alavi B . S c . (Electrical Engineering), University of Tehran, Tehran, Iran, 1990 A THESIS SUBMITTED IN PARTIAL F U L F I L L M E N T OF T H E REQUIREMENTS FOR T H E D E G R E E OF M A S T E R OF A P P L I E D SCIENCE in T H E FACULTY OF G R A D U A T E STUDIES D E P A R T M E N T OF ELECTRICAL AND C O M P U T E R ENGINEERING We accept this thesis as conforming to the required standard T H E UNIVERSITY OF BRITISH COLUMBIA June 1999 © A m i n A l a v i , 1999 In presenting this thesis i n partial fulfilment of the requirements for an advanced degree at the University of B r i t i s h Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of m y department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without m y written permission. Department of Electrical and Computer Engineering T h e University of B r i t i s h C o l u m b i a 2075 Wesbrook Place Vancouver, Canada V 6 T 1W5 Date: Abstract A n adaptive subband image coding system is proposed that uses D P C M and P C M codecs for source encoding the individual subbands, and a family of variable rate channel codes for forward error correction. A low resolution family of trellis coded modulation codes and a high resolution family of punctured convolutional channel codes are implemented and investigated. Implementation of unequal error protection among the subbands, and w i t h i n the subbands, is examined for the two separate versions of our system. Simulations are performed on the A W G N channel and comparisons are made w i t h corresponding systems that use only a single channel code, or that use the same family of codes for an adaptive equal error protection scheme. O u r proposed adaptive systems outperform any of the systems that use only a single channel code greatly, extending the useful S N R range by an amount that depends on the code family. A s well, our systems outperform the corresponding adaptive equal error protection systems by as much as 2 d B P S N R . This is p r i m a r i l y due to the use of unequal error protection among the subbands, as surprisingly little additional gain is achieved by applying unequal error protection w i t h i n the subbands. We use and improve a known modelling technique which enables the system to configure itself optimally for the transmission of an arbitrary image, by only measuring the mean of lowest frequency subband and variance of each of its subbands. Because our systems require an estimate of the channel S N R , we have investigated the sensitivity to poor channel S N R estimation, and have found negligible performance loss for channel mismatches up to 1.5 d B . ii Table of Contents Abstract i'i List of Figures vj List of Tables x Acknowledgments xi 1 Introduction 1 2 Source C o d i n g 6 2.1 Subband Coding 6 2.2 Subband F i l t e r i n g 6 2.3 Implementation on Images 8 2.4 2.5 2.3.1 Circular Convolution M e t h o d 10 2.3.2 Symmetric Extension M e t h o d 10 D P C M Encoding System 11 2.4.1 14 Prediction i n D P C M Quantization 16 2.5.1 U n i f o r m Quantizer . 2.5.2 N o n - U n i f o r m Quantizer 17 17 2.6 B i t Allocation 18 2.7 Simulation Results 24 iil 3 4 Channel Coding 28 3.1 Trellis Coded M o d u l a t i o n 28 3.2 Pragmatic Trellis Codes 29 3.3 Decoding T C M Codes 32 3.4 Performance Results 34 3.5 Punctured Convolutional Codes 38 3.6 Decoding P C Codes 39 3.7 Performance Results 40 Joint Source-Channel C o d i n g 45 4.1 Subband Image Modelling 46 4.2 B i t A l l o c a t i o n and Code M a p p i n g 51 4.2.1 53 4.3 Side Information Overhead Computation 55 4.4 Simulation Results 57 4.4.1 Performance Evaluation of the Proposed Systems Based on the T C M Code F a m i l y 57 4.4.2 Performance Evaluation for Systems Based on the P C Code F a m i l y 61 4.4.3 Universality and Effectiveness of the System 62 4.4.4 Performance Evaluation of the Systems Using a M o r e Noise Sensi- 4.4.5 5 C o m p u t a t i o n of Rate-Distortion Functions tive D P C M Encoder 63 Effect of Channel M i s m a t c h 65 Conclusions and Recommendations for Future Research 70 Glossary 73 Bibliography 77 iv A B Description of C o m p u t e r Simulation 81 A.l Source C o d i n g 81 A.2 Channel C o d i n g 81 A.3 A W G N Channel 82 A.4 Generation of G G D R a n d o m Variables 83 A.5 Confidence Interval 83 S u m m a r y of F E C Codes Used in the System v 85 List of Figures 1.1 Generic block diagram of a communication system 2 2.1 A subband coding system 7 2.2 A n 8-band filter bank 8 2.3 A n image subband encoding system 9 2.4 A simple two band subband coding system 9 2.5 S y m m e t r i c extension signals 2.6 Result of subband filtering applied to Lena image, (a) Original image, (b) 11 Lena image decomposed into 16 subimages. (c) Reconstructed Lena image. 12 2.7 A basic differential encoding system 14 2.8 D P C M encoding system 14 2.9 Performance of subband coding scheme for varying bit rate i n noiseless environment 26 2.10 Near perfect reconstruction i n noiseless environment, (a) Original L e n a image, (b) Reconstructed image using 0.5 bpp. (c) Reconstructed image using 0.75 bpp. (d) Reconstructed image using 1.0 bpp 27 3.1 Encoder/modulator for trellis coded modulator 29 3.2 Set partitioning of the 8 P S K signal set 30 3.3 A pragmatic encoder and its corresponding trellis diagrams (K 3.4 M a p p i n g schemes for pragmatic T C 1 6 P S K . (a) T h e scheme used i n [26]. c (b) T h e scheme introduced i n [27] = 3). . . 31 32 VI 3.5 (a) Signal space, (b) trellis diagram and (c) B E R performance of pragmatic rate 1/2 T C Q P S K . 3.6 . ! 35 (a) Signal space, (b) trellis diagram and (c) B E R performance of pragmatic rate 2/3 T C 8 P S K 3.7 36 (a) Signal space, (b) trellis diagram and (c) B E R performance of pragmatic rate 3/4 T C 1 6 P S K 37 3.8 P C C encoding and puncturing operation 39 3.9 Trellis of the punctured rate = 2/3 code to be used for decoding, (a) Modified trellis of the rate = 1/2 mother code, (b) Conventional trellis. . 3.10 Q P S K signal constellation 40 41 3.11 (a) Modified trellis diagram, (b) perforation m a t r i x and (c) B E R performance of rate 3/4 P C C 42 3.12 (a) Modified trellis diagram, (b) perforation m a t r i x and (c) B E R performance of rate 4/5 P C C 43 3.13 (a) Modified trellis diagram, (b) perforation m a t r i x and (c) B E R performance of rate 5/6 P C C 4.1 44 Histograms of: (a) D E M S L F S of Lena image, (b) other subbands of Lena image, (c) D E M S L F S of Couple image, (d) other subbands of Couple image, (e) D E M S L F S of M a n d image and (f) other subbands of M a n d image. 4.2 47 P r o b a b i l i t y density function of generalized Gaussian distribution w i t h selected parameter values 4.3 48 T h e general block diagram of the proposed image transmission system. vii . 53 4.4 Rate-Distortion curves for several channel conditions, (a) Z)i(r;), generated for M S L F S using G G D - m o d e l e d samples w i t h a = 1.70. (b) D ( ? \ ) , 2 generated for other subimages using G G D - m o d e l e d samples w i t h a = 0.75. 55 4.5 Performance comparison for channel rate R = 0.25 s y m b o l / p i x e l 58 4.6 Performance comparison for channel rate R = 0.5 s y m b o l / p i x e l 58 4.7 Performance comparison for channel rate R = 1.0 s y m b o l / p i x e l 59 4.8 Performance comparison for channel rate R = 0.25 s y m b o l / p i x e l , ( T C M code family used), (a) E E P system w i t h T C 1 6 P S K and R = 0.25, P S N R = 25.7 d B . (b) E E P system w i t h T C 8 P S K and R = 0.25, P S N R = 29.3 d B . (c) E E P system w i t h T C Q P S K and R = 0.25, P S N R = 28.1 d B . (d) System B w i t h R = 0.24, P S N R = 30.6 d B 4.9 60 Performance comparison for channel rate R = 0.25 s y m b o l / p i x e l , ( P C code family used) 63 4.10 Performance comparison for channel rate R = 0.5 s y m b o l / p i x e l , ( P C code family used) 64 4.11 Performance comparison for channel rate R = 1.0 s y m b o l / p i x e l , ( P C code family used) 65 4.12 Performance comparison for channel rate R = 0.25 s y m b o l / p i x e l , ( P C code family used), (a) E E P system w i t h rate 5/6 P C C and R = 0.225, P S N R = 22.5 d B . (b) E E P system w i t h rate 4/5 P C C and R = 0.234, P S N R = 24.4 d B . (c) E E P system w i t h rate 3/4 P C C and R = 0.25, P S N R = 25.8 d B . (d) System B w i t h R = 0.245, P S N R = 27.8 d B 66 4.13 Performance comparison for channel fate R = 0.25 s y m b o l / p i x e l , for C o u ple image ( P C code family used) 67 4.14 Performance comparison for systems employing 2D prediction, channel rate R = 0.25 s y m b o l / p i x e l , for Lena image ( P C code family used). viii . . . 68 4.15 Channel mismatch effect 69 B.l 85 B E R performances of the T C M and P C channel codes List of Tables 2.1 Statistical properties of 16 subbands of Lena image (512x512) 24 2.2 Statistical properties of 16 subbands of Couple image (512x512) 25 4.1 Results of the Kolmogorov-Smirnov test for a few test images 49 4.2 I D prediction coefficients for the test images 51 4.3 Throughput computed for systems using T C M and P C channel codes. . . 56 x Acknowledgments I would like to thank m y father A l i A l a v i Bedjestani and m y sister S a m i n for their continuous support and encouragement. I would also like to express m y appreciation to m y supervisor D r . Samir K a l l e l for his useful suggestions and constructive criticisms, which helped me to start the research and guided me to the completion of m y thesis. I a m deeply indebted to D r . Robert L i n k for his invaluable help throughout this work. He has been a consistent source of advice and guidance and has always been available for discussions. I a m grateful to National Sciences and Engineering Research C o u n c i l of Canada, B r i t i s h C o l u m b i a Advanced Systems Institute and M o b i l e D a t a Solutions Inc. of R i c h m o n d , B C , for their financial support. I would also like to thank M r . Shahram Shirani and m y other friends at the communication group of the department of Electrical and Computer Engineering for their helpful comments and discussions. xi Chapter 1 Introduction T h e evolution of wireless communication systems from analog to digital has opened a new era i n the history of mobile communication. Wireless transmission of image, video and other data has provided a wide range of services to the users of such systems. T h e high demand for such services, and the explosive growth i n the number of users, has made the l i m i t e d resources that are available to digital wireless communication systems even more valuable. T h i s has motivated researchers to modify conventional communication systems w i t h the goal of optimizing the use of the wireless resources. A conventional communication system, as depicted i n Figure 1.1, includes a source encoder that removes the source redundancy. Source encoding, also known as data compression, is intended to reduce the required bandwidth for transmission. T h e conventional system also includes a channel encoder that introduces a controlled amount of redundancy for error detection and correction, known as Forward Error Correction ( F E C ) . Shannon [1][2] proved that i n the limit of large coding block sizes, the separation of the source and channel coding operations does not cause any loss of optimality. T h i s has resulted i n p r i m a r i l y independent development of source and channel codecs i n the design of communication systems. However, for practical cases, where complexity is l i m i t e d , joint design of source and channel coders is a promising approach for achieving efficient bandwidth and power l i m i t e d solutions. A large amount of work has been carried out by researchers on the joint design of source and channel coding systems; like i n [3], where the source and channel coding 1 Chapter 1. Introduction Information Source 2 Source Encoder Channel Encoder o Information Sink Source Decoder Channel Decoder Figure 1.1: Generic block diagram of a communication system. operations are truly integrated. Whereas i n the work of [4] and [5], the known source coders are cascaded by known channel coders, and a bit allocation scheme determines the bit rate of the source coder and the channel coder for the best attainable performance. Some other researchers have modified the source encoder or decoder to account for the presence of the channel noise [6][7]. Protection Another idea for joint design is Unequal Error ( U E P ) , where the source is broken down into several groups, each of which is given a different level of protection against the channel errors [8] [9]. B o t h fixed rate and variable rate source encoders may be used i n the joint design of a source-channel encoding system. Because of error propagation, variable rate source coding tends to be catastrophic i n presence of noise, therefore fixed rate source encoding is the more preferred. However, for bandlimited channels where variable rate coding could still be favorable, packetization is introduced as a remedy to the error propagation problem [8]. In this thesis a joint source-channel image coding system is proposed and analyzed which makes use of a subband source encoder and a family of channel codes. A n o p t i m a l allocation of source coding rate to the subimages and the mapping of channel codes to the source bits is determined by a rate-distortion analysis which takes into account Chapter 1. Introduction 3 both the effects of lossy source compression and the effects of channel errors. In the proposed system, an image is decomposed into 16 subimages by using a bank of 8-tap Quadrature Mirror Filters ( Q M F ) , and Differential and Pulse Coded Modulation Pulse Coded Modulation (DPCM) ( P C M ) encoders w i t h L l o y d - M a x quantizers are used to encode the subimages. Source bits are mapped to channel codes from a family of Trellis Coded Modulation ( T C M ) codes (or a family of Punctured Convolutional Codes ( P C C ) ) , to protect the source bits against the channel errors. B o t h the source encoding and the channel encoding rates are determined subject to a constrained overall channel use per pixel rate, such that the reconstruction quality is maximized, for any given but assumed known channel Signal-to-Noise R a t i o ( S N R ) . T h e m a i n objective of this thesis is the introduction of two adaptive systems A and B . T h e relative importance of the subimages is the determining factor for the bit allocation and the channel code mapping i n system A . W h i l e i n system B , the positioning importance of the source bits to the reconstruction quality is an additional criteria for the o p t i m a l allocation of source bits and the channel code mapping. T h e systems found in [8] and [9] are analogous to our system A i n concept; while the system found i n [10] is analogous to our system B i n concept. T h e system i n [8] uses a rate-distortion analysis similar to ours, however channel errors are not correctly taken into account when computing the contribution to the overall distortion introduced by the D P C M encoded lowest frequency subband. Using a more correct approach has led us to a slightly more complicated but also a more accurate modelling of the lowest frequency subband. Another difference between our system and that of [8] is that we use L l o y d - M a x quantizers instead of uniform quantizers followed by entropy coders. A s shown i n [11] for very noisy channels it is better to avoid entropy coding due to its associated catastrophic error propagation. video coding scheme w i t h .Rate Compatible Punctured In [9] a subband based Convolutional ( R C P C ) codes is Chapter 1. Introduction 4 analyzed. T h e y use a slightly different subband decomposition and vector quantization for the i n d i v i d u a l subbands. In [10] P C M and D P C M encoders are used for the i n d i v i d u a l subbands; however, the bit allocation used there requires an arbitrary weighting factor to take into the fact that errors i n D P C M encoded bits are more severe than errors i n P C M encoded bits, whereas this difference is taken into account by our algorithm automatically. In this work L l o y d - M a x quantization is used as i n our work, however there a B C H code family is employed. Finally, we have performed a channel S N R mismatch sensitivity analysis for Additive White Gaussian Noise ( A W G N ) channel, which is missing i n the above cited works. Therefore, the contributions of this thesis are summarized as follows: • Introduction of a generalized combined bit allocation-channel code mapping algor i t h m which allows the use of multiple channel codes per subimage. • Modification of the above to allow the use of multiple channel codes between subimages, such that no more than one channel code per subimage is permitted. • Study of the performance of the system for two different family of the channel codes. • Investigation of the use of the noise robust one-dimensional ( I D ) and the less noise robust two-dimensional (2D) D P C M source encoders. • Introduction of an improved modelling technique to provide a universal image i n dependent system. • E x a m i n a t i o n of the channel mismatch effect for the proposed systems. T h e outline of this thesis is as follows: Background knowledge of the source encoding systems that are used i n the proposed Chapter 1. Introduction 5 system are introduced i n Chapter 2. Design issues pertaining to the source encoding technique to be used for the individual subbands are studied. Channel coding systems of interest are reviewed i n Chapter 3. T h e encoding and decoding operation is briefly explained and the error correction capabilities of such codes are presented i n terms of the Bit Error Rate ( B E R ) performance. In Chapter 4, two versions of the proposed system are introduced. T h e modelling technique is covered, and a generalized rate distortion analysis is performed. Performance of the proposed systems are compared to those not using U E P . Chapter 5, summarizes the findings, states the conclusions and and suggests some areas related to this work for future research. Chapter 2 Source C o d i n g 2.1 Subband Coding There is a large variety of source coding schemes, each one of them showing advantages for data sources w i t h certain characteristics. For example, as indicated i n [12], a vector quantization scheme is the most effective for a source w i t h a highly clustered nature. A data source w i t h small sample-to-sample differences is best compressed w i t h a differential encoding method, while a source containing random samples w i l l be best compressed w i t h a scalar quantizer. In cases where the source does not show any specific characteristic, it is advantageous to decompose it into sub-components whose statistical properties are such that each component merits its own encoding type. This technique, known as subband coding, is used i n many applications such as speech [13], image [8][10][14][15] and video [9], and is explained i n detail i n the following sections. A general block diagram of the subband coding system is shown i n Figure 2.1. 2.2 Subband Filtering To decompose a data source, it is first passed through a C-band tree structured filter bank, where the frequency band of the sequence is divided into C narrower bands. A n 8-band filter bank is shown i n Figure 2.2. Quadrature mirror filters [16] [17] are used because they have a very sharp cutoff frequency and thus m i n i m i z e aliasing between neighboring bands. These F i n i t e Impulse Response ( F I R ) filters are designed w i t h the 6 Chapter 2. Source Coding Analysis filter 1 1 \ Analysis filter 2 / \ \ Analysis filter 3 / \ Analysis filter M / \ \ \ 7 Encoder 2 I I Encoder 3 ) • Encoder M / \ I Synthesis filter 1 { ) I Synthesis filter 2 Decoder 3 / \ I Synthesis filter 3 Decoder M I ) 1 Synthesis filter M Decoder 1 Encoder 1 ) CD O Decoder 2 \ \ \ Figure 2.1: A subband coding system. sum of \HLP(W)\ 2 + \HHP(W)\ 2 made as near to 1 as possible, for the whole range of frequencies, to be able to reconstruct the signal w i t h the least possible distortion. Note that HLP(W) and HJJP{W) are the frequency responses of the low-pass and the high-pass filter, respectively. Because of the Nyquist theorem which states that only twice as many samples per second as the range of frequencies are needed for signal reconstruction, the output of the filter banks are downsampled by a factor of C . This means every C t h sample is kept and the rest are discarded. This downsampling by a factor of C is denoted by CJ,. To reconstruct the source symbols from the decomposed subbands, they are passed through the same filters which now act as synthesis filters. Subtracting the output of the high pass filter from the output of the corresponding low pass filter, one forms the reconstructed signal at each stage. Chapter 2. Source Coding 8 Low-pass filter Low-pass filter High-pass filter Low-pass filter Low-pass filter High-pass filter High-pass filter Low-pass filter Low-pass filter • High-pass filter High-pass filter Low-pass filter High-pass filter High-pass filter Figure 2.2: A n 8-band filter bank. 2.3 Implementation on Images To perform subband coding on a source w i t h more than one dimension like an image, two dimensional filters are needed to divide the frequency bands of each dimension. B o t h horizontal and vertical frequencies must be divided into smaller bands. In most cases, a product of two one-dimensional filters can be used as a two-dimensional filter. Rows of the image are first filtered and downsampled. A t the next step, columns of the image are passed through filters and downsampled. T h e result is C 2 subimages of size ^ x ^7. Obviously the decomposition process could be continued to obtain smaller subimages. Decomposition of a N x N image into 4 subimages using one dimensional filters is illustrated i n Figure 2.3. There exists an additional requirement i n the design of Chapter 2. Source Original Image Coding 9 (hi) Low-pass filter N/2 X N/2 ». N/2 ^ X N/2 (Ih) NxN High-pass filter (hhj ^_N/2 X N/2 N/2 h x N/2 Figure 2.3: A n image subband encoding system. subband image coding systems: the sum of the number of pixels i n the subimages must be equal to the number of pixels of the original image. This along w i t h the fact that convolution of the spatially l i m i t e d images broaden the region of support of the filtered image, creates a problem for. perfect reconstruction of the edges of subband coded images. There have been a few solutions to this problem proposed, w i t h the two most effective ones being the circular convolution method [14] and the symmetric extension method [18]. For the explanation of these two methods, consider the classical two-band system of Figure 2.4. ho(n) Vo(n) \ 2 y.(n) I ^ V - x'(n) h,(n) v,(n) analysis section • ~%(n) ' synthesis section- Figure 2.4: A simple two band subband coding system. Chapter 2. Source 2.3.1 Coding 10 C i r c u l a r Convolution Method T h e distinguishing feature of the circular convolutional method is that a l l the convolution operations are N-point circular instead of linear. This results i n the outputs of the analysis section to be: y„(n) = v (2n), (2.1) y (n)=v (2n), (2.2) 0 1 1 where, L-l vo(n) = ^2 ho(m)[x(n — m) + x{n -f- N — m)], (2-3) m=0 L-l vi(n) = ^2 hi{m)[x{n — m) + x{n + N — m)], (2.4) m=0 and 0 < n < N. Note that the sequences yo(n) and yi(n) are both of length N / 2 . T h i s method approaches near perfect reconstruction while preventing image size expansion. 2.3.2 S y m m e t r i c Extension M e t h o d This approach also satisfies the length constraint and provides near perfect reconstruction using quadrature mirror filters. For a better explanation of this method, we follow the procedure on the 8-point sample sequence of Figure 2.5(a). T h e high-pass and low-pass filter responses are illustrated i n Figures 2.5(b) and 2.5(c), respectively. T h e finite length sequence x(n) is periodically extended to form a new sequence x(n) as shown i n Figure 2.5(d). {x} = {x ,x 0 {x} = {s_( _i) = L £n, %N u ...,z;v_i} X( -2),X-{L-2) L = (2.5) - X , X(L- ),...,X-i 0 3 X \ , X N - I , = £;V-1, X ^ + 1 = XN-2, £(JV+L-2) = (N-L+l)} X (2-6) Chapter 2. Source 11 Coding Analysis filtering is now performed on the extended sequence x(n) L-l o( ) v n = H h (m)x(n 0 - ra), (2.7) — ra), (2-8) m=0 L - l t>i(n) = ] P hi(m)x(n m=0 and 0 < n < N. T h e final downsampled outputs yo(n) and y i ( n ) , would be the 4-point sequences as shown i n Figures 2.5(e) and 2.5(f). A l t h o u g h both methods show similar • ' 'I I 1 I I IIII I 1 | (> ''I | I | | , | (b) a (c) . . 1 1 1 1 11 11 1 1 i i . . . . 11 11 11 11 111 i • . (d) (e) (f) Figure 2.5: Symmetric extension signals. performance i n the absence of channel coding and noise, the symmetric extension method shows less reconstruction defects on image boundaries when noise is involved [18]. Figure 2.6 exhibits the decomposition of the 512x512 Lena image into 16 subimages, as well as the reconstructed image from the decomposed elements. 2.4 D P C M E n c o d i n g System D P C M is a low complexity lossy compression scheme which takes advantage of the correlation i n the source. Assume a sequence of source samples {x }, from which the difference n sequence is calculated as {d } = {x n n — x _ i } . Once these samples are passed through n the quantizer, they m a y be expressed as {d } — Q{d } = {d + q }, where q is the n n n n n Figure 2.6: Result of subband filtering applied to Lena image, (a) Original image, (b) Lena image decomposed into 16 subimages. (c) Reconstructed Lena image. Chapter 2. Source Coding 13 quantization error. To reconstruct the sample sequence at the receiver, the quantized difference sequence is added to the previous reconstructed values i n a recursive manner to obtain = { £ - i + d }. n Now assuming that the transmitter and the receiver start n w i t h the same value of XQ = xo, the following equation may be derived from a detailed observation of the quantization and reconstruction operations: n X + Y^Qi- = Xn n (2-9) i=l In other words, system suffers from error propagation as the operation continues. To overcome the error propagation problem, the differencing and adding operations are modified at the encoder and the decoder so that they operate on the same piece of information, x . n A t the encoder, the difference sequence is obtained using {d } n x _ i } , and at the decoder, {x } n n = {x„_i + d } n = {x n — is used to reconstruct the samples. In this modified system, we w i l l obtain the following expression for the n t h reconstructed sample: x n = x n + q, (2.10) n where there is no accumulation of errors. Figure 2.7 shows the block diagram of a simple D P C M encoding system. In order to minimize the quantization error, the values of {d } n possible, which may be achieved if x n need to be as small as could be predicted by past values of reconstructed sequence. T h i s gives a motivation to change the block diagram of the D P C M encoding system, to the one i n Figure 2.8. Proper design of the predictor block has a big impact on the performance of the D P C M system, therefore, we w i l l quickly review the design issues i n the following section. Chapter 2. Source ^d n> Coding 14 dn Q r Xn-1 C/n + \ Xn-1 J Xn Delay Decoder Delay Encoder Figure 2.7: A basic differential encoding system. dn predictor Decoder Encoder Figure 2.8: D P C M encoding system. 2.4.1 P r e d i c t i o n in D P C M T h e superior performance of D P C M systems are m a i n l y due to the reduced variance and dynamic range of the difference sequence, which is achieved through the prediction operation. A more accurate predictor design results i n less variances i n the difference sequence. So, the objective here is to design the best prediction function of the form: Pn XQ), (2.11) Chapter 2. Source Coding 15 that minimizes the variance of the difference sequence, <r^, defined as : E[(Zn-Pn) ] <y\ = ^ ^ - ^ 2 (2-12) Note that the selection of the predictor function / ( • ) , w i l l effect crj, which i n t u r n w i l l effect the reconstruction of x sequence, affecting the selection of / ( • ) . T h i s problem n known as the coupling problem makes it very difficult to find an explicit solution for the predictor function, unless it is assumed that the quantizer steps are small enough to be able to ignore any differences between x and x . This is called the n assumption, n fine quantization and changes the definition of the predictor to: Pn = f(x -l, X -2, n X ). n (2.13) 0 To further simplify the task of finding the best predictor function, it m a y be assumed that / ( • ) is a linear function of the form: K Pn = Y2aiX -.i, i=l (2-14) n where, K is the order of the predictor. So, (2.12) may be re-written as: K al = E[{x -Y.^n- ) ]. (2.15) 2 n l i=l To m i n i m i z e a\, derivatives of (2.15) are taken w i t h respect to each of the a; and are set equal to zero. A l l the prediction coefficients {a } may be obtained by solving the 8 following K equations: K Y2, iRxx{i i=l a where, R (j) xx = E[x x j] n n+ - j) = Rxx(j), j = 1,2,K, (2.16) is the autocorrelation function of x . G i v e n A^ data points, 2 n the following gives a fairly good approximation for the autocorrelation function: I Rxx(j) = N -j 2 _ • Yl i i+j3 i=l x N 2 x (2-17) Chapter 2. Source Coding 16 D P C M encoders that use the prediction coefficients as i n (2.16), demonstrate excellent reconstruction quality for noiseless conditions. However, i n presence of noise, the performance of the system deteriorates due to the channel transmission errors. A study of the performance of the D P C M systems i n presence of noise, has found an approximately o p t i m a l solution for the prediction coefficient of a first order system [19]. A p p l i c a t i o n of the results of [19], separately to each dimension, results i n : i=l,2, (2.18) Pi for two-dimensional (2D) t h i r d order prediction, where the horizontal and vertical prediction coefficients, a\ and a , are given by the normalized horizontal, pi, and vertical, 2 P2-, normalized autocorrelation coefficients, respectively. T h e prediction function for 2DD P C M contains both elements of the horizontal and vertical dimensions: Pn = a\Xi,j-i For one-dimensional ( l D ) - D P C M , + a Xi- j a 2 2 lt - axa Xi- ,3-\2 X (2.19) is set equal to zero, and the prediction function contains only one element, where p\ — R (l)/R (0), xx function for the horizontal dimension, xx is the normalized autocorrelation a;.is typically smaller than pi, producing an attenuation effect which diminishes the error propagation of D P C M i n noisy channels. 2.5 Quantization Quantization i n general is a way of representing a large amount of data by a much smaller amount of data, w i t h a tolerable loss i n quality. It is clear that quantizers fall into category of lossy compression schemes. A t the encoder, the source symbols are divided into a fixed number of intervals, each associated w i t h one quantizer level, which i n turn is associated w i t h one codeword. U p o n reception at the decoder, a codeword is mapped to the corresponding quantizer level, as Chapter 2. Source Coding 17 the reconstructed symbol. The number of the intervals and the size of the intervals, as well as the mapping of the quantizer levels to the codewords, play a major role i n the performance of the quantizers; i n terms of the amount of the compression obtained and the distortion incurred. T h e difference between the reconstructed and the original symbol is an indication of the quantization error, and is called the quantization quantization 2.5.1 noise or distortion. U n i f o r m Quantizer Uniform quantizers are the simplest i n the class of scalar quantizers. A l l the decision intervals are spaced evenly, except for the two outer regions. A n bit quantizer would have 2™ intervals, where the spacing of the reconstruction levels, known as the step size ( A ) , is equal to A = |pr. T h i s quantizer is optimal for a data source which has uniformly distributed output symbols between [—X, X]. Note that for the case of a nonuniform source, the average quantization error per symbol for a l l the intervals i n uniform quantizers is fixed, which results i n a high total quantization error i n more populated intervals. A non-uniform quantizer would be a better choice for such data source. 2.5.2 Non-Uniform Quantizer It is clear that the size of quantization intervals has a direct relationship to quantization error. Therefore it is advantageous to reduce the quantization interval i n areas where the source output is most populated; thus achieving a lower total quantization error. Consider a q bit (i.e.: T level) quantizer, where q = l o g T . Let the decision boundaries 2 and the reconstruction levels be denoted by {bi}J =0 and {li}J , =1 respectively. T h e n the quantization operation may be expressed by the following function: Q(x) = li iff bi-iKx^bi. (2.20) Chapter 2. Source Coding 18 T h e mean squared quantization error, is defined as T bi J = E [' (x-h) Px(x)dx, i=i '-i r CT 2 (2.21) Jb where Px(x) is the pdf of the source symbols x. a is minimized by setting the derivative 2 of (2.21) w i t h respect to lj, equal to zero and solving for lj : lb , Jb^ 3 = xPx(x)dx — (2.22) si;. Px(x)dx 1 Taking the derivative w i t h respect to bj and setting it equal to zero, we get an expression for the reconstruction values: hi = ^ y ^ " (2-23) These two equations need to be solved simultaneously to get the design parameters of the non-uniform quantizer. They can be solved by an iterative procedure known as the L l o y d - M a x algorithm [20]. 2.6 Bit Allocation Once the type of the source encoding is determined for each component of a subband decomposition, the next task, is to allocate the bits between the subbands according to their level of importance. T h e variance at the output of each downsampler is used as a measure of importance for that subband. Proper allocation of the bits between subbands has a large impact on the signal reconstruction quality at the receiver, specially i n cases where the variances of subbands are very different. A s an example, if the average number of bits per sample to be used by the system is 1 bit/sample, after decomposition of the original data to four subbands, one bit may be allocated to each sample of each of the subbands. Another possibility is to allocate four bits to the samples of the most important subband, and to discard the rest of the subbands. Chapter 2. Source Coding 19 T h e following is a simple bit allocation algorithm w i t h very low implementation complexity and reasonably good results for noiseless environment [12]: Assuming: o\: variance at the output of the A;th downsampler, M: total number of subbands, r' : bits per sample allocated to the kth subband, k R\,: rate counter, and R'\ average design rate (bit per sample) to be used by the subband coding system, 1.Compare o~\ at the output of each downsampler. 2.Set r' = 0, for all k = 1,2,...,M. k 3.Set Rb = MR', as the total number of bits available for distribution. 4.Sort the variances {cr .}, suppose of is the largest. 2 5.Increment r\ by one, and divide of by 2. 6.Decrement i?& by one. If it equals zero, stop. Otherwise go to step 4. In this simple allocation method, it is assumed that all the subbands are using the same type of quantizer, and that the data of a l l the subbands have similar characteristics. In other words, the rate-distortion functions for a l l the quantizers of a l l the subbands are assumed to have the same form. Huang [21] and Segall [22] developed other algorithms based on this assumption. Obviously this assumption would not hold i n many practical cases. E v e n i f identical quantizers are used, the rate-distortion performances at the output of the subbands would be different, since the subbands do not have the same statistics. This assumption, however, was later relaxed i n the development of the more practical bit allocation schemes, like i n [23]. In fact, the rate-distortion curves i n the presence of channel coding and noise might actually behave quite irregularly. Hence, there is a need for a stronger bit allocation algorithm to take into account the effect of the quantizer functions, even those which have irregular behavior. T h e other l i m i t of this Chapter 2. Source Coding 20 simple noiseless allocation scheme is the fact that it can only deal w i t h integer values, which sets a major drawback for many practical applications. One major requirement for most of the allocation algorithms has been the convexity of the rate-distortion function, which is not realizable i n some practical situations. Gersho and Shoham introduced an efficient bit allocation scheme [24] that handles positive noninteger rates and efficiently finds an o p t i m u m solution for the allocation problem for any arbitrary set of quantizers, that do not necessarily have convex rate-distortion functions. T h e problem may be formulated as follows. Assuming M different quantizers for M subbands, we want to minimize the total distortion M 0 = 5>?A(rj), (2.24) i=l subject to the rate constraint -i R M ' = M ^ i=i (2-25) 1V1 where, af is the variance of the zth subband, r\ is the rate allocated to the zth subband, and Di{r'^) is the quantization function for the ith. subband: N /M 2 E (j x E ~ i) x x) 3=1 where the quantizer inputs and the the quantizer outputs. It is mathemat- ically proved i n [24] that this constrained problem is transformable to the unconstrained m i n i m i z a t i o n problem of m i n i m i z i n g {D (i) k + Xi} fc = l,2,...,M, (2.27) where, i 6 Sk and Sk = {PkiQk} defines the valid range of allocatable bits for the kth. subimage. For a given A, assuming that there is only one solution, Ufc(A), for each subband which minimizes (2.27), then the sum of all the UkS is called the solution rate R'(X). Due Chapter 2. Source Coding 21 to irregularities i n the rate-distortion functions, the solution •Ufc(A) may not be unique, meaning that there may be more than one solution rate for a given A. Such a value of A is defined as singular. T h e objective is to find the solution rate equal to or closest from the bottom to the design rate. T h e collection of u^s corresponding to this solution rate is the solution to the allocation problem. To find them, the authors of [24] proposed the following algorithm: • Step 1. M Set an i n i t i a l value for A to be tj ^ {Dk(lk) — DkUk + -1)}, fe=i where, Ik is the nearest integer to [(pk + Ofc)/2] • Step 2. Solve (2.27) for a l l k and obtain fl'(Ai). • Step 3. If R'(Xi) is greater than R', set A3 = Xi and Uk(\ ) = fi^(A ) for a l l k. T h e n add a 3 1 predetermined constant to A l . G o to step 2. • Step 4. If R'(Xi) is smaller than R', subtract a predetermined constant from A l . G o to step 2. • Step 5. Repeat the last two steps u n t i l A i and A are found so that: 3 iE'(Ai) <R' < i ? ' ( A ) . 3 (2.28) So the search region has reduced to the interval [A3, Ai], where the search continues as i n steps 6 to 8. Chapter 2. Source Coding 22 • Step 6. Start from A3 and solve (2.27) w i t h a new Sk = {i : itfc(Ai) < i < u (X )}, k k = 1,2,...,M. 3 (2.29) If there is more than one solution, find the two solutions w i t h the smallest ^ ( ^ 3 ) and greatest i?'^(A ) constraints. However, i f there is only one solution, there w i l l 3 be only one constraint R'(X ) associated w i t h that solution. 3 • Step 7. If there is only one solution and i f R' = R'(X ), 3 an o p t i m a l solution is found, stop the search. • Step 8. If there is more than one solution and i f R\(X ) 3 < R' < R' (X ), h 3 a l l the solutions are obtained, and the one resulting i n a constraint closest to R' from below is the answer. Stop the search. • Step 9. If R' < R'(X ) 3 or both R'i(X ) and R' (X ) 3 h are larger than R', find the next smaller 3 singular value of A using : 3 mm mm D {i) k D (u (X )) k k 3 (2.30) where, S k = {pk,---,u (X ) k 3 and - 1} M~ = {k : k G { 1 , 2 , . . . M};u (X ) k G o to step 6 3 > 1} (2.31) (2.32) Chapter 2. Source Coding 23 • Step 10. If R' > i ? ' ( A ) , or both -R{(A ) and R' (X ) 3 3 h 5 are smaller than R', the algorithm is not able to find the o p t i m a l solution. W h a t we have is an approximate solution which may be adjusted to the actual R' or the closest possible rate, according to the next step. • Step 11. T h e idea is to increment the rate to the next higher possible value for the subband which provides the greatest reduction i n the reconstruction noise, one increment at a time, as long as the solution rate remains less or equal to R'. F i n d k' that solves m i n {D (u (keM-) k k + 1) - D (u )}, k k (2.33) and increase u >, unless it causes the solution rate to exceed R'. Repeat this step k u n t i l the best accessible solution rate is reached. Chapter 2. Source Coding 24 Table 2.1: Statistical properties of 16 subbands of Lena image (512x512). Image Variance Mean Autocorrelation coefficient Original image Subband # 1 (LFS) Subband # 2 Subband # 3 Subband # 4 Subband # 5 Subband # 6 Subband # 7 Subband # 8 Subband # 9 Subband # 10 Subband # 11 Subband # 12 Subband # 13 Subband # 14 Subband # 15 Subband # 16 Mean-subtracted L F S (MSLFS) 2.7 2296.02 2171.07 34.63 12.72 0.818 8.052 2.081 10.64 0.939 0.577 4.424 1.925 0.381 2.856 0.498 0.577 1.137 2171.07 122.0 123.70 -0.0019 -0.0134 0.0082 0.0155 0.0018 -0.1720 0.0069 0.0062 -0.1301 0.0265 0.0037 -0.0031 0.0026 0.0045 -0.0089 0.0000 0.995686 0.982834 -0.135275 -0.084897 0.099171 -0.274875 -0.004561 0.017112 -0.187677 -0.021266 0.517267 -0.063782 -0.026506 0.216615 0.071791 -0.077262 0.191592 0.867495 Simulation Results To evaluate the performance of the subband image coding scheme, we have implemented a subband encoding scheme for a noiseless environment. T h e 8-tap quadrature mirror filters of [16] are used as separable filters for a decomposition of the image into 16 subbands, where the pixel values of the Lowest Frequency Subimage ( L F S ) are mean subtracted. T h e noiseless bit allocation algorithm described i n the previous section is used for dist r i b u t i o n of the total quota of available bits into subimages. T h e statistics of two test images are presented i n Tables 2.1 and 2.2 for review. Because the autocorrelation coefficients for the M e a n Subtracted L F S ( M S L F S ) values i n the Tables 2.1 and 2.2 show a significant sample-to-sample correlation, while those Chapter 2. Source Coding 25 Table 2.2: Statistical properties of 16 subbands of Couple image (512x512). Image Variance Mean Autocorrelation coefficient Original image Subband 1 (LFS) Subband 2 Subband 3 Subband 4 Subband 5 Subband 6 Subband 7 Subband 8 Subband 9 Subband 10 Subband 11 Subband 12 Subband 13 Subband 14 Subband 15 Subband 16 Mean-subtracted L F S (MSLFS) # # # # # # # # # # # # # # # # 1967.37 1758.67 57.33 47.60 5.558 7.252 5.850 24.77 1.410 1.645 20.94 3.237 0.521 3.509 0.956 0.775 1.626 1758.67 121.90 120.41 0.0106 0.0300 0.0383 -0.0001 -0.0522 -0.1527 0.0057 -0.0049 -0.1891 -0.0061 0.0028 0.0127 0.0113 -0.0081 0.0083 0.0000 0.993606 0.985705 -0.117475. 0.539605 0.288368 -0.215934 -0.013744 0.054462 -0.120824 -0.193377 0.568118 -0.236178 -0.090547 0.188940 0.152371 -0.066752 0.135276 0.869286 of the other subimages do not, we use D P C M to encode the M S L F S and use P C M to encode the other subimages. A t the decoding side each subband is decoded according to its corresponding encoder. T h e mean value of the L F S is added to the received symbols of the first subimage before passing the subimages through the synthesizer filters for image reconstruction. Subjective and objective measures may be used to evaluate the performance of the i m age transmission systems. We have used the Peak Signal-to-Noise R a t i o ( P S N R ) defined as E(255) P S N R = 10 l o g " 1 0 2 (2.34) hi as the objective measure of the performance, where x,j and x,-j denote the original and Chapter 2. 0 Source Coding 0.1 0.2 26 0.3 0.4 0.5 0.6 Overall Bit Rate (bpp) 0.7 0.8 0.9 Figure 2.9: Performance of subband coding scheme for varying bit rate i n noiseless environment. the reconstructed pixel value, respectively. Indices i and j indicate the corresponding row and column indices of a pixel. It is evident from Figure 2.9 that for bit rates higher than 0.5 bit per pixel, this system allows for near perfect reconstruction of the image i n noiseless environment. T h e reconstructed Lena image for several bit rates is displayed i n Figure 2.10 to provide a means of subjective comparison. Chapter 2. Source Coding 27 Figure 2.10: Near perfect reconstruction in noiseless environment, (a) Original Lena image, (b) Reconstructed image using 0.5 bpp. (c) Reconstructed image using 0.75 bpp. (d) Reconstructed image using 1.0 bpp. Chapter 3 Channel 3.1 Coding Trellis C o d e d M o d u l a t i o n It is known that forward error correction increases the performance of a digital communication system at the price of bandwidth expansion. That is why F E C techniques are not appreciated as much for bandlimited channels. B a n d w i d t h efficient modulation techniques are i n common use for such systems to achieve high bandwidth efficiency. Ungerboeck [25] showed that it is possible to combine convolutional coding w i t h a bandw i d t h efficient signaling scheme to achieve significant coding gains for the b a n d l i m i t e d channel. T h e key to this combination scheme is to use an expanded signal set which provides some extra room to be filled by the redundant code bits, at the price of reducing the Euclidean Distance ( E D ) between signals i n the constellation pattern, which i n t u r n increases the error rate. T h i s technique is called Trellis Coded M o d u l a t i o n , and of course, in order to design a good T C M scheme, the performance gained from the coding must overcome the performance lost from the signal expansion. It was shown that almost all the gain that may possibly be attained through signal expansion is reached by doubling the signal space. To translate this into T C M terminology, a n / ( n +1) rate code is needed to use the extra room created by doubling the signal space. Figure 3.1 shows the general block diagram for a trellis encoder w i t h a mapper. T h e mapping process used i n this technique is called set partitioning on successive partitioning of the expanded 2 28 n + 1 and is based signal set into subsets w i t h increasing Chapter 3. Channel Coding 29 n parallel bits (n+1) parallel bits Channel symbol C1C2- Cn- Rate n/(n+1) Convolutional Encoder MPSK Mapper/Modulator Figure 3.1: E n coder/modulator for trellis coded modulator. m i n i m u m Euclidean distances. A n example of the set partitioning for the 8 P S K signal set is shown i n Figure 3.2. To design a T C M code over a given signal configuration (i.e.: M P S K , A S K , ...), the first step is to define a trellis structure according to the desired constraint length. Signals from an expanded signal set are then assigned to the branches of the trellis, in a way which maximizes the free Euclidean distance of the code. A search for the best assignment is performed by computer, especially for codes w i t h high constraint lengths. Unfortunately, this method results i n different encoder/decoder designs for different signal configurations, simply because o p t i m u m T C M codes w i t h different rates have different code structures. Therefore Ungerboecks's family of T C M codes are not attractive for use i n any adaptive system. A more practical approach to use is what are known as pragmatic 3.2 trellis codes. P r a g m a t i c Trellis Codes T h e introduction of puncturing, allows the construction of any rate n / ( n +1) code from a basic rate 1/2 convolutional code, w i t h a performance fairly close to that of an o p t i m u m code. V i t e r b i [26] presented a pragmatic approach to trellis coded modulation based on this idea. Using a rate 1/2 convolutional encoder as the mother code, higher rate codes could be easily built and mapped into signals of the constellation pattern. T h i s allows Chapter 3. (000) Channel (100) Coding (010) 30 (110) (001) (101) (011) (111) Figure 3.2: Set partitioning of the 8 P S K signal set. the realization of T C M codes w i t h different rates, based on the same mother code and its associated trellis structure. Therefore it makes T C M codes more attractive for adaptive systems by reducing the implementation complexity and cost. T h e pragmatic encoder for the optimized convolutional code of constraint length K 1 c = 3, and the corresponding trellis diagrams are displayed i n Figure 3.3. O n l y one bit out of the n input bits is fed into the encoder, and the rest of the input bits are simply passed through uncoded. T h e number of uncoded bits determine the rate of the code as well as the number of parallel branches i n the trellis of the code. In fact, there are 2™ n/(n _1 parallel branches connecting two states i n the trellis diagram of a + 1) T C M P S K pragmatic trellis code. To perform the mapping according to the The definition of the constraint length is the total number of memory elements in the encoder plus one. 1 Chapter 3. Channel Coding (c)8PSK 31 (d)16PSK Figure 3.3: A pragmatic encoder and its corresponding trellis diagrams (K c = 3). scheme proposed by V i t e r b i [26], the two bits which are the outputs of the rate 1/2 encoder, pick one of the four signals according to Gray code, which guarantees that a l l neighboring signals of a particular sector differ i n only one bit. T h i s has a major effect i n error performance of the code, since most of the errors happen i n the neighboring signals. T h e remaining (n — 1) bits are then used to choose sectors i n an order according to the decimal equivalent of their binary vectors. This scheme which is referred to as sectorized gray coded mapping by A l a m o u t i [27], is shown i n Figure 3.4(a). It was further suggested by A l a m o u t i [27], that the (n — 1) uncoded bits at the output of the pragmatic encoder be used to sefect a sector according to gray code. This new mapping approach which is illustrated i n Figure 3.4(b), is called double gray coded mapping, and causes the signals mapped to parallel branches of the neighboring sectors Chapter 3. Channel 01OQ Coding 32 -0010 *^«P011 .0010 01 oa ,0001 0111 011 kOOOO 1000 1010 1011 1001 1010 1100 1000 1110 (b) (a) Figure 3.4: M a p p i n g schemes for pragmatic T C 1 6 P S K . (a) T h e scheme used i n [26]. (b) The scheme introduced i n [27]. to differ i n only one bit, improving the error performance even more. Note that both mapping schemes are identical for constellations w i t h less than 16 signals. 3.3 D e c o d i n g T C M Codes Like for convolutional codes, each sequence of transmitted T C M encoded bits is represented by a path i n the trellis representation of that code. T h e task of the T C M decoder, based on the m a x i m u m likelihood criteria, is to examine the received sequence and to choose the most likely transmitted sequence based on this examination. Assume S = (si, 5 , s i ) 2 is the sequence of transmitted signals and Z = (zi, z , z \ ) is the 2 sequence of received signals from the A W G N channel. We can express the relationship between the transmitted and the received sequence as: Z% — i + i s n f° r 1 ^ i ^ l-i (3.1) Chapter 3. Channel Coding 33 where n - is a sample of the A W G N . These noise samples can be modeled by the Gaussian 2 distribution N(0, No/2), where ^ 0 / 2 is the power spectral density of the white Gaussian noise. The likelihood function of the received sequence, given the transmitted sequence, may be expressed as: P{Z I S) = I I - 7 ^ - ^ = (-^r)' / 2 ex (-^ £ P I zi ~ * | ) . 2 (3.2) Therefore, we conclude that the m a x i m u m likelihood decoding may be done by m i n i m i z ing the Euclidean distance between the received sequence of channel symbols and the transmitted channel sequence: r ED(Z,S)= ( £ \ I 1 / 2 " * lJ (3.3) 2 Thus the Euclidean distance is used as the metric i n decoding such systems using V i t e r b i algorithm [28]. Moreover, the decoding and demodulation are performed simultaneously on the soft output symbols of the channel to avoid the unrecoverable loss of hard-decision demodulation prior to decoding [29]. Decoding T C M codes containing parallel branches should be performed i n two steps: 1. A branch w i t h the m i n i m u m E D from the received signal, is selected from the parallel branches merging to each state. The branch label, which is the decoded bits associated w i t h the surviving branch, and its metric are stored as the winning branch and winning metric. 2. T h e code trellis is searched for the most likely transmitted path using the V i t e r b i algorithm considering only the winning branches. Note that once the parallel branches are replaced w i t h the winning branches, the result is a normal trellis structure which the soft input V i t e r b i algorithm can easily be applied to. Chapter 3. 3.4 Channel Coding 34 Performance Results In this section we report simulation results to evaluate the performances of the T C M codes that are used i n our subband coding system: 1. Rate 1/2 T C Q P S K 2. Rate 2/3 T C 8 P S K 3. Rate 3/4 T C 1 6 P S K The trellis diagram, signal space and the B E R performance of each of these three codes are shown i n Figures 3.5, 3.6 and 3.7. T h e o p t i m u m rate 1/2 convolutional encoder of Figure 3.3(a) is used as the mother code of all these codes. T h e difference i n the trellis diagrams of these codes are the number of parallel branches, and thus a slightly modified V i t e r b i algorithm is used to perform the decoding as explained i n the previous section. Chapter 3. Channel Coding 35 Figure 3.6: (a) Signal space, (b) trellis diagram and (c) B E R performance of pragmatic rate 2/3 T C 8 P S K . Chapter 3. Channel Coding 37 Figure 3.7: (a) Signal space, (b) trellis diagram and (c) B E R performance of pragmatic rate 3/4 T C 1 6 P S K . Chapter 3. 3.5 Channel Coding 38 P u n c t u r e d Convolutional Codes Simple implementation of a variable rate error control system based on a single mother code is only one of the reasons that has made the Punctured Convolutional Codes ( P C C ) so attractive. C a i n [30] was the first to show that puncturing of convolutional codes simplifies the V i t e r b i decoding for high rate convolutional codes. It was shown that a 2 V i t e r b i decoder may be used for a rate k/n punctured convolutional code w i t h only two branches arriving at each node i n the trellis [31], as opposed to the 2 branches of standard k convolutional codes [32]. T h e puncturing operation is performed on a mother code which has the lowest rate i n the code family, according to a m a t r i x called the perforation For a mother code of rate l/Rp, the perforation m a t r i x has R p rows and C p matrix. columns. C which is called the perforation period, depends on the final desired code rate. Larger p values of C are needed to construct higher rate P C codes. Elements of the perforation p m a t r i x are zeros and ones, where a zero indicates that the corresponding output must be deleted from the mother code, and a one indicates that the bit associated w i t h that .position must remain untouched. Needless to say, not every perforation m a t r i x produce a g o o d non-catastrophic code. Various authors have reported several algorithms i n the 3 4 search for good P C codes [31][33][34]. For example, starting from a rate 1/2 mother code w i t h constraint length 3, the perforation m a t r i x of a rate 2/3 punctured code is given by ' l 1^ l 0; [Pi V (3.4) Their study was carried out only for rate 2/3 and 3/4 punctured convolutional codes which were shown to be as good as the best known codes with those) rates. The criteria for a good code is a high value for the minimum free distance of the code and a low value for the total number of bit errors produced by all incorrect paths with distances larger than df . This results in a low B E R performance of the code [33]. Catastrophic codes may translate a small number of errors in the received codeword to an unlimited number of data errors. 2 3 ree 4 Chapter 3. Channel Coding 39 whereas a rate 6/7 code can be obtained using the perforation m a t r i x ( 1 V 1 0 1 0 0 0 0 ^ (3.5) 1 1 1 1 T h e block diagram of a P C C encoder is displayed i n Figure 3.8. information bits Rate 1/Rp Convolutional Encoder Punctured encoded bits 1 « Puncturer Figure 3.8: P C C encoding and puncturing operation. 3.6 D e c o d i n g P C Codes A n slightly modified soft input V i t e r b i algorithm can easily be implemented to decode P C codes. T h e decoding is performed w i t h the trellis of the low-rate mother code. Like the case for the T C M codes, demodulation and the decoding are done together to save the information which is usually lost by making hard decisions. T h e only modification needed is to not account for the punctured bits i n the computation of the branch m e t r i c . T h i s is 5 easily accomplished by inserting d u m m y symbols into the puncturing positions according to the perforation m a t r i x of the code. In the decoding process the same metric value is 6 assigned to these d u m m y symbols. This procedure greatly reduces the complexity of the conventional path metric computation for the punctured convolutional code. Another modification of the mother code decoder that needs to be done to decode the codes of the P C C family, is that the truncation path length must be increased w i t h the code 5 6 The same branch metric is used as the branch metric of the T C M codes for AWGN channel Usually this value is chosen as zero. Chapter 3. Channel Coding 40 rate [33]. T h e differences between the conventional trellis and the one used for modified V i t e r b i decoding based on the mother code (rate = 1/2) is demonstrated i n Figure 3.9, where X denotes a punctured bit position. Q P S K modulation is used i n conjunction w i t h the P C codes, where the code mapping is shown i n Figure 3.10 3.7 Performance Results Computer simulations were performed to evaluate performances of the P C codes that are used i n our subband coding system: Chapter 3. Channel Coding 41 Figure 3.10: Q P S K signal constellation. 1. Rate 3/4 P C C 2. Rate 4/5 P C C 3. Rate 5/6 P C C T h e perforation m a t r i x , modified trellis diagram and the B E R performance curve of each of these three codes are shown i n Figures 3.11, 3.12 and 3.13. T h e o p t i m u m rate 1/2 convolutional encoder of Figure 3.3(a) is used as the mother code for a l l these codes. T h e differences i n the trellis diagrams of these codes are simply i n the pattern of the punctured bit positions. Chapter 3. Channel Coding 42 Figure 3.11: (a) Modified trellis diagram, (b) perforation m a t r i x and (c) B E R performance of rate 3/4 P C C . Chapter 3. Channel Coding 43 Figure 3.12: (a) Modified trellis diagram, (b) perforation m a t r i x and (c) B E R performance of rate 4/5 P C C . Chapter 3. Channel Coding 44 Figure 3.13: (a) Modified trellis diagram, (b) perforation m a t r i x and (c) B E R performance of rate 5/6 P C C . Chapter 4 Joint Source-Channel C o d i n g Consider an image source that is decomposed i n to 16 subbands, and a series of channel codes available w i t h varying rates and performances. To design a subband image coding system subject to a fixed channel symbol rate per pixel, one could choose the lowest rate (i.e.: strongest) channel code and find the source coding rate accordingly. Obviously this system which has a lot of protection against channel errors, performs quite well i n a channel w i t h low signal-to-noise ratio. However, to design a system which operates i n higher channel S N R , a smaller portion of the available channel rate could be allocated for protection against channel errors. T h e amount of channel rate saved could very well be added to the source encoding rate to reduce the distortion caused by lossy source encoding. A n adaptive joint source-channel design minimizes the overall reconstruction error for any given channel condition, and thus has varying parameters based on the channel condition. Based on these observations, we have proposed and studied the following two systems: System A: T h e objective is to find the best possible bit distribution for each subband and to choose the best code from the family of channel codes w i t h the constraint that only one channel code is permitted per subband; subject to overall constraint rate of R (channel use/pixel). System B: T h i s system works similarly to system A , w i t h the difference being that the use of multiple channel codes is allowed w i t h i n every single subband. 45 Chapter 4. Joint Source-Channel Coding 46 System A takes advantage of only the difference i n importance levels of the subbands; whereas system B also takes advantage of the positioning importance of bits w i t h i n pixels of each subband. M a n y source coders, including P C M and D P C M , produce codewords in which bits that are more important to reconstruction quality also occupy the more significant bit positions of the codeword. A s i n Chapter 2, we encode the L F S using D P C M , and encode the other subbands using P C M . It is imperative that the design of a joint source-channel coding system such as ours not be image dependent. Various codec parameters w i l l be image dependent, and i n order that the codec be able to determine these parameters for an arbitrary image, we w i l l model all images i n such a way that any particular image w i l l be fully characterized by only a few parameters. These parameters w i l l be measured by the coder and transmitted to the decoder as side information. 4.1 Subband Image M o d e l l i n g In order to design a universal system, the statistical properties of the subimages of the subband coder are studied to find the best possible mathematical model from which to b u i l d the system upon. We have found the statistics of a l l the subimages other than the L F S , to be sufficiently similar to allow a single model for a l l of them. T h e histograms of all the subimages except the L F S , as well as the histograms of the Differentially-En coded Mean-Subtracted L F S ( D E M S L F S ) are plotted i n Figure 4.1 for several 512x512 standard monochrome images. We w i l l model the D E M S L F S and the other subimages w i t h the Generalized Gaussian Distribution ( G G D ) . T h e probability density function of the G G D is given by [35]: p(x) = ^ ^ ^ e x p i - r j i a , ^ } ; 2r(l/a) (4.1) where T/(a,^) = /3- 1 r(3/«) r(l/a). 1 1 / 2 (4.2) Chapter 4. Joint Source-Channel (e) Coding 47 (f) Figure 4.1: Histograms of: (a) D E M S L F S of Lena image, (b) other subbands of L e n a i m age, (c) D E M S L F S of Couple image, (d) other subbands of Couple image, (e) D E M S L F S of M a n d image and (f) other subbands of M a n d image. Chapter 4. Joint Source-Channel 3r 1 Coding 1 1 48 1 1 1 r 2.5 h Figure 4.2: P r o b a b i l i t y density function of generalized Gaussian distribution w i t h selected parameter values. a > 0, which is called the shaping factor is an indication of exponential decay rate, j3 is the standard deviation of the distribution, and F is the standard g a m m a function. T y p i c a l behavior of the unit variance (/? = 1) G G D pdf w i t h a few different values of the shaping factor is shown i n Figure 4.2. Note that a G G D w i t h a = 1 is a distribution, and that w i t h a = 2, is a Normal Laplacian distribution. T h e Kolmogorov-Smirnov ( K S ) test [36] is used as a measure of distance between the variance-normalized empirical distribution and the probability distribution of the G G D w i t h (3 — 1. For a given set of data samples X = (xi, X2,£jv), the Kolmogorov-Smirnov test measures the distance between the C u m u l a t i v e Distribution Function ( C D F ) of the samples Fx(xi) and a known Chapter 4. Joint Source-Channel Coding 49 Table 4.1: Results of the Kolmogorov-Smirnov test for a few test images. Best value of a for Image Size other subbands DEMSLFS Lena 512 x 512 1.45 0.75 Couple 512 x 512 1.50 0.75 Mand 512 x 512 1.95 0.80 Peppers 512 x 512 2.00 0.75 G r a n d m a 512 x 512 1.90 0.65 Bridge 256 x 256 1.95 0.95 Einstein 256 x 256 1.05 0.65 crowd 256 x 256 2.10 0.50 Tank 256 x 256 1.75 0.80 Kodak 256 x 256 1.60 0.80 Average 1.70 0.75 distribution function F(-). T h e K S test statistic, d ks d = max\F (xi)-F(xi)\, ka x , is defined by i = 1,2,N. (4.3) O f a set of distribution models, the closest to a given empirical distribution is the one that results i n the smallest d . ks We have considered the unit variance generalized Gaussian distributions w i t h a ranging from 0.3 to 2.5 i n steps of 0.05, and compared t h e m against a series of five images of size 512x512 and five images of size 256x256. E m p l o y i n g the K S distance test, we have found the best value of a for the D E M S L F S , as well as the best value of a for the other subimages, to be those listed i n Table 4.1. A first order one dimensional linear predictor w i t h Chang-Donaldson renormalization is used for the differential encoding operation. It is reasonable to choose the averaged a from the table and declare a = 1.70, to be a good approximation for the shape factor of the G G D for the D E M S L F S . Likewise, a = 0.75 is found to be the best shaping factor for modelling the other subimages. Chapter 4. Joint Source-Channel Coding 50 A model found i n this way is more precise than the Laplacian model which was used i n early subband image coding systems [14] [15]. However, the final values of a are somewhat different than the ones reported i n [8] [37], because these values depend on: • filters used for the subband decomposition, • modelling technique for the L F S , and • predictor design of the D P C M encoder. Once the model is defined, a series of G G D - b a s e d synthetically generated random samples w i l l be used as the pixel values of a l l the subimages except the L F S . For the L F S , the inverse of the differential encoding operation is performed on a l l the synthetically generated samples that represent the D E M S L F S . T h e average of the prediction coefficient for the M S L F S pixels are computed from the ten sample monochrome images listed i n Table 4.1, and is used for the inverse differential encoding operation on the synthetically generated samples. It is now timely to explain why the proposed system works on the mean-subtracted symbols. F r o m the calculation of the prediction coefficient i n Chapter 2, it is easy to see that the prediction coefficient of a sequence of pixels changes as the mean is shifted, while it remains unchanged as the variance is varied. T h e inverse of the differential operation on the unit-variance zero-mean samples results i n zero-mean samples w i t h a variance not equal to one. T h e differentially decoded synthetically generated pixels can be variance normalized without any change i n the interpixel correlation characteristics. These new synthetically generated pixels are then stored and used as the model for M S L F S . T h e synthetically generated samples representing the zero-mean, unit-variance subimages form the data sets upon which we design our system. T h e syst e m parameters for actual transmission of a particular image w i l l be determined by the mean and variance of the L F S and the variances of the other subimages of the subband decomposition. Chapter 4. Joint Source-Channel Coding 51 Table 4.2: I D prediction coefficients for the test images. Image Lena Couple Mand Peppers Grandma Bridge Einstein Crowd Tank Kodak Average 4.2 Size 512 512 512 512 512 256 256 256 256 256 x x x x x x x x x x One dimensional prediction coefficient 512 512 512 512 512 256 256 256 256 256 0.579316 0.581730 0.519225 0.634847 0.738692 0.589222 0.489050 0.429054 0.686670 0.601806 0.585 B i t A l l o c a t i o n and C o d e M a p p i n g To determine the o p t i m a l allocation of bits between the source coding and the channel coding of a l l the subimages, we need variance normalized rate-distortion ( R D ) curves. T h e rate of the R D curve for a subimage w i l l be the total rate after source and channel coding and modulation. W h i l e the distortion is the total distortion incurred by the lossy source coding plus that due to uncorrected channel errors. We employ the following channel codes from the family of trellis coded modulation schemes reviewed i n Chapter 3: • T C Q P S K , which produces a channel symbol for every bit, • T C 8 P S K , which produces a channel symbol for every 2 bits, and • T C 1 6 P S K , which produces a channel symbol for every 3 bits. We define the average number of channel uses required to transmit one pixel of the image to be the system constraint; call it the channel rate and denote it as R . O u r goal is to find \ Chapter 4. Joint Source-Channel Coding 52 the o p t i m u m number of bits to be allocated for encoding each subimage, and at the same time assign the best channel code for the source encoded bits, to achieve the m i n i m u m distortion after decoding at the receiver, subject to a fixed design channel rate. Hence, the task of bit allocation and channel code mapping must be performed simultaneously. To formulate the joint bit allocation-code mapping problem we write the overall M e a n Squared E r r o r ( M S E ) of the subband coding technique, D , as: M ^ ^ ( r O +E^ZM^), (4-4) i=2 where M is the total number of subimages, erf is the variance of the i t h subimage, and D\(ri) and / ^ ( ^ i ) denote the variance-normalized distortion-rate functions for the M S L F S and the other subimages, respectively. T h e overall channel rate is given by: 1 « = S M (4.5) I > . . (4.4) and (4.5) are same as (2.24) and (2.25) except that instead of bits per pixel, r; is now the number of channel uses per pixel for the z'th subimage, which is not necessarily an integer. For example, assume that a subimage is to be encoded w i t h one bit, and the single source bit is to be channel coded using T C 1 6 P S K . Recall from Chapter 3 that this code generates one channel symbol for every three input bits. Therefore, the channel rate associated w i t h this single bit representing one subband sample, is 1/3. Once the two rate-distortion functions are known to the transmitter, the allocation algorithm of [24], reviewed i n section 2.6, is used to find the best r - for each subimage and t the appropriate channel code mapping associated w i t h that channel rate. Likewise the same algorithm is used at the receiver, to obtain the required information for decoding. T h e block diagram of the system is shown i n Figure 4.3. T h e rate distortion performance (i.e.: channel use/pixel vs. M S E ) for each subimage is obtained as follows. Chapter 4. Joint Source-Channel Coding 53 Source Encoders 1 MUX ''Channel -Encoder"#.'3? Router :-Cliannel Encoder it 2, Channel Encoder # 3 Channel Estimation Channel Decoder#2 Channel Decoder # 2 =Channel-Decoder #3; DEMUX Source Decoders Figure 4.3: T h e general block diagram of the proposed image transmission system. 4.2.1 C o m p u t a t i o n of Rate-Distortion Functions A t first, a l l possible values of R are computed based on combinations of bit allocation and channel code mapping. Note that there might be more than one configuration leading to a single value of channel rate. For example, if two bits are allocated to each pixel of a subimage and both bits are channel coded using T C Q P S K , the total channel rate for that subimage would be 2. Nonetheless, allocating three bits to each pixel and using T C Q P S K to code the first bit and T C 8 P S K to encode the other two bits, also leads to a total channel rate of 2. For cases where multiple channel codes are to be assigned to the source encoded bits of a pixel, the order of channel code assignment is that the stronger (lower rate) codes are used for the more significant bits, and the weaker (higher rate) codes are assigned to the less significant source encoded bits. Once a l l possible configurations for the points on the R-axis are computed and stored i n memory, synthetically generated Chapter 4. Joint Source-Channel Coding 54 G G D - m o d e l e d samples for the M S L F S (and the other subimages) are fed to the D P C M (and the P C M ) source followed by channel encoders, and are then passed through the A W G N channel according to each configuration. After channel and source decoding, the overall normalized M S E is calculated as a measure of quality between the samples at the output of the source decoder and the original samples, as: ^2( i,j i,j) x x MSE = ^ - = n 4-i ; (4.6) i,i x where a;,-j and Xij denote the original and the reconstructed pixel at the output of the source decoder, respectively. To generate a distortion measure associated w i t h any channel rate n, the smallest measured normalized M S E for a l l configurations is stored, along w i t h the corresponding configuration, only if M S E ( r ) < M S E ( r j _ ! ) for r; > r _ i . 8 t The M S E and the configuration associated w i t h the previous lower channel rate w i l l be stored otherwise. Following this procedure guarantees that under no circumstances w i l l the measured M S E increase as the channel rate increases. T h i s procedure w i l l generate the R D curve for system B , nevertheless, the only modification needed for system A , is that configurations which have more than one channel code for the subimage are ignored. This w i l l l i m i t the realizable values of the channel rate. Figure 4.4 shows the lower envelope of the variance-normalized rate-distortion functions of system B , for several channel conditions. It is clearly seen that as the channel noise increases, more channel rate is needed to keep the distortion unchanged. These curves, generated using G G D - m o d e l e d synthetic source, are stored by both the transmitter and the receiver. Because the curves are actually a collection of discrete points, the storage requirement for this is reasonably low. Chapter 4. Joint Source-Channel Coding 55 For the family of DPCM eivtlecoders 10" 3 10" 10"' 2 For the family of PCM er/decoders 10° 10" 3 10" 10"' 2 MSE (Normalized). MSE (Normalized) (a) (b) 10° Figure 4.4: Rate-Distortion curves for several channel conditions, (a) Z)i(r;), generated for M S L F S using G G D - m o d e l e d samples w i t h a = 1.70. (b) Di(ri), generated for other subimages using G G D - m o d e l e d samples w i t h a = 0.75. 4.3 Side Information Overhead C o m p u t a t i o n A s discussed earlier, the mean value of the L F S must be known to the receiver for reconstruction of the L F S pixels. T h e variances of all subimages are required by the receiver so that it can determine the bit allocation and channel code mapping; as well, the receiver requires the reconstruction levels for the L l o y d - M a x quantizers, and the prediction coefficient of the M S L F S . T h e number of reconstruction levels changes as the source encoding Chapter 4. Joint Source-Channel Coding 56 Table 4.3: Throughput computed for systems using T C M and P C channel codes System using T C M codes for error correction System using P C codes for error correction R = 0.25 R = 0.5 87.6% 95.7% 83.9% 92.9% R = 1.0 84.1% 90.9% rate varies, m a k i n g it impossible to compute a fixed measure of side information. However, i n what follows, we have considered a worst case scenario to compute a lower bound on the system throughput. It can easily be shown that the total number of reconstruction levels for source coding of all subimages according to a given quota of bits is m a x i m i z e d , when a l l available bits are allocated to one subimage. In our model, we have l i m i t e d the m a x i m u m number of bits per pixel for each subimage to be 8. For a design rate of 1 channel use/pixel, and for a m a x i m u m number of reconstruction levels, we assume that the least number of bits are being assigned for forward error correction, meaning that only T C 1 6 P S K is i n use for channel encoding of a l l source encoded bits. It is assumed that 2 bytes are used for transmission of each real number, and it is further assumed that using the strong rate 1/4 P C code and Q P S K modulation, provides sufficient protection for transmission of the side information to the receiver. W i t h these assumptions, the lower bound for the throughput for transmission of a 512x512 image is: [512 x 512 x 8 x 6/16 x 1/3] [(6 x 2 + 16 + 2) x 2 x 8 x 4 x 1/2] + [512 x 512 x 8 x 6/16 x 1/3] 8 ' { ' } T h e lower bound for the throughput for different design rates for our proposed system using two different family of channel codes are computed and presented i n Table 4.3. It was observed that the actual system throughput during the course of simulations, d i d not fall below 98%. Chapter 4.4 4.4.1 4. Joint Source-Channel Coding 57 Simulation Results Performance Evaluation of the Proposed Systems Based on the T C M Code Family To evaluate the performance of the proposed systems, the first system is implemented as follows. A pair of D P C M en coder/decoder w i t h first order linear prediction and ChangDonaldson renormalization and a series of P C M en coder/decoder pairs are implemented w i t h L l o y d - M a x quantizers. Three channel codes from the family of the T C M codes i n chapter 3 are used for channel error protection. T h e D E M S L F S and other subimages are modeled by a generalized Gaussian distribution w i t h a = 1.70 and a = 0.75, respectively. T w o rate-distortion functions D\{r) and D (r) 2 are generated according to the channel S N R , and the bit allocation and mapping algorithm explained i n Section 4.2 is employed to find the o p t i m u m bit allocation and appropriate channel code mapping for the source coded bits. T h e monochrome 512x512 Lena image is sent over the A W G N channel using systems A and B , w i t h the results plotted for different design channel rates and varying channel conditions i n Figures 4.5, 4.6 and 4.7. Note that the dashed curves indicate the performances of E q u a l E r r o r Protection ( E E P ) systems, where only one channel code is available for forward error correction for all subimages. T h e proposed systems A and B show a performance similar to the one for the E E P system using T C Q P S K i n the low channel S N R region, however, they exhibit over 3 d B performance gain for higher values of the channel S N R . Moreover, systems A and B show a similar performance to that of the E E P system w i t h T C 1 6 P S K i n high S N R environments, but perform extremely better ( P S N R gains of up to 17 d B ) i n the presence of low channel S N R . If one is to choose a single channel code to design an image transmission system over the S N R range that we consider, then the T C 8 P S K code would be the best option i n the sense that the average distortion is m i n i m i z e d over the entire range of channel conditions. A l t h o u g h our Chapter 4. Joint Source-Channel Coding 58 34 m •a a SP 6 -o c o J3 32 30 28 26 24 22 C/3 EEP system with TC16PSK - - 0 - • EEP system with TC8PSK - -A— EEP system with TCQPSK - - O - Adaptive system B ^dagti ptive s^stem^^^^^^^^^^^ 20 18 10 12 E / N (in dB) s 14 16 18 20 0 Figure 4.5: Performance comparison for channel rate R = 0.25 s y m b o l / p i x e l . 34 -o 32 30 T3 0) S o o J3 28 26 24 22 (1, EEP system with TC16PSK - - O - • EEP system with TC8PSK - - A - • EEP system with TCQPSK - - B Adaptive system B ^darjtive^stem^^^^^^^^^^^ 20 18 10 12 E / N (in dB) s 14 16 18 0 Figure 4.6: Performance comparison for channel rate R = 0.5 s y m b o l / p i x e l . 20 Chapter 4. Joint Source-Channel Coding 59 36 9 bo e 34 32 30 28 C o o u J3 on Oh 26 24 EEP system with TC16PSK - - O - EEP system with TC8PSK - - A - EEP system with TCQPSK - - a - Adaptive system B Adaptive system A 22 20 10 12 E / N (in dB) s 14 16 18 20 0 Figure 4.7: Performance comparison for channel rate R = 1.0 s y m b o l / p i x e l . adaptive scheme behaves similarly to the T C 8 P S K system i n a small range of channel S N R s i n the m i d region of the whole range, it exhibits a much better performance i n all other channel conditions. Another possible design scenario is that a l l the channel codes are available to the system, but only one could be used at a time according to the channel S N R . Threshold limits must be set according to the B E R performance curves of the channel codes, and the system must be allowed to switch between the channel codes as the S N R changes. T h e performance of such a system is an exact envelope of the three dashed curves i n Figures 4.5, 4.6 and 4.7. T h e adaptive system A outperforms this envelope curve over the whole S N R range, w i t h an advantage that it is as high as 2 d B P S N R . However, since system B outperforms system A by a negligible amount, it is evident from these curves that very little may be gained by allowing m u l t i p l e channel codes to be used per subimage. T h e results of the transmission of the Lena image for Chapter 4. Joint Source-Channel Coding 60 Figure 4.8: Performance comparison for channel rate R — 0.25 s y m b o l / p i x e l , ( T C M code family used), (a) E E P system w i t h T C 1 6 P S K and R = 0.25, P S N R = 25.7 d B . (b) E E P system w i t h T C 8 P S K and R = 0.25, P S N R = 29.3 d B . (c) E E P system w i t h T C Q P S K and R = 0.25, P S N R = 28.1 d B . (d) System B with R = 0.24, P S N R = 30.6 d B . Chapter 4. Joint Source-Channel Coding 61 S N R = 13 d B , are shown i n Figure 4.8 for subjective comparison purposes. The m u l t i p l e codes used by system A or B at a particular channel S N R are i n their operational region according to the B E R performance of the code. In fact, from our results it is evident that the channel S N R is the p r i m a r y factor determining which codes are selected by the system. Moreover, i n practice it was found that most of the subimages other than the L F S are discarded, and even the ones which are not discarded are assigned a very small number of source bits, where there is a little difference between the Most Significant B i t ( M S B ) and the Least Significant B i t ( L S B ) . T h i s explains the small performance gain of system B over system A . It is further observed that for the areas of the channel S N R where not more than one code is considered operational, the performance curves of the adaptive system converges to the performance curve obtained from the E E P system w i t h best code i n that region. In fact, the only gain observed i n this area is due to the more precise bit allocation technique used i n the adaptive system. To investigate this further, the higher resolution family of P C channel codes are considered instead for the adaptive systems i n the next section. 4.4.2 Performance Evaluation for Systems Based on the P C C o d e F a m i l y The following P C codes, used w i t h Q P S K modulation, that were reviewed i n Chapter 3 are used: • rate 3/4 P C C w i t h Q P S K , which produces 2 channel symbols for every 3 bits, • rate 4/5 P C C w i t h Q P S K , which produces 5 channel symbols for every 8 bits, and • rate 5/6 P C C w i t h Q P S K , which produces 3 channel symbols for every 5 bits. The similar performance of these codes, causes more than one code to be available to the system at each channel S N R , which i n turn causes the adaptive system to show a better Chapter 4. Joint Source-Channel Coding 62 performance at every channel S N R . Codes which are weaker i n terms of protection against channel errors are used to protect the L S B s . These codes consume less channel b a n d w i d t h and provide some extra room for additional protection of M S B s of the source bits. O f course there is a price to pay, and that is the reduced dynamic range of channel S N R s . If this system is to perform i n the same range of channel conditions as the system using the T C M code family, more channel codes of the family must be employed. T h e more channel codes used, the more complex would become the task of generation of the rate-distortion curves. However, this added complication is not an issue since the computation of the R D curves are done once, and the results are stored i n the memory thereafter. Figures 4.9, 4.10 and 4.11 exhibit the performance comparisons for the systems A , B , and E E P systems for three design channel rates . 1 It is clearly seen that although there is an overall improvement i n the performance of the adaptive scheme over the E E P systems, both of the proposed systems A and B show similar performance. This is because even though multiple codes are used i n system B to differentiate the M S B from the L S B , the B E R performance of these codes are so close that there is actually not m u c h difference in the amount of protection assigned to M S B s and L S B s . T h e results of the transmission of Lena image for S N R = 6 d B , are plotted i n Figure 4.12 for subjective comparison purposes. 4.4.3 Universality and Effectiveness of the System In order to evaluate the universality of our system, we have performed the simulations over a different test image. This test is performed on the systems employing the family of P C codes, for the design rate R = 0.25 channel s y m b o l / p i x e l . T h e results are presented i n Figure 4.13. Comparing to Figure 4.9, It is observed that the similar gains are In cases where the exact value of the design rate is not reachable, the largest possible value from below is considered. For example, the actual channel rate for E E P systems using the rate 4/5 P C code (rate 5/6 PC code) is 0.234, 0.469 and 0.977 (0.225, 0.488 and 0.975) in Figures 4.9, 4.10 and 4.11 1 Chapter 4. Joint Source-Channel Coding 63 34 32 30 -11 28 y 26 J 24 22 [ 20 i 1! < ><''' • 4.5 ^— ^ f EEPsy stem with fyfi PCC EEP sy stem with <••5 PCC C B f system wim trt Adaptive system B Adaptive system A <''S r / 1 *S 5.5 6.5 7 7.5 E /N (in dB) s 8 8.5 - -A— —u— 9.5 0 Figure 4.9: Performance comparison for channel rate R = 0.25 s y m b o l / p i x e l , ( P C code family used). achieved by the adaptive system for this different test image. Furthermore, to examine the effectiveness of our modelling technique, we have used the actual subband symbols of the Lena image to obtain the required source encoding and channel code m a p p i n g parameters, for any given channel S N R . These parameters were found to be similar to the ones obtained from the model. 4.4.4 Performance Evaluation of the Systems U s i n g a M o r e Noise Sensitive DPCM Encoder T h e performance comparison of a 2D predictor with I D predictor [7] confirms that the latter is less sensitive to noise. T h e use of a more noise sensitive D P C M encoding scheme for encoding the L F S would make the transmission more sensitive to the channel noise, and therefore we expect the performance gain achieved by the adaptive system i n this Chapter 4. Joint Source-Channel Coding 64 34 32 30 28 . x f • 24 20 18 4.5 Ir ' •> i S S * ^ * ' 1 * s 26 22 r r s • s s EEP sy stem with fV6 PCC EEPsy stem with ^/5 PCC cur system witn r<^^ Adaptive system B Adaptive system A i <f 5.5 6.5 7 7.5 E / N (in dB) s 8 8.5 A —tj— 9.5 0 Figure 4.10: Performance comparison for channel rate R = 0.5 s y m b o l / p i x e l , ( P C code family used). case be of more significance than i n the case of I D prediction. Figure 4.14 exhibits the performance comparison for the design rate of R = 0.25, performed w i t h the Lena test image. Evidently, the performance curves of a l l systems are degraded i n the low S N R regions due to the higher noise sensitivity of the encoding scheme used for L F S . It is further noted that the adaptive systems perform slightly better than the E E P systems, as expected. Note that the change i n predictor design affects the characteristics of the D E M S L F S values and therefore a new G G D model is needed. In fact, new tests were performed to find the best model for L F S of the test images, and the G G D w i t h a = 1.40 found to be the best model for the D E M S L F S . A new series of synthetic samples are generated and used to generate a new rate-distortion function for each channel S N R . The rate-distortion functions representing other subimages remain unchanged. Chapter 4. Joint Source-Channel Coding 65 34 32 30 28 26 24 22 EEP system with PCC EEP system with 4/5 PCC EEP system with 3/4 PCC Adaptive system B Adaptive system A 20 18 4.5 5.5 6.5 7 7.5 E / N (in dB) s 8 8.5 — -A— - -ED— - 9.5 0 Figure 4.11: Performance comparison for channel rate R = 1.0 s y m b o l / p i x e l , ( P C code family used). 4.4.5 Effect of Channel Mismatch In the proposed system, we assumed that the channel condition is known to the transmitter and the receiver. T h i s i n fact is a practical approach which can be implemented using a pilot signal to sense the channel condition. However, for a realistic evaluation of the system performance it is desirable to know how the system performs when the channel S N R is poorly estimated. To study the channel mismatch effect we define P S N R p x as the average P S N R resulting from a system designed for channel S N R = F d B and applied to a channel w i t h S N R = X d B . Likewise the P S N R ^ x ^ defined as the average s P S N R resulted from a system designed for and applied to channel S N R = X d B . T h e P S N R g x and P S N R ^ x values are plotted i n figure 4.15 to show the effect of the channel mismatch. These curves are obtained for the Lena image, transmitted using R = 0.25 Chapter 4. Joint Source-Channel Coding 66 Figure 4.12: Performance comparison for channel rate R = 0.25 s y m b o l / p i x e l , ( P C code family used), (a) E E P system with rate 5/6 P C C and R = 0.225, P S N R = 22.5 d B . (b) E E P system w i t h rate 4/5 P C C and R = 0.234, P S N R = 24.4 d B . (c) E E P system with rate 3/4 P C C and R = 0.25, P S N R = 25.8 d B . (d) System B w i t h R = 0.245, P S N R = 27.8 d B . Chapter 4. Joint Source-Channel Coding .E 67 Y- - - y" [ ir < 4.5 f < y y y y y J r y EEPsy stem with!y«PCC EEP sy stem with <•.6 PCC nur system witn .y* Adaptive system B Adaptive system A 5.5 6.5 7 7.5 E / N (in dB) s 8.5 — -A— - —tj— 9.5 0 Figure 4.13: Performance comparison for channel rate R image ( P C code family used). 0.25 s y m b o l / p i x e l , for Couple channel use/pixel and the system using the P C C family and 2 D - D P C M encoding for the MSLFS. Chapter 4. Joint Source-Channel Coding 68 34 32 30 . 28 26 24 22 / [— 20 • I 18 4.5 ^ s *s I s s <' / s 5.5 * s <s/ s s '"-''1 i * s >' 1 ! f 1 11 EEPsy stem with fv^PCC --0-EEPsy stem with </5 • PCC — -A— net- system witn -trAdaptive system B Adaptive system A s > 6.5 7 7.5 E / N (in dB) s 8.5 9.5 0 Figure 4.14: Performance comparison for systems employing 2D prediction, channel rate R = 0.25 s y m b o l / p i x e l , for Lena image ( P C code family used). Chapter 4. Joint Source-Channel Coding 69 Chapter 5 Conclusions and Recommendations for Future Research We have proposed two versions of a joint source-channel image coding scheme which shows an excellent performance over a wide range of A W G N channel conditions. System A allows the use of a l l channel codes for a l l the subimages, but limits the number of channel codes to be used per subimage to one. W h i l e system B does not have the latter restriction. A D P C M codec and a series of P C M codecs are employed to encode the 16 subimages, which are obtained by a 4x4 subband decomposition. A set of channel codes are then made available to the system from one of two families of codes, either T C M or P C codes, and the performance of both of the systems are evaluated i n each case. We have compared our proposed systems to the E E P systems of equivalent channel rate. It is shown i n Chapter 4 that none of the E E P systems can provide a good quality reconstructed image over the range of channel S N R s for which our system can. Another design scenario could be an adaptive E E P system w i t h selective channel coding, where the best channel code is used for the whole image at a particular channel S N R . T h e performance of such an adaptive system would be an exact envelope of the performance of the i n d i v i d u a l E E P systems. Our proposed systems (system A and system B ) outperform the adaptive E E P system by as much as 2 d B P S N R , p r i m a r i l y because of the unequal error protection employed among subimages. There is little difference between system A and system B for both the low-resolution T C M family of codes and the high resolution P C family of codes, which shows that unequal error protection w i t h i n a subimage is relatively unimportant. For the system employing the T C M code family, the fact that 70 Chapter 5. Conclusions and Recommendations for Future Research 71 the performance of the individual members are so different, limits the number of channel codes invoked by the system at each channel S N R . A t a given channel S N R , one code is predominantly used, and therefore the M S B and L S B are not treated very differently for error protection. O n the other hand, the similar performance of the i n d i v i d u a l members of the P C code family causes many codes to be invoked at each channel condition, and therefore different channel codes are assigned to L S B s and M S B s of i n d i v i d u a l subimages. Nevertheless, the similarity of the performance of the channel codes i n the family results i n a similar amount of protection against channel errors for the M S B and the L S B , which causes system B to perform negligibly better than system A at any channel S N R . Since it is observed that there is very little advantage i n the performance of system B over system A , for both the low resolution family and the high resolution family of channel codes, no significant gain is anticipated for any other intermediate resolution code family. Needless to say, the dynamic range of the operating channel S N R s for the family of P C codes is reduced, therefore more than three channel codes would be needed to cover a larger range of channel S N R s by this code family. Our modelling technique allowed us to characterize any arbitrary image by only a few parameters, which enabled us to reduce the amount of the required side information, and achieve a universal system design that for any particular image performs almost as well as a system tuned to that image. It was also shown that although our system needs an estimate of the channel S N R to obtain the transmission parameters, it is very robust to an inaccurate channel S N R estimation. T h e following topics for further research i n this area are suggested: • Evaluate the proposed subband encoding scheme over fading channels. Chapter 5. Conclusions and Recommendations for Future Research 72 • Investigate different methods for modelling the images, like A u t o Regressive M o d elling. • Consider modification of the channel decoders to take advantage of the source statistics for decoding. • Study the performance of the system for color images. • Search for methods of estimating the channel condition. Glossary ASK AWGN ai ay a bpp BER {&;} C C CDF D DEMSLFS Di(r^) dkS d A m p l i t u d e shift keying A d d i t i v e white Gaussian noise z'th prediction poefficient Horizontal prediction coefficient Vertical prediction coefficient B i t per pixel B i t error rate Decision boundaries of the quantizer Number of bands i n the filter bank Number of columns of the perforation m a t r i x Cumulative distribution function The total distortion Differentially-encoded mean-subtracted lowest frequency subimage Distortion of the ith. subimage at given r\ bit rate Kolmogorov-Smirnov distance measure Difference sample d DPCM Di(ri) D<i(ri) ED EEP FEC FIR Fx(x) GGD go(n) <7i (n) Quantized difference sample Differential pulse coded modulation Distortion corresponding to the first subimage, given r; channel rate Distortion corresponding to the other subimages, given r; channel rate Euclidean distance E q u a l error protection Forward error correction F i n i t e impulse response Cumulative distribution function of random samles Generalized Gaussian distribution Impulse response of the low-pass synthesis filter Impulse response of the high-pass synthesis filter Frequency response of the low-pass filter 2 p n n HLP{W) 73 Glossary 74 H {w) h (n) h\{n) K K KS L LFS LSB HP 0 c ft} M MPSK MSB MSE MSLFS N iV(-,-) rii No/2 PC PCC PCM P k Pn PSNR PSNR Px(x) [P] q Q(-) QMF q QPSK R R' R'(A) n Rb F X Frequency response of the high-pass filter Impulse response of the low-pass analysis filter Impulse response of the high-pass analysis filter Order of the prediction function Constraint length of the convolutional code Kolmogorov- Smirnov N u m b e r of filter taps Lowest frequency subband Least significant bit reconstruction levels Total number of subbands M - a r y phase shift keying Most significant bit M e a n squared error Mean-subtracted lowest frequency subimage Number of rows and columns of the image Gaussian distribution Sample of the white Gaussian noise Noise power spectral density Punctured convolutional Punctured convolutional code Pulse coded modulation Smallest allocatable rate for kth subband Prediction function Peak signal-to-noise ratio P S N R of the system designed for F d B , and applied to X d B . channel S N R Probability density function of random samples Perforation m a t r i x N u m b e r of source bits of a quantizer Quantizer function Largest allocatable rate for kth subband Quadrature mirror filter Quantization error Quadrature phase shift keying Average design channel rate (channel use per pixel) Average design bit rate (bit per pixel) Solution rate, given A Rate counter Glossary RCPC RD < R p Rxx(j) Si Sk SNR Sp system A system B T TCM TCMPSK TCQPSK TC16PSK TC8PSK UEP Uk v (n) vi(n) x{n) 0 iJ n XiJ x'(n) x(n) X x Vo(n) 3/i fa) Zi Z ID 2D 8PSK 16PSK 75 Rate compatible punctured convolutional Rate-distortion Largest solution rate, given A Channel rate for the ith subimage B i t rate for the i t h subband Smallest solution rate, given A Number of rows of the perforation m a t r i x j ' t h order autocorrelation function Transmitted signal Collection of allocatable bits or channel rates Signal-to-noise ratio i n d B Signal power System that does not allow multiple codes per subimage System that allows multiple codes per subimage Number of quantizer levels Trellis coded modulation Trellis coded M - a r y phase shift keying m o d u l a t i o n Trellis coded quadrature phase shift keying m o d u l a t i o n Trellis coded 16-ary phase shift keying modulation Trellis coded 8-ary phase shift keying m o d u l a t i o n Unequal error protection Solution rate for kth. subimage, given A Output of the low-pass analysis filter Output of the high-pass analysis filter Source symbol sequence Original pixel of the image Symbol at the output of the quantizer Reconstructed pixel of the image Recomposed symbol sequence Extended symbol sequence Subband low-pass decomposed sequence Subband high-pass decomposed sequence Received signal Received sequence of signals One dimensional T w o dimensional 8-ary phase shift keying 16-ary phase shift keying Glossary o\ a a\ Pi a (3 T A r](-, •) 2 76 Variance of the difference sequence M e a n squared quantization error Variance at the output of the &th downsampler i t h normalized autocorrelation coefficient Shaping factor of the generalized Gaussian distribution Variance of the generalized Gaussian distribution G a m m a function M u l t i p l i e r i n the unconstrained m i n i m i z a t i o n problem A function of the shaping factor and the variance of the G G D Bibliography [1] C . E . Shannon, " A mathematical theory of communication," Bell System Journal, v o l . 27, pp. 379-423 & 623-656, J u l y 1948. Technical [2] C . E . Shannon, "Coding theorems for a discrete source w i t h a fidelity criterion," i n IRE National Convention Record, Part 4, PP- 142-163, 1959. Also i n Information and Decision Processes, R . E . M a c h o l , E d . New York, N Y : M c G r a w - H i l l , 1960, pp. 93-126. [3] E . Ayanoglu and R . M . Gray, "The design of joint source and channel trellis waveform coders," IEEE Trans. Inform. Theory, vol. IT-33, pp. 855-865, November 1987. [4] J . W . Modestino and D . G . Daut, "Combined source-channel coding of images," IEEE Trans, on Communications, vol. 27, pp. 1644-1659, N o v . 1979. [5] J . W . Modestino, D . G . Daut, and A . L . Vickers, " C o m b i n e d source-channel coding of images using the block cosine transform," IEEE, Trans, on Communications, vol. 29, pp. 1261-1274, Sept. 1981. [6] N . Farvardin and V . Vaishampayan, " O p t i m a l quantizer design for noisy channels: A n approach to combined source-channel coding," IEEE Trans, on Information Theory, v o l . 33, pp. 827-838, Nov. 1987. [7] R . L i n k and S. K a l l e l , " O p t i m a l use of markov models for D P C M picture transmission over noisy channels," Submitted to IEEE Transactions on Communications, Feb. 1999. [8] N . Tanabe and N . Farvardin, "Subband image coding using entropy-coded quantization over noisy channels," IEEE Journal on Selected Areas in Communications, vol. 10, pp. 926-943, June 1992. [9] M . Srinivasan and R . Chellappa, " A d a p t i v e source-channel subband video coding for wireless channels," IEEE Journal on Selected Areas in Communications, v o l . 16, pp. 1830-1839, Dec. 1998. [10] P. H . Westerink, J . H . Weber, D . E . Boekee, and J . W . Limpers, " A d a p t i v e channel error protection of subband encoded images," IEEE Trans, on Communications, vol. 41, pp. 454-459, M a r . 1993. 77 Bibliography 78 [11] W . X u , J . Hagenauer, and J . H o l l m a n , "Joint source channel decoding using the residual redundancy i n compressed images," i n Proc. ICC/SUPER COMM'96, pp. 142-148, June 1996. [12] K . Sayood, Introduction to data compression. K a u f m a n n Publishers, 1996. San Francisco, California: M o r g a n [13] R . V . C o x , J . Hagenauer, N . Seshadri, and C . W . Sundberg, "Subband speech coding and matched convolutional channel coding for mobile radio channels," IEEE Trans. Signal Process., vol. 39, pp. 1717-1731, A u g . 1991. [14] J . W . Woods and S. D . O ' N e i l , "Subband coding of images," IEEE Trans, on Acoustics, Speech, and Signal Processing, v o l . 34, pp. 1278-1288, Oct. 1986. [15] H . G h a r a v i and A . Tabatabai, "Sub-band coding of monochrome and color images," IEEE Trans, on Circuits and Systems, vol. 35, pp. 207-214, Feb. 1988. [16] G . P i r a n i and V . Zingarelli, " A n analythical formula for the design of quadrature mirror filters," IEEE Trans, on Acoustics, Speech, and Signal Processing, v o l . 32, pp. 645-648, June 1984. [17] L . Shen, W . J i a , and P. Chen, "Filter banks for image subband coding," vol. S I C E - 9 5 , pp. 1201-1204, 1995. SICE-95, [18] M . S m i t h and S. Eddins, "Subband coding of images w i t h octave band tree structures," Proc. IEEE Int. Conf. Acoust., Speech, and Signal Processing, v o l . 32, pp. 1382-1385, A p r . 1987. [19] K . Y . Chang and R . W . Donaldson, "Analysis, optimization and sensitivity study of differential P C M systems operating on noisy communication channels," IEEE Trans, on Communications, v o l . 20, pp. 338-350, June 1972. [20] S. L L o y d , "Least squares quantization i n P C M , " IEEE ory, v o l . 28, pp. 129-136, M a r . 1982. Trans, on Information The- [21] J . J . Y . Huang and P. M . Schultheiss, "Block quantization of correlated gaussian random variables," IEEE Trans. Commun. Syst., v o l . CS-11, pp. 289-296, Sept. 1963. [22] A . Segall, " B i t allocation and encoding for vector sources," IEEE Information Theory, vol. IT-22, pp. 162-169, M a r . 1976. Transactions on [23] B . Fox, "Discrete optimization v i a marginal analysis," Management pp. 210-216, N o v . 1966. Science, v o l . 13, Bibliography 79 Y . Shoham and A . Gersho, "Efficient bit allocation for an arbitrary set of quantizers," IEEE Trans, on Acoustics, Speech, and Signal Processing, vol. 36, pp. 14451453, Sept. 1988. G . Ungerboeck, "Channel coding w i t h multilevel/phase signals," IEEE form. Theory, v o l . IT-28, pp. 55-67, January 1982. Trans. In- A . J . V i t e r b i , J . K . Wolf, E . Zehavi, and R . Padovani, " A pragmatic approach to trellis-coded modulation," IEEE Communications Magazine, pp. 11-19, J u l y 1989. S. M . A l a m o u t i and S. K a l l e l , "Adaptive trellis-coded multiple-phase-shift keying for rayleigh fading channels," IEEE Trans, on Communications, v o l . 42, pp. 2305-2314, June 1994. J . Hagenauer and P. Hoeher, " A viterbi algorithm w i t h soft-decision outputs and its applications," i n Proc. Globecom, (Dallas, T X ) , pp. 1680-1686, N o v . 1989. S. H . J a m a l i and T . Le-Ngoc, Coded-modulation techniques for fading Norwell, Massachusetts: Kluwer Academic Publishers, 1994. channels. J . B . C a i n , G . C . C . Jr., and J . M . Geist, "Punctured convolutional codes of rate ( n - l ) / n and simplified m a x i m u m likelihood decoding," IEEE Trans, on Information Theory, v o l . 25, pp. 97-100, Jan. 1979. D . Haccoun and G . Begin, "High-rate punctured convolutional codes for viterbi and sequential decoding," IEEE Trans, on Communications, v o l . 37, pp. 1113-1125, Nov. 1989. S. W i c k e r , Error Control Systems for Digital Communication Prentice H a l l Canada Inc., 1995. and Storage. Toronto: Y . Yasuda, K . K a s h i k i , and Y . H i r a t a , "High-rate punctured convolutional codes for soft decision viterbi decoding," IEEE Trans, on Communications, v o l . 32, pp. 315319, M a r . 1984. G . Begin and D . Haccoun, "High-rate punctured convolutional codes: structure properties and construction technique," IEEE Trans, on Communications, v o l . 37, pp. 1381-1385, Dec. 1989. N . Farvardin and J . W . Modestino, " O p t i m u m quantizer performance for a class of non-Gaussian memoryless sources," IEEE Transactions on Information Theory, vol. IT-30, pp. 485-497, M a y 1984. R . Reininger and J . Gibson, "Distribution of the two-dimensional D C T coefficients for images," IEEE Trans, on Communications, vol. 31, pp. 835-839, June 1983. Bibliography 80 [37] P. H . Westerink, J . B i e m o n d , and D . E . Boekee, "Evaluation of image sub-band coding schemes," i n EURASIP, pp. 1149-1152, Sept. 1988. [38] W . H . Press, B . P. Flannery, and W . Vetterling, Numerical recipes in C: The art of scientific computing. Cambrige, New York: Cambrige University Press, 2nd ed., 1992. [39] J . Banks, J . S. Carson, and B . L . Nelson, Discrete-event saddle river, New Jersey: Prentice-Hall, 1996. system simulation. Upper Appendix A Description of C o m p u t e r Simulation A l l the simulations are performed i n C , except i n a few stages where M a t l a b software package was used for simpler application of some mathematical operations, for generation of the G G D random samples. T h e reported P S N R values for the curves i n chapter 4 are averaged over 50 runs w i t h different seed numbers. Here is some detailed description of the simulations. A.l Source C o d i n g Step sizes of the quantizers are initialy distributed equally between the m i n i m u m and m a x i m u m values of the input sequence. To optimize the step sizes according to pdf of input sequence, L l o y d - M a x algorithm is implemented and 50 iterations are performed to obtain the optimized step sizes and corresponding reconstruction levels. T h e mapping of bits to quantization intervals are performed according to the folded binary technique. A.2 Channel Coding A rate 1/2 encoder w i t h constraint length K = 3 and block length of 128 is implemented. c To produce the B E R performance curves of chapter 3, the 18th least significant bit of the random integer generated by lrand48 is used as the input random bit sequence to the encoder. D u r i n g the course of computations of the rate-distortion functions and also for the implementation of the actual system, all the source coded bits are fed into channel 81 Appendix A. Description of Computer Simulation coders to perform the encoding operation. 82 For the channel codes which require more than one input stream, the additional streams are provided w i t h a l l zero bit sequence. Obviously, the decoded sequence corresponding to the encoded sequence at the receiver are discarded. A.3 AWGN Channel Gaussian random generator routine of [38] (page 283) along w i t h the procedure of page 289 of the same reference are used to produce an array of zero-mean unit-variance white Gaussian noise samples. T h e array length is fixed to 10,000 elements which is refilled once a l l the array elements are used. T h e seed number to regenerate a new array each time is provided by the lrand^8 function from the C library. Here is how the channel is modeled. Assuming: • Si : T h e bit intended for transmission, • rii : T h e Gaussian random variable n - 6 t N(0,1), • Zi : T h e received symbol, • S N R : Channel E /N s 0 in dB, • S : Signal power, p • No/2 : Noise power, the additive noise may be represented as (A.l) Since the channel S N R is expressed i n d B as S N R = 10 log Sp (A.2) Appendix A. Description of Computer Simulation 83 the noise power required for equation A . 3 is obtained from N 0 A.4 = Sp (A.3) Generation of G G D R a n d o m Variables Inverse transform technique [39] is a well known method of generating random variables which uses the inverse C u m u l a t i v e D i s t r i b u t i o n Function ( C D F ) . For continuous distributions like G G D where there is no closed form expression for the C D F or its inverse, the approximate of inverse C D F or numerically computed C D F may be used to generate the random variables. It should be noted that numerically computed C D F does not i m ply any imprecision in. generation of the random variables, simply because even i n cases where a closed form expression exists, numerical approximations are made during certain mathematical operations like ln(-) or log(-). We have used steps of length 0.001 i n the interval [-8,8] to approximate the C D F of any given G G D distributions. Once the C D F is generated, the random variables are generated according to the table lookup procedure of [39] (page 336). T h e only disadvantage of this method is the longer run time, which makes it an attractive alternative if the generation of random variables is not to be used repeatedly. A.5 Confidence Interval To check the accuracy of the simulation results, one particular point is tested that represents the performance of system B and S N R = 9 d B , i n Figure 4.9. T h e point is chosen for a clean channel condition which corresponds to a lower number of error events. T h e averaged P S N R over 50 runs was reported as 29.7 d B . T h e 95% confidence interval for this point was calculated to be [29.65 d B - 29.78 d B ] . A l l the other simulations which are Appendix A. Description of Computer Simulation 84 performed for noisier channel conditions, are expected to experience more error events, which result i n more accurate P S N R measurements. Appendix B S u m m a r y of F E C Codes Used in the System T h e B E R performance of all the channel codes used i n this thesis are presented together for ease of comparison i n Figure B . l . This is just a re-collection of previous results and there are no differences from the individually presented curves of Chapter 3. o Rate 3/4 TCI6PSK — E l — Rate2^TC8PSK - - A - Rate 1/2 TCQPSK - - © - - Rate 5/6 PCC 1 Rate 4/5 PCC — * Rate 34 PCC — 0 — I 1k V——s— ( —'-^ k N \ \ 2 3 \ 11 4 "A r \ \ 1 k — V IT 1 i\ \ 0 *•*— 1 5 \ \ —s V r \ 1I — X — —N— V 11 k 6 7 8 E /N s 9 10 11 12 13 14 0 Figure B . l : B E R performances of the T C M and P C channel codes 85 15 16
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- An adaptive subband-based joint source-channel coder...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
An adaptive subband-based joint source-channel coder for image transmission Alavi, Amin 1999
pdf
Page Metadata
Item Metadata
Title | An adaptive subband-based joint source-channel coder for image transmission |
Creator |
Alavi, Amin |
Date Issued | 1999 |
Description | An adaptive subband image coding system is proposed that uses DPCM and PCM codecs for source encoding the individual subbands, and a family of variable rate channel codes for forward error correction. A low resolution family of trellis coded modulation codes and a high resolution family of punctured convolutional channel codes are implemented and investigated. Implementation of unequal error protection among the subbands, and within the subbands, is examined for the two separate versions of our system. Simulations are performed on the AWGN channel and comparisons are made with corresponding systems that use only a single channel code, or that use the same family of codes for an adaptive equal error protection scheme. Our proposed adaptive systems outperform any of the systems that use only a single channel code greatly, extending the useful SNR range by an amount that depends on the code family. As well, our systems outperform the corresponding adaptive equal error protection systems by as much as 2 dB PSNR. This is primarily due to the use of unequal error protection among the subbands, as surprisingly little additional gain is achieved by applying unequal error protection within the subbands. We use and improve a known modelling technique which enables the system to configure itself optimally for the transmission of an arbitrary image, by only measuring the mean of lowest frequency subband and variance of each of its subbands. Because our systems require an estimate of the channel SNR, we have investigated the sensitivity to poor channel SNR estimation, and have found negligible performance loss for channel mismatches up to 1.5 dB. |
Extent | 6248039 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2009-06-16 |
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.0065346 |
URI | http://hdl.handle.net/2429/9230 |
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 | 1999-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_1999-0330.pdf [ 5.96MB ]
- Metadata
- JSON: 831-1.0065346.json
- JSON-LD: 831-1.0065346-ld.json
- RDF/XML (Pretty): 831-1.0065346-rdf.xml
- RDF/JSON: 831-1.0065346-rdf.json
- Turtle: 831-1.0065346-turtle.txt
- N-Triples: 831-1.0065346-rdf-ntriples.txt
- Original Record: 831-1.0065346-source.json
- Full Text
- 831-1.0065346-fulltext.txt
- Citation
- 831-1.0065346.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
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-0065346/manifest