Design of error-control coding schemes for three
`problems of noisy information transmission, storage and
`processing
`van Gils, W.J.
`
`DOI:
`10.6100/IR274904
`
`Published: 01/01/1988
`
`Document Version
`Publisher’s PDF, also known as Version of Record (includes final page, issue and volume numbers)
`
`Please check the document version of this publication:
`
`• A submitted manuscript is the author's version of the article upon submission and before peer-review. There can be important differences
`between the submitted version and the official published version of record. People interested in the research are advised to contact the
`author for the final version of the publication, or visit the DOI to the publisher's website.
`• The final author version and the galley proof are versions of the publication after peer review.
`• The final published version features the final layout of the paper including the volume, issue and page numbers.
`Link to publication
`
`General rights
`Copyright and moral rights for the publications made accessible in the public portal are retained by the authors and/or other copyright owners
`and it is a condition of accessing publications that users recognise and abide by the legal requirements associated with these rights.
`
` • Users may download and print one copy of any publication from the public portal for the purpose of private study or research.
` • You may not further distribute the material or use it for any profit-making activity or commercial gain
` • You may freely distribute the URL identifying the publication in the public portal ?
`Take down policy
`If you believe that this document breaches copyright please contact us providing details, and we will remove access to the work immediately
`and investigate your claim.
`
`Download date: 22. Jul. 2018
`
`IPR2018-1556
`HTC EX1010, Page 1
`
`

`

`DESIGN OF ERROR-CONTROL
`CODING SCHEMES FOR THREE
`PROBLEMS OF NOISY
`INFORMATION TRANSMISSION,
`STORAGE AND PROCESSING
`
`Wil J. van Oils
`
`IPR2018-1556
`HTC EX1010, Page 2
`
`

`

`DESIGN OF ERROR-CONTROL
`CODING SCHEMES FOR THREE
`PROBLEMS OF NOISY
`INFORMATION TRANSMISSION,
`STORAGE AND PROCESSING
`
`Wil J. van Gils
`
`IPR2018-1556
`HTC EX1010, Page 3
`
`

`

`Ill
`
`DESIGN OF ERROR-CONTROL
`CODING SCHEMES FOR THREE
`PROBLEMS OF NOISY
`INFORMATION TRANSMISSION,
`STORAGE AND PROCESSING
`
`Proefschrift
`
`ter verkrijging van de graad van doctor aan de
`Technische Universiteit Eindhoven, op gezag van
`de rector magnificus, prof. dr. F .N. Hooge,
`voor een commissie aangewezen door het college
`van dekanen in het openbaar te verdedigen op
`dinsdag 5 januari 1988 te 16.00 uur
`
`door
`
`Willibrordus Johannes van Gils
`
`geboren te Tilburg
`
`IPR2018-1556
`HTC EX1010, Page 4
`
`

`

`iv
`
`This thesis was approved by the promotors
`prof. dr. J.H. van Lint and prof. dr. ir. H.C.A. van Tilborg
`
`IPR2018-1556
`HTC EX1010, Page 5
`
`

`

`SUMMARY
`
`v
`
`This thesis deals with the design of error-control coding schemes
`for three different problems of noisy information transmission,
`storage and processing. These problems have in common that
`they are of interest from a practical, industrial point of view and
`that they cannot be solved elegantly by traditional error-control
`coding schemes.
`Problem one is concerned with the transmission and storage
`of messages in which different parts are of mutually different im(cid:173)
`portance. So it is natural to give parts of mutually different im(cid:173)
`portance different protection against errors. This can be done by
`using different coding schemes for the different parts, but more
`elegantly by using a single so-called Unequal Error Protection
`coding scheme.
`The second coding scheme is designed to be used as an au(cid:173)
`tomatically readable product identification code in an automated
`manufacturing environment. The identification number (and pos(cid:173)
`sibly other useful information) of a product is encoded into a
`square matrix of round dots on a contrasting background. Prob(cid:173)
`lems to be dealt with in practice are the rotations of dot matrices
`and the corruption of dots due to printing imperfections, dust par(cid:173)
`ticles and reading failures. To this end source codes and so-called
`square-cyclic channel codes have been designed.
`The third part of this thesis describes an approach towards
`error-control coding for systems in which digit as well as sym(cid:173)
`bol errors can occur, where a symbol is a position-fixed group
`of .digits. Examples of such systems are computer systems and
`compound channels. We give the detailed design of the codes
`and the decoders for three particular applications. These are a
`generalized Triple Modular Redundant fault-tolerant computer, a
`memory array composed of three 9-bit wide units for storage of
`16-bit words, and a '(4,2) concept' fault-tolerant computer. Fi(cid:173)
`nally some general theory on these so-called combined Symbol and
`Digit Error-Control codes is developed.
`
`IPR2018-1556
`HTC EX1010, Page 6
`
`

`

