The size required to store an array is crucial for an embedded system, as it affects the memory size, the energy per memory access, and the overall system cost. Existing techniques for finding the minimum number of resources required to store an array are less efficient for codes with large loops and not regularly occurring memory accesses. They have to approximate the accessed parts of the array leading to overestimation of the required resources. Otherwise, their exploration time is increased with an increase over the number of the different accessed parts of the array. We propose a methodology to compute the minimum resources required for storing an array which keeps the exploration time low and provides a near-optimal result for regularly and non-regularly occurring memory accesses and overlapping writes and reads.

Memory management searches for the resources required to store the concurrently alive elements. The solution quality is affected by the representation of the element accesses: a sub-optimal representation leads to overestimation and a non-scalable representation increases the exploration time. We propose a methodology to near-optimal and scalable represent regular and irregular accesses. The representation consists of a set of pattern entries to compactly describe the behavior of the memory accesses and of pattern operations to consistently combine the pattern entries. The result is a final sequence of pattern entries which represents the global access scheme without unnecessary overestimation.

A systematic methodology for near-optimal software/hardware codesign mapping onto an FPGA platform with microprocessor and HW accelerators is proposed. The mapping steps deal with the inter-organization, the foreground memory management, and the datapath mapping. A step is described by parameters and equations combined in a scalable template. Mapping decisions are propagated as design constraints to prune suboptimal options in next steps. Several performance-area Pareto points are produced by instantiating the parameters. To evaluate our methodology we map a real-time bio-imaging application and loop-dominated benchmarks.

Storage-size management techniques aim to reduce the resources required to store elements and to concurrently provide efficient addressing during element accessing. Existing techniques are less appropriate for large iteration spaces with increased numbers of irregularly spread holes. They either have to approximate the accessed regions, leading to overestimation of the final resources, or they require prohibited exploration time to find the storage size. In this work, we present a near-optimal and scalable methodology for storage-size, intrasignal, in-place optimization, that is, to compute the minimum amount of resources required to store the elements of a group (array), for irregular complex access schemes in the target domain of non-overlapping store and load accesses.

High-throughput and area-efficient designs of hash functions and corresponding mechanisms for Message Authentication Codes (MACs) are in high demand due to new security protocols that have arisen and call for security services in every transmitted data packet. For instance, IPv6 incorporates the IPSec protocol for secure data transmission. However, the IPSec's performance bottleneck is the HMAC mechanism which is responsible for authenticating the transmitted data. HMAC's performance bottleneck in its turn is the underlying hash function. In this article a high-throughput and small-size SHA-256 hash function FPGA design and the corresponding HMAC FPGA design is presented. Advanced optimization techniques have been deployed leading to a SHA-256 hashing core which performs more than 30% better, compared to the next better design. This improvement is achieved both in terms of throughput as well as in terms of throughput/area cost factor. It is the first reported SHA-256 hashing core that exceeds 11Gbps (after place and route in Xilinx Virtex 6 board).

Many cryptographic primitives that are used in cryptographic schemes and security protocols such as SET, PKI, IPSec, and VPNs utilize hash functions, which form a special family of cryptographic algorithms. Applications that use these security schemes are becoming very popular as time goes by and this means that some of these applications call for higher throughput either due to their rapid acceptance by the market or due to their nature. In this work, a new methodology is presented for achieving high operating frequency and throughput for the implementations of all widely used-and those expected to be used in the near future-hash functions such as MD-5, SHA-1, RIPEMD (all versions), SHA-256, SHA-384, SHA-512, and so forth. In the proposed methodology, five different techniques have been developed and combined with the finest way so as to achieve the maximum performance. Compared to conventional pipelined implementations of hash functions (in FPGAs), the proposed methodology can lead even to a 160 percent throughput increase.

This paper present a decoupled architecture of processors with a memory hierarchy of only scratch-pad memories, and a main memory. The decoupled architecture also exploits the parallelism between address computation and processing the application data. The application code is split in two programs the first for computing the addresses of the data in the memory hierarchy and the second for processing the application data. The first program is executed by one of the decoupled processors called Access which uses compiler methods for placing data in the memory hierarchy. In parallel, the second program is executed by the other processor called Execute. The synchronization of the memory hierarchy and the Execute processor is achieved through simple handshake protocol. The Access processor requires strong communication with the memory hierarchy which strongly differentiates it from traditional uniprocessors. The architecture is compared in performance with the MIPS IV architecture of SimpleScalar and with the existing decoupled architectures showing its higher normalized performance. Experimental results show that the performance is increased up to 3.7 times. Compared with MIPS IV the proposed architecture achieves the above performance with insignificant overheads in terms of area

