Method and apparatus for encoding and decoding data

[0001] The present invention relates generally to data encoding and decoding, and in particular to a method and apparatus for turbo data encoding and decoding.

Prior art [0002] Digital data transmissions in wired and wireless connections can be distorted, for example, by noise on a link or channel, by interference from other transmissions, or by other environmental factors. To combat errors introduced through a channel, many telecommunications systems use error correction techniques to support communication. [0003] One of the techniques used in error correction is the turbo-coding of the information block to be transmitted. Using this technique, the encoder in the telecommunications system transmitter encodes the input block with a length of K bits into a block of code words x with N bits. This block of x code words is then transmitted by a channel, possibly after further processing such as channel interleaving as defined in the IEEE 802.16e specifications. In the turbo receiver, the decoder takes the received signal vector y with the length N as input and generates an estimate u of the vector u.

[0004] Typically, the turbo coder consists of two constituent convolutional encoders. The first component encoder gets the input block u as input in its original order, and the second component encoder gets the input block u interlaced after passing u through the turbo inter interleaver. X turbo output

PAT-1191-EP-E

EP2080271 encoder is composed of systematic bits (equal to input block u), parity bits from the first component encoder and parity bits from the second component encoder.

[0005] Accordingly, the turbo decoder in a telecommunications system receiver is composed of two component convolutional decoders, one in each of the component codes. The component decoders are separated by a p-interleaver^-1. Messages in the log-likelihood ratios (LLR) format are sent between the component decoders iteratively. The decision is made after several iterations.

[0006] The Turbo interleaver p is a key component in turbo code construction. It is responsible for mixing the input block u in a pseudo-random way, thus providing the code words x good weight distribution, and therefore good error correction capabilities. In addition to decoding speed, the turbo p interleaver has a significant impact on the implementation of the turbo decoder in the receiver. Usually, the turbo code speed improves as the interleaver length increases. However, increasing the interleaver's elongation increases less and less. In practice, the maximum block size of Forward Error Correction (FEC) (i.e., the interleaver size) in the turbo code is limited to a certain size due to the complexity and delays. Hence, if the size of the input block (concatenated transport block:

Concatenated Transport Block (CTB) is larger than the maximum size of the FEC block supported by turbo code, then the CTB block is divided into segments (e.g. by applying a rule

PAT-1191-EP-E

EP2080271 code block segmentation) into several smaller segments, each of which is processed separately by the turbo encoder at the transmitter and respectively by the turbo decoder at the receiver.

[0007] In some turbo systems, the code may for various reasons be designed to support only a few FEC block sizes (e.g. high decoding speed, reduced memory demand, etc.). Therefore, a turbo-coding and decoding method and device are needed which, respectively matches CTB with the available FEC block sizes.

[0008] MOTOROLA, FRANCE TELECOM, GET AND ORANGE: "EUTRA FEC Enhancement" TDOC R1-061050 OF 3GPP TSG RAN WG 1 MEETING # 44BIS, March 27, 2006 (2006-03-27), - March 31, 2006 (2006-03 -31) pp 114, XP002475873 Athens, Greece, concerns turbo-coding for 3GPP CDMA telecommunications systems.

Short description of the drawing [0009]

Fig. 1 is a block diagram of a transmitter.

Fig. 2 is a block diagram of a receiver.

Fig. 3 is a block diagram of the turbo encoder of Fig. 1.

Fig. 4 is a block diagram of a transport block maker on the transmitter side.

Fig. 5 is a block diagram of the transport block assembler on the receiver side.

Fig. 6 is a block diagram of the transmitter of Fig. 1.

Fig. 7 is a block diagram of the receiver of Fig. 2.

PAT-1191-EP-E

EP2080271

Detailed description of the drawing [0010] In order to meet the above-mentioned need, the method and apparatus for turbo coding and decoding are shown below.

[0011] In one embodiment, a concatenated transport block (CTB) of length X is received and from the group of non-adjacent FEC block sizes two block sizes between Kmin and Kmax are determined, where Kmin <= KI-1 <Kmax, Kmin <= KI <= Kmax and where in addition KI-1 and KI are based on X. The concatenated transport block of length X is divided into C segments each with a size substantially equal to KI-1 or KI. For each of the C segments the FEC code word is determined using the FEC KI or KI-1 block sizes and the FEC code words are transmitted by channel.

[0012] An advantage of the above method is that in order to encode CTB, less padding with the smallest number of segments allowed by the available non-adjacent FEC block sizes is needed. In particular, this method uses two different (but adjacent) FEC block sizes to minimize the number of padding bits using the smallest number of segments allowed by the non-adjacent FEC block sizes. Furthermore, FEC block sizes for segment sizes and number of segments can be determined using simple logic circuits.

