JP2958966B2 - Discrete cosine converter - Google Patents

Description

Description: BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a discrete cosine transform device used for image data compression processing.

[Related Art] Recently, in the field of videophones and the like, compression processing of image data using discrete cosine transform (hereinafter abbreviated as DCT) has attracted attention.

Here, DCT is one of orthogonal transforms, and is called a transform method having the highest energy concentration along with the Karnen-Loeve transform.

Now, the result F (u) (u = 0, 1,..., N−) of the signal f (j) (j = 0, 1,..., N−1) by one-dimensional DCT
1) is defined by the following equation.

However, The inverse transformation is Is defined by

In other words, DCT divides a certain waveform into frequency components,
The same number of cosine waves as the number of input samples is expressed. Each waveform is represented by F (0): DC F (1): cos [(2j + 1) π / 2N] F (2): cos [(2j + 1) 2π / 2N] Here, when N = 8, the result is as shown in FIG.

By performing such an orthogonal transformation on the image,
By concentrating energy and encoding only components having a large amount of energy, image data can be compressed.

By the way, when trying to calculate such a DCT with the definition formula, the calculation amount becomes enormous, and a general-purpose microprocessor takes a considerable amount of time to process.
Not realistic.

Therefore, in order to efficiently perform the DCT operation, the reference document IEEE TRANSACTION ON COMMUNICATIONS.VOL.COM-2
5, NO.11, NOVEMBER 1977 (Adaptive Coding of Mo
nochrome and Color Image, WEN-HSIUNGCHEN, C.HA
RRISON SMITH) has been considered. FIG. 11 shows an example of such a DCT flow graph. Here, an eight-dimensional DCT flow graph is shown. Then, in the arithmetic processing using such a graph, the arithmetic is performed from left to right in the case of DFT, and the arithmetic is performed from right to left in the case of inverse DCT.

Conventionally, using such a flow graph
As arithmetic means for executing DCT or inverse DCT, flip-flops FF1, FF are stored in the storage device MA as shown in FIG.
2. An arithmetic unit including a shifter SFT and an adder / subtractor ALU is connected, and a DCT operation is performed by the arithmetic unit on data read from the storage device MA.

[Problem to be Solved by the Invention] By the way, such an arithmetic means can be used, for example, in an N × N
Two-dimensional DC for sub-block image data
When performing T conversion, as shown in FIG.
Assuming that N pieces of image data are one block in the block row direction, N times one-dimensional DCT transform is performed on such N blocks, and then, as shown in FIG. Will perform the same processing. However, in this case, the DCT conversion in the row direction and the DCT conversion in the column direction differ in the direction in which data is read from the storage device MA and the read address thereof, so when the DCT conversion in the row direction is completed, The obtained data is rearranged so that the DCT transform in the column direction can be performed. This causes a reduction in the operation speed in performing the two-dimensional DCT transform, and there is a drawback that efficient processing is difficult. Was.

The present invention has been made in view of the above circumstances, and an object of the present invention is to provide a discrete cosine transform device that can execute a two-dimensional DCT operation without rearranging the converted data and can speed up the operation. And

[Means for Solving the Problems] The present invention is to execute a two-dimensional discrete cosine transform on data blocked into N × N pixels, wherein the data storage means stores the data;
Arithmetic means for inputting data read from the data storage means to perform a discrete cosine operation; buffer means for designating a column address and a row address of the data storage means; and data divided into N × N pixels A control means for outputting an address control signal designating an address of one pixel in a column or a row of data, each time a discrete cosine operation for one line block of a column or a row of data divided into N × N pixels is completed And a row address of the buffer means is designated by the count value of the counter means, and an address control signal of the control means is inputted to a column address of the buffer means, and the counting of the counter means is performed. If the value exceeds N, the column address of the buffer Address switching means for inputting an address control signal of the control means to a row address of the buffer means while being designated by a counter value of the counter means.

[Operation] As a result, one-dimensional DC for each line block in the row direction is obtained.
Without performing rearrangement of the converted data after the T operation, the one-dimensional DCT operation can be executed for each one line block in the next column direction, and the two-dimensional DCT operation can be executed at high speed.

