i [11]
`
`[45]
`
`4,302,775
`
`Nov. 24, 1981
`
`Bandwidth Compression—Pratt & Andrews Proc. Poly-
`technic Institute of Brooklyn, 1969, pp. 56-68.
`Hadamard Transform Image Coding, Pratt, Kane, An-
`drews, Proc. IEEE, vol. 57, No. 1, Jan. 69, pp. 58-68.
`Television Bandwidth Reduction by Encoding Spatial
`Frequencies, Andrews & Pratt, Journal SMPTE, vol.
`77, No. 12, Dec. 1968, pp. 1279-1281.
`Television Bandwidth Reduction by Fourier Image
`Coding; Andrews & Pratt, Paper Delivered to 103rd
`Technical Conference SMPTE, May 5-10, 1968.
`Transform Image Coding, Andrews & Pratt: Proc.
`Symposium on Computer Processing in Communica-
`tions, Polytechnic Institute of Brooklyn, Apr. 8-10,
`1969, Pp. 63-84.
`
`Primary Examiner—James W. Moffitt
`Assistant Exam1'ner—Aristotelis M. Psitos
`Attorney, Agent, or Ft'rm—David B. Harrison.
`
`[57]
`
`ABSTRACT
`
`A digital video compression system and its methods for
`compressing digitalized video signals in real time at
`rates up to NTSC color broadcast rates are disclosed.
`The system compressor
`receives digitalized video
`frames divided into subframes, performs in a single pass
`a spatial domain to transform domain transformation in
`two dimensions of the picture elements of each sub-
`frame, normalizes the resultant coefficients by a normal-
`ization factor having a predetermined compression ratio
`component and an adaptive rate buffer capacity control
`feedback component, to provide compression, encodes
`the coefficients and stores them in a first rate buffer
`memory asynchronously at a high data transfer rate
`from which they are put out at a slower, synchronous
`rate. The compressor adaptively determines the rate
`buffer capacity control feedback component in relation
`to instantaneous data content of the rate buffer memory
`in relation to its capacity, and it controls the absolute
`quantity of data resulting from the normalization step so
`that the buffer memory is never completely emptied and
`never completely filled. In expansion, the system essen-
`tially mirrors the steps performed during compression.
`An efficient, high speed decoder forms an important
`aspect of the present invention. The compression sys-
`tem forms an important element of a disclosed color
`broadcast compression system.
`
`7 Claims, 30 Drawing Figures
`
`United States Patent
`
`[19]
`
`Widergren et al.
`
`[54] DIGITAL VIDEO COMPRESSION SYSTEM
`AND METHODS UTILIZING SCENE
`ADAPTIVE CODING WITH RATE BUFFER
`FEEDBACK
`
`[75]
`
`Inventors: Robert D. Widergren, Saratoga;
`Wen-I-Isiung Chen, Sunnyvale;
`Stanley C. Fralick, Saratoga; Andrew
`G. Tescher, Claremont, all of Calif.
`Compression Labs, Inc., San Jose,
`Calif.
`
`[73] Assignee:
`
`[21] App]. No.: 969,991
`{22] Filed:
`Dec. 15, 1978
`[51]
`Int. c1.3 ...................... .. H04N 7/12;:H04N 9/32;
`G06F 15/20; G08C 9/00
`[52] US. Cl. .................................... .. 358/136; 358/ 13;
`340/347 DD; 364/514; 364/515; 364/582
`[58] Field of Search ............. .. 364/514, 515, 576, 582;
`358/12, 13, 133, 138, 260, 261; 340/347 DD
`References Cited
`U.S. PATENT DOCUMENTS
`
`[56]
`
`........... .. 358/135 X
`.... .. 358/135
`.. 340/347 DD
`358/136
`
`..
`
`358/13
`. 325/419 X
`.... .. 358/133
`...... 358/261
`................ .. 358/13 X
`
`
`
`3/1974 Golding et al.
`3,795,763
`.
`3,984,626 10/1976 Mounts et al.
`4,005,411
`1/1977 Morris .......... ..
`4,047,221
`9/1977 Yasuda et al.
`.
`4,051,530
`9/1977 Kuroda et al.
`.
`4,054,909 10/1977 Kojima et al.
`4,060,797 11/1977 Maxwell et al.
`4,125,861 11/1978 Mounts et al.
`4,168,513
`9/1979 Hains et al.
`4,179,710 12/1979 Ishiguro et al.
`
`.
`
`OTHER PUBLICATIONS
`
`Image Data Compression by Predictive Coding II: En-
`coding Algorithms Bahl & Kobayashi: IBM J. Res.
`Develop., Mar. 1974, pp. 172-179.
`Frame—to—Frame Coding of Television Pictures Using
`Two—Dimensional Fourier Transforms: Haskell: IEEE
`Transactions on Info. Theory: vol. IT-20, No. 1, pp.
`119-120: Jan. 74.
`
`Spahal Transform Coding of Color Images: Pratt:
`IEEE Transactions on Comm. Technology, vol. Co-
`m—19, No. 6, Dec. 71, pp. 980-992.
`Goertzel et al., Two—Dimensional Data Compression &
`Decompression System; Aug. 7, 1979.
`‘
`Application of Fourier—Haclamard Transformation to
`
`
`
`
`-
`
`Muurlrtsxin
`28
`omen LUMINANCE
`
`29
`
`FI
`
`20
`
`‘Z
`
`EXPINDEFI 52
`
`1
`"T4 LIMITED
`| annnwmrul
`I
`MEDIUM
`
`1L
`
`PMC Exhibit 213
`
`Apple v. PM
`|PR2016-0075
`
`Page 1
`
`
`
`
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 1
`
`

