COMMUNICATION TERMINALS AND A METHOD FOR EXCHANGING INFORMATION BETWEEN COMMUNICATION TERMINALS IN A NOISY ENVIRONMENT RELATED APPLICATIONS

This application claims priority from US provisional patent serial number 62/030, 108 filing date July 29 2014 which is incorporated herein by reference.

BACKGROUND

The following documents are referred to in this document:

[1] C. E. Shannon, "The zero-error capacity of a noisy channel," IEEE Trans. Inf. Theory, vol. IT-2, pp. 8-19, Sep 1956.

[2] J. P. M. Schalkwijk and T. Kailath, "A coding scheme for additive noise channels with feedback part I: No bandwidth constraint," IEEE Trans. Inf. Theory, vol. IT-12, pp. 172-182, Apr 1966.

[3] J. P. M. Schalkwijk, "A coding scheme for additive noise channels with feedback part II: Band-limited signals," IEEE Trans. Inf. Theory, vol. IT-12, pp. 183-189, Apr 1966.

[4] M. Horstein, "Sequential transmission using noiseless feedback," IEEE Trans. Info. Theory, vol. IT-9, pp. 136-143, Jul 1963.

[5] O. Shayevitz and M. Feder, "Optimal feedback communication via posterior matching," IEEE Trans. Inf. Theory, vol. 57, no. 3, pp. 1186-1222, Mar 2011.

[6] Y.-H. Kim, A. Lapidoth, and T. Weissman, "On the reliability of Gaussian channels with noisy feedback," in Proc. 41st Allerton Conf. Communication, Control Computing, Sep. 2006, pp. 364-371.

[7] Z. Chance and D. J. Love, "Concatenated coding for the AWGN channel with noisy feedback," IEEE Trans. Inf. Theory, vol. 57, pp. 6633-6649, Oct. 2011.

[8] A. Sato and H. Yamamoto, "Error exponents of discrete memoryless channels and awgn channels with noisy feedback," in ISITA, 2010, pp. 452-457.

[9] M. V. Burnashev and H. Yamamoto, "On reliability function of BSC with noisy feedback," Problems of Information Transmission, vol. 46, pp. 2-23, 2010.

[10] M. V. Burnashev and H. Yamamoto, "Noisy feedback improves the gaussian channel reliability function," in ISIT, 2014, pp. 2554-2558. [11] M. Tomlinson, "New automatic equalizer employing modulo arithmetic," Electronics Letters, vol. 7, no. 5, pp. 138-139, 1971.

[12] H. Harashima and H. Miyakawa, "Matched-transmission technique for channels with intersymbol interference," IEEE Transactions on Communications, vol. 20, no. 4, pp.

774-780, 1972.

[13] Y. Kochman and R. Zamir, "Joint Wyner-Ziv/Dirty-Paper Coding by

Analog Modulo-Lattice Modulation," IEEE Trans. Inf. Theory, vol. 55,

pp. 4878-4889, 2009.

Feedback cannot improve the capacity of point-to-point memory less channels [1].

Nevertheless, noiseless feedback can significantly simplify the transmission schemes and improve the error probability performance, see e.g. [2]-[5]. These elegant schemes fail however in the presence of arbitrarily small feedback noise, rendering them grossly impractical. This fact has been initially observed in [3] for the Additive White Gaussian Noise (AWGN) channel, and further strengthened in [6]. A handful of works have tackled the problem of noisy feedback as means for improving error performance, see e.g. [7]-[10]. However, these works attain their superior error performance at the cost of a significant increase in complexity w.r.t. their noiseless feedback counterparts. There appears to be no simple scheme (in the spirit of [3]-[5]) that is robust to feedback noise known hitherto. SUMMARY

There are provided systems, methods and non-transitory computer readable media for decoding one or more component codes, as illustrated in the claims.

According to an embodiment of the invention there may be provided a method that may include receiving, by a second terminal, a first received signal; wherein the first received signal represents a first transmitted signal that was transmitted from a first terminal and propagated over a noisy feedforward channel; wherein the first transmitted signal represents a portion of a message; calculating, by the second terminal, a first estimate of the portion of the message; calculating, by the second terminal, a representation of the first estimate; wherein the calculating may include applying a second modulo function; transmitting, by the second terminal, over a feedback channel, the representation of the first estimate; repeating, for each iteration out of multiple iterations, the steps of: receiving, by a second terminal, a current received signal; wherein the current received signal represents an estimated error; wherein the estimated error was calculated by the first terminal in response to an outcome of a pervious iteration and may include applying a first modulo function; calculating, by the second terminal, and in response to the current received signal, a current estimate of the message; calculating, by the second terminal, a representation of the current estimate; wherein the calculating may include applying the second modulo function; and transmitting, by the second terminal and over the feedback channel, a representation of the current estimate; and estimating the portion of the message, by the second terminal, and after a completion of the multiple iterations, wherein the estimating of the message is responsive to at least one outcome of at least one iteration.

According to an embodiment of the invention there may be provided a method that may include receiving, by a second terminal, a first received signal; wherein the first received signal represents a first transmitted signal that was transmitted from a first terminal and propagated over a noisy feedforward channel; wherein the first transmitted signal is a dummy signal;

calculating, by the second terminal, a first estimate of the dummy signal; calculating, by the second terminal, a representation of the first estimate; of the dummy signal wherein the calculating may include applying a second modulo function; transmitting, by the second terminal, over a feedback channel, the representation of the first estimate; repeating, for each iteration out of multiple iterations, the steps of: receiving, by a second terminal, a current received signal; wherein the current received signal represents an estimated error; wherein the estimated error was calculated by the first terminal in response to an outcome of a pervious iteration and in response to a portion of a message and may include applying a first modulo function; calculating, by the second terminal, and in response to the current received signal, a current estimate of the message; calculating, by the second terminal, a representation of the current estimate; wherein the calculating may include applying the second modulo function; and transmitting, by the second terminal and over the feedback channel, a representation of the current estimate; and estimating the portion of the message, by the second terminal, and after a completion of the multiple iterations, wherein the estimating of the message is responsive to at least one outcome of at least one iteration.

According to an embodiment of the invention there may be provided a method that may include transmitting a transmitted signal, by a first terminal and over a noisy feedforward channel; wherein the first transmitted signal represents a portion of a message; receiving, by a second terminal, a first received signal; wherein the first received signal represents the first transmitted signal; calculating, by the second terminal, a first estimate of the portion of the message; calculating, by the second terminal, a representation of the first estimate; wherein the calculating may include applying a second modulo function; transmitting, by the second terminal, over a feedback channel, the representation of the first estimate; repeating, for each iteration out of multiple iterations, the steps of: calculating, by the first terminal, an estimated error in response to an outcome of a previous iteration; wherein the calculating may include applying a first modulo function; receiving, by a second terminal, a current received signal; wherein the current received signal represents the estimated error; calculating, by the second terminal, and in response to the current received signal, a current estimate of the portion of the message; calculating, by the second terminal, a representation of the current estimate; wherein the calculating may include applying the second modulo function; and transmitting, by the second terminal and over the feedback channel, a representation of the current estimate; and estimating the portion of the message, by the second terminal, and after a completion of the multiple iterations, wherein the estimating of the message is responsive to at least one outcome of at least one iteration.

According to an embodiment of the invention there may be provided a method that may include transmitting a transmitted signal, by a first terminal and over a noisy feedforward channel; wherein the first transmitted signal is a dummy signal; receiving, by a second terminal, a first received signal; wherein the first received signal represents the first transmitted signal; calculating, by the second terminal, a first estimate of the dummy signal; calculating, by the second terminal, a representation of the first estimate; wherein the calculating may include applying a second modulo function; transmitting, by the second terminal, over a feedback channel, the representation of the first estimate; repeating, for each iteration out of multiple iterations, the steps of: calculating, by the first terminal, an estimated error in response to an outcome of a previous iteration and in response to a content of a portion of a message; wherein the calculating may include applying a first modulo function; receiving, by a second terminal, a current received signal; wherein the current received signal represents the estimated error;

calculating, by the second terminal, and in response to the current received signal, a current estimate of the portion of the message; calculating, by the second terminal, a representation of the current estimate; wherein the calculating may include applying the second modulo function; and transmitting, by the second terminal and over the feedback channel, a representation of the current estimate; and estimating the portion of the message, by the second terminal, and after a completion of the multiple iterations, wherein the estimating of the message is responsive to at least one outcome of at least one iteration.

According to an embodiment of the invention there may be provided a method that may include transmitting, by a first terminal and over a noisy feedforward channel, a first transmitted signal, thereby allowing the second terminal to receive a first received signal; wherein the first transmitted signal represents a portion of a message; receiving, by the first terminal, a second received signal, wherein the second received signal results from a propagation, over a noisy feedback channel, of a representation of a first estimate of at the least portion of the message; wherein the representation of the first estimate is calculated by the second terminal, wherein the calculation of the representation of the first estimate may include applying a second modulo function; repeating, for each iteration out of multiple iterations, the steps of: calculating, by the first terminal, an estimated error, wherein the calculating is responsive to an outcome of a pervious iteration and may include applying a first modulo function; transmitting the estimate error to the second terminal over the noisy feedforward channel; and receiving, by the first terminal and over the feedback channel, a representation of the current estimate.

According to an embodiment of the invention there may be provided a non-transitory computer readable medium that stores instructions that once executed by a second terminal, causes the second terminal to perform the steps of: receiving, by a second terminal, a first received signal; wherein the first received signal represents a first transmitted signal that was transmitted from a first terminal and propagated over a noisy feedforward channel; wherein the first transmitted signal represents a portion of a message; calculating, by the second terminal, a first estimate of the portion of the message; calculating, by the second terminal, a representation of the first estimate; wherein the calculating may include applying a second modulo function; transmitting, by the second terminal, over a feedback channel, the representation of the first estimate; repeating, for each iteration out of multiple iterations, the steps of: receiving, by a second terminal, a current received signal; wherein the current received signal represents an estimated error; wherein the estimated error was calculated by the first terminal in response to an outcome of a pervious iteration and may include applying a first modulo function; calculating, by the second terminal, and in response to the current received signal, a current estimate of the message; calculating, by the second terminal, a representation of the current estimate; wherein the calculating may include applying the second modulo function; and transmitting, by the second terminal and over the feedback channel, a representation of the current estimate; and estimating the portion of the message, by the second terminal, and after a completion of the multiple iterations, wherein the estimating of the message is responsive to at least one outcome of at least one iteration.

