HK1074919A - Erasure-and-single-error correction decoder for linear block codes - Google Patents

Description

Erasure and single error correction decoder for linear block codes

Background

FIELD

The present invention relates generally to data communications, and more particularly to techniques for efficiently performing erasure and single-error-correction decoding of linear block codes.

Background

With the advent of data communications and the need to transmit large amounts of data over lossy or band-limited channels, encoding the data for correct reception is of great importance. Data transmission is often degraded in the communication channel by impairments, such as thermal noise, interference, spurious data due to transmission bandwidth, and so forth. So that the received data is typically a distorted version of the transmitted data.

The encoding may be used to enable the receiver to detect and/or correct errors in the received data. Various error correction codes are available and can be classified into several categories, such as block codes and convolutional codes. Convolutional codes provide good error correction capability but typically output correlated error bursts. Block codes have inherent burst error control capabilities when combined with the correct level of interleaving. For example, Reed-Solomon codes can control any error burst within a symbol, which can be defined to include a particular number of bits.

In theory, block codes can correct a certain number of erasures and/or a certain number of errors, the exact number of each being determined by the code distance. An erasure may indicate a symbol that is known a priori to be potentially bad. But an error is a symbol received in error but not known a priori. Typically erasures are known or can be determined by the receiver and thus taken into account in the decoding process. The error is an undetected symbol error, which is a symbol that was erroneously detected as being correctly received and that itself was not correctly received.

Conventional erasure and error correcting packet decoders (e.g., Berlekamp-Massey or Euclidean decoders) are complex and typically need to be implemented in dedicated hardware. These packet decoders are typically too computationally intensive for software-based implementations executing on a microprocessor. Hardware-based decoders are able to use parallelism in the decoding algorithm and use pipelined datapaths, both of which may not be conventional microprocessors. More efficient packet decoder algorithms are available, which are more suitable for software-based implementations. However, these decoding algorithms typically have limited capabilities and may be able to correct erasures rather than errors.

There is therefore a need in the art for an efficient erasure and error correcting decoder for linear block codes, and which is suitable for software-based implementations.

Abstract

Several aspects of the present invention provide techniques for efficiently performing erasure and single error correction block decoding on a block of received symbols previously encoded in a column-wise manner using an (N, K) linear block code and encoded in a row-wise manner using an error detection code. If the error detection code (e.g., CRC code) on a row has relatively good error detection performance, the probability of more than one undetected error in the received data packet is very low. Thus, a single error correction is generally sufficient in most applications.

Initially, each row of the received packet is marked as an erased row or an unerased row until at least (K +1) unerased rows are found. Typically all N rows of the received packet are marked, but this is not absolutely necessary. The rows may be marked based on Cyclic Redundancy Check (CRC) bits contained in each row, or by other means. Erasure-only or erasure-and-error-correcting block decoding may then be performed on the received block according to the number of erased rows (i.e., supported by the (N, K) block code distance).

To perform erasure and single error correction packet decoding on a received packet, a list of codewords corresponding to the received packet containing undetected symbol errors is initially identified. The undetected symbols may be errors that were not detected by a previous CRC check performed on each row of the received packet. This codeword can be identified by (1) deriving an estimate of the non-erased systematic rows of the received packet; (2) comparing the non-erased systematic row with its estimate; and (3) identifying symbols that do not match between the non-erased systematic row and its estimates.

The symbol error position (previously undetected) in the codeword is then determined based on a particular block decoding scheme (e.g., a scheme known in the art and corresponding to the selected linear block code). Thereafter, the row of the received packet containing the located symbol error is marked as an erased row. Block decoding may then be performed in a conventional manner on the received block with the erasure line containing the marker of the symbol error. The erasure and single error correction packet decoding techniques described herein are computationally efficient (relative to conventional techniques) and may be implemented in hardware, software, or a combination thereof.

Various aspects and embodiments of the invention are described in further detail below, and the invention further provides methods, computer program products, decoders, receiver units, and other apparatuses and elements that implement various aspects, embodiments, and features of the invention, as described in further detail below.

Brief description of the drawings

The features, nature, and advantages of the present invention will become more apparent from the detailed description set forth below when taken in conjunction with the drawings in which like reference characters identify correspondingly throughout and wherein:

FIG. 1 is a block diagram of a transmitter unit and a receiver unit capable of implementing aspects and embodiments of the invention;

FIG. 2 is a diagram illustrating various steps for performing erasure-only correction block decoding of linear block codes;

FIGS. 3A and B illustrate various steps for performing erasure and single error correction block decoding of a linear block code;

FIG. 4 is a simplified flow diagram of an embodiment of a process for performing erasure and single error correction block decoding of linear block codes;

FIGS. 5A and B illustrate a process of performing erasure and single error correction block decoding of a linear block code

Detailed flow charts of the embodiments;

description of The Preferred Embodiment

The inventive block decoding techniques described herein may be used for various coding schemes. For simplicity, these techniques are described in terms of particular two-dimensional product coding schemes, including Cyclic Redundancy Check (CRC) row codes and linear block column codes. An example communication system is described below in which the inventive packet decoding techniques may be used.