`
`U.S. Patent
`
`Nov. 24, 1981
`
`Sheet 1 of 22
`
`4,302,775
`
`MmmoooHmmooozm
`
`
`
`
`
`,.2.zo_§._o>zoo..wm_xn._._.=H_2,_somxoS802moz<z_2om:owm
`
`II|922358mmEm>zooo_n5<_I_<3_22mmozixm,m¢
`
`
`
`_2mon_mz.<EM_moz<z.s_3mw_.,W__wm<mémmoomooo
`
`_:S_»>m‘z«m__mv_n__om__Tl:omo_mommmmmzoom.__m.H_.o.w,,
`
`I
`..IIIImofimimm
`22.82.
`
`.mo<uEm»z_8+2
`ONWN.®OmQ_>
`
`2
`
`,82>
`
`
`
`o_n5<Puaoo
`
`muooozm_mo,&mH.:z_
`
`son.2o_a:<m_o:<
`
`_mmm.:>
`
`muooowo
`
`
`
`.s_o$._oomoooo1N
`.,.moE._on_mE.z_
`
`mafia
`
`Tmmooumo
`m_>_.E<o<
`
`
`
`
`
`._.m._mo...m_.a..E.H
`
`GIN
`
`mzaoo
`
`.Hmm
`
`mm_2_ns_oo
`
`89>
`
`mo<nEmE_
`
`PMC Exhibit 213
`
`Apmev.PM
`|PR2016-0075
`
`Page
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 2
`
`
`
`
`
`
`
`

`
`mzaoo
`
`sEon.mz<_E
`
`
`ummu>z_
` .3.3...mwmm>z_<N_fiw_.»moz
`
`
`
`o.z_n._oom_o
`
`mbqm
`
`mmtnm.
`
`.
`
`
`
`mmtsmmz._mOo
`
`_zzo.._mz<E
`
`U.S. Patent
`
`Nov. 24, 1981
`
`Sheet 2 of 22
`
`4,302,775
`
`#30
`
`
`
`H4:omxr.
`
`:4:
`
`
`._._...O<»<oF152,..N.522O.
`m|_u_u=.=._wm.En5:wm|_..._n_DIm.m._..E2._m
`
`
`
`
`0&4.0%/u.0&4O_nw__<
`
`
`
`wm on.2..mmmm.S
`
`._oE.z8
`
`..~..~_.2
`
`.mm.3
`
`.$.8mmzwwxmm.9E238//29::m-¢xood
`
`pmmmm
`
`PMC Exhibit 213
`
`Apple v. PM
`|PR2016-0075
`
`Page
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 3
`
`
`
`
`
`