[0013] Before describing data encoding and decoding, the following definitions are provided to provide the necessary basis:

PAT-1191-EP-E

EP2080271 · For ease of writing, a concatenated transport block refers to the results of concatenating one or more transport blocks, after adding a header such as CRC bits to each transport block.

· X denotes the size of the concatenated transport block (e.g. length of the concatenated transport block in bits).

· Y denotes the total number of padding bits added to the concatenated transport block.

· C denotes the number of segments into which the concatenated transport block has been divided.

· CBSSi means the size of the ith segment of the concatenated transport block (i = 1, ..., C), where C is the size of the segment. CBSS is the abbreviation for Code Block Segment Size.

· KI-1 and KI denote FEC block sizes (e.g., sizes for which turbo interleavers are defined) that can be used to encode FEC segments of a concatenated transport block.

· Ktable denotes the set of available non-independent FEC block sizes (sizes for which an internal turbo interleaver is defined).

· Kfiller means the number of padding bits added to a segment.

· R stands for the basic rate of the turbo encoder code (e.g. R = 1/3 for Turbo 3GPP Code).

· R^-1 is the inverse of the tempo of the basic turbo encoder code (e.g. R^-1 = 3 for Turbo 3GPP Code).

PAT-1191-EP-E

EP2080271 · Ntb is the number of terminal bits in the FEC codeword at the output of the FEC encoder. In particular, with Ntb = 12 for turbo 3GPP code with end bits with Ntb = 0 for turbo 3GPP tail-biting code.

· Marks the internal turbo code interleaver.

· The Floor [x] operation is the largest integer not greater than x, and the Ceiling [x] operation is the smallest integer not less than x.

[0014] Turning now to the drawings, where the reference numerals indicate the elements in question, FIG. 1 is a block diagram of an exemplary transmitter 100 useful for understanding the invention. As shown, the transmitter 100 includes a code block segmenting circuit 102, padding circuit 103, turbo encoder 104, padding rejection circuit 105, transmitter 108, logic circuit 106 and table / memory 107. The transmitter 100 further includes a receiver circuit (not shown in FIG. 1) which receives a concatenated transport block of length X. Logical circuit 106 determines the available Kl size of the FEC block from the group of 107 non-adjacent FEC block sizes, in which the available non-adjacent FEC block sizes are between Kmin and Kmax, where Kmin <= KI <Kmax , and where Kl is additionally based on X. The segment 102 dividing code blocks divides the concatenated X-length transport block into segments of substantially equal KI sizes; coding circuit 104 determines the FEC code word for each of the C segments using the KI size of the FEC code block. Finally, transmission circuit 108 transmits C FEC code words over the channel.

PAT-1191-EP-E

EP2080271 [0015] In one embodiment, the transmitter 100 includes a receiving circuit (not shown in FIG. 1) that receives a concatenated X transport block, logic circuit 106 that specifies two available FEC KI-1 and KI block sizes from a group of independent sizes FEC blocks 107, in which the available non-adjacent FEC block sizes are contained between Kmin and Kmax, where Kmin <= KI-1 <Kmax, Kmin <= KI <= Kmax, and where KI-1 and KI are additionally based on X. Transmitter 100 includes a block segmentation circuit 102 that divides a X-length concatenated transport block into C segments with sizes substantially equal to KI-1 or Kl, and a coding circuit 104 that specifies the FEC code word for each of the C segments using FEC KI block sizes or KI-1. Finally, transmission circuit 108 is provided that transmits C FEC code words over the channel.

[0016] Coding circuit 104 is preceded by padding 103, which inserts padding bits into segments to form an FEC input block. The FEC encoder 104 encodes the FEC input block, and the complement rejection circuit 105 rejects the corresponding complement bits.

[0017] During operation of the transmitter 100, data in the form of a concatenated transport block is received by the circuit 102. Circuit 102 prepares the concatenated transport block before performing the FEC encoding.

[0018] In general, the CTB (i.e. X) size range may differ from the FEC block size range supported by the FEC scheme at the physical layer for the telecommunications system. Therefore, it is necessary to define a rule that divides CTB into

PAT-1191-EP-E

EP2080271 segments that can be successfully processed by FEC. In particular, the CTB (i.e. X) sizes are often much larger than the maximum FEC block size that can be processed by the encoder 104. Therefore, the CTB must be divided by the circuit 102 into a number of smaller segments, and each segment must be encoded by the FEC 104 encoder in separate FEC code words.