In this paper a high-speed cryptographic coprocessor, named HSSec, is presented. The core embeds two hash functions, SHA-1 and SHA-512, and the symmetric block cipher AES. The architecture of HSSec renders it suitable for widely spread applications with security demands. The presented co-processor can be used in every system integrating standards such as IPSec or the upcoming JPSec and P1619. The main characteristic of the proposed implementation is common use of the available resources, to minimize further area requirements. Additionally the cryptographic primitives can operate in parallel, providing high throughput whenever needed. Finally the system can operate in ECB or CBC modes. The HSSec co-processor has relatively small area and its performance reaches 1 Gbps (AES, SHA-1 and SHA-512) for XILINX's Virtex II FPGA family.

A large number of factors influence the hardware cost and the mapping efficiency of applications on coarse grain reconfigurable architectures. This paper investigates for the first time in a unified way the four factors that are directly related with the efficiency of a coarse grain reconfigurable array architecture namely; the area the clock frequency, the scheduling efficiency and performance. An exploration framework has been build for estimating the values of the 4 a forementioned factors for different architecture alternatives. The exploration framework is composed of an existing retargetable compiler framework from which we estimate the mapping efficiency and the parametric realization of the coarse grained reconfigurable array architecture in hardware description language from which we estimate the clock frequency and the area of each architecture instance. The experiments refer to different architecture alternatives in terms of the processing elements' interconnection network, the register files' size, their number of input/output ports, and finally the available bandwidth. Totally 72 architecture scenarios have been studied revealing how each characteristic influences performance and area for efficiently make design decisions.

The speedups and the energy reductions achieved in a generic single-chip microprocessor system by employing a high-performance data-path are presented. The data-path acts as a coprocessor that accelerates computational intensive kernel sections thereby increasing the overall performance. It is composed by Flexible Computational Components that can realize any two-level sequence of primitive operations. The automated coprocessor synthesis method from high-level software description and its integration to a design flow for executing applications on the system is presented. The estimated application speedups of eight real-life applications, relative to the software execution on the microprocessor range from 1.78 to 4.00, while the overhead in circuit area is small. The energy savings have an average value of 61%. A comparison with another high-performance data-path showed that the proposed coprocessor achieves smaller area-time products, by an average of 23%, for the synthesized data-paths.

This paper presents the performance improvements and the energy reductions by coupling a high-performance coarse-grained reconfigurable data-path with a microprocessor in a generic platform. The datapath has been previously introduced by the authors. It is composed by computational units able to realize complex operations which aid in improving the performance of time critical application parts, called kernels. A design flow is proposed for mapping high-level software descriptions to the microprocessor system. Eight real-life applications are mapped on three different instances of the system. Significant overall application speedups, relative to a software-only solution, ranging from 1.74 to 3.94 are reported being close to theoretical speedup bounds. Average energy savings of 59% are achieved, while the reduction in the system energy-delay product ranges from 66% to 92%.

This article presents the speedups achieved in a generic single-chip microprocessor system by employing a high-performance datapath. The datapath acts as a coprocessor that accelerates computational-intensive kernel sections thereby increasing the overall performance. We have previously introduced the datapath which is composed of Flexible Computational Components (FCCs). These components can realize any two-level template of primitive operations. The automated coprocessor synthesis method from high-level software description and its integration to a design flow for executing applications on the system is presented. For evaluating the effectiveness of our coprocessor approach, analytical study in respect to the type of the custom datapath and to the microprocessor architecture is performed. The overall application speedups of several real-life applications relative to the software execution on the microprocessor are estimated using the design flow. These speedups range from 1.75 to 5.84, with an average value of 3.04, while the overhead in circuit area is small. The design flow achieved the acceleration of the applications near to theoretical speedup bounds. A comparison with another high-performance datapath showed that the proposed coprocessor achieves smaller area-time products by an average of 23% for the generated datapaths. Additionally, the FCC coprocessor achieves better performance in accelerating kernels relative to software-programmable DSP cores.

