Fixed point multiplying apparatus and method using encoded multiplicand
AssigneeElectronics and Telecommunications Research Institute
InventorJin Wuk Seok
Life of this patent
Estimating the term…
Abstract
The invention relates to a fixed point multiplying apparatus and method using an encoded multiplicand. The multiplicand is encoded into an independent binary system instead of a conventional binary system and each bit value of the encoded multiplicand is used as a control signal about an inputted multiplier in order to effectively execute a fixed point multiplication used in a transform algorithm such as the DCT in use for a multimedia codec. The multiplication is executed at a high speed with a simple structure and a small gate number.
Claims5
A fixed point multiplying apparatus for performing a multiplication of a multiplier and an encoded multiplicand, the apparatus comprising:
- n number of n bit shift registers for storing binary data of the multiplier by shifting each of the binary data by one bit;
- adders for selecting and receiving one data as an input from a group consisting of the data stored in the shift registers, inverted data of the stored data, and 0 in response to a control signal for selecting the input;
- control blocks for storing multiplicand data which are binary encoded according to equation 1, selecting the shift registers corresponding to bit values of the multiplicand data, and applying the control signal to the corresponding adders;
- and
- n−1 number of multiplexers for sequentially adding output values from the adders according to each bit to output multiplication data of the multiplier and the multiplicand:
- 15 w k = C k M - 1 · ( 1 - 2 n k - ( M - 1 ) ) · 2 0 + ∑ i = 0 M - 2 C k i · ( 1 - 2 n k i ) · 2 - ( M - 1 ) + i ,
- where ∀i ∈Z[0,M−1], Cki∈{0,1} and nkl∈{0,1},
- 16 Y = ∑ k w k x k ,
- where Wk is the multiplier and Xk is the multiplicand, and
- 17 x k = - C _ k i · 2 M - 1 + ∑ j = 0 M - 2 C _ k j · 2 j ,
- where
- 18 ∀ j ∈ Z [ 0 , M - 1 ] and C _ k j ∈ { 0 , 1 } . Equation 1
A fixed point multiplying method for performing a multiplication of a multiplier and a multiplicand by encoding the multiplicand, the method comprising the following steps of:
- storing binary data of the multiplier into n number of n bit shift registers by shifting each of the binary data by one bit;
- storing multiplicand data which are binary encoded according to Equation 1;
- selecting one data from a group including the data stored in the shift registers, inverted data of the stored data and 0 in response to each of the bit-shifted data of the encoded multiplicand data;
- and
- sequentially adding the selected data according to each bit to output multiplication data of the multiplier and the multiplicand:
- 19 w k = C k M - 1 · ( 1 - 2 n k - ( M - 1 ) ) · 2 0 + ∑ i = 0 M - 2 C k i · ( 1 - 2 n k i ) · 2 - ( M - 1 ) + i ,
- where
- 20 ∀ i ∈ Z [ 0 , M - 1 ] , C k i ∈ { 0 , 1 } and n k i ∈ { 0 , 1 } ,
- 21 Y = ∑ k w k x k ,
- where Wk is the multiplier and Xk is the multiplicand, and
- 22 x k = - C —i k · 2 M - 1 + ∑ j = 0 M - 2 C k —j · 2 j ,
- where
- 23 ∀ j ∈ Z [ 0 , M - 1 ] and C — k j ∈ { 0 , 1 } . Equation 1
A record medium readable by a digital processing device including a program of command languages which can be executed by the digital processing device for performing a fixed point multiplying method using an encoded multiplicand, wherein the program is executed in the following steps of:
- storing binary data of the multiplier into n number of n bit shift registers by shifting each of the binary data by one bit;
- storing multiplicand data which are binary encoded according to Equation 1;
- selecting one data from a group including the data stored in the shift registers, inverted data of the stored data and 0 in response to each of the bit-shifted data of the encoded multiplicand data;
- and
- sequentially adding the selected data according to each bit to output multiplication data of the multiplier and the multiplicand:
- 24 w k = C k M - 1 · ( 1 - 2 n k - ( M - 1 ) ) · 2 0 + ∑ i = 0 M - 2 C k i · ( 1 - 2 n k i ) · 2 - M - 1 ) + i , where ∀ i ∈ Z [ 0 , M - 1 ] , C k i ∈ { 0 , 1 } and n k i ∈ { 0 , 1 } , Y = ∑ k w k x k ,
- where Wk is the multiplier and Xk is the multiplicand, and
- 25 x k = - C k —i · 2 M - 1 + ∑ j = 0 M - 2 C — k j · 2 j ,
- where ∀j ∈Z[0,M−1] and {overscore (C)}kj∈{0,1} Equation 1.
Dependencies are inferred from the claim text.