The complete hierarchical locality of the punctured Simplex code
- PDF / 542,574 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 91 Downloads / 133 Views
The complete hierarchical locality of the punctured Simplex code Matthias Grezet1
· Camilla Hollanti1
Received: 13 March 2019 / Revised: 28 September 2020 / Accepted: 30 September 2020 © The Author(s) 2020
Abstract This paper presents a new alphabet-dependent bound for codes with hierarchical locality. Then, the complete list of possible localities is derived for a class of codes obtained by deleting specific columns from a Simplex code. This list is used to show that these codes are optimal codes with hierarchical locality. Keywords Hierarchical locality · Alphabet-dependent bound · Simplex code · Matroid theory Mathematics Subject Classification 94B65 · 94B60 · 05B35
1 Introduction In modern distributed storage systems (DSSs) failures happen frequently, whence decreasing the number of connections required for node repair is crucial. Locally repairable codes (LRCs) are a subclass of erasure-correcting codes, which allow a small number of failed nodes to be repaired by accessing only a few other nodes. LRCs were introduced in [6], [11] where the codes can locally repair one failure. They were later extended in [12], [8] to be able to repair more failures locally. An [n, k, d] linear code C of length n, dimension k, and minimum Hamming distance d, has all-symbol locality (r , δ) if for all code symbols i ∈ [n] = {1, . . . , n}, there exists a set Ri ⊆ [n] containing i such that |Ri | ≤ r + δ − 1 and the minimum distance of the restriction of C to Ri is at least δ. We refer to C as an (n, k, d, r , δ)-LRC and to the sets Ri as
Communicated by T. Etzion. Part of the results were submitted without any proofs to IEEE International Symposium Information Theory (ISIT) 2019.
B
Matthias Grezet [email protected] Camilla Hollanti [email protected]
1
Department of Mathematics and Systems Analysis, Aalto University, 00076 AALTO (Espoo), Finland
123
M. Grezet, C. Hollanti
repair sets or local sets. Related Singleton-type bounds have been derived for various cases in [6,11,12] and the first bound with a fixed code alphabet was obtained in [3] for δ = 2. Constructions achieving the Singleton-type bounds and the bound in [3] for δ = 2 were provided in [8,9,11–14,16–18,20]. The authors of [1] proposed the first alphabet-dependent bound on LRCs over an alphabet Q with |Q| = q using an upper bound B(n, d) on the cardinality of a code of length n and minimum distance d. The global bound is as follows: k≤
n−d +1 + 1 logq B(r + δ − 1, δ). r +δ−1
(1)
Recently, [7] provided a different alphabet-dependent bound of the same type k−1for LRCs d/q i . The bound has the as the bound in [3] using the Griesmer bound Gq (k, d) := i=0 following form : Any linear (n, k, d, r , δ)-LRC C with κ the upper bound on the dimension of the restriction of C to a repair set satisfies (q) k ≤ min λ + kopt (n − μ, d) λ∈Z+
(2)
where a, b ∈ Z such that λ = aκ + b, 0 ≤ b < κ and μ = (a + 1)Gq (κ, δ) − Gq (κ − b, δ). In [15], the authors introduced the notion of codes with hierarchical locality (H-LRCs), which optimizes
Data Loading...
