H .1
`
`4,003,020
`
`
`
`[45] Jan. 11, 1977
`
`3,913,068
`
`10/1975
`
`Patel
`
`...................... .. 340/146.1 AL
`
`OTHER PUBLICATIONS
`
`Bossen and Patel, Encoder and Decoder for the 2—Re—
`dundant B—Adjacent Perfect Codes, IBM Tech. Discl.
`Bulletin, vol. 14, No. 3, Aug. 1971, 680-682.
`
`Primary Examiner—Charles E. Atkinson
`Attorney, Agent, or Firm—Kem0n. Palmer &
`Estabrook
`
`[57]
`
`ABSTRACT
`
`Digital words are transmitted together with associated
`parity or checking digits. The parity bits are each re-
`lated to a group of bits of the same significance from
`several dilferent words. At a receiving station, a parity
`bit is generated for the same group from the incoming
`' words and compared with the corresponding received
`parity bit. When the generated and received parity bits
`differ, a value is estimated for each word containing a
`bit from the respective group, and the estimated and
`received values for the word are compared to detect
`any word containing an erroneous bit, which hit is then
`corrected.
`
`19 Claims, 5 Drawing Figures
`
`United States Patent “9,
`Clarke
`
`[54] DIGITAL SIGNAL TRANSMISSION
`
`[75]
`
`Inventor: Christopher Keith Perry Clarke,
`Crawley. England
`[73] Assignees: The Marconi Company Limited;
`Standard Telephones & Cables
`Limited, both of London, England
`June 30, 1975
`
`[22]
`
`Filed:
`
`[2l] Appl. No.: 592,021
`[30]
`Foreign Application Priority Data
`July 3, 1974
`United Kingdom ........... .. 29516/74
`
`.................................... .. 340/146.1 AL
`[52] U.S. Cl.
`[51]
`Int. Cl.’ ....................................... .. G06F 11/10
`[58] Field of Search ..... .. 340/146.1 AG. 146.1 AL.
`340/146.1 R, 146.1 AV; 360/38; 358/8
`
`References Cited
`UNITED STATES PATENTS
`
`............... .. 340/146.1 AL
`34')/146.1 R
`.. 340/l46.l AG
`.. 340/146.1 AL
`. . . . . . . . . . .. 340/146.1 R
`....... .. 340/146.1 AL
`.. 340/I46.l AL
`......... .. 340/146.l R
`
`
`
`Kahn .....
`6/1962
`511968 Varsos ..
`3/1971
`Parr. Jr.
`2/1973
`Oiso et al.
`7/I973
`Gibson . . . . .
`611974
`Solomon ..
`8/I974
`En
`IIII974
`Kasahara et al.
`
`[56]
`
`3,037,697
`3,386,081
`3,569,934
`3,718,903
`3,747,065
`3.818.442
`3,831,144
`3,849,761
`
`3
`p.c.m
`
`
`
`9
`9
`3/rs
`5/TS
`7/MNSM/ss/M 5/Hrs
`SIGNAL Ill/PUT
`3/75
`ERROR
`I0 '
`- Aim.9U:J£cr
`
`
`TO ERRORS
`CORRECTOR
`
`
`can/aroma
`OU TFO 7
`
`
`
`I4
`
`PAR/ff
`A/T
`
`PAR/7)’
`BIT
`
`F4 /U 77
`
`mu/=4ma
`
`* 20
`
`C/'/ECKER firs
`Log/C
`
`PMC Exhibit 202
`
`Apple v. PM
`|PR2016-0075
`
`Page 1
`
`
`
`
`
`
`
`
`
`
`PAR/7?’
`GE/VERARDR
`
`
`
`PMC Exhibit 2022
`Apple v. PMC
`IPR2016-00753
`Page 1
`
`

`
`U.S. Patent
`
`779
`
`InS
`
`3fl
`
`4
`
`KbofiQQqfiommxso
`
`mK\%
`
`momxw
`
`«ogommmou
`
`m
`
`9853.Ok
`
`bwwmsmIxvi
`
`.3
`
`mk\mmm
`mtm§\mmEm$E
`
`
`MKS..N§Q\<\:.e<,.:m
`
`m
`
`Edi
`
`
`
`0_w§EM8FbmIIIIIIIIIIIIIa.
`
`&§:a«$:o%EBEEEol_..aIIIIIIIIIIII._0mm
`0..2R.
`nw91:
`
`11k\nm>55.
`
`FmxN\.<v.Q.
`mEm
`
`x.Cw.<n\
`
`xokwwwzmm
`
`..n|uhXECMD:
`
`202...H
`
`mmmmmmP
`5mm
`egaP
`
`PMC Exhibit 2022
`Apple v. PMC
`IPR2016-00753
`Page 2
`
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Jan. 11, 1977
`
`Sheet 2 of 3
`
`4,003,020
`
`fi’£C‘f/VED
`
`BB/7.9
`
`DIFFERENCE 5'/6/VAZ
`OUTPUT T0
`COMPARISON [.06/C20
`
`
`
`I24{
`1
`
`FIG. 5
`DIFFERENCE
`S/6/V/It FROM 94
`To 98
`
`H0
`3:95
`W5
`
`
`
`
`
`IS
`MAGW/TUDE
`9/6
`
`3
`3;?”
`
`S/EWAL
`8/7’ 3
`
`FROM
`84
`
`
`
`PMC Exhibit 202
`
`Apple v. PM
`|PR2016-0075
`
`Page
`
`PMC Exhibit 2022
`Apple v. PMC
`IPR2016-00753
`Page 3
`
`

