T 1198/15 (Multi-level LDPC coding/QUALCOMM) of 6.9.2019

Summary of Facts and Submissions

I. The appeal lies from the decision of the Examining Division to refuse European patent application No. 04715077.6, which was filed on 26 February 2004 as international application PCT/US2004/005783 published as WO 2004/077733 and claiming a priority date of 26 February 2003.

II. The present application was refused for lack of novelty in the subject-matter of the independent claims of the then second auxiliary request and of claim 1 of the then third, sixth and seventh auxiliary requests over a prior-art document D2 not identified in the decision. The main request and first, fourth and fifth auxiliary requests were not admitted into the proceedings under Rule 137(3) EPC. The decision under appeal also refers to a document D1 and to patent document US 2003/0023917.

Documents D1 and D2 were cited by the Examining Division in its communication accompanying the summons to oral proceedings. Accordingly, in this decision the Board cites the following documents:

D1: R. M. Tanner, "On Quasi-Cyclic Repeat-Accumulate Codes", 37th Allerton Conference on Communication, Control and Computing, Monticello, Illinois, USA, pages 249 to 259, 22 to 24 September 1999;

D2: M. M. Mansour, N. R. Shanbhag, "Low-Power VLSI Decoder Architectures for LDPC Codes", Proceedings of the International Symposium on Low Power Electronics and Design ISLPED'02, pages 284 to 289, Monterey, California, USA, 12 to 14 August 2002;

D3: US 2003/0023917 A1, published on 30 January 2003.

In the decision under appeal, the Examining Division expressed the view that the permutation matrices and other features of the invention were known from document D1 (see points 1.1 and 2.1). It also stated that document D3 disclosed the subject-matter of claim 1 of the second auxiliary request.

III. In the statement of grounds of appeal, the appellant requested that the decision under appeal be set aside and that a patent be granted on the basis of the claims of the main or the auxiliary request, both requests submitted with the grounds of appeal. The main request was based on the main request not admitted by the Examining Division and the auxiliary request was based on the second auxiliary request considered in the decision under appeal.

IV. In a communication accompanying a summons to oral proceedings, the Board cited additionally the following documents:

D4: US 2004/0153938 A1, published on 5 August 2004;

D5: US 2004/0153934 A1, published on 5 August 2004;

D6: Okamura, T.: "Designing LDPC Codes Using Cyclic Shifts", IEEE International Symposium on Information Theory, ISIT 2003, Yokohama, Japan, 29 June to 4 July 2003.

Documents D4 and D5 are post-published documents cited in the supplementary European search report. Document D6 was introduced by the Board into the proceedings.

The Board was of the preliminary opinion that claim 1 of both requests did not fulfill the requirements of Article 84 EPC because they did not clearly define two features. It expressed doubts that the invention was sufficiently disclosed (Article 83 EPC).

The Board did not maintain the grounds for refusal based on lack of novelty. The subject-matter of claim 1 was new over document D2. None of the other documents cited in the first-instance proceedings seemed relevant for the question of novelty. The two patent applications D4 and D5 cited as E documents in the supplementary European search report did not constitute prior art with regard to the present application.

The Board further found that the question of inventive step had not been dealt with in substance by the Examining Division and that the novelty analysis of the decision under appeal could not serve as a basis for an inventive-step argumentation. Document D6 seemed relevant and would form part of the state of the art if the priority of the present application were found to be invalid.

The Board was therefore inclined, if other outstanding objections were overcome, especially under Articles 83 and 84 EPC, to remit the case for further prosecution.

V. With a letter of reply, the appellant filed two new sets of claims as revised main and revised auxiliary requests to be considered as further auxiliary requests.

In a second letter, the appellant informed the Board that it would not attend oral proceedings and clarified the requests on file. The appellant requested that the decision under appeal be set aside and that a patent be granted on the basis of the claims of the main request or, in the alternative, on the basis of one of the revised main request, auxiliary request, or revised auxiliary request. As a further auxiliary request, the appellant requested that the case be remitted to the first instance for further prosecution to deal with remaining issues like validity of the priority and novelty and inventive step over D6.

VI. Oral proceedings were held as scheduled in the absence of the appellant. At the end of the oral proceedings, the chairman pronounced the Board's decision.