`vii
`
`PREFACE
`
`As already suggested by the title, this thesis is not monolithi(cid:173)
`cal. Apart from an introduction (Chapter 0), it consists of three
`chapters, each of which is subdivided into one or more sections.
`These sections were written at intervals and either appeared in
`journals, were scheduled to appear or were submitted for publi(cid:173)
`cation. The sections are therefore self-contained and can be read
`independently of one another. Co-author of sections 3.3 and 3.4 is
`J.P. Boly. The research work for these papers was done in strong
`co-operation, but for both papers it holds that the main part of
`the work was done by the first author.
`The author is greatly indebted to the management of the
`Philips Research Laboratories, Eindhoven, The Netherlands, for
`the opportunity to carry out and to publish the work described
`here. Stimulating discussions with Professor J.H. van Lint, Profes(cid:173)
`sor H.C.A. van Tilborg, C.P.M.J. Baggen, G.F.M. Beenker, C.J.L.
`van Driel, L.M.H.E. Driessen, Professor J.-M. Goethals, T. Krol
`and L.M.G.M. Tolhuizen have greatly contributed to the contents
`of this thesis. Special thanks are due to J.-P. Boly for the fine
`co-operation on the subject of combined Symbol and Digit Error(cid:173)
`Control codes.
`
`IPR2018-1556
`HTC EX1010, Page 7
`
`

`

`Vlll viii
`
`|PR2018—1556
`
`HTC EX1010, Page 8
`
`IPR2018-1556
`HTC EX1010, Page 8
`
`

`

`CONTENTS
`
`Summary
`
`Preface
`
`Contents
`
`0. Introductory chapter
`
`1. Linear Unequal Error Protection Codes
`
`1.1 Bounds on their length and cyclic code classes
`
`lX
`
`v
`
`vii
`
`lX
`
`1
`
`13
`
`13
`
`Abstract
`13
`I. Introduction
`14
`II. Definitions and preliminaries
`15
`15
`A. The separation vector
`B. Optimal encoding
`17
`18
`C. The canonical generator matrix
`III. Bounds on the length of L UEP codes
`19
`A. Upper bounds
`19
`B. Lower bounds
`20
`IV. Cyclic UEP codes
`28
`A. The separation vector of a cyclic UEP code 28
`B. A majority decoding method for certain
`binary cyclic UEP code classes
`Acknowledgment
`References
`
`29
`45
`46
`
`1.2 Linear unequal error protection codes
`from shorter codes
`
`Abstract
`I. Introduction
`II. Combining codes to obtain L UEP codes
`of longer length
`
`47
`
`47
`48
`
`49
`
`IPR2018-1556
`HTC EX1010, Page 9
`
`

`

`X
`
`Contents
`
`Acknowledgment
`References
`
`App. Construction of binary LUEP codes of length
`less than or equal to 15
`
`2. Two-dimensional Dot Codes
`for Product Identification
`
`Abstract
`I. Introduction
`II. Definition of square-cyclic codes
`
`III. Source encoding and decoding
`IV. A canonical generator matrix of
`a square-cyclic code
`V. Construction of square-cyclic codes
`
`A. Construction of square-cyclic codes from
`quasi-cyclic codes
`B. Construction of square-cyclic codes from
`shortened cyclic codes
`
`Conclusion
`
`Acknowledgment
`
`References
`
`3. Combined Digit and Symbol Error-Control
`
`3.1 A triple modular redundancy technique providing
`multiple-bit error protection without using
`extra redundancy
`
`Abstract
`I. Introduction
`II. How to generalize TMR
`III. Construction of encoder/ decoder pairs
`IV. Mode register updating
`v. Construction and properties
`of the codes
`
`53
`53
`
`55
`
`65
`
`65
`
`66
`
`69
`
`7 4
`
`84
`87
`
`88
`
`90
`
`94
`
`95
`
`95
`
`97
`
`97
`
`97
`98
`102
`106
`117
`
`118
`
`IPR2018-1556
`HTC EX1010, Page 10
`
`