According to an embodiment of the invention there may be provided a non-transitory computer readable medium that stores instructions that once executed by a second terminal, causes the second terminal to perform the steps of: receiving, by a second terminal, a first received signal; wherein the first received signal represents a first transmitted signal that was transmitted from a first terminal and propagated over a noisy feedforward channel; wherein the first transmitted signal is a dummy signal; calculating, by the second terminal, a first estimate of the dummy signal; calculating, by the second terminal, a representation of the first estimate; of the dummy signal wherein the calculating may include applying a second modulo function; transmitting, by the second terminal, over a feedback channel, the representation of the first estimate; repeating, for each iteration out of multiple iterations, the steps of: receiving, by a second terminal, a current received signal; wherein the current received signal represents an estimated error; wherein the estimated error was calculated by the first terminal in response to an outcome of a pervious iteration and in response to a portion of a message and may include applying a first modulo function; calculating, by the second terminal, and in response to the current received signal, a current estimate of the message; calculating, by the second terminal, a representation of the current estimate; wherein the calculating may include applying the second modulo function; and transmitting, by the second terminal and over the feedback channel, a representation of the current estimate; and estimating the portion of the message, by the second terminal, and after a completion of the multiple iterations, wherein the estimating of the message is responsive to at least one outcome of at least one iteration.

According to an embodiment of the invention there may be provided a non-transitory computer readable medium that stores instructions that once executed by a first terminal and a second terminal, causes the first terminal and the second terminal to perform the steps of:

transmitting a transmitted signal, by a first terminal and over a noisy feedforward channel; wherein the first transmitted signal represents a portion of a message; receiving, by a second terminal, a first received signal; wherein the first received signal represents the first transmitted signal; calculating, by the second terminal, a first estimate of the portion of the message;

calculating, by the second terminal, a representation of the first estimate; wherein the calculating may include applying a second modulo function; transmitting, by the second terminal, over a feedback channel, the representation of the first estimate; repeating, for each iteration out of multiple iterations, the steps of: calculating, by the first terminal, an estimated error in response to an outcome of a previous iteration; wherein the calculating may include applying a first modulo function; receiving, by a second terminal, a current received signal; wherein the current received signal represents the estimated error; calculating, by the second terminal, and in response to the current received signal, a current estimate of the portion of the message;

calculating, by the second terminal, a representation of the current estimate; wherein the calculating may include applying the second modulo function; and transmitting, by the second terminal and over the feedback channel, a representation of the current estimate; and estimating the portion of the message, by the second terminal, and after a completion of the multiple iterations, wherein the estimating of the message is responsive to at least one outcome of at least one iteration.

According to an embodiment of the invention there may be provided a non-transitory computer readable medium that stores instructions that once executed by a first terminal and a second terminal, causes the first terminal and the second terminal to perform the steps of:

transmitting a transmitted signal, by a first terminal and over a noisy feedforward channel; wherein the first transmitted signal is a dummy signal; receiving, by a second terminal, a first received signal; wherein the first received signal represents the first transmitted signal;

calculating, by the second terminal, a first estimate of the dummy signal; calculating, by the second terminal, a representation of the first estimate; wherein the calculating may include applying a second modulo function; transmitting, by the second terminal, over a feedback channel, the representation of the first estimate; repeating, for each iteration out of multiple iterations, the steps of: calculating, by the first terminal, an estimated error in response to an outcome of a previous iteration and in response to a content of a portion of a message; wherein the calculating may include applying a first modulo function; receiving, by a second terminal, a current received signal; wherein the current received signal represents the estimated error; calculating, by the second terminal, and in response to the current received signal, a current estimate of the portion of the message; calculating, by the second terminal, a representation of the current estimate; wherein the calculating may include applying the second modulo function; and transmitting, by the second terminal and over the feedback channel, a representation of the current estimate; and estimating the portion of the message, by the second terminal, and after a completion of the multiple iterations, wherein the estimating of the message is responsive to at least one outcome of at least one iteration.

According to an embodiment of the invention there may be provided a non-transitory computer readable medium that stores instructions that once executed by a first terminal, causes the first terminal to perform the steps of: transmitting, by a first terminal and over a noisy feedforward channel, a first transmitted signal, thereby allowing the second terminal to receive a first received signal; wherein the first transmitted signal represents a portion of a message; receiving, by the first terminal, a second received signal, wherein the second received signal results from a propagation, over a noisy feedback channel, of a representation of a first estimate of at the least portion of the message; wherein the representation of the first estimate is calculated by the second terminal, wherein the calculation of the representation of the first estimate may include applying a second modulo function; repeating, for each iteration out of multiple iterations, the steps of: calculating, by the first terminal, an estimated error, wherein the calculating is responsive to an outcome of a pervious iteration and may include applying a first modulo function; transmitting the estimate error to the second terminal over the noisy feedforward channel; and receiving, by the first terminal and over the feedback channel, a representation of the current estimate.

According to an embodiment of the invention there may be provided a second terminal that may include a processor , a receiver and a transmitter, wherein the receiver may be configured to receive a first received signal; wherein the first received signal represents a first transmitted signal that was transmitted from a first terminal and propagated over a noisy feedforward channel; wherein the first transmitted signal represents a portion of a message; wherein the processor may be configured to calculate a first estimate of the portion of the message; calculate a representation of the first estimate; wherein the calculating may include applying a second modulo function; wherein the transmitter may be configured to transmit over a feedback channel, the representation of the first estimate; wherein the second terminal may be configured to repeat, for each iteration out of multiple iterations, the steps of: receiving, by the receiver, a current received signal; wherein the current received signal represents an estimated error; wherein the estimated error was calculated by the first terminal in response to an outcome of a pervious iteration and may include applying a first modulo function; calculating, by the processor, and in response to the current received signal, a current estimate of the message; calculating, by the processor, a representation of the current estimate; wherein the calculating may include applying the second modulo function; and transmitting, by the transmitter and over the feedback channel, a representation of the current estimate; wherein the processor is further configured to estimate the portion of the message after a completion of the multiple iterations, wherein the estimating of the message is responsive to at least one outcome of at least one iteration.

According to an embodiment of the invention there may be provided a second terminal that may include a processor , a receiver and a transmitter, wherein the receiver may be configured to receive a first received signal; wherein the first received signal represents a first transmitted signal that was transmitted from a first terminal and propagated over a noisy feedforward channel; wherein the first transmitted signal is a dummy signal; wherein the processor may be configured to calculate a first estimate of the dummy signal, and calculate a representation of the first estimate; of the dummy signal wherein the calculating may include applying a second modulo function; wherein the transmitter may be configured to transmit, over a feedback channel, the representation of the first estimate; wherein the second terminal may be configured to repeat, for each iteration out of multiple iterations, the steps of: receiving, by a second terminal, a current received signal; wherein the current received signal represents an estimated error; wherein the estimated error was calculated by the first terminal in response to an outcome of a pervious iteration and in response to a portion of a message and may include applying a first modulo function; calculating, by the second terminal, and in response to the current received signal, a current estimate of the message; calculating, by the second terminal, a representation of the current estimate; wherein the calculating may include applying the second modulo function; and transmitting, by the second terminal and over the feedback channel, a representation of the current estimate; and wherein the processor may be configured to estimate the portion of the message after a completion of the multiple iterations, wherein the estimating of the message is responsive to at least one outcome of at least one iteration. According to an embodiment of the invention there may be provided a system may include a first terminal and a second terminal, wherein the first terminal may include a first processor , a first receiver and a first transmitter; wherein the second terminal may include a second processor , a second receiver and a second transmitter; wherein the first transmitter may be configured to transmit a transmitted signal over a noisy feedforward channel; wherein the first transmitted signal represents a portion of a message; wherein the second receiver may be configured to receive a first received signal; wherein the first received signal represents the first transmitted signal; wherein the second processor may be configured to calculate a first estimate of the portion of the message and to calculate a representation of the first estimate; wherein the calculating may include applying a second modulo function; wherein the second transmitter may be configured to transmit, over a feedback channel, the representation of the first estimate; wherein the first and second terminals are configured to repeat, for each iteration out of multiple iterations, the steps of: calculating, by the first processor, an estimated error in response to an outcome of a previous iteration; wherein the calculating may include applying a first modulo function; receiving, by a second receiver, a current received signal; wherein the current received signal represents the estimated error; calculating, by the second processor, and in response to the current received signal, a current estimate of the portion of the message; calculating, by the second processor, a representation of the current estimate; wherein the calculating may include applying the second modulo function; and transmitting, by the second transmitter and over the feedback channel, a representation of the current estimate; wherein the second processor may be configured to estimate the portion of the message, after a completion of the multiple iterations, wherein the estimating of the message is responsive to at least one outcome of at least one iteration. Blocks 21-24 of figure 2 are non- limiting examples of operations executed by a first (hardware) processor of a first terminal. Blocks 31-35 of figure 2 are non- limiting examples of operations executed by a (second) hardware processor of a second terminal. The first terminal is coupled to the feedforward channel via a (first) transmitter and to the feedback channel via a (first) receiver. The second terminal is coupled to the feedforward channel via a (second) receiver and to the feedback channel via a (second) transmitter.

