TECHNICAL FIELD

The present invention generally relates to the field of interleaver design, and specifically relates to an interleaver and to an interleaving method having a band structure. The present invention relates further to obtaining such an interleaver and using such an interleaver in a communication system, e.g. for channel encoding and decoding.

BACKGROUND

In the followings, the background regarding delay or latency in communication systems and its relation to cannel codes is presented.

In each communication system, there is a delay or latency caused by the channel encoder or decoder. Depending on the application, the delay may have a big influence on the quality of service (QoS) and the quality of experience (QoE). There are several causes for such a delay in communication systems. A structural delay may be seen as the cause of the latency that depends on the system design and not on the processing power and memory of transmitter or receiver. One aspect that causes large structural delay is the block-wise processing of the signals in the transmitter and receiver chains. Especially, forward error correction (FEC) schemes cause large structural delays.

In general, the channel decoder requires coded symbols corresponding to the whole codeword in order to start the decoding operation. Coded symbols may relate to both binary and non- binary symbols, wherein in case of a binary code, a symbol is a bit. Hence the decoder cannot start as long as the whole codeword is not received. For long codewords, this may cause a large delay.

Certain channel codes have special structures that allow the decoder to start the decoding operation even if the whole codeword is not available. This kind of codes may be decoded with a so-called sliding window decoder (SWD), where the availability of only a part of the codeword is enough to start the decoding process.

If a sliding window decoder SWD is used, the decoding is performed over the symbols within a window, said window having a length w. After the decoding of m targeted symbols inside the window (m <vv) is completed, the window is shifted to a new location, where new targeted symbols are then decoded. This procedure is repeated until the whole codeword is decoded. Despite its sub-optimality in terms of error correction performance, the sliding window decoder SWD allows more flexibility in latency: The decoder may indeed start decoding the first targeted symbols as soon as the symbols within a certain window are available.

Convolutional codes may be given as an example for codes that may be decoded with a sliding window decoder SWD, wherein each encoded symbol only depends on certain previously encoded symbols. Another example of convolutional codes may be the low-density parity-check convolutional codes (LDPC-CC) that have a parity check matrix with a band diagonal structure, which also allows using a sliding window decoder SWD. LDPC-CC is known for example from A. J. Felstrom, and K. S. Zigangirov, "Time- varying periodic convolutional codes with low-density parity-check matrix" IEEE Transactions on Information Theory, 45.6 ( 1999): 2181 -2191.

In the followings, the background regarding interleavers is presented.

An interleaver is a deterministic function that takes a sequence as input and outputs the same sequence with a different order. Interleaving is a technique that is usually used to improve the performance of channel codes.

An interleaver of length k, in particular a block interleaver, can be described by a bijective function f(j) with j and f(j) taking integer values from 0 to k— 1. The function f(j) defines the order that the samples or symbols are read from the input vector, i.e., the / ^h output of the interleaver is read from the location /(/) in the input vector.

In the followings, the background regarding turbo codes is presented. Turbo codes, as parallel concatenated convolutional codes, are powerful error correction codes first introduced in C. Berrou, A. Glavieux. "Near optimum error correcting coding and decoding: Turbo-codes", IEEE Transactions on Communications, 44.10 ( 1996): 1261 -1271.

The encoder of a turbo code used e.g., in 3GPP WCDMA or LTE, consists of two

convolutional encoders (constituent encoders), and an interleaver /(. ).

Known interleavers used in turbo codes, i.e. the turbo interleavers, are usually designed in a way such that the input is shuffled as much randomly as possible. It is indeed desired to have interleavers with large spread factors. The spread Sf of an interleaver with interleaving function is defined as the minimum distance of any two different indices: where is the distance metric between the indices i and j defined as:

For turbo codes, usually interleavers with large spreads are desired due to their better error correction performance. Therefore, during the design of an interleaver for a turbo code, one normally tries to build interleavers where the spread is maximized.

For example, an LTE turbo code is constructed using two constituent convolutional codes with 8 states, i.e. with the generators 15 and 13 (in octal) for feedforward and feedback, respectively. As interleaver, the quadratic permutation polynomials (QPP) in the form /(/) = mod k is used, where k is the interleaver length and mod is the modulo operation.

The parameters and k are specified in 3 GPP Technical Specification, TS 36.212 vl2.6.0,

2015.

The decoder of a turbo code consists of two Soft-In-Soft-Out (SISO) decoders, i.e. one SISO decoder for each constituent convolutional code. The two SISO decoders are connected via an interleaver and a deinterleaver

The decoding operation occurs in an iterative way, such that extrinsic information is exchanged between the constituent decoders during each iteration.

However, turbo codes in general cannot be decoded with a sliding window decoder SWD. Indeed, the interleaver and the deinterleaver connecting both SISO decoders make the use of a sliding window decoder SWD impossible or at least difficult. It has to be noted that the sliding window decoder SWD may be used to decode the constituent convolutional codes, however the focus here is the sliding window decoding of the turbo codewords. If a sliding window decoder SWD is used with a turbo code, the following problem occurs. Assume a window with w symbols, where the first m symbols are the targeted symbols. The first SISO decoder may process the first w symbols and produce extrinsic information about those symbols. However, after interleaving, these symbols are usually interleaved to locations that are outside the window. Similarly, the interleaver might require input from symbols outside the window to feed in to the second SISO decoder. Therefore, the extrinsic information exchange is limited due to the interleaving operation, and a window decoding is not possible.

SUMMARY OF INVENTION

Having recognized the above-mentioned disadvantages and problems, the present invention aims to improve the state of the art. In particular, the object of the present invention is to provide an improved interleaver with the distance between input sequence and output sequence limited in a pre-defined range, so that turbo codes can be interleaved in such way that it can be decoded by using sliding window decoding. In this way, a latency caused by interleaver and decoding can be reduced.

The above-mentioned object of the present invention is achieved by the solution provided in the enclosed independent claims. Advantageous implementations of the present invention are further defined in the respective dependent claims.

A first aspect of the present invention provides an interleaver, parti cularly for channel coding, for mapping an input sequence of k indexed input symbols to an output sequence of k indexed output symbols, k being a positive integer, comprising means for mapping an input index of the input sequence to an output index of the output sequence according to an interleaving function,

wherein, for the input indices b, ...,k-b-\ , b being a nonnegative integer smaller than k/2 (excluding the first and the last b indices), a distance between the input index and the output index defined by the interleaving function is smaller than or equal to a threshold p, p being a positive integer smaller than k. Typically, b≤ [fc/4] where f. ] denotes the ceiling operator.

