Reliability polynomial for a ring network

A mathematical model is developed for the reliability of a system made up of m unreliable nodes arranged in a ring. The model can be used to calculate the reliability of single-ring networks in which the network recovery mechanism depends on bypassing failed stations, but link signal power margins are inadequate to overcome losses due to more than n bypass switches in series. Computational complexity is 0(n²m+nm²/2) in time, and 0(m²/2) in memory requirements     

Fiber-optic bus-oriented single-hop interconnections amongmulti-transceiver stations

The merits of the single-path selective-broadcast interconnection (SBI) implemented in fiber-optic technology are explored. This is a static, passive, fiber-optic interconnection among a set of stations, each equipped with multiple transmitters, and receivers. It uses c ² buses, each interconnecting a subset of the stations, and provides a single optical path between any two stations. Thus, it succeeds in decoupling transmission rate from aggregate network throughput. It offers substantial advantages in power budget and the maximum number of stations that can be connected without repeaters and amplifiers. When compared with c buses, each interconnecting all stations, this SBI is attractive in terms of the required passive fiber-optic components such as fiber segments and star couplers. For a fixed power budget, the capacity of this SBI is optimal among bus-oriented single-hop interconnections for both a uniform traffic pattern and worst-case unknown skew     

Performance parameters of a wavelength-division demultiplexer madewith a single 3×3 coupler optical fiber ring or loopresonator

The performance parameters of a two-channel demultiplexer made with a single 3×3 coupler fiber ring or loop resonator are evaluated theoretically. These parameters include crosstalk, output intensity of the selected channel, and channel separation. Their dependence on the parameters of the coupler and the fiber such as the coupling length of the coupler, kd, the phase change of the fiber delay line, &thetas;, and the round-trip amplitude transmission coefficient of the fiber ring or loop G, which is the product of the amplitude transmission coefficients of the coupler and the fiber delay line and the amplitude gain of the degenerate two-wave mixing, is investigated. It is found that the best performance can be obtained at G=1     

Decoding geometric Goppa codes using an extra place

Decoding geometric Goppa codes can be reduced to solving the key congruence of a received word in an affine ring. If the codelength is smaller than the number of rational points on the curve, then this method can correct up to 1.2 (d*-L)/2-s errors, where d* is the designed minimum distance of the code and s is the Clifford defect. The affine ring with respect to a place P is the set of all rational functions which have no poles except at P, and it is somehow similar to a polynomial ring. For a special kind of geometric Goppa code, namely C_Ω(D,mP), the decoding algorithm is reduced to solving the key equation in the affine ring, which can be carried out by the subresultant sequence in the affine ring with complexity O(n³), where n is the length of codewords     

Relayed communication via parallel redundancy

A communication is described where relay stations are moving in groups of k stations. If all k stations of a group fail, then all groups of k stations ahead of the failed k stations as well as the k failed stations are lost. The objective is to have one station reach the destination with all groups having at least one station in good condition. It is shown that this second communication system requires fewer stations on the average than the system of D.T. Chiang and R.-F. Chiang (1986). The probability distribution of the numbers of stations required in the Chiang-Chiang communication system is also examined     

TDM policies in multistation packet radio networks

A multistation packet radio network with m stations and a finite number of nodes n that uses a conflict-free protocol to access the backbone network of stations through a shared channel is discussed. The goal is to derive an allocation of the channel time slots (time-division multiplexing cycle), so that all transmissions will be conflict-free and some measure of performance (e.g., the expected total weighted throughput, the expected weighted holding cost) will be optimized. The methodology that is used is to bound the performance and to allocate the slots according to the golden ratio policy     

A linear lightwave Benes network

The authors consider linear lightwave networks with a single waveband that have N inputs, each with a transmitter, and N outputs, each with a receiver, interconnected by optical links, broadcast stars, and wavelength-independent 2×2 switches. The transmitters and receivers can tune to C different wavelengths. The authors describe a rearrangeably nonblocking network that is a modification of the Benes network and uses transmitters that are fixed tuned and switches with two states. The network uses [1+o(1)] N/log₂(N/C) switches, which is shown to be nearly the minimum number. It is also shown that, if C =o(log N), then a rearrangeably nonblocking network requires [1+o(1)]Nlog₂N switches even if the switches have more than two states     

Reliability evaluation of a limited-flow network in terms ofminimal cutsets

