CHANNEL COMPUTATION

Abstract

A computer-implemented method for in-channel function computation in a digital communication system, with a plurality of transmitting digital units and one or more channels, includes the steps of: digitally encoding input data according to one or more transmitting encoding schemes; transmitting digitally encoded input data from the transmitting digital units through the channels; obtaining superpositions of the digitally encoded input data from the plurality of the transmitting digital units in the one or more channels; based on a decoding scheme, which assigns, to any one of the possible superpositions of the transmitted digitally encoded input data, a predefined value corresponding to a predefined combination of the digitally encoded input data, decoding the superpositions of transmitted digitally encoded input data, thereby obtaining combinations of the digitally encoded input data. A digital communication system implementing the method and a receiver implementing the step of decoding of the method are disclosed.

Claims

1-25. (canceled)

26. A computer-implemented method for in-channel function computation in a digital communication system comprising a plurality of transmitting digital units and one or more channels, the method comprising the steps of: digitally encoding input data according to one or more transmitting encoding schemes, wherein the input data is encoded according to a digital modulation scheme, wherein the digital modulation scheme is an amplitude-based and phased-based modulation scheme; transmitting digitally encoded input data having changed phase and amplitude from the plurality of transmitting digital units through the one or more channels; obtaining superpositions of the digitally encoded input data from the plurality of the transmitting digital units in the one or more channel; based on a decoding scheme, which assigns, to any one of the possible superpositions of the transmitted digitally encoded input data, a predefined value corresponding to a predefined combination of the digitally encoded input data, decoding the superpositions of transmitted digitally encoded input data, thereby obtaining combinations of the digitally encoded input data, wherein the step of decoding the superpositions of transmitted digitally encoded input data comprises determining the phase and amplitude of the transmitted signals comprising superpositions of the digitally encoded input data, and mapping the signals to predefined combinations or functions of the input data.

27. The method for in-channel function computation according to claim 26, wherein the input data comprises several input data sources comprising at least first input data, transmitted using a first transmitting digital unit, and second input data, transmitted using a second transmitting digital unit.

28. The method for in-channel function computation according to claim 26, wherein the channels are time-invariant or time-variant channels.

29. The method for in-channel function computation according to claim 26, wherein the channels are time-variant channels.

30. The method for in-channel function computation according to claim 26, wherein computation and transmission occurs simultaneously.

31. The method for in-channel function computation according claim 26, wherein the superpositions of the digitally encoded input data are obtained by interference of transmitting signals from the plurality of transmitting digital units carrying the transmitted digitally encoded input data.

32. The method for in-channel function computation according to claim 26, wherein the decoding scheme comprises a number of constellation points equal to or more than a number of possible combinations of input data.

33. The method for in-channel function computation according to claim 26, wherein the superpositions of the transmitted digitally encoded input data have a number of superposed constellation points greater than constellation points of digital modulation scheme used for encoding the input data.

34. The method for in-channel function computation according to claim 26, wherein the transmitting encoding scheme and the decoding scheme associate each superposition of the digitally encoded input data with a predefined unique combination of input data, preferably comprising input data from at least first input data, transmitted using a first transmitting digital unit, and second input data, transmitted using a second transmitting digital unit.

35. The method for in-channel function computation according to claim 34, wherein the step of decoding the superpositions of transmitted digitally encoded input data comprises extracting the unique combinations for the received superpositions of transmitted digitally encoded input data.

36. The method for in-channel function computation according to claim 26, wherein the transmitted digitally encoded input data is transmitted over signals with different transmission power.

37. The method for in-channel function computation according to claim 26, wherein the transmitted digitally encoded input data from the transmitting digital units are transmitted at a same carrier frequency.

38. The method for in-channel function computation according claim 26, wherein the transmitted digitally encoded input data from the transmitting digital units are transmitted at a same time.

39. The method for in-channel function computation according to claim 26, wherein the decoding scheme is implemented in a look-up-table (LUT).

40. The method for in-channel function computation according to claim 26, wherein the step of decoding the superpositions of transmitted digitally encoded input data further comprises error correction, and/or synchronization, and/or acquisition of channel state information.

41. The method for in-channel function computation according to claim 26, wherein input data are gradients and/or parameters of a machine learning model.

42. The method for in-channel function computation according to claim 26, wherein the combination of input data is a federated average of machine learning models.

43. The method for in-channel function computation according to claim 26, wherein the digitally encoded input data from the plurality of transmitting digital units is transmitted asynchronously and is decoded based on a unique time sequence of superpositions.

44. A digital communication system comprising a plurality of transmitting digital units; one or more channels; and at least one digital receiver, the transmitting digital units utilizing one or more transmitting encoding schemes for encoding input data and transmit digitally encoded input data, wherein the input data is encoded according to a digital modulation scheme, wherein the digital modulation scheme is an amplitude-based and phased-based modulation scheme, the one or more channels configured to obtain superpositions of transmitted digitally encoded input data, wherein the receiver is configured to decode said superpositions as combinations of transmitted digitally encoded input data, based on a decoding scheme which assigns to any of the possible superpositions a predefined value corresponding to a predefined combination of the digitally encoded input data, wherein the receiver is configured to decode the superpositions by determining the phase and amplitude of the transmitted digitally encoded input data, and mapping the signals to predefined combinations or functions of the input data.

Description

DESCRIPTION OF THE DRAWINGS

[0051] The invention will in the following be described with reference to the accompanying drawings. The drawings are examples of embodiments and not limiting to the presently disclosed computer-implemented method, system and receiver for in-channel function computation in a digital communication system.

[0052] FIG. 1 shows a schematic view of a flow diagram of one embodiment of the presently disclosed method.

[0053] FIG. 2 shows a schematic view of an encoding scheme constellation and decoding scheme of superpositions constellation in one embodiment of the presently disclosed method.

[0054] FIG. 3 shows a communication model of one embodiment of the presently disclosed method.

[0055] FIG. 4 shows a mathematical representation of a decoding scheme in one embodiment of the presently disclosed method.

[0056] FIG. 5 shows an embodiment of the presently disclosed digital communication system.

[0057] FIG. 6 shows a table with a counterexample to show that a symmetric function is not necessarily computable.

[0058] FIG. 7 shows an embodiment of a constellation diagram.

[0059] FIG. 8 shows a counterexample of a non-computable function with more or equal constellation points of the superpositions than the combination or function of input transmitted digital data.

[0060] FIG. 9 shows an embodiment of the space of digital data, the constellation points of the superpositions, and the values of a function or combination of digital data.

[0061] FIG. 10 shows one embodiment of a MIMO setup for decreasing distortion, according to one embodiment of the present disclosure. A k user may use N.sub.t antennas.

[0062] FIG. 11 shows one embodiment of a Rate enhancement MIMO setup.

[0063] FIG. 12 shows one embodiment of a broadband ChannelComp transceiver and transmitter architecture, according to the present disclosure.

[0064] FIG. 13 shows a diagram of one embodiment of federated learning using the presently disclosed ChannelComp method and/or system.

[0065] FIG. 14 shows an overview of application of the presently disclosed computer-implemented method for in-channel function computation.

DETAILED DESCRIPTION

Method

[0066] FIG. 1 shows a flow diagram of one embodiment of the presently disclosed method (100).

[0067] FIG. 2 shows a schematic view of an encoding scheme constellation (201, 202) and a constellation of superpositions (203) in one embodiment of the presently disclosed method (200).

[0068] In one embodiment of the present disclosure, shown in FIG. 2, the transmitting devices, or transmitting digital units, may use a QPSK encoding scheme for 2 Bit quantization.

[0069] In this embodiment the users or transmitting digital units may be 2. A first transmitting digital unit may be transmitting with a first QPSK encoding scheme (201) and a second user or transmitting digital unit may be transmitting with a second QPSK encoding scheme (202). In the embodiment shown if FIG. 2 there are only two users or transmitting units but the presently disclosed method is general and may be applied to an arbitrary number of transmitting units, such as more than 10, preferably more than 100, more preferably more than 1000, even more preferably more than 10000, most preferably more than 100000. In the embodiment shown in FIG. 2 the encoding scheme used by the transmitting digital units is QPSK, but the presently disclosed method is general and may be applied to any arbitrary or standard analog or digital encoding scheme, with the only assumption that a receiver and a decoding scheme is aware of the used encoding schemes for transmission. In the embodiment of FIG. 2 the constellation or representation of digitally converted data in the amplitude-phase plane is limited to 4 points (206). The arrow (206) is pointing to only 2 of the constellation points in the encoding scheme of the first transmitting unit, but it is meant to represent all the 4 points in the constellation of the encoding scheme for the first unit. The encoding scheme of the first and second transmitting digital unit is, in the embodiment shown in FIG. 2, a QPSK encoding scheme, comprising 4 constellation points representing the values, in bit quantization, of 00, 01, 10, 11. In the embodiment shown in FIG. 2 the QPSK encoded transmitted digital data may interfere in the channel forming a number of superpositions (205) arranged in a constellation (203) of possible superpositions in the amplitude-phase plane. The constellation (203) of superpositions may comprise a larger number of points than the constellation of transmitted digital data. Each point in the superposition constellation (203) may be assigned, in a decoding scheme, to a predefined value corresponding to a combination of the input transmitted data. This way, by decoding the points in the superpositions constellation (203) it is possible to obtain a value corresponding to a combination of input transmitted data. In the presently disclosed method, the actual computation of combinations of transmitted data is performed in the channel by means of the formation of superpositions and by means of a decoding scheme configured to give a meaning of said superpositions and to decode them to meaningful values corresponding to combinations, or functions, of transmitted digital data. The receiver can directly decode the superpositions as values corresponding to combinations of transmitted data. Such a combination, may be, for example, a weighted sum, which is beneficial for in-channel computation of a federated average of machine learning models. The combination may, otherwise, be any mathematical function of data.

[0070] In the embodiment of FIG. 2 the channel may be over the air, but any other time-invariant or time-variant channel may be used in the presently disclosed method, such as an electric channel, an optical channel, a quantum channel, an acoustic channels, a light channel, a molecular channel, or any medium capable to carry analog or digital modulated signals.

[0071] FIG. 3 shows one embodiment (300) of the presently disclosed method. In this embodiment true values (301) of input data from K users are quantized by a quantification module (301) and encoded or modulated by encoder (304) into transmitted digital data. In the time-invariant or time-variant channel the transmitted digital data with finite constellation points interfere, for example according to the interference sum (306), are combined with noise effect (307), such as Gaussian noise, and superpositions (308) are obtained in the time-invariant or time-variant channel, ready to be decoded by a receiver using a function (309) that assigns to each superposition (308) a predefined value (310) corresponding to a combination of transmitted digital data. In one embodiment of the present disclosure, the function that assigns to each superposition a predefined value corresponding to a combination of transmitted data is computable, that is it is such that to each superposition a unique combination of transmitted data is assigned.

[0072] FIG. 4 shows a mathematical representation (400) of one embodiment of the presently disclosed decoding scheme. In FIG. 4, (401) is a binary matrix that selects all possible cases of users, or transmitting digital units, to send their digital data. Vector (402) represents the transmitted constellation points for K users. Vector (403) represents all constellation points for all the possible superpositions in the time-invariant or time-variant channel.

Method Details

[0073] The transmitting encoding schemes or modulations may be PSK, QAM, FSK or any analog or digital encoding scheme or modulation. The transmitting encoding schemes may be standard analog or digital encoding schemes or may be arbitrary analog or digital encoding schemes, but they may be known to the receiver and to the decoding scheme. That is, the programmer that implements the presently disclosed decoding scheme may input the type of encoding scheme for the transmitted data as a parameter of the presently disclosed decoding scheme. The transmitting encoding schemes may be the same encoding schemes for all users or transmitting digital units, or they may be different encoding schemes.

[0074] In one embodiment of the present disclosure, the superpositions of transmitted encoded data are obtained, in the time-invariant or time-variant channel, by interference of transmitting signals carrying the transmitted data. As transmitted signals are encoded or modulated and sent to a same time-invariant or time-variant channel, they interfere with each other generating superpositions, wherein superpositions are results of interferences of encoded or modulated transmitted data, for example in the amplitude-phase domain. It is an advantage of the present disclosure that interferences in the amplitude and phase domain are used and that superpositions of encoded transmitted data are superpositions in the amplitude and phase space.

[0075] In one embodiment of the present disclosure, the decoding scheme comprises more constellation points, such as constellation points in amplitude and phase space, as compared to the constellation points of the transmitting encoding schemes. As shown as an example in FIG. 2, the constellation of the superpositions (205) has a higher number of points in the amplitude and phase space than the number of points of the constellation of the first user or transmitting unit (201) or the number of points of the constellation of the second user or transmitting unit (202).