This also implies the same property for the corresponding deinterleaver, since the

deinterleaver can be defined by the inverse of the interleaving function, i.e., it is an interleaver with the interleaving function / ^{~ 1} (. ) .

Thereby, the interleaver is advantageous in that it shows a band structure, such that a sliding window decoder may be used for a decoder for reducing the decoder latency. The interleaver may particularly be an interleaver for a channel encoder or decoder, especially as for forward error correction (FEC).

The k input symbols of the input sequence are indexed in that the order of the k input symbols in the input sequence is determined by respective input indices. In other words, the k input symbols have an order that is determined by their respective input index. Similarly, the k output symbols of the output sequence are indexed in that the order of the k output symbols in the output sequence is determined by respective output indices. In other words, the k output symbols have an order that is determined by their respective output index.

In an implementation form of the interleaver, the interleaver is configured for turbo codes or turbo codewords.

In an implementation form of the interleaver, the distance between the input index and the output index defined by the interleaving function is smaller than or equal to the threshold p for all k input indices.

Particularly, the distance between the input index and the output index may relate to the absolute value of the difference between the input index and the output index. Particularly, the interleaving function may fulfill the condition for all k input

indices,

wherein is the input index, and j is the output index. The same condition is also fulfilled

for the deinterleaver, as a deinterleaver is an interleaver with the interleaving function In fact, it can be shown that when . Therefore, we may not di fferentiate unless otherwise stated.

In an implementation form of the interleaver, the distance between the input index and the output index defined by the interleaving function is smaller than or equal to the threshold p only for a subset of all k input indices.

Particularly, the distance between the input index and the output index may relate to the absolute value of the difference between the input index and the output index.

A second aspect of the present invention provides an interleaving method, particularly for channel coding, for mapping an input sequence of k indexed input symbols to an output sequence of k indexed output symbols, k being a positive integer,

comprising mapping an input index of the input sequence to an output index of the output sequence according to an interleaving function,

wherein, for the input indices b, ...,k-b-\ , b being a nonnegative integer smaller than k/2 (excluding the first and the last b indices), a distance between the input index and the output index defined by the interleaving function is smaller than or equal to a threshold p, p being a positive integer smaller than k. Typically, b≤ ffc/4] where [. | denotes the ceiling operator.

A third aspect of the present invention provides a channel encoder comprising at least one interleaver according to the first aspect of the present invention.

Particularly, the channel encoder may be a turbo encoder.

Particularly, the interleaver may be used in any channel code that can be decoded with the turbo principle. This includes the classical turbo codes, i.e. parallel concatenated

convolutional codes, as well as other types of codes like repeat-accumulate codes (Jin, Hui, Aaniod Khandckar, and Robert McEliece. "Irregular repeat-accumulate codes." Proc. 2nd Int. Symp. Turbo codes and related topics. 2000.),, accumulate-repeat-accumulate codes (Abbasfar, Aliazam, Dariush Divsalar, and Kung Yao. " A ccumul at e-repeat-accumul ate codes." IEEE Transactions on Communications 55.4 (2007): 692-702) and other kind of serial and parallel concatenated codes connected via an interl eaver where the constituent codes may be any block code or convolutional code. Moreover, the proposed interleavers may also be used as interleavers between the channel code and the symbol mapper in any bit interleaved coded modulation (BICM) system (Caire, Giuseppe, Giorgio Taricco, and Ezio Biglieri. "Bit- interleaved coded modulation," IEEE Transactions on Information Theory, 44.3 (1998): 927- 946), where the second constituent code is a symbol mapper. Note that in a "general turbo code", a constituent code can be any channel code, including the conventional turbo code, convolutional code, LDPC code, or LDPC-eonvolutional code.

In an implementation form of the channel encoder for encoding the input sequence into an encoded sequence, the channel encoder is a turbo encoder further comprising:

- first and second constituent encoders,

the first constituent encoder being adapted to generate a first constituent codeword from the input sequence, and

the second constituent encoder being adapted to generate a second constituent codeword from the output sequence of the interl eaver, and

- a combination unit adapted to combine the input sequence, the first constituent codeword and the second constituent codeword into the encoded sequence.

In an implementation form of the channel encoder, the channel encoder comprises:

- an identification unit adapted to identify, from among all k input indices, the input indices for which the distance between the input index and the output index defined by the

interleaving function is above the threshold p, and

- a computing unit adapted to set to known symbols the input symbols located at the identified input indices in the input sequence.

In an implementation form of the channel encoder the channel encoder comprises:

- an identification unit adapted to identify, from among all k input indices, the input indices for which the distance between the input index and the output index defined by the

interleaving function is above the threshold p, and

- a puncturing unit adapted to puncture the identified input indices in the encoded sequence. A fourth aspect of the present invention provides a channel decoder for decoding a received encoded sequence codeword into a sequence of decoded symbols,

comprising at least one interleaver according to the first aspect of the present invention.

In an implementation form of the channel decoder for decoding a received encoded sequence into a sequence of decoded symbols, the channel decoder is a turbo decoder further comprising a first and a second concatenated constituent decoders,

the first and second constituent decoders being connected by the interleaver.

In an implementation form of the channel decoder, the first and second constituent decoders are sliding window decoders.

In an implementation form of the channel decoder, the first constituent decoder is adapted to perform soft output decoding of the received encoded codeword so as to generate the sequence of decoded symbols and a first extrinsic information, and

the second constituent decoder is adapted to perform soft output decoding of the received encoded codeword so as to generate second extrinsic information,

wherein the interleaver is adapted to map the first extrinsic information to side information for the second constituent decoder, and

a deinterleaver is adapted to map the second extrinsic information to side information for the first constituent decoder according to the opposite function of the interleaving function.

In an implementation form of the channel decoder, the channel decoder is adapted to decode an encoded sequence encoded by a channel encoder according to the third aspect of the present invention in that the first and second constituent decoders of the channel decoder are adapted to use perfect a-priori information about the known symbols. Particularly, the first and second constituent decoders of the channel decoder are adapted to use perfect a-priori information about the known symbols set by the computing unit of the channel encoder.

A fifth aspect of the present invention provides a method for obtaining the interleaving function according to any of the claims 1 to 5, said interleaving function being adapted to be used in a turbo encoder or turbo decoder,

the method comprising: - randomly or pseudo-random ]y generating a plurality of input interleaving functions respectively satisfying the condition that, for at least a subset of the set of all k input indices, a distance between the input index and an output index defined by the input interleaving function is smaller than or equal to the threshold p,

