JP3320767B2 - Data processing apparatus and control method thereof - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[Contents] Industrial application field Conventional technology (FIG. 13) Problems to be Solved by the Invention Means for Solving the Problems (FIGS. 1 and 2) Action Embodiment (1) First Embodiment (FIGS. 3 to 8) (2) Description of the second embodiment (FIGS. 9 to 12)

[0002]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a data processing apparatus and a control method therefor, and more particularly, to an apparatus for calculating a median value in an odd number of data, which is one of image processing methods, and an apparatus therefor. The present invention relates to an improvement in a calculation method.

In recent years, the performance of industrial equipment such as medicine and engineering has been improved, and the introduction of computers is indispensable. In image processing in such a field, the need for data analysis is not limited to the function of simply displaying image information on the display, and at the same time, the amount of data handled tends to be enormous.

According to this, in order to increase the speed and efficiency of the image processing system, the median arithmetic unit sequentially extracts data from the maximum value of the odd number of data to be processed to the minimum value thereof, A bubble sort method or a quick sort method for finding the median is employed.

However, in the field of image processing and audio processing, if the amount of data handled increases according to the manner of use by the user, the number of data comparisons increases with this method,
The hardware that makes it up increases.

Therefore, the method of calculating the median value is devised without depending on only the bubble sort method or the quick sort method in relation to the calculation of the median value of the data to be operated. There is a need for an apparatus and method that can achieve high speed.

[0007]

2. Description of the Related Art FIGS. 13A and 13B are explanatory diagrams of a data processing device according to a conventional example, and FIG. 13A is a configuration diagram of a first median value calculating device according to a conventional example. And FIG. 13 (b)
Shows configuration diagrams of the second median value calculation device.

For example, a first median value arithmetic device (hereinafter, simply referred to as a first device) which calculates a median value in an odd number of data, which is one of signal processing methods such as noise elimination, is shown in FIG.
In FIG. 1A, a data array 1 for temporarily storing nine data to be processed, a comparator / exchanger 2 for extracting a median from among the nine data to be processed, and an output unit 3 for outputting the median are provided. .

The comparison / exchanger 2 and the data array 1 are fixedly wired by nine data transfer lines, and the output unit 3 is connected to the center of the data array 1. The function of the first device is that, when nine data to be operated are temporarily stored in each memory area of the data array 1, data from the maximum value to the minimum value of the nine data to be operated is compared / exchanged. 2, the value located at the center thereof is extracted as the median by the comparison / exchanger 2, and the median is output from the output unit 3.

A second median arithmetic unit (hereinafter simply referred to as “second device”) supplemented with the data rearranging function of the first device is shown in FIG. A sub-array 4 for temporarily storing data from the maximum value to the median value is provided.

The subarray 4 and the comparing / exchanging unit 2 are connected via a selector 5, and when the data from the maximum value of the nine data to be processed to the minimum value can be sequentially rearranged, the maximum value is determined. Every time extraction is performed, the selector 5 is switched.

The function of the second device is that when nine data to be processed are temporarily stored in each memory area of the data array 1, the data from the maximum value to the minimum value of the nine data to be processed is compared. -Rearranged by exchanger 2. At this time, every time the maximum value of the data to be operated is extracted, the selector 5 is switched, and data from the maximum value to the median value is temporarily stored in the sub-array 4.

As a result, the value stored at the end is read from the sub-array 4 as the median value, and the median value is output from the output unit 3.

[0014]

By the way, according to the first and second devices of the prior art, the comparison / exchanger 2 and the data array 1 are fixedly wired by an odd number of data transfer lines, and the output section thereof is provided. 3 is connected to the center of the data array 1. Further, a bubble sort method or a quick sort method in which data from the maximum value of the odd number of data to be operated to the minimum value thereof is sequentially extracted and the median value thereof is obtained is employed.

For this reason, in the field of image processing and audio processing, when the amount of handled data increases due to the usage of the user, the number of data comparisons in the comparator / exchanger 2 for sequentially extracting the maximum value from the data to be processed is increased. And the hardware that makes it up.

For example, according to the bubble sort method, assuming that the number of data to be operated is n [odd] and the number of comparisons is k, the comparison is performed according to a relational expression of k = 3/8 · (n ² −1). Time and comparison amount increase.

As a result, there is a problem that high-speed data processing is hindered in the field of image processing or the like due to a delay in processing time for the median value calculation. The present invention has been made in view of the problems of the conventional example, and relates to the calculation of the median value of the data to be operated, without relying only on the bubble sort method or the quick sort method. It is an object of the present invention to provide a data processing device capable of reducing the number of data comparisons and increasing the speed of data processing by devising (shift division method) and a control method thereof.

[0018]

FIG. 1 is a principle diagram of a data processing apparatus according to the present invention, and FIG. 2 is a principle diagram of a data processing method according to the present invention.

