Incremental redundancy with resegmentation

Different transmissions based on different content blocks which were segmented from the same digital content according to different segmentation schemes, where each of the content blocks has any substring in common with at least one of the other content blocks, are received by a receiving radio communication station, for example a mobile telephone or a mobile network base station. Certain encoded received bits derived from different ones of the transmissions are combined into combined bits. Other encoded received bits derived from one or more of the different transmissions are provided together with the combined bits to a decoder.

BACKGROUND

Enhanced General Packet Radio Service (EGPRS), also known as Enhanced Data rates for GSM Evolution (EDGE), is a digital mobile telephone technology that allows data transmission rates to be increased and improves data transmission reliability.

Two types of an error control method known as Automatic Repeat-reQuest (ARQ) are used in EGPRS, as described in 3GPP TS 43.064—3rdGeneration Partnership Project; Technical Specification Group GERAN; Digital cellular telecommunications system (Phase 2+); General Packet Radio Service (GPRS); Overall description of the GPRS radio interface; Stage 2 (Release 5). When a block of data has not been correctly received, the sending entity resends the block of data. The sending entity may be the network or a mobile telephone. The receiving entity may be the network or a mobile telephone. In the first type, blocks of coded data that the receiving entity is unable to successfully decode are resegmented and retransmitted. The receiving entity decodes each retransmission in isolation from the previous transmissions. In the second type, Type II Hybrid ARQ, also known as incremental redundancy (IR), if the receiving entity is unable to successfully decode a block of coded data, that block is retransmitted using a different puncturing scheme. The received bits from the different transmissions are combined to aid the decoding.

It is expected that blocks are not resegmented when using incremental redundancy. Indeed, the EGPRS specifications provide for a “resegment” bit in ARQ control to prevent resegmentation when the network employs incremental redundancy.

It will be appreciated that for simplicity and clarity of illustration, elements shown in the figures have not necessarily been drawn to scale. For example, the dimensions of some of the elements may be exaggerated relative to other elements for clarity.

DETAILED DESCRIPTION

FIG. 1is a block diagram of an exemplary radio communication system100. System100comprises a communication station102and a communication station104able to communicate over radio communication channels106. In the following description, communication station102acts as a sending station and communication station104acts as a receiving station. For example, station102may be a mobile network base station and station104may be a mobile telephone, and transmissions from station102to station104are considered to be downlink communications. However, the following description is equally applicable to uplink communications, which would be the case, for example, if station104were a mobile network base station and station102were a mobile telephone. It should be noted that the mobile telephone may have additional capabilities and may use the mobile network to transmit and/or receive non-telephonic data.

Station102comprises a content source108that produces digital content. The digital content is segmented into blocks by a content block segmenter110according to a particular block segmentation scheme. In some contexts, the content block is known as the payload. Prefix bits and suffix bits are appended to each content block, and the content block with appended bits is then encoded by an encoder112according to a particular coding scheme. For example, encoder112may use a convolutional code without recursiveness.

The encoded block is then punctured by a puncturer114according to a particular puncturing scheme. For example, each third bit of the encoded block may be deleted. The output of puncturer114is referred to as channel bits, which are provided to a transmitter116. As is known in the art, transmitter116puts the channel bits into a form that permit their communication upon radio frequency (RF) channels and cause the communication of the channel bits upon the RF channels via an antenna118. For example, transmitter116may comprise upconverters, modulators, a power amplifier, and other components.

