1

A Novel Recursive Construction for Coded Caching
Schemes
Minquan Cheng, Jing Jiang, Youzhi Yao

arXiv:1712.09090v1 [] 25 Dec 2017

Abstract
As a strategy to further reduce the transmission pressure during the peak traffic times in wireless network, coded caching has
been widely studied recently. And several coded caching schemes are constructed focusing on the two core problems in practice,
i.e., the rate transmitted during the peak traffic times and the packet number of each file divided during the off peak traffic times.
It is well known that there exits a tradeoff between the rate and the packet number. In this paper, a novel recursive construction is
proposed. As an application, several new schemes are obtained. Comparing with previously known schemes, new schemes could
further reduce packet number by increasing little rate. And for some parameters in coded caching systems, the packet number
of our new schemes are smaller than that of schemes generated by memory sharing method which is widely used in the field of
caching. By the way our new schemes include all the results constructed by Tang et al., (IEEE ISIT, 2790-2794, 2017) as special
cases.

I. I NTRODUCTION
As an efficient solution to reduce tremendous pressure on the data transmission during the peak traffic times, caching has
been widely studied [2], [5], [6], [10], [13]–[17] in heterogeneous wireless networks. It has also been recognized as a disruptive
technology to overcome the upcoming tremendous growth of wireless traffics for the next 5th generation (5G) cellular networks
[4], [24]. The basic idea is simple. During the off peak traffic times, some contents are proactively placed into the user’s memory.
Clearly if the content is required by user during the peak traffic times, then traffic amount can be reduced. So traditionally,
most studies of caching system focused on exploiting the history or statistics of the user demands for an appropriate caching
strategy, such as [1], [3], [5], [10], [11], [17], [19].
However, content requests are unknown to the server during the off peak traffic times. Furthermore, the authors in [21]
pointed that even for a known, fixed popularity distribution, deciding what to cache is an NP-hard combinatorial optimization
problem. Surprisingly even the contents which are required were not cached, we can also reduce the traffic amount by creating
broadcast coding opportunities where the central server transmits the XOR of two files and each user uses their cache to
cancel the non-desired file. This method is called coded caching first proposed by Maddah-Ali and Niesen in [18]. In [18],
the following caching scenario is 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. An F -division coded caching scheme consists of two separate
phases: placement phase and delivery phase. In the placement phase, each file is divided into F equal packets, and each user
caches some packets of each file elaborately from server. This phase does not depend on the user demands which are assumed
to be arbitrary. In delivery phase, each user requires a file from server firstly. Then according to each user’s cache, server
sends a coded signal (XOR of some required packets) with size at most R files to the users such that various user demands
are satisfied. Here R is always called the rate of the scheme.
The first F -division coded caching scheme was constructed by Maddah-Ali and Niesen in [18]. Such a scheme is called
MN scheme in this paper. In fact the rate of MN scheme is at most four times larger than the information-theoretic lower
bound on rate in [12]. However F in MN scheme increases exponentially with the number of users K. This would become
infeasible when K is large. Then many studies focus on designing caching schemes that decrease the order of F for practical
application. For example, a combinatorial structure, (K, F, Z, S) placement delivery array (PDA) proposed in [25], can be
M. Cheng, J. Jiang and Y. Yao are with Guangxi Key Lab of Multi-source Information Mining & Security, Guangxi Normal University, Guilin 541004,
China (e-mail: {chengqinshi,jjiang2008,yaoyzhi}@hotmail.com).

2

