JPH0416809B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention provides a method for selecting n pieces of data having the largest or smallest value from N pieces of data used in an optical character reading device, etc., which can be realized at high speed with a small-scale circuit. Regarding the method.

Approximately 2000 commonly used kanji with Japanese optical character reader
Store the characters in the first memory, compare the read characters with approximately 2000 kanji based on the similarity value, store this value in the second memory, and select the one with the highest degree of similarity. is output and processed multiple times. In such a case, when selecting predetermined n pieces of data having the largest or smallest value from among the N pieces of data at high speed, the following selection circuit has conventionally been used. FIG. 1 is a block diagram of a conventional selection circuit, and FIG. 2 shows a table for selecting three pieces of data having large values from among the seven pieces of data in the case of FIG.

In the figure, 1 is a memory that stores N pieces of data, 2 is a control circuit, and 3 is a driver. To explain the principle using FIG. are stored respectively, and the addresses where these seven pieces of data are stored (values from addresses 1 to 7 in FIG. 2) are controlled by the control circuit 2, and the maximum value 10 and its address 2 are memorized. The contents of address 1, 4, and the maximum value, 10, of address 2 are exchanged as shown in b. Next, the contents of the data stored in addresses 2 to 7 are controlled by the control circuit 2, and the maximum value 9 and the address 7 are checked.
is stored and replaced with the content 4 at address 2 as shown in c. Next, the data from address 3 to address 7 is controlled by the control circuit 2, and the maximum value 7 and its address 5 are stored, and the content 6 of address 3 is replaced with 7 as shown in d. If the contents of addresses 1 to 3 are outputted via the driver 3, three pieces of data with large values can be obtained. If you want to select 3 small pieces of data, use the same method.In case A, replace the data with the minimum value 1 with 4, which is the data at address 1.In the case B, use the data with the minimum value 2 from addresses 2 to 7. If you replace the data with the data at address 2, and in the case of C, replace the data with the minimum value 4 from addresses 3 to 7 with the data at address 3, three small pieces of data will be stored at addresses 1 to 3, and this All you have to do is output . However, the memory 1 used in Japanese optical character reading devices, which compares approximately 2,000 characters and indicates the degree of similarity as a value and temporarily stores the data, has the disadvantage of being large in size.

SUMMARY OF THE INVENTION An object of the present invention is to provide a selection method that can perform selection at high speed using a small-scale circuit in order to eliminate the above-mentioned drawbacks.

[The numbers in parentheses below correspond to the numbers of the embodiment shown in FIG. 3. ] A memory 10 that sequentially reads out N pieces of data, stores n pieces of data, and outputs the stored data, a register 5 that stores the address corresponding to the minimum value, and a clock that counts. The counter value is used as an address, and is input to the memory 10 via the selector 7, and input to the register 5, and is also input to the first comparator 8, which compares it with the value of n and resets the counter 6 when it reaches n. a selector 7 that selects whether the output value of the counter 6 is the value stored in the register 5 and gives an address to the memory 10; a second comparator 11 which compares the values of and sends a control signal to the selector 7 and the register 5, and which sends a control signal to control the write signal; Minimum value detection means 12 and 4 are provided for detecting the minimum value and sending a control signal to the selector 7 and the register 5 to store the address at the time of the minimum value in the register 5. Initially, the selector 7 detects the counter. 6 side is selected and inputted n data are sequentially stored in the memory 10, and the stored data are sequentially output to the second comparator 11, and the second comparator 11 compares them with the input data. , when the minimum value is detected, the address of the counter 6 at that time is stored in the register 5 by the control signal from the second comparator 11, and the selector 7 selects the register 5 side and stores it in the memory. 10 outputs the minimum value and inputs it to the second comparator 11, compares it with input data, and if the input data is larger, operates a write signal with a control signal from the second comparator 11, The input data is replaced with the minimum value and stored at the address position of the minimum value, and the n pieces of data are sent to the minimum value detection means 12, 4 to detect the minimum value, and the address of the minimum value is detected by the control signal. The selector 7 selects the register 5 side, inputs the minimum value to the second comparator 11, repeats the operation of comparing with the input data, and stores the top n data in the memory 10. By storing the data in , it becomes possible to select the top n data at high speed with a small-scale circuit.

