公开(公告)号：US4630234A

公开(公告)日：1986-12-16

申请号：US483545

申请日：1983-04-11

申请人： James R. Holly

发明人： James R. Holly

IPC分类号： G06F7/24 ,  G06F17/30 ,  G06T9/20 ,  G06F3/14

CPC分类号： G06F17/30988 ,  G06F7/24 ,  G06T9/20 ,  Y10S707/99933

摘要： A relatively low cost, high speed search processor for efficiently scanning, inserting, and clearing certain data in an ordered linked list of data regarding a plurality of video scan line segments, which segments define mathematical elements (e.g. polygons) and corresponding portions of a three dimensional image. Data items containing information regarding the starting coordinates of the segments of a scan line are encoded and stored in the linked list according to the magnitudes thereof. The present search processor is adapted to read a new data entry to the linked list which is representative of the magnitude of a scan line segment starting coordinate and rapidly search the existing data items of the linked list to determine a particular location in the list at which to insert the new data entry, depending upon the magnitude of the scan line segment starting coordinate thereof relative to the magnitudes of the respective scan line segment starting coordinates of other items in the list.

摘要翻译： 相对低成本的高速搜索处理器，用于有效扫描，插入和清除关于多个视频扫描线段的有序链接数据列表中的某些数据，这些段定义数学元素（例如多边形）和三个对象部分的对应部分 三维图像。 包含关于扫描线的段的开始坐标的信息的数据项被编码并根据其大小被存储在链表中。 本搜索处理器适于读取表示扫描线段开始坐标的大小的链接列表的新数据条目，并且快速搜索链表的现有数据项以确定列表中的特定位置，其中 根据其扫描线段开始坐标的幅度相对于列表中其他项目的相应扫描线段开始坐标的大小来插入新数据条目。

公开(公告)号：US4604726A

公开(公告)日：1986-08-05

申请号：US485809

申请日：1983-04-18

申请人： John Terzian

发明人： John Terzian

IPC分类号： G06F7/24

CPC分类号： G06F7/24 ,  Y10S707/99937

摘要： An improved apparatus for forming an ordered sequence of n digital numbers from a randomly arranged set of n digital numbers is shown to be made up of: (a) n registers, each initially holding a different one of the randomly arranged set of n digital numbers; (b) a digital comparator for each adjacent pair of registers to determine whether or not the digital numbers in each adjacent pair of registers are in the ordered sequence and to interchange the digital numbers in any adjacent pair of registers whenever such numbers are not in the ordered sequence; and (c) a switching arrangement, operative in response to each successive one of (2n-1) clock pulses, alternately to switch each digital comparator from the associated adjacent pair of registers to a different selected pair of registers whereby the digital numbers may be shifted through the n registers as required to form the ordered sequence.

摘要翻译： 用于从随机排列的n个数字数字组中形成n个数字序列的有序序列的改进装置被示为：（a）n个寄存器，每个寄存器最初保存随机排列的n个数字数字集合中的不同的一个 ; （b）用于每个相邻寄存器对的数字比较器，以确定每个相邻寄存器对中的数字数字是否是有序序列，并且每当这些数字不在 有序序列 和（c）响应于（2n-1）个时钟脉冲中的每个连续的一个操作的切换装置，交替地将每个数字比较器从相关联的相邻寄存器对切换到不同的选定的一对寄存器，由此数字数字可以是 根据需要移动n个寄存器以形成有序序列。

公开(公告)号：US4209845A

公开(公告)日：1980-06-24

申请号：US762374

申请日：1977-01-25

申请人： David A. Berger ,  John W. Welch

发明人： David A. Berger ,  John W. Welch

IPC分类号： G06F7/24 ,  G06F17/30 ,  G06F7/02

CPC分类号： G06F17/30988 ,  G06F7/24 ,  Y10S707/99933 ,  Y10S707/99937

摘要： A system for sorting records of a file to find the record in the file having the highest or lowest data in a first field of the records, provided that the record qualifies to be sorted in accordance with the data in a second field of the records. A plurality of such records are stored on a plurality of blocks of a segmented serial storage device. Random access memory used by the system to accomplish the qualifying and sorting is a small fraction of the size of the file. In the preferred embodiment, a multiplicity of qualifying fields and sort fields may be specified. The system may typically be used, for example, to provide names, addresses and other variable text to be merged with form letter text in a printing system to sequentially print automatic form letters in the alphabetical or zip code order of their intended recipients. This information can also be used to list a qualified sublist of a master file in the order specified by the sort information.