[0076] In one embodiment of the present disclosure, the decoding scheme comprises a number of constellation points equal or more than a number of possible combinations of input data or transmitted data. As the presently disclosed method may decode any combination of the input data, it is advantageous that the decoding scheme assigns to each superposition of the transmitted data a value corresponding to a unique combination of the input data and that there are at least as many superposition points in the superposition constellation as there are combinations of the input data.

[0077] In one embodiment of the present disclosure the transmitting encoding scheme and the decoding scheme associate each superposition of the digitally encoded input data with a predefined unique combination of input data. The input data may comprise input data from at least first input data, transmitted using a first transmitting digital unit, and second input data, transmitted using a second transmitting digital unit

[0078] The input data may encoded according to a digital modulation scheme. More specifically, the digital modulation scheme may be an amplitude-based and phased-based modulation scheme. The step of transmitting digitally encoded input data may accordingly comprise changing the phase and amplitude of transmitted signals representing the input data.

[0079] On the receiver side, the step of decoding the superpositions of transmitted digitally encoded input data may comprise determining the phase and amplitude of the transmitted signals comprising superpositions of the digitally encoded input data, and mapping the signals to predefined combination or functions of the input data.

[0080] In one embodiment of the present disclosure, transmitted digital data are transmitted over signals with different transmission power. The use of different transmission power for some or a group or all of the transmitting units is advantageous as it allows generations of a greater number of points in a superposition constellation. Therefore, the use of different transmission power may be advantageous in obtaining enough points in the superpositions constellation, such as to obtain at least one superposition point for each combination of the transmitted digital data. For example the transmitted data is typically encoded in an amplitude and phase space. If the transmitted power is different for different users or different transmitting units, the points in the constellations of the transmitted data for the different users or different transmitting units will be characterized by different amplitudes and the number of superpositions points will be higher as compared to a case where all the users or transmitting units transmit with the same transmitting power, as the amplitudes of the transmitted constellation points in the amplitude and phase plane may be related to the transmitted power. The superposition points may be interferences of transmitted data, and may therefore depend on both amplitude and phase of the encoded transmitted digital data.

[0081] In one embodiment of the present disclosure, transmitted data are transmitted through a same time-invariant or time-variant channel. In order to obtain in-channel computations it is advantageous that the transmitting units transmit data on the same channel. In particular the transmitting units may transmit on the same carrier frequency and at the same time, in order to obtain interferences in the channel and therefore in order to obtain superpositions of encoded or modulated data.

[0082] In the presently disclosed method, the combinations or functions of input data may be sums, or weighed sums, or multiplications, or mathematical operations, or logic operations, or binary operations, or boolean operations, or any other computation that can be expressed by a mathematical function of the input data. As the presently disclosed method assigns to any superposition of encoded data in the time-invariant or time-variant channel a value corresponding to a combination or function of input data, such a combination may be arbitrary and may be defined in the decoding scheme as any mathematical operation between transmitted digital data. That is very advantageous as the presently disclosed method may solve a large variety of problems related to computation. For example, if the combinations or functions of input data are, in one embodiment, assigned to weighed sums of input data and if the input data are gradients or parameters of machine learning models, the presently disclosed method may perform in-channel computation of a federated average of machine learning models and the receiver may simply decode the superpositions as federated average of parameters or gradients of machine learning models, without the need for the receiver to perform the federated average computation in-situ, as that computation has already been performed in the channel by generation of superpositions of encoded data. In the present disclosure, the receiver may simply decode the superpositions based on the presently disclosed decoding scheme. This fully analog or digital in-channel computation brings the benefits of saving time, computation resources and power consumption, together with being fully compatible with fully digital communication systems or with general analog communication systems based on both amplitude and phase modulation, or with mixed systems. The decoding may be done by the receiver based on the presently disclosed decoding scheme which, in this embodiment, may assign to each superposition point in the superposition constellation a weighed sum of the input data. The presently disclosed scheme may be based on a look-up table (LUT).

[0083] In one embodiment of the present disclosure, the decoding scheme or demodulation is based on a function that assigns a unique combination of input data to a unique superposition of transmitted encoded digital data. This is advantageous as it makes the decoding computable, that is that for each detected superposition a unique combination of transmitted data is determined. Whenever computability of the decoding scheme may not be achieved directly, transmission power or phases of the different users or transmitting units may be tweaked and differentiated in order to obtain more superposition constellation points.

[0084] The superpositions of the transmitted digitally encoded input data may have a number of superposed constellation points greater than constellation points of digital modulation scheme used for encoding the input data. An example of this is shown in FIG. 2. The digitally modulated input data has 4 constellation points, whereas the superposed constellation points have a total of 9 constellation points. The step of decoding the superpositions of transmitted digitally encoded input data may comprise extracting the unique combinations for the received superpositions of transmitted digitally encoded input data.

[0085] In one embodiment of the present disclosure, the transmitted data from the transmitting units are transmitted at a same carrier frequency.

[0086] In one embodiment of the present disclosure, the transmitted data from the transmitting units are transmitted at a same time.

[0087] In one embodiment of the present disclosure, the encoded data from the transmitting units are encoded with the same transmitting encoding scheme.

[0088] In a traditional communication system data is transmitted from the transmitters to the receiver through the channel, but no computation is done in the channel. For this reason, in a typical communication system different users or different transmitting units have dedicated frequencies or time slots, or encoding schemes and are therefore separated from each other in at least one of these three domains: frequency domain, time domain, coding domain. In the presently disclosed method a part of the computation happens in the channel and is based on interference of transmitted data. For this reason transmitted data may be sent at same carrier frequency and at the same time, and they may use the same encoding scheme.

[0089] In one embodiment of the present disclosure the decoding scheme is implemented in a look-up-table (LUT).

[0090] In one embodiment of the present disclosure, decoding further comprises error correction, and/or synchronization, and/or acquisition of channel state information.

[0091] In one embodiment of the present disclosure, when digital modulations are used with with digital transmitters or transmitting digital units and a digital receiver, the presently disclosed method may leverage all the advantages of digital systems, such as error correction, and/or synchronization, and/or acquisition of channel state information and all other features that are typical of fully digital communication systems.

[0092] In one embodiment of the present disclosure, transmitted data or input data are gradients and/or parameters of a machine learning model.

[0093] In one embodiment of the present disclosure the combination of input data or transmitted data is a federated average of machine learning models. In this embodiment the in-channel computation is performing a federated average of parameters or gradients of machine learning models. That is very beneficial in the context of Internet of Things, as federated averages are widely used for many applications, such as outlier identification or malfunctioning of devices or many other applications such as virtual reality, edge computing, edge learning.

[0094] In one embodiment, the presently disclosed method is robust to noise in the channel. As channels may present noise, in form for example of white Gaussian noise, the presently disclosed method may account of the noise and the error due to the noise for the definition of the decoding scheme in order to minimize decoding error. In particular the decoding scheme may be designed to minimize the maximum error, and/or the decoding scheme may be designed to minimize the average error. The inventors have realized that the problem of minimizing the maximum error and/or the problem of minimizing the average error have solutions that may be implemented in the decoding schemes, for a broad number of functions or combinations of input or transmitted data.

[0095] The present disclosure further relates to a computer program having instructions which, when executed by a computing device or computing system, cause the computing device or computing system to carry out any embodiment of the presently disclosed method for in-channel function computation in a digital communication system comprising a plurality of transmitting digital units and one or more time-invariant or time-variant channels. The computer program may be stored on any suitable type of storage media, such as non-transitory storage media.

System

[0096] FIG. 5 shows one embodiment of the presently disclosed system (500), comprising a plurality of transmitters or transmitting units (501), one or more time-invariant or time-variant channels (502) and a at least one receiver (503).

[0097] In one embodiment of the present disclosure each of the transmitting units is transmitting by fully digital modulations or encoding and the receiver is fully digital. The transmitted digital data is encoded or modulated according to standard or arbitrary encoding or modulation schemes. The transmitted encoded or modulated data interferes in the time-invariant or time-variant channel giving rise to superpositions of data. Said superpositions are decoded by the receiver according to a decoding scheme that assigns, to each superposition, a predefined value corresponding to a combination of input data. This embodiment of the presently disclosed system is fully digital, that is the transmitting units transmit digitally encoded or digitally modulated data, the channel is configured to carry digitally encoded or digitally modulated signals and the decoder is configured to decode superpositions of digitally encoded data, based on the presently disclosed digital decoding scheme.

[0098] In one embodiment of the present disclosure, the one or more time-invariant or time-variant channels are wireless channels. That is advantageous, for example, for in-channel communication over a wireless network, or over a cellular network or over a local area network, or over a personal area network.

[0099] In one embodiment of the present disclosure, the one or more channels are optical channels, such as optical fiber links. That is advantageous, for example for a communication over the Internet.

[0100] In one embodiment of the present disclosure, the one or more channels are visible light channels.

[0101] In one embodiment of the present disclosure, the one or more channels are quantum channels.

[0102] In one embodiment of the present disclosure the one or more channels are acoustic channels.

[0103] In one embodiment of the present disclosure the one or more channels are electric channels, such as copper wires.

[0104] In one embodiment of the present disclosure the one or more channels are molecular channels, such for in-body transmissions.

[0105] In one embodiment of the present disclosure the one or more channels are wires within an electronic chip, such in electronic chip design. This may be advantageous, for example, in systems on electronic chips.

[0106] In one embodiment of the present disclosure, the one or more channels are on-chip channels and the transmitting units and the receiver are on-chip.

[0107] In one embodiment of the present disclosure the system is a multi-input-multi-output (MIMO) system. That may advantageous, for example, in 5G or 6G mobile networks.

[0108] In one embodiment of the present disclosure, the one or more channels are capable to transmit analog or digitally modulated signals.

Receiver

[0109] The present disclosure further relates to a digital communication receiver, configured to decode in-channel superpositions of digital data from digital transmitters according to a decoding scheme which assigns, to each superposition, a predefined value corresponding to a predefined combination of transmitted digital data.

[0110] In one embodiment of the present disclosure, the presently disclosed receiver decoded superpositions of digital data based on a decoding scheme implemented in a look-up-table (LUT).

[0111] In one embodiment of the present disclosure, the receiver is configured to identify and decode a unique time sequence of constellations from asynchronous transmitters.

General

[0112] The presently disclosed method may be implemented in the presently disclosed system.

[0113] The presently disclosed system may be configured to perform the steps of the presently disclosed method.

[0114] The presently disclosed receiver may be part of the presently disclosed system and/or may be configured for performing the step of decoding according to the presently disclosed method.

[0115] The digital communication system may further comprise peripheral components, such as one or more memories, which may be used for storing instructions that can be executed by any of the processors. The digital communication system may further comprise internal and external network interfaces, input and/or output ports, a keyboard or mouse etc.

[0116] As would be understood by a person skilled in the art, a processing unit also may be a single processor in a multi-core/multiprocessor system. Both the computing hardware accelerator and the central processing unit may be connected to a data communication infrastructure.

[0117] The digital communication system may include a memory, such as a random access memory (RAM) and/or a read-only memory (ROM), or any suitable type of memory. The digital communication system may further comprise a communication interface that allows software and/or data to be transferred between the system and external devices. Software and/or data transferred via the communications interface may be in any suitable form of electric, optical or RF signals. The communications interface may comprise, for example, a cable or a wireless interface.

Synchronization

[0118] In one embodiment of the present disclosure, the transmitting units may transmit data asynchronously. For example a first group of transmitting unit may transmit at time T1, a second group of transmitting unit may transmit at time T2 and a third transmitting unit may transmit at time T3. That may result in a sequence of constellation points, for example constellation Q1, constellation Q2 and constellation Q3 corresponding to times T1, T2 and T3 respectively. In the present disclosure, phase and amplitude of the encoded or modulated signals may be chosen in such a way to make such a sequence of constellation points unique for each possible combination of input data. Therefore, in the present disclosure, the receiver may be configured to identify any unique sequence of constellations and therefore associate to each of these unique sequences a unique combination of input data.

[0119] In one embodiment of the presently disclosed method, the encoded data from the plurality of transmitting digital units is transmitted asynchronously and is decoded based on a unique time sequence of superpositions.

Analog Modulation

[0120] In one embodiment of the present disclosure each of the transmitting units is transmitting by any analog modulation and the receiver is fully analog. The transmitted data is encoded or modulated according to standard or arbitrary analog modulation, not restricted to amplitude modulations. The transmitted digital data interferes in the time-invariant or time-variant channel giving rise to superpositions of transmitted data. Said superpositions are decoded by the receiver according to a decoding scheme that assigns, to each superposition, a predefined value corresponding to a combination of transmitted data. This embodiment of the disclosed system is fully analog, that is the transmitting units transmit analog modulated data, the time-invariant or time-variant channel is configured to carry analog modulated signals and the decoder is configured to decode superpositions of analog modulated data, based on the presently disclosed decoding scheme.

EXAMPLES

[0121] The presently disclosed method, system and receiver are in the following section described with reference to examples. The examples shall not be seen as limiting for the present invention.

