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

Filing 662

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 26, #2 Exhibit Mueller Decl Exhibit 27, #3 Exhibit Mueller Decl Exhibit 28, #4 Exhibit Mueller Decl Exhibit 29, #5 Exhibit Mueller Decl Exhibit 30, #6 Exhibit Mueller Decl Exhibit 31, #7 Exhibit Mueller Decl Exhibit 32, #8 Exhibit Mueller Decl Exhibit 33, #9 Exhibit Mueller Decl Exhibit 34, #10 Exhibit Mueller Decl Exhibit 35, #11 Exhibit Mueller Decl Exhibit 36, #12 Exhibit Mueller Decl Exhibit 37, #13 Exhibit Mueller Decl Exhibit 38, #14 Exhibit Mueller Decl Exhibit 39, #15 Exhibit Mueller Decl Exhibit 40, #16 Exhibit Mueller Decl Exhibit 41)(Related document(s) #660 ) (Selwyn, Mark) (Filed on 1/25/2012)

Download PDF
Mueller Exhibit 30 US007200792B2 (12) United States Patent (10) Patent No.: US 7,200,792 B2 (45) Date of Patent: Apr. 3, 2007 Kim et al. (54) INTERLEAVING APPARATUS AND METHOD FOR SYMBOL MAPPING IN AN HSDPA MOBILE COMMUNICATION SYSTEM (75) inventors: Hun-Kee Kim, Seoul (KR); Gin-Kyu Choi, Seoul (KR); Jae-Seung Yoon, Songnam-shi (KR); Noh-Snn Kim, Suwon-shi (KR); Jan-Sung Lee, Suwon-shi (KR); Yong-Snk Moon, Songnam-shi (KR) 6,351,832 B1 * 6,560,748 B2 * 6,631,491 B1 * 7,028,230 B2 * 2002/0159501 A1 * 2003/0079170 A1 * 2/2002 5/2003 10/2003 4/2006 10/2002 4/2003 Wei ............................ Li .............................. Shibutani et al ............ Manninen et al ........... Agami et al ................ Stewart et al ............... 714/701 714/786 714/762 714/702 375/130 714/755 FORE1GN PATENT DOCUMENTS EP JP 1 248 404 2001-332980 10/2002 11/2001 (73) Assignee: Samsung Electronics Co., Ltd. (KR) Subject to any disclaimer, the term of this patent is extended or adjusted under 35 U.S.C. 154(b) by 583 days. ( * ) Notice: (21) Filed: European Search Report datedApr. 29, 2003, issued in a counterpart application, namely, Appln. No. 02028629.0. Appl. No.: 10/324,215 (22) OTHER PUBLICATIONS (Continued) Primary Examiner Phung My Chung (74) Attorney, Agent, or Firm The Farrell Law Firm Dec. 20, 2002 Prior Publication Data (65) US 2003/0120995 A1 Foreign Application Priority Data (30) Dec. 21, 2001 (KR) ...................... 10-2001-0083064 (51) Int. CI. HO3M 13/00 (2006.01) HO3M 13/03 (2006.01) (52) U.S. CI ....................... 714/755; 714/786; 714/758; 714/790 (58) Field of Classification Search ..................... None See application file for complete search history. (56) References Cited U.S. PATENT DOCUMENTS 5,689,439 A * 11/1997 Weerackody et al ........ 220 210 GENEP, ATOR 230 ABSTRACT (57) Jun. 26, 2003 in an apparatus for data transmission in a communication system, a turbo encoder encodes data bits to generate systematic bits and parity bits, and a rate matcher matches the systematic bits and parity bits. A first interleaver writes the rate-matched systematic bits on a row by row basis, and perfomls inter-column permutation. A second interleaver writes the rate-matched parity bits on a row-by-row basis, and performs inter-column permutation. A modulator alternatively collects the permutated bits on a column by column basis from the first and second interleavers, and maps collected bits from the first and second interleavers onto one modulation symbol, wherein a size of the first interleaver is equal to a size of the second interleaver. 16 Claims, 27 Drawing Sheets 370/329 240 250 270 ENO APLNDC-WH-A 0000017615 US 7,200,792 B2 Page 2 OTHER PUBLICATIONS Samsung Electronics: "Enhanced Sylnbol Mapping Melhod for Modulation of Turbo-coded Bits based on Bit Priority," 3GPP TSG RAN WG1/WG2 Joint Meeting on HSDPA, Apr. 5-6, 2001, pp. 1-6. Nokia: "Channel lnterleaver Modification for HSDPA," TSG-RAN WG1 HSDPA ADHOC Meeting TDOC, Nov. 5-7, 2001, pp. 1-6. Samsung Electronics: "Performance Evaluation of the Enhanced Symbol Mapping Method based on Priority (SMP) in HSDPA," 3GPP TSG-RAN WG1 Meeting #20, May 21-25, 2001, pp. 1-7. Samsung Electronics: "FER Evaluation of SMP for Different TT1 Sizes in HSDPA," 3GPP TSG RAN WG1 ADHOC TDOC R1-010738, Jun. 26-28, 2001, pp. 1-4. Texas Instruments: "Frame Error Rate Based Comparison of Full Bit Level Channel Interleaving, split bit level channel interleaving and symbol based channel interleaving," TSG-RAN Working Group 1 Meeting #20, May 21-25, 2001, pp. 1-10. 3GPP: 3rd Generation Partnership Project; Technical Specification Group Radio Access Nelwork; Physical Layer Aspects of UTRA High Speed Downlink Packet Access, Feb. 27, 2001, pp. 1-92. * cited by examiner APLNDC-WH-A 0000017616 U.S. Patent Apr. 3, 2007 Sheet 1 of 27 US 7,200,792 B2 APLNDC-WH-A 0000017617 U.S. Patent Apr. 3, 2007 Sheet 2 of 27 US 7,200,792 B2 APLNDC-WH-A 0000017618 U.S. Patent Apr. 3, 2007 Sheet 3 of 27 US 7,200,792 B2 APLNDC-WH-A 0000017619 U.S. Patent Apr. 3, 2007 Sheet 4 of 27 US 7,200,792 B2 APLNDC-WH-A 0000017620 U.S. Patent Apr. 3, 2007 Sheet 5 of 27 US 7,200,792 B2 APLNDC-WH-A 0000017621 U.S. Patent Apr. 3, 2007 Sheet 6 of 27 US 7,200,792 B2 ~- STAST ) RECEIVE DATA BiTS F812 i,s...~.P~ . .._ I INITIALIZE R~"C~- BUFFER’ ~OLUMN PERMUTATIONr- FIG.6 APLNDC-WH-A 0000017622 U.S. Patent Apr. 3, 2007 Sheet 7 of 27 US 7,200,792 B2 APLNDC-WH-A 0000017623 U.S. Patent Apr. 3, 2007 US 7,200,792 B2 Sheet 8 of 27 S IST WRITE AREA ;=NO WRITE AREA R2-1 P -WRITE DIRECTION R= 1/2 FIG.8A APLNDC-WH-A 0000017624 U.S. Patent 01 Apr. 3, 2007 US 7,200,792 B2 Sheet 9 of 27 ,,. (32-! 15T WRITE AREA FIG.8B APLNDC-WH-A 0000017625 U.S. Patent 01 Apr. 3, 2007 US 7,200,792 B2 Sheet 10 of 27 ¯.. (32-1 2 1ST WRITE AREA 2NO WRITE AREA R2"1 P WRITEDIRECTION FIG.gA APLNDC-WH-A 0000017626 U.S. Patent Apr. 3, 2007 0 I Sheet 11 of 27 ..¯ US 7,200,792 B2 C2-I 18T WRITE AREA FIG.gB APLNDC-WH-A 0000017627 U.S. Patent 0 Apr. 3, 2007 1 ¯ Sheet 12 of 27 . US 7,200,792 B2 C2-1 1ST WRITE AREA R2-1 FIG.IOA APLNDC-WH-A 0000017628 U.S. Patent 01 Apr. 3, 2007 Sheet 13 of 27 .¯¯ US 7,200,792 B2 C2-1 S 2 !8T WRITE AREA 2ND WRITE AREA R2-1 R=3/4 FIG.lOB APLNDC-WH-A 0000017629 U.S. Patent 0I Apr. 3, 2007 US 7,200,792 B2 Sheet 14 of 27 ¯ ¯, C2-1 S 2 1ST WRITE AREA 2ND WRITE AREA P R2-I FIG.IOC APLNDC-WH-A 0000017630 U.S. Patent Apr. 3, 2007 o1 Sheet 15 of 27 . ¯. US 7,200,792 B2 c2-1 8 ¯ 1ST WRITE AREA 2NO WRITE AREA R2’1 FIG.IOD APLNDC-WH-A 0000017631 U.S. Patent Apr. 3, 2007 Sheet 16 of 27 US 7,200,792 B2 P 2ND READ AREA R2-1 .~’_. R= II~ FIG.IIA APLNDC-WH-A 0000017632 U.S. Patent Apr. 3, 2007 Sheet 17 of 27 US 7,200,792 B2 C2-’1 1 P 2NO READ AREA R2-1 R = 3/4 FIG.lIB APLNDC-WH-A 0000017633 U.S. Patent Apr. 3, 2007 RECEIVE BIT8 Sheet 18 of 27 US 7,200,792 B2 |20O DETERMINE C2, R2 AND x INITIALIZE R2 x C2 BUFFER 1204 WRITE DATA BITS iN PRESCRIBED WRITING METHOD END ) APLNDC-WH-A 0000017634 U.S. Patent Apr. 3, 2007 US 7,200,792 B2 Sheet 19 of 27 1310 I, 1320 1ST WRITE AREA {1ST READ AREA) 16QAM MODULATOR PARITY BITS 2ND WR~’E AFIEA (;?NO READ AREA) OUTPUT 61T PATTERN FIG.13 APLNDC-WH-A 0000017635 U.S. Patent Apr. 3, 2007 Sheet 20 of 27 US 7,200,792 B2 1 I R2-1 1/2 FIG.14A APLNDC-WH-A 0000017636 U.S. Patent Apr. 3, 2007 Sheet 21 of 27 US 7,200,792 B2 C2:-1 ! 1 R2-1 FIG.14B APLNDC-WH-A 0000017637 U.S. Patent Apr. 3, 2007 Sheet 22 of 27 US 7,200,792 B2 ! R2-1 R= 112 FIG.15A APLNDC-WH-A 0000017638 U.S. Patent Apr. 3, 2007 Sheet 23 of 27 US 7,200,792 B2 2 FIG.15B APLNDC-WH-A 0000017639 U.S. Patent Apr. 3, 2007 Sheet 24 of 27 US 7,200,792 B2 WRITE DATA BITS IN L16o6 , I PRESCRIBED WRITING METHOD I- ’ ~INB-ERT DUMMY BligF 1610 ~s .[COLUMN, PERM UTATIONF 1012 .1~1 ....... l ROW PERMUTATION ~ ~,4 I_ DEL~,,I::)UMMY BIT8 I’~ 1818 I READ BITS COLUMN BY-ooI-UMNI-~ 1618 FIG.16 APLNDC-WH-A 0000017640 U.S. Patent Apr. 3, 2007 Sheet 25 of 27 US 7,200,792 B2 APLNDC-WH-A 0000017641 U.S. Patent Apr. 3, 2007 US 7,200,792 B2 Sheet 26 of 27 !610 BYSTEMATIC BITS 160AM DEMODULATOR WRITE AREA READ AREA) I FIG.18 APLNDC-WH-A 0000017642 U.S. Patent Apr. 3, 2007 Sheet 27 of 27 US 7,200,792 B2 START RECEIVE DATA BITS 1900 DETERMINE C2, R2 AND X l g02 INITIALIZE L R2xC2 BUFFEFI 1904 SEQUENTIALLY WRITE DATA BITS IN EACH BUFFER 1906 1000 ~INSERT, DUMMY BIT~I---. I~I0 READ BITS 1016 {s & p) II FIG.19 APLNDC-WH-A 0000017643 US 7,200,792 B2 1 2 INTERLEAVING APPARATUS AND METHOD FOR SYMBOL MAPPING IN AN HSDPA MOBILE COMMUNICATION SYSTEM modulating one symbol by a transmitter, a symbol representing two bits in a macro region like the left/right quadrants or upper/lower quadrants on the X/Y-axis has "high reliability," and a symbol representing two bits in a micro region has "low reliability." PRIORITY FIG. 1 schematically illustrates a structure of a transmitter This application claims priority to an application entitled in an HSDPA (High Speed Downlink Packet Access) mobile communication system. As illustrated, the transmitter "Interleaving Apparatus and Method for Symbol Mapping in an HSDPA Mobile Communication System" filed in the includes a channel encoder, an interleaver and a modulator. Korean Industrial Property ONce on Dec. 21, 2001 and 10 Referring to FIG. 1, input information bits to which CRC assigned Ser. No. 2001-83064, the contents of which are (Cyclic Redundancy Check) bits, or error detection data, are incorporated herein by reference. added in a CRC generator 110, are provided to a channel encoder 120, and the channel encoder 120 encodes the CRC BACKGROUND OF THE INVENTION bit-added input information bits through a predetermined 15 coding process, and outputs coded bits, i.e., systematic bits 1. Field of the Invention S and parity bits R The channel encoder 120 has at least one The present invention relates generally to a data transcode rate in order to encode the information bits. The code mission!reception apparatus and method in a CDMA (Code rate may become 1A or 3/4. In addition, when the channel Division Multiple Access) mobile communication system, encoder 120 supports a plurality of code rates through and in particular, to a data transmission/reception apparatus 20 symbol puncturing or symbol repetition based on a rate R 1~ and method for improving reliability of transmission data or 1A mode code, an operation of selecting a particular code bits. rate from the supportable code rates is required. In FIG. 1, 2. Description of the Related Art for example, the channel encoder 120 determines a code rate In reality, in a conmaunication system, it is impossible to under the control of a controller 160. The coded bits are receive a transmitted signal without any distortion or noise. 25 subject to rate matching in a rate matcher 130. Commonly, Particularly, a mobile communication system that transmits the rate matching is performed through repetition and/or and receives signals through a wireless network is more puncturing on the coded bits, when a transport channel is susceptible to the distortion or noise, compared with a subject to multiplexing or the output symbols of the channel communication system that transmits and receives signals encoder 120 are not identical in number to the symbols through a wired network. 30 transmitted over the air. The puncturing or repetition funcTherefore, various techniques for minimizing the inflution of the rate matcher 130 is identical to the puncturing or ence of the distortion or noise have been proposed, and an repetition function performed to adjust a code rate of the error control coding technique is one of the typical proposed channel encoder 120, the functions can be united. That is, the techniques. Codes used for the error control coding techchannel encoder 120 and the rate matcher 130 can be nique are classified into memoryless codes and memory 35 integrated into one block, but they are separately illustrated codes. The memoryless codes include linear block codes, in FIG. 1, for the sake of convenience. The coded bits and the memory codes include convolutional codes and rate-matched by the rate matcher 130 are subject to interturbo codes. A device for creating such codes is called a leaving in an interleaver 140. The interleaving operation is "channel encoder," and its outputs can be divided into perfomaed to minimize a data loss even though data is lost systematic bits and parity bits according to the error control 4o during transmission. The interleaved coded bits are subject coding technique in use. The turbo codes are typically used to symbol mapping in a modulator 150 according to a for the error control coding technique for separately outputmodulation technique of QPSK (Quadrature Phase Shift ting the systematic bits and the parity bits. Of course, in Keying), 8PSK (8-ary Phase Shift Keying), 16QAM (16-ary addition to the turbo codes, systematic convolutional codes, Quadrature Amplitude Modulation) or 64QAM. The cona kind of the convolutional codes, are used to separately 45 troller 160 controls a coding operation of the channel output the systematic bits and the parity bits. Here, the encoder 120 and a modulation technique of the modulator systematic bits mean actual signals to be transmitted, and the 150 according to a current state of a radio channel. In the parity bits are signals added to correct a possible transmisHSDPA mobile communication system, AMCS (Adaptive sion error of the systematic bits during decoding. However, Modulation and Coding Scheme) is used for the controller even in the case of the error control-coded signals, ifa burst 5o 160 in order to adaptively select one of the modulation error occurs in the systematic bits or parity bits, it is not easy techniques QPSK, 8PSK, 16QAM and 64QAM according to to correct the burst error. Such a phenomenon frequently the radio environment. occurs when a signal passes through a fading channel, and Though not illustrated in the drawing, a CDMA mobile an interleaving technique is typically used to prevent this communication system spreads transmission data with a phenomenon. 55 Walsh code W and a PN (Pseudo Noise) orthogonal code The interleaving technique is used to more efficiently (PN) so that a corresponding UE (User Equipment), or a overcome the burst error by dispersing a defective part into mobile terminal, can identify a channel over which the data several positions instead of concentrating the defective part is transmitted, and a Node B, or a base station, which on a particular position. transmits the data. The interleaved signal undergoes symbol mapping in a 60 In the transmitter structure stated above, as a matter of digital modulator. Here, if an order of the modulator is course, systematic bits and parity bits output from the increased, the number of bits included in one symbol is also channel encoder 120 have different priorities. In other increased. Particularly, in the case of a high-order modulawords, in the case where errors occur in transmission data at tion technique of over 16QAM (16-ary Quadrature Amplia certain rate, the transmission data can be decoded more tude Modulation), one symbol includes 4 or more informa- 65 correctly at a receiver when the errors occur in the parity tion bits, and the information bits can be classified according bits, compared with when the errors occur in the systematic to their reliability. Here, as to the reliability, in a process of bits. The reason is because, as stated above, the systematic APLNDC-WH-A 0000017644 US 7,200,792 B2 3 4 bits are the actual data bits, while the parity bits are the bits muting the columns in the buffer area according to a given rule; dividing the rows in the buffer area into a first read area added to correct the transmission errors during decoding. For this, a symbol mapping (SMP) technique has been and a second read area having the same size; and alternately proposed, and the SMP technique is disclosed in Korean reading as many bits as a number determined based on a patent application No. 2001-17925, filed by the applicant on 5 prescribed modulation technique from the first read area and Apr. 4, 2001 the contents of which are incorporated herein the second read area in such a manner that the bits are by reference. sequentially read in a column direction from a first row to a The SMP technique is a technique for increasing system last row among the rows of each of the first read area and the performance by reducing an error probability of the systemsecond read area. atic bits having higher priority than the parity bits. That is, 10 According to a second aspect of the present invention, the the SMP technique enables the modulator 150 to map the present invention provides a method for interleaving coded systematic bits with higher priority to the bits with higher bits encoded at a prescribed code rate in a transmitter for a reliability among the bits constituting a symbol, and map the mobile communication system including a buffer having an parity bits with lower priority to the bits with lower reli- area comprised of a plurality of rows and columns, for ability, during symbol mapping based on a predetermined 15 writing the coded bits. The method comprises separating the modulation technique. Therefore, in the transmitter of the area of the buffer into a first write area and a second write conventional mobile communication system, it is necessary area according to a ratio of coded bits with higher priority to improve the interleaver 140 which interleaves coded bits among the coded bits to coded bits with lower priority; regardless of their priority. That is, in order to apply the SMP sequentially writing a stream of the coded bits with higher technique, the interleaver 140 must be improved such that it 2o priority in a row direction from a first column to a last can separately interleave the systematic bits and the parity column among the columns in the first write area, and bits. sequentially writing a stream of the coded bits with lower priority in a row direction from a first column to a last SUMMARY OF THE INVENTION column among the columns in the second write area; per25 muting the columns in the buffer area according to a given It is, therefore, an object of the present invention to rule; dividing the rows in the buffer area into a first read area provide a method for reducing complexity and securing and a second read area having the same size; permuting, compatibility with an existing algorithm in realizing an between the first read area and the second read area, as many interleaver for a SMP teclmique. rows as a number determined based on a prescribed moduIt is another object of the present invention to provide a 30 lation technique among the rows of each ofthe first read area data transmission!reception apparatus and method for and the second read area; and sequentially reading the rows improving performance of a mobile communication system in the entire buffer area comprised of the first read area and by realizing an SMP technique for differentially mapping the second read area, in a column direction from a first row reliabilities according to priority. to a last row. It is further another object of the present invention to 35 According to a third aspect of the present invention, the provide a method for efficiently realizing SMP in a mobile present invention provides a method for interleaving coded communication system. bits encoded at a prescribed code rate in a transmitter for a It is yet another object of the present invention to provide mobile communication system including a buffer having an an algorithm for an interleaver in a mobile communication area comprised of a plurality of rows and columns, for system. 4o writing the coded bits. The method comprises separating the It is still another object of the present invention to provide area of the buffer into a first write area and a second write an apparatus for realizing SMP in a mobile communication area according to a ratio of coded bits with higher priority system. among the coded bits to coded bits with lower priority; It is still another object of the present invention to provide sequentially writing a stream of the coded bits with higher an apparatus and method for reducing complexity in real- 45 priority in a row direction from a first column to a last izing SMP. column among the columns in the first write area, and To achieve the above and other objects, the present writing a stream of the coded bits with lower priority in a invention provides a new method for realizing SMP with a row direction from a last column to a first column among the minimized increase in complexity and minor modification of columns in the second write area in such a manner that the the algorithm, compared with an existing interleaving algo- 5o stream of coded bits is written in a reverse direction from a rithm. Further, the present invention proposes a condition to last row to a first row in the second write area; permuting the which the method can be applied. columns in the buffer area according to a given rule; dividing According to a first aspect of the present invention, the the rows in the buffer area into a first read area and a second present invention provides a method for interleaving coded read area having the same size; and alternately reading as bits encoded at a prescribed code rate in a transmitter for a 55 many bits as a number determined based on a prescribed mobile communication system including a buffer having an modulation technique from the first read area and the second area comprised of a plurality of rows and columns, for read area in such a manner that the bits are sequentially read writing the coded bits. The method comprises separating the in a column direction from a first row to a last row among area of the buffer into a first write area and a second write the rows of each of the first read area and the second read area according to a ratio of coded bits with higher priority 60 area. among the coded bits to coded bits with lower priority; According to a fourth aspect of the present invention, the sequentially writing a stream of the coded bits with higher present invention provides a method for interleaving coded priority in a row direction from a first column to a last bits encoded at a prescribed code rate in a transmitter for a column among the columns in the first write area, and mobile communication system including a buffer having an sequentially writing a stream of the coded bits with lower 65 area comprised of a plurality of rows and columns, for priority in a row direction from a first column to a last writing the coded bits. The method comprises separating the column among the columns in the second write area; perarea of the buffer into a first write area and a second write APLNDC-WH-A 0000017645 US 7,200,792 B2 5 6 area according to a ratio of coded bits with higher priority technique from the first read area and the second read area among the coded bits to coded bits with lower priority; in such a manner that the bits are sequentially read in a column direction from a first row to a last row among the sequentially writing a stream of the coded bits with higher priority in a row direction from a first column to a last rows of each of the first read area and the second read area, column among the columns in the first write area, and 5 and multiplexing the read coded bits. writing a stream of the coded bits with lower priority in a According to a seventh aspect of the present invention, the row direction from a last column to a first column among the present invention provides an apparatus for interleaving coded bits encoded at a prescribed code rate in a transmitter columns in the second write area in such a manner that the stream of coded bits is written in a reverse direction from a for a mobile communication system including an encoder last row to a first row in the second write area; permuting the 10 for encoding transmission data into coded bits at the precolumns in the buffer area according to a given rule; dividing scribed code rate, the coded bits including coded bits with the rows in the buffer area into a first read area and a second higher priority and coded bits with lower priority, and a read area having the same size; permuting, between the first buffer having an area comprised of a plurality of rows and read area and the second read area, as many rows as a cohmms, for writing the coded bits. The apparatus c0mnumber determined based on a prescribed modulation tech- 15 prises an interleaver for separating the area of the buffer into nique among the rows of each of the first read area and the a first write area and a second write area according to a ratio second read area; and sequentially reading the rows in the of coded bits with higher priority to coded bits with lower entire buffer area comprised of the first read area and the priority; sequentially writing a stream of the coded bits with higher priority in a row direction from a first column to a last second read area, in a column direction from a first row to a last row. 20 cohmm among the columns in the first write area, and According to a fifth aspect of the present invention, the sequentially writing a stream of the coded bits with lower present invention provides a method for interleaving coded priority in a row direction from a first column to a last bits encoded at a prescribed code rate in a transmitter for a cohmm among the columns in the second write area; permobile communication system including two buffers each muting the columns in the buffer area according to a given having an area comprised of a plurality of rows and col- 25 rule; dividing the rows in the buffer area into a first read area umns, for writing the coded bits. The method comprises and a second read area having the same size; and permuting, writing coded bits with higher priority among the coded bits between the first read area and the second read area, as many in a first buffer and writing coded bits with lower priority in rows as a number determined based on a prescribed modua second buffer, in such a manner that a stream of the coded lation technique among the rows of each of the first read area bits with higher priority is sequentially written in a row 3o and the second read area. direction from a first column to a last column among the According to an eighth aspect of the present invention, the columns in the write area of the first buffer and a stream of present invention provides an apparatus for interleaving the coded with lower priority is sequentially written in a row coded bits encoded at a prescribed code rate in a transmitter direction from a first column to a last column among the for a mobile communication system including an encoder columlls in the write area of the second buffer; permuting the 35 for encoding transmission data into coded bits at the prescribed code rate, the coded bits including coded bits with columns of the write areas in the first buffer and the second buffer according to a given rule; and alternately reading as higher priority and coded bits with lower priority, and a many bits as a number determined based on a prescribed buffer having an area comprised of a plurality of rows and columns, for writing the coded bits. The apparatus cornmodulation technique from the write area of the first buffer and the write area of the second buffer in such a manner that 40 prises an interleaver for separating the area of the buffer into the bits are sequentially read in a column direction from a a first write area and a second write area according to a ratio first row to a last row among the rows of the write areas in of the coded bits with higher priority to the coded bits with each of the first buffer and the second buffer. lower priority, sequentially writing a stream of the coded bits According to a sixth aspect of the present invention, the with higher priority in a row direction from a first column to present invention provides an apparatus for interleaving 45 a last column among the columns in the first write area, and coded bits encoded at a prescribed code rate in a transmitter writing a stream of the coded bits with lower priority in a for a mobile communication system including an encoder row direction from a last column to a first column among the for encoding transmission data into coded bits at the precolumns in the second write area in such a manner that the scribed code rate, the coded bits including coded bits with stream of coded bits is written in a reverse direction from a higher priority and coded bits with lower priority, and a 5o last row to a first row in the second write area, and permuting buffer having an area comprised of a plurality of rows and the columns in the buffer area according to a given rule. columns, for writing the coded bits. The apparatus comFurther, the apparatus comprises a multiplexer for dividing prises an interleaver for separating the area of the buffer the rows in the buffer area into a first read area and a second included therein into a first write area and a second write read area having the same size, alternately reading as many area according to a ratio of the coded bits with higher 55 bits as a number determined based on a prescribed modupriority to the coded bits with lower priority, sequentially lation technique from the first write area and the second writing a stream of the coded bits with higher priority in a write area, and sequentially reading coded bits in a column row direction from a first column to a last column among the direction from a first row to a last row among the rows in the columns in the first write area, and sequentially writing a first read area and the second read area, and multiplexing the stream of the coded bits with lower priority in a row 6o read coded bits. direction from a first column to a last column among the According to a ninth aspect of the present invention, the columns in the second write area, and permuting the colpresent invention provides an apparatus for interleaving unms in the buffer area according to a given rule. Further, the coded bits encoded at a prescribed code rate in a transmitter apparatus comprises a multiplexer for dividing the rows in for a mobile communication system including an encoder the buffer area into a first read area and a second read area 65 for encoding transmission data into coded bits at the prehaving the same size, and alternately reading as many bits as scribed code rate, the coded bits including coded bits with a number determined based on a prescribed modulation higher priority and coded bits with lower priority, and a APLNDC-WH-A 0000017646 US 7,200,792 B2 7 8 buffer having an area comprised of a plurality of rows and including a buffer having an area comprised of rows and cohunns, for writing the coded bits. The apparatus comcolumns, for writing the coded bits. The apparatus comprises an interleaver for separating the area of the buffer into prises a deinterleaver for separating a use area of the buffer a first write area and a second write area according to a ratio into a first write area and a second write area having the of coded bits with higher priority to coded bits with lower same size; sequentially writing one demultiplexed output priority; sequentially writing a stream of the coded bits with into the first write area and sequentially writing another higher priority in a row direction from a first column to a last demultiplexed output into the second write area; dividing the column among the columns in the first write area, and use area into a first read area and a second read area writing a stream of the coded bits with lower priority in a according to a ratio of coded bits with higher priority among row direction from a last column to a first column among the 10 the coded bits to coded bits with lower priority; and reading columns in the second write area in such a manner that the coded bits from the first read area and the second read area stream of coded bits is written in a reverse direction from a according to the ratio of the coded bits with higher priority last row to a first row in the second write area; permuting the to the coded bits with lower priority, and deinterleaving the columns in the buffer area according to a given rule; dividing read coded bits. the rows in the buffer area into a first read area and a second 15 BRIEF DESCRIPTION OF THE DRAWINGS read area having the same size; and permuting, between the first read area and the second read area, as many rows as a The above and other objects, features and advantages of number determined based on a prescribed modulation technique among the rows of each of the first read area and the the present invention will become more apparent from the 2o following detailed description when taken in conjunction second read area. with the accompanying dxawings in which: According to a tenth aspect of the present invention, the present invention provides an apparatus for interleaving FIG. 1 is a block diagram illustrating a structure of a high-speed packet transmission system according to the coded bits encoded at a prescribed code rate in a transmitter for a mobile commnnication system including an encoder prior art; FIG. 2 is a block diagram illustrating a structure of a for encoding transmission data into coded bits at the pre- 25 high-speed packet transmission system supporting SMP for scribed code rate, the coded bits including coded bits with differentially mapping reliabilities according to priority, higher priority and coded bits with lower priority, and according to an embodiment of the present invention; buffers each having an area comprised of a plurality of rows FIG. 3 is a block diagram illustrating a process of mapand columns, for writing the coded bits. The apparatus comprises an interleaver including a first buffer for sequen- 30 ping systematic bits and parity bits, applied in the same ratio to two physically separated interleaving buffers having a tially writing a stream of the coded bits with higher priority sufficient size, to a 16QAM or 64QAM-modulated symbol in a row direction from a first column to a last column among in the case where a code rate is 1/2, according to an the columns in the write area thereof, and a second buffer for embodiment of the present invention; sequentially writing a stream of the coded bits with lower priority in a row direction from a first colun~a to a last 35 FIG. 4 is a block diagram illustrating a process of mapping systematic bits and parity bits, applied in a different column among the columns in the write area thereof, the ratio to two physically separated interleaving buffers having interleaver permuting the columns of the write areas in the a sufficient size, to a 16QAM or 64QAM-modulated symbol first buffer and the second buffer according to a given rule; in the case where a code rate is 3/4, according to an and a multiplexer for alternately reading as many bits as a number determined based on a prescribed modulation tech- 4o embodiment of the present invention; FIG. 5 is a block diagram illustrating a process of mapnique from the write area of the first buffer and the write area ping systematic bits and parity bits, applied in a different of the second buffer in such a manner that the bits are ratio to two physically separated interleaving buffers having sequentially read in a column direction from a first row to a a minimum size, to a 16QAM or 64QAM-modulated symbol last row among the rows of the write areas in each of the first buffer and the second buffer, and multiplexing the read 45 in the case where a code rate is 3/4, according to an embodiment of the present invention; coded bits. FIG. 6 is a flowchart illustrating a process of applying an According to a eleventh aspect of the present invention, SMP technique by physically separating an interleaver the present invention provides a method for deinterleaving according to an embodiment of the present invention; coded bits demodulated by a prescribed demodulation techFIG. 7 is a block diagram illustrating a structure of a nique in a receiver for a mobile communication system 5o including a buffer having an area comprised of rows and transmitter according to a first embodiment of the present invention; columns, for writing the coded bits. The method comprises FIGS. 8A and 8B illustrate examples of a writing process demultiplexing the coded bits at prescribed periods; sepafor a code rate 1/2 according to a first embodiment of the rating a use area of the buffer into a first write area and a second write area having the same size; sequentially writing 55 present invention; FIGS. 9A and 9B illustrate examples of a writing process one demultiplexed output into the first write area and sequentially writing another demultiplexed output into the for a code rate 3¼ according to the first embodiment of the second write area; dividing the use area into a first read area present invention; FIGS. 10A to 10D illustrate examples of a writing process and a second read area according to a ratio of coded bits with higher priority among the coded bits to coded bits with lower 6o lbr a code rate 3/4, using dummy bits, according to the first embodiment of the present invention; priority; and reading coded bits from the first read area and FIGS. llA and llB illustrate examples of a process of the second read area according to the ratio of the coded bits reading coded bits according to the first embodiment of the with higher priority to the coded bits with lower priority. present invention; According to a twelfth aspect of the present invention, the present invention provides an apparatus for deinterleaving 65 FIG. 12 is a flowchart illustrating a process of applying an coded bits demodulated by a prescribed demodulation techSMP technique by logically separating an interleaver nique in a receiver for a mobile communication system according to the first embodiment of the present invention; APLNDC-WH-A 0000017647 US 7,200,792 B2 9 10 FIG. 13 is a block diagram illustrating a structure of a priority among the coded bits to the first interleaver 250, and transmitter according to a second embodiment of the present the bits with lower priority to the second interleaver 260. In invention; addition, if a code rate for encoding is asymmetric, the FIGS. 14A and 14B illustrate examples of a writing distributor 240 can uniformly distribute the coded bits to the process according to the second embodiment of the present 5 first interleaver 250 and the second interleaver 260 according to priority of the coded bits and the code rate. Meaninvention; FIGS. 15A and 15B illustrate examples of a read process while, the first interleaver 250 and the second interleaver according to the second embodiment of the present inven260 separately interleave the coded bits distributed from the distributor 240, and provide the interleaved coded bits in tion; FIG. 16 is a flowchart illustrating a process of applying an 10 parallel to the P/S converter 270. The P/S converter 270 SMP technique by logically separating an interleaver converts the interleaved coded bits provided in parallel into according to the second embodiment of the present invenserial data in the form of a proper bit stream according to a tion; code rate and a modulation technique. To this end, the P/S FIG. 17 is a block diagram illustrating a structure of a converter 270 should be able to select the two inputs in receiver corresponding to the transmitter according to the 15 series for a variable period according to the code rate and the first embodiment of the present invention; modulation technique under the control of a controller. FIG. 18 is a block diagram illustrating a structure of a Meanwhile, examples of applying the SMP technique receiver corresponding to the transmitter according to the using the two physically-separated interleavers are illussecond embodiment of the present invention; and trated in FIGS. 3 to 5. FIG. 19 is a flowchart illustrating an operation of the 20 Referring to FIG. 3, in the case where a code rate is 1/2, receiver according to an embodiment of the present invenand the systematic (S) bits and the parity (P) bits are tion. properly distributed to the two interleavers 250 and 260, the systematic bits and the parity bits can be mapped to H DETAILED DESCRIPTION OF THE positions with higher reliability and L positions with lower PREFERRED EMBODIMENT 25 reliability of each symbol by a modulator 280, respectively. Here, the distributor 240 is optional, and the P/S converter A preferred embodiment of the present invention will be 270 simply serves as a multiplexer (MUX). described herein below with reference to the accompanying Referring to FIG. 4, in the case where a code rate is 3/4, drawings. In the following description, well-hlown funcand the two interleavers 250 and 260 sufficiently receive the tions or constructions are not described in detail since they 30 systematic bits and the parity bits, an output pattern of the would obscure the invention in unnecessary detail. modulator 280 can become optimal as described in conjuncThe present invention provides examples for an intertion with FIG. 3. Likewise, the distributor 240 in FIG. 4 is leaver required for applying the SMP technique. Commonly, also optional. As illustrated in FIG. 4, since two patterns are in a mobile communication system, an amount of (or the required for 64QAM, the P/S converter 270 must control its number of) systematic bits and the number of parity bits, 35 operation according to a modulation order. For example, the mapped to each symbol, are different according to a code P/S converter 270 outputs 1 parity bit per 5 systematic bits rate and a modulation technique. Therefore, in order to for an initial symbol, and outputs 2 parity bits for 4 sysadjust the number of systematic bits and parity bits, an input tematic bits for the next symbol. For an operation proper to of a modulator must be formed in a proper pattern according the modulation technique and the code rate, the P/S conto the above condition. That is, an interleaver for applying 40 verter 270 plays an important role. the SMP technique must be improved such that it can Referring to FIG. 5, in the case where a size of a first separately interleave the systematic bits and the parity bits. buffer 250 is smaller than the total number of systematic There are several methods for realizing such an interleaver bits, a second buffer 2611 must accept the excessive number arranged in front of the modulator according to a given of systematic bits. As illustrated, in the case of 16QAM, condition. 45 there is no output pattern which violates a general idea of The method for improving an intefleaver can be divided SMP. However, in the case of 64QAM, some patterns are into one method for separating the interleaver physically and formed such that the systematic bits can be mapped to the bit another method for separating the interleaver logically. The positions having higher reliability than the parity bits. The physical separation method separates the interleaver into an reason is because after the input bits of the second buffer 2611 interleaver for interleaving coded bits with higher priority 50 are randomly interleaved, the P/S converter 2711 cannot and an interleaver for interleaving coded bits with lower distinguish the systematic bits and the parity bits stored in priority. The logical separation method separates a storage the second buffer 260. area of a buffer included in one interleaver into an area for As can be understood from FIGS. 3 to 5, if the size of the storing coded bits with higher priority and an area for storing buffer (buffer size={the number of systematic bits}+{the coded bits with lower priority. 55 number of parity bits}) is minimized, a symbol pattern for 1. Physical Separation Method the 64QAM cannot be optimally mapped. In other words, in FIG. 2 illustrates a structure of a high-speed packet the case where the interleaving buffer is physically sepatransmission system to which the SMP technique is applied rated, if a high-order modulation technique of 64QAM is using two physically-separated interleavers. The structure of applied, it is necessary to sufficiently increase the sizes of the FIG. 2 includes two physically-separated interleavers, and 6o two buffers for all code rates, in order to create optimal the systematic bits S and the parity bits P are separately mapping patterns. However, in the case of the modulation interleaved by the different interleavers. To this end, an technique with a modulation order of below 16QAM, the interleaving block includes a distributor 240, two interleavoptimal mapping patterns can be generated even though the ers 250 and 260, and a parallel-to-serial (P/S) converter 270. size of the buffer is minimized. Referring to FIG. 2, the distributor 240 properly distrib- 65 Herein, the present invention provides a method for utes input coded bits to the two interleavers 250 and 260. For minimizing a size of the buffer to minimize hardware example, the distributor 240 distributes the bits with higher complexity as described in conjunction with FIG. 5, in the APLNDC-WH-A 0000017648 US 7,200,792 B2 11 12 case where the modulation technique with a modulation nique, only systematic bits or parity bits can be transmitted order of below 16QAM is used. In addition, the present during retransmission when occasion demands. invention provides a method for modifying the existing Meanwhile, in the case where the two interleavers are 3GPP Re199 interleaving algorithm. physically separated, in order to convert outputs from each FIG. 6 is a flowchart illustrating a method for applying an 5 of the two separated interleavers into one bit stream, a SMP technique using physically-separated interleavers serial-to-parallel (S/P) converter controlled by a control according to an embodiment of the present invention. With signal from an external device is necessarily required. reference to FIG. 6, a method for applying the SMP tech2. First Embodiment of Logical Separation Method nique using physically-separated interleavers will be Now, a first embodiment for realizing the SMP technique described. 10 by logically separating a buffer included in one interleaver Referring to FIG. 6, a block interleaver with an interwill be described. column permutation (or column permutation) function is 2.1 Structure of Transmitter According to First Embodiment used for interleaving. The interleaver receives up,l, up,2, FIG. 7 illustrates a structure of a transmitter for realizing u~,3, . .., u~,~ (Step 612). Here, p represents the number of physical channels, and U represents the number of bits per 15 the SMP technique by logically separating a buffer included frame of a physical channel. in one interleaver according to the first embodiment of the (1) First, the total number of columns C2 is set to 30 (Step present invention. 614). The columns are assigned column numbers 0, 1, Referring to FIG. 7, an interleaver 710 includes a buffer 2, ... , C2-1 from left to right. having a prescribed area therein. The prescribed area of the (2) The minimum integer indicating a row of a matrix R2, 2o buffer means a partial area determined by the total number satisfying a condition of U_-<R2xC2, is determined. The of coded bits received from an encoder (not shown). Hererows of the matrix are assigned row numbers 0, 1, 2,..., inafter, the prescribed area determined by the total number R2-1 from top to bottom (Step 616). of coded bits will be referred to as "use area" (or an area in (3) The inputs Up,l, Up,2, Up,3 ..... Up,U are written row use). The interleaver 710 divides the determined use area by row in an R2xC2 rectangular matrix beginning at posi- 25 into two virtual write areas of a first write area and a second tion yp,1 in a 0t~’ row and a 0t~’ column (Step 618), in write area according to a ratio of the bits with first priority accordance with Equation (1). (hereinafter, referred to as "systematic bits") to the bits with Equation (1) [ Yp,((R2 1)×C2+1) ~Vp,((R2 1)×C2+2) Yp,((R2 1)×C2+3) "" Yp,(R2×C2) second priority (hereinafter, referred to as "parity bits"), Here, Yp,~ Up,~ for k 1, 2, . . . , U. If R2xC2>U (Step constituting the coded bits. Here, the ratio of the systematic 620), then dummy bits of Yp,~0 or 1 (for kU+l, U+2,..., R2xC2) are inserted (Step 622). The dummy bits 40 bits to the parity bits is determined depending on a code rate are deleted (Step 626) after being subject to column permuused by the encoder. For example, if the code rate is 1/2, the tation (Step 624). use area is equally divided into two virtual write areas (4) After the column permutation is performed according having the same size, and one of the two areas is defined as the first write area and the other area is defined as the second to a rule (Step 624), the resulting bits Y’p,~ are expressed as Ytp,l Ytp,(R2+l) Ytp,(2×R2+l) [ Ytp, R2 Ytp,(2×R2) Y~p,(3×R2) "’" Ytp((C2 I)×R2+I) "’" Equation (2) Ytp,(C2×R2) (5) Outputs of the block interleaver are read column by 55 write area. FIGS. 8A and 8B illustrate an example of the column from the column-permuted R2xC2 matrix (Step interleaver 71D in which the first write area and the second write area are equal in size. However, if the code rate is 3/4, 628). The outputs are represented by vp,~, Vp,2, Vp,3, . . . , the use area is equally divided into four areas having the same size, and three of the four areas are defined as a first However, in the normal SMP technique, since two interleavers are physically separated, a distributor for properly 6o write area and the remaining one area is defined as a second write area. FIGS. 9A and 9B illustrate an example of the distributing systematic bits and parity bits, the number of interleaver 71D in which the first write area and the second which is variable according the code rate, to the two write area are asymmetric in size. It is assumed in FIG. 7 that interleavers is necessarily required. If the distributor is not the interleaver 71D equally divides the use area into the first provided, each of the interleavers must have a buffer capable of storing the entire input coded bits. The reason is because 65 write area and the second write area, for the code rate 1/2. in a high-speed packet transmission system supporting an Upon receiving coded bits from the encoder, the interHARQ (Hybrid Automatic Retransmission Request) techleaver 71D sequentially writes the systematic bits among the APLNDC-WH-A 0000017649 US 7,200,792 B2 13 14 coded bits in the first write area, and sequentially writes the 2.2 Writing of Coded Bits parity bits in the second write area. Here, the interleaver 710 A method of writing coded bits in the buffer included in the interleaver 710 according to an embodiment of the inserts dummy bits into an area left over after writing the present invention can be divided into one case where systematic bits in the first write area, and inserts the dummy bits into an area left over after writing the parity bits in the 5 dummy bits are used and another case where the dummy bits are not used. The dummy bits are used to fill an area left over second write area. Exemplary methods of writing the sysafter writing coded bits in the use area of the buffer, tematic bits and exemplary methods of writing the parity bits determined depending on the total number of the coded bits are illustrated in FIGS. 8A to 10D. provided form the encoder. The dummy bits are deleted after After completion of writing the systematic bits and the 10 being subject to column permutation for interleaving. parity bits in this manner, the interleaver 710 interleaves the Before a description of the methods for writing the coded coded bits including the dummy bits stored in the use area bits, a method for determining whether to use the dummy through column permutation. The column permutation perbits will be described. mutes the coded bits in the use area column by column, so Whether to use the dummy bits is determined according that the written systematic bits are never mixed with the 15 to whether the total number U of the coded bits received parity bits. from the encoder is a multiple of the total number C2 of columns constituting a buffer matrix for the use area. Here, Further, the interleaver 710 equally divides the use area the C2 can be previously determined according to a size of into a first read area and a second read area in order to read a buffer in the interleaver. Further, the total number R2 of the written coded bits. Therefore, if the code rate is 1½, the first read area is identical to the first write area, and the 2o rows, used to determine the use area, can be determined according to the total number U of the coded bits, as the C2 second read area is identical to the second write area. Thus, is previously determined. Therefore, the use area is deteronly the systematic bits are previously written in the first mined by the product of the C2 and the R2 (C2xR2). In read area, and only the parity bits are previously written in addition, whether to use the dummy bits can be determined the second read area. However, if the code rate is 3¼, the first write area includes the first read area and a part of the second 25 by comparing the product of the C2 and the R2 with the U. For example, if a condition of U C2xR2 is satisfied as the read area, and the remaining part of the second read area U is a multiple of the C2, then the dummy bits are not used. becomes the second write area. Thus, only the systematic However, if a condition of U<C2xR2 is satisfied as the U is bits are previously written in the first read area, and the not a multiple (R2) of the C2, then the dummy bits are used. systematic bits and the parity bits are previously written in 3o 2.2.1 No Dummy Bit Used the second read area row by row. FIGS. 8A, 8B, 9A and 9B illustrate exemplary methods of After interleaving, the interleaver 710 sequentially reads writing coded bits in the interleaver 710 in the case where the coded bits written in the first read area and the second the dummy bits are not used. Specifically, FIGS. 8A and 8B read area. Exemplary methods of reading the coded bits illustrate a case where a code rate used by the encoder is 1½, from the first read area and the second read area are illustrated in FIGS. llA and llB. Herein, the column 35 and FIGS. 9A and 9B illustrate a case where a code rate used by the encoder is 3/4. permutation operation and the reading operation for interFirst, a description will be made of a case where systemleaving have been separately described. However, it would atic bits and parity bits are received in the same ratio, as the be obvious to those skilled in the art that the column code rate of the encoder is 1½. permutation operation and the reading operation can be FIG. 8A illustrates a method of writing the parity bits united into one operation by changing the order of reading. 4o beginning at the end of the use area in the case where the The coded bits read from the first read area and the second code rate is 1/2, and FIG. 8B illustrates a method of writing read area of the interleaver 710, are provided to a multithe parity bits beginning at the head of the second write area plexer (MUX) 720. The MUX 720 multiplexes the coded of the use area in the case where the code rate is 1½. bits from the first read area and the second read area in a 45 Referring to FIG. 8A, the use area, a part of the entire area prescribed ratio, and outputs one bit stream. The ratio for for the buffer included in the interleaver 710, is determined multiplexing the coded bits from the first read area and the depending on the total number U of coded bits received from coded bits li’om the second read area is determined dependthe encoder. The use area is determined in such a matter that ing on the modulation technique used by a modulator 730. if no remainder exists after dividing the U by the predefined For example, if the modulation technique is 16QAM, 4 5o C2, a quotient obtained by the division is defined as the total coded bits are mapped to one symbol. In this case, the MUX number R2 of rows. However, if a remainder exists after the 720 multiplexes the 2 coded bits from the first read area and division, the R2 is determined by adding 1 to the quotient. the 2 coded bits from the second read area, for each symbol. The use area can be defined as the sum of a first write area The coded bits multiplexed by the MUX 720 are applied and a second write area illustrated in FIG. 8A, and the first to the modulator 730. The modulator 730 performs symbol 55 write area and the second write area are determined by mapping on the multiplexed coded bits. For example, when equally dividing the use area into two areas. In the writing using a modulation technique of 16QAM, the modulator 730 method of FIG. 8A, it is not necessary to physically defimaps 2 coded bits read from the first read area to the bits nitely separate the first write area and the second write area. with higher reliability (hereinafter, referred to as "first The reason is because the systematic bits out of the coded reliability") of a particular symbol. Further, the modulator 60 bits are written beginning at the head of the use area 730 maps 2 coded bits read from the second read area to the (represented by black arrows), while the parity bits among bits with lower reliability (hereinafter, referred to as "second the coded bits are written beginning at the end of the use area reliability") of the symbol. (represented by white arrows). In other words, the systemAs stated above, the present invention provides a method atic bits are written in a forward direction beginning at (0,0) for interleaving the systematic bits and the parity bits by 65 of the use area, and the parity bits are written in a reverse logically separating one interleaver, so that the modulator direction beginning at (R2-1,C2-1) of the use area. Here, can perform symbol mapping by the SMP technique. C2 represents the total number of columns constituting a APLNDC-WH-A 0000017650 US 7,200,792 B2 15 16 buffer matrix in the use area, and R2 represents the total sented by black arrows), and the parity bits out of the coded number of rows constituting the buffer matrix in the use bits are written beginning at the head of the second write area. Therefore, when the coded bits are completely written area, i.e., beginning at the (y,z) (represented by white in the use area, the first write area and the second write area arrows). In other words, the systematic bits are written in a can be naturally separated by the coded bits written therein. 5 forward direction beginning at (0,0) of the use area, and the parity bits are written in a forward direction beginning at Referring to FIG. 8B, the use area, a part of the entire area (y,z) of the use area. As stated above, if there exists a for the buffer included in the interleaver 710, is determined depending on the total number U of coded bits received from quotient or a remainder obtained by dividing the total the encoder. The use area can be defined as the sum of a first number of systematic bits by the C2, the y is defined as a write area and a second write area illustrated in FIG. 8B, and 10 value determined by adding 1 to the quotient, and the z the first write area and the second write area are determined becomes the remainder. by equally dividing the use area into two areas. After the first 2.2.2 Dummy Bits Used Although a method of writing the coded bits using the write area and the second write area are determined, the systematic bits out of the coded bits are written beginning at dummy bits will be described with reference to a code rate the head of the first write area (represented by black arrows), 15 3¼, it would be obvious to those skilled in the art that the and the parity bits out of the coded bits are written beginning same method can be applied even to a code rate 1½. at the head of the second write area (represented by white As defined above, the dummy bits are used when there arrows). In other words, the systematic bits are written in a remains an empty area even after the systematic bits and the forward direction beginning at (0,0) of the use area, and the parity bits are completely written in the use area. That is, the parity bits are written in a forward direction beginning at 2o dummy bits are used when the U is not a multiple of the C2. A method of inserting the dummy bits is realized in different (y,z) of the use area. Here, since the code rate is 1½, y R2/2 andz 0. ways according to a position in the use area, where the Next, a description will be made of a case where systemdummy bits are to be inserted. FIGS. 10A to 10D illustrate atic bits and parity bits are received in a ratio of 3:1, as the methods of writing the coded bits according to a position of 25 the dummy bits. The position of the dummy bits can be code rate of the encoder is 3¼. FIG. 9A illustrates a method of writing the parity bits determined depending on a direction in which the parity bits beginning at the end of the use area in the case where the are written in the second write area, and a write starting point code rate is 3¼, and FIG. 9B illustrates a method of writing of the parity bits. the parity bits beginning at the head of the second write area FIG. 10A illustrates a method of writing coded bits in the of the use area in the case where the code rate is 3¼. 3o case where the dummy bits are written in a reverse direction Referring to FIG. 9A, the use area, a part of the entire area and a point shifted from an end of the second write area by for the buffer included in the interleaver 710, is determined the dummy bits is defined as a starting point. FIG. 10B depending on the total number U of coded bits received from illustrates a method of writing coded bits in the case where the encoder. The use area is determined in such a matter that the dummy bits are written in a forward direction and a head a quotient obtained by dividing the U by the predefmed C2 55 of the second write area is defined as a starting point. FIG. is defined as R2. The use area can be defined as the sum of 10C illustrates a method of writing coded bits in the case a first write area and a second write area illustrated in FIG. where the dummy bits are written in a reverse direction and an end the second write area is defined as a starting point. 9A. In the writing method of FIG. 9A, it is not necessary to physically definitely separate the first write area and the FIG. 10D illustrates a method of writing coded bits in the second write area. The reason is because the systematic bits 4o case where the dummy bits are written in a forward direction out of the coded bits are written beginning at the head of the and a point shifted from a head of the second write area by use area (represented by black arrows), while the parity bits the dummy bits is defined as a starting point. out of the coded bits are written beginning at the end of the Referring to FIG. 10A, the use area, a part of the entire use area (represented by white arrows). In other words, the area for the buffer included in the interleaver 710, is detersystematic bits are written in a forward direction beginning 45 mined depending on the total number U of coded bits at (0,0) of the use area, and the parity bits are written in a received from the encoder. The use area can be defined as the reverse direction beginning at (R2-1 ,C2-1) of the use area. sum of a first write area and a second write area illustrated The systematic bits and the parity bits written in the use area in FIG. 10A. In the writing method of FIG. 10A where the are separated by a boundary point (y,z) between the first dummy bits are located at the end of the second write area, write area and the second write area. The (y,z), a boundary 5o it is not necessary to physically definitely separate the first point between the first write area and the second write area, write area and the second write area. The reason is because is a coordinate designating a particular point in the use area. the systematic bits out of the coded bits are written beginIf there exists a quotient or a remainder obtained by dividing ning at the head of the use area (represented by black the total number of systematic bits by the C2, the is defined arrows), while the parity bits out of the coded bits are written as a value determined by adding 1 to the quotient, and the 55 beginning at the end of the use area (represented by white arrows). In other words, the systematic bits are written in a z becomes he remainder. Therefore, the first write area can be defined as an area from the (0,0) to the (y,z) of the use forward direction beginning at (0,0) of the use area, and the parity bits are written in a reverse direction beginning at area, and the second write area can be defined as an area from the (y,z) to the (R2-1,C2-1) of the use area. (R2-1,x) of the use area. The x can be calculated by Referring to FIG. 9B, the use area, a part of the entire area 6o subtracting the number of the dummy bits from a column for the buffer included in the interleaver 710, is determined number corresponding to the C2-1. Therefore, as stated depending on the total number U of coded bits received from above, the systematic bits and the parity bits written in the the encoder. The use area can be defined as the sum of a first use area are separated by a boundary point (y,z) between the write area and a second write area illustrated in FIG. 9B. first write area and the second write area. After the first write area and the second write area are 65 Referring to FIG. 10B, the systematic bits are written in determined, the systematic bits out of the coded bits are the same way as described in the above methods. However, written beginning at the head of the first write area (reprethe parity bits are written in a forward direction beginning at APLNDC-WH-A 0000017651 US 7,200,792 B2 18 17 a boundary (y,z) between the first write area and the second write area. Here, the (y,z) can be newly defined taking into account the dummy bits to be inserted. After the parity bits are completely written, the dummy bits are inserted in a remaining area existing at the end of the second write area. Referring to FIG. 10C, the systematic bits are written in a forward direction beginning at the head of the first write area, and the parity bits are written in a reverse direction beginning at the end of the second write area. Thereafter, the dummy bits are inserted in an area left over after the 10 systematic bits are written and an area left over after the parity bits are written. Referring to FIG. 10D, the systematic bits are written in a forward direction beginning at the head of the first write area, and the parity bits are written in a forward direction 15 beginning at an end of an area between a point where writing of the systematic bits is expected to be completed and a point where the dummy bits are to be inserted. Therefore, the dummy bits are inserted in a part of the first write area and a part of the second write area. bits and the number of parity bits, respectively. The sum of the Us and Up is equal to the number of bits per frame of one physical channel. (1) First, the total number of columns C2 is set to 30. The coltunns are assigned column numbers 0, 1, 2, . . . , C2-1 from left to right. The minimum integer indicating a row of a matrix R2, satisfying a condition of U Us+Up_-< R2xC2, is determined (Step 1202). The rows of the matrix are assigned row numbers 0, 1, 2, . . ., R2-1 from top to bottom (Step 1204). (2) The inputs up,l, up,2, Up,3, . . . , Up,Us are written in a forward direction row by row in an R2xC2 rectangular matrix beginning at yp,1 in a 0a’ row and a 0a’ column, and the inputs Up,us+~, Up,us+2, Up,us+3, . . . , Up,us+up are written in a reverse direction row by row beginning at a point in an (R2-1)t~’ row and a (x-l)t~’ column (Step 1206). Here, x means a remainder obtained by dividing the U by the C2, and is larger than or equal to 1 and smaller than C2 (1 _-<x<C2). Equation (3) shows an exanlple of the matrix generated in this manner. Equation (3) Yp,(C2+I) Yp,(C2+2) .Yp,((R2 1)×C2+1) Yp,((R~I)×C2+2) Yp,(C2+3) ... Yp,(2×C2) Yp,((R2 1)×C2+3) ... Yp,(R2×C2) 30 2.3 Reading of Coded Bits Here, yp,~p,~: for ~1,2, . . . , U. If R2xC2>U (Step The use area of a buffer in the interleaver 710, in which 1208), then dummy bits of Yp,~: 0 or 1 (for k U+I, the coded bits are written, is separated into two virtual read U+2,..., R2xC2) are inserted (Step 1210). The dummy bits areas for reading. The two read areas can be separated by are deleted (Step 1214) after being subject to column equally dividing the use area into two areas with the same 35 permutation (Step 1212). size. The interleaver 710 reads the coded bits written in the (3) After the column permutation is performed according separated first read area and second read area. to a rule (Step 1212), the resulting bits are divided into an FIGS. llA and llB illustrate exemplary methods of H part with higher reliability and an L part with lower reading coded bits from the first read area and the second reliability, and expressed with yp,~ and yp,~:z, as follows. read area by the interleaver 710. Specifically, FIG. llA 40 illustrates a method of reading the coded bits written at a H H H code rate 1½, and FIG. liB illustrates a method of reading the y pH1~ Yp,(R2/2+I) Yp,R2+I "’" Yp,((C2 1)×R2/2+1) Equation (4) coded bits written at a code rate 3¼. H H H H Yp,2 Yp,(R2/2+2) Yp,R2+2 "’" Yp,((C2 1)×R2/2+2) Referring to FIGS. llA and liB, the interleaver 710 sequentially reads coded bits written in the first read area 45 yHR2 yH yH column by column. In addition, the interleaver 710 sequenyHp, l~2/2 p, p,3×R2/2 ... p,(C2×R2/2) L L L L tially reads coded bits written in the second read area as well, Yp, l Yp,(R2/2+I) Yp,R2+I "’" Yp,((C2 1)×R2/2+1) column by column. As a result, in the case of FIG. llA, only L L L L Yp,2 Yp,(R2/2+2) Yp,R2+2 "’" Yp,((C2 1)×R2/2+2) the systematic bits are read from the first read area and only the parity bits are read from the second read area. However, 50 L L L L in the case of FIG. liB, only the systematic bits are read Yp, R2/2 Yp, R2 Yp,3×R2/2 "’" Yp,(C2×R2/2) from the first read area, and the systematic bits and the parity bits are read from second read area. (4) Outputs of the block interleaver are read by two bits 2.4 Operation of Transmitter According to First Embodicoltunn by column by equally dividing the column-perment 55 muted R2xC2 matrix into a part with higher reliability and FIG. 12 is a flowchart illustrating an interleaving process a part with lower reliability (Step 1216). The outputs are according to the first embodiment of the present invention. represented by vp,1, vp,2, Vp,3, . . . , Vp,us. That is, FIG. 12 illustrates a modified interleaving algorithm 3. Second Embodiment of Logical Separation Method for separately writing and reading systematic bits and parity bits. It will be assumed herein that the writing operation is 60 FIG. 13 illustrates a structure of a transmitter lbr realizing performed in the manner described in conjunction with FIG. the SMP technique by logically separating a buffer included 10A, for convenience. in one interleaver according to a second embodiment of the present invention. Referring to FIG. 12, the interleaver receives U coded bits from an encoder (Step 1200). The coded bits are represented Referring to FIG. 13, an interleaver 1310 includes a buffer by up,~, up,~, up,3 ..... Up,us, and Up,us+~, Up,us+~, 65 having a prescribed area therein. The prescribed area of the buffer defines a use area determined by the total number of Up,us+3,..., Up,us+up. Here, p represents a physical channel number, and Us and Up represent the number of systematic coded bits received from an encoder (not shown). The APLNDC-WH-A 0000017652 US 7,200,792 B2 19 2O interleaver 1310 divides the use area into a first write area Re199 reading algorithm. That is, the MUX can be and a second write area according to a ratio of systematic excluded, if the algorithm is changed such that the coded bits bits to parity bits, constituting the coded bits. Here, the ratio written in the two write areas should be read by two bits. In of the systematic bits to the parity bits is determined other words, in the case of logically separated interleaving depending on a code rate used by the encoder. It is assumed 5 buffers, it is possible to exclude a hardware device for the MUX by simply modifying the reading algorithm in the in FIG. 13 that the interleaver 1310 is designed to support a above-stated manner. A novel algorithm which will be code rate 1½. Upon receiving coded bits from the encoder, the interdescribed herein below includes modification of the reading leaver 1310 sequentially writes the systematic bits among algorithm. In addition, in the case where R2 of a buffer the coded bits in the first write area, and sequentially writes 10 matrix is a multiple of 4, it is possible to realize the existing the parity bits in the second write area. Here, the interleaver reading algorithm for reading the entire buffer in the inter1310 inserts dummy bits into an area left over after writing leaver, through row permutation in stead of using the MUX. the systematic bits in the first write area, and inserts the FIGS. 15A and 15B illustrate symbol patterns of a modudummy bits into an area left over after writing the parity bits lator based on the row permutation, for the code rates 1½ and in the second write area. 15 3¼, respectively. Referring to FIGS. 15A and 15B, both After completion of writing the systematic bits and the patterns do not violate an idea of the SMP technique that parity bits in this manner, the interleaver 1310 interleaves differentially maps reliabilities according to priority. When the coded bits including the dummy bits stored in the use an extended amount of actual data is applied, it is possible to obtain the same result as the result obtained by the first area through column permutation. The column permutation permutes the coded bits in the use area column by column, 20 embodiment. so that the written systematic bits are never mixed with the FIG. 16 is a flowchart illustrating an interleaving process written parity bits. After the column permutation, the interaccording to the second embodiment of the present invenleaver 1310 permutes lower half columns among rows tion. Referring to FIG. 16, a block interleaver with a column constituting the first write area with upper half columns permutation function is used for interleaving. The interamong rows constituting the second write area. As a result, 25 leaver receives up,l, up,2, up,3,..., up,~s, and up,~s+l, Up,us+2, the coded bits written in the first write area and the second up,~+3, . . . , up .... up (Step 1600). Here, p represents a write area can be properly read in the form of a bit stream physical channel number, and Us and Up represent the according to the SMP technique. Examples of the inter-row number of systematic bits and the number of parity bits, permutation (or row permutation) are illustrated in FIGS. respectively. The sum of the Us and Up is equal to the 14A and 14B. Specifically, FIG. 14A illustrates row permu- 30 number of bits per frame of one physical channel. tation for a code rate 1½, and FIG. 14B illustrates row (1) First, the total nunlber of columns C2 is set to 30. The cohmms are assigned column numbers 0, 1, 2, . . . , C2-1 permutation for a code rate 3¼. Thereafter, the interleaver 1310 sequentially reads the from left to right. The minimum integer indicating a row of written coded bits. Exemplary methods of reading the coded a matrix R2, satisfying a condition of U Us+Up_-< R2xC2, is bits by the interleaver 1310 are illustrated in FIGS. 15A and 35 determined (Step 1602). The rows of the matrix are assigned 15B. Specifically, FIG. 15A illustrates a method for reading row numbers 0, 1, 2, ..., R2-1 from top to bottom (Step the coded bits in the case where the code rate 1½ is used, and 1604). FIG. 15B illustrates a method for reading the coded bits in (2) The inputs up,~, up,2, up,z, . . . , up,v~ are written in a forward direction row by row in an R2xC2 rectangular the case where the code rate 3¼ is used. Herein, the column permutation operation and the reading 4o matrix beginning at yp,~ in a 0t~’ row and a 0t~’ column, and operation for interleaving have been separately described. the inputs up,~+~, up,~+~, up,~s+3, . . . , Up,~+~p are written However, it would be obvious to those skilled in the art that in a reverse direction row by row beginning at a point in an the column permutation operation and the reading operation (R2-1)~’ row and a (x-l)~’ column (Step 1606). Here, x can be united into one operation by changing the order of means a remainder obtained by dividing the U by the C2, reading. 45 and is larger than or equal to 1 and smaller than C2 As stated above, the coded bits read by the interleaver (1 _-<x<C2). Equation (5) shows an example of the matrix 1310 have a format required for applying the SMP techgenerated in this manner. Equation (5) Yp,(C2+l) Yp,(C2+2) Yp,(C2+3) ... Yp,(2~C2) ~p,((R2 1)×C2+1) Yp,((R~I)×C2+2) Yp,((R2 1)×~2+3) "’" Yp,(R2×C2) nique. Therefore, the coded bits output from the interleaver Here, yp,~,~p,~, for ~1, 2 ..... U. If R2xC2>U (Step 1310 are provided to a modulator 1320, where they are 6o 1608), then dummy bits of yp,~0 or 1 (for k U+I, U+2, . . . , R2xC2) are inserted (Step 1610). subject to symbol mapping by the SMP technique. As described above, the present invention interleaves systematic bits and parity bits by logically separating one (3) After the column permutation is performed according interleaver so that a modulator can perform symbol mapping 65 to a rule (Step 1612), the resulting bits are divided into an by the SMPtechnique. Further, in order to exclude the MUX H part with higher reliability and an L part with lower used in the first embodiment, it is necessary to modify a reliability, and expressed with yp,~ and yp,~z, as follows. APLNDC-WH-A 0000017653 US 7,200,792 B2 21 22 high-speed packet transmission system uses various modulation orders and code rates, each element is controlled by a H Equation (6) controller. Yp,(R2/2+I) Yp,R2+I p,((C2 l,xR2/2+l) 3.1 Structure of Receiver According to First Embodiment Yp,2 Yp,(R2/2+2) Yp,R2+2 "’" p,((C2 1,xR2/2+2) 5 FIG. 17 illustrates a structure of a receiver according to a first embodiment of the present invention. The receiver H H H H Yp, R2/2 Yp,R2 .~p,3xR2/2 "’" Yp,(C2xR2/2) corresponds to the transmitter described in conjunction with L L L yL FIG. 7. Referring to FIG. 17, data bits decoded by a demodulator 10 1710 are demultiplexed by a demultiplexer (DEMUX) 1720. The DEMUX 1720 demultiplexes as many input bits as a L L L L prescribed number according to a modulation technique, and Yp, R2/2 Yp,R2 )’p,3xR2/2 " " " Yp,(C2xR2/2) provides the demultiplexed bits to a first write area and a second write area in a buffer 1730 of the deinterleaver. For (4) Rows with lower reliability are permuted with rows 15 example, if the modulation technique is 16QAM, the DEMUX 1720 provides the input bits by 2 bits to each of the with higher reliability so that rows with higher reliability bits and rows with lower reliability bits should be repeated first and second write areas in the buffer 1730. However, if by lwo rows, as follows (Step 1614). The dummy bits are the modulation technique is 64QAM, the DEMUX 1720 provides the input bits by 3 bits to each of the first and deleted (Step 1616) after being subject to row column permutation (Step 1614). 20 second write areas. If the code rate is 1½, systematic bits and parity bits are separately provided to the first and second write areas. H H H H Equation (7) However, if the code rate is 3/4, only the systematic bits are "’" Yp,((C2 l)xR2/2+l) Yp, l Yp,(R2/2+I) Yp, R2+I provided to the first write area, and the systematic bits and H H H H "’" Yp,((C2 1)×R2/2+2) Yp,2 Yp,(R2/2+2) Yp, R2+2 25 parity bits are provided to the second write area. L L L L "’" Yp,((C2 1)×R2/2+1) Yp, l Yp,(R2/2+l) Yp, R2+l The data bits written in the buffer 1730 of the deinterL L L L leaver are deinterleaved in a reverse operation of the inter"’" Yp,((C2 1)×R2/2+2) Yp,2 Yp,(R2/2+2) Yp, R2+2 leaver, separately generating the systematic bits and the parity bits. H H H H 30 3.2 Structure of Receiver According to Second EmbodiH H H H Yp,R2/2 Yp,R2 Yp,3xR2/2 "’" Yp,(C2xR2/2) ment L L L FIG. 18 illustrates a structure of a receiver according to ypL,3×R2/2 1 the second embodimeut of the preseut invention. The L L L L Yp,R2/2 Yp,R2 Yp,3×R2/2 "’" Yp,(C2×R2/2) receiver corresponds to the transmitter described in conjunc35 tion with FIG. 13. Referring to FIG. 18, data bits decoded by a demodulator (5) Outputs of the block interleaver are read column by 1810 are provided to a first write area and a second write column from the column-permuted, row-permutated R2xC2 area in a buffer 1820 of the deinterleaver, without being matrix (Step 1618). The outputs are represented by vp,1, vp,2, demultiplexed by a demultiplexer. As described in conjunc4o tion with FIG. 13, since the coded bits stored in the buffer 3. Receiver According to Invention 1310 are subject to row permutation in the interleaving Now, a description will be made of a receiver correspondprocess, the transmitter performs multiplexing though a ing to the transmitter that realizes the SMP technique by prescribed reading method, without a multiplexer. Likewise, logically separating a buffer included in one interleaver. The the receiver also can perform deinterleaving without a receiver has a symmetrical structure of the transmitter 45 demultiplexing process, by performing row permutation on illustrated in FIG. 2. A deinterleaver for the receiver is the received bits. illustrated in FIGS. 17 and 18. For example, if the modulation technique is 16QAM, the Since a received signal is in the form of a symbol bits written in the buffer 1820 undergo row permutation by modulated by a modulator in the transmitter, the received two rows between the first write area and the second write signal is first demodulated by a demodulator and then 5o area. However, if the modulation technique is 64QAM, the provided to a deinterleaver. The deiuterleaver has a symbits written in the buffer 1820 undergo row permutation by metrical structure of the interleaver illustrated in FIG. 2. The three rows between the first write area and the second write serial input bits must be converted to parallel bits, so that area. they can be written in upper and lower areas of the interThe data bits written in the buffer 1820 of the deinterleaving buffer. The logically separated buffers perform 55 leaver are deinterleaved in a reverse operation of the interdeinterleaving in a reverse operation of the interleaver, and leaver, separately generating the systematic bits and the a distributor distributes the output bits into systematic bits parity bits. and parity bits. A rate matcher determines positions of the When the interleaver is logically separated, the deinterbits rate-matched by the transmitter and inserts O’s in the leaver has the structures illustrated in FIGS. 17 and 18, determined positions, so that other bits can be applied to a 6o based on a deinterleaving algorithm proposed by the preseut proper input terminal of the demodulator. The demodulator, invention. The deinterleaving algorithm is illustrated in FIG. a device for decoding the bits encoded by an encoder in the 19. transmitter, corrects errors occurring on a channel. The 3.3 Operation of Receiver According to Invention error-corrected output undergoes CRC checking by a CRC FIG. 19 is a flowchart illustrating a deinterleaving process checker in order to determine whether the transmitted signal 65 according to an embodiment of the present invention. The is correctly received. If an error is detected, the receiver deinterleaving process is performed somewhat differently sends a retransmission request to the transmitter. Since a according to the interleaving processes performed by the APLNDC-WH-A 0000017654 US 7,200,792 B2 23 24 interleaver in the transmitter, in order to finally create the a modulator for alternatively collecting the permutated original systematic bits and parity bits, the received bits are bits on a column by column basis from the first interdeinterleaved in a method corresponding to each method leaver and the second interleaver, and mapping colperformed by the transmitter. lected bits from the first interleaver and second interWith reference to F1G. 19, a description will be made of 5 leaver onto one modulation symbol, an operation of the deinterleaver in the receiver according to wherein a size of the first interleaver is equal to a size of an embodiment of the present invention. The deinterleaver the second interleaver. 2. The apparatus of claim 1, wherein if a number of the receives up,l, up,2, Up,3 ..... Up,Us, and Up,us+l, Up,us+2, rate-matched systematic bits is less than a number of the Up,us+3 ..... Up,us+up (Step 1900). (1) First, the total number of columns C2 is set to 30. The 10 rate-matched parity bits, part of the rate-matched parity bits columns are assigned column numbers 0, 1, 2, . . . , C2-1 is written next to the rate-matched systematic bits in the first from left to right. The minimum integer indicating a row of interleaver. a matrix R2, satisfying a condition of U Us+Up_-< R2xC2, is 3. The apparatus of claim 1, wherein if a number of the determined (Step 191)2). The rows of the matrix are assigned rate-matched systematic bits is greater than a number of the row numbers 0, 1, 2, ..., R2-1 from top to bottom (Step 15 rate-matched parity bits, part of the rate-matched systematic 1904). bits is written prior to the rate-matched parity bits in the second interleaver. (2) The inputs Up,l, Up,~, Up,3, . . . , Up,us are written in a forward direction row by row in an R2xC2 rectangular 4. The apparatus of claim 1, wherein if the modulation matrix beginning at yp,~ in a 0t~’ row and a 0t~’ column, and scheme is 16QAM (16-ary Quadxature Amplitude Modulathe inputs Up,us+~, Up,us+~, Up,us+3,..., Up,us+up are written 20 tion), alternatively outputting 2 bits on a column by column basis from the first interleaver and second interleaver. in a reverse direction row by row beginning at a point in an (R2-1)t~’ row and a (x-l)t~’ column (Step 1906). Here, x 5. The apparatus of claim 1, wherein if the modulation means a remainder obtained by dividing the U by the C2, scheme is 16QAM (16-ary Quadxature Amplitude Modulaand is larger than or equal to 1 and smaller than C2 tion), mapping onto one modulation symbol 2 bits from the (1 =<x<C2). if R2xC2>U (Step 1908), then dummy bits of 25 first interleaver and 2 bits from the second interleaver. 6. A method for data transmission in a communication yp,k=0 or 1 (for k=U+l, U+2,..., R2xC2) are inserted (Step 1910). The dummy bits are deleted (Step 1914) after being system, comprising the steps of: subject to column permutation (Step 1912). turbo coding data bits to generate systematic bits and (3) After the column permutation is performed according parity bits; to a rule (Step 1912), the resulting bits are divided into a 30 rate matching the systematic bits and parity bits; systematic bit (S) part and a parity bit (P) part. writing the rate-matched systematic bits on a row by row (4) Outputs of the deinterleaver are read by two bits basis in a first interleaver and the rate-matched parity column by column, by dividing the column-permuted bits on a row by row basis in a second interleaver; R2xC2 matrix into a systematic bit part and a parity bit part performing inter-column permutation in the first inter(Step 1916). leaver and in the second interleaver; As described above, the present invention provides a alternatively collecting the permutated bits on a column method for efficiently performing interleaving in mapping by column basis from the first interleaver and the the bits with higher priority to the position with higher second interleaver; reliability of a symbol, thereby preventing an increase in mapping the collected bits from the first interleaver and hardware complexity and maintaining compatibility with an 40 second interleaver onto one modulation symbol, existing interleaving technique. Since the SMP technique for wherein a size of the first interleaver is equal to a size of differentially mapping reliabilities according to priority the second interleaver. shows theoretically sufficient effects, it is very important to 7. The method of claim 6, wherein if a number of the realize the SMP technique. The present invention, when rate-matched systematic bits is less than a number of the applied to a high-speed packet transmission system, espe- 45 rate-matched parity bits, part of the rate-matched parity bits cially HSDPA or lxEV-DV system, can be realized through is written next to the rate-matched systematic bits in the first minor modification of an algorithm and minor addition of interleaver. hardware, while maintaining its gain. 8. The method of claim 6, wherein if a number of the While the invention has been shown and described with rate-matched systematic bits is greater than a number of the reference to a certain preferred embodiment thereof, it will 5o rate-matched parity bits, part of the rate-matched systematic be understood by those skilled in the art that various changes bits is written prior to the rate-matched parity bits in the in form and details may be made therein without departing second interleaver. from the spirit and scope of the invention as defined by the 9. The method of claim 6, wherein if the modulation appended claims. scheme is 16QAM (16-ary Quadxature Amplitude ModulaWhat is claimed is: 55 tion), alternatively outputting 2 bits on a column by column 1. An apparatus for data transmission in a communication basis from the first interleaver and second interleaver. system, comprising: 10. The method of claim 6, wherein if the modulation a turbo encoder for coding data bits to generate systematic scheme is 16QAM (16-ary Quadxature Amplitude Modulabits and parity bits; tion), mapping onto one modulation symbol 2 bits from the a rate matcher for rate matching the systematic bits and 6o first interleaver and 2 bits from the second interleaver. parity bits; 11. An apparatus for receiving data in a communication a first interleaver for writing the rate-matched systematic system, comprising: bits on a row by row basis, and performing intera demodulator for demodulating a received symbol into a column permutation; plurality of systematic bits and parity bits; a second interleaver for writing the rate-matched parity 65 a first deinterleaver for writing the plurality of systematic bits on a row-by-row basis, and performing interbits on a column by column basis and performing column permutation; inter-column permutation; APLNDC-WH-A 0000017655 US 7,200,792 B2 25 26 a second deinterleaver for writing the plurality of parity writing the plurality of systematic bits on a column by bits on a column by column basis and performing column basis in a first deinterleaver and performing inter-column permutation; inter-column permutation, and writing the plurality of a rate matcher for rate matching the de-interleaved sysparity bits on a column by column basis in a second deinterleaver and performing inter-column permutatematic bits and parity bits; and 5 a decoder for decoding the rate matched systematic bits tion; and parity bits, rate marching the de-interleaved systematic bits and parwherein a size of the first deinterleaver is equal to a size ity bits; and of the second deinterleaver. decoding the rate matched systematic bits and parity bits, 12. The apparatus of claim 11, wherein if a number of the 10 wherein a size of the first deinterleaver is equal to a size systematic bits is less than a number of the parity bits, part of the second deinterleaver. of the parity bits is written next to systematic bits in the first 15. The method of claim 14, wherein if a number of the deinterleaver. systematic bits is less than a number of the parity bits, part 13. The apparatus of claim 11, wherein if a number of the of the parity bits is written next to the systematic bits in the systematic bits is greater than a number of the parity bits, 15 first deinterleaver. part of the systematic bits is written prior to the parity bits 16. The method of claim 14, wherein if a number of the in the second deinterleaver. systematic bits is greater than a number of the parity bits, 14. A method for receiving data in a communication part of the systematic bits is written prior to the parity bits system, comprising: in the second deinterleaver. demodulating a received symbol into a plurality of sys- 20 tematic bits and parity bits; APLNDC-WH-A 0000017656

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?