FIG. 1 is a block diagram of a transmitter unit 110 and a receiver unit 150 capable of implementing various aspects and embodiments of the invention; at transmitter unit 110, data source 112 provides data (e.g., in the form of frames of a particular length) to outer encoder 120, which outer encoder 120 includes a block encoder 122 and a CRC encoder 124. The block encoder 122 receives and encodes each block of a particular number of data frames to provide a corresponding block-encoded data block. In one embodiment, the bits in a data packet are first grouped to form symbols (each symbol includes N_BBits) and each column of K symbols in the burst is encoded using a particular (N, K) linear block code to provide a corresponding codeword having N symbols. So that the block-coded data burst comprises N rows of symbols. For systematic block codes, the first K rows are data rows, while the remaining (N-K) rows are parity rows.

For each of the N frames in the block-coded data block, CRC encoder 124 generates a set of CRC bits based on the data bits in the frame and appends the CRC bits to the end of the frame. At the receiver unit, the CRC bits included in each frame are used for error detection of the frame. The CRC encoder 124 provides encoded packets, each encoded packet being CRC encoded in one (horizontal) direction and block encoded in the other (vertical) direction.

Block encoder 122 may implement linear block codes such as Reed-Solomon codes (commonly used for data transmission), Hamming codes, BCH (Bose, Chaudhuri, and Hocquenghem) codes, and some other codes. The inventive block coding techniques described herein may be used for any linear block coding and are advantageously used for systematic block coding.

In the embodiment shown in fig. 1, the encoded packet is provided to an inner encoder 130 that includes an interleaver 132 and a convolutional encoder 134. The interleaver 132 shuffles (i.e., reorders) the bits in each encoded packet and provides the interleaved bits to the convolutional encoder 134, which then encodes the bits according to a particular convolutional code. Interleaving provides time diversity and disperses burst errors from the convolutional encoder.

Although inner encoder 130 may be used to provide additional error correction capability, the inventive block decoding techniques described herein may be used with coding schemes that do not include the inner encoding provided by encoder 130. The inner encoder 130 is thus optional, as represented by the dashed box. Likewise, the data provided to outer encoder 120 may represent data that has been previously encoded using a particular code (i.e., not "original" data or information bits).

The encoded data from inner encoder 130 is then provided to modulators/transmitters (Mod/TMTR)140, 140 that modulate (e.g., cover and spread) the encoded data to provide modulated data and further condition (e.g., convert to one or more analog signals, filter, amplify, upconvert, and quadrature modulate) the modulated data to provide a modulated signal suitable for transmission over a (e.g., wireless) communication channel.

At receiver unit 150, the transmitted modulated signal is received by an antenna 152 and provided to a receiver/demodulator (RCVR/Demod) 154. Receiver/demodulator 154 conditions (e.g., filters, amplifies, and frequency downconverts) the received signal and digitizes the conditioned signal to provide data samples. The receiver/demodulator 154 may further process (e.g., despread and decover) the data samples to provide demodulated data.

In the embodiment shown in fig. 1, the demodulated data is provided to an inner decoder 160, the inner decoder 160 including a Viterbi decoder 162 and a deinterleaver 164. The Viterbi decoder 162 performs decoding of the convolutional code used at the transmitter unit 110, and the deinterleaver 164 reorders the decoded bits in a manner opposite to that performed by the interleaver 132. The deinterleaved data is then provided to an outer decoder 170.

The outer decoder 170 includes a CRC checker 172 and a packet decoder 174. For each received packet corresponding to an encoded packet sent from the transmitter unit, the CRC checker 172 checks each row of the received packet and provides an indication of whether the row was received correctly or in error (i.e., erased). The CRC-checked packet is then provided to a packet decoder 174, and the packet decoder 174 performs erasure and single-error or erasure-only correct packet decoding of this packet, as described in detail below. The decoded data from the block decoder 174 is then provided to a data sink 176.

Controller 180 may be used to direct various decoding steps at receiver unit 150. The controller 180 may also be used to implement some or all of the outer decoder 170. As such, program code and necessary data may be stored in the memory 182, with the memory 182 being operatively coupled to the controller 180.

Fig. 1 illustrates an embodiment of a transmitter unit and a receiver unit capable of implementing various aspects and embodiments of the invention, and other transmitter and receiver designs may be used and are within the scope of the invention. For example, the receiver unit may be designed to include a CRC checker 172 and a block decoder 174 without an inner decoder 160.

Fig. 2 is a diagram illustrating various steps for performing erasure-only correction block decoding of linear block codes. An (N, K) linear block encoder encodes each "block" of K data symbols (according to a particular set of polynomials if a cyclic code) to provide a corresponding codeword with N code symbols. The minimum distance D of the code determines the erasure and error correction capabilities of the block code, while the code parameters (N, K) determine the storage requirements. It is known that (N, K) block codes can simultaneously correct T symbol errors and F erasures in a given codeword, where T and F satisfy the following condition:

(2T + F) is less than or equal to (D-1) formula (1)

The inventive decoding techniques described herein may be used for any code rate. For simplicity, one small code with code rate (8, 4) and minimum distance D-5 is used for the specific example shown in fig. 2.

