Facebook's Exhibit No. 1018
`001
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 001
`
`

`

`~~~
`
`~~ ~~~~
`
`~
`
`!,
`
`~.
`
`ti
`
`►mtrO
`ae
`
`€,~
`
`'~ j
`
`~ ~~.
`
`Facebook's Exhibit No. 1018
`002
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 002
`
`

`

`Facebook's Exhibit No. 1018
`003
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 003
`
`

`

`1 .
`
`~~
`
`Sri
`
`Facebook's Exhibit No. 1018
`004
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 004
`
`

`

`~ ~~
`
`t.
`
`Facebook's Exhibit No. 1018
`005
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 005
`
`

`

`ERROR CODING FOR
`n r-~i~-unn~Tin onn~rc~c•nr~c~
`
`Facebook's Exhibit No. 1018
`006
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 006
`
`

`

`ELECTRICAL SCIENCE
`A Series of Monographs and Texts
`
`Editors: Henry G. Booker and Nicholas DeClaris
`A complete list of titles in this series appears at the end of this volume
`
`CtP 4 Sip ~9?4
`
`Facebook's Exhibit No. 1018
`007
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 007
`
`

`

`ERROR CODING
`FO R
`AR ITH M ETI C
`0 0
`PR CESS RS
`
`~ '
`
`T.~ R. N. Rao
`
`'a 1
`
`Department of Electrical Engineering
`University of Maryland, College Park
`
`New York and London • 1974
`ACADEMIC PRESS
`A Subsidiary of Harcourt Brace Jovanovich, Publishers
`
`Facebook's Exhibit No. 1018
`008
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 008
`
`

`

`A ~~~
`.~ ~ ~
`1~~~-
`
`COPYRIGHT D LI~4, BY ACADEMIC PRESS, INC.
`ALL RIGHTS RESERVED.
`NO PART OF THIS PUBLICATION MAY BE REPRODUCED OR
`TRANS
`I'1TED IN ANY FORM OR BY ANY MEANS, ELECTRONIC
`OR MECHANICAL, INCLUDING PHOTOCOPY, RECORDING, OR ANY
`INFORMATION STORAGE AND RETRIEVAL SYSTEM, WITHOUT
`PERMISSION IN WRITING FROM THE PUBLISHER.
`
`ACADEMIC PRESS, INC.
`111 Fifth Avenue, New York, New York 10003
`
`United Kingdom Edition published by
`ACADEMIC PRESS, INC. (LONDON) LTD.
`24/28 Oval Road, London NWl
`
`Library of Congress Cataloging in Publication Data
`
`Rao, Thammavarapu R
`N
`Date
`Error coding for arithmetic processors.
`
`(Electrical science)
`Includes bibliographical references.
`I. Error-correcting codes (Information theory)
`2. Computer arithmetic and logic units.
`I. Title.
`QA268.R36 1974
`519.4
`73-22381
`ISBN 0-12-580750-3
`
`PRINTED IN THE UNITED STATES OF AMERICA
`
`Facebook's Exhibit No. 1018
`009
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 009
`
`

`

`To
`
`Rajyalaxmi
`Ramakrishna, Chandrika, and Radhika
`
`S'~
`
`t7"
`
`d
`
`~►'-.
`c-
`
`,-,.~
`
`:~
`
`Facebook's Exhibit No. 1018
`010
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 010
`
`

`

`«~~~ ~~ ~~~ ~~ao~ ~~ao~
`
`~~a ZS ~e~~°~
`
`What I have heard or seen
`from many a scholar,
`a pious hope it has been
`to render it crystal clear.
`
`Translated from Bammera Pothanna's "Bhagavatham."
`
`Facebook's Exhibit No. 1018
`011
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 011
`
`

`

`Contents
`
`Foreword
`Preface
`
`Chapter 1 Introduction and Background
`
`1.1 Algebraic Structures
`1.2 Theory of Divisibility and Congruences
`1.3 Registers and Number Representation Systems
`Problems
`References
`
`Chapter 2 Arithmetic Processars and Error
`Control Preliminaries
`
`2.1 Arithmetic Processors and Digital Computers
`2.2 Nature and Origin of Errors in AP's
`2.3 Error Control Techniques
`Problems
`References
`
`vii
`
`X~
`
`xiii
`
`1
`11
`25
`36
`37
`
`39
`44
`55
`62
`62
`
`Facebook's Exhibit No. 1018
`012
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 012
`
`

`