Briefly,FIGS. 2A and 2Bare illustrations of different exemplary segmentations of digital content into content blocks and the appending of prefix bits and suffix bits to the content blocks.FIG. 2Ashows a content block1, which prior to encoding, has appended to it (as indicated by an arrow202) with prefix bits P1and suffix bits S1. A different segmentation of the same digital content into two separate content blocks, content block1A and content block1B, is indicated by an arrow204. Content block1is identical to a concatenation of content block1A and content block1B. Content block1A is a proper substring of content block1, i.e. content block1A is wholly contained in content block1. Likewise, content block1B is a proper substring of content block1. Moreover, no portion of content block1is common to content block1A and content block1B, i.e. content block1A and content block1B are non-overlapping. For example, content block1may comprise 256 bits of digital content, content block1A may comprise the first 128 bits of that digital content and content block1B may comprise the second 128 bits of the digital content. Resegmentation of a single content block into two non-overlapping content blocks of equal size (or in a few cases, almost equal size), each of which is a proper substring of the single content block, and the reverse case (concatenation of two equal-sized content blocks into a single content block) are the only forms of resegmentation permitted in the EGPRS specification. Prior to encoding, content block1A has appended to it (as indicated by an arrow206) prefix bits P1A and suffix bits S1A, which differ from prefix bits P1and suffix bits S1, respectively. Likewise, prior to encoding, content block1B has appended to it (as indicated by an arrow208) prefix bits P1B and suffix bits S1B, which differ from prefix bits P1and suffix bits S1, respectively. The prefix bits in EDGE are just a couple of bits of control information that, for some reason, were not included in the header of the content block. The number of suffix bits depends on the size of the cyclic redundancy check (CRC). Even if content block1A and content block1B are identical, prefix bits P1A could differ from prefix bits P1B, and suffix bits S1A could differ from suffix bits S1B.

FIG. 2Bshows content blocks2,3and4and an exemplary resegmentation (indicated by an arrow212) of the digital content of those blocks into content blocks11,22,33and44. Content block11comprises a portion of the digital content of content block2. Content block22comprises portions of the digital content of content blocks2and3. Content block33comprises portions of the digital content of content blocks3and4. Content block44comprises a portion of the digital content of content block4and a portion of the digital content of another content block (not shown). The segmentation of the digital content into content blocks2,3, and4results in the appending of prefix bits P2, P3, and P4, respectively, and of suffix bits S2, S3, and S4, respectively, to those content blocks prior to encoding. Likewise, the segmentation of the digital content into content blocks11,22,33and44results in the appending of prefix bits and suffix bits to those content blocks prior to encoding. Content block22has appended to it prefix bits P22and suffix bits P22, which differ from prefix bits P2and suffix bits S2, respectively. Content block33has appended to it prefix bits P33and suffix bits P33, which differ from prefix bits P3and suffix bits S3, respectively. Content block44has appended to it prefix bits P44and suffix bits P44, which differ from prefix bits P4and suffix bits P4, respectively.

Briefly,FIG. 3is an illustration of an exemplary block of data and the matrix of encoded bits generated therefrom. A block300has N bits, which includes the prefix bits, the bits of the content block, and the suffix bits. In the example shown inFIG. 3, a convolutional code with a constraint length K and a rate of 1/R is used by encoder112to encode block300. A convolutional code of rate 1/R has R generator polynomials, G0, G1, . . . , GR-1, and encoder112produces a matrix302of encoded bits with R rows, each row i being the output of generator polynomial Gi. In general, the value of the mthbit in block300affects the values of the encoded bits in columns m through m+K-1of matrix302, where m is an index that runs from 0 to N-1.

Consider, for example, that the first 4 bits of block300are prefix bits, and that the last 6 bits of block300are suffix bits. Then the bits of columns0through3+K-1are all affected by the prefix bits, and the bits of columns N-6through N-1+K-1are all affected by the suffix bits. However, the bits of columns4+K-1through N-7are unaffected by the prefix bits or the suffix bits.

Puncturing is the process of deleting bits of encoded data to reduce the data transmitted. For example, the puncturing scheme used by puncturer114may delete every third bit of matrix302, starting at the top left corner and counting the bits column by column. The deleted bits are indicated inFIG. 3as shaded boxes of matrix302. Although in this description, puncturing and depuncturing are performed in stations102and104, respectively, the technology described herein is equally applicable to cases where no puncturing or depuncturing is performed.

Returning toFIG. 1, station104comprises a receiver120to detect RF signals via an antenna122and to downconvert the received signals to baseband levels. Additional operations not separately illustrated are performed. For example, soft decision operations are also performed on the received data. For example, the output of the soft decision operator may be that there is a 45% probability that a particular received bit is a 1 and a 55% probability that the particular received bit is a 0. Although in this description, soft decision operations are performed on the received data in station104, the technology described herein is equally applicable to cases where hard decision operations are performed on the received data in station104prior to depuncturing and/or combining.

