600
`
`IEEE TR4NSACTIONS ON INFORMATION
`
`THEORY,VOL.IT-3,
`
`NO. 4, OCTOBER 1967
`
`On Linear Unequal Error Protection Codes
`
`BURT MASNICK,
`
`MEMBER,
`
`IEEE, AND JACK WOLF, MEMBER,
`
`IEEE
`
`this paper has the
`in
`class of codes discussed
`Abstract-The
`is described
`in
`terms
`property
`that
`its error-correction
`capability
`of correcting errors in specific digits of a code word even though
`other digits in the code may be decoded incorrectly. To each digit
`of the code words is assigned an error protection
`level ft. Then,
`if f errors occur in the reception of a code word, all digits which
`have protection fi greater than or equal to f will be decoded cor-
`rectly even though
`the entire code word may not be decoded
`correctly.
`these codes are described and illus-
`for synthesizing
`Methods
`trated by examples. One method of synthesis
`involves combining
`the parity check matrices of two or more ordinary
`random error-
`correcting codes to form
`the parity check matrix of the new code.
`A decoding algorithm
`based upon
`the decoding algorithms
`of
`the component codes is presented. A second method of code gen-
`eration
`is described which
`follows
`from
`the observation
`that
`for
`a linear code, the columns of the parity check matrix correspond-
`ing to the check positions must span the column space of the matrix.
`Upper and lower bounds are derived
`for the number of check
`digits
`required
`for such codes. The
`lower bound
`is based upon
`counting
`the number of unique syndromes
`required
`for a speci-
`fied error-correction
`capability. The upper bound
`is
`the
`result
`of a constructive procedure for forming
`the parity check matrices
`of these codes. Tables of numerical values for the upper and lower
`bounds are presented.
`
`considered
`all algebraic codes previously
`LMOST
`that
`their
`have
`the property
`literature
`in
`the
`A
`are described in terms
`error-correction
`capabilities
`of correcting errors in code words rather
`than in correcting
`errors
`in individual
`digits of a code word. For example,
`a “t error correcting
`code” will decode
`to
`the correct
`code word
`if
`t or fewer errors occur
`in
`the
`transmitted
`word.
`in which certain
`this paper, codes are investigated
`In
`against a greater
`digits of a code word are protected
`in
`the code word.
`number of errors
`than other digits
`Specifically,
`assigned to each digit of the code words
`is
`an error protection
`level, denoted
`fi. Then
`if
`f errors
`occur
`in
`the
`transmission
`of a code word, all digits
`for
`which
`fi 2
`f will be decoded correctly even though
`the
`entire word may be decoded incorrectly.
`Such codes will
`be called unequal error protection
`codes (UEP codes).
`
`received June 20, 1966; revised February 20, 1967.
`Manuscript
`An abbreviated version of this paper was presented at the Mohawk
`Valley Communications Symposium
`(NATCOM),
`October 11-13,
`1965. The research in this work was supported by United States
`Air Force of Scientific Research Grant AF-AFOSR-499-65
`and
`Contract AF-49-(638) 1600.
`B. Masnick
`is with the Research Department, Grumman Aircraft
`Engineering Corporation, Bethpage, L.
`I., N. Y. 11714. He was
`formerly with
`the Department of Electrical Engineering, New York
`University, Bronx, N. Y.
`J. Wolf
`is with
`the Department
`of Electrical Engineering,
`Polytechnic
`Institute of Brooklyr), Brooklyn, N. Y. He was formerly
`with
`the Department
`of Electrical Engineering, New York Uni-
`.,
`-
`.T TV
`versity, Bronx,
`IV. Y .
`
`is
`find application
`An example where UEP codes may
`in the transmission of binary coded decimal digits. Con-
`sider
`the binary
`coded decimal
`representation
`of an
`integer M whose magnitude may vary between 0 and
`2” - 1.
`
`- - - + m,
`M = ms-,2’-’ + mb-228-2 +
`where mi = 0 or 1. M can be represented by the coeffi-
`cients mi as
`
`- . - m,.
`ms-lm,+2
`If an error changed the coefficient rnBel, the magnitude
`of M would be changed by 2’-‘. On the other hand,
`if
`an error changed the digit m,, the magnitude of M would
`be changed by 1. Thus
`if errors of large magnitude are
`more important
`(costly)
`than errors of small magnitude,
`it may be desirable to seek a coding scheme that provides
`more protection
`for
`the high-order
`digits
`than
`for
`the
`low-order digits.
`to vary
`it may be advisable
`In some circumstances
`the amount, of error protection
`from block of digits
`to
`block of digits. Consider
`the problem of an observer
`transmitting
`the
`results of many simultaneous
`experi-
`ments (as from a satellite). Some of the experiments may
`be more
`important
`than others and
`therefore may be
`deserving of higher-error
`protection. While
`this could
`be accomplished by using a separate code for each ex-
`periment,
`it, would usually be more efficient, and more
`desirable
`to use one code, and thus one encoder and one
`decoder.
`This paper contains an analysis of the problem of linear
`codes[”
`for which
`the protection
`afforded each digit or
`set of digits can be different
`from
`the protection afforded
`some other digit or set, of digits.
`the work
`include
`Previous approaches
`to this problem
`of Gray,’ ‘j’ Bedrosian,14’ Bellman
`and Kalaba,“’
`and
`Buchner. “’ Gray proposed a kind of magnitude
`pro-
`tection
`code with no
`redundancy
`for
`the problem
`of
`analog
`to digital
`conversion of position data. Bedrosian
`and Bellman and Kalaba analyzed weighted PCM systems
`where greater signal amplitude
`and power are allocated
`to
`the higher-order
`binary
`digits. Buchner
`considered
`sending
`information
`with
`some
`information
`digits en-
`coded by a Hamming
`single-error-correcting
`code and
`other
`information
`digits uncoded. He also evolved a
`figure of merit
`for such schemes.
`
`THEORYOF UEP CODES
`of unequal
`conditions
`for
`the generation
`Sufficient
`error protection
`codes, hereafter
`called UEP codes, are
`presented
`in the following
`theorems.
`
`IPR2018-01474
`Apple Inc. EX1012 Page 1
`
`

`

`MASNICK AND WOLF: ERROR PROTECTION CODES
`The discussion is mainly concerned with
`the properties
`of the parity
`check matrix”’
`H of UEP codes. Consider
`those digits corresponding
`to the columns of H which are
`linearly dependent on 2fi or 2fi + 1 (but no fewer) other
`columns of H. Call
`these digits
`fi protected. Denote by
`the lowest protection
`level and by fZ the highest pro-
`fl
`fi is fl +
`tection
`level and adopt
`the convention
`that
`j-
`1.’ Vector quantities will have a bar above as in
`B. The
`ith column of H will be denoted Ei and the syn-
`drome”’
`of a vector B will be denoted X(S). Unless other-
`wise stated,
`the results discussed hold
`for nonbinary
`as
`well as binary codes so that,
`in general, the components of
`all vectors and matrices will be elements
`from a finite
`field containing p elements.
`
`Theorem 1
`in the
`Consider a code V which consists of all vectors
`null space of a parity
`check matrix H. The code V can
`correct any pattern of weight
`fl or less. In addition,
`if
`fi or less occurs, any fi or
`any error pattern of weight
`greater protected digit can be decoded correctly.
`Proof: Since no
`linear dependence
`relation
`involving
`fewer
`than 2fl + 1 columns can exist,
`the code V must
`be able to correct any error of weight
`less than or equal
`to fl.
`the vector E.
`,weight of
`Let w(E) be the Hamming
`it
`is sufficient
`To prove
`the second part of the theorem
`to show that
`the syndrome of any error pattern
`i?,, 0 <
`w(,!?,) 5
`fj, which contains an error in the pth digit which
`is fi protected
`is unique
`from both 1) the syndrome of
`any error pattern &
`0 < w&z) 5
`fl, which does not
`include an error in the pth digit, and 2) the syndrome of
`any error pattern E,, 0 2 w(&)
`5
`fi, which contains
`a different error in the pth digit.2
`Let
`fi be any code word
`in V
`[e 11, e12, e13, -. - , elp Z 0, - * * , elnl
`[e2,, e22, ez3, . --
`, ezn = 0, -- - , e,,]
`
`E& =
`
`B, =
`
`E3 =
`
`e31, e32, e33, -. - , e3= #
`[
`
`fl:---,e3n].
`
`Then
`X@) = 0, X$ + El) = S(El),
`so that
`
`X(@ +
`
`I%‘,> = S(B2))
`
`i?, and an error
`there exists an error pattern
`Assume
`pattern B2 such that
`i3(E,) = &‘(E,). Then
`
`g
`
`(eli
`
`- e2J& = 0.
`
`Since e,, # 0 and ezp = 0, then a set of at most 2fi columns
`1 Note
`that
`for some values of j
`there may be no digits which
`are fj = fl + j - 1 protected.
`2 This condition need not be considered for binary codes since
`only one type of error can then occur in any digit.
`
`601
`the column &, is linearly dependent, con-
`including
`of H
`to hypothesis. Therefore
`the assumption
`that
`the
`trary
`error patterns
`i?, and 8, can be found such that S(i!?,) =
`-
`X(E,)
`is false.
`Assume
`there exists an error pattern 8, and an error
`pattern
`i?, such that X(s,)
`= x(E,). Then
`
`g
`
`(elj - e3$G = 0.
`
`to both 0 and elp, then a set of at
`Since e3= is unequal
`most 2fi
`-
`1 columns of H,
`including
`the column 5
`is
`linearly
`dependent,
`contrary
`to hypothesis.
`Therefore,
`the assumption
`that error patterns
`i?l and
`i?, can be
`found such that &‘(E,) =
`,!3(&)
`is false.
`Thus
`if any error pattern of weight
`less than or equal
`to fi occurs which
`involves
`the pth digit,
`the syndrome
`will specify
`the particular
`error which occurred
`in
`this
`pth digit. Also if an error pattern of weight
`less than or
`equal
`to fi occurs which does not
`involve
`the pth digit,
`the fact
`that
`the pth digit
`is correct can be determined
`from
`the syndrome. Therefore,
`the
`theorem
`is proved.
`The codes described
`in Theorem 1 have the following
`properties.
`If an error pattern of weight no greater
`than
`fj but greater than fl involves
`the pth digit,
`the syndrome
`will
`identify
`the error in the pth digit,
`thereby permitting
`the correction
`of
`this digit. However,
`some
`incorrect
`digits may remain
`incorrect and some correct digits may
`be erroneously “corrected”
`to become
`incorrect
`digits.
`This can occur since the syndrome may be the same as
`the syndrome of some other error pattern of weight
`less
`than or equal
`to fi
`that has the same error
`in
`the pth
`digit. For example let E, and E, be given as
`
`Z = kb,
`
`- . - , elp f 0, - . * , elJ,
`fh,
`fl < w(El> I
`fi7
`
`and
`
`J% = kb, ez2, - -- , ezp = elp, se- , e$,
`fi < 4-&J 5 fi.
`then
`
`= S(E,)
`
`If x(E,)
`
`(C&i - ezi)Ei = 6.
`
`2
`i=1
`
`t be the number of nonzero terms in this summation.
`Let
`Then,
`there
`is a set of t linearly dependent columns of
`H which does not include
`the column &,. Since
`t is at
`- 2 and none of
`most 2fi - 2, so long as 2f, <
`t 5 2fi
`the t columns corresponds to a digit
`that
`is [t/2] or greater
`protected,
`it
`is possible
`for #(El)
`to be
`the same as
`S(&,).
`(The notation
`[x] indicates
`the integer part of z.)
`It can also be true
`that
`if an error pattern of weight
`greater
`than
`fl but no greater
`than
`fi occurs which does
`not
`involve
`the pth digit,
`the resulting
`syndrome may
`erroneously
`indicate an incorrect error pattern but will
`not indicate an error in the pth digit.
`The
`following
`theorem considers conditions
`tire word
`to be decoded correctly.
`
`for an en-
`
`IPR2018-01474
`Apple Inc. EX1012 Page 2
`
`

`

`602
`
`Theorem 2
`fl pro-
`t, digits
`Let
`there be a linear group code with
`t, digits
`f2 protected,
`. . . , t, digits
`fL protected.
`tected,
`In addition
`to the digit protection
`discussed in Theorem
`1, any error pattern can be corrected provided
`that
`there
`the fi or less protected digits,
`are fi or fewer errors
`in
`j = 1, 2, . . . , 2.
`the syndrome
`to show that
`Proof:
`It will be sufficient
`of any error pattern
`i?, which satisfies
`the above con-
`ditions
`is unique
`from: 1) the syndrome of any other
`error pattern Eiz which also satisfies the above conditions,
`and 2) the syndrome of any error pattern, E,, not neces-
`sarily
`satisfying
`the above condition, where w(i%) 5
`w(fi;l,) and E3 is distinct
`from El.
`Assume error patterns
`i?, and
`x(E,)
`= S(R’,). Therefore,
`
`i?, exist such
`
`that
`
`g hi
`
`- ezi)h = 0.
`
`there must be a most highly
`Since El and E, differ,
`they differ. Assume
`that
`the
`protected
`digit
`in which
`most highly protected digit
`in which 8, and i??, differ
`is
`p protected. By hypothesis, 2, and B, may each have no
`more than p errors
`in digits
`that are b or less protected.
`Therefore,
`the relation above describes a set of at most
`2~ columns of H,
`including one that corresponds
`to a p
`protected digit, which
`is linearly dependent, contrary
`to
`hypothesis.
`Therefore,
`no most highly
`protected
`digit
`in which El and
`i?, differ can be found and hence
`if
`S(nl)
`= X(&J,
`then E, =
`i?,.
`Suppose error patterns
`i?, and
`S(El) = X(R3).
`
`i?, exist such
`
`that
`
`Then
`
`g
`
`(elf -
`
`e3i)Ai
`
`=
`
`6.
`
`the most highly
`Let wl = w(J??,), w3 = w(E,). Assume
`protected digit
`in which El and E, disagree is p protected.
`Let E, and E3 agree in $ nonzero digits which are p or
`greater protected. Therefore,
`there are at most wl -
`II,
`nonzero eli that do not sum to zero with corresponding
`esi. There can be at most w8 -
`J/ nonzero e3? that are
`not summed
`to zero by corresponding
`e<i. But wl
`-
`# 5 E”, and since w3 5 w1 we know w3 -
`It, I: p. Thus the
`summation
`above
`indicates
`that
`there exists a set of
`2~ or fewer columns of H, including a column correspond-
`ing
`to a p protected digit which
`is linearly dependent,
`contrary
`to hypothesis. Hence
`there can be no highest
`protected digit
`in which E, and i?, differ and therefore
`no error patterns E, and E3 can be
`found such
`that
`X@J = 8(E3). Therefore,
`the theorem
`is proved.
`
`COSET DECODING
`the decoding of a linear binary group code,
`Consider
`to be used with
`the binary symmetric
`channel, by using
`._.
`the standard
`array”’
`as a decoding
`table. Then
`the
`
`1967
`IEEETRANSACTIONSONINFORMATIONTHEORY,OCTOBER
`probability
`of correct decoding
`is as large as possible
`if each coset leader is chosen to have the minimum weight
`in its coset. These coset leaders are the correctable error
`patterns. The question now arises as to whether
`the use
`of the correctable error patterns of a UEP code as coset
`leaders would
`lead
`to a situation where a coset leader
`would not be the minimum weight vector
`in
`its coset,
`thereby producing
`a smaller probability
`of correct de-
`coding. Two vectors are in the same coset if, and only
`if,
`their syndromes are equal. Theorem 2 guarantees
`that
`no correctable error pattern has the same syndrome as
`any other error pattern
`of
`the same or
`lower weight.
`Therefore, coset decoding of a UEP code where the coset
`leaders are chosen
`t.o be
`the known
`correctable
`error
`patterns will
`lead
`to minimum
`probability
`of error de-
`coding.
`Another question to be considered is the minimum error
`protection
`requirement of the check digits
`in a UEP code.
`This question arises when one contemplates
`the generation
`of codes with highly protected
`information
`digits and
`little
`protected
`check digits. The check columns are
`linearly
`independent
`(as shown in Masnick”‘),
`and
`thus
`each check digit
`is involved
`in some linear dependence
`relation
`involving
`information
`digits. Therefore,
`each
`check digit
`is as protected as the least protected
`informa-
`tion digit with which
`it is involved
`in a linear dependence
`relation.
`
`A SIMPLE UEP CODE AND A GENERALIZATION
`In order to provide extra error protection
`for one digit
`in a group code one must make
`the column of the H
`matrix
`corresponding
`to
`that digit be of “higher
`linear
`independence”
`than
`the other columns of H. One method
`of accomplishing
`this for binary codes is to add a number
`of ones to
`the chosen column and add on a number of
`columns so that every column
`is involved
`in at least one
`linear dependence
`relation.
`The process
`is
`illustrated
`below. We start with
`the H matrix
`for a Hamming binary
`single-error correcting
`(7, 3) group code[”
`
`cl c2 ml c3 in, m3 m4
`
`H=[;t;;
`
`i
`
`;]-
`
`involving
`two errors
`against any
`Protection
`provided by changing H to H’ where:
`
`digit m4
`
`is
`
`cl c2 ml c3 In2 m3 m4 c4 c5
`
`r 000111100
`
`For
`
`the V’ corresponding
`
`to H’,
`
`the digits m4, c4, and.
`
`IPR2018-01474
`Apple Inc. EX1012 Page 3
`
`

