Design and analysis of a contention-based lookahead reservationprotocol on a multichannel local area network

The contention-based lookahead reservation (CLAR) protocol can provide fast circuit-switching services that are particularly advantageous for networks supporting integrated services. The delay and throughput performance for message transmission are obtained, and they agree closely with that obtained by simulation. The delay performance of CLAR is similar to that of the M-CSMA protocol for an M-channel network, but only CLAR can give a stable maximum throughput of (M-1)/M independent of the cable length. Moreover, CLAR requires only two sets of transceivers, while M-CSMA requires M. The lookahead reservation technique can provide 9% throughput increase for fixed-size messages and 19% for geometrically distributed messages     

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     

Bounds for abnormal binary codes with covering radius one

The normality of binary codes is studied. The minimum cardinality of a binary code of length n with covering radius R is denoted by K(n,R). It is assumed that C is an (n,M)R code, that is, a binary code of length n with M codewords and covering radius R. It is shown that if C is an (n,M)1 code, then it is easy to find a normal (n ,M)1 code by changing C in a suitable way, and that all the optimal (n,M)1 codes (i.e. those for which M=K(n,1)) are normal and their every coordinate is acceptable. It is shown that if C is an abnormal (n,M) code, then n⩾9, and an abnormal (9118)1 code which is the smallest abnormal code known at present, is constructed. Lower bounds on the minimum cardinality of a binary abnormal code of length n with covering radius 1 are derived, and it is shown that if an (n,M)1 code is abnormal, then M⩾96     

On linear structure and phase rotation invariant properties ofblock M-PSK modulation codes

