Welcome to Francis Academic Press

Academic Journal of Computing & Information Science, 2021, 4(7); doi: 10.25236/AJCIS.2021.040715.

Some New Constructions of Centralized Coded Caching Scheme


Fei Wang

Corresponding Author:
Fei Wang

School of Mathematical Sciences University of Science and Technology of China, Hefei, China


As an effective technique to reduce network congestion during peak traffic times, coded caching is being widely studied in wireless network. The coded caching scheme was first proposed by Maddah-Ali and Niesen in 2014. In the placement phase of off- peak times, each file is divided into F equal packets,and each user caches some packets of each file elaborately from the server. In the delivery phase of peak times, each user first requires a file from the server. And then according to each user’s cache, the server sends a coded signal with size at most R to users so that various user demands are satisfied.In order to study this problem better, the placement delivery array was defined by Yan Q et al. in 2016. And they found that the problem of designing a coded caching scheme can be converted into the problem of constructing an appropriate PDA.In this paper, we will construct three kinds of new PDAs based on t -design of k = t + 1 and the incidence matrix of a resolvable transversal design and the partitioning of the incidence matrix. Based on these PDAs, we present several new constructions of coded caching schemes, which have obvious advantages in packet number. The results of this paper enrich the constructions of coded caching schemes of low subpacketization level.


Placement delivery array, coded caching, t-design, transversal design

Cite This Paper

Fei Wang. Some New Constructions of Centralized Coded Caching Scheme. Academic Journal of Computing & Information Science (2021), Vol. 4, Issue 7: 101-111. https://doi.org/10.25236/AJCIS.2021.040715.


[1] Maganioti, A.E., Chrissanthi, H.D., Charalabos, P.C., Andreas, R.D., George, P.N. and Christos, C.N. (2010) Cointegration of Event-Related Potential (ERP) Signals in Experiments with Different Electromagnetic Field (EMF) Conditions. Health, 2, 400-406.

[2] Bootorabi, F., Haapasalo, J., Smith, E., Haapasalo, H. and Parkkila, S. (2011) Carbonic Anhydrase VII—A Potential Prognostic Marker in Gliomas. Health, 3, 6-12.

[3] Yan, Q, M. Wigger , and S. Yang . “Placement Delivery Array Design for Combination Networks with Edge Caching.” IEEE (2018).

[4] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” IEEE Transactions on Information Theory, vol. 60, no. 5, pp. 2856–2867, 2014.

[5] Yan Q , Cheng M , Tang X , et al. On the Placement Delivery Array Design in Centralized Coded Caching Scheme[J]. IEEE Transactions on Information Theory, 2017, 63(9):5821-5833.

[6] Yan Q, Tang X, Chen Q, et al. Placement delivery array design through strong edge coloring of bipartite graphs[J]. IEEE Commun. Lett., 2018, 22(2): 236-239.

[7] K. Shanmugam, M. Ji, A. M. Tulino, J. Llorca, and A. G. Dimakis, “Finite-length analysis of caching-aided coded multicasting,” IEEE Transactions on Information Theory, vol. 62, no. 10, pp. 5524-5537, Oct 2016.

[8] Cheng M , Jiang J , Yan Q , et al. Optimal Placement Delivery Arrays. 2017.

[9] Li Tang and Aditya Ramamoorthy, “Coded Caching Schemes With Re duced Subpacketization From Linear Block Codes,” IEEE Transactions on Information Theory. Theory, vol. 64, no. 4, pp. 3099-3120, Apr 2018.

[10] P. Krishnan, “Coded caching via line graphs of bipartite graphs,” in Proc. IEEE Information Theory Workshop (ITW),2018, pp. 1-5.

[11] C. Hari Hara Suthan, M. Bhavana, and P. Krishnan, “Coded caching via projective geometry: A new low subpacketization scheme,” in Proc. IEEE Int. Symp. Inform. Theory (ISIT), 2019, pp. 682-686.

[12] S. Agrawal, K. V. S. Sree, and P. Krishnan, “Coded Caching based on Combinatorial Designs,” in Proc. IEEE Int. Symp. Inform. Theory (ISIT), 2019, pp. 1227-1231.

[13] M. Cheng, J. Jiang, Q. Yan, and X. Tang, “Constructions of Coded Caching Schemes With Flexible Memory Size,” IEEE Trans. Communications, vol. 67, no. 6, pp. 4166-4176, Jun. 2019. 

[12] Cheng M, Yan Q, Tang X, et al. Coded caching schemes with low rate and subpacketizations[J]. 2017.

[14] D.R. Stison,Combinatorial Designs:Constructions and Analysis[M].Springer New York:2004-01-01.

[15] Wan Z X. Design Theory[M]. Beijing: Higher Educa.

[16] Teirlinck L. Non-trivial t-designs without repeated blocks exist for all t[J]. Discrete Math., 1987, 65(3): 301-311.