`
`
`UNITED STATES PATENT AND TRADEMARK OFFICE
`____________________
`
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`_____________________
`
`LG Electronics, Inc.
`Petitioner,
`
`v.
`FastVDO LLC
`Patent Owner.
`
`
`Patent No. 5,850,482
`________________________
`
`Inter Parte Review No. ____________
`
`___________________________________________________________
`
`Lin, “Codes with Multi-Level Error-Correcting Capabilities,” Discrete
`Mathematics 83 (1990), pp. 301-14
`
`Exhibit 1008
`
`

`

`Discrete Mathematics 83 (1990) 301-314 North-Holland 301 CODES WITH MULTI-LEVEL ERROR-CORRECTING CAPABILITIES* Mao-Chao LIN
`
`National Taiwan University, Taipei, Taiwan, ROC
`
`University of Hawaii, Honolulu, Hawaii 96822, USA
`
`Received 29 December 1987 Revised 29 August 1988 In conventional channel coding, all the information symbols of a message are regarded equally significant, and hence codes are devised to provide equal protection for each information symbol against channel errors. However, in some circumstances, some information symbols in a message are more significant than the other symbols. As a result, it is desirable to devise codes with multi-level error-correcting capabilities. In this paper, we investigate block codes with multi-level error-correcting capabilities, which are also known as unequal error protection (UEP) codes. Several classes of UEP codes are constructed. One class of codes satisfies the Hamming bound on the number of parity-check symbols for systematic linear UEP codes and hence is optimal. 1. Introduction In conventional channel coding, all the information symbols of a message are regarded equally significant, and hence redundant (or parity-check) symbols are added to provide equal protection for each information symbol against channel errors. However, in some occasions, some information symbols in a message are more significant than the other information symbols in the same message. Therefore, it is desirable to devise coding schemes which provide higher protection for the more significant information symbols. Suppose a message from an information source consists of m parts, each has a different level of significance and requires a different level of protection against channel errors. An obvious way to accomplish this is to use a separate code for each message part and then time share the codes. The redundant symbols of each code are designed to provide an appropriate level of error-correcting capability for the corresponding message part. This encoding scheme requires a separate encoder and decoder pair for each code. A more efficient way is to devise a single code for all the message parts. The redundant symbols are designed to provide
`
`m
`levels of error protection for
`m
`m
`
`levels of * This research was supported by NSF Grant DCI-8418248-01 and NASA Grant NAG 5-407. 0012-365X/90/$03.50 0 1990 - Elsevier Science Publishers B.V. (North-Holland)
`
`Apple Inc. Exhibit 1008 Page 1
`
`Shu LIN
`parts of a message. It has been proved that a single code with
`

`