`

`Contents
`
`Conclusion
`Acknowledgment
`References
`
`3.2 An error-control coding system for storage of
`16-bit words in memory arrays composed of
`three 9-bit wide units
`
`Abstract
`I. Introduction
`II. Construction and properties of the codes
`III. Encoder and decoder implementation
`References
`
`3.3 On combined symbol and bit error-control
`[4, 2] codes over {0, 1}8 to be used
`in the ( 4,2) concept fault-tolerant computer
`
`Abstract
`I. Introduction
`II. Definition and properties of the
`minimum distance profile
`III. Construction and properties of the codes
`IV. Decoder outline
`References
`
`xi
`
`123
`123
`123
`
`125
`
`125
`126
`127
`131
`136
`
`137
`
`137
`138
`
`141
`145
`152
`160
`
`3.4 Codes for combined symbol and digit error-control163
`
`163
`164
`
`Abstract
`I. Introduction
`II. Definition and properties of the
`minimum distance profile
`III. SDEC codes
`A. Equivalence of SDEC codes
`B. Construction of a class of SDEC codes
`c. Self-orthogonal SDEC codes
`D. SDEC codes from codes with
`200
`smaller symbols
`E. SDEC codes from shortened cyclic codes 202
`
`165
`170
`172
`179
`191
`
`IPR2018-1556
`HTC EX1010, Page 11
`
`

`

`xii
`
`Contents
`
`F. Extending SD EC codes
`G. Tables of binary SDEC codes
`References
`
`Samenvatting
`
`Curriculum vitae
`
`211
`213
`225
`
`229
`
`231
`
`IPR2018-1556
`HTC EX1010, Page 12
`
`