The soft received bits are provided to a depuncturer124, which inserts erasures at the appropriate locations in the stream of received bits to fill in the gaps created by puncturer114. The output of depuncturer124may be considered a matrix similar to matrix302ofFIG. 3, in which each matrix element that was deleted by puncturer114is replaced by an erasure and each matrix element that was not deleted by puncturer114is replaced by a soft decision regarding a received bit.

The output of depuncturer124, possibly combined by a combiner126with selected contents of one or more buffers128, is provided to an error-correcting decoder130. Decoder130attempts to decode its input and corrects any errors which can be corrected. If there are too many errors, they cannot be corrected. An error checker132checks whether decoder130was successful in decoding the received block. If so, the successfully decoded bits are provided to upper layers, represented as a content sink134. The combination of the output of depuncturer124with the selected contents of one or more of buffers128may occur before each decoding, or may only occur after a first decoding attempt without combining is unsuccessful. One reason to make a first decoding attempt without combining is that the selected contents of one or more of buffers128may be of such poor decodability that combining the selected contents with the output of depuncturer124may impair the decoding of the output of depuncturer124. Methods of combining used by combiner126may include, for example, numerical summation of soft decisions for corresponding bits or averaging of a corresponding stored soft decision value with a new soft decision value.

System100implements a feedback scheme so that sending station102is informed whether transmissions of encoded data to receiving station104are successfully decoded. For example, an ACK/NACK (acknowledgment/negative acknowledgment) scheme may be used, where a positive acknowledgment, ACK, is generated at station104and transmitted to station102in the event that the output of decoder130is accepted by error checker132, and where a negative acknowledgement, NACK, is generated at station104and transmitted to station102in the event that the output of decoder130is rejected by error checker132. Therefore, station104has a transmitter136which enables the ACK/NACK indication to be transmitted to station102via antenna122. The ACK/NACK indication is received in station102via antenna118by a receiver138. In another example, positive acknowledgment may be assumed unless a negative acknowledgment is received by station102within a certain period of time following transmission of the encoded data. In that example, only NACKs are generated at station104and transmitted to station102when appropriate. In yet another example, negative acknowledgment may be assumed if a positive acknowledgment has not been received by station102within a certain period of time following transmission of the encoded data. In that example, only ACKs are generated at station104and transmitted to station102when appropriate.

Receipt of a NACK indication may result in a retransmission by station102of the content block that was not successfully received by station104. Rather than retransmitting the same content block with a different puncturing scheme, one or more different content blocks may be transmitted, where the digital content of the content block that was not successfully received is comprised in the one or more different content blocks. In other words, the detected NACK indication is provided to a baseband component140, which may change how content block segmenter110segments the digital content.

It should be noted that resegmentation is just one possible response to receipt of a NACK indication. In the event that the sending entity chooses to resegment, the technology described herein allows incremental redundancy combining to be used to improve decodability. For example, consider the case where, due to excessive errors, first encoded received bits derived from a first transmission cannot be decoded by an error-correcting decoder. If the sending entity chooses to resegment, second encoded received bits may be derived from a second transmission, where the first transmission is based on a first content block segmented from digital content according to a first block segmentation scheme and the second transmission is based on a second content block segmented from the same digital content according to a second block segmentation scheme that differs from the first scheme, and where the first content block and the second content block have a substring in common. It may happen that, due to excessive errors, the second encoded received bits also cannot be decoded by an error-correcting decoder. However, if the technology described herein is implemented, combining into combined bits selected ones of the first encoded received bits and corresponding selected ones of the second encoded received bits, where the correspondence is based on the encoded bits being related to the same portion of the substring, may counteract the effect of some of the errors. Therefore, providing the others of the first encoded received bits along with the combined bits to the error-correcting decoder may enable successful decoding, which means that the bits of the first content block can be accurately determined. Likewise, providing the others of the second encoded received bits along with the combined bits to the error-correcting decoder may enable successful decoding, which means that the bits of the second content block can be accurately determined.

