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

Filing 661

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

Mueller Exhibit 19

3GPP_TSG_RAN_WG1 Archives--July 1999 (#294)

View:

Next in topic I Previous in topic
Next by same author I Previous by same author
Previous page (July 1999) I Back to main 3GPP TSG RAN WG1 page
Join or leave 3GPP TSG RAN WG1
~1 Post a new message
Search

Options:

Page 1 of 1

Chronologically I Most recent first
Proportional font I Non-proportional font

Date:
Reply-To:
Sender:

Sat, 10 Jul 1999 16:21:47 +0900
Clog in to unmaskl
"3GPP TSG RAN WGI: TSG RAN Working Group 1"
<[log in To unmask]>
"(Min-goo KIM)" <Clog in to unmask]>
From:
Subject:
CAH04] & CAH05] Tdoc 919: "Unified rate matching scheme "
Content-Type: multipart/mixed;

Dear Ad Hoc 4 and 5 colleagues,
Please find attached the final version of our proposal.

Tdoc number: TSGRl#6(99)919
Title:
"Unified rate matching scheme for turbo/convolutional codes
and up/down links"
File name: Tdoc 919.ZIP
I’m sorry for our late submission.
I will bring the paper copies to the meeting.
Ms. Marlene Forina, could you please place these documents on the server?
Thank you in advance.
Best Regards,
Min Goo KIM
Samsung Electronics Co.
E-mail: Clog in to unmaskl

TDOC 919.ZIP Capplication/zip]

Back to: Top of message I Previous page I Main 3GPP TSG RAN WG1 page

http://list.etsi.org/scripts/wa.exe?A2=ind9907&L=3 gpp_tsg_ran_wg 1 &T=0&P=37037 7/26/2011
APLNDC-WH-A 0000010279

TSG-RAN Working Group1 meeting #6
Espoo, Finland, 13-16, July 1999

TSGRl#6(99)919

Agenda item:
Source: SAMSUNG Electronics Co.
Title: Unified rate matching scheme for Turbo/ convolutional codes and
up/down links
Document for: Discussion & decision

1. introduction
In this document, we propose a new common rate matching scheme for both
convolutionai codes and turbo codes, and for both up-link and down-link. Recently, LGIC and
Fujitsu have proposed rate matching algorithms with different algorithms for convolutional
coding and turbo coding, respectively [1]-[5]. Also, Siemens and Nortel have investigated rate
matching algorithms for both down-link and up-link respectively[6]-[7]. However the different
characteristics of convolutional codes and turbo codes make it difficult to find an optimal
solution for all cases. In [6], Siemens proposed a rate matching algorithm for convolutional
codes for up-link and down-link, which has been adopted in [8]. In [1]-[5], Fujitsu and LGI
C proposed two rate matching algorithms for down-link turbo codes. The performances of
two algorithms are similar for turbo coding and it seems difficult to find performance
improvement in terms of puncturing patterns in both algorithms. This reason is related to the
turbo interleaver characteristics such that the random property of turbo interleaver gives a
similar performance regardless of puncturing pattern for parity symbols. In addition, for convolu
tional codes both algorithms have shown little performance degradation. In this contribution,
we propose a new common rate matching scheme for both convolutional codes and Turbo
codes for up/down-links which reuses conventional rate matching algorithm with parameter
control.

Unified rate matching method
Figure 1 illustrates conventional rate matching algorithm for convolutional codes in downlink. The rate matching algorithm has been proposed by Siemens and adopted for convolutional
codes. All symbols from channel encoder are punctured uniformly. However, for turbo codes
systematic code symbols should not be punctured and the number of the punctured parity
symbols should be distributed evenly. In order to achieve optimal puncturing for turbo codes in
down-link with minimal complexity, we propose a new rate matching scheme given in Figure 2.
The idea can also be applied in up-link. In Figure 2, all code symbols are classified into three
parts such as systematic code symbols (information symbols), the first parity symbols from
constituent encoder 1, and the second parity symbols from constituent encoder 2, respectively.
Rate matching algorithm blocks (RMB) for each part are the same as conventional algorithm
except modifying number of bits per matching block and number of bits per matched block. For
R=1/3 turbo codes, number of bits per matching block Nc and number of bits per matched block
Ni are reduced to 1/3 of the total number of bits per matching blocks and matched blocks,
respectively. Parameter (a,b) is selected for generating arbitrary puncturing or repetition
patterns. Typically, (2,1) is used for conventional rate matching algorithm. If (a,b) for all RMB is
fixed to the same value then all patterns for puncturing and repetition are also the same. The

