Search

A distance search in Hamming space finds binary vectors whose Hamming distances are no more than a threshold from a query vector. It is a fundamental problem in many applications, such as image retrieval, near-duplicate Web page detection, and scientific databases. State-of-the-art approaches to Hamming distance search are mainly based on the pigeonhole principle to generate a set of candidates and then verify them. We observe that the constraint by the pigeonhole principle is not always tight and may bring about unnecessary candidates. We also observe that the distribution in real data is often skewed, but most existing solutions adopt a simple equi-width partitioning and allocate the same threshold to all the parts, hence failing to exploit the data skewness to optimize query processing. In this paper, we propose a new form of the pigeonhole principle which allows variable partitioning and threshold allocation. Based on the new principle, we develop a tight constraint of candidates and devise cost-aware methods for partitioning and threshold allocation to optimize query processing. In addition, we extend our methods to answer Hamming distance join queries. We also discuss the application of the pigeonhole principle in set similarity search, a problem that can be converted to Hamming distance search equivalently. Our evaluation on datasets with various data distributions shows the robustness of our solution and its superior query processing performance to the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Recommendation efficiency and data sparsity problems have been regarded as two challenges of improving performance for online recommendation. Most of the previous related work focus on improving recommendation accuracy instead of efficiency. In this paper, we propose a Deep Pairwise Hashing (DPH) to map users and items to binary vectors in Hamming space, where a user's preference for an item can be efficiently calculated by Hamming distance, which significantly improves the efficiency of online recommendation. To alleviate data sparsity and cold-start problems, the user-item interactive information and item content information are unified to learn effective representations of items and users. Specifically, we first pre-train robust item representation from item content data by a Denoising Auto-encoder instead of other deterministic deep learning frameworks; then we finetune the entire framework by adding a pairwise loss objective with discrete constraints; moreover, DPH aims to minimize a pairwise ranking loss that is consistent with the ultimate goal of recommendation. Finally, we adopt the alternating optimization method to optimize the proposed model with discrete constraints. Extensive experiments on three different datasets show that DPH can significantly advance the state-of-the-art frameworks regarding data sparsity and item cold-start recommendation. [ABSTRACT FROM AUTHOR]

Hashing methods have been widely used in Approximate Nearest Neighbor (ANN) search for big data due to low storage requirements and high search efficiency. These methods usually map the ANN search for big data into the $k$ -Nearest Neighbor ($k$ NN) search problem in Hamming space. However, Hamming distance calculation ignores the bit-level distinction, leading to confusing ranking. In order to further increase search accuracy, various bit-level weights have been proposed to rank hash codes in weighted Hamming space. Nevertheless, existing ranking methods in weighted Hamming space are almost based on exhaustive linear scan, which is time consuming and not suitable for large datasets. Although Multi-Index hashing that is a sub-linear search method has been proposed, it relies on Hamming distance rather than weighted Hamming distance. To address this issue, we propose an exact $k$ NN search approach with Multiple Tables in Weighted Hamming space named WHMT, in which the distribution of bit-level weights is incorporated into the multi-index building. By WHMT, we can get the optimal candidate set for exact $k$ NN search in weighted Hamming space without exhaustive linear scan. Experimental results show that WHMT can achieve dramatic speedup up to 69.8 times over linear scan baseline without losing accuracy in weighted Hamming space. [ABSTRACT FROM AUTHOR]

A covering code is a set of codewords with the property that the union of balls, suitably defined, around these codewords covers an entire space. Generally, the goal is to find the covering code with the minimum size codebook. While most prior work on covering codes has focused on the Hamming metric, we consider the problem of designing covering codes defined in terms of either insertions or deletions. First, we provide new sphere-covering lower bounds on the minimum possible size of such codes. Then, we provide new existential upper bounds on the size of optimal covering codes for a single insertion or a single deletion that are tight up to a constant factor. Finally, we derive improved upper bounds for covering codes using R ≥ 2 insertions or deletions. We prove that codes exist with density that is only a factor O(R log R) larger than the lower bounds for all fixed R. In particular, our upper bounds have an optimal dependence on the word length, and we achieve asymptotic density matching the best known bounds for Hamming distance covering codes. [ABSTRACT FROM AUTHOR]

As a special subclass of cyclic codes, BCH codes have wide applications in communication and storage systems. A BCH code of length $n$ over $\mathbb {F}_{q}$ is always relative to an $n$ -th primitive root of unity $\beta $ in an extension field of $\mathbb {F}_{q}$ , and is called a dually-BCH code if its dual is also a BCH code relative to the same $\beta $. The question as to whether a BCH code is a dually-BCH code is in general very hard to answer. In this paper, an answer to this question for primitive narrow-sense BCH codes and projective narrow-sense ternary BCH codes is given. Sufficient and necessary conditions in terms of the designed distances $\delta $ will be presented to ensure that these BCH codes are dually-BCH codes. In addition, the parameters of the primitive narrow-sense BCH codes and their dual codes are investigated. Some lower bounds on minimum distances of the dual codes of primitive and projective narrow-sense BCH codes are developed. Especially for binary primitive narrow-sense BCH codes, the new bounds on the minimum distances of the dual codes improve the classical Sidel’nikov bound, and are also better than the Carlitz and Uchiyama bound for large designed distances $\delta $. The question as to what subclasses of cyclic codes are BCH codes is also answered to some extent. As a byproduct, the parameters of some subclasses of cyclic codes are also investigated. [ABSTRACT FROM AUTHOR]

