T 1529/08 () of 29.11.2011

Summary of Facts and Submissions

I. The appellant (applicant) appealed against the decision of the examining division refusing European patent application No. 06004766.9

II. In the contested decision, the examining division held that the subject-matter of claims 1, 7, 13 and 19 of the applicant's request was not new with regard to the following document:

D1: Ba-Zhong Shen et al.:"Low-Density Parity-Check Coded Modulation Using Multiple Signal Maps And Symbol Decoding", Proc. IEEE International Conference on Communications, Paris, France, 20-24 June 2004, pages 420 - 424, XP01071002.

III. With the statement of grounds of appeal dated 14 July 2008, the appellant filed new claims 1 to 24 of a main request and new claims 1 to 13 of an auxiliary request.

IV. In a communication dated 28 April 2011 accompanying summons to oral proceedings, the Board, taking into account the appellant's new requests and arguments, introduced the following documents into the appeal proceedings:

D2: S.J. Johnson et al., "Construction of Low-density Parity-check Codes from Kirkman Triple Systems", 2001 IEEE, pages 970 - 974;

D3: Tao Tian et al.: "Selective Avoidance of Cycles in Irregular LDPC Code Construction", IEEE Trans. on Communications, Vol. 52, No. 8, August 2004, pages 1242 - 1247;

D4: Tao Tian et al.: "Construction of Irregular LDPC Codes with Low Error Floors", 2003 IEEE, pages 3125 - 3129.

V. Oral proceedings were held before the Board on 29 November 2011.

VI. The appellant requested that the decision under appeal be set aside and a patent be granted on the basis of claims 1 to 24 of the main request or on the basis of claims 1 to 13 of the auxiliary request, both filed with letter of 14 July 2008.

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

"A transmitter (300) used for a communication system, comprising:

an encoder (311) for encoding information data bits in a preset coding scheme when the information data bits are input, and generating a Low Density Parity Check, LDPC, codeword;

a channel interleaver (313) for interleaving the LDPC codeword according to a preset channel interleaving rule; and

a modulator (315) for modulating a channel-interleaved LDPC codeword in a preset modulation scheme and generating a modulation symbol, characterized in that

the channel interleaving rule maps a variable node with a low degree in a factor graph of the LDPC codeword to a bit with a high reliability among bits of the modulation symbol."

The main request further comprises independent claims 5, 7, 10, 11, 13, 16, 17, 19, 22 and 23 which are not relevant to this decision.

Claim 1 according to the auxiliary request reads as follows:

"A transmitter (300) used for a communication system, comprising:

an encoder (311) for encoding information data bits in a preset coding scheme when the information data bits are input, and generating a Low Density Parity Check, LDPC, codeword;

a channel interleaver (313) for interleaving the LDPC codeword according to a preset channel interleaving rule; and

a modulator (315) for modulating a channel-interleaved LDPC codeword in a preset modulation scheme and generating a modulation symbol, characterized in that

the channel interleaving rule sets variable nodes with a preset distance or greater in the LDPC codeword for which channel interleaving is performed, the variable nodes forming a cycle of less than a preset length in a factor graph of the LDPC codeword."

The other independent claims 3, 5, 6, 8, 9, 11 and 12 of the auxiliary request are not relevant to this decision.

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

Even if it might be said that the LDPC coded modulation disclosed in D1 implied units such as an encoder, a channel interleaver and a modulator, this document did not identify any particular channel interleaving rule.

In fact, D1 disclosed some kind of mapping of the m-bit symbol sequence to a constellation signal and pointed out that the mapping of symbols with high degree bits should be different from the mapping of symbols with no high degree bits. As mapping was said to be the crucial problem, D1 taught to use different maps and to select the appropriate map with respect to the bit location of the weak points.

On the other hand, the interleaving rule specified in the characterising part of claim 1 of the main request consisted in mapping a variable node with a low degree in a factor graph of the LDPC codeword to a bit with high reliability among bits of the modulation symbol.

Thus, the essential difference between D1 and the subject-matter of claim 1 was that according to the present invention a particular channel interleaving rule was used for mapping, whereas D1 relied on different Gray maps from which at least two were used in combination to map the symbols only after interleaving and grouping to a corresponding bit symbol sequence.

In other words, the interleaving rule according to claim 1 ensured that, for a constellation of symbols, a variable node with a low degree was mapped to a bit of the modulation symbol with high reliability, whereas D1 taught to select the symbol maps as a function of the interleaver output.

Hence, the subject-matter of claim 1 according to the main request was new within the meaning of Article 54 EPC.

As to claim 1 of the auxiliary request, the interleaving rule specified in the charactering part related to variable nodes forming a cycle of less than a predetermined length in a factor graph of the LDPC codeword and stipulated that, after interleaving, these variables should be separated by a predetermined distance or greater. Document D1 was totally silent about cycles and thus did not imply any interleaving rule based on cycle length. Although D2 to D4 mentioned cycles, these documents were essentially concerned with the problem of avoiding short cycles in an LDPC code and did not teach to deal with them when interleaving and mapping were performed.

