Background Information In some communication systems, data to be transmitted is encoded before transmission to provide symbols that are transmitted to a receiver. The receiver receives the symbols and decodes the symbols to recover the transmitted data.

However, errors may be introduced during the transmission of the data through the channel. For example, the introduced errors may be completely random errors, bursts of errors, or periodic bursts of errors.

Error correction methods can be employed to allow for error detection and correction. Typically, these error correction systems send redundant parity information along with the message so that the receiver can use the parity information to detect and correct received errors. For example, forward-error- correction (FEC) techniques can be used to detect and correct received errors. Block codes such as Reed-Solomon (RS) or Bose-Chaudhuri-Hocquenghem (BCH) codes are one type of FEC technique that is commonly used for their flexibility and suitability for many applications. However, block-coded FEC techniques typically do not work well with long bursts of errors.

One conventional solution to correct long error bursts is to use interleaving techniques. FIGURE 1 illustrates a typical conventional interleaving error correction system 10. System 10 includes an encoder 11, an interleaver 12, a transmitter 13, a channel 14, a receiver 15, a de-interleaver 16, and a decoder 17. Encoder 11 receives data to be transmitted and encodes the data according to the error correction system being used (e. g., RS, BCH). In this example, in response to the data, encoder 11 outputs a stream of data and parity symbols, with every n symbols forming a code word. Interleaver 12 receives the data and parity symbols from encoder 11 and fills a table called an interleave table. Typically, the interleaver 12 fills the interleave table on a row-by-row basis, with a row containing n symbols (i. e., the interleave table has n columns). Thus, each row represents a code word.

After the interleave table is filled, interleaver 12 provides the symbols to transmitter 13 on a column-by-column basis. Transmitter 13 then transmits the code words to receiver 15 through channel 14. In a wireless system, channel 14 represents the atmosphere through which the radio frequency (RF) signals propagate.

Deinterleaver 16 then receives the received symbols from receiver 15. In particular, deinterleaver 16 fills a table called a deinterleave table on a column-by-column basis so that the symbols in the deinterleave table are in the same places as in the interleave table. De-interleaver 16 then provides the symbols to decoder 17 on a row-by-row basis. Thus, every n symbols received by decoder 17 forms a codeword. Decoder 17 then decodes the code words to extract the transmitted data.

FIGURE 2 illustrates how interleaver 12 and de-interleaver 16 operate. As can be seen in FIGURE 2, an interleave table 21 is filled with symbols Sj through ( ?, n). The first row contains symbols S1 through Sn, the second row contains symbols Sn+l through S2n, and so on. Therefore, the first column contains symbols Sl, Sn+lf S2n+l S (x l) n+l Similarly, the second column contains symbols S2, Sn+2 ! S2n+2 and S (R.-l) n+2 and so on. In an interleave system, rather than transmit the symbols on a row-by-row basis, the symbols are transmitted on a column-by-column basis. Thus, symbols SI, Sn+l, S2n+l... S (. n+l are transmitted first, as indicated by arrow 231. Then symbols S2, Sn+2 S2n+2... and S ( ?,-I) n+2 are transmitted, as indicated by arrow 232 and so on through the symbols in the nth column (i. e., symbols Sn, S2n, S3n... and S ?, n) as indicated by arrow 23n. Table 1 below defines the order that symbols are read out of the interleave table (i. e., an index table). 1 1+R 1+2k l + (n-l) R 22+2+22+ (n-l) k 2R 3R... nk

TABLE 1 Deinterleaver 16 then fills the deinterleave table on a column-by-column basis. Thus, the first X symbols received are Si, Sn+l, S2n+... Sa.)) n+], which are filled in the first column of the deinterleave table. Next, symbols S2, Sn+2, S2n+2 and S + are filled in the second column of the deinterleave table, and so on through the symbols in the nth column (i. e., symbols Sn, S2n, S3n... and Ski)- FIGURE 3 illustrates how deinterleaver 16 provides the received symbols to decoder 17. As can be seen, deinterleaver 16 first provides the symbols in the first row of the deinterleave table as indicated by arrow 31 l. Thus, decoder 17 receives symbols, Sl through Sn, which form the first code word. Then, deinterleaver 16 provides the second row of the deinterleave table to the decoder 17 as indicated by arrow 312 and so on through the symbols of the . th row as indicated by arrow 31v,.

