Search

The number-theoretic code is a class of codes defined by single or multiple congruences. These codes are mainly used for correcting insertion and deletion errors, and for correcting asymmetric errors. This paper presents a formula for a generalization of the complete weight enumerator for the number-theoretic codes. This formula allows us to derive the weight enumerators and cardinalities for the number-theoretic codes. As a special case, this paper provides the Hamming weight enumerators and cardinalities of the non-binary Tenengolts’ codes, correcting single insertion or deletion. Moreover, we show that the formula deduces the MacWilliams identity for the linear codes over the ring of integers modulo $r$. [ABSTRACT FROM AUTHOR]

We propose a successive cancellation list (SCL) encoding and decoding scheme for the Gelfand Pinsker (GP) problem based on the known nested polar coding scheme. It applies SCL encoding for the source coding part, and SCL decoding with a properly defined CRC for the channel coding part. The scheme shows improved performance compared to the existing method. A known issue with nested polar codes for binary dirty paper is the existence of frozen channel code bits that are not frozen in the source code. These bits need to be retransmitted in a second phase of the scheme, thus reducing the rate and increasing the required blocklength. We provide an improved bound on the size of this set, and on its scaling with respect to the blocklength, when the Bhattacharyya parameter of the test channel used for source coding is sufficiently large, or the Bhattacharyya parameter of the channel seen at the decoder is sufficiently small. The result is formulated for an arbitrary binary-input memoryless GP problem, since unlike the previous results, it does not require degradedness of the two channels mentioned above. Finally, we present simulation results for binary dirty paper and noisy write once memory codes. [ABSTRACT FROM AUTHOR]

The problem of universal source coding for binary trees is considered. Zhang, Yang, and Kieffer derived upper bounds on the average-case redundancy of codes based on directed acyclic graph (DAG) compression for binary tree sources with certain properties. In this paper, a natural class of binary tree sources is presented such that the demanded properties are fulfilled. Moreover, for both subclasses considered in the paper of Zhang, Yang, and Kieffer, their result is improved by deriving bounds on the maximal pointwise redundancy (or worst-case redundancy) instead of the average-case redundancy. Finally, using context-free tree grammars instead of DAGs, upper bounds on the maximal pointwise redundancy for certain binary tree sources are derived. This yields universal codes for new classes of binary tree sources. [ABSTRACT FROM AUTHOR]

This paper considers a device-to-device (D2D) fog-radio access network wherein a set of users are required to store/receive a set of files. The D2D devices are connected to a subset of the cloud data centers and thus possess a subset of the data. This paper is interested in reducing the total time of communication, i.e., the completion time, required to disseminate all files among all devices using instantly decodable network coding (IDNC). Unlike previous studies that assume a fully connected communication network, this paper tackles the more realistic scenario of a partially connected network in which devices are not all in the transmission range of one another. The joint optimization of selecting the transmitting device(s) and the file combination(s) is first formulated, and its intractability is exhibited. The completion time is approximated using the celebrated decoding delay approach by deriving the relationship between the quantities in a partially connected network. The paper introduces the cooperation graph and demonstrates that the problem is equivalent to a maximum weight clique problem over the newly designed graph. Extensive simulations reveal that the proposed solution provides noticeable performance enhancement and outperforms previously proposed IDNC-based schemes. [ABSTRACT FROM PUBLISHER]

In this paper, we establish some criteria to decide when a discrete memoryless channel admits a metric in such a way that the maximum likelihood decoding coincides with the nearest neighbor decoding. In particular, we prove a conjecture presented by M. Firer and J. L. Walker, establishing that every binary asymmetric channel admits a matched metric. [ABSTRACT FROM AUTHOR]

This paper investigates the construction of rank-metric codes with specified Ferrers diagram shapes. These codes play a role in the multilevel construction for subspace codes. A conjecture from 2009 provides an upper bound for the dimension of a rank-metric code with given specified Ferrers diagram shape and rank distance. While the conjecture in its generality is wide open, several cases have been established in the literature. This paper contributes further cases of Ferrers diagrams and ranks for which the conjecture holds true. In addition, the proportion of maximal Ferrers diagram codes within the space of all rank-metric codes with the same shape and dimension is investigated. Special attention is being paid to MRD codes. It is shown that for growing field size the limiting proportion depends highly on the Ferrers diagram. For instance, for $[m\times 2]$ -MRD codes with rank 2 this limiting proportion is close to $1/e$. [ABSTRACT FROM AUTHOR]

How to model the effect of reflection is crucial for single image reflection removal (SIRR) task. Modern SIRR methods usually simplify the reflection formulation with the assumption of linear combination of a transmission layer and a reflection layer. However, the large variations in image content and the real-world picture-taking conditions often result in far more complex reflection. In this paper, we introduce a new screen-blur combination based on two important factors, namely the intensity and the blurriness of reflection, to better characterize the reflection formulation in SIRR. Specifically, we present Screen-blur Reflection Networks (SRNet), which executes the screen-blur formulation in its network design and adapts to the complex reflection on real scenes. Technically, SRNet consists of three components: a blended image generator, a reflection estimator and a reflection removal module. The image generator exploits the screen-blur combination to synthesize the training blended images. The reflection estimator learns the reflection layer and a blur degree that measures the level of blurriness for reflection. The reflection removal module further uses the blended image, blur degree and reflection layer to filter out the transmission layer in a cascaded manner. Superior results on three different SIRR methods are reported when generating the training data on the principle of the screen-blur combination. Moreover, extensive experiments on six datasets quantitatively and qualitatively demonstrate the efficacy of SRNet over the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

The zero-error capacity of a channel is defined as the maximum rate at which it is possible to transmit information with zero probability of error. In this paper, we settle all previously unsolved cases for the zero-error capacity of binary channels with one memory. [ABSTRACT FROM AUTHOR]