At the transmitter unit, each group of a specific number of data frames consists of a K x L information packet i_K×LAnd (4) showing. In one embodiment, each row of information packets corresponds to a respective frame of data and includes L symbols for all bits in the frame. Each symbol (formed by an information packet i)_K×LSmall square in (c) includes N_BBit, N_BThe specific value of (c) depends on the particular block code selected for use.

Block coding by grouping information i_K×LUsing NxK generator matrix G_N×KLeft-hand multiplication (step 1). The generator matrix may be derived based on a set of polynomials determined for the selected linear block code. Techniques for determining this polynomial and deriving the generator matrix are well known in the art and will not be described here. Since each symbol in the information packet and the generator matrix can be a multi-bit value, the element-by-element multiplication and addition of the matrix multiplication is in the Galois field GF (2)^NB) Is performed, wherein N_BIs the number of bits per symbol. Multiplying the generator matrix by the information packet to produce an N x L code packet c_N×L。

For systematic (N, K) block codes, each codeword includes K data symbols and (N-K) parity symbols formed from a linear combination of the K data symbols. Thus, the packet is encoded as shown in the example in FIG. 2, c_N×LComprising an information packet i_K×LK systematic rows of K data rows, and (N-K) parity rows generated based on the K data rows and the generator matrix. Code packet c_N×LEach of the L columns in (a) corresponds to a respective codeword.

As shown in fig. 1, code packet c_N×LIs further processed at the transmitter unit and sent to the receiver unit, which then performs complementary processing to provide a received packet r_N×L. Receiving a packet r_N×LEach code inThe element corresponding to a code packet c_N×LBut may be received in error due to degradation caused by the communication channel.

At the receiver unit, each row (e.g., each data frame) in the received packet may be checked by a CRC checker 172 to determine whether the row was received correctly or in error (step 2). If the CRC of a row fails to check, the entire row is deemed to have been received incorrectly, regardless of whether errors occur in only one symbol, some symbols, or all symbols of the row. For the example shown in fig. 2, a symbol r is received_N×LThe second and fourth rows of (a) are marked as erased because the CRC does not pass the check of these rows. These erase rows are represented by the rows of shaded squares.

In some instances, even a row including multiple errors may pass the CRC check. This occurs if the number of errors in this row exceeds the error detection capability of the selected CRC code and the particular value of the error is such that the CRC (coincidentally) passes the check. In this case, this row will be (erroneously) indicated as having been correctly received, when in fact it comprises a number of undetected symbol errors. Receiving a packet r_N×LThe sixth row in the figure shows an example of such an error, where three undetected symbol errors are indicated by three black squares.

A block decoding technique that corrects only erasures (not errors) may be performed as follows. First, corresponding to a received packet r_N×LGenerating matrix G of erased rows_N×KThe row of (2) is also marked as erased (step 2). For the example shown in FIG. 2, a matrix G is generated_N×KIs marked as erased, by G_N×KIndicated by the shaded square in (1).

For the next step in error-only packet decoding, a received packet r_N×LIs selected to form a reduced received packet r_K×L', generating a matrix G_N×KIs also selected to form a simplified generator matrix G_K×K' (step 3). For the example shown in fig. 2, a packet r is received_N×LFront ofFour non-erased rows (i.e., rows 1, 3, 5, and 6) are selected to form a simplified received packet r_K×L', to generate a matrix G_N×KAre selected to form a simplified generator matrix G_K×K'. In this example, one of the selected rows (i.e., row 6) also happens to include undetected symbol errors.

Then, the simplified generator matrix G_K×K' inverted to derive an inverted (i.e. inverse) generator matrix G_K×K′^-1(step 4). This matrix inversion may be performed in a manner well known in the art. Inverse generator matrix G_K×K′^-1Followed by a reduced received packet r_K×L' multiplication to derive an information packet i_K×LInitial estimation of' (step 4). Followed by grouping i with the initially estimated information_K×L' corresponding line replacement of received packet r_N×LTo derive an estimate of the information packet(s) by erasing the system rows (i.e., rows 2 and 4)(step 5).

If simplified received packet r_K×L' if the symbols in all rows are correct, then the information packet is estimatedWill equal the transmission information packet i_K×L(i.e., the amount of the acid,). In this way, the block decoding can correct the erasure in the received block by using the redundant parity rows (i.e., rows 5 and 6) to recover the erased systematic rows (i.e., rows 2 and 4).

However, for the example shown in fig. 2, the simplified received packet r_K×L' the last row of undetected symbol errors in the initial estimate information packet i_K×LCorresponding column of `Error of (2). These errors are estimated by initially estimating the information packet i_K×LBlack squares in columns 4, 7 and 12 of' are shown. Because of the reception of the packet r_N×LAre erased so these rows are grouped by the initial estimate information i_K×LThe corresponding lines 2 and 4 of' replace. As shown in fig. 2, each alternate erased row will include the same number of symbol errors as in the error row. These errors will then be submitted to the next processing stage.

