extfieldsofstudy:
Computer Science
Mathematics

text:
Interference Channel with Generalized Feedback (a.k.a. with source cooperation). Part I: Achievable Region

An Interference Channel with Generalized Feedback (IFC-GF) is a model for a wireless network where several source-destination pairs compete for the same channel resources, and where the sources have the ability to sense the current channel activity. The signal overheard from the channel provides information about the activity of the other users, and thus furnishes the basis for cooperation. In this two-part paper we study achievable strategies and outer bounds for a general IFC-GF with two source-destination pairs. We then evaluate the proposed regions for the Gaussian channel. Part I: achievable region. We propose that the generalized feedback is used to gain knowledge about the message sent by other user and then exploited in two ways: (a) to {\em relay} the messages that can be decoded at both destinations--thus realizing the gains of beam-forming of a distributed multi-antenna system--and (b) to {\em hide} the messages that can not be decoded at the non-intended destination--thus leveraging the interference"pre-cancellation"property of dirty-paper-type coding. We show that our achievable region generalizes several known achievable regions for IFC-GF and that it reduces to known achievable regions for some of the channels subsumed by the IFC-GF model.

Introduction
The practical bottleneck of today's communication networks is interference. The solution of commercial available networks is thus to avoid interference through division of the resources, i.e., time, spectrum, space and waveforms, among the competing users. This approach is appealing in practice because it results in a simple network architecture. It might also appear a good solution in theory since it is well known that in SISO (Single Input Single Output) uplink and downlink wireless channels with perfect centralized channel state information, it is sum-rate optimal to allocate all the available channel resources to the user who experiences the instantaneous highest channel gain [39]. Perfect orthogonalization of the users is however not possible in practice. The practical approach to deal with residual interference is to treat it as noise, thus completely neglecting its structure. Whenever interference is treated as noise, the system becomes rate-limited even when there is no power limitation at the transmitters. This negative view of interference was further reinforced by scaling law results of the early 00's that showed that the total rate of the wireless network with K users only scales as √ K, thus yielding a vanishing per-user rate as the network grows [34]. It was also conjectured that, even with cooperation, the multiplexing gain of an interference network would be one irrespectively of the number of users, thus again the per-user rate would vanish as the number of users in the network grows [22].
On the other hand, it has been known since the mid 70's that there exist channels where interference does not reduce capacity [4,41]. These channels are said to have "very strong interference", that is, the power imbalance between the useful signal and the interfering signal at a receiver is so large that a given user can first decode the interfering signal by treating its own signal as noise, then strip the (now known) interference from its received signal, thus effectively having an interference-free channel. This early example showed that interference should not be treated as noise in general-in fact, as opposed to noise, it has a structure that can be exploited-and that power imbalance must be leveraged upon in the system design. With these observations in mind, much progress has been made recently in understanding the ultimate performance limits of interference networks [1,14]. In the authors' opinion, the major recent result has been to show that in an interfering network with K users the sum-rate capacity scales as K 2 log(1+SNR). This implies that each user can get half the rate it would get if it were alone on the network, no matter how how many users are present in the network. The technique that achieves this capacity scaling is referred to as interference alignment [1]. Under the interference alignment paradigm, users do not avoid interference. Instead, they make sure that the interference they collectively generate at a given receiver is neatly confined in a specific signal subspace. This leaves the complement of this subspace interference free. With interference alignment, a per-user rate of 1 2 log(1 + SNR) can be achieved irrespectively of the number of users.
In this work we consider networks of full-duplex nodes, where several sourcedestination pairs share the same channel. The channel is assumed to be static so that every node in the network has perfect knowledge of the channel sate. Extensions to networks of half-duplex nodes and/or of time-varying channels, such as fading channels, are planned as part of future work. We focus on the case where all nodes can listen to the channel activity. In particular, we are interested in the case where the sources can "overhear" what the other sources are sending, as in relay networks. The key observation is that interference due to simultaneous communications effectively spreads "common information" around the network. This information provides the basis for cooperation among otherwise uncoordinated nodes.

Related Works
The signal a node can "overhear" form the channel is a form of feedback. To distinguish this feedback information from the classical Shannon output feedback, Willems referred to it as Generalized Feedback (GF) [48]. GF encompasses a wide range of possible situations, examples are: noisy output feedback (with the nonfeedback case and the output feedback case at the two extremes); conferencing encoders (where there are separate noise-free and interference-free links between the sources, each of finite capacity); the case of GF with independent noises, sometimes referred to as user cooperation. The motivation to study GF comes from the work of Gaarder and Wolf [49] who showed that output feedback can enlarge the capacity region of a MAC channel. Here, we consider the general case of GF. Hence our results can be specialized to all the above situations. Our approach-especially when in dealing with outer bounds-shows that all the above cases can be dealt with in great generality. One of our contributions is to show a unifying way of deriving some of the results available in the literature.
MAC-GF In [48], an achievable region for the MAC-GF (Multiple Access Channels with Generalized Feedback) was derived. The two main ingredients are regular block-Markov superposition coding and backward decoding. Block-Markov coding, also known as Decode-and-Forward from the work by Cover and A. El Gamal [10] in the context of relay channels, works as follows. Communication proceeds over a frame of N > 1 slots. The source splits the message to be transmitted in a given slot into two parts. The first part is decoded by the destination, but treated as noise by the relay. The second part is decoded also by the relay, that then retransmits it to the destination in the next slot. Because the source knows what the relay is going to send in the next slot, it can "coordinate" with the relay. In each slot, the destination receives the superposition of the new information (sent by the source) and the repetition of part of the old information (forwarded by the relay). The receiver waits until the whole frame has been received. Then appropriately combines the information sent in consecutive slots to recover all the transmitted messages.
Willems's coding scheme for Gaussian channels was popularized by Sendonaris et al. [42] under the name of user cooperation diversity in the context of cellular networks. In [42] it was showed that cooperation between users achieves collectively higher data rates or, alternatively, allows to reach the same data rates for less transmission power. Since the publication of [42], the interest in cooperative strategies has not ceased to increase (we do not attempt here to review all the extensions of [42] for sake of space).
Although the MAC-GF has proved to be instrumental in understanding the potential of user cooperation in networks, it is not as well suited for ad-hoc/peerto-peer networks, where the absence of coordination among users exacerbate the problem of interference. Host-Madsen [21] first extended the Gaussian MAC-GF model of [42] to the case of Gaussian IFC-GF. Before dwelling into the literature of IFC-GF, we briefly revise the known results on IFC without feedback.
IFC without feedback The capacity region of a general IFC without feedback is still unknown. The largest achievable region is due to Han and Kobayashi [19], whose "compact" expression appeared [6]. In IFCs without feedback, communications is as follows. Each transmitter splits its message in two parts: a common message and a private message. The two messages are superimposed and sent through the channel. Each receiver decodes its intended common and private messages, as well as the common message of the other user, by treating the other user's private message as noise. The goal of this joint decoding is to reduce the interference level. The idea of information splitting was first proposed by Carleial [5], to whom many other early results on IFCs are due.
In this work, we propose an achievable region that combines the idea of information splitting with that of Block Markov Coding & Backward Decoding.
Early work on IFC-GF Host-Madsen [21] first studied inner and outer bounds for the sum-rate of IFC with both source and destination cooperation. He showed that in IFC networks with two SISO source-destination pairs, where the channel gains stay constant and the user' powers increase, the multiplexing gain is one, with both types of cooperation (instead of two, which would be the case if cooperation were equivalent to a 2×2 virtual MIMO channel). In [21], several achievable strategies are proposed for the Gaussian channel only, each relatively simple and tailored to a specific sets of channel gains.
The work in [21] was extended to a general DMC (Discrete Memoryless Channel) IFC-GF in [2,24,45]. These works proposed to add one extra level of information splitting to the original Han-Kobayashi scheme.
IFC-GF: Cooperation on sending the common information In [45], we proposed to further split the common message in two parts: one part (referred to as non-cooperative common information) is as in the Han-Kobayashi scheme, while the other part (referred to as cooperative common information) is decoded at the other source too. The sources use a block-Markov encoding scheme where in a given slot they "retransmit" the cooperative common information learnt in the previous slot. This cooperation strategy aims to realize the beam-forming gain of a distributed MISO channel.
A scheme similar to ours in [45] was independently proposed by Jiang et al. in [24] for the IFC with output feedback (i.e., not for a general GF setting). The difference lies in the way the cooperative common information is dealt with, both at the sources and at the destination. It is not clear which scheme achieves the largest achievable region (we will elaborate more on this point later on).
Recently, Prabhakaran and Viswanath [35] developed an outer bound for the sum-rate of a symmetric Gaussian IFC-GF with independent noises, inspired by the semi-deterministc model of [44]; they showed that their upperbound is achievable within a constant gap of 18 bits when the cooperation link gains are smaller than the direct link gains; their achievable strategy is a simple form of our region in [45].
Cooperation on sending the common information is the essence of the first achievable region presented in Part I this work.
IFC-GF: Cooperation on sending the private information In [2], the authors proposed to further split the private message in two parts: one part (which we shall refer to as non-cooperative private information) is as in the Han-Kobayashi scheme, while the other part (which we shall refer to as cooperative private information) is decoded at the other source too. The sources use a block-Markov encoding scheme where in a given slot they "hide" the cooperative private information learnt in the previous slot to their intended receiver by using Gelfand-Pinsker coding [7,18]. An approach similar to [2] (commonly referred to as "dirty paper coding" for Gaussian channels [7]) was already used in [21] to characterize the high SNR sum-rate capacity of the Gaussian IFC-GF. In [21], it was first noted that in the high SNR regime, nulling the interference (i.e., an ancestor of interference alignment) is asymptotically optimal.
In [3], the ideas of [2] and of [45] were merged into a scheme where both the common and the private information are split into two parts. In [53] we proposed a different (more structured) coding strategy than in [3]. As opposed to [3], in [53] we did not use independent Gelfand-Pinsker binning codes to pre-cancel the effect of the cooperative private information. Instead, we proposed to superimpose several Gelfand-Pinsker binning codes (inspired by the work in [30] for cognitive IFCs) in such a way that the different binning stages are performed se-quentially and conditionally on the previous ones. In addition, we also added a binning step similar to Marton's achievable scheme for a general two-user broadcast channel [32]. The broadcast-type binning step is possible in IFC-GFs because each encoder knows part of the message sent by the other encoder, i.e., each transmitter is partially cognitive in the sense of [30]. A simple form of [53]'s region was shown to be optimal within a constant gap of 18 bits for the symmetric Gaussian IFC-GF with independent noises when the cooperation link gains are larger than the direct link gains.
The second achievable region presented in Part I of this work is a further enhancement of [53].
IFC with degraded output feedback The GF setting covers a wide range of situations. In particular, the case of degraded output feedback has been studied by a number of groups. Degraded output feedback refers to the case where the GF signal received at a source is a noisier version of the signal received at the intended destination. When the variance of the extra noise on the GF signal is zero, we have the so called output feedback. Kramer in [25,26] developed inner and outer bounds for the Gaussian channel with output feedback. Kramer and Gastpar [17], and more recently Tandon and Ulukus [37], derived an outer bound for the degraded output feedback case based on the dependance balance idea of Hekstra and Willems [20]. Suh and Tse [43] developed a novel outer bound for the Gaussian case with output feedback and showed it to be achievable to within 1.7 bits. In [43] it was also shown that the achievable region of [24] is optimal for the case of deterministic channels with output feedback.
As mentioned earlier, our achievable region is applicable to all forms of GF, thus also to the case of output feedback.
Other channel models The IFC-GF reduces to some well known channel models. Under certain conditions, it reduces to a Broadcast Channel (BC) [32], or to MAC-GF [48], or to a Relay Channel (RC) [10], or to a Cognitive IFC (C-IFC) [38].
We shall also describe how our results encompass known results for these channels.

