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 20

TSG-RAN Working Groupl meeting #7
Hannover, Germany, August 30 - September 3, 1999

TSGRl # 7(99)d84

Agenda Item:
Source: SAMSUNG Electronics Co. and LGIC
Title: Text proposal for Turbo codes and rate matching in TS 25.212, TS 25.222 (rev. of R1-99d56)
Document for: Decision

1. Introduction
Rate matching algorithm for Turbo codes proposed by Samsung and LGIC has been approved as a working assumption in Ad
Hoc 5 meeting. This document proposes a revised text proposal of R1-99d56 [1]. The revisions are mainly focused on
notational consistency and more clear description for the TS 25.212 and 25.222 specification [2,3], as recommended by the
chairman in WG1 plenary meeting.

2. Text proposal for TS 25.212
Start text proposal

4.2.3. Channel coding
The following channel coding schemes can be applied to txansport channels:
¯

Convolutional coding

¯

Turbo coding

¯

No channel coding

Table 1: Error Correction Coding Parameters
~--edieN-seheme

BCH
PCH
FACH
RACH
DCH
DCH

Convolutional code

C-od~g-rate

112

Turbo code

NOTE 1: The exact physical layer encoding/decoding capabilities for different code types are FFS.
NOTE 2: In the UE the channel coding capability should be linked to flae terminal class.