Fig. 3A and B illustrate various steps for performing erasure and single error correction block decoding of linear block codes. For simplicity, the embodiment of fig. 3A and B uses the same example as for fig. 2, thereby receiving a packet r_N×LIncluding two erasure rows 2 and 4 and an error row 6 (containing multiple undetected symbol errors).

A block decoding technique to correct erasures and single errors may be performed as follows. To begin, a packet r is received_N×LIs checked by CRC checker 172 to determine whether the row was received correctly or in error, and if the CRC does not pass the check then the row is marked as erased (step 2 in fig. 2). Receiving a packet r_N×LThe non-erased systematic row of (a) is then marked as a pseudo-erased row (step 3 in fig. 3A) and is processed like an erased row for some of the decoding steps that follow (i.e., steps 4 and 5). Then, corresponding to the received packet r_N×LGenerating matrix G of erased rows_N×KThe row of (a) is marked as erased (step 3). For the example shown in FIGS. 3A and 3B, a matrix G is generated_N×KAre marked as erased, indicated by the shaded boxes.

For the next step of erasure and single error correction packet decoding, a received packet r_N×LIs selected to form a reduced received packet r_K×L', to generate a matrix G_N×KIs selected to form a simplified generator matrix G_K×K' (step 4). For the exemplary embodiment shown in fig. 3A and 3B, a packet r is received_N×LThe first four non-erased rows (i.e., rows 3, 5, 6, and 7) are selected to form the simplified contactReceive packet r_K×L', to generate a matrix G_N×KAre selected to form a simplified generator matrix G_K×K'. Also for this example, one of the selected rows (i.e., row 6) happens to include undetected symbol errors.

Then, for the simplified generator matrix G_K×K' inversion to derive an inverse generator matrix G_K×K′^-1(step 5). Thereafter, the matrix G is inversely generated_K×K′^-1And simplified received packet r_K×L' multiplication to derive an initial estimate information packet i_K×L' (step 5).

For the next step in packet decoding, the pseudo-erased row (i.e., row 1) is combined with the initial estimate information packet i_K×LThe corresponding rows in' (step 6) are compared. Simplified received packet r due to matrix multiplication_K×L' any symbol error results in an initial estimated information symbol i_K×L' where the column is in symbol error. Thus, when the pseudo-erased row is associated with the initial estimated information packet i_K×LWhen the corresponding row in' compares symbol by symbol, errors (i.e., mismatched symbols) are detected in columns 4, 7, and 12 because the symbols at these positions do not match.

The codeword corresponding to the column containing the unmatched symbols is then selected (step 6). For the exemplary embodiment shown in fig. 3A and 3B, the codeword corresponding to the row containing the first unmatched symbol (i.e., row 4) is selected. Calculations are then performed to locate symbol errors in the selected codeword. The error location may be determined based on various packet decoding techniques known in the art. For example, for Reed-Solomon codes, syndromes are first computed from the N symbols of the codeword, then the coefficients of the error location polynomial σ (x) are computed from the syndromes, and then the error locator is computed from these coefficients. For the exemplary embodiment shown in fig. 3A and 3B, the symbol error is located at the 6 th position of the codeword.

In the next step, the entire row (i.e., row 6) in which the symbol error is located is marked as an erased row, and the pseudo-erased row (i.e., row 1) is marked as a non-erased row (step 7).Subsequent packet decoding may then continue as described above in fig. 2. In particular, a packet r is received_N×LCan be selected to form a new reduced received packet r, the K non-erased rows (i.e., rows 1, 3, 5, and 7) of_K×L", to generate a matrix G_N×KIs selected to form a new simplified generator matrix G_K×K". As shown in fig. 3, the row with the (previously undetected) symbol error is marked as an erased row and is not selected for use.

Then, a new simplified generator matrix G_K×KIs inverted to derive an inverse generator matrix G_K×K″^-1(step 8). Inverse generator matrix G_K×K″^-1Followed by a reduced reception matrix r_K×L"multiplication" to derive an information packet i_K×L"is estimated. Estimation of information packetsIt is then possible to group i by using the new initial estimate information_K×L"replaces the received packet r by the corresponding row of_N×LIs derived (step 9) from the erase system rows (i.e., rows 2 and 4).

Because of the new simplified received packet r_K×L"are correct values in all rows, so the estimated information packetEqual to sending information packet i_K×L(i.e., the amount of the acid,). In this example, erasure and single error correction packet decoding enables correction of the received packet r by using redundant parity rows (i.e., rows 5 and 7) to recover the erased systematic rows (i.e., rows 2 and 4)_N×LTwo erasure rows and one error row.

In general, erasure and single error correction packet decoding can be achieved by: (1) using the redundant parity lines to derive estimates for the non-erased systematic lines, (2) comparing the non-erased systematic lines to its estimates to determine the locations of the non-matched symbols (or errors), (3) locating symbol errors in a codeword (or column) containing a non-matched symbol, (4) marking the entire line containing symbol errors as erased, and (5) performing block decoding of the systematic lines based on the non-erased lines of the received block.

