Title: Communication system and method for communication in a communication system

Technical field

The invention relates to a system for communication between nodes and a method for communicating in such a communication system by exchanging information encoded by multiple description coding. Specifically the present invention relates to a communication system as stated in the preamble of claim 1.

The communication system comprises nodes, where a number of nodes acts as source nodes transmitting information, and a number of nodes acts as a receiver node receiving information and yet other nodes may act as intermediate nodes relaying received information to other nodes. Cooperation of source nodes, intermediate nodes and/or receiver nodes can render the communication more efficient.

By a number of source nodes is meant one or more source nodes. By a number of receiver nodes is meant one or more receiver nodes.

Background

Multiple description coding (MDC) is a source coding technique where an input information is described by means of a set of descriptors. Each descriptor comprises non-redundant information and a redundancy overhead with respect to other descrip- tors in the set. A sub-set of this set of descriptors thus allows the receiver to reconstruct a more or less distorted representation of the input information depending on the amount of information contained in the received descriptors. Combining all descriptors at a receiver node allows the receiver node to fully reconstruct the source information.

To reconstruct information encoded as multiple descriptors, a communication system engages decoders at the receiver nodes. In case that only a sub-set of the descriptors is available at the receiver node the communication system engages side decoders reconstructing a distorted representation of the source information. In case all descriptors are received, the communication system engages a central decoder fully reconstructing the source information.

An example for a cooperative system is known from US 2004/0225723 Al which relates to a system and a method for efficient replication of files encoded with mul- tiple description coding. US 2004/0225723 Al discloses how to distribute a given set of descriptors among a plurality of nodes efficiently by allowing for the exchange of descriptors among receiving nodes; US 2004/0225723 Al does not deal with optimizing the transmission by adapting the redundancy overhead of the descriptors.

Varying needs for redundancy can for instance arise in a communication system with varying link reliability. At high link reliability the need for redundancy in the transmitted information is low, because the probability of receiving the descriptors necessary for reconstructing a representation of the input-information is high. At de- grading link quality the communication system has an increasing need for redundancy overhead in the transmitted information, because the probability of losing some of the descriptors in the sending process increases. If a descriptor is lost in the transmission process, the communication system can exploit the redundancy contained in the remaining descriptors to maintain at least a distorted representation of the input information despite the loss of some of the descriptors. At least sub-sets of the complete set of descriptors are thus self-sustained, though at a reduced quality as compared to the input information.

Disclosure of the invention

The present invention addresses the problem of adapting the encoding induced redundancy overhead in a communication system to varying needs.

According to the invention the problem is solved by means of the features stated in the characterising part of claim 1. The encoding induced redundancy overhead is adapted by conditionally compressing the descriptors. The nodes in the communication system may exchange sub-sets of the complete set of descriptors. Such a sub-set can contain only one descriptor, a few or all descriptors. First, a primary sub-set of the complete set of descriptors is determined. Any given sub-set of the complete set of descriptors is then compared to the primary sub-set of descriptors and the redundancy overlap between the given sub-set and at least a first of the descriptors in the primary sub-set is extracted as the redundant part (with respect to said first descrip- tor of the primary sub-set). The remaining part is considered as the non-redundant part. Subject to a condition, such as the presence of the primary sub-set at a receiver node, the given sub-set is compressed to the non-redundant part before being transmitted.

Embodiments of the communication system according to the invention are defined in the dependent claims 2-12.

The conditional removal of the redundancy may be performed anywhere in the communication system on the way from the source to a final destination at a re- ceiver. According to preferred embodiments of the invention the computational complexity involved in extracting the redundant and the non-redundant part is reduced to a minimum by using an appropriate encoding scheme.

The actual need for redundancy can for example be determined by feed-back from receiver nodes indicating the descriptors which actually have reached their destination. A timely feed-back from a receiver can then be used to remove the redundancy

overhead from further descriptors to be sent to the receiver. The descriptors are adapted by keeping or removing the redundant part depending on the actual need as signalled by the feed-back.

The actual need may also be determined by other conditions and parameters, such as the type of link established to the receiver link, the bandwidth of a given link, a geographic location of a receiver node with respect to source nodes or other receiver nodes, the presence of cooperative receiver nodes, or any other physical parameter relating to the communication system.