Hereinafter, one embodiment of the present invention will be described with reference to the drawings.

FIG. 1 shows a circuit configuration of a main circuit of the embodiment. In the figure, 1 is an external interface circuit,
The external interface circuit 1 has a command register addressed by a control signal CP (10:12) from a CPU (not shown), and has an internal operation / external operation, DCT / inverse DCT, READ / WR.
The user designates switching of ITE, Y / BY, RY, etc., and sets the flag EXEC to control the entire system. Also, it has a function of outputting an NBUSY signal to the outside during the operation or quantization of the two-dimensional DCT. Reference numeral 2 denotes a timing generator, which generates a basic timing clock for operating the system. Reference numeral 3 denotes a 10-bit synchronous counter which counts the clock P3 from the timing generator 2 and designates an address of a sequencer memory 6 described later. Here, the synchronous counter 3 is configured as shown in FIG. An OR circuit 31 has an inverter 32 connected to one input terminal of the OR circuit 31.
An end mark signal LNEND written together with a control program for DCT conversion into a sequence memory 6 described later through
And the other input terminal receives count contents CT (0) to CT (3) of the counter 8 described later.
33 outputs are provided. The output of the OR circuit 31 is provided to one input terminal of the AND circuit 34. This AND circuit
A flag EXEC output from the external interface 1 is given to the other input terminal of the. The output of the AND circuit 34 is provided to the D terminal of the flip-flop 35. The output from the Q terminal of the flip-flop 35 is the D terminal of the flip-flop 36, one input terminal of the NOR circuit 37, and the AND circuit.
The output from the terminal is supplied to one input terminal of the NAND circuit 39. Further, the output from the Q terminal of the flip-flop 36 is supplied to the other input terminal of the NOR circuit 37, and the output from the terminal is supplied to the other input terminal of the NAND circuit 39. The NOR circuit 37 outputs a busy signal NBUSY. Also, AND circuit 3
The clock P3 from the timing generator 2 is supplied to the other input terminal of the counter 8 and this clock P3 is
Output to 40. Further NAND circuit
The output of 39 is provided to one input terminal of the NAND circuit 41. A write enable signal WE is supplied to the other input terminal of the NAND circuit 41, and an NWE signal is output from an output terminal thereof. The counter 40 includes three 4-bit binary counters 401, 402, and 403.
The clock signal P3 supplied thereto is counted, and address signals IA (0) to IA (9) for reading data from the sequence memory 6 are output. The reset signal RESET is supplied to the CLR terminals of the flip-flops 35 and 36 via the inverter 42 and the CLR terminals of the binary counters 401, 402 and 403 constituting the counter 40, and the end mark signal LNEND is supplied via the inverter 32. Binary counter 4
01, 402 and 403 are supplied to the LD terminals. Further, the timing signal ARCK is supplied to the CK terminals of the flip-flops 35 and 36.

Returning to FIG. 1, reference numerals 4, 5, and 11 denote 2to1 multiplexers, of which the multiplexer 4 has a width of 1 bit, and the multiplexers 5 and 11 have a width of 10 bits. The multiplexers 4, 5, and 11 select the A-side input when the control signal CPU from the CPU is at the "L" level, and select the B-side input when the control signal is at the "H" level. In this case, the multiplexer 4 is a write enable signal NCWE from the timing generator 2 or the CPU, the multiplexer 5 is an address signal IA (0: 9) from the synchronous counter 3 or an address signal CP (0: 9) from the CPU, and the multiplexer 11 Selects an output of the address conversion circuit 10 or an address signal (0: 9) from the CPU via the converter 23.

