Address transformation system having an address shuffler

Claim 2

An address shuffler including means for receiving an input address and means for shuffling the input address in a predetermined manner to generate a shuffled address having a unique one-to-one correspondence with the input address.

Claim 3

An address shuffler according to claim 1 having an input for receiving a plurality of input address signals, each representing a different digit of a multidigit input address and an output for providing a plurality of shuffled address signals, each representing a different digit of the shuffled address corresponding to the input address, the address shuffler comprising a plurality of conductors coupling a first selected portion of the input address signals to the output, the first selected portion of the input address signals constituting a first selected portion of the shuffled address signals and an adder coupled to receive the first portion of the input address signals and a second portion of the input address signals different from the first portion and generate as an adder output a plurality of adder output signals, each representing a different digit of a multidigit sum of values defined by the first and second portions of the input address signals, said adder output being coupled to provide a second portion of the shuffled address.

Claim 4

An address shuffler according to claim 1 having an input for receiving a plurality of input address signals, each representing a different digit of a multidigit input address and an output providing a plurality of shuffled address signals each representing a different digit of the shuffled address corresponding to the input address, the address shuffler comprising a first adder coupled to receive as inputs different first and second portions of the plurality of input address signals and provide as a first portion of the shuffled address signals a plurality of signals representing different digits of a sum of values represented by the first and second portions of the plurality of input signals and a second adder coupled to receive the first portion of the plurality of input signals and the first portion of the plurality of shuffled address signal and provide as a second portion of the shuffled address signals different from the first portion of the shuffled address signals a plurality of signals representing different digits of a sum of values represented by the first portion of the plurality of input address signals and the first portion of the plurality of shuffled address signals.

Claim 5

An address shuffler coupled to receive at least first and second ordered sets of input signals and output first and second ordered sets of output signals in response thereto, the address shuffler comprising a function generator circuit coupled to generate the first set of output signals as a function of the first and second sets of input signals such that the first set of output signals is identical to neither the first nor the second set of input signals over an entire range of first and second sets of input signal combinations.

Claim 6

An address shuffler coupled to receive at least first and second ordered sets of input signals and output first and second ordered sets of output signals in response thereto, the address shuffler comprising a function generator circuit coupled to generate the first set of output signals as a function of the first and second sets of input signals such that the first set of output signals is identical to neither the first nor the second set of input signals over an entire range of first and second sets of input signal combinations.

Claim 7

An address shuffler according to claim 4 further comprising a second function generator coupled to generate the second set of output signals as a function of the first set of output signals and the second set of input signals such that the second set of output signals is identical to neither the first set of output signals nor the second set of input signals over an entire range of combinations of first set output signals and second set input signals.

Claim 8

An address transformation system comprising: an address shuffler (14) according to claim 1 and an address translator (16) coupled to receive the shuffled address and output a valid store address corresponding thereto.

Claim 9

An address transformation system according to claim 6, wherein the address translator (16) is further coupled to receive the input address and further includes a fault detector (28,32) coupled to receive the shuffled address and generate a fault signal and a valid translated address if the received address is one uf a predetermined set of defective addresses and a multiplexer coupled to output as the store address the translated address in the presence of the fault signal and the input address in the absence of the fault signal.

Claim 10

An address transformation system according to claim 6, wherein the address translator is operative to determine whether the shuffled address belongs to a predetermined set of defective shuffled addresses and outputs as the store address a valid translated address corresponding to the shuffled address if the shuffled address is determined to belong to the predetermined set of defective shuffled addresses.

Claim 11

An address transformation system according to any of claims 6 to 8, wherein the address shuffler is coupled to receive an input address as a first ordered set of signals and to generate the shuffled address as a second ordered set of said signals having a predetermined juxtaposition relative to the first ordered set.

Claim 12

An address transformation system according to any of claims 6 to 8, wherein the address shuffler receives each input address as an ordered set of input address signals, partitions the input address signals into at least first and second mutually exclusive ordered sets of input address signals and outputs the shuffled address as at least first and second ordered sets of shuffled address signals, the address shuffler further including an adder (72) coupled to generate the first ordered set of shuffled address signals as a sum of the first and second ordered sets of input address signals.

Claim 13

The address transformation system according to claim 10, wherein the address shuffler further includes a second adder coupled to generate the second ordered set of shuffled address signals as a sum of the first ordered set of input address signals and the first ordered set of shuffled address signals.

Claim 14

An address transformation system according to any of claims 6 to 8, wherein the address shuffler receives each input address as an ordered set of input address signals, partitions the input address signals into at least first and second mutually exclusive ordered sets of input address signals and outputs the shuffled address as at least first and second ordered sets of shuffled address signal, the address shuffler further including a function generator circuit coupled to generate the first ordered set of shuffled address signals as a functional relationship of the first and second ordered sets of input address signals which produces a first set of shuffled address signals which is different from both the first and second sets of input address signals.

Claim 15

A data store address transformation system comprising: an address translator (16) coupled to receive an input address and a shuffled address having a unique correspondence to the input address, the address translator partitioning the shuffled address into at least first and second different sets of shuffled addresses, each defining respectively first and second pages of shuffled addresses, and including a fault detector (28,32) coupled to generate a fault signal when an address defined by the first and second different sets of shuffled addresses corresponds to an address within a predetermined set of defective shuffled addresses, the address translator including circuitry that is coupled to output the input address as a store address in the absence of the fault signal and to output as the store address a translated address corresponding uniquely to the shuffled address and identifying an operative store location in response to the fault signal; and an address shuffler (14) coupled to receive the input address and generate the shuffled address corresponding uniquely thereto, the correspondence between the shuffled address and the input address being such that no first page of shuffled addresses has more than a first number of defective address locations defined thereby and no second page of shuffled addresses has more than a second number of defective address locations defined thereby.

