A New Construction Structure on MISO Coded Caching with Linear Subpacketization: Half-Sum Disjoint Packing
Bowen Zheng, Minquan Cheng, Kai Wan, Giuseppe Caire · 2026
Read A New Construction Structure on MISO Coded Caching with Linear Subpacketization: Half-Sum Disjoint Packing by Bowen Zheng, Minquan Cheng, Kai Wan, Giuseppe Caire (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-10353.txt.
Introduction
Bowen Zheng, Minquan Cheng, Kai Wan, and Giuseppe Caire cut the packet cost of cache fed broadcast. A server with many antennas sends files to many users. Each user holds a cache of past files. Smart cache use can cut the load on the air.
Past plans oft split files into a vast count of parts. That split cost is named subpacketization. It can grow too fast to run. The team give a new build with a lean split. It uses a half sum pack of parts that do not clash. The aim is the same gain at a far lower split cost.
Catalog record
| CREATOR | Bowen Zheng, Minquan Cheng, Kai Wan, Giuseppe Caire |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-10353
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A New Construction Structure on MISO Coded Caching with Linear Subpacketization: Half-Sum Disjoint Packing Bowen Zheng, Minquan Cheng, Kai Wan, Giuseppe Caire Abstract In the ( L , K , M , N ) (L,K,M,N) cache-aided multiple-input single-output (MISO) broadcast channel (BC) system, the server is equipped with L L antennas and communicates with K K single-antenna users through a wireless broadcast channel where the server has a library containing N N files, and each user is equipped with a cache of size M M files. Under the constraints of uncoded placement and one-shot linear delivery strategies, many schemes achieve the maximum sum Degree-of-Freedom (sum-DoF). However, for general parameters L L , M M , and N N , their subpacketizations increase exponentially with the number of users. We aim to design a MISO coded caching scheme that achieves a large sum-DoF with low subpacketization F F . An interesting combinatorial structure, called the multiple-antenna placement delivery array (MAPDA), can be used to generate MISO coded caching schemes under these two strategies; moreover, all existing schemes with these strategies can be represented by the corresponding MAPDAs. In this paper, we study the case with F = K F=K (i.e., F F grows linearly with K K ) by investigating MAPDAs. Specifically, based on the framework of Latin squares, we transform the design of MAPDA with F = K F=K into the construction of a combinatorial structure called the L L -half-sum disjoint packing (HSDP). It is worth noting that a 1 1 -HSDP is exactly the concept of NHSDP, which is used to generate the shared-link coded caching scheme with F = K F=K . By constructing L L -HSDPs, we obtain a class of new schemes with F = K F=K . Finally, theoretical and numerical analyses show that our L L -HSDP schemes significantly reduce subpacketization compared to existing schemes with exponential subpacketization, while only slightly sacrificing sum-DoF, and achieve both a higher sum-DoF and lower subpacketization than the existing schemes with linear subpacketization. I INTRODUCTION With the exponential growth of data traffic and the proliferation of mobile devices, modern communication networks face increasing pressure to cope with the rising demand for low-latency and high-throughput content delivery. In particular, the high temporal variability of network traffic leads to congestion during peak periods and underutilization during off-peak periods. Coded caching, originally proposed by Maddah-Ali and Niesen (MN) in [ MN ] , has emerged as a promising technique to address these challenges by effectively leveraging storage at the network edge and multicasting opportunities to improve transmission efficiency. The (K,M,N) MN coded caching problem was initially designed for the single-input single-output (SISO) shared-link network model, where a central server with N files connects to K cache-aided users through an error-free shared link 1 1 1 In this paper, we consider the case N\geq K . . Each user can store up to M files, where 0\leq M\leq N . An F -division (K,M,N) coded caching scheme consists of two phases: the placement phase and the delivery phase. In the placement phase, the server divides each file into F equal-size packets and places some packets into each user’s cache without knowing their future requests. If the packets are directly placed in each user’s cache, it is called uncoded placement. Otherwise it is called coded placement. The parameter F is referred to as the subpacketization. In the delivery phase, each user independently requests a file. Based on these demands and the cached packets for each user, the server sends some coded packets such that each user can decode its requested file with help of its cached packets. The transmission load (or load) R is the amount of transmission for the worst demand case of the users, normalized by the size of a single file. The coded caching gain of a coded caching scheme is defined as g=K(1-M/N)/R which represents the average number of users served by the server at each time slot, where K(1-M/N) denotes the transmission load of a conventional uncoded caching scheme. The objective to design a scheme with the load R as small as possible, i.e., the coded caching gain g is as large as possible. Maddah-Ali and Niesen in [ MN ] proposed the first well-known coded caching scheme, which is referred to as the MN scheme. When t=KM/N is an integer, the MN scheme achieves the load R=(K-t)/(t+1) , i.e., the coded caching gain g=t+1 . The authors in [ WTP ] showed that the load is optimal under uncoded placement when K\leq N . For arbitrary user demands, the authors in [ YMA ] derived the converse of the transmission load under uncoded placement and proposed an optimal scheme by eliminating the redundant multicast transmissions in the delivery phase of the MN scheme. So, the MN scheme has been widely used in the variety of network topologies, such as Device-to-Device (D2D) networks [ JCM ] , hierarchical networks [ KNMD ] , combination networks [ JWTLCEL ] , multi-server linear networks [ SMK ] , etc. However, the MN scheme has the subpacketization F=\binom{K}{t} which increases exponentially with the number of users K . There are many studies focusing on reducing the subpacketization by increasing the load, such as the placement delivery array (PDA) [ YCTC , CJYT , CJWY , CWZW , WCWC ] , projective geometry [ CKSM ] , hypergraphs [ SZG ] , Ruzsa-Szeméredi graphs [ STD ] , strong edge coloring of bipartite graphs [ YTCC ] , other combinatorial designs [ ASK ] . The authors in [ SZG ] pointed out that all the schemes in [ SZG , STD , YTCC , ASK ] can be represented by appropriate PDAs, indicating that PDAs are a powerful tool for characterizing coded caching schemes. However, a PDA is merely a combinatorial structure that characterizes the placement and delivery issue in shared-link network, and its definition does not provide explicit guidance for constructing coded caching schemes. To establish a framework for constructing PDAs with linear subpacketization, the authors in [ CWWC ] introduced a novel combinatorial structure, termed non-half-sum disjoint packing (NHSDP) which unifies placement and delivery strategies into a single condition. By constructing NHSDPs, a class of coded caching schemes with F=K was obtained, which achieves a lower or only slightly higher load compared to some existing schemes under some system parameters. I-A MISO Coded Caching The (K,M,N) MN coded caching problem was extended to the (L,K,M,N) cache-aided multiple-input single-output (MISO) broadcast channel (BC) in [ NMA ] where the server equipped with L antennas connects with K single-antenna users over a wireless broadcast channel. The objective of the MISO BC problem is to maximize the sum-DoF (i.e., the average number of users simultaneously served per transmission block) of the system. When L=1 , the sum-DoF is exactly the coded caching gain in the MN coded caching problem. Under the constraints of uncoded placement and one-shot 2 2 2 Each required data bit is transmitted exactly once in coded or uncoded form. zero-forcing (ZF) linear delivery strategies, various schemes achieving the sum-DoF \min\{L+t,K\} were proposed in [ NMA , SCK , LE , SPSET , MB , ST , STSK