T 1196/15 (Puncturing pattern/SAMSUNG ELECTRONICS) 18-10-2016

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

2. The application

2.1 The application relates to encoding and decoding of a channel signal in a communication system by means of Low-Density Parity-Check (LDPC) error-correcting codes.

2.2 The application seeks to support different code word lengths and different code rates on the basis of the parity-check matrices of LDPC codes defined in the Digital Video Broadcasting-Satellite transmission 2nd generation (DVB-S2) standard (see page 9, line 8, to page 10, line 16, of the description as filed). To this end, it proposes the use of "shortening" and "puncturing" techniques.

2.3 The claims are directed to a method and apparatus for decoding. They focus on the use of puncturing. According to this technique, the length of transmitted code words is reduced by not transmitting, i.e. "puncturing", the bits at certain bit positions of generated code words. In order for this to work, the decoder at the receiving side must know which bit positions were punctured by the encoder.

2.4 The description explains on page 16, line 21, to page 18, line 15, that the specific "puncturing pattern" chosen has an effect on the error-correcting capability of the punctured code. By making use of the structural characteristics of the DVB-S2 LDPC code when selecting a puncturing pattern, it is possible to provide "stable decoding performance by maximally suppressing the irregularity of the reliability of the information bits in the decoding process" (page 18, lines 12 to 15).

2.5 Two examples of puncturing patterns are given, one for the DVB-S2 code with parameters N1 = 16200, K1 = 3240 and q = 36 and one for the code with parameters N1 = 16200, K1 = 7200 and q = 25 (see Tables 1 and 2 on pages 23 to 25). They are based on permutations (of, respectively, 36 and 25 elements) which were selected on the basis of a "density evolution analysis" and a "cycle analysis" of the Tanner graph of the two LDPC codes (page 22, lines 5 to 9, and page 25, lines 8 to 11).

3. Third auxiliary request - added subject-matter

3.1 Claim 1 of the third auxiliary request is directed to a method of decoding punctured LDPC code words. The claim includes features defining the structure of a parity-check matrix for an LDPC code of length N1 and information length K1, and it lists the two specific puncturing patterns mentioned in point 2.52.5 above.

3.2 The features defining the structure of the parity-check matrix are based on page 4, line 10, to page 5, line 11, of the description of the application as filed. Figure 3 of the application depicts this structure schematically:

FORMULA/TABLE/GRAPHIC

The matrix includes an (N1-K1)-by-(N1-K1) parity part having a dual diagonal shape and an (N1-K1)-by-K1 information part consisting of K1/M1 groups of M1 columns (where M1 satisfies q = (N1-K1)/M1). The claim expresses the positions of 1s in the j**(th) column of a column group in terms of the positions of the 1s in the (j-1)**(th) column of the column group and, hence, ultimately in terms of the positions of the 1s in the 0**(th) column of each column group. These latter positions are not specified in the claim.

As the appellant explained in the statement of grounds of appeal, the positions of 1s in each 0**(th) column for the codes used in the DVB-S2 standard are found in Annex C of the standard specification (see document D7; Table C.1 for the code with parameters N1 = 16200, K1 = 3240 and q = 36; Table C.4 for the code with parameters N1 = 16200, K1 = 7200 and q = 25).

3.3 Claim 1 specifies two sets of values for the parameters N1, K1 and q, but makes no reference to the DVB-S2 standard. The class of LDPC matrices defined by claim 1 is thus not restricted to the two specific LDPC matrices corresponding to the two sets of parameter values defined in the DVB-S2 standard.

In its communication of 5 October 2016, the Board pointed out that the two specific puncturing patterns listed in the independent claims appeared to be disclosed in the application as filed only in combination with specific DVB-S2 codes.

3.4 At the oral proceedings before the Board, the appellant argued that it was clear from the application as a whole that what was important was the structure of the LDPC matrix. This structure was described on page 4, line 10, to page 5, line 11, and was not disclosed as being restricted to the specific codes used in the DVB-S2 standard. This was also true for the principles behind the puncturing patterns of the invention. Figure 6 of the application illustrated that a randomly chosen puncturing pattern could lead to an unnecessary performance degradation of the punctured code due to its irregularity. Figure 7 showed that a non-random puncturing pattern could lead to even more irregularity. In contrast, the puncturing pattern of Figure 8, which maintained a constant interval of 3 between punctured bits for a code with the structure of an DVB-S2 LDPC code and having 3 as value of the parameter q, led to a regular connection between information bits and punctured bits. As explained on page 18, lines 17 to 27, this regularity was due to the structure of the code. It was independent of the specific positions of the 1-bits in each of the 0**(th) columns.

The specific puncturing patterns claimed were disclosed in Tables 1 and 2 on pages 23 to 25 of the application. Although these tables gave values for "major variables of DVB-S2 LDPC code", this should be understood as referring not to the specific codes defined by the DVB-S2 standard having those parameter values but more generally to LDPC codes having a parity-check matrix structured like the DVB-S2 LDPC codes.

