T 0733/07 () of 16.7.2009

European Case Law Identifier: ECLI:EP:BA:2009:T073307.20090716
Date of decision: 16 July 2009
Case number: T 0733/07
Application number: 99914797.8
IPC class: H03M 13/29
Language of proceedings: EN
Distribution: D
Download and more information:
Decision text in EN (PDF, 26.157K)
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 insertion of known bits
Applicant name: SAMSUNG ELECTRONICS CO., LTD.
Opponent name: -
Board: 3.5.02
Headnote: -
Relevant legal provisions:
European Patent Convention 1973 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. 99 914 797.8.

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. Oral proceedings before the board took place on 16 July 2009.

IV. The appellant requested that the decision under appeal be set aside and that a patent be granted in the following version:

Description

Pages 1, 5 to 7, 9 to 22, 28 to 48 as originally filed,

Page 49 filed with letter of 31 August 2004,

Pages 2, 3a, 8, 23 to 27 filed with letter of 31 August 2005,

Pages 3 and 4 received in the oral proceedings of 16 July 2009.

Claims

Nos. 1 to 11 received in the oral proceedings of 16 July 2009.

Drawings

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

Sheets 2 and 13 filed with letter of 31 August 2005.

V. Claim 1 reads as follows:

"A channel encoding device for channel encoding an input data bit stream, said channel encoding device comprising:

a bit inserter (310, 710, 1010, 1410, 1810, 2210, 2410, 2610, 2810) for inserting at least one predefined bit in said input data bit stream at a predetermined bit position in a channel frame; and

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

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

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

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

a multiplexer for multiplexing 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.

VI. The appellant's arguments relevant to the present decision may be summarised as follows:

If the skilled person were to have considered introducing bit insertion into the known turbo encoder 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 original application is as follows:

Claim 1: original claims 7 to 11 in combination with the first embodiment

Claim 2: original claims 14 to 16 and 19 in combination with the second embodiment

Claims 3 and 4: original claims 17 and 18

Claim 5: original claims 12 and 20

Claim 6: original claim 6 in combination with the first embodiment

Claim 7: original claim 10

Claim 8: original claim 13

Claim 9: original claims 21 to 23 in combination with the third embodiment

Claim 10: original claim 26

Claim 11: original claims 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 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 device for channel encoding an input data bit stream, the channel encoding device comprising a turbo encoder for encoding the input data bit stream to generate an encoded symbol stream, the turbo encoder comprising:

a first recursive systematic convolutional encoder for encoding the input data bit stream to generate a first parity symbol stream;

an interleaver for interleaving the input data bit stream; and

a second recursive systematic convolutional encoder for encoding 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 encoder includes a multiplexer for multiplexing the input data bit stream, the first parity symbol stream and the second parity symbol stream, since the term "multiplexer" covers all of the technical alternatives which might be used to enable the encoded data to be transmitted.

The channel encoding device of the present independent claim 1 is thus distinguished from that of D5 in that it includes also a bit inserter for 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 encoder is arranged 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 device is therefore new.

5. Inventive step

As argued in the decision under appeal, provision of a bit inserter in the channel encoding device 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 provide the bit inserter immediately before the interleaver, and to provide a means for puncturing or pruning the inserted bits immediately after the interleaver, in order to ensure that the inserted bits are not transmitted. The channel encoding device according to the present claim 1 differs from that arrangement 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 device 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 device of D5 of a bit inserter arranged 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 department of first instance with the order to grant a patent in the following version:

Description

Pages 1, 5 to 7, 9 to 22, 28 to 48 as originally filed,

Page 49 filed with letter of 31 August 2004,

Pages 2, 3a, 8, 23 to 27 filed with letter of 31 August 2005,

Pages 3 and 4 received in the oral proceedings of 16 July 2009.

Claims

Nos. 1 to 11 received in the oral proceedings of 16 July 2009.

Drawings

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

Sheets 2 and 13 filed with letter of 31 August 2005.

Quick Navigation