In this paper, we provide two complementary results for cyclic codes of composite length. First, we give a general construction of cyclic codes of length nr from cyclic codes of length n and a lower bound on the minimum distance. Numerical data show that many cyclic codes of composite length with the best parameters can be obtained in this way. Second, in the other direction, we show that for cyclic codes of length n with a primitive n-th root of unity as a non-zero, the minimum distance is roughly bounded by the square-free part of n. This means that we shall not expect good cyclic codes of length n in general if, for example, the length n is divisible by a high power of a prime. [ABSTRACT FROM AUTHOR]

Diameter perfect codes form a natural generalization for perfect codes. They are based on the code-anticode bound which generalizes the sphere-packing bound. The code-anticode bound was proved by Delsarte for distance-regular graphs and it holds for some other metrics too. In this paper we prove the bound for non-binary constant-weight codes with the Hamming metric and characterize the diameter perfect codes and the maximum size anticodes for these codes. We distinguish between six families of non-binary diameter constant-weight codes and four families of maximum size non-binary constant-weight anticodes. Each one of these families of diameter perfect codes raises some different questions. We consider some of these questions and leave lot of ground for further research. Finally, as a consequence, some $t$ -intersecting families related to the well-known Erdös-Ko-Rado theorem, are constructed. [ABSTRACT FROM AUTHOR]

We initiate a study, when $F$ is a general APN function, of the Boolean function $\gamma _{F}$ related to the differential spectrum of $F$ (and which is known to be bent if and only if $F$ is almost bent). We first list many open questions about it. We study its algebraic normal form and its bivariate representation. We characterize its linear structures and specify nonexistence cases; we show, for $n$ even, their relation with the bent components of $F$. We pose three related open problems. We characterize further in terms of $\gamma _{F}$ the fact that a component function of $F$ is bent and study if the number of bent components can be optimal. We consider in particular two classes, one of which is that of APN power functions. We study more deeply the relation between the Walsh transform of $\gamma _{F}$ and the Walsh transform of $F$. By applying the Titsworth relation to the Walsh transform $W_{\gamma _{F}}$ , we deduce a new relation satisfied by $W_{F}^{2}$ , which is as simple as Chabaud-Vaudenay’s characterization by the fourth moment of the Walsh transform (which is in fact a particular case of the new relation), and provides more information. From this new relation, we deduce, for a sub-class of APN functions, a lower bound on the nonlinearity, which is significantly stronger than $nl(F)>0$ (the only general known bound). This sub-class of APN functions includes all known APN functions. The question (which is another open problem that we state) arises whether this sub-class equals that of all APN functions, but our bound provides at least a beginning of explanation why all known APN functions have non-weak nonlinearity. We finally show how the nonlinearities of $\gamma _{F}$ and $F$ are related by a simple formula; this leads to a last open problem. [ABSTRACT FROM AUTHOR]

Locality sensitive hashing (LSH) is an efficient method for solving the problem of approximate similarity search in high-dimensional spaces. Through LSH, a high-dimensional similarity join can be processed in the same way as hash join, making the cost of joining two large datasets linear. By judicially analyzing the properties of multiple LSH algorithms, we propose a generic method to speed up the process of joining two large datasets using LSH. The crux of our method lies in the way which we identify a set of representative points to reduce the number of LSH lookups. Theoretical analyzes show that our proposed method can greatly reduce the number of lookup operations and retain the same result accuracy compared to executing LSH lookups for every query point. Furthermore, we demonstrate the generality of our method by showing that the same principle can be applied to LSH algorithms for three different metrics: the Euclidean distance (QALSH), Jaccard similarity measure (MinHash), and Hamming distance (sequence hashing). Results from experimental studies using real datasets confirm our error analyzes and show significant improvements of our method over the state-of-the-art LSH method: to achieve over 0.95 recall, we only need to operate LSH lookups for at most 15 percent of the query points. [ABSTRACT FROM AUTHOR]

Hash-based nearest neighbor search has become attractive in many applications. However, the quantization in hashing usually degenerates the discriminative power when using Hamming distance ranking. Besides, for large-scale visual search, existing hashing methods cannot directly support the efficient search over the data with multiple sources, and while the literature has shown that adaptively incorporating complementary information from diverse sources or views can significantly boost the search performance. To address the problems, this paper proposes a novel and generic approach to building multiple hash tables with multiple views and generating fine-grained ranking results at bitwise and tablewise levels. For each hash table, a query-adaptive bitwise weighting is introduced to alleviate the quantization loss by simultaneously exploiting the quality of hash functions and their complement for nearest neighbor search. From the tablewise aspect, multiple hash tables are built for different data views as a joint index, over which a query-specific rank fusion is proposed to rerank all results from the bitwise ranking by diffusing in a graph. Comprehensive experiments on image search over three well-known benchmarks show that the proposed method achieves up to 17.11% and 20.28% performance gains on single and multiple table search over the state-of-the-art methods. [ABSTRACT FROM PUBLISHER]

For any bent function, it is very interesting to determine its dual function, because the dual function is also bent in certain cases. For k odd and \gcd (n, k)=1 , it is known that the Coulter–Matthews bent function f(x)=Tr\left(ax^\frac 3^k+12\right) is weakly regular bent over \mathbb F3^{n} , where a\in \mathbb F3^{n}^{*} , and Tr(\cdot ):\mathbb F3^{n}\rightarrow \mathbb F3 is the trace function. In this paper, we investigate the dual function of $f(x)$ , aiming to determine a universal formula. In particular, for two cases, we determine the formula explicitly: for the case of n=3t+1$ and k=2t+1$ with t\geq 2n=3t+2$ and k=2t+1$ with t\geq 2f(x)$ is regular bent. [ABSTRACT FROM PUBLISHER]