Reference numeral 6 denotes a sequence memory. This memory 6 stores various control data required for DCT or inverse DCT operation provided from the external interface circuit 1 as a program for each step, and writes an end mark signal LNEND at a predetermined step. Is embedded. In this case, the control data required for the DCT and the inverse DCT are stored in different areas, here, the DCT program is stored in the lower area, and the inverse DCT program is stored in the upper area.
Specify either DCT or inverse DCT program by TI,
It is designed to be read. Here, the sequence memory 6
Is composed of a rewritable 40-bit × 2K RAM, and can operate a program of up to 1024 steps for a control signal required for DCT or inverse DCT operation.
FIG. 4 shows a configuration diagram of the sequence memory 6.
The bit is the read address AR (0: 2) of the area A of the dual port memory 12, the 3 bits are the write address AW (0: 2) of the area A of the memory 21, and the 3 bits are the read address of the area B of the memory 12. BR (0: 2), 3 bits for write address BW (0: 2) in area B of the same memory 12, 5 bits for shifter 1
7 is a control SA (0: 4), 1 bit is a control ASA of the adder / subtractor 19, 2 bits is a latch mode AM (0: 1) of the flip-flops 13 and 14, and 5 bits is a control SB (0: 4) of the shifter 18. 1 bit is the control ASB of the adder / subtractor 20, 2 bits is the latch mode BM (0: 1) of the flip-flops 15 and 16, 1 bit is the through / loop switching ATL of the arithmetic system A, and 1 bit is the Through / loop switching BTL, 1 bit cross / parallel switching CP, 1 bit sequencer end mark LNEND, 2 bits quantized data AN (0: 1) of operation system A, 2 bits quantized data of operation system B BN (0: 1), 1 bit is used for quantization control COMP.

The various control signals of the sequence memory 6 are the inverted signal NP of the clock P3 from the timing generator 2.
The signal is temporarily latched by the flip-flop 7 at the rising edge of 3 and then output.

Here, the end mark signal LNEND latched by the flip-flop 7 is given to the counter 8 via the inverter 24. In this case, the counter 8 outputs the end mark signal
4 bits that count the falling of LNEND.
For the eight sub-blocks of image data, a primary row operation is performed at 0 to 7H and a secondary column operation is performed at 8 to FH. The read address AR (0: 2) and write address AW (0: 2) stored in the flip-flop 7 are sent to the address conversion circuit 9 by the read address BR (0: 2) and the write address BW (0: 2). Are provided to the address conversion circuit 10, respectively. The address conversion circuit 9 includes a flip-flop 7
The read address AR (0: 2) and the write address AW (0: 2) as the address control signals latched by the counter 8 and the address signal A (0 : 9), and when the MSB of the count value of the counter 8 is 0, that is, when the count value is 0 to 7H, the address control signal latched by the flip-flop 7 is extended to A (0: 4). The three bits on the LSB side of the counter 8 are extended and applied to A (5: 9). When the MSB of the count value of the counter 8 is 1, that is, when the count value is 8 to 15H, A (0: 4) ), The 3 bits on the LSB side of the counter 8 are extended and given.
At (5: 9), the address control signal latched by the flip-flop 7 is extended and applied. The address conversion circuit 10 is the same as the address conversion circuit 9 described above. The read address BR (0: 2) and the write address BW (0: 2), which are the address control signals latched by the flip-flop 7, and the counter 8 The address signal B (0: 9) of the area B of the dual port memory 12 is output from the count value.

The dual port memory 12 stores image data, and is composed of 16 bits × 1024 words. Then, the address signals A (0:
9) and two data MAs (0: 9) simultaneously according to B (0: 9).
15), MB (0:15) can be written and read. Also, this dual port memory 12 is DC
In addition to storing input data when performing T or inverse DCT and output data that is the result of the operation, it is also used as a work memory for temporarily storing data during the operation.

Next, FIG. 2 shows a circuit configuration of the arithmetic unit of the embodiment. In this case, the operation unit has two operation systems A and B.

Reference numerals 13 and 14 denote 16-bit flip-flop groups which latch the first data MA (0:15) from the dual port memory 12. Also, 15 and 16 are 16-bit flip-flop groups, and the second data MB (0:
15) Latch. Here, flip-flop groups 13, 16
Are performed by timing signals ARCK and BRCK, and the operation timings of the flip-flop groups 14 and 15 are performed by timing signals ARPCK and BRPCK.

The data latched by the flip-flop group 13 is
At the same time, the data supplied to the + terminal of the adder / subtractor 20 via the gate G1 and the data latched by the flip-flop group 16 are supplied to the shifter 18 and to the + terminal of the adder / subtractor 19 via the gate G2. Given. The data latched by the flip-flop group 14 is supplied to the + terminal of the adder / subtractor 19 via the gate G7, and the flip-flop group 15
Is supplied to the + terminal of the adder / subtractor 19 via the gate G8.

