United States Patent (19)
`Karim
`
`11
`45
`
`4,589,112
`Patent Number:
`Date of Patent: May 13, 1986
`
`54). SYSTEM FOR MULTIPLE ERROR
`DETECTION WITH SENGLE AND DOUBLE
`BET ERROR CORRECTION
`75) Inventor: Faraydon O. Karim, Vestal, N.Y.
`73 Assignee: International Business Machines
`Corporation, Armonk, N.Y.
`21) Appl. No.: 574,221
`22 Filed:
`Jan. 26, 1984
`51) Int. C. .............................................. G06F 11/10
`52 U.S. C. ......................................... 371/37; 371/39
`58) Field of Search .............................. 371/37, 39, 40
`56)
`References Cited
`U.S. PATENT DOCUMENTS
`3,622,982 11/1971 Clark, Jr. et al. ..................... 371/37
`3,685,014 8/1972 Hsiao et al. ........................... 371/37
`3,714,629 1/1973 Hong et al. ....................... 371/37 X
`4,030,067 6/1977 Howell et al. ........................ 371/37
`4,117,458 9/1978 Burghard et al...................... 371/37
`Primary Examiner-Charles E. Atkinson
`
`Attorney, Agent, or Firm-Mark Levy
`57
`ABSTRACT
`A system for detecting multiple errors that may occur
`during transfer of data and for correcting up to two of
`these errors simultaneously. The system has a compo
`nent for calculating a number of check bits associated
`with the data word. Also provided is a component for
`grouping all data bits into base groups and multiple
`groups, the sum of the number of base groups and multi
`ple groups being equal to the number of check bits. Up
`to two weights are assigned for each data bit. The sys
`tem distributes the data bits among the groups accord
`ing to the weights assigned thereto. Also provided is a
`component for generating a check bit for each of the
`groups and for padding the data word with the check
`bits to form an appended data word. A generator cre
`ates a predetermined number of syndrome bits, the num
`ber being the number of check bits. Finally, a decoder is
`provided for decoding the syndrome bits to identify the
`erroneous bits in the data word.
`
`5 Claims, 3 Drawing Figures
`
`N-BET DATA woRD
`
`SE TABLE TO
`m-Loc (N-b+1)
`COLUMNS
`
`EIGHTS Ol
`ASSIS
`TO REANINGBITS
`
`ARRANGE STS IN
`TABLEACCORDING
`TowcHS Qi
`
`ARRANGE STSN
`TABLE 8
`
`38
`
`40
`
`42
`
`CACULATE NO.
`OF SNORDEBITS
`
`44
`
`GENERATE CHECK -4s
`TS
`
`GENERATE
`SRDE BITS
`
`DECODESEROE-50
`BITS ODENTFY
`ERRORS
`
`
`
`CORRECTERRORS
`
`IPR2018-01474
`Apple Inc. EX1009 Page 1
`
`

`

`U.S. Patent May 13, 1986
`
`Sheet 1 of 3
`
`4,589,112
`
`DATA
`
`
`
`
`
`
`
`
`
`
`
`
`
`10
`
`S. B. GEN
`d S.B.
`DECODER
`
`
`
`6
`
`ND CATOR
`--------- -
`NO ERROR
`SINGLE ERROR
`DOUBLE ERROR
`MULTIPLE ERROR
`
`18
`
`
`
`20
`CORRECTION
`DEVICE
`
`CORRECTED
`DATA
`
`FIG. 1
`
`IPR2018-01474
`Apple Inc. EX1009 Page 2
`
`

`

`U.S. Patent May 13,1986
`
`Sheet 2 of3
`
`4,589,112
`
`N- BIT DATA woRDF30
`
`ARRANGE FIRST b|24
`BITS IN TABLE 8
`
`SET TABLE B TO
`b= LOG) N COLUMNS
`
`L-32
`
`SET TABLE M T0
`m*L0G) (N-b+1)
`COLUMNS
`
`ASSIGN WEIGHTS Qi
`TO REMAINING BITS
`
`ARRANGE BITS IN
`TABLE M ACCORDING
`TQ WEIGHTS Qi
`
`Oo
`
`[9
`
`cM ao
`
`> a
`
`
`
`- ARRANGE BITS IN|go:
`TABLE 8
`
`|
`
`.
`
`CALCULATE NO.
`OF SYNDROME BITS
`
`44
`
`GENERATE CHECK
`BITS
`
`GENERATE
`SYNDROME BITS
`
`:
`
`[-4¢
`
`48
`
`DECODE SYNDROME|_5,
`BITS TO IDENTIFY
`ERRORS
`
`CORRECT ERRORS
`
`}-52
`
`FIG. 2
`
`IPR2018-01474 -
`Apple Inc. EX1009 Page 3
`
`IPR2018-01474
`Apple Inc. EX1009 Page 3
`
`

`

