On Trellis Structures for Reed–Muller Codes

We study trellises of Reed–Muller codes from first principles. Our approach to local trellis behaviour seems to be new and yields amongst other things another proof of a result of Berger and Be'ery on the state complexity of Reed–Muller codes. We give a general form of a minimal-span generator matrix for the family of Reed–Muller codes with their standard bit-order. We apply this to determining the number of parallel subtrellises in any uniform sectionalisation of a Reed–Muller code and to designing trellises for Reed–Muller codes with more parallel subtrellises than the minimal trellis, but with the same state complexity.     

Trellis Structure and Higher Weights of Extremal Self-Dual Codes

A method for demonstrating and enumerating uniformly efficient (permutation-optimal) trellis decoders for self-dual codes of high minimum distance is developed. Such decoders and corresponding permutations are known for relatively few codes.The task of finding such permutations is shown to be substantially simplifiable in the case of self-dual codes in general, and for self-dual codes of sufficiently high minimum distance it is shown that it is frequently possible to deduce the existence of these permutations directly from the parameters of the code.A new and tighter link between generalized Hamming weights and trellis representations is demonstrated: for some self-dual codes, knowledge of one of the generalized Hamming weights is sufficient to determine the entire optimal state complexity profile.These results are used to characterize the permutation-optimal trellises and generalized Hamming weights for all [32,16,8] binary self-dual codes and for several other codes. The numbers of uniformly efficient permutations for several codes, including the [24,12,8] Golay code and both [24,12,9] ternary self-dual codes, are found.     

Some Characterizations of Completeness for Trellises in Terms of Joins of Cycles

This paper gives some new characterizations of completeness for trellises by introducing the notion of a cycle-complete trellis. One of our results yields, in particular, a characterization of completeness for trellises of finite length due to K. Gladstien (see K. Gladstien: Characterization of completeness for trellises of finite length, Algebra Universalis 3(1973), 341–344).     

On maximum length convolutional codes under a trellis complexity constraint

We look at convolutional codes with maximum possible code length for prescribed redundancy, conditioned on constraints on the free distance and on the bit-oriented trellis state complexity. Rate (n−1)/n codes have been studied to some extent in the literature, but more general rates have not been studied much. In this work we consider convolutional codes of rate (n−r)/n, r⩾1. Explicit construction techniques for free distance d_free=3 and 4 codes are described. For codes with r=2, an efficient exhaustive search algorithm is outlined. For the more general case with r⩾2, a heuristic approach is suggested. Several new codes were found for r=1 and in particular for r=2 and 3. Compared to previously known codes of similar free distance and complexity constraints, the new codes have either strictly higher rate, or the same rate but smaller low distance multiplicities.     

Weight distributions and weight hierarchies of two classes of binary linear codes

Linear codes with a few weights can be applied to communication, consumer electronics and data storage system. In addition, the weight hierarchy of a linear code has many applications such as on the type II wire-tap channel, dealing with t-resilient functions and trellis or branch complexity of linear codes and so on. In this paper, we present a formula for computing the weight hierarchies of linear codes constructed by the generalized method of defining sets. Then, we construct two classes of binary linear codes with a few weights and determine their weight distributions and weight hierarchies completely. Some codes of them can be used in secret sharing schemes.     

Some constructions of linearly optimal group codes

We continue here the research on (quasi)group codes over (quasi)group rings. We give some constructions of [n,n-3,3]_q-codes over F_q for n=2q and n=3q. These codes are linearly optimal, i.e. have maximal dimension among linear codes having a given length and distance. Although codes with such parameters are known, our main results state that we can construct such codes as (left) group codes. In the paper we use a construction of Reed-Solomon codes as ideals of the group ring F_qG where G is an elementary abelian group of order q.     

Exterior penalty in optimal control problem with state-control constraints

We consider an abstract optimal control problem with additional equality and inequality state and control constraints, we use the exterior penalty function to transform the constrained optimal control problem into a sequence of unconstrained optimal control problems, under conditions in control lie in L ₁, the sequence of the solution to the unconstrained problem contains a subsequence converging of the solution of constrained problem, this convergence is strong when the problemis non convex, and is weak if the problemis convex in control. This generalizes the results of P.Nepomiastcthy [4] where he considered the control in the Hilbert space L ²(I,? ^m ).     

A mathematical theory of strong emergence using multiscale variety

