T 1477/09 (Huffman shaping/BROADCOM) of 13.12.2011

Summary of Facts and Submissions

I. This appeal is against the decision of the examining division refusing European patent application No. 01963892.3, with international publication number WO-A-02/15443.

The refusal was based, inter alia, on the ground that the subject-matter of claim 1 of a first auxiliary request (which is the request most relevant to the present decision) did not meet the requirement of inventive step pursuant to Article 52(1) in combination with Article 56 EPC. The examining division referred, inter alia, to the following document in its decision:

D1: Kschischang et al: "Optimal Nonuniform Signaling for Gaussian Channels", IEEE Transactions on Information Theory, Vol. 39, No. 3, May 1993, pages 913-929.

II. The appellant filed a notice of appeal against the above decision. Claims of a new main request and an auxiliary request were subsequently filed together with a statement of grounds of appeal.

In the statement of grounds, the appellant implicitly requested that a patent be granted on the basis of the claims of one of the aforementioned requests.

Oral proceedings were conditionally requested.

III. In a communication accompanying a summons to oral proceedings the board gave a preliminary opinion in which, inter alia, it was considered that the subject-matter of claim 1 of either the main or the auxiliary request did not involve an inventive step (Article 52(1) in combination with Article 56 EPC).

IV. With a response to the board's communication received on 9 November 2011, the appellant filed claims of a new auxiliary request to replace the auxiliary request on file.

V. Oral proceedings were held on 13 December 2011. At the oral proceedings the appellant withdrew the main request on file, elevated the pending auxiliary request to the main request, and submitted claims of a new auxiliary request. The appellant requested that the decision under appeal be set aside and a patent granted on the basis of claims 1 and 2 of the request as submitted on 9 November 2011 (main request), or of the single claim as submitted during the oral proceedings (auxiliary request).

At the end of the oral proceedings the board announced its decision.

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

"A method of communicating data for use in a communication system, the method comprising:

accepting data from a source of user data (1303);

scrambling said user data into pseudo-random data (1307); determining an optimum probability distribution for channel symbols of a predetermined modulation, said optimum probability distribution maximizing a shaping gain subject to the constraint of a predetermined rate R and subject to a normalization constraint

FORMULA/TABLE/GRAPHIC

pi = 1; said probability distribution being defined by the equation pi = alpha exp(-s|ai|2), wherein pi represents a probability of a constellation point ai, |ai| represents the amplitude of the respective constellation points ai, alpha and s represent two parameters, the value of s being chosen to achieve a predetermined rate R such that

R=

FORMULA/TABLE/GRAPHIC

pi*log2(pi) <= log2(M), the value of alpha following from

FORMULA/TABLE/GRAPHIC

pi = 1, M representing the total number of constellation points ai,

generating a Huffman code for the optimum-probability distribution of the predetermined modulation, such that a probability 2**(-L)of recognizing the Huffman codeword is approximately equal to the probability pi of the corresponding symbol value;

accumulating the pseudo-random data until a Huffman codeword is recognized (1309); wherein a probability of recognizing the Huffman codeword in the scrambled user data is equal to 2**(-L), wherein L represents a length of the Huffman codeword;

mapping the Huffman codeword into the corresponding channel symbol (1311), and applying the channel symbol to an input of a channel at a constant rate."

VII. Claim 1 of the auxiliary request is the same as that of the main request except for the appending of the following wording to the end of the claim:

"wherein source symbols of the Huffman code are grouped in blocks of K-symbols, K>1, wherein the Huffman code is constructed from the k [sic]-symbol blocks, such that an expected value L of a codeword length l of the Huffman code is closer to a symbol enthropy [sic] H(p) of the channel symbols".

Reasons for the Decision

1. Inventive step

1.1 Claim 1 - main request

1.1.1 The present invention relates to data transmission by mapping data to points of a signal constellation by making use of constellation "shaping", by which is meant arranging for constellation points to be selected with an unequal probability distribution in order to reduce the energy ("entropy") of the transmitted signal and hence the power required to transmit it. As explained in the description of the present application (cf. page 6, lines 19-28), shaping is attained by parsing a scrambled data stream into Huffman codewords, and mapping the codewords into modulation symbols, ie constellation points. The Huffman code is designed to let the modulation symbols assume an approximately Gaussian distribution (governed by the equation pi = alpha exp(-s|ai|**(2)), as set out in claim 1).

1.1.2 Document D1 represents the closest prior art. Document D1 is a theoretical paper which proposes to maximise the shaping gain by using a Maxwell-Bolzmann distribution, which, as was agreed by the appellant, is a Gaussian distribution. In D1 (cf. page 917, left-hand column at the bottom) the same equation is reproduced as set out in claim 1, ie pi = alpha exp(-s|ai|**(2)), except that a different terminology is used, namely s = lambda, a = r and alpha = 1/Z(lambda).