`
`U.S. Patent
`
`Jan. 11, 1977
`
`Sheet 3 of 3
`
`4,003 020
`
`(SI /9 M/V3/J//VQISISOW 1%) 104100 091338803
`
`
`
` III.938¢3.66E8vBEEEESS:#358,
`
`uofiéob
`
`.:$,$m
`
`m2532we
`
`momma
`
`girlI8..mm
`
`vinI.,1..
`
`NN«SEES
`
`20%«$28
`
`QNS93
`
`
`
`.9«mkumtux.§t<o.
`
`
`
`finCE?
`
`R
`
`P
`
`0
`
`mes
`25Me
`EpmCAPM|
`...MV.n_uP
`ZPWW
`xo.0
`I1
`
`PMC Exhibit 2022
`Apple v. PMC
`IPR2016-00753
`Page 4
`
`
`
`

`
`1
`
`4,003,020
`
`2
`merit of one parity bit assigned to the four most signifi-
`cant digits of each word, the parity bits and the signal
`bits are related by equations of the form:
`
`DIGITAL SIGNAL TRANSMISSION
`This invention relates to the transmission of digital
`signals.
`In digital television systems the video signal is com-
`monly represented by a series of eight-digit binary
`numbers. lf any of the bits are altered by errors, then
`the effect appears as a brightness error in the picture,
`the magnitude of which depends on the significance of
`the affected bit.
`Extra bits, known as parity bits, can be added to the
`signal to reduce the effect of errors. Each parity bit
`may typically describe the modulo—two sum ofa group
`of bits in the signal; the rules of modulo—two addition,
`for which the symbol ®is used. being as follows:
`
`‘l@" = "
`
`”®' =
`r@U =
`
`i@i =
`
`P" = "-®"'=®"*®"-
`5': h|@h2®h:I®hr
`
`5
`
`10
`
`P. = hl®h:®h:C®,'4
`
`'
`
`15
`
`55
`
`When a parity digit is found to differ from the modu-
`lo~2 sum of the first four digits of the associated word.
`it is known that one of those four digits is incorrect.
`However, it is not known which digit is incorrect. and
`20 thus the whole word is discarded and replaced by con-
`cealment. This means that the concealment provides a
`relatively poor approximation to the correct signal.
`According to this invention there are provided a
`method of an apparatus for generating parity digits for
`An exlcusive-OR gate is a well known circuit which
`effects modulo—two addition. Ari odd number of errors 25 a digital signal which comprises a plurality of words
`in a group is shown by disagreement between the parity
`each of which consists of a plurality of bits. in which a
`digit and the modulo—two sum of the digits, but an even
`group of bits of the same significance are selected from
`number of errors in a group cannot be detected since
`several different words with a predetermined selection
`the modulo—two sum of the digits is the same as for no
`law. and the hhs Of the group 31"? Cmhblhcd with 3
`errors. For a particular error rate, the probability of 30 P|'€d€t¢"hlh¢d
`¢0mbhl3ll°“ l3W ‘0 PYO‘-’ld¢ 3 P3Yh)’ hh
`more than one error occurring in a group increases
`35S0Cl3t€d With thc Selected 8T°“P~
`with the size of the gi-oup_ so it is an advantage to keep
`When an error is indicated each word which contains
`the number of signal bits protected by one parity bit
`3 hit h'°m ‘h¢ Suspect STOUP °3h ‘heh he C°'hP3Ted with
`small.
`the value for that word estimated from nearby words
`conventionally, one parity bit is assigned to protect 35 (in the signal or in the information which the signal
`each eight-bit word of the television signal. Then, if an
`represents) and the value which gives the best agree-
`error is indicated, the protected word is discarded in its
`lheht Whh ‘he estlmaie C3" he °h°5°“ for th'3 SUSP“-‘t
`entirety and replaced by a value which will “conceal"
`hit-
`the error. Suitable values for substitution are the aver-
`The ihV°h‘l°h 3150 P"°Vlde5 3 meihod Of 3hd 31313373-
`age ofthg two adjacent sampiesin monochrome sigr-rats 40 tus for detecting errors in a received digital signal
`or the average of samples one or more colour subcar-
`which C0ThPl'lS€9 3 Plulalh)’ Of Wmds each 0f Which
`rier period away in colour signals. The accuracy of the
`‘ Cohslsts °f 3 Ph“'3lhY Of hits» ‘he SlEh3l h3Vlh2 P3131)’
`values calculated in this way is such that errors in the
`hhsa l" which Oh‘? Parity hh is Sehefmed f0‘ each Of 3
`fifth and less significant bits are generally less notice-
`370"? of bits Of the "eC°lVed Signal to °°"'e5P°hd Wllih
`abie than the errors caused by this --c0r.rCealmenr»—_ 45 the received parity hits, the corresponding generated
`Therefore it is usual to protect only the four most sig-
`3hd "¢°°lV°d P3Th)_’ bhs 31'? °0f“P3_|’ed» _3'"3 when the
`nificant bits of each word with a parity bit,
`generated and received parity bits differ in respect of a
`Table I shows an array of eight consecutive words,
`3‘_'0UPs 3 Value ls €S1l_m3Ied f0|' each WON‘-l Chhialhlhg 3
`labelled a to h, each made up of eight bits. Digit a. is
`bit from the respective group, and the estimated and
`the most significant hit of word rr representing mg 50 received values are compared to detect any word con-
`levels in the signal, at the next in significance represent—
`7~3lhlhg_3h eT1’0he0US bili-
`irrg 54 levels‘ and so Orr down to an which is the least
`ln this way errors can be corrected rather than con-
`significant digit of word a and represents one level in
`cealedv ‘he
`‘"0" °a“5°d b3’
`°°“°“-allhehl b°l“8
`the signal.
`aV°ld°d-
`The invention will now be described in more detail.
`by way of example. Reference will be made to the
`accompanying drawings, in which:
`FIG.
`1
`is a block circuit diagram of a transmission
`system including an error correction system embodying
`60 the invention;
`FIG. 2 is a block circuit diagram of one section of a
`parity generator for use in the error correction system
`_
`of
`1,
`‘
`FIG. 3 is a block circuit diagram of an estimator for
`65 use in the system;
`FIG. 4 is a block circuit diagram of a parity checker,
`comparison logic and an error corrector for use in the
`system; and
`
`
`
`TABLE l
`Words
`Significance
`h_
`I
`dl
`3.
`C‘
`b‘
`8|
`'23
`h,
`I,
`d.
`e,
`c,
`b,
`a,
`64
`:=
`it
`3*
`:3
`:=
`:3
`:3
`fir
`ir;
`i;
`d;
`e;
`C;
`i,;
`8;
`it
`in
`hit
`ft
`d..
`c..
`b..
`a.
`4
`e.
`2
`a-,
`br
`e,
`d,
`e-,
`(1,
`g,
`h-,
`l
`an
`bu
`Cu
`du
`an
`[it
`Sir
`ha
`
`rainy bits
`9,.
`P.
`P,
`P.,
`P..
`P,
`P.
`P,,
`
`3'
`g,
`33
`
`Associated with the eight words of the signal are
`eight parity bits P,, to P... With the Coven tional arrange-
`
`PMC Exhibit 202
`
`Apple v. PM
`|PR2016-0075
`
`Page
`
`PMC Exhibit 2022
`Apple v. PMC
`IPR2016-00753
`Page 5
`
`

`
`4,003,020
`
`4
`an intervening word to facilitate the generation of an
`estimated word. These four hits form a group and are
`combined in accordance with module—2 addition to
`provide a single parity bit.
`An example will be described comparing the conven-
`tional concealmcnt method with a correction method
`in accordance with this invention as applied to the four
`most significant bits ofeight words ofa television wave-
`form. In both cases the same data will be used. In the
`data -the second digit of the fourth word has been
`changed from a ‘ l ’ to a ‘O’. This changes the value of
`,
`the word from 75 to l l . Table 3 Illustrates the conceal-
`mcnt method‘
`TABLE 3
`Concealment
`Word Numbers
`4
`5
`
`2
`
`3
`
`s
`
`7
`
`II
`
`I05
`0
`I
`I
`0
`I
`0
`U
`I
`0
`
`74
`0
`I
`(1
`0
`I
`0
`I
`0
`I
`
`ll
`
`Q;
`®
`l
`0
`l
`I
`Q)
`
`107
`t)
`I
`I
`0
`I
`0
`l
`l
`(l
`
`l37
`l
`0
`0
`0
`l
`(l
`0
`I
`I
`
`I58
`I
`(l
`II
`I
`I
`I
`I
`o
`o
`
`I67
`I
`(l
`I
`(I
`0
`I
`I
`I
`0
`
`I65
`I
`0
`I
`0
`u
`I
`0
`I
`
`l()
`
`I
`
`I37
`I
`II
`U
`U
`I
`0
`0
`I
`I
`
`3
`FIG. 5 shows one of the comparison circuits in more
`detail.
`
`As some of the nearby words in the waveform are to
`be used to estimate the value of suspect words,
`it is
`necessary to arrange that these words are from a differ-
`ent group from the subject words. An arrangement
`which is convenient for some estimation methods is to
`combine the bits of alternate words together in parity
`groups. This arrangement will be illustrated with refer-
`ence to Table 2.
`
`
`
`Stgnificancc
`
`Words
`
`Table 2
`
`Decimal values
`of signal words:
`Significance
`I2I¢
`(I4
`32
`I6
`a
`4
`2
`l
`
`Parity hits:
`
`I61
`I
`0
`|
`0
`t)
`()
`(l
`I
`
`128
`«4
`32
`its
`It
`4
`7
`}
`Parity bits
`
`II,
`-
`
`a
`-.-I
`u.,
`-
`
`b.
`b.
`hi
`h
`hi
`h.
`
`e.
`~
`
`c
`cl
`c.
`~
`
`(I,
`d
`dz
`d
`al
`d.,
`
`e,
`
`c
`cl
`e.
`
`r,
`r
`f:
`f
`fl
`f.
`
`In,
`
`P.,,
`
`I>,,
`
`9,,
`
`I>_.,
`
`P,.,
`
`g,
`3:
`g
`:3
`3“
`E:
`9.,
`
`h,
`II
`h:
`h
`hi
`h.
`
`In,
`
`In this method the eight parity bits and the eight
`words are related by equations of the form:
`
`An error is indicated in the fourth word of the block
`.
`.
`(value 1 I) because.
`0®0®"(+)0 v‘
`.
`.
`.
`35 The relevant bits In Table 3 have been circled. There-
`fore,
`In the conventional concealment method,
`the
`word is entirely discarded and replaced by the average
`of the preceding and subsequent words, that is by:
`(74 + I07 /2) =91 (rounded up).
`
`I
`
`40
`
`P.,
`I=.,,
`
`=
`=
`
`a.
`h,
`
`(D
`6)
`
`c.
`(I.
`
`Table 4 illustrates the same data in which the parity
`digits are derived as described with reference to Table
`(D
`c.
`Q
`3.
`2
`O
`r.
`(9
`II,
`'
`TABLE 4
`
`Correction
`Word Numbers
`
`I
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`I61
`
`I37
`
`I05
`
`74
`
`I l
`
`Decimal values
`of signal words:
`Significance
`I
`I
`l
`I
`0
`0
`0
`I
`I
`I28
`0
`©
`0
`©
`(0
`I
`(D
`0
`0
`64
`l
`I
`0
`0
`I
`0
`0
`I
`U
`l
`32
`0
`0
`I
`0
`0
`0
`0
`0
`0
`0
`I6
`0
`0
`I
`I
`I
`I
`I
`I
`I
`0
`II
`I
`I
`I
`0
`0
`0
`0
`0
`0
`0
`4
`0
`I
`I
`0
`I
`I
`I
`0
`0
`0
`2
`I
`I
`I
`I
`0
`I
`I
`I
`0
`I
`I
`
`Parity him:
`0
`(l
`0
`®
`I
`0
`1
`0
`
`137
`
`I58
`
`I67
`
`I65
`
`I07
`
`0
`
`Pi,
`P“
`
`=
`=
`
`21..
`hi
`
`(9
`<9
`
`«S.
`“I
`
`(9
`G)
`
`:5.
`‘4
`
`®
`<9
`
`3%
`hi
`
`That is, each parity bit is based on bits of the same
`significance selected from four different words. These
`four words are not successive words but are spaced by
`
`The fourth arit bit indicates an error in the second
`3’
`bit (significance 64) of either the 2nd, 4th. 6th or 8th
`word of the block, which bits have again been circled,
`55 because:
`
`l@()®()®(l # 0
`
`PMC Exhibit 202
`
`Apple v. PM
`|PR2016-0075
`
`Page
`
`PMC Exhibit 2022
`Apple v. PMC
`IPR2016-00753
`Page 6
`
`

`
`5
`
`4,003,020
`
`6
`
`l l, l37‘and 167 are suspect in the second bit,
`So 105,
`that is, the possible values of these words are, respec—
`tively:
`105 or 41 101101001 or 00101001)
`11 or 75 (000()l011 or 01001011)
`137 or 201 (l000100l or 11001001)
`167 or 231 (10l00lll or 11100111)
`An estimated value is now obtained for each of these
`
`U-
`
`of the preceding word is zero-order interpolation, and
`use of the average of preceding and subsequent words
`as described above is first-order or linear interpolation.
`Undoubtedly,
`the use of higher order interpolation
`produces a general improvement in monochrome esti-
`mation accuracy, although some increases in process-
`ing complexity is required. For example, interpolation
`with a quadratic law requires the formation of:
`
`words by forming the average of adjacent samples,
`thus:
`
`10
`
`in = ‘.‘u~i
`
`‘l’
`
`IA‘
`
`l,\’n I_ .\‘n»2l
`
`‘i~‘_- (137 + 74) = 105 5 for word 2
`
`‘/5174 + 107) = 90.5 for word 4
`
`'/21107 + 158) = 136.5 for word 6
`
`or using a cubic iaw
`
`F" 2 2,9. U," rl +_r"H) _ “G (M 2 + yum): W (M_‘ +
`.l'u<il ‘l‘ 1/if‘ i."u~i‘1".“-HI
`‘.1’-:
`1 ‘ .\’nr-ll
`
`15
`
`_
`
`W r 158 + '65) 2 ‘M 5 wmd 8
`
`where -y,,_2, _vr,_,, etc. are the values of consecutive
`words in the signal.
`An in.1pmVCmm." in ?0]Our esfiinatinn agcuracy may
`These estimated values are then compared with the
`possible values shown above. For word 2, the estimated 20 be Obtained by usmg‘ Suitably ".“?‘“fi°“ Vcrsiiins of ihcsc
`Value of 1055 is nearer 105 than 41_ For word 4, the
`methods. Words taken from different television lines or
`estimated value of 90.5 is nearer 75 than 1 1. For word
`fields can also be used 1." the eS“mamm.pmCC.SS.'
`6’ the estimated value of 1365 is nearer 137 than 201‘
`I A correction method in accordance with this inven-
`For word 8, the cstimatcd value of 1615 is nearer 167
`tion is especially suitable for use with
`digital televi-
`than 23 L It is thus apparent that 105’ 75, 137 and 167 25 sion recorder for two reasons‘, firstly, since errors are
`are likely to be the correct values. The error in the
`Corrected rather than, Cgnccalcdflquamy '5 preserved
`second bit of the fourth word has been correctly de-
`th“_)ugh,mmc gencrauons of ulpymg‘ arid Secfmd’ each
`tected and can be corrected. thus avoiding the sixteen-
`pamy bu protects a grfmp (if °°_“5"'°““"“' [ms 0." ‘me
`‘ever error introduced by the Concealment P“-mess,
`track on the tape. which simplifies the detection of
`which substituted 91 instead of 75.
`30 bursts of errors‘
`ln an alternative and less preferred method, the dif-
`of the ,42 micks Of one rccmderi 40 tracks are uscd
`ferences between the received and estimated values for
`for the elghbbn wmds of the {Claws-'0“ Signal‘ so that
`each word are likewise taken, thus:
`five consecutive words are spread across the tape at
`each point. The remaining two tracks are used for par-
`35 ity bits. lf only the four most significant bits of each
`Fur mini zoirremicc = 105- 105.5 =_o_5
`word are protected by parity, then ten signal bits must
`E
`: ::7"_9‘r’-156=s;7:6‘S
`be protected by each parity bit. With the normal parity
`1:", word 3: dm~e,.c,,cc = 157 _ ,;,,f5 = +53
`2lllOC'¢1[l0l'l, lZl’]lS WOl.ll(l l'Il6'cll‘l that the l')l[S f[‘()l'l'l Zlé W()l'ClS
`The differgncc with the largest magnjtudg (p]uS or
`W0l1ld be P|'0iCC"-Cd by One Pafitll bits and» in the CVCM
`minus) is then taken to indicate that that is the incor-
`40 of an error, three words would need to be replaced to
`rec; word_
`conceal the error. This much concealment would prob-
`Both the known conccalmcnt method and thc above-
`ably be m0“? “0tiC€a1310 than the CW0!”-
`described correction method are dependent on the
`With a correction method in accordance with this
`accuracy of
`the estimation In
`the concealment
`invention, ten consecutive hits on one track of the tape
`merhod_ inaccurate estimation may cause those words
`used to conceal errors to differ considerably from the 45 C311 139 Pmlcctcd by 0'10 P3710’ bit The“ W0Uld 139 bits
`correct words.
`In the correction method, inaccurate
`Of thc Same Significance from ten Words take“ at “V9
`estimation may cause bits that arc in error not to be
`word intervals from the waveform. In the case of an
`corrected and, more seriously, may corrupt bits that
`error the two possible values of each of these words can
`are not in error. However, in the correction method,
`be Comparcd With an 651110313 and, Provided the esti-
`immunity to erroneous estimates increases with the 50 mated value is sufficiently accurate, the correct value
`significance of the doubtful bit.
`chosen in each case.
`For monochrome television signals, the average of
`The temporary loss of one track, perhaps due to a
`the prcccding and subsequent words can be used to
`dust particle on the tape, could cause a burst of several
`estimate the value of suspect words. For colour signals
`hundred Errors. With the normal parity allocation
`sampled at three times subcarrier frequency, the aver- 55 method a complicated assessment of the parity error
`age of third preceding and third subsequent words
`indications must be made to determine which track is
`(words one cycle of colour subcarrier away) can be
`at fault. This is only possible if the relationship between
`used to achieve good estimates in areas of uniform
`tho:
`‘(W0 parity bits and the five associated words is
`colour, but performance is poor in areas containing fast
`made to vary in a cyclic pattern. When the faulty track
`luminance transitions. The advantages of the mono- (,0 has been identified, the words likely to be affected by
`chrome and colour averaging estimates can be com~
`errors can be replaced to conceal the errors.
`bined by using the estimate most suitable for the type of
`In the described correction method, each parity bit
`signals currently encountered. The choice of estimate
`protects signal bits from only one track, so an error
`can be judged from a running assessment of estimation
`indication immediately identifies the track affected.
`accuracy for the two methods, using those parts of the 65 However, if there are 2, 4, 6. 8 or 10 errors in a group,
`which is quite likely during bursts of errors, the parity
`signal which do not contain errors.
`check will not show an error. So, whenever a burst of
`The method used for producing estimates will nor-
`errors is suspected, it is necessary to apply correction
`mally be an interpolation procedure. For example, use
`
`PMC Exhibit 202
`
`Apple v. PM
`|PR2016-0075
`
`Page
`
`PMC Exhibit 2022
`Apple v. PMC
`IPR2016-00753
`Page 7
`
`

`
`4,003,020
`
`8
`causes an error Corrector 22 to complement the value
`of the bit or bits in error.
`
`7
`including those
`to all groups on the affected track,
`which give no error indication. Then any errors which
`are present will be corrected. although there is the risk
`of corrupting correct data if the estimate is inaccurate.
`An aid to the detection of an error burst is the possibil-
`ity of counting the errors corrected in those groups
`with positive error indications to determine whether
`there are several errors or a single error in each group.
`If several errors are found. then an error burst is likely.
`Other circuits can be introduced into the recorder. for
`example, to monitor the envelope of the replayed signal
`to give an additional indication of the presence of an
`error burst.
`
`FIG. 1 shows an error correction system embodying
`the principle of the above correction method. To an
`input 10 which receives an 8-bit pulse code modulated
`(p.c.m.) television signal is connected a parity genera-
`tor 12 which produces parity bits from, in this example,
`the four most significant bits of the p.c.m. signal
`in
`accordance with Table 2. These parity bits are trans-
`mitted with the p.c.m. signal, making a total of 9 bits.
`over a transmission path 14 subject to errors. At the
`receiving end of the path I4, in a parity checker 16
`parity bits are generated from the first four bits of the
`received signal and compared with the parity bits trans-
`mitted with the signal. The output signal from the par-
`ity chccker I6 identifies the positions of possible errors
`in the signal for each of the four protected bits sepa-
`rately.
`In the figures the number of bits transmitted over the
`various lines are indicated.
`An estimator 18 produces an estimate of the signal
`value at each point in the waveform by interpolation,
`using nearby signal values. For example, FIG. 3 (de-
`scribed below) shows an estimator which forms the
`average of samples 3 words before and after the current
`signal value. The estimate is then subtracted from the
`received value and the difference is fed to a compari-
`son logic unit 20.
`The comparison logic unit 20 takes in the first four
`bits of the received signal,
`the possible error signal
`from the parity checker 16, and the difference signal
`from the estimator 18. If a possible error is indicated,
`the logic unit 20 calculates whether or not the differ-
`ence signal
`is consistent both in sign and magnitude
`with an error in this position. When only one possible
`error occurs in a word, this can be done by rounding
`the difference signal to the level of the bit which may
`be in error. If this produces a ‘ I‘ at this level, then the
`magnitude of the error is Consistent. If the difference
`signal is positive, then the received value is larger than
`the estimated value. This suggests that a ‘0‘ in the trans-
`mitted word has been changed to a ‘I’ in the received
`word. Therefore. a '1‘ in the position of the possible
`error is consistent with a positive difference signal since
`changing the ‘I’ to a ‘0‘ will reduce the value of the
`difference signal. Similarly, the combination ofa ‘0’ in
`the position of a possible error and a negative differ-
`ence signal is consistent with an error in this position.
`The circuitry for effecting this logic operation is de-
`scribed in more detail below with reference to FIG. 5.
`More than one possible error in a word can be dealt
`with by taking the possible errors in order of decreasing
`significance and, as each error is detected, correcting
`the difference signal accordingly.
`When possible errors are indicated and the differ-
`ence signal is consistent with such errors, the compari-
`son logic unit produces a correction signal which
`
`Referring to the numerical example illustrated in
`Table 4, for the word in error, the received value is 11
`and the estimated value is 90.5. Therefore, the differ-
`ence signal would be -79.5. Since the possible error is
`in the 2nd bit, the number is rounded to the nearest
`integral multiple of 64, that is. -64. Since this corre-
`sponds to a ‘ l‘ at the bit level which may be in error this
`is consistent with an error in this position. Also,
`the
`negative sign of the difference signal combined with zi
`‘O’ in the suspect 2nd bit of the received signal is consis-
`tent with an error in this bit.
`‘
`If one of the other words in the same parity group is
`considered. for example, word 8, the received value is
`I67 and the estimated value is 161.5. Therefore, the
`difference signal would be +5.5. This rounds to 0 as the
`nearest integral multiple of 64. This suggests that the
`received value is correct. Also, with the positive sign of
`the difference and the received value ‘O’ for the second
`bit, altering the ‘O' to a ‘ I ' would increase the size of the
`difference between the word value and the estimate.
`The construction of the various elements of FIG.
`will now be described in more detail.
`The parity generator 12 comprises four circuits 5] of
`the type illustrated in FIG. 2, one for each of the four
`most significant bits of each input word. Each of these
`circuits includes an input terminal 50 connected to the
`respective terminal 10 on FIG. 1. Terminal 50 is con-
`nected to an exclusive-OR gate 52 the output of which
`is in turn applied to a 2-bit shift register 54 which func-
`tions as a delay device, the output 56 of which consti-
`tutes the output of the circuit. The output 56 of shift
`register 54 is also applied through an AND gate 58 to
`the other input of exclusive-OR gate 52. A control
`input 60 is applied to the other input of the AND gate
`58.
`
`1
`
`The exclusive-OR gate 52 and the loop through AND
`gate 58 serve to add successive inputs at terminal 50 in
`accordance with modulo 2. The shift register 54 pro-
`vides a delay in the loop which interlaces information
`from alternate incoming words, that is words I, 3, 5,
`etc. will be added modulo 2 as will words 2, 4, 6, etc..
`and the resultant outputs will be available successively
`at output 56. The circuit output can alternatively be
`taken from the output of gate 52. The AND gate 58 is
`opened by an enabling signal at the control input 60
`during each block of eight input words and is closed
`(i.e. blocked) during the first word of each block to
`reset the circuit for the new block.
`
`As noted above four circuits 51 of the type shown in
`FIG. 2 are provided and a controlled switch 62 selects
`the outputs of the circuits 51 in turn as one of the parity
`bits. In practice the eight-word blocks with respect to
`which the parity bits are generated may not be the same
`for all four digits. Thus, using the terminology of Table
`2 the successive parity bits may be generated by expres-
`sions of the form:
`
`P-:= 0i€')<‘-®<‘i@s:
`
`Pi-a= bl®d|®fl®hI
`
`P2: = ¢'2C9€:@£:@i2
`
`P111: d2@f2@/12$}:
`
`Pa: = e«'l®g"l@iiI®I‘:i
`
`10
`
`IS
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`PMC Exhibit 202
`
`Apple v. PM
`|PR2016-0075
`
`Page
`
`PMC Exhibit 2022
`Apple v. PMC
`IPR2016-00753
`Page 8
`
`

`
`9
`
`PM ‘f-"@""®J’“@’=‘
`P
`.
`4: = Ah®I4®k4®rn.
`
`P... - II. ®j.@l_. ®n.
`
`The cycle then restarts with 1'. $k, $m, 630..
`The estimator 18 of FIG. 3 is suitable for use with
`colour signals sampled at three times the colour subcar-
`rier frequency. The circuit receives the input signal
`over a line 30 which is applied to two series-connected
`3-word delay stages 32 and 34. The junction point of
`these two delays is connected to the non-inverting
`input of a subtractor 36. The input signal and the out-
`put of delay stage 34 are added in an adder 38, the
`output of which is divided by two in an attenuator 40 to
`provide the average of the input and 6-word-delayed
`signals. This average or estimated signal is applied to
`the inverting input of subtractor 36,
`the output of
`which includes a sign bit and is applied to the compari-
`son logic unit 20 of FIG. I. This difference signal thus
`represents the difference between a received word and
`the estimated value for that word.
`The parity checker 16, comparison logic 20 and error
`corrector 22 of FIG. I are shown in more detail in FIG.
`4. The parity checker 16 has an input 70 which receives
`the four most significant bits of the signal input. that is
`the signal from the transmission path 14. A parity gen-
`erator 72 the construction of which is identical to that
`of the parity generator 12 described above is connected
`to the input 70. At an input 74 the parity bits are re-
`ceived and these are compared with the bits generated
`by parity generator 72 in an exclusive-OR gate 76. The
`exclusive-OR gate 76 provides an output whenever the
`parity bit differs from the corresponding bit generated
`by generator 72, indicating the presence of an error in
`the received information.
`When an error is detected in this way the gate 76
`activates four output lines connected to enabling cir-
`cuits 80, 82, 84 and 86, associated with the four most
`significant bits respectively, an which re-associate the
`parity bit with the group of bits to which it relates. To
`this end each of these circuits, only one of which is
`shown in detail, includes a controlled switch 88 and a
`2-bit shift register 90 connected as shown. These en-
`abling circuits ensure correct timing of the correction
`enabling signals.
`The comparison logic 20 of FIG. 1 comprises four
`circuits 92, 94, 96 and 98 associated respectively with
`the first, second. third and fourth most significant bits
`and connected respectively to be enabled by outputs
`from circuits 80, 82, 84 and 86. Each of the compari-
`son circuits 92, 94, 96 and 98 also receives a respective
`bit of the signal input from transmission path 14, and
`the difference signal from subtractor 36 of estimator I8
`shown in FIG. 3 is applied to the first comparison cir-
`cuit 92 and thence successively through the other com-
`parison circuits 94, 96 and 98. The comparison circuits
`92, 94, 96 and 98 are essentially similar in construction
`and will be described in more detail below with refer-
`ence to FIG. 5. Each comparison circuit provides an
`output to a respective exclusive-OR gate 100, 102, 104
`or 106 which together constitute the error corrector
`22. The other input of each exclusive-OR gate receives
`the respective bit of the signal input.
`One of the comparison circuits, namely the circuit 96
`for the third-most~significant bit is shown in more detail
`in FIG. 5. This circuit has an input 110 at which is
`
`l0
`
`IS
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4,003 ,020
`
`10
`received the difference signal which has passed through
`circuits 92 and 94. At an input H2 is received the third
`most significant bit of the input signal from transmis-
`sion path I4, and at an input 114 is received the output
`of enabling circuit 84. The sign bit of the difference
`signal and the third signal bit are applied to an exclu-
`sive-OR gate 116. The rest of the difference signal is
`applied to a circuit 118 which detects whether the
`magnitude (i.e. modulus) of the difference signal
`is
`greater than or equal to 16, this being half the signifi-
`cance of the third bit.
`
`An AND gate 120 receives the output of magnitude
`detecter I18, gate 116 and circuit 114. Thus AND gate
`120 generates an output whenever:
`i. the difference signal is greater than or equal to 16,
`and
`the enabling circuit 84 indicates that an error
`ii.
`exists, and
`is positive and the
`iii. either the difference signal
`third bit in the signal input is l, or the difference signal
`is negative and the third bit in the signal input is 0.
`When all these three conditions are fulfilled the AND
`
`gate 120 provides a correction output which is applied
`to gate 104 to change the third bit of the signal. The
`correction output is also applied to change the position
`of a switch 122 to that shown in FIG. 5 in which the
`magnitude of the difference signal is modified by sub-
`tracting the value 32 from it in subtractor 124. The
`resultant then constitutes the difference signal for com-
`parison circuit 98.
`It will be seen that the operation of the comparison
`circuit is in the presence of an error indication signal
`for the third bit to select a value (0 or 1) for the third
`bit which gives a value for the word nearest to the
`estimated value for that word.
`Various control signals are referred to in the above
`description and these are generated by a control signal
`generator 126 (FIG. 4). The generator 126 uses en-
`tirely well-known techniques and its construction will
`be apparent to a person versed in the art from a consid-
`eration of the above-stated functions of the control
`signals, so that a detailed description thereof is not
`deemed necessary in this specification.
`Thus methods have been described in which errors in
`
`digital signals can be corrected by using an estimate
`derived from the signal waveform to choose the correct
`value of a word from a set of possible values. This
`eliminates the residual errors left by conventional con-
`cealment methods. The use of second-or third-order
`interpolation methods for calculating expected values
`of the waveform can improve the performance of the
`method.
`If monochrome
`and colour
`estimation
`schemes are operated simultaneously, it is possible to
`choose automatically the most suitable estimate for the
`type of signals encountered. The detection of error
`bursts for the digital television recorder is simplified
`when each parity bit protects signal bits on only one
`track of the tape.
`What I claim is:
`1. A method of detecting errors in a received digital
`signal which comprises a plurality of words each of
`which consists of a plurality of bits. the signal having
`parity bits, wherein the method comprises generating
`parity bits, one for each of a group of bits of the re-
`ceived signal, to correspond with the received parity
`bits. comparing the generated parity bits with the cor-
`responding received parity bits, and when the gener-
`ated and received parity bits differ in respect of a
`
`PMC Exhibit.202
`
`Apple v. PM
`|PR201