The erasure and single error correction block decoding technique of the present invention is less computationally intensive than conventional decoding techniques (in part because error localization is only performed on one codeword if undetected symbol errors are subsequently detected as having false erasure lines). Thus, the pseudo-erasure row can be used to indicate the exact codeword (or exact column in the 2-dimensional grouping) where the undetected symbol error is located, and the exact location of the symbol error in the codeword (or exact row in the 2-dimensional grouping) can be determined by performing the grouping error locating on the codeword. Then, the rows containing (previously undetected) symbol errors are marked as erased, and erasure-only correction packet decoding can be performed on the received packet.

Steps 3 through 6 in fig. 3A effectively determine the particular column for which an undetected symbol error can be found. Other schemes may be used to determine the error sequence and are within the scope of the invention.

Also, in step 6, it is not necessary to derive the pseudo-erasures at the same time (i.e., for the entire row). Instead, the pseudo-erasures may be derived one symbol at a time and compared to the corresponding symbols in the received pseudo-erased row. That way, if the error is located within one of the first columns, then other pseudo erasures within this row need not be derived.

Derived information packet i_K×L' initial estimation and estimation of information packet i_K×LThe information of' is a conceptual step. For the example illustrated in fig. 3A and 3B, these steps are shown to better understand the packet decoding technique. However, i is actually derived_K×LThe only few rows of' are initialThose rows of the packet that are erased are received.

Because only (K +1) good rows (or CRC-checked frames) in the received packet are needed to perform erasure and single-error decoding, it is possible that the (K +1) good rows turn off the front end of the receiving unit (e.g., receiver/demodulator 154, Viterbi decoder 162, deinterleaver 164, and CRC checker 172 in fig. 1) as soon as they are received. This will save power in the receiver unit.

Fig. 4 is a simplified flow diagram of a process 400 for performing erasure and single error correction block decoding of linear block codes according to an embodiment of the present invention. Initially in step 412, an encoded packet including several codewords is received and erasure lines in the received packet are determined. The erased row may be determined by performing a CRC check on each row of the received packet or by some other mechanism.

In step 414, the codeword corresponding to a column of the received packet containing the undetected symbol error is identified. This undetected symbol error is one that is not included in the erased row of the received packet. This column may be identified using the pseudo-erase row described above or by other means. Then in step 416, the symbol error location in the codeword is determined (e.g., using any technique known in the art). Next, in step 418, the row of the received packet containing the symbol error is identified as an erased row. Next, in step 420, block decoding may be performed on the received packet with the rows containing symbol errors that were most recently marked as erased.

Fig. 5A and 5B show a detailed flow diagram of a process 500 for performing erasure and single error correction block decoding of (N, K) linear block codes according to an embodiment of the present invention. Initially in step 512, an encoded packet including several (L) codewords is received and erasure lines in the received packet are determined.

Next, in step 514, a determination is made as to whether the number of erase rows in the received packet is greater than (D-1). As noted in equation (1) above, a properly designed block code can correct up to (D-1) erasures in one codeword. Thus, if the number of erased rows exceeds (D-1), it is not possible to correct all erased rows because this code distance is too large, as indicated in step 516. This step is then terminated.

On the other hand, in step 518, if the number of erase rows is equal to or less than (D-1), it is determined whether the number of erase rows in the received packet is greater than (D-3). Also as noted in equation (1) above, a properly designed block code can correct up to (D-3) erasure symbols and one error symbol in one codeword. Thus if the number of erased rows is equal to (D-2) or (D-1), then an erasure-only correction is possible for all erased rows and begins execution in step 522.

Or in step 520, if the number of erased lines is equal to or less than (D-3), it is determined whether the number of erased system lines in the received packet is greater than (K-1). If one of the systematic rows is used as a pseudo-erased row to locate columns of undetected symbol errors, and if no non-erased systematic rows are available for use as pseudo-erased rows, then erasure-only correction of all erased rows is still possible and may likewise be performed beginning at step 522.

Alternatively, if the number of erased rows is equal to or less than (D-3) and at least one non-erased systematic row is available, then beginning at step 532, erasure and single error correction packet decoding may be performed in this received packet. In general, erasure-only and single-error correction packet decoding may be performed whenever possible, if possible and if erasure-only and single-error correction packet decoding cannot be performed.

In step 522, to perform erasure-only-correction-packet decoding, the simplified generator matrix G_K×K' begin by selecting the receiver corresponding to the received packet r_N×LOf arbitrary K non-erased rows of the generator matrix G_N×KK rows of (a). The reduced generator matrix is then inverted in step 524. Next, in step 526, the slave information packet i_K×L' deriving the erased systematic rows of the received packet, information packet i, corresponding to the rows of the initial estimate_K×LThe initial estimate of' is obtained byInverse generator matrix G_K×K′^-1And simplified received packet r_K×L' multiply derived, simplified received packet r_K×L' by receiving a packet r_N×LK corresponding non-erased rows are formed. If simplified received packet r_K×L' if there are no undetected symbol errors in the row, then the information packet i is initially estimated_K×L' will include correction of all erased systematic rows in the received packet. Then, the erasure-only correction packet decoding terminates.

