Conflict-free memory for fast walsh and inverse fast walsh transforms
An address generation component performs in-place address assignments and memory-selection circuitry provides a specific pattern of data storage to avoid memory conflicts that may occur during a fast Walsh transform (FWT) operation.
1 . A system configured for providing a conflict-free memory in a Fast Walsh Transform (FWT), comprising
an address generation component configured to provide for in-place address assignments, and
a memory-selection circuitry configured to provide a pattern of data storage that avoids memory conflicts during an FWT operation.
2 . The system recited in claim 1 , wherein the address generation component is configured to employ the same address for outputs and inputs on the same wing of each butterfly.
3 . The system recited in claim 1 , wherein the address generation component includes common address-generation hardware for both butterfly inputs and butterfly outputs.
4 . The system recited in claim 1 , wherein the address generation component includes one set of address-generation hardware for butterfly inputs and a different set of address-generation hardware for butterfly outputs.
5 . The system recited in claim 1 , further configured to reside in at least one of a microprocessor, a digital signal processor, an application specific integrated circuit, and a field programmable gate array.
6 . The system recited in claim 1 , configured to function with an inverse-FWT operation.
7 . The system recited in claim 1 , wherein the memory-selection circuitry is configured to employ an index matrix for providing the pattern of data storage.
8 . The system recited in claim 7 , wherein the memory-selection circuitry is configured to recursively generate swap codes.
9 . A method for providing conflict-free memory in a Fast Walsh Transform (FWT) operation, comprising
providing for performing in-place address assignments, and
providing for producing a pattern of data storage that avoids memory conflicts during the FWT operation.
10 . The method recited in claim 9 , wherein providing for performing in-place address assignments is configured to employ the same address for outputs and inputs on the same wing of each butterfly.
11 . The method recited in claim 9 , wherein providing for performing in-place address assignments includes accessing common address-generation hardware for both butterfly inputs and butterfly outputs.
12 . The method recited in claim 9 , wherein providing for performing in-place address assignments includes accessing a first address-generation hardware for butterfly inputs and a second set of address-generation hardware for butterfly outputs.
13 . At least one of a microprocessor, a digital signal processor, an application specific integrated circuit, and a field programmable gate array configured to perform the method recited in claim 9 .
14 . The method recited in claim 9 , configured for functioning with an inverse-FWT operation.
15 . The method recited in claim 9 , wherein providing for producing a pattern of data storage includes employing an index matrix.
16 . The method recited in claim 15 , wherein providing for producing a pattern of data storage is configured to recursively generate swap codes.
17 . A system for providing conflict-free memory in a Fast Walsh Transform (FWT) operation, comprising
a means for performing in-place address assignments, and
a means for storing data in a pattern that avoids memory conflicts during the FWT operation.
18 . The system recited in claim 17 , wherein the means for performing in-place address assignments is configured to employ the same address for outputs and inputs on the same wing of each butterfly.
19 . The system recited in claim 17 , wherein the means for performing in-place address assignments includes accessing common address-generation hardware for both butterfly inputs and butterfly outputs.
20 . The system recited in claim 17 , wherein the means for performing in-place address assignments includes accessing a first address-generation hardware for butterfly inputs and a second set of address-generation hardware for butterfly outputs.
21 . The system recited in claim 17 , configured for performing an inverse-FWT operation.
22 . The system recited in claim 17 , wherein the means for storing data is configured to employ an index matrix.
23 . The system recited in claim 22 , wherein the means for storing data is configured to recursively generate swap codes.
24 . A system configured for providing a conflict-free memory in a Fast Walsh Transform (FWT), comprising
an address generation component configured to provide for in-place address assignments, and
a memory-selection circuitry configured for organizing a memory into a pair of 2 M-1 -wide, 2 N -deep memory banks, and providing for conflict-free access of initial, intermediate, and final values used in a 2 N+M -point FWT operation.
25 . The system recited in claim 24 , wherein the address generation component is configured to employ the same address for outputs and inputs on the same wing of each butterfly.
26 . The system recited in claim 24 , wherein the address generation component includes common address-generation hardware for both butterfly inputs and butterfly outputs.
27 . The system recited in claim 24 , wherein the address generation component includes one set of address-generation hardware for butterfly inputs and a different set of address-generation hardware for butterfly outputs.
28 . The system recited in claim 24 , further configured to reside in at least one of a microprocessor, a digital signal processor, an application specific integrated circuit, and a field programmable gate array.
29 . The conflict-free memory system recited in claim 24 , configured to function with an inverse-FWT operation.
30 . The system recited in claim 24 , wherein the memory-selection circuitry is configured to employ an index matrix for providing the pattern of data storage.
31 . The system recited in claim 30 , wherein the memory-selection circuitry is configured to recursively generate swap codes.
32 . A method for providing conflict-free memory in a Fast Walsh Transform (FWT) operation, comprising
providing for performing in-place address assignments, and
providing for organizing a memory into a pair of 2 M-1 -wide, 2 N -deep memory banks and providing for conflict-free access of initial, intermediate, and final values used in a 2 N+M -point FWT operation.
33 . The method recited in claim 32 , wherein providing for performing in-place address assignments is configured to employ the same address for outputs and inputs on the same wing of each butterfly.
34 . The method recited in claim 32 , wherein providing for performing in-place address assignments includes accessing common address-generation hardware for both butterfly inputs and butterfly outputs.
35 . The method recited in claim 32 , wherein providing for performing in-place address assignments includes accessing a first address-generation hardware for butterfly inputs and a second set of address-generation hardware for butterfly outputs.
36 . At least one of a microprocessor, a digital signal processor, an application specific integrated circuit, and a field programmable gate array configured to perform the method recited in claim 32 .
37 . The method recited in claim 32 , configured for functioning with an inverse-FWT operation.
38 . The method recited in claim 32 , wherein providing for organizing includes employing an index matrix.
39 . The method recited in claim 38 , wherein providing for organizing is configured to recursively generate swap codes.
40 . A system for providing conflict-free memory in a Fast Walsh Transform (FWT) operation, comprising
a means for performing in-place address assignments, and
a means for organizing a memory into a pair of 2 M-1 -wide, 2 N -deep memory banks and providing for conflict-free access of initial, intermediate, and final values used in a 2 N+M -point FWT operation.
41 . The system recited in claim 40 , wherein the means for performing in-place address assignments is configured to employ the same address for outputs and inputs on the same wing of each butterfly.
42 . The system recited in claim 40 , wherein the means for performing in-place address assignments includes accessing common address-generation hardware for both butterfly inputs and butterfly outputs.
43 . The system recited in claim 40 , wherein the means for performing in-place address assignments includes accessing a first address-generation hardware for butterfly inputs and a second set of address-generation hardware for butterfly outputs.
44 . The system recited in claim 40 , configured for performing an inverse-FWT operation.
45 . The system recited in claim 40 , wherein the means for organizing is configured to employ an index matrix.
46 . The system recited in claim 45 , wherein the means for organizing is configured to recursively generate swap codes.