Google Inc. v. Compression Labs Inc et al

Filing 14

Google Inc. v. Compression Labs Inc et al

Doc. 14 Att. 5

Case 5:04-cv-03934-JF

Document 14-6

Filed 11/17/2004

Page 1 of 20

EXHIBIT E

Dockets.Justia.com

----Case 5:04-cv-03934-JF Document 14-6 Filed 11/17/2004 Page 2 of 20
United States Patent

(19)

(11)

Patent Number:

Chen et aI.
(54) CODING SYSfEM FOR REDUCING REDUNDANCY
(75) Inventors: Wen-hsiung

(45)

Date of Patent:

698 672 Oct. 6, 1987

Primary Examiner-Howard
Attorney, Agent, or

Chen, Sunnyvale; Daaiel J. Klenke, Milpitas, both of Calif.
Labs, IDeo, San Jose,
Calif.

(73) Assignee: Compression

The present invention rel~tes to methods and apparatus for processing signals to remove redundant information
thereby making tbe signals more suitable for transfef through 8 limited-bandwidth medium. The present invention specifical1y relates to methods and apparatus
useful in video compression systems. Typically, the
. input signals and the previous input signals using

(57)
Lovejoy.

W. Britton FiI77l-Fliesler, Dubb, Meyer &

ABSTRAcr

(21) Appl. No. : '23,63()

(22) Filed: Oct. 27, 1986 (51) Into 0.4 ...................... HD4N 7/133; H04N 7/137 (52) U.s. CL .................................... 358/136; 358/261: 358/262; 375/27 (58) Field of Search ............... 358/136, 135, 133, 261,
358/262; 375/27, 31, 33

(56)

References Cited

S. PATENT DOCUMENTS
302.7.75 11/1981 Widergren .......................... 358/136
476, 495 10/1984 Fujisawa ............................. 358/262 520 490 5/1985' Wei _.........-.................... ;... 375/27 558, 370 1211985 Mitchell.............................. 358/262 633, 325 1211986 .Usubuchi """""""""""""" 358/133

processed and compared with one or more thresholds for determining one of several modes of operation. After processing in some mode, the processed signals are in the form of digital numbers and these digital numbers are coded, using ordered redundancy coding, and transmitted to a receiver.
46 Claims, 4 Drawing Figures

system determines differences between the current meansquare difference signals. These mean- square signals are

- -- ~
Case 5:04-cv-03934-JF

--

- _ -~_
Filed 11/17/2004 Page 3 of 20

--

Document 14-6

U. S. Patent Oct

6, J 987

Sheet 1 of3

698 672

24 :--

15 52
FORWARD

f/2
I 45

PROCESSOR

CODER

aUF

.I
" REVERSE PROCESSOR

I'
56
FORWARD

0;;-

I-"R
BUF

117

DECODER

68

PROCESSO~

I.
REVERSE

PROCESSOR

57

--J

FIG.

--:---.;...

--

--

r,n

Case 5:04-cv-03934-JF

sa.
NORM.
QUANT.

UNIT

UNIT
:..J

f.t
0'1

r-I-IMOTrON

Document 14-6

DETECT a COMP.

INVERSE I 16----' NORM.

-...J

29

tIl

Filed 11/17/2004

PREDICT
DELA Y

(MEMORY)

20
-J
FIG.

Page 4 of 20

L..

-2

Case 5:04-cv-03934-JF

Document 14-6

Filed 11/17/2004

Page 5 of 20

U. S. Patent

Oct 6,

1987.

Sheet 3

of3
. CLK

698 672

67 66 65

129

. RUNLENGTH TABLE

130
CLK
101

CLK

FIG.
104
AMP TAB LE

ClK

ClK5

1/8

114 .
RIR
112

CTRl

110

FI G.-

4

s
Case 5:04-cv-03934-JF Document 14-6
698, 672
CODING SYSTEM FOR REDUCING REDUNDANCY

S
Filed 11/17/2004 Page 6 of 20

adaptively controls the rate at which data is generated so that the buffer is never completely emptied and never.
completely fiJled.

CROSS- REFERENCE TO RELATED

In the system receiver, the transmitted data is stored 5 in a receiver buffer at tbe synchronous data rate of the
limited-bandwidth medium. The data is then output from the receiver buffer asynchronously and is decoded

APPLICATION
. Title: A COMBINED INTRAFRAME AND INTER.

transnritter. The decoded data is inversely normaliZed (now abandoned) Ser. No.: 479,766 Filed: 83103/28 10 and inversely transformed to provi~e a representation Inventors: Wen-hsiung Chen, James Parker Elliott, of the original video image. Robert Edwin George Newell, Ralph Emerson NichThe U.S. Pat. No. 4,302,775 patents reduces redunols, A1bert Edwards Rackett dancy by emp10ying intraframe coding techniques uti. BACKGROUND OF THE INVENTION lizing intraframe comparisons of cosine transform coef15 ficients. While the patent provides significant improveThe present invention relates to methods and apparatus for. processing signals to remove redundant informa- ment over other techniques, there is a need for even
tion thereby making the signals more suitable for trans-

FRAME TRANSFORM CODING SYSTEM

in accordance with an inverse of the encoding in the

greater compression. .

~er thr~ugb a !imited- bandwidth medium. The present In addition to intraframe coding tecbniques, interInventi~n ~peclfically rel~tes to methods and apparatus frame coding techniques have been used to reduce the
useful In ':Ideo compre~lon

Many ~Ignal processIng techniques useful m ~~eo example, in the above-identified application. Typically, comp~CSSIC?n systems are kno~ For ex~mple. dlp!ta1 each video frame is held in memory at both the trans~codmg I~ often employed m processmg tele~ls!on mitter and the receiver and only frame-to-frame signals w~lch w:e. to be transferred over tr :msmlsslon changes are transnritted over the communication link. to ch~nnels smce .digltal data streams are more Immune2S In contrast to intraframe coding schemes in which the noISe degradatio~. ' quality of coded images is dependent upon the amount . In order to digJtal~y encode a teleV1Slon S1!;nal, a of detail in each single image frame, the quaJity of the slgn~cant number of bits, 4 or more, may be reqmred to coded image in interframecoding is dependent upon the provide for an acceptable range of gray scale for eacb of differen es fro tame 0 am:, r ~c;t: Cram diffier0the hundreds of thousands of separate picture elements ' 30 cesare 0 en re:erred to ~ c ft m (pixels) which form an image. Consequently, data rates . Interframe co~mg techmques .are br~ly c~JCd for unprocessed digitalized te1evision signals typicaDy mto two catego~es, na~ely, spatial do~n codmg and require a bandwidth greater tban 40 megabits per sec. . dom~1n codIng. In r~-ume 1I!terframe spa. ond. If the communications link is an earth satellite, an t~form c;odmg syste~ spatial domam da';8 can be tlal-domatn' unprocessed video signal typically occupies nearly the 35 to obtain and store frame difference ~resbo!d entire bandwidth of the satellite, with very few chan- signals ~ a transnutt~r buffer. The ~esbold value neb, if any, Ieft over for other uses. A Tl communica- be adaptively determmed as a functl . of the ~SDI1ttion channel is typical and has only a 1.5 megabit per ter buffer fuJiness. l~ order to ehnunate the . IDlBge . second bandwidth. A practical yet effective way to both spatial and temporal subsampling bas reduce the bandwidth of digitalized television signals is 40 breakdown, been needed so that fewer channels are required for transmisThe abo~e-Identified U. S. patent application entitled

syste~ .

20 rate required for video transmission as descn"bed, for

en

fi t fr motion.

pro~

pro~.

of transmitted signals is maintained even when reduced "A Combmed Intraframe and lnterframe Transform and interframe yst~m:' employs bandwidth transmission . lmagesarc repre4S vanable prediction transform coding. S. Pat. No. 4,302,775, assigned to the same assignee

ion over a communications path and so that the quality

is employed.

intr~e