In addition, there is a memory 10 that sequentially reads out N pieces of data, stores n pieces of data, and outputs the stored data, a register 5 that stores the address corresponding to the maximum value, and a clock that counts. The counter value is used as an address, and is input to the memory 10 via the selector 7, and input to the register 5, and is also input to the first comparator 8, which compares it with the value of n and resets the counter 6 when it reaches n. a selector 7 which selects either the output value of the counter 6 or the value stored in the register 5 and gives an address to the memory 10; Compare the values and send the control signal to the selector 7 and register 5.
a second comparator 11 which sends a control signal to control the write signal to the selector 7 and the register 5; maximum value detecting means 12, 4 for storing the address of the maximum value in the register 5; first, the selector 7 selects the counter 6 side and the input n data are sequentially transferred to the memory; 10 and sequentially outputs the stored data to the second comparator 11, and compares it with the input data in the second comparator 11. When the maximum value is detected, the second comparator 11 outputs the stored data sequentially to the second comparator 11. With the first control signal, the current address of the counter 6 is stored in the register 5, and the selector 7 selects the register 5 side to output the maximum value from the memory 10, and the second It is input to the comparator 11 and compared with the input data, and if the input data is smaller, the second comparator 11
The write signal is activated by the control signal from above, the input data is replaced with the maximum value and stored at the address position of the maximum value, and the n pieces of data are sent to the maximum value detection means 12 and 4 to detect the maximum value. The address of the maximum value is stored in the register 5 by the detection control signal, the selector 7 selects the register 5 side, the maximum value is input to the second comparator 11, and the operation of comparing the input data is repeated. By storing the n lowest data in the memory 10, it becomes possible to select the n lowest data at high speed with a small-scale circuit. An embodiment of the present invention will be described below with reference to the drawings.

FIG. 3 is a block diagram of the selection circuit according to the embodiment of the present invention, and FIG. 4 is a time diagram showing the operation when n pieces of data are first stored in the buffer memory (hereinafter referred to as memory) in the case of FIG. 5 is a time chart showing the operation when the input data is smaller than the minimum value in the memory in the case of FIG. 3.

In the figure, 10 is memory 1 as a buffer memory.
1, 4, and 8 are comparators, 12 is a register, 5 is a register that stores the address of the minimum value data, 6 is a counter that counts the clock, 7 is a selector, and VAL is a register that stores N pieces of data that are sent sequentially. BADD is the address of memory 10, BFWE is the write signal to memory 10, CNTA is the control signal for whether to use the output of register 5 or the output of counter 6 as address BADD of memory 10, PTST is the counter ACE is the control signal for counter 6, VST is the control signal for storing the output from memory 10 in register 12, CHBF is comparator 11.
The output is a control signal to control whether or not to replace the contents of the memory 10 and to control CNTA and PTST.DSET is a control signal to search for the minimum value after replacing the contents of the memory 10 and a control signal to control PTSC and ACE. show.

Initially, the first n data of the N data sent from a memory (not shown) storing N data is stored in the memory 10. I will explain.

Seven items are selected as N items, and this is the data shown by A in FIG. In other words, 7 pieces of data are 4,
10, 6, 2, 7, 1, and 9, n is 3, and three of the largest values are selected from seven data items.

First, an overview of the operation in FIG. 3 will be explained. Seven pieces of data are stored in a memory (not shown), which is given to the buffer memory 10 as VAL, but this memory has a capacity to store n pieces of data, that is, three pieces of data.

That is, data 4, 10, and 6 are sequentially given to the memory 10 as VAL, but the value counted by the clock counter 6 is used as the address BADD. For example, if the clock counter value is 1, the address is 1, and the count value is 1. If it is 2, it becomes address 2. This count value is given via the selector 7. n is given to one terminal of the comparator 8, and the counter 6 is given as the other input.
is given the output of n comparators,
In this example, it has the function of monitoring so that only three pieces of data are stored in the memory 10.

In addition, in the process of storing 4, 10, and 6 in the memory 10, the comparator 11 detects whether the input data values are large or small.
An operation is performed in which the address corresponding to the smallest value is detected. That is, address 1 when 4 is stored is given as memory BADD, but at the same time 5 is also given to the register. Next, when data 10 is given, the previous 4 and 1
0 is compared with the comparator 11, and since 4 is small, the address 1 is stored as is in the register 5,
Next, when 6 comes, compare the minimum values 4 and 6 with comparator 1.
Compare with 1. Since 4 is small, the value 1 in register 5 does not change.