`

`MASNICK
`
`AND WOLF: ERROR PROTECTION CODES
`
`603
`
`ti
`
`‘I- “OL --
`L
`Fig. 1. Check matrix with overlapping
`
`“z--j
`snbmatrices.
`
`c5 are protected against 2 errors and the digits cl, c2, ml,
`cB, m,, and m3 are protected against single errors.
`This
`technique can be generalized as follows. Let there
`be
`two check matrices with
`elements
`from GF(Q); HI
`with
`n, columns and
`random error-correcting
`capacity
`el, and Hz with n, columns and random error capacity
`ez, where e, 5 e,. Let H, and H, be joined as submatrices
`of H where H, and H, overlap, as shown
`in Fig. 1. The
`composite matrix H has n, + n,
`-
`noL columns. Let
`<
`noL - e2.
`
`Theorem 3’
`The code V for which H is the check matrix will protect
`the
`first n,
`-
`noL digits against at
`least e, errors,
`the
`last n,
`-
`noL digits against at
`least e, errors and
`the
`noL middle digits against at least e, + e2 -
`[(noL - 1)/2]
`errors.
`in the first n, - noL columns of
`column
`Proof: Every
`is involved
`in no linear dependence relation
`involving
`H
`2e, or fewer columns. Every column
`in the last n, - noL
`columns of H is involved
`in no linear dependence relation
`involving
`2e, or
`fewer
`columns.
`Therefore,
`the
`first
`-
`noL digits are protected against at least e, errors
`nl
`and the last ez - noL digits are protected against at least
`e, errors.
`the noL
`left) of
`the
`(from
`column
`jth
`the
`Consider
`is involved
`in a linear
`columns. This column
`overlapping
`dependence relation
`involving
`at least 2e, other columns
`of H, and at
`least 2e, other columns of H,. Since noL
`is less than or equal
`to e,, the
`jth column must be in-
`volved
`in a linear dependence relation
`involving
`at least
`2e, + 1 -
`j columns
`to its right and at least 2e, - noL +
`j
`columns
`to its left or at least 2e, + 2e, + 1 - n,, other
`columns of H. Since
`the
`jth column was typical
`of the
`noL middle columns,
`the noL middle digits are protected
`against at least e, + e, -
`[(n,,
`-
`1)/2] errors.
`Theorem 3 provides
`the basis for creating codes with
`three different degrees of error protection depending upon
`the two matrices originally
`chosen and on the number of
`overlapping
`columns. For example using this method one
`can always provide protection
`against one more error
`for
`one
`information
`digit
`by adding on
`two extra
`check
`digits.
`In
`this case e, = 1 and nol. = 1. More general
`techniques
`involving
`the overlapping
`of more
`than
`two
`matrices can be developed.
`Provided
`in
`the
`following
`
`is a decoding procedure
`
`for
`
`binary overlap codes which makes use of the individual
`decoding algorithms
`for the component codes with check
`matrices H, and H,.
`(It
`is assumed that efficient decoding
`algorithms
`are available
`for
`the component
`codes as
`would be
`the case for BCH
`codes.) The proof of
`the
`validity
`of
`this procedure
`is given elsewhere.“’
`This
`proof
`is long and is hence omitted
`from
`this paper.
`Consider
`the occurrence of e +
`fi errors in a code word
`from an e error-correcting
`linear group code. This occur-
`rence is referred
`to as overloading
`the H matrix
`for
`the
`code. Using syndrome decoding, one of three circumstances
`may result.
`1) The correct error is indicated.
`2) An incorrect error is indicated.
`3) An unrecognizable syndrome
`is generated, indicating
`an overload of the H matrix.
`check matrices H, and
`In an overlap code the parity
`H, are considered as the encoding and decoding matrices
`for
`the
`first n, and n, digits,
`respectively,
`of each code
`word. They may be used to compute
`the apparent errors
`in the first n, and n, digits.
`If
`these two apparent errors
`agree in the no& middle digits, and the weight requirements
`specified
`in Theorem 3 are met,
`the error has been deter-
`mined.
`that either H, or H,
`exists
`the possibility
`However,
`or both are overloaded.
`In these events, further steps are
`necessary. If either H, or H, is overloaded, and a recogniz-
`able syndrome
`results,
`the apparent errors will
`either
`not satisfy Theorem 3 or they will not agree in the noL
`middle
`digits. On perceiving
`this
`the procedure
`is
`to
`subtract
`from
`the
`received vector
`the apparent
`error
`in the noL middle digits as determined by H,. Recompute
`the syndromes and apparent errors. If the apparent errors
`now satisfy Theorem 3 and
`the apparent error
`in
`the
`noL middle digits
`is 6 according
`to H,,
`the error has been
`determined. The actual error
`in the first nl digits
`is the
`apparent error obtained
`in the first pass by H,. The actual
`noL digits
`is the apparent error
`error
`in
`the
`last n2 -
`obtained
`in the second pass by H,.
`If
`the new apparent
`errors do not satisfy Theorem
`3,
`the procedure
`is
`to
`subtract
`from
`the
`received
`vector
`the apparent
`error
`in the noL middle digits as originally
`determined by H,
`If
`this does not yield an error
`and proceed as above.
`pattern
`that satisfies Theorem 3, both H, and H, are
`overloaded.
`In
`that event, complement
`the middle
`noL
`digits
`in the received vector. Then decoding with H, and
`H, must give the correct errors in the first n, - noL digits
`in
`the middle
`noL digits. The errors
`and the
`last n,
`-
`noL digits are then readily determined.
`
`THE BASIS METHOD
`OF CODE GENERATION[~’
`A procedure
`is shown in the following
`for constructing
`UEP
`codes, based upon
`the observation”’
`that
`the p
`columns
`of
`the parity
`check matrix
`corresponding
`to
`the p check positions must
`form a basis for
`the column
`space. Choose k the number of information
`digits, and
`hi
`the error protection
`for
`the
`ith
`information
`digit,
`
`IPR2018-01474
`Apple Inc. EX1012 Page 4
`
`