`VIII
`
`CONTENTS
`
`Chapter 3 Arithmetic Codes, Their Classes
`and Fundamentals
`
`3.1 Code Classes
`3.2 AN Codes and Single-Error Detection
`3.3 Checking an Adder by Separate Codes
`3.4 Checking Other Elementary Operations
`3.5 Residue Generators
`Problems
`References
`
`Chapter 4 Single-Error Correction
`
`4.1 AN Codes and Preliminaries
`4.2 Higher Radix AN Codes
`4.3 Cyclic AN Codes
`4.4 More on M(A, 3)
`Problems
`References
`
`Chapter 5 Error Correction Using Separate Codes
`
`5.1 Biresidue Code
`5.2 Error Correction Using Biresidue Codes
`5.3 Construction of Separate Codes from
`Nonseparate Codes
`Problems
`References
`
`Chapter 6 Large-Distance Codes
`
`6.1 Algorithms
`6.2 Barrows-Mandelbaum (BM) Codes
`6.3 Chien-Hong-Preparata (CHP) Codes
`6.4 AN Codes for Composite A = II(2'"' — 1)
`References
`
`65
`68
`71
`78
`81
`85
`86
`
`87
`104
`113
`115
`118
`119
`
`123
`130
`
`136
`143
`144
`
`145
`153
`159
`164
`171
`
`Facebook's Exhibit No. 1018
`013
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 013
`
`

`

`ix
`
`173
`184
`l87
`190
`
`193
`196
`197
`204
`207
`210
`
`2l2
`
`ENTS
`
`CONTENTS
`
`Chapter 7 Other Arithmetic Codes of Interest
`
`7.1 Systematic Nonseparate Codes
`i 7.2 Burst-Error-Correcting Codes
`Iterative Errors
`7.3
`References
`
`I
`
`Chapter 8 Recent Results on Arithmetic Codes
`and Their Applications
`
`j
`
`8.1 Polynomial Cyclic Codes and Cyclic AN Codes
`8.2 BCH Codes and BCH Bound
`8.3 On Bounds for dm,a of Cyclic AN Codes
`8.4 Majority Decodable Arithmetic Codes
`8.5 Self-Checking Processors
`References
`
`Index
`
`65
`(g
`~ ~
`78
`81
`85
`86
`
`87
`104
`113
`115
`118
`119
`
`123
`130
`
`136
`143
`144
`
`145
`153
`159
`164
`171
`
`Facebook's Exhibit No. 1018
`014
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 014
`
`

`

`Foreword
`
`Computation without error remains an illusive goal of considerable
`importance in certain critical applications which require sophisticated
`and extensive computation with a high degree of system reliability.
`Recent advances in solid state technology have provided individual
`devices with exceptional reliability. In some systems, this improvement
`in device reliability has obtained suf~'icient systems reliability. However,
`i in others, the large number of devices required has negated the improve-
`ment in reliability at the systems level. Such problems can be solved by
`the unlikely development of a perfect device which never fails. In the
`absence of such a device, one can expect greater use of the techniques
`f: ', of fault-tolerant computing to obtain improved systems reliability.
`Such improvement is not obtained without cost in performance or
`~~
`equipment, but in some applications, the cost is justifiable.
`'~,
`t The technology of fault-tolerant computing is, at the present time, in
`its infancy and much development is still needed. In particular, more
`~;
`~ research and development directed toward realizable implementations
`is needed. There exists a substantial amount of literature on the subject,
`'~
`but the number of successful applications remains limited. However,
`the need for fault-tolerant computing will probably increase rather than
`decrease in the future.
`Professor Rao, in this book, considers arithmetically invariant
`
`xi
`
`Facebook's Exhibit No. 1018
`015
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 015
`
`

`

`xli
`
`FOREWORD
`
`codes, which is an important technique of fault-tolerant computing. He
`has surveyed the extensive literature on the subject and organized it
`in a form which should be extremely useful to researchers in this area.
`
`HARVEY L. GARNER
`Moore School of Electrical Engineering
`University of Pennsylvania
`Philadelphia, Pennsylvania
`
`Facebook's Exhibit No. 1018
`016
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 016
`
`

`

`Pre ace
`
`JORD
`
`. He
`;d it
`irea.
`
`:NER
`>ring
`ania
`ania
`
`Since the early work of Diamond (1955), there has been continuous
`progress in arithmetic coding theory. This field derives its strength
`and vitality from the classical works of Brown (1960), Peterson (1961),
`Chien (1964-1972), Massey (1964), Garner (1966), and others.
`The purpose of this book is to combine the available knowledge
`on arithmetic codes and bring it under one cover for the benefit of
`students and researchers in this field of specialization. The presentation
`here includes the necessary mathematical background and error control
`preliminaries in order for this book to serve as a viable text in an
`advanced undergraduate or a graduate level course. The preliminary
`drafts of this book have been used for a graduate course in arithmetic
`coding and are presently being used in a new (modified version of the
`above) course entitled "Arithmetic Codes and Fault-Tolerant Com-
`puting " at the University of Maryland.
`The first two chapters provide the student with a minimal mathe-
`matical background in algebra, number theory, and error control
`techniques. Simple mathematical models for registers, arithmetic
`processors, and elementary arithmetic operations are introduced.
`Chapter 3 introduces arithmetic codes, definitions, and code classifi-
`cations. Single-error detection using AN codes and separate codes is
`also presented. Chapters 4 and 5 cover single-error-correcting codes using
`
`xiii
`
`Facebook's Exhibit No. 1018
`017
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 017
`
`

`

