# Coded Caching Schemes for Multiaccess Topologies via Combinatorial Design

Minquan Cheng, Kai Wan, Petros Elia, and Giuseppe Caire  A short version of
this paper was presented at the 2023 IEEE International Symposium on
Information Theory (ISIT). M. Cheng is with Guangxi Key Lab of Multi-source
Information Mining $\&$ Security, Guangxi Normal University, Guilin 541004,
China (e-mail: chengqinshi@hotmail.com). The work of M. Cheng was in part
supported by 2022GXNSFDA035087, NSFC (No.62061004, U21A20474), Guangxi
Collaborative Innovation Center of Multi-source Information Integration and
Intelligent Processing, the Guangxi Bagui Scholar Teams for Innovation and
Research Project, and the Guangxi Talent Highland Project of Big Data
Intelligence and Application.K. Wan is with the School of Electronic
Information and Communications, Huazhong University of Science and Technology,
430074 Wuhan, China, (e-mail: kai_wan@hust.edu.cn). The work of K. Wan was
partially funded by the National Natural Science Foundation of China
(NSFC-12141107).Petros Elia is with the Communication Systems Department,
EURECOM, 06410 Sophia Antipolis, France (e-mail: elia@eurecom.fr). The work of
P. Elia was supported in part by the ERC Project DUALITY under Grant 725929,
as well as by a Huawei France-funded Chair towards Future Wireless Networks.G.
Caire is with the Electrical Engineering and Computer Science Department,
Technische Universität Berlin, 10587 Berlin, Germany (e-mail: caire@tu-
berlin.de). The work of G. Caire was partially funded by the European Research
Council under the ERC Advanced Grant N. 789190, CARENET.

###### Abstract

This paper studies a multiaccess coded caching (MACC) where the connectivity
topology between the users and the caches can be described by a class of
combinatorial designs. Our model includes as special cases several MACC
topologies considered in previous works. The considered MACC network includes
a server containing $N$ files, $\Gamma$ cache nodes and $K$ cacheless users,
where each user can access $L$ cache nodes. The server is connected to the
users via an error-free shared link, while the users can retrieve the cache
content of the connected cache-nodes while the users can directly access the
content in their connected cache-nodes. Our goal is to minimise the worst-case
transmission load on the shared link in the delivery phase. The main
limitation of the existing MACC works is that only some specific access
topologies are considered, and thus the number of users $K$ should be either
linear or exponential to $\Gamma$. We overcome this limitation by formulating
a new access topology derived from two classical combinatorial structures,
referred to as the $t$-design and the $t$-group divisible design. In these
topologies, $K$ scales linearly, polynomially, or even exponentially with
$\Gamma$. By leveraging the properties of the considered combinatorial
structures, we propose two classes of coded caching schemes for a flexible
number of users, where the number of users can scale linearly, polynomially or
exponentially with the number of cache nodes. In addition, our schemes can
unify most schemes for the shared link network and unify many schemes for the
multi-access network except for the cyclic wrap-around topology.

###### Index Terms:

Coded caching, multiaccess networks, combinatorial design, placement delivery
array.

##  I Introduction

Caching can effectively shift traffic from peak to off-peak times [1] by
storing fractions of popular content in users’ local caches during peak
traffic times, so that users can be partially served from their local caches,
thereby reducing network traffic. In the setting of the shared-link caching
model, a single server has access to a library of $N$ files of equal length
and serves $K$ users through an error-free shared link, where each user has a
cache of $M$ files. A coded caching scheme contains two phases: the placement
phase and the delivery phase. During the placement phase, each cache is filled
with content from the library without any knowledge of future users’ requests.
During the delivery phase, each user requests a single file from the library.
In terms of the users’ requests and caches, the server then broadcasts a
sequence of messages such that each user’s request can be satisfied. The
objective is to minimize the worst-case number of transmissions during the
delivery phase (normalized by the file size) among all possible requests,
referred to as worst-case load $R$. Compared to the conventional uncoded
caching scheme, the seminal coded caching technique was originally proposed by
Maddah-Ali and Niesen (MN) in [2] to further reduce the number of
transmissions during peak traffic times by introducing an additional coded
caching gain. The coded caching scheme proposed by MN (referred to as MN
scheme) uses a combinatorial cache placement and transmits coded multicast
messages during the delivery where each multicast message is simultaneously
useful to a set of users. The MN scheme in [2] is generally order optimal
within a factor of $4$ [3], and is optimal under the constraint of $N\geq K$
and uncoded cache placement (i.e., each user directly stores some bits of
files in the library) [4, 5]. For the case $N<K$, the MN scheme was further
improved by removing redundant multicast messages [5]; the resulting scheme is
generally order optimal within a factor of $2$ [6] and is optimal under the
constraint of uncoded cache placement[5]. Combinatorial design was introduced
into coded caching to construct coded caching schemes in [7], where a
combinatorial structure, referred to as _Placement Delivery Array (PDA)_ , was
introduced into coded caching to construct coded caching schemes with the
uncoded placement and one-shot delivery. It was shown in [8, 9] that the coded
caching schemes in [2, 7, 8, 10, 9, 11, 12, 13] can be represented by
appropriate PDAs. Under the PDA structure, various coded caching schemes were
then designed; just list a few, [7, 14, 15, 16, 17, 18, 12, 9, 19, 20, 21,
22].

Following the seminal results in [2], numerous works have addressed a variety
of extended models beyond the original shared-link setting. While the mature
literature on coded caching has explored a rich variety of settings, some
recent results - which we discuss later - have brought to the fore a powerful
new way of exploiting a modest number of edge caches, with the motivation of
edge caching which was widely used in the communication systems. In this paper
we consider this multiaccess coded caching (MACC) model, where cache content
is stored at edge cache-nodes in the network and users do not have their own
caches, as shown in Fig. 1. The original MACC model was proposed in [23],
containing a server with $N$ files, $\Gamma$ cache-nodes and $K$ _cache-less_
users. Each user could access a subset of cache-nodes with negligible cost in
a cyclic wrap-around way; i.e, each user can access $L$ neighbouring cache-
nodes in a cyclic wrap-around fashion. An MACC scheme also contains two
phases. During the placement phase, each cache-node places $M$ files in its
memory, with full knowledge of the network topology but without knowledge of
subsequent users’ requests. During the delivery phase, each user requests a
single file; the server then broadcasts messages to the users such that each
user can recover its requested file from the broadcasted messages and the
cache content in the cache-nodes which it can access. As in the shared-link
model, the objective is to reduce the worst-case delivery load $R$ for any
given memory size $M$.

Figure 1: Multiaccess coded caching system.

The authors in [23] proposed a coloring-based scheme that allows for the
maximum local caching gain (i.e., the cache content stored by the cache-nodes
connected to one user are totally different and thus each user can totally
retrieve $LM$ files from the connected cache), but the coded caching gain is
even worse than the MN scheme for the shared-link model where each user caches
$M$ files. Recent works [19, 20, 24, 25, 26, 27, 28, 29, 30, 31, 32] proposed
improved MACC schemes and converse bounds for this cyclic topology. However,
the general order optimality (with or without the constraint of uncoded cache
placement) for this model still remains open.

Recently, the MACC problem with combinatorial access topology was considered
in [33]. This topology, involves $\Gamma$ cache-nodes and $\binom{\Gamma}{L}$
users, where each subset of $L$ cache-nodes is connected to a distinct user. A
coded caching scheme for this MACC model was proposed in [33], which was shown
to be optimal under the constraint of uncoded cache placement [34]. Another
access topology was considered based on a combinatorial structure known as
cross-resolvable design [29] where this topology contains $\Gamma=mq$ cache-
nodes serving exactly $\binom{m}{L}q^{L}$ users, and each cache has size
$M=N/q$ for any positive integer $q$ and $m\geq L$.111One can check that
$\binom{m}{L}q^{L}=\binom{\Gamma/q}{L}q^{L}=\mathcal{O}((\Gamma/q)^{L}q^{L})=\mathcal{O}(\Gamma^{L}).$

##### Main contributions

Although numerous works have been proposed in the literature for the MACC
model, given the number of cache-nodes $\Gamma$ and the user access degree
$L$, the number of users in the system is either linear with $\Gamma$, or of
order $\Gamma^{L}$. When these schemes are applied in practical systems, a
large number of virtual users may be required. The main contribution of this
paper is to consider the access topology with a more flexible number of users.
By formulating the access topology in terms of two classical combinatorial
structures, $t$-design and $t$-group divisible design (also known as $t$-GDD),
we propose two classes of coded caching schemes for a flexible number of
users, where the number of users can be scaled linearly, polynomially, or
exponentially with the number of cache-nodes. Note that the access topologies
in [33, 29] can be considered as special cases of ours.

Since the combinatorial structures considered in [23, 19, 28, 33, 29], i.e.
the cyclic wrap-around access, the combinatorial access and the cross-
resolvable design access, are different, the authors proposed topology-
dependent cache placement and delivery strategies. In this paper, we aim to
propose unified coded caching strategies for arbitrary parameters of
$t$-designs and $t$-GDDs access topology by exploiting the structure of the
$t$-design and $t$-GDD, respectively. Our main contributions are as follows.

  * •

According to the property of $t$-design, we apply the placement strategy of
the MN scheme into the $t$-design access topology and delivery strategy
generated via the property of $t$-design (Definition 4) to obtain our first
scheme. Interestingly, our scheme covers the schemes in [33] as special cases.

  * •

According to the property of $t$-GDD, by applying an Orthogonal Array (OA)
placement strategy into the $t$-GDD access topology and the delivery strategy
generated by the property of $t$-GDD (Definition 5), we obtain the second
scheme proposed in this paper. Furthermore, we show that the access topology,
i.e. the cross-resolvable design, in [29] can be considered as a special case
of ours. Compared with the schemes in [35, 36, 29], our scheme has smaller
transmission load and subpacketization.

As a by-product, the proposed schemes can also work and unify some existing
schemes for the original MN shared-link coded caching model, where each user
has its own cache. In particular, our $t$-design scheme covers the schemes in
[2, 12], and our $t$-GDD scheme covers the PDA schemes in [9, 11, 7, 37], as
special cases.

##### Notations

In this paper, the following notations will be used unless otherwise stated.

  * •

$|\cdot|$ denotes the cardinality of a set.

  * •

For a set $\mathcal{V}$, we sort it in the lexicographic order; let
$\mathcal{V}(j)$ represent the $j$-th smallest element in $\mathcal{V}$ and
let $\mathcal{V}(\mathcal{J})=\\{\mathcal{V}(j)\ |\ j\in\mathcal{J}\\}$.

  * •

For any positive integers $a$, $b$, $t$ with $a<b$ and $t\leq b$, let
$[a:b]=\\{a,a+1,\ldots,b\\}$, $[1:b]=[b]$, and ${[b]\choose
t}=\\{\mathcal{V}\subseteq[b]\ |\ |\mathcal{V}|=t\\}$, i.e., ${[b]\choose t}$
is the collection of all $t$-subsets of $[b]$.

  * •

Let ${\bf a}$ be a vector with length $n$. For any $i\in[n]$, ${\bf a}(i)$
denotes the $i^{\text{th}}$ coordinate of ${\bf a}$. For any subset
$\mathcal{T}\subseteq[n]$, ${\bf a}(\mathcal{T})$ denotes a vector with length
$|\mathcal{T}|$ obtained by taking only the coordinates with indices in
$\mathcal{T}$.

  * •

For any $F\times m$ array $\mathbf{P}$, for any integers $i\in[F]$ and
$j\in[m]$, $\mathbf{P}(i,j)$ represents the element located in the
$i^{\text{th}}$ row and the $j^{\text{th}}$ column of $\mathbf{P}$;
$\mathbf{P}(\mathcal{V},\mathcal{T})$ represents the subarray generated by the
row indices in $\mathcal{V}\subseteq[F]$ and the columns indices in
$\mathcal{T}\subseteq[m]$. In particular let $\mathbf{P}([F],\mathcal{T})$ be
shortened by $\mathbf{P}(\cdot,\mathcal{T})$ and $\mathbf{P}(\mathcal{V},[m])$
be shortened by $\mathbf{P}(\mathcal{V},\cdot)$.

  * •

If $a$ is not divisible by $q$, $\langle a\rangle_{q}$ denotes the least non-
negative residue of $a$ modulo $q$; otherwise, $\langle a\rangle_{q}:=q$.

  * •

For any two vectors ${\bf x}$ and ${\bf y}$ with the same length, $d({\bf
x},{\bf y})$, which is called the hamming distance of ${\bf x}$ and ${\bf y}$,
i.e., the number of coordinates in which ${\bf x}$ and ${\bf y}$ differ.

##  II System Model of MACC

In this section, we first introduce the original shared-link MN coded caching
model in [2], where each user has its own cache (i.e. the number of cache-
nodes and the number of users are equal, while each user accesses a different
cache-node). We then present the MACC model considered in this paper, where
each user can access an arbitrary subset of cache-nodes.

###  II-A Shared-link coded caching model

In the shared-link coded caching system [2], a server containing $N$ files of
equal length in the library $\mathcal{W}=\\{W_{1},W_{2},\ldots,$ $W_{N}\\}$ is
connected by an error-free shared link to $K$ users in
$\\{U_{1},U_{2},\ldots,U_{K}\\}$ with $K\leq N$, and each user has a cache of
size $M$ files where $0\leq M\leq N$. The memory ratio is defined as
$\mu=M/N$. An $F$-division $(K,M,N)$ coded caching scheme contains two phases:

  * •

Placement phase. Each file is divided into $F$ packets of equal size.222In
this paper, we only consider uncoded cache placement. Each user $U_{k}$, where
$k\in[K]$, caches a total of up to $MF$ packets of files. Let
$\mathcal{Z}_{U_{k}}$ denote the cache content at user $U_{k}$. Note that the
placement phase is done without knowledge of later requests.

  * •

Delivery phase. Each user requests a file from the server. The file requested
by user $U_{k}$ is denoted by $W_{d_{U_{k}}}$, and the request vector of all
users is denoted by $\mathbf{d}=(d_{U_{1}},d_{U_{2}},\ldots,d_{U_{K}})$.
According to the users’ cache content and requests, the server broadcasts
$S_{{\bf d}}$ packets to all users so that each user’s request can be
satisfied.

In such system, the worst-case number of transmitted files (a.k.a. worst-case
load, or simply load) among all possible requests is expected to be as small
as possible, which is defined as

$\displaystyle R=\max\left\\{S_{\mathbf{d}}/F\ |\
\mathbf{d}\in[N]^{K}\right\\}.$ (1)

For the shared-link coded caching problem, the authors in [7] proposed a
combinatorial structure to construct coded caching schemes with uncoded cache
placement (symmetric cross files) and clique-covering delivery,333Clique-
covering delivery means that each multicast message sent is the XOR of some
subfiles and is useful to a subset of users, where each user requests one
subfile and caches all the other subfiles.  referred to as a Placement
Delivery Array (PDA), with the following definition.

######  Definition 1.

([7]) For positive integers $K,F,Z$ and $S$, an $F\times K$ array
$\mathbf{P}=(\mathbf{P}(j,k))_{j\in[F],k\in[K]}$, composed of a specific
symbol $``*"$ and $S$ positive integers from $[S]$, is called a $(K,F,Z,S)$
PDA if it satisfies the following conditions:

  1. C$1$.

the symbol $``*"$ appears $Z$ times in each column;

  2. C$2$.

each integer occurs at least once in the array;

  3. C$3$.

for any two distinct entries $\mathbf{P}(j_{1},k_{1})$ and
$\mathbf{P}(j_{2},k_{2})$, $\mathbf{P}(j_{1},k_{1})=\mathbf{P}(j_{2},k_{2})=s$
is an integer only if

    1. a.

$j_{1}\neq j_{2}$, $k_{1}\neq k_{2}$, i.e., they lie in distinct rows and
distinct columns; and

    2. b.

$\mathbf{P}(j_{1},k_{2})=\mathbf{P}(j_{2},k_{1})=*$, i.e., the corresponding
$2\times 2$ subarray formed by rows $j_{1},j_{2}$ and columns $k_{1},k_{2}$
must be of the following form

$\displaystyle\left(\begin{array}[]{cc}s&*\\\
&s\end{array}\right)~{}\textrm{or}~{}\left(\begin{array}[]{cc}*&s\\\
s&*\end{array}\right).$

$\square$

In a $(K,F,Z,S)$ PDA $\mathbf{P}$, for each $k\in[K]$, column $k$ represents
user $U_{k}$; for each $j\in[F]$, row $j$ represents the $j^{th}$ packet of
each file. If $\mathbf{P}(j,k)=*$, then user $U_{k}$ caches the $j^{th}$
packet of all files. If $\mathbf{P}(j,k)=s$ is an integer, then the $j^{th}$
packet of each file is not cached by user $U_{k}$. In addition, a multicast
message, which is the XOR of the requested packets indicated by $s$, is sent
by the server at time slot $s$. Condition C$2$ of the definition 1 implies
that the number of multicast messages sent by the server is exactly $S$. So
the total transmission load is $R=S/F$. Finally, Condition C$3$ of Definition
1 guarantees that each user can get the packet it requests, since it has
cached all the other packets in the multicast message useful to it except the
packet it requests. Thus, the following lemma was proved by Yan et al. in [7].

######  Lemma 1.

([7]) Using Algorithm 1, an $F$-division caching scheme for the $(K,M,N)$
shared-link coded caching model can be realized by a $(K,F,Z,S)$ PDA with
$\frac{M}{N}=\frac{Z}{F}$. Each user can decode its requested file correctly
for any request ${\bf d}$ with the load $R=\frac{S}{F}$. $\square$

Algorithm 1 Coded caching scheme for Shared-link caching model based on PDA in
[7]

1:procedure Placement($\mathbf{P}$, $\mathcal{W}$)

2: Divide each file $W_{n}\in\mathcal{W}$ into $F$ packets, i.e.,
$W_{n}=(W_{n,j}\ |\ j\in[F])$.

3: for $k\in[K]$ do

4: $\mathcal{Z}_{U_{k}}\leftarrow\\{W_{n,j}\ |\
\mathbf{P}(j,k)=*,\forall~{}n\in[N]\\}$

5: end for

6:end procedure

7:procedure Delivery($\mathbf{P},\mathcal{W},{\bf d}$)

8: for $s=1,2,\cdots,S$ do

9: Server sends
$\bigoplus_{\mathbf{P}(j,k)=s,j\in[F],k\in[K]}W_{d_{U_{k}},j}$.

10: end for

11:end procedure

Let us briefly introduce the MN coded caching scheme in [2] from the viewpoint
of PDA, where the resulting PDA is called an MN PDA. For any
$\mu\in\\{\frac{1}{K},\frac{2}{K},\ldots,\frac{K-1}{K},1\\}$ we let
$F={K\choose\mu K}$. We sort all $(\mu K+1)$-subsets of $[K]$ in lexicographic
order and define $\phi(\mathcal{S})$ as its order for each $(\mu K+1)$-subset
$\mathcal{S}$. Clearly, $\phi$ is a bijection from ${[K]\choose\mu K+1}$ to
$[{K\choose\mu K+1}]$. Then, an MN PDA is defined as a ${K\choose\mu K}\times
K$ array $\mathbf{P}=(\mathbf{P}(\mathcal{D},k))_{\mathcal{D}\in{[K]\choose\mu
K},k\in[K]}$ by

