Understanding OFDM – Part 3 – Refresh

So You Say You Want a Convolution

[intense_image image=”1125″ title=”User Bit Stream -2016″ alt=”User Bit Stream”]

Figure 12: Bits to Encode

In Part 2 of this series, we determined the maximum baud rate for 802.11a/g, and calculated the maximum channel data rates by modulation type. As an example, if using a BPSK modulation type we arrive at raw channel data rate of 12 Mbps, for an 802.11a/g channel. As a wireless LAN professional, you may be aware that the lowest data rate offered, in a pure OFDM 802.11a/g network, is 6 Mbps. In order to understand the difference between the raw channel rate and the actual available channel rate, we need to see the effect that the forward error correction (FEC) mechanism used with 802.11 OFDM technologies, has on the transmitted information stream.

Convolution Codes

Convolutional coding is the form of forward error correction (FEC) used with 802.11-based OFDM technologies. Forward error correction is a technique that allows the restoration of a transmission even if it has experienced minor corruption due to channel interference. Convolutional coding processes an outgoing bitstream by shifting the bits around, performing Boolean addition (1+1=0, etc.), and looping the results back in upon itself. The result of this “convoluted” process is a code that represents the original data bit, but is larger and more reliably restored if damaged in transit.

Methods of Representing the Convolution Coding State Machine

Convolutional coding performs logical mathematical operations to expand an input data stream with redundant bits prior to transmission. There are several forms of coding that may be used with 802.11 OFDM. These different types may take the form and be viewed in several different ways, including:

• Generator format
• Decision Tree format
• State format
• Trellis format

Each of these formats is a way of visualizing the encoding/decoding process used for a convolutional coding type. For this simplified explanation, I’ll use a Decision Tree format method because it affords a clear example of the decision states used during an 802.11a/g OFDM encoding and decoding sequence.

Overview

In the following example we will follow an input data bit stream as it is encoded using ½ rate convolution coding. With this level of coding every input data bit will be represented by two output bits. This pair of output bits is really a code that is used to represent the original bit. Transmitting a code pair instead of the original single bit requires twice as much bandwidth, but the advantage is that the coded pair is more reliable to restore by the receiver if errors occur during transmission. Since the pair of code bits requires twice the bandwidth as the single bit original, the use of ½ rate coding reduces the channel data rate by 50%.

In 802.11a/g, ½ rate convolution coding is dynamically selected by the transmitter for use under poor (noisy channel or weak signals) conditions. Under more favorable conditions, less robust coding options may be selected that have the advantage of better transfer speeds for the data at the expense of less error recovery protection. For example, 2/3 rate coding may be chosen when conditions are good. With 2/3 rate coding, every two input bits are represented by codes that are three bits in length. This coding level represents an error protection overhead of 33%. If the conditions are very good, ¾ rate coding may be selected by the transmitter. With ¾ rate coding 3 input data bits produce output codes that are four bits in length, which results in a 25% overhead for the error correction redundancy.

Visualizing Convolution Coding Operations

Many tutorials on convolution coding use the Polynomial Generator format to explain the coding process. A typical view of the Generator state machine looks like the image shown below.

[intense_image image=”1126″ title=”Polynomial Generator” alt=”Polynomial Generator”]

Figure 13: Convolutional Coding Polynomial Generator State Machine

But there are other ways to represent the convolutional coding process such as the Decision Tree method shown here.

Decision Tree Operations

A convolutional coding decision tree is a hard-coded matrix that pre-arranges all of the Boolean addition code possibilities into a step-by-step progression. Because the hard-coded decision trees can become very large and complicated, the following discussion will use only ½ rate coding, to keep the decision tree as compact as possible. Convolutional coding processes a small group of bits as a set. In this case, the groups will be four bits each, taken sequentially from the input data stream. In order to process these four bits, there will be four decision stops or gateways along the path through the tree. At each gate a decision must be made to change direction either up or down. Each choice determines which two bit code will represent the bit in question. These codes are pre-assigned at each decision gate level. Don’t be concerned if these codes do not appear to follow a logical order, since they are generated using Boolean logic, the meaning is understood at the machine level.

[intense_image image=”1127″ title=”Tx_Decision_Tree” alt=”Tx_Decision_Tree”]