`xlv
`
`PREFACE
`
`AN codes and separate codes, respectively. A section on byte-error
`correction using higher radix codes is included in Chapter 4. In Chapter
`6 we introduce code conversion algorithms leading to a presentation
`of the large distance codes, namely, Barrows—Mandelbaum codes and
`Chien—Hong—Preparata codes. Chapter 7 begins with the systematic
`nonseparate category of codes and covers codes for burst errors and
`iterative errors. We conclude the book with a presentation of codes
`and their applications in Chapter 8.
`I truly believe that I was very fortunate in having the opportunity
`to study under Professor Harvey L. Garner at the University of Michigan.
`I have benefited from and been profoundly influenced by his works,
`thoughts, and teachings. Many fundamental definitions and notations
`and much terminology used in this book reflect this background and
`ini~uence.
`This book contains a number of sections which report on the results
`of our research on "Residue Codes and Application to Arithmetic
`Processors " during the years 1967-1972. This research was made
`possible by grants from the National Science Foundation and the
`National Aeronautics and Space Administration. I acknowledge
`very gratefully the initial guidance and valuable suggestions on the
`subject matter of this book given by Professor Robert T. Chien of the
`University of Illinois. The comments and suggestions from Professor
`Oscar N. Garcia of South Florida University and Dr. Se June Hong
`of the IBM Corporation on portions of this book have been most
`helpful.
`Finally I wish to thank my wife, Rajyalaxmi, for her understanding
`nature and constant encouragement without which this book would
`not have been possible.
`
`T. R. N. Rao
`
`Hf
`
`~~;
`
`'
`
`'
`
`Facebook's Exhibit No. 1018
`018
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 018
`
`

`

`2
`
`ARITHMETIC PROCESSORS
`AND ERROR CONTROL
`PRELIMINARIES
`
`DUND
`
`ding,
`
`4.
`mput.
`
`TDR-
`1963.
`ins to
`
`amber
`
`This chapter introduces the subject of arithmetic processors and
`error control techniques. In the first section, we define arithmetic
`processors (AP), arithmetic operations, and a model to describe their
`functional behavior. In the second section, logic faults, which are the
`cause of errors (both numerical and logical), are discussed. The origin
`and nature of logic faults are discussed. Then arithmetic weight of
`errors (or error numbers) is introduced. In Section 2.3, some error
`control techniques, namely, triple modular redundancy (TMR) as well
`as duplication and switching, are introduced.
`
`2.1 ARITHMETIC PROCESSORS AND DIGITAL COMPUTERS
`
`A digital computer is divided, for convenience, into a number of
`functional units (or subsystems), such as arithmetic processor (AP),
`control unit (CU), memory unit (MU), input/output unit (I/O unit),
`program unit (PU), etc. (see Figure 2.1). These divisions are useful
`from the point of view of computer organization and design. The
`various units are connected together appropriately to enable processing
`of the information required of it. Stated briefly, the function of the
`
`39
`
`Facebook's Exhibit No. 1018
`019
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 019
`
`

`

