TWI695250B - Lookup table configuration method capable of reducing the number of multiplexers and information processing device using the same - Google Patents
Lookup table configuration method capable of reducing the number of multiplexers and information processing device using the same Download PDFInfo
- Publication number
- TWI695250B TWI695250B TW107142549A TW107142549A TWI695250B TW I695250 B TWI695250 B TW I695250B TW 107142549 A TW107142549 A TW 107142549A TW 107142549 A TW107142549 A TW 107142549A TW I695250 B TWI695250 B TW I695250B
- Authority
- TW
- Taiwan
- Prior art keywords
- value
- vertex
- multiplexers
- lookup table
- perform
- Prior art date
Links
Images
Landscapes
- Image Processing (AREA)
Abstract
一種可減少多工器數量的查找表配置方法,用以對以n維排列的複數個內插節點進行一n維線性內插運算,n為大於或等於3的正整數,該方法包括以下步驟:(1b)利用2^n個第一階層多工器電路對所述以n維排列的複數個內插節點進行一預選頂點選取作業以產生2^n個預選頂點;(2b)利用一第二階層多工器電路對所述2^n個預選頂點進行一頂點選取作業以產生2^n個頂點;以及(3b)依所述2^n個頂點進行所述n維線性內插運算。A lookup table configuration method capable of reducing the number of multiplexers to perform an n-dimensional linear interpolation operation on a plurality of interpolation nodes arranged in n dimensions, where n is a positive integer greater than or equal to 3, the method includes the following steps : (1b) use 2^n first-level multiplexer circuits to perform a preselected vertex selection operation on the n-dimensionally arranged plurality of interpolation nodes to generate 2^n preselected vertices; (2b) use a first The two-level multiplexer circuit performs a vertex selection operation on the 2^n preselected vertices to generate 2^n vertices; and (3b) performs the n-dimensional linear interpolation operation according to the 2^n vertices.
Description
本發明係關於內插法與查找表(Look-up table, LUT)的技術領域,尤指一種可減少多工器數量的查找表配置方法及利用其之資訊處理裝置。The invention relates to the technical field of interpolation method and look-up table (LUT), in particular to a look-up table configuration method capable of reducing the number of multiplexers and an information processing device using the same.
利用內插法與查找表以減少電路元件及縮短資料處理時間的做法已廣泛應用在各種電子產品中,尤其是具有顯示、觸控功能的電子產品中。就顯示技術而言, H.264為最新的數位視訊壓縮標準,其係藉由引進不同的編碼方式來獲得更高的壓縮效率,其中,H.264/SVC可調性視訊編碼使用各種內插演算法來提升數位視訊的編碼效率,而目前最普遍使用的內插演算法包括:最鄰近內插法(Nearest - neighborhood interpolation)、雙線性內插法(Bi-linear interpolation)及雙立方內插法(Bi-cubic interpolation)。The method of using interpolation and look-up tables to reduce circuit components and shorten data processing time has been widely used in various electronic products, especially those with display and touch functions. As far as the display technology is concerned, H.264 is the latest digital video compression standard. It introduces different encoding methods to obtain higher compression efficiency. Among them, H.264/SVC adjustable video encoding uses various interpolations. Algorithms to improve the coding efficiency of digital video, and the most commonly used interpolation algorithms currently include: Nearest-neighbor interpolation, Bi-linear interpolation, and double-square interpolation Interpolation (Bi-cubic interpolation).
為了提高影像處理速度,習知已有透過在一個場可程式化邏輯閘陣列(Field Programmable Gate Array, FPGA)晶片中配置暫存器查找表(Look-up table, LUT)及其他必要的影像處理程式,以藉此將該FPGA晶片製成一影像處理晶片的做法。值得說明的是,暫存器查找表會於FPGA晶片啟用時自外部記憶體載入利用內插運算法預先計算好的參考樣本(Reference samples)。如此,當該影像處理晶片對一特定的來源影像進行影像處理或視訊編碼時,影像處理晶片內的核心處理器(Core processor)或控制器便可透過查表的方式,快速地完成所述影像處理或視訊編碼。In order to increase the image processing speed, it is known to configure a look-up table (LUT) and other necessary image processing programs in a Field Programmable Gate Array (FPGA) chip To use this FPGA chip as an image processing chip. It is worth noting that the look-up table of the register will load reference samples pre-calculated by the interpolation algorithm from the external memory when the FPGA chip is activated. In this way, when the image processing chip performs image processing or video encoding on a specific source image, the core processor or controller in the image processing chip can quickly complete the image by means of table lookup Processing or video encoding.
H.264的視訊編碼標準的最小精度到1/4像素(Pixel),也就是說,一個像素可進一步被分為4x4個子像素。因此,利用一維內插演算法對一個影像幀(Image frame)執行影像處理或編碼之時,同樣地可將一個影像幀分割成1x16個像素區塊,並將這些像素區塊視為16個內插估算單元(Interpolation prediction unit, PU),藉以在進行影像處理或視訊編碼的過程中,不斷地對這16個內插估算單元進行移動估計或補償。請參照圖1,其為以17個內插節點進行一個習知一維線性內插作業的示意圖。在進行所述的習知一維線性內插作業時,必須先由(P1、 P2、 P3、P4、P5、P6、P7、P8、P9、P10、P11、P12、P13、P14、P15、P16)這16個內插節點找出一左邊界,接著再由(P2、P3、P4、P5、P6、P7、P8、P9、P10、P11、P12、 P13、P14、P15、P16、P17)這16個內插節點找出該一右邊界。The minimum accuracy of the H.264 video coding standard is 1/4 pixel (Pixel), that is to say, a pixel can be further divided into 4x4 sub-pixels. Therefore, when using a one-dimensional interpolation algorithm to perform image processing or encoding on an image frame, the same image frame can be divided into 1x16 pixel blocks, and these pixel blocks are regarded as 16 Interpolation prediction unit (PU), so as to continuously perform motion estimation or compensation on these 16 interpolation estimation units during image processing or video encoding. Please refer to FIG. 1, which is a schematic diagram of performing a conventional one-dimensional linear interpolation operation using 17 interpolation nodes. When performing the conventional one-dimensional linear interpolation described above, you must first select (P1, P2, P3, P4, P5, P6, P7, P8, P9, P10, P11, P12, P13, P14, P15, P16 ) These 16 interpolating nodes find a left boundary, and then by (P2, P3, P4, P5, P6, P7, P8, P9, P10, P11, P12, P13, P14, P15, P16, P17) 16 interpolation nodes find the right boundary.
請參照圖2,其繪示用以實現圖1之習知一維線性內插作業之一查找表架構圖。如圖2所示,為了加速完成一內插點的左邊界的設定,該查找表架構配置有包括16個暫存器11’與15個多工器12’的一組4輸入查找表(4-input LUT)1’,稱為4輸入LUT,並將 (P1、P2、P3、P4、P5、P6、P7、P8、P9、P10、P11、P12、P13、P14、P15、P16)這16個內插節點的數值分別暫存於16個暫存器11’中。同樣地,為了加速完成該內插點的右邊界的設定,該查找表架構配置有另一組同樣包括16個暫存器11’與15個多工器12’的4輸入查找表1’(參考圖2)。簡單地說,該查找表架構必須用到30個多工器12’才能夠以一維內插法推算出一個內插值。Please refer to FIG. 2, which shows a look-up table architecture for implementing the conventional one-dimensional linear interpolation operation of FIG. 1. As shown in FIG. 2, in order to speed up the setting of the left boundary of an interpolation point, the look-up table architecture is configured with a set of 4-input look-up tables including 16
另外,請參照圖3,其為以17x17個內插節點進行一個習知二維線性內插作業的示意圖。在進行該習知二維線性內插作業時,必須先由4個多工器電路(各包含255(=16x16-1)個2對1多工器)決定四個角(頂點)的數值,包括: P(UR)、P(DR)、P(UL)及P(DL),然後再據以進行一個二維內插演算法(Bi-linear interpolation)。簡單地說,該習知二維線性內插作業必須用到255 x 4=1020個多工器才能夠以二維內插法推算出一個內插值。In addition, please refer to FIG. 3, which is a schematic diagram of performing a conventional two-dimensional linear interpolation operation using 17×17 interpolation nodes. When performing the conventional two-dimensional linear interpolation operation, the values of the four corners (vertices) must be determined by four multiplexer circuits (each containing 255 (=16x16-1) 2 to 1 multiplexers), Including: P(UR), P(DR), P(UL) and P(DL), and then perform a two-dimensional interpolation algorithm (Bi-linear interpolation). Simply put, in this conventional two-dimensional linear interpolation operation, 255 x 4=1020 multiplexers must be used to calculate an interpolated value by two-dimensional interpolation.
然而,前述的習知技術方案除了會包含大量且複雜的線(wires)與網(nets)外,其數目龐大的多工器不但會佔據很多的晶片面積,也會增加很多的晶片功耗。However, in addition to the large number of complicated wires and nets, the aforementioned conventional technical solutions not only occupy a lot of chip area, but also increase the chip power consumption.
因此,本領域亟需一種新穎的查找表配置方法。Therefore, a novel lookup table configuration method is urgently needed in the art.
本發明之主要目的在於提出一種可減少多工器數量的查找表配置方法,其可先藉由一第一階層多工電路對複數個奇數內插節點和複數個偶數內插節點分別進行一預選邊界查找作業,再藉由一第二階層多工電路對複數個預選邊界點進行一邊界點確定作業,然後再依複數個經確定的邊界點進行一線性內插運算以大量減少多工器的數量,從而簡化連接線路(wires, nets )。The main purpose of the present invention is to propose a lookup table configuration method that can reduce the number of multiplexers, which can first perform a preselection of a plurality of odd interpolation nodes and a plurality of even interpolation nodes by a first-level multiplexing circuit Boundary search operation, and then perform a boundary point determination operation on a plurality of preselected boundary points by a second-level multiplex circuit, and then perform a linear interpolation operation on the plurality of determined boundary points to greatly reduce the multiplexer's Quantity, thereby simplifying connection lines (wires, nets).
為達成上述目的,一種可減少多工器數量的查找表配置方法乃被提出,其係用以對N個內插節點進行一個一維線性內插運算,所述N個內插節點包含N1個奇數節點及N2個偶數節點,N、N1及N2皆為正整數且N=N1+N2,該方法包括以下步驟:To achieve the above objective, a lookup table configuration method capable of reducing the number of multiplexers is proposed, which is used to perform a one-dimensional linear interpolation operation on N interpolation nodes, the N interpolation nodes including N1 Odd nodes and N2 even nodes, N, N1 and N2 are all positive integers and N=N1+N2, the method includes the following steps:
(1)配置包含N1-1個第一多工器的一第一查找表單元以對N1個所述奇數節點進行一左邊界預選作業,以獲得一左邊界預選值;(1) Configure a first lookup table unit including N1-1 first multiplexers to perform a left boundary preselection operation on the N1 odd nodes to obtain a left boundary preselected value;
(2)配置包含N2-1個第二多工器的一第二查找表單元以對N2個所述偶數節點進行一右邊界預選作業,以獲得一右邊界預選值;(2) Configure a second lookup table unit including N2-1 second multiplexers to perform a right boundary preselection operation on the N2 even nodes to obtain a right boundary preselected value;
(3)配置包含一個第三多工器的一第三查找表單元以對該左邊界預選值與該右邊界預選值進行一左邊界選取作業,以獲得一左邊界數值;(3) Configure a third lookup table unit including a third multiplexer to perform a left boundary selection operation on the left boundary preselected value and the right boundary preselected value to obtain a left boundary value;
(4)配置包含一個第四多工器的一第四查找表單元以對該左邊界預選值與該右邊界預選值進行一右邊界選取作業,以獲得一右邊界數值;以及(4) Configure a fourth lookup table unit including a fourth multiplexer to perform a right boundary selection operation on the left boundary preselected value and the right boundary preselected value to obtain a right boundary value; and
(5)依該左邊界數值和該右邊界數值進行所述一維線性內插運算。(5) Perform the one-dimensional linear interpolation operation according to the left boundary value and the right boundary value.
在一實施例中,所述第一多工器、所述第二多工器、所述第三多工器、和所述第四多工器均為2對1多工器。In an embodiment, the first multiplexer, the second multiplexer, the third multiplexer, and the fourth multiplexer are all 2-to-1 multiplexers.
為達成上述目的,另一種可減少多工器數量的查找表配置方法乃被提出,其係用以對M×N個內插節點進行一個二維線性內插運算,所述M×N個內插節點中的各列均包含N1個奇數節點及N2個偶數節點,且所述M×N個內插節點中的各行均包含M1個奇數節點及M2個偶數節點,其中N、N1、N2、M、M1、及M2皆為正整數, N=N1+N2,且M=M1+M2;該方法包括以下步驟:To achieve the above purpose, another lookup table configuration method capable of reducing the number of multiplexers is proposed, which is used to perform a two-dimensional linear interpolation operation on M×N interpolation nodes, the M×N Each column in the interpolation node includes N1 odd nodes and N2 even nodes, and each row in the M×N interpolation nodes includes M1 odd nodes and M2 even nodes, where N, N1, N2, M, M1, and M2 are all positive integers, N=N1+N2, and M=M1+M2; the method includes the following steps:
(1a)配置包含M1×N1-1個第一多工器的一第一查找表單元以對M1×N1個所述內插節點進行一左上頂點預選作業,以獲得一左上頂點預選值;(1a) Configure a first look-up table unit containing M1×N1-1 first multiplexers to perform an upper-left vertex preselection operation on the M1×N1 said interpolation nodes to obtain an upper-left vertex preselection value;
(2a)配置包含M2×N1-1個第二多工器的一第二查找表單元以對M2×N1個所述內插節點進行一右上頂點預選作業,以獲得一右上頂點預選值;(2a) Configure a second lookup table unit including M2×N1-1 second multiplexers to perform a pre-selection operation on the upper-right vertex of the M2×N1 interpolation nodes to obtain a pre-selection value on the upper-right vertex;
(3a)配置包含M1×N2-1個第三多工器的一第三查找表單元以對M1×N2個所述內插節點進行一左下頂點預選作業,以獲得一左下頂點預選值;(3a) Configure a third lookup table unit including M1×N2-1 third multiplexers to perform a lower left vertex preselection operation on the M1×N2 interpolation nodes to obtain a lower left vertex preselection value;
(4a) 配置包含M2×N2-1個第四多工器的一第四查找表單元以對M2×N2個所述內插節點進行一右下頂點預選作業,以獲得一右下頂點預選值;(4a) Configure a fourth lookup table unit including M2×N2-1 fourth multiplexers to perform a pre-selection of the lower right vertex on the M2×N 2 interpolation nodes to obtain a pre-selected value of the lower right vertex ;
(5a)配置包含三個第五多工器的一第五查找表單元以對該左上頂點預選值、該右上頂點預選值、該左下頂點預選值、及該右下頂點預選值進行一左上頂點選取作業,以獲得一左上頂點數值;(5a) Configure a fifth lookup table unit including three fifth multiplexers to perform an upper left vertex on the upper left vertex preselected value, the upper right vertex preselected value, the lower left vertex preselected value, and the lower right vertex preselected value Select the job to obtain a top left vertex value;
(6a)配置包含三個第六多工器的一第六查找表單元以對該左上頂點預選值、該右上頂點預選值、該左下頂點預選值、及該右下頂點預選值進行一右上頂點選取作業,以獲得一右上頂點數值;(6a) Configure a sixth lookup table unit including three sixth multiplexers to perform an upper right vertex on the upper left vertex preselected value, the upper right vertex preselected value, the lower left vertex preselected value, and the lower right vertex preselected value Select the job to obtain a top right vertex value;
(7a)配置包含三個第七多工器的一第七查找表單元以對該左上頂點預選值、該右上頂點預選值、該左下頂點預選值、及該右下頂點預選值進行一左下頂點選取作業,以獲得一左下頂點數值;(7a) Configure a seventh lookup table unit including three seventh multiplexers to perform a lower left vertex on the upper left vertex preselected value, the upper right vertex preselected value, the lower left vertex preselected value, and the lower right vertex preselected value Select the job to obtain a lower left vertex value;
(8a)配置包含三個第八多工器的一第八查找表單元以對該左上頂點預選值、該右上頂點預選值、該左下頂點預選值、及該右下頂點預選值進行一右下頂點選取作業,以獲得一右下頂點數值;以及(8a) Configure an eighth lookup table unit including three eighth multiplexers to perform a lower right on the upper left vertex preselected value, the upper right vertex preselected value, the lower left vertex preselected value, and the lower right vertex preselected value Vertex selection operation to obtain a lower right vertex value; and
(9a)依該左上頂點數值、該右上頂點數值、該左下頂點數值和該右下頂點數值進行所述二維線性內插運算。(9a) Perform the two-dimensional linear interpolation operation according to the upper left vertex value, the upper right vertex value, the lower left vertex value, and the lower right vertex value.
在一實施例中,所述第一多工器、所述第二多工器、所述第三多工器、所述第四多工器、所述第五多工器、所述第六多工器、所述第七多工器、和所述第八多工器均為2對1多工器。In an embodiment, the first multiplexer, the second multiplexer, the third multiplexer, the fourth multiplexer, the fifth multiplexer, the sixth The multiplexer, the seventh multiplexer, and the eighth multiplexer are all 2-to-1 multiplexers.
為達成上述目的,又一種可減少多工器數量的查找表配置方法乃被提出,其係用以對以n維排列的複數個內插節點進行一n維線性內插運算,n為大於或等於3的正整數,該方法包括以下步驟:To achieve the above objective, another lookup table configuration method that can reduce the number of multiplexers is proposed. It is used to perform an n-dimensional linear interpolation operation on a plurality of interpolation nodes arranged in n dimensions, where n is greater than or A positive integer equal to 3, the method includes the following steps:
(1b)利用2^n個第一階層多工器電路對所述以n維排列的複數個內插節點進行一預選頂點選取作業以產生2^n個預選頂點;(1b) Use 2^n first-level multiplexer circuits to perform a preselected vertex selection operation on the n-dimensionally arranged plurality of interpolation nodes to generate 2^n preselected vertices;
(2b)利用一第二階層多工器電路對所述2^n個預選頂點進行一頂點選取作業以產生2^n個頂點;以及(2b) Performing a vertex selection operation on the 2^n preselected vertices using a second layer multiplexer circuit to generate 2^n vertices; and
(3b)依所述2^n個頂點進行所述n維線性內插運算。(3b) Perform the n-dimensional linear interpolation operation according to the 2^n vertices.
在一實施例中,所述第一多工器電路和所述第二多工器電路均由複數個2對1多工器所組成。In an embodiment, the first multiplexer circuit and the second multiplexer circuit are both composed of a plurality of 2 to 1 multiplexers.
另外,本發明進一步提出一種資訊處理裝置,其具有一處理器以執行如前述之可減少多工器數量的查找表配置方法。In addition, the present invention further provides an information processing device having a processor to execute a lookup table configuration method that can reduce the number of multiplexers as described above.
在可能的實施例中,所述之資訊處理裝置可為一智慧型手機或一可攜式電腦。In a possible embodiment, the information processing device may be a smart phone or a portable computer.
為使 貴審查委員能進一步瞭解本發明之結構、特徵、目的、極其優點,茲附以圖式及較佳具體實施例之詳細說明如後。In order to enable your review committee to further understand the structure, features, objectives, and extreme advantages of the present invention, the drawings and the detailed description of the preferred embodiments are attached as follows.
第一實施例First embodiment
請一併參照圖4及圖5,其中,圖4顯示本發明之可減少多工器數量的查找表配置方法之一實施例的流程圖,而圖5顯示利用圖4之方法建置的一個查找表模組的架構圖,其包含一儲存單元10、一第一查找表單元11、一第二查找表單元12、一第三查找表單元13及一第四查找表單元14。圖4所示的方法係用以對N個內插節點進行一個一維線性內插運算,所述N個內插節點包含N1個奇數節點及N2個偶數節點,N、N1及N2皆為正整數且N=N1+N2,該方法包括以下步驟:配置包含N1-1個第一多工器的一第一查找表單元11以對N1個所述奇數節點進行一左邊界預選作業,以獲得一左邊界預選值,及配置包含N2-1個第二多工器的一第二查找表單元12以對N2個所述偶數節點進行一右邊界預選作業,以獲得一右邊界預選值(S1);配置包含一個第三多工器的一第三查找表單元13以對該左邊界預選值與該右邊界預選值進行一左邊界選取作業,以獲得一左邊界數值,及配置包含一個第四多工器的一第四查找表單元14以對該左邊界預選值與該右邊界預選值進行一右邊界選取作業,以獲得一右邊界數值(S2);以及依該左邊界數值和該右邊界數值進行所述一維線性內插運算(S3)。Please refer to FIG. 4 and FIG. 5 together. FIG. 4 shows a flowchart of an embodiment of a lookup table configuration method for reducing the number of multiplexers of the present invention, and FIG. 5 shows a method built using the method of FIG. 4. The architecture diagram of the look-up table module includes a
請同時參考圖1,圖4所示的方法主要是用以對N個內插節點進行一個一維線性內插運算,所述N(17)個內插節點包含N1(9)個奇數節點及N2(8)個偶數節點,N、N1及N2皆為正整數且N=N1+N2,且所述N(17)個內插節點的數值係儲存在一儲存單元10(例如一暫存器單元或一靜態隨機存取記憶體(SRAM;static random access memory))中。Please also refer to FIG. 1. The method shown in FIG. 4 is mainly used to perform a one-dimensional linear interpolation operation on N interpolation nodes. The N (17) interpolation nodes include N1 (9) odd nodes and N2(8) even-numbered nodes, N, N1, and N2 are all positive integers and N=N1+N2, and the values of the N(17) interpolated nodes are stored in a storage unit 10 (such as a scratchpad) Unit or a static random access memory (SRAM; static random access memory).
在執行步驟S1時,本發明配置包含N1-1(8)個第一多工器的一第一查找表單元11以對N1(9)個所述奇數節點進行一左邊界預選作業,以獲得一左邊界預選值;及配置包含N2-1(7)個第二多工器的一第二查找表單元12以對N2(8)個所述偶數節點進行一右邊界預選作業,以獲得一右邊界預選值。以圖1所示的17個內插節點為例,在執行步驟S1時,本發明係依據(P1, P3, P5, P7, P9, P11, P13, P15, P17)這9個內插節點找出所述左邊界預選值,及依據(P2, P4, P6, P8, P10, P12, P14, P16)這8個內插節點找出所述右邊界預選值,其中所述的第一多工器和第二多工器皆為2對1多工器。When performing step S1, the present invention configures a first
在執行步驟S2時,本發明配置包含一個第三多工器的一第三查找表單元13以對該左邊界預選值與該右邊界預選值進行一左邊界選取作業,以獲得一左邊界數值;以及配置包含一個第四多工器的一第四查找表單元14以對該左邊界預選值與該右邊界預選值進行一右邊界選取作業,以獲得一右邊界數值,其中所述的第三多工器和第四多工器皆為2對1多工器。When performing step S2, the present invention configures a third
在執行步驟S3時,本發明依該左邊界數值和該右邊界數值進行所述一維線性內插運算。When performing step S3, the present invention performs the one-dimensional linear interpolation operation according to the left boundary value and the right boundary value.
由上述說明可知,本發明的技術方案可大幅減少多工器的數量。請參照表1,本發明總共使用17個多工器,其數量遠低於所述習知一維線性內插作業所使用的多工器數量(30個)。事實上,就一維線性內插而言,當N很大時,本發明可節省約N/2個多工器。As can be seen from the above description, the technical solution of the present invention can greatly reduce the number of multiplexers. Referring to Table 1, the present invention uses a total of 17 multiplexers, the number of which is much lower than the number of multiplexers (30) used in the conventional one-dimensional linear interpolation operation. In fact, in terms of one-dimensional linear interpolation, when N is large, the present invention can save about N/2 multiplexers.
表1
第二實施例Second embodiment
請一併參照圖6及圖7,其中圖6顯示本發明之可減少多工器數量的查找表配置方法之另一實施例的流程圖,其包括:進行四個預選頂點選取作業(步驟S1a);進行四個頂點選取作業(步驟S2a);以及進行一個二維線性內插運算(步驟S3a);而圖7顯示利用圖6之方法建置的一個查找表模組的架構圖,其包含一儲存單元10a、一第一查找表單元11a、一第二查找表單元12a、一第三查找表單元13a、一第四查找表單元14a、一第五查找表單元15a、一第六查找表單元16a、一第七查找表單元17a及一第八查找表單元18a。Please refer to FIG. 6 and FIG. 7 together. FIG. 6 shows a flowchart of another embodiment of a lookup table configuration method for reducing the number of multiplexers of the present invention, which includes: performing four pre-selected vertex selection operations (step S1a ); perform four vertex selection operations (step S2a); and perform a two-dimensional linear interpolation operation (step S3a); and FIG. 7 shows the architecture diagram of a look-up table module built using the method of FIG. 6, which includes A
請同時參考圖3,圖6之可減少多工器數量的查找表配置方法主要是用以對M×N個內插節點進行一個二維線性內插運算,所述M×N(17×17)個內插節點中的各列均包含N1(9)個奇數節點及N2(8)個偶數節點,且所述M×N個內插節點中的各行均包含M1(9)個奇數節點及M2(8)個偶數節點,其中N、N1、N2、M、M1、及M2皆為正整數, N=N1+N2,且M=M1+M2。並且,所述M×N(17×17)個內插節點的數值是預存於儲存單元10a中。儲存單元10a可為SRAM或暫存器單元,並不加以限制。Please also refer to FIG. 3 and FIG. 6 for a lookup table configuration method that can reduce the number of multiplexers, which is mainly used to perform a two-dimensional linear interpolation operation on M×N interpolation nodes. The M×N(17×17 ) Each column of the interpolation nodes includes N1(9) odd nodes and N2(8) even nodes, and each row of the M×N interpolation nodes includes M1(9) odd nodes and M2(8) even-numbered nodes, where N, N1, N2, M, M1, and M2 are all positive integers, N=N1+N2, and M=M1+M2. Moreover, the values of the M×N (17×17) interpolation nodes are pre-stored in the
在執行步驟S1a時,本發明配置有包含M1×N1-1個第一多工器的一第一查找表單元11a以對M1×N1個所述內插節點進行一左上頂點預選作業,以獲得一左上頂點預選值;配置有包含M2×N1-1個第二多工器的一第二查找表單元12a以對M2×N1個所述內插節點進行一右上頂點預選作業,以獲得一右上頂點預選值;配置有包含M1×N2-1個第三多工器的一第三查找表單元13a以對M1×N2個所述內插節點進行一左下頂點預選作業,以獲得一左下頂點預選值;以及配置有包含M2×N2-1個第四多工器的一第四查找表單元14a以對M2×N2個所述內插節點進行一右下頂點預選作業,以獲得一右下頂點預選值。When performing step S1a, the present invention is configured with a first lookup table unit 11a including M1×N1-1 first multiplexers to perform a top-left vertex preselection operation on the M1×N1 interpolation nodes to obtain A top left vertex preselection value; a second
在執行步驟S2a時,本發明配置有包含三個第五多工器的一第五查找表單元15a以對該左上頂點預選值、該右上頂點預選值、該左下頂點預選值及該右下頂點預選值進行一左上頂點選取作業,以獲得一左上頂點數值;配置有包含三個第六多工器的一第六查找表單元16a以對該左上頂點預選值、該右上頂點預選值、該左下頂點預選值及該右下頂點預選值進行一右上頂點選取作業,以獲得一右上頂點數值;配置有包含三個第七多工器的一第七查找表單元17a以對該左上頂點預選值、該右上頂點預選值、該左下頂點預選值及該右下頂點預選值進行一左下頂點選取作業,以獲得一左下頂點數值;以及配置有包含三個第八多工器的一第八查找表單元18a以對該左上頂點預選值、該右上頂點預選值、該左下頂點預選值及該右下頂點預選值進行一右下頂點選取作業,以獲得一右下頂點數值。When performing step S2a, the present invention is configured with a fifth
在執行步驟S3a時,本發明依該左上頂點數值、該右上頂點數值、該左下頂點數值和該右下頂點數值進行所述二維線性內插運算。When performing step S3a, the present invention performs the two-dimensional linear interpolation operation according to the upper left vertex value, the upper right vertex value, the lower left vertex value and the lower right vertex value.
補充說明的是,所述第一多工器、所述第二多工器、所述第三多工器、所述第四多工器、所述第五多工器、所述第六多工器、所述第七多工器、和所述第八多工器均為2對1多工器。It is added that the first multiplexer, the second multiplexer, the third multiplexer, the fourth multiplexer, the fifth multiplexer, the sixth multiplexer The multiplexer, the seventh multiplexer, and the eighth multiplexer are all 2-to-1 multiplexers.
由上述說明可知,本發明的技術方案可大幅減少多工器的數量。請參照表2,本發明總共使用297個多工器,其數量遠低於所述習知二維線性內插作業所使用的多工器數量(1020個)。事實上,就二維線性內插而言,假設M=N,當N很大時,本發明可節省約3N^2/4個多工器。As can be seen from the above description, the technical solution of the present invention can greatly reduce the number of multiplexers. Referring to Table 2, the present invention uses a total of 297 multiplexers, the number of which is much lower than the number of multiplexers used in the conventional two-dimensional linear interpolation operation (1020). In fact, as far as two-dimensional linear interpolation is concerned, assuming M=N, when N is large, the present invention can save about 3N^2/4 multiplexers.
表(2)
第三實施例Third embodiment
雖然前述說明的兩個實施例是分別用以實現一維線性內插演算法和二維線性內插演算法,然而,本發明之方法亦可被擴充應用至n維(n-D)內插演算法。Although the two embodiments described above are used to implement a one-dimensional linear interpolation algorithm and a two-dimensional linear interpolation algorithm, however, the method of the present invention can also be extended to an n-dimensional (nD) interpolation algorithm .
請參照圖8,其為本發明之可減少多工器數量的查找表配置方法之又一實施例的流程圖。該實施例主要是用以對以n維排列的複數個內插節點進行一n維線性內插運算,n為大於或等於3的正整數。如圖8所示,該方法包括:利用2^n個第一階層多工器電路對所述以n維排列的複數個內插節點進行一預選頂點選取作業以產生2^n個預選頂點(步驟1b);利用一第二階層多工器電路對所述2^n個預選頂點進行一頂點選取作業以產生2^n個頂點(步驟2b);以及依所述2^n個頂點進行所述n維線性內插運算(步驟3b)。Please refer to FIG. 8, which is a flowchart of another embodiment of a lookup table configuration method that can reduce the number of multiplexers of the present invention. This embodiment is mainly used to perform an n-dimensional linear interpolation operation on a plurality of interpolation nodes arranged in n dimensions, where n is a positive integer greater than or equal to 3. As shown in FIG. 8, the method includes: using 2^n first-level multiplexer circuits to perform a preselected vertex selection operation on the plurality of n-dimensionally arranged interpolation nodes to generate 2^n preselected vertices ( Step 1b); use a second-level multiplexer circuit to perform a vertex selection operation on the 2^n preselected vertices to generate 2^n vertices (step 2b); and perform the operations according to the 2^n vertices The n-dimensional linear interpolation operation (step 3b) is described.
依上述的說明,本發明進一步提出一種資訊處理裝置。請參照圖9,其繪示本發明之資訊處理裝置之一實施例方塊圖。如圖9所示,一資訊處理裝置100(其可為一智慧型手機或一可攜式電腦)具有一處理器110及一多工器電路120,其中多工器電路120具有如前述之兩階層架構,且處理器110係用以執行如前述之可減少多工器數量的查找表配置方法。According to the above description, the present invention further provides an information processing device. Please refer to FIG. 9, which illustrates a block diagram of an embodiment of the information processing device of the present invention. As shown in FIG. 9, an information processing device 100 (which may be a smartphone or a portable computer) has a
如此,上述已完整且清楚地說明本發明之可減少多工器數量的查找表配置方法及的步驟組成與技術特徵;並且,經由上述可得知本發明係具有下列之優點:In this way, the above has completely and clearly explained the method and the step composition and technical characteristics of the lookup table configuration method which can reduce the number of multiplexers of the present invention; and, through the above, the present invention has the following advantages:
本發明的查找表配置方法可先藉由一第一階層多工電路對複數個奇數內插節點和複數個偶數內插節點分別進行一預選邊界查找作業,再藉由一第二階層多工電路對複數個預選邊界點進行一邊界點確定作業,然後再依複數個經確定的邊界點進行一線性內插運算以大量減少多工器的數量,從而簡化連接線路(wires, nets )。The lookup table configuration method of the present invention can first perform a preselected boundary search operation on a plurality of odd interpolation nodes and a plurality of even interpolation nodes through a first-level multiplex circuit, and then through a second-level multiplex circuit Perform a boundary point determination operation on a plurality of pre-selected boundary points, and then perform a linear interpolation operation on the plurality of determined boundary points to greatly reduce the number of multiplexers, thereby simplifying connection lines (wires, nets).
必須加以強調的是,前述本案所揭示者乃為較佳實施例,舉凡局部之變更或修飾而源於本案之技術思想而為熟習該項技藝之人所易於推知者,俱不脫本案之專利權範疇。It must be emphasized that the aforementioned disclosure in this case is a preferred embodiment, and any part of the modification or modification that originates from the technical idea of this case and is easily inferred by those who are familiar with the art, does not deviate from the patent of this case. Power category.
綜上所陳,本案無論目的、手段與功效,皆顯示其迥異於習知技術,且其首先發明合於實用,確實符合發明之專利要件,懇請 貴審查委員明察,並早日賜予專利俾嘉惠社會,是為至禱。In summary, regardless of the purpose, means and effects of this case, it shows that it is very different from the conventional technology, and its first invention is practical and practical, and it does meet the patent requirements of the invention. I urge your review committee to investigate and give the patent to the AirPlus as soon as possible. Society is for supreme prayer.
<本發明> S1 配置一第一查找表單元以對N1個所述奇數節點進行一左邊界預選作 業,以獲得一左邊界預選值,及配置一第二查找表單元以對N2個所述偶數節點進行一右邊界預選作業,以獲得一右邊界預選值 S2 配置一第三查找表單元以對該左邊界預選值與該右邊界預選值進行 一左邊界選取作業,以獲得一左邊界數值,及配置一第四查找表單元以對該左邊界預選值與該右邊界預選值進行一右邊界選取作業,以獲得一右邊界數值 S3 依該左邊界數值和該右邊界數值進行一個一維線性內插運算 S1a 進行四個預選頂點選取作業 S2a 進行四個頂點選取作業 S3a 進行一個二維線性內插運算 S1b 利用2^n個第一階層多工器電路對以n維排列的複數個內插節點進行 一預選頂點選取作業以產生2^n個預選頂點 S2b 利用一第二階層多工器電路對所述2^n個預選頂點進行一頂點選取作 業以產生2^n個頂點 S3b 依所述2^n個頂點進行一個n維線性內插運算 10 儲存單元 11 第一查找表單元 12 第二查找表單元 13 第三查找表單元 14 第四查找表單元 10a 儲存單元 11a 第一查找表單元 12a 第二查找表單元 13a 第三查找表單元 14a 第四查找表單元 15a 第五查找表單元 16a 第六查找表單元 17a 第七查找表單元 18a 第八查找表單元 100 訊處理裝置 110 處理器 120 多工器電路<The present invention> S1 A first lookup table unit is configured to perform a left border preselection operation on the N1 odd nodes to obtain a left border preselection value, and a second lookup table unit is configured to match the N2 even numbers The node performs a right boundary preselection operation to obtain a right boundary preselection value S2. A third lookup table unit is configured to perform a left boundary selection operation on the left boundary preselection value and the right boundary preselection value to obtain a left boundary value, And configure a fourth look-up table unit to perform a right boundary selection operation on the left boundary preselected value and the right boundary preselected value to obtain a right boundary value S3. According to the left boundary value and the right boundary value, perform a one-dimensional linear Interpolation S1a Perform four pre-selected vertex selection operations S2a Perform four vertex selection operations S3a Perform a two-dimensional linear interpolation operation S1b Use 2^n first-level multiplexer circuit pairs arranged in n dimensions The node performs a pre-selected vertex selection operation to generate 2^n pre-selected vertices S2b using a second-level multiplexer circuit to perform a vertex selection operation on the 2^n pre-selected vertices to generate 2^n vertex S3b according to the description 2 ^ n vertices interpolation
<習知> 1’ 4輸入查找表 11’ 暫存器 12’ 多工器<Xizhi> 1’ 4 input look-up table 11’ register 12’ register 12’ multiplexer
圖1為以17個內插節點進行一個習知一維線性內插作業的示意圖。 圖2繪示用以實現圖1之習知一維線性內插作業之一查找表架構圖。 圖3為以17x17個內插節點進行一個習知二維線性內插作業的示意圖。 圖4顯示本發明之可減少多工器數量的查找表配置方法之一實施例的流程圖。 圖5顯示利用圖4之方法建置的一個查找表模組的架構圖。 圖6顯示本發明之可減少多工器數量的查找表配置方法之另一實施例的流程圖。 圖7顯示利用圖6之方法建置的一個查找表模組的架構圖。 圖8為本發明之可減少多工器數量的查找表配置方法之又一實施例的流程圖。 圖9繪示本發明之資訊處理裝置之一實施例方塊圖。FIG. 1 is a schematic diagram of performing a conventional one-dimensional linear interpolation operation with 17 interpolation nodes. FIG. 2 shows a look-up table architecture for realizing the conventional one-dimensional linear interpolation operation of FIG. 1. FIG. 3 is a schematic diagram of performing a conventional two-dimensional linear interpolation operation with 17×17 interpolation nodes. FIG. 4 shows a flowchart of an embodiment of a lookup table configuration method that can reduce the number of multiplexers according to the present invention. FIG. 5 shows an architecture diagram of a lookup table module built by the method of FIG. 4. FIG. 6 shows a flowchart of another embodiment of a lookup table configuration method that can reduce the number of multiplexers of the present invention. FIG. 7 shows an architecture diagram of a look-up table module built using the method of FIG. 6. FIG. 8 is a flowchart of another embodiment of a lookup table configuration method that can reduce the number of multiplexers in the present invention. 9 is a block diagram of an embodiment of the information processing device of the present invention.
S1b 利用2^n個第一階層多工器電路對所述以n維排列的複數個內插節點進行一預選頂點選取作業以產生2^n個預選頂點 S2b 利用一第二階層多工器電路對所述2^n個預選頂點進行一頂點選取作業以產生2^n個頂點 S3b 依所述2^n個頂點進行一個n維線性內插運算S1b uses 2^n first-level multiplexer circuits to perform a preselected vertex selection operation on the plurality of n-dimensionally arranged interpolated nodes to generate 2^n preselected vertices S2b uses a second-level multiplexer circuit Perform a vertex selection operation on the 2^n preselected vertices to generate 2^n vertices S3b. Perform an n-dimensional linear interpolation operation according to the 2^n vertices
Claims (7)
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
TW107142549A TWI695250B (en) | 2018-11-28 | 2018-11-28 | Lookup table configuration method capable of reducing the number of multiplexers and information processing device using the same |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
TW107142549A TWI695250B (en) | 2018-11-28 | 2018-11-28 | Lookup table configuration method capable of reducing the number of multiplexers and information processing device using the same |
Publications (2)
Publication Number | Publication Date |
---|---|
TWI695250B true TWI695250B (en) | 2020-06-01 |
TW202020600A TW202020600A (en) | 2020-06-01 |
Family
ID=72175764
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
TW107142549A TWI695250B (en) | 2018-11-28 | 2018-11-28 | Lookup table configuration method capable of reducing the number of multiplexers and information processing device using the same |
Country Status (1)
Country | Link |
---|---|
TW (1) | TWI695250B (en) |
Citations (6)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US20030067973A1 (en) * | 2001-09-07 | 2003-04-10 | Samsung Electronics Co., Ltd. | Block interpolation filter structure using lookup table |
TW200515821A (en) * | 2003-10-23 | 2005-05-01 | Mediatek Inc | Highly integrated MPEG-4 video decoding unit and related decoding method |
US20050140438A1 (en) * | 2003-12-27 | 2005-06-30 | Ming-Lu Jin | Fast LUT predistorter for power amplifier |
US20130223565A1 (en) * | 2012-02-29 | 2013-08-29 | Crestcom, Inc. | Transmitter Linearized Using Look-Up Table With Unadaptable Data and Method Therefor |
TW201340601A (en) * | 2012-03-06 | 2013-10-01 | Soitec Silicon On Insulator | Multiplexer, look-up table and FPGA |
TW201729083A (en) * | 2015-10-15 | 2017-08-16 | 曼塔公司 | Logic block architecture for programmable gate array |
-
2018
- 2018-11-28 TW TW107142549A patent/TWI695250B/en active
Patent Citations (6)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US20030067973A1 (en) * | 2001-09-07 | 2003-04-10 | Samsung Electronics Co., Ltd. | Block interpolation filter structure using lookup table |
TW200515821A (en) * | 2003-10-23 | 2005-05-01 | Mediatek Inc | Highly integrated MPEG-4 video decoding unit and related decoding method |
US20050140438A1 (en) * | 2003-12-27 | 2005-06-30 | Ming-Lu Jin | Fast LUT predistorter for power amplifier |
US20130223565A1 (en) * | 2012-02-29 | 2013-08-29 | Crestcom, Inc. | Transmitter Linearized Using Look-Up Table With Unadaptable Data and Method Therefor |
TW201340601A (en) * | 2012-03-06 | 2013-10-01 | Soitec Silicon On Insulator | Multiplexer, look-up table and FPGA |
TW201729083A (en) * | 2015-10-15 | 2017-08-16 | 曼塔公司 | Logic block architecture for programmable gate array |
Also Published As
Publication number | Publication date |
---|---|
TW202020600A (en) | 2020-06-01 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
JP2015513837A (en) | Parallel scaler processing | |
US7742636B2 (en) | Method and apparatus for scaling down a bayer domain image | |
US10402196B2 (en) | Multi-dimensional sliding window operation for a vector processor, including dividing a filter into a plurality of patterns for selecting data elements from a plurality of input registers and performing calculations in parallel using groups of the data elements and coefficients | |
KR20190029433A (en) | Electronic display border gain systems and methods | |
JP2004192110A (en) | Semiconductor device and image data processor | |
WO2000033194A1 (en) | Address generating device and moving vector detecting device | |
JP2002304624A (en) | Filter processor and imaging device | |
TWI695250B (en) | Lookup table configuration method capable of reducing the number of multiplexers and information processing device using the same | |
US6380987B1 (en) | Motion vector detection circuit enabling high-speed search of motion vector | |
JP2013132002A (en) | Image processing apparatus | |
JP5865696B2 (en) | Image processing device | |
JP2011509455A (en) | End-oriented image processing | |
JP2001285745A (en) | Image synthesizer and image synthesizing method | |
US7996657B2 (en) | Reconfigurable computing circuit | |
JP2009175861A (en) | Value selection circuit | |
US20050010742A1 (en) | Multimedia address generator | |
JP6467940B2 (en) | Image processing apparatus, image processing method, and program | |
Chao et al. | Pyramid architecture for 3840 x 2160 quad full high definition 30 frames/s video acquisition | |
KR100620008B1 (en) | Hierarchical image searching method for mobile communication terminal | |
US9330438B1 (en) | High performance warp correction in two-dimensional images | |
JPS6382530A (en) | Semiconductor storage device | |
JP2008278442A (en) | Image processor | |
JP3366033B2 (en) | Address conversion circuit and orthogonal conversion circuit having the same | |
JPH06197222A (en) | Image processor | |
US8804850B1 (en) | System and method to execute a clipping instruction |