KR20000031963A - Half-band subband dct/idct circuit using rac - Google Patents

Abstract

PURPOSE: A half-band sub band DCT/IDCT(discrete cosine transform/inverse discrete cosine transform) circuit using RAC(ROM and Accumulator in cascade) is provided to utilize the DCT having the same size in both of forward and backward directions, thereby enhancing the efficiency of hardware. CONSTITUTION: A half-band sub band DCT/IDCT circuit using RAC comprises a multiplexor(100), an SPC(serial-to-parallel converter; 200), three RACs(300), a butterfly unit(400) and a pre-memory(500). The multiplexor(100) selectively receives input and the output of the pre-memory(500). The SPC(200) consists of 8 resistors(201) and serially receives the image inputs from the multiplexor(100) to parallel output them. The RAC(300) receives parallel data from the SPC(200) to execute half-band sub band DCT. The butterfly unit(400) consists of 8 resistors(401) and one adder-subtracter(430) to execute a butterfly network function.

Description

Half-Band Subband DC / IDC Circuit Using ALC and Its Method

The present invention relates to an 8x8 DCT / IDCT (Discrete Cosine Transform / Inverse Discrete Cosine Transform) circuit using an algorithm and a structure that can be efficiently used in a low-rate imaging system.

In general, in applications requiring image compression, the signal spectrum of the input image has almost all of the energy in a particular frequency band and the energy of other portions can be almost negligible. In this case, it is possible to innovatively reduce the amount of calculation by performing only the calculation of the energy-intensive subbands and not the remaining bands.

There is a new DCT algorithm called subband DCT that enables higher quality transmission with less computational demand in low-rate video signal systems.

FIG. 1 is a block diagram illustrating a conventional two-band subband DCT circuit. As shown in FIG. 1, a subband decomposition unit (N) receiving an N-point input sample X (n) is shown. 1) generates an N / 2-point lower band sample (X _L ) and an N / 2-point upper band sample (X _H ) from the input sample X (n), and generates the N / 2-point lower band. Sample (X _L ) is in N / 2-point DCT (2), and the N / 2-point upper band sample (X _H ) is in N / 2-point Discrete Sine Transform (DST) 3 respectively. Perform The result of the DCT and DST is input to a weighting network 4, and the result C (k) of the final N-point DCT is output.

The great advantage of this subband DCT is that N-point DCT can be expressed as smaller size DCT and DST to reduce the amount of computation required, and the approximation method of DCT, which is useful for image compression, is introduced by introducing the concept of subband. You can do it.

If most of the energy in the video signal is concentrated in the low frequency range, the calculations for no high-pass band calculations are nearly equal to the calculations required to perform N / 2-point DCT. This calculation of DCT is called half-band subband DCT.

2 is a block diagram for performing a conventional half-band subband DCT.

The N-point input sample X (n) is input to generate an N / 2-point lower band sample (X _L ) from the input sample X (n) through a subband decomposition unit 21, and the N / 2- The point lowerband sample (X _L ) performs DCT at N / 2-point DCT 22. The result of the DCT is input to the weighting network 23, and the result C (k) of the final N-point DCT is output.

When the half-band subband DCT configured as described above is implemented in hardware, it is necessary to solve the problem that the size of the DCT actually used is different in the forward and reverse directions. That is, when N = 8, 4-point DCT should be performed in the forward direction, but 8-point IDCT should be performed in the reverse direction. This problem does not occur when the forward DCT and the reverse DCT are performed as independent modules, but in this case, the hardware efficiency is extremely degraded.

In the present invention, the problem of the size of the DCT as described above is to be solved by using the same size of the DCT in both the forward and reverse directions. In other words, the 8-point IDCT is performed by using two RACs, respectively, so that the forward 4-point DCT and the 8-point IDCT can be processed by one device.

Using the same sized DCT for both forward and reverse DCTs creates the possibility of repeating the same hardware. That is, the hardware module used for the 4-point DCT can be used in the reverse direction. In addition, if the 4-point IDCT operation required for the 8-point IDCT operation is performed sequentially without performing the same time, the repeated use of the same hardware is further increased. Therefore, the structure used for 4-point DCT is preferably used to maximize the repeated use of hardware in different DCT operations.

There is a distributed arithmetic method that can maximize the repetitive use of hardware while performing different DCT operations. Distributed arithmetic is a popular method in signal processing and very often used in the implementation of DCT. The distributed arithmetic processing is briefly described below.

