This paper presents a novel construction method for symmetric Sudoku-type games based on Lee distance perfect codes and diameter perfect codes. The proposed method utilizes the tiling property of these codes to define the structure of the subgrid constraints of Sudoku-type games. In this way, our games inherit the symmetric properties of Sudoku. We provide a detailed analysis of two small cases: a$5 \times 5$Sudoku in$\mathbb {Z}_{5}^{2}$, and an$8 \times 8$Sudoku in$\mathbb {Z}_{8}^{2}$. By defining equivalence relations via rigid motions, we provide a complete enumeration of valid grids, identifying 17 inequivalent solutions for$5\times 5$Sudoku. For two different types of$8\times 8$Sudoku, we characterize 232,735 and 304,014 inequivalent solutions, respectively. Furthermore, to verify practical playability, we implement a human-like solver that assesses the difficulty of the generated games. The analysis confirms that our$5\times 5$Sudoku games offer a balanced distribution of difficulty levels, ranging from Easy to Hard, making them a viable alternative to traditional$9 \times 9$Sudoku.

In this article, we introduce a genetic algorithm-based upper confidence bound (GA-UCB), an innovative hybrid genetic algorithm integrating multiarmed bandit. It effectively addresses the challenges of solving large and intricateSudokupuzzles, thus overcoming the constraints of traditional genetic algorithms. In GA-UCB, reinforcement learning is applied to simulate parent selection and crossover. By learning the optimal parent selection within a given population, the population evolves. Based on this technology, GA-UCB demonstrates improved results in solving complexSudokupuzzles. GA-UCB is compared with several state-of-the-art algorithms onSudokupuzzles of different difficulty levels and shows a 55% improvement in convergence speed compared to previous research results, particularly in the most challenging instance among the sixSudokupuzzle instances tested.

We introduce the notion of logarithmically concave (or log-concave) sequences in coding theory. A sequencea0,a1, . . . ,anof real numbers is called log-concave ifa2i⩾ai−1ai+1for all 1 ⩽i⩽n− 1. A natural sequence of positive numbers in coding theory is the weight distribution of a linear code consisting of the nonzero values among Ai’s where Ai denotes the number of codewords of weighti. We call a linear code log-concave if its nonzero weight distribution is log-concave. Our main contribution is to show that all binary general Hamming codes of length 2r−1 (r= 3 orr⩾ 5), the binary extended Hamming codes of length 2r(r⩾ 3), and the second order Reed-Muller codesR(2,m) (m⩾ 2) are all log-concave while the homogeneous and projective second order Reed-Muller codes are either log-concave, or 1-gap log-concave. Furthermore, we show that any MDS [n, k] code over Fqsatisfying 3 ⩽k⩽n/2 + 3 is log-concave ifq⩾q0(n, k) which is the larger root of a quadratic polynomial. We also show that most of QR codes, BCH codes and Roth-Lempel NMDS codes are not log-concave. Hence, we expect that the concept of log-concavity in coding theory will stimulate many interesting problems.

The purpose of this paper is to solve the two conjectures on the largest minimum distance$d_{so}(n,5)$of a binary self-orthogonal$[n, 5]$code proposed by Kim and Choi (2022). The determination of$d_{so}(n,k)$has been a fundamental and difficult problem in coding theory because there are too many binary self-orthogonal codes as the dimension$k$increases. Recently, Kim et al. (2021) considered the shortest self-orthogonal embedding of a binary linear code, and many binary optimal self-orthogonal$[n,k]$codes were constructed for$k=4,5$. Kim and Choi (2022) improved some results of Kim et al. (2021) and made two conjectures on$d_{so}(n,5)$. In this paper, we develop a general method to determine the exact value of$d_{so}(n,k)$for$k=5,6$and show that the two conjectures made by Kim and Choi (2022) are true.