As shown in FIG. 1, a first data processing apparatus according to the present invention comprises a storage means 11 for sequentially storing odd [n = 2m + 1, m ≧ 1] pieces of operation data Dn; And a median output means 13 for outputting a median value of the extracted data Dn. The data extraction means 12 includes: The reading area of the storage means 11 is sequentially changed.

In the first data processing apparatus according to the present invention, the data extracting means 12 comprises [n + 1] / 2 comparison / exchange means Ci, and the comparison / exchange means Ci comprises m + 1 pieces from the forefront or last part. Comparing the operated data Dn up to the first and extracting the maximum value among the operated data Dn;
The maximum value of the data to be operated Dn is exchanged with the foremost or last data to be operated Dn.

Further, the second data processing device of the present invention comprises:
In the first data processing device, the comparison and exchange means Ci compares the (m + 1) th data to be operated Dn from the foremost part or the last part and extracts the minimum value among the data to be operated Dn, The method is characterized in that the minimum value of the data to be operated Dn is exchanged with the foremost or last data to be operated Dn.

Further, in the first and second data processing devices of the present invention, an auxiliary storage means 14 for temporarily storing the extracted data to be operated Dn is provided. Further, in the first and second data processing devices of the present invention, a control means 15 for controlling the input / output of the storage means 11, the data extraction means 12, the median output means 13 and the auxiliary storage means 14 is provided. Features.

Further, the first data processing method of the present invention comprises:
As shown in the processing flow chart of FIG. 2, first, at step P1, an odd number [n = 2m + 1, m ≧ 1] array processing of the data Dn is performed. Alternatively, the maximum value is extracted from the m + 1-th data Dn to be processed from the last part, and
In step P3, the maximum value of the data to be operated Dn is exchanged with the foremost or last data to be operated Dn. Thereafter, in step P4, the read area of the data to be operated Dn is sequentially changed, and The maximum value of the operation data Dn is extracted, and then, in step P5, the operation data Dn
Is exchanged with the foremost or last processed data Dn of the read area, which is sequentially changed, and thereafter, in step P6, the rearranged forefront or rearranged data related to the odd number of processed data Dn The output processing of the minimum value among the (m + 1) data to be operated Dn from the rear end is performed.

Note that the second data processing method of the present invention
As shown in the processing flowchart of FIG.
After the array processing of the operated data Dn, the minimum value is extracted for the (m + 1) -th operated data Dn from the foremost part or the rearmost part that has been arrayed in step P2A. The above object is achieved by performing a process of outputting the maximum value of m + 1 pieces of operation data Dn from the frontmost or rearmost part rearranged with respect to an odd number of operation data Dn based on the extraction processing. .

[0025]

According to the first data processing apparatus of the present invention, as shown in FIG. 1, a storage means 11, a data extraction means 12, and a median output means 13 are provided. Are sequentially changed.

For example, an odd number [n = 2m + 1, m ≧ 1] of processed data Dn is stored in the storage unit 1 via the control unit 15.
When the data is sequentially stored at 1, the data to be processed Dn including the median is extracted from the data to be processed Dn by the data extracting means 12. At this time, the data extracting means 12 composed of [n + 1] / 2 comparing and exchanging means Ci compares the m + 1th pieces of data Dn to be operated from the foremost part or the last part. The maximum value is extracted, and the maximum value of the operand data Dn is exchanged with the foremost or last operand data Dn.

When the maximum value among the (m + 1) -th to-be-processed data Dn from the foremost or last part is exchanged with the foremost or last part of the data to be processed Dn, the data extracting means 12 stores the data. 11 read areas are sequentially changed,
M + from the forefront or end of the changed read area
The maximum value among the first data Dn to be processed is exchanged with the foremost or last data Dn.

At this time, for example, the extracted data to be operated Dn is temporarily stored in the auxiliary storage means 14 via the control means 15. For this reason, it is possible to implement the shift division method of outputting the median value extracted based on the change of the readout area of the data to be operated Dn and the exchange of the maximum value from the median value output means 13.

Thus, in the field of image processing and audio processing, even if the amount of data handled increases due to the usage of the user, the data in the comparison / exchange means Ci for sequentially extracting the maximum value from the data to be operated on. The number of comparisons is smaller than in the conventional example. In addition, it is possible to minimize an increase in hardware constituting the system.

Further, according to the second data processing device of the present invention, in the first data processing device, the comparing and exchanging means Ci compares the data to be processed Dn up to the (m + 1) -th data from the forefront or the last. , The minimum value of the data to be operated Dn is extracted, and the minimum value of the data to be operated Dn is exchanged with the foremost or last data Dn to be operated.

For this reason, as in the first data processing apparatus, in the field of image processing and audio processing, even if the amount of handled data increases due to the manner of use by the user, the data to be processed is sequentially reduced to the minimum value. The number of data comparisons in the comparison and exchange means Ci for extracting a value is smaller than in the conventional example. In addition, it is possible to minimize an increase in hardware constituting the system.