$\displaystyle\mathbf{P}(\mathcal{D},k)=\left\\{\begin{array}[]{cc}\phi(\mathcal{D}\cup\\{k\\}),&\mbox{if}~{}k\notin\mathcal{D}\\\
,&\mbox{otherwise}\end{array}\right.$ (4)

where each of the $\binom{K}{\mu K}$ rows in the array is labelled by a
distinct subset in ${[K]\choose\mu K}$. Thus, according to the definition of
PDA, the achieved load by the MN PDA is as follows.

######  Lemma 2.

(MN PDA[2]) For any positive integer $K$ and each
$\mu\in\\{\frac{1}{K},\frac{2}{K},\ldots,\frac{K-1}{K},1\\}$, there exists a
$\left(K,{K\choose\mu K},{K-1\choose\mu K-1},{K\choose\mu K+1}\right)$ PDA,
which leads a ${K\choose\mu K}$-division $(K,M,N)$ shared-link coded caching
scheme with memory ratio $\frac{M}{N}=\frac{t}{K}$ and load $R=\frac{K-\mu
K}{t+1}$. $\square$

######  Example 1.

We then illustrate the MN PDA by the following example where $N=K=4$ and
$M=2$. By the construction of the MN PDA, we have the following $(4,6,3,4)$
PDA,

$\displaystyle\mathbf{P}=\left(\begin{array}[]{cccc}*&*&1&2\\\ &1&*&3\\\
&2&3&*\\\ 1&*&*&4\\\ 2&*&4&*\\\ 3&4&*&*\end{array}\right).$ (11)

Using Algorithm 1, the detailed caching scheme is as follows.

  * •

Placement Phase: From Line 2 of the algorithm we have
$W_{n}=(W_{n,1},W_{n,2},W_{n,3},W_{n,4},W_{n,5},W_{n,6})$ where $n\in[4]$.
Then by Lines 3-5 in Algorithm 1, the users’ caches are

$\displaystyle\mathcal{Z}_{U_{1}}=\left\\{W_{n,1},W_{n,2},W_{n,3}\ |\
n\in[4]\right\\};\ \ \ \ \ \ \
\mathcal{Z}_{U_{2}}=\left\\{W_{n,1},W_{n,4},W_{n,5}\ |\ n\in[4]\right\\};$
$\displaystyle\mathcal{Z}_{U_{3}}=\left\\{W_{n,2},W_{n,4},W_{n,6}\ |\
n\in[4]\right\\};\ \ \ \ \ \ \
\mathcal{Z}_{U4}=\left\\{W_{n,3},W_{n,5},W_{n,6}\ |\ n\in[4]\right\\}.$

  * •

Delivery Phase: Assume that the request vector is $\mathbf{d}=(1,2,3,4)$. By
the transmitting process by Lines 8-10 in Algorithm 1, the server transmits
the multicast messages in Table I, with total load
$R=\frac{4}{6}=\frac{2}{3}$.

Time slot | Multicast messages
---|---
$1$ | $W_{1,4}\oplus W_{2,2}\oplus W_{3,1}$
$2$ | $W_{1,5}\oplus W_{2,3}\oplus W_{4,1}$
$3$ | $W_{1,6}\oplus W_{3,3}\oplus W_{4,2}$
$4$ | $W_{2,6}\oplus W_{3,5}\oplus W_{4,4}$
TABLE I: Delivery phase in Example 1

$\square$

In the literature of shared-link coded caching model, there are many
constructions based on PDA [14, 16, 15, 37, 18, 38, 7, 12, 9, 17]. Some other
constructions could be also transformed into PDAs such as the caching schemes
based on liner block code [11], projective space [39], combinatorial designs
[40], etc. We list their performances in Table II.

TABLE II: Existing PDAs where $K,K_{1},m,t,q,a,b,r\in\mathbb{Z}^{+}$, $\mu\in\\{i/K\ |\ i\in[0:K]\\}$ and $\mu_{1}\in\\{i/K\ |\ i\in[0:K_{1}]\\}$. Define that $\left[m\atop t\right]_{q}=\frac{(q^{m}-1)\cdots(q^{m-t+1}-1)}{(q^{t}-1)\cdots(q-1)}$. The greatest common divisor of $k$ and $K$ is denoted by $gcd(k,K)$. PDAs | $K$ | $F$ | $Z$ | $S$
---|---|---|---|---
[2, 7, 37] | $K$ | ${K\choose\mu K}$ | ${K-1\choose\mu K-1}$ | ${K\choose\mu K+1}$
[41, 14]: | $K$ | $\frac{K_{1}}{gcd(K_{1},K)}{K_{1}\choose\mu_{1}K_{1}}$ | $\frac{K_{1}}{gcd(K_{1},K)}{K_{1}-1\choose\mu_{1}K_{1}-1}$ | $\frac{K}{gcd(K_{1},K)}{K_{1}\choose\mu_{1}K_{1}+1}$
[7, 11, 37]: $m\geq 2,q\geq 2$ | $mq$ | $q^{m-1}$ | $q^{m-2}$ | $(q-1)q^{m-1}$
$(q-1)q^{m-1}$ | $(q-1)^{2}q^{m-2}$ | $q^{m-1}$
|  [9, 16, 37]:
---
$b<m$, $q\geq 2$
${m\choose t}q^{t}$ | $q^{m}$ | $\left(1-\left(\frac{q-1}{q}\right)^{t}\right)q^{m}$ | $(q-1)^{t}q^{m}$
[16]: $z<q$, $t<m$ | ${m\choose t}q^{t}$ | $\left\lfloor\frac{q-1}{q-z}\right\rfloor^{t}q^{m}$ | $\left(1-\left(\frac{q-z}{q}\right)^{t}\right)\left\lfloor\frac{q-1}{q-z}\right\rfloor^{t}q^{m}$ | $(q-z)^{t}q^{m}$
$mq$ | $\lfloor\frac{q-1}{q-z}\rfloor q^{m-1}$ | $\lfloor\frac{q-1}{q-z}\rfloor q^{m-2}$ | $(q-z)q^{m-1}$
[37]: $t<m$, $q\geq 2$ | ${m\choose t}q^{t}$ | $q^{m-t}$ | $\left(1-\left(\frac{q-1}{q}\right)^{t}\right)q^{m-t}$ | $(q^{t}-1)q^{m-t}$
${m\choose t}q^{t}$ | $q^{m-1}$ | $\left(1-\left(\frac{q-1}{q}\right)^{t}\right)q^{m-1}$ | $(q-1)^{t}q^{m-1}$
|  [12, 15]: $\eta<a$
---
$<m$, $\eta<b<m$,
$a+b\leq m+\eta$
${m\choose a}$ | ${m\choose b}$ | $\left(1-\frac{{a\choose\eta}{m-a\choose b-\eta}}{{m\choose b}}\right){m\choose b}$ |  | ${m\choose a+b-2\eta}\cdot$
---
$\min\\{{m-a-b+2\eta\choose\eta},$
${{a+b-2\eta\choose a-\eta}}\\}$
[39]: $a+t\leq m$, prime power $q\geq 2$ |  | $\frac{1}{t!}q^{\frac{t(t-1)}{2}}$
---
$\prod_{i=0}^{t-1}\left[m-i\atop 1\right]_{q}$
| $\frac{1}{a!}q^{\frac{a(a-1)}{2}}$
---
$\prod_{i=0}^{a-1}\left[m-i\atop 1\right]_{q}$
| $\frac{1}{a!}q^{\frac{a(a-1)}{2}}\left(\prod_{i=0}^{a-1}\left[m-i\atop
1\right]_{q}\right.$
---
$\left.-q^{at}\prod_{i=0}^{a-1}\left[m-t-i\atop 1\right]_{q}\right)$
| $\frac{1}{(a+t)!}q^{\frac{(a+t)(a+t-1)}{2}}$
---
$\prod_{i=0}^{a+t-1}\left[m-i\atop 1\right]_{q}$
$\left[m\atop t\right]_{q}$ | $\left[m\atop a+t\right]_{q}$ | $\left[m\atop a+t\right]_{q}-\left[m-t\atop a\right]_{q}$ | $\left[m\atop a\right]_{q}$
|  [40]: prime power
---
$q\geq 2$
$q^{2}+q+1$ | $q^{2}+q+1$ | $q^{2}$ | $q^{2}+q+1$

###  II-B Multiaccess coded caching

A multiaccess coded caching problem contains a server with a library of $N$
equal-length files (denoted by $\mathcal{W}=\\{W_{1},\ldots,W_{N}\\}$),
$\Gamma$ cache-nodes (denoted by $C_{1},\ldots,C_{\Gamma}$), and $K\leq N$
users (denoted by $U_{1},\ldots,U_{K}$). Each cache-node has a cache of size
$M$ files where $0\leq M\leq\frac{N}{L}$. The memory ratio is defined as
$\mu=M/N$. For any integer $k\in[K]$, $\mathcal{B}_{k}$ denotes the set of
cache-nodes accessible to user $U_{k}$. Assume that each user $k\in[K]$ can
access a distinct set of $L$ cache-nodes, i.e., $|\mathcal{B}_{k}|=L$. We call
the above caching model as $(L,K,\Gamma,M,N)$ multiaccess coded caching system
with access topology $\mathfrak{B}=\\{\mathcal{B}_{k}\ |\ k\in[K]\\}$.

An $F$-division $(L,K,\Gamma,M,N)$ coded caching scheme with access topology
$\mathfrak{B}$ runs in two phases:

  * •

Placement phase: Each file is divided into $F$ packets of equal size. Each
cache-node $C_{\gamma}$ where $\gamma\in[\Gamma]$, caches a totally of up to
$MF$ packets of files. Let $\mathcal{Z}_{C_{\gamma}}$ denote the cache content
at cache-node $C_{\gamma}$. The placement phase is also done without knowledge
of later requests. Each user $U_{k}$ where $k\in[K]$ can retrieve the packets
cached at the $L$ cache-nodes in $\mathcal{B}_{k}$. Let $\mathcal{Z}_{U_{k}}$
denote the packets retrievable by user $U_{k}$.

  * •

Delivery phase: Each user requests one file. According to the request vector
$\mathbf{d}=(d_{U_{1}},d_{U_{2}}$, $\ldots$, $d_{U_{K}})$, the cache content
in cache-nodes and the access topology, the server broadcasts $S_{{\bf d}}$
coded packets to all users, such that each user’s request can be satisfied.

We aim to design multiaccess coded caching schemes with minimum worst-case
load as defined in (1).

The PDA construction (review in Section II-A) could be extended to the MACC
model, to construct MACC coded caching schemes with with the uncoded placement
and one-shot delivery, as proposed in [19]. The placement and delivery
strategies of such MACC can be characterised by three arrays defined as
follows.

######  Definition 2 ([19]).

  * •

An $F\times\Gamma$ node-placement array $\mathbf{C}$ consists of star and
null, where $F$ and $\Gamma$ represent the subpacketization of each subfile
and the number of cache-nodes, respectively. For any integers $j\in[F]$ and
$\gamma\in[\Gamma]$, the entry $\mathbf{C}(j,\gamma)$ is star if and only if
the $\gamma^{\text{th}}$ cache-node caches the $j^{\text{th}}$ packet of each
$W_{n}$ where $n\in[N]$.

  * •

An $F\times K$ user-retrieve array $\mathbf{U}$ consists of star and null,
where $F$ and $K$ represent the subpacketization of each subfile and the
number of users, respectively. For any integers $j\in[F]$ and
$\gamma\in[\Gamma]$, the entry $\mathbf{U}(j,k)$ is a star if and only if the
$k^{\text{th}}$ user can retrieve the $j^{\text{th}}$ packet of each $W_{n}$
where $n\in[N]$ from its connected cache-nodes.

  * •

An $F\times K$ user-delivery array $\mathbf{Q}$ consists of $\\{*\\}\cup[S]$,
where $F$, $K$ and the stars in $\mathbf{Q}$ have the same meaning as $F$, $K$
of $\mathbf{U}$ and the stars in $\mathbf{U}$, respectively. Each integer
represents one multicast message, and $S$ represents the total number of
multicast messages sent in the delivery phase. $\square$

The authors in [19] showed that if user-delivery array $\mathbf{Q}$ satisfies
Condition C3 in Definition 1, each user can decode its required file by its
retrievable cache content and received coded messages from server. Furthermore
if each column of $\mathbf{Q}$ has exactly $Z$ stars, then $\mathbf{Q}$ is a
$(K,F,Z,S)$ PDA. In this paper we will construct the above arrays to obtain
new MACC schemes.

For the sake of simplicity we do not distinguish between user $U_{k}$ and its
accessible cache-node set $\mathcal{B}_{k}$ unless otherwise stated. Then any
fixed access topology can be represented by an appropriate combinatorial
structure. In this paper we will consider some classical combinatorial
structures in combinatorial design theory as the access topologies. In the
following we will introduce some necessary combinatorial concepts that will be
used in our paper.

##  III Combinatorial Designs

###  III-A $t$-design

######  Definition 3.

([42], Design) A design is a pair $(\mathcal{X},\mathfrak{B})$ such that the
following properties are satisfied:

  * •

$\mathcal{X}$ is a set of elements (called points), and

  * •

$\mathfrak{B}$ is a collection of non-empty subsets of $\mathcal{X}$ (called
blocks).

$\square$

######  Definition 4.

([43], $t$-design) Let $\Gamma$, $K$, $L$, $t$ and $\lambda$ be positive
integers. A $t$-$(\Gamma,L,K,\lambda)$ design is a design
$(\mathcal{X},\mathfrak{B})$ where $\mathcal{X}$ has $\Gamma$ points and
$\mathfrak{B}$ has $K$ blocks such that the following properties are
satisfied:

  * •

$|\mathcal{B}|=L$ for any $\mathcal{B}\in\mathfrak{B}$;

  * •

every $t$-subset of $\mathcal{X}$ is contained in exactly $\lambda$ blocks.

$\square$

By Definition 4, the number of blocks is

$\displaystyle K=\frac{\lambda{\Gamma\choose t}}{{L\choose t}}\approx
O\left(\Gamma^{t}\right)\ \ \ \ \ (\Gamma\rightarrow\infty,\Gamma\gg t).$ (12)

Therefore, a $t$-$(\Gamma,L,K,\lambda)$ design is also referred to as a
$t$-$(\Gamma,L,\lambda)$ design in this paper. Note that for a
$t$-$(\Gamma,L,K,\lambda)$ design, each point appears the same time in all
blocks, i.e.,
$r=KL/\Gamma=\frac{\lambda\binom{\Gamma-1}{t-1}}{\binom{L-1}{t-1}}$.

A $t$-$(\Gamma,L,\lambda)$ design is also a
$t^{\prime}$-$(\Gamma,L,\lambda_{t^{\prime}})$ design where $t^{\prime}\leq t$
and

$\displaystyle\lambda_{t^{\prime}}=\frac{\lambda{\Gamma-t^{\prime}\choose
t-t^{\prime}}}{\binom{L-t^{\prime}}{t-t^{\prime}}}.$ (13)

The $2$-$(\Gamma,L,\lambda)$ design is always called $(\Gamma,L,\lambda)$
balanced incomplete block design (in short $(\Gamma,L,\lambda)$ BIBD).

######  Example 2.

1) When $\Gamma=7$ and $L=3$, let $\mathcal{X}=\\{1,2,3,4,5,6,7\\}$ and

$\mathfrak{B}=\\{\\{1,2,4\\},\\{2,3,5\\},\\{3,4,6\\},\\{4,5,7\\},\\{5,6,1\\},\\{6,7,2\\},\\{7,1,3\\}\\}.$

Then $(\mathcal{X},\mathfrak{B})$ is a $2$-$(7,3,1)$ design, i.e., $(7,3,1)$
BIBD.

2) When $\Gamma=9$ and $L=3$, let $\mathcal{X}=\\{1,2,3,4,5,6,7,8,9\\}$ and

$\displaystyle\mathfrak{B}=$
$\displaystyle\\{\\{1,4,7\\},\\{2,5,8\\},\\{3,6,9\\},\\{1,2,3\\},\\{4,5,6\\},\\{7,8,9\\},\\{1,6,8\\},\\{2,4,9\\},\\{3,5,7\\},$
$\displaystyle\\{1,5,9\\},\\{2,6,7\\},\\{3,4,8\\}\\}.$

Then $(\mathcal{X},\mathfrak{B})$ design is a $2$-$(9,3,1)$ design, i.e.,
$(9,3,1)$ BIBD. $\square$

Recently, the following sufficient and necessary condition of the existence of
$t$-design was proved in [44, 45].

######  Lemma 3 ([44, 45]).

Given $t$, $L$ and $\lambda$, there exists an integer
$\Gamma_{0}(t,L,\lambda)$ (which is a function of $(t,L,\lambda)$) such that
for any $\Gamma>\Gamma_{0}(t,L,\lambda)$, a $t$-$(\Gamma,L,\lambda)$ design
exists if and only if for any $0\leq i\leq t-1$, ${L-i\choose t-i}$ divides
$\lambda{\Gamma-i\choose t-i}$. $\square$

For example, if $t=2$ and $L=3$, we have
$\Gamma_{0}(2,3,1)=\Gamma_{0}(2,3,2)=2$ in [43, Page 72, Section 3, Chapter
II]. Since the general expression of $\Gamma_{0}(t,L,\lambda)$ is very
complicated, the interested reader could refer to [44, 45] for the details.

###  III-B $t$-GDD

Next we will review another specific type of design, referred to as group
divisible design, which is also useful to our later construction.

######  Definition 5.

([43], $t$-GDD) Let $L$, $t$, $q$ and $m$ be positive integers with $t\leq
L\leq m$. A $(m,q,L,\lambda)$ group divisible $t$-design (a.k.a,
$t$-$(m,q,L,\lambda)$ GDD) is a triple
$(\mathcal{X},\mathfrak{G},\mathfrak{B})$ where

  * •

$\mathcal{X}$ is a set of $\Gamma=mq$ points;

  * •

$\mathfrak{G}=\\{\mathcal{G}_{1},\mathcal{G}_{2},\ldots,\mathcal{G}_{m}\\}$ is
a partition of $\mathcal{X}$ into $m$ non-overlapping subsets (called groups),
where each subset has size $q$;

  * •

$\mathfrak{B}$ is a family of $L$-blocks of $\mathcal{X}$ such that every
block intersects every group in at most one point, and every $t$-subset of
points from $t$ distinct groups belongs to exactly $\lambda$ blocks.

$\square$

We can obtain the number of blocks in $\mathfrak{B}$ by Definition 5 as
follows.

$\displaystyle K=\frac{\lambda{m\choose t}q^{t}}{{L\choose t}}$ (14)

From (12) and (14) the number of blocks in a $t$-$(\Gamma,L,\lambda)$ design
is no smaller than that of a $t$-$(m,q,L,\lambda)$ GDD, since

$\displaystyle\frac{\lambda{\Gamma\choose t}}{{L\choose
t}}=\frac{\lambda{mq\choose t}}{{L\choose t}}\geq\frac{\lambda{m\choose
t}q^{t}}{{L\choose t}},$

where the equality holds when $q=1$. In other words, when $q=1$, the
$t$-$(m,1,L,\lambda)$ GDD is exactly $t$-$(m,L,\lambda)$ design.

######  Remark 1 (Point representation of GDD).

By Definition 5, in a $t$-$(m,q,L,\lambda)$ GDD for any $u\in[m]$ and
$v\in[q]$, we can denote the $v^{\text{th}}$ point of $u^{\text{th}}$ group by
a vector $(u,v)$.

######  Example 3.

When $m=3$, $q=2$ and $L=3$, we have $\Gamma=mq=6$. Let

$\displaystyle\begin{split}\mathcal{X}&=\\{(1,1),(1,2),(2,1),(2,2),(3,1),(3,2)\\},\\\
\mathfrak{G}&=\\{\mathcal{G}_{1}=\\{(1,1),(1,2)\\},\mathcal{G}_{2}=\\{(2,1),(2,2)\\},\mathcal{G}_{3}=\\{(3,1),(3,2)\\}\\},&\\\
\mathfrak{B}&=\\{\\{(1,1),(2,1),(3,1)\\},\\{(1,2),(2,1),(3,2)\\},\\{(1,1),(2,2),(3,2)\\},\\{(1,2),(2,2),(3,1)\\}\\}.&\end{split}$
(15)

By Definition 5 we can check that the triple
$(\mathcal{X},\mathfrak{G},\mathfrak{B})$ is a $2$-$(3,2,3,1)$ GDD.

By Definition 4 and Definition 5, we can see that any $t$-design could be seen
as a $t$-GDD with $q=1$. There are many results on the construction and
existence of the $t$-GDDs; please refer to [43, Section IV-4] for the details.
The existence of the $t$-GDD with $\lambda=1$ is given in the following lemma.

######  Lemma 4.

([46]) Given $t$, $L$ and $m$ where $t\leq L\leq m$, there exists an integer
$q_{0}(t,L,m)$ (which is a function of $(t,L,m)$) such that for any $q\geq
q_{0}$, a $t$-$(m,q,L,1)$ GDD exists if and only if for any $0\leq i\leq t-1$,
${L-i\choose t-i}$ divides $q^{t-i}{m-i\choose t-i}$.

In the following we will show that the concept of cross resolvable design
proposed in [29] is a special case of $t$-GDD.

######  Definition 6.

([29], Resolvable design and cross resolvable design) A design
$(\mathcal{V},\mathfrak{A})$ is called resolvable if the blocks in
$\mathfrak{A}$ can be divided into parallel classes where the blocks in each
class partition the set of elements $\mathcal{V}$. A resolvable design
$(\mathcal{V},\mathfrak{A})$ is called $t$-cross if the intersection of any
$t$ blocks drawn from any $t$ distinct parallel classes has the same size
$\lambda_{t}$, referred to as the $t^{\text{th}}$ cross intersection number.
$\square$

For the sake of clarification, in the following we use the
$t$-$(v,k,\Gamma,m,\lambda_{t})$ resolvable design to represent the $t$-cross
resolvable design $(\mathcal{V},\mathfrak{A})$, by letting $|\mathcal{V}|=v$
and $\mathfrak{A}$ contain $\Gamma$ blocks with of size $k$, where
$\mathfrak{A}=\mathfrak{A}_{1}\cup\mathfrak{A}_{2}\cup\cdots\cup\mathfrak{A}_{m}$
can be divided into $m$ parallel classes.

For any design $(\mathcal{V},\mathfrak{A})$, we define its dual design as
follows: we regard the blocks in $\mathfrak{A}$ as points and the points in
$\mathcal{V}$ as blocks, where in the dual design each point represented by
$\mathcal{A}\in\mathfrak{A}$ is contained by a block represented by
$a\in\mathcal{V}$ if and only if $a\in\mathcal{A}$; then the resulting design
$(\mathcal{X},\mathfrak{B})$ is called the dual design of
$(\mathcal{V},\mathfrak{A})$. Clearly a design is a dual design of its dual
design.

######  Example 4.

Let $\mathcal{V}=[4]$ and
$\mathfrak{A}=\mathfrak{A}_{1}\cup\mathfrak{A}_{2}\cup\mathfrak{A}_{3}$ where

$\displaystyle\mathfrak{A}_{1}=\\{\mathcal{A}_{1}=\\{1,3\\},\mathcal{A}_{2}=\\{2,4\\}\\},\
\ \
\mathfrak{A}_{2}=\\{\mathcal{A}_{3}=\\{1,2\\},\mathcal{A}_{4}=\\{3,4\\}\\},$
$\displaystyle\mathfrak{A}_{3}=\\{\mathcal{A}_{5}=\\{1,4\\},\mathcal{A}_{6}=\\{2,3\\}\\}.$
(16)

It can be seen that the intersection of any two blocks from different parallel
classes contains exactly one point. So by Definition 6,
$(\mathcal{V},\mathfrak{A})$ is a $2$-$(v,k,\Gamma,m,\lambda_{t})=(4,2,6,3,1)$
resolvable design. Then its dual design is $(\mathcal{X},\mathfrak{B})$ where

$\displaystyle\mathcal{X}=\mathfrak{A}=\\{(1,1)=\mathcal{A}_{1},(1,2)=\mathcal{A}_{2},(2,1)=\mathcal{A}_{3},(2,2)=\mathcal{A}_{4},(3,1)=\mathcal{A}_{5},\mathcal{A}_{6}\\}$
(17)

and all the blocks are

