Design Note DN504 FEC Implementation By Robin Hoel Keywords • • • • • • 1 • • • • • • CC1100 CC1101 CC1110 CC1111 CC1150 CC2500 CC2510 CC2511 CC2550 FEC Viterbi Trellis Introduction This document gives an overview of the FEC implementation in the CC1100, CC1101, CC1110, CC1111, CC1150, CC2500, CC2510, CC2511, and CC2550. SWRA113A Page 1 of 11 Design Note DN504 Table of Contents KEYWORDS.............................................................................................................................. 1 1 INTRODUCTION............................................................................................................. 1 2 ABBREVIATIONS........................................................................................................... 2 3 WHAT IS FEC?............................................................................................................... 3 4 HOW IS FEC IMPLEMENTED? ..................................................................................... 3 5 HOW MANY BIT ERRORS CAN FEC CORRECT? ...................................................... 5 6 FEC IMPLEMENTATION................................................................................................ 8 7 GENERAL INFORMATION .......................................................................................... 11 7.1 DOCUMENT HISTORY................................................................................................ 11 2 Abbreviations FEC FSM Forward Error Coding Finite State Machine SWRA113A Page 2 of 11 Design Note DN504 3 What is FEC? Forward Error Correction (FEC) is a technique that allows the receiver to correct a certain amount of errors in the received message. This is achieved by letting a FEC encoder add redundancy to the data message at the transmitter according to certain prescribed rules. The FEC decoder at the receiver uses the knowledge of these rules to identify and, if possible, correct any errors that have appeared. Broadly speaking there are two main classes of FEC: linear block codes (BCH, Reed-Solomon, etc) and convolutional codes. An (n,k) linear block encoder takes k-bit block of message data and appends n-k redundant bits algebraically related to the k message bits, producing a n-bit code block. There are 2k valid code words, which is far less than the 2n possible code words, and a good linear block code is one in which the minimum distance dmin, the minimum number of bits that must be changed to go from any one code word to any other code word, is maximized. In order to be able to correct e erroneous bits we have that dmin > 2e, i.e. after e erroneous bits the correct code word is still the one with the smallest distance to the received code word. The dimensionless ratio r = k/n is called the code rate. A convolutional encoder is fundamentally a finite state machine with a k-bit input and n-bit output, n>k, and an internal M-bit memory. An important parameter of the convolutional encoder is its constraint length L = M + 1 which specifies over how many consecutive n-bit output periods a k-bit input value affects the output. The FSM is such that any given message sequence input results in a coded output sequence which maximizes the minimum distance to what would be generated for any other input message sequence. Convolutional decoding is usually performed by the Viterbi algorithm, which, conceptually, compares the received sequence to the encoded version of all possible encoder input sequences and keeps tab of how close of a match each is. Periodically, the Viterbi algorithm, tracks back through its memory and outputs part of the input sequence, which when encoded is the closest match to the received code sequence. 4 How is FEC Implemented? The CC1100/CC1101/CC1110/CC1111/CC1150/CC2500/CC2510/CC2511/CC2550 all have a rate r = 1/2 convolutional, non-recursive encoder with constraint length L = 4 (M = 3), implemented as shown in Figure 1. g1 output s2 s1 s0 -1 -1 -1 Z Z Z Input data i g0 output Figure 1. Implementation of Convolutional Encoder Each input bit is encoded into two output bits, thus doubling the amount of data that must be transmitted. If the same radio data rate is used, error-free reception with a lower signal strength is possible – thus effectively the range of the radio has been increased or the power consumption can be decreased for a fixed range. If the same raw data rate is required, the radio data rate must be doubled either by doubling the modulation rate or going from a 2-ary to a 4-ary modulation format. Obviously, this will increase the number of bit errors in the received coded sequence, but the error-correction in the decoder ensures that the decoded message sequence contains less erroneous bits than if the message sequence had been transmitted without coding. SWRA113A Page 3 of 11 Design Note DN504 Convolutional coding works best if the erroneous bits are evenly (or at least randomly) spaced throughout the received coded sequence. Unfortunately, due to the bursty nature of many radio interference sources and the characteristics of the demodulator, it is more likely that erroneous bits will clump together. To combat this problem, so-called interleaving of the coded data is performed after encoding in the transmitter and de-interleaving before decoding in the receiver. The purpose of interleaving is to make sure that adjacent symbols in the coded sequence are spaced out in the transmitted sequence, so that any clumps of bit errors in the received sequence are spread out more uniformly by the de-interleaver, letting the decoder work under optimum conditions. Our chips employ a 4x4 matrix interleaver with 2 bits (one encoder output symbol) per cell. Interleaver Write buffer Packet Engine Interleaver Read buffer FEC Encoder Modulator Interleaver Write buffer Interleaver Read buffer FEC Decoder Demodulator Packet Engine Figure 2. FEC and Interleaving The decoder in the chip implements a Viterbi algorithm that works on 8-bit soft-decision values from the demodulator. The Viterbi algorithm conceptually compares the received coded sequence with the encoded sequences resulting from encoding of all possible input message sequences, calculates a deviation value for each and then selects the most likely one (the one with the lowest deviation). A section of the so-called trellis shown in Figure 3 is useful in understanding how the Viterbi algorithm works. The circles at the left and right represent the possible values of the encoder state at any given time and the lines between them represent possible transitions from any one state to another. The numbers written along the transition lines are, the input bit to the encoder and the resulting output bits from the encoder, respectively. In practice, the Viterbi algorithm manages to explore all possible input sequences to the encoder by keeping track of only a finite number of paths through the trellis (corresponding to certain sequences of input bits). Specifically, the Viterbi algorithm only keeps track of the most probable of all paths that end in each of the 2M encoder states, and the accumulated deviation or cost of that path. For each input symbol, all possible encoder output symbols (00, 01, 10, and 11 in Figure 3) are compared against the received symbol and a transition cost is calculated. The appropriate transition cost is added to the accumulated path cost of each path that terminates in the source state on the left in the figure. It can be seen that there are two transitions into each destination state on the right in the figure. For each destination state the incoming transition with the lowest accumulated path cost is selected (the survivor path) and the other one thrown away – nothing is lost as all future paths that go through this state at this point in SWRA113A Page 4 of 11 Design Note DN504 the trellis would do the same selection. Thus the number of paths that the Viterbi Algorithm tracks is always constant and the optimal path is always one of them. i/g1g0 000 0/00 1/11 000 1 s2..0 0/ 1 001 0/01 1/1 0 1/ 010 0/1 1 0 1/ 0 011 00 010 10 011 1 1/ 0 0/ 1 /0 10 1 100 0/ 001 100 0 0/ 0 101 101 1/11 110 110 0/01 111 1/10 111 Figure 3. Trellis Diagram In order to provide the end of the transmitted data, which do not get the benefit of being evaluated over a full trellis path, with a protection equal to that of the rest of the transmitted data, so-called trellis termination is necessary. Terminating the trellis means to transmit extra data that brings the convolutional encoder to a known state (usually all zero) so that the decoder doesn’t need to make a decision on the most-probable trellis path with limited history. At the end of the transmitted data it is also necessary to fill up the last interleaver buffer with something so that a full interleaver block can be transmitted. Our FEC implementation appends “00001011b” to the data input to the encoder/interleaver when an odd number of data bytes are transmitted and “00001011 00001011 b” when an even num ber of data bytes are transmitted. The first three zeros of these sequences are used to terminate the trellis and the rest are used to fill up the last interleaver block. (The reason that not all zeros are transmitted is to ensure that there are some symbol transitions in the output of the interleaver to facilitate clock recovery.) 5 How Many Bit Errors Can FEC Correct? The convolutional code (optionally) employed in our chips has a maximum free distance of dfree= 6 bits. This means that changing any one bit in the message sequence will change at least 6 bits in the coded output sequence. Correspondingly, at least three erroneous bits are required in the received coded sequence before any other message sequence than the correct one is equally likely or more likely. SWRA113A Page 5 of 11 Design Note DN504 The ability to correct two bits in the entire coded sequence may not sound like much, but of course this is not the whole story. Normally, when there are no bit errors in the received sequence, the correct path through the trellis will have a much lower cost than all other possible paths and these alternative paths will thus quickly die out. This situation is illustrated in Figure 4 (for a different convolutional code than that employed in the CC11xx/CC25xx having fewer states for illustrative clarity): s1..0 00 01 i/g1g0 0/00 1/ 1 1 0/11 1/00 0/10 10 0 11 1/01 /01 1/10 Example trellis Example encoder 00 g1 output 01 s1 s0 Z-1 Z-1 Input data i 10 g0 output 11 Figure 4. Example Trellis and Example Encoder Figure 5. Trellis 1 The numbers above each state node is the cost in erroneous bits in the received sequence (this assumes a binary symmetric channel and hard decoding). It can be seen that most alternative paths quickly disappear since their cost become prohibitively high. If we introduce an error in the received sequence (input) as shown below we see that the cost of the alternative path(s) are much closer to the cost of the correct path and are thus longer-lived. Figure 6. Trellis 2 SWRA113A Page 6 of 11 Design Note DN504 If we were to introduce another bit error in the received sequence close to the first one, this effect would be even more pronounced: Figure 7. Trellis 3 We see that this time there exists an alternative path that originates in state 10 at the point of the first error (marked in green) which for time afterwards has the same (or even lower) cost as the correct path. The culled (non-surviving) transitions are also shown in black to illustrate at which point the correct path and the alternative path merge. The convolutional encoder employed in CCxx00 can tolerate one additional bit error in the received sequence for the lifespan of such an alternative path (from when the two paths split at the first bit error until they meet again at the same state sometime later). If a third bit error was to occur during this time, the alternative path instead of the optimum path might be the survivor path upon merge. We introduce a third error after the two paths merge to demonstrate the principle: Figure 8. Trellis 4 The exact life-span of each such alternative path is dependant on the input data and the state in which the alternative and correct paths split. As a rule of thumb one could say that they usually merge again within 3L (constraint lengths). The interleaver will help in distributing clumps of erroneous bits, which often occur in real-world received data, further part. Due to the inability to precisely predict how many erroneous bits can be corrected by a convolutional coder, the figure of merit usually associated with a convolutional code is its asymptotic coding gain, i.e. the reduction of the SNR of the received signal that yields an equivalent BER as the un-coded case. This can be used to increase range or decrease power in the transmitter. For a binary-input AWGN channel (relevant for 2-ary modulation formats on the CCxx00) the asymptotic coding gain is: ( ) G a = 10 log10 d free r dB , SWRA113A Page 7 of 11 Design Note DN504 where dfree is the free distance of the code and r is the code rate. The used code (dfree= 6, r = 1/2) has an asymptotic coding gain of 4.8 dB, although the achievable gain is considerable less for binary modulation formats (perhaps 2-3 dB). 6 FEC Implementation //-------------------------------------------------------------------------------UINT16 culCalcCRC(BYTE crcData, UINT16 crcReg) { UINT8 i; for (i = 0; i < 8; i++) { if (((crcReg & 0x8000) >> 8) ^ (crcData & 0x80)) crcReg = (crcReg << 1) ^ 0x8005; else crcReg = (crcReg << 1); crcData <<= 1; } return crcReg; }// culCalcCRC //-------------------------------------------------------------------------------// Variables UINT16 xdata fecEncodeTable[] = { 0, 3, 1, 2, 3, 0, 2, 1, 3, 0, 2, 1, 0, 3, 1, 2 }; UINT16 input[260]; UINT16 i, j, val, fecReg, fecOutput; UINT32 intOutput; UINT16 fec[520]; UINT16 interleaved[520]; UINT16 inputNum = 0, fecNum; UINT16 checksum; UINT16 length; //-------------------------------------------------------------------------------//Example code length = 3; input[0] = length; input[1] = 1; input[2] = 2; input[3] = 3; inputNum = length + 1; printf("Input: [%5d bytes]\n", inputNum); for (i = 0; i < inputNum; i++) printf("%02X%s", input[i], (i % 8 == 7) ? "\n" : (i % 2 == 1) ? " printf("\n\n"); " : " "); // Generate CRC checksum = 0xFFFF; //Init value for CRC calculation for(i = 0; i <= input[0]; i++) checksum = culCalcCRC(input[i], checksum); input[inputNum++] = checksum >> 8; // CRC1 input[inputNum++] = checksum & 0x00FF; // CRC0 printf("Appended CRC: [%5d bytes]\n", inputNum); for (i = 0; i < inputNum; i++) printf("%02X%s", input[i], (i % 8 == 7) ? "\n" : (i % 2 == 1) ? " printf("\n\n"); " : " "); // Append Trellis Terminator input[inputNum] = 0x0B; input[inputNum + 1] = 0x0B; fecNum = 2*((inputNum / 2) + 1); printf("Appended Trellis terminator: [%5d bytes]\n", fecNum); for (i = 0; i < fecNum; i++) printf("%02X%s", input[i], (i % 8 == 7) ? "\n" : (i % 2 == 1) ? " printf("\n\n"); SWRA113A " : " "); Page 8 of 11 Design Note DN504 // FEC encode fecReg = 0; for (i = 0; i < fecNum; i++) { fecReg = (fecReg & 0x700) | (input[i] & 0xFF); fecOutput = 0; for (j = 0; j < 8; j++) { fecOutput = (fecOutput << 2) | fecEncodeTable[fecReg >> 7]; fecReg = (fecReg << 1) & 0x7FF; } fec[i * 2] = fecOutput >> 8; fec[i * 2 + 1] = fecOutput & 0xFF; } printf("FEC encoder output: [%5d bytes]\n", fecNum * 2); for (i = 0; i < fecNum * 2; i++) printf("%02X%s", fec[i], (i % 16 == 15) ? "\n" : (i % 4 == 3) ? " printf("\n\n"); " : " "); // Perform interleaving for (i = 0; i < fecNum * 2; i += 4) { intOutput = 0; for (j = 0; j < 4*4; j++) intOutput = (intOutput << 2) | ((fec[i +(~j & 0x03)] >> (2 * ((j & 0x0C) >> 2))) & 0x03); interleaved[i] interleaved[i + 1] interleaved[i + 2] interleaved[i + 3] = = = = (intOutput (intOutput (intOutput (intOutput >> >> >> >> 24) 16) 8) 0) & & & & 0xFF; 0xFF; 0xFF; 0xFF; } printf("Interleaver output: [%5d bytes]\n", fecNum * 2); for (i = 0; i < fecNum * 2; i++) printf("%02X%s", interleaved[i], (i % 16 == 15) ? "\n" : (i % 4 == 3) ? " printf("\n\n"); " : " "); Running this code will give the following result (all data in hexadecimal base): Input: [ 4 bytes] 03 01 02 03 Appended CRC: [ 6 bytes] 03 01 02 03 30 3A Appended Trellis terminator: [ 03 01 02 03 30 3A 0B 0B 8 bytes] FEC encoder output: [ 16 bytes] 00 0E 8C 03 7C 0D F0 0E 82 8C 0E 5E F0 D1 8C D1 Interleaver output: [ 16 bytes] C8 3C 00 20 84 CF 33 31 A2 FC 40 4A 44 30 47 EF To test this FEC encoder program one can transmit its output data from one device (with FEC disabled) and recover the original input from a receiving device with FEC enabled. It is also possible to deliberately insert errors in the transmitted sequence to experiment with the error correcting abilities of the code. SWRA113A Page 9 of 11 Design Note DN504 For relevant register settings in TX and RX, see table 1 and table 2 respectively. Transmitter Comments PKTCTRL0.LENGTH_CONFIG = 0 Fixed Packet Length PKTCTRL0.CRC_EN = 0 Disable CRC MDMCFG1.FEC_EN = 0 Disable FEC PKTLEN = 0x10 Packet length = 16 TXFIFO = 0xC8, 0x3C, 0x00, 0x20 , 0x84, 0xCF, 0x33, 0x31, The output from the interleaver 0xA2, 0xFC, 0x40, 0x4A, 0x44, 0x30, 0x47, 0xEF Table 1. TX Settings Receiver Comments PKTCTRL0.LENGTH_CONFIG = 1 Variable Packet Length PKTCTRL0.CRC_EN = 1 Enable CRC MDMCFG1.FEC_EN = 1 Enable FEC RXFIFO = 0x03, 0x01, 0x02, 0x03 The received packet Table 2. RX Settings SWRA113A Page 10 of 11 Design Note DN504 7 7.1 General Information Document History Revision SWRA113A SWRA113 Date 2007.10.22 2006.07.31 Description/Changes Removed logo from header. Added CC1101 and CC1111 Initial release. SWRA113A Page 11 of 11 IMPORTANT NOTICE Texas Instruments Incorporated and its subsidiaries (TI) reserve the right to make corrections, modifications, enhancements, improvements, and other changes to its products and services at any time and to discontinue any product or service without notice. Customers should obtain the latest relevant information before placing orders and should verify that such information is current and complete. All products are sold subject to TI’s terms and conditions of sale supplied at the time of order acknowledgment. TI warrants performance of its hardware products to the specifications applicable at the time of sale in accordance with TI’s standard warranty. Testing and other quality control techniques are used to the extent TI deems necessary to support this warranty. Except where mandated by government requirements, testing of all parameters of each product is not necessarily performed. TI assumes no liability for applications assistance or customer product design. Customers are responsible for their products and applications using TI components. To minimize the risks associated with customer products and applications, customers should provide adequate design and operating safeguards. TI does not warrant or represent that any license, either express or implied, is granted under any TI patent right, copyright, mask work right, or other TI intellectual property right relating to any combination, machine, or process in which TI products or services are used. Information published by TI regarding third-party products or services does not constitute a license from TI to use such products or services or a warranty or endorsement thereof. Use of such information may require a license from a third party under the patents or other intellectual property of the third party, or a license from TI under the patents or other intellectual property of TI. Reproduction of TI information in TI data books or data sheets is permissible only if reproduction is without alteration and is accompanied by all associated warranties, conditions, limitations, and notices. Reproduction of this information with alteration is an unfair and deceptive business practice. TI is not responsible or liable for such altered documentation. Information of third parties may be subject to additional restrictions. Resale of TI products or services with statements different from or beyond the parameters stated by TI for that product or service voids all express and any implied warranties for the associated TI product or service and is an unfair and deceptive business practice. TI is not responsible or liable for any such statements. TI products are not authorized for use in safety-critical applications (such as life support) where a failure of the TI product would reasonably be expected to cause severe personal injury or death, unless officers of the parties have executed an agreement specifically governing such use. Buyers represent that they have all necessary expertise in the safety and regulatory ramifications of their applications, and acknowledge and agree that they are solely responsible for all legal, regulatory and safety-related requirements concerning their products and any use of TI products in such safety-critical applications, notwithstanding any applications-related information or support that may be provided by TI. Further, Buyers must fully indemnify TI and its representatives against any damages arising out of the use of TI products in such safety-critical applications. TI products are neither designed nor intended for use in military/aerospace applications or environments unless the TI products are specifically designated by TI as military-grade or "enhanced plastic." Only products designated by TI as military-grade meet military specifications. Buyers acknowledge and agree that any such use of TI products which TI has not designated as military-grade is solely at the Buyer's risk, and that they are solely responsible for compliance with all legal and regulatory requirements in connection with such use. TI products are neither designed nor intended for use in automotive applications or environments unless the specific TI products are designated by TI as compliant with ISO/TS 16949 requirements. Buyers acknowledge and agree that, if they use any non-designated products in automotive applications, TI will not be responsible for any failure to meet such requirements. Following are URLs where you can obtain information on other Texas Instruments products and application solutions: Products Applications Amplifiers amplifier.ti.com Audio www.ti.com/audio Data Converters dataconverter.ti.com Automotive www.ti.com/automotive DSP dsp.ti.com Broadband www.ti.com/broadband Interface interface.ti.com Digital Control www.ti.com/digitalcontrol Logic logic.ti.com Military www.ti.com/military Power Mgmt power.ti.com Optical Networking www.ti.com/opticalnetwork Microcontrollers microcontroller.ti.com Security www.ti.com/security RFID www.ti-rfid.com Telephony www.ti.com/telephony Low Power Wireless www.ti.com/lpw Video & Imaging www.ti.com/video Wireless www.ti.com/wireless Mailing Address: Texas Instruments, Post Office Box 655303, Dallas, Texas 75265 Copyright © 2007, Texas Instruments Incorporated