As a result, as in the first data processing device, it is possible to reduce the processing time for the median value calculation and to achieve high-speed data processing in the image processing field and the like. Further, according to the first data processing method of the present invention, as shown in the processing flow chart of FIG. When the maximum value is extracted,
In step P3, the maximum value of the operation data Dn is exchanged with the foremost or last operation data Dn. Thereafter, in step P4, the read area of the operation data Dn is sequentially changed. A value is extracted, and the maximum value is exchanged with the data Dn at the forefront or last part of the read area which is sequentially changed.

For this reason, in the conventional example, including the output processing of the minimum value of the m + 1 pieces of operation data Dn from the front or rearmost part rearranged with respect to the odd number operation data Dn in step P6. In comparison, the number of data comparisons can be reduced.

For example, according to the conventional bubble sorting method, assuming that the number of data to be operated is n [odd] and the number of comparisons is k, the relation follows the relational expression of k = 3/8 · (n ² −1). However, according to the shift division method according to the present invention, assuming that the number of comparisons is q, it follows the relational expression of q = (n ² + 2n−3) / 4.

As a result, as the amount of data to be handled increases, the number of comparisons can be reduced to about 2/3 as compared with the conventional example, and the comparison time and comparison amount can be reduced. It becomes possible.

This eliminates the dependence on the bubble sort method or the quick sort method for calculating the median of the data to be operated, and calculates the median at a high speed based on the shift division method according to the present invention. It is possible to speed up data processing by reducing the number of data comparisons.

According to the second data processing method of the present invention, as shown in the processing flow chart of FIG. 2, m + 1 from the forefront or rearmost part subjected to the array processing in step P2A.
The minimum value is extracted with respect to the first piece of data Dn to be processed, and then, at step P6A, based on the extraction processing, m + 1 pieces of data are rearranged with respect to the odd number of pieces of data Dn to be rearranged. The maximum value in the operation data Dn is output.

Therefore, as in the first data processing method, the number of data comparisons can be reduced as compared with the conventional example, and the comparison time and comparison amount can be reduced.

Thus, the median value can be calculated at a high speed based on the shift division method according to the present invention, and the data processing can be speeded up by reducing the number of data comparisons.

[0040]

Next, an embodiment of the present invention will be described with reference to the drawings. 3 to 12 are diagrams illustrating a data processing device and a data processing method according to an embodiment of the present invention, respectively.

(1) Description of First Embodiment FIG. 3 is a block diagram of a median value arithmetic unit according to a first embodiment of the present invention, and FIG. 4 is a diagram for explaining its function. .

For example, in FIG. 3, a median value calculating device for calculating a median value in an odd number of data, which is one of signal processing methods such as noise removal, includes a data array 21, a data extracting unit 22, a minimum value output unit. It comprises a unit 23 and a CPU (central processing unit) 25.

That is, the data array 21 is stored in the storage unit 1
In this embodiment, odd [n = 2m + 1, m ≧ 1] data Dn are sequentially stored. For example, in the data array 21, nine (n = 9, m = 4) arbitrary numerical values, 26, 95, 13, 31, 57, 18, 2
Operand data D1 to D9 such as 1, 5, 90 are sequentially arranged and stored in the memory area (see FIG. 8).

The data extracting section 22 is an embodiment of the data extracting means 12, and extracts the data Dn including the median from the data D1 to D9. Further, unlike the conventional example, the data extracting unit 22 is characterized in that the read area of the data array 21 is sequentially changed.

For example, the data extraction unit 22 calculates [n + 1] /
2, ie [9 + 1] / 2 = 5 comparison and exchange means C
The first to fifth data comparison exchangers C1 to C as an example of i
In the first embodiment, each of the data comparison and exchange units C1 to C5 includes the m + 1th to-be-processed data D1 from the forefront of the to-be-processed data Dn sequentially stored in the memory area to
To Dm + 1, and the operated data D1 to Dm + 1 are compared.
Has the function of extracting the maximum value of the data Dn and exchanging the maximum value Dmax of the data Dn with the data D1 at the forefront.

That is, in the functional explanatory diagram of FIG. 4, the first to fifth data comparing and exchanging units C1 to C5 correspond to FIG.
When the first data comparison exchanger C1 is activated as shown in FIG. 7, the other second to fifth data comparison exchangers C2 to C2
5 is inactivated. At this time, the memory area ~
The data D1 to D5 from the foremost part to the fifth part of the processed data Dn sequentially stored in the processing data Dn are compared with each other, and the maximum value Dmax among the processed data D1 to D5 is extracted. The maximum value Dmax of Dn and the foremost processed data D
Replace with 1.

Similarly, when the second data comparing and exchanging unit C2 is activated as shown in FIG.
The third to fifth data comparison exchangers C1 and C3 to C5 are inactivated. At this time, up to the fifth data D2 to D6 from the foremost part of the data Dn sequentially stored in the memory area are compared, and the data D2
The maximum value Dmax is extracted from .about.D6, and the maximum value Dmax of the data Dn is exchanged with the data D2 at the forefront.