$\displaystyle\mathfrak{B}=\\{\ $
$\displaystyle\\{(1,1)=\mathcal{A}_{1},(2,1)=\mathcal{A}_{3},(3,1)=\mathcal{A}_{5}\\},$
$\displaystyle\\{(1,2)=\mathcal{A}_{2},(2,1)=\mathcal{A}_{3},(2,2)=\mathcal{A}_{6}\\},$
$\displaystyle\\{(1,1)=\mathcal{A}_{1},(2,2)=\mathcal{A}_{4},(3,2)=\mathcal{A}_{6}\\},$
$\displaystyle\\{(1,2)=\mathcal{A}_{2},(2,2)=\mathcal{A}_{4},(3,1)=\mathcal{A}_{5}\\}\
\\}.$ (18)

Let $\mathcal{G}_{i}=\mathfrak{A}_{i}$ for each $i\in[3]$, then we can define
the set of groups

$\displaystyle\mathfrak{G}=\\{\ $
$\displaystyle\mathcal{G}_{1}=\\{(1,1)=\mathcal{A}_{1},(1,2)=\mathcal{A}_{2}\\},$
$\displaystyle\mathcal{G}_{2}=\\{(2,1)=\mathcal{A}_{3},(2,2)=\mathcal{A}_{4}\\},$
$\displaystyle\mathcal{G}_{3}=\\{(3,1)=\mathcal{A}_{5},(3,2)=\mathcal{A}_{6}\\}\
\\}.$ (19)

We can check that $(\mathcal{X},\mathfrak{G},\mathfrak{B})$ is a
$t$-$(m,q,L,\lambda)=$ $2$-$(3,2,3,1)$ GDD which is exactly the GDD in Example
3. $\square$

Using the above transformation method in Example 4, we can obtain the
following result that the dual of any cross resolvable design is a GDD, whose
proof could be found in Appendix A.

######  Lemma 5.

The dual of a $t$-$(v,k,\Gamma,m,\lambda_{t})$ resolvable design
$(\mathcal{V},\mathfrak{A})$ is a $t$-$(m,q,m,\lambda_{t})$ GDD where $q=v/k$.
$\square$

###  III-C Orthogonal array (OA)

Next, we review a classical combinatorial structure called an orthogonal
array, which will be used in the placement phase of the proposed caching
scheme for the $t$-GDD access topology.

######  Definition 7.

([42], OA) Let $\mathbf{A}$ be an $F_{1}\times m$ matrix whose element is in
$[q]$, for positive integers $F_{1}$, $m$, $q\geq 2$, and $s\leq m$.
$\mathbf{A}$ is an orthogonal array (OA) of strength $s$, denoted by
OA${}_{\lambda}(F_{1},m,q,s)$, if each $1\times s$ row vector in $[q]^{s}$
appears exactly $\lambda$ times in $\mathbf{A}(\cdot,\mathcal{S})$ for each
$\mathcal{S}\in{[m]\choose s}$. $\square$

By definition, we have $F_{1}=\lambda q^{s}$; then any
OA${}_{\lambda}(F_{1},m,q,s)$ can be also written as OA${}_{\lambda}(m,q,s)$
for short [42]. The parameter $\lambda$ is the index of the orthogonal array.
If $\lambda$ is omitted, then it is understood to be $1$.

######  Example 5.

Let us consider the following array,

$\displaystyle\mathbf{A}=\left(\begin{array}[]{ccc}1&1&1\\\ 2&1&2\\\ 1&2&2\\\
2&2&1\end{array}\right).$ (24)

Then we have

$\displaystyle\mathbf{A}(\cdot,\\{1,2\\})=\left(\begin{array}[]{cc}1&1\\\
2&1\\\ 1&2\\\ 2&2\end{array}\right),\ \
\mathbf{A}(\cdot,\\{1,3\\})=\left(\begin{array}[]{cc}1&1\\\ 2&2\\\ 1&2\\\
2&1\end{array}\right),\ \
\mathbf{A}(\cdot,\\{2,3\\})=\left(\begin{array}[]{cc}1&1\\\ 1&2\\\ 2&2\\\
2&1\end{array}\right).$

Clearly for each $\mathcal{S}\in\\{\\{1,2\\},\\{1,3\\},\\{2,3\\}\\}$, each
vector in $[2]^{2}=\\{(1,1),(1,2),(2,1),(2,2)\\}$ appears exactly once in the
rows of $\mathbf{A}(\cdot,\mathcal{S})$. So $\mathbf{A}$ in (24) satisfies
Definition 7, and thus is an OA$(3,2,2)$. $\square$

OA has been widely studied in combinatorial theory, graph theory and coding
theory [43]. There are many results on the construction and existence of the
OAs; please refer to [43, Section II-6,7] for more details. In particular, it
is well known that for any positive integers $m$, $s$ and $s<m$, there exists
an OA$(m,q,s)$ for some prime $q$. In fact, there is a one-to-one mapping
between cross resolvable design and OA. Let us first take an example to show
this mapping.

######  Example 6.

Recall that the $(\mathcal{V},\mathfrak{A})$ is a
$t$-$(v,k,\Gamma,m,\lambda)=2$-$(4,2,6,3,1)$ resolvable design in Example 4.
The dual design of this resolvable design is a $t$-$(m,q,m,\lambda)=$
$2$-$(3,2,3,1)$ GDD $(\mathcal{X},\mathfrak{G},\mathfrak{B})$, where
$\mathcal{X}=\mathfrak{A}$ in (17), all the groups of $\mathfrak{G}$ are in
(19) and all the blocks of $\mathfrak{B}$ are in (18). We sort all the points
in $\mathcal{X}$ in an arbitrary fixed order; for example we sort all points
in $\mathfrak{A}$ in the lexicographic order, i.e.,
$\mathfrak{A}=\\{(1,1),(1,2),(2,1),(2,2),(3,1),(3,2)\\}$. Then we represent
each block by a row vector according to the above order; for example, the
first block of $\mathfrak{B}$ in (18), $\\{(1,1),(2,1),(3,1)\\}$ is
represented by a row vector $((1,1),(2,1),(3,1))$. Similarly, $\mathfrak{B}$
can be represented by the following array,

$\displaystyle\mathbf{A}_{\mathfrak{B}}=\left(\begin{array}[]{ccc}(1,1)&(2,1)&(3,1)\\\
(1,2)&(2,1)&(3,2)\\\ (1,1)&(2,2)&(3,2)\\\
(1,2)&(2,2)&(3,1)\end{array}\right).$

Next we replace each element in $\mathbf{A}_{\mathfrak{B}}$ by its second
coordinate. For example, $(1,1)$ is replaced by $1$; $(1,2)$ is replaced its
second coordinate $2$; $(3,2)$ is replaced by its second coordinate $2$.
Similarly, the resulting array after the above replacement process is

$\displaystyle\mathbf{A}=\left(\begin{array}[]{ccc}1&1&1\\\ 2&1&2\\\ 1&2&2\\\
2&2&1\end{array}\right).$

It is interesting to see that the resulting array $\mathbf{A}$ is an
OA${}_{\lambda}(m,v/k,t)=$OA$(3,2,2)$ in (24).

Furthermore, given the OA in (24), we can also obtain the
$2$-$(v,k,\Gamma,m,\lambda)=(4,2,6,3,1)$ resolvable design in Example 4 by
performing the corresponding inverse operations. Hence, there is a one-to-one
mapping between OA and cross resolvable design. $\square$

Using the above transformation method in Example 6, we have the one-to-one
mapping between a cross resolvable design and an OA, whose proof could be
found in Appendix B.

######  Lemma 6.

There is a one-to-one mapping between a $t$-$(v,k,\Gamma,m,\lambda_{t})$
resolvable design and an OA${}_{\lambda_{t}}(m,q,t)$ where $q=v/k$. $\square$

##  IV Main results

We first consider the access topology as a $t$-design. By leveraging the MN
placement strategy and the properties of $t$-design, we propose a MACC scheme
with the following load, whose description could be found in Section V.

######  Theorem 1 ($t$-design scheme).

Consider a $(L,K,\Gamma,M,N)$ multiaccess coded caching system with access
topology $\mathfrak{B}$ where $([\Gamma],\mathfrak{B})$ is a
$t$-$(\Gamma,L,1)$ design, for positive integers $\Gamma$, $L$ and $t\geq 2$,
the lower convex envelop of the following memory-load tradeoff points is
achievable,

$\displaystyle(M,R_{\text{Th1}})=\left(\mu N,\frac{{\Gamma\choose
t+\mu\Gamma}-K{L\choose t+\mu\Gamma}-\sum^{\mu\Gamma-1}_{i=1}{L\choose
t+i}{\Gamma-L\choose\mu\Gamma-i}}{{\Gamma\choose\mu\Gamma}{L\choose
t}}\right),$ (25)

for each
$\mu=0,\frac{1}{\Gamma},\frac{2}{\Gamma},\ldots,\frac{\Gamma-L}{\Gamma}$.
$\square$

Note that to achieve each memory-load tradeoff point in (25), we first
construct a MACC scheme with whose user-delivery array is a $(K={\Gamma\choose
t}/{L\choose t}$, $F={\Gamma\choose\mu\Gamma}{L\choose t}$,
$Z=\left({\Gamma\choose\mu\Gamma}-{\Gamma-L\choose\mu\Gamma}\right){L\choose
t}$, $S={\Gamma\choose t+\mu\Gamma}$ $-K{L\choose t+\mu\Gamma})$ PDA. Then by
observing each user can re-construct some multicast messages from its
retrieval cache content, we use a $[n,k]$ maximum distance separable (MDS)
code to further reduce the number of transmissions where $n={\Gamma\choose
t+\mu\Gamma}-K{L\choose t+\mu\Gamma}$ and $k={\Gamma\choose
t+\mu\Gamma}-K{L\choose t+\mu\Gamma}-\sum^{\mu\Gamma-1}_{i=1}{L\choose
t+i}{\Gamma-L\choose\mu\Gamma-i}$

.

By Definition 4 and Definition 5, a $t$-$(m,1,L,\lambda)$ GDD is also a
$t$-$(m,L,\lambda)$ design. Next we generalize the access topology in Theorem
1 (i.e., the $t$-design access topology) to the $t$-GDD access topology and
propose a MACC scheme which uses the OA structure into the cache placement by
extending the construction of the PDA in Theorem 1. The achieved load is
stated in the following theorem and the description on the scheme could be
found in Section VI.

######  Theorem 2 ($t$-GDD scheme).

Consider a $(L,K,\Gamma,M,N)$ multiaccess coded caching system with a
$t$-$(m,q,L,1)$ GDD access topology $\mathfrak{B}$ where
$([\Gamma=mq],\mathfrak{G},\mathfrak{B})$ is for positive integers $m$, $q$,
$L$, $t$ and $s$ with $1\leq t\leq L\leq s\leq m$, if there exists an
OA$(m,q,s)$, the following memory-load tradeoff point is achievable,

$\displaystyle(M,R_{\text{Th2}})=\left(\frac{\left(q^{s}-(q-1)^{L}q^{s-L}\right){L\choose
t}}{q^{s}{L\choose t}}N,\frac{q^{m-s}(q-1)^{t}}{{L\choose t}}\right).$ (26)

$\square$

Note that we consider $t$-$(\Gamma,L,\lambda=1)$ design and
$t$-$(m,q,L,\lambda=1)$ GDD as access topologies. For $\lambda>1$, we can also
extend the proposed schemes to the $t$-$(\Gamma,L,\lambda)$ design and
$t$-$(m,q,L,\lambda)$ GDD access topologies. For the details, please referred
to Section VII.

###  IV-A Performance analysis on the proposed schemes in Theorems 1 and 2

By Lemma 3 and Theorem 1, we can obtain arbitrary $t$-$(\Gamma,L,\lambda)$
designs for any parameters $t$, $\Gamma$, $L$ and $\lambda$ when $\Gamma$ is
larger than a threshold $\Gamma_{0}$.444For instance when $t=2$ and $L=3$, it
is well known that $\Gamma_{0}=3$ for any $\lambda\in[3]$. Then by Theorem 1,
we can obtain a $(L,K={\Gamma\choose t}/{L\choose t},\Gamma,M,N)$ multiaccess
coded caching scheme with memory ratio $\mu=M/N$, subpacketization
$F={\Gamma\choose\mu\Gamma}{L\choose t}$ and transmission load in (25). Note
that the number of serving users is $K={\Gamma\choose t}/{L\choose t}$. By
letting $t$ vary from $1$ to $L$, we can have a wide range of user numbers,
which can scale linearly, polynomially, or exponentially with the number of
cache-nodes $\Gamma$. As a result, we can serve a very flexible number of
users. By Lemma 4 and Theorem 2, we can also server a very flexible number of
users.

For any positive integers $\Gamma$ and $L$, there always exists a
$L$-$\left(\Gamma,L,K={\Gamma\choose L},r={\Gamma-1\choose L-1},1\right)$
design $\left(\mathcal{X}=[\Gamma],\mathfrak{B}={[\Gamma]\choose L}\right)$.
In fact, the combinatorial access topology proposed in [33] is exactly the
$L$-$\left(\Gamma,L,K={\Gamma\choose L},r={\Gamma-1\choose L-1},1\right)$
design access topology. Then by Theorem 1, we have a $\left({\Gamma\choose
L},{\Gamma\choose\mu\Gamma},{\Gamma\choose\mu\Gamma}-{\Gamma-L\choose\mu\Gamma},{\Gamma\choose\mu\Gamma+L}\right)$
PDA which leads to a $(L,r={\Gamma-1\choose L-1},K={\Gamma\choose L},M,N)$
multiaccess coded caching scheme based on
$\left(\mathcal{X}=[\Gamma],\mathfrak{B}={[\Gamma]\choose L}\right)$, i.e.,
combinatorial access topology, with memory ratio $\mu=\frac{M}{N}$,
subpacketization $F={\Gamma\choose\mu\Gamma}$ and load
$R_{\text{Th1}}={\Gamma\choose\mu\Gamma+L}/{\Gamma\choose\mu\Gamma}$. This
scheme is exactly the scheme proposed in [33], which was shown to be optimal
under uncoded cache placement and combinatorial access topology [34].

Next, let us compare the scheme in Theorem 2 with the schemes in [35, 36, 29]
for the multiaccess access topology. The scheme in [29] has a coded
multicasting gain equal to $4$ under a
$2$-$(q^{m},q^{m-1},\frac{q(q^{m}-1)}{q-1},\frac{q^{m}-1}{q-1},q^{m-2})$
resolvable design with $L=2$ and memory ratio $M/N=1/q$ where $q$ is any prime
power and $m$ is any positive integer larger than $1$. In this paper we only
devote to studying the coded caching gain that depends on the value of the
parameters $L$, $\Gamma$ and memory ratio $M/N=1/q$ where $q$ is any positive
integer. Furthermore when the memory ratio is $M/N=1/q$, the scheme in [29] is
reduced to the scheme in [35]. So we only need to compare with the scheme with
memory ratio $M/N=1/q$ in [35], where the authors used the OA$(m,q,m)$ for any
positive integer $m$ and $q\geq 2$ as the placement strategy to obtain the
following result.

######  Lemma 7.

(CRS in [35] generated by OA$(m,q,m)$) For any positive integer $m$ and $q$,
there exists a $(L,K,\Gamma,M,N)=\left(t,{m\choose t}q^{t},mq,M,N\right)$
multiaccess coded caching for the $t$-$(v,k,\Gamma,m,\lambda)=t$-$(q^{m}$,
$q^{m-1},mq,m,q^{m-t})$ resolvable design access topology generated by
OA$(m,q,m)$ with memory ratio $M/N=1/q$, transmission load

$\displaystyle R_{\text{MR}}=\frac{\mu_{t}{q\choose 2}^{t}{m\choose
t}}{v}=\frac{q^{m-t}{q\choose 2}^{t}{m\choose t}}{4n}={m\choose
t}\left(\frac{q-1}{2}\right)^{t}$ (27)

and coded gain $g_{\text{MR}}=2^{t}$. $\square$

For the same access topology in Lemma 7, the proposed scheme in Theorem 2 is a
$(t$, ${m\choose t}q^{t}$, $mq$, $M,N)$ multiaccess coded caching scheme with
memory ratio $M/N=1/q$, transmission load $R_{\text{Th2}}=(q-1)^{t}$ and
subpacketization $q^{m-1}$. We can check that
$R_{\text{Th2}}/R_{\text{MR}}=2^{t}/{m\choose t}<1$ always holds when $t\leq
m/2$. So, when $t\leq m/2$, the proposed scheme in Theorem 2 (with $L=t$ and
$s=m-1$) has lower transmission load and subpacketization (i.e., $1/q$ times
smaller) than that of the scheme in [35].

###  IV-B Extension of the proposed schemes to the shared-link model

As a by-product, we can directly extend the proposed schemes in Theorem 1 and
Theorem 2 for the MACC model to the shared-link coded caching model in Section
II-A with the same number of users as the MACC model; this is because we can
let the retrievable content by each user in the MACC model be the the cache
content of one user in the shared-link model, while the delivery phase does
not change. Then we can obtain the following results.

######  Corollary 1.

(PDA via Theorem 1) Given a $t$-$(\Gamma,L,1)$ design, there exists a
$(K={\Gamma\choose t}/{L\choose t}$, $F={\Gamma\choose\mu\Gamma}{L\choose t}$,
$Z=\left({\Gamma\choose\mu\Gamma}-{\Gamma-L\choose\mu\Gamma}\right){L\choose
t}$, $S\leq{\Gamma\choose t+\mu\Gamma}$ $-K{L\choose t+\mu\Gamma})$ PDA. Then
the following memory-load tradeoff for shared-link model is achievable

$\displaystyle(M,R_{\text{Th}_{1}\text{-Shared-
link}})=\left(N-\frac{{\Gamma-L\choose\mu\Gamma}N}{{\Gamma\choose\mu\Gamma}},\frac{{\Gamma-\mu\Gamma\choose
t}}{{t+\mu\Gamma\choose t}{L\choose t}}-\frac{{\Gamma\choose t}{L\choose
t+\mu\Gamma}}{{\Gamma\choose\mu\Gamma}{L\choose t}^{2}}\right).$ (28)

with subpacketization $F={\Gamma\choose\mu\Gamma}{L\choose t}$. $\square$

######  Corollary 2 (PDAs via Theorem 2).

Given a $t$-$(m,q,L,1)$ GDD, we have a $(K={m\choose t}q^{t}/{L\choose t}$,
$F=q^{s}{L\choose t}$, $Z=\left(q^{s}-(q-1)^{L}q^{s-L}\right){L\choose t}$,
$S)$ PDA, where $S\leq(q-1)^{t}q^{m}$. Then the following memory-load tradeoff
for shared-link model is achievable

$\displaystyle(M,R_{\text{Th}_{2}\text{-Shared-
link}})=\left(N-\frac{(q-1)^{L}N}{q^{L}},\frac{(q-1)^{t}q^{m-s}}{{L\choose
t}}\right).$ (29)

with subpacketization $F=q^{s}{L\choose t}$. In addition, we can also compute
the exact value of $S$ in the following cases:

  * •

$L=t$ and $s=m-1$. We have $S=(q-1)^{t}q^{m-1}$ and $R_{\text{Th}_{2}\
\text{Shared-link}}=(q-1)^{t}$;

  * •

$L=t$ and $s+t=m$ with $s>t$. We have $S=(q^{t}-1)q^{m-t}$ and
$R_{\text{Th}_{2}\ \text{Shared-link}}=q^{t}-1$;

  * •

$s=m$. We have $S\leq(q-1)^{t}q^{m}$ and $R_{\text{Th}_{2}\ \text{Shared-
link}}\leq(q-1)^{t}/{L\choose t}$.

$\square$

Let us then compare our proposed PDAs in Corollary 1 and Corollary 2 and the
existing PDAs in [2, 12, 9, 11, 7, 37] for the shared-link model.

First let us consider the comparison between our PDA in Corollary 1 and the
existing PDAs in [2, 12]. For any positive integers $\Gamma$ and $L$, there
always exists a $L$-$\left(\Gamma,L,K={\Gamma\choose L},1\right)$ design and a
$1$-$(\Gamma,1,\Gamma,1)$ design. Thus by Corollary 1, we can obtain a
$({\Gamma\choose
L},{\Gamma\choose\mu\Gamma},{\Gamma\choose\mu\Gamma}-{\Gamma-L\choose\mu\Gamma},{\Gamma\choose\mu\Gamma+L})$
PDA which is exactly the PDA with the parameter $\eta=0$, $a=L$, $b=\Gamma\mu$
in [12], and also a
$(\Gamma,{\Gamma\choose\mu\Gamma},{\Gamma-1\choose\mu\Gamma-1},{\Gamma\choose\mu\Gamma+1})$
PDA which is exact the MN PDA in [2].

Now let us compare our PDA in Corollary 2 with the existing PDAs in [2, 9, 11,
7, 37]. Note that the construction of the PDAs in [37] unifies all the
constructions in [2, 9, 7, 11]. So in the following we need only to dcompare
the PDAs in Corollary 2 and the PDAs in [37], as stated in the following:

  * •

when $L=t$, for any positive integers $s+t\leq m$ we have $({m\choose
t}q^{t},q^{s},\left(q^{s}-(q-1)^{L}q^{s-t}\right),S)$ PDAs in Corollary 2 with
$S\leq q^{m}$ which are exactly the last three PDAs in [37] by Table II. This
implies that the last three PDAs in [37] listed in Table II can be covered by
the PDA in Corollary 2 by letting $L=t$, and can be directly used for the
multiaccess network. So we propose a unified construction framework from the
viewpoint of multiaccess setting;

  * •

when $L>t$, we have some other new PDAs in Theorem 2. So by Theorem 2 we have
some new schemes for the multiaccess network and the shared-link network.

From the above introduction, the relationship between the PDAs in [2, 12, 9,
11, 7, 37] and the PDAs in Theorem 1, Theorem 2 can be represented in Fig. 2.

Figure 2: The relationship among the PDAs in [2, 7, 37, 11, 9, 12] and
Corollaries 1, 2.

Finally, let us compare numerically our proposed PDAs in Corollary 1 and
Corollary 2 and the existing PDAs in [7, 37, 41, 14, 11, 9, 16, 39, 40, 15,
18, 38, 17] for the shared-link model. For the comparison, it is worth
remarking that

  * •