This technique, in effect, serves to spread burst errors in time. In particular, if a burst error were to occur during the transmission of two or more consecutive symbols, these errors do not occur in the same code word. For example, say that these consecutive symbols are symbols SI, Sn+l and S2n+1. As can be seen in the deinterleave table of FIGURE 3, the error of symbol S, appears in the first code word, the error in symbol Sn+l appears in the second code word, and the error in symbol S2n+1 appears in the third code word. Thus, in effect, decoder 17 is able to treat burst errors as if they were random errors in three separate code words rather than a burst error in a single code word. That is, interleaving serves to separate successive errors in time, thereby allowing the decoder to treat burst errors as random errors that can be corrected using standard FEC techniques.

Although conventional interleaving techniques are useful in correcting error bursts, such techniques may not be able to correct errors that occur periodically.

Such periodic errors are known to occur in wireless simulcast (simultaneous broadcast) systems, where periodic errors can occur due to frequency offsets between transmitters. That is, if the period of the periodic errors is a harmonic of the interleave degree, then erroneous symbols could appear in the same code word. For

example, if the period of the periodic errors is 2k, then every 2Xth transmitted symbol could have an error. Because the symbols are transmitted column-wise, errors could be incurred with the reception of symbols SI, S3, S5 and so on, which are all in the first code word. With a sufficient number of erroneous symbols, the errors may be uncorrectable. Accordingly, what is needed is an error correction technique that can correct random errors, burst errors, and periodic errors.

Summary In accordance with the present invention, an error correction system that can correct random, burst, and periodic errors is provided. In one aspect of the present invention, the error correction system includes a mixed order interleaver and a mixed order deinterleaver configured to implement a novel FEC block interleave algorithm.

The system also includes one or more transmitters, a receiver, an FEC encoder, and a corresponding FEC decoder. The interleave algorithm is similar to the conventional FEC block interleave algorithm, except that the order of the symbols transmitted within a column is not sequential. Rather, the symbol order within a column transmission is mixed in a deterministic manner so that the occurrence of uncorrectable periodic errors is significantly reduced. In accordance with this aspect of the present invention, the mixed order deinterleaver is configured to fill the deinterleave table in the inverse deterministic mixed order. Thus, the mixed order deinterleaver places the received symbols in the proper order for each column of the deinterleave table. The symbols are then extracted from the deinterleave table in a row-wise manner. Consequently, the extracted symbols reform the code words that were generated by the encoder and loaded into the interleave table. Because the order of symbols within each column transmission is mixed, the likelihood of periodic errors being concentrated in a single code word is significantly reduced.

In another aspect of the present invention, the mixed ordering can span across column boundaries. This aspect of the present invention allows for more flexibility in mixing the transmission ordering so as to spread periodic errors more easily over more code word.

In still another aspect of the present invention, a method for determining the mixed ordering includes defining burst error performance, specifying a performance level (or rule), and iteratively testing different mixed orders to find one or more mixed orders that achieve the specified performance level for periodic error bursts.

This embodiment can be advantageously used in a simulcast system with frequency

offsets between transmitters. In particular, the burst error performance is defined with dependence on frequency offset.

Brief Description of the Drawings The foregoing aspects and many of the attendant advantages of this invention will become more readily appreciated, when taken in conjunction with the accompanying drawings listed below.

FIGURE 1 is a block diagram illustrating a conventional interleaved error correction communication system.

FIGURE 2 is a diagram illustrating a conventional interleaving technique.

FIGURE 3 is a diagram illustrating a conventional row-wise extraction of the de-interleave table.

FIGURE 4 is a block diagram illustrating a mixed-order interleaved error correction communication system, according to one embodiment of the present invention.

FIGURE 5 is a diagram illustrating mixed-order interleaving in accordance with one embodiment of the present invention.

FIGURE 6 is a flow diagram illustrating the process of determining an interleaved error correction system to meet performance specifications in accordance with one embodiment of the present invention.

FIGURES 7-9 are diagrams illustrating periodic burst performance rules in accordance with three embodiments of the present invention.