Various tests could be designed to check whether the technology described herein has been implemented and is operating properly. A stream of encoded bits could be designed to have so many errors that it cannot be successfully decoded by an error-correcting decoder. In one test, for example, two such streams are designed, each stream representing a different content block segmented from the same digital content according to a different segmentation scheme, where the two content blocks have a substring in common. Each of the streams designed for the test represents a content block in the sense that it represents the received encoded bits that would be the output of a process involving appending prefix bits and suffix bits to that content block, encoding the block having the appended bits, possibly puncturing the encoded block, transmission of the resultant channel bits over one or more RF channels, reception of RF signals, downconversion of the received RF signals to baseband levels, determination of encoded bits and possibly depuncturing. Although neither of the streams can, independently of the other, be successfully decoded by the error-correcting decoder, the streams are designed so that once combined, as described herein, the combined encoded bits together with the uncombined encoded bits of one of the streams can be successfully decoded by the error-correcting decoder, thus enabling the accurate determination of the bits of the content block that was represented by that stream.

Any appropriate resegmentation scheme may be used. For example, the digital content of the content block that was not successfully received may be divided into two or more smaller content blocks, each of which is a proper substring of the original content block and none of which overlap. In another example, the digital content of the content block that was not successfully received may be concatenated with other digital content and included in a single content block. In yet another example, the digital content of the content block that was not successfully received may be included in two or more other content blocks, not all of which or none of which are proper substrings of the original content block.

When resegmentation is employed, the prefix bits and the suffix bits appended to the new content block(s) are not identical to the prefix bits and the suffix bits appended to the original content block, as explained hereinabove with respect toFIGS. 2A and 2B. Consequently, even if the new content block is a proper substring of the original content block, and both blocks, after having prefix bits and suffix bits appended thereto, are encoded using a convolutional code at the same rate 1/R and the same constraint length K, the bits in columns of the resulting matrices of encoded bits that are affected by the prefix bits and/or by the suffix bits will be different, as explained hereinabove with respect toFIG. 3.

In general, employing resegmentation means that the original content block and the new content block are not identical and have a “substring” of digital content in common. The new content block may be a proper substring of the original content block, or the original content block may be a proper substring of the new content block. It may be that the new content block is not a proper substring of the original content block and that the original content block is not a proper substring of the new content block. It may be that one of the content blocks (original or new) is a proper substring of the other content block, but that the complement of the substring in the other content block is not contiguous in the other content block.

It is generally accepted that the matrices of encoded received bits resulting from different segmentations of the same digital content are so different from one another that they must be decoded in isolation from one another. That is the reason that the EGPRS specifications provide for a “resegment” bit in ARQ control to prevent resegmentation when the network employs incremental redundancy. However, the inventor has discovered that if the length of the substring in common between the differently segmented content blocks is at least as long as the constraint length K, then—barring any distortion due to the transmission over the radio channel and ignoring the effects of different puncturing schemes—the bits of at least one column in the matrix of encoded received bits for the original transmission ought to be identical to the bits of at least one column in the matrix of encoded received bits for the retransmission.

Combiner126may store the output of depuncturer124in buffer128, either always or only if the output of decoder130is rejected by error checker132. If the output of decoder130is accepted by error checker132, error checker132may instruct buffer128to delete a stored block when all the content data in that block has been successfully decoded, in order to make room for storing other blocks. When receiving another transmission based on a content block at least a substring of which is identical to a substring of the content block on which the previously received block was based, combiner126will combine the received block after depuncturing with those portions of the buffer contents that were unaffected by the prefix bits and the suffix bits and any new content bits adjacent to the common content substring, thereby providing additional information to decoder130. If error checker132still rejects the output of decoder130, despite the additional information, then the combined block on which the decoding was done, or portions thereof, may be saved in buffer128for further combining with subsequent retransmissions. Saving the combined block in buffer128may overwrite previously stored copies of received blocks (or portions thereof) having substrings in common with the combined block. Alternatively, whole received blocks after depuncturing may be stored in buffer128in their entirety and combiner126may perform multi-way combinations of different overlapping substrings when a new block is received. This latter implementation may require significant memory and processing resources.

Columns of different received matrices are considered to correspond to one another if they represent the encoding of the same bits of digital content.

FIG. 4Aillustrates exemplary received matrices resulting from the encoding, puncturing, transmission, reception and downconverting of content blocks1,1A and1B ofFIG. 2A. Content blocks1,1A and1B are shown inFIG. 4Awith an indication of their content bits. Once the prefix bits and suffix bits are appended to content blocks1,1A, and1B, the process of encoding, puncturing, transmission, reception and downconverting is indicated by arrows402,404and406, respectively.