as tbe present invention, describes a scene adaptive sented oy sequential frames of two-dimensional arrays
coding technique which eliminates redundant informa.

of digital signals. The digital signals are transformed to

Predicted tionand thereby reduces the bandwidth. form transform coefficients for each frame.of variable transform coefficients are formed using sets

The patent describes a single-pass digital video comcoefficients pression system which implements a two-dimensional 50 prediction factors. The predicted transform for each frame are compar,ed with corresponding actual . cosine transform with intraframe block-to-block comtransform coefficients for the frame to form transform parisODS of transform coefficients without need for preliminary statistical matching or preprocessing. coefficient difference signals. The difference signals arc processed to contr01. their range of values. The proEach frame of the video image is divided into a predetermined matrix of spatial subframes or blocks.. The 55 cessed difference signals are statistica11y coded such

system performs a spatial domain to transform domain that
transformation of the picture elements of each block to

the more frequently occurring values are repre-

sented by shorter code lengths and tbe less frequently
values are

provide transform coefficients for each block, The sys. occurring
tem adaptive1y normalizes the transform coefficients so

represented by longer code

lengths. The coded signals are stored in a butTer mem-

that the system generates data at a rate determined 60 ory for transmission. The coded signals' in the butTer adaptively as a function of the fullness of a transmitter memory are transnritted, over a limited.bandwidth me.
buffer. The transform coefficient data tbus produced is dium, to the receiver along witb processing informa-

encoded in accordance With amplitude Huffman codes lion, The processing information includes codes identi- . and zero-c0ef6cient runlength. Huffman codes which fying the set of variable prediction factors utilized in the are stored asynchronously in the transmitter buffer. The 65 transnritter. The same set of variable prediction factors encoded data is output from the buffer at a synchronous is utilized in the receiver to reconstruct predicted trans. rate for transmission through a limited-bandwidth me- form coefficients which in tutn are used to reconstruct. dium. The system determines the buffer fullness and representations of the original images in the transMitter.

Case 5:04-cv-03934-JF

Document 14-6

Filed 11/17/2004

Page 7 of 20

698,672
The extension of the Scene Adaptive Coding of U. Pat. No. 4 302,775 from intraframe coding to interframe coding has proven very significant in terms of improving image quality and reducing. bandwidth. These im-

more thresholds for determining one of several modes of operation. Mter processing in some mode, the processed signals are in the form of digital numbers and these digital numbers are coded, using ordered redunAfter transmission of the coded signals, the received

provements, bowever, have created a need for im- 5 dancy coding, and transmitted to Ii. receiver.

proved coding systems for reducing redundancy and there continues to be a need for improved signal processing methods and apparatus for data . compression
systems.

signals are decoded and processed in reverse of the' particular one of the modes by which the signals were.
p o essed in 10rIncaccordance the transmitter. the present with the above summary,

SUMMARY OF THE INVENTION

The present

invention achieves the objective of providing an improved signal processor for reducing redundancy using ordered redundancy coding.

invention is a signal processor and

different modes.

method for efficiently processing signals using ordered redundancy (OR) coding and anyone of a number of

The signals to be coded are typically multiple values where the multivalued digital numbers, X(k) are typi-

The foregoing and other objects, features and advantages of the invention will be apparent from the following detailed description in conjunction with the drawings.

BRIEF DESCRIPTION OF THE DRAWINGS forming digital numbers and hence t~e ~robable- fre- 20 FIG. 1 depicts a block dia am ora transmitter and quency of occurrence of some values IS different than re ' r ~r other values. In one example ?f digital numbers ';;~ 2 de ~~~ further details of the transmitter f he ot
in any order. Frequently, some values are repeated in

cally the integers 0, I, 2, 3, 4, . . . , and so on arranged

, the

syst
P~

highest frequency of occurrence IS the value 0, the next

highest frequency of occurrence is the value I and the

other values greater than 1 (namely 2, 3, 4,

J~:rr:ed' FiG. ts furtber de iJs f e co er us m the th and so on) G. 2FI 25 ~ans~tter. occur least frequently. With such order to the FIG. . depicts further details of the decoder used m 5,

FIG 1 s t p

fre-

tal 0

most efficient.
the highest most frequently occurring values (O'

quency of occurrence of values to be coded, the orthe receiver. dered redundancy coding of the present invention is

DETAILED DESCRIPTION

Using ordered redundancy coding, the system codes 30 Overall System-FIG:

. a trans~l1tter usual example) using runlength coding. In the most In. FI~. 1, a block dJ8~am ofpresent mventl:rod IS WIth tbe preferable example, the runlength encoding is of two receIVer I~ .ac~rdanceto be proces~ed are mp~t ono? shown. DIgJta1 ~lgnalS Imes types, R and R'. The first type, R, is utilized when a S1gnals on Imes 5 are runlength of consecutive zeros (O's) is followed by the 35 5 to the u:mslllltter 2. The mput next most frequently occurring value (1 in the usual pro~sed m one of a number ?fditT~ntmodes so as

s in the

1

case) and the other type, R',

is utilized when the run- efficlent!y compress the ~ar:a mput Slgn~S to form prois followed by some cessed
S!gnals for transousslon to a

length of consecutive zeros (O's)

~Ivero The pro-

(usually greater than I such as 2, 3, and so on). When- 40 transmitter 2 ~nd are ~smitted to the receiver 3. ever the second type, R', of runJength coding is em- The transoutter 2 mcludes a forward processor 52 ployed. the runJength code is typically followed by air ~d a ~eedback (~everse) process~r 51. Typically, the
amplitude (2, 3, . . . ) of the following other value. ented in the space domain as frames in accordance with Whenever the fltSt type, R, of runlength coding is em- 45 well known techniques. The forward processor 52 typiployed, no coding of the second value (usuaily 1) is cally processes the spatial domain input signals to form required because an amplitude of I is implied simply by processed signals whicb typically are transform domain the use of the first type, R, of runlength coding. signals arraaged in blocks of transform domain coefficiThe ordered redundancy coding of the present inven- ents. The forward processor 52 processes the current don is typically utilized in a system that processes input 50 input signals from t)Je most current frame. signals, such as spatial domain image signals occurring The reverse processor 51 typically inverse processes . in successive frames, to form processed signals for each signals from transform domain to spatial domain. Proframe. Any number of different processing modes are cessor 51 stores signals representing tbe previous frame of data aDd also receives the current input signals so as possible. The processed signals are in the form plurality of multivalued digital numbers, X(k), typically 55 to enable a comparison to be made between the previone number, X(k), for each frame. ous inverse processed input signals and the current In one particular embodiment, the processing modes input signals. When the current input signals have been
amplitude code which explicitly encodes the actual mput signals on Imes 5 represent rmagesand are pres-

other value, one of the least frequently occurring values cessed signals are coded and output on Imes 45 from the

of a

include two replenishment compensation and one without), two

modes (one with motion transformed from the spatial domain to the transform DPcM modes domain, the reverse processor performs an inverse

(one with motion compensation and one without) arid 60 transform to convert the transform domain signals back one intraframe mode. The decision as to which mode to to spatial domain signals and stores tbose spatial domain select is made based upon an analysis of the frame-to- signals for comparison with the current input spatial
frame differences (motion) between the current input

domain signals.

signals and the previous input signals. The reverse processor 51 determines cbanges beTypically, the system determines differences between 65 tween the current signals and tbe previous signals. Typ..

ically, these differences are determined using meandb. hereinafter defined. These using mean-square difference signals, These mean- square signals, do and square signals are processed and compared witb one or mean-square signals are processed and compared with
the current input signals and the previous input signals

~~

Case 5:04-cv-03934-JF

Document 14-6

Filed 11/17/2004

Page 8 of 20

698 672
one or more thresholds for determining" one of several compared to the reconstructed spatial image on lines 6 modes of operation for the system of FIG. 1. of the previous frame on a block-by-block basis through Any number of different modes are possible. In one a motion detector 7. The reconstructed spatial image is

particular embodiment, two replenishment modes (one obtained from the memory 18 of the feedback DPcM

fthe motion detector 7 10 determines that there is little1difference between the and the processor 51, the processed signals are mput to
the Input data. After the processing br the

The feedback loop' includes the inverse normalizer mtraframe mode ~re employed. The 16, inverse transformer 17, the sum unit 20, the delay decision ~ to which mode to sel~t IS made base~ upon (memory) 18, the prediction unit 19, and the motion an~alyslsoftheframe-to-frame
~~~ut) and one.

D~M modes

with motion compe~sation . and one wi~out), two 5 loop'. (on~ With motion compensation and one

