| JP2014194599 | OCR SYSTEM |
| WO/2017/112679 | MULTIMODAL CLOSED-LOOP BRAIN-COMPUTER INTERFACE AND PERIPHERAL STIMULAITON FOR NEURO-REHABILITATION |
| WO/2001/067380 | CORRECTION OF DISTORTIONS IN FORM PROCESSING |
CHATTERJEE CHANCHAL (US)
| US6493467B1 | 2002-12-10 | |||
| US5367476A | 1994-11-22 | |||
| US4805129A | 1989-02-14 |
| Claims:
1. A method for processing an image signal, comprising: providing at least one Finite Impulse Response (FIR) filter, wherein said at least one FIR filter comprises at least one of said functions:
(λ 1 +λ2+c*ONE) » 1, where ce {-2,-1,0,1,2},
(A 1 +A 2 +A 3 +A 4 +c*C)NE) » 2, where ce {0,1,2}, (Ai+A 2 +A 3 +A 4 +A 5 +A 6 +A 7 +A 8 +c*ONE) » 3, where ce {0,1,2,3,4}, (A 1 +A 2 +A 3 +A 4 +...+A 15 +A 16 +c*ONE) » 4, where ce {0,1,2,..., 8}, where each of said A 1 -A] 6 represents a vector, where ONE represents a packed vector; where » represents a bitwise logical right shift; and applying said at least one FIR filter to process the image signal, where a result of said at least one FIR filter is computed using at least an AVG operation.
2. The method of claim 1, wherein said AVG operation is expressed as:
A VG(A,B) = [(fli+b { ) » 1 for /=1,...,8], where ^ and b \ represent data values, where
A represents a vector and where B represents a vector.
3. The method of claim 1, wherein said ONE is expressed as:
ONE = [0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01], where 0x01 is a byte containing 1 in its least significant bit and Os elsewhere.
4. The method of claim 1, wherein said result, R, of said at least one FIR filter is computed as:
R =AVG(Bι,B 2 ) ~ (Bi^B 2 ) | ((AiM 2 ) & (A3M4)) & ONE, where λ represents bitwise exclusive OR, where | represents bitwise OR, and & represents bitwise AND.
5. The method of claim 1, wherein said result, R, of said at least one FIR filter is computed as:
R = AVG(Bι,B 2 ) + (B\ A B 2 ) & ((A jM 2 ) | (A3M4)) & ONE, where λ represents bitwise exclusive OR, where | represents bitwise OR, and & represents bitwise AND.
6. The method of claim 1, wherein said result, R, of said at least one FIR filter is computed as:
R = AVG(B h B 2 ) + (Bι A B 2 ) & (AiM 2 ) & (A 3 λ A 4 ) & ONE, where λ represents bitwise exclusive OR, where ) represents bitwise OR, and & represents bitwise AND.
7. The method of claim 1, wherein said result, R, of said at least one FIR filter is computed as:
R = A VG(A i ,B 2 ) + (A { A B 2 ) & ONE, where λ represents bitwise exclusive OR, where | represents bitwise OR, and & represents bitwise AND.
8. The method of claim 1, wherein said result, R, of said at least one FIR filter is computed as:
R = SUBSATfU - E), where U=ADDSAT(D+2*ONE), where 2*ONE is a constant, where D = AVG(AVG(AVG(A 15 A 2 ), AVG(A 35 A 4 )), AVG(AVG(A 5 ,A 6 ), AVG(A 75 A 8 ))), where E =SUBSAT(U - L) & 7*ONE, where 7*ONE is a constant, where L = (A 1 +A 2 +A 3 +A 4 +A 5 +A 6 +A 7 +A 8 +c*ONE)»3, where c*ONE is a constant, and where SUBSAT(A,B) = [CLIP(aι-b-) for i=l,...,8], where ADDSAT(A,B) = [CL/P(α;+fy) for and where CLIP (x) clips x to range [0,255].
9. A computer-readable carrier having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to perform the steps of a method for processing an image signal, comprising of: providing at least one Finite Impulse Response (FIR) filter, wherein said at least one FIR filter comprises at least one of said functions:
(A 1 +A 2 +c*ONE) » 1, where ce {-2,-1,0,1,2},
(A I +A 2 +A 3 +A 4 +c*ONE) » 2, where ce {0,1,2},
(Ai+A 2 +A 3 +A 4 +A 5 +A 6 +A 7 +A 8 +c*ONE) » 3, where ce {0,1,2,3,4}, (Ai+A 2 +A 3 +A 4 +...+Ai 5 +Ai 6 +c*ONE) » 4, where ce {0,1,2,..., 8}, where each of said ApA 16 represents a vector, where ONE represents a packed vector; where » represents a bitwise logical right shift; and applying said at least one FIR filter to process the image signal, where a result of said at least one FIR filter is computed using at least an AVG operation.
10. The computer-readable carrier of claim 9, wherein said AVG operation is expressed as:
AVG{A,B) = [(aι+b j ) » 1 for /=1,...,8], where a; and b; represent data values, where
A represents a vector and where B represents a vector.
11. The computer-readable carrier of claim 9, wherein said ONE is expressed as:
ONE = [0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01], where 0x01 is a byte containing 1 in its least significant bit and Os elsewhere.
12. The computer-readable carrier of claim 9, wherein said result, R, of said at least one FIR filter is computed as:
R = AVG(B h B 2 ) ~ (B^B 2 ) | ((A 1 M 2 ) & (A 3 M 4 )) & ONE, where λ represents bitwise exclusive OR, where | represents bitwise OR, and & represents bitwise AND.
13. The computer-readable carrier of claim 9, wherein said result, R, of said at least one FIR filter is computed as:
R = AVG(B h B 2 ) + ( 5 1 λ #2) & ((A 1 M 2 ) I (A 3 M 4 )) & 0NE > where λ represents bitwise exclusive OR, where | represents bitwise OR, and & represents bitwise AND.
14. The computer-readable carrier of claim 9, wherein said result, R, of said at least one FIR filter is computed as:
R = AVG(B h B 2 ) + (Bι A B 2 ) & (A 1 M 2 ) & (A 3 M 4 ) & ONE, where λ represents bitwise exclusive OR, where | represents bitwise OR, and & represents bitwise AND. 15. The computer-readable carrier of claim 9, wherein said result, R, of said at least one FIR filter is computed as:
R = A VG(A i ,B 2 ) + (A γ λS 2 ) & ONE, where λ represents bitwise exclusive OR, where | represents bitwise OR, and & represents bitwise AND.
16. The computer-readable carrier of claim 9, wherein said result, R, of said at least one FIR filter is computed as:
R = SUBSATfU - E), where U=ADDSAT(D+2*ONE), where 2*ONE is a constant, where D =
AVG(A VG(AVG(A 1 , A 2 ), AVG(A 35 A 4 )), AVG(AVG(A 55 A 6 ), AVG(A 75 A 8 ))), where E =SUBSAT(U - L) & 7*ONE, where 7*ONE is a constant, where L = (A I +A 2 +A 3 +A 4 +A 5 +A 6 +A 7 +A 8 +c*ONE)»3, where c*ONE is a constant, and where SUBSAT(A,B) = [CUPia j -bø for /=1,...,8], where ADDSA T(A,B) = [CUP{afibø for
/=1,...,8], and where CLIP (x) clips x to range [0,255].
17. An apparatus for processing an image signal, comprising: means for providing at least one Finite Impulse Response (FIR) filter, wherein said at least one FIR filter comprises at least one of said functions:
(Ai+A 2 +c*ONE) » 1, where ce {-2,-1,0,1,2},
(A 1 +A 2 +A 3 +A 4 +c*ONE) » 2, where ce {0, 1,2}, (A 1 +A 2 +A 3 +A 4 +A 5 +A 6 +A 7 +A 8 +c*ONE) » 3, where ce {0,1,2,3,4}, (A ! +A 2 +A 3 +A 4 +...+Ai 5 +Ai 6 +c*ONE) » 4, where ce {0,1,2,..., 8}, where each of said A 1 -Ai 6 represents a vector, where ONE represents a packed vector; where » represents a bitwise logical right shift; and means for applying said at least one FIR filter to process the image signal, where a result of said at least one FIR filter is computed using at least an AVG operation.
18. The apparatus of claim 17, wherein said AVG operation is expressed as: AVG{A,B) = [(aι+bi) » 1 for /=1,...,8], where aj and b, represent data values, where
A represents a vector and where B represents a vector. 19. The apparatus of claim 17, wherein said ONE is expressed as:
ONE = [OxOl, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01], where 0x01 is a byte containing 1 in its least significant bit and Os elsewhere.
20. The apparatus of claim 17, wherein said result, R, of said at least one FIR filter is computed as at least one of:
R = AVG(B h B 2 ) ~ (B\ A B 2 ) I ((AfA 2 ) & (A 3 M 4 )) & ONE,
R = AVG(B h B 2 ) + (BfB 2 ) & ((A 1 M 2 ) | (A 3 M 4 )) & ONE,
R = AVG(B h B 2 ) + (BfB 2 ) & (A 1 M 2 ) & (A 3 M 4 ) & ONE,
R = AVG(A h B 2 ) + (Aj λ 5 2 ) & ONE, where λ represents bitwise exclusive OR, where | represents bitwise OR, and & represents bitwise AND. |
METHOD AND APPARATUS FOR IMPLEMENTING DIGITAL FILTERS
BACKGROUND OF THE INVENTION Field of the Invention
[0001] Embodiments of the present invention generally relate to implementations of Finite
Impulse Response (FIR) digital filters.
Description of the Related Art
[0002] A digital filter is a basic building block in any Digital Signal Processing (DSP) system. The frequency of the filter depends on the value of its coefficients, or taps. A Finite Impulse Response (FIR) digital filter is one whose impulse response is of finite duration. In general, when a digital filter is implemented in hardware, a designer may want to represent the coefficients and also the data with the smallest number of bits that sill gives acceptable resolution for the numbers. Excess bits will increase the size of the registers, buses, adders, multipliers and other hardware used to process the signal. The bigger sizes result in a chip with a larger die size, which translates into increased power consumption, a higher chip price, and so on. Thus, inefficient implementations of Finite Impulse Response (FIR) digital filters will significantly impact cost and performance of a digital signal processing (DSP) system.
[0003] Thus, there is a need in the art for a method and apparatus for providing efficient implementations of Finite Impulse Response (FIR) digital filters.
SUMMARY OF THE INVENTION
[0004] In one embodiment, the present invention discloses an apparatus and method for providing efficient implementations of Finite Impulse Response (FIR) digital filters. Specifically, a result from a FIR digital filter can be efficiently computed by using an AVG operation or instruction in conjunction with one or more other operations. The unique use of the AVG operation will allow FIR filters of various types, e.g., Types 1-4, to significantly reduce computational cycles.
BRIEF DESCRIPTION OF THE DRAWINGS
[0005] So that the manner in which the above recited features of the present invention can be understood in detail, a more particular description of the invention, briefly summarized above, may be had by reference to embodiments, some of which are illustrated in the appended drawings. It is to be noted, however, that the appended drawings illustrate only typical embodiments of this invention and are therefore not to be considered limiting of its scope, for the invention may admit to other equally effective embodiments. [0006] Figure 1 illustrates a subpixel p that is obtained as the average of four pixels ai , b j , c\, and d\ in accordance with one embodiment of the present invention;
[0007] Figure 2 illustrates eight average operations on eight columns of a frame in accordance with one embodiment of the present invention;
[0008] Figure 3 illustrates a SIMD execution model in accordance with one embodiment the present invention;
[0009] Figure 4 illustrates a block diagram of a conventional method for the packed operation;
[0010] Figure 5 illustrates a block diagram of an efficient method for a packed operation in accordance with one embodiment of the present invention; and
[0011] Figure 6 illustrates the present invention implemented using a general purpose computer.
[0012] To facilitate understanding, identical reference numerals have been used, wherever possible, to designate identical elements that are common to the figures.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
[0013] The present invention presents several new implementations of Finite Impulse Response (FIR) digital filters with positive coefficients, e.g., by using the Single Instruction Multiple Data (SIMD) architecture on Analog Devices (ADI) TigerSharc digital signal processor (DSP). The filters discussed herein can be used in pre-processing, postprocessing, motion compensation, and motion estimation for video compression, and a variety of filtering applications. For example, these implementations are useful in H.264 and MPEG-4 video compression standards and the like. The present invention demonstrates novel methods to speedup the computations of these filters when compared to traditional SMD methods.
[0014] The present invention presents a number of methods to efficiently implement a variety of Finite Impulse Response (FIR) digital filters for video/signal processing. These filters, also known as transversal or tapped delay filters, multiply a set of coefficients to pixel values of a video frame to generate a new pixel value. In one embodiment, the present invention considers positive coefficients only for the FTR filters. Let us consider 4 pixels al, bl, cl, dl, 101-104 in Figure 1, and a sub-pixel p 105 obtained as the average of these 4 pixels as:
p = (a λ + h ι + c λ +d x + 2) » 2 ,^
where » is bitwise logical right shift operator.
[0015] The example in Figure 1 and various other filtering functions are used in several aspects of digital video compression such as pre-processing, post-processing, motion estimation, and motion compensation. Since most video frames contain 255 levels of intensity or color values, the pixels a.\, b\, c\, d\ are represented in bytes (8-bits).
[0016] In practical implementations of video compression technologies, such as MPEG, the present invention needs to perform numerous operations of the type (1) over the entire frame. For example, Ά\, bγ, c\, dj can be four pixels on four consecutive rows along the same column of a video frame (see Figure 2 below). The present invention may need to repeat (1) for each column of the frame. If the frame has 240 columns, then the present invention needs 240 such computations for each set of 4 rows of the frame.
[0017] In order to gain computational efficiency, the present invention uses the parallel computation capability of many processors available today. This capability, also known as Single Instruction Multiple Data (SEVID) architecture, is available in many processors including Analog Devices' TigerSharc ADSP-TS201S DSP. In SDVID architecture, there are N identical processors, which work under the control of a single instruction stream issued by a central control unit. There are N data streams, one per processor. The processors operate synchronously: at each step, all processors execute the same instruction on a different data element. This architecture allows the present invention to achieve N computations such as (1) on N separate columns simultaneously in one instruction. Thus, if N=8, we need 240/8=40 instructions instead of 240 instructions for all 240 columns of data
for each 4 consecutive rows of pixel data. This achieves a computational speedup by a factor of 8.
[0018] Here instruction refers to a single SIMD operation by the processor such as add, subtract, bitwise AND, bitwise OR, bitwise logical right shift, bitwise logical left shift, and bitwise exclusive OR. Some processors may combine multiple such operations into one instruction. For the sake of simplicity, the present invention will consider each SIMD operation as an instruction.
[0019] The present invention uses the following notations and functions in the discussions:
Table 1.
[0020] The SEVID architecture is available in several processors. Examples include Intel Multi-Media Extensions (MMX)™ and Streaming SEVID Extension (SSE)™, NEC VR5432, Equator MAP-CA™, Philips TM- 1300, Texas Instruments C64x, Analog Devices Blackfin and TigerSharc DSPs. The present invention demonstrated various algorithms with assembly instructions available in the ADI TigerSharc DSP.
[0021] Figure 2 demonstrates a SEVID operation on two sets of data. Let A=[a^,...,ag] be a vector of 8 data values, each of which is an unsigned byte integer, i.e., a j e [0,255]. Let
B=[b J , ... ,bg] be another vector of unsigned byte integers in the range [0,255] . The final result C=[C j , ...,cg] is achieved by simultaneously operating on all 8 values of aj and bj as q = aj OP bj, for i=l,...,8, where OP is the desired operation. In this example, A, B and C are 64-bit vectors in which all 8 values of a j , b j , and CJ are packed as contiguous bytes as shown in Figure 3, i.e., N=8. Such operations are also known as packed operations, since 8 values of data are packed in a single vector A, B or C.
[0022] One of the packed operations/instructions that the present invention uses frequently in this study is the A VG instruction that does the following computation:
A VG(A,B) = [(ai+b-) » 1 for i= 1 , ... ,8] . (2)
[0023] This operation takes eight 8-bit values of aj, bj, and stores the intermediate sum (aj+bj) in 9 bits before doing bitwise logical right shift operation to get the final result. It is available in many processors, including the ones mentioned above, and uses only one instruction.
[0024] In TigerSharc, this instruction is realized by the (Rm+/-Rn)/2(U) assembly operation. It has a throughput of 1 clock cycle. T his throughput is same for packed addition, subtraction, bitwise AND, bitwise OR, bitwise exclusive OR, bitwise right shift, and bitwise left shift operations.
[0025] Two other SEVID instructions that the present invention uses frequently, are ADDSAT, and SUBSAT, which denote saturated add and subtract respectively.
ADDSAT(A,B)
[0026] In TigerSharc, these instructions are realized by (Rm+Rn)(U), and (Rm-Rn)(U) respectively. They both have throughput of 1 clock cycle.
[0027] The present invention considers a simple computation (a j +bj+l)»l to demonstrate the application of SMD architecture and the benefit of the present methods over traditional SIMD methods. Similar to Figure 3, let us consider a j , bj as unsigned byte
integers. The present invention also considers N=8, i.e., the present invention simultaneously performs the operation (a j +b j +l)»l on 8 values of a j and bj for i=l,...,8.
The present invention packs all 8 values of a j (usually contiguous pixels) in a 64-bit vector A, and 8 values of b j in a 64-bit vector B. Since aj+b j can exceed 8 bits, the present invention needs to first unpack the 8-bit (byte) values of a j , b j into 16-bits as shown in
Figure 4 below, then add the vectors A and B, followed by bitwise logical right shift by 1, followed by packing back into 8-bit values of CJ. Note that in most processors, data can be packed into a 64-bit vector as 8- (byte), 16- (word), 32- (dword), or 64- (qword) bit values only. Figure 4 shows the conventional method of doing the packed operation Cj=(a j +bj+l)»l for i=l,...,8. It is clear from Fig. 4, that given sufficient memory, it will need 11 instructions to achieve the result C j =(aj+bj+l)»l for all 8 values of a j and bj. Each instruction in Figure 4 is represented by an ellipse.
[0028] The present invention now demonstrates the same packed operation (cρ(β ( +.7 j +l)»l) in much fewer instructions by using the AVG instruction and logical operations on 64-bit vectors A and B. The efficient solution is:
C = A VG(A, B) + (A A B) & ONE, (3) where ONE is a 64-bit vector defined in (4). The flowchart for the implementation of (3) in SIMD architecture is given in Figure 5.
[0029] Figure 5 illustrates a block diagram of an efficient method for packed operation C=(A+B+ONE)» 1. Specifically, assuming sufficient memory, the present invention needs only 4 instructions instead of previous 11 instructions to achieve the packed operation C=(A+B+ONE)»l. This is an approximate speedup of 11/4 or 175%.
[0030] As shown above, the present invention can achieve the same computational result with fewer instructions by appropriately using the AVG instruction in combination with simple logical operations. The present invention discusses several FIR filtering operations that can be modified to obtain the result in fewer instructions when compared to conventional SIMD implementations.
[0031 ] Without loss of generality, let A \ , k^, ■ ■ ■ A \ 6 be 16 vectors, each of which contain 8 packed data elements. For example, λ5 contains 8 data elements A 5 = [a^ n, ..., ^(5,8)1-
Each data element α(i ^, ..., «(16,/) for i=l,...8, is within the range [0,255]. We define packed 64-bit vectors ONE and ONE 4 as follows:
ONE = [0x01, OxOl, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01], (4)
ONE 4 = [0x0001, 0x0001, OxOOOl, 0x0001], (5) where OxOl is a byte containing 1 in its least significant bit and O's elsewhere. The packed 64- bit vectors ONE contains 8 packed bytes, each containing 0x01. On the other hand, the packed 64-bit vectors ONE 4 contains 4 packed words (16 bits), each containing 0x0001.
[0032] The FIR functions that are considered here are:
Type 1: (Aι+A 2 +c*ONE) » 1, where ce {-2,-1,0,1,2}, (6)
Type 2: (A 1 +A 2 +A 3 +A 4 +c*C)νE) » 2, where ce { 0, 1 ,2 } , (7)
Type 3: (A 1 +A 2 +A 3 +A 4 +A 5 +A 6 +A 7 +A 8 +c*ONE) » 3, where ce {0,l,2,3,4},(8)
Type 4: (A 1 +A 2 +A 3 +A 4 +...+Ai 3 +Ai 4 +Ai 5 +A 16 +c*ONE) » 4,
where ce {0,1,2,..., 8}, (9)
[0033] All 4 types of FIR filters are useful for video compression applications such as H.264. It should be noted that although the present invention is described within the context of these four filter functions, other filter functions may also exploit the method of the present invention. There are numerous FIR filters that can be constructed from these 4 basic types. For example, the filter (2A ι+A 2 +A^+2*ONE) » 2 is a Type 2 filter with
ApA 4 . Similarly, the filter (A1+2A2+2A3+2A4+A5 +4*ONE)»3 is a Type 3 filter with ^2 = ^6' ^3 = ^7' an d A 4 =Ag. Further note that in all following discussions, vectors ONE and CWE 4 are stored in advance for use in the present methods. Moreover, the vector c*ONE for any integer c≠O is also stored in advance.
[0034] There are 5 variations of the Type 1 FIR filters (A\+A 2 +c*ONE), where ce {-2,-
1,0,1,2}, based on the 5 choices of constant c. The present invention states the SMD implementation for each of these filters:
(A ι+A 2 -2*ONE) » 1 = SUBSAT(A VG(A 1 A 2 ) ~ ONE), (10)
(Aι+A 2 -ONE) » 1 = ADDSAT(SUBSAT(AVG(A I ,A 2 ) - ONE) + (A\ A A 2 ) & ONE)),
(11)
(Aχ+A 2 +ONE) » 1 = ADDSAT (AVG(AγA 2 ) + (A\ A A 2 ) & ONE), (12)
(A 1+ A 2 ) » I = AVG(A 1 A 2 ), (13)
(Aχ+A 2 +2*ONE) » 1 = ADDSAT(AVG(AIA 2 ) + 0NE )- ( 14 >
[0035] The present invention shows the conventional method for only one function (Aι+A 2 -ONE)»l. The remaining functions can be obtained as extensions of this filter. T he steps for the conventional method are:
1. (2 Instructions) A [ L and A 2 L = Unpack Low 4 Bytes of A \ and A 2 respectively.
2. (2 Instructions) A 1L and A 2L = Unpack High 4 Bytes of Al and A2 respectively.
3. (3 Instructions) Add and Shift lower 4 words of Al and A2 to obtain lower 4 words of RL as: RL = (A IL + A 2L - ONE4) » 1.
4. (3 Instructions) Add and Shift higher 4 words of Al and A2 to obtain higher 4 words of RH as: RH = (A m + A 2H - ONE4) » 2.
5. (1 Instruction) Pack RH and RL into final vector R.
[0036] The conventional SEVID method requires 11 instructions. The steps of the efficient method are:
(1 Instruction) Rl = AVG(Ai ,A 2 ).
(1 Instruction) R2 = (Ai λ A 2 ).
(1 Instruction) R3 = R2 & ONE.
(1 Instruction) R4 = SUBSAT(Rl - ONE).
(1 Instruction) R5 = ADDSAT(R4 + R3).
[0037] The efficient method requires a total of 5 instructions with a speedup of 120%.
Table 2.
[0038] There are 3 variations of Type 2 filters (7) based on the 3 choices of constant c. The present invention defines the following 64-bit packed vectors, each containing 8 data elements of one byte each:
#! = AVG(AiA 2 ), B 2 = AVG(A 3 A 4 ). ( 16)
Type 2 - Filter 1 : R = (Aj + A 2 + A3 + A4 + 2*ONE) » 2
[0039] This filter can be implemented in SDVlD architecture (assuming sufficient memory) by conventional method in the following steps:
1. (4 Instructions) λ/L = Unpack Low 4 Bytes of A[, for /=1,2,3,4.
2. (4 Instructions) A iH = Unpack High 4 Bytes of Ai, for i=l,2,3,4.
3. (5 Instructions) Add and Shift lower 4 words of Al,...,A4 to obtain lower 4 words of RL as: RL = (Ai L + A 2L + A 3L + A 4L + 2*ONE4) » 2.
4. (5 Instructions) Add and Shift higher 4 words of A1,...,A4 to obtain higher 4 words of RH as: RH = (A 1H + A 2H + A 3H + A 4n + 2*ONE4) » 2.
5. (1 Instruction) Pack RH and RL into final vector R.
[0040] Thus, it requires 19 instructions to perform this filter by conventional SIMD methods.
[0041] In order to implement this filter efficiently, the present invention simplifies it as follows:
R = (((Aι+A 2 )»l) + ((A 3 +A4)»l)+ONE+E) » 1 = (Bχ+B 2 +ONE+E) » 1, (17)
where E is the correction term that is necessary when both (A\+A 2 ) and (A3+A4) are odd integers. We have:
E=ODD(A^A 2 ) & ODD(A 3 +A 4 ) = (A 1 M 2 ) & (A3M4) & ONE. (18)
[0042] From (18) and (14), we have:
{ AVG(B, , B 2 ) + (B, A B 2 ) & ONE when E = O
R = \ l 2 l 2 . (19)
[ AVG(B U B 2 ) + ONE when E = I
[0043] The present invention simplifies (19) as:
R = AVG(B h B 2 ) - ((Bι A B 2 ) | E) & ONE, (20) which is same as:
R = A VG(B i ,B 2 ) - (B \ A B 2 ) | ((A \ λ A 2 ) & (A3M4)) & ONE. (21 )
[0044] Thus, the present solution in (21) requires 10 instructions. The present invention has an approximate 19:10 speedup (or 90%) by using (21).
Type 2 - Filter 2: R = (A j + A 2 + A 3 + A4 + ONE) » 2
[0045] As seen above, this filter can be implemented by conventional SIMD methods in 19 instructions. For efficient implementation, the present invention simplifies it as follows:
R = (((A 1 +A 2 )»1)+((A3+A4+CW£)»1)+£ 1 )»1 = (Bχ+B 2 +E 2 +Eι)) » 1. (22)
[0046] Here error
Eγ = ODD(Aι+A 2 ) & ODD(A 3 +A4+ONE) = ODD(Aχ+A 2 ) & EVEN(A 3 +A 4 ) = (A ι A A 2 ) & ~(A 3 A A 4 ) & ONE = (Aχ A A 2 ) & -E 2 . (23)
[0047] Note the truth table for E\, E 2 , and Ej=E 2 +E\ below:
E 2 Eγ E j =E 2 +E\
0 0 0
0 1 1
1 0 1
1 1 N/A
[0048] Note that E 2 =I, E\~\ is not a possible outcome due to (23), and Ej= E\ \ E 2 . From (22), (12), and the table above, the present invention obtains:
[AVG(B, ,B 2 ) + (B, λ B 2 ) Sc ONE when E τ = 1
R = \ l 2 λ 2 l (24)
{ AVG(B X ,B 2 ) when E r = 0
The present invention simplifies (24) as:
R = AVG(B h B 2 ) + ((Bi A B 2 ) & (Eγ | ^2» & ONE. (25)
[0049] Note that:
E 1 I E 2 = ((A ! λ λ 2 ) & -E 2 ) \ E 2 = (A ^A 2 ) \ E 2 = ((A t M 2 ) | (A 3 M 4 )) & ONE. (26)
[0050] Combining (25) and (26), the solution is:
R = A VG(B i ,B 2 ) + (B γ A B 2 ) & ((A i M 2 ) | (A 3 M 4 )) & ONE. (27)
[0051] The solution in (26) requires 10 instructions, an approximate 19: 10 speedup or 90%.
Type 2 - Filter 3: R = (Ai + A 2 + A 3 + A 4 ) » 2
[0052] This filter can be implemented by conventional SDVID methods in 17 instructions. For efficient implementation, the present invention simplifies it as follows:
R = (((A!+A 2 )»l) + ((A 3 +A 4 )»l)+£)»1. (28)
[0053] Here E is the correction term as:
E = ODD(Aι+A 2 ) & ODD(A 3 +A 4 ) = (A^A 2 ) & (A 3 M 4 ) & ONE. (29)
[0054] The solution is:
[AVG(B 1 , B 2 ) + (B x ^ B 2 ) SL ONE when £ = l
R = \ * 2 l 2 . (30)
[ AVG(B^B 2 ) when E = O
[0055] The present invention simplify (30) as:
R = AVG(B h B 2 ) + (B{ A B 2 ) & (A\ A A 2 ) & (A3M4) & ONE. (31)
[0056] The solution in (30) requires 10 instructions. Thus, the present invention has an approximate 17:10 (or 70%) speedup by using (30).
Type 2 - Special Filter 1: R = (2A^ + A3 + A4 + 2*ONE) » 2
[0057] This filter is same as Filter 1 with A\=A 2 , i.e., B\= A\. The steps of the conventional method are:
1. (3 Instructions) AJL = Unpack Low 4 Bytes of A/, for /=1,3,4.
2. (3 Instructions) AiH = Unpack High 4 Bytes of Ai, for i= 1 ,3,4.
3. (5 Instructions) Add and Shift lower 4 words of A1,A3,A4 to obtain lower 4 words of RL as: RL = (2A 1L + A 3L + A 4L + 2*ONE4) » 2.
4. (5 Instructions) Add and Shift higher 4 words of A1,A3,A4 to obtain higher 4 words of RH as: RH = (2A, H + A 3H + A 4H + 2*ONE4) » 2.
5. (1 Instruction) Pack RH and RL into final vector R.
[0058] The conventional SEVlD method requires 17 instructions. It is used extensively in JVT video coding scheme. In contrast, the present invention can simplify (21) as:
R = A VG(A i ,B 2 ) + ( A 1 Aβ 2) & ONE. ( 32 )
This solution requires 5 instructions, a computational gain of 240%.
[0059] Table 3 below summarizes the instructions required to compute each filter (given sufficient memory) by the efficient and conventional SDVID methods.
Table 3.
[0060] There are 5 different Type 3 FIR filters depending on the 5 choices of c in (8). The present invention defines the following packed 64-bit vectors, each containing 8 data elements of one byte each:
B 1 = AVG(A 1 A 2 ), B 2 = AVG(A 3 A 4 ), B 3 = AVG(A 5 A 6 ), B 4 = AVG(A 1 A^), C 1 = A VG(Bχ,B 2 \ C 2 = AVG(B 3 ,B 4 ). (33)
Type 3 FIR Filter: R = (A 1 + A 2 + A 3 + A 4 + A5 + Ag + A 7 + Ag + c*ONE) » 3.
[0061] The Type 3 FIR filters can be implemented in SIMD architecture (assuming sufficient memory) by conventional method in the following steps:
1. (8 Instructions) λ/L = Unpack Low 4 Bytes of A/, for / = 1,...,8.
2. (8 Instructions) A; H = Unpack High 4 Bytes of Ai, for i = 1,...,8.
3. (8 or 9 Instructions) Add and Shift lower 4 words of Al,...,A8 to obtain lower 4 words of RL as: RL = (A ]L + A 2 L + A 3L + A 4L + A 5L + A 6 L + A 7L + A 8L + c*ONE4) » 3. It will have 8 instructions for c=0, and 9 instructions otherwise.
4. (8 or 9 Instructions) Add and Shift higher 4 words of Ai, ...,A 8 to obtain higher 4 words of RH as: RH = (Am + A 2 H + A 3H + A 4 H + A 5H + A 6 H + A 7H + A 8H + c*ONE4) » 3.
5. (1 Instruction) Pack RH and RL into final vector R.
Thus it will require 33-35 instructions to compute this filter by conventional SIMD methods.
[0062] The present invention first computes D as:
D = AVG(C h C 2 ), (34)
where C\ and C 2 are given in (33). The present invention next needs to know how far D is from the correct solution R. This is summarized in the following lemma.
[0063] Lemma 1: R-2*ONE < D < R+2*ONE.
Proof: For any two packed vectors X and Y, we have:
2 2 2 2
It follows that c λ +c 2 ONE C 1 + C 2 ONE
— — r" 5
2 2 2 2 which is the same as (from (34)):
AVG(B 1 ^ 2 ) + AVG(B 31- S 4 ) ONE < AVG(^a 2 ) + AVG(g 3 ,# 4 ) | ONE
2 2 2 2
[0064] By further substituting for AVG(B^B 2 ) and AVG(BiJB^), we see that
(B l +B 2 )/2-ONE/2 + (B 3 +B 4 )/2-ONE/2 ONE
2 2
<D<
(B 1 +B 2 )/2 + ONE/2 + (B 3 +B 4 )/2 + ONE/2 ONE
which simplifies to
B l +B 2 +B 3 + B 4 -4*ONE^ B l +B 2 +B 3 +B 4 +4*ONE 4 " 4
[0065] Substituting for the B \ , ... , £4 and simplifying,
A 1 + A 2 + A 3 + ... + A 6 + A 7 + A 8 + 12 * ONE 8 "
[0066] The upper-bound is at most 12/S* 5 more than D before truncation to an integer. We get D-R ≤ (12-c)*ONE/8 ≤ 2*ONE. Likewise, we see that R-D ≤ (12+c)*ONE/S ≤ 2*0NE. The final result of the lemma follows from these two inequalities.
[0067] Following Lemma 1, after D is computed, we do a saturated add by 2*ONE as U=ADDSAT(D+2*ONE). Thus, after 8 instructions, we have
R ≤ U=ADDSAT(D+2*ONE) ≤ R+4*ONE. (35)
[0068] The next step is to determine the correct least significant bits of U. This is done by computing L as:
L = fA/ + Ki + A 3 + A4 + A 5 + A 6 + Aγ + A 8 + c*ONEj » 3. (36)
[0069] The value c*ONE is a stored constant similar to ONE, so there is no need to perform the multiply. In (36), all adds and shifts are on packed 8-bit data, i.e., if the result of each packed add exceeds 8-bits, the result is truncated to 8-bits. Thus, in total, (36) has eight (8) 8-bit adds and one (1) 8-bit shift to compute L, which holds 5 correct least significant bits of R for each packed byte.
[0070] The last step uses the least significant bits of L to correct the least significant bit errors in U (see (35)). Since we know that U is at most 4 more than R, we only need to figure out the error E of U so that it agrees with L in the three least significant bits. This is accomplished by:
E = SUBSATfU - L) & 7*ONE. (37)
[0071] As before, 1*ONE is a stored constant similar to ONE. In 2 instructions (subtraction, bitwise and), the error term E can be determined. The final step is to subtract this error E from U to get the final result. This is 1 additional instruction:
R = SUBSATfU - Ej. (38)
[0072] In total this method requires 20 instructions, and 19 instructions when c = 0 since an addition in (36) can be saved. The steps for the new efficient method are:
1. (7 Instructions) Compute D = AVG(AVG(AVG(A 11 A 2 ), AVG(A 35 A 4 )),
AVG(AVG(A 51 A 6 ), AVG(A 7 A 8 ))).
2. (1 Instruction) Compute U=ADDSAT(D+2*ONE), where 2*ONE is a stored constant.
3. (8 or 9 Instructions) Compute L =
(Ai+A 2 +A 3 +A 4 +A 5 +A 6 +A 7 +A 8 +c*ONE)»3. This is a truncated packed 8-bit addition. The present invention needs 8 instructions for c = 0, and 9 instructions otherwise. Here c*ONE is a stored constant.
4. (2 Instruction) Compute error E =SUBSAT(U - L) & 7*ONE, where 7*ONE is a stored constant.
5. ( 1 Instruction) Subtract this error E from U to obtain R = SUBSAT(U - E).
[0073] The new algorithm requires 19-20 instructions compared to 33-35 instructions by the conventional method.
Type 3 - Special Filter 1: R = (A j + A2 + 2A 3 + 2A5 + 2A 7 + 4*ONE) » 3. [0074] The steps of the conventional method are:
1. (5 Instructions) A/L = Unpack Low 4 Bytes of Aj, for /=1,2,3,5,7.
2. (5 Instructions) A iH = Unpack High 4 Bytes of Ai, for i=l,2,3,5,7.
3. (7 Instructions) Add and Shift lower 4 words of Ai,...,A 7 to obtain lower 4 words of RL as: RL = (Ai L + A 2L + ((A 3L + A 5L + A 7L )«1) + 4*ONE4) » 3.
4. (7 Instructions) Add and Shift higher 4 words of A1,...,A7 to obtain higher 4 words of RH as: RH = (A 1H + A 2H + ((A 311 + A 5H + A 7H )«1) + 4*ONE4) » 3.
5. (1 Instruction) Pack RH and RL into final vector R.
[0075] The conventional SDVID method requires 25 instructions. For the present new method, there is no need to compute AVG(Ai, A3), AVG(A^As), and AVG(Aη,Aη). This saves 3 instructions. Furthermore, the computation of L can be shortened by first doing (A3+A ζ +A j )«l and then adding on the remaining parts. Hence there are 5 adds and 2 shift instructions. The net savings on L is 2 instructions, and the total net savings is 5 instructions. The steps for the new efficient method are:
1. (4 Instructions) Compute D = AVG(AVG(AVG(A ^ 2 ). Aj), AVG(A 5 , A 7 )).
2. (1 Instruction) Compute U = ADDS AT(D+2*ONE).
3. (7 Instructions) Compute L = (Ai+A 2 +((A 3 +A 5 +A 7 )«l)+4*ONE)»3. This is truncated packed 8-bit addition.
4. (2 Instruction) Compute error E = SUBSAT(U - L) & 7*ONE.
5. (1 Instruction) Subtract this error E from U to obtain R = SUBSAT(U - E).
[0076] The new method requires 15 instructions compared to 25 instructions by the conventional method.
Type 3 - Special Filter 2: R = (A\ + A2 + A 3 + 3A4 + 2A 7 + 4*ONE) » 3. [0077] The steps of the conventional method are:
1. (5 instructions) AJL = Unpack Low 4 Bytes of A/, for /=1,2,3,4,7.
2. (5 Instructions) AiH = Unpack High 4 Bytes of Ai, for i= 1 ,2,3,4,7.
3. (8 Instructions) Add and Shift lower 4 words of Al,...,A7 to obtain lower 4 words of RL as: L = (A 1L + A 2L + A 3L + 3A 4L + 2A 7L + 4*ONE4) » 3.
4. (8 Instructions) Add and Shift higher 4 words of A1,...,A7 to obtain higher 4 words of RH as: H = (A, H + A 2H + A 3H + 3A 4H + 2A 7H + 4*ONE4) » 3.
5. (1 Instruction) Pack /?JJ and /?L into final vector R.
[0078] The conventional method requires 27 instructions. For the present new method, there is no need to compute AVG(A^^), and AVG(AjAj)- This saves 2 instructions. Furthermore, the computation of L can be shortened by first doing (A3+A5+A 7 )«l and then adding on the remaining parts. Hence there are 6 adds and 2 shift instructions. The net savings on L is 1 instruction, and the total net savings is 3 instructions. The steps for the new efficient method are:
1. (5 Instructions) Compute D = A VG(A VG(A VG(A 1 ,A 2 ). A VG(Ao 1 Aø), AVG(A 4 , A 7 )).
2. ( 1 Instruction) Compute U = ADDSAT(D+2*ONE).
3. (8 Instructions) Compute L = (A 1 +A 2 +A 3 +A 4 +((A 4 +A 7 )«1)+4*ONE)»3. This is truncated packed 8-bit addition.
4. (2 Instruction) Compute error E = SUBSAT(U - L) & 7*ONE.
5. (1 Instruction) Subtract this error E from U to obtain R = SUBSAT(U - E) .
[0079] The new method requires 17 instructions compared to 27 instructions by the conventional method.
Type 3 - Special Filter 3: R = (Ai + A2 + A3 + 2A4 + Ag + A7+ Ag + 4*ONE) » 3. [0080] The steps of the conventional method are:
1. (7 Instructions) A^ = Unpack Low 4 Bytes of A [ , for /=1,2,3,4,6,7,8.
2. (7 Instructions) A iH = Unpack High 4 Bytes of Ai, for i=l,2,3,4,6,7,8.
3. (9 Instructions) Add and Shift lower 4 words of Ai,...,A 4 to obtain lower 4 words of RL as: RL = (A 1L + A 2L + A 3L + 2A 4L + A 6L + A 7L + A 8L + 4*ONE4) » 3.
4. (9 Instructions) Add and Shift higher 4 words of Ai,...,A 7 to obtain higher 4 words of RH as: RH = (A !H + A 2H + A 3H + 2A 4H + A 6H + A 7H + A 8H + 4*ONE4) » 3.
5. (1 Instruction) Pack RH and RL into final vector R.
[0081] The conventional method requires 33 instructions. For the new method, there is no need to compute AVG(A 4 A 4 )- This saves 1 instruction. The steps for the new efficient method are:
1. (6 Instructions) Compute D = AVG(A VG(A VG(A \ ,A 2 ), A 4 )AVG(AVG(A 3 A 6 )AVG(A 1 AS))).
2. (1 Instruction) Compute U = ADDSAT(D+2*ONE).
3. (9 Instructions) Compute L = (Ai+A 2 +A 3 +(A 4 «1)+A 6 +A 7 +A 8 +4*ONE)»3. This is truncated packed 8-bit addition.
4. (2 Instruction) Compute error E = SUBSAT(U - L) & 7*ONE.
5. (1 Instruction) Subtract this error E from U to obtain R = SUBSAT(U - E).
[0082] The present new method requires 19 instructions compared to 33 by the conventional method.
[0083] Table 4 below summarizes the instructions required to compute each Filter (given sufficient memory) by the efficient and conventional SIMD methods.
Table 4.
[0084] The present invention also defines the following packed 64-bit vectors, each containing 8 data elements of one byte each:
B 1 = AVG(A i A 2 ), B 2 = AVG(A 3 A 4 ), B 3 = AVG(A 5 Ae), B A = AVG(A 1 As), B 5 = AVG(A 9 AlO), B 6 = AVG(A n AnI B 7 = AVG(A 13 Au), #8 = AVG(A 15 ^ 16 ), C 1 = AVG(B h B 2 ), C 2 = AVG(B 3 ,B 4 ), C 3 = AVG(B 5 ,B 6 ), C 4 = AVG(B 1 , Bg), D 1 = AVG(C h C 2 ), D 2 = AVG(C 3 ,C 4 ), D = AVG(D h D 2 ) . (39)
Type 4 FIR Filter: R = (A 1 + A 2 + A3 + A4 +...+ A 13 + A^ + A 15 + A 16 + c*OνE) » 4.
[0085] The Type 4 FIR filters can be implemented in SEVID architecture (assuming sufficient memory) by conventional method in the following steps:
1. (16 Instructions) A/L = Unpack Low 4 Bytes of A/, for i = 1 , ... , 16.
2. (16 Instructions) A iH = Unpack High 4 Bytes of Ai, for i = 1,..., 16.
3. (16 or 17 Instructions) Add and Shift Iower 4 words of Ai,...,A 16 to obtain lower 4 words of RL: RL = (A !L + A 2L + • • • + A 15L + A 16L + c*ONE4) » 4. 16 instructions needed for c=0, and 17 instructions otherwise.
4. (16 or 17 Instructions)Add and Shift higher 4 words of Ai, ...,Ai 6 to obtain higher 4 words of RH: RH = (Ai H + A 2H + ... + Ai 5H + A, 6H + c*ONE4) » 4. 16 instructions needed for c=0, and 17 instructions otherwise.
5. (1 Instruction) Pack RH and RL into final vector R.
[0086] Thus, it would require 65-67 instructions to compute this filter by conventional SMD methods.
[0087] In contrast, the present invention first compute D as AVG(D^DQ) (see (39)), which requires 15 AVG instructions. Here D is an approximate solution for R, where:
R = (A j + A-2 + A j + A4 + ... + A / j + A/4 + A/5 + A/ β + c*ONEj » 4. where ce {0,1,2,...,8). The following result is analogous to Lemma 1:
[0088] Lemma.2; R-3*ONE < D < R+2*ONE.
Proof: We know that
P 1 +D 2 ONE < D x +D 2 ONE
2 2 " " 2 2
[0089] Following the analyses in Lemma 1, we get
A 1 +A 2 +...+ A 7 +A 8 -12*CWE ^ A 1 +A 2 +... + A 7 +A 8 + ■ 1:2* ONE 8 1- 8 and
A 9 +A 10 +... + A 15 +A 16 -12*ONE A 9 +A 10 + ... + A 15 +A 16 + 12* ONE
8 8
[0090] Substituting these ranges, we see that
A 1 +A 2 +... + A 15 +A 16 -32*CWE ^ A 1 + A 2 +- + A 15 +A 16 +32*6WE
16 " " 16
[0091] Thus, D- R≤ (32-c)*ONE/l6 = 2*ONE andR-D≤ (32+c) *ONE /16) ≤ 3*0NE.
[0092] The remaining steps are similar to the Type 3 filters, and all steps are outlined below:
1. (15 Instructions) Compute D = AVG(Dι,D2) - see (39).
2. (1 Instruction) Compute U = ADDSAT(D+3*Oνε) , where 3*ONE is a stored constant.
3. (16 or 17 Instructions) Compute L =
(A]+A 2 +A 3 +...+A 14 +Ai 5 +Ai 6 +c*ONE)»4. This is a truncated packed 8-bit add. We need 16 instructions for c = 0, and 17 instructions otherwise. Here c*ONE is a stored constant.
4. (2 Instruction) Compute error E = SUBSAT(U- L) & 7*ONE, where 7*ONE is a stored constant.
5. (1 Instruction) Subtract this error E from U to obtain R = SUBSAT(U - E) .
[0093] The present new method requires 35-36 instructions compared to 65-67 instructions by the conventional method.
Type 4 - Special Filter 1: R = (Aj + 4A 2 + 6A3 + 4A4 + A5 + 8*ONE) » 4. [0094] The conventional method can be implemented in SIMD architecture as follows:
1. (5 Instructions) A^ = Unpack Low 4 Bytes of A[, for / = 1 , ... ,5.
2. (5 Instructions) A lH = Unpack High 4 Bytes of Ai, for i = 1,...,5.
3. (9 Instructions) Add and Shift lower 4 words of Ai,...,A 5 to obtain lower 4 words of RL: RL = (A 1L + 4A 2L + 6A 3L + 4A 4L + A 5L + 8*ONE4) » 4.
4. (9 Instructions) Add and Shift higher 4 words of Ai,..., A 5 to obtain higher 4 words of RH: RH = (A 1H + 4A 2H + 6A 3H + 4A 4 H + A 5H + 8*ONE4) » 4.
5. (1 Instruction) Pack RH and RL into final vector R.
[0095] The conventional method requires 29 instructions. For the present efficient method, the present invention has the following simplifications:
B 1 =AVG(A 1 A 5 ), B 2 =A 2 , B 3 = A 2 , B 4 = A 3 ,
B 5 = A 3 , B 6 = A 3 , B 7 =A 4 , Bz =A 4 , C 1 = A 2 , C 2 = A 3 , C 3 = A 4 , C 4 = AVG(BiA 3 ),
D 1 = AVG(A 2 A 3 ), D 2 =AVG(A 4^ C 4 ). Thus,
D =AVG(D h D 2 ) = AVG(AVG(A 2 A 3 )AVG(A 4 AVG(AVG(A IA 5 )A 3 ))). (40)
[0096] The present efficient method is:
1. (5 Instructions) Compute D as (40).
2. ( 1 Instruction) Compute U = ADDSAT(D+3*ONE).
3. (9 Instructions) Compute L =
(A 1 +((A 2 +A 3 +A 4 )«2)+(A 3 «1)+A 5 +8*ONE)»4. This is a truncated packed 8-bit addition.
4. (2 Instruction) Compute error E = SUBSAT(U - L) & 7*ONE.
5. (1 Instruction) Subtract this error E from U to obtain R = SUBSAT(U - E).
[0097] The new method requires 18 instructions as compared to 29 instructions for the conventional method.
Type 4 - Special Filter 2: R = (Ai+A2+2A3+2A4+4A5+2Ag+2A7+A 8 +A9+8*ONE)»4. [0098] The conventional method can be implemented in SIMD architecture as follows:
1. (9 Instructions) AJL = Unpack Low 4 Bytes of A/, for / = 1,...,9.
2. (9 Instructions) A iH = Unpack High 4 Bytes of Ai, for i = 1,...,9.
3. (12 Instructions) Add and Shift lower 4 words of A 1 , ... ,A 9 to obtain lower 4 words of RL: RL = (A 1L +A 2L +((A 3L +A 4L +A 6L +A 7L )«1)+(A 5L «2) +A 8L +A 9L +8*ONE) »4.
4. (12 Instructions)Add and Shift higher 4 words of Ai, ...,A 9 to obtain higher 4 words of RH: RH = (A 1H +A 2H + ((A 3H +A4 H +A6 H +A7 H )«1) + (A 5H «2) + As H +A 9H +8*ONE) »4.
5. (1 Instruction) Pack RH and RL into final vector R.
[0099] The conventional method requires 43 instructions. For the present efficient method, the present invention has the following simplifications:
Bi = AVG(Ai ,A 2 ), B 2 = A 3 , B 3 = A 4 , B 4 = A 5 , B 5 = A 5 , B 6 = A 6 , B 1 = A 1 , B 8 = AVG(A 8 A 9 ),
C 1 = AVG(B 1 A 3 ), C 2 = AVG(A 4 A 6 ) , C 3 = A 5 , C 4 = AVG(A 1 , Bg),
Dγ = AVG(C h C 2 ), D 2 = AVG(C 3 ,C 4 ), and D = AVG(D h D 2 ). (41)
[00100] The efficient algorithm is:
1. (8 Instructions) Compute from (41) as: D = AVG(AVG(AVG(AVG(A 1 ,A 2 ),A 3 ),AVG(A 4 ,A 6 )),AVG(A 5 ,AVG(A 7 ,AVG(A 8 ,A 9 )))).
2. ( 1 Instruction) Compute U = ADDSAT(D+3*ONE).
3. (12 Instructions) Compute L= (Ai +A 2 +((A 3 +A 4 +A 6 + A 7 )« 1 ) + (A 5 «2)+A 8 +A 9 +8*ONE) »4. This is a truncated packed 8-bit addition.
4. (2 Instruction) Compute error E = SUBSAT(U - L) & 7*ONE.
5. (1 Instruction) Subtract this error E from U to obtain R = SUBSAT(U - E).
[00101] The present new method requires 24 instructions as compared to 43 instructions for the conventional method.
Type 4 - Special Filter 3: R = (Ai+2A2+2A 3 +2A 4 +2A5+2A6+2A7+2A 8 +A9+8*ONE)»4. [00102] The conventional method can be implemented in SIMD architecture as follows:
1. (9 Instructions) AJL = Unpack Low 4 Bytes of A ;, for / = 1 , ... ,9.
2. (9 Instructions) A iH = Unpack High 4 Bytes of Ai, for i = 1 , ... ,9.
3. (11 Instructions) Add and Shift lower 4 words of Ai,...,A 9 to obtain lower 4 words of RL: RL = (A 1L +((A 2L +A 3L +A 4L +A 5L +A 6L +A 7L +A 8L )«1)+A 9L +8*ONE)»4.
4. (11 Instructions) Add and Shift higher 4 words of A 1 , ...,A 9 to obtain higher 4 words of RH: RH = (A 1H +((A 2H +A 3H +A 4H +A 5H +A 6H +A 7H +A 8H )«1)+A 9H +8*ONE)»4.
5. (1 Instruction) Pack RH and RL into final vector R.
[00103] The conventional method requires 41 instructions. For the efficient method, we have the following simplifications:
B 1 = AVG(A i A 9 ), B 2 =A 2 , B 3 = A 3 , B 4 = A 4 ,
B 5 = A 5 , B 6 = A 6 , B 7 = A 7 , Bg = A 8 , C 1 = AVG(BiA 2 ), C 2 = AVG(A 3 AAI C 3 = AVG(A 5 A 6 ), C 4 = AVG(A 7 Ag),
D x = AVG(C h C 2 ), D 2 = AVG(C 3 ,C 4 ), and D = AVG(D h D 2 ). (42)
[00104] The efficient method is:
1. (8 Instructions) Compute D from (42) as: D = AVG(AVG(AVG(AVG(A 15 A 9 XA 2 XAVG(A 35 A 4 )XAVG(AVG(A 5 A)AVG(A 75 A 8 ))).
2. ( 1 Instruction) Compute U = ADDSAT(D+3*ONE).
3. (1 1 Instructions) Compute L =
(Ai+((A 2 +A 3 +A 4 +A 5 +A 6 +A 7 +A 8 )«l)+A 9 +8*ONE)»4. This is a truncated packed 8-bit addition.
4. (2 Instruction) Compute error E = SUBSAT(U - L) & 7*ONE.
5. (1 Instruction) Subtract this error E from U to obtain R = SUBSAT(U - E).
[00105] The new algorithm requires 23 instructions as compared to 41 instructions for the conventional method.
Type 4 - Special Filter 4: R = (Ai+2A2+3A 3 +4A4+3A5+2A6+A7+8*ONE)»4. [00106] The conventional method can be implemented in SIMD architecture as follows:
1. (7 Instructions) λ/L = Unpack Low 4 Bytes of A[, for / = 1 , ... ,7.
2. (7 Instructions) A; H = Unpack High 4 Bytes of Ai, for i = I 5 ...,7.
3. (12 Instructions) Add and Shift lower 4 words of Aj , ... ,A 7 to obtain lower 4 words of RL: RL =
(A 1L +A 3L +A 5L +((A 2L +A 3L +A 5L +A 6L )«1)+(A 4L «2)+A 7L +8*ONE)»4.
4. (12 Instructions) Add and Shift higher 4 words of A 1 ,...,A 9 to obtain higher 4 words of RH: RH =
(A 1H +A 3H +A 5H +((A 2H +A 3H +A 5H +A 6H )«1)+(A 4H «2)+A 7H +8*ONE)»4.
5. (1 Instruction) Pack RH and RL into final vector R.
[00107] The conventional method requires 39 instructions. For the present efficient method, the present invention has the following simplifications:
B x = AVG(AiA 7 ), B 2 =A 2 , B 3 = A 3 , B 4 = A 4 ,
B 5 = A 4 , B 6 =A 5 , B 7 = A 6 , B 8 = AVG(A 3 A 5 ),
C 1 = AVG(BiA 2 ), C 2 =AVG(A 3 A5), C 3 =A 4 , C 4 =AVG(A 6 ,B % ),
Z) 1 = AVG(C h C 2 ), D 2 = AVG(A 4 ,C 4 ), and D = AVG(D h D 2 ). (43)
[00108] The present efficient method is:
1. (8 Instructions) Compute D from (43) as: D =
AVG(AVG(A VG(AVG(A 1 ,A 7 ),A 2 ),AVG(A 3 ,A 5 )),AVG(A 4 ,AVG(A 6 ,A VG(A 31 A 5 )))).
2. ( 1 Instruction) Compute U = ADDSAT(D+3*ONE).
3. (12 Instructions) Compute L =
(Ai+A 3 +A 5 +((A 2 +A 3 +A 5 +A 6 )<<l)+(A 4 <<2)+A 7 +8*ONE)>>4. This is a truncated packed 8-bit addition.
4. (2 Instruction) Compute error E = SUBSAT(U - L) & 7*ONE.
5. (1 Instruction) Subtract this error E from U to obtain R = SUBSAT(U - E).
[00109] The new method requires 24 instructions as compared to 39 instructions for the conventional method.
[00110] Table 5 below summarizes the instructions required to compute each filter (given sufficient memory) by the efficient and conventional SEVID methods.
Table 5.
[00111] The present invention discloses efficient SIMD implementations for 4 types of causal FIR filters. In each case, the present invention offered an efficient implementation with SIMD architecture and compared that with conventional SIMD implementations. The present invention also discussed several FIR filters that can be used in MPEG and AVC video coding standards. The present implementations of the invention are considerably more efficient than conventional SIMD implementations.
[00112] FIG. 6 is a block diagram of the present signal system being implemented with a general purpose computer or computing device. In one embodiment, the content distribution system is implemented using a general purpose computer or any other hardware equivalents. More specifically, the signal system 600 comprises a processor (CPU) 602, a memory 604, e.g., random access memory (RAM) and/or read only memory (ROM), FIR digital filters 605 for implementing the methods as described above, and various input/output devices 606 (e.g., storage devices, including but not limited to, a tape drive, a floppy drive, a hard disk drive or a compact disk drive, a receiver, a decoder, a decryptor, a transmitter, a clock, a speaker, a display, an output port, a user input device (such as a keyboard, a keypad, a mouse, and the like), or a microphone for capturing speech commands).
[00113] It should be understood that the FIR digital filters 605 can be implemented as a physical device or subsystem that is coupled to the CPU 602 through a communication channel. Alternatively, the FIR digital filters 605 can be represented by one or more software applications (or even a combination of software and hardware, e.g., using application specific integrated circuits (ASIC)), where the software is loaded from a storage medium (e.g., a magnetic or optical drive or diskette) and operated by the CPU in the memory 604 of the computer. As such, the FIR digital filters 605 (including associated data structures and methods employed within the encoder) of the present invention can be stored on a computer readable medium or carrier, e.g., RAM memory, magnetic or optical drive or diskette and the like.
[00114] While the foregoing is directed to embodiments of the present invention, other and further embodiments of the invention may be devised without departing from the basic scope thereof, and the scope thereof is determined by the claims that follow.