The task of non-adaptive group testing is to identify up to d defective items from N items, where a test is positive if it contains at least one defective item, and negative otherwise. If there are t tests, they can be represented as a t × N measurement matrix. We have answered the question of whether there exists a scheme such that a larger measurement matrix, built from a given t × N measurement matrix, can be used to identify up to d defective items in time O(t log2 N). In the meantime, a t × N nonrandom measurement matrix with $t = O \left(\frac{d^2 \log_2^2{N}}{(\log_2(d\log_2{N}) - \log_2{\log_2(d\log_2{N})})^2} \right)$ can be obtained to identify up to d defective items in time poly(t). This is much better than the best well-known bound, $t = O \left(d^2 \log_2^2{N} \right)$. For the special case d = 2, there exists an efficient nonrandom construction in which at most two defective items can be identified in time $4\log_2^2{N}$ using $t = 4\log_2^2{N}$ tests. Numerical results show that our proposed scheme is more practical than existing ones, and experimental results confirm our theoretical analysis. In particular, up to 27 = 128 defective items can be identified in less than 16s even for N = 2100.
Digital watermarking technologies with spread spectrum (SS) sequences have been previously proposed. The sequences used in previous studies, however, do not necessarily have good correlation properties. It is known that complete complementary codes have ideal correlation properties and very effective for mobile communication systems like CDMA. In this paper, it is shown that correlation properties of sequences play very important roles in detecting the embedded secret information from the watermarked images. In addition, we propose a method to embed multiple secret data simultaneously into a single image.
We propose a simple algebraic construction for girth-8 regular QC-LDPC codes of short lengths, a few hundreds, based on the square matrix from some prime integers of the form $t^{2}+1=P$ and a multiplication table method. We generalize the conventional multiplication table method in a way that the size $T$ of the circular permutation matrix (CPM) can be different from the modulus $M$ in the calculation of the exponent matrix. We classify and suggest the parameters $P\leq M\leq T$ with $M=kP$ so that the resulting codes have girth 8. In particular, we prove the existence of a threshold $T_{0}$ so that the resulting code will always have girth 8 if $T > T_{0}$ is used, given that $M=kP$ . Finally, we present various simulation results and theoretical analysis, one of which shows that the proposed codes of length around 250 have an additional coding gain of about 0.4 dB over the 5G NR LDPC codes.
Complete complementary code can be applied to digital watermarking technologies as well as communication systems like approximately synchronized CDMA because of its good correlation properties. In this paper, we propose a blind watermarking algorithm which does not need to refer any original data in the watermark extraction process. We also discuss the analogy between the proposed watermarking scheme and CT-CDMA communication systems based on complete complementary codes. In addition, some extensions of the proposed watermarking method and future problems are discussed in the paper.
1 December 2019 in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Hadamard matrix is defined as a square matrix where any components are -1 or +1, and where any pairs of rows are mutually orthogonal. In this work, we consider the similar matrix on finite field GF(p) where p is an odd prime. In such a matrix, every component is one of the integers on GF(p)\{0}, that is, {1,2,...,p-1}. Any additions and multiplications should be executed under modulo p. In this paper, a method to generate such matrices is proposed. In addition, the paper includes the applications to generate n-shift orthogonal sequences and complete complementary codes. The generated complete complementary code is a family of multi-valued sequences on GF(p)\{0}, where the number of sequence sets, the number of sequences in each sequence set and the sequence length depend on the various divisors of p-1. Such complete complementary codes with various parameters have not been proposed in previous studies.
Signal design methods for the approximately synchronized CDMA systems based on complete complementary codes have been proposed. It has been shown that both the information transmission rate and the frequency usage rate can be increased in these kinds of CDMA systems. The bit error rate (BER) properties of these systems have been also reported recently. However, it's not been considered sufficiently why bit errors occur. In this paper, we analyze the bit error distribution and discuss the cause of bit errors in these systems. In addition, we propose the effective demodulation scheme to decrease bit errors and compare the BER performances of the proposed method with that of the original demodulation scheme of CDMA systems using complete complementary codes through some numerical simulations.