电子种越女学 University of Electroe Scioncad TechofChina 986 Chapter 15 Numerical Strength Reduction Xiang LING National Key Lab of Science and Technology on Communications
Chapter 15 Numerical Strength Reduction Xiang LING National Key Lab of Science and Technology on Communications
Introduction /96 ■ Numerical strength reduction is a transformation techniques for reducing strength of DSP computations. This transformation relays on sub expression elimination (also referred to as substructure sharing). 2021年2月 通信抗干扰技术国家重点实验室 2
2021年2月 通信抗干扰技术国家重点实验室 2 Introduction Numerical strength reduction is a transformation techniques for reducing strength of DSP computations. This transformation relays on sub expression elimination (also referred to as substructure sharing)
Sub-expression elimination 96 Sub-expression elimination is a numerical transformation of the constant multiplications that can lead to efficient hardware in terms of area,power and speed. Sub-expression can only be performed on constant multiplications that operate on a common variable. It is essentially the process of examining the shift and add implementations of the constant multiplications and finding redundant operations. Example:a x and b x,where a=001101 and b=011011 can be performed as follows: ■ a*×=000100*×+001001*× ■ b*×=010010*×+001001*×=(001001*x)<<1+(001001*×) The term 001001 x needs to be computed only once. So,multiplications were implemented using 3 shifts and 3 adds as opposed to 5 shifts and 5 adds. 2021年2月 通信抗干扰技术国家重点实验室 3
2021年2月 通信抗干扰技术国家重点实验室 3 Sub-expression elimination Sub-expression elimination is a numerical transformation of the constant multiplications that can lead to efficient hardware in terms of area, power and speed. Sub-expression can only be performed on constant multiplications that operate on a common variable. It is essentially the process of examining the shift and add implementations of the constant multiplications and finding redundant operations. Example: a * x and b * x, where a = 001101 and b = 011011 can be performed as follows: a * x = 000100 * x + 001001 * x b * x = 010010 * x + 001001 * x = (001001 * x) << 1 +(001001 * x). The term 001001 * x needs to be computed only once. So, multiplications were implemented using 3 shifts and 3 adds as opposed to 5 shifts and 5 adds
Multiple Constant Multiplication The algorithm for MCM uses an iterative matching process that consists of the following steps: 1. Express each constant in the set using a binary format (such as signed,unsigned,2's complement representation). 2. Determine the number of bit-wise matches(nonzero bits)between all of the constants in the set. 3.Choose the best match. 4. Eliminate the redundancy from the best match.Return the remainders and the redundancy to the set of coefficients. 5.Repeat Steps 2-4 until no improvement is achieved. 2021年2月 通信抗干扰技术国家重点实验室 4
2021年2月 通信抗干扰技术国家重点实验室 4 Multiple Constant Multiplication The algorithm for MCM uses an iterative matching process that consists of the following steps: 1. Express each constant in the set using a binary format (such as signed, unsigned, 2’s complement representation). 2. Determine the number of bit-wise matches (nonzero bits) between all of the constants in the set. 3. Choose the best match. 4. Eliminate the redundancy from the best match. Return the remainders and the redundancy to the set of coefficients. 5. Repeat Steps 2-4 until no improvement is achieved
Multiple Constant /96 Multiplication Example: Constant Value Unsigned a 237 11101101 b 182 10110110 93 01011101 Binary representation of constants Constant Unsigned Constant Unsigned Rem.of a 10100000 Rem.of a 00000000 b 10110110 Rem.of b 00010110 Rem.of c 00010000 Rem.of c 00010000 Red.of a,c 01001101 Red.of a,c 01001101 Red.of Rem a,b 10100000 Updated set of constants 1st iteration Updated set of constants 2nd iteration 2021年2月 通信抗干扰技术国家重点实验室 5
2021年2月 通信抗干扰技术国家重点实验室 5 Multiple Constant Multiplication