As noted in D1, "the Maxwell-Bolzmann distribution minimizes average energy for a fixed bit rate", whereby "the parameter lambda >= 0 governs the trade-off between bit rate and average energy" (cf. page 917, left-hand column, last paragraph).

D1 discloses "dyadic approximations" to the ideal Maxwell-Bolzmann distribution by applying the Huffman procedure to the Maxwell-Boltzmann probabilities pi (cf. pages 922-923, section "B. Huffman Codes". In a first step of the process, an "optimal" value of lambda, ie lambdaopt, is chosen which maximises the gain G (page 923, left-hand column, last three lines).

1.1.3 Using the wording and mathematical expressions of claim 1, document D1 discloses a method of communicating data for use in a communication system, the method comprising:

accepting data from a source of pseudo-random data (cf. page 921, right-hand column, lines 14-15); determining an optimum probability distribution ("Maxwell-Boltzmann distribution") for channel symbols of a predetermined modulation (ie a given constellation), said optimum probability distribution maximizing a shaping gain subject to a normalization constraint

FORMULA/TABLE/GRAPHIC

pi = 1 (the appellant agreed that this relationship was inherent to any probability distribution); said probability distribution being defined by the equation pi = alpha exp(-s|ai|2), wherein pi represents a probability of a constellation point ai, |ai| represents the amplitude of the respective constellation points ai, alpha and s represent two parameters (cf. page 917, left-hand column, last line), the value of s being chosen to achieve a rate R such that

R=

FORMULA/TABLE/GRAPHIC

pi*log2(pi) <= log2(M) (cf. page 915, left-hand column, last line assuming a 2-dimensional constellation, N=2), the value of alpha following from

FORMULA/TABLE/GRAPHIC

pi = 1 (since pi = alpha exp(-s|ai2|) and

FORMULA/TABLE/GRAPHIC

pi = 1, it follows that alpha = 1

FORMULA/TABLE/GRAPHIC

FORMULA/TABLE/GRAPHIC

exp(-s|ai2|); in D1, 1/Z(lambda) is derived in the same way, cf. page 917, equation (12)), M representing the total number of constellation points ai (it is considered implicit in D1 that the summation shown in equation (12) extends over the total number M of constellation points),

generating a Huffman code for the optimum-probability distribution of the predetermined modulation, such that a probability 2**(-L)of recognizing the Huffman codeword is approximately equal to the probability pi of the corresponding symbol value (cf. page 923, right-hand column, lines 5-7);

accumulating the pseudo-random data until a Huffman codeword is recognized (cf. page 921, right-hand column, lines 14-18 in combination with pages 922-923, section "B. Huffman Codes"); wherein a probability of recognizing the Huffman codeword in the user data is equal to 2**(-L), wherein L represents a length of the Huffman codeword (cf. page 921, right-hand column, 1ines 18-19);

mapping the Huffman codeword into the corresponding channel symbol (cf. page 921, right-hand column, lines 19-20), and applying the channel symbol to an input of a channel at a constant rate (cf. page 915, left-hand column, lines 5-8).

1.1.4 The subject-matter of claim 1 differs from the disclosure of document D1 in the following aspects:

(i) The pseudo-random data are produced by scrambling the user data.

(ii) The value of s (which in D1 equals lambda) is chosen in accordance with a bit rate constraint, whereas, as pointed out above, in D1 a value lambdaopt is chosen which optimises the gain.

1.1.5 Re (i): Scrambling is a conventional method of generating pseudo-random data. In D1, the input data are required to be "equiprobable", ie must also have a random distribution (cf. page 921, right-hand column, 14-15). Consequently, it would be obvious to include a scrambling step in order to ensure that the input data are [pseudo-]random. This aspect therefore makes no contribution to inventive step, nor has the appellant argued otherwise.

1.1.6 Re (ii): D1 is a theoretical paper which attempts to find an optimised value of lambda with regard to gain, namely lambdaopt. Nevertheless, as pointed out above, it is noted in D1 that lambda governs the trade-off between bit rate and average energy. Moreover, D1 considers the effect of varying lambda to values greater or less than lambdaopt (cf. page 924, left-hand column). It is also noted (cf. the footnote on page 917, left-hand column) that "the given constellation must be able to support the given bit rate or the given average energy value, so these values are themselves constrained". In a practical communication system based on document D1, the skilled person would consequently understand without requiring inventive skill that a different value to lambdaopt may be required in order to meet a given bit rate constraint. Hence, in the board's view, this aspect does not contribute to inventive step either.

1.1.7 At the oral proceedings, the appellant argued mainly that although D1 suggests a Gaussian distribution, it was not the same Gaussian distribution as presently claimed as the distribution in D1 was optimised according to different criteria. In particular, the choice of lambdaopt led away from the claimed invention. In the statement of grounds, the appellant also argued that in D1, the Huffman procedure was not applied to the probabilities of constellation points (as in the present invention) but was used for encoding the source symbols, whereby ""the constellation is matched to the code" and not vice versa".

1.1.8 The board was not convinced by the appellant's arguments. As explained in the foregoing, the skilled person starting out from D1 would not require inventive skill to change the value lambdaopt to a different value in order to meet a given a bit rate constraint. This would lead to the same Gaussian distribution as claimed since the remaining parameter 1/Z(lambda) in D1 (ie alpha, using the terminology of claim 1) is calculated in the same way as required by claim 1. With regard to the second argument, the board disagrees with the appellant's interpretation of D1. In the passage on page 923, left-hand column, fifth line from the bottom, ff., it is apparent that the process begins by taking a given constellation ("Given an N-D constellation ..."). A list of probabilities pi is then generated, from which a complete Huffman code is obtained. The input random data stream is then parsed into codewords (ie codewords in the data stream are "recognised") and mapped to respective constellation points (cf. page 921, right-hand column, lines 14-18), exactly as required by claim 1.

1.1.9 The board concludes that the subject-matter of claim 1 does not involve an inventive step (Articles 52(1) and 56 EPC).

1.2 Claim 1 - auxiliary request

1.2.1 Claim 1 of the auxiliary request differs from claim 1 of the main request in the added feature "wherein source symbols of the Huffman code are grouped in blocks of K-symbols, K>1, wherein the Huffman code is constructed from the k [sic]-symbol blocks, such that an expected value L of a codeword length l of the Huffman code is closer to a symbol enthropy [sic] H(p) of the channel symbols".

1.2.2 This feature is based on the passage at page 9, lines 13 to 23, where it is explained that for low values of L, ie the average bit length of the Huffman code, the difference between L and the entropy H(p) of the source symbols can be significant. This problem is mitigated by constructing the Huffman code from K source symbols. In other words, a better approximation to Gaussian can be achieved by basing the Huffman code on K source symbols.

1.2.3 However, in the board's view the same idea is suggested in D1. In D1 at page 924, right-hand column, it is stated in connection with the previously-mentioned Huffman code embodiment that "the relative entropy between the Maxwell-Boltzmann distribution and its dyadic approximation can be made to approach zero by considering Cartesian products of the basic constellation". As a simple example, the Cartesian product of two identical basic one-dimensional PAM constellations is a two-dimensional QAM constellation in which each constellation point is the concatenation of two (ie a block of K=2) PAM source symbols. This is illustrated in Figs. 4 and 5 and the text bridging pages 921 and 922 of D1 (albeit in connection with a different prefix code, although the code here is not relevant as this example is only used to demonstrate a Cartesian product of a basic constellation). It follows that D1 also suggests constructing a Huffman code based on blocks of K source symbols. Moreover, this is done such that an expected value L of a codeword length l of the Huffman code is closer to a symbol entropy of the channel symbols, as required by claim 1 of the auxiliary request (this is merely another way of expressing that the relative entropy is reduced, cf. D1, page 924, right-hand column, lines 2-5).

1.2.4 The appellant disagreed with the board's view that D1 disclosed the same idea as now claimed, arguing that the added feature of claim 1 of the auxiliary request enabled the average length of the Huffman codewords to be reduced whilst the constellation itself used for transmitting the symbols via the communications channel remained the same size, which was not the case in D1. The board notes however that neither of these aspects appear in the claim or are mentioned in the description. The board also finds the appellant's explanation to be somewhat doubtful given that, as stated in the description on page 9, line 22, the new code comprises M**(K) codewords, implying a larger constellation and hence a longer L (ie a higher number of bits per symbol). Moreover, the parameter K denoting the block size is also used on page 10 to denote the dimension of the constellation, which hardly seems to be a coincidence. Obviously, in general a K-dimensional constellation is larger than a one-dimensional constellation. The board therefore found the appellant's arguments unconvincing.

1.2.5 The board concludes that the subject-matter of claim 1 of the auxiliary request does not involve an inventive step either (Articles 52(1) and 56 EPC).

2. Conclusion

As there is no allowable request, it follows that the appeal must be dismissed.

ORDER

For these reasons it is decided that:

The appeal is dismissed.