CS Paper Radar

Construction of New Complete Complementary Codes Using Extended Boolean Functions and Permutations

Aditya Prakash, Rajen Kumar

cs.IT ·submitted 2026-11-03 12:31 UTC · v1

Abstract

Complete complementary code (CCC) is a crucial component in the design and optimization of modern wireless communication systems, particularly in addressing challenges related to interference, spectral efficiency, and signal quality. The design of CCCs is an active area of research, as it directly impacts the number of users that can be supported interference-free in the system. In the literature, CCC constructions are restricted by a set size smaller than the sequence length. In this paper, we introduce a novel construction method for CCCs based on the extended Boolean functions (EBF) that overcome existing restrictions by including a set size bigger than the sequence length. Further, the proposed construction uses functions which are new in literature and provide us with new CCCs. This is also the very first construction where row PMEPR is also bounded by $n$ for a set size in the form of power of $n$.

Closest papers

Nearest neighbours by meaning across the whole index.

A new class of optimal binary linear complementary pairs of codes

cs.IT ·2026-11-01 ·Yansheng Wu, Jing Chen
published similarity 0.61
Abstract · 31 pages, accepted by SETA 2026

The construction of optimal binary linear complementary pair (LCP) has recently attracted considerable attention in coding theory. Based on the Belov codes, this paper proposes a novel construction of optimal binary LCPs with $θ=4$, extending our previous work on $θ=3$. Our results not only yield abundant new optimal binary LCPs with flexible parameters, but also enable more optimal binary LCPs with smaller minimum distances.

0.30

Hamming and Johnson-Type Bounds for Joint Error Correction and Detection

cs.IT ·2026-11-13 ·Yulin Chen, Raymond W. Yeung
similarity 0.59
Abstract · This manuscript is a preliminary draft and is currently being revised. The final version will be posted once the revisions are complete. Com…