Variable X is variables Y ₀ , Y ₁ , Y ₂ , Y ₃ Is assumed to be obtained according to the following equation.

X = C ₀ Y ₀ + C ₁ Y ₁ + C ₂ Y ₂ + C ₃ Y ₃ … … … (One)

Where the variable Y ₀ , Y ₁ , Y ₂ , Y ₃ Is expressed as n'bit 2's complement. Y _i , 0≤i≤3, Is expressed as

Yi = -2 ^n-1 y _i ^n-1 +2 ^n-2 y _i ^n-2 + ... + 2y _i ¹ + y _i ⁰

X may be expressed as follows.

In the above expression ∑ _{i = 0} ³ y _i ^k C _i The values of y _i ^k For all possible cases of pre-calculation and storing in ROM 2 ^k ∑ _{i = 0} ³ y _i ^k C _i You can easily find the value of. By continuing to obtain these intermediate values, we can finally get the desired value. The circuit which calculates the value of Formula (2) is shown by FIG. In the figure, the ROM and the accumulator are called RAC (ROM and accumulator in cascade), and the output of ROM (31) that receives 4-point inputs Y ₀ , Y ₁ , Y ₂ , Y ₃ is shown. The input value is multiplied by the cosine matrix-vector on the right side of the following equations (3) and (4) by feedback through the adder / subtracter 32 and the shift register 33, and the result is obtained. Is configured to output. This is a general configuration. In the present invention, three RACs are used to process a 4-point forward DCT using one RAC, and two different 4-point RACs are used to process an 8-point IDCT. have.

1 is a block diagram illustrating a conventional two-band subband DCT algorithm.

2 is a block diagram illustrating a conventional half-band subband DCT approximation model.

3 is a block diagram showing a conventional distributed arithmetic processing apparatus.

4 is a block diagram showing a half-band subband 8x8 DCT / IDCT for a low rate video signal using RAC according to the present invention;

<Description of the code | symbol about the principal part of drawing>

100: multiplexer

200: Serial-to-Parallel Converter (SPC)

201,401: register

300: 4-point RAC (ROM and Accumulator in Cascade)

400: butterfly part 410,420: register bank_A, B

430: adder / subtractor

500: Transposition Memory (TM)

Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings.

4 shows the structure of an 8x8 DCT / IDCT for low bit rate video signal. As shown in FIG. 4, an image input supplied from the multiplexer 100 includes one multiplexer 100 and eight registers 201 that selectively receive an input and an output of a pre-memory. And Sequential Parallel Converter (SPC) 200 for sequentially inputting and outputting in parallel in units of rows, three RACs 300 for receiving half-band subband DCT from parallel data from the Sequential Parallel Converter 200; And a butterfly unit 400 composed of eight registers 401 and one adder and subtractor 430 to perform a butterfly network function, and the output of the butterfly unit 400 receives the multiplexer 100. It is composed of a pre-memory 500 to be loaded in and supplied to the sequential parallel converter 200.

According to the present invention configured as described above, the sequential parallel converter 200 is configured such that four registers are connected in series, and four registers receiving the output of the four registers are output in parallel. -to-parallel converter). The butterfly unit 400 is composed of eight registers 401 and adders / subtracters, and four registers receive four-point data output from the three 4-RACs 300. Bank_A) 410, Bank_B (Bank_B) 420 to which the four-point data is inputted in the same configuration as that of Bank_A, and outputs of the Bank_A and Bank_B. It consists of an adder / subtractor 430 that performs the role of a butterfly network by subtracting / subtracting.

4 is provided with three four-input RAC 300, one RAC is used to perform a four-point forward DCT for half-band subband DCT, the other two RAC is an 8-point IDCT ( Is used to perform reverse DCT).

The DCT / IDCT operation for the low bit rate video signal according to the present invention configured as described above will be described.

First, the process of performing IDCT will be described. An eight-point IDCT can be represented by the two equations shown below.

… (3)

… (4)

The process of performing IDCT by the 8x8 DCT / IDCT module of FIG. 4 is as follows.

In the first step, the multiplexer 100 selects an initial external input and supplies it to the sequential parallel converter 200. That is, 8x8 image data is sequentially input to the SPC in units of rows. In this case, one row of four even-numbered data (Y0, Y2, Y4, Y6) is inputted first, and the fourth odd-numbered data (Y1, Y3, Y5, Y7) is input thereafter.