A classical method of constructing a linear code over \mathrm GF(q) with a $t$ -design is to use the incidence matrix of the $t$ -design as a generator matrix over \mathrm GF(q) of the code. This approach has been extensively investigated in the literature. In this paper, a different method of constructing linear codes using specific classes of 2-designs is studied, and linear codes with a few weights are obtained from almost difference sets, difference sets, and a type of 2-designs associated to semibent functions. Two families of the codes obtained in this paper are optimal. The linear codes presented in this paper have applications in secret sharing and authentication schemes, in addition to their applications in consumer electronics, communication and data storage systems. A coding-theory approach to the characterization of highly nonlinear Boolean functions is presented. [ABSTRACT FROM AUTHOR]

Hashing is an important topic in image processing, as it can help save a considerable amount of storage and computational cost. Recently, inspired by 2D strategies employed in other areas of image processing, such as feature extraction, some 2D-based hashing methods were proposed. Related papers have shown that these methods may have better image retrieval performance in terms of both effectiveness and efficiency. However, the difference in the retrieval performances of hashing methods resulting from different forms of input (1D or 2D) has not been previously studied. Whether the widely used bilinear strategy in 2D-based hashing can truly help improve the retrieval precision has not been investigated in existing research. In this paper, we conduct a comparison study on 1D and 2D feature-based hashing methods and attempt to theoretically and experimentally analyse the differences in using 1D and 2D features in hashing. Furthermore, two new hashing methods are proposed for conducting the comparison experiments. Through a comprehensive study, we obtain three main conclusions in this paper: 1) Linear projection on 1D features and bilinear projection on 2D features are essentially the same. 2) 2D-based hashing methods are obviously more efficient than 1D-based methods for analysing high-dimensional input features. 3) 2D-based hashing methods show generally better performance for solving small sample size problems. [ABSTRACT FROM AUTHOR]

Boolean functions with high algebraic immunity are important cryptographic primitives in some stream ciphers. In this paper, two methodologies for constructing minimal binary codes from sets, Boolean functions and vectorial Boolean functions with high algebraic immunity, are proposed. More precisely, a general construction of new minimal codes using minimal codes contained in Reed-Muller codes and sets without nonzero low degree annihilators is presented. The other construction allows us to yield minimal codes from certain subcodes of Reed-Muller codes and vectorial Boolean functions with high algebraic immunity. Via these general constructions, infinite families of minimal binary linear codes of dimension $m$ and length less than or equal to $m(m+1)/2$ are obtained. Besides, a lower bound on the minimum distance of the proposed minimal linear codes is established. Conjectures and open problems are also presented. The results of this paper show that Boolean functions with high algebraic immunity have nice applications in several fields additionally to symmetric cryptography, such as coding theory and secret sharing schemes. [ABSTRACT FROM AUTHOR]

Two general constructions of linear codes with functions over finite fields have been extensively studied in the literature. The first one is given by C(ƒ) = {Tr(aƒ(x) + bx)x∈Fqm*: a, b ∈ Fqm}, where q is a prime power, Fqm* = Fqm \ {0}, Tr is the trace function from Fqm to Fq, and ƒ(x) is a function from Fqm to Fqm with ƒ(0) = 0. Almost bent functions, quadratic functions and some monomials on F2m were used in the first construction, and many families of binary linear codes with few weights were obtained in the literature. This paper studies some punctured codes of these binary codes. Several families of binary linear codes with few weights and new parameters are obtained in this paper. Several families of distance-optimal binary linear codes with new parameters are also produced in this paper. [ABSTRACT FROM AUTHOR]

Fingerprint retrieval aims to identify a query fingerprint image in a large database using indexing algorithms. Because of the abundant level 3 pore features within high-resolution fingerprint images, pore-based fingerprint retrieval algorithms have been rapidly developed. These retrieval algorithms, however, suffer from severe calculation-consuming problems with the pores increasing. This paper proposes a pore-based fingerprint retrieval method for high-resolution fingerprint images. The proposed method consists of two main steps. 1) In the pore indexing step, an indexing space is constructed using the binary codes of pores in enrolled images. Then, a designed graph-based searching algorithm searches the nearest neighbors of pores from the query image to construct one-to-many correspondences. 2) In the refinement step, the one-to-many correspondences are refined by a random walker-based graph comparison algorithm to remove the false correspondences. The remained nearest neighbors are used to calculate the similarities between the query image and the enrolled images. The proposed method is evaluated on two databases, showing that our method achieves better retrieval accuracies with a higher speed than the existing pore-based retrieval algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we apply two-to-one functions over F2n in two generic constructions of binary linear codes. We consider two-to-one functions in two forms: (1) generalized quadratic functions; and (2) (x2t + x)e with gcd (t, n) = gcd(e, 2n−1) = 1. Based on the study of the Walsh transforms of those functions or their variants, we present many classes of linear codes with few nonzero weights, including one weight, three weights, four weights, and five weights. The weight distributions of the proposed codes with one weight and with three weights are determined. In addition, we discuss the minimum distance of the dual of the constructed codes and show that some of them achieve the sphere packing bound. Moreover, examples show that some codes in this paper have best-known parameters. [ABSTRACT FROM AUTHOR]

This paper takes a fresh look at the image authentication problem and proposes an alternative framework for personalized authentication based on the hash learning technology. Conventional image authentication methods tend to provide a general authentication framework for all images with the fixed quantization strategy and fixed control parameters determined based on given limited images and attacks. However, they may suffer from more or less misjudgments in practice, not to mention performance degradation when encountering out-of-sample images. Instead of proposing a new feature extraction algorithm, a novel personalized authentication framework which incorporates the distance metric learning technology and supervised quantization strategy to the process of image authentication is proposed in this paper. The tamper detection task is reformulated as a new supervised manipulation classification problem. For each input image, various content-preserving and content-changing samples are generated automatically firstly. Then, feature representations of all samples can be obtained by existing feature extraction methods. After that, a weighted large margin for manipulation classification (WLMMC) scheme is proposed to learn an effective feature mapping space to improve the classification performance between content-changing samples and content-preserving samples. During the quantization stage, a novel supervised personalized quantization strategy (SPQ), which is motivated by the observation that different attacks have different degrees of influence on feature components, is proposed to learn more compact yet discriminative binary codes for each input image. Effectiveness of the proposed framework is qualitatively and quantitatively demonstrated on a variety of images. Extensive experiments show that the proposed framework can significantly improve the authentication performance over the state-of-the-art techniques while achieve more compact hash codes flexibly as required. [ABSTRACT FROM AUTHOR]

