HK1032693B - Method and apparatus for matching a rate of data bits - Google Patents

Description

Rate matching method and device for data transmission

Technical Field

The present invention relates to rate matching and channel interleaving techniques for communication systems.

Background

It is known to interleave data in a communication system that employs Forward Error Correction (FEC) to make the error distribution uniform after deinterleaving to facilitate error correction. Typically, this interleaving uses a block interleaver to interleave each data block. So-called turbo coding (i.e., concatenated convolutional coding) utilizes an interleaver coupled between the inputs of two convolutional encoders that generate corresponding parity bits from input data before and after interleaving, respectively. With the growing interest in employing turbo codes, especially in wireless communication systems, attention has also been directed to the form of interleavers.

So-called third generation CDMA (code division multiple access) wireless communication systems are also under development. Such a system requires a channel or inter-frame interleaver that interleaves or permutes the data in blocks corresponding to the duration of a radio frame, typically 10 ms. In such a system, the channel interleaver may be configured before or after the rate matching function is performed. The rate matching function is used to match various data rates to the radio frame rate, typically requiring some data symbols, in this case data bits, to be reduced (deleted) or repeated. It is desirable that the erased or repeated bits be distributed as uniformly as possible within the deinterleaved frame, be spaced as widely as possible, and be easily implemented, relatively independent of variables such as frame length, number of frames, and puncturing rate.

Canadian patent application No.2,268,283, "Interleaver and method of Interleaving Data", filed on Men ton et al, 3/19/1999, proposes a method of Interleaving Data and a Data Interleaver that can be used to provide the above-mentioned channel Interleaving. The rate matching proposed by the present invention is particularly applicable to such channel interleaved data, but can also be used for other forms of interleaved data. The present invention also improves various applications of such channel interleaving.

Disclosure of Invention

In one aspect, the present invention provides a method of matching a rate of data bits to a desired rate by deleting some redundant data bits or repeating some data bits in a data bit matrix interleaved by a predetermined interleaving process, the method comprising the steps of: determining a pattern of bits that need to be erased or repeated within a matrix of non-interleaved data bits in order to provide the desired data rate; decoding the address of each bit in the bit pattern in a manner inverse to the interleaving process, resulting in a corresponding address of the bit within the matrix of interleaved data bits; and deleting or repeating corresponding bits of the interleaved data bits according to the address.

It is particularly advantageous and may in fact be necessary that the address decoding should be performed in the same way as the address encoding which generates interleaved data bits from a matrix of non-interleaved data bits. This is due in some preferred embodiments of the method of the invention to the use of

Line permutation I_r(K)＝[α_rK+f_c(I)]modN_r

Column permutation I_c(I)＝[α_cI+f_r(K)]modN_c

To a group consisting of N_rRow and N_cThe permutation of the rows and columns of the matrix, which is formed by columns and represents the data bits to be interleaved, is more convenient, wherein: i is_r(K) Representing a data bit with a row labeled K, K being from 1 to N_rInteger of (a), α_rIs an integer, f_c(I) Is a non-zero function of the index I, I being a number from 1 to N_cIs an integer of (1)_c(I) Representing a data bit, alpha, with a column denoted I_cIs an integer, f_r(K) Is a function of zero or the row index K, and modN_rAnd modN_cRespectively represent a modulus N_rAnd modulo N_cThe interleaved data bits are derived column by column from the matrix.

Such a choice is generally considered optimal: f. of_c(I)＝mI+[N_r+1]mod2, where: m is an integer, m being approximately equal to N_r/N_c，f_r(K)＝2K+[N_c+1]mod2 and α_rIs less than N_r/log₂(log₂(N_r) Maximum prime number of).

The invention also provides a rate matching device for executing the method.

In another aspect, the invention features a method of interleaving data bits, the method including interleaving a plurality of data bits with N_rRow and N_cThe rows and columns of the matrix of columns representing the data bits to be interleaved row by row

Line permutation I_r(K)＝[α_rK+f_c(I)]modN_r

Column permutation I_c(K)＝[α_cI+f_r(K)]modN_c