[0019] Circuit 102 uses a code block segmentation rule designed to obtain good speed (i.e., total segment speed for a given CTB) with a given FEC. For each given size, the CTB includes the following aspects:

Choice of the number of segments C.

Selecting the size of each segment.

Inserting padding bits before FEC encoding and removing padding bits after FEC encoding, if the segment size cannot be handled directly by FEC.

[0020] The proposed segmentation rules are particularly useful in the Evolved-UMTS Terrestrial Radio Access (EUTRA) system in which the turbo encoder can only be defined for a limited set of FEC block sizes (interleaver sizes). Unlike Version 6 Turbo 3GPP Encoder, which defines 5075 interleavers with adjacent sizes, one for each Kl interleaver size between 40 bits and 5114 bits, the turbo EUTRA encoder can define a limited number of FEC K block sizes_table (e.g. 40 - 50 interleavers of independent sizes in the range from 128 to 6144 bits) to cover a large number of segment sizes (e.g. 6144 1191-PAT-EP-PL

EP2080271

128 + 1 = 6017 sizes). When the segment size is equal to the available FEC block size, this segment can be taken directly as an FEC input block (and therefore without the need to insert padding bits). However, if the segment size is not equal to any of the available FEC block sizes, padding bits can be used and Ktable 107 will select the next larger available FEC block size (i.e. interleaver size) for use.

Number of segments:

[0021] In the segmentation rules, the following turbo coding properties are considered:

a) The turbo code speed improves as the FEC block size increases.

b) The increase in turbo code speed by increasing the FEC block size decreases after exceeding several thousand bits.

c) CTB is received correctly only if all segments are received correctly.

[0022] Properties (a) and (c) indicate that the overall performance will probably be determined by the performance of the slowest segment. So it's good to have segments that are approximately equal in size so that FEC encoding is done at roughly equal FEC block sizes (and therefore at roughly equal error protection levels from a FEC perspective).

[0023] Property (b) suggests that it is not necessary to provide interleavers for very large sizes in the table (Ktable). However, the FEC block sizes specified in Ktable may depend on others

PAT-1191-EP-E

EP2080271 factors. For example, i) to reduce the complexity of memory, a small number of interleavers in the Ktable table may be desirable, and ii) the maximum size of the interleaver defined in Ktable can be selected to limit the number of segments on a CTB, which leads to a reduction in the cost of a given CTB. The cost of segmentation means a loss of speed due to dividing the CTB into several segments instead of coding the entire CTB into one FEC code word. [0024] Property c) suggests that as few segments as possible should be used to reduce the cost of segmentation, [0025] Taking all this into account, the number of segments is C = [X / Kmax], where Kmax is the maximum size of the FEC block defined in the Ktable array. Assuming that CBSSi means the size of the ith segment (i = 1, ..., C) of the concatenated transport block, the sum of all the segments is equal to the size X of the concatenated transport block, i.e. the sizes of the segments are limited by the following equation.

C

Σ CBSS_and = X i = 1 [0026] The next chapter describes determining the FEC block size used for FEC encoding, one for each segment size C.

Determining the FEC block size [0027] Since the CTB with the length X is given to the function blocking the code block, the rule determining the FEC block size (interleaver size) for the turbo encoder as described in Version 6 of the 3GPP standard is as follows:

PAT-1191-EP-E

EP2080271

C = k / K max 1

K_AND = max (40, ~ -V / C1), (1)

Y = CK_AND - X

where Kmax = 5114 is the maximum interleaver size for Turbo Code version 6, C is the number of segments (i.e. code blocks), KI is the interleaver size, and Y is the total number of padding bits inserted into the X size CTB when C FEC input blocks are used with size K. In short, CTB with size X is divided into C segments of roughly equal sizes and each segment is encoded using turbo code with a KI bit interleaver. If Y> 0, then Y known bits are added at the beginning of the first segment before coding. Because FEC block sizes (i.e. interleavers) are specified for all sizes between Kmin = 40 and Kmax = 5114 in version 6 turbo of 3GPP code, the number of padding bits is limited by C, i.e. the number of segments used to divide the code block into segments.

[0028] However, in other systems, such as the system considered for EUTRA, FEC block sizes (interleaver sizes) can only be specified for non-adjacent sizes (a "coarser split" set of interleaver sizes) Ktable. In these cases, segment sizes that are not equal to any of the available FEC block sizes (i.e. not specified in Ktable) must be supported using padding bits before FEC encoding (and cleaned after encoding to obtain the desired code speed) [0029] Assuming that the turbo encoder only supports a limited number of FEC block sizes distributed between Kmin and Kmax inclusive

PAT-1191-EP-E