To perform erasure and single error correction packet decoding, the row position of an undetected symbol error in a received packet is first determined. This can be achieved as follows. First, in step 532, a non-erased systematic row (e.g., the first such row in the received packet) is selected as the pseudo-erased row. In the following step, this row is treated as an erasure row to determine the location of undetected symbol errors. Then, in step 534, the simplified generator matrix G_K×K' by selecting the corresponding received packet r_N×LOf arbitrary K non-erased rows of the generator matrix G_N×KK rows of (a). Next, in step 536, the simplified generator matrix is inverted. Next, in step 538, a matrix G is generated by inverting_K×K′^-1And simplified received packet r_K×L' multiplication to derive an estimate of the pseudo-erased line, simplified received packet r_K×L' by receiving a packet r_N×LK corresponding non-erased rows are formed. Since only an evaluation of the pseudo-erased rows is required, G_K×K′^-1And r_K×L' the matrix multiplication can be on G_K×K′^-1Is only one row (not the entire matrix) and r_K×LAll columns of' execute.

The pseudo-erase row and its estimate are then compared in step 540. This comparison is performed symbol by symbol until the first unmatched symbol is detected. It is then determined in step 542 whether there are any mismatched symbols in the pseudo-erased row. If there are no mismatched symbols then there are no undetected symbol errors in the received symbols and the process proceeds to step 526 to derive erased systematic rows.

Alternatively, if at least one of the pseudo-erased rows does not match a symbol, as determined in step 542, undetected symbol errors are present in the received packet and the row locations of these errors are then determined in step 544. This can be achieved by: identifying the location of the mismatched symbol (e.g., the first mismatched symbol) within the pseudo-erased row, retrieving the codeword (or column of the received packet) containing this mismatched symbol, and performing error localization for this codeword based on techniques well known in the art. Thus, in step 546, the symbol error in the codeword is located and the entire row of the received packet containing the symbol error is marked as an erased row.

Then, in step 548, it is determined whether the pseudo-erased row is a row having a symbol error. If the answer is in the affirmative, this error row has been included as a pseudo erasure when the reduced received packet and the reduced generator matrix are formed. Thus, G_K×K′^-1Is correct and r is_K×L' does not contain any undetected errors. The process then continues to step 526 where the erased system row is derived. Otherwise, next in step 550, a new simplified generator matrix G_K×K"Generation of matrix G by selection_N×KIs formed corresponding to the received packet r_N×LReceive a packet r of arbitrary K rows_N×LStill non-erased. At step 552, the new simplified generator matrix is inverted.

The process then continues to step 526, where the erasure system row receiving the packet is selected from the information packet i_K×L"the corresponding line of the new initial estimate, information packet i_K×L"by generating the new inverse to the matrix G_K×K″^-1And a new reduced received packet r_K×L"multiplied to derive, and a new reduced received packet r_K×L"has a received packet r_N×LK corresponding non-erased rows are formed.

Various modifications may be made to the process shown in fig. 5. For example, multiple iterations may be performed from step 532 to step 546 to detect multiple error rows.

The packet detection technique of the present invention may be advantageously used with concatenated codes including error detection codes and block codes. Error detection encoding may be performed in one dimension (e.g., horizontal) of the information packet, while block encoding may be performed in another dimension (e.g., vertical) of the information packet. The inventive packet decoding technique can be used to identify and locate errors that the error detection decoding fails to capture, and to remove these symbol errors from the packet decoding process. The inventive block decoding technique thus improves the problems caused by detection error failures that cannot be handled by conventional block decoding techniques that can only correct erasures and not errors.

The inventive packet decoding described herein is computationally efficient and well suited for software implementation executing on a microprocessor. To quantify the computational efficiency, the multiply and accumulate operands performed by some of the steps of the flow diagrams in fig. 5A and 5B are provided as follows:

step by step number of accumulation operations

524，536，552 KP_sys ²(for each step)

538 KL

544 (P +2) (N-1) + P (P +2) +1 (for Reed-Solomon codes)

526 KLP_sys

Wherein

N is the codeword length;

k is the number of information symbols in the codeword;

r is the number of parity symbols (i.e., R — N-K);

l is the number of codewords per code packet;

p is the number of erasure lines in the received packet; and

P_sysis the number of erasure system lines in the received packet.

The inventive packet decoding techniques described herein may be used in various communication and data transmission systems. For example, these techniques may be advantageously used in wireless communication systems such as CDMA, FDMA and TDMA systems. Moreover, in a wireless communication system, the decoding techniques described herein may be implemented at a terminal (e.g., a wireless device such as a cellular telephone) for the downlink (i.e., forward link) or at a base station or access point for the uplink.

As noted above, the inventive packet decoding techniques described herein may be implemented using a variety of means. For example, these techniques may be implemented in hardware, software, or a combination thereof. For a hardware implementation, some or all of the elements used to implement packet decoding may be implemented in one or more of the following devices: an Application Specific Integrated Circuit (ASIC), a Digital Signal Processor (DSP), a Digital Signal Processing Device (DSPD), a Programmable Logic Device (PLD), a Field Programmable Gate Array (FPGA), a processor, a controller, a microcontroller, a microprocessor, other electronic components designed to perform the functions described herein, or a combination thereof. The hardware (e.g., ASIC or DSP) may include one or more functional units that collectively perform the processing described above to implement the inventive block coding. For example, one unit may be provided to perform row-wise error detection (e.g., CRC checker 172), another unit may be provided to perform column-wise block decoding (e.g., block decoder 174), and so on.