Carrying out a substitution, wherein: i is_r(K) Representing a data bit with a row labeled K, K being from 1 to N_rInteger of (a), α_rIs an integer, f_c(I)＝mI+[N_r+1]mod2 is a non-zero function of the subscript I, I being a number from 1 to N_cIs an integer of (1)_c(I) Representing a data bit, alpha, with a column denoted I_cIs an integer, f_r(K)＝2K+[N_c+1]mod2, and mod2, mod N_rAnd modN_cRespectively represent a mode 2 and a mode N_rAnd modulo N_cThe interleaved data bits are derived column by column from the matrix.

The invention also proposes a data interleaver for carrying out such a method.

Another aspect of the present invention provides a method of interleaving and matching concatenated convolutional encoded data by deleting encoded data bits, including coded bits of systematic bits and parity bits, including interleaving systematic bits separated from parity bits and deleting parity bits from the interleaved parity bits to provide rate matching.

In yet another aspect, the present invention provides a method of interleaving and rate matching concatenated convolutional encoded data by repeating encoded data bits including systematic bits and parity bits, the method comprising the steps of: interleaving systematic bits and parity bits, respectively; and repeating some of the interleaved parity bits by a repetition factor greater than some of any of the repeated interleaved systematic bits to provide rate matching.

The invention also proposes coding, interleaving and rate matching means to carry out these methods.

In yet another aspect, the present invention also relates to a method of shuffling some interleaved and rate matched data streams and applying this method recursively to the case of more than two such data streams in the manner described below in connection with fig. 4.

Drawings

The invention will be further understood from the following description in conjunction with the accompanying drawings. In these drawings:

fig. 1 illustrates a known configuration for traffic multiplexing and channel interleaving in a third generation CDMA communication system;

FIG. 2 is a flow chart relating to a known rate matching algorithm;

fig. 3 illustrates an implementation of an interleaver and rate matching apparatus according to an embodiment of the present invention;

FIG. 4 is a flow chart for the shuffle case for the second level of interleaving of FIG. 1, listed on the same page as FIG. 2; and

fig. 5 shows a portion of the configuration shown in fig. 1 modified for channel interleaving and rate matching of turbo (concatenated convolutional) encoded data.

Detailed Description

Referring to fig. 1, a known arrangement for traffic multiplexing and channel interleaving in a third generation CDMA radio communication system is illustrated. This arrangement includes a service multiplexer 10 for multiplexing together a plurality of data signal streams, referred to as primary traffic or QoS (quality of service) channels, respectively provided by service blocks 12 (only one of which is shown). Each service block 12 has a plurality of input constituent signals applied to its respective input 14, which may be any type of signal such as voice, data and multimedia signals, for example. These signals may have any transmission rate, frame length, and other parameters. These input signals are multiplexed together by a transport channel multiplexer 18 after having added respective CRC (cyclic redundancy check) codes in block 16. The multiplexed and combined signal is segmented by a segmentation block 20 and then FEC-encoded in FEC (forward error correction) encoding blocks 22, respectively. The encoded signals are multiplexed and combined by a multiplexer 24.

The multiplexed combined signal is subjected to rate matching processing (reduction (deletion) of redundant data symbols (bits) or repetition of data symbols (bits)) in block 26 so that the data rate matches the radio communication rate (spatial interface rate) with a frame duration of 10 ms. The data bits are interleaved by a first interleaver 28, the first interleaver 28 also being referred to as a channel or inter-frame interleaver, as it is used to permute blocks of 10ms data bits each, primarily to separate adjacent bits to reduce the deleterious effects of errors due to radio channel fading. Although interleaver 28 is shown in fig. 1 after rate matching block 26, the locations of these two functional blocks are interchangeable as will be explained below, with the multiplexed combined signal from multiplexer 24 being applied to channel interleaver 28 and the interleaved signal output by channel interleaver 28 being applied to rate matching block 26. For example, the two functional blocks may be in the order shown in fig. 1 for the case of downlink transmission of signals from one central station, and in the reverse order for the case of uplink transmission of signals to the central station.