The family of Goppa codes is one of the most interesting subclasses of linear codes. As the McEliece cryptosystem often chooses a random Goppa code as its key, knowledge of the number of inequivalent Goppa codes for fixed parameters may facilitate in the evaluation of the security of such a cryptosystem. In this paper we present a new approach to give an upper bound on the number of inequivalent extended irreducible binary Goppa codes. To be more specific, let $n>3$ be an odd prime number and $q=2^{n}$ ; let $r\geq 3$ be a positive integer satisfying $\gcd (r,n)=1$ and $\gcd \big (r,q(q^{2}-1)\big)=1$. We obtain an upper bound for the number of inequivalent extended irreducible binary Goppa codes of length $q+1$ and degree $r$. [ABSTRACT FROM AUTHOR]

Linear codes generated by component functions of perfect nonlinear (PN for short) and almost perfect nonlinear (APN for short) functions and the first-order Reed-Muller codes have been an object of intensive study in coding theory. The objective of this paper is to investigate some binary shortened codes of two families of linear codes from APN functions and some $p$ -ary shortened codes associated with PN functions. The weight distributions of these shortened codes and the parameters of their duals are determined. The parameters of these binary codes and $p$ -ary codes are flexible. Many of the codes presented in this paper are optimal or almost optimal. The results of this paper show that the shortening technique is very promising for constructing good codes. [ABSTRACT FROM AUTHOR]

This paper generalizes the method proposed by Poulliat et al. for the determination of the optimal Galois field coefficients of a non-binary LDPC parity check constraint based on the binary image of the code. Optimal, or almost-optimal, parity check coefficients are given for check degree varying from 4 to 20 and Galois field varying from GF (64) up to GF (1024). For all given sets of coefficients, no codeword of Hamming weight two exists. A reduced complexity algorithm to compute the binary Hamming weight 3 of a parity check is proposed. When the number of sets of coefficients is too high for an exhaustive search and evaluation, a local greedy search is performed. Explicit tables of coefficients are given. The proposed sets of coefficients can effectively replace the random selection of coefficients often used in NB-LDPC construction. [ABSTRACT FROM AUTHOR]

Consider a channel with a given input alphabet size and input distribution. Our aim is to degrade or upgrade it to a channel with at most L output letters. Channel Q is degraded with respect to a channel W if Q can be obtained from W by processing the output of W. Upgrading is the inverse relation. This paper contains four main results. The first result, from which the paper title is derived, deals with the so called “greedy–merge” algorithm. We derive an upper bound on the reduction in mutual information between input and output, as a function of L. This upper bound is within a constant factor of an algorithm-independent lower bound. Thus, we establish that greedy–merge is optimal in the power-law sense (i.e. the power of L). The other main results deal with upgrading. The second result shows that a certain sequence of channels, which was previously shown to be “hard” for degrading, displays the same hardness in the context of upgrading. That is, suppose we are given such a channel and a corresponding input distribution. If we upgrade (degrade) to a new channel with L output letters, we incur an increase (decrease) in mutual information between input and output. We show that a previously derived bound on the decrease in mutual information for the degrading case is also a lower bound on the increase for the upgrading case. The third result is an efficient algorithm for optimal upgrading, in the binary-input case. That is, we are given a channel and an input distribution. We must find an upgraded channel with L output letters, for which the increase in mutual information is minimal. We give a simple characterization of such a channel, which implies an efficient algorithm. The fourth result is an analog of the first result for the upgrading case when the input is binary. That is, we first present a sub-optimal algorithm for the setting considered in the third result. The main advantage of the sub-optimal algorithm is that it is amenable to analysis. We carry out the analysis and show that the increase incurred in mutual information is within a constant factor of the lower bound derived in the second result. [ABSTRACT FROM AUTHOR]

Linear codes with certain special properties have received renewed attention in recent years due to their practical applications. Among them, binary linear complementary dual (LCD) codes play an important role in implementations against side-channel attacks and fault injection attacks. Self-orthogonal codes can be used to construct quantum codes. In this paper, four classes of binary linear codes are constructed via a generic construction which has been intensively investigated in the past decade. Simple characterizations of these linear codes to be LCD or self-orthogonal are presented. Resultantly, infinite families of binary LCD codes and self-orthogonal codes are obtained. Infinite families of binary LCD codes from the duals of these four classes of linear codes are produced. Many LCD codes and self-orthogonal codes obtained in this paper are optimal or almost optimal in the sense that they meet certain bounds on general linear codes. In addition, the weight distributions of two sub-families of the proposed linear codes are established in terms of Krawtchouk polynomials. [ABSTRACT FROM AUTHOR]

This paper deals with Hadamard \mathbb Z2 \mathbb Z4 {Q}8 -codes, which are binary codes after a Gray map from a subgroup of direct products of \mathbb Z2 , \mathbb Z4 , and Q8 , where Q8 is the quaternionic group. In a previous work, these codes were classified in five shapes. In this paper, we analyze the allowable range of values for the rank and dimension of the kernel, which depends on the particular shape of the code. We show that all these codes can be represented in a standard form, from a set of generators, which can help in understanding the characteristics of each shape. The main results we present are the characterization of Hadamard \mathbb Z2 \mathbb Z4 {Q}8 -codes as a quotient of a semidirect product of \mathbb Z2 \mathbb Z4 -linear codes and the construction of Hadamard \mathbb Z2 \mathbb Z4 {Q}8 -codes with each allowable pair of values for the rank and dimension of the kernel. [ABSTRACT FROM AUTHOR]

