Home
>
Journals & magazines
>
IEE Proceedings - Computers and Digital Technique...
>
Volume 145
Issue 6
IEE Proceedings - Computers and Digital Techniques
Volume 145, Issue 6, November 1998
Volumes & issues:
Volume 145, Issue 6
November 1998
-
- Author(s): I.S. Reed ; R. He ; X. Chen ; T.K. Truong
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 6, p. 369 –376
- DOI: 10.1049/ip-cdt:19982340
- Type: Article
- + Show details - Hide details
-
p.
369
–376
(8)
The error/erasure decoding of the RS(28,24) and RS(32,28) codes, used on a compact disc, are considered in some detail. Gröbner bases are used to obtain the conditions for all error/erasure configurations that fall within the error-correcting ability of the two codes. Finally, a new decoding strategy is presented, which is based on these conditions. - Author(s): C.–H. Huang ; J.–Y. Hsiao ; R.C.T. Lee
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 6, p. 377 –384
- DOI: 10.1049/ip-cdt:19982341
- Type: Article
- + Show details - Hide details
-
p.
377
–384
(8)
It has been proved that an incomplete binary tree cannot be embedded into an incomplete hypercube with dilation 1 and expansion 1. By applying some properties of inorder traversal, the authors present an embedding scheme with dilation 2, edge-congestion 2 and expansion ratio (N + 1)/N, where N is the number of nodes in an incomplete binary tree. The authors prove that this embedding is optimal under the constraint of expansion ratio (N + 1)/N. With this embedding scheme, a method is developed that can be used to simulate a binary tree on an incomplete hypercube effectively. Under the distributed environment, the mapping addresses of neighbouring nodes in an incomplete binary tree can be identified in constant time without repeating the mapping work. Furthermore, experimental results show that this scheme is much better than the corresponding best known dilation 1 embedding scheme in terms of hardware costs and implementation. Even in total time costs (addressing time, computation time and transmission time), this approach is quite competitive. - Author(s): C.-H. Chang and B.J. Falkowski
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 6, p. 385 –394
- DOI: 10.1049/ip-cdt:19982342
- Type: Article
- + Show details - Hide details
-
p.
385
–394
(10)
An adaptive method to minimise fixed-polarity Reed–Muller expansions, combining the advantages of efficient data structures in form of both lookup tables and ternary decision trees, is presented. The algorithm developed converts arrays of cubes to exact solutions based on the desired cost criteria for the systems of completely specified functions. The method also allows one to combine the design for testability together with minimisation of hardware realisation. The algorithm shown is fast, efficient and requires smaller space and time complexity than known algorithms. - Author(s): G. Cabodi ; P. Camurati ; S. Quer
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 6, p. 395 –402
- DOI: 10.1049/ip-cdt:19982343
- Type: Article
- + Show details - Hide details
-
p.
395
–402
(8)
In the fields of synthesis and verification of VLSI circuits, sequential optimisation has attracted increasing interest due to the time, area and power constraints of modern devices. For example, state minimisation aims to reduce the number of states of a sequential circuit, optimising its representation. The need to handle large state sets makes implicit methods, based on binary decision diagrams and symbolic traversal techniques, quite appealing. Nevertheless, implicit techniques have limitations, and two improvements to standard methods are proposed to deal with larger circuits. First, the degree of freedom offered by don't care sets is exploited to enhance the state-of-the-art approach using cofactor-based techniques. Internal steps of the process are simpler and faster, although very large problems cannot be dealt with. Secondly, partitioning and approximation are used. The search space is pruned by constraining it to well suited subspaces. To this purpose, the concepts of underestimation of equivalence classes, and of non-minimal reduction are introduced. This leads to major simplifications and is quite effective in dealing with large problems and improving efficiency. - Author(s): G.M. Megson
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 6, p. 403 –410
- DOI: 10.1049/ip-cdt:19982344
- Type: Article
- + Show details - Hide details
-
p.
403
–410
(8)
A reformulation of the Haar transform algorithm is used to design systolic arrays for data compression. First a triangular array is developed for the normalised 1-D transform and it is then extended to produce an inverse transformation. Area-efficient and unrolled array designs employing the 1-D arrays are used to develop high-throughput, area-efficient arrays with 100% efficiency which produce one transformed data item per clock cycle. The 1-D designs are then incorporated into a 2-D design for image compression using row and column operations. Finally the arrays are augmented with a simple thresholding design which produces a compressed lossy output. High throughput can be achieved. A complete compression/decompression of the data can be performed using the arrays in conjunction with a thresholding array which adds O(m2) cells and an additional latency of 2m steps. The design is scalable in that m can be chosen to suit manufacturing capabilities. - Author(s): I. Ahmad ; M.K. Dhodhi ; R. Ul–Mustafa
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 6, p. 411 –418
- DOI: 10.1049/ip-cdt:19982345
- Type: Article
- + Show details - Hide details
-
p.
411
–418
(8)
Scheduling a parallel program is a crucial step in effectively harnessing the computing power of a heterogeneous computing system. Obtaining a minimum finish time schedule for a set of precedence constrained tasks is a well known NP-complete problem. Heterogeneity in parallel systems introduces an additional degree of complexity to the scheduling problem, i.e. varying speed of processors. A non-preemptive, compile-time scheduling heuristic has been developed, designated as DPS, that uses dynamic priorities based on the difference between b-level and t-level to map and schedule directed acyclic graphs (DAGs) onto heterogeneous processors, with the objective of minimising the schedule length. In the case of homogeneous processors, it is not difficult to compute the b-level and t-level, since the task execution costs are fixed. However, in the case of heterogeneous processors, as each task has a different execution cost on each processor, the b-level and t-level lose their traditional meaning. The b-level and t-level have been computed in a different and effective way that captures the changes which occurred in the DAG during scheduling. Dynamic priorities are thus determined during the scheduling process in order to avoid scheduling less important tasks before the more important ones. Moreover, the effect of changing the task execution cost to compute the b-level and t-level has also been studied. The effectiveness of the algorithm is demonstrated by comparing it against two of the existing closely related algorithms for randomly generated graphs. DPS outperforms both algorithms by a considerable margin and has a reasonable time complexity. - Author(s): J.-K. Jan and Y.-M. Tseng
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 6, p. 419 –424
- DOI: 10.1049/ip-cdt:19982346
- Type: Article
- + Show details - Hide details
-
p.
419
–424
(6)
With the growth in the scale of network technologies, security has become a major concern and a limiting factor. Computer networks provide convenient procedures for users operating at remote places. However, an intruder can easily access and intercept information transmitted in an open channel. Two integrated schemes for user authentication and access control are proposed, which are mechanisms used to provide for the protection of privacy and security in a distributed environment. One scheme is a dynamic approach which provides an efficient updating process for the modification of access rights. The second scheme allows servers to simplify verification processes for multiple access requests of a user at the same time. Both schemes are noninteractive approaches in which security is based on the computational difficulty of solving the discrete logarithm problem. Compared with other schemes proposed previously, the schemes are more secure and efficient and suitable for applications in a distributed environment. Intruders cannot derive secret information from public information. Intruders are not able to acquire the passwords of users from previously intercepted messages. By applying a time stamp, the schemes can withstand the replaying attack. - Author(s): P.-Y. Hsiao ; G.-M Wu ; J.-Y. Su
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 6, p. 425 –432
- DOI: 10.1049/ip-cdt:19982347
- Type: Article
- + Show details - Hide details
-
p.
425
–432
(8)
A branch-and-bound algorithm based on a maximum possibility table (MPT) is proposed to solve scheduling problems in high-level synthesis. Six efficient priority rules are developed as bounding functions in the algorithm. Extensions for real-world constraints are also considered, including chained operations, multicycle operations, mutually exclusive operations and pipelined data paths. Experimental results indicate that the MPT-based algorithm returns competitive scheduling results at significant savings in execution time as compared with other methods. - Author(s): C.-C. Wang ; C.-F. Wu ; K.-C. Tsai
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 6, p. 433 –436
- DOI: 10.1049/ip-cdt:19982348
- Type: Article
- + Show details - Hide details
-
p.
433
–436
(4)
A high-speed 64-bit comparator using two-phase clocking dynamic CMOS logic with modified noninverting all-N-transistor block is presented. The pull-up charging and pull-down discharging of a comparator unit are accelerated by inserting two feedback MOS transistors between the evaluation N-block and the output. Detailed simulation results reveal appropriate L/W guidelines for the all-N-transistor block design. To increase throughput a parallel tree structure with two-phase clocks is employed. The comparator units of two adjacent layers are triggered by two out-of-phase clocks so that their individual outputs are pipelined without using extra hardware, e.g. latches. The operating clock frequency is 1.0 GHz while the compared output of two 64-bit binary numbers is done in 3.5 cycles. - Author(s): R. Furness ; M. Benaissa ; S.T.J. Fenn
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 145, Issue 6, p. 437 –443
- DOI: 10.1049/ip-cdt:19982349
- Type: Article
- + Show details - Hide details
-
p.
437
–443
(7)
Bit-serial and bit-parallel multiplication architectures for GF(2m) are presented, using a triangular basis representation of field elements. The paper is a development of the work originally presented by Hasan and Bhargava. It is shown that, by forcing these multipliers to operate entirely over the triangular basis, lower latency delays and hardware savings can be made. Also, a more flexible definition of the triangular basis is presented which allows a number of triangular bases to any given basis to be defined. It is shown that when the defining irreducible polynomial is a trinomial, the triangular basis is a simple permutation of the polynomial basis elements. Furthermore, if the defining irreducible polynomial is a pentanomial of a certain form the triangular basis to polynomial basis conversion requires minimal hardware and a reordering of basis coefficients.
Application of Gröbner bases for decoding Reed–Solomon codes used on CDs
Embedding incomplete binary trees into incomplete hypercubes
Adaptive exact optimisation of minimally testable FPRM expansions
Implicit manipulation of equivalence classes for large finite state machines
Systolic arrays for the Haar transform
DPS: dynamic priority scheduling heuristic for heterogeneous computing systems
Two integrated schemes of user authentication and access control in a distributed computer network
MPT-based branch-and-bound strategy for scheduling problem in high-level synthesis
1 GHz 64-bit high-speed comparator using ANT dynamic logic with two-phase clocking
GF(2m) multiplication over triangular basis for design of Reed-Solomon codes
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.
