• IEEE
`
`Advancing Technology
`for Humanity
`
`DECLARATION OF GERARD P. GRENIER
`
`I, Gerard P. Grenier, am over twenty-one (21) years of age. I have never been convicted
`of a felony, and I am fully competent to make this declaration. I declare the following to be true
`to the best of my knowledge, information and belief:
`
`1. I am Senior Director of Publishing Technologies of The Institute of Electrical and
`Electronics Engineers, Incorporated ("IEEE").
`
`2. IEEE is a neutral third party in this dispute.
`
`3. Neither I nor IEEE itself is being compensated for this declaration.
`
`4. Among my responsibilities as Senior Director of Publishing Technologies, I act as a
`custodian of certain records for IEEE.
`
`5. I make this declaration based on my personal knowledge and information contained
`in the business records of IEEE.
`
`6. As part of its ordinary course of business, IEEE publishes and makes available
`technical articles and standards. These publications are made available for public
`download through the IEEE digital library, IEEE Xplore.
`
`7. It is the regular practice of IEEE to publish articles and other writings including
`article abstracts and make them available to the public through IEEE Xplore. IEEE
`maintains copies of publications in the ordinary course of its regularly conducted
`activities.
`
`8. The articles below have been attached as Exhibits A - B to this declaration:
`
`A. W. van Gils, "Two topics on linear unequal error protection codes:
`Bounds on their length and cyclic code classes" IEEE Transactions on
`Information Theory, Vol. 29, Issue 6, November 1983.
`B. U. Dettmar, et al. "Modified generalized concatenated codes and their
`application to the construction and decoding ofLUEP codes" IEEE
`Transaction on Information Theory, Vol. 41 , Issue 5, September 1995.
`
`9. I obtained copies of Exhibits A - B through IEEE Xplore, where it is maintained in
`the ordinary course of IEEE' s business. Exhibits A - B are true and correct copies of
`the Exhibits, as they existed on or about August 13, 2018.
`
`445 Hoes Lane Piscataway, NJ 08854
`
`IPR2018-1556
`HTC EX1051, Page 1
`
`

`

`10. The article abstracts from IEEE Xplore shows the date of publication. IEEE Xplore
`populates this information using the metadata associated with the publication.
`
`11 . W. van Gils, "Two topics on linear unequal error protection codes: Bounds on their
`length and cyclic code classes" was published as part of IEEE Transactions on
`Information Theory, Vol. 29, Issue 6. IEEE Transactions on Information Theory,
`Vol. 29, Issue 6 was published in November 1983. Copies of this publication were
`made available no later than the last day of the publication month. The article i
`currently available for public download from the IEEE digital library, IEEE Xplore.
`
`12. U. Dettmar, et al. "Modified generalized concatenated codes and their application to
`the construction and decoding ofLUEP codes" was published as part ofIEEE
`Transaction on Information Theory, Vol. 41 , Issue 5. IEEE Transaction on
`Information Theory, Vol. 41 , Issue 5 was published in September 1995. Copies of
`this publication were made available no later than the last day of the publication
`month. The article is currently available for public download from the IEEE digital
`library, IEEE Xplore.
`
`13. I hereby declare that all statements made herein of my own knowledge are true and
`that all statements made on information and belief are believed to be true, and further
`that these statements were made with the knowledge that willful false statements and
`the like are punishable by fine or imprisonment, or both, under 18 U.S.C. § 1001.
`I declare under penalty of perjury that the foregoing statements are tru5 an)Yrrect.
`Executed on /2/~ ;}c,-J,
`
`2&~ ~
`
`IPR2018-1556
`HTC EX1051, Page 2
`
`

`

`
`
`
`
`
`
`EXHIBIT A
`
`EXHIBIT A
`
`|PR2018-1556
`
`HTC EX1051, Page 3
`
`IPR2018-1556
`HTC EX1051, Page 3
`
`

