T 0168/07 () of 11.2.2010

European Case Law Identifier: ECLI:EP:BA:2010:T016807.20100211
Date of decision: 11 February 2010
Case number: T 0168/07
Application number: 03763495.3
IPC class: H03M 13/00
Language of proceedings: EN
Distribution: D
Download and more information:
Decision text in EN (PDF, 81.446K)
Documentation of the appeal procedure can be found in the Register
Bibliographic information is available in: EN
Versions: Unpublished
Title of application: Bit-interleaved coded modulation using low density parity check (LPDC) codes
Applicant name: DTVG LICENSING, INC
Opponent name: -
Board: 3.5.02
Headnote: -
Relevant legal provisions:
European Patent Convention Art 111(1)
European Patent Convention Art 123(2)
Keywords: Added subject-matter - no (after amendment)
Remittal for further prosecution
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. 03 763 495.3.

II. In the contested decision, the examining division came to the conclusion that the subject-matter of claim 1 of the main request then on file was not novel over each of the following documents:

D2: S. Y. Le Goff, "Channel capacity of bit-interleaved coded modulation schemes using 8-ary signal constellations", Electronics Letters, Vol. 38, No. 4, 14th February 2002, pages 187 - 188;

D3: E. Eleftheriou et al., "Low-density parity-check codes for digital subscriber lines", Proc. IEEE International Conference on Communications, 2002, pages 1752-1757;

D4: R. Narayanaswami, "Coded modulation with low-density parity-check codes," M.S. thesis, Dept. Elect. Eng., Texas A&M Univ., College Station, TX, 2001;

D5: "Flarion Improves Speed for Data Communications and Multimedia Applications with Enhanced Forward Error-Correction Codes",

Flarion Technologies, Press Releases, February 19, 2002