all the schemes in [2, 7, 11, 9] are the special cases of the scheme in [37];

  * •

we cannot find out an appropriate number of users $K$ to compare each of the
schemes in [12, 14, 39, 38, 17, 40] since all of them work for very special
numbers of users;

  * •

the schemes in [15, 38] only work for the specific number of users and the
size of memory such as the combinatorial numbers;

  * •

the scheme in [40] has the memory ratio approximating to $1$;

  * •

[18, 14, 41, 17] devote to proposing the methods such that based on a given
based PDA, we can obtain a new PDA with flexible user number and
subpacketization.

From the above remarks, we only need to compare the schemes in [16, 12, 39].
Let us consider the scheme via $t$-$(\Gamma,L,1)=2$-$(\Gamma,3,1)$ design in
Corollary 1, the scheme via $t$-$(m,q,L,1)=2$-$(m,q,3,1)$ GDD and a trivial
OA$(m,q,m)$ in Corollary 2.

First let us consider the PDA in Corollary 1. Based on a $2$-$(\Gamma,3,1)$
design, the obtained user-delivery array is a $(K,F,Z,S)$ PDA with

$\displaystyle
K=\frac{\Gamma(\Gamma-1)}{6},F=3{\Gamma\choose\mu\Gamma},Z=3\left({\Gamma\choose\mu\Gamma}-{\Gamma-3\choose\mu\Gamma}\right),S={\Gamma\choose
2+\mu\Gamma}-K{3\choose 2+\mu\Gamma}.$ (30)

By Lemma 1 we have a $(K,M,N)$ coded caching scheme for shared-link network
where

$\displaystyle\frac{M}{N}=1-(1-\mu)\left((1-\frac{\mu\Gamma}{\Gamma-1}\right)\left(1-\frac{\mu\Gamma}{\Gamma-2}\right),\
\
R=\frac{(\Gamma-\mu\Gamma)(\Gamma-\mu\Gamma-1)}{3(2+\mu\Gamma)(1+\mu\Gamma)}.$

When $K=35$, by choosing the parameters $\Gamma=15$ in (30), the parameter
$K=35$ of the MN scheme in [2], the parameters $m=7$ and $a=5$ of the scheme
in [12], the parameters $q=2$, $m=4$, $t=2$ and $a=1$ of the scheme in [39],
and the parameters $q=7$ and $m=5$ of the scheme in [16], we have the
transmission loads and the subpacketizations of the schemes in [16, 12, 39]
and Theorem 1 illustrated in Fig. 3 and Fig. 4, respectively. It can be seen
the proposed PDAs have the advantages on subpacketizations or transmission
loads.

Figure 3: The transmission loads of PDAs in [2, 39, 12, 16] and Theorem 1.

Figure 4: The subpacketizatins of PDAs in [2, 39, 12, 16] and Corollary 1.

Now let us consider the PDA in Corollary 2. Based on a $2$-$(m,q,3,1)$ GDD and
OA$(m,q,m)$, the obtained user-delivery array is a $(K,F,Z,S)$ PDA with

$\displaystyle K=\frac{m(m-1)q^{2}}{6},\ \ \ F=3q^{m},\ \ \
Z=3q^{m-3}(q^{3}-(q-1)^{3}),\ \ \ S=(q-1)^{2}q^{m}.$

Due to the special values of the user number and the memory ratio of the
proposed PDA in Corollary 2, the comparison to the schemes in [16, 12, 39] is
provided in Table III.

TABLE III: The schemes in [2, 16, 12, 39] and Theorem 2.  PDAs $\&$ parameters | User number $K$ | Memory ratio $M/N$ | Load $R$ | Subpacketiztion $F$
---|---|---|---|---
Corollary 2: $m=15,q=5$ | 875 | 0.488 | 5.33 | $0.92\times 10^{11}$
[16]: $m=7,q=125,z=61$ | 875 | 0.488 | 64 | $3.8\times 10^{12}$
[2]: $K=875$, $\mu=0.488$ | 875 | 0.488 | 1.05 | $5.3\times 10^{261}$
Corollary 2: $m=16,q=4$ | 640 | 0.578 | 3 | $1.29\times 10^{10}$
[16]: $m=10,q=64,z=37$ | 640 | 0.578 | 13.5 | $3.6\times 10^{16}$
[2]: $K=640$, $\mu=0.578$ | 640 | 0.578 | 0.73 | $5.7\times 10^{187}$
Corollary 2: $m=16,q=5$ | 1000 | 0.488 | 5.33 | $4.56\times 10^{11}$
[16]: $m=10,q=125,z=61$ | 1000 | 0.488 | 64 | $4.8\times 10^{14}$
[2]:$K=1000$, $\mu=0.488$ | 1000 | 0.488 | 1.05 | $2.0\times 10^{299}$
Corollary 2: $m=7,q=20$ | 2800 | 0.143 | 120.33 | $0.38\times 10^{10}$
[39]: $q=7,m=5,t=1,a=4$ | 2801 | 0.143 | 480 | $2.5\times 10^{12}$
Corollary 2: $m=4,q=8$ | 128 | 0.33 | 16.33 | $1.23\times 10^{4}$
[39]: $q=3,m=5,t=1,a=4$ | 121 | 0.33 | 16.2 | $7.64\times 10^{6}$
Corollary 2: $m=1,q=3$ | 165 | 0.704 | 1.333 | 531441
[12]: $m=11,a=3,b=1,\eta=1$ | 165 | 0.727 | 25 | 11
Corollary 2: $m=4,q=12$ | 288 | 0.23 | 40.22 | 62208
[12]: $m=13,a=3,b=1,\eta=0$ | 286 | 0.23 | 55 | 13

In Table III we can see that the proposed PDAs in Corollary 2 has the
advantages both on transmission load and subpacetizations compared with the
PDAs in [16, 39]; has a lower transmission load and higher subpacketization
compared to the PDA in [12].

###  IV-C Sketch of the proposed scheme in Theorem 1

Let us consider an $(L,K,\Gamma,M,N)=(3,7,7,1,7)$ coded caching scheme for the
$t$-$(\Gamma,L,K,\lambda)=2$-$(7,3,7,1)$ design $(\mathcal{X},\mathfrak{B})$
(in Example 2) access topology. More precisely, user $U_{\mathcal{B}_{k}}$
where $k\in[7]$ is connected to the cache-nodes with indices in
$\mathcal{B}_{k}$, where

$\displaystyle\mathcal{B}_{1}=\\{1,2,4\\},\ \mathcal{B}_{2}=\\{2,3,5\\},\
\mathcal{B}_{3}=\\{3,4,6\\},\ \mathcal{B}_{4}=\\{4,5,7\\},$
$\displaystyle\mathcal{B}_{5}=\\{5,6,1\\},\ \mathcal{B}_{6}=\\{6,7,2\\},\
\mathcal{B}_{7}=\\{7,1,3\\}.$

In addition, we have $\mu\Gamma=1$ and ${L\choose t}={3\choose 2}=3$.

Using the MN scheme and the $2$-$(7,3,7,1)$ design, we first divide each file
into $7$ subfiles with equal size, i.e., for each $n\in[7]$,
$W_{n}=(W_{n,\mathcal{D}})_{\mathcal{D}\in{[7]\choose 1}}$, and further divide
each subfile into $3$ packets with equal size, i.e., for each $n\in[N]$ and
$\mathcal{D}\in{[7]\choose 1}$,
$W_{n,\mathcal{D}}=(W^{\mathcal{T}}_{n,\mathcal{D}})_{\mathcal{T}\in{[3]\choose
2}}$. Let us introduce our main idea by constructing three arrays
$\mathbf{C}$, $\mathbf{U}$, and $\mathbf{Q}$ defined in Definition 2.

By Definition 2, we have $F={\Gamma\choose\mu\Gamma}{L\choose t}={7\choose
1}{3\choose 2}=21$ and $K={\Gamma\choose t}/{L\choose t}={7\choose
2}/{3\choose 2}=7$. For convenience, we will represent the row labels of
$\mathbf{C}$, $\mathbf{U}$, and $\mathbf{Q}$ by a pair
$(\mathcal{D},\mathcal{T})$ where
$\mathcal{D}\in{[\Gamma]\choose\mu\Gamma}={[7]\choose 1}$,
$\mathcal{T}\in{[L]\choose 2}={[3]\choose 2}$.

####  IV-C1 Construction of node-placement array $\mathbf{C}$

We divide each file $W_{n}$ where $n\in[7]$ into $21$ packets, where each
packet is denoted by $W^{\mathcal{T}}_{n,\mathcal{D}}$ where
$\mathcal{T}\in{[3]\choose 2}$ and $\mathcal{D}\in{[7]\choose 1}$, and is
cached by cache-node $\gamma$ if $\gamma\in\mathcal{D}$. Then the packets
cached by cache-nodes can be written as (note that in the examples for
simplicity we omit the braces and commas when we indicate the indices of
cache-nodes, users and packets)

$\displaystyle\mathcal{Z}_{C_{1}}$ $\displaystyle=\\{W^{12}_{n,1},\
W^{13}_{n,1},\ W^{23}_{n,1}\ |\ n\in[7]\\},\ \
\mathcal{Z}_{C_{2}}=\\{W^{12}_{n,2},\ W^{13}_{n,2},\ W^{23}_{n,2}\ |\
n\in[7]\\},$ $\displaystyle\mathcal{Z}_{C_{3}}$
$\displaystyle=\\{W^{12}_{n,3},\ W^{13}_{n,3},\ W^{23}_{n,3}\ |\ n\in[7]\\},\
\ \mathcal{Z}_{C_{4}}=\\{W^{12}_{n,4},\ W^{13}_{n,4},\ W^{23}_{n,4}\ |\
n\in[7]\\},$ $\displaystyle\ \mathcal{Z}_{C_{5}}$
$\displaystyle=\\{W^{12}_{n,5},\ W^{13}_{n,5},\ W^{23}_{n,5}\ |\ n\in[7]\\},\
\ \mathcal{Z}_{C_{6}}=\\{W^{12}_{n,6},\ W^{13}_{n,6},\ W^{23}_{n,6}\ |\
n\in[7]\\},$ $\displaystyle\mathcal{Z}_{C_{7}}$
$\displaystyle=\\{W^{12}_{n,7},\ W^{13}_{n,7},\ W^{23}_{n,7\\}}\ |\
n\in[7]\\}.$ (31)

By Definition 2, a $21\times 7$ node-placement array $\mathbf{C}$ which
represents the packets cached by the cache-nodes can be written in Table IV as
follows. Note that since each row of $\mathbf{C}$ represents a packet
$W^{\mathcal{T}}_{n,\mathcal{D}}$ for the files $n\in[N]$, we let the row
index of $\mathbf{C}$ be $(\mathcal{D},\mathcal{T})$, where
$\mathcal{T}\in{[3]\choose 2}$ and $\mathcal{D}\in{[7]\choose 1}$.

TABLE IV: Node-placement array $\mathbf{C}$.  Packet labels | Cache-node set $\mathcal{X}$
---|---
$\mathcal{D},\mathcal{T}$ | $C_{1}$ | $C_{2}$ | $C_{3}$ | $C_{4}$ | $C_{5}$ | $C_{6}$ | $C_{7}$
$\\{1\\},\\{1,2\\}$ | $*$ |  |  |  |  |  |
$\\{2\\},\\{1,2\\}$ |  | $*$ |  |  |  |  |
$\\{3\\},\\{1,2\\}$ |  |  | $*$ |  |  |  |
$\\{4\\},\\{1,2\\}$ |  |  |  | $*$ |  |  |
$\\{5\\},\\{1,2\\}$ |  |  |  |  | $*$ |  |
$\\{6\\},\\{1,2\\}$ |  |  |  |  |  | $*$ |
$\\{7\\},\\{1,2\\}$ |  |  |  |  |  |  | $*$
$\\{1\\},\\{1,3\\}$ | $*$ |  |  |  |  |  |
$\\{2\\},\\{1,3\\}$ |  | $*$ |  |  |  |  |
$\\{3\\},\\{1,3\\}$ |  |  | $*$ |  |  |  |
$\\{4\\},\\{1,3\\}$ |  |  |  | $*$ |  |  |
$\\{5\\},\\{1,3\\}$ |  |  |  |  | $*$ |  |
$\\{6\\},\\{1,3\\}$ |  |  |  |  |  | $*$ |
$\\{7\\},\\{1,3\\}$ |  |  |  |  |  |  | $*$
$\\{1\\},\\{2,3\\}$ | $*$ |  |  |  |  |  |
$\\{2\\},\\{2,3\\}$ |  | $*$ |  |  |  |  |
$\\{3\\},\\{2,3\\}$ |  |  | $*$ |  |  |  |
$\\{4\\},\\{2,3\\}$ |  |  |  | $*$ |  |  |
$\\{5\\},\\{2,3\\}$ |  |  |  |  | $*$ |  |
$\\{6\\},\\{2,3\\}$ |  |  |  |  |  | $*$ |
$\\{7\\},\\{2,3\\}$ |  |  |  |  |  |  | $*$

####  IV-C2 Construction of user-retrieve array $\mathbf{U}$

Recall that the $2$-$(7,3,7,1)$ design $(\mathcal{X},\mathfrak{B})$ in Example
2 has the blocks $\mathfrak{B}=\\{\\{1,2,4\\}$, $\\{2,3,5\\}$, $\\{3,4,6\\}$,
$\\{4,5,6\\}$, $\\{5,6,1\\}$, $\\{6,7,2\\}$, $\\{7,1,3\\}\\}$. Then the users
$U_{\mathcal{B}}$ where $\mathcal{B}\in\mathfrak{B}$ can retrieve the
following packets,

$\displaystyle\mathcal{Z}_{U_{124}}=\\{{\color[rgb]{1,0,0}W^{12}_{n,1},W^{13}_{n,1},W^{23}_{n,1}},{\color[rgb]{0,0,1}W^{12}_{n,2},W^{13}_{n,2},W^{23}_{n,2}},{\color[rgb]{1,0,1}W^{12}_{n,4},W^{13}_{n,4},W^{23}_{n,4}}|n\in[7]\\},$
$\displaystyle\mathcal{Z}_{U_{235}}=\\{{\color[rgb]{1,0,0}W^{12}_{n,2},W^{13}_{n,2}},{\color[rgb]{1,0,0}W^{23}_{n,2}},{\color[rgb]{0,0,1}W^{12}_{n,3},W^{13}_{n,3},W^{23}_{n,3}},{\color[rgb]{1,0,1}W^{12}_{n,5},W^{13}_{n,5},W^{23}_{n,5}}|n\in[7]\\},$
$\displaystyle\mathcal{Z}_{U_{346}}=\\{{\color[rgb]{1,0,0}W^{12}_{n,3},W^{13}_{n,3},W^{23}_{n,3}},{\color[rgb]{0,0,1}W^{12}_{n,4},W^{13}_{n,4}},{\color[rgb]{0,0,1}W^{23}_{n,4}},{\color[rgb]{1,0,1}W^{12}_{n,6},W^{13}_{n,6},W^{23}_{n,6}}|n\in[7]\\}$
$\displaystyle\mathcal{Z}_{U_{457}}=\\{{\color[rgb]{1,0,0}W^{12}_{n,4}},{\color[rgb]{1,0,0}W^{13}_{n,4},W^{23}_{n,4}},{\color[rgb]{0,0,1}W^{12}_{n,5},W^{13}_{n,5},W^{23}_{n,5}},{\color[rgb]{1,0,1}W^{12}_{n,7},W^{13}_{n,7},W^{23}_{n,7}}|n\in[7]\\},$
$\displaystyle\mathcal{Z}_{U_{156}}=\\{{\color[rgb]{1,0,0}W^{12}_{n,5},W^{13}_{n,5},W^{23}_{n,5}},{\color[rgb]{0,0,1}W^{12}_{n,6},W^{13}_{n,6}},{\color[rgb]{0,0,1}W^{23}_{n,6}},{\color[rgb]{1,0,1}W^{12}_{n,1},W^{13}_{n,1},W^{23}_{n,1}}|n\in[7]\\},$
$\displaystyle\mathcal{Z}_{U_{267}}=\\{{\color[rgb]{1,0,0}W^{12}_{n,6}},{\color[rgb]{1,0,0}W^{13}_{n,6},W^{23}_{n,6}},{\color[rgb]{0,0,1}W^{12}_{n,7},W^{13}_{n,7},W^{23}_{n,7}},{\color[rgb]{1,0,1}W^{12}_{n,2},W^{13}_{n,2}},{\color[rgb]{1,0,1}W^{23}_{n,2}}|n\in[7]\\},$
$\displaystyle\mathcal{Z}_{U_{137}}=\\{{\color[rgb]{1,0,0}W^{12}_{n,7},W^{13}_{n,7},W^{23}_{n,7}},{\color[rgb]{0,0,1}W^{12}_{n,1}},{\color[rgb]{0,0,1}W^{13}_{n,1},W^{23}_{n,1}},{\color[rgb]{1,0,1}W^{12}_{n,3},W^{13}_{n,3},W^{23}_{n,3}}|n\in[7]\\}.$
(32)

By Definition 2, a $21\times 7$ node-placement array $\mathbf{C}$ representing
the packets retrieved by the users can be written in Table V as follows.

TABLE V: User-retrieve array $\mathbf{U}$.  Subpacket labels | User set $\mathfrak{B}$
---|---
$(\mathcal{D},\mathcal{T})$ | $U_{124}$ | $U_{235}$ | $U_{346}$ | $U_{457}$ | $U_{156}$ | $U_{267}$ | $U_{137}$
$(\\{1\\},\\{1,2\\})$ | * |  |  |  | * |  | *
$(\\{2\\},\\{1,2\\})$ | * | * |  |  |  | * |
$(\\{3\\},\\{1,2\\})$ |  | * | * |  |  |  | *
$(\\{4\\},\\{1,2\\})$ | * |  | * | * |  |  |
$(\\{5\\},\\{1,2\\})$ |  | * |  | * | * |  |
$(\\{6\\},\\{1,2\\})$ |  |  | * |  | * | * |
$(\\{7\\},\\{1,2\\})$ |  |  |  | * |  | * | *
$(\\{1\\},\\{1,3\\})$ | * |  |  |  | * |  | *
$(\\{2\\},\\{1,3\\})$ | * | * |  |  |  | * |
$(\\{3\\},\\{1,3\\})$ |  | * | * |  |  |  | *
$(\\{4\\},\\{1,3\\})$ | * |  | * | * |  |  |
$(\\{5\\},\\{1,3\\})$ |  | * |  | * | * |  |
$(\\{6\\},\\{1,3\\})$ |  |  | * |  | * | * |
$(\\{7\\},\\{1,3\\})$ |  |  |  | * |  | * | *
$(\\{1\\},\\{2,3\\})$ | * |  |  |  | * |  | *
$(\\{2\\},\\{2,3\\})$ | * | * |  |  |  | * |
$(\\{3\\},\\{2,3\\})$ |  | * | * |  |  |  | *
$(\\{4\\},\\{2,3\\})$ | * |  | * | * |  |  |
$(\\{5\\},\\{2,3\\})$ |  | * |  | * | * |  |
$(\\{6\\},\\{2,3\\})$ |  |  | * |  | * | * |
$(\\{7\\},\\{2,3\\})$ |  |  |  | * |  | * | *

####  IV-C3 Construction of user-delivery array $\mathbf{Q}$

For the sake of clarity, in the user-delivery array each non-null entry is
filled by a set, instead of an integer. As shown in Table V, each entry
$\mathbf{U}((\mathcal{D},\mathcal{T}),\mathcal{B})$ is null if and only if
$\mathcal{D}\bigcap\mathcal{B}=\emptyset$ where $\mathcal{D}\in{[7]\choose 1}$
and $\mathcal{B}\in\mathfrak{B}$. Then we put the subset
$\mathcal{D}\cup\mathcal{B}(\mathcal{T})$ into the entry
$\mathbf{U}((\mathcal{D},\mathcal{T}),\mathcal{B})$ to the user-delivery array
$\mathbf{Q}$. For example, we can see that the entries
$\mathbf{U}((\\{3\\},\\{1,2\\}),\\{1,2,4\\})$,
$\mathbf{U}((\\{1\\},\\{1,2\\}),\\{2,3,5\\})$ and
$\mathbf{U}((\\{2\\},\\{1,2\\}),\\{1,3,7\\})$ are null in Table V. Then we put
the subset

$\displaystyle\\{1,2,3\\}=$
$\displaystyle\\{3\\}\cup\\{1,2,4\\}(\\{1,2\\})=\\{3\\}\cup\\{1,2\\}$
$\displaystyle=$
$\displaystyle\\{1\\}\cup\\{2,3,5\\}(\\{1,2\\})=\\{1\\}\cup\\{2,3\\}$
$\displaystyle=$
$\displaystyle\\{2\\}\cup\\{1,3,7\\}(\\{1,2\\})=\\{2\\}\cup\\{1,3\\}$

into the entries $\mathbf{U}((\\{3\\},\\{1,2\\}),\\{1,2,4\\})$,
$\mathbf{U}((\\{1\\},\\{1,2\\}),\\{2,3,5\\})$ and
$\mathbf{U}((\\{2\\},\\{1,2\\}),\\{1,3,7\\})$. We can check that the entries

$\displaystyle\mathbf{U}((\\{3\\},\\{1,2\\}),\\{2,3,5\\})=\mathbf{U}((\\{3\\},\\{1,2\\}),\\{1,3,7\\})$
$\displaystyle=$
$\displaystyle\mathbf{U}((\\{1\\},\\{1,2\\}),\\{1,2,4\\})=\mathbf{U}((\\{1\\},\\{1,2\\}),\\{1,3,7\\})$
$\displaystyle=$
$\displaystyle\mathbf{U}((\\{2\\},\\{1,2\\}),\\{1,2,4\\})=\mathbf{U}((\\{2\\},\\{1,2\\}),\\{2,3,5\\})=*.$