Many systems can be regarded as flow networks whose arcs have discrete and multi-valued random capacities. The probability of the maximum flow at each various level and the reliability of such a flow network can be calculated in terms of K-lattices which are generated from each subset of the family of all MCs (minimal cutsets). However the size of such a family 2^m-1 (m=number of MCs) grows exponentially with m. Such a flow network can be considered as a multistate system with multistate components so that its reliability can be evaluated in terms of upper boundary points of each level d (named d-MCs here). This work presents an algorithm to generate all d-MCs from each MC for each system capacity level d. The new algorithm is analyzed and compared with the algorithm given by J. Xue (1985). Examples show how all d-MCs are generated; the reliability of one example is computed     

A fast topology maintenance algorithm for high-bandwidth networks

A fast time-driven algorithm for topology maintenance in high-speed networks is presented. The algorithm uses only four time units for each broadcast by each computer. The best previous algorithm required O(log m) time units for each broadcast by each computer, where m is the number of currently operational computers in the network. In addition to its speed, the presented algorithm makes several significant contributions. I. Cidon et al. (1988) have shown that Ω(log m) time units are necessary for time-driven topology maintenance algorithms of high-speed networks that do not allow a packet to traverse the same edge in both directions. The proposed algorithm shows that this lower bound does not hold for networks that do allow a packet to traverse the same edge in both directions. The O(log m) algorithm assumed that it takes each computer at most one time unit to simultaneously broadcast messages to all neighbors of the computer. In contrast, a node in the proposed algorithm can send at most, one message per time unit. As in the O(log m) algorithm, the algorithm requires O (D) broadcasts per node before all nodes know the correct topology of the network, where D is the diameter of the currently operational portion of the network     

A multibus train communication (AMTRAC) architecture for high-speedfiber optic networks

A multibus train (ordered demand assignment) communication architecture, using the AMTRAC protocol (for efficient utilization of fiber-optic-based very-high-speed networks) is presented. Taking advantage of the emerging WDM (wavelength-division multiplexing) and FDM (frequency-division multiplexing) technologies, the proposed solution introduces a coordinated multichannel control combining the performance advantages of two known approaches for high-speed communication: multichannel and train protocols. As a result an AMTRAC-based high-speed network achieves channel utilization significantly higher than previous approaches. For a network consisting of N stations, with propagation delay to packet transmission time ratio given by a, the AMTRAC architecture reaches a capacity of 1/(1+a/N ²)     

Packet error probabilities in frequency-hopped spread-spectrumpacket radio networks-memoryless frequency-hopping patterns considered

The packet error probability induced in a frequency-hopped spread-spectrum packet radio network is computed. The frequency spectrum is divided into q frequency bins. Each packet is exactly one codeword from an (M, L) Reed-Solomon code [M=number of codeword symbols (bytes); L=number of information symbols (bytes)]. Every user in the network sends each of the M bytes of his packet at a frequency chosen among the q frequencies with equal probability and independently of the frequencies chosen for other bytes (i.e., memoryless frequency-hopping patterns). Statistically independent frequency-hopping patterns correspond to different users in the network. Provided that K users have simultaneously transmitted their packets on the channel and a receiver has locked on to one of these K packets, the probability that this packet is not decoded correctly is evaluated. It is also shown that although memoryless frequency-hopping patterns are utilized, the byte errors at the receiver are not statistically independent; instead they exhibit a Markovian structure     

An approximate performance analysis of interconnected token-passingrings

An analysis of the performance, in terms of average message delay, is presented for a system of interconnected ring networks. The system is hierarchical, with local rings served by a high-speed backbone ring through gateway queues. In both the local and the backbone rings, the access technique employed is token passing. Service disciplines, with and without priority, have been studied. In the former, priority is given to inter-ring traffic over local traffic. The study makes use of certain results on average delay in systems where the customer initiating a busy period receives special service for the M/G/1 queue with nonpreemptive priority and for the G/G/1 queue. The analysis, which involved several approximations, was verified by simulation     

On the number of memories that can be perfectly stored in a neuralnet with Hebb weights

Let {w_ij} be the weights of the connections of a neural network with n nodes, calculated from m data vectors v¹, ···, v^m in {1,-1}ⁿ, according to the Hebb rule. The author proves that if m is not too large relative to n and the v^k are random, then the w_ij constitute, with high probability, a perfect representation of the v^k in the sense that the v ^k are completely determined by the w_ij up to their sign. The conditions under which this is established turn out to be less restrictive than those under which it has been shown that the v^k can actually be recovered by letting the network evolve until equilibrium is attained. In the specific case where the entries of the v^k are independent and equal to 1 or -1 with probability 1/2, the condition on m is that m should not exceed n/0.7 log n     

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     

