Apple Inc. v. Samsung Electronics Co. Ltd. et al

Filing 661

EXHIBITS re 660 Administrative Motion to File Under Seal Apple Inc.'s Notice of Motion and Motion for Partial Summary Judgment Exhibits to Mueller Declaration ISO Apple's Motion for Partial Summary Judgment [660-9] filed byApple Inc.(a California corporation). (Attachments: # 1 Exhibit Mueller Decl Exhibit 2, # 2 Exhibit Mueller Decl Exhibit 3, # 3 Exhibit Mueller Decl Exhibit 4, # 4 Exhibit Mueller Decl Exhibit 5, # 5 Exhibit Mueller Decl Exhibit 6, # 6 Exhibit Mueller Decl Exhibit 7, # 7 Exhibit Mueller Decl Exhibit 8, # 8 Exhibit Mueller Decl Exhibit 9, # 9 Exhibit Mueller Decl Exhibit 10, # 10 Exhibit Mueller Decl Exhibit 11, # 11 Exhibit Mueller Decl Exhibit 12, # 12 Exhibit Mueller Decl Exhibit 13, # 13 Exhibit Mueller Decl Exhibit 14, # 14 Exhibit Mueller Decl Exhibit 15, # 15 Exhibit Mueller Decl Exhibit 16, # 16 Exhibit Mueller Decl Exhibit 17, # 17 Exhibit Mueller Decl Exhibit 18, # 18 Exhibit Mueller Decl Exhibit 19, # 19 Exhibit Mueller Decl Exhibit 20, # 20 Exhibit Mueller Decl Exhibit 21, # 21 Exhibit Mueller Decl Exhibit 22, # 22 Exhibit Mueller Decl Exhibit 23, # 23 Exhibit Mueller Decl Exhibit 24)(Related document(s) 660 ) (Selwyn, Mark) (Filed on 1/25/2012)

Download PDF
Mueller Exhibit 17 US007050410B1 (12) United States Patent (lO) Patent No.: US 7,050,410 B1 (45) Date of Patent: May 23, 2006 Kim et al. (54) APPARATUS AND METHOD FOR CONTROLLING A DEMULTIPLEXER AND A MULTIPLEXER USED FOR RATE MATCHING IN A MOBILE COMMUNICATION SYSTEM (75) inventors: Se-Hyonng Kim, Seoul (KR); Min-Goo Kim, Suwon-shi (KR); Beong-Jo Kim, Songnam-shi (KR); Soon-Jae Choi, Songnam-shi (KR) (73) Assignee: Samsnng Electronics Co., Ltd. (KR) ( * ) Notice: Subject to any disclaimer, the term of this patent is extended or adjusted under 35 U.S.C. 154(b) by 620 days. (21) Appl. No.: 09/613,068 (22) Filed: Jnl. 10, 2000 Jul. 8, 1999 Jul. 23, 1999 Aug. 30, 1999 References Cited U.S. PATENT DOCUMENTS 5,771,229 A * 5,881,109 A * 5,978,365 A * 6,061,820 A * 110 DATA 375/222 714/755 370/342 714/790 714/785 OTHER PUBLICATIONS Japanese Office Action dated Dec. 9, 2003 issued in a counterpart application, namely, Appln. No. 2001-509176. Nortel Networks: "Proposal for Rate Matching for Turbo Codes", 1999. 3rd Generation Partnership Project (3GPP), "Multiplexing and Channel Coding (FDD)", 1999. Samsung Electronics Co., "Unified Rate Matching Scheme for Turbo/Convolutional Codes and Up/Down Links", 1999. (Continued) (57) (KR) ............................... 1999-27407 (KR) ............................... 1999-30095 (KR) ............................... 1999-37496 (51) Int. CI. HO4B 7/216 (2006.01) HO3M 13/03 (2006.01) (52) U.S. CI ....................... 3701335; 370/342; 370/535; 375/240.27; 714/786; 714/790 (58) Field of Classification Search ................ 370/328, 370/536, 537, 542; 714/786, 790 See application file for complete search history. (56) 7/2000 Gelblum et al ............. 10/2001 Rowitch et al ............. 6/2002 Park et al ................... 4/2003 Markarian el al ........... 9/2003 Williamson et al ......... Primary Examiner~Chau Nguyen Assistw~t Examiner Soon D. Hyun (74) Attorney, Agent, or Firm Dilworth & Barrese LLP Foreign Application Priority Data (30) 6,088,387 A * 6,304,991 B1 * 6,400,703 B1 * 6,553,539 B1 * 6,615,387 B1 * 6/1998 Gavrilovich ................ 3/1999 Kimet ~ ................... 11/1999 Yi .............................. 5/2000 Nakakita et al ............. 370/342 375/298 370/331 714/751 120 ABSTRACT A transmitting device including an encoder for receiving an information bit stream in a frame and outputting an information symbol, a first parity symbol, and a second parity symbol by encoding each information bit. An interleaver sequentially arranges the information symbols and the first and second parity symbols by rows in an array with an integer number of rows and an integer number of columns. The interleaver further outputs a plurality of radio frames in a stream, by reading the symbols by going down each column, starting at the leflmost column and proceeding right. Each radio frame has a predetermined size. A demultiplexer demultiplexes the radio frames received from the interleaver into streams of information, first parity symbols, and second parity symbols. A rate matcher bypasses the stream of information symbols and punctures the streams of the first and second parity symbols for rate matching. 57 Claims, 24 Drawing Sheets 141 145 RADIO FRAME APLNDC-WH-A 0000014034 US 7,050,410 B1 Page 2 OTHER PUBLICATIONS Samsung Electronics Co., "A Method to Classify the Interleaved Symbols of 1St MIL Interleaver Using Some Property", 1999. Fujitsu & Siemens, "Universal Rate Matching Method for Up/Downlink and Turbo/Convolutional Coding", 1999. Nortel Networks, Optimum Rate Matching of Turbo/Convolutional Coding for 3 GPP Up/Down Links, 1999. Nortel Networks, Analysis of Conmaonalities of Turbo Code Puncturing Rate Matching Proposals, 1999. * cited by examiner APLNDC-WH-A 0000014035 U.S. Patent May 23, 2006 Sheet 1 of 24 US 7,050,410 B1 APLNDC-WH-A 0000014036 U.S. Patent May 23, 2006 Sheet 2 of 24 US 7,050,410 B1 APLNDC-WH-A 0000014037 U.S. Patent May 23, 2006 Sheet 3 of 24 US 7,050,410 B1 110 01010011110 ,,, TURBO | ,FNCODER| FIG. 3 APLNDC-WH-A 0000014038 U.S. Patent May 23, 2006 Sheet 4 of 24 US 7,050,410 B1 1 =tlNTERLEAVER INPUT(CODE RATE R--1/3) 91 97 94 103 100 112 109 106 118 115 127 124 121 130 136 133 142 145 ~ 51 14.8 154 157 160 FIG. 4 APLNDC-WH-A 0000014039 U.S. Patent May 23, 2006 Sheet 5 of 24 US 7,050,410 B1 IST INIERLEAVER OUTPUT WHEN Til=2Omsec (:CODE RATE=l/3) 139 6 106 124 136 FIG. 5A APLNDC-WH-A 0000014040 U.S. Patent May 23, 2006 Sheet 6 of 24 US 7,050,410 BI IST INTERLEAVER OUTPUT WHEN TTl=4Omeec (CODE RATE=l/3) 73 133 11 71 119 107 1 ~3 :30 6 ~2 102 75 FIG. 5B APLNDC-WH-A 0000014041 U.S. Patent May 23, 2006 Sheet 7 of 24 US 7,050,410 B1 IST INTERLEAVER OUTPUT WHEN TTI=BOmSEC(COOE RATE=I/3) 4.9 121 13 85 157 4,3 115 31 79 151 58 106 22 70 142 4 28 52 124- ~ 76 88 112 FIG. 5C APLNDC-WH-A 0000014042 U.S. Patent May 23, 2006 Sheet 8 of 24 US 7,050,410 B1 105 121 129 FIG. 6 APLNDC-WH-A 0000014043 U.S. Patent May 23, 2006 Sheet 9 of 24 US 7,050,410 B1 1ST INIERLEAVER OUTPUT WHEN TTI--2Omsec (CODE RATE R=1/2) 1 3 5 7 9 11 ’ "13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 *,7 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 t19 12t 123 125 127 129 131 133 135 137 139 141 14.3 145 147 149 151 153 155 157 159 FIG. 7A APLNDC-WH-A 0000014044 U.S. Patent May 23, 2006 Sheet 10 of 24 US 7,050,410 B1 1~T INTERLEAVER OUTPUT WHEN TTl=4Omsec (CODE RATE R=1/2) 1 5 9 13 17 21 25- 29 3,.3 37 41 4,5 4.9 5,5 57 51 65 69 73 77 111 85 89 93 97 101 105 109 113 117 121 125 129 ! 33 137 14.1 14.5 !49 153 157 ,:3 7 11 15 lg 23 27 31 35 39 43 47 51 55 59 63 87 71 75 79 83 87 91 95 gg 103 107 111 115 119 123 127 1.31 135 1.39 143 FIG. 7t3 APLNDC-WH-A 0000014045 U.S. Patent May 23, 2006 Sheet 11 of 24 US 7,050,410 B1 1ST INTERLEAVER OUTPUT WHEN Tl"l=EOmsec (CODE RATE R=1/2) 9 17 25 33 4.1 4.9 57 65 73 B1 89 97 105 113 121 129 137 145 153 5 13 21 29 37 45 53 61 69 77 85 93 101. 109 117 125 133 141 "149 157 3 11 19 27 43 51 59 67 75 83 91 35 gg 107 115 123 131 139 147 155" 7 15 23 31 39 47 55 63 71 79 87 95 103 111 119 FIG. 7C APLNDC-WH-A 0000014046 U.S. Patent May 23, 2006 Sheet 12 of 24 TTI -- l Omsec US 7,050,410 B1 RF Y X Y Z FIG. 8A TTI-~- 20msec RF1 RF’2 x y y x z y z x Y z FIG. 8B APLNDC-WH-A 0000014047 U.S. Patent May 23, 2006 Sheet 13 of 24 US 7,050,410 B1 RF1 RF2 RF3 RF4 x z Y x z Y x z x ~ )t x Y x z Y z Y x z FIG. 8C TTI -- 80rrlsec RF1RF2 RF3 RF4 RF5 RF6 RF7 RF8 y y z x z x x y z x y z x Y z x y z x y z x Y z x Y z x Y z x Y z x y z x y z x Y z x Y z x y z FIG. 8D APLNDC-WH-A 0000014048 U.S. Patent May 23, 2006 Sheet 14 of 24 US 7,050,410 B1 1ST INTERLEAVER INPUT WHEN TTI -- 80reset x Y z x Y z x z x y z x y z X y z x y z x Y z x y z x y z x Y z x Y z FIG. 9A 1ST INTERLEAVER OUTPUT x y z x y z x y ~ x y z x y z x y z x y z x Y z x Y z x y z x y z y x z FIG. 9B APLNDC-WH-A 0000014049 U.S. Patent May 23, 2006 Sheet 15 of 24 US 7,050,410 B1 RADIO FRAME SEGMENTER OUTPUT (WITH FILLER BITS INSERTED) FIG. 9C APLNDC-WH-A 0000014050 U.S. Patent May 23, 2006 Sheet 16 of 24 US 7,050,410 B1 1ST INTERLEAVER INPUT WHEN TTI = 40reset y Z x z x y x Y Z Y z x z x y FIG. IOA 1ST INTERLEAVER OUTPUT x z y x Y x z Y z Y x z x z Y x Y Y Z FIG. 10B APLNDC-WH-A 0000014051 U.S. Patent May 23, 2006 Sheet 17 of 24 US 7,050,410 B1 RADIO FREAME SEGMENTER OUTPUT (WITH FILLER BITS INSERTED) FIG. IOC APLNDC-WH-A 0000014052 U.S. Patent May 23, 2006 Sheet 18 of 24 US 7,050,410 B1 1ST INTERLEAVI~R INPUT WHEN 131 = BOmsec x y z x y z x y | z x y z x y z x Y z .x y z x Y z z x Y | x y z x x y y z L z FIG. llA 1 ST IN TERLEAVER OU TPU T x y z x Y z x Y z x Y z x Y z x Y z x y z x y z x y z x y = =, xyz z y x z FIG. 1 I.B APLNDC-WH-A 0000014053 U.S. Patent May 23, 2006 Sheet 19 of 24 US 7,050,410 B1 FIRST INTERLEAVER OUTPUT (WITH FILLER BITS INSERTED) x Y z x Y ¯ x y z x y z x y z x Y z x Y z x y z x y ~z O Y x y z x Y O x 0 z 0 z FIG. 11C RADIO FRAME SEGMENTEI;I( OUTPUT FIG. llD APLNDC-WH-A 0000014054 U.S. Patent May 23, 2006 Sheet 20 of 24 US 7,050,410 B1 1ST INTERLEAVER. INPUT ~rlEN TTI= BOmsec x y z x Y z x y z x y z x y Z x y z x Y z x Y z x y z x y z x y z x y z FIG. 12A 1ST INTERLEAVER OUTPUT x y z x y z xY z x y z ~ Y zx y z x y z x y x y z ~ y z x z Y x y z FIG. 12B APLNDC-WH-A 0000014055 U.S. Patent May 23, 2006 Sheet 21 of 24 US 7,050,410 B1 RADIO FRAME SEGMENTER OUTPUT FIG. 12C APLNDC-WH-A 0000014056 U.S. Patent May 23, 2006 Sheet 22 of 24 US 7,050,410 B1 APLNDC-WH-A 0000014057 U.S. Patent May 23, 2006 Sheet 23 of 24 US 7,050,410 B1 APLNDC-WH-A 0000014058 COMPONENT DEMUX(~ 4-1) 142 COMPONENT MUX(145) COMPONENT FROM RADIO FRAME SEGMENTAIIDN RAIE MATCHED RADIO FRAME INITIAL COMPONENT 210 CONTROLLER --TTI ----z, MEMORY US 7,050,410 B1 1 2 APPARATUS AND METHOD FOR blocks of which size is determined by (the number of CONTROLLING A DEMULTIPLEXER AND A encoded symbols)/(10), wherein 10 is the radio frame length MULTIPLEXER USED FOR RATE unit. A rate matcher 140 matches the data rate of a radio MATCHING IN A MOBILE frame received from the radio frame segmenter 130 to a 5 preset data rate by puncturing or repeating symbols of the COMMUNICATION SYSTEM radio frame. The above-described components can be proPRIORITY vided for each service. A MUX 150 multiplexes rate-matched radio frames from This application claims priority to applications entitled each service. A physical channel segmenter 160 segments "Apparatus and Method for Controlling Demultiplexer and 10 the multiplexed radio frames received from the MUX 150 Multiplexer for Rate Matching in Mobile Communication into physical channel blocks. A T’d interleaver 170 interSystem" filed in the Korean Industrial Property ONce on leaves the physical channel blocks received from the physiJul. 8, 1999 and assigned Ser. No. 99-27407, "Apparatus and cal channel segmenter 160. A physical channel mapper 180 Method for Controlling Demultiplexer and Multiplexer for maps the T’<interleaved blocks on physical channels for Rate Matching in Mobile Communication System" filed in 15 transmission. the Korean Industrial Property ONce on Jul. 23, 1999 and As shown in FIG. 1, the UMTS uplink transmitting device assigned Ser. No. 99-30095, and "Apparatus and Method for is provided with rate matchers 140. The rate matcher 140 Controlling Demultiplexer and Multiplexer for Rate Match- varies in configuration depending on whether the channel ing in Mobile Communication System" filed in the Korean encoder 110 is a convolutional encoder or a turbo encoder. Industrial Property ONce on Aug. 30, 1999 and assigned 2o When a linear block code is used (a convolutional encoder Ser. No. 99-37496, the contents of all of which are hereby and a single decoder are used in this case) for the channel incorporated by reference. encoder, the following requirements of rate matching should be satisfied to increase data transmission efficiency and BACKGROUND OF THE INVENTION system performance in a multiple-access/multiple-channel 25 scheme. 1. Field of the Invention 1. An input symbol sequence is punctured/repeated in a The present invention relates generally to the rate matchpredetermined periodic pattern. ing of a channel encoded signal, and in particular, to an 2. The number of punctured symbols is minimized apparatus and method for controlling a demultiplexer (DE- whereas the number of repeated symbols is maximized. MUX) and a multiplexer (MUX) used for rate matching. 30 3. A uniform puncturing/repeating pattern is used to 2. Description of the Related Art puncture/repeat encoded symbols uniformly. In general, radio communication systems, such as satelThe above requirements are set on the assumption that the lite, ISDN (Integrated Services Digital Network), W-CDMA error sensitivity of a code symbol at any position in one (Wide band-Code Division Multiple Access), UMTS (Uni- frame output from a convolutional encoder is similar. versal Mobile Telecommunication System), and IMT (Inter- 35 Although some favorable results can be produced using the national Mobile Telecommunication)-2000 systems, chanabove requirements, a rate matching scheme different from nel-encode source user data with an error correction code the convolutional encoder should be employed when using prior to transmission, in order to increase system reliability. a turbo encoder because of the different error sensitivities of Typical codes used for channel encoding are convolutional symbols at different positions in one frame. codes and linear blocks code for which a single decoder is 4o When a turbo encoder is used, it is preferred that the used. Lately, turbo codes, which are useful for data transsystematic information part of the encoded symbols is not mission and reception, have been suggested. punctured since the turbo encoder is a systematic encoder. A multiple-access and multiple-channel communication Due to the two component encoder structure of the turbo system matches the number of channel encoded symbols to encoder, the minimum free distance of the output code is a given number of transmission data symbols to increase 45 maximized when the minimum free distance of each of the data transmission efficiency and system performance. This two component codes is maximized. To do so, the output operation is called rate matching. Puncturing and repetition symbols of the two component encoders should be puncare widely performed to match the data rate of channel tured equally to thereby achieve optimal performance. encoded symbols. Rate matching has recently emerged as a As described above, a distinction should be made between significant factor in UMTS for increasing data transmission 5o the information symbols and the parity symbols in the efficiency in the air interface and for improving system encoded symbols when a turbo encoder is used, to achieve performance. optimal rate matching. Processing, such as channel interFIG. 1 is a block diagram of an uplink transmitting device leaving, can be interposed between the turbo encoder and a in a general mobile communication system (a UMTS sys- rate matcher. Nevertheless, the distinction between informa55 tion symbols and parity symbols should be preserved. Howtem, herein). Referring to FIG. 1, a channel encoder 110 receives frame ever, this is impossible because all of the channel encoded data at predetermined TTIs (Transmission Time Intervals) symbols are randomly mixed after channel interleaving. which may be 10, 20, 40, or 80 ms, and encodes the received SUMMARY OF THE INVENTION frame data. And the channel encoder 110 outputs encoded symbols according to a predetermined coding rate R. The 6O An object of the present invention is to provide an frame data size (number of information bits) is determined apparatus and method for performing rate matching sepaby a (data rate of the frame data)*(TTI). If tail bits are not considered, the number of encoded symbols are determined rately on information symbols and parity symbols during by the (frame data size)*(coding rate R). A 1st interleaver symbol encoding in an uplink transmitting device of a 120 interleaves the output of the channel encoder 110. A 65 mobile communication system. radio frame segmenter 130 segments interleaved symbols Another object of the present invention is to provide an received from the 1st interleaver 120 into 10-ms radio frame apparatus and method for disposing a DEMUX before a rate APLNDC-WH-A 0000014060 US 7,050,410 B1 3 4 matcher in order to separate symbol data into information FIGS. 1DA, 10B, and 1DC illustrate VMnterleaver input, symbols and parity symbols in a mobile communication l~Mnterleaver output, and radio frame segmenter output system. according to a second embodiment of the present invention; FIGS. llA to liD illustrate lSqinterleaver input, 1~A further object of the present invention is to provide an apparatus and method for controlling a DEMUX and a MUX 5 interleaver output, and radio frame segmenter output according to a third embodiment of the present invention; for use in rate matching in an uplink transmitting device of FIGS. 12A, 12B, and 12C illustrate VMnterleaver input, a mobile communication system. l~Mnterleaver output, and radio frame segmenter output Still another object of the present invention is to provide according to a fourth embodiment of the present invention; an apparatus and method for controlling a DEMUX and a MUX for use in the rate matching of a turbo-encoded signal 10 FIG. 13 is a block diagram of a DEMUX & MUX controlling apparatus according to an embodiment of the in an uplink transmitting device of a mobile communication present invention; system. FIG. 14 is a block diagram of a DEMUX & MUX To achieve the above and other objects, there is provided controlling apparatus according to another embodiment of a transmitting device in a mobile communication system. In the preferred embodiments of the transmitting device, an 15 the present invention; and FIG. 15 is a block diagram of a DEMUX & MUX encoder receives an information bit stream in a frame as long controlling apparatus according to yet another embodiment as an integer multiple of a predetermined size and generates of the present invention. an information symbol and first and second parity symbols by encoding each information bit. An interleaver sequenDETAILED DESCRIPTION OF THE tially arranges information symbols and the first and second 20 PREFERRED EMBODIMENTS parity symbols corresponding to each of the information symbols row by row in an array having a number of rows Preferred embodiments of the present invention will be and a number of columns. The number of rows and the described hereinbelow with reference to the accompanying number of columns in the array are both integers. The interleaver reorders the columns according to a predeter- 25 drawings. In the following description, well-known functions or constructions are not described in detail since they mined rule, reading the symbols down by column from left would obscure the invention in unnecessary detail. to right, and outputs a plurality of radio frames in a stream, For rate matching, the UMTS uplink transmitting device each radio frame having a size determined by L/(TTI/10 of FIG. 1 has rate matcher 140 that varies in structure ms), where L is number of coded symbols. A demultiplexer demultiplexes each of the radio frames received from the 30 depending on whether channel encoder 110 is a convolutional encoder or a turbo encoder, as stated before. When a interleaver to the information symbols, the first parity symturbo encoder is used as the channel encoder 110 according bols, and the second parity symbols of the radio frame. Rate to the preferred embodiments of the present invention, the matchers bypass the information symbols and puncture or rate matcher 140 is so constituted as to include a DEMUX repeat the first and second parity symbols for rate matching. 35 141, component rate matchers 142, 143, and 144, and a MUX 145, as shown in FIG. 2. The DEMUX 141 separates BRIEF DESCRIPTION OF THE DRAWINGS the output symbols of the radio frame segmenter 130 into information symbols and parity symbols and switches them The above and other objects, features and advantages of to the corresponding component rate matchers 142, 143, and the present invention will become more apparent from the 40 144. The MUX 145 multiplexes symbols received from the following detailed description when taken in conjunction component rate matchers 142, 143, and 144 and feeds the with the accompanying drawings in which: multiplexed symbols to the MUX 150 of FIG. 1. FIG. 1 is a block diagram of an uplink transmitting device The uplink transmitting device shown in FIG. 2 is so in a conventional mobile communication system; constituted that the systematic information symbols of FIG. 2 is a block diagram of an uplink transmitting device provided with a DEMUX and a MUX for rate matching, 45 encoded symbols is not punctured in view of the fact that a turbo code is a systematic code. It is preferred that the two according to the preferred embodiments of the present component encoders are connected in parallel in the turbo invention; encoder and that the minimum free distance between final FIG. 3 illustrates an example of turbo encoder input and codes maximizes that of each component encoder. The turbo encoder output in the uplink transmitting device of 50 consideration that the best performance can be achieved by FIG. 2; equal puncturing of the output symbols of the two compoFIG. 4 illustrates an example of lSt-interleaver input with nent encoders is reflected in the constitution of the uplink coding rate R 1B in the uplink transmitting device of FIG. transmitting device in FIG. 2. 2; According to the preferred embodiments of the present FIGS. 5A, 5B, and 5C illustrate examples of lSMnter55 invention, the DEMUX 141 is located between radio frame leaver output with R 1/3 in the uplink transmitting device of segmenter 130 and component rate matchers 142, 143, and FIG. 2; 144, while MUX 145 is located between component rate FIG. 6 illustrates an example of l~Mnterleaver input with matchers 142, 143, and 144 and MUX 150 in the uplink R 1A in the uplink transmitting device of FIG. 2; transmitting device. FIGS. 7A, 7B, and 7C illustrate examples of lSt-inter- 60 In the embodiment of the present invention shown in FIG. leaver output with R 1/2 in the uplink transmitting device of 2, the DEMUX 141 and MUX 145 are synchronized with FIG. 2; each other such that the DEMUX 141 and MUX 145 switch FIGS. 8A to 8D illustrate examples of radio frame segto the same rate matcher block (i.e., if DEMUX 141 menter output in the uplink transmitting device of FIG. 2; switches to rate matcher 142 to input a symbol into the FIGS. 9A, 9B, and 9C illustrate l~Mnterleaver input, 65 DEMUX 141, then MUX also switches to the rate matcher l’~-intefleaver output, and radio frame segmenter output 142 after the input symbol has been rate matched to receive according to a first embodiment of the present invention; the rate matched symbol.). APLNDC-WH-A 0000014061 US 7,050,410 B1 5 6 The turbo code used in turbo encoder 110 of F1G. 2 is a F1G. 4 illustrates an example of Vt-interleaver input after systematic code and, thusly, can be separated into a systemturbo-encoding 160 input bits at R 1B and the TT1 80 ms. atic information symbol Xk and parity symbol Yk and Z~. For in F1G. 4, a blank rectangle denotes a system information turbo encoder 110, code rate R 1/3. Hereinafter, the systemsymbol x, a rectangle marked with slant lines denotes a first atic information symbol will be labeled with x and the first 5 parity symbol y, and a rectangle marked black denotes a second parity symbol z. parity symbols with y and second parity symbols with z. When R 1/3, the relationship between the input and output of in F1G. 4, the 1~* interleaver 120 sequentially receives the turbo encoder 110 is shown in F1G. 3. code symbols 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,..., 160 from the Referring to F1G. 3, the turbo encoder output is a turbo encoder 110. Each number represents an order of sequence of an information symbol Xl, a first parity symbol 10 encoded symbol received from the turbo encoder 110. The numbers also indicate the order by which each of the Yl, a second parity symbol zl, an information symbol x2, a first parity symbol Y2, a second parity symbol z2, an infornumbers has been received in the interleaver 120 (i.e., ’1’ mation symbol x3, a first parity symbol Y3, a second parity has been received first by the interleaver 120, ’2’ has been symbol z3, . . . in this order. received second, etc.). Because of the nature of a turbo code, The 1st interleaver 120 interleaves encoded symbols at a 15 the lS*-interleaver input follows the pattem of x, y, z, x, y, z, TT1 (Transmission Time interval) according to the number x,y, Z, . . . . of input symbols, interleaving can be considered in two F1G. 5A illustrates an example of VMnterleaver output steps. when R 1/3 and TT1 20 ms. Referring to F1G. 5A, the VMnterleaver output sequence is 1, 3, 5, 7, 9, 11, 13, 15, 17, First Step 2o 19, . . . , 160 in an interleaved order in the pattern of x, z, y, x, z, y, x, z, y, .... 1. The total number of colunms is determined referring to F1G. 5B illustrates an example of Vt-interleaver output Table 1 shown below. when R 1B and TT1 40 ms. Referring to F1G. 5B, the 2. A minimum integer R~ is found in an equation given by l~*-interleaver output sequence is 1, 5, 9, 13, 17, 21, 25, 29, 25 33, . . . , 160 in an interleaved order in the pattern of x, y, KI<RIXCI (1) z, x, y, z, x, y, z .... FIG. 5C illustrates an example of VMnterleaver output where R~ is the number of rows, K~ is the length of the input when R 1B and TT1 80 ms. Referring to FIG. 5C, the block (total encoded symbols), and C~ is the number of l~t-interleaver 17, 25, 33, 41, 49, 57, columns, wherein the number of columns C1 is 1, 2, 4 or 8 30 65, . .., 160 inoutput sequence is 1, 9,in the pattern of x, z, an interleaved order according to TTls. y, x, z, y, x, z, y .... 3. The input symbols of the VMnterleaver are sequenF1G. 6 illustrates an example of VMnterleaver input after tially arranged by rows in an rectangular array having R~ turbo encoding 160 input bits at code rate R 1½ and TT1 80 rows and C~ columns. ms. When TTI=10 ms, the 1st -interleaver input is identical to 35 the Vt-interleaver output, in F1G. 6, a blank rectangle Second Step denotes a system information symbol x and a rectangle marked with black dots denotes a parity symbol y. 1. Columns are reordered according to an inter-column in F1G. 6, the 1~* interleaver 120 sequentially receives permutation pattern {P,(j)}j 0, 1,..., C-l) shown in Table encoded symbols 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, . . ., 160 from 1. P~(j) represents the original column of a j*~’ permuted 4o the turbo encoder 110. Each number represents an order of column and the pattern is derived by a bit reverse method. encoded symbol received from the turbo encoder 110. in the bit reverse method, the binary bit sequence of each Because of the nature of the turbo code, the VMnterleaver number is reversed, e.g., 00-~00, 01-~10, 10-~01, and input follows the pattern of x, y, x, y, x, y, .... 11-~11, as shown by the 40 ms TT1 row in Table 1. 45 F1G. 7A illustrates an example of l~*-interleaver output when R 1/2 and TT1 20 ms. Referring to F1G. 7A, the TABLE 1 l~*-interleaver output sequence is 1, 3, 5, 7, 9, 11, 13, 15, 17, TTI Total number of columns inter-colmml permutation patterns 19,..., 159, 2, 4, 6, 8,..., 160 in an interleaved order. The first half {1, 3, 5, . . . , 159} of the interleaver output is 10 ms 1 {0} 20 ms 2 {0, 1} 5o information symbols x, and the last half {2, 4, 6, . . ., 160} 40 ms 4 {0, 2, 1, 3} is parity symbols y. That is, the information symbols are 80 ms 8 {0, 4, 2, 6, 1, 5, 3, 7} followed by the parity symbols in the Vt-interleaver output. F1G. 7B illustrates an example of V*-interleaver output 2. The VMnterleaver output is a sequence resulting from when R 1½ and TT1 40 ms. Referring to F1G. 7B, the reading the permuted RlxC~ array by columns. Bits that do 55 1s*-interleaver output sequence is 1, 5, 9, 13, ..., 155, 159, not exist in the Vt-interleaver input are excluded from 2, 6, 10, 14, . . . , 156, 160 in an interleaved order. The first outputting by eliminating 11 defined as half {1, 5, 9, 13, . . . , 159} of the interleaver output is information symbols x, and the last half {2, 6, 10, 14, . . ., XCI-K I1 ]~i (2) 1 156, 160} is parity symbols y. That is, the information By interleaving using Eqs. 1 and 2, the 1"~ interleaver 120 6o symbols are followed by the parity symbols in the 1~*interleaver output. outputs interleaved symbols in a similar pattern as a turbo encoder output pattem, that is, in the pattern of x, y, z, x, y, F1G. 7C illustrates an example of V*-interleaver output z, . . . (or x, z, y, x, z, y, . . . with parity symbols z and y when R 1½ and TT1 80 ms. Referring to F1G. 7C, the exchanged in position). l~t-interleaver output sequence is 1, 9, 17, 25,..., 127, 135, When TT1 is 10 ms, the number of columns C~ is 1. 65 143,151,159, 2, 10, 18,..., 144, 152, 160 in an interleaved Therefore, the 1s~ interleaver input and the 1s~ interleaver order. The first half {1, 9, 17, 25,..., 143,151, 159} of the output are identical. interleaver output is information symbols x, and the last half APLNDC-WH-A 0000014062 US 7,050,410 B1 7 8 {2, 10, 18, ..., 144, 152, 160} is parity symbols y. That is, The purpose of using the component rate matchers 142, the information symbols are followed by the parity symbols 143, and 144 of FIG. 2 is to increase the data transmission in the lSt-intedeaver output. efficiency and improve system performance in a multipleaccess/multiple-channel system using the above-described The intedeaver outputs shown in FIGS. 5A, 5B, and 5C are given on the assumption that an intedeaver size (160) 5 channel encoding mechanism. Rate matching refers to control of input bit number to output bit number through is an integer multiple of TTI/10 ms ( 1, 2, 4, or 8). In case puncturing when the input size is larger than the output size an interleaver size is not an integer multiple of TTI/10 ms, or repetition when the input size is smaller than the output a different lSMntedeaver output is produced. size. The symbol puncturing or repetition is generally perThe radio frame segmenter 130 of FIG. 2 segments a frame of 10, 20, 40, or 80 ms into 10-ms radio frame blocks. 10 formed periodically but the following should be considered for rate matching when a turbo code is used. Because the ratio (L/T) of an input frame size (L) to the TTI 1. Because the turbo code is a systematic code, a system(T TTI/10 ms) of an input frame is not always an integer, atic information symbol part of encoded symbols should be the number (r) of filler bits is calculated by Eq. 3 to excluded from puncturing. compensate for L/T with the filler bits (L is in units of bits or symbols). Here, T {1, 2, 4, 8}. If the input frame size 15 2. The minimum free distance between final codes preferably maximizes that of each component encoder since two (number of coded symbols) of the first intedeaver is an component encoders are connected in parallel in a turbo integer multiple of TTI/10 ms, the filler bit is not needed encoder by definition of a turbo code. Therefore, the output (~0). If the TTI is 20 ms and the input frame size is not an symbols of the two component encoders should be equally integer multiple of 2(TTI/10 ms), the number of filler bits r is 1. If the TTI is 40 ms and the input frame size is not an 20 punctured to achieve optimal performance. In the rate matching structure shown in FIG. 2, rate integer multiple of 4, the number of filler bit r can be 1, to matching is implemented separately for each component rate 3. If the TTI is 80 ms and the input frame size is not an matcher. The first, second, and third component rate matchinteger multiple of 8, the number of filler bits can be 1 to 7. ers 142, 143, and 144 subject an information symbol x, a first The (L+r)/T value resulting from the filler bits is defined as 25 parity symbol y, and a second parity symbol z, respectively, R(number of row). to rate matching. According to a given input and output r T-(L rood T) where r ~{0, 1, 2, 3 .... T-l}. (3) sizes, each rate matcher performs puncturing/repetition on a predetermined number of symbols. This rate matching strucRi (Li+rO/]"~ (4) ture is built on the assumption that the DEMUX 141 outputs 30 x, y, z, separately. Hence, the DEMUX 141 should be able Ifr is not 0, the radio frame segmenter 130 inserts a filler to separate a radio frmne received from the radio frame bit into the last bit position of a corresponding frame from ~’ radio frame in order to maintain a radio frame segmenter 130 into symbols x, y, z in a certain order. a (T-r+l) A description of radio frame output patterns of the radio size of R. The filler bit is arbitrarily chosen as a 0 or 1. Now frame segmenter 130 will be given. Radio frames are read a description will be made of the bit-basis operation of the 35 down by colurruls and each colurrul corresponds to a radio radio frame segmenter 130. frame. For description of bits prior to processing in the radio FIG. 8A illustrates an output pattern of the radio frame frame segmenter 130, it is assumed that the number of filler segmenter 130 when R 1B and TTI 10 ms. Referring to bits r has been calculated. Here, t represents the index of a FIG. 8A, a radio frame output pattern is identical to a radio radio frame, ranging from 1 through T (1 -<t_<T). t 1 for the 4o frame input pattern, that is, x, y, z, x, y, z, . . . . first radio frame, t 2 for the second radio frame, and FIG. 8B illustrates an output pattern of the radio frame similarly, t T for the last radio frame. Each radio frame is segmenter 130 when code rate R 1B and TTI 20 ms. the same size (L+r)/T. It is assumed that the l~Mnterleaver Referring to FIG. 8B, a first radio frame RF #1 is output in output is bl, b2 ..... bL, T ( TTI/10 ms) {1, 2, 4, 8}, and the pattern of x, z, y, x, z, y, . . . and a second radio frame the radio frame segmenter output symbols are Cl, c2, . . . , 45 RF #2 is output in a radio frame pattern of..., x, y, x, z, c(L+~9/r in a 10-ms frame. Then, y, x, z, . . . . The output patterns correspond to the output from the Vt interleaver shown in FIG. 5A. TABLE 2 FIG. 8C illustrates an output pattern of the radio frame segmenter 130 when R 1B and TTI 40 ms. Referring to output symbols of the radio frame segmenter for the first 10 msec: t = 1 50 FIG. 8C, a first radio frame RF #1 is output in the pattern cj=bj j = 1,2 ..... (L+r)/T output symbols of the radio frame segmenter for the second 10 msec: t = of..., x, y, z, x, y, z,..., a second radio frame RF #2 in 2 the pattern of..., z, x, y, z, x, y, . . ., a third radio frame j = 1, 2, . . . , (L + r)/T Cj = b(i+(L+lg/~r) RF #3 in the pattern of .... y z, x, y, z, x ..... and a fourth radio frame RF #4 in the pattern of... , x, y, z, x, y, 55 z,.... The output patterns correspond to the output from the a’ 10 msec: output symbols of the radio frame segmenter for the (T - r) Vt interleaver shown in FIG. 5B. t = (T - r) FIG. 8D illustrates an output pattern of the radio frame cj = b(i+(~r r ~)(I~+r~/~r j = 1, 2, . . . , (L + r)/T ourput symbols of the radio frame segmenter for the (T - r + 1)a’ segmenter 130 when R 1B and TTI 80 ms. Referring to 10 msec: t = (T - r + 1)~’ FIG. 8D, a first radio frame RF #1 is output in the pattern Cj = b(j+(T r)(L+r)/T) j = 1, 2, . . . , (L + r)/T - 1 60 of..., x, z, y, x, z, y,..., a second radio frame RF #2 in cj = fillerbit (0/1) j = (L + r)/T the pattern of..., y, x, z, y, x, z, . . ., a third radio frame RF #3 in the pattern of..., z, y, x, z, y, x,..., a fourth radio frame RF #4 in the pattern of..., x, z, y, x, z, y,..., a fifth output bits of the radio frame segmenter for the T 10 msec: t = T radio frame RF #5 in the pattern of... , y, x, z, y, x, Cj = b(j+(T I)(L+r)/T) j = 1, 2, . . . , (L + r)/T - 1 65 z,..., a sixth radio frame #6 in the pattern of..., z, y, x, cj = fillerbit (0/1) j = (L + r)/T z, y, x, a seventh radio frame RF #7 in the pattern of..., x, z, y, x, z, y, ..., and an eighth radio frame RF #8 in the APLNDC-WH-A 0000014063 US 7,050,410 B1 9 10 pattern of... , y, x, z, y, x, z, . . . . The output patterns Although filler bits are inserted, radio frames may have correspond to the output from the 1st interleaver shown in the same initial symbols as those in the filler bit-free case. An example of such a case using three filler bits for TTI 40 FIG. 5C. Output patterns of the radio frame segmenter 13D have a ms will be described. certain regularity. Each radio frame pattern with the same 5 FIGS. 1DA and 1DB illustrate l~Mnterleaver input, 1s~TTI has a different initial symbol x, y, or z but has the same interleaver output, and radio frame segmenter output accordsymbol repeating pattern. For TTIs 10 ms and 40 ms, ing to the first embodiment. symbols are repeated in the pattern of... , x, y, z, x, y, If the input of the 1s~ interleaver 12D for TTI 40 ms is z,..., and for TTIs 20 ms and 80 ms, symbols are repeated given in FIG. 1DA, it is interleaved by columns according to in the pattern of x, z, y, x, z, y, .... 10 an interleaving rule of the 1~t interleaver 12D as shown in The radio frames in the above cases are free of a filler bit. FIG. 1DB. The resulting VMnterleaver output (i.e., the radio This is because the input size is an integer multiple ofTTI/10 segmenter input) is x, y, z, x, y, z, z, x, y, z, x, y, z, x, y, z, ms. When filler bits are to be inserted, radio frames have x, y, z, x, y. The output of the radio frame segmenter different patterns from the above-described patterns. The shown in FIG. 1DC results from adding filler bits to the radio first through fourth embodiments as described below pertain 15 frame segmenter input. to insertion of filler bits. The filler bits are 0s. Symbols in the array of FIG. 1DC are read column by colunm and each column represents one FIRST EMBODIMENT radio frame. As shown in FIG. ll)C, each radio frame has a different initial symbol but follows the same symbol repetiFIGS. 9A, 9B, and 9C illustrate lSt-interleaver input, 2o tion pattern of... , x, y, z, . . . . That is, the radio frames l~Mnterleaver output, and radio frame segmenter output have the same initial symbols in this filler bit inserting case according to a first embodiment of the present invention. ~ interleaver 12D for TTI 80 ms is as those in the filler bit-free case. If the input of the 1 The initial symbol of each radio frame is determined by given in FIG. 9A, it is interleaved by columns according to a TTI and ~ interleaver 12D, as shown in segmenter the number of filler bits added by the radio frame an interleaving rule of the 1 25 131). Herein below, initial symbols in all possible FIG. 9B. Then, symbols are read down each column starting cases will be described. Tables 3 to 6 list initial symbols for from the left to the right column in the array of FIG. 9B. The TTIs 10, 20, 40, and 80 ms, respectively, when the radio resulting VMnterleaver output (i.e., the radio segmenter frame segmenter 13D outputs radio frames RF#1, RF #2, RF input) is x, z, y, x, z, y, x, z, y, z, y, x, z, y, x, z, y, x, y, x, #3, RF #4, RF #5, RF #6, RF #7, and RF #8 sequentially. z, y, x, z, y, x, z, x, z, y, X, z, y, x, z, y. The output of the 30 radio frame segmenter 13D results from adding filler bits to TABLE 3 the radio frame segmenter input. In the first embodiment, the filler bits are 0s. In the first TTL = 10 ms embodiment of the present invention, the radio frame segInitial symbol of meuter 13D outputs the symbols received from the inter- 35 total number of filler bits RF #1 leaver 12D in a such way that the all of the filler bits are 0 x placed towards the end of the last row, as shown in FIG. 9C. In FIG. 9B, the last positions in the second, fourth, sixth and eight columns are empty. Instead of filling those positions with filler bits, the next symbol coming after the empty 40 TABLE 4 position is used to fill the empty position. For example, to fill the last position in the second column, the ’z’ symbol from TTL = 20 ms the first position in the third column is moved in to the empty Initial symbol of position in the second column. The position previously occupied by the ’z’ symbol is now occupied by the ’y’ 45 total number of filler bits RF #1 RF #2 symbol which came after the ’z’ symbol in the third column. 0, 1 X y Basically the positions of the symbols have been pushed up by one position. This process is repeated to fill the empty position in the fourth column, and so on. However, the last In Table 4, since the 1"~ interleaver 120 leaves the columns positions in the last four columns (i.e., column #5, 6, 7 and 5o intact, positions are not changed when one filler bit is used. 8) are filled with the filler bits so that the filler bits are Consequently, the initial symbols are the same as those in pushed towards the end of the last row, as shown in FIG. 9C. the filler bit-free case. Symbols in the array of FIG. 9C are read column by column and each column represents one radio frame. As shown in TABLE 5 FIG. 9C, each radio frame has a different initial symbol but 55 follows the same symbol repeating pattern of x, z, y, except TTL = 40 ms for radio frames 4 and 6 because of the position shifting. Initial s,/mbol of However, the repeating patterns for the radio frames 4 and 6, which are shown below in Table 15, can be used. The total number of filler bits RF #1 RF #2 RF #3 RF #4 patterns in the radio frames follow the predetermined repeat- 60 0, 1,3 x z y x ing patterns shown in Table 15 except for the tail ends of 2 x z z x certain radio frames. In those cases, the tail ends are ignored and treated as if the tail ends follow the predetermined repeating patterns shown in Table 15 and are rated matched When one or three filler bits are used, the number of according to the predetermined repeating patterns. That is, 65 symbols in each column before interleaving is equal to that the radio frames have different initial symbols in the filler bit of symbols in the column of the same index after interleavinserting case, as compared to the filler bit-free case. ing. Therefore, the initial symbols are the same as those in APLNDC-WH-A 0000014064 US 7,050,410 B1 11 12 the filler bit-free case. If two filler bits are used, the number of symbols in each column before interleaving is different from that of symbols in the column of the same index after interleaving. Therefore, the initial symbols are different from those in the filler bit-free case. TABLE 6 TTL = 80 ms 0, 1, 7 2, 3 4 5, 6 x x x x RF #2 RF #3 y y y y z z y y TABLE 7 10 initial symbol of total number RF of filler bits #1 and 80 ms, respectively, when the radio frame segmenter 130 outputs radio frames RF#1, RF #2, RF #3, RF #4, RF #5, RF #6, RF #7, and RF #8 sequentially. The initial symbols of the radio frames in the second embodiment are independent of the total number of the filler bits, as shown below; however, in the first embodiment, the initial symbols of the radio frames are dependent on the total number of the filler bits. TTI = 10 ms RF RF RF RF RF #4 #5 #6 #7 #8 x x z z Y X Z X z y y z x z z x y y y y initial symbol of RF #1 When one or seven filler bits are used, the number of symbols in each column before interleaving is equal to that 2o of symbols in the column of the same index after interleaving. Therefore, the initial symbols are the same as those in the filler bit-free case. If two, three, four, five, or six filler bits are used, the number of symbols in each column before interleaving is different from that of symbols in the column 25 of the same index after interleaving. Therefore, the initial symbols are different from those in the filler bit-free case. As noted from the above tables, symbols are repeated in the pattern of x, y, z, x, y, z, for TTIs 10 ms and 40 ms, whereas symbols are repeated in the pattern of x, z, y, x, z, 3o y, for TTIs 20 ms and 80 ms. Therefore, given a TTI and the number of filler bits to be inserted by the radio frame segmenter 130, the DEMUX 141 demultiplexes l St-interleaver output in the above-described nlallller. x 15 TABLE 8 TTI = 20 ms initial symbol of RF #1 RF #2 X y TABLE 9 TTI = 40 ms initial symbol RF #1 RF #2 RF #3 RF #4 X z y x 35 SECOND EMBODIMENT TABLE 10 TTI = 80 ms FIGS. llA to llD illustrate lSt-interleaver input, 1stinitial symbol of interleaver output, and radio frame segmenter output accord- 40 ing to a second embodiment of the present invention. The RF RF RF RF RF RF RF RF second embodiment is different from the first embodiments #1 #2 #3 #4 #5 #6 #7 #8 in that filler bits are inserted by the 1 st interleaver 120 instead X y z x y z x y of the radio frame segmenter 130. Instead of pushing the filler bit positions to the end of the last row, as in the first 45 As noted from the above tables, symbols are repeated in embodiment (i.e., FIG. 9C), the interleaver 120 fills the the pattern of x, y, z, x, y, z, for TTIs 10 ms and 40 ms, empty positions with filler bits, as shown in FIG. llC. In whereas symbols are repeated in the pattern of x, z, y, x, z, terms of initial symbols and repeating patterns, this case is y, for TTIs 20 ms and 80 ms. the same as the typical filler bit-free case. If the input of the 1st interleaver 120 for TTI 80 ms is50 Therefore, given a TTI, the DEMUX 141 demultiplexes given as in FIG. llA, it is interleaved by columns according VMnterleaver output in the above-described manner. to an interleaving rule of the 1st interleaver 120 as shown in THIRD EMBODIMENT FIG. llB. Then, filler bits are inserted to the array of FIG. llB as shown in FIG. llC. Here, the filler bits are 0s. Therefore, the lSt-interleaver output, i.e., the radio frame 55 FIGS. 12A, 12B, and 12C illustrate VMnterleaver input, segmenter input is a sequence of x, z, y, x, z, y, z, y, 0, z, y, lSMnterleaver output, and radio frame segmenter output according to a third embodiment of the present invention. x, z, y, x, z, y, x, 0, y, x, z, y, x, z, y, x, z, 0, x, z, y, x, z, y, x, z, y, 0. The output of the radio frame segmenter 130 is The third embodiment is different from the second embodishown in FIG. llD. ments in that a controller (host) designates filler bit insertion The symbols in the array of FIG. llD are read down by 6o positions and the radio l?ame segmenter 130 inserts the filler column from left to right and each column is a radio frame. bits in the designated positions. In terms of initial symbols and repeating patterns, this case is the same as the typical As shown in FIG. llD, each radio frame follows the same repeating pattern of x, z, y with a different initial symbol. As filler bit-free case. noted from FIGS. llA to liD, the initial symbols are the If the input of the 1s~ interleaver 120 for TTI 80 ms is same as those in the general filler bit-free case. 65 given in FIG. 12A, it is interleaved by columns according to The initial symbol of each radio frame is determined by an interleaving rule of the 1"t interleaver 120 as shown in a TTI. Tables 7 to 10 list initial symbols for TTIs 10, 20, 40, FIG. 12B. Therefore, the lSMnterleaver output, i.e., the radio APLNDC-WH-A 0000014065 US 7,050,410 B1 13 14 frame segmenter input is a sequence of x, z, y, x, z, y, x, z, y, z, y, x, z, y, x, z, y, x, y, x, z, y, x, z, y, x, z, x, z, y, x, z, y, x, z, y. A controller (host) designates filler bit insertion positions and then the radio frame segmenter 130 inserts the filler bits in the designated positions as shown in F1G. 12C. 5 in this embodiment, the filler bits are 0s. The symbols in the array of F1G. 12C are read down column by column from left to right and each column is a radio frame. As shown in F1G. 12C, each radio frame follows the same repeating 10 pattern of x, z, y with a different initial symbol. As noted from F1GS. 12A, 12B, and 12C, initial symbols are the same as those in the general filler bit-free case. The initial symbol of each radio frame is determined by 15 a TT1. Tables 11 to 14 list initial symbols for TTls 10, 20, 40, and 80 ms, respectively, when the radio frame segmenter 130 outputs radio frames RF#1, RF #2, RF #3, RF #4, RF #5, RF #1 RF #6, RF #7, and RF #8 sequentially. The initial symbols of the radio frames in the third embodiment are independent 2o x of the total number of the filler bits, as shown below. TABLE 13 TTL - 40 ms initial symbol RF #1 RF #2 RF #3 RF #4 X z y x TABLE 14 TTL = 80 ms initial symbol of RF #2 RF #3 RF #4 RF #5 RF #6 RF #7 RF #8 y z x y z x y As noted from the above tables, symbols are repeated in the pattern of x, y, z, x, y, z, for TTls 10 ms and 40 ms, 25 whereas symbols are repeated in the pattern of x, z, y, x, z, y, for TTls 20 ms and 80 ms. Given a TT1, the DEMUX 141 demnltiplexes lSt-interleaver output in the above-described manner. TABLE 11 TTI = 10 ms initial symbol of RF #1 x 30 Returning to F1G. 2, the DEMUX 141 demultiplexes a radio frame received from the radio frame segmenter 131) into its symbols x, y, z, according to a switching rule. The switching rule is deternlined by a TT1 and the number of filler bits used by the radio frame segmenter 131) in the first 35 embodiment and a TTI in the second and third embodiments. The symbols are repeated in a certain pattern. The repeating patterns for the embodiments are tabulated in Tables 15 and 16. in the tables, N/A indicates "not applicable". TABLE 12 TTI = 20 ms initial symbol of RF #1 RF #2 X y TABLE 15 For First Embodiment total number Switching rules (repeating patterns) TTI of filler bits RF #1 RF #2 RF #3 RF #4 RF #5 RF #6 RF #7 RF #8 10 ms 20 ms 40 ms 0 0, 1 0, 1, 3 2 0, 1,7 2, 3 4 5, 6 x, y, z x, z, y x, y, z x, y, z x,z,y x, z, y x, z, y x, z, y N/A y, x, z z, x, y z, x, y y,x,z y, x, z y, x, z y, x, z N/A N/A y, z, x z, x, y z,y,x z, y, x y, x, z y, x, z N/A N/A x, y, z x, y, z x,z,y x, z, y z, y, x z, y, x N/A N/A N/A N/A y,x,z x, z, y z, y, x x, z, y N/A N/A N/A N/A z,y,x y, x, z y, x, z z, y, x N/A N/A N/A N/A x,z,y z, y, x z, y, x x, z, y N/A N/A N/A N/A y,x,z y, x, z y, x, z y, x, z 80 ms TABLE 16 For Second aald Third Embodiments Switching rules (repeating patterns) TTI RF #1 RF #2 RF #3 RF #4 RF #5 RF #6 RF #7 RF #8 10 ms 20 ms 40 ms 80 ms x,y,z x,z,y x,y,z x,z,y N/A y,x,z z,x,y y,x,z N/A N/A y,z,x z,y,x N/A N/A x,y,z x,z,y N/A N/A N/A y,x,z N/A N/A N/A z,y,x N/A N/A N/A x,z,y N/A N/A N/A y,x,z APLNDC-WH-A 0000014066 US 7,050,410 B1 15 16 If two filler bits are used for TTI 40 ms in the first and second embodiments, the switching patterns in the DEMUX 141 are x, y, z, x, y, z for the first radio frame, z, x, y, z, x, y for the second radio frame, z, x, y, z, x, y for the third radio frame, and x, y, z, x, y, z for the fourth radio frame. In the second and third embodiments, the initial symbol of each radio frame only needs to be given because the repeating patterns are already predetermined based on the TTI. However, in the first embodiment, the total number of the filler bits also needs to be given in addition to the other information. Tables 17 19 reflect that difference between the embodiments. the DEMUX 141 and the MUX 145 based on the initial symbol and a repeating/puncturing pattern determined by the TTI. The DEMUX 141 separates the current radio frame symbols into input for the corresponding component rate matchers and the MUX 145 multiplexes the output symbols of the rate matchers to a radio frame. Here, the DEMUX 141 separates an information symbol, a first parity symbol, and a second parity symbol from a radio frame stream received from the radio frame segmenter 130. The component rate matchers 142, 143, and 144 rate match the information symbol, the first parity symbol, and the second parity symbol from the DEMUX 141, respectively, by puncturing 10 TABLE 17 For First Embodiment Initial symbol of total number TTI of filler bits RF #1 RF #2 RF #3 RF #4 RF #5 RF #6 RF #7 RF #8 10 ms 20 ms 40 ms 0 0, 1 0, 1, 3 2 0, 1, 7 2,3 4 5,6 x x x x x x x x N/A y z z y y y y N/A N/A y z z z y y N/A N/A x x x x z z N/A N/A N/A N/A y x z x N/A N/A N/A N/A z y y z N/A N/A N/A N/A x z z x N/A N/A N/A N/A y y y y 80 ms TABLE 18 For Second aald Third Embodiments initiN symbol of TTI RF #1 RF #2 RF #3 RF 84 RF #5 RF #6 RF #7 RF #8 10 ms 20 ms x,y,z x,z,y N/A y,x,z N/A N/A N/A N/A N/A N/A N/A N/A N/A N/A N/A N/A 40 ms 80 ms x,y,z x,z,y z,x,y y,x,z y,z,x z,y,x x,y,z x,z,y N/A y,x,z N/A z,y,x N/A x,z,y N/A y,x,z TABLE 19 Repeating Pat~ erns TTI 10 ms, 40 ms 20 ms, 80 ms 45 Repeating patterns . . . , x, y, z, x, y, z, . . . . . . , x, z, y, x, z, y, . . . 50 Referring to FIG. 2 again, the MUX 145 multiplexes three streams received from the component rate matchers 142, 143, and 144 to one stream, to thereby generate a ratematched radio frame with the same symbol pattern as before rate matching. Because this MUX 145 is the counterpart of 55 the DEMUX 141, it switches according to the same switching patterns. FIG. 13 is a block diagram of a DEMUX and MUX controlling apparatus according to the first embodiment of the present invention. 60 Referring to FIG. 13, upon receipt of a TTI, the total number of the filler bits, and a radio frame length from the host 200, the controller 210 feeds the TTI, the total number of the filler bits, and the radio frame index of a current radio frame to the memory 220 (see Table 17) and receives the 65 initial symbol of the current radio frame from the memory 220. The controller 210 controls the switching operations of or repetition. The component rate matcher 142 just bypasses the received information symbols without real puncturing, whereas the component rate matchers 143 and 144 puncture the received parity symbols according to a preset pattem which is determined by the ratio of the number of input symbols to the number of output symbols. In most of the real cases, the component rate matchers 143 and 144 just bypass the received parity symbols without real repetition except heavy repetition of the encoded symbols, whereas the component rate matcher 142 repeats the received information symbols according to a preset pattern determined by the ratio of the number of input symbols to the number of output symbols. The MUX 145 multiplexes the symbols received from the component rate matchers 142, 143, and 144 to one stream according to the same switching pattern as used in the DEMUX 141. FIG. 14 is a block diagram of a DEMUX and MUX controlling apparatus according to the second embodiment of the present invention. Referring to FIG. 14, upon receipt of a TTI and a radio frame length from the host 200, the controller 210 feeds the TTI, the total number of filler bits, and the radio frame index of a current radio frame to memory 220 (see Table 17) and receives the initial symbol of the current radio frame from memory 220. The number of filler bits is determined by the APLNDC-WH-A 0000014067 US 7,050,410 B1 17 18 controller 210 based on the TTI and the frame length in the As described above, the present invention is advantageous same manner as used in the radio frame segmenter. Then, the in that effective rate matching can be performed by adding controller 210 controls the switching operations of the a DEMUX before a rate matching unit to separate an DEMUX 141 and the MUX 145 based on the initial symbol information symbol and parity symbols of the encoded and a repeating/puncturing pattern determined by the TTI. 5 symbols when the information symbol is not to be punctured The DEMUX 141 separates the current radio frame symbols for rate matching in an uplink transmitter in a mobile into component rate matchers input and the MUX 145 communication system. multiplexes the output symbols of the rate-matchers to a While the invention has been shown and described with radio frame. Here, the DEMUX 141 separates an informareference to certain preferred embodiments thereof, it will be tion symbol, a first parity symbol, and a second parity 10 understood by those skilled in the art that various changes in symbol from a radio frame stream received from the radio form and details may be made therein without departing frame segmenter 130. from the spirit and scope of the invention as defined by the The component rate matchers 142, 143, and 144 rate appended claims. match the information symbol, the first parity symbol, and What is claimed is: the second parity symbol from the DEMUX 141, respec- 15 1. An uplink transmitting device in a mobile communitively, by puncturing or repetition. The component rate cation system, comprising: an encoder for receiving a first information bit stream and matcher 142 just bypasses the received information symbol without real puncturing, whereas component rate matchers for outputting three streams, a second information bit stream, a first parity stream, and a second parity stream, 143 and 144 puncture the received parity symbols according to a preset pattern determined by the ratio of the number of 2o by encoding the first information bit stream; input symbols to the number of output symbols. In most of an interleaver for interleaving the encoded streams by a the real cases, the component rate matchers 143 and 144 just predetermined interleaving rule; bypass the received parity symbols without real repetition a radio frame segmenter for receiving the interleaved except heavy repetition of the encoded symbols, whereas the stream from the interleaver and mapping the received component rate matcher 142 repeats the received informa- 25 interleaved stream onto at least one consecutive radio tion symbols according to a preset pattern determined by the frame; ratio of the number of input symbols to the number of output a demultiplexer for separating each of the at least one symbols. The MUX 145 multiplexes the symbols received radio frames received from the radio frame segmenter from the component rate matchers 142, 143, and 144 to one into a third information bit stream, and first and second stream according to the same switching pattern as used in the 30 parity streams from the demultiplexer; and DEMUX 141. a rate matcher for bypassing the third information bit FIG. 15 is a block diagram of a DEMUX and MUX stream and for puncturing a part of the first and second controlling apparatus according to the third embodiment of parity streams from the demultiplexer according to a the present invention. given rate matching rule. Referring to FIG. 15, upon receipt of a TTI and a radio 35 2. The transmitting device of claim 1, wherein the interframe length from the host 200, the controller 210 feeds the leaved stream is mapped onto consecutive radio frames TTI and the radio frame index of a current radio frame to when a transmission time interval (TTI) is longer than 10 memory 220 (see Table 18) and receives the initial symbol ms. of the current radio frame from memory 220. Then, the 3. The transmitting device of claim 1, wherein the transcontroller 210 controls the switching operations of the 4o mission time interval (TTI) is one of 10, 20, 40, and 80 ms. DEMUX 141 and the MUX 145 based on the initial symbol 4. The transmitting device of claim 1, wherein the interand a repeating/puncturing pattern determined by the TTI. leaving rule is a bit reverse method. The DEMUX 141 separates the current radio frame symbols 5. The transmitting device of claim 1, wherein an arrangeinto input for the component rate matchers and the MUX ment of information bits and parity bits in each of the at least 145 multiplexes the output symbols of the rate matchers to 45 one radio frames has a regular pattern. a radio frame. Here, the DEMUX 141 separates an infor6. The transmitting device of claim 2, wherein the conmation symbol, a first parity symbol, and a second parity secutive radio frames have initial bits determined by the symbol from a radio frame stream received from the radio TTI. frame segmenter 130. The component rate matchers 142, 7. The transmitting device of claim 5, wherein the demul143, and 144 rate match the information symbol, the first 5o tiplexer separates bits of the radio frame into the third parity symbol, and the second parity symbol from the information bit stream, and the first and second parity DEMUX 141, respectively, by puncturing or repetition. The streams from the demultiplexer according to the regular component rate marcher 142 just bypasses the received pattern. information symbol without real rate puncturing, whereas 8. The transmitting device of claim 7, further comprising: component rate matchers 143 and 144 puncture or repeat the 55 a memory for storing initial symbols of the consecutive received parity symbols according to a pattern preset deterradio frames; and mined by the ratio of the number of input symbols to the a controller for controlling the demultiplexer according to number of output symbols. The MUX 145 multiplexes the the regular pattern and the stored initial bits of the at symbols received from the component rate matchers 142, least one radio frames. 143, and 145 to one stream according to the same switching 6o 9. The transmitting device of claim 8, further comprising: pattern as used in the DEMUX 141. In most of the real cases, a multiplexer for multiplexing the outputs of the rate the component rate matchers 143 and 144 just bypass the matcher under a control of the controller. received parity symbols without real repetition except heavy 10. The transmitting device of claim 1, wherein the repetition of the encoded symbols, whereas the component interleaver interleaving the encoded stremns at a TTI (Transrate matcher 142 repeats the received information symbols 65 mission Time Interval) after inserting filler bits into the according to a preset pattern determined by the ratio of the encoded streams in order to equalize a size of the at least one number of input symbols to the number of output symbols. radio frames. APLNDC-WH-A 0000014068 US 7,050,410 B1 19 20 11. The transmitting device of claim 1, wherein the rate 22. The transmitter device of claim 12, wherein the matcher comprises: encoder is a turbo encoder. 23. A method of transmitting in a mobile communication a first component rate matcher for rate-matching the information bits; system, the method comprising the steps of: receiving an information bit stream transmitted at a prea second component rate matcher for rate-matching the 5 first parity bits; and determined transmission time interval (TTI); encoding the information bit stream and outputting the a third component rate matcher for rate-matching the encoded information bit stream and at least one type of second parity bits. parity stream corresponding to the information bit 12. A transmitting device in a mobile communication 10 stream, a number of the parity streams corresponding to system, comprising: a coding rate of an encoder; an encoder for receiving an information bit stream transinterleaving the information bit stream and the parity mitted at a predetermined transmission time interval stream and outputting the interleaved stream; (TTI) and for outputting the information bit stream and dividing the interleaved stream into at least one radio at least one type of parity stream by encoding the frame and outputting the at least one radio frame, each information bit stream in accordance with a coding rate 15 of the at least one radio frame having a predetermined of said encoder; time frame; an interleaver for receiving the information bit stream and demultiplexing the received radio frame back into the the at least one type of parity stream from the encoder, information bit stream and at least one type of parity for interleaving the information bit stream and the at stream; and least one type of parity stream and for outputting 20 rate matching the demultiplexed streams by a rate interleaved stream; matcher; a radio frame segmenter for receiving the interleaved wherein parity bits in the radio frame are switched to a stream from the interleaver, for dividing the received component rate marcher corresponding to each of the at stream into radio frames, and for outputting the radio 25 least one parity stream, said component rate marcher frames in sequence; having at least one parity component rate marcher for a demultiplexer for receiving the radio frames and for rate matching a part of said at least one parity stream, demultiplexing the received radio frames back into the a number of the at least one parity component rate information bit stream and the at least one type of parity matcher being equal to a number of the at least one stream; and parity stream. a rate matcher for rate matching the streams received from 24. The method of claim 23, wherein bits of the at least the demultiplexer and outputting rate matched streams, one radio frame are separated to the component rate matcher said rate matcher having at least one component rate by the demultiplexer in accordance with a regular pattern for matcher for rate matching a part of the parity stream, a arranging information bits and parity bits in each radio number of the at least one component rate matcher 35 frame. being equal to a number of the parity streams, 25. The method of claim 24, wherein the regular pattern wherein the demultiplexer switches each of the parity bits is determined by the TTI. in the radio frames to said at least one component rate 26. The method of claim 25, wherein the regular pattern matcher corresponding to each of the parity bits. is further determined by the coding rate. 13. The transmitter device of claim 12, wherein bits of the 27. The method of claim 23, further comprising the step radio frame are separated to the at least one component rate 4o of." matcher corresponding to each type of parity stream in multiplexing the rate matched streams by synchronizing accordance with a regular pattern for arranging information the multiplexing with the demultiplexing by switching bits and parity bits in each radio frame. to the corresponding component rate matcher. 14. The transmitter device of claim 13, wherein the 45 28. The method of claim 23, wherein the predetermined regular pattern is determined by the TTI. length of the radio frame is 10 ms. 15. The transmitter device of claim 14, wherein the 29. The method of claim 23, wherein the TTI is one of 10, regular pattern is further determined by the coding rate. 20, 40 and 80 ms. 16. The transmitter device of claim 12, further compris30. The method of claim 23, wherein the coding rate is 1/3. ing: 50 31. A transmitting device in a mobile communication a multiplexer for multiplexing the rate matched streams system, comprising: by switching outputs of the at least one component rate an encoder for receiving an information bit stream transmatcher. mitted at a predetermined transmission time interval 17. The transmitter device of claim 16, further compris(TTI) and for outputting the information bit stream and ing: 55 at least one kind of parity stream corresponding to the a controller for controlling the switching of the demultiinformation bit stream in accordance with a coding rate plexer and the multiplexer based on at least one of the of said encoder; TTI and the length of each of the radio frames. an interleaver for receiving the information bit stream and 18. The transmitter device of claim 12, wherein a length the parity stream from the encoder, for interleaving the of each of the radio frames is 10 ms. 60 information bit stream and the parity stream, and for 19. The transmitter device of claim 12, wherein the TTI outputting an interleaved stream; is one of 10, 20, 40 and 80 ms. a demultiplexer for receiving the interleaved stream and 20. The transmitter device of claim 12, wherein the coding for demultiplexing the received interleaved stream rate is 1~. back into the infomlation bit stream and the at least one 21. The transmitter device of claim 13, further comprising 65 kind of parity stream; and a memory for storing the regular pattern including an initial a rate matcher for rate matching the information bit symbol corresponding to each of the radio frames. stream and the at least one kind of parity stream APLNDC-WH-A 0000014069 US 7,050,410 B1 21 22 44. The method of claim 41, further comprising the step received from the demultiplexer, wherein said rate matcher includes at least one component rate matcher of: for rate matching a part of the at least one kind of parity multiplexing the output bits of the rate matching step by stream, and a number of the component rate matcher is synchronizing the multiplexing with the demultiplexequal to a number of the at least one kind of parity 5 ing by switching in the rate matcher. stream, 45. The method of claim 41, wherein a length of at least wherein the demultiplexer switches bits in the interleaved one of the information bit stream and the interleaved stremn stream to the component rate marcher corresponding to is 10 ms. each of the at least one kind of parity stream. 46. The method of claim 41, wherein the TTI is one of 10, 32. The transmitter device of claim 31, wherein the 10 20, 40 and 80 ms. demultiplexer switches each of the bits of the interleaved 47. The method of claim 41, wherein the coding rate is 1/3. stream to the at least one component rate matcher in accor48. A mobile communication system, comprising: dance with a regular pattern for arranging information bits an encoder for receiving an information bit stream and for and parity bits in the interleaved stream. outputting three encoder output streams, an information 33. The transmitter device of claim 32, wherein the 15 bit stream, a first parity stream, and a second parity regular pattern is determined by the TTI. stream, by encoding the information bit stream; 34. The transmitter device of claim 32, further comprisan interleaver coupled to the encoder for performing an ing: interleaving operation according to a predetermined a multiplexer for synchronously multiplexing output bits interleaving rule; of the at least one component rate matcher by synchro- 20 a radio frame segmenter for receiving an interleaved nizing with the demultiplexer. stream from the interleaver and mapping the inter35. The transmitter device of claim 34, further comprisleaved stream onto at least one radio frame; ing: a demultiplexer for separating the at least one radio frame a controller for controlling the demultiplexer and the received from the radio frame segmenter into three 25 multiplexer based on the regular pattern. demultiplexer output streams; and 36. The transmitter device of claim 31, wherein a length a rate matcher for bypassing an information bit stream of at least one of the information bit stream and the interfrom the demultiplexer and for puncturing a part of a leaved stream is 10 ms. first and second parity streams from the demultiplexer 37. The transmitter device of claim 31, wherein the TTI according to a given rate matching rule. is one of 10, 20, 40 and 80 ms. 49. The system of claim 48, wherein the interleaved 38. The transmitter device of claim 31, wherein the coding stream is mapped onto consecutive radio frames when a rate is 1A. transmission time interval (TTI) is longer than 10 ms. 39. The transmitter device of claim 33, further comprising: 50. The system of claim 48, wherein the interleaver a memory for storing the regular pattern including an 35 performs the interleaving operation at a TTI (Transmission initial symbol corresponding to the interleaved stream. Time Interval), after inserting filler bits into an output of the 40. The transmitter device of claim 31, wherein the encoder, in order to equalize a size of the at least one radio encoder is a turbo encoder. frames. 41. A method of transmitting in a mobile communication 51. The system of claim 48, wherein the rate matcher system, the method comprising the steps of: 40 comprises: receiving an information bit stremn at a predetermined a first component rate matcher for rate-matching the transmission time interval (TTI); information bit stream from the demultiplexer; encoding the information bit stream and outputting the a second component rate matcher for rate-matching the encoded information bit stream and at least one kind of first parity stream from the demultiplexer; and parity stream corresponding to the information bit 45 a third component rate matcher for rate-matching the stream in accordance with a coding rate of a encoder; second parity stream from the demultiplexer. interleaving the information bit stream and the parity 52. A method for transmitting data in a mobile commustream and outputting an interleaved stream; nication system, the method comprising: demultiplexing the interleaved stream back into the inforencoding an information bit stream corresponding to a mation bit stream and the at least one kind of parity 5o coding rate of an encoder and outputting the informastream; and tion bit stream, a first parity stream, and a second parity rate matching the demultiplexed streams by a rate stream; matcher, said rate matcher including at least one comperforming an interleaving operation with an interleaver ponent rate matcher for rate matching a part of said at coupled to the encoder; least one kind of parity stream; 55 mapping an interleaved stream from the interleaver onto wherein bits in the interleaved stream are switched to at at least one radio frame and outputting the at least one least one parity component rate matcher corresponding radio frame; to each of the at least one kind of parity stream, a performing an demultiplexing operation with a demultinumber of the at least one parity component rate plexer and outputting an inlbrmation bit stream of the matcher being equal to a number of the at least one 6o demultiplexer, and a first parity stream of the demulparity stream. tiplexer, and a second parity stream of the demulti42. The method of claim 41, wherein the bits of the plexer; and interleaved stream are separated in accordance with a regular pattern for arranging information bits and parity bits in bypassing the information bit stream of the demultiplexer the interleaved stream. 65 and puncturing a part of the first and second parity 43. The method of claim 42, wherein the regular pattern stream from the demultiplexer according to a given rate is determined by the TTI. matching rule. APLNDC-WH-A 0000014070 US 7,050,410 B1 23 24 53. The method of claim 52, wherein the interleaved means for separating the at least one radio frame into a stream is mapped onto consecutive radio frames when a separate information bit stream, a first separate parity transmission time interval (TTI) is longer than 10 ms. stream, and a second separate parity stream; and 54. The method of claim 52, wherein the interleaving means for bypassing the separate information bit stream operation is performed at a TTI (Transmission Time Inter- 5 and for puncturing a part of the first and second val), after inserting filler bits into an output of the encoder, separate parity streams according to a given rate matchin order to equalize a size of the at least one radio frame. ing rule. 55. A mobile communication system, comprising: 56. The system of claim 55, wherein the interleaved means for receiving an information bit stream and for stream is mapped onto consecutive radio frames when a outputting an output stream including an information 10 transmission time interval (TTI) is longer than 10 ms. bit stream, a first parity stream, and a second parity 57. The system of claim 55, wherein the interleaving stream, by encoding the information bit stream; operation is performed at a TTI (Transmission Time Intermeans for performing an interleaving operation in val), after inserting filler bits into the output stream, in order response to the output stream and outputting an interleaved stream; 15 to equalize a size of the at least one radio frame. means for creating at least one radio frame in response to the interleaved stream; APLNDC-WH-A 0000014071

Disclaimer: Justia Dockets & Filings provides public litigation records from the federal appellate and district courts. These filings and docket sheets should not be considered findings of fact or liability, nor do they necessarily reflect the view of Justia.


Why Is My Information Online?