Permutation codes are extensively studied because of applications such as frequency-shift keying modulation for power line communication (PLC). In PLC channels with synchronization issues, the error propagation due to insertion/deletion errors blurs the boundaries of codewords, thus making the communication unreliable. Prior studies on regaining synchronization focused on scenarios where noise and errors distort permutation codewords that were consecutively transmitted. In this paper, we consider the case where the channel output is a two-dimensional array, which is a concatenation of distorted permutation matrices of the transmitted codewords. Firstly, we propose algorithms to achieve two tasks. The first is to predict the distance of subarrays of the channel output from all codewords, and the second is to predict the original transmitted codewords given the output matrices corresponding to these codewords. Secondly, we apply these algorithms in an extended version of Viterbi-like algorithms proposed by Cheng et al. to decode the outputs received from transmissions over PLC channels with synchronization issues. Finally, our simulations demonstrate that block error rates were significantly improved over implementations lacking neural network-based algorithms, regardless of noise and error types.

Recovery sets for vectors and subspaces are important in the construction of distributed storage system codes. These concepts are also interesting in their own right. In this paper, we consider the following very basic recovery question: what is the maximum number of possible pairwise disjoint recovery sets for each recovered element? The recovered elements in this work ared-dimensional subspaces of ak-dimensional vector space over$\mathbb {F}_{q}$. Each server stores one representative for each distinct one-dimensional subspace of thek-dimensional vector space, or equivalently a distinct point of PG$(k-1,q)$. As column vectors, the associated vectors of the stored one-dimensional subspaces form the generator matrix of the$[(q^{k} -1)/(q-1),k,q^{k-1}]$simplex code over$\mathbb {F}_{q}$. Lower bounds and upper bounds on the maximum number of such recovery sets are provided. It is shown that generally, these bounds are either tight or very close to being tight.

A multiset combinatorial batch code (MCBC) over vector space consists of a set of subspaces of$\mathbb{F}_{q}^{n}$, each corresponding to a server, such that requests consisting of$t$dimensional subspaces, can be retrieved from the servers. The code is said to be regular if all the subspaces in the code have the same dimension. The aim is to find the minimum number of total storage, and also the minimum number of servers in the regular case, fixing other parameters. In this paper, we provide bounds and constructions for this new class of batch codes.

The class of multiset combinatorial batch codes (MCBCs) was introduced by Zhang et al. (2018) as a generalization of combinatorial batch codes (CBCs), which are replication-based batch codes. The MCBCs allow multiple users to retrieve items in parallel in a distributed storage and a fundamental objective in this study is to determine the minimum total storage given certain requirements. We formulate linear programs so that the optimal solutions provide lower bounds on the total storage of MCBCs. Borrowing techniques from linear programming, we improve known lower bounds in some cases. Furthermore, for some parameters, we showed that these lower bounds are either tight or asymptotically tight by constructing the corresponding codes.

Recovery sets for vectors and subspaces are important in constructions of distributed storage system codes. These concepts are also interesting in their own right. In this paper we consider the following very basic recovery question: what is the maximum number of possible pairwise disjoint recovery sets if the recovered element is a d-dimensional subspace and the elements stored are the one-dimensional subspaces of an n-dimensional vector space over GF(q). Lower and upper bounds on the number of such recovery sets are provided. It is shown that generally these bounds are either tight or very close of being tight.

The class of multiset combinatorial batch codes (MCBCs) was introduced by Zhang et al. (2018) as a generalization of combinatorial batch codes (CBCs). MCBCs allow multiple users to retrieve items in parallel in a distributed storage system and a fundamental objective in this study is to determine the minimum total storage given certain requirements.We formulate an integer linear programming problem so that its optimal solution provides a lower bound of the total storage of MCBCs. Borrowing techniques from linear programming, we improve known lower bounds in some cases and also, determine the exact values for some parameters.

Private Information Retrieval (PIR) array codes were introduced by Fazeli et al. (2015) to reduce the storage overhead in designing PIR protocols. Blackburn and Etzion (2017) introduced the (virtual server) rate to quantify the storage overhead of the codes, and when s > 2 (here, 1/s is the proportion of the database storing in one server), they gave a general construction of PIR array codes with the highest rate known so far. In this paper, we generalize their construction and reduce the number of servers, while maintaining the rate. In order to give PIR array codes with significantly fewer servers, we also construct classes of codes with a smaller rate s/2s-1.