An example for an application may be a situation where customers participating in a communication system pay for a link reliability level, and the redundancy in the descriptors transmitted to each customer is adapted to a scheme determined beforehand.

According to an embodiment of a communication system according to the invention a number of receiver nodes can cooperate by exchanging descriptors via a direct link. To minimize the amount of data exchanged each receiver node indicates to the other receiver nodes which descriptors it already has received, thus requesting only the non-redundant part of the remaining descriptors. Cooperating by transmitting conditionally compressed descriptors according to the invention the receiver nodes not only exchange descriptors in an informed manner, but also adapt the descriptors that are exchanged to the actual need.

The feed-back from receivers can also be sent back to the source nodes and processed there.

According to a special embodiment of a communication system according to the invention a single source node transmits descriptors to a single receiver node either via different channels or successively via a single channel. Based on the feed-back from the receiver node the source can then compensate for varying link quality, by adapt-

ing the descriptors. For example if a channel degrades, full descriptors are transmitted. If the channel recovers, the redundant part of the descriptors may be removed and only the non-redundant part of the descriptors is transmitted to minimize the total amount of data transmitted and save bandwidth.

According to a further embodiment of a communication system according to the invention a number of sources cooperate to transmit information to a single receiver node. Each source transmits a sub-set of the complete set of descriptors to the receiver node. The cooperation is optimized by choosing a primary sub-set from the sub-sets to be transmitted and conditionally compressing the remaining sub-sets with respect to the primary sub-set. An example of the application of this embodiment is the scenario of a receiver node joining an existing communication system comprising a number of source nodes cooperatively linked to each other, such as a system for streaming multimedia content where the multimedia content is encoded by MDC and each descriptor is stored at a different serve. The source with the fastest link to the receiver, e.g. the source closest to the receiver, may be chosen to transmit the primary sub-set and the remaining sources transmit the non-redundant part of the remaining sub-sets.

Conditional compression in a communication system with cooperating source nodes can also be applied in a security context, for instance for making the transmission of information more secure. An existing secure link is used to transmit a full descriptor, while insecure links only transmit compressed descriptors which are useless unless at least one full descriptor is present at the receiver node. In such an application for security of transmission the compression depends on link status "secure" or "insecure".

A further embodiment of a communication system according to the invention also comprises intermediate nodes in addition to source nodes and receiver nodes. The role of the intermediate nodes is to receive sub-sets of the complete set of descriptors and to forward said sub-sets. The intermediate nodes may also act to optimize

the transmission of the descriptors by conditionally compressing the received subsets with respect to a primary sub-set of the complete set of descriptors before forwarding them. The primary sub-set may for example be determined by the source nodes, received as feed-back from the receiver nodes or chosen from the sub-sets present at a number of cooperative intermediate nodes.

The above mentioned embodiments can be combined in a mesh of source nodes cooperating to distribute information encoded by multiple description coding to a number of cooperating receivers. All nodes in the cooperating mesh can take on the role of source nodes, receiver nodes or intermediate nodes. The exchange of descriptors is optimized by conditionally compressing the transmitted sub-sets.

According to a preferred embodiment of a communication system the differentiation of the descriptors into a redundant part and a non-redundant part can already be an- ticipated at the encoding stage, for example by employing a highly structured encoding technique, such as multiple-description lattice vector quantization (MDLVQ). Doing so only little computational effort is required for conditionally compressing the descriptors. Therefore, means for conditional compression of sub-sets of the complete set of descriptors are easily implemented anywhere in the communication system.

Input information characterized by n different parameters, where n is an integer number greater than 0, can be represented by n-dimensional vectors in a continuous n-dimensional vector space. A multiple description lattice quantiser "quantises" the input information by mapping the input vectors to discrete lattice points of a predefined fundamental lattice. Multiple descriptions of a lattice point are then found in a labelling step by mapping the lattice point to other lattices, where each of the multiple descriptions is based on a different lattice.

For the initial quantisation the multiple description lattice quantizer employs a lattice penetrating the n-dimensional input vector space. The lattice points are repre-

sented by lattice vectors. Around each lattice point a closed volume, the so-called Voronoi-region, is defined as the set of all points to which the lattice point is closer than to any other lattice point. All input vectors within the Voronoi-region around a lattice point are "quantised" to the lattice point, i.e. replaced by the lattice vector representing the lattice point.