[0122] The technology underlying the presently disclosed method and system may be referred to as ChannelComp, which may be an abbreviation of Channel Computing, and wherever used in this text, the word ChannelComp may refer to the presently disclosed method and system and receiver.

[0123] Over-the-air computation (AirComp) is a well known technique by which several wireless devices transmit by amplitude analog modulations to achieve a sum or function of their transmit signals at a common receiver. The underlying principle is the superposition property of the radio waves. Due to that such superposition is analog, it is natural that AirComp use amplitude analog modulations and analog hardware to obtain analog sum of signals. Unfortunately, this is impractical because rarely wireless devices today use amplitude analog modulations. It would be highly desirable to use more general anaog modulations than amplitude modulations, and also digital communications, because of the numerous benefits that they offer such as error correction, synchronization, acquisition of channel state information, software nature, and widespread use. However, when using analog modulations more general than amplitude analog modulations, or digital modulations for AirComp, a general belief is that the superposition property of the radio waves returns incomprehensible overlapping of the signals. The present disclosure breaks through such belief and discloses ChannelComp, an entirely new digital communication system and method, that allow to use general analog modulations as well as digital modulations. The inventors define the presently disclosed method as ChannelComp method.

[0124] ChannelComp inherits all the digital communication benefits, as well as the benefit of general analog modulations. In contrast to AirComp, ChannelComp can be implemented as a pure software method that is compatible with current digital technologies. ChannelComp can be used for all the use-cases of AirComp such as distributed machine learning and artificial intelligence, without waiting for the daunting if not impossible task to re-equip wireless devices with amplitude analog modulations. ChannelComp has the potential to be a new disruptive technology for the future generation wireless systems, and to enable groundbreaking new services such as artificial intelligence, augmented and virtual reality over networks, or safe autonomous driving and flying.

[0125] Towards implementing the idea of the internet of things (IoT), which can reshape our lifestyle through providing ubiquitous connectivity of almost everything, the generations of wireless communications have been accompanied by a paradigm shift from human-type communications to machine-type communications. On the one hand, the number of IoT devices is predicted to reach 75 billion by 2025, much larger than that of mobile phone users. On the other hand, the various IoT applications based on machine learning (ML) are set to emerge in 6G, which require collecting, transmitting, and performing calculation of enormous amounts of data from many devices. Consequently, extensive connectivity needs to scaled-up radio and computation resources, which means swamping the capacity of the current systems. To better support emerging compute-intensive ML applications, e.g., virtual reality, edge computing, edge learning, especially federated learning, over the air computation (AirComp) is a promising concept to simultaneously collect and compute data at the edge network.

[0126] The AirComp solution leverages the waveform superposition property of the multi-access linear time-invariant channel to realize aggregation of data simultaneously transmitted by devices, allowing each device to access all radio resources, unlike the standard transmit-then-compute scheme. Moreover, the AirComp approach integrates communication and computation steps and provides ultra-fast wireless data aggregation in IoT networks with high-spectrum efficiency. AirComp reduces the required energy of each device for transmission while it can bring high rate communication thereof by harnessing interference to help functional computation. Besides preserving the privacy and security of data, the coverage area can also be enlarged since more devices can transmit at the same time and frequency.

[0127] However, AirComp must use a special analog communication system, where the communication happens via amplitude analog modulations. This is highly impractical because almost no device today uses the simple amplitude analog communications of AirComp. AirComp would thus require a new communication hardware. Instead, in this document the inventors disclose a channel computing (ChannelComp) method that is fully compatible with existing digital communication systems such as those currently available on any smartphone or IoT system. Moreover ChannelComp does not require new hardware, because may be fully software. ChannelComp can be implemented both via any analog modulation (not restricted to amplitude modulation) and digital modulation. The inventors have established the broad set of functions that ChannelComp may compute and propose the methods that make it possible to any modulation scheme to perform computations.

[0128] The presently disclosed ChannelComp overcomes the limitation of AirComp due to the use of analog amplitude modulations, and uses instead any analog modulation or digital modulations. The compatibility with digital modulations makes it possible to benefit from all the digital communication methods such as error correction, synchronization, and acquisition of channel state information. Thus, contrarily to AirComp, ChannelComp is a pure software invention that is compatible with digital technologies already present in the current 5th generation (5G), and in most any digital communication system.

[0129] The present disclosure dramatically improves the use of communication resources (energy, time, frequency), which are an important need to IoT for ML or artificial intelligence (AI) services. Thus, ChannelComp may be used to make the complex AI/ML computations over-the-channel and thereby greatly accelerating the AI/ML algorithms. To be concrete, an application example of ChannelComp is the use of distributed ML/AI over a camera network to monitor events such as accidents or traffic in a city or the appearance of obstacles while driving a car.

[0130] One benefit of the presently disclosed solution is the use of existing digital systems to implement ChannelComp. If we wish to implement AirComp on existing digital systems, it is necessary to enforce amplitude analog communication systems to work on top of current digital systems, which is very difficult and impractical. This enforcement works in very few and very specific cases, and the results are highly inefficient in terms of communication resource usage. One such AirComp enforcement on top of digital communications has been recently proposed, named one-bit broadband digital aggregation (OBDA), but only works for binary phase shift key (BPSK) and quadratic phase shift key (QPSK) digital modulations. These are extremely simple digital modulation format. In contrast, the presently disclosed method and system ChannelComp works on a broad set of functions, combination of transmitted data and uses digital modulations as well as any analog modulation. Moreover, due to that AirComp is not conceived for digital communication, the performance of such application is highly inefficient. AiComp's non-coherent communication solution for single and multi cell using pulse-position modulation and frequency-shift keying (FSK) both are limited to signSGD problem, like OBDA, and AiComp extension to general function computations is at the moment not known. In summary, the application of AirComp to digital modulation or general analog modulations is restricted to very few cases and to limited functions, with inefficient performance.

[0131] Differently than OBDA, the presently disclosed ChannelComp may be compatible with any digital or analog modulation. The presently disclosed method ChannelComp may use any currently available digital systems (which are almost everywhere used) instead of amplitude analog modulations (which are very rarely used) of AirComp. The amplitude analog systems must be tailored hardware-wise to analog AirComp, which do not exist yet today. Hence, the presently disclosed solution is purely software and leverages current digital systems to make the function computation over-the-channel and benefits in terms of the existing digital communications structure, including error correction, synchronization, and acquisition of channel state information. This may enable a quick adoption of ChannelComp method in current and future devices, including IoT devices, and systems. This quick adoption may likely generate huge economical savings for operators and companies in the telecommunication industry due to the use of already available digital infrastructure.

[0132] AirComp's main drawback is to rely on amplitude analog communications, which are almost never used today. Moreover, analog communications are not robust to the communication channel errors that introduce an inevitable error at the receiver device. The error cannot be removed by forward error correction as possible in digital systems. AirComp can only be used for linear time-invariant channels.

[0133] Within AirComp, the closest solution is OBDA, which forces analog communications into digital modulations. In OBDA, analog transmissions are used together with digital orthogonal multiple-access schemes, such as orthogonal frequency division multiplexing (OFDM) transceivers, and digital modulation schemes, such as BPSK and QAM. But result is order of magnitudes less efficient in terms of communication resources than ChannelComp. In addition ChannelComp may be extended to any function and therefore to any of the existing digital modulations, or even to other arbitrary digital modulations. Moreover ChannelComp can be a fully software method which may be implemented in a fully digital communication system.

ChannelComp: Computation over the MAC by Digital Modulations

[0134] Consider a communication network in which there exist a computation point (CP) together with K nodes. The computation point may be a common receiver connected by shared time-invariant or time-variant channels to the nodes. The CP aims to compute a desired function f(x.sub.1, x.sub.2, . . . , x.sub.K) whose x.sub.k.sub.q is a value owned at the k-th node. In particular, the assumption is that the nodes transmit messages by digital communications. In this digital communication system, all the nodes transmit their values f at the CP.k-th x.sub.k(t) node digital transmits the value at time t where ={1,2, . . . , T} denotes the set of time slots of interest for a sufficiently large number T. To perform such digital transmission, the usual digital procedure is the following: each value x.sub.k(t) is quantized into a length q vector (t), (where q equals 2 to the power of number of bits), thereafter the resultant vector is mapped into the digitally modulated signal {right arrow over (x.sub.k)}(t) using encoder .sub.k(.) i.e {right arrow over (x.sub.k)}(t)=.sub.k((t)). The signal {right arrow over (x)}.sub.k(t) is what node k transmits over the communication time-invariant or time-variant channel. Since all the nodes transmit simultaneously, CP receives the summation of all {right arrow over (x)}.sub.k(t)s over MAC at the time t, i.e.

[00001]$\begin{array}{cc}\stackrel{.fwdarw.}{y}\left(t\right)={.Math.}_{k=1}^K{\stackrel{.fwdarw.}{x}}_k\left(t\right)+\stackrel{.fwdarw.}{z}\left(t\right),t,& \left(\mathrm{eq}.1\right)\end{array}$

where {right arrow over (y)}(t) is physically generated by the superposition nature of electromagnetic waves, and {right arrow over (z)}(t) is a receiver noise that the receive antennas unavoidably capture. Following the usual modeling in digital communications, such noise may be modeled as a white Gaussian noise (AWGN) process with zero-mean and variance

[00002]${}_z^2.$

Note that each digital signal {right arrow over (x)}.sub.k(t) is selected from finite q chosen modulation signal, thereby {right arrow over (y)}(t) has finite constellation points. The summation in eq. 1 induces a specific constellation diagram of y which depends on the number of nodes K and which modulation has been used for each {right arrow over (x)}.sub.k(t) e.g. FIG. 2 shows this deformation for the case of using BPSK for two users i.e. K=2.

[0135] To compute f, one needs to use mapping (association function) ({right arrow over (y)}(t)) based on the resultant constellation diagram of signal {right arrow over (y)}(t). More precisely, the mapping must be determined such that its output approaches the value of the function much as possible. In mathematical terms, at time t, map can be found from the following optimization (2)

[00003]${}^{*}=\underset{}{\arg \min }{.Math.}_{x_1,.Math.,x_K{}_f}{.Math.f\left(x_1\left(t\right),.Math.,x_K\left(t\right)\right)-\left(\stackrel{.fwdarw.}{y}\left(t\right)\right).Math.}^2$

[0136] Here, .sub.f is the domain of function f.

[0137] To illustrate optimization problem (2), consider a simple noiseless scenario in which transmitters use BPSK modulation and the desired function f is the summation function for two users K=2. The users send {1,1} and CP receive {2,0,2} as sum over the air, since. Here, the association tabular is nothing expect a simple map that assign values of the constellation diagram of {right arrow over (y)}(t) to the corresponding output of f i.e.

[00004]$\left(\left\{-2\right\}\right)=0,\left(\left\{0\right\}\right)=1,\left(\left\{2\right\}\right)=2$

where : 43 is a map can be uniquely determined based on which kind of modulation is used for x.sub.k(t) for k, in addition to which characteristics of the function f has

[0138] Therefore, in the next section, the characteristics of the desired function and the employed modulation are discussed. Then, possible choices of from the minimization in (2) will be highlighted.

Uniform Modulation

[0139] Without using precoders, computing all types of functions may not be achievable when all K nodes use same modulation. Hence, there is a class of function f with some specific features that it can be perfectly computed by using digital communication. Let (.) be the modulation used by all nodes to send the data over the air. Then, received signal by CP has different constellation points formed by summation of .sub.k[K](x.sub.k). Then, the remained question is which functions are computable using this communication architecture?

[0140] In the following, a necessary condition on the function f in order to be determined uniquely by using an appropriate tabular function is brought.

[0141] Proposition 1: The K multivariate function f(x.sub.1, x.sub.2, . . . , x.sub.K) with domain .sub.f where x.sub.k.sub.f for k[K] is the desirable function. Using identical modulation, all the users use the modulation . Then, function f can be uniquely determined by the constellation diagram of

[00005]${.Math.}_{k=1}^K\left(x_k\right),$

if f is a symmetric function with respect to all input variables in its domain i.e. the function is unchanged by any permutation of its variables.

[0142] Proof. For simplicity, we assume K=2, and f(x.sub.1, x.sub.2) is not a symmetric function i.e. f(a,b)f(b, a) where a, b.sub.f. Then, for a case where x.sub.1=a and x.sub.2=b, we have {right arrow over (a)} and {right arrow over (b)} as modulated signal thereof and {right arrow over (a)}+{right arrow over (b)} would be received by server, accordingly. It is easy to see that for the reverse scenario i.e. x.sub.1=b and x.sub.2=a the server also observed {right arrow over (a)}+{right arrow over (b)}. Therefore, we have same constellation point for the different values of asymmetric function f and it is impossible to assign the same vector {right arrow over (a)}+{right arrow over (b)} to the two different values of f(a, b) and f(b, a).