Figure 14: Convolutional Encoder (Transmit) Decision Tree – ½ Rate

Encoding at the Transmitter

In the upcoming example, the data bits “1011” will be inserted into the tree from left to right, and will make directional choices based on the value of the bit being processed. If the bit carries a value of “0” then the decision will be to follow the path upward. If the bit is a “1”, then the decision will be to follow the trail downward. In the diagram shown as Figure 2, the red lines show the directions taken by “0” bit decisions and the blue lines show the paths taken when “1” bits are encoded.

Encoding the first data bit

Using the pattern “1011” as our four bit input group, the information bits will enter the coding machine in the order of left to right, with the leftmost “1” bit of the string being the first to be encoded. Since the first bit is a “1”, the decision at the first gate will be to travel downward since “1” bits force downward decisions (blue lines) and “0” bits direct the flow upwards (red lines). Therefore the “code” that will be used to represent this first bit will be found at the lower level of the first decision gate and happens to be “11”. That pattern will be stored and used as the first part of the output sequence when its time to send this code stream to the transmit modulator. Remember, that since the first decision made by the coding machine sent the direction of travel downward, all of the remaining bits in the set will also follow that path down past the first gate.

Encoding the second data bit

The second bit in the string “1011” is “0” and so that binary digit is next to enter the coding machine. It follows the previous path through the first decision gate, but at the second decision gate the path changes direction upward, since zero bits force the direction of travel to go up. The code for the upper level of second decision gate happens to be “10”, and so that will be the second coded pair stored as the output sequence.

Encoding the third data bit

The third bit in the string “1011” is a “1” bit. As the third bit follows the paths previously selected by the first and second bits of the set, it arrives at the third decision gate on the path. Once again, “1” bits force a decision to follow the path downward where the code for this level is “00”. Therefore, the third code in the output sequence will be “00”.

Encoding the fourth data bit

Finally, the fourth bit of the string “1011”, which is also a “1” takes the previous path through the decision tree to arrive at the fourth decision gate. Once again, following the previous logic, the choice is to go downward where the final code is found to be “01”.

Output Sequence to Transmit

With that final choice the decision process is complete and the output sequence to transmit will be “11 10 00 01”. That is the coded data stream that will be sent to the modulator and sequenced out various OFDM subcarriers as part of the transmitted OFDM waveform.

[intense_image image=”1128″ title=”Rx_Decision_Tree” alt=”Rx_Decision_Tree”]

Figure 15: Coded Sequence to Decode by Receiver

Decoding at the Receiver

Now that the output sequence has been transmitted, let’s say that during the transmission our waveform becomes partially disrupted as a result of noise in the channel. (Watch for Understanding OFDM – Part 4 for more details about noise and interference.) At the receiver, the “errored” OFDM waveform is translated as best as possible by the demodulator, which comes up with the bit pattern of “01 10 00 01”. As you can see, the pattern that was received, does NOT match the pattern that was transmitted, “11 10 00 01”. In this case, the first (leftmost) code pair has been received in error. Of course the receiver has no way of knowing that the received bit pattern is wrong. Fortunately, it doesn’t have to. The receiver does know that, ½ rate convolutional coding was used at the transmitter and so it prepares to decode the received code stream using the ½ rate error correction decision tree.

Decoding Overview

As you can see in Figure 3, the decoding and error correction procedure is similar to but slightly different from the encoding process described earlier. Instead of sending a single binary digit at a time, the received code pairs will be input into the decision tree, sequentially. Since the receiver has no way to determine when a correct decision has been made, it will need to treat every possibility with equal likelihood until a judgment call can be made based on the path that has the most matches.

Inserting the first code pair

Using the uncorrected code pattern of “01 10 00 01” as our input example, the first pair to be sent into the decision tree will be “01”. This pair will be split to follow both of the possible directions found at the first level of the decision tree. In this case, neither branch will result in a match, because this pair was received incorrectly from the air interface. So for this decision gate, a “match / no match” determination cannot be made.

Inserting the second code pair

The next pair of code bits from the pattern “01 10 00 01” is “10”. This pair is next to be sent into the decision tree and that pattern will be duplicated through every possible path up to the second decision gate. At this point a match is found between the input code pair and the code label assigned to the second gate up on the lower path. This hardcoded label is also“10”. Remember that the receiver has no way of knowing whether or not this match is correct, and so it stores the result but reserves judgment until all of the coded bit pairs have been processed.