wherein k is a positive integer and p is a positive integer smaller than k,

- selecting the best performing interleavers in terms of the performance of turbo coding from the generated input interleavers, and

- choosing one of the selected interleavers so as to obtain the interleaving function.

A sixth aspect of the present invention provides a method that may be referred to as s-random construction method for obtaining the interleaving function according to any of the claims 1 to 5, said interleaving function being adapted to be used in a turbo encoder or turbo decoder, the method comprising:

- A. defining a set } of all k indices, and setting/-^, and

the method further comprising recursively performing following steps:

- B. selecting from the set / an input value (index) A fulfilling the following criteria:

- C. defining the interleaving function / so as to map the input value to the output

value j,

- D. removing the selected input value A from the set /.

- E incrementing y by 1 and repeating the steps starting from step B, unless j equals k-1.

Particularly, the steps B to E are performed recursively until the input set / is empty. In this case, the distance between the input index and the output index defined by the interleaving function is smaller than or equal to the threshold p for all k input indices.

Alternatively, the steps B to E are performed recursively until no input value A from the input set / fulfils the criteria i. and ii., wherein the input set / is not empty. In such a case, the steps B to E may be further performed recursively by ignoring the condition ii . In this case, the distance between the input index and the output index defined by the interleaving function may be smaller than or equal to the threshold p only for a subset of all k input indices. Alternatively, the steps B to E are performed recursively until no input value A from the input set / fulfils the criteria i. and ii., wherein the input set / is not empty. In such a case, the interleaving function is obtained by performing again the step A and the recursive steps B to

E.

A seventh aspect of the present invention provides a method that may be referred to as base interleaver construction method for obtaining an interleaving function , said interleaving

function being adapted to be used in a turbo encoder (100) or turbo decoder (200), the method comprising:

- providing a positive integer parameter L and a base interleaver of length ' defined by a

corresponding base interleaver function ' being a positive integer,

- building a helper function with being an

integer, and

- constructing the interleaving function according to the equation:

Particularly, the base interleaver may be chosen as an LTE turbo interleaver.

Particularly, the helper function may be chosen according to the following equation:

wherein . Here, c= is the subset or equal to operator. In this case, the

obtained interleaving function defines a zigzag-window interleaver.

Particularly, the helper function may be chosen according to the following equation:

wherein are two non-overlapping subsets of defined as either:

and logical and operators, respectively. In this case, the obtained interleaving function defines a smoothed window interleaver. An eight aspect of the present invention provides an interleaving device comprising:

a serial to parallel converter to write the input sequence to a matrix M of size L by k \ a base interleaver to be applied on each row of M, where the output is written to the corresponding rows of a matrix R of the same size,

a cyclic shift operator to be applied on each column of R in the vertical dimension to obtain a matrix S of the same size where the shift values tj for each column is determined by the integers tj, j=0, ... ,/c '- 1 ,

a parallel to serial converter to read the matrix S row by row to generate the interleaved output of length k'L.

Particularly, the base interleaver may be chosen as LTE interleaver.

Particularly, the base interleaver may be a Quadratic Permutation Polynomial (QPP) interleaver.

A ninth aspect of the present invention provides a channel encoder for encoding an input sequence into an encoded sequence,

the channel encoder comprising at least one interleaver,

wherein the interleaver is defined such that the encoded sequence is adapted to be decoded by a channel decoder comprising concatenated constituent decoders in the form of sliding window decoders.

A tenth aspect of the present invention provides a computer program having a program code for performing the method according to the second, fifth, sixth or seventh aspect of the present invention, when the computer program runs on a computing device.

It has to be noted that all devices, units and means described in the present application could be implemented by software or hardware elements or any kind of combination thereof. All steps which are performed by the various entities described in the present application as well as the functionalities described to be performed by the various entities are intended to mean that the respective entity is adapted to or configured to perform the respective steps and functionalities. Even if, in the following description of specific embodiments, a specific functionality or step to be full formed by eternal entities not reflected in the description of a specific detailed element of that entity which performs that specific step or functionality, it should be clear for a skilled person that these methods and functionalities can be implemented in respective software or hardware elements, or any kind of combination thereof.

BRIEF DESCRIPTION OF DRAWINGS

Fig. 1 shows a turbo encoder according to an embodiment of the present invention,

Fig. 2 shows a turbo decoder according to an embodiment of the present invention,

Fig. 3 shows a turbo encoder according to a further embodiment of the present invention,

Fig. 4 shows a turbo decoder according to a further embodiment of the present invention,

Fig. 5 shows an interleaving function of an interleaver according to the state of the art,

Fig. 6 shows an interleaving function of an interleaver according to an embodiment of the present invention,

Fig. 7 shows an interleaving function of an interleaver according to another embodiment of the present invention,

Fig. 8 shows a zigzag window interleaver according to an embodiment of the present invention,

Fig. 9 shows a smoothed window interleaver according to an embodiment of the present invention,

Fig. 10 shows a smoothed window interleaver according to another embodiment of the present invention,

Fig. 1 1 shows a sliding window decoding according to an embodiment of the present invention, Fig. 12 shows performance results of wi-turbo codes with smoothed window interleavers according to an embodiment of the present invention,

Fig. 13 shows performance results of wi-turbo codes with zigzag window interleavers according to an embodiment of the present invention,

Fig. 14 shows performance results of wi-turbo codes with smoothed-window interleavers according to an embodiment of the present invention,

Fig. 15 shows possible gains due to the flexible latency adjustment according to the present invention, and

Fig. 16 shows an interleaving device with an interleaving function according to an embodiment of the present invention.

DETAILED DESCRIPTION OF EMBODIMENTS

The present invention will be explained in details in the following.

The present invention proposes an interleaver, particularly for channel coding, for mapping an input sequence of k indexed input symbols to an output sequence of k indexed output symbols, k being a positive integer.

The interleaver comprises means for mapping an input index of the input sequence to an output index of the output sequence according to an interleaving function. For at least a part of all k input indices, a distance between the input index and the output index defined by the interleaving function is smaller than or equal to a threshold p, k and the threshold p being positive integer.