In the second step, the first four data inputted are matrix-vector multiplication shown in equation (3) by one RAC 300, and the result of the butterfly unit 400 is obtained. It is stored in register bank_A 410.

The third step is that the next four data inputs are performed by the matrix-vector multiplication shown in equation (4) by another RAC 300 and the result is the register bank_B of the butterfly unit 400. 420 is stored.

In the fourth step, intermediate results in register banks A, B 410, and 420 are processed by the adder / subtracter 430 while the next row of data is processed in the RAC 300. The butterfly calculations shown on the left side of the c) are performed and the results are sequentially stored in the prememory (TM) 500.

The process from the first to the fourth step is continued until all 64 data are stored in the pre-memory 500.

In the fifth step, 8x8 data in the pre-memory 500 is sequentially input to the SPC 200 in units of columns. That is, the multiplexer 100 selects the output of the pre-memory 500 instead of an external input and sequentially supplies the output to the parallel converter 200.

Also in this case, data of four even-numbered data (Y0, Y2, Y4, Y6) is input first, and four odd-numbered data (Y1, Y3, Y5, Y7) are input thereafter.

In the sixth step, the first four data inputs are performed by a single RAC 300 with matrix-vector multiplication shown in equation (3), and the result is the register bank_A (of the butterfly unit 400). 410.

In the seventh step, the next four data inputs are performed by the matrix-vector multiplication shown in equation (4) by another RAC 300 and the result is the register bank_B of the butterfly unit 400. 420 is stored.

In the eighth step, intermediate results in register banks A, B, 410, and 420 are processed by the adder / subtracter 430 while the next column of data is processed in the RAC 300. The butterfly calculation shown on the left side of is performed and the result is sequentially output as the result of 8x8 2-D IDCT.

The process from the fifth step to the eighth step is continued until all 64 data are output.

It is important that no register bank conflicts occur between the third and fourth stages and the seventh and eighth stages of the IDCT process shown above. The DCT / IDCT proposed in the present invention uses a distributed arithmetic method, so that the result of the RAC is output to the register bank at once after all four intermediate results are determined, so that there is no register bank conflict. For example, if the internal precision is 16-bit and each input of 4-RAC is 2-bit, RAC will output an intermediate result every 8 clocks. Therefore, if the register bank and the adder / subtracter 430 output eight results every eight clocks, there is no register contention.

The operation of the 8x8 DCT / IDCT module proposed in the present invention performs half-band subband DCT. Here, the image compression system inputs 4x4 data on which 2x2 Hadamard transform is performed as an input of DCT / IDCT. Each element of the 4x4 matrix is simply an average of the 2x2 sub-matrix of the 8x8 matrix, so it can be simply calculated.

The 8x8 DCT / IDCT proposed in the present invention performs only DCT on Hadamard transformed 4x4 data and the DCT coefficients for the remaining 48 of 8x8 data are treated as '0' in the image compression system. The process of performing 4x4 2-D DCT in 8x8 DCT / IDCT is as follows.

In the first step, 4x4 image data selected by the multiplexer 100 is sequentially input to the SPC 200 in row units.

The second step is that four input data are performed by one RAC 300 for matrix-vector multiplication necessary for 1-D DCT, and the result is stored in register bank_A 410 of the butterfly unit 400. Stored.

In a third step, intermediate results in register bank_A 410 are sequentially stored in pre-memory TM 500 while the next row of data is processed in RAC 300.

The process from the first to the third step is continued until all 16 data are stored in the pre-memory 500.

In the fourth step, 4x4 data in the pre-memory memory 500 is sequentially input to the sequential parallel converter 200 in units of columns through the multiplexer 100.

In the fifth step, four input data are performed by one RAC for matrix-vector multiplication necessary for 1-D DCT, and the result is stored in register bank_B 420 of the butterfly unit 400.

In the sixth step, the results in the register bank_B 420 are sequentially output as the result of the 4x4 2-D DCT while the next column of data is processed in the RAC.

The process from the fourth step to the sixth step is continued until all 16 data are output.

In FIG. 4, it is assumed that one clock takes eight clocks to perform matrix-vector multiplication on four inputs. This assumes that the internal precision is 16-bit and there are 2-bits for each channel. Therefore, data input to the sequential parallel converter 200 should be input one by one to two clocks.

In the case of performing 8x8 2-D IDCT, in the butterfly circuit of FIG. 4, after eight data are input to the 8x8 2-D IDCT register bank_A 410 and register bank_B 420, the 8x8 2-D IDCT is executed within 8 clocks. Data must be calculated and supplied to the pre-memory 500. This is because eight data are input to the bank_A 410 and the bank_B 420, and new data is supplied to the bank_A 410 after eight clocks.

