Structural properties and enumeration of quasi cyclic codes

Given any finite fieldF _q , an (N, K) quasi cyclic code is defined as aK dimensional linear subspace ofF _q ^N which is invariant underT ⁿ for some integern, 0 <n N, and whereT is the cyclic shift operator. Quasi cyclic codes are shown to be isomorphic to theF _q []-submodules ofF _q ^N where the product(gl)· is naturally defined as ₀ + ₁T ⁿ +...+ _m T ^mn if()= ₀ + ₁ +...+ _{m m} .In the case where (N/n, q)=1, all quasi cyclic codes are shown to be decomposable into the direct sum of a fixed number of indecomposable components called irreducible cyclicF _q []-submodules providing for the complete characterisation and enumeration of some subclasses of quasi cyclic codes including the cyclic codes, the quasi cyclic codes with a cyclic basis, the maximal and the irreducible ones. Finally a general procedure is presented which allows for the determination and characterisation of the dual of any quasi cyclic code.     

Implicit enumeration algorithms for the Set-Partitioning Problem

Summary A new column enumeration algorithm for solving the Set-Partitioning Problem is presented. It is not based on the staircase form of the coefficient matrix. Rather, it uses a preordering of the variables with respect to their cost of covering one row that is a supposition of a new strong lower bound concept. The enumeration process itself is organized similar to a general branch-and-bound concept. The performance of the algorithm is evaluated on the basis of a systematic comparison with different variants of the wellknown algorithms by Pierce and Garfinkel-Nemhauser. The computational experiences indicate that the new algorithm is superior for problems with moderatly dense coefficient matrices.

---

Zusammenfassung In diesem Artikel wird ein neuer spaltenenumerierender Algorithmus zur Lösung des Set-Partitioning-Problems beschrieben, der nicht die übliche treppenförmige Anordnung der Koeffizientenmatrix benutzt. Das Verfahren geht vielmehr von einer Sortierung der Variablen nach aufsteigenden Kosten zur Bedeckung einer Zeile aus. Unter der Voraussetzung einer solchen Ordnung läßt sich dann eine scharfe untere Schranke berechnen. Die Enumeration selber wird ähnlich wie in einem generellen Branch-and-Bound-Verfahren vollzogen. Die Güte dieses Algorithmus wird auf der Grundlage eines systematischen Vergleichs mit verschiedenen Varianten der bekannten Verfahren von Pierce und Garfinkel-Nemhauser überprüft. Die Ergebnisse zeigen, daß der neue Algorithmus für Probleme mit mittlerer Dichte der Koeffizientenmatrix überlegen ist.

     

Rapid and sensitive detection of respiratory virus molecular signatures using a silver nanorod array SERS substrate

A spectroscopic assay based on surface enhanced Raman scattering (SERS) using silver nanorod array substrates has been developed that allows for rapid detection of trace levels of viruses with a high degree of sensitivity and specificity. This novel SERS assay can detect spectral differences between viruses, viral strains, and viruses with gene deletions in biological media. The method provides rapid diagnostics for detection and characterization of viruses generating reproducible spectra without viral manipulation.     

Distribution and enumeration of attractors in probabilistic boolean networks

Many mathematical models for gene regulatory networks have been proposed. In this study, the authors study attractors in probabilistic Boolean networks (PBNs). They study the expected number of singleton attractors in a PBN and show that it is (2 - (1=2)/sup L-1)/sup n/, where n is the number of nodes in a PBN and L is the number of Boolean functions assigned to each node. In the case of L = 2, this number is simplified into 1.5/sup n/. It is an interesting result because it is known that the expected number of singleton attractors in a Boolean network (BN) is 1. Then, we present algorithms for identifying singleton and small attractors and perform both theoretical and computational analyses on their average case time complexities. For example, the average case time complexities for identifying singleton attractors of a PBN with L = 2 and L = 3 are O(1.601/sup n/) and O(1.763/sup n/), respectively. The results of computational experiments suggest that these algorithms are much more efficient than the naive algorithm that examines all possible 2/sup n/ states.     

Cutset enumeration of network systems with link and node failures

