Optimal relayed mobile communication systems

Recently, D.T. Chiang and R.F. Chiang (1986) considered a relayed mobile communication system with evenly spaced mobile relay stations (spacecraft) moving at the same speed from an origin towards a destination. Such a system can be considered as a consecutive-k-out-of-n line. They gave equations for computing the mean number of stations needed for a successful relay and studied the optimal choice of k to minimize the mean number. In the present work, the authors show that it is always better to replace a consecutive-k-out-of-n line by a consecutive-1-out-of- n line, but with k redundancy. The problem of choosing an optimal k still has no closed-form solution, but it is much more tractable than the original problem studied by Chiang and Chiang. Exact solutions are provided for a wide range of parameters     

A consecutive-k-out-of-n:G system: the mirrorimage of a consecutive-k-out-of-n:F system

A consecutive-k-out-of-n:F (consecutive-k -out-of-n:G) system consists of an ordered sequence of n components such that the system is failed (good) if and only if at least k consecutive components in the system are failed (good). In the present work, the relationship between the consecutive- k-out-of-n:F system and the consecutive-k-out-of-n:G system is studied, theorems for such systems are developed, and available results for one type of system are applied to the other. The topics include system reliability, reliability bounds, component reliability importance, and optimal system design. A case study illustrates reliability analysis and optimal design of a train operation system. An optimal configuration rule is suggested by use of the Birnbaum importance index     

Optimal-arrangement and importance of the components in aconsecutive-k-out-of-r-from-n:F system

The authors examine: the determination of an optimal consecutive k-out-of-r-from-n:F system, under permutations of the components, and the Birnbaum-importance of components in the i.i.d. case. The authors first study (theorem 1) the optimality of a general system, with not necessarily s-identical components, under permutation of the components. Then they study (theorem 2) the importance of components in the i.i.d. case. Theorem 2 is readily derived from theorem 1. The main results are given in theorems 1 and 2, and proofs are given. The assumptions are: the system and each component are either good or failed: all binary component states are mutually statistically independent, and all n can be arranged in any linear order; and the system fails if and only if within r consecutive components, there are at least k failed ones     

Invariant permutations for consecutive k-out-of-ncycles

Consecutive-k-out-of-n cycles are proposed as topologies for k-loop computer networks and describe a circular system of n components where the system fails if and only if any k consecutive components all fail. Suppose that the components are interchangeable. The the question arises as to which permutation maximizes the system reliability, assuming that the components have unequal reliabilities. If there exists on optimal permutation which depends on the ordering, but not the values, of the component reliabilities, then the system (and the permutation) is called invariant. The circular system is found to be not invariant except for k=1, 2, n-2, n-1, and n     

k-out-of-n:G systems: some cost considerations

The authors provide a tool that an engineer designing a subsystem can use to decide between one subsystem and a more reliable but more costly one. The authors provide methods for selecting redundancy levels in k-out-of-n:G systems in order to minimize particular cost considerations where the k-out-of-n:G system is a subsystem of a major system. The n and k are chosen to minimize the total cost of the subsystem plus the average loss due to subsystem failure. A BASIC program is available to determine the n and k which find this minimum. Five loss functions are considered, and illustrations are given     

The number of failed components in aconsecutive-k-of-n:F system

For a consecutive-k-out-of-n:F system an exact formula and a recursive relation are presented for the distribution of the number of components, X, that fail at the moment the system fails. X estimates how many cold spares are needed to replace all failed components upon system failure. The exact formula expresses the dependence of the distribution of X upon parameters k , n. The recursive formula is suitable for efficient numerical computation of the distribution of X     

Pseudocyclic maximum-distance-separable codes

The (n, k) pseudocyclic maximum-distance-separable (MDS) codes modulo (xⁿ- a) over GF(q) are considered. Suppose that n is a divisor of q+1. If n is odd, pseudocyclic MDS codes exist for all k. However, if n is even, nontrivial pseudocyclic MDS codes exist for odd k (but not for even k) if a is a quadratic residue in GF(q), and they exist for even k (but not for odd k) if a is not a quadratic residue in GF(q). Also considered is the case when n is a divisor of q-1, and it is shown that pseudocyclic MDS codes exist if and only if the multiplicative order of a divides (q-1)/n, and that when this condition is satisfied, such codes exist for all k. If the condition is not satisfied, every pseudocyclic code of length n is the result of interleaving a shorter pseudocyclic code     

Optimal designs of{k,n-k+1}-out-of-n:F systems(subject to 2 failure modes)

The problem of achieving optimal system size (n) for {k,n-k+1}-out-of-n systems, assuming that failure may take either of two forms, is studied. It is assumed that components are independently identically distributed (i.i.d.) and that the two kinds of system failures can have different costs. The optimal k or n that maximizes mean system-profit is determined, and the effect of system parameters on the optimal k or n is studied. It is shown that there does not exist a pair (k,n) maximizing the mean system-profit     

Reliability of consecutive-k-out-of-n:F systemswith nonidentical component reliabilities

A system with n components in sequence is a consecutive- k-out-of-n:F system if it fails whenever k consecutive components are failed. Under the supposition that component failures need not be independent and that component failure probabilities need not be equal, a topological formula is presented for the exact system reliability of linear and circular consecutive-k -out-of-n:F networks. The number of terms in the reliability formula is O(n⁴) in the linear case and O(n⁵) in the circular case     

Index system and separability of constant weight Gray codes