dlfferences(motion)of detector and compensator 7.

pr~r52

coding, signals with a statistically higher frequency of 15

The coder 14 encodes the processed signals using other hand, If enou~h difference I S detecu:d, the block m statistical frequency coding. With satistical frequency the current fr~e IS compared to the n ';lghborh~ of
the corresponding reconstructed block m tbe preVIous
pose.o~ increasing the sys!e

the coder 14.

bl ks ..epIems m~n m d'" oc , ' ~ o~

IS seI eC ted

.e

occurrence are encoded with a shorter code length than

frame to find tbe best matcb of the block. For the pur-

',D performance a sub-pixel match IS employed. If the dJtTerCl!ce between the curdered redundancy (OR) coding technique. In the or- rent block and its best matched block does not result in dered redundancy coding, the processed signals to be 20 a reasonable improvement over the difference between coded have multiple values. For example, values are the current block and its original counterpart, a motion typically 0, 1, 2, 3, 4, . - , , and so on. Typically, the compensation is not justified. In this case, a " DPcM statistical frequencies of the values to be coded have an mode " with variable predictions is selected to handle order. Particularly, that order is based upon the proba- the block difference. On the other hand, if the differble frequency of occurrence of tbe different values. The 25 ence between the current block and its best matched
rence. Additionally, the coder 14 utilizes a novel orbighest frequency of occurrence is typically the value 0,

signals with a statistically lower frequency of occur

the next most frequently occurring value is 1 and the

other values greater than I (2, 3, 4

5,

some other value of the least frequently occurring type. 40 The motion d~!ecli?n serves two purposes, It C?m(usual1y greater than I such as 2, 3, and so on).

least frequently. With such order to tbe signals to be between the current block and its best matcbed block is ~ded,. th~ ordered r~undancy coding of the present 30 screened to determine if the block belongs to a " 1Dotion mve ~tion IS most, compensated replenishment" block or a " motion com. UsIng OR codIng, tbe coder ~4 of FIG. 1 ~d pensated DPCM" block. The forward loop of the highest most freq~ently occumng ,,:alues (0 s m the DPCM system encodes the ;' DPcM" or "motion comusual example) usmg runlength codIng. . In ~e most pensated preferable example, the runlength ~n~mg IS of two 35 tical fr DPCM" data in the transform domain. StatiSuen codin is em ed to im rove the effltypes, R and R' . The first type, R, IS utIlIzed when the operrunlength ofO's is followed by the next most frequently clenc y. The f~back I~p of the D~cM syst occurring value (1 in the usual case) and the other type, ated m. the spati~ domam WIth van ~ble predictions. Compensation , is employed when the runlength ofo' s is followed by Motion I?etection

efficient

and so on) occur compensation is initiated. In this case, the difference

block is reasonably smaller than the difference between the current block and its original counterpart, a motion

es the

ever the R' type of runlength coding is employed, the borhood pIXels of the corrCSJJ':'ndin~ block m the prevl- runleDgth code is typically followed by an amplitude ous frame , t? find the sub-pixel displacement of code which explicitly encodes the actual amplitude of block that gives the best match. It also tracks the dlsthe other value, Whenever the first type, R, of run- 45 placement vectors and the degree of differences during length coding is employed, no coding of the second the matching process for a subsequent modification of value (usually I) is required because au amplitude of 1 is the DPCM frame memory and controlling of the preimplied simply by the use of the first type, R, of run. dictor parameters in the feedback DPCM loop. Three

When. pares the ~Iock pIXels m the pres~nt frame to the nel~-

length coding.
After the ordered redundancy coding in coder 14,

basic types of modes (replenishment modes, intraframe

data is transferred to the transmitter buffer 15. The motion detection. A decision process among the modes . buffer 15 provides a feedback signal on line 25 to con. is employed. The decision process relies in part on a trol the forward processor 52 data rate. determination as to whether motion-compensation or In FIG. 1, the data from line 45 is input on line 68 noD-Motion-compensation is to be employed. Motion after transmission over some conventional transmission 55 compensation is determined using the mean-square du-

SO

mode, and DPcM modeS)

are determined from the

buffer 53 stores the received data. A decoder 54 de- The mean-square difference do. is formed as follows:
codes the received data. Thereafter, the decoded data is

medium to the receiver 3 :

In the receiver 3, a receiver ference, do. aDd the mean square error, db-

processed in reverse of the particular one of the modes by which the data was processed in the transmitter 2. 60 The reconstituted data appears on output line 6'.

Transmitter-

FIG. .2 is a block diagram of a transmitter for. motion compensated combined interframe and intraframe codwhere f(j,k) are spatial pixe1s (on lines 5 of FIG. 2) of ing system of FIG. 1. Motion compeDsation is incorpo- 65 the curreDt frame and fG,k) are the corresponding pixels rated into a combined interframe and intraframe coding (on line 6 of FIG. 2) of tbe reconstructed previous system using the spatial pixels in the inverse loop 9. In frame. N is the transform block size. operation, the original spatial image on input lines 5 is The mean-square error, db. is formed as follows;

FIG. 2

l !/Iik) do = (1/)\12) 1=0

k=D

ftJ,k)j2

Eq. (I)

Case 5:04-cv-03934-JF

Document 14-6

Filed 11/17/2004

Page 9 of 20

698,672
if (do-db).c:::TMand do.c:::TolI,

select non-motion-com-

db

= (I/N") N i I Ni
1=0

pensated DPcM mode.
I k) iu + A).

+ Ak)J2 Eq. (2) If a non-motion-compensated

k=O

w~ere f(j,k)are the block plxelsm the ~rese ?t ramean d 5 for subsequent encoding. Again, the mode identification fU+Aj, k+Ak) are the best matched p~xels m the pre';'!- is HulTman coded. Typically, a two-bit code (10) used ously reconstructed frame where Aj, Ak are the dls- for the non-motion-compensated DPcM mode and placemen! (vector) for the best match. appears on line 66 in FIG. 2Replemsh 10 At the receiver, the DPCM data are inverse1y transThe replemshm~nt modes are either motJo~~ompen- formed and added onto the block pixels from the recousated or non-motlon-c ?mpensated. The dec~slon pro- structed previous frame to form the present block pixcess selects compensation or non-compensatlon based els.

fj

DPCM mode is se-

lected, the predictor in the feedback loop is enabled and
the difference is sent to the discrete cosine transformer

~ent Modes .

For the motion-compeusated DPcM mode, the difdb. between the current block pixels and the spatial pixels of a block and the reconstructed spatial best matched block pixels is compared to a predeterpixels of the corresponding block in the previous frame. mined. motion-compensated replenisbment thresho1d,
upon motion detection. The motion detection unit 7 of

FIG. 2 determines the difference between the incoming 15

ference,

If the motion detection process determines that there is

To/R.

If

db

is larger than the threshold, a motion-com-

little frame-to-frame difference between corresponding pensated DPcM mode is selected to handle the pixel
blocks, a non-motion-compensated replenishment mode 20 differences. is selected and a code word is sent on 1ine 21 from unit The decision processs is given as follows:

7 of FIG. 2 to the encoder 14 to identify the mode. If(do-db):;:'

TMand db:;:' To/R,

select motion-compen-

