T 2377/17 (Parallel additions and subtractions/PHILIPS) of 3.12.2018

Summary of Facts and Submissions

I. The applicant (appellant) appealed against the decision of the Examining Division refusing European patent application No. 99902775.8.

II. The application was filed as international application PCT/IB99/00315 on 22 February 1999. The international search report was issued by the Swedish Patent Office on 1 September 1999. The applicant filed requests for entry into the regional phase before the EPO and examination on 26 October 1999 and paid the relevant fees on 20 December 1999.

On 16 March 2012, the applicant requested accelerated examination under the EPO's programme for accelerated prosecution of European patent applications (PACE). On 5 April 2012, the appellant was informed that the EPO would be able to supply a communication within six months.

The first substantive communication under Article 94(3) EPC was issued on 7 February 2014, to which the applicant replied by letter of 2 May 2014.

On 20 April 2015, the applicant filed a second PACE request. On 6 May 2015, the appellant was informed that the EPO would be able to supply a communication within three months.

On 12 November 2015, the appellant was summoned to oral proceedings to be held on 19 April 2016. After a further exchange of letters, communications and emails and a number of telephone conversations, the oral proceedings were postponed to 22 June 2016.

III. After the oral proceedings, the Examining Division issued a communication under Rule 71(3) EPC, expressing the intention to grant a patent on the basis of the then second auxiliary request with minor amendments made by the Examining Division in the Druckexemplar. The applicant subsequently disapproved of the proposed text and maintained its main request and first and second auxiliary requests. The Examining Division then refused the application.

IV. The decision cited the following documents:

D1: |WO 97/08608 A1, 6 March 1997; |

D2: |EP 0 755 015 A1, 22 January 1997; |

D3: |EP 0 680 013 A2, 2 November 1995; |

D4: |E. Holmann et al.: "Single Chip Dual-Issue RISC Processor for Real-Time MPEG-2 Software Decoding", Journal of VLSI Signal Processing, Vol. 18, No. 2, 1998, pp. 155-165; |

D5: |EP 0 723 220 A2, 24 July 1996; |

D6: |K. Kloker et al.: "Efficient FFT Implementation on an IEEE Floating-point Digital Signal Processor", Proceedings of ICASSP, 23-26 May 1989, Vol. 2, pp. 1302-1305; |

D7: |S. Ramaswamy and G. Miller: "Efficient Implementation of the Two Dimensional Discrete Cosine Transform for Image Coding Applications on the DSP96002 Processor", Proceedings of the 36th Midwest Symposium on Circuits and Systems, 16-18 August 1993, pp. 96-99; |

D8: |P. Kalapathy: "Hardware-software Interactions on Mpact", IEEE Micro, Vol. 17, No. 2, 1997, pp. 20-26; |

D8a: |P. Kalapathy: "Hardware/Software Interactions on the Mpact Media Processor", Hot Chips: A Symposium on High Performance Chips (HC08), 18-20 August 1996, retrieved from: http://www.hotchips.org/wp-content/uploads/hc_archives/hc08/3_Tue/HC8.S6/HC8.6.2.pdf; and|

D9: |US 5 815 698 A, 29 September 1998. |

The Examining Division decided that the subject-matter of claim 1 of both the main request and the first auxiliary request lacked inventive step over document D2 in combination with common general knowledge as exemplified by documents D5 to D8. The decision mentioned that the applicant had not approved the text of the second auxiliary request.

V. In the statement of grounds of appeal, the appellant submitted a main request and first and second auxiliary requests. The main request corresponded to the previous main request refused by the Examining Division with minor clarifying amendments. The first auxiliary request was a new request. The second auxiliary request was the previous second auxiliary request as amended by the Examining Division in the Druckexemplar.

VI. In a communication accompanying a summons to oral proceedings, the Board introduced the following document:

D10: |C. Loeffler et al.: "Practical Fast 1-D DCT Algorithms with 11 Multiplications", Proceedings of the International Conference on Acoustics, Speech, and Signal Processing 1989, pp. 988-991.|

