Worst-case interactive communication. I. Two messages are almostoptimal

The reduction in communication achievable by interaction is investigated. The model assumes two communicators: an informant having a random variable X, and a recipient having a possibly dependent random variable Y. Both communicators want the recipient to learn X with no probability of error, whereas the informant may or may not learn Y. To that end, they alternate in transmitting messages comprising finite sequences of bits. Messages are transmitted over an error-free channel and are determined by an agreed-upon, deterministic protocol for (X,Y) (i.e. a protocol for transmitting X to a person who knows Y). A two-message protocol is described, and its worst case performance is investigated     

Two-dimensional consecutive-k-out-of-n:F models

A two-dimensional version of the consecutive-k-out-of-n:F model is considered. Bounds on system failure probabilities are determined by comparison with the usual one-dimensional model. Failure probabilities are determined by simulation for a variety of values of k and n     

Periodic-replacement models with threshold levels

The authors suggest five replacement policies where a unit is replaced at periodic times, jT(j=1,2, . . .), and the replacement cost is expensive when some number of events occurring in (0,t) is greater than a threshold level. The usual models for inspection, periodic replacement, block replacement, parallel systems, and cumulative damage can be transformed into replacement models with threshold levels. The mean cost-rate of each model is obtained, using well-known results of reliability theory. The optimum replacement time which minimizes the cost-rate of an inspection model is discussed and shown to exist uniquely     

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     

State-dependent routing on symmetric loss networks with trunkreservations. I

The aggregated-least-busy-alternative (ALBA), a distributed, state-dependent, dynamic routing strategy for circuit-switched loss networks is discussed. The networks considered are symmetric and fully connected. The offered calls form Poisson streams, and routes have at most two links. In ALBA(K), the states of each link are lumped into K (K⩾2) aggregates, and the route of each call is determined by local information on the aggregate states of the links of the alternate routes at the time of the call's arrival. The last aggregate is always the set of states reserved for direct traffic. A fixed-point model for ALBA(K) for general K is presented. The particular case of ALBA in which there is no aggregation is least busy alternative (LBA); ALBA(2) represents the other extreme of aggregation. Simulation and analytic results for LBA are compared. An asymptotic scaling based on the fixed-point models is also discussed. It is shown that there is a dichotomy in network behavior: if the offered traffic is below a threshold, then the network loss probability decreases exponentially with increasing network size, and above the threshold, performance is poor     

Systolic arrays for the discrete Hartley transform

Recently, R.N. Bracewell (1983) introduced the discrete Hartley transform (DHT) as an alternative to the discrete Fourier transform (DFT). Two linear systolic array models for the (DHT) are derived. One model requires O(2N-1) in the computational phase and O(N) in the preloading phase. The other model requires O(2N-1) in the computational phase and O(N) in the output phase. A square systolic array for two-dimensional DHT is also constructed by combining the individual advantages of each model. The CORDIC algorithm is proposed as an alternative to conventional multipliers. To speed up the systolic array, two-level pipelining with CORDIC is also possible     

Maximum-rank array codes and their application to crisscross errorcorrection

A μ-[n×n,k] array code C over a field F is a k-dimensional linear space of n×n matrices over F such that every nonzero matrix in C has rank ⩾μ. It is first shown that the dimension of such array codes must satisfy the Singleton-like bound k⩽n(n-μ+1). A family of so-called maximum-rank μ-[n×n,k=n ( n-μ+1)] array codes is then constructed over every finite field F and for every n and μ, 1⩽μ⩽n . A decoding algorithm is presented for retrieving every Γ∈C, given a received array Γ+E, where rank (E)+1⩽(μ-1)/2. Maximum-rank array codes can be used for decoding crisscross errors in n×n bit arrays, where the erroneous bits are confined to a number t of rows or columns (or both). This construction proves to be optimal also for this model of errors. It is shown that the behavior of linear spaces of matrices is quite unique compared with the more general case of linear spaces of n×n. . .×n hyper-arrays     

Performance analysis of the Josephson DC flip-flop

