The Experts below are selected from a list of 291 Experts worldwide ranked by ideXlab platform
Shuvra S. Bhattacharyya - One of the best experts on this subject based on the ideXlab platform.
-
joint minimization of code and data for synchronous dataflowprograms
Formal Methods, 1997Co-Authors: Praveen K Murthy, Shuvra S. Bhattacharyya, Edward A LeeAbstract:In this paper, we formally develop techniques that minimize the memory requirements of a target program when synthesizing software from dataflow descriptions of Multirate Signal Processing algorithms. The dataflow programming model that we consider is the synchronous dataflow (SDF) model [21], which has been used heavily in DSP design environments over the past several years. We first focus on the restricted class of well-ordered SDF graphs. We show that while extremely efficient techniques exist for constructing minimum code size schedules for well-ordered graphs, the number of distinct minimum code size schedules increases combinatorially with the number of vertices in the input SDF graph, and these different schedules can have vastly different data memory requirements. We develop a dynamic programming algorithm that computes the schedule that minimizes the data memory requirement from among the schedules that minimize code size, and we show that the time complexity of this algorithm is cubic in the number of vertices in the given well-ordered SDF graph. We present several extensions to this dynamic programming technique to more general scheduling problems, and we present a heuristic that often computes near-optimal schedules with quadratic time complexity. We then show that finding optimal solutions for arbitrary acyclic graphs is NP-complete, and present heuristic techniques that jointly minimize code and data size requirements. We present a practical example and simulation data that demonstrate the effectiveness of these techniques.
-
generating compact code from dataflow specifications of Multirate Signal Processing algorithms
IEEE Transactions on Circuits and Systems I-regular Papers, 1995Co-Authors: Shuvra S. Bhattacharyya, J T Buck, Edward A LeeAbstract:Synchronous dataflow (SDF) semantics are well-suited to representing and compiling Multirate Signal Processing algorithms. A key to this match is the ability to cleanly express iteration without overspecifying the execution order of computations, thereby allowing efficient schedules to be constructed. Due to limited program memory, it is often desirable to translate the iteration in an SDF graph into groups of repetitive firing patterns so that loops can be constructed in the target code. This paper establishes fundamental topological relationships between iteration and looping in SDF graphs, and presents a scheduling framework that provably synthesizes the most compact looping structures for a large class of practical SDF graphs. By modularizing different components of the scheduling framework, and establishing their independence, we show how other scheduling objectives, such as minimizing data buffering requirements or increasing the number of data transfers that occur in registers, can be incorporated in a manner that does not conflict with the goal of code compactness. >
-
Looped schedules for dataflow descriptions of Multirate Signal Processing algorithms
Formal Methods in System Design, 1994Co-Authors: Shuvra S. BhattacharyyaAbstract:The synchronous dataflow (SDF) programming paradigm has been used extensively in design environments for Multirate Signal Processing applications. In this paradigm, the repetition of computations is specified by the relative rates at which the computations consume and produce data. This implicit specification of iteration allows a compiler to easily explore alternative nested loop structures for the target code with respect to their effects on code size, buffering requirements and throughput. In this paper, we develop important relationships between the SDF description of an algorithm and the range of looping structures offered by this description, and we discuss how to improve code efficiency by applying these relationships.
-
memory management for dataflow programming of Multirate Signal Processing algorithms
IEEE Transactions on Signal Processing, 1994Co-Authors: Shuvra S. Bhattacharyya, Edward A LeeAbstract:Managing the buffering of data along arcs is a critical part of compiling a synchronous dataflow (SDF) program. This paper shows how dataflow properties can be analyzed at compile-time to make buffering more efficient. Since the target code corresponding to each node of an SDF graph is normally obtained from a hand-optimized library of predefined blocks, the efficiency of data transfer between blocks is often the limiting factor in how closely an SDF compiler can approximate meticulous manual coding. Furthermore, in the presence of large sample-rate changes, straightforward buffering techniques ran quickly exhaust limited on-chip data memory, necessitating the use of slower external memory. The techniques presented in this paper address both of these problems in a unified manner. >
Edward A Lee - One of the best experts on this subject based on the ideXlab platform.
-
joint minimization of code and data for synchronous dataflowprograms
Formal Methods, 1997Co-Authors: Praveen K Murthy, Shuvra S. Bhattacharyya, Edward A LeeAbstract:In this paper, we formally develop techniques that minimize the memory requirements of a target program when synthesizing software from dataflow descriptions of Multirate Signal Processing algorithms. The dataflow programming model that we consider is the synchronous dataflow (SDF) model [21], which has been used heavily in DSP design environments over the past several years. We first focus on the restricted class of well-ordered SDF graphs. We show that while extremely efficient techniques exist for constructing minimum code size schedules for well-ordered graphs, the number of distinct minimum code size schedules increases combinatorially with the number of vertices in the input SDF graph, and these different schedules can have vastly different data memory requirements. We develop a dynamic programming algorithm that computes the schedule that minimizes the data memory requirement from among the schedules that minimize code size, and we show that the time complexity of this algorithm is cubic in the number of vertices in the given well-ordered SDF graph. We present several extensions to this dynamic programming technique to more general scheduling problems, and we present a heuristic that often computes near-optimal schedules with quadratic time complexity. We then show that finding optimal solutions for arbitrary acyclic graphs is NP-complete, and present heuristic techniques that jointly minimize code and data size requirements. We present a practical example and simulation data that demonstrate the effectiveness of these techniques.
-
generating compact code from dataflow specifications of Multirate Signal Processing algorithms
IEEE Transactions on Circuits and Systems I-regular Papers, 1995Co-Authors: Shuvra S. Bhattacharyya, J T Buck, Edward A LeeAbstract:Synchronous dataflow (SDF) semantics are well-suited to representing and compiling Multirate Signal Processing algorithms. A key to this match is the ability to cleanly express iteration without overspecifying the execution order of computations, thereby allowing efficient schedules to be constructed. Due to limited program memory, it is often desirable to translate the iteration in an SDF graph into groups of repetitive firing patterns so that loops can be constructed in the target code. This paper establishes fundamental topological relationships between iteration and looping in SDF graphs, and presents a scheduling framework that provably synthesizes the most compact looping structures for a large class of practical SDF graphs. By modularizing different components of the scheduling framework, and establishing their independence, we show how other scheduling objectives, such as minimizing data buffering requirements or increasing the number of data transfers that occur in registers, can be incorporated in a manner that does not conflict with the goal of code compactness. >
-
memory management for dataflow programming of Multirate Signal Processing algorithms
IEEE Transactions on Signal Processing, 1994Co-Authors: Shuvra S. Bhattacharyya, Edward A LeeAbstract:Managing the buffering of data along arcs is a critical part of compiling a synchronous dataflow (SDF) program. This paper shows how dataflow properties can be analyzed at compile-time to make buffering more efficient. Since the target code corresponding to each node of an SDF graph is normally obtained from a hand-optimized library of predefined blocks, the efficiency of data transfer between blocks is often the limiting factor in how closely an SDF compiler can approximate meticulous manual coding. Furthermore, in the presence of large sample-rate changes, straightforward buffering techniques ran quickly exhaust limited on-chip data memory, necessitating the use of slower external memory. The techniques presented in this paper address both of these problems in a unified manner. >
Markku Renfors - One of the best experts on this subject based on the ideXlab platform.
-
Multirate Signal Processing and Filterbanks
Orthogonal Waveforms and Filter Banks for Future Communication Systems, 2017Co-Authors: Markku Renfors, Juha Yli-kaakinenAbstract:This chapter introduces certain important theories and Signal Processing tools as background for later developments in this book. After a brief introduction to real and complex linear systems, spectral models for discrete-time systems are formulated in a generalized way and conditions for alias-free sampling are formulated for real and complex baseband and passband systems. Next, Multirate filtering concepts are introduced, again with emphasis on complex and bandpass Signal models. Also polyphase filters and filterbanks are introduced in this context. Then the Nyquist pulse shaping principle is explained as a central element of both classical communication theory and filterbank based waveforms. Finally, after a brief introduction to the Discrete Fourier Transform (DFT), the basic form of effective uniform filterbanks, the DFT FilterBank (DFT-FB), is introduced, and general filterbank concepts and classifications are summarized.
-
Advanced techniques on Multirate Signal Processing for digital information Processing [Editorial]
Signal Processing IET, 2011Co-Authors: Massimiliano Laddomada, Ching Lim Yong, Fa-long Luo, Gordana Jovanovic Dolecek, Markku Renfors, L. WanhammarAbstract:Multirate Signal Processing has become a key topic enabling efficient techniques for digital information Processing in a variety of applications such as digital transceivers s for wireless as well as satellite communication systems, digital broadcasting, high performance audio and video, multimedia services, and Signal compression. In the wireless communications arena, Multirate Signal Processing techniques provide effective means to implement flexible receiver channelisation filtering and sampling rate conversion for software and cognitive radio digital frontends. As far as multimedia Signal Processing is concerned, recent techniques relying on Multirate filter banks have resulted in improved subband coding techniques reflected in the JPEG-2000 multimedia standard, as well as on some modern audio compression formats such as MP3, AAC3 and ATRAC3plus, to cite but a few.
-
Signal Processing challenges for applying software radio principles in future wireless terminals an overview
International Journal of Communication Systems, 2002Co-Authors: Mikko Valkama, Juho Pirskanen, Markku RenforsAbstract:The general idea of software radio is to develop highly integrated radio transceiver structures with high degree of flexibility and multimode capabilities, achieved through increased role of digital Signal Processing software in defining the functionalities which have traditionally been implemented with analog RF techniques. This paper explores the software radio concept from the receiver architecture and Signal Processing points of view, with mainly the wireless terminal application in mind. We first discuss the critical issues in alternative receiver architectures with simplified analog parts and increased configurability. We also introduce certain advanced digital Signal Processing techniques which could potentially relieve some of the essential problems and pave the way towards DSP-based, highly integrated, and highly configurable terminals. Big emphasis is on efficient digital Multirate Signal Processing methods and complex (I/Q) Signal Processing. Copyright © 2002 John Wiley & Sons, Ltd.
-
decimation by irrational factor using cic filter and linear interpolation
International Conference on Acoustics Speech and Signal Processing, 2001Co-Authors: D Babic, Jussi Vesma, Markku RenforsAbstract:This paper presents an efficient way to implement flexible Multirate Signal Processing systems with high oversampling ratio and adjustable fractional or irrational sampling rate conversion ratio. One application area is a multi-standard communication receiver which should be adjustable for different symbol rates utilized in different systems. The proposed decimation filter consists of parallel CIC (cascaded integrator-comb) filters followed by a linear interpolation filter. The idea is to use two parallel CIC filters to calculate the two needed sample values for linear interpolation. These samples occur just before and after the final output sample. This corresponds to a system where the linear interpolation is done at the higher input sampling rate.
James Scrofani - One of the best experts on this subject based on the ideXlab platform.
-
theory of Multirate Signal Processing with application to Signal and image reconstruction
2005Co-Authors: James ScrofaniAbstract:Abstract : Signal Processing methods for Signals sampled at different rates are investigated and applied to the problem of Signal and image reconstruction or super-resolution reconstruction. The problem is approached from the viewpoint of linear mean-square estimation theory and Multirate Signal Processing for one- and two-dimensional Signals. A new look is taken at Multirate system theory in one and two dimensions which provides the framework for these methodologies. A careful analysis of linear optimal filtering for problems involving different input and output sampling rates is conducted. This results in the development of index mapping techniques that simplify the formulation of Wiener-Hopf equations whose solution determine the optimal filters. The required filters exhibit periodicity in both one and two dimensions, due to the difference in sampling rates. The reconstruction algorithms developed are applied to one- and two-dimensional reconstruction problems.
-
a stochastic Multirate Signal Processing approach to high resolution Signal reconstruction
International Conference on Acoustics Speech and Signal Processing, 2005Co-Authors: James Scrofani, C W TherrienAbstract:This paper addresses the problem of reconstructing a Signal at some high sampling rate from a set of Signals sampled at a lower rate and subject to additive noise and distortion. A set of periodically time-varying filters are employed in reconstructing the underlying Signal. Results are presented for a one-dimensional case involving simulated data, as well as for a two-dimensional case involving real image data where the image is processed by rows. In both cases, considerable improvement is evident after the Processing.
Y Nomura - One of the best experts on this subject based on the ideXlab platform.
-
adaptive volterra filters using Multirate Signal Processing and their application to identification of loudspeaker systems
Electronics and Communications in Japan Part Iii-fundamental Electronic Science, 2004Co-Authors: S Kinoshita, Yoshinobu Kajikawa, Y NomuraAbstract:The subband adaptive Volterra filter (SBAVF), which can assign the filter length of each subband arbitrarily, is proposed. If the frequency characteristics of a system to be identified are shifted to a certain bandwidth, it is usually not possible to carry out efficient identification by taking account of the shift of the bandwidth in a (full band) adaptive Volterra filter. On the other hand, in the proposed SBAVF, efficient system identification is possible by assigning a longer filter length to the dominant frequency range of the system of interest. When the proposed method is applied to a speaker system, it is shown through simulation results that the error attenuation can be improved from 1.5 dB to 7.5 dB in comparison with the conventional method. © 2004 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 87(7): 45–54, 2004; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.10135
-
volterra filters using Multirate Signal Processing and their application to loudspeaker systems
International Conference on Acoustics Speech and Signal Processing, 2001Co-Authors: S Kinoshita, Yoshinobu Kajikawa, Y NomuraAbstract:We propose two methods for reducing the computational complexity of Volterra filters. First, a method reducing the computational complexity of Volterra filters is proposed. This method can be realized by incorporating Multirate Signal Processing into the Volterra filters. Hence, it is possible to operate the bandlimited Volterra filter at a low sampling rate and with a short system length. Second, we also propose a method to replace the conventional Volterra filter with one including many zero coefficients by using Multirate Signal Processing. The conventional Volterra filter is bandlimited in order to avoid aliasing so that waste arithmetic is done. In contrast, the Volterra filter including many zero coefficients derived by the proposed method can eliminate such waste arithmetic. We demonstrate their effectiveness in application to loudspeaker systems whose nonlinear distortions are generally concentrated in the lower frequency band. Even though the processed frequency band is limited, the proposed method has about 0.03 times as many computational complexities as the conventional method.
