Discrete cosine converting device

[Detailed Description of the Invention]

[Objects of the Invention] (Field of the Invention) This invention relates to the simple discrete cosine transform device in which pipeline processing is possible. (PRIOR ART) As a discrete cosine transform unit in which the conventional pipeline processing is possible, there is U.S. Pat. No. 4,385,363 (May 24 *1983). This performs the 16th cosine transform according to the operation expressed by a signal flow chart showing in Drawing 14. It is a block circuit diagram showing in Drawing 15. Here, basic arithmetic unit A is constituted by the circuit which memorizes input data temporarily, and the circuit added or subtracted. Basic arithmetic unit C is constituted by the circuit which memorizes input data temporarily, two multiplication circuits, and the circuit which adds or subtracts this multiplication result. That is, the device which uses four multiplication circuits was performing the 16th cosine transform conventionally. In order to perform inverse transform, as shown in Drawing 16, basic arithmetic unit A of the first rank of Drawing 15 must be used as basic arithmetic unit c which switches an arithmetic circuit or includes two multiplication circuits. Thus, the hard scale became very big, when at least four multiplication circuits and the change circuit of input and output of a basic arithmetic unit were needed and operation accuracy was made high, in order to perform the 16th cosine transform and inverse transform conventionally. The conversion degree was decided less than as the 16th order from a point of operation accuracy, a middle buffer memory, or a multiplier memory. (Object of the Invention) As mentioned above, when making operation accuracy high in prior art, the hard scale of an arithmetic circuit etc. had a fault used as a very big thing. Then, an object of this invention is to provide the discrete cosine transform device for which the operating efficiency of a multiplication circuit does not need many multiplication circuits well, the same composition may be used for conversion, inverse transform, and circuit composition, and they moreover do not need the change circuit of input and output of a basic arithmetic unit. It is also possible to unite, to use a middle buffer memory as multiplier RAM, to use a butterfly adding machine as an accumulation adding machine to make a procession arithmetic circuit, and to expand a conversion degree. [Elements of the Invention] (Means for solving problem) Basic arithmetic unit A constituted by circuit which memorizes input data temporarily, and adds or subtracts an operation of this invention and the 21141st discrete cosine transform Basic arithmetic unit B constituted by circuit which memorizes input data temporarily, and adds or subtracts a multiplication result below the number of input data and the same number is used, n step Cascade connection is made, a circuit which made Cascade connection of basic arithmetic circuit B and the basic arithmetic circuit A for basic arithmetic circuit A after that at the first rank is constituted, and it is because a signal flow chart according to a value of n shown in Drawing 1 is calculated. In an operation of inverse transform, it is the same circuit composition as the time of conversion, and is because a flow chart contrary to a signal flow chart according to a value of N shown in Drawing 1 is calculated. However, basic arithmetic circuit A of the first rank and a final stage at least has a function which outputs input data as it is. (OPERATION) Since conversion and inverse transform become the completely same circuit composition as mentioned above, the present invention can perform a change of conversion and inverse transform very easily. About a stage which multiplies, since it is the number of times of multiplication below the number of input data, and the same number, pipeline processing is possible at one multiplier. That is, since the 21141st conversion and inverse transform can be performed with n multipliers, hardware can be simplified very much. (EXAMPLE) Hereinafter, an example of the present invention is explained in full detail with reference to drawings. Here, it is assumed that the Nth discrete cosine transform and a discrete reverse cosine transform are defined by following formula. however, -1+J = Op L ... and N-1f(i):F(1): Original Drawing 1 of data by which data (or data by which inverse transform was carried out) conversion was carried out shows a signal flow chart of an example of the present invention in the 32nd discrete cosine transform. A block diagram which performs conversion according to this is shown in Drawing 2. 5TAGE of Drawing 1 and 5TAGE of Drawing 2 correspond. Five TAGE(s) each of an odd number are basic arithmetic circuits A, and show this example in Drawing 3. Inside A1 of a figure is a memory for pipelines who memorize input data All temporarily. An order read from this memory A1 can be changed with an order of having been inputted, by an order to calculate. Data latch A2.A3.A4 changes data read every 1 word per 2 A 1 Do. Numerals reversal machine A5 is inputted into addition-and-subtraction stop circuit A7, without reversing numerals of output data of data latch A4, when data of addition-and-subtraction selection signal A51 is a high level (1), and reversing numerals of output data of data latch A4, when data of an addition-and-subtraction selection signal is a low level (zero). When data of addition-and-subtraction stop selection signal A61 of addition-and-subtraction stop circuit A6 is a high level (1), Output data of data latch A3 is inputted into adding machine A8 as it is, and when data of addition-and-subtraction stop selection signal 61 is a low level (zero), all output data of data latch A3 is made into zero, and is inputted into adding machine A8. When data of addition-and-subtraction stop selection signal A71 is a low level, addition-and-subtraction stop circuit A7 reverses output data of numerals reversal machine A5, is inputted into adding machine A8, when data of addition-and-subtraction stop selection signal A71 is a high level, makes zero all output data of numerals reversal machine A5, and is inputted into adding machine A8. When data of addition-and-subtraction stop selection signal A71 is a low level and Datta of addition-and-subtraction stop selection signal A71 is a high level as it is about data of addition-and-subtraction selection signal A51, addition-and-subtraction stop circuit A70 makes zero data of addition-and-subtraction selection signal A51, and inputs it into a carry input terminal of adding machine A8. Therefore, when addition-and-subtraction stop selection signal A61 is a high level and A71 is a low level, If data of addition-and-subtraction selection signal A51 is high level alpha, addition of output data of data latch A3 and output data of data latch A4 will be performed, If data of addition-and-subtraction selection signal A51 is zero, subtraction of output data of data latch A4 will be performed from output data of data latch A3. If data of addition-and-subtraction stop selection signals 61 and 71 is a high level, from adding machine A8, output data of data latch A3 will be outputted as it is. If data of addition-and-subtraction stop selection signals 61 and 71 is [ data of addition-and-subtraction selection signal 51 ] a high level on a low level, from adding machine A8, output data of data latch A4 will be outputted as it is. That is, an operation of all the 5TAGE of an odd number of Drawing 1 can be performed with this basic arithmetic unit A. Next, an example of basic arithmetic circuit B used for five TAGE(s) each of an even number of Drawing 2 is shown in Drawing 4. 81 in a figure is a memory for pipelines who memorize input data B101 temporarily. This memory B1 can change a To read order with an order of having been inputted, as well as the above-mentioned memory At. Data latch B-2 and B3 latch data read from memory B1 every l words once per 4 words. Data latch B4 latches data read from memory B1 every 1 word twice per 4 words. Selector B5 inputs into multiplier B7 by turns data outputted from data latch B-2 and 83. Multiplier memory 818 has an address controlled by system controller S, and inputs multiplier data into multiplier B7 via data latch B6. Data latch B8.B9.BIO, numerals reversal machine Bll, and addition-and-subtraction stop circuit B12.813.B130, The same operation as the above-mentioned basic arithmetic circuit A is performed, and addition and subtraction of output data of data latch B9 and output data of data latch 816 are performed by addition-and-subtraction selection signal B 111. Output data of data latch A3 and output data of data latch 816 can be outputted from adding machine B14 as it is by addition-and-subtraction stop selection signal B121 or B131. Selector B17 is outputted data which performed addition and subtraction of a multiplication result outputted from data latch 816, data through data latch B4 outputted from data latch B15, and by turns. Drawings 5 and 6 are timing charts which show basic Computing device[A and an example of basic arithmetic circuit B of operation which were mentioned above, respectively. If each multiplier memory 818 of 5TAGEn, 5TAGE■ and 5TAGErV, and 5TAGEVI has multiplier data of conversion and inverse transform as a common thing by a system of Drawing 2 here, A discrete cosine transform and its inverse transform can be performed only by address control of multiplier memory B18 or buffer memories A1 and B1, and change of an addition-and-subtraction stop selection signal. Even if it does not have multiplier data 2 times by five YAGE(s) each for conversion and inverse transform, conversion and inverse transform can be performed by switching a multiplier memory by 5TAGEII, 5TAGEVffi and 5TAGEIV, and 5TAGEVI. Although inverse transform makes it extra special, since this can be performed in a pit shift, there is no trouble in this system. although the 32nd conversion was described here -- 211+'' (n = 2, 3, ...) -- it is easily realizable also about the next conversion. It is T of Drawing 8 (a) to Drawing 7 (b) about a operator of K T r of Drawing 7 (a) as other examples! - A operator of - can be used as Drawing 8 (b). If these are applied to an algorithm as shown in Drawing 1 developed here, the number of times of multiplication will be made to a time (21og, N 1) to the Nth cosine transform. As for this, an algorithm of the number of times of the minimum multiplication known now and below the same number become, and when based on devices, such as DSP, it can perform very high-speed conversion. As explained above, when a discrete cosine transform device is constituted, Even if it makes variable a degree (in the case of this example 4th ~ 36th order) as shown in Drawing 1 since each stage has composition by which Cascade connection was made one by one in basic arithmetic circuit B including basic arithmetic circuit A which consists of addition or a subtraction circuit, or a multiplication circuit, it is satisfactory at all, An L character type circuit may be added to the 4th circuit one by one. Drawing 9 is a block diagram showing other examples. the inside of 1 figure which is what this can perform the 8th discrete cosine transform [ 8th / 16th / 32nd ] x its inverse transform, and also enables a procession operation up to the 64th order, and circuit BA are what combined basic arithmetic circuit B mentioned above and basic arithmetic circuit A -- the -- it is shown inO [ 1 ] figure. the -- be because lends and there is not any carrying out 1 bit shift of bit Shifter AIO and B20 in theta [ 1 ] figure -- twice -- it is chosen whether lends and there is any carrying out. Rounding-off circuit B21 is rounded off under number A bit rather than a decimal point. When circuit BA follows a high-speed algorithm of Drawing 1, Selector 10I inputs into data latch B-2, and B3 and B4 output data from memory B1 in which input data B101 was memorized temporarily, Selector 102 inputs output data from multiplier memory 818 into data latch B6, and selector 103 inputs output data of memory A1 into circuit ASsigma which works as a butterfly adding machine. And output data of bit Shifter AIO turns into high-speed operation output data, and is inputted into the next 5TAGE. Here, it is circuit ASsigma. It has become as it is shown in Drawing 11, and selector A14 inputs input data A13 into data latch A2. Operation of each part at this time is almost the same as being shown in Drawings 5 and 6. When performing the 8th cosine transform [ 8th ] x inverse transform in Drawing 9, Input data la prepares an order of data outputted in buffer memory 9 via circuit BA of 4 and 5 via selector 8 via basic arithmetic circuit A via selector 7 via circuit BA of 2 and 3 via one basic arithmetic circuit A, and is outputted via selector 10. A point of differing from the 8th time [ 8th ] x at the time of the 16th cosine transform [ 32nd ] and its inverse transform is a point that an output of circuit BA of 3 is inputted into circuit BA of 4 via selector 8. At the time of the 16th cosine transform, circuit BA of 2 inputs input data into circuit BA of 3 as it is, and circuit BA of 5 inputs input data into buffer memory 9 as it is at the time of the 16th reverse cosine transform. A multiplier memory of each circuit BA can be saved by using this appearance. Here, as for about 1 Do of 32 A, memories aluminum and Bl and buffer memory 9 which memorize input data temporarily are prepared at a time except for a thing of basic arithmetic circuit A of 6. As for about 1 Do of 64 A, memory A1 used for basic arithmetic circuit A of 6 is prepared in order to work as 8th memory [ 8th ] for transposition x. Next, how to operate a circuit shown in Drawing 9 as a procession arithmetic circuit is explained. At this time, input data la is inputted into basic arithmetic circuit A of 6 via selector 7. At the time of conversion, butterfly addition is carried out in this basic arithmetic circuit A, and it is inputted into input terminal BA21 for a procession operation of each circuit BA of 2~5 via selector 8. At the time of inverse transform, even if it carries out butterfly addition in basic arithmetic circuit A of 6 and does not carry out, it can calculate similarly. Here, it is in memories A1 and B1 of each circuit BA, passing along a signal wire for a high-speed operation -- a multiplier for a procession operation -- a passage -- beforehand -- memorizing -- having -- After -- each -- two data is outputted by time sharing among the 64th conversion data, and eight data is further outputted [ from circuit BA ] via selector 10 in selector 11~13 by time sharing in it. That is, if eight circuits of Drawing 9 are used, an operation of the 64th discrete cosine transform is possible. Drawings 12 and 13 are timing charts which show an example of operation when performing the 64th cosine transform and inverse transform by making into a procession arithmetic circuit a circuit shown with a block diagram of Drawing 9. Even if compared with a timing chart of these figures, Drawings 5, and Drawings 6, it turns out that a portion which needs to change operation a lot is very small. Therefore, simple composition may be sufficient also as a control circuit, and it can perform easily a change with this procession operation and high-speed operation. [Effect of the Invention] In order to base this invention on the new high-speed arithmetic algorithm of Drawing 1, arrangement of a basic arithmetic circuit completely becomes the same by that inverse transform about a discrete cosine transform. And in order that the number of the basic arithmetic circuits which need a multiplier may be n to a 2fl+1 order discrete cosine transform and those basic arithmetic circuits may just perform the multiplication below the number of input data, Since [ this ] it may have at least one multiplier, respectively, the pipeline processing of a discrete cosine transform and its inverse transform can be carried out in a very simple circuit.

[Brief Description of the Drawings]

Drawing 1 is a signal flow chart showing the new high-speed arithmetic algorithm used for the example of this invention, The figure and Drawings 3 and 4 in which Drawing 2 shows the example of this invention are figures for describing an example, The timing chart and Drawings 7 and 8 in which Drawings 5 and 6 show the example of a circuit of operation are figures showing a means to further decrease the number of times of multiplication of a high-speed arithmetic algorithm, the [ the figure showing the example of everything / Drawing / 9 / but this invention, and ] -- a figure forO [ 1 ] figure and Drawing 11 to illustrate the example of Drawing 9, The timing chart Drawings 12 and 13 indicate the example of Drawings 10 and 11 of operation to be, The signal flow chart showing the high-speed arithmetic algorithm of the former [ Drawing / 14 ], the figure showing the example of the former [ Drawing / 15 ], and Drawing 16 are figures showing a way stage for using the cosine transform device by the conventional high-speed operation as an electronic power inverter. A: The basic arithmetic circuit which memorizes input data temporarily and performs addition or subtraction B: The circuit S NicheStem controller which memorizes input data temporarily and performs addition or subtraction for the multiplication result below the number of input data