T 1900/08 () of 19.4.2012

European Case Law Identifier: ECLI:EP:BA:2012:T190008.20120419
Date of decision: 19 April 2012
Case number: T 1900/08
Application number: 04255346.1
IPC class: H03M 13/11
H03M 13/29
Language of proceedings: EN
Distribution: D
Download and more information:
Decision text in EN (PDF, 50.446K)
Documentation of the appeal procedure can be found in the Register
Bibliographic information is available in: EN
Versions: Unpublished
Title of application: Method and apparatus for encoding short block length low density parity check (LPDC) codes for broadband satellite applications
Applicant name: DTVG LICENSING, INC
Opponent name: -
Board: 3.5.02
Headnote: -
Relevant legal provisions:
European Patent Convention Art 83
European Patent Convention Art 84
European Patent Convention Art 123(2)
Keywords: -
Catchwords:

-

Cited decisions:
-
Citing decisions:
-

Summary of Facts and Submissions

I. The appellant (applicant) appealed against the decision of the examining division refusing European application No. 04 255 346.1.

II. According to the contested decision, the examining division came to the conclusion that some amendments filed by the applicant did not comply with Article 123(2) EPC, that the subject-matter of the independent claims 1, 7 and 12 did not involve an inventive step (Article 56 EPC) and that the subject-matter of claim 12 was not clear (Article 84 EPC).

III. With the statement of grounds of appeal dated 5 September 2008, the appellant filed three new sets of claims by way of a main request and two auxiliary requests.

IV. With a letter dated 15 April 2011, the appellant filed a new set of claims by way of a third auxiliary request.

V. In a communication dated 6 May 2011 summoning the appellant to oral proceedings, the Board expressed the opinion that the application left several questions relating to the determination of the parity bits of short block length LDPC codes unanswered and thus did not appear to satisfy the requirements of Article 83 EPC. Furthermore, all requests appeared to offend against Article 123 (2) EPC.

VI. Following the Board's communication, the appellant filed, with a fax letter dated 14 October 2011, a further set of claims constituting a fourth auxiliary request and also drew the Board's attention to the following documents:

D5: USSN 10/613,824 (published as US-A1-2004/0153960)

D6: USSN 60/456,220 (corresponding to D7)

D7: European Patent Application no. 03763495.3.

VII. Oral proceedings before the Board were held as scheduled on 19 April 2012.

VIII. 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 filed with the letter dated 5 September 2008 or, in the alternative, the first or second auxiliary request, both filed with the letter dated 5 September 2008, or the third auxiliary request filed with the letter dated 15 April 2011 or the fourth auxiliary request filed with the fax letter dated 14 October 2011.

IX. Claim 1 according to the main request reads as follows:

"A method for supporting transmission of a Low Density Parity Check (LDPC) coded signal, comprising:

receiving blocks of information bits; and

generating, based on the information bits, a Low Density Parity Check (LDPC) code by accumulating information bits at parity bit addresses of parity bit accumulators specified in Tables 1 - 10 below: [see Tables 1 to 10 of the application]".

Claim 1 according to the auxiliary request 1 reads as follows:

"A method for supporting transmission of a Low Density Parity Check (LDPC) coded signal, comprising:

receiving blocks of information bits; and

generating, based on the information bits, a Low Density Parity Check (LDPC) code by accumulating information bits at a parity bit addresses of parity bit accumulators specified in Table 1 below, wherein parity bits, pi, are determined according to pi=pi+p1-l, i=1,2, ... nldpc - kldpc-1, kldpc being information block size and nldpc being codeword size: [see Table 1 of the application]".

Claim 1 according to the auxiliary request 2 reads as follows:

"A method for supporting transmission of a Low Density Parity Check (LDPC) coded signal, comprising:

receiving blocks of information bits; and

generating, based on the information bits, a Low Density Parity Check (LDPC) code by accumulating a first information bit at parity bit addresses of parity bit accumulators specified in Tables 1-7 below: [see Tables 1 to 7 of the application]".

Claim 1 according to the auxiliary request 3 reads as follows:

"A method for supporting transmission of a Low Density Parity Check (LDPC) coded signal, comprising:

encoding an input message into a codeword with a Low Density Parity Check (LDPC) encoder (203),

wherein the step of encoding comprises:

receiving information bits, i0, i1, … , im, … ,

i kldpc - 1;

initializing parity bits, p0 , p1 , … , pj, … ,

p nldpc - kldpc - 1; of a Low Density Parity Check (LDPC) code having a code rate of 1/2, 5/6, or 3/4 according to