blocks, typiunder some circumstances, a motion-compensated re- 25 cally a three-bit code (110) is used together with the plenishment mode is selected. The detection process displaC?Cment ~ector reprc:senting the best match of the typically uses the mean-square difference, do, and com- block along With ~e m~tion compensated DPcM data (transform coefficient dllTerences between the present pares it to a predetermined non-motion-compensated TR. This process. is written as block and the best matched block from the reconreplenishment threshold, 30 structed prc:vious f!ame). The mode ID ~d vector receIVer, these

If the motion detection process determines that the sated DPcM mode. frame- to-frame block difference is great enough then, For the motion compensated- DpcM

follows:
if (do-db).c:::TM and do.c:::TR, select If (do-db):;:' db.c:::TDIR, 2 IS used if the non-

The detection process compares tbe mean square the c:ompensated block pIXels from pIXels. redetermined motion-compensated prevIous frame to form the present block error, b. with a Intraframe Mode. as 0 lows. TDIR, ~lemsbment threshold, select motlon-compeg- The intraframe mode is selected when neither the

and added onto pensated replenishment mode. DPcM data are mverse !,ansformedthe re~nstructed .

uon-motion-com- appear on line 6~ m FIG. 2. At the

35

bit ~de (0), on line 21 of .FIG.

~odes are typlca1!y Huffman coded; TYPlc~ly, a one- 40 compared with the predetermined DPCM threshold,
molion.compe~ted replemshm~nt mode

motion-compensated mode nor the .v: and sat~ rc:plem~hment mode. justified. The difference, do. between the current block The Identlfi~ation code words for the r~lemshment pixels and the reconstructed previous block pixels is

DPcM mode is

frequently sta~stlcally. Once this code wor~ IS I~enti- If the intraframe mode is selected; the predictor is
fled at the receIVer, the reconstructed block piXelS

a~ mo~t If
TD/I.

(do-db).c:::TMand

The decision process is as follows: selectintraframe mode. do:;:.TolI,

In t~e disabled and the current block pixels are sent to the
code (1110) appearing on line 66 in FIG. 2 is used to identify the "intraframe mode . The intraframe data in

previou~ frame are repeated to form the present block In 45

the receiVer. .

transformer with unit 11 of FIG. 2. Typically, a four-bit
the receiver are inverse1y transformed to form the pres-

~or tbe motlo~ compensat~ replen2shment .block, typically a four-bit code (1111) IS used, aJong WIth the

displacemen! vecl~1f representing the ~st

match, and ent block pixels.

appears on Ime 67 m FIG. 2. At t,he receiver, the vector

due to the necessity of encoding tbe vector information sated or motion-compensated. Selection of the compen, as system overhead, the range and resolution of the sation or non-compensation DPcM modes is dependant searching process is somewhat limited.
are either non-motion-compenS5

sDrucMed block. t P ct Modes
The DPcM modes
reconstructed previous frame. The difference, db, smaller than the motion threshold, T M,

The performance of the motion compensated system structed previous frame to form the presently recon- is dependent upon the range and resolution of the matching process. The larger the range and the finer the
uses the compensated block pixels from the recon-

50 Compensation Range and Resolution

resolution, the better the system performs. However,

in part on motion detection. The motion detection Searching Algorithm
searches for the best matched block pixels from the . The

search for the best matched position is a very

be- 60 time consuming process. As one example, a simple bitween the present block pixels and the best matched nary search algorithm for a maximum range of 1.75 can this difference is be employed. Using such an algorithm, the nine wholeblock pixels is then computed.

no motion com- pixel positions. centered around the position of the pres-

pensation is justified due to the necessity of sending the ent block are first examined to find the best match. displacement vector as coding overhead. In this case, 65 Next, the eight haJf-pixe1 neighborboo~ positi?~ centhe difference, do. is compared to a DPcM threshold, . tered around the best matched whole- pIXel poSItion are examined. The process continues until the best matched to determine if the block belongs to a TOil,
mOde. The decision process is given as follows: quarter-pixel

DPcM

position is located. The horizontaJ and

p(j,

= \,

-\

Case 5:04-cv-03934-JF

Document 14-6

Filed 11/17/2004

Page 10 of 20

698 672
vertical addresses of this location are then recorded as a vector and encoded accordingly. The number of steps required for a binary searc;:h is many times lower than that of a brute force search. Subpixe1 translation is done by performing bilinear 5 interpolation taking weighted averages ofthe four nearest values at integral pixel positions

-continued
=((2j

+ 1)""'I2NJ co.((2k + 1)...12NJ

foru,r=O

I,...,

C(w) = 1/(21) for for

=I

=0
2. .. ..

surrounding the

pixel positions. As an example, a displacement of 1.25

lows:
horizontally, and 0.75
JU+I. 25.k~ 75)::"JIU+I.k)+"'2IU+J. JU+l.k)+w4f(f+2,k- I)
Referring to FIG. 2, the

subpixellocation. The weighting factors that are used where
are linear functions. of the horizontal and vertical dis-

where w=u or v
O,k)

and (u,v) represent indices in the horizontal

and vertical directions for the pixel difference and cootance of the fractional displacement from the integral 10 ficient difference blocks, respectively, and where C(w)
vertically is performed as fol-

075 '~. 5. W2 075 02 (0. 25), and w4=(0.25) (0.75)

were WI

DPCM

, 320 Loop
Differential Pulse Code

represents C(u) or C(v). The cosine transform restructures the spatial domain data into the coefficient domain such that it wi)! be beneficial to the subsequent coding and redundancy removal processes. I)+w). Normalization Eq. (3) The coefficient differences, En (u,v), are scaled acording to a feedback normalization factor, ~. on lines w=

15

25, from tbe output rate buffer 15 accordmg to the .
relation
1 (u,r)=E,,(u. r)ID
Eq. (6)

Modulated (DPCM) loop consists of a cosine transform uni! 11, a normal~ti~n unit. 12, a q~tization unit

~ation fr~m the preVIous frame.

an mverse normalization Unit 16, an mverse .transform differences such that a desired number of code bits can unit 17, a delay memory 18, and a prediction unit 1'. In 25 be used during the coding process. operation, .au input pixe1 bl~k on lines 5 from ~e pr~ent ~rame IS fllSt subt;acted m subt~actor 10 bY The quantization process in unit 13 is any conven-

13, The scaling process adjusts the range of the coefficient

lts esti-

Quantization

on Ime23 on a plxe!-by-

pIXel b8Sls to generate
ences are then cos!De

block differ~nces. These di!'f'er-

tionallinear or non- linear

quantization. The quantiza-

~sformed m ?,ansform urut 11 .30 leave a limited number . of significant other differences to form the coefficient differences ?n lines to be coded. The quantized coefficient differences on ficient differences are next scaled ID normalizer Unit 12 lines 28 are represented as follows: according to a feedback parameter. on lines 25 from the

tion process wiU set some of the differences to zeros and

~. The~f-

output rate buffer 15. The scaled coefficient difference
on lines 26 are then quantiZed in unit 13 and fed into 35

l,,(u,r)=o!1,,(u. r))

Eq. (7)

differences on lines 27. These differences are then added 40 speaking, setting the minimum value of D to one in adder 20 to the motion compensated estimation on sufficient for a low rate compression applications in-

both the coder unit 14 and the inverse DPCM loop'. In where Q( ) is a quantization function. the inverse DPCM loop " tbe quantized and scaled data It should be noted that a lower bound is determined are inversely normalized in unit 16 and inverse1y trans- for the normalization factor in order to introduce pleanfonned in unit 17, to form the quantized coefficient ingful coefficient differences to the coder. Generally

lines 3 to form the reconstructed

in osine Transform Cthe output block.
from the present frame on 1ines
The coefficient differences between the input
from the previously reconstructed frame on lines 3 are

sated block from the memory 18, multiplies it by a pre. 45 signal-to-quantization-noise ratio of 40. 86 db which is diction weighting factor, and is ready for the next frame re1ative1y insignificant for low rate applications. . of operation. At the receiver, the received data follows Inverse Normalization
tbe inverse DPCM loop to reconstruct the spatial pixels

