T 0254/06 () of 30.4.2009

Summary of Facts and Submissions

I. The applicant appealed against the decision of the examining division to refuse the European patent application No. 00 915 575.5.

II. In the contested decision, the examining division refused the application on the grounds that claim 1 was not supported by the description, Article 84 EPC, and that the same objection applied to (independent) claim 7 and all dependent claims.

III. Oral proceedings were held before the Board on 30 April 2009. The appellant requested that the decision under appeal be set aside and that a patent be granted on the basis of claims 1 to 14 filed with the letter dated 30 March 2009, or, as an auxiliary request, that the case be remitted to the department of first instance for further prosecution.

IV. Claim 1 as filed with the letter dated 30 March 2009 reads as follows:

"An interleaving/deinterleaving device comprising an address generator (111; 222, 223, 224) and an interleaver memory (212) wherein the device is adapted to generate L addresses, which are smaller in number than N = Ng x 2**(m) virtual addresses for reading data from said interleaver memory in which L data bits are stored, the device comprising:

said address generator (211; 222, 223, 224) including a plurality Ng of Pseudo Noise generators (211; 811, 822...8N1) each corresponding to an address generation area of size 2**(m) including m memories and generating address components for changing the sequence of the L data bits stored in the associated address generation area, wherein the device is further adapted to provide said N virtual addresses having a size of multiple Ng of 2**(m), with Ng and m as integers greater than 1, by using an offset value, OSV, stored in a look-up table, to be added to the data size L and said device further comprising a random address generator (221) adapted to generate random address components using a plurality of Pseudo Noise generators and a comparator (222) adapted to compare the random addresses output from the random address generator (221) with group thresholds, GTH, determined by the offset value and to delete the corresponding random address when one of them is identical to generate addresses other than addresses corresponding to the OSV, and

means for reading the input data from the interleaver memory (212) using the random addresses generated from the address generation areas, wherein Ng also denotes a group number corresponding to each address generation area and m also denotes an order of Pseudo Noise generator polynomial for the Ng Pseudo Noise generator."

V. The appellant argued essentially that the claims are supported by the description as required by Article 84 EPC. The appellant's arguments are discussed in more detail in the reasons which follow.

Reasons for the Decision

1. The appeal is admissible.

2. Problems and solutions disclosed

2.1 The description of the present application identifies a number of problems with prior art interleavers. One problem is that it is not practical to implement an interleaver for a large input frame size (l) because of the increased calculations and hardware complexity required (see page 2, lines 17 to 21 and page 3, lines 12 to 17 of the published specification WO-A-00/60750). A further problem is that most data input frame sizes (l) cannot be expressed in terms of a power of 2 (see page 6, lines 32 and 33).

2.2 According to page 6, lines 35 to 38, when the size L of the frame data to be interleaved cannot be expressed in terms of a power of 2, the proposed address generator adds an offset value OSV to the frame size L to make a virtual interleaving size N = L + OSV become a multiple of 2**(m). The multiple is referred to as the group number Ng. Then pseudo noise addresses are generated according to an area of size 2**(m) and selected sequentially or randomly to interleave the whole input frame (see page 7, lines 4 to 6). The pseudo noise addresses are generated by a plurality Ng of pseudo noise generators each including m memories (see page 4, lines 10 to 16, and page 11, lines 15 and 16). It seems that by dividing the virtual interleaver size into address areas and by using a plurality of pseudo noise generators the hardware complexity problem can be solved.

2.3 Additional unnecessary read addresses (invalid address) that are generated for the addresses added by the offset value can be excluded when the stored interleaved data bits are output (see page 7, lines 15 to 17, and page 10, lines 32 and 33). It seems that this enables efficient interleaving of data frame sizes that cannot be expressed as a multiple of 2**(m).

2.4 In the case of a specific interleaver (i.e. an interleaver for a specific data frame size), suitable values of group number Ng and exponent m can be determined through computer simulation and a search algorithm to optimally satisfy the interleaver properties (see page 7, lines 6 to 8).

3. Claim 1: Clarity and support by the description, Article 84 EPC

3.1 Present claim 1 specifies that "the device is adapted to generate L addresses, which are smaller in number than N = Ng x 2**(m) virtual addresses for reading data from said interleaver memory in which L data bits are stored". The board notes that in the contested decision the examining division reasoned that the definition "L addresses, which are smaller in number than N = Ng × 2**(m) virtual addresses" was meaningless because for any value of L, infinitely many combinations of m and Ng could be found, for which L is smaller than Ng × 2**(m). According to the examining division, claim 1 did not imply anything about optimal choices of m and Ng. Even when it was assumed that m>1, as was only defined in claim 7, then m=2 would be allowed, leading to improperly high values of Ng (which should be avoided; page 7, lines 21 to 28) for realistic values of L (at least several hundred bits, as in the disclosed examples). The examining division concluded that claim 1 was not supported by the description, contrary to Article 84 EPC.