p0 = p1 = … = p nldpc - kldpc - 1 = 0;

generating, based on the information bits, the parity bits by accumulating the information bits using parity bit accumulators, and subsequently performing the operation, starting with j = 1, pj = pj

FORMULA/TABLE/GRAPHIC

pj-1, for

j = 1, 2, …, nldpc - kldpc - 1; and

generating the codeword, c, of size nldpc as c = (i0, i1, … , i kldpc - 1, p0 , p1 , … , p nldpc - kldpc - 1 ) where pj, for j = 1, 2, …, nldpc - kldpc - 1, is final content of pj,

wherein addresses for the parity bit accumulators are specified based on one of Tables 1 to 10 below, wherein each of Tables 1 to 10 has a code rate that is specified by the Table, wherein nldpc is a codeword size equating to 16200, kldpc is an information block size equating to the code rate x nldpc , wherein Tables 1 to 10 are as follows: [see Tables 1 to 10 of the application]"

Claim 1 according to the auxiliary request 4 reads as follows:

"A method for supporting transmission of a Low Density Parity Check (LDPC) coded signal, comprising:

encoding an input message into a codeword with a Low Density Parity Check (LDPC) encoder (203),

wherein the step of encoding comprises:

receiving information bits, i0, i1, … , im, … ,

i kldpc - 1;

initializing parity bits, p0 , p1 , … , pj, … ,

p nldpc - kldpc - 1, of a Low Density Parity Check (LDPC) code having a code rate of 1/2, 5/6, or 3/4 according to

p0 = p1 = … = p nldpc - kldpc - 1 = 0;

generating, based on the information bits, the parity bits by accumulating the information bits using parity bit accumulators, and subsequently performing the operation, starting with j = 1, pj = pj

FORMULA/TABLE/GRAPHIC

pj-1, for

j = 1, 2, …, nldpc - kldpc - 1; and generating the codeword, c, of size nldpc as c = ( i0, i1, … , i kldpc - 1, p0 , p1 , … , p nldpc - kldpc - 1 ) where pj, for j = 1, 2, …, nldpc - kldpc - 1, is final content of pj,

wherein j is a parity bit address equal to {x + m mod 360 x q} mod (nldpc - kldpc), nldpc is a codeword size equating to 16200, kldpc is an information block size equating to the code rate multiplied by nldpc, m is an integer corresponding to a particular information bit, and x denotes a parity bit address, wherein each row of the following tables specifies addresses x for a particular one of the code rates of 1/2, 5/6, and 3/4 corresponding to a particular one of the tables, wherein q is specified in the following table for each one of the code rates of 1/2, 5/6, and 3/4, whereby each successive row of the corresponding table for the particular code rate provides all parity bit addresses j for the first information bit in each successive group of 360 information bits, and each successive row of the table provides all addresses x used in calculating parity bit addresses, j, for the next information bits according to {x + m mod 360 x q} mod (nldpc - kldpc) in each successive group of 360 information bits:- [see Tables 1, 4 and 6 of the application]."

All requests contain further independent claims relating to a "computer-readable medium", an "encoder" and a "transmitter". As they are not relevant to the decision, there is no need to give their wording.

X. The appellant's arguments may be summarized as follows:

Paragraph [40] on page 18 of the application incorporated by reference D5. In paragraph [0001] of D5, there was a further incorporation by reference to D6 which was available to the EPO at the filing date of the present application via European patent application D7. Subject-matter contained in D6 could therefore be incorporated into the present application and provided a basis for amendments. Moreover, the content of D6 represented a disclosure which the skilled person could rely upon for understanding how the invention could be put into effect.

Pages 3 and 4 of D6 described how, for successive groups of 360 information bits, the values in the successive rows of parity bit accumulator address tables were used to derive the parity bit addresses for all parity bits. Based on the incorporated disclosure of D6, the skilled person understood how the invention disclosed in the application and specified in the independent claims could be put into effect. Thus, the application satisfied the requirements of Article 83 EPC.

The distinguishing feature of the present invention was that a Low Density Parity Check (LDPC) code of a specific code rate was generated by accumulating bits at the parity bit addresses of parity bit accumulators specified in a corresponding table. The LDPC codes generated from the parity bits derived from the specified tables exhibited certain properties, such as high speed implementation without incurring performance loss or exhibiting any sign of error floor. Moreover, these LDPC codes allowed the use of a parallelizable decoding algorithm which advantageously permitted quick operations to be performed.

