Sort circuit and method using multiple parallel sorts of the sor

Details Sort circuit and method using multiple parallel sorts of the sor Sort circuit and method using multiple parallel sorts of the sor

1983-02-17

1986-06-17

Springborn, Harvey E.

Boots, shoes, and leggings

364300, G06F 708

Patent

active

045959951

ABSTRACT:
In a sort circuit comprised of m sort stages, the sort stages perform respective sorts, in parallel, on each input word as it is received. In particular, in the j.sup.th one of the stages, j=1,2, . . . m, a bit is associated with each different possible pattern of the values of the D.sub.j highest-order digits in the input word, D.sub.1 >D.sub.2 > . . . D.sub.m. As each input word is received, the values of its D.sub.j higher-order digits are examined and the associated bit is set.
During output processing, the j.sup.th stage of the sort circuit receives from the (j+1).sup.st stage a D.sub.j+1 -digit pattern representing the D.sub.j+1 highest-order digits of a word or words previously input to the sort circuit. The D.sub.j+1 -digit pattern is used to identify the bits within the j.sup.th stage associated with the D.sub.j -digit patterns whose D.sub.j+1 highest-order digits match the input pattern. The bits thus identified are processed within the j.sup.th stage using priority logic circuitry so as to provide the D.sub.j -digit patterns associated with the ones of the identified bits which are set. These D.sub.j -digit patterns are provided to the (j-1).sup.st stage as its input digit pattern or, in the case of j=1, to the utilizing system. When the j.sup.th stage has processed all of the bits identified in response to a particular D.sub.j+1 -digit pattern, it requests a new pattern from the (j+1).sup.st stage.

REFERENCES:
patent: 3587057 (1971-06-01), Armstrong
patent: 3872289 (1975-03-01), Kawanabe
patent: 3931612 (1976-01-01), Stevens et al.
patent: 4003031 (1977-01-01), Kashio
patent: 4030077 (1977-06-01), Florence et al.
patent: 4031520 (1977-06-01), Rohner
patent: 4064556 (1977-12-01), Edelberg et al.
patent: 4110837 (1978-08-01), Chen
patent: 4131947 (1978-12-01), Armstrong
patent: 4410960 (1983-10-01), Kasuya
patent: 4414643 (1983-11-01), Meyer
patent: 4425617 (1984-01-01), Sherwood
patent: 4464732 (1984-08-01), Clark
patent: 4520456 (1985-05-01), Miranker et al.
D. E. Knuth, "Sorting and Searching," The Art of Computer Programming, vol. 3, 1973, pp. 170-180.

Affiliated with

Also associated with

Rating

Sort circuit and method using multiple parallel sorts of the sor does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Sort circuit and method using multiple parallel sorts of the sor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sort circuit and method using multiple parallel sorts of the sor will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2276473