摘要翻译： 用于对文件的记录进行排序以在记录的第一字段中具有最高或最低数据的文件中的记录进行排序的系统，条件是记录符合根据记录的第二字段中的数据进行排序。 多个这样的记录被存储在分段串行存储设备的多个块上。 系统使用的随机存取存储空间是文件大小的一小部分。 在优选实施例中，可以指定多个限定字段和分类字段。 通常可以使用该系统来提供姓名，地址和其他可与文本文本合并的可变文本，以便按照其预期的接收者的字母或邮政编码顺序顺序打印自动表单。 该信息还可用于按照排序信息指定的顺序列出主文件的合格子列表。

公开(公告)号：US4031520A

公开(公告)日：1977-06-21

申请号：US642849

申请日：1975-12-22

申请人： Michel Alexandre Rohner

发明人： Michel Alexandre Rohner

IPC分类号： G06F7/24

CPC分类号： G06F7/24

摘要： An input list of N numbers is clocked through a first sort stage having S1 locations entered into an interstage memory as S2 groups of S1 numbers each. The S1 numbers in each group are in numerical order. The first number in each group forms an initial group of S2 numbers which necessarily includes the smallest number of the N input numbers. This initial group is loaded into a second sort stack having S2 locations which arranges the initial S2 numbers in numerical order. The smallest number forms the first number in the output list. A replacement number from the interstage memory is numerically sorted into the second stack each time the smallest remaining number is clocked out. This replacement number is the next number from the same group as the most recently clocked out number. Each new smallest remaining number must either be the second number in the second stack or the replacement number. In one embodiment two candidates exist for the next replacement number: (1) the next number from the same group as the current replacement number and (2) the next number from the same group as the second number. These candidates are addressed in advance of the current output determination to minimize the clock period. Alternatively, preaddressing may be accomplished by having an initial group of 256 numbers -- the two smallest numbers in each of the S2 groups. There is only one candidate for the next replacement number, which candidate may be identified in advance.

摘要翻译： N个数字的输入列表通过具有S1个位置的第一分类阶段被输入到级间存储器中，作为S2组的每个S1编号。 每组中的S1数字按数字顺序排列。 每组中的第一个数字形成一个初始的S2号码组，其中必须包括N个输入号码的最小数目。 该初始组被加载到具有S2位置的第二排序堆栈中，该位置以数字顺序排列初始S2数字。 最小的数字形成输出列表中的第一个数字。 每当最小的剩余数量被输出时，来自级间存储器的替换数字被数字地分类到第二堆栈中。 该替换号码是与最近输出的号码相同的组中的下一个号码。 每个新的最小剩余数字必须是第二个堆栈中的第二个数字或替换数字。 在一个实施例中，对于下一个替换号码存在两个候选者：（1）与当前替换号码相同的组中的下一个号码和（2）与第二个号码相同的组的下一个号码。 这些候选者在当前输出确定之前被寻址以最小化时钟周期。 或者，可以通过具有256个数字的初始组 - 每个S2组中的两个最小数目来实现预寻址。 下一个替换号码只有一个候选人，可以提前确定候选人。

公开(公告)号：US4030077A

公开(公告)日：1977-06-14

申请号：US622911

申请日：1975-10-16

申请人： Judit Katalin Florence ,  Michel Alexandre Rohner

发明人： Judit Katalin Florence ,  Michel Alexandre Rohner

IPC分类号： G06F7/24

CPC分类号： G06F7/24

摘要： An input list of N numbers is clocked through a first sort stack which provides S2 groups of S1 numbers each arranged in ascending numerical order. The numbers are stored in a buffer where the first location within each group always contains the smallest number in that group. These S2 first numbers are loaded into a second sort stack which arranges them in ascending numerical order. The first location in the second stack contains the smallest number in the entire list of N numbers. This smallest number is clocked out of the second stack to form the first number in the output list. A replacement number is numerically sorted into the second stack from the S2 groups each time the smallest remaining number is clocked out. This replacement number is the next smallest number from the same group as the most recently clocked out number. Each time the smallest remaining number is clocked out, the remaining numbers in the second stack are rearranged to accommodate the replacement number for maintaining numerical order. Thus the smallest remaining number whether from the second stack or from the buffer is always advanced to the first location of the second stack. Each stack includes a push-down shift register which contains already sorted numbers (B) at the top of the stack. Each new number (A) is compared to the sorted number (B) at each location. If the replacement number (A) is greater than the previously sorted number (B) at a particular stack location, the replacement number (A) is loaded into that location. The sorted numbers (B) at that location and all subsequent locations are simultaneously pushed down by one location. The input numbers (A) are thus sequentially inserted in numerical order into the stack of already sorted numbers (B).

