As on 21st October 2007, we moved from blogspot domain at  to the self hosted domain at http://www.dsplog.com. Over the last two years, the blog has grown quite a bit, and am reasonably happy with the progress. Let us look back at the positives and negatives over the last year.

The positives

Around the same time last year (i.e in October 2007), we had around 65+ posts and 300+ subscribers. As on today, we have

• 100 posts
• 2200+ subscribers and
• 2600+ comments

Some of the new topics which we discussed this year are

• MIMO
• Viterbi decoder

As traffic statistics, we have around*

• 40,000 page views per month
• 16,000 visits per month
• Average visit time of 3 minutes, 40 seconds

The top 5 countries based on the visitor location are*

• US
• India
• South Korea
• United Kingdom
• China

The top 5 articles are*

• Bit Error Probability for BPSK modulation
• BER for BPSK in Rayleigh channel
• Download free e-Book for error rates in AWGN
• Compare BPSK, QPSK, 16QAM, 16PSK, 64QAM etc
• Maximal Ratio Combining

* – based on Google Analytics data for September 2009

The negatives

My goal is to maintain around 4 posts per month, but over the last two months or so, it dropped to two posts or sometimes one posts per month. I will put efforts to improve on that aspect.

Feedback

I created a poll to collect your feedback on the aspect you like most in dspLog. You can chose any one from Articles/Matlab-C code/Comments/Web page template.

Note: RSS/email subscribers need to visit the site for participating and seeing the results from the poll.

Related posts:

1. Summary – feedback on [dspLog], July 2008
2. Happy Birthday – dspLog
3. Matlab or C for Viterbi Decoder?

The IEEE 802.11a specifications are used by many to understand a wireless communication link built using OFDM. In this post, I have put together a set of 10 multiple choice questions based on 802.11a specifications. The questions are on the building blocks in 802.11a specifications, preamble structure and so on. Upon completion of the quiz, you will be lead to a page showing the correct answers and their explanations.

Click here to download IEEE 802.11a specifications.

Note: The quiz might not be visible on RSS reader or over email. Please visit the site to access the quiz.

Good luck!

Related posts:

1. Frequency offset estimation using 802.11a short preamble
2. Cylcic prefix in Orthogonal Frequency Division Multiplexing
3. Trying out PAPR reduction for OFDM by multiplication with j

In previous posts, we have discussed convolutional codes with Viterbi decoding (hard decision, soft decision and with finite traceback). Let us know discuss a block coding scheme where a group of information bits is mapped into coded bits. Such codes are referred to as codes. We will restrict the discussion to Hamming codes, where 4 information bits are mapped into 7 coded bits. The performance with and without coding is compared using BPSK modulation in AWGN only scenario.

Hamming (7,4) codes

With a Hamming code, we have 4 information bits and we need to add 3 parity bits to form the 7 coded bits. The can be seven valid combinations of the three bit parity matrix (excluding the all zero combination) i.e. .

The coding operation can be denoted in matrix algebra as follows:

where,

is the message sequence of dimension ,

is the coding matrix of dimension ,

is the coded sequence of dimension .

Using the example provided in chapter eight (example 8.1-1) of Digital Communications by John Proakis , let the coding matrix be,

.

This matrix can be thought of as,

,

where,

is a identity matrix and

is a the parity check matrix.

Since an identity matrix, the first coded bits are identical to source message bits and the remaining bits form the parity check matrix.

This type of code matrix where the raw message bits are send as is is called systematic code.

Assuming that the message sequence is , then the coded output sequence is :

, where

,

,

.

The operator denotes exclusive-OR (XOR) operator.

Table: Coded output sequence for all possible input sequence

Hamming Decoding

Minimum distance

Hamming distance computes the number of differing positions when comparing two code words. For the coded output sequence listed in the table above, we can see that the minimum separation between a pair of code words is 3.

If an error of weight occurs, it is possible to transform one code word to another valid code word and the error cannot be detected. So, the number of errors which can be detected is .

To determine the error correction capability, let us visualize that we can have valid code words from possible values. If each code word is visualized as a sphere of radius , then the largest value of which does not result in overlap between the sphere is,

where,

is the the largest integer in .

Any code word that lies with in the sphere is decoded into the valid code word at the center of the sphere.

So the error correction capability of code with distance is .

In our example, as , we can correct up-to 1 error.

Parity Check Matrix

For any linear block code of dimension, there exists a dual code of dimension . Any code word is orthogonal to any row of the dual code. For the chosen coding matrix , the dual code is,

.

