{'fraction_non_alphanumeric': 0.05672187232719073, 'fraction_numerical': 0.01426794183967032, 'mean_word_length': 3.843344003012615, 'pattern_counts': {'":': 0, '<': 18, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 21, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Novel Time-Varying Coding Scheme for the Gaussian Broadcast Channel with Feedback

In this paper, we generalize a coding strategy for the Gaussian broadcast channel with feedback, analyze error probabilities and achievable rate region for this coding strategy by using the iterated random function theory [1], [2], [6]. By changing some parameters in our scheme, we realize a variant of the Ozarow-Leung's code for the general two-user broadcast channel with feedback. A capacity-achieving coding scheme for the degraded broadcast channel with feedback is drawn. More interestingly, we come to a coding scheme for the symmetric Gaussian broadcast channel with feedback which achieves the same sum-rate as the LQG code [18] and strictly outperforms the Kramer code [14]. The fact that our coding scheme is a variant of the Kramer's code or time-varying posterior matching code [1] may give useful information to solve some open problems proposed in [19], [20].


I. INTRODUCTION
The capacity of the broadcast channel is a well-known open problem. However, it is known that feedback can increase the capacity of this kind of channel. Specially, Ozarow and Leung [4] proved that feedback could increase the capacity of the two-user additive white Gaussian broadcast channel (AWGN-BC) with feedback by providing a means of cooperation between the receivers and the sender. Kramer [14] extended this encoding-decoding scheme for more than two users. Later, Elia [7] showed that the achievable rate region obtained by Ozarow and Leung [4] could be enlarged by using robust control theory. Ardestanizadeh et al. [18] proposed an LQG (Linear Quadratic Gaussian) based encoding-decoding scheme for the symmetric Gaussian broadcast channels with feedback and shown that their LQG code to provide the same achievable rate as Elia [7] for the symmetric two-user Gaussian broadcast channel with feedback and strictly outperform Kramer code [14] for the symmetric Gaussian broadcast channel with feedback when the number of users is greater than 3. The LQG code is derived based on a mapping from a feedback control problem to a linear code for the AWGN-BC with feedback. The set of achievable rates is determined by the eigenvalues of the openloop matrix of a linear system and the power constraint is related to the minimum power needed to stabilize the system using a feedback control signal.
In a more general direction, Gaspar et al. [19], [20] proposed a coding scheme for the Gaussian broadcast channel with correlated noises for the two user case with arbitrary noise covariance and for the more user case when noise samples at receivers are all multiples of each other. For example, they showed that for all noise correlation other than ±1, the gap between the sum-rate of their scheme achieves and the full-cooperation bound vanishes as the signal-to-noise ratio tends to infinity. Although their coding scheme works well in the asymptotic regime, it does not work well when the input power is not sufficiently large.
In this paper, using analysis tool, we firstly analyze the achievable rate region for a general coding strategy for the Gaussian broadcast channel with feedback that includes all the coding schemes [1], [4], [14]. Then, we prove that a variant of the Ozarow-Leung [4] scheme can be obtained from this strategy with the same achievable rate region. Moreover, we come to an coding scheme for the multiuser degraded AWGN-BC with feedback. Furthermore, we proposed a coding scheme for the non-degraded AWGN-BC with feedback to achieve the same sum-rate as the LQG code. Our encoding scheme is a variant of the Kramer's code, hence it shows a potential of this method to design a coding scheme which achieves not only the asymptotic capacity [19], [20], but also provides good performance in non-asymptotic settings.
The rest of this paper is organized as follows. Section II presents the channel model and some mathematical preliminaries. Section III proposes a general time-varying coding scheme for Gaussian broadcast channel with feedback. Section IV analyses the achievable rate region and error probabilities for this general scheme. Section V shows that Ozarow-Leung coding scheme is a variant of this coding scheme. Section VI proposed a coding scheme for the degraded Gaussian broadcast channel with feedback. Section VII designs a coding scheme achieving the same sum-rate as the LQG code. Finally, Section VIII concludes this paper.

II. CHANNEL MODEL AND PRELIMINARIES
A. Mathematical notations [1] Upper-case letters, their realizations by corresponding lower-case letters, denote random variables. A real-valued random variable X is associated with a distribution P X (·) defined on the usual Borel σ-algebra over R, and we write X ∼ P X . The cumulative distribution function (c.d.f.) of arXiv:1404.2520v6 [cs.IT] 8 Sep 2014 X is given by F X (x) = P X ((−∞, x]), and their inverse c.d.f is defined to be F −1 X (t) := inf{x : F X (x) > t}. The uniform probability distribution over (0, 1) is denoted through U. The composition function (f • g)(x) = f (g(x)). In addition, Y (q,m) ) for p ≤ q, tr(A) is defined as the trace of the matrix A. In this paper, we use the following lemma: Lemma I: Let X be a continuous random variable with X ∼ P X and Θ be an uniform distribution random variable, i.e. Θ ∼ U be statistical independent. Then F −1 X (Θ) ∼ P X and F X (X) ∼ U.
Proof: Refer to [2] for the proof. Big O notation (with a capital letter O, not a zero), also called Landau's symbol, is a symbolism used in complexity theory, computer science, and mathematics to describe the asymptotic behavior of functions. Basically, it tells you how fast a function grows or declines. For the formal definition, suppose f (n) and g(n) are two functions defined on positive integer number. We write ) for n → ∞ to be more precise) if and only if there exists constants N and C such that |f (n)| ≤ C|g(n)| for all n > N Intuitively, this means that f does not grow faster than g.
In addition to big O notations, another Landau symbol is used in mathematics: the little o. Formally, we write f (n) = o(g(n)) for n → ∞ if and only if for every C > 0 there exists a real number N such that for all n > N we have |f (n)| < C|g(n)|. If g(n) = 0, this is equivalent to lim n→∞ f (n)/g(n) = 0.
A Hadamard matrix [15] of order n is an (n × n) matrix of +1s and −1s such that HH T = nI. In fact, it is not yet known for which values of n an H n does exists. However, we know that if a Hadamard matrix of order n exists, then n is 1, 2, 4, or a multiple of 4. Moreover, if n is of the form 2 m , m a positive integer, we can construct H n by using the Sylvester method. Besides, the Paley construction, which uses quadratic residues, can be used to construct Hadamard matrices of order n, where n is of the form (p + 1), p is a prime, and n is a multiple of 4.

B. Gaussian Broadcast Channel with Feedback
Consider the communication problem between one sender and M receivers over a broadcast channel with additive Gaussian noise (AWGN-BC) when channel outputs are noiselessly fed back to all the senders (Figure 1). Let Θ m be a random message point uniformly distributed over the unit interval that will intend to transmit from the transmitter to the receiver m ∈ {1, 2, ..., M }. At each time n, the received signal at the receiver m is n where X n ∈ R is the transmitted symbol by the sender at time n; Y (m) n ∈ R is the received signal by the receiver m at m . For the non-physically degraded white Gaussian broadcast channel, we can set σ 2 = 0. Also, we assume that output symbols are casually fed back to the sender and that the transmitted symbol X n at time n can depend on both the message Θ 1 , Θ 2 , ..., Θ M and the previous channel output sequences n−1 , ∀m ∈ {1, 2, · · · , M }. A transmission scheme for a Gaussian broadcast channel is a measurable transmission function g n : (0, 1) × (0, 1) × · · · × R n−1 × R n−1 × · · · × R n−1 , so that the input to the channel generated by the transmitter is given by n (y (n,m) ) as to the decoded interval at the receiver m. The error probabilities at time n associated with a transmission scheme and a decoding rule, is defined as n (e) := P(Θ m / ∈ ∆ (m) n (Y (n,m) ), ∀m ∈ {1, 2, · · · , M } and the corresponding achievable rate region at time n is defined to be We say that a transmission scheme together with a decoding rule achieve a rate region (R 1 , R 2 , · · · , R M ) over a Gaussian broadcast channel if for m ∈ {1, 2, ..., M } we have The rate vector is achieved within input power constraint P , if in addition An optimal fixed rate decoding rule for a Gaussian broadcast channel with feedback with rate region (R 1 , R 2 , ..., R M ) is one that decodes a vector of fixed length intervals {(J 1 , J 2 , ..., J M ) : |J m | = 2 −nRm , ∀m}, whose marginal posteriori probabilities are maximal, i.e., (m) n (y (n,m) ) = argmax Jm∈E:|Jm|=2 −nRm P Θm|Y n (J m |y (n,m) ) An optimal variable rate decoding rule with target error probabilities p  Lemma II: The achievability in the definition (1) and (2) implies the achievability in the standard framework.
Proof: See the detailed proof in papers [1], [2], [18]. The idea is that if we transmit a message point which is uniformly distributed on (0,1) (no prior knowledge about Θ m ), we can find a decoded interval with length 2 −nR * m , where R * m depends on the signal to noise ratio, such that the transmitted message point belongs to this interval in probability by repeating the decoding process infinitely many times (n → ∞). Hence, at each transmission time slot n, we can choose M message points in (0,1) separated by 2 −nR * m with the property that their decoded intervals to be non-overlapped. Mapping message points {1, 2, ..., 2 nRm * } defined in the standard framework to those message points will complete our encoding in the traditional way. The error probabilities of the associated scheme can be shown to decay as the root square of the p

III. A GENERAL TIME-VARYING CODING SCHEME FOR
GAUSSIAN BROADCAST CHANNEL WITH FEEDBACK In this section, we proposed a novel time-varying encoding scheme and a variable-rate decoding strategy for the Gaussian broadcast channel with feedback. We refer our below encoding-decoding to as a time-varying coding and decoding strategy for the Gaussian broadcast channel with feedback. Assuming that the transmitter is trying to reliably send M different messages {Θ m } M m=1 to M receivers, where Θ m is the intended message for the user m, Θ m ∼ U. Our general encoding-decoding scheme as following: A. Encoding Scheme 1) At each time slot n for n ≥ 1 • The transmitter broadcasts the following signal to all the receivers: Here, β n is a coefficient to be chosen to satisfy the input power constraint (2), and is a modulated vector. • The receiver m receives the signal The receiver m feedbacks the random variable Y > 0) are some real number sequences depending on the network situations. In addition, the initial sequence S (m) where S is a Gaussian random variable and S ∼ N (0, P 0 ) for some value of power P 0 > 0.