We demonstrate that certain Johnson-type bounds are asymptotically exact for a variety of classes of codes, namely, constant-composition codes, nonbinary constant-weight codes, group divisible codes, and multiply constant-weight codes. We achieve this via an application of the theory of decomposition of edge-colored digraphs.

Grassmannian codes are known to be useful in error correction for random network coding. Recently, they were used to prove that vector network codes outperform scalar linear network codes, on multicast networks, with respect to the alphabet size. The multicast networks which were used for this purpose are generalized combination networks. In both the scalar and the vector network coding solutions, the subspace distance is used as the distance measure for the codes which solve the network coding problem in the generalized combination networks. In this paper, we show that the subspace distance can be replaced with two other possible distance measures which generalize the subspace distance. These two distance measures are shown to be equivalent under an orthogonal transformation. It is proved that the Grassmannian codes with the new distance measures generalize the Grassmannian codes with the subspace distance and the subspace designs with the strength of the design. Furthermore, optimal Grassmannian codes with the new distance measures have minimal requirements for the network coding solutions of some generalized combination networks. The coding problems related to these two distance measures, especially with respect to network coding, are discussed. Finally, by using these new concepts, it is proved that the codes in the Hamming scheme form a subfamily of the Grassmannian codes.

Subspace codes are known to be useful in error-correction for random network coding. Recently, they were used to prove that vector network codes outperform scalar linear network codes, on multicast networks, with respect to the alphabet size. In both cases, the subspace distance is used as the distance measure. In this work we show that we can replace the subspace distance with two other possible distance measures which generalize the subspace distance. We prove that each code with the largest number of codewords and the generalized distance, given the other parameters, has the minimum requirements needed to solve a given multicast network with a scalar linear code. We discuss lower and upper bounds on the sizes of the related codes.

Batch codes, first introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai, mimic a distributed storage of a set of n data items on m servers, in such a way that any batch of k data items can be retrieved by reading at most some t symbols from each server. Combinatorial batch codes, are replication-based batch codes in which each server stores a subset of the data items. In this paper, we propose a generalization of combinatorial batch codes, called multiset combinatorial batch codes (MCBCs), in which n data items are stored in m servers, such that any multiset request of k items, where any item is requested at most r times, can be retrieved by reading at most t items from each server. The setup of this new family of codes is motivated by recent work on codes which enable high availability and parallel reads in distributed storage systems. The main problem under this paradigm is to minimize the number of items stored in the servers, given the values of n, m, k, r, t, which is denoted by N(n, k, m, t; r). We first give a necessary and sufficient condition for the existence of MCBCs. Then, we present several bounds on N(n, k, m, t; r) and constructions of MCBCs. In particular, we determine the value of N(n, k, m, 1; r) for any n ≥ ⌊k - 1/r⌋ (k-1m) - (m - k + 1)A(m, 4, k - 2), where A(m, 4, k - 2) is the maximum size of a binary constant weight code of length m, distance four and weight k - 2. We also determine the exact value of N(n, k, m, 1; r) when r ϵ {k, k - 1} or k = m.

Multiply constant-weight codes (MCWCs) have been recently studied to improve the reliability of certain physically unclonable function response. In this paper, we give combinatorial constructions for the MCWCs, which yield several new infinite families of optimal MCWCs. Furthermore, we demonstrate that the Johnson-type upper bounds of the MCWCs are asymptotically tight for fixed Hamming weights and distances. Finally, we provide bounds and constructions of the 2-D MCWCs.

Multiport switches are commonly used as data processing and routing devices in computer networks. A network switch routes data packets between its multiple input and output ports. Packets from input ports are stored upon arrival in a switch fabric comprising multiple memory banks. This can lead to memory contention when distinct output ports request packets from the same memory bank, resulting in a degraded switching bandwidth. To solve this problem, switch codes are introduced by Wang et al. [1] as a tradeoff between redundancy and service. Using techniques from combinatorial design theory, we improve their result on switch codes serving any one-burst request to a denser set of parameters. New constructions for switch codes serving repetition limited request and consecutive-generation request are also given.