In this way, out of 7 data, 3 data 4,
10 and 6 are stored at addresses 1, 2, and 3 of memory 10, and address 1 corresponding to the minimum value 4 is stored in register 5.

When the fourth data 2 is given as VAL in this state, the comparator 11 compares it with the minimum value 4 in the memory.

In this case, since the fourth data 2 is smaller than 4, 2 is not stored in the memory, and 4, 10, 6 are still stored in the memory, and 1 indicating the address for data 4 is stored in register 5. is memorized. When the fifth data 7 is given as VAL, this 7 and 4 are compared by the comparator 11. When it is determined that this new data 7 is greater than 4, the contents of address 1, which contained 4, are changed from data 4 to data 7.

In the memory 10, data 7, 10, and 6 are stored at addresses 1, 2, and 3. The smallest data among these three pieces of data is determined by the register 12 and comparator 4 of the minimum value detection means. The details of this discrimination operation will be described later, but the minimum value is 6, and the address 3
, and the contents of register 5 are changed from 1 to 3.

When the sixth data 1 is given as VAL, the comparator 11 compares the minimum value 6 in the memory 10 with the magnitude of 1, and since 6 is larger, data 1 is not stored in the memory. , the contents of the memory 10 and the contents of the register 5 remain unchanged.

When the seventh data 9 is given, comparator 1
1 compares the size, and 9 is greater than 6, so
Data 6 of address 3 is changed to 9, and 3 of register 5 is not changed. However, in this way, 7, 10, and 9 are stored in the memory 10 at addresses 1, 2, and 3 as the three largest data among the seven data, and are selected.

The above is an outline of the operation of the embodiment circuit shown in FIG. 3, and the detailed operation is as follows.

At the start of operation, no data is stored in the memory 10, but when data 4 is given as VAL, the output of the comparator 11
CHBF is in the on state, a pulse is also generated in PTST, and the control signal ACE to counter 6 and memory 1
The write signal BFWE to 0 and the control signal CNTA to select are also in the on state. This is as shown in FIG.

When CNTA is on, the value from counter 6 that counts the clock is selected by selector 7, and this count value 1 is the memory address.
BADD is given to the memory 10 as address 1. Therefore, data 4 as VAL is memory 1
It is stored at address 1 of 0. On the other hand, the count value 1 from the counter 6 is also stored in the register 5.
The output from the counter 6 becomes a new value when PTST is on, but does not change the previous value when it is off.

Furthermore, the output of the counter 6 is given to a comparator 8,
As described above, this comparator has the function of determining when the output from the counter reaches the value n and restricting new storage operations in the memory 10. memory 10 to 4
When CNTA is stored, CNTA is turned off, so the value 1 indicating address 1 of data 4 stored in register 5 is given to memory 10 through selector 7, and the value 1 indicating address 1 of data 4 stored at address 1 is applied to memory 10. The value is simultaneously retrieved to the output Do while being stored. In this state, the next second data 10
is given to the memory 10 as VAL, since CNTA is on at this time, the value 2 counted by the clock counter 6 is transferred to the selector 7.
address BADD to memory selected by
Address 2 is given as , data 10 is stored at address 2 of the memory, and the previous 4 and new 10 are compared in comparator 11 . Since 4 is smaller than 10, CHBF is off at this time, so
Since PTST continues to be off, the value 2 is not given to register 5, and the value 1 remains stored in this register.

That is, the memory 10 has data 4 at addresses 1 and 2.
and 10 are stored, and the value 1 is stored in the register 5 as the address where the minimum value 4 is stored. Since CNTA is off in this state, selector 7 sets the value 1, which is the content of register 5.
Give address 1 to memory 10 as BADD,
Output data 4 of address 1 to Do. When the third data 6 is given, CNTA is turned on again, so the selector 7 selects the value 3 counted by the clock counter 6, gives 3 as the address BADD to the memory 10, and sends the data 6 is stored at address 3.

At the same time, this data 6 is 4 in Do and comparator 1
1 to compare the size. Since 4 is still small, CHBF is off and therefore PTST is also off, so the contents of register 5 remain unchanged. That is, data 4, 10, and 6 are stored at addresses 1, 2, and 3 of the memory 10, and the value 1 corresponding to the address of the smallest data 4 among them is stored in the register 5. Since three pieces of data as n are now stored in the memory 10, this is determined by the comparator 8 and new storage in the memory 10 is blocked.