We show an explicit (that is, efficient and deterministic) capacity approaching interactive coding scheme that simulates any interactive protocol under random errors with nearly optimal communication rate. Specifically, over the binary symmetric channel with crossover probability $\epsilon $ , our coding scheme achieves a communication rate of $1 - O(\sqrt {H({\epsilon })})$ , together with negligible $\exp (-\Omega (\epsilon ^{4}\,\,n/\log n))$ failure probability (over the randomness of the channel). A rate of $1 - \tilde \Theta (\sqrt {H({\epsilon })})$ is likely asymptotically optimal as a result of Kol and Raz (2013) suggests. Prior to this paper, such a communication rate was achievable only using randomized coding schemes [Kol and Raz (2013); Hauepler (2014)]. [ABSTRACT FROM AUTHOR]

In this paper, a class of binary three-weight linear codes is constructed. Their dual codes are also studied. The dual codes are either optimal or almost optimal. These codes have applications in authentication codes, secret sharing schemes, and association schemes, in addition to their applications in consumer electronics and communication and data storage systems. [ABSTRACT FROM PUBLISHER]

Online image hashing has received increasing research attention recently, which processes large-scale data in a streaming fashion to update the hash functions on-the-fly. To this end, most existing works exploit this problem under a supervised setting, i.e., using class labels to boost the hashing performance, which suffers from the defects in both adaptivity and efficiency: First, large amounts of training batches are required to learn up-to-date hash functions, which leads to poor online adaptivity. Second, the training is time-consuming, which contradicts with the core need of online learning. In this paper, a novel supervised online hashing scheme, termed Fast Class-wise Updating for Online Hashing (FCOH), is proposed to address the above two challenges by introducing a novel and efficient inner product operation. To achieve fast online adaptivity, a class-wise updating method is developed to decompose the binary code learning and alternatively renew the hash functions in a class-wise fashion, which well addresses the burden on large amounts of training batches. Quantitatively, such a decomposition further leads to at least 75 percent storage saving. To further achieve online efficiency, we propose a semi-relaxation optimization, which accelerates the online training by treating different binary constraints independently. Without additional constraints and variables, the time complexity is significantly reduced. Such a scheme is also quantitatively shown to well preserve past information during updating hashing functions. We have quantitatively demonstrated that the collective effort of class-wise updating and semi-relaxation optimization provides a superior performance comparing to various state-of-the-art methods, which is verified through extensive experiments on three widely-used datasets. [ABSTRACT FROM AUTHOR]

Hashing has recently received substantial attention in large-scale multimedia search for its extremely low-cost storage cost and high retrieval efficiency. However, most existing hashing techniques focus on learning hash codes for single-view or cross-view retrieval. It is still an unsolved problem that how to efficiently learn discriminative binary codes for multi-view data that is common in real world multimedia search. In this paper, we propose an efficient Supervised Discrete Multi-view Hashing (SDMH) to solve the problem. SDMH first properly detects the shared binary hash codes, with an integrated multi-view feature mapping and latent hash coding, by exploiting the complementarity of different view-specific features and removing the involved inter-view redundancy. To further enhance the discriminative capability of hash codes, SDMH directly represses the explicit semantic labels of data samples with their corresponding binary codes. Different from most existing multi-view hashing methods that adopt “relaxing+rounding” hash optimization strategy or the discrete optimization method based on discrete cyclic coordinate descent, an efficient augmented Lagrangian multiplier (ALM) based discrete hash optimization method is developed in this paper to optimize the hash codes within a single step. Experimental results on four benchmark datasets demonstrate the superior performance of the proposed approach over state-of-the-art hashing techniques, in terms of both learning efficiency and retrieval accuracy. [ABSTRACT FROM AUTHOR]

Entropy coding is a fundamental technology in video coding that removes statistical redundancy among syntax elements. In high efficiency video coding (HEVC), context-adaptive binary arithmetic coding (CABAC) is adopted as the primary entropy coding method. The CABAC consists of three steps: binarization, context modeling, and binary arithmetic coding. As the binarization processes and context models are both manually designed in CABAC, the probability of the syntax elements may not be estimated accurately, which restricts the coding efficiency of CABAC. To address the problem, we propose a convolutional neural network-based arithmetic coding (CNNAC) method and apply it to compress the syntax elements of the intra-predicted residues in HEVC. Instead of manually designing the binarization processes and context models, we propose directly estimating the probability distribution of the syntax elements with a convolutional neural network (CNN), as CNNs can adaptively build complex relationships between inputs and outputs by training with a lot of data. Then, the values of the syntax elements, together with their estimated probability distributions, are fed into a multi-level arithmetic codec to perform entropy coding. In this paper, we have utilized the CNNAC to code the syntax elements of the DC coefficient; the lowest frequency AC coefficient; the second, third, fourth, and fifth lowest frequency AC coefficients; and the position of the last non-zero coefficient in the HEVC intra-predicted residues. The experimental results show that our proposed method achieves up to 6.7% BD-rate reduction and an average of 4.7% BD-rate reduction compared to the HEVC anchor under all intra (AI) configuration. [ABSTRACT FROM AUTHOR]

The quad-phase codes of a given length may be organized into equivalence classes relative to a set of operations preserving autocorrelation peak sidelobe level (PSL). Knowledge about these equivalence classes can be exploited for faster searches or for efficient listing of low- $\rm PSL$ codes. This paper is part of an effort to enumerate autocorrelation $\rm PSL$ equivalence classes for quad-phase codes of any length. An earlier paper achieved a formula for the number of $\rm PSL$ equivalence classes for even lengths $N \geq 2$ , as well as a simple algorithm for generating equivalence class representatives. This paper completes the enumeration task by extending the same formula to the odd lengths $N \geq 3$. The results make use of work by Yurramendi in enumerating equivalence classes for binary rectangular grids relative to horizontal reflection and vertical reflection. In addition, a method is described for generating a minimal set of $\rm PSL$ equivalence class representatives covering the space of quad-phase codes of any odd length $N > 3$. [ABSTRACT FROM AUTHOR]

