Binary cyclic [n,k] codes used for simultaneoustEC and SBD

In a hybrid forward-error-correction-automatic-repeat-request system one may wish to use an [n,k] cyclic code because its decoding algorithm is well known. An analytic formula is given for determining the fraction of undetectable single bursts of different lengths when a cyclic code is used for simultaneous single-burst-error detection and t-random error correction     

The (d,k) subcode of a linear block code

A simple technique employing linear block codes to construct (d,k) error-correcting block codes is considered. This scheme allows asymptotically reliable transmission at rate R over a BSC channel with capacity C_BSC provided R ⩽C_d,k-(1+C_BSC), where C_d,k is the maximum entropy of a (d,k ) source. For the same error-correcting capability, the loss in code rate incurred by a multiple-error correcting (d,k) code resulting from this scheme is no greater than that incurred by the parent linear block code. The single-error correcting code is asymptotically optimal. A modification allows the correction of single bit-shaft errors as well. Decoding can be accomplished using off-the-shelf decoders. A systematic (but suboptimal) encoding scheme and detailed case studies are provided     

Construction of t-EC/AUED codes

A t-EC/AUED code is constructed by appending a single check symbol from an alphabet S to each word of an n-bit binary t-EC code of even weight. Conditions are derived for the construction of S and a procedure is given which, for some values of t, n, leads to codes with fewer check bits than known codes with equivalent properties     

On the cutoff rate of a discrete memoryless channel with(d, k)-constrained input sequences

The cutoff rate of a discrete memoryless channel whose output sequences are from a (d, k) encoder is investigated. A rational rate (d, k) encoder is considered as a finite state machine and maximum-likelihood decoding is used to compute the cutoff rate. Some commonly used (d, k) codes, such as the rate 1/2 (1, 3) code with a two-state encoder, the IBM rate 2/3 (1, 7) code having a five-state encoder, and the IBM rate 1/2 (2, 7) code with a seven-state encoder, are used to illustrate the cutoff rate computation. Results are presented for both the binary symmetric channel (BSC) and the Gaussian noise channel. The performance of a decoder designed for noiseless transmission of (1, 3) code is compared to that of a maximum-likelihood decoder for the (1, 3) code. It is also shown that for the case of the Gaussian noise channel, a gain of about 1.7 dB in signal-to-noise ratio is possible by using 3-bit soft decisions over hard decisions     

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     

On the weight distribution of linear codes having dual distanced'⩾k

Using only the principle of inclusion and exclusion, the author derives a formula for the weight distribution of an [n,k ] code whose dual code has a minimum distance d'⩾k . The result yields a new condition on the weight distributions of a linear code and its dual which is necessary and sufficient for the code to be a maximum distance separable (MDS) code. Moreover, it shows how the weight distribution for linear MDS codes is obtained in an elementary manner     

An O(kn) algorithm for a circularconsecutive-k-out-of-n:F system

An O(k×n) algorithm is described for evaluating the reliability of a circular consecutive-k-out- n:F system     

Constructions and bounds for systematic tEC/AUED codes

Several methods of constructing systematic t-error correcting/all unidirectional error-detecting codes are described. These codes can be constructed by adding a tail to a linear t-error correcting code, but other constructions presented are more of an ad hoc nature. These codes will often be found as suitably chosen subsets of nonsystematic tEC/AUED codes. Further bounds on the word length of systematic tEC/AUED codes are derived, and extensive tables are given     

New multilevel codes over GF(q)

Set partitioning is applied to multidimensional signal spaces over GF(q), i.e., GFⁿ¹(q) (n1⩽q ), and it is shown how to construct both multilevel block codes and multilevel trellis codes over GF(q). Multilevel (n, k, d) block codes over GF(q) with block length n, number of information symbols k, and minimum distance d_min⩾d are presented. These codes use Reed-Solomon codes as component codes. Longer multilevel block codes are also constructed using q-ary block codes with block length longer than q+1 as component codes. Some quaternary multilevel block codes are presented with the same length and number of information symbols as, but larger distance than, the best previously known quaternary one-level block codes. It is proved that if all the component block codes are linear. the multilevel block code is also linear. Low-rate q-ary convolutional codes, word-error-correcting convolutional codes, and binary-to-q-ary convolutional codes can also be used to construct multilevel trellis codes over GF(q) or binary-to-q-ary trellis codes     