That is, the condition C3 of Definition 1 holds. Similarly in this example we
can obtain the $21\times 7$ user-delivery array $\mathbf{Q}$ listed in Table
VI. We can check that there are exactly $S={\Gamma\choose
t+\mu\Gamma}-K{L\choose t+\mu\Gamma}={7\choose 2+1}-7\times{3\choose
2+1}=35-7=28$, and the obtained $\mathbf{Q}$ is a $(7,21,9,28)$ PDA which
leads to a $(7,M^{\prime},N)$ coded caching scheme for a shared-link network
with $M^{\prime}/N=3/7$, subpacketization $21$ and transmission load
$28/21=4/3$ by Lemma 1. The total coded caching gain is $K(F-Z)/S=7\times
4\times 3/28=3$.

TABLE VI: User-delivery array $\mathbf{Q}$.  Subpacket labels | User set $\mathfrak{B}$
---|---
$\mathcal{D},\mathcal{T}$ | $U_{124}$ | $U_{235}$ | $U_{346}$ | $U_{457}$ | $U_{156}$ | $U_{267}$ | $U_{137}$
$\\{1\\},\\{1,2\\}$ | * | $123$ | $134$ | $145$ | * | $126$ | *
$\\{2\\},\\{1,2\\}$ | * | * | $234$ | $245$ | $125$ | * | $123$
$\\{3\\},\\{1,2\\}$ | $123$ | * | * | $345$ | $135$ | $236$ | *
$\\{4\\},\\{1,2\\}$ | * | $234$ | * | * | $145$ | $246$ | $134$
$\\{5\\},\\{1,2\\}$ | $125$ | * | $345$ | * | * | $256$ | $135$
$\\{6\\},\\{1,2\\}$ | $126$ | $236$ | * | $456$ | * | * | $136$
$\\{7\\},\\{1,2\\}$ | $127$ | $237$ | $347$ | * | $157$ | * | *
$\\{1\\},\\{1,3\\}$ | * | $125$ | $136$ | $147$ | * | $127$ | *
$\\{2\\},\\{1,3\\}$ | * | * | $236$ | $247$ | $126$ | * | $127$
$\\{3\\},\\{1,3\\}$ | $134$ | * | * | $347$ | $136$ | $237$ | *
$\\{4\\},\\{1,3\\}$ | * | $245$ | * | * | $146$ | $247$ | $147$
$\\{5\\},\\{1,3\\}$ | $145$ | * | $356$ | * | * | $257$ | $157$
$\\{6\\},\\{1,3\\}$ | $146$ | $256$ | * | $467$ | * | * | $167$
$\\{7\\},\\{1,3\\}$ | $147$ | $257$ | $367$ | * | $167$ | * | *
$\\{1\\},\\{2,3\\}$ | * | $135$ | $146$ | $157$ | * | $167$ | *
$\\{2\\},\\{2,3\\}$ | * | * | $246$ | $257$ | $256$ | * | $237$
$\\{3\\},\\{2,3\\}$ | $234$ | * | * | $357$ | $356$ | $367$ | *
$\\{4\\},\\{2,3\\}$ | * | $345$ | * | * | $456$ | $467$ | $347$
$\\{5\\},\\{2,3\\}$ | $245$ | * | $456$ | * | * | $567$ | $357$
$\\{6\\},\\{2,3\\}$ | $246$ | $356$ | * | $567$ | * | * | $367$
$\\{7\\},\\{2,3\\}$ | $247$ | $357$ | $467$ | * | $567$ | * | *

###  IV-D Sketch of the proposed scheme in Theorem 2

Now we let the access topology be the $t$-$(m,q,L,\lambda)=2$-$(3,2,2,1)$ GDD
$(\mathcal{X},\mathfrak{G},\mathfrak{B})$ where

$\displaystyle\mathcal{X}$
$\displaystyle=\\{(1,1),(1,2),(2,1),(2,2),(3,1),(3,2)\\},$ (33a)
$\displaystyle\mathfrak{G}$
$\displaystyle=\\{\mathcal{G}_{1}=\\{(1,1),(1,2)\\},\ \
\mathcal{G}_{2}=\\{(2,1),(2,2)\\},\ \ \mathcal{G}_{3}=\\{(3,1),(3,2)\\}\\},$
(33b) $\displaystyle\mathfrak{B}$ $\displaystyle=\\{\
\mathcal{B}_{1}=\\{(1,1),(2,1)\\},\ \ \mathcal{B}_{2}=\\{(1,1),(2,2)\\},\ \
\mathcal{B}_{3}=\\{(1,1),(3,1)\\},$ $\displaystyle\ \ \ \ \
\mathcal{B}_{4}=\\{(1,1),(3,2)\\},\ \ \mathcal{B}_{5}=\\{(1,2),(2,1)\\},\ \
\mathcal{B}_{6}=\\{(1,2),(2,2)\\},$ $\displaystyle\ \ \ \ \
\mathcal{B}_{7}=\\{(1,2),(3,1)\\},\ \ \mathcal{B}_{8}=\\{(1,2),(3,2)\\},\ \
\mathcal{B}_{9}=\\{(2,1),(3,1)\\},$ $\displaystyle\ \ \ \ \
\mathcal{B}_{10}=\\{(2,1),(3,2)\\},\ \mathcal{B}_{11}=\\{(2,2),(3,1)\\},\
\mathcal{B}_{12}=\\{(2,2),(3,2)\\}\ \\}.$ (33c)

The topology represented by the above $t$-GDD, contains $6$ cache-nodes and
$12$ users. Each cache-node is represented by a vector in $\mathcal{X}$. Each
user $U_{\mathcal{B}_{k}}$ where $k\in[12]$ is connected to the cache-nodes
with indices in $\mathcal{B}_{k}$ as shown in (33c). In the following, for the
$2$-$(3,2,2,1)$ GDD $(\mathcal{X},\mathfrak{G},\mathfrak{B})$ access topology,
we will design a $(L,K,\Gamma,M,N)=(2,12,6,3,6)$ coded caching scheme whose
cache placement is based on the OA$(m=3,q=2,s=2)$, denoted by
$\mathbf{A}=(\mathbf{A}(j,u))_{j\in[4],u\in[3]}$ (shown in (24) of Example 5).

We will also introduce our main idea by constructing three arrays
$\mathbf{C}$, $\mathbf{U}$, and $\mathbf{Q}$ as follows.

####  IV-D1 Construction of node-placement array $\mathbf{C}$

We divide each file into $\binom{L}{t}q^{s}=4$ subfiles with equal size, i.e.,
for each $n\in[6]$, $W_{n}=\left(W_{n,j}:\mathcal{T}\in{[L]\choose
t},j\in[q^{s}]\right)=\left(W_{n,j}:\mathcal{T}\in{[2]\choose
2},j\in[4]\right)$. Each cache-node $C_{u,v}$ where $u\in[3]$ and $v\in[2]$
caches the packet $W^{[2]}_{n,j}$ if $\mathbf{A}(j,u)=v$ for each $j\in[4]$.
So the packets cached by the cache-nodes can be written as follows.

$\displaystyle\mathcal{Z}_{C_{1,1}}=\left\\{W^{[2]}_{n,1},W^{[2]}_{n,3}\ |\
n\in[6]\right\\},\ \ \
\mathcal{Z}_{C_{1,2}}=\left\\{W^{[2]}_{n,2},W^{[2]}_{n,4}\ |\
n\in[6]\right\\},$
$\displaystyle\mathcal{Z}_{C_{2,1}}=\left\\{W^{[2]}_{n,1},W^{[2]}_{n,2}\ |\
n\in[6]\right\\},\ \ \
\mathcal{Z}_{C_{2,2}}=\left\\{W^{[2]}_{n,3},W^{[2]}_{n,4}\ |\
n\in[6]\right\\},$
$\displaystyle\mathcal{Z}_{C_{3,1}}=\left\\{W^{[2]}_{n,1},W^{[2]}_{n,4}\ |\
n\in[6]\right\\},\ \ \
\mathcal{Z}_{C_{3,2}}=\left\\{W^{[2]}_{n,2},W^{[2]}_{n,3}\ |\
n\in[6]\right\\}.$ (34)

We can see that each cache-node caches $2\times 6=12$ packets. By Definition
2, the $4\times 6$ node-placement array $\mathbf{C}$ representing the packets
cached by the cache-nodes can be written in Table VII. Note that the row index
of $\mathbf{C}$ is $(j,[2])$ where $j\in[4]$.

TABLE VII: Node-placement array $\mathbf{C}$.  Array | Packet labels | cache-nodes
---|---|---
$\mathbf{A}$ | $(j\in[4],\mathcal{T}=[2])$ | $C_{1,1}$ | $C_{1,2}$ | $C_{2,1}$ | $C_{2,2}$ | $C_{3,1}$ | $C_{3,2}$
111 | $(1,[2])$ | * |  | * |  | * |
212 | $(2,[2])$ |  | * | * |  |  | *
122 | $(3,[2])$ | * |  |  | * |  | *
221 | $(4,[2])$ |  | * |  | * | * |

####  IV-D2 Construction of user-retrieve array $\mathbf{U}$

Using the $2$-$(3,2,3,1)$ GDD $(\mathcal{X},\mathfrak{G},\mathfrak{B})$ in
Example 4, the users can retrieve the following packets.

$\displaystyle\begin{split}\mathcal{Z}_{U_{(1,1),(2,1)}}&=\mathcal{Z}_{C_{1,1}}\bigcup\mathcal{Z}_{C_{2,1}}=\\{W^{[2]}_{n,1},W^{[2]}_{n,2},W^{[2]}_{n,3}\
\Big{|}\ n\in[6]\\},&\\\
\mathcal{Z}_{U_{(1,2),(2,1)}}&=\mathcal{Z}_{C_{1,2}}\bigcup\mathcal{Z}_{C_{2,1}}=\\{W^{[2]}_{n,1},W^{[2]}_{n,2},W^{[2]}_{n,4}\
\Big{|}\ n\in[6]\\},&\\\
\mathcal{Z}_{U_{(1,1),(2,2)}}&=\mathcal{Z}_{C_{1,1}}\bigcup\mathcal{Z}_{C_{2,2}}=\\{W^{[2]}_{n,1},W^{[2]}_{n,3},W^{[2]}_{n,4}\
\Big{|}\ n\in[6]\\},&\\\
\mathcal{Z}_{U_{(1,2),(2,2)}}&=\mathcal{Z}_{C_{1,2}}\bigcup\mathcal{Z}_{C_{2,2}}=\\{W^{[2]}_{n,2},W^{[2]}_{n,3},W^{[2]}_{n,4}\
\Big{|}\ n\in[6]\\},&\\\
\mathcal{Z}_{U_{(1,1),(3,1)}}&=\mathcal{Z}_{C_{1,1}}\bigcup\mathcal{Z}_{C_{3,1}}=\\{W^{[2]}_{n,1},W^{[2]}_{n,3},W^{[2]}_{n,4}\
\Big{|}\ n\in[6]\\},&\\\
\mathcal{Z}_{U_{(1,2),(3,1)}}&=\mathcal{Z}_{C_{1,2}}\bigcup\mathcal{Z}_{C_{3,1}}=\\{W^{[2]}_{n,1},W^{[2]}_{n,2},W^{[2]}_{n,4}\
\Big{|}\ n\in[6]\\},&\\\
\mathcal{Z}_{U_{(1,1),(3,2)}}&=\mathcal{Z}_{C_{1,1}}\bigcup\mathcal{Z}_{C_{3,2}}=\\{W^{[2]}_{n,1},W^{[2]}_{n,2},W^{[2]}_{n,3}\
\Big{|}\ n\in[6]\\},&\\\
\mathcal{Z}_{U_{(1,2),(3,2)}}&=\mathcal{Z}_{C_{1,2}}\bigcup\mathcal{Z}_{C_{3,2}}=\\{W^{[2]}_{n,2},W^{[2]}_{n,3},W^{[2]}_{n,4}\
\Big{|}\ n\in[6]\\},&\\\
\mathcal{Z}_{U_{(2,1),(3,1)}}&=\mathcal{Z}_{C_{2,1}}\bigcup\mathcal{Z}_{C_{3,1}}=\\{W^{[2]}_{n,1},W^{[2]}_{n,2},W^{[2]}_{n,4}\
\Big{|}\ n\in[6]\\},&\\\
\mathcal{Z}_{U_{(2,2),(3,1)}}&=\mathcal{Z}_{C_{2,2}}\bigcup\mathcal{Z}_{C_{3,1}}=\\{W^{[2]}_{n,1},W^{[2]}_{n,3},W^{[2]}_{n,4}\
\Big{|}\ n\in[6]\\},&\\\
\mathcal{Z}_{U_{(2,1),(3,2)}}&=\mathcal{Z}_{C_{2,1}}\bigcup\mathcal{Z}_{C_{3,2}}=\\{W^{[2]}_{n,1},W^{[2]}_{n,2},W^{[2]}_{n,3}\
\Big{|}\ n\in[6]\\},&\\\
\mathcal{Z}_{U_{(2,2),(3,2)}}&=\mathcal{Z}_{C_{2,2}}\bigcup\mathcal{Z}_{C_{3,2}}=\\{W^{[2]}_{n,2},W^{[2]}_{n,3},W^{[2]}_{n,4}\
\Big{|}\ n\in[6]\\}.&\end{split}$ (35)

By Definition 2 we have a $4\times 12$ user-retrieve array $\mathbf{U}$ to
represent the packets retrieved by the users in Table VIII as follows.

TABLE VIII: User-retrieve array $\mathbf{U}$. We omit the braces and commas in the vectors; e.g., $111$ represents $(1,1,1)$, $U_{11,21}$ represents $U_{(1,1),(2,1)}$.  Array | Packet labels | User set $U_{\mathcal{B}}$, $\mathcal{B}\in\mathfrak{B}$
---|---|---
$\mathbf{A}$ | $j\in[4],\mathcal{T}=[2]$ | $U_{11,21}$ | $U_{11,22}$ | $U_{11,31}$ | $U_{11,32}$ | $U_{12,21}$ | $U_{12,22}$ | $U_{12,31}$ | $U_{12,32}$ | $U_{21,31}$ | $U_{21,32}$ | $U_{22,31}$ | $U_{22,32}$
111 | $1,[2]$ | * | * | * | * | * |  | * |  | * | * | * |
212 | $2,[2]$ | * |  |  | * | * | * | * | * | * | * |  | *
122 | $3,[2]$ | * | * | * | * |  | * |  | * |  | * | * | *
221 | $4,[2]$ |  | * | * |  | * | * | * | * | * |  | * | *

####  IV-D3 Construction of user-delivery array $\mathbf{Q}$

Using the OA$(m=3,q=2,s=2)$ $\mathbf{A}=(\mathbf{A}(j,u))_{j\in[4],u\in[3]}$
in (24) of Example 5 and the GDD $(\mathcal{X},\mathfrak{G},\mathfrak{B})$ in
(33), we can put the null entries of $\mathbf{U}$ in the following way to
obtain the use-delivery array $\mathbf{Q}$, i.e., Table IX. For the sake of
clarity, each block $\mathcal{B}_{k},k\in[12]$ in (33) can be represented by
$\\{(u_{k,1},v_{k,1}),(u_{k,2},v_{k,2})\\}$ where $u_{k,1}$, $u_{k,2}\in[3]$
and $v_{k,1}$, $v_{k,2}\in[2]$, and each non-null entry of $\mathbf{U}$ is
filled by a vector, instead of an integer. As shown in Table VIII, for any
integer $j\in[4]$ and integer $k\in[12]$, the entry
$\mathbf{U}((j,[2]),\mathcal{B}_{k}\\})$ is null if and only if
$\text{d}(\mathbf{A}(j,\\{u_{k,1},u_{k,2}\\}),(v_{k,1},v_{k,2}))=2$. Then we
put the vector ${\bf e}=(e_{1},e_{2},e_{3})$ where

$\displaystyle{\bf e}(\\{u_{k,1},u_{k,2}\\})=(v_{k,1},v_{k,2})\ \ \text{and}\
\ {\bf
e}([3]\setminus\\{u_{k,1},u_{k,2}\\})=\mathbf{A}(j,[3]\setminus\\{u_{k,1},u_{k,2}\\})$

into the entry $\mathbf{U}((j,[2]),\mathcal{B}_{k})$. For example, let us see
the columns of the user-retrieve array $\mathbf{U}$ in Table VIII which are
labeled by the blocks

$\displaystyle\mathcal{B}_{2}$
$\displaystyle=\\{(u_{2,1},v_{2,1})=(1,1),(u_{2,2},v_{2,2})=(2,2)\\}$
$\displaystyle\mathcal{B}_{4}$
$\displaystyle=\\{(u_{4,1},v_{4,1})=(1,1),(u_{4,2},v_{4,2})=(3,2)\\}$
$\displaystyle\mathcal{B}_{12}$
$\displaystyle=\\{(u_{12,1},v_{12,1})=(2,2),(u_{12,2},v_{12,2})=(3,2)\\}$

respectively. We can see that the entries

$\displaystyle\mathbf{U}((2,[2]),\mathcal{B}_{2}),\ \
\mathbf{U}((4,[2]),\mathcal{B}_{4}),\ \ \mathbf{U}((1,[2]),\mathcal{B}_{12})$

are null in Table VIII. Then we put the vector $(1,2,2)$ into these three
entries since

