US 5,179,717 AGranted

Sorting circuit using first and last buffer memories addressed by reference axis data and chain buffer memory addressed by datum number of the first and last buffer memories

AssigneeManco, Inc.

InventorsSeiichi Sato, Shigeichi Nakamura

Life of this patent

Estimating the term…

Loading patent…

Abstract

A circuit for sorting a plurality of inputted (reference-axis) data includes an index generator for generating an index (datum number) for each of the inputted data; a first buffer memory having storage areas each of which can be addressed by the data, the first buffer memory for storing an index generated by the index generator when the corresponding data is initially inputted into the index generator; a last buffer memory having storage areas each of which can be addressed by the data, the last buffer memory for updating and storing an index generated by the index generator at each time when the corresponding data is inputted thereinto; a chain buffer memory having chain index storage areas each of which can be addressed by the previous index in the chain; a first control for writing a new updated index into a chain index storage area addressed by a before-updated index at each time when the index of the last buffer memory is updated; a second control for writing the index of the data into the chain datum number storage areas so that they will be chained with each other in the ascending or descending order of the sorted data; and a third control for reading the index in the chain index storage areas in accordance with a predetermined read-out rule index. Such an arrangement of the sorting circuit can sort and output a plurality of data in a simple and high-speed manner.

Claims21

Dependent claims

A circuit for sorting a plurality of inputted reference-axis data, comprising:

means for generating a datum number corresponding to each of the inputted reference-axis data;
a first buffer memory having first datum number storage areas which are addressed by said reference-axis data, each of the first datum number storage areas being adapted to store a datum number generated by said datum number generating means when a reference-axis datum corresponding to each of the first datum number storage areas is first inputted into said first buffer memory;
a last buffer memory having last datum number storage areas which are addressed by said reference-axis data, each of the last datum number storage areas being adapted to update and store a datum number generated by said datum number generating means at each time when a reference-axis datum corresponding to each of said last datum number storage areas is inputted into said last buffer memory;
a chain buffer memory having chain datum number storage areas each of which is addressed by the corresponding datum number;
a first control means for writing a new updated datum number into a chain datum number storage area addressed by a before-updated datum number in said last buffer memory at each time when the before-updated datum number is updated;
a second control means for writing a datum number stored in each one of said first datum storage areas and corresponding in a predetermined relation to said datum number of said last datum number storage area into said chain datum number storage area, said chain datum number storage area addressed by said datum number stored in said last datum number storage area after the writing of the numbers of said data into said first and last buffer memories has been completed, thereby causing the reference-axis data to chain in said chain datum number storage areas in ascending or descending order;
and
a third control means for reading the datum numbers out of said chain datum number storage areas in accordance with a predetermined read-out rule and then sorting and outputting the inputted reference-axis data in the sequence of the read-out datum numbers.

5 more elements

A sorting circuit for sorting a plurality of inputted data based on given reference-axis data, comprising:

an information memory for storing the necessary portion of each of said plurality of inputted data with its datum number and sorting means for receiving the reference-axis data in each of said data, said sorting means comprising means for generating a datum number corresponding to each of the inputted reference-axis data;
a first buffer memory having first datum number storage areas which are addressed by said reference-axis data, each of the first datum number storage areas being adapted to store a datum number generated by said datum number generating means when a reference-axis datum corresponding to each of the first datum number storage areas is first inputted into said first buffer memory;
a last buffer memory having last datum number storage areas which are addressed by said reference-axis data, each of the last datum number storage areas being adapted to update and store a datum number generated by said datum number generating means at each time when a reference-axis datum corresponding to each of said last datum number storage areas is inputted into said last buffer memory;
a chain buffer memory having chain datum number storage areas each of which is addressed by the corresponding datum number;
a first control means for writing a new updated datum number into a chain datum number storage area addressed by a before-updated datum number in said last buffer memory at each time when the before-updated datum number is updated;
a second control means for writing a datum number stored in each one of said first datum number storage areas and corresponding in a predetermined relation to said datum number of said last datum number storage area into said chain datum number storage area, said chain datum number storage area addressed by said datum number stored in said last datum number storage area after the writing of the datum numbers into said first and last buffer memories has been completed, thereby causing the reference-axis data to chain in said chain datum number storage areas in ascending order;
and
a third control means for reading the datum numbers out of said chain datum number storage areas in accordance with a predetermined read-out rule and reading the data from said information memory in the order following the datum numbers thus read out.

5 more elements

A sorting circuit for sorting a plurality of reference-axis data, each consisting of a plurality of digits in accordance with a datum number given to each of said reference-axis data, said sorting circuit comprising:

a reference-axis data memory for storing said reference-axis data with their datum numbers;
a datum number pointer for outputting a datum number to said reference-axis data memory as a read-out address and to read the lowest searched digit of each of said reference-axis data from said reference-axis memory in the order following the datum numbers;
a first buffer memory including first datum number storage areas each of which can be addressed based on one of the reference-axis data having a given searched digit and outputted from said reference-axis data memory and for storing a datum number from said address pointer when the corresponding reference-axis datum is initially inputted from said reference-axis data memory into one of said first datum number storage areas;
a last buffer memory including last datum number storage areas each of which can be addressed based on one of the reference-axis data having a given searched digit and outputted from said reference-axis data memory, said last buffer memory being adapted to update a datum number stored in one of the last datum number storage areas into a datum number from said address pointer at each time when the corresponding reference-axis datum is read out from said reference-axis data memory at its storage area;
a chain buffer memory including chain datum number storage areas which can be addressed by the datum numbers;
a first control means for writing a newly updated datum number into a chain datum number storage area addressed by a before-updated datum number at each time when the datum number of said last buffer memory is updated;
a second control means, which is operative after the writing of data into said first and last buffer memories has terminated, for writing a datum number stored in each one of said first datum number storage areas and placed in a predetermined relationship with said datum number of said last datum number storage area into said chain datum number storage area, said datum number storage area addressed by the datum number stored in the last datum number storage area, whereby the datum numbers of the reference-axis data can be written into the chain datum number storage areas to chain said reference-axis data with each other in the ascending or descending order;
a fourth control means for setting the next higher searched digit of a reference-axis datum and for reading the datum numbers from said chain datum number storage areas in accordance with a predetermined read-out rule, said fourth control means being adapted to perform the sorting operation of each of the searched digits such that the set searched digits of said reference-axis data are outputted from said reference-axis data memory to each of said first and second buffer memories in the order following their datum numbers, said sorting operation being repeated while shifting the searched digits by one digit in the order starting from the lowest digit of the reference-axis data and terminating at the highest digit thereof;
and
a third control means operative such that after the highest searched digit has been sorted, the datum numbers written in said chain datum number storage areas being read out therefrom in a predetermined read-out rule, whereby said reference-axis data can be sorted and outputted from said reference-axis data memory in the order following their datum numbers.

7 more elements

A circuit for sorting a plurality of inputted data based on given reference-axis data, said circuit comprising:

an information memory for storing the necessary part of each of said data with its datum number and sorting means for receiving reference-axis data included in each of said data, said sorting means comprising a reference-axis data memory for storing said reference-axis data with their datum numbers;
a datum number pointer for outputting a datum number toward said reference-axis data memory as a read-out address and for reading the lowest searched digits of said reference-axis data from said reference-axis data memory in the order following their datum numbers;
a first buffer memory including first datum number storage areas each of which can be addressed based on one of the reference-axis data having a given searched digit and outputted from said reference-axis data memory and for storing a datum number from said address pointer when the corresponding reference-axis datum is initially inputted from said reference-axis data memory into one of said first datum number storage areas;
a last buffer memory including last datum number storage areas each of which can be addressed based on one of the reference-axis data having a given searched digit and outputted from said reference-axis data memory, said last buffer memory being adapted to update a datum number stored in one of the last datum number storage areas into a datum number from said address pointer at each time when the corresponding reference-axis datum is read out from said reference-axis data memory at its storage area;
a chain buffer memory including chain datum number storage areas which can be addressed by the datum numbers;
a first control means for writing a newly updated datum number into a chain number storage area addressed by a before-updated datum number at each time when the datum number of said last buffer memory is updated;
a second control means, which is operative after the writing of data into said first and last buffer memories has terminated, for writing a datum number stored in each one of said first datum number storage areas and placed in a predetermined relationship with said last datum number storage area into said chain datum number storage area, said chain datum number addressed by the datum number stored in the last datum number storage area, whereby the datum numbers of the reference-axis data can be written into the chain datum number storage areas to chain said reference-axis data with each other in the ascending or descending order;
a fourth control means for setting the next higher searched digit of a reference-axis datum and for reading the datum numbers from said chain datum number storage areas in accordance with a predetermined read-out rule, said fourth control means being adapted to perform the sorting operation of each of the searched digits such that the set searched digits of said reference-axis data are outputted from said reference-axis data memory to each of said first and second buffer memories in the order following their datum numbers, said sorting operation being repeated while shifting the searched digits by one digit in the order starting from the lowest digit of the reference-axis data and terminating at the highest digit thereof;
and
a third control means operative such that after the highest searched digit has been sorted, the datum numbers written in said chain datum number storage areas being read out therefrom in a predetermined read-out rule, whereby said reference-axis data can be sorted and outputted from said reference-axis data memory in the order following their datum numbers.

7 more elements

Dependencies are inferred from the claim text.