15 June 2018 in IEEE Transactions on Information Theory
The centralized coded caching scheme is a technique proposed by Maddah-Ali and Niesen as a method to reduce the network burden in peak times in a wireless network system. Yan et al. [IEEE Trans. Inform. Theory, vol. 63, no. 5, pp. 5821–5833, 2017] reformulate the problem as designing a corresponding placement delivery array and propose two new schemes from this perspective. These schemes significantly reduce the rate compared with the uncoded caching schemes. However, to implement these schemes, each file should be cut into F pieces, where F grows exponentially with the number of users K. Such constraint is obviously infeasible in the practical setting, especially when K is large. Thus it is desirable to design caching schemes with constant rate R (independent of K) as well as smaller F. In this paper we view the centralized coded caching problem in a hypergraph perspective and show that designing a feasible placement delivery array is equivalent to constructing a linear and (6,3)-free 3-uniform 3-partite hypergraph. Several new results and constructions arise from our novel point of view. First, by using the famous (6,3)-theorem in extremal graph theory, we show that constant rate placement delivery arrays with F growing linearly with K do not exist. Second, we present two infinite classes of placement delivery arrays to show that constant rate caching schemes with F growing sub-exponentially with K do exist.
5 July 2016 in Designs, Codes and Cryptography
19 August 2016 in Designs, Codes and Cryptography
24 August 2017 in IEEE Transactions on Information Theory
Cyclic codes are widely employed in communication systems, storage devices, and consumer electronics, as they have efficient encoding and decoding algorithms. BCH codes, as a special subclass of cyclic codes, are in most cases among the best cyclic codes. A subclass of good BCH codes are the narrow-sense BCH codes over GF(q) with length n = (q m -1)/(q -1). Little is known about this class of BCH codes when q > 2. The objective of this paper is to study some of the codes within this class. In particular, the dimension, the minimum distance, and the weight distribution of some ternary BCH codes with length n = (3 m - 1)/2 are determined in this paper. A class of ternary BCH codes meeting the Griesmer bound is identified. An application of some of the BCH codes in secret sharing is also investigated.
8 May 2017 in Designs, Codes and Cryptography
13 August 2004 in Journal of Combinatorial Designs