.<..~d(t~..K.s...~.~.~e..~..~ e...m...~..~.aJ..~ f.JL2...r..~..~.&~...~W~..r.~.~.~.~.~(~.~.~t~‘.~

APLNDC-WH-A 0000010518

End text proposal

Start text proposal
4.2.3.2.1. Turbo coder
NOTE: 4-state SCCC is not included in Release-99. It needs to be clarified from TSG-SA what are the selvice specifications
with respect to different quality of services. The performance below BER of 10.6 need to be studied if flaere is a
requirement for this quality of services of physical layer.
For data services requiring quality of service between 10.3 and 10.6 BER inclusive, parallel concatenated convolutional code
(PCCC) wifla 8-state constituent encoders is used.
The 8-state PCCC and the 4-state SCCC -are described below.
The transfer function of the 8-state constituent code for PCCC is
G(D)= I1, n(D) 1
d(D) J
where,

d(D)= 1 +D2+D3
n(D)= 1 +D+D3.
~ X(t)

X(t)

-~ X’(t)

Figure 1 : Structure of the 8 state PCCC encoder (dotted lines effective for trellis termination only)
The initial value of the shift registers of the PCCC encoder shall be all zeros.
The output of the PCCC encoder is punctured to produce coded bits corresponding to the desired code rate 1/3.-at--i-/2-. For rate
1/3, none of the systematic or parity bits are punctured, and the output sequence is X(0), Y(0), Y’(0), X(1), Y(1), Y’(1), etc.

The SCCC is a rate 1/3 SCCC, The outer code of the SCCC is a rate 2/3 obtained by puncturing a rate 1/2 code with generating
matrix

G(°) (z) = (1, (1 + z2)/(1 + z + z2))
End text proposal
Start text proposal

4.2.6. Rate matchin9
[Editors’ note." Rate matching_for Turbo codes is a workin~

APLNDC-WH-A 0000010519

Rate matching means that bits on a transport channel are repeated or punctured. Higher layers assign a rate-matching attribute
for each lxansport channel. This attribute is semi-static and can only be changed through higher layer signalling. The ratematching atlxibute is used when the number of bits to be repeated or punctured is calculated.
The number of bits on a transport channel can vary between different transmission time intervals. In ~e downlink the
transmission is interrupted if the number of bits is lower ~an maximum. When the number of bits between different
transmission time intervals in uplink is changed, bits are repeated or punctured to ensure that the total bit rate after second
multiplexing is identical to the total channel bit rate of the allocated dedicated physical channels.
Notation used in Section 4.2.6 and subsections:
For uplink : Number of bits in a radio frame before rate matching on transport channel i with transport format
combinationj.
For downlink : An intermediate calculation variable (not a integer but a multiple of 1/8).
Number of bits in a ~xansmission time interval before rate matching on TrCH i with ~xansport format 1.
For uplink : If positive - number of bits that should be repeated in each radio frame on TrCH i with transport format
combinationj.
If negative - number of bits l~at should be punctured in each radio frame on TrCH i wi~ transport format
combinationj.
For downlink : An intermediate calculation variable (not a integer but a multiple of 1/8).
If positive - number of bits to be repeated in each transmission time interval on TrCH i with ~xansport format I.
If negative - number of bits to be punctured in each ~xansmission time interval on TrCH i with ~xansport format 1.
Semi-static rate matching attribute for TrCH i. Signalled from higher layers.
PL:

Puncturing limit for uplink. This value limits the amount of puncturing that can be applied in order to avoid multicode
or to enable l~e use of a higher spreading factor. Signalled from higher layers.
Total number of bits that are available for the CCTrCH in a radio frame with transport format combinationj.
Number of TrCHs in the CCTrCH.

Z~).."

Intermediate calculation variable.
Number of radio frames in the transmission time interval of TrCH i.

ni."

Radio frame number in the lxansmission time interval of TrCH i (0 _~ni < F,).
Average puncturing distance. Used in uplink only.
The inverse interleaving function of the 1st interleaver (note that the inverse interleaving function is identical to the
interleaving function itself for the 1st interleaver). Used in uplink only.
The shift of the puncturing pattern for radio frame n,. Used in uplink only.

TF i (1) :
TFS(i) :
TFCS."
X:

Transport format of TrCH i for the lxansport format combination j.
The set of lxansport format indexes I for TrCH i.
The set of transport format combination indexesj.
Initial value of variable e in lke rate matching pattern determination algorilhrn of section 4.2.6.3.
._Systematic bit in 4.2.3.2.1.
st

nd

Note: Time index t in 4.2.3.2.1 is omitted~ the rate matchin~tion.

The * (star) notation is used to replace an index x when lhe indexed variable Xu does not depend on the index x. In lhe left wing
X, = F’ is equivalent to "f~r all _x d~ Xu =/7 ". In lke right wing of an assignment, the
meaning is that "/7 =X," is equivalent to "take a~y _x a~d d~/7 Xu"
The following relations, defined for all TFCj, are used when calculating the rate matching parameters:

APLNDC-WH-A 0000010520

Ndata,j
~ m=l

Z~.

for all = 1 .. I, where [ Jmeans round downwards

for all

~ij = Zij - Zi l,j - N#.

4.2.6.1. Determination of rate matching parameters in uplink
In uplink puncturing can be used to avoid multicode or to enable the use of a higher spreading factor when this is needed
because the UE does not support SF down to 4. The maximum amount of puncturing fiaat can be applied is signalled setup
from higher layers and denoted by PL. The number of available bits in the radio frames for all possible spreading factors is
given in [2]. Denote these values by N256, N¢2s, N64, N3:, N¢o, N~, and N4, where the index refers to fiae spreading factor. The
possible values of Na.t. then are { N:5o, JVI~s, JV64, JV3;, JV16, JV~, JV4, 2N~, 3N~, 4N~, 5N~, 6N4}.Depending on fiae ~ capabilities,
the supported set of Naata, denoted SETO, can be a subset of { N2~6, N12s, No~, N~2, NlO, N~, N~, 2N~, 3N~, 4N4, 5N~, 6N~}.
for the transport format combination j is determined by executing flae following algoriflam:

=, in u hth t _ i" nonn tiw,
If the smallest element of SET 1 requires just one PhCH then
N~.t.j = min SET 1
else

SET2={Na.~.inSETOsuchthatNdata--l)L’x/~=llm<_~<_nz{l~My}’Nx,j is non negative }
Sort SET2 in ascending order
Na.~. = min SET2
While N~.~ is not the max of SET2 and the follower of N~ requires no additional PhCH do
Na.~. = follower of Na.~. in SET2
End while
End if
The number of bits to be repeated or punctured, AN, u, wiflain one radio frame for each TrCH i is calculated wifla the relations
given in Section 4.2.6 for all possible txansport format combinations j and selected every radio frame. Additionally for
determining e~.~, the following parameters are needed:
For convolutonal codes,
.a..~.2..f..~t..h..e..~r.a..t.e..~.m..~.a.t.£~h..i..n.~g~a..~.g.~.~i..t.~~g:.~:~
q= lNij /( / AN~j / ) J

if
then q’
--

q
note

, where l

q
gcd(q, F~)/F~
that
q’

J means round downwards a~d / / mea~s absolute value.

is
even
-- where gcd (q, F~) means greatest common divisor of q and F~
is
not
an
integer,
but
a
multiple
of
1/8

else

q’ q
endif
for

to

F~-I

APLNDC-WH-A 0000010521

For each radio frame, the rate-matching pattern is calculated with the algorithm in section 4.2.6.4?4_, where:
N N~j, and
eii~i = (-2-.a.’S(ni)’lANI ÷ N) mod a.a...N, .i..f....e.~,_~..U....0...t..h..e...n...e.i_,_~..~..a.:..N..:
For turbo codes if re etition is to be erformed such as 2~,_.~,_._>0~Q~arameters for turbo codes are the same as parameter for
a=2 or Y ari se uence and
a= l ~uence.

~AN~ 21for Y’ sequence
AN=" IkNilj / j / 2Jfor Y sequence

__S~:_.~~].]~ = x rood 2;