$\displaystyle\left\\{\begin{array}[]{c}(1,2,2)(\\{u_{2,1},u_{2,2}\\})=(1,2,2)(\\{1,2\\})=(1,2)=(v_{2,1},v_{2,2}),\\\
(1,2,2)([3]\\{1,2\\})=(1,2,2)(3)=2=\mathbf{A}(2,3);\end{array}\right.$
$\displaystyle\left\\{\begin{array}[]{c}(1,2,2)(\\{u_{4,1},u_{4,2}\\})=(1,2,2)(\\{1,3\\})=(1,2)=(v_{4,1},v_{4,2}),\\\
(1,2,2)([3]\\{1,3\\})=(1,2,2)(2)=2=\mathbf{A}(4,2);\end{array}\right.$
$\displaystyle\left\\{\begin{array}[]{c}(1,2,2)(\\{u_{12,1},u_{12,2}\\})=(1,2,2)(\\{2,3\\})=(2,2)=(v_{2,1},v_{2,2}),\\\
(1,2,2)([3]\\{2,3\\})=(1,2,2)(1)=1=\mathbf{A}(1,1).\end{array}\right.$

One can check that then entries

$\displaystyle\mathbf{U}((2,[2]),\mathcal{B}_{8})=\mathbf{U}((2,[2]),\mathcal{B}_{12})=\mathbf{U}((4,[2]),\mathcal{B}_{2})=\mathbf{U}((4,[2]),\mathcal{B}_{12})$
$\displaystyle=$
$\displaystyle\mathbf{U}((1,[2]),\mathcal{B}_{2})=\mathbf{U}((1,[2]),\mathcal{B}_{4})=*.$

That is, the condition C3 of Definition 1 holds. We can check that
$\mathbf{Q}$ is a $(12,4,3,4)$ PDA.

TABLE IX: User-delivery array $\mathbf{U}$. We omit the braces and commas in the vectors; e.g., $111$ represents $(1,1,1)$, $U_{11,21}$ represents $U_{(1,1),(2,1)}$.  Array | Packet labels | User set $U_{\mathcal{B}}$, $\mathcal{B}\in\mathfrak{B}$
---|---|---
$\mathbf{A}$ | $(j\in[4],\mathcal{T}=[2])$ | $U_{11,21}$ | $U_{11,22}$ | $U_{11,31}$ | $U_{11,32}$ | $U_{12,21}$ | $U_{12,22}$ | $U_{12,31}$ | $U_{12,32}$ | $U_{21,31}$ | $U_{21,32}$ | $U_{22,31}$ | $U_{22,32}$
111 | $(1,[2])$ | * | * | * | * | * | 221 | * | 212 | * | * | * | 122
212 | $(2,[2])$ | * | 122 | 111 | * | * | * | * | * | * | * | 221 | *
122 | $(3,[2])$ | * | * | * | * | 212 | * | 221 | * | 111 | * | * | *
221 | $(4,[2])$ | 111 | * | * | 122 | * | * | * | * | * | 212 | * | *

##  V Multiaccess coded caching scheme for the $t$-design access topology:
Proof of Theorem 1

In this section, we describe the $(L,K,\Gamma,M,N)$ coded caching scheme for
the $t$-$(\Gamma,L,K,1)$ design $(\mathcal{X},\mathfrak{B})$ access topology
for Theorem 1. By Definition of $t$-design, we have $K={\Gamma\choose
t}/{L\choose t}$. We will propose a coded caching scheme with a placement
phase that depends only on $(\Gamma,M,N)$ MN scheme and is agnostic to the
access topology.555 This is also practical in real systems because placement
is always done at peak times when we only know the number of cache-nodes
(which are fixed edges in the network) and do not know the network access
topology exactly.  Our delivery phase is designed with the knowledge of the
access topology. In addition, it is a unified delivery phase for all
topologies of $t$-design, given a $t$. It can also be seen that the load
decreases as $t$ increases. This corresponds to the fact that, $t_{1}$-design
contains $t_{2}$-design if $t_{1}<t_{2}$, and that the topologies in
$t_{2}$-design have denser connectivity than the topologies in $t_{1}$-design
which are not $t_{2}$-design.

In the following, we describe our scheme by constructing sequentially node-
placement, user-retrieve, and user-delivery arrays.

###  V-A Node-placement array

The server places the files on $\Gamma$ cache-nodes using the placement
strategy of the MN scheme. That is, the server divides each file into
${\Gamma\choose\mu\Gamma}$ subfiles of equal size, i.e., for each $n\in[N]$,
$W_{n}=(W_{n,\mathcal{D}})_{\mathcal{D}\in{[\Gamma]\choose\mu\Gamma}}$. Each
cache-node $C_{\gamma}$ where $\gamma\in[\Gamma]$ caches the subfiles

$\displaystyle\mathcal{Z}_{C_{\gamma}}=\left\\{W_{n,\mathcal{D}}\ \Big{|}\
\gamma\in\mathcal{D},\mathcal{D}\in{[\Gamma]\choose\mu\Gamma},n\in[N]\right\\}.$
(36)

So cache-node $C_{\gamma}$ totally caches $N{\Gamma-1\choose\mu\Gamma-1}$
subfiles, i.e.,
$\frac{N{\Gamma-1\choose\mu\Gamma-1}}{{\Gamma\choose\mu\Gamma}}=\frac{NM}{N}=M$
files. Based on the $t$-$(\Gamma,L,K,1)$ design $(\mathcal{X},\mathfrak{B})$,
we further divide each subfile into ${L\choose t}$ packets, i.e.,
$W_{n,\mathcal{D}}=(W^{\mathcal{T}}_{n,\mathcal{D}})_{\mathcal{T}\in{[L]\choose
t}}$ for each $n\in[N]$ and $\mathcal{D}\in{[\Gamma]\choose\mu\Gamma}$. Then
the content cached by cache-node $C_{\gamma}$ in (36) can be written as

$\displaystyle\mathcal{Z}_{C_{\gamma}}=\left\\{W^{\mathcal{T}}_{n,\mathcal{D}}\
\Big{|}\
\gamma\in\mathcal{D},\mathcal{D}\in{[\Gamma]\choose\mu\Gamma},\mathcal{T}\in{[L]\choose
t},n\in[N]\right\\}.$ (37)

From (37) and by Definition 2 we can define a
${\Gamma\choose\mu\Gamma}{L\choose t}\times\Gamma$ node-placement array
$\mathbf{C}=\left(\mathbf{C}((\mathcal{D},\mathcal{T}),\gamma)\right)_{\mathcal{D}\in{[\Gamma]\choose\mu\Gamma},\mathcal{T}\in{[L]\choose
t},\gamma\in[\Gamma]}$ to represent the subpackets cached by the cache-nodes
where

$\displaystyle\mathbf{C}((\mathcal{D},\mathcal{T}),\gamma)=\left\\{\begin{array}[]{ll}*&\
\ \ \hbox{if}\ \ \gamma\in\mathcal{D}\\\ \text{null}&\ \ \
\hbox{otherwise}\end{array}\ .\right.$ (40)

Note that the row index of $\mathbf{C}$ is $(\mathcal{D},\mathcal{T})$
corresponding to each packet; the column index is $\gamma$ corresponding to
each cache-node. From (36) and (40), it can be seen that there are $\mu\Gamma$
stars in each row of $\mathbf{C}$, which means that each packet is stored by
$\mu\Gamma$ cache-nodes.

Let us return to the example in Section IV-C. In the
$(L,r,K,\Gamma,M,N)=(3,3,7,7,1,7)$ coded caching scheme for the
$t$-$(\Gamma,L,K,\lambda)=2$-$(7,3,7,1)$ design $(\mathcal{X},\mathfrak{B})$
access topology, by (37) and (40) the packets cached by cache-nodes are in
(31) and the node-placement array is listed in Table IV, respectively.

###  V-B User-retrieve array

Given a $t$-$(\Gamma,L,K,1)$ design $(\mathcal{X},\mathfrak{B})$ access
topology, let $U_{\mathcal{B}}$ denote the user who can access the cache-node
$C_{\gamma}$ where $\gamma\in\mathcal{B}$. Then from (37) user
$U_{\mathcal{B}}$ where $\mathcal{B}\in\mathfrak{B}$ can retrieve the
following packets,

$\displaystyle\mathcal{Z}_{U_{\mathcal{B}}}=\bigcup\limits_{\gamma\in\mathcal{B}}\mathcal{Z}_{C_{\gamma}}=\left\\{W^{\mathcal{T}}_{n,\mathcal{D}}\
\Big{|}\
\mathcal{B}\cap\mathcal{D}\neq\emptyset,\mathcal{D}\in{[\Gamma]\choose\mu\Gamma},\mathcal{T}\in{[L]\choose
t},n\in[N]\right\\}.$ (41)

From (41) and by Definition 2 we can define a
${\Gamma\choose\mu\Gamma}{L\choose t}\times K$ user-retrieve array

$\mathbf{U}=\left(\mathbf{U}((\mathcal{D},\mathcal{T}),\mathcal{B})\right)_{\mathcal{D}\in{[\Gamma]\choose\mu\Gamma},\mathcal{T}\in{[L]\choose
t},\mathcal{B}\in\mathfrak{B}}$

to represent the packets retrieved by the users where each entry
$\mathbf{U}((\mathcal{D},\mathcal{T}),\mathcal{B})$ can be defined as follows,

$\displaystyle\mathbf{U}((\mathcal{D},\mathcal{T}),\mathcal{B})=\left\\{\begin{array}[]{ll}*&\
\ \ \hbox{if}\ \ \mathcal{B}\cap\mathcal{D}\neq\emptyset\\\ \text{null}&\ \ \
\hbox{otherwise}\end{array}\ .\right.$ (44)

Each column of $\mathbf{U}$ (representing one user) has exactly
${\Gamma-L\choose\mu\Gamma}\times{L\choose t}$ non-star entries. So there are

$Z=\left({\Gamma\choose\mu\Gamma}-{\Gamma-L\choose\mu\Gamma}\right){L\choose
t}$

stars in each column. Since each user can retrieve $Z$ packets of each file,
the local caching gain is
$\frac{F-Z}{F}={\Gamma-L\choose\mu\Gamma}/{\Gamma\choose\mu\Gamma}$ which
increases with the access degree $L$.

Let us return to the example in Section IV-C. In the
$(L,K,\Gamma,M,N)=(3,7,7,1,7)$ coded caching scheme for the
$t$-$(\Gamma,L,K,\lambda)=2$-$(7,3,7,1)$ design $(\mathcal{X},\mathfrak{B})$
access topology, by (41) and (44), the packets retrieved by users are in (32)
and the user-retrieve array is listed in Table V, respectively.

###  V-C User-delivery array

Based on $\mathbf{U}$, the ${\Gamma\choose\mu\Gamma}{L\choose t}\times K$
user-delivery array
$\mathbf{Q}=\left(\mathbf{Q}((\mathcal{D},\mathcal{T}),\mathcal{B})\right)_{\mathcal{D}\in{[\Gamma]\choose\mu\Gamma},\mathcal{T}\in{[L]\choose
t},\mathcal{B}\in\mathfrak{B}}$ to represent the transmitted packets to the
users can be defined as follows,

$\displaystyle\mathbf{Q}((\mathcal{D},\mathcal{T}),\mathcal{B})=\left\\{\begin{array}[]{ll}\mathcal{D}\cup\mathcal{B}(\mathcal{T})&\
\ \ \hbox{if}\ \ \mathcal{D}\cap\mathcal{B}=\emptyset\\\ &\ \ \
\hbox{otherwise}\end{array},\right.$ (47)

where $\mathcal{B}(\mathcal{T})$ represents the elements in $\mathcal{B}$ with
index in $\mathcal{T}$.666Let us return to the example in Section IV-C again.
In the $(L,K,\Gamma,M,N)=(3,7,7,1,7)$ coded caching scheme for the
$t$-$(\Gamma,L,K,\lambda)=2$-$(7,3,7,1)$ design $(\mathcal{X},\mathfrak{B})$
access topology, by (47), the user-delivery array is listed in Table VI.

It can be seen that the resulting array $\mathbf{Q}$ only contains the
$(\mu\Gamma+t)$-subsets of $[\Gamma]$ which indicate the broadcasted messages.
Let us count the number of these different subsets occurring in $\mathbf{Q}$.
For any $(t+\mu\Gamma)$-subset of $\mathcal{X}$, denoted by $\mathcal{S}$,
where $\mathcal{S}$ is a subset of some block $\mathcal{B}$ in $\mathfrak{B}$,
one can see that $\mathcal{S}$ cannot be an entry in the array $\mathbf{Q}$.
Otherwise, suppose there is an entry
$\mathcal{D}\cup\mathcal{B}^{\prime}(\mathcal{T}^{\prime})=\mathcal{S}$ in the
array $\mathbf{Q}$. Then we have
$\mathcal{B}^{\prime}(\mathcal{T}^{\prime})\subseteq\mathcal{B}^{\prime}\cap\mathcal{B}$.
Recall that from the property of $t$-design with $\lambda=1$,
$\mathcal{B}=\mathcal{B}^{\prime}$ always holds. So we have
$\mathcal{D}\subseteq\mathcal{S}\subseteq\mathcal{B}$ which implies that this
entry is a star from (47); by contradiction, we can prove that $\mathcal{S}$
cannot be an entry in the array $\mathbf{Q}$.

As a result, there are at most ${\Gamma\choose t+\mu\Gamma}-K{L\choose
t+\mu\Gamma}$ different $(t+\mu\Gamma)$-subset of $\mathcal{X}$ occurring in
$\mathbf{Q}$. Thus the number of multicast messages is at most ${\Gamma\choose
t+\mu\Gamma}-K{L\choose t+\mu\Gamma}$.

Let us then show that $\mathbf{Q}$ satisfies Condition C$3$ of Definition 1.

Consider Condition C3-a) first. Assume that there exists a set occurring in
the same row, denoted by
$\mathcal{S}=\mathbf{Q}((\mathcal{D},\mathcal{T}),\mathcal{B}_{1})=\mathbf{Q}((\mathcal{D},\mathcal{T}),\mathcal{B}_{2})$,
where $\mathcal{D}\in{[\Gamma]\choose\mu\Gamma}$, $\mathcal{T}\in{[L]\choose
t}$, $\mathcal{B}_{1}$, $\mathcal{B}_{2}\in\mathfrak{B}$ and
$\mathcal{B}_{1}\neq\mathcal{B}_{2}$. From (47), we have

$\displaystyle\mathcal{D}\cap\mathcal{B}_{1}=\mathcal{D}\cap\mathcal{B}_{2}=\emptyset,\
\
\mathcal{D}\cup\mathcal{B}_{1}(\mathcal{T})=\mathcal{D}\cup\mathcal{B}_{1}(\mathcal{T}).$

This implies that $\mathcal{B}_{1}(\mathcal{T})=\mathcal{B}_{2}(\mathcal{T})$
which is impossible since the parameter $\lambda=1$ in our used design.
Similarly assume that there exists a set occurring in the same column, denoted
by
$\mathcal{C}=\mathbf{Q}((\mathcal{D}_{1},\mathcal{T}_{1}),\mathcal{B})=\mathbf{Q}((\mathcal{D}_{2},\mathcal{T}_{2}),\mathcal{B}),$
where $\mathcal{D}_{1},\mathcal{D}_{2}\in{[\Gamma]\choose\mu\Gamma}$,
$\mathcal{T}_{1},\mathcal{T}_{2}\in{[L]\choose t}$,
$\mathcal{B}\in\mathfrak{B}$ and
$(\mathcal{D}_{1},\mathcal{T}_{1})\neq(\mathcal{D}_{2},\mathcal{T}_{2})$. From
(47), we have

$\displaystyle\mathcal{D}_{1}\cap\mathcal{B}=\mathcal{D}_{2}\cap\mathcal{B}=\emptyset,\
\
\mathcal{D}_{1}\cup\mathcal{B}(\mathcal{T}_{1})=\mathcal{D}_{2}\cup\mathcal{B}(\mathcal{T}_{2}).$

This implies that $\mathcal{D}_{1}=\mathcal{D}_{2}$. Then we have
$\mathcal{B}(\mathcal{T}_{1})=\mathcal{B}(\mathcal{T}_{2})$, i.e.,
$\mathcal{T}_{1}=\mathcal{T}_{2}$. So
$(\mathcal{D}_{1},\mathcal{T}_{1})=(\mathcal{D}_{2},\mathcal{T}_{2})$ which is
contradiction with our hypothesis
$(\mathcal{D}_{1},\mathcal{T}_{1})\neq(\mathcal{D}_{2},\mathcal{T}_{2})$. From
the above introduction, we have that each subset of $\mathcal{X}$ occurring in
$\mathbf{P}$ occurs at most once in each row and each column, i.e., Condition
C3-a) holds.

Next consider Condition C3-b). Assume that there exist two different entries
in $\mathbf{Q}$ which are filled by the same set,

$\displaystyle\mathbf{Q}((\mathcal{T},\mathcal{D}),\mathcal{B})=\mathbf{Q}((\mathcal{T}^{\prime},\mathcal{D}^{\prime}),\mathcal{B}^{\prime})=\mathcal{B}(\mathcal{T})\cup\mathcal{D}=\mathcal{B}^{\prime}(\mathcal{T}^{\prime})\cup\mathcal{D}^{\prime}.$
(48)

It can be seen that $\mathcal{B}\neq\mathcal{B}^{\prime}$ and
$\mathcal{D}\neq\mathcal{D}^{\prime}$, since $\mathbf{Q}$ satisfies Condition
C3-a). Then for any $x\in\mathcal{D}\setminus\mathcal{D}^{\prime}$ and
$x^{\prime}\in\mathcal{D}^{\prime}\setminus\mathcal{D}$, we have

$x\in\mathcal{B}^{\prime}(\mathcal{T}^{\prime})\ \ \ \text{and}\ \ \
x^{\prime}\in\mathcal{B}(\mathcal{T}),$

which implies that $\mathcal{B}^{\prime}\bigcap\mathcal{D}\neq\emptyset$ and
$\mathcal{B}\bigcap\mathcal{D}^{\prime}\neq\emptyset$. From (47) we have
$\mathbf{Q}((\mathcal{T},\mathcal{D}),\mathcal{B}^{\prime})=\mathbf{Q}((\mathcal{T}^{\prime},\mathcal{D}^{\prime}),\mathcal{B})=*$,
implying that Condition C3-b) is satisfied.

As a result, $\mathbf{Q}$ is a $(K,F,Z,S)$ PDA, where

$\displaystyle K$ $\displaystyle={\Gamma\choose t}/{L\choose t},\ \
F={\Gamma\choose\mu\Gamma}{L\choose t},\ \
Z=\left({\Gamma\choose\mu\Gamma}-{\Gamma-L\choose\mu\Gamma}\right){L\choose
t},$ (49a) $\displaystyle S$ $\displaystyle\leq{\Gamma\choose
t+\mu\Gamma}-K{L\choose t+\mu\Gamma}.$ (49b)

Then by Lemma 1, we have a $(L,r,K,\Gamma,M,N)$ multiaccess coded caching
scheme based on a $t$-$(\Gamma,L,K,r,1)$ design with transmission load

$\displaystyle R$ $\displaystyle\leq\frac{{\Gamma\choose
t+\mu\Gamma}-K{L\choose t+\mu\Gamma}}{{\Gamma\choose\mu\Gamma}{L\choose t}}.$

We should point out that when $\mu\Gamma>\Gamma-L$, we have
${\Gamma-L\choose\mu\Gamma}=0$. So the parameter
$Z=\left({\Gamma\choose\mu\Gamma}-{\Gamma-L\choose\mu\Gamma}\right){L\choose
t}={\Gamma\choose\mu\Gamma}{L\choose t}=F$ in (49a). This implies that each
user can retrieve all the packets of any file. So in this paper we only need
to study the case $\mu\Gamma\leq\Gamma-L$.

###  V-D Further reduce the amount of transmission

In addition, we can further reduce the transmissions by using the following
observation.

######  Proposition 1.

In $\mathbf{Q}$ generated by (47), for any column labelled by
$\mathcal{B}\in\mathfrak{B}$ and any $(t+\mu\Gamma)$-subset $\mathcal{S}$ of
$[\Gamma]$ with $t+1\leq|\mathcal{S}\cap\mathcal{B}|<t+\mu\Gamma$, the
following always holds:

  * •

$\mathbf{Q}((\mathcal{D},\mathcal{T}),\mathcal{B})=*$, where
$\mathcal{D}\in{[\Gamma]\choose\mu\Gamma}$, $\mathcal{T}\in{[L]\choose t}$,
$\mathcal{B}^{\prime}\in\mathfrak{B}$, and
$\mathbf{Q}((\mathcal{D},\mathcal{T}),\mathcal{B}^{\prime})=\mathcal{S}$.

$\square$

###### Proof.

Since
$\mathbf{Q}((\mathcal{D},\mathcal{T}),\mathcal{B}^{\prime})=\mathcal{S}$,
$\mathcal{S}$ is composed of all elements in $\mathcal{D}$ and $t$ elements in
$\mathcal{B}^{\prime}$. Since
$t+1\leq|\mathcal{S}\cap\mathcal{B}|<t+\mu\Gamma$, there must be at least one
element in $\mathcal{D}$ which is also in $\mathcal{B}$, and so
$\mathbf{Q}((\mathcal{D},\mathcal{T}),\mathcal{B})=*$. ∎

Given $\mathcal{B}$, there are exactly

$\displaystyle S^{\prime}=\sum\limits_{i\in[\mu\Gamma-1]}{L\choose
t+i}{\Gamma-L\choose\mu\Gamma-i}$ (50)

$(t+\mu\Gamma)$-subsets $\mathcal{S}$ of $[\Gamma]$ satisfying
$t+1\leq|\mathcal{S}\cap\mathcal{B}|<t+\mu\Gamma$. By Proposition 1, the
number of the multicast messages (i.e., XOR of packets in each time slot)
which are unknown to user $U_{\mathcal{B}}$ is at most $S-S^{\prime}$. Thus,
using a $[S,S-S^{\prime}]$ MDS code, the server only needs to send
$S-S^{\prime}$ coded packets. Then the transmission load is

$\displaystyle\begin{split}R_{\text{Th1}}&=\frac{{\Gamma\choose
t+\mu\Gamma}-\sum^{\mu\Gamma-1}_{i=1}{L\choose
t+i}{\Gamma-L\choose\mu\Gamma-i}-K{L\choose t+\mu\Gamma}}{{L\choose
t}{\Gamma\choose\mu\Gamma}}&\\\\[5.69046pt] &=\frac{{\Gamma\choose
t+\mu\Gamma}}{{\Gamma\choose\mu\Gamma}{L\choose
t}}-\frac{\sum^{\mu\Gamma-1}_{i=1}{L\choose
t+i}{\Gamma-L\choose\mu\Gamma-i}}{{L\choose
t}{\Gamma\choose\mu\Gamma}}-\frac{K{L\choose t+\mu\Gamma}}{{L\choose
t}{\Gamma\choose\mu\Gamma}}&\end{split}$ (51)

which coincides with Theorem 1..

##  VI Multiaccess coded caching scheme for the $t$-GDD access topology: Proof
of Theorem 2

In this section, we focus on the MACC system with the $t$-GDD access topology
and propose a unified construction on the coded caching scheme given a $t$.
Then we show that by extending the proposed MACC scheme to the shared-link
model, the resulting scheme covers the shared-link caching scheme in [37] as a
special case.

For any positive integers $m$, $q\geq 2$, $s$, $t$ and $L$ satisfying $1\leq
t\leq L\leq s\leq m$, assume that there exists a $t$-$(m,q,L,1)$ GDD
$(\mathcal{X},\mathfrak{G},\mathfrak{B})$ and an OA$(m,q,s)$
$\mathbf{A}=(\mathbf{A}(j,u))_{j\in[q^{s}],u\in[m]}$. Without loss of
generality, we can let $\mathcal{X}=\\{(u,v)\ |\ u\in[m],v\in[q]\\}$,
$\mathfrak{G}=\\{\mathcal{G}_{1},\mathcal{G}_{1},\ldots,\mathcal{G}_{m}\\}$
and
$\mathfrak{B}=\\{\mathcal{B}_{1},\mathcal{B}_{2},\ldots,\mathcal{B}_{K}\\}$
where

$\displaystyle\mathcal{G}_{u}$ $\displaystyle=\\{(u,1),(u,2),\ldots,(u,q)\\},\
\forall u\in[m]$ (52a) $\displaystyle\mathcal{B}_{k}$
$\displaystyle=\\{(u_{k,1},v_{k,1}),\ldots,(u_{k,L},v_{k,L})\\},\ 1\leq
u_{k,1}<u_{k,2}<\cdots<u_{k,L}\leq m,$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1\leq
v_{k,1},v_{k,2},\ldots,v_{k,L}\leq q.$ (52b)

From (14) we have $K=|\mathfrak{B}|={m\choose t}q^{t}/{L\choose t}$. Then we
can obtain a $(L,K=|\mathfrak{B}|,\Gamma=mq,M,N)$ coded caching scheme with
$M/N=1/q$ under $(\mathcal{X},\mathfrak{G},\mathfrak{B})$ access topology and
OA$(m,q,s)$ placement strategy by constructing the following node-placement,
user-retrieval and user-delivery arrays.

###  VI-A Node-placement array

We will use the rows $\mathbf{A}(j,\cdot)$ where $j\in[q^{s}]$ of OA$(m,q,s)$
$\mathbf{A}=(\mathbf{A}(j,u))_{j\in[q^{s}],u\in[m]}$ as the packet labels and
place the packets on each cache-node according to the entries in $\mathbf{A}$.
Specifically, the server divides each file into $q^{s}$ subfiles with equal
size, i.e., for each $n\in[N]$, $W_{n}=(W_{n,j})_{j\in[q^{s}]}$. For
simplicity, the cache-nodes are denoted by $C_{u,v}$ where $u\in[m]$ and
$v\in[q]$, i.e., $C_{\gamma}=C_{u,v}$ if and only if $u=\lceil\gamma/q\rceil$
and $v=<\gamma>_{q}$. Each cache-node $C_{u,v}$ caches the following subfiles

$\displaystyle\mathcal{Z}_{C_{u,v}}=\left\\{W_{n,j}\ \Big{|}\
\mathbf{A}(j,u)=v,j\in[q^{s}],n\in[N]\right\\}.$ (53)

Based on the $t$-$(m,q,L,1)$ GDD $(\mathcal{X},\mathfrak{G},\mathfrak{B})$, we
further divide each subfile into ${L\choose t}$ packets, i.e.,
$W_{n,j}=(W^{\mathcal{T}}_{n,j})_{\mathcal{T}\in{[L]\choose t}}$ for each
$n\in[N]$ and $j\in[q^{s}]$. Then the packets cached by the cache-node
$C_{u,v}$ in (53) can be written as

$\displaystyle\mathcal{Z}_{C_{u,v}}=\left\\{W^{\mathcal{T}}_{n,j}\ \Big{|}\
\mathbf{A}(j,u)=v,j\in[q^{s}],\mathcal{T}\in{[L]\choose t},n\in[N]\right\\}.$
(54)

From (54) we can define a ${L\choose t}q^{s}\times mq$ node-placement array
$\mathbf{C}=\left(\mathbf{C}((j,{\mathcal{T}}),(u,v))\right)$, where
$\mathcal{T}\in{[L]\choose t}$, $j\in[q^{s}]$ and $u\in[m],v\in[q]$, to
represent the packets cached by the cache-nodes where

$\displaystyle\mathbf{C}((j,{\mathcal{T}}),(u,v))=\left\\{\begin{array}[]{ll}*&\
\ \ \hbox{if}\ \ \mathbf{A}(j,u)=v\\\ \text{null}&\ \ \
\hbox{otherwise}\end{array}\ .\right.$ (57)

Note that the row index of $\mathbf{C}$ is $(j,{\mathcal{T}})$ corresponding
to each packet; the column index of $\mathbf{C}$ is $(u,v)$ corresponding to
each cache-node. From (57), each column of $\mathbf{C}$ has exactly ${L\choose
t}q^{s-1}$ stars which implies that each cache-node caches $Nq^{s-1}{L\choose
t}$ packets, i.e., $\frac{N}{q}=\frac{NM}{N}=M$ files; there are $m$ stars in
each row, which means that each packet stored by $m$ cache-nodes.

Let us return to the example in Section IV-D. In the
$(L,K,\Gamma,M,N)=(2,12,6,3,6)$ coded caching scheme with the
OA$(m=3,q=2,s=2)$ placement for the $2$-$(3,2,2,1)$ GDD access topology, by
(54) and (57), the packets cached by cache-nodes are in (34) and the node-
placement array is in Table VII, respectively.

###  VI-B User-retrieve array

We treat each block of $\mathfrak{B}$ as the index of a user. For each integer
$k\in[K]$, from (52b) we use $\psi(\mathcal{B}_{k})$ to represent the set
consisting of the first coordinate of each point in $\mathcal{B}_{k}$ and use
$\psi(\mathcal{B}_{k})$ to represent the vector generated by the second
coordinate of each point in $\mathcal{B}_{k}$, i.e.,

$\displaystyle\psi(\mathcal{B}_{k})=\\{u_{k,1},u_{k,2},\ldots,u_{k,L}\\},\ \
\psi(\mathcal{B}_{k})=(v_{k,1},v_{k,2},\ldots,v_{k,L}).$

Then from (54) user $U_{\mathcal{B}_{k}}$ where $k\in[K]$ can retrieve the
following subpackets.

$\displaystyle\mathcal{Z}_{U_{\mathcal{B}_{k}}}=\bigcup\limits_{i\in[L]}\mathcal{Z}_{C_{u_{i},v_{i}}}=\left\\{W^{\mathcal{T}}_{n,j}\
\Big{|}\
\text{d}\left(\mathbf{A}(j,\psi(\mathcal{B}_{k})),\varphi(\mathcal{B}_{k})\right)<L,j\in[q^{s}],\mathcal{T}\in{[L]\choose
t},n\in[N]\right\\}.$ (58)

Note that
$\text{d}\left(\mathbf{A}(j,\psi(\mathcal{B}_{k})),\varphi(\mathcal{B}_{k})\right)$
is the hamming distance between the vectors
$\mathbf{A}(j,\psi(\mathcal{B}_{k}))$ and $\varphi(\mathcal{B}_{k})$, i.e.,
the number of coordinates in which $\mathbf{A}(j,\psi(\mathcal{B}_{k}))$ and
$\varphi(\mathcal{B}_{k})$ differ. From (58) we can define a ${L\choose
t}q^{s}\times K$ user-retrieve array
$\mathbf{U}=\left(\mathbf{U}((j,{\mathcal{T}}),\mathcal{B}_{k})\right)_{j\in[q^{s}],\mathcal{T}\in{[L]\choose
t},k\in[K]}$ to represent the packets retrieved by the users where each entry
$\mathbf{U}((j,{\mathcal{T}}),\mathcal{B}_{k})$ can be defined as follows.

$\displaystyle\mathbf{U}((j,{\mathcal{T}}),\mathcal{B}_{k})=\left\\{\begin{array}[]{ll}*&\
\ \ \hbox{if}\ \
\text{d}\left(\mathbf{A}(j,\psi(\mathcal{B}_{k})),\varphi(\mathcal{B}_{k})\right)<L\\\
\text{null}&\ \ \ \hbox{otherwise}\end{array}\right.$ (61)

For example, in the $(L,K,\Gamma,M,N)=(2,12,6,3,6)$ coded caching scheme under
OA$(m=3,q=2,s=2)$ placement and $2$-$(3,2,2,1)$ GDD access topology in (33) of
Subsection IV-D, from (58), the packets retrieved by users can be obtained in
(35). From (61) the user-retrieve array is obtained in Table VIII.

###  VI-C User-delivery array

Using the $\mathbf{U}$ generated in (61), the ${L\choose
t}q^{s}\times{m\choose t}q^{t}/{L\choose t}$ user-delivery array

$\mathbf{Q}=\left(\mathbf{Q}((j,{\mathcal{T}}),\mathcal{B}_{k})\right)_{j\in[q^{s}],\mathcal{T}\in{[L]\choose
t},k\in[K]}$

to represent the transmitted packets to the users can be defined as follows.

$\displaystyle\mathbf{Q}((j,{\mathcal{T}}),\mathcal{B}_{k})=\left\\{\begin{array}[]{ll}({\bf
e},n_{\bf
e})&\textrm{if}~{}\text{d}\left(\mathbf{A}(j,\psi(\mathcal{B}_{k})),\varphi(\mathcal{B}_{k})\right)=L,\\\
&\textrm{otherwise},\end{array}\right.$ (64)

where ${\bf e}=(e_{1},e_{2},\ldots,e_{m})\in[q]^{m}$ such that for each
$i\in[m]$

$\displaystyle
e_{i}=\left\\{\begin{array}[]{ll}\varphi(\mathcal{B}_{k})(h)&\textrm{if}\
i=\psi(\mathcal{B}_{k})(h)\in\mathcal{T}\ \text{for some}\
h\in[t],\\\\[5.69046pt] \mathbf{A}(j,i)&\textrm{otherwise,}\end{array}\right.$
(67)

$n_{\bf e}$ is the order of occurrence of the vector ${\bf e}$ in column
labelled by $\mathcal{B}_{k}$ and starts from $1$.

For example, in the $(L,K,\Gamma,M,N)=(2,12,6,3,6)$ coded caching scheme under
OA$(m=3,q=2,s=2)$ placement and $2$-$(3,2,2,1)$ GDD access topology of
Subsection IV-D, from (64) and (67), the user-delivery array is obtained in
Table IX. Since each vector occurs at most once in each column of Table IX, we
omit the occurrence number of each vector.

Now let us show that the obtained array $\mathbf{Q}$ satisfies Condition C3 of
Definition 1. For any two different entries say
$\mathbf{Q}((j,{\mathcal{T}}),\mathcal{B}_{k})$ and
$\mathbf{Q}((j^{\prime},\mathcal{T}^{\prime}),\mathcal{B}_{k^{\prime}})$ where
$j$, $j^{\prime}\in[q^{s}]$, $\mathcal{T}$,
$\mathcal{T}^{\prime}\in{[L]\choose t}$ and $k,k^{\prime}\in[K]$, assume that

$\displaystyle\mathbf{Q}((j,{\mathcal{T}}),\mathcal{B}_{k})=\mathbf{Q}((j^{\prime},\mathcal{T}^{\prime}),\mathcal{B}_{k^{\prime}})=(e_{1},e_{2},\ldots,e_{m},n).$
(68)

From (52), we denote the blocks $\mathcal{B}_{k}$ and
$\mathcal{B}_{k^{\prime}}$ as follows

$\displaystyle\mathcal{B}_{k}=\\{(u_{k,1},v_{k,1}),\ldots,(u_{k,L},v_{k,L})\\}\
\ \ \
\mathcal{B}_{k^{\prime}}=\\{(u_{k^{\prime},1},v_{k^{\prime},1}),\ldots,(u_{k^{\prime},L},v_{k^{\prime},L})\\}$

where $1\leq u_{k,1}<u_{k,2}<\cdots<u_{k,L}\leq m$, $1\leq
u_{k^{\prime},1}<u_{k^{\prime},2}<\cdots<u_{k^{\prime},L}\leq m$, $1\leq
v_{k,1},v_{k,2},\ldots,v_{k,L}\leq q$ and $1\leq
v_{k^{\prime},1},v_{k^{\prime},2},\ldots,v_{k^{\prime},L}\leq q$.

  * •

Let us consider condition C3-a) of Definition 1. From (64) we have
$\mathcal{B}_{k}\neq\mathcal{B}_{k^{\prime}}$, i.e., $k\neq k^{\prime}$, since
all the vectors are different in each column. So each vector occurs at most
once in each column. Assume that $(e_{1},e_{2},\ldots,e_{m})$ occurs twice in
a row $(j,\mathcal{T})$, i.e.,
$(j,\mathcal{T})=(j^{\prime},\mathcal{T}^{\prime})$. Let us consider the
subsets $\psi(\mathcal{B}_{k})$, $\psi(\mathcal{B}_{k^{\prime}})$ and the
vectors $\varphi(\mathcal{B}_{k})$, $\varphi(\mathcal{B}_{k^{\prime}})$
respectively. If
$\psi(\mathcal{B}_{k})(\mathcal{T})=\psi(\mathcal{B}_{k^{\prime}})(\mathcal{T})$
we have $\varphi(\mathcal{B}_{k})\neq\varphi(\mathcal{B}_{k^{\prime}})$ by the
definition of $t$-GDD. Then from (64) we have
$\mathbf{Q}((j,{\mathcal{T}}),\mathcal{B}_{k})\neq\mathbf{Q}((j^{\prime},\mathcal{T}^{\prime}),\mathcal{B}_{k^{\prime}})$
which contradicts our hypothesis. When
$\psi(\mathcal{B}_{k})(\mathcal{T})\neq\psi(\mathcal{B}_{k^{\prime}})(\mathcal{T})$
without loss of generality there must be two different integers say $u_{k,i}$
and $u_{k^{\prime},i^{\prime}}\in[m]$ where $i,i^{\prime}\in[L]$ such that

$\displaystyle
u_{k,i}\in\psi(\mathcal{B}_{k})(\mathcal{T})\setminus\psi(\mathcal{B}_{k^{\prime}})(\mathcal{T})\
\ \ \text{and}\ \ \
u_{k^{\prime},i^{\prime}}\in\psi(\mathcal{B}_{k^{\prime}})(\mathcal{T})\setminus\psi(\mathcal{B}_{k})(\mathcal{T})$

always hold. From (61) we have

$\displaystyle\mathbf{A}(j,u_{k^{\prime},i^{\prime}})=e_{u_{k^{\prime},i^{\prime}}}=v_{k^{\prime},i^{\prime}}\
\ \ \ \ \text{and}\ \ \ \ \ \mathbf{A}(j,u_{k,i})=e_{u_{k,i}}=v_{k,i}$

which implies that
$\mathbf{Q}((j,{\mathcal{T}}),\mathcal{B}_{k})=\mathbf{Q}((j^{\prime},\mathcal{T}^{\prime}),\mathcal{B}_{k^{\prime}})=*$,
a contradiction to our hypothesis. So Condition C3-a) holds.

  * •

Let us consider C3-b). That is (68) holds for the case
$(j,\mathcal{T})\neq(j^{\prime},\mathcal{T}^{\prime})$ and
$\mathcal{B}_{k}\neq\mathcal{B}_{k^{\prime}}$ (i.e., $k\neq k^{\prime}$).
Recall that every $t$-subset of points from $t$ different groups belongs to
exactly $\lambda=1$ block, i.e, the third property of a $t$-GDD,

$\displaystyle(\psi(\mathcal{B}_{k})(\mathcal{T}),\varphi(\mathcal{B}_{k})(\mathcal{T}))\neq(\psi(\mathcal{B}_{k^{\prime}})(\mathcal{T}^{\prime}),\varphi(\mathcal{B}_{k^{\prime}})(\mathcal{T}^{\prime}))$

always holds for any $\mathcal{T}$, $\mathcal{T}^{\prime}\in{[L]\choose t}$.
When
$\psi(\mathcal{B}_{k})(\mathcal{T})=\psi(\mathcal{B}_{k^{\prime}})(\mathcal{T}^{\prime})$
we have
$\varphi(\mathcal{B}_{k})(\mathcal{T})\neq\varphi(\mathcal{B}_{k^{\prime}})(\mathcal{T}^{\prime})$.
Then from (67) we have
$\mathbf{Q}((j,{\mathcal{T}}),\mathcal{B}_{k})\neq\mathbf{Q}((j^{\prime},\mathcal{T}^{\prime}),\mathcal{B}_{k^{\prime}})$,
a contradiction to our hypothesis in (68). When
$\psi(\mathcal{B}_{k})(\mathcal{T})\neq\psi(\mathcal{B}_{k^{\prime}})(\mathcal{T}^{\prime})$,
similar to proof of Condition C3-a), we also have that
$\mathbf{Q}((j,{\mathcal{T}}),\mathcal{B}_{k})=\mathbf{Q}((j^{\prime},\mathcal{T}^{\prime}),\mathcal{B}_{k^{\prime}})=*$,
a contradiction to our hypothesis.

From the above discussion, $\mathbf{Q}$ generated by (64) satisfies Condition
C3 of a PDA. Now let us compute the parameters $K$, $F$, $Z$ and $S$
respectively. First we have $K={m\choose t}q^{t}/{L\choose t}$,
$F=q^{s}{L\choose t}$ and $Z=\left(q^{s}-(q-1)^{L}q^{s-L}\right){L\choose t}$.

Finally let us consider the value of $S$. First there are at most $q^{m}$
different vectors ${\bf e}$ with length $m$. In addition, from (64) and (67)
it is easy to count that each vector ${\bf e}$ occurs at most $(q-1)^{t}$
times in a column. So the value of $S$ is at most $(q-1)^{t}q^{m}$. In fact it
is not easy to count the exact value of $S$ for any parameters $L$, $t$, $s$
and $m$. However when $L=t$, we can check that (64) is exactly the formula (2)
in [37, Construction 1]. Then the proof is completed.

##  VII The case $\lambda>1$

Using the same placement strategy in (37) and (41), we can also obtain the
scheme under any $t$-design accessing topology with index $\lambda>1$ by just
replacing the $(t+\mu\Gamma)$-subset
$\mathcal{D}\cup\mathcal{B}(\mathcal{T})$, which is defined in (71) for the
non-star entry at the row labelled by $(\mathcal{D},\mathcal{T})$ and the
column labelled by $\mathcal{B}$, by a pair
$(\mathcal{D}\cup\mathcal{B}(\mathcal{T}),n_{\mathcal{D},\mathcal{B}(\mathcal{T})})$
where $n_{\mathcal{D},\mathcal{B}(\mathcal{T})}$ is the occurrence order of
pair $(\mathcal{D},\mathcal{B}(\mathcal{T}))$ from top to bottom and left to
right in $\mathbf{Q}$. That is using the same constructions of node-placement
array in (40), user-retrieve array in (44) and changing construction of user-
delivery array $\mathbf{Q}$ in (47) as follows.

$\displaystyle\mathbf{Q}((\mathcal{D},\mathcal{T}),\mathcal{B})=\left\\{\begin{array}[]{ll}(\mathcal{D}\cup\mathcal{B}(\mathcal{T}),n_{\mathcal{D},\mathcal{B}(\mathcal{T})}),&\
\ \ \hbox{if}\ \ \mathcal{D}\cap\mathcal{B}=\emptyset\\\ &\ \ \
\hbox{otherwise}\end{array}\right.$ (71)

For instance, we take the node placement array $\mathbf{C}$ in Table IV of
Subsection IV-C to illustrate our rule defined in (71). When we use a
$2$-$(7,4,7,2)$ design $(\mathcal{X},\mathfrak{B})$ where

$\mathfrak{B}=\\{\\{1,2,3,5\\},\\{2,3,4,6\\},\\{3,4,5,7\\},\\{4,5,6,1\\},\\{5,6,7,2\\},\\{6,7,1,3\\},\\{7,1,2,4\\}\\},$

as the accessing topology, and from (47) we have a $42\times 7$ user-retrieve
array $\mathbf{U}$ listed in Table X to represent the packets retrieved by the
users.

TABLE X: User-retrieve array $\mathbf{U}$.  Subpacket labels | User set $\mathfrak{B}$
---|---
$\mathcal{D},\mathcal{T}$ | $U_{1235}$ | $U_{2346}$ | $U_{3457}$ | $U_{1456}$ | $U_{2567}$ | $U_{1367}$ | $U_{1247}$
$\\{1\\},\\{1,2\\}$ | * |  |  | * |  | * | *
$\\{2\\},\\{1,2\\}$ | * | * |  |  | * |  | *
$\\{3\\},\\{1,2\\}$ | * | * | * |  |  | * |
$\\{4\\},\\{1,2\\}$ |  | * | * | * |  |  | *
$\\{5\\},\\{1,2\\}$ | * |  | * | * | * |  |
$\\{6\\},\\{1,2\\}$ |  | * |  | * | * | * |
$\\{7\\},\\{1,2\\}$ |  |  | * |  | * | * | *
$\\{1\\},\\{1,3\\}$ | * |  |  | * |  | * | *
$\\{2\\},\\{1,3\\}$ | * | * |  |  | * |  | *
$\\{3\\},\\{1,3\\}$ | * | * | * |  |  | * |
$\\{4\\},\\{1,3\\}$ |  | * | * | * |  |  | *
$\\{5\\},\\{1,3\\}$ | * |  | * | * | * |  |
$\\{6\\},\\{1,3\\}$ |  | * |  | * | * | * |
$\\{7\\},\\{1,3\\}$ |  |  | * |  | * | * | *
$\\{1\\},\\{1,4\\}$ | * |  |  | * |  | * | *
$\\{2\\},\\{1,4\\}$ | * | * |  |  | * |  | *
$\\{3\\},\\{1,4\\}$ | * | * | * |  |  | * |
$\\{4\\},\\{1,4\\}$ |  | * | * | * |  |  | *
$\\{5\\},\\{1,4\\}$ | * |  | * | * | * |  |
$\\{6\\},\\{1,4\\}$ |  | * |  | * | * | * |
$\\{7\\},\\{1,4\\}$ |  |  | * |  | * | * | *
$\\{1\\},\\{2,3\\}$ | * |  |  | * |  | * | *
$\\{2\\},\\{2,3\\}$ | * | * |  |  | * |  | *
$\\{3\\},\\{2,3\\}$ | * | * | * |  |  | * |
$\\{4\\},\\{2,3\\}$ |  | * | * | * |  |  | *
$\\{5\\},\\{2,3\\}$ | * |  | * | * | * |  |
$\\{6\\},\\{2,3\\}$ |  | * |  | * | * | * |
$\\{7\\},\\{2,3\\}$ |  |  | * |  | * | * | *
$\\{1\\},\\{2,4\\}$ | * |  |  | * |  | * | *
$\\{2\\},\\{2,4\\}$ | * | * |  |  | * |  | *
$\\{3\\},\\{2,4\\}$ | * | * | * |  |  | * |
$\\{4\\},\\{2,4\\}$ |  | * | * | * |  |  | *
$\\{5\\},\\{2,4\\}$ | * |  | * | * | * |  |
$\\{6\\},\\{2,4\\}$ |  | * |  | * | * | * |
$\\{7\\},\\{2,4\\}$ |  |  | * |  | * | * | *
$\\{1\\},\\{3,4\\}$ | * |  |  | * |  | * | *
$\\{2\\},\\{3,4\\}$ | * | * |  |  | * |  | *
$\\{3\\},\\{3,4\\}$ | * | * | * |  |  | * |
$\\{4\\},\\{3,4\\}$ |  | * | * | * |  |  | *
$\\{5\\},\\{3,4\\}$ | * |  | * | * | * |  |
$\\{6\\},\\{3,4\\}$ |  | * |  | * | * | * |
$\\{7\\},\\{3,4\\}$ |  |  | * |  | * | * | *

Then from (71) the $42\times 7$ user-delivery array $\mathbf{Q}$ which is
listed in Table XI.

TABLE XI: User-delivery array $\mathbf{Q}$.  Subpacket labels | User set $\mathfrak{B}$
---|---
$\mathcal{D},\mathcal{T}$ | $U_{1235}$ | $U_{2346}$ | $U_{3457}$ | $U_{1456}$ | $U_{2567}$ | $U_{1367}$ | $U_{1247}$
$\\{1\\},\\{1,2\\}$ | * | 123,1 | 134,2 | * | 125,1 | * | *
$\\{2\\},\\{1,2\\}$ | * | * | 234,1 | 124,1 | * | 123,1 | *
$\\{3\\},\\{1,2\\}$ | * | * | * | 134,1 | 235,1 | * | 123,1
$\\{4\\},\\{1,2\\}$ | 124,1 | * | * | * | 245,2 | 134,2 | *
$\\{5\\},\\{1,2\\}$ | * | 235,1 | * | * | * | 135,1 | 125,1
$\\{6\\},\\{1,2\\}$ | 126,1 | * | 346,1 | * | * | * | 126,2
$\\{7\\},\\{1,2\\}$ | 127,1 | 237,2 | * | 147,1 | * | * | *
$\\{1\\},\\{1,3\\}$ | * | 124,1 | 135,1 | * | 126,2 | * | *
$\\{2\\},\\{1,3\\}$ | * | * | 235,1 | 125,1 | * | 126,2 | *
$\\{3\\},\\{1,3\\}$ | * | * | * | 135,1 | 236,1 | * | 134,2
$\\{4\\},\\{1,3\\}$ | 134,1 | * | * | * | 246,1 | 146,1 | *
$\\{5\\},\\{1,3\\}$ | * | 245,1 | * | * | * | 156,1 | 145,1
$\\{6\\},\\{1,3\\}$ | 136,1 | * | 356,2 | * | * | * | 146,1
$\\{7\\},\\{1,3\\}$ | 137,1 | 247,1 | * | 157,2 | * | * | *
$\\{1\\},\\{1,4\\}$ | * | 126,1 | 137,1 | * | 127,1 | * | *
$\\{2\\},\\{1,4\\}$ | * | * | 237,1 | 126,1 | * | 127,1 | *
$\\{3\\},\\{1,4\\}$ | * | * | * | 136,1 | 237,1 | * | 137,1
$\\{4\\},\\{1,4\\}$ | 145,1 | * | * | * | 247,1 | 147,1 | *
$\\{5\\},\\{1,4\\}$ | * | 256,1 | * | * | * | 157,1 | 157,2
$\\{6\\},\\{1,4\\}$ | 156,1 | * | 367,1 | * | * | * | 167,1
$\\{7\\},\\{1,4\\}$ | 157,1 | 267,1 | * | 167,1 | * | * | *
$\\{1\\},\\{2,3\\}$ | * | 134,1 | 145,1 | * | 156,1 | * | *
$\\{2\\},\\{2,3\\}$ | * | * | 245,1 | 245,2 | * | 236,1 | *
$\\{3\\},\\{2,3\\}$ | * | * | * | 345,1 | 356,2 | * | 234,1
$\\{4\\},\\{2,3\\}$ | 234,1 | * | * | * | 456,1 | 346,1 | *
$\\{5\\},\\{2,3\\}$ | * | 345,1 | * | * | * | 356,2 | 245,2
$\\{6\\},\\{2,3\\}$ | 236,1 | * | 456,1 | * | * | * | 246,1
$\\{7\\},\\{2,3\\}$ | 237,1 | 347,1 | * | 457,1 | * | * | *
$\\{1\\},\\{2,4\\}$ | * | 136,1 | 147,1 | * | 157,2 | * | *
$\\{2\\},\\{2,4\\}$ | * | * | 247,1 | 246,1 | * | 237,2 | *
$\\{3\\},\\{2,4\\}$ | * | * | * | 346,1 | 357,1 | * | 237,2
$\\{4\\},\\{2,4\\}$ | 245,1 | * | * | * | 457,1 | 347,1 | *
$\\{5\\},\\{2,4\\}$ | * | 356,1 | * | * | * | 357,1 | 257,1
$\\{6\\},\\{2,4\\}$ | 256,1 | * | 467,1 | * | * | * | 267,1
$\\{7\\},\\{2,4\\}$ | 257,1 | 367,1 | * | 467,2 | * | * | *
$\\{1\\},\\{3,4\\}$ | * | 146,1 | 157,1 | * | 167,1 | * | *
$\\{2\\},\\{3,4\\}$ | * | * | 257,1 | 256,1 | * | 267,1 | *
$\\{3\\},\\{3,4\\}$ | * | * | * | 356,1 | 367,1 | * | 347,1
$\\{4\\},\\{3,4\\}$ | 345,1 | * | * | * | 467,1 | 467,2 | *
$\\{5\\},\\{3,4\\}$ | * | 456,1 | * | * | * | 567,1 | 457,1
$\\{6\\},\\{3,4\\}$ | 356,1 | * | 567,1 | * | * | * | 467,2
$\\{7\\},\\{3,4\\}$ | 357,1 | 467,1 | * | 567,1 | * | * | *

It is not difficult to check that $\mathbf{Q}$ is a $(7,42,24,42)$ PDA which
realizes a $(7,M^{\prime},N)$ shared-link coded caching scheme with memory
ratio $M^{\prime}/N=4/7$ and transmission load $R=1$777With the same user
number and memory ratio, by Lemma 2 we have the $(7,M^{\prime},N)$ MN scheme
with transmission load $R=3/5$ which is smaller than our scheme. . Then we
have a $(L,K,\Gamma,M,N)=(4,7,7,1,7)$ coded caching scheme under the
$2$-$(7,4,7,2)$ design accessing topology with transmission load $R=1$.

Now let us show that the user-delivery array $\mathbf{Q}$ generated by (71)
satisfies C3 of Definition 1. Similar to the discussion of the case
$\lambda=1$, we can easy to check that $\mathbf{Q}$ generated in (71)
satisfies Condition C$3$-a) of Definition 1. Now let us see Condition C$3$-b)
in the following. Assume that there exist two distinct entries in $\mathbf{Q}$
which are filled by the same pair,