It expressed, inter alia, the preliminary view that the subject-matter of claim 1 of the main request lacked inventive step over document D2 and that the subject-matter of claim 1 of the second auxiliary request lacked inventive step over document D10. It also questioned the admissibility under Article 12(4) RPBA of the first auxiliary request and raised a number of objections under Articles 84 and 123(2) EPC.

VII. As part of its written submissions in preparation for the oral proceedings, the appellant filed auxiliary requests 1a, 1b, 1c, 2aa, 2a, 2b, 2c, 3a, 3b, 3c and 3d.

VIII. In the course of the oral proceedings held on 3 December 2018, the appellant replaced its requests with a new sole request and submitted a request for reimbursement of the appeal fee in view of the delays in the first-instance proceedings. It also consented to the Board mentioning its PACE requests in the written decision. At the end of the oral proceedings, the chairman pronounced the Board's decision.

IX. The appellant's final requests were that the decision under appeal be set aside, that a patent be granted on the basis of the following documents:

- Description: pages 1, 2, 2a and 3 to 15, as filed during the oral proceedings;

- Drawings: sheets 1/4 to 4/4, as filed during the oral proceedings;

- Claims: claim 1 of the new sole request, as filed during the oral proceedings;

and that the appeal fee be reimbursed.

X. Claim 1 of the sole request reads as follows:

"A data processing device configured to perform a DCT or iDCT computation, comprising:

an operand storage circuit comprising at least one source register for storing operands and at least one result register for storing a result, each register being notionally subdivided into a plurality of segments at respective positions in the register,

a functional unit (20) for executing an instruction (INS2) including an opcode and referring to one source register and to one result register in the operand storage circuit,

said instruction causing the functional unit to execute at least two operations in parallel and independently of one another,

each of the at least two operations adding or subtracting segments from the referred one source register, half of the operations are addition operations and half of the operations are subtraction operations, the segments having mutually different positions in the referred one source register,

each of the one source register and the one result register comprises a first segment, a second segment, a third segment and a fourth segment,

said at least two operations comprise

summing numbers stored in the first segment of the one source register and the fourth segment of the one source register yielding a first result,

summing numbers stored in the second segment of the one source register and the third segment of the one source register yielding a second result,

subtracting the number stored in the third segment of the one source register from the number stored in the second segment of the one source register yielding a third result,

subtracting the number stored in the fourth segment of the one source register from the number stored in the first segment of the one source register yielding a fourth result,

and to store the first result in the first segment of the one result register, the second result in the second segment of the one result register, the third result in the third segment of the one result register and the fourth result in the fourth segment of the one result register."

Reasons for the Decision

1. The appeal complies with the provisions referred to in Rule 101 EPC and is therefore admissible.

2. The application

2.1 The application relates to a data processing device employing SIMD (Single Instruction Multiple Data) instructions for processing data in parallel. As explained on page 1, lines 3 to 15, of the published application, SIMD instructions typically operate on two operands, each operand being subdivided into a plurality of segments. Conventional SIMD instructions apply the same operation in parallel to segments in corresponding positions of each operand.

2.2 The application proposes providing SIMD instructions that apply different operations to different operand segments or that operate on segments which are not in corresponding positions. It also proposes a set of specific instructions INS1 to INS7 for speeding up (inverse) discrete cosine transform (DCT/IDCT) computations.

2.3 These specific instructions were designed to support an 8-point one-dimensional IDCT computation performed according to the data-flow diagram shown in Figure 2:

FORMULA/TABLE/GRAPHIC

To allow this computation to be implemented efficiently, the data-flow diagram was split up into boxes 39a to 39f and 39h, as shown in Figure 3 below, and a dedicated SIMD instruction for each box was designed and provided the corresponding functionality.

FORMULA/TABLE/GRAPHIC

2.4 Claim 1 of the sole request is directed to the INS2 instruction, which provides the functionality of box 39b and is described on page 10, lines 14 to 32, of the published application with reference to Figure 4a. The INS2 instruction has one source operand and one result operand - both operands having four segments - and performs the four operations listed in claim 1 (two additions, two subtractions).

3. Added subject-matter