The k input symbols of the input sequence are i ndexed in that the order of the k input symbols in the input sequence is determined by respective input indices. In other words, the k input symbols have an order that is determined by their respective input index. Similarly, the k output symbols of the output sequence are indexed in that the order of the k output symbols in the output sequence is determined by respective output indices. In other words, the k output symbols have an order that is determined by their respective output indices.

The means for mapping may e.g. be a computing unit adapted to map the input index of the input sequence to the output index of the output sequence according to the interleaving function.

The input symbols and output symbols of the respective input sequence and output sequence may be values or coded symbols related to either binary and non-binary codes. Particularly, in case of a binary code, a symbol may be a bit.

The threshold p may be a positive integer. The threshold p may be set such that 2p+l is smaller than the value k, the value k reflecting the total length of input sequence or the total number of input symbols of the input sequence. In other words, the threshold p may verify or fulfill the equation p<(k- \ )/2, with p and k being positive integers. To achieve low latency, p can be typically chosen as p<(k- \ )/4.

The proposed interleaver may be an interl eaver for turbo codes, i.e. a turbo code interl eaver.

Figs. 1 and 2 show two embodiments for using the interl eaver according to the present invention.

Fig. 1 shows a turbo encoder 100 according to an embodiment of the present invention. The turbo encoder 100 comprises an interleaver 104 according to the present invention.

Particularly, Fig. 1 shows the interleaver 104, particularly for channel coding, for mapping an input sequence 101 of k indexed input symbols to an output sequence 105 ot ^' k indexed output symbols, k being a positive integer.

The interleaver 104 comprises means for mapping an input index of the input sequence 101 to an output index of the output sequence 105 according to an interleaving function. For the input indices b, ... ,k-b-\ , (b being a nonnegative integer smaller than k/2), a distance between the input index and the output index defined by the interleaving function is smaller than or equal to a threshold p, p being a positive integer smaller than k. The said means may be implemented through a module, unit or on a software basis.

The input of the turbo encoder 100 is the sequence of information symbols to be encoded 101 corresponding to the input sequence 101 of k indexed input symbols. Output of the encoder contains systematic symbols 101 - i.e. the sequence of information symbols itself-, parity symbols 103 generated by a first constituent encoder 102, and parity symbols 107 generated by a second encoder 106 after interleaving 104.

The turbo encoder 100 is adapted to encode the input sequence 101 into an encoded sequence or codeword 109. The turbo encoder 100 comprises the interleaver 104, as well as first 102 and second 106 concatenated constituent encoders. The first constituent encoder 102 is adapted to generate a first constituent codeword 103 from the input sequence 101, and the second constituent encoder 106 is adapted to generate a second constituent codeword 107 from the output sequence 105 of the interleaver 104.

The turbo encoder 100 also comprises a combination unit, like a serial/parallel unit 108, adapted to combine the first constituent codeword 103 and the second constituent codeword 107 into the encoded sequence 109. Particularly, the combination unit 108 may be adapted to combine the input sequence 101 , the first constituent codeword 103, and the second constituent codeword 107 into the encoded sequence 109.

Particularly, the first and second constituent encoders 102, 106 of the turbo encoder 100 may be respectively in the form of convolutional encoders as shown in Fig. 1.

Fig. 2 shows a turbo decoder 200 according to an embodiment of the present invention. The turbo decoder 200 comprises an interleaver 205 according to the present invention.

Particularly, Fig. 2 shows the interleaver 205, particularly for channel coding, for mapping an input sequence 204 of k indexed input symbols to an output sequence 206 of k indexed output symbols, k being a positive integer.

The interleaver 205 comprising means for mapping an input index of the input sequence 204 to an output index of the output sequence 206 according to an interleaving function. For the input indices b,...,k-b-l, (b being a nonnegative integer smaller than k/2), a distance between the input index and the output index defined by the interleaving function is smaller than or equal to a threshold p, the threshold p being a positive integer smaller than k. The said means may be implemented through a module, unit or on a software basis.

The input of the turbo decoder 200 is the received symbols 201 in form of reliability values, e.g. log-likelihood values or L-values, or soft values. The output 210 corresponds to the decoded symbols.

The turbo decoder 200 comprises first and second constituent decoders 202, 203 that are connected by the interleaver 205. The two constituent decoders 202, 203 are also connected by a de-interleaver 208 corresponding to interleaver 205, i.e. being the opposite of the interleaver 205. The two constituent decoders 202, 203 perform a soft output decoding, and generate respective extrinsic information 204, 207 about each symbol of the information sequence 201.

The extrinsic information 204 of the first constituent decoder 202 is then interleaved by the interleaver 205 and fed 206 to the second constituent decoder 203 as side information.

Likewise, the extrinsic information 207 of the second constituent decoder 203 is de- interleaved by the de-interleaver 208 and fed 209 to the first constituent decoder 202 as side information. The respective extrinsic information 204, 207 of one constituent decoder is fed iteratively to the other constituent decoder.

This iterative procedure is repeated a certain amount of times before making a final decision on the decoded symbols 210. If decoding is successful, the decoded symbols 210 are equivalent to the transmitted information sequence 101.

The channel encoder and channel decoder of Figs. 1 and 2 comprise respectively constituent encoders 102, 106 and constituent decoders 202, 203 that are parallel concatenated.

Specifically, Figs. 1 and 2 show parallel concatenated turbo codes in form of parallel concatenated binary convolutional codes.

The invention is also applicable to channel encoder and channel decoder having alternative structures, see for example Figs. 3 and 4. For example, the invention is also applicable to non- binary and/or to serially concatenated codes. Also the invention may be used with parallel or serially concatenated codes containing more constituent codes, i.e. containing more than the two constituent encoders 102, 106 of Fig. 1 and more than the two constituent decoders 202, 203 of Fig. 2. A parallel or serial concatenated code according to the invention may then be a turbo code consisting of at least two constituent codes and at least one interleaver. The intcrleaver may be referred to as the turbo interleaver.

In the followings, the structural delay or latency of channel encoders and decoders according to the present invention is presented with respect to the structural delay or latency of known channel encoders and decoders.

It is assumed that the symbols are the input 101 to the channel encoder 100, and

the symbols are the output 109 of the channel encoder, i.e. the encoded sequence

109, or the input 201 of the channel decoder 200, i.e. the received encoded sequence 201, wherein k and n are time indices and R = K/N is usually called the channel code rate and K and N are positive integers. According to the state of the art, to produce the encoded sequence, all of the K symbols of the input sequence have to be available at the input of the channel encoder, such that the N encoded symbols can be generated. This may cause a large delay if the input sequence is long.