FIGURE 10 is a diagram illustrating a mixed-order interleaved error correction system, according to another embodiment of the present invention.

FIGURE 11 is a flow diagram illustrating the process of defining an index table for a mixed order interleaved error correction communication system in accordance with one embodiment of the present invention.

FIGURE 12 is a diagram illustrating a swapped-flag table in accordance with one embodiment of the present invention.

FIGURE 13 is a diagram illustrating an interleave table of degree sixteen and having sixteen symbol codewords.

FIGURE 14 is a diagram illustrating an index table generated using the method of FIGURES 6 and 11 in accordance with one embodiment of the present invention.

FIGURE 15 is a diagram illustrating periodic burst error performance using the index table of FIGURE 14.

FIGURE 16 is a diagram illustrating periodic burst error performance using a conventional rectangular interleaving technique.

Detailed Description The present invention is directed toward a communication system that can correct random errors, error bursts, and error patterns that are periodic. To facilitate understanding of the present disclosure, the same reference numbers are used among the drawings to indicate elements having the same or similar structure or function.

FIGURE 4 illustrates a communication system 40, according to one embodiment of the present invention. System 40 is similar to system 10 (FIGURE 1), except that system 40 includes a mixed order interleaver 42 and a mixed order deinterleaver 44 instead of interleaver 12 (FIGURE 1) and deinterleaver 16 (FIGURE 1), respectively.

Thus, in this embodiment, system 40 is interconnected as follows. An input lead of encoder 11 is connected to receive data. An input lead of mixed order interleaver 42 is connected to an output lead of encoder 11. An input lead of transmitter 13 is connected to an output lead of mixed order interleaver 42. Transmitter 13 is configured to transmit signals corresponding to the encoded symbols through channel 14, which are then received by receiver 15. An input lead of mixed order deinterleaver 44 is connected to an output lead of receiver 15. An input lead of decoder 17 is connected to an output lead of mixed order deinterleaver 44.

System 40 operates as follows. As in system 10, encoder 11 is configured to receive data to be encoded using a standard error correction technique or algorithm.

For example, in this embodiment, encoder 11 is configured to implement a block- coded forward-error-correction (FEC) algorithm. More particularly, in this embodiment, the FEC algorithm is a (n, k) cyclic code that can correct up to l symbols containing errors in a codeword. Such cyclic FEC codes are well known in the art (e. g., RS, BCH).

Mixed order interleaver 42 then receives symbols from encoder 11 and fills an interleave table that is substantially similar to interleave table 21 (FIGURE 2).

The symbols in a row of the interleave table form a codeword. In this exemplary embodiment, mixed order interleaver 42 generates an interleave table of X rows.

Accordingly, this interleave code has a degree equal to S. As in a conventional interleave algorithm, this interleave algorithm of the present invention can correct random burst errors of length k I by spreading the errors over X codewords.

After the interleave table is filled, mixed order interleaver 42 then provides the symbols of each column of the interleave table to transmitter 13. However,

instead of sequentially extracting the symbols of a column from the interleave table, mixed order interleaver 42 is configured to extract the symbols of each column in a mixed order. In particular, mixed order interleaver 42 mixes the transmission order of the symbols of a column so that the number of times a row position of a column is transmitted at a spacing of a multiple of X does not exceed 1, for any particular shift of the periodic fading process and for specified frequencies and/or frequency ranges of interest (e. g., specifying a range f to fmax) This transmission ordering and frequency specification can be used to form a performance rule, as described in more detail below.

In addition, to maintain the same burst error correction performance of conventional interleaving, any kl consecutive symbols ideally should have only I symbols in the same codeword. Further, in accordance with the present invention, this mixed ordering is deterministic. That is, the ordering is predetermined or known or can be reconstructed.

Receiver 15 then receives, via channel 14, the mixed ordered symbols for each column and provides the received symbols to mixed order deinterleaver 44.

Because the mixed ordering is deterministic, mixed order deinterleaver can be configured to fill the deinterleave table so that the symbols of each column are loaded into the deinterleave table at their proper positions. Then decoder 17 can detect and correct errors in extracting the code words from the deinterleave table, as described above.