摘要翻译： 通过第一分类堆栈对N个数字的输入列表进行计时，该第一分类堆栈提供S2组，每组按升序排列顺序排列。 数字存储在缓冲区中，每个组中的第一个位置始终包含该组中最小的数字。 这些S2的第一个数字被加载到一个以升序排列的第二个排序堆栈中。 第二个堆栈中的第一个位置包含N个数字的整个列表中最小的数字。 这个最小的数字从第二个堆栈中输出，形成输出列表中的第一个数字。 每当最小的剩余数量被输出时，从S2组中将替换号数字分类到第二堆栈中。 该替换号码是与最近计时号码相同的组中的下一个最小号码。 每当最小的剩余数量被计时时，第二堆叠中的剩余数字被重新排列以容纳维持数字顺序的替换数字。 因此，无论从第二堆栈还是从缓冲区，最小的剩余数量总是前进到第二堆栈的第一位置。 每个堆栈包括一个下拉移位寄存器，其包含堆栈顶部已经排序的数字（B）。 每个新数字（A）与每个位置的排序数（B）进行比较。 如果替换号（A）大于特定堆栈位置处的先前排序数（B），则将替换号（A）加载到该位置。 在该位置和所有后续位置的排序数（B）同时被按下一个位置。 因此，输入数字（A）以数字顺序依次插入到已经排序的数字（B）的堆栈中。

公开(公告)号：US3931612A

公开(公告)日：1976-01-06

申请号：US468811

申请日：1974-05-10

申请人： William W. Stevens ,  Donald J. Ruder

发明人： William W. Stevens ,  Donald J. Ruder

IPC分类号： G06F7/24 ,  G06F7/02

CPC分类号： G06F7/24 ,  Y10S707/99937

摘要： Disclosed is a system for sorting information such as used, for example, in inventory control. New items to be sorted are fetched from a memory unit and are stored as buffered items in buffer stores. Comparators compare each new item from the memory unit with each of the buffered items in the buffer stores and with a lower limit and an upper limit. Item sort address registers store addresses which define the sorted order of the items in the buffer stores. After comparison of each new item, the item sort address registers are updated by the results of the comparison to establish a new sorted order and to cause rejected buffered items to be deleted from the buffer stores to make room for accepted new items. Reformatting apparatus is provided for reformatting items from the memory unit which have variable length and different weight fields such as prefix, body and suffix fields. Apparatus is provided for recognizing control fields which cause items to be ignored or included within the sorting process.

摘要翻译： 公开了一种用于对例如在库存控制中使用的信息进行排序的系统。 要从排序的新项目从存储器单元获取，并作为缓冲项目存储在缓冲存储器中。 比较器将来自存储器单元的每个新项目与缓冲存储器中的每个缓冲项目进行比较，并且具有下限和上限。 项目排序地址寄存器存储定义缓冲存储器中项目排序顺序的地址。 在比较每个新项目后，通过比较结果更新项目排序地址寄存器，以建立新的排序顺序，并使缓冲区中的被缓存项目从缓冲存储器中删除，为接受的新项目腾出空间。 提供重新格式化装置用于从具有可变长度和不同权重字段（诸如前缀，正文和后缀字段）的存储器单元重新格式化项目。 提供了用于识别控制字段的装置，这些控制字段导致在分类过程中忽略或包含项目。

公开(公告)号：US3815083A

公开(公告)日：1974-06-04

申请号：US16217271

申请日：1971-07-13

申请人： DIRKS ELECTRONICS CORP

发明人： DIRKS G ,  SCHENCK P

IPC分类号： G06F7/24 ,  G06F7/06

CPC分类号： G06F7/24 ,  G06F2207/222 ,  Y10S707/99937

