%\documentclass [11pt]{report} \documentclass[12pt]{article} %\usepackage[dvips]{graphicx} \usepackage{setspace} \usepackage{timeline} \usepackage{amssymb,amsmath} \usepackage{floatflt} \doublespacing %\onehalfspacing \usepackage{graphicx} \usepackage[left=2cm,top=2cm,right=2cm, bottom=2cm]{geometry} \title { %Queen's University at Kingston\\ %Faculty of Applied Science\\ %~\\ %High Data Rate Visual Communication via Soft-Decision Robust Quantization Soft Decision Combined Source-Channel Coding\\ Design Chapter } \author { ~\\~\\~\\~\\~\\~\\~\\Tamra Baxter \and ~\\~\\~\\~\\~\\~\\~\\ Ken Edwards \and ~\\~\\~\\~\\~\\~\\~\\ Tim Evans %442 1922\\ %Tim Evans\\ %445 0933\\ %Ken Edwards\\ %435 6010\\ } \date { ~\\ \today\\ ~\\ ~\\ Supervised by: \\ Dr. Fady Alajaji\\ Dr. Firouz Behnamfar\\ } \providecommand{\abs}[1]{\lvert#1\rvert} \providecommand{\norm}[1]{\lVert#1\rVert} \begin{document} \pagestyle{empty} \maketitle \thispagestyle{empty} %no page number on title page \pagebreak %\tableofcontents %\pagebreak %\parindent=0in %\setlength{\parskip}{\baselineskip} \setcounter{page}{1} \setcounter{section}{1} \pagestyle{plain} %start of document \section{Design} \subsection{Engineering Design} The goal of this project is to investigate the performance of various decoding schemes for transmissions over noisy channels. Performance can be measured in complexity, cost, and bandwidth. Visual evaluation can sometimes conflict with the previous quantitative measures, as human visual perception can often mask certain types of distortion. The following discusses the main areas of design within this project. The simulation of noisy channels has already been done so the project will not focus on this simulation. However, there are aspects of the design as to how these noisy channels are simulated in our C models such as implementation, storage, precision, etc. The binary symetric channel is great for initially verifying the correctness of code. The Gaussian channel is better used to simulate real world performance. The Rayleigh fading channel is an even better approximation to wireless channel behaviour and will be enforcement to the validity of our simulations. This project will focus on how decoding is accomplished on noisy transmissions. Hard-decision decoding is a very simple decoding scheme. Received vectors/codewords generally include noise, so to determine what codeword was actually sent involves choosing the closest codeword from the codebook. Here we define closest codeword, $y_{i}$, as having the highest probability that $y_{i}$ was sent given our received codeword. A decision region is the region where all reveived vectors/codewords lie that will be mapped to a given codeword from our codebook. Complexity is minimal with this decoding scheme, small errors will be corrected while large errors will be decoded as incorrect codewords. If a received codeword included enough noise to put it slightly in an incorrect region then decoding will increase the perceived noise and decrease the signal to distortion ratio (SDR). We want to see if a different decoding scheme will provide better results. Soft-decision decoding, as opposed to hard-decision decoding, offers a different way of decoding that has the potential to improve SDR as well as perceived image quality. In soft-decision decoding, we will have intermediate regions that received codewords may be decoded into. Of course this method of decoding has its tradeoffs. While there is the opportunity that we decrease SDR compared with hard-decision decoding for the case of uncorrected decoding, we can also increase SDR when decoding received codewords in an intermediate region that would otherwise be corrected with hard-decision decoding. \subsection{Mathematical and Software Models} \subsubsection{Binary Symmetric Channel} The binary symmetric channel (BSC) is one in which each bit in the stream has an equal probability of being flipped. If the probability of one bit being flipped is $\epsilon$ then the probability of a message containing $n$ bits being sent over a BSC with k bits being flipped is: \begin{equation*} \binom{n}{k}\epsilon^{k}(1-\epsilon)^{n-k} \end{equation*} \subsubsection{Additive White Gaussian Noise Channel} The additive white Gaussian noise (AWGN) channel is a simple and effective general channel model. In an AWGN channel the source vector $\bf{x}$ may have an error introduced by the addition of an error vector $\bf{n}$. The only error that is introduced in an AWGN channel is additive. Multiplicative noise, which models such things as fading, is not modeled in this channel. The whiteness of the channel refers to the fact that noise is added at equal power across the frequency spectrum. The noise that is added to the source vector has zero mean and an average of $\sigma^2$, and hence the noise is Gaussian. \begin{figure}[h] \begin{center} \includegraphics[angle=0,scale=1]{bsc.png} \includegraphics[angle=0,scale=1]{awgn.png} \end{center} \caption{BSC and AWGN Channel Models} \label{awgn} \end{figure} \subsection{Vector Quantization} In vector quantization (VQ) we take a string of bits and assign them one codeword. There is an iterative algorithm called the Lloyd algorithm used to choose the optimal codewords for a set of vectors using two conditions: the nearest neighbour condition and the centroid condition. \begin{figure}[h] \begin{center} \includegraphics[angle=0,scale=0.75]{lloyd.pdf} \end{center} \caption{Lloyd Algorithm Flow Chart} \label{one} \end{figure} \subsubsection{Nearest Neighbour Condition} Each $R_i$ consists of all vectors $\bf{x}$ which have less distortion when reproduced with code vector ${\bf c}_i$ than with any other code vector. The nearest neighbour condition is how we divide up the whole space of possible inputs into decision regions. In this case we use the mean square error (MSE) as our distortion measure, yielding the following equation: \begin{equation*} R_i = \{ {\bf x} : \norm{{\bf x}-{\bf c}_i} \le \norm{{\bf x} - {\bf c}_j} , ~j = 1,\ldots,N\} ~\forall~ i= 1,\ldots,N \end{equation*} where $R_i$ is the $i^{\text{th}}$ decision region, ${\bf x}$ is an input vector, ${\bf c}_i$ is the $i^{\text{th}}$ codevector, and $N$ is the number of codevectors. \subsubsection{Centroid Condition} Once the decision regions, $R_i$ have been determined by the nearest neighbour condition, the centroid condition decides what codevector should act as the representative for this region. In the case that we use MSE as our distortion measure, the centroid condition reduces to finding the average codevector in the region: \begin{equation*} {\bf c}_i = \frac{\sum_{m:{\bf x}_m\in R_i} {\bf x}_m}{\sum_{m:{\bf x}_m\in R_i}1} \end{equation*} The two steps of applying the nearest neighbour condition and the centroid condition are repeated until the difference between two consecutive iterations falls below a predetermined threshold value. After the threshold has been reached we call the codebook $\mathcal{C}=\{{\bf c}_i\}_{i=1}^{N}$ \subsection{Channel Optimized Vector Quantization} Once the quantizer must be optimized for a particular channel the nearest neighbour and centroid conditions must be changed accordingly. The difference between the nearest neighbour and centroid conditions in a COVQ and a VQ is that the transition probabilities of the channel must be taken into account. These probabilities incorporate the fact that noise might take a transmitted signal from one codevector to another. The nearest neighbour condition becomes: \begin{equation*} R_{i}^{*}= \{ x: \sum_{j=0}^{M-1}P_{J|I}(j|i)\norm{{\bf x}-{\bf c}_j}^2 \le \sum_{j=0}^{M-1}P_{J|I}(j|k)\norm{{\bf x}-{\bf c}_j}^2 ~\forall~ k = 0,\ldots,M-1\} \end{equation*} while the centroid condition changes to: \begin{equation*} {\bf c}_{i}^{*} = \frac{\sum_{j=0}^{M-1}P_{J|I}(j|i)\sum_{m:{\bf x}_m\in R_{j}}{\bf x}_m}{\sum_{j=0}^{M-1}P_{J|I}(j|i)\sum_{m:{\bf x}_m\in R_{j}}1} \text{ for } j=0,\ldots,M-1 \end{equation*} We now get an optimal codebook to get $\mathcal{C}^{*}=\{{\bf c}_{i}^{*}\} , i = 0,\ldots,M-1$. \subsection{Software Design and Analysis} The old saying in software engineering goes: ``Fast, cheap, or good. Pick any two.'' In this adage \emph{fast} refers to time to market, \emph{cheap} to the cost of the project, and \emph{good} to how well the product is implemented. Our software must be developed quickly. We have a hard deadline of the end of March, 2005. By that time our software must be stable and be producing correct results. Since we are but undergraduate students, our cost comes in terms of an opportunity cost. We have to make tradeoffs both in terms of different parts of this project and in terms of time division between this project and our other coursework. It is in the \emph{good} of the project that we had to make some sacrifices. This is not to say that the code produced does not work, it does. The sacrifices come in the fact that the program has not been developed in a manner that follows what are considered good software design patterns. The tradeoffs with price and development time are not the only reason for this sacrifice. This project is one in which the source code goes through many incremental changes. Once the team understands a new mathematical concept, we go back to the code and make the necessary changes. The code base started with a program provided by Dr. Behnamfar which simulated vector quantization of a Gaussian source. The team's first step was to make the connection between our mathematical understanding of Gaussian sources, the nearest neighbour condition, and the centroid condition, and the source code provided. Dr. Behnamfar stressed that a strong understanding of the original source code and the underlying mathematics would be critical to the success of the project. Once the connection was made, the first step was to simulate communication across a channel. The first channel implemented was the binary symmetric channel, the simplest channel to understand. Once this step was complete, the team modified the code to adapt the vector quantization to the characteristics of the channel, in effect, the team implemented channel optimized vector quantization (COVQ). The channel is represented by an n by n\footnote{Where n is the number of vectors in our code book} transition probability matrix. We pre-computed the matrix so that when channel errors are simulated, only a table lookup need be preformed. The next step in the project is to change the channel to one that models additive white Gaussian noise (AWGN). Once a more realistic channel is in place, the soft decision decoding portion of the project will be introduced. This will involve a more significant amount of programming than the previous portions of the project. If time remains after soft decision decoding is implemented two other possible avenues of exploration include implementing a Rayleigh fading channel or to move on to a higher dimension quantization method, for example moving from BPSK to QAM. The project does not end with the simulation of different channels and decoders. Once complete, a numerous amount of simulations must be run and analysis preformed. One of the team members has some experience in automated testing and report generation, so these skills will be exploited in a hope that extensive automated testing will lead to a greater amount of data, which will in turn lead to a more precise analysis. The analysis will include comparing VQ to COVQ and soft decision COVQ to hard decision COVQ. The analysis will also include details on how a `good' codebook is chosen. Good can be described both quantitatively, by examining various signal to noise ratios (SDR, SNR), and quantitatively, by examining the resulting transmissions. Standard images such as Lena and the baboon [Figure~\ref{LenaBaboon}] will be used. \begin{figure}[h] \begin{center} \includegraphics[angle=0,scale=0.3]{lena.jpg} \includegraphics[angle=0,scale=0.3]{baboon.jpg} \end{center} \caption{Standard sample images in communications theory} \label{LenaBaboon} \end{figure} \pagebreak \subsection{Division of Labour} After setting up several meetings with our advisor Dr. Behnamfar, the team decided that it would be in our best interests to make the meeting at least a weekly occurrence. The team members are fortunate in that they have very similar academic schedules, which makes group work very easy to schedule. Eighty to ninety percent of the work done so far has been done as a group. Any work that has been done individually has been reviewed together as a group. As mentioned in a previous section, Dr. Behnamfar has been extremely helpful by providing guidance both with the mathematical concepts and the computer implementation. \end{document}