Kim et al. (2021) gave a method to embed a given binary$[n,k]$code$\mathcal {C}\,\,(k = 3, 4)$into a self-orthogonal code of the shortest length which has the same dimension$k$and minimum distance$d' \ge d(\mathcal {C})$. We extend this result by proposing a new method related to a special matrix, called the self-orthogonality matrix$SO_{k}$, obtained by shortening a Reed-Muller code${\mathcal R}(2,k)$. Using this approach, we can extend binary linear codes to many optimal self-orthogonal codes of dimensions 5 and 6. Furthermore, we partially disprove the conjecture (Kim et al. (2021)) by showing that if$31 \le n \le 256$and$n\equiv 14,22,29 \pmod {31}$, then there exist optimal$[n], [5]$codes which are self-orthogonal. We also construct optimal self-orthogonal$[n], [6]$codes when$41 \le n \le 256$satisfies$n \ne 46, 54, 61$and$n \equiv \!\!\!\!\!/~7, 14, 22, 29, 38, 45, 53, 60 \pmod {63}$.

We obtain a characterization on self-orthogonality for a given binary linear code in terms of the number of column vectors in its generator matrix, which extends the result of Bouyukliev et al. (2006). As an application, we give an algorithmic method to embed a given binary k-dimensional linear codeC( k = 3,4) into a self-orthogonal code of the shortest length which has the same dimension k and minimum distance d' ≥ d(C). For k > 4, we suggest a recursive method to embed a k-dimensional linear code to a self-orthogonal code. We also give new explicit formulas for the minimum distances of optimal self-orthogonal codes for any length n with dimension 4 and any length n \not ≡ 6, 13,14,21,22,28,29 (mod 31) with dimension 5.

We introduce complementary information set codes of higher order. A binary linear code of length tk and dimension k is called a complementary information set code of order t (t-CIS code for short) if it has t pairwise disjoint information sets. The duals of such codes permit to reduce the cost of masking cryptographic algorithms against side-channel attacks. As in the case of codes for error correction, given the length and the dimension of a t-CIS code, we look for the highest possible minimum distance. In this paper, this new class of codes is investigated. The existence of good long CIS codes of order 3 is derived by a counting argument. General constructions based on cyclic and quasi-cyclic codes and on the building up construction are given. A formula similar to a mass formula is given. A classification of 3-CIS codes of length ≤ 12 is given. Nonlinear codes better than linear codes are derived by taking binary images of Z4-codes. A general algorithm based on Edmonds' basis packing algorithm from matroid theory is developed with the following property: given a binary linear code of rate 1/t, it either provides t disjoint information sets or proves that the code is not t-CIS. Using this algorithm, all optimal or best known [tk, k] codes, where t = 3, 4, . . . , 256 and 1≤ k ≤⌊256/t⌋ are shown to be t-CIS for all such k and t, except for t = 3 with k = 44 and t = 4 with k = 37.

We introduce the class of multiply constant-weight codes to improve the reliability of certain physically unclonable function response, and extend classical coding methods to construct multiply constant-weight codes from known \(q\) -ary and constant-weight codes. We derive analogs of Johnson bounds and give constructions showing these bounds to be asymptotically tight up to a constant factor under certain conditions. We also examine the rates of multiply constant-weight codes and demonstrate that these rates are the same as those of constant-weight codes of corresponding parameters.

The function M(m, n, d, w), the largest size of an unrestricted binary code made of m by n arrays, with constant row weight w, and minimum distance d is introduced and compared to the classical functions of combinatorial coding theory Aq(n, d) and A(n, d, w). The analogues for systematic codes of A(n, d) and A(n, d, w) are introduced apparently for the first time. An application to the security of embedded systems is given: these codes happen to be efficient challenges for physically unclonable functions.

We introduce a new class of rate one-half binary codes: complementary information set codes. A binary linear code of length$2n$and dimension$n$is called a complementary information set code (CIS code for short) if it has two disjoint information sets. This class of codes contains self-dual codes as a subclass. It is connected to graph correlation immune vectorial Boolean functions of use in the security of hardware implementations of cryptographic primitives. Such codes permit to improve the cost of masking cryptographic algorithms against side channel attacks. In this paper, we investigate this new class of codes: we give optimal or best known CIS codes of length$ < 132$. We derive general constructions based on cyclic codes and on double circulant codes. We derive a Varshamov–Gilbert bound for long CIS codes, and show that they can all be classified in small lengths$\leq 12$by the building up construction. Some nonlinear permutations are constructed by using${\BBZ}_{4}$-codes, based on the notion of dual distance of a possibly nonlinear code.

