T 0873/07 () of 27.11.2009

European Case Law Identifier: ECLI:EP:BA:2009:T087307.20091127
Date of decision: 27 November 2009
Case number: T 0873/07
Application number: 04003085.0
IPC class: H03M 13/29
Language of proceedings: EN
Distribution: D
Download and more information:
Decision text in EN (PDF, 26.638K)
Documentation of the appeal procedure can be found in the Register
Bibliographic information is available in: EN
Versions: Unpublished
Title of application: Turbo encoding with dummy bit insertion
Applicant name: SAMSUNG ELECTRONICS CO., LTD.
Opponent name: -
Board: 3.5.02
Headnote: -
Relevant legal provisions:
European Patent Convention Art 56
Keywords: Inventive step (yes)
Catchwords:

-

Cited decisions:
-
Citing decisions:
-

Summary of Facts and Submissions

I. This is an appeal of the applicant against the decision of the examining division to refuse European patent application No. 04 003 085.0. That application was a divisional application of European patent application No. 99 914 797.8 (referred to in the following as the parent application), which was the subject of appeal No. T 0733/07.

II. The reasons given for the refusal were that the subject-matter of claim 1 lacked an inventive step (Article 52(1) EPC in combination with Article 56 EPC) and that claim 1 was not clear (Article 84 EPC). With respect to the first of these objections, the following documents of the state of the art were cited:

D5: D. Divsalar and F. Pollara, "Turbo Codes for Deep-Space Communications", TDA Progress Report 42-120, 15 February 1995, pages 29 to 39;

D6: D. Divsalar and F. Pollara, "Turbo Codes for PCS Applications", Proceedings of the IEEE International Conference on Communications ICC'95, 18 to 22 June 1995, vol. 1, pages 54 to 59;

D7: Patent Abstracts of Japan, Abstract of JP-A-09 146 785, 6 June 1997; and

D8: GB-A-2 296 165.

III. In a letter dated 28 July 2009 the appellant argued that since the claims of the request filed with that letter corresponded, except for their category, to the allowed claims of the parent application, and since the description also corresponded to that of the parent application, the application met the requirements of the EPC for the same reasons that led to the decision T 0733/07 issued for the parent application on 16 July 2009.

In a further letter dated 13 November 2009 the appellant requested the grant of a patent in the following version:

Description

Pages 1, 9, 11 to 16, 19 to 21, 29 to 33, 37, 41, 43, 44 and 46 to 48 as originally filed,

Pages 2, 3a, 8, 24 to 26 and 49 filed with a letter of 6 October 2005,

Page 3 filed with the letter of 28 July 2009,

Pages 4 to 7, 10, 17, 18, 22, 23, 27, 28, 34 to 36, 38 to 40, 42 and 45 filed with the letter of 13 November 2009.

Claims

Nos. 1 to 11 filed with the letter of 13 November 2009.

Drawings

Sheets 1, 3 to 12 and 14 to 31 as originally filed

Sheets 2 and 13 filed with the letter of 6 October 2005.

IV. Claim 1 reads as follows:

"A channel encoding method for channel encoding an input data bit stream, said channel encoding method comprising the steps of:

inserting at least one predefined bit in said input data bit stream at a predetermined bit position in a channel frame; and

turbo encoding the bit-inserted data bit stream by a turbo encoder to generate an encoded symbol stream, the turbo encoding comprising the steps of:

encoding, by a first recursive systematic convolutional encoder (320, 720, 1020, 1420, 1820, 2220, 2420, 2620, 2820) of the turbo encoder, the bit-inserted data bit stream to generate a first parity symbol stream;

interleaving, by an interleaver (330, 730, 1030, 1430, 1830, 2230, 2430, 2630, 2830) of the turbo encoder, the bit-inserted data bit stream;

encoding, by a second recursive systematic convolutional encoder (340, 740, 1040, 1440, 1840, 2240, 2440, 2640, 2840) of the turbo encoder, the interleaved bit-inserted data bit stream output from the interleaver to generate a second parity symbol stream; and