`U.S. Patent May 13, 1986
`
`Sheet 3 of 3
`
`4,589,112
`
`-
`
`ARRANGE m BITS WITH
`CORRESPONDING WEIGHTS - 60
`Dm, Dm2, --, Dmm
`
`K= O
`
`62
`
`ASSGN NEW WEIGHTS
`W , W2, ---, Wm.
`
`66
`
`S = K
`
`68
`
`
`
`PLACE THIS PAR IN
`CORRESPONDING ROW WITH
`SAME VALUE
`
`
`
`YES
`
`NO
`
`YES
`END
`
`FIG. 3
`
`IPR2018-01474
`Apple Inc. EX1009 Page 4
`
`

`

`1.
`
`SYSTEM FOR MULTIPLE ERROR DETECTION
`WITH SNGLE AND DOUBLE BETERROR
`CORRECTION
`
`4,589,112
`2
`occurred in a given row and column of the matrix.
`While these geometric codes were an improvement
`over parity check bits perse, they still could not be used
`to detect errors that were even in number and symmet
`rical in two dimensions.
`After parity check codes and geometric codes were
`devised, a code was invented by Hamming, after whom
`it is named. The Hamming code is a system of multiple
`parity checks that encodes data words in a logical man
`ner so that single errors can be not only detected but
`also identified for correction. A transmitted data word
`used in the Hamming code consists of the original data
`word and parity check digits appended thereto. Each of
`the required parity checks is performed upon specific
`bit positions of the transmitted word. The system ena
`bles the isolation of an erroneous digit, whether it is in
`one of the original data word bits or in one of the added
`parity check bits.
`If all the parity check operations are performed suc
`cessfully, the data word is assumed to be error free. If
`one or more of the check operations is unsuccessful,
`however, the single bit in error is uniquely determined
`by decoding so-called syndrome bits, which are derived
`from the parity check bits. It should be noted once again
`that only single bit errors are detected and corrected by
`use of the conventional Hamming code. Double bit
`errors, although detectable by the Hamming code, are
`not correctable.
`The Hamming code is only one of a number of codes,
`generically called error correcting codes (ECC's).
`Codes are usually described in mathematics as closed
`sets of values that comprise all the allowed number
`sequences in the code. In data communications, trans
`mitted numbers are essentially random data patterns
`which are not related to any predetermined code set.
`The sequence of data, then, is forced into compliance
`with the code set by adding to it at the transmitter, as
`hereinabove mentioned. A scheme has heretofore been
`developed to determine what precise extra string to
`append to the original data stream to make the concate
`nation of transmitted data a valid code. There is a con
`sistent way of extracting the original data from the code
`value at the receiver and to deliver the actual data to the
`location where it is ultimately used. For the code
`scheme to be effective, it must contain allowed values
`sufficiently different from one another so that expected
`errors do not alter an allowed value such that it be
`comes a different allowed value of the code.
`A cyclic redundancy code (CRC) consists of strings
`of binary data evenly divisible by a generator polyno
`mial, which is a selected number that results in a code
`set of values different enough from one another to
`achieve a low probability of an undetected error. To
`determine what to append to the string of original data,
`the original string is divided as it is being transmitted.
`When the last data bit is passed, the remainder from the
`division is the required string that is added since the
`string including the remainder is evenly divisible by the
`generator polynomial. Because the generator polyno
`mial is of a known length, the remainder added to the
`original string is also offixed length.
`At the receiver, the incoming string is divided by the
`generator polynomial. If the incoming string does not
`divide evenly, an error is assumed to have occurred. If
`the incoming string is divided by the generator polyno
`mial evenly, the data delivered to the ultimate destina
`
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`The present invention relates to a system for detect
`ing and correcting errors in data transfer and, more
`particularly, to a system for detecting single or multiple
`10
`bit errors and for correcting single or double bit errors.
`2. Description of the Prior Art
`In any digital system where data is transmitted, one
`or more of the data bits in each data word or message
`may be received in error. This has been a problem from
`15
`the time data processing systems were first invented.
`As more sophisticated data processing operations are
`performed, involving more complex equipment, there is
`a greater need for systems to detect and correct multiple
`errors in data transfers. For example, operations such as
`20
`merging of files, sorting of data within files, numerical/-
`statistical analyses, complex data handling procedures
`and word processing operations require increased reli
`ability in data transfer. In the field of telecommunica
`tions and telemetry, error rates tend to increase when
`25
`data is transmitted over analog lines at high baud rates.
`If data errors occur and are undetected, valuable infor
`mation and system operation itself may be affected.
`Thus, error detecting and correcting features are not
`only advantageous, they are required to improve system
`30
`integrity.
`In response to the problem of error generation during
`data transfers, systems have been developed to detect
`such errors. One of the earliest methods for detecting
`errors was the parity check code. A binary code word
`35
`has odd parity if an odd number of its digits are 1's. For
`example, the number 1011 has three 1 digits and there
`fore has odd parity. Similarly, the binary code word
`1100 has an even number of 1 digits and therefore has
`even parity.
`A single parity check code is characterized by an
`additional check bit that is added to each word to gener
`ate either odd or even parity. An error in a single digit
`or bit in a data word would be discernible since the
`parity check bit associated with that data word would
`45
`then be reversed from what is expected. Typically, a
`parity generator adds the parity check bit to each word
`before transmission. This technique is called padding
`the data word. At the receiver, the digits in the word
`are tested and if the parity is incorrect, one of the bits in
`50
`the data word is considered to be in error. When an
`error is detected at a receiver, a request for a repeat
`transmission can be given so that the error can be cor
`rected. It should be noted that only errors in an odd
`number of digits can be detected with a single parity
`55
`check, since an even number of errors results in the
`parity expected for a correct transmission. Moreover, it
`should be noted that the specific bit in error cannot be
`identified by the parity check procedure as hereinabove
`described.
`A more sophisticated error detection system was
`later devised. Data words of a fixed length of bits were
`grouped into blocks of a fixed number of data words
`each. Parity checks were then performed between dif
`ferent data words as well as for each individual data
`65
`word. The block parity code detected many patterns of
`errors and could be used not only for error detection,
`but also for error correction when an isolated error
`
`IPR2018-01474
`Apple Inc. EX1009 Page 5
`
`