The present invention is advantageous in that the encoded symbols c, may be generated even if only a part of the input sequence is available. We make the following definitions. The output symbol c _n is called the delay-d and window-w encoded, if c„ may be generated using with Further on, when c„ is delay-d and window-w encoded for all n, then the channel code is called delay-d and window-w

encodable, and the corresponding encoder is called delay-d and window-w encoder.

Obviously, if a code is delay-d and window-w encodable, then it is also d and window-(w+l) encodable. Since we are interested only in the minimum of d and w, unless otherwise stated, the delay-i/ and window-w encodable channel code is referred to as the code which is not delay -(d- 1) and window-(w-l) encodable. Thus, without considering the processing delay, the delay d is dependent only on the structural delay of the channel encoder.

Similar definitions can be made for the decoders, too. The symbol bk is called the delay-d and window-w decodable, if b* can be decoded using with w > d≥ 0. Further on, when b _k is delay-d and window-w decodable for all k, the channel code is called the delay-d and window-w decodable, and the corresponding decoder is called the delay-d and window-w decoder. Since any delay-d and window-w decodable code is also delay-(d+l) and window-(w+J) decodable, unless otherwise stated, d and w are the minimum delay d and window w of the delay-d and window-w code, respectively. With unlimited processing power and memory, and for a given channel and a target decoder performance (e.g. BER or BLER), the delay d is dependent only on the structural delay of the channel decoder, and may serve as a structure delay parameter.

For example, a known non-recursive convolutional encoder may consist of s memory elements - shift registers - and the output at each time instant may be a linear combination of the values in the memory elements. The input sequence is fed to the memory elements and shifted by one symbol after the outputs are generated. Due to this structure, one can say that a non-recursive convolutional code with s memory elements is delays windows encodable. Recursive convolutional codes are similar to non-recursive codes, except their output may also depend on the previous outputs due to the feedback connection. For recursive convolutional codes, the encoding delay is the same as the non-recursive codes, but as the output depends also on the previous outputs, the window size may be regarded as infinity. In general, one can decode a convolutional code with the same delay and window parameters as they are required for the encoding, i.e., if no errors are occurred during the transmission, the symbols can be decoded correctly with the same delay as the encoding delay. This corresponds to making a decision on the decoder output after the reception of each trellis section of the Viterbi decoder. However, as the channel conditions degrade, this would decrease the error correction performance. To improve the performance, one usually makes the decision after receiving τ trellis segments. Therefore, the decoder can be regarded as delay-is window-is decoder.

For example, for known encoders and decoders, the turbo codes respectively use

unconstrained interleavers, such that the input and the output order of the interleaver may be arbitrary. Therefore, a known encoder requires the whole input sequence in order to produce its encoded sequence. Similarly, a known decoder requires the whole input sequence in order to start decoding. With these constraints, one can say that a turbo code is delay-k window-k encodable and delay-k window-k decodable. It can be noted that in general the constituent codes of a turbo code can be any kind of codes (like block codes or convolutional codes), however one usually uses convolutional codes as constituent codes with parallel concatenated turbo codes due to their advantages such as performance and simplicity.

The invention proposes particularly a new interleaver, a new channel encoder and channel decoder and new turbo codes generated by using the new interleaver having band

characteristics. Such kind of turbo codes according to the present invention may be called window interleaved turbo codes, i. e. Wi -Turbo or wi-turbo codes. The proposed interleaver having band structure or properties may be referred to as Window Interleaver.

The concept of delay-d and window-w encoder can be extended to many devices, including the (de)interleavers. In their most general case, an interleaver of length k can be interleavcd/deinterleaved with a delay of k symbols. 1 lowever, interleavcrs with special structures (such as window interleavcrs, WI) can be (de)interleaved with smaller delay values.

The proposed new Wi -Turbo codes provide better performances with regard to the

conventional turbo codes approaching the theoretical bounds. Moreover, due to the proposed interleaver structure, such as the band interleaver structure, the Wi -Turbo encoder or decoder has a reduced structural latency or delay, i.e. a reduced waiting time for encoding or decoding. The proposed new coding method allows the generated codewords to be encoded or decoded using a sliding window encoder or decoder. In other words, their encoding or decoding time is dependent on the chosen WI parameters. Moreover, Wi -Turbo codes are more flexible in supporting rate matching and incremental redundancy, compared to other modern codes such as the LDPC-CC.

The proposed Wi-turbo codes according to the present invention have special interleavcrs, like window interleavers, that allow them to be decoded using a sliding window decoder. A window interleaver is defined by the parameter p that defines the maximum distance between the input and the output of the interleaver. Therefore, assuming that the convolutional encoders of the turbo code, i.e. of the turbo encoder, has s memory elements, the encoding delay of the wi-turbo codes can be regarded as s+p<k. Note that s is usually small compared to p and can be neglected.

The main advantage of the present invention, i.e. of the wi-turbo codes compared to conventional turbo codes is their suitability to sliding window decoder (SWD). If an SWD is used, the decoding latency can be as small as p symbols, similar to the encoder. However to obtain good error correction performance, one usually defines a number of target symbols m - number of symbols to be decoded in each window - and chooses a window of size greater than m+p. Experimental evaluations suggest that, for example, choosing m-p and the window size w~5m usually leads to good results.

Figs. 3 and 4 show two embodiments for using the interleaver according to the present invention in respectively a turbo encoder and a turbo decoder having an alternative structure.

Fig. 3 shows a turbo encoder 300 according to a further embodiment of the present invention. The turbo encoder 300 comprise an interleaver 304 according to the present invention.

The turbo encoder 300 is a serial concatenated encoder. Two constituent codes 302, 306 are connected serially with the interleaver 304. Repeat-accumulate codes, wherein the first constituent code 302 is a repetition code and the second one 306 is an accumulator, and accumulate-repeat-accumulate codes, wherein the first constituent code 302 is an

accumulator/repetition code and the second one 306 is an accumulator, can be given as examples for serially concatenated codes.

The turbo encoder 300 of Fig. 3 generates an encoded sequence or encoded symbols 309 from an input sequence or input symbols 301. The input sequence 301 is applied to a first constituent code, i.e. a first constituent encoder 302, to obtain a first constituent codeword 303. The interleaver of the present invention generates an output sequence 305 from the first constituent codeword 303. The output sequence 305 is applied to a second constituent code, i.e. a second constituent encoder 306, to obtain a second constituent codeword 307. A combination unit 308 is adapted to combine the input sequence 301 and the second constituent codeword 307 into the encoded sequence 309.