In this paper we classify all extremal and s-extremal binary self-dual codes of length 38. There are exactly 2744 extremal self-dual codes, two s-extremal codes, and 1730 s-extremal codes. We obtain our results from the use of a recursive algorithm used in the recent classification of all extremal self-dual codes of length 36, and from a generalization of this recursive algorithm for the shadow. The classification of -extremal codes permits to achieve the classification of all -extremal codes with .

The building-up construction for self-dual codes was developed by the authors over finite fields GF(q) when q is a power of 2 or q ¿ 1 (mod 4). In this paper, we complete the building-up construction for self-dual codes over GF(q) with q ¿ 3 (mod 4). For example, we construct new 945 extremal self-dual ternary [32, 16, 9] codes, each of which has a trivial automorphism group.

Skew Hadamard designs (4 n – 1, 2 n – 1, n – 1) are associated to order 4 n skew Hadamard matrices in the natural way. We study the codes spanned by their incidence matrices A and by I + A and show that they are self-dual after extension (resp. extension and augmentation) over fields of characteristic dividing n . Quadratic Residues codes are obtained in the case of the Paley matrix. Results on the p -rank of skew Hadamard designs are rederived in that way. Codes from skew Hadamard designs are classified. An optimal self-dual code over GF (5) is rediscovered in length 20. Six new inequivalent [56, 28, 16] self-dual codes over GF (7) are obtained from skew Hadamard matrices of order 56, improving the only known quadratic double circulant code of length 56 over GF (7).

We construct new MDS or near-MDS self-dual codes over large finite fields. In particular, we show that there exists a Euclidean self-dual MDS code of length n = q over GF(q) whenever q = 2m(m ges 2) using a Reed-Solomon (RS) code and its extension. It turns out that this multiple description source (MDS) self-dual code is an extended duadic code. We construct Euclidean self-dual near-MDS codes of length n = q-1 over GF(q) from RS codes when q = 1 (mod 4) and q les 113. We also construct many new MDS self-dual codes over GF(p) of length 16 for primes 29 les p les 113. Finally, we construct Euclidean/Hermitian self-dual MDS codes of lengths up to 14 over GF(q2) where q = 19, 23,25, 27, 29.

Our purpose is to find an upper bound for the length of ans-extremal code over F2(resp. F4) when d equiv 2 (mod 4) (resp. d odd). This question is left open in [A bound for certain s -extremal lattices and codes, Archiv der Mathematik, vol. 89, no. 2, pp. 143-151, 2007] (resp. [s-extremal additive F4codes, Advances in Mathematics of Communications, vol. 1, no. 1, pp. 111-130,2007]). More precisely, we show that if there is an [n, n/2, d]s-extremal Type I binary self-dual code with d > 6 and d equiv 2 (mod 4), then n1 and d, equiv 1 (mod 2), then n2+ uF2and derive an upper bound for the length of an .s-extremal self-dual code over F2+ uF2using the information on binarys-extremal codes.

Recently Bachoc and Gaborit introduced the notion of s-extremality for binary self-dual codes, generalizing Elkies' study on the highest possible minimum weight of the shadows of binary self-dual codes. In this paper, we introduce a concept of s-extremality for additive self-dual codes over F4, give a bound on the length of these codes with even distance d, classify them up to minimum distance d = 4, give possible lengths (only strongly conjectured for odd d) for which there exist s-extremal codes with 5 ≤ d ≤ 11, and give five s-extremal codes with d = 7 as well as four new s-extremal codes with d = 5. We also describe codes related to s-extremal codes.

In this paper we develop a complete generalization of the building-up method [J.-L. Kim, (2001)] for the Euclidean and Hermitian self-dual codes over finite fields GF(q). Using this method we construct many new Euclidean and Hermitian self-dual MDS (or near MDS) codes of length up to 12 over various finite fields GF(q), where q=8, 9, 16, 25, 32, 41, 49, 53, 64, 81, and 128.

