摘要:

We present a new parallel algorithm to solve the all-pairs shortest path problem in a given graph which is considerably faster than the most recently published algorithm [7] for the same problem. Next we propose a suitable VLSI systolic architecture to map our algorithm and evaluate the performance of the proposed architecture in terms of execution time and inter-processor communication time. We show that our implementation has O(log2n) execution time (compare-exchange time) and O(nlogn) communication time compared to O(nlogn) and O(n2) in [7].

DOI:10.1049/ip-e.1989.0012

出版商:IEE    

年代:1989

数据来源: IET

摘要:

The problem of optimal flow control of a general queuing network with random routing as a model of virtual circuit or datagram computer communication networks is presented by approximating the general channel transmission-time distributions by a maximum entropy model with known first-two moments. A Norton-maximum entropy algorithm is used to facilitate the optimisation process. It is shown that the flow control mechanism maximising the throughput, under a bounded time delay criterion, is of the window type (bang-bang control). The maximum number of packets in transit within the system (i.e. sliding window size) is derived in terms of the maximum allowed average time delay, flow equivalent parameters and maximum input rate. Consequently, the relationship between the maximum throughput and maximum time delay is determined. Numerical examples provide useful information on how critically the optimal throughput is affected by the random routing and the distributional form of the traffic patterns.

DOI:10.1049/ip-e.1989.0013

出版商:IEE    

年代:1989

数据来源: IET

摘要:

In the paper we are concerned with a method for choosing the initial approximations to the zeros of a polynomial. Methods for finding all the zeros of a polynomial simultaneously, which can be considered modified a Newton Method, have been reported by quite a few authors. The initial approximations for these simultaneous methods take much CPU-time to find all the zeros of a polynomial, since CPU time depends mostly on the situation of the initial distribution of zeros. Here, a new method for choosing the initial approximations is proposed, which simplifies Aberth's method for choosing the initial approximations, and reduces the CPU time to obtain initial approximations and find all the zeros of a polynomial. In this method, the quasistandard deviation obtained by the degree and coefficients of a polynomial is defined, and the initial approximations to zeros are given by this quasi-standard deviation. A comparison between Aberth's method and our proposing method for choosing the initial approximations is made through numerical experiments.

DOI:10.1049/ip-e.1989.0015

出版商:IEE    

年代:1989

数据来源: IET

摘要:

In a wide sense, easy test generation (ETG) circuits can be considered as design for testability (DFT) circuits. However most of the DFT techniques presented so far in the literature are attempts to ease test application. Major disadvantages with these DFT techniques are degradation of circuit performance, and often the requirement of a long and continuous test mode. However, an ETG circuit attempts to make test generation easier without any significant degradation of circuit performance, and the test mode can be divided into pieces to fit the requirement of real-time systems. The paper presents two important types of PLA design techniques which reduce the computational complexity for test generation. An O(n) ETG PLA is defined, and a sufficient condition for O(n2) ETG PLAs is also obtained. It is shown that the easily testable PLAs introduced by Bozorgui-Nesbat and McCluskey are O(n2) ETG PLAs.

DOI:10.1049/ip-e.1989.0016

出版商:IEE    

年代:1989

数据来源: IET

摘要:

This paper presents an analysis and synthesis of bent sequences in the Hadamard domain. It is shown that the basic bent sequence of length 4kis threshold realizable using 3knonzero weights and the realisation of arbitrary bent sequences is also discussed.

DOI:10.1049/ip-e.1989.0017

出版商:IEE    

年代:1989

数据来源: IET

摘要:

Recognition of partially-occluded three dimensional (3D) objects is an essential task for many industrial applications of machine vision. In the paper, the authors tackle the problem of 3D object recognition using depth map representations. The method consists of two stages: the first is a subtemplate matching scheme that breaks down the object to be recognised into surface patches, called subtemplates, for matching. A special spherical windowing scheme is used to extract the correct patches. The algorithm estimates the orientation of a surface patch and performs the matching using mainly the outer boundary of the patch. In the second stage, dynamic programming (DP) is used to obtain a constrained optimal solution. It selects, among a number of probable matches resulting from the subtemplate matching stage, an optimal consistent set of matches. Experimental results show that the algorithm works well on objects that are truly irregularly shaped. Great reduction in computing time can also be achieved if the search regions for matching can be restricted to the neighbourhoods of extremal points or easily detected features.

DOI:10.1049/ip-e.1989.0018

出版商:IEE    

年代:1989

数据来源: IET

摘要:

Programmable array logic (PAL) devices can be used for realising both combinational and sequential circuits. The final behaviour of a PAL chip is determined by the fuse pattern in this chip. This paper presents a systematic procedure for generating a minimal test set to examine whether a programmed chip functions as expected. The upper bound of the size of a test set generated by the proposed procedure is also derived.

DOI:10.1049/ip-e.1989.0019

出版商:IEE    

年代:1989

数据来源: IET

摘要:

The paper presents the design of the distributed multimedia kernel system (DMKS) developed for supporting multimedia applications based on a distributed approach. It adopts the device independent GKS concepts and extends them to include images and text from databases using a reference method, so that it is not necessary for the application program to have direct contact with the actual contents. The task of manipulating the real image and text data can be left until the presentation stage which is performed on the workstation. The various advantages offered with such an approach to multimedia integration are described, and details of the implementation of DMKS are given to illustrate the practical aspects of the system.

DOI:10.1049/ip-e.1989.0020

出版商:IEE    

年代:1989

数据来源: IET

摘要:

The major advantage of the binary coded decimal (BCD) system is in providing rapid binary-decimal conversion. The shortcoming of the BCD system is that BCD arithmetic operations are often slow and require complex hardware. The performance of BCD operations can be improved through a redundant binary coded decimal (RBCD) representation which leads to carry-free operations. This paper introduces the VLSI design of an RBCD adder. The design consists of two small PLA's and two 4-bit binary adders for one digit of the RBCD adder. The addition delay is constant forn-digit RBCD addition (no carry propagation delay). The VLSI time and space complexities of the design as well as its layout are presented. In addition, we show that BCD to RBCD conversion can be carried out in a constant time. However, RBCD to BCD conversion requires a carry-ripple operation which can be accomplished with a complexity equivalent to that of the carry-look-ahead circuitry.

DOI:10.1049/ip-e.1989.0021

出版商:IEE    

年代:1989

数据来源: IET