Summary of Contributions
In this first part of the paper we present our achievable regions. We first present a region where cooperation is on sending the common information only. The purpose is to highlight the key elements of our encoding and decoding scheme before proceeding to describe our more general scheme, where the sources cooperate in sending both the common and the private messages. Our contributions are as follows.
Cooperation to send the common information only: 1. We propose a structured way of superimposing the different codebooks that greatly simplifies the error analysis. Our codebook "nesting" is such that the "cloud center" codebook is the one all terminals will be decoding, i.e., the cooperative common codebook, to which we superimpose the noncooperative common codebook (to be decoded by the two destinations but not by the other source) and finally we superimpose the non-cooperative private codebook (to be decoded at the intended receiver only). We shall see that although the destinations have to decode five messages, only 5 out of the possible 2 5 − 1 = 31 error events matter.
2. We then perform Fourier Motzking elimination to obtain a region with only five types of rate bounds, as in the case of IFC without feedback. This was not immediately obvious since, with GF, each message is split into three parts, and not in two as for the case without feedback.
3. We also show that when cooperation is on sending the common information only, the achievable rate region cannot be enlarged if the sources are required to decode more information than they will eventually "relay" to the destinations. 4. We show how our region does reduce to the achievable regions of the channels subsumed by the IFC-GF model.
For the more general form of cooperation (to send both the common information and the private information): 1. We extend our previous achievable region so as to include cooperation on sending the private information too. Our achievable region uses superposition of several Gelfand-Pinsker binning codes. We propose a structured way of binning that reduces the number of rate constraints necessary to guarantee arbitrary small probability of error at the encoders.
Moreover, we propose to "jointly bin" the different codebooks, rather than perform several binning steps, one per codebook. Our proposed joint binning is similar in spirit to multiple description source coding.
2. The error analysis at the decoders could be very messy and lengthy with so many messages to decode. Our proposed method for error analysis leverages the way the codebooks are superimposed. The type of error analysis we use could be of interest in its own. In particular, with our encoding structure, we show that only 28 error events matter, out of the 2 8 − 1 = 255 possible.
3. We show how our new region does reduce to the achievable regions of the channels subsumed by the IFC-GF model. Our region however does not give the largest possible achievable rate for the relay channel because it does not include Compress-and-Forward [10]. 1 Extensions of the current achievable region so as to include Compress-and-Forward are left for future work.
4. For the Gaussian channel, by means of a numerical example, we show that cooperation greatly increases the achievable rates with respect to the case without GF.
The rest of the paper is organized as follows. Section 2 introduces the channel model and the notation. Section 3 revises known results for IFC without feedback. Section 4 presents our achievable regions; in particular, subsection 4.1 describes the region where cooperation is on sending the common message only, and subsection 4.2 describes the region where cooperation is also on sending the private message. Section 5 evaluates the achievable region in subsection 4.1 for the Gaussian channel (the evaluation of the region in subsection 4.2 is postponed to Part-II of this paper where we will also compare it with an outer bound). Section 6 concludes Part I of this paper. All the proofs are in the Appendix. Fig. 1 shows an IFC-GF with two source-destination pairs. It consists of a channel with two input alphabets (X 1 , X 2 ), four output alphabets (Y 1 , Y 2 , Y 3 , Y 4 ), and a

Network Model and Definitions
We assume that all the alphabets are finite sets (the extension to continuous alphabets follows from standard argument [12]) and that the channel is memoryless. Source u, u ∈ {1, 2}, has a message W u for destination u. The messages W 1 and W 2 are independent and uniformly distributed over the set {1, · · · , e n R 1 } × {1, · · · , e n R 2 }, where n denotes the codeword length and R u the transmission rate for user u, u ∈ {1, 2}. At time t, t ∈ {1, · · · , n}, source u maps its message W u and its past channel observations Y t−1 u into a channel input symbol At time n, destination u outputs the estimate of its intended message W u based on all its channel observations Y n u+2 , i.e., The capacity region is the closure of all rate pairs (R 1 , R 2 ) such that max u∈{1,2}

Notation
The symbol R xyz is used to indicate the information rate "from source x to destination y with the help of z", with x ∈ {1, 2}, y ∈ {0, 1, 2} and z ∈ {c, n}. In particular, y = 0 means that the message is decoded at both destinations (common message), y = 1 means that the message is decoded only at destination 1 (private message for user 1), and y = 2 means that the message is decoded only at destination 2 (private message for user 2); z = c means that the message is sent cooperatively by both sources, and z = n means that the message is sent non-cooperatively. T (n) (P |S) indicates the set of length-n sequences that are strongly -typical with respect to the distribution P , conditioned on the sequences in S [13].

IFC without feedback
In this section we briefly revise the best known inner and outer bound regions for an IFC without feedback. This will make the exposition of our coding strategy and outer bound easier. The channel transition probability of an IFC without feedback is that is, the GF signals Y 1 and Y 2 are independent of the inputs (for example Y 1 = Y 2 = ∅).

Inner Bound Region
The largest known achievable region for an IFC without feedback is due to Han and Kobayashi [19] and is as follows [6]. Class of Input Distributions: Consider a distribution from the class The channel transition probability P Y 3 Y 4 |X 1 X 2 is fixed, while the other factors in (1) can be varied. Rate Splitting: The message W u ∈ {1, ..., e nRu }, u ∈ {1, 2}, is split into two parts (W u0n , W uun ): W u0n ∈ {1, ..., e nR u0n } is the common information decoded at both receivers while W uun ∈ {1, ..., e nRuun } is the private information decoded only at the intended receiver, with R u = R u0n + R uun . Without feedback, all messages are sent non-cooperativly. Coodbook Generation: Consider a distribution in (1). Pick uniformly at random a length-n sequences Q n from the typical set T (n) (P Q ). For the codeword Q n = q n , pick uniformly at random e nR 10n length-n sequences U n 1 (k), k ∈ {1, · · · , e nR 10n }, from the typical set T (n) (P U 1 |Q |q n ). For each codeword Q n = q n and each codeword U n 1 (k) = u n 1 (k), pick uniformly at random e nR 11n length-n sequences T n 1 (m, k), m ∈ {1, · · · , e nR 11n }, from the typical set T (n) (P T 1 |QU 1 |q n , u n 1 (k)). For each Q n = q n , U n 1 (k) = u n 1 (k) and T n 1 (m, k) = t n 1 (m, k), choose uniformly at random a sequence X n 1 (m, k) from the typical set T (n) (P X 1 |QU 1 T 1 |q n , u n 1 (k), t n 1 (m, k)). The generation of the codebooks at source 2 proceeds similarly. Encoding: In order to send the messages W u = (W u0n , W uun ), source u, u ∈ {1, 2}, transmits X n u (W u0n , W uun ). Decoding: Destination 1 decodes from Y n 3 the triplet (W 10n , W 20n , W 11n ) by searching for a unique pair (i 1 , j 1 ), j 1 ∈ {1, ..., e nR 10n } and i 1 ∈ {1, ..., e nR 11n }, and some index j 2 , j 2 ∈ {1, ..., e nR 20n }, such that If no pair (i 1 , j 1 ) is found, or more than one pair is found, the receiver sets (i 1 , j 1 ) = (1, 1); in this case we say that an error at destination 1 has occurred. Decoding at destination 2 proceeds similarly. Error Analysis: The error analysis can be found in [6]. The probability of error at destination 1 can be driven to zero if the rates R u = R u0n + R uun , u ∈ {1, 2}, are such that and similarly, the probability of error at destination 2 can be driven to zero if Achievable Region: The region given by the intersection of (2) and (3) can be compactly expressed after Fourier-Motzkin elimination as [6]: ). For any distribution in (1) the following region is achievable: Without loss of generality, one can set T 1 = X 1 and T 2 = X 2 in (4), and, by Caratheodory's theorem, choose the auxiliary random variables (Q, U 1 , U 2 ) from alphabets with cardinality |Q| ≤ 7, |U 1 | ≤ |X 1 | + 4 and |U 2 | ≤ |X 2 | + 4.

Remark 3.2.
It was remarked in [6] that after Fourier-Motzkin elimination, the following bounds also appear: however they can be shown to be redundant. Intutively, the reason is as follows: if , then decoding at destination 2 constrains the rate of source 1 too much; in this case, destination 2 should not be required to decode the common information U 1 . Indeed, it can be shown [6] (see also Appendix A) that the rate points for which (2a) + (3b) < R 1 , but otherwise satisfy all other rate constraints in (4), are contained in the sub-region of (4) obtained by choosing U 1 = ∅; thus the constraint R 1 ≤ (2a) + (3b) can be removed without enlarging the achievable region. A similar reasoning holds for the constraint R 2 ≤ (3a) + (2b).