(available online: http://www.flarion.com/news/pr_2002/021902.asp).

Furthermore, the subject-matter of claim 1 according to the auxiliary request then on file lacked an inventive step with respect to D5 and to the following document:

D7: R. Echard and S.-C. Chang, "The pi-rotation low-density parity-check codes", Global Telecommunications Conference, San Antonio, TX,

2001, November 2001, pp. 980-984.

III. With the statement of grounds of appeal dated 22 December 2006, the appellant filed a new set of claims constituting a Main Request and four sets of claims constituting Auxiliary Requests 1 to 4.

IV. In a communication dated 13. October 2009 accompanying the summons to attend oral proceedings, the Board expressed its preliminary view that the subject-matter of claim 1 according to the Main Request and to the Auxiliary Requests 1 to 4 appeared to cover subject-matter which was not sufficiently disclosed (Article 83 EPC). Furthermore, the Board drew the appellant's attention to the following document:

D8: C. Howland and A. Blanksby: "Parallel Decoding Architectures for Low Density Parity Check Codes", 2001 IEEE International Symposium on Circuits and Systems (ISCAS 2001), vol. 4, pages IV-742 to IV-745,

and concluded that the method of the invention as claimed did not appear to go beyond a straightforward application of the teaching of parallel decoding known from D8.

V. Oral proceedings before the Board were held as scheduled on 11 February 2010.

VI. The appellant requested that the decision under appeal be set aside and that a patent be granted on the basis of a claim as received during the oral proceedings.

VII. Claim 1 according to the appellant's request reads as follows:

"A method for processing signals, the method comprising:

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

transmitting the codeword as an encoded signal, wherein the encoded signal is modulated according to a non-sequential mapping of a plurality of bits corresponding to the codeword;

receiving the encoded signal;

demodulating the received Low Density Parity Check (LDPC) encoded signal representing the codeword; and

decoding the codeword associated with the encoded signal by performing bit node and check node processing on the demodulated signal, by accessing, from memory, values for edges of bit nodes and check nodes for groups of 360 bit nodes, wherein the values for the edges of each group are stored together in the memory;

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 2/3 according to p0 = p1 = ... = p nldpc - kldpc - 1 = 0;

generating, based on the information bits, the parity bits by accumulating the information bits by performing operations for each information bit, im, pj = pj

FORMULA/TABLE/GRAPHIC

im for each corresponding value of j, 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 64800, kldpc is an information block size equating to 43200 information bits, m is an integer corresponding to a particular information bit, q = 60, and x denotes a parity bit address, wherein each row of the following table specifies addresses x, whereby each successive row of the table 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:-

|0 10491 16043 506 12826 8065 8226 2767 240 18673 9279 10579 209|

|28 1 17819 8313 6433 6224 5120 5824 12812 17187 9940 13447 138|

|25 18483 2 17957 6024 8681 18628 12794 5915 14576 10970 12064 |

|20437 4455 7151 3 19777 6183 9972 14536 8182 17749 11341 5556 |

|4379 17434 15477 18532 4 4651 19689 1608 659 16707 14335 6143 |

|3058 14618 17894 20684 5306 5 9778 2552 12096 12369 15198 1689|

|0 4851 3109 1700 18725 1997 15882 6 486 6111 13743 11537 5591 |

|7433 15227 14145 1483 3887 17431 12430 7 20647 14311 11734 418|

|0 8110 5525 12141 15761 18661 18441 10569 8192 8 3791 14759 15|

|264 19918 10132 9062 10010 12786 10675 9682 19246 5454 9 19525|

| 9485 7777 19999 8378 9209 3163 20232 6690 16518 716 7353 10 4|

|588 6709 20202 10905 915 4317 11073 13576 16433 368 3508 21171 |

| 11 14072 4033 19959 12608 631 19494 14160 8249 10223 21504 123|

|95 4322 12 13800 14161 13 2948 9647 14 14693 16027 15 20506|

| 11082 16 1143 9020 17 13501 4014 18 1548 2190 19 12216 215|

|56 20 2095 19897 21 4189 7958 22 15940 10048 23 515 12614 |

|24 8501 8450 25 17595 16784 26 5913 8495 27 16394 10423 28 |

|7409 6981 29 6678 15939 30 20344 12987 31 2510 14588 32 179|

|18 6655 33 6703 19451 34 496 4217 35 7290 5766 36 10521 892|

|5 37 20379 11905 38 4090 5838 39 19082 17040 40 20233 12352|

| 41 19365 19546 42 6249 19030 43 11037 19193 44 19760 11772|

| 45 19644 7428 46 16076 3521 47 11779 21062 48 13062 9682 |

|49 8934 5217 50 11087 3319 51 18892 4356 52 7894 3898 53 59|

|63 4360 54 7346 11726 55 5182 5609 56 2412 17295 57 9845 20|

|494 58 6687 1864 59 20564 5216 0 18226 17207 1 9380 8266 2|

| 7073 3065 3 18252 13437 4 9161 15642 5 10714 10153 6 11585|

| 9078 7 5359 9418 8 9024 9515 9 1206 16354 10 14994 1102 1|

|1 9375 20796 12 15964 6027 13 14789 6452 14 8002 18591 15 1|

|4742 14089 16 253 3045 17 1274 19286 18 14777 2044 19 13920|

| 9900 20 452 7374 21 18206 9921 22 6131 5414 23 10077 9726 |

| 24 12045 5479 25 4322 7990 26 15616 5550 27 15561 10661 28|

| 20718 7387 29 2518 18804 30 8984 2600 31 6516 17909 32 111|

|48 98 33 20559 3704 34 7510 1569 35 16000 11692 36 9147 103|

|03 37 16650 191 38 15577 18685 39 17167 20917 40 4256 3391 |

| 41 20092 17219 42 9218 5056 43 18429 8472 44 12093 20753 4|

|5 16345 12748 46 16023 11095 47 5048 17595 48 18995 4817 49|

| 16483 3536 50 1439 16148 51 3661 3039 52 19010 18121 53 89|

|68 11793 54 13427 18003 55 5303 3083 56 531 16668 57 4771 6|

|722 58 5695 7960 59 3589 14630 |

| |

VIII. The appellant essentially argued that the additional limitations incorporated into the claim had their basis in paragraphs [46] to [51], [105] to [107] and in Table 3 on pages 12 to 14 of the application. They related to the LPDC encoding of an information signal according to one particular parity check matrix which was implemented according to a particular sequence of processing in parity bit accumulators with addresses specified in Table 3. This table defined how bit nodes were connected to check nodes. These limitations provided the necessary encoding features and thus overcame the objections of Articles 83 and 56 EPC raised in the Board's communication.

Reasons for the Decision

1. The appeal is admissible.

2.1 The only claim of the appellant's request is essentially directed to a method for encoding information blocks of 43200 bits into a codeword of 64800 bits with a Low Density Parity Check (LDPC) code with a code rate of 2/3 and for decoding the codeword associated with the encoded signal.

The encoding step specified in the claim can be summarized as follows:

- after initializing all parity bits of an information block, the first information bit i0 of the first group of 360 information bits is accumulated at parity bit addresses specified in the first row of the table given in the claim;

- each of the following information bits im in the first group is accumulated at parity bit addresses j, whereby j = {x + m mod 360 x q} mod (64800 - 43200), m= 1, 2, .... 359, q = 60 and x represents the address of the parity bit accumulator corresponding to the first bit i0, i.e. x corresponds to the addresses given in the first row of the table;

- the procedure is repeated for each of the successive groups of 360 bits, whereby the addresses for the initial bit of each group are specified in a corresponding row of the table and addresses j for each of the following bits in the group is also given by j = {x + m mod 360 x q} mod (64800 - 43200), as specified above.

- the final parity bits pj are obtained by adding the parity bit pj-1 to pj, starting with j=1.

2.2. As pointed out by the appellant, one advantage of the claimed coding scheme is that both encoding and decoding can be performed in parallel on groups comprising 360 bit nodes and their corresponding check nodes.

Articles 84 and 123 (2) EPC

3.1 The steps of encoding an input message into a codeword, transmitting the codeword, receiving the encoded signal and demodulating the received Low Density Parity Check encoded signal according to the appellant's claim specify the basic features of a method for transmitting information signals and thus find ample support in the original application (see e. g. Figure 8C).

The step of encoding specified in the claim corresponds to the operation of the encoder 203 disclosed in paragraphs [47] to [51] and Table 3 of the description.

As to the step of decoding according to the claim, it is specified in paragraph [105] of the published application that "the bit nodes can be divided into groups of a fixed size" and that the check nodes corresponding to each of the bit nodes of the group can be defined as a function of the check nodes connected to the first check node and of a parameter p = number of check nodes / number of bit nodes in a group. For the coding scheme specified in the claim, p is equal to 60. According to paragraph [106] "the check matrix design ensures that the relevant edges for a group of bit nodes and check nodes are simultaneously placed together in RAM".

3.2 In summary, the Board is satisfied that the appellant's claim does not contain subject-matter which extends beyond the content of the application as originally filed. It is thus admissible under Article 123 (2) EPC.

Furthermore, the Board considers that the claim complies with the requirements of Article 84 EPC.

Articles 54 and 56 EPC

4.1 None of the documents D2 to D5, D7 and D8 cited in the course of the examining and appeal proceedings discloses a method for processing signals comprising the step of encoding specified in the appellant's claim.

Although this step now constitutes an essential feature of the claimed invention, it was not included in any of the previously filed claims and thus it does not appear to have been examined by the department of first instance.

4.2 Under these circumstances, the Board considers that it is not in a position to decide whether the subject-matter of the appellant's claim satisfies the requirements of Articles 54 and 56 EPC.

5. For the above reasons, the Board decides to make use of its discretion under Article 111(1) EPC and remit the case to the department of first instance for further prosecution.

ORDER

For the above 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.

Quick Navigation