.... ~’L~ i ( &.+...?.L.m...o..4.~ Jl.......x....m...o..4..2.:

end for
else

_j~is even
then ~/~_,. -- where cd~,.~reatest common divisor of ~_,.

............................................. : ~n~t~e~t~h~a~t~q~i~s~n~t~a~n~i~m~t~e~ge~r~¢~mu!*ip~a~£~!~(~
endif
for x=0 to F._,. - 1

.,:......,!7.~..*.¢:.~..m...o..4.~,:
......
.......i..f.(.y ..s..e...qu.e...n..c..e.)

..........

...... j!i( ..Y. :...s..e..q .u..e...n..c..e.).
endfor
endif
e_~,,~), z:VV + N) mod a.N Ue~,~ 0 then e,~ a.N.

4.2.6.2. Determination of rate matching parameters in downlink
For downlink N~,t,j does not depend on the txansport format combination j. N~,,,~ is given by tke channelization code(s)
assigned by higher layers.

APLNDC-WH-A 0000010522

4.2.6.2.1. Determination of rate matching parameters for fixed positions of TrCHs
First an intermediate calculation variable Ni,. is calculated for all transport channels i by the following formula ¯

1

¯ In N ij
Ni,* -- ~i l+~Fa~’~i)rrz
The computation of the ANi,~z parameters is then performed in for all TrCH i and all TF I by the following formula, where
ANi,. is derived from Ni,. by the formula given at section 4.2.6:

~Vi~z -- F,.o
Note : the order in which the transport format combinations are checked does not change the final result.
For each transmission time interval of TrCH i with TF l, the rate-matching pattern is calculated with the algorithm in Section
4.2.6..-3_4. The following parameters are used as input:

_F___o__r___t__u__r__b___o____c_9__d__e__s_0__j_f____r_e_petition is to be P.e..r..f..~....rr~..e...d.=...s..u..c...h....a..s...~L.~....>...~.~..parameters for turbo codes are the same as parameter for
a 2~
S~stematic bit should not be punctured.