This paper presents performance improvements and energy savings from mapping real-world benchmarks on an embedded single-chip platform that includes coarse-grained reconfigurable logic with a microprocessor. The reconfigurable hardware is a 2-D array of processing elements connected with a mesh-like network. Analytical results derived from mapping seven real-life digital signal processing applications, with the aid of an automated design flow, on six different instances of the system architecture are presented. Significant overall application speedups relative to an all-software solution, ranging from 1.81 to 3.99 are reported being close to theoretical speedup bounds. Additionally, the energy savings range from 43% to 71%. Finally, a comparison with a system coupling a microprocessor with a very long instruction word core shows that the microprocessor/coarse-grained reconfigurable array platform is more efficient in terms of performance and energy consumption.

In this paper we study the performance improvements and trade-offs derived from an optimized mapping approach applied on a parametric coarse grained reconfigurable array architecture. The processing elements' local register files and the processing elements' interconnection network is exploited for caching memory data values with data reuse opportunities. The data reused values are transferred through the processing elements' interconnection network hence, relieving the bus from the burden of transferring these values. A novel mapping algorithm is also proposed that uses a modulo scheduling technique. This algorithm targets on a flexible architecture template which permits experimental exploration over different architecture alternatives. The experimental results showed that the operation parallelism was significantly improved by our mapping approach. Additionally, we have outlined the relation that exists between the performance improvements and the memory access latency, the interconnection network and the processing elements' register file size.

A design flow for processor platforms with on-chip coarse-grain reconfigurable logic is presented. The reconfigurable logic is realized by a 2-dimensional array of processing elements. Performance is improved by accelerating critical software loops, called kernels, on the reconfigurable array. Basic steps of the design flow have been automated. A procedure for detecting critical loops in the input C code was developed, while a mapping technique for coarse grain reconfigurable arrays, based on software pipelining, was also devised. Analytical results derived from mapping five real-life DSP applications on eight different instances of a generic system architecture are presented. Large values of instructions per cycle were achieved on two reconfigurable arrays that resulted in high-performance kernel mapping. Additionally, by mapping critical code on the reconfigurable logic, speedups ranging from 1.27 to 3.18 relative to an all-processor execution were achieved

In this paper, we present performance results from mapping five real-world DSP applications on an embedded system-on-chip that incorporates coarse-grain reconfigurable logic with an instruction-set processor. The reconfigurable logic is realized by a 2-dimensional array of processing elements. A mapping flow for improving application's performance by accelerating critical software parts, called kernels, on the coarse-grain reconfigurable array is proposed. Profiling is performed for detecting critical kernel code. For mapping the detected kernels on the reconfigurable logic a priority-based mapping algorithm has been developed. The experiments for three different instances of a generic system show that the speedup from executing kernels on the reconfigurable array ranges from 9.9 to 151.1, with an average value of 54.1, relative to the kernels' execution on the processor. Important overall application speedups, due to the kernels' acceleration, have been reported for the five applications. These overall performance improvements range from 1.3 to 3.7, with an average value of 2.3, relative to an all-software execution.

It is widely known that bandwidth limitations degrade parallel systems' performance. This paper presents a mapping methodology for coarse-grain reconfigurable arrays which alleviates the bandwidth bottleneck by exploiting the processing elements interconnection network for transferring values with data reuse opportunities. A novel mapping algorithm is also proposed that uses a resource-aware modulo scheduling technique. From the application of the proposed mapping approach, significant improvements in performance were achieved while we have also quantified these improvements in respect to crucial architecture parameters such as the memory latency and the register file size. For this reason, our methodology targets on a parametric architecture template which can model a large number of existing architectures of this kind

Results from mapping five real-world DSP applications on a system-on-chip that incorporates coarse-grain reconfigurable hardware with an instruction-set processor is presented. The reconfigurable logic is realized by a 2-dimensional array of processing elements. A mapping method for improving application's performance by accelerating critical software parts, called kernels, on the coarse-grain reconfigurable array is proposed. For mapping the detected kernels on the reconfigurable logic a priority-based mapping algorithm has been developed. Important overall application speedups, due to the kernels' acceleration, have been reported for the five applications. These overall performance improvements range from 1.27 to 3.07, with an average value of 2.16, relative to an all-software execution

