1

Coded Caching Schemes with Low Rate and
Subpacketizations
Minquan Cheng, Qifa Yan, Xiaohu Tang, Member, IEEE, Jing Jiang

arXiv:1703.01548v3 [cs.IT] 2 Oct 2017

Abstract
Coded caching scheme, which is an effective technique to increase the transmission efficiency during peak traffic times, has
recently become quite popular among the coding community. Generally rate can be measured to the transmission in the peak
traffic times, i.e., this efficiency increases with the decreasing of rate. In order to implement a coded caching scheme, each file
in the library must be split in a certain number of packets. And this number directly reflects the complexity of a coded caching
scheme, i.e., the complexity increases with the increasing of the packet number. However there exists a tradeoff between the rate
and packet number. So it is meaningful to characterize this tradeoff and design the related Pareto-optimal coded caching schemes
with respect to both parameters.
Recently, a new concept called placement delivery array (PDA) was proposed to characterize the coded caching scheme.
However as far as we know no one has yet proved that one of the previously known PDAs is Pareto-optimal. In this paper, we
first derive two lower bounds on the rate under the framework of PDA. Consequently, the PDA proposed by Maddah-Ali and
Niesen is Pareto-optimal, and a tradeoff between rate and packet number is obtained for some parameters. Then, from the above
observations and the view point of combinatorial design, two new classes of Pareto-optimal PDAs are obtained. Based on these
PDAs, the schemes with low rate and packet number are obtained. Finally the performance of some previously known PDAs are
estimated by comparing with these two classes of schemes.
Index Terms
Coded caching scheme, rate, packet number, placement delivery array, lower bound, Pareto-optimal.

I. I NTRODUCTION
Recently, as the wireless data traffic is increasing at an incredible rate dominated by the video streaming, the wireless
network has been imposed a tremendous pressure on the data transmission [1]. Consequently the communication systems are
always congested during the peak-traffic times. So reducing this congestion is very meaningful in wireless network and now
is a hot topic in industrial and academic fields. Caching system, which proactively caches some contents at the network edge
during off-peak times, is a promising solution to reduce congestion (see [2], [5], [6], [8], [10], and references therein).
An important caching system, centralized caching system, is widely studied. In this system, the following scenario are always
focused: a single server containing N files with the same length connects to K users over a shared link and each user has
a cache memory of size M files (see Fig. 1). We call it (K, M, N ) caching system in this paper. In the caching system, a

Fig. 1: Coded caching system
caching scheme consists of two phases: a placement phase during off-peak traffic times and a delivery phase during peak
traffic times. In the placement phase, the server proactively sends some contents in each user’s cache. In the delivery phase,
each user requests for one file from server. And after receiving the requests, server transmits some data to users such that each
M. Cheng and J. Jiang are with Guangxi Key Lab of Multi-source Information Mining & Security, Guangxi Normal University, Guilin 541004, China
(e-mail: {chengqinshi,jjiang2008}@hotmail.com).
Q. Yan and X. Tang are with the Information Security and National Computing Grid Laboratory, Southwest Jiaotong University, Chengdu, 610031, China
(e-mail: qifa@my.swjtu.edu.cn, xhutang@swjtu.edu.cn).

2

user’s demand is satisfied with the help of its caches. Since the placement phase is carried out without any knowledge of the
user requests, it is interested in studying the caching scheme such that the broadcasted amount, which can be satisfied for all
possible user requests, is as small as possible in the delivery phase. This broadcasted amount is called the rate. Clearly the
first objective is to minimize the rate R since it represents the efficiency of a caching scheme.
In the seminal work [10], a coded caching scheme based on network coding theory was proposed for the centralized caching
system. They showed that the rate of a coded caching scheme can be effectively further reduced by jointly designing the
content placement phase and the content delivery phase They also designed the first determined scheme for a (K, M, N )
coded caching system. Such a scheme is referred to as MN scheme in this paper. According to an elaborate uncoded placement
and a coded delivery, they showed that the (K, M, N ) MN scheme is able to reduce the rate R from K(1 − M
N ) of uncoded
KM
caching scheme to K(1 − M
)/(1
+
).
When
N
<
K,
by
employing
coded
multicasting
opportunities
across
users with the
N
N
same demand, an improved coded caching scheme is presented in [18]. When K ≤ N , by means of graph theory, reference
[20] showed that MN scheme has minimum delivery rate under the constraint of uncoded cache placement. So MN scheme
has been also extensively employed in practical scenarios, such as decentralized version [11], device to device networks [7],
online caching update [12], [23] and hierarchical networks [9], [26] and so on. There are also many studies following [10],
for instances, [3], [4], [13], [19], [21], [24] etc.
In order to implement a coded caching scheme, Maddah-Ali and Niesen in [10] showed that each file must be split
 into a
K
certain number of packets. We denote such a number by F . In MN scheme, each file must be divided into KM/N
packets
where KM/N is an integer. Clearly this would become infeasible when K is large. Furthermore, the complexity of a coded
caching scheme increases with the parameter F . So the second objective is to minimize the packets number F , and plays
an important role in the field of coded caching scheme. Aiming at this objective, Shanmugam et al. in [15] first discussed
the problem of subpacketization by grouping method. Recently Yan et al. in [22] characterized the (K, M, N ) coded caching
scheme with F subpacketization by a very interesting F × K array which is called (K, F, Z, S) placement delivery array
(PDA), where M/N = Z/F and R = S/F . Then they proved that MN scheme is equivalent to a special PDA (MN PDA
for short throughout this paper). Furthermore, by increasing little delivery rate, they obtained two infinite classes of PDAs
such that F reduces significantly comparing with that of MN PDA. By increasing more rate several PDAs were constructed
for further reducing the value of F respectively by means of hypergraphs [14], bipartite graphs [25], Ruzsa-Szeméredi graphs
[16], resolvable design [19] and so on. From the above introductions, we can see that there is a tradeoff between rate and
packet number. Clearly it is very interesting to characterize this tradeoff and construct the related Pareto-optimal coded caching
schemes with respect to both parameters. However as far as we know no one has yet proved that one of the previously known
PDAs is Pareto-optimal.
In this paper, we focus on Pareto-optimal PDAs. Firstly two lower bounds on the value of R are derived. Consequently, MN
PDA is a pareto optimal, and a tradeoff between R and F is obtained for some parameters. Secondly, unlike the previously
know strategies of constructing PDAs, we use a different strategy, i.e., we characterize PDAs by means of a set of 3 dimensional
vectors. From this characterization and the above lower bounds, two new classes of Pareto-optimal PDAs are obtained. Based
on these PDAs, the schemes with low rate and packet number are obtained when K ≤ N . Finally the performance of three
previously known schemes are estimated by comparing with these two classes of schemes.
The rest of this paper is organized as follows. Section II briefly reviews the relationship between the coded caching scheme
proposed in [10] and concept of the PDA introduced in [22]. In Section III, two lower bounds on the value of R are derived.
In Section IV, we characterize a PDA by means of a set of 3 dimensional vectors and obtain two new classes of PDAs by the
MN PDA. In Section V we show that these two class of PDAs are Pareto-optimal. Finally for some parameters K, M/N and
R, three comparisons with previously known PDAs are proposed. Conclusion is drawn in Section VII.
II. P RELIMINARIES
In this paper, we denote arrays by bold capital letters, and assume that each entry has exactly one symbol. We use [a, b] =
{a, a + 1, . . . , b} and [a, b) = {a, a + 1, . . . , b − 1} for any integers a and b with a ≤ b.
A. Coded caching schemes
In a (K, M, N ) caching system, we denote the N files by W = {W0 , W1 , . . . , WN −1 } and K users by K = {0, 1, . . . , K−1}.
A coded caching scheme consists of two separated two phases which are introduce by Maddah-Ali and Niesen in [10] as follows:
•