(Iz~v,~z/2|for g sequence
[1AN~,, / 2|for Y’ sequence

N=LN2/3]
max IN2
e~,, = max--

/3/.

4.2.6.2.2. Determination of rate matching parameters for flexible positions of TrCHs
First an intermediate calculation variable NO. is calculated for all transport channels i and all lxansport format combinationsj
by the following formula ¯

1

= __. ~[TTI (~)
"’ ~,~F~

APLNDC-WH-A 0000010523

Then rate matching ratios RFi are calculated for each the txansport channel i in order to minimise the number of DTX bits when
the bit rate of flae CCTrCH is maximum. The RFi ratios are defined by the following formula ¯
N data,*
.RA/I
) i

R/~,. = max i=I
~-~,(RMi’Ni,J
j~TFCS ~1 -

The computation of ANi,~z parameters is flaen performed in two phases. In a first phase, tentative temporary values of ANg,~z
are computed, and in the second phase they are checked and corrected. The first phase, by use of the RF~ ratios, ensures that the
number of DTX indication bits inserted is minimum when the CCTrCH bit rate is maximum, but it does not ensure that the
maximum CCTrCH bit rate is not greater than N~.t.,.. per 10ms. The latter condition is ensured through the checking and
possible corrections carried out in the second phase.
TTI.

At the end of the second phase, the latest value of ANi,z is the definitive value.
The first phase defines the tentative temporary ANi,~z for all transport channel i and any of its transport format I by use of the
following formula ¯
[-RF .N~z

AN~I = ~

i_ i,z /_NrrZ

¯/

/ z. /

The second phase is defined by the following algorithm :
for all j in TFCS do
-- for all TFC
i=I ]~TTI

D

TTI

~’~ ~ " i,TF, (j) -I- ~i,TF, (j)
il

-- CCTrCH bit rate (bits per lOms) for TFC l

Fii

if D > Nd.t.,. then
fori= 1 toldo

-- for all TrCH
-- ANi,j is derived from Ni,j by the formula given at section 4.2.6

TTI

if AN~,r~,(j.) > ANthen
TTI
~i, TF, (j) = ~

end-if
end-for
end-if
end-for
Note : the order in which the transport format combinations are checked does not change the final result.
For each txansmission time interval of TICH i with TF 1, the rate-matching pattern is calculated with the algorithm in Section 0.
The following parameters are used as input:

.F..o..r...c..o..n...v..o.!.u..t.i.o...n..a.!...c..o...d..e..s.,
AN= AN~rz

N = Ni~rz

For turbo codes, if re etition is to be erformed such as ~3N>0 arameters for turbo codes are the same as parameter for

APLNDC-WH-A 0000010524

s_Systematic bit should not be punctured.
AN~z / 2 for Y sequence

[I ANiz / 2|for Y’ sequence

4.2.6.3. Bit separation for rate matchinq
..iiii01011...

Channel
encoder
R=1/3

Bit
Seperation

..llxllOlOx...

Y

Rate matching
algorithm
..llxllOlOx...

yv

..111101011...

Radio
frame
segmentation

..llxllOlOx...

Y
Bit
Seperation

Rate matching
algorithm
yv

..llxllOlOx...

Figure 4-2. Overall rate matchin~am after first interleaving~where x denotes punctured bit.
Rate matchin~ for Turbo codes in u link is a lied se aratelv to Y and Y’ sequences. No uncturin is a lied to X
se_~uence. Therefore. it is necessa~ ~ and Y’ sequences before rate matchin isgjLgI@plied.
TrCH as shown in Table 1.

APLNDC-WH-A 0000010525

TTIms(m~)

TTI

L.m...s..e..c.)

Alternation patterns
... XYY’...

Table 2 Initial ~e of radio frames of TrCH in uplink
Radio frame indexes ~i)
1

2

3

4
NA
NA
NA

10
20
40
80

5
NA
NA
NA

6

7

Table 1 and 2 defines a com lete out ut bit attem from Radio frame se_ggmentation.

Ex. 2 TTI = 40 msec._n.~ = 3
Radio frame attern: X Y Y’ X Y Y’ X Y Y’ X ...
specified in Table 1 and 2 according to the TTI and _n! of a TrCH.

achieved with the alternative selection of bits from Turbo encoder.

4:-2:6:-3:-4.2.6.4. Rate matching pattern determination
Denote the bits before rate matching by:
Xil, Xi2, Xi3 .... XiN, where i is the TrCH number and N is the
4.2.6.2.
The rate matching rule is as follows:

’

’-_- ’ " ....

" p..a..r..a...m...e..t.e..r...gi..v..e...n..j..n...

if puncturing is to be performed

y = -AN
e

m1
do whilem< N
e e -2.a.,*y
if e < 0 then
puncture bit
ee+
end if
m m+l
end do

-- initial error between current and desired punctuHng ratio
-- index of current bit
-- update error
-- check if bit number m should be punctured
-- update error
-- next bit

else
m=l

-- initial error between current and desired puncturing ratio
-- index of current bit

APLNDC-WH-A 0000010526

do whilem< N
e e~2~..*y
do whilee< 0
repeat bit Xi, m
e e + -2.a*N
enddo
m m+l
end do

-- update error
-- check if bit number m should be repeated
-- update error
-- next bit

end if
A repeated bit is placed directly after the original one.

3. Text proposal for TS 25.222
Start text proposal

6.2.3. Channel coding
Code blocks are delivered to the channel coding block. They are denoted by Oirl, Oir 2, Oir 3,’’’, OirKi ’ where i is the TICH
number, r is the code block number, and K,. is the number of bits in each code block. The number of code blocks on TICH i is
denoted by Ci. After encoding the bits are denoted by Xirl, xir2, xi~3,..., xi~& . The encoded blocks are serially multiplexed so
that, Ci2, Ci3 ,,,with lowest index r theoutput first from theE~ = C.~.. The output bits are defined by the following relations:
Cil the block ,, C~,i , where i is is TrCH number and channel coding block. The bits output are denoted by

Cik z "~ilk

k=l,2 ..... X~

Cik ~ Xi,2,(k X~)

k =X,. + 1, X,. + 2 ..... 2X~

Cik ~ Xi,3,(k 2X~)

k = 2X,. + 1, 2~,. + 2 ..... 3X~

Cik ~ "?~i,C~,(k (C~ 1)Xz)

k = (C~- ]~ + ], (C~- ]~ + 2 ..... C.~

