T 2341/13 (Interleaver/SAMSUNG) 31-05-2017
Download and more information:
Interleaving/deinterleaving device and method for communication system
Claims - clarity after amendment (yes)
Inventive step - after amendment (yes)
I. The applicant (appellant) appealed against the decision of the Examining Division refusing European patent application No. 99960006.7, published as international application WO 00/38333.
II. The Examining Division decided that the subject-matter of independent claims 1 and 4 of both the then main request and the then auxiliary request lacked inventive step over the following document:
D1: Clark G. et al.: "Error-Correction Coding for Digital Communications", Plenum Press, New York, 1981, pp. 349-352.
III. With the statement of grounds of appeal, the appellant submitted a main request and first and second auxiliary requests. The main request and the second auxiliary request were identical to the requests considered in the decision under appeal. The first auxiliary request corresponded to the main request with amendments for clarification.
IV. In a communication accompanying a summons to oral proceedings, the Board introduced the following documents:
D2: Chen C.: "Linear Dependencies in Linear Feedback Shift Registers", IEEE Transactions on Computers, Vol. C-35, No. 12, December 1986, pp. 1086-1088; and
D3: WO 96/24196, 8 August 1996.
It expressed the preliminary view that claim 1 of each request was unclear and lacked support in the description. In so far as claim 1 of the main request could be understood, its subject-matter appeared to lack inventive step over document D1. The features added to claim 1 of the first and second auxiliary requests appeared to be unsuitable to overcome that objection.
V. With a letter dated 28 April 2017, the appellant replaced its requests with an amended main request and an amended auxiliary request 1.
VI. In the course of oral proceedings held on 31 May 2017, the appellant replaced its requests with a sole substantive request filed at 16.15 hrs. At the end of the oral proceedings, the chairman pronounced the Board's decision.
VII. The appellant requested that the decision under appeal be set aside and that a patent be granted on the basis of the following documents:
- claims: claims 1 and 2 of the sole request, filed as main request at 16.15 hrs in the oral proceedings;
- description: pages 1 and 2 filed in the oral proceedings, and 3 to 17 of the international publication; and
- drawings: sheets 1/9 to 9/9 of the international publication.
VIII. Claim 1 of the sole substantive request reads as follows:
"A method for interleaving input data having a size of L symbols, comprising the steps of:
providing an interleaver memory (112), an address generator (121), a comparator (122) and a subtractor (124), said address generator having Ng Pseudo Noise (PN) generators (711,721) each including m shift register cells and corresponding to a respective address area of size 2**(m), with m>1;
wherein the size N of an address area is L + OSV = Ng×2**(m) by adding (811) an offset value, OSV, to the input data size L, the input data size L not being equal to Ng×2**(m);
providing OSV random addresses corresponding to random addresses defined by the address generator for the OSV addresses [L...N-1] and using those OSV random addresses as threshold values in the comparator;
sequentially storing the input data having a size of L symbols in said interleaver memory (112);
sequentially reading input data symbols from the interleaver memory in a sequence defined by random addresses generated by the address generator and shifted by corresponding specific values by means of the subtractor, each said reading step comprising:
generating by means of the address generator a random address;
identifying by means of the comparator for said random address how many of the threshold values are smaller than said current random address;
shifting said current random address by a specific value by subtracting by means of the subtractor, the number of threshold values, whose value is smaller than said current random address; and
reading a symbol of the stored input data from the interleaver memory using the random address as shifted by the subtractor;
repeating the reading step of input data from the interleaver memory L times."
Claim 2 reads as follows:
"A device for interleaving input data having a size of L, comprising an interleaver memory (112), an address generator (121), a comparator (122) and a subtractor (124), said address generator having Ng Pseudo Noise (PN) generators (711,721) each including m shift register cells and corresponding to a respective address area of size 2**(m), with m>1, said device being adapted to carry out the method according to claim 1."
1. The appeal complies with the provisions referred to in Rule 101 EPC and is therefore admissible.
2. The invention
2.1 The invention relates to the hardware implementation of an interleaver. The interleaver operates on a frame of input data and works essentially by first storing the input data sequentially in a memory and then reading the input data from the memory in an order defined by a mapping rule. To avoid having to store the mapping rule as a look-up table in a separate memory, circuitry is provided for generating read addresses as the input data is being read out.
2.2 The address-generation circuitry of the claimed invention is based on pseudo-noise (PN) generators. A PN generator may be implemented by means of a relatively simple linear-feedback shift register. It produces a pseudorandom sequence of addresses of length 2**(m)-1, where m is the number of shift-register cells of the PN generator. By combining a number of PN generators, shifting their outputs by multiples of 2**(m) and adding one further address per PN generator (as shown in Figure 7A), a "random address generator" is obtained that generates read addresses suitable for interleaving frames with a size divisible by 2**(m).
2.3 To allow the use of such a random address generator in a system where the frame size is not a multiple of 2**(m), the invention proposes adjusting the generated addresses by means of comparator and subtractor circuits as follows.
In a preparatory design phase, numbers OSV, Ng and m are determined, satisfying L + OSV = Ng×2**(m). By combining Ng PN generators, a random address generator is obtained that outputs N = Ng×2**(m) addresses, all in the range [0...N-1]. The last OSV addresses returned by this random address generator are determined and stored as "threshold values" in the comparator circuit.
Now, when reading an input data symbol from the interleaver memory, a random address is generated by the random address generator. The comparator compares the generated address with the threshold values and determines the number of threshold values smaller than the generated address. The subtractor then adjusts the generated address to obtain a "shifted" address by subtracting that number from the address. The resulting shifted address is guaranteed to be in the range [0...L-1]. And since the threshold values were selected to be those values that would have been generated when reading the (non-existing) L-th to (N-1)-th symbols, it is guaranteed that the first L shifted addresses contain no duplicates and cover the full range [0...L-1].
3. Added subject-matter - Article 123(2) EPC
3.1 Figures 6 and 7A and their description disclose an interleaver comprising random address generator 121, comparator 122 and subtractor 124. Random address generator 121 outputs random addresses generated by Ng PN generators 711 to 7N1 (page 11, lines 27 to 29). Each PN generator includes m shift-register cells (page 11, lines 3 and 4; Figure 7A) and corresponds to a respective address area of size 2**(m), with m>1 (page 13, lines 4 to 17; original claims 2 and 3). Random address generator 121 hence corresponds to an address area of size N = Ng×2**(m).
3.2 The interleaver is arranged to interleave an input data frame of size L, which is not a multiple of 2**(m) and satisfies L + OSV = Ng×2**(m) for an offset value OSV (page 6, lines 14 to 24; original claim 1). The passage on page 10, lines 8 to 25, discloses that threshold values are determined corresponding to the last OSV addresses from the N addresses generated by random address generator 121 (the passage assumes OSV to be equal to 8). These threshold values are used in comparator 122 (page 11, lines 29 to 32; Figure 6).
3.3 When an input data frame is received, the interleaver sequentially stores the L symbols of input data in interleaver memory 112 (page 7, lines 18 to 26; original claim 2). Next, the L symbols are read out in an order determined by addresses generated by random address generator 121 as "shifted" by comparator 122 and subtractor 124 (page 7, lines 26 to 29; page 9, line 35, to page 10, line 6; page 11, line 22, to page 12, line 4). In more detail, comparator 122 effectively counts the number of threshold values which are smaller than the address generated by random generator 122 (page 9, lines 15 to 25; page 10, lines 17 to 25; Figure 6), and subtractor 124 shifts the random address by subtracting that number (page 9, line 7; page 10, lines 22 to 25; page 12, lines 1 to 4; Figure 6). The symbol stored at the shifted random address is then read from interleaver memory 112 (page 12, lines 1 to 4).
3.4 Figure 6 and the passages on page 11, lines 32 to 35, and page 13, line 24 to 27, disclose that the comparator deletes an address generated by random address generator 121 if it is identical to one of the threshold values. However, since in the invention as claimed the threshold values were selected to be the last OSV values from the N addresses generated by random address generator 121, these threshold values are not among the first L generated addresses (see point 2.3 above). The delete function of the comparator therefore need not be included in the claim (cf. page 13, lines 30 to 34).
3.5 In view of the above, the Board is satisfied that the subject-matter of independent method claim 1 and the corresponding independent device claim 2 is directly and unambiguously derivable from the application as filed. The requirement of Article 123(2) EPC is therefore complied with.
4. Clarity and support - Article 84 EPC
The objections of lack of clarity and support raised in the Board's communication no longer apply to the present claims. The Board thus considers that Article 84 EPC is now complied with.
5. Inventive step - Article 56 EPC
5.1 The Examining Division refused the application for lack of inventive step over document D1. In its communication, the Board also drew attention to document D3.
5.2 Document D1 discloses a method for interleaving a frame of input data having a size of L, wherein input data is sequentially stored in a random access memory and then read out pseudorandomly (page 349, lines 7 to 11). The desired permutation may be stored in a read-only memory and then be used to address the interleaver memory (page 349, lines 11 to 13).
Document D1 discusses various techniques for generating suitable permutations. In particular, the use of a (maximal-length) linear-feedback shift register is suggested in the context of an interleaver where L = 2**(m) (page 351, lines 13 to 15 and 31 to 36).
5.3 Document D3 discloses an interleaver (see Figure 2 and page 5, line 28, to page 6, line 22; Figure 3 and page 7, lines 2 to 17) which uses a pseudorandom sequence either pre-stored in ROM or generated on the fly without utilising a ROM by means of, for example, a linear-feedback shift register (page 6, line 26, to page 7, line 1).
5.4 Neither document D1 nor document D3 addresses the problem of constructing, from a plurality of m-stage PN generators, an interleaver of low hardware complexity which is capable of interleaving input data frames with a size that is not a multiple of 2**(m). In particular, neither document hints at the solution as claimed.
5.5 In the oral proceedings before the Examining Division, it was repeatedly asked why the invention should use a frame size that was not a multiple of 2**(m). The Examining Division appears to have considered it problematic that the application suggests that the invention may be used in a communication system based on a standard that was neither publicly available at the priority date nor fully disclosed in the application.
The Board observes that knowledge of any communication standard is not necessary to carry out the claimed invention and that it is perfectly valid to pose the problem of obtaining interleavers for frame sizes that are not a multiple of 2**(m). If the claimed solution to this problem is not rendered obvious by the prior art, then an inventive step is present. Whether the application sufficiently discloses the advantages of such frame sizes is irrelevant, unless it is argued - unlike in the present case - that the mere idea of using such frame sizes is itself inventive (and may therefore not be included in the problem formulation). The Examining Division's concerns as expressed in the oral proceedings are therefore not justified.
5.6 None of the documents cited in the international search report and the supplementary European search report (all cited as "A" and none having been cited by the Examining Division) comes closer to the claimed invention than documents D1 and D3.
5.7 Document D2 was cited by the Board as evidence of common general knowledge about linear-feedback shift registers. It does not relate to interleavers.
5.8 Hence, the subject-matter of claim 1 and of corresponding claim 2 is not rendered obvious by the available prior art and thus involves an inventive step (Articles 52(1) and 56 EPC).
6. Since the application now complies with the requirements of the EPC, the appeal is to be allowed.
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:
- claims: claims 1 and 2 of the sole request, filed as main request at 16.15 hrs in the oral proceedings;
- description: pages 1 and 2 filed in the oral proceedings, and 3 to 17 of the international publication; and
- drawings: sheets 1/9 to 9/9 of the international publication.