`4O
`
`2 ARITHMETIC PROCESSORS AND ERROR CONTROL PRELIMINARIES
`
`memory units) is to store data, instructions, and intermediary results
`and to enable transfer of these to the arithmetic unit or I/O unit as
`required. The control unit handles the supervisory functions such as
`providing reference signals (or clock pulses) to initiate or terminate
`the various functions of these units. The I/O units provide the ability
`t.o communicate with the outside world. It may consist of tape readers
`or card readers and punch tape or punch card equipment. The arith-
`metic processor receives data (or operands) and operation commands
`(or instructions) from the memory and control units and performs the
`needed processing. The results of these operations are stored in the
`
`Arithmetic I~ Memory ~ I/O
`processor
`unit
`~
`~~
`unit
`
`Control
`unit
`
`Figurc 2.1 An organization of the functional units of a computer.
`
`specified memory locations or retained in tl~e arithmetic registers which
`are included as part of an AP. The nature and complexity of these
`various functional units depend on the class of problems they are to
`solve, and the instruction re~sertoire. Besides, the speed-=cost trade-offs
`play a significant part in the makeup of each functional_ unit. No less
`important are factors such as the tyke of number system used, the
`arithmetic procedures (or algorithms) built in, the maintenance circuits
`(if any provided), and the required "reliability " or "dependability "
`of operation of the entire system. Therefore, any general characteriz~.-
`tion of any unit such as an AP will not be meaningful for any special-
`purpose computer operation but applies only in a rather general way.
`Since our interest here lies in (the error control coding for) arithmetic
`processors, we discuss their organization next.
`
`Facebook's Exhibit No. 1018
`020
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 020
`
`

`

`ARIES
`
`'SUItS
`ilt aS
`:h as
`inate
`bility
`►ders
`~rith-
`ands
`s the
`i the
`
`rhich
`these
`re to
`-OAS
`IeSS
`the
`~cuits
`lity "
`:riza-
`;cial-
`way.
`netic
`
`2.1 ARITHMETIC PROCESSORS AND DIGITAL COMPUTERS
`
`41
`
`~I
`
`Organization of an arithmetic processor
`
`An arithmetic processor is the part of a computer that provides the
`logic circuits required to perform arithmetic operations such as ADD,
`SUBTRACT, MULTIPLY, DIVIDE, SQUARE-ROOT, etc. There are a number of
`other operations such as complement, shift, rotate, and scale which are
`classified at times as arithmetic operations and are performed by
`arithmetic units of large- and medium-sized computers. In order to
`perform these operations, an AP usually consists of a number of registers
`to store operands, intermediate results (partial sums or partial products),
`and logic blocks such as adders, division logic, over$ow detection logic,
`shift—rotate logic, and in addition, several gating and decoding and
`control logic blocks.
`A sample organization of a small arithmetic processor is shown in
`Figure 2.2. This setup shows four arithmetic registers, called accumulator,
`addend, augend (or multiplicand), and multiplier—quotient registers.
`Parallel adder, complement, and shift—rotate logic blocks are shown.
`
`/ ,~~
`~ ~
`~ ~
`Addend
`i
`f
`
`Input ~
`bus
`~
`~
`
`Padded
`
`From control unit
`
`- -
`
`~ ______-
`___
`!~`
`
`Algorithm
`control
`
`Augend
`
`~.
`
`.'~ ~~~ ~
`'~.,
`~ Comp.
`~~'~, ~~ , i%, i
`~Le ~~~,. ~~
`i ~
`i
`~~.
`i~
`i
`i~
`~
`i
`
`put
`Ob~
`
``~
`
`Accumulator
`
`~" ~ ~
`Shift-rotate
`~ ia9~~
`
`''Multi-Quo ~i~ ~
`..
`~ i,.
`'' d
`~~,
`~
`
`,,
`------
`~~
`
`~ ~
`
`Figure 2.2 Sample organization of arithmetic processors.
`
`Facebook's Exhibit No. 1018
`021
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 021
`
`

`