An O(kn)-time algorithm for computing thereliability of a circular consecutive-k-out-of-n:Fsystem

I. Antonopoulou and S. Papastavridis (1987) published an algorithm for computing the reliability of a circular consecutive-k-out-of-n:F system which claimed O (kn) time. J.S. Wu and R.J. Chen (1993) correctly pointed out that the algorithm achieved only O(kn²) time. The present study shows that the algorithm can be implemented for O(kn) time     

Closest coset decoding of |u|u+v| codes

The general concept of closest coset decoding (CCD) is presented, and a soft-decoding technique for block codes that is based on partitioning a code into a subcode and its cosets is described. The computational complexity of the CCD algorithm is significantly less than that required if a maximum-likelihood detector (MLD) is used. A set-partitioning procedure and details of the CCD algorithm for soft decoding of |u|u+v| codes are presented. Upper bounds on the bit-error-rate (BER) performance of the proposed algorithm are combined, and numerical results and computer simulation tests for the BER performance of second-order Reed-Muller codes of length 16 and 32 are presented. The algorithm is a suboptimum decoding scheme and, in the range of signal-to-noise-power-density ratios of interest, its BER performance is only a few tenths of a dB inferior to the performance of the MLD for the codes examined     

k-out-of-m system availability with minimum-costallocation spares

An optimization method for determining the number of spare units that should be allocated to a k-out-of-m system to minimize the system-spares cost yet attain the specified system availability is presented. The objective function for optimization is a nonlinear integer type. The optimization method is a variation of the simplex search technique used for continuous functions. The optimization problem is cast in a form that minimizes the system-spares cost, with the required system availability as an inequality constraint. Results obtained by using the proposed optimization technique, as well as the computation time required for optimization, are compared to those for methods developed specifically for dealing with nonlinear integer problems. The method is simple, easy to implement, and yet very effective in dealing with the spare allocation problem for k-out-of-m:F systems     

On computing MTBF for a k-out-of-n:G repairablesystem

It is often necessary to calculate the MTBF (mean time between failures) quickly in order to make timely design decisions. An important system for which such calculations must be made is a k-out-of- n:G parallel system with unlimited repair and exponential interfailure and repair times at the unit level. Although a general formula is known, it is not easily remembered or derived. A method for deriving a formula for MTBF in this situation that is easily reproduced quickly by remembering a few simple concepts is presented     

The efficiency of computing the reliability of k-out-of n systems

It is shown that the algorithm of R.S. Barlow and K.D. Heidtmann (ibid., vol.R-33, p.322-3, Oct. 1984) is more computationally efficient than those reported by S.P. Jain and K. Gopal (ibid., vol.R-34, p.144-6, June 1985) and S. Rai et al. (ibid., vol.R-36, p.261-5, June 1987). Efficiency is measured here by the number of multiplications     

Reliability of a k-out-of-n warm-standby system

A general closed-form equation is developed for system reliability of a k-out-of-n warm-standby system (dormant failures). The equation reduces to the hot and cold standby cases under the appropriate restrictions     

On the optimal design of k-out-of-n:G subsystems

For a k-out-of-n:G subsystem, the mathematical determination of the most economical number of components in the subsystem is sought. Optimal values of k (for fixed n) and n (for fixed k), which minimize the mean total cost of k-out-of-n:G subsystems, are given. A numerical example illustrates the results     

Design considerations for vertical δk directionalcoupler

Theoretical results relevant to the design of a vertical Δκ switch are presented. The principle of a Δκ switch is the modulation of the coupling length by the application of an even electrooptic perturbation on the coupling region. Power switching requires that ΔκL=π/2. The initial state can be tuned electrically. The coupling length and the change with the index perturbation depend on many factors, such as the thickness and the refractive index of the coupling layer. Based on an analytic solution of the eigenmodes and eigenindices of the symmetric structure, the author clarifies many of these dependencies and obtains the relationship between the switching length required for power crossover and the available index change. The merits of the Δκ switch are discussed, and its efficiency is compared with that of the conventional Δβ switch     

Lower bounds for q-ary covering codes

The authors prove combinatorial lower bounds for K_q (n,R), the minimal cardinality of any q-ary code of length n and covering radius R. Tables of lower bounds for K_q(n,R) are presented for q=3, 4, 5     

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