Similarly, when the fifth data comparison exchanger C5 is activated as shown in FIG. 4C, the other first to fourth data comparison exchangers C1 to C4 are inactive. Is becoming At this time, up to the fifth data D5 to D9 from the forefront of the data Dn sequentially stored in the memory area are compared, and the data D5 to D9 are compared.
9 to extract the maximum value Dmax from the data Dn
Is exchanged with the foremost processed data D5.

Therefore, in the embodiment of the present invention, the above-described relay control (shift division control) can be performed between the first to fifth data comparison exchangers C1 to C5. The minimum value output unit 23 is an embodiment of the median value output means 13 and outputs a median value among the extracted data D1 to D5. The minimum value output unit 23 is connected to an output line of the memory area of the data array 21 and the data D1 to D5 arranged in the memory area are arranged.
Is output, that is, the median value among the given nine data to be operated. In the embodiment of the present invention, arbitrary numerical values, 26, 95, 13, 31, 31, 57, 1
A median value of 26 among 8, 21, 5, 90 can be output.

The CPU (central processing unit) 25 is an embodiment of the control means 15 and controls the input and output of the data array 21, the data extraction unit 22, and the minimum value output unit 23.

As described above, according to the median value arithmetic unit according to the first embodiment of the present invention, as shown in FIG. 1, the data array 21, the data extraction unit 22, and the minimum value output unit 23 are provided. The data extraction unit 22 sequentially changes the read area of the data array 21.

For example, when the odd [n = 9, m = 4] pieces of data D1 to D9 are sequentially stored in the data array 21 via the CPU 25, the median value among the pieces of data D1 to D9 is calculated. Are extracted by the data extracting unit 22. At this time, the data extraction unit 22 including the five data comparison exchangers C1 to C5
The m + 1-th processed data D1 to D5 from the foremost part are compared, the maximum value among the processed data D1 to D5 is extracted, and the maximum value Dmax of the processed data D1 to D5 is determined as the foremost part. It is exchanged with the operation data D1.

When the maximum value Dmax of the first to fifth operation data D1 to D5 from the memory area is exchanged with the foremost operation data D1, the data extraction unit 22 outputs the data. The read area of the array 21 is sequentially changed, and the maximum value Dmax of the fifth to the fifth data D2 to D6 from the foremost part of the changed read area is exchanged with the foremost data D2. .

For this reason, it is possible to implement a shift division method in which the median value extracted based on the change of the read area of the operated data D1 to D9 and the exchange of the maximum value Dmax is output from the minimum value output unit 23. Becomes

As a result, in the field of image processing and audio processing, even if the amount of data handled increases due to the manner of use by the user, the maximum value D is sequentially selected from the data to be processed.
The number of data comparisons in the data comparison exchangers C1 to C5 for extracting max is smaller than in the conventional example. In addition, it is possible to minimize an increase in hardware constituting the system.

Next, the median value calculating method according to the first embodiment of the present invention will be described while supplementing the operation of the device. FIG. 5 is a processing flowchart of the median value calculation according to the first embodiment of the present invention, and FIGS. 6 to 8 show supplementary explanatory diagrams (parts 1 to 3) thereof.

For example, nine (n = 9, m = 4) arbitrary numerical values, 26, 95, 13, 31, 57, 18, 21, 21,
In the case of calculating the median from among the data to be processed D1 to D9 consisting of 5, 90, first, in FIG. 5, in step P1, odd [n = 9 = 2m + 1, 4 = m ≧ 1] The array processing of the data D1 to D9 is performed.

At this time, for example, FIG.
As shown in (a), D1 = numerical value 26 in the first memory area of the data array 21 and D1 in the second memory area.
2 = 95, D3 = numerical value 13 in the third memory area, D4 = 31 in the fourth memory area, D5 = numerical value 57 in the fifth memory area, D6 = 1 in the sixth memory area
8, D7 = numerical value 21 in the seventh memory area, D8 = 5 in the eighth memory area, D9 in the ninth memory area
= Numerical value 90 is stored.

Next, the maximum value Dmax is extracted from the m + 1 = 5th data D1 to D5 from the foremost part which has been arrayed in step P2. Here, FIG.
As shown in (b), 1, 2, 3, m, m +
As shown in FIG. 8B, up to the fifth data D1 to D5 to be operated, for example, numerical values 26, 95, 13, 31,
The maximum value Dmax = 95 out of 57 is extracted by the first data comparison and exchange C1.

Further, at step P3, the operation data D1
The maximum value Dmax of .about.D5 is exchanged with the forefront data D1. Here, the maximum value Dmax = 95 and the numerical value 2
6 are exchanged by the first data comparison exchange C1.

Thereafter, in step P4, the data array 21
, The read area of the operated data D1 to D9 is shifted by one. At this time, the control right is transferred from the first data comparison and exchange C1 to the second data comparison and exchange C2, and a transition is made from the read area of the memory area to the read area of the memory area.

