Caching is a promising solution to satisfy the ever-increasing demands for the multi-media traffics. In caching networks, coded caching is a recently proposed technique that achieves significant ...performance gains over the uncoded caching schemes. However, to implement the coded caching schemes, each file has to be split into F packets, which usually increases exponentially with the number of users K. Thus, designing caching schemes that decrease the order of F is meaningful for practical implementations. In this paper, by reviewing the Ali-Niesen caching scheme, the placement delivery array (PDA) design problem is first formulated to characterize the placement issue and the delivery issue with a single array. Moreover, we show that, through designing appropriate PDA, new centralized coded caching schemes can be discovered. Second, it is shown that the Ali-Niesen scheme corresponds to a special class of PDA, which realizes the best coding gain with the least F. Third, we present a new construction of PDA for the centralized coded caching system, wherein the cache size M at each user (identical cache size is assumed at all users) and the number of files N satisfies M/N = 1/q or (q - 1)/q (q is an integer, such that q ≥ 2). The new construction can decrease the required F from the order O(e K·((M/N) ln(N/M)+(1-(M/N)) ln (N/(N-M)) ) of Ali-Niesen scheme to O(e K·(M/N) ln(N/M) ) or O(e K·(1-(M/N)) ln(N/(N-M)) ), respectively, while the coding gain loss is only 1.
The technique of coded caching proposed by Madddah-Ali and Niesen is a promising approach to alleviate the load of networks during peak-traffic times. Recently, placement delivery array (PDA) was ...presented to characterize both the placement and delivery phase in a single array for the centralized coded caching algorithm. In this letter, we reinterpret PDA from a new perspective, i.e., the strong edge coloring of bipartite graph (bigraph). We prove that, a PDA is equivalent to a strong edge colored bigraph. Thus, we can construct a class of PDAs from existing structures in bigraphs. The class subsumes the scheme proposed by Maddah-Ali et al. and a more general class of PDAs proposed by Shangguan et al. as special cases.
Parent-identifying schemes provide a way to identify causes from effects for some information systems, such as digital fingerprinting and group testing. In this paper, we consider the combinatorial ...structures for parent-identifying schemes. First, we establish an equivalent relationship between the parent-identifying schemes and forbidden configurations. Based on this relationship, we derive the probabilistic existence lower bounds for two related combinatorial structures, that is, <inline-formula> <tex-math notation="LaTeX">t </tex-math></inline-formula>-parent-identifying set systems (<inline-formula> <tex-math notation="LaTeX">t </tex-math></inline-formula>-IPPS) and <inline-formula> <tex-math notation="LaTeX">t </tex-math></inline-formula>-multimedia parent-identifying codes (<inline-formula> <tex-math notation="LaTeX">t </tex-math></inline-formula>-MIPPC), which are used in broadcast encryption and multimedia fingerprinting, respectively. The probabilistic lower bound for the maximum size of a <inline-formula> <tex-math notation="LaTeX">t </tex-math></inline-formula>-IPPS has the asymptotically optimal order of magnitude in many cases, and that for <inline-formula> <tex-math notation="LaTeX">t </tex-math></inline-formula>-MIPPC provides the asymptotically optimal code rate when <inline-formula> <tex-math notation="LaTeX">t=2 </tex-math></inline-formula> and the best known asymptotic code rate when <inline-formula> <tex-math notation="LaTeX">t\ge 3 </tex-math></inline-formula>. Furthermore, we analyze the structure of 2-IPPS and prove some bounds for certain cases.
Wu et al. (IEEE Signal Process Mag 21:15–27, 2004) showed that fingerprinting system can be designed according to different criteria: catching one, catching many and catching all. For the case of ...“catching many”, binary multimedia identifiable parent property codes (
t
-MIPPCs) were introduced to construct fingerprints resistant to the averaging collusion attack on multimedia contents. In this paper, we focus on such a case, and introduce the binary strongly multimedia identifiable parent property code (
t
-SMIPPC) whose tracing algorithm is more efficient than that of a binary
t
-MIPPC. Then a concatenation construction for binary
t
-SMIPPCs from
q
-ary
t
-SMIPPCs is provided. Moreover, we establish a probabilistic lower bound on
q
-ary
t
-SMIPPCs, whose code rate is asymptotically as good as that of
q
-ary
t
-MIPPCs. Finally, several infinite series of optimal
q
-ary
t
-SMIPPCs of length 2 with
t
=
2
,
3
are derived from the relationships among
t
-SMIPPCs and other fingerprinting codes, such as
t
-MIPPCs and
t
¯
-separable codes.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OBVAL, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
In a hierarchical caching system, a server is connected to multiple mirrors, each of which is connected to a different set of users, and both the mirrors and the users are equipped with caching ...memories. All the existing schemes focus on single file retrieval, i.e., each user requests one file. In this paper, we consider the linear function retrieval problem, i.e., each user requests a linear combination of files, which includes single file retrieval as a special case. We propose a new scheme that reduces the transmission load of the first hop by jointly utilizing the two layers' cache memories, and we show that our scheme achieves the optimal load for the second hop in some cases.
Full text
Available for:
IZUM, KILJ, NUK, PILJ, PNG, SAZU, UL, UM, UPUK
The concept of a locally repairable code (LRC) was introduced to protect the data from disk failures in large-scale storage systems. In this paper, we consider the LRCs with multiple disjoint repair ...sets and each repair set contains exactly one check symbol. By using several structures from combinatorial design theory, such as balanced incomplete block design, cyclic packing, group divisible design, near-Skolem sequence and Langford sequence, we construct several infinite classes of LRCs with the size of each repair set at most 3, which are optimal with respect to the bound proposed by Rawat et al. in 2016.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OBVAL, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
Multimedia fingerprinting is an effective technique to trace the sources of pirate copies of copyrighted multimedia information. AND anti-collusion codes can be used to construct fingerprints ...resistant to collusion attacks on multimedia contents. In this paper, we first investigate AND anti-collusion codes and related detection algorithms from a combinatorial viewpoint, and then introduce a new concept of logical anti-collusion code to improve the traceability of multimedia fingerprinting. It reveals that frameproof codes have traceability for multimedia contents. Relationships among anti-collusion codes and other structures related to fingerprinting are discussed, and constructions for both AND anti-collusion codes and logical anti-collusion codes are provided.
In this paper, we study the entropy functions on extreme rays of the polymatroidal region which contain a matroid, i.e., matroidal entropy functions. We introduce variable strength orthogonal arrays ...indexed by a connected matroid
and positive integer
which can be regarded as expanding the classic combinatorial structure orthogonal arrays. It is interesting that they are equivalent to the partition-representations of the matroid
with degree
and the (M,v) almost affine codes. Thus, a synergy among four fields, i.e., information theory, matroid theory, combinatorial design, and coding theory is developed, which may lead to potential applications in information problems such as network coding and secret-sharing. Leveraging the construction of variable strength orthogonal arrays, we characterize all matroidal entropy functions of order n≤5 with the exception of log10·U2,5 and logv·U3,5 for some
.
Full text
Available for:
IZUM, KILJ, NUK, PILJ, PNG, SAZU, UL, UM, UPUK
In a traditional (H,r) combination network, each user connects to a unique set of r relays. However, few research efforts have considered the (H,r,u) multiaccess combination network problem wherein ...each unique set of r relays is connected by u users. In this paper, we focus on designing coded caching schemes for a (H,r,u) multiaccess combination network. By directly applying the well-known coding method (proposed by Zewail and Yener) for a (H,r) combination network, a coded caching scheme (called ZY scheme) for (H,r,u) multiaccess combination network is obtained. However, its subpacketization has an exponential order with the number of users which leads to high implementation complexity. In order to reduce subpacketization, a direct construction of a coded caching scheme (called the direct scheme) for (H,r,u) multiaccess combination network is proposed by means of combinational design theory, where the parameter u must be a combinatorial number. For the arbitrary parameter u, the hybrid construction of a coded caching scheme (called the hybrid scheme) for the (H,r,u) multiaccess combination network is proposed based on the direct scheme. Theoretical and numerical analysis shows that the direct scheme and the hybrid scheme have a smaller transmission load for each relay compared with the naive scheme (which is obtained by repeatedly applying the coded caching scheme for a traditional (H,r) combination network by u times) and have much lower subpacketization compared with the ZY scheme.
Coded caching is widely regarded as an important tool to reduce pressure on the data transmission during the peak traffic times in heterogeneous wireless networks. In this paper, we will provide two ...concatenating constructions of coded caching schemes based on the schemes derived by Shangguan et al. in 2018 and Yan et al. in 2017, respectively. Then we show that our new schemes have good performance in reducing packet number. Furthermore, in some case, we present that our schemes have better performances on user number, memory ratio, packet number and transmission rate than the schemes obtained by Chittoor et al. in 2019 and Krishnan in 2018.
PDF