According to an embodiment of the invention there may be provided a system may include a first terminal and a second terminal, wherein the first terminal may include a first processor , a first receiver and a first transmitter; wherein the second terminal may include a second processor , a second receiver and a second transmitter; wherein the first transmitter may be configured to transmit a transmitted signal over a noisy feedforward channel; wherein the first transmitted signal is a dummy signal; wherein the second receiver may be configured to receive a first received signal; wherein the first received signal represents the first transmitted signal; wherein the second processor may be configured to calculate a first estimate of the dummy signal and to calculate a representation of the first estimate; wherein the calculating may include applying a second modulo function; wherein the second transmitter may be configured to transmit, over a feedback channel, the representation of the first estimate; wherein the first and second terminals are configured to repeat, for each iteration out of multiple iterations, the steps of: calculating, by the first processor, an estimated error in response to an outcome of a previous iteration and in response to a content of a portion of a message; wherein the calculating may include applying a first modulo function; receiving, by a second receiver, a current received signal; wherein the current received signal represents the estimated error; calculating, by the second processor, and in response to the current received signal, a current estimate of the portion of the message; calculating, by the second processor, a representation of the current estimate; wherein the calculating may include applying the second modulo function; and transmitting, by the second transmitter and over the feedback channel, a representation of the current estimate; wherein the second processor may be configured to estimate the portion of the message, after a completion of the multiple iterations, wherein the estimating of the message is responsive to at least one outcome of at least one iteration.

According to an embodiment of the invention there may be provided a first terminal that may include a first processor, a first receiver and a first transmitter; wherein the transmitter may be configured to transmit over a noisy feedforward channel, a first transmitted signal, thereby allowing the second terminal to receive a first received signal; wherein the first transmitted signal represents a portion of a message; wherein the receiver may be configured to receive a second received signal, wherein the second received signal results from a propagation, over a noisy feedback channel, of a representation of a first estimate of at the least portion of the message; wherein the representation of the first estimate is calculated by the second terminal, wherein the calculation of the representation of the first estimate may include applying a second modulo function; wherein the first terminal us configured to repeat, for each iteration out of multiple iterations, the steps of: calculating, by the first processor, an estimated error, wherein the calculating is responsive to an outcome of a pervious iteration and may include applying a first modulo function; transmitting by the transmitter the estimate error to the second terminal over the noisy feedforward channel; and receiving, by the receiver and over the feedback channel, a representation of the current estimate.

BRIEF DESCRIPTION OF THE DRAWINGS

The subject matter regarded as the invention is particularly pointed out and distinctly claimed in the concluding portion of the specification. The invention, however, both as to organization and method of operation, together with objects, features, and advantages thereof, may best be understood by reference to the following detailed description when read with the accompanying drawings in which:

FIG. 1 illustrates prior art first and second terminals;

FIG. 2 illustrates first and second terminals according to an embodiment of the invention; FIG. 3 illustrates a capacity gap in various scenarios that differ from each other by a ratio between the signal to noise ratio (SNR) of the feedback channel and the SNR of the feedforward channel, according to an embodiment of the invention;

FIG. 4 illustrates a capacity gap in various scenarios that differ from each other by a ratio between the signal to noise ratio (SNR) of the feedback channel and the SNR of the feedforward channel, according to an embodiment of the invention;

FIG. 5 illustrates first and second terminals according to an embodiment of the invention; FIG. 6 illustrates a method according to an embodiment of the invention;

FIG. 7 illustrates a method according to an embodiment of the invention;

FIG. 8 illustrates a method according to an embodiment of the invention;

FIG. 9 illustrates a method according to an embodiment of the invention; and

FIG. 10 illustrates a method according to an embodiment of the invention.

DETAILED DESCRIPTION OF THE DRAWINGS

In the following detailed description, numerous specific details are set forth in order to provide a thorough understanding of the invention. However, it will be understood by those skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known methods, procedures, and components have not been described in detail so as not to obscure the present invention.

The subject matter regarded as the invention is particularly pointed out and distinctly claimed in the concluding portion of the specification. The invention, however, both as to organization and method of operation, together with objects, features, and advantages thereof, may best be understood by reference to the following detailed description when read with the accompanying drawings.

It will be appreciated that for simplicity and clarity of illustration, elements shown in the figures have not necessarily been drawn to scale. For example, the dimensions of some of the elements may be exaggerated relative to other elements for clarity. Further, where considered appropriate, reference numerals may be repeated among the figures to indicate corresponding or analogous elements.

Because the illustrated embodiments of the present invention may for the most part, be implemented using electronic components and circuits known to those skilled in the art, details will not be explained in any greater extent than that considered necessary as illustrated above, for the understanding and appreciation of the underlying concepts of the present invention and in order not to obfuscate or distract from the teachings of the present invention.

Any reference in the specification to a method should be applied mutatis mutandis to a system capable of executing the method and should be applied mutatis mutandis to a non- transitory computer readable medium that stores instructions that once executed by a computer result in the execution of the method.

Any reference in the specification to a system should be applied mutatis mutandis to a method that may be executed by the system and should be applied mutatis mutandis to a non- transitory computer readable medium that stores instructions that may be executed by the system.

Any reference in the specification to a non-transitory computer readable medium should be applied mutatis mutandis to a system capable of executing the instructions stored in the non- transitory computer readable medium and should be applied mutatis mutandis to method that may be executed by a computer that reads the instructions stored in the non-transitory computer readable medium. According to various embodiments of the invention there are provided systems and method for communicating between terminals. Appendix A and figures 1, 2, 3 and 4 illustrate two terminals according to an embodiment of the invention, a method for transmitting information according to various embodiments of the invention and a mathematical analysis of the suggested methods.

Figure 1 Illustrates first and second terminals 11 and that are coupled via a noisy feedforward channel 13 and a noisy feedback channel 14.

Figure 1 illustrates prior art pair of terminals Terminal A l l and Terminal B 12 and their environment.

The feedforward channel 13 and feedback channel 14 connecting Terminal A to Terminal B and vice versa respectively, are AWGN channels (represented by adders in each one of the channels).

Figure 2 illustrates first and second terminals 20 and 30 according to an embodiment of the invention.

Especially, figure 2 illustrates signals exchanged during various iterations.

In figure 2 the feedforward channel is denoted 13 and the feedback channel is denoted 14. In figure 2 the first terminal 20 may receive a signal Θ, scale (21) it by -γ _η and sum (22) the scaled signal, dither -V _n and a second receive signal or a representation of the current estimate to provide a sum that undergoes a modulo (24) operation with a fixed interval and is further scaled (25) by a to provide the first transmitted signal X _n .

It is noted that at least some of the operations (such as the double scaling and the addition of dither is optional).

For simplicity of explanation figure 2 only shows some of the signals. Thus, some of the signals transmitted during the iterations are not shown.

In figure 2 the second terminal 30 may receive a received signal Y _n , scale (31) it by -β _η and sum (22) the received signal with a previous (delayed by delay unit 33) outputted signal (Θ _η )· The sum is scaled by γ _η to provide a scaled signal that is added (35) to dither V _n and to provide a second sum that undergoes a second modulo operation (36) to provide the

representation of the current estimate X _n . Graphs 40 and 50 of figures 3 and 4 illustrate capacity gaps in various scenarios that differ from each other by a ratio between the signal to noise ratio (SNR) of the feedback channel and the SNR of the feedforward channel, according to an embodiment of the invention.

Physical-layer security

Our invention admits an inherent physical layer security feature that makes it stochastically impossible for a non- intended user to listen and decode the communicated data. This can be thought of as an interactive encryption process at the analog signal level. Loosely speaking, it is based on the observation that our communication protocol constitutes a stochastic dynamical system that can be stabilized (for the duration of the interaction) by the intended users; anyone else who attempts to accurately track the trajectory of this system (which corresponds to the transmitted data) is doomed to fail since his emulation of the system will become unstable and quickly diverge from the correct trajectory (much like the "butterfly effect" in chaotic systems).

Suppose an eavesdropper/wiretapper (denoted here by Terminal E) listens to signals transmitted to Terminal A and Terminal B, through two noisy channels. Namely

where are noises that are different from (but otherwise arbitrarily correlated to) the noises experienced by Terminal A and Terminal B

The closed loop nature of our transmission scheme implies that in order to decode the message reliably, one must have access to a very clean (virtually noiseless) version of the input signal to Terminal B (i.e., Y _n ). More precisely, even if Terminal E is able to reconstruct a noisy version of Y _n , this estimation noise (however small) will accumulate in the course of the interactive process. This will result in very large error in the estimation of the message point at Terminal E, which in turn can be shown to imply that most of the message bits (the least significant bits of the message point) reconstructed at Terminal E will be virtually statistically independent of the original transmitted bits. Since the most significant bits can still be decoded by Terminal E, they can be set so to dummy bits, i.e. so that they carry no information (random, pseudo random etc.). The number of dummy bits should be determined by the quality of eavesdropper's channels observed at Terminal E. This induces a natural trade-off between communication rate and security. Namely, the better the quality of the eavesdropper's channels, the lower the possible secure communication rate.

There are a couple of different ways (other than dummy bits insertion) of achieving the same goal, as described in the sequel.

The following points are in order:

1. In non-interactive communication (which is the common practice) Terminal E can decode the transmitted message as long as is statistically weaker than Z _n (i.e. with lower or equal variance). In stark contrast, to achieve the same in our interactive system, Terminal E has to be able to learn then sequence Y _n itself, precisely, which is a much harder constraint and typically infeasible.

2. Following the above, it should be emphasized that we can achieve perfect security even when the eavesdropper's channels are much better than the communication channels.

3. Common practice in data security is to employ encryption algorithms that typically work on the digital signal. These algorithms are almost always based on the hardness of some mathematical problem (e.g. prime factorization). Thus, if one has sufficient computational resources, or if one is able to come up with a more efficient algorithm, these encryptions can be broken. In contrast, our system is stochastically secure, in the sense that the data gathered by the eavesdropper is statistically insufficient for reliable decoding, regardless of computational power or algorithmic innovation.