Next, in step P5, the maximum value Dmax is extracted from the shifted data D2 to D6. Here, as shown in FIG. 6C, the data to be processed D2 to D6 from the foremost part after the shift to the fifth of 2, 3, m, m + 1, m + 2 are shown in, for example, FIG. As described above, the maximum value Dmax = 57 is extracted from the numerical values 26, 13, 31, 57 and 18 by the second data comparison and exchange C2.

Next, in step P6, the data to be operated D2
An exchange process is performed between the maximum value Dmax in D6 and the data D2 at the forefront of the memory area. At this time, the maximum value Dmax = 57 and the numerical value 26 are exchanged by the second data comparison exchange C2.

Thereafter, at step P7, the data array 21
It is determined whether or not all of the remaining memory areas have been completed. At this time, if all the reading is not completed (NO), the process returns to Step P4, and the read area is further shifted by one. If all the processing has been completed (YES), the program shifts to Step P8.

In the embodiment of the present invention, since the processing has not been completed, the process returns to step P4, and the read area is further shifted by one. In step P5, the processed data D3 to D7 after the shift are shifted. Extraction processing of the middle maximum value Dmax is performed. Here, as shown in FIG.
Maximum value Dmax = 3 out of 3, 31, 26, 18, and 21
1 is extracted by the third data comparison and exchange C3.

Next, at step P6, the operation data D3 to
The maximum value Dmax in D7 is exchanged with the data D3 at the forefront of the memory area. At this time, the maximum value Dmax = 31 and the numerical value 13 are exchanged by the third data comparison and exchange unit C3.

Further, returning to step P4, the read area is further shifted by one, and in step P5, the maximum value Dmax is extracted from the shifted data D4 to D8. Here, as shown in FIG.
Maximum value Dmax = 26 from among 3,26,18,21,5
Is extracted by the fourth data comparison and exchange unit C4.

Next, at step P6, the operation data D4 to
The maximum value Dmax of D8 is exchanged with the data D4 at the forefront of the memory area. At this time, the maximum value Dmax = 26 and the numerical value 13 are exchanged by the fourth data comparison and exchange unit C4.

Further, returning to step P4, the read area is further shifted by one, and in step P5, the maximum value Dmax is extracted from the shifted data D5 to D9. Here, as shown in FIG. 7A, from the forefront after the last shift, m + 1, m + 2, m + 3, 2m, 2
The data to be operated D5 to D9 up to the fifth of m + 1, for example, as shown in FIG.
The maximum value Dmax = 90 out of 5, 90 is extracted by the fifth data comparison and exchange C5.

Next, at step P6, the data to be operated D5
An exchange process is performed between the maximum value Dmax of D9 and the data D5 at the forefront of the memory area. At this time, the maximum value Dmax = 90 and the value 13 are exchanged by the fifth data comparison and exchange unit C5.

As a result, the output of the minimum value Dmin of m + 1 = 5 pieces of data D1 to D9 from the foremost part rearranged in relation to the nine pieces of data D1 to D9 in step P8 is completed. Do the processing. At this time, FIG.
As shown in FIG.
3... Up to the fifth data D1 to D of m and m + 1
5, for example, as shown in FIG. 8 (f), rearranged numerical values 95, 57, 31, 26, 90, 18, 21, 5, 1
M + 1 = 5 pieces of operation data D1 to D5 from the front of
Can be output as the median value of the minimum value Dmin = 26.

As described above, according to the median value calculating method according to the first embodiment of the present invention, as shown in the processing flowchart of FIG. When the maximum value Dmax is extracted from the operation data D1 to D5, the maximum value Dmax of the operation data D1 to D5 and the foremost operation data D1 are exchanged in step P3. At P4 to P7, the read area of the data to be processed D2 to D9 is sequentially changed, and the maximum value Dmax is extracted based on the data, and the maximum value Dmax and the data to be processed Dn at the forefront of the sequentially changed read area are changed. Has been exchanged.

For this reason, the output processing of the minimum value Dmin of the rearmost five processed data D1 to D5 related to the odd number of processed data D1 to D9 in step P8 and Compared with the example, the number of data comparisons can be reduced.

For example, according to the conventional bubble sorting method, if the number of data to be operated is n = 9 and the number of comparisons is k, k = 3/8 · (n ² −1) = 30. But,
According to the shift division method according to the present invention, the number of comparisons is represented by q
Then, q = (n ² + 2n−3) / 4 = 24.

As a result, as the amount of data to be processed increases, the number of comparisons can be reduced to about 2/3 as compared with the conventional example, and the comparison time and the amount of comparison can be reduced. Can be achieved.

This eliminates the dependence on only the bubble sort method or the quick sort method for calculating the median value of the data to be operated, and calculates the median value at high speed based on the shift division method according to the present invention. It is possible to speed up data processing by reducing the number of data comparisons.

In the first embodiment of the present invention, the maximum value Dma of the data Dn to be operated is
Although the case where x is extracted has been described, the same effect can be obtained by extracting the maximum value Dmax of the data Dn to be operated from the last part of the memory area.