The relation between Oirlc and Xirlc and between K~ and)2,, is dependent on the channel coding scheme.
The following channel coding schemes can be applied to txansport channels.
¯ Convolutional coding
¯

Turbo coding

¯

No channel coding

10

APLNDC-WH-A 0000010527

Table 6.2.3-1 Error Correction Coding Parameters

-1-/2

DON

442v--14,3-eF-P,e- -Go d#q g

-T-u.Fbe--Gede

Transport channel ty~p~
BCH
PCH
FACH
RACH
DCH
DCH

Codin~ scheme

Convolutional code

Coding~ rate
112

Turbo code

Note 1." The exact physical layer encoding/decoding capabilities for difJbrent code types are FFS.
Note 2: In the UE the channel coding capability shouM be linked to the terminal class.
End text proposal
Start text proposal

6.2.3.2. 1. Turbo coder
<Note." It needs to be clarified ffom TSG SA what are the service specifications with respect to difJbrent qualities of service.
6
The pe~ormance below BER of lO- needs to be studied if there is a requirement for this quality of services over the physical
layer. >
For data selvices requiring quality of selvice between 10.3 and 10.6 BER inclusive, parallel concatenated convolutional code
(PCCC) wifla 8-state constituent encoders is used.
The transfer function of the 8-state constituent code for PCCC is
G(D)= [1, n(D) 1
d(D) J
where,

d(D)= 1 +D2+D~
n(D)= 1 +D+D3.

11

APLNDC-WH-A 0000010528

~, X(t)

x(t)

"~ X’(t)

Figure 6-3. Structure of the 8 state PCCC encoder (dotted lines effective for trellis termination only)
The initial value of the shift registers of the PCCC encoder shall be all zeros.
The output of the PCCC encoder is punctured to produce coded bits corresponding to the desired code rate 1/3-~)v-t,/-Z For rate
1/3, none of the systematic or parity bits are punctured, and the output sequence is X(0), Y(0), Y’(0), X(1), Y(1), Y’(1), etc.
F~--r~e--t ¢=v-~-he--parity--Joi~--pr~d~e 0~-~oy--~-he--e~n~ tit t~ent--ene~te~ ~--are--attemate4) --p,ane4u~e&~e,-pr~k~ee--t~-~tiyat-- ~e~ue~ee
End proposal
Start text proposal