As none of the cited documents was concerned with the subject-matter of claim 1 according to the auxiliary request, this request satisfied the requirement of Article 54 EPC.

Reasons for the Decision

1. The appeal is admissible.

Main request

2. Claim 1 of the main request, which essentially corresponds to claim 1 considered in the contested decision, relates to a "transmitter used for a communication system" comprising the following features:

(a) an encoder for encoding information data bits in a preset coding scheme when the information data bits are input, and generating a Low Density Parity Check, LDPC, codeword;

(b) a channel interleaver for interleaving the LDPC codeword according to a preset channel interleaving rule;

(c) a modulator for modulating a channel-interleaved LDPC codeword in a preset modulation scheme and generating a modulation symbol;

(d) the channel interleaving rule maps a variable node with a low degree in a factor graph of the LDPC codeword to a bit with a high reliability among bits of the modulation symbol.

3.1 Document D1 is concerned with bit interleaved coded modulation (BICM) of low-density parity-check codes (LDPC). It is not contested that a communication system, in particular a transmitter, relying on LDPC-BICM necessarily comprises an encoder, a channel interleaver and a modulator as specified in features (a) to (c) of claim 1.

3.2 According to the appellant, however, D1 did not disclose feature (d) of claim 1.

In fact, D1 taught to select different Gray maps to map symbols after the bits of an LDPC codeword had been interleaved and grouped to a corresponding bit symbol sequence, whereas the present application used channel interleaving for mapping.

4.1 Figure 4 of the present application illustrates the modulation constellation based on a "conventional 16QAM scheme". As pointed out on page 14, last paragraph, to page 15, first paragraph, of the application as originally filed, bits S3, S2, S1, S0 mapped to one modulation symbol have different reliabilities. In particular, the reliability of S3 and S2 is higher than the reliability of S1 and S0, respectively.

In the example shown in Figure 6, it is assumed that a parity check matrix has four columns 1 to 4 with a low degree and four columns 5 to 8 with a high degree. "Assuming that the 16QAM scheme is applied to the communication system using the LDPC code as illustrated in FIG. 4, the reliability of bits S3 and S2 of a modulation symbol is higher than that of bits S1 and S0 of the modulation symbol" (page 20, first paragraph of the application as filed). In order to map the low degree variable nodes in columns 1 to 4 to bits of the symbol constellation with a high reliability, the transmitter according to the present invention employs a channel interleaver which performs inter-column permutation by re-ordering columns 3, 4, 5 and 6 as 5, 6, 3 and 4.

4.2 In other words, the present application teaches to rearrange the output bits of an LDPC encoder so that bits with weaker protection (i.e. lower degree) are associated to more reliable bits within the signal constellation of a given map.

5.1 D1 (page 421, right-hand column, first paragraph) points out that the different bits of an LDPC code may have different degrees in the bipartite graph of the code. "The higher the degree of a bit, the more check equations are connected to this bit. Thus the higher degree bits could have more protection from the code, and the symbols with higher degree bits in them could also have more protection. This property suggests that a symbol with more protection from the code could bear some weakness of its corresponding signal caused by the constellation mapping".

"In an LDPC-BICM system, the bit sequence output from the LDPC encoder is interleaved and grouped to generate an m-bit symbol sequence. The symbols are then mapped to constellation signals. ... Since bit decoding is used in the conventional BICM, a map which causes fewer bit errors when a symbol error occurs will be a good candidate" (page 421, left-hand column, second paragraph - underlining added).

5.2 Figure 1 at page 421 shows 12 possible Gray maps of 8-PSK, each having two or four weak points at MSB, 2SB and LSB. According to the example at the bottom of the right-hand column at page 421, the code has 43200 bit nodes with 4800 degree 9 nodes at the beginning, followed by 24000 degree 3 nodes and 14400 degree 2 nodes which correspond to redundant bits. The interleaver outputs the first 4800 three-bit symbols with one degree 9 bit at the LSB, one degree 3 bit at the MSB and one degree 2 bit at the 2SB. As these symbols are more protected at the LSB by the LDPC code, D1 teaches to prefer maps with the weakest points at the LSB (D1, page 422, left-hand column, second sentence). "In general, for any signal constellation, one can select many maps to construct an LDPC-BICM according to 1) the weakness table of Gray maps, 2) the degree distribution of the LDPC code and 3) interleaver".