Neural computation of arithmetic functions

A neuron is modeled as a linear threshold gate, and the network architecture considered is the layered feedforward network. It is shown how common arithmetic functions such as multiplication and sorting can be efficiently computed in a shallow neural network. Some known results are improved by showing that the product of two n-bit numbers and sorting of n n-bit numbers can be computed by a polynomial-size neural network using only four and five unit delays, respectively. Moreover, the weights of each threshold element in the neural networks require O(log n)-bit (instead of n -bit) accuracy. These results can be extended to more complicated functions such as multiple products, division, rational functions, and approximation of analytic functions     

Optimal selection of Reed-Solomon code rate and the number offrequency slots in asynchronous FHSS-MA networks

The performance of Reed-Solomon codes in an asynchronous frequency-hop spread-spectrum multiple-spectrum (FHSS-MA) network is discussed. When q denotes the number of frequency slots available to the network and r denotes the rate of the Reed-Solomon code, optimal (q,r) pairs that meet a given performance criterion with minimum bandwidth expansion (q/r) for a given number of active users are obtained. It is shown that the optimal code rate rapidly converges to a constant value and the optimum number of slots increases approximately linearly as the number of active users increases. This suggests that one should fix the code rate and increase the number of slots to accommodate the increasing number of users in the network under a given performance criterion with minimum bandwidth expansion     

Bounding the capacity of saturation recording: the Lorentz modeland applications

The authors consider the problem of bounding the information capacity of saturation recording. The superposition channel with additive Gaussian noise is used as a model for recording. This model says that for a saturation input signal, x(t) (i.e., one that can assume only one of two levels), the output can be expressed as y(t)=x˜(t)+z(t ) where x˜(t) is a filtered version of the input x(t) and z(t) is additive Gaussian noise. The channel is described by the impulse response of the channel filter, h(t), and by the autocorrelation function of the noise. A specific example of such a channel is the differentiated Lorentz channel. Certain autocorrelation and spectrum expressions for a general Lorentz channel are derived. Upper and lower bounds on the capacity of saturation recording channels are described. The bounds are explicitly computed for the differentiated Lorentz channel model. Finally, it is indicated how the derived bounds can be applied in practice using physical measurements from a recording channel     

A parallel algorithm for allocation of spare cells on memory chips

The authors propose a parallel algorithm based on the artificial neural network model for solving the spare-allocation problem. The goal is to find a spare allocation which repairs all the faulty cells in the given faulty-cell map. The parallel algorithm requires 2n processing elements for the n×n faulty-cell map problem. The algorithm is verified by many simulation runs. Under the simulation the algorithm finds one of the near-optimum solutions in a nearly constant time with O(n) processors. The simulation results show the consistency of this algorithm. The algorithm can be easily extended for solving rectangular or other shapes of fault map problems     

On (k, t)-subnormal covering codes

The concept of a (k, t)-subnormal covering code is defined. It is discussed how an amalgamated-direct-sumlike construction can be used to combine such codes. The existence of optimal (q, n, M) 1 codes C is discussed such that by puncturing the first coordinate of C one obtains a code with (q, 1)-subnorm 2     

Design of coded CPFSK modulation systems for bandwidth and energyefficiency

Consideration is given to the problems related to the design of M-ary continuous-phase frequency-shift keying (CPFSK) systems with modulation index h=J/M, combined with eternal rate r binary convolution encoders. The following questions are raised and answered: (1) how should different encoder-modulator systems be compared and how can comparable systems be recognized from the system parameters, i.e. M, h, and r?; (2) what are the limits on the information rate per unit bandwidth, versus signal-to-noise ratio, when reliable transmission is required?; (3) how does one choose the system parameters M, h, and r when the overall system has to achieve a specified performance?; and (4) how does one design the external rate r binary convolutional encoder to put in front of the M-ary CPFSK modulation system with h=J/M ? A simple approximation for the bandwidth of a CPFSK signal is given and shown to be sufficiently accurate for system design purposes. The design of the external convolutional encoder is carried out in a novel way that leads to fewer states in the combined encoder-modulator system and thus yields improved performance for a given demodulation-decoding complexity compared to previous approaches for the design of coded CPFSK systems