APLNDC-WH-A 0000010708

definition of parameters is as follows. It is obvious that the proposed algorithm is identical to
conventional rate matching algorithm in [8] except parameter control. So, there are no
implementation complexity increases.
Definition of parameters
Ne: Number of bits per matching block (=Ncs for convolutional codes)
Ni: Number of bits per matched block (=Nis for convolutional codes)
Ncs: Total number of bits per all matching blocks
Nis: Total number of bits per all matched blocks
(a,b): Parameter for conventional rate matching algorithm (to control pattern generation)
The following shows the definition and roles of parameter (a,b) in conventional rate matching
algorithm. Parameter "b" is usually 1 and parameter "a" is only variable for considering hardware
or software implementation complexity.

Conventional Rate Matching Algorithm with parameters (a,b) control
Let’s denote:

~o = { d] , d2 ..... d N~: }= set ofNcdata bits
The rate matching rule is as tbllows:
if puncturing is to be performed

y = NC-Ni
e-~ (2*S(k) * y + h’~Nc) mod ~f*NC
-- initial error bePa,een current and desired puncturing rdtio (down/ink : S-O)
m=1

-- index of current bit

do while m < ~- NC
e =e-,:~ *y

-- update error

i f e < = 0 then

-- check if bit number m should be punctured

puncture bit m from set SO
e = e + t*NC

-- update error

end if
m=mtl

-- next bit

end do
else
y = Ni-NC

e = (2*S(k) * y + b*Nc) rood c~NC
-- initial error between current and desired puncturing ratio (downlink : S=O)
m-I

-- index of current bit

APLNDC-WH-A 0000010709

do while m <- NC
e e ~*y

--updateerror

do while e < = 0

-- check ifbit number mshouMbe repeated

repeat bit m ~orn set SO
~’ = e +