In this paper, we study the decoding error probability of linear codes over the erasure channel under the list decoding. The notion of the $q^\ell $ -incorrigible sets of linear codes is introduced to characterize its decoding error probability under the list decoding or the maximum likelihood decoding. By calculating the $q^\ell $ -incorrigible set distributions, the decoding error probability of a linear code over the erasure channel under the list decoding or the maximum likelihood decoding is expressed by its support weight distributions. For the ensemble of all $[n,k]$ linear codes, the average decoding error probability under the maximum likelihood decoding and the average unsuccessful decoding probability under unambiguous decoding are determined. Furthermore, the error exponent of the average unsuccessful decoding probability under the unambiguous decoding is determined for the ensemble of all $[n,nR]$ linear codes. [ABSTRACT FROM AUTHOR]

This paper investigates fundamental properties of nonlinear binary codes by looking at the codebook matrix not row-wise (codewords), but column-wise. The family of weak flip codes is presented and shown to contain many beautiful properties. In particular the subfamily fair weak flip codes, which goes back to Shannon et al. and which was shown to achieve the error exponent with a fixed number of codewords $\mathsf {M}$ , can be seen as a generalization of linear codes to an arbitrary number of codewords. The fair weak flip codes are related to binary nonlinear Hadamard codes. Based on the column-wise approach to the codebook matrix, the $r$ -wise Hamming distance is introduced as a generalization to the well-known and widely used (pairwise) Hamming distance. It is shown that the minimum $r$ -wise Hamming distance satisfies a generalized $r$ -wise Plotkin bound. The $r$ -wise Hamming distance structure of the nonlinear fair weak flip codes is analyzed and shown to be superior to many codes. In particular, it is proven that the fair weak flip codes achieve the $r$ -wise Plotkin bound with equality for all $r$. In the second part of this paper, these insights are applied to a binary erasure channel with an arbitrary erasure probability 0 < $\delta$ < 1. An exact formula for the average error probability of an arbitrary (linear or nonlinear) code using maximum likelihood decoding is derived and shown to be expressible using only the $r$ -wise Hamming distance structure of the code. For a number of codewords $\mathsf {M}$ satisfying $\mathsf {M}\le 4$ and an arbitrary finite blocklength $n$ , the globally optimal codes (in the sense of minimizing the average error probability) are found. For $\mathsf {M}$ = 5 or $\mathsf {M}$ = 6 and an arbitrary finite blocklength $n$ , the optimal codes are conjectured. For larger $\mathsf {M}$ , observations regarding the optimal design are presented, e.g., that good codes have a large $r$ -wise Hamming distance structure for all $r$. Numerical results validate our code design criteria and show the superiority of our best found nonlinear weak flip codes compared with the best linear codes. [ABSTRACT FROM AUTHOR]

In this paper, we show how the presence of locality within a binary cyclic code can be exploited to improve decoding performance and to reduce decoding complexity. We pursue two approaches. Under the first approach, we show how the ordered statistics decoding (OSD) method can be modified by inserting a simple single round belief-propagation step at the start that involves only the local codes. The resultant locality-aware OSD algorithm yields an appreciable signal-to-noise ratio (SNR) gain for a given level of reliability and essentially the same level of decoder complexity. Under the second, trellis decoding approach, we show that the careful introduction of locality results in the creation of a cyclic subcode that possesses lower maximum state complexity. In addition, we present a simple means of deriving an upper bound to the state complexity profile of any cyclic code that is based only on the zeros of the code. Furthermore, we show how the decoding speed of either locality-aware OSD or trellis decoding can be significantly increased in the presence of locality, in the moderate-to-high SNR regime, by making the use of a quick-look decoder that often returns the maximum likelihood code word. [ABSTRACT FROM AUTHOR]

In this paper, we formulate the problem to cope with the transmission of extra bits over an existing coded transmission link (referred to as coded payload link) without any cost of extra transmission energy or extra bandwidth. This is possible since a gap to the channel capacity typically exists for a practical code. A new concept, termed as accessible capacity, is introduced to specify the maximum rate at which the superposition transmission of extra bits is reliable and has a negligible effect on the performance of the coded payload link. For a binary-input output-symmetric (BIOS) memoryless channel, the accessible capacity can be characterized as the difference between the channel capacity and the mutual information rate of the coded payload link, which can be numerically evaluated for very short payload codes. For a general payload code, we present a simple lower bound on the accessible capacity, given by the channel capacity minus the coding rate of the payload code. We then focus on the scenarios where low-density parity-check (LDPC) codes are implemented for the payload link. We propose to transmit extra bits by random superposition for encoding, and exhaustive search (with the aid of statistical learning) for decoding. We further propose, by establishing an auxiliary channel (called syndrome channel) induced from “zero-forcing” over the binary field, to transmit extra bits with structured codes such as repetition codes and first-order Reed-Muller (RM) codes. Numerical results show that up to 60 extra bits can be reliably transmitted along with a rate-1/2 LDPC code of length 8064. [ABSTRACT FROM AUTHOR]

In this paper, we are tackling the weakly-supervised referring expression grounding task, for the localization of a referent object in an image according to a query sentence, where the mapping between image regions and queries are not available during the training stage. In traditional methods, an object region that best matches the referring expression is picked out, and then the query sentence is reconstructed from the selected region, where the reconstruction difference serves as the loss for back-propagation. The existing methods, however, conduct both the matching and the reconstruction approximately as they ignore the fact that the matching correctness is unknown. To overcome this limitation, a discriminative triad is designed here as the basis to the solution, through which a query can be converted into one or multiple discriminative triads in a very scalable way. Based on the discriminative triad, we further propose the triad-level matching and reconstruction modules which are lightweight yet effective for the weakly-supervised training, making it three times lighter and faster than the previous state-of-the-art methods. One important merit of our work is its superior performance despite the simple and neat design. Specifically, the proposed method achieves a new state-of-the-art accuracy when evaluated on RefCOCO (39.21 percent), RefCOCO+ (39.18 percent) and RefCOCOg (43.24 percent) datasets, that is 4.17, 4.08 and 7.8 percent higher than the previous one, respectively. The code is available at https://github.com/insomnia94/DTWREG. [ABSTRACT FROM AUTHOR]