`

`4,589,112
`
`3
`tion is the incoming data with the fixed length remain-
`der field removed.
`A longitudinal redundancy code (LRC)is a special
`case of CRC wherethe particular generator polynomial
`chosen results in the same CRC code as would be ob-
`tained by performing an EXCLUSIVE ORoperation
`once for every bit in the data word. If the data stream
`were represented as a succession of multi-bit words, for
`example, the LRC code added to the end of the stream
`would equal the first word EXCLUSIVE ORed with
`the second, EXCLUSIVE ORedwith the third, and so
`on. Whenthe check is madeat the receiver, the result is
`zero if no errors occurred. This is simply because the
`EXCLUSIVEORofany value with itself is zero. A
`multiple memory error correction technique is shown in
`J. Datres, et al, “Multiple Memory Error Correction”,
`IBM Technical Disclosure Bulletin, Vol. 24, No. 6,
`November 1981. This system first detects an error and
`then stores the erroneous double word back in memory
`in its complemented form. The double word is then
`fetched from memory again. The newly fetched double
`word is then complemented and the ECC check syn-
`dromeis examined. Finally, the recomplemented data is
`then stored back into memory.
`U.S. Pat. No. 4,163,147, issued to Scheuneman,et al
`also discloses a double bit error correction system using
`double bit complementing.
`Both of the references hereinabove cited have disad-
`vantages. One disadvantage is that memory time, nor-
`mally slower than CPUtime, is required for these com-
`plementing and storage/restorage operations. Another
`disadvantage for both of the above-mentioned systems
`is that the error correction technique is reliable only
`when twoerrors occur, one being a so-called hard er-
`ror, induced by media defects, mechanical nonlineari-
`ties and the like, and the other being a soft error, in-
`duced by random noise, correlated noise and the like.
`Thatis, these systemsarereliable if, and only if, one of
`the twobits is erroneous due to memory failure. If both
`data bits detected are in error due to hard causesorif
`both errors are due to soft causes, these detection/cor-
`rection systemsfail. Other errors not related to memory
`devices can occur during the transfer of data over elec-
`trical lines. Thus, another disadvantage of the above-
`mentioned references is that during the course oftrans-
`ferring data and the complemented form of the data
`back and forth to memory, more errors may be gener-
`ated.
`U.S. Pat. No. 4,397,022, issued to Weng, et al dis-
`closes a weighted erasure codec for a Golay code. This
`system uses a pair of read only memories (ROM’s)
`which are used to store the most likely 12-bit error
`patterns corresponding to each syndrome. This system
`is inherently expensive due to the very large number of
`patterns that may occur, requiring correspondingly
`great memory capacity for look-up tables.
`U.S. Pat. No. 4,330,860, issued to Wada, et al dis-
`closes an error correction scheme requiring two types
`of check codes, P and Q. These two check codes result
`in the accumulation of a great numberof checkbits that
`must be stored and processed in the course of data oper-
`ations. The large numberoferror correction checkbits,
`requiring relatively large memorysize, forces the sys-
`tem with which it is used to become morecostly as
`larger data words are handled.
`It would be advantageous for a system not only to
`detect single and multiple errors during data transfer,
`but also to correct single and double bit errors.
`
`-— 0
`
`20
`
`25
`
`35
`
`40
`
`45
`
`50
`
`35
`
`60
`
`65
`
`4
`It would also be advantageousfor an error correcting
`system to minimize the amount of time required for
`memory operations.
`It would also be advantageous to detect and correct
`one or two errors in a data message that may have
`occurred due to hardware malfunction alone, extrane-
`ous causes other than hardware malfunction, or a com-
`bination of both hard and soft causes.
`It would also be advantageous to minimize data trans-
`fer operations during error detection and/or correction
`in order to reduce the probability of extraneous data
`errors occurring.
`It would also be advantageous to minimize the num-
`ber and size of error patterns required as look-up tables
`during the course of error detection/correction opera-
`tions, thus reducing memorycapacity required therefor.
`Finally, it would be advantageous to use an error
`correction system requiring a minimum number of
`checkbits in order to reduce memorycapacity, process-
`ing time and probability of further error during data
`manipulation.
`
`SUMMARYOF THE INVENTION
`
`In accordance with the present invention, there is
`provided a system for detecting multiple errors that
`may occur during transfer of data and for correcting up
`to two of these errors simultaneously. The system has a
`componentfor calculating a number of checkbits asso-_
`ciated with the data word. Also provided is a compo-
`nent for grouping all data bits into base groups and
`multiple groups, the sum of the number of base groups
`and multiple groups being equal to the number of check
`bits. Up to two weights are assigned for each data bit.
`The system distributes the data bits among the groups
`according to the weights assigned thereto. Also pro-
`vided isa componentfor generating a checkbit for each
`of the groups and for padding the data word with check
`bits to form an appended data word. A generatorcre-
`ates a predetermined numberof syndromebits, the num-
`ber being the numberof checkbits. Finally, a decoderis
`provided for decoding the syndromebits to identify the
`erroneousbits in the data word.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`A complete understanding of the present invention
`may be obtained by reference to the accompanying
`drawings, when taken in conjunction with the detailed
`description thereof and in which:
`FIG.1 is a schematic diagram of the system in accor-
`dance with the present invention;
`FIG. 2 is a flow chart representing a preferred
`method of detecting and correcting multi-bit errors for
`use in the instant system; and
`FIG.3 is a flow chart representing a method of gen-
`erating a base grouptable.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`
`It should be understood that any readily available
`programmable computer, properly programmed, may
`form the structure on which the present invention can
`operate. The nature of this invention, however, allows
`any one of a plurality of computers produced by any
`one of a number of manufacturers to be used with this
`invention.
`Referring now to FIG. 1, there is shown a system
`memory device 10, which receives and stores a data
`stream consisting of separate data words or messages.
`
`IPR2018-01474
`Apple Inc. EX1009 Page 6
`
`IPR2018-01474
`Apple Inc. EX1009 Page 6
`
`

`