(~*~rC

update error

enddo
m=m1

-- next bit

end do
end if

3. Rate matching for down-link
3.1 Convolutional codes
For convolutional codes, the proposed algorithm is identical to the current optimal rate matching
algorithm using parameters below
Nc = Ncs
Ni=Nis
(a,b)=(2, 1) : exactly the same as conventional rate matching algorithm in [6,8].
This assures that the proposed algorithm gives optimal performance for convolutional coding.
3.2 Turbo code codes
For turbo codes, all code symbols are classified into three parts such as systematic code
symbols (information symbols), the first parity symbols from constituent encoder 1, and the
second parity symbols from constituent encoder 2, respectively. Rate matching algorithm blocks
(RMB) for each part are the same as conventional algorithm except modifying number of bits
per matching block and number of bits per matched block as follows.
Systematic information symbols part: Nc=Ncs/3, Ni=Ncs/3, (a,b)=(2,1)
Parity symbols part 1: Nc=Ncs/3, Ni=(Nis- Ncs/3)/2, (a,b) =arbitrary constant
Parity symbols part 2: Nc=Ncs/3, hh=(NJs- Ncs/3)/2, (a,b) =arbitrary constant
Parameter "b" is usually 1 and parameter "a" is only variable for considering hardware or
software implementation complexity. In order to generate the same puncturing or repetition
patterns for RMB2 and RMB3, it is sufficient to make parameter "a" have the same value for
RMB2 and RMB3. Otherwise, it is sufficient to make parameter "a" have different value for
RMB2 and RMB3, respectively. Therefore, there are no change of conventional rate matching
algorithm except these parameters.
Table 1 shows examples of rate matching algorithm (puncturing) according to different
parameters (a,b). Typically parameter "b" is 1 and parameter "a" is 2. However, arbitrary
constant can be used for (a,b). Case 1, 3, and 5 give systematic puncturing with the same
puncturing pattern and Case 2, 4, and 6 give systematic puncturing with different puncturing

APLNDC-WH-A 0000010710

patterns.
Figure 3 shows implementation of the proposed rate matching scheme using single rate
matching block for both convoultional codes and turbo codes in down-link. It is sufficient to use
single conventional rate matching block with temporal registers to store (Nc, Ni, e, b, a). These
parameters are updated for each RMB blocks. Also, the proposed scheme requires neither high
speed clock nor additional memory for buffering. Furthermore a current rate matching algorithm
block hardware can be used for the proposed scheme with slight modification for loading
parameters. Software implementation is very simple such that it needs only one more
subroutine call for rate matching with updated parameters.
Another merit of the proposed scheme is that it dose not produce time delay for rate matching.
All symbols form channel encoder are transferred into rate matching block and pass out through
rate matching block at the same time, with or without puncturing or repetition.
Table1. Examples of rate matching algorithm variation according to parameters (a,b).
Case
1
2
3
4
5
6

RMB1
Nc
Ni
a
b
Ncs/3 Ncsi3 NR NR
Ncs/3 Ncs/3 NR NR

RMB2
Nc
Ni
Ncs/3 (Nis-Ncs/3)/2
Ncs/3 (Nis-Ncs/3)/2

a
2
2

b
1
1

RMB3
Nc
Ni
a
Ncs/3 (Nis-Ncs/3)/2 2
Ncs/3 (Nis-Ncs/3)/2 5

b
1
1

(Nis-Ncs/3)/2
(Nis-Ncs/3)/2

p
p

1
1

Ncs/3
Ncs/3

111

INcs/3 INcs/31NRINRINcs/3
Ncs/3
Ncs/3 NR NR Ncs/3

(Nis-Ncs/3)/2 q
(Nis-Ncs/3)/21P

INcsl3 INcsl3 tNRINRINcsl3 I(Nis-Ncsl3)12
tPp Iqq INcs/3
Ncs/3
Ncs/3 NR NR Ncs/3
(Nis-Ncs/3)/2
Ncs/3 (Nis-Ncs/3)/2 IP
(Nis-Ncsi3)/2
p,q,r,s: arbitrary constant
NR: Not related to the rate matching algorithm.
RMB1, RMB2, RMB3: Rate Matching Block 1, 2, 3.
RMBI: Rate matching block for Systematic information symbols part (By passed)
RMB2: Rate matching block for Parity symbol I
RMB3: Rate matching block for Parity symbol 2

yk

Rate Matching
Block

..11xllx10x...

Fig. 1. Conventional rate matching scheme for convolutional codes (Down-link).

APLNDC-WH-A 0000010711

,,111101011.

Rate Matching
Algorithm Block

Nc N i (a,b)
Xk

Turbo
Encoder
R=1/3

C2k

I Rate Matching
----~ [~°rithi Bl°cki

.. 11X! 1010x.

yk

-- (a,b)
Nc

Ni

Rate Matching
AIg_~rithm block 3

Nc

,, x101

lxl lx.

Ni

Fig. 2. A conceptual block diagram of the proposed rate matching scheme for both convoultional
codes and turbo codes (Down-link).

Input
information
symbols

Rate Matching Block
Output
symbols

Channel
Encoder
Code rate R=k/n
(R=1/3 or 1/2)

Clock

Register(F/F) or RAM
for temporal
(Nc,Ni,e,b,a)

nxClock

* Initial value for Turbo codes
RMBl:(Nc,Ni,e,b,a)
RMB2:(Nc,Ni,e,b,a)
RMBn:(Nc,Ni,e,b,a)
* Initial value for Convolutlonal
codes
RMB:(Nc,Ni,e,b,a)

Fig. 3. Implementation of the proposed rate matching scheme using single rate matching block
for both convoultional codes and turbo codes (Down-link).

APLNDC-WH-A 0000010712

4. Rate matching for up-link
Figure 4 illustrates conventional rate matching algorithm for up-link. Rate matching algorithm
operates after radio frame segmentation so it is difficult to separate the flow containing
systematic bits and the two flows containing parity bits (in the case of R=1/3). Operation of rate
matching block is identical to that of down-link. To solve this problem, we proposed a new rate
matching scheme in Figure 5. Note that there is no difference between up-link and down-link
except the existence of de-multiplexing in case of up-link. The key idea is that de-multiplexing
can separate the three flows containing systematic information, parity bits part 1, and parity bits
part 2 one another. This is done due to the good property of MIL 1’t interleaver for transmission
time interval of 10, 20, 40, 80msec. So, the proposed rate matching algorithm in up-link is
exactly the same as in down-link.
4.1 Convolutional codes
For convolutional code, the proposed algorithm is identical to the current optimal rate matching
algorithm using parameters below

Nc=Ncs
Ni=Nis
This assures that the proposed algorithm gives optimal performance for convolutional coding.
4.2 Turbo code codes
For turbo codes, all code symbols are classified into three parts such as systematic code
symbols (information symbols), the first parity symbols from constituent encoder 1, and the
second parity symbols from constituent encoder 2. Rate matching algorithm blocks (RMB) for
each part are the same as conventional algorithm except modifying number of bits per matching
block and number of bits per matched block as follows
Systematic information symbols part." Nc=Ncs/3, Ni=Ncsi3, (a,b)=(2,1)
Parity symbols part 1: Nc=Ncs/3, Ni=(Nis- Ncs/3)/2, (a, b) =arbitrary constant
Parity symbols part 2: Nc=Ncs/3, Ni=(Nis- Ncs/3)/2, (a,b) =arbitrary constant

yk

i

Encoder
K=9, R=1/3

1 ’st
Interleaver

Radio
frame
segementation

Rate Matching
Algorithm Block

..11xllxlOx...

Fig. 4. Conventional rate matching scheme for convolutional codes (Up-link).

APLNDC-WH-A 0000010713

systematic
information
symbols

Nc
Xk

! Radio
1’st
__~,, i Frame
Intedeaver
Segmentation

Turbo
Encoder
R=1/3

Ni (a,b)

Rate Matching

parity 1
symbols

.111101011..,

Rate Matching
Algorithm Block 1

i

.11x11010x...

yk

.Algorithm Block 2

(a,b)
Nc Ni
C3k

parity 2
symbols

Rate Matching
Algorithm block

.x1011xllx,..

(a,b)
Nc Ni

Fig. 5. A conceptual block diagram of the proposed rate matching scheme for both convoultional
codes and turbo codes (Up-link).

input
information
symbols

Channel
Encoder
Code rate
R=1/3

Rate Matching Algorithm
Block
~ n:l I ,..._!
1 ’st
MUX [-~
Interleavar
¯
¯
!

Radio
frame
l:n
seg~ DEMUX
, ementation
i

I

Clock

nxClock

Note. xk: systematic information symbot
ylk,y2k: parity symbols of encoderl and encoder 2, respectively

Output
symbols

Register(F/F) or RAM |
for temporal
(Nc,Ni,e,b,a)

Initial value for Turbo codes
RMBI:(Nc,Ni ,e,b,a)
RI~B2: (Nc,Ni ,e,b,a)
RMBn:(Nc,Ni ,e,b,a)
Initial value for Convolutlonal
codes
RI~B:(Nc,Ni ,e,b,a)

Fig, 6. Implementation of the proposed rate matching scheme using single rate matching block
for both convoultional codes and turbo codes (Up-link).

APLNDC-WH-A 0000010714

Figure 6 shows implementation of the proposed rate matching scheme using single rate
matching block for both convoultional codes and turbo codes in up-link. It is sufficient to use
single conventional rate matching block with temporal registers to store (Nc, Ni, e, b, a)

5. Simulation results
For turbo codes, the suggested simulation conditions announced at the 2nd AdHoc meetin
g at Cheju are as follows
Block sizes: 320, 321,640,641, 5120, 5119
Puncturing rates: 5%, 10%, 15%, 20%, and 1/2 code (=33%)
Decoding algorithm: Log MAP decoder
Turbo interleaver: PIL
Number of iterations: 12
BFR: >10E-6
Number of frame error: greater than 100
Channel model: AWGN
Tail bits puncturing
Algorithms: SEC, Siemens ,LGIC, and Fujitsu
In the following figures, SEC_T1 and SEC_T2 mean the following parameter setting for RMB2
and RMB3, respectively.

SEC_T1
SEC T2

RMB1
Not used
Not used

RMB2
(atb)=(2,1 )
(a,b)=(2,1)

RMB3
(a,b)=(5,4)
(a,b)=(3,1)

6. Conclusion
In this contribution, we proposed a unified rate matching algorithm for both turbo codes a
nd convolutional codes and both down-link and up-link. The proposed rate matching algori
thm does not change the conventional rate matching algorithm proposed by Siemens. It o
nly controls parameter for the conventional rate matching algorithm. The conclusions are
as follows
The proposed rate matching algorithm can support both turbo code and convolutional
codes and both up-link and down-link.
¯ The rate matching algorithm is optimal for both convolutional coding and turbo coding.
¯ For up-link, it has been shown that the output symbols from the 1’st interleaver can b
e classified into two parts implicitly such as systematic information symbol part and parity
symbols (from constituent encoder "1 or 2 part, respectively.
For rate matching of turbo codes, LGIC’s algorithm and Fujitsu’s old algorithm are sp
ecial cases of the proposed algorithm.
Implementation of the proposed rate matching algorithm require neither increase in ha
rdware complexity nor software complexity. It can be easily implemented by using convent
ional rate matching algorithm block with parameter configuration.
The proposed rate matching algorithm provides a single structure of rate matching for
both down-link and up-link.
The proposed rate matching algorithm does not require any increase of buffer memor

APLNDC-WH-A 0000010715

y in both sides of transmitter and receiver. Also it does not require processing delay for
storing output symbols from channel encoder for reordering.

7. References
[1] "Comparison of downlink puncturing algorithms", LGIC, TSGR1#5(99)654(1999-06).
[2] "Puncturing algorithm for turbo code", LGIC, TSGR1#4(99) 338 (1999-04)
[3] "Further results of rate matching algorithm for downlink", Fujitsu,TSGRl#5(99)698(199
9-06).
[4] "Tail bits and puncturing of rate 1/2 turbo coding", Fujitsu, TSGR1#5(99)665(1999-06).
[5] "Optimised puncturing schemes for turbo coding", Fujitsu, TSGR1#4(99)388(1999-04).
[6] "Optimised rate matching after interleaving", Siemens, TSGR1#3(99)203.
[7] "Proposal for rate matching for turbo codes", Nortel Networks, TSGR1#4(99)467 (199
9-04)
[8] 3GPP TSG RAN WG1 Multiplexing and channel coding (FDD)TS 25.212 v2.0.0 (1999-06)

Contact inform:
K i m m i n qu_~Z!A#_&g, c o. k r
~telecom.samsung..co. kr

APLNDC-WH-A 0000010716

intedeaver si/~=320,puncturing rate=5%
I OE+O0

I 0E-02

I 0E-03

1.5
Eb!No (dB)

Fig. 7. interleaver size=320,puncturing rate=5%.
interlenver size=320,pun¢luring rale=10%
10E+O0

l 0E~03

I 0E-04

I 0E-05

E b/’Na (dB)

Fig. 8. interleaver size=320,puncturing rate=10 o
’/’o.

10

APLNDC-WH-A 0000010717

10E+O0

I 0E-02

10E-05

I 0E-06

Fig. 9. interleaver size=320,puncturing rate=15%.
interleaver size=320,punemring rate=20%
I 0E+00

I OE-02

I OE-04

I 0E-05

Fig. 10. interleaver size=a20,puncturing rate=20%.

11

APLNDC-WH-A 0000010718

1 0E-03

I 0E-04

Fig. 11. interleaver size=320,puncturing rate=33%.
interleaver size=321 ,puncturing rate=5%

Fig. 12. interleaver size=321,puncturing rate=5%.

12

APLNDC-WH-A 0000010719

interleaver size=32 l,p~nctur2ng rate~ 10%

E b, ,,%to (dB)

Fig. 13. interleaver size=321,puncturing rate=lO%.
interleaver size=32 l,puncturing rate= 15%

t OE-02

F~g. 14. interleaver size=321,puncturing rate=15%.

13

APLNDC-WH-A 0000010720

interleaver size=32],puncturing rate~20%
IOE+O0

| OE-02

I 0E-04

1 OH-05

1.5
EI~’N o (dB)

Fig. 15. interleaver size=321,puncturing rate=20%.
interleaver size~321,punctuang rate=33%

I 0E4)I

