T 1338/16 (Contention-free parallel LDPC decoder/SAMSUNG ELECTRONICS) 29-06-2020

1. Admissibility of the appeal

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

The invention

2. The application relates to decoding data received by a wireless communication device. The received data was coded before transmission using a low density parity check (LDPC) code, which is an error correcting code (description as published, paragraphs [0003] and [0004]).

It is well known that LDPC codes describe, by means of a sparse matrix H (i.e. a matrix in which most elements are zero), a set of parity checks. Using iterative belief propagation techniques, LDPC codes can be decoded in time linear to their block length. For the decoding the following equation has to be solved:

H*b**(T) = 0, wherein b represents the sequence of received code symbols.

3. The application proposes a receiver comprising, among other things, a plurality of decoders configured to perform an LDPC decoding operation, each decoder being configured to decode at least a portion of the received data simultaneously and to co-ordinate the decoding with other decoders.

Main request and auxiliary requests 1 to 3 - admission

4. Claim 1 according to the present main request and each of present auxiliary requests 1 to 3 differs from claim 1 according to the main request and each of auxiliary requests 1 to 3 as filed with the statement of grounds of appeal essentially in that it contains clarifications of the elements of the parity check matrix (in particular it was clarified that the sub-matrices have the same size).

4.1 In the oral proceedings, the appellant argued that these requests were filed to overcome objections under Articles 123(2) and 84 EPC raised by the Board in its communication pursuant to Article 15(1) RPBA 2020. Auxiliary request 4 also addressed the Board's objections concerning novelty and inventive step.

4.2 In view of the appellant's submissions, the Board considers that the amendments made in the main request and auxiliary requests 1 to 3 are primarily directed to overcoming objections raised by the Board in the communication under Article 15(1) RPBA 2020 in relation to added subject-matter, clarity and support, but prima facie do not overcome the Board's objections to patentability under Articles 54 and 56 EPC. Consequently, the Board exercises its discretion under Article 13(1) RPBA 2020 not to admit the main request and auxiliary requests 1 to 3 into the proceedings.

Auxiliary request 4

5. Admission

5.1 Auxiliary request 4 was filed after the oral proceedings had been arranged, and its admittance is thus subject to the Board's discretion on account of the stringent criteria set out in Article 13(2) RPBA 2020. Auxiliary request 4 adds a number of features to independent claim 1, which had not been present in the independent claims filed with the statement of grounds. Nevertheless, as auxiliary request 4 constitutes prima facie a legitimate attempt to overcome all the objections raised in the Board's communication under Article 15(1) RPBA 2020, and some of these objections were raised for the first time by the Board, the Board decides to exercise its discretion under Article 13(1) and (2) RPBA 2020 to admit auxiliary request 4 into the appeal proceedings.

6. Added subject-matter

6.1 Claim 1 of auxiliary request 4 comprises, among other things, the following amended features:

F1 wherein the at the least one zero matrix and the at least one shifted unit matrix have the same size

F2 wherein the columns of each of [the] rows [of] the decoding matrix are divided in groups, wherein the number of groups is equal at least to the number of columns of the decoding matrix divided by the number of the plurality of decoders; wherein each group is used in a different cycle of the decoding operation, wherein each of the plurality of decoders uses a different element of a corresponding group in a corresponding cycle; wherein the different element indicates in which memory bank a read/write access is performed in the corresponding cycle;

F3 wherein the decoding matrix has been preprocessed to avoid memory contentions by moving at least one element of a row in a group to the same row of another group, wherein the at least one element is identical to another element in the same row of the same group.

According to the appellant, feature F1 was based on paragraph [63] of the description, and features F2 and F3 were based on Figures 20 and 21 and the corresponding description, paragraphs [145] to [152].

6.2 Feature F1 does not exclude that zero matrices having a non-quadratic form (i.e. the number of rows differs from the number of columns) can be used to compose the parity check matrix. This feature appears to have no basis in the passage of the description cited by the appellant, as paragraph [0063] explains that the H-matrices used by the invention are composed of ZxZ sub-matrices, i.e. all sub-matrices have the same size and the same number of rows and columns. The Board is not aware of any other passage of the application as filed that supports the broader wording of claim 1 according to auxiliary request 4, which encompasses sub-matrices of non-quadratic form. Consequently, claim 1 comprises added subject-matter.

