Skip to content
Open access

New Lower Bounds for Weak Superimposed Codes

2026 · IEEE Signal Processing Letters · Vol 33, pp. 4271-4275 · 0 citations · 20 references

TL;DR

A new general lower bound on the largest code rate of weak superimposed codes for all integers is derived by improving the best known lower bound on the largest asymptotic code rate of weak <inline-formula><tex-math notation="LaTeX">$(t,T)$</tex-math></inline-formula> by the Lovász local lemma.

Abstract

Weak <inline-formula><tex-math notation="LaTeX">$(t,T)$</tex-math></inline-formula>-superimposed codes were introduced for noisy multimedia fingerprinting to determine the exact size of a coalition (up to <inline-formula><tex-math notation="LaTeX">$t$</tex-math></inline-formula> malicious users) under bounded adversarial noise <inline-formula><tex-math notation="LaTeX">$\Vert \epsilon \Vert \leq \frac{\sqrt{T}} {2\sqrt{2}t^{2}}$</tex-math></inline-formula>, where <inline-formula><tex-math notation="LaTeX">$T$</tex-math></inline-formula> is the least number of positions that contain a signal from exactly one user among the coalition. It is a specialized variant of classical superimposed codes in binary multi-access channels, which are widely recognized in the literature as disjunct matrices in group testing or cover-free families in combinatorial set systems. Existing results on weak superimposed codes are limited to the lower bound on the largest asymptotic code rate and randomized constructions. In this paper, we derive a new general lower bound on the largest code rate of weak <inline-formula><tex-math notation="LaTeX">$(t,T)$</tex-math></inline-formula>-superimposed codes for all integers <inline-formula><tex-math notation="LaTeX">$t\geq 2$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$T\geq 1$</tex-math></inline-formula> by the Lovász local lemma. Moreover, we show that our result improves the best known lower bound on the largest asymptotic code rate of weak <inline-formula><tex-math notation="LaTeX">$(t,T)$</tex-math></inline-formula>-superimposed codes for infinitely many pairs of <inline-formula><tex-math notation="LaTeX">$t$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$T$</tex-math></inline-formula>.

Read PDF

Similar papers

Open access Oct 2026

Singer-Difference-Set Qudit Stabilizer Codes From Non-Degenerate Quadrics in PG(d, q): Construction, Structural Theorems, and Monte-Carlo Performance

We propose <inline-formula> <tex-math notation="LaTeX">$\mathcal {Q}(q,d)$ </tex-math></inline-formula>, a new family of <inline-formula> <tex-math notation="LaTeX">$\mathbb {F}_{q}$ </tex-math></inline-formula>-ary non-CSS qudit stabilizer codes parameterised by a prime power <inline-formula> <tex-math notation="LaTeX...

Michel Kulhandjian, L. Hanzo · 0 citations
Open access 2026

Perfectly Private Lossless Variable-Length Coding With a Sequential Encoder

A lossless data compression problem with a privacy constraint is studied where a server has access to a database of <inline-formula> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula> files, <inline-formula> <tex-math notation="LaTeX">$(Y_{1},\ldots,Y_{N})$ </tex-math></inline-formula>, each of size <inline-fo...

A. Zamani, Mikael Skoglund · 0 citations
Open access Nov 2026

Minimax-Optimal Estimation of High-Order Missing Masses, and the Rare-Type Match Problem

Consider <inline-formula> <tex-math notation="LaTeX">$n\geq 1$ </tex-math></inline-formula> random samples <inline-formula> <tex-math notation="LaTeX">$\mathbf {X}_{n}=(X_{1},\ldots,X_{n})$ </tex-math></inline-formula> from an unknown distribution <inline-formula> <tex-math notation="LaTeX">$P=\sum _{j\geq 1}p_{j}\delt...

S. Favaro, Zacharie Naulet · 0 citations
Open access 2026

Criss-Cross Burst-Deletion Correcting Codes With Optimal Redundancy and En/Decoding Complexity $\mathcal{O}(n^{2})$

Two-dimensional error-correcting codes have attracted significant attention due to their applications in QR codes, DNA-based storage, and racetrack memories. This paper focuses on <inline-formula> <tex-math notation="LaTeX">$(t_{r}, t_{c})$ </tex-math></inline-formula>-criss-cross burst-deletion correcting codes, which...

Wen-Hao Liu, Zheng-Yi Jiang, Zhong-Yi Huang et al. · 0 citations
Open access 2026

On the Generalization of g-Circulant Matrices for Cryptographic MDS Matrix Construction

This paper generalizes circulant-type matrices over a finite field using the quotient rings to establish conditions related to their MDS, involutory, and semi-involutory properties and studies their invertibility, MDS, and involutory properties.

A. Khan, Amal S. Alali, Shakir Ali et al. · 0 citations
Open access Dec 2024

Sparse PCA: Phase Transitions in the Critical Regime

This work studies sparse principal component analysis (PCA) in high dimensions. Given <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> independent <inline-formula> <tex-math notation="LaTeX">$p$ </tex-math></inline-formula>-dimensional Gaussian samples with covariance <inline-formula> <tex-m...

Michal Feldman, Theodor Misiakiewicz, Elad Romanov · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.