`42
`
`2 ARITHMETIC PROCESSORS AND ERROR CONTROL PRELIMINARIES
`
`Also indicated are an algorithm controller which receives the operation
`command from the control unit, and control signals to the logic blocks.
`These organizations come in a great variety and differ enormously in
`complexity. For the purpose of understanding the operation of an AP,
`we resort in the next section to a simple model which characterizes, in
`a rather general way, its operation from the point of view of error
`control coding logic. In this discussion one has to keep in mind the
`objective of this study, which is error control coding and not the design
`aspects of an AP. We discuss an organization only to enable a good
`understanding of the error control techniques presented later.
`
`A simple model for arithmetic processors
`
`An AP can be described by the inputs (operands and the operation
`command) .and outputs (the sum or product, etc.). We can assume,
`without loss of generality, that one or more of the operands have
`already been supplied to the AP, and are stored in the appropriate
`registers; and the input required in such cases may be simply an opera-
`tion command. "Shift right five times the contents of an accumulator"
`is an example of that type of instruction. For instructions such as ADn,
`generally one operand such as an augend is already available in the
`accumulator (or augend register), and another will be an input to the
`AP. Similarly, the outputs may simply be posted in one or more
`~ registers of the AP and can be retrieved from it on a separate operation
`command. Therefore, a block diagram of the type shown in Figure 2.3
`can serve as a model for an AP.
`Without any loss of generality, the input operand B, the internal
`operand A (available initially in the register A), and the results R
`are each assumed to be of n binary digits (bits). The opcode for ~ may
`be k bits long, where k must be sufficiently large to accommodate all
`the possible operations of an AP. (Note that the number of different
`operation commands must be less than or equal to 2k). Further, we
`could denote the results R by R = ~(A, B). R is the result of the specified
`operation ~ (when the input operand is B and the internal operand is A).
`
`Facebook's Exhibit No. 1018
`022
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 022
`
`

`

`4RIES
`
`2.1 ARITHMETIC PROCESSORS AND DIGITAL COMPUTERS
`
`43
`
`ltlOri
`)GIGS.
`ly in
`APB
`
`;S~ 121
`error
`l the
`:Sign
`;000I
`
`~tion
`ume,
`have
`~riate
`pera-
`.tor "
`ADD,
`1 the
`~ the
`more
`ation
`e 2.3
`
`ernal
`lts R
`~aY
`to all
`Brent
`r, we
`cified
`is A).
`
`-
`
`~;.
``~
`
`~
`
`(
`Operation command: ¢ j~
`~
`
`Operand:8
`
`~
`
`_
`
`Register A
`
`Operand A
`
`R: Results
``~' ('4~ B)
`
`Figure 2.3 A model for an arithmetic processor.
`
`The outputs R are numerical and/or logical results. The interpretation
`of the outputs as to the nature of their values is left to the control
`function. If ~ is the ADv instruction, then R may represent the sum,
`A + B modulo m, denoted as ~ A + B~,,, , where m = 2" for 2's comple-
`ment binary logic, or m = 2" — 1 for 1's complement binary logic.'
`If ~ denotes "cyclic shift left register A by one place," then R may
`represent the contents of register A after the execution of the instruc-
`tion. If the register A represents the integer A (where 0 < A < 2") before
`the cyclic shift, the integer value of A after the shift equals ~ 2A ~ Zn _ 1 ~
`which may also represent the numerical value of R. If ~ represents an
`operation, say "clear and add " (cLAD), then the register A will be
`replaced by the operand B. If ~ represents MULTIPLY, then R may
`represent the n most significant binary digits of the product of A and B.
`The least significant bits may be stored in one of the specified arithmetic
`registers.
`The discussion above is intended as an overall view of the operations
`of the arithmetic units. A sample of operations has been given in Table
`2.1. The seven operations listed first may be termed "elementary," and
`the rest "compound."
`A compound operation can be performed by repeated use of one
`or more of the elementary operations; for example, MULTirLY can be
`realized by repeated nDD, SHIFT operations. Therefore a number of
`medium-sized computers may not have any "built-in " compound
`
`t For formulas which characterize these elementary operations and for examples
`the reader is advised to see Section 1.3 and in particular Table 1.4.
`
`Facebook's Exhibit No. 1018
`023
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 023
`
`