A high-performance data path to implement digital signal processing (DSP) kernels is introduced in this paper. The data path is realized by a flexible computational component (FCC), which is a pure combinational circuit and it can implement any 2 times 2 template (cluster) of primitive resources. Thus, the data path's performance benefits from the intracomponent chaining of operations. Due to the flexible structure of the FCC, the data path is implemented by a small number of such components. This allows for direct connections among FCCs and for exploiting intercomponent chaining, which further improves performance. Due to the universality and flexibility of the FCC, simple and efficient algorithms perform scheduling and binding of the data flow graph (DFG). DSP benchmarks synthesized with the FCC data path method show significant performance improvements when compared with template-based data path designs. Detailed results on execution time, FCC utilization, and area are presented

It is widely known that parallel operation execution in multiprocessor systems generates a respective increase in memory accesses. Since the memory and bus subsystems provide a limited access bandwidth, the applications performance cannot be that high as the multiprocessor system capabilities promise. This is the case for the 2D coarse-grained reconfigurable arrays for which a mapping methodology that aims in improving the mapped applications' performance by alleviating the data bandwidth bottleneck, is presented in this paper. This is achieved by exploiting the applications' data reuse opportunities both at the data dependence and source code level and the architecture's foreground memory. The methodology considers a realistic 2D coarse-grained reconfigurable architecture template, which can model the majority of the existing coarse-grained reconfigurable array architectures. The experimental results show a significant reduction in both execution time and memory accesses for two architecture scenarios that has been achieved by the application of the proposed methodology on a representative set of DSP applications.

In this paper, we propose a hardware/software partitioning method for improving applications' performance in embedded systems. Critical software parts are accelerated on hardware of a single-chip generic system comprised by an embedded processor and coarse-grain reconfigurable hardware. The reconfigurable hardware is realized by a 2D array of processing elements. The partitioning flow utilizes an analysis procedure at the basic-block level for detecting kernels in software. A list-based mapping algorithm has been developed for estimating the execution cycles of kernels on coarse-grain reconfigurable arrays. The proposed partitioning flow has been largely automated for a program description in C language. Extensive hardware/software experiments on five real-life applications are presented. It is shown that the benchmarks spend an average of 69% of their instruction count in 11% on average of their code that correspond to the kernels' code. The results illustrate that by mapping critical code on coarse-grain reconfigurable hardware, speedups ranging from 1.2 to 3.7, with an average value of 2.2, are achieved.

In this paper, we propose a method for speeding-up applications by partitioning them between the reconfigurable hardware blocks of different granularity and mapping critical parts of applications on the coarse-grain reconfigurable hardware. The partitioning method consists of four steps; the intermediate representation creation, the kernel identification, the mapping onto coarse-grain reconfigurable blocks, and the mapping onto the FPGA hardware. The method is validated using five real-world applications, where the speedup relative to an all-FPGA solution ranges from 1.4 to 3.1.

A hardware/software partitioning methodology for improving applications' performance in embedded single-chip systems is presented. Critical software parts are accelerated on hardware of a system comprised by an embedded processor and coarse-grain reconfigurable hardware. The reconfigurable hardware is realized by a 2-dimensional array of processing elements. The partitioning method uses a basic-block level analysis procedure for detecting kernels in software. A mapping algorithm for coarse-grain reconfigurable arrays has been developed for estimating the execution time of kernels on the reconfigurable hardware. The proposed partitioning flow has been largely automated for a program description in C language. Analytical hardware/software experiments on five real-world applications are given. The results show that by mapping critical parts on coarse-grain reconfigurable hardware, speedups ranging from 1.2 to 3.7, with an average value of 2.3, are achieved.

In this paper, we propose a methodology for partitioning and mapping computational intensive applications in reconfigurable hardware blocks of different granularity. A generic hybrid reconfigurable architecture is considered so as the methodology can be applicable to a large number of heterogeneous reconfigurable platforms. The methodology mainly consists of two stages, the analysis and the mapping of the application onto fine and coarse-grain hardware resources. A prototype framework consisting of analysis, partitioning and mapping tools has been also developed. For the coarse-grain reconfigurable hardware, we use our previously developed high-performance coarse-grain datapath. In this work, the methodology is validated using two real-world applications, an OFDM transmitter and a JPEG encoder. In the case of the OFDM transmitter, a maximum clock cycle decrease of 82 % relative to the ones in an all fine-grain mapping solution is achieved. The corresponding performance improvement for the JPEG is 43 %.

