In this paper we will examine the rate-reliability function in source coding, its concavity property, as well as two optimality conditions that hold for this function. The first of these conditions is related to the successive refinement of information, the second to the robust descriptions coding.
Some reconstruction problems arising in combinatorics and coding theory are motivated by applications in information transmission when the redundancy of messages is not sufficient for their exact reconstruction, and in molecular biology, when one is interested in reconstructing unknown genetic data, or in restoring an evolution process.
The commonly used representations of genetic data, such as genomes, are permutations and signed permutations. In this paper, we focus our attention on a survey of recent results concerning the reconstruction of permutations and signed permutations from their erroneous patterns which are distorted by transpositions or reversals that are global rearrangements of genomes and can be considered as biological errors on genomes. The proposed approach is based on the investigation of structural properties of corresponding Cayley graphs Γ(G,S) where the symmetric group Sn of permutations and the hyperoctahedral group of signed permutations are considered as a group G, and generating sets S are specified by two operations that are transpositions and reversals.
The switching methods for constructing codes (binary, quaternary, q-ary, q>2) and an investigation of the nontrivial properties of codes are discussed in this paper. For each r, 0 ≤ r ≤ m, we present the class of quaternary linear codes [Lscr ][Rscr ][Mscr ](r,m) whose images under the Gray map are binary codes with the parameters of Reed-Muller RM(r,m) codes.
The following question is considered: Suppose f is a real function on the hypercube with non zero Fourier coefficients only at the vertices with few fixed weights. Is f uniquely determined by its values at these vertices or not? The main result of the paper gives a necessary and sufficient condition for this to be true, in the case of two fixed weights.