At this time, CNTA is off, value 1 stored in register 5 is selected by selector 7, BADD is given to memory 10 as address 1, data 4 at address 1 is output as Do, and in that state 4th data 2 is VAL
given as , this means data 4 and comparator 1
1 is compared. In this case, CHBF is turned on when the new data is larger than 4, but in this case, since the new data 2 is smaller than 4, it is turned off. Therefore, no change occurs in the state of register 5. This state is as shown in FIG.

Since CNTA is off in this state, the value 1 of register 5 is given to memory 10 as address 1 via selector 7, and data 4 of address 1 is given to memory 10 as address 1.
is output to Do. The fifth data 7 is VAL
, data 7 and this data 4 are compared by a comparator. Since the new data is greater than 4, CHBF is turned on and the write signal
By means of BFWE and by address 1 which is also present in memory 10, data 7 is stored in place of data 4 at this address location.

That is, in this state, address 1 of memory 10,
Data 7, 10, and 6 are stored in registers 2 and 3, and address 1 is still stored in register 5.

Next, the operation moves to the determination of the minimum value of data 7, 10, and 6. In this case again the control signal CNTA,
ACE is turned on and addresses 1, 1 on memory 10
The data 7, 10, and 6 stored in 2 and 3 are sequentially read out, and the determination of the number of times these three readings are performed is monitored by the comparator 8 in the same way as in the case of writing.

That is, when reading data 7, since CNTA is on, the clock is newly set to counter 6.
The value 1 is selected by the selector 7, address 1 is given to the memory 10 as BADD, and data 7 at address 1 is stored in the register 12.
given to. At the same time, since this PTST is turned on, the value 1 is stored in the register 5.

Note that VST stores the output of memory 10 in register 12.
This is a control signal to be stored in the .

Next, when CNTA is turned on again, the clock is counted by counter 6, the value 2 is selected by selector 7, and address 2 is given to memory 10 as BADD, thereby
10 is read from the memory and compared with the previous 7 in comparator 4. Since 7 is small, DSET is off, so PTST is off, and the count value 2 of the counter does not affect the contents of register 5. is not given and the value 1 is still stored.

When CNTA is turned on again, the counter value 3 passed through the counter 6 is selected by the selector 7, and address 3 is given to the memory 10 as BADD. As a result, data 6 is transferred from address 3.
is read out and compared with unchanged data 7 in register 12 by comparator 4. In this case, since the new data 6 is less than 7, DSET is turned on, which turns on PTST, and the count value of 3 from counter 6 changes to the value 1 in register 5 and is stored. .

In this state, address 1 of memory 10,
Data 7, 10, and 6 are stored in 2 and 3, and 3 corresponds to the address of data 6 as the minimum value.
is stored in register 5. At this time, CNTA
is off, so 3 stored in register 5 is given to memory 10 as address BADD via selector 7, and data 6 at address 3 is
It is output to Do. When the sixth data 1 is given as VAL in this state, 1 and 6 are compared in comparator 11, and since 6 is larger, CHBF is off, PTST is also off, and register 5 still has a value. 3 is memorized.

Since CNTA is off at this time, this 3 is selected again by selector 7 and the address
The data 6 is applied to the memory as BADD, 6 is output to Do, and the seventh data 9 is applied to the comparator 11 as VAL. Since 9 is greater than 6, CHBF is turned on, and 9 is stored in place of data 6 at address 3 in memory 10.

As a result, addresses 1, 2, 3 of memory 10
Of the seven pieces of data 4, 10, 6, 2, 7, 1, and 9, three large pieces of data 7, 10, and 9 will be stored.

The above explained the operation of selecting n pieces of data with a large value, but when selecting n pieces of data with a small value, the minimum value is the maximum value, and when comparing with the comparator 11, when data with a smaller value comes ,Control signal
The same method can be used by turning on CHBF and turning on the control signal DSET when data with a large value is received when comparing to find the maximum value of n data in comparator 4. Among the N data values, n data having a small value are stored in the memory 10 and selected. This is very effective when the value of n is sufficiently smaller than the value of N. The above deals only with values, but if you store values indicating magnitude and related values, such as similarity and character code,
Since the optical character reading device stores the recognition result (character code) and the degree of similarity between it and the input character, it can be used in the matching section of the optical character reading device.

