`
`I, Steve Wasserman, declare that:
`1.
`I have personal knowledge of the facts set forth in this declaration,
`which are know by me to be true and correct, and if called as a witness, I could and
`would testify competently.
`2.
`I am the owner of Retriev-it, located at 324 South Beverly Drive Suite
`200, Beverly Hills, CA 90212 (“Retriev-it”). Retriev-it is an information retrieval
`company. I have owned and worked for Retriev-it since approximately 2000.
`3.
`As part of my duties, I retrieve information related to publications
`from various libraries in California. For example, if a customer needs to find out
`when a publication was added to a certain library’s catalog, but there is no online
`record, I will go the library, search for the book through a library’s catalog, retrieve
`the book from the shelf, and inspect the book to determine if there is a date stamp.
`4.
`On August 10, 2018, I went to the library of the University of
`California, Los Angeles (“UCLA”). While at UCLA, I reviewed the article entitled
`“Modified Generalized Concatenated Codes and Their Application To The
`Construction And Decoding of LUEP Codes,” included as part of the IEEE
`Transaction on Information Theory, Vol. 41, Issue 5, September 1995 (the
`“Information Theory”). I copied the cover page and introductory pages of the
`Information Theory. The cover page and page 1217 contain stamps showing that
`the Information Theory was entered into UCLA’s collection on September 20,
`1995. Attached hereto as Exhibit A are true and correct copies of the cover page
`and page 1217 of the Information Theory.
`5.
`On August 13, 2018, I returned to UCLA, where I reviewed the article
`entitled “Some Constructions of Optimal Binary Linear Unequal Error Protection
`Codes,” included as part of the Philips Journal of Research, Vol. 39, no. 6, 1984
`
`IPR2018-1556
`HTC EX1052, Page 1
`
`
`
`HI
`
`I copied the coverpagethat contains a stamp showingthat
`(the “Philips Journal”).
`the Philips Journal was entered into UCLA’s collection on March 21, 1985.
`Attached hereto as Exhibit B is a true and correct copy of the cover page of the
`Philips Journal.
`6.
`On August 15, 2018, I once again returned to UCLA,whereI
`reviewedthearticle entitled “Future Trends in Optical Recording,” included 7 om
`ofthe Philips Technical Review, Vol. 44, no. 2, April 1988 (the “Philips Review ).
`I copied the cover pagethat contains a stamp showingthat the Philips Review _
`entered into UCLA’s collection on June 8, 1988. Attached hereto as Exhibit C 1s a
`true and correct copy ofthe cover page ofthe Philips Review.
`
`ited
`I declare underthe penalty ofperjury under the laws ofthe United
`America that the foregoing is true and correct.
`
`States of
`
`
`Executed on August 16, 2018 in Los An
`
`
`Steve Wasserman
`
`IPR2018-1556
`HTC EX1052, Page 2
`
`IPR2018-1556
`HTC EX1052, Page 2
`
`
`
`Exhibit A
`Exhibit A
`
`IPR2018-1556
`HTC EX1052, Page 3
`
`IPR2018-1556
`HTC EX1052, Page 3
`
`
`
`
`
`IPR2018-1556
`HTC EX1052, Page 4
`
`
`
`IPR2018-1556
`HTC EX1052, Page 5
`
`
`
`
`TEEE INFORMATION THEORY SOCIETY
`
`The Infcrmation Theory Society is an organization, within the framework of the IEEE, of members with principal professionalinterestsin informatj
`On th
`All members of the IEEE are eligible for membership in the Society and will receive this TRANSACTIONS upon payment of the annual Society mem
`bership fog
`of $15.00. For information on joining, write to the IEEE at the address below. Membercopies of Transactions/Journals are for personal use only,
`BOARD OF GOVERNORS
`
`President
`BRUCE HAJEK
`Dept. Elec. & Comput. Eng.
`Coordinated Sci. Lab.
`University of Illinois
`1308 W. Main Street
`Urbana, IL 61801
`
`First Past President
`CHRIS D. HEEGARD,
`School of Elec. Eng.
`327 Eng. Theory Ctr.
`Cornell University
`Ithaca, NY 14853-3801
`
`JULIA ABRAHAMS(‘96)
`ANDREW R. BARRON('97)
`VAY K. BHARGAVA('97)
`AUBREY BUSH (’95)
`A. R. CALDERBANK ("96)
`
`First Vice President
`JERRY D. GIBSON
`Dept. Elec. Eng.
`Texas A&M Univ.
`College Station, TX 77843
`
`Second Vice President
`SERGIO VERDU
`Dept. Elec. Eng.
`Princeton Univ.
`Princeton, N} 08544
`
`Secretary
`SERENA M. ZABIN
`School of Elec.
`and Comput. Eng.
`Georgia Inst. Technol.
`Atlanta, GA 30332
`
`Treasurer
`TOM FUIJA
`Dept. Elec. Eng.
`Univeristy of Maryland
`College Park, MD 20742
`
`Second Past President
`STUART C, SCHWARTZ
`Dept. Elec. Eng.
`Princeton University
`Princeton, NJ 08544
`
`Transactions Editor
`RICHARD E. BLAHUT
`Coordinated Sci. Lab.
`University of Illinois
`1308 W, Main Street
`Urbana, IL 61801
`
`AGNES HUI CHAN ('97)
`DANIEL J. COSTELLO,JR. ('95)
`ANTHONY EPHREMIDES (96)
`THOMAS ERICSON ('95)
`
`THOMASR.FISCHER (97)
`TOM FUJA (797)
`TE SUN HAN ('96)
`HIDEKI IMAI(795)
`
`Newsletter Editor
`RAMESH RAO
`Dept. Elec. & Comput, Eng,
`Univ. California, San Diego
`LaJolla, CA 92093
`
`SALEEM A. KASSAM ('96)
`JAMES L. MASSEY('95)
`SHLOMO SHAMAI (SHITZ) ('97)
`PAUL H.SIEGEL (°96)
`HENK VAN TILBORG(96)
`
`E. ARIKAN
`At Large
`
`U. M. MAURER
`Complexity and
`Cryptography
`
`T. M. COVER
`Book Reviews
`
`B. HUGHES
`Detection
`
`IEEE TRANSACTIONS ON INFORMATION THEORY
`R. E. BLAHUT, Editor
`J. A. O’SULLIVAN, Publications Editor
`Associate Editors
`T. HOHOLDT
`P, V. KUMAR
`Coding Theory
`Coding Theory
`
`H. IMAI
`Coding Theory
`
`P. H. SIEGEL
`Coding Techniques
`
`A. JUDITSKY
`Estimation
`
`A, HERO
`Signal Processing
`
`A. R. BARRON
`Nonparametric
`Estimation,
`Classification, and
`Neural
`Networks
`Please refer to inside back cover for instructions on submitting manuscripts.
`
`T. S. HAN
`Shannon Theory
`
`C, N. GEORGHIADES
`Communications
`
`R. CRUZ
`Communication
`Networks
`N. FARVARDIN M. FEDER
`Source Coding
`Source Coding
`
`THE INSTITUTE OF ELECTRICAL AND ELECTRONICS ENGINEERS, INC.
`Officers
`
`JoEL B. SNYDER, Vice President, Professional Activities
`James T. Cain, President
`W. KENNETH Dawson,Vice President, Publications
`WALLACE S. READ, President-Elect
`Vuay K. Buaraava, Vice President, Regional Activities
`CHARLES W. TURNER, Secretary
`E. G, KIENER, Vice President, Standards Activities
`V. THOMAS RHYNE, Treasurer
`BRUCE EISENSTEIN, Vice President, Technical Activities
`KENNETH R. LAKER, Vice President, Educational Activities
`THEODORE W.HisseEy, JR., Executive Director
`TzyH-JONG (T.J.) TARN, Director, Division X—Systems and Control
`
`Headquarters Staff
`RICHARD D. SCHWARTZ, Acting General Manager
`PHYLLIS HALL, Staff Executive, Publications
`FRANK R. Moore, Staff Executive, Volunteer Activities
`IRVING ENGELSON, Staff Director, Corporate Activities
`ANDREW G.SALEM,StaffDirector, Standards Activities
`Peter A. Lewis, Staff Director, Educational Activities
`W. Tuomas SUTTLE, StaffDirector, Professional Activities
`MELVIN I. OLKEN, Staff Director, Regional Activities
`RoBert T. WANGEMANN,StaffDirector, Technical Activities
`Transactions/Journals Department
`StaffDirector: PATRICIA WALKER
`Manager: GAIL S. FERENC ©
`Electronic Production Manager: Jeri L. Uzzo
`Managing Editor: VALERIE CAMMARATA
`Senior Associate Editor: NELA RYBOWICZ
`e
`IEEE TRANSACTIONS ON INFORMATION THEORYis published bimonthly by the Institute of Electrical andElectronics Engineers,Inc. Responsibility for iv
`
`contents rests upon the authors and not upon the IEEE, the Society/Council,or its members. IEEE Ce
`Office: 345 East 47th Street, New Hog
`
`10017-2394. IEEE Operations Center: 445 Hoes Lane, P.O. Box 1331, Piscataway,
`h
`55-1331. NJ Telephone: (908) 981-0060. Price/Pub '*
`;
`per
`copy.
`(Note:
`a
`Information: Individual copies: IEEE Members $10.00 (first «
`Add $4.00 postage and handling 2
`
`=
`any order from $1.00 to $50.00, including prepaid orders.) Member and
`upon request. Available in microficl
`
`ited
`to photocopy for P
`microfilm, Copyright and Reprint Permissions:
`Ab
`
`of patrons, provided the per-copy fee indicated
`Clearance Center, 222
`
`Drive, Danvers, MA 01923. For all
`
`Administration, 445 Hoes Lane, P.O.
`
`' All rights reserved. Second.
`
`=e
`
`
`
`
`
`IPR2018-1556
`HTC EX1052, Page 6
`
`
`
`
`
`HTC EX1052, Page 7
`
`IPR2018-1556
`
`IPR2018-1556
`HTC EX1052, Page 7
`
`
`
`INFO
`
`
`
`ee
`
`
`
`a R
`
`INFORMATION FOR AUTHORS
`MATION THEORY 1s
`:
`f
`sACTIONS ON
`ql
`The IEEE
`that publishes theoretical and exper!
`pimonthly pur med with the transmission, processing,
`‘ental
`oorformation. The boundaries of meee
`vd u
`tion © intentionally not sharply delimited. Rather,
`eabjest
`fer Fe
`focus of research activity changes, a
`ma a th
`ui
`:
`SACTIONS to follow suit.
`it
`T noped thal
`;
`:
`+c TRAN
`ie
`aa =
`ted by recent Table
`arized in the titles of editorial areas
`‘aside front cover.
`Nae the form of regular papers or of
`t one of quality, but of
`e. The distinction is not
`on
`denc a correspondence item will have one point to
`nt ‘efly and without adornment, whereas an regular paper
`om= Les well-rounded treatment of a problem area.
`Contributions should comprise novel and previously un-
`jished material; however, prior publication in conference
`nae 5 of an abstract, summary, or other abbreviated,
`jiminary form of the material shall not preclude publica-
`tion in this journal when notice of such prior or concurrent
`publication given at the time of submission. The novelty
`will usually lie in original results, methods, observations,
`concepts, OF applications, but may also reside in syntheses
`of or new insights into previously reported research. Novelty
`alone does not assure publication; the significance of a paper
`and its usefulness to the TRANSACTIONS readership also will
`~ be assessed. Notice ofprior submission of the material must be
`given at the time of submission to this TRANSACTIONS,there-
`after, submission elsewhere is precluded unless the material is
`refused for publication or is withdrawn by the author. Survey
`and expository papers are also welcome.
`In regular papers, the title, abstract, introduction, and sum-
`_ mary should be sufficiently informative to makethegist of the
`_ paper clear to the broadest possible audience and to place the
`- contributions of the paperin context with related work. The
`body of the paper should be understandable without undue
`effort by its intended audience. Supporting material not of
`central interest is best relegated to appendixes.
`ee should be less discursive but equally lucid.
`ould be awarethat a well-written correspondence
`
`usually can be published morerapi
`e
`published more
`rapidly than can a regular paper.
`Authore shay dd etree dees
`i
`five legible copies of all written
`
`
`ed in the last paragraph. If there is
`h 1)essential for the reviewing
`
`thereviewers (e.g., preprints)
`
`Ie ‘Teviewing process, au-
`
`; ofrelevant excerpts. Each
`
`informative abstract of not
`
`emust include an abstract
`
`aea-
`stofindex terms (key words
`
`‘ the abstract, a total of
`
`The terms should be relatively.
`u »Should characterize the paper.
`
`abstract and references,
`
`should be double spaced, single sided. A list of figure captions
`should be included. Authors should be prepared to supply
`originals of figures upon notification of acceptance, and also
`biographical sketches (for regular papers).
`In all other respects, papers should be prepared for publi-
`cation in a mannersimilar to that for the PROCEEDING OF THE
`IEEE. “Information for IEEE TRANSACTIONS and JOURNAL
`Authors” is available from the IEEE Transactions/Journals
`Department, 445 Hoes Lane, Piscataway, NJ 08855. For
`further details, see “Advice to Authors,” JEEE Transactions
`on Information Theory, vol. 36, no. 5, pp. 1193-1194, Sept.
`1990.
`NOTICE:All papers should be submitted directly to the
`Editor-in-Chief (see below). Authors must indicate whether
`the manuscript
`is to be reviewed as a regular paper or as
`a correspondence. Also it would be helpful
`if a suggested
`Associate Editorial area is given. Authors desiring immediate
`confirmation of receipt of their manuscripts should enclose a
`return-addressed postcard with their submission.
`
`After September 1, submit manuscripts to:
`
`A. R. Calderbank, Editor-in-Chief
`IEEE TRANSACTIONS ON INFORMATION THEORY
`AT&T Bell Laboratories, Room 2C-363
`600, Moutain Avenue
`Murray Hill, NJ 07974
`
`Electronic Publishing: The IEEE is now able to produce
`page proofs directly from electronic media. A floppy disk of
`tape should accompany manuscripts that have been accepted
`for publication. The contents of the disk or tape must agree
`with the hard copy, since both are used in copyediting. Please
`try to includeall material (biographies, captions, etc.) on the
`disk or tape.
`After the manuscript has been accepted
`Page Charges:
`y or institution will be
`for publication, the author’s compan
`ation. Page charges
`requested to cover part of the cost of public
`for this journal, like those for journals of other professional
`societies, are not obligatory nor is their payment a prerequisite
`for publication. The author will
`receive 100 free reprints
`without covers if the charge is honored. Detailed instructions
`will accompany the proof.
`Copyright:It is the policy ofthe IEEE to own the copyright
`to the technical contributions it publishes on behalf of the
`interests of the IEEE,its authors, and their employers, and to
`facilitate the appropriate reuse of this material by others. To
`comply with the U.S. Copyright Law, authors are required to
`sign an IEEE Copyright Form before publication. This form
`which appears in the January issue ofthis journal, returns to
`authors and their employers full rights to reuse their material
`fortheirown purposes. Authors are required to submit a signed
`:
`tah thei
`ee.
`copy of this form Wi
`eir manuscrip Pent EEG
`HTC EX1052, Page 8
`
`IPR2018-1556
`HTC EX1052, Page 8
`
`
`
`
`
`IPR2018-1556
`HTC EX1052, Page 9
`
`
`
`TRANSACTIONS ON INFORMATION THEORY, VOL, 41, NO. 5, SEPTEMBER 1995
`
`,T
`
`ERE
`
`author would also like to acknowledge stimulating discussions
`with O. Amrani and F.-W. Sun. Finally, the author wishes to thank
`Hagit Itzkowitz for her invaluable help.
`REFERENCES
`
` (1) A. D. Abbaszadeh and C. K. Rushforth, “VLSI implementation of a
`
`1499
`
`Modified Generalized Concatenated
`Codes and their Application to the
`Construction and Decoding of LUEP Codes
`
`Uwe Dettmar, Yan Gao, and Ulrich K. Sorger
`
`Abstract—Wepropose a modification of generalized concatenated codes,
`which allows us to construct some of the best known binary codes in
`a simple way. Furthermore, a large class of optimal
`linear unequal
`error protection codes (LUEP codes) can easily be generated. All con-
`structed codes can be efficiently decoded by the Blokh—Zyablov—Zinov’ cy
`algorithm if an appropriate metric is used.
`Index Terms—Linear unequalerror protection codes, generalized con-
`catenated codes, multistage decoding.
`
`I.
`INTRODUCTION
`Manyof the best known codes can be constructed as Generalized
`Concatenated (GC) codes [2], [3]. Generally, the constructions of
`GC codes use different outer codes A; of constant length 1, but
`only one inner code B‘") together with its partition. However, this
`restriction is not necessary. In this correspondence we construct GC
`codes consisting of outer codes A; with different lengths na. ;, and
`inner codes BY in the columns of the code matrix with different
`lengths np, ; and distances dy together with their partitions.
`In Section II, modified GC codes are defined and a lower bound
`on their minimum distance, a designed minimum distance,is derived.
`Two examples of the construction of good binary codes as modified
`GC codes are given. In Section IH,
`the modification is used to
`construct binary optimal
`linear unequal error protection (LUEP)
`codes. In Section IV, a decoding algorithm for the modified GC
`codes is presented, which allows decoding up to half their designed
`minimum distance. Moreover, decoding of the constructed LUEP
`codes up to half the separation vector is discussed.
`Forthe sake of simplicity only binary codes are considered in this
`correspondence. An extension to the nonbinary case is straightfor-
`ward.
`;
`
`Il. DEFINITION OF MopiFiED GC CopEs
`
`GC codes are a generalization of concatenated codes defined
`‘by Forney [4]. The inner code is multiply partitioned, and this
`partitioning into subcodes is protected by different outer codes.
`Denote the m outer codes by A; = Aj(qi: Ma, ka, i, da,i), where
`qi = 2”:
`is the alphabet size, nq is the code length, ka,;
`is the
`number of information symbols, and da,; is the Hamming distance
`of the code. Further, denote by B®) = B‘(2; ny, ksi, ds,i), for
`i = 1, 2,--++, m, the binary inner codes, where
`
`BOTY c BO
`
`and
`
`xe) — RtD
`
`= log, (qi).
`
`By concatenating inner and outer codes we get a GC code with the
`
`Manuscript received February 11, 1994; revised March 5, 1995. The
`material in this correspondence was presented in part at the IEEE International
`Symposium on Information Theory, San Antonio, TX, 1993..
`The authors are with the Institut fiir Netzwerk- und Signaltheorie, Techni-
`sche Hochschule Darmstadt, D-64283 Darmstadt, Germany.
`IEEE Log Number 9413060.
`
`maximum likelihood decoder for the Golay (24,12) code,” JEEE J.
`Selected Areas Commun., vol. 6, pp. 558-565, 1988.
`(2) 0. Amrani and Y. Be'ery, “Efficient bounded-distance decoding of the
`hexacode and associated decoders for the Leechlattice and the Golay
`code,” in Proc. IEEE Int. Symp. on Information Theory (Trondheim,
`Norway, 1994), p. 400.
`3] O. Amrani, Y. Be’ery, and A. Vardy, “Bounded-distance decoding of
`the Leech lattice and the Golay code,” Lecture Notes Comput. Sci., vol.
`781, pp. 236-247, 1993.
`[4] 0. Amrani, Y. Be'ery, A. Vardy, F.-W. Sun, and H. C. A. van Tilborg,
`“The Leech lattice and the Golay code: bounded-distance decoding
`and multilevel constructions” JEEE Trans. Inform. Theory, vol. 40, pp.
`1030-1043, 1994.
`(5) EB F. Assmus, Jr. and H. F. Mattson, Jr., “Algebraic theory of codes,”
`Rep. 1, Contract F19628-69C0068, Air Force Cambridge Res. Labs.,
`Bedford, MA, 1969.
`E
`[6] Y. Be'ery and B. Shahar, “VLSI architectures for soft decoding of
`the Leech lattice and the Golay codes,” in Proc. IEEE Int. Workshop
`on Microelectronics in Communications (Interlaken, Switzerland, Mar.
`1991).
`[7] Y. Be’ery, B. Shahar, and J. Snyders, “Fast decoding of the
`ec: lattice,” JEEEJ. Selected Areas Commun., vol. 7, pp.959-967,
`(8] Y. Be’ery and J. Snyders, “Optimal soft decision block decoders based
`it
`_ on Fast Hadamard Transform,” [EEE Trans. Inform. Theory, vol. IT-32,
`thy
`pp. 355-364, 1986.
`tt
`in prepara-
`[9] A.R. Calderbank, Bandwidth Efficient Communication,
`|e
`ition.
`
`3 [10] J. H. Conway and N.J. A. Sloane, “Soft decoding techniques for codes
`
`and lattices, including the Golay code and the Leechlattice,” JEEE
`Trans. Inform. Theory, vol. IT-32, pp. 41-50, 1986.
`__
`
`[Il] ——, Sphere Packings, Lattices and Groups. New York: Springer-
`
`Verlag, 1988.
`
`[12] M. V. Byuboglu and G. D.Forney, Jr., “Lattice and trellis quantiza-
`
`tion with lattice- and trellis-bounded codebooks—high-rate theory for
`___ memoryless sources,” JEEE Trans. Inform. Theory, vol. 39, pp. 46-59,
`
`1993,
`.
`
`D. Forney, Jr., “Generalized minimum distance decoding,” IEEE
`
`Trans. Inform. Theory, vol. I1T-12, pp. 125-131, 1966.
`
`[14] —_, “Coset codesI: Introduction and geometrical classification,” IEEE
`
`_ Trans. Inform. Theory, vol. 34, pp. 1123-1151, 1988.
`
`——.. “Coset codes I: Binary lattices and related codes,” EEE Trans.
`
`rm. Theory, vol. 34, pp. 1152-1187, 1988.
`
`——, “A boundeddistance decoding algorithm for the Leech lattice,
`
`“i sca IEEETrans. Inform. Theory,vol. 35, pp. 906-909,
`
`
`{17] —_.,, “Density/length profiles andtrellis complexity oflattices,” JEEE
`Trans, Inform. Theory, vol. 40, pp. 1753-1772, 1994.
`
`118) G. R. Lang and F, M. Longstaff, “A Leech lattice modem,” /EEE J.
`
`____
`Selected Areas Commun., vol. 7, pp. 968-973, 1989.
`
`[19] J. Snyders and Y, Be’ery, “Maximum likelihood soft decoding of binary
`
`block codes and decoders for the Golay codes,” JEEE Trans, Inform.
`
`Fin Theory, vol. 35, pp. 963-975, 1989.
`
`10) F.-W.Sun and H. C. A. van Tilborg, “More efficient bounded-distance
`
`decoding of the Golay code and the Leech lattice,” in Proc. IEEE Int.
`
`‘pj Symp. on Information Theory (Trondheim, Norway, 1994), p. 399.
`
`——., “The Leechlattice, the octacode, and decoding algorithms,” JEEE
`
`“fay ans: Inform. Theory, vol. 41, no, 4, pp. 1097-1106, July 1995,
`
`a. Vardy,
`“A new sphere packing in 20 dimensions,” Inventiones
`
`py,
`Mathematicae, vol. 121, no. 1, July 1995.
`
`ae A Vardy and Y, Be’ery, “More efficient soft-decision decoding of
`
`-
`the Golay codes,” JEEE Trans. Inform.Theory, vol.37, pp. 667-672,
`
`r, ‘1991.
`
`cim
`decoding of the Leechlattice,” IEEE
`». 1435-1444, 1993.
`
`Ny
`ty,”
`“ te
`ni
`Xi
`by
`t
`,
`“hy
`by
`:
`hi
`4
`Nay
`Rh
`fy
`Mes
`y
`| Dl
`ty
`bn
`
`
`
`001 8-9448/95$04,00 © 1995 IEEE
`
`IPR2018-1556
`HTC EX1052, Page 10
`
`IPR2018-1556
`HTC EX1052, Page 10
`
`
`
`1500
`
`IEEE TRANSACTIONS ON INFORM.ATION THEORY, VOL. 41, NO. 5, SEPTEMBER 1995
`
`TABLE I
`EXAMPLE |
`
`Inner codes
`fs
`Outer codes
`|_GC code
`|
`
`j= 24s =o 0
`|
`
`
`
`Bl Jy = {1,--.10}|(75, 11, 32)(8, 4,4) (4,1,4) (7,3,4) (23:10, 7bit,8)
`
`
`
`
`(8,1,8)
` (4,0,c0)
`(7,0,00)|
`A>
`(2;8,4,4)
`Ja = {1-8}
`5:
`Be
`
`
`
`
`BU (73,4)|Ar(8.4.4) (43,2) (2510,3,8) A ={1,---,10} Ceuta}
`
`
`
`
`
`Be) _(7,0,00)|Ao(81,8) (4,0,00) (2384.4) Ja = {1-8}
`
`
`
`:
`
`arameters
`
`[3
`TABLE II
`a
`CONSTRUCTION:
`1
`
`eo ea
`[
`Inner codes
`[
`Outer codes
`
`-
`j=1,--.™ |
`
`
`
`
`ic Daeva, i log, (qi) (ng,kn + k22,da1)|ArBY” (2*:ny,ki1.81) A = {1,....m}
`
`
`
`7 (mg, kraedaa)|A2_(2":m1,kiz,82)BO?) Ja = {1,.--.m1}
`
`d > min {da,1db,1, da,2ds,2, ---, da, mdb, m}-
`
`The lower bound on the minimum distance is derived as follows
`[3]: since the codes are linear, the minimum weight and distance are
`equal. If a; # 0, with a; € Ax, then notless than da, ; codewords of
`the inner code B“? are different from the zero word. However, this
`inner code has a minimum weight d;,; which leads to a minimum
`weight of da.id»,1 for the appropriate codeword of the GC code.
`Similar considerations hold for the other stages.
`In the above definition the outer codes all have equal length na.
`However, this restriction is not necessary: denote the outer codes by
`
`Aj = Ai( qi; Nak
`
`a,t>
`
`iia =)
`
`where the n,,; now can be different. Define a set of indices 7; with
`|%| = ma,i and jmax so that
`
`l<j<jma, VIER
`
`holds. The inner codes are given by
`Be = BY(2; Nb, 7 Keue dy*)7
`fori = 1, 2,---, m and 7 = 1,--+, jmax, With
`(i+1)
`(2)
`@)
`G4) _ flog, (qi),
`
`C Bj"
`
`and ky; — fy; ={0 2
`
`B;
`
`fg EK
`
`7 @ I.
`
`We assume that U;.7; = 7, with 7 € J for 7 = 1, 2, ---, jmax,
`because in this case all inner codes are concatenated with someouter
`codes.
`The GC code has the parameters
`Jmax
`n= De Nb,
`s=1
`
`k= Ss ka, i 1085 (qi).
`i=1
`
`(1)
`
`The minimum distance of the GC code is given by
`d> min min oe ant
`ps
`j€8;
`where 5; C J; with |S;| = da,;.
`The lower bound for the minimum distance is derived similarly
`to that for conventional GC codes: the minimum weightin stage 7
`is attained if the positions where a; # 0 coincide with codewords
`of the inner codes BY with the smallest minimum distances. This
`leads to (1).
`To simplify this expression, we define by II(j) the permutation of
`the indices 7 = 1, ---, ™a,i so that
`
`dyna) < dem) S++: < de,m(ng,,)-
`
`This results in
`
`a
`
`da, a
`
`Gams »X ding):
`
`holds for any 7 € {1,---, k}, where
`Si
`s;-|—|,
`
`IPR2018-1556;, :=
`
`HTC EX1052, Page 11
`
`Example 1: The (75, 11,32) and the (75, 13,30) code from [5]
`can be constructed as given in Table I.
`
`Ill. OptiMAL LUEP Copges CONSTRUCTED AS GC CODES
`if
`Linear unequal error protection (LUEP) codes can be useful
`different information symbols have different importance. In [1] and
`[6], van Gils proposedconstructions for somespecial classes of LUEP
`codes (some of them based on product or concatenated codes). In [7],
`Zinovev investigated the application of GC codesonthe construction
`of LUEP codes, but these constructions only work for composite code
`length, i.e., 2 = many. The modified construction yields a large class
`of binary LUEP codes which contains most of van Gils constructions
`and which can be easily decoded.
`The LUEPcodeis characterized by its separation vector [6].
`Definition I; For a linear (n, k) code C over the alphabet GF(q),
`the separation vector s = (s), so, ---, s,) with respect to a generator
`matrix G of C,
`is defined as
`
`5; := min{wt{mG|m € GF(q)*, m: 4 0}, i=1,---,
`
`k}
`
`where m is an information vector and wt {-} denotes the Hamming
`weight function.
`
`We assume, without loss of generality that s is nonincreasing,i.e.,
`
`{1,---,k}. Note that this definition is
`8; > 8s; ift < j Vi,j €
`different from that in [8] as it deals with information symbolsinstead
`of code symbols. The separation vector guarantees the correct inter-
`pretation of the ith information symbol whenever nearest neighbor
`decoding [9] is applied and not more than |(s(G); — 1)/2] errors
`have occurred in the transmitted codeword [10].
`An (n, k, 8) codeis called optimal if an (n, k, £) code witht > s,
`ie., t > 8; Vi
`€ {1,--+,k} and 3y € {1,---,k}:t; > sj, does
`not exist. Denote by n(s) the length of the shortest linear binary
`code of dimension & with separation vector at
`least s and denote
`n°*(s) the length ofthe shortest linear binary code of dimension *
`with separation vector (exactly) s. Van Gils [1], [11], has derived the
`following lower bounds on n(s):
`Theorem 1: For any k € NV,and nonincreasing s € N*
`
`m(Fy ep aie sh) > si tn(hi,---, Syl. ate Sx)
`
`(2)
`
`2” Lz
`rah
`[a] denotes the smallest integer larger than or equal to 2.
`
`for
`
`uae
`j<i
`
`:
`
`LOK o> 4.
`
`3)
`
`IPR2018-1556
`HTC EX1052, Page 11
`
`
`
`Py TRANSACTIONS ON INFORMATION THEORY,VOL.41, NO. 5, SEPTEMBER 1995
`
`1501
`
`TABLE III
`CONSTRUCTION 2
`|
`Inner codes
`|
`Outer codes
`|
`j=1,...m j =m 4t1,-....m+n'
`
`BY (m2,m2,1) —(ma—ha,m2—k2,1)|Ay
`(27> nyt+n',ki,81) A= {l,....mtn'}
`
`(na—k2, 0,00)
`(2"; ny, ki2, $2)
`Ja = {1,..-,m}
`
` BYPi(M2,ka, daa)
`
`TABLE V
`TABLE IV
`EXAMPLE 2
`
`CONSTRUCTION 3
`
`
`Inner codes
`| Outer codes
`= ==
`[
`Inner codes
`A
`Outer codes
`
`|
`L—=T om j=mti|
`
`j=l.
`j=20
`f=4
`
`
`
`
`
`BOS
`(45352)
`(3, 2,2)
`(22,1)
`Ar
`(273452,3) A= {1,...,4}
`
`
`
`Bo) (1,11)|Ai(make + 1,dz) (2: ny, kyr, 81) Tua fi, .;m}
`
`
`
`
`
`
`
`
`
`pe) (1,0,00)|Ao(4,1,4) (3,0,00) (251,11) A ={1}
`
`
`
`go
`(na,1, nz)
`(1, Le 1)
`Az
`(23m, + 1, k12,2[5/2]) = Ae m+ 1}
`
`
`
`
`
`
`TABLE VI
`EXAMPLE 3
`
`
`li
`Inner codes
`Outer codes
`al
`fale gas
`jas
`
`
`
`B® (4,1,4) (1,0,00)|Ao(3,0,00) (2;2,2,1) Fa = {11,2}
`
`NV, and nonincreasing s € NVKF n(s)
`Theorem 2: For any k €
`}
`satisfies the inequalities
`
`
`
` peraIaae (453)2)°9(3,2,2): (2,2)1)|Ar (2774,2,3) A= {1-14}
`naradznea’on [Do
`
`n(siy =02) [scr|-
`(5)
`Brnicdon J; First we construct a two-level GC code as shown
`in Table I]. Ay and A» are LUEP codes with ponincreasing separation
`vectors
`
`
`
`
`
`8; = (811, $12, °°", $1ky,)
`
`52 = (S21, 522, °°", $2ki2)-
`
`As a special case, both A; and A», or one of them, may be chosen
`as equal error protection codes. If d211x%,, > d22821, then the GC
`code is a binary (nine, kiiko1 + ki2k22, s) LUEP code, where
`
`s=(daiS111k5,,° ane d2181ky,1k, ’ d225211 ko) os d2282ky,1k2) :
`
`where s1,,, denotes the k2; vector with all components equal to s.
`Obviously, [6, Construction 5]
`is a special case of the above
`construction.
`t
`If A; is an (n, 1, n) pees code, A» is anoptimal(n, k, s)
`__LUEP code, Be and Be are Reed—Muller codes with parame-
`ters (2", m + 1, iey ‘and (2™, 1, 2”) an optimal LUEP code
`equivalent to the code of [6, Construction 1] is obtained. Choosing
`-
`Bl”as the (2, 2, 1) code and B®)as the (2, 1, 2) code, theabove
`construction is equivalent to [6,Construction 3A].
`nes2:The GCCodegivenin TableIII hasthe param-
`
`
`
`
`
`_LUEPcode, we : with the inner
`
`a(2, 2, 1) code and B® is a
`, we obtain all the LUEP codes
`from van Gils in [1] and a class
`thecodes of [6, Construction 2]
`
`+n’, 1, ni +n’) repetition code
`
`Proof: For the proof we use Theorem 1. First we show that the
`GC code is optimal in length
`n(n, +n’, 2s) > ni tn+n(s) > 2ni + n'.
`Wenow have to show thatall codes with a greater separation vector
`also have greater length
`n(n +n’ +1, 2s) >mi +n’ +1+4+n(s)
`>2ni+n' +1
`>2nj +n’
`
`and
`
`‘n(n, +n',2stu)>nitn +n
`EEE] tobe
`>2n. +n' +1.
`Construction 3: The construction is guet in Table IV, where
`[82/2] denotes [s2:/2] for all i = 1, 2,---, hia.
`We suppose here that
`the outer code A is the code A‘
`(2;m1, ki2, 5)) with an added overall parity bit. With six,d) > no
`we obtain a new
`{nino +1, kirk + hie, mis: -++, 8x,d21z,, (n2 — 1)s9
`+2[s2/2]]}
`
`LUEPcode. Using the (2, 2, 1) and the (2, 1, 2) code as inner codes
`for j = 1, +++, m1, we obtain the LUEP codes [6, Construction 3B]
`of van Gils. If at the same time A; is a repetition code and A} is
`uncoded, the LUEP codes are the same as in [1, Construction B],
`ie., they are optimal.
`Choosing A; as a repetition code and Az as uncoded andthe
`(4, 3, 2) and (4, 1, 4) codes as inner codes for j = 1,---, m1,
`results in [1, Construction H] of van Gils.
`In the following examples we show the construction of some codes
`from [1] as GC codes,
`Example 2: The GC code given by Table V has the parameters
`n= 120
`(k= os — (555544).
`Example 3: The GC code given by Table VI has the parameters
`i lo hea bens — (905044),
`Example 4: The GC code given by Table VII has the parameters
`n=14, k=7)
`s = (5550444).
`For these three codes, see [1, Construction MJ]. IPR2018-1556
`HTC EX1052, Page 12
`
`IPR2018-1556
`HTC EX1052, Page 12
`
`
`
`plete code-
`
`IEEE TRANSACTIONS ON
`
`INFORMATION
`
`THEORY, VOL. 41, NU. 9) 98r omen 195
`
`[|
`
`1502
`
`Example 5: The GC code given by Table VIII has the parameters
`ne bee e (55554443) (See [1, Construction R)).
`
`IV. A DECODING ALGORITHM
`GC codes can be decoded by the well-known Blokh—Zyablov—
`Zinov’ev (BZZ) algorithm up to half their designed minimum dis-
`tance.For decoding GC codes with different inner codes we use the BZZ
`algorithm together with an appropriate metric.
`‘As shown in Section I,the designed minimum
`constructed codes is given by
`
`distance of the
`
`1=1, Dears IT | 1o:
`rithm: For each stage i, with
`Decoding Algo
`r in the inner codes to gei
`an
`Decode the received word
`TABLE VII
`1) estimated codeword O° of code Be for j €
`Ji.
`EXAMPLE 4
`2) Map these estimates BS, eo to the outer code
`L Outer codes
`Inner codes
`symbolsto get a; and use a) as reliability for position j of4;
`|
`
`j=1,2,3
`j=4
`
`
`
`BOT (2,241)|At(4,3,2) (0%4,2,3) i= (lr-ndd
`3) For} = 1. -+-, da,i Set the | positions with smallest relia-
`
`
`BO) (4,1,4)_(1,0,00)|42 (2;3,3,1) Ja = (1,233
`
`bilities as) to erasures and use an Error-and-Erasure Deceder
`
`(EED) to find a: {l}-
`4) Check if any 4: {i} satisfies Condition 1. If yes, ai = ai{I} is
`the final decision. If no, signal decoding failure.
`TABLE VIII
`EXAMPLE 5
`5) Continue with the next stage.
`[__Outer codes Inner codes
`we prove the following theorem.
`
`
`In the Appendix,
`algorithm will find the transmitted codeword as
`j=i4
`
`j=1,2,3
`
`
`BO (4,3,2) (3,3,1)|An (27,4, 2,3) Hy = {1,4}
`
`long as less than d/2 errors have occurred during transmission.
`Theorem 3: The
`Bt)
`(41,4)
`(3,1,3) Ay
`(2;4,4,1)
`Ty = {ld}
`For an LUEP code constructed as a (modified) GC code,
`it
`is
`desirable to be able to guarantee a correct decoding as long as at most
`|(s(@)i- 1)/2| errors have occurred in the transmitted codeword.If
`the outer codes in the above constructions have an equal protection
`of their information symbols, the described decoding algorithm can
`be applied directly and guarantees a decoding upto [(s(G)i—1)/2]
`errors. This isdue to theproperties ofthe multistage decoding. Similar
`to the BZZ algorithm, many error patterns of higher weight are
`1 BMD decoder for LUEP
`decoded too.
`The authors are not aware of a genera
`codes that corrects errors and erasures, and issues com
`words. Such a decoder would be necessary for the general case.
`However, if we again assume that the outer codes Ai
`in the con-
`structions are also GC LUEP codes with inner codesthat are not UEP
`codes, the decoding up to [(s(G)i — 1)/2] errors can be achieved
`by the algorithm for modified GC codes as described above. This
`is demonstrated for the first information symbol 7mwith separation
`s(G)i: first the inner codes By efor = iso
`are BMD
`decoded and an estimation for the outer code symbols 41,7+ together
`with the estimation of the reliability for these symbols a,
`. are
`transmitted to the outer code Ai. Since this codeis again a GC LUEP
`code with inner codes that are not UEPcodes, the aw represent the
`reliabilities for the code symbols of the inner codes Bo of the GC
`code A:. Proceeding in this way until the outer code is no longer
`an UEP code (this occurs in the worst case after ka.1 steps) finally
`allowsthe application of the above algorithm and a decoding of ™1-
`
`(7)
`
`Tha, 1s
`
`:
`
`da,i
`
`a
`
`d>min )/ 4m)"
`€ BO for
`to be the transmitted codeword, with ¢;
`Denote by 4: the transmitted codeword of the outer
`Define ¢
`and by 4; the estimate for di calculated by
`gols-tty Jmax-
`the result to symbols
`code A; with respect to ¢,
`decoding the inner codes of stage t and mapping
`of the outer code
`of the outer code alphabet. Let 4: be a codeword
`# a;. Define w
`A; and E(ai