VII. Claim 1 of the main request reads as follows:

"A device for performing an LDPC processing operation by employing a multi-level permutation, the device comprising:

a memory for storing a plurality of Z element vectors, each Z element vector includes Z elements wherein Z is an integer value greater than 1, each element including at least one bit to be processed;

a parallel LDPC processing module including Z processing elements arranged to perform parity check operations including one of encoding or decoding operations on Z vector elements in parallel; and

a controllable factorable permuter for coupling said memory to said parallel LDPC processing module that reorders the Z element vectors to facilitate processing of the Z element vectors by the Z processing elements, said controllable factorable permuter including switching circuitry, said switching circuitry being responsive to a control signal to perform a factorable permutation operation on a Z element vector being passed through said factorable permuter, said factorable permutation operation including first and second permutation operations which cause first and second re-orderings of vector elements to occur, said first and second reordering operations being performed on n equally sized vector portions of size Z/n, said first permutation operation causing a change in the order of at least two equally sized vector portions, said second permutation operation being performed on each of the Z/n sized portions to cause a change in the ordering of elements within each of said Z/n sized portions, where n is an integer greater than 1 and less than Z."

VIII. Claim 1 of the revised main request differs from claim 1 of the main request in that the following text was added at the end of the claim:

"; and

wherein the LPDC code being processed corresponds to a parity check matrix H that is composed of Z×Z matrices that are either zero or a Z×Z permutation matrix, and wherein the controllable factorable permute [sic] carries out permutation s [sic] corresponding to Z×Z permutation matrices."

Reasons for the Decision

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

The invention

2. The invention concerns the implementation of Low Density Parity Check (LDPC) coding allowing different levels of parallelism in the encoders and decoders using the same code. For instance, in a system with a base station serving four wireless terminals, the base station may have to encode and decode four times as much data as any of the individual wireless terminals. Using the invention, the base station can be implemented using more processing units operating in parallel than the individual wireless terminals serviced by the base station (see page 4, line 20, to page 5, line 19 of the international publication).

2.1 In order to support parallelism, bits to be encoded and/or bits corresponding to a received codeword are arranged into Z-element vectors, where Z is a positive integer greater than 1. Each Z-element vector is processed using Z processing elements in parallel (page 4, lines 20 to 29).

2.2 In this context, the application describes "lifting" or vectorisation of LDPC codes, in which each entry in the small parity-check matrix is replaced by a Z×Z matrix which is either the zero matrix or a Z×Z permutation matrix ("Z-lifting").

It then explains that "it is desirable to have a given code that can be viewed as a lifting not of just one size, but of two or more sizes thereby facilitating the possibility of different levels of parallelism in encoders/decoders using the same code" (page 5, lines 16 to 19; page 11, line 16, to page 12, line 22).

2.3 Claim 1 is directed to a parallel decoder/encoder with Z processor units operating in parallel on an LDPC code corresponding to a parity matrix H that can be viewed both as a Z-lifting and as a Z/n lifting. This is achieved by ensuring that each Z×Z permutation matrix represents a "factorable permutation" which can be factored into permutations of Z/n elements. This code is therefore also suitable for processing with Z/n parallel processing units.

2.4 The "factorable permutations" work as follows. In a first level of switching, elements are reordered within the vector being processed, e.g. by shifting n equally sized subsets of the elements in the vector using a first cyclic shift. In a second level, the elements of the processed vector are further permuted within the n equal sized portions but not between portions. The same second permutation is performed on each of the n equal sized portions resulting in the same change in element positions in each of the portions (page 8, lines 14 to 28).

2.5 A device for LDPC encoding or decoding according to the invention includes a Z-element parallel LDPC processing module, a factorable permuter, a memory, an address generator, an address generator and permuter controller and stored LDPC code (graph) information (Figures 7 and 8). While processing is ongoing, Z-element vectors are read from and written to memory taking into account LDPC code (graph) information and information about the level of parallelism Z which has been implemented. The factorable permuter is controlled to perform switching operations and vector element reordering, used to achieve a particular graph structure corresponding to the code being implemented (page 10, line 13, to page 11, line 14).