3.5 The Board agrees with the appellant that the skilled reader of the application as filed understands that the disclosed structure of LDPC matrices as discussed in point 3.2 above is not restricted to the specific LDPC codes defined in the DVB-S2 standard. It is also at least arguable that Figure 8 and its description on page 18, lines 17 to 27, which suggest that a puncturing pattern should maintain a constant interval linked to the value of the parameter q, are not tied to a specific DVB-S2 code.

However, the example of Figure 8 relates, in the wording of claim 1, to only a single "parity bit set". The two specific puncturing patterns listed in claim 1 each define an order in which 36 and 25 (i.e. q) parity bit sets are punctured in terms of two specific permutations pi(0), ..., pi(35) and pi(0), ..., pi(24) on 36 and 25 parity bit sets. The first permutation is mentioned on page 22, lines 11 and 12, and in Table 1 on pages 23 and 24 in the context of a detailed example described from page 21, line 20, to page 23, line 5. In this example, "The DVB-S2 LDPC code used [...] is a code with N1 = 16200, K1 = 3240, M1 = 360, and q = 36" (page 21, lines 21 and 22). The permutation for this code was "selected [...] using the connections between the punctured parity bits and the parity bits and the density evolution analysis method considering the case where the asymptotic performance is excellent" (page 22, lines 6 to 9). After listing the second permutation in Table 2 on pages 24 and 25, the application mentions that the invention "determines order of the punctured bits by using the density evolution analysis method and a cycle analysis method on the Tanner graph" (page 25, lines 8 to 11).

3.6 Although the skilled reader of the application does not learn exactly how "density evolution analysis" and "cycle analysis" methods were employed to arrive at the two permutations defining the two specific puncturing patterns, he is given the information that the two permutations were not randomly chosen. Rather, they were arrived at by methods that take into account "the Tanner graph", which is a graph representation of, and equivalent to, the parity-check matrix of an LDPC code (see page 2, lines 5 to 10, of the description). This is a clear indication that each of the two permutations is tied to a specific LDPC code, which can only be the DVB-S2 code having the corresponding parameters.

The skilled person would therefore understand the sentence "The DVB-S2 LDPC code used [...] is a code with N1 = 16200, K1 = 3240, M1 = 360, and q = 36" on page 21, lines 21 and 22, as indeed referring to the corresponding LDPC code defined in the DVB-S2 standard. The same applies to the other references to "DVB-S2 LDPC code" made in the application in connection with the two specific permutations (see Tables 1 and 2 and originally filed claims 3, 4, 6 and 7).

3.7 Hence, the Board concludes that the application as filed does not disclose the specific puncturing patterns listed in claim 1 in combination with a class of LDPC codes that is not restricted to the two specific codes defined in the DVB-S2 standard. The subject-matter of claim 1 of the third auxiliary request therefore does not meet the requirements of Article 123(2) EPC.

4. Fifth auxiliary request - added subject-matter

4.1 Claim 1 of the fifth auxiliary request essentially corresponds to a combination of independent claim 1 and dependent claims 3 and 4 as originally filed and includes an amendment based on page 28, lines 22 to 26, indicating that positions of punctured parity bits are determined on the basis of a demodulated received signal. The claim lists the same two specific puncturing patterns as claim 1 of the third auxiliary request, but now in combination with the corresponding LDPC codes defined in the DVB-S2 standard.

Thus the subject-matter of claim 1 is directly and unambiguously derivable from the application as filed.

4.2 Apparatus claim 2, computer program claim 3 and machine-readable storage claim 4 correspond to original claims 5, 8 and 9 adapted to present claim 1.

4.3 Hence, the fifth auxiliary request meets the requirements of Article 123(2) EPC.

5. Fifth auxiliary request - clarity

5.1 In its decision, the Examining Division deduced from the wording of method claim 1 of the then main request that "data [was] decoded with regard to ... bits sets which could possibly have been punctured". It stated that this "[seemed] to be an indirect attempt at putting a limitation on the subject-matter of claim 1 by citing features of the corresponding encoder". It was not clear which restrictions were placed on the decoding method "by this attempt".

The Board finds it difficult to understand what exactly was considered to be unclear about then claim 1 and, consequently, is unsure whether the objection the Examining Division had in mind might still be relevant to claim 1 of the fifth auxiliary request.

In any event, the Board notes that claim 1 is not defined in terms of features of an undefined encoder.

Claim 1 lists a number of decoding steps to be performed in a receiver in a communication system. The decoding steps are based on an LDPC code corresponding to one of two parity-check matrices defined in the DVB-S2 standard and on a precisely defined puncturing pattern. The relevant information from the DVB-S2 standard was available to the public before the priority date of the application, and the skilled person would have had no problem finding it.

According to the claim, the number Np of punctured bits is determined on the basis of the demodulated received signal. Once this number has been determined, the positions of the punctured bits are known from the applicable puncturing pattern. Knowing these positions, decoding of the received code words can be performed by "depuncturing" the punctured bit positions, i.e. by treating the punctured bits as erased. Puncturing and depuncturing are standard techniques in the field of error-correcting codes and need no further explanation in the claim or even in the description.