$\displaystyle\mathbf{Q}((\mathcal{T},\mathcal{D}),\mathcal{B})=\mathbf{Q}((\mathcal{T}^{\prime},\mathcal{D}^{\prime}),\mathcal{B}^{\prime})=(\mathcal{D}\cup\mathcal{B}(\mathcal{T}),n_{\mathcal{D},\mathcal{B}(\mathcal{T})})=(\mathcal{D}^{\prime}\cup\mathcal{B}^{\prime}(\mathcal{T}^{\prime}),n_{\mathcal{D}^{\prime},\mathcal{B}^{\prime}(\mathcal{T}^{\prime})}).$
(72)

If
$\mathcal{D}\cup\mathcal{B}(\mathcal{T})=\mathcal{D}^{\prime}\cup\mathcal{B}^{\prime}(\mathcal{T}^{\prime})$
we have $\mathcal{D}=\mathcal{D}^{\prime}$. Then from (71) we have
$n_{\mathcal{D},\mathcal{B}(\mathcal{T})}\neq
n_{\mathcal{D}^{\prime},\mathcal{B}^{\prime}(\mathcal{T}^{\prime})}$, a
contradiction to our hypothesis. So we have
$\mathcal{B}(\mathcal{T})\neq\mathcal{B}^{\prime}(\mathcal{T}^{\prime})$ which
implies that $\mathcal{D}\neq\mathcal{D}^{\prime}$.