The board considers that the present application does disclose interleaver device structures that are adapted to generate a number L of addresses which is smaller than a number N of virtual addresses that can be expressed as an integer multiple Ng of a power of 2 (i.e. N = Ng × 2**(m) where Ng and m are integers greater than 1). Specifically, in the embodiment of figures 7 and 8, a random address generator 221 sequentially stores addresses in an address buffer 817 (see figure 8). The addresses are generated using a plurality Ng of pseudo noise generators, numbered #0, #1 ... #Ng-2 and #Ng-1. Each pseudo noise generator generates an m bit output that is modified using a subtracter 818, multiplexer 813, comparator 814 and counter 815 and used to set the m low address bits of the address buffer 817 (see figure 8). This provides 2**(m) addresses. The high address bits of the address buffer 817 are set by the output of a counter 816 that sequentially selects from among the Ng pseudo noise generators. Hence the address buffer 817 is able to sequentially store Ng × 2**(m) addresses. This corresponds to the N virtual addresses specified in claim 1. Thereafter, a comparator 222, selector 223 and subtracter 224 are used (see figure 7) to delete addresses that are regarded as invalid addresses (see page 13, lines 1 to 6). The invalid addresses are unnecessary read addresses generated by an offset value (OSV) (see page 7, lines 15 to 17). Hence, the device as set out in the description is able to generate L addresses, which are smaller in number than N = Ng x 2**(m) virtual addresses.

It may indeed be true that claim 1 does not imply anything about optimal choices of m and Ng, but it is not a requirement of the European Patent Convention, and in particular not a requirement of Article 84 EPC, that the claims should specify the optimum way of carrying out the invention. Hence, the board sees no reason to object to the claimed feature that "the device is adapted to generate L addresses, which are smaller in number than N = Ng x 2**(m) virtual addresses for reading data from said interleaver memory in which L data bits are stored".

3.2 Notwithstanding the above, the board considers that claim 1 is not supported by the description for the following reasons.

3.3 According to claim 1, the address generator includes a plurality Ng of Pseudo Noise generators "each corresponding to an address generation area of size 2**(m)" and generates address components "for changing the sequence of the L data bits stored in the associated address generation area" (emphasis added). The board has doubts as to what is meant in the claim by an "address generation area" and has difficulty relating the feature to the disclosed embodiments. According to page 10, lines 20 to 30, addresses are generated "using a PN generator corresponding to its associated address generation area" and according to page 7, lines 2 to 6, "PN addresses are generated according to an area of size 2**(m)". Thus, it appears that the address generation areas relate in some way to the pseudo noise generators. However according to claim 1 and the description (see page 4, lines 8 to 10), the L data bits are stored not in the pseudo noise generators, but in the interleaver memory 212.

The appellant has argued that the address generation areas refer to the groups of valid read addresses [0, 8, 345], [4, ...], [67, 46] that are indicated in figure 4 as being separated by thresholds T1; T2; Tj. However the thresholds correspond to invalid addresses that are generated by the offset value OSV. Hence, the number of thresholds and the number of groups of valid addresses between them would be equal to the offset value OSV (see page 10, lines 11 to 18). The board does not find this explanation consistent with the statement that each pseudo noise generator corresponds to an address generation area of size 2**(m), which implies that the number of address generation areas would be equal to Ng.

3.4 According to claim 1, "the device is further adapted to provide said N virtual addresses having a size of multiple Ng of 2**(m), with Ng and m as integers greater than 1, by using an offset value, OSV, stored in a look-up table, to be added to the data size L" (emphasis added). The hardware structures disclosed in figures 7, 8 and 10 as embodiments of the interleaving device according to the invention include the interleaver memory, address generator, pseudo noise generators and comparator as specified in claim 1. Figures 7, 8 and 10 and the associated description do not however disclose a look-up table for storing an offset value and means for adding the offset value to the data size L. These claimed features are therefore not supported by the disclosed embodiments of the interleaving device.

The appellant has cited various passages of the description that refer to the address generator adding an offset value (OSV) to the frame size L (see: page 6, lines 35 to 38; page 7, lines 21 and 22; page 8, line 7; page 13, lines 13 to 21; and tables 1 and 2). However, the board sees these disclosures as referring to notional steps in the design of a particular interleaver, rather than features of the interleaving device per se. The board sees no clear indication in the passages cited that the interleaving device itself has means for adding an offset value that is stored in a look-up table.

3.5 Claim 1 specifies an interleaving/deinterleaving device comprising an "address generator (211; 222, 223, 224) including a plurality Ng of Pseudo Noise generators (211; 811, 822...8N1) ..." and it also specifies "said device further comprising a random address generator (221) adapted to generate random address components using a plurality of Pseudo Noise generators and a comparator (222) adapted to compare the random addresses output from the random address generator (221) with group thresholds...".

This wording implies that the interleaving device includes two sets of pseudo noise generators, one set in the "address generator" and one set in the "random address generator".

This is not supported by the described embodiment, in which the address generator 211 comprises the random address generator 221 and the comparator 222 (see figure 7), and the pseudo noise generators 811, 821, etc are features of the random address generator 221 (see figure 8).

3.6 Claim 1 refers to "address components", "random address components" and "random addresses" but does not use the terms consistently and does not make clear the distinction between them. A lack of clarity results.

4. For the reasons set out above, the board concludes that at least claim 1 as filed with the letter dated 30 March 2009 is not supported by the description in the sense of Article 84 EPC. As the ground for the refusal has not been overcome, it is not appropriate to remit the case to the department of first instance. The board is therefore not in a position to accede to the appellant's requests.

ORDER

For these reasons it is decided that:

The appeal is dismissed.