Placement phase: Firstly each file is subdivided into F equal packets, i.e., Wi = {Wi,j : j ∈ [0, F )}. Such a coded
caching scheme is called F -division scheme; Then Each user just caches some part of the packets of all files (This is also
called uncoded placement phase), and uses the same caching policy for all files, i.e., each user caches packets with the

3

•

same indices from all files, where packets belonging to every file is ordered according to a chosen numbering. Denote
Zk the packets cached by user k.
Delivery phase: Each user randomly requests one file from the files set W independently. The request is denoted by
d = (d0 , d1 , · · · , dK−1 ), which indicates that user k requests the dk -th file Wdk for any dk ∈ [0, N ) and k ∈ K. Once the
server received the users’ request d, it broadcasts a signal of at most RF packets to users. Each user is able to recover
its requested file from the received signal with the help of the contents in its own cache.

By the way the assumptions in placement phase are very useful and have been used in many references. Since the placement
phase is carried out without any knowledge of the user requests, we prefer to construct an F -division (K, M, N ) caching
scheme such that the rate R is as small as possible for any request d ∈ [0, N )K . By means of graph theory, reference
[20] showed that the rate of MN scheme is the minimum rate in the uncoded cache placement. However the packet number
K
F = KM/N
is too large when K is large. In order to study the packet number of a coded caching scheme, an interesting
combinatorial structure called placement delivery array, which is introduced in the following subsection, was proposed in [22].
B. Placement delivery array
Definition 1: ([22]) For positive integers K and F , an F × K array P = (pi,j ), i ∈ [0, F ), j ∈ [0, K), composed of a
specific symbol “ ∗ ” called star and S nonnegative integers 0, 1, · · · , S − 1, is called a (K, F, S) placement delivery array
(PDA) if it satisfies C1 in the following conditions:
C1. For any two distinct entries pi1 ,j1 and pi2 ,j2 , pi1 ,j1 = pi2 ,j2 = s is an integer only if
a. i1 6= i2 , j1 6= j2 , i.e., they lie in distinct rows and distinct columns; and
b. pi1 ,j2 = pi2 ,j1 = ∗, i.e., the corresponding 2 × 2 subarray formed by rows i1 , i2 and columns j1 , j2 must be of the
following form




s ∗
∗ s
or
.
∗ s
s ∗
For any positive integer Z ≤ F , P is denoted by (K, F, Z, S) PDA if
C2. each column has exactly Z stars.
And for any positive integer g, a (K, F, Z, S) PDA is said to be g-regular, denoted by g-(K, F, Z, S) PDA, if each integer of
[0, S) appears exactly g times.
Example 1: It is easy to verify that the following array

∗
 ∗

 ∗
P6×4 = 
 0

 1
2

is a 3-(4, 6, 3, 4) PDA:

∗ 0 1
0 ∗ 2 

1 2 ∗ 
.
∗ ∗ 3 

∗ 3 ∗ 
3 ∗ ∗

Given a (K, F, Z, S) PDA P = (pj,k )j∈[0,F ),k∈[0,K) , Yan et al. in [22] showed that an F -division (K, M, N ) coded caching
scheme with M/N = Z/F and R = S/F can be realized by the following rule:
1. Placement Phase: Each file is divided into F equal packets, i.e., Wi = (Wi,0 , Wi,1 , . . . , Wi,F −1 ), i = 0, 1, . . ., N − 1.
Then user k ∈ K caches the packets
Zk = {Wi,j : pj,k = ∗, i ∈ [0, N )}.

(1)

Clearly each user stores N · Z packets by condition C2. So the whole size of cache is N FZ = N M
N = M , which satisfies
the users’ cache constraint.
2. Delivery Phase: Once the server receives the request d = (d0 , d1 , · · · , dK−1 ), at the time slot s, 0 ≤ s < S, it sends
M
Wdk ,j
(2)
pj,k =s,j∈[0,F ),k∈[0,K)

The rate of the scheme is R = S/F for any request d since each file is divided into F equal packets and there are S distinct
integers in P.
Example 2: Given a (4, 6, 3, 4) PDA in Example 1, from the above analysis one can obtain a 6-division (4, 3, 6) coded
caching scheme in the following way.

4

•

•

Placement Phase: First the files are denoted by W0 , W1 , W2 , W3 , W4 , W5 respectively, and each file is divided into F = 6
packets, i.e. Wi = {Wi,0 , Wi,1 , Wi,2 , Wi,3 , Wi,4 , Wi,5 } , i ∈ [0, 6). Then the contents in each user are
Z0 = {Wi,0 , Wi,1 , Wi,2 : i ∈ [0, 6)}

Z1 = {Wi,0 , Wi,3 , Wi,4 : i ∈ [0, 6)}

Z2 = {Wi,1 , Wi,3 , Wi,5 : i ∈ [0, 6)}

Z3 = {Wi,2 , Wi,4 , Wi,5 : i ∈ [0, 6)}

Delivery Phase: Assume that the request vector is d = (0, 1, 2, 3, 4, 5). Table I shows the transmitting process.
Time Slot
0
1
2
3

Transmitted Signnal
W0,3 ⊕ W1,1 ⊕ W2,0
W0,4 ⊕ W1,2 ⊕ W3,0
W0,5 ⊕ W2,2 ⊕ W3,1
W1,5 ⊕ W2,4 ⊕ W3,3

TABLE I: Delivery steps in Example 2
Theorem 1: ([22]) Given a (K, F, Z, S) PDA P = (pj,k )F ×K , one can obtain a corresponding F -division caching scheme
for any (K, M, N ) caching system with M/N = Z/F . Precisely, each user is able to decode its requested file correctly for
any request d at the rate R = S/F .

 K
Theorem 2: (MN PDA,[22]) MN scheme is equivalent to a (t + 1)-(K, Kt , K−1
t−1 , t+1 ) PDA with t stars in each row
where t = KM/N .
When K is very large, Shanmugam et al. in [15] proposed a grouping method to reduce F . That is, for some integers K 0
K
and K, assume that K 0 |K (for the sake of simplicity). First we divide K users into K
0 groups with the same size, then we
use MN PDA for each group. So the following result can be obtained.



k
Lemma 1: ([15]) For any positive integers k, m and t with 0 < t < k, there exists an (mk, kt , k−1
t−1 , m t+1 ) PDA
generated by MN PDA in Theorem 2.
In order to reduce the packet number efficiently while the rate increases a little, the following PDA was constructed.
Lemma 2: ([22]) For any positive integers m and q ≥ 2, there exists a (q(m + 1), (q − 1)q m , (q − 1)2 q m−1 , q m ) PDA.
By increasing more R, there are some other PDAs with smaller F constructed in a different light, such as resolvable design
[19], hypergraphs [14], strongly bipartite graphs [25], Ruzsa-Szeméredi graphs [16] and so on. For example, the following
result is obtained from the view point of hypergraphs.