6.2.7. Rate matching
Rate matching means that bits on a TrCH are repeated or punctured. Higher layers assign a rate-matching attribute for each
TrCH. This attribute is semi-static and can only be changed through higher layer signalling. The rate-matching atlxibute is used
when the number of bits to be repeated or punctured is calculated.
The number of bits on a TrCH can vary between different transmission time intervals. In flae downlink the ~xansmission is
interrupted if the number of bits is lower than maximum. When the number of bits between different ~xansmission time
intervals in uplink is changed, bits are repeated or punctured to ensure that the total bit rate after second multiplexing is
identical to the total channel bit rate of the allocated dedicated physical channels.
Notation used in Section 6.2.7 and subsections:
Number of bits in a radio frame before rate matching on TrCH i with txansport format combinationj.
If positive - number of bits that should be repeated in each radio frame on TrCH i with txansport format combinationj.
If negative - number of bits that should be punctured in each radio frame on TrCH i with transport format combination
Semi-static rate matching attribute for TrCH i. Signalled from higher layers.
Puncturing limit for uplink. This value limits the amount of puncturing that can be applied in order to avoid multicode
or to enable the use of a higher spreading factor. Signalled from higher layers.
Total number of bits that are available for the CCTrCH in a radio frame with transport format combinationj.
Number of TrCHs in the CCTrCH.

12

APLNDC-WH-A 0000010529

Intermediate calculation variable.
Number of radio frames in the transmission time interval of TrCH i.
Radio frame number in the txansmission time interval of TrCH i (0 _<n~ < F,).
Average puncturing distance.
The inverse interleaving function of the 1st interleaver (note that the inverse interleaving function is identical to the
interleaving function itself for the 1st interleaver).
The shift of the puncturing pattern for radio frame
TF £1) ."
TFS(i)."
X."

Transport format of TrCH i for the lxansport format combination j.
The set of lxansport format indexes I for TrCH i.
Initial value of variable e in the rate matching pattern determination algorilkm of section 6.2.7.3.
s_Systematic bit in 6.2.3.2.1.
st

nd

._Y__’_._. _2______p__a__r_i__.ty___b_ j_t___( _f_r__o___m__ 1h.e.~..~.~.w...e..r.~.T..u..r.?.~..~.~.c...~..n..s.
...............
Note." Time index t in 6.2.3.2.1 is omitted~ the rate matchin~tian.

6.2.7.1. Determination of rate matching parameters
The following relations are used when calculating the rate matching pattern:

li

¸

~RMm ¯ Nmj.

ZO

Z Rl~m " N mj

for all i= 1 .. I

m=]

~ ij

= Z ij - Z

i 1,j -- No

for all i = 1 .. I

Puncturing can be used to minimise the number of required transmission capacity. The maximum amount of puncturing that
can be applied is signalled from higher layers and denoted by PL. The possible values for Na,t, in uplink and downlink depend
on the dedicated physical channels which are assigned to the link, respectively. The supported set of Ndata , denoted SET0,
depends on the UE capabilities. Na, t,, ~ for the lxansport format combination j is determined by executing the following
algorithm:
SET1 = { N~ in SET0 such that Ndat~ - PL. ~- @ ,. Nij is non negative
}

~l m~nlRMz }

Na,~,,~ = min SET 1
The number of bits to be repeated or punctured, AN,> within one radio frame for each TrCH i is calculated wilh the relations
given at the beginning of this section for all possible transport format combinationsj and selected every radio frame. For each
radio frame, the rate-matching pattern is calculated with the algorilkm in Section 6.2.7.2, where AN AN,.~ and N N,)..
Additionally for determining e~., the following parameters are needed:
For convolutonal codes

.q...~fq~.~.r~.~.~O!.~.g..q!g~.r!~O.,~.!.~.~.~!~.~..~g:.~:.&
q=
if

INo. /( / AN~ / ) J , where l

J means round downwards and / / means

absolute value.

q
is
even
then q’ = q gcd(q, F,)/F, -- where gcd (q, F,) means greatest common divisor of q and F,
note that q’ is not an integer, but a multiple of 118

13

APLNDC-WH-A 0000010530

else
q’ q
endif
for

x
S(Iu ([-x*q’ ]mod Fi)) ([-x*q’ ] div Fi)

to