Network reliability analysis has received considerable attention and is thus widely studied to predict and prevent any network failure. However, most of such works presume perfectly reliable nodes. Although a few studies have considered both link and node failures, none of these methods has utilized the minimal paths or cuts, which are considered as fundamental approaches in the network reliability evaluation. An efficient method for deducing the minimal cutsets of a system subject to both link and node failures from the minimal cutsets of the system, which assumes perfect node reliability, is presented. The proposed method does not require re-enumeration of minimal cutsets for the additional consideration of the node failures. For a simple extension of such a method, the proposed approach can be embedded in any exact or approximate algorithm to account for link failures as well as node failures. As a result, the application of this method would be more realistic and valuable in practice for the reliability evaluation of networks with unreliable nodes.     

An implicit enumeration approach to tolerance allocation in sequential tolerance control

The accuracy and precision of a manufactured dimension is largely dependent on the accuracy and precision of the technological processes selected for its execution. It is not unusual to have available several competing technological processes for execution of each manufacturing operation specified in a process plan, where it is generally assumed that as the precision of the technological process improves, the associated cost and yield of the operation increase. This paper presents an implicit enumeration approach to the selection of an optimum subset of technological processes required to execute a process plan under a. sequential (or adaptive) tolerance control strategy.     

A Stepwise partial enumeration algorithm for the economic lot scheduling problem

This paper presents a stepwise partial enumeration algorithm for determining the economic lot schedule of a multiproduct single facility system on a repetitive basis. The algorithm is based on a simple “sufficient feasibility” test. The algorithm starts from a feasible schedule determined from the common cycle solution and continues stepwise partial enumerations to improve the schedule until no appreciable improvement occurs. Performance of the algorithm is demonstrated by solving six problems recently solved by Haessler. The algorithm gives better or equal solutions to the problems.     

Generalized quasi-cyclic codes over Galois rings: structural properties and enumeration

For R a Galois ring and m ₁, . . . , m _l positive integers, a generalized quasi-cyclic (GQC) code over R of block lengths (m ₁, m ₂, . . . , m _l ) and length ?_i=1^lm_i{\sum_{i=1}^lm_i} is an R[x]-submodule of R[x]/(x^m₁-1)×?×R[x]/(x^m_l-1){R[x]/(x^{m_1}-1)\times\cdots \times R[x]/(x^{m_l}-1)}. Suppose m ₁, . . . , m _l are all coprime to the characteristic of R and let {g ₁, . . . , g _t } be the set of all monic basic irreducible polynomials in the factorizations of x^m_i-1{x^{m_i}-1} (1 ≤ i ≤ l). Then the GQC codes over R of block lengths (m ₁, m ₂, . . . , m _l ) and length ?_i=1^lm_i{\sum_{i=1}^lm_i} are identified with G₁×?×G_t{{\mathcal G}_1\times\cdots\times {\mathcal G}_t}, where G_j{{\mathcal G}_j} is an R[x]/(g _j )-submodule of (R[x]/(g_j))^n_j{(R[x]/(g_j))^{n_j}}, where n _j is the number of i for which g _j appears in the factorization of x^m_i-1{x^{m_i}-1} into monic basic irreducible polynomials. This identification then leads to an enumeration of such GQC codes. An analogous result is also obtained for the 1-generator GQC codes. A notion of a parity-check polynomial is given when R is a finite field, and the number of GQC codes with a given parity-check polynomial is determined. Finally, an algorithm is given to compute the number of GQC codes of given block lengths.     

An implicit enumeration approach to probabilistic tolerance allocation under conventional tolerance control

The accuracy and precision of a manufactured dimension is largely dependent on the accuracy and precision of the technological processes selected for its execution. It is not unusual to have available several competing technological processes for execution of each manufacturing operation specified in a process plan, where it is generally assumed that, as the precision of the technological process improves, the associated cost and yield of the operation increase. This paper presents an implicit enumeration approach to the selection of an optimum subset of technological processes required to execute a process plan under a conventional tolerance control strategy. A probabilistic approach to the problem is presented and the First Order Second Moment Method (FOSMM) is used to estimate yield for an interdependent system of functional requirements.     

On the use of Petri nets for the enumeration of all trees in a graph

A technique utilizing the reachability concept of Petri nets for the enumeration of all the trees in a graph is proposed. Unlike the existing methods, the proposed technique does not require the selection of an arbitrary tree as the first step. Furthermore, instead of a larger number o steps being involved, only vector additions on a single matrix are needed. This alleviates the computational effort. The proposed technique is simple and easily adaptable on digital computers.