We argue conceptually and then demonstrate mathematically that it is possible to define a scientifically meaningful notion of strong emergence. A strong emergent property is a property of the system that cannot be found in the properties of the system's parts or in the interactions between the parts. The possibility of strong emergence follows from an ensemble perspective, which states that physical systems are only meaningful as ensembles rather than individual states. Emergent properties reside in the properties of the ensemble rather than of any individual state. A simple example is the case of a string of bits including a parity bit, i.e. the bits are constrained to have, e.g., an odd number of ON bits. This constraint is a property of the entire system that cannot be identified through any set of observations of the state of any or all subsystems of the system. It is a property that can only be found in observations of the state of the system as a whole. A collective constraint is a property of the system, however, the constraint is caused when the environment interacts with the system to select the allowable states. Although selection in this context does not necessarily correspond to biological evolution, it does suggest that evolutionary processes may lead to such emergent properties. A mathematical characterization of multiscale variety captures the implications of strong emergent properties on all subsystems of the system. Strong emergent properties result in oscillations of multiscale variety with negative values, a distinctive property. Examples of relevant applications in the case of social systems include various allocation, optimization, and functional requirements on the behavior of a system. Strongly emergent properties imply a global to local causality that is conceptually disturbing (but allowed!) in the context of conventional science, and is important to how we think about biological and social systems. © 2004 Wiley Periodicals, Inc. Complexity 9: 15–24, 2004     

How to Mask the Structure of Codes for a Cryptographic Use

In this paper we show how to strengthen public-key cryptosystems against known attacks, together with the reduction of the public-key. We use properties of subcodes to mask the structure of the codes used by the conceiver of the system. We propose new parameters for the cryptosystems and even a modified Niederreiter cryptosystem in the case of Gabidulin codes, with a public-key size of less than 4000 bits.Communicated by: P. WildAMS Classification: 11T71     

Weights modulo p e of linear codes over rings

In this paper we look at linear codes over the Galois ring $GR(p^{\ell}, m)$ with the homogeneous weight and we prove that the number of codewords with homogenous weights in a particular residue class modulo p ^e are divisible by high powers of p. We also state a result for a more generalized weight on linear codes over Galois rings. We obtain similar results for the Lee weights of linear codes over $\mathbb{F}_{2^m}+u\mathbb{F}_{2^m}$ and we prove that the results we obtain are best possible. The results that we obtain are an improvement to Wilson’s results in [Wilson RM (2003) In: Proceedings of international workshop on Cambridge linear algebra and graph coloring]     

An efficient algorithm for constructing reversible quasi-cyclic codes via Chinese remainder theorem

Regarding quasi-cyclic codes as certain polynomial matrices, we show that all reversible quasi-cyclic codes are decomposed into reversible linear codes of shorter lengths corresponding to the coprime divisors of the polynomials with the form of one minus x to the power of m. This decomposition brings us an efficient method to construct reversible quasi-cyclic codes. We also investigate the reversibility and the self-duality of the linear codes corresponding to the coprime divisors of the polynomials. Specializing to the cases where the number of cyclic sections is not more than two, we give necessary and sufficient conditions for the divisors of the polynomials for which the self-dual codes are reversible and the reversible codes of half-length-dimension are self-dual. Our theorems are utilized to search reversible self-dual quasi-cyclic codes with two cyclic sections over binary and quaternary fields of lengths up to seventy and thirty-six, respectively, together with the maximums of their minimum weights.     

Non-invertible-element constacyclic codes over finite PIRs

In this paper we introduce the notion of λ-constacyclic codes over finite rings R for arbitrary element λ of R. We study the non-invertible-element constacyclic codes (NIE-constacyclic codes) over finite principal ideal rings (PIRs). We determine the algebraic structures of all NIE-constacyclic codes over finite chain rings, give the unique form of the sets of the defining polynomials and obtain their minimum Hamming distances. A general form of the duals of NIE-constacyclic codes over finite chain rings is also provided. In particular, we give a necessary and sufficient condition for the dual of an NIE-constacyclic code to be an NIE-constacyclic code. Using the Chinese Remainder Theorem, we study the NIE-constacyclic codes over finite PIRs. Furthermore, we construct some optimal NIE-constacyclic codes over finite PIRs in the sense that they achieve the maximum possible minimum Hamming distances for some given lengths and cardinalities.     

Simulated annealing with asymptotic convergence for nonlinear constrained optimization

In this paper, we present constrained simulated annealing (CSA), an algorithm that extends conventional simulated annealing to look for constrained local minima of nonlinear constrained optimization problems. The algorithm is based on the theory of extended saddle points (ESPs) that shows the one-to-one correspondence between a constrained local minimum and an ESP of the corresponding penalty function. CSA finds ESPs by systematically controlling probabilistic descents in the problem-variable subspace of the penalty function and probabilistic ascents in the penalty subspace. Based on the decomposition of the necessary and sufficient ESP condition into multiple necessary conditions, we present constraint-partitioned simulated annealing (CPSA) that exploits the locality of constraints in nonlinear optimization problems. CPSA leads to much lower complexity as compared to that of CSA by partitioning the constraints of a problem into significantly simpler subproblems, solving each independently, and resolving those violated global constraints across the subproblems. We prove that both CSA and CPSA asymptotically converge to a constrained global minimum with probability one in discrete optimization problems. The result extends conventional simulated annealing (SA), which guarantees asymptotic convergence in discrete unconstrained optimization, to that in discrete constrained optimization. Moreover, it establishes the condition under which optimal solutions can be found in constraint-partitioned nonlinear optimization problems. Finally, we evaluate CSA and CPSA by applying them to solve some continuous constrained optimization benchmarks and compare their performance to that of other penalty methods.     

