TY - JOUR

T1 - Linear Coded Caching Scheme for Centralized Networks

AU - Cheng, Minquan

AU - Li, Jie

AU - Tang, Xiaohu

AU - Wei, Ruizhong

PY - 2021/3

Y1 - 2021/3

N2 - Coded caching systems have been widely studied to reduce the data transmission during the peak traffic time. In practice, two important parameters of a coded caching system should be considered, i.e., the transmission rate which is the maximum amount of the data transmission during the peak traffic time, and the subpacketization level, the number of divided packets of each file when we implement a coded caching scheme. Although there exists a tradeoff between transmission rate and subpacketization, we prefer to design a scheme with transmission rate and subpacketization as small as possible since they reflect the transmission efficiency and complexity of the caching scheme, respectively. In this paper, we first characterize a coded caching scheme from the viewpoint of linear algebra and show that designing a linear coded caching scheme is equivalent to constructing three classes of matrices satisfying some rank conditions. Then based on the invariant subspaces in linear algebra and combinatorial design theory, a new class of coded caching schemes over F2 is obtained by constructing these three classes of matrices. It turns out that the transmission rate of our new scheme is the same as the scheme construct by Yan et al. (IEEE Trans. Inf. Theory 63, 5821-5833, 2017), but the subpacketization is significantly reduced. Finally by means of these matrices, we show that the minimum storage regenerating codes can also be used to construct coded caching schemes.

AB - Coded caching systems have been widely studied to reduce the data transmission during the peak traffic time. In practice, two important parameters of a coded caching system should be considered, i.e., the transmission rate which is the maximum amount of the data transmission during the peak traffic time, and the subpacketization level, the number of divided packets of each file when we implement a coded caching scheme. Although there exists a tradeoff between transmission rate and subpacketization, we prefer to design a scheme with transmission rate and subpacketization as small as possible since they reflect the transmission efficiency and complexity of the caching scheme, respectively. In this paper, we first characterize a coded caching scheme from the viewpoint of linear algebra and show that designing a linear coded caching scheme is equivalent to constructing three classes of matrices satisfying some rank conditions. Then based on the invariant subspaces in linear algebra and combinatorial design theory, a new class of coded caching schemes over F2 is obtained by constructing these three classes of matrices. It turns out that the transmission rate of our new scheme is the same as the scheme construct by Yan et al. (IEEE Trans. Inf. Theory 63, 5821-5833, 2017), but the subpacketization is significantly reduced. Finally by means of these matrices, we show that the minimum storage regenerating codes can also be used to construct coded caching schemes.

KW - Complexity theory

KW - Decoding

KW - Encoding

KW - Handheld computers

KW - Linear algebra

KW - Linear coded caching scheme

KW - Manganese

KW - matrices

KW - Servers

KW - subpacketization

KW - transmission rate

UR - http://www.scopus.com/inward/record.url?scp=85099233304&partnerID=8YFLogxK

U2 - 10.1109/TIT.2020.3049074

DO - 10.1109/TIT.2020.3049074

M3 - Article

AN - SCOPUS:85099233304

VL - 67

SP - 1732

EP - 1742

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 3

M1 - 9312631

ER -