FIGURE 5 illustrates an example of the mixed ordering provided by mixed order interleaver 42 (FIGURE 4). In this exemplary embodiment, the first column of the interleave table is burst provided to transmitter 13 as indicated by arrow 521.

However, unlike in system 10, the symbols are not transmitted in sequential order (i. e., Sl, Sl+n, Sl+2n... and S (x l) n+l) Instead, the first column is transmitted in a mixed order. For example, the mixed order may be determined using a recursive algorithm. Alternatively, a mixed order may simply be preselected for each column.

As described above, mixed order deinterleave table 44 (FIGURE 4) uses the "inverse"of the mixed order to place the received symbols of the first column in their proper positions. For example, symbol Sj is placed in the first row of the first column of the deinterleave table even though symbol S I may not have been transmitted first when extracted from the interleave table. Likewise, symbol S I +n is placed in the second row of the first column even though it may not have been the

second symbol transmitted. This process repeats for each received symbol of the first column.

Then, the second column is transmitted as indicated by arrow 522. The order of the symbols is mixed in the same manner as the first column, as described above.

The symbols of the second column of the interleave table are received and then properly placed in the second column of the deinterleave table. That is, even though the order that the symbols were transmitted was mixed, each received symbol of the second column is placed in the same position in the deinterleave table as it was in the interleave table. This process is repeated for each column until all n columns are transmitted as indicated by arrow 52n. After the deinterleave is filled, the symbols are extracted from the deinterleave table and provided to decoder 17 (FIGURE 4) as described above in conjunction with FIGURE 3.

In another embodiment of the present invention, the mixed ordering of symbols cross column boundaries. This embodiment provides more flexibility in "randomizing"the transmission order of the symbols to avoid synchronization with periodic error patterns. In one embodiment, the mixed ordering is adapted for use in a simulcast system in which the transmitter has frequency offsets. Such a system is disclosed in U. S. Patent No. 5,913,172 to McCabe etal. The ordering of the transmission of the symbols from the interleave table can be summarized in an index table (an example index table in shown in FIGURE 14). The number in each position in the index table indicates the order that the symbols are extracted from the interleave table.

FIGURE 6 illustrates a method or process to find an index table that meets a specified performance level. In a block 60, an interleave table is defined. The interleave table definition includes the number of columns (i. e., n) and rows (i. e., k).

Thus, the codewords of the FEC algorithm have n symbols and the interleave table is of degree A.

Next, in a block 61, a periodic burst error performance definition is provided.

In this embodiment, burst error performance is defined as the number of maximum number of symbols in a codeword that are"hit"by a periodic burst for a given frequency offset band. In one embodiment, a hit is recorded at discrete frequencies at integer spacing of symbols. This definition is an easier model to implement for designing an interleave method for simulcast systems with frequency offsets. In such systems, nulls tend to periodically occur at certain geographical locations because of destructive interference between signals from different transmitters. If the receiver is

at one of these locations, the receiver, in effect, experiences a periodic burst errors.

Accordingly, for a given interleave algorithm (or index table), this definition records an error each symbol in a given codeword that would coincide with a null, as a function of offset frequency. One embodiment of an index table is described below in conjunction with FIGURE 14.

In another embodiment, the burst error performance definition can be based on the predicted profile of the fading in the simulcast system. A hit would be counted for a symbol if the fading that occurs when that symbol is received and the fade level falls below a predetermined level (e. g.,-30dB). Those skilled in the art will appreciate that the fading can span more than one symbol, depending on the frequency offset and the symbol rate. This method would model the periodic error burst performance more accurately relative to the method above.

Preferably, the burst error performance definition accounts for the maximum number of hits for each frequency. This can be ensured by shifting the periodic fade process by increments that may be symbol or sub-symbol steps of the index table for one period of the fade process. A shift of more than one period results in recounting positions in the index table that have already been checked.

The process then proceeds to a block 63 in which a performance rule is specified. The performance rule is, in effect, the specification that the interleaving algorithm is designed to meet. That is, the rule sets a performance level, as defined in the block 61, to be achieved by the system under predetermined or expected periodic burst error conditions. Examples of performance rules are described below in conjunction with FIGURES 7-9, which illustrate example performance rules using graphs with the vertical axis indicating the number of hits within a codeword and the horizontal axis indicating the frequency offset.