The study of Armstrong codes is motivated by the problem of understanding complexities of dependences in relational database systems, where attributes have bounded domains. A $(q,k,n)$ -Armstrong code is a $q$ -ary code of length $n$ with minimum Hamming distance $n-k+1$ , and for any set of $k-1$ coordinates, there exist two codewords that agree exactly there. Let $f(q,k)$ be the maximum $n$ for which such a code exists. In this paper, $f(q,3)=3q-1$ is determined for all $q\geq 5$ with three possible exceptions. This disproves a conjecture of Sali. Furthermore, we introduce generalized Armstrong codes for branching, or $(s,t)$ -dependences, construct several classes of optimal Armstrong codes, and establish lower bounds for the maximum length $n$ in this more general setting. [ABSTRACT FROM AUTHOR]

Irregular quasi-cyclic (QC) low-density parity-check (LDPC) codes with the block dual-diagonal (BDD) parity structure are widely adopted in many communication standards because the BDD structure supports an efficient encoding and many degree-2 variable nodes inside are adequate for the construction of mid- to high-rate codes. However, we observe that low-rate irregular QC LDPC codes with the BDD parity structure inherently contain too many degree-2 variable nodes and suffer from error floors in high signal-to-noise ratio (SNR) region. In this paper, a generalized BDD structure including double-weight circulants as well as circulant permutation matrices is proposed for low-rate irregular QC LDPC codes with low error floors which is achieved with a little bit giving up error performance in the waterfall region. When constructing the parity part of a code with the generalized BDD structure, the portion of double-weight circulants is variable so that the resulting LDPC code can achieve a desired degree distribution including degrees 2 and 3 while supporting the efficient encoding. We show that low-rate QC LDPC codes constructed with the proposed BDD structure have better theoretical properties and lower error floor than those with the conventional BDD structure. [ABSTRACT FROM AUTHOR]

In this paper, we first study deviations of the complete weight distribution of a linear code from that of a random code. Then, we consider a large family of subfield subcodes of algebraic-geometric codes over prime fields which include BCH codes and Goppa codes and prove that the complete weight distribution is close to that of a random code if the code length is large compared with the genus of the curve and the degree of the divisor defining the code. [ABSTRACT FROM AUTHOR]

We consider the algebraic combinatorics of the set of injections from a $k$ -element set to an $n$ -element set. In particular, we give a new combinatorial formula for the spherical functions of the Gelfand pair $(S_{k} \times S_{n}, diag(S_{k}) \times S_{n-k})$. We use this combinatorial formula to give new Delsarte linear programming bounds on the size of codes over injections. [ABSTRACT FROM AUTHOR]

The weight spectra of MDS codes of length n and dimension k over arbitrary alphabets are studied. For all q-ary MDS codes of dimension k and length ${n}\ne {q}+{k}-1 $ containing the zero codeword, it is shown that all k weights from n to ${n}-{k}+1 $ are realized. The weight spectrum in the remaining case ${n}={q}+{k}-1 $ is also determined. Additionally, we prove that all binary MDS codes are equivalent to linear MDS codes. The proofs are combinatorial, and self contained. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of increasing the robustness to bit errors for two description scalar quantizers. Our approach is to start with an m -diagonal index assignment and further apply a permutation to the indexes of each description to increase the minimum Hamming distance d_{\rm min} of the set of valid index pairs. In particular, we show how to construct linear permutation pairs achieving d_{\rm min}\geq 3$ , and establish a lower bound in terms of the description rate $R$ , for the highest value of $m$ for which such permutations exist. [ABSTRACT FROM AUTHOR]

This paper studies the problem of information symbol availability in codes: we refer to a systematic code as code with $(r, t)$ -availability if every information (systematic) symbol can be reconstructed from $t$ disjoint groups of other code symbols, each of the sizes at most $r$ . This paper shows that it is possible to construct codes that can support a scaling number of parallel reads while keeping the rate to be an arbitrarily high constant. It further shows that this is possible with the minimum Hamming distance arbitrarily close to the Singleton bound. This paper also presents a bound demonstrating a tradeoff between rate, minimum Hamming distance, and availability parameters. Our codes match the aforementioned bound, and their constructions rely on certain combinatorial structures. Resolvable designs provide one way to realize these required combinatorial structures. The two constructions presented in this paper require field sizes, which are linear and exponential in the code length, respectively. From a practical standpoint, our codes are relevant for distributed storage applications involving hot data, i.e., the information, which is frequently accessed by multiple processes in parallel. [ABSTRACT FROM AUTHOR]

We investigate the list decodability of symbol-pair codes in this paper. First, we show that the list decodability of every symbol-pair code does not exceed the Gilbert–Varshamov bound. On the other hand, we are able to prove that with high probability, a random symbol-pair code can be list decoded up to the Gilbert–Varshamov bound. Our second result of this paper is to derive the Johnson-type bound, i.e., a lower bound on list decoding radius in terms of minimum distance. Finally, we present a list decoding algorithm of Reed–Solomon codes beyond the Johnson-type bound in the pair metric. 1 A symbol-pair code is referred to a code in the pair metric. [ABSTRACT FROM AUTHOR]