pixel blOCk in the volving transform blocks of 16 by 16 pixe1s. In this case frame memory 18. After a single-frame delay, in mem- the worst mean square quantization error is less than ory 18, the motion detector 7 uses the motion compen- 0. 083. This mean square error corresponds to a peak

Sand the estimations
E,,(u. o)= l,,(u,o)D

The process of inverse normalization in unit 16 produces the quantized coefficient differences on lines 2' in 50 the inverse DPCM loop ,. This process is represented pixels as follows:
Eq. (8)

formed by the difference circuit 10 on lines 23 and are

expressed as follows:
enfj.k)=/n(j.k)- p(j.k'ilN- IU+A).k+Ak)

Eq. (4)

where 4j and 4k represent the vector values for the best

Inverse Cosine Transform The inverse cosine transform process in unit 17 in the inverse DPCM loop' converts the quantized coeffici. ent differences on ' lines 29 back to the spatial domain
pixe1 differences on lines 27. This process is defined as

match determined by the motion detector and wbere
estimation. These diffe.-ences within a N X N block are cosine transformed in trans. former 11 to form tJie coemcientdifferences on lines 24.
k)

represents the

follows:
(j.k)

The cosine transform is defined as follows:
E,,(u. o) = 41C(u)C(0)JIJV2 I
)::0

= u=O I N- C(u)C(o)E.(u. I 0::0
I)U1l'l/2N

Eq. (9)

INk=O

(j.k)

Eq. (5)

co5((2) fOl"j. k.

cosll2k + 1)"'112N

= 0, I, .. . ,

Frame Memory

(j,

-!.-

Case 5:04-cv-03934-JF

Document 14-6

Filed 11/17/2004

Page 11 of 20

698,672
The frame memory 18 contains the reconstructed input pixels in the inverse DPCM loop. The quantized pixel differences from the inverse cosine transformer on lines 27 and the motion compensated estimations from
tbe previously reconstructed frame on lines 3 are added 5

TABLE 2-continued

..MQQE.

VECTOR DPCM

variable

-.-!ill!!...

DPCM or Molion Compensated Block'

together in adder 20 to form the reconstructed pixels,
k), wbich replace the block pixels in the memory 18. This process is represented as follows:
1"Q. k)="l"Q. k)+pV. ki!n- IU+4tk+4k)

DPCM Encoding
The Scene Adaptive Coding (SAC) is very efficient
coefficients.

' Eq. (10) loin terms of coding the intraframe transfonn

Prediction The prediction process in unit l' finds an estimation of a datum from its surrounding data. By way of exam-

When this scheme is applied to a coding system involving intraframe, interframe and motion compensation,

the coding efficiency is somewhat reduced due to the
removal of redundancies. One observation that can be made in the motion compensated coefficient differences (non-zero after normalization and quantization) and, to

structure of coeffiCient differences or motion compenple for a simple predictor that uses the previous frame as 15 sated coefficient differences caused by the additional

a base for the estimation, the estimated value is termed as the correlation coefficient, p(j,k), given as follows:
pV. k)=E(tn (j.k)cn- IU+4j, k+4k)j/u2U.

Eq. (II) a certain degree, the interframe coefficient differences

sents the variance of en k). The corre1ation coefficient, of them having an absolute value of one. Also, within termed as leak factor, ranges from 0 to I depending on these differences of ones, a significant portion of tbem the frame-ta-frame pixel differences. The value is very are isolated (surrounded by. zero-valued coefficients) close to 1 for a limited motion sequence. However, 2S' along the path of a scanning. It is wasteful to use one during a scene cut or a rapid zooming sequence, the amplitude codeword to code each of these isolated ones value is way below the value of 1. Because different in addition to using one runlength code word to identify leak factors have to be identified in the encoding of the their address (RunJength alone should be enougb). DPCM process, it represents a significant overhead for Ordered Redundancy Coding the low rate system if too many values are to be identi- 30 A new Ordered Redundancy (OR) coding algorithm fled. In one embodiment, only two leak factor '(a1ues is speciflcal1y designed to code multi-valued digital
are used for the five-mode motion detection system: I for the non-motion-compensated DPCM and motion

where E represents expected value and u2(j,k)

repre- are sparsely distributed with an overwhelming majority

20 (non-zero differences) is that most of these differences

eal example the encoding process in unit 14 for the FlG. In general, a K-valued digital number, X(k), is formed 2 system is performed on a frame by frame bases. The by a series of K values, x(k), as follows:
coded bit stream includes sync, header, scaling factor 40

modie. C odng
(NF), and variable-length
data as follows:

numbers where the statistical frequency of occurrence

of some va1ues in the series of values fonning the digital compensated DPCM modes and 0 for the intraframe number is greater than the statistical frequency of oc35 currence for other values in the series of values forming the digital number. The values forming the digital num-

In order to minimize overhead code bits, in one typi-

bers are generally the integers 0, 1, 2, 3, . . . and so on.

X(k)=x(I),.-(2), x(3), .. . x(k),

. . '. x(K)

TABLE I
variable

where I ~k~K.. Eacb value, x(k), has some value, Vp
from the set of J values,
VI, V2, VJ,...,
DATA

SYNC

HEADER

Vjo....

. In ~e header, at I~t one bit is r~erved fo~ the iden- where 1 ~j;;aJ. tlficatlon .of ~ull motion and graphic operatlon~. Th~ The occurrence of i consecutive values, Vjo within data portion mcludes the block-to-bl~k mode Identi- 50 the series X(k) is the runlength of such values denoted
fietS, ~he vect?r values, DPCM and Intrafr~m~ ~ata.
The bit al"oc~tl?ns are de~endent upon each indiVIdual In a first example with k= I, 0 . . , 14, if the digital block which IS Illustrated In TABLE 2. number XI (k) =0100000o 100021 , Vo=O, VI=I and V2=2 then XI(k)=VO , VI , V0 , VI , V0 , V2 , VI . In TABLE 2

by Vi-

-L
..MQQE. -2....-L

55 the series values forming XI(k), the first value Vo=O
occurs most frequent1y, the second value V I = I occurs next most frequently, and the other value V2=2 occurs least frequently. In a second example with k = I , 000' 14, if the digital
60 number X2(k)=O211l110001130, and

Replenishment Block

VECTOR Replenishment of Mouon Compensated Block
variable

V2=2, and V3=3; then X2(k)=VI I; V2 , VaS, VI

Vo=l, VI =0,

, Vel-,

DPCM or Non-motion Compensated Block
variable

D~M

, VI . In the series ofvalues forming X2(k), the first value, Vo= 1, occurs most frequently, the seond value

VI=O occurs next most frequently, and the other val65 ues, V2=2 and V3=3, occur next most frequently. Digital numbers formed with such frequencies of
occurrence ofvalues such as for XI(k) and X2(k) above,

INTRAFRAME EOB
Inlraframe or Non.molion Compen'Bled Block

are defined as having ordered redundancy. In the typi-

,'

."

~;

~. , .. ., , ".

.'
Page 12 of 20
is followed by another

Case 5:04-cv-03934-JF

Document 14-6

Filed 11/17/2004

698, 672
cal example described for X.(k), O's are most redundant,
runlength of O's

s are next most redundant, and so on. The frequency

is followed by a 1. The second part, R'

). The TABLE 3 formudescribed is merely one typical example. Any frequency lation is for one preferred embodiment of the ordered of occurrence order is possible, for example, the 2' s may 5 redundancy coding. Many variations, some hereinafter occur more frequently than I' s aDd O's may occur more described, are possib1e.
frequently than 2's.
dancy of the values,

of occurrence order of values 0, I, 2, . , . and so on

implies that a runlength of O' s