used to realize an F -division (K, M, N ) coded caching scheme where M/N = Z/F and R = S/F . They also proved that
MN scheme is equivalent to a special PDA which is denoted by MN PDA. There are other viewpoints of characterizing coded
caching schemes, such as hypergraphs [20], resolvable designs and cyclic codes [22], bipartite graphs [26], Ruzsa-Szeméredi
graphs [21] and so on. However [20] showed that all the constructions in [20]–[22], [26] can be represented by PDAs. And
the authors in [8] generalized all the constructions in [25] and most main results in [20] by means of PDAs.
In this paper, we will propose an novel recursive construction of PDAs. Consequently several new schemes are obtained. By
performance analyses, our new schemes can further reduce packet number by increase little rate comparing with the previously
known results. And for some fixed K, M/N and R, F in our new schemes is smaller than that of schemes generated by
memory sharing method. In addition, our results include all the results in [22] as a special case.
The rest of this paper is organized as follows. Section II briefly reviews the relationship between PDA and coded caching
scheme. In Section III, a recursive construction is proposed. In Section IV, several classes of PDAs are obtained by using
our recursive construction based on previously known PDAs. And some comparisons are considered. Conclusion is drawn in
Section V.
II. P RELIMINARIES
A. Placement Delivery Array
Definition 1: (Placement Delivery Array, [25]) For positive integers K, F, Z and S, an F × K array P = (pj,k ), 0 ≤ j <
F, 0 ≤ k < K, composed of a specific symbol “ ∗ ” and S integers 0, 1, · · · , S − 1, is called a (K, F, Z, S) placement delivery
array (PDA) if it satisfies the following conditions:
C1. The symbol “ ∗ ” appears Z times in each column;
C2. Each integer occurs at least once in the array;
C3. For any two distinct entries pj1 ,k1 and pj2 ,k2 , pj1 ,k1 = pj2 ,k2 = s is an integer only if
a. j1 6= j2 , k1 6= k2 , i.e., they lie in distinct rows and distinct columns; and
b. pj1 ,k2 = pj2 ,k1 = ∗, i.e., the corresponding 2 × 2 subarray formed by rows j1 , j2 and columns k1 , k2 must be of
the following form
!
!
s ∗
∗ s
or
.
∗ s
s ∗
Yan et al, in [25] showed that a (K, F, Z, S) PDA P can be used to realize an F -division (K, M, N ) caching scheme with
M/N = Z/F and R = S/F .
Theorem 1: ( [25]) An F -division caching scheme for a (K, M, N ) caching system can be realized by a (K, F, Z, S)
PDA with Z/F = M/N . Each user can decode his requested file correctly for any request d at the rate R = S/F .
Example 1: It is easy to verify that the following array

∗

 ∗

 ∗
P6×4 = 
 0


 1
2

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

Then one can obtain a 6-division (4, 3, 6) coded caching scheme in the following way.
•

Placement Phase: First let Wi , 1 ≤ i ≤ 6, be the 6 files, and each file is divided into F = 6 packets with equal size, i.e.,
Wi = {Wi,0 , Wi,1 , Wi,2 , Wi,3 , Wi,4 , Wi,5 },

i ∈ [0, 6).

According to the positions of the stars in each column of P6×4 , the contents cached in each users are defined as follows.
Zk = {Wi,j | pj,k = ∗, j ∈ [0, 6), i ∈ [0, 6)} , k ∈ [0, 4)

3

That is

•

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 the k-th user requires the k-th file. For each integer s ∈ [0, 6), the server transmits the following
coded signal in the s-th time.
⊕pj,k =s,j∈[0,6),k∈[0,4) Wk,j
Table I lists all the coded signals.
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 1
From Theorem 1 and Example 1, we can obtain some coded caching schemes by constructing appropriate PDAs.
B. Known results
Here we list some previously known PDAs which have low R and different level of packet numbers. For the other results
the interested reader could be referred to [7], [20], [21], [26].

 K
Lemma 1: (MN PDA [18]) For any positive integers K and t with t < K, there exists a (K, Kt , K−1
t−1 , t+1 ) PDA
with M/N = t/K and R = K−t
1+t .
q−1
⌋q m ,
Lemma 2: ( [8]) For any positive integers q, z and m with q ≥ 2 and z < q, there exists an ((m + 1)q, ⌊ q−z
q−1
q−1
z⌊ q−z
⌋q m−1 , (q − z)q m ) PDA with M/N = zq and R = (q − z)/⌊ q−z
⌋.
 t q−1 t m