Here, the shifter 17 is configured as shown in FIG. Reference numeral 51 denotes a barrel shifter. The barrel shifter 51 can shift 16-bit data up and down by 8 bits in units of 1 bit, and the shift amount is controlled by the output of the multiplexer 52. If the quantization control COMP is at the “L” level in the normal DCT operation, the AND circuit
By the "L" level output of 53, the multiplexer 52 is controlled by the shifter control SA (0: 4). When the quantization control COMP is at the "H" level, the AND circuit waits until the AND circuit goes to the "H" level. Controlled by the output of table 54. Here, the table 54 stores the count value CT of the counter 8 based on the shift amount shown in FIG. 6 (a) which has been assigned to the quantized data AN (0: 1) in advance.
The tables shown in FIGS. 6 (b) and 6 (c) are configured corresponding to (0: 2) to enable power-of-two quantization in sub-block 8 × 8 pixel units. Here, FIG. 6 (b)
Shows a table of the luminance signal Y, and FIG. 4C shows a table of the color difference signals BY and RY. Further, the quantized data AN (0) and AN (1) are both “1”, and the output from the barrel shifter 51 is clipped by the clip circuit 56 by the output of the NAND circuit 55. This is because the purpose of the 16-bit shift is to make the harmonic component data zero. Of course, the other shifter 18 is the same as the shifter 17.

Returning to FIG. 2, the output from the shifter 17 is supplied to the ± terminal of the adder / subtractor 19, and is written to the dual port memory 12 via the gate G3. And written to the dual port memory 12 via the gator G4. Adder / subtractor 1
9 and 20 are composed of a 4-bit full adder × 4 and an EXOR group, and perform 2's complement operation. And
The operation results from the adders / subtractors 19 and 20 are latched by flip-flops 21 and 22, respectively, and then written to the dual port memory 12 via the gates G5 and G6. Here, the operation timing of the flip-flops 21 and 22 is performed by a timing signal ALCK.

 Next, the operation of the embodiment configured as described above will be described.

In this case, when the control signal CPU from the CPU is at the "L" level, the A input side of both the multiplexers 4 and 5 is selected. In the sequence memory 6, the DCT program has already been loaded in the lower area and the inverse DCT program has been loaded in the upper area. From this state, the DCT program in the lower area of the sequence memory 6 is now activated by the area designation signal DCTI of the external interface 1. Is specified.

First, in FIG. 3, the flip-flops 35 and 36 and the counter 40 are cleared by the reset signal RESET. After that, the 8-bit image data expanded to signed 16-bit data is supplied from the CPU to the dual port memory 12 via DB (0: 7). And sub-block 8
When all of the x8 data 16 bits x 64 have been written,
The flag EXEC is set in the external interface 1 [FIG. 7 (b)]. Then, the output of the AND circuit 34 becomes "H" level [FIG. 7 (k)], and the outputs of the Q terminals of the flip-flops 35 and 36 are sequentially turned on at the rise of the timing signal ARCK shown in FIG. 7 (c). It becomes the “H” level [FIGS. 7 (d) and (e)], and the
The clock P3 shown in FIG. 7A is supplied to the counter 40 (FIG. 7F). At the same time, the output of the NOR circuit 37 becomes “L” level, and the busy signal NBUSY
Is output [FIG. 7 (l)]. In addition, since the output of the NAND circuit 39 becomes “H” level, the write enable signal WE shown in FIG. 7 (j) is output via the NAND circuit 41 as the write enable signal NWE whose polarity is inverted [the seventh embodiment]. Figure (m)]. In this state, the output of the counter 40 is applied to the sequence memory 6 as the address signal IA (0: 9) from the synchronous counter 3, and the control data is read out and DCT conversion is performed [FIG. 7 (g)]. . here,
The control data read in the third step of the sequence memory 6 includes the end mark signal LNEN as shown in FIG.
Assuming that D is written, the counter 40 is loaded with 0 at the next rising edge of the clock P3 and reset, and at the falling of the end mark signal LNEDN, the count content CT (0: 3) is counted up (FIG. 7 (i)). In this case, although the details will be described later, the DCT transform for the 8 × 8 block proceeds in the row direction and then in the column direction by counting up the count content CT (0: 3) of the counter 8, and the two-dimensional final stage, that is, the column direction When CT (0: 3) = 15, the end mark signal is turned on by the L level “H” level or the OR circuit 31
Becomes "L" level, and the output of the Q terminal of the flip-flop 35 becomes "L" in response to the next given timing signal ARCK.
Therefore, the clock P3 applied to the counter 40 through the AND circuit 38 is stopped, and the data reading from the sequence memory 6 is also stopped. Also, flip-flop 36
Accordingly, the write enable signal NWE is also stopped with a delay of one timing.