6.3 Feature F2 specifies that "the different element indicates in which memory bank a read/write access is performed in the corresponding cycle". Feature F3 refers to avoiding memory contentions. According to the appellant, features F2 and F3 were in particular based on the description, paragraphs [149] and [150].

However, as argued in the oral proceedings, the Board considers that the embodiment disclosed in the cited passages relates to the memory array illustrated in Figure 9, as the reference signs used in paragraph [146], which describes the same embodiment as paragraphs [149] and [150], refer to Figure 9.

Moreover, as indicated in the oral proceedings before the Board, the matrices shown in Figures 20 and 21, which were also cited as a basis for features F2 and F3, are modulo 24 representations of the parity check matrix used in the cited embodiment. The memory array according to Figure 9 uses 24 memory units having 8 memory banks. Hence, the Board considers that the skilled person reading the description would directly and unambiguously derive that the elements shown in Figures 20 and 21 indicated in which memory unit a read/write access was performed. In view of this, feature F2, which specifies that an element indicates the accessed memory bank, appears to have no basis in the application as filed, even though the Board acknowledges that paragraph [149] of the description refers to a memory bank. However, this is inconsistent with the whole technical content of the application as filed, and the skilled person reading paragraph [149] would recognise the reference to a memory bank as an inconsistency in the application.

Feature F3 refers to memory contention, but claim 1 does not further define why accessing the same memory unit within a cycle results in memory contention. As explained in the oral proceedings, the embodiment disclosed in the description, paragraphs [145] to [152], and Figures 20 and 21, refers to the memory array illustrated in Figure 9 and further described in paragraph [101] of the description. As disclosed in the cited passage, data cannot be simultaneously accessed in two memory banks in the same memory unit. However, claim 1 is entirely silent on what kinds of memory conflicts are addressed. Hence, it appears that the subject-matter of claim 1 is not directly and unambiguously derivable from the content of the application as filed.

6.4 Consequently, claim 1 according to auxiliary request 4 does not comply with Article 123(2) EPC.

7. Clarity

7.1 Feature F2 specifies that "the number of groups is equal at least to the number of columns of the decoding matrix divided by the number of the plurality of decoders". In the oral proceedings, the Board raised the objection that the wording "equal at least" was unclear and not supported by the description, as the embodiment disclosed in paragraphs [145] to [152] provided the example that a matrix having 22 columns was grouped into 6 groups of columns for processing by 4 decoders. Hence, the number of groups was equal to the integer obtained by rounding up the number of columns of the decoding matrix divided by the number of the plurality of decoders. The appellant agreed that the Board's interpretation in the light of the description corresponded to the intended meaning of feature F2.

7.2 In the oral proceedings, the Board also raised the objection that the wording "each of the plurality of decoders uses a different element of a corresponding group in a corresponding cycle" in feature F2 was unclear, as it could not be understood what was meant by "a corresponding group in a corresponding cycle". The appellant did not argue against this objection.

7.3 In view of the above, the Board concludes that claim 1 of auxiliary request 4 does not meet the requirements of Article 84 EPC.

Auxiliary request 5

8. Admission

8.1 Auxiliary request 5 was filed during the oral proceedings and introduces amendments to clarify that the elements of the parity check matrix are square matrices, how the elements of the columns in a given row of the parity check matrix are grouped and processed in parallel, how the decoding matrix was preprocessed and that memory contention is caused by simultaneous access to the same memory unit.

As these clarifications and amendments raise no new issues, can be regarded as a legitimate reaction to the objections under Articles 84 and 123(2) EPC raised by the Board for the first time in the oral proceedings, and prima facie overcome such objections, the Board finds it appropriate to admit auxiliary request 5 into the proceedings under Article 13(1) and (2) RPBA 2020.

9. Clarity and amendments

9.1 The Board agrees with the appellant that the amendments to claim 1 are based on the embodiment disclosed in Figures 9, 20 and 21 and the description (for example, paragraphs [63], [101] and [145] to [152]). Claim 6 essentially corresponds to claim 1 in terms of method. Hence, claims 1 and 6 of auxiliary request 5 comply with Article 123(2) EPC.

9.2 The Board is satisfied that the clarifications made to the claims according to auxiliary request 5 overcome the clarity issues it had raised. In particular, the sub-matrices are limited to square matrices, the problematic wording in feature F2 (see the discussion of auxiliary request 4 above) has been clarified and the claims set out clearly when memory contentions arise. Furthermore, the Board is not aware of any clarity issue for the dependent claims. Consequently, the Board is satisfied that the claims of auxiliary request 5 meet the requirements of Article 84 EPC.