A linear analytical model of the Josephson DC flip-flop is proposed. The model describes both the Baechtold's and Hebard's flip-flops. The output signal line is treated as either a single inductance or a transmission line with a finite impedance. The former leads to the lumped model, while the latter leads to the distributed model. The lumped model gives the load condition for successful reset. This is given as a relationship between the CR and L/ R time constant, where C is the device capacitance, L is the load inductance, and R is the load resistance. The switching delay is also described as a linear function of the CR and L/R. With the distributed circuit model, the load condition for successful reset is Z₀⩾R. Minimum delay is obtained at Z₀=R. Grounding one end of the output signal line reduces the delay more than the nongrounded configuration. The scalar relationship of the switching delay and the power consumption to the design rule is discussed     

A storage-efficient method for solving banded Toeplitz systems

A method is presented for solving the banded Toeplitz system Tx=y by decomposing T into its asymptotic upper and lower triangular factors (which are banded and Toeplitz) and a rank-p correction matrix, where p is the bandwidth of T. This way of representing T requires only O(p²) words of storage and allows computation of x in O(2Np) operations. A similar method is presented for the case in which T is bi-infinite and y is zero outside a finite region     

Binary [18,11]2 codes do not exist-Nor do [64,53]2 codes

A binary, linear block code C with block length n and dimension n is commonly denoted by [n, k] or, if its minimum distance is d, by [n, k,d]. The code's covering radius r(C) can be defined as the smallest number r such that any binary column vector of length (n-k) can be written as a sum of r or fewer columns of a parity-check matrix of C. An [n,k] code with covering radius r is denoted by [n,k]r. R.A. Brualdi et al., (1989) showed that l(m,r) is defined to be the smallest n such that an [n,n-m]r code exists. l(m,2) is known for m⩽6, while it is shown by Brualdi et al. that 17⩽l(7,2)⩽19. This lower bound is improved by A.R. Calderbank et al. (1988), where it is shown that [17,10]2 codes do not exist. The nonexistence of [18,11]2 codes is proved, so that l(7,2)=19. l[7.2)=19 is established by showing that [18,11]2 codes do not exist. It is also shown that [64,53]2 codes do not exist, implying that l(11,2)⩾65     

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     

Optimization of signal sets for partial-response channels. II.Asymptotic coding gain

For Pt. I see ibid., vol.37, no.5, p.1327-141 (1991). For a linear, time-invariant, discrete-time channel with a given transfer function H(f), and information rate R bits/ T, where T is the symbol interval, an optimal signal set of length K is defined to be a set of 2^RK inputs of length K that maximizes the minimum l₂ distance between pairs of outputs. The author studies the minimum distance between outputs, or equivalently, the coding gain of optimal signal sets as K→∞. He shows how to estimate the coding gain, relative to single-step detection, of an optimal signal set length K when K is large     

Balancing sets of vectors

For n>0, d⩾0, n≡d (mod 2), let K(n, d) denote the minimal cardinality of a family V of ±1 vectors of dimension n, such that for any ±1 vector w of dimension n there is a v∈V such that |v- w|⩽d, where v-w is the usual scalar product of v and w. A generalization of a simple construction due to D.E. Knuth (1986) shows that K(n , d)⩽[n/(d+1)]. A linear algebra proof is given here that this construction is optimal, so that K(n, d)-[n/(d+1)] for all n≡d (mod 2). This construction and its extensions have applications to communication theory, especially to the construction of signal sets for optical data links     

Self-avoiding random loops

A random loop, or polygon, is a simple random walk whose trajectory is a simple Jordan curve. The study of random loops is extended in two ways. First, the probability P_n(x,y) that a random n-step loop contains a point (x,y) in the interior of the loop is studied, and (1/2, 1/2) is shown to be (1/2)-(1/ n). It is plausible that P_n(x,y) tends toward 1/2 for all ( x,y), but this is not proved even for (x,y)=(3/2,1/2) A way is offered to simulate random n-step self-avoiding loops. Numerical evidence obtained with this simulation procedure suggests that the probability P_n (3/2,1/2)≈(1/2)-(c/n), for some fixed c      

A maintenance policy for repairable systems based on opportunisticfailure-rate tolerance