`

`8/15/2018
`IEEE.org
`
`|
`
`
`|
`
`Two topics on linear unequal error protection codes: Bounds on their length and cyclic code classes - IEEE Journals & Magazine
`IEEE Xplore Digital Library
`
`IEEE-SA
`
`IEEE Spectrum
`
`More Sites
` Cart(0)
`
`Create Account
`
` Personal Sign In
`|
`|
`|
`|
`|
`
`|
`
` Back to Results
`
`Related Articles
`
`Modified majority logic decoding of
`cyclic codes in hybrid-ARQ systems
`
`The Weight Distributions of the Duals of
`Cyclic Codes With Two Zeros
`
`The Weight Distributions of Cyclic
`Codes and Elliptic Curves
`
`View All View All
`
`Institutional Sign In
`
`Browse
`
`My Settings
`
`Get Help
`
`Subscribe
`
`Browse Journals & Magazines > IEEE Transactions on Informat... > Volume: 29 Issue: 6
`
`Two topics on linear unequal error protection codes: Bounds on
`their length and cyclic code classes
`
`<< Results
`
`143
`Full
`Text Views
`
`1P
`
`atent
`Citation
`
`63
`Paper
`Citations
`
`Sign In or Purchase
`to View Full Text
`
`1
`Author(s)
`
`W. van Gils W. van Gils
`
`View All Authors
`
`Abstract
`
`Authors
`
`Figures
`
`References
`
`Citations
`
`Keywords
`
`Abstract: It is possible for a linear block code to provide more protection for selected positions in the input
`message words than is guaranteed by the minimum distance of the code. Linear codes having this property are
`called linear unequal error protection (LUEP) codes. Bounds on the length of a LUEP code that ensures a given
`unequal error protection are derived. A majority decoding method for certain classes of cyclic binary UEP codes
`is treated. A list of short (i.e., of length less than 16) binary LU... View more
`
` Metadata
`Abstract:
`It is possible for a linear block code to provide more protection for selected positions in the input message words
`than is guaranteed by the minimum distance of the code. Linear codes having this property are called linear
`unequal error protection (LUEP) codes. Bounds on the length of a LUEP code that ensures a given unequal error
`protection are derived. A majority decoding method for certain classes of cyclic binary UEP codes is treated. A
`list of short (i.e., of length less than 16) binary LUEP codes of optimal (i.e., minimal) length and a list of all cyclic
`binary UEP codes of length less than 40 are included.
`
`Published in: IEEE Transactions on Information Theory ( Volume: 29, Issue: 6, Nov 1983 )
`
`Page(s): 866 - 876
`
`DOI: 10.1109/TIT.1983.1056753
`
`Date of Publication: Nov 1983
`
`Publisher: IEEE
`
` ISSN Information:
`
`Sponsored by: IEEE Information Theory Society
`
`
`
`Authors
`
`References
`
`Citations
`
`Keywords
`
`Related Articles
`
`https://ieeexplore.ieee.org/document/1056753/
`
`1/3
`
`IPR2018-1556
`HTC EX1051, Page 4
`
`

`

`8/15/2018
`
`Two topics on linear unequal error protection codes: Bounds on their length and cyclic code classes - IEEE Journals & Magazine
`
`Back to Top
`
`Authors
`
`References
`
`Citations
`
`Keywords
`
`Related Articles
`
` Download Citation
`
`View References
`
` Email
`
` Print
`
` Request Permissions
`
` Alerts
`
`
`
`
`
`
`
`
`
`
`
` Download Citation
`
`View References
`
` Email
`
` Print
`
` Request
`
`Permissions
`
` Alerts
`
`
`
`Authors
`
`References
`
`Citations
`
`Keywords
`
`Related Articles
`
`Back to Top
`
`IEEE Account
`
` Purchase Details
`
` Profile Information
`
` Need Help?
`
`» Change Username/Password
`» Update Address
`
`» Payment Options
`» Order History
`» View Purchased Documents
`
`» Communications Preferences
`» Profession and Education
`» Technical Interests
`
`» US & Canada: +1 800 678 4333
`» Worldwide: +1 732 981 0060
`» Contact & Support
`
`|
`
`About IEEE Xplore
`
`
`|
`
`Contact Us
`
`
`|
`
`Help
`
`
`|
`
`Accessibility
`
`
`|
`
`Terms of Use
`
`
`|
`
`Nondiscrimination Policy
`
`
`|
`
`Sitemap
`
`
`|
`
`Privacy & Opting Out of Cookies
`
`A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity.
`© Copyright 2018 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.
`
`IEEE Account
`
`Profile Information
`
`Purchase Details
`
`Need Help?
`https://ieeexplore.ieee.org/document/1056753/
`
`2/3
`
` Download
`PDF
`
` Export to
`
`Collabratec
`
` Download PDF
`
` Export to Collabratec
`
`IPR2018-1556
`HTC EX1051, Page 5
`
`

`

`8/15/2018
`
`Two topics on linear unequal error protection codes: Bounds on their length and cyclic code classes - IEEE Journals & Magazine
`
`Other
`
`A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity.
`© Copyright 2018 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.
`US & Canada: +1 800 678 4333
`Worldwide: +1 732 981 0060
`
`https://ieeexplore.ieee.org/document/1056753/
`
`3/3
`
`IPR2018-1556
`HTC EX1051, Page 6
`
`

