UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

An adaptive subband-based joint source-channel coder for image transmission Alavi, Amin 1999

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

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

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  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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>
                        
                    
IIIF logo 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

Comment

Related Items