multiplexing, by a multiplexer of the turbo encoder, the bit-inserted data bit stream, the first parity symbol stream and the second parity symbol stream."

Claims 2 to 11 are dependent on claim 1.

V. The appellant's arguments relevant to the present decision (as presented during the appeal procedure for the parent application) may be summarised as follows:

If the skilled person were to have considered introducing bit insertion into the known turbo encoding method in order to provide frame size matching for the interleaver, he would have done so in a manner such that the bit insertion would occur immediately before the interleaver, and such that the inserted bits would be removed by pruning or puncturing immediately after the interleaver, so that the inserted bits would not be encoded by the constituent encoders.

The claimed invention in contrast defined that the inserted bits are encoded by both of the constituent encoders. This difference reflected the fact that the application addresses a different technical problem, namely that of improving the performance of the decoder, in particular decreasing the number of iterations required by the decoder to reach convergence.

Reasons for the Decision

1. The appeal is admissible.

2. Amendments

The basis for the present claims in the parent application (and in parentheses, in the present divisional application) as originally filed is as follows:

Claim 1: original claims 40 to 44 (7 to 11) in combination with the first embodiment

Claim 2: original claims 47 to 49 and 52 (14 to 16 and 19) in combination with the second embodiment

Claims 3 and 4: original claims 50 and 51 (17 and 18)

Claim 5: original claims 45 and 53 (12 and 20)

Claim 6: original claim 39 (6) in combination with the first embodiment

Claim 7: original claim 43 (10)

Claim 8: original claim 46 (13)

Claim 9: original claims 54 to 56 (21 to 23) in combination with the third embodiment

Claim 10: original claim 59 (26)

Claim 11: original claims 62 to 65 (29 to 32) in combination with the fourth embodiment.

The description of the application has been amended to be consistent with the claims, to correct a number of evident errors (also in the drawings), and to acknowledge further prior art cited during the procedure before the examining division.

Thus, the amendments to the application do not contravene Article 76(1) EPC or Article 123(2) EPC.

3. Clarity

The wording in claim 1 which was objected to under Article 84 EPC in the decision under appeal has been deleted. No further objections under Article 84 EPC arise with respect to the claims in their present form. The use of the two-part form (Rule 43(1) EPC) is in the present case not appropriate, since the rearrangement of the claim which this would entail would lead to a loss of clarity in the claim. The most relevant prior art (the pertinent disclosure of which is similar to that of D5 and D6) has been clearly acknowledged on pages 2 and 3 of the description, referring to Figs. 1 and 2.

4. Novelty

The document D5 discloses (see section II, first paragraph, and Fig. 1):

a channel encoding method for channel encoding an input data bit stream, the channel encoding method comprising the step of turbo encoding the input data bit stream to generate an encoded symbol stream, the turbo encoding comprising the steps of:

encoding, by a first recursive systematic convolutional encoder of the turbo encoder, the input data bit stream to generate a first parity symbol stream;

interleaving, by an interleaver of the turbo encoder, the input data bit stream; and

encoding, by a second recursive systematic convolutional encoder of the turbo encoder, the interleaved input data bit stream outputted from the interleaver to generate a second parity symbol stream.

It is moreover implicit in D5 that the turbo encoding includes multiplexing, by a multiplexer of the turbo encoder, the input data bit stream, the first parity symbol stream and the second parity symbol stream, since the term "multiplexing" covers all of the technical alternatives which might be used to enable the encoded data to be transmitted.

The channel encoding method of the present independent claim 1 is thus distinguished from that of D5 in that it includes also the step of inserting at least one predetermined bit in the input data bit stream at a predetermined bit position in a channel frame, and in that the turbo encoding is carried out so as to encode the resultant bit-inserted data stream (i.e. the bit-inserted data stream is encoded by the first recursive systematic convolutional encoder, interleaved by the interleaver, in interleaved form encoded by the second recursive systematic convolutional encoder, and multiplexed with the first and second parity symbol streams by the multiplexer). The claimed method is therefore new.