`302
`
`M.-C. Lin, S. Lin
`
`error-correcting capability usually requires less redundant symbols than that required by time-sharing
`m
`m
`
`Cloud structure and the separation vector of a block code
`
`levels of error- correcting capability [l-8]. Moreover, a single code requires only one encoder and one decoder. This may be desirable in many situations. A code with multi-levels of error-correcting capabilities is known as an unequal error protection (UEP) code. UEP codes were first studied by Masnick and Wolf [9], than by other coding theorists [5,6, 10-201. In this paper, we investigate codes with multi-level error-correcting capabilities. Two classes of multi-level UEP codes are presented. Each code in the first class is obtained by combining codes of shorter lengths. We find that a subclass of such codes meets the Hamming bound on the parity-check symbols for systematic linear UEP codes. Each of the second class of codes is achieved by taking direct sums of product codes. The minimum distances of such codes are greater than those for the simple product codes of comparable dimensions, besides, some message bits have extra error protection. 2.
`Let (0, l}” denote the vector space of all n-tuples over the binary field GF(2). Let V and W be two subsets of (0, l}“. Let u and w denote two vectors from V and W respectively. We define the separation between V and W, denoted d(V, W), as follows: d(V, W) p min{d(v, w): u E V and w E W}, (1) where d(v, w) denotes the Hamming distance between v and w. Clearly the separation d(V, W) between V and W is simply a measure of distance between the two sets, V and W. Let r be a vector in (0, l}“. Then it is easy to show that the separations between {r}, V and W satisfy the following triangle inequality, d[{r}, V] + d[{r], WI 3 d(V, W). (2) Consider a message space A4 which is the product of
`let xi denote a message from the message space Mi. Then the product space M consists of the following set of m-tuples, M = {(xl, xz> . . . , n,,J:xiEMifor lSi<m}. (3) Let C be a binary block code of length IZ for the product message space M. Let u(x1, x2, . . * , x,,J denote the codeword for the message (x1, x2, . . . , x,) from M. Let u be a specific message in M,. Consider the following subset of codewords in C, Q,(a)= (~(~17.. . ,xi-1, a,xi+~j.. . 7 x,,J:x,~M~for 1SjSm andj#i}. (4) This set Q,(a) is called an i-cloud of C corresponding to the message a in Mi.
`
`m
`component message spaces, Ml, M,, . . . , M,,,. For 1 s i =S
`m,
`
`Apple Inc. Exhibit 1008 Page 2
`
`separate codes with the same
`

`

`Codes with multi-level error-correcting
`
`capabilities
`
`303
`
`: U, b E Mi
`
`b}.
`
`(5)
`
`There are lMil i-clouds in C corresponding to ]Mil messages in Mi. These i-clouds form a partition of C. For two distinct i-clouds, Qi(U) and Qi(b), the separation between them is d(Qi(a), Qi(6)). Then we define the minimum separation among the i-clouds of C as follows: si A min{dQi(a), Qi(b))
`Si = min{d[u(xl, . . . , Xi, . . . , X,), U(X;, . . . , Xl, . . . , XL)] : q,x;EMIforl~Z~mandxi#xl}. Geometrically, we may view that the code C consists of [Mil i-clouds, where any two i-clouds are separated by a distance at least si. This distance structure of i-clouds determines the level of error protection for component message Xi. The m-tuple, sp (Sl, 32, . . . ? L), is called the
`
`M=M,xM,x..
`
`separation vector
`* x Mm.
`
`This separation vector determines the levels of error protection for the m component messages, x1, x2, . . . , x,. We readily see that the minimum Hamming distance of C is dmin = min{s, : 1s
`are ready to show that the minimum separation Si of the i-clouds of a block code C determines the level of error protection (or error correction) for the ith component message Xi from
`
`Now we
`
`Mi.
`
`i G m}.
`
`Mi
`
`To do this we devise a nearest cloud decoding algorithm for which each component message is decoded independently. Suppose a codeword u is transmitted and a vector r is received. To decode the ith component message, we compute the separation between {r} and every i-cloud. Let Q,(u) be the i-cloud such that for any q E
`and Xi #a. Then the ith component message is decoded into a. The ith component message contained in r will be decoded correctly provided that there are ](si - 1)/2] or fewer transmission errors in r. To see this, let 21 = v(q, x2, . . . ) x,) be the transmitted codeword. For xl #xi, it follows from (2) that d[{r}, Qi(xi)l +
`
`d[{rIl, Qi(xr)] 2 d[Qi(xi), Qi(r,>].
`Since d[Qi(xi)t Qi(xi>] 2 Si
`and d(r, V) 3 d[{r}, Qi(Xi)], we have d[{r},
`Qi(xi)] 2 si - d(rt v)*
`
`(6)
`
`(7) If there are tj = ](Si - 1)/2] or fewer transmission errors in r, then d(r, u) c ti. It follows from (6) and (7) that d[{r}, Qi(x)] s ti and d[{r}, Qi(xl)] > ti. Hence, d[{r>,
`
`Qi(xi>] < d[{r), Qi(xzf)] f
`or q #xi. Thus, the decoding algorithm described above results in the correct i-cloud, Qi(Xi), and hence the correct component
`
`Apple Inc. Exhibit 1008 Page 3
`
`and u f
`It follows from (l), (4) and (5) that
`of the block code C for the product space
`

`

`304 M.-C. Lin, s. Lin message xi. However, if there are more than fi errors in the received vector r, the
`inequality 4(r), Qi(xi)] < 4(r), Qi(xi)] f
`or xi #xf may not hold. As a result, the ith component message is decoded incorrectly into some xi #xi. Theorem 1 characterizes the multi-level error-correcting capabilities of a block code.
`
`spaces,
`the product of m message
`for
`be a block code
`1. Let
`Theorem
`M,,,. Lets = (s,, s2,
`be the separation vector of C. Then, for
`MI, M,,
`the
`component message contained
`in a received vector can be
`i urn,
`correctly decoded provided
`that the number of transmission errors in the received
`vector is l(Si -
`
`. . . , s,,,)
`
`1)/2] or less. A code C with a separation vector s = (sl, s2, . . . , s,) is called a (t1, fz, . . . , t,)-error-correcting code where ti = L(si - 1)/2] for 16
`
`i s m
`and is the error correcting capability of the code for the ith component message xi. If
`
`t1, t2,
`
`. . * , t, are all distinct, then C provides m levels of error-correcting capabilities, one for each component message. In this case, C is called a m-level error-correcting code or a m-level UEP code. Without loss of generality, we assume that s1 > s2 2 . . * 2 s, throughout of this paper. The concept of separation vector was first introduced by Dunning and Robbins [13]. The separation vector defined in this paper is a generalization of Dunning and Robbins’, which applies for either linear or nonlinear codes. Note that the minimum separation si for the i-clouds depends on how a code is partitioned into the i-clouds. Different encoding (or mapping) of
`
`M
`
`onto C yields different partitions of C. As a result, the separation vector of C depends on the encoding mapping.
`
`3. Direct-sum
`
`codes for unequal error protection
`
`An approach for constructing multi-level UEP codes is to take direct-sums of linear component codes. For 1 G
`i s m,
`(n, ki)
`linear block code for the message space
`Mi = (0,
`i Zj, we
`require that Ci n Cj contains only the all-zero n-tuple 0. Let V(Xi) denote the codeword in C, for the message xi E
`
`Xl,
`
`x2,
`
`. . . 7 x,)
`
`Mi.
`(n, k)
`Let C be the direct-sum of Ci, CZ, . . . , C,, denoted C = C, @ C2 @ . . . @ C,. Then C is an
`M=M,xM,x-.-xM,,,
`k=k,+k,+-.-+k,.
`M,
`For any message (
`
`the corresponding codeword is n(x,, x2, . . . ) x,) = V(X,) + u(x2) + * * . + u&J. (8) Let {j1, j2, . . . , jr} be a subset of (1, 2, . . . ,
`
`m}.
`. . . f jl) = Cj, @ Cj, @ ’ * . @ Cj,.
`
`C(j1,
`
`j2,
`
`Then C(ji, j2, . . . , jl) is a subcode of C. An i-cloud of C for the component
`
`Apple Inc. Exhibit 1008 Page 4
`
`C
`. . . ,
`1 s
`ith
`let Ci be a binary
`l}“‘. For
`linear code for the product message space
`where
`in
`Consider the direct-sum,
`

`

`Codes with multi-level error-correcting
`
`capabilities
`
`305
`
`message x, from Mj is simply the following set: Q(xJ = u (xi) G.3 C(l, . . . ,
`i -
`i +
`1, . . . , m). The vector v(q) is in the i-cloud Q,(q) and is called the center of Q&q). A vector in Qi(xi) is of the form v(q) + w, where w E C(l, . . . ,
`1 > . . . 9 ml. Let w(u) denote the Hamming weight of the vector V. Since d(u, u) = W(V + u), the minimum separation of the i-clouds of C is Si = min{w[u(x,,
`
`i -
`
`i +
`
`. . . , Xi, . . . , X,)]
`
`:Xi ZO}.
`
`Theorem 2. Consider an (n, k) linear code C which is the direct sum of codes
`CI, C*, . . . 7 C,,,, where Ci is an (n, kj) linear code for the component message
`space Mi = (0,
`for
`i S m.
`If the minimum weight of codewords
`in
`is at least di and d, 3 d2 2
`d,,,, then C is an
`m)
`C-C(i+l,i+2,.
`m-level error-correcting
`code
`for
`the product message space M = M, X M2 X
`. . .M, with separation
`vector
`s = (sl, s2,
`where
`si sdi
`for
`i =
`m.
`
`Proof.
`
`C(i +
`
`i + 2,
`
`m),
`
`the corresponding component message x1, x2, . . . , xi are all zero. Each codeword of C, U(XI, . . . ) xi, . . . , x,) with xi # 0, is not in
`
`m)
`i + 2,
`C(i +
`and hence has weight at least
`di.
`
`The proof then follows from (9). 0 Theorem 2 describes a method of constructing multi-level UEP codes by taking direct sums of linear component codes. With this method, we are able to construct two classes of UEP codes. 4.
`
`Construction of linear multi-level UEP codes by combining
`
`shorter codes
`
`Ho = [Hz&tTblT
`k, + r)
`Ha,
`(n,, k,)
`Hob
`Ha
`k, - r) x n,
`r x n,
`k,) x n,
`is an (n, -
`Hbb
`H, = [H&H&IT
`matrix and T denotes the transpose operation. Let
`kb + r)
`(nb, kb)
`be the parity-check matrices of an (nb,
`H bb
`Hbo
`linear code C, respectively, where
`(nb - kb - r) X nb
`r x nb
`Hb
`(n, + nb, k, + kb + r)
`kb) X nb
`
`N,, 0 H= Ha, &a ,
`
`1 0 &b
`
`(10)
`
`Apple Inc. Exhibit 1008 Page 5
`
`1,
`1,
`(9)
`l}“’
`1 =Z
`. . ,
`* . .S
`. . . , s,),
`1,2, . . . ,
`Note that for each codeword in
`1,
`. . . ,
`1,
`. . . ,
`Let H,, and
`be the parity-check matrices of an (n,,
`linear code C,, and an
`linear code C, respectively, where
`matrix,
`is a
`matrix,
`is an (n, -
`and
`linear code C,, and an
`is an
`matrix,
`is a
`matrix and
`is an (nb -
`matrix. Consider the
`linear code C with the following parity-check matrix,
`[
`

`

`306
`
`M.-C. Lin, S. Lin
`
`k, + kb)
`
`where 0 represents a zero matrix of proper dimension. Let C2 be the (n, + rrb, k,) subcode of C such that each codeword in C2 is the concatenation of a codeword in C, and the all-zero nb-tuple. Let C3 be the (n, + nb, kb) subcode of C such that every codeword in C3 is the concatenation of the all-zero n,-tuple and a codeword in Cb. Since C2 @ C3 = C(2, 3) is an (n, + q,,
`subcode of C, there must exist r linear independent codewords in C - C(2, 3). These r linear independent codewords span an (n, + nb, r) linear subcode C, of C. We readily see that C is the direct sum of C,, C2, and C,, i.e. C = C, @ C2 @ C3. Let
`examine the distance structure of C. Any codeword v in C can be expressed as v = (v,, vb) where v, is an n,-tuple and vb is an nb-tuple. Then (v,, vb) * HT = 0. This if@ieS that v, * H;f, = 0 and v, . H&, = 0. Thus, v, is a codeword in C,, and vb is a codeword in Cbb. Consider a codeword (v,, vb) in C - C(2, 3). Then, v, f 0 and vb f 0. Hence, the weight of any codeword v in C - C(2, 3) is at least
`
`db
`da,, dbb, d,
`be the minimum distances of C,,, Cbb, C, and C, respectively. Suppose
`da, + dbb 2 da 2 db. Now we
`
`da, + dbb.
`
`For any codeword (v,, 2)b) in C - C3, either it is in C2, or both v, and v, are not zero. For the former case, the weight of the codeword is at least
`da.
`For the latter case, the weight of the codeword is at least
`d,, + dbb 2 d,,
`da, + dbh.
`the minimum weight of codewords in C - C3 is
`d,.
`da, + dbb 3 d, Zz db, we
`can easily see that the minimum weight of C is
`db.
`da, + dbb 2 da 2 db,
`the code C with the parity-check matrix H of (10) is a linear block code for the product message space M = (0, 1}’
`X
`X
`(0, l}“” with separation vector s = (si, s2, sg) where s1 3
`d,, + dbb, s2 2 d,
`db.
`A
`generator matrix for the code C with a parity-check matrix of the form given by (10) can be formed easily. Let G, and Gb be the generator matrices for the (IZ,, k,) code C, and (&,
`
`kb)
`code Cb respectively. Let [G;fG;fhlT and [GEG;f,lT be generator matrices for the (IZ,,
`k, + r)
`kb + r)
`(k, + kb + r) X (n, + rtb)
`code Cbb respectively. Then the following
`
`matrix, (11) is a generator matrix for C where [G,,Gbb], [G,O] and [OGb] generate the (n, + $,, r) code Ci, the (n, + ltb,
`code C3 respectively. In the following, we present two special classes of linear UEP codes with parity-check matrices of the form given by (10). Let LY be a primitive element in GF(2m). Every nonzero element in GF(2m) can be expressed as a power of (Y and can be represented by a nonzero m-tuple over GF(2) (in column form). For any nonnegative integer
`
`k,)
`
`kb)
`
`1,
`1
`let pi, p2, . . . , &p+l_p represent all the (m + l)-tuples over GF(2) (in column form) for which the last
`
`Apple Inc. Exhibit 1008 Page 6
`
`and
`Since
`Since
`It follows from Theorem 2 that, for
`(0, l}“a
`and s3 =
`code C,, and the (&,,
`code C2 and the (n, + Itb,
`components are not all zero.
`

`

`(12)
`Codes with multi-level error-correcting capabilities 307 Consider the binary code C associated with the following parity-check matrix: 1 & a* . . . (y*m-* : 0, 0, * *. 0, Hz [ 1 (y3 (y6 . . . &*“‘-2) ;. . . . . . . . . . . . . . . . . . . . ,
`0, 0, 0, ' * * 0, i p1 p* * *. /3p+'-*m
`1
`where each power of a is represented by an m-tuple in column form, OI is a column of 1 zeros and 0, is a column of m zeros. The matrix H consists of 2m + I rows and 2”+’ - 1 columns, and hence the code C associated with H is a (2m+l- I, 2m+-r - 2m - 1 - 1) linear code over GF(2). Note that the H matrix has the form given by (10) where Ha = H,, [
`I[ 1 (Y a3 **a (y2m-2 = &b 1 a3 a6 . . . a3w-2) I & =
`
`= [PI
`
`P2 . . * P2m+r-2ml H,,=[l LY a3 . . . a2m-2] Hbb = SOme 1 x (??+I - 2”) matrix which has no zero column. The codes, C,, and C,, generated by parity-check matrices Ha, and H, are simply the Hamming and double-error-correcting BCH codes of length 2” - 1 respectively. Hence, d,, = 3 and da = 5. The code Cb generated by the parity- check matrix H, is a shortened Hamming code with minimum distance db = 3, and the code Cbb generated by the parity-check matrix &, has minimum distance dbb = 2. As a result, C is a code for the product message space M = h4, X Al2 X M3 where M1 = (0, l}“, M2 = (0, 1}2m-*-1 and M3 = (0, 1}2m+‘-2m--m--[. The separa- tion vector of C is s =(sl, s2, s3) where slbd,, +dbb =5, s2Sd, =5, and s3 = db = 3. For this code, the first 2” - m - 1 message bits of a message are protected against up to 2 random errors while the next 2m+’ - 2” - m - I message bits against any single error. Hence, it is a (2,1)-error-correcting code. For m = 0, C becomes a conventional single-error-correcting Hamming code of length 2’ - 1. For I= 0, C reduces to a primitive double-error-correcting BCH code of length 2” - 1. For m = 1, C is equivalent to Boyarinov-Katsman UEP code [16]. The code C can be transformed into systematic form with identical two-level error-correcting capability. A lower bound (equivalent to the Hamming bound for single-level error- correcting codes) on the number of parity-check bits for systematic linear UEP codes has been derived by Masnick and Wolf [9], and van Gils [20]. It follows from Theorem 2 of [9] that, for a two-level (tl, t,)-error-correcting code of length IZ, the number of parity-check bits satisfies the following inequality: (13)
`
`Apple Inc. Exhibit 1008 Page 7
`
`

`

`308 M.-C. Lin, S. Lin Consider a two-level UEP code with the following parameters: k1 = 2” - m - 1, t, = 2, t2 = 1. It follows from the Hamming bound that n=y+l-l, given by (13) 2”-k Z 2-l * {22m+‘+1 - (2m) . 2m+1 - (2” - 2m + 1) .2” - (m’ - m) + 2) = 2-l . {22m+l + A}, (14) where A = 2m+‘(2m-’ - 2m) + 22m(2’-’ - 1) + (2m - 2) .2” + (2” - m2 + m + 2). For either m = 3 and I = 3, or m 3 4 and 13 1, the number
`
`A
`
`is greater than zero. Hence, it follows from (14) that n - k > 2m + I - 1. This is to say that the number of parity-check symbols required for a two-level linear systematic UEP code with parameters, n = 2m+1 - 1, kI = 2” - m - 1, ti = 2 and t2 = 1 is at least 2m + 1. The two-level UEP code given by the parity-check matrix H of (12) has exactly 2m + 1 parity-check symbols. Hence, under the condition that m = 3, I = 3, or m 2 4 and 12 1, the code meets the Hamming bound of (13) and hence is optimal. A list of codes with lengths 63 and 127 is given in Table 1 for various m and 1, where k,=2”-m-1 and kz=2”‘+‘- 2” - m - 1 and k = kI + kz. For example, there is a (63,52) code which provides protection for the first 26 message bits against up to 2 random errors and protection for the next 26 message bits against any single error. The second class of linear UEP codes with parity-check matrices of the form given by (10) is specified by the following submatrices: 1 1 1 *** 1 - & = [(), 1 $-l . . . (,t-1)2m-2] Hba = [l (u2.‘-’ . . . ((Y~-~)~“-‘] (15) 1 (y~-3 . , . (g9-3)2=2 . . & = ’ ’ 1 a3 . . . 1 (y . . . (y2m-2 where s s t. Note that H,, and H, = [H~$S~~]’ are parity-check matrices of an extended (t - 1)-error-correcting and an extended t-error-correcting primitive BCH codes of length 2” respectively. Also note that H,, and Hb = [Hz&f,,]’ are parity-check matrices of an (S - 1)-error-correcting and an s-error-correcting primitive BCH codes of length 2” - 1 respectively. We require that H,, and Hba have the same dimension, i.e. azrel and (Y~-~ from the same subfield of GF(2m). The submatrices of (15) arranged in the form of (10) generate a linear UEP code with a separation vector s = (si, s2, s3) where s1 2 2(t + s) - 1, s2 2 2t + 2 and
`
`Apple Inc. Exhibit 1008 Page 8
`
`

`

`Codes with multi-level error-correcting capabilities 309
`
`Table 1. A list of (2, I)-error-correcting codes.
`Codes of length 63
`Codes of length 127
`
`m 1 k k, k, 0 6 57 0 57 2 4 55
`
`1
`3 54 4 50
`2 53 11 42
`1 52 26 26
`0 51 51
`0
`
`3
`4
`5
`6
`
`m 1 k k, k, 0 7 120 0 120 2 4 118
`
`1 117
`4 113
`117
`4
`11 105
`116
`3
`26
`89
`115
`2
`57
`57
`1 114
`0
`113 113
`0
`
`3
`4
`5
`6
`7
`
`s3 = 2~ + 1. The code has at most m(t + s - 1) + 1 parity-check symbols. It protects the first k, = m message bits against s + I - 1 or fewer errors, the next kz = 2” - mt - 1 message bits against t or fewer errors, and the other message bits against s or fewer errors. Example 1. Let m = 5 and t = s = 2. Let (Y be a primitive element in GF(25). Consider the code generated by the following parity-check matrix: 1 [ 05 1 1 1 -0. 1 0, 0, 0, . . * 0, 1 (Y (Y2 . * - H= a30 05 05 OS - * . 0, (& 1 (y3 (y6 . . . (p 1 a3 &p . . . . (ym 05 0, 0, 0, * . . 0, 1 (y @2 . . . (y3”
`1
`
`(0, l}*l with separation vector at least (7,6,5). Note that there is a (63,45) triple-error- correcting BCH code and a (63,51) double-error-correcting BCH code.
`
`x
`
`x
`
`5. Direct sums of product codes
`
`Let V be an (N, K) linear code with minimum distance D, and W be an (n, k) linear code with minimum distance d. Let V CO W denote the product of V and W [21]. Then, V CO W is an (Nn, Nk) linear code with minimum distance Dd. A codeword in V 8 W can be arranged as an IZ
`
`x N
`
`array in which every row is a codeword in V and every column is a codeword in W. For a nonzero code array in V @ W, there are at least D nonzero columns and each nonzero column has at least d nonzero components. Hence, the weight of any nonzero code array in V 60 W is at least Dd. Product codes are capable of correcting both random and burst errors [21]. Now, we consider direct sums of certain binary product codes which provide burst error protection in addition to the two-level random error protection.
`
`Apple Inc. Exhibit 1008 Page 9
`
`54
`It is a (63,47) UEP code for the message space M = (0, l}”
`(0, l}*l
`

`

`put? IQ saxn?Js~p uInw!u~w
`Yl!M
`ZQ
`
`pue IQ c Q keys xap s! 11 *zA ulA 30 axn2qp wnuI~u!tu aq3 aq a IaT .z~ put2 l;i yloq30 apbqns .waug E S! “A ulA alouap '"/i put? IA 30 uoyDasIa)u! ay,L .1CIa+padsal
`
`*ZQ c Q
`
`@IO aAl?q zM@zA pUe 'M @I/i ‘(0) ='A @IM aXUS +?!a aXIE?JS!p urnru!u~w ql!M apoa leaug (!y!x ‘24~) uc sl !M @ J~ )Dnpold ayl '~‘1~ j JOT aq p IaT .apoD leau!I (“3 + Iy ‘24) ue si ‘ZM @ 1~ = M palouap ‘Z/M pue 1~ 30 tuns vaxp ayl ‘uagL ‘(0) = z~ u ‘4 v2y1 azunsse aM *dIay~adsa~ Zp pue Ip sax.nit)s!p tunuytu qJ!M sapo:, cnzau!I h?u!q (Z?/ ‘U) ue pue (‘y ‘U) ul? aq zM pUE? 'M Ia? 'zA +IA 30 axwwp t.unugur at.p aq Q Ia? .z~ put2 IA 30 urns IDanp ar.p SIZA +1/i uayt ‘(0) =z~ UIA 31 'z~ pue 1~ yloq30 apoxadns e pue .waug S!ZA +'A Apeal ‘Ias %.1!~01103 ayl alouap z~ + I/i )a?
`
`apO3 OXJZ aq)
`
`*zM@lM
`31 'Z&j @z/i@lM @IA =3 u! 3 Awn2 ape:, olazuou e 30 l@aM aql lapy_Io3 aM
`MEN
`(3)~
`uayl
`‘1~ @IA
`33
`
`‘snqL 'ZA USA uy proMapo:, e aq lsntu n uaqL =n lolsaa uya:, " e 01 IeDyuapr pue ayy? ale % pue b u!
`SMO.I
`aseal me a.w alaq) ~eyl sagdw! " s!q~
`*QC((~)M
`Q
`
`II! plOMapO:, I? S! 3 U! KIUIn~O:, IjDlZa pIIt2 'z/i +'A II! pJOMapO9 t? Si 3 h.IC III MO1 Y3k?TJ 'ZCB +b =3 'a.! ‘ZM Bz/i II! z3 hr12 apO3 I? puk? IM @IA u! '3 lCe.~.w ape:, e 30 urns s! 3 u! 3 lie1112 apoD v *apoD .wau!l (Zyzx+Iyly ‘UN) ue sl3 uaqL OzM Bz~ pue TM ~~JIA 30 tuns lDal!p aql aq 3 Ia? wouu.uo3 u! liege
`olazuou ay$ 111~ asoddns '1 asv3 .palap!suoD aq 01 sase3 In03 ale alay ‘Za+1D=3 30 @$aM aql auyra4ap 0~ 'ZM @ZA u! 9 lCw.~e apo3 0Iazuou e pue 1~ 81~ u! '3 liw.w ape:, olazuou t2 30 urns ayt s! 3 uaylZMmz~ u! IOU 1~ 8,'~ u! layl!au s! 3 31 'ZpZQe(3)M uayl ‘zMgbz~ 33 31 .IptQe
`aloN 'Q jseal IF! @!aM sey pw Z/i +1/i u! ploMapo:, olazuou I? s! Zn +%f uaqL %x+$x alarIM ‘ZA u! %I plomapo:, awes 01 le3yuapj an2 Z3 u! SMOI o.xazuou atp 11x2 pue I(i UT In proMap au.xos 01 Iwguap! ale 9 u! SMOJ olazuou atp 11" )eq$ asoddns '11 aszg .pge(3)~ ‘qnsal e sv 'p Iseal me @!aM seq suurnIo3 asayl30 yxa axug '3 Aw~e u! suwnIo:, olazuou
`~~~3 ar[L ‘p JseaI je @aM sky pue ZM @IM ul ploMapo9 olazuou e s! uunyo3 e yxis 'z3 UI uwn~o~ olazuou e pue I3 UI uuuyo~ olazuou le 30 wns aql s! uwnlo:, qxa )w.p S!D u! suunyo:, olazuou 30 add; puo3as ayL '{Zp‘~p}ug~ lseal le $y%!aM seq3 II! adh JSI~ ayl30 wunlo:, olazuou e ‘alo3alaqL *ZM u! ploMapo3 olazuou e 10 IM u! p.IoMapor, Olazuou e _Iay)!a s! uuIn~o3 e 4xyj 'ZD II! uwnlo:, Olaz e pue I3 u! uurnlo3 o.xazuou e 30 tuns ayl~o 9 u! uwnlo~ 0Jazuou e pun! 13 u! uwnIo3 olaz e 30 urns aql layl!a s! ut.unloD qxa ~eyl s! adli) JS+J ayL '3 II! suwnlo~ olazuou 30 sadA 0~1 ax alayL 'zQe
`
`)eql
`
`(%I)M
`
`(h)~
`
`%a)~
`
`Isea le a.w alay uayL .QcjaIaqM 3 II! suwnlor, olazuou l-adlC$30 IaquInu ay, aqJ $a? '3 uy suwnlo:, olazuou I-adh
`
`Q
`
`ZQ +‘a)]
`
`ley3
`
`Apple Inc. Exhibit 1008 Page 10
`
`aq~ uo punoq ~a~01 e a3ua~ '3 u! sutunlo~ 01azuou Z-adL$ Lz/(j-
`$seal be ale alatp ~ey$ saydy Q c(Zn +
`pue IQ<
`sap03 .wau!I lileu!q (Zx ‘N) pue (‘a ‘N) aq z/I pUl? '(i la?
`

`

`Codes with multi-level error-correcting capabilities weight of c is 311 = D * min{d,, d,} + [(DI + Dz -f)/2] . d. Case 111. Suppose that there are two nonzero rows u1 and V; in c1 such that v1 #vi. Then there are at least D1 + [D,/2] nonzero columns in cl. This implies that there are at least D, + [D,/21 nonzero columns in c. Each of these nonzero columns is a nonzero codeword in W, @ W, and has weight at least d. Thus the weight of c is at least {DI + [D,/2] } - d. Case IV. Suppose that there are two nonzero rows, y and u; in c2 such that y #vi. It follows the same argument as that in Case III that w(c) 2 {D2 + ID,/21 > . d. Denote D * min{di, d,} + [(DI + 4 - D)/2] . d by A, {DI + [D,/2]} - d by A, and (4 + [4/2] } . d by A,. Summarizing the above results, we have the following weight structure of a nonzero code array c in C = VI @ WI @ V, 8 W,: (1) For c E VI @ W,, w(c) 2 DIdI. (2) For c E V, @ W,, w(c) 2 D2d2. (3) For c $ VI 8 WI and c 4 V, @ W,, w(c) 2 min{Dd, A, A,, A,}. From the above weight distribution, we see that the weight of a nonzero code array c in VI G0 WI @ V, 8 W, is at least min{D*d,, D2d2, bd, A, AI, A.,}. Suppose min{D,dl, bd, A, AI, A,} > D2d2. Then we have the following weight structure of a nonzero code array c in VI 8 WI @ V, @ W,: (1) For c E V, 8 W,, w(c) 3 D,d,. (2) For c E VI 8 WI @ V, @ W2 - V, @ W,, w(c) 2 min{D,d,, L?d, A, Ai, AZ}. It follows from Theorem 2 that C = V, 8 W, @ V, 8 W2 is a linear block code with a separation vector s = (sl, sJ, where s1 2 min{D,d*, bd, A, A,, A2}, s2 2 D2d2. (16) The message space for C is M = (0, l}K1kl x (0, l}@?. Example 2. Let VI and V, be two equivalent (7,4) Hamming codes. Let W, and W, be the (7,l) and (7,3) BCH codes over GF(2) respectively. Then, WI @ W, is a (7,4) Hamming code. The minimum distances of VI and V, are D1 = 3 and D2 = 3 respectively. The minimum distances of WI, W,, and W, @ W, are dI = 7, dz = 4 and d = 3 respectively. Note that VI n V, is the (7, 1) binary code with minimum distance D = 7 while V, + V, is the (7,7) binary code with minimum distance D = 1. Thus, A = 13, A, = 15, A, = 15, bd = 21, DIdI = 21 and D2d2= 12. Note that N =7, K1 = K2=4, n =7, k, = 1, k,=3. Since min{D,d,, bd, A, AI, A,} = 13 2 D2d2 = 12, we see that VI 69 WI @ V, 8 W, is a
`
`Apple Inc. Exhibit 1008 Page 11
`
`

`

`312 M.-C. Lin, S. Lin two-level UEP (49,16) binary code for the message space M = Mr x M2 with separation vector s = (sl, sZ), where M1 = {0,1}4, M2 = (0, l}‘*, si 2 13, s2?= 12. We may compare this code with the product code of two (7,4) BCH codes with minimum distance 3, which is a (49,16) single-level binary code with minimum distance only 9. Direct sums of product codes for unequal error protection was first studied by Boyarinov and Katsman [16]. The lower bound on the separation vector given by (16) is better than the bound derived by Boyarinov and Katsman. Now we present a special class of direct sums of product codes. Let & and /I be two different primitive Nth roots of unity. Let VI be an (N, K,) binary cyclic code which has a; LX*, . . . , a?’ and their conjugates as zeros. Let V2 be an (iV, K2) binary cyclic code which has /I, /3*, . . . , P2r and their conjugates as zeros. Clearly, VI and V2 are equivalent codes. Hence, K1 = K2 = K and Dr = D2 2 2t + 1, where D1 is the minimum distance of VI and 4 is the minimum distance of V,. If the set {(pi)2m:i= 1, 2, . . . , 2t, m is an integer} contains {&*r+l, a*[+*, . . . ) cY*t+a} as a subset, then VI f~ V2 includes cr, (Y*, . . . , a~*‘+~ as zeros. Thus, either the minimum distance b of VI fl V2 is at least 2t + 2s + 1 or VI fl V, = (0) which is the case that VI f~ V2 contains all the & as zeros. If the set {((Yi)2”:i = 1, 2, . . . , 2t and m is an integer} contains {/I, p*, , . . , p*“} as a subset, then VI + V2 contains p, /3*, . . . , p2u as zeros. Thus, D, the minimum distance of V, + V2 is at least 2u + 1. With the above codes VI and V,, if min((2t + l)d,, (2t + 2s + l)d, A, Ai, A,} 2 (2t + l)d2, the direct sum VI 60 WI Q3 V, 8 W, is an (Nn, K(k, + k2)) code with separation vector s = (sr, s2) where s1 2 min((2t + l)dl, (2t + 2s + l)d, A, A,, A,}, s* 2 (2t + l)d*, A = (2~4 + 1) - min{di, d2} + (2t - u + l)d, A1 = A* = (3t + 2)d. Example 3. Let (Y be a primitive element in GF(25). Let VI be a (31,21) BCH code with minimum distance D1 = 5, which contains a; a3 and their conjugates as zeros. Let V2 be a (31,21) BCH code with minimum distance D2 = 5, which contains a’, (a3)3, and their conjugates as zeros. Since (Y~ is a conjugate of (Ye, V,
`
`n
`
`V, includes a, cx3, (Ye, and their conjugates as zeros. Since VI fl V, # {0}, the minimum distance B of VI n V2 is at least 7. Furthermore, the minimum distance D of V, + V2 is at least 3, since a3 is a zero for both VI and V,. Let WI and W, be (7,l) and (7,3) BCH code over GF(2). Thus, the minimum distance of WI is d1 = 7 and the minimum distance of W2 is d2 = 4. Furthermore, WI @ W2 is a (7,4) BCH code over GF(2) with minimum distance d = 3. Thus, t = 2, s = 1, u = 1, A =24, A1 =A, =24, bd ~21, D,d, =35, and D2d2 =20. Note that N =31, n = 7, kI = 1, k2 = 3, K1 = K2 = 21. Since min{D,d,, bd, A, A,, A2} 2 212 D2d2= 20, VI @ WI @ V2@ W2 is a (217,84) binary two-level UEP for the
`
`Apple Inc. Exhibit 1008 Page 12
`
`

`

`Codes with multi-level error-correcting
`
`capabilities
`
`Table 2. Some direct sums of product codes for unequal error protection 313
`
`N Ki D, D
`
`b
`
`n
`
`k,
`
`k,
`
`d,
`
`d,
`
`d Nn K,k, K,k,
`
`s,
`
`s2
`
`t,
`
`15 10 4 2 6 17 1 8 17 6 5 255 10 80 27 24 30 15 10 4 2 6 7 1 3 7 4 3 105 10 30 17 16 15 15 10 4 2 6 15 1 10 15 4 3 225 10 100 17 16 15 15 10 4 2 6 15 1 6 15 6 5 225 10 60 27 24 30 15 10 4 2 6 15 2 5 10 7 5 225 20 50 29 28 30 31 21 5 3 7 15 1 10 15 4 3 465 21 210 21 20 31 31 21 5 3 7 15 1 6 15 6 5 465 21 126 35 30 62 31 21 5 3 7 15 2 5 10 7 5 465 42 105 35 35 62 message space M = M, x iV& with separation vector s = (sr, s2) where MI = (0, 1}2l, M2 = (0, 1}63, s1 2 21, and s2 2 20. Note that the product code of a (7,4) Hamming code with minimum distance 3 and a (31,21) BCH code with minimum distance 5 is a (217,84) linear code with minimum distance 15 which is inferior to the (217,84) direct-sum code. Suppose we transmit each code array in VI 63 WI 63 V, C3 W, row by row. By a proof similar to that for simple product codes [21], it can be shown that the code VI C3 WI @ V, (23 W, can correct any error-burst of length up to N * [(d - 1)/2] in addition to the random-error-correcting capabilities represented by its separation vector. Consider the (217,84) binary code illustrated in Example 3. For this code 21 message bits of a message are protected against up to 10 random errors and any error burst of length up to 31, while the other 63 message bits of the same message are protected against up to 9 random errors