4. It is important to note that in the original invention we had to restrict ourselves to asymmetrical setting, where the feedback channel has a large amount of excess SNR over the feedforward channel. This restriction was imposed in order to make the system more efficient (in terms of power, rate, delay, complexity) relative to common practice, which was the original motivation of the invention. In cases where the goal is secure transmission (and not efficient transmission) our system can operate in any SNR regime, symmetric or asymmetric. The quality of the feedback channel will in general determine the cost in rate required to achieve security. It should be emphasized that in the original asymmetrical setting, there is no such loss in rate (apart from the dummy bits). Dummy bits assignment The number of dummy bits is essentially determined by the variance σ ² of the MMSE estimator of Y _n from the pair which can be computed. The larger σ ² , the smaller the number of dummy bits required, and the smaller the rate penalty incurred. When decoding, Terminal E will be able to reconstruct the message point within some large variance that does not decay exponentially (just like in noisy feedback systems that do not use our modulo method). The larger σ ² the larger this variance, hence the less resolution obtainable by Terminal E. When increasing the number of iterations N, Terminal B can decode more bits (as its reconstruction resolution decays exponentially), but Terminal E gets "stuck", hence the rate penalty diminishes. Of course, N cannot grow very large due to modulo errors. But for secure transmission, we would like to set it to be as large as possible without jeopardizing reliability at Terminal B. Once the number of dummy bits is determined, they are randomly selected and constitute the MSB's of the message point. Note that the labeling of the constellation should be chosen such that large deviations would correspond to MSB's.