Supervised cross-modal hashing has attracted much attention. However, there are still some challenges, e.g., how to effectively embed the label information into binary codes, how to avoid using a large similarity matrix and make a model scalable to large-scale datasets, how to efficiently solve the binary optimization problem. To address these challenges, in this paper, we present a novel supervised cross-modal hashing method, i.e., scalaBle Asymmetric discreTe Cross-modal Hashing, BATCH for short. It leverages collective matrix factorization to learn a common latent space for the labels and different modalities, and embeds the labels into binary codes by minimizing a distance-distance difference problem. Furthermore, it builds a connection between the common latent space and the hash codes by an asymmetric strategy. In the light of this, it can perform cross-modal retrieval and embed more similarity information into the binary codes. In addition, it introduces a quantization minimization term and orthogonal constraints into the optimization problem, and generates the binary codes discretely. Therefore, the quantization error and redundancy may be much reduced. Moreover, it is a two-step method, making the optimization simple and scalable to large-scale datasets. Extensive experimental results on three benchmark datasets demonstrate that BATCH outperforms some state-of-the-art cross-modal hashing methods in terms of accuracy and efficiency. [ABSTRACT FROM AUTHOR]

Deletion errors are notoriously difficult to correct. The capacity of the binary deletion channel is not yet fully known, and there is no completely satisfactory solution even to the specific problem of correcting only two deletion errors. In this paper, we show that polarization theory, along with the powerful methods of polar coding and successive-cancellation decoding, can be extended to channels with deletion errors. Our results further generalize to channels corrupted by insertion errors and/or combinations of insertions and deletions. It was recently proposed to correct deletion errors using polar codes designed for the BEC, precoded with a sufficiently powerful CRC code. In this approach, in order to correct ${d}$ deletions in a codeword of length ${n}$ , successive-cancellation decoding is run separately for each of the $\binom {n}{d}$ possible deletion patterns, while treating the deleted symbols as erasures. The resulting complexity of decoding is ${O}\bigl ({n}^{d+1}\log {n}\bigr)$. In contrast, we develop herein a natural generalization of successive-cancellation decoding to channels with deletion errors. Our algorithm is based on the recursive structure of polar codes, processing the channel output in ${m} = \log _{2} {n}$ decoding layers, just like the conventional successive-cancellation decoder. Every node in each decoding layer propagates its uncertainty about the deletion pattern to the nodes in the next layer and, eventually, the correct deletion pattern becomes visible at the decoder output, with high probability. This makes it possible to consider at most $\binom {d+2}{2}$ scenarios at each node, and the overall decoding complexity is only ${O}\bigl ({d}^{3} {n} \log {n}\bigr)$ , which scales polynomially rather than exponentially with the number of deletions. Based on the proposed algorithm, we also investigate the channel polarization phenomenon. We are able to prove weak polarization where the number of deletions ${d}$ is small, i.e. ${d}={o}({n})$. We also conjecture the strong polarization for when ${d}={O}(1)$ and provide some evidence to support this conjecture. The strong polarization, if proven, implies that our coding scheme achieves the capacity of any binary-input symmetric channel which furthermore introduces a constant number of deletions. [ABSTRACT FROM AUTHOR]

In this paper, we focus on learning semantic representations for large-scale highly abstract sketches that were produced by the practical sketch-based application rather than the excessively well dawn sketches obtained by crowd-sourcing. We propose a dual-branch CNN-RNN network architecture to represent sketches, which simultaneously encodes both the static and temporal patterns of sketch strokes. Based on this architecture, we further explore learning the sketch-oriented semantic representations in two practical settings, i.e., hashing retrieval and zero-shot recognition on million-scale highly abstract sketches produced by practical online interactions. Specifically, we use our dual-branch architecture as a universal representation framework to design two sketch-specific deep models: (i) We propose a deep hashing model for sketch retrieval, where a novel hashing loss is specifically designed to further accommodate both the abstract and messy traits of sketches. (ii) We propose a deep embedding model for sketch zero-shot recognition, via collecting a large-scale edge-map dataset and proposing to extract a set of semantic vectors from edge-maps as the semantic knowledge for sketch zero-shot domain alignment. Both deep models are evaluated by comprehensive experiments on million-scale abstract sketches produced by a global online game QuickDraw and outperform state-of-the-art competitors. [ABSTRACT FROM AUTHOR]

This paper evaluates the practically achievable best error performance obtained from a dimmable visible light communication (VLC) system that conveys information using binary modulations, such as on-off keying (OOK). As compared to previous studies that address the ideal performance of dimmable VLC systems only over reliable channels with arbitrarily small error probability, this paper presents the best achievable error probability of various configurations with the dimming targets, signal quality, and data rate. The numerical results establish the ultimate decoding error performance targeted for dimmable VLC systems and are expected to provide a practical guideline for the enhanced VLC system design. [ABSTRACT FROM AUTHOR]

This paper studies a large random matrix system (LRMS) model involving an arbitrary signal distribution and forward error control (FEC) coding. We establish an area property based on the approximate message passing (AMP) algorithm. Under the assumption that the state evolution for AMP is correct for the coded system, the achievable rate of AMP is analyzed. We prove that AMP achieves the constrained capacity of the LRMS with an arbitrary signal distribution provided that a matching condition is satisfied. As a byproduct, we provide an alternative derivation for the constraint capacity of an LRMS using a proved property of AMP. We discuss realization techniques for the matching principle of binary signaling using irregular low-density parity-check (LDPC) codes and provide related numerical results. We show that the optimized codes demonstrate significantly better performance over un-matched ones under AMP. For quadrature phase shift keying (QPSK) modulation, bit error rate (BER) performance within 1 dB from the constrained capacity limit is observed. [ABSTRACT FROM AUTHOR]