Stochastic approximations of constrained discounted Markov decision processes

We consider a discrete-time constrained Markov decision process under the discounted cost optimality criterion. The state and action spaces are assumed to be Borel spaces, while the cost and constraint functions might be unbounded. We are interested in approximating numerically the optimal discounted constrained cost. To this end, we suppose that the transition kernel of the Markov decision process is absolutely continuous with respect to some probability measure μ  . Then, by solving the linear programming formulation of a constrained control problem related to the empirical probability measure _μn${\mu }_n$ of μ, we obtain the corresponding approximation of the optimal constrained cost. We derive a concentration inequality which gives bounds on the probability that the estimation error is larger than some given constant. This bound is shown to decrease exponentially in n. Our theoretical results are illustrated with a numerical application based on a stochastic version of the Beverton–Holt population model.     

Recursive constructions of secure codes and hash families using difference function families

To protect copyrighted digital data against piracy, codes with different secure properties such as frameproof codes, secure frameproof codes, codes with identifiable parent property (IPP codes), traceability codes (TA codes) are introduced. In this paper, we study these codes together with related combinatorial objects called separating and perfect hash families. We introduce for the first time the notion of difference function families and use these difference function families to give generalized recursive techniques that can be used for any kind of secure codes and hash families. We show that some previous recursive techniques are special cases of these new techniques.     

CONDOR,a new parallel,constrained extension of Powell's UOBYQA algorithm: Experimental results and comparison with the DFO algorithm

This paper presents an algorithmic extension of Powell's UOBYQA algorithm (Unconstrained Optimization BY Quadratical Approximation). We start by summarizing the original algorithm of Powell and by presenting it in a more comprehensible form. Thereafter, we report comparative numerical results between UOBYQA, DFO and a parallel, constrained extension of UOBYQA that will be called in the paper CONDOR (COnstrained, Non-linear, Direct, parallel Optimization using trust Region method for high-computing load function). The experimental results are very encouraging and validate the approach. They open wide possibilities in the field of noisy and high-computing-load objective functions optimization (from 2 min to several days) like, for instance, industrial shape optimization based on computation fluid dynamic codes or partial differential equations solvers. Finally, we present a new, easily comprehensible and fully stand-alone implementation in C++ of the parallel algorithm.     

Optimal vector quantization in terms of Wasserstein distance

The optimal quantizer in memory-size constrained vector quantization induces a quantization error which is equal to a Wasserstein distortion. However, for the optimal (Shannon-)entropy constrained quantization error a proof for a similar identity is still missing. Relying on principal results of the optimal mass transportation theory, we will prove that the optimal quantization error is equal to a Wasserstein distance. Since we will state the quantization problem in a very general setting, our approach includes the Rényi-α-entropy as a complexity constraint, which includes the special case of (Shannon-)entropy constrained (α=1) and memory-size constrained (α=0) quantization. Additionally, we will derive for certain distance functions codecell convexity for quantizers with a finite codebook. Using other methods, this regularity in codecell geometry has already been proved earlier by György and Linder (2002, 2003) [11] and [12].     

State constrained reachability for stochastic hybrid systems

Many control problems can be formulated as driving a system to reach some target states while avoiding some unwanted states. We study this problem for systems with regime change operating in uncertain environments. Nowadays, it is a common practice to model such systems in the framework of stochastic hybrid system models. In this casting, the problem is formalized as a mathematical problem named state constrained stochastic reachability analysis. In the state constrained stochastic reachability analysis, this probability is computed by imposing a constraint on the system to avoid the unwanted states. The scope of this paper is twofold. First we define and investigate the state constrained reachability analysis in an abstract mathematical setting. We define the problem for a general model of stochastic hybrid systems, and we show that the reach probabilities can be computed as solutions of an elliptic integro-differential equation. Moreover, we extend the problem by considering randomized targets. We approach this extension using stochastic dynamic programming. The second scope is to define a developmental setting in which the state constrained reachability analysis becomes more tractable. This framework is based on multilayer modelling of a stochastic system using hierarchical viewpoints. Viewpoints represent a method originated from software engineering, where a system is described by multiple models created from different perspectives. Using viewpoints, the reach probabilities can be easily computed, or even symbolically calculated. The reach probabilities computed in one viewpoint can be used in another viewpoint for improving the system control. We illustrate this technique for trajectory design.