Outer Bounds
As shown in the second part of this paper, the outer bound techniques of [28] for the Gaussian channel, and the bound in [44] for the semi-determinisic channel, give: and [44]). For any P U X 1 X 2 = P U P X 1 |U P X 2 |U , the following region is an outer bound for a general IFC without feedback: i.e., same marginal distribution, but otherwise P Y 3 ,Y 4 |X 1 ,X 2 has arbitrary joint distribution. Furthermore, if the channel is semi-deterministic as defined in in [44], that is, if there exist deterministic functions f 3 , f 4 , v 32 , v 41 and noise random variables Z 3 , Z 4 such that where V 41 and V 32 are independent copies of V 41 = v 41 (X 1 , Z 4 ) and V 32 = v 32 (X 2 , Z 3 ) conditioned on the input (X 1 , X 2 ).
Remark 3.4. Other outer bounds exist for specific channels. For example, for the Gaussian channel in weak interference, Kramer [28] developed a bound based on the idea of enhancing the IFC and make it equivalent to a degraded broadcast channels. Shang et at [52], simultaneously and independently of [33,47], showed that for the Gaussian channel in very weak interference, it is sum-rate optimal to treat the interference as noise. Outer bounds based on the idea of dependance balance appeared in [17,37]. Extensions of these bounding techniques to non-Gaussian channels and/or their evaluation is not straightforward and it will not be attempted in this paper.

Inner Bounds
In this section we derive our achievable region. We divide the section into two parts. In the first part (Section 4.1), we propose a scheme where the sources cooperate by "beam-forming" part of the common messages. In this scheme, all messages are superimposed and thus we refer to it as superposition-only achievable region. In the second part (Section 4.2), we propose a scheme where the sources also cooperate on sending part of the private messages by using binning, or dirty paper coding. We refer to this schemes as superposition & binning achievable region. The superposition & binning achievable region includes the superpositiononly achievable region as special case. We present them both to guide the reader into the two possible cooperation mechanisms.

Superposition-only achievable region
Class of Input Distributions: Consider a distribution from the class that is, conditioned on Q, the random variables (V 1 , U 1 , T 1 , X 1 ) generated at source 1 are independent of the random variables (V 2 , U 2 , T 2 , X 2 ) generated at source 2. The channel transition probability P Y 1 Y 2 Y 3 Y 4 |X 1 X 2 is fixed, while the other factors in the distribution in (6) can be varied. Rate Splitting and Transmission Strategy: .., e nR u0c } is the part of the common message sent cooperatively by the sources, W u0n ∈ {1, ..., e nR u0n } is the part of the common message sent by source u alone (i.e., non-cooperatively), and W uun ∈ {1, ..., e nRuun } is the private private message sent non-cooperatively, with R u = R u0c + R u0n + R uun .
We propose that the cooperative common message sent by a source is decoded at the other source thanks to the generalized feedback. Then, the sources send both cooperative common messages to the receivers as in a virtual MIMO channels, thus realizing the gain of beamforming. This is possible by using regular block Markov superposition encoding [11] at the sources and backward decoding [48] at the destinations. In particular, transmission occurs over a frame of N slots of n channel uses each. Source 1 in slot b, b ∈ {1, · · · , N − 1}, has an estimate W 20c,b−1 of the cooperative common message sent by source 2 in the previous slot. Similarly, source 2 in slot b has an estimate W 10c,b−1 of the cooperative common message sent by source 1 in the previous slot. The random variable Q in (6) conveys the two cooperative common messages (W 10c , W 20c ) from the previous time slot to the destinations. In slot b, b ∈ {1, · · · , N − 1}, the random variables V u , U u , and T u in (6), u ∈ {1, 2}, convey the new cooperative common message W u0c,b , the new non-cooperative common message W u0n,b , and the new non-cooperative private message W uun,b , respectively.
By setting V 1 = V 2 = ∅, i.e., no cooperative common messages, our proposed encoding schemes reduces to the Han and Kobayashi [19] for the IFC without feedback in Th. 3.1. In this case, Q acts as a simple time-sharing random variable. Codebook Generation: Pick uniformly at random e n(R 10c +R 20c ) length-n sequences Q n ([i, j]), i ∈ {1, · · · , e nR 10c } and j ∈ {1, · · · , e nR 20c }, from the typical set .
, pick uniformly at random e nR 10n length-n sequences U n , pick uniformly at random e nR 11n length-n sequences T n The generation of the codebooks at source 2 is similar. Figure 2: A visual representation of the codebook generation for the superposition-only achievable scheme. An arrow to a codebook/random variable indicates that the codebook is superimposed to all the codebooks that precede it, and codebooks linked by a vertical line are conditionally independent given everything that precedes them.
for u ∈ {1, 2}, the transmitted codewords are with the "boundary" conditions W u0c,0 = W u0c,N = 1, u = {1, 2}, i.e., on the first slot of the frame there is no cooperative common information from a previous slot to relay, and on the last slot of the frame there is no new cooperative common information to send because there will not be a future slot to relay it. With this scheme, user u ∈ {1, 2} transmits at an actual rate R u = (1 − 1/N )R u0c + R u0n + R uun < R u (because no new cooperative common information is sent on the last slot). The rate R u can be made arbitrarily close to R u by taking the frame length N to be sufficiently large. Fig. 2 visualizes the proposed superposition coding scheme: an arrow to a codebook/random variable indicates that the codebook is superimposed to all the codebooks that precede it, and codebooks linked by a vertical line are conditionally independent given everything that precedes them. For example, codebook U 1 is superimposed to Q and V 1 , and it is conditionally independent of any codebook with index 2 when conditioned on Q.
Cooperation: In slot b, b ∈ {1, · · · , N − 1}, we can assume that the users' estimate of the previous cooperative common messages is exact, that is, W 10c,b−1 = W 10c,b−1 and W 20c,b−1 = W 20c,b−1 , since the total average probability of error at the receivers can be upper bounded by the sum of the decoding error probabilities at each step, under the assumption that no error propagation from the previous steps has occurred [48]. Next we describe how source 2 cooperates with source 1. Source 1 proceeds similarly.
Source 2 at the end of slot b decodes user 1's new cooperative common message W 10c,b carried by V n 1 from its channel output Y n 2,b , knowing everything that was generated at source 2 at the beginning of the slot. Formally, at the end of slot b, b ∈ {1, · · · , N − 1}, source 2 has received Y n 2,b and looks for the unique index i ∈ {1, ..., e nR 10c } such that where the dots indicate known message indices, where all that is known at source 2 is represented by and where If none or more than one index i is found, then source 2 sets i = 1; in this case we say that an error has occurred at source 2.
Error Analysis: By standard arguments [45] (see Appendix B), the probability of error at source 2 can be made as small as desired if Decoding: The destinations wait until the last slot of the frame (i.e. slot N ) has been received and then perform backward decoding. In slot b ∈ {N, · · · , 1} destination 1 looks for the unique triplet (i 1 , j 1 , m 1 ) ∈ {1, ..., e nR 10c }×{1, ..., e nR 10n }× {1, ..., e nR 11n } and some pair (i 2 , j 2 ) ∈ {1, ..., e nR 20c } × {1, ..., e nR 20n } such that where the pair (W 10c,b , W 20c,b ) was decoded in the previous step (W u0c,B = 1 by assumption, hence W u0c,B = 1 too) and where In words, destination 1 decodes the old cooperative common messages in Q n , the current non-cooperative common messages in (U n 1 , U n 2 ), and the current noncooperative private message in T n 1 , from its channel output Y n 3,b . The current cooperative common messages in (V n 1 , V n 2 ) are known from the decoding of slot b + 1. The current non-cooperative private message of user 2 in T n 2 is treated as noise. If none or more than one triplet (i 1 , j 1 , m 1 ) is found, then destination 1 sets (i 1 , j 1 , m 1 ) = (1, 1, 1); in this case we say that an error has occurred at destination 1. Error Analysis: By standard arguments [45] (see Appendix C), the probability of error at destination 1 can be made as small as desired if By similar arguments, the probability of error at source 1 can be made as small as desired if and the probability of error at destination 2 can be made as small as desired if Achievable region: The intersection of the region in (7) with the region in (8) can be compactly expressed after Fourier-Motzkin elimination as follows: Theorem 4.1. For any distribution in (6), the following region is achievable: Without loss of generality, one can take X 1 = T 1 and X 2 = T 2 in (9).
We remark here that the proposed structured way of superimposing the codebooks greatly simplifies the error analysis. Our codebook "nesting", in fact, is such that the "cloud center" codebook is the one all terminals will be decoding, i.e., the cooperative common coodebok, to which we superimposed the noncooperative common codebook (to be decoded by the two destinations but not by the other source) and finally we superimposed the non-cooperative private codebook (to be decoded at the intended receiver only). As a consequence, although a destination has to decode five messages, only 5 out of the possible 2 5 − 1 = 31 error events matter (see (7) for destination 1 and (8) for destination 2).
Remark 4.2. The following rate constraints also appear after Fourier-Motzkin elimination: It can be shown (see Appendix A) that (10) and (11) can be removed without enlarging the region in (9). The intuitive argument is as for the channel without feedback in Remark 3.2.
2. By setting Y 1 = Y 3 and Y 2 = Y 4 we obtain an IFC with output feedback as studied in [24,25,43]. In particular, the region in [24, eq.(18)-(29)] has the same codebook structure of our Th. 4.1. However, they differ in the encoding and decoding of the messages in Q. In our achievable region, the sources repeat in Q the whole past cooperative common messages. In [24], the sources repeat in Q a quantized version of the past cooperative common message indices. In principle, thus the encoding in [24] is more general. However, in our achievable region, the destinations decode Q jointly with all other messages. In [24], Q is decoded first by treating all the rest as noise, and then all the other messages are jointly decoded. It is thus not clear a priori whether the rate-saving due to sending a quantized version of Q are wiped out by the low rate imposed by decoding Q first. A formal comparison among the two regions is however difficult, since the two could appear different but be actually the same when the union over all possible input distributions is taken.
3. By setting (7a) = ∞, and (8a) = 0 in (9), we obtained a cognitive interference channel, in which source 2 knows the message of source 1, while source is unaware of the messages sent by source 2. The cognitive channel has also been referred to as IFC with degraded message set [51] and as IFC with unidirectional cooperation [31].
With (7a) = ∞, and (8a) = 0 (and with U 1 = V 1 = V 2 = Q without loss of generality) the achievable region in (9) reduces to: The region in (12) is only a subset of the best known achievable region for a cognitive IFC by Rini et at [38] because the region in (9) does not use binning.
4. By setting (7a) = (8a) = ∞ (and with U 1 = V 1 = U 2 = V 2 = Q without loss of generality) in (9), we obtain the achievable region with superposition-only for a broadcast channel (BC), namely The region in (13) is only a subset of the largest known achievable region for a general BC by Marton [32] because the region in (9) does not use binning. The region in (13) is however optimal for the case of "more capable BC channels" [16] and for the case of "BC with degraded message set" [23].
6. The region in (14) is for a MAC-GF "without common message". The case with common message, that is, a message W 0 available at both sources and to be decoded at both destinations, can be easily incorporated by having the codebook/random varaible Q also carry the common message W 0 . If the rate of the common message W 0 is R 0 , the region in (14) must be modified as follows: the rate constraint (14c) becomes This trick (i.e., the random variable Q carries the common message) can be used whenever a common message has to be included in the IFC-GF setting. In particular, with a common message, our Th. 4.1 must be modified as follows: the left hand side of the inequalities in (7f) and (8f) must also include the rate of the common message.
7. Further setting R 2 = 0 in (14) gives which is the achievable rate for a full-duplex relay channel with partial decode and forward. The above rate does not include the case of Compressand-Forward [10].
8. Channels with conferencing encoders are also a special case of GF. A twosource conferencing model [48] assumes that there are two non-interferring, noise-free channels of finite capacity between the communicating nodes, one for each direction of communication. Let C ij be the capacity of the conferencing channel from node j to node i. Following [29] and with some abuse notation, the conferencing model is captured as follows. Let the inputs be X 1 = [F 1 ; X 1 ] and X 2 = [F 2 ; X 2 ], where F 1 and F 2 have alphabet sizes log(C 12 ) and log(C 21 ), respectively. Further set Y 1 = F 2 and Y 2 = F 1 and define the channel transition probability to be In this model, the choice V 1 = F 1 and V 2 = F 2 gives (7a) = C 21 and (8a) = C 12 is capacity achieving [48].
it is show that the region in Th. 4.1 is sum-rate optimal to within 18 bits for Gaussian channels with independent noises and symmetric cooperation links when the gain of the cooperation links are smaller than the gain of the interfering links.
In the same work, it is show that when the gain of the cooperation links are larger than the gain of the interfering links, then the transmitters should decode more information from their received generalized feedback signal than they will actually use for cooperation. In our setting this amounts to: at the end of slot b, b ∈ {1, · · · , N − 1}, source 1 looks for a unique index i ∈ {1, ..., e nR 20c } and some index j ∈ {1, ..., e nR 20n } such that the sequences where the dots indicate known message indices, where all that is known at source 2 is represented by Decoding is successful with high probability if Notice that the constraint in (15) However, the constraint in (15) constrains R 20n to satisfies R 20n ≤ I( while the constraint in (8a) does not constrain R 20n at all. It is not clear at priori which cooperation strategy is better, i.e., whether (8a) or (15). We will show next-as intuition suggests-that the two are equivalent, that is, with superposition-only, the sources should relay to the destinations all the common information they have acquired through the generalized feedback.
Corollary 4.4. After FM elimination of the regions in (7) and (8) with (8a) replaced by (15), we get It can be easily verified that the region in (16) is the same as region (9) , in the case of no feedback this choice corresponds to sending only private information for user 2). Hence, requiring source 1 to decode more information than actually used for cooperation does not enlarge the achievable region in (9).
Along the same line of reasoning, one could also require that at the end of slot b, b ∈ {1, · · · , N − 1}, source 1 looks for a unique indices i ∈ {1, ..., e nR 20c }, and some pair of indices j ∈ {1, ..., e nR 20n } and k ∈ {1, ..., e nR 22n }, such that the sequences where P (enc1) Decoding is successful if The constraint in (17) can be too restrictive for rate R 2 when the cooperation link is weak. Indeed, consider the extreme case where Y 1 is independent of everything else (i.e., unilateral cooperation), then the constraint in (17) implies R 2 = 0, which can be easily beaten by ignoring the generalized feedback.