value greater than I (2, 3,

Digital numbers, X(k), will often have ordered redun- TABLE 3

Vj, forming the number. Ordered 1. From the magnitude (witbout sign) of quantized coefredundancy means that the frequency of occurrence of 10 ficient difference, form the following sets of histosome of the v~lues, Vi, formng the number (or grou~ of grams

such values) IS greater than that ~or other values (or

other groups of s~ch values) forming the n~mber and differences (including runlength of zero length)
that such frequencIes of occurrence are predlctab1e for
a number of digital numbers, X(k). IS

a. Runlength of consecutive zero-value

coefficient

When such o~dered redundancy. occu,:!, ~e orderc;d b. Runlength of consecutive zero-valued coefficient redu ndancy ~lng of the pr~ent inventIon IS us~ful In differences ("mcluding runlength of zero length) I!'aking the codmg more effiCIent. In the present mvenwith absolute amplitude value of greater than one
!IOn, the p~sence of a fi~t
IS used to Imply the eXIstence o~ a

the run)ength.
0.
Roo Rio R2, . . . , R255,

with absolute amplitude value of one at the end of

value (or a first set of values) at the end of the runlength.

second set of values) thereby ehmmating the need to
code the second value(or secc;md set ofv:u~es).

sec?nd value (or a 20 c. Occurrence of end of blocks (BOB, all D'
2. Get runlength Huffman code table from the histo10 R 2, . .

XJ(k) above is achieved as follows. Assume that when rep
the first vaJue, Vo, is followed by the second value, VI, 2S

By way' of example, the coding of am~sofntIdigital hnumberofROo R tabl the above. T e entries sthi ~e
2550 3 .,

that the second value is implied and such code is denoted

. Fr?m case b of 1, get the histogram of the amplitudes
values greater than one) at the end of the run-

(WIth Col where i represents the number of consecutive

Assume that when the first value Vo. is not"followed by 4. Get amplitude Huffman co~e table ~rom the histothe second value, V 10 such codeis denoted CoT/.

first values Vopreceding the implied second value, VI. length.

Assume 30

gram of 3 above. The entnes of this table can be

that any otber value is amplitude coded with A2=2 and represented as A2, ~3, 5. Encode the coeffiCIent differences along the Zlg-zag A3=3. With such. a notation, XI(k)=Qu , Co. , CoT3 path from the Huffman tables generated from 2 and 4 A3 Col
By way of the second example, X2(k) above, the first
in the follc:'wing

. . , A510. .

fashion.

value, Vo- I implies the second value, V I =0 such that 35 . a. CoefficIent differences of one at the end of the consecutive :reros-encode with R+SIGN, n= I, X2(k)=Clll , Coy3, A:z. Col , Col , CIll CoI , Coy2
ClO

, A30 2, 3, . o. , , 255.

b. Coefficient ~erences of greater t~an o~e at the , CoT3 , A3, Col , Col 6aud so forth are repre- end of consecutive zeros-encode with R +Am+255 and m=2, 3, 4, 00., 510. sented by a unique statistical code (typically a binary 40 SIGN, n = 1, 2, 3 code) from a runIength table such that the statistically 6. Encode With EOB at the end of each block.

In order to code XI(k)=CoI , Co.

each of the values Coi

more frequently occurring values have sborter code As can be seen from TABLE 3, two Huffman tables lengths and the statistically less frequently occurring or equivalent statistical coding tables are specified in the
values have longer code lengths.

One s Redundancy" (OR) coding. The runIength table

A series of values in digital numbers having a large 45 (including EOB~ consists of two parts, R and R' , with a percentage of zeros (O' s) followed by ones (l's) is . total of 5 13 entries (256 each for the first part R and the termed "One s Redundancy". One s Redundancy Cod- second part R' and 1 for EOB). The amplitude table

ing is one example of Ordered Redundancy (OR) cod- consists

of SO9 entries (amplitude values of 2 to 510). In

ing. The OR coding procedures for One s Redundancy a practical implementation, these two tables can be appear in TABLE 3 and are based upon 16X 16 trans- SO shortened with little performance degradation. form blocks of values where each such block gives rise ~pecific examples oftbe two tables specified in accortoadigitalnumber, X(k), having256values. Ofcourse, dance with TABLE 3 appear as the following TAany size blocks (NxM)ofdigitaJ values can be selected. BLES 6 and 7. TABLE 6 is a runlength table of the two Also, the digital values can be in block form represent- part example (R and R' or RI and R2) wbere R implies ing tI:ansform coefficients or can be multi-valued digital 5S a runlength ofO's followed by a 1. TABLES 6 and 7 are
derived based upon the bardware constraints (which In order to identify the beginning or end of the values are intended to be representative of a practical system, forming a number, X(k), a special "End of Block" sig- but are not intended to be limiting) of the following

signals, X(k), of any form.

nal, EOB, is utilized. When a plurality of numbers TABLE
XI(k), X2(k), X3(k), . . . and so on are to be coded and 60
transmitted, the EOB. code is inserted between the num-

bers, usually once after eacb number.
The TABLE 3 example is premised upon digitaJ sig-

nals having rust values V.=O, second values V2= I
and a set of other values, Vi". greater than I (2, 3, 4, . . 65

TABLE 4 1. Every code word must belong to part of a complete "tree 2. The longest code word (mcluding runlength escape,
runlength code and sign, or amplitude escape and

. ). Also, TABLE 3 has a run1ength table partitioned
into first and second parts, a fmt part, R (or COl), aDd
a

amplitude code) must not exceed 16 bits in length. 3. The maximum number of entries for each runlength
or amplitude table must not exceed 32.

second part, R' (or CoT). The first part, R, implies that a

Case 5:04-cv-03934-JF

Document 14-6

Filed 11/17/2004

Page 13 of 20

698 672
TABLE 5 gives four comparative examples for cod-

ing digital numbers using Scene

TABLE 6-continued
RUN LENGTH CODE TABLE FOR THE ONE' S REDUNDANCY" CODING RUN LENGTH CODES FOR DPCM MODE

Adaptive Coding

(SAC) and One s Redundancy (OR) coding. The One Rendundancy coding examples utilize TABLES 6 and 7
coding is considerably shorter than the SAC coding and hence OR coding is more efficient.

and the Scene Adaptive Coding examples utilize TA- 5 TL BLES 8 and 9. As can be seen from TABLE 5, the OR

FREQ # of BITS CODE ocr AL EQUIV

EOB

5047. 4

0010

TABLE 5
COMPARISON OF " OR" AND "SAC" CODING

10 where,

R ESC=code used whenever R-type value not in
R' ESC=code used when R' -type value not in table.

1. CO OOOOOOOOOOOOOOO1

EOB

OR RI9+S+EOB

SAC RLP+RI9 + A1+S + EOB 01/1110111/11/0/100001
000 1 OOO/OJIJO 10

table '
TABLE 7

2. CO ool-IOOOOOIOlJO..IEOB

SAC RLP+RJ:rAI+S+AI+S+RLP+R5+AI+S+RLP+ . RJ+AI+S+EOB
01/1111/11/0/11/1/01/11010/11/0/01/1011/11/1/

OR R2+S+Ro+S+R5+S+R)+S+EOB J 110/0/10/1100011/0/0000/1/0010 J. CO 200000oo.1 EOB
SAC A2+S+RLP+R7+AI+S+EOB
101/0/01/110011/11/1/100001 OR . Ro' +A2+S+R7+5+EOB 110/1/0/011110/1/0010 4. CO 1001.200001 EOB

100001 -

AMPLITUDE CODE TABLE FOR THE ONE' S REDUNDANCY" CODING AMPLITUDE CODES FOR DPCM MODE FREQ # or BITS CODE OCTALEQUlV

\1076.

2S :

where, coded
OR Ro+S+R2+S+Ro' +A2+S+Il4+S+EOB
10/0/1 I 10/0/1101 1/01101/0/0010

SAC AI+S+R2+AI+S+AH5+Il4+AI+S+EOB
11/0/1111/11/0/101/1/11100/11/0/10001

30 A

\I 178. 8 12 137. 7 13 113. 7
16 68. 17 67. 19 58. 8 10 49. 21 30. 50. 22 32. 10 23 33. 24 20. 10 2 25 31. 9 27 30. 9 6 22. 10 28 23. 10 29 14. II 20 14. II 31 10. II 32 14. II 3 ESe 423.
14 116. 15 79.
8