According to a further preferred embodiment the lattices used for quantizing the input information (fundamental lattice) and generating the multiple descriptors (encoding lattices) are periodic, i.e. exhibit translational symmetry in all dimensions. Lattice points can then easily be constructed by integer coefficient linear combinations of fundamental vectors describing the symmetry.

Preferably, the encoding lattices are sub-lattices to the fundamental sub-lattice such that the sub-lattice points are comprised in the lattice points of the fundamental lat- tice points. Further preferably the encoding sub-lattices are similar to the fundamental sub-lattice and, as a consequence, also similar to each other such that they can be transformed into each other by simple scaling and rotation operations. Also preferably, the Voronoi region walls of the encoding lattices do not intersect lattice points of the other lattices. This choice of the encoding sub-lattices simplifies the unique encoding and the subsequent decoding of the quantised representation of the input information by the receiver node, and also allows for each descriptor to be constructed as a vector to a common reference point, and a vector specific for each descriptor containing the (local) refinement information. The vector to the common reference point of two different descriptors can easily be extracted from the descrip- tors as the redundant part, and the descriptors may be compressed to the non- redundant refinement information.

The invention further relates to a method for communicating in a communication system according to claim 13. Embodiments of the method according to the inven- tion are defined in the dependent claims 14-20.

A number of nodes participating in a communication system according to the invention and conditionally compressing a sub-set of descriptors before transmission may also be considered as an embodiment according to the invention. Examples for such an embodiment are a single source node or a group of cooperating source nodes conditionally compressing at least a sub- set of descriptors before transmitting the descriptors. Other examples for such an embodiment according to the invention are intermediate nodes or cooperating receiver nodes conditionally compressing descriptors based on a feed-back obtained from the communication system or based on information exchanged over the cooperative link before transmitting the descriptors.

Brief Description of the Drawingfs)

The invention is described below with reference to the accompanying drawings, in which

Fig. 1 shows a schematic of a communication system using multiple description coding comprising one source node and two receiver nodes cooperating over a fast feed-back link,

Fig. 2 shows an embodiment of a communication system with a source node broadcasting to cooperating receiver nodes,

Fig. 3 shows an embodiment of a communication system comprising source nodes cooperating to transmit information to a receiver node,

Fig. 4 shows an embodiment of a communication system applying meshed cooperation where each node S acts both as source node and receiver node exchanging information along unidirectional links I _y as indicated by arrows,

Fig. 5 shows examples of fundamental lattices in two dimensions, the translational symmetry being marked by arrows, where (a) is a cubic lattice, and (b) is a hexagonal lattice,

Fig. 6 shows a fundamental lattice (thin solid line, dots) of the cubic type in two dimensions and two sub-lattices denoted as N=5 (dashed line, crosses) and N=9 (thick solid line, circles), where (a) shows the Voronoi regions of the three lattices and (b) shows the corresponding lattice points and the Voronoi region for the N _s =45 sub- lattice where the two sub-lattices have common lattice points (reference points),

Fig. 7 shows a schematic of the encoding / transmission / decoding scheme using multiple description lattice vector quantization suited for conditional compression.

Detailed Description of the Invention

Fig. 1 illustrates essential functional elements of a communication system according to the invention and their interaction.

For clarity, a simplified embodiment comprising only one source node and two re- ceiver nodes linked to each other via a fast feed-back channel has been chosen. The extrapolation to a more complex communication system comprising more nodes and a more complex encoding scheme with more descriptors is obvious to person skilled in the art.

In the communication system shown in figure 1 an input information X is encoded by multiple description encoding means (encoder) as a number of descriptors, here a first descriptor d _! and a second descriptor d ₂ . Inherent to the multiple description coding technique, the two descriptors have a redundancy overlap. The source node includes a base station that transmits the two descriptors to the receiver nodes, ter- minal 1 and terminal 2, for example over wireless links as indicated in the drawing.

In the present example each receiver node comprises a terminal and a controller. At each receiver node the controller registers the received descriptors as the corresponding receiver node status and forwards this status to the other terminal controller via the fast feed-back link.