5.2 The Examining Division further stated that "whether bits have been punctured or not is not given" because "the number of punctured bits is not known to the encoder/encoding, and no corresponding input whatsoever is defined in claim 1". The number of punctured bits in claim 1 was "arbitrary".

The Board again cannot quite follow the Examining Division's argument. If a decoding method depunctures bits at, say, 5 bit positions, then that decoding method may be used to decode a signal encoded by a matching encoder that punctures bits at the same 5 bit positions. There is no need to clarify this in the claim as it is self-evident to the skilled person. Requiring the applicant to specify in some way that the decoding method or decoder is to be used in conjunction with a corresponding encoding method or encoder puncturing the same number of bits would serve no purpose and would not be relevant to Article 84 EPC.

Furthermore, if a claim to a decoding method or a decoder leaves open the number Np of punctured bits in a received code word, then that does not make the claim unclear either.

5.3 In its communication accompanying the summons to oral proceedings, the Board questioned whether claim 1 of the main request filed with the statement of grounds of appeal was supported by the description. The wording of the claim appeared to encompass, for each value of Np, a decoding method dealing with a predetermined number Np of punctured parity bits. The originally filed independent claims and various passages of the description, on the other hand, appeared to consistently present the decoding method as including a step or steps to the effect that the number of punctured parity bits was determined dynamically.

Claim 1 of the fifth auxiliary request includes features making clear that the number of punctured parity bits is determined on the basis of a demodulated received signal. The claim is thus limited to a method of decoding in a receiver having the ability to determine the number of punctured bits and to decode code words with that number of punctured bits. The requirement of support by the description is therefore fulfilled.

5.4 It follows that claim 1 meets the requirements of Article 84 EPC.

5.5 Apart from an obvious typographical mistake in corresponding apparatus claim 2 ("K1 - 7200" instead of "K1 = 7200"), claims 2 to 4 likewise cannot be objected to under Article 84 EPC.

6. Fifth auxiliary request - remittal

6.1 The decision under appeal contains objections of lack of novelty with respect to the then main request and, under the heading "Article 56 EPC", objections against the then auxiliary request. Since these objections rely on a reading of the then independent claims as not requiring a step of depuncturing, they do not apply to the fifth auxiliary request.

Indeed, as explained in point 5.3 above, independent claims 1 and 2 are now limited to a method of decoding in a receiver and to an apparatus for decoding which have the ability to determine the number of punctured bits and to decode code words with that number of punctured bits. The presence of this ability restricts the claimed subject-matter and is thus to be taken into account when assessing novelty and inventive step, regardless of whether the method and apparatus may also be used for decoding signals without punctured bits (or, for that matter, signals in which all parity bits were punctured).

6.2 In its communication accompanying the summons to oral proceedings, the Board observed that claim 1 of the main request filed with the statement of grounds of appeal essentially left open the parity-check matrix defining the LDPC code, the only implicit condition on such binary matrices being that they are "sparse". It appeared, however, that a particular choice of positions of punctured parity bits could only have technical relevance in terms of the reliability of the resulting punctured code in relation to the particular parity-check matrix used. In this respect, the Board noted that the description of the application as filed appeared to confirm that the determination of the positions of punctured bits as specified in the independent claims had been designed to make use of certain structural characteristics of the DVB-S2 LDPC codes (cf. point 2.42.4 above).

Since the claims of the fifth auxiliary request are restricted to two particular LDPC codes defined in the DVB-S2 standard, these concerns do not apply to them.

6.3 In its decision, the Examining Division did not discuss novelty and inventive step with respect to any of the documents cited in the European search report or introduced during the examination proceedings.

In the course of the written proceedings, the Examining Division cited document D1 as evidence of the existence of conventional methods of decoding punctured LDPC codes. Present claim 1, however, is limited to specific LDPC codes and specific puncturing patterns. The description of the application explains that the puncturing patterns were constructed to have improved decoding performance by making use of the structural characteristics of those LDPC codes. The Examining Division has not yet dealt with this aspect of the invention in relation to document D1.

When issuing its summons to oral proceedings, the Examining Division cited document D2 to show that "equidistant patterns are known" and referred to document D3 as "the true basis for the determination of the equidistant puncturing pattern in DVB-S2". However, neither document was discussed in any depth and no specific passages were cited.

6.4 In summary, a full examination of novelty and inventive step of the present application has not yet taken place. Although the appellant requested the Board to rule positively on inventive step because a remittal would result in a further delay and so be unfair to the appellant, the Board notes that the boards of appeal do not have the capacity of the examining divisions and that the interests of other appellants have to be taken into consideration as well. In the absence of particular circumstances, the Board is therefore reluctant to enter upon a full examination of novelty and inventive step in these appeal proceedings. Moreover, any further delay is mitigated at least to some extent by the fact that the Board has accelerated the prosecution of the present appeal of its own motion.

6.5 Hence, the Board will remit the case to the Examining Division for further prosecution on the basis of the fifth auxiliary request (Article 111(1) EPC).