EP2080271 inclusive, two simple ways to split the code block into segments for a concatenated X-length transport block using Ktable will be described below. These methods use the minimum possible number of segments, and the number of padding bits required for coding is also reduced.

Only one FEC block size possible [0030] One example method useful for understanding the invention is to modify (1) and allow all segments to be encoded using a single KI interleaver, where ¹ = ^arg Ki sń 7 -^{Λ /} C i) '(2) where and such that 1 <= i <= T indexes the group of non-adjacent FEC block sizes available in the Ktable table, assuming that the T sizes in the Ktable table are sorted in ascending order. In short, this method selects the smallest KI with Ktable not less than [X / C], i.e. KI = [X / C] + δ, where 0 £ d <K_AND - K_I-1 and KI-1 <[X / C]. Note that KI-1 = 0 is required when I = 1. Therefore, the number of padding bits is given by

Y = CK_AND - X = C (X / C1 + J) -X (3) [0031] Therefore, Y is large when δ is large. The following examples illustrate how the number of available FEC (Ktable) block sizes affects Y.

If K_table contains all values ​​between Z_min = 40 and Zmax = 5114, the largest number of padding bits is equal to C - 1.

If K_table contains T = 100 values ​​evenly distributed between Zmin = 40 and Zmax = 5114, then

PAT-1191-EP-E

EP2080271 the maximum total number of padding bits added to all segments is approximately equal to 50 X C.

[0032] Hence, the number of padding bits can be controlled by changing the granularity of the FEC block size in the Ktable table. The number of padding bits may also be using a different approach, as described in the text. However, before discussing this method, it should be noted that in the general case of Table K_table you can choose any K_AND (> [X / C]) for FEC encoding at the expense of potentially increased number of padding bits. In this case, the segment sizes obtained after dividing the code blocks into segments meet the CBSS_and £ K_AND for i = 1, .., C. In this case, logic circuit 106 determines the number of segments using the following relation