[0143] Here, the modulation and the domain may not be determined. Therefore, the proposition is valid for any arbitrary modulation with different number of bits for each user. If one restricts the domain to binary, this condition can be also sufficient. In fact, for one bit communication this argument is the only required condition for the function f to be computed correctly.

[0144] To see why this condition is not a sufficient condition, one can check a simple function f(x.sub.1, x.sub.2)=x.sub.1x.sub.2. Indeed, instead of one bit for each user if we enlarge the domain to two bits for instance, then there could be exist some points that have different values of a certain constellation point. For instance, Table FIG. 6 shows a counter example for this case. FIG. 6 shows a counter example to show that being symmetric is not sufficient to be computable. Here, x.sub.1x.sub.2 is a symmetric function respect to x.sub.1 and x.sub.2 while we can not compute this function because of conflict occurs on point {right arrow over (2)}. In fact, it needs to assign simultaneity this constellation point to the two different values 0 and 1 which is impossible.

[0145] To give insight, one may consider the summation

[00006]${.Math.}_{k=1}^K\left(x_k\right)$

as a function that map the q.sup.K points in the domain of function to a lower number of constellation points over the air. Moreover, if we define R.sub.s as range set of summation

[00007]${.Math.}_{k=1}^K\left(x_k\right)$

and R.sub.f to be the range of desired function f. Then, one has the following lower and upper bound on cardinality of R.sub.s when using same modulation.

[0146] Proposition 2: Assume that one has K different points x.sub.k which each one consists of q distinct points in 2D space. Then, the aggregation of the modulated signals i.e.

[00008]${.Math.}_{k=1}^K\left(x_k\right)$

can not impose lower than (q1)K+1 number of distinct constellation points and greater than

[00009]$\left(\begin{array}{c}K+q-1\\ q-1\end{array}\right).$

In other words, for ine range of summation R.sub.s we have that

[00010]$\left(q-1\right)K+1.Math.R_s.Math.\left(\begin{array}{c}K+q-1\\ q-1\end{array}\right)$

[0147] The upper bound and lower bound in (2) are also the limitation on the symmetry function. As a result, if the range of desirable function f be greater than existed points by the constellation points i.e. |R.sub.f||R.sub.s|, then it may be impossible to cover perfectly all the range of function.

[0148] As mentioned earlier, using same modulation would limit us to the symmetric function. To go beyond symmetric function, one needs to change the modulation in a such way that allows us to compute any class of function. In what follows, one looks for a finding the best possible modulation under different scenarios in order to obtain a reliable computation over the network.

Analog Modulations

[0149] It should be highlighted that the modulation (.) can be any type of analog or digital modulation, regardless of it has an analog or digital carrier, or the input of the data is digital or analog. For the digital carriers such as pulse amplitude (PAM), pulse position (PPM) and etc., one can solve the problem for each symbol per time and decode the data in a sequence of time. For the analog data, using the quantization step (see FIG. 2) allows to perform ChannelComp for either analog modulation such as amplitude

[0150] (AM), phase (PM), and frequency modulations (FM), or digital modulation e.g. ASK, PSK, FSK, and QAM. As long as input data are finite points, the resultant overlapped signal would read to finite constellation points which accordingly lets the desired function f to be computed by designing a proper tabular function to map the finite constellation points to the output of the function f. To be more specific, let x.sub.1, x.sub.2 be the input values of the first and the second users, respectively. The quantization converts the x.sub.1 and x.sub.2 into {0,1, . . . , q1} where q shows the quantization levels. Next, using any analog modulation for transmitting and would lead to at most qq different points each point can represent different amplitudes or phases. Since received signals have finite constellation points, one can a tailor tabular which maps q.sup.2 points to the output of the range of function R.sub.f. In this regime, the communication system does not need to be changed and the only requirement is to add quantizer to the transmitter and tabular function to the receiver side.

Modulation Selection in ChannelComp

[0151] As mentioned, to transmit the value of k-th node using BPSK modulation over the AWGN channel, one first quantizes the scalar x.sub.k(t) to q bit values and then modulates it by a carrier. For the case of BPSK modulation, the scalar x.sub.k(t) is one-bit quantized to {tilde over (x)}.sub.k{0,1} for which we have {tilde over (x)}.sub.k=x.sub.k(t)+q.sub.k(t) where q.sub.k(t) denotes the quantization error of the k-th symbol. The resultant symbol modulated by a basis signal {right arrow over (x)}.sub.k(t) where