If a descriptor is lost on the way from the source node to the receiver node, for example if d ₂ is lost on the way from the base station to a first receiver node, the corresponding controller will check if d ₂ is available at the second receiver node and if so request the missing information from the second receiver node via the fast feed-back link.

The second controller could now provide that missing information by sending the descriptor d ₂ . However, to avoid charging the communication link with redundant data and thus optimize the exchange of information according to the invention, the communication system has means to conditionally compress that information before sending it. Such means for conditional compression may be implemented in each of the controllers. In the present example, the controller of the second receiver node checks for the condition that U ₁ is present at the first receiver node and if so differentiates d2 with respect to dl, extracts and finally transmits only the non-redundant part of d2.

The details of the terminals shown in figure 1 illustrate how decoding works in a communication system using multiple description coding with two descriptors d _l5 d ₂ . Depending on the descriptors available the receiver node engages different decoders. The controller accomplishes the task of collecting the descriptors and engaging the correct decoder. In case only descriptor di is available the receiver node engages side decoder 1 to reconstruct a distorted representation X ₁ of the input information X. In case only descriptor d ₂ is available the receiver node engages side decoder 2 to reconstruct another distorted representation X ₂ of X. In case both descriptors are available the central decoder is engaged to reconstruct the least distorted representation X ₀ of X. The central decoder is also engaged in the case where one of the de-

scriptors is collected as a conditionally compressed descriptor from the other receiver node. In this case, the controller regenerates the two descriptors from the available information before forwarding it to the central decoder.

Figure 2 shows a simplified representation of the communication system in figure 1. A source node BS broadcasts descriptors di and d ₂ to mobile receiver nodes MS ₁ and MS ₂ . The receiver nodes can cooperate via a direct link to exchange descriptors di or d ₂ or the conditionally compressed descriptors Cd ₁ or cd ₂ .

Figure 3 and figure 4 show schematically the basic configurations for alternative embodiments of cooperative communication systems according to the invention. Again, for the sake of clarity, the embodiments are chosen to have a minimum of nodes and descriptors. The generalisation to larger numbers of nodes or descriptors is obvious to skilled person.

Figure 3 shows an embodiment, comprising three source nodes S ₁ , S ₂ and S ₃ which cooperate to send information to a receiver node. Each of the three source nodes S ₁ , S ₂ and S ₃ carry a different descriptor or sub-set of descriptors, d _l5 d ₂ and d ₃ , respectively. Approaching one of the source nodes, here S ₂ , the receiver node obtains the full descriptor d ₂ from S ₂ , while it retrieves only the non-redundant parts of the descriptors di and d ₃ with respect to d ₂ , namely the conditionally compressed descriptors Cd ₁ = Cd ₁ Jd ₂ ) and cd ₃ = (d ₃ |d ₂ ). The cooperation between the source nodes may be initiated by feed-back from the receiver node or coordinated directly among the source nodes. Applying conditional compression at the time of communication, rather than removing redundant overlap from the descriptors beforehand, allows adapting the compression to the actual network situation. If it, for example due to a faster link, is more appropriate that the receiver node retrieves the full descriptor d ₃ from source node S ₃ , then the communication system adapts to this situation by transmitting the descriptors Cd ₁ and cd ₂ conditionally compressed with respect to d ₃ .

Figure 4 illustrates a further embodiment of a communication system according to the invention. The communication system comprises three cooperatively linked nodes N ₁ , N ₂ and N ₃ forming a meshed cooperative communication system. All of the nodes can act as source node and as a receiver node and are linked to each other by unidirectional links I _y , where i,j = 1,2,3. Input information may be generated at each node and encoded by two descriptors. Information at node Ni is encoded by the descriptors di ₂ and di ₃ , and transmitted to node N ₂ via the link Z ₁₂ and to node N ₃ via the link Z ₁₃ . Similarly, node N ₂ transmits descriptor d ₂₁ through link Z ₂₁ and descriptor d ₂₃ through link Z ₂₃ , while node N ₃ transmits descriptors d ₃₁ and d ₃₂ through links Z ₃₁ , Z ₃₂ , respectively. Depending on link quality each node can forward compressed or full descriptions on behalf of another node. If all links are operable each of the nodes may forward the compressed descriptors to save bandwidth. All nodes still receive the complete information from the other nodes. The first, full descriptor is transmitted from one node to the other through the direct link, while the second, condition- ally compressed descriptor is received indirectly via the third node. If one of the links drops out, the third node forwards the full descriptor containing enough information to reconstruct the information at a lower quality.

