IEEE Transactions on Information Theory, 67 (2021), 200-216.
Signature codes for weighted binary adder channel and multimedia fingerprinting
by Jinping Fan, Yujie Gu, Masahiro Hachimori, Ying Miao
Abstract
In this paper, we study binary signature codes for the weighted binary adder channel (WbAC) and collusion-resistant
multimedia fingerprinting. Let A(n, t) denote the maximum size of a t-signature code of length n, and A(n, w, t) denote
the maximum size of a t-signature code of length n and constant-weight w. First, we derive asymptotic and general upper
bounds on A(n, t) by relating signature codes to Bt codes and bipartite graphs with large girth respectively, and also
show the upper bounds are tight for certain cases. Second, we determine the exact values of A(n, 2, 2) and A(n, 3, 2) for
infinitely many n by connecting signature codes with C_4 -free graphs and union-free families, respectively. Third,
we provide two explicit constructions for t-signature codes which have efficient decoding algorithms and applications to
two-level signature codes. Furthermore, we show from a geometric viewpoint that there does not exist any binary code with
complete traceability for noisy WbAC and multimedia fingerprinting. A new type of signature codes with a weaker requirement
than complete traceability is introduced for the noisy scenario.