Lemma 3: ( [8]) For any positive integers q, z, m and t with q ≥ 2, z < q and t < m, there exists an ( m
t q , ⌊ q−z ⌋ q ,
q−1 t
t m
m−t
t
t
⌊ q−1
(q − z)t ), (q − z)t q m ) PDA with M/N = 1 − ( q−z
q−z ⌋ (q − q
q ) and R = (q − z) /⌊ q−z ⌋ .

In addition, the following result is very useful.
Lemma 4: ( [9]) Let P be a (K, F, Z, S) PDA for some positive integers K, F , Z and S with Z < F . Then there exists
a (K, S, S − (F − Z), F ) PDA.
III. R ECURSIVE

CONSTRUCTIONS

For ease of introduction, we will use the following notations.
•

•

•

JF ×K denotes a matrix with F rows and K columns where each entry contains 1. A JF ×1 is denoted by JF and JF is
written as J if there is no need to list the parameter F .
S
Given an array P = (pj,k ), 0 ≤ j < F , 0 ≤ k < K with alphabet {0, 1, . . . , S − 1} {∗}, define P + a = (pj,k + a) and
aP = (apj,k ) for any integer a where ∗ + a = ∗ and a∗ = ∗.
haib denotes the least nonnegative residue of a modulo b for any positive integers a and b.

Now let us introduce our recursive construction. First the following constructions are very useful. Given two positive integers
u and v with u > v and gcd(u, v) = 1, define a u × (u + v) array





A=



0
0
0

1
1
1

0

1

...
...
...
...
...

u−1
u−1
u−1

0
v
2v

1
v+1
2v + 1

u−1

(u − 1)v

(u − 1)v + 1

...
...
...
...
...

v−1
2v − 1
3v − 1
uv − 1









(1)

4

where all the operations are performed modulo u. For each j, 0 ≤ j < u, denote
Aj = {hjviu , hjv + 1iu , . . . , h(j + 1)v − 1iu }.
We can define another u × (u + v) array B = (bj,k ), where 0 ≤ j < u, 0 ≤ k < u + v, and each entry
(
j
if k ∈ [0, u + v) \ Aj
bj,k =
jv+hk−jviu
u+⌊
⌋ if k ∈ Aj
u

(2)

Construction 1: For any F × u array P = (p0 , p1 , . . . , pu−1 ) with S distinct integers and any two matrices A = (aj,k ),
B = (bj,k ), 0 ≤ j < u, 0 ≤ k < u + v, we can define a map ψ from (P, A, B) to an (F u) × (u + v) array


pa0,0
pa1,0
..
.
pau−1,0



pa0,0 + b0,0 SJ
pa1,0 + b1,0 SJ
..
.
pau−1,0 + bu−1,0 SJ



ψ(P, A, B) = 





=



pa0,1
pa1,1
..
.
pau−1,1

Example 2: When u = 3 and v = 2,

0

A= 0
0

Let F = 3 and

...
...
..
.
...

pa0,u+v−1
pa1,u+v−1
..
.
pau−1,u+v−1









+S





pa0,1 + b0,1 SJ
pa1,1 + b1,1 SJ
..
.
pau−1,1 + bu−1,1 SJ

...
...
..
.
...

b0,0 J
b1,0 J
..
.
bu−1,0 J

pa0,u+v−1
pa1,u+v−1
pau−1,u+v−1

by (1) and (2) the following arrays


3 3
1 2 0 1


B= 4 1
1 2 2 0 
2 4
1 2 1 2


∗

P = (p0 , p1 , p2 ) =  0
1

b0,1 J
b1,1 J
..
.
bu−1,1 J



...
...
..
.
...

b0,u+v−1 J
b1,u+v−1 J
..
.
bu−1,u+v−1 J

+ b0,u+v−1 SJ

+ b1,u+v−1 SJ

.
..


.
+ bu−1,u+v−1 SJ






(3)

can be obtained.

0 0 0

3 1 1 
4 2 2

(4)


0 1

∗ 2 .
2 ∗

Then using A and B in (4), the following array can be obtained by (3),





p0 + 3SJ

ψ(P, A, B) =  p0 + 4SJ
p0 + 2SJ

p1 + 3SJ
p1 + SJ
p1 + 4SJ

p2
p2 + 3SJ
p2 + 4SJ

p0
p2 + SJ
p1 + 2SJ




 


p1
 
p0 + SJ  = 


p2 + 2SJ






∗
9
10
∗
12
13
∗
6
7

9
∗
11
3
∗
5
12
∗
14

1
2
∗
10
11
∗
13
14
∗

∗
0
1
4
5
∗
6
∗
8

0
∗
2
∗
3
4
7
8
∗










.








It is easy to check that P is a (3, 3, 1, 3) PDA and ψ(P, A, B) is a (5, 9, 3, 15) PDA in Example 2.
Lemma 5: Given a (K1 , F, Z, S) PDA, there exists a (K1 + K2 , K1 F, K1 Z, (K1 + K2 )S) PDA for any positive integer
K2 with gcd(K1 , K2 ) = 1.
Proof. Assume that P is a (K1 , F, Z, S) PDA. Let u = K1 and v = K2 . Then matrices A and B can be obtained by (1) and (2)
respectively. We claim that ψ(P, A, B) defined in (3) is a (u+v, uF, uZ, (u+v)S) PDA, i.e., (K1 +K2 , K1 F, K1 Z, (K1 +K2 )S)
PDA. It is easy to check that C1 and C2 hold by (3). So we only need to consider C3. We consider two distinct sub-columns,
say paj,k + bj,k SJF and paj′ ,k′ + bj ′ ,k′ SJF with j, j ′ ∈ [0, u) and k, k ′ ∈ [0, u + v). Clearly if bj,k 6= bj ′ ,k′ , there is no integer
both in paj,k + bj,k SJF and paj′ ,k′ + bj ′ ,k′ SJF . So we only need to consider the case bj,k = bj ′ ,k′ with (j, k) 6= (j ′ , k ′ ).
•

When bj,k = bj ′ ,k′ ∈ [0, u), we have that bj,k = j and k, k ′ ∈ [0, u + v) \ Aj from (2). By (3) we have
ψ(P, A, B)|bj,k =j = (paj,k )k∈[0,u+v)\Aj + bj,k SJF ×u = (paj,k )k∈[0,u+v)\Aj + jSJF ×u .

5

•

Clearly (paj,k )k∈[0,u+v)\Aj can be obtained by permutating the columns of P. Hence it is also a PDA. So ψ(P, A, B)|bj,k =j
satisfies C3, which implies paj,k + bj,k SJ and paj,k + bj ′ ,k′ SJ satisfy C3 too.
When bj,k = bj ′ ,k′ ∈ [u, u + v), then j, j ′ ∈ [0, u) and k, k ′ ∈ [0, u) from (2).
– If j = j ′ , k 6= k ′ must hold by our hypothesis. Then we have the following sub-array
(paj,k + bj,k SJ, paj,k′ + bj,k′ SJ) = (paj,k , paj,k′ ) + bj,k S(J, J).
Since (paj,k , paj,k′ ) is a sub-array of P, (paj,k , paj,k′ ) satisfies C3. This implies that paj,k +bj,k SJ and paj,k +bj,k′ SJ
satisfy C3 too.
T
– If k = k ′ , j 6= j ′ must hold by our hypothesis. Since bj,k = bj ′ ,k ∈ [u, u + v), we have k ∈ Aj Aj ′ from (2),
which implies 0 ≤ k < u. Without loss of generality, let j ′ > j, xk = hk − jviu and x′k = hk − j ′ viu . Then
T
k + uz = jv + xk and k + uz ′ = j ′ v + x′k for some nonnegative integers z and z ′ . If z ′ = z, we have Aj Aj ′ = ∅,
a contradiction to our hypothesis. So z ′ > z always holds. Then

 

 ′
 

jv + xk
k
k
j v + x′k
bj,k = u +
= z+
= z and bj ′ ,k = u +
= z′ +
= z′.
u
u
u
u
This implies bj,k 6= bj ′ ,k , a contradiction to our assumption bj,k = bj ′ ,k . So this subcase does not happen.
– If j 6= j ′ and k 6= k ′ , the following sub-array can be obtained.
!
paj,k + bj,k SJ
paj,k′ + bj,k′ SJ
paj′ ,k + bj ′ ,k SJ paj′ ,k′ + bj ′ ,k′ SJ

By (1) and (3), we have aj,k = aj ′ ,k and aj,k′ = aj ′ ,k′ since k, k ′ ∈ [0, u). So together with our hypothesis of
bj,k = bj ′ ,k′ , the above sub-array can be written as follows.
!
!
!
paj,k paj′ ,k′
paj,k + bj,k SJ paj′ ,k′ + bj,k′ SJ
bj,k SJ bj,k′ SJ
=
(5)
+
paj,k + bj ′ ,k SJ paj′ ,k′ + bj,k SJ
paj,k paj′ ,k′
bj ′ ,k SJ bj,k SJ
So the sub-array in (5) satisfies C3 if and only if the sub-array (paj,k , paj,k′ ) satisfies C3. Clearly (paj,k , paj,k′ )
satisfies C3 since it is a sub-array of P.

For any two positive integers K1 and K2 , let d = gcd(K1 , K2 ), K1′ = K1 /d and K2′ = K2 /d. Based on the K1′ × (K1′ + K2′ )
matrices, A and B defined in (1) and (2) respectively, we can define another two K1′ × (K1 + K2 ) matrices A′ = (a′j,k ) and
B′ = (b′j,k ) where
a′j,k = (daj,k , daj,k + 1, . . . , daj,k + d − 1)

b′j,k = (bj,k , bj,k , . . . , bj,k )

and

are row vectors with length d, 0 ≤ j < K1′ , 0 ≤ k < K1′ + K2′ .
Example 3: When K1 = 6, K2 = 4, we have d = gcd(K1 , K2 ) = 2, K1′ = 3 and K2′ = 2.
matrices A and B by applying (1) and (2) with u = K1′ = 3 and v = K2′ = 2 respectively, which
on these two matrices, the following two 3 × (6 + 4) matrices can be obtained.



3 3 3 3 0 0 0 0
0 1 2 3 4 5 0 1 2 3



′
′
B = 4 4 1 1 3 3 1 1
A = 0 1 2 3 4 5 4 5 0 1 
2 2 4 4 4 4 2 2
0 1 2 3 4 5 2 3 4 5
Given a (6, 4, 2, 4) PDA




P=


∗
∗
0
1

∗
0
∗
2

∗
1
2
∗

0
∗
∗
3

1
∗
3
∗

2
3
∗
∗





,


Then we can obtain two
were listed in (4). Based
0
1
2


0

1 
2

(6)

6

and A′ , B′ in (6), we have












′
′
ψ(P, A , B ) = 











∗
∗
12
13
∗
∗
16
17
∗
∗
8
9

∗
12
∗
14
∗
16
∗
18
∗
8
∗
10

∗
13
14
∗
∗
5
6
∗
∗
17
18
∗

12
∗
∗
15
4
∗
∗
7
16
∗
∗
19

1
∗
3
∗
13
∗
15
∗
17
∗
19
∗

2
3
∗
∗
14
15
∗
∗
18
19
∗
∗

∗
∗
0
1
5
∗
7
∗
∗
9
10
∗

∗
0
∗
2
6
7
∗
∗
8
∗
∗
11

∗
1
2
∗
∗
∗
4
5
9
∗
11
∗

0
∗
∗
3
∗
4
∗
6
10
11
∗
∗













.











It is easy to check that the above array is a (10, 12, 6, 20) PDA. Similar to the proof of Lemma 5, we can also obtain a new
PDA ψ(P, A′ , B′ ) defined in (3) based on a given PDA P and the above matrices A′ , B′ .
Theorem 2: For any given (K1 , F, Z, S) PDA and any positive integer 0 < K2 ≤ K1 , there exists a (K1 +K2 , h1 F, h1 Z, (h1 +
h2 )S) PDA where h1 = K1 /gcd(K1 , K2 ) and h2 = K2 /gcd(K1 , K2 ).
In fact, Theorem 2 also holds when K1 < K2 if we make small changes to the expression in (2). However here we omit
the similar introduction to save space. In the following section, let us consider the applications of Theorem 2 based on some
previously known results.
IV. A PPLICATIONS
For simplicity, we only consider the case K2 ≤ K1 . Let K1 = dh1 and K2 = dh2 where d = gcd(K1 , K2 ) and h1 > h2
in the following.

A. Application on MN scheme
From Lemma 1, the following results can be obtained by Theorem 2.
Theorem 3: For any positive integers K1 , K2 and t with t, K2 < K1 , there exists a (K1 + K2 , h1

K1
1 −t
.
h2 ) t+1
) PDA with M/N = t/K1 and R = (1 + hh21 ) K1+t

K1
t

From Theorem 3, we have a PDA with user number K1 + K2 , M/N = t/K1 and


 
h2 K 1 − t
K1
.
,
R= 1+
F = h1
h1
1+t
t


, h1

K1 −1
t−1


, (h1 +

(7)

We claim that this PDA has smaller packet number but little larger rate than that of MN PDA. For simplicity we assume
that t|K2 . From Lemma 1, we have an MN PDA with


(K1 + K2 ) K1 −t
(K1 + K2 )(K1 − t)
K1 + K2
,
RMN = t(K +K ) K1 =
FMN =
.
(8)
1
2
(K1 + K2 )t/K1
t(K1 + K2 ) + K1
+1
K1

So we have
F
FMN
R
RMN

=

K1
t

K1 +K2
(K1 +K2 )t/K1

h1



t

≈ h1 2−K2 H( K1 ) ,






h2
h2 K1 − t t(K1 + K2 ) + K1
h2
.
1−
= 1+
= 1+
h1
1 + t (K1 + K2 )(K1 − t)
h1
(1 + t)(h1 + h2 )

(9)

By the way the last approximate equality of the first formula holds for large enough K1 where H(λ) is the entropy function
defined as follows.
H(λ) = −λ log2 (λ) − (1 − λ) log2 (1 − λ) 0 < λ < 1

7

t

K2 H( K )
1
For fixed K1 and M/N , we have that F is about h−1
times smaller than that of MN scheme, but R just increases
1 2



h2
h2
h2
1+
<2
<1+
1−
h1
(1 + t)(h1 + h2 )
h1
K H(

t

2
K1
times. Clearly h−1
1 2
approach infinite very fast.

)

is increases exponentially with K2 , i.e., when K1 and K2 approach infinite, h−1
1 2

K2 H( Kt )
1

Example 4: When M/N = 0.5 and K1 /K2 = 2, the corresponding rates and packets numbers in the following table can
be obtained by (7) and (8).
K K1
6
4
12 8
18 12
24 16
30 20
36 24
42 28
48 32

K2
2
4
6
8
10
12
14
16

R
1.0000
1.2000
1.2857
1.3333
1.3636
1.3846
1.4000
1.4118

RMN
F
FMN
0.7500
12
20
0.8571
140
924
0.9000
1848
48620
0.9231
25740
2704156
0.9375
369512
155117520
0.9474
5408312
9075135300
0.9545 80233200
538257874440
0.9600 1202160780 32247603683100

It is interesting that for the same K, M/N and R, packet number of a PDA obtained by Theorem 3 is sometimes smaller
than that of the scheme generated by memory sharing method based on MN PDAs. Let us introduce memory sharing method
first. Given the parameters K and N , assume that there exist r schemes with (M1 , R1 , F1 ), . . ., (Mr , Rr , Fr ) where M1 <
M2 < . . . < Mr . [18] showed that a scheme with
M1
M2
Mr
M
= λ1
+ λ2
+ . . . + λr
N
N
N
N
RM−MN = λ1 R1 + λ2 R2 + . . . + λr Rr

(10)

FM−MN = F1 + F2 + . . . + Fr
P
can be obtained where M1 ≤ M ≤ Mr , 0 < λi ≤ 1 and ri=1 λi = 1.

Unfortunately it may be hard to theoretically compare with the advantages of them since the parameters are confusable.
Instead we illustrate the reduction in packet number by numerical comparisons. Given a positive integer K, there exist K + 1
MN PDAs with M = 0, N/K, . . . , N (K − 1)/K, N respectively from Lemma 1. Based on these MN PDAs, we have many
pairs (RM−MN , FM−MN ) obtained by (10) for a fixed M/N . Denote the set of all these pairs by H. For the fixed M/N , we
can choose appropriate positive integers K1 and K2 such that K = K1 + K2 and obtain a PDA with F and R from Theorem
(1)
(1)
(2)
(2)
3. With the aid of a computer we can find out all the pairs from H, say (RM−MN , FM−MN ), (RM−MN , FM−MN ), . . .,
(s)
(s)
(RM−MN , , FM−MN ), such that
(1)

(s)

|RM−MN − R| = . . . = |RM−MN − R| = min{|RM−MN − R| | (RM−MN , FM−MN ) ∈ H}
(1)

(i)

With out loss of generality we assume that FM−MN = min{FM−MN | 1 ≤ i ≤ s}. From Table II, the packet number obtained
(1)
by Theorem 3 is smaller even though R ≤ RM−MN for the same K and M/N .

8

TABLE II: Schemes generated by Theorem 3 and memory sharing method based on MN PDAs
K
18
20
25
28
30
34
36
40
44
48
50

K1
12
11
14
15
18
18
19
21
24
25
26

K2
6
9
11
13
12
16
17
19
20
23
24

h1
2
11
14
15
3
9
19
21
6
25
13

h2
1
9
11
13
2
8
17
19
5
23
12

t
9
7
11
11
11
10
13
14
13
16
18

M/N
3/4
7/11
11/14
11/15
11/18
5/9
13/19
2/3
13/24
16/25
9/13

R
0.450
0.909
0.446
0.622
0.972
1.373
0.812
0.889
1.440
1.016
0.810

(1)

RM−MN
0.484
0.928
0.454
0.655
0.993
1.402
0.851
0.922
1.460
1.032
0.815

F
440
3630
5096
20475
95472
393822
515508
2441880
14976864
51074375
20309575

(1)

FM−MN
816
5035
12675
101556
593776
5657872
8724672
80743065
710016516
6918064890
10809156820

Finally let us consider the performance comparing with the PDAs in Lemma 2. The authors in [8] showed that PDAs in
Lemma 2 have lower packet number level than that of MN PDAs. By the way when M/N = 1/q and 1 − 1/q, this fact had
also been shown in [22], [25] respectively. Given a positive integer K, we have many types of PDAs by choosing different q
and z for a fixed M/N . Based on these PDAs, we have many pairs (RM−le2 , FM−le2 ) obtained by (10) for a fixed M/N .
(1)
Similarly we can also obtain a PDA with R and F from Theorem 3. And we also assume that RM−le2 is nearest R and
(1)
FM−le2 is the related minimum packet number. For some fixed K, M/N , three types of schemes are listed in Table III. From
(1)
(1)
(1)
(1)
Table III, we have R < RM−le2 , R < RM−MN and FM−le2 < F < FM−MN . This implies that comparing with memory
sharing method based on MN PDAs and PDAs in Lemma 2 respectively, Theorem 3 has smaller packet number but larger
rate, and Theorem 3 has larger packet number but smaller rate.
TABLE III: PDAs in Theorem 3 and generated by memory sharing based on MN PDAs and PDAs in Lemma 2
K
18
20
28
35
38
44

K1
12
11
15
20
20
24

K2
6
9
13
15
18
20

t
9
6
8
11
11
13

q
6
5
4
5
19
4

m
2
3
6
6
1
10

M/N
3/4
6/11
8/15
11/20
11/20
13/24

(1)

RM−le2
0.600
1.401
1.489
1.375
4.125
1.444

R
0.450
1.299
1.452
1.313
1.425
1.440

(1)

RM−MN
0.466
1.351
1.461
1.327
1.441
1.455

(1)

FM−le2
252
375
16384
46875
95
4194304

F
440
5082
96525
671840
1679600
14976864

(1)

FM−MN
43776
16644
1560780
183631756
472807571
686354883984

Similarly we can also discuss the performance of Theorem 3 comparing with other PDAs in Lemmas 3.

B. Applications on other known PDAs
Based on the PDAs in Lemmas 2 and 3, we can obtain the following results by Theorem 2.
q−1
Theorem 4: Given positive integers q, z, m with q ≥ 2 and z < q, there exists an ((m + 1)q + K2 , h1 ⌊ q−z
⌋q m ,
q−z
q−1
h1 z⌊ q−z ⌋q m−1 , (h1 + h2 )(q − z)q m ) PDA with M/N = z/q and R = (1 + hh12 ) ⌊ q−1 ⌋ .
q−z
 t
q−1 t m
Theorem 5: For any positive integers q, z, m and t with q ≥ 2, z < q and t < m, there exists an ( m
t q +K2 , h1 ⌊ q−z ⌋ q ,
q−1 t
h2
t m
m−t
t
t
h1 ⌊ q−1
(q − z)t ), (h1 + h2 )(q − z)t q m ) PDA with M/N = 1 − ( q−z
q−z ⌋ (q − q
q ) and R = (1 + h1 )(q − z) /⌊ q−z ⌋ .

Similarly let us conder PDAs in Theorem 4 and in Lemma 2 for some parameters K. Given any positive integers q, m, let
K1 = (m + 1)q and K2 = qm′ < K1 for simplicity, where m′ is a positive integer. When M/N = z/q, from Theorem 4, we
have a PDA with user number K1 + K2 and
q−1 m
h2 q − z
F = h1 ⌊
⌋q
R = (1 + ) q−1
(11)
q−z
h1 ⌊ q−z ⌋

9

where
h1 =

m+1
K1
=
,
gcd(K1 , K2 )
gcd(m + 1, m′ )

h2 =

K2
m′
=
.
gcd(K1 , K2 )
gcd(m + 1, m′ )

(12)

Now let us consider the decrement of packet number. When K = K1 + K2 = q(m + m′ + 1) and M/N = z/q, from Lemma
2, we have a PDA with
q − 1 m+m′
q−z
Fle2 = ⌊
⌋q
Rle2 = q−1
q−z
⌊ q−z ⌋
So we have
R
h2
m′
m + 1 + m′
=1+
=1+
=
< 2.
Rle2
h1
m+1
m+1

′
F
= h1 q −m
Fle2

(13)

m
For fixed K and M/N , we have that F is exactly h−1
times smaller than that of a PDA in Lemma 2, but R just increases
1 q
h2
1 + h1 < 2 times.
′

In addition, the results in Claims 3, 4 of [22], which have been summarized in Theorem 1 of [23], are just our special cases.
First let us introduce the results in Theorem 1 of [23]. For any positive integers n, let K = nq and x be the least positive
integer such that (m + 1)|nx. References [22], [23] proposed the following coded caching schemes with K = nq when q is a
prime power and satisfies some conditions related the [n, m] cyclic code (The interested readers could be referred to [23] for
more details).
•

•

When M/N = 1/q, there exists a coded caching scheme with
n
(q − 1) and
R1 =
m+1
When M/N = 1 −

m+1
nq ,

F1 = q m x;

(14)

there exists a coded caching scheme with
R2 =

m+1
and
(q − 1)n

F2 = (q − 1)q m

xn
.
m+1

(15)

Let us consider the case M/N = 1/q first. From Theorem 4 we have an ((m + 1)q + K2, h1 q m , h1 q m−1 , (h1 + h2 )(q − 1)q m )
PDA with M/N = 1/q and R = (1 + hh21 )(q − 1). Let K1 = (m + 1)q and K = K1 + K2 . Clearly q|K2 . Then we have
(h1 + h2 )gcd(K1 , K2 )
K1 + K2
=
.
q
q
By (12), h1 = x holds and the following equations can be easily verified.
n=

R = (1 +

(h1 + h2 ) · gcd(K1 , K2 )
n
h2
nq
)(q − 1) =
=
(q − 1) =
(q − 1) = R1
h1
h1 · gcd(K1 , K2 )
K1
m+1

F = h1 q m = xq m = F1
Now let us consider the case M/N = 1 − k+1
nq . With the same parameter K1 and K2 in the case M/N = 1/q, from Theorem
4 and Lemma 4, we have an ((m + 1)q + K2 , (h1 + h2 )(q − 1)q m , (h1 + h2 )(q − 1)q m − (h1 q m − h1 q m−1 ), h1 q m ) PDA with
M
h1
(h1 + h2 )(q − 1)q m − (h1 q m − h1 q m−1 )
m+1
=1−
=
=1−
,
N
(h1 + h2 )(q − 1)q m
(h1 + h2 )q
nq
R=

h1
h1 q m
m+1
=
=
= R2
(h1 + h2 )(q − 1)q m
(h1 + h2 )(q − 1)
(q − 1)n

(16)

(17)

and
F = (h1 + h2 )(q − 1)q m =

nx
(q − 1)q m = F2
m+1

(18)

where the second item in (18) can be derived by the fact
(h1 + h2 ) = (h1 + h2 ) ·

nqh1
nx
gcd(K1 , K2 ) h1
=
·
=
.
gcd(K1 , K2 ) h1
(m + 1)q
m+1

It is worth to note that with the same parameters K, M/N , R and F in [22], our result holds for any positive integer q ≥ 2.
We can discuss the PDAs in Theorem 5 similarly.

10

V. C ONCLUSION
In this paper, a novel recursive construction was proposed. As an application, several new schemes were obtained. Comparing
with previously known schemes, our new schemes could further reduce packet number by increasing little rate. And the packet
number of our new schemes are smaller than that of schemes generated by memory sharing method for some fixed K, M/N
and R. In addition, our new schemes include all the results in [22] as special cases.
R EFERENCES
[1] 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.
[2] Z. H. Awan, A. Sezgin, Fundamental limits of caching in D2D networks with secure delivery, 2015 IEEE International Conference on Communication
Workshop, pp. 464-469, June 2015.
[3] I. Baev, R. Rajaraman, and C. Swamy, Approximation algorithms for data placement problems, SIAM Journal on Computing, vol. 38, no. 4, pp. 1411-1429,
2008.
[4] F. Boccardi, R. W. Heath, A. Lozano, T. L. Marzetta, and P. Popovski. Five disruptive technology directions for 5g. IEEE Communications Magazine,
vol. 52, no. 2, pp.74-80, 2014.
[5] S. Borst, V. Gupta, and A. Walid, Distributed caching algorithms for content distribution networks, in Proc. IEEE International Conference on Computer
Communications, San Diego, CA, Mar. 2010, pp. 1-9.
[6] P. Blasco and D. Gunduz, Multi-armed bandit optimization of cache content in wireless infostation networks, in Proc. IEEE International Symposium on
Information Theory, Honolulu, HI, Jun. 2014, pp. 51-55.
[7] M. Cheng, J. Jiang, Q. Yan, X. Tang, and H. Cao, Optimal placement delivery arrays, arXiv:1611.04213 [], Nov. 2016.
[8] M. Cheng, J. Jiang, Q. Yan and X. Tang, Coded caching schemes generated by partitions for flexible memory sizes, Aug. 2017. arXiv:1708.06650 [cs,IT]
[9] M. Cheng, Q. Yan, X. Tang, and J. Jiang ,Coded caching schemes with low rate and subpacketizations, arXiv:1703.01548v2 [], Apr 2017.
[10] A. Dan, D. Sitaram, and P. Shahabuddin, Dynamic batching policies for an on-demand video server, Multimedia Syst., vol. 4, pp. 112-121, June 1996.
[11] L. W. Dowdy and D. V. Foster, Comparative models of the file assignment problem, ACM Comput. Surv., vol. 14, pp. 287-313, June 1982.
[12] H. Ghasemi and A. Ramamoorthy, Further results on lower bounds for coded caching, in Proc. IEEE International Symposium on Information Theory,
Barcelona, Spai, July, 2016, pp. 2319-2323.
[13] 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.
[14] 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.
[15] 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.
[16] 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.
[17] M. R. Korupolu, C. G. Plaxton, and R. Rajaraman, Placement algorithms for hierarchical cooperative caching, in Proc. ACM-SIAM SODA, pp. 586-595,
Jan. 1999.
[18] M. A. Maddah-Ali and U. Niesen, Fundamental limits of caching, IEEE Transactions on Information Theory, vol. 60, no. 5, pp. 2856-2867, 2014.
[19] A. Meyerson, K. Munagala, and S. Plotkin, Web caching using access statistics, in Proc. ACM-SIAM SODA, pp. 354-363, 2001.
[20] C. Shangguan, Y. Zhang, G. Ge, Centralized coded caching schemes: A hypergraph theoretical approach, arXiv:arXiv:1608.03989 [], Aug. 2016.
[21] 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, Germany, Jun. 2017, pp. 1237-1241.
[22] L. Tang and A. Ramamoorthy, Coded caching with low subpacketization levels, in Proc. IEEE International Symposium on Information Theory, Aachen,
Germany, Jun. 2017, pp. 2790-2794.
[23] L. Tang, A. Ramamoorthy, Low subpacketization schemes for coded caching, arXiv:1706.00101v1 [] 31 May 2017.
[24] X. Wang, M. Chen, T. Taleb, A. Ksentini, and V. Leung, Cache in the air: exploiting content caching and delivery techniques for 5g systems, IEEE
Communications Magazine, vol. 52, no. 2, pp.131C139, 2014.
[25] 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.
[26] Q. Yan, X. Tang, Q. Chen, and M. Cheng, Placement delivery array design through strong edge coloring of bipartite graphs, IEEE Communications
Letters, to appear.

