US3810112A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Shift-shuffle memory system with rapid sequential access
Assignee: Nokia Bell Labs
•
Filing: 1972-12-18
•
Granted: 1974-05-07
•
Expires: 1992-12-18
Abstract
Abstract A shift register memory having interconnections among its internal stages permitting stored data to be rearranged in two different ways. A first set of interconnections permits the usual cyclic rotation of data in response to a first ''''shift'''' control pulse. A second set of interconnections permits data to be rearranged in a shuffle pattern in response to a second ''''shuffle'''' control pulse, similar to the rearrangement of cards in a deck when shuffled. A pair of control registers records the current state of the data arrangement. Addressing circuitry calculates the present storage location of an addressed datum from this state information. Additional circuitry generates an accessing sequence of shift and shuffle control pulses which brings the addressed datum to the output stage of the shift register. After data at two succeeding addresses have been accessed in this fashion, all the data in the shift register have been reordered and succeeding datum addresses may be accessed with a single shift pulse per address.
Inventors
- 👤 A Aho
- 👤 J Ullman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 05:46
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/76; G11; G11C; G11C19/00
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
193 words
A memory system comprising: a memory containing N storage cells, where N satisfies the relationship N rk-1, where r and k are selected integers r > OR = 2 and k > OR = 1, the storage cells of said memory being interconnected by first and second sets of interconnections, said first set providing a cyclic shift rearrangement of the contents of said memory in response to a shift control signal, said second set providing a shuffle rearrangement of the contents of said memory in response to a shuffle control signal; and control means for generating a sequence of said shift and shuffle control signals in response to a datum address of a sought datum comprising, means responsive to said datum address for registering the current cell address of said datum, means responsive to said cell address for generating a shift control signal and for decrementing said cell address, means responsive to said cell address for generating a shuffle control signal and for cyclically shifting the digits of said cell address, means responsive to said cell address for detecting a predetermined value, and means for accessing the contents of a predetermined storage cell.
Claim 2
Dependent Claim
193 words
A memory system comprising: a memory containing N storage cells, where N satisfies the relationship N rk-1, where r and k are selected integers r > OR = 2 and k > OR = 1, the storage cells of said memory being interconnected by first and second sets of interconnections, said first set providing a cyclic shift rearrangement of the contents of said memory in response to a shift control signal, said second set providing a shuffle rearrangement of the contents of said memory in response to a shuffle control signal; and control means for generating a sequence of said shift and shuffle control signals in response to a datum address of a sought datum comprising, means responsive to said datum address for registering the current cell address of said datum, means responsive to said cell address for generating a shift control signal and for decrementing said cell address, means responsive to said cell address for generating a shuffle control signal and for cyclically shifting the digits of said cell address, means responsive to said cell address for detecting a predetermined value, and means for accessing the contents of a predetermined storage cell.
Claim 3
Dependent Claim
79 words
A memory system as set forth in claim 1 wherein: said means responsive to said datum address for registering the current cell address of said datum comprises, means for registering the number of shuffle rearrangements which have been undertaken and means for registering the current cell address of a reference datum address, and wherein, said means for generating said sequence of shift and shuffle control signals includes means for updating said number of shuffles and said current cell address.
Claim 4
Dependent Claim
40 words
A memory system as set forth in claim 2 wherein: said control means further comprises means for providing shift control signals and for updating said current cell address in response to input signals requesting sequential access to successive datum addresses.
Claim 5
Dependent Claim
107 words
A memory system comprising: rk - 1 storage cells each storing a single datum where r and k are selected integers, means foR generating shift and shuffle pulses which respectively shift and shuffle the contents among the storage cells, means for storing the storage cell address of a predetermined datum, means for decrementing said storage cell address in response to a shift pulse, means for shifting said storage cell address in response to a shuffle pulse, means for counting the number of shuffle pulses, and means responsive to said means for storing and said means for counting for determining the storage cell address of a given datum.
Claim 6
Dependent Claim
107 words
A memory system comprising: rk - 1 storage cells each storing a single datum where r and k are selected integers, means foR generating shift and shuffle pulses which respectively shift and shuffle the contents among the storage cells, means for storing the storage cell address of a predetermined datum, means for decrementing said storage cell address in response to a shift pulse, means for shifting said storage cell address in response to a shuffle pulse, means for counting the number of shuffle pulses, and means responsive to said means for storing and said means for counting for determining the storage cell address of a given datum.
Claim 7
Dependent Claim
140 words
A memory system comprising: rk-1 storage cells each storing a single datum, where r and k are selected integers, means for generating shift and shuffle pulses which respectively shift and shuffle the contents among the storage cells, q-register means for storing the storage cell address of a predetermined datum, means for decrementing the contents of said q-register means in response to a shift pulse and for shifting the contents of said q-register means, in response to a shuffle pulse, -register means for storing the number of shuffle pulses which have occurred, means for incrementing the contents of said p-register means in response to a shuffle pulse, means for shifting the digits of an input datum address by the number stored in said p-register means, and means for incrementing the shifted datum address by the number stored in said q-register means.
Claim 8
Dependent Claim
140 words
A memory system comprising: rk-1 storage cells each storing a single datum, where r and k are selected integers, means for generating shift and shuffle pulses which respectively shift and shuffle the contents among the storage cells, q-register means for storing the storage cell address of a predetermined datum, means for decrementing the contents of said q-register means in response to a shift pulse and for shifting the contents of said q-register means, in response to a shuffle pulse, -register means for storing the number of shuffle pulses which have occurred, means for incrementing the contents of said p-register means in response to a shuffle pulse, means for shifting the digits of an input datum address by the number stored in said p-register means, and means for incrementing the shifted datum address by the number stored in said q-register means.
Claim 9
Dependent Claim
112 words
A memory system comprising rk - 1 storage cells each storing a single datum, where r and k are selected integers, means for generating shift and shuffle pulses which respectively shift and shuffle the contents among the storage cells, a q-register for storing the storage cell address q of a predetermined datum, means for decrementing q in response to a shift pulse and for shifting q in response to a shuffle pulse, a p-register for storing the number of shuffle pulses which have been generated, means for incrementing p in response to a shuffle pulse, and means for calculating a cell address rp j + q for a given datum address j.
Claim 10
Dependent Claim
112 words
A memory system comprising rk - 1 storage cells each storing a single datum, where r and k are selected integers, means for generating shift and shuffle pulses which respectively shift and shuffle the contents among the storage cells, a q-register for storing the storage cell address q of a predetermined datum, means for decrementing q in response to a shift pulse and for shifting q in response to a shuffle pulse, a p-register for storing the number of shuffle pulses which have been generated, means for incrementing p in response to a shuffle pulse, and means for calculating a cell address rp j + q for a given datum address j.
Claim 11
Dependent Claim
86 words
A memory system comprising storage cells numbering (rk - 1) where r and k are selected integers, register means for storing a storage cell address, means for generating shift and shuffle pulses which respectively shift and shuffle the contents among the storage cells, means for decrementing the contents of said register means using (r - 1)'' s complement arithmetic in response to a shift pulse, and means for shifting the contents of said register means by one base r digit in response to a shuffle pulse.
Claim 12
Dependent Claim
86 words
A memory system comprising storage cells numbering (rk - 1) where r and k are selected integers, register means for storing a storage cell address, means for generating shift and shuffle pulses which respectively shift and shuffle the contents among the storage cells, means for decrementing the contents of said register means using (r - 1)'' s complement arithmetic in response to a shift pulse, and means for shifting the contents of said register means by one base r digit in response to a shuffle pulse.
Claim 13
Dependent Claim
117 words
A shift register memory having N storage locations, where N rk - 1, for given values of integers r and k, said storage locations being designated cell0 through cellN 1, said storage locations being connected by a first set of interconnections wherein the contents of each celli, where i is any integer within the range of 1 through N-1, is shifted into celli 1 and the contents of cell0 is shifted into cellN 1 in response to a shift control signal, said storage locations further being connected by a second set of interconnections wherein the contents of each celli is shuffled into cellM, where M r X i (modulo N), in response to a shuffle control signal.
Claim 14
Dependent Claim
117 words
A shift register memory having N storage locations, where N rk - 1, for given values of integers r and k, said storage locations being designated cell0 through cellN 1, said storage locations being connected by a first set of interconnections wherein the contents of each celli, where i is any integer within the range of 1 through N-1, is shifted into celli 1 and the contents of cell0 is shifted into cellN 1 in response to a shift control signal, said storage locations further being connected by a second set of interconnections wherein the contents of each celli is shuffled into cellM, where M r X i (modulo N), in response to a shuffle control signal.
Claim 15
Dependent Claim
123 words
Control means for a shift-shuffle memory having a plurality of storage locations comprising: means for counting the number of shuffles which have been executed, means for registering the reference address of a selected datum, means responsive to said means for counting for shifting an input datum aDdress by said number of shuffles, means for adding said reference address to the shifted datum address, thereby producing a cell address, means for decrementing the cell address and the reference address and producing a shift pulse, means for shifting the cell address, shifting the reference address, incrementing the number of shuffles and producing a shuffle pulse, and means for respectively shifting and shuffling said shift-shuffle memory in response to said shift pulse and said shuffle pulse.
Claim 16
Dependent Claim
123 words
Control means for a shift-shuffle memory having a plurality of storage locations comprising: means for counting the number of shuffles which have been executed, means for registering the reference address of a selected datum, means responsive to said means for counting for shifting an input datum aDdress by said number of shuffles, means for adding said reference address to the shifted datum address, thereby producing a cell address, means for decrementing the cell address and the reference address and producing a shift pulse, means for shifting the cell address, shifting the reference address, incrementing the number of shuffles and producing a shuffle pulse, and means for respectively shifting and shuffling said shift-shuffle memory in response to said shift pulse and said shuffle pulse.
Claim 17
Dependent Claim
30 words
Control means as recited in claim 9 further comprising, means for decrementing the reference address and for producing a shift pulse, thereby permitting abbreviated sequential access to successive storage locations.
Claim 18
Dependent Claim
42 words
Control means as recited in claim 9 further comprising, means for incrementing said means for counting, and shifting said reference address and for producing a shuffle pulse, and means for detecting a predetermined count, thereby permitting abbreviated rearrangement of storage location contents.
Claim 19
Dependent Claim
22 words
Control means as recited in claim 11 comprising means for reducing said count to zero, thereby reordering the contents of said memory.
Claim 20
Dependent Claim
88 words
A cyclically accessible memory system comprising means for cyclically shifting the contents of said memory system in response to a shift control signal, means for shuffling the contents of said memory system in response to a shuffle control signal, an address register for storing the address of the currently accessible data in said memory system, means for cyclically shifting the contents of said address register in response to each said shuffle control signal, and means for decrementing said address register in response to each said shift control signal.
Claim 21
Dependent Claim
88 words
A cyclically accessible memory system comprising means for cyclically shifting the contents of said memory system in response to a shift control signal, means for shuffling the contents of said memory system in response to a shuffle control signal, an address register for storing the address of the currently accessible data in said memory system, means for cyclically shifting the contents of said address register in response to each said shuffle control signal, and means for decrementing said address register in response to each said shift control signal.
Claim 22
Dependent Claim
59 words
The cyclically accessible memory system in accordance with claim 13 further comprising means for generating a plurality of shuffle control signals, means responsive to said means for generating for determining that the contents of said memory system is in a predetermined order, and means responsive to said means for determining for cyclically shifting the contents of said memory system.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1977-05-06 | 1977-11-05 | 1978-05-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1981-05-06 | 1981-11-05 | 1982-05-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1985-05-06 | 1985-11-05 | 1986-05-07 | $7700.00 | Window Closed / Lapsed |