For a software implementation, the inventive block coding techniques may be implemented with modules (e.g., procedures, functions, and so on) that perform the functions described herein. The software may be stored in a memory unit (e.g., memory 182 of fig. 1) and executed by a processor (e.g., controller 180). The memory unit may be implemented within the processor or external to the processor, in which case it can be communicatively coupled to the processor via various means as is known in the art.

The previous description of the preferred embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without the use of the inventive faculty. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

Claims (32)

1. A method of performing block decoding on a received symbol block previously encoded in a column-wise manner using an (N, K) linear block code and encoded in a row-wise manner using an error detection code, comprising:

identifying a codeword corresponding to a column of the received packet in which the undetected symbol error is located;

determining the location of undetected symbol errors in a codeword;

marking a row of the received packet containing the undetected symbol error as an erased row; and

packet decoding is performed on the received packet with the erasure line marked.

2. The method of claim 1, further comprising:

deriving an estimate of non-erased systematic rows of the received packet;

comparing the non-erased systematic row with its estimate; and

the location of the mismatched symbol between the non-erased systematic row and its estimate is identified, where this codeword is identified as corresponding to the column containing the mismatched symbol.

3. The method of claim 2, wherein the estimate of non-erased systematic rows of the received packet is derived by:

marking the non-erased system row as an erased row;

forming a reduced received packet comprising K non-erased rows of the received packet; and

the inverse of the generator matrix with K non-erased rows is multiplied with the reduced received packet.

4. The method of claim 1, wherein the location of undetected symbol errors in a codeword is determined by performing error localization for the codeword based on a particular block decoding scheme.

5. The method of claim 1, wherein performing packet decoding comprises:

forming a reduced received packet consisting of K non-erased rows of the received packet;

forming a simplified generator matrix comprised of K rows in the generator matrix corresponding to the K non-erased rows;

inverting the simplified generator matrix; and

the inverse of the generator matrix is multiplied with the reduced received packet.

6. The method of claim 1, further comprising:

each row of the received packet is marked as either an erased row or an unerased row until at least (K +1) unerased rows are found.

7. The method of claim 6, wherein each row is marked as an erased row or a non-erased row based on a result of a Cyclic Redundancy Check (CRC) test.

8. The method of claim 1, further comprising:

the number of erasure lines is determined in the received packet.

9. The method of claim 8, further comprising:

if the number of erasure lines is equal to (D-2) or (D-1), erasure-only correction packet decoding is performed.

10. The method of claim 8, further comprising:

if the number of erasure lines is less than or equal to (D-3), erasure and error correction block decoding is performed.

11. The method of claim 10, further comprising:

determining the number of erasure system lines in the received packet; and

if the number of erasure system lines is less than or equal to (K-1), erasure and error correction block decoding is performed.

12. The method of claim 8, further comprising:

if the number of erase rows exceeds (D-1), an error is declared.

13. The method of claim 1, wherein the (N, K) linear block code is a Reed-Solomon code.

14. A method of performing block decoding on a received symbol block previously encoded in a column-wise manner using an (N, K) linear block code and encoded in a row-wise manner using an error detection code, comprising:

marking each row of the received packet as an erased row or an unerased row until at least (K +1) unerased rows are found;

deriving an estimate of non-erased systematic rows of the received packet;

comparing the non-erased systematic row with its estimate;

identifying symbols that do not match between the non-erased systematic row and its estimate;

identifying a codeword corresponding to a column of the received packet containing non-matching symbols;

determining a location of a symbol error in the codeword based on the particular block decoding scheme;

marking a row of the received packet containing the symbol error as an erasure row; and

packet decoding is performed on the received packet with the erasure line marked.

15. A computer program product for performing block decoding on a received packet of symbols previously encoded column-wise using an (N, K) linear block code and row-wise using an error detection code, comprising:

code for identifying a codeword corresponding to a column of the received packet in which the undetected symbol error is located;

code for determining a location of an undetected symbol error in a codeword;

code for marking a row of the received packet containing undetected symbol errors as an erased row;

code for performing block decoding on the received packet with the erasure line marked; and

a computer usable medium for storing such code.

16. The computer program product of claim 15, further comprising:

code for deriving an estimate of non-erased systematic rows of the received packet;

code for comparing the non-erased systematic row with its estimate; and

code for identifying the location of a mismatched symbol between a non-erased systematic row and its estimate, wherein this codeword with undetected symbol errors is identified as corresponding to the column containing the mismatched symbol.

17. The computer program product of claim 16, wherein code for deriving an estimate of non-erased systematic rows of a received packet comprises:

code for marking the non-erased systematic row as an erased row;

code for forming a reduced received packet comprised of K non-erased rows of the received packet; and

code for multiplying an inverse of a generator matrix having K non-erased rows with the simplified received packet.

