T 2234/15 (Turbo decoding/SAMSUNG ELECTRONICS) of 5.6.2019

European Case Law Identifier: ECLI:EP:BA:2019:T223415.20190605
Date of decision: 05 June 2019
Case number: T 2234/15
Application number: 03017538.4
IPC class: H03M 13/29
G11C 19/00
Language of proceedings: EN
Distribution: D
Download and more information:
Decision text in EN (PDF, 468 KB)
Documentation of the appeal procedure can be found in the Register
Bibliographic information is available in: EN
Versions: Unpublished
Title of application: Turbo decoding apparatus and method
Applicant name: Samsung Electronics Co., Ltd.
Opponent name: -
Board: 3.5.07
Headnote: -
Relevant legal provisions:
European Patent Convention Art 56
European Patent Convention Art 84
European Patent Convention Art 123(2)
Keywords: Amendments - added subject-matter
Amendments - claims 1 and 7 (no)
Claims - clarity
Claims - claims 1 and 7 (yes)
Inventive step - claims 1 and 7 (yes)
Catchwords:

-

Cited decisions:
-
Citing decisions:
-

Summary of Facts and Submissions

I. The applicant (appellant) appealed against the decision of the Examining Division refusing European patent application No. 03017538.4, which claims a priority date of 6 August 2002. This was the second refusal decision, taken after the Examining Division had rectified its first refusal decision.

II. The Examining Division had decided that the independent claims of the then main request and auxiliary requests I to V infringed Article 123(2) EPC. Claim 1 of auxiliary request VI violated Article 84 EPC for lack of clarity. Claim 1 of auxiliary request VII infringed both Articles 84 and 123(2) EPC.

III. The following documents had been cited in the course of the first-instance proceedings:

D1:|"Bidirectional Shift Registers", 1999 [retrievable from https://web.archive.org/web/19991011172611/http://www.eelab.usyd.edu.au/digital_tutorial/part2/register06.html];|

D2:|EP 1 261 139 A2, published on 27 November 2002; |

D3:|G. Masera et al.: "VLSI Architectures for Turbo Codes", IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 7, No. 3, September 1999, pp. 369-379; |

D4:|W. Ryan: "A Turbo Code Tutorial", 1998 [retrievable from https://web.archive.org/web/20010604180428/http://www.ece.arizona.edu/~ryan/turbo2c.pdf]; |

D5:|M. Marandian et al.: "Performance Analysis of Sliding Window Turbo Decoding Algorithms for 3GPP FDD Mode", International Journal of Wireless Information Networks, Vol. 9, No. 1, January 2002, pp. 39 to 54.|

IV. In its statement of grounds of appeal, the appellant replaced its requests with a main request and auxiliary requests I and II.

V. In a communication accompanying the summons to oral proceedings, the Board raised objections under Article 84 EPC against the main request and the auxiliary requests. It indicated that it was inclined to agree with the appellant's analysis of the cited prior art.

VI. In a letter dated 2 May 2019, the appellant amended the claims of the main request and filed an amended description page.

VII. During oral proceedings held on 5 June 2019, the appellant replaced its requests with a sole substantive request labelled "third request". At the end of the oral proceedings, the chairman pronounced the Board's decision.

VIII. The appellant requested that the decision under appeal be set aside and that a patent be granted on the basis of the claims of the sole substantive request filed in the oral proceedings as the "third request".

IX. The application documents are as follows:

Description:

- pages 1 to 38 as originally filed;

- page 39 as filed with the letter of 2 May 2019.

Drawings:

- sheets 1/20 to 20/20 as originally filed.

Claims:

- Nos. 1 and 7 as filed in the oral proceedings as part of the "third request";

- Nos. 2 to 6 and 8 to 24 as filed with the letter of 2 May 2019 as the main request and referred to in the "third request".

X. Independent claim 1 of the sole substantive request reads as follows:

"A memory buffer for processing sequential input symbols and providing the input symbols to an N-window mode Soft-In Soft-Out 'SISO' turbo decoder having a window size of W symbols, comprising:

a control logic (330);

a unidirectional shift register (310) having an input terminal and an output terminal, wherein the unidirectional shift register is configured to sequentially shift and store 2NW sequential input symbols from the input terminal in a predetermined direction, and sequentially output the shifted symbols via the output terminal; and

N bidirectional shift registers (321,322,...,323),

wherein each of the bidirectional shift registers includes first and second input terminals, first and second output terminals, and a select terminal,

wherein the bidirectional shift registers are configured by means of the control logic to be sequentially activated at intervals of W symbols of the 2NW sequential input symbols received at the input terminal of the unidirectional shift register,

wherein each of the bidirectional shift registers is configured by means of the control logic to receive first NW symbols among the sequential input symbols received at the input terminal of the unidirectional shift register after activation of the bidirectional shift register, through the first input terminal of the bidirectional shift register, and shift and store the received symbols in a predetermined direction, and at the same time, serially output previously stored second NW symbols through its second output terminal,

wherein each of the bidirectional shift registers is configured by means of the control logic to thereafter receive second NW symbols among the sequential input symbols received at the input terminal of the unidirectional shift register after activation of the bidirectional shift register, through its second input terminal, shift and store the received symbols in the opposite direction of the predetermined direction, and at the same time, serially output the previously stored first NW symbols via its first output terminal, and

wherein the control logic of the memory buffer is configured to provide the select terminal of each of the bidirectional shift registers with a select signal for applying the first NW symbols to the first input terminal or the second NW symbols to the second input terminal."

Independent claim 7 reads as follows:

"A memory buffer for processing sequential input symbols and providing the sequential input symbols to an N-window mode Soft-In Soft-Out 'SISO' turbo decoder having a window size of W symbols, comprising:

a control logic (530);

N first stage's bidirectional shift registers (521; 522) having NW storage areas, a first terminal and a second terminal for input/output, the sequential input symbols being divided into groups each comprised of a sequence of symbols of a predetermined length NW, wherein the first stage's bidirectional shift registers are configured, under control of the control logic, to form symbol streams of the length NW by sequentially receiving and shifting the sequence of symbols of odd-numbered groups among the divided groups via the first terminal and then sequentially outputting the formed symbol streams via the first terminal; and form symbol streams of the length NW by sequentially receiving and shifting the sequence of symbols of even-numbered groups among the divided groups via the second terminal and then sequentially outputting the formed symbol streams via the second terminal, wherein the memory buffer is configured such that the symbols of the odd-numbered groups are sequentially output via the first terminal and, at the same time, the symbols of the even-numbered groups are sequentially received and shifted via the second terminal, wherein the N first stage's bidirectional shift registers are configured by means of the control logic to be sequentially activated at intervals of W symbols of sequential input symbols; and

a second stage's bidirectional shift register (510) having NW storage areas, a third terminal for data input/output, and a fourth terminal for data input/output, wherein the second stage's bidirectional shift register is configured to, under control of the control logic, form symbol streams of the length NW by sequentially receiving and shifting the symbol streams sequentially output via the first terminal of the first activated one (521) of the first stage's bidirectional shift registers, via the third terminal, and then sequentially output the formed symbol streams via the third terminal; and form symbol streams of the length NW by sequentially receiving and shifting the symbol streams sequentially output via the second terminal of the first activated one (521) of the first stage's bidirectional shift registers, via the fourth terminal, and then sequentially outputting the formed symbol streams via the fourth terminal."

The text of the remaining claims is not relevant to this decision.

Reasons for the Decision

1. The appeal complies with the provisions referred to in Rule 101 EPC and is therefore admissible.

2. The invention

2.1 The application relates to the decoding of turbo codes. Its background section discusses in detail the components and functioning of a conventional Soft-In Soft-Out (SISO) turbo decoder that uses a conventional sliding-window scheme. Such turbo decoders include a memory buffer which must operate at a rate that - in the case of two windows - is three times faster than the operating frequency of the turbo decoder. This is because, in each clock cycle of the turbo decoder, three delta metric calculators need to access the memory at three different addresses (see page 7, line 10, to page 8, line 27, and Figures 3, 6 and 7 of the application as filed).

2.2 The invention aims to provide a memory buffer for use in a turbo decoder that operates at the same rate as the turbo decoder (see page 18, line 23, to page 19, line 9).

This is achieved by inserting, between the memory buffer 46-10 and the decoder, a "high-rate memory buffer" 260 (see Figure 8) that reads the bits from the memory buffer 46-10 in the normal order and rearranges and outputs those bits in exactly the order required by the delta metric calculators of the turbo decoder (see page 23, lines 17 to 22). This allows the memory buffer 46-10 to operate at the same clock rate as the turbo decoder. The "high-rate memory buffer" 260 is made up of a number of shift registers and also operates at the same clock rate as the turbo decoder (so not at a "high rate").

3. Claim 1 - added subject-matter and clarity

3.1 Independent claim 1 is directed to the embodiment of the memory buffer 260 depicted in Figure 9:

FORMULA/TABLE/GRAPHIC

3.2 As explained on page 20, line 9, to page 26, line 4, this memory buffer functions as follows.

Input "data bits" (from memory buffer 46-10) are applied to the shift register 310 and to the N shift registers 321 to 323, where N is the number of windows used in the sliding-window scheme. Since the memory buffer is to provide data to a SISO decoder, these "data bits" are not binary values but "soft" values representing the likelihood that a bit is a zero or a one. Claim 1 therefore uses the term "symbol" instead of "data bit".

The shift register 310 is a unidirectional shift register of size 2NW, where W is the size of each window. The symbols it receives are shifted into the register. The symbols that are shifted out of the register are applied to the delta metric calculator connected to the alpha metric calculation section of the turbo decoder.

Each of the N shift registers 321 to 323 is a bidirectional shift register of size NW. The control logic activates these N registers one after the other at intervals of W received symbols.

Once a bidirectional shift register has been activated, the first NW symbols it receives are shifted into the register from left to right. The shift register then changes direction under the control of the control logic, which means that the "second" next NW symbols it receives are shifted into the register from right to left, and so on. Any symbols shifted out of the shift register are applied to the delta metric calculator connected to the beta metric calculation section for the corresponding window.

3.3 Claim 1 is based on original claim 1 with the following amendments taken from the description.

The memory buffer includes control logic 330, the shift register 310 is unidirectional, and the N shift registers 321 to 323 are bidirectional (see page 20, lines 11 to 13).

The control logic 330 controls the sequential activation of the shift registers 321 to 323 (page 24, line 24, to page 25, line 2). It also provides select signals to the select terminal of each of the bidirectional shift registers to control whether "first NW symbols" are applied to the first input terminal or "second NW symbols" to the second input terminal (page 22, lines 10 to 18).

3.4 The Examining Division appears to have been of the view that claim 1 has to include features corresponding to the demultiplexer (DEMUX) and multiplexer (MUX) components shown in Figure 9 for it to comply with Articles 84 and 123(2) EPC.

The Board does not consider this to be necessary. The demultiplexers in Figure 9 apply received symbols to the input terminal on the left of a bidirectional shift register if the register is shifting from left to right and to the input terminal on the right otherwise. The multiplexers likewise apply symbols shifted out of a bidirectional shift register from the correct output terminal to the delta metric calculator. These components hence constitute minor details of the implementation of functionality which is already specified in claim 1. The multiplexers and demultiplexers are therefore not essential to a clear definition of the invention within the meaning of Article 84 EPC. Moreover, since they were not present in original claim 1, their absence from present claim 1 requires no justification under Article 123(2) EPC.

3.5 Although not formally raising a clarity objection, in its decision with respect to the then main request, the Examining Division took issue with the claim expressions "configured by means of a control logic to receive first NW data bits" and "configured by means of the control logic to be sequentially activated at intervals". It appears to have considered that for a bidirectional shift register to be configured by means of the control logic "to receive first NW data bits" and "to be sequentially activated at intervals", the shift register needs to include means for counting data bits (or symbols), which is not the case for conventional shift registers and is not expressed in the claim.

However, it is clear from these very claim expressions and the fact that a conventional shift register does not include counting means that it is the control logic that performs the necessary counting and controls the bidirectional shift registers accordingly.

3.6 The clarity objections raised in the Board's communication against independent claim 1 of the then main request no longer apply to present claim 1.

3.7 It follows that present claim 1 is clear (Article 84 EPC) and that its subject-matter is disclosed in the application as filed (Article 123(2) EPC).

4. Claim 7 - added subject-matter and clarity

4.1 Independent claim 7 is directed to the embodiment of the memory buffer 260 described on page 33, line 20, to page 37, line 25, and depicted in Figure 17 (for N=2):

FORMULA/TABLE/GRAPHIC

4.2 The memory buffer of Figure 17 differs from that of Figure 9 in that the unidirectional shift register 310 of size 2NW is replaced with the bidirectional shift register 510 of size NW. The shift register 510 receives, as input, the symbols that are output by the bidirectional shift register 521, which is the bidirectional shift register that is activated first.

The shift register 521 reverses the order of both the first and the second NW symbols it receives. The bidirectional shift register 510 does the same and thereby cancels the reversals. As a consequence, the bidirectional shift register 510 outputs the same symbols in the same order to the delta metric calculator for the alpha metric calculation section as the unidirectional shift register 310 in Figure 9.

4.3 Although claim 7 is worded differently from claim 1, the Board is satisfied that it also defines the essential features of the invention in clear terms. In particular, the claim defines the ("second stage's") bidirectional shift register 510 and its functionality, the N ("first stage's") bidirectional shift registers 521 and 522 and their functionality and sequential activation, and the control of the shift registers by the control logic. The clarity objections raised in the Board's communication against then independent claim 8 of the main request no longer apply to present claim 7.

4.4 Since the embodiments of Figures 9 and 17 involve alternative solutions to a particular problem which cannot easily be covered by a single claim, independent claim 7, which is in the same category as independent claim 1, does not infringe Rule 43(2) EPC.

4.5 Hence, present claim 7 also complies with Articles 84 and 123(2) EPC.

5. Inventive step

5.1 The memory buffers of claims 1 and 7 consist of specific arrangements of shift registers and control logic that allow the buffers to be used in conjunction with a sliding-window SISO turbo encoder, obviating the need for a conventional memory buffer that operates at a rate that is three (or more) times higher than the operating rate of the turbo decoder (see point 2 above).

5.2 Document D1 merely confirms that conventional unidirectional and bidirectional shift registers were known in the art. It is not a suitable starting point for assessing inventive step of the claimed invention.

5.3 Document D2, which is prior art under Article 54(2) EPC only if the invention does not validly claim priority, relates to a turbo decoder using a sliding-window scheme (see abstract and paragraph [0010]). It explains that this decoding scheme requires multiple simultaneous memory accesses at different addresses and discloses a conventional turbo decoder system with four sliding windows employing a dual-port main memory and an eight-block beta memory (paragraph [0018] to [0021]; Figure 9). It proposes an alternative memory control solution for a turbo decoder with four sliding windows consisting of a single-port main memory, a scratch memory and a four-block beta memory (paragraph [0022]; Figure 14). It makes no mention of shift registers.

5.4 Document D3 presents VLSI architectures suitable for implementing a turbo decoder (see abstract). It explains, in section II, the turbo-decoding algorithm including the sliding-window modification (page 370, right-hand column, lines 4 to 8). The general architecture of a SISO turbo decoder is described in section III, with specific implementations being discussed in section IV. Paragraph B of section IV mentions the use of (unidirectional) shift registers in the context of a "Full-Speed SISO Architecture" as depicted in Figure 6, which - unlike the decoder architecture of the present application - employs a separate beta metric calculation section for each symbol in a window. More efficient architectures in terms of hardware resources are described in paragraphs C and D of section IV and shown in Figures 7 to 9. The architecture corresponding to Figures 8 and 9 employs three separate RAM memories to store branch metrics. Shift registers are not mentioned.

5.5 Document D4 is a tutorial on turbo codes. It does not mention the sliding-window decoding scheme.

5.6 Document D5 studies the performance of a turbo decoder that uses a sliding-window scheme. It briefly discusses the memory requirements of sliding-window decoders in section 6 but does not describe any memory architectures for supplying data to the delta metric calculators of the decoder.

5.7 In view of the above analysis, there is nothing in the cited prior art that could have led the skilled person, looking for an efficient memory architecture for supplying data to the delta metric calculators of a sliding-window turbo decoder, to the specific arrangements of shift registers and control logic defined by claims 1 and 7.

5.8 Hence, the subject-matter of claims 1 and 7 involves an inventive step (Article 52(1) and 56 EPC).

6. Remittal

The amendments made in the oral proceedings to independent apparatus claims 1 and 7 of the main request as filed with the letter of 2 May 2019 have rendered these claims allowable. Suitable amendments may still have to be made to the remaining claims, including independent method claims 14 and 18, and to the description. The case is therefore to be remitted to the Examining Division for further prosecution, to which course of action the appellant did not object.

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 for further prosecution.

Quick Navigation