data storage architects

Abstract: The sequence reconstruction problem for $q$-ary deletion channels, introduced by Levenshtein in 2001, concerns the minimum number of channels required to uniquely recover a transmitted sequence when each channel introduces exactly $t$ deletions. Combinatorially, it is equivalent to determining $N_q(n,d,t)$, the maximum intersection size of two $t$-deletion balls with centers at Levenshtein distance at least $d$, for $q$-ary sequences of length $n$ over the alphabet \(Σ_q=\{0,1,\dots,q-1\}\). Levenshtein solved the uncoded case $N_q(n,1,t)$ for all $n\ge t$; subsequently, Gabrys and Yaakobi determined $N_2(n,2,t)$, and Wang et al. extended the result to $N_3(n,2,t)$. In this paper, we study the problem for \(q\)-ary sequences under minimum Levenshtein distance \(d=2\) with channels that introduce exactly \(t\) deletions. We determine the exact value of \(N_q(n,2,t)\) for all \(t\ge 2, q\geq 4\), and for sufficiently large \(n\), and construct explicit pairs of sequences attaining the maximum intersection. Furthermore, for each $q\ge3$, we characterize all extremal sequence pairs. In particular, if the intersection size matches the first two terms of \(N_q(n,2,t)\), then the two center sequences must contain, at the same positions, length-5 blocks of the forms \((a,b,c,a,b)\) and \((b,a,c,b,a)\) for some distinct \(a,b,c\inΣ_q\); for \(t\ge q+2\), the exact maximum \(N_q(n,2,t)\) is attained precisely by \(2q!\) unordered pairs of sequences with a specific block structure. Asymptotically, we prove that for \(q\ge 4\) and \(t\ge 2\), \[ N_q(n,2,t)=\frac{6}{(t-2)!}n^{t-2}-\frac{3t+13}{(t-3)!}n^{t-3}+\frac{3t^2+25t+64}{4(t-4)!}n^{t-4}+O(n^{t-5}). \] Moreover, \(N_q(n,2,t)\) and \(N_{q-1}(n,2,t)\) share their first \(q-1\) terms, and for \(t\ge q\) the coefficient of \(n^{t-q}\) in their difference is \(\frac{6t-6q+5}{(t-q)!}\).

Abstract: The minimum distance and the covering radius are two fundamental properties of the code. Both have been extended: the former to the generalized Hamming weights hierarchy, and the latter to the generalized covering radii hierarchy. In both cases, the lowest level of the hierarchies corresponds to the classical minimum distance and covering radius, respectively. From a geometric point of view, the minimum distance of the code determines the packing radius, which is upper bounded by the covering radius. It was conjectured this relation extends to all other orders of the hierarchy, namely, that the generalized packing radii are upper bounded by the generalized covering radii of the same order. In this paper we prove this conjecture is true for the second order radii. We also prove the conjecture holds for all orders when the code rate is at most $3/5$. Finally, we show that for any code rate in $(0,1)$, for all sufficiently long codes the conjecture holds for all orders.