B. Decoding Scheme
1) At the time slot n for n ≥ 1: • At the time slot n, the receiver m receives the signal n+1 . • Then, the receiver m estimates the decoded interval for the S  n (x) are monotone increasing in the variable x for any realization y (n,m) of the random vector Y (n,m) ). • Finally, the decoded interval for Θ m is set to be In this section, we evaluate the performance of the general time-varying posterior matching scheme in Section III.
Theorem I: Consider a real Gaussian broadcast channel with feedback having one transmitter and M receivers. Assuming that the time-varying coding and decoding strategy in section III is being employed for this channel. Under the condition that 0 < lim sup n→∞ a (m) n < 1 and that Then, without input power constraint consideration, the rate n (e) decays to zero as following: as the instant rate to transmit the intended messages Θ m to the receiver m. For any fixed rate R m , we have where Here, (a) follows from the definition of the corresponding instant achievable rate vector at time n in the Section II.
Observe that by our definition, then for all t, s ∈ R, we have (3) and (4), we have where (a) follows from the Markov's inequality and the law of iterated expectations, (b) follows from v m := sup 1≤n≤N a (m) n , and (c) is a recursive application of the preceding transitions, (d) follows from sup n≤N a (m) n < a m + above and the recursive applications of the preceding transitions.
From (5), it is easy to see that a sufficient condition for P(R Denote Q(x) as the well-known tail function of the standard normal distribution and use the Chernoff bound of this function, we obtain Here, (a) follows from the fact that J is symmetric if we set s m = −t m , and (b) follows from the Chernoff bound for the Q-function 0 < Q(x) ≤ (1/2) exp(−x 2 /2), ∀x > 0.
By the fact that R m < log(a m + ) −1 < R * m , we have |J (m) 1 | → ∞. Furthermore, with the assumption that W n is upper bounded by some W , we have To put it simply, if R m < R * m , the error probabilities tend to zero as Remark: Since we can estimate R * m and know our desired rate R m in advance, it is possible to choose by target. This means that the decoding algorithm is technically realizable. However, there is a tradeoff between the transmission rate R m (the possible values of ) and the code length n. If we transmit at the rate R m very close to R * m , we need to choose to be very small. As a result, the required N may be very large. Furthermore, the fact that log(a m + ) −1 is very lose to R m also makes the error probabilities be slowly decayed to zero. To put it simply, the code length n may be very large if we transmit at the rate R m is nearly R * m . On the contrary, being able to choose quite large makes the required N smaller and the decay of error probabilities faster.
In this case, we set P 0 = P/2 Here, sgn(x) := 1 if x ≥ 0 and sgn(x) := −1 if x < 0. We also define n ) By our transmission strategy, we have Therefore, we have the output sequences at the two receivers are Note that n Y Replacing the calculations above, we finally have By the general time-varying coding scheme, we obtain Hence, Replacing all the results above, and perform some simple calculations we get a recursive formula for ρ n as following where Π = (P + σ 2 + σ 2 1 )(P + σ 2 + σ 2 2 ), Σ = P + σ 2 + σ 2 1 + σ 2 2 , D n = 1 + g 2 + 2g|ρ n | It is very difficult to affirm that the sequence |ρ n | is convergent. One strategy to overcome this situation is to keep |ρ n | unchanged (see [4]). Then we have ρ n = (−1) n+1 ρ, where ρ is the biggest positive solution of the following equation: Then, we have lim sup n→∞ a (1) n = σ 2 + σ 2 1 + (P g 2 (1 − ρ 2 ))/(1 + g 2 + 2gρ) It is easy to verify that 0 < lim sup n→∞ a (m) n < 1, ∀m = 1, 2. Besides, we can prove by induction that S n ] 2 is a constant and upper bounded, of course. In summary, we have proved that all the constraints in the Theorem I are satisfied by using this encoding scheme. Therefore, the achievable rate region with this coding scheme is ( Remark: As shown, this encoding scheme is a variant of the Ozarow-Leung coding scheme [4] or a form of timevarying posterior matching [1]. However, the performance of this code is strictly worse than the one of LQG code [18] or Elia [7]. In the Section V below, we prove that by choosing a better choice of sequences α (m) n , we can achieve better achievable rate. Specifically, our proposed coding scheme for the symmetric Gaussian broadcast channel in the Section V obtains the same achievable sum rate as LQG code [18] and strictly outperforms Kramer code [14].

VI. A CODING SCHEME FOR DEGRADED GAUSSIAN BROADCAST CHANNEL WITH FEEDBACK
For the degraded Gaussian broadcast channel, i.e, σ 2 = 1, σ 2 1 = σ 2 2 = ... = σ 2 M = 0, in which case the receivers observe the sequence. In this case, we set parameters as following: The modulated vector α n = [ α (1) n , α n , · · · , α where α n = [ α (1) n , α (2) n , · · · , α (M ) n ] T is the modulated vector above. We can show that this strategy is the same as the coding scheme used for Gaussian MAC channel with feedback proposed in [1], i.e. , Observe that for this physically degraded case, the Gaussian broadcast channel with feedback can be considered as M Gaussian virtual MACs with feedback, each MAC corresponds to a receiver with the inputs S Proof: Using the same arguments as the the of the the paper [1].
As a corollary [1], the degraded Gaussian broadcast channel with feedback can achieves the sum-rate where λ is the biggest solution in [1, M ] of the following equation: Note that this achievable sum-rate is obtained if the input power constraint is where (a) follows from the result of paper [1] and (b) follows from the Cesaro means and the fact that the eigenvalue λ n converges to λ. Remark: By replacing P by P λ, we see that our scheme for the degraded broadcast channel with feedback obtains the sum-rate (1/2) log(1 + P ), which is the sum-rate capacity of this channel since we know that feedback does not increase the capacity of degraded Gaussian broadcast channel with feedback [10], [11], [19].

VII. A NOVEL TIME-VARYING CODING SCHEME FOR M-USER SYMMETRIC NON-DEGRADED GAUSSIAN BROADCAST CHANNEL WITH FEEDBACK
In this section, we propose a time-varying code for the non-physical degraded case, i.e., σ 2 1 = σ 2 2 = ... = σ 2 M = 1 and σ 2 = 0, which achieves the same performance as the LQG code [18]. Our proposed coding scheme is based on the following Lemmas: Lemma III: Let λ 1 , λ 2 , ...λ M be a set of positive numbers satisfying: where λ 1 = λ is the biggest positive root of the following equation: Assuming that γ is a negative number satisfying: Then, we have λ m + γ > 0 for all m.
Proof: Indeed, from the given relation, we have for all m = 1, 2, · · · , M − 1. Moreover, we have Combining with our assumption, then This concludes our proof.
Lemma IV: For any positive number λ, the following equation system has an unique solution pair (b, γ) with b > 0, γ < 0.
Moreover, we have Proof: The equality (10) is equivalent to Performing some simple manipulations, we get the quadratic equation of b 2 .
It is easy to see that this quadratic equation has an unique solution b 2 Besides, from (11) we easily see that γ > −λ. This means that λ + γ > 0. We also have Since this equation has a positive solution b as we mentioned, we must have λ + γ ≥ M (P/M )λ 2 1 + P λ = P λ 2 1 + P λ or γ ≥ − λ 1 + P λ It is obvious that γ < 0 by their relation mentioned above. That concludes our proof.
Theorem III: The time-varying coding scheme for M-user non-degraded Gaussian broadcast channel with feedback can achieve the following sum-rate where λ is the biggest solution in [1, M ] of the following equation: Proof: We divide the proof into two parts. In the first part, we provide extra notations used in our analysis later. Then, in the next part, we show how to set parameters (sequences) for our encoding-decoding scheme, then prove that our coding system to achieve the same performance as the LQG code [18].

A. Extra notations:
Define a normalized covariance matrix by ∀m where b n is a real sequence. We also define an associated matrix G n as following where γ n is another real sequence.
B. Parameter settings, achievable rate region analysis, and error probabilities: Let λ 1 , λ 2 , ..., λ M be the set of the positive numbers defined on the Lemma III. We firstly show by induction that if there exists n 0 ∈ N such that G n0 is symmetric positive definite and has all of the columns of the M -by-M Hadamard matrix as its eigenvectors, then by suitably choosing sequences b n , γ n , β n for all n ≥ n 0 , the matrices G n (n ≥ n 0 ) aslo have all these properties. In addition, by this way of parameter setting, if λ n , and λ 1 := λ, hereafter. Indeed, the matrix G n0 , of course, satisfies all these properties by our assumption. Assuming that our assumption is true for some n ≥ n 0 . Denote Here, we define the delta function δ(n) = 1 if n = 0 and δ(n) = 0 if n = 0. By our encoding scheme, the transmitted signal has the following form: where β n is a coefficient to be chosen to satisfy the input power constraint. Then, the transmitted input power at time n is To put it simply, (Here, we use the fact that G n α n = λ n α n ). Moreover, the relation between the input and the output at the receiver m is expressed as Therefore, With the assumption that G n is symmetric and that λ n is an eigenvalue associated with the eigenvector α n of this matrix, we have α T n G n = α T n G T n = α T n λ n Hence, we obtain α T n ρ n . Combining these facts, we have Furthermore, we also obtain = E(X 2 n )+E(Z (m) n Z (k) n ) = P β 2 n (λ n +γ n )+δ(m−k) (16) Note that by our transmission scheme Then, Now, if we set a n = 1 + (P/M )λ n (M − λ n ) 1 + P λ n (18) and choose Then for all m, k we have Combining with (17), we obtain Now, for all n ≥ n 0 , we will set b n = b > 0, γ n = γ < 0 which is the unique solution in the equation system in the Lemma IV above. With the induction assumption that λ n = λ, in order for satisfying the input power constraint, we can set Note that this definition of β n is well-defined for the Lemma IV λ + γ > 0. Moreover, from (14), we see that E(X 2 n ) = P for all n ≥ n 0 . In addition, we also see that Combining these facts, from (21) come to the following recursion ρ (m,k) This leads to Since we assume that the matrix G n is symmetric, the matrix G n+1 is obviously symmetric. Denote H n = α n α n+1 · · · α n+M −1 by our induction assumption. We see that the columns of H n creates M linearly independent eigenvectors of the matrix R n . Furthermore, Note that since all columns of H n are eigenvectors of the matrix G n , so all the columns of the matrix H n+1 are also eigenvectors of the matrix R n , hence we has the following eigenvalue decomposition n , ..., λ n+1 ), which are diagonal matrices. We also have From (23), (24), (25), (26), the matrix H T n+1 G n+1 H n+1 must be a diagonal one since the right side of (23) is a diagonal matrix. Hence, all columns of the matrix H n+1 are eigenvectors of the matrix R n+1 .
Moreover, from (23) and our notations mentioned above, we also have Since we assumed that all eigenvalues of G n are positive (G n symmetric positive definite), from (27) we see that all eigenvalues of G n+1 are also positive. Note that we also confirmed that G n+1 is symmetric above, therefore G n+1 is a symmetric positive definite matrix. In short, if G n is a symmetric positive definite matrix and has all columns of the Hadamard matrix as its eigenvectors, then G n+1 has all these properties. Moreover, by our induction assumption that λ (m) n = λ m , ∀m and the relation among λ m 's defined on the Lemma III, from the recursion formula (28) we easily come to conclusion that λ From (34), it is easy to see that λ (1) Replacing the chosen value of λ 0 , we must have Note that from equations (33), (35) we can easily see that for 1 ≤ n ≤ M then Therefore, combining with (36), for 1 ≤ n ≤ M − 1, we obtain γ + d n λ n = γ + a 2n 1 a 2(n−1) Here, the last equality follows from the Lemma IV. On the other hand, since a 2 = 1 + (P/M )λ(M − λ) 1 + P λ < 1 then d n = a 2n < 1. Therefore, From these facts, the inequality (37) is, of course, satisfied. It is easy to show that the equation (31) indeed has two positive solutions with that choice of the sequence d n . We can choose any solution of these as the value of β n b, but in order for reducing the transmitted power in the first M transmission, we can choose β n b is the smallest one. To finish the induction proof, we need to show that our encoding scheme is realizable by proving that R 1 is a diagonal matrix the same elements in its main diagonal. This can be showed by observing that Furthermore, since 1 ≤ λ ≤ M , we have 0 < lim sup n→∞ a n = 1 + (P/M )λ(M − λ) P λ + 1 < 1 In summary, the two constraints in the Theorem I are both satisfied. Applying the result of this theorem, we have any rate less than R * m = − lim sup log a n   (72), [16]). This means the difference of the sum rate of broadcast channel as well as MAC channels compared with no-feedback case grows as (log log M )/2.

C. Comparison with other well-known AWGN-BC
The time-varying coding scheme approach has been applied to the AWGN-MAC with feedback. It is shown in [1] that the time-varying coding scheme can achieve the the linear feedback sum capacity [16] as the Kramer code [14] or LQG code [17]. Let R M AC (M, P ) denote the symmetric sum-rate achievable by the time-varying code [1] for M -user AWGN MAC with feedback where each sender has power constraint P . Then, we have [1, Theorem III], This shows that under the same sum-power constraint P , the sum rate achievable by the time-varying code over MAC and BC is equal. This connection between MAC and the BC is already mentioned in [18]. Our result confirms the duality between broadcast and MAC channel.

VIII. CONCLUSION
A general coding strategy for the Gaussian broadcast channel with feedback was proposed, and achievable rate region, error performance were drawn. Then, based on the error analysis of performance of this coding strategy, we designed a novel coding scheme which obtain the same sumrate as the LQG code [18]. Besides, we show that a variant of Ozarow-Leung's coding scheme can be obtained by using this strategy. We also proposed a coding scheme for the degraded Gaussian broadcast channel. An interesting further research topic is to find a good sequences a (m) n , b (m) n to obtain good asymptotic capacity for more general settings in [19], [20].