`For a 15-bit data word, for example, the number of
`columns m is:
`
`m= |Log2 (15-4+1) = Log2 12 = 3.584=4
`A check bit is generated from each group of bits.
`Thus, the length of the code (i.e., the total number of
`check bits required for a data word) is the sum of the
`base bits b and the multiple layer bits m. For a 15-bit
`data word, the total number of check bits is therefore:
`b --In
`
`4-4-8
`
`Weights Qi, each consisting of m bits, are assigned to
`the multiple layer bits, block 38. These bits are arranged
`in Table M according to the weights Qi assigned
`thereto, block 40.
`
`4,589,112
`5
`6
`Each data word has a number of individual data bits,
`where D represents a data bit and the subscript indicates
`depending on the data processing system with which
`the ordinal number thereof. Each column of bits is
`the present invention is intended to operate. Each bit is
`called a base group.
`set to a value of 0 or 1. The data stream signal is also fed
`The bits of the data word that remain after the base
`into a check bit generator 12 that generates a number of 5
`bits b are subtracted are called multiple layer bits. These
`check bits which can be predetermined, as hereinbelow
`multiple layer bits are distributed among base groups
`described, depending upon the length of the data words.
`and multiple layer groups as hereinbelow described.
`A multiple layer table, Table M is generated, block
`These check bits are transferred from the check bit
`generator 12 to memory 10.
`36, having a number of columns which is calculated by
`the equation:
`Once the data words and the check bits are stored in
`10
`memory 10, they are accessed and retrieved from mem
`ory 10 by a syndrome bit generator 14. The same data
`stream signal transferred from memory 10 to the syn
`drome bit generator 14 is also applied to a correction
`15
`device hereinafter described.
`Connected to the syndrome bit generator 14 is a de
`coder 16. The decoder 16 receives syndrome bits from
`the syndrome bit generator 14 and decodes this infor
`mation, generating a signal that represents a particular
`20
`type of error. The signal generated by the decoder 16
`indicates which of the bits in the data word are in error.
`The decoder 16 is adapted to provide a signal to identify
`whether an error occurred, whether the error was a
`single bit error, a double bit error or a multiple bit error.
`25
`This signal is applied to a suitable indicator 18, such as
`a display, indicator LED's, a printout device or the like.
`Once the decoder 16 has identified the errors, if any,
`it sends a signal to a correction device 20. The correc
`tion device 20 also accepts data words directly from
`30
`memory 10. Thus, the correction device 20 receives
`both the data word and the syndrome bits which have
`been decoded by the decoder 16. The single bit or dou
`ble bit errors are corrected, as appropriate.
`Referring now also to FIG. 2, there is shown a flow
`35
`chart of the operations that occur during a data transfer
`operation. The first data word consists of N bits, block
`30. The minimum number of check bits required to
`detect and identify any single bit error or double bit
`error in an N-bit data word must be capable of repre
`senting the following number of possibilities:
`
`TABLE M
`data Bits
`Db--1
`Db--2
`Db-i-3
`Db--4
`Db-5
`Db-i-6
`
`Qi
`0001
`0010
`0.011
`0100
`01.01
`010
`
`N
`
`2.
`N + 2 x
`45
`A base table, Table B, is generated, block 32. The
`number of columns in Table B is equal to:
`b= Log2 N
`
`50
`The symbols are used in equations herein to denote a
`quantity raised to the next highest integer.
`For example, for a data word of 15 bits (D15----
`D2 D1), the number of columns in Table B is calculated
`as follows:
`
`55
`
`That is, a 15-bit data word requires four columns in
`Table B.
`The first b bits of the data word are arranged in se
`quence in Table B according to the distribution shown
`below, block 34:
`
`Bb
`Db
`
`TABLE B
`B4
`B3
`D4
`D3
`
`B2
`D2
`
`B1
`D1
`
`65
`
`The weights Qi have sequential binary values from 0
`through (N-b), one weight for each multiple layer bit.
`The distribution of the multiple layer bits on the base
`groups is accomplished by arranging these multiple
`layer bits with their weights Qi according to the follow
`ing distribution, block 40.
`
`(- - - )
`(Db--2Db-i-3) (- - - )
`0---01 F Db-i-1
`0--- 10 = Db--2 (Db+1Db+3) (---) (---)
`0- - - 11 = Pb--3
`(Pb--1Db+2) (---) (- - -)
`
`-------DN ---- (--- (--)
`
`Multiple layer bit distribution Table M shown herein
`above is generated by EXCLUSIVE ORing each bit
`Db with each other bit Db-1, Db-2, ..., DN sequen
`tially starting from the first entry in the table. Each
`EXCLUSIVE ORed pair is then placed in the row
`corresponding to the assigned weight with the same
`value, if it exists.
`For example, bit Db-1, whose binary value is 0 --
`-01, EXCLUSIVE ORed with bit D-2, whose binary
`value is 0 - - - 10, results in:
`
`IPR2018-01474
`Apple Inc. EX1009 Page 7
`
`

`

`7
`
`0---016D0 - - - 10=0--- 11
`
`Note that the value of this EXCLUSIVE OR operation
`is equal to the weight assigned to Db-3. Thus, the pair 5
`Db-1 Dh-2 is placed in the first column of row Dh3.
`This procedure continues until all pairs of bits are
`EXCLUSIVE ORed with one another and the results
`indicate their appropriate placement in Table M.
`This distribution can be further explained in greater 10
`detail with reference to FIG. 3, which is a flow chart of
`the method by which the base group table, Table B, is
`generated.
`As hereinabove described, the multiple layer bits are
`arranged in Table B with their corresponding weights, 15
`block 60. A counter K is initialized to 0, block 62. The
`counter K is then incremented, block 64.
`A new weight Wi is then assigned to each multiple
`layer bit, block 66. Each new weight Wi has b digits.
`The weight Wi may be any binary number from 0 -- 20
`- 00 to 1 - - - 11 and is empirically and iteratively
`derived as herein described. The only restriction on
`new weights Wiis that, for a given Dith row in multiple
`layer bit distribution Table M shown hereinabove (the
`new weight having the form WoW ---W), none of 25
`the pairs of bits placed in the Dith row, when EXCLU
`SIVE ORed with their new weights Wii, can equal each
`other. Similarly, the result of the EXCLUSIVE OR
`operation cannot equal the new weight Wi with any one
`bit inverted. That is, the result of the EXCLUSIVE OR 30
`operation may not equal WoW1. --W, or WoW -
`-- Wh, and so on to WOW --- Wh.
`The above-mentioned new weight generation can
`also be described in flow chart form with reference to
`35
`FIG. 3.
`Another variable S is set equal to the value of K,
`block 68. The variable S is then incremented, block 70.
`The Kth weight is then EXCLUSIVE ORed with the
`Sth weight, block 72. The data bit and newly assigned 40
`weight pair is then placed in the corresponding row
`with the same value in Table B, block 74. The system
`then tests for whether the result of EXCLUSIVE
`ORing the new weight of the pair is equal to the weight
`of variable bik; or whether the result of EXCLUSIVE 45
`ORing any other pair's weight is equal to the weight of
`bK, block 76. If the new pair's EXCLUSIVE ORed
`weight or any other pair's EXCLUSIVE ORed weight
`is equal to the bk weight, yet another set of new weights
`is then assigned and tested empirically, block 66.
`50
`If, however, the new EXCLUSIVE ORed weight or
`any other EXCLUSIVE ORed weight does not equal
`the bk weight, the system then tests whether all data bits
`have been processed on the current row (for the current
`value of K), block 78. If all data bits have not yet been 55
`processed, the variable S is again incremented, block 70,
`and processing continues from that point.
`If, however, all data bits have been processed for the
`current value of K, the system then tests whether all
`data bits have been processed for all values of K (i.e., all 60
`of the rows), block 80. That is, have all data bits in the
`matrix been processed?
`If certain data bits have not yet been processed, the
`system returns to block 64, incrementing the value of
`variable K and continuing processing. If, however, all 65
`data bits have been processed, the system terminates
`processing, block 82, indicating that all of the new
`weights are valid.
`
`4,589, 112
`8
`It should be noted, in the ongoing example of a 15-bit
`data word, that the number of multiple layer bits is
`equal to:
`
`In this example, each of the 11 bits is assigned the
`following bit locations.
`TABLE M
`
`D5=0001
`D6=0.010
`D=0.011
`D8= 0100
`D9s:0101
`D10=0110
`D1 =0111
`D12=1000
`D13 = 100
`D14=1010
`D15=1011
`Weights are assigned to the multiple layer bits to be
`distributed on the multiple layer groups according to
`the following arrangement.
`
`Multiple Layer Groups
`M3
`M2
`M1
`ds
`D6
`D5
`
`M4
`D12
`
`Base Groups
`B3
`B2
`B4
`D4 D3
`D2
`
`B1
`D1
`
`D15
`
`D11
`
`D1
`D14
`D15
`
`D
`D13
`D5
`
`The multiple layer bits are then distributed onto the
`base groups as shown below.
`TABLE 1.
`0001 D5 (D6D) (D8Ds) (DoD) (D12D13) (D4D15)
`0010 D6 (D5D) (Dg)10) (D9D11) (D12D 14) (D3D15)
`001 D7 (D5D6) (Dgd1) (Dgd10) (D12D15) (D13D 14)
`01.00 D8 (D5D9)
`(D6D10) (D7D11)
`01.01 Dg (DSD8)
`(D6D11) (D7D10)
`O110 D10 (D5D11) (D6D8)
`(D7D9)
`011
`D11 (D5D10) (D6Ds) (DD8)
`1000 D12 (DSD13) (D6D4) (DD15)
`1001 D13 (D5D12) (D6D15) (DD4)
`1010 D4 (D5D15) (D6D12) (DD13)
`011 D15 (D5D 14) (D6D3) (DD17)
`
`New weights are assigned to the bits Ds through D15
`as shown below.
`
`Bit
`D5
`D6
`D7
`Dg
`D9
`D10
`D
`D2
`D13
`D4
`D5
`
`New Weight
`0000
`1000
`110
`O011
`1100
`000
`1000
`010
`010
`O001
`010
`
`These new weights are then checked for validity by
`EXCLUSIVE ORing each of the bits with its pair, as
`follows.
`
`IPR2018-01474
`Apple Inc. EX1009 Page 8
`
`

`

`4,589,112
`
`9
`D569Dg=000069001 = 0011
`
`D669D=1000691000=0000
`
`D7GD10=1110690001 =1111
`
`Note that none of the EXCLUSIVE ORed results
`equal one another in the same row. Nor does any EX
`CLUSIVE OR result equal the multilayer bit in the
`10
`same row. None of the pairs for D9 in the Table equals
`the D9 original weight (01.01) or the D9 original weight
`with any one bit inverted (i.e., 0100, 0111,0001 or 1101).
`In the same way, all of the rows in Table 1 can be veri
`fied.
`Referring now again to FIG. 2, once the validity of 15
`the new weights is proven for all bits in all rows, the bits
`are distributed on base groups according to their new
`weights in the same manner as was performed on multi
`ple layer groups, block 42.
`20
`In the ongoing 15-bit data word example, the above
`mentioned distribution appears as follows:
`
`M4 M3
`D12 D8
`
`D4 D10
`D15 D11
`
`M2
`D6
`
`D10
`D11
`D14
`D15
`
`M1
`D5
`
`B4
`D4
`
`D7
`D9
`D9
`D
`D13 D
`D15
`
`B3
`D3
`
`Dg
`D12
`d13
`D15
`
`B2
`D2
`
`B1
`D1
`
`D8 D10
`D12 D13
`D15 D14
`
`25
`
`30
`
`In order to decode the syndrome bits, block 50, an
`error code list must be generated. The preferred
`method of generating such an error code list is again,
`empirically, to exercise arbitrary single code errors and
`record the resultant syndrome codes. Then double bit
`error combinations should be exercised for the same
`purpose.
`In the ongoing 15-bit data word example, a partial
`error code list is shown below.
`
`Type of Error
`No Error
`D
`D1 and D2
`D1 and D3
`D1 and D4
`D1 and D5
`D and D6
`D and D7
`D1 and D8
`D1 and D9
`
`So S. S2 S3 S4 S5 S6 S7
`0 0 0 0 0 0 0 0
`0 0
`0 0 0 0 0
`1
`0 0 0 0 0 0 1
`1
`0 0 O 0 0 1
`0 1
`0 0 0 0
`1
`0 0
`1
`0 0 0 1
`0 0
`0
`1
`0 0
`1
`0
`0
`0 0 1
`0 0
`1
`1
`1
`1
`1
`1
`0 1
`0 0 0
`0
`1
`0
`0 1
`0
`1
`1
`1
`0
`1
`
`The number of syndrome bits can be generated, block
`44, as the result of EXCLUSIVE ORing the check bits
`with the corresponding group of data bits for each data
`word.
`35
`Check bits are generated, block 46, by EXCLUSIVE
`ORing all of the data bits of each group (base group or
`multiple layer group), much as odd parity is normally
`generated, in the manner shown below.
`
`45
`
`50
`
`The check bits shown above are appended to and
`55
`stored with the data word for furture transmission.
`Syndrome bits are then generated, block 48, as here
`inabove mentioned, by EXCLUSIVE ORing the previ
`ously generated check bits with their corresponding
`data bits. For the ongoing 15-bit data word example, the
`syndrome bits are derived as shown below.
`
`65
`
`Once the syndrome bit code list or pattern has been
`arranged, errors can be corrected, block 52.
`Referring again also to FIG. 1, the indicator 18 is
`adapted to indicate any one of the following four condi
`tions:
`(a) No error.
`(b) Single error.
`(c) Double error.
`(d) Multiple error.
`A syndrome code of all 0's indicates no error; one or
`more 1's in the syndrome code indicates that at least one
`error has occurred during data transmission.
`The list of error codes that identifies single bit errors
`can be used to generate a single indicative of that condi
`tion. Similarly, the list of error codes that identifies
`double bit errors can be used to generate a single indica
`tive of double bit errors. Finally, the list of all remaining
`error codes, excluding the code of all 0's, can be used to
`generate a signal indicative of multiple errors.
`Correction of single bit or double bit errors in a data
`word is accomplished merely by EXCLUSIVE ORing
`the list of single bit or double bit error codes with the
`corresponding data bits.
`Since other modifications and changes varied to fit
`particular operating requirements and environments
`will be apparent to those skilled in the art, the invention
`is not considered limited to the example chosen for
`purposes of disclosure, and covers all changes and mod
`ifications which do not constitute departures from the
`true spirit and scope of this invention.
`What is claimed is:
`1. A method for detecting multiple errors that occur
`during transfer of a data message having a plurality of
`
`IPR2018-01474
`Apple Inc. EX1009 Page 9
`
`

`

`4,589, 112
`11
`12
`(h) decoding said syndrome bits to identify the erro
`data bits and for correcting up to two of said errors, the
`steps comprising:
`neous bits in said data message.
`2. The method in accordance with claim 1 wherein
`(a) calculating a number of check bits associated with
`the number of bits bin one of said base groups is derived
`said data message;
`from the equation:
`(b) grouping all data bits in a data message into base
`groups and multiple layer groups, the sum of the
`b= Log2 (N)
`number of base groups and the number of multiple
`ps where N is the number of bits in said data message.
`layer groups of data bits being equal to said number
`3. The method in accordance with claim 2 wherein
`the number of bits m in one of said multiple layer groups
`of check bits;
`(c) assigning up to two weights for each data bit;
`is derived from the equation:
`(d) distributing data bits among said groups accord
`m = Log2 (N-b--).
`ing to weights assigned thereto;
`(e) generating a check bit for each of said groups the
`total number of generated check bits being equal to 15
`the number calculated in step (a);
`(f) padding said data message with said total number
`of generated check bits to form an appended data
`message;
`20
`(g) generating a predetermined number of syndrome
`bits, said predetermined number being equal to said
`number of check bits; and
`
`4. The method in accordance with claim 1 wherein
`said check bit is generated by performing an EXCLU
`SIVE OR operation on all of the data bits o