Optimal Binary Linear Complementary Pairs of Codes

Date

2022-11-01

Author

Choi, Whan-Hyuk
GÜNERİ, CEM
Kim, Jon-Lark
Özbudak, Ferruh

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

114
views

0
downloads

A pair of linear codes (C, D) of length n over F-q is called a linear complementary pair (LCP) if their direct sum yields the full space F-q(n). By a result of Carlet et al. (2019), the best security parameters of binary LCPs of codes are left open. Motivated by this, we study binary LCPs of codes. We describe a sufficient condition for binary LCPs of codes which are not optimal. We carry out an exhaustive search to determine the best security parameters for binary LCPs of codes up to length 18. We also obtain results on optimal binary LCPs of codes for infinitely many parameters. For any k >= 2 and length n congruent to 0 or 1 mod (2(k) - 1), we prove that binary [n, k] LCPs of codes are optimal. Binary LCPs of codes of dimensions 2, 3, and 4 are also optimal for all lengths except for two instances, when (n, k) = (4, 3) and (8, 4). We provide explicit constructions of these infinite families of optimal LCPs. Our results also indicate that many security parameters coming from binary LCPs of codes exceed those from binary LCD codes by 1 or 2.

Subject Keywords

Griesmer bound, Linear complementary pair, Optimal code, Simplex code

URI

https://hdl.handle.net/11511/101740

Journal

CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES

DOI

https://doi.org/10.1007/s12095-022-00612-4

Collections

Department of Mathematics, Article

Suggestions

OpenMETU
Core

A Bound on the Minimum Distance of Quasi-cyclic Codes Gueneri, Cem; Özbudak, Ferruh (2012-01-01) We give a general lower bound for the minimum distance of q-ary quasi-cyclic codes of length ml and index l, where m is relatively prime to q. The bound involves the minimum distances of constituent codes of length l as well as the minimum distances of certain cyclic codes of length m which are related to the fields over which the constituents are defined. We present examples which show that the bound is sharp in many instances. We also compare the performance of our bound against the bounds of Lally and Es...
Belief propagation decoding of polar codes under factor graph permutations Peker, Ahmet Gökhan; Yücel, Melek Diker; Department of Electrical and Electronics Engineering (2018) Polar codes, introduced by Arıkan, are linear block codes that can achieve the capacity of symmetric binary-input discrete memoryless channels with low encoding and decoding complexity. Polar codes of block length N are constructed by channel polarization method, which consists of channel combining and splitting operations to obtain N polarized subchannels from N copies of binary-input discrete memoryless channels. As N grows, symmetric channel capacities of the polarized subchannels converge to either 0 or...
Factorization of Joint Probability Mass Functions into Parity Check Interactions Bayramoglu, Muhammet Fatih; Yılmaz, Ali Özgür (2009-07-03) We show that any joint probability mass function (PMF) can be expressed as a product of parity check factors an d factors of degree one with the help of some auxiliary variables, if the alphabet size is appropriate for defining a parity chec k equation. In other words, marginalization of a joint PMF is equivalent to a soft decoding task as long as a finite field can be constructed over the alphabet of the PMF. In factor graph terminology this claim means that a factor graph representing such a joint PMF alw...
Valid Inequalities for the Maximal Matching Polytope Tural, Mustafa Kemal (2019-12-01) Given a graph G=(V,E), a subset M of E is called a matching if no two edges in M are adjacent. A matching is said to be maximal if it is not a proper subset of any other matching. The maximal matching polytope associated with graph G is the convex hull of the incidence vectors of maximal matchings in G. In this paper, we introduce new classes of valid inequalities for the maximal matching polytope.
LCD codes from tridiagonal Toeplitz matrices Shi, Minjia; Özbudak, Ferruh; Xu, Li; Solé, Patrick (2021-10-01) Double Toeplitz (DT) codes are codes with a generator matrix of the form (I,T) with T a Toeplitz matrix, that is to say constant on the diagonals parallel to the main. When T is tridiagonal and symmetric we determine its spectrum explicitly by using Dickson polynomials, and deduce from there conditions for the code to be LCD. Using a special concatenation process, we construct optimal or quasi-optimal examples of binary and ternary LCD codes from DT codes over extension fields.

Citation Formats

W.-H. Choi, C. GÜNERİ, J.-L. Kim, and F. Özbudak, “Optimal Binary Linear Complementary Pairs of Codes,” CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES, pp. 0–0, 2022, Accessed: 00, 2023. [Online]. Available: https://hdl.handle.net/11511/101740.