Main request

3. Article 84 EPC

3.1 Claim 1 does not clearly express that the LDPC code being processed corresponds to a parity matrix H that is composed of Z×Z matrices that are either the zero matrix or a Z×Z permutation matrix, and that the controllable factorable permuter carries out permutations corresponding to those Z×Z permutation matrices.

These are essential features of the device, without which the device of the invention does not produce a valid LDPC code. Both features are also necessary to understand the claimed subject-matter. Furthermore, without those two features the scope of claim 1 is broader than justified by the description.

3.2 With its reply to the Board's preliminary opinion the appellant did not contest the Board's objection against the omission of both features.

3.3 In the light of the foregoing, the Board concludes that the main request does not fulfil the requirements of Article 84 EPC.

4. Therefore, the main request is not allowable.

Revised main request

5. Articles 83 and 84 EPC

5.1 Claim 1 of the revised main request differs from claim 1 of the main request essentially in that the two features mentioned in point 3.1 above have been added (see also section VIII. above).

The objection under Article 84 EPC raised against the main request has thus been overcome by amendment.

5.2 Even though the title of point 2 of the decision under appeal mentions Article 84 EPC, the reasoning of the Examining Division does not include a substantiated clarity objection, and Article 84 EPC appears not to have been a ground for refusal. The Board does not agree with the contested decision's statement that the term "factorable permuter" of the claim is unclear. The claim clearly defines a factorable permutation as including first and second permutation operations which are further explained in the claim.

5.3 The Board is thus satisfied that claim 1 is clear and supported by the description in accordance with Article 84 EPC.

5.4 The Board also accepts that the skilled person would have been capable of carrying out the invention. A detailed architecture for parallel decoding of lifted LDPC codes is described in US 2003/0033575 A1, which was published before the present application's priority date on 26 February 2003 and which is referred to on page 12, lines 6 to 13, of the published application as US application S.N. 09/975,331. Parallel encoding of lifted codes is explained in the published application on page 16, line 9, to page 17, line 24. The requirements of Article 83 EPC are therefore met.

6. Article 123(2) EPC

6.1 Claim 1 of the revised main request differs from claim 1 as originally filed in that it additionally specifies the following features:

(a) "employing a multi-level permutation";

(b) "Z is an integer greater than 1";

(c) (Z processing elements arranged to) "perform parity check operations including one of encoding or decoding operations on Z vector elements";

(d) (a controllable factorable permuter) "that reorders the Z element vectors to facilitate processing of the Z element vectors by the Z processing elements";

(e) the two features added to claim 1 of the main request mentioned in section VIII. above.

6.2 Feature (a) is mentioned in the title of the application (see page 1, first two lines of the A2 publication) and is disclosed on page 8, lines 14 to 28, and page 13, lines 23 and 24.

6.3 Feature (b) is disclosed on page 4, lines 25 to 27.

6.4 The basis for feature (c) can be found on page 6, line 34, to page 7, line 17, and in original independent claim 10.

6.5 From the description on page 8, lines 14 to 28, and on page 9, lines 8 to 12, it can be directly and unambiguously derived that the controllable factorable permuter reorders the Z element vectors to facilitate processing of the Z element vectors by the Z processing elements. Feature (d) has therefore also a basis in the application as filed.

6.6 As described in the paragraph bridging pages 11 and 12 of the application as filed, the invention uses a process called Z-lifting whereby each entry of the parity-check matrix H is replaced with a Z×Z matrix. A zero entry of the parity-check matrix H is replaced with a zero Z×Z matrix, and a one entry is replaced with a Z×Z permutation matrix. Figure 5 shows the lifted version of the parity-check matrix of Figure 2. The factorable permuter carries out the permutations corresponding to the Z×Z permutation matrices (see also page 10, lines 24 to 31, Figures 7 and 8). Features (e) are hence also disclosed in the application as filed.

6.7 Therefore, claim 1 complies with Article 123(2) EPC.

7. Novelty - claim 1