As described above in detail, the present invention has the advantage of being able to select at high speed with a selection circuit having a small circuit configuration.

[Brief explanation of drawings]

Figure 1 is a block diagram of a conventional selection circuit, and Figure 2 is a block diagram of a conventional selection circuit.
The figure shows a table for selecting the three largest pieces of data from the seven pieces of data in the case of Fig. 1, Fig. 3 is a block diagram of the selection circuit of the embodiment of the present invention, and Fig. 4
The figure is a time chart showing the operation when n pieces of data are first stored in the buffer memory in the case of figure 3, and figure 5 shows the value of the input data smaller than the minimum value in the buffer memory in the case of figure 3. This is a time chart showing the operation in this case.

Claims (1)

[Claims] 1. A memory 10 that sequentially reads out N pieces of data, stores n pieces of data, and outputs the stored data, and a register that stores an address corresponding to the minimum value. 5, and a first circuit that counts the clock, uses the counter value as an address, inputs it to the memory 10 via the selector 7, and inputs it to the register 5, and also compares it with the value of n, and resets the counter 6 when it reaches n. the counter 6 which inputs the data to the comparator 8; the selector 7 which selects either the output value of the counter 6 or the value stored in the register 5 and gives an address to the memory 10; and the data output from the memory 10. a second comparator 11 which compares the value with the input data and sends a control signal to the selector 7 and the register 5, and sends a control signal to control the write signal; minimum value detecting means 12 and 4 for inputting the data, detecting the minimum value, and sending a control signal to the selector 7 and the register 5 to store the address at the minimum value in the register 5. The selector 7 selects the counter 6 side and sequentially stores n pieces of input data in the memory 10, and sequentially outputs the stored data to the second comparator 11. When the minimum value is detected, the address of the counter 6 at that time is stored in the register 5 by the first control signal from the second comparator 11, and the selector 7 stores the address of the counter 6 at that time. The register 5 side is selected and the minimum value is outputted from the memory 10 and inputted to the second comparator 11, and compared with the input data.If the input data is larger, the second comparator 11 outputs the minimum value.
The write signal is activated by the control signal of the second one, the input data is replaced with the minimum value and stored at the address position of the minimum value, and the n pieces of data are sent to the minimum value detection means 12, 4 to detect the minimum value. The address of the minimum value is stored in the register 5 by the detection control signal, the selector 7 selects the register 5 side, the minimum value is input to the second comparator 11, and the operation of comparing with the input data is repeated. A selection circuit characterized in that the top n data are stored in the memory 10 by changing the data. 2. A memory 10 that sequentially reads out N pieces of data, stores n pieces of data, and outputs the stored data, a register 5 that stores the address corresponding to the maximum value, and a clock count. The counter value is used as an address, and is input to the memory 10 via the selector 7, and input to the register 5, and is also input to the first comparator 8, which compares it with the value of n and resets the counter 6 when it reaches n. The selector 7 selects between the output value of the counter 6 and the value stored in the register 5 and gives an address to the memory 10; The selector 7 inputs the output data of the memory 10 and inputs the input data. a second comparator 11 which compares the values with and sends a control signal to the selector 7 and the register 5, and sends a control signal to control the write signal; and inputs the n data stored in the memory 10. and maximum value detecting means 12 and 4 for detecting the maximum value and sending a second control signal to the selector 7 and the register 5 to store the address at the time of the maximum value in the register 5. Initially, the selector 7 selects the counter 6 side and sequentially stores n data to be input into the memory 10, outputs the stored data sequentially to the second comparator 11, and inputs the data to the second comparator 11. When the maximum value is detected, the address of the counter 6 at that time is stored in the register 5 using a control signal from the second comparator 11, and the selector 7 selects the register 5 side. Then, output the maximum value from the memory 10 and input it to the second comparator 11, compare it with the input data, and if the input data is smaller, write it using the control signal from the second comparator 11. The signal is operated to replace the input data with the maximum value and store it in the address position of the maximum value, and the n pieces of data are stored in the maximum value detection means 1.
2 and 4 to detect the maximum value, and store the address of the maximum value in the register 5 by a control signal.
The selector 7 selects the register 5 side, inputs the maximum value to the second comparator 11, repeats the operation of comparing with the input data, and stores the lower n data in the memory 10. selection circuit.