Superposition & binning achievable region
Because the achievable region with superposition-only does not reduce to the largest known achievable region when the IFC-GF reduces to a cognitive channel or a broadcast channel, we now introduce binning in the superposition only achievable scheme. In this new achievable scheme, the sources also cooperate in sending part of the private messages. Each message is divided into four parts: two common messages and two private messages. The sources cooperate in sending one part of the common messages and one part of the private messages. Communication again proceeds on a frame on N slots. In any given slot, the sources decode the cooperative messages from their GF signal; these message are then relayed in the next slot. Since the common messages are decoded at both destinations, the sources cooperate by forwarding the cooperative common messages to the destinations as in a virtual MIMO channel. On the other hand, the private messages are decoded at the intended destination only and treated as noise at the non-indened destination. In this case, a source treats the other source's cooperative private message as "noncausally know interference" in the next slot. Cooperation is then in the form of repetition/forwarding for one destination and pre-coding/binning for the other destination. The details of our proposed superposition & binning scheme are as follows.
Class of Input Distributions: Consider a distribution from the class that is, conditioned on (Q, S 1 , S 2 ), the random variables (V 1 , U 1 , T 1 , Z 1 , X 1 ) generated at source 1 are independent of the random variables (V 2 , U 2 , T 2 , Z 2 , X 2 ) generated at source 2. The channel transition probability P Y 1 Y 2 Y 3 Y 4 |X 1 X 2 is fixed, while the other factors in the distribution in (18) can be varied. The random variables S u and Z u , u = {1, 2}, which did not appear in (6), convey the previous and the new, respectively, cooperative private information in a block-Markov encoding scheme. Codebook Generation: From the input distribution in (18), compute the marginals P V 1 U 1 T 1 |Q and P V 2 U 2 T 2 |Q (i.e., drop the dependance on (S 1 , S 2 )), and construct codebooks (Q n , V n 1 , U n 1 , T n 1 , V n 2 , U n 2 , T n 2 ) as described in Section 4.1. From the input distribution in (18), compute the marginals P S 1 |Q and P S 2 |Q . . Similarly, generate a codebook S n 2 (k 2 , [i, j]) by picking uniformly at random length-n sequences from the typical set T (n) (P S 2 |Q |q n ([i, j])). The range of the index k 2 will be specified later.
From the input distribution in (18), compute the the marginal , generate a codebook Z n 1 (m 1 , 1 , k 1 , [i, j]) by picking uniformly at random lengthn sequences from the typical set ). The range of the indices m 1 will be specified later. Similarly, but with the role of the users swapped, construct a codebook Z n 2 (m 2 , 2 , k 2 , [i, j]). Finally, for each set of codewords (Q n , S n 1 , S n 2 , V n 1 , U n 1 , T n 1 , Z n 1 ) = (q n , s n 1 , s n 2 , v n 1 , u n 1 , t n 1 , z n 1 ) (we omit here the list of indices for sake of space) pick uniformly at random one sequence X n 1 from the typical set T (n) (P X 1 |QS 1 S 2 V 1 U 1 T 1 Z 1 |q n , s n 1 , s n 2 , v n 1 , u n 1 , t n 1 , z n 1 ). Similarly, but with the role of the users swapped, construct a codebook X n 2 . Fig. 3 visualizes the proposed codebook generation (the convention is the same used for Fig. 2). The class of input distributions in (18) however allows for codebooks as depicted in Fig. 4. With binning we will force a codebook generated as in Fig. 3 to look like a codebook generated as in Fig. 4.
In order to complete the generalization of the scheme in Section 4.1, we must , where W xyz ∈ {1, · · · , e nRxyz } represents a message index, and B xyz ∈ {1, · · · , e nR xyz } represents a "bin index". Notice that each bin index B xyz has the same subscript of the corresponding message index W xyz and has rate R xyz (i.e., notice the prime in the superscript). The only exception is for S 1 and S 2 where the rate of the bin index is indicated with a double prime as a superscript, that is, R 11c and R 22c , so as not to confuse them with R 11c in Z 1 and R 22c in Z 2 . Encoding: We can assume correct decoding of the message indices at the sources' side at the end of slot b − 1 (no error propagation), i.e., W 10c,b−1 = W 10c,b−1 (carried by V n 1 and to be repeated in Q n ), W 11c,b−1 = W 11c,b−1 (carried by Z n 1 and to be repeated in S n 1 ), W 20c,b−1 = W 20c,b−1 (carried by V n 2 and to be repeated in Q n ), W 21c,b−1 = W 21c,b−1 (carried by Z n 2 and to be repeated in S n 1 ), since the total average probability of error can be upper bounded by the sum of the decoding error probabilities at each step, under the assumption that no error propagation from the previous steps has occurred [6,54].
The encoding process at the beginning of slot b consists of the following binning and superposition steps, whose purpose is to allow the most general possible class of input distributions: • Binning codebooks S n 1 and S n 2 against each other. At the beginning of slot b, given the past messages where the dots are in place of the know messages [W 10c,b−1 , W 20c,b−1 ] from the previous slot. If more than one pair is found, then source 1 chooses one at random. If the search fails, source 1 sets (b 11c,b−1 , b 22c,b−1 ) = (1, 1); in this case we say that an error has occurred at source 1.
Error analysis. The codewords (Q n , S n 1 , S n 2 ) were sampled in an i.i.d. fashion from the distribution P QS 1 S 2 = P Q P S 1 |Q P S 2 |Q . The encoding process "forces" them to actually look as if they were sampled in an i.i.d. fashion from the distribution P Q P S 1 S 2 |Q . For that to be feasible with high probability we must have (see Appendix D) This encoding step is the same as the encoding in Marton's achievable region for a general two-user broadcast channel with common message [32].
This first encoding step is run in parallel at both sources, so that the two sources have the same set of past cooperative messages (W 10c,b−1 , W 20c,b−1 , W 11c,b−1 , W 22c,b−1 ), and of bin indices (B 11c,b−1 , B 22c,b−1 ). This "common knowledge" furnishes the basis for cooperation in slot b, where can be treated as "non-causally known interference" at source 1, and can be treated as "non-causally known interference" at source 2.
• Joint conditional binning: Given the new messages (W 10c,b , W 10n,b , W 11n,b ), source 1 tries to find a set of bin indices where the dots are in place of the know previous message [W 10c,b−1 , W 20c,b−1 ]. If more than one triplet is found, then source 1 chooses one at random. If the search fails, source 1 sets (b 10c,b , b 10n,b , b 11n,b ) = (1, 1, 1); in this case we say that an error has occurred at source 1.
This encoding steps is a generalization of the "sequential binning" idea introduced in [30]. Here, instead of doing several sequential binning steps, we bin all the codewords at once.
Error analysis. The triplet (Q n , S n 1 , S n 2 ) found in the previous encoding step, appears jointly typical according to P QS 1 S 2 . The set of codewords (Q n , V n 1 , U n 1 , T n 1 ) is jointly typical according to P QV 1 U 1 T 1 by construction. However, codewords (V n 1 , U n 1 , T n 1 ) and (S n 1 , S n 2 ) were generated independently conditioned on Q n . The purpose of this binning step is to make the whole set (Q n , S n 1 , S n 2 , V n 1 , U n 1 , T n 1 ) to look jointly typical according to P QS 1 S 2 V 1 U 1 T 1 . By standard arguments, similar to those used in Multiple Description Coding [36] (see Appendix E), the joint binning step is successful with arbitrary high probability if The rate constraint in (20a) can be understood as follows. After the first (successful) binning step, the codewords (Q n , S n 1 , S n 2 , V n 1 ) look as if they sampled from the distribution P Q P S 1 S 2 |Q P V 1 |Q . The encoding step requires them to look as if they were sampled from the distribution P Q P S 1 S 2 |Q P V 1 |QS 1 S 2 ; hence we need to be able to search among an exponential (in n) number of codewords V n 1 , whose exponent must be at least H(V 1 |Q)−H(V 1 |QS 1 S 2 ) = I(V 1 ∧ S 1 , S 2 |Q). The rate constraints in (20b) and in (20c) have a similar interpretation.
• Final binning step: Given the new messages W 11c,b , source 1 tries to find a bin index b 11c,b such that Q n (· · · ), S n 1 (· · · ), S n 2 (· · · ), V n 1 (· · · ), U n 1 (· · · ), T n 1 (· · · ), where the dots are in place of the know messages and bin indices. If more than one index is found, then source 1 chooses one at random. If the search fails, source 1 sets b 11c,b = 1; in this case we say that an error has occurred at source 1.
Error analysis. The set (Q n , S n 1 , S n 2 , V n 1 , U n 1 , T n 1 ) found from the previous encoding steps, appears jointly typical according to P QS 1 S 2 V 1 U 1 T 1 . By construction, (Q n , S n 1 , V n 1 , Z n 1 ) are jointly typical according to P QS 1 V 1 Z 1 , that is, conditioned on (Q, S 1 , V 1 ), Z 1 is independent of (S 2 , U 1 , T 1 ). The purpose of this binning step is to make the whole set jointly typical according to P QS 1 S 2 V 1 U 1 T 1 Z 1 . By standard arguments (see Appendix E), this binning step is successful with arbitrary high probability if (20d) • Finally, source 1 sends a codeword X n 1 that is jointly typical with all the sequences found in the previous binning steps.
Encoding at source 2 proceeds similarly.
Cooperation: If the encoding steps are successful at both sources, all the transmitted and received signals are jointly typical according to the distribution in (18).
At the end of slot b, source 1 knows all the messages generated at source 1 at the beginning of the slot, including (Q n , S n 2 ) (because we can assume successfully decoding of all past cooperative messages). Source 1 then searches for a unique pair of codeword indices (i, j) and some bin index , where all that is known at source 1 is represented by where the dots indicate known old cooperative messages and related bin indices, and where T2 S1 Z1 S2 Z2 If the search fails, source 1 sets (i, j) = (1, 1); in this case we say that an error has occurred at source 1. Error analysis. From the point of view of source 1, this decoding step is equivalent to decoding the two codewords V n 2 ([W 20c,b , B 20c,b ], · · · ) and Z n 2 ([W 22c,b , B 22c,b ], · · · ) in a MAC-like channel with output Y n 1,b and state X n 1 known at the receiver only, similar in spirit to [50]. Decoding at source 1 is depicted in Fig. 5 where the variables circled in blue are to be decoded, and the ones circled in red are treated as noise (the rest is known). By standard arguments (see Appendix F), decoding is correct with high probability if with Intuitively, the constraints in (21) are a consequence of the following observations. Conditioned on (Q, S 1 , S 2 ), a wrong V 2 looks sampled from P V 2 |QS 1 S 2 but it was actually sampled from P V 2 |Q ; this accounts for the term I(V 2 ∧ S 1 , S 2 |Q). Similarly, conditioned on (Q, S 1 , S 2 ), a wrong Z 2 looks sampled from P Z 2 |QS 1 S 2 V 2 but it was actually sampled from P Z 2 |Q,S 2 ,V 2 ; this accounts for the term I(Z 2 ∧ S 1 |Q, S 2 , V 2 ).
The inequalities in (21) generalizes the one in (7a), and reduce to (7a) when Decoding at source 2 proceeds similarly. Decoding: The receivers wait until the last slot has been received, and then proceed to decode by using backward decoding. We can assume that when decoding the information sent in slot b, the decoding of the information sent in the slots b+1, · · · , N was successful [6,48]. When decoding slot b, destination 1 knows the current cooperative messages (W 10c,b , W 20c,b , W 11c,b ) carried by (V 1 , Z 1 , V 2 ), and tries to decode the previous cooperative common messages (W 10c,b−1 , W 20c,b−1 ) in Q, the previous cooperative private message W 11c,b−1 in S 1 , and the current non-cooperative messages W 10n,b in U 1 , W 20n,b in U 2 , and W 11n,b in T 1 . Decoding at destination 1 is depicted in Fig. 6 where the variables circled in blue are those whose message index is known (but the bin index is not), and the ones circled in red are treated as noise; the rest is to be decoded.
Formally, destination 1 tries to find a unique set of message indices (q 1 , q 2 , s 1 , u 1 , u 2 , t 1 ) and some bin indices where P (dec1) and where, without loss of generality, we have assumed that the known messages have index one. Notice that the above expression for P (dec1) T2 S1 Z1 S2 Z2 Figure 6: Decoding at destination 1: the variables whose message index is known (but the bin index is not) are circled in blue, the variables that are treated as noise are circled in red, the remaining variables are to be decoded.
The error analysis can be found in Appendix G. The probability of error at destination 1 can be made as small as desired if the following rate constraints are satisfied: 6 } (22c) 14 , E 16 , E 17 , E 20 , E where the rates R , ∈ {Q, V 1 , U 1 , T 1 , S 1 , Z 1 , V 1 , U 2 , T 2 , S 2 , Z 2 }, and the quantities E (1) , ∈ {0, ..., 27}, are defined in Appendix G. Similarly, the rate constraints at destination 2 are as in (22) but with the role of the users swapped, Achievable region: The achievable region with superposition & binning as a function of R 1 and R 2 only, can be obtained by applying the Fourier-Motzkin elimination procedure to the intersection of (19), and (20), (21), (22), and the regions corresponding to (20), (21), (22) but with the role of the users swapped. However, the rates constraints are expressed as the minimum of several quantities that we do not report it here for sake of space. We note that when the binning rates are taken to satisfy the constraints in (20) and in (21) with equality for both users, the achievable region has five types of rate bounds as for the non-feedback case, i.e., for R 1 , for R 2 , for R 1 + R 2 , for 2R 1 + R 2 , and for R 1 + 2R 2 .
As for the case of superposition-only, the error analysis for the case of binning & superposition is greatly simplified by the structured way we performed superposition. In particular, only 28 error events matter out of the 2 8 −1 = 255 possible that result from the joint decoding of 8 messages.
Remark 4.5. In [53], we constructed the codebooks as depicted in Fig. 7. The difference with respect to the encoding proposed in this paper is that Z 1 was superimposed to S 2 too (which carries the private message from source 2-sent Q V1 V2 U1 U2 T1 T2 S1 Z1 S2 Z2 Figure 7: A visualization of the codebook generation proposed in [53]. cooperatively by source 1 too-but not decoded at destination 1), and Z 2 was superimposed to S 1 too. Thus, with the encoding of [53], Z 1 could not be decoded at destination 1, since its decoding implies the decoding of all messages to which Z 1 is superimposed, thus also S 2 ; but S 2 is a private message that must not be decoded at destination 1. Similarly, Z 2 could be decoded at destination 2.
With the encoding proposed in [53], the rate constraint in (20d) should be replaced by and the rate constraints in (21) should be replaced by where the term I(Z 2 ∧ S 1 |Q, S 2 , V 2 ) in (21) does not appear in (24) since Z 2 is superimposed to S 1 by construction (thus it already has the desired joint distribution). In other words, the encoding of [53] is less stringent in terms of "binning rates constraints" but it is more stringent in terms on "decoding rate constraints". However, these two effects do compensate one another. Indeed, from (24) and (23) we have: which is the same we obtain from (21) and (20d). The two schemes are not the same. With the encoding proposed in this paper, the codeword in Z 1 and Z 2 can be decoded at the corresponding destination. This improves on the performance since now the Z's do not longer act as noises at the intended destination.
We showed in the previous section that the achievable region with superpositiononly in (9)  The reason why our superposition & binning region does not comprises the region in [38] is as follows. Assume source 1 is the cognitive user and source 2 is the primary user. Since the primary user is unaware of the message of the cognitive user, we need to set S 1 = V 1 = Z 1 = ∅.
Since there is not part of the primary user's message that is not available at the cognitive user, we must set Z 2 = V 2 = U 2 = T 2 = ∅. With these choices, our encoding scheme only uses (Q, U 1 , T 1 , S 2 ) and is equivalent to the scheme in [38] with U 2pb = ∅ (U 2pb in [38] carries part of the message of the primary user that is only sent by the cognitive user; this feature is not present in our encoding scheme.) 3. When the IFC-GF channel reduces to a relay channel, our region with superposition & binning does not seem to include the compress-and-forward relaying strategy.