A received matrix412corresponds to content block1, a received matrix414corresponds to content block1A, and a received matrix416corresponds to content block1B. The “b” position markers on the matrices indicate the first column that the corresponding content bit “b” starts affecting the output. Note that this column would also be affected by the preceding K-1bits of the segmented block, whether these bits are other content bits or prefix bits. Hatched columns418are the columns of matrix412that are unaffected by prefix bits P1and/or suffix bits S1, for example, columns20through240. Hatched columns420are the columns of matrix414that are unaffected by prefix bits P1A and/or suffix bits S1A, for example, columns18through116. Hatched columns422are the columns of matrix416that are unaffected by prefix bits P1B and/or suffix bits S1B, for example, columns22through112. Therefore lightly shaded columns424of matrix412and lightly shaded columns426of matrix414correspond to the same bits of digital content. Likewise, darkly shaded columns428of matrix412and darkly shaded columns430of matrix416correspond to the same bits of digital content. In this example, columns420and426are identical and columns422and430are identical.

Therefore, if decoder130is unable to successfully decode matrix412, then when station104has received matrix414, combiner126updates received matrix414so that each bit in columns426is replaced by a combination of the bit and the corresponding bit in columns424. Then decoder130decodes updated matrix414and performs error correction, if possible. Likewise, when station104has received matrix416, combiner126updates received matrix416so that each bit in columns430is replaced by a combination of the bit and the corresponding bit in columns428. Then decoder130decodes updated matrix416and performs error correction, if possible. Alternatively, station104may attempt to decode matrix414and matrix416independently and may only combine one or both of those matrices with matrix412if the independent decoding is unsuccessful.

In the reverse case, where the initial transmissions resulted in the receipt of matrix414, which was not successfully decoded, and the receipt of matrix416, which was not successfully decoded, and the resegmentation and retransmission resulted in the receipt of matrix412, then combiner126updates received matrix412so that each bit in columns424is replaced by a combination of the bit and the corresponding bit in columns426, and so that each bit in columns428is replaced by a combination of the bit and the corresponding bit in columns430. Then decoder130decodes updated matrix412and performs error correction, if possible. It should be noted that station104may combine matrix414and matrix412and perform decoding on the combined matrix even without the receipt of matrix416. It should also be noted that station104may combine matrix416and matrix412and perform decoding on the combined matrix even without the receipt of matrix414.

FIG. 4Billustrates exemplary received matrices resulting from the encoding, puncturing, transmission, reception and downconverting of content blocks3,22and33ofFIG. 2B. Content blocks3,22and33are shown inFIG. 4Bwith an indication of their content bits. In this example, bit indices h, i, j, l and m satisfy the following condition: h<i<j<l<m. Once the prefix bits and suffix bits are appended to content blocks3,22and33, the process of encoding, puncturing, transmission, reception and downconverting is indicated by arrows442,444and446, respectively.

A received matrix452corresponds to content block3, a received matrix454corresponds to content block22, and a received matrix456corresponds to content block33. Hatched columns458are the columns of matrix452that are unaffected by prefix bits P3and/or suffix bits S3. Hatched columns460are the columns of matrix454that are unaffected by prefix bits P22and/or suffix bits P22. Hatched columns462are the columns of matrix456that are unaffected by prefix bits P33and/or suffix bits S33. However, only the latter part of content block22has digital content in common with content block3, and only the initial part of content block33has digital content in common with content block3. Therefore, only lightly shaded columns464of matrix452and lightly shaded columns466of matrix454correspond to the same bits of digital content. Likewise, only darkly shaded columns468of matrix452and darkly shaded columns470of matrix456correspond to the same bits of digital content.

FIG. 5is a flowchart of an exemplary method that may be implemented in combiner126, decoder130and error checker132. At501, combiner126identifies which buffered matrix (or matrices) has columns that correspond to columns in a currently received matrix of received bits. The correspondence of columns arises from the columns being related to the same bits of digital content. At502, combiner126selects columns of the buffered matrix (or matrices) and of the currently received matrix of received bits, where each pair of corresponding selected columns is unaffected by prefix bits and/or by suffix bits and/or by other adjacent content bits present in one segmentation but not the other. At504, combiner126updates the currently received matrix by combining bits of its selected columns with the bits of corresponding selected columns of the buffered matrix. At506, the updated matrix is decoded using error-correction by decoder130. At508, error checker132checks whether decoder130has successfully decoded the updated matrix.