Lemma 3: ([14]) There exists an ( ml q l , q m (q − 1)l , (q m − q m−l )(q − 1)l , q m ) PDA for any positive integers q ≥ 2, l
and m with l ≤ m.
From the above illustrations, we can study an F -division (K, M, N ) coded caching scheme by means of a (K, F, Z, S)
PDA where M/N = Z/F and R = S/F . And we can see that there is a tradeoff between rate and packet number intuitively.
For convenience, a PDA is called Pareto-optimal if the scheme generated by it achieves the tradeoff between R and F among
the schemes which can realized by PDAs. So in this paper we will consider the tradeoff between the lower bound on R and
F , and then obtain some related classes of Pareto-optimal PDAs. Based on these Pareto-optimal PDAs, we can obtain the
corresponding schemes with low R and F when K ≤ N .
III. L OWER BOUND ON S
In this section, we derive two lower bounds on S for given positive integers K, F and Z of a PDA. According to these
lower bounds, we have that MN PDA is Pareto-optimal, and there exactly exists a tradeoff between the lower bound on R and
F.
A. The first lower bound on S
Now let us consider our first lower bound on S in the following. Let P be a (K, F, S) PDA. For any integer s ∈ [0, S),
assume that there are rs entries in all, say pju ,ku , 1 ≤ u ≤ rs , 0 ≤ ju < F and 0 ≤ ku < K, such that pju ,ku = s. Consider
the subarray formed by rows j1 , · · · , jrs and columns k1 , · · · , krs , which is of order rs × rs since ju 6= jv and ku 6= kv for

5

all 1 ≤ u 6= v ≤ rs from the definition of a PDA. Further,
subarray is equivalent to the following rs × rs array

s
 ∗

P(s) =  .
 ..

we have pju ,kv = ∗ for all 1 ≤ u 6= v ≤ rs . That is to say, this

∗

∗
s
..
.

···
···
..
.

∗
∗
..
.

∗

···

s







(3)

with respect to row/column permutation.
For instance, in Example 1, there are 3 entries p3,0 = p1,1
rows 0, 1, 3 and columns 2, 1, 0 can be obtained.

0
P(0) =  ∗
∗

= p0,2 = 0 of P6×4 . Then the following subarray formed by

∗
∗ 
0

∗
0
∗

Theorem 3: If there exists a (K, F, S) PDA P with n > 0 integer entries and integer set [0, S), then
nF
≤ S.
KF + F − n

(4)

Further the above equality holds if and only if each row has n/F integer entries and each integer s ∈ [0, S) occurs exactly
n/S times.
Proof. Assume that an integer s ∈ [0, S) occurs exactly rs times in P. From (3), there are rs (rs − 1) stars in P(s) . Then the
total number of stars in P(s) , s = 0, 1, . . ., S − 1, is
W =

S−1
X

rs (rs − 1).

(5)

s=0

On the other hand, we can estimate the value of W in a different way. Without loss of generality, assume that K < F , and
row i has exactly ri0 integer entries, denoted by s1,i , . . ., sri0 ,i . Then each star of the i-th row occurs in at most ri0 times in
(s

0

)

P(s1,i ) , . . ., P ri ,i since it occurs in P(sh,i ) at most once for any h ∈ [1, ri0 ]. So the total number of occurrences of all the
stars of P in P(s) , s = 0, 1, . . ., S − 1, is at most
W0 =

F
−1
X

ri0 (K − ri0 ).

(6)

i=0

Clearly W ≤ W 0 , i.e.,
S−1
X

rs (rs − 1) ≤

F
−1
X

s=0

ri0 (K − ri0 ).

i=0

This implies,
S−1
X

rs2 +

s=0

F
−1
X

2

r0 i ≤ Kn + n.

(7)

i=0

Moreover,
S−1
X

1
rs2 ≥
S
s=0

S−1
X

!2
rs

s=0

n2
=
,
S

F
−1
X
i=0

2
r0 i

1
≥
F

F
−1
X
i=0

!2
ri0

=

n2
,
F

(8)

where the equalities hold if and only if r0 = r1 = . . . = rS−1 and r00 = r10 = . . . = rF0 −1 respectively. Combining (7)
and (8), the inequality (4) can be obtained. And the equality in (4) holds if and only if r0 = r1 = . . . = rS−1 = Sn and
r00 = r10 = . . . = rF0 −1 = Fn are positive integers.
From Theorem 3, the following statement can be obtained.
Lemma 4: Given a (K, F, Z, S) PDA P, S =

(F −Z)KF
KZ+F

if and only if it is a g-regular where g = KZ/F + 1.

6

Proof. Clearly n = (F − Z)K. When S =
integer in [0, S) is
g=

(F −Z)KF
KZ+F

, i.e., S =

nF
KF +F −n ,

from Theorem 3 the number of occurrence of each

n
KF + F − n
(F − Z)K
KZ
=
=
=
+ 1.
nF
S
F
F
KF +F −n

KZ
Conversely if P is ( KZ
F + 1) regular, we have S( F + 1) = n by counting the number of integer entries. So

S=

nF
n
K(F − Z)F
(F − Z)KF
=
=
=
.
KZ
F
+
KZ
KF
+
F
−
K(F
−
Z)
Z
1+ F

Lemma 5: ([22]) For a g-(K, F, Z, S) PDA, if g = KZ/F + 1, then F ≥

K
KZ/F



.

From Theorem 3 and Lemma 5, the following result can be obtained.
Theorem 4: For a (K, F, Z, S) PDA with S =
When S =

(F −Z)KF
KZ+F

, i.e., R = S/F =

(F −Z)K
KZ+F

(F −Z)KF
KZ+F

= K(1 −

, then F ≥
M
M
N )/(K N

K
KZ/F



.

+ 1). This is exactly the rate of MN PDA.

Remark 1: In [22], the authors showed that an MN PDA has the minimum number of rows among the g-regular PDAs
M
with the same parameters K, M/N and R = K(1 − M
N )/( N + 1). From Theorem 4, we have that MN PDA is Pareto-optimal.
B. The second lower bound on S
Theorem 5: Given any positive integers K, F, Z with 0 < Z < F , if there exists a (K, F, Z, S) PDA, then

 




 
 
(F − Z)K
F − Z − 1 (F − Z)K
1
2
(F − Z)K
S≥
+
+ ... +
...
...
.
F
F −1
F
Z +1 Z +2
F

(9)

Proof. Suppose that P is a (K, F, Z, S)l PDA. Totally,
there are (F −Z)K integers in this array. Thus, among
there
m
l the F rows,
m
(F −Z)K
must exist one row containing at lest (F −Z)K
integers.
Without
loss
of
generality,
assume
that
these
integers,
F
F
m
l
(F −Z)K
− 1, are in the first row, i.e.,
say 0, 1, . . .,
F
l
m


(F −Z)K
0 1 2 ···
−
1
·
·
·
F





.
P=

.
.
0

. 
P
l
m
If not, we can get such form of P by row/column permutations. Clearly P0 is an ( (F −Z)K
, F − 1, Z, S 0 ) PDA for one
F
l
m
nonnegative integer S 0 . Further, we know that all the integers in [0, (F −Z)K
) do not appear in P0 . Otherwise, it would
F
contradict Property C2. Therefore, we have