LDPC codes are serious contenders to turbo codes in terms of decoding performance. One of the main problems is to give an explicit construction of such codes whose Tanner graphs have known girth. For a prime power q and m/spl ges/2, Lazebnik and Ustimenko construct a q-regular bipartite graph D(m,q) on 2q/sup m/ vertices, which has girth at least 2/spl lceil/m/2/spl lfloor/+4. We regard these graphs as Tanner graphs of binary codes LU(m,q). We can determine the dimension and minimum weight of LU(2,q), and show that the weight of its minimum stopping set is at least q+2 for q odd and exactly q+2 for q even. We know that D(2,q) has girth 6 and diameter 4, whereas D(3,q) has girth 8 and diameter 6. We prove that for an odd prime p, LU(3,p) is a [p/sup 3/,k] code with k/spl ges/(p/sup 3/-2p/sup 2/+3p-2)/2. We show that the minimum weight and the weight of the minimum stopping set of LU(3,q) are at least 2q and they are exactly 2q for many LU(3,q) codes. We find some interesting LDPC codes by our partial row construction.

It is well known that the problem of finding stabilizer quantum-error-correcting codes (QECC) is transformed into the problem of finding additive self-orthogonal codes over the Galois field GF(4) under a trace inner product. Our purpose is to classify the extremal additive circulant self-dual codes of lengths up to 15, and construct good codes for lengths 16/spl les/n/spl les/27. We also classify the extremal additive 4-circulant self-dual codes of lengths 4,6,8,12,14, and 16 and most codes of length 10, and construct good codes of even lengths up to 22. Furthermore, we classify the extremal additive bordered 4-circulant self-dual codes of lengths 3,5,7,9,11,13,15, and 17, and construct good codes for lengths 19,21,23, and 25. We give the current status of known extremal (or optimal) additive self-dual codes of lengths 12 to 27.

Low-density parity-check (LDPC) codes are serious contenders to turbo codes in terms of decoding performance. One of the main problems is to give an explicit construction of such codes whose Tanner graphs have known girth. For a prime power q and m/spl ges/2, Lazebnik and Ustimenko construct a q-regular bipartite graph D(m,q) on 2q/sup m/ vertices, which has girth at least 2/spl lceil/m/2/spl rceil/+4. We regard these graphs as Tanner graphs of binary codes LU(m,q). We can determine the dimension and minimum weight of LU(2,q), and show that the weight of its minimum stopping set is at least q+2 for q odd and exactly q+2 for q even. We know that D(2,q) has girth 6 and diameter 4, whereas D(3,q) has girth 8 and diameter 6. We prove that for an odd prime p, LU(3,p) is a [p/sup 3/,k] code with k/spl ges/(p/sup 3/-2p/sup 2/+3p-2)/2. We show that the minimum weight and the weight of the minimum stopping set of LU(3,q) are at least 2q and they are exactly 2q for many LU(3,q) codes. We find some interesting LDPC codes by our partial row construction. We also give simulation results for some of our codes.

We study certain projections of binary linear codes onto larger fields. These projections include the well-known projection of the extended Golay [24,12,8] code onto the hexacode over $\mbox{GF}(4)$ and the projection of the Reed--Muller code R(2,5) onto the unique self-dual [8,4,4] code over $\mbox{GF}(4)$. We give acharacterization of these projections, and we construct several binary linear codes which have best known optimal parameters, for instance, [20,11,5], [40,22,8], [48,21,12], and [72,31,16]. We also relate the automorphism group of a quaternary code to that of the corresponding binary code.

We construct new extremal self-dual binary codes of lengths 36, 38, and 58. We show that there are at least 14 inequivalent extremal self-dual [38,18,8] codes and that there are at least 368 inequivalent extremal self-dual [38,19,8] codes. For length 58, we construct 11 extremal self-dual [58,29,10] codes whose weight enumerators were previously unknown.

The purpose of this correspondence is to construct new Hermitian self-dual codes over GF(4) of lengths 22, 24, 26, 32, and 34 which have the highest known minimum weights. In particular, for length 22, we construct eight new extremal self-dual [22,11,8] codes over GF(4) which do not have a nontrivial automorphism of odd order. The existence of such codes has been left open since 1991 by Huffman.