According to an embodiment of the invention the transmission scheme include reduce the power of the constellation such that in the first transmissions the first terminal transmits dummy bits such as information that is below the noise level of the noisy feedthrough channel. The power reduction again corresponds to the estimation variance σ ² . In this case, Terminal A effectively transmits just modulo-filtered noise during the first few iterations, and only then starts to incorporate the actual message. In these first few iterations, Terminal A and B remain synchronized, yet Terminal E becomes "decorrelated" from them and can no longer reliably follow the conversation. These first few iterations can be thought of as our interactive analogue of a cryptographic key exchange. As before, the rate penalty incurred for secrecy is inversely related to both σ ² (which determines the number of " key exchange' ' rounds) and the number of iterations N. Note that other variations on this method are possible, playing with the transmission power.

According to another embodiment of the invention the first terminal applies a masking function (known to the first and second terminals) on the message in the and the second terminal applies an known unmasking function on the decoded information.

A non- limiting example of a masking function is a sum with a known message. A message that is generated in a known manner. W' is the known message and W is the data. W ¹ is known to both Terminal A and B (say pseudo randomly generated) and W is the actual message Map both to (say) PAM constellation points Θ', Θ of suitable rates, and use our interactive communication system to transmit Θ' + Θ (or some other suitable linear combination). The number of bits for W ^´ and the associated power allocated to Θ' are determined by the

aforementioned estimation variance σ ² at Terminal A. Terminal E will be able to decode only Θ' that does not contain any information, while Terminal B will be able to remove Θ' and reliably decode Θ as desired. Again, increasing the number of iterations N (up to a limit dictated by the modulo-aliasing errors) will increase the part played by the actual message W, and will render the rate loss smaller. This method may be favored over Method 1 when there is system constraint requiring transmission at a constant power at all times.

Figures 5 and 6 illustrate a method that is executed by both the first terminal and the second terminal. Figures 7 and 8 illustrate the steps executed by the second terminal. Figure 9 and 10 illustrate the steps executed by the first terminal.

Figures 5, 7 and 9 refer to a scenario in which the first transmitted signal represents a portion of the message. Figures 6, 8 and 10 refer to a scenario in which the first transmitted signal is a dummy signal.

Figure 5 illustrates method 300 according to an embodiment of the invention.

Method 300 includes an initialization sequence of steps 310, 320, 330, 340 and 350. This initialization sequence of steps is followed by multiple iterations (predetermined number of iterations, monitored by step 360) of steps 370, 375, 380, 390, 400, and 410. Method 300 ends by step 420.

Step 310 may include transmitting a transmitted signal, by a first terminal and over a noisy feedforward channel; wherein the first transmitted signal represents a portion of a message.

Step 320 may include receiving, by a second terminal, a first received signal; wherein the first received signal represents the first transmitted signal.

Step 330 may include calculating, by the second terminal, a first estimate of the portion of the message.

Step 340 may include calculating, by the second terminal, a representation of the first estimate; wherein the calculating may include applying a second modulo function.

Step 350 may include transmitting, by the second terminal, over a feedback channel, the representation of the first estimate. Step 370 may include calculating, by the first terminal, an estimated error in response to an outcome of a previous iteration; wherein the calculating may include applying a first modulo function.

Step 375 may include transmitting the estimate error to the second terminal over the noisy feedforward channel.

Step 380 may include receiving, by a second terminal, a current received signal;

wherein the current received signal represents the estimated error.

Step 390 may include calculating, by the second terminal, and in response to the current received signal, a current estimate of the portion of the message.

Step 400 may include calculating, by the second terminal, a representation of the current estimate; wherein the calculating may include applying the second modulo function.

Step 410 may include Transmitting, by the second terminal and over the feedback channel, a representation of the current estimate.

Step 340 may include estimating the portion of the message, by the second terminal, and after a completion of the multiple iterations, wherein the estimating of the message is responsive to at least one outcome of at least one iteration of the multiple iterations.

The first transmitted signal may be modulated by any modulation scheme, such as but not limited to pulse amplitude modulation, quadrature amplitude modulation, pulse position modulation, phase shift keying modulation or continuous phase modulation.

The calculating of each representation of the current estimate may include calculating a scaled version of the current estimate modulo a fixed interval.

The calculating of a scaled version of the current estimate modulo the fixed interval may be responsive to power constraints. For example- a maximal power consumption, an allowed power change, and the like.

The calculating of each representation of the current estimate may include calculating a sum of a dither signal and the current estimate and applying the second modulo operation on the sum.

The estimating of the portion of the message may include applying an unmasking function, the unmasking function reverses a masking function applied by the first terminal on the portion of the message.

The applying of the unmasking function may include subtracting a known content. The applying of the unmasking function may include subtracting a content that is generated by a predefined process known to the first and second terminals.

The calculating of each estimate error, by the first terminal, may include calculating a sum of a dither signal and the outcome of the pervious iteration and applying the first modulo operation on the sum.

Figure 6 illustrates method 500 according to an embodiment of the invention.

Method 500 includes an initialization sequence of steps 510, 320, 530, 340 and 350. This initialization sequence of steps is followed by multiple iterations (predetermined number of iterations, monitored by step 360) of steps 570, 375, 380, 390, 400, and 410. Method 300 ends by step 420.

As indicated above, method 500 differs from method 300 by replacing steps 310, 330 and 370 by steps 510, 550 and 570, respectively.

Step 510 may include transmitting a transmitted signal, by a first terminal and over a noisy feedforward channel; wherein the first transmitted signal is a dummy signal.

The dummy signal may have a content of the portion of the message and an intensity that does not exceed a noise level of the feedforward channel.

The dummy signal may have a content that is set regardless of a content of the portion of the message.

Step 550 may include calculating, by the second terminal, a first estimate of the dummy signal.

Step 570 may include calculating, by the first terminal, an estimated error in response to an outcome of a previous iteration and in response to a content of a portion of a message;

wherein the calculating may include applying a first modulo function. Because the first terminal calculates the error estimate, at least partially based on the portion of the message (that was not properly transmitted to the second terminal), the second terminal eventually is able to reconstruct the portion of the message. During the first iteration the first terminal may calculate an error between the first estimate of the dummy signal and during further iterations the first terminal may calculate the error between the outcome of the previous iteration and the portion of the message.

Figure 7 illustrates method 100 according to an embodiment of the invention. Method 100 includes an initialization sequence of steps 110, 120, 130 and 140. This initialization sequence of steps is followed by multiple iterations (predetermined number of iterations, monitored by step 150) of steps 160, 170, 180 and 190. Method 100 ends by step 194.

Step 110 may include receiving, by a second terminal, a first received signal; wherein the first received signal represents a first transmitted signal that was transmitted from a first terminal and propagated over a noisy feedforward channel; wherein the first transmitted signal represents a portion of a message.

Step 120 may include calculating, by the second terminal, a first estimate of the portion of the message.

Step 130 may include calculating, by the second terminal, a representation of the first estimate; wherein the calculating may include applying a second modulo function.

Step 140 may include Transmitting, by the second terminal, over a feedback channel, the representation of the first estimate.

Step 160 may include receiving, by a second terminal, a current received signal; wherein the current received signal represents an estimated error; wherein the estimated error was calculated by the first terminal in response to an outcome of a pervious iteration and may include applying a first modulo function.

Step 170 may include Calculating, by the second terminal, and in response to the current received signal, a current estimate of the message.

Step 180 may include calculating, by the second terminal, a representation of the current estimate; wherein the calculating may include applying the second modulo function.

Step 190 may include transmitting, by the second terminal and over the feedback channel, a representation of the current estimate.

Step 194 may include estimating the portion of the message, by the second terminal, and after a completion of the multiple iterations, wherein the estimating of the message is responsive to at least one outcome of at least one iteration.

Figure 8 illustrates method 200 according to an embodiment of the invention.

Method 200 includes an initialization sequence of steps 210, 220, 130 and 140. This initialization sequence of steps is followed by multiple iterations (predetermined number of iterations, monitored by step 150) of steps 260, 170, 180 and 190. Method 200 ends by step 194. As indicated above, method 200 differs from method 100 by replacing steps 110, 120 and 260 by steps 210, 220 and 260, respectively.

Step 210 may include receiving, by a second terminal, a first received signal; wherein the first received signal represents a first transmitted signal that was transmitted from a first terminal and propagated over a noisy feedforward channel; wherein the first transmitted signal is a dummy signal.

Step 220 may include calculating, by the second terminal, a first estimate of the dummy signal.

Step 260 may include receiving, by a second terminal, a current received signal; wherein the current received signal represents an estimated error; wherein the estimated error was calculated by the first terminal in response to an outcome of a pervious iteration and in response to a portion of a message and may include applying a first modulo function.

Figure 9 illustrates method 600 according to an embodiment of the invention.

Method 600 includes an initialization sequence of steps 610 and 620. This initialization sequence of steps is followed by multiple iterations (predetermined number of iterations, monitored by step 630) of steps 640, 650 and 660.

Step 610 may include transmitting, by a first terminal and over a noisy feedforward channel, a first transmitted signal, thereby allowing the second terminal to receive a first received signal; wherein the first transmitted signal represents a portion of a message.

Step 620 may include receiving, by the first terminal, a second received signal, wherein the second received signal results from a propagation, over a noisy feedback channel, of a representation of a first estimate of at the least portion of the message; wherein the representation of the first estimate is calculated by the second terminal, wherein the calculation of the representation of the first estimate may include applying a second modulo function.

Step 640 may include calculating, by the first terminal, an estimated error, wherein the calculating is responsive to an outcome of a pervious iteration and may include applying a first modulo function.

Step 650 may include transmitting the estimate error to the second terminal over the noisy feedforward channel.

Step 660 may include receiving, by the first terminal and over the feedback channel, a representation of the current estimate. Figure 10 illustrates method 700 according to an embodiment of the invention.

Method 700 includes an initialization sequence of steps 710 and 720. This initialization sequence of steps is followed by multiple iterations (predetermined number of iterations, monitored by step 630) of steps 740, 650 and 660.

Method 700 differs from method 600 by replacing steps 610, 620 and 640 by steps 710, 720 and 740.

Step 710 may include transmitting, by a first terminal and over a noisy feedforward channel, a first transmitted signal, thereby allowing the second terminal to receive a first received signal. The first transmitted signal is a dummy signal.

Step 720 may include receiving, by the first terminal, a second received signal, wherein the second received signal results from a propagation, over a noisy feedback channel, of a representation of a first estimate of the dummy signal. The representation of the first estimate is calculated by the second terminal, wherein the calculation of the representation of the first estimate may include applying a second modulo function.

Step 740 may include calculating, by the first terminal, an estimated error, wherein the calculating is responsive to an outcome of a pervious iteration and to a portion of the message may include applying a first modulo function.

Any combination of any steps of any methods can be provided.

There is provided a first terminal that is configured to execute any combination of any method stages that were mentioned above as executed by the first terminal. See, for example figures 9 and 10, steps 310, 370, 375 and 360 of figure 5 and steps 360, 375, 510 and 570 of figure 6.

There is provided a second terminal that is configured to execute any combination of any method stages that were mentioned above as executed by the second terminal. See, for example figures 7 and 8, steps 320, 330, 340, 350, 380, 390, 400 and 410 of figure 5 and steps 320, 530, 340, 350, 380, 390, 400 and 410 of figure 6.

The invention may also be implemented in a computer program for running on a computer system, at least including code portions for performing steps of a method according to the invention when run on a programmable apparatus, such as a computer system or enabling a programmable apparatus to perform functions of a device or system according to the invention. The computer program may cause the storage system to allocate disk drives to disk drive groups.

A computer program is a list of instructions such as a particular application program and/or an operating system. The computer program may for instance include one or more of: a subroutine, a function, a procedure, an object method, an object implementation, an executable application, an applet, a servlet, a source code, an object code, a shared library/dynamic load library and/or other sequence of instructions designed for execution on a computer system.

The computer program may be stored internally on a non-transitory computer readable medium. All or some of the computer program may be provided on computer readable media permanently, removably or remotely coupled to an information processing system. The computer readable media may include, for example and without limitation, any number of the following: magnetic storage media including disk and tape storage media; optical storage media such as compact disk media (e.g., CD-ROM, CD-R, etc.) and digital video disk storage media; nonvolatile memory storage media including semiconductor-based memory units such as FLASH memory, EEPROM, EPROM, ROM; ferromagnetic digital memories; MR AM; volatile storage media including registers, buffers or caches, main memory, RAM, etc.

A computer process typically includes an executing (running) program or portion of a program, current program values and state information, and the resources used by the operating system to manage the execution of the process. An operating system (OS) is the software that manages the sharing of the resources of a computer and provides programmers with an interface used to access those resources. An operating system processes system data and user input, and responds by allocating and managing tasks and internal system resources as a service to users and programs of the system.

The computer system may for instance include at least one processing unit, associated memory and a number of input/output (I/O) devices. When executing the computer program, the computer system processes information according to the computer program and produces resultant output information via I/O devices.

In the foregoing specification, the invention has been described with reference to specific examples of embodiments of the invention. It will, however, be evident that various modifications and changes may be made therein without departing from the broader spirit and scope of the invention as set forth in the appended claims. Moreover, the terms "front," "back," "top," "bottom," "over," "under" and the like in the description and in the claims, if any, are used for descriptive purposes and not necessarily for describing permanent relative positions. It is understood that the terms so used are interchangeable under appropriate circumstances such that the embodiments of the invention described herein are, for example, capable of operation in other orientations than those illustrated or otherwise described herein.

Those skilled in the art will recognize that the boundaries between logic blocks are merely illustrative and that alternative embodiments may merge logic blocks or circuit elements or impose an alternate decomposition of functionality upon various logic blocks or circuit elements. Thus, it is to be understood that the architectures depicted herein are merely exemplary, and that in fact many other architectures may be implemented which achieve the same functionality.

Any arrangement of components to achieve the same functionality is effectively "associated" such that the desired functionality is achieved. Hence, any two components herein combined to achieve a particular functionality may be seen as "associated with" each other such that the desired functionality is achieved, irrespective of architectures or intermedial components. Likewise, any two components so associated can also be viewed as being "operably connected, " or "operably coupled, " to each other to achieve the desired functionality.

Furthermore, those skilled in the art will recognize that boundaries between the above described operations merely illustrative. The multiple operations may be combined into a single operation, a single operation may be distributed in additional operations and operations may be executed at least partially overlapping in time. Moreover, alternative embodiments may include multiple instances of a particular operation, and the order of operations may be altered in various other embodiments.

Also for example, in one embodiment, the illustrated examples may be implemented as circuitry located on a single integrated circuit or within a same device. Alternatively, the examples may be implemented as any number of separate integrated circuits or separate devices interconnected with each other in a suitable manner.

Also for example, the examples, or portions thereof, may implemented as soft or code representations of physical circuitry or of logical representations convertible into physical circuitry, such as in a hardware description language of any appropriate type. Also, the invention is not limited to physical devices or units implemented in non- programmable hardware but can also be applied in programmable devices or units able to perform the desired device functions by operating in accordance with suitable program code, such as mainframes, minicomputers, servers, workstations, personal computers, notepads, personal digital assistants, electronic games, automotive and other embedded systems, cell phones and various other wireless devices, commonly denoted in this application as 'computer systems'.

However, other modifications, variations and alternatives are also possible. The specifications and drawings are, accordingly, to be regarded in an illustrative rather than in a restrictive sense.

In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. The word 'comprising' does not exclude the presence of other elements or steps then those listed in a claim. Furthermore, the terms "a" or "an," as used herein, are defined as one or more than one. Also, the use of introductory phrases such as "at least one" and "one or more" in the claims should not be construed to imply that the introduction of another claim element by the indefinite articles "a" or "an" limits any particular claim containing such introduced claim element to inventions containing only one such element, even when the same claim includes the introductory phrases "one or more" or "at least one" and indefinite articles such as "a" or "an." The same holds true for the use of definite articles. Unless stated otherwise, terms such as "first" and "second" are used to arbitrarily distinguish between the elements such terms describe. Thus, these terms are not necessarily intended to indicate temporal or other prioritization of such elements The mere fact that certain measures are recited in mutually different claims does not indicate that a combination of these measures cannot be used to advantage.

While certain features of the invention have been illustrated and described herein, many modifications, substitutions, changes, and equivalents will now occur to those of ordinary skill in the art. It is, therefore, to be understood that the appended claims are intended to cover all such modifications and changes as fall within the true spirit of the invention. 1 Appendix A 2 1 I ntr oducti on 3 Feedback cannot improve the capacity of point-to-point memoryless channels4 [1 ]. Nevertheless, noiseless feedback can significantly simplify the transmis-5 sion schemes and improve the error probability performance, see e.g. [2–5].6 These elegant schemes fail however in the presence of arbitrarily small feed-7 back noise, rendering them grossly impractical. This fact has been initially8 observed in [3] for the Additive White Gaussian Noise (AWGN) channel, and9 further strengthened in [6]. A handful of works have tackled the problem of10 noisy feedback as means for improving error performance, see e.g. [7–10].11 However, these works attain their superior error performance at the cost of12 a significant increase in complexity w.r.t. their noiseless feedback counter-13 parts. There appears to be no simple scheme (in the spirit of [3–5]) that is14 robust to feedback noise known hitherto.

15 Our work is therefore motivated by the following question: Does the sim-16 plicity of the infeasible noiseless feedback schemes extend itself to the more17 realistic noisy feedback setup, while still offering near-optimal performance?18 While the answer to this question appears to be negative if one insists on ap-19 proaching capacity in the usual sense (vanishing error probability in the limit20 of large delay), we answer it here in the affirmative under afixed (but small)21 error probability criterion. Specifically, we consider the following setup: Two22 Terminals A and B are connected by pair of independent AWGN channels,23 and are limited by individual power constraints. The channel from Terminal A (resp. B) to Terminal B (resp. A) is referred to as the feedforward (resp. feedback) channel. Terminal A wishes to send bits to Terminal B, within a given bit error probability. Thefigure-of-merit we look at is the capacity gap, which is the amount of excess SNR required by our scheme over the minimal possible SNR for an optimal Shannon scheme (of unbounded complexity), achieving the same bit rate and bit error probability. For this setup, we introduce and analyze a simple interactive scheme, that can operate near ca- pacity. Our construction is based on the Schalkwijk-Kailath (S-K) noiseless feedback scheme [3] with active feedback, endowed with modulo arithmetic. Loosely speaking, our scheme is founded on the following observations: (1) The capacity gap (in dB) attained by the S-K scheme (for noiseless feed- back) is inversely proportional to the number of iterations, and hence capacity is approached in a small number of rounds. (2) The S-K scheme can be described as follows. Terminal A encodes and sends its message via Pulse Amplitude Modulation (PAM), and in subse- quent rounds, sends a scaled version of the estimation error of Terminal B (which is computable due to noiseless feedback), thereby exponentially decreasing the variance of the total estimation error. This scheme can operate using only passive feedback. Alternatively, Terminal B could clearly employ active feedback by transmitting its current estimate of the message, rather then its observations. This simple tweak is mean- ingless in the noiseless feedback case, yet turns out to be essential when feedback is noisy. (3) Suppose the S-K scheme is used when noise is present in the feedback

channel. I n each round, Terminal B knows the sum of the estimation er- ror and the PAM message, whereas Terminal A knows the PAM message only. Describing the estimation error to Terminal A over the feedback channel is therefore a joint source-channel coding problem with side infor- mation at the receiver. Exploiting the side information could potentially yield a markedly better description of the estimation error. One simple way to reap this gain is by employing modulo arithmetic in the spirit of Tomlinson-Harashmia precoding [11, 12]. (4) Following the above joint source-channel coding procedure, the estima- tion error of Terminal B becomes known at Terminal A, up to some excess additive noise induced by the noisy feedback. Due to the modulo- linearity of the operations, this excess noise can be effectively pushed into the forward channel. In a nutshell, our scheme operates as follows. Terminal A encodes and sends its message using PAM. I n subsequent rounds, Terminal B computes its best linear estimate of the message, and feeds back a scaled version of that estimate, modulo afixed interval. I n turn, Terminal A employs a suitable modulo computation and obtains the estimation error, corrupted by excess additive noise. This quantity is then properly scaled and sent over the feed- forward channel to Terminal B. After afixed number of rounds, Terminal B decodes the message via a simple minimum distance rule. Loosely speaking, the scheme’s error probability is dictated by the events of a modulo aliasing in one of the rounds, and the event where the remaining estimation noise in the last round exceeds half the minimum distance of the PAM constella- tion. The maximal number of rounds is limited by the need to control the 1 modulo-aliasing errors.

2 The resulting capacity gap (Theorem 1) consists of four terms: 1) An3 “S-K term” that is inversely proportional to the number of rounds; 2) A4 “concatenated channel” term, that corresponds to the decrease in SNR in-5 curred by trivially concatenating the forward and feedback channels, and6 is (roughly) inversely proportional to the excess SNR of the feedback chan-7 nel over the feedforward channel; 3) a“modulo-aliasing” term that stems8 from the errorfloor imposed by employing the modulo operation, and is9 (roughly) inversely proportional to the SNR of the feedback channel; and 4)10 An auxiliary term that is (roughly) inversely proportional to the SNR of the11 feedforward channel.