It can be seen that modulo-2 multiplication of the coding matrix with the transpose of the dual code matrix is all zeros i.e

.

This dual code is also known as parity check matrix.

Maximum Likelihood decoding

A simple method to perform maximum likelihood decoding is to compare the received coded sequence with all possible coded sequences, count the number of differences and choose the code word which has the minimum number of errors.

As stated in Chapter 8.1-5 of Digital Communications by John Proakis, a more efficient way (with identical performance) is to use the parity check matrix .

Let the system model be,

, where

is the received code word of dimension ,

is the raw message bits of dimension ,

is the raw message bits ,

is the error locations of dimension .

Multiplying the received code word with the parity check matrix,
.

The term is called the syndrome of the error pattern and is of dimension . As the term , the syndrome is affected only by the error sequence.

Lets assume that the message sequence

.

The code output sequence is

Let us find the error syndrome for all possible one bit error locations.

Table: Syndrome for all possible one bit error locations

Observations

1. If there are no errors (first row), the syndrome takes all zero values

2. For the one bit error, the syndrome takes one among the valid 7 non-zero values.

3. If we have more than one error locations, then also the syndrome will fall into one of the 8 valid syndrome sequence and hence cannot be corrected.

Simulation Model

The Matlab/Octave script performs the following

(a) Generate random binary sequence of 0’s and 1’s.

(b) Group them into four bits, add three parity bits and convert them to 7 coded bits using Hamming (7,4) systematic code

(c) Add White Gaussian Noise

(d) Perform hard decision decoding

(e) Compute the error syndrome for groups of 7 bits, correct the single bit errors

(f) Count the number of errors

(g) Repeat for multiple values of and plot the simulation results.

Click here to download Note: There is a file embedded within this post, please visit this post to download the file.

Figure: BER plot for Hamming (7,4) code with hard decision decoding in AWGN

Observations

1. For above 6dB, the Hamming (7,4) code starts showing improved bit error rate.

Reference

Digital Communications by John Proakis

Related posts:

1. Soft Input Viterbi decoder
2. Viterbi decoder
3. Viterbi with finite survivor state memory

While browsing through the web for materials on the wireless communication and implementation, found this rich set of articles as part of MIT OPEN COURSEWARE program. The course is from Vladimir Stojanovic, course materials for 6.973 Communication System Design, Spring 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology.

I quickly browsed through the articles. Most of the contents are heavy, and I guess suited for a practicing communication system design engineer. You may check out the material using the links given below. I have added some of the material to my study list. Wish me luck.

Course Description

This course presents a top-down approach to communications system design. The course will cover communication theory, algorithms and implementation architectures for essential blocks in modern physical-layer communication systems (coders and decoders, filters, multi-tone modulation, synchronization sub-systems). The course is hands-on, with a project component serving as a vehicle for study of different communication techniques, architectures and implementations. This year, the project is focused on WLAN transceivers. At the end of the course, students will have gone through the complete WLAN System-On-a-Chip design process, from communication theory, through algorithm and architecture all the way to the synthesized standard-cell RTL chip representation.

Topics

The course will focus on four major categories as outlined below:

1. Introduction to digital communications
   • Modulation and detection, vector channel representation
   • Equalization
   • Multi-channel systems (modulation methods, waterfiling, bit loading)
   • Practical examples including 802.11a
   • Coding – sequence detection, gap, convolutional and block codes
2. ASIC design fundamentals
   • ASIC design flow, tools, system-on-a-chip design issues
   • Micro-architectures and transformations (parallelism, pipelining, folding, time-multiplexing)
   • Hardware description languages: introduction to Bluespec™ and Verilog® review
3. Theory and building blocks
   • Fast fourier transform (theory, fast algorithms and VLSI implementations)
   • Convolutional and Trellis codes, and Viterbi algorithm (theory, algorithms and VLSI implementations)
   • Synchronization (phase and frequency tracking loops, algorithms and VLSI implementations)
   • Block codes (Hamming, BCH, Reed-Solomon), basic theory and VLSI implementations
4. Wireless channel fundamentals
   • Properties and modeling (fading, Doppler effect,…)
   • Channel estimation (theory and VLSI implementations)

Lecture Notes

Important links

Course Home

Syllabus

Reading list

Lecture Notes

Assignments

Exams

Download Course Materials

Reference

Vladimir Stojanovic, course materials for 6.973 Communication System Design, Spring 2006. MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology.

Related posts:

1. Example of Cascaded Integrator Comb filter in Matlab
2. Soft Input Viterbi decoder
3. Objective

