Home
>
Journals & magazines
>
IEE Proceedings - Computers and Digital Technique...
>
Volume 145
Issue 1
IEE Proceedings - Computers and Digital Techniques
Volume 145, Issue 1, January 1998
Volumes & issues:
Volume 145, Issue 1
January 1998
-
- Author(s): D. Johnson and V. Akella
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 1, p. 1 –8
- DOI: 10.1049/ip-cdt:19981770
- Type: Article
- + Show details - Hide details
-
p.
1
–8
(8)
An asynchronous adder can take advantage of the shorter carry propagation chains that occur in practice and exhibit a data-dependent computation delay. Basically, an asynchronous adder has a mechanism to announce early completion by detecting when it is done. Such an adder is extremely useful in asynchronous implementation of computing structures. In this paper we evaluate the designs tradeoffs of well-known asynchronous adder configurations based on ripple-carry and carry lookahead topologies. We show that, using complex gates, carry lookahead asynchronous adders can be realised that outperform ripple-carry asynchronous adders, both in average-case delay and worst-case delay without increasing the area and power consumption. The underlying timing assumptions and applications of the adder in asynchronous pipelines (micropipelines) are also discussed. - Author(s): N. Nassif and N. Bagherzadeh
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 1, p. 9 –14
- DOI: 10.1049/ip-cdt:19981699
- Type: Article
- + Show details - Hide details
-
p.
9
–14
(6)
Since its introduction in the literature, the star interconnection network has become a popular architecture for connecting parallel processors. It compares favourably with the famous hypercube as far as basic network attributes are concerned. Its degree and diameter are sublogarithmic with respect to the total number of processors and it enjoys fault tolerance and symmetry properties. It remains to be seen whether known efficient algorithms that have been developed for other interconnection network architectures can be implemented efficiently on the star, and how well these will perform in the presence of faults in the network. The authors address this question for image analysis algorithms, specifically for the image component labelling problem. Component labelling is a fundamental and basic task common to virtually all image analysis problems. The star interconnection network is modelled with a graph, an innovative grid embedding into the star is used and an efficient algorithm to solve the image component labelling problem on the star graph is developed. The authors then analyse the performance of the algorithm in the fault-free star graph. - Author(s): W.-B. Lee and C.-C. Chang
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 1, p. 15 –18
- DOI: 10.1049/ip-cdt:19981599
- Type: Article
- + Show details - Hide details
-
p.
15
–18
(4)
Group signatures, introduced by Chaum and Heyst, allow individual members to make signatures on behalf of the group while providing anonymity. All previously proposed schemes, as far as we know, are not very efficient in terms of computational, communication and storage costs. In the paper, we describe a novel group signature that is used to reflect and project the actual needs arising from practical applications. This new scheme is very efficient compared to previous results. The security of the newly proposed scheme is based on the discrete logarithm problem. - Author(s): A.E. Bashagha and M.K. Ibrahim
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 1, p. 19 –26
- DOI: 10.1049/ip-cdt:19981771
- Type: Article
- + Show details - Hide details
-
p.
19
–26
(8)
It is well known that the existing two's complement radix-2k division methods require a set of full wordlength comparisons of the multiples of the divisor against the shifted remainder. For fast division, these comparisons should be implemented in parallel. Therefore, a huge area is required to implement such high radix division. The paper presents a novel two's complement radix-2k division algorithm. For the first time, the set of full precision additions are replaced with a set of (k + 2)-bit additions. Then, only two full wordlength additions are required to select the k-bit quotient digit out of two values selected by the (k + 2)-bit comparisons. As a result, the required area is reduced by 77% with the speed of the two algorithms are nearly the same. Moreover, the speed of the new algorithm can be made faster by using one of the known fast adders because only two full precision additions (rather than the set of the full precision additions) per radix-2k quotient digit is required. - Author(s): P.-J. Chuang
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 1, p. 27 –32
- DOI: 10.1049/ip-cdt:19981702
- Type: Article
- + Show details - Hide details
-
p.
27
–32
(6)
An interconnection network with redundant paths is desirable for high-performance multiprocessor systems owing to its ability to tolerate faults by routing requests through alternative paths. The gamma interconnection network (GIN) provides a unique path from any source (S) to a destination (D) when S equals D and the multiple paths between certain (S, D) pairs share a single common route for many stages, yielding unsatisfactory terminal reliability. To enhance the terminal reliability of the GIN, a modified GIN is proposed, the Balanced GIN (BGIN), whose connecting patterns between stages exhibit a balance feature. Due to the unique balance feature of its connecting patterns, the BGIN is able to provide multiple disjoint paths between any communication pair and thus can tolerate any arbitrary single fault. Without increasing hardware complexity or degrading performance, the BGIN demonstrates enhanced terminal reliability when compared with other modified GINs. - Author(s): Z. Shao
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 1, p. 33 –36
- DOI: 10.1049/ip-cdt:19981773
- Type: Article
- + Show details - Hide details
-
p.
33
–36
(4)
The paper proposes two new digital signature schemes, the security of which is based on the difficulties of computing discrete logarithms and factoring, the performance of which is similar to those of the original ElGamal signature scheme and the Harn signature scheme. The paper also considers some possible attacks, and shows that the two schemes are more secure than the original ElGamal signature scheme and the Harn signature scheme. - Author(s): J.-S. Cherng ; S.-J. Chen ; J.-M. Ho
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 1, p. 37 –45
- DOI: 10.1049/ip-cdt:19981703
- Type: Article
- + Show details - Hide details
-
p.
37
–45
(9)
A novel module-migration bipartitioner (MMP) for VLSI circuits is proposed. MMP uses an efficient module migration process, which can relax the size constraints temporarily and intensify the capability of escaping from local optima, as its iterative improvement mechanism. Besides evaluating the same module gain when performing the Fiduccia–Mattheyses (FM) algorithm for selecting the module to move, MMP also examines the connection strengths between modules, thus capturing more global implications of module moving. Moreover, MMP is robust with a self-adjusted probabilistic function set which can reduce the sensitivity of some key parameters. Experiments on circuits allowing different deviations from exact bipartition show that MMP is stable on solution quality and that it not only performs much better than FM, but also outperforms many state-of-the-art bipartitioners. - Author(s): N. Zhuang and P.Y.K. Cheung
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 1, p. 47 –51
- DOI: 10.1049/ip-cdt:19981700
- Type: Article
- + Show details - Hide details
-
p.
47
–51
(5)
The paper describes an algorithm which combines logic synthesis and technology mapping specifically for Xilinx's XC6200, a new family of fine-grain, dynamically reconfigurable FPGA. The algorithm employs a BDD representation of the logic function and a genetic algorithm (GA) is used to find a good decomposition variable ordering. The algorithm also exploits the architectural features of the XC6200 to minimise the number of cells required to implement a given function. Results on benchmark circuits show that the new algorithm performs similarly or better than other synthesis tools in a large number of cases. - Author(s): K. Chakrabarty and J.P. Hayes
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 1, p. 52 –62
- DOI: 10.1049/ip-cdt:19981769
- Type: Article
- + Show details - Hide details
-
p.
52
–62
(11)
Many common logic circuits such as adders, parity checkers and multiplexers realise Boolean functions that are true for exactly half their input combinations, and false for the other half; we refer to such functions as balanced. Recently, these functions have been shown to be very useful for testing logic circuits, and for data encryption in cryptography. Here, we present a general theory of balanced Boolean functions. We derive a necessary and sufficient condition for balance by establishing an equivalence between a balanced function f(X) and a bijection from X to itself. We then analyse the conditions under which functional compositions preserve balance, and examine some specific balance-preserving decompositions. A new characterisation of functional completeness in terms of balance is presented. Finally, we address the problem of counting equivalence classes of balanced functions. - Author(s): M. Kjelsø ; M. Gooch ; S. Jones
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 1, p. 63 –67
- DOI: 10.1049/ip-cdt:19981797
- Type: Article
- + Show details - Hide details
-
p.
63
–67
(5)
The authors present results from an investigation into the characteristics of memory-data in Unix applications. The memory-data analysis shows a number of surprising characteristics and reveals substantial similarities across applications. It is also shown that memory-data typically compresses to half the original volume. The characteristics of the memory-data, as well as the results on compression, are of interest to researchers connected with computer systems design in general, and resource management in particular. - Author(s): I. Cahit
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 1, p. 68 –72
- DOI: 10.1049/ip-cdt:19981772
- Type: Article
- + Show details - Hide details
-
p.
68
–72
(5)
A deadlock detection method based on the use of the resource allocation graph is presented. The method is different from the existing deadlock avoidance techniques in that the original directed resource allocation graph is first transformed into an undirected (0 1)-labelled graph in which the deadlock would occur only if a cycle has been labelled alternatingly with 0s and 1s. The algorithm is applicable to the centralised and distributed systems. Another feature of the algorithm is that it can be used in distributed systems, since the detection of deadlock is carried out by an interprocess communications which is basically the exchange of 0 and 1 bits among the processes. The worst case cost of the algorithm is O(e), which is low enough to run it at the background of the operating system.
Design and analysis of asynchronous adders
Image component labelling on the star graph using divide and conquer
Efficient group signature scheme based on the discrete logarithm
Two's complement division without using the set of full precision comparisons
Creating a highly reliable modified gamma interconnection network using a balance approach
Signature schemes based on factoring and discrete logarithms
Efficient bipartitioning algorithm for size-constrained circuits
Logic synthesis for a fine-grain FPGA
Balanced Boolean functions
Empirical study of memory-data: Characteristics and compressibility
Deadlock detection using (0, 1)-labelling of resource allocation graphs
Most viewed content for this Journal
Article
content/journals/ip-cdt
Journal
5
Most cited content for this Journal
We currently have no most cited data available for this content.