Example: the Gaussian IFC-GF
In this section we provide an evaluation of our superposition-only achievable region for the Gaussian channel. We will provide an evaluation of our superposition & binning achievable region, as well as, a comparison with outer bounds, in the second part of this paper. We assume full duplex communication, perfect channel state information at all terminals, and an average power constraint on the inputs. A Gaussian channel in standard form has outputs: We assume that the additive noises on the different channels are independent (the case of correlated noises will be discussed in the second part of this paper). Without loss of generality we assume that the direct link channel gains h 31 and h 42 are real-valued since the destinations can compensate for the phase of the intended signal. Similarly, we assume that the cooperation link channel gains h 21 and h 12 are also real-valued. As opposed to the case without GF, the phase of the interfering link channel gains h 32 and h 41 matter because of transmitter cooperation.
In the following we are going to consider jointly Gaussian inputs only when evaluating the achievable region in Th. 4.1. Without loss of generality, let Q ∼ N (0, 1) and let 10n, 11n, 20c, 20n, 22n} are independent random variables whose variances satisfy The right hand side of the rate bounds in region (7)  and similarly for the other user. Notice that, conditioning on Q removes the dependency between X 1 and X 2 . The cooperation gain shows in eq. (7f) (where instead of |h 31 α 1 | 2 + |h 32 α 2 | 2 one has |h 31 α 1 + h 32 α 2 | 2 ) and in equation (7a). The private message X 22n (X 11n ) acts as noise for destination 1 (destination 2). For the purpose of numerical example, we consider a symmetric network where, in a two dimensional Cartesian place with x ≥ 0 and y ≥ 0, source 1 is in position (−x/2, −y/2), source 2 is in position (−x/2, +y/2), destination 1 is in position (+x/2, −y/2), and destination 2 is in position (+x/2, +y/2). Both users have the same power constraint P and the channel gains are inversely proportional to the distance between the terminals, that is, h 21 = h 12 = h 34 = h 43 = 1/y, h 31 = h 13 = h 24 = h 42 = 1/x and h 41 = h 14 = h 23 = h 32 = 1/ x 2 + y 2 . Fig. 8 shows the performance of our superposition-only scheme and compares it with the case without generalized feedback, for the case P 1 = P 2 = 6 and x = 2 and y = 1. It can be seen that great rate improvements are possible thanks to cooperation, when compared to the case without GF. For example, the maximum rate for a given user improves from 1.3 bit/sec/Hz to 1.9 bit/sec/Hz (1.9=1.3×(1+0.46), i.e., 46% improvement), while the sum-rate improves from 1.7 bit/sec/Hz to 2.2 bit/sec/Hz (2.2=1.7×(1+0.29) , i.e., 29% improvement).