Next, the calculation timing in the calculation unit will be described. First,
In response to the clock P3 from the timing generator 2 shown in FIG. 8A, the synchronous counter 3 sends the address signal IA to the sequence memory 6 shown in FIG. 8C.
When (0: 9) is output in the order of 0, 1, 2,..., The sequence data is read from the sequence memory 6 [FIG. 8 (d)], and the falling signal NP3 of the clock signal P3 is applied to the flip-flop 7. It is latched [FIG. 8 (e)]. This state is maintained for one operation cycle.

Here, the first half of one cycle is a read section of the dual port memory 12 as shown in FIG. 8 (f), which is a 4-bit counter value of the counter 8 and an address control signal latched by the flip-flop 7. Read address AR
(0: 2) and BR (0: 2) are applied to the address conversion circuits 9 and 19, and the first and second address signals A (0: 9) and B (0:
9) is provided to the dual port memory 12. In this case, as the first address signal A (0: 9), when the count value of the counter 8 is 0, the address control signal latched in the flop flop 7 is extended and assigned to A (0: 4). At 5: 9), the 3 bits on the LSB side of the count value of the counter 8 are extended and assigned. As a result, A is applied to the blocked image data shown in FIG.
The first one-line block in the row direction is designated by the count value of the counter 8 assigned to (5: 9), and A (0:
The address in the one-line block in the row direction is designated by the address control signal from the flop flop 7 assigned to 4), and when the count value of the counter 8 is counted up, the one-line block in the row direction is counted. Is shifted line by line in the column direction. Thereafter, when the count value of the counter 8 becomes 8, the LSB side 3 bits of the count value of the counter 8 are extended and assigned to A (0: 4), and latched to the flop flop 7 at A (5: 9). The assigned address control signal is extended and assigned. Thus, the first one-line block in the column direction is designated by the count value of the counter 8 assigned to A (0: 4) for the blocked image data shown in FIG. The address within the one-line block in the column direction is designated by the address control signal from the flop 7 assigned to (5: 9), and when the count value of the counter 8 is counted up, the address in the column direction is increased. The designation of one line block is shifted line by line in the row direction. The same applies to the second address signal B (0: 9).

Then, based on the first and second address signals A (0: 9) and B (0: 9) thus obtained, the data MA (0:15) and MB (0: 15) are simultaneously read and latched by the flip-flops 13 and 16 at the timing of the timing signals ARCK and BRCK shown in FIG. The predetermined operation at 20 is executed [FIG. 8 (i)].

Here, when the cross-parallel switching CP from the flip-flop 7 is at the “H” level, the gates G1 and G2 close, the gates G7 and G8 open, and the data latched by the flip-flop 13 is added / subtracted via the shifter 17. And the data latched by the flip-flop 16 is applied to the ± terminal of the adder / subtractor 20 via the shifter 18, and is applied to the ± terminal of the adder / subtractor 20 via the gate G 1. The signal is applied to the + terminal of the adder / subtractor 19 via the gate G2, and when the cross-parallel switching CP is at "L" level, the gates G1 and G2 are opened, the gates G7 and G8 are closed, and the flip-flop 13 The latched data is supplied to the ± terminal of the adder / subtractor 19 via the shifter 17 and the flip-flop 14
The data latched by the flip-flop 16 is supplied to the + terminal of the adder / subtractor 19, and the data latched by the flip-flop 16 is shifted by the shifter.
The data supplied to the ± terminal of the adder / subtractor 20 via 18 and the data latched by the flip-flop 15 are supplied to the + terminal of the adder / subtractor 20 to execute a predetermined operation. When the operation in each of the adders / subtractors 19 and 20 is executed, the latter half of the write period shown in FIG. 8 (f) occurs, and the operation result is output to the flip-flop 2 at the timing of ALCK shown in FIG. 8 (h).
1, 22 and are written to the addresses AW (0: 2) and BW (0: 2) of the dual port memory 12 at the rising timing of the write enable signal NWE shown in FIG. 8 (j). . Note that the through loop switching ATL and BTL are "H".
In the through mode in which the gates G3 and G4 are opened at the level, the result shifted by the shifters 17 and 18 is written to the dual port memory 12 as it is.