In a next block 65, an index table is defined. For example, the index table may define the mixed ordering described above in conjunction with FIGURE 5. In other embodiments, the method described below in conjunction with FIGURE 11 can be used to generate pseudo-random index tables.

The process then proceeds to a block 67 in which the performance (defined in the block 61) of the index table (defined in the block 65) is determined under the specified or expected periodic burst conditions. Then in a next block 69, the performance determined in the block 67 is compared to the performance rule or level (specified in the block 63). If the performance of the index table does not satisfy the performance rule, the process returns to the block 65 to define a new index table. If

the index table performance does satisfy the performance rule, the index table can be used in the system, thereby ending the process. Alternatively, to find a better performing index table, the process can return to the block 65 to define and test another index table.

Referring now to FIGURE 7, a graph is shown that illustrates a performance rule that can be used in the block 63 (FIGURE 6). This performance rule sets a maximum number of hits within any codeword to be lperiodic for frequency offsets between fmin and fmax, where lperiodic is a non-negative integer. This is indicated by a horizontal line segment 70 in FIGURE 7 with one end at the point (foin, lperiodic) and the other end at the point (fmax, lperiodic) This performance rule can be used in an application where fmin and fmax define the range of the frequency offsets and a single set number of hits (i. e., lperiodic) can be tolerated over the entire band.

FIGURE 8 illustrates a performance rule that is slightly more complex than that of FIGURE 7. In particular, this performance rule defines the performance for two adjacent bands of frequency offset, each band tolerating a different maximum number of hits. In this embodiment, for the band between offset frequencies foin, and fmaxl a codeword can have a maximum of lperiodicl hits, as indicated by a horizontal line segment 80 between the points (fminlf lperiodicl) and (fmaxl lperiodicl) For the adjacent band between offset frequencies fmin2 (fmin2 being coincident with fmaxl) and fmax2, a codeword can have a maximum of lperiodic2 hits, as indicated by a horizontal line segment 81 between the points (fmin2 lperiodic2) and (fmax29 lperiodic2) In view of this disclosure, those skilled in the art will appreciate that these bands need not be adjacent in other embodiments and that segment 81 may be lower than segment 80.

FIGURE 9 illustrates another performance rule defining the performance for several non-adjacent and non-overlapping frequency bands. This performance rule can be advantageously used in a simulcast application in which the frequency offsets between transmitters may be set to multiples of an incremental offset value (e. g., ml5Hz, where m is an integer). In this rule, lperiodic hits can be tolerated per codeword in each offset frequency band. In this example, because there are four frequency offset bands, line segments 91-94 represent the performance rule. The line segments 91-94 are between points (fminl, lperiodic) and (fmaxlf lperiodic) points (fmin2 lperiodic) and (fmax2 lperiodic) points (fmin35 lperiodic) and (fmax3, lperiodic), and points (fmin4 lperiodic) and (fmax4 lperiodic) respectively.

Although the performance rules described above do not specifically address systems that intersperse pilot symbols or pilot symbol sequences or other synchronization patterns in the data stream, those skilled in the art, in light of the present disclosure, can determine without undue experimentation other performance rules accounting for pilot symbols. For example, FIGURE 10 illustrates a system 100 that uses synchronization symbols interspersed in the data stream.

System 100 is similar to system 40 (FIGURE 4) except system 100 includes a synchronization inserter 102 and a synchronization extractor 104. In this embodiment, synchronization inserter 102 is connected between transmitter 13 and mixed order interleaver 42, whereas synchronization extractor 104 is connected between receiver 15 and mixed-order interleaver 44. Synchronization inserter 102 inserts pilot symbols or other synchronization symbols into the data stream to transmitter 13. Conversely, synchronization extractor 104 extracts the pilot or synchronization symbols from the received data stream, leaving the data symbols to be filled in the deinterleave table by deinterleaver 44.

Those skilled in the art will appreciate that when performing block 67 (FIGURE 6), the performance modeling would have to include the pilot or synchronization symbols in the transmissions through the channel in determining the effects of fading on performance.