摘要： Record units, each addressable by a record unit address, have keyfields with keyfield bits arranged to be presented in descending order of significance. The record unit addresses are separated into first and second address groups, comprising all addresses corresponding, respectively, to record units having a most significant keyfield bit of 0 and 1. The first and second address groups are each similarly subdivided into two successive address sub-groups in dependence on the next most significant keyfield bit of each record unit. The separating process of each successive sub-groups of addresses is continued under control of equally weighted bits from each record unit until all keyfield bits have been utilized. A system of indicator numbers are assigned to each record unit address and are modified during each successive sub-grouping to reflect from which of the immediately preceding sub-groups the address is derived.

摘要翻译： 记录单元，每个可由记录单元地址寻址，具有密钥字段，其中密钥字段位被布置成按重要性的降序呈现。 记录单元地址被分成第一和第二地址组，包括分别对应于具有最高有效密钥字段位0和1的记录单元的所有地址。第一和第二地址组各自类似地细分为两个连续的地址子块 依赖于每个记录单元的下一个最重要的键位。 每个连续的地址子组的分离过程在来自每个记录单元的相同加权比特的控制下继续，直到所有密钥字段位被使用为止。 指示符编号的系统被分配给每个记录单元地址，并且在每个连续的子分组期间被修改以反映从哪个前一个子组导出该地址。

公开(公告)号：US3740538A

公开(公告)日：1973-06-19

申请号：US3740538D

申请日：1971-07-28

申请人： US AIR FORCE

发明人： HEMPHILL J

IPC分类号： G06F7/24 ,  G06F7/06 ,  G06F7/00

CPC分类号： G06F7/24 ,  G06F2207/222 ,  G06F2207/226

摘要： A digital sorter and ranker in which pairs of binary words are subtracted from each other in adders by feed-in in one word of the pair together with the adjacent word one''s complement. A carry output indicates which word is the lowest and this output is fed through coincidence logic circuits to additional series of address and logic circuits in pyramid fashion until a single output is obtained from a final adder. The adder logic circuits, the carry output and the output of the final adder are fed through minimum value logic circuits to a series of minimum value flip-flops with the outputs thereof being fed back to the adders and their logic circuits. To record the rank of each word, a series of flip-flop groups with each group corresponding to a binary word is set according to the word''s rank, the flip-flops being controlled by gating circuits fed by preceding logic circuits, the final adder, and a binary counter.

摘要翻译： 数字分拣机和排队者，其中通过在一对单词中与馈入的相邻单词的补码相加，在加法器中相互减去二进制字对。 进位输出指示哪个字是最低的，并且该输出通过重合逻辑电路馈送到金字塔式的附加系列地址和逻辑电路，直到从最终加法器获得单个输出。 加法器逻辑电路，进位输出和最终加法器的输出通过最小值逻辑电路馈送到一系列最小值触发器，其输出反馈给加法器及其逻辑电路。 为了记录每个字的等级，根据字的等级来设置每个组对应于二进制字的一系列触发器组，触发器由前面的逻辑电路馈送的选通电路控制，最后的加法器， 和二进制计数器。

公开(公告)号：USRE27119E

公开(公告)日：1971-04-27

申请号：US27119D

申请日：1967-03-13

IPC分类号： G06F7/24 ,  G11C11/44 ,  G11C15/06

CPC分类号： G11C11/44 ,  G06F7/24 ,  G06F2207/226 ,  G11C15/06

摘要： AN ASSOCIATIVE MEMORY IS PROVIDED WHICH SORTS WORDS AS THE WORDS ARE ENTERED INTO THE MEMORY. AN ASSOCIATIVE SEARCH IN THE MEMORY LOCATES THE POSITION AMONG THE WORDS PREVISOULY ENTERED INTO THE MEMORY WHERE THE NEXT WORD IS TO BE ENTERED. DUMMY REGISTERS BETWEEN THE WORD STORING REGISTERS PROVIDE A TEMPORARY LOCATION FOR THE WORD BEING ENTERED. THE WORD STORAGE LOCATIONS ARE SHIFTABLE TO CLEAR THE DUMMY REGISTERS FOR THE NEXT ENTRY. A SEARCH CAN BE MADE UNDER A MASK, AND MEANS IS PROVIDED FOR SELECTING WORDS ONE AT A TIME IN ORDER WHEN A MULTIPLE MATCH OCCURS.

公开(公告)号：US3309674A

公开(公告)日：1967-03-14

申请号：US27224963

申请日：1963-04-11

申请人： EMI LTD

发明人： GORDON LEMAY CHRISTOPHER ARCHI

IPC分类号： G06F7/24 ,  G06K9/68

CPC分类号： G06F7/24 ,  G06K9/68