347. 6 10 277. 7 173. 6

3846. 4 I7SI. 52 982. 5 663. 435. 6

0110
01111 01010

01100

010011 010001 0101100

010\101 0100100
01110101 01110110 01001010 01000011 01000010 011101110 011101000 0\1101001
165 166 112 103 102

R=runlength, A = amplitude, S=positive sign,

S=negative sign, RLP=Run Length PrefIX (01), EOP=End Of Block, CO=digitaJ number to be 35 A
TA,BLE6

356

350
351

01\1011111 010000010
010000011 0100101100 0100000o1 0100101101 0100000oo 0100101110 01001011111 01110111100 01001011 110 01110111101 010111

T

RUN LENGTH CODE TABLE FOR THE ONE' S REDUNDANCY" CODING RUN LENGTH CODES FOR DPCM MODE CODE OCTAL EQUJV FREQ # orBITS L

737 202 203 454
201

40 A

455

200 456
1137 1674 1136 1675

R0

RI R2 RJ
R' I

R' 0

R4
R5
II. 6

R7 R8 R9
II. 10

R' 2

26644. 15621. 12324. 7148. 4610. 3384. 3143. 2577. 1967. 1764. 1452. 1327. 1089. 1013.

R' J
R ESC
R' ESC

994. 884. 876. 861. 687. 673. 602. 7 550. 496. 485. 455. 413. 402. 370. 345. 4599. 5 982.

2 3 3 4 4 5 5 5 6 6 6 6 6 7

110

010
1110

45 A .A

0000
01101

01100
00011 111100
011 110
50

where,

ESC=code used when amplitude "y.alue not in table. TABLE 8
RUN-LENGTH CODES FOR "SCENE ADAPTIVE CODING" VALUE LENGTH HUFFMAN CODE

001111 001101 000101 1111011 11 11010 011 1011

173 172

1111 1011

0111010 0011100 0011100 0011001 0011000 0001001 0001000 01111101 01111100
0111 000 I

9,
175 174
161
6.

01110000 00111011 00111010

160

III II

01\1111

11100 11010 10000 110011 110010 110001 110000 101011 101001 101000 100111 100110 100101 100100 100010

...,

),

Case 5:04-cv-03934-JF

Document 14-6

Filed 11/17/2004

Page 14 of 20

698, 672
TABLE 8-continued
RUN. LENGTH CODES FOR MSCENE ADAPTIVE CODING" VALUE LENGTH HURoMAN CODE
1110111 1110110 1101111 1101110 1101101 1101100 1010101 1000111 1000110
10101000 .