In summary, the problem to be solved by the invention was one of how to provide improved LDPC codes. This problem was essentially solved by accumulating information bits at the specific parity bit addresses of parity bit accumulators given in the tables recited in claims 1 and 7 of the main request and of the auxiliary requests 1 to 3. As the independent claims of the main request and of the auxiliary requests 1 to 3 clearly specified the essential features of the invention, they complied with Article 84 EPC.

Claims 1 and 7 of the auxiliary request 4 incorporated features from pages 4 and 5 of D6 which described how, for successive groups of 360 information bits, the values in the successive rows of parity bit accumulator address tables were used to derive parity bit addresses for all parity bits.

Reading the present application in the light of the background knowledge provided by D6, the skilled person would recognize the similarities with the teaching of D6 and realize that the invention effectively extended the teaching disclosed in D6 in connection with long block LDPC codes (64800 bits) to short block codes, i.e. codes having a codeword length of 16200. The skilled person would also realize that it was advantageous to process groups of 360 information bits so as to be able to utilize the same encoding and decoding hardware developed for long block codes. If, for a particular code rate, the block of information bits to be coded into a codeword did not divide exactly by the number of information bits in a group, it was evident to the skilled person that the remainder information bits would have to be processed together with the following information bits. Similarly, if the known expression for obtaining q did not result into an integer for a given code rate, a codeword length of 16200 bits and a group length of 360 bits, the skilled person would understand that the fractional results should be rounded up.

In summary, claim 1 of the auxiliary request 4 did not contain any subject-matter which extended beyond the content of the original application as interpreted by a skilled person who could rely on the common general knowledge to be expected in the field of LDPC codes. Hence, the auxiliary request 4 was in compliance with Article 123(2) EPC.

Reasons for the Decision

1. The appeal is admissible.

Article 83 EPC

2.1 An essential aspect of the present invention is the encoding of "short block length Low Density Parity Check (LDPC) codes" (see paragraph [06]).

As explained in paragraphs [32] and [33], "the task of the LDPC encoder 203 is to determine nldpc - kldpc parity bits [pi] for every block of kldpc information bits [ii]".

The procedure explained in paragraph [32] comprises the following steps:

(a) the parity bits are initialized by setting all pi to zero,

(b) the first information bit i0 is accumulated "at parity bit addresses specified in the first row of Tables 1-7".

After all of the information bits (in a block) are exhausted, the final parity bits are obtained as follows (see paragraph [35]):

(c) the operations pi = pi

FORMULA/TABLE/GRAPHIC

pi-1 (i = 1, 2, .... nldpc - kldpc - 1) are performed,

(d) the final content of pi is equal to the parity bit pi.

2.2 In view of the disclosure in paragraphs [32] and [33], a first question that springs to mind is how the bits following the first bit of a "block of kldpc information bits ii " are to be processed and in particular how the values specified in the table rows following the first row are to be used for determining all the parity bits of a block.

The answer cannot be found in other parts of the description, as they deal with different aspects of LDPC encoding and decoding.

2.3 As the application does not explicitly provide all the detailed information necessary to carry out the method of the invention, it is to be considered whether the present invention is disclosed in a manner sufficiently clear and complete for it to be carried out by a person skilled in the art, as required by Article 83 EPC.

2.4 The appellant has argued that the content of D6 represented a disclosure which the skilled person could rely upon for understanding the application, as D6 reflected the general knowledge to be expected from an expert in the field of LDPC coding. All more so as D6 was identified and incorporated by reference in D5 which paragraph [40] of the application explicitly incorporated.

3.1 According to the Case Law of the Boards of Appeal (6th edition, II.A.2a), page 230), patent specifications and scientific publications may, by way of exception, be considered to form part of the common general knowledge where the invention is in a field of research so new that the relevant knowledge is not yet available from textbooks. The Board agrees with the appellant that this may indeed be the case for the highly specialized and fast developing field of LDPC codes for broadband satellite applications to which the present application belongs.

3.2 In section 3. ("LDPC Encoder"), D6 describes, inter alia, an LDPC encoder for encoding an information block of size kldpc onto a codeword of size nldpc at code rates ranging from 1/2 to 9/10. In particular, D6 describes how information bits are divided into groups of 360 bits and how the values specified in tables relating to particular code rates should be used to define the addresses of the parity bit accumulators for all bits of every group of 360 information bits.