In spatial modulation (SM), the information bit stream is divided into two different sets: the transmit antenna index bits (TA-bits) and the amplitude and phase modulation bits (APM-bits). However, the conventional bit-to-symbol mapping (BTS-MAP) scheme maps the APM-bits and the TA-bits independently. For exploiting their joint benefits, we propose a new BTS-MAP rule based on the traditional 2-D Gray mapping rule, which increases the Hamming distance (HD) between the symbol pairs detected from the same transmit antenna (TA) and simultaneously reduces the average HD between the symbol pairs gleaned from different TAs. Based on the analysis of the distribution of minimum Euclidean distance (MED) of SM constellations, we propose a criterion for the construction of a meritorious BTS-MAP for a specific SM setup, with no need for additional feedback links or extra computational complexity. Finally, Monte Carlo simulations are conducted for confirming the accuracy of our analysis. [ABSTRACT FROM AUTHOR]

In this paper, time-invariant spatially coupled low-density parity-check convolutional codes (SC-LDPC-CCs) are considered, and the connections existing between their low-weight codewords and cycles in their Tanner graphs are studied. Using the polynomial representation of these codes, we show that parity-check matrices having columns with weight ≥2 can be analyzed considering a certain number of parity-check sub-matrices having regular columns with weight 2. These sub-matrices are associated to cycles in the code Tanner graph and define as many codes we denote as component codes. Based on this observation, we find that codewords of the main code can be expressed as combinations of codewords of the component codes. The design of codes free of codewords up to a certain weight is also addressed. We show that low-weight codewords in the main code can be avoided by removing some types of cycles in its Tanner graph. Our design approach is applied to some well-known ensembles of SC-LDPC-CCs to prove its effectiveness. [ABSTRACT FROM AUTHOR]

A q -ary code of length n , size M , and minimum distance d code. An (n,q^{k},n-k+1)_{q} code is called a maximum distance separable (MDS) code. In this paper, some MDS codes over small alphabets are classified. It is shown that every (k+d-1,q^{k},d)_{q} code with k\geq 3 , d \geq 3 , is equivalent to a linear code with the same parameters. This implies that the (6,5^4,3)5 code and the (n,7^{n-2},3)7 MDS codes for n\in \6,7,8\ are unique. The classification of one-error-correcting 8-ary MDS codes is also finished; there are 14, 8, 4, and 4 equivalence classes of (n,8^n-2,3)8 codes for $n=6,7,8$ , and 9, respectively. One of the equivalence classes of perfect (9,8^{7},3)_{8} codes corresponds to the Hamming code and the other three are nonlinear codes for which there exists no previously known construction. [ABSTRACT FROM PUBLISHER]

Codes over Galois rings have been studied extensively during the last three decades. Negacyclic codes over \mathop \mathrm GR\nolimits (2^a,m) of length 2^s have been characterized: the ring \mathcal R2(a,m,-1)= {\mathrm{ GR}}(2^{a},m)[x]/\langle x^{2^{s}}+1\rangle is a chain ring. Furthermore, these results have been generalized to \lambda -constacyclic codes for any unit \lambda of the form 4z-1 , . In this paper, we study more general cases and investigate all cases, where {\mathcal{ R}}_{p}(a,m,\gamma) = {\mathrm{ GR}}(p^{a},m)[x]/\langle x^{p^{s}}-\gamma \rangle is a chain ring. In particular, the necessary and sufficient conditions for the ring {\mathcal{ R}}_{p}(a,m,\gamma) to be a chain ring are obtained. In addition, by using this structure we investigate all \gamma -constacyclic codes over \mathop {\mathrm {GR}}\nolimits (p^{a},m) when {\mathcal{ R}}_{p}(a,m,\gamma)$ is a chain ring. The necessary and sufficient conditions for the existence of self-orthogonal and self-dual \gamma$ -constacyclic codes are also provided. Among others, for any prime p$ , the structure of is used to establish the Hamming and homogeneous distances of $\gamma$ -constacyclic codes. [ABSTRACT FROM PUBLISHER]

Consider the problem of packing Hamming balls of a given relative radius subject to the constraint that they cover any point of the ambient Hamming space with multiplicity at most $L$ . For odd $L\ge 3$ , an asymptotic upper bound on the rate of any such packing is proved. The resulting bound improves the best known bound (due to Blinovsky’1986) for rates below a certain threshold. The method is a superposition of the linear-programming idea of Ashikhmin, Barg, and Litsyn (that was previously used to improve the estimates of Blinovsky for $L=2$ ) and a Ramsey-theoretic technique of Blinovsky. As an application, it is shown that for all odd $L$ , the slope of the rate-radius tradeoff is zero at zero rate. [ABSTRACT FROM AUTHOR]

DNA-based storage is considered to be a promising option to accommodate huge amounts of data. The strings of nucleotides are prone to errors though. To reduce the error probability, these strings should satisfy constraints on the ratio of A’s and T’s versus the number of G’s and C’s, and on the maximum number of repeated identical nucleotides. To deal with errors when they occur after all, it is also desirable that the set of DNA-strings possesses certain error correction or detection capabilities. This is established by designing quaternary constrained codes with a specified minimum distance. Here, maximum-sized block codes with a fixed number of G/C symbols, no symbol repetition, and a minimum Hamming distance of two are presented. [ABSTRACT FROM AUTHOR]

