For a directed graphGwith edge set {1, 2, . . . ,k}, a feasible permutations forGis a permutation π on {1, 2, . . . ,k} such that there exists an injective weight functionp: {1, 2, . . . ,k} → Z+for which the sum of the weights of all incoming edges equals the sum of the weights of all outgoing edges at every vertex ofG, provided that ifp(i1)p(i2)p(ik), then π(it) =tfor everyt∈ {1, . . . ,k}. In this paper, we study the number of feasible permutations (denoted byFq,ℓ) for the De Bruijn graphGq,ℓ−1, whereq> 2 is the size of the alphabet. In the caseq= 4, the corresponding De Bruijn graph is used in DNA data storage. To enumerate these feasible permutations, we establish a connection between feasible permutations and regions in a special hyperplane arrangement, denoted byA. Using Zaslavsky’s formula, we present some numerical results and obtain the exact number ofF3,2andF4,2. Since the formula becomes complicated for larger values ofqand ℓ, we concentrate on the case ℓ = 2 and then by counting the regions in a hyperplane sub-arrangement ofA, we provide a lower bound onFq,2. We compare our bound with the latest lower bound onFq,2and show that our bound is Ω(q3J(q)) while the previous one is Ω(q2J(q)), whereJ(q)= (q2−2q+1)!(q2)!/(q2−q)!.

In order to overcome the challenges caused by flash memories and also to protect against errors related to reading information stored in DNA molecules in the shotgun sequencing method, the rank modulation method has been proposed. In the rank modulation framework, codewords are permutations. In this paper, we study the largest size P(n, d) of permutation codes of length n, i.e., subsets of the set Sn of all permutations on {1, ..., n} with the minimum distance at least d ∈ {1, ..., (n/2)} under the Kendall τ-metric. By presenting an algorithm and two theorems, we improve the known lower and upper bounds for P(n, d). In particular, we show that P(n, d) = 4 for all n ≥ 6 and 3/5 (n/2) < d ≤ 2/3 (n/2). Additionally, we prove that for any prime number n and integer r ≤ n/6, P(n, 3) ≤ (n − 1)! − n − 6r/√n2 − 8rn + 20r2 √(n − 1)!/n(n − r)!. This result greatly improves the upper bound of P(n, 3) for all primes n ≥ 37.

In this study, using Group Permutation Low‐Density Parity‐Check (GP‐LDPC) codes, the authors generalise the concept of array Low‐Density Parity‐Check (LDPC) codes from fields of prime order to those of prime power order. In fact, they consider the additive group of the finite field GF( q ), q a prime power, as the underlying group for the GP‐LDPC code construction and since when q is a prime, the author's code construction method coincides with that of quasi‐cyclic array LDPC codes, they call their codes, generalised array LDPC (GA‐LDPC) codes. First, they prove that, like array LDPC codes, GA‐LDPC codes are quasi‐cyclic codes. Then, they analyse the girth of GA‐LDPC codes in a way similar to that for array LDPC codes and introduce some shortened GA‐LDPC codes with girths 8, 10 and 12. For many values of g , J and L , the lengths of ( J , L )‐regular shortened GA‐LDPC codes of girth g and rate at least 1 − J / L , constructed in this study, are smaller than the lengths of ( J , L )‐regular LDPC codes of girth g and rate at least 1 − J / L , constructed in the literature. Also, simulation results show that GA‐LDPC codes perform well with the iterative message‐passing decoding.

In this study, a new method for constructing low-density parity-check (LDPC) codes is presented. This construction is based on permutation matrices which come from a finite abstract group and hence the codes constructed in this manner are called group permutation low-density parity-check (GP-LDPC) codes. A necessary and sufficient condition under which a GP-LDPC code has a cycle is given and some properties of these codes are investigated. A class of flexible-rate GP-LDPC codes without cycles of length four is also introduced. Simulation results show that GP-LDPC codes perform very well with the iterative decoding and can outperform their random-like counterparts.