Nowadays, the resistance against algebraic attacks and fast algebraic attacks are considered as an important cryptographic property for Boolean functions used in stream ciphers. Both attacks are very powerful analysis concepts and can be applied to symmetric cryptographic algorithms used in stream ciphers. The notion of algebraic immunity has received wide attention since it is a powerful tool to measure the resistance of a Boolean function to standard algebraic attacks. Nevertheless, an algebraic tool to handle the resistance to fast algebraic attacks is not clearly identified in the literature. In the current paper, we propose a new parameter to measure a Boolean function’s resistance to fast algebraic attack. We also introduce the notion of fast immunity profile and show that it informs both on the resistance to standard and fast algebraic attacks. Further, we evaluate our parameter for two secondary constructions of Boolean functions. Moreover, A coding-theory approach to the characterization of perfect algebraic immune functions is presented. Via this characterization, infinite families of binary linear complementary dual codes (or LCD codes for short) are obtained from perfect algebraic immune functions. Some of the binary LCD codes presented in this paper are optimal. These binary LCD codes have applications in armoring implementations against so-called side-channel attacks (SCA) and fault non-invasive attacks, in addition to their applications in communication and data storage systems. [ABSTRACT FROM AUTHOR]

Symbol-pair codes were introduced by Cassuto and Blaum in 2010 to protect pair errors in symbol-pair read channels. Recently Yaakobi, Bruck and Siegel (2016) generalized this notion to b-symbol codes in order to consider consecutive b errors for a prescribed integer b ≥ 2, and they gave constructions and decoding algorithms. Cyclic codes were considered by various authors as candidates for symbol-pair codes and they established minimum distance bounds on (certain) cyclic codes. In this paper we use algebraic curves over finite fields in order to obtain tight lower and upper bounds on b-symbol Hamming weights of arbitrary cyclic codes over Fq. Here b ≥ 2 is an arbitrary prescribed positive integer and Fq is an arbitrary finite field. We also present a stability theorem for an arbitrary cyclic code C of dimension k and length n: the b-symbol Hamming weight enumerator of C is the same as the k-symbol Hamming weight enumerator of C if k ≤ b ≤ n−1. Moreover, we give improved tight lower and upper bounds on b-symbol Hamming weights of some cyclic codes related to irreducible cyclic codes. Throughout the paper the length n is coprime to q. [ABSTRACT FROM AUTHOR]

A pair of sequences is called a Z-complementary pair (ZCP) if it has zero aperiodic autocorrelation sums at each of the non-zero time-shifts within a certain region, called the zero correlation zone (ZCZ). ZCPs are categorised into two types: Type-I ZCPs and Type-II ZCPs. Type-I ZCPs have the ZCZ around the in-phase position and Type-II ZCPs have the ZCZ around the end-shift position. Till now only a few constructions of Type-II ZCPs are reported in the literature, and all have lengths of the form 2m ± 1 or N + 1 where N = 2a 10b 26c and a, b, c are non-negative integers. In this paper, we propose a recursive construction of ZCPs based on concatenation of sequences. Inspired by Turyn’s construction of Golay complementary pairs, we also propose a construction of Type-II ZCPs from known ones. The proposed constructions can generate optimal Type-II ZCPs with new flexible parameters and Z-optimal Type-II ZCPs with any odd length. In addition, we give upper bounds for the PMEPR of the proposed ZCPs. It turns out that our constructions lead to ZCPs with low PMEPR. [ABSTRACT FROM AUTHOR]

The binary quadratic-residue codes and the punctured Reed-Muller codes ${\mathcal {R}}_{2}((m-1)/2, m))$ are two families of binary cyclic codes with parameters $[n, (n+1)/2, d \geq \sqrt {n}]$. These two families of binary cyclic codes are interesting partly due to the fact that their minimum distances have a square-root bound. The objective of this paper is to construct two families of binary cyclic codes of length $2^{m}-1$ and dimension near $2^{m-1}$ with good minimum distances. When $m \geq 3$ is odd, the codes become a family of duadic codes with parameters $[2^{m}-1, 2^{m-1}, d]$ , where $d \geq 2^{(m-1)/2}+1$ if $m \equiv 3 \pmod {4}$ and $d \geq 2^{(m-1)/2}+3$ if $m \equiv 1 \pmod {4}$. The two families of binary cyclic codes contain some optimal binary cyclic codes. [ABSTRACT FROM AUTHOR]

This paper presents a family of training preambles for offset quadratic-amplitude modulation based filter-bank multi-carrier (FBMC) modulations with low peak-to-average power ratio (PAPR) property. We propose to use binary Golay sequences as FBMC preambles and analyze the maximum PAPR for different numbers of zero guard symbols. For both the PHYDYAS and Hermite prototype filters with overlapping factor of 4, as an illustration of the proposed preambles, we show that a preamble PAPR less than 3 dB can be achieved with probability of one, when three or more zero guard symbols are inserted in the vicinity of each preamble. [ABSTRACT FROM AUTHOR]

