Essay title - CDMA Coding Technique
Code Division Multiple Access (CDMA) forms part of one of the emerging technologies in wireless communications nowadays. It is deployed in diverse fields, ranging from military use to commercial wireless communication. The CDMA is a digital spread spectrum technique which provides a highly efficient way of using radio waves to communicate because it allows multiple users to share radio frequencies at the same time without interfering with each other, in contrast to TDMA and FDMA systems. This project investigates the noise performance of a CDMA system using a Hybrid Rank-Based source coding scheme with different modulation techniques.
Source coding removes redundancy from the source message for effective transmission while channel coding adds redundancy to that message to make the signal more resistant to noise during transmission. The coding scheme which has been used is a combination of Shannon-Fano and Quaternary Huffman coding, with some dynamic characteristics. Convolutional channel coding scheme has been used due to its relative ease of simulation during coding and decoding which has been done using the Viterbi Algorithm. Source coding and channel coding are transformations which can seem to have conflicting roles, but both are essential in communication.
The modulation process transforms the channel coded bits into a form (usually electromagnetic waves for wireless communication) whereby it can be transmitted across a channel. Obviously, the modulation method chosen depends on the channel in use. For this project, different variations of phase shift-keying (PSK) have been used primarily and then the system performance has also been tested using Quadrature Amplitude Modulation (QAM).
The demodulation process is the reverse of the modulation process, where the received signal is converted back into binary form (usually voltage levels) to be sent to the channel decoder. A detector is associated with the demodulation process since the waveforms may be corrupted with noise and a decision has to be made to convert the signals back into streams of bits. Hard Decision Decoding (HDD) was used in the software for the simulations.
Introduction
FDMA and TDMA are two very useful multiple access schemes which have been very prominent in the development of radio communications, especially for commercial purposes. However, both these techniques have their limits. Indeed, for FDMA, the usable bandwidth is not infinite, while for TDMA, guard times limit the system capacity at high rates and though TDMA and FDMA systems are usually combined to maximize channel use, the system still inherits from their limitations. Therefore it is clear that the number of users cannot be indefinitely increased in both cases, new multiple access techniques need to be considered and CDMA systems have emerged to provide some respite to the communication sector . Though this technology is relatively new compared to FDMA and TDMA, and many further advances are yet to be made, it provides a useful alternative.
CDMA was first developed for military use during World War II, since transmission could be done over a wide bandwidth of frequencies, and therefore the enemy could not identify the signal easily. Nowadays, the use of CDMA has been extended to many communication and navigation systems, including Global Positioning System (GPS) and OmniTRACS satellite system for transportation logistics. It is also the basis to the 3G market since it enables significantly higher data rate compared to 2G, thus supporting additional features like global roaming, TV/video streaming, video conferencing etc…
CDMA is described as a spread spectrum modulation technique since the modulated coded signal has a much higher bandwidth than the data being communicated. As mentioned earlier, the transmission can occupy the whole bandwidth for simultaneous transmissions without interference or loss of data. This is achieved by making use of the orthogonal properties of vectors. Each transmitter is assigned a pseudorandom code, which is unique to it, and orthogonal to the codes assigned to the other transmitters using that channel. This pseudorandom code (Walsh codes have been used for this report) is used to transform the signal into a wideband spread spectrum signal.
1.1 General Communication System (GCS)
Let us first consider a generalized communication system to get a better idea of where CDMA comes into action.
1.1.1 The message
S0(t) represents the original message to be transmitted. This can be any text, image or multimedia file, but only text transmission has been considered for the works carried out in this project.
1.1.2 Source Coding
This is the process by which redundancy from the original message is removed in order to send the data more effectively. It usually encodes the information to be sent into binary form using one of the various source coding methods that have been developed before transmission.
1.1.3 Channel Coding
On the other hand, channel coding adds redundancy to the signal S1(t) from the source encoder. This is done to provide the system with some means of detecting and/or correcting the errors that may occur during transmission due to the presence of noise in the channel.
1.1.4 Modulation
This is the process that takes place in the modulator, where the signal from the channel encoder, which usually is in the binary format, is transformed into a form in which it can be transmitted over the channel.
1.1.5 Multiple Access
It is in this portion of the communication system that CDMA is called in action. The channel coded signal which is narrowband is first transformed into a wideband signal by making use of a spreading code such that it then enables simultaneous transmissions in the same channel. This wideband signal is then modulated before being transmitted. The multiple access part simply indicates that other messages from other sources interfere with the signal from the transmitter under study.
1.1.6 The channel
The channel is the medium through which the signal is to be sent. It is typically characterized by the noise associated with it, whether the Discrete Memoriless Model or Additive White Gaussian Noise Model is used and can be described using relatively simple Mathematical equations.
1.1.7 Receiver Side
The GCS is symmetric to some extent, since the reverse link on the receiver side simply performs the inverse of the transformations performed on the transmitter side. Demodulation is the complement of modulation, and yields back the channel coded data; the channel decoder and source decoder will be based on the channel encoding and source encoding technique used at the transmitter side.
1.2 Overview of report
Chapter 2 covers the source coding part of a GCS. Its role has been discussed as well as some of the desirable properties of source codes. Some existing source coding techniques have been studied and analyzed by calculating the Entropy, H(S) of the source and average length, resulting from the coding schemes.
Chapter 3 relates to the channel coding part of GCS. Its purpose has been explained and two major classes of structured sequences have been studied, namely block coding and convolutional coding. The operating principle of each has been discussed together with their fundamental differences.
Chapter 4 covers the bandpass modulation i.e. the various ways in which this can be carried out, with particular attention given to the schemes that have been used during the simulation process. The pros and cons of each method have also been mentioned and the parameters used to measure the performance of the techniques have also been included.
Chapter 5 is about the multiple access part of a GCS, more specifically about CDMA since the basis of the project stands on code division multiple access. The different alternatives of multiple access schemes have first been discussed followed by a study of the variants of CDMA. The advantages of CDMA over its counterparts have been included as well as its constraints.
Chapter 6 deals with the programming aspect of the project. The different technicalities of the software design part have been explained with respect to the theory parts that have been covered in the preceding chapters. The methods used for modeling the different parts of the communication system have been included.
Chapter 7 and Chapter 8 comprise the simulation results, subsequent to chapter 6. The graphs plotted for the different simulations and the conclusions drawn thereafter, and scope for future works has also been mentioned.
Source Coding
Source coding is the process by which data generated by a discrete source is represented efficiently. It involves removing redundancy from the original message in order to get it into a binary form whereby it can be transmitted by making use of error detection or error correction schemes.
This process can be carried out in various ways, using different techniques. However, a good knowledge of the statistics of the source is often desirable in order to develop an efficient source code. The frequency of occurrence of the source symbols may be used to develop an efficient coding scheme, where the most frequently occurring symbols are assigned shorter codewords while the rarely occurring symbols are assigned longer codewords (variable length coding).
2.1 Properties of codes
Two desirable properties of the source coding are that the codewords should be uniquely and instantaneously decodable. The first property means that for any given stream of bits, there is always only one possible stream of symbols that will be decoded. This is better illustrated in example 2.1 below.
Example 2.1
Symbol |
Binary Code |
A |
0 |
B |
1 |
C |
00 |
D |
01 |
E |
001 |
F |
011 |
Table 2.1 Example of non-uniquely decodable codes
Assuming that the symbol “e” is to be sent, the resulting stream of bits would be “001.”
During the decoding process, it can be observed that the stream can be interpreted in different ways, yielding different streams of symbols. For example, “aab”, “cb”, “ad” and “e” are the possible outcomes. Therefore this is not a good code since it is not uniquely decodable.
The second property (instantaneously decodable) means that as soon as a code is observed in the stream, it is decoded, i.e. there is no need to wait for the next symbol. Consider example 2.2 below.
Example 2.2
Symbol |
Binary Code |
A |
0 |
B |
01 |
C |
011 |
D |
0111 |
Table 2.2 Example of prefix codes
For the stream of bits “010011101”, the only possible outcome after decoding would be “badb” but each time a zero is encountered, the next bit has to be taken into consideration before decoding. This code therefore is uniquely, but not instantaneously decodable.
The prefix-free property is often desirable since it is enough to guarantee both the above properties. This property implies that no codeword can be the prefix of any other codeword. In fact, an instantaneously decodable code will automatically be uniquely decodable, but the inverse is not true.
Another desirable property of codes is the balance property, i.e. the number of zeros and ones in each codeword should differ by one atmost.
2.2 Entropy
In information theory, the Shannon entropy or information entropy is a measure of the uncertainty associated with a random variable. It quantifies the average information content in a message, usually in bits or bits/symbol. It is the minimum message length necessary to communicate information. “For a discrete memory-less source (DMC), the Markov model of text is often used to define the binary entropy is given by [1] “
H(S)= - (2.1)
where Pk is the probability of occurrence of the kth symbol from a set of K possible symbols.
2.3 Average Length
The average codeword length of a source coding scheme naturally depends on the number of different symbols occurring in the source. Consider a source that can produce K different symbols (i.e. S0,S1,S2,….,Sk-1). The average length can be calculated according to the equation given below.
= (2.1)
Where
: average number of bits per source symbol
Pk : probability of occurrence of Sk
Lk : length of binary sequence representing the symbol Sk
2.4 Shannon-Fano coding
Shannon-Fano is yet another variable length, prefix-free coding technique which is based on the symbols and their probabilities of occurrence but it has been superseded by Huffman coding since Shannon-Fano coding does not always produce optimal codes. The building of the coding tree is similar, but computationally simpler than building the Huffman coding tree. The following outlines can be used for building the Shannon-Fano codes.
- The symbols are sorted in descending order of occurrence, with the most common one at the top.
- The list is divided into two sets (or branches), such that the sum of the probabilities of each of the two sets is approximately equal.
- The symbols in the upper set are assigned value ‘1’ and those in the lower set are assigned value ‘0’. This means that the symbols from the upper set will start with binary digit ‘1’, and those from the lower set will start with value ‘0’.
- Steps (ii), and (iii) are repeated on each branch until each corresponding symbol has become a code leaf on the tree.
Example 2.3 below illustrates the building of a Shannon-Fano coding tree.
Example 2.3
Symbol |
Probability |
a |
0.2 |
b |
0.09 |
c |
0.12 |
d |
0.11 |
e |
0.48 |
Table 2.3 Example of probability distribution of a source (Shannon-Fano coding example)
The resulting code assignment is given in the following table.
Symbol |
Code |
a |
01 |
b |
0000 |
c |
001 |
d |
0001 |
e |
1 |
Table 2.4 Code assignment using Shannon-Fano coding
The entropy of the code:
H(S)= -
=(-) + (-) + (-) + (-) + (-) = 2.00 bits per symbol
The average length of the code:
=
= (0.481) + (0.22) + (0.123) + (0.114) + (0.094)
=2.04 bits per symbol
2.5 Huffman coding
The Huffman code was developed in 1952 by David A. Huffman. It is a prefix free code that is widely used as a compression technique in digital imaging and video. It is a variable length coding method which assigns shorter bit patterns to the most frequent characters and longer codewords to the less commonly occurring characters and this assignment operation is outlined below.
- “The symbols are rearranged in descending order of occurrence.
- The two symbols at the bottom, with the least probabilities are combined into a new symbol, with their probabilities added.
- For this symbol, the lower branch is assigned a value ’1’ while the upper branch is assigned value ‘0’.
- Steps (i),(ii) and (iii) are repeated until all characters have been combined to form a single symbol, with a probability of one [2].”
Note: in case two probabilities on 2 branches are the same, by default, take the upper branch as ‘1’ and lower one as ‘0’.
Below in an example of how the Huffman tree is built.
Example 2.4
Symbol |
Probability |
A |
0.2 |
B |
0.09 |
C |
0.12 |
D |
0.11 |
E |
0.48 |
Table 2.5 Probability distribution of a source (Huffman coding example)
The resulting code assignment is given in the following table.
Symbol |
Code |
A |
000 |
B |
011 |
C |
001 |
D |
010 |
E |
1 |
Table 2.6 Code assignment by Huffman coding
The entropy of the code:
H(S)= -
=(-) + (-) + (-) + (-) + (-) = 2.00 bits per symbol
The average length of the code:
=
= (0.481) + (0.23) + (0.123) + (0.113) + (0.093)
=2.04 bits per symbol
2.6 Quaternary Huffman Coding
“Quaternary Huffman coding is simply an extension of the Binary Huffman coding technique studied above, but it can yield better results for the case where the symbol probabilities are very close [3].” The following example illustrates this method. The symbols are grouped into sets of four instead of two like in Binary Huffman encoding, and the list is sorted out again after each branch code assignment. Consider example 2.5.
Example 2.5
Symbols |
Probability |
a |
0.15 |
b |
0.05 |
c |
0.3 |
d |
0.2 |
e |
0.15 |
f |
0.05 |
g |
0.1 |
Table 2.7 Probability distribution of source (Quaternary Huffman Coding example)
The code assignment is given in the table below.
Symbol |
Code |
A |
1010 |
B |
1001 |
C |
00 |
D |
01 |
E |
11 |
F |
1011 |
G |
1000 |
Table 2.8 Code assignment using Quaternary Huffman Coding
The entropy of the code:
H(S)= -
=(-) + (-) + (-) + (-) +
(-) = 2.57 bits per symbol
The average length of the code:
=
= (0.32) + (0.22) + (0.152) + (0.154) + (0.14) + (20.054)
=2.7 bits per symbol
2.7 Dynamic Huffman Coding
The Huffman coding algorithm developed by D.A. Huffman is in fact a two-pass algorithm in which the system first has to go through the message to count the frequency of occurrence of the each symbol before building the Huffman tree which it then transmits to the receiver. Then it goes through the data a second time to encode and send the actual message. “This causes a delay in the system so a one-pass scheme was proposed by Faller and Gallager, which was later improved by Knuth [4].” In this method, each new symbol sent is taken into consideration. The Huffman tree is rebuilt both at the transmitter and receiver side each time a symbol is sent. In fact, the tree used to send the (k+1)th character depends on the previous k symbols that were sent. This may considerably reduce the bandwidth required since the Huffman tree need not be sent for each new message.
2.8 Hybrid Rank-Based Coding Scheme
In this project, the source coding scheme that has been used will be based on a combination of static quaternary Huffman coding and Shannon-Fano coding, firstly for simplicity and secondly because it is essential that the codewords used in the scheme remain the same to facilitate the sending of the control information for the rebuilding of the coding tree at the receiver side.
Firstly, like in the case of Shannon Fano coding, the symbols are sorted only once in descending order of occurrence, unlike Huffman coding, where the rearrangement is performed after the code assignment for each branch. Secondly, instead of modifying one bit at a time, the symbols are grouped into sets of four, with the lengths differing by two bits mostly.
In fact the coding trees will be pre-built at both the transmitter and receiver side and do not actually change, but it is only the symbol assignment to each code that varies with each message. Each time a message is to be transmitted, the frequency of occurrence of each symbol in that message is counted. The symbols are then rearranged in descending order, i.e. the most common symbol is assigned the shortest code. This is better explained in example 2.6 given below.
The initial code assignment will be as follows:
After rearranging the symbols in descending order, the new coding tree will be as shown below.
The entropy of the code:
H(S)= -
=(-) + (-) + (-) + (-) +
(-) = 2.57 bits per symbol
The average length of the code:
=
= (0.32) + (0.22) + (0.152) + (0.154) + (0.14) + (0.054) + (0.055)
=2.75 bits per symbol
Now suppose each symbol is assigned a rank beforehand as follows:
Symbol |
Code |
A |
000 |
B |
001 |
C |
010 |
D |
011 |
E |
100 |
F |
101 |
G |
110 |
Table 2.10 Ranks assigned to each symbol
Before the actual message is transmitted, a block of control information is sent, containing the necessary data to rebuild the hybrid coding tree at the receiver side. This control information would consist of the ranks, sent in the order in which the symbols occur in the coding tree with the most common symbol rank sent first.
Thus the control information would be “010 011 000 100 110 001 101”.
At the receiver side, the order in which these ranks are received are used to rebuild the coding tree.
It can be argued that for the transmission of short messages (e.g. “cd”), the scheme might not be very efficient since, in the worst case, even if the reassignment were not carried out, the transmission would only be 6 bits long. Therefore it might seem pointless to transmit 21 bits of control information in addition to the 4 bits of the actual message that would be sent. However, for long transmissions (provided the symbols occur randomly), the scheme starts to serve its purpose, since the code reassignment will reduce the number of bits that would otherwise have needed to be sent.
An important note on this scheme would be that the key to the correct functioning of the system would hugely depend on the error free reception of the control information, since if there is an error in rebuilding this coding tree, the message will be irretrievably garbled in any case, even if there were no error in the message itself.
Two alternatives might be considered in order to increase the probability of the correct reception and decoding of the control information. Either a separate channel could be used to transmit this information (this could also act as a means of security as well), or a more powerful channel coding technique than that used for the data might be used. During simulations, however, for simplicity, none of these two have been used, and moreover, it also served as a means of stress testing the system, to see if the control information could still be retrieved correctly.
Channel Coding
The task of source coding is to remove redundancy from the source information to represent it with the minimum of symbols. When the coded data is sent over the channel however, it will be corrupted by noise, which will inevitably lead to errors. The task of channel coding therefore is to add structured redundancy (hence the alternative name of structured sequences) into the code in order to provide some mechanism for detecting and even correcting errors, thus reducing the likelihood of incorrect decoding of the message.
There are three major categories of channel coding schemes namely block coding, convolutional coding and turbo coding. The first two named above have been discussed in the report in an attempt to compare the two schemes. Due to time constraint, turbo coding was not studied for the purpose of this project.
3.1 Block Codes
Block codes are usually characterized by the (n, k) notation. The message is grouped into blocks of k bits, which are then mapped onto n-bit channel input sequences, the code rate being given by k/n. Each k-bit block has a unique n-bit codeword, and the successive blocks have no inter-relation, meaning that no memory is required.
For Binary codes, k-bit blocks form 2k distinct message sequences (referred to as k-tuples), and n-bit blocks can form 2n distinct sequences (n-tuples). Each k-tuple is uniquely matched onto an n-tuple, thus forming part of a set of 2k n-tuples. “In the case of linear codes, the mapping will be linear. The set of all 2n binary n-tuples over the binary element of 2 elements (0, 1) is called a vector space, Vn. Multiplication and modulo-2 addition will yield a vector that is in the same set of two elements. The set of n-tuples comprising the set of possible codewords in fact form a subset of the vector space Vn. This subset, S is called a subspace, if it satisfies the following two conditions [1].”
- The all-zero vector is in the subset, S.
Vi= (0,0,0,…..,0); ViS
- The sum of any two vectors in S is also in S (known as the closure property) i.e. no vector outside S can result from the modulo-2 addition of any two vectors from S. This is what characterizes linear block codes.
Vi S; Vj S;
(ViVj) S
For small values of k, a simple look-up table could be implemented, where the data is processed in n-bits blocks at a time, compared in the look up table for decoding. For large values of k, however, the use of a look-up table becomes impractical. It is often better to generate the codewords as needed.
Since the set of code vectors that form a linear block code is a k-dimensional subspace of the n-dimensional binary vector space, it is always possible to find a set of linearly independent n-tuples (V1,V2,….,Vk), called the basis of the subspace, fewer than 2k, that can span the subspace, i.e. each codeword can be represented as a linear combination of the basis. These vectors, when rearranged in matrix form, are used to define a (kn) generator matrix G.
G = (3.1)
The codeword (U) for any k-bit block (m) is generated by performing the dot product of the message vector with the generator matrix G.
U=mG(3.2)
Example 3.1
=
3.1.1 Systematic linear block codes
A (n,k) systematic linear block code processes k-bit blocks at a time to produce n-bit long codewords, with the particularity that the k-message bits are present, unchanged within the codeword, and the remaining (n-k) bits are parity bits. Systematic linear block codes have a generator matrix of the form
G= (3.3)
Where P is the parity array portion of the generator matrix and Ik is the kk identity matrix.
3.1.2 Decoding
Before studying the decoding part, a new matrix, the parity check matrix (H) needs to be defined. For each kn generator matrix, there is an ((n-k)n) parity check matrix defined as follows.
H= (3.4)
Where I(n-k) represents the (n-k) (n-k) identity matrix and PT represents the transpose of the parity matrix (P).
“G and H for a linear systematic block code are such that the rows of G are orthogonal to the rows of H [1].”
GHT=0(3.5)
where HT = (3.6)
3.1.3 Syndrome decoding
Suppose the vector U= (u1,u2,u3,….,un) is transmitted through the channel and the vector R=(r1,r2,r3,….,rn) is retrieved at the receiver end. R = U + e, where e is a vector representing the errors due to noise in the channel.
The syndrome, s is defined as
s=RHT (3.7)
Since
R = U + e (3.8)
s= RHT
= (U+e) HT
= UHT + eHT
=mGHT + eHT
But GHT = 0
Therefore
s = RHT = eHT(3.9)
For each codeword received, the syndrome is calculated. If s=0, then either there is no error or the error vector converts the codeword into another codeword, i.e. there is no detectable error. If s0, there is an error. In fact, there is a one to one correspondence between a correctable error vector and the syndrome.
The transmitted codeword U is recalculated using the syndrome according to the following equation.
U=s + R(3.10)
In fact, for the decoding, only the last k bits of the codeword ( for the case G= ) and the syndrome are used. “This is because for systematic linear block coding, the actual message bits can be read directly from the last k bits, the previous (n-k) bits being only parity bits [1].”
3.2 Convolutional Encoding
Convolutional encoding is yet another channel coding technique used to add controlled redundancy into the message signals. A convolutional code is normally characterized by the (n,k,m) notation, where
n: number of bits per code;
k: number of information bits sent at a time;
K: number of shift registers (memory space used).
Information bits enter the encoder k bits at a time to produce n-bit codewords (U), usually by means of some generator polynomials gi(x), and where
U={u1,u2,u3,…,un}(3.11)
K is the constraint length and it represents the number of k-bit shifts over which a single information bit can influence the encoder output. The code rate is still given by (k/n).
Example 3.2
One fundamental difference with the convolutional encoder compared to the linear block encoder is the presence of memory space since each new block sent depends not only on present block to be sent, but also the past values, hence the presence of shift registers. Another consequence of this mechanism is that the there is no 1-1 mapping of a k-tuple onto an n-tuple set.
3.2.1 The trellis diagram
“The trellis is an elegant way of representing the convolutional encoder operation. It shows how the state changes as the bits are encoded. Each branch of a trellis represents a state transition [5]”. Consider the case of a (2,1,2) encoder, with generator polynomials g1(x)=1+x+x2 and g2(x)=1+x2 . The table below shows the set of inputs, the state of the shift registers and the resulting codeword.
Input |
Present state |
Next state |
Output |
0 |
00 |
00 |
00 |
1 |
00 |
10 |
11 |
0 |
01 |
00 |
11 |
1 |
01 |
10 |
00 |
0 |
10 |
01 |
10 |
1 |
10 |
11 |
01 |
0 |
11 |
01 |
01 |
1 |
11 |
11 |
10 |
Table 3.1 List of all possible inputs and their corresponding outputs for Convolutional encoder example given above in Fig 3.1.
Since a convolutional encoder works on a principle similar to that of a finite state machine, and its operation can be illustrated by a state machine model.
The trellis diagram for the example is shown below.
For the decoding process, the Viterbi algorithm is used. The Hamming distance between the received bits and the bits corresponding to the state transition of each branch is calculated, such that there will be 8 Hamming distances computed. The Hamming distance is the number of bits by which 2 sequences differ. E.g. 11 and 00 have Hamming distance 2; 01 and 11 have Hamming distance 1.
“At each state, the Hamming distance between the output of each branch, and the received bits are computed, and cumulated with the distance obtained from the previous states. If two branches lead to the same state, the smaller distance is used for the calculation of the next cumulative error metrics. For the case of a state having the same error hamming distance leading to it from two different previous states, any one of the two might be taken, as long as there is consistency, i.e. if the upper branch is chosen, it should apply for all cases of equal branch error metrics. The final output would be obtained by going through the reverse direction of the trellis diagram, and following only the path with the lowest error metrics to reach the initial state [6].”
3.3 Channel Modeling
Signals transmitted in the channel are always likely to be affected by distortions and noise present in the channel. Distortions occur due to the different amount of attenuation and phase shifts suffered by each frequency components of the signal. “This can be corrected at the receiver end by the use of complementary equalizers [7].” The noise part however can only be minimized, but never eliminated completely. Noise is in fact one of the basic limiting factors of communications rate.
3.3.1 Discrete Memoriless Channel (DMC)
There are three well-known channel models that can be used. The Discrete Memory-less Channel (DMC), the Binary Symmetric Channel (BSC), and the Gaussian Channel. “The DMC model is characterized by a discrete input alphabet, a discrete output alphabet, and a set of conditional probabilities. For an M-ary input U, the conditional probability of a corresponding output alphabet Z is given by [1]”
P(Z|U)=P(zm|um)(3.12)
3.3.2 Binary Symmetric Channel (BSC)
“The BSC is a special case DMC where the input and output alphabet are binary and the conditional probabilities are symmetric [1].”
P(error)=P(0|1)=P(1|0)=p(3.13)
P(correct)=P(1|1)=P(0|0)=(1-p)(3.14)
3.3.3 Gaussian Channel Model (GCM)
The Gaussian Channel Model is an extension of the DMC model to the extent that the symbols output are not discrete. The noise follows a Gaussian distribution with mean zero and variance σ2. The conditional probability can be computed in the same way as for the DMC model, where
P(z|uk)= (3.15)
With the Gaussian model, there is the possibility of making performing either soft decision decoding or hard decision decoding. In hard decision decoding, the demodulator output consists of discrete elements, i.e. it makes a hard decision. Therefore a symbol error probability may be associated with it. This method is used for DMC and BSC models as well, since the demodulator output consists of discrete levels. Soft decision decoding can be performed using the Gaussian model. With soft decision, the output is in terms of quantization levels (>2) and it has a certain degree of uncertainty associated with it.
Modulation
Modulation is the process of transforming the symbols into a form that is compatible with the channel characteristics. For example, in radio communication, data which may be in the form of voltage levels are transformed into electromagnetic waves for effective transmission over the channel. In digital modulation, channel coded data is used to modulate a sinusoidal carrier wave by adjusting its frequency, phase, amplitude or a combination thereof. Different modulation schemes make use of these characteristics. The waveform sent may be expressed as
s(t)=A(t)cos[ω0t +φi(t)](4.1)
4.1 Frequency Shift Keying(FSK)
FSK is one of the most widely used modulation schemes due to its simple implementation. Essentially, FSK simply represents a symbol by a given frequency, i.e. for an M-ary modulation scheme, M different waves, each having a distinct frequency but same amplitude, will be assigned to the M different symbols. FSK however, has the disadvantage of having poor spectral efficiency, obviously due to the high bandwidth resources that it requires ( 4.1).
4.2 Amplitude Shift Keying (ASK)
In the case of ASK, the carrier amplitude is varied in accordance with the symbol, while keeping the phase and frequency constant. It should be noted, however that a negative voltage applied will result in a 180° phase shift. For example, a 4-ary modulation scheme may make the following assignments.
The carrier will be modulated as shown below in the diagram with each waveform representing a set of two bits.
ASK requires the use of linear power amplifiers since it is a linear modulation technique, and it is also very sensitive to noise and distortions from the channel. As such, its use is not suitable for wireless transmissions, but it can be used for transmission of digital data for optical fiber.
4.3 Phase Shift Keying ( PSK)
PSK, as its name suggests, relies on phase shifting the carrier to represent the different symbols, while attempting to keep the amplitude and frequency constant. It may be generally expressed in the form
Acos(ω0t+φi(t))
Where i = 0,1,…..,M and (M=2k)
The presence of rapid phase discontinuities in the signal means that the waveform may not be spectrally efficient. Therefore, some filtering may be required. Still, PSK is one of the most widespread modulation techniques, especially for wireless LAN standards, Bluetooth.
Most of the simulation works are based on PSK, so more careful study of PSK has been carried out for the purpose of this report.
4.3.1 Binary PSK (BPSK)
BPSK usually assigns binary 1 to the original carrier, and binary 0 to the carrier phase shifted by 180°. This is means that for BPSK, each symbol carries only 1 information bit, and hence it usually cannot be used for high speed data transmissions where bandwidth is limited. The advantage of BPSK over higher order PSK is that it has a lower symbol error probability, Psym.
4.3.2 Quadrature PSK (QPSK)
QPSK can be viewed as 2 BPSK signals in quadrature, i.e. two carriers, one phase shifted by 90°. In Euler representation, a QPSK signal may be expressed as
s(t)=Acos(ω0t) + jBsin(ω0t)(4.2)
QPSK makes use of four symbols (Fig 4.6b) to represent the set of two-bits. The points on the constellation diagram are equidistant from their adjacent points on the unit circle. Moreover, Gray coding is used, i.e. each adjacent point on the constellation diagram differs by only one bit. This is particularly useful for the theoretical calculations of the bit error probabilities (Pe) associated with QPSK for any given energy per bit to noise power spectral density ratio (Eb/No).
4.3.3 8-PSK/16-PSK
These simply are higher order PSK methods that increase the bits per symbol rate, with 8-PSK encoding 3 bits per symbol and 16-PSK encoding 4 bits at a time. The effect of this is a relatively increased spectral efficiency, however, with the adverse effect of increasing the Psym, since the decision interval between adjacent points on the constellation diagram (Fig 4.6c and Fig 4.6d) is reduced.
4.3.4 Bit error probability (Pe) / Symbol Error Probability (Psym)
The bit error probability is a useful parameter in determining the performance of a given modulation scheme. The bit error probability, as its name suggests, is the probability of a bit being in error in a symbol. For an M-PSK system, the probability of error in general is the probability that a signal is phase-shifted by more than α where α=360°/M. As can be seen from the constellation diagrams in Fig 4.5, as M is increased, the decision interval is reduced due to the points being more closely packed. As a result, there is an increase in the probability of error.
The bit error probability of a BPSK signal is given by
Pe=(4.3)
The symbol error probability is closely related to the bit error probability, since a bit in error automatically leads to an error in the corresponding symbol. For an M-PSK system, the following equation applies
Pe(4.4)
assuming Gray coding, and that a phase shift of more than (2×α) is highly improbable.
The below is a plot of typical values of symbol error probability to noise power spectral density ratio.
4.4 Quadrature Amplitude Modulation (QAM)
QAM is a hybrid scheme which combines phase and amplitude shift keying. It makes use of two carriers in quadrature with each other (90° phase shifted), like for QPSK and higher. In fact, the phase is modulated by varying the amplitudes of the two carriers which results in a phase shift in the transmitted waveform, sQAM(t). Below is the block diagram of a QAM system, followed by the constellation diagram of 16-QAM.
4.8 schematic representation of QAM modulator
QAM can usually be used to encode 2 or more bits (typical values being 4 bits for 16 QAM and 6 for 64 QAM) per symbol. QPSK can be viewed as a special case of QAM where the amplitude of the waveforms remains constant.
Code Division Multiple Access
The radio spectrum is a precious and scarce resource. It usage must be carefully planned and allocated in order to satisfy a maximum number of users. To maximize the use of this resource, several types of multiple access techniques are deployed.
- Frequency Division Multiple Access (FDMA)
- Time Division Multiple Access (TDMA)
- Space Division Multiple Access (SDMA)
- Code Division Multiple Access (CDMA)
These methods may be used separately or jointly by systems so as to optimize the bandwidth usage.
5.1 Frequency Division Multiple Access (FDMA)
FDMA systems divide the available bandwidth into specific portions, with each portion representing a channel which will be allocated to a specific user. This frequency will not be used by any other user for transmission. The constraint in FDMA systems is that the usable radio spectrum is not infinite; new users cannot be accommodated indefinitely.
5.2 Time Division Multiple Access (TDMA)
In TDMA systems, the user is allowed to use the whole bandwidth, but only for a time interval. The channel is divided into timeslots; each timeslot is periodically assigned to a specific user, during which no other user is allowed to transmit. TDMA is usually associated with FDMA, and therefore suffers from the same bandwidth limitation, though it provides an improvement over pure FDMA.
5.3 Space Division Multiple Access (SDMA)
For wireless SDMA systems, these take advantage of the fact that a signal transmitted in the atmosphere will get undergo fading as it moves away from the transmitting antenna since the energy density decreases (according to the inverse square law) and part of it will also be absorbed. For example, this is used for GSM systems, where there is frequency reuse by several base stations, i.e. different base stations serving the same network may use the same frequency ranges provided they are separated by a distance large enough to prevent co-channel interference.
5.4 Code Division Multiple Access (CDMA)
CDMA can be described as a spread spectrum modulation technique since the modulated coded signal has a much higher bandwidth than the data being communicated. “The transmission can occupy the whole bandwidth for simultaneous transmissions without interference or loss of data [8].” This is achieved by making use of the orthogonal properties of vectors. Each transmitter is assigned a pseudorandom code, which is unique to it, and orthogonal to the codes assigned to the other transmitters using that channel. This pseudorandom code is used to transform the signal into a wideband spread spectrum signal. At the receiver side, the signal can be demodulated using the same code as the transmitter has used to encode it. This also increases the security in the transmission since only the receiver using the right code will be able to demodulate the message.
5.4.1 Advantages of CDMA
- It can allow multiple access for very large number of users especially if combined with FDMA; only the code length has to be increased.
- “If the spreading codes have good auto correlation properties, then it can resist to multipath interference [8].”
- “CDMA has a good jamming resistance because the power spectral density of the signal is so low and resembles background noise, it is difficult to detect and jam on purpose. Therefore, CDMA communication systems are popular with the military [8].”
- CDMA also provides privacy, since to despread any given signal, the intruder must know the exact original spreading code used at the transmitter side.
There exist different types of CDMA techniques that are in use presently.
- Multi Carrier CDMA (MC-CDMA)
- Time Hopping CDMA (TH-CDMA)
- Frequency Hopping CDMA (FH-CDMA)
- Direct Sequence CDMA (DS-CDMA)
5.4.2 Multi Carrier CDMA (MC-CDMA)
MC-CDMA spreads the signal in the frequency domain. Each user symbol is transmitted simultaneously over multiple parallel, narrowband carriers, each phase shifted according to the code value.
5.4.3 Time Hopping CDMA (TH-CDMA)
TH-CDMA spreads the signal in the time domain, i.e. the user symbols are sent only at certain intervals of time (or timeslots) according to the spreading code of the user; the transmission is bursty. Each user is allowed to use the whole bandwidth but only during the time slots as determined by the code.
5.4.4 Frequency Hopping CDMA (FH-CDMA)
In FH-CDMA, the carrier frequency is varied according to the spreading code. The receiver can then use the same code to convert the signal back to the original one. It is worth noting that FH-CDMA uses only part of the bandwidth at a time, but the portion used varies with each spreading code.
5.4.5 Direct Sequence CDMA (DS-CDMA)
In DS-CDMA the baseband signal is transformed into a wideband signal by modulating it with a unique spreading code. Each user has a unique spreading code, referred to as the Walsh code, which is orthogonal to all other spreading codes of the other users of the system. At the receiver side, the signal received is demodulated using the same code vector as was used during the modulation process. The simulation works carried out are based on DS-CDMA so it will be more elaborately studied.
5.4.5.1 Walsh Codes
The spreading codes are can be generated using the Walsh-Hadamard Matrix as shown below.
Let
H1=[1](5.1)
Then
H2=(5.2)
= (5.3)
And
H3= (5.4)
Generally,
Hn=(5.5)
The Walsh-Hadamard Matrix shown above is a simple way of generating the orthogonal vectors required as spreading codes. Each row in the matrix is orthogonal to the remaining (n-1) rows.
Example 5.1
This example illustrates the fundamental principle of operation of DS-CDMA. Consider a system with two users assigned two spreading codes for transmission are to send messages data1= [0011] and data2= [1011] respectively.
(i) The code vectors would be derived, using the Walsh-Hadamard Matrix as:
H2=
- Sender1= [1 1]
- Sender2= [1 -1]
where 1 represents a binary ‘1’ and -1 represents a binary ‘0’.
(ii) Each transmitter then encodes its data with its code vector.
- Encode1= sender1.data1
=.
=
- Encode2= sender2.data2
=.
=
Note: The matrix is converted to a bit stream since the transmission is done serially. The bits are read column-wise, such that Encode2 would be read as [1 -1 -1 1 1 -1 1 -1].
(iii) The transmitted stream would be given by:
- Tx = Encode1 + Encode2
=
(iv) At the receiver side, the following correlation operation carried out on the received signal gives back the original message.
- Decode1 =Sender1. Tx
=.
=
=
- Decode2 =Sender2. Tx
=.
=
=
5.4.5.2 Power Control
One of the main features with DS-CDMA is that it requires power control. The power level at which the signals from different users arrive at the receiver may vary according to their relative distance mostly, and also due to the environmental conditions prevailing. Also, if due to the near far effect, users further from the receiver may not get their signals through due to the signals from transmitters closer to the receiver since their signals would arrive at the receiver with more power. Secondly, CDMA systems have a frequency reuse factor of 1. Therefore, sending too much power may cause interference with adjacent systems, unless SDMA is also applied. During simulations, the same power levels have been assumed to be received from all users, i.e. near-far effect has been neglected and also that no adjacent cell interference has been considered.
5.4.5.3 Synchronization
The issue of synchronization is also to be considered when dealing with CDMA. As shown in the example above, synchronization in CDMA is imperative since the waveforms will be orthogonal only if they are synchronized. Another class of pseudorandom codes called Gold codes can be used for non-orthogonal CDMA, whereby synchronization is less important. In practice, the synchronization is not easy to achieve due to asynchronous multipath interference, but for the purpose of simulations, it has been assumed that all systems are perfectly synchronized.
Software Design and Testing
The project is based on software simulation only since a hardware implementation would have been very time consuming as well as costly to realize. All programs have been written primarily in C/C++ programming language. Initially, each component has been designed and tested separately, according to the Bottom-Up approach. This way of proceeding is more suitable since it facilitates the integration of the different components to model the final system as a whole, rather than having to design a whole new system each time. It also facilitates the debugging process, since each prototype of the components can be removed or modified in case of malfunction. The graphs of symbol error probability against energy per bit to noise spectral density ratio (Eb/No) have been plotted using Matlab6.5.
6.1 Message
The message consists of the control information and a random text message, where each symbol forming part of the tree occurs at least once, to perform stress testing of the system. Each transmission is preceded by a starting bit sequence and is terminated by an ending character so that only the sent message is decoded, and noise that may be received in between transmissions is neglected.
6.2 Source coding
A two-pass algorithm has been used, where the program first goes through the message to count the frequency of each character occurring in the message in order to build the tree according to the Hybrid Rank-Based coding system explained in section 2.8 and then goes through it a second time to perform the source coding process.
The control information to rebuild the coding tree followed by the source-coded data is then transmitted on the same channel.
6.3 Channel Coding
Convolutional codes do not offer more protection against noise than an equivalent block code but they generally offer greater simplicity of implementation over a block code of equal power. A (rate=1/3,K=3) convolutional encoder has been used to add redundancy to the data to be sent, with generating polynomials:
- g1(x)=I+x2;
- g2(x)=I+x+x2;
- g3(x)=I;
The table below shows the set of all possible inputs and their corresponding outputs and states of the registers.
Input |
Present State (x,x2) |
Output (g1,g2,g3) |
Next State |
0 |
00 |
000 |
00 |
0 |
01 |
110 |
00 |
0 |
10 |
010 |
01 |
0 |
11 |
100 |
01 |
1 |
00 |
111 |
10 |
1 |
01 |
001 |
10 |
1 |
10 |
101 |
11 |
1 |
11 |
011 |
11 |
Table 6.1 Table for convolutional coding inputs and their corresponding outputs
6.4 Code Division Multiple Access
From the Walsh-Hadammard algorithm, a 64-bit Walsh code generator has been designed (i.e. a 64×64 matrix), with the rows representing the 64 different orthogonal vectors. For the simulation, the 64th code vector has been used to modulate the coded message, and the remaining 63 sequences have been used to modulate random messages which have been later added to the signal under study in the channel. For spreading the signal, no multiplication has actually been done like in the example 5.1. Instead, a simpler method has been adopted as shown.
To transmit a ‘1’, the Walsh sequence was sent and to transmit a ‘0’, the 1’s complement of the code was sent. This significantly reduces complexity of design of the program.
E.g. code vector [1 -1 1 1]
To transmit a ‘1’, [1 -1 1 1] is sent;
To transmit a ‘0’, i.e. [-1 1 -1 -1] is sent.
6.5 Modulation
The system has been tested using several digital modulation techniques namely BPSK, QPSK, 8PSK, 16PSK and 16-QAM. The amplitude of all the waveforms have been taken to be so as to normalize the energy per symbol to noise spectral density (Esym/No) because then, the energy per symbol for all the simulations can be taken as 1. This has been particularly simple for PSK since all waveforms for a given MPSK method then have the same amplitude (as in cos(ω0t+φi)), and hence have the same energy associated with it. However, for QAM, the computation has been slightly more complicated due to the fact that the amplitude also changes. The steps taken to normalize the waveforms are given in table 6.2 and table 6.3.
6.5.1 MPSK
M |
symbol |
rms value (symbol) |
Esym |
Eb |
rms value (bit) |
2 |
cos(ω0t+φi) |
1 |
1 |
1 |
1 |
4 |
cos(ω0t+φi) |
1 |
1 |
||
8 |
cos(ω0t+φi) |
1 |
1 |
||
16 |
cos(ω0t+φi) |
1 |
1 |
Table 6.2 Normalization table for PSK
6.5.2 16 QAM
The fact that amplitude of the symbols are not the same, unlike for MPSK implied that some further steps needed to be taken to validate the comparisons. Since the QAM constellation is symmetric about both axes, only the first quadrant has been considered for the computations as shown below.
Constellation point |
Symbol Amplitude (V) |
Average Energy per symbol (J) |
New amplitude values (V) |
(1,1) |
1 |
/ |
|
(1,3) |
5 |
||
(3,1) |
5 |
||
(3,3) |
3 |
9 |
3/ |
Table 6.3 Normalization table for 16 QAM
The average energy per symbol therefore is
= 5Joules/symbol(6.1)
Now, to make the average energy per symbol =1, each symbol amplitude has to be divided by as shown in the table above.
New average energy per symbol is equal to
= 1Joule/symbol(6.2)
Note: (1) The bit period (Tb) has been taken as 1 by default.
(2) The normalization process carried out has the effect of making the bit error probabilities equal for all the different MPSK.
For each modulation scheme used, the noise behavior is different. Referring to the constellation diagrams in Fig 4.6 and Fig 4.9, the distance between each point on the constellation diagram determines the resilience of the scheme to noise.
Where,
r is the distance from the origin to the constellation point.
α is the phase difference between two adjacent points.
d is the distance between two adjacent points.
From 6.3, it can be seen that
(6.3)
(6.4)
The rms (root mean square) value of d can be expressed as
(6.5)
The threshold value for cross-over to the adjacent symbol is therefore
(6.6)
The values of threshold calculated for each modulation scheme are tabulated below.
Modulation Scheme |
d |
dthreshold |
BPSK |
2 |
1.000 |
QPSK |
2 |
0.707 |
8PSK |
1.082 |
0.383 |
16PSK |
0.552 |
0.195 |
16QAM |
0.894 |
0.316 |
Table 6.4 dthreshold values for each modulation scheme
6.6 The channel
The channel is characterized by noise, and AWGN has been chosen to corrupt the signal. For each modulation technique simulated, the noise values have been diminished, keeping the symbol energy value constant when plotting the Psym against Eb/No graph.
The AWGN has been generated using the Box-Muller equation given below:
S= (6.7)
Where r1 and r2 are random numbers between 1 and 100
(Note: noise was added only to the signal under study and not in the channel for it to corrupt the other random messages as well since only the error performance of the system transmitting the original signal is required.)
6.7 Decoding
A coherent demodulator with hard decision decoding has been assumed and the signal has been de-spread before being sent to the channel decoder. The trellis decoder operation can be illustrated by the following state diagram model. The retrieved data is then used to rebuild the coding tree at the receiver side, before performing the source decoding.
Results
The system performance was to be tested under different noise conditions, for different modulation techniques {BPSK, QPSK, 8-PSK, 16-PSK & 16-QAM}. For each modulation scheme, the simulation has been done for different values of noise power. The program compares the values at the modulation stage with those at the demodulation/detection (i.e. after being subjected to AWGN) in order to calculate the symbol error probability (Psym) and the bit error probability (Pe). The third parameter, i.e. the energy per bit to noise spectral density (Eb/No) has been calculated for each simulation result and the results plotted on a graph as shown below. A second graph comparing the expected Pe against Eb/No with those obtained during simulations has also been plotted.
The above graph shows the plot for Psym against Eb/No. It can be observed that higher order MPSK schemes have higher symbol error probabilities for the same value of Eb/No. This is normal since when referring to the constellation diagrams in Fig 4.6 and Fig 4.9, the symbol error probability depends on the distance between each adjacent constellation point.
Comparing the values obtained to the theoretical graph in Fig 4.7, it is noted that the simulation results are slightly worse. This can be attributed to the fact that theoretical graphs make use of Gray coding, together with the assumption that a phase shift resulting in more than one bit error is highly improbable, while in practice this is not true.
It is interesting also to notice that 16QAM gives a better performance than 16PSK for the same energy per symbol value, and the same symbol content (i.e. 4 bits per symbol).
Following the reasoning of equation (4.4) in section 4.3.4,
Pe
the expected value of Pe has been calculated from the values of Psym obtained during simulations. It can be seen that the simulated results have a slightly worse performance than the expected values. This can again be explained by the fact that a symbol in error may actually comprise more than one bit in error.
Conclusion and Further Works
8.1 Conclusion
160 bits of overhead information have been sent in addition to the actual source coded data each time as control information to build the tree at the receiver side. Yet, simulation results have shown that the Hybrid Rank-Based coding scheme leads to an improvement compared to techniques using pre-defined coding trees since the coding scheme tree adapts itself to each new message. This technique can be most beneficial to a system sending data in blocks and/or having bursty traffic.
The excellent cross correlation properties of Walsh codes have been confirmed through simulations, since despite the noise and interference from other codes, the despreading (or decorrelation) has yielded back the original channel coded data in most cases. On some rare instants, when an error has occurred in the dispreading process, this error has been corrected during the Viterbi decoding stage such that at the source decoding step, the received corresponds exactly to the original source coded data.
The error performance graphs of the different modulation techniques which have been used for simulations have confirmed the theoretical part as far as the trend of the graphs is concerned, i.e. an increase in Eb/No led to a decrease in Psym. However, it has been noted that the graphs during simulations gave a slightly degraded performance when compared to the graphs derived in theory. This is because Gray Coding has been used, with the assumption that each symbol in error represents a bit in error and that phase shifts leading to more than one bit in error are highly improbable, when in practice, more than one bit in error may form part of the same symbol. This causes Psym to increase slightly as well as Pe.
The system as it has been designed in the project may not actually be implemented in practice. It is true that for the different blocks described in the Fig 1.1, only modification of their software is required, but for hardware implementation, certain assumptions made need to be satisfied first. Additional components for synchronization need to be integrated into the system, as well as a power control scheme for all receivers to be received with the same power. Moreover, in comparison to a system using the IS 95A (cdmaone) standard, for example, components like repeaters, scramblers, and interleavers have been omitted so obviously, certain changes need to be brought to the system before it can be deployed.
8.2 Further Works
A more realistic model of the system may need to be designed, with the missing components like repeaters, scramblers and interleavers also included in the system before its hardware implementation can be tested. Secondly, issues of power control and synchronization can be studied relative to the system to meet the assumptions made in this project. Thirdly, a method of carrying out cryptography on this system can be studied. For the source coding part, the system structure/protocols could also be modified to transmit control information about the symbols used in the message. This could reduce the size of the data to be sent since the actual program sends the information for all symbols. The simulations were run only for PSK and QAM. It could be extended to other higher order modulation schemes to compare the result obtained. Finally, this report dealt only with Walsh codes, but other alternatives like Gold codes or Kasami codes can also be considered.
Appendix A
Derivation of Bit Error Probability for a coherent BPSK demodulator
The two possible signals are the two symbols representing binary ‘1’ and binary ‘0’ respectively.
stx1(t)= Acos(ω0t)(A.1)
stx0(t)= Acos(ω0t+π)(A.2)
=-Acos(ω0t)(A.3)
At the receiver end, the signal picked up by the antenna would be the original transmitted signal plus some wideband noise.
si1(t)= Acosω0t +ni(t)(A.4)
si0(t)= -Acosω0t+ni(t)(A.5)
After passing through the filter, the noise is band-limited.
s2(t)= Acosω0t+no(t)(A.6)
where no(t)=x(t)cosω0t - y(t)sinω0t
Multiplying by the local carrier:
s3(t)=s2(t)2cos(ω0t)(A.7)
={Acosω0t+no(t)}2cosω0t
=2cos2ω0t[A+x(t)]- [2y(t)sinω0t]×[cosω0t]
Only the dc components of the signal pass through the lowpass filter.
The signal at the threshold detector is given as:
s5(t)=[ A+x](A.8)
The probability of an error occurring during detection (Pe) can hence be represented as:
(i) P[x>A] for the case of stx0(t)= -Acos(ω0t) OR
(ii) P[x<-A] for the case of stx1(t)= Acos(ω0t)
Complementary Error Function (erfc)
Noise has been modeled as following a random normal distribution in the project and the probability distribution function is given as shown in the diagram below.
Let noise be denoted by the random variable x. The probability density function, p(x) of the Gaussian distribution as described by the Box-Muller plot is given by
p(x)=exp
where μ is the represents the mean and σ represents the standard deviation of the distribution.
The probability that x lies between -a and +a can be calculated as follows.
P(-a<x<+a) = (A.9)
=(A.10)
Since the distribution is symmetric about the vertical axis, with mean zero, the formula may be simplified to
P(-a<x<+a) = (A.11)
Now using the substitution method, the formula can be modified as follows.
t = (A.12)
dt =
α=
P(-a<x<+a) =
P(-a<x<+a) = erf (A.13)
The error function (erf(a)) in fact gives the probability that the random variable, x lies between values -a and +a. The complementary error function can be calculated as given below.
erfc(α) = 1 - erf(α) (A.14)
= 1 - (A.15)
= (A.16)
The complementary error function gives the probability that the random variable, x falls in the range >+a or <-a.
Again using the symmetry of the distribution, the probability of x being greater than any given value A is given by
P(x>A) = P(x<-A)
P(x>A)= erfc (A.16)
Appendix B
Energy per bit to noise power spectral density ratio (Eb/No)
Signal to Noise Ratio (SNR) has been traditionally used to characterize signal waveforms, especially for analog communication. In digital communication, information is transmitted in the form of bits (which can be represented as specific voltage levels) in a given window of time. This implies that for each symbol transmitted, the corresponding amount of energy is finite, i.e. it is an energy signal.
(B.1)
A further implication is that the average signal power would be zero.
(B.2)
= = (B.3)
Energy is therefore viewed as a more suitable means to characterize a digital waveform, because it provides a good metric for “measuring” the signal waveform. Secondly, in digital communication, each waveform may carry a k-bit meaning, where k=1,2,3,…,K. Hence, to facilitate comparison among different systems, a certain normalization is required. The energy per bit provides this of merit, since it allows effective comparison to be carried out at the bit level among different systems.
References and Bibliography
[1]B. Sklar, “Digital Communications, Fundamentals and Application,” 2nd Edition, pp142-143, pp193-200, pp243-259, pp341-344, pp352-365, pp587-589
[2]http://www.si.umich.edu/Classes/540/Readings/Encoding%20-%20Huffman%20Coding.htm, Accessed Sept. 18, 2007
[3]J. S. Lee, “Principles of Applied Mathematics, Data Compression and its Applications,” MIT ID#: 950706586 / jsslee@MIT.EDU, Term Paper / December 13, 2006 ,pp2-8
[4]J. S. Vitter, “Design and Analysis of Dynamic Huffman Codes,” Brown University, Providence, Rhode Island, pp825-830
[5]http://www.tkt.cs.tut.fi/kurssit/8404171/Harjoitukset/K05/ohje/viterbi_intro.html, Accessed Jan. 20, 2008
[6]http://home.netcom.com/~chip.f/viterbi/algrthms2.html, Accessed Jan. 20, 2008
[7]B.P. Lathi, “Modern Digital and Analog Communication Systems,” 3rd Edition, pp337-340, pp611-616, pp652-656
[8]Juha Korhonen, “Introduction to 3G mobile communication,” 2nd Edition, pp25-47, pp101-108, pp112-118, pp123-125
[9]http://www.bearcave.com/misl/misl_tech/wavelets/hurst/random.html, Accessed Jan. 23, 2008
[10]M. Eroh, Ed., “Next Generation Mobile Systems, 3G and Beyond,” DoCoMo Communication Labs, USA pp60-64
[11]http://www.cs.ucl.ac.uk/staff/S.Bhatti/D51-notes/node15.html, Accessed Dec. 27, 2007
[12]http://adsabs.harvard.edu/abs/1994SPIE.2308.1636J, Accessed Sept. 20, 2007
[13]http://www.compressconsult.com/huffman/ Accessed Sept. 21, 2007
[14]www.cs.ucl.ac.uk/staff/S.Bhatti/D51-notes/node30.html, Accessed Dec. 23, 2007
[15]www.cs.ucl.ac.uk/staff/s.bhatti/D51-notes/node12.html, Accessed Nov. 17, 2007
[16]A. M. Chan, J. Feldman, R. Madyastha, P. Indyk and D. KargerLocal “decoding of Walsh Codes to reduce CDMA dispreading computation,”pp1-2
[17]http://www.umtsworld.com/technology/cdmabasics.htm, Accessed Jan. 17, 2008
[18]K. G. Paterson, “On Codes with Low Peak-to-Average Power Ratio for Multi-Code CDMA,” Member, IEEE pp1-4
[19]www.bee.net/mhendry/vrml/library/cdma/cdma.htm, Accessed Sept. 2, 2007
[20]Eric Lawrey, “The suitability of OFDM as a modulation technique for wireless telecommunications,” with a CDMA comparison, James Cook University, October 1997 pp19-26
[21]http://rice.ecs.soton.ac.uk/bjc97r/pnseq.old/node6.html, Accessed Jan. 15, 2008
[22]www.ece.mtu.edu/faculty/ztian/ee5900s/walsh.pdf, Accessed Aug. 30 , 2007
[23]http://www.ant.uni-bremen.de/whomes/rinas/dfsim/dfblocks/toolbox/ Communications/ ErrorRates/QAM/QAM_gray_vs_PSK_gray.disp.html, Accessed Feb. 10, 2004
[24]http://www.aero.org/publications/crosslink/winter2002/03_sidebar2.html, Accessed Dec. 3, 2008
[25]G. Bauch, P. Sethuraman and F. Schreckenbach, “Partially unique mappings bit interleaved coded modulation iterative detection” pp3-4
[26]G. Breed, “Bit Error Rate: Fundamental Concepts and Measurement Issues, High Frequency Electronics,” Copyright 2003 Summit TechnicalMedia, LLC, pp46-48
[27]J. L. Pinto and I. Darwazeh, “Phase Distortion and Error Vector Magnitude for 8-PSK Systems,” Department of Electrical Engineering and Electronics, University of Manchester Institute of Science and Technology (UMIST), Manchester M60 1QD, U.K, pp1-4
[28]J. Lassing, E. Str¨om, E. Agrell and T. Ottosson, “Computation of the Exact Bit Error Rate of Coherent M-ary PSK with Gray Code Bit Mapping,” pp1-3
[29]Geoff Smithson, “Introduction to digital modulation schemes,” pp2-8
[30]http://www.elec.mq.edu.au/~cl/files_pdf/elec321/lect_mask.pdf, Accessed Sept. 18, 2007
[31]L. Hanzo, W.T. Webb and T. Keller, “Single- and Multi-carrier Quadrature Amplitude Modulation: Principles and Applications for Personal Communications, WLANs and Broadcasting” pp2-10
[32]Mooi Choo Chuah, Qinqing and Zhang, “Design and performance of 3G wireless networks and wireless LANs,” Lehigh University, Bell Laboratories, Lucent technologies
pp2-10
[33]http://www.ics.uci.edu/~dan/pubs/DC-Sec3.html, Accessed Sept. 22, 2007
[34]Samuel C. Yang , “3G CDMA2000 Wireless System Engineering” pp32-34