This paper generalizes the conventional noncoherent OFDM-IM systems by allowing selection of different numbers of active subcarriers for message representation. We then present the maximum-likelihood (ML) detection rule for frequency-selective block fading channels. The performance of the ML receiver is analyzed in terms of pairwise-error probability as well as diversity order. Asymptotic analysis of the proposed system reveals the role of partial Hamming distance in designing diversity-exploiting activation patterns. Practical issues including low-complexity receiver, and code (activation pattern) design techniques are discussed. Furthermore, the effect of inter-carrier interference in fast fading scenarios, and generalization of the technique to multiple-antenna scenarios are studied. Finally, we present simulation results to illustrate performance benefits of the generalized OFDM-IM systems over the conventional noncoherent OFDM-IM systems. [ABSTRACT FROM AUTHOR]

Knuth's celebrated balancing method consists of inverting the first z bits in a binary information sequence, such that the resulting sequence has as many ones as zeroes, and communicating the index z to the receiver through a short balanced prefix. In the proposed method, Knuth's scheme is extended with error-correcting capabilities, where it is allowed to give unequal protection levels to the prefix and the payload. The proposed scheme is very general in the sense that any error-correcting block code may be used for the protection of the payload. Analyses with respect to redundancy and block and bit error probabilities are performed, showing good results while maintaining the simplicity features of the original scheme. It is shown that the Hamming distance of the code is of minor importance with respect to the error probability. [ABSTRACT FROM PUBLISHER]

Multiple-edge protographs have some advantages over single-edge protographs, such as potentially having larger minimum Hamming distance. However, most of results in the literature are related to the construction of single-edge quasi-cyclic low-density parity-check codes (QC-LDPC) codes and little research has been done for the construction of multiple-edge QC-LDPC codes. In this letter, for the first time, necessary and sufficient conditions for the exponent matrices to have multiple-edge QC-LDPC codes with girth 6 are provided. As a consequence of this letter, a lower bound on the lifting degree of regular and irregular multiple-edge QC-LDPC codes with girth 6 is derived. We also present QC-LDPC codes whose lifting degrees meet our proposed lower bound. These codes have shorter lengths compared with single-edge QC-LDPC codes. Another contribution of this letter is presenting a technique to reduce the size of the search space to find these codes. [ABSTRACT FROM AUTHOR]

Similarity search is essential to many important applications and often involves searching at scale on high-dimensional data based on their similarity to a query. In biometric applications, recent vulnerability studies have shown that adversarial machine learning can compromise biometric recognition systems by exploiting the biometric similarity information. Existing methods for biometric privacy protection are in general based on pairwise matching of secured biometric templates and have inherent limitations in search efficiency and scalability. In this paper, we propose an inference-based framework for privacy-preserving similarity search in Hamming space. Our approach builds on an obfuscated distance measure that can conceal Hamming distance in a dynamic interval. Such a mechanism enables us to systematically design statistically reliable methods for retrieving most likely candidates without knowing the exact distance values. We further propose to apply Montgomery multiplication for generating search indexes that can withstand adversarial similarity analysis, and show that information leakage in randomized Montgomery domains can be made negligibly small. Our experiments on public biometric datasets demonstrate that the inference-based approach can achieve a search accuracy close to the best performance possible with secure computation methods, but the associated cost is reduced by orders of magnitude compared to cryptographic primitives. [ABSTRACT FROM AUTHOR]

Generalized index modulation (GIM) which implicitly conveys information by the activated indices is a promising technique for next-generation wireless networks. Due to the prohibitive challenge of bit-to-index combination (IC) mapping optimization, conventional GIM system obtains the bit-to-IC mapping table randomly, which may suffer from some performance loss. To circumvent this issue, we propose a low-complexity graph theory assisted bit-to-IC gray coding for GIM systems by minimizing the average hamming distance (HD) between any two ICs having one different value. Specifically, we decompose and transform the optimization problem into two subproblems using the graph theory, i.e., 1) Select an IC set whose corresponding graph has the minimum degree; 2) Design a bit-to-IC mapping principle to minimize the weight of the selected graph. Low-complexity algorithms are developed to solve the subproblems with a significant reduced complexity. Both simulation and theoretical results are shown that the GIM systems with our proposed mapping table are capable of providing significant performance gains over the conventional counterparts without the need for any additional feedback-link and without extra computational complexity. It is also shown that the proposed bit-to-IC mapping table is straightforward for any GIM systems over generalized fading channels. [ABSTRACT FROM AUTHOR]

Separability in a code is crucial in guaranteeing a decent Hamming-distance separation among the codewords. In multibit biometric discretization where a code is used for quantization-intervals labeling, separability is necessary for preserving distance dissimilarity when feature components are mapped from a discrete space to a Hamming space. In this paper, we examine separability of Binary Reflected Gray Code (BRGC) encoding and reveal its inadequacy in tackling interclass variation during the discrete-to-binary mapping, leading to a tradeoff between classification performance and entropy of binary output. To overcome this drawback, we put forward two encoding schemes exhibiting full-ideal and near-ideal separability capabilities, known as Linearly Separable Subcode (LSSC) and Partially Linearly Separable Subcode (PLSSC), respectively. These encoding schemes convert the conventional entropy-performance tradeoff into an entropy-redundancy tradeoff in the increase of code length. Extensive experimental results vindicate the superiority of our schemes over the existing encoding schemes in discretization performance. This opens up possibilities of achieving much greater classification performance with high output entropy. [ABSTRACT FROM AUTHOR]