5.3 Hence, both the present application and D1 realize that a low degree bit in an LDPC codeword should be mapped to a bit with a high reliability among the bits of the modulation symbol. Although D1 does not explicitly define the interleaving rule according to feature (d), it teaches to interleave the output of the LDPC encoder so that the degrees in the groups of the codeword bits to be mapped follow a certain pattern. In the given example, for instance, the 9 degree bits occupy the same position (i.e. LSB) within the group. This implies that the interleaver in fact maps a variable node with a low degree to a bit with a high reliability among the bits of the modulation symbol of the selected symbol constellation (cf. feature (d)).

5.4 Hence, the disclosure in D1 falls within the terms of claim 1 of the main request and, consequently, the subject-matter of this claim is not new within the meaning of Article 54 EPC.

Auxiliary request

6.1 Claim 1 according to the auxiliary request relates to a "transmitter used for a communication system" comprising features (a) to (c) of claim 1 of the main request and the following feature:

(d') the channel interleaving rule sets variable nodes with a preset distance or greater in the LDPC codeword for which channel interleaving is performed, the variable nodes forming a cycle of less than a preset length in a factor graph of the LDPC codeword.

6.2 As specified at page 18, last paragraph, of the application as originally filed, feature (d'), corresponding to "Rule 3", means that variable nodes, which are coupled to cycles of a short length and thus are "in a short distance on the factor graph", are to be separated from each other when the codeword bits are interleaved. "The reason why the variable nodes coupled to cycles of a short length are maximally separated from each other on the LDPC codeword is that bits with a low reliability can be prevented from being successively generated in a channel in which a burst error occurs as in a fading channel" (application as originally filed, page 18, last line to page 19, line 4).

7.1 According to D1, page 421, first paragraph of section II., in "an LDPC-BICM system, the bit sequence output from the LDPC encoder is interleaved and grouped to generate an m-bit symbol sequence. The symbols are then mapped to constellation signals".

In the given example, the LDPC "code has 43200 bit nodes with 4800 degree 9 nodes at the beginning, followed by 24000 degree 3 nodes, and 14400 degree 2 nodes which correspond to redundant bits. Suppose the interleaver outputs the first 4800 symbols with one degree 9 bit at the LSB, one degree 3 bit at the MSB and one degree 2 bit at the 2SB. The rest of the symbols contain two degree 3 bits at the MSB and the LSB respectively, and one degree 2 bit at the 2SB" (D1, page 421, right-hand column, last paragraph).

However, D1 does not specify which cycles are formed by the bit nodes and, in particular, their length.

7.2 As explained in D2, page 970, left-hand column, second paragraph of the "I. Introduction", a "Tanner graph displays the relationship between codeword bits and parity checks and is a useful way to describe LDPC codes. ... The number of edges connected to a code bit vertex is the degree of that code bit, which is simply the number of parity check equations that include it.

"A cycle in a Tanner graph is a sequence of connected code bits and check sums which start and end at the same vertex in the graph and contain no other vertices more than once" (D1, paragraph bridging the two columns on page 970 - underlining added).

A definition of cycle length can also be found, for instance, in D4 (page 3125, see "Definition 1") where it is specified that a "cycle of length 2d is a set of d variable nodes and d constraint nodes connected by edges such that a path exists that travels through every node in the set and connects each node to itself without traversing an edge twice".

It is pointed out in D3 (page 1242, second paragraph of the "Introduction") that "bipartite graphs of finite-length codes without singly connected nodes inevitably have cycles and are thus not tree-like. If cycles exist, neighbors of a node are not independent..." (underlining added).

7.3 In summary, as documents D2 to D4 show, it is generally known in the art that bipartite graphs of finite-length codes inevitably have cycles and that variable nodes coupled to cycles of short length offer weaker protection and thus are more difficult to decode successfully.

7.4 In the light of the above background knowledge, it is reasonable to assume that some of the 14400 consecutive nodes of degree 2 in the 43200 bit code according to the example given in D1 are likely to form cycles of "a predetermined length".

The interleaver referred to in D1 separates bits of the same degree by outputting the first 4800 symbols with one degree 9 bit at the LSB, one degree 3 bit at the MSB and one degree 2 bit at the 2SB. As to the remaining symbols, they contain two degree 3 bits at the MSB and the LSB respectively, and one degree 2 bit at the 2SB. In this way, the interleaver according to D1 sets variable nodes with a preset distance in the codeword for which channel interleaving is performed. As a result, neighbouring nodes of degree 2, which may be coupled within cycles of length 4, are mapped to different symbols and thus separated by a preset distance. In fact, in the example of D1, all variable nodes of the same degree are separated by at least one bit.

8. In summary, the interleaving and mapping rule shown in D1 falls within the terms of feature (d') of claim 1 according to the auxiliary request. Since D1 discloses or necessarily implies also features (a), (b) and (c), the subject-matter of claim 1 is not new within the meaning of Article 54 EPC.

9. As none of the appellant's requests provide a basis for allowable claims, the application has to be refused.

ORDER

For the following reasons it is decided that:

The appeal is dismissed.