Fig. 4 shows a turbo decoder 400 according to a further embodiment of the present invention. The turbo decoder 400 comprise an interleaver 405 according to the present invention.

The turbo decoder 400 of Fig. 4 may be used to decode the encoded sequence 309, 401 generated by the turbo encoder 300 of Fig. 3 so as to obtain decoded symbols 410. Similarly to the turbo decoder 200 of Fig. 2, the turbo decoder 400 comprises a first 403 and a second constituent decoder 402 that are connected by the interleaver 405 and by a de-interleaver 408 being the opposite of the interleaver 405. The input sequence 401 of the turbo decoder 400 is applied to the second constituent decoder 402 and the decoded symbols 410 is generated by the first constituent decoder 403.

By using the interleaver according to the present invention, the distance between the input and the output of the interleaver is limited. Since both constituent codes 302, 306 may be chosen as codes with low latency - like accumulators, for example memory- 1 convolutional codes, and repeaters -, the overall latency may be characterized by the interleaver latency. Therefore, if a window interleaver with parameter p is used, the encoder latency may be regarded as p, and is reduced with respect to known interleaves.

The interleaver according to the present invention may be realized by several constrained interleavers. In the folio wings, two embodiments for the interleaver are presented, as well as two interleaver construction methods.

Fig. 6 shows an interleaving function of an interleaver according to a first embodiment of the interleaver. The first proposed interleaver shown in Fig. 6 is called -window interleaver, or It is defined with the interleaving function of length k, where the absolute

difference is smaller than or equal to a predefined threshold or number for all k input indices.

The interleaving function f defines the order that the samples or values are read from the

input vector or sequence, i.e., the output of the interleaver is read from the location f in the input vector. The interleaving function has a length k, and the values j and _p are integer values between 0 and k In this way, the distance between the input and the output indices are limited by p for all

The embodiment shown in Fig. 6 correspondingly presents an interleaver function having a band structure with a width of In comparison, Fig. 5 shows an interleaving function of

an interleaver according to the state of the art that does not have such a band structure.

Due to the structure of the f a sliding window decoder with the following parameters

can be utilized for channel coding: window size w (w>p) and number of targeted symbols m , where the target symbols are the first m symbols within the window. The

structure of the interleaver prevents the extrinsic information of the targeted symbols to be interleaved to locations that are located outside the current or previous windows. Th )- window interleaver of length k according to the embodiment of Fig. 6 is a

constrained interleaver with the interleaving function , wherein the following condition

holds, k and p being positive integers:

Here means that is defined as the set consisting of elements

means that j is respectively an element of the set J. The

value is the interleaving function, and is the threshold or parameter defining the maximum distance between input and the output of the interleaving function. It is proportional to the interleaver size and has an influence on the possible window- sizes if this interleaver is used as the turbo interleaver of a wi -turbo code. As shown previously, should hold, wherein m is the number of targeted symbols and w is

the window size. Fig. 7 shows an interleaving function of an interleaver according to a second embodiment of the interleaver. The interleaver of the second embodiment may be called _P( - window interleaver or -WI. It is defined with the interleaving function of length k,

wherein the absolute difference is not greater than a predefined number p for the

input indices being a nonnegative integer, and d being a nonnegative integer defining the number of indices where the condition is not fulfilled. In this way, the distance between the input and the output indices is limited by the threshold p for only a subset of all possible input indices. In the example shown in Fig. 7, the distance between the input and the output indices is limited by p for only the input indices comprised between

and /

The / WI has the advantage of a simple construction. However, it has to be noted that

when used with a turbo code, it may experience problems in exchanging extrinsic information corresponding to symbols located at the d indices that do not fulfill the distance constraints. One solution to overcome this problem is to transmit known bits - e.g., zeros - over the d known locations, such that during iterative decoding, no extrinsic information exchange is needed, as those bits are already known perfectly at the receiver.

The -window interleaver of length k according to the embodiment of Fig. 7 is a

constrained interleaver with the interleaving function wherein the following condition

holds, k and p being positive integers, d being a nonnegative integer: wherein J _d is a subset of / with cardinality k-d. Here, d is the parameter specifying the number that shows at how many input indices of the interleaving function do not fulfill the constraint given in equation (4). It is desired to have a small d - because for these indices other measures have to be taken during decoding, like setting systematic bits to known values or puncturing systematic bits corresponding to these known values, as explained below -, but its value mainly depends on the construction methods explained in the next sections. Note that the d indices are located in the first or in the last b locations.

A -window interleaver fulfills the same conditions as a window interleaver

except for d indices. For d=0, both definitions are equivalent.

In the foUowings, a first construction method for constructing the interleaver according to the present invention is presented. This first construction method may be called random construction method.

The first proposed construction method is a brute force method to construct a random WI. With this method, one basically generates a large number of length- A: random or pseudo random interleavers such that enough number of Wis can be also generated. Later, the best performing WI may be selected among the generated interleavers. One option to select the best performing one is to evaluate the performance of turbo codes constructed with the stored interleavers in terms of bit error rate (BER) or block error rate (BLER) and then select the interleaver that give the best error correction performance. As a common practice for engineers in the area of channel coding, one can do computer simulations by using a simulation chain consisting of Wi-Turbo encoder, channel and Wi- Turbo decoder. By alternating the selected Wis employed in Wi-Turbo encoder and decoder, different BLERs (block error rates) or BERs (bit error rates) can be measured at the Wi-Turbo decoder. The best performing Wis are then the Wis - used in Wi-Turbo - which lead to the lowest FER or BER.

Alternatively, one can truncate the best performing length-^ interleaver to obtain an interleaver of smaller length.

In the followings, a second construction method for constructing the interleaver according to the present invention is presented. This second construction method may be called s-random construction method, and is based on the method proposed by S. Dolinar, D. Divsalar, "Weight distributions for turbo codes using random and nonrandom permutations," TDA Progress Report 42.122, 1995, with the modification that during the construction of the interleaving function / the constraint is also considered.

This second method describes how to construct a window interleaver of length k with a modified s-random construction method. The inputs of the following algorithm are interleaver length k, minimum spread s of the interleaver and the threshold p - being a constraint for SWD -, where all of the inputs are non-negative integers. The second construction method comprises:

3. Remove the assigned index from J, increase j by 1 and go to step 2 until - 3a either the set / is empty (in this case, one obtains a -window interleaver), or

- 3b there are no indices left in / that can fulfill the conditions in step 2.

If the case 3b, continue by considering only the condition (5) and not the condition (6). In this case, one obtains a -window interleaver. Otherwise, if there is still no index left, start

again from the beginning, i.e. from step 1.

In the followings, a third constraction method for constructing the interleaver according to the present invention is presented. This second construction method may be called base interleaver construction method.

According to this third constraction method, one may use an unconstrained interleaver of length k' - called here the base interleaver - to build a larger interleaver of length , where L is a positive integer. For the construction, first a helper function is generated by modifying the base interleaver function, which is then concatenated L times using a deterministic method to obtain a Theoretically, L can approach infinity such that

the encoder/decoder can work for infinite size of data streams.

Depending on the construction of the helper function, the obtained WI can have a

zigzag form - zigzag-WI - or a smooth form - smoothed- WI.

According to this third constraction method from a base interleaver, it is possible to build an window interleaver of length k and L are positive integers - by using an

unconstrained base interleaver of length

For the constraction, first the following helper function is defined wherein is an integer.

Then, is used to construct the function / in the following way:

This method can be seen as concatenating the base interleaver L times where the connection between each interleaver is defined by the helper function.

Similar to this construction method, the interleaving method for mapping an input sequence of k'L indexed input symbols to an output sequence of k'L indexed output symbols, k' and L being positive integers, can be defined. Accordingly, the interleaving function will be

In the Ibllowings, a first example of the third construction method from a base interleaver is presented together with Fig. 8. According to this first example, a Zigzag Window Interleaver may be constructed, as shown in the right diagram of Fig. 8.

It is proposed to construct the zigzag window interleaver with the third construction method, using the following helper function:

Here,

The left diagram of Fig. 8 shows the helper function and the right diagram shows the resulting zigzag window interleaver, wherein is a randomly selected subset of J with cardinality The indices of ] are depicted with red markers.