7.1 In the novelty analysis of the decision under appeal, the Examining Division considered that the claimed device was anticipated by the decoder of Figure 1 of document D2, interpreted in light of other passages, especially of Figures 2, 3 and 9. The property "factorable" of the claim was unclear, and "a hardware implementation for routing LLR messages" according to the graph shown in Figure 2 corresponded to a "permuter". An "interconnection network" permuted "LLR messages". A switching circuit was implied in document D2. The feature defining the first and second reordering operations performed in n equally sized vector portions was not sufficiently defined to differentiate the claimed device from the prior art.

7.2 The lack-of-novelty reasoning of the contested decision is unconvincing. The decoder of Figure 1 of document D2 is based on the "Fully parallel decoder architecture" which has the problem that "the interconnection networks require complex wiring to perform global routing of messages and hence must be deeply pipelined" (see D2, page 284, right column). In the decoder of Figure 1 of D2 the parity-check matrix is not lifted.

Document D2 suggests improvements to that architecture based on an "approach for designing the codes, i.e., the matrix H, such that this interconnection complexity is minimized". That approach relies on partitioning "the parity check matrix H into blocks of p×p matrices, for some appropriately chosen p, such that each bit in a block participates in only one check equation in the block, and each check equation in the block involves only one bit from the block" (page 285, section 2.1, Figure 3). Those passages of document D2 disclose a permuter but not a multi-level permutation of the type defined in present claim 1.

7.3 With reference to Figure 5, document D2 also discloses a decoder architecture for a regular LDPC code which follows the above mentioned approach based on an "interconnect-driven code construction" (see sections 2.1 to 2.3). However, the device of Figure 5 of document D2 does not rely on the first and second re-orderings being performed on n equally sized vector portions of size Z/n as defined in the claim. Indeed, in section 2.1 the number p, which corresponds to Z, is a prime number (p = 31), and hence not suitable for supporting two levels of parallelism by multi-level permutation as in the current invention.

In sum, document D2 does not disclose a parity-check matrix H as claimed that allows interoperability with decoders/encoders using a different level of parallelism. The subject-matter of claim 1 is therefore novel over the disclosure of document D2.

7.4 In the decision under appeal, the Examining Division also mentioned that the subject-matter of claim 1 lacked novelty over document D3 (see page 7, fourth full paragraph, "It is not apparent what makes claim 1 even novel over this prior art US-2003-0023917"). However, the Examining Division cited only pages and figures not found in document D3. Furthermore, document D3 does not disclose any device similar to that of the present invention.

7.5 None of the other documents cited in the first-instance proceedings is relevant for the question of novelty. Document D1 is not about Z-lifting. The two documents D4 and D5 cited as E documents in the search report are US applications that were published after the filing date of the present application (26 February 2004). They are therefore not prior art for the present invention.

8. Inventive step - claim 1

8.1 The question of inventive step was not dealt with in the decision under appeal, and it was not dealt with in detail during the proceedings before the Examining Division.

As explained with regard to the novelty reasoning above, none of documents D1 to D3 discloses the parity-check matrix H of claim 1 or addresses the problem of supporting different levels of parallelism in the encoders and corresponding decoders. The subject-matter of claim 1 of the revised main request is therefore inventive over the prior art disclosed in documents D1, D2 and D3.

Further prosecution

9. Claim 1 of the revised main request satisfies the requirements of Articles 83, 84 and 123(2) EPC. The ground for refusal of the decision under appeal on the basis of lack of novelty is not maintained, and the subject-matter of claim 1 is inventive over the documents cited in the first-instance proceedings.

10. In the Board's communication pursuant to Article 15(1) RPBA, the Board introduced document D6 into the proceedings. Document D6 does not mention the problem of interoperability of encoders and decoders with different levels of parallelism, but it does appear to disclose an encoder based on a parity-check matrix H such as that of claim 1. However, document D6 forms part of the state of the art only if the priority of the present application is found to be invalid. Since the application is not identical to the priority application, it is not immediately clear whether the priority is valid.

11. Under these circumstances, the case is to be remitted to the Examining Division under Article 111(1) EPC for further prosecution on the basis of the revised main request, in particular for examining whether the priority of the present application is valid and, if not, whether the claimed subject-matter is novel and inventive over document D6.

12. In the further prosecution of the case, care should be taken to correct the typographical errors of the text of the claims (see section VIII. above).

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 for further prosecution.