3.1 The data processing device of present claim 1 essentially corresponds to the data processing device of original claim 1, limited to being adapted to execute the INS2 instruction as described on page 10, lines 14 to 32, of the application, and to being "configured to perform a DCT or iDCT computation".

3.2 According to the description on page 14, lines 9 to 19, any one of the instructions INS1 to INS7 can be used to speed up the computation of an IDCT. Although the term IDCT is normally understood to refer to the inverse discrete cosine transform, the application as filed uses the term synonymously with "discrete cosine transform"; see page 1, lines 17 to 19, "consider the function of performing a discrete cosine transform (IDCT) ...". Moreover, original claim 6 refers to the computation of component coefficients of a vector transformation "such as an IDCT or DCT". Since the skilled person is aware that the two computations involve essentially identical operations, the Board considers that the application discloses the application of the INS2 instruction to both.

3.3 It follows that the sole request complies with Article 123(2) EPC.

4. Clarity

Since the clarity objections raised in its communication no longer apply to claim 1 of the sole request, the Board is satisfied that the sole request complies with Article 84 EPC.

5. Inventive step

5.1 According to the description on page 7, lines 25 to 29, the data-flow diagram of Figure 2 is based on document D10. In its communication, the Board suggested that the subject-matter of claim 1 of the then second auxiliary request, on which claim 1 of the present sole request is based, lacked inventive step over the disclosure of this document.

5.2 Document D10 discloses a number of DCT algorithms that are suitable for implementation in hardware (see abstract and section 6). In section 3 and Figure 1, it discloses an 8-point DCT algorithm with the following data-flow diagram:

FORMULA/TABLE/GRAPHIC

Document D10, on page 989, left-hand column, lines 8 to 11, explains that the four stages have to be executed in series and cannot be evaluated in parallel because of data dependencies, but that calculations inside one stage can be parallelised.

As stated on page 989, left-hand column, lines 32 to 35, the inverse DCT uses the same algorithmic structure as the DCT, but in reverse order, whereby outputs become inputs and vice versa. The Board notes that reversing the order of the four stages indeed leads to the data-flow diagram shown in Figure 2 of the present application.