Claim 16

A data store address transformation system comprising: an address translator (16) coupled to receive an input address and a shuffled address having a unique correspondence to the input address, the address translator partitioning the shuffled address into at least first and second different sets of shuffled addresses, each defining respectively first and second pages of shuffled addresses, and including a fault detector (28,32) coupled to generate a fault signal when an address defined by the first and second different sets of shuffled addresses corresponds to an address within a predetermined set of defective shuffled addresses, the address translator including circuitry that is coupled to output the input address as a store address in the absence of the fault signal and to output as the store address a translated address corresponding uniquely to the shuffled address and identifying an operative store location in response to the fault signal; and an address shuffler (14) coupled to receive the input address and generate the shuffled address corresponding uniquely thereto, the correspondence between the shuffled address and the input address being such that no first page of shuffled addresses has more than a first number of defective address locations defined thereby and no second page of shuffled addresses has more than a second number of defective address locations defined thereby.

Claim 17

14 . An address transformation system coupled to receive an input address defining a data store location and output in response thereto a store address defining a valid data store location, the address transformation system comprising: an address translator (16) coupled to receive first and second portions of a shuffled address representative of an input address and output the store address in response thereto, the address translator requiring a number of defective address locations within any page of address locations defined by the first set of address information to be less than or equal to a first predetermined number and a number of defective address locations within any page of address locations defined by the second set of address information to be less than or equal to a second predetermined number; and an address shuffler (14) coupled to receive the input address and in response thereto generate the first and second portions of the shuffled address having a unique correspondence and a selected relationship to the input address with a number of defective address locations within any page of address locations defined by the first portion being less than or equal to the first predetermined number-and with a number of defective address locations within any page of address locations defined by the second portion being less than or equal to the second predetermined number.

Claim 18

14 . An address transformation system coupled to receive an input address defining a data store location and output in response thereto a store address defining a valid data store location, the address transformation system comprising: an address translator (16) coupled to receive first and second portions of a shuffled address representative of an input address and output the store address in response thereto, the address translator requiring a number of defective address locations within any page of address locations defined by the first set of address information to be less than or equal to a first predetermined number and a number of defective address locations within any page of address locations defined by the second set of address information to be less than or equal to a second predetermined number; and an address shuffler (14) coupled to receive the input address and in response thereto generate the first and second portions of the shuffled address having a unique correspondence and a selected relationship to the input address with a number of defective address locations within any page of address locations defined by the first portion being less than or equal to the first predetermined number-and with a number of defective address locations within any page of address locations defined by the second portion being less than or equal to the second predetermined number.

Claim 19

An address-transformation system according to claim 14, wherein the address shuffler includes an adder coupled to generate the first set of address information as a sum of first and second ordered sets of signals defining the input address.

Claim 20

An address translation system for receiving an input address from a set of input addresses and outputting in response thereto a store address defining a valid data storage location within a data store, the address translation system comprising: an address shuffler (14) coupled to receive an input address 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 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 relationship to an input address and to an address within the other of the first and second sets, the addresses of the second set being partitioned into different first and second parts defining respectively 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 is no greater than a given number; and an address translator (16) coupled to receive -iran the address shuffler a first set address and a second set address and to output a store address in response thereto, the output store address being the received first set address in response to an absence of a fault signal and a translated address outside the first set of addresses in response to a presence of the fault signal, the address translator including a fault detector responsive to the second set addresses and coupled to generate the fault signal when a received second set address corresponds to an address within a predetermined subset of the second set addresses having corresponding first set addresses which define a defective storage location within the associated data store.

Claim 21

An address translation system for receiving an input address from a set of input addresses and outputting in response thereto a store address defining a valid data storage location within a data store, the address translation system comprising: an address shuffler (14) coupled to receive an input address 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 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 relationship to an input address and to an address within the other of the first and second sets, the addresses of the second set being partitioned into different first and second parts defining respectively 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 is no greater than a given number; and an address translator (16) coupled to receive -iran the address shuffler a first set address and a second set address and to output a store address in response thereto, the output store address being the received first set address in response to an absence of a fault signal and a translated address outside the first set of addresses in response to a presence of the fault signal, the address translator including a fault detector responsive to the second set addresses and coupled to generate the fault signal when a received second set address corresponds to an address within a predetermined subset of the second set addresses having corresponding first set addresses which define a defective storage location within the associated data store.

Claim 22

An address translation system according to claim 12, wherein 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 second set of pages is no greater than a second given number.

Claim 23

An address translation system according to any of claims 6 to 17, wherein the address shuffler comprises a switching circuit coupled to switch the order of received input address signals to generate a shuffled address signal.

Claim 24

An address translation system according to any of claims 6 to 17, wherein the address shuffler separates the input address into first and second parts, generates a first part of the shuffled address as the first part of the input address and includes an adder coupled to generate a second part of the shuffled address as a sum of values represented by the first and second parts of the input address.

Claim 25

An address translation system according to any of claims 6 to 17, wherein the address shuffler separates the input address into first and second parts, generates a first part of the shuffled address as a sum of values represented by the first and second parts of the input address and generates a second part of the shuffled address as a sum of values represented by the first part of the input address and the first part of the shuffled address.