T 1888/18 (Multi-symbol deinterleaver/QUALCOMM) 06-07-2021
Download and more information:
Efficient multi-symbol deinterleaver
Claims - clarity
Claims - all requests (no)
Reimbursement of appeal fee - full (no)
Reimbursement of appeal fee - partial (yes)
I. The appeal lies from the decision of the examining division to refuse European patent application No. 05724226.5, filed as international application PCT/US2005/006635 published as WO 2005/086358. The examining division decided that the subject-matter of claim 1 of a main request and a first auxiliary request was not clearly defined and lacked inventive step over the disclosure of the following document:
D6: US 2003/0225985 A1, published on 4 December 2003.
The other independent claims of the two requests were also considered to lack inventive step. A second auxiliary request was not admitted into the proceedings under Rule 137(3) EPC.
II. In the statement of grounds of appeal the appellant maintained all three requests considered in the appealed decision and requested reimbursement of the appeal fee. The appellant argued that the duration of the proceedings had to be considered excessive by any standards and amounted to a substantial procedural violation.
III. The appellant was invited to oral proceedings.
IV. With letter dated 14 April 2021, the appellant announced that it would not attend the oral proceedings and did not intend to file a response to the summons to oral proceedings. The appellant requested a decision according to the current status of the case.
V. In response to the appellant's letter, the board cancelled the oral proceedings.
VI. The appellant's final requests are thus that
- the decision under appeal be set aside and that a patent be granted on the basis of the main request or one of the first or second auxiliary request, and
- the appeal fee be reimbursed pursuant to Rule 103(1)(a) EPC.
VII. Claim 1 of the main request reads as follows:
"An apparatus (930), comprising:
means (1010) for mapping a first and second value to a plurality of third values; wherein the first and second values are In-phase, I, and Quadrature, Q, values, respectively, and the third values are soft decision values; and
means (1020; 1040) for simultaneously storing the plurality of third values in a plurality of memory banks (1030A-H) according to a storage pattern;
wherein the storage pattern (1050) comprises a plurality of cycles, each cycle indicating a selected subset of the plurality of memory banks (1030A-H) and an address offset value for each memory bank in the selected subset, each of the memory banks (1030A-H) in the selected subset for storing one of the plurality of third values, respectively; and further wherein the number of cycles in the storage pattern (1050) corresponds to a rate of encoding."
VIII. Claim 1 of the first auxiliary request reads as follows:
"An apparatus (930), comprising:
means (1010) for mapping a first and second value to a plurality of third values; wherein the first and second values are In-phase, I, and Quadrature, Q, values, respectively, and the third values are soft decision values; and
means (1020; 1040) for simultaneously storing the plurality of third values in a selected subset of a plurality of memory banks (1030A-H) using a base address for all memory banks and individual offset values for each memory bank according to a storage pattern;
wherein the storage pattern (1050) determines the selected subset of memory banks and the individual offset values; and further wherein the storage pattern is characterized by a plurality of cycles, each cycle selecting a different subset of the plurality of memory banks (1030A-H) and an individual offset value for each memory bank in the selected subset to be added to the base address, each of the memory banks (1030A-H) in the selected subset for storing one of the plurality of third values, respectively; and further wherein the number of cycles in the storage pattern (1050) corresponds to a rate of encoding;
wherein the means for mapping comprises a mapper and the means for simultaneously storing comprises a plurality of memory banks and a controller."
IX. Claim 1 of the second auxiliary request differs from claim 1 of the first auxiliary request in that the following text has been added at the end:
"wherein the number of cycles is six, and wherein: the first cycle indicates first, third, fifth, and seventh memory banks are selected, with an offset of zero; the second cycle indicates first, second, fifth, and sixth memory banks are selected, with respective offsets of one, zero, one, and zero; the third cycle indicates second, third, seventh, and eighth memory banks are selected, with respective offsets of one, zero, one, and zero; the fourth cycle indicates second, fourth, sixth, and eighth memory banks are selected, with an offset of one; the fifth cycle indicates first, second, fifth, and sixth memory banks are selected, with an offset of two; and the sixth cycle indicates second, third, seventh, and eighth memory banks are selected, with an offset of two."
X. The appellant's arguments, where relevant to this decision, are addressed in detail below.
Application
1. The application relates to a multi-symbol de-interleaver for a decoder, e.g. a turbo decoder, in a receiver of a mobile station, e.g, user equipment in a wireless communication system (see paragraphs [0001], [0009], [0030] and [0049], and Figures 1 and 9 of the international publication).
1.1 At the transmitter, as shown in Figure 3, data is encoded for instance by a turbo encoder according to the IS-856 specification at one of different code rates, e.g. 1/3 or 1/5. The turbo encoder receives the unencoded data bits U and generates parity bits V0 and V1 from the first encoder and V0' and V1' from the second encoder. Rate 1/3 encoding uses parity bits V0 and V0'; rate 1/5 encoding uses parity bits V0, V1, V0' and V1'. An interleaving matrix carries out interleaving. Code words UV0V0' and UV0V0'V1V1' are used for rate 1/3 and 1/5 codes respectively. The sequence of U of all information bits is permuted on its own. The V0 and V0' sequences are concatenated and permuted together, the same being done for the V1 and V1' sequences. The interleaved encoded data may optionally be punctured and is then modulated to format the data for transmission according to one of a variety of modulation formats, e.g. 16 QAM, 8 PSK or QPSK. For example, the modulator symbol is mapped onto a constellation to generate an In-phase (I) and Quadrature (Q) value. The output of the modulator is delivered to an RF up-converter for transmission via an antenna (paragraphs [0041] to [0046] and [0048]).
1.2 The receiver, as shown in Figure 9, includes an RF down-converter, a de-modulator (which generates an I, Q pair for each symbol it receives), a de-interleaver, and a decoder. The de-interleaver is depicted in Figure 10 and includes a mapper 1010, a symbol buffer 1020, a controller 1040 and multiplexers 1060 and 1070. The mapper receives the I,Q pairs from the de-modulator and calculates soft decision values, e.g. six-bit Log Likelihood Ratio (LLR) symbols. In one example, if 16 QAM is used, four LLR symbols will be generated from each mapped I, Q pair. The soft decision values (LLR symbols) are used in the decoder, following interleaving, to ultimately determine the most likely decoded data (paragraphs [0049] to [0053]).
1.3 The LLR symbols from the mapper are stored in the symbol buffer 1020 for de-interleaving. According to the description in paragraph [0052], all LLR symbols generated for each de-modulator output are stored simultaneously. The LLR symbols are stored in such a way that the symbol buffer may be read sequentially to provide a linear data stream for the decoder. In the example shown in Figure 10, four LLR symbols A, B, C, and D are generated by the mapper. The symbol buffer includes eight memory banks, four even and four odd banks. Multiplexers are used to select one of the symbols for storage in the respective memory bank. The memory banks are adapted to be written to simultaneously. Thus each of the four LLR symbols may be written to a memory bank during each clock cycle (paragraphs [0051] to [0056]).
1.4 The controller 1040 is used to select the address and memory bank which receives each LLR symbol in accordance with a storage pattern 1050 stored in a memory accessible by the controller. There may be storage patterns for different transmission formats, e.g. 16 QAM, 8 PSK, QPSK (1/3), QPSK (1/5). (paragraphs [0057] to [0063]).
1.5 A storage pattern establishes for each cycle a subset of memory banks for storage and corresponding offsets to be added to the base address within each memory bank. The number of cycles in a storage pattern corresponds to the rate of encoding and is twice the number of encoded symbols. For example, rate 1/3 codes generate three encoded symbols for each information symbol and utilize a six-cycle storage pattern. Example storage patterns are detailed in Tables 1 to 4 (paragraphs [0060] and [0061]).
Main request
2. Clarity and support - claim 1
2.1 In the decision under appeal, the examining division found that the term "cycle" and the phrase "the number of cycles in the storage pattern corresponds to a rate of encoding" were unclear.
2.1.1 In its statement of grounds of appeal the appellant argued that it was already clear from the claim wording alone that the pattern of storing data was realised in cycles, i.e. in storing steps occurring one after another, and it was clear that within a cycle the "third values", i.e. soft decision values of claim 1, were stored in certain memory banks. In addition, the expression "cycle" was explained several times in the description and in the prior art.
The appellant also argued that it was clear to the skilled person that the soft decision values to be stored were stored in agreement with the cycles, and that the number of cycles depended on the rate of encoding of the data values (e.g., rate 1/3 had six cycles or rate 1/5 had 10 cycles, as explained in paragraph [0060] of the description). As a result, the correspondence between the "rate of encoding" and the "number of cycles" was clear to the skilled person. Introducing the exact process of storing the data values in the memory banks into the claims would limit the claim to one specific example (e.g., 16QAM, 8PSK, QPSK(1/3), QPSK(1/5)) which was considered unnecessary and unduly limiting.
2.1.2 The board does not find these arguments convincing. The terms "cycle" and "corresponds to a rate of encoding" are vague in the context of the claim. Furthermore, the claim specifies that "the plurality of third values" are stored simultaneously. It is unclear why different cycles, each cycle for storing third values in selected subsets of the plurality of memory banks, are necessary if the (totality of the) plurality of third values are stored simultaneously, i.e. at a single point in time.
2.2 It is not clear from the claim what purpose is served by the claimed apparatus and, in particular, why the values are stored according to storage patterns in the memory banks. The general purpose of the invention is to perform de-interleaving for decoding, but the claim merely describes means for storing de-modulated values in memory banks according to a storage pattern in the context of encoding. In view of that, the claim is broader than justified by the description and unclear.
2.3 In addition, the claim does not define the essential features of the invention. The de-interleaver of the invention relies on storing the values according to a storage pattern in order to be efficiently read in a de-interleaved manner for decoding (paragraphs [0052], [0055] and [0058], original claims 33 and 34). For the purpose of de-interleaving for decoding, the way the values are read from the memory to be passed on to the decoder is as important as the storage pattern, but the claim does not specify such details, not even that the apparatus is used for de-interleaving in the context of decoding.
2.4 Therefore, claim 1 does not satisfy the requirements of Article 84 EPC.
First auxiliary request
3. Claim 1 of the first auxiliary request differs from claim 1 of the main request essentially in that it further specifies that
(a) the third values are simultaneously stored in a plurality of memory banks using a base address for all memory banks and individual offset values for each memory bank according to the storage pattern;
(b) the storage pattern determines also the individual offset values to be added to the base address;
(c) the means for mapping comprises a mapper and the means for simultaneously storing comprises a plurality of memory banks and a controller.
3.1 In the statement of grounds of appeal the appellant argued that the amended features attempted to define the storing process in more detail, so that the determination of the subsets was claimed in further detail. By the amendment, it became clear that each cycle selected a different subset and an individual offset in order to enable simultaneous storage of data in a cycle.
3.2 The board notes however that claim 1 of the first auxiliary request does not overcome the deficiencies listed above for the main request. The claim still refers to "simultaneously storing the plurality of third values", instead of specifying the simultaneous storage of third values in each cycle, and does not mention de-interleaving nor means for reading the values from the memory to be passed on to a decoder.
3.3 Therefore, claim 1 does not meet the requirements of Article 84 EPC.
Second auxiliary request
4. Claim 1 of the second auxiliary request differs from claim 1 of the first auxiliary request in that it further adds that the number of cycles is six and specifies which of the first to eighth memory banks and which offsets are used in each cycle (see section IX. above).
5. According to the appellant, claim 1 relates to the 16 QAM embodiment.
6. Admission into the proceedings
6.1 Pursuant to Article 12(4) RPBA 2007, the board has discretion not to admit requests which were not admitted in the first instance proceedings.
The examining division was of the opinion that the second auxiliary request, which was filed during the oral proceedings, prima facie did not overcome the objections raised against the higher ranking requests. In view of that, the examining division decided not to admit the second auxiliary request into the proceedings.
6.2 The appellant argued that the second auxiliary request should have been admitted by the examining division because it overcame the objections and because the applicant should have been given the possibility of presenting its arguments. In the statement of grounds of appeal the appellant provided arguments in support of the allowability of the second auxiliary request.
6.3 It is not apparent to the board that the examining division has exceeded the proper limit of its discretion. Since the claims of the second auxiliary request were filed at the oral proceedings, the request was clearly late filed and the examining division had the discretion for not admitting it taking into account a number of criteria including prima facie allowability of the claims.
In decision G 7/93 (OJ EPO 1994, 775), the Enlarged Board of Appeal ruled that a board of appeal should only overrule the way in which a department of first instance has exercised its discretion when deciding on a particular case if it concludes that it has done so according to the wrong principles, or without taking into account the right principles, or in an unreasonable way. However, as established by a number of decisions, in a situation in which a request had not been admitted into the first instance proceedings, a board nevertheless has to exercise its discretion under Article 12(4) RPBA 2007 independently (see T 971/11, reasons 1.2 and 1.3; T 2219/10, reasons 3.1 and 3.2; T 1816/11, reasons 2; Case Law of the Boards of Appeal, 9th edition, July 2019, IV.B.2.6.1), giving due consideration to the appellant's additional submissions and to any changes in the circumstances. In doing so, the board is not re-exercising the discretion of the department of first instance based on the case as it was presented then (T 971/11, reasons 1.2 and 1.3).
By analogy to the statement of T 971/11 with regard to the admission of documents (reasons 1.3), a set of claims submitted with the grounds of appeal which would have been admitted by the board if it had been filed for the first time at the outset of the appeal proceedings, should not be held inadmissible for the sole reason that it had been already filed before the department of first instance (and not admitted). A submission made with the statement of grounds of appeal should not be considered inadmissible if it is an appropriate and immediate reaction to developments in the previous proceedings and to the non-admission.
In the present case, one of the main reasons on which the examining division based its decision not to admit the second auxiliary request no longer holds because the request is not late filed in the appeal proceedings. The second auxiliary request has been submitted with the statement of grounds of appeal, i.e. at the earliest stage of the appeal proceedings. It is not fundamentally different from the originally filed claims and it further restricts the claimed subject-matter of the higher ranking requests. Therefore, there is no need to fully examine whether the examining division correctly exercised its discretion in not admitting the second auxiliary request, since in the exercise of its own discretion under Article 12(4) RPBA 2007 the board admits the second auxiliary request into the appeal proceedings.
7. Lack of clarity - claim 1
7.1 The second auxiliary request does not overcome all the objections raised above for the main request. Furthermore, it introduces new deficiencies as explained in the following.
7.2 Even if the claim is interpreted in the context of decoding, it is not clear how the storage pattern according to the features introduced by claim 1 of the second auxiliary request can be used for de-interleaving. According to those features, the symbol stored in the 3rd cycle, 2nd bank, offset 1, is overwritten with another symbol in the 4th cycle. Similarly, the symbol stored in the 1st cycle, 3rd bank, offset 0, is overwritten in the 3rd cycle. Since symbols are overwritten, the wrong symbols are passed on to the decoder.
7.3 In this regard, the board further notes that the description of the storage pattern according to claim 1 does not correspond exactly to the 16 QAM storage pattern of Table 1 (also illustrated in Figure 11) of the application, which is supposed to be the support in the description for the additional features. The correspondence between the memory banks designated in Table 1/Figure 11 and the first to eighth memory banks of claim 1 is as follows:
0A|0B|1A|1B|2A|2B|3A|3B|
1 |2 |3 |4 |5 |6 |7 |8 |
Taking that correspondence into account, the following table shows for comparison both the storage pattern defined by claim 1 and that of Table 1 (and Figure 11):
|claim 1memory banks|claim 1offsets|Table 1memory banks|Table 1offsets|
1st cycle|1 3 5 7 |0 0 0 0|0A 1A 2A 3A |0 0 0 0|
2nd cycle|1 2 5 6 |1 0 1 0|0B 0A 2B 2A |0 1 0 1|
3rd cycle|[deleted: 2](4) 3 7 8|[deleted: 1]0 [deleted: 0]1 1 0|1B 1A 3B 3A |0 1 0 1|
4th cycle|2 4 6 8 |1 1 1 1|0B 1B 2B 3B |1 1 1 1|
5th cycle|1 2 5 6 |2 2 2 2|0A 0B 2A 2B |2 2 2 2|
6th cycle|2 [deleted: 3](4) 7 8|2 2 2 2|1A 1B 3A 3B |2 2 2 2|
As the table shows, in the 3rd cycle the 2nd memory bank with offset 1 is specified in claim 1 instead of the 4th bank (1B) with offset 0 used in the storage pattern of Table 1 ("[deleted: 2](4)" means that claim 1 specifies the memory bank number 2, whereas the corresponding feature of Table 1 indicates the 4th memory bank 1B). Two other differences are present in the offsets of the 3rd cycle and the memory banks of the 6th cycle, as indicated in the table above. This raises not only an objection due to lack of clarity, as explained in point 7.2 above, but also one of lack of support by the description.
7.4 Therefore, claim 1 of the second auxiliary request infringes Article 84 EPC.
Concluding remarks and reimbursement of the appeal fee
8. In its statement of grounds of appeal the appellant submitted that the examination procedure in this case was tainted by a substantial procedural violation. The appellant requested reimbursement of the appeal fee in full pursuant to Rule 103(1)(a) EPC.
The appellant contended that the duration of the examination procedure from entry into the regional phase before the EPO to the decision to refuse took over eleven years. The appellant noted that the EPO had acted as International Search Authority in the present case and had required more than ten years to issue the first substantive communication after entry into the regional phase. A new prior-art document had been cited even though no amendments had been filed.
The appellant argued that this duration of the proceedings had to be considered excessive by any standards. In addition, it had the impression that the examining division had made a hasty attempt to conclude the examination, thereby violating both the high-quality standards of the EPO and the right of the applicant to a fair and economical procedure.
9. The appeal is not allowable in view of the above mentioned deficiencies and is therefore to be dismissed. In that case, the decision on whether a substantial procedural violation occurred does not have any procedural consequences and does not change the outcome of the appeal proceedings. In particular, the appeal fee cannot be reimbursed in full pursuant to Rule 103(1)(a) EPC.
In view of that, the board refrains from reviewing the appellant's allegations and from deciding on whether a procedural violation occurred.
10. The board notes however that the appellant's letter announcing that it would not attend the oral proceedings and requesting a decision according to the state of the file is equivalent to a withdrawal of any request for oral proceedings. Since the letter was sent before notification of a communication issued by the board of appeal in preparation for the oral proceedings, and no oral proceedings took place, the criteria are met for partial reimbursement of the appeal fee according to Rule 103(4)(c) EPC.
Order
For these reasons it is decided that:
1. The appeal is dismissed.
2. The request for reimbursement in full pursuant to Rule 103(1)(a) EPC is refused.