Turning now to FIGURE 11, a method is described that can be used in the block 65 (FIGURE 6) to define an index table. FIGURE 11 includes a flow diagram illustrating a process of defining an index table with mixed ordering of symbols, according to one embodiment of the present invention. In a block 110, a swapped- flag table is built. The swapped-flag table has n columns and X rows, matching the size of the index table to be defined. Each position of the swapped-flag table is "mapped"to the corresponding position of the index table. Initially, all of the entries in the swapped-flag table are reset (e. g., all to zero). Each zero entry in the swapped indicates that the corresponding entry in the desired index table has not been reordered. An example of a reset swapped-flag table is shown in FIGURE 12.

In a block 111, an index table of n columns and degree X is built. Initially, the ordering of the index table is for a conventional rectangular interleave system.

This index table is referred to as the rectangular index table. For example, a rectangular index table with sixteen columns and degree sixteen is illustrated in FIGURE 13. As previously described, an index table defines the order in which symbols are transmitted (i. e., the symbol sequence). In a block 113, a maximum

distance 8 (typically, 6 < n/2) between swapped symbols in a symbol sequence is defined. That is, the position in which a particular symbol is transmitted in the symbol sequence can be changed a maximum of 8 positions relative to its original position in the rectangular index table. As used herein, 8 includes both positive and negative shifts. This allows the position of the symbol in the symbol sequence to cross a column boundary.

The process then proceeds to a block 115. In the block 115, the process randomly or pseudo-randomly selects one of the positions of the index table (see the block 111) whose corresponding flag in the swapped-flag table is reset (i. e., an unswapped position). The algorithm can allow a symbol to be swapped with itself so that its position is unchanged. Then the process randomly or pseudo-randomly selects a position in the index table (whose corresponding flag is also reset or unswapped) within 8 positions of that previously selected position (i. e., the most recently selected position)."Wrap-around"is used so that there are 8 positions on either side of the first and last selected position in the table, forming, in effect, a "circular"index table. The positions of these two most recently selected positions are swapped in the index table. For example, say the first and second selected positions in the rectangular index table are the 3rd and the 9th positions, respectively. Then, a "9"and a"3"are entered in the 3rd and 9th positions of the new index table, respectively. Consequently, the symbol in the third position of the interleave table will be transmitted in the ninth position of the symbol sequence.

In a next block 117, the flags corresponding to the two positions selected in the block 115 are set (i. e., indicating that these positions have been swapped). The process then proceeds to a block 119 in which the swapped-flag table is checked to determine whether all of the flags have been set. If all of the flags have been set, then the mixed-ordering of the index table is complete and the process ends. If all of the flags are not set, the process returns to the block 115 to swap two more positions in the index table. FIGURE 14 shows a mixed-order index table derived from the rectangular index table of FIGURE 13 using this process. In light of this disclosure, those skilled in the art will appreciate that the blocks 110,111 and 113 may be performed in a different order than described above.

FIGURE 15 is a graph illustrating periodic burst error performance using the new index table of FIGURE 14. The vertical axis of this graph indicates the maximum number of errors that can occur in any codeword under specified periodic burst error conditions, whereas the horizontal axis indicates the frequency offset. As

can be seen in FIGURE 15, the graph shows for frequency offsets from about 12.5Hz to 135Hz, a maximum of three errors can occur in any codeword. In contrast, the periodic burst error performance of conventional rectangular interleaving is significantly poorer under the same conditions, as shown in FIGURE 16. As shown in FIGURE 16, the maximum number of errors in a codeword for frequency offsets between about 12.5Hz to 135Hz can be as high as eight errors. An FEC algorithm that can correct eight errors in a codeword is relatively costly in bandwidth, throughput and implementation and, thus, may not be practical for many applications.

The embodiments of the mixed order FEC interleaving system described above are illustrative of the principles of the present invention and are not intended to limit the invention to the particular embodiments described. For example, in light of the present disclosure, those skilled in the art can devise without undue experimentation, define different algorithms for mixing the transmission order of symbols within a column. Further, the values for X and n can be different than those described. Still further, the performance rules may have non-linear, sloped, and different sized segment (s) in other embodiments. Accordingly, while the preferred embodiment of the invention has been illustrated and described, it will be appreciated that various changes can be made therein without departing from the spirit and scope of the invention.