In conventional multiple description coding (MDC), two descriptions of a source are generated and sent over ON/OFF channels. In this paper, we are interested in exploiting the redundancy built in MDC to additionally confer robustness against other channel errors. In particular, we consider a multiple description lattice vector quantizer (MDLVQ) whose output (a pair of side lattice points) is mapped to a pair of binary indexes and each index is sent over a binary channel. One channel is noiseless, while the other is noisy. Thus, at the decoder, one description is received error-free, while the other may carry bit errors. Then the decoder uses the error-free description as side information to improve the reconstruction. The effectiveness of the decoder in alleviating the impact of bit errors depends on the mapping $\gamma $ of side lattice points to binary indexes. We propose the design of a structured bit-error resilient mapping $\gamma $. For this, the set of side lattice points is first partitioned using Voronoi regions of an appropriate coarse lattice. Next a good linear channel code is selected, each Voronoi region is assigned a coset of this channel code, and the side lattice points within each Voronoi region are mapped to binary sequences in the corresponding coset. In addition, we argue that the performance of $\gamma $ is improved by assigning cosets close in Hamming distance to neighboring Voronoi regions, and propose a technique to achieve this goal. We derive a lower bound on the error correction performance of the proposed mapping $\gamma $ in terms of the performance of the channel code $C$ used in its construction. Interestingly, we prove that, as the rate of the MDLVQ grows to infinity, the mapping $\gamma $ becomes as good as the code $C$ in correcting bit errors. Simulation results show the significant superiority of the proposed index mapping versus random mappings. [ABSTRACT FROM AUTHOR]

A new feature-extraction paradigm for graph-based automatic modulation classification is proposed in this letter. In the proposed new framework, the modulation features are optimally constructed using the Kullback–Leibler divergence of the dominant entries in the adjacency matrices associated with the graph presentation of the cyclic spectra. Then, the Hamming distance is invoked to measure the discrepancies between the features derived from the training and test data to determine the modulation type. The proposed algorithm, which can select the most distinguishable features, leads to the promising solution to automatic modulation classification (AMC). Compared with the existing AMC approach based on cyclic spectra, Monte Carlo simulation results demonstrate that the proposed AMC method using the new feature-extraction scheme is much more effective. [ABSTRACT FROM AUTHOR]

In this paper, we propose two novel modulation concepts based on a simple maximum distance separable (MDS) code and show that these concepts can achieve better error performance than index modulation (IM) and related schemes. In the first concept, we use amplitude and phase levels to form a simple MDS code, whereas, in the second one, in-phase and quadrature components of codeword elements are used to construct the MDS code. We depict practical schemes for using the proposed concepts with orthogonal frequency division multiplexing (OFDM). We analyze the performance in terms of the minimum Euclidean distance and bit error rate. We also show that the proposed techniques exhibit desirable properties such as efficient low-complexity detection, very simple bits-to-symbols, and symbols-to-bits mappings, and a better error performance when compared to the OFDM-IM and related schemes. More importantly, contrary to the vast majority of IM studies that focus on showing the superiority of the IM techniques against conventional modulation techniques, we show that modulation concepts based on a well-known MDS code can achieve better error performance than the IM and related schemes while exhibiting a structure as simple as these schemes. [ABSTRACT FROM AUTHOR]

A novel automatic modulation classification method based on the graph presentation of the cyclic spectrum is proposed. In our proposed scheme, the periodicity and the symmetry of the cyclic spectrum will be exploited to establish a concise feature representation of multiple graphs. The modulated signal is first transformed from the cycle-frequency domain into the graph domain. Consequently, the concise graph-presentation, namely, a set of weighted directed rings, will be formulated as the robust features of the original signal. Those features can be easily expressed by the corresponding adjacency matrices. It can be verified that the adjacency matrices are sparse and the non-zero entries therein can be registered as the efficient feature parameters. Through the Hamming distance measure to enumerate the difference between the feature parameters resulting from the training data and the test data, one can perform the modulation classification. Monte Carlo simulation results demonstrate that our proposed method can achieve much better classification accuracy than the existing technique when the cyclic spectrum is used. [ABSTRACT FROM PUBLISHER]

In this paper, a novel modulation scheme called set partition modulation (SPM) is proposed. In this scheme, set partitioning and ordered subsets in the set partitions are used to form codewords. We define different SPM variants and depict a practical model for using SPM with orthogonal frequency division multiplexing (OFDM). For the OFDM-SPM schemes, different constellations are used to distinguish between different subsets in a set partition. To achieve good distance properties as well as better error performance for the OFDM-SPM codewords, we define a codebook selection problem and formulate such a problem as a clique problem in graph theory. In this regard, we propose a fast and efficient codebook selection algorithm. We analyze error and achievable rate performance of the proposed schemes and provide asymptotic results for the performance. It is shown that the proposed SPM variants are general schemes, which encompass multi-mode OFDM with index modulation (MM-OFDM-IM) and dual-mode OFDM with index modulation (DM-OFDM-IM) as special cases. It is also shown that OFDM-SPM schemes are capable of exhibiting better error performance and improved achievable rate than conventional OFDM, OFDM-IM, DM-OFDM-IM, and MM-OFDM-IM. [ABSTRACT FROM AUTHOR]

