Apple Computer Inc. v. Burst.com, Inc.
Filing
108
Declaration of Allen gersho in Support of 107 Response of Burst.com, Inc.'s Opposition to Plaintiff Apple Computer, Inc.'s Motion for Summary Judgment on Invalidity Based on Kramer and Kepley Patents filed byBurst.com, Inc.. (Attachments: # 1 Exhibit A to A. Gersho Declaration# 2 Exhibit B to A. Gersho Declaration# 3 Exhibit C to A. Gersho Declaration# 4 Exhibit D to A. Gersho Declaration# 5 Exhibit E to A. Gersho Declaration# 6 Exhibit F to A. Gersho Declaration (Part 1)# 7 Exhibit F to A. Gersho Declaration (Part 2)# 8 Exhibit G to A. Gersho Declaration# 9 Exhibit H to A. Gersho Declaration# 10 Exhibit I to A. Gersho Declaration (Part 1)# 11 Exhibit I to A. Gersho Declaration (Part 2)# 12 Exhibit J to A. Gersho Declaration# 13 Exhibit K to A. Gersho Declaration# 14 Exhibit L to A. Gersho Declaration# 15 Exhibit M to A. Gersho Declaration# 16 Exhibit N to A. Gersho Declaration# 17 Exhibit O to A. Gersho Declaration)(Related document(s) 107 ) (Crosby, Ian) (Filed on 6/7/2007)
Apple Computer Inc. v. Burst.com, Inc.
Doc. 108 Att. 13
Case 3:06-cv-00019-MHP
Document 108-14
Filed 06/07/2007
Page 1 of 10
Dockets.Justia.com
Case 3:06-cv-00019-MHP
702
Document 108-14
Filed 06/07/2007
Page 2 of 10
IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. COM-30, NO. 4, APRIL 1982
Abstract-New algorithms for the design of trellis encoding data Algorithm compression systems described. main are The algorithm a uses training sequence of actual data from a source to improve an initial trellis decoder. An additional algorithm extends the constraint length Decoder Algorithm DeltaMod Viterbi of a given decode? Combined, these algorithms allow the automatic. M, L Algorithm design a of trellis encoding system for a particular source. The sequence XU) .-source algorithms' effectiveness for random sources is demonstrated through performance comparisons with other source coding systems and with theoretical bounds. algorithms applied the The are to practical problem of the design of trellis and hybrid codesfor medium-to-lowrate speech compression.
y(i)
p:q
...
+p ...
Nonlinear Filter
Adpcm Decoder Fake ProcesS Decoder
u(j) .. channel sequence .-reproduction'sequence
Fig. 1 .
Datacompressionsystem.
INTRODUCTION
N the past decade considerable progress has been made towards an understanding of tree and trellis encoding data compression systems. In thesediscrete-time or sampled-data systems (Fig. l), a deterministic but possibly nonlinear decoding filter transforms the channel sequence into a reproduction sequence. The channel sequence is chosen by a tree or trellis search encoding algorithm to minimize the distortion between the reproduction sequence and the sourcesequence.Results in information theory have proved the existence of tree and trellis systems which operate close to the theoretical limits of performance,but these papersofferonly existence proofs, witho,ut describing ways of actually constructing good codes [201, ~ 5 1 . The study of encoding algorithms for tree and trellis codes has been of interest since the earliest work on convolutional channel coding. TheViterbialgorithm [l 11 is optimum for searching the trellis structures associated with finite-state decoders, but has computational cost exponential in the constraint length of the code. Someof the nonoptimal algorithms, such as the Fano and stack algorithms, have been derived from problems of decoding error correcting codes; othershave been designedspecifically forthetree source encoding problem. The M , L algorithm [21] , for example, is simply a breadthfirst tree search. Other search algorithms are classed as depthfirst or metric-first (distortion-first) types [2], [3]. Because many effective encoding algorithmsare known, the more difficult part of the design of a tree or trellis coding system lie's in the design of the decoder. Decoders may be drawn
'
I
Manuscript received June 2, 1981; revised September 29, 1981. This paper was presented in part at the IEEE International Symposium on Information Theory, Santa Monica, CA, February 1981. This work was supported in part by the Joint Services Electronics Program under Contract DAAG-0047, by .the U.S. Army Research Office under Contract DAAG29-80-K-0073, and by the Xerox Corporation. L. C. Stewart is with the Information Systems Laboratory, Stanford University, Stanford, CA 94305, and the ComputerScience Laboratory, Xerox Palo Alto Research Center, Palo Alto, CA 94304. R. M. Gray is with the Information Systems Laboratory, Stanford University, Stanford, CA 94305. Y.Linde is with the Codex Corporation, Mansfield, MA 02048.
from any of the traditional waveform coding techniques, such as predictive quantization. Such plagiarized decoder systems achieve improved performance by replacing their traditionalencodersby a tree or trellissearchalgorithm. In the literature, various other methods for selecting decoders have beenproposed.For speech sources, forexample,attempts have been made at the design of tree decoders based on predictive quantizers which match the average correlation properties 'of speech [4]. Variational methods have been proposed to improve decoders based on predictive quantizers and Linde and Gray have used the notion of a fake process to suggest decoders[5],[24] . While most of thesecodes based on traditional systems incorporate structures similar to recursive digital filters and thus have such a large number of states that they generate tree codes, several investigators - have use'd decoders incorporating either transversal digital filter approximations of recursivefilters or decoders originally based on f i n i t e impulse response models [23]. These decoders have a relatively small number of states and, therefore, a trellis structure. In this paper we describe new algorithms for the design of trellis encoding data compression systems. The main algorithm uses a training sequence 'of actual data from a source t o improve an initialtrellis decoder. An additionalalgorithmextendstheconstraintlength.of a given decoder.Combined, these algorithms allow the automatic design of a trellis encoding system for a particular source. The decoders designed with these techniques are locally optimal and, we. conjecture, globally optimal certain for sources [17]. The algorithms' effectiveness for random sourcesis demonstrated through performance comparison withother source coding systems and with theoretical bounds. The algorithms are also applied to the 'practical problem of the design oftrellis and hybrid codes for medium-to-low-rate speech compression. Additional information, includinga Soundsheet with the speech coding results, may be found in [34]. The goal of this paper is not the presentation of particular coding results, but the presentation of design methods which offer the potential of improving the performance of any existing trellis coder-or of constructing a new coder for a source of entirely unknown character.
'
'
0090-6778/82/0400-0702$00.75 0 1982 IEEE
Case 3:06-cv-00019-MHP
STEWART et a1 : TRELLIS WAVEFORM CODERS
Document 108-14
Filed 06/07/2007
Page 3 of 10
703
The new codeword is the average of those training sequence samples encoded by the old codeword. As a step towards the description of the trellis code design Repeated application these of twostepsmust result in algorithms, we describe an algorithm for the design of block decreasing, or at least nonincreasing, sample average distortion source codes,or vector quantizers, based on a long training sequence of symbols from a source. This algorithm is a multi- over the training sequence. Since the average distortion is nonnegative and decreasing, it must eventually a reach limit. dimensional version ofa quantizer design method ofLloyd Although the limitmay not be the global optimum, it is at [25] and is more completely reported by Linde et al. [22]. An N-level, k-dimensional quantizer is a function f that least a local optimum. The algorithm may be stopped either assigns t o each input vector x a reproduction vector x' drawn when a fixed point is reached (when no changes occur in the from a finite alphabet A = bi:i = 0, .-, N - l}. The function reproduction vectors or partitions), or when the reduction in f returnstheindex of the selected reproduction vector or average distortion per iteration falls below some threshold. If the vectorsource {xi} is ergodic andstationary,the codeword. quantizer The is described by reproduction the quantizer designed by this algorithm will work as well on data alphabet and an encoding rule. For a particular input (training) trainingsequence as fromthe training sesequence {xi: j = 0, -., n - l}, the encoding rule induces a fromoutsidethe quence itself. However, operation of the design algorithm does partition,S = { S i : i= 0, -,N- l}, of the input sequence into ergodicity. the disjoint sets Si = { j : f ( x i ) = y i } of the time indexes of not depend on either stationarity or those input vectors mapping into the ith reproductionvector. TRELLIS CODE DESIGN ALGORITHM The fidelity of reproduction is measured by a nonnegative The most general case ofatrellis decoder consistsofa distortion measure d(x, x'). Many distortion measures have finite-state machine driving a table-lookup codebook. of debeen proposed for various applications, but perhaps the best coder output values. Symbols arriving from channel the known is the squared-error measure drive the finite-state machine, which in turn selects reproduck- 1 tion symbols from the codebook. In what follows, we speciald(x, x') = ( X i -x i y . ize thefinite-state machine tothetradional case of a shift i= 0 register containingthe most recent k channel symbols (Fig. 2). The contents of the shift register are used as a table index An obviousencodingrulemaps each sourcevector into the trellis codedereproduction vector giving minimum distortion. A tie break- to select the decoder output codeword. The sign algorithm seeks t o fill in the contents of the codebook. ing rule is necessary but since ties are generally lowprobability events, nearly any rule will do. Suppose that we have a table-lookup trellis decoder, a single The initial conditions for the design algorithm are N , the symbol additive distortion measure, and an optimal encoding desired number of reproduction vectors, A', an initial quan- (search) algorithm such as theViterbi algorithmwhich will tizer, and {xi}, a long training sequence of symbols from the find the trellis encoding of a source sequence giving the lowsource. The algorithm consists of the repetition of two steps: est possible sample average distortion.The symbolsof the finding the best encoding of the training sequence for a given channel sequence, path or map, chosen by the encoding with the set of reproduction vectors, and finding the best set of repro- algorithm associate the sequence of source symbols reproduction sequence of codewords. This association can be duction vectors for the given encoding. used as thepartitionfunction inatrellis adaptation of the Encode: Given A m , the reproduction alphabet ofgeneration m, find the minimum distortion partition = p ( A m ) by block quantizer design algorithm. (See Table I.) Sm mapping each element of the training sequence to the minimum The initial conditions for the design algorithm are a finitestatedecoderwith initial codebook C o (such as theshift distortion reproduction vector: register decoder described above), a single symbol distortion f(x) = i: d(x,y i ) < d(x,yi), for all j measure (such as squared-error), and {xi}, a long training sewith some tie breaking rule. quence of symbols from some source. The algorithm consists the best encoding of the training Update Reproduction Alphabet: Given a partition Sm , find of two keysteps:finding the minimum distortion reproduction alphabet for generation sequence for a given codebook, and finding the best codebook m + 1, Am+' = A(Sm) = A(p(Am)),by settingy i m + ' ,the ith for the given encoding. Executed alternately, these steps proreproduction vector of the new alphabet, to the value giving vide an iterative design algorithm for improving the initial the minimum average distortion over the trainingsequence vec- trellis decoder. tors indexed by elements of Sirn. This value will be the genFind Encoding: Given the trellis codebook for generation eralized centroid,orcenter of gravity underthedistortion m, find the minimum average distortion encoding of the trainmeasure, of those training sequence values which were repro- ing sequence. This encoding induces a partition on the trainduced by the value y i m. ing sequence so that the elements of the partition cell correInthe case ofthesquared-errordistortion measure, this ponding to a certain codeword are the time indexes of those center of gravity calculation is just the sample average over a elements of the training sequence which were reproduced by partition: that codeword. Find Codebook: Given the partition for generation m , find the minimum distortion codebook for generation m 1. The updated value for a certain codeword will be the value giving BLOCK SOURCE CODE DESIGN ALGORITHM
x
+
Case 3:06-cv-00019-MHP
704
Shift Register Implementation (constraint-length9)
Document 108-14
TRANSACTIONS IEEE
Filed 06/07/2007
Page 4 of 10
4,APRIL 1982
COMMUNICATIONS, ON
VOL.NO. COM-30,
output (to D/A)
This expression does not work when a partition cell is empty. As mentioned, there are many ways to handle this situation; the goal of the method selected must be to select a value that will be used by the next pass of the encoder. Once the partition cell is no longer empty, the design algorithm will take care of adjusting the value of the associated codeword. EXTENSION
In thissection, we describea method of constructing a decoder based on a shift register of length k 1 from a decoder of length k. Our method has the advantage of constructTABLE I ing a decoder with sample average distortion over the training TRELLIS DECODER DESIGN ALGORITHM sequence at least as low as that of the starting (shorter) decoder. We call this method exlension because the new, longer (0) Initialization: Given a distortion threshold + 0, a q-ary noiseless .y t channel, an R state decoder, an initial codebookCo with cardinality decoder is constructedbyadding an additional stage to the I1Co I1 = N = qR, and a training sequence {xi} = { x j : j = 0, -, n shift register of the starting decoder. I}, set m = 0. Again, the decoder ofatrellis encoding system is imple(1) Given Cm = b i m : i = 0, ...,N - 1}, the codebook for generationm , find the minimum distortion trellis encoding{ i j : j = 0, .-,n - I} of mented by a shift register driving a table-lookupcodebook. the training sequence. This encoding induces a artition on the training sequence { S i m : i = O , - . , N - l}withSim = fIi:;i=yim}. Eachset Arriving channel symbols are shifted into the least significant Sim = P(Cm, { x i } ) contains the time indexes of those elementsthe end of the register and the contents of the register act as the of training sequence which were encoded by codeword yim. table address or codeword index to generate the decoder out(2) Compute theaverage distortion Am = n-lXi=On-l d(xi, ;i). (3) If at least one full iteration has been completed (m > 0) and the de- put. For a q-ary channel and constraint-length k decoder, let the register contents be r. With the arrival of symbol u from crease in distortion has fallen below the threshold E , ( a m - am-1)/ Am-1 < E , then halt with Cm as the final codebook. Otherwisego the channel, the new register contents will be (qr u ) mod qk to step (4). m o d q k . Now (4) Find the optimal codebook Cm+l for generation m + 1 as Cm+l = and the decoder will produce codewordy(,.,,.) C(P(Cm,{xi})) with Cm+l = {yim+l:i= 0, . - , N - 1) andyim+l = suppose the shift register is extended by one stage t o length Y : E a i m d ( X i , Y ) < Z i q m d ( x i , JJ'), for ally'. Replace m by m + 1 k 1; the codebook must increase in size from qk entries to and go to step(1). qk+' entries. We fill in the new codeword values by duplicating the old codebook 4 times so that the symbol stored in theminimum average distortion over thoseelements of the the new register stage does not affect the decoder output. Let training sequence indexed by the partition cell corresponding the old codebook contain codewords { y i : i = 0 , qk - 1); to that codeword. then the extended codebook contain codewords y r : will The encoding function-the trellis search-does not necessarily map a source symbol into the minimum distortion codeword, but maps the entiretraining sequence into the minimum average distortion sequence of codewords. i = 0 , -, qk - I . Each iteration of this procedure can only result in decreasing, or at least. nonincreasing, average distortion. Because the This procedure produces a decoder of constraint length encodingalgorithm is optimal, the new encoding canresult k 1 whose behavior is identical tothe behavior of the in distortion no worse thanthedistortiondue to using the original constraint-length k decoder. This new decoder can be old path with the new codewords-which, in turn, is at least used as the initial guess forthedecoderimprovement algoas good as the distortion due to using the old path with the rithm. old codewords. If the same path is chosen twice, the algorithm From an initial constraint-length 1 decoder, alternate applihas reached a f n e d point and will proceed no further. cation of the decoder improvement algorithm and the extenEach new codewordhasthe value whichminimizes the sion algorithm permits the design of successively longer codes average distortion over itspartition cell. Eachcodeword in (Table 11). generation m 1 will be the centroid of those elenients of the Extension can be illustrated by considering its application training sequencewhichwere encoded by the corresponding t o a one bit per symbol (q = 2 ) system using squared error codewordofgeneration m . Some rule mustbeadoptedto distortion. cover the case of an empty partition cell. Some approaches to Let the initial codebook for the constraint-length1 decoder this problem are t o retain the old codeword, to copy thevalue includecodewords - . l and +l. The trellis code design algoof anothercodeword,orto use thecentroidoftheentire rithm for this constraint length selects a locally optimal twotraining sequence as the new codeword. level scalar quantizer for the training sequence. Assuming that If the distortion measure is squared-error, d(x, X I ) = the mean of the training data is 0, the optimum partition for (x thencentroid the computationthe forupdated the final constraint-length 1 decoder collects all the samples codewords is particularly simple: in the training sequence with positive values in one partition cell and all the samples with negative values in the other. We have So = { j Ixi > 0 ) and SI = { j / x i< 0); ties are broken by assigning the associated sample to the first partition. The two
Fig. 2.
Shiftregisterimplementationofaonebitpersymboltrellis decoder.
+
+
+
., e .
+
+
Case 3:06-cv-00019-MHP
STEWART et al. : TRELLIS WAVEFORM
CODERS
Document 108-14
Filed 06/07/2007
Page 5 of 10
705
TABLE I1 A COMBINED EXTENSION N D IMPROVEMENT ALGORITHM
,380
Lloyd-Max quantizer
Scrambling function fake process decoder
Let Ckm refer to a constraint-length k codebook at the mth iteration of the decoder improvement algorithm. (1) Design an initial codebook CIO by finding a good q-level quantizer .rx)Trained decoders for the training sequence. .280 (2) Given Cko, an initial code of a certain constraint length, use the trellis code design algorithm improveit. The extentof this procedure will to .m Rate-distortion bound be governed by the value of E in the trellis code algorithm. I (3) If the constraint-length k is sufficiently large, or the distortion pro2 3 4 5 6 7 8 9 4 0 16 3 64 12a ~. 256 . _ . 512 vided by ckmsufficiently low, then halt. Constraint length (L number of codewords from (4)Use the extension algorithm to produce the codebook ck+lo Ckm and return to step(2). Fig. 3. Performance of fake process codes and trained random codes on the memoryless Gaussian source.
codeword values will be the means, respectively, of the positive and negative trainingsequence samples. The first extension of this decoder-to constraintlength 2-contains four codewords. The original partition is refined in a very intuitive way: the partition cell containing the positive valued samples of the training data is divided into two cells containing, respectively, the positive samples which were preceded in the training data by other positive samples, and those which were
whe1e.D is the average squared error and R is the information rat.qfn bits per symbol. In this formula, R is the theoretical minimum information rate required for any data compression system with average distortion no greater than D [8].
Memoryless Gaussian Sources
Fig. 3 compares decoders designed by the iterative design algorithm with the rate distortion bound, with the one-bit best n o t . S o o = { j I x ~ > O , x ~ - ~ > O } a n d S l o = { j I x ~ > O , x ~ - lscalar quantizer(the Lloyd-Max quantizer[31] ), andwith < 0} are the two subcells created from So (using binary notation the Linde-Grayscrambling function decoder [22]. Pearlman [32] reports squared error performance of 0.303 and 0.301 for the partition cell indexes). for length 9 and 10 decoders,respectively, designed using a CODING RANDOM SOURCES new theoryfor source coding with constrained alphabets. The basic trellis code design algorithm guarantees only two These results are very close to ours. Pearlman's decoders use only four discrete codeword values, but a fairly complex things: it will eventually halt and the average distortion obtained over the training data will be nonincreasing with each function is used to map the decoder register contents to the successive iteration. These guarantees are of considerable four codewords. Fehnand No11 [lo] have obtained similar theoretical interest, but the algorithm wouldbe of little practi- results using randomly populated trellis. Thetraineddecoders of Fig. 3 were designed using the cal value if iteither failed t o produce improved codes or atraining converged slowly. In practice, its convergence is almost always Viterbiencodingalgorithmforteniterationson shift register extremely rapid-a few iterations usually suffice-and per- sequence of 20 000 samples. Table-lookup decoders withrandomcodewords were used as the "initial formance improvements are usually obtained. The Gaussian i.i.d. and Gauss-Markov (autoregressive) guess" for the design algorithm. The results of Fig. 3 represent sources are common yardsticks of source coding. In this sec- thetraineddecoderperformanceondatafromoutsidethe tion, one bit per symbol trellis codes designed by the iterative training sequence. algorithm are compared with the fake process trellis codes of Fromtheory [8, ch. 41 we knowthatthereproduction Linde-Gray, with some recent results byother researchers, values of a data compression system should have a distribution andwiththeratedistortionlimits[18]. Since existing tree yielding theappropriatedistortion-ratefunction(thistechand trellis codes already perform quite close to the theoretical nique is used in [ 101). Since we would eventually like to use limits, there is not a lot of room for improvement, but the the trellis code design algorithm for sources with an unknown design algorithm is able toobtain 0.2-0.4 dB performance distribution, we may not be able to calculate the best R-D gains. Since the design maybe accomplishedoff-line,these distribution for the initial codebook. For this reason, we have gains are obtained without additional operating complexity. repeatedtheapproach of [22]and used initial codewords drawn from the sample distribution of the source, based on Rate-Distortion Functions the training sequence. A first-order Gauss-Markov source is the output of a first-order digital filter driven by Gaussian i.i.d. symbols: First-Order Gauss-Markov Fig. 4 presents performance results of trained decoders for xI. = = a x . !the < 1. al first-order Gauss-Markov source with correlation coefficients between 0.35 and 0.95. Shift register decoders of conwhere w is distributed N(0, u2 ). For u2 = 1 and sufficiently straint lengths 5 and 6 were designed by a combination of the small distortion,theShannon lower boundforthis source extensionalgorithmandthedecoderimprovementalgorithm with squared error. distortion is starting initial from constraint-length 1 decoders codewith words +1 and -1. The resulting decoders are compared with I -a2 1 -a R(D) = lg D
Disclaimer: Justia Dockets & Filings provides public litigation records from the federal appellate and district courts. These filings and docket sheets should not be considered findings of fact or liability, nor do they necessarily reflect the view of Justia.
Why Is My Information Online?