A number system is developed for the conversion of natural numbers to the codewords of the Gray code G(n,k) of length n and weight k, and vice versa. The focus is on the subcode G(n,k) of G(n) consisting of those words of G(n) with precisely k 1-bits, 0<k<n. This code is called the constant weight Gray code of length n and weight k. As an application sharp lower and upper bounds are derived for the value of |i-j|, where i and j are indices of codewords g_i and g_j of G(n,k) such that they differ in precisely 2 m bits     

A coding scheme for m-out-of-n codes

A scheme for the construction of m-out-of-n codes based on the arithmetic coding technique is described. For appropriate values of n, k, and m, the scheme can be used to construct an (n,k) block code in which all the codewords are of weight m. Such codes are useful, for example, in providing perfect error detection capability in asymmetric channels such as optical communication links and laser disks. The encoding and decoding algorithms of the scheme perform simple arithmetic operations recursively, thereby facilitating the construction of codes with relatively long block sizes. The scheme also allows the construction of optimal or nearly optimal m-out-of-n codes for a wide range of block sizes limited only by the arithmetic precision used     

m-consecutive-k-out-of-n:F systems

An m-consecutive-k-out-of-n:F system, consists of n components ordered on a line; the system fails if and only if there are at least m nonoverlapping runs of k consecutive failed components. Three theorems concerning such systems are stated and proved. Theorem one is a recursive formula to compute the failure probability of such a system. Theorem two is an exact formula for the failure probability. Theorem three is a limit theorem for the failure probability     

Reliability of a consecutivek-out-of-r-from-n:F system

The reliability of the consecutive k-out-of-r-from-n:F system is studied. For k=2 an explicit solution is given for n components in line or in cycle in the i.i.d. case. For k⩾3 sharp lower and upper bounds are given for the reliability of the system and demonstrated for different values of n, k, r, p. These bounds are exact for r=n, n-1, n-2, n-3, and for these values the exact analytic solution is also given     

Reliability of a general consecutive-k-out-of-n:Fsystem

A linear (circular) consecutive-k-out-of-n:F system consists of n components ordered on a line (circle). Each component and the system have two states: good or failed. The system fails if and only if at least k consecutive components fail. The reliability of such systems is computed. The most general case is examined without any restriction on the components     

Optimum codes of dimension 3 and 4 over GF(4)

n_q(k,d), the length of a q-ary optimum code for given k and d, for q=4 and k=3, 4 is discussed. The problem is completely solved for k=3, and the exact value of n₄(4,d) is determined for all but 52 values of d     

On the influence of coding on the mean time to failure fordegrading memories with defects

The application of a combined test-error-correcting procedure is studied to improve the mean time to failure (MTTF) for degrading memory systems with defects. The degradation is characterized by the probability p that within a unit of time a memory cell changes from the operational state to the permanent defect state. Bounds are given on the MTTF and it is shown that, for memories with N words of k information bits, coding gives an improvement in MTTF proportional to (k/n) N(d_min^-2)/(d_min ^-1), where d_min and (k/n) are the minimum distance and the efficiency of the code used, respectively. Thus the time gain for a simple minimum-distance-3 is proportional to N^-1. A memory word test is combined with a simple defect-matching code. This yields reliable operation with one defect in a word of length k+2 at a code efficiency k/(k+2)     

Maximum-likelihood blind deconvolution: non-whiteBernoulli-Gaussian case

The authors present a maximum-likelihood deconvolution (MLD) algorithm for estimating nonwhite Bernoulli-Gaussian signals μ(k ), which were distorted by a linear time-invariant system υ( k) taking into account the measured spectrum of μ(k) such as that obtained from sonic logs. The proposed MLD algorithm can recover both the phase of a minimum-phase coloring filter υ₁(k) and that of υ(k) as long as the spectrum of μ(k) is known in advance. The authors also present some simulation results which support the proposed MLD algorithm     

A replacement policy maximizing MTTF of a system with several spareunits

A replacement policy is considered that maximizes mean time-to-failure (MTTF) of a system with N spare units. The optimum replacement time of a system with k spares (k=1, 2, ..., N) is derived successively from MTTF with k-1 spares by induction. The maximum MTTF is approximately given by a reciprocal of the hazard rate     

Calculation of the binomial survivor function [reliabilityapplications]

A method is presented for calculating the binomial SF (cumulative binomial distribution), binfc(k;p,n), especially for a large n, beyond the range of existing tables, where conventional computer programs fail because of underflow and overflow, and Gaussian or Poisson approximations yield insufficient accuracy for the purpose at hand. This method is used to calculate and sum the individual binomial terms while using multiplication factors to avoid underflow; the factors are then divided out of the partial sum whenever it has the potential to overflow. A computer program uses this technique to calculate the binomial SF for arbitrary inputs of k, p, and n. Two other algorithms are presented to determine the value of p needed to yield a specified SF for given values of k and n and calculate the value where p=SF for a given k and n. Reliability applications of each algorithm/program are given, e.g. the value of p needed to achieve a stated k-out-of-n :G system reliability and the value of p for which k -out-of-n:G system reliability equals p     

Asymptotic results for partial concentrators

Various switching network construction advantageously use modules known as partial concentrators. A partial concentrator is an n-input, m-output, single-stage switching device in which each input has access to some but not all of the outputs. A partial concentrator is said to have capacity c, if, for any k⩽c inputs, there exist k disjoint paths from the k inputs to some set of k outputs. Here, capacity values achievable for large n when each input has access to exactly M outputs, are considered. For a partial concentrator in which each input has access to exactly M outputs, it is shown that the cost ratio can be made arbitrarily small for any fixed M⩾2. In addition, it is shown that the rate of decrease of the cost ratio with increasing n is logarithmic for M=2, and polynomial for M⩾3