12 As an example, for a bit error probability of 10 ⁻⁶ , if the SNR of the13 feedback channel exceeds the SNR of the feedforward channel by 20dB (resp.14 10dB), our scheme operates at a capacity gap of 0.8dB (resp. 3.5dB), with15 only 19 (resp. 11 ) rounds of interaction. This should be juxtaposed against16 two reference systems: On the one hand, state-of-the-art FEC codes attaining17 the same capacity gap and error probability, require roughly a two orders-18 of-magnitude increase in delay and complexity. On the other hand, the19 capacity gap attained by a minimal delay uncoded system with the same20 error probability, is at least 9dB.

21 The rest of the paper is organized as follows. The problem setup is22 introduced in Section 2. Necessary background including the capacity gap23 of uncoded PAM and an active feedback representation of the S-K scheme24 are given in Section 3. Our new scheme is described in Section 4, and its25 performance is discussed in Section 5. A detailed analysis of the scheme 1 is provided in Section 6. Some numerical results andfigures are given in2 Section 7. I mplementation issues and the applicability of our scheme to real3 world scenarios are treated I n Section 8. A discussion of the results and their ears in Section 9. 5 2 etu p 6 In the sequel, we use the following notations. For any number x > 0, we d ^ef

7 write x _dB = 10 log ₁₀ (x) to denote the value of x in decibels. The Gaussian d ^ef ∫∞

8 Q-function is Q (x) = (2π) ⁻ 1

2

x exp (−u ² /2) du, and Q ⁻¹ (·) is its functional9 inverse. We use the vector notation x ^{n def}

= (x ₁ , . . . , x _n ). We write f (x) =10 O(g(x)) for limsup _x→∞ |f (x)/g(x)| <∞.

Our problem d in Fig. 1. The feedforward and feedback ch ng Terminal A to Terminal B and vice versa respectively, are AWGN channels given by Y _n

Y ^˜

_{n = X} ^˜ _{n + Z} ^˜ _{n . 11 Where X n , Yn (resp. X} ^˜ _{n , Y} ^˜ _{n) are the input and output of the feedforward} 12 (resp. feedback) channel at time n respectively. The feedforward (resp. _{13 feedback) channel noise Zn ∼ N (0, σ} ² _{) (resp. Z} ^˜ _{n ∼ N (0, σ} ² _{)) is indepen- 14 dent of the input X n ( resp. X} ^˜ _{n ), and constitutes an i.i.d. sequence. The} 15 feedforward and feedback noise processes are mutually independent.

Terminal A is in possession of a message W ∼ Uniform([M ]), to be described to Terminal B over N rounds of communication. To that end, the terminals can employ an interactive scheme defined by a pair of functions (ϕ, ϕ) as follows: At time n, Terminal A sends a function of its message W and possibly of past feedback channel outputs over the feedforward channel, i.e., = _{ϕ(W, Y} ^{˜ n−1} _). Similarly, Terminal B sends function of its past observations to Terminal A over the feedback channel, i.e., X ^˜ _{n = ϕ(Y} ⁿ _). 1 Remark 1 The dependence of ϕ and ϕ on n is suppressed. I n general, we2 allow these functions to further depend on common randomness shared by3 the terminals. A general interactive scheme can therefore be very complex;4 however, in what follows we will present and discuss a scheme that is very5 simple. We note in passing that our definition of the feedback transmission6 scheme is sometimes referred to as active feedback; the term passive feedback7 is usually reserved to the special case where ϕ(Y ⁿ ) = Y _n . We assume that Terminal A (resp. Terminal B) is subject to a power c _{onstraint P (resp. P} ^˜ _{), namely}

∑ N ∑ N

E(X ²

n)≤ N · P, _E(X ^{˜ 2}

n _{)≤ N · P} ^˜ _.

n=1 n= 1

d ^ef

8 We denote the feedforward (resp. feedback) SNR by SNR = ^P

σ ² (resp. ˜

9 _SN ^{˜ def}

R ₌ ^P

σ ² ). The ratio between the feedback SNR and the feedforward SNR d ^ef

10 is denoted by ΔSNR = ^{SN˜ R}

S _NR . Throughout this work, we assume that the feed-11 back channel has excess SNR over the feedforward channel, i.e. ΔSNR > 1. ^def

1 An interactive scheme (ϕ, ϕ) is associated with a rate R = ^{log M}

N and an2 error probability p _e , which is the probability that Terminal B errs in decoding3 the message W at time N , under the optimal decision rule.

4 The capacity gap Γ attained by the scheme is defined as follows. Recall5 that the Shannon capacity of the AWGN implies that the maximal rate6 achievable by any scheme (of unbounded complexity/delay, with or without7 feedback) under vanishing error probability, is given by

1

C = log(1 + SNR). (1) 2

Conversely, the minimal SNR required to attain a rate R is 2 ^2R − 1. The capacity gap is the excess SNR required by the scheme, i.e.,

d ^ef SNR

Γ(ϕ, ϕ) = Γ =

2 ^2R . (2) − 1

8 Note that if a nonzero bit/symbol error probability is allowed, then one can9 achieves rates exceeding the Shannon capacity (1), and this effect should10 in principle be accounted for, to make the definition of the capacity gap11 fair. However, for small error probabilities the associated correction factor12 (given by the inverse of the corresponding rate distortion function) becomes13 negligible, and we therefore ignore it in the sequel. 14 3 P rel i m i nar i es 15 In this section, we describe the three building blocks underlying our interac-16 tive scheme. First, we discuss the performance of uncoded PAM transmission,17 and the associated capacity gap. We then describe the S-K scheme with ac-18 tive (noiseless) feedback, and derive the associated decay of the capacity gap 1 as a function of the number of interaction rounds. Lastly, we briefly discuss2 the notations and properties of modulo arithmetic to be used in our scheme. 3 3.1 U ncoded PAM PAM is a simple and commonly used modulation scheme, where 2 ^R symbols are mapped (one-to-one) to the set {± 1η, ± 3η, · · · , ± (2 ^R − 1 )η}. 4 Canonically, the normalization factor η is set so that the overall mean square5 of the constellation (assuming equiprobable symbols) is unity. A straight- √

6 forward calculation yields η = 3/ (2 ^2R − 1). I n the general case where the7 mean square of the constellation is constrained to be P , η is replaced with √

8 η P .

9 It mean noise of10 varian , bility of error11 incurred by the optimal detector is bounded by the probability that the noise12 exceed half t he PAM constellation, i.e.,

(√ )

Pη 3SNR

p _e < 2Q = 2Q . (3) σ 2 ^2R − 1

13 Fixing the e or R yields:

( )

1 SNR

R > log 1 + , (4) 2 Γ

where

( ]

d ^ef 1 [ ₂

Γ ₀ (p Q ⁻¹ _p )

e

e) = . (5) 3 2 Comparing (4) and (1), we see that PAM signaling with error probability p _e admits a capacity gap typical value of the

capacity gap of uncoded