`

`866
`
`_
`
`IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. IT - 29, NO. 6, NOVEMBER 1983
`
`Two Topics on Linear Unequal Error
`Protection Codes: Bounds on Their
`Length and Cyclic Code Classes
`
`WIL J.VAN GILS, MEMBER,IEEE
`
`is possible for a linear block code to provide more protec-
`Abtract-It
`tion for selected positions in the input message words than is guaranteed by
`the minimum distance of the code. Linear codes having this property are
`called linear unequal error protection (LUEP) codes. Bounds on the length
`of a LUEP code that ensures a given unequal error protection are derived.
`A majority decoding method for certain classes of cyclic binary UEP codes
`is treated. A list of short (i.e., of length less than 16) binary LUEP codes of
`optimal (i.e., minimal)
`length and a list of all cyclic binary UEP codes of
`length less than 40 are included.
`
`I.
`
`INTRODUCTION
`
`M OST error-correcting block codes considered in the
`
`literature have the property that their correcting
`capabilities are described in terms of the correct reception
`of the entire message. These codes can successfully be
`applied in those cases where all positions in a message
`word require equal protection against errors.
`However, many applications exist in which some mes-
`sage positions are more important than others. For exam-
`ple in transmitting numerical data, errors in the sign or in
`the high-order digits are more serious than are errors in the
`low-order digits. As another example consider the trans-
`mission of message words from different sources simulta-
`neously in only one codeword, where the different sources
`have different demands concerning the protection against
`errors.
`Linear codes that protect some positions in a message
`word against a larger number of errors than other ones are
`called linear unequal error protection (LUEP) codes.
`Masnick and Wolf [8] introduced the concept of unequal
`error protection (UEP). But, in contrast with what one
`would expect, they considered error protection of single
`positions in codewords. In this paper we consider error
`protection of single positions in the input message words,
`following the formal definitions of Dunning and Robbins
`[2]. They introduced a so-called separation vector to mea-
`sure the error-correcting capability of a LUEP code.
`Whenever a k-dimensional LUEP code over GF (q) with
`separation vector s = (si, s2,. . * ,s,) is used on q-ary sym-
`metric channel, complete nearest neighbor decoding [7, p.
`
`received June 25, 1982; revised December 23, 1982. This
`Manuscript
`paper was partially presented at the IEEE
`International Symposium on
`Information Theory, Les Arcs, France, June 21-25,1982.
`The author was with
`the Denartment of Mathematics and Computing
`Science, Eindhoven University-of
`Technology, Eindhoven, The Nether-
`lands, He is now with Philins Research Laboratories. 5600 MD Eindho-
`ven, The Netherlands.
`
`111 guarantees the correct interpretation of the ith input
`message digit if no more than [(si - 1)/2] errors have
`occurred in the transmitted codeword.
`A basic problem is to find a LUEP code with a given
`dimension and separation vector such that its length is
`minimal and hence its information rate is maximal. In
`Section III we derive a number of bounds on the length of
`LUEP codes. For the special case where all message posi-
`tions are equally protected, some of our bounds reduce to
`the well-known Singleton, Plotkin, and Griesmer Bounds.
`Some earlier work on bounds was done by Katsman [6]; he
`derived Corollary 14 for the binary case. Our bounds give
`better results than the bound in [6]. Table I provides a
`table of binary LUEP codes with maximal separation
`vector and length less than or equal to 15.
`In Section IV we consider classes of cyclic UEP codes
`that can be decoded by majority decoding methods. Earlier
`results on cyclic UEP codes were obtained by Dyn’kin and
`Togonidze [3]. Table II provides a table of all binary cyclic
`UEP codes of length less than or equal to 39.
`
`II.
`
`DEFINITIONSAND
`
`PRELIMINARIES
`
`A. The Separation Vector
`Let q be a prime power and let GF (q) be the Galois
`field of order q. A linear [n, k] code C of length it and
`dimension k over GF (q) is a k-dimensional linear sub-
`space of GF (4)“. A generator matrix G of this code is a
`k-by-n matrix whose rows form a basis of C. The bijection
`from GF ( q)k onto C that maps any element m E GF ( q)k
`of the message set onto a codeword c = mG is called an
`encoding of C by means of the generator matrix G. For
`x E GF (q)“, wt (x) denotes the Hamming weight of X,
`i.e., the number of nonzero components in X.
`Dunning and Robbins [2] have introduced the following
`formal definition.
`Definition 1: For a linear [n, k] code C over the al-
`phabet GF (q)
`the
`separation
`vector s(G) =
`. .T So)
`of length k, with respect to a generator
`(4%.
`matrix G of C, is defined by
`So
`:= min {wt(mG)(m
`
`E GF(q)k, m, Z O),
`(1)
`i = l;**,k.
`This means that for any (Y, /3 E GF(q),
`(Y # /I, the sets
`
`OOlS-9448/83/1100-0866$01.00 01983 IEEE
`
`IPR2018-1556
`HTC EX1051, Page 7
`
`

`

`VAN GILS: TWO TOPICS ON LINEAR UNEQUAL ERROR PROTECTION CODES
`
`{mGlm E GF(q)k, m, = a} and {mGjm E GF(q)k, m,
`= /I } are at distance S( G)i apart (i = 1,. . . , k). This ob-
`servation implies the following error-correcting capability
`of a code when we use it on a q-ary symmetric channel.
`Theorem 1: For a linear [n, k] code C over GF (q),
`which uses a matrix G for its encoding, complete nearest
`neighbor decoding guarantees the correct interpretation of
`the ith message digit whenever the error pattern has a
`Hamming weight less than or equal to
`I( s( G) i - 1)/2]
`( 1x1 denotes the largest integer less than or equal to x).
`From Definition 1 it
`is immediately clear that
`the
`minimum distance of the code equals d = min { s(G)Ji =
`1; * * , k }. If a linear code C has a generator matrix G such
`that the components of the separation vector s(G) are not
`mutually equal, then the code C is called a linear unequal
`error protection (LUEP) code.
`One can easily decode LUEP codes by applying a syn-
`drome decoding method using a standard array (cf. [7, p.
`151). This decoding method reaches the correction capabil-
`ity given by Theorem 1, because of the following fact. For
`a fixed coset R of a linear code C, encoded by means of a
`generator matrix G, let U be the set of all possible coset
`leaders of R. For any r E R, r + U contains all codewords
`that are closet to r, i.e., at distance d( r, C) := min { wt( r -
`c)]c E C} from r. If i E (1;.
`.,k}
`is such that the weight
`of
`the elements of U
`is
`less
`than or equal
`to
`I( s(G) i - 1)/2],
`then the i th digits of the messages corre-
`sponding to the elements of r + U are easily seen to be
`mutually equal. Hence, if c = mG
`is
`the transmitted
`codeword and r is the received word such that wt (r - c) <
`th en syndrome decoding correctly repro-
`I(s(G)i
`- 1)/2I
`duces the ith digit m, of the message m sent.
`For two vectors x, y E Nk we define the ordering > by
`foralli = l;*.,k,
`x>y
`if
`xi>/yi,
`where the ordering 2 in xi > y, denotes the natural order-
`ing in the integers. We call a vector x E Nk nonincreasing
`if xi 2 xi+i
`for i = l;..,k
`- 1.
`By simultaneously permuting the message positions in
`the message words and the rows of a generator matrix G,
`we may obtain a generator matrix G for the code such that
`s(G) is nonincreasing, i.e., So
`> So+,
`for i = 1;. a,
`k - 1. From now on we assume that the message positions
`and the rows in generator matrices are ordered such that
`the corresponding separation vectors are nonincreasing.
`B. Optimal Encoding
`The separation vector defined by (1) depends upon the
`choice of a generator matrix for the code. But, fortunately
`every code has a so-called optimal generator matrix G*,
`whose separation vector s(G*)
`is componentwise larger
`than or equal to the separation vector s(G) of any other
`generator matrix G of the code (notation: s(G*) > s(G)).
`This was shown in [2]. From [2] we mention the following
`two results, which we will need later on. For a linear [n, k]
`code C and p E (0; .*, n } let C(p) denote the set of
`codewords in C of weight less than or equal to p, i.e.,
`C(p) := {c E Clwt(c) =s p}.
`
`867
`
`Theorem 2 [2, ths. 4 and 61: a) A generator matrix G of
`a linear [n, k] code C is optimal if and only if for any
`P (5 {L***, n } a subset X of the rows of G exists such that
`the linear span (C(p)) of C(p) equals the linear span (X)
`ofX.b)ForpE
`{l;..
`,n}, dim (C(P)) - dim (W-J - 1))
`components of the separation vector of an optimal genera-
`tor matrix G of a linear [n, k] code C are equal to p.
`Theorem 3 [2, ths. 5 and 61: For a linear [n, k] code C a
`minimal weight generator matrix G, i.e., a generator matrix
`of C with
`the minimal number of nonzero entries, is
`optimal and satisfies wt (G,*) = s(G),
`for
`i = 1,. . . , k,
`where Gi * denotes the i th row of G.
`Hence the following definition makes sense.
`Definition 2: The separation vector of a linear code is
`defined as the separation vector of an optimal generator
`matrix of the code.
`We shall use the notation [n, k, s] for a linear code of
`length n, dimension k, and (nonincreasing) separation vec-
`tor s.
`
`C. The Canonical Generator Matrix
`Boyarinov and Katsman [l] have introduced a special
`form of a generator matrix, called a canonical form.
`Definition 3: A generator matrix G of a linear [n, k]
`code, whose nonincreasing separation vector s(G) has z
`distinct components t, > t, > . . . > t, with multiplicities
`is called canonical if
`the submatrix
`. ., k,,
`resp. k,, k,;
`consisting of the k rows of G and the first k columns of G
`is a k-by-k lower triangular partitioned matrix having unit
`matrices of order resp. k,-by-k,, k,-by-k,, * * . , k,-by-k, on
`its diagonal. That is, G has the following form:
`0
`. . .
`0
`0
`I kl
`G
`. . .
`I k2
`0
`0
`2,1
`
`P
`
`.
`
`&-I,,
`G 2.1
`
`Gz-1,~
`G
`2.2
`
`*-’
`. . .
`
`hi-,
`G 2,2-l
`
`d
`
`‘k;
`
`(3)
`Any generator matrix G of a code can be transformed
`into a canonical generator matrix G,, of the code, such
`that s(G,,,) > s(G), by a number of elementary transfor-
`mations on the rows of G, that are permutation and
`addition of rows and multiplication of rows by scalars (cf.
`[l], [4]). If we want to transform a generator matrix G into
`a systematic generator matrix Gsyst, we cannot guarantee
`that s(G,,,,) >, s(G). For example [4], for q = 2,
`1000011110
`1100010001
`0
`0
`1 0 0
`0001010101
`0000110011
`1
`i
`It is easy to see
`has separation vector s(G) = (5,4,4,4,4).
`that it
`is impossible to transform G into a systematic
`
`G=
`
`1 1 0 0
`
`1
`
`IPR2018-1556
`HTC EX1051, Page 8
`
`

`

`86i3
`
`IEEE TRANSACTIONSON INFORMATIONTHEORY,VOL.1T- 29, NO,6,NOVEMBERl983
`
`generator matrix G,,,, such that s(G,,,,) > (5,4,4,4,4). Ac-
`tually, it can be easily verified that a 5 x 10 binary sys-
`tematic generator matrix with a separation vector of at
`least (5,4,4,4,4) does not exist.
`
`LUEP CODES
`III.
`BOUNDSONTHELENGTHOF
`A basic problem is to find LUEP codes with a given
`dimension and separation vector such that their length is
`minimal and hence their information rate is maximal.
`Definition 4: For any prime power q, k E N, and s E N k
`we define n,(s) as the length of the shortest linear code
`over GF (q) of dimension k with a separation vector of at
`least s and ny(s) as the length of the shortest linear code
`over GF (q) of dimension k with separation vector (ex-
`actly) s.
`An [n,(s), k, s] code is called optimal if an [n4(s), k, t]
`code with t > s, t # s, does not exist. For any prime power
`q, k E N and s, t E Nk, the functions n,(e) and nF(.)
`satisfy the following properties.
`q/(s) G q(s),
`(4)
`s < t - n&s) < n,(t),
`(5)
`s < t + q(s) Q n’,“(t).
`(6)
`To illustrate (6), observe that ny(5,4,4) = 8 (cf. Table I)
`and n’;;(5,4,3) = 9, which can be seen by easy verification.
`We now derive upper and lower bounds for these func-
`tions.
`A. Upper Bounds
`The following theorem provides a trivial upper bound
`for n,(e) and ny( e) and an easy way to construct LUEP
`codes. Let “ ] ” denote concatenation.
`Theorem 4: For any prime power q, k E N, u E N, and
`an arbitrarily partitioned vector (sl]sz] * . * Is,) E N k we
`have
`
`(7)
`
`ny(s1lS~I . * . IS”) < 2 neqx(sJ.
`i=l
`The same inequality holds for n4( .) (replace n?(o) in (7)
`by n,(3):
`, u let G, be a generator matrix of
`Proof: Foru = l;..
`a code with length nF(su) and separation vector s(G,) = s,.
`Then G := diag(G,, G,; . ., G,) has separation vector s(G)
`= (SII%l . * . I%)-
`Corollary 5: For any prime power q, k E N, and s E N k
`we have
`
`si.
`
`(8)
`
`q(s)
`
`<
`
`k
`c
`i=l
`Proof: Apply Theorem 4 with u = k, and G, = [ill
`. * . 11, 1 by su, for all u = 1; + .,k.
`Hence for any s E Nk it
`is possible to construct a
`k-dimensional code over GF (q) with separation vector s.
`
`TABLE1
`SEPARATIONVECTORSOFBINARYOPTIMALLUEPCODESOF
`LENGTHLESSTHANOREQUALTO~~
`separation vector
`
`dhk)
`
`k
`
`2
`2
`3
`2
`3
`4
`2
`3
`4
`5
`2
`3
`4
`5
`6
`2
`3
`4
`5
`6
`7
`2
`3
`4
`5
`6
`7
`8
`2
`3
`4
`5
`6
`7
`8
`9
`2
`3
`4
`5
`6
`7
`8
`9
`IO
`2
`3
`4
`5
`6
`7
`a
`9
`10
`II
`2
`3
`4
`5
`6
`7
`8
`9
`IO
`
`2
`3
`2
`4
`3
`2
`4
`4
`3
`2
`5
`4
`4
`2
`2
`6
`4
`4
`3
`2
`2
`6
`5
`4
`4
`3
`2
`2
`7
`6
`5
`4
`4
`3
`2
`2
`8
`6
`6
`4
`4
`4
`3
`2
`2
`8
`7
`6
`5
`4
`4
`4
`3
`2
`2
`9
`8
`7
`6
`5
`4
`4
`4
`3
`
`32
`42
`322
`52
`422
`3222
`62. 54
`522
`4222
`32222
`72, 64
`622, 544
`5222
`42222, 33332
`322222
`82, 74
`722, 644, 554
`6222, 5444
`52222, 44442, 43333
`422222, 333322
`3222222
`92, 84, 76
`822, 744, 664
`7222, 6444, 5544
`62222, 54444
`522222, 444422, 433332
`4222222, 3333222
`32222222
`10.2, 94, 86
`922, 844, 764
`0222, 7444, 6644
`72222, 64444, 55444
`622222, 544442, 533333
`5222222, 4444222, 4333322
`42222222, 33332222
`322222222
`11.2, 10.4, 96
`10.22, 944, 864, 774, 766
`9222, 8444, 7644
`82222, 74444, 66444, 55554
`722222, 644444, 554444
`6222222, 5444422, 5333332
`52222222, 44442222, 43333222
`422222222, 333322222
`3222222222
`12.2, 11.4, 10.6, 98
`11.22, 10.44, 964, 884, 866
`10.22, 9444, 8644, 7744. 7666
`92222, 04444, 76444, 66664, 66555
`822222, 744444, 664444, 555544
`7222222, 6444442, 6333333, 5544442, 5444444
`62222222, 54444222, 53333322
`522222222, 444422222, 433332222
`4222222222, 3333222222
`32222222222
`13.2, 12.4, 11.6, 10.8
`12.22. 11.44, 10..64, 984, 966
`11.222, 10.444, 9644,
`8844.
`0666
`10.2222,
`94444,
`064i4.
`77444,
`76666
`922222,
`844444,
`764444,
`666644,
`665552
`8222222,
`7444444,
`6644442,
`6544444,
`5555444
`li222222.
`64444422,
`63333332,
`55444422,
`54444444
`622222222,
`544442222,
`533333222
`5222222222,
`4444222222
`
`n
`
`4
`5
`5
`6
`6
`6
`7
`7
`7
`7
`a
`8
`8
`8
`a
`9
`9
`9
`9
`9
`9
`IO
`IO
`IO
`IO
`10
`IO
`10
`II
`II
`II
`II
`II
`II
`II
`II
`12
`12
`Ii
`12
`12
`12
`I2
`12
`12
`13
`13
`13
`13
`13
`13
`13
`13
`13
`13
`14
`14
`14
`14
`14
`14
`14
`14
`14
`
`IPR2018-1556
`HTC EX1051, Page 9
`
`

`

`VAN GILS: TWO TOPICS ON LINEAR UNEQUAL ERROR PROTECTION CODES
`
`869
`
`TABLE I
`(continued)
`
`Corollary 9: For any prime power q, k, j E N, 1 < j <
`k, and nonincreasing s E N k we have
`
`14
`14
`15
`15
`15
`15
`IS
`
`15
`15
`
`15
`15
`15
`15
`15
`
`11
`12
`2
`3
`4
`5
`6
`
`7
`a
`
`9
`10
`II
`12
`13
`
`2
`2
`10
`8
`8
`7
`6
`
`5
`4
`
`4
`4
`3
`2
`2
`
`42222222222,
`322222222222
`14.2,
`13.4.
`13.22,
`12.44,
`12.222,
`11.444,
`11.2222,
`10.4444.
`10.22222,
`944444,
`765554
`9222222,
`82222222,
`64444444,
`72222222i.
`6222222222.
`52222222222,
`422222222222,
`3222222222222
`
`33332222222
`
`11.8
`12.6.
`11.64,
`10.84,
`10.644,
`9844,
`96444,
`88444,
`864444,
`774444,
`
`988
`
`10.66.
`9666
`06666
`766662,
`
`766644,
`
`6655522
`6666444,
`7644444,
`66444422,
`65444442,
`. . . . . . . .
`(2)
`
`(1)
`
`633333322,
`5333332222
`
`554444222,
`
`544444444
`
`8444444,
`74444442,
`. . . . . . . .
`644444222,
`5444422222,
`44442222222
`333322222222
`
`B. Lower Bounds
`We start with a trivial, but useful, lower bound on n4( e).
`Theorem 6: For any prime power q, k E N, and s E Nk
`we have
`n&1, S2,‘. . ,Sk) > n&l
`
`- 1, s2 -
`
`l,...,Sk
`
`- 1) + 1.
`
`(9)
`Proof: By deleting a column from a k-by-(n,(s)) ma-
`trix G with separation vector s(G) 2 (st, s2;.
`.,sk), we
`obtain a k-by-(n,(s)
`- 1) matrix G’ with separation vector
`s(G’) > (sl - 1, s2 -
`l;..,sk
`- 1).
`Theorem 7: For q = 2, any k E N, and (sl, s2;.
`E Nkwehave
`
`.,sk)
`
`n,(s,,
`
`s2,’ * ‘,sk)
`
`(10)
`The same inequality holds when we replace n2( .) by ny( .).
`Proof: By adding an overall parity check to a binary
`[n = n2(s1;. . ,s,), k] code with a separation vector of at
`least (st;
`. . ,sk), we obtain an [n + 1, k] code with a
`separation
`vector
`of
`at
`least
`(2 \(sr + 1)/2],
`2 lb2 + 1)/2],’
`1’,2 [($ + 1)/2]).
`Theorem 8: For any prime power q, k E N, and nonin-
`creasing s E Nk we have
`n&1, S2,‘. . ,sk) > 1 + n&l,
`
`~2;~~,~k&~).
`
`(11)
`
`Proof: By deleting the column ek := (0, 0, . . . ,O, 1)r
`and the k th row from an optimal canonical (cf. Definition
`3) generator matrix of a linear [n = n,(s), k] code over
`GF (q) with a separation vector of at least s, we obtain a
`generator matrix of an [n - 1, k -
`l] code with a separa-
`tion vector of at least (sl, s2; . .,skPl).
`
`Corollary IO: For any prime power q, k E N, and non-
`increasing s E N k we have
`(13)
`n&1, 32,’ *. ,sk) > s1 + k - 1.
`For s1 = s2 = . . . = Sk Corollary 10 reduces to the Single-
`ton bound (cf. [7, ch. 1, th. 111).
`Theorem 11: For any prime power q and k E N, and
`any u E N and nonincreasing s E Nk such that s,-t
`is
`strictly larger than s, and
`k
`c si < q(s)
`i=o
`
`- 1,
`
`(14
`
`we must have
`*. ,Sk) >, 1 + nq(sl -
`ny(s,;
`
`l;..
`
`TS,-l
`
`- 1, s,;**,s,).
`05)
`Proof: Let v E N and a nonincreasing vector s E Nk
`be such that s,-r > s, and (14) holds. Let G be a minimal
`weight generator matrix of an [n = n?(s), k, s] code over
`GF (q). Because of (14) and Theorem 3, G has a column
`containing zero elements in the last k - v + 1 positions.
`By deleting this column from G we obtain a k-by-(n - 1)
`matrix G’, whose separation vector satisfies s(G’) 2 (sl -
`- 1, So,‘. . ,sk), since sUeI > s,.
`1; . . TS,-l
`Theorem 12: For any prime power q, k E N, and non-
`increasing s E N k we have that
`
`holds for any i E (1; . .,k}, where
`
`forj < i;
`
`07)
`
`‘j - 1(9 - ‘)‘i/91 J
`forj > i,
`‘j ‘=
`[Sj/ql,
`i
`where 1x1 denotes the smallest integer larger than or equal
`to x.
`Proof: Let C be a linear [n = n?(s), k, s] code over
`GF (q) and let G be a minimal weight generator matrix for
`C. By Theorem 3, wt(G,*) = si for all i = 1;.
`.,k.
`Fix i E (1; . . , k}. Without loss of generality the first si
`columns of G have a 1 in the ith row. Deleting these first si
`columns and the ith row from G, we obtain a (k - 1) by
`(n - si) matrix G. Clearly G has rank (k -
`l), for otherwise
`there would be a nontrivial linear combination of rows of
`G that equals 0, and hence the corresponding linear com-
`bination of rows of G would have a distance less than si to
`aGi * for some (Y E GF (q) \ {0}, a contradiction. Hence G
`is a generator matrix of an [n - si, k -
`l] code with sep-
`aration vector s^ := s(G) = (J1;.
`.,Sir-l, ji+t;.
`.,ik).
`. , k}, j # i, and let m E GF(q)k be such
`Let j E (1;.
`that m, = 0, m, # 0, and c := mG = (c,Ic2), where ct has
`length s,, satisfies wt (c2) = jj. Since mj Z 0, we have that
`wt (Cl) + ij 2 s/.
`08)
`
`IPR2018-1556
`HTC EX1051, Page 10
`
`