t OE-05

Fig. 16. interleaver size=321,puncturing rate=33%.

!4

APLNDC-WH-A 0000010721

imerleavel size=640.pun¢turing rate=~%

I OE-02

I 0E-06
Eb/No

Fig. 17. interleaver size=640,puncturing rate=5%.
interleaver size=640,punctufing tale= 10%
I.OE+O0

I OE-02

I 0 E-()4

I OE-O5

Fig. 18. interleaver size=640,puncturing rate=lO%.

15

APLNDC-WH-A 0000010722

Fig. 19. inter|eaver size=640,puncturing rate=15%.
intefleaver size=fi4{t,punctunng rate=20%

Eb,qqo (dB)

Fig. 20. interleaver size=640,puncturing rate=20%.

APLNDC-WH-A 0000010723

interleave~ size=640,puncmflng rate~33%

Fig. 21. interleaver size=640,puncturing rate=33%.
interleaver size=64 l,puncturing rate~5%

I OE-03

I 0E-04

Eb/No (d13)

Fig. 22. interleaver size=641,puncturing rate=5%.

17

APLNDC-WH-A 0000010724

interleaver size=64 I,punctunng rate=

I 0E-02

[ 0E-05

I 0E-06

Fig. 23. interleaver size=641,puncturing rate=l 0%.

Eb,No

Fig. 24. interleaver size=641,puncturing rate=l 5%.

18

APLNDC-WH-A 0000010725

mterleav*r size=641,puncturn~g rate~20%
l OE+O0

I 0E-02

Fig. 25. in~erleaver size=641,|mnet~ring ra~e=20%.
interleaver size=641 ,puncturing rate-33%
IOE+O0

I 0E-02

t 0E~03

] OE~04

Fig. 26. interleaver size=641,p~net~ring rate=33%.

APLNDC-WH-A 0000010726