5. Inventive step

As argued in the decision under appeal, provision of a bit inserting step in the channel encoding method of D5 would as such be obvious to the skilled person, since both D5 (see page 31, second paragraph) and D6 (from the same authors, see paragraph spanning the two columns of page 56) describe the use of interleavers which the skilled person would recognise as being restricted to a particular block length, and since D7 and D8 (page 30, line 3 to page 34, line 21, referring to Fig. 9) illustrate that the use of bit insertion for matching of block lengths forms part of the common knowledge of the skilled person in the technical field of channel encoding. However, the obvious implementation of such bit insertion would be to carry out the bit inserting immediately before the interleaver, and to puncture or prune the inserted bits immediately after the interleaver, in order to ensure that the inserted bits are not transmitted. The channel encoding method according to the present claim 1 differs from that implementation in that the bit-inserted data stream is provided to the multiplexer and to both of the constituent encoders. The skilled person would not consider such an arrangement to be obvious, because the puncturing or pruning of the inserted bits after encoding would be much more difficult than doing so immediately after the interleaver, since, as the appellant has argued, the position of the inserted bits in the output from the interleaver is deterministic, which is no longer the case after encoding.

The manner in which bits are inserted in the channel encoding method of the present claim 1 reflects the fact that the application does not address the problem of block size matching discussed in the previous paragraph, but instead addresses the problem of improving decoder performance (see e.g. page 11, lines 2 to 4 of the application). The positioning of the bit inserter such that the inserted bits are not only interleaved, but also provided to the multiplexer and to both constituent encoders results in the performance of the decoder being improved through two mechanisms, both of which are specific to the type of decoder which is used for turbo coding (i.e. decoders using two constituent decoders with feedback of intrinsic information, so that the decision is reached iteratively), namely:

(a) the intrinsic information relating to the known inserted bits outputted by the first constituent decoder has a high reliability, and this provides a positive bias to the decision-making process in the second constituent decoder, so that the convergence of the results of the two constituent decoders is accelerated; and

(b) the recursive nature of the convolutional encoding used in the constituent encoders of the encoding device results in the known information of the inserted bits being spread across all the encoded parity symbols of the frame, which known information results in a further acceleration of the convergence process in the decoder.

The available prior art provides no suggestion that the insertion of known bits in the input data stream could have such an advantageous effect. Thus the introduction into the channel encoding method of D5 of a bit inserting step carried out as defined in the present claim 1 (that is, so that the bit-inserted data stream is provided not only to the interleaver, but also to the multiplexer and the two constituent encoders) would not be obvious to the skilled person.

6. Therefore, the subject-matter of claim 1 is considered to be new in the sense of Article 54 EPC and to involve an inventive step in the sense of Article 56 EPC.

The subject-matter of claims 2 to 11, which are dependent on claim 1, is thereby also to be considered as being new and involving an inventive step.

ORDER

For these reasons it is decided that:

1. The decision under appeal is set aside.

2. The case is remitted to the first instance with the order to grant a patent in the following version:

Description

Pages 1, 9, 11 to 16, 19 to 21, 29 to 33, 37, 41, 43, 44 and 46 to 48 as originally filed,

Pages 2, 3a, 8, 24 to 26 and 49 filed with the letter of 6 October 2005,

Page 3 filed with the letter of 28 July 2009,

Pages 4 to 7, 10, 17, 18, 22, 23, 27, 28, 34 to 36, 38 to 40, 42 and 45 filed with the letter of 13 November 2009.

Claims

Nos. 1 to 11 filed with the letter of 13 November 2009.

Drawings

Sheets 1, 3 to 12 and 14 to 31 as originally filed

Sheets 2 and 13 filed with the letter of 6 October 2005.

Quick Navigation