C = [X / Kmax 1

Possible two adjacent FEC block sizes [0033] In this implementation, instead of using one FEC KI block size to encode all segments of a given CTB, it is proposed to select two adjacent FEC block sizes from the Ktable table, namely KI-1 and KI, where KI-1 <KI, 1 <= I <= T. It should be noted that when I = 1, it is necessary KI-1 = 0. The number of C segments and the larger FEC KI block size are still selected to be identical as in the previous case, ie. C is still calculated as in (1), and KI is still calculated as in (2). However, the number of segments encoded with KI-1 size and KI size are determined as follows (for ease of understanding, all calculations are repeated below). In this case the circumference

PAT-1191-EP-E

EP2080271 Logic 106 performs the following operations to find the number of segments

C = Γ * / K max 1 = Ci + C-1,

Y = C KI - X,

D, = K, - K, -1, (4)

C, -1 = Iz / D, and C, = c - Lr / d, ii CI-1 and CI are the numbers of segments that are encoded using FEC block sizes KI-1 and KI, respectively, where KI is the smallest size among available FEC block sizes not less than [X / C], and DI means the difference between adjacent sizes of the KI-1 and KI interleaver.

[0034] It should be noted that in (4) Y does not indicate the number of complementary bits required when two adjacent sizes are allowed, but indicates the number of complementary bits required when only one size KI is used for all C segments.

[0035] Thus, the code block division forms C segments, of which the CI-1 segments are FEC encoded with the FEC block size KI-1. It should be noted that when Y <DI, (4) gives CI-1 = 0 and this method degenerates to use one FEC block size equal to KI (i.e. size KI-1 is allowed but not used). On the other hand, when Y> = DI, this method requires fewer padding bits than when all C segments are completed to a larger FEC KI block size. This method is optimal in that the number of Y '' complementary bits added to the CTB is guaranteed at the smallest level using the smallest possible number of segments. Y '' is determined as follows:

PAT-1191-EP-E

EP2080271

Y '' = CI-1KI-1 + CI KI - X, (5) [0036] It can be proved that Y '' is limited by DI regardless of C,

0 £ Y '' <KI -KI-1. (6) [0037] In this case, the segment sizes obtained after segmenting the blocks have the following limitations, assuming (without reducing the generality) that the first CI segments are encoded by KI and the rest by KI-1.

CBSSi £ KI for i = 1, ..., CI

CBSS_and £ K_I-1 for i = C_AND +1, ..., C; if C_I-1 > 1 [0038] Returning to FIG. 1, as discussed above, from the table 107 non-adjacent block sizes, select the appropriate FEC block size. The task of selecting the appropriate FEC block size or sizes is performed by logic circuit 106, as discussed above. An example of table 107 is given in Table 1. For example, in the first case, logic circuit 106 selects the FEC block size from the available non-adjacent FEC block sizes between Kmin and Kmax, where Kmin <= KI <= Kmax and where in addition KI is based on X. In particular, if a single is to be used FEC block size KI, logical circuit 106 selects the smallest KI (from Ktable), which is not less than [X / C], i.e. KI = [X / C] + δ, where d £ 0 and K <[X / C] . However, if two FEC block sizes are to be used, KI-1 and KI are determined from equation (4) giving the number of segments that are encoded using the FEC block sizes KI-1 and KI.

PAT-1191-EP-E

EP2080271

Table 1: FEC block size set for which the encoder turbo interleaver is defined

<td colspan="6">Ktable</td>

<td> 128</td><td> 256</td><td> 512</td><td> 1024</td><td> 2048</td><td> 4096</td>

<td> 144</td><td> 288</td><td> 576</td><td> 1152</td><td> 2304</td><td> 4608</td>

<td> 160</td><td> 320</td><td> 640</td><td> 1280</td><td> 2560</td><td> 5120</td>

<td> 176</td><td> 352</td><td> 704</td><td> 1408</td><td> 2816</td><td> 5632</td>

<td> 192</td><td> 384</td><td> 768</td><td> 1536</td><td> 3072</td><td> 6144</td>

<td> 208</td><td> 416</td><td> 832</td><td> 1664</td><td> 3328</td><td></td>

<td> 216</td><td> 440</td><td> 888</td><td> 1776</td><td> 3568</td><td></td>

<td> 240</td><td> 480</td><td> 960</td><td> 1920</td><td> 3840</td><td></td>

[0039] The FEC encoder 104 only supports a limited set of FEC block sizes (i.e., input sizes). Without loss of generality, it is assumed that the FEC 104 encoder is a turbo encoder, and that the set of FEC block sizes supported by the turbo encoder is a set of interleaver sizes for which an internal turbo code interleaver is defined. However, based on the knowledge of the subject, it can be concluded that 104 may use other FEC schemes, including low-density parity check (LDPC) codes, convolutional codes, turbo block codes, Rees-Solomon codes, etc.

[0040] After determining the number of C segments and the size of each segment, this information is transferred responsible for carrying out the segmentation, bits) is divided into C segments, which are the size of the FEC KI block, if only FEC block is allowed for to circuit 102 where CTB (X coded for one FEC block size, but if two adjacent FEC block sizes are allowed, segmenting circuit 102 may output CI segments,

PAT-1191-EP-E

EP2080271 to be encoded with FEC KI block size and CI-1 segments to be encoded with FEC KI-1 block size.

Inserted padding bits [0041] The number of padding bits (added to each segment) can be determined based on the segment size and FEC block size used for FEC encoding of the segment. There are at least two ways to distribute complementary bits to C segments.

· Concentrated filler. Insert the padding bits into the smallest number of segments without unduly reducing the segment sizes. In one example, all padding bits may appear at the beginning of the first segment. The advantage is that only one segment (containing all padding bits) must be processed separately. Furthermore, padding bits can be added to the segment that is encoded with a larger FEC KI block size instead of a smaller FEC KI-1 block size when two FEC block sizes are used for CTB. This method is particularly attractive when encoding two adjacent FEC block sizes are allowed.

· Dispersed filler. Distributes complementary bits evenly (as much as possible) among many segments. Supplementary bits can be spread even among all C segments.

[0042] For efficient implementation of the transmitter and receiver, concentrated filler is preferred. In the preferred implementation, Y '' adjacent padding bits are added

PAT-1191-EP-E

EP2080271 (if two adjacent FEC block sizes are allowed; Y if only one FEC block size is allowed) in front of one of the segments (e.g. first or last) using the FEC KI block size before sending it to the encoder. In terms of performance, this is equivalent to adding Y '' adjacent padding bits to the end of the segment having the FEC KI block size.

Returning to FIG 1, for each segment (generated by circuit 102) the FEC code word is determined using the segment insertion bit insertion steps to form the FEC input block ; block FEC coding

<td colspan="2">FEC input, complementary.</td><td>and</td><td>rejection</td><td>related bits</td><td>with bits</td>

<td>[0044] Everyone</td><td colspan="2">segment</td><td>produced</td><td>across the perimeter</td><td>102 is</td>

<td>forwarded</td><td>down</td><td>circuit</td><td colspan="2">complementary 103, where</td><td>followed by</td>

inserting padding bits. If no padding bits are needed, the padding circuit is transparent, i.e. no padding bits are added. (Kfiller = 0). The segments (along with the complementary bits) are then passed to the turbo encoder 104, where the turbo C coding of the segments leads to C FEC code words. Complementary bits are then discarded by circuit 105 and the resulting C code words are respectively transmitted via transmission circuit 108. If no padding bits are supplied by circuit 103, then the padding rejection circuit 105 is transparent, i.e. no padding bits are rejected (Kfiller = 0). Note that it is possible that circuit 105 may not discard any bits corresponding to the complementary bits.

PAT-1191-EP-E

EP2080271 [0045] FIG. 2 is a block diagram of the receiver. During operation, the received signal vector passes through a block segmentation circuit 202, which organizes the fragments of the resulting signal vector according to the segments with which they are associated. Segment size, number of segments, FEC block size used for turbo decoding of each segment, number of padding bits can be determined using logic circuit 213 and table 215 of available FEC block sizes in a similar way as in an encoder. The circuit 204 operates the complementary bits to know the location of the complementary bits for use in the turbo decoder 206, e.g., to establish large LLRs corresponding to the complementary bits. After turbo decoding, circuit 208 discards padding bits to obtain segment estimation. The 211 code block assembler combines transport estimates by appropriately collecting and setting segment estimates obtained from circuit 208.

Removing the parity bits of the component encoder [0046] This part provides a specific method for determining the FEC codeword. A method using the knowledge of inserting padding bits in a transmitter is described. In particular, the method determines which bits (both systematic and parity bits) can be discarded from the turbo encoder output without degradation of speed or with only minimal impact on speed. In general, padding bits are known, so the systematic bits of these bits (equal to those known bits) may be discarded before being sent. It is not clear, however, whether any parity bits can be discarded.

PAT-1191-EP-E

EP2080271 [0047] FIG. 3 is a block diagram of turbo encoder 104 of FIG. 1.

During operation, an input block with a length of KI bits enters both interleaver 301 and the component encoder 302. Interleaver 301 interleaves the input block and passes this input block in interlaced order to the component 303 encoder. The component 303 encoder then encodes the interleaved input block. In a similar manner, the component encoder 302 encodes the original input block. A code word x is created from a systematic block (equal to the FEC input block), output from the component encoder

302 and the output from the component encoder 303. The block of code words x is then sent to circuit 105.

[0048] In a conventional turbo encoder, such as turbo codes with tails, the initial state of the component encoders (content of shift registers) is assumed to be filled with zeros. In this case, when the Kfiller complementary bits (usually zero) are inserted at the beginning of the turbo code input block, the system bits and the parity bits of the 302 encoder corresponding to the Kfiller bit positions are all equal to zero. Hence, these bits can be discarded in the transmitter and the receiver can use this knowledge when performing turbo decoding. However, in the 303 Kfiller encoder, the bits are mixed due to the turbo interleaver, so the parity bits of the 303 encoder corresponding to the complementary bits are not known, so they cannot be simply discarded.

[0049] When the turbo encoder has component end-bit coders, the initial state of the component encoders may not always be zero. For terminal bit type codes, status

PAT-1191-EP-E

EP2080271 initial and final state of the component encoder are equal and depend on the input block. Therefore, when Kfiller of adjacent complementary bits (i.e. zeros) are inserted at the beginning of the turbo code of the input block, the parity bits of the 302 encoder corresponding to the Kfiller bit positions are not always zero. However, it can be proved that most of these Kfiller parity bits of the 302 encoder component carry no information.

[0050] In general, groups of adjacent complement bits are inserted into a segment to form an FEC input block in which the length of such a group is a multiple of 2^m-1 (= 7 for component convolutional codes in the 3GPP turbo encoder). Then the FEC input block is FEC encoded and the parity bits associated with the complement bits are discarded. The FEC encoder may be a terminal bit type convolutional code used alone or a terminal bit type convolutional code used as the turbo encoder component code.

[0051] In particular, when applied to turbo codes with component codes with terminal bit characteristics, groups of systematic bits corresponding to complementary bits may be discarded, and parity bits corresponding to groups of complementary bits at the output of the component encoder may be rejected, where the component encoder gets the input block Non-interleaving FEC for turbo end bit coders. This can be demonstrated as follows.

[0052] Let the state of the coder shift register 302 in step i be S (i), let m be the number of elements in the shift register and let g be any positive integer.

PAT-1191-EP-E

EP2080271

When the component encoder is given (2^m-1) xg zeros between steps i + 1 and i (2^m-1) xg, the following formula is the property of a recursive convolutional encoder (such as the 3GPP code used in Version 6 turbo):

S (i) = S (i + (2^m -1) g) (7)

Note that S (i) may not be constant. In addition, intermediate states S (j) may not be constant or equal to S (i), i &lt;j &lt;i + (2^m-1) g.

[0053] Therefore, the state of the component encoder remains unchanged between step i + 1 and step i + (2^m-1) xg. Therefore, the transmitter can use (7) by rejecting the output of the component encoder during these steps, as these padding bits do not change the state of the shift register, so they do not provide information to the decoder. The decoder in the receiver can also use similarly (7) based on the knowledge of the position and value of the complementary bits. The above method is further described with an example in which Kfiller complementary (zero) bits are inserted into adjacent positions at the input to the turbo terminal bit type code.

[0054] Since Kfiller is inserted adjacent complement bits (zeros) into the turbo code input block, g = [Kfiller / (2^m- 1)] and thus rejected from the 302 encoder may be pxgx (2^m - 1) parity bits, where p is the number of parity bits output from component 302 encoder, generated for each bit in the FEC input block. Hence, in the component encoder 302, only parity bits corresponding to the groups of padding bits are rejected, while the component encoder 302 retrieves the block

PAT-1191-EP-E

EP2080271 FEC input without interleaving for turbo end bit coders.

[0055] In the case of the 3GPP turbo end bit type encoder p = 1 in component encoder 1, m = 3. Thus, from component 302 encoder for Kfiller, adjacent padding bits may be rejected 7 [Kfiller / (2^m-1)] parity bits. Because m = 3, at most only 6 parity bits corresponding to these Kfiller complementary bits of the 302 encoder may have to be retained at the output of component 302 encoder. [0056] In the 303 Kfiller component encoder, the complementary bits may be distributed due to interleaver operation turbo code. Hence, it may not be possible to discard the parity bits from the 303 encoder without affecting performance.

[0057] The next section describes some sample scenarios in which the segment block code rule can be applied, e.g. hybrid-Automatic Repeat reQuest (HARQ), Multiple Input Multi Output (MIMO) etc.

Transport Block (TB) Creation [0058] The segmenting rule of the code block described above is applied to the concatenated transport block (CTB) in the AQR hybrid channel (HARQ). Before dividing the code block into segments, the information bits that must be sent to a single user from the base station during the transmission time interval (TTI) may need to be divided into at least one transport block, thus passing through at least one HARQ channel . For example, FIG. 4

PAT-1191-EP-E

EP2080271 shows an example in which information bits are transmitted using two HARQ channels (HARQ1 and HARQ2, respectively) and two TB1 and TB2 transport blocks. During this operation, the bits of length information A are received by the forming circuit TB 402 for transmission on one or more spatial channels. Circuit 402 means X 'bits as TB1 transport block, where *' £ A; HARQ1 404 processor attaches the CRC bits to these X 'bits to form a concatenated X-length transport block; the concatenated X transport block is projected onto the first HARQ channel. The concatenated transport block is sent to circuit 102 dividing the code blocks into segments.

[0059] Circuit 402 means W '= A - X' bits from the information bit set as the second transport block TB2; HARQ2 406 processor attaches CRC bits to Y bits from the second concatenated transport block, the concatenated transport block is projected onto the second HARQ channel. The concatenated transport block is sent to circuit 102 dividing the code block into segments.

[0060] It should be noted that circuits 404 and 406 may perform additional HARQ functions, append control information, etc.

[0061] Although the concepts of FIG. 4 are illustrated using two HARQ channels, they can easily be extended to multiple HARQ channels. If more than one HARQ channel is supported for a given user during the transmission time period (TTI), the segment code block rule can be applied to each TB.

PAT-1191-EP-E

EP2080271 [0062] If too many FEC code words (or segments) occur on the TTI per user, multiple HARQ channels may occur, such as wide band (e.g. 20 MHz), higher order modulation (e.g. 64QAM), multi-stream MIMO etc. Many HARQ channels can also be used for TBs that have different QoS, such as VoIP and best effort data.

[0063] The MIMO code word includes bits that are sent to a single user as part of a TTI or one MIMO stream. Thus, the MIMO code word may include one or more FEC code words. Sometimes the MIMO code word is used to specify bits in a MIMO stream.

[0064] Rules can be defined for the creation of TB. In one implementation, TB is to comprise no more than x (e.g. x = 8) FEC code words (the value of x is specified in EUTRA by the eNodeB programmer). In another implementation, if more than x FEC code words are needed per TB, two TBs are created as follows. The packet is divided approximately equally between two TBs, each having almost the same number of FEC code words of roughly the same size. In yet another implementation of the FEC code words to be sent to three MIMO streams using 2 simultaneous HARQ channels, the first (medium, highest quality stream) belongs to one TB, and the second and third streams belong to the second TB. In yet another embodiment, when four MIMO code words are to be sent using two HARQ channels, several combinations are possible. For example, (a) TB1 = 1.2, TB2 = 3.4, (b) TB1 = 1.3, TB2 = 2.4, (c) TB1 = 1.2, TB2 = 2.3, (d ) TB1 = 1, TB2 = 2,3,4. TBi means

PAT-1191-EP-E

EP2080271 here TB of the i-th HARQ channel, numbers from 1 to 4 indicate the number of the MIMO codeword (or stream).

[0065] FIG. 5 is a block flow diagram of processing at a receiver when information bits are received through at least one HARQ channel. The received bits from the 211 code block assembler are fed to the respective channel processors 504 and 506. The output from the channel processors are the TB1 and TB2 transport block estimates, which are fed to the TB 502 assembler circuit, which combines TB blocks and information bit estimates.

[0066] FIG. 6 is a block diagram illustrating the operation of the transmitter of FIG. 1. The algorithm starts at step 601, in which the segmenting circuit receives a concatenated transport block of length X. In step 603, the logical circuit reaches table 107 and selects the appropriate FEC block size. As discussed above, in the first embodiment of the present invention, the FEC KI block size is determined from the group of non-adjacent FEC block sizes provided in Table 107, where available non-adherent FEC block sizes are between Kmin and Kmax, and where Kmin &lt;= KI &lt;Kmax. As discussed above, KI is based on X. X is determined by logic circuit 106 based on the concatenated transport block. After determining X, K is determined_AND = [X / C] + di C = [X / Kmax]. In a second embodiment of the present invention, the FEC block sizes KI and KI-1 are determined, where KI = [X / C] + δ.

[0067] Continuing, in step 605, the number of C segments and FEC block sizes are transferred to segmenter circuit 102 and in step 607, the segmenter circuit divides the concatenated X transport block into C segments of substantially equal size KI

PAT-1191-EP-E

EP2080271 (or alternatively KI and KI-1). In step 609, complementary bits are added (as needed) through circuit 103 and in step 611 each of the C segments is coded (i.e., the FEC code word is determined for each of the C segments). Finally, in step 613, the FEC code words are transmitted through transmission circuit 108.

[0068] As discussed above, the FEC codeword step includes the steps of inserting the complement bits into a segment to form an FEC input block, FEC encoding the FEC input block, and discarding the bits associated with the complement bits. This step may involve inserting groups of adjacent filler bits into a segment to form an FEC input block, where the group length is a multiple of 7, FEC encoding the FEC input block, and discarding bits associated with the complementary bits. The rejection of the complementary bits includes the steps of rejecting the systematic bit groups corresponding to the groups of the complementary bits and rejecting the parity bits at the output of component encoder 1, where the component encoder retrieves the FEC input block without interleaving in the case of turbo end bit coders.

[0069] FIG. 7 is a flow chart of the receiver of FIG. 2. The algorithm starts at step 701, in which the segment size, number of segments, size of the FEC block used for turbo-coding each segment and the number of padding bits are determined using logic circuit 213 and table 215. As discussed above, in an example useful for understanding of the present invention, the KI size of the FEC block is determined from the group of non-adjacent FEC block sizes listed in Table 215,

PAT-1191-EP-E

EP2080271 where available non-adherent FEC block sizes are between Kmin and Kmax and where Kmin &lt;= KI &lt;Kmax. As discussed above, KI is based on X. X is determined by logic circuit 213 based on the received signal vector. Logic circuit 213 then determines KI = [X / C] + δ and C = [X / Kmax]. In one embodiment of the present invention, the sizes KI and KI-1 are determined, where KI = [X / C] + δ.

[0070] In step 703, the received signal vector passes through a circuit 202 segmenting the blocks of code that organizes portions of the obtained signal vector according to the C-th segment to which they are associated. At step 705, circuit 204 intended for padding uses the knowledge of padding bit positions in favor of the turbo decoder 206, e.g., by setting high LLR values ​​corresponding to padding bits. Each of the C segments is decoded in step 707. After turbo decoding, circuit 208 discards padding bits to obtain segment estimation (step 709). The 211 code block assembler combines the estimated transport by appropriately collecting and arranging the estimates of the segments obtained from circuit 208 (step 711).

[0071] Although the present invention has been particularly illustrated and described with reference to a particular embodiment, it should be understood that various changes in form may be made therein and the details may be changed therein without departing from the scope of the invention as set out in the following claims.

PAT-1191-EP-E

EP2080271