In this paper, a high performance reconfigurable coarse-grain data-path, part of a mixed-granularity reconfigurable platform, is presented. The computational resources are coarse grain components of the same type. An automated methodology for mapping DSP applications on the data-path is also presented, and it is based on unsophisticated, yet efficient, algorithms. Results on DSP benchmarks show the performance improvements over previously published high-performance data-paths.

In this paper, an efficient implementation of a high performance coarse-grain reconfigurable data-path on a mixed-granularity reconfigurable platform is presented. It consists of several coarse grain components of the same type, a reconfigurable inter-component network, and a centralized register bank. The universal type of coarse grain component is shown to increase the system's performance due to significant reductions in the latency. A flexible interconnection network facilitates the data transfers between the coarse grain components and also from or to the register bank. An automated methodology for mapping DSP and multimedia kernels on the data-path is also presented. Chaining of operations is optimally exploited, and the architecture allows for simple and efficient algorithms for scheduling, live signal reduction, and component binding. Experimental results verify the impact of our architectural decisions and design automation methods.

Techniques for the power efficient data path synthesis of sum-of-products computations between data and coefficients are presented. The proposed techniques exploit specific features of this type of computations. Efficient heuristics for the scheduling and assignment tasks, based on the concept of the Traveling Salesman's Problem, are described. Different cost functions are proposed to drive the synthesis tasks. The proposed cost functions target the power consumption either in the interconnect buses or in the functional units. Experimental results from different relevant digital signal processing algorithmic kernels prove that the proposed synthesis techniques lead to significant power savings.

This paper focuses on I-cache behaviour enhancement through the application of high-level code transformations. Specifically, a flow for the iterative application of the I-Cache performance optimizing transformations is proposed. The procedure of applying transformation is driven by a set of analytical equations, which receive parameters related to code and I-cache structure and predict the number of I-cache misses. Experimental results from a real-life demonstration application shows that order of magnitude reductions of the number of I-cache misses can be achieved by the application of the proposed methodology.

A systematic methodology for the reduction of the power consumption and the execution time in realizations of multimedia applications on programmable processors is proposed. The methodology is mainly based on the application of data transfer and storage optimizing code transformations to a high-level description of the target algorithm. Application of the code transformations according to the proposed order moves the main part of the memory accesses from the large background memories (lying possibly off-chip) to smaller ones (on-chip) or even to foreground storage. Data cache performance is improved as well. In this way the power consumption in the data memory hierarchy of the target processor and in the related interconnect, which forms a significant part of the total power budget of the system, is significantly reduced. Execution time and the power consumption due to instruction storage and transfers are reduced as well after the application of the proposed methodology. Experimental results from real-life applications prove the effectiveness of the proposed methodology.

This paper describes an efficient implementation of an image coding system based on the independent wavelet-tree coding concept. The system consists of a transform and a (de)coding engine that operate in a pipelined fashion. The main focus of this paper is on the encoding part since, due to the system architecture, the decoder has identical memory utilization. Experimental results prove that the proposed system achieves comparable coding performance to the state-of-the-art, while it localizes the memory accesses to small memory modules and uses minimal computational resources.

Two basic approaches for implementing the 9/7 filtering unit, used in the discrete wavelet transform, are addressed. The first is the lifting scheme approach and the second is the conventional, convolutional filter approach. Two architectures are examined for each approach, a simple straightforward one and an optimized one, substituting the multipliers used for scaling with shift-add operations. The quantization of the constants used in the calculations is thoroughly explored and the selection of the data-path bit-width is addressed. Experimental results based on hardware implementation, for several quantizations and for the different hardware architectures of the 9/7 filtering units are given.

A new method for the implementation of the binary-tree decomposition of the convolution-based wavelet transform, called the local wavelet transform (LWT) has been recently proposed in the literature. While it produces exactly the same results as the classical row-column implementation of the transform, it has many implementation benefits. This fact is shown experimentally for the first time for a general-purpose processor-based architecture, by comparing our C implementation of the LWT with an optimal C implementation of the lifting-scheme row-column algorithm. The comparisons are made for the forward multilevel binary-tree decomposition using the 9/7 filter pair, in the typical Intel Pentium processor family.

