Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEmbedding in a perfect code
175
0
0.0
(
0
)
Added by
Denis Krotov
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Authors
Sergey Avgustinovich
Ask ChatGPT about the research
No Arabic abstract
A binary 1-error-correcting code can always be embedded in a 1-perfect code of some larger length
rate research
Read More
We investigate perfect codes in $mathbb{Z}^n$ under the $ell_p$ metric. Upper bounds for the packing radius $r$ of a linear perfect code, in terms of the metric parameter $p$ and the dimension $n$ are derived. For $p = 2$ and $n = 2, 3$, we determine all radii for which there are linear perfect codes. The non-existence results for codes in $mathbb{Z}^n$ presented here imply non-existence results for codes over finite alphabets $mathbb{Z}_q$, when the alphabet size is large enough, and has implications on some recent constructions of spherical codes.
Multi-class classification is mandatory for real world problems and one of promising techniques for multi-class classification is Error Correcting Output Code. We propose a method for constructing the Error Correcting Output Code to obtain the suitable combination of positive and negative classes encoded to represent binary classifiers. The minimum weight perfect matching algorithm is applied to find the optimal pairs of subset of classes by using the generalization performance as a weighting criterion. Based on our method, each subset of classes with positive and negative labels is appropriately combined for learning the binary classifiers. Experimental results show that our technique gives significantly higher performance compared to traditional methods including the dense random code and the sparse random code both in terms of accuracy and classification times. Moreover, our method requires significantly smaller number of binary classifiers while maintaining accuracy compared to the One-Versus-One.
We propose steganographic systems for the case when covertexts (containers) are generated by a finite-memory source with possibly unknown statistics. The probability distributions of covertexts with and without hidden information are the same; this means that the proposed stegosystems are perfectly secure, i.e. an observer cannot determine whether hidden information is being transmitted. The speed of transmission of hidden information can be made arbitrary close to the theoretical limit - the Shannon entropy of the source of covertexts. An interesting feature of the suggested stegosystems is that they do not require any (secret or public) key. At the same time, we outline some principled computational limitations on steganography. We show that there are such sources of covertexts, that any stegosystem that has linear (in the length of the covertext) speed of transmission of hidden text must have an exponential Kolmogorov complexity. This shows, in particular, that some assumptions on the sources of covertext are necessary.
Compressive sensing (CS) has been widely studied and applied in many fields. Recently, the way to perform secure compressive sensing (SCS) has become a topic of growing interest. The existing works on SCS usually take the sensing matrix as a key and the resultant security level is not evaluated in depth. They can only be considered as a preliminary exploration on SCS, but a concrete and operable encipher model is not given yet. In this paper, we are going to investigate SCS in a systematic way. The relationship between CS and symmetric-key cipher indicates some possible encryption models. To this end, we propose the two-level protection models (TLPM) for SCS which are developed from measurements taking and something else, respectively. It is believed that these models will provide a new point of view and stimulate further research in both CS and cryptography. Specifically, an efficient and secure encryption scheme for parallel compressive sensing (PCS) is designed by embedding a two-layer protection in PCS using chaos. The first layer is undertaken by random permutation on a two-dimensional signal, which is proved to be an acceptable permutation with overwhelming probability. The other layer is to sample the permuted signal column by column with the same chaotic measurement matrix, which satisfies the restricted isometry property of PCS with overwhelming probability. Both the random permutation and the measurement matrix are constructed under the control of a chaotic system. Simulation results show that unlike the general joint compression and encryption schemes in which encryption always leads to the same or a lower compression ratio, the proposed approach of embedding encryption in PCS actually improves the compression performance. Besides, the proposed approach possesses high transmission robustness against additive Gaussian white noise and cropping attack.
We study a random code ensemble with a hierarchical structure, which is closely related to the generalized random energy model with discrete energy values. Based on this correspondence, we analyze the hierarchical random code ensemble by using the replica method in two situations: lossy data compression and channel coding. For both the situations, the exponents of large deviation analysis characterizing the performance of the ensemble, the distortion rate of lossy data compression and the error exponent of channel coding in Gallagers formalism, are accessible by a generating function of the generalized random energy model. We discuss that the transitions of those exponents observed in the preceding work can be interpreted as phase transitions with respect to the replica number. We also show that the replica symmetry breaking plays an essential role in these transitions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