Then for any $x\in\mathcal{D}\setminus\mathcal{D}^{\prime}$ and
$x^{\prime}\in\mathcal{D}^{\prime}\setminus\mathcal{D}$, we have

$x\in\mathcal{B}^{\prime}(\mathcal{T}^{\prime})\ \ \ \text{and}\ \ \
x^{\prime}\in\mathcal{B}(\mathcal{T})$

which implies that $\mathcal{B}^{\prime}\bigcap\mathcal{D}\neq\emptyset$ and
$\mathcal{B}\bigcap\mathcal{D}^{\prime}\neq\emptyset$. From (71) we have
$\mathbf{Q}((\mathcal{T},\mathcal{D}),\mathcal{B}^{\prime})$
$=\mathbf{Q}((\mathcal{T}^{\prime},\mathcal{D}^{\prime}),\mathcal{B})$ $=*$.

Similar to Subsection V-D, let us consider the parameters $K$, $F$ and $S$.
First we have $K=\lambda{\Gamma\choose t}/{L\choose t}$ from (12) and
$F={\Gamma\choose\mu\Gamma}{L\choose t}$ from (40). So we only need to count
the number of different pairs occurring in $\mathbf{Q}$ generated in (71),
i.e., the value of $S$. Clearly there are at most $\lambda{\Gamma\choose
t+\mu\Gamma}$ different pairs; for each $(t+\mu\Gamma)$-subset $\mathcal{S}$
belonging to some block $\mathcal{B}\in\mathfrak{B}$, $\mathcal{B}$ contains
all the $t$-subsets which are the subset of $\mathcal{S}$, i.e., there are
exactly ${\mu\Gamma+t\choose t}$ subsets $\mathcal{T}\in{[L]\choose t}$
satisfying $\mathcal{B}(\mathcal{T})\subseteq\mathcal{S}$, this implies that
for each $t$-subset belonging to $\mathcal{S}$, the subset $\mathcal{S}$
occurs in $\mathbf{Q}$ at most $\lambda-1$ times, then there are at least
$K{L\choose t+\mu\Gamma}$ pairs which do not occur in $\mathbf{Q}$. So
$\mathbf{Q}$ has at most

$\displaystyle S$ $\displaystyle\leq\lambda{\Gamma\choose
t+\mu\Gamma}-K{L\choose t+\mu\Gamma}=\lambda{\Gamma\choose
t+\mu\Gamma}-\frac{\lambda{\Gamma\choose t}}{{L\choose t}}{L\choose
t+\mu\Gamma}$ $\displaystyle=\lambda\left({\Gamma\choose
t+\mu\Gamma}-\frac{{\Gamma\choose t}{L\choose t+\mu\Gamma}}{{L\choose
t}}\right)$

different pairs in $\mathbf{Q}$. We have that $\mathbf{Q}$ generated in (71)
is a $\left(K=\lambda{\Gamma\choose t}/{L\choose t}\right.$, $F={L\choose
t}{\Gamma\choose\mu\Gamma}$, $Z={L\choose t}{\Gamma\choose\mu\Gamma}-{L\choose
t}{\Gamma-L\choose\mu\Gamma}$, $\left.S\leq\lambda({\Gamma\choose
t+\mu\Gamma}-{\Gamma\choose t}{L\choose t+\mu\Gamma})/{L\choose t}\right)$
PDA.

Recall $\mathbf{Q}$ listed in Table XI. We can see that there exactly
$K{L\choose t+\mu\Gamma}=7\times{4\choose 3}=28$ subset with size $3$

$\displaystyle\begin{split}&\\{1,2,3\\},\\{1,2,5\\},\\{1,3,5\\},\\{2,3,5\\}\subseteq\\{1,2,3,5\\},&\\\
&\\{2,3,4\\},\\{2,3,6\\},\\{2,4,6\\},\\{3,4,6\\}\subseteq\\{2,3,4,6\\},&\\\
&\\{3,4,5\\},\\{3,4,7\\},\\{3,5,7\\},\\{4,5,7\\}\subseteq\\{3,4,5,7\\},&\\\
&\\{4,5,6\\},\\{1,4,5\\},\\{1,4,6\\},\\{1,5,6\\}\subseteq\\{1,4,5,6\\},&\\\
&\\{5,6,7\\},\\{2,5,6\\},\\{2,5,7\\},\\{2,6,7\\}\subseteq\\{2,5,6,7\\},&\\\
&\\{1,6,7\\},\\{3,6,7\\},\\{1,3,6\\},\\{1,3,7\\}\subseteq\\{1,3,6,7\\},&\\\
&\\{1,2,7\\},\\{1,4,7\\},\\{2,4,7\\},\\{1,2,4\\}\subseteq\\{1,2,4,7\\}.&\end{split}$
(73)

each of which occurs in $\mathbf{Q}$ exactly once. Since the subset
$\\{1,2,6\\}$ doest not occur in any blocks in (73) and $\lambda=2$, the
subset $\\{1,2,6\\}$ occurs in $\mathbf{Q}$ exactly twice for each
$t=2$-subset $\\{1,2\\}$, $\\{1,6\\}$ and $\\{2,6\\}$.

Finally similar to Subsection V-D, we can also further reduce the
transmission. First we can prove that Proposition 1 also holds for the
$\mathbf{Q}$ generated by (71). Then given any block
$\mathcal{B}\in\mathfrak{B}$, there are exactly
$S^{\prime}=\sum_{i\in[\mu\Gamma-1]}{L\choose
t+i}{\Gamma-L\choose\mu\Gamma-i}$ $(t+\mu\Gamma)$-subsets $\mathcal{S}$ of
$[\Gamma]$ satisfying $t+1\leq|\mathcal{S}\cap\mathcal{B}|<t+\mu\Gamma$, and
for each $t$-subset of $\mathcal{S}$, there are exactly $\lambda$ different
pairs containing $\mathcal{S}$, so by Proposition 1 the number of the coded
packets which are unknown for user $U_{\mathcal{B}}$ is at most $S-\lambda
S^{\prime}$. Using a $[S,S-\lambda S^{\prime}]$ maximum sparable code, the
server only needs to send $S-\lambda S^{\prime}$ coded packets. Then the
transmission load is

$\displaystyle\begin{split}R&=\frac{\lambda{\Gamma\choose
t+\mu\Gamma}-\lambda\sum^{\mu\Gamma-1}_{i=1}{L\choose
t+i}{\Gamma-L\choose\mu\Gamma-i}-K{L\choose t+\mu\Gamma}}{{L\choose
t}{\Gamma\choose\mu\Gamma}}&\\\\[5.69046pt] &=\frac{\lambda{\Gamma\choose
t+\mu\Gamma}}{{\Gamma\choose\mu\Gamma}{L\choose
t}}-\frac{\lambda\sum^{\mu\Gamma-1}_{i=1}{L\choose
t+i}{\Gamma-L\choose\mu\Gamma-i}}{{L\choose
t}{\Gamma\choose\mu\Gamma}}-\frac{K{L\choose t+\mu\Gamma}}{{L\choose
t}{\Gamma\choose\mu\Gamma}}.&\end{split}$ (74)

######  Remark 2.

(The schemes via $t$-design with $\lambda=1$ and $\lambda>1$) When there
exists a $t$-$(\Gamma,L,K,1)$ design $(\mathcal{X},\mathfrak{B})$ and a
$t$-$(\Gamma,L,\lambda K,\lambda)$ design
$(\mathcal{X},\mathfrak{B}^{\prime})$, we can obtain a $(L,K={\Gamma\choose
t}/{L\choose t},\Gamma,M,N)$ coded caching scheme (Scheme A) under
$(\mathcal{X},\mathfrak{B})$ with transmission load $R_{1}$ in (25), and a
$(L,\lambda K,\Gamma,M,N)$ coded caching scheme (Scheme B) under
$(\mathcal{X},\mathfrak{B}^{\prime})$ with transmission load $R_{2}$ in (74).
We can see that Scheme B has the $\lambda$ times larger transmission load than
that of Scheme A. So by grouping method (replicating Scheme A $\lambda$ times)
we can easily obtain a scheme with the user number $\lambda K$ which has the
same performance as Scheme B.

We should point out that if there exists a $t$-$(\Gamma,L,K,1)$ design, then
there must exit a $t$-$(\Gamma,L,\lambda K,\lambda)$ design for any
$\lambda>1$. However it does not always hold conversely. So studying a coded
caching scheme under a $t$-$(\Gamma,L,\lambda K,\lambda)$ design for any
$\lambda>1$ is also meaningful.

##  VIII Conclusion

In this paper, we considered a very general MACC setting where the topology
defining the connectivity between the users and the caches is directly derived
from a general combinatorial $t$-design and $t$-GDD structures. For this
general setting, we have developed new schemes that manage to unify a broad
spectrum of existing MACC schemes and the shared-link schemes. Most
importantly, by allowing this unification, our schemes can dramatically
densify the range of users for which high-performance MACC scheme can treat.

##  Appendix A Proof of Lemma 5

Let $(\mathcal{V},\mathfrak{A})$ be a $t$-cross
$(v,k,\Gamma_{t},m,\lambda_{t})$ resolvable design. Then $|\mathcal{V}|=v$,
$|\mathfrak{A}|=\Gamma_{t}$, where each block has $k$ points. Let $q=v/k$.
Without loss of generality let $\mathcal{V}=\\{1,2,\ldots,v\\}$ and
$\mathfrak{A}$ consist of $m$ parallel classes $\mathfrak{A}_{1}$,
$\mathfrak{A}_{2}$, $\ldots$, $\mathfrak{A}_{m}$ where

$\mathfrak{A}_{u}=\\{\mathcal{A}_{u,1},\mathcal{A}_{u,2},\ldots,\mathcal{A}_{u,q}\\},\
\ \ \ \ u\in[m].$

Then we can obtain the dual design
$(\mathcal{X},\mathfrak{B})=(\mathfrak{A},\mathcal{V})$ where for each
$j\in\mathcal{V}$, the block is defined as follows.

$\displaystyle\mathcal{B}_{j}=\\{\mathcal{A}_{u,v}\ |\
j\in\mathcal{A}_{u,v},u\in[m],v\in[q]\\}$ (75)

Clearly each block $\mathcal{B}_{j}$ has exactly $m$ points, i.e.,
$|\mathcal{B}_{j}|=m$. Let

$\displaystyle\mathfrak{G}=\\{\mathcal{G}_{1}=\mathfrak{A}_{1},\mathcal{G}_{2}=\mathfrak{A}_{2},\ldots,\mathcal{G}_{m}=\mathfrak{A}_{m}\\}.$
(76)

Clearly, each point occurs exactly $r$ times since each block of
$\mathfrak{A}$ has $r$ points of $\mathcal{V}$, and $\mathfrak{G}$ is a
partition of $\mathcal{X}$ into $m$ subsets each of which has size $q$.

Now let us show that the triple $(\mathcal{X},\mathfrak{G},\mathfrak{B})$ is a
$t$-$(m,q,m,\lambda_{t})$ GDD. By Definition 6, i.e., the intersection of any
$t$ blocks drawn from any $t$ different parallel classes has the same size
$\lambda_{t}$, we have that any $t$-subset of points in $\mathcal{X}$ from $t$
different groups belongs to exactly $\lambda_{t}$ blocks. So
$(\mathcal{X},\mathfrak{B})$ is a $t$-$(m,q,m,\lambda_{t})$ GDD.

##  Appendix B Proof of Lemma 6

Let us continue to use the notations in Lemma 5. Recall the
$t$-$(m,q,m,\lambda_{t})$ GDD $(\mathcal{X},\mathfrak{G},\mathfrak{B})$
generated by (75) and (76) in proof Lemma 5. Similarly to defining the block
of $\mathfrak{B}$ (75) we can define a $v\times m$ array
$\mathbf{A}=(\mathbf{A}(j,u))_{j\in\mathcal{X},u\in[m]}$ where

$\displaystyle\mathbf{A}(j,u)=v\ \ \ \text{if}\ \ j\in\mathcal{A}_{u,v}\ \
\text{for some integer}\ v\in[q].$ (77)

It is not difficult to check that for any $t$ columns, each vector of
$[q]^{t}$ occurs in exactly $\lambda_{t}$ rows by the property of
$t$-$(v,k,\Gamma,m,\lambda_{t})$ resolvable design, i,e., the size of the
intersection of the $t$ blocks $\mathcal{A}_{1,a_{j,1}}$,
$\mathcal{A}_{2,a_{j,2}}$, $\ldots$, $\mathcal{A}_{m,a_{j,m}}$ is
$\lambda_{t}$, which implies that for any $t$ columns, each vector of
$[q]^{t}$ occurs in exactly $\lambda_{t}$ rows. By Definition 7
$v=\lambda_{t}q^{t}$, $\Gamma=qm$ and each integer occurs exactly
$\lambda_{t}q^{t-1}$ in each column. This is the reason why the cross
resolvable design always has $v=\lambda_{t}q^{t}$ and each block has exactly
$\lambda_{t}q^{t-1}$ points in [29, 36, 35, 47].

Conversely suppose
$\mathbf{A}=(\mathbf{A}(j,u))_{j\in[\lambda_{t}q^{t}],u\in[m]}$ is a
OA${}_{\lambda_{t}}(m,q,t)$. Let

$\displaystyle\mathcal{V}=\\{\mathbf{A}(j,\cdot)\ |\
j\in[\lambda_{t}q^{t}]\\}$ (78)

and $\mathfrak{A}=\\{\mathcal{A}_{u,v}\ |\ u\in[m],v\in[q]\\}$ where

$\displaystyle\mathcal{A}_{u,v}=\\{j\in[F]\ |\ \mathbf{A}(j,u)=v\\}$ (79)

Clearly each $\mathfrak{A}_{u}=\\{\mathcal{A}_{u,v}\ |\ v\in[q]\\}$ where
$u\in[m]$ is a parallel class of $\mathcal{V}$. Furthermore, one can check
that $(\mathcal{V},\mathfrak{A})$ is a $t$ cross
$(v,k,\Gamma_{t},m,\lambda_{t})$ resolvable design by the property of
OA${}_{\lambda_{t}}(m,q,t)$, i.e., for any $t$ columns, each vector of
$[q]^{t}$ occurs in exactly $\lambda_{t}$ rows which is equivalent to that the
intersection of any $L$ blocks from different $t$ parallel classes contains
exactly $\lambda_{t}$ points.

## References

  * [1] E. Bastug, M. Bennis, and M. Debbah, “Living on the edge: The role of proactive caching in 5G wireless networks,” _IEEE Communications Magazine_ , vol. 52, no. 8, pp. 82–89, 2014.
  * [2] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” _IEEE Transactions on Information Theory_ , vol. 60, no. 5, pp. 2856–2867, 2014.
  * [3] H. Ghasemi and A. Ramamoorthy, “Improved lower bounds for coded caching,” _IEEE Transactions on Information Theory_ , vol. 63, no. 7, pp. 4388–4413, 2017.
  * [4] K. Wan, D. Tuninetti, and P. Piantanida, “An index coding approach to caching with uncoded cache placement,” _IEEE Transactions on Information Theory_ , vol. 66, no. 3, pp. 1318–1332, 2020.
  * [5] Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “The exact rate-memory tradeoff for caching with uncoded prefetching,” _IEEE Transactions on Information Theory_ , vol. 64, no. 2, pp. 1281–1296, 2018.
  * [6] ——, “Characterizing the rate-memory tradeoff in cache networks within a factor of 2,” _IEEE Transactions on Information Theory_ , vol. 65, no. 1, pp. 647–663, 2019.
  * [7] Q. Yan, M. Cheng, X. Tang, and Q. Chen, “On the placement delivery array design for centralized coded caching scheme,” _IEEE Transactions on Information Theory_ , vol. 63, no. 9, pp. 5821–5833, 2017.
  * [8] K. Shanmugam, A. M. Tulino, and A. G. Dimakis, “Coded caching with linear subpacketization is possible using Ruzsa-Szeméredi graphs,” in _2017 IEEE International Symposium on Information Theory (ISIT)_ , 2017, pp. 1237–1241.
  * [9] C. Shangguan, Y. Zhang, and G. Ge, “Centralized coded caching schemes: A hypergraph theoretical approach,” _IEEE Transactions on Information Theory_ , vol. 64, no. 8, pp. 5755–5766, 2018.