T 0374/04 (OFDM block code/SAMSUNG) of 8.9.2006

European Case Law Identifier: ECLI:EP:BA:2006:T037404.20060908
Date of decision: 08 September 2006
Case number: T 0374/04
Application number: 00302323.1
IPC class: H04L 27/26
Language of proceedings: EN
Distribution: D
Download and more information:
Decision text in EN (PDF, 70.995K)
Documentation of the appeal procedure can be found in the Register
Bibliographic information is available in: EN
Versions: Unpublished
Title of application: Block code for multicarrier transmission
Applicant name: SAMSUNG ELECTRONICS CO., LTD.
Opponent name: -
Board: 3.5.03
Headnote: -
Relevant legal provisions:
European Patent Convention 1973 Art 123(2)
European Patent Convention 1973 Art 84
European Patent Convention 1973 Art 83
European Patent Convention 1973 Art 52(1)
Keywords: Main request - clarity - no
First auxiliary request - inventive step - no
Second auxiliary request allowable
Catchwords:

-

Cited decisions:
-
Citing decisions:
-

Summary of Facts and Submissions

I. This is an appeal against the decision of the examining division, dated 6 October 2003, to refuse patent application number 00 302 323.1, publication number 1 039 714. The reason given for the refusal was that the claimed subject-matter was not clear (Article 84 EPC), the decision also mentioning other objections under Articles 123(2), 84 and 83 EPC.

II. Notice of appeal was filed and the fee paid on 2 December 2003. A statement setting out the grounds of the appeal was filed on 11 February 2004 together with amendments according to a main and two auxiliary requests. Oral proceedings were requested.

III. On 23 March 2006 the board issued a summons to oral proceedings to take place on 6 July 2006. The communication accompanying the summons raised potential objections against all of the requests. It cited inter alia the document

D2: T.A. Wilkinson et al., "Minimisation of the peak to mean envelope power ratio of multicarrier transmission schemes by block coding," IEEE Vehicular Technology Conference, 25 to 28 July 1995, Proceedings pages 825 to 829, IEEE, 1995.

IV. The appellant filed a new main and two auxiliary requests, together with arguments in their favour, on 6 June 2006. On 4 July 2006 the appellant withdrew the request for oral proceedings and requested that the proceedings be continued in writing. It was stated that the appellant would not be represented at the oral proceedings if they were held.

V. The board informed the appellant that the oral proceedings would take place as scheduled. The appellant was not represented at the oral proceedings, during which the board deliberated and decided to continue the proceedings in writing since it appeared that with certain amendments the second auxiliary request could be granted.

VI. A corresponding communication was issued on 10 July 2006. The appellant filed amendments to its second auxiliary request with a letter dated 26 and received 31 July 2006.

VII. Claim 1 of the main request reads as follows:

"An orthogonal frequency division multiplexing (OFDM) transmission system comprising:

a block encoder (100) for encoding binary data of U bits into V-ary data of U V-ary values, each of the V-ary values having n bit binary data to express V into 2**(n) according to a predetermined mapping rule, wherein the block encoder (100) is a codebook storage unit (248) for stroring [sic] a plurality of codewords of V-ary data of U V-ary values and outputting corresponding codeword that is addressed by a U bit binary data;

a serial-to-parallel converter (101) for converting the output codeword into parallel data;

a V-ary modulator (102) for V-ary modulating the paralleled codeword;

an Inverse Fast Fourier Transformer (103) for inverse Fast Fourier transforming the V-ary modulated result into an orthogonal frequency division multiplexing (OFDM) symbol having U sub-symbols; and

a transmitter for transmitting each sub-symbol of the OFDM symbol on each sub-carrier,

characterized by

a V-ary data generator (240) for generating V-ary data of n bits of binary data;

an OFDM symbol generator (242) for generating OFDM symbols by V-ary modulating the generated V-ary data and inverse Fast Fourier transforming the V-ary modulated result;

a determiner (244) for determining whether each of the OFDM symbol satisfies a predetermined condition and an OFDM symbol satisfying the predetermined condition to be a codeword candidate; and