A comparison study of four blocking matching algorithms is presented in terms of performance, energy consumption and area, assuming five matching criteria. Two widely-used programmable processor cores, namely the embedded processor, ARM, with specialized memory hierarchy and the general purpose processor, Pentium/sup /spl copy//, are chosen for performing the comparative study, and eventually, determining the most efficient solution for certain design specifications. Adopting a systematic design methodology, efficient high-level transformations are applied to the considered algorithm structures resulting in performance-, energy-, and area-optimized solutions The plethora of alternative implementations under the different distance criteria and processor cores, offers flexibility to the designer in finding the most suitable solution for him/her, given the design specifications.

In this paper, the three main hardware architectures for the 2-D discrete wavelet transform (2-D-DWT) are reviewed. Also, optimization techniques applicable to all three architectures are described. The main contribution of this work is the quantitative comparison among these design alternatives for the 2-D-DWT. The comparison is performed in terms of memory requirements, throughput, and energy dissipation, and is based on a theoretical analysis of the alternative architectures and schedules. Memory requirements, throughput, and energy are expressed by analytical equations with parameters from both the 2-D-DWT algorithm and the implementation platform. The parameterized equations enable the early but efficient exploration of the various tradeoffs related to the selection to the one or the other architecture.

Recent advances in electronic technology integration coupled with increasing needs for more services in portable communications favors the development of high performance dual-mode terminals. We present the complete architecture implementation of the GMSK/GFSK modulator/demodulator including the FIR filters design. The main features of the modulator/demodulator and the architectural implementation of FIR filters are described. The interface with ASPIS processor and A/D & D/A converters is also described in detail manner. The whole architecture of the modulator/demodulator was described by VHDL hardware language, synthesised and implemented in Xilinx environment.

Power management is a low-power technique applicable in almost all design levels. Event-driven power management has been applied at the system-level. The same concept can be applied for receiver design at the behavioral-level. Power management involves a trade-off according to which, on the one hand, power is decreased by shutting down parts of the circuit, but on the other hand, power is increased by the insertion of the required logic for the generation of the shutdown signals. In this paper, receiver context characteristics are exploited in order to develop a methodology for the behavioral-level exploration of this trade-off. The efficiency of the proposed methodology is proven by its application on a real-life digital DECT receiver.

Novel techniques for the power efficient synthesis of sum-of-product computations are presented. Simple and efficient heuristics for scheduling and assignment are described. Different partly static cost functions are proposed to drive the synthesis tasks. The proposed cost functions target the power consumption either in the buses connecting the functional units with the storage elements or inside the functional units. The partly static nature of the proposed cost functions reduces the time of the synthesis procedure. Experimental results from different relevant digital signal processing algorithmic kernels prove that the proposed synthesis techniques lead to significant power savings.

A methodology for power efficient partitioning of real-time datadominated system specifications is presented. The proposed methodology aims at reducing the memory requirements in realizations of such applications by applying extensive code transformations in the initial system specification before partitioning over processors. This reorganization basically aligns the data production and consumption between the different procedures of the initial specification thus reducing the memory size requirements (and the resulting power) of the system's realizations especially those in the interfaces between different processors. The main novel contribution is that performance issues are explicitly taken into account during power oriented system-level transformations. The proposed methodology can be applied both in a parallel (programmable) processor context and also in heterogeneous hardware-software architectures.

Application studies in the areas of image- and video-processing indicate that between 50%-80% of the power cost in these systems is due to data storage and transfers. This is especially true for multiprocessor realizations because conventional parallelization methods ignore the power cost and focus only on performance. However, the power consumption also heavily depends on the way a system is parallelized. To reduce this dominant cost, we propose to address the system-level storage organization for the multidimensional signals as a first step in mapping these applications, before the parallelization or partitioning decisions (in particular, before the hardware/software (HW/SW) partitioning, which is traditionally done too early in the design trajectory). Our methodology is illustrated on a parallel quadtree-structured difference pulse-code modulation video codec.