(2) Description of the Second Embodiment FIG. 9 is a block diagram of a median value calculating device according to a second embodiment of the present invention, and FIG. 10 is a functional explanatory diagram thereof. .

The second embodiment differs from the first embodiment in that a data extraction / distribution unit 32 is provided instead of the data extraction unit 22, and a sub-array 24 and a comparator 26 are provided.
Is provided.

That is, the data extracting / distributing unit 32 is another embodiment of the data extracting means 12, and comprises data comparing and exchanging units C1 to C5 as in the first embodiment (see FIG. 3).
The function of each of the data comparing / exchanging units C1 to C5 is different from that of the first embodiment in that the m + 1-th processed data D1 to D5 are compared from the forefront part. The minimum value Dmin is extracted, the minimum value is exchanged with the foremost data D1, and the exchanged minimum value Dmin is distributed to the sub-array 24 via the switching unit.

In the function explanatory diagram of FIG. 10, the second data comparison and exchange unit C2 is connected to the second data comparison and exchange unit C2 as shown in FIG.
Is activated, the other first, third to fifth data comparison exchangers C as shown in FIG.
1, C3 to C5 are inactivated. At this time, the fifth data D2 to D6 from the foremost part of the data Dn sequentially stored in the memory area are compared to determine the minimum value Dmin of the data D2 to D6. The minimum value Dmin of the processed data Dn is exchanged with the foremost processed data D2, and the exchanged minimum value Dmi is extracted.
n to the subarray 24.

Similarly, when the fifth data comparison exchange C5 is activated as shown in FIG. 10B, the other first to fourth data comparison exchanges as shown in FIG. C1
To C4 are inactivated. At this time, 5 bits from the forefront of the data to be operated Dn sequentially stored in the memory area
By comparing the data D5 to D9 up to the first data, a minimum value Dmin of the data D5 to D9 is extracted, and the minimum value Dmin and the data D5 at the forefront are exchanged.
The exchanged minimum value Dmin is output to the subarray 24.

Therefore, in the second embodiment of the present invention, first to
Between the fifth data comparison exchangers C1 to C5, in addition to the relay control as in the first embodiment, the minimum value Dmin
Can be output to the outside.

The sub-array 24 is an embodiment of the auxiliary storage means 14, and includes five extracted data D1-D5.
Is temporarily stored. The comparator 26 outputs the maximum value Dmax among the five operated data D1 to D5 as a median value.

As described above, according to the median value arithmetic device according to the second embodiment of the present invention, in the median value arithmetic device of the first embodiment, the data comparison exchangers C1 to C are 5 By comparing the first to third pieces of data D1 to D5, a minimum value Dmin of the pieces of data D1 to D5 is extracted,
The minimum value Dmin is exchanged with the foremost processed data Dn, which is output to the subarray 26 via the switching unit.

For this reason, similarly to the median arithmetic unit according to the first embodiment, in the field of image processing and audio processing, even when the amount of data handled increases due to the usage of the user, the data to be operated on The number of data comparisons in the data comparison exchangers C1 to C5 for sequentially extracting the minimum value from the center becomes smaller than in the conventional example. In addition, it is possible to minimize an increase in hardware constituting the system.

As a result, as in the first embodiment, high-speed data processing can be achieved in the field of image processing and the like by shortening the processing time for the median value calculation. next,
Regarding the median value calculation method according to the second embodiment of the present invention,
A description will be given while supplementing the operation of the device.

FIG. 11 is a processing flowchart of the median value calculation according to the second embodiment of the present invention, and FIG. 12 is a supplementary explanatory diagram thereof. For example, nine arbitrary numerical values, 26, 95, 13, 31, 57, 18, 21, 5,
When calculating the median value from among the data to be operated D1 to D9 consisting of 90, first, in FIG.
When 1, the odd [n = 9 = 2m + 1, 4 = m ≧ 1] array processing of the data to be processed D1 to D9 is performed.

At this time, for example, as shown in FIG. 12, in the first to ninth memory areas of the data array 21, numerical values 26, 95, 13, 31, and
57, 18, 21, 5, 90 are respectively stored.

Next, a process of extracting the minimum value Dmin from the m + 1 = 5th data D1 to D5 from the foremost portion subjected to the array processing in step P2 is performed. Here, FIG.
As shown in (b), numerical values 26, 95, 13, 31, 5
7 is the first data comparison exchanger C1.
Is extracted by

Further, at step P3, the operation data D1
Exchange processing between the minimum value Dmin of .about.D5 and the foremost processed data D1. Here, the minimum value Dmin = 13 and the numerical value 2
6 are exchanged by the first data comparison and exchange unit C1, and the data is transferred to the array 24 through the switching unit.

Thereafter, in step P4, the data array 21
, The read area of the operated data D1 to D9 is shifted by one. At this time, the control right is transferred from the first data comparison and exchange C1 to the second data comparison and exchange C2, and a transition is made from the read area of the memory area to the read area of the memory area.