Finally, we assume as usual that bits are mapped to PAM constellation symbols via Gray labeling. The associated bit error probability can thus be bounded by

where the approximation is becomes tight for small p _? due to the strong decay of the Q-function.

The S-K Scheme with Active Feedback

Consider the setting of communication over the AWGN with noiseless feedback, i.e., where The S-K scheme with active feedback is described as follows. First, Terminal A maps the message W to a PAM constellation point Θ. In the first round, it sends a scaled version of Θ satisfying the power constraint P. In subsequent rounds, Terminal B maintains an estimate θ„ of Θ given all the observation it has, and feeds it back to Terminal A. Terminal A then computes the estimation error and sends a properly scaled version of it to Terminal B. Formally:

Terminal A: Map the message W to a PAM point Θ.

• Receive

Terminal B: Initialize the Θ estimate ¹ to

(B) Iteration:

Terminal B => Termin al A:

• Send the current Θ estimate:

• Receive

Terminal A: Compute the estimation error ε _n =

Terminal A => Terminal B:

• Send the scaled estimation error where α _n =

that the input power constraint holds, and where

• Receive

Terminal B: Update the Θ estimate ¹ where is the Minimum Mean Square Error (MMSE) estimate of ε _n , thus

(C) Decoding:

At time N the receiver decodes the message using a minimum distance decoder for w.r.t. the PAM constellation.

¹ Note that this is the minimum variance unbiased estimate of Θ.

1 T te attained by the S-K scheme,2 we note that ε _n+1 = ε _n − ε _n . Computing the corresponding variance by3 plugging in the optimal v , β _n , Y _n yields

4 Sinc t s s equvaen to signaling5 over .e.

6 Pluggin -function byQ(x) < ¹

₂ exp(− 1

2x ² )7 gives: (

1 3 SNR · (1 + SNR) ^N−1 )

p _e < exp − .

2 2 2 ^2NR − 1

8 Plugging in the AWGN capacity (1) and removing the“−1” term, we obtain: p _e < 1 (

2 exp − 3 SNR C−R) ⁾

2 _1+SNR · 22N( _.

9 whi ay of the error probability of10 the

11 Let us now provide an alternative interpretation of the S-K scheme perfor-12 mance, in terms of the capacity gap attained after afinite number of rounds.13 Plugging

)

Plugging the resulting R in the definition of the capacity gap (2) and assum- ing yields the following approximation for high SNR:

14 This behavior is depicted by the dashed curve in Fig.3. 1 3.3 M We briefly overview basic notations and properties of modulo arithmetic. For a given d > 0, define the modulo function

( _x )

d

nteger to its argument ² . The

d

4 (i) M _d [x]∈ [− ^d

2 , ₂ ) (ii) if d ₁ + d ₂ ∈ [− ^d

2 , d

2), then M _d d ₂ − x] = d ₁ + d ₂ . (9)

5 -aliasing error term of kd s added to the right-

6 an -s e , or some integer k. 7 (iii) Let V∼ Uniform( [− ^d

2 , d

2)). Then M _d [x + V ] is uniformly distributed

over d

8 [− ^d

2 , ₂ ) for any x∈ R. here 104 The Scheme 11 In what follows we assume that the terminals share a common random i.i.d12 sequence {V} ^N d

n

√ _n=1 where V _n ∼ Uniform([− ₂ , d

2)). Furthermore, we set d = _{13 12P} ^˜ _{which guarantees that E(Md[x + Vn])} ² _{= P} ^˜ _{for any x ∈ R. Recall} 2 (

We arbitrarily define round k + ¹ )

2 = k + 1 for every integer k

that the estimation of the PAM point at Terminal B and time instance n is denoted by and the associated estimation error by e _n

Our scheme is described below.

(A) Initialization:

Terminal A: Map the message W to a PAM point Θ.

Terminal A =Φ· Terminal B:

* Send A ₁ -

* Receive y ₁ = X ₁ + Z ₁

Terminal B: Initialize the Θ estimate ³ to

(B) Iteration:

Terminal B =Φ Terminal A:

® Given the Θ estimate θ _η , compute and send

® Receive

Terminal A: Extract a noisy scaled version of estimation error ε _η : (10)

Note that unless a modulo-aliasing error occurs.

Terminal A => Terminal B:

°Note that this is the minimum variance unbiased estimate of Θ. · Send a scaled version of where a is set so that to meet the input power constraint P (computed later). · Receive Y _n = X _n + Z _n

Terminal B: Update the Θ estimate ³ where

is the MMSE estimate of ε _η . The optimal selection of β _η is described in the sequel.

(C) Decoding:

At time N the receiver decodes the message using a minimum distance decoder for Θ _Ν w.r.t. the PAM constellation.

Recall the capacity gap function of uncoded PAM given in (5). Fix some target error probability p _e . Define:

(ID

1 For a proper choice of parameters, the interactive communication scheme described in Section 4 achieves in A' rounds an error probability p _e and a capacity gap Γ ^∗

d _B satisfying: Γ ^∗

d _B (p _e , N ) < 1

N Γ _0,dB ( ^pe

2 ) + N−1

N (Ψ _{1 ,dB} + Ψ _2,dB ) + Ψ ₃ 1 We prove this theorem is Section 6. 2 Remark 2 λ is a factor that encapsulates the cost of controlling the modulo-3 aliasing error, as seen below. I t decreases with a decreasing p _e . Remark 3 Ψ ₁ is a penalty term roughly corresponding to the decrease in SNR incurred by trivially concatenating the forward and feedback channels. T _{o see this, consi der the concatenated channel from X n to Y} ^˜ _{n where Termi nal B performs si mple li near scaling to meet the power constraint P} ^˜ _{, i . e. X} ^˜ _{n =} √

P ^˜

P +σ2Y _n . The SNR of this channel is d ^ef _{SNR · SN} ^˜ _R

SNR _concatenated = ,

S _{NR + SN} ^˜ _{R + 1}

hence, the associated SNR loss w.r.t. the feedforward channel is

SNR 1 1 1

= 1 + + ≈ 1 + .

SNR _concatenated ΔSNR _SN ^˜ _R ΔSNR4 This latter expression is very similar to Ψ ₁ , with the exception of the addi-5 tional λ factor. Hence, loosely speaking, Ψ ₁ encapsulates the inherent loss6 due to essentially employing a feedback scheme over the concatenated chan-7 nel, together with a feedback power reduction by the amount of λ used to avoid8 modulo-aliasing errors. This loss vanishes for afixed p _e as ΔSNR increases.9 However, if ΔSNR isfixed, this term does not vanish in the limit of high10 SNR. 1 Remark 4 Ψ ₂ can be interpreted as a penalty term stemming from the modulo-2 aliasing error endemic to the system, due to the presence of feedback noise _{3 in the modulo operati ons at Termi nal A. For afixed SN} ^˜ _{R, the mi nimal value 4 of λ supported by our scheme i s gi ven by SN} ^˜ _R ⁻¹ _{, which i n turn dictates the} 5 minimal error probability that can be attained. Due to this errorfloor, our6 scheme cannot achieve any rate in the usual sense. The loss of SNR incurred _{7 by Ψ2 vani shes for anyfixed error probability pe as SN} ^˜ _{R i ncreases.} 8 Remark 5 Ψ ₃ is an additional penalty term (already in logarithmic scale),9 that result from the fact that we consider the capacity gap in terms of SNR10 ratios, whereas the explicit term arising from the capacity formula is related

( )

11 t R ⁻¹ . Corollary 1 (H igh SNR behavior) Let ΔSNR and p _e befixed. The capac- ity gap attained by our scheme for SNR large enough, can be approximated by

[ ]

1

Γ ^∗

d _B (p _e , N )≈ 1

N Γ _0,dB ( ^pe N−1

2 ) + N 1 + . (12) λΔSNR dB12 Thefirst term is roughly the capacity gap of the S-K scheme with noiseless13 feedback. The second term pertains to the SNR loss w.r.t. a concatenated14 channel as well as modulo-aliasing errors, as discussed in Remark 3. 15 Remark 6 Note that there is a“low SNR” regime (related also to the tar-16 get error probability or to ΔSNR), where the loss terms Ψ _{1 ,dB} + Ψ _2,dB are17 larger than say Γ _0,dB (p _e ). I n that case, setting N = 1, namely using an un-18 coded system with no interaction, is the optimal choice of parameters for our scheme ⁴ . As we shall see however, for many practical values of SNR, SÑR and p _e , interaction results in significant gains. 6 Proof of Main Result In Subsection 3.2 we analyzed the error probability of S-K with noiseless feedback, relying on the fact that all the noises are jointly Gaussian, including the noise ε _N experienced by the PAM decoder. To that end, we were able to directly use the error probability analysis of simple PAM over AWGN discussed in Subsection 3.1.

In the noisy feedback case however, the non-linearity induced by modulo operations at both terminals induce a non-Gaussian distribution of ε _N . An analysis of the decoding error based on the actual distribution of ε _N is very involved. Yet, an upper bound can be derived via a simple coupling argument described below.

Recall that Terminal A computes a noisy scaled version of the es- timation error of Terminal B, via a modulo operation (10). For any n∈ {1, . . . , N— 1} we define E _N as the event where this computation results in a modulo-aliasing error, i.e.,

Furthermore, we define EN as the PAM decoding error event:

⁴ The reason we get the looser term in (12) is for brevity of exposition; a

more accurate trade-off is given in the next section. where d _min is the PAM constellation minimal distance. As mentioned above, the distribution of ε _N is not Gaussian due to the nonlinearity introduced by the modulo operations. To circumvent this, we consider the following upper bound for the error probability:

1 The inequality stems from the fact that a modulo-aliasing error does not2 necessarily cause a PAM decoding error.

3 To proceed, we define the coupled system as a system that is fed by the4 same message and experiences the (sample-path) exact same noises, with the5 only difference being that no modulo operations are implemented at neither6 of the terminals. Clearly, the coupled system violates the power constraint at7 Terminal B. However, given the message W , all the random variables in the8 coupled system are jointly Gaussian, and in particular, the estimation errors9 ε _n in that system are Gaussian for n = 1, . . . , N . Moreover, it is easy to10 see that the estimation errors are sample-path identical between the original11 system and the coupled system until thefirst modulo-aliasing error occurs.12 To be precise: _{13 Lemma 1 denote the probabi li ty operator in for the coupled process.} 14

15 1 oreover, or any i ∈ {2, ... , N}

2 _{and trivially P h concludes the proof.}

Combining the above with (14) and applying the union bound in the coupled system, we obtain

Calculati olves only scalar Gaussian densi-4 ties, which si nificantl simplifies the analysis. 5 6.1 Calculation of the Parameters

d ^ef

6 _{We set γn su = P} ^˜ _r(En−1) = p _m , for some p _m small7 enough to b . y, recalling the definition (13) and that √

8 d = _12P ^˜ _{, an n in the coupled system is Gaussian, we} 9 obtain the foll :

10 11 k 7 λ defined in (11) is a special case of the above with p _m = ^pe _2N . _{2 Note again that λ ust hold, which lower bounds the attainable} 3 error probability,

4 α is set so that the input power constraint at Terminal A is met. namely5 _{P≥ E} ^˜ _X ²

_{n = α} 2E˜ε ²

n. From (16) it stems tha

√

P

α = .

λ _P ^˜

6 Remark 8 It should be emphasized that this calculation is accurate for the7 coupled system only. In the original system, a modulo-aliasing error may _{8 cause the power constraint to be violated. However, since ε} ²

_{n ≤ 3P} ^˜ _{and since} 9 the probabilities of modulo-aliasing errors are set to be very low (lower then10 the target error probability) the power constraint violation is negligible, and11 can be practically ignored; e.g., for p _e = 10 ⁻⁶ and N = 20, the increase12 in avera ower due to this effect is lower than 10 ⁻⁴ dB. We also note in t the power lways satisfied (regardless ter choice), .

15 The ution of the estimation error. The16 linear e e optimal estimate in the coupled system, Gaussian. We would thus like to m _{inimize E} ^˜ _{(εn− εn)} ² _{. Plugging in Y n+1 = α(γnεn + Z} ^˜ _{n) + Zn+1 and solving} 19 the optimization problem yields:

√ ( )

SNR · 1− ¹

σ _{n λSN} ^˜ _R

β _n+1 = ,

σ 1 + SNR

20 where σ ²

n is the variance of ε _n in the coupled system. Recalling that ε _n+1 =21 ε _n − ε _n and computing the MMSE for the optimal choice of β _n+1 above, we 1 obtain a recursive formula for σ ²

n, which boils down to the following expression2 for th

3 and using (15), the error probability is bounded by

(√ )

4 Juxtapos and (7) shows that e noisy feed se, the expo-5 nential growth of the SNR with the number rounds is d d by a factor6 that is inversely related to SNR and ΔSNR, and also related to the term7 λ that is in turn determined by the modulo-aliasing error probability. This8 factor corresponds to Ψ ₁ , Ψ ₂ in Theorem 1 , where Ψ ₃ is a remainder term obtained by pedestrian manipulations and the inequality− ln(1− x)≤ ^{x 9}

x−110 for x < 1. The result in Theorem 1 was obtained for the specific choice11 p _m = ^pe

2 _N of the modulo-aliasing error. I n general, reducing p _m decreases λ12 which in turn decreases SNR _N , and hence increases the second addend on13 the right-hand-side of (19), resulting in a trade-off that could potentially be14 further optimized. 15 7 N um er i cal R esu lts 16 The behavior of the capacity gap for our scheme as a function of the number17 of interaction rounds and ΔSNR is depicted in Fig. 3 and Fig. 4, for“high18 SNR” and“low SNR” setups. I n bothfigures we plotted the capacity gap,19 for a target rate R and a target error probability p _e = 10 ⁻⁶ , where the SNR 1 corresponding to R was found by numeric search on (8), and the capacity2 gap calculated by definition (2). We can see that the higher ΔSNR, the3 smaller the capacity gap, where ΔSNR = 30dB is close to noiseless feedback.4 The points marked n _opt are those for which the capacity gap is less than5 0.2dB above the minimal value attained. I n Fig. 3, R = 1, and can see6 that ΔSNR = 10dB reduces the capacity gap to 4.2dB in 12 iterations, and7 ΔSNR = 20dB reduces the capacity gap to 1.1dB in 22 iterations. I n Fig. 48 R = 4 and for ΔSNR = 10dB the capacity gap to 3.5dB in 11 iterations, and NR = 20dB reduces the capacity gap to 0.8dB in 19 iterations. Observing10 (12) we can see that for high SNR the result is only a function of ΔSNR,11 thus does not depend on the target rate or the base SNR. 12 8 N otes on I m pl em entati on 13 The scheme described in this paper is simple and practical, as opposed to its14 noiseless feedback counterparts. This provides impetus for further discussing15 implementation related aspects. The following conditions should be met for16 our results to carry merit: 1) I nformation asymmetry : Terminal A has sub-17 stantially more information to convey than Terminal B; 2) SNR asymmetry :18 The SNR of the feedforward channel is lower than the SNR of the feedback19 channel. This can happen due to differences in power constraints and/or20 path losses; 3) Complexity/delay constraints: There are severe complexity or21 delay constraint at Terminal A; 4) Two-way signaling: Our scheme assumes22 sample-wise feedback. The communication system should therefore be full23 duplex where both terminals have virtually the same signaling rate; hence, 1 the terminals split the bandwidth between them even though only Terminal2 A is transmitting information. This situation can sometimes be inherent to3 the system, but should otherwise be tested against the (non-interactive) so-4 lution where the entire bandwidth is allocated to Terminal A. This choice5 of forward vs. feedback bandwidth allocation yields a system trade-off that6 is SNR dependent: Terminal A can use our scheme and achieve a rate of7 C(SNR _dB −Γ ^∗

d _B ), or alternatively employ FEC over the full forward–feedback8 bandwidth, thereby doubling the forward signaling rate but also incurring a9 3dB loss in SNR and a potentially larger capacity gap Γ ^FEC

d _B , resulting in a10 rate of 2C(SNR _dB − 3dB− Γ ^FEC

d _B ). I t can therefore be seen that our solution11 is generally better for low enough SNR. For instance, for p _e = 10 ⁻⁶ and12 ΔSNR > 30dB our scheme outperforms (with comparable complexity and13 delay) full bandwidth uncocded PAM for any SNR < 23dB, and outperforms14 (with significantly smaller complexity and delay) full bandwidth FEC with15 Γ ^FEC

d _B = 3dB for any SNR < 9dB.

16 The use of very large PAM constellations, whose size is exponential in17 the product of rate and interaction rounds, seemingly requires extremely low18 noise and distortion at the digital and analog circuits in Terminal A, which19 may appear to impose a major implementation obstacle. Fortunately, this20 is not the case. The full resolution implied by the constellation size is by21 construction confined only to the original message Θ and thefinal estimate _{22 Θ} ^̂ _{N ; the transmitted and received signals in the course of interaction can be} 23 safely quantized at a resolution determined only by the channel noise (and24 not thefinal estimation noise), as in commonplace communication systems.25 Figuratively speaking, the source bits are revealed along the interaction pro- 1 cess, where the number of bits revealed in every round is determined by the2 channel SNR. This desirable property has also been confirmed in simulations.3 Another important implementation issue is sensitivity to model assump-4 tions. We have successfully verified the robustness of the proposed scheme in5 several reasonable scenarios including correlative noise, excess quantization6 noise, and multiplicative channel estimation noise. The universality of the7 scheme and its performance for a wider range of models remains to be further8 investigated. 9 9 D iscu ssi on 10 Note that so far we have limited our discussion to the PAM symbol error11 rate p _e . The bit-error rate is in fact lower, since an error in PAM decoding12 affects only a single bit with high probability (6), assuming Gray labeling.13 However, note that the modulo-aliasing error will typically result in many14 erroneous bits, and hence optimizing the bit error rate does not yield a major15 improvement over its upper bound p _e . Furtherfine-tuning of the scheme can16 be obtained by non-uniform power allocation over interaction rounds in both17 Terminal A and B; in particular, we note that Terminal B is silent in the last18 round, which can be trivially leveraged. We also note in passing that our19 scheme can be used in conjunction with FEC as an outer code, to achieve20 other power/delay/complexity/error probability tradeoffs.

21 We note again that for any choice of SNR and ΔSNR, the error prob-22 ability attained by our scheme cannot be made to vanish with the number23 interaction rounds while maintaining a non-zero rate, as in the noiseless feed- 1 back S-K scheme case. The reason is that (17) implies a minimal attainable2 error probability dictated by the modulo-aliasing incurred by feedback noise.3 Equivalently, one cannot get arbitrarily close to capacity for a given target4 error probability; the reason is that while increasing the number of iter-5 ations would increase SNR _N and reduce the PAM decoding error term in6 (19), it would also increase the modulo-aliasing error term in (19). Hence,7 our scheme is not capacity achieving in the usual sense. However, it can get8 close to capacity in the sense of reducing the capacity gap using a very short9 block length, typically N ≈ 20 in the examples presented. To the best of10 our knowledge, FEC schemes require a block length typically larger by two11 order of magnitudes to reach the same gap at the same error probability.12 Consequently, the encoding delay of our scheme is also markedly lower than13 that of competing FEC schemes. Alternatively, compared to a minimal delay14 uncoded system under the same error probability, our scheme operates at a15 much lower capacity gap for a wide regime of settings, and hence can be16 significantly more power efficient.

17 Another important issue is that of encoding and decoding complexity.18 Our proposed scheme applies only a two multiplications and one modulo19 operation at each terminal in each interaction round. This is markedly lower20 than the encoding/decoding complexity of FEC, even if non-optimal methods21 such as iterative decoding are employed.