Slepian-Wolf coding (SWC) can be effectively implemented by distributed arithmetic coding (DAC) codes. A theoretical tool named spectrum has been developed to analyze the complexity of the full-search binary DAC (BDAC) decoder for equiprobable sources. Following this work, this paper aims at improving the coding efficiency of BDAC codes. To achieve this goal, this paper analyzes how BDAC codes partition source space into codebooks and links codebook cardinalities with the initial spectrum. Further, by exploiting the final spectrum, this paper proves that the decoding error probability of BDAC codes will not tend to zero as code length goes to infinity, even at rates greater than the Slepian-Wolf limit. On the basis of theoretical analyses, two techniques are proposed to reduce the decoding error probability of BDAC codes, i.e., the permutation technique, which removes "near" (in the sense of Hamming distance) codewords in each codebook, and the weighted branching technique, which reduces the mis-pruning risk of proper paths during the decoding. The effectiveness of both techniques is well verified by experimental results. [ABSTRACT FROM PUBLISHER]

Nearest neighbor search is a problem of finding the data points from the database such that the distances from them to the query point are the smallest. Learning to hash is one of the major solutions to this problem and has been widely studied recently. In this paper, we present a comprehensive survey of the learning to hash algorithms, categorize them according to the manners of preserving the similarities into: pairwise similarity preserving, multiwise similarity preserving, implicit similarity preserving, as well as quantization, and discuss their relations. We separate quantization from pairwise similarity preserving as the objective function is very different though quantization, as we show, can be derived from preserving the pairwise similarities. In addition, we present the evaluation protocols, and the general performance analysis, and point out that the quantization algorithms perform superiorly in terms of search accuracy, search time cost, and space cost. Finally, we introduce a few emerging topics. [ABSTRACT FROM PUBLISHER]

We define a variable-length code having the property that no (non-empty) prefix of each its codeword is a suffix of any other one, and vice versa. This kind of code can be seen as an extension of two well-known codes in the literature, called, respectively, fix-free code and non-overlapping code. In this paper we present constructive algorithms for such codes and some numerical results about their cardinality. [ABSTRACT FROM PUBLISHER]

The growing interest in data storage has made the data size to be exponentially increased, hampering the process of knowledge discovery from these large volumes of high-dimensional and heterogeneous data. In recent years, many efficient algorithms for mining data associations have been proposed, facing up time and main memory requirements. Nevertheless, this mining process could still become hard when the number of items and records is extremely high. In this paper, the goal is not to propose new efficient algorithms but a new data structure that could be used by a variety of existing algorithms without modifying its original schema. Thus, our aim is to speed up the association rule mining process regardless the algorithm used to this end, enabling the performance of efficient implementations to be enhanced. The structure simplifies, reorganizes, and speeds up the data access by sorting data by means of a shuffling strategy based on the hamming distance, which achieve similar values to be closer, and considering both an inverted index mapping and a run length encoding compression. In the experimental study, we explore the bounds of the algorithms’ performance by using a wide number of data sets that comprise either thousands or millions of both items and records. The results demonstrate the utility of the proposed data structure in enhancing the algorithms’ runtime orders of magnitude, and substantially reducing both the auxiliary and the main memory requirements. [ABSTRACT FROM PUBLISHER]

Recently, brain-inspired hyperdimensional computing (HDC) becomes an emerging computational scheme that has achieved success in various domains, such as human activity recognition, voice recognition, and bio-medical signal classification. HDC mimics the brain cognition and leverages high-dimensional vectors (e.g., 10 000 dimensions) with fully distributed holographic representation and (pseudo-)randomness. Ensemble learning is a classical learning method utilizing a group of weak learners to form a strong learner, which aims to increase the accuracy of the model. This letter presents a systematic effort in exploring ensemble learning in the context of HDC and proposes an ensemble HDC model referred to as EnHDC. EnHDC uses a majority voting-based mechanism to synergistically integrate the prediction outcomes of multiple base HDC classifiers. To enhance the diversity of base classifiers, we vary the encoding mechanisms, dimensions, and data width settings among base classifiers. By applying EnHDC on a wide range of applications, results show that EnHDC can achieve on average 3.2% accuracy improvement over a single HDC classifier. Further, we show that EnHDC with reduced dimensionality can achieve similar or even surpass the accuracy of baseline HDC with higher dimensionality. This leads to a 20% reduction of storage requirement of the HDC model, which can enhance the efficiency of HDC enabled on low-power computing platforms. [ABSTRACT FROM AUTHOR]

Linear codes achieving or nearly achieving the Singleton bound are interesting in both theory and practice. The objective of this paper is to construct several infinite families of MDS, near MDS and almost MDS codes from some special cyclic subgroups of ${\mathbb {F}}_{q^{2}}^{*}$. To this end, the augmentation and extension techniques are used. The codes in this paper have flexible parameters and their lengths could be large. The minimum linear locality of the codes constructed in this paper is also studied. Some infinite families of optimal linearly locally recoverable codes are obtained. Besides, some codes in this paper are proved to be proper for error detection. [ABSTRACT FROM AUTHOR]

Consider an assignment of bits to the vertices of a connected graph $G(V,E)$ with the property that the value of each vertex is a function of the values of its neighbors. A collection of such assignments is called a storage code of length $|V|$ on $G$. The storage code problem can be equivalently formulated as maximizing the probability of success in a guessing game on graphs, or constructing index codes of small rate. If $G$ contains many cliques, it is easy to construct codes of rate close to 1, so a natural problem is to construct high-rate codes on triangle-free graphs, where constructing codes of rate $> 1/2$ is a nontrivial task, with few known results. In this work we construct infinite families of linear storage codes with high rate relying on coset graphs of binary linear codes. We also derive necessary conditions for such codes to have high rate, and even rate potentially close to one. We also address correction of multiple erasures in the codeword, deriving recovery guarantees based on expansion properties of the graph. Finally, we point out connections between linear storage codes and quantum CSS codes, a link to bootstrap percolation and contagion spread in graphs, and formulate a number of open problems. [ABSTRACT FROM AUTHOR]