of" " parts (Rio R2, where n is equal to or greater than 2.' . The TABLES 6 and 7 were formed based upon the . assumption thai a separate sign bit, S. or S, not in the tables is to be used to indicate the sign of each value coded in the manner indicated in TABLE 5. Alternatively, the sign information can be encoded into
RII

(Rio R20 and R3), or more generally

TABLE 6 or TABLE 7. For example, a table like TABLE 6 can be used to represent runlengtbs of O'

10 that are followed both by positive and by negative nonzero numbers. Such a table would be greater in length

than TABLE 6 (expanded essentially to double the
length) to provide entries for runlengths ofO' s followed by both negative and . positive non-zero numbers. Of

RL. ESC

101010011 101010010 111010

15 course, such a table would be ordered in accordance
with the statistical frequency of both positive and negative numbers, The two tables, TABLES 6 and 7, were formed based

TABLE 9
AMPLITUDE CODES FOR SCENE ADAPTIVE CODING HUFFMAN CODE

VALUE LENGTH

20 categorized into. three basic groups or values, namely a firsl value, VI. a second value, V2, and all other values.

upon .the assumption that the values to be coded were

100

000
0011
10001

AMP.
RL-

12 . 8 0 1 14 13 16 5 19 7 8 11 22 . 9 0 24 JO 25 10 3 26 2 10 278 10 2SC E9 EOB
PREFIX

00100
100000 1001110. 1001100 0010111 10011111 10011011 10010011 10010001 00101101 100111101 100110101 100110100 100100100 100100000 001011001 001011000 1001111001 1001111000 1001001011 1001001010 1001000011 .1001000010 001010
100001

0, the second value V2 is I, and the third value is one within the set ofall values greater than 1. It often occurs 25 that in a block of values to be coded, the value 0 (the

In the particular example of coding, the first value V 1 is

first value) occurs statistically most frequently,
value I (the second value) occurs

the

statistically second . most frequently, and the other values (the third values)

30 With such a distribution tJaving ordered redundancy, .
the coding of tbe seccIDd value (I' s in this case) is

the least frequently.

avoided because the first value (O's in this case) is run-

length coded in two parts, one part that implies that the number following the runlength of O' s is the second
35 value (I in this case) and the other part that indicates

that the number following the runlength of O' s is within

the set of third values (values greater than I in this case).

Alternative formulations are possible. For example
. rather than categorizing the values to be coded into 40 three groups as done in connection with TABLE 6, four
or more groups are possible. For four groups, the fIrSt

. 00

. is coded in three parts, namely, a first part for implying a second value (for example V2= I), a second part for implying a third 45 value (for example V3=2) and a third part for indicating a set of fourth values (values greater than 2).
value (for example V 1=0)

In general, a multivalued digital number, X(k), to be

Vj, a (J+ I)-value, for j ranging from 1 to II, and or more parts or their equivalent may be used in the bas other values. The digital signals are coded with nrun1ength table. A typical example with three parts (R, implied values to form statistically coded signals such R' and R" ) is as follows. Runlengths of consecutive first that the more frequently occurring values of the digital . values (V I =0) are runlength encoded with three differ- signals are represented by shorter code lengths and the ent parts (Rio R2, or R3) depending upon the value 55 less frequently occurring values of coded signals are Additional variations are possible, for example, three 50 Vj+ VII' I.. . . , a n-value,

Ordered Redundancy Variations second value, V2, . . . , a j-value,

coded with n- I implied values has a first value, VI. a

is another value (greater than 2 such as 3, 4, 5, ' . 0 ), then
- value (O's in this case). If R3 is selected, then R3 is fol.

formingjrh encoding the runJength of the first value (O' s in this runlength code values representing the pumber of concase). If the following value is a third value (such as . secutive first values followed by thej+1 value; forming V3=2), then R2 is selected for encoding the runJength 60 additional runlength code values representing the numof the first value (O' s in this case). If the following value ber of consecutive first values followed by any of said
other values.

following the run1ength oCO' s. If the following value is represented by longer code lengths. The a second value (such as V2=1), thenRI is selected for cludes, for each value, Vj, for j from I to n,

coding in-

R3 is selected for encoding the runlength of tbe first While the embodiments

described have used one

code (such as R) based upon the existence of a runlength lowe d by an amplitude code to specify the exact value 65 of a first value to imply a second valu~ the implied code (3, 5, 0" ) following the runlength of first values (O's). is not limited to a single value but can be itse1fmultivalThe runlength table utilized with ordered redun- ued. For ~p~e, a runlength ofO's followed by two I' dancy coding can be oftwo parts (R and R'), three parts can be implied by a code R"

"-"

Case 5:04-cv-03934-JF

Document 14-6

Filed 11/17/2004

Page 15 of 20

698,672
While the implied coding of the second value was Aftl:r.a coded value is loaded into register 85, the sign typically as a result of runlength coding the first value, bit from register 76 is enabled to be stored in register 85 other types of coding of the first value are included by the enable gate 91 under control of the signal 94 from

within the present invention.

s, l' s and greater than l' s), the second value t~ts a no~.zero valu~ by asse~ng eit~er ~ equal-tosignal on Ime" or a s~gnal on lme 80slgnlfymg a greatfirst value (O's in this case) or to speci"fy the third values 10 ~r-than- l value m register 76. If the runlengtb of zer~s
(such as O'

As another alternative, the statistically most frequent 5 Thereafter, the next value, Vi, of the number, X(k), IS value is not necessarily the value that is runlength en- loaded into register 76. Counter 82 is cleared and a new coded. ' Where three groups of values are employed runlength of zeros is counted until ' comparator 77 dein tbis case) can be runlengtb encoded to imply the

the control 81.

(l' s

(numbers greater than I in this case). IS foJlowed by a value greater tban I, then line 80 IS
In an example. where the number of values Vi,

are present in tbe number X(k), then no amplitude cod- 15 the non-asserted signal on Ime ~7 ca~ses the runlength ing is required since the V,=O values can be runlength table ~4 to be addressed to obta!n a R value from table the output from table 84 to be gated coded and the values of V I = I can be implied. Simi- 84. Lme 8'

nated. For example, ifonly the values V. =0 and V2= I length value from. counter ~20n line '5 together WIth

limited, the need for amplitude coding can be elimi-

~d ~',Itrol 81 ~uses 87 to ~ not asserted, are asserted slgmfymg an R -typeline ~peration. . The ~nthereby of

ca~

V2=I, and V3=2, the valuesofV,=Ocan be runlength Because of a gr~ter than 1 value m register 76, ~n88.to be next enabled to pr~VJde coded while both V2= I. and V3=2, are implied using 20 trol 81 causes the lme

larly, for an example
nl' o-par ru en

with only the values V, =0,

to the code register 85. .

tnwexample where all of the valuesdavecrt ie ed. es b I an same
h table as

reviousl

n . , w mer FIG

0 er e a18FIG

, the si

coding can be eliminated.
eta! s ~ .

8.ltal value, Vi, of ~ digital the control 81 causes line 94 to be enabled to cause the num~er, X(k), tob~coded lsmput~othe COreg.ster.'6. sign value from register 76 to be stored in the code Typ~cally, the register 76.'s. a 160M regISter f~r stonng register 85. 16-blt val~es where the digital numbe~, X(k), !s form~ 30 The FIG. 3 coder continues to process code values in of K 16oblt values, each ~alue clocked mto register 76 an register 76 until an entire block of code values (aD val-

shown. In FIG. 3, each ~1

toprovi e eappropnateampltu 1 fth co er fFIG :2 -e line '3 for storage in the code regi. steev ueoutputon e d 14 n r 85. Thereafter,

0'

25

au outp~t from the amplitude table 83. The amplitude table 83 IS a random access memory or read only memroyI oa W t.h nI u e va ues ose ~fTABLE ded an:'p 7. The value m register 76 addrc:sses the amplitude table

lile th

output signal on line 78. an eq~-to-I SIgnal on line andaf!reate~-than- 1slgnalonhne80as~function
~al~e In register 76. The les ~han- I

ues for a digital number,. X(k)) bas been processed. pares ~e ~bsolute value of eac~ value an register 76 to Control 81 includes counters and other appropriate determme Irthat absolute value IS less ~an I, equal to 1, means for counting or otherwise determining all values or great~r than 1. .Comparator 78 provl~es a less-~an- I 35 comprising a

sequence and one at a time. The com1?arato~ 77 com-

m~lcates an equal-to-O condition. control 81 re- register 85. Control 81 provides the CLK, signal for celves the three. control values on ~ne 78, " an~ 80 40 clocking each new value into register 76, provides the from comparator 77 and controls, m a conventional CLK2 signal for incrementing the zero counter 83 and

~e

Signal on line 78 block, EOB, signal on line'3 for storage in the control

ofthe trot 81 enables the output line'3 to provide an end

79, ues for a digital number X(k) has been processed, con-

digital number. When a fuJl series of val-

manner, the coder operations.

from control 81 causes counter 82 to beset to a counting 45 In FIG. 3, when the amplitude table 83 is addressed and produces the ESe code, the ESe detector 126 senses that no amplitude value is available in tbe table length of zeros is counted. After being reset and with and signals control 81. The ESe value from table 83 is
mode for counting consecutive 0 values in register 76. Line 86 causes counter 82 to be reset after each run-

The "zero" counter 82 counts the run1ength of con- conventional manner, control 81 is controlled by a massecutive zeros detected by the comparator 77. Line 86 ter clock signal CLK, from the transmitter of FIG. 2.

CLK3 signal for clocking values into register 44. In a

line 86 setting counter 82 to tbe counting mode, counter gated into the code register 85. Thereafter, control 81 82 will count zeros until a non-zero value is detected in SO enables gate 127 via line 181 to gate the value from

register 76. If a non-zero value is detected, eitber a

equal-ta-l

signal on line" or a greater-than-

line 80 is enabled and detected by control 81. If an Huffman coded values of amplitudes not in the table 83.
equal-to-I signal is detected, control 81 asserts the line

I signal on additional table (not shown) can be provided for storing
Such an additional Huffman table would provide com-

register 76 into the code register 85. Alternatively, an

87 to specify the R type of operation. The enable line 87 55 pression or additional amplitude values.
together with the run1engtb count from counter
addresses tbe runlength table 84. Runlength table 84 is

82 In FIG. 3, when the runlength table 84 provides the
R ESe or the R' ESe code value, tbe ESe detector 126

typically a raudom access memory or a read oll1y

counter 82 together with the I-bit on line 87 address the cessing to occur. In the example described, gage 12' is table 84 to provide a runJength coded value output on enabled to enter directly the value from counter 82 into lines'3. The output from table 84 is under control of the the code register 85 so that runlengths not in the runsignal on line 8!1 from control 81 and loads the code lengtb table 84 are directly entered after the ESe code. register 85 with the runJength coded value from the 65 Atternative1y, an additional runlength table with HuffCODE column of TABLE 6. The runlength coded man coded runlength values can be employed to provalue implies that a runlength of zeros is followed by a vide additional compressed runlengths not in the table I in the manner previously described. '84.

ory storing coded runlength values like those of 130. The Ese code value is clocked into register 85, TABLE 6. The 0 run1ength output on line '5 from 60 and on the next cycle, control 81 causes alternate pro-

mem- senses the ESe value and signals the control 81 on line

..

Case 5:04-cv-03934-JF

Document 14-6

Filed 11/17/2004

Page 16 of 20

698,672

possible. 4
Decoder Detail-FIG.

While FIG. 3 depicts one embodimentforimplement- If line 113 indicates an R' -type operation, then line ing the coder 14 of FIG. 2, many other software and 121 is not enabled and line 118 is enabled to read out an hardwllI'e implementations of the coder are, of course, amplitude from amplitude table 104. Amplitude table 104 contains the information of TABLE 7 in inverse
In FIG, 4, further details of the decoder 54 of FIG. 1 dressed by the information in the CODE column and
5 order. The inverse order indicates that table 104 is ad-

into the register 101 by the CLK4 signal, is continuously binary number representing the amplitude. If an ESC value is called for, detector 102 signals synchronization , header and other control information control 107 to indicate that no valid ampl,tude will be and signals the control 107 when coded data is to fol- obtained' from table 104. When the A ESe code appears low. The coded data is clocked into register 101 one bit in the code register 101, the control 107 causes the next at a time. A code value clocked into register 101 is amplitude value in code register 101 to be gated directly presented in left-to-right order when viewing the 15 via gate 108 to the CO register 109. CODE column of TABLE 6. With eacb new code After an amplitude value is loaded into register 109 value bit, the coded data from.register 101 is input to the from table 104 or register 101, control 107 then signals inverse runlength table 103 and to the inverse amplitude via line 119 the loading of the sign bit from register 101
detected by the detector 102. Detector 102 senses the 10
table 104. The runlength table 103 includes the data of

are sbown. The serial-by.bit data is input on line 117 to provides an output on line 120 from the A column. the code register 101. The input data, as it is clocked Typically, the output value from the A column is a.

TABLE 6 organized in an inverse order. The inverse 20 the next code value on line 117 from the buffer 53 of order means that tab1e 103 of FIG, 4 is addressed by the FIG. 1.

into register 100. Register