[00011]${}_k\left({\tilde{x}}_k\right)=\{\begin{array}{c}E\cos \left(2f_{c}t+\right),{\tilde{x}}_k=1\\ E\cos \left(2f_{c}t\right),{\tilde{x}}_k=0\end{array}.$

[0152] Here, E and f.sub.c are amplitude and frequency of the career signal, respectively. In the sequel, to alleviate notation for general cases, one uses representation of band-pass signals where allows to represent a signal by only its amplitude and phase. Particularly, one expands a general form of the cosine function as follows

[00012]$\begin{array}{c}{\stackrel{.fwdarw.}{x}}_k\left(t\right)=E_k\cos \left(2f_{c}t+{}_k\right),\\ =E_k\mathrm{co}\underset{E_{1,k}}{\underset{}{s}}\left({}_k\right)\cos \left(2f_{c}t\right)+E_k\mathrm{si}\underset{E_{2,k}}{\underset{}{n}}\left({}_k\right)\sin \left(2f_{c}t\right)\\ =E_{1,k}\cos \left(2f_{c}t\right)+E_{2,k}\sin \left(2f_{c}t\right),\end{array}$

[0153] This expression is desired form for the representation of a band-pass signal {right arrow over (x)}.sub.k(t) where E.sub.1,k and E.sub.2,k are well known as quadratic components of the band-pass signal. In the signal space domain, {right arrow over (x)}.sub.k(t) can be considered as a complex like x.sub.k whose real and imaginary parts are E.sub.1,k and E.sub.2,k, respectively. The complex number x.sub.k also can be seen in the polar domain with amplitude E.sub.k and phase .sub.k that shows one bit data. To generalize the problem, the inventors assume k-th user transmit q.sub.k over the communication time-invariant or time-variant channel which equivalently means x.sub.k has q.sub.k complex numbers to transmit. Therefore, one can represent modulated signal {right arrow over (x)}.sub.k(t) by a complex vector x.sub.k.sup.q.sup.k.sup.1 where x.sub.k,i shows element i-th of this vector (e.g. see FIG. 7). Furthermore, the inner product of two complex signals {right arrow over (x)}.sub.k and defined on interval [a, b] is considered as inner product of continuous functions i.e.

[00013]$.Math.{\stackrel{.fwdarw.}{x}}_k\left(t\right),{\stackrel{.fwdarw.}{x}}_{}\left(t\right).Math.={}_a^b{\stackrel{.fwdarw.}{x}}_k\left(t\right){\stackrel{.fwdarw.}{x}}_{}^{*}\left(t\right)\mathrm{dt},$

[0154] Subsequently, two signals are not linearly independent unless their inner product be zero. Also, the norm of signal {right arrow over (x)}.sub.k is defined

[00014]$.Math.{\stackrel{.fwdarw.}{x}}_k\left(t\right).Math.={\left({}_a^b{.Math.{\stackrel{.fwdarw.}{x}}_k\left(t\right).Math.}^2\mathrm{dt}\right)}^{1/2},$

[0155] We recall the received signal by CP i.e. y(t) is equal to .sub.k{right arrow over (x)}.sub.k which has finite constellation points. Invoking the complex vector representation of each x.sub.k, we can represent all possible constellation points as shown in FIG. 4, where

[00015]$A{\left\{0,1\right\}}^{{.Math.}_{k=1}^K{q}_k{.Math.}_K{q}_k}$

is a binary matrix that select the all possible cases of users to send their data and the vector x.sup..sup.K.sup.q.sup.k.sup.1 consist of all K block of complex vector where block k-th is a modulation of corresponding node i.e. node k-th. Also, (.sub.Kq.sub.K)1 vector s denotes all possible constellation points over the channel. For simplicity, the inventors may assume all the users send exactly log(q) number of bits. To alleviate the notation, let N:=qK and M:=q.sup.K, then A{0,1}.sup.MN and x.sup.N1.

Feasibility Check

[0156] In order to compute the function f associate with modulated signal x.sub.1, . . . , x.sub.K, one needs to make sure that employed modulations for nodes are able to compute accurately the desired function. the first necessary condition under which prefect computation can be possible is related to range of function R.sub.f and rang of the summation over the channel R.sub.s. Indeed, the number of constellation points at receiver has to be greater than range of function f i.e. |R.sub.s||R.sub.f|. To illustrate that this condition is not sufficient, one can consider function f to be x.sub.1x.sub.2+x.sub.1 for x.sub.1, x.sub.2{0,1} where the signals modulated using BPSK. In FIG. 8, the inventors depicted the ranges points of the function f and summation over channel i.e. .sub.k[K]{right arrow over (x)}.sub.k. While having |R.sub.s|=|R.sub.f|=3, the function f can not be computed by this communication model (modulation).

[0157] FIG. 8 shows a counter example to demonstrate that R.sub.sR.sub.f is not enough to compute function f. Since there exist a conflict on point {right arrow over (1)}, we ca not compute the function while R.sub.f=R.sub.s=3.

[0158] Furthermore, it requires that the .sub.Kx.sub.k covers all the range of function f. In fact, for i[M], let f.sub.i be an output of function f for a certain value of input x.sub.1, x.sub.2 . . . , x.sub.K where all x.sub.ks have same q possible values. Then, if f.sub.i is different from f.sub.j, it requires the correspondence constellation point s.sub.i also must not be as the same as s.sub.j for ij see FIG. 9. Therefore, to verify that given modulation signals are suitable for computing the desired function f, one can solve the following problem (10)

[00016]${}_1=\mathrm{find}x$$s.t.f_i{f}_{j_{.Math.}}{s}_i{s}_j,$$\left(i,j\right)\left[M\right]\left[M\right],$

in which x.sup.N1 is the modulation vector. This is a feasibility problem wherein it finds a point that satisfies the constraints. As we can see, the constraints are not convex and non-continuous that it turns the problem to be NP-hard. To overcome this issue, the inventors replace the condition with its convex relaxation as follows (11)

[00017]${}_2=\mathrm{find}x$$s.t.{.Math.s_i-s_j.Math.}^2{.Math.f_i-f_j.Math.}^2,$$\left(i,j\right)\left[M\right]\left[M\right],$

where >0 is a positive constant. The inventors have shown that for a enough large Problem .sub.1 can be equal to .sub.2. Therefore, the inventors can deduce that these two problems are equal to each other. Since there is no assumption on the amplitude of variable x, the constant can be absorbed by x and we drop it from optimization problem .sub.1, accordingly. To determine whether the constraints are consistent, and if so, find a point that satisfies them, we have the following lemma.

[0159] Lemma 1: Let .sub.i,js for (i, j)[M][M] be the Lagrangian multipliers corresponding to the constraints of optimization problem i.e. .sub.2. Then, the problem .sub.2 is feasible if and only if

[00018]$\underset{ji,j}{\overset{}{.Math.}}\underset{i}{\overset{}{.Math.}}{}_{i,j}{B}_{i,j}x=0$${}_{i,j}=0,.Math.{.Math.f_i-f_j.Math.}^2{.Math.s_i-s_j.Math.}^2$${}_{i,j}>0,.Math.{.Math.f_i-f_j.Math.}^2={.Math.s_i-s_j.Math.}^2,$

where B.sub.i,j=(a.sub.ia.sub.j)(a.sub.ia.sub.j).sup.T and a.sub.i denotes i-th rows of matrix A.

[0160] Indeed, the Lagrangian multipliers of optimization in .sub.2 is built as below (15)

[00019]$=\underset{ji,j}{.Math.}\underset{i}{.Math.}{}_{i,j}\underset{g_{i,j}}{\underset{}{\left(-{.Math.s_i-s_j.Math.}^2+{.Math.f_i-f_j.Math.}^2\right)}}.$

[0161] Since the constraint are convex and differentiable, from KKT conditions, the inventors know that the feasible points must satisfy the following conditions (16)

[00020]$\underset{ji,j}{.Math.}\underset{i}{.Math.}{}_{i,j}{g}_{i,j}=0$${}_{i,j}=0,.Math.g_{i,j}0$${}_{i,j}>0,.Math.g_{i,j}=0,$

where g.sub.i,j is the gradient respect to x i.e. (19)

[00021]$g_{i,j}=-2{\left(\underset{B_{i,j}}{\underset{}{\left(a_i-a_j\right)\left(a_i-a_j\right)}}\right)}^{}x,$

in which a.sub.i denotes i-th rows of matrix A. By substituting (19) in (16), it gives us

[00022]$\underset{ji,j}{\overset{}{.Math.}}\underset{i}{\overset{}{.Math.}}{}_{i,j}{B}_{i,j}x=0$${}_{i,j}=0,.Math.{.Math.f_i-f_j.Math.}^2{.Math.s_i-s_j.Math.}^2$${}_{i,j}>0,.Math.{.Math.f_i-f_j.Math.}^2={.Math.s_i-s_j.Math.}^2,$

for ij. Therefore, giving the modulation vector x, yhe inventors can obtain the conditions under which function f can be computed perfectly. In what follows, we solved conditions in (16) for standard modulations such as BPSK and QPSK for class of linear functions.

Linear Functions

[0162] In this subsection, the inventors used the KKT conditions for a linear function to provide guarantee in which linear functions can be compute for a certain modulation. A linear function f: .sup.K is defined

[00023]$f\left(x_1,.Math.,x_k\right)=\underset{k=1}{\overset{K}{.Math.}}{a}_k{x}_k+c,$

where a.sub.1, . . . , a.sub.K and c are real constant numbers. Here, the inventors aim at determining the constraints for the case of linear functions in two different scenarios where all the users using same modulations or different modulations. We first solve KKT condition (16) for a linear function f with binary domain i.e. q=1 where users using BPSK modulation for their communication. Then, the invenrors repeat the analyze for the case in which each node has different modulations. Finally, the inventors extend the results for the K user with arbitrary modulation order q1.

Binary Domain Bi-Variable Function with BPSK

[0163] Let the desired function be f(x.sub.1, x.sub.2)=a.sub.1x.sub.1+a.sub.2x.sub.2+c where x.sub.1, x.sub.2{0,1} and their corresponding modulation signals {right arrow over (x)}.sub.1, {right arrow over (x)}.sub.2 are set to be BPSK. We can see the range of the function includes R.sub.f=f.sub.1, f.sub.2, f.sub.3, f.sub.4 where the values of f.sub.1, f.sub.2, f.sub.3 and f.sub.4 are equal to 0, a.sub.1, a.sub.2, a.sub.1+a.sub.2, respectively. Utilizing BPSK modulation for both users equals to set vector x to be [b, b, b, b].sup.T where b is a nonzero real number denotes amplitude for transmitting data which is the same for all the users here. Then, by putting the modulation vector x into (15), it gives us the following cost function in term of b and .sub.is

[00024]$={{}_{1,2}\left(2b\right)}^2+{{}_{1,3}\left(2b\right)}^2+{{}_{1,4}\left(4b\right)}^2+{}_{2,3}0+{{}_{2,4}\left(-2b\right)}^2+{{}_{3,4}\left(-2b\right)}^2.$

[0164] Next, by setting its derivative respect to b to be zero i.e.

[00025]$\frac{}{b}=0,$

we have

[00026]$-8\left({}_{1,2}+{}_{1,3}+4{}_{1,4}+{}_{2,4}+{}_{3,4}\right)b=0$

[0165] Hence, b0 is a nonzero real number and all Lagrangian multipliers are non-negative, we can directly conclude that all .sub.1,2=.sub.1,4=.sub.3,4=.sub.2,4=.sub.1,3=0 expect .sub.2,3>0. Then, the inventors know the Lagrangian multipliers for the next KKT conditions in (16) it needs absolute value of b be greater than |a.sub.1| and |a.sub.2| i.e.

[00027]$.Math.b.Math.\frac{\max \left\{.Math.a_1.Math.,.Math.a_2.Math.\right\}}{2}.$

[0166] Also, for the condition corresponding to .sub.2,3, the inventors need to check the last KKT condition in (16) that it leads to

[00028]$a_1=a_2.$

[0167] This is not valid in general. In other words, by using same BPSK modulation, one can not compute a linear function unless its coefficients have same value which is not enough general model.

Bi-Variable Function with Different Modulation

[0168] Here, we use different modulations for each user i.e. x=[b, b, d, d] in which d, b. It should be noted that this model for BPSK is general enough to include arbitrary one bit modulation because of symmetry of two points in a 2-D space.

[0169] Proposition 3: For a bi-variable function f(x.sub.1, x.sub.2)=a.sub.1x.sub.1+a.sub.2x.sub.2 where x.sub.1, x.sub.2{0,1} and a.sub.1, a.sub.2, we can compute the function over the air using BPSK modulation for two users with amplitudes d, b or equivalently x=[b, b, d, d], if and only if there exist an >0 such that

[00029]$$\begin{gathered} .Math.b.Math.\sqrt{}\frac{.Math.a_1.Math.}{2}, \\ .Math.d-b.Math.\sqrt{}\frac{.Math.a_1-a_2.Math.}{2}. \end{gathered}$$

[0170] At this time, the first condition gives

[00030]$$\begin{gathered} \frac{}{b}=b\left({}_{1,2}+{}_{1,4}+{}_{2,3}+{}_{3,4}\right)+d\left({}_{1,4}-{}_{2,3}\right)=0, \\ \frac{}{d}=d\left({}_{1,3}+{}_{1,4}+{}_{2,3}+{}_{2,4}\right)+b\left({}_{1,4}-{}_{2,3}\right)=0, \end{gathered}$$

[0171] By rearranging the coefficients of the equations, we have

[00031]$\left(b-d\right){}_{2,3}+\left(b+d\right){}_{1,4}+b\left({}_{1,2}+{}_{3,4}\right)=0\left(d-b\right){}_{2,3}+\left(b+d\right){}_{1,4}+d\left({}_{1,3}+{}_{2,4}\right)=0.$

[0172] Here, the inventors can see that either b>d or d>b in both cases, these equations enforces all of the Lagrangian multipliers .sub.1,2=.sub.1,4=.sub.3,4=.sub.2,4=.sub.1,3=.sub.2,3=0 to be zero which means all constraints are feasible. In particular, the function f can be computed if

[00032]$$\begin{gathered} .Math.b.Math.\frac{.Math.a_1.Math.}{2}, \\ .Math.d-b.Math.\frac{.Math.a_1-a_2.Math.}{2}, \end{gathered}$$

[0173] Next, by following similar steps for QPSK modulation it yields the condition under which function f would be computed as follows

[00033]$$\begin{gathered} .Math.b_1.Math.\frac{.Math.a_1.Math.}{2}, \\ .Math.b_2-b_1.Math.\frac{.Math.a_1-a_2.Math.}{2}, \end{gathered}$$

[0174] In what follows, the inventors extent the conditions for the general case of a linear function.

K Different Modulation with Different q.SUB.k .Bits

[0175] To extend the obtained results for the K different modulation, the inventors express modulation vector of the k-th user with q symbols by x.sub.k=[b.sub.k,1, b.sub.k,2, . . . , b.sub.k,q].sup.T.sup.q. In this case, the output of function are totally not equal to each other i.e. f.sub.if.sub.j for all possible (i, j) except i=j.

[0176] Proposition 4: For a K multi-variable function

[00034]$f\left(x_1,.Math.,x_k\right)={.Math.}_{k=1}^K{a}_k{x}_k+c$

where x.sub.k{0, . . . , q1} and a.sub.k for k[K], one can compute the function over the air using modulation vector {right arrow over (x)}.sub.k=d.sub.k[b.sub.1, b.sub.2, . . . , b.sub.q].sup.T.sup.q if and only if there exist >0 such that (40)

[00035]$.Math.\underset{k=1}{\overset{K}{.Math.}}{d}_k\left(b_{{}_k}-b_{r_k}\right).Math.\sqrt{}.Math.\underset{k=1}{\overset{K}{.Math.}}{a}_k\left(x_{{}_k}-x_{r_k}\right).Math.,$

for all (.sub.k, r.sub.k)[q][q] and k=[K].

[0177] Based on Proposition 4, modulation vector x.sub.k needs to satisfy q.sup.K conditions for computing linear functions. However, one can see that for linear functions if one sets

[00036]$d_k=a_k,\mathrm{and},b_r=x_r,$

for k[K], r[q], and an arbitrary complex number such that ||{square root over ()}, then all the constraints in (40) would be accordingly fulfilled. Moreover, by choosing elements of x.sub.k from (40) for ={square root over ()}, the cost function may equal to zero.

ChannelComp over AWGN Channels

[0178] In this section, one may consider a more realistic scenario where the channel coefficients are not ideal and the received data are polluted by Gaussian noise. The communication network is considered to be known and deterministic channels (i.e. prefect CSI), which restricts the applicability of the results to applications with known CSI. We also assumed that we have access to the prefect CSI at each time slot. Consequently, the measured signals at CP read to

[00037]${\stackrel{.fwdarw.}{y}}_n\left(t\right)=\underset{k\left[K\right]}{.Math.}{h}_k\left(t\right){\stackrel{.fwdarw.}{x}}_k\left(t\right)+z\left(t\right).$

[0179] Here, h.sub.k(t) is the known channel coefficient form k-th device to CP and z denotes AWGN noise with variance

[00038]${}_z^2.$

To alleviate the notation, let define vector h:=[h.sub.1, . . . , h.sub.K].sup.T.sup.K. Also, we need to define operator .sub.q: .sup.K.sup.NN as follows

[00039]${}_q\left(h\right)=\mathrm{diag}\left(h\right).Math.I_q=\mathrm{diag}\left(h_1{I}_q,.Math.,h_K{I}_q\right),$

where .Math. denotes Kronecker product and I.sub.q represent qq identity matrix. To alleviate the notation, we drop the sub index q. Then, the constellation points can be represented as

[00040]$A\left(h\right)x=\stackrel{}{s},$

where {tilde over (s)}=[{tilde over (s)}.sub.q, {tilde over (s)}.sub.2, . . . , {tilde over (s)}.sub.M].sup.T.sup.M denotes constellation points in the presence of fading. In this scenario, we can observe

[00041]${\stackrel{}{s}}_i=a_i^T\left(h\right)x.$

[0180] Since there exist noise in the channel, performance of computation network would be degraded by polluted signals {right arrow over (x)}.sub.ks which leads to the computation error. In addition, one need to ensure that received signals satisfy a minimum signal to noise ratio (SNR) constraint for providing a reliable communication. Therefore, the following constraints need to be taken into account (48)

[00042]$$\begin{gathered} {.Math.s_i-s_j.Math.}^2{.Math.f_i-f_j.Math.}^2, \\ \frac{{.Math.s_i-s_j.Math.}^2}{{}_z^2}{}_0. \end{gathered}$$

[0181] Here, the first condition in (48) control the computation. Since all the values in both sides of the equations (48) are positive, one consequence is the distance between each pair of the constellation points to be greater than product of both right side of them i.e.

[00043]${.Math.s_i-s_j.Math.}^2{}_z^2{}_0{.Math.f_i-f_j.Math.}^2$

for all (i, j). Accordingly, by incorporating the constraints, the inventors may propose the following optimization problem to find an appropriate modulation vector x for the communication and computation (50).

[00044]$\stackrel{}{x}=\underset{x}{\arg \min }{.Math.x.Math.}_2^{2}s.t.{.Math.{\left(a_i-a_j\right)}^T\left(h\right)x.Math.}^2{}_0{}_z^2{.Math.f_i-f_j.Math.}^2,$

for all (i, j)[M][M], ij. This problem is a quadratically constrained quadratic programming (QCQP) problem, but unfortunately the constraints are not convex. Non-convexity does not mean that the problem is difficult to solve; Nevertheless, this problem is a NP-hard problem. Toward solving this issue, the inventors use lifting trick in which the inventors first recast the cost function as bellow

[00045]$\stackrel{}{x}=\underset{x}{\arg \min }\mathrm{Tr}\left({\mathrm{xx}}^H\right)s.t.\mathrm{Tr}\left({\mathrm{xx}}^H{\tilde{B}}_{i,j}\right){\tilde{f}}_{i,j},$

where {tilde over (f)}.sub.i,j=.sup.1|f.sub.if.sub.j|.sup.2 for all (i, j).sup.2, ij and {tilde over (B)}.sub.i,j=(h).sup.T(a.sub.ia.sub.j)(a.sub.ia.sub.j).sup.T(h). Now, if one treats xx.sup.H as a matrix like X.sup.NN, then the problem may be reformulated as

[00046]$$\begin{gathered} \stackrel{}{X}=\underset{X}{\arg \min }\mathrm{Tr}\left(X\right)s.t..Math.X,{\tilde{B}}_{i,j}.Math.{\tilde{f}}_{i,j}, \\ X0,\mathrm{rank}\left(X\right)=1, \end{gathered}$$

in which the inequality X0 means that the matrix X is symmetric positive semi-definite and X, {tilde over (B)}.sub.i,j represents matrix inner product i.e.

[00047]$\mathrm{Tr}\left(X{\tilde{B}}_{i,j}^T\right).$

This is linear and convex problem respect to matrix X except about the rank constraint. One possible way to handle this issue is to relax the problem by dropping the rank-one constraint from the optimization which leads to

[00048]$$\begin{gathered} \stackrel{}{X}=\underset{X}{\arg \min }\mathrm{Tr}\left(X\right)s.t..Math.X,{\tilde{B}}_{i,j}.Math.{\tilde{f}}_{i,j}, \\ X0, \end{gathered}$$

which is a SDP problem, and it can be efficiently solved by using CVX. Afterwards, the optimal modulation vector x solution to the original problem can be obtained via Cholesky decomposition of X* unless the solution to the SDP problem becomes a rank one matrix; otherwise, as a sub-optimal solution to the original problem, one can use the Gaussian randomization method. Nevertheless, the solution of the relaxed problem oftentimes does not meet the rank-one constraint and is a sub-optimal, especially for cases wherein the dimension of the optimization variables becomes large i.e. N>>1. To overcome the mentioned drawback, the rank-one constraint may be replaced by another equivalent function which would be successively solved using the primal and dual problems thereof. Particularly, the inventors have the representation in the following Lemma for the rank-one constraint.

[0182] Proposition 6: For a PSD matrix X.sup.NN with Tr(X)>0, we have

[00049]$\mathrm{rank}\left(X\right)=1Tr\left(X\right)-{.Math.X.Math.}_2=0,$

where .sub.2 denotes spectral norm.

[0183] As a result, the inventors may replace rank one constraint with the penalty term in the Proposition 6 as follows

[00050]$$\begin{gathered} \stackrel{}{X}=\underset{x}{\arg \min }\mathrm{Tr}\left(X\right)+\left(\mathrm{Tr}\left(X\right)-{.Math.X.Math.}_2\right)s.t..Math.X,{\tilde{B}}_{i,j}.Math.{\tilde{f}}_{i,j}, \\ X0. \end{gathered}$$

where >0 is the penalty parameter. As the aforementioned problem is still non-convex, the optimization can be solved using difference-of-convex (DC) programming algorithm.

Computation with Minimizing Maximum Error

[0184] Another interesting approach to have a reliable computation or equivalently computation with minimum error is to minimize the maximum error coming from detection. Particularly, let P.sub.i,j be probability of the error of computing f.sub.j instead of f.sub.i, then, the computation error can be defined as E.sub.i,j:=P.sub.i,j|f.sub.if.sub.j|. As a result, one can solve the following optimization problem

[00051]$\stackrel{}{x}=\underset{x}{\arg \min }\underset{i,j}{\max }{P}_{i,j}.Math.f_i-f_j.Math.s.t.{.Math.x.Math.}_2^{2}P,$

where the last condition is the maximum available power budget for the communication. Also, it has been assumed that all constellation symbols are selected for transmission with equal probability. We can see this problem is too complicated to be solved. One possible approximation solution is to employ union bound of the probability of the error P.sub.i,j i.e.

[00052]$P_{i,j}Q\left(\sqrt{\frac{{.Math.{\left(a_i-a_j\right)}^{T}x.Math.}^2}{2{}_z}}\right),$

as a surrogate function to replace a simple upper bound with the complex cost function. The rationale is that as the Q-function decrease, the probability of error P.sub.i,j shall also diminish. However, working with Q function is still difficult, one well-known way to upper bound the Gaussian Q-function is to use the Chernoff upper bound i.e.

[00053]$Q\left(x\right)\frac{e^{-x^2/2}}{2}$

accordingly. More accurate approximations than the Chernoff bound is also proposed as Chiani bound. However, in our optimization problem, Chiani bound can make the problem more complicated. Hence, using Chernoff bound, the objective function reads to

[00054]$\hat{x}=\underset{x}{\mathrm{argmin}}\underset{i,j}{\max }\exp \left(-\frac{{.Math.{\left(a_i-a_j\right)}^{}\left(h\right)x.Math.}^2}{4{}_z}\right)\frac{.Math.f_i-f_j.Math.}{2}$$s.t.{.Math.x.Math.}_2^{2}P,$

[0185] Next, by taking the logarithm of the objective function and taking out mines thereof, one could reach to

[00055]$\begin{array}{cc}\hat{x}=\underset{x}{\mathrm{argmax}}\underset{i,j}{\min }& \frac{x^{}{\tilde{B}}_{i,j}x}{4{}_z}-\log \left(\frac{.Math.f_i-f_j.Math.}{2}\right)\\ s.t.& {.Math.x.Math.}_2^{2}P,\end{array}$

[0186] This problem special class of non-convex QCQP problems is a non-smooth, non-convex optimization problem due to the fact that the point-wise minimum of convex quadratics is non-differentiable and non-concave. For solving this problem, one can use successive convex approximation (SCA) method. In particular, the inventors iteratively approximate the primal non-convex problem by a sequence of convex problem. A feasible point x.sup.(0) is picked as a starting point, then the algorithm proceeds by minimizing a convex majorization function of the non-convex cost function. Now, let us define the function .sub.(x, x.sup.(t)) as follows

[00056]${}_{}\left(x,x^{\left(t\right)}\right):=\log \left(\underset{i,j}{\overset{M}{.Math.}}\exp \left(\frac{c_{i,j}^{\left(t\right)H}x+d_{i,j}^{\left(t\right)}}{}\right)\right),$

where

[00057]$c_{i,j}^{\left(t\right)}=2{\tilde{B}}_{i,j}{x}^{\left(t-1\right)},\mathrm{and}{d}_{i,j}^{\left(t\right)}={x^{\left(t-1\right)}}^H{\tilde{B}}_{i,j}{x}^{\left(t-1\right)}-\log \left(.Math.f_i-f_j.Math./2\right).$

Then, at each iteration we would solve the following optimization

[00058]$\begin{array}{cc}\underset{x}{\min }& {}_{}\left(x,c_{i,j}^{\left(t\right)},d_{i,j}^{\left(t\right)}\right)\\ s.t.& {.Math.x.Math.}_2^{2}P,\end{array}$

[0187] Since it is a smooth optimization problem, accordingly, it can be solved using an accelerated first order method like Nesterov's smoothing technique. The overall SCA procedure may be implemented in an Algorithm.

Computation with Minimizing Average Error

[0188] On the other hand, minimizing computation error can be implemented through minimizing the average error coming from detection. Particularly, for probability of the error of computing f.sub.j instead of f.sub.i, one can solve the following optimization problem

[00059]$\begin{array}{cc}\hat{x}=\underset{x}{\mathrm{argmin}}& \underset{i}{\overset{M}{.Math.}}{}_i\underset{j=1}{\overset{M}{.Math.}}{P}_{i,j}{.Math.f_i-f_j.Math.}^2\\ s.t.& {.Math.x.Math.}_2^{2}P,\end{array}$

where .sub.i represents the probability of transmitting signal to compute f.sub.i. Similar to the previous optimization problem, the inventors are able to approximate the probabilities of error using an upper bound which allows us to culminate into a convex optimization problem as follows:

[00060]$\begin{array}{cc}\hat{x}=\underset{x}{\mathrm{argmin}}& \underset{i}{\overset{M}{.Math.}}{}_i\underset{j=1}{\overset{M}{.Math.}}{e}^{\left(-\frac{{.Math.{\left(a_i-a_j\right)}^{}\left(h\right)x.Math.}^2}{4{}_z}\right)}{.Math.f_i-f_j.Math.}^2\\ s.t.& {.Math.x.Math.}_2^{2}P,\end{array}$

[0189] Here, we again use lifting trick by defining X=xx.sup.T and {tilde over (B)}.sub.i,j=(a.sub.ia.sub.j)(a.sub.ia.sub.j).sup.T. After substituting the variables, the optimization problem therefore is given in following (63)

[00061]$\begin{array}{cc}\hat{x}=\underset{x}{\mathrm{argmin}}& \underset{i}{\overset{M}{.Math.}}{}_i\underset{j=1}{\overset{M}{.Math.}}\exp \left(-\frac{.Math.X,{\tilde{B}}_{i,j}.Math.}{4{}_z}\right){.Math.f_i-f_j.Math.}^2\\ s.t.& .Math.X,I.Math.P,X0\end{array}$

where rank(X)=1 constraint has been dropped as a relaxation step.

[0190] Proposition 7: the optimization problem in (63) is convex in X0.

[0191] Proof. Since {tilde over (B)}.sub.i,j0 is a positive semi-definite matrix for (i, j)[M][M], we have that:

[00062]$\frac{\exp \left(-\frac{.Math.X,{\tilde{B}}_{i,j}.Math.}{4{}_z}\right)}{X}=-\frac{{\tilde{B}}_{i,j}}{4{}_z}\exp \left(-\frac{.Math.X,{\tilde{B}}_{i,j}.Math.}{4{}_z}\right)0,$$\frac{{}^2\exp \left(-\frac{.Math.X,{\tilde{B}}_{i,j}.Math.}{4{}_z}\right)}{X^2}=-\frac{{\tilde{B}}_{i,j}^2}{16{}_z^2}\exp \left(-\frac{.Math.X,{\tilde{B}}_{i,j}.Math.}{4{}_z}\right)0.$

[0192] Since the convexity is preserved under an affine transformation, the objective function in (63) is accordingly a convex function (48).

[0193] It is well known that a convex optimization problem can be solved by using interior point methods which require polynomial complexity. Utilizing log barrier method is a standard method to solve the optimization in (63).

Stochastic Fading Channel

[0194] The nodes usually can estimate the channel coefficients h.sub.ks and use the estimation as imperfect value to perform the communication. However, there exist scenarios where one is not able to estimate the channel. In this case, by modeling the physical model of communication, the nodes can obtain a distribution for the channel. One well-known stochastic model for radio propagation is to consider Rician distribution for the channel. The Rician fading typically occurs when one of the paths, a line of sight signal is much stronger than the others. Without line of sight signal, it can be shown that the distribution would be reduced to Rayleigh fading.

[0195] Since channel coefficients h.sub.ks are no longer deterministic, accordingly, the mentioned minimization problems become random optimization. To perform Digital ChannelComp, one possible solution is to replace the computation condition by its expectation respect to h.sub.ks i.e. the computation condition would read to

[00063]$\left[{.Math.{\left(a_i-a_j\right)}^{}\left(h\right)x.Math.}^2\right]{}_0{}_z^2{.Math.f_i-f_j.Math.}^2$${\left(a_i-a_j\right)}^{}{C}_h\left(a_i-a_j\right){}_0{}_z^2{.Math.f_i-f_j.Math.}^2$$\mathrm{where}$$\begin{array}{c}{C}_h=\left[\left(h\right){\mathrm{xx}}^{}\left(h\right)\right]\\ =\left[\left({\mathrm{hh}}^H.Math.I_q\right){\mathrm{xx}}^{}\right]\\ =\left(\left[{\mathrm{hh}}^H\right].Math.I_q\right){\mathrm{xx}}^{},\end{array}$

where indicates Hadamard product. Next, for [hh.sup.H], we have

[00064]$\left[{\mathrm{hh}}^H\right]=\left[\begin{array}{cccc}{}_{h_1}^2& {}_{h_1}{}_{h_2}& .Math.& {}_{h_1}{}_{h_K}\\ {}_{h_2}{}_{h_1}& {}_{h_2}^2& .Math.& {}_{h_2}{}_{h_K}\\ .Math.& .Math.& .Math.& .Math.\\ {}_{h_K}{}_{h_1}& .Math.& .Math.& {}_{h_K}^2\end{array}\right]$

in which .sub.h.sub.K and

[00065]${}_{h_k}^2$

are the mean and variance of the distribution of h.sub.k, respectively. Therefore, the inventors replace channel coefficients by their available mean from the distribution and then through same optimization can be determined the modulation. Note that in this case, the solution of the optimization is also valid in expectation and the computed value for the function f are not always correct, accordingly.

MIMO Digital Computation For Matrix Calculation

[0196] In the previous sections, the existing solutions focus only on single-function AirComp, assuming there exists a single antenna on each node. However, in the next generation of wireless networks, the nodes equipped with large-scale arrays will provide the possibility of computing multiple functions of multi-data AirComp, simultaneously. This inspires us to extend the previous optimization for a multi-input multi-output (MIMO) MAC in which we have multi-function computation. We reconsider a wireless network consisting of K multi-nodes and a single receiver CP. Particularly, each node uses N.sub.t antennas for transmitting data and N.sub.r antenna existed at CP.

[0197] The MIMO structure can be effective on both improvement of the computation rate or decreasing the distortion. Others have developed a MIMO setup for AirComp using beam-forming techniques in analog modulation. Moreover, they designed beam-forming to minimize the mean square error (MSE) criterion to remove resultant distortion by the AWGN noise and the fading. Here, the inventors instead aim to utilize the channel state information to design constellation points so that the inventors can satisfy the computation constraints.

[0198] In the following subsection, the inventors have discussed two possible different scenarios for MIMO of the DiChComp.

MIMO for Improving Distortion

[0199] For the first setup, we aim to decreasing only noise effect by using beam-former for compute a desire function f(x.sub.1, . . . , x.sub.K):.sup.K.sup.L with L output (L must be lower than number of receiver antenna i.e. LN.sub.r). In the note worthy case L=1, the computation problem would be reduced to the previous scalar function problem. Therefore, the computation problem is extended to a vector function instead of a scalar function together with using beam-formers at transmitters and receivers to decrease distortion. To illustrate, consider the following systems of linear equations as an example of desired function f for an input vector x.sup.K

[00066]$f\left(x\right)=Ax+b,$

where A.sup.LK and b.sup.L. Here, i-th element of the input vector i.e. x.sub.i can correspond to data of i-th node for i[K]; j-th element of the out put vector i.e. [f].sub.j corresponds to the received data by j-th antenna at receiver, accordingly. Assuming symbol-level synchronization, all users transmit their symbol vectors simultaneously using their arrays. The distortion of the received vector concerning the target function vector due to MIMO channels and noise is suppressed using transmit and receive beam-forming. In other words, the joint beam-forming attempts to attain coherent combining of K symbol vectors at the CP. Particularly, let v.sub.k.sup.N.sup.t.sup.1 is the transmit beam-forming vector at sensor k and U.sup.N.sup.r.sup.L denotes the receive beam-forming matrix (see FIG. 10). Then, the measured signals received by CP over MAC at time t is (73)

[00067]${\stackrel{.fwdarw.}{y}}_n\left(t\right)=U^H\left(\underset{k\left[K\right]}{.Math.}{H}_k\left(t\right)v_k{\stackrel{.fwdarw.}{x}}_k\left(t\right)+Z\left(t\right)\right),$

where Z(t).sup.N.sup.r.sup.1 denotes the AWGN vector with independent and identically distributed (i.i.d.) (0, .sub.zI.sub.N.sub.r.sub.N.sub.r). Next, let x.sub.k.sup.q be the modulation vector of signal {right arrow over (x)}.sub.k and vector c.sub.k.sup.N.sup.t.sup.q1 be the Kronecker product of two vectors v.sub.k and x.sub.k i.e. c.sub.k:=x.sub.k.Math.v.sub.k. In addition, for the channel coefficients between transmitters and receivers, we have the following NN.sub.rNN.sub.t complex matrix

[00068]$:=\mathrm{diag}\left(\left[I_{qq}.Math.H_1,.Math.,I_{qq}.Math.H_K\right]\right),$

where .Math. denotes the Kronecker product. We further define C=[c.sub.1, . . . , c.sub.K].sup.T.sup.NN.sup.t.sup.1, and =A.Math.I.sub.N.sub.r.sub.N.sub.r which is a MN.sub.rNN.sub.r matrix, =I.sub.MM.Math.U.sup.MN.sup.r.sup.ML. Hence, for the constellation points, we have

[00069]${}^H\tilde{A}C=S$

where S.sup.ML. For sake of simplicity, we decompose the C as v where v=[v.sub.1, . . . , v.sub.K].sup.T.sup.N.sup.t.sup.K1 and :=diag ([.sub.N.sub.t(x.sub.1), . . . , .sub.N.sub.t(x.sub.K)]) in which .sub.N.sub.t is an linear operator which for a vector a.sup.q is defined as

[00070]${}_{N_t}\left(a\right):={\left[a_1{I}_{N_t{N}_t}.Math.,a_N{I}_{N_t{N}_t}\right]}^{}{}^{N_{t}q{N}_t},$

where a.sub.i denotes i-th element of vector a. For computing the vector function f.sup.L, the computation condition in (10) needs to be modified, consequently. We bring this condition in the form of the following proposition.

[0200] Proposition 8: Let f.sub.i.sup.L be the i-th output of the function for a certain value of input x.sub.1, x.sub.2, . . . , x.sub.K from [M.sup.L] possible values of the function f and also, s.sub.i.sup.L represents the corresponding L constellation points. Then, the computation is valid if and only if when we have the following

[00071]$\mathrm{if}{f}_i{f}_j.Math.s_i{s}_j,$

where s.sub.i denotes i-th rows of matrix S.

[0201] We suggest a similar relaxation to (11) for the mentioned condition in Proposition (8) which leads to following feasibility problem

[00072]$\begin{array}{cc}{}_{M-\mathrm{feas}}=\mathrm{find}& v,U\\ s.t.& {.Math.s_i-s_j.Math.}_2^2{.Math.f_i-f_j.Math.}_2^2,\\ & \left(i,j\right)\left[M^L\right]\left[M^L\right],\end{array}$

[0202] As a result, in the MIMO scenario, using the aforementioned condition and matrix notation, one can reformulate the optimization in (50) for a given set of modulation vectors

[00073]${\left\{x_k\right\}}_{k=1}^K$

as follows

[00074]$\begin{array}{cc}\stackrel{}{v},\widehat{.Math.}=& \arg \underset{v,.Math.}{\min }{.Math.v.Math.}_2^2\\ s.t.& {.Math.{.Math.}^H\left({\tilde{A}}_i-{\tilde{A}}_j\right)v.Math.}_2^2{}_0{}_z^2{.Math.f_i-f_j.Math.}_2^2\end{array}$

where .sub.i denotes i-th block matrix of size N.sub.rNN.sub.r of matrix . Similarly, the other optimizations can be addressed as follows (79)

[00075]$\begin{array}{cc}\stackrel{}{v},\hat{U}=\underset{v,U}{\mathrm{argmax}}\underset{i,j}{\min }& \underset{k}{.Math.}\frac{v_k^{}{C}_{i,j}{v}_k}{4{}_z}-\log \left(\frac{{.Math.f_i-f_j.Math.}_2}{2}\right)\\ s.t.& {.Math.v_k.Math.}_2^2{P}_k,\end{array}$$\mathrm{where}$$C_{i,j}={}^H{{}^H\left({\tilde{A}}_i-{\tilde{A}}_j\right)}^H{\mathrm{UU}}^H\left({\tilde{A}}_i-{\tilde{A}}_j\right),$

and P.sub.k denotes allocated power budget for node k. Similarly, for minimizing the average error we have that

[00076]$\begin{array}{ccc}\hat{V},\widehat{.Math.}=\mathrm{argmin}& V,.Math.{.Math.}_{i=1}^M{.Math.}_{j=1}^M\exp \left(-\frac{.Math.V,\widetilde{c_{i,j}.Math.}}{4{}_z}\right){.Math.f_i-f_j.Math.}_2^2& \\ s.t.& .Math.V,I.Math.P,& V0\end{array}$

in which V=vv.sup.H is the lifted variable of vector v. The mentioned optimization can be solved by suggested solution in the previous section.

MIMO for Increasing Computation Rate

[0203] In subsection, the inventors consider another MIMO extension of the computation model in which the model allows us simultaneously compute functions with different input data for each node. The model would be designed such that it aids us to increasing the rate of computation instead of decreasing the distortion in the previous subsection. Particularly, we consider the scenario where the goal is to compute R desire functions f.sup.(r)(x.sub.1, x.sub.2, . . . , x.sub.K):.sup.Kfor r[R] whose input x.sub.k.sup.R contains R values of k-th node i.e. {right arrow over (x)}.sub.k=[{right arrow over (x)}.sub.k,1, {right arrow over (x)}.sub.k,2, . . . , {right arrow over (x)}.sub.k,R].sup.T. For the validation, the rate R must be lower than number of transmitters and receivers antenna i.e. Rmin{N.sub.t, N.sub.r}. To give better insight, consider the following linear equation

[00077]$f^{\left(r\right)}:=\underset{k}{.Math.}{a}_{k,r}{x}_{k,r}+b_r,$

for r[R]. In the case of {right arrow over (x)}.sub.k,j={right arrow over (x)}.sub.k,i for i, j[R] and k[K], this model reduce to the previous MIMO model. The measured signals received by CP over MAC at time t is

[00078]${\stackrel{.fwdarw.}{Y}}_n\left(t\right)=U^H\left(\underset{k\left[K\right]}{.Math.}{H}_k\left(t\right)V_k{\stackrel{.fwdarw.}{x}}_k\left(t\right)+Z\left(t\right)\right),$

where V.sub.k.sup.N.sup.t.sup.R and U.sup.N.sup.r.sup.R are beam-forming matrices at k-th transmitter and receiver, respectively. The inventors further define the modulation matrix as

[00079]$X_k={\left[{\stackrel{.fwdarw.}{x}}_k^1,.Math.,{\stackrel{.fwdarw.}{x}}_k^q\right]}^{}{}^{qR},$

[0204] Beside, we define

[00080]$C_k:=\mathrm{vec}\left(V_k{X}_k^{}\right){}^{N_{t}q1}$

or equivalently (X.sub.k.Math.V.sub.k).sub.R.sub.2 where .sub.R.sub.2:=vec(I.sub.RR). Accordingly, one has matrix {tilde over (C)}=[C.sub.1, . . . , C.sub.K].sup.T and =I.sub.MM.Math.U. Therefore, the measured constellation points at CP is

[00081]${\tilde{U}}^H\tilde{A}\stackrel{}{C}=S$

where S=[s.sub.1, . . . , s.sub.M].sup.T and s.sub.k.sup.R for k[M]. Similarly, it can be seen that matrix {tilde over (C)} can be written as W{tilde over (X)} in which W=Diag([w.sub.1, . . . , w.sub.K]) and w.sub.k:=I.sub.qq.Math.V.sub.k and {tilde over (X)}=[vec(X.sub.1), . . . , vec(X.sub.K)].sup.T.sup.KRq1.

[0205] For computing the vector function f.sup.R, the computation condition in (10) needs to be modified, consequently. The inventors bring this condition in the form of the following proposition.

[0206] Proposition 9: Let f.sup.(i) be the i-th output of the function for a certain value of input x.sub.1, x.sub.2, . . . , x.sub.k from [MR] possible values of the function f.sup.(r)s and also, s.sub.i.sup.R represents the corresponding R constellation points. Then, the computation is valid if and only if when we have the following

[00082]$\mathrm{if}{f}_i^r{f}_j^r.Math.{\left[s_i\right]}_r{\left[s_j\right]}_r,$

for all r[R].

[0207] The inventors suggest a similar relaxation to (11) for the mentioned condition in Proposition 9 which it would lead to the following feasibility problem

[00083]$\begin{array}{cc}{}_{M-\mathrm{feas}}=\mathrm{find}& V,U\end{array}$$\begin{array}{cc}s.t.& {.Math.{\left[s_i\right]}_r-{\left[s_j\right]}_r.Math.}^2{.Math.f_i^{\left(r\right)}-f_j^{\left(r\right)}.Math.}^2,\end{array}$$\left(i,j\right)\left[M\right]\left[M\right],\mathrm{and},r\left[R\right]$

[0208] For the reliable communication in the case of MIMO, the problem of computing with minimum power can be extended as follows

[00084]$\begin{array}{cc}\stackrel{}{V},\hat{U}& =\arg \underset{V,U}{\min }{.Math.V.Math.}_F^2\end{array}$$\begin{array}{cc}s.t.& .Math.e_r^{}U\left({\tilde{A}}_{\mathrm{.Math.}}-{\tilde{A}}_J\right)W\tilde{X}.Math.{}_0{}_z^2{.Math.f_i^{\left(r\right)}-f_j^{\left(r\right)}.Math.}^2,\end{array}$$U^{H}U=N_r{I}_R$

for r[R] and e.sub.r.sup.R is the canonical vector whose r-th element is 1 and zero elsewhere. Here, the constraint on U comes from the orthogonality of function f.sup.(r)s from each other.

Minimizing the Maximum Error Using MIMO

[0209] Using multiple antennas provide allows computing R different functions at the same time. Before introducing the problem of minimizing the maximum error, the inventors need to redefine the error for this new setup. Hence, let

[00085]$P_{i,j}^{\left(r\right)}$

be probability of the error of computing

[00086]$f_j^{\left(r\right)}$

instead of

[00087]$f_i^{\left(r\right)},$

then, the computation error can be defined as

[00088]$E_{i,j}^{\left(r\right)}:=P_{i,j}^{\left(r\right)}.Math.f_i^{\left(r\right)}-f_j^{\left(r\right)}.Math.,$

consequently. Since the decision regions of the function f.sup.(r.sup.1.sup.)(x.sub.1, . . . , x.sub.2) and function f.sup.(r.sup.2.sup.)(x.sub.1, . . . , x.sub.2) are different, there can not be any error

[00089]$f_i^{\left(r_1\right)}\mathrm{and}{f}_i^{\left(r_2\right)}$

where r.sub.1, r.sub.2[R] for two different cases of r.sub.1 and r.sub.2. Finally, the optimization problem reads to

[00090]$\begin{array}{cc}{\stackrel{}{v}}_1,.Math.,{\stackrel{}{v}}_K,\mathrm{.Math.}\underset{v_1,.Math.,v_K,U}{=\mathrm{argmin}}\underset{i,j,r}{\max }& P_{i,j}^{\left(r\right)}.Math.f_i^{\left(r\right)}-f_j^{\left(r\right)}.Math.\end{array}$$\begin{array}{cc}s.t.& {.Math.v_k.Math.}_2^2{P}_k,\end{array}$$U^{H}U=N_r{I}_R,$

[0210] The considered problem can be approximated using similar arguments as prvided in section about noise, and it can finally give

[00091]$\begin{array}{cc}{\stackrel{}{v}}_1,.Math.,{\stackrel{}{v}}_K,\mathrm{.Math.}\underset{v_1,.Math.,v_K,U}{=\mathrm{argmax}}\underset{i,j,r}{\min }& \underset{k}{.Math.}\frac{v_k^T{}_{i,j}^{\left(r\right)}{v}_k}{4{}_z}-{}_{i,j}^{\left(r\right)}\end{array}$$\begin{array}{cc}s.t.& {.Math.v_k.Math.}_2^2{P}_k,\end{array}$$U^{H}U=N_r{I}_R,$

where

[00092]${}_{i,j}^{\left(r\right)}=\log \left(\frac{.Math.f_i^{\left(r\right)}-f_j^{\left(r\right)}.Math.}{2}\right),$

P.sub.k denotes allocated power budget for node k and

[00093]${}_{i,j}^{\left(r\right)}={}_{i,j}^{\left(r\right)H}{}_{i,j}^{\left(r\right)}$

in which

[00094]${}_{i,j}^{\left(r\right)}=e_r^T{U}^H\left({\tilde{A}}_i-{\tilde{A}}_j\right)W\tilde{X}.$

Minimizing the Average Error Using MIMO

[0211] Based on what has been mentioned in the previous subsection, the inventors need to revise the problem of minimizing the average error coming from detection. More precisely, for probability of the error of computing

[00095]$f_j^{\left(r\right)}$

instead of

[00096]$f_i^{\left(r\right)},$

one can solve the following optimization problem

[00097]$\begin{array}{cc}\stackrel{}{V},\mathrm{.Math.}& =\underset{V,U}{\mathrm{argmin}}\underset{r=1}{\overset{R}{.Math.}}\underset{i}{\overset{M}{.Math.}}{}_{i,r}\underset{j=1}{\overset{M}{.Math.}}{P}_{i,j}^{\left(r\right)}{.Math.f_i^{\left(r\right)}-f_j^{\left(r\right)}.Math.}^2\end{array}$$\begin{array}{cc}s.t.& {.Math.v_k.Math.}_2^2{P}_k,\end{array}{U}^{H}U=N_r{I}_R,$

where .sub.i,r is the probability of transmitting signal to compute

[00098]$f_i^{\left(r\right)}.$

Similarly, the cost function can be replaced by Chernoff upper bound which would lead to the following optimization

[00099]$\begin{array}{cc}\stackrel{}{V},\mathrm{.Math.}& =\underset{V,U}{\mathrm{argmin}}\underset{r=1}{\overset{R}{.Math.}}\underset{i}{\overset{M}{.Math.}}{}_{i,r}\underset{j=1}{\overset{M}{.Math.}}\exp \left(-\frac{.Math.V,{}_{i,j}^{\left(r\right)}.Math.}{4{}_z}\right){\stackrel{}{}}_{i,j}^{\left(r\right)}\end{array}$$\begin{array}{cc}s.t.& .Math.V,I.Math.P,V0,U^{H}U=N_r{I}_R,\end{array}$

win which

[00100]${\stackrel{~}{}}_{i,j}^{\left(r\right)}={.Math.f_i^{\left(r\right)}-f_j^{\left(r\right)}.Math.}^2.$

The mentioned optimization can be solved by suggested solution in the previous section.

Massive MIMO

[0212] For a large enough number of receiver and transmitter antennas N.sub.t, N.sub.r>>1, the interference within communication cells can be substantially reduced. With a very large antenna array, the effect of fast fading can be diminished. Accordingly, random characteristics of the channel start to look deterministic. Moreover, when the number of receiver antennas grows large, the stochastic channel vectors between the nodes and the CP become pair-wisely orthogonal. Here, the inventors consider a massive MIMO scenario for the case of computation and study its effects on the problem setup.

[0213] We can model independent fast fading, geometric attenuation, and shadow fading using the channel matrix G.sub.k where the coefficient g.sub.n.sub.1.sub.,n.sub.2.sub.,k can be written as

[00101]$g_{n_1,n_2,k}=h_{n_1,n_2,k}\sqrt{{}_{n_2,k}}$

for n.sub.1=1, . . . , N.sub.r where h.sub.n.sub.1.sub.,n.sub.2.sub.,k is the fast fading coefficient from the n.sub.2-th antenna of User k to the n.sub.1-th antenna of the CP. {square root over (.sub.n.sub.2.sub.,k )}denotes the geometric attenuation and shadow fading which is independent over parameter . This in-dependency is .sub.n.sub.2.sub.,k the distances between the users and the CP are always much larger than the distance between the antennas. In addition, the value of .sub.n.sub.2.sub.,k changes very slowly over time. Then, we have

[00102]$H_k=G_k\sqrt{J_k}$

where G.sub.k.sup.N.sup.r.sup.N.sup.t denotes the fast fading coefficients between the k-th user and the CP. Also, J is a N.sub.tN.sub.t diagonal matrix in which [J.sub.k].sub.n.sub.2.sub.,n.sub.2=.sub.n.sub.2.sub.,k. In the case of massive MIMO, one has

[00103]$H_k^H{H}_k=\sqrt{J_k}{G}_k^H{G}_k\sqrt{J_k}{J}_k,N_r{N}_t$

[0214] Also, for the interference between two different channel k and k, one has

[00104]$H_{k^{}}^H{H}_{k}0$

[0215] Using the resultant features, we obtain the following simplification for the aforementioned MIMO scenarios.

[0216] Lemma 2: For the MIMO scenario in (73), if L be equal to N.sub.r and N.sub.r>>1 the computation condition in (78) can be simplified to

[00105]${.Math.s_i-s_j.Math.}_2^2={.Math.}_{k=1}^K{.Math.\left({\tilde{A}}_{k,i}-{\tilde{A}}_{k,i}\right){}_k{X}_k{v}_k.Math.}_2^2,$

for i, j[M.sup.L][M.sup.L], where .sub.k:=diag(I.sub.qq.Math.H.sub.k) and .sub.k:=diag(x.sub.k.Math.I.sub.n.sub.t.sub.N.sub.t) where .sub.k,i.sup.MN.sup.r.sup.N.sup.r.sup.q denotes i-th rows of k-th column block of matrix . Here, we supposed UU.sup.H=N.sub.rI.sub.N.sub.r which is acceptable considering the fact that L=N.sub.r.

[0217] One can simplified the optimization problem in (50), and it can be reformulated as follows

[00106]$\begin{array}{c},...,=\arg \underset{v_1,...,v_k{.Math.}_{k=1}^K}{\min }{.Math.v_k.Math.}_2^2\\ s.t.\underset{k=1}{\overset{K}{.Math.}}{.Math.\left(-\right){}_k{X}_k{v}_k.Math.}_2^2{}_0{}_z^2{.Math.f_i-f_j.Math.}_2^2\end{array}$

[0218] The other optimization problem can be derived in similar manner.

Broadband Digital Over-the-Air Computation via OFDM

[0219] The inventors use OFDM symbols for the case where the CP has access to the-frequency wireless channel on the same time resources. Indeed, each node is able to send its signal over a subset of the frequencies under a certain power constraint. The CP receives aggregated values at the parallel channels and then computes the sum of the values of nodes for each channel, separately. The OFDM modulation is tailored to divide the available bandwidth into orthogonal sub-channels. This requires mapping each quantized data element to one digital symbol to facilitate the ChannelComp method. Particularly, the transmitted baseband OFDM symbol of the k-th nodes in the time slot, can be expressed as

[00107]$t_k={}_{\mathrm{NI}}^{.Math.}\left(L\left\{x_k\left(t\right)\right\}\right),$

where .sub.{dot over (N)}I denotes the NI point inverse Fourier transform and .sub.F is the F-point Fourier transform. Also, L.sup.NIF is the mapping matrix that maps the output of the Fourier transform pre-coder to a set of contiguous sub-carriers, and x.sub.k(t).sup.f contains the f symbols. The investors consider the cyclic prefix duration to be larger than the synchronization offset, in which the offset equals a phase shift of the received symbol. Then, the superposed symbol on the f sub-carrier OFDM symbols at the CP at time slot can be written as

[00108]$\stackrel{.fwdarw.}{y_f}\left(t\right)=\underset{k=1}{\overset{K}{.Math.}}{h}_{k,f}\left(t\right)\stackrel{.fwdarw.}{t_{k,f}}\left(t\right)+\stackrel{.fwdarw.}{z_f}\left(t\right)$

where h.sub.k,f is the channel coefficient between the CP and k-th node, {right arrow over (t.sub.k,f )}is the transmitted symbol from the f-th node, {right arrow over (z.sub.f )}is the symmetric AWGN with zero mean and the variance

[00109]${}_z^2$

on the f-th sub-carrier. The transmitter and the receiver design for edge devices are shown in FIG. 12.

Asynchronous Computation Over the Air

[0220] One of the well-known challenges in the over-the-air problem is to have a strict time synchronization over all the devices. To overcome this issue, one can use the timing advance technique. In particular, one needs to consider the propagation delay of each device regardless of their location, and then change the tabular function based on the constellation diagram of the corresponding transmitted devices in regard of the time.

[0221] More specifically, let {right arrow over (x.sub.k)}(t) represents the modulation vector of k-th user in the time slot t[T] where denotes the set of time slots of interest. For sake of simplicity, suppose that the desired function f can be written as

[00110]$f\left(x\right)={.Math.}_{k=1}^K{g}_k\left(x_k\right)$

where g.sub.k():. Also, consider for user k in which k{1,2, . . . , L}, we have same delay, and the rest of the users are in different locations and have different propagation delays i.e. k{L+1, L+2, . . . , T}. Hence, the desire function can be divided into two functions f.sub.1 and f.sub.2 as follows

[00111]$f\left(x\right)=\underset{k=1}{\overset{L}{.Math.}}{g}_k\left(x_k\right)+\underset{k^{}=L+1}{\overset{K}{.Math.}}{g}_{k^{}}\left(x_{k^{}}\right)=f_1\left(x\right)+f_2\left(x\right)$

[0222] Therefore, the inventors have realized that onemay compute the function f using two tabular functions and in two time slots t.sub.1 and t.sub.2 corresponding to the functions f.sub.1 and f.sub.2, respectively. Consequently, one way that the inventors have realizzed to handle noise and find proper modulation is to solve an optimization problem for each function separately. Although, the discussed cases consist of two delays, extending to the higher number of delays is straightforward.

[0223] For the case of inseparable functions as long as can be the sequence of the functions can be uniquely determined, or there is a set of unique sequences generated by the same input, the desired function can be computed. In fact, in the aforementioned example, to compute functions f.sub.1 and f.sub.2, it is required to have knowledge of the input domain of functions. However, one can consider cases in which function and have the same domain and computing the other one required information of the other one's input. In this regard, the inventors have realized that one may decode the domain of the functions as well.

[0224] Consider we first compute the function f.sub.1 and f.sub.2 with domain .sub.1={x.sub.1, x.sub.2, . . . , x.sub.L} and .sub.2={x.sub.L+1, x.sub.L+2, . . . , x.sub.K}{x.sub.1} at time t.sub.1 and t.sub.2, respectively where t.sub.1<t.sub.2. Then, for computing function f.sub.2, it needs to know the value of the first user x.sub.1 which is transmitted in time t.sub.1. Therefore, the constraint in feasibility check optimization would be changed and investors suggest the following optimization

[00112]$\begin{array}{c}\begin{array}{c}{}_1^{\mathrm{asynch}}=\mathrm{find}x\\ s.t.\mathrm{if}{f}_{1i}{f}_{1j}\mathrm{or}{x}_1^i{x}_1^j.Math.s_i{s}_j\end{array}\\ \left(i,j\right)\left[M\right]\left[M\right]\end{array}$

where

[00113]$x_1^i$

denotes the corresponding values of x.sub.1 to the output of f.sub.1i. Consequently, the inventors have realized that one can relax these conditions as follows

[00114]$\begin{array}{c}\begin{array}{c}{}_2^{\mathrm{asynch}}=\mathrm{find}x\\ s.t.\mathrm{if}{.Math.s_i-s_j.Math.}^2{.Math.f_{1i}-f_{1j}.Math.}^2+{.Math.x_1^i-x_1^j.Math.}^2\end{array}\\ \left(i,j\right)\left[M\right]\left[M\right]\end{array}$