a codeword extractor (246) for extracting 2**(u) codewords from the codeword candidates, the extracted codewords having smaller bit changes between adjacent codewords than between non-adjacent codewords,

wherein the extracted codewords are stored as the V-ary data at corresponding locations in the codebook storage unit where the U-bit binary data acts as an address."

Independent claims 3 and 5 respectively claim "An orthogonal frequency division multiplexing (OFDM) receiving system" and "A method of generating codewords for OFDM transmission" in substantially corresponding terms.

Claim 1 of the first auxiliary request differs from claim 1 of the main request in that the final features are amended to read:

"... a codeword extractor (246) for extracting 2**(u) codewords from the codeword candidates;

wherein the extracted codewords are stored as the V-ary data at corresponding locations in the codebook storage unit where the U-bit binary data acts as an address;

wherein the determiner (244) determines whether a ratio of peak power to an average power of the OFDM symbol is smaller than or equal to a predetermined value."

Independent claims 2 and 3, directed to the receiving system and method respectively, are amended equivalently.

Claim 1 of the second auxiliary request reads:

"An orthogonal frequency division multiplexing (OFDM) transmission system comprising:

a block encoder (100) for encoding binary data of U bits into V-ary data of U V-ary values, each of the V-ary values having n bits of binary data to express V as one of 2**(n) values, the block encoder encoding the binary data according to a predetermined mapping rule, wherein the block encoder (100) is a codebook storage unit (248) for storing a plurality of codewords of V-ary data of U V-ary values and outputting the corresponding codeword that is addressed by U bit binary data;

a serial-to-parallel converter (101) for converting the output codeword into parallel data;

a V-ary modulator (102) for V-ary modulating the paralleled codeword;

an Inverse Fast Fourier Transformer (103) for Fast Fourier transforming the V-ary modulated result into an orthogonal frequency division multiplexing (OFDM) symbol having U sub-symbols; and

a transmitter for transmitting each sub-symbol of the OFDM symbol on a corresponding sub-carrier,

characterised in that the codebook maps eight bits of input data A0, A1, A2, A3, A4, A5, A6, A7 to sixteen bits of output data C0, C1, C2, C3, C4, C5, C6, C7, C8, C9, C10, C11, C12, C13, C14, C15 using the mapping:

[Boolean algebraic equations defining each C in terms of the A's and intermediate variables.]"

Claim 2 is a corresponding independent claim to a receiving system.

VIII. The appellant requests that the decision be set aside and a patent be granted on the basis of:

claims 1 to 6 of the main request or alternatively claims 1 to 3 of the first auxiliary request, both filed on 6 June 2006, or alternatively claim 1 (part - pages 13 and 14) filed on 6 June 2006 and claim 1 (part) and claims 2 and 3 (pages 15 and 16) filed with the letter dated 26 and received 31 July 2006 of the second auxiliary request;

description, pages

1 and 4 to 12 as originally filed;

3 filed on 9 April 2003; and

2 according to each of the three requests filed on 6 June 2006;

drawing sheets

1 to 5 as originally filed.

Reasons for the Decision

1. The main request

1.1 Each independent claim of the main request contains the feature, "the extracted codewords having smaller bit changes between adjacent codewords than between non-adjacent codewords." This feature is not clear, firstly since the property of adjacency of codewords is neither defined in the application nor is there to the board's knowledge any commonly accepted definition. Secondly it is unclear whether the "adjacent" and "non-adjacent codewords" refer to the extracted codewords or to the codeword candidates.

1.2 The appellant argues on this point (see submission of 6 June 2006, page 3) that the description discloses that codewords are extracted "in sequence of codewords having a small bit change". It is argued that, "The skilled person could only interpret this as requiring the adjacent codewords in the sequence to have a small bit change from one codeword to the next." Thus, the appellant apparently sees "adjacency" as relating to the order in which the codewords are extracted. However this is not clear from the claim, which does not make any reference to the order of extraction.

1.3 Moreover the board does not agree that the description is unambiguous. In particular the "small bit change" could be measured from the first element chosen or could be a property of the set of extracted codewords as a whole. Thus for example it is not clear from the application as a whole which of the sets of codewords {0001, 0010, 0100, 1000} and {0001, 0011, 0111, 1111} would be chosen in a 4-bit case using this criterion.

1.4 Thus the matter for which protection is sought is not clear and the claims do not satisfy Article 84 EPC. The request is therefore not allowable.

1.5 The board notes that to the extent that any meaning can be assigned to the feature discussed it was not present in the application as filed. The concept of adjacency was not discussed in the original application, nor is it clearly and unambiguously derivable that the small bit change relates to adjacent codewords in the order in which they are extracted - see Point 1.3. The claim therefore goes beyond the original disclosure. Hence Article 123(2) EPC is also not satisfied.

2. The first auxiliary request

2.1 The board notes that the claims contain a number of typographical or linguistic errors, making the claimed subject-matter not entirely clear. However these problems could apparently be overcome fairly easily and the board will rather interpret the claims as it takes them to be intended in its analysis of novelty and inventive step. Since the three claims are independent but are in essence directed to the same invention, the analysis given below applies to all three.

2.2 In OFDM systems digital data are transmitted simultaneously over a number of frequencies having a defined numerical relationship to each other, ensuring that they do not mutually interfere. Data may be modulated onto each individual frequency according to any one of a number of well-known schemes such as QAM ("Quadrature Amplitude Modulation") or QPSK ("Quadrature Phase Shift Keying"), so that the "sub-symbols" transmitted on a single frequency ("sub-carrier") may take any one of a number of values (normally a power of 2), which is referred to in the application as "Q-ary" (in the specific case of four values) or "V-ary" (in general) data. The appellant has not argued and the board does not believe that there was anything new in the processes of transmitting and receiving signals by this method (including for example the inverse Fast Fourier transform) at the present priority date.

2.3 While the different frequencies do not interfere with each other they can combine to produce brief peaks of power output which are very high compared to the average power, which is technically disadvantageous. The appellant therefore set out to decrease the "peak-to-average power ratio" (abbreviated to "PAR" in the application but also frequently abbreviated to "PAPR" or "PMEPR" ("Peak-to-Mean Envelope Power Ratio") elsewhere). The high peaks occur when certain specific symbols are transmitted, so that the appellant has adopted a method which avoids sending the worst offending symbols.

2.4 Assuming as an example that an 8-bit block of data is to be sent simultaneously as an OFDM symbol and that each sub-carrier conveys two bits of information at a time, if only four frequencies are used then all the possible combinations of sub-symbols must be available to send, including those with high PAR's. The appellant's solution is to send the symbol on more than four frequencies, eight in the specific example given, which involves mapping the initial eight bits into a 16-bit block. Since there are many (more than 64,000) combinations of sixteen bits but only 256 of them are needed, it is possible to choose a subset of the 16-bit codes whose members do not have high PAR's. In the method as claimed a "determiner" checks which of the 16-bit codes have a PAR under a predetermined value to provide "codeword candidates" and then an "extractor" selects the necessary number (e.g. 256) from the codeword candidates according to criteria which are not specified in the independent claims of the first auxiliary request. A "codebook storage unit" is provided to convert each possible 8-bit code into one of the chosen 16-bit codes for transmission and vice versa for reception.

2.5 However, this solution to the problem of high PARs was known at the present priority date, e.g. from document D2 - see D2, page 825, column 2, lines 10 and 11, and 14 and 15, page 826, column 1, lines 20 to 25 and page 827, column 1, lines 22 and 23. The only claimed feature not disclosed by D2 explicitly or implicitly (see Point 2.2) is the limitation that the number of sub-carriers U equals the number of bits in the block which addresses the codebook. D2 shows a number of possible ratios between the number of bits coded and the "code rate", which is the product of the number of sub-carriers and the number of bits modulated onto each sub-carrier. The appellant has not identified any technical problem solved by this feature and the board concludes that it is merely an arbitrary choice which would have been available to the skilled person and which does not involve an inventive step.

2.6 Hence the subject-matter of the independent claims of the first auxiliary request does not involve an inventive step with respect to the disclosure of document D2 and this request is not allowable.

3. The second auxiliary request

3.1 Article 123(2) EPC

3.1.1 The subject-matter of the new claims of the second auxiliary request is disclosed in the application as filed, e.g. at Figs. 1A, 1B, 3 and 4 and Paragraphs [0027] to [0032]. The amendments to the description are confined to an acknowledgement of prior art in accordance with Rule 27(1)(b) EPC, and a formal amendment to satisfy Rule 27(1)(c) EPC. Hence the text of the second auxiliary request satisfies the requirements of Article 123(2) EPC.

3.1.2 The board notes however that the last two lines of page 2 of the description are in error in that they refer to a previous set of claims. This may be dealt with in the Rule 51(4) communication.

3.2 Article 84 EPC

3.2.1 The claimed subject-matter is supported by the description for the reasons given in Point 3.1.

3.2.2 The board also considers the claims to be clear and concise, bearing in mind that the skilled person would be familiar with the steps required in transforming and modulating binary data blocks for OFDM transmission. The examining division raised an objection to the use of unspecified values "U" and "V". However the board considers that their meaning has been clarified by the general reformulation of the claims, again taking into account that the skilled person would be aware that in OFDM a sub-symbol would usually encode the equivalent of more than one bit of data. Moreover, the restriction of the claims to eight bits of input data and sixteen bits of output data in fact limits U and V to 8 and 4 (i.e. 2**(2), representing 2 bits of data) respectively.

3.2.3 The board notes an evident typographical error in claim 1, which presently states, "Inverse Fast Fourier Transformer (103) for Fast Fourier transforming ...," rather than "Inverse Fast Fourier Transformer (103) for inverse Fast Fourier transforming ...," c.f. claim 1 of the main request. This too may be dealt with in the Rule 51(4) communication.

3.3 Article 83 EPC

3.3.1 In its decision to refuse the application the examining division mentioned an objection under Article 83 EPC. It arose because the "PAR" value of a symbol was defined by taking the peak power output during transmission of the OFDM symbol and dividing it by the average power over the period of transmission of that symbol only. It was argued that this did not deliver the value which was needed for eliminating symbols having a large peak-to-average power since the average should be taken over whole messages possessing the typical distribution of frequencies of symbol occurrence. The board agrees that the definition given is not, in the most general case, correct. However, the board considers that the skilled person would realise the defect and correct it if it was necessary to do so. In fact, it would appear that for modulation schemes such as QPSK where the energy of each constellation element is equal, all the symbols have the same average power, so that for such schemes the PAR definition given would be correct and the symbols with a high peak-to-average power ratio are in fact the same ones as those having a high absolute peak power output. This is the assumption also underlying the measurements in document D2, where "PEP" ("Peak Envelope Power") is used interchangeably with "PMEPR" ("Peak-to-Mean Envelope Power Ratio").

3.4 Novelty and inventive step

3.4.1 According to the description codewords are chosen to have "a small bit change between data" (Paragraph [0026]). They are so chosen to reduce the size of an encoder or decoder by "reduc[ing] the number of gates constituting the encoder or the decoder". The condition, "a small bit change between data," is ambiguous but the description goes on to give a specific mapping. It is clear therefore that the example mapping has the desirable property of leading to a small encoder or decoder. The independent claims of the second auxiliary request give the mappings between 8- and 16-bit data in the form of Boolean algebra equations which the skilled person would be able to implement efficiently in combinatorial logic.

3.4.2 D2 indicates that an implementation using combinatorial logic is preferable ("This may be realisable in combinatorial logic or it may require a look-up table," page 827, column 2, lines 18 and 19). However, it does not give any indication of how to choose the codewords to so as to make it possible to use combinatorial logic. Indeed it appears to teach away from using this aim in selecting the code words - see page 828, column 1, lines 5 to 29. Hence the board concludes that the skilled person would not be led to the presently claimed mapping by the teaching of D2.

3.4.3 This is also true of the other prior art documents available, so that the board concludes that the presently claimed subject-matter is novel and involves an inventive step.

3.5 No other objections have been raised or are apparent to the board. Hence the board considers that with the exception of the minor objections mentioned at Points 3.1.2 and 3.2.3 above, a patent can be granted in the form specified in the second auxiliary request.

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 on the basis of the second auxiliary request, with the necessary corrections to the description.

Quick Navigation