Conclusion
In this paper we presented an achievable region for a general IFC-GF. We built on the idea of message splitting into common and private messages and proposed a coding scheme where the sources cooperate to send part of the two messages. The cooperation in sending the common message aims to realizing the gains of beam-forming, as in a distributed multi-antenna system, while the cooperation in sending the private message aims to leverage the interference "pre-cancellation" property of dirty-paper-type coding. We showed that our achievable region generalizes several known achievable regions for IFC-GF and that it reduces to known achievable regions for some of the channels subsumed by the IFC-GF model. Numerical results show that cooperation can improve the achievable rate of all the involved sources. In the second part of this paper, we will derive an outer bound for a general IFC-GF and use to assess the performance of our proposed achievable strategy.
[28] G. Kramer. Outer bounds on the capacity of gaussian interference channels.
[31] I. Maric, R. D . Yates, and G. Kramer A Proof of the redundancy of two single-rate constraints that is, source 1 does not send any common information.
the achievable region in (9) reduces to: where a prime as a superscript indicates that the mutual information in the corresponding equation must be computed for the distribution . Notice that all the mutual informations in (7) are larger under Consider the region in (9) (under P QV 1 U 1 T 1 X 1 V 2 U 2 T 2 X 2 ). If } then the rate constraint in (10) is redundant and can be omitted from the region in (9). We will now show that the rate constraint in (10) can always be omitted from the region in (9) without enlarging the achievable region. We will do so by showing that the rate points for which the rate constraint in (10) is violated, that is, when holds together with all the rate constraint in (9), are contained in the region in (25) . The region in (25) is a special case of the region in (9) for which the rate constraint in (10) is redundant. This shows that the region in (9) is indeed achievable. Assume now that (26) holds together with all the rate constraint in (9) (under P QV 1 U 1 T 1 X 1 V 2 U 2 T 2 X 2 ). We will show that that (26) and (9) imply (25). We have: (25a) = (9b). Moreover . This concludes the proof.
B Proof of (7a) and of (8a) At the end of slot b, b ∈ {1, · · · , N − 1}, transmitter 1 has received Y n 1,b and looks for the unique index i ∈ {1, ..., e nR 20c } such that the sequences where the dots indicate known message indices, and where all that is known at transmitter 1 is represented by X n 1 = (Q n , V n 1 , U n 1 , T n 1 , X n 1 ).
If none or more than one index i ∈ {1, ..., e nR 20c } are found, then transmitter 1 sets i = 1. Assume message i = 1 was sent. An error occurs when transmitter 1 declares i = 1 in (27), which occurs with probability because V 2 and Y 1 are independent conditioned on Q for any i = 1. The error probability goes to zero if (8a) holds, where O( ) denotes a function of that goes to zero when → 0. Similarly, we can prove (15) and (17) as follows. We only give the proof for (15). Assume i = 1 was sent. An error occur if the search for , results in an i = 1. Thus an error occurs with probability because (V 2 , U 2 ) and Y 1 are independent conditioned on Q for any i = 1. Hence, the probability of error vanishes as the block-length increases if (15) holds.
C Proof of (7) and (8) For the error analysis, we consider only the probability of error in each block as the total average probability of error can be upper bounded by the sum of the decoding error probabilities at each step, under the assumption that no error propagation from the previous steps has occurred [6,54]. Receiver 1 looks for the unique triplet (q 1 , u 1 , t 1 ) and some pair (q 2 , u 2 ) such that the sequences where (W 10c,b , W 20c,b ) were decoded exactly in the previous step. Let E q 1 q 2 u 1 u 2 t 1 be the event that the sequences in (29) are strongly jointly typical. Assume that (q 1 q 2 u 1 u 2 t 1 ) = (11111) was sent. The total probability of error at receiver 1 can be bounded as where all probabilities are conditioned on the event that (q 1 q 2 u 1 u 2 t 1 ) = (11111) was sent.
The probability of the event E c 11111 vanishes because the transmitted codewords are jointly typical with the received sequence with high probability.
The developed analysis can be summarized as in Table 1. In Table 1 the symbols "1", "0" and " " have the following meaning. A "1" indicates that the message index is in error. A "0" indicates that the message index is correct. A " " indicates that it does not matter whether the message index is in error; this is so because of superposition coding; in this case in fact, the codeword selected by the decodereven though with the correct message index-is superimposed to a wrong codeword and it is thus independent of the received signal. In case of a " ", the factorization Table 1: Error events at destination 1.
of the joint probability needed for the evaluation of the probability of error is as for the case where the message is wrong; this implies that the error event that gives the most stringent rate bound is that for which the message is wrong (i.e., as far as error bounds are concerned, a " " is equivalent to a "1"). The second to last column in Table 1 counts how many error events are included in the corresponding row (i.e., each " " corresponds to two possible cases), and the last column lists the elements of the sect C, where C is the set of correctly decoded codewords.

D Proof of (19)
The probability that encoder 1 fails to find a good pair of indices B 11c,b−1 = i, which goes to zero as n → ∞ if (19) holds, where where O( ) → 0 as → 0.

E Proof of (20)
Encoding fails if for all set of indices (B 10c,b , B 10n,b , B 11n,b ) can be found no triplet (V n 1 , U n 1 , T n 1 ) can be found to be jointly typical with (Q n , S n 1 , S n 2 ). The probability of this event can be bounded as and 1 {A} is the indicator function that equals one whenever the condition in A is true.
The mean of the random variable K is easily lower bounded as |T n (P Q,S 1 ,S 2 ,V 1 ,U 1 ,T 1 |Q n , S n 1 , S n 2 )|P V n and upper bounded as We now evaluate A and B. We have, neglecting the terms that go to zero as → 0, and e −nA = Pr[T n 1 ∈ T n (P Q,S 1 ,S 2 ,V 1 ,U 1 ,T 1 |Q n , S n 1 , S n 2 , V n 1 , U n 1 )] ≤ e nH(T 1 |Q,S 1 ,S 2 ,V 1 ,U 1 )−nH(T 1 |Q,V 1 ,U 1 ) ≤ e −nI(T 1 ∧S 1 ,S 2 |Q,V 1 ,U 1 ) .
After having evaluated A and B, we have that goes to zero as n → ∞ if (20) holds.

F Proof of (21)
Let where all that is known at transmitter 1 is represented by X n 1 = (Q n , S n 1 , S n 2 , Z n 1 , V n 1 , U n 1 , T n 1 , X n 1 ).
Assume that (i, j, b i , b j ) = (1111) was sent. The probability that the estimate of (j, i) = (W 20c,b , W 22c,b ) is wrong is bounded by where all probabilities are conditioned on (i, j, b i , b j ) = (1111) being sent. The probability of E c 1111 is vanishing as n → ∞ because the transmitted codewords are jointly typical with the received signal with high probability.
For the other three terms we have: if i > 1, j > 1, i.e., when V n 2 is wrong then whether Z n 2 is correct or wrong does not change the distribution to use in the error events and the most string error bound is for the case where both are wrong; thus we have i>1,j>1 since by construction V 2 and Z 2 are independent conditioned on Q and Z 2 is superimposed to (S 2 , V 2 ). This probability can be driven to zero if (21b) holds.
Finally, if i > 1, j = 1, i.e., V n 2 correct and Z n 2 wrong, we have since now the V 2 has the marginal imposed by the binning step during the encoding process. This probability can be driven to zero if (21a) holds.