After passing through the functional blocks 26 and 28, the resulting rate matched and interleaved signal is successively radio frame segmented and physical channel segmented by segmentation blocks 30 and 32, resulting in a signal that is multiplexed and combined by the multiplexer 10. The signal output by the multiplexer 10 is interleaved by a second interleaver 34, the output of which is mapped to dedicated physical channels after segmentation in a segmentation and mapping block 36 for transmission over the CDMA radio communications path in a well known manner.

The first interleaver 28 may have a sufficiently good performance such that the second interleaver 34 may omit or perform only a simple shuffling operation, for example as described below. This is desirable, particularly since the second interleaver 34 may otherwise degrade the performance of the interleaving performed by each of the first interleavers 28, which may be optimized for the respective rate-matched data streams and QoS.

The first interleaver 28 is therefore implemented in the form of an algebraic interleaver which provides good random spreading characteristics. A plurality of coding bit blocks or data transmission frames of each QoS channel are mapped into a two-dimensional matrix, and the rows and the columns of the matrix are replaced by linear congruence law, so that the interleaving function is realized. The maximum interleaving depth and time span can be determined by searching for an optimal set of parameters. Thus, the interleaver has a relatively simple form without the disadvantages of known interleavers such as the need for a large memory to store the look-up table or the inability to fully accommodate the rate matching function.

Although the following description is directed to rows and columns of a matrix, it should be noted that this is for convenience and clarity only and that the rows and columns can be interchanged without changing the function of the interleaver, which in fact, as described below, operates equivalently to control the read and write addressing of the memory cells of a linear memory storing data bits, without any actual movement of the stored bits between the memory cells.

As described in the previously incorporated by reference patent application, the interleaver 26 functions to perform the following three steps:

1. will N_cEach length is N_rA block of coded data bits of a data bit is represented as a block having N_rBehavior N_cA matrix of columns;

2. according to

Line permutation I_r(K)＝[α_rK+f_c(I)]modN_r

Column permutation I_c(I)＝[α_cI+f_r(K)]modN_c

Permuting the rows and columns of this matrix, wherein: i is_r(K) Representing a data bit with a row labeled K, K being from 1 to N_rInteger of (a), α_rIs a line permutation parameter which is an integer, f_c(I) Is a positive function of subscript I, I being a number from 1 to N_cIs an integer of (1)_c(I) Representing a data bit, alpha, with a column denoted I_cIs a column permutation parameter which is an integer, f_r(K) Is a positive function of the column index K, and modN_rAnd modN_cRespectively represent a modulus N_rAnd modulo N_cAn arithmetic operation of (1); and

3. the interleaved data bits are derived column by column from the matrix.

Step 1 may be slightly modified so that a given number of matrix columns can be adapted to different number of data transfer frames. For example, the number of columns N of the matrix_cThe data transfer frame number may be N ═ 8_cY, where y is 1, 2, 4 or 8, so the matrix has N_rY rows and step 3 is modified accordingly to read out the y columns of the matrix per radio frame. For simplicity of description, it is assumed that γ is 1, N_c＝8。

For step 2, the row permutation parameter α r is selected to be less than [ N_r/Iog₂(Iog₂(N_r))]Maximum prime number of, column permutation parameter α_cIs selected to be less than [ N ]_c]Maximum prime number of, function f_c(I)＝mI+[N_r+1]mod2 where m is one equal to [ N ]_r/N_c]And a function f_r(K)＝2K+[N_c+1]mod2 symbol.Is rounded down, andmeaning rounding up. It can be understood that [ N ]_r+1]mod2 at N_rIs equal to 0 when it is odd, and is equal to N when it is N_rEven numbers are equal to 1. Also, [ N ]_c+1]mod2 at N_cIs equal to 0 when it is odd, and is equal to N when it is N_cEven numbers are equal to 1. Thus, function f_c(I) And f_r(K) The two parts in (1) are simplified to be in corresponding N_rOr N_cAnd if the number is even, 1 is added.