(F − Z)K
S≥
+ S0.
(10)
F
l
l l
m mmm
l
(F −Z)K
2
1
...
, Z, Z, 0) PDA. Then,
Perform the same argument to P 0 till that the remaining array is a ( Z+1
Z+2 . . .
F
the bound in (9) follws by recursively applying (10) F − Z times.
l
l
mm
−Z−1) (F −Z)K
Example 3: When K = 6, F = 8 and Z = 5, (F F
= 1. So we have S ≥ 3 + 3 − 1 = 5. It is easy to
−1
F
check that the following array is an optimal (6, 8, 5, 5) PDA .


0 ∗ ∗ ∗ 3 ∗
 1 3 ∗ ∗ ∗ 4 


 ∗ 0 1 ∗ ∗ ∗ 


 2 ∗ 3 ∗ ∗ ∗ 


P8×6 = 

 ∗ 2 ∗ 1 ∗ ∗ 
 ∗ ∗ 4 0 2 ∗ 


 ∗ ∗ ∗ ∗ 1 0 
∗ ∗ ∗ 3 ∗ 2

7

From (9), we have
(F − Z)K
F − Z − 1 (F − Z)K
1
2
(F − Z)K
+
+ ... +
...
F 
F −1
F
Z +1Z +2
 F
F −Z
F −Z −1
1
2
F −Z −1
=K
1+
+ ··· +
···
F
F −1
Z +1Z +2
F −1
(F − Z)K
≥
Z +1

S≥

(11)

since
F −Z −1
2
3
F −Z −1
1
2
F −Z −1
+ ··· +
···
+
···
F −1
Z
+
2
Z
+
3
F
−
1
Z
+
1
Z
+
2
F −1


F −Z −1
1
2
3
F −Z −1
1+
+ ··· + 1 +
···
F −1
Z +1 Z +2Z +3
F −1
F −Z −1
Z +2 2
F −Z −1
1+
+ ... +
...
F −1
Z +1Z +2
F −1
F −Z −1
2
3
F −Z −1
1+
+ ··· +
...
F −1
Z +1Z +3
F −1
F −Z −1 F −2F −Z −2 3 F −Z −1
1+
+
F −1
Z +1 F −2 Z +3 F −1
F −Z −1 F −Z −2F −Z −1
1+
+
Z
F −1
 F −1
+ 1
F −Z −2 F −Z −1
1+ 1+
Z +1
F −1
F −Z −1
F
1+
=
.
Z +1
Z +1
1+

=
=
=
=
=
=
=

Given a positive integer K and a positive real number M/N , let Z/F = M/N . Then the following inequality can be obtained
by (11).
R=

K(1 − M
S
N)
≥
M
F
F N +1

(12)

From the above formula, we can see that the lower bound on R increases with F decreasing for any fixed K and M/N . And
we will show that the equality in (12) holds for some fixed parameters in Subsection V-B. However we claim that this lower
K(1− M
N )
bound is not tight when F > K since reference [20] showed that R = KM +1
is the minimum rate. When F > K,
N

M
N)

M
N)

K(1 −
K(1 −
< KM
FM
N +1
N +1
holds for any positive integers K, M and N . Clearly this is impossible.

Unfortunately according to these two lower bound on S in this section, it is not easy to check whether one of the other
know PDAs is Pareto-optimal. But according to the two new classes of PDAs obtained in Section IV, we can estimate the
performance of some known PDAs indirectly in Section VI.
IV. C HARACTERIZATION OF PDA FROM COMBINATORIAL DESIGNS
In this section, we characterize a PDA by means of a set of 3 dimensional vectors. Consequently several classes of PDAs
are obtained. For ease of exposition, an F × K array P = (pi,j ), 0 ≤ i < F , 0 ≤ j < K, on [0, S) ∪ {∗} will be represented
by a set of ordered triples C = {(i, j, pi,j )T |pi,j ∈ [0, S)} in this section. Clearly an array corresponds to an unique vector
set, and the converse is also correct. So we assume that C ⊆ [0, F ) × [0, K) × [0, S) and is called the incidence set of P in
the following.
Example 4: The (4, 6, 3, 4) PDA P6×4
is a vector.

0
C= 2
0

in Example 1 can be represented by the following vector set where each column
0
3
1

1
1
0

1
3
2

2
1
1

2
2
2

3
0
0

3
3
3

4
0
1

4
2
3

5
0
2


5
1 
3

8

Let x and y be elements of C. The (Hamming) distance between x and y, denoted by d(x, y), is defined to be the number
of coordinates at which x and y differ. And the (minimum) distance of C, denoted by d(C), is
d(C) = min{d(x, y) | x, y ∈ C, x 6= y}.
For instance, d(C) = 2 in Example 4. Furthermore it is easy to
4, where i1 6= i2 ∈ [0, 6), j1 6= j2 ∈ [0, 4) and a 6= b ∈ [0, 4).

i1 i1
4 =  j1 j2
a b

check that the following 4 is not a subset of C in Example

i2
j2 
a

(13)

In fact, we can show that 4 6⊆ C from C1. We call such 4 a forbidden configuration of C.
Theorem 6: There exists a (K, F, S) PDA with n integer entries if and only if there exists a set C with cardinality n
satisfying
P1: the minimum Hamming distance is at least 2, and
P2: 4 in (13) is the forbidden configuration.
Proof. Given a (K, F, S) PDA P, denote its incidence set by C. Clearly the number of integer entries equals the order of C.
Firstly, assume that there exist two distinct vectors, say (i1 , j1 , a1 )T and (i2 , j2 , a2 )T ∈ C, with distance less than 2. It is easy
to check that at most one of equalities i1 = i2 and j1 = j2 holds since every entry has at most one symbol in P. Without loss
of generality we assume that i1 = i2 . Then we have a1 = a2 . This contradicts C1-a) of Definition 1. So P1 holds. Secondly,
suppose that 4 in (13) is a subset of C. Then we have pi1 ,j1 = pi2 ,j2 = a, pi1 ,j2 = b, a, b ∈ [0, S), a contradiction to C1-b)
of Definition 1. So P2 holds.
Conversely, assume that a set C with cardinality n satisfies P1 and P2. From P1, for any integers i ∈ [0, F ) and j ∈ [0, K),
there is at most one integer a ∈ [0, S) such that (i, j, a)T ∈ C. Then we can define an F × K array P = (pi,j ) in the following
way:

a if (i, j, a)T ∈ C,
(14)
pi,j =
∗ otherwise.
Clearly there are n integer entries, and the integer set is [0, S). For any two distinct entries pi1 ,j1 and pi2 ,j2 , assume that
pi1 ,j1 = pi2 ,j2 = s ∈ [0, S). Then i1 6= i2 and j1 6= j2 hold from P1. So C1-a) holds. And pi1 ,j2 = pi2 ,j1 = ∗. Otherwise,
without loss of generality, suppose that pi1 ,j2 ∈ [0, S). Then by (14), there exists a subset 4 = {(i1 , j1 , s)T , (i1 , j2 , pi1 ,j2 )T ,
(i2 , j2 , s)T } ⊆ C, a contradiction to P2. So C1-b) holds.
From Theorem 6, we can study PDA by means of discussing its incidence set C. Given a set C, conjugates of C are defined
by rearranging the coordinates of C. Let C(l0 ,l1 ,l2 ) be the conjugate set obtained by rearranging the coordinates of C in the
order (l0 , l1 , l2 ) ∈ L, where L is the set formed by all the permutations of [0, 3). For instance, C can be written as C(0,1,2) .
C(2,1,0) is obtained by changing the first coordinate and the third coordinate of C. It is very easy to verify that the following
statement holds.
Lemma 6: C satisfies P1 and P2 if and only if its conjugates satisfy P1 and P2.
Theorem 7: Let P be a (K, F, Z, S) PDA for some positive integers K, F , Z and S with 0 < Z < F . Then
1) there exists an (K, S, S − (F − Z), F ) PDA;
2) if P is g-regular, then there exist an (S, F, F − g, K) PDA and an (S, K, K − g, F ) PDA;
3) if each row has h integer entries in P, then there exist an (F, S, S − h, K) PDA and an (F, K, K − h, S) PDA.
Proof. Let C be the incidence set of P. Now let us consider the conjugates of C.
•

•

•