We derive upper bounds on the size of codes for joint error correction and detection over classical $q$-ary Hamming spaces. A $(c,c')$ joint error correcting and detecting code corrects every error of weight at most $c$ and detects every error whose weight lies between $c+1$ and $c+c'$. We establish equivalent conditions for this decoding requirement using Hamming balls and Hamming rings, and derive a joint bound that reduces to the Hamming bound when $c'=0$. We introduce joint perfect codes and show that binary repetition codes attain the joint bound whenever $n=2c+c'+1$. For codes satisfying $d_{\min}=2c+c'+1$, we investigate an alternative joint bound based on ring multiplicity and constant-weight code bounds. A further argument using the Cauchy-Schwarz inequality and pairwise ring intersections yields a refined joint bound that is always at least as strong as the original joint bound. We then incorporate an additional outer Hamming shell to obtain a Johnson-type extension. This extension provides a strict improvement for binary codes with $c'=1$, $d_{\min}=2c+2$, $c\geq2$, and $d_{\min}+2\leq n\leq3d_{\min}/2-1$. These results connect sphere-packing bounds with the geometry of joint error correction and detection.

0.12

LDPC Fractus Codes: Sparse Codes with Recursive Structure

cs.IT math.CO ·2026-09-28 ·Jesús Carrillo-Pacheco
similarity 0.58
Abstract · 43 pages

We introduce a new family of recursively constructed sparse matrices, termed Fractus matrices, and investigate their use in constructing low-density parity-check (LDPC) codes. Generated through a self-similar recursive process, these matrices yield regular sparse parity-check matrices while preserving key structural properties across successive iterations. This recursive structure enables an efficient encoding algorithm with computational complexity that is nearly linear in the block length. Decoding is performed using standard iterative message-passing algorithms, thereby retaining the low-complexity decoding characteristic of LDPC codes. The proposed construction produces Tanner graphs with girth six and guarantees a minimum Hamming distance of at least $\ell+1$. We establish several algebraic properties of Fractus matrices, including sparsity, regularity, recursive decomposition, and symmetry under the flip-transpose operation. In addition, we show that the family of Fractus matrices admits a natural lattice structure and that the associated LDPC codes inherit corresponding lattice-theoretic properties. These results establish a connection between order theory and coding theory. Overall, the proposed framework integrates recursive matrix constructions, efficient encoding, graph-theoretic analysis, and lattice theory into a unified algebraic approach to the design and analysis of scalable LDPC codes.

0.28

Low-Density Parity-Check Codes of High Girth from Permutation Polynomials

cs.IT ·2026-10-02 ·Tasawwar Hussain, Anthony Gómez-Fonseca, Tefjol Pllaha
similarity 0.57
Abstract · 6 pages, 1 figure

Quasi-cyclic low-density parity-check (QC-LDPC) codes are widely used in modern communication standards due to their simple structure and efficient encoder and decoder implementations. However, the commutativity of the circulant permutation matrices used in their construction significantly limits their girth and minimum distance, affecting iterative decoding performance. In this paper, we investigate protograph-based codes constructed using permutation polynomials of higher degree, focusing on a closed family of non-commuting binomial permutation polynomials that enables these constructions to exceed both of these girth and minimum distance upper bounds while maintaining a simple representation. Simulation results demonstrate improved decoding performance compared to constructions based on affine permutation polynomials, which include QC-LDPC codes.

0.15

New Minimum Storage Regenerating Codes With Small Sub-packetization Levels for All Admissible Repair Degrees

cs.IT ·2026-10-11 ·Jie Li, Xiaohu Tang, Linqi Song
similarity 0.57
Abstract · 14 pages

In this paper, {we propose a new family of $(n, k)$ Minimum Storage Regenerating (MSR) codes} for distributed storage systems. By structuring the parity-check matrix as a block Vandermonde matrix composed of diagonal matrices and generalized permutation matrices, the proposed code achieves a sub-packetization level of $N = (d-k+1)^{\lceil\frac{n}{2}\rceil}$ and supports any repair degree $k+1\le d<n$. A key innovation of the new construction lies in relaxing the strict commutativity condition previously required for the building blocks in the parity-check matrices of Ye-Barg codes. We introduce a novel proof technique to establish the MDS property without relying on full commutativity, thereby generalizing the applicability of block Vandermonde matrices and enriching the family of Ye-Barg codes. Additionally, the sparsity of the parity-check matrix enhances encoding and decoding efficiency by reducing computational complexity. This work provides new insights into the construction of MSR codes.

0.21

Block basis reduction for linear codes in non-Hamming metrics

cs.IT cs.DM ·2026-10-19 ·N. S. Kolesnikov, S. A. Novoselov
similarity 0.57
Abstract

In this paper, we generalize the code basis reduction to non-Hamming metrics. We propose a block basis reduction (BKZ) algorithm for codes that works for all coordinate-additive metrics. Our algorithm is a generalization of the algorithm of Ghentiyala and Stephens-Davidowitz, which in turn is an adaptation of the famous BKZ algorithm for lattices to linear codes and the Hamming metric. For block size~$2$ (LLL), we propose a polynomial-time algorithm with complexity~$\mathcal{O}(n^4 q^3)$ operations in~$\mathbb{F}_q$, where~$n$ is the length of the code and~$q$ is the alphabet size. For the Lee metric we provide an implementation of our algorithms and present experimental results on finding low Lee weight codewords.

0.27

Explicit construction of optimal binary linear complementary pairs via Belov codes

cs.IT ·2026-10-16 ·Yansheng Wu, Jing Chen, Jong Yoon Hyun
similarity 0.57
Abstract · 30 pages

The study of linear complementary pairs (LCPs) has been a hot topic in coding theory. Recently, Güneri constructed an infinite family of optimal binary LCPs from Solomon-Stiffler codes. Specifically, he proved that for every $k \geq 5$ and $d \geq \lceil (k - 1)/2 \rceil 2^{k - 1}$, there exist optimal binary linear complementary pairs of codes of length $g_2(k,d)$, where $g_2(k,d)$ denotes the Griesmer bound. In this paper, we construct additional optimal binary LCPs from Belov codes, which form a generalized class of Solomon-Stiffler codes. Our results not only generalize Güneri's construction, but also enable more flexible construction of optimal binary LCPs with a wide range of minimum distances.

0.22

Task-Oriented Boolean Function Computation: Practical Code Constructions

cs.IT ·2026-10-01 ·Yangshuo He, Guanding Yu, Jingge Zhu
similarity 0.57
Abstract

Task-oriented communication conveys information that is necessary for downstream tasks. For binary decision tasks, this paradigm is information-theoretically formalized by Boolean function computation (BFC) via channels, where the receiver aims to determine the value of a function unknown to the transmitter. In this paper, we devise a practical code construction for the BFC problem based on a Reed-Solomon code. For noiseless binary channels, we derive finite-blocklength worst-case error bounds. By defining a rate function that captures how supported message length scales with channel uses, we characterize the rate-reliability tradeoff for different Boolean function families. With respect to this rate function, the proposed construction achieves an asymptotic computation rate of $1/2$. We further extend this construction to noisy channels by packing multiple BFC tasks into a single block and concatenating them with a conventional channel code. The corresponding finite-blocklength guarantees are expressed in terms of effective channel uses per function evaluation. With a channel code rate $R_c$, this construction achieves an asymptotic computation rate of $R_c/2$, yielding $C/2$ when capacity-achieving channel codes are employed. Numerical results illustrate the derived bounds and demonstrate substantial performance gains over conventional transmission. As examples, the proposed scheme achieves SNR coding gains of approximately $3.4$ and $6.4$ dB at an average task error probability of $10^{-5}$ for the exact-weight and rank-test tasks, respectively.

0.07