As described above, rate matching reduces (deletes) some redundant data bits (bit redundancy due to the presence of the FEC coding block 22) when the length of the data transfer frame is greater than the length of the radio frame, with a maximum reduction ratio of 20% of the length of the radio frame. Conversely, if the length of the data transmission frame is less than the length of the radio frame, some bits in the transmission frame are repeated to achieve rate matching. It is desirable that the rate matching be as far apart as possible so that the distance between the punctured bits is maximized and so that the number of punctured bits in each radio frame is equalized, i.e., the punctured bits are evenly distributed within each radio frame and are spaced apart by the maximum distance.

In the case where the rate matching block 26 is configured before the channel interleaver 28 as shown in fig. 1, a known rate matching method as shown in fig. 2 may be employed.

Referring to FIG. 2, there is N for each score_iA radio frame of bit length, an integer y, y ═ N, is determined in block 40_r-N_i. Y is greater than 0 (positive) where reduction is required, less than 0 (complex) where repetition is required, and y is equal to 0 where neither reduction nor repetition is required. In the latter case, the flow proceeds to stop block 41. As can be seen from the various steps shown in fig. 2, the processing for bit repetition (y < 0, shown in the right branch of fig. 2) and for bit reduction (y > 0, shown in the left branch of fig. 2) is essentially the same, except that y and reduction are replaced by y and repetition, so only the reduction case is described in detail below.

If y > 0, N is required in the transmitted frame_rScaling y bits of the plurality of bits to produce N of the radio frame_iAnd (4) a bit. In this caseIn block 42, a parameter e is initialized to a starting offset e_0SIt is determined in any way that is required for this particular radio frame; and the row count gamma is initialized to 1. At block 43, it is determined whether γ ≦ N_r. If so, the value of e is subtracted by 2y at block 44. At a subsequent decision block 45 it is determined whether e ≦ 0. If so, the bit in line γ is decremented at block 46 and the value of e is incremented by 2N at block 47_rAfter the row counter γ is incremented by 1 at block 48, the decision block 43 is returned to. If the decision at block 45 is negative (i.e., e > 0), then the row counter γ is incremented by 1 via block 48 and returns to block 43 without any operation to decrement or change the value of e. If the decision at block 43 is negative (i.e., γ > N)_r) It indicates that the end of frame has been reached and flow proceeds to stop block 41 where it ends.

However, in the case where the rate matching block 26 is arranged after the channel interleaver 28, rate matching is performed on the permuted (interleaved) bit stream, and thus the rate matching problem is rather complicated. In general, the requirements of the channel interleaving and rate matching processes are not uniform.

Specifically, designing a suitable and optimized rate matching pattern that reduces or repeats bits within the channel interleaved bit matrix is a very complex or even impractical task. The present invention avoids this problem by providing a rate matching pattern for the matrix prior to interleaving that is appropriate and satisfies the optimization of the reduced or repeated bits, and then using a de-interleaving or decoding process to determine the corresponding bits that need to be reduced or repeated at the output of the channel interleaver. This process is facilitated because the de-interleaving or decoding process can be implemented with exactly the same structure as the interleaving process, as will be further described below. For convenience and clarity, the bit matrix before interleaving (or after deinterleaving) is referred to as a natural matrix NM and the bit matrix after interleaving is referred to as a randomized matrix RM in the following description.