G Proof of (22)
In slot b, b = N, N − 1, ..., 1, destination 1 tries to find a unique set of message indices (q 1 , q 2 , s 1 , u 1 , u 2 , t 1 ) and some bin indices Notice that, given (Q, S 1 ) the input variables for source 1 are not independent of the input variables for source 2.
The possible error events are listed in Table 2. In Table 2 the symbols "1", "0" and " " have the following meaning. A "1" indicates that either the message index or the bin index are in error. A "0" indicates that both the message index and the bin index are correct. A " " indicates that it does not matter whether the message index is in error; this is so because of superposition coding; in this case in fact, the codeword selected by the decoder-even though with the correct message index-is superimposed to a wrong codeword and it is thus independent of the received signal. In case of a " ", the factorization of the joint probability needed for the evaluation of the probability of error is as for the case where the message is wrong; this implies that the error event that gives the most stringent rate bound is that for which the message is wrong (i.e., as far as error bounds are concerned, a " " is equivalent to a "1"). The second to last column in Table 2 Q V1 V2 U1 U2 T1 S1 Z1 counts how many error events are included in the corresponding row (i.e., each " " corresponds to two possible cases).
There are several groups of error events in  27 : both S 1 and Z 1 are correct. Notice that, because of the way codebooks are superimposed, out of the possible 2 8 − 1 = 255 error events, only 28 events matter. A way to understand the error events listed in Table 2 is a follows. From destination 1's perspective, given Q, there are three "super-codebooks" to decode. Conditioned on Q, each "super-codebook" is the superposition of one or more codebooks; each "super-codebook" is represented as a separate line in Fig. 9.
Decoding proceeds as for a multiple access channel. In particular, we need to consider all possible combinations of events that consist of jointly decoding a set of messages from the first column of Fig. 10 and a set of messages from the second column of Fig. 10 and a set of messages from the third column of Fig. 10 (even though not all combinations are actual errors for destination 1). In considering such "joint-decoding events", the messages that do not appear in the "set of jointly decoded messages" must be considered as correctly decoded and stripped form the received signal, as in a standard multiple access channel.
The last column in Table 2 is used as follows. Let X be the set of transmitted V2 U1 U2 S1 Z1   T1  T1  T1 U1 V1  Z1  U2 and and 0 0 0 codewords (we do not write here the superscript n that indicates the block-length in order to have a lighter notation), and X be the set of decoded codewords. Let C be the subset of the correctly decoded message indices such that X(C) = X (C) (recall that with superposition coding, the decoder might select a codeword X that is different from the transmitted codeword X but with same message index; this happens when an error is committed on one of the "base layer" codewords). The last column of Table 2 lists the elements of C, i.e., C contains the codewords that have a "0" in the corresponding row. The sets C are important for the factorization of the joint probability needed for the evaluation of the probability of error. The error analysis proceeds as follows. The joint distribution of the decoded codewords and the received signal is X (C c )|X(C) P X(C)Y , where P is a distribution from the set of possible input distributions in (18) and P (g) is computed from P as described in the codebook generation paragraph in Section 4.2, that is, where all the factors of P (g) are obtained from the corresponding marginalization of P . In the following, we shall drop the prime superscript to distinguished between the wrongly decoded codewords and the transmitted codewords. We will add a superscript "(g)" to the symbol for entropy to indicate that the entropy must be evaluated by using the distribution P (g) ; the symbol for entropy without any superscript indicates that the entropy must be evaluated by using the distribution P .
Destination 1 searches for codewords that are joint typicality with the received signal according to P X(C)X(C c )Y ; however, assuming that the messages in C are correctly decoded and those in C c are wrongly decoded (this is the case that gives the most stringent error bound), the actual joint distribution is P (g) X(C c )|X(C) P X(C)Y . The probability of the error for the messages in C c (neglecting the terms that will eventually be taken to go to zero) is: where R(C c ) is the sum of the rates corresponding to the wrongly decoded messages that are indexed by C c . In the following, for any two distributions P and Q, the notation E[log(P/Q)] stands for the Kullback-Leibler divergence D(P ||Q). Let ∆ (1) ∆ = H (g) (X(C c ), X(C)) − H(X(C c ), X(C)) = E log P X(C c ∪C) We now evaluate ∆ C for all possible error events in Table 2. For E (1) 0 : Q is wrong and hence-because of superposition encoding-the most stringent error event is when the messages carried by Q and all the messages superimposed to Q are wrong. In this case C = ∅ and thus ∆ because in these cases P X(C) = P (g) X(C) . Then we have: 12 : ∆ (1) Q,V 1 ,U 1 ,T 1 ,V 2 ,U 2 = E log 18 : ∆ (1)
In addition to the rate constraints from cooperation among the sources (see (21)), i.e., we have the following rate constraints arising from decoding at destination 1: and V 1 are correct. In this case, the 9 error events from E (1) 13 to E (1) 21 listed in Table 2 are impossible and the achievable region becomes 15 , E 18 , E 24 } (32c) 20 , E 25 , E 26 } (32d) 27 }, (32e) 10 , E 11 } (32f) with only five rate constraints, as for the case of superposition only. Notice that the rate bound on R U 2 can be removed since an error on U 2 alone is not an error from the point of view of source 1.
• Instead of joint decoding of all the messages, one can perform a two-step decoding as follows. First step: decode Q and S 1 jointly, and then strip them from the received signal. This the first decoding step is successful if Second step: jointly decode all the other messages. For this second step, one only needs to consider the error events from E


extfieldsofstudy:
Computer Science
Medicine

text:
Frequency shifting approach towards textual transcription of heartbeat sounds

Auscultation is an approach for diagnosing many cardiovascular problems. Automatic analysis of heartbeat sounds and extraction of its audio features can assist physicians towards diagnosing diseases. Textual transcription allows recording a continuous heart sound stream using a text format which can be stored in very small memory in comparison with other audio formats. In addition, a text-based data allows applying indexing and searching techniques to access to the critical events. Hence, the transcribed heartbeat sounds provides useful information to monitor the behavior of a patient for the long duration of time. This paper proposes a frequency shifting method in order to improve the performance of the transcription. The main objective of this study is to transfer the heartbeat sounds to the music domain. The proposed technique is tested with 100 samples which were recorded from different heart diseases categories. The observed results show that, the proposed shifting method significantly improves the performance of the transcription.

Introduction
Auscultation is the most remarkable approach that has been used in diagnosing many cardiovascular diseases for many years. It still plays an important role in the diagnosis of heart disease. Sounds produced by the heart frequently reflect the structural abnormalities of the heart. Physicians use the stethoscope as a common tool to listen to the heart sounds and make a correct diagnosis. Modern stethoscopes are making the auscultation easier to be done. Despite murmurs and tones are easily distinguished, weak murmurs and below audibility threshold easily disappear in background sound. Analysis of heart sounds and extraction of its audio features would be important towards the development of automatic diagnosis systems. Phonocardiogram (PCG) is a diagram of sonic vibration of heart beats. Most researches used PCG as an audio input of system to apply different techniques of digital signal processing [1][2][3]. Based on characteristics of the audio signals, it is possible to apply various signal processing and modeling approaches. Healthy heart sound includes symmetric cycles and pulse values. In contrary, unhealthy heart sounds are commonly disordered by different unexpected frequencies.
Segmentation is a technique for separating cycles and its pulses [2,3]. Classification of heart sound is another research area that divides heartbeat sounds in different clusters based on their characteristics [1,4,5]. In the similar study, neural network has been used for classification of different heart sounds such as normal, systolic and diastolic murmurs [6]. A high performance localization technique of the first heart sound pulse was proposed in [7]. The localization was performed based on an additional enhancement to improve the accuracy of pulse detection. In our previous study on real-time segmentation [8], a simple segmentation technique using amplitude reconstruction was proposed which divided the heartbeat sound pulses with a high accuracy. However, the limitation was to lose of low-amplitude harmonics.
Automatic music transcription [9][10][11][12] is an approach to process the audio signals to extract the pitch levels that can be notated as musical notes and the music. Most researches in automatic music transcription attempted to increase the accuracy of the transcription to cover different frequency levels [9,11]. Transcription can be applied on heartbeat sounds in order to represent heartbeat sounds with the music notation. In previous studies [13][14][15], heart sounds were represented with MIDI (Musical Instrument Digital Interface) format. A good performance of transcription was illustrated in those studies. For long duration sampling of the heartbeat sounds and developing a biomedical database, text-based formats (i.e. MIDI) are the suitable mediums to convert and store the biomedical signals. Text-based music information retrieval [16,17] allows developing query-based system to highlight various events of heartbeat sounds in particularly. In our previous study [18], music transcription of heartbeat sounds was performed that demonstrated good accuracy for different heart sound samples. We proposed several preparation techniques for de-noising and cleaning heart sound signals in order to use in real-time systems. The results showed that, heart sounds can be represented as musical notation. Since heart sound signals are in very low-frequency domain [19], automatic transcription techniques that are used for music transcription are not suitable for this particular application. Therefore, in order to provide a high accuracy transcription, two methods can be used. The first method is to provide an automatic transcription technique with a new configuration to cover very low-frequency spectrum which requires complex algorithms and several modifications. The second method is to transfer the heartbeat sounds to the frequency that is used by music instruments, which allows utilizing the ordinary music processing methods.
In this paper, we propose a frequency shifting (transferring) method to increase the accuracy of the heartbeat sounds transcription. We modify automatic music transcription methods to be used in specific frequency spectrum. The process begins with a frequency estimation technique using Fast Fourier Transform (FFT), a commonly used technique. Heart sounds are divided in several parts with similar size that is called window. Thus, FFT is applied for each window and the estimated frequency is approximated to the nearest pitch number. The main problem in this step is the lower frequency of heart sounds in comparison with music. The proposed shifting method aims to solve the problem with transferring the low-frequency samples to high-frequency notes (music instruments). Moreover, the textual transcription is implemented in two processing methods which are real-time (RT) and non-real-time (NRT). The performance of the transcription is investigated in both methods.

Music Transcription
Automatic music transcription is a technique to analyze audio signals in order to extract the pitch levels and transcribed as musical notation. The pitch extraction or pitch tracking for monophonic music starts with note or pitch onset detection, followed by a nearest pitch approximation [10]. Monophonic music in this context is when a single note or onset is sounded at any one point in time as opposed to polyphonic whereby multiple onsets may occur at a given point in time. Pitch approximation is based on the fundamental frequency (f 0 ) of the given piece of music to find nearest note number relative to that particular note. In order to extract the fundamental frequency of a played note, Fast Fourier Transform (FFT) would be the most appropriate method. FFT detects all the frequencies in a given window. An audio signal stream is usually broken into smaller sections called windows for analysis. The following formula illustrates the frequency distribution, X, from a window with size of N samples: Transcription of polyphonic music is more complex than monophonic due to the occurrence of several notes at a given point in time [10].

Heartbeat Sounds Transcription
This section presents the transcription technique that is used to process the heartbeat sounds. According to the nature of the heart sound, the music signal processing techniques can be adopted with a few modifications in terms of frequency and window sizes. These modifications are required due to differences between music and heartbeat sounds' characteristics.

