Ex Parte Budagavi

Patent Trial and Appeal Board

Apr 18, 2018

13668289 (P.T.A.B. Apr. 18, 2018)

UNITED STA TES p A TENT AND TRADEMARK OFFICE
APPLICATION NO. FILING DATE
13/668,289 11104/2012
23494 7590 04/20/2018
TEXAS INSTRUMENTS IN CORPORA TED
P 0 BOX 655474, MIS 3999
DALLAS, TX 75265
FIRST NAMED INVENTOR
Madhukar Budagavi
UNITED STATES DEPARTMENT OF COMMERCE
United States Patent and Trademark Office
Address: COMMISSIONER FOR PATENTS
P.O. Box 1450
Alexandria, Virginia 22313-1450
www .uspto.gov
ATTORNEY DOCKET NO. CONFIRMATION NO.
TI-71610 1048
EXAMINER
LAROCQUE, EMILY E
ART UNIT PAPER NUMBER
2182
NOTIFICATION DATE DELIVERY MODE
04/20/2018 ELECTRONIC
Please find below and/or attached an Office communication concerning this application or proceeding.
The time period for reply, if any, is set in the attached communication.
Notice of the Office communication was sent electronically on above-indicated "Notification Date" to the
following e-mail address( es):
uspto@ti.com
PTOL-90A (Rev. 04/07)
UNITED STATES PATENT AND TRADEMARK OFFICE
BEFORE THE PATENT TRIAL AND APPEAL BOARD
Ex parte MADHUKAR BUDAGA VI 1
Appeal 2017-011341
Application 13/668,289
Technology Center 2100
Before JASON V. MORGAN, ERIC B. CHEN, and NABEEL U. KHAN,
Administrative Patent Judges.
MORGAN, Administrative Patent Judge.
DECISION ON APPEAL
STATEMENT OF THE CASE
Introduction
This is an appeal under 35 U.S.C. § 134(a) from the Examiner's Final
Rejection of claims 1 and 6. Claims 2-5 and 7-10 are canceled. Ans. 2; see
also App. Br. 2. We have jurisdiction under 35 U.S.C. § 6(b).
We AFFIRM.
1 Appellant is the applicant, Texas Instruments Incorporated, identified in
the Appeal Brief as the real party in interest. App. Br. 2.
Appeal 2017-011341
Application 13/668,289
Invention
Appellant discloses "a unified forward and inverse transform
architecture that supports computation of both forward and inverse
transforms ... using shared hardware circuits." Abstract.
Representative Claim (key limitations emphasized)
1. An apparatus for computation of forward and inverse transforms,
the apparatus comprising:
a first decomposition circuit configured to receive an N-point input
vector, wherein the first decomposition circuit is operable to
decompose the N-point input vector to form a first (N/2)-point vector
and a second (N/2)-point vector, wherein, in response to a control
signal, the first (N/2)-point vector and the second (N/2)-point vector
are inputs for an N-point forward transform computation or inputs for
an N-point inverse transform computation;
a first matrix multiplication circuit coupled to the first decomposition
circuit to receive the second (N/2)-point vector;
aforward and inverse (N/2)-point transform computation circuit
coupled to the first decomposition circuit to receive the first (N/2)-
point vector;
a first recomposition circuit coupled to receive a first (N/2)-point
output vector from the first matrix multiplication circuit and a second
(N/2)-point output vector from the forward and inverse (N/2)-point
transform computation circuit, wherein the first recomposition circuit
is operable to compose an N-point output vector from the first (N/2)-
point output vector and the second (N/2)-point output vector, wherein,
in response to the control signal, the N-point output vector is an
output of the N-point forward transform computation or an output of
the N-point inverse transform computation,
wherein the first matrix multiplication circuit is configured to multiply
the second (N/2)-point vector with an (N/2) x (N/2) matrix, the
(N/2) x (N/2) matrix consisting of elements from odd lines of an NxN
transform coefficient matrix, and
2
Appeal 2017-011341
Application 13/668,289
wherein the forward and inverse (N/2)-point transform computation
circuit is configured to compute an (N/2)-point forward transform or
an (N/2)-point inverse transform responsive to the control signal.
Rejection
The Examiner rejects claims 1 and 6 under 35 U.S.C. § 103(a) as
being unpatentable over Fettweis (US 5,452,466; issued Sept. 19, 1995) and
Pan (US 6,587,590 Bl; issued July 1, 2003). Final Act. 2-10.
INVENTION SUMMARY
Claim 1 is directed to circuitry that computes one of two transforms
using shared operations. These are referred to as a "forward" transform and
an "inverse" transform, although there is no guarantee that the inverse
transform will be the inverse of the forward transform. This lack of a
guaranteed inverse relationship between the two transforms reflects the
intended application of the claimed circuitry to high efficiency video coding
(HEVC), which involves additional quantize and inverse quantize operations
between the forward and inverse transforms. Spec. i-fi-1 3, 87, 90, and Fig. 19.
Each of the transforms is represented by the multiplication of an NxN
matrix by an N-point input vector to obtain an N-point output vector. The
Specification provides example forward and inverse 4-point transforms that,
while non-limiting, illustrate how operations between forward and inverse
transforms are shared.
The Specification discloses a forward 4-point transform of input
vector M = [MO, Ml, M2, M3f to output vector P = [PO, Pl, P2, P3f
using the operation P = D4 M, where D4 is given by:
[
C16
cs
D4 = C16
C24
C16
C24
-C16
-cs
3
C16
-C24
-C16
cs
C161 -cs
C16
-C24
Appeal 2017-011341
Application 13/668,289
Spec. i-f 37. C8, C16, and C24 are constants defined in the 32-point HEVC
core transform matrix as C8 = 83, C16 = 64, and C24 = 36. Id. i-f 35.
The inverse 4-point transform of input vector X = [XO, Xl, X2, X3f
to output vector Y = [YO, Yl, Y2, Y3f uses the operation Y = DIX. Spec.
,-r 40.
Both the forward and inverse 4-point transforms are decomposed in
slightly different ways to create matrices that, with either some pre-
processing or post-processing, can be used for either transform.
The forward 4-point transform is decomposed by pre-processing input
vector M values to produce intermediate input vector [KO, Kl, K2, K3f
using addition and subtraction operations as follows:
[
KO] I MO + M31 l l 2
K2 - -Ml+ M2
K3 -MO+M3
Spec. Fig. 2.
The even output vector values are calculated from a 2x2 matrix
multiplication involving two of the intermediate vector values as follows:
[PO] = [C16 P2 C16
C16] [KO]
-C16 Kl
Id.
The odd output vector values are calculated from a different 2x2
matrix multiplication involving two of the intermediate vector values as
follows:
[Pl] = [-C24 P3 CS
-CS ] [K2]
-C24 K3
Id.
4
Appeal 2017-011341
Application 13/668,289
The inverse transform is decomposed slightly differently, with the
even input values used directly-using the same matrix used to produce
even forward transform output vector values-to produce two values in
intermediate output vector Z = [ZO, Zl, Z2, Z3f using the following matrix
multiplication:
[ZO] = [C16 Zl C16
C16] [XO]
-C16 X2
Id. at Fig. 3.
Similarly, the odd input values are used directly-using the same
matrix used to produce odd forward transform output vector values-to
produce the remaining two values in intermediate output vector Z using the
following matrix multiplication:
[Z2] = [-C24 Z3 CS
-CS ] [Xl]
-C24 X3
Id.
To produce output vector Y of the inverse transform, values from
intermediate output vector Z are used in post-processing addition and
subtraction operations as follows:
[
YO] [zo -Z31 Yl Zl -Z2
Y2 Zl +Z2
Y3 ZO +Z3
Id.
With these even-odd decompositions, referred to in the Specification
as "partial butterfly decomposition[ s ]" (Spec. i-f 3 8), a shared architecture
can perform either a forward or an inverse transform. An example unified
architecture for performing the 4x4 forward or inverse transforms P = D4 M
and Y = DIX is disclosed in the Specification's Figure 7, reproduced below:
5
Appeal 2017-011341
Application 13/668,289
r---------------,
I DECOMPOSITION I
I I
I AddSub4 I
I I
I I
I EVEN4
i---o-I ~ rC16 C16]
C16 -CHl
I
I
I
inv_fwd_flag I
I
I I
L--------------~
r-------------....,
I RECOMPOSITION I
I I
I I
I I
I AddSub4 I
:~1 :
I J I
- I ~]
invJwd __ flag
,____....._ 021
I 03
I
I
1 inv_fwdJag :
L-------------...l
FIG. 7
The Specification's Figure 7 illustrates an architecture for perfonning
either a forward or inverse transform using input vector I = [IO, 11, 12, I3F
(which represents M for a forward transform and X for an inverse transform),
output vectors [00, OlF and [02, 03F (which represent2 [PO, P2F and
[Pl, P3F for a forward transform or [YO, Yl F and [Y2, Y3F for an inverse
transform), intermediate output vectors [AO,A2F and [A2,A3F, and a
control flag (inv_fwd_flag). See also Spec. i-fi-145--46. The architecture
includes decomposition components, even and odd 2x2 matrix
multiplication components, and recomposition components. Id. at Fig. 7.
How the example architecture reads on the limitations of claim 1 is
mostly straightforward. Figure 7 illustrates decomposition and
2 The Specification's disclosure erroneously maps 02 to PO instead of PI.
Spec. i1 45. However, this mapping is inconsistent with the decomposition
illustrated in the Specification's Figure 2 and the non-unified example
architecture illustrated in the Specification's Figure 6.
6
Appeal 2017-011341
Application 13/668,289
recomposition components that read on the claimed first decomposition
circuit andfirst recomposition circuit. And Figure 7's ODD4 matrix reads
on the claimed first matrix multiplication circuit. The only recitations in
need of additional context beyond the example 4x4 transforms architecture
are the recitations directed to a forward and inverse (N/2)-point transform
computation circuit coupled to the first decomposition circuit to receive the
first (N/2)-point vector, wherein the forward and inverse (N/2)-point
transform computation circuit being configured to compute an (N/2)-point
forward transform or an (N/2)-point inverse transform responsive to the
control signal.
With the 4x4 forward or inverse transform example provided in the
Specification, the "forward and inverse (N/2)-point transform computation
circuit" would be the even 2x2 matrix multiplication, which operates the
same regardless the inv_fwd_flag value. Spec. n 5---6. However, the
Specification also discloses additional embodiments directed to architectures
for at least 8x8, 16x16, and 32x32 forward or inverse transforms. See, e.g.,
id. i-fi-147-58, Figs. 13-15. In each of these example embodiments, the even
(N/2)x(N/2) matrix multiplication is identical to the forward and inverse N/2
transform disclosed in the Specification. See id. i-fi-1 50 ("the even matrix of
the 8-pt forward transform ... is identical to the 4-pt forward transform ...
and the even matrix of the 8-pt inverse transform ... is identical to the 4-pt
inverse transform"), and 56. Thus, these embodiments can make use of an
N/2 forward or inverse transform circuit rather than a matrix multiplication
to obtain the output values of the (N/2)x(N/2) even matrix multiplication.
See id. Figs. 13-15. The recitations directed to use of a "forward and
7
Appeal 2017-011341
Application 13/668,289
inverse (N/2)-point transform computation circuit" appear intended to
encompass these recursively-defined embodiments.
FINDINGS AND CONTENTIONS
In rejecting claim 1 under 35 U.S.C. § 103(a), the Examiner finds the
discrete cosine transforms (DCT) and inverse discrete cosine transforms
(IDCT) architecture of Fettweis-which includes pre-processor 3', shuffle-
exchange unit 30, and post-processor 2'-teaches or suggests most of the
recitations, including a forward and inverse (N/2)-point transform
computation circuit coupled to the first decomposition circuit to receive the
first (N/2)-point vector, wherein the forward and inverse (N/2)-point
transform computation circuit is configured to compute an (N/2)-point
forward transform or an (N/2)-point inverse transform responsive to the
control signal. Final Act. 3--4 (citing Fettweis col. 7, 11. 27-28, 32-37, 45-
54, col. 8, 11. 1-5, Figs. 1, and 9-10). The Examiner relies on Pan's matrix
multiplication, using an (N/2)x(N/2) matrix formed using a subset of
elements from an NxN matrix, to teach or suggest wherein the first matrix
multiplication circuit is configured to multiply the second (N/2)-point vector
with an (N/2) x (N/2) matrix, the (N/2) x (N/2) matrix consisting of elements
from odd lines of an NxN transform coefficient matrix. Final Act. 5 (citing
Pan col. 28, 11. 37--44, col. 29, 11. 45-54, 60-64, col. 53, 1. 67---col. 54, 1. 5,
Figs. 13, and 14).
Appellant contends the Examiner erred because the Examiner relies
on a subset of outputs from the shuffle-exchange unit of Fettweis to teach or
suggest the claimedforward and inverse (N/2)-point transform computation
circuit, but "each of the outputs of such an operation is still dependent on all
[NJ inputs." App. Br. 8. Appellant argues an "N input, N/2 output operation
8
Appeal 2017-011341
Application 13/668,289
does not correspond to an '(N/2)-point transform."' Id.; see also Reply Br.
2--4. Appellant further argues that "when operating in the IDCT mode, the
shuffle-exchange circuit (30) in Fettweis receives data that has already been
partially transformed. As such, the shuffle-exchange circuit (30) in Fettweis
at most performs a part of an N-point transform." App. Br. 8 (citation
omitted); see also Reply Br. 4.
Appellant also contends the Examiner erred in relying on Pan because
"Pan does not include a circuit that implements" the (N/2)x(N/2) matrix
multiplication relied on. App. Br. 10. Appellant argues the equation "is
merely part of a derivation for [another equation] (which serves as the core
component for the 2-D DCT algorithm) and is not actually implemented as a
circuit in the system of Pan." Id.
Appellant also argues "the shuffle-exchange circuit (30) in Fettweis
operates on vectors and not matrices," but "Pan operates on matrices - not
vectors." Id.; see also Reply Br. 5-7. Appellant contends "replacing the
shuffle-exchange circuit in Fettweis (30) with an incompatible component
would not provide another way of performing the DCT and IDCT
operations, but would instead destroy the functionality of the overall
DCT/IDCT architecture in Fettweis, thereby rendering the system in
Fettweis to be unsatisfactory for its intended purpose." App. Br. 11; see also
Reply Br. 6-9.
Appellant makes substantially the same arguments with respect to
claim 6. App. Br. 12-18; see also Reply Br. 9.
ANALYSIS
We agree with and adopt as our own the Examiner's findings of facts
and conclusions as set forth in the Answer and in the Action from which this
9
Appeal 2017-011341
Application 13/668,289
appeal was taken. We have considered Appellant's arguments, but do not
find them persuasive of error. We provide the following explanation for
emphasis.
We are unpersuaded by Appellant's argument that an "N input, N/2
output operation does not correspond to an '(N/2)-point transform."' App.
Br. 8. As the Examiner correctly notes, "[r]egardless of how many input
points [shuffle-exchange circuit] 30 comprises, [N/2] of those inputs are
transformed." Ans. 3. Appellant does not identify any recitations that
preclude the forward and inverse (N/2)-point transform computation circuit
from accepting more than N/2 inputs as part of the transformation.
We are unpersuaded by Appellant's argument that "the shuffle-
exchange circuit (30) in Fettweis receives data that has already been partially
transformed." App. Br. 8. Appellant fails to identify recitations that
proscribe the N-point input vector from having been partially transformed
before being processed by the claimed apparatus.
We are unpersuaded by Appellant's arguments that "Pan does not
include a circuit that implements" the (N/2)x(N/2) matrix multiplication
relied on. Id. at 1 O; see also Reply Br. 8 ("an equation does not perform an
algorithm"). "[T]he question under 35 USC 103 is not merely what the
references expressly teach but what they would have suggested to one of
ordinary skill in the art at the time the invention was made." Merck & Co. v.
Biocraft Labs., Inc., 874 F.2d 804, 807 (Fed. Cir. 1989) (quoting In re
Lamberti, 545 F.2d 747, 750 (CCPA 1976)) (emphasis added). The
Examiner's findings show that Pan teaches or suggests using circuitry to
perform operations expressed through equations. See Ans. 4 (citing Pan col.
52, 11. 10-23).
10
Appeal 2017-011341
Application 13/668,289
We are unpersuaded by Appellant's argument that "replacing the
shuffle-exchange circuit in Fettweis (30) with [Pan's] incompatible
component would ... destroy the functionality of the overall DCT /IDCT
architecture in Fettweis." App. Br. 11; see also Reply Br. 6, 8-9. However,
the test for obviousness is based on what the combined teachings of the
references suggest, not on whether features of one reference can be bodily
incorporated into another. See In re Keller, 642 F.2d 413, 425 (CCPA
1981 ). As the Examiner notes, the rejection does not posit replacing the
entire shuffle-exchange circuit of Fettweis, but rather replacing the butterfly
architecture within shuffle-exchange circuit 30. See Ans. 4 (citing Final Act.
5); see also Fettweis col. 6, 11. 12-21, Fig. 9 (shuffle exchange circuit 30
employs "butterfly units").
Finally, we are also unpersuaded by Appellant's argument that
Fettweis merely operates on vectors while Pan merely operates on matrices.
See App. Br. 10; see also Reply Br. 5-7. The Examiner correctly finds that
a "vector is a type of matrix that ... is one-dimensional, i.e.[,] N rows by 1
column" (Ans. 4). Appellant responds by noting "that the matrix described
in Pan and relied upon by the Examiner is not an N rows by 1 column
matrix." Reply Br. 5; see also id. at 7. Appellant's arguments are
unpersuasive because an artisan of ordinary skill would have understood that
the matrices described in Pan represent ordered sets of column vectors.
Appellant argues that "[ m ]ultiplying two matrices together to produce a
matrix ... does not correspond to multiplying a vector with a matrix to
produce a vector." Reply Br. 5. However, multiplying a matrix by an
ordered set of column vectors (i.e., by a second input matrix) produces an
output ordered set of column vectors (i.e., an output matrix). The number of
11
Appeal 2017-011341
Application 13/668,289
column vectors produced depends on the number of columns in the second
input matrix, but the multiplication produces at least one column vector
(assuming the matrices are not empty). Because an artisan of ordinary skill
would have recognized and appreciated this nexus between matrices and
vectors, we agree with the Examiner that the premise of Appellant's
arguments-that there are major differences between vectors and matrices
that would render non-obvious the use of Pan's teachings to modify
Fettweis-is unsupported by the preponderance of evidence. See Ans. 5.
Therefore, Appellant's arguments are not persuasive of error in the
Examiner's findings and conclusions.
For these reasons, we agree with the Examiner that the combination of
Fettweis and Pan renders obvious: (1) "a forward and inverse (N/2)-point
transform computation circuit coupled to the first decomposition circuit to
receive the first (N/2)-point vector"; (2) "wherein the first matrix
multiplication circuit is configured to multiply the second (N/2)-point vector
with an (N/2) x (N/2) matrix, the (N/2) x (N/2) matrix consisting of
elements from odd lines of an NxN transform coefficient matrix"; and (3)
"wherein the forward and inverse (N/2)-point transform computation circuit
is configured to compute an (N/2)-point forward transform or an (N/2)-point
inverse transform responsive to the control signal," as recited in claim 1.
Accordingly, we sustain the Examiner's 35 U.S.C. § 103(a) rejection
of claim 1, and claim 6, which Appellant argues is patentable for
substantially the same reasons. App. Br. 12-18; see also Reply Br. 9.
12
Appeal 2017-011341
Application 13/668,289
DECISION
We affirm the Examiner's decision rejecting claims 1 and 6.
In the event of further prosecution, the Examiner should ascertain
whether the claims are directed to statutory subject matter. Although the
Specification discloses the application of claimed forward and inverse
transforms computation apparatus in HEVC, the claims contain no
recitations limiting the claimed apparatus to HEVC applications. The
Specification explicitly discloses that an artisan of ordinary skill would
recognize "embodiments for transforms that have similar symmetry
properties to the HEVC core transform." Spec. i-f 108. Furthermore, while
claimed as a combination of "circuits," the Specification broadly discloses
"[ e ]mbodiments of the methods, encoders, and decoders described ... may
be implemented in hardware, software, firmware, or any combination
thereof." Spec. i-f 111. Thus, rather than being directed to a particular
machine or being limited to particular application, the invention as claimed
appears to encompass an abstract mathematical algorithm implemented on
any type of machine. This Board has affirmed 35 U.S.C. § 101 rejections, or
entered new grounds of rejection under 35 U.S.C. § 101, with respect to
claims that are similarly directed to abstract mathematical algorithms not
tied to a particular machine. See, e.g., Ex parte Gustavson, App. No. 2010-
003918, (PTAB 2013) (expanded panel) (non-precedential), available at
https://e-foia.uspto.gov/Foia/RetrievePdf?system=BPAI&flNm=
fd2010003918-04-18-2013-1; Ex parte Cryptography Research, Inc., App.
No. 2017-005069, (PTAB 2017) (non-precedential), available at https://e-
13
Appeal 2017-011341
Application 13/668,289
foia.uspto.gov/Foia/RetrievePdf?system=BPAI&flNm=fd2017005069-09-
26-2017-1.
No time period for taking any subsequent action in connection with
this appeal may be extended under 37 C.F.R. § 1.136(a). See 37 C.F.R.
§ 41.50(±).
AFFIRMED
14