`

`44
`
`2 ARITHMETIC PROCESSORS AND ERROR CONTROL PRELIMINARIES
`
`Table 2.1 Arithmetic operation commands
`
`Elementary operations
`
`ADD
`susTRncT (Complement and Add)
`SHIFT RT°
`SHIFT LT
`CYCLE LT
`CLEAR and ADD
`STORE ACC
`
`~ ann
`~su~
`~SHR
`~SHL
`~CYL
`~cian
`
`~STA
`
`Compound operations
`MULTIPLY
`FLOATING PT. ADD
`DIVIDE
`SCALE
`SQUARE-ROOT
`COMPARE
`
`° We discussed previously in Chapter 1 two
`types of sxiFT xT operations. One is "Logical
`Shift Rt" and the other "Arith Shift Rt."
`
`,~
`~~
`
`operations, but only a good set of elementary operations. Further, an
`elementary operation may be assumed to use a logic block or logic
`circuit just once. There are exceptions to this; for example, in the serial
`ADD operation, a single full adder stage is repeatedly used. This aspect
`of single-use or multiple-use of a logic block is an important concern
`for error control coding and is therefore discussed in detail in Chapter 7
`in the section on iterative errors.
`Further, if an effective error-correcting scheme is available for all
`elementary operations, then one could say that all arithmetic operations
`can be error controlled, Then the elementary operations that are more
`amenable to error control coding become an important part of our
`study.
`
`2.2 NATURE AND ORIGIN OF ERRORS IN AP's
`
`The words errors, logic faults, component failures, malfunctions, and
`troubles have been defined and used previously by different authors.
`Unfortunately there is no uniformity in their definitions. Before we
`
`Facebook's Exhibit No. 1018
`024
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 024
`
`

`

`RTES
`
`2.2 NATURE AND ORIGIN OF ERRORS IN aP•S
`
`45
`
`attempt some definitions of our own here, it may be appropriate to
`make a clear distinction between the words component, logic element,
`logic network, functional unit, etc. (See Figure 2.4.)
`
`/ Digital \
`computer
`Ex: IBM 7090
`
`Functional unit
`Ex: AP, MU, CU, etc.
`
`Logic block (network)
`Ex: adder, shift register, counter, etc.
`
`Logic element
`Ex: NAND, OR, AND, flip-flop, etc.
`Component
`Ex: resistor, transistor, lead terminal, etc.
`
`an
`~gic
`rial
`sect
`ern
`~r 7
`
`all
`ons
`ore
`our
`
`end
`ors.
`we
`
`Figure 2.4 Subdivisions of a digital computer.
`
`A component is the smallest building block of a digital computer, for
`example, a resistor, transistor, diode, or lead terminal. A logic element
`refers to a logic gate such as rrArrn, ox, AND, NOT, or a flip-flop. A logic
`network (or logic block) refers to a combinational network such as an
`adder, a com~lementer, an overflow detector, or a sequential network
`such as a shift register or a binary counter. Logic networks may vary
`in size considerably from one to another. A functional unit consists of
`a number of logic networks interconnected to perform any operation
`from a comprehensive set of operations. Functional units refer to large
`units such as an arithmetic processor, a control unit, or a memory unit.
`
`Logic faults and their classifications
`
`A ~logic fault or simply a fault is a deviation of logic variables from
`their specified values at one or more points of a logic network. Logic
`faults in an AP may be grouped broadly into two categories:
`
`Facebook's Exhibit No. 1018
`025
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 025
`
`

`