Are you bothered by speed of the speed of the simulations which you develop in Matlab/Octave? I was not bothered much, till I ran into the Viterbi decoder. If you recall, the Matlab/Octave simulation script for BER computation with hard soft decision Viterbi algorithm provided in post Viterbi with finite survivor state memory took around 10 hours to run.

I knew C was much faster, so I coded the simulation again in C. Of Course, coding in C was much more difficult. I missed many functions (like conv(), rand(), randn() etc), the plotting capabilities and the statistical analysis capabilities of Matlab/Octave.

To have a graphical debug environment for C, I installed KDbg. I already had the gcc compiler installed, and I was all set to go. The C code, executed in 14 seconds !!!

home@home-desktop:$ gcc -g -lm script_ber_bpsk_convolutional_code_viterbi_decode.c
script_ber_bpsk_convolutional_code_viterbi_decode.c: In function ‘main’:
script_ber_bpsk_convolutional_code_viterbi_decode.c:54: warning: incompatible implicit declaration of built-in function ‘exp10’
home@home-desktop:$ date;./a.out; date
Fri Aug 21 05:35:09 IST 2009
|BER for BPSK in AWGN with hard/soft Viterbi decoder
|----------------------------------------------
|Eb/N0 | BER (sim) | BER (sim) | BER (theory) |
| (dB) | (hard)    | (soft)    | (uncoded)    |
|----------------------------------------------
|  0   | 0.198044  | 0.096864  | 0.078650     |
|  1   | 0.128787  | 0.045707  | 0.056282     |
|  2   | 0.072306  | 0.017853  | 0.037506     |
|  3   | 0.032038  | 0.005107  | 0.022878     |
|  4   | 0.011104  | 0.001269  | 0.012501     |
|  5   | 0.002886  | 0.000277  | 0.005954     |
|  6   | 0.000696  | 0.000054  | 0.002388     |
|  7   | 0.000100  | 0.000005  | 0.000773     |
|  8   | 0.000014  | 0.000000  | 0.000191     |
|  9   | 0.000000  | 0.000000  | 0.000034     |
Fri Aug 21 05:35:24 IST 2009
home@home-desktop:$

Please click here to download the C code for simulating BER for BPSK with convolutional coding with hard/soft decision Viterbi having finite survivor state memory.

Poll

I created a poll to collect your feedback on the choice of programming language. You can chose any two from Matlab/Octave/C/Scilab/Simulink/Others. If you chose “Others”, please specify some more details of the programming language in the Comments section.

Note: RSS/email subscribers need to visit the site for participating and seeing the results from the poll.

Related posts:

1. Soft Input Viterbi decoder
2. Viterbi decoder
3. Viterbi with finite survivor state memory

In this post, let us evaluate the impact of frequency offset resulting in Inter Carrier Interference (ICI) while receiving an OFDM modulated symbol. We will first discuss the OFDM transmission and reception, the effect of frequency offset and later we will define the loss of orthogonality and resulting signal to noise ratio (SNR) loss due to the presence of frequency offset. The analysis is accompanied by Matlab/Octave simulation scripts.

OFDM transmission

As discussed in the post on Understanding an OFDM transmission,  for sending an OFDM modulated symbol, we use multiple sinusoidals with frequency separation is used, where is the symbol period. The information to be send on each subcarrier is multiplied by the corresponding carrier and the sum of such modulated sinusoidals form the transmit signal. Mathematically, the transmit signal is,

The interpretation of the above equation is as follows:
(a) Each information signal multiplies the sinusoidal having frequency of .
(b) Sum of all such modulated sinusoidals are added and the resultant signal is sent out as .

OFDM reception

In an OFDM receiver, we will multiply the received signal with a bank of correlators and integrate over the period . The correlator to extract information send on subcarrier  is.

The integral,
,

where
takes values from till .

Frequency offset

In a typical wireless communication system, the signal to be transmitted is upconverted to a carrier frequency prior to transmission. The receiver is expected to tune to the same carrier frequency for down-converting the signal to baseband, prior to demodulation.

Figure: Up/down conversion

However, due to device impairments the carrier frequency of the receiver need not be same as the carrier frequency of the transmitter. When this happens, the received baseband signal, instead of being centered at DC (0MHz), will be centered at a frequency , where
.

The baseband representation is (ignoring noise),

, where

is the received signal

is the transmitted signal and

is the frequency offset.

Effect of frequency offset in OFDM receiver

Let us assume that the frequency offset is a fraction of subcarrier spacing i.e.
.

Also, for simplifying the equations, lets us assume that the transmitted symbols on all subcarriers, 