`
`N..._oE2ou
`
`mmnrsm
`
`IL&Imwm NWJANM
`
`%w3Mn
`
`.33KWKLDQ..z<srE::
`
`
`
`
`‘>mos_m_s_I.mmaoomo
`
`
`._<zoo<_o
`
`z_aqua
`
`
`
`..Eozms.
`
`«Eaas
`
`..mm..r.Sm
`
`Hmmooozm\,....
`
`n_<z8<_o
`
`
`
`Wmmm8<_.
`
`V630
`
`02$
`
`mo.5m._um
`
`om._mz.&»zoE
`>:._<:oDEm
`
`05V\N»
`
`
`mmooomoz<z_s5._.4.
`
`_m.
`
`cmez_s__»
`
`._oE.z8
`
`Wm..m2<¢Eomn.
`
`
`
`E0002moz<z_s_:._.m
`om_mm_K
`m=¢omk?um§woz__>_:.
`3moi
`
`wm
`
`$2550.5
`
`..n|uhXECMD:
`
`312...H
`
`“WmP
`
`mwm
`5mm
`“mm
`egaP
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 4
`
`
`
`
`
`
`

`
`.
`
`4,302,775
`
`E?
`u.
`
`S!
`u.
`
`u.
`
`Q as
`u.
`u.
`
`0 Q‘ to go
`m m
`
`0
`
`_
`
`t~
`
`oI
`
`I
`
`O
`
`I
`
`O
`
`O
`
`0
`
`0
`
`0
`
`.
`
`O
`
`O
`
`O
`
`I
`
`O
`
`O
`
`O
`
`0
`
`co
`
`
`4.2pa:4.
`W/4M«H«\\.V\./.a.A“.flw.I¥.{4~\.“HHmm~M%««.\%A»V.IrlN.%...w
`
`I
`
`PMC Exhibit 213
`
`Applev. PM
`PR2016-0075
`
`Page
`
`.
`
`Sheet 4 of 22
`
`Nov.24,1981
`EHH§$w44W‘\Hi_,H..\%V//u4\wxi/a.
`
` %
`
`Patent
`
`.¢.Om.u_
`
`.O»
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 5
`
`
`

`
`U.S. Patent
`
`Nov. 24, 1981
`
`Sheet 5 of 22
`
`4,302,775
`
`DATA IN
`
`71
`
`A ADDRESS
`
`: B ADDRESS
`
`
`
`
`
`
`
`|6xn
`|6xn'
`DUAL PORT
`1
`DUAL PORT
`RAM
`RAM
`
`
`E
`-
`
`..
`
`-
`
`W
`
`II
`22 H WE
`.
`OEA
`: OEB
`
`INPUT a
`SHUFFLE
`
`CONTROL
`
`l|6
`
`
`
`
`
`.
`
`T
`
`-é
`PIPELINE
`REGISTER :
`
`PIPELINE
`REGISTER
`
`ADD/SUBTRACT
`
`I20 _
`
`V7
`
`..
`
`.
`
`s:
`‘
`
`I22
`
`;
`
`-
`
`
`
`'°2I6g°4«
`DATA OUT
`| (8x 2l4T)
`FIG 8
`(HORIZONTAL)
`_]
`4§‘;M8
`L (VERTICAL)
`DATA IN
`8
`(sxzm,
`DATA OUT
`
`
`n-I!
`
`PMC Exhibit 213
`
`Apple v. PM
`|PR2016-0075
`
`Page
`
` 4Kx8
`
`(8x2|47)
`
`;
`
`
`
`; C
`
`C LOCK
`
`A
`
`' BANK
`WRITE
`SELECT
`
`ONTROL
`CH I P SEL
`BIWRITE ENABLE
`TO EACH BANK
`
`CLOCK
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 6
`
`

`
`US, Patent A Nov. 24, 1981
`
`%
`
`Sheet 6 of 22
`DATA IN
`
`4,302,775
`
`FIG. 7 A
`
`B ADDRESS
`
`A
`
`-22.
`
`WE
`
`'1 ’0EA
`
` II; A ADDRESS .
`
`INPUT a
`SHUFFLE
`CONTROL A
`
`(353
`—
`
`-
`
`_
`.26
`
`130
`
`I28
`
`I32
`
`PIPELINE REGISTER‘
`
`PIPELINE REGISTER
`
`'
`
`.
`
`_
`
`‘
`
`I
`
`I”
`I
`
`_.
`
`/2
`-1
`
`’I
`
`.-
`I
`.
`V —|
`.
`I
`_MUL.TIPLlER -
`MU’-T—5—.43—I_
`,
`MULTIPLIER
`;
`A
`I
`5I2x8
`MULl;B_4_ __‘___ _ __ _ '__
`PROM I
`I42 B
`-
`.
`I
`55352;
`‘ I
`_!/I36
`:
`A
`I
`I
`|
`\+
`‘ En/4] 'LSZ83
`I
`I
`I
`I
`I
`I
`-
`L._.._ ___4 |____'____I
`
`5|2x8
`IMO PROM
`
`.
`
`I34
`
`.
`
`_
`
`I44
`
`'
`
`% 8
`
`n
`
`_
`
`n
`
`|O6,I|0
`
`ADD / SUBTRACT
`-
`
`.
`
`a
`
`,, _3.T
`ALU
`
`use
`
`nil
`
`DATA OUT
`
`PMC Exhibit 213
`
`Apple v. PM
`|PR2016-0075
`
`Page
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 7
`
`

`
`US. Patent
`
`Nov. 24, 1931
`
`Sheet 7 of 22
`
`4,302,775
`
`DATA IN ~—~--—-*-
`
`
`
`
`IGO - _
`
`LATCHED
`
`8
`
`DATA OUT
`'72
`
`I70
`
`LATCHED
`MUX
`
`_
`
`I64
`
`/”
`66. 92
`
`
`
`READ
`ADDRESS
`COUNTR _'
`3
`
`
`
`%
`
`4
`
` ‘
`
`CLOCK
`
`CONTROL
`
`mg g
`
`CONTROL
`CONTROL
`(WRITE ENABLE a
`OUTPUT ENABLE)
`
`CLOCK
`
`TRANSFORM PIXEL ROW
`
`
`
`TRANSFORM PIXEL COLUMNS
`
`PMC Exhibit 213
`
`Apmev{PM
`IPR2016-0075
`
`Page
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 8
`
`

`
`U.S. Patent
`
`Nov, 24, 1981
`
`57
`
`
`
`
`
`.Eozm:mmm.mm.
`
`f55.0%.m0M58obmun
`22mommn
`
`20$.“.58oo8uz>mms_<Ematw3.oh..mmxommS.¢mo._zm..._
`
`
`
`
`oz>mms_<Etmsmm2Emtne.fifizaooa
`A.omm.¢m_
`Emursm.:._I:55:23
`
`oh«:5..<_mmm
`
`
`
`Eozmzmmuizm
`
`om.m:.<»m.5
`mmm.5.omm
`
`3..
`
`mmom,8_m,
`
`Emtam.mmxmmmmxov
`
`sow:maooE:
`
`.mam%.-I.:m..m._
`mmooow._mzmmmuiomm
`Eozm:Em_o._&moo98..
`
`mooomom0<._.<o
`
`
`
`»zm__oEmoo.Em_o_&uoom
`
`com3N4:maxflaxoomzo_m.m_mweE2EmaaM¢mmmjomkzoommooozuow__.0_.u_0mjaom_._5zn._._
`
`
`
`
`PMC Exhibit 213
`
`Apple v. PM
`|PR2016-0075
`
`Page
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 9
`
`
`
`

`
`U.S. Patent
`
`1
`
`1
`
`6kn.
`
`9
`
`2
`
`3,
`
`ca
`
`530
`
`EHOflzmmm
`
`mmfimamm_m.55%ma?8..mxmWEtna
`
`Jmh<m
`
`mmme
`
`mmoem.Non:mmmmm
`mwmwmobiN0mV.Um.
`M,sN.mi
`
`mmmE8<E...“
`
`V890
`
`:2.:,_m_o_..rm_oox.2»zm_oEnn._ooxE320%.
`
`Trnn<qp|n1;
`
`
`
`
`
`S_+zmoooxxxxxx288xxxxxxxxxxTzM58._.:O20$
`
`9.o,m:-z.mon
`
`axxxx2moooxxx.12moooxxxH20mummxa
`
`4ma
`
`n4-nuzoaJam
`
`zew4mm
`
`
`
`7/..7.,ouztfioramoo.onTz.Em_oEmoo.ouN12»zm_u_.._..m_oo
`
`
`
`
`
`..n|uhXECMD:
`
`312...H
`
`“WmP
`
`mwm M5PWv.n_u
`
`
`0.0
`1egaP
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 10
`
`
`
`
`

`
`U.S. Patent
`
`Nov. 24, 1981
`
`.m_.9“.
`
`m4mam0amN9
`
`momom
`
`4mom
`
`mmkzaooopam
`
`uzqmm
`
`mmpzaoo
`
`mm»z:ou
`
`A4zwa
`
`
`mmooozmoh»om4um
`
`.mwe.aoo:»ozu4
`
`wuomm4m<»mmz:mmE.mm
`
`n4.zm.
`
`2mm..._oEzoo:12ON...
`pm.Eos_m228...EBxoodmmqxm-~
`
`numuooozm
`
`03
`
`atFarm
`n4mmmuamopomo;
`
`9»mo:m2mzoa_;
`
`:aM.17usedP
`
`mPWW...HV.0.ab6Pmm1XD.0ED.2CAW
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 11
`
`
`
`
`

`
`U.S. Patent
`
`Nov. 24, 1981
`
`Sheet 11 of 22
`
`4,302,775
`
`
`
`STATE(Q) *;”__—‘ T== DELAY THRU STATE
`LOGIC
`
`ACHON CHANGE
`N STATE :m 2
`‘D’
`Tr ¢33'1:2—':¢;N
`
`T = oummom OF
`
`C°NTR("C'-)
`
`¢|
`
`jx_—;_**__“——___“:_*“_
`T2
`|——-1
`
`T3
`
`FLAGS (F) :i__..__*‘“_‘-—:"_
`
`T4
`______I-TT"l_______
`
`(252
`
`,
`
`T = DURATION OF
`4
`LATCH c._o5.NG
`
`TOTAL = so TO 40 ns
`
`PMC Exhibit 213
`Apple v. PM
`|PR2016-0075
`
`Page 1
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 12
`
`

`
`U.S. Patent
`
`Nov. 24, 1981
`
`ASheet12of22
`
`4,302,775
`
`STATE
`
`FLAG
`
`£44‘:/i(TTIa
`
`CONTROL
`
`°I
`
`02 03
`
`Fe Fe Fs
`
`DI D2 03
`
`“F “I3
`
`‘*2 Cs RD NI:
`
`0
`
`o
`
`o
`
`o
`
`o
`
`o
`
`o
`
`I
`
`o
`
`o
`
`x
`
`x
`
`o
`
`o
`
`o
`
`o
`
`I
`
`o
`
`o
`
`o
`
`o
`
`o
`
`I
`
`I
`
`o
`
`I
`
`RST
`
`o
`
`I
`
`I
`
`I
`
`RC
`
`RC
`
`I
`
`I
`
`RC
`
`0
`
`o
`
`o
`
`o
`
`o
`
`o
`
`o
`
`o
`
`o
`
`I
`
`I’
`
`I
`
`x
`
`o
`
`o
`
`I
`
`I
`
`o
`
`I
`
`x
`
`x
`
`x
`
`x
`
`x
`
`I
`
`o
`
`I
`
`o
`
`o
`
`o
`
`I
`
`I
`
`o
`
`o
`
`o
`
`o
`
`o
`
`I
`
`o
`
`o
`
`I
`
`o
`
`RST o
`
`o’
`
`o
`
`o
`
`o
`
`o
`
`I
`
`o
`
`o
`
`o
`
`o
`
`o
`
`I
`
`I
`
`I
`
`o
`
`o x x
`
`x
`
`I
`
`o
`
`x xx
`
`I
`
`o
`
`x
`
`x
`
`o
`
`o
`
`o
`
`0
`
`o
`
`o
`
`I
`
`o
`
`o
`
`o
`
`I
`
`o
`
`o
`
`I
`
`o
`
`o
`
`o
`
`o
`
`o
`
`o
`
`I RST RST
`
`o
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`RLS o
`
`RI.
`
`0
`
`RE
`
`RE
`
`I"
`
`I
`
`I
`
`I
`
`I
`
`I
`
`o
`
`o
`
`o
`
`o
`
`o
`
`o
`
`I
`
`I
`
`FIG. I6
`
`x
`
`I
`
`o
`
`x
`
`x
`
`x
`
`I
`
`x
`
`x
`
`I
`
`o
`
`o
`
`o
`
`o
`
`I
`
`o
`
`I
`
`o
`
`o
`
`RST I
`
`RST
`
`I
`
`o
`
`o
`
`I
`
`I
`
`I
`
`I
`
`RE
`
`0
`
`RF
`
`RF
`
`I
`
`I
`
`PMC Exhibit 213
`
`Apple v. PM
`|PR2016-0075
`
`Page 1
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 13
`
`

`
`tHetaD...SU
`
`odN4,2v.0N
`
`Sheet 13 of 22
`
`4,302,775
`
`<55
`
`5m.n._m
`
`owmmeu
`
`mm._._oE.zoomm.._n=._ms_om.._
`
`
`
`
`m4<zo_m~m=.FoI34
`mzoornfioaamodn__:E«mm.mEmoz>m
`
`
`
`«Ea..<Emm
`
`.
`
`
`
`mvm.Eum.53..
`
`
`
`»_2<m
`
`
`
`Tooms?5.mummam
`
`mmoouzm.
`
`
`
`Em._._oEzoo.
`
`,W8
`
`mmmEo<LMmwmu
`o..=.._|_|_.Dn_96..
`
`MB>8E:o.&N.<20..5n_z_.._«.__.~,mw
`
`
`
`
`
`Kimo..__.._
`
`o
`
`
`
`I..5528momma
`
`on-
`
`
`
`Em.joE.zoommooozm.
`
`PMC Exhibit 213
`
`Apple v. PM
`|PR2016-0075
`
`Page 1
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 14
`
`
`
`
`

`
`% U.S. Patent
`
`.2v.0N
`
`4,
`
`1|.8
`
`._.DO93
`
`mutamO._.
`
`Eozmz
`
`m_.oE
`
`9.
`
`mo:52.
`
`
`M3%wm;-
`Sm_2<E
`
`
`
`“EE<mxzo_mmmEzoo
`
`El.0
`
`2«mm
`
`57
`
`2momV50.5._...__:m0omm3,,_a%,%.
`an4mmmmoo<25.NN
`7..:4;
`
`.
`
`2m._m<_z_2<mooE
`
`«EaSmdm
`
`mmwzsoo
`
`PMC Exhibit 213
`
`Apple v. PM
`|PR2016-0075
`
`Page 1
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 15
`
`
`

`
`U.S. Patent
`
`Nov. 24, 1981
`
`Sheet 15 of éz
`
`4,302,775
`
`FIG. i9
`
`OUTPUT READ CYCLE
`
`B4
`
`39:2
`SEL
`DATA
`
`SYNC INSERTION SEQUENCE
`
`T
`
`‘
`
`WAIT
`
`__l—_—L__
`
`LOAD
`F”"0
`
`I
`
`I
`LOAD INPUT FIFO SEQUENCE
`
`RDY __l'-‘_l____F-L____|'_|____
`
`INPUT WRITE CYCLE
`
`PMC Exhibit 213
`
`Apple v. PM
`|PR2016-0075
`
`Page 1
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 16
`
`

`
`18W
`
`Sheet 16 of 22
`
`4,302,775
`
`O N 9
`
`'
`U.
`
`--
`
`>mm<o
`
`o<m:<.v_oo._
`
`..LnCt3PSU
`
`2V.ON
`
`AuONM
`
`
`
`
`
`22....$228:9<Nmtom._<zmutn._
`
`ownw.2mmm
`
`
`
`
`
`mzoosEon.mz<Exoo._m
`
`
`
`
`
`mm::n_.522zo:.<N_._<s_mozOh
`
`
`
`
`
`52.. .mT§o§,$_.%w_¢mlw.momm.
`
`
`
`
`
`N¢n292..zmN.m
`
`>o<mEE28rm.
`
`.man
`
`.E:mmm»z_
`
`moSm>
`
`Amxmm.
`n_<2
`
`wmm
`
`o¢xmmm
`Eozms
`
`s_<moomn_omo_z
`
`mz_._mn_Emo
`mufiomx
`
`.nXECMD:
`
`..n|u
`
`312...M
`
`p2ARP
`
`mm0-0 M5PWv.0.
`
`
`1egaP
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 17
`
`
`
`
`
`
`
`

`
`U.S. Patent
`
`Nov. 24, 1981
`
`Sheet 17 of 22
`
`4,302,775
`
`P§:“é$§R‘%P
`
`,,EL,,<g{:,!>L,
`°°”5TANT
`
`B”m:‘i\%‘¢”T
`
`A
`
`
`
`REGISTER
`DI-IF'N|T'°N
`R'=S(k)-S(k—|)
`R2=I.5-S(k-I)
`R3=S(k) SIGN (s(k)~' S(k_-|))
`R4=S(k)
`R5=TEMP0RARY STORAGE FOR °(k)
`
`R6=TEMP0RARY STORAGE
`
`R7=D(k)
`
`R8=|/D(k)
`
`R9=R0/R|
`
`(CONSTANT)
`
`BLOCK TRANSFORM
`DONE
`
`
`
`
`
`
`INTO R9
`
`DONE
`
`CHANGE RATE
`
`LOAD EXTERNAL
`REG IST ER:
`
`RAD CLK
`|_oAD |=| F0
`
`NEXT BIT
`CLOCK
`
`B4
`Q
`
`___I"|::
`3-‘;
`._____.l"'L__
`
`READ/WRITE SEQUENCE
`
`LOAD SHIFT REGISTER SEQUENCE
`
`PMC Exhibit 213
`
`Apple v. PM
`|PR2016-0075
`
`Page 1
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 18
`
`

`
`U.S. Patent 4 Nov. 24, 1981
`
`Sheet 18 of 22
`
`4,302,775
`
`wmmmoo<
`
`mmhzaoo
`
`o<um
`
`mmmmoo<
`
`-mo-.om
`
`wmmmpzzoo
`
`:m-¢
`
`mtmz,mm»
`
`33Io..__.._
`I8.....|I|fie.
`
`in«mm.«m
`
`
`mmpznooww<ImIN
`5%anvmo_L
`
`o.Sb
`
`IE1_u
`
`MP
`
`t
` _.mvhmxo.
`
`CA
`MM2P
`ED.
`|PR2016-6075
`Page 1
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 19
`
`
`
`
`
`
`

`
`US. Patent
`
`Nov. 24, 1981
`
`Sheet 19 of 22
`
`4,302,775
`
`
`
`mam.29mA
`
`
`
`ummooé...D%..._MDO
`
`w..:mo.Sm.__mw:$5.
`
`.XE8ommmNfiummm%omon_mo
`
`
`mmu-—muaoomowow>9..6
`mom..._mIN.;<._.2_
`
`xood
`
`oz>m
`
`mommfiznoo
`tmum
`
`
`
`5:8%_2<..
`
`52..~n._u_..sm
`
`.dwmumo
`
`
`3}.2om;>o<mm
`
`v.OO|_0Ou:n_
`
`
` w_v.HIEu.
`
`-goodrm.Caz
`
`o_¢wzu
`
`omvntm
`mu._.m_ommfl
`
`
`
`._om,m.mmnfioo\
`
`mm
`
`EémmQMmE
`
`PMC Exhibit 213
`
`Apple v. PM
`|PR2016-0075
`
`Page 2
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 20
`
`
`
`
`

`
`U.S. Patent
`
`Nov. 24, 1981
`
`Sheet 20 of 22
`
`4,302,775
`
`
`
`FIG. 27
`NEXT BIT CLK
`
`
`
`DATA
`
`LATCH OUTP_UT
`
`PROM OUTPUT
`
`SHIFT IN (LOAD FIFO)
`
`FIG. 28
`SHIFT OUT
`
`FIFO OUT
`
`ZERO CODE
`
`A NEXT COEF-F CODE
`
`JAM COUNTER
`
`CO U NT CLOCK
`
`OVER FLOW
`
`___m___‘
`
`W ______... _._ . __
`
`PMC Exhibit 213
`
`Apple v. PM
`|PR2016-0075
`
`Page 21
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 21
`
`

`
`U
`
`tHCta%P
`
`omooozm
`
`o._.
`
`.504..<m<a9:...
`
`<...<on_mwmw
`
`7,2
`
`<4
`
`
`
`wimmooouomoz<z\zom:o
`
`42w0N“
`
`M9
`
`S
`
`22:1
`
`Aw
`
`paakno
`
`Jomrzoo
`
`nu.mm
`nsw/x
`
`
`
`anxoogoJmxz
`
`1._o4u:
`oommmmsm
`
`hmonem¢¢¢¢vxnzmoNew«av
`a4z_<e<omomooozu
`
`
`
`muooozmmoz<z\2om:o
`
`oz>m
`
`PMC Exhibit 213
`
`Apple v. PM
`|PR2016-0075
`
`Page 2
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 22
`
`
`

`
`U.S. Patent
`
`Nov. 24, 1981
`
`Sheet 22 of 22
`
`4,302,775
`
`T°co%%'Ii“
`
`DATA
`CLOCK
`
`
`
`?§E%EV
`SCOUNTER
`
`PROM
`2 33*?
`
`452
`
`svuc
`WORD -
`
`’
`
`SOUND
`
`FIFO
`READY
`
`DATA
`C‘-0°“
`FIFO
`READY
`
`CHROM DATA
`CLOCK
`FIFO
`READY
`
`FIFO
`
`F'F°
`
`460
`
`I
`
`‘
`
`458
`
`SELECTOR
`,
`
`- _
`.
`
`LUM DATA
`
`FIFO
`
`464
`
`\\
`as
`
`46
`
`a
`
`466
`
`FROM
`VFTERBI
`DECODER
`
`D ATA
`
`4M
`
`UEHPLEXER
`
`456
`
`473
`
`»
`
`DEMULTIPLEXER
`
`5-sn'V
`FRAME .
`COUNTER
`
`PMC Exhibit 213
`
`Apple v. PM
`|PR2016-0075
`
`Page 2
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 23
`
`

`
`1
`
`4,302,775
`
`DIGITAL VIDEO COMPRESSION SYSTEM AND
`METHODS UTILIZING SCENE ADAPTIVE
`CODING WITH RATE BUFFER FEEDBACK .
`
`BACKGROUND OF THE INVENTION
`The present invention relates to methods and appara-
`tus for compression, transfer through a limited band-
`width medium, and expansion of digitalized television
`picture signals-at real time rates up to standard broad-
`cast frame rates.. More particularly, thevpresent inven-
`tion relates to methods and apparatus for television
`picture single pass scene adaptive compression, transfer
`and expansion with two dimensional transformation in
`conjunction with compression coding schemes wherein
`rate buffer feedback is effectively utilized to provide
`optimalized compression normalization factoring in real
`time without undue degradation of restored picture
`imagery and with minimized hardware implementation
`requirements. "
`,
`Digital coding techniques are increasingly employed
`in processing television signals for transfer over noisy
`transmission channels. Digital data streams may be
`made essentially free of noise ‘degradation, and this
`advantage in the transmission of digitized information
`has_been advantageously utilized over long, noisy trans-
`mission paths. Thus, it is an increasingly common prac-
`tice today to digitalize broadcast television signals for
`transmission and relay through otherwise noisy long
`distance paths, such as stationary earth satellitesmany
`thousands of miles away from the earth.
`To digitize a televion signal, a significant number of
`bits, 4, 5, 6 or even more, may be requiredvto provide for
`the proper range of gray ‘scale of each of the hundreds
`of thousands of separate picture elements (pixels). Con-
`sequently, data rates for digitalized television signals are
`far in excess of the highest frequency components of
`analog _television'signals. It is not unusual to find in a
`digitalized television communications link, a required
`video bandwidth of 40 megabits per second. While
`digitalized television transmission formats advanta-
`geously overcome the signal to noise problems inherent
`in analog transmission over similar path lengths,
`the
`substantial bandwidths for such digitalized signals often
`occupy the entire bandwidth capability of the commu-
`nications link- If the communications link is an earth
`satellite in stationary orbit above the earth, the video
`signal typically occupies the entire transponder band-—
`width of the satellite, with very few channels, if any, left
`over for other uses. Thus, need has arisen for a practical
`yet effective way to reduce the bandwidth of digitalized
`television signals to provide for more channels within a
`communications path such as anearth satellite.
`BRIEF, DESCRIPTION OFPERTINIENT PRIOR
`'
`_
`V’
`_ ART
`It is known and discussed in the prior art relating to
`television ‘image bandwidth compression that two-di-
`mensional cosine transform techniques have yielded
`reproduced pictures of superior quality at the same and
`even higher picture data compression ratios than were
`obtainable with other transforms or techniques. I-Iereto-‘
`fore, television picture compression techniques have
`been directed to simple implementations with substane I
`tial throughput speedsin real time with concomitant
`significant degradation of restored picture resolution
`and the introduction of unwanted compression process
`artifacts into the restored picture. Such techniques have
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65,
`
`2
`included two-dimensional digital pulse code modulation
`schemes with block adaptive coding or with rate buffer-
`ing; hybrid cosine transformation and digital pulse code
`modulation schemes; and, unidimensional, bidimen-
`sional and hybrid Haar-Hadamard transformations. Run
`length coding has also been employed.
`. Two basic techniques for coding transform domain
`coefficients: are known in the prior art, namely zonal
`coding and adaptive coding. Zonal coding essentially
`eliminated all high frequency picture transform coeffici-
`ents regardless of energy content with a resultant loss of
`picture detail upon reconstitution of the picture. On the
`other hand, adaptive coding schemes, including thresh-
`old sampling techniques, were used to identify and pre-
`serve» large amplitude high frequency coefficients, and
`those schemes provided reconstituted pictures having
`less distortion from the compression process at signifi-
`cantly higher degrees of compression.
`In threshold
`sampling when a coefficient exceeded a preset ampli-
`tude, it was sent with full precision (normally 6 to 8
`bits), and many times a coefficient was transmitted with
`8 bits when one or two bits would have accurately
`characterized the coefficient.
`.
`
`Adaptive coding techniques followed two basic ap-
`proaches: multiple class energy bit map coding and
`recursive coding with rate buffer feedback. In the multi-
`ple class bit map approach, transform sub-fraines of the
`picture were sorted into categories related to the level
`of image-activity present in each sub-frame. Within each
`activity level, AC energy coding bits were allocated to
`individual transform elements in classes according to a
`variance matrix of the transform data with the variance
`matrix being computed for each of the classes and dif-
`ferent bit allocation matrices being created with more
`bits being assigned to areas of high image activity and
`fewer bits to those areas of lower activity. Such classifi-
`cations were carried out either with a two-pass statisti-
`cal gathering and mapping scheme or with a fixed
`pregenerated statistical model created upon assump-
`tions, made for the particular system application.
`In the two-pass approach, the first pass of processing
`generated statistics for sub-block classification maps, set
`up bit assignment matrices and calculated normalization .
`factors for compression. The second pass was for multi-
`plying the normalization factor to quantize transform
`coefficients, for encoding the resultant. data, and for
`adding overhead information. The drawback of the two
`pass approach is the substantial times required for two
`pass processing within existing equipment which un-
`duly limited the size of pictures to be compressed and
`the number of sub-frame activity classifications that
`could be utilized. Also, the hardware requirements for
`real time implementation were prohibitively complex,
`and hence the two pass approach is presently impracti-
`cal, particularly at picture broadcast rates.
`The pregenerated statistics modeling approach suf-
`fered from the fact that no pregenerated statistics ever
`exactly matched those of a real time picture being com-
`pressed. Additionally, several sets of pregenerated sta-
`tistics were often needed to accommodate multiple
`applications which required multiple passes to preselect
`the most nearly appropriate statistical set to be utilized
`for the particular picture.
`Inethe recursive coding with rate buffer feedback
`scheme, the sub-frame activity was determined, by the
`estimated variances of the transform coefficients, the
`variances being derived by a simple linear predicter.
`
`PMC Exhibit 213
`
`Apple v. PM
`|PR2016-0075
`
`Page 2
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 24
`
`

`
`3
`
`4,302,775
`
`One significant drawback in the recursive coding ap-
`proach was the elimination of high frequency AC coef-
`ficients, including those having significant amplitudes.
`Once the linear predicter produced a variance which
`needed a zero bit assignment, theencoding of that par-
`ticular picture subframe was terminated, and all subse-
`quent AC terms, including those with significant values,
`' were lost. Such losses unduly degraded high activity
`regions in the reconstituted pictures following inverse
`expansion and reconstruction of the compressed picture
`signal. Another drawback of the recursive coding
`scheme was that heretofore there has been no theoreti-
`cal analysis which justifies the assumed optimality of a
`linear predicter. One feature of recursive coding which
`has been advantageously incorporated into and signifi-
`cantly expanded in the present invention is that of the
`rate buffer technique.
`A major problem with image data compression has
`been the non-stationarity of image statistics. Early cod-
`ing schemes such as a single map zonal coder attempted
`to ignore the problem by assuming image statistics as a
`stationary process. The Markov model used by investi-
`gators was an example of the stationary statistical char-
`acterization of image data. Adaptive coding procedures
`have been proposed to take care of the non-stationary
`nature of the image processes and to improve the image
`quality. A well designed adaptive coder generally needs
`a priori non-stationary statistical information. This a
`priori information can either be estimated or computed
`on line, or predetermined a priorily. Neither case is
`desirable since it causes complications in hardware im-
`plementation on the former and causes statistical mis-
`matches on the latter. The undesirable feature can be
`eliminated by introducing the rate buffer concept for
`the channel rate equalization in accordance with the
`present invention.
`
`SOME OBJECTS OF THE PRESENT INVENTION
`
`A general object of the present invention is to pro-
`vide a digital video compression system which effec-
`tively combines scene adaptive coding with rate buffer
`feedback in methods and apparatus which overcome
`limitations and drawbacks of the prior art.
`Another object of the present invention is to provide
`a digital video compression system which operates ef-
`fectively at real time picture frame rates as high as those
`of the NTSC color broadcast standards.
`Another object of the present invention is to combine
`novel circuits and subsystems into a digital video com-
`pressor and expander which effectively compresses the
`bandwidth of a television picture in accordance with
`novel methods and techniques.
`Another object of the present invention is to provide
`a digital video compression system which effectively
`implements a two-dimensional discrete cosine transform
`of blocks of the picture.
`Another object of the present invention is to provide
`a digital video compression system which effectively
`implements a two—dimensional transform in which the
`DC term of each transformed picture block may always
`be transmitted in a fixednumber of bits.
`
`.
`
`l0
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`Another object of the present invention is to provide
`a digital video compression system which effectively
`implements a two-dimensional transform of blocks of
`the picture in which uniformly quantized AC coeffici-
`ents of each block fall into a single Huffman codeable
`statistical set.
`.
`
`65
`
`4
`Another object of the present invention is to provide
`a digital video compression system which effectively
`implements a two-dimensional transform of blocks of
`the picture in which low order uniformly quantized AC
`coefficients can be efficiently Huffman coded by the
`compressor and decoded by the expander in accordance
`with a predetermined Huffman code table, without
`transmitting the Huffman table or generating a new
`table for each block.
`V
`Another object of the present invention is to provide
`a digital video compression system which: implements a
`two-dimensional transform of blocks of the picture in
`which long strings of zero value high order AC coeffici-
`ents may be effectively’ run length encoded and in
`which high amplitude high order AC coefficients will
`be preserved.
`'
`‘
`Another object of the present invention is to provide
`a digital video compression system which implements a
`two-dimensional transform of blocks of the picture in
`which variance calculations, bit allocation matrix calcu-
`lations, and nonlinear block quantization are eliminated
`and not required in the compression process.
`Another object of the present invention isto provide
`a single pass digital video compression system which
`implements a two-dimensional transform of blocks of
`the picture which eliminates the requirement of prelimi-
`nary statistical matching or preprocessing to determine
`applicable statistics needed by prior two-pass picture
`compression techniques.
`-
`Another object of the present invention is to provide
`a digital video compression system which effectively
`utilizes rate buffer feedback control to provide global
`adaptivity of the system to the picture in real time.
`Another object of the present invention is to provide
`a digital video compression system which requires only
`one two-dimensional block of a fraction of the picture
`for input buffering, but which in practice will buffer at
`input an image strip of blocks of the same number of
`lines as defines the block size and will further provide
`some preformatting of the data.
`Yet another object of the present invention is to pro-
`vide a digital video compression system in which the
`output of the compression process yields a white noise
`error image‘ with no apparent structure.
`A further object of the present invention is to provide
`a digital video compression and expansion system in
`which the expander includes an instantaneous decoder
`which operates on each bit as it is received.
`.
`
`SUMMARY OF THE INVENTION
`
`An NTSC color broadcast compression and expan-
`sion system incorporating the principles of the present
`invention divides the color picture into luminance
`(monochrome) and I and Q chrominance components.
`The luminance signal is compressed and expanded with
`the scene adaptive coding with rate buffer feedback
`techniques of the present invention. The I and Q chro-
`minance components are given simple spatial low pass
`filtering followed by spatial subsampling with two-di-
`mensional
`interpolation at
`the system receiver. The
`audo is filtered and sampled at a predetermined rate,
`with each sample quantized to a predetermined bit reso-
`lution. The digitalized and compressed luminance (in-
`cluding picture synchronization pulses) chrominance
`and audio components are multiplexed together with bit
`stream synchronization codes and transmitted as a sin-
`gle composite bit stream.
`
`PMC Exhibit 213
`
`Apple v. PM
`IPR2016-0075
`
`Page 2
`
`PMC Exhibit 2133
`Apple v. PMC
`IPR2016-00755
`Page 25
`
`

`
`5
`The scene adaptive coding with rate buffer feedback
`compression system of the present invention receives
`each digitalized video luminance frame divided into a
`predetermined matrix of subframes or blocks. The com-
`pressor performs a spatial domain to transform domain
`transformation in both horizontal and vertical dimen-
`sions of the picture elements of each subframe to pro-
`vide transform coefficients corresponding to each sub-
`frame. The compressor normalizes the coefficients by a
`normalization factor having a predetermined compres-
`sion ratio component and an adaptive rate buffer capac-
`ity control feedback component to provide~compres-
`sion to the transform coefficients and to provide nor-
`malized transform coefficients compatible with a prede-
`termined data coding scheme. The coefficients are en-
`coded in accordance with, eg., Huffman codes and zero
`coefficient run length codes, and then stored in a first
`rate buffer memory asynchronously at a high data trans-
`fer rate from which they are put out at a slower, syn-
`chronous bit stream rate capable of passing through a
`limited bandwidth medium. The compressor adaptively
`determines the rate buffer capacity control feedback
`component in relation to the instantaneous data content
`of the rate buffer memory in relation to its capacity to
`control at normalization the absolute quantity of data
`resulting from that process so that the buffer memory is
`never completely emptied and never completely filled.
`In expansion, the system stores the coded coefficients
`in a second, decoder rate buffer memory at the slow
`synchronous data transfer rate through the limited me-
`dium. The coefficients are then put out from the second
`memory asynchronously at a high data transfer rate.
`The coefficients are decoded in accordance with an
`inverse of the predetermined coding scheme, and then
`the decoded coefficients are inversely normalized by
`operation of an inverse normalization factor with a
`predetermined expansion ratio coefficient and an adapt-
`ive decoder rate buffer capacity control feedforward
`component to provide expansion of the transform coef-
`ficients.
`
`l0
`
`I5
`
`20
`
`25
`
`30
`
`35
`
`The scene adaptive coded picture expansion system
`adaptively determines the rate buffer capacity control
`feedforward component in relation to the instantaneous
`data content of its rate buffer memory in further relation
`to its capacity. This is done to control at an inverse
`normalization step the absolute quantity of data result-
`ing therefrom and thus the rate which the coded coeffi-
`cients are put out advantageously from the expander’s
`rate buffer memory so that it, too, is never completely
`emptied and never completely filled. A high speed de-
`coder decodes Huffman and run-length codes in real
`time in accordance with a “tree” state functional
`scheme which progressively decides upon a new state
`on the basis of the old state and the next bit received.
`The scene adaptive expansion system then performs the
`inverse of the predetermined transformation‘ of the ex-
`panded transforrn coefficients to provide reconstituted
`luminance picture elements of the subframes.
`The subframes are then assembled into the predeter-
`mined matrix to reconstruct the digitalized luminance
`picture frame which closely approximates the corre-‘
`sponding original frame. The