`46
`
`2 ARITHMETIC PROCESSORS AND ERROR CONTROL PRELIMINARIES
`
`1. Control logic faults, which are due to failures' or malfunctions
`in the control logic. As an example, a logic fault in the operation
`command decoder lets a wrong algorithm (~' instead of ~) be
`executed.
`2. Arithmetic logic faults, which include logic faults in an adder,
`or division logic block, etc.
`
`_
`
`~~
`j;
`
`Both categories of faults relate to logic faults within the processor. If
`{ wrong inputs have been applied, that would constitute faults outside
`the premise of AP but are logic faults of the control processor or memory
`~'
`'
`unit. Our concern is directed mainly toward obtaining error-free arith-
`metic processing through detection, location, and correction of errors
`originating in an AP. The techniques and codes studied for this purpose
`can also be used for error control of other functional units in an
`appropriate manner.
`A logic fault was defined previously to be a deviation of logic vari-
`ables from their specified values at one or more points of a logic net-
`work. Afault may invert a binary variable from 1 to a 0, from 0 to a 1,
`or force it to assume a constant logic value (such as stuck-at-1 or stuck-
`at-0). These faults are naturally caused by component failures) or
`malfunctions in a logic network. The origins of logic faults are related
`to component failures or malfunctions, electrical noise, overheating,
`etc., while the ef~'ects of logic faults are the errors in the outputs (or
`numerical results) of the AP.
`The faults may be classified as temporary or permanent, single fault
`or multiple fault, single-use or multiple-use. This classification is based
`on the origin, nature, or use of the faulty network. A temporary fault
`is usually caused by a component malfunction or electromagnetic noise
`interference; its ei~'ects (the errors) .cannot be reproduced under the
`program control. A permanent fault is often caused by a component
`,failure, and its effects are reproducible. A single fault refers to one error-
`
`I, '#
`
`i
`
`;,.
`(s
`i; 1
`,;
`
`fi.
`
`j' A component failure is the permanent destruction of a component such as a
`shorted or an open diode, or a grounded lead. A component malfunction is a
`temporary misbehavior due to outside noise interference, or overheating, or a
`marginal component.
`
`Facebook's Exhibit No. 1018
`026
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 026
`
`

`

`RIES
`
`ons
`:ion
`be
`
`der,
`
`~. If
`side
`gory
`ith-
`rors
`>ose
`an
`
`ari-
`net-
`a 1,
`ick-
`~r
`ited
`~ng~
`(or
`
`ault
`used
`ault
`oise
`the
`gent
`ror-
`
`as a
`is a
`or a
`
`~
`
`~
`
`2.2 NATURE AND ORIGIN OF ERRORS IN AP's
`
`47
`
`inducing event, a multiple fault (double or triple, etc.) refers to several
`single faults occurring simultaneously. The effects of a multiple fault
`may be described as the cumulative effect of the individual single faults.
`A fault (either single or multiple) can be classified as simple (local) or
`complex (distributed) depending on its effect on the errors. A simple
`fault causes minimal damage on the outputs, or in other words, may
`produce an error of the type ±2'; a complex fault causes extensive
`damage. Thus, a fault in a logic element, depending on the intricacy
`of the location of that logic element, is either simple or complex. By
`this definition, control faults are often classified as complex. This
`classification is based 'on the damage wrought on the results of an
`elementary operation or by the error value E, and more precisely, by
`its arithmetic weight W(E), to be defined later.
`The types of errors produced by a fault also differ from one opera-
`tion to another. If an operation does not require the use of a faulty
`network, then the fault is virtually inactive for the duration of that
`operation. Another operation may use that faulty network just once,
`and still another operation may require repeated use. of the same faulty
`network. Thus a logic fault will have different levels of damage on the
`output results of elementary operations and complex operations. This
`fact should be borne in mind by the error control coding designer. As
`an example, a simple fault may be dt~e to a component failure in the
`carry generation logic of the ith stage of a parallel adder, so that the
`error generated (in the addition operation) has a value E _ ±2'. (The
`error word may have several successive nonzero positions, but we call
`the error a single error. A later section has precise definitions of arith-
`metic weights and single and double errors.) A complex fault in the
`same stage of an adder could be a cause for both the carry and sum to
`be in error. Tn the latter case, the error value E - ± 2' ± 2'-1 (E here
`may be a single error or double error, depending on its error magnitude
`~ E ~ ). An important aspect to be noted here is that a fault becomes
`simple or complex' depending on the role of the logic element that
`contains the fault or the failed component. Another point of interest
`is the need for preventing complex faults by suitable logic design. This
`objective can often conflict with the natural, time-old objective of the
`
`Facebook's Exhibit No. 1018
`027
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 027
`
`

`

`i'
`
`''
`
`48
`
`2 ARITHMETIC PROCESSORS AND ERROR CONTROL PRELIMINARIES
`
`logic design, which is to realize logic circuits at minimal cost. An error
`control objective is to limit logic faults to simple and single-use cate-
`gories, as far as possible, by design and by use of algorithms. This
`constraint is likely to limit the size of fanout of a logic element and
`increase the cost of hardware of the processor. This price, however,
`may be reasonable in view of the overall costs of alternative approaches
`such as the triple modular redundancy (TMR) or duplication and
`switching methods, which are described in Section 2.3.
`
`Errors and arithmetic weight
`
`Component failures or malfunctions produce logic faults. The logic
`faults generate erroneous results, or errol-s. Errors are thus the deviations
`in the outputs (numerical or logical) of the arithmetic processor. An
`error is said to occur in an operation ~ of AP whenever the actual output
`R' _ (r„ _ 1, r„ _ 2 , ... , ro) differs from the expected value It = (rn-1,
`ri_ 2, ..., ro) specified by the designer. Therefore, the error word E
`(also called damage pattern or error pattern [1]) is
`_ fie„-i~e,~-z, . . .,eo)=R —R
`(2.1)
`where e~ = r~ — r~ for i = 0, 1, 2, ... , n — 1. If we consider only binary
`outputs, r~ and ri can only be 0 or 1, and consequently e; can be 0, 1,
`or —1.
`
`EXAMPLE
`Actual output
`
`specified output
`
`error word
`
`R' _ (110001), R' = bl(~t')
`
`It = (101101),
`
`R = SI(R)
`
`E _ (011100)
`where 1 denotes —1 in the error word.
`
`_
`
``~a
`
`Facebook's Exhibit No. 1018
`028
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 028
`
`

`

`IARIES
`
`error
`cate-
`This
`and
`ever,
`aches
`and
`
`logic
`~tions
`r. An
`utput
`~rn-1~
`>rd E
`
`(2.1)
`Binary
`0, 1,
`
`2.2 NATURE AND ORIGIN OF ERRORS IN AP's
`
`49
`
`For each error word E, we define an error value E (or hereafter
`error) given by
`
`n-1
`
`and
`
`=o
`
`For the example above, the error E = SI(E) = SI(011100) = 16 — 8 —
`4 = 4. This mapping 8j of error words into errors is a conversion of the
`n-tuples into integer. values, and is not cone-to-one correspondence.
`As examples, the error words (01 t 100), (001100), and (000100) all
`correspond to the same error E = 4. The one most significant property
`of an error is its arithmetic weight, which is defined as follows.
`The arithmetic weight fi of an integer N, denoted W(N) (in radix r),
`is defined as the minimum number of terms in an expression of the form
`
`where a~ ~ 0, ~ a; ~ < r (see Peterson [2, Chapter 15j).
`Since binary arithmetic processors and binary codes are of special
`interest, we may restate the definition above for binary systems. The
`binary arithmetic weight of N is the minimum number of terms in an
`expression of the form
`
`where a~ = 1 or —1. For instance, the decimal number 31 has a binary
`representation 11111, but that is certainly not in a minimal form. Its
`minimal form is 100001 (1 denotes —1). Hence W(31) = 2, the number
`of terms in a minimal form. There may be more than one minimal form
`for a number N. For instance, 25 = 01 1001 and 25 = 101001. While the
`binary arithmetic weight of 31 is 2, its ternary arithmetic weight is 3,
`since 31 = 33 + 3 + 1 is a minimal form. Thus the arithmetic weight
`of a number depends very much on the radix notation used. In order
`to simplify our notation, we observe the following. Unless spec~cally
`stated otherwise, we will assume an arithmetic weight to refer to the
`binary arithmetic weight.
`
`'~ The arithmetic weight is also referred to as Peterson weight in some instances.
`
`Facebook's Exhibit No. 1018
`029
`
`MOBILEIRON, INC. - EXHIBIT 1022
`Page 029
`
`

`

`50
`
`2 ARITHMETIC PROCESSORS AND ERROR CONTROL PRELIMINARIES
`
`An important property of the arithmetic weight is that
`(2.6)
`W(N) = W(— N)
`This can be very trivially observed from the expression (2.4) where each
`k k
`a; can be negative or positive. If N = ~ air", then —N = ~ (—a~)r~'
`~=i
`=i
`and both Nand —N have exactly the same number of terms in their
`minimal forms. Another important property of the arithmetic weight
`is the triangular inequality given as
`(2.7)
`W(Nl + N2) < W(Nt) + W(NZ)
`This is clear if we consider addition of the numbers Nl and N2 which
`are initially in their minimal forms. Cancellation of nonzero terms or
`carries may occur, but the number of nonzero terms of the sum cannot
`possibly exceed the sum of the number of nonzero terms of Nl and NZ .
`As said before, the minimal form (or minimal weight form) for N is not
`unique. As another example, a decimal number 19 = 24 + 22 — 1 =
`24 + 2 + 1. Reitwiesner [3] has shown that if an integer is given in
`such a form that the coefficients ai a~+l = 0 for i = 0, 1, ... , n — 2 in
`the expression
`
`aL = 0, 1, or —1
`
`n-1
`N = ~ ai r`,
`=o
`then it is called the nonadjacent form (NAF) and it is also a minimal
`weight form. In Section 6.1 the interested reader can find further dis-
`cussion on NAF and algorithms for conversion to these forms. An
`algorithm to determine by inspection the arithmetic weight of an integer
`expressed in binary form is availa