`

`870
`
`IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. IT - 29, NO. 6, NOVEMBER 1983
`
`least
`at
`for some (Y E GF (q) \ (0)
`Furthermore,
`- 111 components of (YC~ equal 1, and hence
`b(ClM9
`wt(G,,
`- ac) < si -[wt(c,)/(q
`-
`l)] +jj.
`(19)
`On the other hand we have that
`wt(G,,
`- (YC) 2 max{si,sj}.
`(20)
`The combination of (18), (19), and (20) ‘yields (16) and
`(17).
`Lemma 13: For any prime power q, k E I+J, and nonin-
`creasing s E Nk a linear [n,(s), k] code over GF (q) with a
`nonincreasing separation vector s* such that s < s* <
`s,l (sil denotes the k-vector with all components equal to
`sl) exists, i.e., ny(s*) = n,(s).
`Proof: Let G be a minimal weight generator matrix of
`an [n = n,(s), k] code with separation vector s(G) > s. If
`s(G), > si then replace a nonzero element in the first row
`of G by zero to obtain a matrix G’, whose separation vector
`satisfies s(G’) > s and s(G’), = s(G), - 1. We may
`transform G’ into a minimal weight generator matrix G”
`spanning the same linear subspace.
`Now, we repeat the above procedure until we obtain a
`k-by-n matrix G* such that s < s(G*) < sil.
`The combination of Theorem 12 and Lemma 13 gives
`the following corollary.
`Corollary 14: For any prime power q, k E N, and non-
`increasing s E N k, n 4( s) satisfies the inequalities
`ng(sl,-. ‘3 k s ) 2 % + n,(Ts,/ql,.‘.,Tsk/ql),
`,sk) > i
`[si/qipl] *
`i=l
`For s1 = s2 = . . * = sk, Corollary 14 reduces to the
`Griesmer bound (cf. [7, ch. 17, th. 241). Deleting the [ *1
`brackets in (22) we obtain an analog of the Plotkin bound
`(cf. [7, ch. 2, th. 11) for LUEP codes.
`Lemma 13 also implies the following corollary.
`Corollary 15: For any prime power q, k E N, and non-
`increasing s E Nk we have
`n,(s) = min { ny(s’)]s d s’ < s,l}.
`(23)
`This corollary allows us to use the bounds on ny( a) to
`obtain bounds on n4( *)
`Katsman [6] has shown Corollary 14 for q = 2. In many
`cases a combination of Corollary 15 and the bounds on
`ny( .) give better results than Corollary 14. For example,
`Corollary 14 yields that n,(5,4,3,3,3,3) > 11, while a
`combination of Corollary 15 and the Theorems 6 and 12
`yield that n,(5,4,3,3,3,3) 2 12 (using the values of Table
`I for n < 10). Actually n,(5,4,3,3,3,3) = 12 (cf. Table I).
`Another interesting fact is the observation that Theorem 12
`gives better results than the bound in [6], i.e., Theorem 12
`for i = 1 and q = 2. For example, Theorem 12 yields that
`ny(6,6,3,3,3,3,3)
`> 6 + n,(3,2,2,2,2,2)
`= 14,
`for i = 1
`
`t21)
`
`and
`ny(6,6,3,3,3,3,3)
`
`>, 3 + n,(5,5,2,2,2,2)
`
`= 15,
`for i = 7.
`Table I provides the separation vectors of the binary
`optimal LUEP codes of length less than or equal to 15,
`except for two. n denotes the length of the code, k denotes
`the dimension, and d(n, k) denotes the maximal minimum
`distance of a binary linear code of length n and dimension
`k. The brackets and commas commonly appearing in sep-
`aration vectors have been deleted. Only in the cases where
`a component of a separation vector is larger than 9, it is
`followed by a point (0). The construction of the codes in
`Table I can be found in [4]. In Table I there are two open
`places. 1) Does a binary
`[15, 8, s] code with
`(6,5,3,3,3,3,3,3) G s G (6,5,4,4,4,3,3,3) exist? 2) Does
`a [15,8,(5,5,5,x,4,4,4,4)]
`binary code with x E {4,5}
`exist? A [15,8, (5,5,5,5,4,4,4,3)]
`binary code exists (cf.
`[41)*
`In [4] also a number of constructions of optimal LUEP
`codes and methods for combining (LUEP) codes to obtain
`LUEP codes of larger length are given.
`
`IV. CYCLIC UEP CODES
`
`A. The Separation Vector of a Cyclic UEP Code
`A cyclic [n, k] code over GF (q) is the direct sum of a
`number of minimal
`ideals in
`the residue class ring
`- 1) of polynomials in x over GF (q) mod-
`GF(q)[xl/(x”
`ulo (x” - 1) (cf. [7, ch. 8, sec. 31).
`Theorem 16, [2]: For a cyclic code C that is the direct
`sum of v minimal ideals, an ordering Ml, M2,. i. ,M, of
`generator matrices of these minimal ideals exist such that
`
`G :=
`
`is an optimal generator matrix.
`Proof: For p E {l;..,n},
`is a cyclic code.
`(C(p))
`Hence (C(p))
`is the direct sum of a number of minimal
`- 1). By applying Theorem 2a) we
`ideals of GF(q)[x]/(x”
`get the theorem.
`The following corollaries are immediate consequences of
`Theorem 2 and 16.
`Corollary 17: For a minimal ideal in GF (q)[ xl/( x” - 1)
`all components of the separation vector are mutually equal.
`Corollary 18: For a cyclic code C with an optimal gen-
`erator matrix G defined by formula (24) the i th and jth
`component of the separation vector s = s(G) are equal if
`the ith and jth row of G are in the same minimal ideal of
`GF(q)[xl/(x”
`- 1).
`
`IPR2018-1556
`HTC EX1051, Page 11
`
`

`

`VANGILS:TWOTOPICSONLINEARUNEQUALERRORPROTECTIONCODES
`
`871