`

`604
`
`IEEETRANSACTIONSONINFORMATION
`
`THEORY,OCTOBER 1967
`
`Power of x
`
`Remainder when divided by g(z)
`
`Fig. 2. UEP check matrix constructed by basis method.
`
`p-
`independent
`i = 1 to k. Choose a set of p linearly
`tuples
`to
`form
`the basis
`(check columns of H). Then
`choose a linear combination of 2bi or more basis elements
`for
`the ith
`information
`column of H such that no linear
`combination of t columns thatminvolves the ith information
`column
`is itself a combination of fewer than 2b, + 1 -
`t
`basis vectors
`(check columns). The results of such a pro-
`cedure are illustrated
`in Fig. 2. In Fig. 2 there are lc = 5
`information
`digits.
`Digit m, is protected against up to 1 error
`Digit m, is protected against up to 2 errors
`Digit m3 is protected against up to 3 errors
`Digit m4 is protected against up to 4 errors
`Digit m,
`is protected against up to 5 errors.
`The method of basis elements becomes difficult
`more
`than
`five
`information
`digits when an attempt
`made to use the fewest possible check digits.
`
`for
`is
`
`CODES
`CYCLIC AND PSEUDO-CYCLIC
`for
`instrumented
`Since cyclic codes are very easily
`if a
`it
`is appropriate
`.to ask
`encoding and decoding,“’
`cyclic code can provide unequal protection
`for the various
`digits. The answer, unfortunately,
`is no, as is shown
`in
`the following
`theorem.
`Theorem 4
`from
`A cyclic code cannot provide greater protection
`random errors
`for any particular
`digit
`than
`it does for
`any other digit. The proof
`follows by assuming
`that a
`cyclic code can provide greater protection
`to one digit
`than
`to another digit and proving a contradiction.
`However,
`shortened-cyclic
`codes, which have much
`the ease of
`instrumentation
`of cyclic codes, can be
`of
`UEP
`codes. A hand constructed
`example of a binary
`shortened-cyclic
`code which can correct all single errors
`and all double errors
`that
`involve
`the x5 digit
`is shown
`in the following.
`of g(z) = x6 +
`Let
`the code words be all multiples
`x5 + x4 + 2’ + 1 of degree < 10. This code has five
`information
`digits and six redundant
`digits. Since de-
`coding of cyclic and shortened-cyclic
`codes can be ac-
`complished by dividing
`the altered code word by
`the
`generator polynomial
`and determining
`the error by
`the
`remainder,
`let us establish
`the remainders of the powers
`of x from x0 through x1’.
`
`1
`5
`X2
`;:
`X6
`x5 + x4 + 2% + 1
`x4 + x3 + 2% + x + 1
`x6 + x4 + 23 + x2 + x
`x3 + 1
`x4 + 2
`
`the
`remainder of x5 and
`the
`the sum of
`that
`Note
`remainder of any other single error cannot be duplicated
`by
`the sum of any
`two other
`remainders whereas
`the
`remainder of the error x4 + x can be duplicated by the
`remainder of x1’ and the remainder of the error x3 + x0
`can be duplicated by the remainder of x9.
`
`BOUNDS
`In this section, upper and lower bounds on the required
`redundancy
`for UEP codes are investigated.
`
`Modified Hamming Bound”’
`By counting
`the number of unique syndromes necessary
`to achieve a specified
`level of error protection
`it
`is pos-
`sible to give a lower bound on the number of redundant
`digits. Consider an (n, k) linear code over the field of 4
`unique
`syndromes. Let
`there be
`symbols, having $-”
`tj digits
`j protected,
`j = 1, . . . , s, where
`
`&ti =n.
`
`Let Ai be the number of correctable error patterns of
`weight
`i. Let Ti be the number of code digits
`that are
`i or more protected.
`
`Ti =
`
`f=ti.
`
`the code digits as follows. The z protected digits
`Number
`1 protected digits
`from 1 to T,. The z -
`are numbered
`are numbered
`from T, + 1 to T,-,, etc.
`the Ai. We
`We now give a procedure
`to determine
`as follows.
`construct
`a “graph”
`of every error pattern
`Between x = 1 and x = 1 + 1, we plot on the y axis the
`number of errors
`in
`the digit positions with numbers
`greater
`than 1. For an error of weight
`i the graph must
`have the value y = i between x = 0 and z = 1, and must
`fall to y = 0 at or before x = n. The graph of a correctable
`error pattern must be at or below y =
`j for each set of
`j protected digits, which corresponds
`to x between Tj-,
`and Tis
`
`Example: Consider a code with
`10 digits 1 protected,
`4 digits 2 protected, and
`2 digits 3 protected.
`
`IPR2018-01474
`Apple Inc. EX1012 Page 5
`
`

`