FIG. 3 illustrates a channel interleaver 28 and a channel interleaver according to one embodiment of the present inventionImplementation of the rate matching block 26. As shown in FIG. 3, the interleaver 28 includes a working memory 50 divided into two halves which alternately hold read and write memories in a known manner, N in each half of the memory matrix_rN_cData bits that are linearly written into the memory in correspondence with the row-by-row structure of the matrix. Mode N_rThe line counter 51 counts according to the clock signal ClK and provides a reading representing the line index K. The carry output of counter 51 is fed to modulo N which provides a reading representative of the index I_cThe column counter 52. The readings K and I of the counters 51 and 52 are fed to an address encoder 53 enclosed by a dotted line in fig. 3. Specifically, the readings of the column counter 52 are fed to respective further parameters α_cAnd m multipliers 54 and 55, respectively, to produce a representation of alpha, respectively_cThe product of I and mI, and the reading of the line counter 51 is fed to the line counter which is also fed by the integer 2 and the parameter α, respectively_rRespectively, of multipliers 56 and 57, respectively producing the respective representations 2K and alpha_rThe product of K. Adder 58 adds the outputs of multipliers 54 and 56 according to N_cWhether even or odd is selectively added by 1 or 0 respectively, and the output of adder 58 is converted to modulo N by modulo function 59_cAnd thus the above column permutation is completed. Adder 60 adds the outputs of multipliers 55 and 57 according to N_rWhether it is even or odd, is selectively added with 1 or 0, respectively, and the output of the adder 60 is converted into modulo N by a modulo operation function 61_rForm, thereby completing the row permutation described above. Modulo function blocks 59 and 61 may each include comparison and subtraction functions. The outputs of the functional blocks 59 and 61 are combined in a read address combiner 62 into an address for reading the corresponding bit in the interleaved sequence from the memory 50. As shown in fig. 3, the read address is supplied to the memory 50 via a switch 63 configured as will be described below.

If the number of rows N_rBeing a power of 2, the address combiner 62 can take the output of the modulo function 61 as the low order bits of the read address to the memory 50 and the output of the modulo function 59 as the high order bits of the read address to the memory 50, which corresponds to the address combiner 62 taking the output of the function 61 and N_rOutput of multiplier function block 59And (4) adding.

It may be desirable to interleave other than N_cInteger multiples of data bits within an arbitrary length frame. In this case, the number of rows of the matrix is chosen to accommodate all the data bits to be interleaved, while the last few (less than N) rows in the memory 50_c) The memory cell is not written to. To omit the data bits of these memory locations from the interleaved data bits, the interleaver 28 of FIG. 3 also includes a decoder 64 for detecting the addresses of these memory locations in the read address output of the address combiner 62 and, upon detection, opening the switch 63 to prevent the data in these memory locations from being read from the memory 50. To ensure that the interleaved data bits from the memory 50 have a constant data output rate, the interleaver 28 of fig. 3 also includes a FIFO (first in first out) memory 65 clocked by the clock signal CLK, through which the interleaved data bits are fed to the interleaver output line 66. The FIFO 65 is pre-filled at the beginning of each interleaving operation, having a length sufficient to accommodate the data bits of the unreadable, and therefore ignored, memory cells (e.g., up to N at most_cOne bit).

The interleaved data bits on line 66 are sent to the rate matching block 26 also shown in fig. 3. This rate matching block comprises a rate matching address generator 70 to which a clock signal CLK is also applied, an address splitter 71, an address decoder 72, a buffer 73, a comparator 74 and a data bit selector 75, the rate matched data output being applied to a line 76. Similar to configuring FIFO 65 to ensure a constant data bit rate output by interleaver 28, rate matching block 26 may also include a FIFO or other buffer (not shown) to ensure a constant rate of data bits output by output line 76.

The rate matching address generator 70 generates at its output an address for each reduced or repeated bit in the natural matrix NM according to a reduced or repeated pattern determined for this process, as will be explained further below. This address is split by address splitter 71 into a more significant bit and a less significant bit portion, which is the inverse of the operation of read address combiner 62 described above. Due to the fact thatIf the number of rows is N_rBeing a power of 2, address splitter 71 can simply split the address bits output by generator 70 directly into higher order bits and lower order bits, which is equivalent to dividing the address from generator 70 by N_rAn integer quotient and a remainder are generated, respectively forming two outputs of address splitter 71.

The address decoder 72 performs the inverse operation of the address encoder 53. As indicated before, if the algebraic interleaving process described above is used, the structure of the deinterleaver and thus the address decoder 72 may be identical to the structure of the interleaver and thus the address encoder 53. Therefore, the structure of the address decoder 72 is not shown in detail in fig. 3, and is identical to the structure of the address encoder 53 shown in fig. 3. It will be appreciated that this same structural feature of the complementary operations of interleaving and deinterleaving is quite advantageous for achieving these functions, and may simplify implementation.