Next, at step P5, a process of extracting the minimum value Dmin from the shifted data D2 to D6 is performed. Here, as shown in FIG.
The minimum value = 18 out of 6, 31, 57 and 18 is extracted by the second data comparison and exchange C2.

Next, at step P6, the operation data D2
An exchange process is performed between the minimum value Dmin of D6 and the data D2 at the forefront of the memory area. At this time, the minimum value Dmin = 18 and the numerical value 95 are exchanged by the second data comparison and exchange unit C2, and the data is transferred to the array 24 via the switching unit.

Thereafter, in step P7, the data array 21
It is determined whether or not all of the remaining memory areas have been completed. At this time, if all the reading is not completed (NO), the process returns to Step P4, and the read area is further shifted by one. If all the processing has been completed (YES), the program shifts to Step P8.

In the embodiment of the present invention, since the processing has not been completed, the process returns to step P4, and the read area is further shifted by one. In step P5, the processed data D3 to D7 after the shift are shifted. An extraction process of the minimum value Dmin is performed. Here, as shown in FIG.
Minimum value Dmin = 2 out of 6, 31, 57, 95 and 21
1 is extracted by the third data comparison and exchange C3.

Next, at step P6, the data D3 to
An exchange process is performed between the minimum value Dmin of D7 and the data D3 at the forefront of the memory area. At this time, the minimum value Dmin = 21 and the numerical value 26 are exchanged by the third data comparing / exchanging unit C3, and the data is transferred to the array 24 via the switching unit.

Further, returning to step P4, the read area is further shifted by one, and in step P5, the minimum value Dmin is extracted from the shifted data D4 to D8. Here, as shown in FIG.
The minimum value Dmin = 5 is extracted by the fourth data comparison and exchange C4 from 1,57,95,26,5.

Next, in step P6, the data D4 to
Exchange processing is performed between the minimum value Dmin of D8 and the data D4 at the forefront of the memory area. At this time, the minimum value Dmin = 5 and the numerical value 31 correspond to the fourth data comparison and exchange C
Replaced by 4.

Further, returning to step P4, the read area is further shifted by one, and in step P5, the process of extracting the minimum value Dmin from the shifted data D5 to D9 is performed. Here, as shown in FIG.
7,95,26,31,90 minimum value Dmin = 2
6 is extracted by the fifth data comparison and exchange C5.

Next, at step P6, the data to be operated D5
An exchange process is performed between the minimum value Dmin of D9 and the data D5 at the forefront of the memory area. At this time, the minimum value Dmin = 26 and the numerical value 57 are exchanged by the fifth data comparison and exchange unit C5, and the data is transferred to the array 24 via the switching unit.

As a result, the output of the minimum value Dmin of the (m + 1) = 5 pieces of data D1 to D9 from the foremost part rearranged with respect to the nine pieces of data D1 to D9 in step P8 is completed. Do the processing. At this time, FIG.
, The rearranged numbers 13, 18, 21,
5, 26, 95, 57, 31, 90 are read from the sub-array 24 and the comparator 26 calculates m + 1
= Maximum value Dmax of five pieces of data D1 to D5 =
26 are extracted and can be output as a median.

As described above, according to the median value calculating method according to the second embodiment of the present invention, as shown in the processing flowchart of FIG. The minimum value Dmin is extracted according to the data D1 to D5, and then, at step P7, the five operands from the forefront rearranged according to the extraction data according to the nine data D1 to D9 are rearranged. Data D1 to D5
Is output.

Therefore, as in the first embodiment, the number of data comparisons can be reduced as compared with the conventional example.
The comparison time and the amount of comparison can be reduced. Accordingly, the median value can be calculated at high speed based on the shift division method according to the present invention, and the data processing can be speeded up by reducing the number of data comparisons.

In the second embodiment of the present invention, the minimum value Dmi of the data Dn to be operated is
Although the case where n is extracted has been described, the same effect can be obtained by extracting the maximum value Dmin of the data Dn to be operated from the last part of the memory area.

[0106]

As described above, according to the data processing apparatus of the present invention, there are provided storage means, data extraction means, median value output means, auxiliary storage means, and control means. Are sequentially changed.

Therefore, it is possible to implement a shift division method in which the median value extracted based on the change of the readout area of the data to be operated and the exchange of the maximum value and the minimum value is output from the median value output means. . As a result, in the field of image processing and audio processing, even if the amount of data handled increases due to the usage of the user, the data in the comparison and exchange means for sequentially extracting the maximum value and the minimum value from the data to be operated on. The number of comparisons is smaller than in the conventional example. In addition, it is possible to minimize an increase in hardware constituting the system.

Further, according to the data processing method of the present invention,
When the maximum value or the minimum value is extracted from the m + 1-th processed data from the foremost part or the last part of the array processing, the maximum value or the minimum value and the foremost or last part of the processed data are extracted. Is exchanged, and thereafter, the read area of the data to be operated is sequentially changed, the maximum value or the minimum value is extracted based on this, and the maximum value or the minimum value is sequentially changed to the forefront of the read area or the read area that is sequentially changed. The data to be processed is exchanged with the last data.

