IMPROVED RATE MATCHING BASED ON REVERSE INTERLEAVING AND REVERSE RATE MATCHING

Technical Field

The invention relates to rate matching a bit stream output from a channel encoder to a data transmission rate on a physical transmission channel.

Background

Prior to transmitting data on a physical transmission channel, the data is typically subjected to channel encoding. For example, mobile terminals conforming to the 3GPP (3rd Generation Partnership Project) LTE (Long Term Evolution) mobile communication standard use either Turbo Coding or Convolution Coding of rate 1/3. To allow flexible coding rates, a rate matching may be applied to the encoded data provided by the channel encoder before a transmission over the physical transmission channel. The rate matching adapts the number of bits output from the channel encoder to the number of bits that can be transmitted on the physical channel. Thereto, bits of the encoded data may be repeated or bits may be punctured to generate a requested number of bits according to a desired code rate that may be different from the mother code rate of the encoder.

Operations to be performed by the rate matching may be prescribed. For above- mentioned LTE devices, the rate matching is described in 3GPP Technical Specification, TS, 36.212, current version 1 1 .2.0, in the following simply being referred to as TS 36.212. As specified in section 5.1 .4 of TS 36.212 and depicted in Fig. 1 a, the rate matching function 14 basically transforms successive code or data blocks of consecutive bits d _r ^l _l (wherein code block index r is indicative of a code block number generated by a channel coding function 10 and buffered in a so-called code block buffer 12, into rate-matched output data blocks of consecutive bits ek. The rate matched data blocks may be stored in an output buffer to be fetched by a transmitting function for transmitting the data onto the physical channel.

In the following only one exemplary code block of the successive code blocks r will be regarded; thus for the sake of simplicity, the code block index will not be shown in the following. As shown in Fig. 1 b, according to LTE, the code block d\ to be rate matched, in the following also being referred to as input code block or input sequence, comprises three information bit streams or sub blocks d? , d and df each of sub block length D (I = 0,1 ,2,...,D-1 ) said blocks being referred to as systematic, parity-1 and parity-2 sub blocks respectively. Thus, the entire bit sequence shows a length 3D. The rate matched output sequence ek shows a length E (k=0,1 ,2,...,E-1 ).

Fig. 1 c shows the different rate matching sub functions in more details. The rate matching essentially comprises dummy bit insertion functions 141 , 141 ' and 141 " associated to each one of the systematic, parity-1 and parity-2 sub blocks and corresponding sub block interleaving functions 142, 142' and 142". Further a bit collection function 143 and a bit selection function 144 is comprised.

The dummy bit insertion functions 141 , 141 ' and 141 " insert a certain number (>=0) of dummy bits into each of said sub blocks of length D up to a length K. According to above-cited TS 36.212, the dummy bits are inserted, if needed, at the beginning (left side) of the blocks and the bits of the input sequences are shifted accordingly to generate each length-adjusted sub blocks d _d ^l _bi ior i=0,1 ,2. Adjusted sub block bit index dbi runs from 0 to K-1 .

The sub block interleaving functions 142, 142' and 142"perform each an interleaving of the adjusted sub blocks to generated interleaved sub blocks d _s ' _bi each for i=0,1 ,2. Adjusted sub block bit index sbi accordingly runs from 0 to K-1 . The bit collection function 143 collects all interleaved sub blocks into one virtual circular buffer having a length of 3K.

The bit selection block 144, selects a number of E bits from the virtual circular buffer bits to generate the rate matched output. Bit selection basically comprises a defined puncturing of bits (can be systematic, parity-1 , parity-2, depending on the applied redundancy version) in order to adapt the data rate to the capacity of the physical channel. Thereto, a certain section of the virtual output buffer may be chosen for the output. As part of this selection, dummy bits, which have been inserted at earlier stages are to be identified and pruned. Although 3GPP standards, e.g. the above-described 3GPP document, prescribe a data transformation to be performed for the rate matching, 3GPP does not prescribe an implementation thereof. An efficient implementation may take care to minimize an introduction of latency in the data transformation process, and/or of a usage of resources required for the rate matching e.g. memory usage or processor usage. European patent application EP 2150001 of the same applicant proposes a method that efficiently uses memory resources at low latency introduction. Thereto, before transmitting one or more code blocks on the transmission channel, bit positions of the dummy bits with respect to the output buffer are pre-calculated. While performing the rate matching algorithm, the calculated positions are used for early pruning of the dummy bits. Therewith, storage of dummy bits in the output buffer can be avoided, allowing keeping the output buffer size small.

Summary

It is an object of the present invention to provide a further improced rate matching implementation. This object is achieved by the independent claims. Advantageous embodiments are described in the dependent claims.

According to an embodiment, a rate matching is performed with respect to an input sequence of bits to generate an output sequence comprised of bits of the input sequence, wherein the number of bits to be assigned to the output sequence is chosen according to a given matching rate (e.g. in cases of high coding rates with good radio channel conditions, a subset of the input bits may be chosen with almost 1/3 of the number of bits of the input sequence). An algorithm is applied that calculates a bit position of the input sequence as a function of the bit position of the output sequence, and assigns the corresponding input bit to the output sequence at the bit position of the output sequence.

As described above, rate matching according to LTE comprises performing the functions of an insertion of dummy bits, a block interleaving, and a bit selection (comprising a pruning of the previously inserted dummy bits) according to LTE specifications so that eventually a certain number (e.g. a subset) of the input bits are assigned to the output sequence at prescribed bit positions. However, said functions are to be performed irrespective of the matching rate and thus the number of output bits to be selected from the input sequence. It is an insight of the invention that it may be avoided to perform unnecessary calculations by providing a reverse algorithm based the rate matching functions in such a way that for each position of the output sequence, the corresponding input bit position is determined. This is especially advantageous in cases where only a rather small part of the output bits have to be selected. In a worst case two third of the bits are punctured, meaning that two third of the processing is wasted for unnecessary calculations with a forward approach. Thus the invention allows to perform only absolutely necessary calculations. As an advantageous effect, usage of processing resources and time as well as storage resources are minimized.

The rate matching function may be described as to insert a number of dummy bits so that a resulting adapted input sequence (or each adapted sub sequence of a number of sub sequences as will be described later) fits to a matrix or block tor interleaving. As for the interleaving the block must be filled having a prescribed number of rows and columns, the length of the adapted input sequence equals to the product of the number of rows and the number of columns. The interleaving results into an interleaved sequence, While the inserted dummy bits are usually inserted en-block, e.g. at the beginning of the sequence, the dummy bits after interleaving are scattered over the interleaved sequence. A significant task of the bit selection function is to identify the dummy bits and to pruning such bits before assigning to the output sequence. The invention proposes to perform the following steps to detect the input bit to be assigned to the output sequence at a certain position within the output sequence:

• determine a bit position within the interleaved sequence of the bit to be assigned to the certain position of the output sequence,

• determine the corresponding bit position within the adapted input sequence (by applying a reverse function with respect to the interleaving function),

• determine the corresponding bit position within the input sequence (by applying a reverse function with respect to the dummy bit insertion function). In a variation, for performing the reverse rate matching, a counter is employed to run from an initial value (e.g. "0" pointing to the most left bit of the output sequence) to a target value (e.g. "E-1 " pointing to the most right bit of the output sequence) according to the chosen number of E bits. For each of these counter values, the corresponding bit of the input sequence is identified and assigned to the output sequence at the corresponding position.

In a further variation, the input sequence is a result of a 1/3 turbo coding e.g. according to TS 36.212, section 5.1 .3.2. Such input sequence comprises three sub sequences, the sub sequences comprising a systematic sub sequence, a first parity sub sequence and a second parity sub sequence. Above explained dummy bit insertion and interleaving is performed separately for each of said sub-sequences. After performing these functions separately a bit collection is performed prior to the bit selection. Each input bit is thus identified by an index i indicative to an adherence to one of the sub-sequences and an index I indicative of the bit position within each of said sub-sequences. Determining the input bit to be assigned to a certain position of the output sequence may comprise determining the indices i and I, in the following also being referred to as index pair (i,l).

Above-described functions may be implemented in a radio transmitter and/or in a radio receiver, especially according to above-cited TS 36.212. Such radio transmitter and/or radio receiver may be incorporated in to a mobile station and/or a base station.

The present invention also concerns computer programs comprising portions of software codes in order to implement the method as described above when operated by a respective processing unit of a user a mobile station or a base station. The computer program can be stored on a computer readable medium. The computer- readable medium can be a permanent or rewritable memory e.g. within said node or device. The respective computer program can be also transferred for example via a cable or a wireless link as a sequence of signals.

In the following, detailed embodiments of the present invention shall be described in order to give the skilled person a full and complete understanding. However, these embodiments are illustrative and not intended to be limiting. Brief Description of the Figures

Figs. 1 a-c show block diagrams of a rate matching function according to TS

36.212,

Fig. 2 shows an exemplary block diagram of a rate matching implementation according to the invention,

Fig. 3 shows an exemplary flow diagram of the rate matching implementation,

Fig. 4 shows a sub function of Fig. 3 in more details,

Fig. 5a-d show exemplary mathematical equations with respect to Fig. 4,

Fig. 6 shows a block diagram of an exemplary radio receiver comprising a rate matching according to the invention, and

Fig. 7 shows an exemplary communication arrangement with a mobile station and a base station employing a rate matching according to the invention.

Detailed Description

As discussed above, Fig. 1 a illustrates a transmitter comprising an encoding circuit 10 representing a channel encoding stage and a rate matching stage 14. It is exemplarily assumed in the following that the transmitter 1 is implemented in a mobile terminal adapted for communication with an LTE mobile network, so that the rate matched data may be stored in a physical output buffer of the mobile terminal to be transmitted on a radio uplink channel of a radio interface between the mobile terminal and a base station -eNodeB- of an the LTE access network.

The channel encoding stage 10 encodes a number of C bits, C being the number of bits to encode, into a number of D bits, D being the number of encoded bits per output stream. The relation between the bits to be encoded and the encoded bits and the relation between K and D is dependent on the channel coding.

As described in the introduction, TS 36.212, section 5.1 .3, prescribes a coding rate of 1/3. According to section 5.1 .3.2, if the encoding stage performs turbo encoding, above cited index i runs from 0 to 2 three information streams are generated that may be denoted as information bit streams d\ , wherein the sub block index i = 0 denotes a first bit stream, also being referred to as systematic bit stream, sub block index i = 1 denotes a second bit stream, also being referred to as parity-1 bit stream, and sub block index i = 2 denotes a third bit stream, also being referred to as parity-2 bit stream, and sub block bit position index I denotes a bit position in each of said sub blocks.

As mentioned in the background, for LTE the functions of the rate matching 14 are prescribed in TS 36.212, comprising inserting dummy bits into the information bit streams, performing sub block interleaving with respect to each information bit stream, bit collection of the interleaved blocks in a virtual buffer and bit selection, whereby a number of E bits are selected from the 3K collected bits.

Straightforward implementation may suggest calculating all the 3K bits to be collected in physical buffer resulting from the rate matching steps as aforementioned. The collected 3K bits may then be used as basis for the selection and pruning operation. However as the number E of the bits to be selected may be far smaller than the number of 3K bits; a significant number of collected bits (in the virtual buffer) are not used for the further processing. Consequently, the straight forward solution may require more resources than necessary.

The invention proposes a solution that does not apply a dummy bit insertion, a (sub-) block interleaving and a bit selection (and hence does not need to realize the virtual buffer) but that applies said functions in a reverse way for each bit position of the output sequence, a bit position of the input sequence is determined, and assigned to the output sequence at the bit position of the output sequence

Thereto, Fig. 2 shows an exemplary block diagram illustrating a new rate matching 24 in the following also being referred to as rate matching block or function 24, an input code block buffer 12 that may be correspond to code block buffer 12 of Fig. 1 a, and an output ode block buffer 16. The rate matching block 24 comprises a first interface 241 coupled to the input code block buffer 12, a bit calculation function block 242, a bit reading function block 244, a bit assigning function block 246 and a second interface 247 coupled to the output code block buffer 16.

The rate matching block 24 is connected, over the interface 241 , to the code block buffer 12 mentioned earlier to receive input code blocks or sequences generated by a channel (en)coding stage 10 to be transformed into rate matched output code blocks or sequences. As discussed previously, the encoded code blocks may be coded by a 1/3 ratio by generating three sub blocks d\ (i=0,1 ,2; 1=0,1 ,2,...,D-1 ) said blocks being referred to as systematic, parity-1 and parity-2 sub blocks respectively. Thus the length of the entire input code block has a length of 3D. Depending on a requested bit rate at the physical channel of the transmitter, the rate matching circuit selects a certain number of bits of each input code block, e.g. selecting a subset by puncturing corresponding bits (E<3K).

The bit calculating function block 242 determines all the positions of the bits of the input code block that shall form the output code block based on the desired bit rate.

The bit reading function block 244 reads all those bits from the input code block that shall be further used for transmission on the physical channel by a transmitting function not shown in Fig. 2.

The bit assigning function block 246 assigns the bits read by the bit reading function 244 to be stored to the output code block buffer 16.

Fig. 3 shows an exemplary implementation embodiment of rate matching block 24 performing a recursive algorithm controlled by a counter. The counter is tied to the output sequence such that the counter runs through a value range that corresponds to the output sequence size, i.e. from 0 to E-1 . Each counter value is associated to the bit position of the output sequence, e.g. counter value k=0 is associated to the first (or most left) bit of the output sequence, k=1 is associated to the right adjacent bit and k=E-1 is associated to the last (or most right) bit of the output sequence. Thereto, in a first function block 341 , the counter is initialized e.g. by setting the counter to zero.

A second function block 342 comprises a determination of the input bit to be assigned to the output sequence at the bit position that corresponds to the actual counter value k. As each bit of an input code block is uniquely identified by its indices i and I, determining the bit positions comprises determining the corresponding index pair (i,l) of said input bits.

A third function block 343 comprises reading the input identified by the index pair (i,l) from the code block buffer 12. A fourth function block 344 comprises assigning the read bit to the output sequence at the position corresponding to the value k.

A fifth function block 345 comprises a decision function whether the value k is equal E-1 . In the affirmative, all E bits are assigned and the rate matching is finished for the current code block. Otherwise, this function block branches to a sixth function block 346.

The sixth function block 346 increments the counter value k and refers back to the second function block 342.

The following Fig. 4 describes an exemplary embodiment of the second function block 342, in the following also being referred to as index calculation (function) block. As discussed previously the index calculation function 342 determines the index pair (i,l) as a function of the counter value k.

In a first sub function block 41 (of index calculation function block 342), it is determined whether the actual counter value equals zero. In the affirmative, this sub block diverts to a second sub function block 42. Otherwise, this sub block diverts a third sub function block 43.

In a second sub function block 42, a further counter value be associated to the virtual circular buffer as discussed in the introductory section is initialized, e.g. by setting this counter to an initial value k ₀ wherein k ₀ may be a function of the redundancy version number (rv _id x = 0, 1 , 2, 3) according to TS 36.212, section 5.1 .4.1 .2 . Each value of this counter, in the following being referred to as circular buffer bit position counter, is associated (or points to) one bit position of the virtual circular buffer.

In a third sub function 43, the circular buffer bit position counter value be is incremented.

After processing of either sub function 42 and 43, a fourth sub function 44 is executed by determining the sub block index value i and a bit position index of the interleaved sub blocks 142, 142' or 142" according to Fig. 1 c, in the following being referred to as interleaved sub block index sbi, as a function of the actual circular buffer bit position value be. In a subsequent fifth sub function 45, a bit position index of the adjusted or non- interleaved sub blocks 142, 142' or 142" according to Fig. 1 c, in the following being referred to as non-interleaved sub block index dbi is calculated as a function of the interleaved sub block index sbi.

In a subsequent sixth sub function 46, an intermediate bit index I ^* is calculated as a function of the non-interleaved sub block index dbi.

In a subsequent seventh sub function 47, it is determined whether the intermediate bit index I ^* is smaller than 0. In the affirmative, the index results are dropped and the flow is diverted back to third sub function block 43. Otherwise, the intermediate bit index value I ^* is chosen as sub block bit position bit index value I, that forms together with sub block index value i the index pair (i,l) uniquely identifying the input bit to be assigned to the output sequence as discussed above.

In the following figures, exemplary mathematical equations are shown for a rate matching as specified in TS 36.212.

Fig. 5a shows an exemplary calculation of a number of N _D dummy bits o be inserted as a function of the number of columns C ^TC rows R ^TC of sub blocks matrices according to section 5.1 .4.1 .1 . of TS 36.212.

Fig. 5b shows an exemplary calculation of the sub block index value i and the bit position index sbi as a function of actual circular buffer bit position value be according to fourth sub function 44 of Fig. 4. Fig. 5c shows an exemplary calculation of non-interleaved sub block index dbi as a function of interleaved sub block index sbi according to fifth sub function 45 of Fig. 4 and corresponding to table 5.1 .4-1 of TS 36.212.

Fig. 5d shows an exemplary calculation of intermediate bit index I ^* as a function of non-interleaved sub block index dbi and number N _D of dummy bits previously calculated according to sixth sub function 46 of Fig. 4

As can be seen from previous figures, the proposed rate matching allows for efficiently using processing and memory resources, as only such bits are calculated, that are to be used for further transmitting. It is further not necessary to calculate any dummy bit positions in advance to the selection process.

The technique described herein furthermore allows to minimize memory space required by a rate matching as no bits need to be stored intermediately.

In the preceding figures, the rate matching has been described with respect to a radio transmitter especially employed in an LTE mobile station (LTE UE) or in an LTE base station (eNodeB). In such device or node, the rate matching performs a data rate adaptation between an encoding stage and a transmitting stage dependent on capabilities or resources of the radio channel between the mobile station and the base station. However, above-described rate matching functions may be as well applied in a corresponding radio receiver. Thereto, Fig. 6 shows a radio receiver 60 comprising a first set of functions to detect or decode the bits that have been encoded in the corresponding transmitter. Thereto, the first set of functions comprise a symbol update function 61 , a soft bit de-mapping function 62, a rate de-matching function 63 and a channel decoding function 64 that are carried sequentially to calculate the decoded bits from the received symbols.

The radio receiver further comprises a second set of functions that calculate feedback information from the decoded bits to be provided to the symbol update function 61 . Thereto the second set of functions comprises a channel re-encoding function 65, a receiver rate matching function 66 and a receiver soft symbol mapping function 67 carried out sequentially to calculate the feedback information as a function of the decoded bits. The receiver rate matching function 66 may be similar or implemented according to above-described rate matching function 24.

Fig. 7 shows a communication arrangement comprising an exemplary mobile station 71 , and base station 72. Thereto, the mobile station 71 comprises a first radio transmitter 71 1 and a first radio receiver 712, wherein one of the radio receiver and the radio transmitter or both of them may employ a rate matching function 24 as described above. Similarly the base station comprises a second radio transmitter 721 and a second radio receiver 722, wherein one of the radio receiver and the radio transmitter or both of them may employ a rate mating function 24 as described above. The mobile station 71 1 mav be a user equipment, UE, according to 3GPP LTE specifications. Correspondingly, the base station 721 may be a so-called evolved node B, eNB, according to 3GPP LTE specifications.