Novel techniques for power-efficient implementation of sum of product computation are presented. The proposed techniques aim at reducing the switching activity required for the successive evaluation of the partial products, in the busses connecting the storage elements where data and coefficients are stored to the functional units. This is achieved through reordering the sequence of evaluation of the partial products. Heuristics based on the traveling salesman problem are proposed to perform the reordering for different categories of algorithms. Information related to both data (dynamic) and coefficients (static) is used to drive the reordering. Experimental results from the application of the proposed techniques on several signal-processing algorithms have proven that significant switching activity savings can be achieved.

In this paper an accurate, analytical model for the evaluation of the CMOS inverter delay in the sub-micron regime, is presented. A detailed analysis of the inverter operation is provided which results in accurate expressions describing the output waveform. These analytical expressions are valid for all the inverter operation regions and input waveform slopes. They take into account the influences of the short-circuit current during switching, and the gate-to-drain coupling capacitance. The presented model shows clearly the influence of the inverter design characteristics, the load capacitance, and the slope of the input waveform driving the inverter on the propagation delay. The results are in excellent agreement with SPICE simulations.

Novel algorithms for vector quantization codebook design are presented. Two basic techniques are proposed. The first technique takes into consideration specific characteristics of the blocks of the training sequence during the generation of the initial codebook. In this way a representative initial codebook is generated. Starting from a high quality initial codebook the iterative optimization procedure converges fast to representative final codebook which in turn leads to a high output image quality. The second proposed technique extends small codebooks computationally. The main idea is the application of simple transformations on the codewords. This technique reduces the memory requirements of the traditional vector quantization making it useful for applications requiring low-power consumption.

A novel scheme for low-power image and video coding and decoding is presented. It is based on vector quantization, and reduces its memory requirements, which form a major disadvantage in terms of power consumption. The main innovation is the use of small codebooks, and the application of simple but efficient transformations to the codewords during coding to compensate for the quality degradation introduced by the small codebook size. In this way, the small codebooks are computationally extended, and the coding task becomes computation based rather than memory based, leading to significant power consumption reduction. The parameters of the transformations depend on the image block under coding, and thus the small codebooks are dynamically adapted each time to this specific image block, leading to image qualities comparable to or better than those corresponding to classical vector quantization. The algorithm leads to power savings of a factor of 10 in coding and of a factor of 3 in decoding at least, in comparison to classical full-search vector quantization. Both image quality and power consumption highly depend on the size of the codebook that is used.

Recently, a new fast algorithm has been proposed for the computation of the 2-D N/spl times/N-point Discrete Cosine Transform, where N is decomposed into two mutually prime numbers N/sub 1/ and N/sub 2/. Using Prime-Factor Decomposition (PFD) and appropriate index mappings, the algorithm results in fewer multiplications than other fast 2-D DCT algorithms. In this paper, a methodology for systematic mapping of this algorithm onto hardware is presented. The proposed methodology reveals the existence of a few connected components in the signal-flow graph (SFG) of the algorithm and leads to architectures that can be systematically derived and exhibit varying throughput and hardware complexity.

There are numerous fields of applications that demand the storage of large quantities of data that represent images. Many of these applications need to preserve every single detail of the input picture (e.g. medical purposes) thus image compression is necessary to reduce the number of bytes that are stored in a magnetic or optical medium. In this paper a novel method is presented that, for the first time, combines fuzzy logic principles, accomplishing smart smoothing of an image, with standard lossless compression techniques. The output of the fuzzy non-linear filtering process feeds the Q-Coder as described in JPEG standard achieving an increase of the compression ratio. Since the proposed selective smoothing of the image does not affect regions with edges or isolated points, all essential details are preserved resulting to a high quality near-lossless compression.>

In this paper, a new processor that computes the Discrete Cosine Transform (DCT) is presented. Based on a recently proposed DCT algorithm, this architecture overcomes the major drawbacks of the original implementation resulting in a design with considerably less area consumption and higher speed. To achieve these results, a novel architecture, based on the CORDIC circular rotation algorithm, is introduced: it reduces the required area by more than 60% compared to the use of standard CORDIC architectures. Furthermore, bit serial arithmetic is used, resulting in a very compact design. In order to get maximum throughput, the proposed processor is fully pipelined, achieving a performance efficient even for signals as fast as HDTV.>