Extensive studies on data analysis have been conducted to address pavement engineering problems including material and structure design, performance evaluation, maintenance, and preservation. This paper summarized and discussed more than 40 types of data analysis methods including statistical tests, experimental design, regressions, count data model, survival analysis, stochastic process models, supervised learnings, unsupervised learnings, reinforcement learnings, and Bayesian analysis applied in pavement engineering. Generally, traditional statistical regression models are proper for significant factors quantification and pavement performance predictions with explicit model equations and meanings of parameters. The supervised machine learnings are powerful in prediction, dealing with large data volume or unstructured data such as pavement distress images, sounds, and other unprocessed signals. The unsupervised machine learnings are usually used to pre-process data by reducing the dimensionality, extracting common factors of variables, and clustering the data samples. Selecting proper models and their combinations will be the key for the increasing accumulation of historical pavement performance data, as well as the big data from automatic pavement evaluations and pavement instrumentation in future practices and studies. [ABSTRACT FROM AUTHOR]

In recent years, convolutional neural networks (CNNs) have achieved significant advancements in various fields. However, the computation and storage overheads of CNNs are overwhelming for Internet-of-Things devices. Both network pruning algorithms and hardware accelerators have been introduced to empower CNN inference at the edge. Network pruning algorithms reduce the size and computational cost of CNNs by regularizing unimportant weights to zeros. However, existing works lack intrakernel structured types to tradeoff between sparsity and hardware efficiency, and the index storage for irregularly pruned networks is significant. Hardware accelerators leverage the sparsity of pruned CNNs to improve energy efficiency. However, their process element (PE) utilization rate is low because of uneven sparsity among input convolutional kernels. To overcome these problems, we propose PACA: a Pattern pruning Algorithm and Channel-fused high PE utilization Accelerator for CNNs. It includes three parts: a pattern pruning algorithm to explore the intrakernel sparsity type and reduce the index storage, a channel-fused hardware architecture to reduce the PEs’ idle rate and improve the performance, and a heuristic and taboo search-based smart fusion scheduler to analyze the idle PE problem and schedule the channel fusion in hardware. To demonstrate the effectiveness of PACA, we have implemented the software parts by Python and the hardware architecture by RTL codes. Experimental results on various datasets show that compared with an existing work, PACA can reduce the index storage overhead by $3.47\times $ – $5.63\times $ with 3.85–9.12 average patterns, and it can improve the hardware performance by $2.01\times $ – $5.53\times $ because of PEs’ idle rate reduction. [ABSTRACT FROM AUTHOR]

In network-wide monitoring, finding the large monitoring data entries is a fundamental network management function. However, the retrieval of large entries is extremely difficult and challenging as a result of incompleteness of network measurement data. Enlightened by tensor model’s strong capability of information representation and extraction, we model the network-wide monitoring data as a 3-way tensor. With tensor completion, the retrieval can be performed after recovering all missing entries. However, this not only incurs an extremely high cost when the tensor is large, but is also unnecessary. Instead, to quickly retrieve large entries at low cost, we transform the large entry retrieving problem to a cosine similarity searching problem, and propose two algorithms: 1) Quickly reordering the factor vectors based on Locality Sensitive Hashing (LSH) hash table so that vectors with small cosine distances are placed in the same hash bucket; 2) Quickly finding the similar vector of a queried one that the two together determine a large entry without incurring the high cost of recovering all entries through the dot products. In the process of LSH table building and similarity query, several novel techniques are proposed, including LSH table representation with the LSH forest, good hash table building to support the flexible search of cosine similarity, and bit-shifting-based quick similarity query. Our experimental studies on 4 real world datasets indicate that our technique is at least up to 60 times faster than the approach based on direct tensor completion. [ABSTRACT FROM AUTHOR]

Multiple-input multiple-output (MIMO) technology is helpful with improving the communication throughput and performance of molecular communication (MC) systems. Though index modulation (IM) approaches aid to alleviate intersymbol interference (ISI) and interlink interference (ILI) issues in molecular MIMO systems by encoding the information in the antenna index, ISI and ILI problems still exist in such environments. Coded modulation strategies show promising results in terms of system error performance due to their better ISI and ILI combating capability. In this letter, a novel coded modulation scheme is proposed where the pulse position constellation is incorporated with the coded antenna indices. The proposed scheme is shown to yield an improved error performance owing to its better ILI mitigating strength. [ABSTRACT FROM AUTHOR]

A class of self-dual quasi-abelian codes of index 2 over any finite field $F$ is introduced. By counting the number of such codes and the number of the codes in this class whose relative minimum weights are small, such codes are proved to be asymptotically good provided −1 is a square in $F$. Moreover, a class of self-orthogonal quasi-abelian codes of index 2 is defined; and such codes always exist. In a way similar to that for self-dual quasi-abelian codes of index 2, it is proved that these self-orthogonal quasi-abelian codes of index 2 are asymptotically good. [ABSTRACT FROM AUTHOR]