`

`0. Introductory chapter
`
`1
`
`This introductory chapter gives the motivation for the research
`work reported in this thesis. It also provides some basic concepts
`of coding theory necessary for understanding the results. For an
`extensive treatment of the theory of error-correcting codes the
`reader is referred to the books of Blahut [1], van Lint [10] and
`Mac Williams and Sloane [ 11].
`
`Coding theory preliminaries
`
`In data transmission, storage and processing systems a desired
`level of error control can be guaranteed by using error-correcting
`codes. A linear [n, k] block code C of length n and dimension
`k (k < n) over the alphabet GF(q), the Galois field contain(cid:173)
`ing q elements, is a k-dimensional subspace of the n-dimensional
`vector space GF(q)n. A (linear) encoding of the message set
`M := GF(q)k is a linear mapping from M onto the code space C;
`a message m = (mb m 2, ... , m~c) E M is mapped onto the code(cid:173)
`word!;,.= mG, where G denotes a k-by-n matrix over GF(q) whose
`rows generate C. The matrix G is called a generator matrix of the
`code C and the fraction R := kjn is called the {information) rate
`of the code. If a generator matrix G contains the k-by-k identity
`matrix I as a submatrix, then G is called systematic. In that
`situation the message is a part of the corresponding codeword.
`If a message m E GF(q)k has to be transmitted (respectively
`stored or processed), then one does not transmit (respectively
`store or process) the message, but the codeword attached to it.
`During transmission (respectively storage or processing) the code(cid:173)
`word can be corrupted. The nature of the corruption depends on
`the specific channel used. In this thesis we will assume that the
`channel is (or is very close to) a q-ary symmetric channel. For a
`q-ary symmetric channel the probability that an arbitrary, trans(cid:173)
`mitted symbol from GF(q) will be received as an arbitrary, differ(cid:173)
`ent symbol from GF(q) is constant, say c:. The corrupted version
`r.. of a codeword !;,. can be seen as the addition of an error pattern
`
`IPR2018-1556
`HTC EX1010, Page 13
`
`

`

`2
`
`Introductory chapter
`
`(additive noise) ~ E GF(q)n to~: r. =~+~~where the probability
`that ~ occurs is independent of the codeword ~ sent.
`It is the task of the decoder, which is at the receiving end of the
`channel, to estimate the original message m as good as possible
`~ + ~ of the codeword ~ = mG.
`from the corrupted version r.
`The decoder's strategy is to choose the most likely codeword f._,
`given that r. was received. Provided the codewords are all equally
`likely, this strategy is optimal in the sense that it minimizes the
`probability of the decoder making a mistake. It is called maximum
`likelihood decoding.
`To describe the maximum likelihood decoder more precisely
`we need the definitions of (Hamming) weight and distance. For a
`vector;!?_ in GF(q)n the (Hamming) weight wt(;!;_) is defined as the
`number of nonzero components in;!;_:
`I { i : Xi f:: 0 , i = 1, ... , n} I·
`
`wt(;!;_)
`
`For two vectors ;!;_and~ in GF(q)n, the (Hamming) distanced(;!;_,¥)
`between {f and 'lL is defined as the number of positions in which {f
`and ~ differ:
`
`d(;!;_,~) := l{i :Xi Yi, i = 1, ... ,n}l.
`
`Hence, for ;f,'lf_ in GF(q)n we have
`
`We assume that the channel error rate cis smaller than 1/ q. Then,
`to minimize the probability of making a miscorrection, the decoder
`decodes a received vector r. as a nearest {in Hamming distance
`sense) codeword f., i.e., it picks an error vector§.. which has smallest
`weight:
`
`d(r.,f..) = minimum{d(r.,~): ~ E C},
`
`or equivalently
`
`wt(~) = minimum{wt(~) : r.- ~ E C}.
`
`This procedure is called (complete) nearest neighbour decoding.
`It is equivalent to maximum likelihood decoding if c < ljq. In
`practice such a complete decoding strategy would be too complex
`
`IPR2018-1556
`HTC EX1010, Page 14
`
`

`

`Coding theory preliminaries
`
`3
`
`for implementation. Therefore an incomplete, so-called bounded
`distance decoder is used, which only corrects the error patterns
`of weight at most some fixed value t. To determine this value t,
`we need the definition of the minimum (Hamming) distance of a
`code. For a linear code C the minimum {Hamming) distance is
`defined as the minimum distance between two different codewords
`of C,
`
`d := minimum{ d(~, ;l!.) : ~' 'M. E C, ~ =/= 'M_}·
`Because Cis linear, the minimum Hamming distance of Cis equal
`to the minimum Hamming weight of C,
`
`d minimum{ wt(~) : ~ E C, ~ =/= Q},
`
`where Q denotes the allzero vector of length n. When the minimum
`(Hamming) distance of a code C equals d, then all error patterns
`of weight at most some fixed value t can be corrected if and only
`if t:::; l(d- 1)/2J, where lxJ denotes the largest integer less than
`or equal to x. The code is called t-error-correcting. All received
`words that are outside the spheres with radius t around codewords
`can be detected to be in error. Because all error patterns of weight
`1 and at most d- (t + 1) can be detected, the code C
`at least t
`is called (d- t -!)-error-detecting. In practice, it is not feasible
`to compare a received word to all codewords to determine which
`is closest. To overcome this problem we introduce a so-called
`syndrome decoder.
`An (n k)-by-n matrix Hover GF(q) is called a parity-check
`matrix of the linear code C if
`
`For a vector~ E GF(q)n,
`
`is called the syndrome of ~· So for all codewords Q in C the
`syndrome equals Q. It is well-known that for all error patterns ~
`of weight at most l (d-1)/2 J the syndromes are mutually different.
`Hence these syndromes can be used in the decoder. Two elements
`in GF(qt are in the same coset of C if and only if they have
`
`IPR2018-1556
`HTC EX1010, Page 15
`
`

`

`4
`
`Introductory chapter
`
`identical syndromes. For all cosets of C we determine a minimum
`weight element contained in it and call it a coset leader of that
`coset. Notethateachofthecosets~+G,wt(*.) S l(d-1)/2J has
`a unique coset leader. The coset leaders are used in the syndrome
`decoder which works as follows:
`
`1. whenever r. is received, the syndrome§.:= r.HT is computed;
`
`2. the coset leader L of the coset with syndrome §.is taken as
`the estimate for the error pattern;
`
`3. the estimate for the codeword is~:= r.- [.
`
`In the incomplete syndrome decoder only the syndromes of cosets
`with a coset leader of weight at most some fixed value t, t S
`1) /2 J, are used for error-correction, the other syndromes
`l ( d
`being used for error-detection. Step 2 of the syndrome decoder
`can be implemented as a list of syndrome, coset leader pairs. If
`this list becomes too long, other implementations of step 2 are
`needed. For example, for codes defined in an algebraic way, e.g.
`BCH and Reed-Solomon codes, this can be implemented by more
`sophisticated (algebraic) algorithms.
`We say that a received word contains an error if it is not a
`codeword and we do neither know the position nor the value of
`the corruption. We say that a received word contains an erasure if
`it is not a codeword and we know the position, but not the value
`of the corruption. Of course, combinations of erasures and errors
`can also occur. A linear [n, k, d] code of length n, dimension k,
`and minimum distance d can correct e erasures and t errors if
`e + 2t S d
`1 [1,Ch.9,Sec.2].
`In coding theory, it is very popular to construct new codes
`from old ones. The most trivial way to do this is by adding to any
`codeword ( c11 ••• , en) one symbol, namely its overall pan'ty-check
`
`Cn+l := - L Ci•
`
`n
`
`i=l
`
`Other minor changes to codes are called extending, puncturing,
`expurgating, augmenting, lengthening and shortening, whose def(cid:173)
`initions can be found in [ll,Ch.1,Sec.9]. More complex ways of
`
`IPR2018-1556
`HTC EX1010, Page 16
`
`

`

`Motivation
`
`5
`
`constructing new codes consist in combining several codes into
`new ones. This is done to construct good codes and for ease of
`decoding. These methods can be found in [ll,Ch.18].
`For ease of encoding and decoding so-called cyclic codes
`[11, Chs.3,4, 7, 8], [10, Ch.6] are often used. A linear code is called
`cyclic if the cyclic shifts of the codewords of the code again yield
`codewords of the code. The most famous classes are the BCH
`codes [ll,Ch.9], [10,Ch.6] and the Reed-Solomon (RS) codes
`[11, Ch.10], [10, Ch.6].
`
`Motivation
`The investigations reported in this thesis were initiated by the
`following considerations. In practical situations, the size q of the
`alphabet is a power of 2: q =2m, m ~ 1. If m > 1, then a symbol
`from GF(2m) is built up from m binary digits (bits). In the past
`four decades a lot of linear coding schemes have been constructed
`with the following three assumptions:
`
`• all q-ary message digits are equally important,
`
`• codewords are only corrupted by additive noise,
`
`• either binary digit error-control or 2m-ary symbol error(cid:173)
`control is required, in other words the channel is supposed
`to be a binary symmetric channel or a 2m-ary symmetric
`channel for some m > 1.
`Chapters 1,2, and 3 deal with three practical situations in which
`in each of them exactly one of the above assumptions is not
`fulfilled. These three situations demand three different coding
`schemes which have the following three respective properties:
`
`• different parts of a message should get different protection
`against errors because they are of mutually different impor(cid:173)
`tance,
`
`• 'rotations' (that are certain permutations of the symbols)
`of codewords during transmission, in addition to corruption
`by additive noise up to a certain level, should not cause
`miscorrections by the decoder,
`
`IPR2018-1556
`HTC EX1010, Page 17
`
`

`

`6
`
`Introductory chapter
`
`• both bit and (m-bit) symbol errors should be coped with
`because the behaviour of the channel is a combination of
`that of a binary symmetric channel and that of a 2m-ary
`symmetric channel.
`
`Those three coding schemes are briefly discussed below.
`
`1. Unequal Error Protection
`
`Most error-correcting codes considered in the literature have the
`property that their correcting capabilities are described in terms
`of the correct reception of the entire message. These codes can
`successfully be applied in those cases where all positions in ames(cid:173)
`sage word require equal protection against errors.
`However, many applications exist in which some message po(cid:173)
`sitions are more important than others. For example in trans(cid:173)
`mitting numerical data, errors in the sign or high-order digits are
`more serious than are errors in the low-order digits. As another
`example consider the transmission of message words from different
`sources simultaneously in only one codeword, where the different
`sources have mutually different demands concerning the protec(cid:173)
`tion against errors. Linear codes that protect some positions in a
`message word against a larger number of errors than other ones
`are called Linear Unequal Error Protection {LUEP} codes. Mas(cid:173)
`nick and Wolf [12] introduced the concept of unequal error protec(cid:173)
`tion (UEP). But, in contrast with what one would expect, they
`considered error protection of single positions in codewords. In
`Chapter 1 we consider error protection of single positions in the
`input message words, following the formal definitions of Dunning
`and Robbins [6]. They introduced the so-called .separation vec(cid:173)
`tor to measure the error-correcting capability of an LUEP code.
`Whenever a k-dimensional LUEP code over GF(q) with separa(cid:173)
`tion vector~ (sb s 2 , ••• , sk) is used on a q-ary symmetric chan(cid:173)
`nel, complete nearest neighbour decoding guarantees the correct
`interpretation of the ith message digit if no more than (si- 1)/2
`errors have occurred in the transmitted codeword.
`Chapter 1 deals with L UEP codes. A basic problem is to find
`an LUEP code with a given dimension and separation vector such
`
`IPR2018-1556
`HTC EX1010, Page 18
`
`

`

`Motivation
`
`7
`
`that its length is minimal and hence its information rate is maxi(cid:173)
`mal. In Section 1.1 we derive a number of bounds on the length of
`L UEP codes. For the special case where all message positions are
`equally protected, some of our bounds reduce to the well-known
`Singleton, Plotkin and Griesmer bounds. Section 1.1 provides a
`table containing the parameters of all binary L UEP codes with
`maximal separation vector and length less than or equal to 15.
`The construction of these codes is given in the Appendix of Chap(cid:173)
`ter 1. The second part of Section 1.1 deals with cyclic UEP codes.
`It gives a table of all binary cyclic UEP codes of length at most
`39 and it provides classes of binary cyclic UEP codes that are
`majority logic decodable. Majority logic decoding means that the
`decoder estimates a message bit by taking the majority vote over a
`number of votes generated from the received word. In Section 1.2,
`methods for combining codes, such as the direct sum, direct prod(cid:173)
`uct, and lulu+ vi construction, concatenation, etc., are extended
`to L UEP codes.
`Section 1.1 is a reprint from IEEE Transactions on Informa(cid:173)
`tion Theory, vol. IT-29, no. 6, pp. 866-876, Nov. 1983, except for
`the tables which have been updated. Section 1.2 was published
`in the same journal, vol. IT-30, no. 3, pp. 544-546, May 1984.
`The constructions in the Appendix appeared in Philips Journal
`of Research, vol. 39, no.6, pp. 293-304, 1984. Finally, we like
`to refer to Driessen et al. [4], who describe the application that
`stimulated the research in Unequal Error Protection.
`
`2. Two-dimensional square-cyclic dot codes
`
`The widespread use of bar codes in automated manufacturing
`clearly shows the need for an automatically readable product iden(cid:173)
`tification code. A bar code is built up from a number of parallel
`bars. The relative widths and mutual distances of these bars de(cid:173)
`termine the meaning of the bar code.
`We believe, however, that dot codes provide a better alterna(cid:173)
`tive to bar codes in this area of technology. A dot code consists of
`a square matrix of round dots on a contrasting background. The
`meaning of the dot code is determined by the absence or presence
`
`IPR2018-1556
`HTC EX1010, Page 19
`
`

`

`8
`
`Introductory chapter
`
`of dots. In a dot code the information is recorded in two dimen(cid:173)
`sions, whereas in a bar code only one direction is used to encode
`information. This difference enables the dot code to offer higher
`information density, thereby allowing smaller product identifica(cid:173)
`tion areas. For example, at the flat top of an electric motor shaft
`there is not enough room for a bar code. Furthermore, in auto(cid:173)
`mated manufacturing it is easy to write the dot codes onto the
`mechanical parts by an engraving process. With bar codes this
`would be more complicated. The dot codes can be read by a stan(cid:173)
`dard TV camera and can be recognized by a relatively inexpensive
`picture processing system.
`We shall therefore introduce a method for the transmission
`of numbers from one point to another point by means of square
`matrices of round dots. These square dot matrices can be trans(cid:173)
`lated into square binary matrices by representing the presence of
`a dot by a one (1) and the absence of a dot by a zero (0). In
`a practical situation it was observed that only random dot cor(cid:173)
`ruptions (causing random bit errors) occurred in the dot squares.
`These errors were due to printing imperfections, dust particles,
`and reading failures. Furthermore, because of the possibly ran(cid:173)
`dom rotation of the mechanical parts during the manufacturing
`process, decoding of the dot matrices should be possible irrespec(cid:173)
`tive of the orientation of the matrices. For example, one should
`again think of a square dot matrix on the flat top of a rotated
`shaft of an electric motor, without any synchronization indication
`outside the dot matrix.
`Chapter 2 describes a possible solution to this transmission
`problem, where we have to deal with random corruptions but also
`with 'rotations' of codewords. The solution is split into a source
`coding scheme and a channel coding scheme. In the source cod(cid:173)
`ing scheme product identification numbers are transformed into
`channel message words. The channel coding scheme encodes the
`channel message words into channel codewords, which are trans(cid:173)
`mitted as square dot matrices. The source code depends on the
`channel code and is such that the four rotations of a dot matrix
`are all decoded into the same product identification number. We
`describe two source coding schemes. One is the optimal one, in
`the sense that it uses the minimum number of bits to encode a
`
`IPR2018-1556
`HTC EX1010, Page 20
`
`

`

`Motivation
`
`9
`
`product identification number into a channel message word. The
`other scheme is not optimal, but gives rise to a very simple and
`fast encoding/decoding algorithm. The channel coding scheme
`uses so-called square-cycl£c codes. In a square-cyclic code, the ro(cid:173)
`tation of a codeword (as a dot matrix) again gives a codeword
`of the code. We construct square-cyclic codes from well-known
`quasi-cyclic and (shortened) cyclic codes.
`This research was stimulated by the application of dot codes in
`product identification schemes as described in [2] and [13]. Chap(cid:173)
`ter 2 appeared in the IEEE Transactions on Information Theory,
`vol. IT-33, no. 5, September 1987.
`
`3. Combined symbol and digit error-control
`
`Up to now coding experts have spent a great deal of effort con(cid:173)
`structing binary codes that can correct random bit errors, such as,
`for example, BCH codes. A lot of research into codes over larger
`alphabets, such as the Reed-Solomon (RS) codes, has also been
`done. These RS codes are able to correct symbol errors, a symbol
`being a position-fixed group of (binary) digits. In many applica(cid:173)
`tions, however, one encounters situations where both types of er(cid:173)
`rors, i.e., random bit and random symbol errors, occur. For exam(cid:173)
`ple, this is the case in computers, memory arrays and compound
`channels. Up to now substantial effort has only been put into
`designing codes that can detect single symbol errors, in addition
`to their single-bit error-correcting and double-bit error-detecting
`capabilities [3,5,7,8,14,15]. These codes were designed for mem(cid:173)
`ory systems composed of m-bit wide chips, where m is larger than
`one. In such architectures a chip failure causes a random (m-bit)
`symbol error, which has to be detected. Single bit errors caused
`by the failure of single memory cells are corrected, double bit er(cid:173)
`rors are detected. The need for a wider class of codes that are
`able to detect and correct digit errors and erasures and symbol
`errors and erasures was first recognized by Krol in his design of
`the '(4,2) concept' fault-tolerant computer [9].
`Chapter 3 deals with the design of these so-called combined
`Symbol and Digit Error-Control (SDEC) codes. The first three
`
`IPR2018-1556
`HTC EX1010, Page 21
`
`

`

`10
`
`Introductory chapter
`
`sections give the design of SDEC codes for three particular appli(cid:173)
`cations and describe their implementations.
`Section 3.1 describes a so-called generalized Triple Modular
`Redundant fault-tolerant computer design. In the Triple Modu(cid:173)
`lar Redundancy (TMR) concept, computer hardware is triplicated
`and majority voting is applied to improve the overall system avail(cid:173)
`ability and reliability. Seen from the point of view of coding the(cid:173)
`ory, the TMR technique is a realization of a [3,1] repetition code.
`The question posed by us was how to construct [3,1] codes that
`cannot only correct symbol errors, caused by the failure of one of
`the three identical parts in the system, but also multiple bit errors
`caused by the memories. These codes would save the use of bit(cid:173)
`error-correcting codes for the memories. In Section 3.1, [3,1] codes
`over GF(2m), m = 4,8, 16 are constructed, their error-control ca(cid:173)
`pacities are shown, and their decoder designs are described.
`Section 3.2 describes codes for storing 16-bit words in a mem(cid:173)
`ory array consisting of three 9-bit wide units, a unit being a single
`card or a single chip. These codes are able to correct single bit
`errors, to detect up to four bit errors, and to detect the failure
`of a complete memory unit. The codes have an elegant structure
`which makes fast decoding possible by simple means.
`In Section 3.3 the construction, properties and decoding of
`four nonequivalent [4,2] codes over GF(28
`) are described. These
`codes are able to correct single (8-bit) symbol errors, to correct
`up to three bit errors, and to correct the combination of a symbol
`erasure and at most one bit error. In addition all error patterns
`containing one symbol erasure and two bit errors can be detected.
`These codes can be used in a ( 4,2) concept fault-tolerant computer
`[9] and in memory systems composed of 8-bit wide chips or cards.
`Finally, Section 3.4 gives, after the 'preparing' sections, a more
`theoretical discussion of combined Symbol and Digit Error-Control
`codes. It starts with the definition of the minimum distance pro(cid:173)
`file, a measure for the symbol and digit error-control capacities
`of a code. Equivalence of SDEC codes is discussed and the con(cid:173)
`struction of several classes of SDEC codes is given. Furthermore,
`Section 3.4 contains tables of parameters of SDEC codes over al(cid:173)
`phabets of 2-,3-,4-,6- and 8-bit symbols.
`Section 3.1 appeared in IEEE Transactions on Computers, vol.
`
`IPR2018-1556
`HTC EX1010, Page 22
`
`

`

`References
`
`11
`
`C-35, no.7, pp. 623-631, July 1986. Section 3.2 was published in
`Philips Journal of Research, vol. 41, no. 4, pp. 391-399, 1986.
`Section 3.3 appeared in IEEE Transactions on Information The(cid:173)
`ory, vol. 33, no.6, November 1987. Section 3.4 has been submitted
`to the same journal for publication.
`
`References
`
`[1] R.E. Blahut, Theory and Practice of Error Control Codes,
`Reading,MA: Addison-Wesley 1983.
`
`[2] J.W. Brands, W. Venema, "Product identification with dot
`codes", Philips CAM messages, no. 2, pp. 18-20, Jan. 1984,
`and Philips CAMera, no. 15-IDT -CA-84001, pp. 4-5, Febr.
`1984.
`
`[3] C.L. Chen, "Error-correcting codes with byte error detection
`capability", IEEE Trans. on Computers, vol. C-32, no. 7,
`pp. 615-621, July 1983.
`
`[4] L.M.H.E. Driessen, W.A.L. Heijnemans, E. de Niet, J.H. Pe(cid:173)
`ters, A.M.A. Rijkaert, "An experimental digital video record(cid:173)
`ing system", IEEE Trans. on Consumer Electronics, vol.
`CE-32, no. 3, August 1986.
`
`[5] L.A. Dunning, "SEC-BED-DED codes for error control in
`byte organized memory systems", IEEE Trans. on Comput(cid:173)
`ers, vol. C-34, no. 6, pp. 557-562, June 1985.
`
`[6] L.A. Dunning and W.E. Robbins, "Optimal encodings of
`linear block codes for unequal error protection", Inform.
`Contr., vol. 37, pp. 150-177, 1978.
`
`[7] L.A. Dunning and M.R. Varanasi, "Code constructions for
`error control in byte o