Inserting the third code pair

The third bit pair from the pattern “01 10 00 01”, is “00”, and it is the next to be sent into the decision tree. Again it is duplicated over every possible path through to the third level decision gates. During this trial, two matches are found. One is located on the upper path at the third level and another can be found on the lower path, third level. Both of these code labels are set to “00”. But, which of these choices is correct? The decoding machine still doesn’t know and must continue its processing.

Inserting the fourth code pair

Finally, the fourth code pair of “01” from the uncorrected, received data stream of “01 10 00 01” is inserted into the decision tree. As before, this final pair is duplicated through every possibility up to the fourth and final decision gate. At this stage and in this example, four matches are found. There are two on the upper path and two on the lower path. These final four results are added to the previous matches and stored for the next part of the processing.

Calculating the score

Now comes the “best guess” part of the procedure. The convolutional decoder will compare all of the results and determine which of the paths contains the most matches. In this case the path with the most matches is the one that goes down, then up, then down, then down. The code result for that path is “11 10 00 01”, which just so happens to match the original code pattern sent by the transmitter.

This time it’s right

Finally, in order to translate the coded bit stream back into the original information stream (without the redundant coding material) the decoder maps the direction of travel to information bits by assigning a “0” to an upward decision and a “1” to a downward decision. In this case, the most likely correct path is down (assigns a “1”), up (assigns a “0”), down (assigns a “1”), and down (assigns a “1”) which results in a best guess of “1011”. In this case, that guess turns out to be correct.

But, what if it’s wrong?

Of course, in real life situations, many times those best guesses turn out to be wrong, especially in cases where more than one error exists in the received information. In that event, a final safety valve exists up at Layer 2, where the Frame Check Sequence (FCS) calculation is performed, using a 32-bit Cyclical Redundancy Check (CRC32). If the FCS value calculated by the receiver does not match the FCS result placed in the frame trailer by the transmitter, then the required Acknowledgement will be withheld forcing the information to be sent again.

[intense_image image=”1123″ title=”IandQ_v3″ alt=”IandQ_v3″]

Figure 16: Modulation Coding Schemes (MCS) Used in 802.11a/g

How does convolutional coding affect the channel data rate?

The use of ½ rate coding reduces the amount of user data by ½, so that in a 20 MHz channel with 48 usable subcarriers signaling at 12 megabaud, only 6 Mbps of actual user data can be transferred (12 Mbps x ½ = 6 Mbps). ½ rate coding is the least conducive to high throughput but the most resilient in the face of interference. Other coding rates allow for more of the transmitted bits to be used for user data but this comes at the expense of less error correction protection during transmission. For example, the use of ¾ rate coding in conjunction with BPSK modulation provides 9 Mbps of user data over an 802.11a/g connection (12 Mbps x ¾ rate coding = 9 Mbps). The table shown as Figure 4 lists the results of 802.11a/g modulation coding schemes when used within the 12 megabaud channel.

This episode of “Understanding OFDM” has illustrated how Convolution Codes are used to allow OFDM transmissions to recover from errors induced by the presence of noise or interference in the air. But, like me, you may be curious how that noise actually causes the coded bit patterns to be received incorrectly in the first place? The next part of this series will discuss how interference destructively affects our WLAN transmissions.

Summary of Part 3

• Large user data bitstreams are divided into smaller groups
• Each bit in a group or set is sent into the convolutional coding machine
• Using the decision tree format, each bit in the set follows the path of the previous bit
• Binary digit pairs are assigned as codes to each gate level on the decision tree
• All of the resulting code pairs are assigned as the output sequence to be transmitted
• At the receiver, each code pair is inserted into the error correction decision tree
• Each pair is sent over every possible path at each subsequent level
• The path with the most matches is assumed to be correct
• The sequence of “up” and “down” choices is translated into “1’s” and “0’s”
• The resulting string is assumed to represent the original user data information.
• ½ rate coding reduces the channel bandwidth by half
• 2/3 rate coding reduces the channel bandwidth by one-third
• ¾ rate coding reduces the channel bandwidth by one-quarter

 

Next “Understanding OFDM, Part 4 – RF Noise, the Sounds of Silence”