For this reason, including the output processing of the minimum value or the maximum value of the m + 1 pieces of operation data from the frontmost or rearmost part rearranged with respect to the odd number of operation data, compared with the conventional example, It is possible to reduce the number of data comparisons. As a result, even when the amount of handled data increases, the number of comparisons can be reduced to about 2/3 as compared with the conventional example, and the comparison time and comparison amount can be reduced. Becomes

As a result, the median value can be calculated at high speed based on the shift division method according to the present invention, and the efficiency of the arithmetic processing can be increased, which greatly contributes to speeding up the data processing.

[Brief description of the drawings]

FIG. 1 is a principle diagram of a data processing device according to the present invention.

FIG. 2 is a principle diagram of a data processing method according to the present invention.

FIG. 3 is a configuration diagram of a median value calculation device according to a first example of the present invention.

FIG. 4 is a functional explanatory diagram of the median value calculating device according to the first embodiment of the present invention.

FIG. 5 is a processing flowchart of a median value calculation according to the first embodiment of the present invention.

FIG. 6 is a supplementary explanatory diagram (part 1) of the median value calculation process according to the first embodiment of the present invention.

FIG. 7 is a supplementary explanatory diagram (part 2) of the median value calculation process according to the first embodiment of the present invention.

FIG. 8 is a supplementary explanatory diagram (part 3) of the median value calculation process according to the first embodiment of the present invention.

FIG. 9 is a configuration diagram of a median value calculation device according to a second example of the present invention.

FIG. 10 is an explanatory diagram of functions of a median value calculation device according to a second example of the present invention.

FIG. 11 is a processing flowchart of a median value calculation according to the second embodiment of the present invention.

FIG. 12 is a supplementary explanatory diagram of the median value calculation processing according to the second example of the present invention.

FIG. 13 is an explanatory diagram of a median value calculation device according to a conventional example.

[Explanation of symbols]

 11: storage means, 12: data extraction means, 13: median output means, 14: auxiliary storage means, 15: control means, Ci: comparison and exchange means, Dn [n = 2m + 1]: operated data.

Claims (7)

(57) [Claims] A storage means (11) for sequentially storing odd [n = 2m + 1, m ≧ 1] pieces of operation data (Dn);
Data extraction means (12) for extracting operation data (Dn) including a median from the operation data (Dn);
Median value output means (13) for outputting a median value of the extracted data to be operated (Dn), wherein the data extraction means (12) sequentially changes the read area of the storage means (11). Characteristic data processing device. 2. The data processing apparatus according to claim 1, wherein said data extracting means comprises [n + 1] / 2 comparison and exchange means (Ci), and said comparison and exchange means (Ci).
i) compares the (m + 1) -th data to be operated (Dn) from the foremost part or the last part, extracts the maximum value among the data to be operated (Dn), and calculates the maximum value of the data to be processed (Dn). A data processing device for exchanging a value with the foremost or last data to be operated (Dn). 3. The data processing device according to claim 2, wherein the comparison and exchange means (Ci) compares the (m + 1) th data to be operated (Dn) from the foremost part or the last part to obtain the data to be operated on (Dn). Dn), wherein the minimum value of the data to be processed (Dn) is extracted and the minimum value of the data to be processed (Dn) is exchanged with the foremost or last data to be processed (Dn). 4. A data processing apparatus according to claim 1, further comprising an auxiliary storage means for temporarily storing said extracted data to be processed (Dn). . 5. A data processing apparatus according to claim 1, wherein said storage means (11), data extraction means (12), median value output means (13) and auxiliary storage means (14). A data processing device provided with control means (15) for controlling input / output. 6. Arrangement processing of odd [n = 2m + 1, m ≧ 1] pieces of operation data (Dn) is performed, and the m + 1-th operation data (Dn) from the foremost or last part of the array processing is processed. ), The maximum value of the data to be operated (Dn) is exchanged with the foremost or last data to be operated (Dn), and thereafter the data to be operated (Dn) is exchanged. ) Is sequentially changed, the maximum value of the data to be operated (Dn) is extracted, and the maximum value of the data to be operated (Dn) and the forefront or last part of the sequentially changed read area are changed. Exchange processing with the operated data (Dn)
M + 1 pieces of data (Dn) from the forefront or rearmost rearranged with respect to the odd number of pieces of data (Dn)
a data processing method for performing output processing of a minimum value in n). 7. The data processing method according to claim 6, wherein after the array processing of the data to be operated (Dn), the data to be operated (Dn) from the foremost part or the last part of the array processing to the (m + 1) -th element , The minimum value is extracted, and the maximum of m + 1 pieces of operation data (Dn) from the frontmost or rearmost part rearranged according to the odd number of operation data (Dn) based on the extraction processing. A data processing method characterized by performing value output processing.