In the above description, the area designation signal DCTI of the external interface 1 or 5 causes the lower area of the sequence memory 6 to be
Specify the DCT program and follow this program
Although the case where the CT operation is executed has been described, when the inverse DCT program in the upper area of the sequence memory 6 is designated by the area designation signal DCTI, each circuit is operated according to the control data of the program in the same manner as described above. According to the present invention, the row address of the buffer unit is set to 1 in the column direction for the data blocked into N × N pixels according to the count value of the counter unit. A one-dimensional discrete cosine operation is performed for each one-line block in the row direction while shifting line by line. After this operation, the column address of the buffer means is shifted line by line in the row direction according to the count value of the counter means, and the column address is shifted in the column direction. , A one-dimensional discrete cosine operation can be performed for each line block of One-dimensional discrete cosine operation for each one-line block in the row direction while shifting one line at a time, and one-dimensional discrete cosine for each one-line block in the column direction while shifting the column address one line at a time in the row direction Since the calculation can be performed continuously, the two-dimensional discrete cosine calculation can be executed at high speed, and efficient processing can be realized.

[Brief description of the drawings]

1 and 2 are block diagrams showing a circuit configuration of an embodiment of the present invention, FIG. 3 is a block diagram showing a circuit configuration of a synchronous counter used in the embodiment, and FIG. FIG. 5 is a block diagram showing a circuit configuration of a shifter used in the embodiment, FIG. 6 is a diagram for explaining the shifter, and FIGS. 7 and 8 are for explaining the embodiment. FIG. 9 is a diagram for explaining the embodiment, FIG. 10 is a waveform diagram for explaining DCT, FIG. 11 is a diagram showing an example of a DCT flow graph used for DCT calculation, FIG. 12 is a circuit diagram showing a conventional DCT operation means, and FIG. 13 is a diagram for explaining DCT conversion by the operation means. 1 ... External interface, 2 ... Timing generator, 3 ... Synchronous counter, 4, 5, 11 ...
Multiplexer, 6 Sequence memory, 7 Flip-flop, 8 Counter, 9, 10 Address conversion circuit, 12 Dual port memory, 13-16, 21, 22
…… Flip-flops, 17, 18 …… Shifters, 19, 20 ……
Adder / subtractor,

──────────────────────────────────────────────────続 き Continuation of the front page (56) References JP-A-54-94251 (JP, A) JP-A-58-151675 (JP, A) JP-A-60-7576 (JP, A) 500425 (JP, A) (58) Field surveyed (Int. Cl. ⁶ , DB name) G06F 17/14

Claims (1)

(57) [Claims] An apparatus for performing a two-dimensional discrete cosine transform on data divided into N × N pixels, comprising: data storage means for storing the data; and data read from the data storage means. Arithmetic means for inputting a discrete cosine operation; buffer means for indicating a column address and a row address of the data storage means; and an address for one pixel of a column or a row of data divided into N × N pixels Control means for outputting an address control signal to be processed, counter means for counting up each time a discrete cosine operation for one line block of a column or row of data divided into N × N pixels is completed, and the buffer Specifying the row address of the means by the count value of the counter means An address control signal of the control means is input to a column address of the buffer means, and when the count value of the counter means exceeds N, the column address of the buffer means is designated by the counter value of the counter means, and An address switching means for inputting an address control signal of the control means to a row address of the means.