`
`EUROCO
`
`'90
`
`d ppb
`
`t1 n
`
`IPR2018-1556
`HTC EX1018, Page 1
`
`
`
`Lecture Notes in Computer Science
`
`514
`
`Edited by G. Goos and J. Hartmanis
`Advisory Board: W. Brauer D. Gries J. Stoer
`
`IPR2018-1556
`HTC EX1018, Page 2
`
`
`
`G. Cohen P. Charpin (Eds.)
`
`EUROCODE '90
`
`International Symposium on Coding Theory
`and Applications
`Udine, Italy, November 5-9, 1990
`Proceedings
`
`Springer-Verlag
`Berlin Heidelberg NewYork
`London Paris Tokyo
`Hong Kong Barcelona
`Budapest
`
`IPR2018-1556
`HTC EX1018, Page 3
`
`
`
`Series Editors
`
`Gerhard Goos
`GMO Forschungsstelle
`Universitiit Karlsruhe
`Vincenz-Priessnitz-Stra8e l
`W-7500 Karlsruhe, FRO
`
`Juris Hartmanis
`Department of Computer Science
`Cornell University
`Upson Hall
`Ithaca, NY 14853, USA
`
`Volume Editors
`
`Gerard Cohen
`Ecole Nationale SupCrieures des Telecommunications
`46, rue Barrault, 75634 Paris Cedex 13, France
`
`Pascale Charpin
`INRIA, B.P.105, 78153 Le Chesnay, France
`
`CR Subject Classification (1991): E.4, E.3
`
`ISBN 3-540-54303-1 Springer-Verlag Berlin Heidelberg New York
`ISBN 0-387-54303-1 Springer-Verlag New York Berlin Heidelberg
`
`This work is subject to copyright. All rights are reserved, whether the whole or part of
`the material is concerned, specifically the rights of translation, reprinting, re-use of
`illustrations, recitation, broadcasting, reproduction on microfilms or in other ways, and
`storage in data banks. Duplication of this publication or parts thereof is only permitted
`underthe provisions of the German Copyright Law of September 9, 1965, in its current
`version, and a copyright fee must always be paid. Violations fall under the prosecution
`act of the German Copyright Law,
`
`© Springer-Verlag Berlin Heidelberg 1991
`Printed in Germany
`
`Printing and binding: Druckhaus Beltz, Hemsbach/Bergstr.
`2145/3140-543210 - Printed on acid-free paper
`
`IPR2018-1556
`HTC EX1018, Page 4
`
`
`
`Preface
`
`is a continuation as well as an
`Eurocode 90, held in Udine, Italy, 5.9 November 1990,
`extension of the previous colloquia "Trois Journees sur le codage". The previous ones took
`place in Cachan, France in 1986 and Toulon, France in 1988 ; their proceedings appeared as
`Lecture Notes in Computer Science, Volume 311 (G. Cohen, P. Godlewski, eds.) and Volume
`388 (G. Cohen, J. Wolfmann, eds.) respectively. The Udine meeting gathered approximately
`one hundred scientists and engineers.
`
`These colloquia are characterized by a very broad spectrum, ranging from algebraic
`geometry to implementation of coding algorithms. We would like to thank the referees (see
`enclosed list) with a special mention for P. Camion, J. Conan, A. Thiong Ly andJ. Wolfmann,
`as well as C. Dubois, secretary of "projet code INRIA" and N. Le Ruyet for help in editing.
`
`1 Algebraic Codes
`
`The construction of spherical codes is now a classical problem related to important special
`cases, as showed by Delsarte et al. (1977). In their invited paper, Ericson and Zinoviev
`propose a new construction, improving the method of generalized concatenation. Following the
`work of A. Dilr, two papers deal with the structure of Reed-Solomon codes. Elia and Taricco
`present new results on code automorphism groups which imply some properties on covering
`radius and coset weight distribution of RS-codes. Berger gives a new basis describing primitive
`cyclic codes of length q · 1 over Fq ; as an application he obtains directly the group of some
`automorphisms of the RS-codes. Beth, Lazic and li'enk present a very simple construction of an
`infinite sequence of self-dual codes ; properties of the first four codes imply a conjecture on the
`distance distribution.
`
`The following two papers are devoted to open problems on Reed-Muller codes. Carlet shows
`that the weight of an RM-code of any order is related to the weight distribution of an RM-code
`of order 3 and greater length. Langevin studies the covering radius of the RM-code of order 1
`and length 2m, for small odd m; he obtains a bound form= 9.
`
`In his paper, Rodier constructs codewords in the dual of binary BCH-codes of length 2m • I,
`for an infinite number of m ; he can disprove a conjectured improvement of the Carlitz(cid:173)
`Uchiyama bound. Augot, Charpin and Sendrier present an algebraic point of view in order to
`prove or disprove the existence of words of given weight in binary primitive cyclic codes of
`short length.
`
`2 Combinatorial Codes
`
`The next three papers are devoted to less classical coding problems. Burger, Chabanne and
`Gira ult deal with the construction of Gray codes with an additional constraint that O· 1
`transitions should be evenly distributed, to provide, e.g., uniform wearing of memories.
`Mabogunje and Farell construct unequal error protection codes based on array codes and give
`simulation results for their bit error rates. Cohen, Gargano and Vaccaro propose t-unidirectional
`error detecting codes with high rates, for both systematic and nonsystematic cases, together
`with linear time encoding and decoding algorithms.
`
`Two papers are devoted to graphs and finite fields. Montpetit presents some results in graphs
`which extend combinatorial results in coding theory. Astle-Vidal and Dugat propose a
`construction of homogeneous tournaments based on Galois fields.
`
`IPR2018-1556
`HTC EX1018, Page 5
`
`
`
`3 Geometric Codes
`
`VI
`
`In 1989, Pellikaan gave an algorithm which decodes geometric codes up to l(d - l)/2J-errors,
`where d is the designed distance of the code. Le Brigand shows how this algorithm can be
`performed, using some results about the Jacobian of a hyperelliptic curve. Rotillon and
`Thiong Ly describe an effective decoding procedure for some geometric codes on the Klein
`quartic. Gallager proved, in 1963, that almost all binary linear codes meet the Gilbert(cid:173)
`Varshamov bound. In her paper, Voss presents a generalisation of this result. Moreover she
`proves that almost all linear codes in the class of subfield subcodes of certain geometric Goppa
`codes meet the Gilbert-Varshamov bound. Perret constructs nonlinear geometric codes for
`which the distance is lowerbounded by use of multiplicative character sums.
`
`4 Protection of Information
`
`The invited paper by Girault is devoted· to a survey of a large variety of recent identification
`schemes. Harari introduces a secret key coding scheme which relies on a subset of a panicular
`set of random codes. Patarin presents some improvements to the work of Luby and Rack off on
`pseudorandom permutations.
`
`The paper by Fell deals with the effects of bit change errors on the linear complexity of finite
`sequences. Chasse considers the situation where the cells of a LFSR over Fq are disturbed by
`sequences of elements of Fq, Creutzburg obtains valuable results for the determination of
`convenient parameters for complex number-theoretic transforms.
`
`Domingo-Ferrer and Huguet-Rotger describe a cryptographic scheme for program protection by
`means of a coding procedure, using a one-way function and a public-key signature.
`
`5 Convolutional codes
`
`The basic principles and limitations of decoding techniques for convolutional codes are
`presented by Haccoun. Visualizing the decoding process as being a search procedure through
`the tree or trellis representation of the code, he gives methods to circumvent the inherent
`shortcomings of Viterbi and sequential decoding. Sfez and Battail describe a weighted-output
`Viterbi algorithm used in a concatenated scheme where the inner code is convolutional, and
`simulate it over Gaussian and Rayleigh channels. Baldini Filho and Farrel present a multilevel
`convolutional coding method over rings, suitable for coded modulation, and show curves of
`performance for 4-PSK and 8-PSK.
`
`6 Information Theory
`
`This section starts with an invited paper by Sgarro offering a Shannon-theoretic coding theorem
`for authentication codes. Next paper, by the same author together with Fioretto, continues work
`on fractional entropy, a kind of measure of uncertainty for list coding. The section ends with
`two papers on source coding: Battail and Guazzo compare the respective merits of three
`algorithms (Huffman-Gallager, Lempel-Ziv and Guazzo) ; Capocelli and De Santis derive a
`tight upper bound on the redundancy of Huffman codes, in terms of the minimum codeword
`length, and use it to improve a bound due to Gallager.
`
`IPR2018-1556
`HTC EX1018, Page 6
`
`
`
`VII
`
`invited paper by Calderbank describes how binary covering codes can be used to design
`'equiprobable signaling schemes for use in high-speed modems, gaining in low(cid:173)
`nsional space as would shaping the boundaries of the signal constellation in higher
`sions. The next paper, by Battail, De Oliveira and Weidong, considers a combination of
`S code over a large alphabet and a one-to-one mapping of the alphabet into a symmetric
`tellation, for combined coding and multilevel modulation. Two modulation-coding
`ines are compared by Sfez, Belfiore, Leeuwin and Fihel for low-rate digital land mobile
`communication. Finally, Leeuwin, Belfiore and Kawas Kaleb derive a Chernoff upper
`d for the pairwise error probability over a correlated Rayleigh channel.
`
`on and Sadot propose a hybrid ARQ+FEC system using a convolutional code with large
`itraint length and sequential decoding, combined with a modified Go-Back-N ARQ
`· ol, adapted to a two-way troposcatter (Rayleigh) channel. The last paper, by Politano and
`y, describes a VLSI implementation of a Reed-Solomon coder-decoder.
`
`ugot, G. Battail, F. Bayen, J.C. Belfiore, P. Camion, C. Carlet, G. Castagnoli,
`arpin, G. Chasse, G. Cohen, J. Conan, B. Courteau, M. Darmon, J.L. Dornstetter,
`II, L. Gargano, M. Girault, C. Goutelard, S. Harari, D. Haccoun, S. Lebel,
`Brigand, A. Lobstein, G. Longo, H.F. Mattson, P. Langevin, A. Montpetit, F. Morain,
`rton, J. Patarin, J.J. Quisquater, P. Sadat, N. Sendrier, P. Sole, H. Stichtenoth,
`hiong Ly, U. Vaccaro, J. Wolfmann, G. Zemor.
`
`Gerard Cohen
`Pascale Charpin
`
`IPR2018-1556
`HTC EX1018, Page 7
`
`
`
`Contents
`
`1. Algebraic Codes
`
`Concatenated spherical codes...................................................................... 2
`Th. Ericson, V.A. Zinoviev (Invited paper)
`
`A note on automorphism groups of codes and symbol error probability computation...... 6
`M. Elia, G. Taricco
`
`A direct proof for the automorphism group of Reed-Solomon codes......................... 21
`T. Berger
`
`A family of binary codes with asymptotically good distance distribution..................... 30
`T. Beth, D. E. Lazi(:, V. Senk
`
`A transformation on boolean functions, its consequences on some problems .... ........... 42
`related to Reed-Muller codes
`C. Carlet
`
`Covering radius of RM (1,9) in RM (3,9) ................................................. :...... 51
`P. Langevin
`
`The weights of the duals of binary BCH codes of designed distance 15 = 9.. .. . .. . .. . ... ... . 60
`F. Rodier
`
`The minimum distance of some binary codes via the Newton's identities.................... 65
`D. Augot, P. Charpin, N. Sendrier
`
`2. Combinatorial Codes
`
`Minimum-change binary block-codes which are well balanced................................. 76
`J. Burger, H. Chabanne, M. Girault
`
`Construction of unequal error protection codes................................................... 87
`A. 0. Mabogunje, P. G. Farrell
`
`Unidirectional error-detecting codes ................................................................ 94
`G.D. Cohen, L. Gargano, U. Vaccaro
`
`Coherent partitions and codes....................................................................... 106
`A. Montpetit
`
`(JIA)-regular and (]/}.,)-homogeneous tournamenrs .... ........................................... 114
`A. Astie-Vidal, V. Dugat
`
`IPR2018-1556
`HTC EX1018, Page 8
`
`
`
`X
`
`3. Geometric Codes
`
`Decoding of codes on hypere/lip1ic curves........................................................ 126
`D. Le Brigand
`
`Decoding of codes on lhe Klein Quarlic.. .. . ... .. . .. ... ... . .. . .. . .. . .. . ... .. . . . . .. . .. . .. • .. . .. . . . . . 135
`D. Rotillon, J.A. Thiong Ly
`
`Asymplotically good families of geometric Gappa codes and 1he .. . . . . . . .. . .. . ...... .. . .. . . . .. 150
`Gilbert-Varshamov bound
`C. Voss
`
`Mulliplicalive character sums and non linear geometric codes................................... 158
`M.Perret
`
`4. Protection of Information
`
`A survey of idenlification schemes.... . . . . . . . . . . . . . . . . . . . .. . . . . .. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . 168
`M. Girault (invited paper)
`
`A correlation cryptographic scheme ............................•.................................... 180
`S. Harari
`
`Pseudorandom permutalions based on the DES scheme......................................... 193
`J. Patarin
`
`Linear complexity of transformed sequences...................................................... 205
`H.J. Fell
`
`Some remarks on a LFSR "disturbed" by other sequences ...................................... 215
`G. Chasse
`
`Parameters for complex FFTs infinite residue class rings ........................................ 222
`R. Creutzburg
`
`A cryptographic too/for programs proteclion ......................... ............................ 227
`J. Domingo-Ferrer, L. Huguet - Rotger
`
`5. Convolutional Codes
`
`Decoding techniques for convolutional codes................. .. . . . . . . . . . . .. . . . . . . . .. . . . . . . . . . . . .. 242
`D. Haccoun (invited paper)
`
`A weighted-outpUI variant of the Viterbi algorithm for concatenated ........................... 259
`schemes using a convolutional inner code
`R. Sfez, G. Battail
`
`Coded modulalion with convolutional codes over rings.... . . . . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . 271
`R. Baldini Filho, P.G. Farrell
`
`IPR2018-1556
`HTC EX1018, Page 9
`
`
`
`XI
`
`6. Information Theory
`
`A Shannon-theoretic coding theorem in authentication theory ......................•............ 282
`A. Sgarro (Invited speaker)
`
`Joint fractional entropy ............................................................................... 292
`A. Fioretto, A. S garro
`
`On the adaptive source coding ....................................................................... 298
`G. Battail, M. Guazzo
`
`Minimum codeword length and redundancy of Huffman codes ................................. 309
`R.M. Capocelli, A. De Santis
`
`7. Modulation
`
`Binary covering codes and high speed data transmission........................................ 320
`A.R. Calderbank (Invited speaker)
`
`Coding and modulation for the Gaussian channel, in the absence or........................... 337
`in the presence of fluctuations
`G. Battail, H. Magalhaes De Oliviera, Z. Weidong
`
`Comparison of two modulation-coding schemes for /ow-rate digital.. ......................... 350
`land mobile radio communication
`R. Sfez, J.C. Belfiore, K. Leeuwin, A. Fihel
`
`Chernoff bound of trellis coded modu/mion over correlated Rayleigh channel.. .............. 364
`K. Leeuwin, J.C. Belfiore, G. Kawas Kaleh
`
`8. Applications of Coding
`
`A hybrid FEC-ARQ communication system using sequential decoding ........................ 378
`M.M. Darrnon, P.R. Sadot
`
`A 30 Mbits/s (255,223) Reed-Solomon decoder .................................................. 385
`J.-L. Politano, D. Deprey
`
`IPR2018-1556
`HTC EX1018, Page 10
`
`
`
`CONSTRUCTION
`
`UNEQUALERRORPR!
`πCllONCOP않
`。
`
`。1F
`
`A.O.Mab얘unjeandP. G. I;없πll
`Cαnmu띠catlαis Research Group
`Department of타eclrica!En밍ne<:ring
`U띠versity of Manchester
`lanchester M13 9PL
`‘
`
`~!Udy of unequal error protection(uep) codes bas been prompted by an in~ in the voll,llllC of digital
`g tnmsmitted across communi~tion channels,. where. an increa.sinJ percentage- of this data has
`'ty req~irements th~ vary within a block of data. Classical error control codes. also referred to in this
`· equal error proreqti1m (~) code~. provide the same Ievet of protection for all parts ohn infomlation
`•.... This makes them non-optimal for protecting data with uep .requirements. It is poBSiblc to optimize
`:;'. Ul'ldancy ~ an error control <::ode by giving different parts of an infonnation biock different kvels of
`. tian. This can be done by usiJ)g uep c«Ies. The concept of uep codes was first introdueed by Ma.snick
`olf(l967).
`
`objecti.ve in this paper is to draw attention. to construction methods by wijch array codes can be
`to provide unequal c:cror protection. and to highlight some of the advantages of using uep code$_,
`. ·1.ation results a.re shown .for some array codes with unequal error protecdon.
`
`"'·· inimum distance of a code -relative to any infonnation position is alwayt the same in an cep ~ and
`i ual 10 the true minimum distan~ of the code. The error correction captibUity of such random en:or
`,;· coon codes is based on the true mininrum distance of the code. In a uep code. the situation is different
`\1se the relative .minimum. distance of the code differs from one infonnation position: co another and is
`lilways the same. as the true minimum distance of !he code. In other words, information symbols in
`entpqsitions see the code as having different minimmn distances. The e.n-or,CQrrectiori capability of a
`~ is therefore base<.l on a more complicated distaoce p;munetcr known as the separation vector,
`• 'was introduced by Dunning and Rotibins (1978). Unlike Ute rnminmm distance of a code. which is
`ndent of the generator matrix QSed in encoding, the separation vector is depemlent on the generator
`'_)· It is theref 9re defined with re.spect to a particular. ge~ror matrix, The individual components of the
`ation vector refer to the minimwn distance of' a code relative to a particular position in the information
`· ·being encoded.
`
`’
`
`IPR2018-1556
`HTC EX1018, Page 11
`
`
`
`Preliminary definitions
`
`88
`
`Let the symbols in the infonnation stream to be encoded be taken from GF(q) and let
`I = ( I; : j=O, l, ... ,k-1) be the infonnation stream with k positions per word,
`C = ( C; : j=fJ, I , ... ,n-1) be an n-symbol codeword of a code V,
`(!.i.J) be a codeword fonned from an information stream with symbol 'i' in position Ii'
`
`and
`
`The separation of position Ti in the inforination stream I with respect to a code with generator ma
`and weight function w is the minimum distance of the code relative to position Ii and is defined as
`,1.(G) =min w(c<,.,i_ CV,))
`I
`
`i>'i'
`
`I
`
`The separation vector is defined along the same lines as
`s.(G)= (,1.(G)
`: i =0,1,. •. ,k -1]
`1
`When no ambiguity will result, the separation 'W (G) . will be represented as si and the separation v
`I
`~ (G) as S. For large codes, the above form of the separation vector is cumbersome and it be
`convenient to use the polynomial fonn of the separation vector which is introduced below:
`'
`S = L,axb
`b=O
`where a is the number of infonnation bits that have a separation of band z is the number of protection levels.
`When reference needs to be made to a particular generator matrix and weight function, subscripts m8
`use.d in the usual manner.
`
`The protection level lj of an infonnation positionj with separation si is defined as
`
`'i = L c 'i - 1)/2 J
`where L x j is the integer part of x.
`
`The protection spread of a code is defined as: p = 1 + ('sm= - S111i11 ) where Smaz. and smin ~(cid:173)
`maximum and minimum components of the separation vector. By th!s definition, eep codes have a-,.
`protection spread. Note that this is a slightly different from the protection bandwidth inttoduced by Pi
`et al. (1988).
`
`Construction of unequal error protection codes from array codes.
`
`Two infonnation arrays (square or rectangular, say) are said to be orthogonal in the /1' order if and on_
`no more and no less than j positions are common to any of their rows and columns. There is a
`number of o~ogonal arrays of the jlh order that can be formed on any particular array of informa_
`positions. In this study, orthogonal array codes of the first order are of primary interest because they
`easy to understand and are easily decoded by one step majority logic decoding algorithms. Most of:
`arguments for the first order orthogonal arrays hold for higher order arrays. The three possible first o
`orthogonal 5x5 arrays that can be formed with twCnty-five infonnation positions are shown in figure 1.
`
`IPR2018-1556
`HTC EX1018, Page 12
`
`
`
`89
`
`hold a binary infonnation symbol. Each row and column can be made a codeword of an even
`
`2
`
`7
`
`3
`
`8
`
`4
`
`9
`
`12
`
`13
`
`14
`
`5
`
`10
`
`15
`
`1
`
`7
`
`13
`
`17
`
`18
`
`19
`
`20
`
`19
`
`23
`
`10
`
`14
`
`18
`
`22
`
`11
`
`17
`
`20
`
`24
`
`21
`
`2
`
`5
`
`6
`
`3
`
`9
`
`15
`
`1
`
`9
`
`8
`
`15
`
`17
`
`24
`
`11
`
`18
`
`25
`
`2
`
`12
`
`19
`
`21
`
`20
`
`22
`
`4
`
`3
`
`6
`
`10
`
`13
`
`22
`
`23
`
`24
`
`25
`
`25
`
`4
`
`8
`
`12
`
`16
`
`23
`
`5
`
`7
`
`14
`
`16
`
`Figure 1: Orthogonal arrays possible with 25 positions
`
`y check code by adding a l or a O to make the number of non-zeros in the row an even number. The
`It.is a 6x6 array without the check on checks (figure 2). There are two sets of parity information on
`array. One set corresponds to symbols a-e and the other to symbols f-k in figure 2. Due to the fact that
`Parity information is formed from onhogona1 information arrays, each set of parity is orthogonal to the
`""¥IS and can be used independently to increase the minimum distance of the code by one. All six sets of
`-'.ty information formed on the above arrays can be combined to give a triple error correcting (55,25,7)
`By combining different numbers of parity sets, the following eep (n.k,d) array codes can be
`ed:(30,25,2), (35,25,3), (40,25,4), (45,25,5), (50,25,6) and (55,25,7). The simulated bit error rates
`}he (55,25,7), (45,25,5) and (35,25,3) codes when used for random error correction are shown in figure
`from which it is seen that there is little difference in performance below Ei,/N0 values of 10dB. The
`oding algorithm used in the simulation is a one step majority logic decoding algorithm. It should be
`from table 2 that the asymptotic coding gains of these ~cxies differ.
`
`asymptotic coding gain (dB)
`lOlog(rote x min. dist)
`
`5.027
`
`4.437
`
`3.3099
`
`I
`
`6
`
`11
`
`16
`
`21
`
`f
`
`2
`
`7
`
`12
`
`17
`
`3
`
`8
`
`13
`
`18
`
`4
`
`9
`
`14
`
`19
`
`22
`
`23
`
`24
`
`g
`
`h
`
`j
`
`s
`
`a
`
`b
`
`C
`
`d
`
`e
`
`10
`
`15
`
`20
`
`25
`
`k
`
`Figure 2: 6x6 array without check on checks.
`
`information in a parity set is not used simultaneously, a code with non-unity protection spread will
`For example, if only those parity symbols that check the information .symbol in one particular
`are included in the code, only one parity check is included from each of the parity sets and the
`tion vector of the resulting (31,25) code will be
`S =x1 + 25x1
`
`IPR2018-1556
`HTC EX1018, Page 13
`
`
`
`90
`
`Figure 3: Sit Error Rote curves for (55,25), (45,25) ond (35,25) array codes
`
`10•
`
`(45,25) code
`10_, b------+----=::::4::::;si~~::j=.\::(3'.:_5,~25~)~c~o~de:...j.. _ _ _ _j
`
`10-• '---~--...L..--~-.....L--...L..--L--~--...L..--"-'"-"-
`0
`2
`4
`6
`8
`
`E,/N, (dS)
`
`10•
`
`10-•
`
`10...,
`
`,-;,
`,e;. 10-3
`"' .!!
`
`10-<
`
`10-•
`
`10 ...
`
`0
`
`Figure 4: SER for (39,25,S 1)code
`
`2
`
`4
`
`6
`
`8
`
`E,/N, (dB)
`
`IPR2018-1556
`HTC EX1018, Page 14
`
`
`
`91
`
`Figure 5: BER in positions with s=7 in (39,25,S1) and (55,25,7) codes
`
`i ........................ J ........................ L ............... · ...... J ...................... ..
`1
`1
`: (55,25, 7)
`""'~;-..,~_.:::·~··-i--1 -(;9,25,S
`":·· > .................... j ........................ i ..................... ;.... . . ............. ~ ....................... .
`i
`i
`i
`.
`!
`uncoded
`:
`:
`j
`j
`i
`1
`4
`
`i
`
`r
`
`6
`
`2
`
`10
`
`/
`
`1)
`
`:
`
`!
`
`8
`
`E,/N, (dB)
`
`Figure 6: BER I~ positions with s=5 in (39,25,S,) and (45,25,5) codes
`
`............... .! ·······t45;2fr,5)! ........................ 1 ....................... .
`···················
`'
`-+-.
`.
`[
`(35,2~.s,)
`. . .............. ;-······················· :·
`······· ......... .:. ........................ ' ....................... .
`'
`uncoded
`·
`·
`:
`:
`l
`
`i,
`
`2
`
`4
`
`6
`
`8
`
`10
`
`E,/N, (dB)
`
`IPR2018-1556
`HTC EX1018, Page 15
`
`
`
`92
`
`Figure 7: BER in positions with s=3 in (39,25,S1) and (35,25,3) codes
`10° .--------'-------,---.:....---,--------------'-____c:...:.--".._----'--:::,..:...:.c__ __ _;__
`
`.................
`
`;
`
`tJ9:25S)
`
`~
`
`;
`
`"'
`
`·······················!~~~- 1
`-1--------- -!-~ --l-- - i
`
`•• ! (35,25,3) ········l····················}il
`
`-
`----------------1-
`, ...................... 1 ........................ 1 ....................... l ........................ ~ ...... .
`l
`l
`l
`;
`l
`:
`:
`:
`10-• '--~---'----~--'---~--'--~---'----'--''--~
`4-
`2
`8
`6
`0
`
`Eb/No (dB)
`
`Figure 8: BER of s=5 positions in (39,25,S1) codes ond in (55,25,7) code
`10° .--------:....C-----..,...-~---=----,--------'-C.:..:.::C..:..C!'...,C..:...---------------'-..;..:::c..:....:.._c.:..c..:....c'-'
`
`....•.............
`
`.......... ~ ..... J55,25,7J. .. ~ .................•.... ) ..........•.............
`.
`.
`---;._
`:
`:
`j
`.
`j ~ (39,r5,S1)
`:
`:
`:
`:
`!
`.
`j
`j
`·······················1·····················-··i······················· I······· ··--··········}········-···············
`:
`:
`:
`:
`...... ...
`. ······················.···········
`.. . ..
`!
`!
`:
`l
`l
`l
`i
`.
`l
`!
`·······················r·······················r······················· r······················ -~·-··
`!
`I
`1
`10-• L..-~---'----~--'---~-_j--~--.L..~~"'--...J'J
`4-
`2
`8
`6
`0
`
`E,/N. (dB)
`
`IPR2018-1556
`HTC EX1018, Page 16
`
`
`
`93
`
`y uep array ccxles can be formed in this way. As an example of the uep codes that can be achieved, the
`us here will be mainly on the array codes introduced above, i.e. the (35,25), (45,25) and (55,25) codes
`d the (39,25,S 1) code, where
`S1= 2x 1 + 2x5 + 8x 4 + 13x 3
`e parity symbols in this code are formed as illustrated in table 3, and the BER performance is shown in
`-~gure 4. The first row of table 3 means the parity symbol in position 1 checks the information in positions
`·2, 3, 4 and 5 of the information word Column l tells us that the information in position 1 is checked by
`'ty symbols in parity poSitions 1, 5, 6 and 7.
`
`I
`
`2 3 • 5 6 7
`• •
`•
`
`8 9 JO 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
`
`7
`8
`9
`
`•
`
`•
`•
`
`•
`
`• • • • •
`
`•
`
`•
`
`•
`•
`•
`
`•
`
`•
`
`•
`
`•
`
`•
`
`•
`
`•
`
`•
`
`• • • • • •
`•
`•
`
`•
`
`•
`• •
`
`•
`•
`
`•
`
`•
`
`•
`
`•
`
`•
`•
`
`..
`
`•
`
`_comparison of the error rates in positions with the same separation in the different codes confirms the
`ry that the error rate of a code depends on both its distance structure and its rate. Figure 5, 6 and 7
`ws the BER in those information positions with a separation of 7, 5 and 3 respectively. The advantage
`uep can be seen in figures 5 and 6, which shows that the protection received by the information in the
`:Sand s=7 positions of the (39,25,S 1) code is greater than that received by infonnation with an identical
`eparation in the (45,25,5) and (55,25,7) codes respectively. This improvement in perfonnance is easily
`__ Xptained by the higher rate of the (39,25,S 1) code. A similar explanation can be given for the lower
`tection received by the s=3 positions of the (39,25,S1) code when compared to positions with identical
`para1ions in the (35,25,3) code as shown in figure 7. Finally, a situation where the advantages of a high
`.ie out-weighs that of a slightly increased separation is illustrated in figure 8, where it is shown that below
`j)dB, the BER in the s=7 positions of.the (55,25) code is higher than that in the s=5 positions of the
`
`B. Masnick and J. Wolf, " On Linear Unequal Error Protection Codes," JEEE Trans. Inform. Theory,
`vol. IT-3 no. 4, pp 600- (IJ?, Oct. 1967.
`
`A. Dunning and W. E. Robbins, "Optimal encodings of linear block codes for unequal error
`. protection" Information and control, vol 37, pp 150 - 177, 1978.
`
`iF, Pingzhi, C. Zhi and J. Fan, "One Step Completely Onhogonalisable UEP Codes and Their Soft
`Decision Decoding," Electronic Letters, vol. 24, no. 17, pp 1095 - 1096, 18 Aug. 1988.
`
`IPR2018-1556
`HTC EX1018, Page 17
`
`