Granted Patent B2

US 9,921,969 · App. 14/967,169 · Granted Mar 20, 2018

Abstract

Claims (52)

1. A method of generating a random address mapping for a non-volatile memory (NVM), comprising:

identifying a number of bits (N) in a physical address space of the NVM;

selecting at least one bit (G) of the N bits of the physical address space to be used for global interleaving, where G is less than N;

determining a number of bits equal to N minus G (N−G) to be used for local interleaving;

mapping the at least one G bit using a mapping function for global interleaving;

interleaving (N−G) bits using an interleaving function for local interleaving; and

generating a combined mapping comprising the mapped at least one G bit and the interleaved (N−G) bits.

2. The method of claim 1 , wherein the mapping function for the global interleaving is selected from the group consisting of a bit inverse mapping function, a random swap mapping function, and a deterministic swap mapping function.

3. The method of claim 1 , wherein the interleaving function for the local interleaving is selected from the group consisting of a deterministic interleaving function and a random interleaving function.

4. The method of claim 1 , wherein the interleaving function is implemented using a multi-stage connection network.

5. The method of claim 1 , wherein the interleaving function is implemented using a network selected from the group consisting of an Omega network, a Butterfly network, a Benes network, and combinations thereof.

6. The method of claim 5 , wherein the network comprises a plurality of control inputs, the method further comprising providing a plurality of random values to the plurality of control inputs.

7. The method of claim 1 :

wherein the mapping function for the global interleaving is a bit inverse mapping function; and

wherein the interleaving function is implemented using a Benes network.

8. The method of claim 7 :

wherein the at least one G bit comprises the most significant bit of the physical address space of the NVM; and

wherein the bit inverse mapping function comprises inversing each of the at least one G bit.

9. The method of claim 1 , further comprising:

mapping at least one address in the physical address space of the NVM to a logical memory address for the NVM using the combined mapping.

10. The method of claim 1 , wherein the combined mapping constitutes a mapped physical memory address.

11. The method of claim 1 , wherein the mapping the at least one G bit using the mapping function for global interleaving comprises mapping the at least one G bit from a logical memory address using the mapping function for global interleaving.

12. The method of claim 11 , wherein the interleaving (N−G) bits using the interleaving function for local interleaving comprises interleaving (N−G) bits from the logical memory address using the interleaving function for local interleaving.

13. The method of claim 12 , wherein the combined mapping constitutes a mapped physical memory address.

14. An apparatus for generating a random address mapping for a non-volatile memory (NVM), comprising:

a memory;

a processor coupled to the memory and configured to:

identify a number of bits (N) in a physical address space of the NVM;

select at least one bit (G) of the N bits of the physical address space to be used for global interleaving, where G is less than N; and

determine a number of bits equal to N minus G (N−G) to be used for local interleaving;

a global interleaver configured to map the at least one G bit using a mapping function for global interleaving; and

a local interleaver configured to interleave (N−G) bits using a interleaving function for local interleaving,

wherein the processor is further configured to generate a combined mapping comprising the mapped at least one G bit and the interleaved (N−G) bits.

15. The apparatus of claim 14 , wherein the mapping function for the global interleaving is selected from the group consisting of a bit inverse mapping function, a random swap mapping function, and a deterministic swap mapping function.

16. The apparatus of claim 14 , wherein the interleaving function for the local interleaving is selected from the group consisting of a deterministic interleaving function and a random interleaving function.

17. The apparatus of claim 14 , wherein the interleaving function is implemented using a multi-stage connection network.

18. The apparatus of claim 14 , wherein the interleaving function is implemented using a network selected from the group consisting of an Omega network, a Butterfly network, a Benes network, and combinations thereof.

19. The apparatus of claim 18 :

wherein the network comprises a plurality of control inputs, and

wherein the processor is further configured to provide a plurality of random values to the plurality of control inputs.

20. The apparatus of claim 14 :

wherein the mapping function for the global interleaving is a bit inverse mapping function; and

wherein the interleaving function is implemented using a Benes network.

21. The apparatus of claim 20 :

wherein the at least one G bit comprises the most significant bit of the physical address space of the NVM; and

wherein the bit inverse mapping function comprises inversing each of the at least one G bit.

22. The apparatus of claim 14 :

wherein the processor is further configured to map at least one address in the physical address space of the NVM to a logical memory address for the NVM using the combined mapping.

23. The apparatus of claim 14 , wherein the combined mapping constitutes a mapped physical memory address.

24. The apparatus of claim 14 , wherein the processor is further configured to map the at least one G bit from a logical memory address using the mapping function for global interleaving.

25. The apparatus of claim 24 , wherein the processor is further configured to interleave (N−G) bits from the logical memory address using the interleaving function for local interleaving.

26. The apparatus of claim 25 , wherein the combined mapping constitutes a mapped physical memory address.

Assignments (11)