If a zigzag window interleaver is used with a turbo code, resulting in a wi-turbo code, a SWD with window size w can be used. Thus, the codeword can be

decoded with a latency that is equal to an integer multiple of the base interleaver length. In the followings, a second example of the third construction method from a base interleaver is presented together with Fig. 9. According to this second example, a smoothed Window Interleaver may be constructed, as shown in the right diagram of Fig. 9. It is proposed to construct the smoothed window interleaver with the third construction method, using the following helper function:

where are two non-overlapping subsets of

Figure 9 shows an example of this construction, in that the left diagram the helper function and the right diagram shows the resulting smoothed window interleaver, wherein k' = 256 and are obtained according to equations (1 1 ) and (12) and are depicted with

red and green markers, respectively.

In the followings, a third example of the third construction method from a base interleaver is presented together with Fig. 10. According to this third example, a smoothed Window Interleaver may be constructed, as shown in the right diagram of Fig. 10.

It is proposed to construct this smoothed window interleaver with the third construction method, using the helper function defined in equation (10). However, are not

defined according to equations ( 1 1 ) and ( 12) like for the second example, but alternatively it is proposed to use any such that the following criteria are fulfilled:

This third example also yields a smoothed window interleaver, as depicted in Fig. 10. The left diagram of Fig. 10 shows the helper function while the resulting smoothed window interleaver is presented in the right diagram of Fig. 10, wherein

are obtained according to equations ( 13) and (14) and are depicted with red and green markers, respectively.

If a smoothed window interleaver is used with a turbo code, resulting in a wi-turbo code, an

SWD with any window size between 2p and k can be used. Compared to the zigzag- WI, this gives a higher flexibility in terms of decoding latency.

In the followings, the choice of the base interleaver for the third construction method is presented.

Although one can use any unconstrained interleaver as a base interleaver, the choice can have an influence in the performance and in the implementation.

It may be shown that if an interleaver is used as base interleaver that is contention-free for an integer c, the resulting WI is also contention-free for c. This may be shown by using equation (8) and rewriting the definition of contention- free interleavers for this special structure of the interleavers.

It may numerically be verified that if the base interleaver is a Quadratic Permutation

Polynomial (QPP) interleaver - see J. Sun, Y. O. Takeshita. "Interleavers for turbo codes using permutation polynomials over integer rings." IEEE Transactions on Information Theory, 51.1 (2005): 101 -1 19 - with spread Sf, the resulting WI has a spread no smaller than

As the interleavers used in LTE turbo codes - see O. Y. Takeshita. "On maximum contention- free interleavers and permutation polynomials over integer rings." IEEE Transactions on

Information Theory, 52.3 (2006): 1249-1253 - are contention-free QPP interleavers, one can construct contention free Wis with good spread factor by using LTE Turbo code interleavers as base interleavers.

In the followings, a Sliding Window Decoding for Turbo Codes using an Window

Interleaver is presented. It is proposed to define the sliding window decoder with window length w for the turbo codes with a as follows:

1. Decoding starts by processing the first w systematic bits and their corresponding parity bits, where the first m systematic bits in the window are the targeted symbols.

2. The symbols inside the window are decoded using standard turbo decoding technique with the following modification: During interleaveing/deinterleaving, if extrinsic information - e.g., in terms of log-likelihood value, also referred to as soft value - in the range from an unknown symbol from outside the window is required, it is set

to 0.

3. After a certain number of iterations is reached, the following parameters are stored:

^■ The state of the constituent decoders at the index.

^■ The extrinsic information of the first m systematic bits in the window, which will be needed for the next window.

4. The window is then shifted by m, such that the new window starts with the

systematic bit of the previous window.

5. The symbols inside the window are decoded similar to the first window, except the

following modification:

^■ The constituent decoders start with the states, which were stored in the previous step.

^■ Due to the interleaver structure, extrinsic information of some symbols from the previous window might be needed. This information is taken from the stored values in the last step.

6. Go to step 3, unless the end of the current window corresponds to the end of the

codeword.

This procedure is shown in Fig. 11. In each window, w systematic bits are processed, where only the first m bits are the targeted symbols. After the processing of the current window is finished, the window is shifted by m.