FIG. 6is a flowchart of another exemplary method that may be implemented in combiner126, decoder130and error checker132. At601, combiner126identifies which buffered matrix has columns that correspond to columns in a currently received matrix of received bits. The correspondence of columns arises from the columns being related to the same bits of digital content. At602, combiner126selects columns of the buffered matrix and of the currently received matrix of received bits, where each pair of corresponding selected columns is unaffected by prefix bits and/or by suffix bits and/or by other adjacent content bits present in one segmentation but not the other. At604, combiner126updates the buffered matrix by combining bits of its selected columns with the bits of corresponding selected columns of the currently received matrix. At606, the updated matrix is decoded using error-correction by decoder130. At608, error checker132checks whether decoder130has successfully decoded the update matrix.

FIG. 7is a flowchart of yet another exemplary method that may be implemented in combiner126, decoder130and error checker132. This method involves updating the currently received matrix, decoding the updated received matrix and error checking as described above with respect to the method ofFIG. 5, and updating the buffered matrix and decoding the updated buffered matrix, and error checking as described above with respect to the method ofFIG. 6. At710, station104may then compare the decoding outputs. At712, station104may select the decoding output that, according to the comparison, has the best results. An example of a metric for determining the best results is which result enables more bits of the received data to be successfully decoded. Specifically, the metric may be which result advances the sliding window the most.

An example of how to identify columns that can be combined is as follows. Given two input blocks, A and B, to the encoder112, where A is a string of M bits a0, a1, . . . , aM-1, and B is a string of N bits b0, b1, . . . , bN-1, and each block is analogous to block300inFIG. 3, and there exists a common substring of L bits, L at least as large as constraint length K, starting at index i in block A and index j in block B, then the bits in column i+K-1+h of the encoded matrix for A and the bits in column j+K-1+h of the encoded matrix for B can be combined, for h running from 0 to L-K. Each of the encoded matrices is analogous to matrix302inFIG. 3.

The example of encoder112using a convolutional code without recursiveness has been described. However, the technical description provided above is also applicable, with certain modifications, to systems in which encoder112uses a turbo code. Turbo codes use recursive convolutional codes but also send systematic bits which are semi-static during retransmissions. Referring again toFIG. 3, it was stated above that in general, the value of the mthbit in block300affects the values of the output bits in columns m through m+K-J of matrix302, where m is an index that runs from 0 to N-1. Specifically in the case of turbo codes, the mthbit in block300affects different rows of matrix302in different ways. On the recursive rows, the mthbit affects output bits in all of the column positions. On the systematic rows, the mthbit affects only the bit at column m. Therefore, the exemplary matrices shown inFIGS. 4A and 4Band the accompanying description are applicable to turbo codes if it is assumed that the matrices contain only systematic rows (the recursive rows having been stripped out) and that the constraint length K is 1. Combining bits of received blocks after depuncturing prior to decoding therefore ought to be applied only to systematic bits (i.e. bits of the systematic rows, but not necessarily all of the bits of the systematic rows). The recursive bits (i.e. bits of the recursive rows, but not necessarily all of the bits of the recursive rows) used along with the updated systematic bits in the decoding may be obtained either from the initial transmission or from the retransmission. It is also possible to decode twice—once with the recursive bits from the initial transmission and once with recursive bits from the retransmission, to compare the decoding outputs, and to select the decoding output that has the best results. An example of a metric for determining the best results is which result enables more bits of the received data to be successfully decoded. Specifically, the metric may be which result advances the sliding window the most. When an initial transmission is not successfully decoded and resegmentation occurs at the sending entity, the sending entity may transmit only the new recursive bits and only the systematic bits which could not already be in the receiver's buffer from a previous segmentation.

The example of how to identify columns that can be combined, provided above, applies in the case of turbo codes if one considers for combining only the bits on the systematic rows of the encoded matrices and one takes K to be 1 for those rows.