The Experts below are selected from a list of 15105 Experts worldwide ranked by ideXlab platform
Verger-gaugry Jean-louis - One of the best experts on this subject based on the ideXlab platform.
-
Alphabets, chemins de réécriture et représentations périodiques en bases algébriques
'Springer Fachmedien Wiesbaden GmbH', 2021Co-Authors: Dutykh Denys, Verger-gaugry Jean-louisAbstract:International audienceFor β > 1 a real Algebraic Integer (the base), the finite alphabets A ⊂ Z which realize the identity Q(β) = Per_A (β), where Per_A (β) is the set of complex numbers which are (β , A)-eventually periodic representations, are investigated. Comparing with the greedy algorithm, minimal and maximal alphabets are defined. The maximal alphabets are shown to be correlated to the asymptotics of the Pierce numbers of the base β and Lehmer's problem. The notion of rewriting trail is introduced to construct intermediate alphabets associated with small polynomial values of the base. Consequences on the representations of neighbourhoods of the origin in Q(β), generalizing Schmidt's theorem related to Pisot numbers, are investigated. Applications to Galois conjugation are given for convergent sequences of bases γ s := γ n,m 1 ,...,m s such that γ −1 s is the unique root in (0, 1) of an almost Newman polynomial of the type −1 + x + x^n + x^(m_1) +. .. + x_(m_s) , n ≥ 3, s ≥ 1, m_1 − n ≥ n − 1, m_(q+1) − m_q ≥ n − 1 for all q ≥ 1. For β > 1 a reciprocal Algebraic Integer close to one, the poles of modulus < 1 of the dynamical zeta function of the β-shift ζ_β (z) are shown, under some assumptions, to be zeroes of the minimal polynomial of β
-
Alphabets, rewriting trails and periodic representations in Algebraic bases
2021Co-Authors: Dutykh Denys, Verger-gaugry Jean-louisAbstract:For $\beta > 1$ a real Algebraic Integer ({\it the base}), the finite alphabets $\mathcal{A} \subset \mathbb{Z}$ which realize the identity $\mathbb{Q}(\beta) = {\rm Per}_{\mathcal{A}}(\beta)$, where ${\rm Per}_{\mathcal{A}}(\beta)$ is the set of complex numbers which are $(\beta, \mathcal{A})$-eventually periodic representations, are investigated. Comparing with the greedy algorithm, minimal and maximal alphabets are defined. The maximal alphabets are shown to be correlated to the asymptotics of the Pierce numbers of the base $\beta$ and Lehmer's problem. The notion of rewriting trail is introduced to construct intermediate alphabets associated with small polynomial values of the base. Consequences on the representations of neighbourhoods of the origin in $\mathbb{Q}(\beta)$, generalizing Schmidt's theorem related to Pisot numbers, are investigated. Applications to Galois conjugation are given for convergent sequences of bases $\gamma_s := \gamma_{n, m_1 , \ldots , m_s}$ such that $\gamma_{s}^{-1}$ is the unique root in $(0,1)$ of an almost Newman polynomial of the type $-1+x+x^n +x^{m_1}+\ldots+ x^{m_s}$, $n \geq 3$, $s \geq 1$, $m_1 - n \geq n-1$, $m_{q+1}-m_q \geq n-1$ for all $q \geq 1$. For $\beta > 1$ a reciprocal Algebraic Integer close to one, the poles of modulus $< 1$ of the dynamical zeta function of the $\beta$-shift $\zeta_{\beta}(z)$ are shown, under some assumptions, to be zeroes of the minimal polynomial of $\beta$.Comment: 17 pages, 7 figures, 29 reference
-
Une Démonstration de la Conjecture de Lehmer_v5
HAL CCSD, 2021Co-Authors: Verger-gaugry Jean-louisAbstract:The Conjecture of Lehmer is proved to be true. The proof mainly relies upon: (i) the properties of the Parry Upper functions f_{house α}(z) associated with the dynamical zeta functions ζ_{house α} (z) of the Rényi-Parry arithmetical dynamical systems (β-shift), for α a reciprocal Algebraic Integer α of house {house α} greater than 1, (ii) the discovery of lenticuli of poles of ζ_{house α}(z) which uniformly equidistribute at the limit on a limit "lenticular" arc of the unit circle, when α tends to 1^+ , giving rise to a continuous lenticular minorant M_r(α) of the Mahler measure M(α), (iii) the Poincaré asymptotic expansions of these poles and of this minorant M_r(α) as a function of the dynamical degree. The Conjecture of Schinzel-Zassenhaus is proved to be true. A Dobrowolski type minoration of the Mahler measure M(α) is obtained. The universal minorant of M(α) obtained is (θ_η)^{-1) > 1, for some Integer η ≥ 259, where θ_η is the positive real root of −1 + x + x^η. The set of Salem numbers is shown to be bounded from below by the Perron number (θ_{31})^(-1) = 1.08545. . ., dominant root of the trinomial −1 − z^(30) + z^(31). Whether Lehmer's number is the smallest Salem number remains open. For sequences of Algebraic Integers of Mahler measure smaller than the smallest Pisot number Θ = 1.3247. . ., whose houses have a dynamical degree tending to infinity, the Galois orbit measures of conjugates are proved to converge towards the Haar measure on |z| = 1 (limit equidistribution)
-
Une Démonstration de la Conjecture de Lehmer
HAL CCSD, 2021Co-Authors: Verger-gaugry Jean-louisAbstract:The Conjecture of Lehmer is proved to be true. The proof mainly relies upon: (i) the properties of the Parry Upper functions f_{house α}(z) associated with the dynamical zeta functions ζ_{house α} (z) of the Rényi-Parry arithmetical dynamical systems (β-shift), for α a reciprocal Algebraic Integer α of house {house α} greater than 1, (ii) the discovery of lenticuli of poles of ζ_{house α}(z) which uniformly equidistribute at the limit on a limit "lenticular" arc of the unit circle, when α tends to 1^+ , giving rise to a continuous lenticular minorant M_r(α) of the Mahler measure M(α), (iii) the Poincaré asymptotic expansions of these poles and of this minorant M_r(α) as a function of the dynamical degree. The Conjecture of Schinzel-Zassenhaus is proved to be true. A Dobrowolski type minoration of the Mahler measure M(α) is obtained. The universal minorant of M(α) obtained is (θ_η)^{-1) > 1, for some Integer η ≥ 259, where θ_η is the positive real root of −1 + x + x^η. The set of Salem numbers is shown to be bounded from below by the Perron number (θ_{31})^(-1) = 1.08545. . ., dominant root of the trinomial −1 − z^(30) + z^(31). Whether Lehmer's number is the smallest Salem number remains open. For sequences of Algebraic Integers of Mahler measure smaller than the smallest Pisot number Θ = 1.3247. . ., whose houses have a dynamical degree tending to infinity, the Galois orbit measures of conjugates are proved to converge towards the Haar measure on |z| = 1 (limit equidistribution). The dynamical zeta function is used to investigate the domain of very small Mahler measures of Algebraic Integers in the range (1, 1.176280], if any
-
A proof of the Conjecture of Lehmer
2021Co-Authors: Verger-gaugry Jean-louisAbstract:The Conjecture of Lehmer is proved to be true. The proof mainly relies upon: (i) the properties of the Parry Upper functions $f_{\house{\alpha}}(z)$ associated with the dynamical zeta functions $\zeta_{\house{\alpha}}(z)$ of the R\'enyi--Parry arithmetical dynamical systems ($\beta$-shift), for $\alpha$ a reciprocal Algebraic Integer of house $\house{\alpha}$ greater than 1, (ii) the discovery of lenticuli of poles of $\zeta_{\house{\alpha}}(z)$ which uniformly equidistribute at the limit on a limit "lenticular" arc of the unit circle, when $\house{\alpha}$ tends to $1^+$, giving rise to a continuous lenticular minorant ${\rm M}_{r}(\house{\alpha})$ of the Mahler measure ${\rm M}(\alpha)$, (iii) the Poincar\'e asymptotic expansions of these poles and of this minorant ${\rm M}_{r}(\house{\alpha})$ as a function of the dynamical degree. The Conjecture of Schinzel-Zassenhaus is proved to be true. A Dobrowolski type minoration of the Mahler measure M$(\alpha)$ is obtained. The universal minorant of M$(\alpha)$ obtained is $\theta_{\eta}^{-1} > 1$, for some Integer $\eta \geq 259$, where $\theta_{\eta}$ is the positive real root of $-1+x+x^{\eta}$. The set of Salem numbers is shown to be bounded from below by the Perron number $\theta_{31}^{-1} = 1.08545\ldots$, dominant root of the trinomial $-1 - z^{30} + z^{31}$. Whether Lehmer's number is the smallest Salem number remains open. For sequences of Algebraic Integers of Mahler measure smaller than the smallest Pisot number $\Theta = 1.3247\ldots$, whose houses have a dynamical degree tending to infinity, the Galois orbit measures of conjugates are proved to converge towards the Haar measure on $|z|=1$ (limit equidistribution).The dynamical zeta function is used to investigate the domain of very small Mahler measures of Algebraic Integers in the range (1, 1.176280 . . .], if any.Comment: Results unchanged, revised arguments in Section 5. "Mahler measures M(beta) < 1.176280" indicated explicitely everywhere. Theorem 10.1 and its proof: revised. arXiv admin note: substantial text overlap with arXiv:1709.0377
V S Dimitrov - One of the best experts on this subject based on the ideXlab platform.
-
computation of 2d 8 8 dct based on the loeffler factorization using Algebraic Integer encoding
IEEE Transactions on Computers, 2018Co-Authors: Diego F G Coelho, Arjuna Madanayake, Renato J Cintra, Sushmabhargavi Nimmalapalli, V S Dimitrov, Arnaud TisserandAbstract:This paper proposes a computational method for 2D 8×8 DCT based on Algebraic Integers. The proposed algorithm is based on the Loeffler 1D DCT algorithm, and it is shown to operate with exact computation—i.e., error-free arithmetic—up to the final reconstruction step (FRS). The proposed Algebraic Integer architecture maintains error-free computations until an entire block of DCT coefficients having size 8×8 is computed, unlike algorithms in the literature which claim to be error-free but in fact introduce arithmetic errors between the column- and row-wise 1D DCT stages in a 2D DCT operation. Fast algorithms are proposed for the final reconstruction step employing two approaches, namely, the expansion factor and dyadic approximation. A digital architecture is also proposed for a particular FRS algorithm, and is implemented on an FPGA platform for on-chip verification. The FPGA implementation operates at 360 MHz, and is capable of a real-time throughput of $3.6\cdot 10^8$ 2D DCTs of size 8×8 every second, with corresponding pixel rate of $2.3\cdot 10^{10}$ pixels per second. The digital architecture is synthesized using 180 nm CMOS standard cells and shows a chip area of 7.41 mm $^2$ . The CMOS design is predicted to operate at 893 MHz clock frequency, at a dynamic power consumption 13.22 mW/MHz $\cdot$ V $_{sup}^2$ .
-
a single channel architecture for Algebraic Integer based 8 times 8 2 d dct computation
IEEE Transactions on Circuits and Systems for Video Technology, 2013Co-Authors: Amila Edirisuriya, Arjuna Madanayake, Renato J Cintra, V S Dimitrov, Nilanka RajapakshaAbstract:An area efficient row-parallel architecture is proposed for the real-time implementation of bivariate Algebraic Integer (AI) encoded 2-D discrete cosine transform (DCT) for image and video processing. The proposed architecture computes 8 × 8 2-D DCT transform based on the Arai DCT algorithm. An improved fast algorithm for AI-based 1-D DCT computation is proposed along with a single channel 2-D DCT architecture. The design improves on the four-channel AI DCT architecture that was published recently by reducing the number of Integer channels to one and the number of eight-point 1-D DCT cores from five down to two. The architecture offers exact computation of 8 × 8 blocks of the 2-D DCT coefficients up to the FRS, which converts the coefficients from the AI representation to fixed-point format using the method of expansion factors. Prototype circuits corresponding to FRS blocks based on two expansion factors are realized, tested, and verified on FPGA-chip, using a Xilinx Virtex-6 XC6VLX240T device. Post place-and-route results show a 20% reduction in terms of area compared to the 2-D DCT architecture requiring five 1-D AI cores. The area-time and area-time2 complexity metrics are also reduced by 23% and 22% respectively for designs with eight-bit input word length. The digital realizations are simulated up to place and route for ASICs using 45 nm CMOS standard cells. The maximum estimated clock rate is 951 MHz for the CMOS realizations indicating 7.608·109 pixels/s and a 8 × 8 block rate of 118.875 MHz.
-
vlsi architectures for the 4 tap and 6 tap 2 d daubechies wavelet filters using Algebraic Integers
IEEE Transactions on Circuits and Systems I-regular Papers, 2013Co-Authors: Shiva Madishetty, Arjuna Madanayake, Renato J Cintra, V S Dimitrov, Dale H. MuglerAbstract:This paper proposes a novel Algebraic Integer (AI) based multi-encoding of Daubechies-4 and -6 2-D wavelet filters having error-free Integer-based computation. Digital VLSI architectures employing parallel channels are proposed, physically realized and tested. The multi-encoded AI framework allows a multiplication-free and computationally accurate architecture. It also guarantees a noise-free computation throughput the multi-level multi-rate 2-D filtering operation. A single final reconstruction step (FRS) furnishes filtered and down-sampled image outputs in fixed-point, resulting in low levels of quantization noise. Comparisons are provided between Daubechies-4 and -6 designs in terms of SNR, PSNR, hardware structure, and power consumptions, for different word lengths. SNR and PSNR improvements of approximately 30% were observed in favour of AI-based systems, when compared to 8-bit fixed-point schemes (six fractional bits). Further, FRS designs based on canonical signed digit representation and on expansion factors are proposed. The Daubechies-4 and -6 4-level VLSI architectures are prototyped on a Xilinx Virtex-6 vcx240t-1ff1156 FPGA device at 282 MHz and 146 MHz, respectively, with dynamic power consumption of 164 mW and 339 mW, respectively, and verified on FPGA chip using an ML605 platform.
-
a row parallel 8 times 8 2 d dct architecture using Algebraic Integer based exact computation
IEEE Transactions on Circuits and Systems for Video Technology, 2012Co-Authors: Arjuna Madanayake, Renato J Cintra, D Onen, Len T Bruton, V S Dimitrov, N Rajapaksha, Amila EdirisuriyaAbstract:An Algebraic Integer (AI)-based time-multiplexed row-parallel architecture and two final reconstruction step (FRS) algorithms are proposed for the implementation of bivariate AI encoded 2-D discrete cosine transform (DCT). The architecture directly realizes an error-free 2-D DCT without using FRSs between row-column transforms, leading to an 8 × 8 2-D DCT that is entirely free of quantization errors in AI basis. As a result, the user-selectable accuracy for each of the coefficients in the FRS facilitates each of the 64 coefficients to have its precision set independently of others, avoiding the leakage of quantization noise between channels as is the case for published DCT designs. The proposed FRS uses two approaches based on: 1) optimized Dempster-Macleod multipliers, and 2) expansion factor scaling. This architecture enables low-noise high-dynamic range applications in digital video processing that requires full control of the finite-precision computation of the 2-D DCT. The proposed architectures and FRS techniques are experimentally verified and validated using hardware implementations that are physically realized and verified on field-programmable gate array (FPGA) chip. Six designs, for 4-bit and 8-bit input word sizes, using the two proposed FRS schemes, have been designed, simulated, physically implemented, and measured. The maximum clock rate and block rate achieved among 8-bit input designs are 307.787 MHz and 38.47 MHz, respectively, implying a pixel rate of 8 × 307.787≈2.462 GHz if eventually embedded in a real- time video-processing system. The equivalent frame rate is about 1187.35Hz for the image size of 1920 × 1080. All implementations are functional on a Xilinx Virtex-6 XC6VLX240T FPGA device.
-
an accurate fixed point 8 8 idct algorithm based on 2 d Algebraic Integer representation
Proceedings of SPIE, 2007Co-Authors: Ihab Amer, W Badawy, V S DimitrovAbstract:This paper proposes an algorithm that is based on the application of Algebraic Integer (AI) representation of numbers on the AAN fast Inverse Discrete Cosine Transform (IDCT) algorithm. AI representation allows for maintaining an error-free representation of IDCT until the last step of each 1-D stage of the algorithm, where a reconstruction step from the AI domain to the fixed precision binary domain is required. This delay in introducing the rounding error prevents the accumulation of error throughout the calculations, which leads to the reported high-accuracy results. The proposed algorithm is simple and well suited for hardware implementation due to the absence of computationally extensive multiplications. The obtained results confirm the high accuracy of the proposed algorithm compared to other fixed-point implementations of IDCT.
Khan A. Wahid - One of the best experts on this subject based on the ideXlab platform.
-
multi beamforming with uniform linear array and Algebraic Integer quantization based dct
International Symposium on Circuits and Systems, 2015Co-Authors: Ziad Gias, Md Mehedi Hasan, Khan A. WahidAbstract:Aperture arrays are widely used in beamforming applications where element signals are steered to a particular direction of interest and a single beam is formed. Multi-beamforming is an extension of single beamforming which is desired in the fields where sources located in multiple directions are of interest. Discrete Fourier Transform (DFT) is usually used in these scenarios to segregate the received signals based on their direction of arrivals. In this work, instead of DFT, the Discrete Cosine Transform (DCT) is used and an efficient implementation technique using Decomposed Algebraic Integer Quantization (DAIQ) is proposed for error-free and multiplier-less implementation of the DCT. Its performance for beamforming application is also studied.
-
An Efficient Algorithm for Daubechies Lifting Wavelets Using Algebraic Integers
Canadian Journal of Electrical and Computer Engineering, 2014Co-Authors: Pranav Balakrishnan, Mehedi Hasan, Khan A. WahidAbstract:This paper presents an efficient lifting-based algorithm for the computation of Daubechies-4 (D4) and Daubechies-6 (D6) wavelet transforms using an Algebraic Integer quantization (AIQ) technique. The transform filter coefficients are first mapped by Algebraic Integers, and then quantized using a subband coding algorithm. The performance of the algorithm is assessed by using several benchmark images and the results are compared in terms of peak signal-to-noise ratio and bit rate. The architecture of both D4 and D6 is implemented on field programmable gate array (FPGA). The results show that the proposed AIQ-based implementations perform better and consume fewer resources than similar other lifting-based techniques.
-
error free algorithms and architectures of discrete cosine transforms using multidimensional Algebraic Integer quantization
2008Co-Authors: Khan A. WahidAbstract:The recent growth of data intensive multimedia-based applications has sustained the need for more efficient ways to encode signals and images. Over the years, the Discrete Cosine Transform (DCT) has emerged as the most popular transform for many image and video compression applications. Because of its enormous popularity, much research has been published on fast algorithms, where the effort is devoted to reducing the number of arithmetic operations used. In all the previous cases of finite-precision implementations, approximation is required to implement the real-valued irrational transform coefficients - this not only results in computational error throughout the transform process, but also limits the quality of the reconstruction process. An error-free encoding using Algebraic Integers, previously introduced by Vassil Dimitrov, has been shown to be an effective way of resolving the issue. This is a mapping technique that encodes the irrational transform basis functions using Algebraic Integers. The mapping scheme is referred to as Algebraic Integer Quantization (AIQ). After the success of the previous schemes, this research extends the concept of error-free (infinite-precision) mapping and investigates novel AIQ-based architectures for the fast implementation of several 8x8 2-D scaled Discrete Cosine Transforms and Inverse scaled DCTs. A detailed discussion on the AIQ-based Integer-like 8x8 2-D DCT for the H.264 standard, along its quantization and de-quantization stages, is also presented. Apart from the multiplication-free nature, this new mapping scheme eliminates any computational or quantization errors during the transform stage and resulting in hardware-efficient and high-speed designs that focus on real-time image or video compression and HDTV applications. This research work also discusses VLSI implementations and architectures for these scaled and Integer-like DCT algorithms. For FPGA implementations, both Xilinx and Altera cells have been used, whereas for the ASIC designs, TSMC Artisan 0.18um library cells have been used. These new architectures have been shown to perform at a rate of 40% higher frequency and a hardware cost reduction of 30% compared to previously published architectures. Finally several finite wordlength simulations have been presented which show that the accuracy and the precision of the designed hardware fully comply with the IEEE implementation standard (for JPEG and MPEG-4 decoders).
-
error free computation of 8 spl times 8 2d dct and idct using two dimensional Algebraic Integer quantization
Symposium on Computer Arithmetic, 2005Co-Authors: Khan A. Wahid, V S DimitrovAbstract:This paper presents a novel error-free (infinite-precision) architecture for the fast implementation of both 8/spl times/8 2D discrete cosine transform and inverse DCT. The architecture uses a new Algebraic Integer quantization of a 1D radix-8 DCT that allows the separable computation of a 2D 8/spl times/8 DCT without any intermediate number representation conversions. This is a considerable improvement on previously introduced Algebraic Integer encoding techniques to compute both DCT and IDCT which eliminates the requirements to approximate the transformation matrix elements by obtaining their exact representations and hence mapping the transcendental functions without any errors. Using this encoding scheme, an entire 8/spl times/8 1D DCT-SQ (scalar quantization) algorithm can be implemented with only 24 adders. Apart from the multiplication-free nature, this new mapping scheme fits to this algorithm, eliminating any computational or quantization errors and resulting short-word-length and high-speed-design.
-
VLSI ARCHITECTURES OF DAUBECHIES WAVELET TRANSFORMS USING Algebraic IntegerS
Journal of Circuits Systems and Computers, 2004Co-Authors: Khan A. Wahid, Vassil S. Dimitrov, Graham A. JullienAbstract:Two-Dimensional Wavelet Transforms have proven to be highly effective tools for image analysis. In this paper, we present a VLSI implementation of four- and six-coefficient Daubechies Wavelet Transforms using an Algebraic Integer encoding representation for the coefficients. The Daubechies filters (DAUB4 and DAUB6) provide excellent spatial and spectral locality, properties which make it useful in image compression. In our algorithm, the Algebraic Integer representation of the wavelet coefficients provides error-free calculations until the final reconstruction step. This also makes the VLSI architecture simple, multiplication-free and inherently parallel. Compared to other DWT algorithms found in the literature, such as embedded zero-tree, recursive or semi-recursive, linear systolic arrays and conventional fixed-point binary architectures, it has reduced hardware cost, lower power dissipation and optimized data-bus utilization. The architecture is also cascadable for computation of one- or multi-dimensional Daubechies Discrete Wavelet Transforms.
Arjuna Madanayake - One of the best experts on this subject based on the ideXlab platform.
-
computation of 2d 8 8 dct based on the loeffler factorization using Algebraic Integer encoding
IEEE Transactions on Computers, 2018Co-Authors: Diego F G Coelho, Arjuna Madanayake, Renato J Cintra, Sushmabhargavi Nimmalapalli, V S Dimitrov, Arnaud TisserandAbstract:This paper proposes a computational method for 2D 8×8 DCT based on Algebraic Integers. The proposed algorithm is based on the Loeffler 1D DCT algorithm, and it is shown to operate with exact computation—i.e., error-free arithmetic—up to the final reconstruction step (FRS). The proposed Algebraic Integer architecture maintains error-free computations until an entire block of DCT coefficients having size 8×8 is computed, unlike algorithms in the literature which claim to be error-free but in fact introduce arithmetic errors between the column- and row-wise 1D DCT stages in a 2D DCT operation. Fast algorithms are proposed for the final reconstruction step employing two approaches, namely, the expansion factor and dyadic approximation. A digital architecture is also proposed for a particular FRS algorithm, and is implemented on an FPGA platform for on-chip verification. The FPGA implementation operates at 360 MHz, and is capable of a real-time throughput of $3.6\cdot 10^8$ 2D DCTs of size 8×8 every second, with corresponding pixel rate of $2.3\cdot 10^{10}$ pixels per second. The digital architecture is synthesized using 180 nm CMOS standard cells and shows a chip area of 7.41 mm $^2$ . The CMOS design is predicted to operate at 893 MHz clock frequency, at a dynamic power consumption 13.22 mW/MHz $\cdot$ V $_{sup}^2$ .
-
a single channel architecture for Algebraic Integer based 8 times 8 2 d dct computation
IEEE Transactions on Circuits and Systems for Video Technology, 2013Co-Authors: Amila Edirisuriya, Arjuna Madanayake, Renato J Cintra, V S Dimitrov, Nilanka RajapakshaAbstract:An area efficient row-parallel architecture is proposed for the real-time implementation of bivariate Algebraic Integer (AI) encoded 2-D discrete cosine transform (DCT) for image and video processing. The proposed architecture computes 8 × 8 2-D DCT transform based on the Arai DCT algorithm. An improved fast algorithm for AI-based 1-D DCT computation is proposed along with a single channel 2-D DCT architecture. The design improves on the four-channel AI DCT architecture that was published recently by reducing the number of Integer channels to one and the number of eight-point 1-D DCT cores from five down to two. The architecture offers exact computation of 8 × 8 blocks of the 2-D DCT coefficients up to the FRS, which converts the coefficients from the AI representation to fixed-point format using the method of expansion factors. Prototype circuits corresponding to FRS blocks based on two expansion factors are realized, tested, and verified on FPGA-chip, using a Xilinx Virtex-6 XC6VLX240T device. Post place-and-route results show a 20% reduction in terms of area compared to the 2-D DCT architecture requiring five 1-D AI cores. The area-time and area-time2 complexity metrics are also reduced by 23% and 22% respectively for designs with eight-bit input word length. The digital realizations are simulated up to place and route for ASICs using 45 nm CMOS standard cells. The maximum estimated clock rate is 951 MHz for the CMOS realizations indicating 7.608·109 pixels/s and a 8 × 8 block rate of 118.875 MHz.
-
Algebraic Integer architecture with minimum adder count for the 2-D Daubechies 4-tap filters banks
Multidimensional Systems and Signal Processing, 2013Co-Authors: Shiva Madishetty, Vassil S. Dimitrov, Arjuna Madanayake, Renato J Cintra, Dale H. MuglerAbstract:A multiplierless architecture based on Algebraic Integer representation for computing the Daubechies 4-tap wavelet transform for 1-D/2-D signal processing is proposed. This architecture improves on previous designs in a sense that it minimizes the number of parallel 2-input adder circuits. The algorithm was achieved using numerical optimization based o exhaustive search over the Algebraic Integer representation. The proposed architecture furnishes exact computation up to the final reconstruction step, which is the operation that maps the exactly computed filtered results from Algebraic Integer representation to fixed-point. Compared to Madishetty et al. (IEEE Trans Circuits Syst I (Accepted, In Press), 2012a), this architecture shows a reduction of $$10\cdot n-3$$ 10 · n - 3 adder circuits, where $$n$$ n is the number of wavelet decomposition levels. Standard $$512\times 512$$ 512 × 512 images Mandrill, Lena, and Cameraman were submitted to digital realizations of both proposed Algebraic Integer based as well as fixed-point schemes, leading to quantifiable comparisons. The design is physically implemented for a 4-level 2-D decomposition using a Xilinx Virtex-6 vcx240t-1ff1156 FPGA device operating at up to a maximum clock frequency of 263.15 MHz. The FPGA implementation is tested using hardware co-simulation using an ML605 board with clock of 100 MHz. A 45 nm CMOS synthesis shows improved clock frequency of better than 500 MHz for a supply voltage of 1.1 V.
-
vlsi architectures for the 4 tap and 6 tap 2 d daubechies wavelet filters using Algebraic Integers
IEEE Transactions on Circuits and Systems I-regular Papers, 2013Co-Authors: Shiva Madishetty, Arjuna Madanayake, Renato J Cintra, V S Dimitrov, Dale H. MuglerAbstract:This paper proposes a novel Algebraic Integer (AI) based multi-encoding of Daubechies-4 and -6 2-D wavelet filters having error-free Integer-based computation. Digital VLSI architectures employing parallel channels are proposed, physically realized and tested. The multi-encoded AI framework allows a multiplication-free and computationally accurate architecture. It also guarantees a noise-free computation throughput the multi-level multi-rate 2-D filtering operation. A single final reconstruction step (FRS) furnishes filtered and down-sampled image outputs in fixed-point, resulting in low levels of quantization noise. Comparisons are provided between Daubechies-4 and -6 designs in terms of SNR, PSNR, hardware structure, and power consumptions, for different word lengths. SNR and PSNR improvements of approximately 30% were observed in favour of AI-based systems, when compared to 8-bit fixed-point schemes (six fractional bits). Further, FRS designs based on canonical signed digit representation and on expansion factors are proposed. The Daubechies-4 and -6 4-level VLSI architectures are prototyped on a Xilinx Virtex-6 vcx240t-1ff1156 FPGA device at 282 MHz and 146 MHz, respectively, with dynamic power consumption of 164 mW and 339 mW, respectively, and verified on FPGA chip using an ML605 platform.
-
Asynchronous realization of Algebraic Integer-based 2D DCT using achronix speedster SPD60 FPGA
Journal of Electrical and Computer Engineering, 2013Co-Authors: Nilanka Rajapaksha, Amila Edirisuriya, Dennis Onen, Arjuna Madanayake, Renato J Cintra, Ihab Amer, Vassil S. DimitrovAbstract:Transformation and quantization play a critical role in video codecs. Recently proposed Algebraic-Integer-(AI-) based discrete cosine transform (DCT) algorithms are analyzed in the presence of quantization, using the High Efficiency Video Coding (HEVC) standard. AI DCT is implemented and tested on asynchronous quasi delay-insensitive logic, using Achronix SPD60 field programmable gate array (FPGA), which leads to lower complexity, higher speed of operation, and insensitivity to process-voltage-temperature variations. Performance of AI DCT with HEVC is measured in terms of the accuracy of the transform coefficients and the overall rate-distortion (R-D) characteristics, using HM 7.1 reference software. Results indicate a 31% improvement over the Integer DCT in the number of transform coefficients having error within 1%. The performance of the 65 nm asynchronous hardware in terms of speed of operation is investigated and compared with the 65 nm synchronous Xilinx FPGA. Considering word lengths of 5 and 6 bits, a speed increase of 230% and 199% is observed, respectively. These results indicate that AI DCT can be potentially utilized in HEVC for applications demanding high accuracy as well as high throughput. However, novel quantization schemes are required to allow the accuracy improvements obtained.
Renato J Cintra - One of the best experts on this subject based on the ideXlab platform.
-
computation of 2d 8 8 dct based on the loeffler factorization using Algebraic Integer encoding
IEEE Transactions on Computers, 2018Co-Authors: Diego F G Coelho, Arjuna Madanayake, Renato J Cintra, Sushmabhargavi Nimmalapalli, V S Dimitrov, Arnaud TisserandAbstract:This paper proposes a computational method for 2D 8×8 DCT based on Algebraic Integers. The proposed algorithm is based on the Loeffler 1D DCT algorithm, and it is shown to operate with exact computation—i.e., error-free arithmetic—up to the final reconstruction step (FRS). The proposed Algebraic Integer architecture maintains error-free computations until an entire block of DCT coefficients having size 8×8 is computed, unlike algorithms in the literature which claim to be error-free but in fact introduce arithmetic errors between the column- and row-wise 1D DCT stages in a 2D DCT operation. Fast algorithms are proposed for the final reconstruction step employing two approaches, namely, the expansion factor and dyadic approximation. A digital architecture is also proposed for a particular FRS algorithm, and is implemented on an FPGA platform for on-chip verification. The FPGA implementation operates at 360 MHz, and is capable of a real-time throughput of $3.6\cdot 10^8$ 2D DCTs of size 8×8 every second, with corresponding pixel rate of $2.3\cdot 10^{10}$ pixels per second. The digital architecture is synthesized using 180 nm CMOS standard cells and shows a chip area of 7.41 mm $^2$ . The CMOS design is predicted to operate at 893 MHz clock frequency, at a dynamic power consumption 13.22 mW/MHz $\cdot$ V $_{sup}^2$ .
-
a single channel architecture for Algebraic Integer based 8 times 8 2 d dct computation
IEEE Transactions on Circuits and Systems for Video Technology, 2013Co-Authors: Amila Edirisuriya, Arjuna Madanayake, Renato J Cintra, V S Dimitrov, Nilanka RajapakshaAbstract:An area efficient row-parallel architecture is proposed for the real-time implementation of bivariate Algebraic Integer (AI) encoded 2-D discrete cosine transform (DCT) for image and video processing. The proposed architecture computes 8 × 8 2-D DCT transform based on the Arai DCT algorithm. An improved fast algorithm for AI-based 1-D DCT computation is proposed along with a single channel 2-D DCT architecture. The design improves on the four-channel AI DCT architecture that was published recently by reducing the number of Integer channels to one and the number of eight-point 1-D DCT cores from five down to two. The architecture offers exact computation of 8 × 8 blocks of the 2-D DCT coefficients up to the FRS, which converts the coefficients from the AI representation to fixed-point format using the method of expansion factors. Prototype circuits corresponding to FRS blocks based on two expansion factors are realized, tested, and verified on FPGA-chip, using a Xilinx Virtex-6 XC6VLX240T device. Post place-and-route results show a 20% reduction in terms of area compared to the 2-D DCT architecture requiring five 1-D AI cores. The area-time and area-time2 complexity metrics are also reduced by 23% and 22% respectively for designs with eight-bit input word length. The digital realizations are simulated up to place and route for ASICs using 45 nm CMOS standard cells. The maximum estimated clock rate is 951 MHz for the CMOS realizations indicating 7.608·109 pixels/s and a 8 × 8 block rate of 118.875 MHz.
-
Algebraic Integer architecture with minimum adder count for the 2-D Daubechies 4-tap filters banks
Multidimensional Systems and Signal Processing, 2013Co-Authors: Shiva Madishetty, Vassil S. Dimitrov, Arjuna Madanayake, Renato J Cintra, Dale H. MuglerAbstract:A multiplierless architecture based on Algebraic Integer representation for computing the Daubechies 4-tap wavelet transform for 1-D/2-D signal processing is proposed. This architecture improves on previous designs in a sense that it minimizes the number of parallel 2-input adder circuits. The algorithm was achieved using numerical optimization based o exhaustive search over the Algebraic Integer representation. The proposed architecture furnishes exact computation up to the final reconstruction step, which is the operation that maps the exactly computed filtered results from Algebraic Integer representation to fixed-point. Compared to Madishetty et al. (IEEE Trans Circuits Syst I (Accepted, In Press), 2012a), this architecture shows a reduction of $$10\cdot n-3$$ 10 · n - 3 adder circuits, where $$n$$ n is the number of wavelet decomposition levels. Standard $$512\times 512$$ 512 × 512 images Mandrill, Lena, and Cameraman were submitted to digital realizations of both proposed Algebraic Integer based as well as fixed-point schemes, leading to quantifiable comparisons. The design is physically implemented for a 4-level 2-D decomposition using a Xilinx Virtex-6 vcx240t-1ff1156 FPGA device operating at up to a maximum clock frequency of 263.15 MHz. The FPGA implementation is tested using hardware co-simulation using an ML605 board with clock of 100 MHz. A 45 nm CMOS synthesis shows improved clock frequency of better than 500 MHz for a supply voltage of 1.1 V.
-
vlsi architectures for the 4 tap and 6 tap 2 d daubechies wavelet filters using Algebraic Integers
IEEE Transactions on Circuits and Systems I-regular Papers, 2013Co-Authors: Shiva Madishetty, Arjuna Madanayake, Renato J Cintra, V S Dimitrov, Dale H. MuglerAbstract:This paper proposes a novel Algebraic Integer (AI) based multi-encoding of Daubechies-4 and -6 2-D wavelet filters having error-free Integer-based computation. Digital VLSI architectures employing parallel channels are proposed, physically realized and tested. The multi-encoded AI framework allows a multiplication-free and computationally accurate architecture. It also guarantees a noise-free computation throughput the multi-level multi-rate 2-D filtering operation. A single final reconstruction step (FRS) furnishes filtered and down-sampled image outputs in fixed-point, resulting in low levels of quantization noise. Comparisons are provided between Daubechies-4 and -6 designs in terms of SNR, PSNR, hardware structure, and power consumptions, for different word lengths. SNR and PSNR improvements of approximately 30% were observed in favour of AI-based systems, when compared to 8-bit fixed-point schemes (six fractional bits). Further, FRS designs based on canonical signed digit representation and on expansion factors are proposed. The Daubechies-4 and -6 4-level VLSI architectures are prototyped on a Xilinx Virtex-6 vcx240t-1ff1156 FPGA device at 282 MHz and 146 MHz, respectively, with dynamic power consumption of 164 mW and 339 mW, respectively, and verified on FPGA chip using an ML605 platform.
-
Asynchronous realization of Algebraic Integer-based 2D DCT using achronix speedster SPD60 FPGA
Journal of Electrical and Computer Engineering, 2013Co-Authors: Nilanka Rajapaksha, Amila Edirisuriya, Dennis Onen, Arjuna Madanayake, Renato J Cintra, Ihab Amer, Vassil S. DimitrovAbstract:Transformation and quantization play a critical role in video codecs. Recently proposed Algebraic-Integer-(AI-) based discrete cosine transform (DCT) algorithms are analyzed in the presence of quantization, using the High Efficiency Video Coding (HEVC) standard. AI DCT is implemented and tested on asynchronous quasi delay-insensitive logic, using Achronix SPD60 field programmable gate array (FPGA), which leads to lower complexity, higher speed of operation, and insensitivity to process-voltage-temperature variations. Performance of AI DCT with HEVC is measured in terms of the accuracy of the transform coefficients and the overall rate-distortion (R-D) characteristics, using HM 7.1 reference software. Results indicate a 31% improvement over the Integer DCT in the number of transform coefficients having error within 1%. The performance of the 65 nm asynchronous hardware in terms of speed of operation is investigated and compared with the 65 nm synchronous Xilinx FPGA. Considering word lengths of 5 and 6 bits, a speed increase of 230% and 199% is observed, respectively. These results indicate that AI DCT can be potentially utilized in HEVC for applications demanding high accuracy as well as high throughput. However, novel quantization schemes are required to allow the accuracy improvements obtained.