3.3 The Board agrees with the appellant that the skilled person would recognize the evident similarities between the encoding scheme of the present invention and the one disclosed in D6 and thus realize that the algorithm for determining the accumulator addresses of the information bits used in D6 should also be used for implementing the present invention.

Thus, relying on the detailed information provided in D6, the skilled person would be able to carry out the invention disclosed in the present application.

3.4 The Board is, therefore, satisfied that the application complies with Article 83 EPC.

Main request

4.1 Claim 1 of the main request relates to a "method for supporting transmission of a Low Density Parity Check (LDPC) coded signal" which comprises the following steps:

(i) receiving blocks of information bits; and

(ii) generating, based on the information bits, a Low Density Parity Check (LDPC) code by accumulating information bits at parity bit addresses of parity bit accumulators specified in Tables 1 - 10.

4.2 As pointed out above, the person skilled in the field of LDPC coding may be able to implement an LDPC code according to the invention on the basis of the information given in paragraphs [31] to [35] of the application once this information is complemented with the specialized background knowledge provided by D6. However, claim 1 is evidently not limited to such implementation of the invention but covers any method for generating an LDPC code by accumulating, in any conceivable way, information bits at the accumulator addresses specified in Tables 1 to 10.

Whilst some of these methods may indeed achieve the object of the present application, i.e. provide "expedient encoding as well as decoding of LDPC code, while minimizing processing resources" (cf. paragraph [06]), it is not plausible to assume that the whole range of encoding methods falling within the terms of claim 1 can achieve the objects enumerated in paragraphs [23] to [25] and thus constitute a solution to the technical problem addressed in the application.

4.3 As claim 1 leaves undefined some of the essential details of the method of the invention, it fails to identify in a clear manner the subject-matter for which protection may be legitimately sought. Hence, claim 1 does not satisfy the requirements of Article 84 EPC.

Auxiliary request 1 to 3

5.1 Claim 1 according to the auxiliary request 1 differs from claim 1 according to the main request in that the generating step reads as follows:

(ii') generating, based on the information bits, a Low Density Parity Check (LDPC) code by accumulating information bits at a parity bit addresses [sic] of parity bit accumulators specified in Table 1 below, wherein parity bits, pi, are determined according to pi = pi + pi-1, i = 1, 2, ..., nldpc - kldpc - 1, kldpc being information block size and nldpc being codeword size: [see Table 1 of the application].

5.2 The generating step (ii'') of claim 1 according to the auxiliary request 2 reads as follows:

(ii'') generating, based on the information bits, a Low Density Parity Check (LDPC) code including accumulating a first information bit at parity bit addresses of parity bit accumulators specified in Tables 1 - 7 below: [see Tables 1 to 7 of the application].

5.3 In claim 1 according to the auxiliary request 3, the steps of generating the parity bits of the LDPC code are essentially specified as follows:

- generating, based on the information bits, the parity bits by accumulating the information bits using parity bit accumulators, and subsequently performing the operation starting with j = 1,

pj = pj

FORMULA/TABLE/GRAPHIC

pj-1, for j = 1, 2, …, nldpc - kldpc - 1; and

- generating the codeword, c, of size nldpc as c = (i0, i1, … , i kldpc - 1, p0 , p1 , … , p nldpc - kldpc - 1) where pj, for j = 1, 2, …, nldpc - kldpc - 1, is final content of pj,

- wherein addresses for the parity bit accumulators are specified based on one of Tables 1 to 10 below,

- wherein each of Tables 1 to 10 has a code rate that is specified by the Table,

- wherein nldpc is a codeword size equating to 16200, kldpc is an information block size equating to the code rate x nldpc ,

- wherein the Tables 1 to 10 are as follows: [see Tables 1 to 10 of the application].

5.4 None of the above auxiliary requests specifies how, for all the information bits in an information block, the values in the successive rows of the tables should be used to derive parity bit addresses for all corresponding parity bits.

While the person skilled in the art relying on D6 may indeed arrive at a viable encoding scheme based on the corresponding algorithm for deriving the parity bit addresses of all the information bits in a block, as in the case of the main request, claims 1 according to the auxiliary requests 1 to 3 still fail to clearly define this essential feature of the invention.

5.5 Thus, for the same reasons given above (see item 4.2), claims 1 according to the auxiliary requests 1 to 3 do not comply with Article 84 EPC.

Auxiliary request 4

6.1 Claim 1 of the auxiliary request 4 specifies in detail the step of generating the parity bits and in particular the algorithm for calculating the parity bit addresses for the information bits following the first information bits. The method now claimed corresponds essentially to the method shown in D6 and differs from it only by the fact that a different codeword size, different tables and different q values are used.

6.2 The appellant has acknowledged that the step of generating the parity bits and the corresponding parameters now specified in claim 1 according to the auxiliary request 4 are not explicitly disclosed in the application as filed. According to the appellant, however, the skilled person would recognize in the light of the background knowledge provided by D6 that the present invention consisted essentially in realizing that the same coding scheme used for long block length LDPC codes could also be advantageously used for short block length codes and in providing corresponding tables for the parity bit addresses of the first bit of every group of 360 information bits.

6.3 The Board doubts whether specialized knowledge considered to be generally available to the skilled addressee of patent literature should necessarily be regarded as information implicitly disclosed in a patent application. Furthermore, it is also doubtful whether features taken from a document identified and "incorporated by reference" in another document which is "incorporated by reference" in an application may be used to delimit the subject-matter of the application's claims.

However, even under the assumption that the teaching of D6 forms part of the content of the application as originally filed, the question to be considered in the present case is whether the subject-matter of claim 1 and in particular the parameters specified in this claim are known or can be directly and unambiguously derived from D6.

7.1 Section 3 of D6 describes an LDPC encoder for encoding an information block of size kldpc onto a codeword of size nldpc. The code parameters kldpc and nldpc are given in Table 1. For the code rates 1/2, 3/4 and 5/6 the LDPC coded block length is 64800. As known in the art, q is obtained by dividing the number of parity bits in a codeword by the number of bits in a group of information bits. Thus, its values depend on the codeword length, the code rate and the length of successive groups of information bits, i.e. the "parallelism factor". In D6 the information bits are divided into groups of 360 bits and thus q = 90 for the code rate 1/2, q=45 for a code rate 3/4 and q=30 for the code rate 5/6. No values of q are given for a codeword size of 16200 bits.

7.2 It is evident from D6 that the code rate, the tables and the LDPC coded block length are chosen so that there are as many rows in a table as groups of information bits in a codeword and that the codeword size, the code rate and the "parallelism factor" M (i.e. the group size of 360 bits) are selected so that

q = (nldpc - kldpc)/M is an integer.

According to claim 1 of the auxiliary request 4, a codeword has a size nldpc = 16200 bits. The number of information bits obviously depends on the rate and is equal to 8100 for a code rate 1/2, to 13500 for a code rate 5/6 and to 12150 for a code rate 3/4. For none of the three coding rates covered by the claim the number of information bits divides evenly into groups of 360 information bits. Similarly, the expression for obtaining q, i. e. (n-k)/360, does not result in an integer.

7.3 The appellant has argued that the skilled person reading the application in the light of the disclosure in D6 would realize that, apart from requiring the new accumulator addresses specified in the tables of the invention, extending the teaching of D6 to short block length LDPC codes would imply a straightforward adaptation of some code parameters. The advantage of maintaining the same information group size of 360 bits was self-evident, as this parameter had a clear impact on hardware design. Thus, the skilled person would find it implicit to round up the values of q to the next integer and to continue the processing of the remainder information bits with the bits of the following codeword.

7.4 Although the code parameters specified in claim 1 can be regarded as a reasonable choice inspired by the wish to create short block length LDPC codes which follow as closely as possible the coding and decoding algorithms developed for long block size LDPC codes, it is evidently not the only choice available to the skilled person. As shown in Table 1 of D6, it is also known in the art to increase the length of the LDPC coded block nldpc, so as to be able to divide the corresponding number of information bits evenly into groups of 360 information bits. In fact, D6 explicitly teaches on page 3, top paragraph, to adapt the size of the LDPC coded block to the code rate in order to have parity check matrices with a periodicity of 360.

In other words, the Board considers that the combination of code parameters specified in claim 1 of the auxiliary request 4 cannot be regarded as a necessary consequence of the teaching of D6 applied to the short block length LDPC codes of the invention. Consequently, the subject-matter of claim 1 of the auxiliary request 4 cannot be directly and unambiguously derived from the original application in combination with D6.

7.5 In the result, the Board finds that, even if it were assumed that D6 was part of the disclosure of the application as originally filed, the subject-matter of claim 1 according to the auxiliary request 4 would extend beyond the content of the application as originally filed. Hence, the auxiliary request 4 is not in compliance with Article 123(2) EPC.

8. As none of the appellant's requests is allowable, the appeal has to be dismissed.

ORDER

For the above reasons it is decided that:

The appeal is dismissed.

Quick Navigation