In the case of performing 8x8 2-D IDCT, 40 rows are required until one row of 1-D DCT is performed and stored in the pre-memory 500. In reality, eight data are stored in the pre-memory memory 500 only in 32 clocks, but since the butterfly circuit does not operate for eight clocks, it takes 40 clocks.

Therefore, if eight rows are supplied in a pipelined manner, 1-D DCT is performed on each of the eight rows, and it takes 152 clocks to store the result in the pre-memory. Since each 1-D DCT is performed on 8 rows stored in the pre-memory memory 500, and it takes 152 clocks to output the result, it takes 304 clocks to perform one 8x8 2-D DCT. do.

When 4x4 2-D IDCT is performed, 24 rows are required until one row of 1-D DCT is performed and stored in the pre-memory. When four rows are supplied in a pipelined manner, each 1-D DCT is performed on each of the four rows, and it takes 48 clocks to store the result in the prememory. Since each 1-D DCT is performed on each of four rows stored in the pre-memory, and the result is 48 clocks again, it takes 96 clocks to perform one 4x4 2-D DCT.

When two IDCTs are performed at 30 QCIFs per second and one half-band subband DCT is performed, the number of clocks is as follows. It is assumed here that no pipeline method is used between blocks.

30 x 99 x 6 x (96 + 304 + 304) ≈ 11.4 x 10 ⁶

Therefore, the operating clock frequency required for 8x8 DCT / IDCT is about 12 MHz.

According to the present invention, when two IDCTs are performed for 30 QCIF screens per second and one half-band subband DCT, the required operating frequency is about 12 MHz, which is very low, thereby reducing power consumption. By repeatedly using the same hardware, 8x8 DCT / IDCT for low bit rate video signal can be efficiently performed at low hardware cost.

Claims (6)

A multiplexer to select the input and output of the prememory, Sequential parallel conversion means for sequentially receiving the image input selected by the multiplexer in units of rows and outputting them in parallel; Three RACs that receive the input data output from the sequential parallel converter and perform matrix-beta multiplication to process half-band subband DCT / IDCT; Butterfly means for performing a function of a butterfly network on data output from the RAC; A half-band subband DCT / IDCT circuit using a RAC consisting of a pre-memory means for receiving the output of the butterfly means, loading it into the multiplexer, and supplying it to the serial-to-parallel conversion means. The method of claim 1, wherein the DCT / IDCT circuit, Half-band subband DCT / IDCT circuit using RAC, characterized in that it is configured to transmit to the butterfly means at once after all four intermediate results in the RAC have been determined using distributed arithmetic. . The method of claim 1, wherein the three RAC, One RAC that performs 4-point forward DCT for half-band subband DCT, Half-band subband DCT / IDCT circuit using RAC, characterized in that it consists of two RACs performing 8-point IDCT. The method of claim 1, wherein the butterfly means, Register bank_A, register bank_B, each of which consists of four registers and alternately stores the output of the RAC; A half-band subband DCT / IDCT circuit using the RAC, characterized in that the register bank_A and one adder / subtracter for performing butterfly calculations by reading the data in the register bank_B. In the DCT / IDCT circuit, One 4-point RAC for DCT processing and two 4-point RAC different from the RAC for IDCT processing, A first process of first inputting even-numbered data in row units and then receiving odd-numbered data in parallel and sequentially converting them in parallel; The serial-converted data is input from the RAC and matrix-vector multiplication is performed on a row-by-row basis, but in one RAC for 4-point forward DCT processing, and different from the one RAC for 8-point IDCT processing. Performing a matrix-vector multiplication by dividing data by four points in two RACs and storing the result in register bank_A and register bank_B in sequence; A third step of reading data stored in the register banks A and B, performing butterfly calculation by addition / decrement calculation, and storing the data in the pre-memory; After repeating the third process from the first process to process all the data in units of rows, the butterfly calculation is completed while repeating the processes from the first to the third process of data stored in the transpose memory in columns The half-band subband DCT / IDCT method using the RAC, characterized in that for performing a fourth process of outputting the. The method of claim 5, wherein the second process, A half-band subband DCT / IDCT method using a RAC, characterized in that the result of the RAC is output to the register bank at once after all four intermediate results are determined by using a distributed arithmetic processing.