JPH03237887A - Dct processor unit - Google Patents

Abstract

PURPOSE:To make a linear DCT (discrete cosine transformation) processing complete by dividing a bit length into specific bit length sets, executing the calculation of partial product in parallel depending on the bit length and executing the sum of intermediate results finally. CONSTITUTION:The DCT processor is provided with a 14-bit picture signal input u(j)2, 14-bit data registers 3-10 and 14-bit picture signal {u(n=mod(j)s), m=0-7} 11-18. Bit serial arithmetic sections 19-22 employ shift registers to apply addition and subtraction in bit serial. An M-bit length is divided into L bit length sets to satisfy the relation of L<N, the calculation of partial product is executed in parallel in the L bit length and the intermediate results are added finally. Thus, in the case of N=8, J=2, 8X1 linear DCT processing is realized for a period of 8 sampling clocks and the accuracy of the internal arithmetic operation is ensured up to the accuracy of M=14-bit without use of a multiplier.

Description

DETAILED DESCRIPTION OF THE INVENTION Industrial Fields of Application The present invention is applicable to videoconferencing systems.The 64 bits per second image codec processing system is being used for standardization work by the CCITT for video telephony video bandwidth compression.
CT (Discrete Co51ne Tran)
sfora (discrete cosine transform) processing device Conventional technology When performing DCT on an M×NIf element block in which one pixel data has a length of M bits, the data access period of N pixels is different from the case of filter processing, etc. Among them, there is an advantage that processing in the -dimensional direction only needs to be completed. Taking advantage of this advantage, there is a method to perform bit-serial calculation processing. As a fractional type calculation method, for example, I. Transaction Acoustic Speech, Signa/k Processing Volume 22 (
December 1974), pages 456 to 462 (IE
E E Trans, Ac.

ustic, 5peech, Signal Proc
essing vol, ASSP=22゜pp, 45
6-462. Dec. 1974 A new har
dware realization of digi
tal filters,'by A, Pe1ed a
nd B, Li.

Although this processing method was published in
The final result is obtained by applying 11 digit corrections and adding them.4 When this method is applied to DCT processing, the result is as follows.ゎ-1 N integer data string (u(n)-Σa+ (n)2'
, an-+ (n)--■ [0,-1], (at (n) (0,1, 0≦i≦
One-dimensional DCI friend for 12,0≦n≦N-1))
This formula can be expressed as formulas (1-1) to (1-3), and when summarized by addition regarding i, as in the following formula, 0≦≦N-1 (1-5) Formula (1-5), the data in brackets ()''Q,
at(n) can be prepared with 1-bit data of 0 or 1 or O or -1, so it is written in square brackets (1172 α(0)-(> (1-2) 2 1'). α(k)-(-), O≦≦N-1 (1-3) Substituting the exponential expression of u(n) into the above equation (1-1), it can be written as equation (1-4). It can also be executed using only addition and subtraction without using arithmetic.
Even though it has the advantage of being able to reduce the chip size when implemented using an integrated circuit compared to using parallel multipliers, in addition, if the DCTO field is an even number, A N-2N
', the equation (1-5> can be written as below.If we transform the second term C05(・) in the above equation, we get Equation (1-8), (1-9 ) and transform equation (1-7) with an even term and an odd term for k, we get ν(2 ni')
-Σ21(Σ(at (n)+a+ (2N' -1-
11) ) (Z (to 2') cos snow・n・− to −2′ +1.0≦°≦N°Similarly when −1, to −2′ +1. O≦′≦N′ −1, using equations (1-10) and (1-11), and using the symmetry of the DCT transformation kernel cos[π (2n+1)k], α(k)cos capacity (as one 2111/I for k from word
I don't know how much money I can save.
(a, (n)+a+ (2N'-1-n)) or (a+
(n)-a+ (2N'-1-n)) term, carry and borrow occur, so the number of additions for i is (M
+1) times In this way, this calculation method can save ROM capacity by using the symmetry of the DCT transformation kernel while converting the operations in square brackets () to the DCT.
The operations themselves can be performed using only addition and subtraction without using multiplication.These characteristics have the advantage that the chip size can be made smaller when implemented using integrated circuits compared to when parallel multipliers are used. However, the problem to be solved by the invention is as follows: Assuming that the sampling time of 1\A element is one basic clock period, there is a synchronous system that can perform one addition process and one ROM access in this one clock period. Assuming that, if the bit length M#tDCT is larger than the processing unit N, this means that the processing on ζ will not be completed. ! Nails that are not a problem in cases of N-16 or higher Standardization work is being carried out by CCITT6
N- used in image codec processing at 4 bits per second
In the case of a DCT of 8 bits, there is a problem that sufficient accuracy cannot be obtained in the intermediate processing section, which is limited to M≦8 bits.1. The present invention takes into consideration this point - LM>N
Nx1 with a period of N sampling clocks with bit precision
The object of the present invention is to provide an N×N DCT processing device that completes one-dimensional DCT processing at a low cost. It has a structure in which the M bit length is divided into L bit lengths satisfying L<N, partial product operations are executed in parallel with L-L bit lengths, and finally the intermediate results are added. According to the present invention, with the above-described configuration, when partial product operations are executed in parallel with a length of L bits, intermediate sums are generated in parallel, so that the operations are executed at high speed.
Even if the DCT processing unit N is larger than the processing unit N of the DCT, the processing is completed in a period of N sampling clocks. An 8×1 one-dimensional D for a 14-bit image signal u(j) in one embodiment
In the block diagram of the CT processing device, 2 is 14.
11-18 are 14-bit image signals [u(n=mod(j)*), m-0-7) and 19 .about.22 is a bit-serial calculation unit that performs bit-serial addition and subtraction using a shift register. 23 to 38 are bit serial calculation units 19 to 22
The signals 39 to 42 are each 1-bit signal which is the result of the bit serial operation of Takes 4-bit data as address information,
, generate partial products of multiplication of coefficients and data by ROM.
It is a coefficient multiplication unit consisting of a ROM and an adder that performs cumulative addition by shifting the value to the left; 4o47 to 54 are 8×1
The 33-bit output 4 words (ν(k)
, k-0 to k-7) and 55 to 62 are 33-bit tri-state drivers, which perform parallel/serial conversion of output data. 63 is the 33-bit signal output time-series by the operation of 55-62 of the 33-bit tri-state driver. The 14-bit image signal u(n), 66 is the 14-bit image signal u(7-n
) and 7)c, 67.68 is a 14-bit right shifter with a data load function in which the upper 7 bits and lower 7 bits are independent, and performs bit-by-bit processing necessary for bit serial operation. 69.70 is 1 bit total addition! 7
1.72 is a 1-bit full subtractor, and mores 3 to 76 are 1-bit data latch blocks, a carry generated by the operation in the 1-bit full adder 69, and 70, and a 1-bit full subtractor 71.
The signals 77 to 80 that hold the borrow generated in the operation at 72 are each 1-bit operation result signals, and are used as address information when reading out the partial product of multiplication with a coefficient from the ROM. Figure 1 is a circuit diagram of the coefficient multipliers 43 to 46 using the ROM and the adder. Figures 82 to 85 are 4-bit data each serving as address information when reading out the partial product of multiplication with a coefficient from the ROM. 86 to 89 are 16 word x 18 bit capacity. ROK 90 to 93 are 26 bit full adders that generate partial products for multiplication with coefficients. 94 to 97 are 26 bit right shifters with data loading function.
．． 99 is a 33-bit full adder, 100.101 is a 33-bit register, and 102 is a 33-bit output signal ν (2).
), 103 is a 33-bit output signal ν (2 + 1).The operation of 8×1 one-dimensional DCT processing will be explained using FIGS. One pixel data with LLM>8 bit length is divided into L bit length data and processing is executed. For example, if M bit length data is divided into three L bit length data, the formula (1
−5) can be transformed as follows: 2π(2n+1)k ν(k)−Σ21(Σat(n)α(k)cos []
) - 1 inside ° - 2N The above equation is calculated by the sum of 3 subterms. This means that each subterm is executed by L additions, which requires 4L addition times and 3 terms. Total time to add 75t N
For example, if the sampling time is shorter than the data sampling time of N-8, J-2, the desired high-speed processing can be achieved.
Consider the case of 8≧trune(M/2+0.5)+1;trune
(-) Round down (1-13), so M≦14.
, the formula (1-12
), applying equations (1-10) and (1-11), equations (1-14) and (1-15) are obtained, and -2',
When 0≦′≦3・1 y(2′)−Σ2′(Σ(a+(n)10a+(7−n
)) α(to 2')cosl-@*-・2π(2n+1)k' [-1), O≦to'≦3to-2'+1. When O≦′≦3 (1-14) ν (2′+1)−Σ2 −I (Σ(a+ (n)−a+ (7−n)) a (2′+1) cosonic structure By using the groove bottom, M-1
It is possible to realize 8xl one-dimensional DCT processing with 4-bit precision and an 8-pixel sampling clock period. Since the signal force u(j)2 is subjected to DCT processing on a subset of 8 pixels, 6 14
Bit registers 3 to 10 [u(n), n
-mod(j)s, O≦n≦7) and is held in 14-bit registers 3 to 10 (these eight subset data strings (u(n), 0≦n≦7) are completely Until the data is updated, one shift operation is performed for one data sampling (＼ Data is sent sequentially.

In other words, every 8 data samplings, a new subset data count <, u(
7),..., even if set as u(0), then
This data is supplied to the bit serial calculation units 19 to 22 via the upper 14 bit signal lines 11 to 18, respectively.The processing in the bit serial calculation units 19 to 22 will be explained with reference to FIG. Bit image input 65~
661 Upper Data entry from any of the 14-bit registers 3 to 10 in Figure 1 is expressed using two's complement representation (a
+*(7-n)ε[0,-1, at(7-n)E[0
, 1], 0≦i≦ 12. O≦n≦3) These data lengths: Right shifter 67 with a 14-bit data load function where the upper 7 bits and lower 7 bits are independent;
68, each seven bits are processed separately and right-shifted to the LSB side once every clock period. Right shifter 6 with data load function
7. Signals CL u(n) and u output from 68
2L for the upper 7 bits and lower 7 bits of (7-n)
The value of each 1 bit of the digit is al(n) and at・〒(n)
and at(7-n) and a+*y(7-1) With these signals, in the 1-bit full adder 69.70 and the 1-bit full subtracter 71.72, the formula (1-14) The carries and borrows generated by these operations are held in 1-bit latches 73 to 76, and are used for the operation one clock later, so that the original 1
Bit full adder 69. To and 1-bit full subtractor 71.
1-bit full adder 69.7
The operation result of 0 (outputted to the 1-bit data lines 77 and 78, respectively, and the operation result of the 1-bit full subtracter 71, 72 outputted to the 1-bit data line 79, 80, respectively) is the same as explained in FIG. Similarly, bit serial operation section 19.2
2, (y) (a+◆ma(n)+a+-7(7-n>), (at (n)+a+) on the right side of equation (1-4L(1-5))
(7-n)), ((aly(n)-a-7(7-n)
), (at (n)-at (7-n)) are executed, and the bit serial calculation unit 19 calculates u(0) and u(7
), the bit serial calculation unit 20 calculates u(1) and u(6), and the bit serial calculation unit 21 calculates u(
2) and u(5), the bit serial calculation unit 22 executes this calculation for u(3) and u(4).
4-bit data lines 39 to 424 output from each bit serial calculation unit 19 to 22; L4 bit data line 39 is ((a+*〒(n)+a+◆v(7-n))
, rro, 1.2.3) L4 bit data line 40
is ((at (n)+a+ (7-n)), n-0,1
, 2, 3).The LA 4-bit data line 41 indicates ((at
-v(n)-a+◆y(7-n)), n-0,1,2°3), and the 4-bit data line 42 shows ((at (n)
-at (7-n)), n-0, 1, 2, 3) respectively. 1
Returning to 5), equation (1-14) and equation (1-
Expanding the sum part with respect to n in 15), it can be expressed as follows: -2', O≦°≦3
When k-2k''+1, when 0≦′≦3, 0≦k”≦3 (1-17) δ, 0≦′≦3 (1-16) Thus, the above equation (1-16 ) for each 2L digit, fix K' and write gi ((at-v(n)
4-bit data of +a+-y(7-n)), n-0, 1, 2, 3) and ((at (n)+a+(7-n)),
It can be uniquely determined by the 4-bit data of n-0, 1, 2, 3), and the same holds true for equation (1-17).Therefore, these 4-bit signals can be used as address information. It is not easy to determine the address information.
In this way, the 4-bit data on the 4-bit data line 39 (
From the 2197th digit in formula (1-14) h ROM
Similarly, 2''' 7 digits (Σ(a+*〒(n)-a+-y (7
Similarly, the 4-bit data on the 4-bit data line 42 is input to the coefficient multipliers 43 to 46 using the h ROM and the adder. Coefficient multiplier 4 by
Next, the processing in the coefficient multipliers 43 to 46 by the ROM and adder will be explained using FIG. 3. In FIG. -14) 21+? digit, (,4(a
+Used as the desired address information t''t Also input to the coefficient multipliers 43 to 46 by the ROM and adder.Similarly, the pit data line 41-4 is the address information sought by the formula, and is input via the 4-bit data line 39. Similarly, the 4-bit signal line 83C type (1-
(Σ(a+(n)+a+(7-n))α16 in 2+ digits in 14)
Similarly, if a ROM 87 with a word x 18-bit capacity is input manually via a 4-bit data line 40 using i3 4 bits, the 4-bit signal 84
0yr (2n+1) (2 to ' +1) []) Even if input via the 4-bit data line 41, the 4-bit signal 85 (the 2-digit value in the above equation (1-15)) is inputted via the 4-bit data line 41. Similarly, a ROM88 with a capacity of 16 words x 18 bits outputs a 4-bit signal 84 all at once.Similarly, a ROM89 with a capacity of 18 words x 18 bits sends a 4-bit signal 85 to an address π(
2n+1) (2 to '+1) []) Even if it is input via the 4-bit data line 42, the ROM 86, which has a capacity of 167-bits and 18-bits, receives the 4-bit signal 82 as the address information ( Σ(a+◆ma(n)+a+◆te value is output as 18-bit data. Next, 26-bit full adders 90 to 93 and 26-bit full adders 90 to 93,
BIT's right shifter with data load function 94-97
(Table 4 functions as a 26-bit cumulative adder, and the R
18-bit output data from OM86 to 89 (friend 2
MSB side 1 of one input of 6-bit full adders 90 to 93
8 bits input to 7, 26 bit full adder 90-9
The addition result ζ in step 3 is shifted by 1 bit to the LSB side (to the right) by right shifters 94 to 97, each with a 26-bit data loading function.
However, in this operation, when I-O, 26-bit data load function shifters 94-97 on ζ are added to 26-bit full adders 90-93.
Although the data input to the input terminal is initialized to 0'', this operation allows the expressions (1-14) and (1-1
5) are calculated by the 33-bit full adders 98 to 99 (the outputs of the upper 26-bit shifters 94 to 97 are added together).
The output of is corrected by 27 at the time of addition and becomes the formula (1-14
), (1-15) ν(2' ), (2' +1)
Calculate the value of a and the 33-bit register 100
．． l0IE, the result of the operation is set in the 33-bit register 100.101 for the next 8 clocks.
) is calculated, hold the current value. Now return to Figure 1 and continue the explanation.
Data 102 from 3-bit registers 100, 101
．． 103i, which corresponds to 47 to 54 in Fig. 1, and together with the output signals of the other three blocks, the DCT processed signal sequence (ν(k), 0≦to≦7) and this 33
Bit output signal sequence (ν(k).

0≦ and ≦7) are each tri-state driver 55
FIG. 4 shows the adaptive D according to an embodiment of the present invention.
This figure shows the general configuration of the CT processing device, in which a104 is a control signal input terminal, 105 is a data strobe signal input terminal, 106 is a 14-bit image signal input terminal, and 107 is a 1-bit image signal input terminal.
4-bit reference image signal input terminal, 108 is a subtractor 10
9 is the clipping time [110 is 8×1 one-dimensional DCT
Timing signal generation section 112 for processing circuit 111
The same area 113 controls the writing to the 128 word x 16 bit dual port memory 114. The area 115 controls the reading from the dual port memory 114. The area 116 shows the 8x1 one-dimensional DCT.
Timing signal generation time j for the processing circuit 117! 1
118 is clipping/rounding processing; 119 is 14
Even if it is a bit image output terminal, Figure 4 shows the 8x1 of Figure 1.
This is an example of an 8x8 adaptive DCT processing device using the DCT processing circuit block of 6. In the case where adaptive processing is performed using the control signal 104, the subtractor 108 inputs the 14-bit image signal 106 and the 14-bit reference image signal. If the resulting signal exceeds the assumed maximum and minimum thresholds, it is clipped by the clipping circuit 109, tN, 8X1.
If the signal is not clipped even if it is input to the one-dimensional DCT processing circuit 111, the signal from the subtractor 108 is passed through, and is manually input to the 8×1 one-dimensional DCT processing circuit 111, where it is subjected to 8×1 DCT processing. and the processing timing in the 18xl one-dimensional DCT processing circuit 111 (
A set of 14-bit image signals input from the data strobe signal input terminal 105 and a set 6 input from the input terminal 106
The timing signal generation circuit 110 is triggered by a strobe signal indicating the first signal of the four digital image signals.
Next, the clipping/rounding processing circuit 112 is controlled by the 8×1 one-dimensional DCT processing circuit 11.
Clipping and rounding processing is performed on the processing output from 1, and the result is input to the 128 word x 16 bit dual port memory 114.
When writing and reading the bit dual port memory 114, it is controlled by the write control circuit 11a and the read control circuit 115.Next, the 8X1 one-dimensional DC
The T processing circuit 117 performs DCT processing on the input signal from the 128 word x 16 bit dual port memory 114, and the processing timing here is controlled by the timing signal generation circuit 116. The output data floor from 117 is output to a 14-bit image output terminal 119 through a clipping/rounding processing circuit 118, and two-dimensional 8×8 DCT processing is completed, but in this embodiment, one pixel data has a length of 14 bits. Even if you divide the M-bit length into a L-bit-long signal that satisfies the force <, M>N of dividing the signal into 2 into a 7-bit-long signal (however, L
As explained above, according to the present invention, the ζCM bit length can be reduced to L.
> N=8. By dividing the partial product into L bit lengths satisfying N, the partial product operation is executed in parallel with LL bit length, and finally the intermediate results are added. When J=2, 8×1 one-dimensional DC in 8 sampling clock periods
It is possible to realize T processing and the internal calculation accuracy is M =
Accuracy up to 14 bits can be secured without using a multiplier, and its practical effect is 1.

[Brief explanation of drawings]

FIG. 1 shows an 8×1 one-dimensional D
Blocks of the CT processing circuit & Figure 2 shows the circuit configuration of the bit serial operation section. Figure 3 shows the circuit configuration of the coefficient multiplication section using ROM and an adder. Figure 4 shows the circuit configuration of the adaptive DCT processing circuit according to an embodiment of the present invention. In the schematic configuration diagram, 2...Image signal input 9 3-10...Data reception 19-22...Bit serial operation 43-
46...Coefficient multiplication by ROM and adder @ 11
1,117...8Xl one-dimensional DCT processing speed 11
4...Dual port memory.

Claims (2)

[Claims] (1) In DCT processing used for band compression of image signals, a signal of M bit length is converted to DC in a processing unit of N×N pixels.
When performing T processing, when the relationship M>N holds, M
Divide the bit length into L-bit length signals that satisfy L<N, perform the calculation of partial products of each L-bit length in a bit-serial manner using an adder and ROM, and finally calculate the results of these operations. A DCT processing device characterized in that by performing addition, N×1 one-dimensional DCT processing of M bit length is completed in N sampling clock periods. (2) N×N of M bit length characterized by using two N×1 one-dimensional DCT processing devices of M bit length and a dual port memory for converting the scanning direction of the data string.
Two-dimensional DCT processing device.