The output of the address decoder 72 is buffered by a memory 73 and fed to a comparator 74 which compares the current readings K and I of the row and column counters 51 and 52, respectively, of the channel interleaver 28 and applies a selector control signal to line 77 if the compared values are the same. Thus, such a selector control signal is generated and applied to line 77 whenever the bits on line 66 need to be reduced or repeated. For other times when it is not desired to reduce or repeat the bit, the control signal applied on line 77 controls the selector 75 to supply the bit supplied from line 66 to an intermediate input of the three inputs of the selector 75 (see fig. 3) to its output line 76 in synchronism with the clock signal CLK. Conversely, whenever a bit is to be repeated or reduced, the control signal on line 77 controls the selector 75 to pass a bit on either its upper or lower input (see FIG. 3) to its output line depending on whether it is to be repeated or reduced as determined by another control input P/R applied to the selector 75. The upper input of the selector 75 is connected to the output line 76 to provide a repeated bit, while the lower input of the selector is not connected and is therefore used to reduce the bit. As previously indicated, the data bits on output line 76 are provided to a buffer (not shown) so that the interleaved and rate matched data bits are output at a constant output data bit rate.

With address decoding provided by decoder 72 within rate matching block 26, rate matching address generator 70 can directly determine the desired reduced or repeated pattern from the normal matrix address in the manner described above in connection with FIG. 2, using a single parameter e determined in the desired manner_osThis mode is optimized. For example, this parameter may be in accordance with equation e_os＝[2py+1]mod2N_rWherein y is the number of bits per column of the matrix to be reduced or repeated and p is the column index from 0 to 7 of the matrix (for N), as previously explained_cIn the case of 8).

Tables 1, 2 and 3 below detail this example, interleaving 8 data transfer frames of 10 bits as described above, requiring a maximum reduction ratio of 20% to produce channel interleaved and rate matched radio frames of 8 bits each (16 bits reduced or erased in total out of 80 bits). Thus, N_cNot greater than 8, but N_r10. Table 1 illustrates the arrangement of the 80 data bits coded from 0 to 79 row by row into a 10 × 8 natural matrix with row labels K from 1 to 10 and column labels I from 1 to 8.

		1
										1	2	3	4	5	6	7	8
		K	1	0	1	2	3	4	5									6	7
2	8									9	10	11	12	13	14	15
			3	16	17	18	19	20	21								22	23
4	24									25	26	27	28	29	30	31
			5	32	33	34	35	36	37								38	39
6	40									41	42	43	44	45	46	47
			7	48	49	50	51	52	53								54	55
8	56									57	58	59	60	61	62	63
			9	64	65	66	67	68	69								70	71
10	72									73	74	75	76	77	78	79

TABLE 1

The randomization matrix obtained by the channel interleaving as described above is shown in table 2 below.

		1
										1	2	3	4	5	6	7	8
		K	1	57	40	79	62	45	28									11	74
2	35									18	1	64	23	6	69	52
			3	13	76	59	42	25	8								47	30
4	71									54	37	20	3	66	49	32
			5	73	56	15	78	61	44								27	10
6	51									34	17	0	39	22	5	68
			7	29	12	75	58	41	24								63	46
8	7									70	53	36	19	2	65	48
			9	9	72	31	14	77	60								43	26
10	67									50	33	16	55	38	21	4

TABLE 2

After rate matching as described above, the randomizer is reduced by 2 bits per column for a total of 16 bits, and the reduced randomizer is obtained from the pattern generated by the rate matching algorithm as followsAs shown in table 3:

		1
										1	2	3	4	5	6	7	8
		K	1	57	40	79	62	45	28										74
2	35									18	1		23	6	69	52
			3	13	76	59	42		8									30
4	71										37	20	3	66	49
			5	73	56	15	78		44								27	10
6	51										17	0	39	22	5
			7		12		58	41	24								63	46
8	7									70	53	36	19		65	48
			9		72		14	77	60								43	26
10	67									50	33		55		21	4

TABLE 3