5.3 The subject-matter of claim 1 differs from the disclosure of document D10 in that a data processing device is provided which is adapted to execute an instruction that performs the functionality of the top half of stage 2 in parallel. The effect of this difference is that the 8-point DCT/IDCT algorithm can be implemented more efficiently by means of processor instructions. (As explained in the application's description on page 14, lines 9 to 19, this advantage is already achieved if only one of the INS1 to INS7 instructions is provided for; the functionality of any missing instructions can then be implemented with conventional instructions.)

5.4 In the Board's judgment, the skilled person, starting from document D10 and faced with the problem of allowing an efficient implementation of the 8-point DCT/IDCT algorithm by means of processor instructions, is not prompted by document D10 to provide dedicated instructions implementing the functionality of individual stages or parts of stages. Although document D10 does focus on implementation aspects in that it states that the stages have to be executed in series and that the operations within each stage can be performed in parallel, the skilled reader would have in mind an implementation of the algorithm in the form of a hardware circuit. Moreover, none of the other documents on file discloses the required incentive.

5.5 Hence, starting from the disclosure of document D10, the skilled person would not arrive at the claimed invention without the exercise of inventive skill.

5.6 The Board has further considered the potential argument that the skilled person in the field of processor design, when given a specification of particular arbitrary desired functionality, would provide a processor supporting a dedicated instruction implementing precisely that functionality. However, in the present case, the functionality of the INS2 instruction is not arbitrary functionality, for which this argument could have worked (it would still have to be assessed whether the skilled person would come up with an SIMD-like instruction), but has been designed specifically to speed up DCT and IDCT computations.

5.7 As to the remaining cited documents, only documents D1, D4, D5, D8 and D8a relate to the use of SIMD instructions for performing DCT/IDCT computations. However, none of these documents specifically disclose or point to the INS2 instruction. In the Board's view, they do not represent more promising starting points for assessing inventive step than either document D10 or the common general knowledge of the skilled person in the field of processor design.

5.8 The subject-matter of claim 1 of the sole request hence involves an inventive step (Articles 52(1) and 56 EPC).

6. Since the sole request complies with the EPC, the appeal is to be allowed.

7. Request for reimbursement of the appeal fee

7.1 The appellant requested reimbursement of the appeal fee under Rule 103(1)(a) EPC in view of the delays in the first-instance proceedings. For this request to be allowable, it has to be established that the delays form a substantial procedural violation which renders reimbursement of the appeal fee equitable.

7.2 The Examining Division became responsible for the application's examination on 20 December 1999, the day on which the requests for entry into the regional phase and examination became effective (no supplementary European search report was to be drawn up in view of the decision under Article 157(3)(a) EPC 1973 of the Administrative Council of 21 December 1978, OJ EPO 1979, 4, Corr. 50). It then took more than 14 years until, on 7 February 2014, the Examining Division issued its first substantive communication under Article 94(3) EPC. After the appellant's reply by letter of 2 May 2014, it took a further 18 months for the Examining Division to issue its next action on 12 November 2015, which was a summons to oral proceedings. During these periods of delay, no procedural complications occurred that could have prevented the Examining Division from carrying out the substantive examination of the application.

7.3 In its decisions T 823/11 of 21 December 2015 and T 2707/16 of 11 December 2018, this Board held that unnecessary, excessive delays in the first-instance proceedings resulting in an unreasonable total duration of the grant proceedings may amount to a substantial procedural violation in view of both the applicant's and the public's legitimate interest in a speedy conclusion of the proceedings. In the present case, even though the Board has dealt with the appeal considerably out of turn, it is highly unlikely that the EPO will be able to publish the mention of the grant of a patent before the term of the patent expires. The delay of 14 years before the Examining Division issued its first substantive communication therefore has to be considered to be a substantial procedural violation.

7.4 The remaining question to be answered is whether reimbursement of the appeal fee is equitable in view of the circumstances of the case. In this respect, it was pointed out in decision T 2707/16, reasons 35, that the requirement that the procedural deficiency was causal for the necessity to appeal, which in the jurisprudence of the boards of appeal is often considered to be a necessary condition for reimbursement of the appeal fee to be equitable, does not in fact sufficiently take into account all possible circumstances in which reimbursement may be equitable.

7.5 In decision T 315/03 (published in abbreviated form in OJ EPO 2006, 15), the deciding board considered - in the context of requests for payment of costs to be met by the EPO in respect of a second oral proceedings before the Opposition Division - that reimbursement of the appeal fee in view of an unjustified delay in the opposition proceedings was not equitable because some of the parties had not appealed but would have had the same claim to some relief for the delay all parties had suffered, and because the appeal fee was a trivial sum compared with the gravity of the delay and the likely additional costs thereby incurred.

It is true that reimbursement of the appeal fee cannot be seen as a true compensation for the costs incurred as a result of delays in the proceedings. But, in the Board's view, reimbursement of the appeal fee may well be "equitable" even if it is not full compensation.

7.6 In case T 2707/16, reimbursement of the appeal fee was found not to be equitable because the applicant there had taken insufficient action to try to move the proceedings forward. In the present case, the appellant remained inactive for over 12 years before it requested accelerated examination. But the Examining Division then still did not succeed in issuing a communication within the period of six months to which it had committed; instead, it required close to two more years. And after the appellant had filed a timely reply, it again took more than 18 months - and a second request for accelerated examination, again leading the Examining Division to commit itself to a date it ultimately did not keep - before the Examining Division issued the summons to oral proceedings. The total delay therefore includes periods of unjustified delay that occurred despite the appellant's attempts to move the case forward. In these circumstances, the Board considers reimbursement of the appeal fee to be equitable.

Order

For these reasons it is decided that:

1. The decision under appeal is set aside.

2. The case is remitted to the department of first instance with the order to grant a patent on the basis of the following documents:

- Description: pages 1, 2, 2a and 3 to 15, as filed during the oral proceedings;

- Drawings: sheets 1/4 to 4/4, as filed during the oral proceedings;

- Claims: claim 1 of the new sole request, as filed during the oral proceedings.

3. The appeal fee is to be reimbursed.