18. The computer program product of claim 15, wherein code for performing packet decoding comprises:

code for forming a reduced received packet comprised of K non-erased rows of the received packet;

code for forming a reduced generator matrix of K rows of the generator matrix corresponding to the K non-erased rows;

code for inverting the reduced generator matrix; and

code for multiplying an inverse of the generation matrix with the simplified received packet.

19. A memory coupled to a Digital Signal Processing Device (DSPD) capable of interpreting digital information to:

identifying a codeword corresponding to a column of the received packet in which the undetected symbol error is located;

determining the location of undetected symbol errors in a codeword;

marking a row of the received packet containing undetected symbol errors as an erased row; and

packet decoding is performed on the received packet with the erasure line marked.

20. The digital signal processor includes: a first unit operable to receive a block of symbols previously encoded column-wise using an (N, K) linear block code and row-wise using an error detection code, and to mark each row of the received block as an erased row or an unerased row until at least (K +1) unerased rows are found; and

a second unit operable to identify a codeword corresponding to a column of the received packet in which the undetected symbol error is located, determine a location of the undetected symbol in the codeword, mark a row of the received packet containing the undetected symbol error as an erased row, and perform block decoding on the received packet with the erased row marked.

21. The digital signal processor of claim 20, wherein the second unit is further operable to derive an estimate of a non-erased systematic row of the received packet, compare the non-erased systematic row to its estimate, and identify a mismatched symbol between the non-erased systematic row and its estimate, wherein the codeword with the undetected symbol error is identified as corresponding to the column containing the mismatched symbol.

22. The digital signal processor of claim 20, wherein the second unit is further operable to mark the non-erased systematic row as an erased row, form a reduced received packet consisting of K non-erased rows of the received packet, and multiply the reduced received packet with an inverse of a generator matrix having the K non-erased rows.

23. The digital signal processor of claim 20, wherein the second unit is further operable to form a reduced received packet comprised of K non-erased rows of the received packet, form a reduced generator matrix comprised of K rows of the generator matrix corresponding to the K non-erased rows, invert the reduced generator matrix, and multiply the inverted matrix of the generator matrix with the reduced received packet.

24. A decoder, comprising:

a first decoder operable to receive a block of symbols previously encoded column-wise using an (N, K) linear block code and row-wise using an error detection code, and to mark each row of the received block as an erased row or an unerased row until at least (K +1) unerased rows are found; and

a second decoder operable to identify codewords located in a column of the received packet corresponding to the undetected symbol error, determine the location of the undetected symbol error in the codewords, mark a row of the received packet containing the undetected symbol error as an erasure row, and perform block decoding on the received packet with the erasure row marked.

25. The decoder of claim 24, wherein the first decoder is operable to mark each row as an erased row or a non-erased row based on a result of a Cyclic Redundancy Check (CRC) test.

26. The decoder of claim 24, wherein the (N, K) linear block code is a Reed-Solomon code.

27. A decoding apparatus, comprising:

means for marking each row of a received packet previously encoded in a column-wise manner using an (N, K) linear block code and encoded in a row-wise manner using an error detection code as an erased row or a non-erased row until at least (K +1) non-erased rows are found;

means for identifying a codeword corresponding to a column of the received packet in which the undetected symbol error is located;

means for determining the location of undetected symbol errors in a codeword;

means for marking a row of the received packet containing undetected symbol errors as an erased row; and

means for performing block decoding on the received packet with the erasure line marked.

28. The decoding device of claim 27, further comprising:

means for deriving an estimate of non-erased systematic rows of the received packet;

means for comparing the non-erased systematic row with its estimate; and

location means for identifying symbols that do not match between the non-erased systematic row and its estimate, wherein this codeword with undetected symbol errors is identified as corresponding to the column containing the non-matched symbols.

29. The decoding apparatus of claim 28, wherein the means for performing packet decoding comprises:

means for marking non-erased system rows as erased rows;

means for forming a reduced received packet comprised of K non-erased rows of the received packet; and

means for multiplying an inverse of a generator matrix having K non-erased rows with the reduced received packet.

30. The decoding apparatus of claim 27, wherein the means for performing packet decoding comprises:

means for forming a reduced received packet comprised of K non-erased rows of the received packet;

means for forming a simplified generator matrix of K rows of the generator matrix corresponding to the K non-erased rows;

means for inverting the reduced generator matrix; and

means for multiplying the inverse of the generating matrix with the reduced received packet.

31. A receiver unit in a wireless communication system, comprising:

a receiver operable to process a received signal to provide data samples;

a demodulator operable to process the data samples to provide received packets of symbols;

a first decoder operable to mark each row of the received packet as an erased row or a non-erased row; and

a second decoder operable to identify a codeword corresponding to a column of the received packet in which the undetected symbol error is located, determine the location of the undetected symbol error in the codeword, mark a row of the received packet containing the undetected symbol error as an erasure row, and perform block decoding on the received packet with the erasure row marked.

32. The receiver unit of claim 31, further comprising:

a third decoder is operative to receive and decode demodulated data from the demodulator in accordance with a particular convolutional decoding scheme to provide received packets of symbols.