The study of Armstrong codes is motivated by the problem of understanding complexities of dependences in relational database systems, where attributes have bounded domains. A (q, k, n)-Armstrong code is a q-ary code of length n with minimum Hamming distance n - k + 1, and for any set of k - 1 coordinates, there exist two codewords that agree exactly there. Let f (q, k) be the maximum n for which such a code exists. In this paper, f (q, 3) = 3q -1 is determined for all q ≥ 5 with three possible exceptions. This disproves a conjecture of Sali. Furthermore, we introduce generalized Armstrong codes for branching, or (s, t)-dependences, construct several classes of optimal Armstrong codes, and establish lower bounds for the maximum length n in this more general setting.

We demonstrate that certain Johnson-type bounds are asymptotically exact for a variety of classes of codes, namely, constant-composition codes, nonbinary constant-weight codes and multiply constant-weight codes. This was achieved via an interesting application of the theory of decomposition of edge-colored digraphs.

The study of Armstrong codes is motivated by the problem of understanding complexities of dependencies in relational database systems, where attributes have bounded domains. A (q, k, n)-Armstrong code is a q-ary code of length n with minimum Hamming distance n - k + 1, and for any set of k - 1 coordinates there exist two codewords that agree exactly there. Let f(q, k) be the maximum n for which such a code exists. In this paper, f(q, 3) = 3q - 1 is determined for all q ≥ 5 with three possible exceptions. This disproves a conjecture of Sali. Further, we introduce generalized Armstrong codes for branching, or (s, t)-dependencies and construct several classes of optimal Armstrong codes in this more general setting.

Coding in a new metric space, the Enomoto-Katona space, is considered recently in connection to the study of implication structures of functional dependencies and their generalizations in relational databases. The central problem here is the determination of C(n, k, d), the size of an optimal code of length n, weight k, and distance d in the Enomoto-Katona space. The value of C(n, k, d) is known only for some congruence classes of n when (k, d) ∈ {(2, 3), (3, 5)}. In this paper, we obtain new infinite families of optimal codes in the Enomoto-Katona space. In particular, C(n, k, 2k-1) is determined for all sufficiently large n satisfying either n ≡ 1 mod k and n(n-1) ≡ 0 mod 2k2, or n ≡ 0 mod k.

Constant-weight codes play an important role in coding theory. The problem of determining the sizes for optimal quaternary constant-weight codes with length$n$, weight 4, and minimum Hamming distance 5 ($(n,5,4)_{4}$codes) has been investigated in several papers. Although some constructions and several infinite families for such codes with length$n\equiv 0,1\pmod4$have been given, the problem is still far from complete. In this paper, we determine the size of an optimal$(n,5,4)_{4}$code for each integer$n\geq 4$leaving 55 lengths unsolved. Especially, for length$n\equiv 0,1\pmod 4$, the existence problem of the equivalent combinatorial object, namely the generalized Steiner system, is solved leaving only seven values undetermined.

Constant-weight codes (CWCs) play an important role in coding theory. The problem of determining the sizes for optimal ternary CWCs with length$n$, weight 4, and minimum Hamming distance 5 ($(n,5,4)_{3}$code) has been settled for all positive integers$n\leq 10$or$n > 10$and$n\equiv 1\pmod {3}$with$n\in \{13,52,58\}$undetermined. In this paper, we investigate the problem of constructing optimal$(n,5,4)_{3}$codes for all lengths$n$with the tool of group divisible codes. We determine the size of an optimal$(n,5,4)_{3}$code for each integer$n\geq 4$leaving the lengths$n\in \{12,13,21,27,33,39,45,52\}$unsolved.

Recently, Chee and Ling (“Constructions for$q$-ary constant-weight codes”,IEEE Trans. Inf. Theory, vol. 53, no. 1, 135–146, Jan. 2007 ) introduced a new combinatorial construction for$q$-ary constant-weight codes which reveals a close connection between$q$-ary constant-weight codes and sets of pairwise disjoint combinatorial designs. In this paper, we study the problem of constructing optimal ternary constant-weight codes with Hamming weight four and minimum distance six using this approach. The construction here exploits completely reducible super simple designs and group divisible codes. The problem is solved leaving only two cases undetermined. Previously, the sizes of constant-weight codes of weight four and distance six were known only for those of length no greater than 10.