Two important structural properties of block M(=2^' )-ary PSK modulation codes, linear structure and phase symmetry, are investigated. An M-ary modulation code is first represented as a code with symbols from the integer group S_M-PSK=(0,1,2,---,M-1) under modulo-M addition. Then the linear structure of block M-PSK modulation codes over S_M-PSK with respect to modulo- M vector addition is defined, and conditions are derived under which a block M-PSK modulation code is linear. Once the linear structure is developed, the phase symmetry of block M-PSK modulation codes is studied. In particular, a necessary and sufficient condition for a block M-PSK modulation code that is linear as a binary code to be invariant under 2^h/180°M phase rotation, for 1⩽h⩽l is derived. Finally, a list of short 8-PSK and 16-PSK modulation codes is given, together with their linear structure and the smallest phase rotation for which a code is invariant     

Asymptotic performance of M-ary orthogonal signals inworst case partial-band interference and Rayleigh fading

It is shown that for worst-case partial-band jamming, the error probability performance (for fixed E_b/N_I) becomes worse with increasing M for (M>16). The asymptotic probability-of-error is not zero for any E_b/N _I(>ln 2), but decreases inverse linearly with respect to it. In the fading case, the error-probability performance (for fixed E_b/N₀) improves with M for noncoherent detection, but worsens with M for coherent detection. For large E_b/N₀ the performance of the Rayleigh fading channel asymptotically approaches the same limit as the worst case partial-band jammed channel. However, for values of M at least up to 4096, the partial-band jammed channel does better. While it is unlikely that an M-ary orthogonal signal set with M>1024 will be used in a practical situation, these results suggest an important theoretical problem; namely, what signal set achieves reliable communication     

A simple derivation of the power spectrum of full-response CPM andsome of its properties

Using a new representation for continuous-phase modulated (CPM) signals, it is shown how a closed-form expression for the power spectral density of full-response M-ary CPM with modulation index J /M can be obtained by straightforward computations. This result is used to provide an explanation of the fact that this power spectral density depends only on J and not on M     

Fast cosine transform of Toeplitz matrices, algorithm andapplications

A fast algorithm for the discrete cosine transform (DCT) of a Toeplitz matrix of order N is derived. Only O(N log N)+O(M) time is needed for the computation of M elements. The storage requirement is O(N). The method carries over to other transforms (DFT, DST) and to Hankel or circulant matrices. Some applications of the algorithm are discussed     

Scattering by a multilayer chiral cylinder

An efficient recursive eigenfunction solution for the problem of scattering by a multilayer chiral circular cylinder, with or without a surface impedance center cylinder, is presented. For an M layer cylinder, the solution requires the multiplication of M4×4 matrices, versus the solution of a 4M×4M matrix equation in a standard approach. The problem of a transverse electric (TE) incident plane wave differs from that of a transverse magnetic (TM) wave only by a plus/minus sign at one step in the solution. The addition of the surface impedance center cylinder requires only one additional matrix multiplication. Numerical results, including echo width and internal fields, are presented for several sample cylinders     

Asymptotically optimal classification for multiple tests withempirically observed statistics

The decision problem of testing M hypotheses when the source is Kth-order Markov and there are M (or fewer) training sequences of length N and a single test sequence of length n is considered. K, M, n, N are all given. It is shown what the requirements are on M , n, N to achieve vanishing (exponential) error probabilities and how to determine or bound the exponent. A likelihood ratio test that is allowed to produce a no-match decision is shown to provide asymptotically optimal error probabilities and minimum no-match decisions. As an important serial case, the binary hypotheses problem without rejection is discussed. It is shown that, for this configuration, only one training sequence is needed to achieve an asymptotically optimal test     

Rate-compatible punctured convolutional codes (RCPC codes) andtheir applications

The concept of punctured convolutional codes is extended by punctuating a low-rate 1/N code periodically with period P to obtain a family of codes with rate P/(P+l), where l can be varied between 1 and (N-1)P. A rate-compatibility restriction on the puncturing tables ensures that all code bits of high rate codes are used by the lower-rate codes. This allows transmission of incremental redundancy in ARQ/FEC (automatic repeat request/forward error correction) schemes and continuous rate variation to change from low to high error protection within a data frame. Families of RCPC codes with rates between 8/9 and 1/4 are given for memories M from 3 to 6 (8 to 64 trellis states) together with the relevant distance spectra. These codes are almost as good as the best known general convolutional codes of the respective rates. It is shown that the same Viterbi decoder can be used for all RCPC codes of the same M. the application of RCPC codes to hybrid ARQ/FEC schemes is discussed for Gaussian and Rayleigh fading channels using channel-state information to optimise throughput     

Offset DPSK with differential phase detector in satellite mobilechannel with narrow-band receiver filter

An expression is derived for the error probability of M-ary offset differential phase-shift keying (DPSK) with the differential phase detector and narrowband receiver filter in the satellite mobile (Rician) channel, which includes as special cases the Gaussian and land mobile (Rayleigh) channels. The error probability is computed as a function of various system parameters for M=2, 4, and 8 symbols and third-order Butterworth receiver filter. Both symmetric and conventional DPSK systems are considered. The optimal normalized bandwidth is close to 1.0. Symmetric and conventional DPSK differ significantly in error probability only for M=2 and in the lower range filter bandwidth. In most cases, symmetric DPSK outperforms conventional DPSK. This was particularly noted when the time delay between the specular and diffused signal components was taken into account     

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     

M-ary frequency shift keying withlimiter-discriminator-integrator detector in satellite mobile channelwith narrowband receiver filter

An expression is derived for the error probability of M-ary frequency shift keying with a limiter-discriminator-integrator detector and a narrowband receiver filter in the satellite mobile channel. This channel contains, as special cases, the Gaussian and Rayleigh (land mobile) channels. The error probability is computed as a function of various system parameters for M=2, 4, 8 symbols and a third-order Butterworth receiver filter     

Repeated convolutional codes for high-error-rate channels

An error-correction scheme for an M-ary symmetric channel (MSC) characterized by a large error probability p_e is considered. The value of p_e can be near, but smaller than, 1-1/M, for which the channel capacity is zero, such as may occur in a jamming environment. The coding scheme consists of an outer convolutional code and an inner repetition code of length m that is used for each convolutional code symbol. At the receiving end, the m inner code symbols are used to form a soft-decision metric, which is passed to a soft-decision decoder for the convolutional code. The effect of finite quantization and methods to generate binary metrics for M>2 are investigated. Monte Carlo simulation results are presented. For the binary symmetric channel (BSC), it is shown that the overall code rate is larger than 0.6R₀, where R₀ is the cutoff rate of the channel. New union bounds on the bit error probability for systems with a binary convolutional code on 4-ary and 8-ary orthogonal channels are presented. For a BSC and a large m, a method is presented for BER approximation based on the central limit theorem     

Performance of fast frequency hopped noncoherent MESK witha fixed hop rate under worst case jamming

The performance of fast-frequency-hopped M-ary frequency-shift keying with a fixed hop rate is evaluated, utilizing the Chernoff union bound method. The performance criterion used is a throughput measure i.e., an information rate sustained by a system for a given bit error rate, normalized by the hop rate. Both uncoded and coded systems are considered. It is shown using the cutoff rate argument that coding can provide a few dB gain in throughput. This is confirmed by the performance evaluation of various convolutional and block codes. Both partial-band noise jamming and multitone jamming with one tone per M -ary band are considered. Jamming parameters are assumed to be the worst case against the coding channel. Determination of the optimum M is also addressed     

A fast time slot assignment algorithm for TDM hierarchicalswitching systems

A fast (polynomial time) network-flow-based algorithm is presented for time slot assignment in time-division-multiplexing (TDM) hierarchical switching systems. For a nonblocking time-multiplexed central switch the algorithm produces a conflict-free time slot assignment for a given frame (whenever this is possible) on O(M ⁵) time, where M is the system size     

Markov-modulated flow model for the output queues of a packetswitch

The output queues of an M×N packet switch are studied using a Markov-modulated flow model. The switching element is a central server which sequentially routes packets from the inputs to the outputs. The focus is on systems in which the server speed is such that the bulk of the queuing takes place in the output queues. The conventional point process approach neglects the impact of switching and transmission time. An attempt is made to account for these finite system speeds by using a Markov-modulated continuous flow to approximate the arrival process to an output queue. This model captures the dependency between arrivals at different outputs and reflects the fact that packet arrivals and departures are not instantaneous. The output queue content distribution is obtained, for both infinite and finite buffer systems, from the spectral expansion of the solution of a system of differential equations. Numerical examples and comparisons with the results of an M/M/1 approximation are presented     

Identities and approximations for the weight distribution of q-ary codes

An explicit formula is derived that enumerates the complete weight distribution of an (n, k, d) linear code using a partially known weight distribution. An approximation formula for the weight distribution of q-ary linear (n, k , d) codes is also derived. It is shown that, for a given q-ary linear (n, k, d) code, the ratio of the number of codewords of weight u to the number of words of weight u approaches the constant Q=q ^-(n-k) as u becomes large. The error term is a decreasing function of the minimum weight of the dual. The results are also valid for nonlinear (n, M, d) codes with the minimum weight of the dual replaced by the dual distance     

Limiter-discriminator detection of a coherent optical heterodyneM-ary CPFSK receiver

The performance of a coherent optical M-ary continuous-phase frequency-shift-keying (CPFSK) receiver using limiter-discriminator (L-D) detection is investigated. It is shown that L-D detection of CPFSK optical signals offers the best performance for a large normalized IF beat spectral linewidth, ΔνT. When the modulation index is unity, the receiver is immune to laser phase noise and can produce (M/4) exp (-SNR) symbol error probability, which may be considered as the upper bound if the optimal modulation index is used (SNR is the signal-to-noise ratio per symbol). Optimum modulation indexes are 0.8 and 1 at ΔνT=1% and ΔνT=2%, respectively, for M=4, 8, and 16