In the followings, encoding and decoding of a turbo codes using an / _p (/)-Window Interleaver are presented. Turbo codes with an / _{p fi} (;)-Wi may be decoded by using the same method in the previous part, i.e. may be decoded by a Sliding Window Decoding for Turbo Codes using an - Window Interleaver. However, there may be a performance loss due to the d indices of the interleaver, which do not fulfill the condition (4) and hence will lie outside of the window.

To solve this problem, the following modification is proposed:

1. At the encoder, the systematic bits corresponding to d indices are set to known values - e.g., zeros, whose corresponding log-likelihood value equals such that no information is transmitted over these indices.

2. At the output of the encoder, the systematic bits corresponding to these known values are punctured, i.e. not transmitted.

3. At the decoder, a sliding window decoder is used with the following modification.

During iterative decoding, the known values of the d indices are fed to the decoder as perfect a-priori information - e.g., with a log-likelihood value of

This solution causes a small rate loss. However, for d « k the rate loss will be small.

Fig. 16 shows an interleaver or an interleaving device 1600 with an interleaving function according to an embodiment of the present invention. The interleaving device 1600 is adapted to generate an output sequence or interleaved sequence 1609 from the input sequence 1601. The input sequence 1601 and the output sequence 1609 have a length

The interleaving device 1600 comprises a serial to parallel converter 1602 to write the input sequence 1601 to a matrix M 1603 of size L by k '. The serial to parallel converter 1602 is adapted to reshape the input sequence 1601 into the matrix M 1603.

The interleaving device 1600 comprises a base interleaver 1604 to be applied on each row of M 1603, wherein the output of the base interleaver 1604 is written to the corresponding rows of the matrix R 1605 of the same size. Each row is interleaved using the base interleaver 1604.

The interleaving device 1 600 comprises a cyclic shift operator 1606 to be applied on each column of R 1605 in the vertical dimension to obtain the matrix S 1607 of the same size, wherein the shift values tj for each column is determined by the integers tj,j=0,... ,k '- \ . The cyclic shift operator 1606 performs a cyclic shift in vertical dimension according to tj.

The interleaving device 1600 comprises a parallel to serial converter 1608 to read the matrix S 1607 row by row so as to generate the interleaved output 3609 of length k 'L.

Particularly, the base interleaver 1604 may be an LTE interleaver.

In the followings, performance results are presented together with Figs. 12 to 15.

Fig. 12 shows performance results of wi-turbo codes - in terms of required Et/No to achieve a target error probability - with smoothed window interleavers according to the present invention. LTE QPP interleavers with lengths k' = 64, ... ,2048 are used as base interleavers.

The performance of the wi-turbo codes decoded with a sliding window decoder is shown in Fig. 12. The window-interleavers are generated by using the third construction method and using the LTE QPP interleavers of different lengths as base interleavers. Here, latency is defined as the number of required symbols to start decoding, i.e. for SWD the latency equals the window length. The performance metric is the required SNR or Et/No to reach a target error bit probability of 0.0001. One can observe that for each of eight codes the performance gets better with increasing window length (latency).

For comparison the performance of LTE turbo codes are also given. Each square marker in Fig. 12 corresponds to the performance of an LTE Turbo code with different interleaver lengths. It may be noted that, for providing a fair comparison, the decoding latency of the LTE turbo codes where no SWD is possible are considered as the message length, i.e.

interlcaver length. It may be observed that the performance of LTE turbo codes and wi-turbo codes are comparable. However, the wi-turbo codes can be decoded with flexible latency. One LTE turbo code can be decoded only with a fixed latency value because they are not suitable for SWD. Advantageously, the decoding latency of wi-turbo codes according to the present invention can be adjusted at the receiver to obtain the desired latency, without changing the code itself. Fig. 13 shows performance results of wi-turbo codes - in terms of required Eb/No to achieve a target error probability - with zigzag window interleaves according to the present invention. S-random interleavers with lengths k' = 200, ... ,1000 are used as base interleavers. Again, the results are comparable with LTE turbo codes.

Fig. 14 shows the bit error rate (BER) performance of wi-turbo codes with smoothed-window interleavers constructed from LTE QPP interleavers, i.e. constructed from different LTE QPP interleaver lengths k and different values L. For each curve, the length of the window interleaver is the same, but the length of the base interleaver is different. One can observe that for the same interleaver length, the performance gets better as the size of the base interleaver increases.

Fig. 15 shows an example scenario where the wi-turbo codes can have a significant advantage compared to LTE turbo codes. Assume that the receiver has to wait for τ seconds due to some other processing tasks, where it receives additional 750 symbols. Traditional turbo decoder would not be able to use this information to improve the decoding performance, but wi-turbo code can make use of these symbols to increase the performance, in this example by up to 0.4 IdB. Note that due to the special structure, any latency can be supported such that the decoder can work with nearly no idle periods.

The present invention is advantageous in that, by using the turbo codes with the proposed interleaver, the transmitter and receiver can have lower latency in channel encoding and decoding. One can adjust its decoding latency easily according to its latency budget by changing the window size of e.g. an SWT). This is not possible if a conventional interleaver is used because in known communication systems utilizing turbo codes, the latency cannot be adjusted at the transmitter or receiver side.

The present invention is advantageous in that, by using the proposed wi-turbo codes, the same codeword can be decoded with low latency in case of a good channel realization, and hence if a small window is enough for successful decoding.

The present invention is advantageous in that, by using the proposed wi-turbo codes, the latency can be increased by the transmitter or by the receiver to improve the error correction performance. The present invention is advantageous in that, by using the third construction method, one can build Wis that can have some good properties of the base interleaver, like contention-free property and the spread factor.

The present invention is advantageous in that, by using the third construction method, one can build Wis with a periodic structure, such that the storage need for the interleaver function does not increase with the interleaver length.

The present invention is advantageous in that, by using the third construction method, one can build Wis of any length that are integer multiples of base interleaver length.

The present invention may be implemented in hardware and/or software. The proposed wi -turbo codes and interleaver may be used in optical, wireline or wireless

communications.

The present invention has been described in conjunction with various embodiments as examples as well as implementations. However, other variations can be understood and effected by those persons skilled in the art and practicing the claimed invention, from the studies of the drawings, this disclosure and the independent claims. In the claims as well as in the description the word "comprising" does not exclude other elements or steps and the indefinite article "a" or "an" does not exclude a plurality. A single element or other unit may fulfill the functions of several entities or items recited in the claims. The mere fact that certain measures are recited in the mutual different dependent claims does not indicate that a combination of these measures cannot be used in an advantageous implementation.