`MASNICK
`
`AND WOLF: ERROR PROTECTION CODES
`
`605
`
`cl
`
`4
`
`5
`
`7
`
`8
`
`I3 14 15 16
`123
`6
`T,
`T,
`T2
`Fig. 3. Typical map of correctible error patterns.
`
`9
`
`10
`
`II
`
`12
`
`x
`
`the boundary
`line represents
`In Fig. 3 the heavy black
`of the graph of a correctable error pattern. The shaded
`line represents
`the map of an error pattern of weight 3
`with errors
`in
`the
`lst, 4th, and 11th positions. Since a
`one to one mapping
`exists between error patterns
`and
`the graphs of an error pattern,
`the problem of counting
`the number
`of correctable
`error patterns
`of weight
`3
`resolves to the problem of counting
`the number of graphs
`that begin at y = 3 and have y = 0 at x = 16 without
`going above
`the boundary
`(the thick black
`line) at any
`point.
`In general, we may establish
`the following
`formulas.
`
`4
`
`=
`
`iT,l(q
`
`- 1)
`
`A2
`
`=
`
`((A,
`
`-
`
`1)
`
`+
`
`(A,
`
`-
`
`- 3)
`
`A, = {[A2 -
`
`II2
`-
`- TJl(q
`(A,
`- 1) -
`(A, - 5%
`- 1) -
`(A,
`- 2)
`
`IL-1
`i-1
`where 0 = ~1 + 1.
`taken
`of n things
`Consider
`the number of combinations
`r at a time, denoted by
`y
`.
`This number can be divided
`0
`into
`those combinations which do include a certain
`item,
`of which
`there are
`and
`those which do not
`include a certain
`item, of which
`there are
`
`Similarly,
`
`so that
`
`n
`0
`
`can be written as
`
`(“1)=(:‘_:)I(‘I:::)
`
`+
`
`*-* +
`
`t
`
`I
`
`:) = $,
`
`(r ”
`
`J
`
`Thus
`
`x
`
`(4
`
`= (T3 3+ “)
`
`--.
`
`+
`
`(A,
`
`-
`
`[A2
`
`from which
`
`it follows
`
`that
`
`.$ $
`
`i = g
`
`(” z “) = x
`
`(3
`
`= (”
`
`4+ “)
`
`(A,
`2) +
`+
`. . . +
`(A, - 01 + [A, -(A,
`+
`--- +
`[A,
`-
`(A,
`- 1)”
`- TJ]}(q
`(A,
`-
`-a-
`-
`A = ((A3 - [A, - (A, - 01) + (A, - [A, - (A, - 111
`-
`[A, -
`(A, - 1) -
`(A, - 211)
`- (A, - Ul)
`+
`-
`[A, - (A, - 1) - (A, - 211
`-
`s-s -
`[A,
`-
`(A,
`- 1) -
`(A,
`
`- 2)
`
`-
`
`-- - -
`
`(A,
`
`- T,)lXq
`
`-
`
`I>“,
`
`etc.
`Combining
`terms we find
`A, = V’J(q - 1)
`A2 = [T2.& - f$ i](q - 1)’
`
`z
`
`and
`
`2
`#=I
`Thus we have
`A, = 1
`
`ki=
`. . . 5
`p=1 i=l
`
`(“+:-l).
`
`A, = T,(p
`
`-
`
`1)
`
`A, =
`
`T,.A,
`
`-
`
`z
`
`iAl +
`
`f$ g
`
`il(q
`
`- 1)”
`
`A2
`
`=
`
`[($I
`
`-
`
`("2'
`
`')](P
`
`-
`
`;I2
`
`A,
`
`=
`
`[($h
`
`-
`
`("2'
`
`')A'+
`
`p;
`
`2)](q
`
`-
`
`II3
`
`A, =
`
`[(:)A3
`
`-
`
`(“2’
`
`‘)A2
`
`etc.
`These equations
`relations.
`
`are simplified
`
`using
`
`the
`
`following
`
`etc.
`
`+
`
`(T4 3+ “)A1
`
`-
`
`(”
`
`4f 3)](q
`
`-
`
`l>“,
`
`IPR2018-01474
`Apple Inc. EX1012 Page 6
`
`

`

`606
`
`for
`i in
`of
`
`These equations reduce to the general form
`Ai = & (‘i +jj - l)A,-,(-l)‘“(n - ui
`where A,, = 1.
`relationship
`a recursive
`Thus we have derived
`the number of correctable error patterns of weight
`terms of
`the number of correctable
`error patterns
`weight
`i - 1, i - 2, . . . , 1.
`concerning
`A word of caution
`should be mentioned
`the use of
`these recursive
`relations.
`.Suppose we have
`T, 1 or more protected digits and T, = T, 2 or more
`protected digits.
`In
`the formulas mentioned
`in the
`fore-
`going T, must be taken
`to be Tz -
`1 since the highest
`numbered position on the second level of the error map
`could not be used. In general, if ti = 0, Ti must be reduced.
`Since each of the correctable error patterns must cor-
`respond to a distinct syndrome and since there are qn-” =
`q’ available syndromes,
`then a lower bound for the number
`of check digits, denoted rL, is given as
`
`1967
`IEEETRANSACTIONSONINFORMATIONTHEORY,OCTOBER
`any 2fl
`-
`1 or fewer previously
`chosen r-tuples. Choose
`t, r-tuples
`such
`that each is not a linear combination
`of any 2fz -
`1 or fewer previously
`chosen r-tuples.
`. . .
`Choose t,
`-
`1 r-tuples
`such
`that each is not a linear
`combination
`of any 2fZ -
`1 or fewer previously
`chosen
`r-tuples. We now have n
`-
`1 r-tuples or columns.
`In
`the worst case, all
`the
`linear combinations mentioned
`above may be distinct.
`If q’
`is greater
`than
`the number
`of
`linear
`combinations
`listed above, one more column
`can be added
`to
`the matrix and the code, which
`is the
`null space of this matrix, must have at least the desired
`properties. Let
`rU be the smallest value of T such that
`the q’ is greater than all the linear combinations mentioned
`above. Then another column can be added which will
`correspond
`to the t,th
`fZ protected
`information
`digit and
`a code with
`the desired properties need have no more
`than rU check digits. Let
`
`and y be the number of r-tuples which have been banned.
`Then y can be shown to be given as
`
`t
`
`;
`
`l)(Y
`
`- 1j2 +
`
`. . . +
`
`(;,;‘I)(*
`
`- 1)=-l
`
`y=[l+(yl) 02 - 1) +
`y n g’: ;s ‘) + (:)(n ;2T’; ‘) + . . . + (2f,T” 2)}k - 1)2/~--p
`+ {( >(
`+ {( )( : n ;Y2’:; ‘> + (:>in gT;; ‘) + *. . + (2f,T” l)}(q - l>2’a-1
`
`+ ( { F )( n ,r,‘“; ‘) + (T))(n ;,T”; ‘) + * * * + (2f,T” 2)}(P - 1)21”-2
`+ ( i Ii’3 )( n iaT,;
`
`“> + (T))(n
`
`&‘;;
`
`‘) +
`
`. . . +
`
`(2j,T”
`
`l)}(q
`
`- 1Y-l
`
`+
`
`. . .
`
`Bourn
`VARSIIARMOV"~~-GILBERT""-SACHS'~~'
`MODIFIED
`This bound
`is established by considering a procedure
`which must
`realize a linear code with
`the desired error
`correction
`capacity.
`Let us establish a code
`that has
`1)
`tl information digits
`I1 protected
`2)
`t, information digit’s S2 protected
`
`It
`
`is known
`
`that
`
`Hence
`
`g
`
`(4)(4
`
`1:)
`
`= (9
`
`2ri-1 7;
`=
`(
`i=1
`
`)(
`
`;,yy_T;)
`
`= y-&(n
`
`-&Ti)
`
`f. protected.
`t, information digits
`z)
`Choose r linearly
`independent
`r-t’uples. These will be
`the check columns
`for
`the parity
`check matrix. Choose
`of
`
`tl r-tuples such that each is not a linear combination
`
`and
`
`IPR2018-01474
`Apple Inc. EX1012 Page 7
`
`

`

`MASNICKANDWOLF:
`Therefore,
`y = ‘2’
`i-0
`
`n ; 1
`) (4 - ui
`(
`
`ERRORPROTECTION
`
`CODES
`
`607
`
`TAI
`
`r77
`
`y. The
`Thus rV is the smallest value of r such that q’ >
`number
`rU serves as an upper bound on the redundancy
`required
`to construct a code with given error protection
`specifications.
`
`OF BOUNDS
`EXAMPLES
`NUMERICAL
`results obtained using
`the upper and lower
`Numerical
`bounds are presented
`in Table
`I. The
`first
`two numbers
`in each row are the number of information
`digits which
`are, respectively,
`one error and two error protected. The
`third and fourth numbers
`in each row are, respectively,
`the lower and upper bounds on the number of redundant
`digits needed for such a code. The upper bound
`is realiz-
`able in the sense that
`it
`follows
`from a construction
`pro-
`cedure for such codes.
`
`EVALUATION
`OFPERFORMANCE
`OF CODES
`The codes considered
`in
`this paper were motivated
`by
`the
`fact
`that
`in certain situations
`different weights
`(or “values of
`importance”)
`should be associated with
`different digits of the code wo