10. Novelty and inventive step

10.1 Document D3 as starting point

In the contested decision, the Examining Division considered document D3 as the starting point for assessing inventive step of the subject-matter of the then auxiliary request, which was also directed to avoiding memory contention. For the same reasons, the Board considers this document as a suitable starting point for assessing inventive step of auxiliary request 5. This was not contested by the appellant.

10.1.1 Document D3 discloses a decoding method and apparatus using low density parity check (LDPC) codes. According to Figure 2A of D3 (description, page 8, line 24, to page 9, line 20), a transmitter performs communication with a receiver through a wireless channel. In the transmitter, k-bit source data output from a data source is LDPC-encoded into an n-bit codeword through an LDPC encoder and transmitted through an antenna. The receiver receives the data over a wireless channel through an antenna. The received data is then LDPC-decoded into source data through an LDPC decoder.

Figure 3 of D3 discloses that the parity check matrix H is composed of a number of permutation matrices or a zero matrix of dimension ZxZ, as the matrix elements Pi,j in Figure 3 denote a permutation or zero matrix of dimension ZxZ (D3, page 10, lines 6 to 10). D3 explains in Figure 4 and the description (page 10, line 11, to page 11, line 23) that each permutation matrix can be obtained by shifting an identity matrix. Document D3 discloses exemplary H-matrices in Figures 5A to 5F (see description, page 15, lines 11 to 18).

10.1.2 Figure 16 of document D3 discloses an LDPC decoder with a memory block including an "R-memory", a "received Log Likelihood Ratio (LLR) memory" and a "Q-memory". The received LLR memory stores, for example, LLR values of a codeword of a received signal. The R-memory stores results of a likelihood value update at a specific check node, and the Q-memory stores results of a likelihood value update at a specific variable node (Figure 16 and description, page 31, lines 18 to 25, and page 32, lines 4 to 10).

10.1.3 Document D3 further discloses in Figure 16 a decoder comprising a Variable Node update Unit (VNU) block and a Check Node update Unit (CNU) block. The CNU block performs updating of the likelihood values of check nodes (i.e. performs check node update) and includes at least one CNU, i.e. a processing unit for performing a check node update. The VNU block performs updating of the likelihood values of variable nodes (i.e. performs variable node update) and includes at least one VNU for performing a variable node update. The CNUs and the VNUs are controlled by a control block to calculate and update likelihood values of non-zero elements of the matrix H. In particular, the control unit controls the order of operation of the units and the operation timing of them. The control unit is connected to the CNU and VNU routing networks. Hence, the decoders are configured to "coordinate" the LDPC decoding with other decoders (see Figure 16 and the description, page 30, line 13, to page 31, line 18; page 32, lines 10 to 12). The respective numbers of the CNUs and the VNUs of the decoder are preferably determined by the structure of the parity check matrix. The number of the CNUs is preferably equal to the number of rows included in each of the so-called layers of the parity check matrix that are processed in parallel, and the number of the VNUs is preferably equal to the number of columns of the parity check matrix. For example, the number of the CNUs of the decoder that uses the parity check matrix defined in equation 6 on page 39 of the description of D3 is preferably 2, and the number of the VNUs is preferably 24 (description, page 39, line 10, to page 40, line 6; page 19, lines 12 to 17 and Figure 9).

10.1.4 It is uncontroversial that D3 does not disclose at least the following key features of claim 1 of auxiliary request 5:

F4 wherein [the] columns in each of the rows of the decoding matrix are divided in groups, wherein the number of groups is equal to a rounded up result of dividing the number of columns of the decoding matrix by the number of the plurality of decoders; wherein each group is used in a different cycle of the decoding operation; wherein in each cycle of the decoding operation elements of a group processed in said cycle are used by the plurality of decoders and each decoder of the plurality of decoders uses a different element than the other decoders of the plurality of decoders; wherein the different element indicates in which memory unit a read/write access is performed in the corresponding cycle;

F5 wherein the decoding matrix has been preprocessed to avoid memory contentions by moving at least one element of a row in a group to the same row of another group, wherein the at least one element was before the preprocessing identical to another element in the same row of the same group;

F6 wherein memory contentions happen when more than one decoder of the plurality of decoders simultaneously try to perform a read/write access to the same memory unit.

