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)

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