A novel space-time representation of iterative algorithms, which can be expressed in nested loop form and may include non-constant dependencies is proposed and a systematic methodology for their mapping onto regular processor arrays is presented. In contrast to previous design methodologies, the execution time of any variable instance is explicitly expressed in the Dependence Graph, by the construction of the Space-Time Dependence Graph (STDG). This approach avoids the uniformization step of the algorithm and the requirement for fully indexing the variables.

Large block circulant sparse matrices whose submatrices have all non-zero elements within an elliptical or general closed strip, appear in Tomographic image reconstruction from projections. A new 2-D array architecture which fully exploits these features is introduced for the iterative solution of linear systems involving such matrices. Each sub row-vector product is computed in parallel by one row of simple processing units and pipelined to give a high utilisation ratio. A two level controller is used having one Main Control Unit (MCU) and identical simple Sub-Control Units (SCU) - one for each row of the array. This allows appropriate flow of the data and partial products, which in effect split and straighten the elliptical strip to produce two strip diagonal matrices. The VLSI designs for the MCU and SCU have been completed.

Two new iterative algorithms for AR parameter estimation are presented. The first minimizes the sum of the prediction error energy and the cross covariance between prediction error and additive noise, and models the noise covariance matrix with a separate AR filter whose reflection coefficient are constrained to be sufficiently small. The second algorithm minimizes the cross covariance between the prediction error and the data. In both algorithm a steepest descent updating procedure is employed and stability of the AR filter for the stohastic processes is ensured by constraining the corresponding reflection coefficients to be less than one.

A general method for the optimization of convex or concave cost functions over the intersection of convex constraint sets is described for applications in signal reconstruction and restorarion. A unique continuous function is obtained, under certain conditions, by employing Fenchel's duality theorem to give a finite dimensional dual problem. This approach allows the solution of very complex constrained problems by separating the constraints into those related to the solution and those related to additive noise statistics. The method is applied to computed tomography with noisy data of which the noise covariance and bounds on the solution are known approximately. A fast implementation of the required optimization procedure is given and the resulting solution is shown to be significantly better than a suboptimal feasible solution.

The autoregressive and Prony methods for spectral estimation do not make full use of the statistics of the additive noise. These statistics are included in the following as constraints on the solution. The finite number of data samples imposes a limit on the resolution thus making it possible to approximate random signals by a set of deterministic signals which can be modelled in terms of a finite set of time-invariant parameters, θ. The non-Toeplitz covariance calculated from the data is modelled here using the θ parameters. Statistical constraints and covariance modelling are combined to produce non-linear methods for spectral estimation. The resulting higher resolution requires high computational complexity; this can often be substantially reduced by using knowledge-based techniques.

A unified theoretical treatment of constrained optimisation methods for tomographic and spectral estimation from discrete data is given. The solution is shown to be equivalent to the unconstrained optimisation of a dual functional in which the image or spectrum is modelled in terms of a Lagrange multiplier vector and the kernel of the constraint integrals. In order to obtain the best possible solution it is important to consider the effects of noise in the constraints. The problem is reformulated using the above models and the exact data is replaced with the noise statistics as constraints; this is solved using a penalty method. A very fast direct algorithm is also introduced which matches the noise variance provided the signal to noise ratio is approximately known.

Polar periodicities associated with the Radon transform and Lagrange multipliers are studies to obtain the sample/ recovery relationships. By considering a window function, which is zero outside the object boundaries and inside its transparent areas, a Fourier domain algorithm is introduced in which the Lagrange multipliers are determined using the window as a constraint. By expressing the backprojection image using the basis function of the projection transform a reconstruction model for fan beam projections is given. A very fast, iterative, space domain algorithm for divergent ray projections is introduced which gives the minimum energy reconstruction by exploiting a special matrix structure; this method matches the noise statistics and can utilise 'a priori' knowledge.

This paper extends the constrained optimisation image reconstruction techniques to curved-ray projections for a number of scanning systems and for 2-D and 3-D reconstructions. The work presented is general in that it includes the previous results on parallel-ray and divergent-ray geometries as special cases. Treating the problem in Hilbert space a general cost function is optimised and the solution is applied to a number of practical criteria. This has led to a convergent iterative algorithm which evaluates the associated Lagrange multiplier functions and establishes the reconstruction for all scanning geometries. Further a generalised Projection Slice Theorem is introduced based on a new Projection Transform.