Note: Descriptions are shown in the official language in which they were submitted.
This invention relates to an address shuffler and
particularly to one useful in address transformation systems
having an address translator with a translation address
distributlon limitation and the address shuffler coupled to
generate shuffled addresses which avoid the distribution
limitation.
This application is a divisional application of
applicant's Canadian application Serial No. 440,151 filed
November 1, 1983.
Discussion of the Prior Art
Data storage devices have become increasingly
larger in recent years in order to meet the demands of the
data processing industry for ever more storage and in order
to reduce manufacturing costs. However, as data store sizes
increase it becomes increasingly difficult to produce defect
free components. A single defect within a batch fabricated
component such as a semiconductor memory chip may require
the discarding of the entire component or at least a
significant portion of the component. Other data storage
components such as some types of core memories may be
repairable, but at relatively high cost.
In order to avoid disposal of an expensive
component because of a relatively small number of defects,
address transformation systems have been developed which
translate an input address for a defective data store
location to a different, valid data store location. IJpon
manufacture of a data store component, the component is
tested to identify defective storage
3~
kh/~ ``j,~
locations. The address transformation system is then
programmed to recognize the deEective address locations
and translate any such address to a different, ~alid
address location. Except for possible time delay penalties
under some arrangements, an external device using the data
store is unaware that any address translation has taken
place.
Examples of such an address transformation system
are disclosed in U.S. Patent 3,633,175 to ~arpe_ and U.S.
Patent 4,310,901 to Harding et al.
Typically these address transformation systems
partition incoming address signals into two or more
ordered sets. One set can be said to select one of many
pages and the other set can be said to identify a particular
address on the selected page. If the number of defective
locations associated with any single page exceeds a certain
given number, the system fails. Usually an economic trade-
off must be made between the cost of the transformation
system and the limitations on the number and distribution
' of defective addresses that can be accommodated.
For example, an address transformation system
for a 512K word core memory can accommodate up to 4K
defective address locations if they are properly distributed.
However, there may be no more than 64 faults associated with
any single page, whether an A page or a B page, and accom-
modating all defects becomes increasingly difficult as the
maximum number of 4K defects is approached. It is estimated
that with the maximum number of 4K randomly dis~ributed
defects, the probability of more than 64 defects ,occurring
on any single addressing page is less than one in 100,000.
kh~''j'
--3--
However, any memory system will tend to
experience the occurrence of nonrandom defects. For
example, a defective current line or in a core memory a
noisy or defective sense winding may result in unsatis-
factory operation at a large number of physicallyrela~ed data storage locations. Because economy of
manufacture often requires address decoders to associate
address pages with certain sense windings or control
lines, a single defect may cause a large number of
memory defects to occur on the same addressing page.
This can cause an address translation system to fail
even though the total number of data store faulty
address locations is less than the maximum for the
address translation system. The present invention
shuffles the input addresses relative to the actual
data store addresses in such a way that grouped data
store defects will be distri~uted over multiple address-
ing pages so that an address translation system need
not fail because of the nonrandom occurrence of multiple
defectsO
Summary of the Invention
The invention~is llsed in a data store address
translation system whlch avoidsjdefe~tive memory
address locationsO The system includes an address
translator which partitions an input address into pages
for economical faulty address detection and an address
shuf1er which provides a first set of addresses and a
shuffled second set of addresses which avoids maximum
- defects per page limitations.
The address shuffler is coupled to receive a
multi-digit input address represented by a plurality
of input address signals from a set of input addresses
and in response thereto to generate a first set address
which is within a first set of addresses, and a second
3s set address which is within a second set of addresses
with each address in each of the first and second sets
having a unique correspondence and a selected relation-
--4--
ship to a~ input address and to an address within theother of the first and second sets, the addresses of
the second set being partitioned into different first
and second parts defining r~spectively a first set of
pages and a second set of pages of addresses such that
within the associated data store a number of defective
data store address locations defined by addresses in
the first set of addresses corresponding to addresses
within any single page of the first set of pages i5 no
greater than a given number.
The address translator is coupled to receive
from the addxess shuffler a first set addxess and a
second set address and to output a store address in
response thereto, the output store address being the
received first ~et address in response to an absence of
a faul~ signal and a translated address outside the
first set of addresses in response to a presence of the
fault signal. The address translator includes a fault
detector responsive to second set addresses and coupled
to generate the fault signal when a received second
- set address corresponds to an address within a predeter-
mined subset of the second set addresses having corres-
ponding first set addresses which define a defective
storage location within the associated data store.
In a specific embodiment the address shuffIer
may comprise a switch mechanism which generates the
shuffled, second set of addresses by interch~nging the
order of a received set of ordered input address signal
conductors. In another embodiment the ordered input
set of address signal conductors may be partitionéd
into two groups with the first group being passed
through to generate a first group of second set address
conductors definlny a first part address signal. ~n
adder is connected to generate the second part address
signal as a sum of partial addresses derined by the t~o
groups of partial address signal conductors. In still
another embodiment the first group of second set
L6~
. --5~
addresses is generated by a second adder as the sum of
the first group of input address signals and second
group of second set address si~nals. This is equivalent
to the sum of the second group and twice the first group
(BS = Bi + Ai) (AS - Bi ~ 2~i).
Brief Description o the Drawin~s
A better understanding of the invention may
be had from a consideration of the following detailed
. description taken in conjunction with the accompanying
drawings in which:
Fig. I is a block diagram and schematic
representation o an address translation system
useful with the address shuffler of the invention;
Fig. 2 is an unshuffled address page map that
is useful in understanding the invention;
Fig. 3 is a shuffled address page map that is
useful in understanding the invention;
. Fig. 4 is a block diagra~ representation of
an alternative embodimen~ of an addres5 shuffler inclu~ed
2~ in the address translation system shown in Fig. 1;
Pig. 5 is a block diagram representation of
another altexnati~e embodiment of an address shuffler
included in the address translation system shown in
E'ig. l;
Fig. 6 is a shuffled address page map relating
to the embodiment shown in Fig. 5; and
Fig. 7 is a block diagram representation of
still another a1ternative embodiment of an address
shuffler included in the address translation system
shown in Fig~ 1.
Detailed Description .
Referring now to Fig. 1, an address
translation system 10 is
coupled between a suitable source of input addresses
AO-18 such as a memory address register (not shown) and
a data store 12. The address translation system 10
includes an address shuffler 14 and an address trans-
--6--
lator 16.
The address shuffler 14 receives multi-digit
input addresses represented by 19 input address signals,
each representing a different one of the binary inpuk
address digits A0-18. The input addresses are passed to
the address translator 16 as a first set of addresses.
Address shuffler 14 also shuffles the input addresses
to produce a second set of multi-digit shuffled addresses
represented by a plurality of shuffled address signals
having first and second multi-digit portions designated
AS0-9, and BS0-8. Signals representing the digits of
the first and second set addresses are coupled to
address translator 16.
The 512~ main storage portion of data store
12 requires a 19 bit binary address to select a single
word location therein. A 20th bit selects the 512R main
portion when logic 0 and the 4K portion when at logic
- 1. Because the address translation system 10 is
transparent to a data processing system using the data
20 store 12, the input address signals A0-18 contain only
19 bits of addressing to select one of 512K words. The
20th bit which selects either the main memory portion
or the auxiliary portion when an address is to be
translated, is generated by address translator 16.
The 19 bit input address signal appears on lg
parallel conductors which may be ordered and assigned
binary weights so that each input address m~y be con-
sidered to be a 19 bit binary number which uniquely
identifies an address location within data store 12.
The higher numbered address bits are considered to be
the more significant. With the input address conductors
and corresponding signals carried thereby ordered and
binary weighted, a change in the order and corresponding
weighting results in a shuffling of the input address.
Address shuffler 14 in effect provides a switching
function which switches the relative order of the
address bits to produce the second set of addresses in
--7--
response to the input firs~ set of addresses. Address
shuffler 14 partitions the input addresses into four
groups. Group one is designated AI0-4 and includes
address bits A0-4. Group two is designated AI5-9 and
includes address bits A5-9. Group three is designated
BI0-4 and includes input address bits A10-14. Group
four is designated BI5-8 and includes address bits A15-
18. Address shuffler 14 shuffles the input addresses
by interchanging the relative order of the second and
third groups designated AI5-9 and BI0-4. That is, the
second set of addresses is partitioned into four groups
of ordered address signals with a first group designated
AS0-4 corresponding to input addresses A0-4, a second
group designated AS5-9 corresponding to input addresses
A10-14, a third group designated BS0-4 corresponding to
inpu~ addresses A5-9, and a fourth group designated
BS;-8 corresponding to input addresses A15-18.
The first and second groups of second set
addresses are combined to form an ord red weighted set
of A page addresses and the third and fourth groups of
second set addresses are ~ombined to provide an ordered
weighted set of B page addresses.
The A page addresses now designated AS0-9 are
coupled to address an A key prom 20 which responds by
outputting four A key bits designated AK0-3O The A
page address is also communicated to an A translation
prom 22 which responds by generating a 6 bi~ translation
address designated AT0-5. Similarly, the third and
fourth groups of the second set designated BS0-4 and
BS5-8 are combined in a binary weighted order to generate
a second or B page address of 9 bits which is communi-
cated to a B translation prom 24 and a B key prom 26.
B translation prom 24 responds by generating a 6 bit
translation address output and B key prom 26 responds
by generating a 3 bit B key prom output. The A trans-
lation bits AT0-5 and B translation bits BT0-5 are co~-
bined in a binary weighted order to form a 12 bit
translation address which is co~unicated to a 4K by 8
fault prom 28 and also to an address multiplexer 30
Fault prom 28 stores predete~nined bi~ary
codes at addressed word locations~ At each word location
7 bits are selected to equate to the 7 key bits AKO-3
and BKO-2 and an eighth bit is set to 1 to indicatP
that the addressed location is active. That is, the
location relates to an address within the auxiliary 4I~
portion of data store 12 which is to be addressed
whenever a certair defecti~e location within the main
portion of data store 12 is defined by the input address
AO-18. A comparator 32 compares the 7 bits genPrated
by fault prom 28 with the 7 key bits and the eigh~h bit
FK7 generated by fault prom 28 with logic 1. If the
lS comparison indicates complete equality, a logic 1 fault
sisnal is generated by compare circuit 32. This ault
signal becomes the 2Oth address bit for data store 12
designated SAl9. The fault signal is also coupled to
the select B inputs of multiplexer 30 and a second
multiplexer 34. Multiplexer 30 is a 12 bit two to one
mu-tiplexer having input address signals from the first
set designated AO-ll coupled to the A input and the 12
translated address bits designated ATO-5 and BTO-5
coupled to the B input. T~le 12 bit output of multiplexer
30 generates the 12 least significant data store address
signals designated SAO-ll. These least significant
address bits designate one o. 4K address loc.ations
within the auxiliary portion of data store 12 when the
fault signal is true or alternatively when the fault
signal is false, one of 4K locations within the main
portion of this data store from a group of 4K locations
which is designated by data store address bits S~i2-18.
Data store address bits SA12-18 are generated b~ multi-
plexer 34 which has logic O connected to its B input
and input address bits A12-18 connected to the ~ in?ut.
Consequently, in the event o' the occurrence of the
fault signal, address bits SA12-18 are constrained to O
- .:
Whlle iTI the absence of a ault signa]., input add~ess bits
A12-la are communicated to data skore 12 as the address
bits SA12-18. A description of address translation systems
simila~ to address translator 16 can be found in U.S. Patents
Nos. 3,633,175 and 4,310,901, previously identified.
As an example of the operation of the address
translation system 10, assume that the data store 12 is a
core memory having for the main portion of the data store
4K word lines with 128 words times 1~ bits per word equal
2304 bit lines crossing each word line. That is, each word
line partially selects 128 words with 18 bits in each word.
If it is assumed by way of example that one of the word lines
is defective, then the 128 words which are partially salected
by the defective word line will all represent de~ective
storage locations. This is far less than the 4K maximum
capacity of the address translator 16. However, let it be
further assumed that the word lines are selected by a
predetermined group of bits within the store address, for
example bits SA0-11. Let it be further assumed that the
defective word line is word line 928, as an arbitrary example~
The address translator 16 operates in a paging
mode and partititions the incoming address signals into an
A group and a B group which can be set to define an A page
and a B page. Since together an A page address and a B
page address uniquely identify an address location, the A
and B address portions can be conceptualiæed as orthogonal
lines on an address map as shown in Fig. 2. ~here the A
page addresses have numbers which increase alon~ the
horizontal axis and are represented as vertically extending
lines and the B page addresses have numbers which increase
along the vertical axis and are represented as horizontallY
extending lines. Because 12 bits are re~uired to
~ 5 ~
~lo--
select one of 4K data store word lines, and only 10
bits are utilized to define the A portion of the trans-
lator 16 partitioned address, four physical data store
12 word lines map into each vertically extending AI
mapping line as shown in Fig. 20 These four word lines
are distinguished by the two least significant B page
address bits BI0, 1. ~or example, partitioned mapping
address AI 928 which is shown as vertical line 40 in
Fig. 2 actuaLly corresponds to the four physical word
lines 0 ~ 928 - 928, lK + 928 = 1952, 2K f g28 = 2976
and 3K f 928 = 4000. In the present exampIe only the
single word line 928 is actually defective. In the page
map of Fig. 2 the 128 words along physical word line 928
map into every fourth bit along AI mapping line 928 where
B group bits BIl, 0 = 0, 0 as illustratively represented
by points 42. Bits BI2-8 select one of 128 words along
physical word line 928.
~ owever, one of the conditions imposed by
address translator 16 (because there are 6 bits from the
B translate P~OM to enu~erate the faul.s) is that no
more than 64 faulty address word locations occur along
any single A group mapping line or any single B group
mapping line~ Assuming no other faults, the require-
ment fails in the present example because 128 faults
occur along mapping line AI928.
However, address shuffler 14 changes the
relative order of the conductors carrying the data
store 12 address so that the 128 defective word locations
do not all map into the same A group page as received
by address translator 16. It will he appreciated that
the defective word locations still appe-~r along the
same word line 928 in data store 12, but now map into
different locations in the shuffled address A and B
page map as shown in Fig. 3 so that all of the defective
address locations do not map into the same A page
address line. Since the A and B page addresses as used
by address translator 16 merely represent a convenient
.
partitioning of the input addresses, the address bit
lines can be grouped in any desired order and need not
conform to the physical decoding implemented by data
store 12. In the present example physical word line
g28 in data store 12 is defined by input address bits
All-A0 equal binary 001110100000. Input address bits
A18-12 (BI8-2~ can vary between 0 and 127 to define the
different 128 words along data store physical word line
928. With inpu~ address lines A9~5 (AI9-5) exchanged
with input address lines A14 10 (BI4-0) as shown in
Fig. 1 by address shuffler 14, the weighted order becomes
B8-B5, A9-A5, B4-B0, A4-A0. The first defective word
location along physical word line 928 maps into location
AS0? BS2g as represented by point 50 on the shuffled
address A and B page map shown in Fig. 3. The next
defective location maps into A address AS128 and B
address BS29 as shown at point 510 The third defective
storage location maps into A page address AS256 and B
page address BS29 as shown b~ point 52.
It will be observed that the eighth defective
word location (B4, B3, B2 = 1, 1, 1) along physical
data store 12 word line 9~ maps in the shuffled address
A and B page map shown in Fig. 3 into A page address
AS896 and B page address BS29 as represented by point
58. After eight defective word locations have been
mapped onto B page address BS29, the B page address is
incremented by 32 and the A page address is returned to
0 to map the ninth defective word location into A page
address AS0 and B page address BS61 as represented by
point 59. The tenth defective word location then maps
into A page address AS128 and B page address BS61 as
represented by point 60. The pattern then continues
with 16 defective word locations being mapped into each
of the A page address lines ASO, AS128, AS256, AS88~,
AS512, AS640, AS768, and AS896. At the same time, eight
defective word locations are mapped into each of the B
page address lines BS29, BS61, BS93, BS125, BS157,
~6~
BS189, BS221~ BS253, BS285, BS317, BS349, BS381, BS413,
BS445, BS477, and BS509. As a result of the address
shuffling, the nonrandom 128 defective word locations
which result from defective word line 928 within data
store 12 are distributed in such a way that no single A
page within address translator 16 has more than 16
defective word locations assigned thereto and no
single B page within address translator 16 has more
than 8 defective word locations assigned thereto. This
is well within the maximum of 64 which is permitted by
the particular example.
It will be appreciated that as the address
translator 16 is programmed to recognize and translate
defective addresses, the progr~m responds in exactly
the same way as it did when there was no address
shur!ling except that the program will respond to the
shuffled address BS8-0 and AS9-0 while the data store
- 12 is tested using the input or first set address A18-0.
That is, as data store 12 is addressed at location 928
and the first fault along word line 928 is tested, the
fault indication will be generated but address trans-
lator 16 will view this fault as occurring on shuf1ed
address 29,696 which corresponds to the intersection of
A map address AS0 and B map address BS29 in the shuffled
address A and B page map o~ Fig. 3. Then, during
subsequent operation, as input address 928 is received
on input address lines A0-18, address translator la will
be experiencing the corresponding shuffled address
29,696 on shuffled address lines AS0-9 and BS0-8 and
will recognize shuffled address 24,696 as a fault
location, generate the fault signal at compare circuit
32 and cause the selection of a valid data storage
location within the 4K auxiliary portion of data store
12.
Fig. 4 illustrates an address shu~rler 70
which ma~ ~e used as an altern2tive to the address
shuffler 14 shown in Fig. 1. .~ddress shuffler 70
-13-
includes a function circuit 72 which generates a
shuffled group of addresses as a selected function of two
groups of input addresses. In the present example,
function generator 72 comprises a 9 bit full adder 72
which generates the ~ page portion of the shuffled
address BS8-0 as the sum of the binary value represented
by input address line A18-10 and the binary value
represented by input addxess line A8-0 which is 446 when
physical word line 928 is selected. The A page portion
of the shuffled address AS9-0 is generated as a straight
passthrough of the input address line A9-0.
The address shuffler 70 of Fig. 4 wo~ld be
ineffective in distributing the 128 defective locations
which occur on physical word line 928 in data store 12
of the prior example since all.of these locations would
still map into A page address line 928. The Fig. 4
arransement fails to distribute these defective word
locations because it does not modify ~he lower order
input address ~its which define the defective word line
within data store 12. However, the arrangement of Fig.
4 would be ef~ective in distributing nonrandom defective
word locations which might result fro~ defective bit
lines which would be selected by decoding the higher
order input address bits A18-12.
Another alternative arrangement of an address
shuffler 80 shown in Fig. 5 is essentially the mirror
image of address shuffler 70 shown in Fig. 4. Address
shuffler 80 generates shuffled B page address bits BS0-
8 as a straight passthrough of input address bitQ A10-
18 and includes a 10 bit full addér 82 which generate~
the shuffled A page address bits AS9-0 as the sum of a
binary value represented by input address bits A18~10
and the binary value represen-ted by input address bits
A9-0. By arbitrary choice address line A18 is aligned
with address line A9 in the address 82 and zero is
provided at the input opposite address line A0.
The address shuffler 80 shown in Fig. 5 is
~3l6
-14-
very effective in dis~ributing ~he defective ward
locations which result fxom ~he defective word line 928
in our prior exampleO For example, as shown in Fig. 6,
the zeroth word of physical word address line 928 maps
into ~ map address line AS928 and B map address line
BS0 as represented by point 90.
The second (number 11 defective location
along physical word line 928 within data store.l2 has
an input address of 5024. When shuffled by the address
shuffler 80 shown in Fig. 5, this address maps into A
map address line 936 and B map address line 4 as repre-
sented by point 91 in Fig. 6. This occurs because next
adjacent words along physical word line 928 are defined
by incrementing bit B~ (A12~ of the B group. This
results in incrementing the shuffled AS group by 8 and
the s~u~fled BS group by 4.
The third (number 2) defective word location
along word line 928 within data store 12 has an input
address of 9120. ~hen shuffled by the address shuffler.
80 shown in Fig. 5, this address maps into A map address
line AS344 and B map address line BS8 as shown in point
92 in Fig. 6. It will thus be seen that each successive
defective word location along the hypothesized defective
word line 928 causes the shuffled A map address num~er
to be incremented by 8 and the shuffled B map address
number to be incremented by 4. The locus of defective
word locations on the shuffled address A and B page map
shown in Fig. 6 thus creates a diagonal line which will
wrap around to A map address AS0 as the A address count
increments to 1024. This locus of points is repre-
sentatively indicated by dashed lines ~3, 94.
It will thus be seen that as a result of. the
address shuffling provided by address shuffler 80 sho~
in Fig. 5, no single A page map address has more than
one defective word location assigned thereto and no
single B page address has more than one defective word
location assigned thereto. It will be appreciated
12~
-15 -
however that in any particular instance, the distri~u-
tion of assigned defective word locations will depend
~pon the distribution of such word locations within
data store 12. The effectiveness of any particular
embodiment of the address shuFler will depend upon the
particular defective word location distribution for any
given instance.
Still another em~odiment of an address shuffler
100 which in effect combines the address shufflers
illustrated in Fig. 4 and 5 is illustrated in Fig. 7.
Address shuffler 100 includes a full adder 102 which
generates the 9 most signîficant bits of the shuffled
address BS8-0 as the sum of the ~inary value represented by
input address lines A18-10 and the binary value repre-
sented by input address lines A8-0. A full adder 104
gene~ates the 10 least significant bits AS9~0 of the
shufrled address as the sum o~ the 9 most significant
bits of the shuffled address BS8-0 (~A18-10) with zero
in the additional least significant bit position and the
binary value represented by the 10 least significant
input address bits AI9-0 (A9-0~. TLle address shuffler
100 shown in Fig. 7 thus provides an efective additive
type shuffling of hoth the A page addresses and ~he B
page addresses as seen by the address translator 16.
Fox the arrangement o~ Fig. 7, the shuffled B page map
addresses are the same as for the arrangement of Fig. 4
and thus the 128 defective word locations along physical
word line 928 would produce B page addresses of 446r 450
454r 458, 462 and so forth as in the Fig. 4 arrangement.
However, the A page addresses now are generated as the
sum of the 10 least significant bits of the input
address plus the shuffled B page address. In the
particular example, the 10 least significant bits of
the input address will be the same for all defective
locations along physical word line 928 and have a value
of 928. The A page map address will thus ineremen~ bv
8 as the B page address increments by 4 as bit BI2
-16-
increments and the shuffled A group addresses will have
the values starting with 928 ~ 832 a 1760~ Ignoring over-
flows this is equivalent to 736. The zeroth word on
physical word line 928 thus occurs at AS736, BS446.
Successive words cause the A group address to increment
by 8 and the B group address to incxement by 4. The
Fig. 7 arrangement has the advantage of being capable
of distributing nonrandom word location defects which
may occur along bit lines defined by the higher order
portions of the data store address as well as defective
locations which occur along word lines defined by the
lower order portion of the data store address.
It should be appreciated that functions other
than addition can be utilized to s11uffle the input
addresses to generate the shuffled addresses as a func-
~ion of two groups of input addresses. For example,
in the arrangements of Figs. 4, 5 and 7, the full adders
72, 82, 102 and 104 could be replaced with a function
generator circuit having Exclusive-OR gates which
receive the pairs of input addresses. In effect, such
an arrangement would comprise half adders providing no
carries between adjacent stages. Other functional rela-
tionships could be used as well so long as defects
which group into a single page in the input addresses
2S are distributed among multiple pages in the shuffled
address so that no more than the maximum allowed number
of defects occux on a single page.
While there have been described above several
embodiments of an address shuffler for the
purpose of enabling a person of ordinary skill in the
art to make and use the invention, it will be appreci-
ated that the invention is not limited thereto.
Accordingly, modifications, variations or equivalent
arrangements within the scope of the attached claims
should be considered to be within the scope of the
invention.