When (l0 , l1 , l2 ) = (2, 1, 0), C(2,1,0) ⊆ [0, S) × [0, K) × [0, F ) satisfies P1 and P2 from Lemma 6. Then P(2,1,0) generated
by C(2,1,0) in (14) is a (K, S, F ) PDA from Theorem 6. It is easy to check that each integer in [0, K) occurs F − Z
times in the second coordinate of C. This implies that each column of P(2,1,0) has S − (F − Z) stars. So P(2,1,0) is a
(K, S, S − (F − Z), F ) PDA.
When (l0 , l1 , l2 ) = (0, 2, 1), C(0,2,1) ⊆ [0, F ) × [0, S) × [0, K) satisfies P1 and P2 from Lemma 6. Then P(0,2,1) generated
by C(0,2,1) in (14) is an (S, F, K) PDA. If P is g-regular, i.e., each integer, say s ∈ [0, S) occurs g times in P, then s
occurs g times in the third coordinate of C. This implies that each column of P(0,2,1) has F − g stars. So P(0,2,1) is an
(S, F, F − g, K) PDA. Similarly we can show that P(1,2,0) is an (S, K, K − g, F ) PDA.
When (l0 , l1 , l2 ) = (2, 0, 1), C(2,0,1) ⊆ [0, S) × [0, F ) × [0, K) satisfies P1 and P2 from Lemma 6. Then P(2,0,1) generated
by C(2,0,1) in (14) is an (F, S, K) PDA. If each row has h integer entries in P, i.e., each integer, say f ∈ [0, F ) occurs

9

h times in the first coordinate of C, then each column of P(2,0,1) has h integers. That is, each column has S − h stars.
So P(2,0,1) is an (F, S, S − h, K) PDA. Similarly we can show that P(1,0,2) is an (F, K, K − h, S) PDA.

From Theorems 2 and 7, the following result can be obtained.
Theorem 8: For any positive integers k and t with 0 < t < k − 1, we have the following PDAs.

 k 
(a) (t + 1)-(k, kt , k−1
, t+1 ) PDA with t stars in each row;
t−1



k
k−1
k
(b) (k, t+1 , t+1 , t ) PDA;
 k k
k
(c) ( t+1
, t , t − (t + 1), k) PDA;


k
, k, k − (t + 1), kt ) PDA;
(d) ( t+1
 k  k 
(e) ( kt , t+1
, t+1 − (k − t), k) PDA;


k
(f) ( kt , k, t, t+1
) PDA.
For 0 < t0 < k − 1, let t = k − t0 − 1. Clearly
8-(c) and 8-(f) to t = k − t0 − 1, we
 k 0 < kt <
 k − 1. Applying Theoremk8-(a),

k
k−1
k
k
can obtain (k, t+1 , t+1 , t ) PDA, ( t , t+1 , t+1 − (k − t), k) PDA and ( t+1 , k, k − (t + 1), kt ) PDA, i.e., Theorem
8-(b), 8-(d) and 8-(e). So we only need to consider the PDAs in Theorem 8-(a), 8-(c) and 8-(f).
The subcase (a), i.e., MN PDA, in Theorem 8 has been full discussed. Now let us consider the subcases (c) and (f). In the
following, we will show that the PDAs in Theorem 8-(c) and 8-(f) are Pareto-optimal by the two lower bounds on the value
of S in Section III.
V. T WO PARETO - OPTIMAL PDA S
We first consider the PDAs in Theorem 8-(c) and 8-(f) using the lower bound on the value of S respectively. Then we
show that there exactly exists a tradeoff between rate R and F of the code caching schemes generated by the PDAs for some
parameters.
A. The first Pareto-optimal PDA
From Theorem 5 and Theorem 8-(c), the following result can be obtained.
 k k
k
Theorem 9: The ( t+1
, t , t − (t + 1), k) PDA P1 in Theorem 8-(c) is Pareto-optimal.


k
k
Proof. From Theorem 1, a coded caching scheme with K = t+1
, M/N = 1 − t+1
and R = kk can be obtained
k , F =
t
(t)
(t)

by P1 . First for any positive integer F 0 < kt , assume that there exists a (K, F 0 , Z, S) PDA with Z = F 0 (1 − t+1
). We will
(kt)

show that the corresponding rate R = S/F 0 > k/ kt . According to (9)
 0

F (t+1) k 
 0

k
(F − Z)K
F 0 (t + 1)
 ( t ) t+1  F 0 (t + 1)
0
S≥
−
1
=
k
−
t
−
1
+
+
F
−
Z
−
1
=
+

 .


k
k


F0
F0
t
t


So we have
S
R= 0 ≥
F

k−t−1+
F0

F 0 (t+1)

(kt)

=

k
k−t−1 t+1
+ k > k .
0
F
t
t


Conversely we claim that for any positive real number R < kk , the corresponding F 0 > kt always holds. Assume that
(t)
 0 0

0
(kt)
k
k
k
0
0
0
0 t+1
0
there exists a ( t+1
, F , F (1 − t+1
and K
0 <
k ), K ) PDA P with F ≤
k . Let x = F
k , i.e., F = x t+1 . It is easy
t
F
(t)
(t)
(t)
to check that the number of integer entries in P0 is
!! 



t+1
k
k
0
0
n = F − F 1 − k
= F 0 (k − t) =
x.
t+1
t+1
t

k
0
Let C 0 be the incidence set of P0 . Then C(0,2,1)
⊆ [0, F 0 ) × [0, K 0 ) × [0, t+1
) satisfies P1 and P2 from Lemma 6. So P0(0,2,1)

k
0
generated by C(0,2,1)
in (14) is a (K 0 , F 0 , t+1 ) PDA from Theorem 6. From (4) we have
' 
 0



 &

k
k
nF 0
k
x
t+1 xF
0
≥S ≥
=
≥
.
(15)
t+1
K 0F 0 + F 0 − n
K 0 F 0 + F 0 − F 0 (k − t)
t + 1 K 0 + 1 − (k − t)

10

So we have
holds

x
K 0 +1−(k−t)

≤ 1. Clearly we have K 0 + 1 − (k − t) > 0 since K 0 F 0 + F 0 − n > 0. Then the following inequality
K 0 − k + (t + 1) ≥ x ≥ 1.

From hypothesis

(16)

k
K0
K0
=
>

k
x(kt)
F0
t
t+1

we have
k
K0
K0
>
≥ 0
.
t+1
x
K − k + (t + 1)
Then

t+1
K 0 − k + (t + 1)
.
<
k
K0

That is

k−t−1
k−t−1
<
.
K0
k

This implies K 0 > k since t < k − 1. So we have R =

F > kt if R < kk .
(t)

K0
F0

>

k

(kt)

, a contradiction to our hypothesis

K0
F0

<

From Theorem 1, the parameters of the scheme generated by P1 can be obtain as follows.


 
M1
k
t+1
k
k
= 1 − k , K1 =
, F1 =
, R1 = k .
N1
t+1
t
t
t

k

(kt)

. Then we have

(17)

1
From Theorem 9, this scheme has not only the low rate for the fixed parameters K1 , M
N1 and F1 , but also the low packet
M1
number for the fixed parameters K1 , N1 and R1 . In the following, by comparing the performance with MN PDA, we will
 M
k
t+1
1
show that there exits a tradeoff between F and R for the fixed parameters K1 and M
N1 . When K = t+1 , N = 1 − (k) , from
t
Theorem 2 we have an MN PDA (K, FM N , ZM N , SM N ) PDA, where


 

  k 

 
k
k
k
t+1
t+1
t+1
t+1
FM N =
=
and
SM N =
=
.


k
k
t+1
t+1
k−t
k−t−1
t+1 (1 − (k) )
t+1 (1 − (k) ) + 1
t
t

Then
RM N =

SM N
=
FM N

k
t+1



k−t
.
−k+t+1

From (17), we have

k
F1
t
=
≤
k
(t+1
)
FM N

!k−t

k
k
t+1



k−t

and

R1
k
k
k
=
− k +
.
RM N
t+1
(k − t) kt
t

The first item in (18) is derived by the following fact.

k(k−1)...(t+1)
k
t
k
t+1

(

)

=

(k−t)!

k
t+1

k
k
)((t+1
)−1)...((t+1
)−k+t+1)
(k−t)!