A preferred embodiment of the communication system according to the invention employs an encoding scheme using multiple lattice vector quantisation (MDLVQ). The highly structured nature of the multiple lattice vector quantisation allows anticipating the differentiation of the descriptors into a redundant and non-redundant part already at the encoding stage and conditional compression can be implemented with low computational complexity anywhere in the communication system.

In an encoding scheme with multiple lattice vector quantisation the input information is quantised to lattice points before being encoded as multiple descriptors. The lattice has the dimensionality of the input information. Examples for preferred lattice types for the case of two-dimensional input information are shown in figure 5. Fig- ure 5a shows a cubic lattice and figure 5b shows a hexagonal lattice. Dots mark lattice points and solid lines mark the so-called Voronoi-regions. All input vectors

within such a Voronoi region are quantised to the lattice point within the Voronoi region, i.e. replaced by the lattice vector corresponding to the lattice point. The arrows represent fundamental lattice vectors denoting the translational symmetry. Any lattice point can be generated as a linear combination in units of the fundamental lat- tice vectors.

A schematic of the encoding / transmission / decoding process for a two-descriptor encoding scheme is shown in figure 7. Input information X is quantised at the lattice vector quantisers Q(X) and Qs(X)- Q(X) quantises the input vector X to the funda- mental lattice λ generating the lattice vector λ. Qs(X) quantises the input vector X to the shift lattice λ _s generating the shift lattice vector λ _s . The difference between the lattice vector λ and the shift lattice vector λs is the reduced lattice vector λ-λs. The reduced lattice vector is fed to a label function β generating two relative sub-lattice points λi* and λ _j * by mapping the reduced lattice vector to two different sub-lattices. The shift lattice vector λ _s is combined with the first relative sub-lattice point λi* and transmitted via channel i to the receiver node. The label function β also yields an offset sub-lattice vector λ, ⁺ between the two sub-lattices. The sum of the shift lattice vector and the offset sub-lattice vector, λs ⁺ = λs + λ _j ⁺ , is combined with the second relative sub-lattice point λ _j * and transmitted via channel j to the receiver node. If only one of the channels is operable the receiver node engages the corresponding side decoder i or side decoder j to reconstruct a distorted representation, respectively λi = λs + λj* or λ _j = λs ⁺ + λ _j *, of the quantised input information λ. If both channels are operable to transmit the descriptors the central decoder is engaged to fully reconstruct the quantised input information λ. The central decoder receives the shift lattice vector information λ _s , λ _s ⁺ directly from the channels, while the relative lattice vector information λ*, λ _j ⁺ is produced by the inverse label function β ⁽⁴⁾ acting on the relative sub-lattice vectors λi* and λ _j *.

The highly structured nature of the lattice vector quantisation allows for dividing each descriptor into a rough information common to both descriptors and a local re-

fmement information specific for each descriptor and anticipates the conditional compression already at the encoding stage. The conditional compression of a descriptor is thus reduced to a relatively simple extraction of the redundant (common) part and the non-redundant (specific) part.

Figure 6 illustrates the relation between the different lattices involved in an encoding process for multiple description coding using conditional compression according to the invention for the case of a two-dimensional input information which is encoded by two descriptors. According to a preferred embodiment of the invention the fun- damental lattice chosen here is of the cubic type. According to a further preferred embodiment of the invention the sub-lattices are chosen such that the walls separating adjacent Voronoi-regions do not intersect any of the lattice points. Figure 6a shows the Voronoi-regions of the fundamental lattice (thin solid line), and two sub- lattices, denoted by N=5 (broken line) and by N=9 (thick solid line) according to the number of fundamental lattice points contained in the corresponding sub-lattice Vo- ronoi-region. Figure 6b shows the lattice points for the fundamental lattice (dots) the N=5 sub-lattice (crosses) and the N=9 sub-lattice (circles). The lattice points that are common to the N=5 sub-lattice and the N=9 sub-lattice form yet another sub-lattice, the N=45 sub-lattice which may be used as the shift lattice. The thick solid line in figure 6b marks a Voronoi region of the N=45 sub-lattice.