Most codes with an algebraic decoding algorithm are derived from Reed-Solomon codes. They are obtained by taking equivalent codes, for example, generalized Reed-Solomon codes, or by using the so-called subfield subcode method, which leads to alternant codes over the underlying prime field, or over some intermediate subfield. The main advantage of these constructions is to preserve both the minimum distance and the decoding algorithm of the underlying Reed-Solomon code. In this paper, we explore in detail the subspace subcodes construction. This kind of codes was already studied in the particular case of cyclic Reed-Solomon codes. We extend this approach to any linear code over the extension of a finite field. We are interested in additive codes who are deeply connected to subfield subcodes. We characterize the duals of subspace subcodes. We introduce the notion of generalized subspace subcodes. We apply our results to generalized Reed-Solomon codes which leads to codes with interesting parameters, especially over a large alphabet. To conclude this paper, we discuss the security of the use of generalized subspace subcodes of Reed-Solomon codes in a cryptographic context. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of cross-modal retrieval by hashing-based approximate nearest neighbor search techniques. Most existing cross-modal hashing works mainly address the issue of multi-modal integration complexity using the same mapping and similarity calculation for data from different media types. Nonetheless, this may cause information loss during the mapping process due to overlooking the specifics of each individual modality. In this paper, we propose a simple yet effective cross-modal hashing approach, termed collective reconstructive embeddings (CRE), which can simultaneously solve the heterogeneity and integration complexity of multi-modal data. To address the heterogeneity challenge, we propose to process heterogeneous types of data using different modality-specific models. Specifically, we model textual data with cosine similarity-based reconstructive embedding to alleviate the data sparsity to the greatest extent, while for image data, we utilize the Euclidean distance to characterize the relationships of the projected hash codes. Meanwhile, we unify the projections of text and image to the Hamming space into a common reconstructive embedding through rigid mathematical reformulation, which not only reduces the optimization complexity significantly but also facilitates the inter-modal similarity preservation among different modalities. We further incorporate the code balance and uncorrelation criteria into the problem and devise an efficient iterative algorithm for optimization. Comprehensive experiments on four widely used multimodal benchmarks show that the proposed CRE can achieve a superior performance compared with the state of the art on several challenging cross-modal tasks. [ABSTRACT FROM AUTHOR]

In this paper, two different Gray-like maps from $Z_{p}^\alpha \times Z_{p^{k}}^\beta $ , where $p$ is prime, to $Z_{p}^{n}$ , $n={\alpha +\beta p^{k-1}}$ , denoted by $\varphi $ and $\Phi $ , respectively, are presented. We have determined the connection between the weight enumerators among the image codes under these two mappings. We show that if $C$ is a $Z_{p} Z_{p^{k}}$ -additive code, and $C^\bot $ is its dual, then the weight enumerators of the image $p$ -ary codes $\varphi (C)$ and $\Phi (C^\bot)$ are formally dual. This is a partial generalization of [D. S. Krotov, On $Z_{2^{k}}$ -dual binary codes, IEEE Transactions Information Theory 53 (2007), 1532–1537], and the result is generalized to odd characteristic $p$ and mixed alphabet. In addition, a construction of 1-perfect additive codes in the mixed $Z_{p} Z_{p^{2}}\ldots Z_{p^{k}}$ alphabet is given. [ABSTRACT FROM AUTHOR]

Lattice codes are elegant and powerful structures that not only achieve the capacity of the additive white Gaussian noise (AWGN) channel but are also a key ingredient to many multiterminal schemes that exploit linearity properties. However, constructing lattice codes that can realize these benefits with low complexity is still a challenging problem. In this paper, efficient encoding and decoding algorithms are proposed for multilevel binary low-density parity-check (LDPC) lattices constructed via Construction $\text{D}'$ whose complexity is linear in the total number of coded bits. Moreover, a generalization of Construction $\text{D}'$ is proposed, which relaxes some of the nesting constraints on the parity-check matrices of the component codes, leading to a simpler and improved design. Based on this construction, low-complexity multilevel LDPC lattices are designed whose performance under multistage decoding is comparable to that of polar lattices and close to that of low-density lattice codes on the power-unconstrained AWGN channel. [ABSTRACT FROM AUTHOR]

Linear complementary pairs (LCPs) of codes play an important role in armoring implementations against side-channel attacks and fault injection attacks. One of the most common ways to construct LCP of codes is to use Euclidean linear complementary dual (LCD) codes. In this paper, we first introduce the concept of linear codes with $\sigma $ complementary dual ($\sigma $ -LCD), which includes known Euclidean LCD codes, Hermitian LCD codes, and Galois LCD codes. Like Euclidean LCD codes, $\sigma $ -LCD codes can also be used to construct LCP of codes. We show that for $q > 2$ , all $q$ -ary linear codes are $\sigma $ -LCD, and for every binary linear code $\mathcal C$ , the code $\{0\}\times \mathcal C$ is $\sigma $ -LCD. Furthermore, we study deeply $\sigma $ -LCD generalized quasi-cyclic (GQC) codes. In particular, we provide the characterizations of $\sigma $ -LCD GQC codes, self-orthogonal GQC codes, and self-dual GQC codes, respectively. Moreover, we provide the constructions of asymptotically good $\sigma $ -LCD GQC codes. Finally, we focus on $\sigma $ -LCD abelian codes and prove that all abelian codes in a semi-simple group algebra are $\sigma $ -LCD. The results derived in this paper extend those on the classical LCD codes and show that $\sigma $ -LCD codes allow the construction of LCP of codes more easily and with more flexibility. [ABSTRACT FROM AUTHOR]

In addition to their applications in data communication and storage, linear codes also have nice applications in combinatorics and cryptography. Minimal linear codes, a special type of linear codes, are preferred in secret sharing. In this paper, a necessary and sufficient condition for a binary linear code to be minimal is derived. This condition enables us to obtain three infinite families of minimal binary linear codes with $w_{\min }/w_{\max } \leq 1/2$ from a generic construction, where $w_{\min }$ and $w_{\max }$ , respectively, denote the minimum and maximum nonzero weights in a code. The weight distributions of all these minimal binary linear codes are also determined. [ABSTRACT FROM AUTHOR]

This paper presents a simple and very flexible method for constructing quasi-cyclic (QC) low density parity-check (LDPC) codes based on finite fields. The code construction is based on two arbitrary subsets of elements from a given field. Some well known constructions of QC-LDPC codes based on finite fields and combinatorial designs are special cases of the proposed construction. The proposed construction in conjunction with a technique, known as masking, results in codes whose Tanner graphs have girth 8 or larger. Experimental results show that codes constructed using the proposed construction perform well and have low error-floors. Also presented in the paper is a reduced-complexity iterative decoding scheme for QC-LDPC codes based on the section-wise cyclic structure of their parity-check matrices. The proposed decoding scheme is an improvement of an earlier proposed reduced-complexity iterative decoding scheme. [ABSTRACT FROM PUBLISHER]