end for
For each radio frame, the rate-matching pattern is calculated with the algorithm in section 6.2.7.3, where:
N ~j, and
<,. (..a..S(nO.lz~Vl + N) mod.a..N,

For turbo codes if re etition is to be erformed, such as A~.,.~i_>0~_~arameters for turbo codes are the same as parameter for
.c..o...n..v...o..1..u..t j..o..n...aj..c...o..d..e...s,...I..f.p..u.~rj.~g.i~.;.~.h~.~r£9.~ ~.,.p~r~m~!~r~..~r~..~.f~jjg~,
a= 2 for F ari se uence and
a = l~uence.
For each radio frame~ the rate-matching~attern is calculated with the a_~lKorithm in section 6.2.7.3~ where:

~AN~ / 2Jfor Y sequence
LW =~ idNiij. /j.21for Y’ sequence

....
...... _i_f_L_Y____s__e__~_u__e__n___c__e_)
__S_~~~ = x mod 2~
end for
else

14

APLNDC-WH-A 0000010531

6.2.7.2. Bit separation for rate matchinq

..iiii01011...

Radio
frame
segmentation

..llxllOlOx...

Y

Bit
Seperation

Rate matching
algorithm
..llxllOlOx...

Figure 6-1. Overall rate matchin~am after first interleavin&where x denotes punctured bit.

Rate matchingl?_U___n__c___tA___r__m__g for Turbo codes is . _a_ p_ l?_ _l_i_ _e_ _d_ _ _ _s_ _el?_ _a_ _r_ _a_ _t_e_ _ly_ " to Y and Y’ sequences. No p__u___n_£_t__u__rj__n_g__i_s____a_p_p
Therefore i~ arateX Yand Y’ se uences before rate matchin isgjkkp_plied.
shown in Table 1.
Table 1 A~temati~n.p...a.t..t..e...m...s..9.f...b..i..t.s....f.r..~...m....r..a..d..i£.[[~£.~#~enmti~n
TTI ms~_s~)
Alternation patterns

...xy, Y’...

~

radio flame ofa TrCH with TTI = ~10 20 40, 8@ msec.
TTI

.(..m..s..e...c.)
0
10
20
40
80

X
X
X
X

1
NA
Y
Y’
Y

2

3

4
NA
NA
NA
y

5
NA
NA
NA
y’

6

7

Table 1 and 2 defines acom lete out ut bit attem from Radio frame se~g_mentation.

.T..T...I..~....4..0.....m...s.e...c.~..n..,..~....2.

~ a...d.>...f.r.a...m...e...p..a..t.t..e...m...k L.r,.N.!.r~.N.!.r~.N. .....

Ex. 2 TTI = 40 msec. _n_,. = 3
Radio frame attern: X Y Y’ X Y, Y’ X Y Y’ X ...
Therefore, bit se aration is achieved with the alternative selection of bits with the initial ~ and alternation at~
specified in Table 1 and 2 according to the TTI and _n_,.,of a TrCH.

15

APLNDC-WH-A 0000010532

~6.2.7.3. Rate matching pattern determination
Denote the bits before rate matching by:
xil, xi2, x~3 .... X~N, where i is lke TrCH number and N is lke
6.2.7.1.
The rate matching rule is as follows:

’

’ _~ ’ ....

" ~iven in section

if puncturing is to be performed

y = -AN
e

m1
do whilem< N
e e~2a *y
if e < 0 then
puncture bit X~,m
e e+~a*N
end if
m m+l

-- initial error between current and desired puncturing ratio
-- index of current bit
-- update error
-- check if bit number m should be punctured
-- update error
-- next bit

end do
else
-- initial error between current and desired puncturing ratio
m1
-- index of current bit
do whilem< N
e e --2..q.*y
-- update error
do whilee< 0
-- check if bit number m should be repeated
repeat bit X,,m
e e +--2a *N
-- update error
enddo
m m+l
-- next bit
end do

e

end if
A repeated bit is placed directly after the original one.

4. References
[1] "Text proposal for rate matching algorithm for turbo codes in TS25.212, TS25.222", Samsung Electronics Co. and LGIC,
WGI#7, R1-99b56.
[2] TS 25.212 (V2.0.1): "Multiplexing and channel coding (FDD)"
[3] TS 25.222 (V2.1.1): "Multiplexing and channel coding (TDD)"

16

APLNDC-WH-A 0000010533