An opportunistic hazard rate replacement policy for a repairable system with several types of units is presented. A unit is repaired at failure when the hazard rate falls in (0, L-u). A unit is replaced at failure when the hazard rate falls in (L-u , L). An operating unit is replaced when its hazard rate reaches L. When a unit is replaced because its hazard rate reaches L, all operating units with their hazard rates falling in (L-u, L) are replaced. The long-run mean cost rate as a function of L and u is derived. Optimal L and u are obtained to minimize the total maintenance cost rate. Application and analysis of results are demonstrated through a numerical example. The maintenance model is designed for a system with multitype units. Each type has its own increasing hazard rate. Units are repaired or replaced depending on their hazard rate at a failure or active replacement of another unit. The repair interval, replacement limit, and replacement tolerance are determined to yield the optimal total maintenance cost rate     

A generalization of consecutive-k-out-of-n:Fsystems

A linear (m, n)-lattice system consists of m ·n elements arranged like the elements of a (m ,n)-matrix, i.e. each of the m rows includes m elements, and each of the n columns includes m elements. A circular (m,n)-lattice system consists of m circles (centered at the same point) and n rays. The intersections of the circle and the rays represent the elements, i.e. each of the circles includes n elements and each of the rays has m elements. A (linear or circular) (m, n)-lattice system is a (linear or circular) connected-X-out-of-(m,n):F lattice system if it fails whenever at least one subset of connected failed components occurs which includes failed components connected in the meaning of connected-X. The paper presents some practical examples and the reliability formulas of simple systems using results of consecutive-k-out-of-n:F systems     

Parameter correlation and modeling of the power-law relationship inMOSFET hot-carrier degradation

Correlation between the parameters A and n in the empirical hot-carrier degradation formula, parametric shift=A ×tⁿ, is reported for both n- and p-channel MOSFETs fabricated with various submicrometer processing technologies. Analysis of data indicates that A increases with a decreasing value of n, satisfying a simple exponential relationship, A=α×exp(-βn), within the stress conditions considered. A phenomenological model to explain this relation is provided. Implications for device lifetime prediction under different hot-carrier injection stress conditions are also indicated     

Improved sphere bounds on the covering radius of codes

The sphere bound is a trivial lower bound on K(n,R), the minimal cardinality of any binary code of length n and with covering radius R. By simple arguments it is considerably improved, to K(n,1)⩾2 ⁿ/n for n even. A table of lower and upper bounds on K(n,R) for n⩽33, R ⩽10 is included     

On the performance of an ATM switch with multichannel transmissiongroups

A routing architecture applying the concept of multichannel transmission groups (MCTGs) for ATM systems is proposed. A queuing analysis of an internally nonblocking ATM switch employing this MCTG concept with partially shared output buffers is presented. The analysis is based on the discrete-time DA///D/c /B queuing model. Both bulk input traffic bulk-size distribution (A) and deterministic traffic (D₁ +. . .+D_N) are considered. The impact of switch speedup on the performance is also taken into account. It is shown that the MCTG architecture yields better performance in terms of delay and cell loss probability than its single channel counterpart. It is also found that the switch speedup required to closely approximate the optimal performance obtained by having the switch fabric run N times as fast as the input and output channels, where N is the size of the switch, is rather small compared to N. This makes the practical realization of the proposed switch architecture feasible     

Average waiting time assignment. I. The single link case

A system is considered in which V users are competing for the transmission capacity of a link. The users generate messages in a Poisson manner. The message length distribution of each user is arbitrary and may differ for different users. The objective is to investigate nonpreemptive service-time independent scheduling as a means of selectively controlling the average waiting time of the users. The average waiting time assignments that can be realized are characterized. They can be used to establish, in O(V log V) computations, whether a given average waiting time assignment is feasible. The proof of the result relies on a universal scheduling strategy which is simple, is time-invariant, and can be used to realize any feasible average waiting time assignment. A waiting time cost function is associated with each user in order to investigate the problem of finding a nonpreemptive scheduling strategy that minimizes the overall waiting time cost. A set of optimality conditions is given for this problem, and an algorithm is constructed solving it in O (V) log V steps. With a simple modification, the algorithm also solves the problem of finding a nonpreemptive scheduling strategy that minimizes the lexicographic ordering of the waiting time costs. Results are extended to the preemptive case