The channel interleaved and rate matched data bits are read out from table 3 column by column, i.e. in the order [57, 35, …, 51, 7, 67, 40, …,26, 4 ]. The reduced bits are 2, 9, 11, 16, 25, 29, 31, 32, 34, 38, 47, 54, 61, 64, 68, and 75, the maximum reduction distance is 9(25-16), and the minimum reduction distance is 1(32-31), such a small minimum reduction distance indicating that this particular example is not optimal, it is desirable that the minimum reduction distance can be larger. It will be appreciated that many other ways of determining these parameters, particularly parameter eOS, can be used to optimize the reduction process.

As previously indicated, it is desirable that the operation of the second interleaver 34 not affect the performance achieved by the first interleaver 28. To this end, it is preferred that the second interleaver 34 be weakened to perform only a simple shuffle operation, interleaving data streams having different QoS, while maintaining the spreading characteristics achieved by the first interleaver 28 for each QoS data stream.

Fig. 4 shows a flow chart of a bit shuffling algorithm that can be advantageously used for interleaving the bits of two data streams of interleaved radio frames, derived as described above by respective traffic blocks 12, provided by the traffic multiplexer 10 in fig. 1. Suppose one has each a group of N₁The stream of frames consisting of one bit is TQ₁And the other has a structure of each of N₂The stream of frames consisting of one bit is TQ₂And N is₁≥N₂FIG. 4 shows a flow TQ₂How bits of stream TQ are inserted₁The case (1).

Referring to FIG. 4, initially, a parameter e is initialized to N at block 82₁And the counter gamma is initialized to 1. At block 83, a determination is made whether γ ≦ N₁If so, the value of e is decreased by 2N at block 84₂. At the next decision block 85, a determination is made as to whether e ≦ 0, and if so, at block 86 the flow TQ is passed₂Into the stream TQ₁Thereafter, the value of e is incremented by 2N at block 87₁The counter gamma is incremented by 1 at block 88 and then returns to decision block 83. If the decision at block 85 is negative (i.e., e > 0), then the counter γ is incremented by 1 via block 88 and the process returns to block 83 without any bit insertion or e value change operations. If the decision at block 83 is negative (i.e., γ > N)₁) This means that the end of the frame has been reached, whereupon the routine proceeds to the end of the stop block 81.

For the case of more than two data streams, the same procedure is applied recursively for subsequent ones of these data streams. As can be seen from the above description and the situation shown in fig. 4, the various steps of this process are directly related to the steps of the reduction and repetition process of fig. 2, so that it may be particularly convenient to implement such a recursive shuffle process.

As noted above, the reduction of bits to achieve the desired rate matching is applied to data bits that have redundancy due to the FEC encoding provided by encoder 22. One preferred form of encoding is the so-called turbo (concatenated convolutional) encoding, the encoded data bits comprising the input data bits themselves, referred to as systematic data bits S, and parity bits P1 and P2 provided by convolutional encoders operating on the input data bits and on the interleaved input data bits, respectively. Parity bits P1 and P2 are typically reduced within the turbo encoder to provide a turbo encoder with a rate that meets the requirements. For an encoder 22 consisting of a turbo encoder, it is necessary to ensure that the following rate matching block 26 does not scale down any systematic bits S, but only the parity bits P1 and/or P2. In the case of repetition, it has been determined that performance gains may be provided if the parity bits P1 and P2 repeat about 2 or 3 times the repetition of the systematic bits S.

To this end, a modified portion of the configuration of fig. 1 for channel interleaving and rate matching of data resulting from turbo coding is shown in fig. 5. Referring to fig. 5, a turbo encoder, which forms one of the FEC encoders 22, is shown within a block 90 enclosed by dashed lines. It includes a turbo code interleaver (turbo codeinterleaver)91 that interleaves the input data bits, and two convolutional encoders 92 that operate on the input data bits before and after interleaving, respectively, to produce parity bits P1 and P2, as is well known. The input data bits are also provided to the output of the encoder as systematic bits S. There may also be a reduction block (not shown) to select only some of the parity bits P1 and P2 to be provided to the encoder output.

