вход по аккаунту


Патент USA US3089133

код для вставки
May 7, 1963
Filed Jan. 11, 1957
2 Sheets-Sheet 1
MOD N2 /33
FIG. _1 _
May 7, 1963
Filed Jan. 11, 1957
2 Sheets-Sheet 2
_/l 1 /l/////////////////// ‘_
United States Patent @t’iiice
Patented May 7, 1963
internal address corresponds to an external address. The
problem is therefore to automatically determine the cor
rect internal address for any given external address.
It is an object of the present invention to provide
improved means for automatically determining the cor
rect internal address for any given external address.
Andrew C. Reynolds, Jr., Waterbury, C0nn., assignor to
International Business Machines Corporation, New
York, N.Y., a corporation of New York
Filed Jan. 11, 1957, Ser. No. 633,700
It is uneconomical to use the external address as the
4 Claims. (Cl. 340-1725)
internal address; that is to say, providing a storage posi
This invention relates to the automatic addressing of 10 tion for the unassigned external addresses as well as
those which are assigned. Speci?cally, therewould be
random access storage units.
as much wasted storage space as there are unassigned ex
An object of this invention is to provide improved
ternal addresses.
means for automatically locating the address of some
The method of scanning the entire storage in order to
given information stored in a random access memory
?nd the correct information is enormously time consum
ing, especially when the number of items of information
A random access memory or storage unit is a device
is large. With this type of system, on the average half
which stores information in such a way that any unit
of the memory would be scanned for each inquiry.
of the information is directly accessible. That is, given
It is another object of the present invention to provide
the address of any location, the memory device is able
improved means for addressing random access storage
to directly go to that location and read out the infor
in a relatively short time and enabling relatively economi
mation stored there. One or more units of information
cal use of storage space.
If the external address is converted to some nonuniquc
internal address of fewer positions, then more than one
position, then the storage of 10n units of information in 25 item number is stored at each internal address and the
are stored at a storage position. “Internal address” is
de?ned as the name of this storage position.
If but one unit of information is stored in one storage
scanning of each internal address is required. If the
internal address contains comparatively few members,
the time required for scanning is relatively small.
a random access ?le, requires l0n storage positions and
an n decimal digit internal address.
Depending upon the speci?c application, the unit of
In general, there is no way of predicting the distribu
tion of items over the internal address positions, that is,
predicting how many of the items will fall in any given
information may refer to an insurance policy, machine
part, or customer transaction, etc. The term “external
address” will be used to designate the policy, part or
customer number. For example, part No. 153216 is an
external address and if the information referring to this
part is stored in 956th storage position, it would have
the internal address of 956. Thus, just as the internal
address is the name of the memory location, so the ex
ternal address is the name of the policy or part, etc.
The external addresses are sometimes alphanumeric.
address position. Thus, the internal address positions
would need to be of a very large size or a proportionately
large over?ow storage would be required.
“Over?ow” is de?ned as the exceeding of the capacity
of an internal address, and over?ow means are the means
provided to accommodate these over?ows.
If the internal
addresses formed by compressing the external addresses
fall in unpredictable groupings, then there is no way
of the characters are numeric, and j alphabetic (where 40 of knowing which internal addresses will receive the ma
jority of the items. Thus, some of the internal addresses
i+j=m) then the number of possible external addresses
would receive such a disproportionately large number of
is M=lO1><261'.
items that the required over?ow means would have to be
The discussion hereafter will refer only to numeric ad
so extensive as to counteract any economies in storage
dresses for simplicity. The alphabetic addresses may be
or time. If, however, the distribution of items in the
handled in the same manner as numeric addresses, for
internal addresses is known, then the over?ow means may
example, by Choosing a system of notation having a suf
be made only large enough to handle an over?ow known
?ciently large base.
to any desired probability.
Although there are M possible external addresses, it
If we have an M character external address and if i
is rare if ever that each of them designates some policy 5
or part number. The more usual case is that only N of
the M possible external addresses are actually assigned.
It is usually the case that the internal addresses are or
dered from 1 to N, where N is the number of storage
positions or units of storage. However, it is not usually
the case that the external addresses are assigned in any
The distribution of a series of random numbers can
be predicted. Assume that the external addresses are
shortened or compressed and that the shortened addresses
are randomly distributed throughout the range of all pos~
sible shortened addresses, then the probability of 1' rec
ords having the same shortened address is given by the
Poisson approximation to the binominal distribution
it is thus seen that the external addresses range over
a much larger class of numbers than do the internal ad
dresses for any given application. Thus, there are large 60
unused or unassigned gaps in the sequence of external
where u is the total number of entries required, divided
by the number of internal addresses available, 1' equals
Furthermore, it often happens that some of
the unassigned external addresses may be assigned to a
the number of items in a given address cell, E is the
new part, and likewise, it may happen that one or more
natural logarithmic base, and P(u, i) equals the deci
parts become obsolete and hence their part numbers
are no longer used. Additionally, the used external ad
dresses may be numbers bunched together. It is thus
seen that these gaps are fundamentally unpredictable.
The problem of automatically adressing is to ?nd the
_ mal fraction of the total number of items distributed
internal address for any given assigned external address.
to provide means for generating a series of random
numbers from a series of other numbers.
Another object is to provide means for generating a
Since there are unpredictable gaps in the sequence of ex
ternal addresses, there is no direct way to know which
among cells containing precisely 1' items. Thus, it can
have any positive rational value, but i is restricted to in‘
tcgral positive values including Zero.
Accordingly, it is an object of the present invention
smaller multidigit random number from a larger multi
digit number.
Another object is to provide means for compressing
external addresses into randomly distributed internal ad
The four outputs of adders 32 through 35 manifest
the compressed or shortened internal address.
The four outputs 36. through 39 of adders 32 through
35 are plug wired to the inputs of a register 41. Regis
ter 41 may be of the same type as register 21 but need
only store four digits.
Addressing apparatus 20 is thus adapted to compress
an external address to an internal address ‘is accom
eigh digit external addresses into four digit internal ad
plished by compressing the external address into the
dresses. The outputs 36 through 39 provide the internal
required number of digits such that the same external
address. The adders 32 through 35 are designated
address always produces the same internal address. This
Mod N1 through Mod N4, respectively. The signi?cance
is done by adding digits from selected positions in the
of Mod N2, for example, is that the sum produced by
external address, discarding the carry, and forming the
adder 33 has the numbers N2 cast out. That is, the
According to the present invention, translation from
required number of such sums to produce an internal
address of the desired length. For example, suppose
that the external address consists of eight digits while
the internal address requires four digits.
Such an ex
ternal address might be 34908562. A possible selec
tion of positions to be added is the ?rst and ?fth, second
and sixth, etc. Adding thusly and casting out lO‘s pro
duces the internal address 1952.
This system of compression produces a regrouping of
the records, which regrouping is according to the in
ternal addresses. This regrouping is also in the form of
a Poisson distribution.
The regrouping in this form is
independent of the orignal set of external addresses.
Thus, a general addressing arrangement is provided that
is applicable to all random access systems.
Other objects of the invention will be pointed out in
the following description and claims and illustrated in
the accompanying drawings, which disclose, by way of
examples, the principle of the invention and the best
mode, which has been contemplated, of applying that
In the drawings:
FIG. 1 is a diagrammatic block representation of a
random access storage system addressed by apparatus
constructed in accordance with the present invention.
FIG. 2 is a family of curves representing the Poisson
Referring to FIG. 1, addressing apparatus 20 for ran
output of adder 33 is a partial sum or the remainder of
the sum of the two inputs when divided by N2. For
example, if N2 is 10 and the two inputs are 9 and 4,
the sum output is the remainder when 9+4=13 is divided
by 10, namely 3. N1, N2, N3 and N4 may be the same
but they need not be. The total number of internal
addresses produced by the system shown is N1~N2'N3'N4.
With all the adders 32 through 35 Mod 10 adders, the
total number of possible internal addresses produced
is 104.
FIG. 2 shows a family of curves representing the
Poisson distribution.
described addressing apparatus produces internal ad
dresses, the distribution of which is predictable.
A random access storage with a coacting address selec
tion circuit is shown and described in the above-men
tioned application of F. E. Hamilton et a1.
Brie?y, this
random access storage comprises a magnetic drum storage
with an address register and diode switching circuits for
selecting addresses on the magnetic drum. Address se
lection circuit 42 of FIG. I may be constructed as shown
in the aforementioned application at FIGS. 59a through
dom access storage is shown comprising a register 21
adapted to store an eight digit external address.
FIG. 2 is drawn as a family of con
tinuous curves, but by de?nition has meaning only at
the points de?ning u and i as given above.
It has been found that internal addresses produced as
described above are randomly distributed over the entire
30 range of internal addresses regardless of the distribution
of the original external addresses. Thus, the above
590 and at FIGS. 71c and 71f. These circuits are re
ferred to as static and dynamic selection circuits. In the
ter 21 may be a shift register into which digits are en
tered serially or in parallel from any desired source over
afore-mentioned application, the address register is
adapted to store information represented in the biquinary
serial input 22 or parallel input 23.
Such registers are
The address selection circuit 42 coacts with the
well known in the art and are not shown in detail herein
but may be constructed if desired in accordance with
the teachings of Hamilton et al. Patent No. 2,700,502, as
random access storage 43 as described in the afore
mentioned application in that a number entered into the
signed to the same assignee as the present application.
This patent uses a four element code and thus requires
only four binary type shift registers operating in paral
in the random access storage to read out the values stored
thereat or write new values therein.
When an address location in the random access storage
register 41 activates the corresponding address location
To form a biquinary shift register, three additional
43 is activated by selection circuits 42, the contents
binary type registers like those shown and connected
thereof may be read out over output 44 to a comparison
together as shown are all that is required. Register 21
is adapted to store digits in the biquinary coded form,
circuit 45. The value standing in register 21 is also fed
to comparison circuit 45 to be compared with the values
being read out of storage 43. Upon coincidence at com
parison circuit 45, a signal is fed to switch 46 to allow
the contents of this portion of the address of storage 43
therefore each digit position requires seven bistable de
vices such as triggers. Accordingly, each of the eight
digit outputs, 24 through 31, consists of a seven wire
channel. The outputs 24 through 31 are plug wired to 60 to pass through switch 46 to utilization device 47. In
this manner the different items at a single internal ad
the inputs of adders 32 through 35. The register out
dress are scanned and the one sought is fed to utiliza
puts 24 and 28 are wired to the inputs of adder 32, the
tion device 47. The comparing and scanning system
outputs 25 and 29 are wired to the inputs of adder 33,
forms no part of the present invention and is therefore
discussed only brie?y.
Adders 32 through 35 may each be biquinary adders
Means for accommodating an over?ow from an inter
of the type shown in FIGS. 68a through 681 of F. E.
nal address location may be provided as desired, but are
Hamilton et a1. application Serial No. 544,520, ?led
not described herein since they form no part of the present
November 2, 1955, and assigned to the present assignee.
Such an adder should be modi?ed by disconnecting the
While there have been shown and described and pointed
output of the carry latch 556 of FIG. 68:: of the above 70
out the fundamental novel features of the invention as
identi?ed application. Brie?y, this adder is a diode
switching and mixing circuit that receives a value on each
of two seven-line inputs and merges the several lines to
manifest the lowest ordered position of the sum of the
two values on a seven-line output.
applied to a preferred embodiment, it will be understood
that various omissions and substitutions and changes in
the form and details of the device illustrated and in its
operation may be made by those skilled in the art, with
out departing from the spirit of the invention. It is the
intention, therefore, to be limited only as indicated by
the scope of the following claims.
What is claimed is:
1. Apparatus for addressing random access storage
with multidigit external address numbers comprising in
combination internal address means for selecting a loca
tion within said storage, a plurality of modulus adders
each having ?rst and second inputs and a single output,
of adders each having a pair of input channels and a
single output channel and each adapted to produce on
said output channel the partial sum of the values mani
fested at said pair of input channels, means for transmit
ting only selected pairs of digits of each multidigit ex
ternal address number in parallel to said plurality of
adders to thereby add only selected pairs of digits to pro
duce an internal address number, each digit of which
corresponds to an output of one of said adders, means
means for simultaneously transmitting only selected pairs 10 for
addressing the addressable position in said random
of digits of said external address number to the inputs
of said plurality of adders to thereby add only selected
pairs of digits, and means connecting the outputs of said
access storage, and means connecting said output chan
nels to said addressing means.
4. Apparatus for converting multidigit numbers into
randomly distributed other multidigit numbers of fewer
having a plurality of addressable positions, apparatus for 15 digits comprising: a plurality of adders each having a
pair of input channels and a single output channel and
producing a random number from a multidigit number
each adapted to add the digits manifested at said pair of
manifestation for selecting a corresponding addressable
input channels and manifest the partial sum at said out
position of said storage device, comprising a source of
multidigit number manifestations, means responsive to 20 put channel, means manifesting the digits of a multidigit
number, and means for transmitting only selected pairs
said source for adding only digits from selected positions
of digits from said manifesting means to each of said
of a multidigit number manifestation from said source to
adders to thereby produce a random multidigit number
produce a plurality of partial sum manifestations such
adders to said ?rst named means.
2. In combination With a random access storage device
manifestation each digit of which corresponds to one of
that the output of each adding means comprises one digit
said output channels.
of the random number, and means for addressing said 25
positions with said partial sum manifestations.
References Cited in the ?le of this patent
3. Apparatus for addressing a random access storage
having a plurality of addressable positions comprising a
source of multidigit external address numbers, a plurality
Nettleton ____________ __ June 16, 1959
Без категории
Размер файла
498 Кб
Пожаловаться на содержимое документа