{'fraction_non_alphanumeric': 0.03973767742708271, 'fraction_numerical': 0.011049889201652991, 'mean_word_length': 4.197665369649806, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 20, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimal caching placement for wireless femto-caching network

This paper investigates optimal caching placement for wireless femto-caching network. The average bit error rate (BER) is formulated as a function of caching placement under wireless fading. To minimize the average BER, we propose a greedy algorithm finding optimal caching placement with low computational complexity. Exploiting the property of the optimal caching placement which we derive, the proposed algorithm can be performed over considerably reduced search space. Contrary to the optimal caching placement without consideration of wireless fading aspects, we reveal that optimal caching placement can be reached by balancing a tradeoff between two different gains: file diversity gain and channel diversity gain. Moreover, we also identify the conditions that the optimal placement can be found without running the proposed greedy algorithm and derive the corresponding optimal caching placement in closed form.


I. INTRODUCTION
The recent spread of wireless devices has brought heavy data traffic which video-streaming requests, such as YouTube, occupy a dominant portion of. Unfortunately, however, current wireless systems have limitations of resources to accommodate this tremendous video traffic.
Discovering new but inexpensive resources is considered a solution to cope with the explosive traffic. In the same vein, memory for data caching arises as a new resource to exploit in wireless communications [2]. The characteristic of video traffic facilitates utilization of memory to handle huge video traffic; a few popular videos account for the majority of video traffic [3] and hence network traffic to carry the videos to the end users can be significantly reduced by storing the top-ranked video files near the users who are likely to request them.
Although caching has been intensively studied in wired networks, also known as content delivery network (CDN), it is transparent to wireless segments. Without consideration of wireless aspects, CDN is not enough to provide sufficient data rate to wireless end users. In this context, there have been recent studies figuring out wireless caching. For a given caching placement, several transmission schemes to exploit the given memory contents have been studied in [4]- [6]. Based on appropriate user grouping, when each user requests multiple files, a groupcasting scheme was proposed in [7]. With practical Zipf popularity distribution, [8] characterized the regimes with different coded multicasting gains. Prefix caching for wireless video streaming was proposed and optimized in [11]. Caching was exploited in cooperative multi-point MIMO transmission (CoMP) to reduce backhaul cost in [12]- [14]. Because where and what to cache determines the performance of wireless caching, caching placement has also attracted research interests, namely femto-caching and device-to-device (D2D) caching. In [9], proactive caching for femto-caching and D2D caching was studied. A caching scheme based on prediction of future demands was proposed in [10]. Optimal caching placement is able to minimize the access distance and inter-cell interference in wireless cache networks. In [15], [16], an optimization problem in terms of the average delay, a function of caching placement, was formulated and proved to be NP-complete when each user can access to a different set of femto base stations. With random caching placement for D2D communication, optimal cluster size and the parameter characterizing the random caching distribution were studied in [17], [18], where a square cell was composed of square clusters and D2D communication was activated if the file requested by user in a cluster was cached in any device inside the cluster. For D2D coded caching placement, optimal portion of files to store and density of nodes caching the requested file were investigated in [19], [20], respectively. Combining coded multicasting with D2D communication, [21] proposed caching and delivery schemes which can exploit spatial reuse gain as well as coded multicasting gain. Caching placement optimizing a tradeoff between throughput and outage was explored in [22], [23]. When Maximum-distance separable coding is used, optimal storage allocation under a total memory constraint was studied in [24], [25]. It was shown in [25] that symmetric allocation achieved asymptotically optimal performance. Replacing outage with delay, a similar tradeoff was revealed in a multi-hop network [26].
Although the aforementioned studies on caching placement aim at wireless caching, the wireless channel models in those studies partially address effects of wireless channel fading on caching placement. In particular, constant and identical channel links are assumed in most of the previous works [4]- [10], [15]- [23], [26]. Although the averaging effect of long file transmission justifies the assumption from a viewpoint of each link, random fading channels might reveal different aspects. For example, caching different files according to their popularity (i.e., file diversity), which increases the chance to access nearby caching nodes, is reported to be optimal [17] because caching the same file in multiple helpers is redundant under constant and identical channels. However, caching the same file in different helpers might be able to offer channel diversity [27] and hence caching the same file can be rather beneficial in random fading channels. Although channel fading is considered in [12]- [14], [24], the fundamental tradeoff was not clearly shown since they focused on proposing suboptimal or asymptotic solutions.
In this context, under random channel fading, this paper revisits and studies the optimal caching placement to minimize average bit error rate (BER) when there exist multiple helpers storing files. We identify the tradeoff between channel diversity and file diversity and derive optimal caching placement optimizing the tradeoff. Our main contributions are as follows: • We propose a greedy algorithm to find the optimal caching placement in terms of BER.
Exploiting the property of the optimal caching placement which we derive, the proposed algorithm has considerably reduced search space. It is shown that optimal caching placement is not focusing on the file diversity gain only, contrary to [17]; optimal caching placement is a balance between the file diversity gain and the channel diversity gain.
• We identify the conditions in terms of the popularity factor, i.e., Zipf exponent, that the optimal placement can be found without running the proposed greedy algorithm, and derive the corresponding optimal caching placement in closed form. In particular, we derive two special thresholds of popularity seeking an extreme of either file diversity gain or channel diversity gain, respectively. Furthermore, given enough proximity and transmit power, we show that optimal caching placement is parametrized solely with popularity.
The rest of this paper is organized as follows: Section II presents our system model. An optimization problem is formulated in Section III. We propose the algorithm to find a solution in Section IV and prove the optimality of the proposed algorithm. In Section V, we identify and analyze the tradeoff between the file diversity gain and the channel diversity gain. Numerical results are presented in Section VII. Finally, Section VIII concludes this paper.

II. SYSTEM MODEL
In this paper, we consider a cell composed of multiple clusters. In each cluster, the users can access N helpers which are capable of storing files in their memories. There is a file library whose size is F which is strictly larger than N. i.e., N < F . Each helper can store one file from the library in advance, and the users request a file in the library independently with probability q i according to the Zipf distribution with exponent γ, of which probability mass function is In each cluster, only one user is served for each file delivery period, which corresponds to orthogonal multiple access. Assuming orthogonal frequency allocation across clusters, inter-cluster interference is not considered in this paper, and thus we consider one cluster in isolation for tractable analysis. In addition, for simplicity, we assume that based on open loop power control, all of the users in a cluster have the same average received signal-tonoise ratio (SNR) from helpers regardless of their positions, but they still suffer from independent small-scale fading effects. As a result, the multi-user scenario is simplified into single-user one where a user who requests a file is served at every moment.
If the requested file is already stored in any helper's memory in a cluster, the requested file is transmitted from the helper which cached the file. Throughout this paper, we call this type of communication cluster communication. If the requested file is cached by more than one helper, a helper which has the largest channel gain is selected by the requesting user, using perfect channel state information. Fig. 1 shows an example of caching placement for a system with seven helpers, where the instantaneous received SNR from helper k which caches the ith file is denoted by ρ k i ; the average of ρ k i is represented asρ. If the first file is requested by the user, since there are three helpers which has the file, the requesting user selects the helper whose received SNR is the maximum among the three helpers and informs the corresponding helper to deliver the the first file. On the other hands, if the file requested by the user is not stored in the cluster, the BS serves the requesting user with average received SNR,ν; namely, the file is transmitted through cellular communication. We denote the ratio between the average received SNRs of cluster and cellular communication as β such that β =ρ/ν, and owing to closer distances to caching helpers than to the macro base station, β is reasonably assumed to be greater than one.
However, instantaneous channels gains from helpers and BS follow Rayleigh distribution.
Packet error rate (PER) and frame error rate (FER) are practical performance metrics. However, it is hard to mathematically analyze the impacts of caching placement and channel fading with PER or FER because an expression of PER or FER incorporating all affecting factors, such as channel coding and upper layer parameters, is usually not available. On the other hand, FER or PER is in general represented as a function of BER. Therefore, minimizing BER results in reducing FER or PER, albeit not linearly proportional. In this context, we study optimal caching placement to minimize BER, which will also proportionally reduce PER or FER. Assuming arbitrary coherent modulation/demodulation, the instantaneous BER in general form is given as [28] p e = α 0 Q √ α 1 λ , where λ is the instantaneous received SNR, α 0 , and α 1 are appropriate constants for each type of modulation, and Q (x) is Q-function defined as du. For simplity, we assume α 0 = 1 and α 1 = 2, which corresponds to QPSK, but generalization for arbitrary α 0 and α 1 is straightforward and the assumption of α 0 = 1 and α 1 = 2 does not lose any insights. Then, a file is transmitted over many coherent periods and the corresponding average BER of the file is obtained asp e = E λ Q √ 2λ .

III. PROBLEM FORMULATION
Otherwise, if n i = 0, the ith file is delivered via cluster communication. Since the helper with the largest channel gain among n i helpers is chosen to deliver the ith file to the user, the received SNR of cluster communication follows the distribution of ρ max Using (2), the average BER of the ith file via cluster communication conditioned on n i cached helpers, p cluster e (n i ) is obtained as Then, p e (n i ) is obtained as Since the ith file is requested by the user with probability q i , given caching placement n N , the average BER is derived as where 1(X) is the indication function; if event X is true, 1(X) = 1 and otherwise, 1(X) = 0.
Then, the optimal caching placement that minimizes the average BER for the N-helper system can be obtained by solving the following optimization problem: subject to where Z + is a set of non-negative integers.

IV. OPTIMAL CACHING PLACEMENT
The design variable of P is an N-dimension integer vector n N . A problem which finds an optimal integer variable is called integer programming. In many cases, integer programming is too complicated to get a closed-form solution. On that account, instead of solving the problem directly, we propose a greedy algorithm, which will be proven to be optimal under a mild condition. Algorithm 1 presents the proposed greedy algorithm, where ∆p e (n k ) is defined as By using (1) and (4), ∆p e (n k ) is given as As shown in Algorithm 1, at the mth iteration, the placement obtained by the proposed greedy algorithm provides the lowest average BER for the system with m + 1 helpers. This is because the proposed greedy algorithm compares the amount of reduction in BER, q k ∆p e ((n m ) k ), for each file and adds one file whose contribution is the largest to the memory in the cluster, where (n m ) k is the kth element of vector n m . In general, a greedy algorithm is not global optimal; (n m+1 ) j ← (n m ) j + 1 6: end for 7: return n N however, we show that the proposed greedy algorithm can find an optimal solution. Through the following lemma and theorem, we prove the optimality of the proposed greedy algorithm.
Proof: Please refer to Appendix A.

Theorem 1 (Optimality of the Proposed Greedy Algorithm):
For β ≥ 2, the caching placement obtained by the proposed greedy algorithm, n N greedy , is optimal for the N-helper system.
Proof: Please refer to Appendix B.
The proposed greedy algorithm has low complexity, however, we can reduce the complexity further with the following proposition.
Proposition 1 implies that since a lower index file is requested more frequently, the placement which stores more files whose index is low can decrease the average BER more.

Remark 1:
It is shown in the proof of Theorem 1 that caching placement of the mth iteration is optimal for the system with m + 1 helpers. When there exist m + 1 helpers, caching the m + 2th file is strictly suboptimal since this implies one of the files more popular than the m + 2th file is not cached. Hence, n m+2 = 0 for optimal caching placement. Moreover, by Proposition 1, n k = 0 for k ≥ m + 2. Therefore, in the mth iteration which determines optimal caching placement of a system with m + 1 helpers, it is unnecessary to compare the BER gain of the files less popular than the m + 2th popular file. Consequently, the number of comparisons in the mth iteration is reduced from the size of file library F to m. Because N − 1 iterations are required to find optimal caching placement of a system with N helpers, the total number of Theorem 1 ensures that the proposed greedy algorithm finds the optimal caching placement, given system parameters (i.e., N, F , γ,ν, andρ). In this section, we identify the conditions that the optimal placement can be found without running the proposed greedy algorithm, and derive the corresponding optimal placement. Before analyzing further, we first define the two types of gains which can be reaped by caching: file diversity gain and channel diversity gain.

Definition 1 (File Diversity Gain):
The amount of BER reduced by adding a new file which is not cached in any helper, is called file diversity gain.
Changing communication from cellular to cluster reduces average BER by means of the proximity between the helpers and the user. Obviously, file diversity gain is proportional to the popularity of the file. Hence, the file diversity gain of the kth file is defined as Definition 2 (Channel Diversity Gain): The amount of BER reduced by adding a file cached already by some helpers, is called channel diversity gain.
As we consider the effect of wireless fading channel such as small-scale fading, if we increase the number of helpers which store a specific file, the selection pool of channel links enlarges and BER of the file correspondingly improves due to the channel diversity. The channel diversity gain of the kth file is given as a function of the number of helpers that caches the kth file and the popularity of the kth file. The channel diversity gain of the kth popular file is written as

A. Even caching placement
In this subsection, we derive the condition when even placement, [n 1 , ..., n N , n N +1 , ..., n F ] = [1, ..., 1, 0, ..., 0], is optimal. In order that the output of the algorithm becomes even placement, at each iteration, the file which was not cached in the past iterations need to be cached. This happens when the maximum file diversity gain, is larger than the maximum channel diversity gain, for all iterations. On the other hand, if there exists any single iteration at which there is a file which has larger channel diversity gain than the maximum of file diversity gain, even caching placement cannot be realized by the greedy algorithm. The following proposition reveals the condition when even placement is optimal.
Proposition 2 (Optimality of Even Caching Placement): For β ≥ 2, even caching placement is optimal if and only if γ ≤ γ 0 , where γ 0 is defined as Proof: Please refer to Appendix D.
This proposition states that if user's preference for files is sufficiently unbiased (i.e., low Zipf exponent γ), even caching placement is a reasonable approach toward optimal performance.
This corollary implies that no matter how the received SNR of cluster communication is large, if popularity is highly biased, channel diversity gain should be considered.

B. Single-file caching placement
On the other extreme, if the smallest channel diversity gain is larger than the largest file diversity gain at every iteration, the output of the algorithm is single-file caching, i.e., if and only if γ ≥ γ 1 , where γ 1 is defined as Proof: Please refer to Appendix E.

C. Doubly caching placement
When the Zipf exponent is between γ 0 and γ 1 , owing to the following lemmas, we can analyze the structure of optimal placement in high SNR regime. , where Proof: Please refer Appendix G.
With Propositions 2, 3 and 4, optimal caching placement can be obtained without running the greedy algorithm by comparing the Zipf exponent of popularity, γ, with the thresholds, γ i , That is, if we have information about the file preference of users, then we can determine the optimal caching placement of helpers.
Until this point, we focused on the case when β is larger than or equal to two. The condition β ≥ 2 is necessary for file diversity gain of each file to be larger than channel diversity gain of the file from one to two helpers. The regime where β ≥ 2 implies that the average received SNR from helpers is larger than that from the macro base station by 3 dB. Given the proximity of femto base stations, it is known that the average received SNR of a femto cell user is approximately 10 dB higher than that of a macro cell user [29], so β ≥ 2 is typically achieved. We identified the optimal caching placement in the region of β ≥ 2.
For β < 2, fortunately, we can find optimal caching placement without running the proposed algorithm in high SNR for β < 2.

Proposition 5 (Optimality of Doubly Caching Placement with
Proof: Please refer Appendix H.
Proposition 5 verifies the analytic insights; smaller β brings less file diversity gain since the gain of first caching is higher as the SNR difference between BS and helpers is larger.
Consequently, when β is less than 2, channel diversity gain is more preferred. Combining this fact with Lemma 2, we can naturally conclude that caching all files in two helpers becomes optimal for β < 2 in high SNR. Table I summarizes the results of Section V; optimal caching placement depending on the range of Zipf exponent and β. The optimal caching placement in the region of β ≥ 2 is identified.
For β < 2, the solution when SNR is not large is unknown due to analytic intractability involved in Lemma 1 but optimal caching placement is presented when SNR is high.

VI. CACHING MULTIPLE FILES IN HELPERS
In this section, we extend the proposed greedy algorithm to when each helper caches up to M files. When each helper can cache up to M files, the optimization of minimizing the BER requires additional constraint n i ≤ N. Since caching the same file at a helper more than twice is strictly not optimal, n i ≤ N is additionally imposed to avoid unnecessary repetition. Note  fill the memory of each helper in each round by using the original greedy algorithm. However, in the original greedy algorithm n i ≤ N is not addressed. Therefore, to cover this constraint, if n i = N is satisfied at a certain round, the ith file is discarded after that round until the algorithm finishes. Although the proposed M-round greedy algorithm is suboptimal, Fig. 2 shows that its performance is close to the BER achieved by the optimal one found by exhaustive searches.

VII. NUMERICAL RESULTS
In this section, we demonstrate some numerical results that verify our analysis. We assume F = 20, N = 10, γ = 0.6, and β = 5 [dB] as a default setting [2]. Depending independent variables, the simulation environment is slightly changed and mentioned in each subsection.

A. Optimality of the proposed greedy algorithm
In this subsection, we verify that the proposed greedy algorithm finds the optimal caching placement. Table II shows optimal caching placement for various numbers of helpers forρ = 15 [dB], which is found by numerical full search. It is exhibited that optimal caching placement changes in a greedy way as the number of helpers increases. That is, only one component of optimal caching placement is changed as N increases to N + 1.  (16) and (17)

C. Performance comparison with other caching placement
We compare BER performance of optimal caching placement with other caching placement for various system environments. In Fig. 3     figure reveals that doubly caching placement achieves almost the same BER performance as optimal caching placement in all SNR region. Although even caching placement is known to be optimal without consideration of wireless aspects [17], it is rather outperformed by doubly caching placement in all SNR region.

Number of helpers Optimal caching placement Number of helpers Optimal caching placement
The effects of the Zipf exponent is considered in Fig. 4  exponent increases, the frequency of requesting the most popular file increases and thus the BER of high-ranked file dominates the average BER. Consequently, single-file caching placement shows better performance than even caching placement in high γ, but the opposite result is observed in low γ. On the other hand, doubly caching placement still show comparable BER performance with optimal caching placement for all values of the Zipf exponent γ.

VIII. CONCLUSION
We proposed an optimal greedy algorithm for caching placement in wireless femto-caching network. The proposed algorithm minimizes the average bit error rate with low computational complexity, exploiting the property of optimal caching placement which we derived. We also identified and explored the tradeoff between file diversity gain and channel diversity gain to minimize the average bit error rate. We derived two special thresholds of popularity seeking an extreme of either file diversity gain or channel diversity gain, respectively, which provide a useful caching placement guideline without running the proposed algorithm. Furthermore, given enough proximity and transmit power, we showed that optimal caching placement was parametrized solely with popularity. APPENDIX A PROOF OF LEMMA 1 We prove this lemma according to the range of n: n = 1 and n > 1. For n = 1, since zero is only integer which satisfies inequality m < 1, (10) becomes ∆p e (0) > ∆p e (1) . Using (9), ∆p e (0) and ∆p e (1) become Obviously, we have, for β ≥ 2, Second, for the case when n > 1, we prove the equivalent statement that ∆p e (n) > ∆p e (n + 1) for ∀n > 1. The equivalence is established by the two facts; (1) ∀m < n and n > 1, ∆p e (m) > ∆p e (n) obviously implies ∆p e (n) > ∆p e (n + 1).
(2) Conversely, ∆p e (n) > ∆p e (n + 1) can be extended to ∆p e (n − 1) > ∆p e (n), and using mathematical induction, we can conclude ∆p e (m) > p e (n) for ∀m such that m < n. Now, we prove the equivalent statement. Expressing the ∆p e (n) with (3), ∆p e (n) − ∆p e (n + 1) can be rewritten as positive value for all x, it is enough to show that R (x, n) > 0 ∀x ≥ 0 and ∀n ≥ 1.
Using the given PDF formula of f ρ max which is greater than zero for arbitrary x ≥ 0 and n ≥ 1.

APPENDIX B PROOF OF THEOREM 1
This theorem is proved by induction. First, for N = 1, we can readily show that n 1 opt = n 1 greedy .
Supposing n N −1 opt = n N −1 greedy , we will show that n N opt = n N greedy by contradiction. Suppose n N greedy is not optimal and there exists optimal caching placement for the N-helper system such that Now, let us consider another caching placementñ N −1 for the N − 1 helpers system, of which elements are the same as n N opt except that one element which least increases the average BER is reduced by one. In other words,ñ N −1 comes from n N opt in a reverse-greedy way.
where j is defined as j = arg min k∈F q k ∆p e n N opt k − 1 .
We note that the average BER ofñ N −1 must not be less than that of n N −1 opt ; hence, we havē Since, min k q k ∆p e n N opt k − 1 is smaller than the left-hand side of (B.9), and max k q k ∆p e n N −1 opt k is greater than the right-hand side of (B.9), we have Consider another caching placementn N that has the same element with n N opt except that n l and n l+1 are switched with each other as follows: Then, the difference of average BER between two caching placement schemes becomes p e n N opt −p e n N =q l p e n N opt l + q l+1 p e n N opt l+1 − q l p e n N l − q l+1 p e n N l+1 = (q l − q l+1 ) p e n N opt l − p e n N opt l+1 .

(C.3)
Since the l-th popular file is more probable to be requested than the l + 1-th popular file, the first term on the right-hand side on (C.3) is positive. (C.1) indicates that we have more helpers which cache the l + 1-th popular file than helpers which cache the l-th popular file. Consequently, the average BER of the l + 1-th popular file is lower than that of the l-th popular file because more helpers provide higher channel diversity gain which reduces BER. Therefore, (C.3) is positive; we havep e n N opt >p e n N . This contradicts to optimal caching placement.

APPENDIX D PROOF OF PROPOSITION 2
First, we prove the necessary condition for optimality of even caching placement. The condition γ ≤ γ 0 can be rewritten as Note that (D.3) means that the file diversity gain of the N-th file (i.e., the least popular file among possibly cached files) is larger than the channel diversity gain of the most popular file cached in a single helper. In addition to that, by the order of popularity, both of file and channel diversity gain decreases as popularity of file becomes lower. Hence, for any i ≤ N, g file i ≥ g file N .
Similarly, for any k ≥ 1, g channel (1) ≥ g channel k (n k ) for i < N which implies that lower bound of file diversity gain is larger than upper bound of channel diversity gain. As a consequence, file diversity gain is always larger than the maximum of channel diversity gain, which concludes optimality of even caching placement.
For the proof of converse, we will show the contraposition of the converse is true. The contraposition of the converse is that if γ > γ 0 , even caching placement is not optimal. Similarly, γ > γ 0 implies g file N < g channel 1 (1) . Then, obviously, before the N-th popular file is cached, the most popular file will be cached in two helpers. As a consequence, even caching placement cannot be optimal.
APPENDIX E

PROOF OF PROPOSITION 3
We first prove the sufficient condition for optimality: if γ ≥ γ 1 , then single-file placement is optimal. The condition γ ≥ γ 1 can be rewritten as By Lemma 1, g channel 1 (n) ≥ g channel 1 (N − 1) ≥ g file 2 for n ≤ N − 1 which implies that if γ ≥ γ 1 , channel diversity gain of the most popular file is always larger than file diversity gain of the second-popular file until N helpers cache the most popular file. Thus, the maximum channel diversity gain is always larger than maximum of file diversity gain for all iterations and consequently single-file placement becomes optimal. For proving the necessary condition, we prove the contraposition: if γ < γ 1 , then single-file placement is not optimal. γ < γ 1 is equivalent to g channel 1 (N − 1) < g file 2 which means the second-popular file will be cached before caching the first-popular one N times. Hence, single-file placement cannot be optimal. 0ρ sin 2 θ n l n l + 1 +ρ sin 2 θ B n l , 1 +ρ where G n l , sin 2 θ,ρ is defined as Hence, the ratio between g channel k (n k ) and g channel j (1) is represented by (1) for any j, k such that n j = 1 and n k ≥ 2.
Since numerator and denominator in (F.6) have −n k order ofρ and −1 order ofρ for high SNR regime, respectively, the limit becomes Therefore, g channel k (n k ) ∈ o g file j for any j, k such that n j = 0 and n k ≥ 2.

APPENDIX G PROOF OF PROPOSITION 4
To prove the proposition 4, we first show the special character of optimal caching placement: asρ → ∞, the optimal caching placement n opt satisfies (n opt ) i , Therefore, the total number of helpers is bounded as F l=1 n l ≤ N − 1. This bound implies existence of at least one empty helper, which contradicts the fact that the optimal placement uses up all of helpers' memories. Consequently, the case when (n i , n N −i+1 ) ∈ {(0, 0) , (1, 0)} cannot lead optimal caching placement. Second, let us consider the case when (n i , n N −i+1 ) = (2, 1).
Then, by Proposition 1, n l = 2 for l ≤ i, and n l ≥ 1 for i+1 ≤ l ≤ N −i+1. Using these bound, the total number of helpers is bounded below by F l=1 n l ≥ N + 1. This lower bound implies that the caching placement requires at least N + 1 helpers, which contradicts the fact that we have N caching helpers. Consequently, the case when (n i , n N −i+1 ) = (2, 1) is not feasible. As a result, the optimal caching placement satisfies that (n i , n N −i+1 ) ∈ {(1, 1) , (2, 0)} for i ≤ N 2 .
Using the above property, optimality of the doubly caching placement can be proven as follows.
For each k ∈ 1, ..., N 2 , we will prove there exists an unique range of Zipf exponent which makes doubly caching placement with k optimal. From the fact that we have just shown, as ρ → ∞, optimal caching placement has to satisfy (n k , n N −k+1 ) = (1, 1) or (2, 0) , for k ≤ N 2 .
For the converse, we prove that doubly caching placement with k < N 2 is optimal only if γ 2 (k) ≤ γ ≤ γ 3 (k) and doubly caching placement with k = N 2 is optimal only if γ ≥ γ 2 N 2 . In order to prove the converse, we prove their contrapositions that if γ < γ 2 (k) or γ > γ 3 (k), then doubly caching placement with k < N 2 is not optimal and if γ < γ 2 N 2 , doubly caching placement with k = N 2 is not optimal, respectively.
Consequently, optimal caching placement is to cache the k-th popular file in a single helper. On the other hand, for k ∈ 1, · · · , N 2 − 1 , γ > γ 3 (k) can be rewritten as g channel

k+1
(1) > g file N −k which indicates that optimal caching placement is to cache the k + 1-th popular file in two helpers. Hence, if γ < γ 2 (k) or γ > γ 3 (k), optimal caching placement is to cache the k-th popular file in a single helper or to cache the k + 1-th popular file in two helpers. Therefore, doubly caching placement with k < N 2 is not optimal if γ < γ 2 (k) or γ > γ 3 (k) and doubly caching placement with k = N 2 is not optimal if γ < γ 2 is not optimal. Then, there exists another optimal caching placement. Let us denote optimal caching placement as n opt and doubly caching placement with k = N 2 as n ⌊ N 2 ⌋ . Since Proposition 4 characterizes optimal caching placement in whole range of γ in high SNR regime, n opt has to be doubly caching placement with k < N 2 for some k. If we subtract the average BER of n ⌊ N 2 ⌋ from the that of n opt , the difference must be less than zero due to optimality, i.e., p e (n opt ) − p e n ⌊ N 2 ⌋ < 0. Now, we show the difference becomes larger than zero. The difference of the average BER is expressed as where F 1 is a set of files cached in n opt but not cached in n ⌊ N 2 ⌋ , and F 2 is a set of files cached doubly in n ⌊ N 2 ⌋ but not doubly cached in n opt , respectively. Except for the files in F 1 and F 2 , other elements are the same in n opt and n ⌊ N 2 ⌋ . Therefore, we can express the difference as a function of channel diversity gain and file diversity gain as (a); to be cached only in n opt , the popularity of the file has to be less than N 2 . Also, the files which has lower popularity than N 2 cannot be cached doubly due to Proposition 1 for optimal caching placement. Thus, all the files in F 1 are less popular than all the files in F 2 . If we increase the popularity of the files in F 1 up to the popularity of F 2 , we can make a lower bound (b); Applying (A.1) and (A.2) to the definitions of both diversity gain (11) and (12), we can get (c). (H.4) is greater than zero due to β < 2, which contradicts the supposition that doubly caching placement with k = ⌊ N 2 ⌋ is not optimal.