Coded caching schemes with low subpacketization and small transmission rate are desirable in practice due to the requirement of low implementation complexity and efficiency of transmission. Placement ...delivery arrays (PDA in short) can be used to generate coded caching schemes. However, many known coded caching schemes, which have low subpacketizations, realized by PDAs do not fully use the users' caching content to create multicasting opportunities. So we propose a method to overcome this drawback. As an application, we obtain a new scheme, which has significantly advantages on the tradeoff between memory ratio and transmission rate.
Separable Codes Cheng, Minquan; Ji, Lijun; Miao, Ying
IEEE transactions on information theory,
03/2012, Volume:
58, Issue:
3
Journal Article
Peer reviewed
Multimedia fingerprinting is an effective technique to trace the sources of pirate copies of copyrighted multimedia information. Separable codes can be used to construct fingerprints resistant to the ...averaging collusion attack on multimedia contents. In this paper, we investigate -separable codes from a combinatorial point of view. We first derive several upper bounds on the sizes of -separable codes, and then turn our attention to the constructions of optimal -separable codes with short length. Two infinite families of optimal -separable codes of length 2 are constructed from projective planes, and all optimal -separable codes of length 3 are explicitly constructed by means of difference matrices. These optimal -separable codes with short length can be used to construct good -separable codes with long length by a known composition construction.
Seven infinite classes of relative difference families with variable block sizes are presented explicitly. In particular, a balanced ( gv , g , K ,1)-DF with g =Σ k∈K ( k 2 - k )/2 is explicitly ...given for: (i) K ={3,4,5} and every v coprime to 6; (ii) K ={3,4,6}, {3,5,6} or {3,4,5,6} and every v coprime to 30. As far as the authors are aware, these difference families can be viewed as the first explicit constructions of infinite classes of optimal variable-weight optical orthogonal codes with more than two weights. It is observed, however, that there are infinitely many values of v for which an optimal ( v , W ,1, Q ) -OOC exists, whatever the set of weights W and the weight distribution sequence Q are.
Matroidal entropy functions are entropy functions in the form h = log v ·r M , where v ≥ 2 is an integer and r M is the rank function of a matroid M . They can be applied into capacity ...chracterization and code construction of information theory problems such as network coding, secret sharing, index coding and locally repairable code. In this paper, by constructing the variable strength orthogonal arrays of some matroid operations, we characterize matroidal entropy functions induced by regular matroids and some matroids with the same p-characteristic set as uniform matroid U 2,4 .
Coded caching scheme recently has become quite popular in the wireless network, since the maximum transmission amount <inline-formula> <tex-math notation="LaTeX">{R} </tex-math></inline-formula> ...reduces effectively during the peak-traffic times. To realize a coded caching scheme, each file must be divided into <inline-formula> <tex-math notation="LaTeX">{F} </tex-math></inline-formula> packets, which usually increases the computation complexity of a coded caching scheme. So we prefer to design a scheme with <inline-formula> <tex-math notation="LaTeX">{R} </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">{F} </tex-math></inline-formula> as small as possible in practice. However, there exists a tradeoff between <inline-formula> <tex-math notation="LaTeX">{R} </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">{F} </tex-math></inline-formula>. In this paper, we generalize the schemes constructed by Shangguan et al. (IEEE Transactions on Information Theory, 64, 5755-5766, 2018) and Yan et al. (IEEE Transactions on Information Theory 63, 5821-5833, 2017), respectively. These two classes of schemes have a wider range of application due to the more flexible memory size than the original ones. By comparing with the previous known deterministic schemes, our new schemes have advantages on <inline-formula> <tex-math notation="LaTeX">{R} </tex-math></inline-formula> or <inline-formula> <tex-math notation="LaTeX">{F} </tex-math></inline-formula>.
In caching system, it is desirable to design a coded caching scheme with the transmission load <inline-formula> <tex-math notation="LaTeX">R </tex-math></inline-formula> and subpacketization ...<inline-formula> <tex-math notation="LaTeX">F </tex-math></inline-formula> as small as possible, in order to improve efficiency of transmission in the peak traffic times and to decrease implementation complexity. Yan et al. reformulated the centralized coded caching scheme as designing a corresponding <inline-formula> <tex-math notation="LaTeX">F\times K </tex-math></inline-formula> array called placement delivery array (PDA), where <inline-formula> <tex-math notation="LaTeX">F </tex-math></inline-formula> is the subpacketization and <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula> is the number of users. Motivated by several constructions of PDAs, we introduce a framework for constructing PDAs, where each row is indexed by a row vector of some matrix called row index matrix and each column's index is labelled by an element of a direct product set. Using this framework, a new scheme is obtained, which can be regarded as a generalization of some previously known schemes. When <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula> is equal to <inline-formula> <tex-math notation="LaTeX">{\binom{m}{ t}}q^{t} </tex-math></inline-formula> for positive integers <inline-formula> <tex-math notation="LaTeX">m </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">t </tex-math></inline-formula> with <inline-formula> <tex-math notation="LaTeX">t < m </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">q\geq 2 </tex-math></inline-formula>, we show that the row index matrix must be an orthogonal array if all the users have the same memory size. Furthermore, the row index matrix must be a covering array if the coded gain is <inline-formula> <tex-math notation="LaTeX">{\binom{m}{ t}} </tex-math></inline-formula>, which is the maximal coded gain under our framework. Consequently the lower bounds on the transmission load and subpacketization of the schemes are derived under our framework. Finally, using orthogonal arrays as the row index matrix, we obtain two more explicit classes of schemes which have significantly advantages on the subpacketization while the transmission load is equal or close to that of the schemes constructed by Shangguan et al. for the same number of users and memory size.
In the coded caching problem apart from transmission rate, reducing the number of packets <inline-formula> <tex-math notation="LaTeX">F </tex-math></inline-formula> ia also meaningful for practical ...implementation for coded caching scheme. Yan et al. reformulate the centralized coded caching schemes as designing a corresponding placement delivery array (PDA). In this letter, we propose two concatenating constructions by concatenating some known PDAs to obtain new PDAs therefore new code caching schemes with low sub-packetization level. Further, the comparison and analysis of parameters between our new schemes and known schemes is also performed.
In coded caching system we prefer to design a coded caching scheme with low subpacketization and small transmission rate (i.e., the low implementation complexity and the efficient transmission during ...the peak traffic times). Placement delivery arrays (PDA) can be used to design code caching schemes. In this article we propose a framework of constructing PDAs via Hamming distance. As an application, two classes of coded caching schemes with linear subpacketizations and small transmission rates are obtained.
This paper considers the multiaccess coded caching systems formulated by Hachem et al. , including a central server containing <inline-formula> <tex-math notation="LaTeX">N ...</tex-math></inline-formula> files connected to <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula> cache-less users through an error-free shared link, and <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula> cache-nodes, each equipped with a cache memory size of <inline-formula> <tex-math notation="LaTeX">M </tex-math></inline-formula> files. Each user has access to <inline-formula> <tex-math notation="LaTeX">L </tex-math></inline-formula> neighbouring cache-nodes with a cyclic wrap-around topology. The coded caching scheme proposed by Hachem et al. suffers from the case that <inline-formula> <tex-math notation="LaTeX">L </tex-math></inline-formula> does not divide <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula>, where the needed number of transmissions (a.k.a. load) is at most four times the load expression for the case where <inline-formula> <tex-math notation="LaTeX">L </tex-math></inline-formula> divides <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula>. Our main contribution is to propose a novel transformation approach to smartly extend the schemes satisfying some conditions for the well known shared-link caching systems to the multiaccess caching systems. Then we can get many coded caching schemes with different subpacketizations for multiaccess coded caching system. These resulting schemes have the maximum local caching gain (i.e., the cached contents stored at any <inline-formula> <tex-math notation="LaTeX">L </tex-math></inline-formula> neighbouring cache-nodes are different such that the number of retrieval packets by each user from the connected cache-nodes is maximal) and the same coded caching gain as the original schemes. Applying the transformation approach to the well-known shared-link coded caching scheme proposed by Maddah-Ali and Niesen, we obtain a new multiaccess coded caching scheme that achieves the same load as the scheme of Hachem et al. but for any system parameters. Under the constraint of the cache placement used in this new multiaccess coded caching scheme, our delivery strategy is approximately optimal when <inline-formula> <tex-math notation="LaTeX">K </tex-math></inline-formula> is sufficiently large. Finally, we also show that the transmission load of the proposed scheme can be further reduced by compressing the multicast message.
In coded caching system, we prefer to design a scheme with the rate R and the packet number F of each file split as small as possible since the efficiency of transmission in the peak traffic times ...increases with the decreasing of R and the realizing complexity increases with the increasing of F. Up to now, almost all of the previously known schemes can be realized by the combinatorial structure which is called placement delivery array (PDA). In this paper, we also study the schemes by means of PDAs. We first show that given the minimum rate, the scheme proposed by Maddah-Ali and Niesen (MN scheme) has the minimum packet number which is too large in practice. From the view point of combinatorial design, two variant MN schemes, which can significantly reduce the packet number by increasing some rate, are obtained. Especially one of these schemes has better performance than the scheme generated by the well known grouping method.
PDF
