`
`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
`
`
`
`111'
`
`(the “Philips Journal”). I copied the Cover page that contains a stamp showing that
`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, where I
`reViewed the article entitled “Future Trends in Optical Recording,
`Incmde
`.
`u
`'
`'
`of the Philips Technical Review, Vol. 44, no. 2, April 1988 (the Phlllps
`Review was
`l copied the cover page that contains a stamp SllOWing tllatt e
`111 S
`entered into UCLA’s collection on June 8, 1988. Attached hereto as
`
`rt
`”)
`
`.
`
`.
`
`,
`
`.
`
`.
`
`.
`
`-
`
`97 '
`
`d as pa
`
`ReVleW -
`
`.
`
`-t C iS a
`
`Exhlbl
`
`true and correct c0py of the cover page of the Philips Review.
`
`America that the foregoing is true and correct.
`
`
`Executed on August 16, 2018 in Los An
`
`
`Steve Wasserman
`
`|PR2018-1556
`
`HTC EX1052, Page 2
`
`IPR2018-1556
`HTC EX1052, Page 2
`
`
`
`Exhibit A
`Exhibit A
`
`|PR2018—1556
`
`HTC EX1052, Page 3
`
`IPR2018-1556
`HTC EX1052, Page 3
`
`
`
`
`
`IPR2018-1556
`HTC EX1052, Page 4
`
`
`
`IPR2018-1556
`HTC EX1052, Page 5
`
`
`
`
`IEEE INFORMATION THEORY SOCIETY
`
`The Inldrmation Theory SocietyIS an organization within the framework of the IEEE of members with principal professional interests'In information Eh
`All members of the IEEE are eligible for membership'1n the Society and will receive this TRANSACTIONS upon payment of the annual SOCiety membershjeory'
`of $15.00. For information on joining, write to the IEEE at the address below. Member copies of Transactions/Journals ore for personal use only
`Pie;
`BOARD OF GOVERNORS
`
`President
`BRUCE HAIEK
`Dept. Elec. & Compul. Eng.
`Coordinated Sci. Lab.
`University of Illinois
`1303 w. Main Street
`Urbana. IL 61801
`
`First Past President
`CHRIS D. HEEGARD.
`School of Elec. Eng.
`3211 Eng. leory Ctr.
`Cornell University
`lthaca. NY 14853—3801
`
`JULIA ABRAHAMS (‘96)
`ANDREW R. BARRON ('97)
`WNW K. BHARGAVA ('97)
`AUBREY BUSH (’95)
`A. R. CALDERBANK (‘96)
`
`First 1rice President
`JERRY D. GIBSON
`Dept. Elec. Eng.
`Texas A&M Univ.
`College Station. TX T7843
`
`Second Vice President
`SERGIO VERDI'J
`Dept. Elec. Eng.
`Princeton Univ.
`Princeton. N} 08544
`
`Secretary
`SERENA M. ZABIN
`School of Elec.
`and-Compul. Eng.
`Georgia Inst. Technol.
`Atlanta. GA 30332
`
`Treasurer
`TOM {rum
`Dept Elec Eng,
`Univeristy of “mind
`College Park, MD 20M).
`
`Second Past President
`STUART C. SCHWARI'z
`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. IR. (‘95)
`ANTHONY EPlIREMDES {’96)
`THOMAS ERICSON (‘95)
`
`THOMAS R. FISCHER (‘97)
`TOM FUJA (’9?)
`TB SUN HAN ('96)
`HIDEKI [MAI (‘95)
`
`Newsletter Editor
`RAMESH RAO
`Dept. Elec. «it Comput_ Eng.
`Univ. California. San Diego
`LaJ'olla. CA 92093
`
`SALEEM A. KASSAM (=95)
`JAMES L. MASSEY ('95)
`SI-ILOMO SHAMAI (51111-2) (-90)
`PAUL H. SIEGEL ('96)
`HEN'K VAN moons (‘96)
`
`E. ARIKAN
`At Large
`
`U. N]. MAURER
`Complexity and
`Cryptography
`
`T. M. COVER
`Book Reviews
`
`B. HUGHES
`Detection
`
`IEEE TRANSACTIONS ON INFORMATION THEORY
`R. E. BLAHUT, Editor
`J. A. O'SULLWAN, Publications Editor
`Associate Editors
`T. HDHOLDT
`P. V. KUMAR
`Coding Theory
`Coding Theory
`
`II. [MAI
`Coding Theory
`
`P. H. SIEGEL
`Coding Techniques
`
`A. JUDITSKY
`Estimation
`
`A. HERO
`Signal Processing
`
`A. R. BARRON
`Nonparametric
`Estimation.
`Closstjictttion. and
`Neural
`Networlut
`Please refer to inside back cover for insu'uctions on submitting manuscripts.
`
`T. S. HAN
`Shannon Theory
`
`C. N. GEDRGHIAD-
`Communications
`
`R. CRUZ
`Conununicotion
`Newark:
`N. FARVARDHH M FEDER
`Source Coding
`Source Coding
`
`THE INSTITUTE OF ELECTRICAL AND ELECTRONICS ENGINEERS, INC.
`Officers
`
`JOEL B. SNYDER. Vice President. Pmfissional Activities
`JAMES T. CAIN. President
`W. KENNETH DAWSON. Vice President, Publications
`WALLACE S. READ. President-Elect
`VIJAY K. BILARGAVA. Vice President. Regional Activities
`CHARLES W. TURNER. Secretary
`E. G. KENER. Vice President, Standards Activities
`V. THOMAS RHYNE. Treasurer
`BRUCE BISENS'IEIN. Vice President. Technical Activities
`KENNETH R. LAKER. Vtce President. Educational Activities
`THEODORE W. HJSSEY. JR., Executive Director
`TZYH-JDNG (T.J.) TARN, Director, Division X—Systems and Control
`
`Headquarters Stall
`RICHARD D. 81:me Acting General Manager
`PHYLLIS HALL. Stqfl' Executive. Publications
`FRANK R. MOORE, Stafi Executive. Volunteer Activities
`IRVING ENGELSON. StafDirector, Corporate Activities
`ANDREW G. SALEM. Stquirectar. Standards Activities
`PETER A. LEWIS. $1013r Director. Educational Activities
`W. 'I‘HOMAS Sums. Stqfl' Director Professional Acmmfl‘
`MELVIN I. OLKEN. Staff Director. Regional Activities
`Roam T. WARM. MDirector Technical ACII'WMS
`Itamcllonsljourmls Deparhnent
`StafDirector: PATRICIA WAIm
`Manager GAIL 8331:3111:
`_
`Electronic Production Manager: IBM L. U220
`Managing Editor: VALERIE CWTA
`Senior Associate Editon Neu— RYBOWIILZ
`
`-
`
`..
`
`2W figlncets. Inc. mum f“ ‘
`contents rests upon the authors and not upon the IEEE. the SocietleomchL or its mm. IEEE
`ark,
`IEEE TRANSACTIONS ON INFORMATION THEORY is published bimonthly by the Instinne'of Electrical and
`018cc: 345 East 4701 Street. New Y
`”I. i
`_ W (908) 981-0060.
`_
`10017-2394. IEEE Operations Center: 4-45 Hoes lane. P..0 13011331 Enemy HI .08855
`-
`Information: Individual copies. IEEE Members $10.00 (first copy only). noummbm '
`'
`'
`It? Add 34:00 postage and handling "
`
`
`any order from $100 to $50.00 including prepaid crdera.)Mmberendnmmnbersub‘mpdm;ucce
`;
`'mmhflflmiflM'
`
`'
`'
`-
`microfilm Copyright and Reprint Pendulum: Autumn;
`.
`_
`to
`_'-
`for.
`
`-
`'
`-.-
`.
`_
`.
`‘
`,
`__
`of pan-ens, provided the per-copy fee indicated-to
`.-
`'
`Center.
`
`‘
`-
`_-.
`,
`'
`-
`_ We
`Drive, Danvers, MA 01923. For all
`_
`'
`
`Administration. 445 Hoes Lane. 13.0.
`'
`'
`' 1nd Eamon!“ * {I‘ 'L'
`'Allrightsreserved. Second
`_.
`ON INFORMATION Tammi;-
`Printed in USA-
`
`,
`|PR2018-1555‘
`
`' EX1052, Page 6
`
`..
`
`-
`
`
`
`IPR2018-1556
`HTC EX1052, Page 6
`
`
`
`
`
`HTC EX1052, Page 7
`
`|PR2018-1556
`
`IPR2018-1556
`HTC EX1052, Page 7
`
`
`
`—*
`
`nmb
`
`INFORMATION FOR AUTHORS
`
`RMATION THEORY is
`on INFO
`eoretical and experi'
`'shes th
`.
`processmg,
`the transmissmn.
`f acceptable
`ited. Rather,
`
`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 manner similar to that for the PROCEEDING OF THE
`IEEE. “Information for IEEE TRANSACTIONS and JOURNAL
`Authors” is available from the IEEE Transactionslloumals
`Department, 445 Hoes Lane, Piscataway, NJ 08855. For
`further details, see “Advice to Authors." IEEE 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 lNFORMA'IION 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 include all 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.
`f the IEEE to own the copyright
`Copyright: It is the policy 0
`ishes on behalf of the
`to the technical contributions it pub]
`
`facilitate the appropriate re
`.
`‘
`‘
`,
`comply with the US. Copyrig
`Sign an IEEE Copyright Form before publication. This form
`which appears in the January issue of this joumal..returns-to
`authors and their employers full rights to reuse their material
`for their own purposes. Authors are required to submit a Signed
`.
`.m th .
`.
`ts.
`copy of this form w1
`eir manuscnp |PR2018-1556
`HTC EX1052, Page 8
`
`
`
`'
`
`-
`
`_
`
`B
`' side front cover.
`n the m be in the form of regular papers or of
`not one of quality, but of
`11110115 may
`,
`.
`The distinction is
`a con-espondeiice item will have one point to
`without adorninent, whereas an regular paper
`are well-rounded treatment of a problem area.
`“tigers-lbflions should comprise novel and previously un-
`pubncehsehdedjngl::t:nan' abstract, summary, or other abbreviated,
`preliminary form of the material shall not preclude publica-
`don in this journal when notice of such prior or concurrent
`time of submission. The novelty
`publication given at the
`.
`‘nal results, methods. observations,
`will usually lie in ori
`concepts. or 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 of prior 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-
`.
`' marl! should be sufficiently informative to make the gist of the
`_ paper clear to the broadest possible audience and to place the
`. connibutions of the paper in context with related work. The
`' body 01' the paper should be underutandablc without undue
`effort by its intended audience, Supporting material not of
`- mm! interest is best relegated to appendixes;
`Afigsgndenee should 5‘". less discursive but equally lucid.
`Duld beam. that a wen-written correspondence
`
`Warmth“ can-maximum-
`
`
`fl“ Wk Wigs ”f 3““ “we“
`and illustrative-
`Cu Immune Signed copy of the IEEE
`'
`lathelastparagraphlfthereis
`
`1): essential for the reviewing
`filth? reviewers (cg, prepflnts)
`
`reviewing process, au-
`
`w figmlevant excerpts. Each
`
`rmuve abstract of not
`
`must include an abstract
`
`__ flf Wax terms (key words
`
`i
`the abstract, a total of
`m terms should be relatively.
`" thuld characterize the paper.
`
`abstract and references,
`
`
`IPR2018-1556
`HTC EX1052, Page 8
`
`
`
`
`
`IPR2018-1556
`HTC EX1052, Page 9
`
`
`
`
`i.
`_
`
`13135
`
`MACTIONS ON INFORMATION THEORY. VOL. 41. NO. 5. SEPTEMBER 1995
`
`1499
`
`
`
`The author would also like to acknowledge stimulating discussions
`with 0. Amranl and F.—W. Sun. FIDHHY. the author wishes to thank
`kowitz for her invaluable help.
`sari! "1
`
`Modified Generalized Concatenated
`Codes and their Application to the
`Construction and Decoding of LUEP Codes
`
`REFERENCES
`
`Uwe Dettmar. Yarl G210. and Ulrich K. Sorger
`
`[2]
`
`_
`
`i.
`
`a.
`
`I...” ‘
`
`.
`‘
`l.
`“it
`Mi;
`in.)
`‘t
`
`r.
`iii:
`Mil:
`
`!“
`1:.
`12-.
`‘1.
`{1'1
`m":-
`x
`I)
`. In:
`grin!
`hill:
`
`[l] A. D. Abbaszadch and C. K- RUSthflh. “VLSI implementation of a
`maximum likelihood decoder for the Golay (24.12] code." IEEE J.
`Selected Areas Common. vol. 6. pp. 558—565, 193:;
`0. Amrani and Y. Be'ery. "Efficient bounded'distance decoding of the
`hexacode and associated decoders for the Leech lattice and the Golay
`code." in pm: IEEE Int. Symp. on Information Theory (Trondheim.
`_
`'
`Norway! 1994) P- 400'
`[3] 0. Ammfll. Y_- 35 cry. and A Vardy. “Bounded-distance decoding of
`the 1459“" lattice and the GUI” C006." Lecture Notes Compni. Sci. vol.
`781. pp. 236—247. 1993.
`[4] 0- Ami. Y- BF’CW- A- ley, F--W. Sun. and H. c. A. van TllbOt'g,
`"Hie Leech lattice an" the (3013)? code; bounded-distance decoding
`and multilevel constructions“ IEEE Trans. Inform. Them-y. vol. 40. pp.
`10301043. 1994-
`{5] E. F. Assmus. Jr. and H. F. Manson. Jr.. “Algebraic theory of codes."
`R39, 1. Contract F19628—69C0068. Air Force Cambridge Res. Labs.
`Bedford, MA. 1959.
`.
`[5] Y. Be'ery and B. Shelter. “VLSI architectures for soft decoding of
`the [fed] lattice‘and the Going codes." in Proc. IEEE Int. Workshop
`or! Microelectronics in Communications (Interlaken. Switzerland, Mar.
`1991).
`{7] Y. Bc’ery. B. Shahar, and J. Snyders. “Fast decoding of the
`Egg? lattice." IEEE J. Selected Areas Common. vol. 7. pp.'959—967.
`[8] Y. Be‘ery and J. Snydcrs. “Optimal soil decision block decoders based
`'1 oi
`. on Fast Hadamard Transform." IEEE Trans. Inform. Theory. vol. IT-32.
`11h:
`pp. 355—364, 1986.
`(til;
`[9] AR. Calderbank. Bandwidth Eficienr Communication.
`tion.
`-
`.
`
`'. ['10] J. H. Conway and N. J. A. Sloane. “Soft decoding techniques for codes
`
`and lattices. including the Golay code and the Leech lattice," IEEE
`Iii-ans. Inform Theory. vol. IT-32. pp. 41-50. 1986.
`‘..
`'.
`
`Ill] _. Sphere Packings. lattices and Groups. New York: Springer—
`.
`
`Vedag. 1988.
`.
`
`[12] M. V. Eyuboglu and G. D. Fomey. Jr.. “Lattioe and trellis quantizao
`
`'
`lion with lattice- and trellis-bounded codebooks—whigh-rate theory for
`_
`unmoryless sources." IEEE Trans. Inform Theory. vol. 39, pp. 46—59,
`
`19.93.
`-
`
`.Ir.. “Generalized minimum distance decoding," IEEE
`D. Fomey,
`
`The)”. Worm. Theory, vol. IT-12. pp. 125-131. 1966.
`
`4} _. "Ccset codes I: Introduction and geometrical classification," IEEE
`_
`
`I W8. Inform. Theory. vol. 34. pp. 11234151. 1988.
`
`.—.._._... ‘Coset codes I]: Binary lattices and related codes.“ IEEE Trans.
`
`on. ”teary. vol. 34. pp. 1152—1187. 1938.
`
`~_—. “A bounded distance decoding algorithm for the Leech lattice,
`
`_
`'
`figmahzations," IEEE Trans. Infonn. Theory. vol. 35. pp. 906—909,
`
`1’ fl —_. “Dcnsityllcngth profiles and trellis complexity of lattices." IEEE
`
`Tim. Inform. Theory, vol. 40. pp. 17534772. 1994.
`
`G.- R. Lang and F. M. Longsioir. “A Leech lattice modern," recs J.
`
`Selected Areas Common. vol. 7. pp. 968—973. 1989.
`_.
`.
`' 9] 1 Snyders and Y. Be‘ery. “Maximum likelihood soft decoding of binary
`.
`
`block codes and decoders for the Golay codes." IEEE onus. Inform.
`
`' m Theory. Vol. 35. pp. 963—975, 1939.
`'
`
`.' _. l F.-W. Sun and H C. A. van Tilborg. “Mme efficient bounded-distance
`
`decoding of the Golay code and the [reach lattice." in Proc. IEEE Int.
`
`[21] SW- 0” Infomtation Theory (Trondheim. Norway. 1994). p. 399.
`
`--—. "The Leech lattice. the octacode. and decoding algorithm.” IEEE
`
`1 21m Wat-Ln mom vol. 41. no. 4, pp. 1097-1106. July 1995.
`
`M. VWY- A new sphere packing in 20 dimensions." Inventions:
`
`-Woe, vol. 121. no. 1, July 1995.
`' 9" Vardy- and Y- Be’ery. “More efficient sofiedecision decoding of
`
`I.
`‘ 1 39-9919? ms IEEE nuns Minolheom vol. 37. pp. 667—672.
`
`
`decoding crate Leech lattice,” ices
`
`1435—1444, 1993.
`
`in prepara-
`
`Abstract—We propose a modification of generalized concatenated codes.
`which allows us to construct some of the best known binan codes- in
`a simple way. Furthermore, a large class of optimal
`linear unequal
`error protection code; (LUEP codes) can easily be generated. All um-
`structed codes can be efficiently decoded by the BlokhoZyahlovVZlnm-‘i v
`algorithm if an appropriate metric is used.
`
`Index Tamas—Linear unequal error protection codes. generalized con-
`catenated codes, multistage decoding.
`
`I.
`
`INTRODUCTION
`
`Many of 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 n.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 it... ,-, and
`inner codes BE” in the columns of the code matrix with different
`lengths no, ,- and distances (13)]. together with their partitions.
`In Section 1]. 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 1]].
`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.
`For the sake of simplicity only binary codes are considered in this
`correspondence. An extension to the nonbinary case is straightfor-
`ward.
`
`II. Damon OF MODIFIED GC Cones
`
`_ GC codes are a generalization of concatenated codes defined
`by 'Forncy [4]. The inner code is multiply partitioned, and this
`partitioning into subcodes is protected by different outer codes.
`Denote the in outer codes by A.- = {in-((1.; n... k.._.-. d..,.-). where
`q.- = 2" is the alphabet size. n...
`is the code length. In.“-
`is the
`number of infomation symbols. and d.“- is the Hamming distance
`of the code. Further. denote by B“) = EMU}; n... In“; 03...). for
`t’ = 1. 2. ---, m. the binary inner codes. where
`
`3““) C BU)
`
`and
`
`kin _ k£i+ll
`
`= log2 ((1.).
`
`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 filr Netzwerk- und Signaltheorie, Techni-
`sehc Hochschule Darmstadt, 13-64283 Dannstadt. Germany.
`IEEE Log Number 9413060.
`
`001849448I9§$0430 o 1995 [EBB
`
`|PR2018-1556
`
`HTC EX1052, Page 10
`
`IPR2018-1556
`HTC EX1052, Page 10
`
`
`
`1500
`
`IEEE TRANSACTIONS ON INFORMA'I'IDN THEORY, voc. 41. NO. 5, SEPTEMBER M5
`
`TABLE I
`EXAMPLE I
`
`Inner codes
`[——
`Outer codes
`L GC code
`i
`
`j:1.2.....s
`j=9
`j:10|
`|
`
`
`3‘
`(3.4.4)
`(4.1.4)
`(7.3.4)
`(23:10.7b1l.3) J, : {1.....lfl}
`(75,11,321
`
`BE"
`(3.1.3)
`(4.0m)
`[7.0.00]
`(28.4.4)
`7; — {1
`}
`-
`
`JG ={1.....10} (75.13.30)‘
`3)“
`(3,4,4)
`(4.3.2)
`(13.41
`A1
`(23:10.3.8)
`3‘“
`(8.1.81
`(4.0.00)
`(7.0.oo1 A;
`(2:51.414)
`.72={1----.S}
`
`
`p
`
`arameters 3
`]
`[
`H = "a ”b
`m
`1:: 21km .logg (‘11)
`'1:
`d 2 n1i11{da,2db.1-1 da.2dh.29 "'1 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 m ¢ 0, with a1 6 At, then not less than dd, 1 codewords of
`the inner code B“) are difi'erent from the zero word. However, this
`inner code has a minimum weight db, 1 which leads to a minimum
`weight of 11¢;de 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 on.
`However, this restriction is not necessary: denote the outer codes by
`
`A: :Ai(9i: "11.1-3ka 1-1 dm 3')
`
`where the 11a. . now can be different. Define a set of indices ,7.- with
`L5“ = na.i and jmax so that
`
`ISjSJ'maxa VJEtyI
`
`holds. The inner codes are given by
`
`B§l=3§‘;’(2 n j,k£f;,d§)-)51.!
`
`fort: 1, 2. "u m and] = 1: "'vJ'mm" With
`
`(i+1)
`
`BJ.
`
`(g)
`
`QBJ-
`
`(i)
`
`andirb’j—kbly {0, 2
`
`(i+1)_10g (9!)!
`
`ifj E ‘7'
`
`ifjgj;
`
`We assume that Uh};- = .7, withj E J forj = 1, 2, ---,jmu,
`because in this case all inner codes are concatenated with some outer
`codes.
`
`The GC code has the pararneters
`
`n: 2 nb'J-
`
`16:2 ka,i10g2 (40°
`i=1
`
`The minimum distance of the GC code is given by
`
`a > min min 2 ag"
`5'
`1'65.-
`
`‘
`
`(1)
`
`where S.- Q .7.- With [Sgl = dc”;
`The lower bound for the minimum distance is derived similarly
`to that for conventional GC codes: the minimum weight in stage 1'
`is attained if the positions where a.- 9’: 0 coincide with codewords
`of the inner codes B?) with the smallest minimum distances. This
`leads to (1).
`
`To simplify this expression, we define by l'l(j) the permutation of
`the indices 3' = 1,-‘-, nu..- so that
`
`dorm) S danrz) S‘ 'S dial—Hun”)-
`
`This results in
`
`_
`
`da‘ ‘5
`d 2 “iii“ 2 d5?)no)
`
`'
`he .
`
`I
`
`TABLE [I
`CONSTRUCTION l
`
`
`Inner codes
`[
`Outer codes
`
`
`j : 11-"11111
`i
`3}
`(n3,k21+kzg,d‘gl)
`A1
`(zenithhhsll 31—.“,,,,,1.11}
`
`Bi”
`(flat-hmdnl
`A: meantime)
`31—. {1at}
`
`1
`i
`
`Example I: The (75,113?) and the (75.13.30) code from [5}
`can be constructed as given in Table 1.
`
`IE. OPTIMAL LUEP Cones Consrnucran as GC Coons
`
`if
`Linear unequal error protection (LUEP) codes can be useful
`different information symbols have different importance. In [1] and
`[6], van Gils proposed constructions for some special classes of LUEP
`codes (some of them based on product or concatenated codes). In [7],
`Zinov’ev investigated the application of GC codes on the construction
`of LUEP codes. but these constructions only work for composite code
`length, i.e., n = nuns. 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 LUEP code is characterized by its separation vector [6].
`Definition 1: For a linear (n, k) code C over the alphabet Gth).
`the separation vector 3 = (31 , 92.,
`-
`- - . s 1;) with respect to a generator
`matrix G of C,
`is defined as
`
`3,1: min{wt{mG|m e Gr(q)*, m. sé 0}. s: 1. -
`
`- -.r-}
`
`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.
`s.- 2 3, ifz' < j W, 3' E {1- -l..}. Note that dris definition is
`different from that in [8] as it deals with information symbols instead
`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 “MGM - 1V2] errors
`have occurred in the transmitted codeword [10].
`An (in, k, 8) code is called optimai if an (n. F". t) code with: > 8,
`Len t1 2 3.- Vi E {Lu-Jr} and Etj e {1.o--.t-}:rJ > sJ. does
`not exist. Denote by 11(8) the length of the shortest linear binary
`code of dimension In: with separation vector at
`least 5 and denote
`n" (s) the lengthof the shortest linear binary code of dimension k
`with separation vector (exactly) 3. Van Oils [1]. [l I], has derived the
`following lower bounds on n(s):
`Theorem 1. For any i: E N. and nonincreasing s E M
`
`”£1131; 329"'13k)23i+n(§l,"'5iii—1. §i+1r"'w§i&}
`
`(2)
`
`holds for any i E {1, - - - , k}. where
`s.-
`s- -— — ,
`
`|PR2018—1556§j :2
`
`izi
`’
`[is],
`
`HTC EX1052, Page 11
`
`for
`
`.
`<2
`
`.
`
`’
`
`for j>i.
`
`(31
`
`[x] denotes the smallest integer larger than or equal to r.
`
`IPR2018-1556
`HTC EX1052, Page 11
`
`
`
`-
`
`1595 TRANSACHONS ON INFORMATION THEORY. 1101.. 41. N0. 5. SEPTEMBER 1995
`
`:11}
`1‘
`
`TABLE In
`CONSTRUCTION 2
`| 0 1.: tot codes
`1
`In her cod es
`j:1,...,n]
`J-n1+l ...,n]+n
`
`1 |
`
`
`FEET
`("IM1)
`(”E—kmni‘kliF. A1
`t2"""’;n1+n'.ku.!1)
`Ji={1s---1“1+fl'}
`
`3‘,”
`
`1:11.11 an)
`
`("z—k210<‘3°}
`
`A:
`
`121:;n,,1.,,.,3
`
`J, = {1.1.1111}
`
`TABLE 1V
`CONSTRUCTION 3
`
`
`|
`Inner codes
`‘
`l
`Outer codes
`
`j=fl1+1|
`I
`j:1,...,fl]
`I
`
`
`
`
`1. mamas.)
`inz.kz+ 1111)
`11.1.1)
`
`
`
`A:
`(21"1+11k1212i5’11’2])
`(“2,1,“)
`(1,1,1)
`
`
`171 = {1.1.1111}
`J? = {11"'tn1+1}
`
`
`TABLE V
`
`EXAMPLE 2
`
`I—n—Inner codes
`l Outer codes
`.
`_
`— -_‘.
`
`
`
`
`i=1
`j:213
`i=4
`
`
`12.2.11
`1, 12:22.31 J1
`1
`1413.21
`13.2.21
`11 2]
`(1,1,4)
`(3,0,eo)
`(1.11.1301
`111
`1'2: 1.1.1)
`
`
`
`TABLE VI
`EXAMPLE 3
`
`
`O 11 let codes
`L
`Innercodes
`j:l,2 1:3
`(1,3,2)
`(3,2,2)
`
`B,‘
`
`i121“?
`
`(1,1,4)
`
`(3.11.110)
`
`(1,0,00)
`
`i=4
`{2.2.1} A.
`
`
`
`11
`
`J
`—"1
`(22:42.3) J.:{1....,4}
`
`21:11.2} i
`
`(2:22.11
`
`theorem 2" For any k E N- and nonincreasing s E N", 11(3)
`satisfies the inequalities
`
`.111, ,111111.qs,211., 1a)
`
`3k) 2
`
`[2%,].
`
`(5)
`
`Construction I: First we construct a two-level GC code as shown
`in Table 11 A1 and A2 are LUEP codes with nonincreasing separation
`vectors
`
`51 = (811., 312. ' " 1 811111)
`
`as = (821, 822, 1 ”1321113).
`
`As a special case, both A1 and A2, or one of them, may be chosen
`as equal error protection codes. If c121 an,” 2 dggszl, then the GC
`code is a binary (111112, km k2; + klgkgz, a) LUEP code, where
`
`and
`
`8=(d2181111=211“' 16121311111121.112232111221'"1
`
`03223211121112)
`
`.
`
`where 311,2 denotes the Ice,- vector with all components equal to s.
`Obviously, [6, Construction 5]
`is a special case of the above
`wnsuuction.
`
`_
`
`HA1 is an -{n, 1, n)repetition code, A: is an- optimal (n, Ir, a)
`' LUEP code, Bo) and 5? are Reed—Muller codes with parame-
`'911163”. to +' '1, 2m 1) and (2m,1,2’") an optimal LUEP code
`eq(uivalent to the code of [6, Construction 1] is obtained. Choosing
`'
`,Bl" asthec2, 2 1)eodeaid3§.)asthe(2, 1, 2)eode, thcabove
`13011;111uction'ls equivalent to. [6,. Construction 31A].
`_ Common.,21_-.. The dc.Code.given in Table. 111 has the param-
`
`
`
`a"(2, 2'; I)-e"ode and B?) is a
`
`,we obtain all the LUEP codes
`
`"fi‘Om van Gils-in‘ [l] and-a class
`
`file'codes of- [6,- Construction 2]
`
`
`
`y+ 11,1,111 + n') repetition code
`_
`1321'code, we get with the inner
`
`onoptima] (2n1+n, 1+k, (111+
`
`can be shown as follows:
`
`'Praofi For the proof we use Theorem 1. First we show that the
`GC code is optimal in length
`
`1181(111 + 11’, 2s) 2 "1+“: + 71(11): 2111+ n'.
`
`We now have to show that all codes with a greater separation vector
`also have greater length
`
`n“(n1 + n' + 1, 2s) 2 111 + n' + 1 + 11(8)
`
`2 2111+ 11’ +1
`
`>211; +11!
`
`‘12”(111 + 11’, 2s + u) 2 111 + nl + n,
`
`writ-w
`22n1+n'+l.
`
`[511 + 1111])
`
`Construction 3: The construction is given in Table IV, where
`fag/2] denotes [Szi/2-I for all i =1, 2,
`,ku
`We suppose here that
`the outer code A2 is the code A;
`.
`(2; 111, km, 32) with an added overall parity bit With Slkldg > n:
`we obtain a new
`
`{“1112 + 1,-k11k2 + kin, [3111211121 "'1 311112112. {712 — 1)s'2
`+2lsE/2ll}
`
`LUEP code. Using the (2, 2, 1) and the (2, 1, 2) code as inner codes
`for j = 1, -- -, 121, we 'obtain the LUEP codes [6, Construction 31-3]
`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],
`i.e., they are optimal.
`Choosing A1 as a repetition code and A2 as uncoded and. the
`(4, 3, 2) and {4, 1, 4) codes as inner codes for j = 1, ---, 111,
`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
`11 = 12,
`k = 6
`a = (555544).
`Example 3: The GC code given by Table VI has the parameters
`11 = 13,
`k = 6
`a = (555544).
`Example 4: The GC code given by Table VII has the parameters
`11 = 14,
`k—— 7
`s = (5555444)
`IPR201 8- 1556
`For these three codes, see [1, Construction M]
`HTC EX1052, Page 12
`
`IPR2018-1556
`HTC EX1052, Page 12
`
`
`
`INFORMATION THEORY. V01... 41,
`
`NU. 3. star tuiuuun Huh
`
`
`
`decoded too.
`The authors are not awar
`codes that corrects errors an
`Such a decoder would be nec
`words.
`ain assume t
`HOWever, if we ag
`structions are also GC LUEP codes with inner codes t
`codes, the decoding up to Lis(G),- — 1”?) errors can
`by the algorithm for modified GC codes as descri
`is demonstrated for the first information symbol on with separation
`5(6)]: first the inner codes B30) , for} : 1,
`its, 1, are BMD
`decoded and an estimation for the outer code symbol
`_
`.
`to?
`with the estimation of the reliability for these symbols oJ
`.
`transmitted to the outer code Al. Since this code is again a GC LUEP
`code with inner codes that are not UEP codes, the 030) represent the
`reliabilities _for the code symbols of the inner codes 1350}: of the GC
`eding in this way until the outer code is no longer
`an UEP code (this occurs in the worst case after if“. 1 steps) finally
`allow the application of the above algorithm and a decoding of m 1.
`
`ISOZ
`
`I
`
`l
`
`TABLE VII
`EXAMPLE 4
`
`1— Outer codes
`
`Inner codes
`j: 1,2,3
`
`BJ'
`
`BE”
`
`(4,3,2)
`
`{4.1.4}
`
`i=4
`:1]
`(2,2,1)
`(1,0,00) A;
`
`{2’;4,2,3)
`(2:3.3.”
`
`J; = {1.....4}
`J; :- {1.2.3}
`
`TABLE WI
`EXAMPLE 5
`LOuLer codes
`
`Inner codes
`j=l,2,3 i=4
`(3.3.1} A.
`(4.3.2)
`(3.1.3)
`112
`(4,1,4)
`
`a'
`of.”
`
`|
`
`(2’;4.2,3)
`(2:4,4,1)
`
`J,={1,,..,4}
`J;={i,m.4}
`
`ble V111 has the parameters
`Example 5: The GC code given by Ta
`n = 15.
`is = 8
`s = (55554443) (See [1, Construction RD.
`
`IV: A DECODING ALGORITHM
`coded by the well-known Blokh—Zyablov—
`GC codes can be dc
`to. half their designed minimum dis-
`Zinov’ev (BZZ) algorithm up
`lance.
`rent inner codes we use the B22
`For decoding GC codes with diffe
`algorithm together with an appropriate metric.
`As showu in Section H,'the designed minimum distance of the
`constructed codes is given by
`
`IEEE TRANSACTIONS ON
`_ ”L 3“:
`Decoding Algorithm: For each stage i, with i = 1. 2.
`1) Decode the received word :-
`in the inner codes to pp;
`in
`estimated codeword b5” of code BE," for j 6 5‘2.
`2) Map these estimates b3"),
`j = 1,
`n.“ to the Outer i- dc
`symbols to get (i. and use cut-S“) as reliability for position 3 in;
`,I
`3) For I = 1.
`d,,_.- set the 1 positions with smallest reg-d.
`bilities 03’) to erasures and use an Error-and-Erasure Decl-‘dCr
`(EED) to find (“{I}.
`4) Check if any (1,-{1} satisfies Condition 1. If yes, a,- : a,{]} is
`the final decision. If no. signal decoding failure.
`5) Continue with the next stage.
`e the following theorem:
`In the Appendix, we prov
`e transmitted codeword as
`Theorem 3: The algorithm will find th
`uring transmission.
`long as less than d/2 errors have occurred (1
`is
`it
`dified} GC code.
`For an LUEP code constructed as a (mo
`long as at most
`desirable to be able to
`correct decoding as
`[(s(G).- -— 1}]2] errors have oceurred 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 up to L{ s-(G). — l l/‘ZJ
`f the multistage decoding. Similar
`errors. This is due to the properties 0
`to the 32.2 algorithm, many error patterns of higher Weight are
`l BMD decoder for LUEP
`plete code—
`
`to be the transmitted codeword, with c,- E BE” for
`Define c
`Denote by ii.- the transmitted codeword of the outer
`and by d.- the estimate for (hf calculated by
`j=ls"'tjmax-
`Code A.- with respect to c,
`decoding the inner codes of stage i and mapping the result to symbols
`of the outer code alphabet. Let a.- be a codeword of the outer code
`be the set of indices 3' such that a; # (it. Define to
`A and £(at, 5i)
`_
`to be the cardinality of £(cn, in). Denote by «9"‘(ciI oi) the da, .; _— to
`components in
`
`5' = {1, -
`
`-
`
`- , na_i}/£(ai. at)
`
`following
`
`with the smallest of).
`An appropriate reliability function is given by the
`definition:
`dis);- be the min