Shown in fig. 5 is not a single channel interleaver as explained before, but individual channel interleavers 93 configured for the systematic bit stream and the parity bit stream, respectively. As shown in fig. 5, there are three channel interleavers 93, but it will be appreciated that since the streams of parity bits P1 and P2 can be merged together, only two channel interleavers need be configured, one responsible for the systematic bit stream and the other for the parity bit stream. The other inputs to the channel interleaver 93 in fig. 5 represent the systematic and parity bit stream multiplexing of multiple channels, corresponding to the multiplexer 24 in fig. 1.

The rate matching function block after the channel interleaver 93 is shown within the box 94 enclosed by the dashed line. The reduction function 95 performs bit reduction only on the channel interleaved parity bit stream, whereas the repetition function 96 may perform bit repetition on the parity and systematic bit streams, so that a selector 97 is shown coupling these channel interleaved bits accordingly. The reduction and repetition may be as previously described. It will be appreciated that the illustration in fig. 5 in this respect is merely a schematic representation of the principle of not reducing the systematic bits, and does not show the actual implementation of the rate matching function. It will also be appreciated that the reduction and repetition are performed on the parity bit stream only as needed to provide the required rate matching, for example, without any reduction or repetition of the systematic bit stream.

Although the above description refers to separate functions and units for the various processes described therein, it will be appreciated that in many cases these processes can be implemented using the functions of one or more digital signal processors or other integrated circuits.

While particular embodiments of the present invention have been described above, it should be understood that various modifications, changes and adaptations may be made therein without departing from the scope of the present invention as set forth in the claims.

Claims (8)

1. A method of rate matching for data transmission, the method matching the rate of data bits to a desired rate by deleting redundant data bits or repeating data bits derived from a matrix of data bits interleaved by an interleaving process, the method comprising the steps of:

determining a mode of bits to be deleted or repeated in the data bit matrix which is not interleaved according to the rate required to be matched;

decoding the address of each bit within the pattern to be deleted or repeated in a manner inverse to the interleaving process to produce a corresponding bit address within the matrix of interleaved data bits; and

deleting or repeating corresponding bits of the interleaved data bits according to the corresponding addresses.

2. The method of claim 1, wherein the pattern of bits to be deleted or repeated depends on the number of bits to be deleted or repeated per column and the column index within the matrix.

3. The method of claim 1, wherein said interleaving comprises the data bits to be interleaved being given row by a matrix of N_rRow and N_CColumn formation, the rows and columns of the matrix are performed as follows:

line permutation I_r(K)＝[α_rK+f_C(I)]modN_r

Column permutation I_C(I)＝[α_CI+f_r(K)]modN_CWherein: i is_r(K) Representing a data bit with a row labeled K, K being from 1 to N_rInteger of (a), α_rIs an integer, f_C(I) Is a non-zero function of the index I, I being a number from 1 to N_CIs an integer of (1)_C(I) Representing a data bit, alpha, with a column denoted I_CIs an integer, f_r(K) Is a function of zero or the row index K, and modN_rAnd modN_CRespectively represent a modulus N_rAnd modulo N_CThe interleaved data bits are derived column by column from the permuted rows and columns of the matrix.

4. A method as in claim 3 wherein f_C(I)＝mI+[N_r+1]mod2, m is an integer.

5. The method as set forth in claim 4, wherein m is approximately equal to N_r/N_C。

6. As in any one of claims 3 to 5The method of claim, wherein f_r(K)＝2K+[N_C+1]mod2。

7. A method as claimed in any of claims 3 to 5, wherein α is_rIs one less than N_r/log₂(log₂(N_r) Maximum prime number of).

8. A rate matching apparatus for matching a rate of data bits to a desired rate by deleting redundant data bits or repeating data bits derived from a matrix of data bits interleaved by an interleaver, the apparatus comprising:

an address generator (70) for determining the address of the bits to be deleted or repeated within the matrix of unentangled data bits, according to the rate of required matching;

a decoder (72) for decoding the bit addresses to be deleted or repeated in a manner inverse to the interleaving process to provide corresponding bit addresses in the interleaved data bit matrix; and

a selector (75) for deleting or repeating respective ones of the interleaved data bits according to the respective addresses.