Heartbeat Sounds
Heartbeat sounds are semi-periodical signals that are generated by blood turbulence and the beating heart. These sounds provide important and common ways for diagnosing of heart diseases with its ease of availability as well as in a cost-effective way. A heartbeat sound normally consists of two pulses; first heart sound (S1) and second heart sound (S2). Figure 1 shows a normal heart (healthy) sound waveform. The duration of heart Figure 1 Waveform of a normal heart sound. S1 denotes first heart sound S2 denotes second heart sound. sound pulses is approximately 100 ms [3,20]. This duration is sufficient for applying signal processing techniques. Moreover, the frequency of heart sounds is low in range between 20 and 150 Hz [19]. Hence, the heart sounds can be represented in first and second music octaves. Figure 2 shows the frequency distribution of three randomly selected samples of heart sounds from normal, gallop rhythm and systolic murmurs cases. Clearly, it has been shown that the signals are mostly in low-frequency spectrum.

Preprocessing
Generally, the recorded heart sound consists of the background audio and other organs sounds. Therefore, preprocessing of heartbeat sounds is an important task for de-noising of samples [18]. Based on our domain of study, the unexpected sounds (e.g., other organs) are assumed as the noise. Before frequency estimation of the heart sound, different levels of the preparation on frequency and amplitude domains are required [8]. Figure 3 shows a randomly selected heart sound from healthy (normal) category before and after preprocessing. The frequency distribution of the first pulse is shown in the right side of the each PCG. As it is illustrated in the frequency distribution, the heart sounds consist of various higher frequencies with higher magnitudes. Hence, filtering and noise cancellation of unexpected signals are required. A low-pass filter with f pass = 250 Hz and f stop = 400 Hz is applied for heart sound samples.

Textual Transcription
In this paper, we aim to process heart sounds with a monophonic pitch tracking method. However, some modifications must be applied for the case of onset time detection and frequency estimation of heart sounds with low frequencies. In order to simplify the process and provide outputs with similar duration, we eliminate the onset detection. Therefore, the heart sounds are processed in small size windows (with size of w). The results are stream of text that each byte shows binary value of the pitch numbers. On the other hand, to reduce the number of calculations frequency is limited between 1 and 500 Hz. Frequency estimation is the main step in musical transcription. After that, the relevant pitch number is estimated with a simple calculation by the following formula: where f(p) denotes the estimated frequency and N(p) is the nearest pitch approximation. The note number 60 is the musical note C 4 with frequency value of 261.6 Hz. This formula shows that, if the value f(p) is increased to 2 times, the value of 12 which is an octave interval is added to the N(p). Each calculated section is equivalent to one musical note, and generates binary codes based on N(p).    Figure 4 shows an example of transcription for a normal heartbeat sounds with window size of 250 ms. In this sample, each window is converted to a eighth note duration. There is a slight correlation between pulses and frequencies which in most normal cases S1 shows higher frequency than S2.
We use textual transcription term instead of musical transcription due to storage format of the converted samples that is a plain text consists of binary value of the note numbers. Moreover, the notes are started periodically with a constant window size.

Frequency Shifting
The preliminary experiments revealed a low accuracy of transcription due to the low frequency of heart sound [21]. Therefore, we propose a frequency shift method that increases the frequency level of the heart sound to provide an accurate transcription. Based on this, a constant shifting value, f sh , is added to the extracted frequency in order to reach a high frequency note. The shifting size impacts the performance of the transcription that must be investigated to find a suitable value. Figure 5 shows an example of frequency shifting for one and two octaves. In that example, if original signal is assumed as f 0 hence the first octave shifting is performed by f 1 = 2 * f 0 and second octave is calculated with f 2 = 2 * f 1 (f 2 = 4 * f 0 ). As it is shown in Figure 5, each window consists of vast distribution of the frequencies. This distribution must be limited to achieve an accurate transcription. In a previous study, we proposed an amplitude reconstruction method that passes the high magnitude signals and reconstructs the lower magnitude than a specified threshold level [8]. Therefore, by applying that method, the low magnitude signals and frequencies (known as harmonics) are eliminated. Figure 6 shows our process diagram for heart sounds transcription. The pitch extraction function estimates the frequency of the specific window. The frequency shifting is called for the cases of lower frequencies than 100 Hz. After the shifting task, the inverse FFT is used to prepare an audio signal from the shifted sounds. In some cases with very low frequency (< 50 Hz), the shifting task must be applied at least two times to reach the accepted minimum frequency level.

Experiments
This section explains experimental configuration and platforms that are utilized to perform the proposed transcription. In addition, the method of sampling and resources are described in this section as well. In this study, the aim is in obtaining a high accuracy transcription of the heartbeat sounds with both real-time and non-real-time methods. Furthermore, the size of the converted textual files must be small that can be used for a continuous transcription of the audio heartbeat data stream.
For investigating the accuracy of the transcription, the ratio of correct notes transcribed, n t , to the total transcribed notes, N, is calculated.

Experimental Setup
The proposed transcription method is implemented using real-time and non-real-time processes. We investigate both processing methods in terms of accuracy and feasibility.

Real-Time Process
With the real-time (RT) process, a digital signal processor (DSP) evaluation module was utilized. A TMS320C55 series DSP was deployed as the main processor. The DSP is a 16-bit processor with on-chip 320 KB memory. Figure 7 shows an image of the evaluation module. We use a single input channel of the module which directly captures the heart sounds. To accelerate the frequency calculation, TMS320C5515 was equipped  with a hardware accelerator for FFT computation which estimates the frequency of the given signals simultaneously. After real-time processing of each window, the estimated byte (pitch number) is sent to the PC to save as a plain text. The aim of the use of this module is to evaluate the possibility of the RT process for the future applications.

Non-Real-Time Process
For the non-real-time (NRT) process, we use MATLAB software version 6. Each record is loaded into an array of integer values where each cell contains a magnitude of a sample. The array is divided into several sub-arrays with length of window and pitch extraction is performed for each window separately. The extracted notes are then stored as plain text format. To reduce the number of calculations, the estimated frequencies are limited in a range from 0 to 500 Hz.

Data Collection
The proposed transcription technique and the shifting method must be evaluated for both healthy and unhealthy heart sound samples. Following this, the samples are recorded from different heart problems as well as healthy heart sounds. In this study, 100 heart sounds were recorded by an electrical stethoscope (3M-Littman Stethoscope) and were checked by a cardiologist. The samples were categorized in 8 different groups based on heart diseases. Table 1 shows the number of recorded samples in different categories. In this study, we are not interested to propose an automatic heart diseases detection or classification. Although different categories have been obtained, these were grouped as healthy and unhealthy for evaluating the performance of the transcription. Therefore, the proposed method is tested with 84 records from heart diseases and 16 healthy heartbeat sounds. The duration of each sample is around 10 sec.

Results and Discussion
In this section, the results of the performed experiments are discussed. The first part of our experiments estimates the appropriate threshold level in order to define an experimental framework. Figure 8 reveals the results of three different threshold levels with respect to the maximum peak that has been occurred in samples. The threshold levels are T {0.2, 0.4, 0.6} and the window size is 250 ms. The observed results reveal that, an increase in threshold level results in an increase with the performance of the transcription for both RT and NRT processes. By increasing the threshold level, the low magnitude samples (including noise and harmonics) are eliminated and high energy samples are used for sampling. As it is expected, the NRT process has better performance in most cases in comparison with RT process.
Therefore, the higher ratio of threshold values show better performance. This results were also illustrated in our previous study [18]. In the following experiments,   the threshold level was assigned as T = 0.6 A max , where A max denotes the sample with maximum magnitude. The second part of the experiments is to estimate a suitable size of the window (w) for frequency estimation process. In this regard, different window sizes are evaluated (w {100, 250, 500} in milliseconds). Figure 9 shows the performance of the transcription for different categories with RT and NRT processes. The observed results show that, window sizes of 100 and 250 ms are suitable duration for process. However, in large size window (500 ms), some events are lost due to coverage size of the window. As an example, in some windows more than one note (pulse) may appear. Although with a short window (100 ms) the performance is good, the number of notes is extremely increases and size of the recorded text file is become larger than window with size of 250 ms. The results of the experiment show that, utilizing 250 ms as the window size gives higher performance and it provides relatively small output size.
The important part of the experiments is to investigate the effects of the different amounts of the frequency shifting in order to find a suitable shifting size. Figure 10 shows the average results of both processing methods (RT and NRT) for the shifting method with different amounts (8,14,20 and 26 semi-notes). This method has different impacts on our samples with respect to the categories. Totally, shifting with 14 seminotes illustrates better performance in most cases. Increasing the shifting size more than two octaves reduces the performance due to the loss of some higher frequencies, which may occur in filtering process.
Finally, an experiment is performed with the obtained configuration values (T = 0.6 A max , w = 250 ms and f sh = 14 semi-notes). Figure 11 shows the results of the performance evaluation. It shows that, the frequency shifting significantly increases the accuracy of the transcription regardless of the categories. The average accuracy of 90% and 85% for NRT and RT respectively in unhealthy cases and 95% and 89% for NRT and RT respectively in normal heart sounds are obtained. Therefore, the frequency shifting increases the accuracy of transcription that was performed in [18].
In contrast with the previous studies [13,14], the proposed frequency shifting could cover the low frequency samples without complex calculations. In addition, based on the duration of each pulse that is enough for applying the frequency estimation, with selecting small window sizes it was shown to be possible to implement the frequency shifting in real-time applications.

Conclusion
In this paper, we proposed a frequency shifting method in order to increase the accuracy of the transcription. This method was tested in various recorded heart sounds samples including healthy and unhealthy cases that were categorized in 8 groups. The suitable values for configuration parameters of signal processing such as window size and threshold level were estimated by the initial experiments (w = 250 ms and T = 0.6). Following this, the shifting method was evaluated and an appropriate shifting size (14 semi-notes) was selected. The performance of the transcription was tested in different heart sound samples using real-time and nonreal-time processes. The observed results showed that non-real-time process has a better performance in comparison with real-time process (95% and 90% for healthy and unhealthy cases respectively). The accuracy of the real-time process was also good (89% and 85% for healthy and unhealthy cases respectively). It reveals that, this method can be used in real-time systems such as house hold heart problem detection systems as early warning systems.