Consequently, the subject-matter of claim 1 of auxiliary request 5 is new over document D3 (Article 54 EPC). The same applies to independent claim 6 according to auxiliary request 5 which corresponds to claim 1 in terms of method, and to the further claims, by virtue of their dependency on independent claim 1 or 6.

10.1.5 In the oral proceedings, the appellant argued that compared to document D3, the distinguishing features F4 to F6 solved the problem of providing an alternative parallel LDPC decoder without memory contention. The Board accepts this formulation of the problem.

10.1.6 As to obviousness, the appellant argued in the oral proceedings that the kinds of memory contention were different when processing columns instead of rows in parallel. In addition, there were not only memory collisions but also dependencies when processing rows in parallel. Consequently, when starting from document D3, the skilled person could not arrive at the claimed solution without hindsight.

10.1.7 The Board agrees that the skilled person would not have arrived at the claimed solution involving features F4 to F6 in an obvious manner when starting from document D3. In the Board's view it would have been obvious for the skilled person to consider parallel processing of columns, as this was well known at the relevant date (see for example document D4, paragraphs [0130] to [0137]). However, the particular solution claimed was not obvious; there is no pointer in either document D3 or the further prior art presently on file (i.e. documents D1, D2 and D4) to exchange elements of a row of the parity check matrix between different column groups to ensure that no memory contention arises within a given cycle of parallel decoding.

10.2 As to documents D1, D2 and D4, the Board considers that none of these documents addresses the issue of memory contention when performing LDPC decoding in parallel. Hence, these documents are clearly less promising as starting points compared to document D3 and cannot render the claimed invention obvious.

10.3 Consequently, the Board considers that the subject-matter of claim 1 according to auxiliary request 5 involves an inventive step over the prior art presently on file (Article 56 EPC). The same applies to independent claim 6 according to auxiliary request 5 which corresponds to claim 1 in terms of method, and to the further claims, which are inventive over the prior art presently on file by virtue of their dependency on independent claim 1 or 6.

Remittal to the Examining Division

11. In the present case, the issue arises whether the search was complete, as the subject-matter of claim 1 according to auxiliary request 5 has been limited to the embodiment disclosed in Figures 20 and 21 and the description, paragraphs [145] to [152], and comprises technical features that were not present in the claims searched. In particular, claim 16 as originally filed only specified that the decoding matrix was "preprocessed to avoid contentions", but the preprocessing itself was not further defined. Thus, the Board cannot establish how far this feature has been covered by the search, in particular regarding the details now claimed.

Under Article 111(1) EPC, the Board may either proceed further with the examination of the application, or remit the case to the department which was responsible for the decision under appeal for further prosecution. In addition, Article 11 RPBA 2020, which applies since the present appeal was pending on 1 January 2020 (Article 25(1) RPBA 2020), provides that the Board should not remit a case for further prosecution, unless special reasons present themselves for doing so. This provision should be read in conjunction with the principle that the primary object of appeal proceedings is to review the decision under appeal in a judicial manner (Article 12(2) RPBA 2020), not to conduct a complete examination of the application, including an additional search for relevant prior-art documents.

12. As the Board in the present case is not in a position to decide whether the scope of the search carried out by the responsible department of first instance also covered the subject-matter of claim 1 according to auxiliary request 5, special reasons within the meaning of Article 11 RPBA 2020 present themselves (see for example decision T 2496/17 of 6 May 2020, Reasons 6.4). It is therefore appropriate for the Board, in exercising its discretion under Article 111(1) EPC, to remit the case to the Examining Division for further prosecution on the basis of auxiliary request 5. In view of the above, the Board cannot arrive at a final conclusion on patentability for the present case as requested by the appellant in the oral proceedings.

Hence, the case is to be remitted to the Examining Division for further prosecution, in particular for considering whether an additional search needs to be carried out, for examination of the dependent claims with respect to the requirements of Article 123(2) EPC, and for adaptation of the description and the drawings.

Conclusion

13. In view of the above, the main request and auxiliary requests 1 to 3 are not admissible and auxiliary request 4 is not allowable. The independent claims of auxiliary request 5 satisfy the requirements of Articles 123(2) and 84 EPC and, at least in view of the prior art presently on file, i.e. documents D1 to D4, also the requirements of Articles 54 and 56 EPC. However, it still needs to be examined by the department of first instance whether the search is complete in relation to the subject-matter of auxiliary request 5, whether the dependent claims comply with Article 123(2) EPC, and whether the description and the drawings will require adaptation.