(

k−t

=

≤

k
k
t+1



k
k
t+1

k−1
...

k
t+1 − 1
!k−t

k
t+1



=

k
t+1



(

(18)

k(k − 1) . . . (t + 1)


k
− 1) . . . ( t+1
− k + t + 1)

k
t+1

t+1
−k+t+1



k
≥ k−x
for any positive integer x ∈ [1, k − t).
k
k
(t+1
)
(t+1
)−x
1
Remark 2: MN PDA with the parameters K1 and M
N1 in (17) could achieve the minimum rate, but its F is at least
k


k
k
k
t+1)
. By (18), if F reduces by more than ( t+1
F = (k−t
− kk + (k−t)
/k)k−t times, the rate must increase at least t+1
(kt)
(
)
t
 k−t
k
k
times. In other words, if R increases by a factor of t+1 times, then F could decrease by more than ( t+1 /k)
times.

The last inequality of the above formula holds due to

11

Example 5: Let t = k − 3. By (18) we have
F
8k − 16
=
FM N
((k − 1)k − 4) ((k − 1)k − 2)

and

R
k
4
=
−
.
RM N
k − 2 (k − 1)(k − 2)

According to above formula, the following table can be obtained.
k
K
F
FM N
R
RM N

5
10
0.194
1.333

6
20
0.088
1.3

B. The second optimal PDA

Theorem 10: The ( kt , k, t,

7
8
35
56
0.047 0.028
1.267 1.238

k
t+1



9
10
84
120
0.018 0.013
1.214 1.194

11
165
0.009
1.178

12
13
220
286
0.007 0.005
1.164 1.152

14
364
0.004
1.141

15
455
0.003
1.132

) PDA P2 in Theorem 8-(f) is Pareto-optimal.


(k)
Proof. From Theorem 1, a coded caching scheme with K = kt , M/N = t/k, F = k and R = t+1
can be obtained by
k
P2 . Clearly F ≤ K. So we only need to consider the relationship between R and F in (12). It is easy to check that (12) is a
monotonic decreasing function of F . So we only need to check whether the equality in (12) holds for the parameters K, F ,
M/N and R. Then the result directly follows from (12), i.e.,



k
k
k k−t
K(1 − M/N )
t+1
t+1
t
k
≥
= t
.
=
R=
k
F M/N + 1
k
kk + 1

From Theorem 1, the parameters of the scheme generated by P2 can be obtain as follows.

 
k
M2
k
t
t+1
, F2 = k, R2 =
.
= , K2 =
N2
k
t
k

(19)

2
From Theorem 10, this scheme has not only the low rate for the fixed parameters K2 , M
N2 and F2 , but also the low packet
M2
number for the fixed parameters K2 , N2 and R2 . Similarly by comparing the performance with MN PDA in the above
2
subsection, we will also show that there exactly exists a tradeoff between F and R for the fixed parameters K2 and M
N2 in

k
M
t
(19). When K = t and N = k , from Theorem 2 we have an MN PDA (K, FM N , ZM N , SM N ) PDA P, where
 
 k   k 

k
t
t
t
FM N = k t = k−1
and SM N = k t
.
t k
t−1
t k +1

Then

 
k
SM N
k−t
= k
.
FM N
t t +k t

RM N =
From (19), we have
F2
=
FM N

k
≤k
(kt) 
(k−1
t−1 )

 (k−1
t t−1 )
k
k
t −x
k−1
t−1 −x

()

≥

R2
=
RM N

and
k
t
k−1
t−1

()

k
t




=

for any integer x ∈ [1,



k−1
1
+1
t−1
t+1
k−1
t−1



(20)

).
( )
( )
2
Remark 3: MN PDA with the parameters K2 and M
N2 in (19) could achieve the minimum rate, but its F is at least
k

k−1
(t) 
. From (20), if F reduces by more than ( kt )( t−1 ) times, the rate must increase at least k−1
t−1 times. In other words, if
(k−1
)
t−1

k−1
k ( t−1 )
R increases about k−1
times.
t−1 times, then F could decrease by more than ( t )
where the first inequality holds due to

=

k
t+1 /k

k
k−t
k
t
t( t )+k

Example 6: When t = 2, by (20), we have
F2
=
FM N

k
=
(kt) 
k−1
( t−1 )

k
k
≤ k k−1
(k2) 
(2)

k−1

and

R2
k
= ,
RM N
3

12

where the first item holds due to ( ml )l ≤
obtained.
k
F2
FM N
R2
RM N

4
0.2000
1.3

5
2.3810 · 10−2
1.7

m
l



for any positive integers m and l with l ≤ m. Then the following table can be

6
1.9980 · 10−3
2.0

7
1.2900 · 10−4
2.3

8
6.7565 · 10−6
2.7

9
2.9742 · 10−7
3.0

10
1.1285 · 10−8
3.3

VI. T HE PERFORMANCE OF PREVIOUSLY KNOWN PDA S
In fact, comparing the two Pareto-optimal PDAs in the above section, we can estimate the performance of some previously
known results. In this section, we will have the following statements.
•
•
•

Comparison 1: For the same parameters K, M/N and R, the packet number of the scheme generated by P2 is far less
than that of PDA in Lemma 1. This implies that the PDA in Lemma 1 is not Pareto-optimal for some K and M/N ;
Comparison 2: The packet number of the scheme generated by P1 significantly decrease by increasing a little delivery
rate R comparing with that of the PDA in Lemma 2;
Comparison 3: For some parameters K and M/N , the performance of P1 is better than that of the PDA in Lemma 3,
i.e., both the rate and the packet number of the scheme generated by P1 are smaller than that of the PDA in Lemma 3.
This implies that the PDA in Lemma 3 is not Pareto-optimal for some K and M/N ;

Now let us introduce above three comparisons one by one.
A. Comparison 1
For any positive integers K and K 0 with K 0 |K, let m = K/K 0 . From Lemma 1, we have a (K,

K0
m KM/N
+1 ) PDA. From Theorem 1,



K0
m KM/N
K 0 (1 − M
K0
+1
0
0
N) K
=
.
F =
and
R
=

0
K
M
0
0
K M/N
1 + K N K0
KM/N

K0
KM/N



,

K 0 −1
KM/N −1



,

For any positive integers k and t, now let us consider the performance of the PDA in Lemma 1 and Theorem 10. Assume
 
k
M
t
K=
and
= .
t
N
k
From Theorems 1 and 10, we have
k
t+1



F2 = k

and

R2 =

k

 
k−t k
=
.
k(1 + t) t

0

Assume that R = R2 , i.e.,
 
 
K 0 (1 − kt ) K
k−t k
k−t k
=
=
.
k(1 + t) t
k + K 0t t
1 + K 0 kt K 0
Then we have K 0 = k. So we have

F2
k
= k .
F0
t



k
Remark 4: From the above discussion, for same parameters K = kt , M
= kt and R = t+1
/k, the row number F 0 of
N

the PDA in Lemma 1 is kt /k times larger than that of P2 in Theorem 8-(c), where k, t are any positive integers with t < k.
So the PDA in Lemma 1 is not Pareto-optimal when any 1 < t < k − 1.
B. Comparasion 2
Let us consider the (q(m + 1), (q − 1)q m , (q − 1)2 q m−1 , q m ) PDA P3 in Lemma 2. From Theorem 1, the parameters of
the scheme generated by P3 can be obtained as follows.
M3
1
1
= 1 − , K3 = q(m + 1), F3 = q m (q − 1), R3 =
N3
q
q−1

13

From (17), assume that

M3
N3

=

M1
N1

and K3 = K1 , i.e.,
1
t+1
1 − = 1 − k
q
t



k
t+1

and


= q(m + 1),

for some positive integers m, t and k. Then we have
m+1=k−t
and


k
k
F1
t
t
= m
=  k k−t−1  k
F3
q (q − 1)
(t)
(t)
t+1

t+1

−1

k
R1
(q − 1)k
k
=
− k .
 =
k
R3
t
+
1
t
t

,

(21)

Now let us consider the values of F1 /F3 and R1 /R3 according to 0 < t < k − 1.
•

When t = k − 2, (21) can be written in the following way.
F1
2(k − 1)
=
F3
k−2

•

R1
k−2
=
R3
k−1

When t ≤ k − 3, (21) can be written in the following way.
R1
k
k
=
− k
R3
t+1
t

F1
t+1
≤ k−t−2
F3
k
(k − 1)

(22)

The first above item is derived by the following fact when 3 ≤ t ≤ k − 3.

k
k(k − 1) . . . (t + 1)
k−1k−2
t+3t+2
t
=
=k
...
≥k
t+1
(k − t)!(t + 1)
t t−1
3·2 4
Remark 5: By comparing P3 in Lemma 2 above, the row number of P1 in Theorem 8-(c) decreases by more than k k−t−2
k
times, but R increases about t+1
times for some parameters t and k.
Example 7: When K1 = K3 and
and q.

M3
N3

=

k
6
6
7
7
8
8
9
9
10

M1
N1 ,

t
2
3
2
4
3
4
2
6
2

the following table can be obtained for some small positive integers k, t, m

m
3
2
4
2
4
3
6
2
7

q
F1 /F3
5
0.03
5
0.2
7
0.001457
7
0.119048
14 0.000112
14 0.001962
12 0.000001
12
0.05303
15 0.00000002

R1 /R3
1.6
1.2
2
1.2
1.85714
1.48571
2.75
1.17857
3.11111

C. Comparison 3

Finally let us consider the ( ml q l , q m (q − 1)l , (q m − q m−l )(q − 1)l , q m )PDA P4 in Lemma 3 for any positive integers q ≥ 2,
l and m with l ≤ m. From Theorem 1, the parameters of the scheme generated by P4 can be obtain as follows.
 
1
m l
1
M4
= 1 − l , K4 =
q , F4 = q m (q − 1)l , R4 =
.
N4
q
l
(q − 1)l
From (17), assume that

M1
N1

≤

M4
N4

and K1 ≥ K4 , i.e.,
1−

t+1
1
 ≤ 1 − l and
k
q
t



k
t+1



≥ ql

 
m
l

for some positive integers m, t, l and k with t ≤ k and l ≤ m. So we have
 
 
 
k
k
m t+1
q l (t + 1) ≥
and
≥ ql
.
t
t
l k−t

(23)

14

This implies
k
t



t+1

k−t

m

!1/l

l

≥q≥

k
t

 !1/l

 
m
≤ k − t.
l

and

t+1

Then we have

k
q l (t + 1)
t+1
F1
t
≤
= m−l
= m
F4
q (q − 1)l
q m (q − 1)l
q
(q − 1)l

(24)

 q − 1 l k k − t
R1
k(q − 1)l
k(q − 1)l

.
=
≤
=

t+1
k
R4
q
t + 1 ml
q l ml k−t
t

(25)

With the aid of a computer, we can find out some parameters K, t, m and l listed in the following example satisfying
K1
≥ 1,
K4

M1
M4
≤
,
N1
N4

F1
<1
F4

and

R1
< 1.
R4

(26)

Example 8: Let l = m − 1 in Lemma 3. The following table can be obtained by (24) and (25).
k
7
25
9
13
14
17
20
11
13
13
13
16
18
19
23
25
15
17
17
17
19
20
20
20
21
21
23
23
23
26
28

t m
3 3
22 3
4 4
7 4
9 4
12 4
15 4
5 5
5 5
6 5
7 5
9 5
10 5
12 5
17 5
19 5
7 6
7 6
8 6
9 6
11 6
9 6
10 6
11 6
13 6
14 6
14 6
15 6
16 6
18 6
21 6

q K1 /K4
3 1.2963
10 7.6667
3 1.1667
6 1.9861
6 2.3171
8 3.0215
10 3.8760
3 1.1407
4 1.0055
4 1.3406
4 1.3406
6 1.7654
8 2.1366
8 2.4604
9 3.0772
10 3.5420
4 1.0474
5 1.0372
5 1.2965
5 1.2965
6 1.6200
7 1.6656
7 1.8321
7 1.6656
7 2.0179
6 2.4923
9 2.3065
8 2.4939
7 2.4311
10 2.6038
9 3.3420

M1 M4
N1 / N4

0.9964
1
0.9973
1
0.9996
0.9999
1
0.9994
0.9992
0.9998
0.9992
0.9999
1
1
1
1
0.9997
0.9999
0.9999
0.9999
1
1
1
1
1
1
1
1
1
1
1

F1 /F4
0.6481
0.2556
0.7778
0.2648
0.3090
0.2158
0.1723
0.9506
0.4189
0.5586
0.5586
0.2942
0.1908
0.2197
0.2137
0.1968
0.5237
0.3112
0.3890
0.3890
0.3240
0.2379
0.2617
0.2379
0.2883
0.4985
0.1922
0.2672
0.3473
0.1736
0.2785

R1 /R4
0.8000
0.8804
0.5714
0.9470
0.8741
0.9423
0.9404
0.3810
0.8182
0.6136
0.6136
0.8741
0.9877
0.9054
0.9332
0.9262
0.5664
0.8951
0.7161
0.7161
0.7856
0.9259
0.8418
0.9259
0.8025
0.5644
0.9223
0.7884
0.7295
0.9827
0.7749

In fact, we can find out several classes of the parameters k, t, m and l with 0 < t < k − 1 and 1 ≤ l < m such that (26)
holds. First we can obtain that
 !1/l 
 k−t−1
k
l
k
t
q≥
≥
(27)
t+1
k−t

15

since
k
t



k
k−t



k(k − 1) . . . (t + 1)
k
k−1
t+2t+1
=
=
=
...
≥
t+1
t+1
(k − t)!(t + 1)
k−tk−t−1
2 t+1
The last item is derived by the fact that

k
k−t

<

k−x
k−t−x

k
k−t

k−t−1

where 1 ≤ x < k − t.

Moreover we have k − t − 1 ≥ l since
k−t≥
This implies that q >



 
m
≥ m ≥ l + 1.
l

k
k−t

from (27). Submitting this inequality into (24) and (25), the following results can be obtained.

l 
m−l

l
F1
k−t
k−t
k−t
R1
k k−t
.
< (t + 1)
<
(28)
F4
t
k
R4
t
t + 1 ml

Clearly from (23) and (28), for some parameters k, t, m and l, (26) always holds. For instance, when 41 ≤ t = k − 6 and
1 < l < m, from (28) we have

l  m−l

l−1  m−l−1
36(k − 5)
36(k − 5)
6
6
6
6
F1
=
≤
< (k − 5)
,
F4
k−6
k
k(k − 6) k − 6
k
k(k − 6)
l

l−1

6
6
R1
k
36k
6
36k

.
<
≤
<
m
R4
k−6 k−5 l
(k − 5)(k − 6) k − 6
(k − 5)(k − 6)
√

36k
1
2089 = 46.352, F1 /F4 < 1 and R1 /R4 < 1 always hold.
Clearly when 0 < 36(k−5)
k(k−6) < (k−5)(k−6) < 1, i.e., k > 2 47 +
Remark 6: By the above comparison, both the parameters F and R of P1 in Theorem 8-(c) are smaller than that of P4
in Lemma 3 even if K ≥ K4 and M1 /N1 ≤ M4 /N4 for some positive integers k, t, m, l and q. So the PDA in Lemma 3 is
not Pareto-optimal for some parameters K and M/N .
VII. C ONCLUSION
In this paper, we considered Pareto-optimal PDAs for some parameters K and M/N . Firstly two lower bounds on the
value of R were derived. Consequently, MN PDA was pareto optimal, and a tradeoff between the lower bound on R and F
was obtained for some parameters. Secondly, unlike the previously know strategies of constructing PDAs, we used a different
strategy, i.e., we characterized PDAs by means of a set of 3 dimensional vectors. From this characterization and the above
lower bounds, two new classes of Pareto-optimal PDAs were obtained. Based on these two new PDAs, the schemes with
low rate and packet number were obtained. Finally the performance of three previously known schemes were estimated by
comparing with these two classes of PDAs.
It is interesting to prove that one class of the other previously known PDAs is Pareto-optimal for some parameters K and
M/N . And it would be meaningful to characterize the tradeoff between R and F for the other parameters K and M/N and
construct the related Pareto-optimal PDAs.
R EFERENCES
[1] White paper: Cisco VNI forecast and methodology, 2015-2020, Tech. Report, 2015.
[2] K. C. Almeroth and M. H. Ammar, The use of multicast delivery to provide a scalable and interactive video-on-demand service, IEEE Journal on Selected
Areas in Communications, vol. 14, no. 6, pp. 1110-1122, 1996.
[3] M. M. Amiri and D. Gündüz, Fundamental limits of caching: Improved delivery rate-cache capacity trade-off, IEEE Transactions on Communications,
vol. 65, no. 2, pp. 806-815, 2017.
[4] H. Ghasemi and A. Ramamoorthy, Improved lower bounds for coded caching, in Proc. IEEE International Symposium on Information Theory, Hong
Kong, Jun. 2015, pp. 1696-1700.
[5] N. Golrezaei, A. F. Molisch, A. G. Dimakis, and G. Caire, Femtocaching and device-to-device collaboration: A new architecture for wireless video
distribution, IEEE Communications Magazine, vol. 51, no. 4, pp. 142-149, 2013.
[6] M. Gregori, J. Gomez-Vilardebo, J. Matamoros, and D. Gündüz, Wireless content caching for small cell and D2D networks, IEEE Journal on Selected
Areas in Communications, Vol. 34, no. 5, pp. 1222-1234, 2016.
[7] M. Ji, G. Caire and A. F. Molisch, Fundamental Limits of Caching in Wireless D2D Networks, IEEE Transactions on Information Theory, vol. 62, no.
2, pp.849-869, 2016.
[8] M. Ji, A. M. Tulino, J. Llorca, and G. Caire, Order-optimal rate of caching and coded multicasting with random demands, in Proc. 11th International
Symposium on Wireless Communications Systems, Barcelona, Aug. 2014, pp. 922-926.
[9] N. Karamchandani, U. Niesen, M. A. Maddah-Ali, and S. Diggavi, Hierarchical coded caching, in Proc. IEEE International Symposium on Information
Theory, Honolulu, HI, Jun. 2014, pp. 2142-2146.
[10] M. A. Maddah-Ali and U. Niesen, Fundamental limits of caching, IEEE Transactions on Information Theory, vol. 60, no. 5, pp. 2856-2867, 2014.
[11] M. A. Maddah-Ali, Urs Niesen, Decentralized coded caching attains order-optimal memory-rate tradeoff, EEE/ACM Transactions on Networking, vol.
23, no. 4, pp.1029-1040, 2015.

16

[12] R. Pedarsani, M. A. Maddah-Ali, and U. Niesen, Online coded caching, in Proc. IEEE International Conference on Communications, Sydney, Australia,
Jun. 2014, pp. 1878-1883.
[13] A. Sengupta, R. Tandon, and T. C. Clancy, Improved approximation of storage-rate tradeoff for caching via new outer bounds, in Proc. IEEE International
Symposium on Information Theory, Hong Kong, Jun. 2015, pp. 1691-1695.
[14] C. Shangguan, Y. Zhang, G. Ge, Centralized coded caching schemes: A hypergraph theoretical approach, arXiv:arXiv:1608.03989 [cs.IT], Aug. 2016.
[15] K. Shanmugam, M. Ji, A. M. Tulino, J. Llorca, and A. G. Dimakis, Finite-length analysis of caching-aided coded multicasting, IEEE Transactions on
Information Theory, vol. 62, no. 10, pp. 5524-5537, 2016.
[16] K. Shanmugam, A. M. Tulino, and A. G. Dimakis, Coded caching with linear subpacketization is possible using Ruzsa-Szemredi graphs, in Proc. IEEE
International Symposium on Information Theory, Aachen, June 2017, pp. 1237-1241.
[17] I. Tamo, Z. Wang, and J. Bruck, Zigzag codes: MDS array codes with optimal rebuilding, IEEE Transactions on Information Theory, vol. 59, no. 3, pp.
1597–1616, 2013.
[18] C. Tian and J. Chen, Caching and delivery via interference elimination, in Proc. IEEE International Symposium on Information Theory, Barcelona, July
2016, pp. 830-834.
[19] L. Tang, A. Ramamoorthy, Coded caching with low subpacketization levels, GLOBECOM Workshops 2016: 1-6.
[20] K. Wan, D. Tuninetti and P. Piantanida, On the optimality of uncoded cache placement, in Proc. IEEE Information Theory Workshop, Robinson College,
Sept. 2016, pp. 11-14.
[21] C. Y. Wang, S. H. Lim, M. Gastpar, A new converse bound for coded caching, in Proc. IEEE Information Theory Workshop, Robinson College, Oct.
2016.
[22] Q. Yan, M. Cheng, X. Tang and Q. Chen, On the placement delivery array design in centralized coded caching scheme, IEEE Transactions on Information
Theory, vol. 63, no. 9, pp. 5821-5833, 2017.
[23] Q. Yan, U. Parampalli, X. Tang, and Q. Chen, Online coded caching with random access, IEEE Communications Letters, 2016.
[24] Q. Yan, X. Tang, and Q. Chen, On the gap between decentralized and centralized coded caching schemes, arXiv: 1605.04626 [cs.IT], May 2016.
[25] Q. Yan, X. Tang, Q. Chen, and M. Cheng, Placement delivery array design through strong edge coloring of bipartite graphs, arXiv: 1609.02985 [cs.IT],
Sep. 2016.
[26] L. Zhang, Z. Wang, M. Xiao, G. Wu, and S. Li, Decentralized caching in two-layer networks: Algorithms and limits, IEEE 12th International Conference
on Wireless and Mobile Computing, Networking and Communications, New York, Oct. 2016.