The received signal is,

.

The output of the correlator for sub-carrier is,

.

For  ,

The integral reduces to the OFDM receiver with no impairments case.

However for non zero values of , we can see that the amplitude of the correlation with subcarrier includes

• distortion due to frequency offset between actual frequency  and the desired frequency .
• distortion due to interference with other subcarriers with with desired frequency . This term is also known as Inter Carrier Interference (ICI).

Simulation Model

Click here to download the Matlab/Octave script for computing RMS error with frequency offset. The script performs the following:

1. Generates an OFDM symbol with all subcarriers modulated with .

2. Introduce frequency offset and add noise to result in =30dB.

3. Perform demodulation at the receiver.

4. Find the difference between the desired and actual constellation.

5. Compute the rms value of error across all subcarriers.

6. Repeat this for different values of frequency offset.

Figure: Error Magnitude vs frequency offset for OFDM

Observations

The theoretical results are computed by .

Quite likely the simulated results are slightly better than theoretical results because the simulated results are computed using average error for all subcarriers (and the subcarriers at the edge undergo lower distortion).

Related posts:

1. Frequency offset estimation using 802.11a short preamble
2. BPSK BER with OFDM modulation
3. Understanding an OFDM transmission

In the post on Viterbi decoder and soft input Viterbi decoder, we discussed a convolutional encoding scheme with rate 1/2, constraint length and having generator polynomial and having generator polynomial . If the number of uncoded bits is , then the number of coded bits at the output of the convolutional encoder is . Decoding the convolutionaly encoded bits by Viterbi algorithm consisted of the following steps.

1. For group of two bits, compute Hamming distance or Euclidean distance (for hard decision or soft decision respectively)

2. For each of the states, compute the path metric knowing the following.

• Each state can be reached from only two previous states (out of the 4 possible states).
• For each possible transition, compute the branch metric by adding the path metric of the previous state to the Hamming/Euclidean distance of the transition
• Select the branch metric which is minimum among the two values and store it as the path metric for the current state

3. Store the survivor predecessor state for each state.

4. Once we have processed received bits, we know that the convolution encoder has reached state 00. We start traceback from state 00, and given that we know the current and previous state, the input bits can be decoded.

However, when the number of input uncoded bits is large, the memory requirements for a survivor state matrix  of dimension becomes impossible to manage.

Traceback with finite survivor memory

To be able to decode with finite survivor memory, lets say we need to start the traceback at some time instant , where

is the decoding depth and

is the traceback depth.

The sequence of events are as follows:

• At time instant , we start the traceback and continue tracing back through the survivor path times. Once we are done with the traceback, we start estimating the decoded bits knowing the current state and previous state.
• Similarly, we again start the traceback at time , do traceback times and then decode bits from to .
• Once we reach the end of the input sequence at time instance , we know that trellis has converged to state00 and then we do demodulation with traceback.

Figure: Viterbi traceback with finite survivor memory

Given that traceback speed is equal to storing the speed incoming coded bits, we can implement the above algorithm with a memory of .

Note: The literature of different architectures for survivor state management is vast and is not explored in this post.

Selecting start state for traceback

At time instant , there are multiple ways to select the state to

• Always start from a defined state (for example state 00)
• Start from the state which has the minimum path metric

From simulations, can identify the minimum value of traceback depth (), which results in performance comparable to infinite survivor path memory case. From simulations shown in the post on hard decision Viterbi decoder, we know that at , results in a bit error rate of

Figure: BER vs traceback depth at Eb/N0 = 4dB

From simulations it has been observed that doing traceback  depth of around 15 ensures that the obtained BER with finite survivor state memory is close to the BER with infinite survivor state memory. Note that corresponds to around 5 times the constraint length of .

Additionally, as expected starting traceback with from the state with minimum pathmetric shows better performance than always starting at state 00.

Simulation results

Click here to download Matlab/Octave script for simulating bit error rate vs traceback for Eb/N0 = 4dB.

Click here to download Matlab/Octave script for simulating BER for BPSK with convolotional coding with hard/soft decision Viterbi decoding and with finite survivor state memory

Warning: This simulation took around 10hrs to complete. Am thinking that I will move to C code for simulations involving lots of for-loops.

Figure: BER for BPSK with convolutional coding with finite survivor state memory

Reference

Digital Communication: Third Edition, by John R. Barry, Edward A. Lee, David G. Messerschmitt

Digital Communications by John Proakis

Related posts:

1. Viterbi decoder
2. Matlab or C for Viterbi Decoder?
3. Soft Input Viterbi decoder